Lost in Aggregation: On a Fundamental Expressivity Limit of Message-Passing Graph Neural Networks
This work identifies a critical bottleneck in graph neural networks for researchers in graph learning, showing their inherent limitations in expressivity.
The paper proves that message-passing graph neural networks (MP-GNNs) have a fundamental expressivity limit, inducing only a polynomial number of equivalence classes on graphs, while the number of non-isomorphic graphs is doubly-exponential, making them infinitely weaker than color refinement in distinguishing graphs.
We define a generic class of functions that captures most conceivable aggregations for Message-Passing Graph Neural Networks (MP-GNNs), and prove that any MP-GNN model with such aggregations induces only a polynomial number of equivalence classes on all graphs - while the number of non-isomorphic graphs is doubly-exponential (in number of vertices). Adding a familiar perspective, we observe that merely 2-iterations of Color Refinement (CR) induce at least an exponential number of equivalence classes, making the aforementioned MP-GNNs relatively infinitely weaker. Previous results state that MP-GNNs match full CR, however they concern a weak, 'non-uniform', notion of distinguishing-power where each graph size may required a different MP-GNN to distinguish graphs up to that size. Our results concern both distinguishing between non-equivariant vertices and distinguishing between non-isomorphic graphs.