图编辑距离概述
详细信息 查看官网全文
- 英文论文题名：A Summary of Graph Edit Distance
- 论文作者：张鹍 ; 徐周波
- 英文论文作者：Zhang Kun ; Xu Zhou-bo ; Guangxi Key Laboratory of Trusted Software ; Guilin University of Electronic Technology
- 年：2016
- 作者机构：桂林电子科技大学广西可信软件重点实验室;
- 论文关键词：图编辑距离 ; 二分图匹配 ; A*算法 ; Hausdorff匹配
- 英文论文关键词：Graph edit distance ; Bipartite graph matching ; A* algorithm ; Hausdorff matching
- 会议召开时间：2016-11-25
- 会议录名称：广西计算机学会2016年学术年会论文集
- 语种：中文
- 分类号：TP391.4
- 学会代码：GXJH
- 会议名称：广西计算机学会2016年学术年会
- 会议地点：中国广西南宁
- 主办单位：广西计算机学会
- 学会名称：广西计算机学会
- 页数：11
- 文件大小：356k
- 原文格式：D
- 会议级别：地方
摘要
图编辑距离是图模式匹配技术中最常用的方法之一。根据距离值的精确与否,图编辑距离分为精确图编辑距离和容错图编辑距离。本文介绍了图编辑距离的相关概念,并简述了基于A*搜索和Hausdorff匹配的图编辑距离,着重分析了二分图匹配的近似图编辑距离算法。最后对现存的一些问题进行了总结,并对未来发展趋势做了简要的展望。
Graph edit distance is one of the most flexible and general graph pattern matching models available. According to the accuracy of the distance value, the distance between the graph edit distance is divided into the exact graph edit distance and the error-tolerant graph edit distance. In this paper, the related concepts of graph edit distance are introduced, and we described the graph edit distance based on A* search and Hausdorff matching briefly, what's more, the approximate edit distance algorithm of bipartite graph matching is emphatically analyzed. Finally, some existing problems are summarized, and the future development trend is simply discussed.
Graph edit distance is one of the most flexible and general graph pattern matching models available. According to the accuracy of the distance value, the distance between the graph edit distance is divided into the exact graph edit distance and the error-tolerant graph edit distance. In this paper, the related concepts of graph edit distance are introduced, and we described the graph edit distance based on A* search and Hausdorff matching briefly, what's more, the approximate edit distance algorithm of bipartite graph matching is emphatically analyzed. Finally, some existing problems are summarized, and the future development trend is simply discussed.
引文
[1].Pasouale Foggia,Gennaro Percannella,Mario Vento.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].于静,刘燕兵,张宇,等.大规模图数据匹配技术综述[J].计算机研究与发展,2015,52(2):391-409.
[3].Borgwardt K M,Ong C S,Sch?nauer S,et al.Protein function prediction via graph kernels.[J].Oral Radiology,2005,6(2):29-35.
[4].Harchaoui Z,Bach F.Image Classification with Segmentation Graph Kernels[C]//Computer Vision&Pattern Recognition,Cvpr 07,IEEE Conference on.IEEE,2007:1-8.
[5].Peter Shoubridge,Miro Kraetzl,Wal Wallis,et al.Detection of Abnormal Change in A Time Series of Graphs[J].Journal of Interconnection Networks,2002,3(3):85-101.
[6].D.Conte,P.Foggia,C.Sansone,et al.Thirty Years of Graph Matching in Pattern Recognition[J].International Journal of Pattern Recognition&Artificial Intelligence,2011,18(3):265-298.
[7].Riesen K.Structural Pattern Recognition with Graph Edit Distance[J].Advances in Computer Vision&Pattern Recognition,2016.
[8].Bunke H,Allermann G.Inexact graph matching for structural pattern recognition[J].Pattern Recognition Letters,1983,1(4):245-253.
[9].Gao X,Xiao B,Tao D,et al.A survey of graph edit distance[J].Pattern Analysis and Applications,2010,13(1):113-129.
[10].Hart P E,Nilsson N J,Raphael B.A Formal Basis for the Heuristic Determination of Minimum Cost Paths[J].IEEETransactions on Systems Science&Cybernetics,1968,4(2):100-107.
[11].Berretti S,Bimbo A D,Vicario E.Efficient Matching and Indexing of Graph Models in Content-Based Retrieval[J].IEEE Transactions on Pattern Analysis&Machine Intelligence,2001,23(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 Recognition.Springer-Verlag,2002:186-194.
[13].Riesen K,Bunke H.Approximate graph edit distance computation by means of bipartite graph matching[J].Image&Vision Computing,2009,27(7):950-959.
[14].Solé-Ribalta A,Serratosa F,Sanfeliu A.On the Graph Edit Distance cost:Properties and Applications[J].International Journal of Pattern Recognition&Artificial Intelligence,2012,25(5):53-61.
[15].Bunke H.Error Correcting Graph Matching:On the Influence of the Underlying Cost Function[J].Pattern Analysis&Machine Intelligence IEEE Transactions on,1999,21(9):917-922.
[16].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.
[17].Levenshtein V I.Binary codes capable of correcting deletions,insertions and reversals[J].Problems of Information Transmission,1966,10(1):707-710.
[18].Problem T T E.The tree-to-tree editing problem[J].Information Processing Letters,1977,6(6):184-186.
[19].Eshera M A,Fu K S.A graph distance measure for image analysis[J].IEEE Transactions on Systems Man&Cybernetics,1984,14(3):398-408.
[20].Wei J.Markov edit distance.[J].IEEE Transactions on Pattern Analysis&Machine Intelligence,2004,26(3):311-21.
[21].Wagner R A,Fischer M J.The String-to-String Correction Problem[J].Journal of the Acm,1974,21(1):168-173.
[22].Bunke H.On a relation between graph edit distance and maximum common subgraph[J].Pattern Recognition Letters,1997,18(9):689-694.
[23].Maltoni D,Maio D,Jain A K,et al.Handbook of Fingerprint Recognition[C]//Springer Publishing Company,Incorporated,2009:1314.
[24].Caetano T S,Mcauley J J,Cheng L,et al.Learning graph matching.[J].IEEE Transactions on Pattern Analysis&Machine Intelligence,2009,31(6):1048-58.
[25].Lladós J,MartíE,Villanueva J J.Symbol Recognition by Error-Tolerant Subgraph Matching between Region Adjacency Graphs[J].IEEE Transactions on Pattern Analysis&Machine Intelligence,2001,23(10):1137-1143.
[26].Neuhaus M,Bunke H.Automatic learning of cost functions for graph edit distance[J].Information Sciences,2007,177(1):239-247.
[27].Wong A K C,You M.Entropy and Distance of Random Graphs with Application to Structural Pattern Recognition[J].IEEE Transactions on Pattern Analysis&Machine Intelligence,1985,PAMI-7(5):599-609.
[28].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.
[29].Alberto Sanfeliu,Francesc Serratosa,R.Alquézar.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.
[30].Neuhaus M,Bunke H.A Probabilistic Approach to Learning Costs for Graph Edit Distance[C]//Pattern Recognition,International Conference on.IEEEComputer Society,2004:389-393.
[31].Neuhaus M,Bunke H.Self-organizing maps for learning the edit costs in graph matching.[J].IEEETransactions on Systems Man&Cybernetics Part BCybernetics A Publication of the IEEE Systems Man&Cybernetics Society,2005,35(3):503-14.
[32].Serratosa F,Soléribalta A,Cortés X.Automatic Learning 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.
[33].Dumay A C M,Geest R J V D,Gerbrands J J,et al.Consistent inexact graph matching applied to labelling coronary segments in arteriograms[C]//Iapr International Conference on Pattern Recognition,1992.Vol.iii.Conference C:Image,Speech and Signal Analysis,Proceedings.1992:439-442.
[34].Riesen K,Fankhauser S,Bunke H.Speeding Up Graph Edit Distance Computation with a Bipartite Heuristic.[C]//Mining and Learning with Graphs,MLG 2007,Firence,Italy,August 1-3,2007,Proceedings.2007.
[35].Fischer A,Plamondon R,Savaria 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.
[36].Neuhaus M,Riesen K,Bunke H.Fast suboptimal algorithms for the computation of graph edit distance[C]//Joint Iapr International Conference on Structural,Syntactic,and Statistical Pattern Recognition.Springer-Verlag,2006:163-172.
[37].Abu-Aisheh Z,Raveaux R,Ramel J Y,et al.An Exact Graph Edit Distance Algorithm for Solving Pattern Recognition Problems[C]//Icpram.2015.
[38].Abu-Aisheh Z,Raveaux R,Ramel J Y,et al.A Distributed Algorithm for Graph Edit Distance[C]//Graph SM.2016.
[39].Koopmans T C,Beckmann M.Assignment Problems and the Location of Economic Activities[J].Cowles Foundation Discussion Papers,1955,25(1):53-76.
[40].R.Burkard,M.Dell’Amico,and S.Martello,Assignment Problems.Philadelphia,PA,USA:Society for Industrial and Applied Mathematics,2009.
[41].Fankhauser S,Riesen K,Bunke H.Speeding Up Graph Edit Distance Computation through Fast Bipartite Matching.[C]//Graph-Based Representations in Pattern Recognition,Iapr-Tc-15 International Workshop,Gbrpr2011,Münster,Germany,May 18-20,2011.Proceedings.2011:102-111.
[42].Kuhn K W.The Hungarian Method for the assignment problem.Naval research logistics 1955;2:83-97[C]//Computer-Aided Design&Applications.1955:83--97.
[43].Munkres J.Algorithms for the assignment and transportation problems.J Soc Ind Appl Math[J].Journal of the Society for Industrial&Applied Mathematics,1957,5(1):32-38.
[44].Jonker R,Volgenant A.A shortest augmenting path algorithm for dense and sparse linear assignment problems[J].Computing,1987,38(4):325-340.
[45].Riesen K,Bunke H.Improving bipartite graph edit distance approximation using various search strategies[J].Pattern Recognition,2014,48(4):1349-1363.
[46].Riesen K,Ferrer M,Bunke H.Approximate Graph Edit Distance in Quadratic Time.[J].IEEE/ACMTransactions on Computational Biology&Bioinformatics,2015:1-1.
[47].Serratosa F.Fast computation of Bipartite graph matching☆[J].Pattern Recognition Letters,2014,45(8):244-250.
[48].Bourgeois,Fran&#,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.
[49].Francesc Serratosa.Speeding up Fast Bipartite Graph Matching Through a New Cost Matrix[J].International Journal of Pattern Recognition&Artificial Intelligence,2014,29(2).
[50].Riesen K,Fischer A,Bunke H.Approximation of Graph Edit Distance by Means of a Utility Matrix[M]//Artificial Neural Networks in Pattern Recognition.Springer International Publishing,2016.
[51].Justice D,Hero A.A binary linear programming formulation of the graph edit distance.[J].IEEETransactions on Pattern Analysis&Machine Intelligence,2006,28(8):1200-14.
[52].Riesen K,Fischer A,Bunke H.Computing Upper and Lower Bounds of Graph Edit Distance in Cubic Time[C]//Int.Workshop on Artificial Neural Networks in Pattern Recognition.2014:129-140.
[53].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.
[54].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.
[55].Wilson R C,Hancock E R.Structural Matching by Discrete Relaxation[J].IEEE Transactions on Pattern Analysis&Machine Intelligence,1997,19(6):634-648.
[56].[56].Myers R,Wilson R C,Hancock E R.Bayesian Graph Edit Distance[J].IEEE Transactions on Pattern Analysis&Machine Intelligence,2000,22(6):628-635.
[57].Cross A D J,Wilson R C,Hancock E R.Inexact graph matching using genetic search[J].Pattern Recognition,1997,30(6):953-970.
[58].Boeres M C,Ribeiro C C,Bloch I.A Randomized Heuristic for Scene Recognition by Graph Matching[J].Lecture Notes in Computer Science,2004,3059:100-113.
[59].Sorlin S,Solnon C.Reactive Tabu Search for Measuring Graph Similarity[J].Lecture Notes in Computer Science,2005,3434:172-182.
[2].于静,刘燕兵,张宇,等.大规模图数据匹配技术综述[J].计算机研究与发展,2015,52(2):391-409.
[3].Borgwardt K M,Ong C S,Sch?nauer S,et al.Protein function prediction via graph kernels.[J].Oral Radiology,2005,6(2):29-35.
[4].Harchaoui Z,Bach F.Image Classification with Segmentation Graph Kernels[C]//Computer Vision&Pattern Recognition,Cvpr 07,IEEE Conference on.IEEE,2007:1-8.
[5].Peter Shoubridge,Miro Kraetzl,Wal Wallis,et al.Detection of Abnormal Change in A Time Series of Graphs[J].Journal of Interconnection Networks,2002,3(3):85-101.
[6].D.Conte,P.Foggia,C.Sansone,et al.Thirty Years of Graph Matching in Pattern Recognition[J].International Journal of Pattern Recognition&Artificial Intelligence,2011,18(3):265-298.
[7].Riesen K.Structural Pattern Recognition with Graph Edit Distance[J].Advances in Computer Vision&Pattern Recognition,2016.
[8].Bunke H,Allermann G.Inexact graph matching for structural pattern recognition[J].Pattern Recognition Letters,1983,1(4):245-253.
[9].Gao X,Xiao B,Tao D,et al.A survey of graph edit distance[J].Pattern Analysis and Applications,2010,13(1):113-129.
[10].Hart P E,Nilsson N J,Raphael B.A Formal Basis for the Heuristic Determination of Minimum Cost Paths[J].IEEETransactions on Systems Science&Cybernetics,1968,4(2):100-107.
[11].Berretti S,Bimbo A D,Vicario E.Efficient Matching and Indexing of Graph Models in Content-Based Retrieval[J].IEEE Transactions on Pattern Analysis&Machine Intelligence,2001,23(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 Recognition.Springer-Verlag,2002:186-194.
[13].Riesen K,Bunke H.Approximate graph edit distance computation by means of bipartite graph matching[J].Image&Vision Computing,2009,27(7):950-959.
[14].Solé-Ribalta A,Serratosa F,Sanfeliu A.On the Graph Edit Distance cost:Properties and Applications[J].International Journal of Pattern Recognition&Artificial Intelligence,2012,25(5):53-61.
[15].Bunke H.Error Correcting Graph Matching:On the Influence of the Underlying Cost Function[J].Pattern Analysis&Machine Intelligence IEEE Transactions on,1999,21(9):917-922.
[16].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.
[17].Levenshtein V I.Binary codes capable of correcting deletions,insertions and reversals[J].Problems of Information Transmission,1966,10(1):707-710.
[18].Problem T T E.The tree-to-tree editing problem[J].Information Processing Letters,1977,6(6):184-186.
[19].Eshera M A,Fu K S.A graph distance measure for image analysis[J].IEEE Transactions on Systems Man&Cybernetics,1984,14(3):398-408.
[20].Wei J.Markov edit distance.[J].IEEE Transactions on Pattern Analysis&Machine Intelligence,2004,26(3):311-21.
[21].Wagner R A,Fischer M J.The String-to-String Correction Problem[J].Journal of the Acm,1974,21(1):168-173.
[22].Bunke H.On a relation between graph edit distance and maximum common subgraph[J].Pattern Recognition Letters,1997,18(9):689-694.
[23].Maltoni D,Maio D,Jain A K,et al.Handbook of Fingerprint Recognition[C]//Springer Publishing Company,Incorporated,2009:1314.
[24].Caetano T S,Mcauley J J,Cheng L,et al.Learning graph matching.[J].IEEE Transactions on Pattern Analysis&Machine Intelligence,2009,31(6):1048-58.
[25].Lladós J,MartíE,Villanueva J J.Symbol Recognition by Error-Tolerant Subgraph Matching between Region Adjacency Graphs[J].IEEE Transactions on Pattern Analysis&Machine Intelligence,2001,23(10):1137-1143.
[26].Neuhaus M,Bunke H.Automatic learning of cost functions for graph edit distance[J].Information Sciences,2007,177(1):239-247.
[27].Wong A K C,You M.Entropy and Distance of Random Graphs with Application to Structural Pattern Recognition[J].IEEE Transactions on Pattern Analysis&Machine Intelligence,1985,PAMI-7(5):599-609.
[28].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.
[29].Alberto Sanfeliu,Francesc Serratosa,R.Alquézar.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.
[30].Neuhaus M,Bunke H.A Probabilistic Approach to Learning Costs for Graph Edit Distance[C]//Pattern Recognition,International Conference on.IEEEComputer Society,2004:389-393.
[31].Neuhaus M,Bunke H.Self-organizing maps for learning the edit costs in graph matching.[J].IEEETransactions on Systems Man&Cybernetics Part BCybernetics A Publication of the IEEE Systems Man&Cybernetics Society,2005,35(3):503-14.
[32].Serratosa F,Soléribalta A,Cortés X.Automatic Learning 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.
[33].Dumay A C M,Geest R J V D,Gerbrands J J,et al.Consistent inexact graph matching applied to labelling coronary segments in arteriograms[C]//Iapr International Conference on Pattern Recognition,1992.Vol.iii.Conference C:Image,Speech and Signal Analysis,Proceedings.1992:439-442.
[34].Riesen K,Fankhauser S,Bunke H.Speeding Up Graph Edit Distance Computation with a Bipartite Heuristic.[C]//Mining and Learning with Graphs,MLG 2007,Firence,Italy,August 1-3,2007,Proceedings.2007.
[35].Fischer A,Plamondon R,Savaria 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.
[36].Neuhaus M,Riesen K,Bunke H.Fast suboptimal algorithms for the computation of graph edit distance[C]//Joint Iapr International Conference on Structural,Syntactic,and Statistical Pattern Recognition.Springer-Verlag,2006:163-172.
[37].Abu-Aisheh Z,Raveaux R,Ramel J Y,et al.An Exact Graph Edit Distance Algorithm for Solving Pattern Recognition Problems[C]//Icpram.2015.
[38].Abu-Aisheh Z,Raveaux R,Ramel J Y,et al.A Distributed Algorithm for Graph Edit Distance[C]//Graph SM.2016.
[39].Koopmans T C,Beckmann M.Assignment Problems and the Location of Economic Activities[J].Cowles Foundation Discussion Papers,1955,25(1):53-76.
[40].R.Burkard,M.Dell’Amico,and S.Martello,Assignment Problems.Philadelphia,PA,USA:Society for Industrial and Applied Mathematics,2009.
[41].Fankhauser S,Riesen K,Bunke H.Speeding Up Graph Edit Distance Computation through Fast Bipartite Matching.[C]//Graph-Based Representations in Pattern Recognition,Iapr-Tc-15 International Workshop,Gbrpr2011,Münster,Germany,May 18-20,2011.Proceedings.2011:102-111.
[42].Kuhn K W.The Hungarian Method for the assignment problem.Naval research logistics 1955;2:83-97[C]//Computer-Aided Design&Applications.1955:83--97.
[43].Munkres J.Algorithms for the assignment and transportation problems.J Soc Ind Appl Math[J].Journal of the Society for Industrial&Applied Mathematics,1957,5(1):32-38.
[44].Jonker R,Volgenant A.A shortest augmenting path algorithm for dense and sparse linear assignment problems[J].Computing,1987,38(4):325-340.
[45].Riesen K,Bunke H.Improving bipartite graph edit distance approximation using various search strategies[J].Pattern Recognition,2014,48(4):1349-1363.
[46].Riesen K,Ferrer M,Bunke H.Approximate Graph Edit Distance in Quadratic Time.[J].IEEE/ACMTransactions on Computational Biology&Bioinformatics,2015:1-1.
[47].Serratosa F.Fast computation of Bipartite graph matching☆[J].Pattern Recognition Letters,2014,45(8):244-250.
[48].Bourgeois,Fran&#,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.
[49].Francesc Serratosa.Speeding up Fast Bipartite Graph Matching Through a New Cost Matrix[J].International Journal of Pattern Recognition&Artificial Intelligence,2014,29(2).
[50].Riesen K,Fischer A,Bunke H.Approximation of Graph Edit Distance by Means of a Utility Matrix[M]//Artificial Neural Networks in Pattern Recognition.Springer International Publishing,2016.
[51].Justice D,Hero A.A binary linear programming formulation of the graph edit distance.[J].IEEETransactions on Pattern Analysis&Machine Intelligence,2006,28(8):1200-14.
[52].Riesen K,Fischer A,Bunke H.Computing Upper and Lower Bounds of Graph Edit Distance in Cubic Time[C]//Int.Workshop on Artificial Neural Networks in Pattern Recognition.2014:129-140.
[53].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.
[54].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.
[55].Wilson R C,Hancock E R.Structural Matching by Discrete Relaxation[J].IEEE Transactions on Pattern Analysis&Machine Intelligence,1997,19(6):634-648.
[56].[56].Myers R,Wilson R C,Hancock E R.Bayesian Graph Edit Distance[J].IEEE Transactions on Pattern Analysis&Machine Intelligence,2000,22(6):628-635.
[57].Cross A D J,Wilson R C,Hancock E R.Inexact graph matching using genetic search[J].Pattern Recognition,1997,30(6):953-970.
[58].Boeres M C,Ribeiro C C,Bloch I.A Randomized Heuristic for Scene Recognition by Graph Matching[J].Lecture Notes in Computer Science,2004,3059:100-113.
[59].Sorlin S,Solnon C.Reactive Tabu Search for Measuring Graph Similarity[J].Lecture Notes in Computer Science,2005,3434:172-182.