Research map / Graph learning / Graph algorithms and clustering
Efficient Graph Matching for Correlated Stochastic Block Models
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.
Gives the first polynomial-time algorithm for exact graph matching in two-community correlated SBMs in the logarithmic-degree regime when s^2 > Otter's constant alpha (~0.338), extending chandelier-based matching and enabling efficient exact community recovery from two graphs.
Problem
Efficient average-case graph matching between two correlated stochastic block models with two balanced communities in the logarithmic average degree regime, where exact matching is information-theoretically possible but no efficient algorithm was known.
Approach
Extends the chandelier signed-subgraph-count matching of Mao, Wu, Xu, and Yu to correlated SBMs by centralizing adjacency matrices using estimated community labels, controls the resulting estimation errors, and boosts almost-exact matching to exact matching via seeded common-neighbor matching.
Key results
- Efficient almost-exact matching of (1-o(1))n vertices with high probability whenever s^2 > alpha ≈ 0.338 in the logarithmic degree regime.
- Extends to efficient exact matching whenever s^2(a+b)/2 > 1, the information-theoretic threshold, resolving an open problem of Racz and Sridhar.
- Gives efficient exact community recovery from two correlated graphs in regimes where it is impossible from a single graph.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use signed chandelier counts with estimated community labels for vertex matching | Correlated SBM graph matching · Correlated SBM, logarithmic average degree | matching recovery | Helped |
| Boost almost exact matching with seeded graph matching | Chandelier matching algorithm · Correlated SBM, logarithmic average degree | matching recovery | Helped |
| Combine matched correlated graphs into a union graph for community recovery | Correlated SBM community recovery · Correlated SBM, logarithmic average degree | community recovery | Helped |
Limitations
- Requires s^2 > alpha (~0.338), conjectured necessary; gap to information-theoretic threshold s^2(a+b)/2 > 1 remains.
- Analysis restricted to logarithmic average degree and two balanced communities.
- Community recovery error rate must be polynomially small, requiring diverging degree; sparser regimes not covered.
Experimental setup
Metrics: fraction of correctly matched vertices exact matching probability
Baselines: Yang et al. binary tree counting for correlated SBMs Racz and Sridhar information-theoretic matching
Builds on: Mao, Wu, Xu, Yu chandelier matching (STOC 2023) Mossel, Neeman, Sly community recovery Racz and Sridhar exact matching threshold seeded graph matching
Closest papers by meaning
- Harnessing Multiple Correlated Networks for Exact Community Recovery (NeurIPS 2024 · similarity 0.93)
- From Your Block to Our Block: How to Find Shared Structure Between Stochastic Block Models over Multiple Graphs (AAAI 2025 · similarity 0.89)
- Query-Limited Community Recovery in Stochastic Block Models (NeurIPS 2026 · similarity 0.89)
- Exact Community Recovery under Side Information: Optimality of Spectral Algorithms (ICLR 2025 · similarity 0.88)
- Network two-sample test for block models (NeurIPS 2025 · similarity 0.88)
- Differentially private exact recovery for stochastic block models (ICML 2024 · similarity 0.88)
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.