{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,2,21]],"date-time":"2025-02-21T03:41:12Z","timestamp":1740109272823,"version":"3.37.3"},"reference-count":46,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2020,9,16]],"date-time":"2020-09-16T00:00:00Z","timestamp":1600214400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2020,9,16]],"date-time":"2020-09-16T00:00:00Z","timestamp":1600214400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1350590","CCF-1637598"],"award-info":[{"award-number":["CCF-1350590","CCF-1637598"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000181","name":"Air Force Office of Scientific Research","doi-asserted-by":"publisher","award":["FA9550-16-1-0210"],"award-info":[{"award-number":["FA9550-16-1-0210"]}],"id":[{"id":"10.13039\/100000181","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000879","name":"Alfred P. Sloan Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100000879","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Math. Program."],"published-print":{"date-parts":[[2022,2]]},"DOI":"10.1007\/s10107-020-01564-4","type":"journal-article","created":{"date-parts":[[2020,9,16]],"date-time":"2020-09-16T15:26:26Z","timestamp":1600269986000},"page":"595-629","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Convex graph invariant relaxations for graph edit distance"],"prefix":"10.1007","volume":"191","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1416-4909","authenticated-orcid":false,"given":"Utkan Onur","family":"Candogan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Venkat","family":"Chandrasekaran","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,9,16]]},"reference":[{"key":"1564_CR1","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1016\/j.patrec.2017.10.007","volume":"100","author":"Z Abu-Aisheh","year":"2017","unstructured":"Abu-Aisheh, Z., et al.: Graph edit distance contest: results and future challenges. Pattern Recognit. Lett. 100, 96\u2013103 (2017)","journal-title":"Pattern Recognit. Lett."},{"key":"1564_CR2","volume-title":"Robust Optimization. Princeton Series in Applied Mathematics","author":"A Ben-Tal","year":"2009","unstructured":"Ben-Tal, A., El Ghaoui, L., Nemirovski, A.: Robust Optimization. Princeton Series in Applied Mathematics. Princeton University Press, Princeton (2009)"},{"key":"1564_CR3","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898718829","volume-title":"Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications","author":"A Ben-Tal","year":"2001","unstructured":"Ben-Tal, A., Nemirovski, A.: Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications, vol. 2. SIAM, London (2001)"},{"key":"1564_CR4","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611971262","volume-title":"Nonnegative Matrices in the Mathematical Sciences","author":"A Berman","year":"1994","unstructured":"Berman, A., Plemmons, R.J.: Nonnegative Matrices in the Mathematical Sciences, vol. 9. SIAM, London (1994)"},{"key":"1564_CR5","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1016\/j.patrec.2016.10.001","volume":"87","author":"S Bougleux","year":"2017","unstructured":"Bougleux, S., et al.: Graph edit distance as a quadratic assignment problem. Pattern Recognit. Lett. 87, 38\u201346 (2017)","journal-title":"Pattern Recognit. Lett."},{"key":"1564_CR6","volume-title":"Spectra of Graphs","author":"AE Brouwer","year":"2011","unstructured":"Brouwer, A.E., Haemers, W.H.: Spectra of Graphs. Springer, Berlin (2011)"},{"issue":"6","key":"1564_CR7","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1007\/s10208-009-9045-5","volume":"9","author":"EJ Cand\u00e8s","year":"2009","unstructured":"Cand\u00e8s, E.J., Recht, B.: Exact matrix completion via convex optimization. Found. Computat. Math. 9(6), 717 (2009)","journal-title":"Found. Computat. Math."},{"issue":"1","key":"1564_CR8","doi-asserted-by":"publisher","first-page":"735","DOI":"10.1137\/16M1075144","volume":"28","author":"UO Candogan","year":"2018","unstructured":"Candogan, U.O., Chandrasekaran, V.: Finding planted subgraphs with few eigenvalues using the Schur-Horn relaxation. SIAM J. Optim. 28(1), 735\u2013759 (2018)","journal-title":"SIAM J. Optim."},{"issue":"3","key":"1564_CR9","doi-asserted-by":"publisher","first-page":"513","DOI":"10.1137\/100816900","volume":"54","author":"V Chandrasekaran","year":"2012","unstructured":"Chandrasekaran, V., Parrilo, P.A., Willsky, A.S.: Convex graph invariants. SIAM Rev. 54(3), 513\u2013541 (2012)","journal-title":"SIAM Rev."},{"issue":"2","key":"1564_CR10","doi-asserted-by":"publisher","first-page":"572","DOI":"10.1137\/090761793","volume":"21","author":"V Chandrasekaran","year":"2011","unstructured":"Chandrasekaran, V., Sanghavi, S., Parrilo, P.A., Willsky, A.S.: Rank-sparsity incoherence for matrix decomposition. SIAM J. Optim. 21(2), 572\u2013596 (2011)","journal-title":"SIAM J. Optim."},{"issue":"7","key":"1564_CR11","doi-asserted-by":"publisher","first-page":"4324","DOI":"10.1109\/TIT.2013.2249572","volume":"59","author":"Y Chen","year":"2013","unstructured":"Chen, Y., Jalali, A., Sanghavi, S., Caramanis, C.: Low-rank matrix recovery from errors and erasures. IEEE Trans. Inf. Theory 59(7), 4324\u20134337 (2013)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"03","key":"1564_CR12","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1142\/S0218001404003228","volume":"18","author":"D Conte","year":"2004","unstructured":"Conte, D., Foggia, P., Sansone, C., Vento, M.: Thirty years of graph matching in pattern recognition. Int. J. Pattern Recognit. Artif. Intell. 18(03), 265\u2013298 (2004)","journal-title":"Int. J. Pattern Recognit. Artif. Intell."},{"doi-asserted-by":"crossref","unstructured":"Daller, \u00c9., Bougleux, S., Ga\u00fcz\u00e8re, B., Brun, L.: Approximate graph edit distance by several local searches in parallel. In: 7th International Conference on Pattern Recognition Applications and Methods (2018)","key":"1564_CR13","DOI":"10.5220\/0006599901490158"},{"key":"1564_CR14","doi-asserted-by":"publisher","first-page":"1008","DOI":"10.1287\/moor.1090.0419","volume":"34","author":"Y Ding","year":"2009","unstructured":"Ding, Y., Wolckowicz, H.: A low-dimensional semidefinite relaxation for the quadratic assignment problem. Math. Oper. Res. 34, 1008\u20131022 (2009)","journal-title":"Math. Oper. Res."},{"issue":"5","key":"1564_CR15","doi-asserted-by":"crossref","first-page":"2197","DOI":"10.1073\/pnas.0437847100","volume":"100","author":"DL Donoho","year":"2003","unstructured":"Donoho, D.L., Elad, M.: Optimally sparse representation in general (nonorthogonal) dictionaries via $$\\ell $$1 minimization. Proc. Natl. Acad. Sci. 100(5), 2197\u20132202 (2003)","journal-title":"Proc. Natl. Acad. Sci."},{"doi-asserted-by":"crossref","unstructured":"Finke, G., Burkard, R.E., Rendl, F.: Quadratic assignment problems. In: Surveys in Combinatorial Optimization, pp. 61\u201382. North-Holland (2011). https:\/\/www.sciencedirect.com\/science\/article\/pii\/S0304020808732328","key":"1564_CR16","DOI":"10.1016\/S0304-0208(08)73232-8"},{"doi-asserted-by":"crossref","unstructured":"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\u2013203. Springer, Berlin (2013)","key":"1564_CR17","DOI":"10.1007\/978-3-642-38221-5_21"},{"key":"1564_CR18","volume-title":"Computers and Intractability","author":"MR Garey","year":"2002","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability, vol. 29. W.H. Freeman, New York (2002)"},{"issue":"6","key":"1564_CR19","doi-asserted-by":"publisher","first-page":"1115","DOI":"10.1145\/227683.227684","volume":"42","author":"MX Goemans","year":"1995","unstructured":"Goemans, M.X., Williamson, D.P.: Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM (JACM) 42(6), 1115\u20131145 (1995)","journal-title":"J. ACM (JACM)"},{"unstructured":"Grant, M.C., Boyd, S.P.: CVX: Matlab software for disciplined convex programming, version 2.0 beta. http:\/\/cvxr.com\/cvx, September 2013","key":"1564_CR20"},{"doi-asserted-by":"publisher","unstructured":"Grant, M.C., Boyd, S.P.: Graph implementations for nonsmooth convex programs. In: Recent Advances in Learning and Control, pp. 95\u2013110. Springer, London (2008). https:\/\/doi.org\/10.1007\/978-1-84800-155-8_7","key":"1564_CR21","DOI":"10.1007\/978-1-84800-155-8_7"},{"issue":"2","key":"1564_CR22","doi-asserted-by":"publisher","first-page":"100","DOI":"10.1109\/TSSC.1968.300136","volume":"4","author":"PE Hart","year":"1968","unstructured":"Hart, P.E., Nilsson, N.J., Raphael, B.: A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Syst. Sci. Cybernet. 4(2), 100\u2013107 (1968)","journal-title":"IEEE Trans. Syst. Sci. Cybernet."},{"doi-asserted-by":"crossref","unstructured":"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.\u00a034. Schloss Dagstuhl-Leibniz-Zentrum f\u00fcr Informatik (2013)","key":"1564_CR23","DOI":"10.1145\/2576768.2598390"},{"issue":"2","key":"1564_CR24","doi-asserted-by":"publisher","first-page":"113","DOI":"10.1016\/0031-3203(86)90017-8","volume":"19","author":"DK Isenor","year":"1986","unstructured":"Isenor, D.K., Zaky, S.G.: Fingerprint identification using graph matching. Pattern Recognit. 19(2), 113\u2013122 (1986)","journal-title":"Pattern Recognit."},{"issue":"2","key":"1564_CR25","doi-asserted-by":"publisher","first-page":"371","DOI":"10.1089\/10665270252935511","volume":"9","author":"T Jiang","year":"2002","unstructured":"Jiang, T., Lin, G., Ma, B., Zhang, K.: A general edit distance between RNA structures. J. Comput. Biol. 9(2), 371\u2013388 (2002)","journal-title":"J. Comput. Biol."},{"issue":"4","key":"1564_CR26","doi-asserted-by":"publisher","first-page":"685","DOI":"10.11650\/twjm\/1500407302","volume":"4","author":"MJ Jou","year":"2000","unstructured":"Jou, M.J., Chang, G.J.: The number of maximum independent sets in graphs. Taiwan. J. Math. 4(4), 685\u2013695 (2000)","journal-title":"Taiwan. J. Math."},{"issue":"8","key":"1564_CR27","doi-asserted-by":"publisher","first-page":"1200","DOI":"10.1109\/TPAMI.2006.152","volume":"28","author":"D Justice","year":"2006","unstructured":"Justice, D., Hero, A.: A binary linear programming formulation of the graph edit distance. IEEE Trans. Pattern Anal. Mach. Intell. 28(8), 1200\u20131214 (2006)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"unstructured":"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\u20131122 (2009)","key":"1564_CR28"},{"issue":"6","key":"1564_CR29","doi-asserted-by":"publisher","first-page":"1258","DOI":"10.1109\/TPAMI.2013.223","volume":"36","author":"ZY Liu","year":"2014","unstructured":"Liu, Z.Y., Qiao, H.: GNCCP\u2014graduated nonconvexity and concavity procedure. IEEE Trans. Pattern Anal. Mach. Intell. 36(6), 1258\u20131267 (2014)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"7","key":"1564_CR30","doi-asserted-by":"publisher","first-page":"617","DOI":"10.1016\/0031-3203(91)90029-5","volume":"24","author":"SW Lu","year":"1991","unstructured":"Lu, S.W., Ren, Y., Suen, C.Y.: Hierarchical attributed graph representation and recognition of handwritten Chinese characters. Pattern Recognit. 24(7), 617\u2013632 (1991)","journal-title":"Pattern Recognit."},{"issue":"7","key":"1564_CR31","doi-asserted-by":"publisher","first-page":"734","DOI":"10.1039\/c2ib00140c","volume":"4","author":"V Memi\u0161evi\u0107","year":"2012","unstructured":"Memi\u0161evi\u0107, V., Pr\u017eulj, N.: C-GRAAL: common-neighbors-based global GRAph ALignment of biological networks. Integr. Biol. 4(7), 734\u2013743 (2012)","journal-title":"Integr. Biol."},{"issue":"4","key":"1564_CR32","doi-asserted-by":"publisher","first-page":"533","DOI":"10.4153\/CJM-1965-053-6","volume":"17","author":"TS Motzkin","year":"1965","unstructured":"Motzkin, T.S., Straus, E.G.: Maxima for graphs and a new proof of a theorem of Tur\u00e1n. Can. J. Math. 17(4), 533\u2013540 (1965)","journal-title":"Can. J. Math."},{"doi-asserted-by":"crossref","unstructured":"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\u2013189. Springer, Berlin (2004)","key":"1564_CR33","DOI":"10.1007\/978-3-540-27868-9_18"},{"doi-asserted-by":"crossref","unstructured":"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\u2013200. Springer, Berlin (2005)","key":"1564_CR34","DOI":"10.1007\/11527923_20"},{"issue":"10","key":"1564_CR35","doi-asserted-by":"publisher","first-page":"1852","DOI":"10.1016\/j.patcog.2006.04.012","volume":"39","author":"M Neuhaus","year":"2006","unstructured":"Neuhaus, M., Bunke, H.: Edit distance-based kernel functions for structural pattern classification. Pattern Recognit. 39(10), 1852\u20131863 (2006)","journal-title":"Pattern Recognit."},{"issue":"7","key":"1564_CR36","doi-asserted-by":"publisher","first-page":"950","DOI":"10.1016\/j.imavis.2008.04.004","volume":"27","author":"K Riesen","year":"2009","unstructured":"Riesen, K., Bunke, H.: Approximate graph edit distance computation by means of bipartite graph matching. Image Vis. Comput. 27(7), 950\u2013959 (2009)","journal-title":"Image Vis. Comput."},{"doi-asserted-by":"crossref","unstructured":"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\u2013140. Springer, Berlin (2014)","key":"1564_CR37","DOI":"10.1007\/978-3-319-11656-3_12"},{"key":"1564_CR38","doi-asserted-by":"publisher","DOI":"10.1515\/9781400873173","volume-title":"Convex Analysis","author":"RT Rockafellar","year":"1970","unstructured":"Rockafellar, R.T.: Convex Analysis, vol. 28. Princeton University Press, Princeton (1970)"},{"doi-asserted-by":"crossref","unstructured":"Sanfeliu, A., Fu, K.S.: A distance measure between attributed relational graphs for pattern recognition. IEEE Trans. Syst., Man, Cybern. SMC-13(3), 353\u2013362 (1983)","key":"1564_CR39","DOI":"10.1109\/TSMC.1983.6313167"},{"issue":"2","key":"1564_CR40","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1112\/S002557931100132X","volume":"57","author":"R Sanyal","year":"2011","unstructured":"Sanyal, R., Sottile, F., Sturmfels, B.: Orbitopes. Mathematika 57(2), 275\u2013314 (2011)","journal-title":"Mathematika"},{"issue":"4","key":"1564_CR41","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1038\/nbt1196","volume":"24","author":"R Sharan","year":"2006","unstructured":"Sharan, R., Ideker, T.: Modeling cellular machinery through biological network comparison. Nat. Biotechnol. 24(4), 427 (2006)","journal-title":"Nat. Biotechnol."},{"issue":"6","key":"1564_CR42","doi-asserted-by":"publisher","first-page":"1974","DOI":"10.1073\/pnas.0409522102","volume":"102","author":"R Sharan","year":"2005","unstructured":"Sharan, R., et al.: Conserved patterns of protein interaction in multiple species. Proc. Natl. Acad. Sci. 102(6), 1974\u20131979 (2005)","journal-title":"Proc. Natl. Acad. Sci."},{"doi-asserted-by":"crossref","unstructured":"Toh, K.C., Todd, M.J., T\u00fct\u00fcnc\u00fc, R.H.: SDPT3 \u2014 a MATLAB software package for semidefinite programming, version 1.3. Optimization Methods and Software 11(1-4), 545\u2013581 (1999)","key":"1564_CR43","DOI":"10.1080\/10556789908805762"},{"issue":"7","key":"1564_CR44","doi-asserted-by":"publisher","first-page":"775","DOI":"10.1109\/34.598235","volume":"19","author":"L Wiskott","year":"1997","unstructured":"Wiskott, L., Fellous, J.M., Kr\u00fcger, N., Von Der Malsburg, C.: Face recognition by elastic bunch graph matching. IEEE Trans. Pattern Anal. Mach. Intell. 19(7), 775\u2013779 (1997)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"1","key":"1564_CR45","doi-asserted-by":"publisher","first-page":"25","DOI":"10.14778\/1687627.1687631","volume":"2","author":"Z Zeng","year":"2009","unstructured":"Zeng, Z., Tung, A.K., Wang, J., Feng, J., Zhou, L.: Comparing stars: on approximating graph edit distance. Proc. VLDB Endow. 2(1), 25\u201336 (2009)","journal-title":"Proc. VLDB Endow."},{"issue":"1","key":"1564_CR46","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1023\/A:1009795911987","volume":"2","author":"Q Zhao","year":"1998","unstructured":"Zhao, Q., Karisch, S.E., Rendl, F., Wolkowicz, H.: Semidefinite programming relaxations for the quadratic assignment problem. J. Combin. Optim. 2(1), 71\u2013109 (1998)","journal-title":"J. Combin. Optim."}],"container-title":["Mathematical Programming"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01564-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s10107-020-01564-4\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s10107-020-01564-4.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,2,23]],"date-time":"2022-02-23T02:07:44Z","timestamp":1645582064000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s10107-020-01564-4"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,9,16]]},"references-count":46,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2022,2]]}},"alternative-id":["1564"],"URL":"https:\/\/doi.org\/10.1007\/s10107-020-01564-4","relation":{},"ISSN":["0025-5610","1436-4646"],"issn-type":[{"type":"print","value":"0025-5610"},{"type":"electronic","value":"1436-4646"}],"subject":[],"published":{"date-parts":[[2020,9,16]]},"assertion":[{"value":"17 April 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"4 September 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"16 September 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}