Top

The VLDB Journal

Published in:

15-07-2019 | Special Issue Paper

Comparing heuristics for graph edit distance computation

Authors: David B. Blumenthal, Nicolas Boria, Johann Gamper, Sébastien Bougleux, Luc Brun

Published in: The VLDB Journal | Issue 1/2020

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Because of its flexibility, intuitiveness, and expressivity, the graph edit distance (GED) is one of the most widely used distance measures for labeled graphs. Since exactly computing GED is NP-hard, over the past years, various heuristics have been proposed. They use techniques such as transformations to the linear sum assignment problem with error correction, local search, and linear programming to approximate GED via upper or lower bounds. In this paper, we provide a systematic overview of the most important heuristics. Moreover, we empirically evaluate all compared heuristics within an integrated implementation.

previous article LSM-based storage techniques: a survey

next article Event modeling and mining: a long journey toward explainable events

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

As BRANCH-CONST was proposed before BRANCH and BRANCH-FAST, it is in fact more correct to say that BRANCH and BRANCH-FAST generalize BRANCH-CONST to arbitrary edit costs. For the sake of simplicity, we here change the order of presentation.

In the original publications, this technique is suggested for the LSAPE instance produced by BP (cf. Sect. 5.2.2). It can, however, be employed in combination with the LSAPE instances produced by any instantiation of LSAPE-GED.

In [58], SA is presented as a technique for improving the upper bound computed by the LSAPE-GED instantiation BP. Since SA can be used with any instantiation of LSAPE-GED, we here present a more general version.

To be precise, we tested 19 algorithms that compute lower bounds and 173 algorithms that compute upper bounds. The reason for this is that the extensions of the paradigms LSAPE-GED and LS-GED only affect the upper bounds.

Abu-Aisheh, Z., Gaüzere, B., Bougleux, S., Ramel, J.Y., Brun, L., Raveaux, R., Héroux, P., Adam, S.: Graph edit distance contest 2016: results and future challenges. Pattern Recognit. Lett. 100, 96–103 (2017). https://doi.org/10.1016/j.patrec.2017.10.007 CrossRef

Abu-Aisheh, Z., Raveaux, R., Ramel, J.: A graph database repository and performance evaluation metrics for graph edit distance. In: Liu, C., Luo, B., Kropatsch, W.G., Cheng, J. (eds.) GbRPR 2015, LNCS, vol. 9069. Springer, Cham, pp. 138–147 (2015). https://doi.org/10.1007/978-3-319-18224-7_14 CrossRef

Babai, L.: Graph isomorphism in quasipolynomial time [extended abstract]. In: Wichs, D., Mansour, Y. (eds.) STOC 2016. ACM, New York, pp. 684–697 (2016). https://doi.org/10.1145/2897518.2897542

Blumenthal, D.B., Bougleux, S., Gamper, J., Brun, L.: Ring based approximation of graph edit distance. In: Bai, X., Hancock, E., Ho, T., Wilson, R., Biggio, B., Robles-Kelly, A. (eds.) S+SSPR 2018, LNCS, vol. 11004. Springer, Cham, pp. 293–303 (2018). https://doi.org/10.1007/978-3-319-97785-0_28

Blumenthal, D.B., Bougleux, S., Gamper, J., Brun, L.: Upper bounding GED via transformations to LSAPE based on rings and machine learning (2019)

Blumenthal, D.B., Bougleux, S., Gamper, J., Brun, L.: GEDLIB: a C++ library for graph edit distance computation. In: Conte, D., Ramel, J.Y., Foggia, P. (eds.) Graph-Based Representations in Pattern Recognition. GbRPR 2019. Lecture Notes in Computer Science, vol. 11510, pp. 14–24. Springer, Cham (2019)CrossRef

Blumenthal, D.B., Daller, E., Bougleux, S., Brun, L., Gamper, J.: Quasimetric graph edit distance as a compact quadratic assignment problem. In: ICPR 2018. IEEE Computer Society, pp. 934–939 (2018). https://doi.org/10.1109/ICPR.2018.8546055

Blumenthal, D.B., Gamper, J.: Correcting and speeding-up bounds for non-uniform graph edit distance. In: ICDE 2017. IEEE Computer Society, pp. 131–134 (2017). https://doi.org/10.1109/ICDE.2017.57

Blumenthal, D.B., Gamper, J.: Improved lower bounds for graph edit distance. IEEE Trans. Knowl. Data Eng. 30(3), 503–516 (2018). https://doi.org/10.1109/TKDE.2017.2772243 CrossRef

10.

