Document Open Access Logo

Correlation Detection in Trees for Planted Graph Alignment

Authors Luca Ganassali, Laurent Massoulié, Marc Lelarge

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2022.74.pdf
  • Filesize: 0.71 MB
  • 8 pages

Document Identifiers

Author Details

Luca Ganassali
  • Inria, DI/ENS, PSL Research University, Paris, France
Laurent Massoulié
  • MSR-Inria Joint Centre, Inria, DI/ENS, PSL Research University, Paris, France
Marc Lelarge
  • Inria, DI/ENS, PSL Research University, Paris, France

Funding

This work was partially supported by the French government under management of Agence Nationale de la Recherche as part of the "Investissements d’avenir" program, reference ANR19-P3IA-0001 (PRAIRIE 3IA Institute).

Acknowledgements

The authors would like to thank Guilhem Semerjian for helpful discussions, and the reviewers for relevant comments.

Cite AsGet BibTex

Luca Ganassali, Laurent Massoulié, and Marc Lelarge. Correlation Detection in Trees for Planted Graph Alignment. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 74:1-74:8, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ITCS.2022.74

Abstract

Motivated by alignment of correlated sparse random graphs, we study a hypothesis problem of deciding whether two random trees are correlated or not. Based on this correlation detection problem, we propose MPAlign, a message-passing algorithm for graph alignment, which we prove to succeed in polynomial time at partial alignment whenever tree detection is feasible. As a result our analysis of tree detection reveals new ranges of parameters for which partial alignment of sparse random graphs is feasible in polynomial time. We conjecture that the connection between partial graph alignment and tree detection runs deeper, and that the parameter range where tree detection is impossible, which we partially characterize, corresponds to a region where partial graph alignment is hard (not polytime feasible).

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Hypothesis testing and confidence interval computation
  • Mathematics of computing → Max marginal computation
  • Mathematics of computing → Graph algorithms
Keywords
  • inference on graphs
  • hypothesis testing
  • Erdős-Rényi random graphs

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Jessica E. Banks, C. Moore, Joe Neeman, and Praneeth Netrapalli. Information-theoretic thresholds for community detection in sparse networks. ArXiv, abs/1607.01760, 2016. Google Scholar
  2. Béla Bollobás. Random Graphs. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2 edition, 2001. URL: https://doi.org/10.1017/CBO9780511814068.
  3. Charles Bordenave, Marc Lelarge, and Laurent Massoulié. Nonbacktracking spectrum of random graphs: Community detection and nonregular Ramanujan graphs. The Annals of Probability, 46(1):1-71, 2018. URL: https://doi.org/10.1214/16-AOP1142.
  4. Donatello Conte, Pasquale Foggia, Mario Vento, and Carlo Sansone. Thirty Years Of Graph Matching In Pattern Recognition. International Journal of Pattern Recognition and Artificial Intelligence, 18(3):265-298, 2004. URL: https://doi.org/10.1142/S0218001404003228.
  5. Daniel Cullina and Negar Kiyavash. Exact alignment recovery for correlated Erdős-Rényi graphs, 2017. URL: http://arxiv.org/abs/1711.06783.
  6. Daniel Cullina, Negar Kiyavash, Prateek Mittal, and H. Vincent Poor. Partial recovery of Erdős-Rényi graph alignment via k-core alignment. CoRR, abs/1809.03553, 2018. URL: http://arxiv.org/abs/1809.03553.
  7. Jian Ding, Zongming Ma, Yihong Wu, and Jiaming Xu. Efficient random graph matching via degree profiles. arXiv e-prints, page arXiv:1811.07821, November 2018. URL: http://arxiv.org/abs/1811.07821.
  8. Osman Emre Dai, Daniel Cullina, and Negar Kiyavash. Database Alignment with Gaussian Features. arXiv e-prints, page arXiv:1903.01422, March 2019. URL: http://arxiv.org/abs/1903.01422.
  9. Zhou Fan, Cheng Mao, Yihong Wu, and Jiaming Xu. Spectral graph matching and regularized quadratic relaxations II: Erdős-Rényi graphs and universality, 2019. URL: http://arxiv.org/abs/1907.08883.
  10. Luca Ganassali, Marc Lelarge, and Laurent Massoulié. Impossibility of partial recovery in the graph alignment problem, 2021. URL: http://arxiv.org/abs/2102.02685.
  11. Luca Ganassali and Laurent Massoulié. From tree matching to sparse graph alignment. In Jacob Abernethy and Shivani Agarwal, editors, Proceedings of Machine Learning Research, volume 125, pages 1633-1665. PMLR, 09-12 July 2020. URL: http://proceedings.mlr.press/v125/ganassali20a.html.
  12. Luca Ganassali, Laurent Massoulié, and Marc Lelarge. Correlation detection in trees for partial graph alignment. arXiv e-prints, page arXiv:2107.07623, July 2021. URL: http://arxiv.org/abs/2107.07623.
  13. Georgina Hall and Laurent Massoulié. Partial Recovery in the Graph Alignment Problem. arXiv e-prints, page arXiv:2007.00533, July 2020. URL: http://arxiv.org/abs/2007.00533.
  14. Florent Krzakala, Cristopher Moore, Elchanan Mossel, Joe Neeman, Allan Sly, Lenka Zdeborová, and Pan Zhang. Spectral redemption in clustering sparse networks. Proceedings of the National Academy of Sciences, 110(52):20935-20940, 2013. URL: https://doi.org/10.1073/pnas.1312486110.
  15. Konstantin Makarychev, Rajsekar Manokaran, and Maxim Sviridenko. Maximum quadratic assignment problem: Reduction from maximum label cover and lp-based approximation algorithm. CoRR, abs/1403.7721, 2014. URL: http://arxiv.org/abs/1403.7721.
  16. Elchanan Mossel, Joe Neeman, and Allan Sly. Belief propagation, robust reconstruction and optimal recovery of block models. The Annals of Applied Probability, 26(4):2211-2256, 2016. URL: https://doi.org/10.1214/15-AAP1145.
  17. A. Narayanan and V. Shmatikov. Robust de-anonymization of large sparse datasets. In 2008 IEEE Symposium on Security and Privacy (sp 2008), pages 111-125, May 2008. URL: https://doi.org/10.1109/SP.2008.33.
  18. Panos Pardalos, Franz Rendl, and Henry Wolkowicz. The Quadratic Assignment Problem: A Survey and Recent Developments, pages 1-42. DIMACS/AMS, August 1994. URL: https://doi.org/10.1090/dimacs/016/01.
  19. Rohit Singh, Jinbo Xu, and Bonnie Berger. Global alignment of multiple protein interaction networks with application to functional orthology detection. Proceedings of the National Academy of Sciences, 105(35):12763-12768, 2008. URL: https://doi.org/10.1073/pnas.0806627105.
  20. Yihong Wu, Jiaming Xu, and Sophie H. Yu. Settling the sharp reconstruction thresholds of random graph matching. ArXiv, abs/2102.00082, 2021. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact