Convex graph invariant relaxations for graph edit distance. (English) Zbl 07495397

Summary: The edit distance between two graphs is a widely used measure of similarity that evaluates the smallest number of vertex and edge deletions/insertions required to transform one graph to another. It is NP-hard to compute in general, and a large number of heuristics have been proposed for approximating this quantity. With few exceptions, these methods generally provide upper bounds on the edit distance between two graphs. In this paper, we propose a new family of computationally tractable convex relaxations for obtaining lower bounds on graph edit distance. These relaxations can be tailored to the structural properties of the particular graphs via convex graph invariants. Specific examples that we highlight in this paper include constraints on the graph spectrum as well as (tractable approximations of) the stability number and the maximum-cut values of graphs. We prove under suitable conditions that our relaxations are tight (i.e., exactly compute the graph edit distance) when one of the graphs consists of few eigenvalues. We also validate the utility of our framework on synthetic problems as well as real applications involving molecular structure comparison problems in chemistry.


90C35 Programming involving graphs or networks
90C25 Convex programming
90C22 Semidefinite programming
90C90 Applications of mathematical programming


Full Text: DOI


[1] Abu-Aisheh, Z., Graph edit distance contest: results and future challenges, Pattern Recognit. Lett., 100, 96-103 (2017)
[2] Ben-Tal, A.; El Ghaoui, L.; Nemirovski, A., Robust Optimization. Princeton Series in Applied Mathematics (2009), Princeton: Princeton University Press, Princeton · Zbl 1221.90001
[3] Ben-Tal, A.; Nemirovski, A., Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications (2001), London: SIAM, London · Zbl 0986.90032
[4] Berman, A.; Plemmons, RJ, Nonnegative Matrices in the Mathematical Sciences (1994), London: SIAM, London · Zbl 0815.15016
[5] Bougleux, S., Graph edit distance as a quadratic assignment problem, Pattern Recognit. Lett., 87, 38-46 (2017)
[6] Brouwer, AE; Haemers, WH, Spectra of Graphs (2011), Berlin: Springer, Berlin · Zbl 1231.05001
[7] Candès, EJ; Recht, B., Exact matrix completion via convex optimization, Found. Computat. Math., 9, 6, 717 (2009) · Zbl 1219.90124
[8] Candogan, UO; Chandrasekaran, V., Finding planted subgraphs with few eigenvalues using the Schur-Horn relaxation, SIAM J. Optim., 28, 1, 735-759 (2018) · Zbl 1395.90199
[9] Chandrasekaran, V.; Parrilo, PA; Willsky, AS, Convex graph invariants, SIAM Rev., 54, 3, 513-541 (2012) · Zbl 1250.05091
[10] Chandrasekaran, V.; Sanghavi, S.; Parrilo, PA; Willsky, AS, Rank-sparsity incoherence for matrix decomposition, SIAM J. Optim., 21, 2, 572-596 (2011) · Zbl 1226.90067
[11] Chen, Y.; Jalali, A.; Sanghavi, S.; Caramanis, C., Low-rank matrix recovery from errors and erasures, IEEE Trans. Inf. Theory, 59, 7, 4324-4337 (2013)
[12] 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)
[13] Daller, É., Bougleux, S., Gaüzère, B., Brun, L.: Approximate graph edit distance by several local searches in parallel. In: 7th International Conference on Pattern Recognition Applications and Methods (2018)
[14] Ding, Y.; Wolckowicz, H., A low-dimensional semidefinite relaxation for the quadratic assignment problem, Math. Oper. Res., 34, 1008-1022 (2009) · Zbl 1218.90161
[15] Donoho, DL; Elad, M., Optimally sparse representation in general (nonorthogonal) dictionaries via \(\ell 1\) minimization, Proc. Natl. Acad. Sci., 100, 5, 2197-2202 (2003) · Zbl 1064.94011
[16] Finke, G., Burkard, R.E., Rendl, F.: Quadratic assignment problems. In: Surveys in Combinatorial Optimization, pp. 61-82. North-Holland (2011). https://www.sciencedirect.com/science/article/pii/S0304020808732328 · Zbl 0607.90026
[17] Fischer, A., Suen, C.Y., Frinken, V., Riesen, K., Bunke, H.: A fast matching algorithm for graph-based handwriting recognition. In: International Workshop on Graph-Based Representations in Pattern Recognition, pp. 194-203. Springer, Berlin (2013) · Zbl 1382.68208
[18] Garey, MR; Johnson, DS, Computers and Intractability (2002), New York: W.H. Freeman, New York
[19] Goemans, MX; Williamson, DP, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming, J. ACM (JACM), 42, 6, 1115-1145 (1995) · Zbl 0885.68088
[20] Grant, M.C., Boyd, S.P.: CVX: Matlab software for disciplined convex programming, version 2.0 beta. http://cvxr.com/cvx, September 2013
[21] Grant, M.C., Boyd, S.P.: Graph implementations for nonsmooth convex programs. In: Recent Advances in Learning and Control, pp. 95-110. Springer, London (2008). doi:10.1007/978-1-84800-155-8_7 · Zbl 1205.90223
[22] Hart, PE; Nilsson, NJ; Raphael, B., A formal basis for the heuristic determination of minimum cost paths, IEEE Trans. Syst. Sci. Cybernet., 4, 2, 100-107 (1968)
[23] Ibragimov, R., Malek, M., Guo, J., Baumbach, J.: GEDEVO: an evolutionary graph edit distance algorithm for biological network alignment. In: OASIcs-OpenAccess Series in Informatics, vol. 34. Schloss Dagstuhl-Leibniz-Zentrum für Informatik (2013) · Zbl 1281.92002
[24] Isenor, DK; Zaky, SG, Fingerprint identification using graph matching, Pattern Recognit., 19, 2, 113-122 (1986)
[25] Jiang, T.; Lin, G.; Ma, B.; Zhang, K., A general edit distance between RNA structures, J. Comput. Biol., 9, 2, 371-388 (2002)
[26] Jou, MJ; Chang, GJ, The number of maximum independent sets in graphs, Taiwan. J. Math., 4, 4, 685-695 (2000) · Zbl 0967.05038
[27] 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)
[28] Leordeanu, M., Hebert, M., Sukthankar, R.: An integer projected fixed point method for graph matching and MAP inference. In: Advances in Neural Information Processing Systems, pp. 1114-1122 (2009)
[29] Liu, ZY; Qiao, H., GNCCP—graduated nonconvexity and concavity procedure, IEEE Trans. Pattern Anal. Mach. Intell., 36, 6, 1258-1267 (2014)
[30] Lu, SW; Ren, Y.; Suen, CY, Hierarchical attributed graph representation and recognition of handwritten Chinese characters, Pattern Recognit., 24, 7, 617-632 (1991)
[31] Memišević, V.; Pržulj, N., C-GRAAL: common-neighbors-based global GRAph ALignment of biological networks, Integr. Biol., 4, 7, 734-743 (2012)
[32] Motzkin, TS; Straus, EG, Maxima for graphs and a new proof of a theorem of Turán, Can. J. Math., 17, 4, 533-540 (1965) · Zbl 0129.39902
[33] Neuhaus, M., Bunke, H.: An error-tolerant approximate matching algorithm for attributed planar graphs and its application to fingerprint classification. In: SSPR/SPR, pp. 180-189. Springer, Berlin (2004) · Zbl 1104.68660
[34] Neuhaus, M., Bunke, H.: A graph matching based approach to fingerprint classification using directional variance. In: International Conference on Audio-and Video-Based Biometric Person Authentication, pp. 191-200. Springer, Berlin (2005)
[35] Neuhaus, M.; Bunke, H., Edit distance-based kernel functions for structural pattern classification, Pattern Recognit., 39, 10, 1852-1863 (2006) · Zbl 1096.68140
[36] Riesen, K.; Bunke, H., Approximate graph edit distance computation by means of bipartite graph matching, Image Vis. Comput., 27, 7, 950-959 (2009)
[37] Riesen, K., Fischer, A., Bunke, H.: Computing upper and lower bounds of graph edit distance in cubic time. In: IAPR Workshop on Artificial Neural Networks in Pattern Recognition, pp. 129-140. Springer, Berlin (2014)
[38] Rockafellar, RT, Convex Analysis (1970), Princeton: Princeton University Press, Princeton · Zbl 0193.18401
[39] Sanfeliu, A., Fu, K.S.: A distance measure between attributed relational graphs for pattern recognition. IEEE Trans. Syst., Man, Cybern. SMC-13(3), 353-362 (1983) · Zbl 0511.68060
[40] Sanyal, R.; Sottile, F.; Sturmfels, B., Orbitopes, Mathematika, 57, 2, 275-314 (2011) · Zbl 1315.52001
[41] Sharan, R.; Ideker, T., Modeling cellular machinery through biological network comparison, Nat. Biotechnol., 24, 4, 427 (2006)
[42] Sharan, R., Conserved patterns of protein interaction in multiple species, Proc. Natl. Acad. Sci., 102, 6, 1974-1979 (2005)
[43] Toh, K.C., Todd, M.J., Tütüncü, R.H.: SDPT3 — a MATLAB software package for semidefinite programming, version 1.3. Optimization Methods and Software 11(1-4), 545-581 (1999) · Zbl 0997.90060
[44] Wiskott, L.; Fellous, JM; Krüger, N.; Von Der Malsburg, C., Face recognition by elastic bunch graph matching, IEEE Trans. Pattern Anal. Mach. Intell., 19, 7, 775-779 (1997)
[45] Zeng, Z.; Tung, AK; Wang, J.; Feng, J.; Zhou, L., Comparing stars: on approximating graph edit distance, Proc. VLDB Endow., 2, 1, 25-36 (2009)
[46] Zhao, Q.; Karisch, SE; Rendl, F.; Wolkowicz, H., Semidefinite programming relaxations for the quadratic assignment problem, J. Combin. Optim., 2, 1, 71-109 (1998) · Zbl 0904.90145
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.