# Two-Dimensional Weisfeiler-Lehman Graph Neural Networks for Link Prediction

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

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 40 references that are in the map.
- First posted on arXiv 20 Jun 2022.

## Builds on (most cited first, 23 of 23)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Optuna: A Next-generation Hyperparameter Optimization Framework](https://mlsanity.com/paper/1907.10902/) (2019)
- [node2vec: Scalable Feature Learning for Networks](https://mlsanity.com/paper/1607.00653/) (2016)
- [Modeling Relational Data with Graph Convolutional Networks](https://mlsanity.com/paper/1703.06103/) (2017)
- [Variational Graph Auto-Encoders](https://mlsanity.com/paper/1611.07308/) (2016)
- [Complex Embeddings for Simple Link Prediction](https://mlsanity.com/paper/1606.06357/) (2016)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Learning Convolutional Neural Networks for Graphs](https://mlsanity.com/paper/1605.05273/) (2016)
- [Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction](https://mlsanity.com/paper/2106.06935/) (2021)
- [A Review of Relational Machine Learning for Knowledge Graphs](https://mlsanity.com/paper/1503.00759/) (2015)
- [Inductive Relation Prediction by Subgraph Reasoning](https://mlsanity.com/paper/1911.06962/) (2019)
- [Identity-aware Graph Neural Networks](https://mlsanity.com/paper/2101.10320/) (2021)
- [Hyperspherical Variational Auto-Encoders](https://mlsanity.com/paper/1804.00891/) (2018)
- [On the equivalence between graph isomorphism testing and function approximation with GNNs](https://mlsanity.com/paper/1905.12560/) (2019)
- [Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning](https://mlsanity.com/paper/2010.16103/) (2020)
- [Weisfeiler and Leman go Machine Learning: The Story so far](https://mlsanity.com/paper/2112.09992/) (2021)
- [Line Graph Neural Networks for Link Prediction](https://mlsanity.com/paper/2010.10046/) (2020)
- [Inductive Matrix Completion Based on Graph Neural Networks](https://mlsanity.com/paper/1904.12058/) (2019)
- [Link Prediction with Persistent Homology: An Interactive View](https://mlsanity.com/paper/2102.10255/) (2021)
- [Neural Link Prediction with Walk Pooling](https://mlsanity.com/paper/2110.04375/) (2021)

## Built on by (most cited first, 6 of 6)

- [FakeEdge: Alleviate Dataset Shift in Link Prediction](https://mlsanity.com/paper/2211.15899/) (2022)
- [Foundations and Frontiers of Graph Learning Theory](https://mlsanity.com/paper/2407.03125/) (2024)
- [Expressive Higher-Order Link Prediction through Hypergraph Symmetry Breaking](https://mlsanity.com/paper/2402.11339/) (2024)
- [Attribute-Enhanced Similarity Ranking for Sparse Link Prediction](https://mlsanity.com/paper/2412.00261/) (2024)
- [On the Expressive Power of GNNs to Solve Linear SDPs](https://mlsanity.com/paper/2604.27786/) (2026)
- [Edge-Level Automorphism in GNNs: A Quantitative Framework and Effective Designs For Link Prediction](https://mlsanity.com/paper/2609.34729/) (2026)

## Abstract (arXiv)

Link prediction is one important application of graph neural networks (GNNs). Most existing GNNs for link prediction are based on one-dimensional Weisfeiler-Lehman (1-WL) test. 1-WL-GNNs first compute node representations by iteratively passing neighboring node features to the center, and then obtain link representations by aggregating the pairwise node representations. As pointed out by previous works, this two-step procedure results in low discriminating power, as 1-WL-GNNs by nature learn node-level representations instead of link-level. In this paper, we study a completely different approach which can directly obtain node pair (link) representations based on textittwo-dimensional Weisfeiler-Lehman (2-WL) tests. 2-WL tests directly use links (2-tuples) as message passing units instead of nodes, and thus can directly obtain link representations. We theoretically analyze the expressive power of 2-WL tests to discriminate non-isomorphic links, and prove their superior link discriminating power than 1-WL. Based on different 2-WL variants, we propose a series of novel 2-WL-GNN models for link prediction. Experiments on a wide range of real-world datasets demonstrate their competitive performance to state-of-the-art baselines and superiority over plain 1-WL-GNNs.