Research map / Graph learning / Graph algorithms and clustering
Harnessing Multiple Correlated Networks for Exact Community Recovery
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Determines the exact information-theoretic threshold for exact community recovery and exact graph matching from K correlated edge-subsampled two-community SBMs, showing a regime where K graphs suffice though no K-1 graphs and no pairwise matching suffice.
Problem
Exact community recovery from multiple correlated stochastic block models with two balanced communities, where the latent vertex correspondences between graphs are unknown; prior work only solved the two-graph case.
Approach
Combines pairwise k-core matchings across all K(K-1)/2 graph pairs and aggregates information through union graphs over "good" vertices matched in at least two matchings; uses a meta-graph connectivity argument and a Łuczak-type expansion adapted to decouple dependencies between matchings, yielding tight thresholds for K>=3.
Key results
- Exact community recovery from K correlated SBMs is possible iff (1-(1-s)^K) D_ch(a,b) > 1 and s(1-(1-s)^{K-1}) d_conn(a,b) + s(1-s)^{K-1} D_ch(a,b) > 1 (tight threshold for any constant K).
- Exact graph matching threshold from K correlated SBMs is s(1-(1-s)^{K-1}) d_conn(a,b) = 1, which is strictly weaker than the pairwise threshold s^2 d_conn = 1 for K>2.
- For every K>=3 there is a region where exact community recovery is possible from K graphs but impossible from any K-1 graphs and no latent matching is exactly recoverable.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| add the Kth correlated graph when K ≥ 3 | Exact community recovery in correlated SBMs · K correlated SBMs | exact community recovery | Helped |
| combine information across K graphs using multiple partial matchings | Exact community recovery in correlated SBMs · K correlated SBMs | exact community recovery | Helped |
| use K correlated graphs rather than only two | Exact graph matching · K correlated SBMs | exact graph matching | Helped |
Surprising findings
- Exact graph matching becomes possible with K>=3 graphs in regimes where pairwise exact matching between any two graphs is impossible.
Limitations
- The recovery algorithm relies on k-core matching that enumerates all permutations, so it is not computationally efficient.
- Analysis restricted to the two-balanced-community SBM in the logarithmic degree regime and the specific subsampling correlation model.
Experimental setup
Metrics: exact recovery probability (overlap = 1) threshold conditions
Baselines: Gaudio, Rácz, and Sridhar (COLT 2022) two-graph threshold pairwise exact graph matching threshold s^2 d_conn > 1 (Rácz and Sridhar)
Builds on: Gaudio, Rácz, and Sridhar (COLT 2022) two-graph community recovery threshold k-core matching (Cullina, Kiyavash, Mittal, Poor) Chernoff-Hellinger divergence exact recovery threshold (Abbe, Bandeira, Hall / M Łuczak expansion
Closest papers by meaning
- Correlated Stochastic Block Models: Exact Graph Matching with Applications to Recovering Communities (NeurIPS 2021 · similarity 0.97)
- Efficient Graph Matching for Correlated Stochastic Block Models (NeurIPS 2024 · similarity 0.93)
- Exact Community Recovery under Side Information: Optimality of Spectral Algorithms (ICLR 2025 · similarity 0.91)
- Query-Limited Community Recovery in Stochastic Block Models (NeurIPS 2026 · similarity 0.90)
- Differentially private exact recovery for stochastic block models (ICML 2024 · similarity 0.88)
- Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model (ICML 2025 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.