Walking Out of the Weisfeiler Leman Hierarchy: Graph Learning Beyond Message Passing
This addresses limitations in graph neural networks for researchers and practitioners by offering a novel approach that can handle non-local features, though it is incremental as it builds on existing graph learning methods.
The authors tackled the problem of graph learning beyond message-passing GNNs by proposing CRaWl, a neural network architecture that uses random walks and 1D convolutions to detect long-range interactions, and proved its expressiveness is incomparable with the Weisfeiler-Leman algorithm and GNNs, matching state-of-the-art performance on benchmark datasets.
We propose CRaWl, a novel neural network architecture for graph learning. Like graph neural networks, CRaWl layers update node features on a graph and thus can freely be combined or interleaved with GNN layers. Yet CRaWl operates fundamentally different from message passing graph neural networks. CRaWl layers extract and aggregate information on subgraphs appearing along random walks through a graph using 1D Convolutions. Thereby it detects long range interactions and computes non-local features. As the theoretical basis for our approach, we prove a theorem stating that the expressiveness of CRaWl is incomparable with that of the Weisfeiler Leman algorithm and hence with graph neural networks. That is, there are functions expressible by CRaWl, but not by GNNs and vice versa. This result extends to higher levels of the Weisfeiler Leman hierarchy and thus to higher-order GNNs. Empirically, we show that CRaWl matches state-of-the-art GNN architectures across a multitude of benchmark datasets for classification and regression on graphs.