# Scalable Message-Passing Quantum Graph Neural Networks in the Weisfeiler-Leman Hierarchy

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 57 references that are in the map.
- First posted on arXiv 25 Jun 2026.

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

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [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)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks](https://mlsanity.com/paper/1810.02244/) (2018)
- [Barren plateaus in quantum neural network training landscapes](https://mlsanity.com/paper/1803.11173/) (2018)
- [Provably Powerful Graph Networks](https://mlsanity.com/paper/1905.11136/) (2019)
- [Invariant and Equivariant Graph Networks](https://mlsanity.com/paper/1812.09902/) (2018)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Can Graph Neural Networks Count Substructures?](https://mlsanity.com/paper/2002.04025/) (2020)
- [Barren Plateaus in Variational Quantum Computing](https://mlsanity.com/paper/2405.00781/) (2024)
- [Theory of overparametrization in quantum neural networks](https://mlsanity.com/paper/2109.11676/) (2021)
- [Does provable absence of barren plateaus imply classical simulability?](https://mlsanity.com/paper/2312.09121/) (2023)
- [Quantum Graph Neural Networks](https://mlsanity.com/paper/1909.12264/) (2019)
- [Theory for Equivariant Quantum Neural Networks](https://mlsanity.com/paper/2210.08566/) (2022)
- [Theoretical Guarantees for Permutation-Equivariant Quantum Neural Networks](https://mlsanity.com/paper/2210.09974/) (2022)
- [Equivariant quantum circuits for learning on weighted graphs](https://mlsanity.com/paper/2205.06109/) (2022)
- [An Empirical Study of Realized GNN Expressiveness](https://mlsanity.com/paper/2304.07702/) (2023)
- [Quantum Deep Hedging](https://mlsanity.com/paper/2303.16585/) (2023)
- [Quantum Graph Convolutional Neural Networks](https://mlsanity.com/paper/2107.03257/) (2021)
- [Quantum machine learning with subspace states](https://mlsanity.com/paper/2202.00054/) (2022)
- [Training-efficient density quantum machine learning](https://mlsanity.com/paper/2405.20237/) (2024)
- [Towards Quantum Graph Neural Networks: An Ego-Graph Learning Approach](https://mlsanity.com/paper/2201.05158/) (2022)
- [From Graphs to Qubits: A Critical Review of Quantum Graph Neural Networks](https://mlsanity.com/paper/2408.06524/) (2024)
- [QuIC: Quantum-Inspired Compound Adapters for Parameter Efficient Fine-Tuning](https://mlsanity.com/paper/2502.06916/) (2025)
- [Graph Neural Networks on Quantum Computers](https://mlsanity.com/paper/2405.17060/) (2024)
- [Bayesian Quantum Orthogonal Neural Networks for Anomaly Detection](https://mlsanity.com/paper/2504.18103/) (2025)
- [Scalable On-Hardware Training of Quantum Neural Networks and Application to Clinical Data Imputation](https://mlsanity.com/paper/2606.03517/) (2026)

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

- [Variational Quantum Attention for Molecular Graph Learning](https://mlsanity.com/paper/2610.04588/) (2026)

## Abstract (arXiv)

Graphs provide a natural language for relational data in chemistry, biology and optimisation. Graph neural networks (GNNs) have driven much of the recent progress in learning from such data through message passing, a single primitive that generalises convolution and attention. Quantum counterparts have been proposed, but with limited connection to message passing and few guarantees on performance or scalability. More broadly, the trainability of variational quantum circuits is a recognised bottleneck for their wide applicability, and pre-training has emerged as one way to address it. Yet for a quantum model to be useful, it must offer expressivity guarantees along with demonstrable scalability. Here we show how a quantum graph neural network can be built to perform message passing, to be permutation equivariant, and to sit at a chosen level of the Weisfeiler-Leman hierarchy, the standard measure of how finely a model can tell graphs apart. We show that, as for classical GNNs, the training can be done first on small graph instances, allowing for a pre-training that can mitigate usual training issues, and its output can be read out at a cost that stays low as the graph grows. We validate the framework in large-scale simulations of up to 56 qubits across three datasets, on synthetic graphs that ordinary message passing cannot separate, on molecular property prediction, and on the travelling salesperson problem. Our framework opens a path for near-term quantum algorithms with theoretical guarantees and practical scalability, bringing the principles of graph learning into quantum circuit design.