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

arXiv: https://arxiv.org/abs/2102.06966 · HTML: https://mlsanity.com/paper/2102.06966/

## 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 (most cited first, 26 of 26)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [Fast Graph Representation Learning with PyTorch Geometric](https://mlsanity.com/paper/1903.02428/) (2019)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Interaction Networks for Learning about Objects, Relations and Physics](https://mlsanity.com/paper/1612.00222/) (2016)
- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Generalization and Representational Limits of Graph Neural Networks](https://mlsanity.com/paper/2002.06157/) (2020)
- [What graph neural networks cannot learn: depth vs width](https://mlsanity.com/paper/1907.03199/) (2019)
- [Two Sides of the Same Coin: Heterophily and Oversmoothing in Graph Convolutional Neural Networks](https://mlsanity.com/paper/2102.06462/) (2021)
- [Contextual Stochastic Block Models](https://mlsanity.com/paper/1807.09596/) (2018)
- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [Community detection thresholds and the weak Ramanujan property](https://mlsanity.com/paper/1311.3085/) (2013)
- [Community Detection in Networks with Node Attributes](https://mlsanity.com/paper/1401.7267/) (2014)
- [Stochastic Blockmodels meet Graph Neural Networks](https://mlsanity.com/paper/1905.05738/) (2019)
- [A Proof Of The Block Model Threshold Conjecture](https://mlsanity.com/paper/1311.4115/) (2013)
- [Optimizing Generalized PageRank Methods for Seed-Expansion Community Detection](https://mlsanity.com/paper/1905.10881/) (2019)
- [Covariate-assisted spectral clustering](https://mlsanity.com/paper/1411.2158/) (2014)
- [Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs](https://mlsanity.com/paper/1501.06087/) (2015)
- [Beyond Homophily in Graph Neural Networks: Current Limitations and Effective Designs](https://mlsanity.com/paper/2006.11468/) (2020)
- [Consistency Thresholds for the Planted Bisection Model](https://mlsanity.com/paper/1407.1591/) (2014)
- [Contextual Stochastic Block Model: Sharp Thresholds and Contiguity](https://mlsanity.com/paper/2011.09841/) (2020)
- [The Computer Science and Physics of Community Detection: Landscapes, Phase Transitions, and Hardness](https://mlsanity.com/paper/1702.00467/) (2017)
- [Information-theoretic thresholds for community detection in sparse networks](https://mlsanity.com/paper/1601.02658/) (2016)
- [Block Models and Personalized PageRank](https://mlsanity.com/paper/1607.03483/) (2016)

## Built on by (most cited first, 30 of 70)

- [Is Homophily a Necessity for Graph Neural Networks?](https://mlsanity.com/paper/2106.06134/) (2021)
- [Retrieval-Augmented Generation with Graphs (GraphRAG)](https://mlsanity.com/paper/2501.00309/) (2024)
- [Handling Distribution Shifts on Graphs: An Invariance Perspective](https://mlsanity.com/paper/2202.02466/) (2022)
- [Node Feature Extraction by Self-Supervised Multi-scale Neighborhood Prediction](https://mlsanity.com/paper/2111.00064/) (2021)
- [Out-Of-Distribution Generalization on Graphs: A Survey](https://mlsanity.com/paper/2202.07987/) (2022)
- [Subgroup Generalization and Fairness of Graph Neural Networks](https://mlsanity.com/paper/2106.15535/) (2021)
- [A Non-Asymptotic Analysis of Oversmoothing in Graph Neural Networks](https://mlsanity.com/paper/2212.10701/) (2022)
- [Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPs](https://mlsanity.com/paper/2212.09034/) (2022)
- [Demystifying Structural Disparity in Graph Neural Networks: Can One Size Fit All?](https://mlsanity.com/paper/2306.01323/) (2023)
- [Mind the Label Shift of Augmentation-based Graph OOD Generalization](https://mlsanity.com/paper/2303.14859/) (2023)
- [Graph Attention Retrospective](https://mlsanity.com/paper/2202.13060/) (2022)
- [Effects of Graph Convolutions in Multi-layer Networks](https://mlsanity.com/paper/2204.09297/) (2022)
- [Towards Deep Attention in Graph Neural Networks: Problems and Remedies](https://mlsanity.com/paper/2306.02376/) (2023)
- [Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspective](https://mlsanity.com/paper/2207.11311/) (2022)
- [Revisiting Robustness in Graph Machine Learning](https://mlsanity.com/paper/2305.00851/) (2023)
- [Graph Learning under Distribution Shifts: A Comprehensive Survey on Domain Adaptation, Out-of-distribution, and Continual Learning](https://mlsanity.com/paper/2402.16374/) (2024)
- [Node-wise Filtering in Graph Neural Networks: A Mixture of Experts Approach](https://mlsanity.com/paper/2406.03464/) (2024)
- [Augmentation-Free Graph Contrastive Learning with Performance Guarantee](https://mlsanity.com/paper/2204.04874/) (2022)
- [Understanding Heterophily for Graph Neural Networks](https://mlsanity.com/paper/2401.09125/) (2024)
- [Single-Pass Contrastive Learning Can Work for Both Homophilic and Heterophilic Graph](https://mlsanity.com/paper/2211.10890/) (2022)
- [Explaining and Adapting Graph Conditional Shift](https://mlsanity.com/paper/2306.03256/) (2023)
- [Homophily modulates double descent generalization in graph convolution networks](https://mlsanity.com/paper/2212.13069/) (2022)
- [Optimality of Message-Passing Architectures for Sparse Graphs](https://mlsanity.com/paper/2305.10391/) (2023)
- [Weisfeiler-Leman at the margin: When more expressivity matters](https://mlsanity.com/paper/2402.07568/) (2024)
- [What functions can Graph Neural Networks compute on random graphs? The role of Positional Encoding](https://mlsanity.com/paper/2305.14814/) (2023)
- [Optimal Inference in Contextual Stochastic Block Models](https://mlsanity.com/paper/2306.07948/) (2023)
- [Quantifying the Optimization and Generalization Advantages of Graph Neural Networks Over Multilayer Perceptrons](https://mlsanity.com/paper/2306.13926/) (2023)
- [Joint Graph Rewiring and Feature Denoising via Spectral Resonance](https://mlsanity.com/paper/2408.07191/) (2024)
- [A Metadata-Driven Approach to Understand Graph Neural Networks](https://mlsanity.com/paper/2310.19263/) (2023)
- [Finding Diverse and Predictable Subgraphs for Graph Domain Generalization](https://mlsanity.com/paper/2206.09345/) (2022)

## 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.