mlsanityData to 14 Oct 2026

Graph Convolution for Semi-Supervised Classification: Improved Linear Separability and Out-of-Distribution Generalization

arXiv 2102.06966 ↗First posted 13 Feb 2021cs.LG stat.MLcited by 70

Not on the map. Why?

Abstract (arXiv)

Recently there has been increased interest in semi-supervised classification in the presence of graphical information. A new class of learning models has emerged that relies, at its most basic level, on classifying the data after first applying a graph convolution. To understand the merits of this approach, we study the classification of a mixture of Gaussians, where the data corresponds to the node attributes of a stochastic block model. We show that graph convolution extends the regime in which the data is linearly separable by a factor of roughly 1/√D, where D is the expected degree of a node, as compared to the mixture model data on its own. Furthermore, we find that the linear classifier obtained by minimizing the cross-entropy loss after the graph convolution generalizes to out-of-distribution data where the unseen data can have different intra- and inter-class edge probabilities from the training data.

Key facts. Cited by 70 papers in the map (data through 14 Oct 2026). Builds on 26 of its 47 references that are in the map. First posted on arXiv 13 Feb 2021.

Builds on

26 of 47 references.

References · 26

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Inductive Representation Learning on Large Graphscited by 6,320
  3. 2018How Powerful are Graph Neural Networks?cited by 4,393
  4. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  5. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,434
  6. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,138
  7. 2016Interaction Networks for Learning about Objects, Relations and Physicscited by 509
  8. 2017Community Detection and Stochastic Block Modelscited by 319
  9. 2020Generalization and Representational Limits of Graph Neural Networkscited by 218
  10. 2019What graph neural networks cannot learn: depth vs widthcited by 201
  11. 2021Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networkscited by 182
  12. 2018Contextual Stochastic Block Modelscited by 134
14 more
  1. 2014Exact Recovery in the Stochastic Block Modelcited by 78
  2. 2013Community detection thresholds and the weak Ramanujan propertycited by 47
  3. 2014Community Detection in Networks with Node Attributescited by 44
  4. 2019Stochastic Blockmodels meet Graph Neural Networkscited by 39
  5. 2013A Proof Of The Block Model Threshold Conjecturecited by 36
  6. 2019Optimizing Generalized PageRank Methods for Seed-Expansion Community Detectioncited by 35
  7. 2014Covariate-assisted spectral clusteringcited by 29
  8. 2015Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphscited by 26
  9. 2020Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designscited by 25
  10. 2014Consistency Thresholds for the Planted Bisection Modelcited by 24
  11. 2020Contextual Stochastic Block Model: Sharp Thresholds and Contiguitycited by 22
  12. 2017The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardnesscited by 20
  13. 2016Information-theoretic thresholds for community detection in sparse networkscited by 17
  14. 2016Block Models and Personalized PageRankcited by 7

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 3; 2022: 15; 2023: 18; 2024: 21; 2025: 8; 2026: 5.

70 papers.

Sort:

By area:

  1. 2021Is Homophily a Necessity for Graph Neural Networks?cited by 182
  2. 2024Retrieval-Augmented Generation with Graphs (GraphRAG)cited by 172
  3. 2022Handling Distribution Shifts on Graphs: An Invariance Perspectivecited by 164
  4. 2021Node Feature Extraction by Self-Supervised Multi-scale Neighborhood Predictioncited by 138
  5. 2022Out-Of-Distribution Generalization on Graphs: A Surveycited by 97
  6. 2021Subgroup Generalization and Fairness of Graph Neural Networkscited by 69
  7. 2022A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networkscited by 49
  8. 2022Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPscited by 42
  9. 2023Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?cited by 41
  10. 2023Mind the Label Shift of Augmentation-based Graph OOD Generalizationcited by 34
  11. 2022Graph Attention Retrospectivecited by 24
  12. 2022Effects of Graph Convolutions in Multi-layer Networkscited by 24
