More Web Proxy on the site http://driver.im/

research-article

Public Access

Random Graph Matching at Otter’s Threshold via Counting Chandeliers

Authors:

Sophie H. YuAuthors Info & Claims

STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing

Pages 1345 - 1356

https://doi.org/10.1145/3564246.3585156

Published: 02 June 2023 Publication History

Abstract

We propose an efficient algorithm for graph matching based on similarity scores constructed from counting a certain family of weighted trees rooted at each vertex. For two Erdős–Rényi graphs G(n,q) whose edges are correlated through a latent vertex correspondence, we show that this algorithm correctly matches all but a vanishing fraction of the vertices with high probability, provided that nq→∞ and the edge correlation coefficient ρ satisfies ρ²>α ≈ 0.338, where α is Otter’s tree-counting constant. Moreover, this almost exact matching can be made exact under an extra condition that is information-theoretically necessary. This is the first polynomial-time graph matching algorithm that succeeds at an explicit constant correlation and applies to both sparse and dense graphs. In comparison, previous methods either require ρ=1−o(1) or are restricted to sparse graphs.

The crux of the algorithm is a carefully curated family of rooted trees called chandeliers, which allows effective extraction of the graph correlation from the counts of the same tree while suppressing the undesirable correlation between those of different trees.

References

[1]

Yonathan Aflalo, Alexander Bronstein, and Ron Kimmel. 2015. On convex relaxation of graph isomorphism. Proceedings of the National Academy of Sciences, 112, 10 (2015), 2942–2947. https://doi.org/10.1073/pnas.1401651112

[2]

Noga Alon, Phuong Dao, Iman Hajirasouliha, Fereydoun Hormozdiari, and S Cenk Sahinalp. 2008. Biomolecular network motif counting and discovery by color coding. Bioinformatics, 24, 13 (2008), i241–i249. https://doi.org/10.1093/bioinformatics/btn163

[3]

Noga Alon, Raphael Yuster, and Uri Zwick. 1995. Color-coding. Journal of the ACM (JACM), 42, 4 (1995), 844–856. https://doi.org/10.1145/210332.210337

Digital Library

[4]

Vikraman Arvind and Venkatesh Raman. 2002. Approximation algorithms for some parameterized counting problems. In International Symposium on Algorithms and Computation. 453–464. https://doi.org/10.1007/3-540-36136-7_40

[5]

László Babai. 2016. Graph Isomorphism in Quasipolynomial Time [Extended Abstract]. In Proceedings of the Forty-eighth Annual ACM Symposium on Theory of Computing (STOC ’16). ACM, New York, NY, USA. 684–697. isbn:978-1-4503-4132-5 https://doi.org/10.1145/2897518.2897542

Digital Library

[6]

Boaz Barak, Chi-Ning Chou, Zhixian Lei, Tselil Schramm, and Yueqi Sheng. 2019. (Nearly) Efficient Algorithms for the Graph Matching Problem on Correlated Random Graphs. In Advances in Neural Information Processing Systems. 9186–9194. https://doi.org/10.48550/arXiv.1805.02349

[7]

Terry Beyer and Sandra Mitchell Hedetniemi. 1980. Constant time generation of rooted trees. SIAM J. Comput., 9, 4 (1980), 706–712. https://doi.org/10.1137/0209055

Digital Library

[8]

Béla Bollobás. 1982. Distinguishing vertices of random graphs. North-Holland Mathematics Studies, 62 (1982), 33–49. https://doi.org/10.1016/S0304-0208(08)73545-X

[9]

Sébastien Bubeck, Jian Ding, Ronen Eldan, and Miklós Z Rácz. 2016. Testing for high-dimensional geometry in random graphs. Random Structures & Algorithms, 49, 3 (2016), 503–532. https://doi.org/10.1002/rsa.20633

[10]

Rainer E Burkard, Eranda Cela, Panos M Pardalos, and Leonidas S Pitsoulis. 1998. The quadratic assignment problem. In Handbook of combinatorial optimization. Springer, 1713–1809. https://doi.org/10.1007/978-1-4613-0303-9_27

