Research map / Learning theory and algorithms / Clustering
Exact Community Recovery under Side Information: Optimality of Spectral Algorithms
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.
Designs a single-stage spectral algorithm (top eigenvectors of the observation matrix plus side-information log-likelihood ratios) for exact recovery in two-community block models with node side information, shown to match the information-theoretic threshold via genie-aided estimators.
Problem
Exact community recovery in two-community block models (Gaussian rank-one spike and Bernoulli SBM) with node-attributed side information, where efficient algorithms achieving the information-theoretic threshold were previously lacking beyond special cases.
Approach
Form a spectral score from the top eigenvectors of A (weighted by coefficients derived from the model) and add the side-information log-likelihood ratio; entrywise eigenvector analysis shows this approximates the genie-aided score in l-infinity, so sign thresholding mimics the genie and attains the MAP/IT threshold without a clean-up stage.
Key results
- Spectral algorithm achieves exact recovery whenever I*>1 for ROS and SBM with side information (Theorems on optimality), matching the MAP information-theoretic threshold.
- For Z2-synchronization with n=300 and N=50 trials, simulations over (beta, a) grids match the theoretical BEC/BSC side-information thresholds.
- Runtime is nearly linear: Otilde(n) for SBM and Otilde(n^2) for ROS.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the spectral algorithm to approximate genie scores and threshold them | ROS · ROS | exact recovery: I^*>1 | Helped |
| Use the spectral algorithm to approximate genie scores and threshold them | SBM · SBM | exact recovery: I^*>1 | Helped |
| Add Gaussian features as side information | Exact recovery under ROS or SBM · ROS or SBM with Gaussian features | information-theoretic threshold: L_{\mathsf{GF}}(t)=L_{\text{no-SI}}(t)+\frac{t(1-t) \norm{\boldsymbol{\beta}_{+}- \boldsymbol{\beta}_{-}}_2^2}{ 2 \sigma | Helped |
| Add BEC side information | Exact recovery under ROS or SBM · ROS or SBM with BEC | information-theoretic threshold: L_{\mathsf{BEC}}(t)=L_{\text{no-SI}}(t)+\beta | Helped |
| Add BSC side information | Exact recovery under ROS or SBM · ROS or SBM with BSC | information-theoretic threshold: L_{\mathsf{BSC}}(t)=L_{\text{no-SI}}(t)+\beta \min\{t,1-t\} | Helped |
| Use side-information labels directly as a proxy for the genie instead of using the spectral method | Degree-profiling algorithm · Exact recovery with weak or absent side information | exact recovery | Hurt |
Surprising findings
- Unlike the censored-edge variant, a single adjacency matrix suffices for optimality in the general uncensored SBM, without two matrix representations.
- Degree-profiling (trusting side information labels directly) can fail when side information is weak or absent, whereas the spectral algorithm does not.
Limitations
- Analysis restricted to two communities and to Gaussian (ROS) or Bernoulli (SBM) pairwise models; more communities left to future work.
- Model parameters assumed known; estimation of parameters (especially BSC alpha) unclear for preserving optimality.
- Degenerate cases with multiple eigenvalues are not handled for more than two blocks.
Experimental setup
Metrics: exact recovery success rate information-theoretic threshold I*
Baselines: MAP estimator degree profiling two-stage algorithms
Builds on: Dreveton et al. 2024 information-theoretic limits with side information entrywise eigenvector analysis Abbe-Fan-Wang-Zhong spectral exact recovery
Closest papers by meaning
- Harnessing Multiple Correlated Networks for Exact Community Recovery (NeurIPS 2024 · similarity 0.91)
- Query-Limited Community Recovery in Stochastic Block Models (NeurIPS 2026 · similarity 0.89)
- On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models (NeurIPS 2024 · similarity 0.89)
- Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model (ICML 2025 · similarity 0.89)
- Differentially private exact recovery for stochastic block models (ICML 2024 · similarity 0.89)
- Efficient Graph Matching for Correlated Stochastic Block Models (NeurIPS 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.