mlsanityData to 13 Oct 2026

Random Features Strengthen Graph Neural Networks

arXiv 2002.03155 ↗First posted 8 Feb 2020cs.LG stat.MLcited by 184

Not on the map. Why?

Abstract (arXiv)

Graph neural networks (GNNs) are powerful machine learning models for various graph learning tasks. Recently, the limitations of the expressive power of various GNN models have been revealed. For example, GNNs cannot distinguish some non-isomorphic graphs and they cannot learn efficient graph algorithms. In this paper, we demonstrate that GNNs become powerful just by adding a random feature to each node. We prove that the random features enable GNNs to learn almost optimal polynomial-time approximation algorithms for the minimum dominating set problem and maximum matching problem in terms of approximation ratios. The main advantage of our method is that it can be combined with off-the-shelf GNN models with slight modifications. Through experiments, we show that the addition of random features enables GNNs to solve various problems that normal GNNs, including the graph convolutional networks (GCNs) and graph isomorphism networks (GINs), cannot solve.

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

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2021: 25; 2022: 39; 2023: 45; 2024: 37; 2025: 22; 2026: 16.

184 papers.

Sort:

By area:

  1. 2021Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gaugescited by 1,147
  2. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  3. 2022How Powerful are Spectral Graph Neural Networkscited by 169
  4. 2023Exphormer: Sparse Transformers for Graphscited by 169
  5. 2021Equivariant Subgraph Aggregation Networkscited by 154
  6. 2021From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awarenesscited by 154
  7. 2021Nested Graph Neural Networkscited by 136
  8. 2022Data Augmentation for Deep Graph Learning: A Surveycited by 133
  9. 2022Pre-training via Denoising for Molecular Property Predictioncited by 124
  10. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
  11. 2021DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networkscited by 117
  12. 2023Randomized Positional Encodings Boost Length Generalization of Transformerscited by 116
38 more
  1. 2021Breaking the Limits of Message Passing Graph Neural Networkscited by 101
  2. 2022Equivariant and Stable Positional Encoding for More Powerful Graph Neural Networkscited by 94
  3. 2022How Powerful are K-hop Message Passing Graph Neural Networkscited by 90
  4. 2024Graph Mamba: Towards Learning on Graphs with State Space Modelscited by 86
  5. 2021The Logic of Graph Neural Networkscited by 84
  6. 2022Graph Neural Networks for Link Prediction with Subgraph Sketchingcited by 81
  7. 2022A Survey on Graph Representation Learning Methodscited by 66
  8. 2021Reconstruction for Powerful Graph Representationscited by 65
  9. 2022Benchmarking Graphormer on Large-Scale Molecular Modeling Datasetscited by 63
  10. 2021On the Unreasonable Effectiveness of Feature propagation in Learning on Graphs with Missing Node Featurescited by 62
  11. 2022Theory of Graph Neural Networks: Representation and Learningcited by 61
  12. 2022Ordered Subgraph Aggregation Networkscited by 57
  13. 2022Provably expressive temporal graph networkscited by 56
  14. 2021Optimization of Graph Neural Networks: Implicit Acceleration by Skip Connections and More Depthcited by 55
  15. 2021Graph Neural Networks with Local Graph Parameterscited by 51
  16. 2023InGram: Inductive Knowledge Graph Embedding via Relation Graphscited by 50
  17. 2021On Positional and Structural Node Features for Graph Neural Networks on Non-attributed Graphscited by 49
  18. 2021Walking Out of the Weisfeiler Leman Hierarchy: Graph Learning Beyond Message Passingcited by 47
  19. 2022A Theoretical Comparison of Graph Neural Network Extensionscited by 47
  20. 2022Message passing all the way upcited by 47
  21. 2022Shortest Path Networks for Graph Property Predictioncited by 46
  22. 2021Simple GNN Regularisation for 3D Molecular Property Prediction & Beyondcited by 44
  23. 2024GOAL: A Generalist Combinatorial Optimization Agent Learnercited by 40
  24. 2021Learning General Optimal Policies with Graph Neural Networks: Expressive Power, Transparency, and Limitscited by 38
  25. 2023Equivariant Polynomials for Graph Neural Networkscited by 38
  26. 2022SpeqNets: Sparsity-aware Permutation-equivariant Graph Networkscited by 37
  27. 2023Cooperative Graph Neural Networkscited by 36
  28. 2023The expressive power of pooling in Graph Neural Networkscited by 35
  29. 2023Graph Positional and Structural Encodercited by 33
  30. 2023Fractional Denoising for 3D Molecular Pre-trainingcited by 33
  31. 2023A Theory of Link Prediction via Relational Weisfeiler-Leman on Knowledge Graphscited by 32
  32. 2023Path Neural Networks: Expressive and Accurate Graph Neural Networkscited by 32
  33. 2025Relational Graph Transformercited by 32
  34. 2023WL meet VCcited by 30
  35. 2023Graph Positional Encoding via Random Feature Propagationcited by 30
  36. 2022One Model, Any CSP: Graph Neural Networks as Fast Global Search Heuristics for Constraint Satisfactioncited by 27
  37. 2023The Expressive Power of Graph Neural Networks: A Surveycited by 27
  38. 2021On the Universality of Graph Neural Networks on Large Random Graphscited by 26

50 most cited of 184 All 184 (JSON)