{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,20]],"date-time":"2026-02-20T11:13:21Z","timestamp":1771586001015,"version":"3.50.1"},"reference-count":36,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,2,11]],"date-time":"2022-02-11T00:00:00Z","timestamp":1644537600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,2,11]],"date-time":"2022-02-11T00:00:00Z","timestamp":1644537600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"name":"Singapore Ministry of Education Academic Research","award":["Fund Tier 1 R-155-000-214-114"],"award-info":[{"award-number":["Fund Tier 1 R-155-000-214-114"]}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","award":["EP\/V013432\/1"],"award-info":[{"award-number":["EP\/V013432\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Stat Comput"],"published-print":{"date-parts":[[2022,2,15]]},"abstract":"Abstract<\/jats:title>Graph matching is a fruitful area in terms of both algorithms and theories. Given two graphs $$G_1 = (V_1, E_1)$$<\/jats:tex-math>\n \n \n G<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n =<\/mml:mo>\n \n (<\/mml:mo>\n \n V<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n E<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $$G_2 = (V_2, E_2)$$<\/jats:tex-math>\n \n \n G<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n =<\/mml:mo>\n \n (<\/mml:mo>\n \n V<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n ,<\/mml:mo>\n \n E<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n )<\/mml:mo>\n <\/mml:mrow>\n <\/mml:mrow>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, where $$V_1$$<\/jats:tex-math>\n \n V<\/mml:mi>\n 1<\/mml:mn>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> and $$V_2$$<\/jats:tex-math>\n \n V<\/mml:mi>\n 2<\/mml:mn>\n <\/mml:msub>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula> are the same or largely overlapped upon an unknown permutation $$\\pi ^*$$<\/jats:tex-math>\n \n \u03c0<\/mml:mi>\n \u2217<\/mml:mo>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, graph matching is to seek the correct mapping $$\\pi ^*$$<\/jats:tex-math>\n \n \u03c0<\/mml:mi>\n \u2217<\/mml:mo>\n <\/mml:msup>\n <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. In this paper, we exploit the degree information, which was previously used only in noiseless graphs and perfectly-overlapping Erd\u0151s\u2013R\u00e9nyi random graphs matching. We are concerned with graph matching of partially-overlapping graphs and stochastic block models, which are more useful in tackling real-life problems. We propose the edge exploited degree profile graph matching method and two refined variations. We conduct a thorough analysis of our proposed methods\u2019 performances in a range of challenging scenarios, including coauthorship data set and a zebrafish neuron activity data set. Our methods are proved to be numerically superior than the state-of-the-art methods. The algorithms are implemented in the R (A language and environment for statistical computing, R Foundation for Statistical Computing, Vienna, 2020) package GMPro (GMPro: graph matching with degree profiles, 2020).<\/jats:p>","DOI":"10.1007\/s11222-022-10079-1","type":"journal-article","created":{"date-parts":[[2022,2,11]],"date-time":"2022-02-11T21:05:23Z","timestamp":1644613523000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Graph matching beyond perfectly-overlapping Erd\u0151s\u2013R\u00e9nyi random graphs"],"prefix":"10.1007","volume":"32","author":[{"given":"Yaofang","family":"Hu","sequence":"first","affiliation":[]},{"given":"Wanjie","family":"Wang","sequence":"additional","affiliation":[]},{"given":"Yi","family":"Yu","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,2,11]]},"reference":[{"key":"10079_CR1","doi-asserted-by":"crossref","unstructured":"Cherkassky, B.V., Goldberg, A.V., Martin, P., Setubal, J.C., Stolfi, J.: Augment or push: a computational study of bipartite matching and unit-capacity flow algorithms. J. Exp. Algo. (JEA) 3, 8\u2013es (1998)","DOI":"10.1145\/297096.297140"},{"issue":"03","key":"10079_CR2","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 Recogn. Artif. Intell. 18(03), 265\u2013298 (2004)","journal-title":"Int. J. Pattern Recogn. Artif. Intell."},{"key":"10079_CR3","unstructured":"Csardi, G., Nepusz, T.: The igraph software package for complex network research. Int. J. Compl. Syst. 1695 (2006). http:\/\/igraph.org"},{"issue":"1","key":"10079_CR4","first-page":"85","volume":"6","author":"T Czajka","year":"2008","unstructured":"Czajka, T., Pandurangan, G.: Improved random graph isomorphism. J. Disc. Algo. 6(1), 85\u201392 (2008)","journal-title":"J. Disc. Algo."},{"key":"10079_CR5","unstructured":"Ding, J., Ma, Z., Wu, Y., Xu, J.: Efficient random graph matching via degree profiles. arXiv preprint arXiv:1811.07821 (2018)"},{"key":"10079_CR6","doi-asserted-by":"crossref","unstructured":"Eppstein, D.: Subgraph isomorphism in planar graphs and related problems. In: Graph Algorithms and Applications I, pp. 283\u2013309. World Scientific (2002)","DOI":"10.1142\/9789812777638_0014"},{"issue":"26","key":"10079_CR7","first-page":"290","volume":"6","author":"P Erd\u00f6s","year":"1959","unstructured":"Erd\u00f6s, P., R\u00e9nyi, A.: On random graphs. Publ. Math. 6(26), 290\u2013297 (1959)","journal-title":"Publ. Math."},{"key":"10079_CR8","unstructured":"Fishkind, D.E., Adali, S., Patsolic, H.G., Meng, L., Singh, D., Lyzinski, V., Priebe, C.E.: Seeded graph matching. arXiv preprint arXiv:1209.0367 (2012)"},{"issue":"01","key":"10079_CR9","doi-asserted-by":"publisher","first-page":"1450001","DOI":"10.1142\/S0218001414500013","volume":"28","author":"P Foggia","year":"2014","unstructured":"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(01), 1450001 (2014)","journal-title":"Int. J. Pattern Recogn. Artif. Intell."},{"issue":"4","key":"10079_CR10","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1109\/34.491619","volume":"18","author":"S Gold","year":"1996","unstructured":"Gold, S., Rangarajan, A.: A graduated assignment algorithm for graph matching. IEEE Trans. Pattern Anal. Mach. Intell. 18(4), 377\u2013388 (1996)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"key":"10079_CR11","doi-asserted-by":"crossref","unstructured":"Haghighi, A.D., Ng, A.Y., Manning, C.D.: Robust textual inference via graph matching. In: Proceedings of the Conference on Human Language Technology and Empirical Methods in Natural Language Processing, pp. 387\u2013394. Association for Computational Linguistics (2005)","DOI":"10.3115\/1220575.1220624"},{"key":"10079_CR12","unstructured":"Hu, Y., Wang, W., Yu, Y.: GMPro: Graph Matching with Degree Profiles (2020). https:\/\/CRAN.R-project.org\/package=GMPro. R package version 0.1.0"},{"key":"10079_CR13","unstructured":"Jaggi, M.: Revisiting frank-wolfe: projection-free sparse convex optimization. In: Proceedings of the 30th International Conference on Machine Learning, CONF, pp. 427\u2013435 (2013)"},{"issue":"4","key":"10079_CR14","first-page":"1779","volume":"10","author":"P Ji","year":"2016","unstructured":"Ji, P., Jin, J.: Coauthorship and citation networks for statisticians. Ann. Appl. Stat. 10(4), 1779\u20131812 (2016)","journal-title":"Ann. Appl. Stat."},{"issue":"1","key":"10079_CR15","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1214\/14-AOS1265","volume":"43","author":"J Jin","year":"2015","unstructured":"Jin, J.: Fast community detection by score. Ann. Stat. 43(1), 57\u201389 (2015)","journal-title":"Ann. Stat."},{"issue":"1","key":"10079_CR16","doi-asserted-by":"publisher","first-page":"527","DOI":"10.1186\/s12859-016-1395-9","volume":"17","author":"E Kazemi","year":"2016","unstructured":"Kazemi, E., Hassani, H., Grossglauser, M., Modarres, H.P.: Proper: global protein interaction network alignment through percolation matching. BMC Bioinform. 17(1), 527 (2016)","journal-title":"BMC Bioinform."},{"key":"10079_CR17","doi-asserted-by":"crossref","unstructured":"Kazemi, E., Yartseva, L., Grossglauser, M.: When can two unlabeled networks be aligned under partial overlap? In: 2015 53rd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 33\u201342. IEEE (2015)","DOI":"10.1109\/ALLERTON.2015.7446983"},{"key":"10079_CR18","doi-asserted-by":"crossref","unstructured":"Leordeanu, M., Hebert, M.: A spectral technique for correspondence problems using pairwise constraints. In: Tenth IEEE International Conference on Computer Vision (ICCV\u201905), vols. 1,\u00a02, pp. 1482\u20131489. IEEE (2005)","DOI":"10.1109\/ICCV.2005.20"},{"key":"10079_CR19","unstructured":"Li, L., Campbell, W.M.: Matching community structure across online social networks. arXiv preprint arXiv:1608.01373 (2016)"},{"issue":"7","key":"10079_CR20","doi-asserted-by":"publisher","first-page":"1451","DOI":"10.1109\/TPAMI.2012.45","volume":"34","author":"ZY Liu","year":"2012","unstructured":"Liu, Z.Y., Qiao, H., Xu, L.: An extended path following algorithm for graph-matching problem. IEEE Trans. Pattern Anal. Mach. Intell. 34(7), 1451\u20131456 (2012)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"1","key":"10079_CR21","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1109\/TPAMI.2015.2424894","volume":"38","author":"V Lyzinski","year":"2015","unstructured":"Lyzinski, V., Fishkind, D.E., Fiori, M., Vogelstein, J.T., Priebe, C.E., Sapiro, G.: Graph matching: relax at your own risk. IEEE Trans. Pattern Anal. Mach. Intell. 38(1), 60\u201373 (2015)","journal-title":"IEEE Trans. Pattern Anal. Mach. Intell."},{"issue":"1","key":"10079_CR22","first-page":"3513","volume":"15","author":"V Lyzinski","year":"2014","unstructured":"Lyzinski, V., Fishkind, D.E., Priebe, C.E.: Seeded graph matching for correlated erd\u00f6s-r\u00e9nyi graphs. J. Mach. Learn. Res. 15(1), 3513\u20133540 (2014)","journal-title":"J. Mach. Learn. Res."},{"issue":"4","key":"10079_CR23","doi-asserted-by":"publisher","first-page":"786","DOI":"10.1080\/10618600.2017.1321551","volume":"26","author":"V Lyzinski","year":"2017","unstructured":"Lyzinski, V., Park, Y., Priebe, C.E., Trosset, M.: Fast embedding for jofc using the raw stress criterion. J. Comput. Graph. Stat. 26(4), 786\u2013802 (2017)","journal-title":"J. Comput. Graph. Stat."},{"key":"10079_CR24","unstructured":"Mossel, E., Ross, N.: Shotgun assembly of labeled graphs. IEEE Trans. Netw. Sci. Eng. (2017)"},{"key":"10079_CR25","doi-asserted-by":"crossref","unstructured":"Narayanan, A., Shmatikov, V.: De-anonymizing social networks. In: 2009 30th IEEE Symposium on Security and Privacy, pp. 173\u2013187. IEEE (2009)","DOI":"10.1109\/SP.2009.22"},{"key":"10079_CR26","unstructured":"Patsolic, H.G., Park, Y., Lyzinski, V., Priebe, C.E.: Vertex nomination via seeded graph matching. arXiv preprint arXiv:1705.00674 (2017)"},{"key":"10079_CR27","doi-asserted-by":"crossref","unstructured":"Pedarsani, P., Grossglauser, M.: On the privacy of anonymized networks. In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 1235\u20131243 (2011)","DOI":"10.1145\/2020408.2020596"},{"issue":"7","key":"10079_CR28","doi-asserted-by":"publisher","first-page":"727","DOI":"10.1038\/nmeth.2964","volume":"11","author":"R Prevedel","year":"2014","unstructured":"Prevedel, R., Yoon, Y.G., Hoffmann, M., Pak, N., Wetzstein, G., Kato, S., Schr\u00f6del, T., Raskar, R., Zimmer, M., Boyden, E.S.: Simultaneous whole-animal 3d imaging of neuronal activity using light-field microscopy. Nat. Methods 11(7), 727\u2013730 (2014)","journal-title":"Nat. Methods"},{"key":"10079_CR29","unstructured":"R Core Team: R: A language and environment for statistical computing. R Foundation for Statistical Computing, Vienna, Austria (2020). https:\/\/www.R-project.org\/"},{"key":"10079_CR30","doi-asserted-by":"publisher","first-page":"353","DOI":"10.1109\/TSMC.1983.6313167","volume":"3","author":"A Sanfeliu","year":"1983","unstructured":"Sanfeliu, A., Fu, K.S.: A distance measure between attributed relational graphs for pattern recognition. IEEE Trans. Syst. Man Cybern. 3, 353\u2013362 (1983)","journal-title":"IEEE Trans. Syst. Man Cybern."},{"key":"10079_CR31","unstructured":"Scheinerman, E.R., Ullman, D.H.: Fractional Graph Theory: A Rational Approach to the Theory of Graphs. Courier Corp. (2011)"},{"key":"10079_CR32","doi-asserted-by":"crossref","unstructured":"Schellewald, C., Schn\u00f6rr, C.: Probabilistic subgraph matching based on convex relaxation. In: International Workshop on Energy Minimization Methods in Computer Vision and Pattern Recognition, pp. 171\u2013186. Springer (2005)","DOI":"10.1007\/11585978_12"},{"issue":"1","key":"10079_CR33","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/321921.321925","volume":"23","author":"JR Ullmann","year":"1976","unstructured":"Ullmann, J.R.: An algorithm for subgraph isomorphism. J. ACM (JACM) 23(1), 31\u201342 (1976)","journal-title":"J. ACM (JACM)"},{"key":"10079_CR34","doi-asserted-by":"crossref","unstructured":"Villani, C.: The wasserstein distances. In: Optimal Transport, pp. 93\u2013111. Springer (2009)","DOI":"10.1007\/978-3-540-71050-9_6"},{"key":"10079_CR35","doi-asserted-by":"crossref","unstructured":"Yan, J., Yin, X.C., Lin, W., Deng, C., Zha, H., Yang, X.: A short survey of recent advances in graph matching. In: Proceedings of the 2016 ACM on International Conference on Multimedia Retrieval, pp. 167\u2013174 (2016)","DOI":"10.1145\/2911996.2912035"},{"key":"10079_CR36","doi-asserted-by":"crossref","unstructured":"Young, S.J., Scheinerman, E.R.: Random dot product graph models for social networks. In: International Workshop on Algorithms and Models for the Web-Graph, pp. 138\u2013149. Springer (2007)","DOI":"10.1007\/978-3-540-77004-6_11"}],"container-title":["Statistics and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11222-022-10079-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11222-022-10079-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11222-022-10079-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,3,2]],"date-time":"2022-03-02T19:09:58Z","timestamp":1646248198000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11222-022-10079-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,2,11]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,2,15]]}},"alternative-id":["10079"],"URL":"https:\/\/doi.org\/10.1007\/s11222-022-10079-1","relation":{},"ISSN":["0960-3174","1573-1375"],"issn-type":[{"value":"0960-3174","type":"print"},{"value":"1573-1375","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,2,11]]},"assertion":[{"value":"21 July 2020","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"19 January 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"11 February 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}],"article-number":"19"}}