mlsanityData to 14 Oct 2026

Expressivity of Graph Neural Networks Through the Lens of Adversarial Robustness

arXiv 2308.08173 ↗First posted 16 Aug 2023cs.LGcited by 1

Not on the map. Why?

Abstract (arXiv)

We perform the first adversarial robustness study into Graph Neural Networks (GNNs) that are provably more powerful than traditional Message Passing Neural Networks (MPNNs). In particular, we use adversarial robustness as a tool to uncover a significant gap between their theoretically possible and empirically achieved expressive power. To do so, we focus on the ability of GNNs to count specific subgraph patterns, which is an established measure of expressivity, and extend the concept of adversarial robustness to this task. Based on this, we develop efficient adversarial attacks for subgraph counting and show that more powerful GNNs fail to generalize even to small perturbations to the graph's structure. Expanding on this, we show that such architectures also fail to count substructures on out-of-distribution graphs.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 24 of its 28 references that are in the map. First posted on arXiv 16 Aug 2023.

Builds on

24 of 28 references.

References · 24

  1. 2014Explaining and Harnessing Adversarial Examplescited by 7,364
  2. 2018How Powerful are Graph Neural Networks?cited by 4,393
  3. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  4. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  5. 2019Graph Neural Networks for Social Recommendationcited by 714
  6. 2020Directional Message Passing for Molecular Graphscited by 561
  7. 2018Adversarial Attacks on Neural Networks for Graph Datacited by 397
  8. 2019Provably Powerful Graph Networkscited by 389
  9. 2018Invariant and Equivariant Graph Networkscited by 346
  10. 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 318
  11. 2018Adversarial Attack on Graph Structured Datacited by 301
  12. 2020Can Graph Neural Networks Count Substructures?cited by 236
12 more
  1. 2022Understanding and Extending Subgraph GNNs by Rethinking Their Symmetriescited by 112
  2. 2018N-Gram Graph: Simple Unsupervised Representation for Graphs, with Applications to Moleculescited by 93
  3. 2022How Powerful are K-hop Message Passing Graph Neural Networkscited by 90
  4. 2020An Analysis of Adversarial Attacks and Defenses on Autonomous Driving Modelscited by 68
  5. 2018MotifNet: a motif-based Graph Convolutional Network for directed graphscited by 64
  6. 2022Boosting the Cycle Counting Power of Graph Neural Networks with I2-GNNscited by 56
  7. 2021Generalization of Neural Combinatorial Solvers Through the Lens of Adversarial Robustnesscited by 35
  8. 2023Adversarial Training for Graph Neural Networks: Pitfalls, Solutions, and New Directionscited by 28
  9. 2020Counting Substructures with Higher-Order Graph Neural Networks: Possibility and Impossibility Resultscited by 19
  10. 2023Revisiting Robustness in Graph Machine Learningcited by 19
  11. 2023Learning to Count Isomorphisms with Graph Neural Networkscited by 13
  12. 2020Faster motif counting via succinct color coding and adaptive samplingcited by 4

Built on by

Cited by year

Citing papers per year: 2024: 1.

1 paper.

  1. 2024Discrete Randomized Smoothing Meets Quantum Computingcited by 2