Reproduce “Statistical-computational gap in multiple Gaussian graph alignment” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Bertrand Even, Luca Ganassali
Researchers from Université Paris-Saclay, CNRS, and Inria precisely characterized the information-theoretic and computational limits for aligning multiple Gaussian graphs, demonstrating that increasing the number of graphs offers statistical gains for partial recovery but no significant computational advantage. They also established that the "all-or-nothing" recovery phenomenon, where non-trivial recovery implies perfect recovery, vanishes when the number of graphs grows with the number of nodes.
Key insights
- The "all-or-nothing" phenomenon, observed in fixed-p graph alignment, vanishes when the number of graphs ($p$) grows rapidly with $n$, creating an intermediate regime where partial recovery is possible but perfect recovery is not.
- Computational hardness for multiple Gaussian graph alignment persists and remains largely equivalent to aligning two graphs, even with the availability of many more graphs, attributed to inherent "bi-dimensional combinatorial structures."
- Information-theoretic thresholds for partial recovery improve with more graphs ($p$) up to a point, saturating at $ ho acksim rac{\log(n)}{n}$ when $p$ is large ($p \gtrsim n/\log(n)$).
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.