{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,9]],"date-time":"2026-01-09T19:06:38Z","timestamp":1767985598796,"version":"3.49.0"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T00:00:00Z","timestamp":1620000000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Shanghai Sailing Program","award":["18YF1401200"],"award-info":[{"award-number":["18YF1401200"]}]},{"DOI":"10.13039\/501100003399","name":"Shanghai Science and Technology Commission","doi-asserted-by":"crossref","award":["17JC1420200"],"award-info":[{"award-number":["17JC1420200"]}],"id":[{"id":"10.13039\/501100003399","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["61802069"],"award-info":[{"award-number":["61802069"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/501100003399","name":"Science and Technology Commission of Shanghai Municipality","doi-asserted-by":"crossref","award":["19511120700"],"award-info":[{"award-number":["19511120700"]}],"id":[{"id":"10.13039\/501100003399","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2021,6,30]]},"abstract":"<jats:p>\n            Driven by many real applications, we study the problem of seeded graph matching. Given two graphs\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            and\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            , and a small set\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            of pre-matched node pairs\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            where\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            and\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            , the problem is to identify a matching between\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            and\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            growing from\n            <jats:inline-formula>\n              <jats:alternatives>\n                <jats:tex-math>\n                  \n                <\/jats:tex-math>\n              <\/jats:alternatives>\n            <\/jats:inline-formula>\n            , such that each pair in the matching corresponds to the same underlying entity. Recent studies on efficient and effective seeded graph matching have drawn a great deal of attention and many popular methods are largely based on exploring the similarity between local structures to identify matching pairs. While these recent techniques work provably well on random graphs, their accuracy is low over many real networks. In this work, we propose to utilize higher-order neighboring information to improve the matching accuracy and efficiency. As a result, a new framework of seeded graph matching is proposed, which employs Personalized PageRank (PPR) to quantify the matching score of each node pair. To further boost the matching accuracy, we propose a novel postponing strategy, which postpones the selection of pairs that have competitors with similar matching scores. We show that the postpone strategy indeed significantly improves the matching accuracy. To improve the scalability of matching large graphs, we also propose efficient approximation techniques based on algorithms for computing PPR heavy hitters. Our comprehensive experimental studies on large-scale real datasets demonstrate that, compared with state-of-the-art approaches, our framework not only increases the precision and recall both by a significant margin but also achieves speed-up up to more than one order of magnitude.\n          <\/jats:p>","DOI":"10.1145\/3442340","type":"journal-article","created":{"date-parts":[[2021,5,3]],"date-time":"2021-05-03T22:07:27Z","timestamp":1620079647000},"page":"1-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":4,"title":["Efficient and High-Quality Seeded Graph Matching: Employing Higher-order Structural Information"],"prefix":"10.1145","volume":"15","author":[{"given":"Haida","family":"Zhang","sequence":"first","affiliation":[{"name":"University of New South Wales, Sydney NSW, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zengfeng","family":"Huang","sequence":"additional","affiliation":[{"name":"Fudan University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xuemin","family":"Lin","sequence":"additional","affiliation":[{"name":"University of New South Wales, Sydney NSW, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zhe","family":"Lin","sequence":"additional","affiliation":[{"name":"East China Normal University, Shanghai, China"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Wenjie","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of New South Wales, Sydney NSW, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ying","family":"Zhang","sequence":"additional","affiliation":[{"name":"University of Technology Sydney, Ultimo NSW, Australia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2021,5,3]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/1777879.1777891"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.44"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/3045118.3045309"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1242572.1242598"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.135"},{"key":"e_1_2_1_6_1","volume-title":"Higher-order organization of complex networks. Science 353, 6295","author":"Benson Austin R.","year":"2016","unstructured":"Austin R. Benson , David F. Gleich , and Jure Leskovec . 2016. Higher-order organization of complex networks. Science 353, 6295 ( 2016 ), 163\u2013166. Austin R. Benson, David F. Gleich, and Jure Leskovec. 2016. Higher-order organization of complex networks. Science 353, 6295 (2016), 163\u2013166."},{"key":"e_1_2_1_7_1","volume-title":"Johnson","author":"Garey Michael R.","year":"2002","unstructured":"Michael R. Garey and David S . Johnson . 2002 . Computers and Intractability. Vol. 29 . W.H. Freeman , New York. Michael R. Garey and David S. Johnson. 2002. Computers and Intractability. Vol. 29. W.H. Freeman, New York."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/140976649"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.5555\/1958573.1958588"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3269206.3271788"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020512"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIFS.2016.2529591"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/2794367.2794371"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-10-S1-S59"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.1611275114"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.14778\/2732269.2732274"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1772690.1772756"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1080\/15427951.2009.10129177"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/2999134.2999195"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASONAM.2012.184"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1718487.1718519"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2016.2595583"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/2976456.2976583"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2009.22"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2245276.2245413"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3018661.3018731"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020596"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACSSC.2017.8335178"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0806627105"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1401890.1402008"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/1756006.1859891"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDCS.2018.00065"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3183713.3196919"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2010.21"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-013-0693-z"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2512938.2512952"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220079"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098069"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 3rd International ICWSM Conference. 354\u2013357","author":"Zafarani Reza","year":"2009","unstructured":"Reza Zafarani and Huan Liu . 2009 . Connecting corresponding identities across communities . In Proceedings of the 3rd International ICWSM Conference. 354\u2013357 . Reza Zafarani and Huan Liu. 2009. Connecting corresponding identities across communities. In Proceedings of the 3rd International ICWSM Conference. 354\u2013357."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939766"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783268"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2017.2784430"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2015.2485222"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-012-0292-8"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3442340","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3442340","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:48:15Z","timestamp":1750193295000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3442340"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,3]]},"references-count":44,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3442340"],"URL":"https:\/\/doi.org\/10.1145\/3442340","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,3]]},"assertion":[{"value":"2019-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-05-03","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}