mlsanityData to 7 Oct 2026

Optimal Exact Recovery in Semi-Supervised Learning: A Study of Spectral Methods and Graph Convolutional Networks

arXiv 2412.13754 ↗First posted 18 Dec 2024cs.LG math.PR math.STcited by 0

Not on the map. Why?

Abstract (arXiv)

We delve into the challenge of semi-supervised node classification on the Contextual Stochastic Block Model (CSBM) dataset. Here, nodes from the two-cluster Stochastic Block Model (SBM) are coupled with feature vectors, which are derived from a Gaussian Mixture Model (GMM) that corresponds to their respective node labels. With only a subset of the CSBM node labels accessible for training, our primary objective becomes the accurate classification of the remaining nodes. Venturing into the transductive learning landscape, we, for the first time, pinpoint the information-theoretical threshold for the exact recovery of all test nodes in CSBM. Concurrently, we design an optimal spectral estimator inspired by Principal Component Analysis (PCA) with the training labels and essential data from both the adjacency matrix and feature vectors. We also evaluate the efficacy of graph ridge regression and Graph Convolutional Networks (GCN) on this synthetic dataset. Our findings underscore that graph ridge regression and GCN possess the ability to achieve the information threshold of exact recovery in a manner akin to the optimal estimator when using the optimal weighted self-loops. This highlights the potential role of feature learning in augmenting the proficiency of GCN, especially in the realm of semi-supervised learning.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 37 of its 50 references that are in the map. First posted on arXiv 18 Dec 2024.

Builds on

37 of 50 references.

References · 37

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2019Simplifying Graph Convolutional Networkscited by 1,470
  3. 2020LightGCN: Simplifying and Powering Graph Convolution Network for Recommendationcited by 1,134
  4. 2018Pitfalls of Graph Neural Network Evaluationcited by 994
  5. 2016Revisiting Semi-Supervised Learning with Graph Embeddingscited by 970
  6. 2017Deep Gaussian Embedding of Graphs: Unsupervised Inductive Learning via Rankingcited by 332
  7. 2017Community Detection and Stochastic Block Modelscited by 317
  8. 2021Is Homophily a Necessity for Graph Neural Networks?cited by 182
  9. 2022Neural Networks can Learn Representations with Gradient Descentcited by 161
  10. 2022High-dimensional Asymptotics of Feature Learning: How One Gradient Step Improves the Representationcited by 146
  11. 2018Contextual Stochastic Block Modelscited by 134
  12. 2014Exact Recovery in the Stochastic Block Modelcited by 77
25 more
  1. 2021Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalizationcited by 70
  2. 2021Learning Theory Can (Sometimes) Explain Generalisation in Graph Neural Networkscited by 51
  3. 2022A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networkscited by 49
  4. 2023Towards Understanding the Generalization of Graph Neural Networkscited by 41
  5. 2017Efficient and Adaptive Linear Regression in Semi-Supervised Settingscited by 29
  6. 2022Graph Attention Retrospectivecited by 24
  7. 2022Effects of Graph Convolutions in Multi-layer Networkscited by 24
  8. 2020Contextual Stochastic Block Model: Sharp Thresholds and Contiguitycited by 22
  9. 2018Stochastic Block Model for Hypergraphs: Statistical limits and a semidefinite programming approachcited by 20
  10. 2022Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspectivecited by 19
  11. 2017Supervised Community Detection with Line Graph Neural Networkscited by 18
  12. 2022An Information-theoretical Approach to Semi-supervised Learning under Covariate-shiftcited by 18
  13. 2019Asymptotic Bayes risk for Gaussian mixture in a semi-supervised settingcited by 15
  14. 2018Semi-supervised Inference for Explained Variance in High-dimensional Linear Regression and Its Applicationscited by 14
  15. 2022Homophily modulates double descent generalization in graph convolution networkscited by 13
  16. 2023Optimality of Message-Passing Architectures for Sparse Graphscited by 13
  17. 2023Quantifying the Optimization and Generalization Advantages of Graph Neural Networks Over Multilayer Perceptronscited by 12
  18. 2021Information-Theoretic Characterization of the Generalization Error for Iterative Semi-Supervised Learningcited by 11
  19. 2023Optimal Inference in Contextual Stochastic Block Modelscited by 11
  20. 2022On Classification Thresholds for Graph Attention with Edge Featurescited by 5
  21. 2023Asymptotic Bayes risk of semi-supervised multitask learning on Gaussian mixturecited by 4
  22. 2024Asymptotic generalization error of a single-layer graph convolutional networkcited by 3
  23. 2023Optimal and exact recovery on the general nonuniform Hypergraph Stochastic Block Modelcited by 2
  24. 2023Information-Theoretic Limits and Strong Consistency on Binary Non-uniform Hypergraph Stochastic Block Modelscited by 1
  25. 2023The Self-Loop Paradox: Investigating the Impact of Self-Loops on Graph Neural Networkscited by 1

Built on by

Not cited yet.