{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T06:05:01Z","timestamp":1784268301812,"version":"3.55.0"},"reference-count":81,"publisher":"Institute of Electrical and Electronics Engineers (IEEE)","issue":"8","license":[{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/ieeexplore.ieee.org\/Xplorehelp\/downloads\/license-information\/IEEE.html"},{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-029"},{"start":{"date-parts":[[2026,8,1]],"date-time":"2026-08-01T00:00:00Z","timestamp":1785542400000},"content-version":"stm-asf","delay-in-days":0,"URL":"https:\/\/doi.org\/10.15223\/policy-037"}],"funder":[{"name":"National Key Research and Development Program of China","award":["2023YFA1010102"],"award-info":[{"award-number":["2023YFA1010102"]}]},{"DOI":"10.13039\/501100001809","name":"NSFC Key Program","doi-asserted-by":"publisher","award":["12231002"],"award-info":[{"award-number":["12231002"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEEE Trans. Inform. Theory"],"published-print":{"date-parts":[[2026,8]]},"DOI":"10.1109\/tit.2026.3702566","type":"journal-article","created":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T20:01:32Z","timestamp":1781121692000},"page":"6093-6111","source":"Crossref","is-referenced-by-count":0,"title":["Robust Random Graph Matching in Dense Graphs via an Approximate Message Passing Type Algorithm"],"prefix":"10.1109","volume":"72","author":[{"ORCID":"https:\/\/orcid.org\/0009-0000-7182-8639","authenticated-orcid":false,"given":"Zhangsong","family":"Li","sequence":"first","affiliation":[{"name":"School of Mathematical Science, Peking University, Beijing, China"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"263","reference":[{"key":"ref1","first-page":"1276","article-title":"Robust graph matching when nodes are corrupt","volume-title":"Proc. 41st Int. Conf. Mach. Learn. (ICML)","author":"Ameen"},{"key":"ref2","first-page":"684","article-title":"Graph isomorphism in quasi-polynomial time","volume-title":"Proc. 48th Annu. ACM Symp. Theory Comput. (STOC)","author":"Babai"},{"key":"ref3","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451001"},{"key":"ref4","first-page":"9190","article-title":"(Nearly) efficient algorithms for the graph matching problem on correlated random graphs","volume-title":"Proc. Adv. Neural Inf. Process. Syst. (NeurIPS)","volume":"32","author":"Barak"},{"key":"ref5","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2010.2094817"},{"key":"ref6","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2005.320"},{"key":"ref7","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-013-1862-3"},{"key":"ref8","first-page":"1787","article-title":"Gardner formula for Ising perceptron models at small densities","volume-title":"Proc. Conf. Learn. Theory","author":"Bolthausen"},{"key":"ref9","article-title":"Seedless graph matching via tail of degree distribution for correlated Erdos-Renyi graphs","author":"Bozorg","year":"2019","journal-title":"arXiv:1907.06334"},{"key":"ref10","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4613-0303-9_27"},{"key":"ref11","doi-asserted-by":"publisher","DOI":"10.52202\/079017-3696"},{"key":"ref12","doi-asserted-by":"publisher","DOI":"10.1214\/25-AOS2565"},{"key":"ref13","article-title":"Detecting correlation efficiently in stochastic block models: Breaking Otter\u2019s threshold in the entire supercritical regime","author":"Chen","year":"2025","journal-title":"arXiv:2503.06464"},{"key":"ref14","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978971.101"},{"key":"ref15","article-title":"Orthogonal approximate message passing with optimal spectral initializations for rectangular spiked matrix models","author":"Chen","year":"2025","journal-title":"arXiv:2512.19334"},{"key":"ref16","doi-asserted-by":"publisher","DOI":"10.7551\/mitpress\/7503.003.0044"},{"key":"ref17","article-title":"Exact alignment recovery for correlated Erd\u0151s-R\u00e9nyi graphs","author":"Cullina","year":"2017","journal-title":"arXiv:1711.06783"},{"key":"ref18","doi-asserted-by":"publisher","DOI":"10.1145\/2896377.2901460"},{"key":"ref19","doi-asserted-by":"publisher","DOI":"10.1145\/3393691.3394211"},{"key":"ref20","doi-asserted-by":"publisher","DOI":"10.1109\/ISIT.2014.6875223"},{"key":"ref21","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2023.3265009"},{"key":"ref22","doi-asserted-by":"publisher","DOI":"10.1214\/23-AOS2305"},{"key":"ref23","doi-asserted-by":"publisher","DOI":"10.1214\/25-AOS2517"},{"key":"ref24","doi-asserted-by":"publisher","DOI":"10.1214\/25-AOS2545"},{"key":"ref25","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-024-09662-x"},{"key":"ref26","doi-asserted-by":"publisher","DOI":"10.1287\/moor.2024.0487"},{"key":"ref27","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-020-00997-4"},{"key":"ref28","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00046"},{"key":"ref29","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-025-01364-x"},{"key":"ref30","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0909892106"},{"key":"ref31","article-title":"Optimal recovery of correlated Erd\u0151s-R\u00e9nyi graphs","author":"Du","year":"2025","journal-title":"arXiv:2502.12077"},{"key":"ref32","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511581274"},{"key":"ref33","doi-asserted-by":"publisher","DOI":"10.52202\/079017-2260"},{"key":"ref34","article-title":"TAP equations for orthogonally invariant spin glasses at high temperature","author":"Fan","year":"2022","journal-title":"arXiv:2202.09325"},{"key":"ref35","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-022-09570-y"},{"key":"ref36","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-022-09575-7"},{"key":"ref37","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-024-01309-w"},{"key":"ref38","doi-asserted-by":"publisher","DOI":"10.1561\/2200000092"},{"key":"ref39","first-page":"1633","article-title":"From tree matching to sparse graph alignment","volume-title":"Proc. 33rd Conf. Learn. Theory (COLT)","author":"Ganassali"},{"key":"ref40","first-page":"2080","article-title":"Impossibility of partial recovery in the graph alignment problem","volume-title":"Proc. 34th Conf. Learn. Theory (COLT)","author":"Ganassali"},{"key":"ref41","doi-asserted-by":"publisher","DOI":"10.1214\/23-AAP2020"},{"key":"ref42","doi-asserted-by":"publisher","DOI":"10.1214\/23-AAP2048"},{"key":"ref43","article-title":"The umeyama algorithm for matching correlated Gaussian geometric models in the low-dimensional regime","author":"Gong","year":"2024","journal-title":"arXiv:2402.15095"},{"key":"ref44","doi-asserted-by":"publisher","DOI":"10.3115\/1220575.1220624"},{"key":"ref45","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2022.2355"},{"key":"ref46","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188748"},{"key":"ref47","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649713"},{"key":"ref48","doi-asserted-by":"publisher","DOI":"10.1145\/3717823.3718165"},{"key":"ref49","doi-asserted-by":"publisher","DOI":"10.14778\/2794367.2794371"},{"key":"ref50","volume-title":"Probabilistic Graphical Models: Principles and Techniques","author":"Koller","year":"2009"},{"key":"ref51","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188970"},{"key":"ref52","doi-asserted-by":"publisher","DOI":"10.1088\/1742-5468\/2012\/08\/P08009"},{"key":"ref53","doi-asserted-by":"publisher","DOI":"10.1002\/nav.3800020109"},{"key":"ref54","article-title":"Algorithmic contiguity from low-degree conjecture and applications in correlated random graphs","volume":"353","author":"Li","year":"2025","journal-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX\/RANDOM)"},{"key":"ref55","article-title":"Unifying AMP algorithms for rotationally-invariant models","author":"Liu","year":"2024","journal-title":"arXiv:2412.05714"},{"key":"ref56","first-page":"3513","article-title":"Seeded graph matching for correlated Erd\u0151s-R\u00e9nyi graphs","volume":"15","author":"Lyzinski","year":"2014","journal-title":"J. Mach. Learn. Res."},{"key":"ref57","doi-asserted-by":"publisher","DOI":"10.1109\/ACCESS.2017.2653119"},{"key":"ref58","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14165-2_50"},{"key":"ref59","first-page":"3296","article-title":"Random graph matching with improved noise robustness","volume-title":"Proc. 34th Conf. Learn. Theory (COLT)","author":"Mao"},{"key":"ref60","doi-asserted-by":"publisher","DOI":"10.1007\/s00440-022-01184-3"},{"key":"ref61","doi-asserted-by":"publisher","DOI":"10.1214\/23-AOS2261"},{"key":"ref62","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585156"},{"key":"ref63","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649761"},{"key":"ref64","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511794308.010"},{"key":"ref65","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2015.2457942"},{"key":"ref66","doi-asserted-by":"publisher","DOI":"10.1145\/2897518.2897548"},{"key":"ref67","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20934"},{"key":"ref68","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2008.33"},{"key":"ref69","doi-asserted-by":"publisher","DOI":"10.1109\/SP.2009.22"},{"key":"ref70","doi-asserted-by":"publisher","DOI":"10.1145\/2020408.2020596"},{"key":"ref71","first-page":"22259","article-title":"Correlated stochastic block models: Exact graph matching with applications to recovering communities","volume-title":"Proc. Adv. Neural Inf. Process. Syst. (NeurIPS)","volume":"34","author":"Racz"},{"key":"ref72","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2019.2916359"},{"key":"ref73","doi-asserted-by":"publisher","DOI":"10.1109\/ACSSC.2017.8335178"},{"key":"ref74","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0806627105"},{"key":"ref75","doi-asserted-by":"publisher","DOI":"10.1080\/14786437708235992"},{"key":"ref76","doi-asserted-by":"publisher","DOI":"10.1017\/9781108231596"},{"key":"ref77","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pone.0121002"},{"key":"ref78","first-page":"3441","article-title":"Random graph matching in geometric models: The case of complete graphs","volume-title":"Proc. 35th Conf. Learn. Theory (COLT)","author":"Wang"},{"key":"ref79","doi-asserted-by":"publisher","DOI":"10.1214\/22-AAP1786"},{"key":"ref80","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2022.3169005"},{"key":"ref81","doi-asserted-by":"publisher","DOI":"10.1145\/2512938.2512952"}],"container-title":["IEEE Transactions on Information Theory"],"original-title":[],"link":[{"URL":"http:\/\/xplorestaging.ieee.org\/ielx8\/18\/11611849\/11557367.pdf?arnumber=11557367","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,7,17]],"date-time":"2026-07-17T05:16:19Z","timestamp":1784265379000},"score":1,"resource":{"primary":{"URL":"https:\/\/ieeexplore.ieee.org\/document\/11557367\/"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,8]]},"references-count":81,"journal-issue":{"issue":"8"},"URL":"https:\/\/doi.org\/10.1109\/tit.2026.3702566","relation":{},"ISSN":["0018-9448","1557-9654"],"issn-type":[{"value":"0018-9448","type":"print"},{"value":"1557-9654","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026,8]]}}}