[11]

Charles J Colbourn and Kellogg S Booth. 1981. Linear time automorphism algorithms for trees, interval graphs, and planar graphs. SIAM J. Comput., 10, 1 (1981), 203–225. https://doi.org/10.1137/0210015

Digital Library

[12]

Daniel Cullina and Negar Kiyavash. 2016. Improved achievability and converse bounds for Erdos-Rényi graph matching. ACM SIGMETRICS performance evaluation review, 44, 1 (2016), 63–72. https://doi.org/10.1145/2964791.2901460

Digital Library

[13]

Daniel Cullina and Negar Kiyavash. 2017. Exact alignment recovery for correlated Erdős-Rényi graphs. arXiv 1711.06783, https://doi.org/10.48550/arXiv.1711.06783

[14]

Daniel Cullina, Negar Kiyavash, Prateek Mittal, and H Vincent Poor. 2019. Partial Recovery of Erdős-Rényi Graph Alignment via k-Core Alignment. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 3, 3 (2019), 1–21. https://doi.org/10.1145/3366702

Digital Library

[15]

Tomek Czajka and Gopal Pandurangan. 2008. Improved random graph isomorphism. Journal of Discrete Algorithms, 6, 1 (2008), 85–92. https://doi.org/10.1016/j.jda.2007.01.002

Digital Library

[16]

Osman Emre Dai, Daniel Cullina, Negar Kiyavash, and Matthias Grossglauser. 2019. Analysis of a canonical labeling algorithm for the alignment of correlated Erdos-Rényi graphs. Proceedings of the ACM on Measurement and Analysis of Computing Systems, 3, 2 (2019), 1–25. https://doi.org/10.1145/3341617.3326151

Digital Library

[17]

Jian Ding and Hang Du. 2022. Matching recovery threshold for correlated random graphs. arXiv preprint arXiv:2205.14650, https://doi.org/10.48550/arXiv.2205.14650

[18]

Jian Ding, Zongming Ma, Yihong Wu, and Jiaming Xu. 2021. Efficient random graph matching via degree profiles. Probability Theory and Related Fields, 179, 1 (2021), 29–115. https://doi.org/10.1007/s00440-020-00997-4

[19]

Zhou Fan, Cheng Mao, Yihong Wu, and Jiaming Xu. 2022. Spectral Graph Matching and Regularized Quadratic Relaxations I Algorithm and Gaussian Analysis. Foundations of Computational Mathematics, Jun, 1–55. https://doi.org/10.1007/s10208-022-09570-y

Digital Library

[20]

Zhou Fan, Cheng Mao, Yihong Wu, and Jiaming Xu. 2022. Spectral Graph Matching and Regularized Quadratic Relaxations II: Erdős-Rényi Graphs and Universality. Foundations of Computational Mathematics, Jun, 1–51. https://doi.org/10.1007/s10208-022-09575-7

Digital Library

[21]

Luca Ganassali and Laurent Massoulié. 2020. From tree matching to sparse graph alignment. In Conference on Learning Theory. 1633–1665. https://doi.org/10.48550/arXiv.2002.01258

[22]

Luca Ganassali, Laurent Massoulié, and Marc Lelarge. 2021. Impossibility of partial recovery in the graph alignment problem. In Conference on Learning Theory. 2080–2102. https://doi.org/10.48550/arXiv.2102.02685

[23]

Luca Ganassali, Laurent Massoulié, and Marc Lelarge. 2022. Correlation Detection in Trees for Planted Graph Alignment. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). 74:1–74:8. isbn:978-3-95977-217-4 issn:1868-8969 https://doi.org/10.4230/LIPIcs.ITCS.2022.74

[24]

Luca Ganassali, Laurent Massoulié, and Guilhem Semerjian. 2022. Statistical limits of correlation detection in trees. arXiv preprint arXiv:2209.13723, https://doi.org/10.48550/arXiv.2209.13723

