Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks
In recent years, graph neural networks (GNNs) have emerged as a powerful neural architecture to learn vector representations of nodes and graphs in a supervised, end-to-end fashion. Up to now, GNNs have only been evaluated empirically -- showing promising results. The following work investigates GNNs from a theoretical point of view and relates them to the $1$-dimensional Weisfeiler-Leman graph isomorphism heuristic ($1$-WL). We show that GNNs have the same expressiveness as the $1$-WL in terms of distinguishing non-isomorphic (sub-)graphs. Hence, both algorithms also have the same shortcomings. Based on this, we propose a generalization of GNNs, so-called $k$-dimensional GNNs ($k$-GNNs), which can take higher-order graph structures at multiple scales into account. These higher-order structures play an essential role in the characterization of social networks and molecule graphs. Our experimental evaluation confirms our theoretical findings as well as confirms that higher-order information is useful in the task of graph classification and regression.
Code (1)
Tasks
Graph ClassificationSimilar Papers 제목 키워드 기반
Walking Out of the Weisfeiler Leman Hierarchy: Graph Learning Beyond Message Passing
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…
Graph ClassificationGraph LearningGraph RegressionregressionWeisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings
Graph kernels based on the $1$-dimensional Weisfeiler-Leman algorithm and corresponding neural architectures recently emerged as powerful tools for (supervised) learning with graphs. However, due to the purely local natu…
General ClassificationGraph ClassificationGraph LearningGraph RegressionWeisfeiler and Leman Go Walking: Random Walk Kernels Revisited
Random walk kernels have been introduced in seminal work on graph learning and were later largely superseded by kernels based on the Weisfeiler-Leman test for graph isomorphism. We give a unified view on both classes of …
Graph LearningThe Logic of Graph Neural Networks
Graph neural networks (GNNs) are deep learning architectures for machine learning problems on graphs. It has recently been shown that the expressiveness of GNNs can be characterised precisely by the combinatorial Weisfei…
BIG-bench Machine LearningDescriptiveScaling Higher-Order Graph Learning with Maximal Clique Complexes
Graph neural networks (GNNs) are limited to modeling pairwise interactions, while higher-order models based on cell complexes achieve greater expressivity but often suffer from poor scalability. We introduce simplified a…
Computational EfficiencyGraph Learning