{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,21]],"date-time":"2026-04-21T14:47:51Z","timestamp":1776782871977,"version":"3.51.2"},"reference-count":71,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2023,2,24]],"date-time":"2023-02-24T00:00:00Z","timestamp":1677196800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2023,8,31]]},"abstract":"<jats:p>\n            What is the best way to match the nodes of two graphs? This\n            <jats:italic>graph alignment<\/jats:italic>\n            problem generalizes graph isomorphism and arises in applications from social network analysis to bioinformatics. Some solutions assume that auxiliary information on known matches or node or edge attributes is available, or utilize arbitrary graph features. Such methods fare poorly in the pure form of the problem, in which only graph structures are given. Other proposals translate the problem to one of aligning node embeddings, yet, by doing so, provide only a single-scale view of the graph.\n          <\/jats:p>\n          <jats:p>In this article, we transfer the shape-analysis concept of functional maps from the continuous to the discrete case, and treat the graph alignment problem as a special case of the problem of finding a mapping between functions on graphs. We present GRASP, a method that first establishes a correspondence between functions derived from Laplacian matrix eigenvectors, which capture multiscale structural characteristics, and then exploits this correspondence to align nodes. We enhance the basic form of GRASP by altering two of its components, namely the embedding method and the assignment procedure it employs, leveraging its modular, hence adaptable design. Our experimental study, featuring noise levels higher than anything used in previous studies, shows that the enhanced form of GRASP outperforms scalable state-of-the-art methods for graph alignment across noise levels and graph types, and performs competitively with respect to the best non-scalable ones. We include in our study another modular graph alignment algorithm, CONE, which is also adaptable thanks to its modular nature, and show it can manage graphs with skewed power-law degree distributions.<\/jats:p>","DOI":"10.1145\/3561058","type":"journal-article","created":{"date-parts":[[2022,9,15]],"date-time":"2022-09-15T09:53:08Z","timestamp":1663235588000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["GRASP: Scalable Graph Alignment by Spectral Corresponding Functions"],"prefix":"10.1145","volume":"17","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-2170-4635","authenticated-orcid":false,"given":"Judith","family":"Hermanns","sequence":"first","affiliation":[{"name":"Aarhus University, Aarhus, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5078-6468","authenticated-orcid":false,"given":"Konstantinos","family":"Skitsas","sequence":"additional","affiliation":[{"name":"Aarhus University, Aarhus, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5519-7961","authenticated-orcid":false,"given":"Anton","family":"Tsitsulin","sequence":"additional","affiliation":[{"name":"Google Research, New York, NY"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5638-3712","authenticated-orcid":false,"given":"Marina","family":"Munkhoeva","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Intelligent Systems, T\u00fcbingen, Germany"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4823-4060","authenticated-orcid":false,"given":"Alexander","family":"Kyster","sequence":"additional","affiliation":[{"name":"Aarhus University, Aarhus, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-5230-5231","authenticated-orcid":false,"given":"Simon","family":"Nielsen","sequence":"additional","affiliation":[{"name":"Aarhus University, Aarhus, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9699-8730","authenticated-orcid":false,"given":"Alexander M.","family":"Bronstein","sequence":"additional","affiliation":[{"name":"Technion, Haifa, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8256-2258","authenticated-orcid":false,"given":"Davide","family":"Mottin","sequence":"additional","affiliation":[{"name":"Aarhus University, Aarhus, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0509-9129","authenticated-orcid":false,"given":"Panagiotis","family":"Karras","sequence":"additional","affiliation":[{"name":"Aarhus University, Aarhus, Denmark"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2023,2,24]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"publisher","DOI":"10.5555\/928525"},{"key":"e_1_3_2_3_2","doi-asserted-by":"publisher","DOI":"10.5555\/3115489.3115871"},{"key":"e_1_3_2_4_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btt071"},{"issue":"1","key":"e_1_3_2_5_2","first-page":"3:1\u20133:31","article-title":"Message-passing algorithms for sparse network alignment","volume":"7","author":"Bayati Mohsen","year":"2013","unstructured":"Mohsen Bayati, David F. Gleich, Amin Saberi, and Ying Wang. 2013. Message-passing algorithms for sparse network alignment. Transactions on Knowledge Discovery from Data 7, 1 (2013), 3:1\u20133:31.","journal-title":"Transactions on Knowledge Discovery from Data"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.5555\/2976456.2976473"},{"key":"e_1_3_2_7_2","doi-asserted-by":"publisher","DOI":"10.1109\/34.121791"},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3340531.3412136"},{"key":"e_1_3_2_9_2","doi-asserted-by":"publisher","DOI":"10.1145\/3308558.3313499"},{"key":"e_1_3_2_10_2","volume-title":"Spectral Graph Theory","author":"Chung Fan R. K.","year":"1997","unstructured":"Fan R. K. Chung. 1997. Spectral Graph Theory. Vol. 92. American Mathematical Soc."},{"key":"e_1_3_2_11_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220119"},{"key":"e_1_3_2_12_2","doi-asserted-by":"publisher","DOI":"10.1098\/rsif.2014.1004"},{"key":"e_1_3_2_13_2","doi-asserted-by":"publisher","DOI":"10.1145\/3459637.3482418"},{"key":"e_1_3_2_14_2","doi-asserted-by":"publisher","DOI":"10.1145\/2714576.2714590"},{"key":"e_1_3_2_15_2","doi-asserted-by":"publisher","DOI":"10.5555\/3524938.3525218"},{"key":"e_1_3_2_16_2","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2019.2913233"},{"key":"e_1_3_2_17_2","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0107878"},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-97242-3"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467332"},{"key":"e_1_3_2_20_2","doi-asserted-by":"publisher","DOI":"10.2200\/S01045ED1V01Y202009AIM046"},{"key":"e_1_3_2_21_2","doi-asserted-by":"publisher","DOI":"10.1145\/3269206.3271788"},{"key":"e_1_3_2_22_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-85896-4_4"},{"key":"e_1_3_2_23_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02278710"},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467377"},{"key":"e_1_3_2_25_2","doi-asserted-by":"publisher","DOI":"10.1145\/1386118.1386124"},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.14778\/2794367.2794371"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1186\/1471-2105-10-S1-S59"},{"key":"e_1_3_2_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-02124-4_15"},{"key":"e_1_3_2_29_2","volume-title":"The Graph Isomorphism Problem: Its Structural Complexity","author":"Kobler Johannes","year":"2012","unstructured":"Johannes Kobler, Uwe Sch\u00f6ning, and Jacobo Tor\u00e1n. 2012. The Graph Isomorphism Problem: Its Structural Complexity. Springer Science & Business Media."},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1186\/1756-0500-6-35"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/2743021"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2013.152"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12064"},{"key":"e_1_3_2_34_2","doi-asserted-by":"publisher","DOI":"10.1145\/2487788.2488173"},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1145\/3459637.3482067"},{"key":"e_1_3_2_36_2","article-title":"SNAP Datasets: Stanford Large Network Dataset Collection","author":"Leskovec Jure","year":"2014","unstructured":"Jure Leskovec and Andrej Krevl. 2014. SNAP Datasets: Stanford Large Network Dataset Collection. Retrieved 06 October 2022 from http:\/\/snap.stanford.edu\/data.","journal-title":"http:\/\/snap.stanford.edu\/data"},{"key":"e_1_3_2_37_2","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btp203"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.13123"},{"key":"e_1_3_2_39_2","first-page":"1774","volume-title":"Proceedings of the 25th International Joint Conference on Artificial Intelligence","author":"Liu Li","year":"2016","unstructured":"Li Liu, William K. Cheung, Xin Li, and Lejian Liao. 2016. Aligning users across social networks using network embedding. In Proceedings of the 25th International Joint Conference on Artificial Intelligence. 1774\u20131780."},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132983"},{"key":"e_1_3_2_41_2","first-page":"1823","volume-title":"Proceedings of the 25th International Joint Conference on Artificial Intelligence","author":"Man Tong","year":"2016","unstructured":"Tong Man, Huawei Shen, Shenghua Liu, Xiaolong Jin, and Xueqi Cheng. 2016. Predict anchor links across social networks via an embedding approach. In Proceedings of the 25th International Joint Conference on Artificial Intelligence. IJCAI\/AAAI Press, 1823\u20131829."},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186128"},{"key":"e_1_3_2_43_2","doi-asserted-by":"publisher","DOI":"10.1137\/S003614450342480"},{"key":"e_1_3_2_44_2","doi-asserted-by":"publisher","DOI":"10.1080\/00107510500052444"},{"key":"e_1_3_2_45_2","first-page":"583","volume-title":"Proceedings of the 17th International Conference on Extending Database Technology","author":"Nobari Sadegh","year":"2014","unstructured":"Sadegh Nobari, Panagiotis Karras, HweeHwa Pang, and St\u00e9phane Bressan. 2014. \\(L\\) -opacity: Linkage-aware graph anonymization. In Proceedings of the 17th International Conference on Extending Database Technology. 583\u2013594."},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/2185520.2185526"},{"key":"e_1_3_2_47_2","volume-title":"The PageRank Citation Ranking: Bringing Order to the Web.","author":"Page Lawrence","year":"1999","unstructured":"Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. 1999. The PageRank Citation Ranking: Bringing Order to the Web.Technical Report. Stanford InfoLab."},{"key":"e_1_3_2_48_2","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623732"},{"key":"e_1_3_2_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/3159652.3159706"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1145\/3097983.3098061"},{"key":"e_1_3_2_51_2","volume-title":"Flowers and Insects: Lists of Visitors to Four Hundred and Fifty-Three Flowers","author":"Robertson Charles","year":"1928","unstructured":"Charles Robertson. 1928. Flowers and Insects: Lists of Visitors to Four Hundred and Fifty-Three Flowers. n.p., Carlinville, Ill."},{"key":"e_1_3_2_52_2","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2019.00063"},{"key":"e_1_3_2_53_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289451"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1109\/34.868688"},{"key":"e_1_3_2_55_2","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0806627105"},{"key":"e_1_3_2_56_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3219991"},{"key":"e_1_3_2_57_2","doi-asserted-by":"publisher","DOI":"10.1145\/3178876.3186120"},{"key":"e_1_3_2_58_2","doi-asserted-by":"publisher","DOI":"10.14778\/3447689.3447713"},{"key":"e_1_3_2_59_2","doi-asserted-by":"publisher","DOI":"10.1109\/34.6778"},{"key":"e_1_3_2_60_2","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2017.2740381"},{"key":"e_1_3_2_61_2","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467227"},{"key":"e_1_3_2_62_2","first-page":"3046","volume-title":"Proceedings of the 33rd International Conference on Neural Information Processing Systems","author":"Xu Hongteng","year":"2019","unstructured":"Hongteng Xu, Dixin Luo, and Lawrence Carin. 2019. Scalable Gromov-Wasserstein learning for graph partitioning and matching. In Proceedings of the 33rd International Conference on Neural Information Processing Systems. 3046\u20133056."},{"key":"e_1_3_2_63_2","first-page":"6932","volume-title":"Proceedings of the International Conference on Machine Learning","author":"Xu Hongteng","year":"2019","unstructured":"Hongteng Xu, Dixin Luo, Hongyuan Zha, and Lawrence Carin. 2019. Gromov-Wasserstein learning for graph matching and node embedding. In Proceedings of the International Conference on Machine Learning. 6932\u20136941."},{"key":"e_1_3_2_64_2","doi-asserted-by":"publisher","DOI":"10.1145\/2396761.2396823"},{"key":"e_1_3_2_65_2","doi-asserted-by":"publisher","DOI":"10.1145\/3442381.3450053"},{"key":"e_1_3_2_66_2","doi-asserted-by":"publisher","DOI":"10.1145\/2512938.2512952"},{"key":"e_1_3_2_67_2","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220079"},{"key":"e_1_3_2_68_2","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939766"},{"key":"e_1_3_2_69_2","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467331"},{"key":"e_1_3_2_70_2","doi-asserted-by":"publisher","DOI":"10.1109\/INFOCOM.2018.8486231"},{"key":"e_1_3_2_71_2","doi-asserted-by":"publisher","DOI":"10.1145\/3442381.3449886"},{"key":"e_1_3_2_72_2","doi-asserted-by":"publisher","DOI":"10.1145\/3442381.3449823"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3561058","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3561058","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:15Z","timestamp":1750182555000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3561058"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,2,24]]},"references-count":71,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2023,8,31]]}},"alternative-id":["10.1145\/3561058"],"URL":"https:\/\/doi.org\/10.1145\/3561058","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"value":"1556-4681","type":"print"},{"value":"1556-472X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,2,24]]},"assertion":[{"value":"2021-12-05","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-08-19","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-02-24","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}