# On the Relationship Between Robustness and Expressivity of Graph Neural Networks

arXiv: https://arxiv.org/abs/2504.13786 · HTML: https://mlsanity.com/paper/2504.13786/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 46 references that are in the map.
- First posted on arXiv 18 Apr 2025.

## Builds on (most cited first, 25 of 25)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Delving Deep into Rectifiers: Surpassing Human-Level Performance on ImageNet Classification](https://mlsanity.com/paper/1502.01852/) (2015)
- [Open Graph Benchmark: Datasets for Machine Learning on Graphs](https://mlsanity.com/paper/2005.00687/) (2020)
- [Deep Sets](https://mlsanity.com/paper/1703.06114/) (2017)
- [MoleculeNet: A Benchmark for Molecular Machine Learning](https://mlsanity.com/paper/1703.00564/) (2017)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [Bit-Flip Attack: Crushing Neural Network with Progressive Bit Search](https://mlsanity.com/paper/1903.12269/) (2019)
- [A survey on modern trainable activation functions](https://mlsanity.com/paper/2005.00817/) (2020)
- [Propagation Kernels](https://mlsanity.com/paper/1410.3314/) (2014)
- [Towards More Practical Adversarial Attacks on Graph Neural Networks](https://mlsanity.com/paper/2006.05057/) (2020)
- [Universal Approximation of Functions on Sets](https://mlsanity.com/paper/2107.01959/) (2021)
- [Theory of Graph Neural Networks: Representation and Learning](https://mlsanity.com/paper/2204.07697/) (2022)
- [DeepHammer: Depleting the Intelligence of Deep Neural Networks through Targeted Chain of Bit Flips](https://mlsanity.com/paper/2003.13746/) (2020)
- [Globally Injective ReLU Networks](https://mlsanity.com/paper/2006.08464/) (2020)
- [RowHammer: A Retrospective](https://mlsanity.com/paper/1904.09724/) (2019)
- [The Power of the Weisfeiler-Leman Algorithm for Machine Learning with Graphs](https://mlsanity.com/paper/2105.05911/) (2021)
- [Rank Collapse Causes Over-Smoothing and Over-Correlation in Graph Neural Networks](https://mlsanity.com/paper/2308.16800/) (2023)
- [1-WL Expressiveness Is (Almost) All You Need](https://mlsanity.com/paper/2202.10156/) (2022)
- [A Generalized Weisfeiler-Lehman Graph Kernel](https://mlsanity.com/paper/2101.08104/) (2021)
- [A Closer Look at Evaluating the Bit-Flip Attack Against Deep Neural Networks](https://mlsanity.com/paper/2209.14243/) (2022)
- [Securing Graph Neural Networks in MLaaS: A Comprehensive Realization of Query-based Integrity Verification](https://mlsanity.com/paper/2312.07870/) (2023)
- [Beyond 1-WL with Local Ego-Network Encodings](https://mlsanity.com/paper/2211.14906/) (2022)

## Built on by (most cited first, 3 of 3)

- [Weisfeiler and Leman Go Gambling: Why Expressive Lottery Tickets Win](https://mlsanity.com/paper/2506.03919/) (2025)
- [Enhancing Graph Classification Robustness with Singular Pooling](https://mlsanity.com/paper/2510.22643/) (2025)
- [A Unifying Relational Perspective on Expressive Lottery Tickets](https://mlsanity.com/paper/2608.18819/) (2026)

## 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.