Blumenthal, D.B., Gamper, J.: On the exact computation of the graph edit distance. Pattern Recognit. Lett. (2018). https://doi.org/10.1016/j.patrec.2018.05.002 CrossRef

11.

Bonacich, P.: Power and centrality: a family of measures. Am. J. Sociol. 92(5), 1170–1182 (1987). https://doi.org/10.1086/228631 CrossRef

12.

Boria, N., Blumenthal, D.B., Bougleux, S., Brun, L.: Improved local search for graph edit distance (2019). Submitted. arXiv:1907.02929

13.

Boria, N., Bougleux, S., Brun, L.: Approximating GED using a stochastic generator and multistart IPFP. In: Bai, X., Hancock, E.R., Ho, T.K., Wilson, R.C., Biggio, B., Robles-Kelly, A. (eds.) S+SSPR 2018. Springer, Cham, pp. 460–469 (2018). https://doi.org/10.1007/978-3-319-97785-0_44

14.

Bougleux, S., Brun, L., Carletti, V., Foggia, P., Gaüzère, B., Vento, M.: Graph edit distance as a quadratic assignment problem. Pattern Recognit. Lett. 87, 38–46 (2017). https://doi.org/10.1016/j.patrec.2016.10.001 CrossRef

15.

Bougleux, S., Gaüzère, B., Blumenthal, D.B., Brun, L.: Fast linear sum assignment with error-correction and no cost constraints. Pattern Recognit. Lett. (2018). https://doi.org/10.1016/j.patrec.2018.03.032 CrossRef

16.

Bougleux, S., Gaüzère, B., Brun, L.: Graph edit distance as a quadratic program. In: ICPR 2016. IEEE Computer Society, pp. 1701–1706 (2016). https://doi.org/10.1109/ICPR.2016.7899881

17.

Bougleux, S., Gaüzère, B., Brun, L.: A Hungarian algorithm for error-correcting graph matching. In: Foggia, P., Liu, C., Vento, M. (eds.) GbRPR 2017, LNCS, vol. 10310. Springer, Cham, pp. 118–127 (2017). https://doi.org/10.1007/978-3-319-58961-9_11 CrossRef

18.

Brin, S., Page, L.: The anatomy of a large-scale hypertextual web search engine. Comput. Netw. 30(1–7), 107–117 (1998). https://doi.org/10.1016/S0169-7552(98)00110-X CrossRef

19.

Brun, L., Foggia, P., Vento, M.: Trends in graph-based representations for pattern recognition. Pattern Recognit. Lett. (2018). https://doi.org/10.1016/j.patrec.2018.03.016 CrossRef

20.

Bunke, H., Allermann, G.: Inexact graph matching for structural pattern recognition. Pattern Recognit. Lett. 1(4), 245–253 (1983). https://doi.org/10.1016/0167-8655(83)90033-8 CrossRefMATH

21.

Carletti, V., Gaüzère, B., Brun, L., Vento, M.: Approximate graph edit distance computation combining bipartite matching and exact neighborhood substructure distance. In: Liu, C., Luo, B., Kropatsch, W.G., Cheng, J. (eds.) GbRPR 2015, LNCS, vol. 9069. Springer, Cham, pp. 188–197 (2015). https://doi.org/10.1007/978-3-319-18224-7_19 CrossRef

22.

Chang, C.C., Lin, C.J.: LIBSVM: a library for support vector machines. ACM Trans. Intell. Syst. Technol. 2(3), 27 (2011). https://doi.org/10.1145/1961189.1961199 CrossRef

23.

Conte, D., Foggia, P., Sansone, C., Vento, M.: Thirty years of graph matching in pattern recognition. Int. J. Pattern Recognit. Artif. Intell. 18(3), 265–298 (2004). https://doi.org/10.1142/S0218001404003228 CrossRef

24.

Cordella, L.P., Foggia, P., Sansone, C., Vento, M.: A (sub)graph isomorphism algorithm for matching large graphs. IEEE Trans. Pattern Anal. Mach. Intell. 26(10), 1367–1372 (2004). https://doi.org/10.1109/TPAMI.2004.75 CrossRef

25.

Cortés, X., Serratosa, F., Moreno-García, C.F.: On the influence of node centralities on graph edit distance for graph classification. In: Liu, C., Luo, B., Kropatsch, W.G., Cheng, J. (eds.) GbRPR 2015, LNCS, vol. 9069. Springer, Cham, pp. 231–241 (2015). https://doi.org/10.1007/978-3-319-18224-7_23 CrossRef

26.

