A Polynomial-Time Iterative Algorithm for Random Graph Matching with Nonvanishing Correlation

References

• [1] Barak B, Chou CN, Lei Z, Schramm T, Sheng Y (2019) (Nearly) efficient algorithms for the graph matching problem on correlated random graphs. Wallach H, Larochelle H, Beygelzimer A, Alche-Buc F, Fox E, Garnett R, eds. Adv. Neural Inform. Processing Systems (NIPS), vol. 32 (Curran Associates, Vancouver, Canada), 9190–9198.Google Scholar
• [2] Bayati M, Montanari A (2011) The dynamics of message passing on dense graphs, with applications to compressed sensing. IEEE Trans. Inform. Theory 57(2):764–785.Crossref, Google Scholar
• [3] Bayati M, Lelarge M, Montanari A (2015) Universality in polytope phase transitions and message passing algorithms. Ann. Appl. Probab. 25(2):753–822.Crossref, Google Scholar
• [4] Berg AC, Berg TL, Malik J (2005) Shape matching and object recognition using low distortion correspondences. Schmid C, Soatto S, Tomasi C, eds. IEEE Comput. Soc. Conf. Comput. Vision Pattern Recognition (CVPR), vol. 1 (IEEE, Piscataway, NJ), 26–33.Google Scholar
• [5] Bozorg M, Salehkaleybar S, Hashemi M (2019) Seedless graph matching via tail of degree distribution for correlated Erdős–Rényi graphs. Preprint, submitted July 15, https://arxiv.org/abs/1907.06334.Google Scholar
• [6] Chen W-K, Lam W-K (2021) Universality of approximate message passing algorithms. Electronic J. Probab. 26:1–44.Crossref, Google Scholar
• [7] Chen S, Jiang S, Ma Z, Nolan GP, Zhu B (2022) One-way matching of datasets with low rank signals. Preprint, submitted April 29, https://arxiv.org/abs/2204.13858.Google Scholar
• [8] Cour T, Srinivasan P, Shi J (2006) Balanced graph matching. Scholkopf B, Platt J, Hofmann T, eds. Adv. Neural Inform. Processing Systems (NIPS), vol. 19 (MIT Press, Cambridge, MA).Google Scholar
• [9] Cullina D, Kiyavash N (2016) Improved achievability and converse bounds for Erdős–Rényi graph matching. Alouf S, Jean-Marie A, eds. Proc. ACM SIGMETRICS Internat. Conf. Measurement Model. Comput. Sci. (ACM, New York), 63–72.Google Scholar
• [10] Cullina D, Kiyavash N (2017) Exact alignment recovery for correlated Erdős–Rényi graphs. Preprint, submitted November 18, https://arxiv.org/abs/1711.06783.Google Scholar
• [11] Cullina D, Kiyavash N, Mittal P, Poor HV (2020) Partial recovery of Erdős–Rényi graph alignment via k-core alignment. Yeh E, ed. SIGMETRICS ‘20 Abstracts 2020 SIGMETRICS/Performance Joint Internat. Conf. Measurement Model. Comput. Systems (ACM, New York), 99–100.Google Scholar
• [12] Dai OE, Cullina D, Kiyavash N, Grossglauser M (2019) Analysis of a canonical labeling algorithm for the alignment of correlated Erdős–Rényi graphs. Proc. ACM Measurement and Anal. Comput. Systems 3(2):1–25.Google Scholar
• [13] Ding J, Du H (2023) Detection threshold for correlated Erdős–Rényi graphs via densest subgraph. IEEE Trans. Inform. Theory 69(8):5289–5298.Crossref, Google Scholar
• [14] Ding J, Du H (2023) Matching recovery threshold for correlated random graphs. Ann. Statist. 51(4):1718–1743.Crossref, Google Scholar
• [15] Ding J, Li Z (2025) A polynomial time iterative algorithm for matching Gaussian matrices with non-vanishing correlation. Foundations Computational Math. 25(5):1287–1344.Crossref, Google Scholar
• [16] Ding J, Du H, Gong S (2024) A polynomial-time approximation scheme for the maximal overlap of two independent Erdős–Rényi graphs. Random Structures Algorithms 65(1):220–257.Crossref, Google Scholar
• [17] Ding J, Du H, Li Z (2025) Low-degree hardness of detection for correlated Erdős–Rényi graphs. Ann. Statist. 53(5):1833–1856.Crossref, Google Scholar
• [18] Ding J, Ma Z, Wu Y, Xu J (2021) Efficient random graph matching via degree profiles. Probab. Theory Related Fields 179(1–2):29–115.Crossref, Google Scholar
• [19] Dudeja R, Lu YM, Sen S (2023) Universality of approximate message passing with semirandom matrices. Ann. Probab. 51(5):1616–1683. Crossref, Google Scholar
• [20] Elmsallati A, Clark C, Kalita J (2016) Global alignment of protein-protein interaction networks: A survey. IEEE/ACM Trans. Comput. Biol. Bioinformics 13(4):689–705.Crossref, Google Scholar
• [21] Fan Z, Wang T, Zhong X (2024) Universality of approximate message passing algorithms and tensor networks. Ann. Appl. Probab. 34(4):3943–3994.Google Scholar
• [22] Fan Z, Mao C, Wu Y, Xu J (2023) Spectral graph matching and regularized quadratic relaxations I: Algorithm and Gaussian analysis. Foundations Computational Math. 23(5):1511–1565.Crossref, Google Scholar
• [23] Fan Z, Mao C, Wu Y, Xu J (2023) Spectral graph matching and regularized quadratic relaxations II. Foundations Computational Math. 23(5):1567–1617.Crossref, Google Scholar
• [24] Ferizi S, Quon G, Medard M, Kellis M, Jadbabaie A (2016) Spectral alignment of networks. Preprint, submitted February 12, https://arxiv.org/abs/1602.04181.Google Scholar
• [25] Ganassali L, Massoulié L (2020) From tree matching to sparse graph alignment. Abernethy J, Agarwal S, eds. Proc. 33rd Conf. Learn. Theory (COLT) (PMLR, New York), 1633–1665.Google Scholar
• [26] Ganassali L, Massoulié L, Lelarge M (2021) Impossibility of partial recovery in the graph alignment problem. Belkin M, Kpotufe S, eds. Proc. 34th Conf. Learn. Theory (COLT) (PMLR, New York), 2080–2102.Google Scholar
• [27] Ganassali L, Massoulié L, Lelarge M (2024) Correlation detection in trees for planted graph alignment. Ann. Appl. Probab. 34(3):2799–2843.Crossref, Google Scholar
• [28] Ganassali L, Massoulié L, Semerjian G (2024) Statistical limits of correlation detection in trees. Ann. Appl. Probab. 34(4):3701–3734.Crossref, Google Scholar
• [29] Haghighi AD, Ng AY, Manning CD (2005) Robust textual inference via graph matching. Mooney R, Brew C, Chien LF, Kirchhoff K, eds. Proc. Human Language Tech. Conf. Conf. Empirical Methods Natural Language Processing (EMNLP) (ACL, Vancouver), 387–394. Google Scholar
• [30] Hall G, Massoulié L (2023) Partial recovery in the graph alignment problem. Oper. Res. 71(2):259–272.Link, Google Scholar
• [31] Kazemi E, Hassani SH, Grossglauser M (2015) Growing a graph matching from a handful of seeds. Proc. VLDB Endowment 8(10):1010–1021.Crossref, Google Scholar
• [32] Lyzinski V, Fishkind DE, Priebe CE (2014) Seeded graph matching for correlated Erdős–Rényi graphs. J. Machine Learn. Res. 15:3513–3540.Google Scholar
• [33] Mao C, Rudelson M, Tikhomirov K (2021) Random graph matching with improved noise robustness. Belkin M, Kpotufe S, eds. Proc. 34th Conf. Learn. Theory (COLT) (PMLR, New York), 1–34.Google Scholar
• [34] Mao C, Rudelson M, Tikhomirov K (2023) Exact matching of random graphs with constant correlation. Probab. Theory Related Fields 186(1–2):327–389.Crossref, Google Scholar
• [35] Mao C, Wu Y, Xu J, Yu SH (2023) Random graph matching at Otter’s threshold via counting chandeliers. Servedio R, ed. Proc. 55th Annual ACM Sympos. Theory Comput. (STOC) (ACM, New York), 1345–1356.Google Scholar
• [36] Mao C, Wu Y, Xu J, Yu SH (2024) Testing network correlation efficiently via counting trees. Ann. Statist. 52(6):2483–2505.Crossref, Google Scholar
• [37] Mossel E, Xu J (2020) Seeded graph matching via large neighborhood statistics. Random Structures Algorithms 57(3):570–611.Crossref, Google Scholar
• [38] Narayanan A, Shmatikov V (2008) Robust de-anonymization of large sparse datasets. Blanton M, Enck W, Nita-Rotaru C, eds. Proc. 29th IEEE Sympos. Security Privacy (IEEE, Piscataway, NJ), 111–125.Google Scholar
• [39] Narayanan A, Shmatikov V (2009) De-anonymizing social networks. Du, David, ed. Proc. 30th IEEE Sympos. Security Privacy (IEEE, Piscataway, NJ), 173–187.Google Scholar
• [40] Pedarsani P, Grossglauser M (2011) On the privacy of anonymized networks. Ghose J, ed. Proc. 17th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (ACM, New York), 1235–1243.Google Scholar
• [41] Piccioli G, Semerjian G, Sicuro G, Zdeborová L (2022) Aligning random graphs with a sub-tree similarity message-passing algorithm. J. Statist. Mech. Theory Experiment 2022(6):063401.Crossref, Google Scholar
• [42] Rácz MZ, Sridhar A (2021) Correlated stochastic block models: Exact graph matching with applications to recovering communities. Ranzato M, Beygelzimer A, Dauphin Y, Liang PS, Vaughan JW, eds. Adv. Neural Inform. Processing Systems (NIPS), vol. 34 (Curran Associates Inc., Red Hook, NY), 22259–22273.Google Scholar
• [43] Rácz MZ, Sridhar A (2022) Correlated randomly growing graphs. Ann. Appl. Probab. 32(2):1058–1111.Crossref, Google Scholar
• [44] Shirani F, Garg S, Erkip E (2017) Seeded graph matching: Efficient algorithms and theoretical guarantees. Leus G, ed. 51st Asilomar Conf. Signals Systems Comput. (IEEE, Piscataway, NJ), 253–257.Google Scholar
• [45] Singh R, Xu J, Berger B (2008) Global alignment of multiple protein interaction networks with application to functional orthology detection. Proc. Natl. Acad. Sci. USA 105(35):12763–12768.Crossref, Google Scholar
• [46] Vogelstein JT, Conroy JM, Lyzinski V, Podrazik LJ, Kratzer SG, Harley ET, Fishkind DE, Vogelstein RJ, Priebe CE (2015) Fast approximate quadratic programming for graph matching. PLoS One 10(4):e0121002.Crossref, Google Scholar
• [47] Wang H, Wu Y, Xu J, Yolou I (2022) Random graph matching in geometric models: The case of complete graphs. Loh PL, Raginsky M, eds. Proc. 35th Conf. Learn. Theory (COLT) (PMLR, New York), 3441–3488.Google Scholar
• [48] Wu Y, Xu J, Yu SH (2022) Settling the sharp reconstruction thresholds of random graph matching. IEEE Trans. Inform. Theory 68(8):5391–5417.Crossref, Google Scholar
• [49] Wu Y, Xu J, Yu SH (2023) Testing correlation of unlabeled random graphs. Ann. Appl. Probab. 33(4):2519–2558.Crossref, Google Scholar
• [50] Yartseva L, Grossglauser M (2013) On the performance of percolation graph matching. Muthukrishnan M, ed. COSN ‘13 Proc. First ACM Conf. Online Social Networks (ACM, New York), 119–130.Google Scholar
• [51] Yu L, Xu J, Lin X (2021) Graph matching with partially-correct seeds. J. Machine Learn. Res. 22:12829–12882.Google Scholar