Aligning Multiple Inhomogeneous Random Graphs: Fundamental Limits of Exact Recovery

References

• Abbe E (2018) Community detection and stochastic block models: Recent developments. J. Machine Learn. Res. 18(177):1–86.Google Scholar
• Ameen T, Hajek B (2023) Robust graph matching when nodes are corrupt. Preprint, submitted October 23, https://arxiv.org/abs/2310.18543.Google Scholar
• Ameen T, Hajek B (2025a) Detecting correlation between multiple unlabeled Gaussian networks. 2025 IEEE Internat. Sympos. Inform. Theory (ISIT) (IEEE, Piscataway, NJ), 1–6.Google Scholar
• Ameen T, Hajek B (2025b) Exact random graph matching with multiple graphs. 2025 IEEE Internat. Sympos. Inform. Theory (ISIT) (IEEE, Piscataway, NJ), 1–6.Google Scholar
• Bandyopadhyay S, Sharan R, Ideker T (2006) Systematic identification of functional orthologs based on protein network comparison. Genome Res. 16(3):428–435.Crossref, Google Scholar
• Barak B, Chou CN, Lei Z, Schramm T, Sheng Y (2019) (Nearly) efficient algorithms for the graph matching problem on correlated random graphs. Adv. Neural Inform. Processing Systems 32:186–9194.Google Scholar
• Calissano A, Papadopoulo T, Pennec X, Deslauriers-Gauthier S (2024) Graph alignment exploiting the spatial organization improves the similarity of brain networks. Human Brain Mapp. 45(1):e26554.Crossref, Google Scholar
• Chai S, Rácz MZ (2024) Efficient graph matching for correlated stochastic block models. Preprint, submitted December 3, https://arxiv.org/abs/2412.02661.Google Scholar
• Chung F, Lu L (2002) The average distances in random graphs with given expected degrees. Proc. Natl. Acad. Sci. USA 99(25):15879–15882.Crossref, Google Scholar
• Cullina D, Kiyavash N (2016) Improved achievability and converse bounds for Erdős-Rényi graph matching. ACM SIGMETRICS Performance Evaluation Rev. 44(1):63–72.Crossref, Google Scholar
• 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
• Cullina D, Kiyavash N, Mittal P, Poor V (2019) Partial recovery of Erdős-Rényi graph alignment via k-core alignment. Proc. ACM Measurement Anal. Comput. Systems 3(3):1–21.Crossref, Google Scholar
• 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 Anal. Comput. Systems 3(2):1–25.Crossref, Google Scholar
• Ding J, Du H (2023) Matching recovery threshold for correlated random graphs. Ann. Statist. 51(4):1718–1743.Crossref, Google Scholar
• Ding J, Li Z (2023) A polynomial-time iterative algorithm for random graph matching with non-vanishing correlation. Preprint, submitted June 1, https://arxiv.org/abs/2306.00266.Google Scholar
• Ding J, Fei Y, Wang Y (2023) Efficiently matching random inhomogeneous graphs via degree profiles. Preprint, submitted October 16, https://arxiv.org/abs/2310.10441.Google Scholar
• Ding J, Ma Z, Wu Y, Xu J (2021) Efficient random graph matching via degree profiles. Probab. Theory Related Fields 179:29–115.Crossref, Google Scholar
• Du H (2025) Optimal recovery of correlated Erdos-Renyi graphs. Preprint, submitted February 17, https://arxiv.org/abs/2502.12077.Google Scholar
• Even B, Ganassali L (2025) Statistical-computational gap in multiple Gaussian graph alignment. Preprint, submitted November 29, https://arxiv.org/abs/2512.00610.Google Scholar
• Fan Z, Mao C, Wu Y, Xu J (2022) Spectral graph matching and regularized quadratic relaxations II: Erdős-Rényi graphs and universality. Foundations Comput. Math. 23:1567–1617.Crossref, Google Scholar
• Ganassali L, Massoulié L, Lelarge M (2021) Impossibility of partial recovery in the graph alignment problem. Conf. Learn. Theory (PMLR, New York), 2080–2102.Google Scholar
• Gaudio J, Rácz MZ, Sridhar A (2022) Exact community recovery in correlated stochastic block models. Conf. Learn. Theory (PMLR, New York), 2183–2241.Google Scholar
• Haghighi A, Ng AY, Manning CD (2005) Robust textual inference via graph matching. Proc. Human Language Tech. Conf. Conf. Empirical Methods Natural Language Processing (Association for Computational Linguistics, Stroudsburg, PA), 387–394.Google Scholar
• Hall G, Massoulié L (2023) Partial recovery in the graph alignment problem. Oper. Res. 71(1):259–272.Link, Google Scholar
• Holland PW, Laskey KB, Leinhardt S (1983) Stochastic blockmodels: First steps. Soc. Networks 5(2):109–137.Crossref, Google Scholar
• Huang D, Song X, Yang P (2024) Information-theoretic thresholds for the alignments of partially correlated graphs. Preprint, submitted June 8, https://arxiv.org/abs/2406.05428.Google Scholar
• Josephs N, Li W, Kolaczyk ED (2021) Network recovery from unlabeled noisy samples. 2021 55th Asilomar Conf. Signals Systems Comput. (IEEE, Piscataway, NJ), 1268–1273.Google Scholar
• Kazemi E, Hassani H, Grossglauser M, Pezeshgi Modarres H (2016) Proper: Global protein interaction network alignment through percolation matching. BMC Bioinformatics 17(1):1–16.Crossref, Google Scholar
• Liao CS, Lu K, Baym M, Singh R, Berger B (2009) IsoRankN: Spectral methods for global alignment of multiple protein networks. Bioinformatics 25(12):i253–i258.Crossref, Google Scholar
• Liu S, Rácz MZ (2023) Phase transition in noisy high-dimensional random geometric graphs. Electron. J. Statist. 17(2):3512–3574.Crossref, Google Scholar
• Lubars J, Srikant R (2018) Correcting the output of approximate graph matching algorithms. IEEE INFOCOM 2018-IEEE Conf. Comput. Comm. (IEEE, Piscataway, NJ), 1745–1753.Google Scholar
• Łuczak T (1991) Size and connectivity of the k-core of a random graph. Discrete Math. 91(1):61–68.Crossref, Google Scholar
• Mao C, Rudelson M, Tikhomirov K (2023a) Exact matching of random graphs with constant correlation. Probab. Theory Related Fields 186(1–2):327–389.Crossref, Google Scholar
• Mao C, Wu Y, Xu J, Yu SH (2023b) Random graph matching at Otter’s threshold via counting chandeliers. Proc. 55th Annual ACM Sympos. Theory Comput., 1345–1356.Google Scholar
• Mitzenmacher M, Upfal E (2017) Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis (Cambridge University Press, Cambridge, UK).Google Scholar
• Mossel E, Xu J (2020) Seeded graph matching via large neighborhood statistics. Random Structures Algorithms 57(3):570–611.Crossref, Google Scholar
• Narayanan A, Shmatikov V (2008) Robust de-anonymization of large sparse datasets. 2008 IEEE Sympos. Security Privacy (SP 2008) (IEEE, Piscataway, NJ), 111–125.Google Scholar
• Narayanan A, Shmatikov V (2009) De-anonymizing social networks. 2009 30th IEEE Sympos. Security Privacy (IEEE, Piscataway, NJ), 173–187.Google Scholar
• Pedarsani P, Grossglauser M (2011) On the privacy of anonymized networks. Proc. 17th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (Association for Computing Machinery, New York), 1235–1243.Google Scholar
• Rácz MZ, Sridhar A (2021) Correlated stochastic block models: Exact graph matching with applications to recovering communities. Adv. Neural Inform. Processing Systems 34:22259–22273.Google Scholar
• Rácz MZ, Sridhar A (2023) Matching correlated inhomogeneous random graphs using the k-core estimator. 2023 IEEE International Sympos. Inform. Theory (ISIT) (IEEE, Piscataway, NJ), 2499–2504.Google Scholar
• Rácz MZ, Zhang J (2024) Harnessing multiple correlated networks for exact community recovery. Adv. Neural Inform. Processing Systems 37:53834–53886.Google Scholar
• Schellewald C, Schnörr C (2005) Probabilistic subgraph matching based on convex relaxation. Internat. Workshop Energy Minimization Methods Comput. Vision Pattern Recognition (Springer, Berlin, Heidelberg), 171–186.Crossref, Google Scholar
• 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
• Sporns O, Tononi G, Kötter R (2005) The human connectome: A structural description of the human brain. PLoS Comput. Biol. 1(4):e42.Crossref, Google Scholar
• Vassaux L, Massoulié L (2025) The feasibility of multi-graph alignment: A Bayesian approach. Preprint, submitted February 24, https://arxiv.org/abs/2502.17142.Google Scholar
• Vento M, Foggia P (2013) Graph matching techniques for computer vision. Image Processing: Concepts, Methodologies, Tools, and Applications (IGI Global, Hershey, PA), 381–421.Crossref, Google Scholar
• Vijayan V, Milenković T (2017) Multiple network alignment via multiMAGNA+. IEEE/ACM Trans. Comput. Biol. Bioinform. 15(5):1669–1682.Crossref, Google Scholar
• Wang Z, Zhang N, Wang W, Wang L (2024) On the feasible region of efficient algorithms for attributed graph alignment. IEEE Trans. Inform. Theory 70(5):3622–3639.Crossref, Google Scholar
• 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
• Yan J, Yin XC, Lin W, Deng C, Zha H, Yang X (2016) A short survey of recent advances in graph matching. Proc. 2016 ACM Internat. Conf. Multimedia Retrieval (Association for Computing Machinery, New York), 167–174.Google Scholar
• Yang J, Chung HW (2024) Exact graph matching in correlated Gaussian-attributed Erdős-Rényi model. 2024 IEEE Internat. Sympos. Inform. Theory (ISIT) (IEEE, Piscataway, NJ), 3450–3455.Google Scholar
• Ye K, Dong S, Fan Q, Wang H, Yi L, Xia F, Wang J, Chen B (2022) Multi-robot active mapping via neural bipartite graph matching. Proc. IEEE/CVF Conf. Comput. Vision Pattern Recognition, 14839–14848.Google Scholar
• Zhang N, Wang Z, Wang W, Wang L (2024) Attributed graph alignment. IEEE Trans. Inform. Theory 70(8):5910–5934.Crossref, Google Scholar
• Zhu X, Zhu L, Geng X (2024) k-wise multi-graph matching. IET Image Processing 18(14):4760–4777.Crossref, Google Scholar