# On Graph Neural Networks versus Graph-Augmented MLPs

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

## Key facts

- Cited by 30 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Oct 2020.

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

- [How Powerful are Spectral Graph Neural Networks](https://mlsanity.com/paper/2205.11172/) (2022)
- [Data Augmentation for Deep Graph Learning: A Survey](https://mlsanity.com/paper/2202.08235/) (2022)
- [Breaking the Limit of Graph Neural Networks by Improving the Assortativity of Graphs with Local Mixing Patterns](https://mlsanity.com/paper/2106.06586/) (2021)
- [On Provable Benefits of Depth in Training Graph Convolutional Networks](https://mlsanity.com/paper/2110.15174/) (2021)
- [Rethinking Tokenizer and Decoder in Masked Graph Modeling for Molecules](https://mlsanity.com/paper/2310.14753/) (2023)
- [Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPs](https://mlsanity.com/paper/2212.09034/) (2022)
- [Equivariant Polynomials for Graph Neural Networks](https://mlsanity.com/paper/2302.11556/) (2023)
- [Grain: Improving Data Efficiency of Graph Neural Networks via Diversified Influence Maximization](https://mlsanity.com/paper/2108.00219/) (2021)
- [The Expressive Power of Graph Neural Networks: A Survey](https://mlsanity.com/paper/2308.08235/) (2023)
- [Graph Neural Networks Use Graphs When They Shouldn't](https://mlsanity.com/paper/2309.04332/) (2023)
- [A Practical, Progressively-Expressive GNN](https://mlsanity.com/paper/2210.09521/) (2022)
- [Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspective](https://mlsanity.com/paper/2207.11311/) (2022)
- [Information Gain Propagation: a new way to Graph Active Learning with Soft Labels](https://mlsanity.com/paper/2203.01093/) (2022)
- [NOSMOG: Learning Noise-robust and Structure-aware MLPs on Graphs](https://mlsanity.com/paper/2208.10010/) (2022)
- [Topology-aware Embedding Memory for Continual Learning on Expanding Networks](https://mlsanity.com/paper/2401.13200/) (2024)
- [On the Ability of Graph Neural Networks to Model Interactions Between Vertices](https://mlsanity.com/paper/2211.16494/) (2022)
- [Quantifying the Optimization and Generalization Advantages of Graph Neural Networks Over Multilayer Perceptrons](https://mlsanity.com/paper/2306.13926/) (2023)
- [Training MLPs on Graphs without Supervision](https://mlsanity.com/paper/2412.03864/) (2024)
- [Graph-Skeleton: ~1% Nodes are Sufficient to Represent Billion-Scale Graph](https://mlsanity.com/paper/2402.09565/) (2024)
- [TINED: GNNs-to-MLPs by Teacher Injection and Dirichlet Energy Distillation](https://mlsanity.com/paper/2412.11180/) (2024)
- [HOPSE: Scalable Higher-Order Positional and Structural Encoder for Combinatorial Representations](https://mlsanity.com/paper/2505.15405/) (2025)
- [Graph Neural Networks with Parallel Neighborhood Aggregations for Graph Classification](https://mlsanity.com/paper/2111.11482/) (2021)
- [Teaching MLPs to Master Heterogeneous Graph-Structured Knowledge for Efficient and Accurate Inference](https://mlsanity.com/paper/2411.14035/) (2024)
- [Graph Learning at Scale: Characterizing and Optimizing Pre-Propagation GNNs](https://mlsanity.com/paper/2504.13266/) (2025)
- [Towards Quantized Model Parallelism for Graph-Augmented MLPs Based on Gradient-Free ADMM Framework](https://mlsanity.com/paper/2105.09837/) (2021)
- [Training Free Graph Neural Networks for Graph Matching](https://mlsanity.com/paper/2201.05349/) (2022)
- [Unleashing the potential of GNNs via Bi-directional Knowledge Transfer](https://mlsanity.com/paper/2310.17132/) (2023)
- [Isomorphic-Consistent Variational Graph Auto-Encoders for Multi-Level Graph Representation Learning](https://mlsanity.com/paper/2312.05519/) (2023)
- [SimMLP: Training MLPs on Graphs without Supervision](https://mlsanity.com/paper/2402.08918/) (2024)
- [Sparse Decomposition of Graph Neural Networks](https://mlsanity.com/paper/2410.19723/) (2024)

## Abstract (arXiv)

From the perspective of expressive power, this work compares multi-layer Graph Neural Networks (GNNs) with a simplified alternative that we call Graph-Augmented Multi-Layer Perceptrons (GA-MLPs), which first augments node features with certain multi-hop operators on the graph and then applies an MLP in a node-wise fashion. From the perspective of graph isomorphism testing, we show both theoretically and numerically that GA-MLPs with suitable operators can distinguish almost all non-isomorphic graphs, just like the Weifeiler-Lehman (WL) test. However, by viewing them as node-level functions and examining the equivalence classes they induce on rooted graphs, we prove a separation in expressive power between GA-MLPs and GNNs that grows exponentially in depth. In particular, unlike GNNs, GA-MLPs are unable to count the number of attributed walks. We also demonstrate via community detection experiments that GA-MLPs can be limited by their choice of operator family, as compared to GNNs with higher flexibility in learning.