lw-A Comperhensive
2024-10-13 16:39:27 0 举报AI智能生成
haha
作者其他创作
大纲/内容
过滤
过滤类型
一轮过滤方法：只利用单个节点的局部特征。这些方法简单快速，但可能产生较多的误报
传播过滤技术：一个顶点过滤后的结果可以用于优化其邻居的过滤结果
过滤规则
局部过滤
传播过滤
领域的使用
不同的算法会设计了不同的辅助数据结构来考虑过滤中的邻域
最新的工作
集中在设计严格的过滤规则，以实现具有较少误报的候选集。
匹配顺序
数据无关顺序
依赖于查询图的结构，不依赖于数据图的内容，eg：例如，RI（Reverse Iteration）算法选择查询图中度数最大的顶点作为起始顶点，然后迭代选择具有最多后向邻居的顶点。
数据相关顺序
结合了查询图和数据图的信息来生成有效的匹配顺序。eg：VF2++算法首先选择具有最小标签选择性的顶点，并迭代选择具有最多后向邻居的顶点。
动态顺序
顶点标签的分布可能在不同区域是不均衡的。所以一边迭代一边选择匹配顺序
之前有一篇论文的配对顺序可以类比，1首先快速估计各个区间的运算时间2.优先匹配时间短的，这样在如果支持度提前达标或者r+n-u<s(n=所有的个数，u=匹配对的个数，s=支持度，r=已经的带的支持度)的情况下提前终止运算。
枚举
关键技术
局部候选计算
在回溯的步骤中可能会要求计算可以扩展匹配的顶点集合,所以会涉及到查询图中的顶点以及顶点的邻居
剪枝策略
为了减少不必要的搜索和回溯，算法可能会采用剪枝策略来排除那些不可能产生有效匹配的搜索路径。这可以通过识别和记录失败的模式，从而避免重复相同的错误。
同时枚举多个嵌入
一些算法尝试同时枚举多个可能的匹配，而不是一个接一个地进行。这可以通过识别查询图中的对称性或等价性来实现，从而减少重复的计算
策略
一步领先（One-Step Ahead）
在回溯的最后步骤中，对于每个未访问的数据顶点，可以直接计算出完整的嵌入，而不需要进一步的回溯（没搞懂）
叶子枚举（Leaf Enumeration）
对于度数为一的叶子顶点，其匹配只依赖于其唯一的邻居。算法可以利用这一性质，通过一次枚举多个叶子顶点的匹配来提高效率。
核壳搜索（Kernel-and-Shell Search）
将图中的顶点分为核顶点集合（连通的点集合）和壳顶点集合（前者的补集，被前者分开后各自都不相连接），对核顶点集进行回溯，对壳顶点集合直接匹配
实验
评定指标
平均候选规模
过滤后的平均候选大小，表示过滤算法的有效性。一个优秀的过滤技术应该能够显著减少候选集的大小，同时保留所有可能的匹配。
每秒嵌入数(EPS)
考虑到经过的时间和报告的嵌入数量，EPS被定义为每秒返回的平均嵌入数量，并提供跨时间和输出大小限制的算法性能的一致评估。由于EPS是一种效率度量（如速度），因此需要注意的是，较大的EPS分数不一定与较大数量的结果相关。
实验过程
测试了各种各样的算法在相同数据集下的情况，部分算法在哪种情况下运行的情况最好，以及算法在不同的类型的数据集合下各个表现的优劣和原因。同时将过滤、排序、枚举算法之间分类比较性能和将三种类别组合起来在相同数据集下比较。
其他方法
通过改变迭代时候的树宽去比较算法
评估技术组合的可伸缩性：：通过改变顶点数V、边数E和顶点标签大小Σ在合成数据集上进行实验
子图匹配算法的分类（补充）
基于连接（用于并行运算）
二元连接
最坏情况最优连接
探索（基于内存单线程）
混合
收藏
0 条评论
下一页