Daller, É., Bougleux, S., Gaüzère, B., Brun, L.: Approximate graph edit distance by several local searches in parallel. In: Fred, A., di Baja, G.S., Marsico, M.D. (eds.) ICPRAM 2018. SciTePress, pp. 149–158 (2018). https://doi.org/10.5220/0006599901490158

27.

Ferrer, M., Serratosa, F., Riesen, K.: A first step towards exact graph edit distance using bipartite graph matching. In: Liu, C., Luo, B., Kropatsch, W.G., Cheng, J. (eds.) GbRPR 2015, LNCS, vol. 9069. Springer, Cham, pp. 77–86 (2015). https://doi.org/10.1007/978-3-319-18224-7_8 CrossRef

28.

Fischer, A., Suen, C.Y., Frinken, V., Riesen, K., Bunke, H.: Approximation of graph edit distance based on Hausdorff matching. Pattern Recognit. 48(2), 331–343 (2015). https://doi.org/10.1016/j.patcog.2014.07.015 CrossRefMATH

29.

Foggia, P., Percannella, G., Vento, M.: Graph matching and learning in pattern recognition in the last 10 years. Int. J. Pattern Recognit. Artif. Intell. 28(1), 1450001:1–1450001:40 (2014). https://doi.org/10.1142/S0218001414500013 MathSciNetCrossRef

30.

Frank, M., Wolfe, P.: An algorithm for quadratic programming. Nav. Res. Logist. Q. 3(1–2), 95–110 (1956). https://doi.org/10.1002/nav.3800030109 MathSciNetCrossRef

31.

Gao, X., Xiao, B., Tao, D., Li, X.: A survey of graph edit distance. Pattern Anal. Appl. 13(1), 113–129 (2010). https://doi.org/10.1007/s10044-008-0141-y MathSciNetCrossRefMATH

32.

Gaüzère, B., Bougleux, S., Riesen, K., Brun, L.: Approximate graph edit distance guided by bipartite matching of bags of walks. In: Fränti, P., Brown, G., Loog, M., Escolano, F., Pelillo, M. (eds.) S+SSPR 2014, LNCS, vol. 8621. Springer, Cham, pp. 73–82 (2014). https://doi.org/10.1007/978-3-662-44415-3_8

33.

Guennebaud, G., Jacob, B., et al.: Eigen v3 (2010). http://eigen.tuxfamily.org. Accessed 5 July 2019

34.

Gurobi Optimization LLC: Gurobi Optimizer Reference Manual. http://www.gurobi.com. Accessed 5 July 2019

35.

Henry, E.R.: Classification and Uses of Finger Prints. Routledge, London (1900)

36.

Justice, D., Hero, A.: A binary linear programming formulation of the graph edit distance. IEEE Trans. Pattern Anal. Mach. Intell. 28(8), 1200–1214 (2006). https://doi.org/10.1109/TPAMI.2006.152 CrossRef

37.

Karmarkar, N.: A new polynomial-time algorithm for linear programming. Combinatorica 4(4), 373–396 (1984). https://doi.org/10.1007/BF02579150 MathSciNetCrossRefMATH

38.

Kuhn, H.W.: The Hungarian method for the assignment problem. Nav. Res. Logist. Q. 2(1–2), 83–97 (1955). https://doi.org/10.1002/nav.3800020109 MathSciNetCrossRefMATH

39.

Le Digabel, S.: Algorithm 909: NOMAD: nonlinear optimization with the MADS algorithm. ACM Trans. Math. Softw. 37(4), 44:1–44:15 (2011). https://doi.org/10.1145/1916461.1916468 MathSciNetCrossRefMATH

40.

Le Gall, F.: Powers of tensors and fast matrix multiplication. In: Nabeshima, K., Nagasaka, K., Winkler, F., Szántó, Á. (eds.) ISSAC 2014. ACM, pp. 296–303 (2014). https://doi.org/10.1145/2608628.2608664

41.

Lee, L., Lumsdaine, A., Siek, J.: The Boost Graph Library: User Guide and Reference Manual. Addison-Wesley Longman, Boston (2002)

42.

Leordeanu, M., Hebert, M., Sukthankar, R.: An integer projected fixed point method for graph matching and MAP inference. In: Bengio, Y., Schuurmans, D., Lafferty, J.D., Williams, C.K.I., Culotta, A. (eds.) NIPS 2009. Curran Associates, pp. 1114–1122 (2009)

43.

Lerouge, J., Abu-Aisheh, Z., Raveaux, R., Héroux, P., Adam, S.: Exact graph edit distance computation using a binary linear program. In: Robles-Kelly, A., Loog, M., Biggio, B., Escolano, F., Wilson, R. (eds.) S+SSPR 2016, LNCS, vol. 10029. Springer, Cham, pp. 485–495 (2016). https://doi.org/10.1007/978-3-319-49055-7_43

