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

**Authors:** Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, Martin Grohe  
**arXiv:** [1810.02244](https://arxiv.org/abs/1810.02244)  
**Date:** 2018-10-04  
**Summary page:** https://www.summarizepaper.com/en/paper/1810.02244v5/

## Key points

- Graph Neural Networks (GNNs) have become popular for learning vector representations of nodes and graphs
- This study aims to investigate GNNs from a theoretical perspective and establish connections with the 1-dimensional Weisfeiler-Leman graph isomorphism heuristic (1-WL)
- GNNs possess the same expressive power as the 1-WL algorithm in distinguishing non-isomorphic subgraphs
- To overcome limitations, the authors propose k-dimensional GNNs (k-GNNs) that can capture higher-order graph structures at multiple scales
- k-GNNs outperform traditional GNNs in tasks related to graph classification and regression
- The work contributes to our understanding of GNNs by providing theoretical insights into their capabilities and limitations
- The proposed k-GNN framework extends the applicability of GNNs by considering higher order structures, leading to improved performance in various graph related tasks.

## Summary

In recent years, Graph Neural Networks (GNNs) have become a popular neural architecture for learning vector representations of nodes and graphs in a supervised manner. However, their evaluation has been mainly empirical, leaving room for further theoretical understanding. This study aims to bridge this gap by investigating GNNs from a theoretical perspective and establishing connections with the 1-dimensional Weisfeiler-Leman graph isomorphism heuristic (1-WL). The authors demonstrate that GNNs possess the same expressive power as the 1-WL algorithm when it comes to distinguishing non-isomorphic subgraphs. This finding suggests that both algorithms share similar limitations. To overcome these limitations, the authors propose a generalization of GNNs called k-dimensional GNNs (k-GNNs). Unlike traditional GNNs, k-GNNs can capture higher-order graph structures at multiple scales. These higher order structures are essential for characterizing complex networks such as social networks and molecule graphs. By incorporating this higher order information into their models, the authors show through experimental evaluations that k-GNNs outperform traditional GNNs in tasks related to graph classification and regression. Overall, this work contributes to our understanding of GNNs by providing theoretical insights into their capabilities and limitations. The proposed k-GNN framework extends the applicability of GNNs by considering higher order structures, leading to improved performance in various graph related tasks.