Graph Edit Distance or Graph Edit Pseudo-Distance?

详细信息    查看全文

• 关键词：Graph Edit Distance ; Edit cost ; Distance function
• 刊名：Lecture Notes in Computer Science
• 出版年：2016
• 出版时间：2016
• 年：2016
• 卷：10029
• 期：1
• 页码：530-540
• 全文大小：642 KB
• 参考文献：1.Solé, A., Serratosa, F., Sanfeliu, A.: On the graph edit distance cost: properties and applications. Int. J. Pattern Recogn. Artif. Intell. 26(5), 1260004 (2012). (21 pages)MathSciNet CrossRef
  2.Sanfeliu, A., Fu, K.-S.: A distance measure between attributed relational graphs for pattern recognition. IEEE Trans. Syst. Man Cybern. 13(3), 353–362 (1983)CrossRef MATH
  3.Conte, D., Foggia, P., Sansone, C., Vento, M.: Thirty years of graph matching in pattern recognition. Int. J. Pattern Recogn. Artif. Intell. 18(3), 265–298 (2004)CrossRef
  4.Vento, M.: A long trip in the charming world of graphs for pattern recognition. Pattern Recogn. 48, 291–301 (2015)CrossRef
  5.Foggia, P., Percannella, G., Vento, M.: Graph matching and learning in pattern recognition in the last 10 years. Int. J. Pattern Recogn. Artif. Intell. 28, 1450001 (2013)MathSciNet CrossRef
  6.Gao, X., et al.: A survey of graph edit distance. Pattern Anal. Appl. 13(1), 113–129 (2010)MathSciNet CrossRef
  7.Bunke, H., Allermann, G.: Inexact graph matching for structural pattern recognition. Pattern Recogn. Lett. 1(4), 245–253 (1983)CrossRef MATH
  8.He, L., et al.: Graph matching for object recognition and recovery. Pattern Recogn. Lett. 37(7), 1557–1560 (2004)CrossRef
  9.Serratosa, F., Cortés, X., Solé, A.: Component retrieval based on a database of graphs for hand-written electronic-scheme digitalisation. Expert Syst. Appl. 40, 2493–2502 (2013)CrossRef
  10.Berretti, S., Del Bimbo, A., Vicario, E.: Efficient matching and indexing of graph models in content-based retrieval. IEEE Trans. Pattern Anal. Mach. Intell. 23(10), 1089–1105 (2001)CrossRef
  11.Wong, A., You, M.: Entropy and distance of random graphs with application to structural pattern recognition. Trans. Pattern Anal. Mach. Intell. 7(5), 599–609 (1985)CrossRef MATH
  12.Neuhaus, M., Bunke, H.: Automatic learning of cost functions for graph edit distance. Inf. Sci. 177(1), 239–247 (2006)MathSciNet CrossRef MATH
  13.Serratosa, F., Alquézar, R., Sanfeliu, A.: Function-described graphs for modelling objects represented by attributed graphs. Pattern Recogn. 36(3), 781–798 (2003)CrossRef
  14.Serratosa, F., Alquézar, R., Sanfeliu, A.: Efficient algorithms for matching attributed graphs and function-described graphs. In: Proceedings of 15th International Conference on Pattern Recognition, ICPR 2000, Barcelona, Spain, vol. 2, pp. 871–876 (2000)
  15.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. Int. J. Pattern Recogn. Artif. Intell. 18(3), 375–396 (2004)CrossRef
  16.Alquézar, R., Sanfeliu, A., Serratosa, F.: Synthesis of function-described graphs. In: Amin, A., Dori, D., Pudil, P., Freeman, H. (eds.) SSPR’98 and SPR’98. LNCS, vol. 1451, pp. 112–121. Springer, Heidelberg (1998)CrossRef
  17.Bunke, H.: On a relation between graph edit distance and maximum common subgraph. Pattern Recogn. Lett. 18(8), 689–694 (1998)CrossRef
  18.Bunke, H.: Error correcting graph matching: on the influence of the underlying cost function. Trans. Pattern Anal. Mach. Intell. 21(9), 917–922 (1999)CrossRef
  19.Caetano, T., et al.: Learning graph matching. Trans. Pattern Anal. Mach. Intell. 31(6), 1048–1058 (2009)CrossRef
  20.Ferrer, M., Serratosa, F., Riesen, K.: Improving bipartite graph matching by assessing the assignment confidence. Pattern Recogn. Lett. 65, 29–36 (2015)CrossRef
  21.Cortés, X., Serratosa, F.: Learning graph matching substitution weights based on the ground truth node correspondence. Int. J. Pattern Recogn. Artif. Intell. 30(2), 1650005 (2016). (22 pages)MathSciNet CrossRef
  22.Cortés, X., Serratosa, F.: Learning graph-matching edit-costs based on the optimality of the Oracle’s node correspondences. Pattern Recogn. Lett. 56, 22–29 (2015)CrossRef
  23.Jain, A.K., Maltoni, D.: Handbook of Fingerprint Recognition. Springer, New York (2003)MATH
  24.Levenshtein, V.I.: Binary codes capable of correcting deletions, insertions and reversals. Sov. Phys. Dokl. Cybern. Control Theory 10, 707–710 (1966)MathSciNet MATH
  25.Serratosa, F., Sanfeliu, A.: Signatures versus histograms: definitions, distances and algorithms. Pattern Recogn. 39(5), 921–934 (2006)CrossRef MATH
  26.Riesen, K., Bunke, H.: Approximate graph edit distance computation by means of bipartite graph matching. Image Vis. Comput. 27(7), 950–959 (2009)CrossRef
  27.Serratosa, F.: Fast computation of bipartite graph matching. Pattern Recogn. Lett. 45, 244–250 (2014)CrossRef
  28.Serratosa, F.: Computation of graph edit distance: reasoning about optimality and speed-up. Image Vis. Comput. 40, 38–48 (2015)CrossRef
  29.Serratosa, F.: Speeding up fast bipartite graph matching through a new cost matrix. Int. J. Pattern Recogn. Artif. Intell. 29(2), 1550010 (2015)MathSciNet CrossRef
  30.Arkhangel’skii, A.V., Pontryagin, L.S.: General Topology I: Basic Concepts and Constructions Dimension Theory. Encyclopaedia of Mathematical Sciences. Springer, Heidelberg (1990)CrossRef
  31. http://​deim.​urv.​cat/​~francesc.​serratosa/​databases/​
  32. http://​deim.​urv.​cat/​~francesc.​serratosa/​SW
  
