Expressivity of Graph Neural Networks Through the Lens of Adversarial
  Robustness
Francesco Campi Lukas Gosch Tom Wollschläger Yan Scholten Stephan Günnemann
We perform the first adversarial robustness study into Graph Neural Networks
(GNNs) that are provably more powerful than traditional Message Passing Neural
Networks (MPNNs). In particular, we use adversarial robustness as a tool to
uncover a significant gap between their theoretically possible and empirically
achieved expressive power. To do so, we focus on the ability of GNNs to count
specific subgraph patterns, which is an established measure of expressivity,
and extend the concept of adversarial robustness to this task. Based on this,
we develop efficient adversarial attacks for subgraph counting and show that
more powerful GNNs fail to generalize even to small perturbations to the
graph's structure. Expanding on this, we show that such architectures also fail
to count substructures on out-of-distribution graphs.