38 more
  1. 2023Towards Deep Attention in Graph Neural Networks: Problems and Remediescited by 24
  2. 2022Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspectivecited by 19
  3. 2023Revisiting Robustness in Graph Machine Learningcited by 19
  4. 2024Graph Learning under Distribution Shifts: A Comprehensive Survey on Domain Adaptation, Out-of-distribution, and Continual Learningcited by 18
  5. 2024Node-wise Filtering in Graph Neural Networks: A Mixture of Experts Approachcited by 17
  6. 2022Augmentation-Free Graph Contrastive Learning with Performance Guaranteecited by 16
  7. 2024Understanding Heterophily for Graph Neural Networkscited by 15
  8. 2022Single-Pass Contrastive Learning Can Work for Both Homophilic and Heterophilic Graphcited by 14
  9. 2023Explaining and Adapting Graph Conditional Shiftcited by 14
  10. 2022Homophily modulates double descent generalization in graph convolution networkscited by 13
  11. 2023Optimality of Message-Passing Architectures for Sparse Graphscited by 13
  12. 2024Weisfeiler-Leman at the margin: When more expressivity matterscited by 13
  13. 2023What functions can Graph Neural Networks compute on random graphs? The role of Positional Encodingcited by 12
  14. 2023Optimal Inference in Contextual Stochastic Block Modelscited by 12
  15. 2023Quantifying the Optimization and Generalization Advantages of Graph Neural Networks Over Multilayer Perceptronscited by 12
  16. 2024Joint Graph Rewiring and Feature Denoising via Spectral Resonancecited by 12
  17. 2023A Metadata-Driven Approach to Understand Graph Neural Networkscited by 10
  18. 2022Finding Diverse and Predictable Subgraphs for Graph Domain Generalizationcited by 9
  19. 2024Feature Distribution on Graph Topology Mediates the Effect of Graph Convolution: Homophily Perspectivecited by 9
  20. 2022Learnable Graph Convolutional Attention Networkscited by 8
  21. 2023When Do Graph Neural Networks Help with Node Classification? Investigating the Impact of Homophily Principle on Node Distinguishabilitycited by 7
  22. 2026Query-Aware Flow Diffusion for Graph-Based RAG with Retrieval Guaranteescited by 7
  23. 2024Few-Shot Causal Representation Learning for Out-of-Distribution Generalization on Heterogeneous Graphscited by 6
  24. 2024Deeper Insights into Deep Graph Convolutional Networks: Stability and Generalizationcited by 6
  25. 2022On Classification Thresholds for Graph Attention with Edge Featurescited by 5
  26. 2022A Spectral Analysis of Graph Neural Networks on Dense and Sparse Graphscited by 5
  27. 2024Generalization of Graph Neural Networks is Robust to Model Mismatchcited by 4
  28. 2024Mixture of Experts for Node Classificationcited by 4
  29. 2023How Graph Neural Networks Learn: Lessons from Training Dynamicscited by 3
  30. 2024Asymptotic generalization error of a single-layer graph convolutional networkcited by 3
  31. 2024On the Topology Awareness and Generalization Performance of Graph Neural Networkscited by 3
  32. 2025Unveiling Mode Connectivity in Graph Neural Networkscited by 3
  33. 2022Tackling Provably Hard Representative Selection via Graph Neural Networkscited by 2
  34. 2023Improving Signed Propagation for Graph Neural Networks in Multi-Class Environmentscited by 2
  35. 2023Information-Theoretic Limits and Strong Consistency on Binary Non-uniform Hypergraph Stochastic Block Modelscited by 2
  36. 2024Statistical Guarantees for Link Prediction using Graph Neural Networkscited by 2
  37. 2024Analysis of Corrected Graph Convolutionscited by 2
  38. 2024Graph Attention is Not Always Beneficial: A Theoretical Analysis of Graph Attention Mechanisms via Contextual Stochastic Block Modelscited by 2

50 most cited of 70 All 70 (JSON)