Research map / Graph learning / Graph algorithms and clustering
Optimal Exact Recovery in Semi-Supervised Learning: A Study of Spectral Methods and Graph Convolutional Networks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Combine the graph and feature spectral estimators in the PCA spectral estimator | Semi-supervised CSBM · CSBM with q_m \gtrsim \log(m) | exact recovery probability: 1 - m^{1 - I_{\tau}} | Helped |
| Use the modified estimator with training-label quadratic forms and the feature-derived graph estimate | PCA spectral estimator · Semi-supervised CSBM with 1 \ll q_m \ll \log(m) | expected mismatch ratio exponent: \limsup_{m \to \infty} q^{-1}_m \log \E \psi_m \big(\by_{\sU}, \sign(\widetilde{\by}_{\mathrm{PCA}}) \big) \leq - I(a_{\ | Helped |
| Add the optimal weighted self-loop (ablation) | Linear ridge regression on GCN · Semi-supervised CSBM | exact recovery probability: I(a_\tau,b_\tau, 0 )>1; I(a_\tau,b_\tau,c_\tau)>1 | Helped |
| Set the self-loop weight to zero instead of the optimal weighted value (ablation) | Linear ridge regression on GCN · Semi-supervised CSBM | exact recovery probability: I(a_\tau,b_\tau, 0 )>1; I(a_\tau,b_\tau,c_\tau)>1 | Hurt |
| Increase feature signal strength c_{\tau} | Semi-supervised CSBM · CSBM exact recovery | exact recovery difficulty | Helped |
| Use gradient-based training with a learned feature direction and selected self-loop parameter | GCN · Semi-supervised CSBM | exact recovery probability: I(a_\tau, b_\tau, c_\tau )>1 | Helped |
| Attempt exact recovery below the information-theoretic threshold | Any algorithm · Semi-supervised CSBM with q_m = \log(m) | exact recovery: I(a_{\tau}, b_{\tau}, c_{\tau}) < 1 | Hurt |
Closest papers by meaning
- Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization (ICML 2021 · similarity 0.90)
- Collaborative Graph Convolutional Networks: Unsupervised Learning Meets Semi-Supervised Learning (AAAI 2020 · similarity 0.89)
- LEARNING GUARANTEES FOR GRAPH CONVOLUTIONAL NETWORKS ON THE STOCHASTIC BLOCK MODEL (ICLR 2022 · similarity 0.88)
- Unsupervised Neighborhood Propagation Kernel Layers for Semi-supervised Node Classification (AAAI 2024 · similarity 0.87)
- Analysis of Corrected Graph Convolutions (NeurIPS 2024 · similarity 0.87)
- Exact Community Recovery under Side Information: Optimality of Spectral Algorithms (ICLR 2025 · similarity 0.86)
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.