Attacking Graph Neural Networks with Bit Flips: Weisfeiler and Leman Go Indifferent

Prior attacks on graph neural networks have mostly focused on graph poisoning
and evasion, neglecting the network’s weights and biases. Traditional weight-
based fault injection attacks, such as bit flip attacks used for convolutional neural
networks, do not consider the unique properties of graph neural networks. We pro-
pose the Injectivity Bit Flip Attack, the first bit flip attack designed specifically for
graph neural networks. Our attack targets the learnable neighborhood aggregation
functions in quantized message passing neural networks, degrading their ability to
distinguish graph structures and losing the expressivity of the Weisfeiler-Lehman
test. Our findings suggest that exploiting mathematical properties specific to cer-
tain graph neural network architectures can significantly increase their vulnerabil-
ity to bit flip attacks. Injectivity Bit Flip Attacks can degrade the maximal expres-
sive Graph Isomorphism Networks trained on various graph property prediction
datasets to random output by flipping only a small fraction of the network’s bits,
demonstrating its higher destructive power compared to a bit flip attack transferred
from convolutional neural networks. Our attack is transparent and motivated by
theoretical insights which are confirmed by extensive empirical results.