Scalable Message-Passing Quantum Graph Neural Networks in the Weisfeiler-Leman Hierarchy
Abstract
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.
Related
- Exact solutions for models of evolving clustered networks with addition and deletion via age-resolved message passing
- Projective Geometric Algebra Graph Neural Networks: Edge-Modulated Message Passing via the Geometric Product
- CTMRG as a tensor-network message-passing algorithm
- Why Multi-Layer Message Passing Works: Completeness Theory for Graph Neural Network Interatomic Potentials
- Learning to Decode Concatenated Quantum Codes with Hierarchical Message Passing
BibTeX
@misc{raj2026scalable,
title = {{Scalable Message-Passing Quantum Graph Neural Networks in the Weisfeiler-Leman Hierarchy}},
author = {Snehal Raj and Brian Coyle and Léo Monbroussou and André J. Ferreira-Martins and Renato M. S. Farias and Elham Kashefi},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2606.26873},
eprint = {2606.26873},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2606.26873},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Scalable Message-Passing Quantum Graph Neural Networks in the Weisfeiler-Leman Hierarchy
AU - Snehal Raj
AU - Brian Coyle
AU - Léo Monbroussou
AU - André J. Ferreira-Martins
AU - Renato M. S. Farias
AU - Elham Kashefi
PY - 2026
DA - 2026/10/27
PB - arXiv
DO - 10.48550/arxiv.2606.26873
UR - https://arxiv.org/abs/2606.26873
AB - 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.
ER -