What Expressivity Theory Misses: Message Passing Complexity for GNNs
This addresses the gap between theoretical expressivity and practical capabilities in GNNs for researchers and practitioners, offering a more nuanced framework.
The paper argues that expressivity theory is insufficient for analyzing Graph Neural Networks (GNNs) and proposes Message Passing Complexity (MPC) as a continuous measure to quantify task difficulty, showing that its predictions correlate with empirical performance on fundamental tasks.
Expressivity theory, characterizing which graphs a GNN can distinguish, has become the predominant framework for analyzing GNNs, with new models striving for higher expressivity. However, we argue that this focus is misguided: First, higher expressivity is not necessary for most real-world tasks as these tasks rarely require expressivity beyond the basic WL test. Second, expressivity theory's binary characterization and idealized assumptions fail to reflect GNNs' practical capabilities. To overcome these limitations, we propose Message Passing Complexity (MPC): a continuous measure that quantifies the difficulty for a GNN architecture to solve a given task through message passing. MPC captures practical limitations like over-squashing while preserving the theoretical impossibility results from expressivity theory, effectively narrowing the gap between theory and practice. Through extensive validation on fundamental GNN tasks, we show that MPC's theoretical predictions correlate with empirical performance, successfully explaining architectural successes and failures. Thereby, MPC advances beyond expressivity theory to provide a more powerful and nuanced framework for understanding and improving GNN architectures.