On the Relationship Between Robustness and Expressivity of Graph Neural Networks
This addresses security risks for GNNs in expressivity-critical applications, though it is incremental as it builds on existing robustness and expressivity research.
The paper tackles the vulnerability of Graph Neural Networks (GNNs) to bit-flip attacks by analyzing how architectural features and graph properties affect their expressivity, finding that ReLU-activated GNNs on homophilous graphs with low-dimensional features are most susceptible, with empirical validation on ten datasets.
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.