mlsanityData to 14 Oct 2026

The Surprising Power of Graph Neural Networks with Random Node Initialization

arXiv 2010.01179 ↗First posted 2 Oct 2020cs.LG cs.AI stat.MLcited by 198

Not on the map. Why?

Abstract (arXiv)

Graph neural networks (GNNs) are effective models for representation learning on relational data. However, standard GNNs are limited in their expressive power, as they cannot distinguish graphs beyond the capability of the Weisfeiler-Leman graph isomorphism heuristic. In order to break this expressiveness barrier, GNNs have been enhanced with random node initialization (RNI), where the idea is to train and run the models with randomized initial node features. In this work, we analyze the expressive power of GNNs with RNI, and prove that these models are universal, a first such result for GNNs not relying on computationally demanding higher-order properties. This universality result holds even with partially randomized initial node features, and preserves the invariance properties of GNNs in expectation. We then empirically analyze the effect of RNI on GNNs, based on carefully constructed datasets. Our empirical findings support the superior performance of GNNs with RNI over standard GNNs.

Key facts. Cited by 198 papers in the map (data through 14 Oct 2026). First posted on arXiv 2 Oct 2020.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 21; 2022: 40; 2023: 52; 2024: 39; 2025: 28; 2026: 18.

198 papers.

Sort:

By area:

  1. 2021Combinatorial optimization and reasoning with graph neural networkscited by 268
  2. 2022How Powerful are Spectral Graph Neural Networkscited by 169
  3. 2021Frame Averaging for Invariant and Equivariant Network Designcited by 168
  4. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 155
  5. 2021Equivariant Subgraph Aggregation Networkscited by 154
  6. 2021Nested Graph Neural Networkscited by 137
  7. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 122
  8. 2021DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networkscited by 118
  9. 2022Understanding and Extending Subgraph GNNs by Rethinking Their Symmetriescited by 112
  10. 2021Breaking the Limits of Message Passing Graph Neural Networkscited by 101
  11. 2022Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networkscited by 94
  12. 2022A Generalization of ViT/MLP-Mixer to Graphscited by 93
38 more
  1. 2022How Powerful are K-hop Message Passing Graph Neural Networkscited by 90
  2. 2021The Logic of Graph Neural Networkscited by 85
  3. 2022Graph Neural Networks for Link Prediction with Subgraph Sketchingcited by 81
  4. 2021Reconstruction for Powerful Graph Representationscited by 65
  5. 2022Benchmarking Graphormer on Large-Scale Molecular Modeling Datasetscited by 64
  6. 2021On the Unreasonable Effectiveness of Feature propagation in Learning on Graphs with Missing Node Featurescited by 63
  7. 2022Theory of Graph Neural Networks: Representation and Learningcited by 61
  8. 2022Ordered Subgraph Aggregation Networkscited by 57
  9. 2022Provably expressive temporal graph networkscited by 56
  10. 2022Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNscited by 56
  11. 2021Graph Neural Networks with Local Graph Parameterscited by 52
  12. 2023InGram: Inductive Knowledge Graph Embedding via Relation Graphscited by 52
  13. 2021On Positional and Structural Node Features for Graph Neural Networks on Non-attributed Graphscited by 49
  14. 2022A Theoretical Comparison of Graph Neural Network Extensionscited by 48
  15. 2021Walking Out of the Weisfeiler Leman Hierarchy: Graph Learning Beyond Message Passingcited by 47
  16. 2022Shortest Path Networks for Graph Property Predictioncited by 46
  17. 2021Learning General Optimal Policies with Graph Neural Networks: Expressive Power, Transparency, and Limitscited by 38
  18. 2023Equivariant Polynomials for Graph Neural Networkscited by 38
  19. 2022SpeqNets: Sparsity-aware Permutation-equivariant Graph Networkscited by 37
  20. 2023Cooperative Graph Neural Networkscited by 36
  21. 2023The expressive power of pooling in Graph Neural Networkscited by 35
  22. 2023An Empirical Study of Realized GNN Expressivenesscited by 33
  23. 2023Graph Positional and Structural Encodercited by 33
  24. 2023A Theory of Link Prediction via Relational Weisfeiler-Leman on Knowledge Graphscited by 32
  25. 2023Path Neural Networks: Expressive and Accurate Graph Neural Networkscited by 32
  26. 2023WL meet VCcited by 31
  27. 2023Graph Positional Encoding via Random Feature Propagationcited by 31
  28. 2023Learning Domain-Independent Heuristics for Grounded and Lifted Planningcited by 31
  29. 2022One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfactioncited by 27
  30. 2023Provably Powerful Graph Neural Networks for Directed Multigraphscited by 27
  31. 2023The Expressive Power of Graph Neural Networks: A Surveycited by 27
  32. 2024A Canonicalization Perspective on Invariant and Equivariant Learningcited by 27
  33. 2021On the Universality of Graph Neural Networks on Large Random Graphscited by 26
  34. 2023The Descriptive Complexity of Graph Neural Networkscited by 26
  35. 2023Learning Probabilistic Symmetrization for Architecture Agnostic Equivariancecited by 26
  36. 2023Probabilistically Rewired Message-Passing Neural Networkscited by 26
  37. 2023Fine-grained Expressivity of Graph Neural Networkscited by 25
  38. 2025Learning Efficient Positional Encodings with Graph Neural Networkscited by 24

50 most cited of 198 All 198 (JSON)