翻译:Efficient parallel branch-and-bound approaches for exact graph edit distance problem

, 评论

是一个作业,但是是自己第一次这么看论文,所以发一下

来自链接

摘要

图编辑算法(Graph Edit Distance ,GED)是一种在图匹配领域广泛使用的方法.它通过计算将一个图转化成另一个图的最小编辑成本来衡量两个图的相似性或差异性.这个过程看起来很简单,但是是NP难问题并且非常耗时,因为它的搜索空间是指数级增加的.一个解决这个问题的最优算法是分支限界法(Branch and Bound，B&B),通过对搜索空间进行隐式枚举而不是而不是基于剪枝技术的全部枚举,来减少探索整个搜索空间的实践.然而当处理大型问题实例的时候,B&B算法探索整个搜索空间所需要的时间仍然太长了,它在此时依然是不够有效的.为了解决这个问题,在本文中我们提出了三种基于共享内存的B&B并行方法来利用多核CPU处理器.第一种是一种工作窃取的方法,多个B&B实例并发搜索单个搜索树,比顺序版本最多快24倍.其次是一种基于树的方法,由独立的B&B实例同时搜索搜索树的多个部分,能够提速28倍,最后,由于GED问题的不规则特性,提出了两种负载均衡策略来保证并行进程之间的负载均衡,达到了令人惊叹的300倍,所有的实验都在知名的数据集上进行过了.

1. 介绍

图编辑算法(Graph Edit Distance ,GED)是一种在图匹配领域广泛使用的方法来计算两个图之间的最小距离.GED算法的目的是计算两个图之间的不相似的总和.换句话说,它代表将一个图编辑成另一个图所需要的最优操作集的成本1.允许的操作包括插入,删除和增加,这三种操作可以运用在顶点或者边上.这个问题由于其NP难特性而被认为是非常具有挑战性的2,这意味着计算两个图之间最小距离的时间复杂度随着顶点数量的增加呈指数级增长.GED的重要性来自于它的多种使用用例.它可以用于精确匹配也可以用于能容忍一定错误的非精确匹配.并且,GED可以用于多种领域3,特别是在与模式识别相关的领域,比如手写识别456,个人识别和认证(例如指纹识别)7,文档分析8910,和图数据库搜索11.它也可以被用于机器学习,最近邻居分类和数据挖掘领域.12

为了计算两个图之间的最佳编辑距离,蚊香13经常使用的基于A*14的搜索算法.然而,这种方法需要大量内存资源,这使得其不能被用于处理大型的图.分支限界法(B&B)是一种广为人知的技术,它通过智能枚举搜索空间来解决最优化问题.这个方法用两个组件,分支(branching)和界限(bounding),将搜索空间建模成一棵树.分支是一个递归的过程,它将一个给定问题的搜索空间划分成多个更小的子问题,并对这些子问题用同样的方式处理,知道找到解决方法.在分支过程结束后,界限操作符评估每一个生成的子问题是否可能包含好的解决方案.B&B算法使用多种技术(消除和选择)来避免探索没有最优解可能的子问题(分支)并家扩搜索过程.由于GED问题的复杂性,它对于一般图来说是NP难问题15,B&B算法需要很长的实践去找到最优解,特别是在解决大型图问题的时候.为了客服这个缺点,我们认为并行计算是一个减少这类问题的运行时间的有趣的方法.

在这片论文之中,我们研究了利用单台计算机的计算资源所带来的影响和可能的收益.事实上,现在的的大部分计算机从硬件上来看都是并行的,能够提供可观的计算能力,尽管在大部分情况下都没能被利用.因此.也为了评估使用并行方法可能得到的收益,我们提出了几种B&B算法.这里的目的是评估每一个并行方法在减少执行时间和有效探索整个搜索空间的影响和行为.我们给出的方法可以归类成高级并行化,其中多个B&B算法的实例同时探索搜索空间.

本文提出了两个并行算法,第一种是基于工作窃取策略,用以在不额外增加内存使用的条件下加快对搜索树的顺序搜索.因此,我们用多个B&B实例同时探索同一颗存储在共享内存空间中的搜索树,所有并行的B&B实例都可以对这个搜索树进行读/写操作.在参考数据集上使用16核CPU的实验显示,相对于顺序版本,速度提升24倍.为了更有效地探索这个搜索空间,也为了研究多样化的影响,我们提出了第二个B&B算法.后者用基于树的方法表示,用多个独立的B&B实例并行地探索整个搜索树的多个部分.因此,更新上界(UB),这最终能够改善一定复杂度.这个算法基于主从策略(Master-Worker),主节点将搜索树分成多个B&B实例,也就是工作者(Workers),在这之后,每一个工作者在自己的内存空间之中构建自己独有的搜索树,进程间唯一共享的信息就是更新的上界的值,这在每一次一个更优路径被发现的时候更新.这个算法得到的结果显示多样化探索过程对性能产生了积极的影响,相比于顺序B&B实例,提速了约28倍.然而,因为搜索树中的子问题的负载不均衡,许多工作者很快地结束了工作(空闲),然而其他会需要运行很长的时间.解决GED问题的负载平衡策略的影响在Abu-Aisheh等人的研究16，17中没有得到很好的研究.因此,我们提出了两种原创的负载均衡策略来避免工作者的共线.我们的第一种负载均衡策略包括将主节点当做负载均衡器,听过改变它的搜索策略来保证子问题的大量可用性.这个避免空闲的想法就是给所有的并行工作者读写权限来让它们在自己的工作池为空的时候从负载均衡器的工作池之中选取一个子问题.第二种保证工作者之间的负载平衡的方法是将前两个并行算法结合起来.这里的想法是允许工作者在本地进行次迭代,接着将它们自己本地工作池整合进一个共享的全局工作池.用参看数据集刨出来的结果显示了将多样性和负载均衡结合起来带来的好的影响,并且,增加负载均衡算法能够将基于树的并行算法提升高达11倍.

本文余下的内容总结如下.在第二节提出了一些基础的有关GED的符号和定义,在第三节中,我们讨论相关的工作.在第四节描述了串行B&B算法和它的组成,在第五节我们详细介绍我们提出的并行B&B算法和负载均衡策略.在第六节报告计算结果,最终,在第七节提出了结论和展望.

2.问题定义

在接下来的部分,我们首先定义了一些基本的概念接下来去正式地定义GED问题

2.1图(Graph)

一个图是一个用于建模对象之间的成对关系的结构.18,它包含了一组由一组边连接起来顶点,

正式定义中,一个带标签的图可被表示为,在其中

  • ,表示包含n个顶点的集合
  • .表示包含个边的集合
  • 是顶点的标记函数，也就是将每个顶点映射到一个标记的函数，表示为:
  • 是边的标记函数，也就是将每个边映射到一个标记的函数，表示为:. 和被限制为可以由一组整数描述的标签,向量空间或者符号标签

在这篇论文之中,我们考虑简单的无向无环标记图.

2.2 GED操作

在GED问题之中,一个将图转换成图的编辑路径由一组图的编辑操作组成.每一个编辑操作对顶点,边或者顶点和边执行一次操作.在本文之中,我们采用一种以顶点为中心的方法,其变形都是在顶点上进行的,而其中隐含了对边的操作.因此,只有一下三种基本备案及操作是被允许的:插入(),删除()和替换()

我们描述一个顶点来自于图,以及领一个顶点来自于图,我们表示为

  1. 将顶点替换为
  2. ,顶点从之中删除
  3. 顶点加入到之中

2.2.1隐含的边操作

在以顶点为中心的算法之中,对于边的编辑操作是隐含的,事实上,一个边的替换,删除或者增加取决于它的相关顶点的编辑操作19.让我们考虑图之中的两个顶点,和另外两个顶点在图之中.如果我们在顶点和进行如下的两个编辑操作和.可以分别区分出三种边的隐含操作:

  1. 如果在中和之间存在一个边,也存在一个边连接和,那么就被替换掉,表示为
  2. 如果在中和之间存在一个边,而之中没有连接和的边,那么就在之中删除,表示为
  3. 如果如果在中和之间不存在边而存在一个边,那么就被加入到了之中,表示为

注意当一个顶点从之中删除的时候,与它相连的所有边都被自动删除,类似地,吐过一个顶点被插入进所有在之中预期相连的边会被插入,如果这个边的另一个端点已经存在于之中

2.3成本函数

在GED之中,成本函数是一个重要的组成部分.成本函数为每一个对于边或者顶点的操作分配一个值(成本).因此,图编辑的成本分配影响着最优编辑路径.成本函数提供了一个将与对象相似性有关的领域信息融入进来的有效方法.对于一个特定操作的成本实在底层标签字母表的层面定义的,三种编辑操作的成本给出如下

我们应该注意如果这两个顶点或者边的拥有相同便签的时候,其替换成本为0.

2.4图编辑距离

让和为源图和目标图,分别地,和之间的图编辑距离由表示,代表着两个图之间的差异程度.换句话说,它代表着一组将转换成的最优编辑集合(在成本角度上)

最终,和之间的图编辑距离(GED)定义为

其中表示为所有的将转化成的编辑路径的集合.每一个路径都包含着一组编辑操作,并且表示编辑操作的成本20

2.5举例

我们将源和目的图表示在在图1之中,我们让删除和插入的操作成本为2,替换的成本为1,那么将图编辑成图的最优路径可以由操作四个顶点的替换得到,这意味着要替换三条边,并且删除其他的两条,完整编辑路径如下

因此将转化成的最优路径的成本

Fig. 1. Both source and target graphs.

图1:源图和目的图

3.相关工作

在模式识别之中,一个真实世界的对象通常由数组向量(图)来表示.这种表示对评议,缩放和旋转等操作是敏感的,因此我们用以图为基础的表示方法来克服这些问题.以图为基础的表示方法具有不可更改性以及更强的表现能力,因为我们可以在断电或者边上增加信息.精确匹配(Exact-GED)假设环境是无噪音的,因此它认为当且仅当两个图(和)之间的图编辑距离(GED(,))为0的时候,二者是匹配的.然而,由于噪音因素,相同对象的两个图可能并不完全匹配.在这种情况下,我们称之为非精确匹配(Inexact-GED),当两个图之间的编辑路径在给定阈值的以下的时候就认为是可以接受的陪陪.因此,GED可以在精确匹配和非精确匹配的场景之中运用.一些应用需要将一个图转化成另一个的最优方法(编辑路径).因此它们通常使用最优化算法,像是A*和B&B算法.额俺儿,B&B算法也可以被用于得到一个次优解,例如在计算规定时间之后就停止.在本节的剩余部分,我们会着重于现有的最优GED问题的处理工作,这些工作基于树遍历和并行计算.21

在1983年A. Sanfeliu 和 K.-S. Fu 提出了GED22,而在其出版的同一年,Bunke 和 Allermann23 首次实现并调整A*算法来解决GED问题.他们的想法是将第一个图的所有元素映射到第二个图之中来寻找最优解.因此,生成了一个为所有可能解建模的搜索树.映射使用三种编辑操作:删除,增加和替换.他们用一些小规模的图证明了这一算法.

A*GED算法能够找到最优解,但是存在巨大的计算和空间复杂度.在这一篇论文中24,作者提出了GED问题的近似算法,称之为A*-波束搜索(A*-Beamsearch).这个算法用一个特定的大小s来限制A*的优先队列的大小,只保留有s个具有醉的成本(实际成本+估计成本)的编辑路径,波束搜索的队列越大,这个算法越准确.

为了加速A*算法的搜索过程,Riesen 等人25 提出了一个二分启发算法 (bipartite heuristic),来给出对于成本下界(h)的评估.这个启发式基于二部图匹配.首先,创建两个成本矩阵,分别对应图一和图二之间的三种操作所对应的顶点和边的不同分配情况.之后,用Munkres算法2627来分别计算出边和点的最佳分配.最后,近似值h就是边的最优分配和顶点的最优分配之和,在28这篇论文之中,作者用他们的启发式算法近似地解决了GED问题.因此,为这个问题提出了一个很好的上界.二分启发式算法在2930中被进一步讨论和优化来更准确地计算下界

在31这篇论文中,Abu-Aisheh等人使用深度优先算法(DFS)来最优地解决GED问题.这位作者的目标是相比对于A*算法来减少大量使用的内存空间.这个算法在开始的时候使用Munkres算法来对顶点进行排序,然后用DFS策略来探索搜索空间.在32这篇论文中,作者提出了一种DF-GED的共享内存并行方法,称之为PDFS.在PDFS之中,多个并行的DF-GED实例同时探索搜索空间.并且,这位作者使用了负载均衡策略避免并行线程的空闲.最后结果显示,相比于DF-GED,这个算法提升了20%.但是这个实验并没有用经典指标(加速比和效率)来表示并行化和负载均衡策略的影响.在33之中,作者提出了一个DF-GED算法分布式内存版本.他们给出的并行方法使用主从模式,并且使用Hadoop framework34实现.这个分布式版本在运行时间上与串行版本相近.

在35之中, Gouda 和 Hassaan提出了一个称之 CSI_GED 的基于边的深度优先算法来解决统一的GED问题,统一的GED问题指的是所有的编辑操作的成本都是相同的.这位作者的主要想法就是将第一张图的所有边都用射到第二张图的边上,顶点隐含在其中,详细的实验部分验证了所提出的方法.

在36[^25]之中Blumenthal和Gamper修改了在37中的DF-GED算法,以解决具有统一编辑成本的GED问题.在这种情况下,使用Munkres算法估算成本的时间复杂度可以从立方降低到线性时间.在同一篇论文之中,作者提出了在38中的CSI_GED算法的一般化,称其为CSI_GEDnu来覆盖非统一编辑成本问题.这个一般化算法使用Munkres算法39来计算未来预估成本.在[^26]之中,相同的作者提出了一个用来近似或者准确地解决GED问题的C++的库,称之为GEDLIB.这个库包含了多种用于GED的文献算法,也可以是其他新算法的基础实现.

在[^27]之中,Chang等人提出了了GED问题的新的下界,这极大减少了DFS算法和A*算法的内存占用.在这个下界的基础上,他们开发了能够处理多达六十个顶点的图的AStar+-LSa 和 AStar+-BMa算法.

在[^28]中,Wang等人针对精确GED问题提出了在[^27]中提出的AStar+-LSa算法的并行实现.他们的并行算法被称之为PGED,其主要思想是将A*算法最耗时的步骤(搜索和最优顶点映射)分配给多个线程同时执行.他们的实验结果显示,与算法的串行版本相比,快了两倍.

在精准匹配领域,Allen等人在1997年发表了一个并行算法[^29].他们的算法适用于两个拥有相同顶点数量的图,其中距离的计算称之为关系距离,通过寻找让和对其的最优顶点排列就能找到和之间的最优匹配.对于每一种可能的排列,会对和之间的边进行比较,对于每一条不匹配的边,会增加一个错误.并行部分基于启发式B&B搜索算法来计算出和之间的估计距离(下界).一个很重要的观点认为,该算法被设计为适用于单指令流/多数据流(SIMD)并行性的特定体系结构,这个实验在10个顶点到27个顶点的中小型图上进行,用拥有1024个处理器的大规模并行计算.

因为GED问题的NP难特性,计算出来小型图的最短距离就要花费很长时间.因此.大部分上述的文献只用小型的数据集或者在特定时间内探索部分搜索树来在概念上证明其算法.在[^30]之中,我们提出了一个基于树的近似方法来算出一个接近最优解的结果.因为探索整个搜索树是不切实际的,这个算法在每棵树层中只保留最优节点用以后续探索,这极大减少了计算时间也并没有损耗太多解决方案的质量.

为了解决更大的图,也为了报告并行在最优解决精准GED问题上的影响,我们提出了几种并行的B&B算法和负载均衡策略来加快搜索过程以及尽可能地有效利用现代计算机的可用计算资源.

https://ars.els-cdn.com/content/image/1-s2.0-S0167819122000734-fx1001.jpg

download

4.GED的B&B算法

分支限界法(B&B)是广泛用于最优解决组合优化问题的基数.它在1960年被A. H. Land 和 A. G. Doig提出用以解决离散规划问题[^31].这些算法对整个搜索空间进行智能而准确地枚举,将其建模成一个搜索树,并对这颗搜索树用分支限界操作来探索.分支限界法的目的是去找到将一个图转换成另一个图从成本角度来说最优的编辑路径.搜索树的节点的分支操作会将它的搜索空间分解成几个更小的子问题而产生一组后继节点.这些后继节点会同样进行分支操作直到找到解决方法.在分支之后,限界操作评估每一个后继节点的改善已经找到的找到最优解的能力.如果不能改善,对该分支修剪并删除后续结点,此外,算法1描述了使用B&B算法的一般结构.

在接下来的内同理,我们介绍对B&B算法的几种操作进行修改让其适用于GED问题.

4.1 分支

B&B算法在由整个搜索空间建模成的搜索树上进行分支操作,B&B的搜索树用分支操作生成.它将问题(树的节点)分解成若干较小子问题,并对这些子问题重复上述操作直到达到叶子结点.对GED问题的分支是基于将图g1的节点映射到图g2的节点上的思想,也就是说,我们用以顶点为中心的算法,映射操作执行几种传统的图编辑操作:增加,删除和替换.形式上,一个搜索树的节点的特征包括

  • 一组已知的过去编辑操作,称为路径(path),表示为其中是编辑操作之一(增加,删除和修改)
  • 两个图(和)中剩余的节点,分别表示为和
  • 两个图(和)中已经加工的节点,分别表示为和

在上述情况下,根节点(最初的问题)可以被定义为

对于一个搜索树节点的分支操作都会通过将一个顶点替换成在之中的任意一个结点来产生个后继节点.换句话说,每个后继节点表示一个节点通过节点进行映射,定义如下

(需要注意的是这里的)

除了上述的后续子节点的生成方法之外,我们增加了一个表示顶点被删除后产生后续结点.定义如下

这个过程会一直重复直到到达叶子节点,也就是在这种情况下,如果和第二张图有关的剩余的节点不为空()我们一次性地将中剩下的所有节点插入,表示如下

图2展示了一个用以解决GED问题的搜索树的例子,在这个图的每一个层次,来自第一个图的一个顶点被中的剩余节点以及生成删除操作的映射.

Fig2

图2,与GED问题相关的一般搜索树方案

5.提出的GED问题的B&B并行算法

6.表现分析

7.结论和展望

引用

  1. Inexact graph matching for structural pattern recognition 链接↩︎

  2. Comparing stars: On approximating graph edit distance 链接↩︎

  3. Structural Pattern Recognition with Graph Edit Distance: Approximation Algorithms and Applications, Advances in Computer Vision and Pattern Recognition, Springer International Publishing (2016) 链接↩︎

  4. K. Riesen, S. Fankhauser, H. Bunke, Speeding Up Graph Edit Distance Computation with a Bipartite Heuristic, in: MLG, 2007. Google Scholar↩︎

  5. Approximate graph edit distance computation by means of bipartite graph matching 链接↩︎

  6. Z. Abu-Aisheh, R. Raveaux, J.-Y. Ramel, P. Martineau, An exact graph edit distance algorithm for solving pattern recognition problems, in: 4th International Conference on Pattern Recognition Applications and Methods 2015, 2015. Google Scholar↩︎

  7. Approximate graph edit distance guided by bipartite matching of bags of walks 链接↩︎

  8. Approximate graph edit distance computation by means of bipartite graph matching 链接↩︎

  9. A graph distance measure for image analysis 链接↩︎

  10. Recent advances in graph-based pattern recognition with applications in document analysis 链接↩︎

  11. Graph similarity search with edit distance constraint in large graph databases 链接↩︎

  12. Approximate graph edit distance computation by means of bipartite graph matching 链接↩︎

  13. Structural Pattern Recognition with Graph Edit Distance: Approximation Algorithms and Applications, Advances in Computer Vision and Pattern Recognition, Springer International Publishing (2016) 链接↩︎

  14. A formal basis for the heuristic determination of minimum cost paths 链接↩︎

  15. Comparing stars: On approximating graph edit distance 链接↩︎

  16. Z. Abu-Aisheh, R. Raveaux, J.-Y. Ramel, P. Martineau, A Distributed Algorithm for Graph Edit Distance, in: DBKDA 2016, 2016, p. 76. Google Scholar↩︎

  17. A parallel graph edit distance algorithm 链接↩︎

  18. Introduction to Graph Theory, vol. 2 Google Scholar↩︎

  19. Approximate graph edit distance computation by means of bipartite graph matching 链接↩︎

  20. Approximate graph edit distance computation by means of bipartite graph matching 链接↩︎

  21. Thirty years of graph matching in pattern recognition 链接↩︎

  22. A distance measure between attributed relational graphs for pattern recognition 链接↩︎

  23. Inexact graph matching for structural pattern recognition 链接↩︎

  24. Fast suboptimal algorithms for the computation of graph edit distance 链接↩︎

  25. K. Riesen, S. Fankhauser, H. Bunke, Speeding Up Graph Edit Distance Computation with a Bipartite Heuristic, in: MLG, 2007. Google Scholar↩︎

  26. Algorithms for the assignment and transportation problems 链接↩︎

  27. Assignment Problems: Revised Reprint 链接↩︎

  28. Approximate graph edit distance computation by means of bipartite graph matching 链接↩︎

  29. Computing upper and lower bounds of graph edit distance in cubic time 链接↩︎

  30. Correcting and speeding-up bounds for non-uniform graph edit distance 链接↩︎

  31. Z. Abu-Aisheh, R. Raveaux, J.-Y. Ramel, P. Martineau, An exact graph edit distance algorithm for solving pattern recognition problems, in: 4th International Conference on Pattern Recognition Applications and Methods 2015, 2015. Google Scholar↩︎

  32. A parallel graph edit distance algorithm 链接↩︎

  33. Z. Abu-Aisheh, R. Raveaux, J.-Y. Ramel, P. Martineau, A Distributed Algorithm for Graph Edit Distance, in: DBKDA 2016, 2016, p. 76. Google Scholar↩︎

  34. Hadoop-The Definitive Guide: Storage and Analysis at Internet Scale (revised and updated) Google Scholar↩︎

  35. Csi_Ged: An efficient approach for graph edit similarity computation 链接↩︎

  37. Z. Abu-Aisheh, R. Raveaux, J.-Y. Ramel, P. Martineau, An exact graph edit distance algorithm for solving pattern recognition problems, in: 4th International Conference on Pattern Recognition Applications and Methods 2015, 2015. Google Scholar↩︎

  38. Csi_Ged: An efficient approach for graph edit similarity computation 链接↩︎

  39. Algorithms for the assignment and transportation problems 链接↩︎

Noirking's Pawn

个人简介。