44.

Lerouge, J., Abu-Aisheh, Z., Raveaux, R., Héroux, P., Adam, S.: New binary linear programming formulation to compute the graph edit distance. Pattern Recognit. 72, 254–265 (2017). https://doi.org/10.1016/j.patcog.2017.07.029 CrossRef

45.

Lin, C.L.: Hardness of approximating graph transformation problem. In: Du, D.Z., Zhang, X.S. (eds.) Algorithms and Computation, LNCS, vol. 834. Springer, Berlin, pp. 74–82 (1994). https://doi.org/10.1007/3-540-58325-4_168 CrossRef

46.

Munkres, J.: Algorithms for the assignment and transportation problems. SIAM J. Appl. Math. 5(1), 32–38 (1957). https://doi.org/10.1137/0105003 MathSciNetCrossRefMATH

47.

Nissen, S.: Implementation of a Fast Artificial Neural Network Library (FANN). Technical report, Department of Computer Science, University of Copenhagen (2003). http://fann.sourceforge.net/report/

48.

Ozdemir, E., Gunduz-Demir, C.: A hybrid classification model for digital pathology using structural and statistical pattern recognition. IEEE Trans. Med. Imaging 32(2), 474–483 (2013). https://doi.org/10.1109/TMI.2012.2230186 CrossRef

49.

Riesen, K.: Structural Pattern Recognition with Graph Edit Distance. Advances in Computer Vision and Pattern Recognition. Springer, Cham (2015). https://doi.org/10.1007/978-3-319-27252-8 CrossRefMATH

50.

Riesen, K., Bunke, H.: IAM graph database repository for graph based pattern recognition and machine learning. In: da Vitoria Lobo, N., Kasparis, T., Roli, F., Kwok, J.T., Georgiopoulos, M., Anagnostopoulos, G.C., Loog, M. (eds.) S+SSPR 2008, LNCS, vol. 5342. Springer, Berlin, pp. 287–297 (2008). https://doi.org/10.1007/978-3-540-89689-0_33

51.

Riesen, K., Bunke, H.: Approximate graph edit distance computation by means of bipartite graph matching. Image Vis. Comput. 27(7), 950–959 (2009). https://doi.org/10.1016/j.imavis.2008.04.004 CrossRef

52.

Riesen, K., Bunke, H.: Graph Classification and Clustering Based on Vector Space Embedding. Series in Machine Perception and Artificial Intelligence, vol. 77. World Scientific, Singapore (2010). https://doi.org/10.1142/7731 CrossRefMATH

53.

Riesen, K., Bunke, H., Fischer, A.: Improving graph edit distance approximation by centrality measures. In: ICPR 2014. IEEE Computer Society, pp. 3910–3914 (2014). https://doi.org/10.1109/ICPR.2014.671

54.

Riesen, K., Ferrer, M.: Predicting the correctness of node assignments in bipartite graph matching. Pattern Recognit. Lett. 69, 8–14 (2016). https://doi.org/10.1016/j.patrec.2015.10.007 CrossRef

55.

Riesen, K., Ferrer, M., Fischer, A., Bunke, H.: Approximation of graph edit distance in quadratic time. In: Liu, C., Luo, B., Kropatsch, W.G., Cheng, J. (eds.) GbRPR 2015, LNCS, vol. 9069. Springer, Cham, pp. 3–12 (2015). https://doi.org/10.1007/978-3-319-18224-7_1 CrossRef

56.

Riesen, K., Fischer, A., Bunke, H.: Combining bipartite graph matching and beam search for graph edit distance approximation. In: Gayar, N.E., Schwenker, F., Suen, C. (eds.) ANNPR 2014, LNCS, vol. 8774. Springer, Cham, pp. 117–128 (2014). https://doi.org/10.1007/978-3-319-11656-3_11 CrossRef

57.

Riesen, K., Fischer, A., Bunke, H.: Computing upper and lower bounds of graph edit distance in cubic time. In: Gayar, N.E., Schwenker, F., Suen, C. (eds.) ANNPR 2014, LNCS, vol. 8774. Springer, Heidelberg, pp. 129–140 (2014). https://doi.org/10.1007/978-3-319-11656-3

58.

Riesen, K., Fischer, A., Bunke, H.: Improved graph edit distance approximation with simulated annealing. In: Foggia, P., Liu, C., Vento, M. (eds.) GbRPR 2017, LNCS, vol. 10310. Springer, Cham, pp. 222–231 (2017). https://doi.org/10.1007/978-3-319-58961-9_20 CrossRef

