计算机科学 ›› 2018, Vol. 45 ›› Issue (4): 11-18.doi: 10.11896/j.issn.1002-137X.2018.04.002

• 综述 • 上一篇    下一篇

图编辑距离概述

徐周波,张鵾,宁黎华,古天龙   

  1. 桂林电子科技大学广西可信软件重点实验室 广西 桂林541004,桂林电子科技大学广西可信软件重点实验室 广西 桂林541004,桂林电子科技大学广西可信软件重点实验室 广西 桂林541004,桂林电子科技大学广西可信软件重点实验室 广西 桂林541004
  • 出版日期:2018-04-15 发布日期:2018-05-11
  • 基金资助:
    本文受国家自然科学基金(61572146,61363030,U1501252,61762027),广西自然科学基金(2017GXNSFAA198172,2015GXNSFAA139285,2014GXNSFAA118354),桂林电子科技大学研究生教育创新计划项目(2017YJCX08,2017YJCX54)资助

Summary of Graph Edit Distance

XU Zhou-bo, ZHANG Kun, NING Li-hua and GU Tian-long   

  • Online:2018-04-15 Published:2018-05-11

摘要: 图编辑距离是图模式匹配技术中常用的方法之一。基于图编辑距离的匹配方法能够处理多种类型的图数据,因而受到了学术界的广泛关注。首先介绍了图编辑距离的相关概念;然后简述了基于启发式搜索技术的精确图编辑距离算法,重点分析了基于二分图匹配的近似图编辑距离算法;最后对现存的一些图编辑问题进行了总结,并对未来的发展趋势进行了展望。

关键词: 图编辑距离,二分图匹配,A算法,Hausdorff匹配

Abstract: Graph edit distance is one of the most flexible and general graph pattern matching models available.This matching method has provoked wide concern from scholars owing to its capability to handle many kinds of graph data.Firstly,the related concepts of graph edit distance were introduced.Then the exact graph edit distance algorithms based on heuristic search technology were described briefly,and the inexact edit distance algorithms of bipartite graph matching was emphaticallyanalyzed.Finally,some existing problems were summarized,and the future development trend was simply discussed.

Key words: Graph edit distance,Bipartite graph matching,A* algorithm,Hausdorff matching

