{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,1]],"date-time":"2025-10-01T15:16:55Z","timestamp":1759331815353,"version":"3.41.0"},"reference-count":46,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2020,5,30]],"date-time":"2020-05-30T00:00:00Z","timestamp":1590796800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["FA8750-17-C-0153"],"award-info":[{"award-number":["FA8750-17-C-0153"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100007515","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1947135,1715385, 1939725"],"award-info":[{"award-number":["1947135,1715385, 1939725"]}],"id":[{"id":"10.13039\/100007515","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000180","name":"U.S. Department of Homeland Security","doi-asserted-by":"publisher","award":["2017-ST-061-QA0001"],"award-info":[{"award-number":["2017-ST-061-QA0001"]}],"id":[{"id":"10.13039\/100000180","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Knowl. Discov. Data"],"published-print":{"date-parts":[[2020,8,31]]},"abstract":"<jats:p>\n            Networks are prevalent in many areas and are often collected from multiple sources. However, due to the veracity characteristics, more often than not, networks are incomplete. Network alignment and network completion have become two fundamental cornerstones behind a wealth of high-impact graph mining applications. The state-of-the-art have been addressing these two tasks\n            <jats:italic>in parallel<\/jats:italic>\n            . That is, most of the existing network alignment methods have implicitly assumed that the topology of the input networks for alignment are perfectly known a priori, whereas the existing network completion methods admit either a single network (i.e., matrix completion) or multiple aligned networks (e.g., tensor completion). In this article, we argue that network alignment and completion are inherently complementary with each other, and hence propose to jointly address them so that the two tasks can mutually benefit from each other. We formulate the problem from the optimization perspective, and propose an effective algorithm (\n            <jats:sc>iNeAt<\/jats:sc>\n            ) to solve it. The proposed method offers two distinctive advantages. First (\n            <jats:italic>Alignment accuracy<\/jats:italic>\n            ), our method benefits from the higher-quality input networks while mitigates the effect of the incorrectly inferred links introduced by the completion task itself. Second (\n            <jats:italic>Alignment efficiency<\/jats:italic>\n            ), thanks to the low-rank structure of the complete networks and the alignment matrix, the alignment process can be significantly accelerated. We perform extensive experiments which show that (1) the network completion can significantly improve the alignment accuracy, i.e., up to 30% over the baseline methods; (2) the network alignment can in turn help recover more missing edges than the baseline methods; and (3) our method achieves a good balance between the running time and the accuracy, and scales with a provable\n            <jats:italic>linear<\/jats:italic>\n            complexity in both time and space.\n          <\/jats:p>","DOI":"10.1145\/3384203","type":"journal-article","created":{"date-parts":[[2020,5,30]],"date-time":"2020-05-30T12:25:16Z","timestamp":1590841516000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Incomplete Network Alignment"],"prefix":"10.1145","volume":"14","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4509-5173","authenticated-orcid":false,"given":"Si","family":"Zhang","sequence":"first","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL"}]},{"given":"Hanghang","family":"Tong","sequence":"additional","affiliation":[{"name":"University of Illinois at Urbana-Champaign, Urbana, IL"}]},{"given":"Jie","family":"Tang","sequence":"additional","affiliation":[{"name":"Tsinghua University, Beijing, China"}]},{"given":"Jiejun","family":"Xu","sequence":"additional","affiliation":[{"name":"HRL Laboratories, Malibu, CA"}]},{"given":"Wei","family":"Fan","sequence":"additional","affiliation":[{"name":"Tencent Medical AI Lab, Palo Alto, CA"}]}],"member":"320","published-online":{"date-parts":[[2020,5,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2006.44"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623733"},{"key":"e_1_2_1_3_1","volume-title":"Message-passing algorithms for sparse network alignment. ACM Transactions on Knowledge Discovery from Data 7, 1","author":"Bayati Mohsen","year":"2013","unstructured":"Mohsen Bayati , David F. Gleich , Amin Saberi , and Ying Wang . 2013. Message-passing algorithms for sparse network alignment. ACM Transactions on Knowledge Discovery from Data 7, 1 ( 2013 ), 3. Mohsen Bayati, David F. Gleich, Amin Saberi, and Ying Wang. 2013. Message-passing algorithms for sparse network alignment. ACM Transactions on Knowledge Discovery from Data 7, 1 (2013), 3."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0305199101"},{"key":"e_1_2_1_5_1","volume-title":"Proceedings of the Advances in Neural Information Processing Systems. 406--414","author":"Boumal Nicolas","year":"2011","unstructured":"Nicolas Boumal and Pierre-antoine Absil. 2011 . RTRMC: A riemannian trust-region method for low-rank matrix completion . In Proceedings of the Advances in Neural Information Processing Systems. 406--414 . Nicolas Boumal and Pierre-antoine Absil. 2011. RTRMC: A riemannian trust-region method for low-rank matrix completion. In Proceedings of the Advances in Neural Information Processing Systems. 406--414."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.socnet.2007.11.001"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1137\/080738970"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132904"},{"key":"e_1_2_1_9_1","volume-title":"Simon","author":"Ding Chris","year":"2005","unstructured":"Chris Ding , Xiaofeng He , and Horst D . Simon . 2005 . On the equivalence of nonnegative matrix factorization and spectral clustering. In Proceedings of the 2005 SIAM International Conference on Data Mining. SIAM , 606--610. Chris Ding, Xiaofeng He, and Horst D. Simon. 2005. On the equivalence of nonnegative matrix factorization and spectral clustering. In Proceedings of the 2005 SIAM International Conference on Data Mining. SIAM, 606--610."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3219819.3220002"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357384.3357944"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.3390\/a8041035"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btu450"},{"key":"e_1_2_1_14_1","volume-title":"Node representation learning for multiple networks: The case of graph alignment. Arxiv Preprint Arxiv:1802.06257","author":"Heimann Mark","year":"2018","unstructured":"Mark Heimann , Haoming Shen , and Danai Koutra . 2018. Node representation learning for multiple networks: The case of graph alignment. Arxiv Preprint Arxiv:1802.06257 ( 2018 ). Mark Heimann, Haoming Shen, and Danai Koutra. 2018. Node representation learning for multiple networks: The case of graph alignment. Arxiv Preprint Arxiv:1802.06257 (2018)."},{"volume-title":"Proceedings of the 22nd ACM International Conference on Information 8 Knowledge Management. ACM, 179--188","author":"Kong Xiangnan","key":"e_1_2_1_15_1","unstructured":"Xiangnan Kong , Jiawei Zhang , and Philip S. Yu . 2013. Inferring anchor links across multiple heterogeneous social networks . In Proceedings of the 22nd ACM International Conference on Information 8 Knowledge Management. ACM, 179--188 . Xiangnan Kong, Jiawei Zhang, and Philip S. Yu. 2013. Inferring anchor links across multiple heterogeneous social networks. In Proceedings of the 22nd ACM International Conference on Information 8 Knowledge Management. ACM, 179--188."},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDM.2013.152"},{"key":"e_1_2_1_17_1","first-page":"985","article-title":"Kronecker graphs: An approach to modeling networks","author":"Leskovec Jure","year":"2010","unstructured":"Jure Leskovec , Deepayan Chakrabarti , Jon Kleinberg , Christos Faloutsos , and Zoubin Ghahramani . 2010 . Kronecker graphs: An approach to modeling networks . Journal of Machine Learning Research 11 , Feb (2010), 985 -- 1042 . Jure Leskovec, Deepayan Chakrabarti, Jon Kleinberg, Christos Faloutsos, and Zoubin Ghahramani. 2010. Kronecker graphs: An approach to modeling networks. Journal of Machine Learning Research 11, Feb (2010), 985--1042.","journal-title":"Journal of Machine Learning Research 11"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1217299.1217301"},{"key":"e_1_2_1_19_1","volume-title":"Mcauley","author":"Leskovec Jure","year":"2012","unstructured":"Jure Leskovec and Julian J . Mcauley . 2012 . Learning to discover social circles in ego networks. In Proceedings of the Advances in Neural Information Processing Systems . 539--547. Jure Leskovec and Julian J. Mcauley. 2012. Learning to discover social circles in ego networks. In Proceedings of the Advances in Neural Information Processing Systems. 539--547."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btp203"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.5555\/1241540.1241551"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2012.39"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the 25th International Joint Conference on Artificial Intelligence. 1774--1780","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--1780 . 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--1780."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973440.99"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btv130"},{"volume-title":"Proceedings of the 2017 IEEE International Conference on Bioinformatics and Biomedicine (BIBM\u201917)","author":"Manners Hazel N.","key":"e_1_2_1_26_1","unstructured":"Hazel N. Manners , Ahed Elmsallati , Pietro H. Guzzi , Swarup Roy , and Jugal K. Kalita . 2017. Performing local network alignment by ensembling global aligners . In Proceedings of the 2017 IEEE International Conference on Bioinformatics and Biomedicine (BIBM\u201917) . IEEE, 1316--1323. Hazel N. Manners, Ahed Elmsallati, Pietro H. Guzzi, Swarup Roy, and Jugal K. Kalita. 2017. Performing local network alignment by ensembling global aligners. In Proceedings of the 2017 IEEE International Conference on Bioinformatics and Biomedicine (BIBM\u201917). IEEE, 1316--1323."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/2808797.2809407"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-23783-6_28"},{"key":"e_1_2_1_29_1","volume-title":"Griffiths","author":"Miller Kurt","year":"2009","unstructured":"Kurt Miller , Michael I. Jordan , and Thomas L . Griffiths . 2009 . Nonparametric latent feature models for link prediction. In Proceedings of the Advances in Neural Information Processing Systems . 1276--1284. Kurt Miller, Michael I. Jordan, and Thomas L. Griffiths. 2009. Nonparametric latent feature models for link prediction. In Proceedings of the Advances in Neural Information Processing Systems. 1276--1284."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCBB.2014.2318707"},{"key":"e_1_2_1_31_1","volume-title":"The matrix cookbook, vol 7","author":"Petersen K. B.","year":"2008","unstructured":"K. B. Petersen , M. S. Pedersen , and others. 2008. The matrix cookbook, vol 7 . Technical University of Denmark 15 ( 2008 ). K. B. Petersen, M. S. Pedersen, and others. 2008. The matrix cookbook, vol 7. Technical University of Denmark 15 (2008)."},{"key":"e_1_2_1_32_1","first-page":"3413","article-title":"A simpler approach to matrix completion","author":"Recht Benjamin","year":"2011","unstructured":"Benjamin Recht . 2011 . A simpler approach to matrix completion . Journal of Machine Learning Research 12 , Dec (2011), 3413 -- 3430 . Benjamin Recht. 2011. A simpler approach to matrix completion. Journal of Machine Learning Research 12, Dec (2011), 3413--3430.","journal-title":"Journal of Machine Learning Research 12"},{"volume-title":"Proceedings of the 22nd International Conference on Machine Learning. ACM, 713--719","author":"Jasson D.","key":"e_1_2_1_33_1","unstructured":"Jasson D. M. Rennie and Nathan Srebro. 2005. Fast maximum margin matrix factorization for collaborative prediction . In Proceedings of the 22nd International Conference on Machine Learning. ACM, 713--719 . Jasson D. M. Rennie and Nathan Srebro. 2005. Fast maximum margin matrix factorization for collaborative prediction. In Proceedings of the 22nd International Conference on Machine Learning. ACM, 713--719."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0806627105"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/ASONAM.2016.7752227"},{"key":"e_1_2_1_36_1","first-page":"615","article-title":"An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems","volume":"6","author":"Toh Kim-Chuan","year":"2010","unstructured":"Kim-Chuan Toh and Sangwoon Yun . 2010 . An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems . Pacific Journal of Optimization 6 , 615 \u2013 640 (2010), 15. Kim-Chuan Toh and Sangwoon Yun. 2010. An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems. Pacific Journal of Optimization 6, 615\u2013640 (2010), 15.","journal-title":"Pacific Journal of Optimization"},{"key":"e_1_2_1_37_1","unstructured":"Rianne van den Berg Thomas N. Kipf and Max Welling. 2017. Graph convolutional matrix completion. arXiv preprint arXiv:1706.02263.  Rianne van den Berg Thomas N. Kipf and Max Welling. 2017. Graph convolutional matrix completion. arXiv preprint arXiv:1706.02263."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1093\/bioinformatics\/btv161"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10115-013-0693-z"},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2487575.2487648"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2017.144"},{"volume-title":"Proceedings of the 2015 IEEE International Conference onData Mining (ICDM\u201915)","author":"Zhang Jiawei","key":"e_1_2_1_42_1","unstructured":"Jiawei Zhang and S. Yu Philip . 2015. Multiple anonymized social networks alignment . In Proceedings of the 2015 IEEE International Conference onData Mining (ICDM\u201915) . IEEE, 599--608. Jiawei Zhang and S. Yu Philip. 2015. Multiple anonymized social networks alignment. In Proceedings of the 2015 IEEE International Conference onData Mining (ICDM\u201915). IEEE, 599--608."},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2939672.2939766"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2018.2866440"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1109\/BigData47090.2019.9005663"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2783258.2783268"}],"container-title":["ACM Transactions on Knowledge Discovery from Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3384203","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3384203","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3384203","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T22:03:23Z","timestamp":1750197803000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3384203"}},"subtitle":["Problem Definitions and Fast Solutions"],"short-title":[],"issued":{"date-parts":[[2020,5,30]]},"references-count":46,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2020,8,31]]}},"alternative-id":["10.1145\/3384203"],"URL":"https:\/\/doi.org\/10.1145\/3384203","relation":{},"ISSN":["1556-4681","1556-472X"],"issn-type":[{"type":"print","value":"1556-4681"},{"type":"electronic","value":"1556-472X"}],"subject":[],"published":{"date-parts":[[2020,5,30]]},"assertion":[{"value":"2018-05-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-05-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}