Provably Powerful Graph Networks

By Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, Yaron Lipman. 2019

683 citations recorded by the source corpus.

Recently, the Weisfeiler-Lehman (WL) graph isomorphism test was used to measure the expressive power of graph neural networks (GNN). It was shown that the popular message passing GNN cannot distinguish between graphs that are indistinguishable by the 1-WL test (Morris et al. 2018; Xu et al. 2019). Unfortunately, many simple instances of graphs are indistinguishable by the 1-WL test. In search for more expressive graph learning models we build upon the recent k-order invariant and equivariant graph neural networks (Maron et al. 2019a,b) and present two results: First, we show that such k-order networks can distinguish between non-isomorphic graphs as good as the k-WL tests, which are provably stronger than the 1-WL test for k>2. This makes these models strictly stronger than message passing models. Unfortunately, the higher expressiveness of these models comes with a computational cost of processing high order tensors. Second, setting our goal at building a provably stronger, simple and scalable model we show that a reduced 2-order network containing just scaled identity operator, augmented with a single quadratic operation (matrix multiplication) has a provable 3-WL expressive power. Differently put, we suggest a simple model that interleaves applications of standard Multilayer-Perceptron (MLP) applied to the feature dimension and matrix multiplication. We validate this model by presenting state of the art results on popular graph classification and regression tasks. To the best of our knowledge, this is the first practical invariant/equivariant model with guaranteed 3-WL expressiveness, strictly stronger than message passing models.

Subfields: Artificial Intelligence, Materials Chemistry, Graph Learning, Statistical Learning Theory

How researchers see this paper

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

In Artificial Intelligence

In Materials Chemistry

In Graph Learning

In Statistical Learning Theory

Citations in the corpus

Directional Message Passing for Molecular Graphs (2020, methodology): “We use 6 state-of-the-art models for comparison: SchNet (Schütt et al., 2017), PhysNet (results based on the reference implementation) (Unke & Meuwly, 2019), provably powerful graph networks (PPGN, results provided by the original authors) (Maron et al., 2019), MEGNet-simple (without auxiliary infor”
Set2Graph: Learning Graphs From Sets (2020, methodology): “We denote for an arbitrary tensor A ∈ R a × b ×···× c its inﬁnity norm by For an arbitrary (cid:15) > 0 , there exists an equivariant polynomial This is a standard lemma, similar to (Yarotsky, 2018; Maron et al., 2019c; Segol & Lipman, 2020); for completeness we provide a proof in the supplementary.”
Combinatorial optimization and reasoning with graph neural networks (2021, background): “…the Trade-off in Scalability, Expressivity, and Generalization Current GNN architectures might miss crucial structural patterns in the data [Morris et al. , 2019; Xu et al. , 2019a], while more expressive approaches [Morris et al. , 2020; Maron et al. , 2019] do not scale to large-scale inputs.”
What graph neural networks cannot learn: depth vs width (2019, background): “This result compliments recent universality results (Maron et al., 2019b; Keriven & Peyr ´ e, 2019) that considered approximation (rather than computability) over speciﬁc classes of functions (invariant and equivariant) and particular architectures.”
Benchmarking Graph Neural Networks (2023, methodology): “[58] Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman.”
Graph Representation Learning (2020, methodology): “Another line of work that is motivated by the idea of building GNNs that are as powerful as the k-WL test are the invariant and equivariant GNNs proposed by Maron et al. [2019]. A crucial aspect of message-passing GNNs (MP-GNNs; as defined in Theorem 7.”
Graph Neural Networks with Learnable Structural and Positional Representations (2021, methodology): “Another approach is to compute higher-order node-tuple aggregations such as in WL-based GNNs (Maron et al., 2019; Chen et al., 2019); though these models are computationally more expensive to scale than MP-GNNs, even for medium-sized graphs (Dwivedi et al.”
Towards a practical k-dimensional Weisfeiler-Leman algorithm (2019, background): “Recently, some connections to neural networks for graphs [25, 29] and dimension reduction in linear programming [16] have been shown.”
Graph Information Bottleneck (2020, neutral): “Recently, many works have been focusing on developing more powerful GNNs [8–13], in a sense that they can fit more complex graph-structured data.”
Discovering Invariant Rationales for Graph Neural Networks (2022, methodology): “Also, more powerful graph encoders like RingGNN (Chen et al., 2019) and 3WLGNN (Maron et al., 2019) can be used as the graph encoders to distinguish different substructures better.”
GemNet: Universal Directional Graph Neural Networks for Molecules (2021, background): “[42] showed that so-called folklore GNNs are the most expressive GNNs for a given tensor order.”
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…”
Generalization and Representational Limits of Graph Neural Networks (2020, background): “Maron et al. (2019c); Keriven and Peyr´e (2019) proved universality theorems for a speciﬁc class of invariant and equiv-ariant networks, respectively.”
Can graph neural networks count substructures? (2020, methodology): “Note that there has been an different definition of WL in the literature, sometimes known as Folklore Weisfeiler-Lehman (FWL), with different properties [39, 44].”
Identity-aware Graph Neural Networks (2021, methodology): “Recently, many neural networks have been proposed with expressive power beyond the 1-WL test, including (Chen et al. 2019; Maron et al. 2019a; Murphy et al. 2019; You, Ying, and Leskovec 2019; Li et al. 2020).”
Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings (2019, methodology): “Later, this was reﬁned in (Maron et al., 2019a) by introducing k -order invariant graph networks ( k - IGN ), based on Maron et al. (Maron et al., 2019b), and references therein, which are equivalent to the folklore variant of the k - WL (Grohe, 2017) in terms of distinguishing non-isomorphic…”