mlsanityData to 7 Oct 2026

DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks

arXiv 2111.06283 ↗First posted 11 Nov 2021cs.LGcited by 117

Not on the map. Why?

Abstract (arXiv)

This paper studies Dropout Graph Neural Networks (DropGNNs), a new approach that aims to overcome the limitations of standard GNN frameworks. In DropGNNs, we execute multiple runs of a GNN on the input graph, with some of the nodes randomly and independently dropped in each of these runs. Then, we combine the results of these runs to obtain the final result. We prove that DropGNNs can distinguish various graph neighborhoods that cannot be separated by message passing GNNs. We derive theoretical bounds for the number of runs required to ensure a reliable distribution of dropouts, and we prove several properties regarding the expressive capabilities and limits of DropGNNs. We experimentally validate our theoretical findings on expressiveness. Furthermore, we show that DropGNNs perform competitively on established GNN benchmarks.

Key facts. Cited by 117 papers in the map (data through 7 Oct 2026). Builds on 32 of its 39 references that are in the map. First posted on arXiv 11 Nov 2021.

Builds on

32 of 39 references.

References · 32

  1. 2014Adam: A Method for Stochastic Optimizationcited by 36,960
  2. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  3. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  4. 2017Graph Attention Networkscited by 8,854
  5. 2015Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shiftcited by 6,979
  6. 2017Inductive Representation Learning on Large Graphscited by 6,284
  7. 2018How Powerful are Graph Neural Networks?cited by 4,355
  8. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  9. 2019A Comprehensive Survey on Graph Neural Networkscited by 2,906
  10. 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
  11. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,085
  12. 2018Relational inductive biases, deep learning, and graph networkscited by 1,341
20 more
  1. 2019Certified Adversarial Robustness via Randomized Smoothingcited by 1,324
  2. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,097
  3. 2017MoleculeNet: A Benchmark for Molecular Machine Learningcited by 1,037
  4. 2019Strategies for Pre-training Graph Neural Networkscited by 964
  5. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  6. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 875
  7. 2020Learning to Simulate Complex Physics with Graph Networkscited by 867
  8. 2019DropEdge: Towards Deep Graph Convolutional Networks on Node Classificationcited by 679
  9. 2020Directional Message Passing for Molecular Graphscited by 556
  10. 2019Provably Powerful Graph Networkscited by 385
  11. 2016Learning Convolutional Neural Networks for Graphscited by 314
  12. 2015Diffusion-Convolutional Neural Networkscited by 268
  13. 2020Generalization and Representational Limits of Graph Neural Networkscited by 217
  14. 2020Graph Random Neural Network for Semi-Supervised Learning on Graphscited by 213
  15. 2019What graph neural networks cannot learn: depth vs widthcited by 195
  16. 2020The Surprising Power of Graph Neural Networks with Random Node Initializationcited by 190
  17. 2020Random Features Strengthen Graph Neural Networkscited by 184
  18. 2019On the equivalence between graph isomorphism testing and function approximation with GNNscited by 172
  19. 2019Approximation Ratios of Graph Neural Networks for Combinatorial Problemscited by 68
  20. 2020Efficient Robustness Certificates for Discrete Data: Sparsity-Aware Randomized Smoothing for Graphs, Images and Morecited by 56

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 2; 2022: 34; 2023: 34; 2024: 29; 2025: 12; 2026: 6.

117 papers.

Sort:

By area:

  1. 2022Sign and Basis Invariant Networks for Spectral Graph Representation Learningcited by 176
  2. 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
  3. 2023Rethinking the Expressive Power of GNNs via Graph Biconnectivitycited by 119
  4. 2022Understanding and Extending Subgraph GNNs by Rethinking Their Symmetriescited by 112
  5. 2022SPECTRE: Spectral Conditioning Helps to Overcome the Expressivity Limits of One-shot Graph Generatorscited by 96
  6. 2023DRew: Dynamically Rewired Message Passing with Delaycited by 81
  7. 2022DiffWire: Inductive Graph Rewiring via the Lov'asz Boundcited by 79
  8. 2022A Survey on Graph Representation Learning Methodscited by 66
  9. 2023A Complete Expressiveness Hierarchy for Subgraph GNNs via Subgraph Weisfeiler-Lehman Testscited by 64
  10. 2022Ordered Subgraph Aggregation Networkscited by 57
  11. 2022Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNscited by 55
  12. 2022Graph Pooling for Graph Neural Networks: Progress, Challenges, and Opportunitiescited by 52
