License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2022.74
URN: urn:nbn:de:0030-drops-156709
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15670/
Ganassali, Luca ;
Massoulié, Laurent ;
Lelarge, Marc
Correlation Detection in Trees for Planted Graph Alignment
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).
BibTeX - Entry
@InProceedings{ganassali_et_al:LIPIcs.ITCS.2022.74,
author = {Ganassali, Luca and Massouli\'{e}, Laurent and Lelarge, Marc},
title = {{Correlation Detection in Trees for Planted Graph Alignment}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {74:1--74:8},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-217-4},
ISSN = {1868-8969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15670},
URN = {urn:nbn:de:0030-drops-156709},
doi = {10.4230/LIPIcs.ITCS.2022.74},
annote = {Keywords: inference on graphs, hypothesis testing, Erd\H{o}s-R\'{e}nyi random graphs}
}
Keywords: |
|
inference on graphs, hypothesis testing, Erdős-Rényi random graphs |
Collection: |
|
13th Innovations in Theoretical Computer Science Conference (ITCS 2022) |
Issue Date: |
|
2022 |
Date of publication: |
|
25.01.2022 |