[1] FOGGIA P,PERCANNELLA G,VENTO M.Graph Matching and Learning in Pattern Recognition in the Last 10 Years[J].International Journal of Pattern Recognition & Artificial Intelligence,2014,28(1):178-215.
[2] YU J,LIU Y B,ZHANG Y,et al.Survey on Large-Scale Graph Pattern Matching[J].Journal of Computer Research and Deve-lopment,2015,52(2):391-409.(in Chinese) 于静,刘燕兵,张宇,等.大规模图数据匹配技术综述[J].计算机研究与发展,2015,52(2):391-409.
[3] BORGWARDT K M,ONG C S,SCHNAUER S,et al.Proteinfunction prediction via graph kernels[J].Oral Radiology,2005,6(2):29-35.
[4] HARCHAOUZI Z,BACH F.Image Classification with Segmentation Graph Kernels[C]∥IEEE Conference on Computer Vision & Pattern Recognition(Cvpr 07).IEEE,2007:1-8.
[5] SHOUBRIDGE P,KRAETZL M,WALLIS W,et al.Detection of Abnormal Change in A Time Series of Graphs[J].Journal of Interconnection Networks,2002,3(3):85-101.
[6] CONTE D,FOGGIA P,SANSONE C,et al.Thirty Years of Graph Matching in Pattern Recognition[J].International Journal of Pattern Recognition & Aritificial Intelligence,2011,8(3):265-298.
[7] BUNKE H,ALLERMANN G.Inexact graph matching forstructural pattern recognition[J].Pattern Recognition Letters,1983,1(4):245-253.
[8] GAO X,XIAO B,TAO D,et al.A survey of graph edit distance[J].Pattern Analysis and Applications,2010,13(1):113-129.
[9] CORTS X,SERRATOSA F.Learning graph-matching edit-costs based on the optimality of the oracle’s node correspondences[J].Pattern Recognition Letters,2015,56:22-29.
[10] SOL-RIBALTA A,SERRATOSA F,SANFELIU A.On theGraph Edit Distance cost:Properties and Applications[J].International Journal of Pattern Recognition & Artificial Intelligence,2012,25(5):53-61.
[11] BERRETTI S,BIMBO A D,VICARIO E.Efficient Matchingand Indexing of Graph Models in Content-Based Retrieval[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2001,3(10):1089-1105.
[12] GREGORY L,KITTLER J.Using Graph Search Techniques for Contextual Colour Retrieval[C]∥Joint Iapr International Workshop on Structural,Syntactic,and Statistical Pattern Re-cognition.Springer-Verlag,2002:186-194.
[13] ABU-AISHEH Z,RAVEAUX R,RAMEL J Y,et al.An Exact Graph Edit Distance Algorithm for Solving Pattern Recognition Problems[C]∥4th International Conference on Pattern Recognition Applications and Methods.Lisbon,Portugal,2015:271-278.
[14] ABU-AISHEH Z,RAVEAUX R,RAMEL J Y,et al.A Distri-buted Algorithm for Graph Edit Distance[C]∥The Eighth International Conference on Advances in Databases,Knowledge,and Data Applications.Lisbon,Portugal,2016:66-71.
[15] RIESEN K,BUNKE H.Approximate graph edit distance computation by means of bipartite graph matching[J].Image & Vision Computing,2009,27(7):950-959.
[16] FISCHER A,SUEN C Y,FRINKEN V,et al.Approximation of graph edit distance based on Hausdorff matching[J].Pattern Recognition,2015,48(2):331-343.
[17] SERRATOSA F,CORTS X.Graph Edit Distance:Movingfrom global to local structure to solve the graph-matching pro-blem [J].Pattern Recognition Letters,2015,65:204-210.
[18] FISCHER A,RIESEN K,BUNKE H.Improved Quadratic Time Approximation of Graph Edit Distance by Combining Hausdorff Matching and Greedy Assignment[J].Pattern Recognition Letters, 2017,87:55-62.
[19] AMBAUEN R,FISCHER S,BUNKE H.Graph Edit Distance with Node Splitting and Merging,and Its Application to Diatom Idenfication[C]∥Iapr International Conference on Graph Based Representations in Pattern Recognition.Springer-Verlag,2003:95-106.
[20] LEVENSHTEIN V I.Binary codes capable of correcting dele-tions,insertions and reversals[J].Problems of Information Transmission,1966,0(1):707-710.
[21] PROBLEM T T E.The tree-to-tree editing problem[J].Information Processing Letters,1977,6(6):184-186.
[22] ESHERA M A,FU K S.A graph distance measure for imageanalysis[J].IEEE Transactions on Systems Man & Cyberne-tics,1984,4(3):398-408.
[23] RIESEN K.Structural Pattern Recognition with Graph EditDistance:Approximation Algorithms and Applications[M].Springer Publishing Company,Incorporated,2016:14-135.
[24] WEI J.Markov edit distance[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2004,26(3):311-321.
[25] WAGNER R A,FISCHER M J.The String-to-String Correction Problem[J].Journal of the ACM,1974,21(1):168-173.
[26] BUNKE H.Error Correcting Graph Matching:On the Influence of the Underlying Cost Function[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,1999,21(9):917-922.
[27] BUNKE H.On a relation between graph edit distance and maxi-mum common subgraph[J].Pattern Recognition Letters,1997,18(9):689-694.
[28] MALTONI D,MAIO D,JAIN A K,et al.Handbook of Fingerprint Recognition[M].New York:Springer-Verlag,2009:12-50.
[29] CAETANO T S,MCAULEY J J,CHENG L,et al.Learninggraph matching [J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2008,31(6):1048-1058.
[31] NEUHAUS M,BUNKE H.Automatic learning of cost func-tions for graph edit distance[J].Information Sciences,2007,177(1):239-247.
[32] WONG A K C,YOU M.Entropy and Distance of RandomGraphs with Application to Structural Pattern Recognition[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,1985,7(5):599-609.
[33] SERRATOSA F,ALQUEZAR R,SANFELIU A.Function-described graphs for modelling objects represented by sets of attributed graphs[J].Pattern Recognition,2003,36(3):781-798.
[34] SANFELIU A,SERRATOSA F,ALQUZAR R.Second-Order Random Graphs for modelling sets of Attributed Graphs and their application to object learning and recognition[J].International Journal of Pattern Recognition & Artificial Intelligence,2011,18(3):375-396.
[35] NEUHAUS M,BUNKE H.A probabilistic approach to learning costs for graph edit distance[C]∥ Proceedings of IEEE International Conference on Pattern Recognition.2004:389-393.
[36] NEUHAUS M,BUNKE H.Self-organizing maps for learningthe edit costs in graph matching[J].IEEE Transactions on Systems Man & Cybernetics Part B Cybernetics A Publication of the IEEE Systems Man & Cybernetics Society,2005,35(3):503-514.
[37] SERRATOSA F,SOLRIBALTA A,CORTS X.AutomaticLearning of Edit Costs Based on Interactive and Adaptive Graph Recognition[C]∥International Conference on Graph-Based Representations in Pattern Recognition.Springer-Verlag,2011:73-78.
[38] DUMAY A C M,GEEST R J V D,G ERBRANDS J J,et al.Consistent inexact graph matching applied to labelling coronary segments in arteriograms[C]∥Iapr International Conference on Pattern Recognition.1992:439-442.
[39] RIESEN K,FANKHAUSER S,BUNKE H.Speeding Up Graph Edit Distance Computation with a Bipartite Heuristic[C]∥Proc.5th Int.Workshop on Mining and Learning with Graphs.Firence,Italy,2007:21-24.
[40] FISCHER A,PLAMONDON R,S AVARIA Y,et al.A Hausdorff Heuristic for Efficient Computation of Graph Edit Distance[C]∥Int.Workshop on Structural and Syntactic Pattern Recognition.2014:83-92.
[41] HART P E,NILSSON N J,RAPHAEL B.A Formal Basis forthe Heuristic Determination of Minimum Cost Paths[J].IEEE Transactions on Systems Science & Cybernetics,1968,4(2):100-107.
[42] NEUHAUS M,RIESEN K,BUNKE H.Fast suboptimal algo-rithms for the computation of graph edit distance[C]∥Joint Iapr International Conference on Structural,Syntactic,and Statistical Pattern Recognition.Springer-Verlag,2006:163-172.
[43] KOOPMANST C,BECKMANN M.Assignment Problems andthe Location of Economic Activities[J].Cowles Foundation Discussion Papers,1955,25(1):53-76.
[44] BOUGLEUX S,BRUN L,CARLETTI V,et al.Graph Edit Distance as a Quadratic Assignment Problem[J].Pattern Recognition Letters,2016,3(4):1-9.
[45] SERRATOSA F.Fast computation of Bipartite graph matching [J].Pattern Recognition Letters,2014,45(8):244-250.
[46] BOURGEOIS F,LASSALLE J C.An extension of the Munkres algorithm for the assignment problem to rectangular matrices[J].Communications of the ACM,1971,14(12):802-804.
[47] SERRATOSA F.Speeding up Fast Bipartite Graph MatchingThrough a New Cost Matrix[J].International Journal of Pattern Recognition & Artificial Intelligence,2014,29(2):1550010.
[48] RIESEN K,FISCHER A,BUNKE H.Approximation of Graph Edit Distance by Means of a Utility Matrix[C]∥Artificial Neural Networks in Pattern Recognition.Springer International Publishing,2016:185-194.
[49] BURKARD R E,DELL’AMICRO M,M ARTELLO S.Assignment Problems[M].Scoiety for Industrial and Applied Mathmatics,2009:9-100.
[50] FANKHAUSER S,RIESEN K,BUNKE H.Speeding up graph edit distance computation through fast bipartite matching[J].Lecture Notes in Computer Science,2011,6658(1):102-111.
[51] KUHN H W.The Hungarian method for the assignment problem[J].Naval Research Logistics,2005,52(1):83-97.
[52] MUNKRES J.Algorithms for the assignment and transportation problems[J].Journal of the Society for Industrial & Applied Mathematics,1957,5(1):32-38.
[53] JONKER R,VOLGENANT A.A shortest augmenting path algorithm for dense and sparse linear assignment problems[J].Computing,1987,38(4):325-340.
[54] JONES W,CHAWDHARY A,KING A.Optimizing the Vol-genant-Jonker algorithm for approximating graph edit distance [J].Pattern Recognition Letters,2016,13(27):1-8.
[55] RIESEN K,FERRER M,BUNKE H.Approximate Graph Edit Distance in Quadratic Time[J].IEEE/ACM Transactions on Computational Biology & Bioinformatics,2014,13(9):1-12.
[56] RIESEN K,BUNKE H.Improving bipartite graph edit distance approximation using various search strategies[J].Pattern Re-cognition,2014,48(4):1349-1363.
[57] JUSTICE D,HERO A.A binary linear programming formulation of the graph edit distance[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2006,28(8):1200-1214.
[58] RIESEN K,FISCHER A,BUNKE H.Computing Upper andLower Bounds of Graph Edit Distance in Cubic Time[C]∥Int.Workshop on Artificial Neural Networks in Pattern Recognition.2014:129-140.
[59] HUTTENLOCHER D P,KLANDERMAN G,RUCKLIDGE W J.Comparing images using the Hausdorff distance[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,1993,15(9):850-863.
[60] WILSON R C,HANCOCK E R.Structural Matching by Dis-crete Relaxation[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,1997,19(6):634-648.
[61] MYERS R,WILSON R C,HANCOCK E R.Bayesian GraphEdit Distance[J].IEEE Transactions on Pattern Analysis & Machine Intelligence,2000,22(6):628-635.
[62] CROSS A D J,WILSON R C,HANCOCK E R.Inexact graph matching using genetic search[J].Pattern Recognition,1997,30(6):953-970.
[63] BOERES M C,RIBEIRO C C,BLOCH I.A Randomized Heuristic for Scene Recognition by Graph Matching[C]∥ Experimental and Efficient Algorithms,Third International Workshop,WEA 2004.Angra dos Reis,Brazil,2004:100-113.
[64] SORLIN S,SLONON C.Reactive Tabu Search for Measuring Graph Similarity[C]∥Iapr International Conference on Graph-Based Representations in Pattern Recognition.Springer-Verlag,2005:172-182.

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
[1] 编辑部. 新网站开通,欢迎大家订阅![J]. 计算机科学, 2018, 1(1): 1 .
[2] 雷丽晖,王静. 可能性测度下的LTL模型检测并行化研究[J]. 计算机科学, 2018, 45(4): 71 -75 .
[3] 孙启,金燕,何琨,徐凌轩. 用于求解混合车辆路径问题的混合进化算法[J]. 计算机科学, 2018, 45(4): 76 -82 .
[4] 张佳男,肖鸣宇. 带权混合支配问题的近似算法研究[J]. 计算机科学, 2018, 45(4): 83 -88 .
[5] 伍建辉,黄中祥,李武,吴健辉,彭鑫,张生. 城市道路建设时序决策的鲁棒优化[J]. 计算机科学, 2018, 45(4): 89 -93 .
[6] 史雯隽,武继刚,罗裕春. 针对移动云计算任务迁移的快速高效调度算法[J]. 计算机科学, 2018, 45(4): 94 -99 .
[7] 周燕萍,业巧林. 基于L1-范数距离的最小二乘对支持向量机[J]. 计算机科学, 2018, 45(4): 100 -105 .
[8] 刘博艺,唐湘滟,程杰仁. 基于多生长时期模板匹配的玉米螟识别方法[J]. 计算机科学, 2018, 45(4): 106 -111 .
[9] 耿海军,施新刚,王之梁,尹霞,尹少平. 基于有向无环图的互联网域内节能路由算法[J]. 计算机科学, 2018, 45(4): 112 -116 .
[10] 崔琼,李建华,王宏,南明莉. 基于节点修复的网络化指挥信息系统弹性分析模型[J]. 计算机科学, 2018, 45(4): 117 -121 .