# Twin Weisfeiler-Lehman: High Expressive GNNs for Graph Classification

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 32 references that are in the map.
- First posted on arXiv 22 Mar 2022.

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

- [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)
- [Neural Message Passing for Quantum Chemistry](https://mlsanity.com/paper/1704.01212/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Hierarchical Graph Representation Learning with Differentiable Pooling](https://mlsanity.com/paper/1806.08804/) (2018)
- [Self-Attention Graph Pooling](https://mlsanity.com/paper/1904.08082/) (2019)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [A Fair Comparison of Graph Neural Networks for Graph Classification](https://mlsanity.com/paper/1912.09893/) (2019)
- [The Surprising Power of Graph Neural Networks with Random Node Initialization](https://mlsanity.com/paper/2010.01179/) (2020)
- [Identity-aware Graph Neural Networks](https://mlsanity.com/paper/2101.10320/) (2021)
- [A Survey on Graph Kernels](https://mlsanity.com/paper/1903.11835/) (2019)
- [Nested Graph Neural Networks](https://mlsanity.com/paper/2110.13197/) (2021)
- [A Survey on The Expressive Power of Graph Neural Networks](https://mlsanity.com/paper/2003.04078/) (2020)
- [Computing Graph Neural Networks: A Survey from Algorithms to Accelerators](https://mlsanity.com/paper/2010.00130/) (2020)
- [k-hop Graph Neural Networks](https://mlsanity.com/paper/1907.06051/) (2019)
- [Graph Neural Networks: Taxonomy, Advances and Trends](https://mlsanity.com/paper/2012.08752/) (2020)

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

- [The Expressive Power of Graph Neural Networks: A Survey](https://mlsanity.com/paper/2308.08235/) (2023)
- [Demystifying Higher-Order Graph Neural Networks](https://mlsanity.com/paper/2406.12841/) (2024)
- [Improving Subgraph Matching by Combining Algorithms and Graph Neural Networks](https://mlsanity.com/paper/2507.20226/) (2025)

## Abstract (arXiv)

The expressive power of message passing GNNs is upper-bounded by Weisfeiler-Lehman (WL) test. To achieve high expressive GNNs beyond WL test, we propose a novel graph isomorphism test method, namely Twin-WL, which simultaneously passes node labels and node identities rather than only passes node label as WL. The identity-passing mechanism encodes complete structure information of rooted subgraph, and thus Twin-WL can offer extra power beyond WL at distinguishing graph structures. Based on Twin-WL, we implement two Twin-GNNs for graph classification via defining readout function over rooted subgraph: one simply readouts the size of rooted subgraph and the other readouts rich structure information of subgraph following a GNN-style. We prove that the two Twin-GNNs both have higher expressive power than traditional message passing GNNs. Experiments also demonstrate the Twin-GNNs significantly outperform state-of-the-art methods at the task of graph classification.