A Novel Higher-order Weisfeiler-Lehman Graph Convolution
This addresses a fundamental limitation in graph neural networks for researchers and practitioners, though it appears incremental as it builds on existing WL tests.
The paper tackled the limited discriminative power of current GNNs by proposing a novel graph convolution operator based on the 2-dimensional Weisfeiler-Lehman test, showing it is more discriminative theoretically and competitive on benchmarks.
Current GNN architectures use a vertex neighborhood aggregation scheme, which limits their discriminative power to that of the 1-dimensional Weisfeiler-Lehman (WL) graph isomorphism test. Here, we propose a novel graph convolution operator that is based on the 2-dimensional WL test. We formally show that the resulting 2-WL-GNN architecture is more discriminative than existing GNN approaches. This theoretical result is complemented by experimental studies using synthetic and real data. On multiple common graph classification benchmarks, we demonstrate that the proposed model is competitive with state-of-the-art graph kernels and GNNs.