# A Unifying Generative Model for Graph Learning Algorithms: Label Propagation, Graph Convolutions, and Combinations

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

## Key facts

- Cited by 18 papers in the map (data through 14 Oct 2026).
- Builds on 55 of its 132 references that are in the map.
- First posted on arXiv 19 Jan 2021.

## Builds on (most cited first, 30 of 55)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Simplifying Graph Convolutional Networks](https://mlsanity.com/paper/1902.07153/) (2019)
- [Deeper Insights into Graph Convolutional Networks for Semi-Supervised Learning](https://mlsanity.com/paper/1801.07606/) (2018)
- [Predict then Propagate: Graph Neural Networks meet Personalized PageRank](https://mlsanity.com/paper/1810.05997/) (2018)
- [Adaptive Universal Generalized PageRank Graph Neural Network](https://mlsanity.com/paper/2006.07988/) (2020)
- [Multi-scale Attributed Node Embedding](https://mlsanity.com/paper/1909.13021/) (2019)
- [Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification](https://mlsanity.com/paper/2009.03509/) (2020)
- [Representation Learning on Graphs: Methods and Applications](https://mlsanity.com/paper/1709.05584/) (2017)
- [EvolveGCN: Evolving Graph Convolutional Networks for Dynamic Graphs](https://mlsanity.com/paper/1902.10191/) (2019)
- [Graph Signal Processing: Overview, Challenges and Applications](https://mlsanity.com/paper/1712.00468/) (2017)
- [PairNorm: Tackling Oversmoothing in GNNs](https://mlsanity.com/paper/1909.12223/) (2019)
- [Towards Deeper Graph Neural Networks](https://mlsanity.com/paper/2007.09296/) (2020)
- [SIGN: Scalable Inception Graph Neural Networks](https://mlsanity.com/paper/2004.11198/) (2020)
- [Position-aware Graph Neural Networks](https://mlsanity.com/paper/1906.04817/) (2019)
- [Combining Label Propagation and Simple Models Out-performs Graph Neural Networks](https://mlsanity.com/paper/2010.13993/) (2020)
- [Scaling Graph Neural Networks with Approximate PageRank](https://mlsanity.com/paper/2007.01570/) (2020)
- [Higher-order organization of complex networks](https://mlsanity.com/paper/1612.08447/) (2016)
- [A Unified View on Graph Neural Networks as Graph Signal Denoising](https://mlsanity.com/paper/2010.01777/) (2020)
- [Unifying Graph Convolutional Neural Networks and Label Propagation](https://mlsanity.com/paper/2002.06755/) (2020)
- [Simplicial Closure and higher-order link prediction](https://mlsanity.com/paper/1802.06916/) (2018)
- [Random Walks on Simplicial Complexes and the normalized Hodge 1-Laplacian](https://mlsanity.com/paper/1807.05044/) (2018)
- [GMNN: Graph Markov Neural Networks](https://mlsanity.com/paper/1905.06214/) (2019)
- [Label Efficient Semi-Supervised Learning via Graph Filtering](https://mlsanity.com/paper/1901.09993/) (2019)
- [Design of graph filters and filterbanks](https://mlsanity.com/paper/1711.02046/) (2017)
- [Nonlinear Higher-Order Label Spreading](https://mlsanity.com/paper/2006.04762/) (2020)
- [Algorithms for Lipschitz Learning on Graphs](https://mlsanity.com/paper/1505.00290/) (2015)
- [Tensor Spectral Clustering for Partitioning Higher-order Network Structures](https://mlsanity.com/paper/1502.05058/) (2015)
- [The Spacey Random Walk: a Stochastic Process for Higher-order Data](https://mlsanity.com/paper/1602.02102/) (2016)

## Built on by (most cited first, 18 of 18)

- [Is Homophily a Necessity for Graph Neural Networks?](https://mlsanity.com/paper/2106.06134/) (2021)
- [Generalised Implicit Neural Representations](https://mlsanity.com/paper/2205.15674/) (2022)
- [Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspective](https://mlsanity.com/paper/2207.11311/) (2022)
- [LazyGNN: Large-Scale Graph Neural Networks via Lazy Propagation](https://mlsanity.com/paper/2302.01503/) (2023)
- [A nonlinear diffusion method for semi-supervised learning on hypergraphs](https://mlsanity.com/paper/2103.14867/) (2021)
- [Why Propagate Alone? Parallel Use of Labels and Features on Graphs](https://mlsanity.com/paper/2110.07190/) (2021)
- [Graph-Based Methods for Discrete Choice](https://mlsanity.com/paper/2205.11365/) (2022)
- [A Markov Random Field model for Hypergraph-based Machine Learning](https://mlsanity.com/paper/2308.14172/) (2023)
- [How Graph Neural Networks Learn: Lessons from Training Dynamics](https://mlsanity.com/paper/2310.05105/) (2023)
- [Graph Belief Propagation Networks](https://mlsanity.com/paper/2106.03033/) (2021)
- [How Powerful is Implicit Denoising in Graph Neural Networks](https://mlsanity.com/paper/2209.14514/) (2022)
- [Heterogeneous Graph Structure Learning through the Lens of Data-generating Processes](https://mlsanity.com/paper/2503.08760/) (2025)
- [Learning Label Initialization for Time-Dependent Harmonic Extension](https://mlsanity.com/paper/2205.01358/) (2022)
- [A Robust Stacking Framework for Training Deep Graph Models with Multifaceted Node Features](https://mlsanity.com/paper/2206.08473/) (2022)
- [Random Graph-Based Neuromorphic Learning with a Layer-Weaken Structure](https://mlsanity.com/paper/2111.08888/) (2021)
- [Nonlinear Correct and Smooth for Semi-Supervised Learning](https://mlsanity.com/paper/2310.05757/) (2023)
- [Graph Adversarial Diffusion Convolution](https://mlsanity.com/paper/2406.02059/) (2024)
- [iN2V: Bringing Transductive Node Embeddings to Inductive Graphs](https://mlsanity.com/paper/2506.05039/) (2025)

## Abstract (arXiv)

Semi-supervised learning on graphs is a widely applicable problem in network science and machine learning. Two standard algorithms -- label propagation and graph neural networks -- both operate by repeatedly passing information along edges, the former by passing labels and the latter by passing node features, modulated by neural networks. These two types of algorithms have largely developed separately, and there is little understanding about the structure of network data that would make one of these approaches work particularly well compared to the other or when the approaches can be meaningfully combined. Here, we develop a Markov random field model for the data generation process of node attributes, based on correlations of attributes on and between vertices, that motivates and unifies these algorithmic approaches. We show that label propagation, a linearized graph convolutional network, and their combination can all be derived as conditional expectations under our model, when conditioning on different attributes. In addition, the data model highlights deficiencies in existing graph neural networks (while producing new algorithmic solutions), serves as a rigorous statistical framework for understanding graph learning issues such as over-smoothing, creates a testbed for evaluating inductive learning performance, and provides a way to sample graphs attributes that resemble empirical data. We also find that a new algorithm derived from our data generation model, which we call a Linear Graph Convolution, performs extremely well in practice on empirical data, and provide theoretical justification for why this is the case.