Computer Science ›› 2018, Vol. 45 ›› Issue (4): 11-18.doi: 10.11896/j.issn.1002-137X.2018.04.002

Previous Articles     Next Articles

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

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!
Full text



[1] . [J]. Computer Science, 2018, 1(1): 1 .
[2] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75 .
[3] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[4] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[5] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[6] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99 .
[7] ZHOU Yan-ping and YE Qiao-lin. L1-norm Distance Based Least Squares Twin Support Vector Machine[J]. Computer Science, 2018, 45(4): 100 -105 .
[8] LIU Bo-yi, TANG Xiang-yan and CHENG Jie-ren. Recognition Method for Corn Borer Based on Templates Matching in Muliple Growth Periods[J]. Computer Science, 2018, 45(4): 106 -111 .
[9] GENG Hai-jun, SHI Xin-gang, WANG Zhi-liang, YIN Xia and YIN Shao-ping. Energy-efficient Intra-domain Routing Algorithm Based on Directed Acyclic Graph[J]. Computer Science, 2018, 45(4): 112 -116 .
[10] CUI Qiong, LI Jian-hua, WANG Hong and NAN Ming-li. Resilience Analysis Model of Networked Command Information System Based on Node Repairability[J]. Computer Science, 2018, 45(4): 117 -121 .