图匹配技术研究
|
摘要
图(Graph)在众多的科学领域和工程领域(如模式识别和计算机视觉)中具有广泛的应用,其具备强大的信息表达能力。当图被用来表示物体结构时,衡量物体的相似程度将会被转化成计算两个图的相似度,这就是图匹配(Graph Matching)。近几十年来,对图匹配相关技术和算法的研究已经成为了研究领域内的一个重要课题,尤其是随着大数据时代的来临,图作为数据之间关系的一种表示形式,将会受到越来越多的关注。文中对图匹配技术的发展现状进行了综述,详细介绍了该技术的理论基础,梳理了解决图匹配问题的几种主流思路。最后,结合图匹配技术的一种具体应用对几种算法的性能进行了对比分析。
Graph has been applied to many fields of science and technology,such as pattern recognition and computer vision,because of its powerful representation of structure and information.When graph is used to represent object structure,calculating the similarity of two objects equals to calculating the similarity of two graphs.The research of graph matching algorithms has been carried out for decades,especially as the big data technology increasingly becomes hot recently.As a representation of relationship among data,graph has been paid more attention in the research.This paper gave a survey of the development of the graph matching technology as well as the foundation of this theory.Then,this paper made a summarization of graph matching methods,and compared the performance of several classical algorithms.
Graph has been applied to many fields of science and technology,such as pattern recognition and computer vision,because of its powerful representation of structure and information.When graph is used to represent object structure,calculating the similarity of two objects equals to calculating the similarity of two graphs.The research of graph matching algorithms has been carried out for decades,especially as the big data technology increasingly becomes hot recently.As a representation of relationship among data,graph has been paid more attention in the research.This paper gave a survey of the development of the graph matching technology as well as the foundation of this theory.Then,this paper made a summarization of graph matching methods,and compared the performance of several classical algorithms.
引文
[1]WEST D B.Introduction to graph theory[M].Upper Saddle River:Prentice hall,2001.
[2]HARTLEY R,ZISSERMAN A.Multiple view geometry in computer vision[M].Cambridge:Cambridge University Press,2003.
[3]SZEGEDY C,VANHOUCKE V,IOFFE S,et al.Rethinking the inception architecture for computer vision[C]∥Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.2016:2818-2826.
[4]WOLD S.Pattern recognition by means of disjoint principal components models[J].Pattern Recognition,1976,8(3):127-139.
[5]ULLMANN J R.An algorithm for subgraph isomorphism[J].Journal of the ACM(JACM),1976,23(1):31-42.
[6]CORDELLA L P,FOGGIA P,SANSONE C,et al.Performance evaluation of the VF graph matching algorithm[C]∥International Conference on Image Analysis and Processing,1999.IEEE,1999:1172.
[7]KOTTHOFF L,MCCREESH C,SOLNON C.Portfolios of Subgraph Isomorphism Algorithms[C]∥International Conference on Learning and Intelligent Optimization.Springer International Publishing,2016:107-122.
[8]BUNKE H.On a relation between graph edit distance and maximum common subgraph[J].Pattern Recognition Letters,1997,18(8):689-694.
[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]BUNKE H.Error correcting graph matching:On the influence of the underlying cost function[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1999,21(9):917-922.
[11]UMEYAMA S.An eigendecomposition approach to weighted graph matching problems[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1988,10(5):695-703.
[12]ALMOHAMAD H A,DUFFUAA S O.A linear programming approach for the weighted graph matching problem[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1993,15(5):522-525.
[13]FIORI M,SAPIRO G.On spectral properties for graph matching and graph isomorphism problems[J].Information and Inference,2015,4(1):63-76.
[14]BUNKE H.Error-tolerant graph matching:a formal framework and algorithms[C]∥Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition(SPR)and Structural and Syntactic Pattern Recognition(SSPR).Springer Berlin Heidelberg,1998:1-14.
[15]MESSMER B T,BUNKE H.A new algorithm for error-tolerant subgraph isomorphism detection[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1998,20(5):493-504.
[16]BUNKE H,SHEARER K.A graph distance metric based on the maximal common subgraph[J].Pattern Recognition Letters,1998,19(3):255-259.
[17]BUNKE H,JIANG X,KANDEL A.On the minimum common supergraph of two graphs[J].Computing,2000,65(1):13-25.
[18]WILLETT P.Maximum Common Subgraph Isomorphism Algorithms:A Review[J].MATCH Communications in Mathematical and in Computer Chemistry,2017:77(2):213-232.
[19]CHEN A C L,ELHAJJ A,GAO S,et al.Approximating the maximum common subgraph isomorphism problem with a weighted graph[J].Knowledge-Based Systems,2015,85(C):265-276.
[20]LEVI G.A note on the derivation of maximal common subgraphs of two directed or undirected graphs[J].Calcolo,1973,9(4):341-352.
[21]MCGREGOR J J.Backtrack search algorithms and the maximal common subgraph problem[J].Software:Practice and Experience,1982,12(1):23-34.
[22]FOGGIA P,PERCANNELLA G,VENTO M.Graph matching and learning in pattern recognition in the last 10years[J].International Journal of Pattern Recognition and Artificial Intelligence,2014,28(1):1450001.
[23]TSAI W H,FU K S.Error-correcting isomorphisms of attributed relational graphs for pattern analysis[J].IEEE Transactions on systems,man,and cybernetics,1979,9(12):757-768.
[24]SHAPIRO L G,HARALICK R M.Structural descriptions and inexact matching[M].IEEE Computer Society,1981.
[25]SANFELIU A,FU K S.A distance measure between attributed relational graphs for pattern recognition[J].IEEE Transactions on Systems,Man,and Cybernetics,1983,SMC-13(3):353-362.
[26]ESHERA M A,FU K S.A graph distance measure for image analysis[J].IEEE Transactions on Systems,Man,and Cybernetics,1984,SMC-14(3):398-408.
[27]SCHMID D C,DRUFFEL L E.A fast backtracking algorithm to test directed graphs for isomorphism using distance matrices[J].Journal of the ACM,1976,23(3):433-445.
[28]CHRISTMAS W J,KITTLER J,PETROU M.Structural matching in computer vision using probabilistic relaxation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1995,17(8):749-764.
[29]WILSON R,HANCOCK E R.Graph matching by discrete relaxation[J].Pattern Recognition Letters,1999,20(10):1041-1052.
[30]WILSON R C,HANCOCK E R.Structural matching by discrete relaxation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1997,19(6):634-648.
[31]FENG J S,LAUMY M,DHOME M.Inexact matching using neural networks[J].Machine Intelligence&Pattern Recognition,1994,16:177-184.
[32]XU L,OJA E.Improved simulated annealing,Boltzmann machine,and attributed graph matching[M]∥Neural Networks.Springer Berlin Heidelberg,1990:151-160.
[33]CROSS A D,WILSON R C,HANCOCK E R.Genetic search for structural matching[C]∥European Conference on Computer Vision.Springer Berlin Heidelberg,1996:514-525.
[34]CROSS A D,WILSON R C,HANCOCK E R.Inexact graph matching using genetic search[J].Pattern Recognition,1997,30(6):953-970.
[35]FARAHANI M M,CHAHARSOUGHI S K.A genetic and iterative local search algorithm for solving subgraph isomorphism problem[C]∥2015International Conference on Industrial Engineering and Operations Management(IEOM).IEEE,2015:1-6.
[36]WANG T L,ZHANG K Z,CHIRN G W.The approximate graph matching problem[C]∥Proceedings of the 12th IAPR International Conference on Pattern Recognition,1994.Vol.2-Conference B:Computer Vision&Image Processing.IEEE,1994:284-288.
[37]UMEYAMA S.An eigendecomposition approach to weighted graph matching problems[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1988,10(5):695-703.
[38]CANTONI V,CINQUE L,GUERRA C,et al.2-D object recognition by multiscale tree matching[J].Pattern Recognition,1998,31(10):1443-1454.
[39]OFLAZER K.Error-tolerant retrieval of trees[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1997,19(12):1376-1380.
[40]PELILLO M,KALEMM S,ZUCKER S W.Matching hierarchical structures using association graphs[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1999,21(11):1105-1120.
[41]WANG T L,SHAPIRO B A,SHASHA D,et al.An algorithm for finding the largest approximately common substructures of two trees[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1998,20(8):889-895.
[42]MESSMER B T.Efficient graph matching algorithms for preprocessed model graphs[D].Swizerland:University of Bern,1996.
[43]MESSMER B T,BUNKE H.A new algorithm for error-tolerant subgraph isomorphism detection[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1998,20(5):493-504.
[44]MESSMER B T,BUNKE H.A decision tree approach to graph and subgraph isomorphism detection[J].Pattern Recognition,1999,32(12):1979-1998.
[45]MESSMER B T,BUNKE H.Efficient subgraph isomorphism detection:A decomposition approach[J].IEEE Transactions on Knowledge and Data Engineering,2000,12(2):307-323.
[46]CORDELLA L P,FOGGIA P,SANSONE C,et al.A(sub)graph isomorphism algorithm for matching large graphs[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2004,26(10):1367-1372.
[47]MCKAY B D.Practical graph isomorphism[J].Journal of Sgmpolic Computation,2014,60(1):94-112.
[48]MCKAY B D,PIPERNO A.Practical graph isomorphism,II[J].Journal of Symbolic Computation,2014,60(1):94-112.
[49]MESSMER B T,BUNKE H.Error-correcting graph isomorphism using decision trees[J].International Journal of Pattern Recognition and Artificial Intelligence,1998,12(6):721-742.
[50]DIAS J R,MILNE G W A.Chemical applications of graph theory[J].Journal of Chemical Information&Modeling,1976,32(1):210-242.
[51]POOLE J.Similarity in legal case-based reasoning as degree of matching between conceptual graphs:Work in progress[C]∥Proceedings First European Workshop on Case-Based Reasoning.1993.
[52]BRNER K,PIPPIG E,TAMMER E C,et al.Structural similarity and adaptation[C]∥European Workshop on Advances in Case-Based Reasoning.Springer Berlin Heidelberg,1996.
[53]FISHER D H.Knowledge acquisition via incremental conceptual clustering[J].Machine Learning,1987,2(2):139-172.
[54]LEAKE D B,PLAZA E,INTELLIGEN Z.Case-Based Reasoning Research and Development[C]∥Second International Conference on Case-Based Reasoning.1997.
[55]EHRIG H,HABEL A,KREOWSKI H J.Introduction to graph grammars with applications to semantic networks[J].Computers&Mathematics with Applications,1992,23(6-9):557-572.
[56]MAHER P E.A similarity measure for conceptual graphs[J].International Journal of Intelligent Systems,1993,8(8):819-837.
[57]SHOWBRIDGE P,KRAETZL M,RAY D.Detection of abnormal change in dynamic networks[C]∥Information,Decision and Control,1999(IDC 99).IEEE,1999:557-562.
[58]WANG Y K,FAN K C,HORNG J T.Genetic-based search for error-correcting graph isomorphism[J].IEEE Transactions on Systems,Man,and Cybernetics,Part B(Cybernetics),1997,27(4):588-597.
[59]YAMAZAKI K,BODLAENDER H L,FLUITER B D,et al.Isomorphism for graphs of bounded distance width[C]∥Italian Conference on Algorithms and Complexity.1997:276-287.
[60]BALKO M,CIBULKA J,KRI K,et al.Ramsey numbers of ordered graphs[J].Electronic Notes in Discrete Mathematics,2015,49:419-424.
[61]JIANG X Y,BUNKE H.Optimal quadratic-time isomorphism of ordered graphs[J].Pattern Recognition,1999,32(7):1273-1283.
[62]SHEARER K R.Indexing and retrieval of video using spatial reasoning techniques[D].Curtin University of Technology,1998.
[63]SHEARER K,BUNKE H,VENKATESH S.Video indexing and similarity retrieval by largest common subgraph detection using decision trees[J].Pattern Recognition,2001,34(5):1075-1091.
[64]FOGGIA P,SANSONE C,VENTO M.A performance comparison of five algorithms for graph isomorphism[C]∥Proceedings of the 3rd IAPR TC-15 Workshop on Graph-based Representations in Pattern Recognition.2001:188-199.
[2]HARTLEY R,ZISSERMAN A.Multiple view geometry in computer vision[M].Cambridge:Cambridge University Press,2003.
[3]SZEGEDY C,VANHOUCKE V,IOFFE S,et al.Rethinking the inception architecture for computer vision[C]∥Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition.2016:2818-2826.
[4]WOLD S.Pattern recognition by means of disjoint principal components models[J].Pattern Recognition,1976,8(3):127-139.
[5]ULLMANN J R.An algorithm for subgraph isomorphism[J].Journal of the ACM(JACM),1976,23(1):31-42.
[6]CORDELLA L P,FOGGIA P,SANSONE C,et al.Performance evaluation of the VF graph matching algorithm[C]∥International Conference on Image Analysis and Processing,1999.IEEE,1999:1172.
[7]KOTTHOFF L,MCCREESH C,SOLNON C.Portfolios of Subgraph Isomorphism Algorithms[C]∥International Conference on Learning and Intelligent Optimization.Springer International Publishing,2016:107-122.
[8]BUNKE H.On a relation between graph edit distance and maximum common subgraph[J].Pattern Recognition Letters,1997,18(8):689-694.
[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]BUNKE H.Error correcting graph matching:On the influence of the underlying cost function[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1999,21(9):917-922.
[11]UMEYAMA S.An eigendecomposition approach to weighted graph matching problems[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1988,10(5):695-703.
[12]ALMOHAMAD H A,DUFFUAA S O.A linear programming approach for the weighted graph matching problem[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1993,15(5):522-525.
[13]FIORI M,SAPIRO G.On spectral properties for graph matching and graph isomorphism problems[J].Information and Inference,2015,4(1):63-76.
[14]BUNKE H.Error-tolerant graph matching:a formal framework and algorithms[C]∥Joint IAPR International Workshops on Statistical Techniques in Pattern Recognition(SPR)and Structural and Syntactic Pattern Recognition(SSPR).Springer Berlin Heidelberg,1998:1-14.
[15]MESSMER B T,BUNKE H.A new algorithm for error-tolerant subgraph isomorphism detection[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1998,20(5):493-504.
[16]BUNKE H,SHEARER K.A graph distance metric based on the maximal common subgraph[J].Pattern Recognition Letters,1998,19(3):255-259.
[17]BUNKE H,JIANG X,KANDEL A.On the minimum common supergraph of two graphs[J].Computing,2000,65(1):13-25.
[18]WILLETT P.Maximum Common Subgraph Isomorphism Algorithms:A Review[J].MATCH Communications in Mathematical and in Computer Chemistry,2017:77(2):213-232.
[19]CHEN A C L,ELHAJJ A,GAO S,et al.Approximating the maximum common subgraph isomorphism problem with a weighted graph[J].Knowledge-Based Systems,2015,85(C):265-276.
[20]LEVI G.A note on the derivation of maximal common subgraphs of two directed or undirected graphs[J].Calcolo,1973,9(4):341-352.
[21]MCGREGOR J J.Backtrack search algorithms and the maximal common subgraph problem[J].Software:Practice and Experience,1982,12(1):23-34.
[22]FOGGIA P,PERCANNELLA G,VENTO M.Graph matching and learning in pattern recognition in the last 10years[J].International Journal of Pattern Recognition and Artificial Intelligence,2014,28(1):1450001.
[23]TSAI W H,FU K S.Error-correcting isomorphisms of attributed relational graphs for pattern analysis[J].IEEE Transactions on systems,man,and cybernetics,1979,9(12):757-768.
[24]SHAPIRO L G,HARALICK R M.Structural descriptions and inexact matching[M].IEEE Computer Society,1981.
[25]SANFELIU A,FU K S.A distance measure between attributed relational graphs for pattern recognition[J].IEEE Transactions on Systems,Man,and Cybernetics,1983,SMC-13(3):353-362.
[26]ESHERA M A,FU K S.A graph distance measure for image analysis[J].IEEE Transactions on Systems,Man,and Cybernetics,1984,SMC-14(3):398-408.
[27]SCHMID D C,DRUFFEL L E.A fast backtracking algorithm to test directed graphs for isomorphism using distance matrices[J].Journal of the ACM,1976,23(3):433-445.
[28]CHRISTMAS W J,KITTLER J,PETROU M.Structural matching in computer vision using probabilistic relaxation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1995,17(8):749-764.
[29]WILSON R,HANCOCK E R.Graph matching by discrete relaxation[J].Pattern Recognition Letters,1999,20(10):1041-1052.
[30]WILSON R C,HANCOCK E R.Structural matching by discrete relaxation[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1997,19(6):634-648.
[31]FENG J S,LAUMY M,DHOME M.Inexact matching using neural networks[J].Machine Intelligence&Pattern Recognition,1994,16:177-184.
[32]XU L,OJA E.Improved simulated annealing,Boltzmann machine,and attributed graph matching[M]∥Neural Networks.Springer Berlin Heidelberg,1990:151-160.
[33]CROSS A D,WILSON R C,HANCOCK E R.Genetic search for structural matching[C]∥European Conference on Computer Vision.Springer Berlin Heidelberg,1996:514-525.
[34]CROSS A D,WILSON R C,HANCOCK E R.Inexact graph matching using genetic search[J].Pattern Recognition,1997,30(6):953-970.
[35]FARAHANI M M,CHAHARSOUGHI S K.A genetic and iterative local search algorithm for solving subgraph isomorphism problem[C]∥2015International Conference on Industrial Engineering and Operations Management(IEOM).IEEE,2015:1-6.
[36]WANG T L,ZHANG K Z,CHIRN G W.The approximate graph matching problem[C]∥Proceedings of the 12th IAPR International Conference on Pattern Recognition,1994.Vol.2-Conference B:Computer Vision&Image Processing.IEEE,1994:284-288.
[37]UMEYAMA S.An eigendecomposition approach to weighted graph matching problems[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1988,10(5):695-703.
[38]CANTONI V,CINQUE L,GUERRA C,et al.2-D object recognition by multiscale tree matching[J].Pattern Recognition,1998,31(10):1443-1454.
[39]OFLAZER K.Error-tolerant retrieval of trees[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1997,19(12):1376-1380.
[40]PELILLO M,KALEMM S,ZUCKER S W.Matching hierarchical structures using association graphs[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1999,21(11):1105-1120.
[41]WANG T L,SHAPIRO B A,SHASHA D,et al.An algorithm for finding the largest approximately common substructures of two trees[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1998,20(8):889-895.
[42]MESSMER B T.Efficient graph matching algorithms for preprocessed model graphs[D].Swizerland:University of Bern,1996.
[43]MESSMER B T,BUNKE H.A new algorithm for error-tolerant subgraph isomorphism detection[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,1998,20(5):493-504.
[44]MESSMER B T,BUNKE H.A decision tree approach to graph and subgraph isomorphism detection[J].Pattern Recognition,1999,32(12):1979-1998.
[45]MESSMER B T,BUNKE H.Efficient subgraph isomorphism detection:A decomposition approach[J].IEEE Transactions on Knowledge and Data Engineering,2000,12(2):307-323.
[46]CORDELLA L P,FOGGIA P,SANSONE C,et al.A(sub)graph isomorphism algorithm for matching large graphs[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2004,26(10):1367-1372.
[47]MCKAY B D.Practical graph isomorphism[J].Journal of Sgmpolic Computation,2014,60(1):94-112.
[48]MCKAY B D,PIPERNO A.Practical graph isomorphism,II[J].Journal of Symbolic Computation,2014,60(1):94-112.
[49]MESSMER B T,BUNKE H.Error-correcting graph isomorphism using decision trees[J].International Journal of Pattern Recognition and Artificial Intelligence,1998,12(6):721-742.
[50]DIAS J R,MILNE G W A.Chemical applications of graph theory[J].Journal of Chemical Information&Modeling,1976,32(1):210-242.
[51]POOLE J.Similarity in legal case-based reasoning as degree of matching between conceptual graphs:Work in progress[C]∥Proceedings First European Workshop on Case-Based Reasoning.1993.
[52]BRNER K,PIPPIG E,TAMMER E C,et al.Structural similarity and adaptation[C]∥European Workshop on Advances in Case-Based Reasoning.Springer Berlin Heidelberg,1996.
[53]FISHER D H.Knowledge acquisition via incremental conceptual clustering[J].Machine Learning,1987,2(2):139-172.
[54]LEAKE D B,PLAZA E,INTELLIGEN Z.Case-Based Reasoning Research and Development[C]∥Second International Conference on Case-Based Reasoning.1997.
[55]EHRIG H,HABEL A,KREOWSKI H J.Introduction to graph grammars with applications to semantic networks[J].Computers&Mathematics with Applications,1992,23(6-9):557-572.
[56]MAHER P E.A similarity measure for conceptual graphs[J].International Journal of Intelligent Systems,1993,8(8):819-837.
[57]SHOWBRIDGE P,KRAETZL M,RAY D.Detection of abnormal change in dynamic networks[C]∥Information,Decision and Control,1999(IDC 99).IEEE,1999:557-562.
[58]WANG Y K,FAN K C,HORNG J T.Genetic-based search for error-correcting graph isomorphism[J].IEEE Transactions on Systems,Man,and Cybernetics,Part B(Cybernetics),1997,27(4):588-597.
[59]YAMAZAKI K,BODLAENDER H L,FLUITER B D,et al.Isomorphism for graphs of bounded distance width[C]∥Italian Conference on Algorithms and Complexity.1997:276-287.
[60]BALKO M,CIBULKA J,KRI K,et al.Ramsey numbers of ordered graphs[J].Electronic Notes in Discrete Mathematics,2015,49:419-424.
[61]JIANG X Y,BUNKE H.Optimal quadratic-time isomorphism of ordered graphs[J].Pattern Recognition,1999,32(7):1273-1283.
[62]SHEARER K R.Indexing and retrieval of video using spatial reasoning techniques[D].Curtin University of Technology,1998.
[63]SHEARER K,BUNKE H,VENKATESH S.Video indexing and similarity retrieval by largest common subgraph detection using decision trees[J].Pattern Recognition,2001,34(5):1075-1091.
[64]FOGGIA P,SANSONE C,VENTO M.A performance comparison of five algorithms for graph isomorphism[C]∥Proceedings of the 3rd IAPR TC-15 Workshop on Graph-based Representations in Pattern Recognition.2001:188-199.