Demystifying MPNNs: Message Passing as Merely Efficient Matrix Multiplication
This work addresses a foundational problem for researchers in graph machine learning by offering incremental theoretical insights into GNN behavior.
The paper tackles the lack of theoretical understanding in Graph Neural Networks (GNNs) by analyzing their behavior, showing that gradient issues, not just over-smoothing, impact performance in sparse graphs for deeper models, and providing a framework linking empirical success to theory.
While Graph Neural Networks (GNNs) have achieved remarkable success, their design largely relies on empirical intuition rather than theoretical understanding. In this paper, we present a comprehensive analysis of GNN behavior through three fundamental aspects: (1) we establish that \textbf{$k$-layer} Message Passing Neural Networks efficiently aggregate \textbf{$k$-hop} neighborhood information through iterative computation, (2) analyze how different loop structures influence neighborhood computation, and (3) examine behavior across structure-feature hybrid and structure-only tasks. For deeper GNNs, we demonstrate that gradient-related issues, rather than just over-smoothing, can significantly impact performance in sparse graphs. We also analyze how different normalization schemes affect model performance and how GNNs make predictions with uniform node features, providing a theoretical framework that bridges the gap between empirical success and theoretical understanding.