[25]

Georgina Hall and Laurent Massoulié. 2022. Partial recovery in the graph alignment problem. Operations Research, https://doi.org/10.1287/opre.2022.2355

Digital Library

[26]

Samuel B Hopkins and David Steurer. 2017. Efficient Bayesian Estimation from Few Samples: Community Detection and Related Problems. In 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE Computer Society, Los Alamitos, CA, USA. 379–390. issn:0272-5428 https://doi.org/10.1109/FOCS.2017.42

[27]

Camille Jordan. 1869. Sur les assemblages de lignes. Journal für die reine und angewandte Mathematik, 70 (1869), 185–190. http://eudml.org/doc/148084

[28]

Vince Lyzinski, Donniell Fishkind, Marcelo Fiori, Joshua Vogelstein, Carey Priebe, and Guillermo Sapiro. 2016. Graph matching: Relax at your own risk. IEEE Transactions on Pattern Analysis & Machine Intelligence, 38, 1 (2016), 60–73. https://doi.org/10.1109/TPAMI.2015.2424894

Digital Library

[29]

Konstantin Makarychev, Rajsekar Manokaran, and Maxim Sviridenko. 2010. Maximum quadratic assignment problem: Reduction from maximum label cover and lp-based approximation algorithm. In International Colloquium on Automata, Languages, and Programming. 594–604. https://doi.org/10.1007/978-3-642-14165-2_50

[30]

Cheng Mao, Mark Rudelson, and Konstantin Tikhomirov. 2021. Random Graph Matching with Improved Noise Robustness. In Proceedings of Thirty Fourth Conference on Learning Theory (Proceedings of Machine Learning Research, Vol. 134). 3296–3329. https://doi.org/10.48550/arXiv.2101.11783

[31]

Cheng Mao, Mark Rudelson, and Konstantin Tikhomirov. 2023. Exact matching of random graphs with constant correlation. Probability Theory and Related Fields, 1–63. https://doi.org/10.1007/s00440-022-01184-3

[32]

Cheng Mao, Yihong Wu, Jiaming Xu, and Sophie H Yu. 2021. Testing network correlation efficiently via counting trees. arXiv preprint arXiv:2110.11816, https://doi.org/10.48550/arXiv.2110.11816

[33]

Cheng Mao, Yihong Wu, Jiaming Xu, and Sophie H Yu. 2022. Random graph matching at Otter’s threshold via counting chandeliers. arXiv preprint arXiv:2209.12313, https://doi.org/10.48550/arXiv.2209.12313

[34]

Ron Milo, Shai Shen-Orr, Shalev Itzkovitz, Nadav Kashtan, Dmitri Chklovskii, and Uri Alon. 2002. Network motifs: simple building blocks of complex networks. Science, 298, 5594 (2002), 824–827. https://doi.org/10.1126/science.298.5594.824

[35]

Elchanan Mossel, Joe Neeman, and Allan Sly. 2015. Reconstruction and estimation in the planted partition model. Probability Theory and Related Fields, 162, 3 (2015), 431–461. https://doi.org/10.1007/s00440-014-0576-6

[36]

Arvind Narayanan and Vitaly Shmatikov. 2008. Robust de-anonymization of large sparse datasets. In 2008 IEEE Symposium on Security and Privacy (sp 2008). 111–125. https://doi.org/10.1109/SP.2008.33

Digital Library

[37]

Christoffer Olsson and Stephan Wagner. 2022. Automorphisms of random trees. In 33rd International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2022). https://doi.org/10.4230/LIPIcs.AofA.2022.16

[38]

Richard Otter. 1948. The number of trees. Annals of Mathematics, 583–599. https://doi.org/10.2307/1969046

[39]

Pedram Pedarsani and Matthias Grossglauser. 2011. On the privacy of anonymized networks. In Proceedings of the 17th ACM SIGKDD international conference on Knowledge discovery and data mining. 1235–1243. https://doi.org/10.1145/2020408.2020596

Digital Library

[40]

Giovanni Piccioli, Guilhem Semerjian, Gabriele Sicuro, and Lenka Zdeborová. 2022. Aligning random graphs with a sub-tree similarity message-passing algorithm. Journal of Statistical Mechanics: Theory and Experiment, 2022, 6 (2022), 063401. https://doi.org/10.1088/1742-5468/ac70d2

[41]

George Pólya. 1937. Kombinatorische anzahlbestimmungen für gruppen, graphen und chemische verbindungen. Acta mathematica, 68 (1937), 145–254.

[42]

Pedro Ribeiro, Pedro Paredes, Miguel EP Silva, David Aparicio, and Fernando Silva. 2021. A survey on subgraph counting: concepts, algorithms, and applications to network motifs and graphlets. ACM Computing Surveys (CSUR), 54, 2 (2021), 1–36. https://doi.org/10.1145/3433652

Digital Library

[43]

Rohit Singh, Jinbo Xu, and Bonnie Berger. 2008. Global alignment of multiple protein interaction networks with application to functional orthology detection. Proceedings of the National Academy of Sciences, 105, 35 (2008), 12763–12768. https://doi.org/10.1073/pnas.0806627105

[44]

Shinji Umeyama. 1988. An eigendecomposition approach to weighted graph matching problems. IEEE Transactions on Pattern Analysis and Machine Intelligence, 10, 5 (1988), 695–703. https://doi.org/10.1109/34.6778

Digital Library

[45]

Yihong Wu, Jiaming Xu, and Sophie H. Yu. 2022. Settling the sharp reconstruction thresholds of random graph matching. IEEE Transactions on Information Theory, 68, 8 (2022), Apr, 5391–5417. https://doi.org/10.1109/TIT.2022.3169005

Digital Library

[46]

Lyudmila Yartseva and Matthias Grossglauser. 2013. On the performance of percolation graph matching. In Proceedings of the first ACM conference on Online social networks. 119–130. https://doi.org/10.1145/2512938.2512952

Digital Library

[47]

Mikhail Zaslavskiy, Francis Bach, and Jean-Philippe Vert. 2008. A path following algorithm for the graph matching problem. IEEE Transactions on Pattern Analysis and Machine Intelligence, 31, 12 (2008), 2227–2242. https://doi.org/10.1109/TPAMI.2008.245

Digital Library

Cited By

Ameen THajek BSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Robust graph matching when nodes are corruptProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692124(1276-1305)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692124
Araya ETyagi H(2024)Graph Matching via convex relaxation to the simplexFoundations of Data Science10.3934/fods.2024034(0-0)Online publication date: 2024
https://doi.org/10.3934/fods.2024034
Ganassali LMassoulié LSemerjian G(2024)Statistical limits of correlation detection in treesThe Annals of Applied Probability10.1214/23-AAP204834:4Online publication date: 1-Aug-2024
https://doi.org/10.1214/23-AAP2048
Show More Cited By

Index Terms

Random Graph Matching at Otter’s Threshold via Counting Chandeliers
1. Mathematics of computing
  1. Discrete mathematics
    1. Graph theory
      1. Random graphs
2. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Random network models

Recommendations

Error-tolerant geometric graph similarity and matching
Highlights
- An intuitive approach to graph similarity and matching using geometric graphs.
- ...
Abstract
Geometric graph matching is the process of evaluating the similarity between geometric graphs, where each vertex has an associated coordinate point in a plane. Exact matching computes a strict correspondence between two geometric ...
Error Correcting Graph Matching: On the Influence of the Underlying Cost Function

This paper investigates the influence of the cost function on the optimal match between two graphs. It is shown that, for a given cost function, there are an infinite number of other cost functions that lead, for any given pair of graphs, to the same ...
A graph matching method and a graph matching distance based on subgraph assignments

During the last decade, the use of graph-based object representation has drastically increased. As a matter of fact, object representation by means of graphs has a number of advantages over feature vectors. As a consequence, methods to compare graphs ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

