Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks

By Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, Martin Grohe. 2018

2,039 citations recorded by the source corpus.

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.

Subfields: Model Architectures, Graph Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Model Architectures

In Graph Learning

Citations in the corpus

Directional Message Passing for Molecular Graphs (2020, methodology): “Some recent progress has been focused on GNNs that are more powerful than the 1-Weisfeiler-Lehman test of isomorphism (Morris et al., 2019; Maron et al., 2019).”
Fast Graph Representation Learning with PyTorch Geometric (2019, background): “Similar to the concepts of convolutional and pooling layers on regular domains, GNNs are able to (hierarchically) extract localized embeddings by passing, transforming, and aggregating information (Bronstein et al., 2017; Gilmer et al., 2017; Battaglia et al., 2018; Ying et al., 2018; Morris et al.,”
Set2Graph: Learning Graphs From Sets (2020, background): “…is more intricate: some models, such as message passing (a.k.a. graph convolutional networks), are known to be non-universal (Xu et al., 2019; Morris et al., 2018; Maron et al., 2019a; Chen et al., 2019); high-order equivariant models are known to be universal (Maron et al., 2019c) but as…”
Just Jump: Dynamic Neighborhood Aggregation in Graph Neural Networks (2019, methodology): “GNNs follow a simple neighborhood aggregation procedure motivated by two major perspectives: The generalization of classical CNNs to irregular domains (Shuman et al., 2013), and their strong relations to the Weisfeiler & Lehman (1968) algorithm (Xu et al., 2019; Morris et al., 2019).”
On the equivalence between graph isomorphism testing and function approximation with GNNs (2019, methodology): “Recent works [28, 42] proposed to study the representation power of GNNs via their performance on graph isomorphism tests.”
Long Range Graph Benchmark (2022, neutral): “…to the understanding of the limitations of message passing based GNNs [22] with respect to the 1-Weisfeiler Leman (WL) isomorphism test [60, 62, 46] and the information oversquashing [2], there has been several developments of GNN and Graph Transformer architectures which have strictly greater…”
Benchmarking Graph Neural Networks (2023, methodology): “Although provably powerful in terms of graph isomorphism tests and invariant function approximation [60, 18, 66], the recent 3WLGNNs and RingGNNs were not able to outperform GCNs for our medium-scale datasets, as shown in Table 2.”
Representation Learning for Dynamic Graphs: A Survey (2019, background): “In a concurrent work, a similar result has been reported by Morris et al. (2019).”
Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks (2021, methodology): “We also show that the SWL test and MPSN are at least as powerful as the 3-WL test (Cai et al., 1992; Morris et al., 2019).”
GemNet: Universal Directional Graph Neural Networks for Molecules (2021, background): “Kondor et al. [37], Maron et al. [43], Morris et al. [45, 46] then investigated higher-order representations to circumvent this issue.”
Recipe for a General, Powerful, Scalable Graph Transformer (2022, background): “, over-smoothing [44], over-squashing [1], and expressiveness bounds [57, 42], by allowing nodes to attend to all other nodes in a graph (global attention).”
On the Bottleneck of Graph Neural Networks and its Practical Implications (2020, methodology): “Under-reaching Although GNNs can be as powerful as the Weisfeiler-Lehman graph isomorphism test (Morris et al., 2019; Xu et al., 2019; Maron et al., 2019), their expressiveness captures only a small fragment of ﬁrst-order logic (Barceló et al., 2020); the main limitation arises from the inability…”
Learning to Reason: Leveraging Neural Networks for Approximate DNF Counting (2019, methodology): “GNNs are highly expressive computational models: GNNs can be as discerning between graphs as the Weisfeiler-Lehman (WL) graph isomorphism heuristic (Xu et al. 2019; Morris et al. 2019).”
Understanding over-squashing and bottlenecks on graphs via curvature (2021, background): “Some of the drawbacks of the message passing paradigm have now been identified and formalized, including the limits of expressive power (Xu et al., 2019; Morris et al., 2019; Maron et al., 2019) and the problem of over-smoothing (NT & Maehara, 2019; Oono & Suzuki, 2020).”