59.

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). https://doi.org/10.1109/TSMC.1983.6313167 CrossRefMATH

60.

Schomburg, I., Chang, A., Ebeling, C., Gremse, M., Heldt, C., Huhn, G., Schomburg, D.: BRENDA, the enzyme database: updates and major new developments. Nucleic Acids Res. 32(Database–Issue), 431–433 (2004). https://doi.org/10.1093/nar/gkh081 CrossRef

61.

Stauffer, M., Fischer, A., Riesen, K.: A novel graph database for handwritten word images. In: Robles-Kelly, A., Loog, M., Biggio, B., Escolano, F., Wilson, R. (eds.) S+SSPR 2016, LNCS, vol. 10029. Springer, Cham, pp. 553–563 (2016). https://doi.org/10.1007/978-3-319-49055-7_49

62.

Stauffer, M., Tschachtli, T., Fischer, A., Riesen, K.: A survey on applications of bipartite graph edit distance. In: Foggia, P., Liu, C., Vento, M. (eds.) GbRPR 2017, LNCS, vol. 10310. Springer, Cham, pp. 242–252 (2017). https://doi.org/10.1007/978-3-319-58961-9_22 CrossRef

63.

Strassen, V.: Gaussian elimination is not optimal. Numer. Math. 13(4), 354–356 (1969). https://doi.org/10.1007/BF02165411 MathSciNetCrossRefMATH

64.

Uno, T.: Algorithms for enumerating all perfect, maximum and maximal matchings in bipartite graphs. In: Leong, H.W., Imai, H., Jain, S. (eds.) ISAAC 1997, LNCS, vol. 1350. Springer, Berlin, pp. 92–101 (1997). https://doi.org/10.1007/3-540-63890-3_11 CrossRef

65.

Uno, T.: A fast algorithm for enumerating bipartite perfect matchings. In: Eades, P., Takaoka, T. (eds.) ISAAC 2001, LNCS, vol. 2223. Springer, Berlin, pp. 367–379 (2001). https://doi.org/10.1007/3-540-45678-3_32 CrossRef

66.

Vento, M.: A long trip in the charming world of graphs for pattern recognition. Pattern Recognit. 48(2), 291–301 (2015). https://doi.org/10.1016/j.patcog.2014.01.002 CrossRefMATH

67.

Wang, X., Ding, X., Tung, A.K.H., Ying, S., Jin, H.: An efficient graph indexing method. In: Kementsietsidis, A., Salles, M.A.V. (eds.) ICDE 2012. IEEE Computer Society, pp. 210–221 (2012). https://doi.org/10.1109/ICDE.2012.28

68.

Zeng, Z., Tung, A.K.H., Wang, J., Feng, J., Zhou, L.: Comparing stars: on approximating graph edit distance. PVLDB 2(1), 25–36 (2009). https://doi.org/10.14778/1687627.1687631 CrossRef

69.

Zhao, X., Xiao, C., Lin, X., Zhang, W., Wang, Y.: Efficient structure similarity searches: a partition-based approach. VLDB J. 27(1), 53–78 (2018). https://doi.org/10.1007/s00778-017-0487-0 CrossRef

70.

Zheng, W., Zou, L., Lian, X., Wang, D., Zhao, D.: Graph similarity search with edit distance constraint in large graph databases. In: He, Q., Iyengar, A., Nejdl, W., Pei, J., Rastogi, R. (eds.) CIKM 2013. ACM, pp. 1595–1600 (2013). https://doi.org/10.1145/2505515.2505723

71.

Zheng, W., Zou, L., Lian, X., Wang, D., Zhao, D.: Efficient graph similarity search over large graph databases. IEEE Trans. Knowl. Data Eng. 27(4), 964–978 (2015). https://doi.org/10.1109/TKDE.2014.2349924 CrossRef

Title: Comparing heuristics for graph edit distance computation
Authors: David B. Blumenthal
Nicolas Boria
Johann Gamper
Sébastien Bougleux
Luc Brun
Publication date: 15-07-2019
Publisher: Springer Berlin Heidelberg
Published in: The VLDB Journal / Issue 1/2020
Print ISSN: 1066-8888
Electronic ISSN: 0949-877X
DOI: https://doi.org/10.1007/s00778-019-00544-1

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 1/2020

Dataset search: a survey

Evaluating interactive data systems

Making data visualization more efficient and effective: a survey

Special issue on best papers of VLDB 2017

In-memory database acceleration on FPGAs: a survey

Explaining Natural Language query results

Premium Partner