• 作者单位：Francesc Serratosa (18)
  Xavier Cortés (18)
  Carlos-Francisco Moreno (18)
  
  18. Universitat Rovira i Virgili, Tarragona, Catalonia, Spain
  
• 丛书名：Structural, Syntactic, and Statistical Pattern Recognition
• ISBN：978-3-319-49055-7
• 刊物类别：Computer Science
• 刊物主题：Artificial Intelligence and Robotics
  Computer Communication Networks
  Software Engineering
  Data Encryption
  Database Management
  Computation by Abstract Devices
  Algorithm Analysis and Problem Complexity
  
• 出版者：Springer Berlin / Heidelberg
• ISSN：1611-3349
• 卷排序：10029

文摘

Graph Edit Distance has been intensively used since its appearance in 1983. This distance is very appropriate if we want to compare a pair of attributed graphs from any domain and obtain not only a distance, but also the best correspondence between nodes of the involved graphs. In this paper, we want to analyse if the Graph Edit Distance can be really considered a distance or a pseudo-distance, since some restrictions of the distance function are not fulfilled. Distinguishing between both cases is important because the use of a distance is a restriction in some methods to return exact instead of approximate results. This occurs, for instance, in some graph retrieval techniques. Experimental validation shows that in most of the cases, it is not appropriate to denominate the Graph Edit Distance as a distance, but a pseudo-distance instead, since the triangle inequality is not fulfilled. Therefore, in these cases, the graph retrieval techniques not always return the optimal graph.