Random Graph Matching at Otter’s Threshold via Counting Chandeliers

References

• Aflalo Y, Bronstein A, Kimmel R (2015) On convex relaxation of graph isomorphism. Proc. Natl. Acad. Sci. USA 112(10):2942–2947.Crossref, Google Scholar
• Alon N, Yuster R, Zwick U (1995) Color-coding. J. ACM 42(4):844–856.Crossref, Google Scholar
• Alon N, Dao P, Hajirasouliha I, Hormozdiari F, Sahinalp SC (2008) Biomolecular network motif counting and discovery by color coding. Bioinformatics 24(13):i241–i249.Crossref, Google Scholar
• Arvind V, Raman V (2002) Approximation algorithms for some parameterized counting problems. Proc. Internat. Sympos. Algorithms Comput. (Springer, New York), 453–464.Google Scholar
• Babai L, Erdos P, Selkow SM (1980) Random graph isomorphism. SIAM J. Comput. 9(3):628–635.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 (MIT Press, Cambridge, MA), 9186–9194.Google Scholar
• Berg AC, Berg TL, Malik J (2005) Shape matching and object recognition using low distortion correspondences. Proc. IEEE Comput. Soc. Conf. Comput. Vision Pattern Recognition, vol. 1 (IEEE, Piscataway, NJ), 26–33.Google Scholar
• Beyer T, Hedetniemi SM (1980) Constant time generation of rooted trees. SIAM J. Comput. 9(4):706–712.Crossref, Google Scholar
• Bollobás B (1982) Distinguishing vertices of random graphs. North-Holland Math. Stud. 62:33–49.Crossref, Google Scholar
• Bubeck S, Ding J, Eldan R, Rácz MZ (2016) Testing for high-dimensional geometry in random graphs. Random Struct. Algorithms 49(3):503–532.Crossref, Google Scholar
• Burkard RE, Cela E, Pardalos PM, Pitsoulis LS (1998) The quadratic assignment problem. Handbook of Combinatorial Optimization (Springer, New York), 1713–1809.Crossref, Google Scholar
• Colbourn CJ, Booth KS (1981) Linear time automorphism algorithms for trees, interval graphs, and planar graphs. SIAM J. Comput. 10(1):203–225.Crossref, Google Scholar
• Conte D, Foggia P, Sansone C, Vento M (2004) Thirty years of graph matching in pattern recognition. Internat. J. Pattern Recognition Artificial Intelligence 18(03):265–298.Crossref, Google Scholar
• Cour T, Srinivasan P, Shi J (2007) Balanced graph matching. Adv. Neural Inform. Processing Systems (MIT Press, Cambridge, MA), 313–320. Crossref, Google Scholar
• Cullina D, Kiyavash N (2016) Improved achievability and converse bounds for Erdos-Rényi graph matching. 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 HV (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
• Czajka T, Pandurangan G (2008) Improved random graph isomorphism. J. Discrete Algorithms 6(1):85–92.Crossref, Google Scholar
• Dai OE, Cullina D, Kiyavash N, Grossglauser M (2019) Analysis of a canonical labeling algorithm for the alignment of correlated Erdos-Rényi graphs. Proc. ACM Measurement Anal. Comput. Systems 3(2):1–25.Crossref, Google Scholar
• Ding J, Du H (2022) Matching recovery threshold for correlated random graphs. Preprint, submitted May 29, https://arxiv.org/abs/2205.14650.Google Scholar
• Ding J, Li Z (2024) 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, Du H, Li Z (2023) Low-degree hardness of detection for correlated erdősrényi graphs. Preprint, submitted November 27, https://arxiv.org/abs/2311.15931.Google Scholar
• Ding J, Ma Z, Wu Y, Xu J (2021) Efficient random graph matching via degree profiles. Probability Theory Related Fields 179(1):29–115.Crossref, Google Scholar
• Fan Z, Mao C, Wu Y, Xu J (2023a) Spectral graph matching and regularized quadratic relaxations I algorithm and Gaussian analysis. Foundations Comput. Math. 23(5):1511–1565.Google Scholar
• Fan Z, Mao C, Wu Y, Xu J (2023b) Spectral graph matching and regularized quadratic relaxations II: Erdős-Rényi graphs and universality. Foundations Comput. Math. 23(5):1567–1617.Google Scholar
• Feizi S, Quon G, Recamonde-Mendoza M, Médard M, Kellis M, Jadbabaie A (2016) Spectral alignment of networks. Preprint, submitted February 12, https://arxiv.org/abs/1602.04181.Google Scholar
• Ganassali L, Massoulié L (2020) From tree matching to sparse graph alignment. Proc. Conf. Learn. Theory (PMLR, New York), 1633–1665.Google Scholar
• Ganassali L, Massoulié L, Lelarge M (2021) Impossibility of partial recovery in the graph alignment problem. Proc. Conf. Learn. Theory (PMLR, New York), 2080–2102.Google Scholar
• Ganassali L, Massoulié L, Lelarge M (2022a) Correlation detection in trees for planted graph alignment. Proc. 13th Innovations Theoretical Comput. Sci. Conf. 74:1–74:8.Google Scholar
• Ganassali L, Massoulié L, Semerjian G (2022b) Statistical limits of correlation detection in trees. Preprint, submitted September 27, https://arxiv.org/abs/2209.13723.Google Scholar
• Haghighi AD, Ng AY, Manning CD (2005) Robust textual inference via graph matching. Proc. Conf. Human Language Tech. 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
• Hopkins SB, Steurer D (2017) Efficient Bayesian estimation from few samples: Community detection and related problems. Proc. IEEE 58th Ann. Sympos. Foundations Comput. Sci. (IEEE Computer Society, Piscataway, NJ), 379–390.Google Scholar
• Jordan C (1869) Sur les assemblages de lignes. J. Reine Angewandte Math. 70:185–190.Google Scholar
• Koopmans TC, Beckmann M (1957) Assignment problems and the location of economic activities. Econometrica 25(1):53–76.Crossref, Google Scholar
• Livi L, Rizzi A (2013) The graph matching problem. Pattern Anal. Applications 16(3):253–283.Crossref, Google Scholar
• Lubars J, Srikant R (2018) Correcting the output of approximate graph matching algorithms. Proc. IEEE Conf. Comput. Comm. (IEEE, Piscataway, NJ), 1745–1753.Google Scholar
• Lyzinski V, Fishkind D, Fiori M, Vogelstein J, Priebe C, Sapiro G (2016) Graph matching: Relax at your own risk. IEEE Trans. Pattern Anal. Machine Intelligence 38(1):60–73.Crossref, Google Scholar
• Lyzinski V, Fishkind DE, Priebe CE (2014) Seeded graph matching for correlated Erdös-Rényi graphs. J. Machine Learn. Res. 15(1):3513–3540.Google Scholar
• Makarychev K, Manokaran R, Sviridenko M (2010) Maximum quadratic assignment problem: Reduction from maximum label cover and LP-based approximation algorithm. Proc. Internat. Colloquium Automata, Languages, Programming (Springer, New York), 594–604.Google Scholar
• Mao C, Rudelson M, Tikhomirov K (2021a) Random graph matching with improved noise robustness. Proc. 34th Conf. Learn. Theory, Proceedings of Machine Learning Research, vol. 134 (PMLR, New York), 3296–3329.Google Scholar
• Mao C, Rudelson M, Tikhomirov K (2023) Exact matching of random graphs with constant correlation. Probability Theory Related Fields 186(1):327–389.Crossref, Google Scholar
• Mao C, Wu Y, Xu J, Yu SH (2021b) Testing network correlation efficiently via counting trees. Preprint, submitted October 22, https://arxiv.org/abs/2110.11816.Google Scholar
• Milo R, Shen-Orr S, Itzkovitz S, Kashtan N, Chklovskii D, Alon U (2002) Network motifs: Simple building blocks of complex networks. Science 298(5594):824–827.Crossref, Google Scholar
• Mossel E, Xu J (2019) Seeded graph matching via large neighborhood statistics. Proc. 30th Ann. ACM-SIAM Sympos. Discrete Algorithms (SIAM, Philadelphia), 1005–1014.Google Scholar
• Mossel E, Neeman J, Sly A (2015) Reconstruction and estimation in the planted partition model. Probability Theory Related Fields 162(3):431–461.Crossref, Google Scholar
• Narayanan A, Shmatikov V (2008) Robust de-anonymization of large sparse datasets. Proc. IEEE Sympos. Security Privacy (IEEE, Piscataway, NJ), 111–125.Google Scholar
• Narayanan A, Shmatikov V (2009) De-anonymizing social networks. Proc. 30th IEEE Sympos. Security Privacy (IEEE, Piscataway, NJ), 173–187.Google Scholar
• Olsson C, Wagner S (2022) Automorphisms of random trees. Proc. 33rd Internat. Conf. Probabilistic, Combinatorial Asymptotic Methods Analysis Algorithms (Schloss Dagstuhl-Leibniz-Zentrum für Informatik, Wadern, Germany).Google Scholar
• Otter R (1948) The number of trees. Ann. Math. 49(3):583–599.Crossref, Google Scholar
• Pardalos PM, Wolkowicz H (1994) Proc. Quadratic Assignment and Related Problems: DIMACS Workshop, vol. 16 (American Mathematical Society, Providence, RI).Google Scholar
• Pedarsani P, Grossglauser M (2011) On the privacy of anonymized networks. Proc. 17th ACM SIGKDD Internat. Conf. Knowledge Discovery Data Mining (ACM, New York), 1235–1243.Google Scholar
• Piccioli G, Semerjian G, Sicuro G, Zdeborová L (2022) Aligning random graphs with a sub-tree similarity message-passing algorithm. J. Statist. Mechanisms 2022(6):063401.Crossref, Google Scholar
• Pólya G (1937) Kombinatorische anzahlbestimmungen für gruppen, graphen und chemische verbindungen. Acta Math. 68:145–254.Crossref, Google Scholar
• Racz M, 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
• Ribeiro P, Paredes P, Silva ME, Aparicio D, Silva F (2021) A survey on subgraph counting: Concepts, algorithms, and applications to network motifs and graphlets. ACM Comput. Survey 54(2):1–36.Crossref, Google Scholar
• Shirani F, Garg S, Erkip E (2017) Seeded graph matching: Efficient algorithms and theoretical guarantees. Proc. 51st Asilomar Conf. Signals, Systems, Comput. (IEEE, Piscataway, NJ), 253–257.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
• Umeyama S (1988) An eigendecomposition approach to weighted graph matching problems. IEEE Trans. Pattern Anal. Machine Intelligence 10(5):695–703.Crossref, Google Scholar
• Vogelstein JT, Conroy JM, Podrazik LJ, Kratzer SG, Harley ET, Fishkind DE, Vogelstein RJ, et al. (2011) Large (brain) graph matching via fast approximate quadratic programming. Preprint, submitted December 23, https://arxiv.org/abs/1112.5507.Google Scholar
• Wang Z, Wang W, Wang L (2023) Efficient algorithms for attributed graph alignment with vanishing edge correlation. Preprint, submitted August 17, https://arxiv.org/abs/2308.09210.Google Scholar
• Wang H, Wu Y, Xu J, Yolou I (2022a) Random graph matching in geometric models: The case of complete graphs. Proc. Conf. Learn. Theory (PMLR, New York), 3441–3488.Google Scholar
• Wang Z, Zhang N, Wang W, Wang L (2022b) On the feasible region of efficient algorithms for attributed graph alignment. Proc. IEEE Internat. Sympos. Inform. Theory (IEEE, Piscataway, NJ), 1163–1168.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
• Yartseva L, Grossglauser M (2013) On the performance of percolation graph matching. Proc. 1st ACM Conf, Online Social Networks (ACM, New York), 119–130.Google Scholar
• Yu L, Xu J, Lin X (2021a) Graph matching with partially-correct seeds. J. Machine Learn. Res. 22(1):12829–12882.Google Scholar
• Yu L, Xu J, Lin X (2021b) The power of d-hops in matching power-law graphs. Proc. ACM Measurement Anal. Comput. Systems 5(2):1–43.Crossref, Google Scholar
• Zaslavskiy M, Bach F, Vert JP (2008) A path following algorithm for the graph matching problem. IEEE Trans. Pattern Anal. Machine Intelligence 31(12):2227–2242.Crossref, Google Scholar