On the Relationship Between Robustness and Expressivity of Graph Neural Networks
Not on the map. Why?
Abstract (arXiv)
We investigate the vulnerability of Graph Neural Networks (GNNs) to bit-flip attacks (BFAs) by introducing an analytical framework to study the influence of architectural features, graph properties, and their interaction. The expressivity of GNNs refers to their ability to distinguish non-isomorphic graphs and depends on the encoding of node neighborhoods. We examine the vulnerability of neural multiset functions commonly used for this purpose and establish formal criteria to characterize a GNN's susceptibility to losing expressivity due to BFAs. This enables an analysis of the impact of homophily, graph structural variety, feature encoding, and activation functions on GNN robustness. We derive theoretical bounds for the number of bit flips required to degrade GNN expressivity on a dataset, identifying ReLU-activated GNNs operating on highly homophilous graphs with low-dimensional or one-hot encoded features as particularly susceptible. Empirical results using ten real-world datasets confirm the statistical significance of our key theoretical insights and offer actionable results to mitigate BFA risks in expressivity-critical applications.
Key facts. Cited by 3 papers in the map (data through 7 Oct 2026). Builds on 25 of its 46 references that are in the map. First posted on arXiv 18 Apr 2025.
Builds on
25 of 46 references.
References · 25
- 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,282
- 2017Graph Attention Networkscited by 8,854
- 2018How Powerful are Graph Neural Networks?cited by 4,355
- 2015Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classificationcited by 3,590
- 2020Open Graph Benchmark: Datasets for Machine Learning on Graphscited by 2,148
- 2017Deep Setscited by 1,394
- 2017MoleculeNet: A Benchmark for Molecular Machine Learningcited by 1,037
- 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 718
- 2021Weisfeiler and Leman go Machine Learning: The Story so farcited by 121
- 2019Bit-Flip Attack: Crushing Neural Network with Progressive Bit Searchcited by 106
- 2020A survey on modern trainable activation functionscited by 89
- 2014Propagation Kernelscited by 88
13 more
- 2020Towards More Practical Adversarial Attacks on Graph Neural Networkscited by 76
- 2021Universal Approximation of Functions on Setscited by 62
- 2022Theory of Graph Neural Networks: Representation and Learningcited by 60
- 2020DeepHammer: Depleting the Intelligence of Deep Neural Networks through Targeted Chain of Bit Flipscited by 53
- 2020Globally Injective ReLU Networkscited by 23
- 2019RowHammer: A Retrospectivecited by 19
- 2021The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphscited by 19
- 2023Rank Collapse Causes Over-Smoothing and Over-Correlation in Graph Neural Networkscited by 18
- 20221-WL Expressiveness Is (Almost) All You Needcited by 15
- 2021A Generalized Weisfeiler-Lehman Graph Kernelcited by 9
- 2022A Closer Look at Evaluating the Bit-Flip Attack Against Deep Neural Networkscited by 5
- 2023Securing Graph Neural Networks in MLaaS: A Comprehensive Realization of Query-based Integrity Verificationcited by 5
- 2022Beyond 1-WL with Local Ego-Network Encodingscited by 2
Built on by
Citing papers per year: 2025: 2; 2026: 1.
3 papers.