mlsanityData to 13 Oct 2026

On Graph Neural Networks versus Graph-Augmented MLPs

arXiv 2010.15116 ↗First posted 28 Oct 2020cs.LG math.CO stat.MLcited by 30

Not on the map. Why?

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.

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

Builds on

No reference list yet.

Built on by

Cited by year

Citing papers per year: 2021: 5; 2022: 9; 2023: 7; 2024: 7; 2025: 2.

30 papers.

Sort:

  1. 2022How Powerful are Spectral Graph Neural Networkscited by 169
  2. 2022Data Augmentation for Deep Graph Learning: A Surveycited by 133
  3. 2021Breaking the Limit of Graph Neural Networks by Improving the Assortativity of Graphs with Local Mixing Patternscited by 95
  4. 2021On Provable Benefits of Depth in Training Graph Convolutional Networkscited by 58
  5. 2023Rethinking Tokenizer and Decoder in Masked Graph Modeling for Moleculescited by 49
  6. 2022Graph Neural Networks are Inherently Good Generalizers: Insights by Bridging GNNs and MLPscited by 42
  7. 2023Equivariant Polynomials for Graph Neural Networkscited by 38
  8. 2021Grain: Improving Data Efficiency of Graph Neural Networks via Diversified Influence Maximizationcited by 28
  9. 2023The Expressive Power of Graph Neural Networks: A Surveycited by 27
  10. 2023Graph Neural Networks Use Graphs When They Shouldn'tcited by 26
  11. 2022A Practical, Progressively-Expressive GNNcited by 20
  12. 2022Understanding Non-linearity in Graph Neural Networks from the Bayesian-Inference Perspectivecited by 19
18 more
  1. 2022Information Gain Propagation: a new way to Graph Active Learning with Soft Labelscited by 16
  2. 2022NOSMOG: Learning Noise-robust and Structure-aware MLPs on Graphscited by 14
  3. 2024Topology-aware Embedding Memory for Continual Learning on Expanding Networkscited by 14
  4. 2022On the Ability of Graph Neural Networks to Model Interactions Between Verticescited by 12
  5. 2023Quantifying the Optimization and Generalization Advantages of Graph Neural Networks Over Multilayer Perceptronscited by 12
  6. 2024Training MLPs on Graphs without Supervisioncited by 8
  7. 2024Graph-Skeleton: ~1% Nodes are Sufficient to Represent Billion-Scale Graphcited by 6
  8. 2025HOPSE: Scalable Higher-Order Positional and Structural Encoder for Combinatorial Representationscited by 5
  9. 2021Graph Neural Networks with Parallel Neighborhood Aggregations for Graph Classificationcited by 4
  10. 2024TINED: GNNs-to-MLPs by Teacher Injection and Dirichlet Energy Distillationcited by 4
  11. 2024Teaching MLPs to Master Heterogeneous Graph-Structured Knowledge for Efficient and Accurate Inferencecited by 2
  12. 2025Graph Learning at Scale: Characterizing and Optimizing Pre-Propagation GNNscited by 2
  13. 2021Towards Quantized Model Parallelism for Graph-Augmented MLPs Based on Gradient-Free ADMM Frameworkcited by 0
  14. 2022Training Free Graph Neural Networks for Graph Matchingcited by 0
  15. 2023Unleashing the potential of GNNs via Bi-directional Knowledge Transfercited by 0
  16. 2023Isomorphic-Consistent Variational Graph Auto-Encoders for Multi-Level Graph Representation Learningcited by 0
  17. 2024SimMLP: Training MLPs on Graphs without Supervisioncited by 0
  18. 2024Sparse Decomposition of Graph Neural Networkscited by 0