mlsanityData to 7 Oct 2026

Graph Neural Networks Use Graphs When They Shouldn't

arXiv 2309.04332 ↗First posted 8 Sep 2023cs.LG cs.AIcited by 25

Not on the map. Why?

Abstract (arXiv)

Predictions over graphs play a crucial role in various domains, including social networks and medicine. Graph Neural Networks (GNNs) have emerged as the dominant approach for learning on graph data. Although a graph-structure is provided as input to the GNN, in some cases the best solution can be obtained by ignoring it. While GNNs have the ability to ignore the graph- structure in such cases, it is not clear that they will. In this work, we show that GNNs actually tend to overfit the given graph-structure. Namely, they use it even when a better solution can be obtained by ignoring it. We analyze the implicit bias of gradient-descent learning of GNNs and prove that when the ground truth function does not use the graphs, GNNs are not guaranteed to learn a solution that ignores the graph, even with infinite data. We examine this phenomenon with respect to different graph distributions and find that regular graphs are more robust to this over-fitting. We also prove that within the family of regular graphs, GNNs are guaranteed to extrapolate when learning with gradient descent. Finally, based on our empirical and theoretical findings, we demonstrate on real-data how regular graphs can be leveraged to reduce graph overfitting and enhance performance.

Key facts. Cited by 25 papers in the map (data through 7 Oct 2026). Builds on 24 of its 32 references that are in the map. First posted on arXiv 8 Sep 2023.

Builds on

24 of 32 references.

References · 24

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
  2. 2017Graph Attention Networkscited by 8,854
  3. 2017Inductive Representation Learning on Large Graphscited by 6,284
  4. 2018How Powerful are Graph Neural Networks?cited by 4,355
  5. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  6. 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
  7. 2016Understanding deep learning requires rethinking generalizationcited by 1,657
  8. 2017Deep Setscited by 1,394
  9. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 878
  10. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 718
  11. 2019DropEdge: Towards Deep Graph Convolutional Networks on Node Classificationcited by 679
  12. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 649
12 more
  1. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 624
  2. 2020Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classificationcited by 500
  3. 2020Parameterized Explainer for Graph Neural Networkcited by 423
  4. 2019Gradient Descent Maximizes the Margin of Homogeneous Neural Networkscited by 308
  5. 2020Towards Deeper Graph Neural Networkscited by 296
  6. 2018Implicit Bias of Gradient Descent on Linear Convolutional Networkscited by 251
  7. 2019A Fair Comparison of Graph Neural Networks for Graph Classificationcited by 244
  8. 2017SGD Learns Over-parameterized Networks that Provably Generalize on Linearly Separable Datacited by 79
  9. 2021Implicit Regularization in Tensor Factorizationcited by 43
  10. 2020On Graph Neural Networks versus Graph-Augmented MLPscited by 30
  11. 2022Learning Low Dimensional State Spaces with Overparameterized Recurrent Neural Netscited by 7
  12. 2021Node Feature Kernels Increase Graph Convolutional Network Robustnesscited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 5; 2025: 14; 2026: 5.

25 papers.

Sort:

By area:

  1. 2025Position: Graph Learning Will Lose Relevance Due To Poor Benchmarkscited by 52
  2. 2024Cayley Graph Propagationcited by 21
  3. 2024The Interpretable and Effective Graph Neural Additive Networkscited by 19
  4. 2025No Metric to Rule Them All: Toward Principled Evaluations of Graph-Learning Datasetscited by 16
  5. 2024MANTRA: The Manifold Triangulations Assemblagecited by 12
  6. 2025Beyond Topological Self-Explainable GNNs: A Formal Explainability Perspectivecited by 10
  7. 2024Future Directions in the Theory of Graph Machine Learningcited by 5
  8. 2025Geometry-Aware Edge Pooling for Graph Neural Networkscited by 5
  9. 2026Billion-Scale Graph Foundation Modelscited by 5
  10. 2025Towards Invariance to Node Identifiers in Graph Neural Networkscited by 4
  11. 2025Graph Representational Learning: When Does More Expressivity Hurt Generalization?cited by 4
  12. 2025Understanding and Mitigating Distribution Shifts For Machine Learning Force Fieldscited by 3
13 more
  1. 2025Spectral Graph Neural Networks are Incomplete on Graphs with a Simple Spectrumcited by 3
  2. 2025When Structure Doesn't Help: LLMs Do Not Read Text-Attributed Graphs as Effectively as We Expectedcited by 3
  3. 2025Short-Range Oversquashingcited by 2
  4. 2026Hyperbolic Graph Neural Networks Under the Microscope: The Role of Geometry-Task Alignmentcited by 2
  5. 2025Node Embeddings via Neighbor Embeddingscited by 1
  6. 2025Structural Invariance Matters: Rethinking Graph Rewiring through Graph Metricscited by 1
  7. 2026Improving LLM Final Representations with Inter-Layer Geometrycited by 1
  8. 2023Global Minima, Recoverability Thresholds, and Higher-Order Structure in GNNScited by 0
  9. 2024Graph Transductive Defense: a Two-Stage Defense for Graph Membership Inference Attackscited by 0
  10. 2025Memorization in Graph Neural Networkscited by 0
  11. 2025Enhancing Graph Neural Networks: A Mutual Learning Approachcited by 0
  12. 2026Invariant-Based Weight Sharing for Message Passingcited by 0
  13. 2026Ramanujan Graph Rewiring with Non Negative Resistance Curvaturecited by 0