Message Passing on the Edge: Towards Scalable and Expressive GNNs
This addresses the problem of balancing expressiveness and scalability for researchers and practitioners in graph learning, offering a more efficient general-purpose GNN architecture.
The paper tackles the problem of limited expressiveness and scalability in Graph Neural Networks (GNNs) by proposing EB-1WL, an edge-based color-refinement test, and EB-GNN, a corresponding architecture that explicitly uses triangles during message passing. The results show that EB-1WL is significantly more expressive than 1-WL, requires near-linear time and memory, and EB-GNN outperforms simple MPNNs while remaining competitive with task-specialized GNNs with higher computational efficiency.
We propose EB-1WL, an edge-based color-refinement test, and a corresponding GNN architecture, EB-GNN. Our architecture is inspired by a classic triangle counting algorithm by Chiba and Nishizeki, and explicitly uses triangles during message passing. We achieve the following results: (1)~EB-1WL is significantly more expressive than 1-WL. Further, we provide a complete logical characterization of EB-1WL based on first-order logic, and matching distinguishability results based on homomorphism counting. (2)~In an important distinction from previous proposals for more expressive GNN architectures, EB-1WL and EB-GNN require near-linear time and memory on practical graph learning tasks. (3)~Empirically, we show that EB-GNN is a highly-efficient general-purpose architecture: It substantially outperforms simple MPNNs, and remains competitive with task-specialized GNNs while being significantly more computationally efficient.