{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:10:14Z","timestamp":1785543014705,"version":"3.56.0"},"reference-count":62,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T00:00:00Z","timestamp":1727654400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100006374","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["62192731, 62192730, 61690200"],"award-info":[{"award-number":["62192731, 62192730, 61690200"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2024,10,1]]},"abstract":"<jats:p>\n                    Heterogeneous graphs provide a universal data structure for representing various kinds of structured data in numerous domains. The\n                    <jats:italic toggle=\"yes\">graph alignment<\/jats:italic>\n                    problem aims to find the correspondences of vertices in different graphs, playing a fundamental role in many downstream tasks of heterogeneous graph mining. In recent years, many graph alignment methods have been proposed, ranging from\n                    <jats:italic toggle=\"yes\">classical optimization methods<\/jats:italic>\n                    ,\n                    <jats:italic toggle=\"yes\">spectral methods<\/jats:italic>\n                    , to\n                    <jats:italic toggle=\"yes\">embedding learning based-methods<\/jats:italic>\n                    . Due to the problem's complexity, the result found by most existing methods is either a\n                    <jats:italic toggle=\"yes\">heuristic solution<\/jats:italic>\n                    or a\n                    <jats:italic toggle=\"yes\">critical point<\/jats:italic>\n                    in the solution space. In this paper, we propose GABoost, a graph alignment boosting algorithm that takes as input an initial alignment between two heterogeneous graphs and outputs a boosted alignment via an iterative\n                    <jats:italic toggle=\"yes\">local-optimum-escape<\/jats:italic>\n                    process. One of the distinctive features of GABoost is that it can be sequentially composed with any graph alignment methods to improve the output of upstream methods. To examine the effectiveness of GABoost, we select 7 upstream methods of graph alignment as well as 6 real-world datasets, and quantitatively investigate the degree to which GABoost boosts these methods. The results show that GABoost improves the alignment accuracy of the 7 upstream methods by 25.25% on average with acceptable time overhead.\n                  <\/jats:p>","DOI":"10.1145\/3677135","type":"journal-article","created":{"date-parts":[[2024,9,30]],"date-time":"2024-09-30T17:41:44Z","timestamp":1727718104000},"page":"1-26","source":"Crossref","is-referenced-by-count":2,"title":["GABoost: Graph Alignment Boosting via Local Optimum Escape"],"prefix":"10.1145","volume":"2","author":[{"ORCID":"https:\/\/orcid.org\/0009-0005-4603-4227","authenticated-orcid":false,"given":"Wei","family":"Liu","sequence":"first","affiliation":[{"name":"Key Laboratory of High Confidence Software Technologies (Peking University), MoE &amp; School of Computer Science, Peking University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1543-0196","authenticated-orcid":false,"given":"Wei","family":"Zhang","sequence":"additional","affiliation":[{"name":"Key Laboratory of High Confidence Software Technologies (Peking University), MoE &amp; School of Computer Science, Peking University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3600-8923","authenticated-orcid":false,"given":"Haiyan","family":"Zhao","sequence":"additional","affiliation":[{"name":"Key Laboratory of High Confidence Software Technologies (Peking University), MoE &amp; School of Computer Science, Peking University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1087-226X","authenticated-orcid":false,"given":"Zhi","family":"Jin","sequence":"additional","affiliation":[{"name":"Key Laboratory of High Confidence Software Technologies (Peking University), MoE &amp; School of Computer Science, Peking University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,9,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btt713"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-2836(05)80360-2"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2009.135"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800260111"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1057\/jors.1982.210"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipm.2021.102790"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3340531.3412136"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/TAES.2016.140952"},{"key":"e_1_2_1_9_1","volume-title":"Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems","author":"Cuturi Marco","year":"2013","unstructured":"Marco Cuturi. 2013. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems, Vol. 26 (2013)."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-006-6993-y"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICME.2013.6607513"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2012.140"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3534678.3539080"},{"key":"e_1_2_1_14_1","unstructured":"Paul ErdHos Alfr\u00e9d R\u00e9nyi et al. 1960. On the evolution of random graphs. Publ. math. inst. hung. acad. sci Vol. 5 1 (1960) 17--60."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/TNSE.2019.2913233"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467332"},{"key":"e_1_2_1_17_1","volume-title":"Network Alignment with Transferable Graph Autoencoders. arXiv preprint arXiv:2310.03272","author":"He Jiashu","year":"2024","unstructured":"Jiashu He, Charilaos I Kanatsoulis, and Alejandro Ribeiro. 2024. Network Alignment with Transferable Graph Autoencoders. arXiv preprint arXiv:2310.03272 (2024)."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3269206.3271788"},{"key":"e_1_2_1_19_1","volume-title":"Simon Daugaard Nielsen, Alex Bronstein, Davide Mottin, and Panagiotis Karras.","author":"Hermanns Judith","year":"2022","unstructured":"Judith Hermanns, Konstantinos Skitsas, Anton Tsitsulin, Marina Munkhoeva, Alexander Frederiksen Kyster, Simon Daugaard Nielsen, Alex Bronstein, Davide Mottin, and Panagiotis Karras. 2022. GRASP: Scalable Graph Alignment by Spectral Corresponding Functions. ACM Transactions on Knowledge Discovery from Data (TKDD) (2022)."},{"key":"e_1_2_1_20_1","volume-title":"Tam Thanh Nguyen, Vinh Van Tong, Abdul Sattar, Hongzhi Yin, and Quoc Viet Hung Nguyen.","author":"Huynh Thanh Trung","year":"2021","unstructured":"Thanh Trung Huynh, Chi Thang Duong, Tam Thanh Nguyen, Vinh Van Tong, Abdul Sattar, Hongzhi Yin, and Quoc Viet Hung Nguyen. 2021. Network alignment with holistic embeddings. IEEE Transactions on Knowledge and Data Engineering (2021)."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE53745.2022.00131"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3447548.3467377"},{"key":"e_1_2_1_23_1","volume-title":"A new graph-based method for pairwise global network alignment. BMC bioinformatics","author":"Klau Gunnar W","year":"2009","unstructured":"Gunnar W Klau. 2009. A new graph-based method for pairwise global network alignment. BMC bioinformatics, Vol. 10, 1 (2009), 1--9."},{"key":"e_1_2_1_24_1","volume-title":"The Hungarian method for the assignment problem. Naval research logistics quarterly","author":"Kuhn Harold W","year":"1955","unstructured":"Harold W Kuhn. 1955. The Hungarian method for the assignment problem. Naval research logistics quarterly, Vol. 2, 1--2 (1955), 83--97."},{"key":"e_1_2_1_25_1","volume-title":"Learning to discover social circles in ego networks. Advances in neural information processing systems","author":"Leskovec Jure","year":"2012","unstructured":"Jure Leskovec and Julian Mcauley. 2012. Learning to discover social circles in ego networks. Advances in neural information processing systems, Vol. 25 (2012)."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btp203"},{"key":"e_1_2_1_27_1","first-page":"1","article-title":"On the efficiency of entropic regularized algorithms for optimal transport","volume":"23","author":"Lin Tianyi","year":"2022","unstructured":"Tianyi Lin, Nhat Ho, and Michael I Jordan. 2022. On the efficiency of entropic regularized algorithms for optimal transport. Journal of Machine Learning Research, Vol. 23, 137 (2022), 1--42.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10618-020-00733-5"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.24963\/ijcai.2017\/99"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2021.3086689"},{"key":"e_1_2_1_31_1","volume-title":"Megadiff: A Dataset of 600k Java Source Code Changes Categorized by Diff Size. arXiv preprint arXiv:2108.04631","author":"Monperrus Martin","year":"2021","unstructured":"Martin Monperrus, Matias Martinez, He Ye, Fernanda Madeiral, Thomas Durieux, and Zhongxing Yu. 2021. Megadiff: A Dataset of 600k Java Source Code Changes Categorized by Diff Size. arXiv preprint arXiv:2108.04631 (2021)."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/s12532-010-0012-6"},{"key":"e_1_2_1_33_1","volume-title":"Ahmed","author":"Rossi Ryan A.","year":"2015","unstructured":"Ryan A. Rossi and Nesreen K. Ahmed. 2015. The Network Data Repository with Interactive Graph Analytics and Visualization. In AAAI. https:\/\/networkrepository.com"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.1998.710701"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1515\/9781400841059"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btu409"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3360596"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/3068777.3068781"},{"key":"e_1_2_1_39_1","volume-title":"Multilingual Knowledge Graph Completion With Joint Relation and Entity Alignment. In 3rd Conference on Automated Knowledge Base Construction.","author":"Singh Harkanwar","year":"2021","unstructured":"Harkanwar Singh, Soumen Chakrabarti, PRACHI JAIN, Sharod Roy Choudhury, et al. 2021. Multilingual Knowledge Graph Completion With Joint Relation and Entity Alignment. In 3rd Conference on Automated Knowledge Base Construction."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-71681-5_2"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.2307\/2314570"},{"key":"e_1_2_1_42_1","unstructured":"Konstantinos Skitsas Karol Orlowski Judith Hermanns Davide Mottin and Panagiotis Karras. 2023. Comprehensive evaluation of algorithms for unrestricted graph alignment. In EDBT. 260--272."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-2836(81)90087-5"},{"key":"e_1_2_1_44_1","volume-title":"Multi-view heterogeneous molecular network representation learning for protein--protein interaction prediction. BMC bioinformatics","author":"Su Xiao-Rui","year":"2022","unstructured":"Xiao-Rui Su, Lun Hu, Zhu-Hong You, Peng-Wei Hu, and Bo-Wei Zhao. 2022. Multi-view heterogeneous molecular network representation learning for protein--protein interaction prediction. BMC bioinformatics, Vol. 23, 1 (2022), 1--15."},{"key":"e_1_2_1_45_1","volume-title":"Towards Higher-order Topological Consistency for Unsupervised Network Alignment. 2023 IEEE 39th International Conference on Data Engineering (ICDE)","author":"Sun Qingqiang","year":"2023","unstructured":"Qingqiang Sun, Xuemin Lin, Ying Zhang, Wenjie Zhang, and Chaoqi Chen. 2023. Towards Higher-order Topological Consistency for Unsupervised Network Alignment. 2023 IEEE 39th International Conference on Data Engineering (ICDE) (2023)."},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE55515.2023.00129"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2023.3270119"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3539618.3591735"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE48307.2020.00015"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.6778"},{"key":"e_1_2_1_51_1","volume-title":"GTCAlign: Global Topology Consistency-based Graph Alignment","author":"Wang Chenxu","year":"2023","unstructured":"Chenxu Wang, Peijing Jiang, Xiangliang Zhang, Pinghui Wang, Tao Qin, and Xiaohong Guan. 2023. GTCAlign: Global Topology Consistency-based Graph Alignment. IEEE Transactions on Knowledge and Data Engineering (2023)."},{"key":"e_1_2_1_52_1","doi-asserted-by":"crossref","unstructured":"Hongwei Wang Miao Zhao Xing Xie Wenjie Li and Minyi Guo. 2019. Knowledge graph convolutional networks for recommender systems. In The world wide web conference. 3307--3313.","DOI":"10.1145\/3308558.3313417"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2024.3351107"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/3494523"},{"key":"e_1_2_1_55_1","volume-title":"Scalable Gromov-Wasserstein learning for graph partitioning and matching. Advances in 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. Advances in neural information processing systems, Vol. 32 (2019)."},{"key":"e_1_2_1_56_1","volume-title":"International conference on machine learning. PMLR, 6932--6941","author":"Xu Hongteng","year":"2019","unstructured":"Hongteng Xu, Dixin Luo, Hongyuan Zha, and Lawrence Carin Duke. 2019. Gromov-wasserstein learning for graph matching and node embedding. In International conference on machine learning. PMLR, 6932--6941."},{"key":"e_1_2_1_57_1","volume-title":"Distributional Learning for Network Alignment with Global Constraints. ACM Transactions on Knowledge Discovery from Data","author":"Xu Hui","year":"2024","unstructured":"Hui Xu, Liyao Xiang, Xiaoying Gan, Luoyi Fu, Xinbing Wang, and Chenghu Zhou. 2024. Distributional Learning for Network Alignment with Global Constraints. ACM Transactions on Knowledge Discovery from Data, Vol. 18, 4 (2024), 1--16."},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2014.44"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-59416-9_26"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939766"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2866440"},{"key":"e_1_2_1_62_1","volume-title":"Fusing multiple protein-protein similarity networks to effectively predict lncRNA-protein interactions. BMC bioinformatics","author":"Zheng Xiaoxiong","year":"2017","unstructured":"Xiaoxiong Zheng, Yang Wang, Kai Tian, Jiaogen Zhou, Jihong Guan, Libo Luo, and Shuigeng Zhou. 2017. Fusing multiple protein-protein similarity networks to effectively predict lncRNA-protein interactions. BMC bioinformatics, Vol. 18, 12 (2017), 11--18."}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3677135","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3677135","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T17:10:30Z","timestamp":1774977030000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3677135"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,9,30]]},"references-count":62,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2024,10,1]]}},"alternative-id":["10.1145\/3677135"],"URL":"https:\/\/doi.org\/10.1145\/3677135","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2024,9,30]]}}}