mlsanityData to 14 Oct 2026

Non-convolutional Graph Neural Networks

arXiv 2408.00165 ↗First posted 31 Jul 2024cs.LG cs.AIcited by 11

Not on the map. Why?

Abstract (arXiv)

Rethink convolution-based graph neural networks (GNN) -- they characteristically suffer from limited expressiveness, over-smoothing, and over-squashing, and require specialized sparse kernels for efficient computation. Here, we design a simple graph learning module entirely free of convolution operators, coined random walk with unifying memory (RUM) neural network, where an RNN merges the topological and semantic graph features along the random walks terminating at each node. Relating the rich literature on RNN behavior and graph topology, we theoretically show and experimentally verify that RUM attenuates the aforementioned symptoms and is more expressive than the Weisfeiler-Lehman (WL) isomorphism test. On a variety of node- and graph-level classification and regression tasks, RUM not only achieves competitive performance, but is also robust, memory-efficient, scalable, and faster than the simplest convolutional GNNs.

Key facts. Cited by 11 papers in the map (data through 14 Oct 2026). Builds on 55 of its 86 references that are in the map. First posted on arXiv 31 Jul 2024.

Builds on

55 of 86 references.

References · 55

  1. 2017Attention Is All You Needcited by 60,361
  2. 2015Deep Residual Learning for Image Recognitioncited by 52,096
  3. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,305
  4. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  5. 2017Graph Attention Networkscited by 8,923
  6. 2017Inductive Representation Learning on Large Graphscited by 6,320
  7. 2018How Powerful are Graph Neural Networks?cited by 4,393
  8. 2014Learning Phrase Representations using RNN Encoder-Decoder for Statistical Machine Translationcited by 4,057
  9. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  10. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,163
  11. 2019Simplifying Graph Convolutional Networkscited by 1,477
  12. 2018Relational inductive biases, deep learning, and graph networkscited by 1,360
38 more
  1. 2017MoleculeNet: A Benchmark for Molecular Machine Learningcited by 1,051
  2. 2018Pitfalls of Graph Neural Network Evaluationcited by 1,007
  3. 2018Predict then Propagate: Graph Neural Networks meet Personalized PageRankcited by 993
  4. 2016Revisiting Semi-Supervised Learning with Graph Embeddingscited by 976
  5. 2017Sigmoid-Weighted Linear Units for Neural Network Function Approximation in Reinforcement Learningcited by 950
  6. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 877
  7. 2020Simple and Deep Graph Convolutional Networkscited by 860
  8. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 728
  9. 2022Recipe for a General, Powerful, Scalable Graph Transformercited by 713
  10. 2015Image-based Recommendations on Styles and Substitutescited by 706
  11. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 631
  12. 2019GraphSAINT: Graph Sampling Based Inductive Learning Methodcited by 618
  13. 2018FastGCN: Fast Learning with Graph Convolutional Networks via Importance Samplingcited by 584
  14. 2019Cluster-GCN: An Efficient Algorithm for Training Deep and Large Graph Convolutional Networkscited by 541
  15. 2017Ray: A Distributed Framework for Emerging AI Applicationscited by 527
  16. 2020Principal Neighbourhood Aggregation for Graph Netscited by 478
  17. 2021Understanding over-squashing and bottlenecks on graphs via curvaturecited by 478
  18. 2016Geometric deep learning on graphs and manifolds using mixture model CNNscited by 468
  19. 2019Provably Powerful Graph Networkscited by 389
  20. 2021Do Transformers Really Perform Bad for Graph Representation?cited by 320
  21. 2020Improving Graph Neural Network Expressivity via Subgraph Isomorphism Countingcited by 313
  22. 2019PairNorm: Tackling Oversmoothing in GNNscited by 297
  23. 2020SIGN: Scalable Inception Graph Neural Networkscited by 284
  24. 2021GRAND: Graph Neural Diffusioncited by 258
  25. 2020A Note on Over-Smoothing for Graph Neural Networkscited by 249
  26. 2023A Survey on Oversmoothing in Graph Neural Networkscited by 247
  27. 2020Generalization and Representational Limits of Graph Neural Networkscited by 218
  28. 2020Graph Random Neural Network for Semi-Supervised Learning on Graphscited by 213
  29. 2019What graph neural networks cannot learn: depth vs widthcited by 201
  30. 2021Inductive Representation Learning in Temporal Networks via Causal Anonymous Walkscited by 193
  31. 2019Layer-Dependent Importance Sampling for Training Deep and Large Graph Convolutional Networkscited by 177
  32. 2017Go for a Walk and Arrive at the Answer: Reasoning Over Paths in Knowledge Bases using Reinforcement Learningcited by 161
  33. 2019Relational Pooling for Graph Representationscited by 150
  34. 2019A Survey on Graph Kernelscited by 148
  35. 2022Graph-Coupled Oscillator Networkscited by 124
  36. 2023Specformer: Spectral Graph Neural Networks Meet Transformerscited by 102
  37. 2019LanczosNet: Multi-Scale Deep Graph Convolutional Networkscited by 73
  38. 2021Scalable and Adaptive Graph Neural Networks with Self-Label-Enhanced trainingcited by 54

50 most cited of 55 All 55 (JSON)

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 2; 2025: 7; 2026: 2.

11 papers.

  1. 2025Beyond Message Passing: Neural Graph Pattern Machinecited by 17
  2. 2025Generative Graph Pattern Machinecited by 11
  3. 2025Flock: A Knowledge Graph Foundation Model via Learning on Random Walkscited by 9
  4. 2025Are We Measuring Oversmoothing in Graph Neural Networks Correctly?cited by 6
  5. 2024On the design space between molecular mechanics and machine learning force fieldscited by 4
  6. 2025CLOUD: A Scalable and Physics-Informed Foundation Model for Crystal Representation Learningcited by 3
  7. 2024Molecular Dynamics and Machine Learning Unlock Possibilities in Beauty Design -- A Perspectivecited by 1
  8. 2025Random Search Neural Networks for Efficient and Expressive Graph Learningcited by 1
  9. 2026From Message-Passing to Linearized Graph Sequence Modelscited by 1
  10. 2025Learn to Jump: Adaptive Random Walks for Long-Range Propagation through Graph Hierarchiescited by 0
  11. 2026Modern Structure-Aware Simplicial Spatiotemporal Neural Networkcited by 0