STOC 2023: Proceedings of the 55th Annual ACM Symposium on Theory of Computing

June 2023

1926 pages

ISBN:9781450399135

DOI:10.1145/3564246

General Chair:
Barna Saha
University of California at San Diego, USA
,
Program Chair:
Rocco A. Servedio
Columbia University, USA

Copyright © 2023 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 June 2023

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Conference

STOC '23

Sponsor:

SIGACT

STOC '23: 55th Annual ACM Symposium on Theory of Computing

June 20 - 23, 2023

FL, Orlando, USA

Acceptance Rates

Overall Acceptance Rate 1,469 of 4,586 submissions, 32%

Upcoming Conference

STOC '25

Sponsor:
sigact

57th Annual ACM Symposium on Theory of Computing (STOC 2025)

June 23 - 27, 2025

Prague , Czech Republic

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
299
Total Downloads

Downloads (Last 12 months)159
Downloads (Last 6 weeks)17

Reflects downloads up to 21 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ameen THajek BSalakhutdinov RKolter ZHeller KWeller AOliver NScarlett JBerkenkamp F(2024)Robust graph matching when nodes are corruptProceedings of the 41st International Conference on Machine Learning10.5555/3692070.3692124(1276-1305)Online publication date: 21-Jul-2024
https://dl.acm.org/doi/10.5555/3692070.3692124
Araya ETyagi H(2024)Graph Matching via convex relaxation to the simplexFoundations of Data Science10.3934/fods.2024034(0-0)Online publication date: 2024
https://doi.org/10.3934/fods.2024034
Ganassali LMassoulié LSemerjian G(2024)Statistical limits of correlation detection in treesThe Annals of Applied Probability10.1214/23-AAP204834:4Online publication date: 1-Aug-2024
https://doi.org/10.1214/23-AAP2048
Liu HScaglione AWai H(2024)Blind Graph Matching Using Graph SignalsIEEE Transactions on Signal Processing10.1109/TSP.2024.338284072(1766-1781)Online publication date: 2024
https://doi.org/10.1109/TSP.2024.3382840
Li ZJohnson BSussman DPriebe CLyzinski V(2024)Gotta Match 'Em All: Solution Diversification in Graph Matching Matched FiltersIEEE Transactions on Signal and Information Processing over Networks10.1109/TSIPN.2024.346792110(752-764)Online publication date: 2024
https://doi.org/10.1109/TSIPN.2024.3467921
Zhang NWang ZWang WWang L(2024)Attributed Graph AlignmentIEEE Transactions on Information Theory10.1109/TIT.2024.340381070:8(5910-5934)Online publication date: Aug-2024
https://doi.org/10.1109/TIT.2024.3403810
Wang ZZhang NWang WWang L(2024)On the Feasible Region of Efficient Algorithms for Attributed Graph AlignmentIEEE Transactions on Information Theory10.1109/TIT.2024.335110770:5(3622-3639)Online publication date: May-2024
https://doi.org/10.1109/TIT.2024.3351107
Yang JChung H(2024)Exact Graph Matching in Correlated Gaussian-Attributed Erdős- Rényi Mode2024 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT57864.2024.10619555(3450-3455)Online publication date: 7-Jul-2024
https://doi.org/10.1109/ISIT57864.2024.10619555
Oren-Loberman MPaslev VHuleihel W(2024)Testing Dependency of Weighted Random Graphs2024 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT57864.2024.10619266(1263-1268)Online publication date: 7-Jul-2024
https://doi.org/10.1109/ISIT57864.2024.10619266
Muratori ASemerjian G(2024)Faster algorithms for the alignment of sparse correlated Erdős–Rényi random graphsJournal of Statistical Mechanics: Theory and Experiment10.1088/1742-5468/ad87472024:11(113405)Online publication date: 20-Nov-2024
https://doi.org/10.1088/1742-5468/ad8747
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents