We are glad to announce our paper “On the Relationship Between Robustness and Expressivity of Graph Neural Networks” by Lorenz Kummer, Wilfried Gansterer and Nils Kriege has been accepted at the 28th International Conference on Artificial Intelligence and Statistics (AISTATS) , which will take place from 3rd – May 5th, 2025 in Mai Kaho, Thailand!

Overview

Graph Neural Networks (GNNs) are widely used for learning on structured data, yet their robustness against bit-flip attacks (BFAs) remains an open challenge. This paper develops a theoretical framework to analyze how architectural choices, graph properties, and feature encodings influence both the expressivity and vulnerability of GNNs.

Key Contributions

• A formal characterization of how bit flips affect GNN expressivity.
• Theoretical bounds on Empirical validation on ten real-world datasets, examining the role of homophily, feature encoding, and activation functions.the number of bit flips required to degrade expressivity.
• Insights into why ReLU-based GNNs operating on highly homophilous graphs with low-dimensional features are particularly susceptible to BFAs.

Implications

These findings contribute to a deeper understanding of the trade-offs between robustness and expressivity in GNNs, with potential applications in secure graph-based learning.

We look forward to discussing our work with the research community at AISTATS 2025.