38 more
  1. 2022Oversquashing in GNNs through the lens of information contraction and graph expansioncited by 52
  2. 2022A Theoretical Comparison of Graph Neural Network Extensionscited by 47
  3. 2022Message passing all the way upcited by 47
  4. 2024Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressivenesscited by 38
  5. 2022SpeqNets: Sparsity-aware Permutation-equivariant Graph Networkscited by 37
  6. 2023Cooperative Graph Neural Networkscited by 35
  7. 2023An Empirical Study of Realized GNN Expressivenesscited by 33
  8. 2023Path Neural Networks: Expressive and Accurate Graph Neural Networkscited by 32
  9. 2023WL meet VCcited by 30
  10. 2022DropMessage: Unifying Random Dropping for Graph Neural Networkscited by 29
  11. 2023The Expressive Power of Graph Neural Networks: A Surveycited by 27
  12. 2023Probabilistically Rewired Message-Passing Neural Networkscited by 26
  13. 2023Provably Powerful Graph Neural Networks for Directed Multigraphscited by 24
  14. 2023Counterfactual Learning on Graphs: A Surveycited by 22
  15. 2022A Survey of Trustworthy Graph Learning: Reliability, Explainability, and Privacy Protectioncited by 20
  16. 2022Template based Graph Neural Network with Optimal Transport Distancescited by 20
  17. 2023Pure Message Passing Can Estimate Common Neighbor for Link Predictioncited by 18
  18. 2023Efficient Subgraph GNNs by Learning Effective Selection Policiescited by 17
  19. 20221-WL Expressiveness Is (Almost) All You Needcited by 15
  20. 2024Probabilistic Graph Rewiring via Virtual Nodescited by 15
  21. 2023Facilitating Graph Neural Networks with Random Walk on Simplicial Complexescited by 14
  22. 2025Graph-Augmented Large Language Model Agents: Current Progress and Future Prospectscited by 14
  23. 2022Agent-based Graph Neural Networkscited by 13
  24. 2023An Efficient Subgraph GNN with Provable Substructure Counting Powercited by 13
  25. 2023Extending the Design Space of Graph Neural Networks by Rethinking Folklore Weisfeiler-Lehmancited by 13
  26. 2024Revisiting Random Walks for Learning on Graphscited by 13
  27. 2025GNNs Getting ComFy: Community and Feature Similarity Guided Rewiringcited by 13
  28. 2023BeMap: Balanced Message Passing for Fair Graph Neural Networkcited by 11
  29. 2023MAG-GNN: Reinforcement Learning Boosted Graph Neural Networkcited by 11
  30. 2024Graph Classification via Reference Distribution Learning: Theory and Practicecited by 11
  31. 2022Recent Advances in Reliable Deep Graph Learning: Inherent Noise, Distribution Shift, and Adversarial Attackcited by 10
  32. 2023Weisfeiler and Lehman Go Paths: Learning Topological Features via Path Complexescited by 10
  33. 2022Graph Augmentation Learningcited by 9
  34. 2022Fundamental Limits in Formal Verification of Message-Passing Neural Networkscited by 9
  35. 2023MulGT: Multi-task Graph-Transformer with Task-aware Knowledge Injection and Domain Knowledge-driven Pooling for Whole Slide Image Analysiscited by 9
  36. 2023Graph Out-of-Distribution Generalization with Controllable Data Augmentationcited by 9
  37. 2023Are GATs Out of Balance?cited by 9
  38. 2022Towards Quantum Graph Neural Networks: An Ego-Graph Learning Approachcited by 8

50 most cited of 117 All 117 (JSON)