# Provably Powerful Graph Networks

arXiv: https://arxiv.org/abs/1905.11136 · HTML: https://mlsanity.com/paper/1905.11136/

## Key facts

- Cited by 389 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 27 May 2019.

## Built on by (most cited first, 30 of 389)

- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Recipe for a General, Powerful, Scalable Graph Transformer](https://mlsanity.com/paper/2205.12454/) (2022)
- [DiGress: Discrete Denoising diffusion for graph generation](https://mlsanity.com/paper/2209.14734/) (2022)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [Rethinking Graph Transformers with Spectral Attention](https://mlsanity.com/paper/2106.03893/) (2021)
- [GemNet: Universal Directional Graph Neural Networks for Molecules](https://mlsanity.com/paper/2106.08903/) (2021)
- [Graph Neural Networks with Learnable Structural and Positional Representations](https://mlsanity.com/paper/2110.07875/) (2021)
- [Do Transformers Really Perform Bad for Graph Representation?](https://mlsanity.com/paper/2106.05234/) (2021)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Weisfeiler and Lehman Go Topological: Message Passing Simplicial Networks](https://mlsanity.com/paper/2103.03212/) (2021)
- [Weisfeiler and Lehman Go Cellular: CW Networks](https://mlsanity.com/paper/2106.12575/) (2021)
- [Multi-Task Learning as a Bargaining Game](https://mlsanity.com/paper/2202.01017/) (2022)
- [Large-Scale Chemical Language Representations Capture Molecular Structure and Properties](https://mlsanity.com/paper/2106.09553/) (2021)
- [Identity-aware Graph Neural Networks](https://mlsanity.com/paper/2101.10320/) (2021)
- [Discovering Invariant Rationales for Graph Neural Networks](https://mlsanity.com/paper/2201.12872/) (2022)
- [Pure Transformers are Powerful Graph Learners](https://mlsanity.com/paper/2207.02505/) (2022)
- [Graph neural networks for materials science and chemistry](https://mlsanity.com/paper/2208.09481/) (2022)
- [How Powerful are Spectral Graph Neural Networks](https://mlsanity.com/paper/2205.11172/) (2022)
- [Spherical Message Passing for 3D Graph Networks](https://mlsanity.com/paper/2102.05013/) (2021)
- [Frame Averaging for Invariant and Equivariant Network Design](https://mlsanity.com/paper/2110.03336/) (2021)
- [From Stars to Subgraphs: Uplifting Any GNN with Local Structure Awareness](https://mlsanity.com/paper/2110.03753/) (2021)
- [Equivariant Subgraph Aggregation Networks](https://mlsanity.com/paper/2110.02910/) (2021)
- [Nested Graph Neural Networks](https://mlsanity.com/paper/2110.13197/) (2021)
- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks](https://mlsanity.com/paper/2111.06283/) (2021)
- [Understanding and Extending Subgraph GNNs by Rethinking Their Symmetries](https://mlsanity.com/paper/2206.11140/) (2022)
- [Transformer for Graphs: An Overview from Architecture Perspective](https://mlsanity.com/paper/2202.08455/) (2022)
- [Equivariant Architectures for Learning in Deep Weight Spaces](https://mlsanity.com/paper/2301.12780/) (2023)
- [Not too little, not too much: a theoretical analysis of graph (over)smoothing](https://mlsanity.com/paper/2205.12156/) (2022)
- [Breaking the Limits of Message Passing Graph Neural Networks](https://mlsanity.com/paper/2106.04319/) (2021)

## Abstract (arXiv)

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.