Continuous-Time Quantum Walks based Graph Neural Network

Yuliang Zhan; Zefeng Gao; Jian Li; Yang Liu; Hao sun

cs.AIAug 21, 2026

Continuous-Time Quantum Walks based Graph Neural Network

Authors: Yuliang Zhan, Zefeng Gao, Jian Li, Yang Liu, Hao sun

Organizations: Renmin University of China Beijing, China

Abstract

Graph Neural Networks (GNNs) are widely used on graph-structured data, but most suffer from two key weaknesses. First, message passing behaves as a low-pass filter under the homophily assumption, leading to poor performance on heterophilic graphs. Second, stacking layers drives node features toward constants, causing over-smoothing. Existing methods usually address these issues separately, while the few joint solutions rely largely on empirical heuristics, and many over-smoothing remedies sacrifice model expressiveness. We propose CTQW-GNN, a GNN based on Continuous-Time Quantum Walks (CTQW), to address both issues with theoretical justification. Its design exploits two properties of the CTQW propagator $e^{-\mathrm{i}Ht}$ . First, it is unitary and has eigenvalues on the unit circle, so no frequency component is damped, counteracting the low-pass bias. Second, unitarity preserves feature norms and prevents the Dirichlet energy from decaying exponentially with depth, thereby mitigating over-smoothing. CTQW-GNN combines three complementary aggregation modules. CTQW-based Aggregation evolves node features through the unitary propagator, preserving mid- and high-frequency signals for heterophilic graphs while preventing Dirichlet-energy collapse. CTQW-Attention Aggregation constructs a multi-hop neighbor graph from CTQW amplitudes and applies attention over it, enabling access to distant homophilic nodes missed by single-hop aggregation. LF Aggregation uses a standard low-pass GAT branch to retain strong performance on homophilic graphs, where pure CTQW aggregation can be suboptimal. We further provide a spectral-gap analysis explaining energy preservation and a Lieb--Robinson-type bound that gives a principled rule for selecting the walk time $t$ .

Figures & tables

Figure 1. The overview of CTQW-GNN for heterophilic graphs and over-smoothing problem. (a). We define an undirected graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ , with $\mathcal{V}$ as the node set of size $N$ and $\mathcal{E}$ as the edge set. (b). We conduct a CTQW on the original graph $\mathcal{G}$ to obtain a new edge set $\mathcal{E}_{CTQW}$ with edge weights $W_{\mathcal{E}_{CTQW}}$ ; both connectivity relations $\mathcal{E}$ and $\mathcal{E}_{CTQW}$ share the same node features $X^{(n)}$ . (c). We employ three distinct information aggregation methods proposed in this paper to derive three types of node information: $X^{(n)}_{LF}$ , $X^{(n)}_{CTQW}$ and $X^{(n)}_{Attention}$ . through the three types of features, we obtain the node features $X^{(n+1)}$ for the next layer. The details of the formula are provided in Section 4 .

Panel of Figure 2 — Figure 2. Probability Distribution Comparison Between CTQW and CTRW on a Path (starting from node 126, $t=40$ ).

Datasets	Roman-empire	Amazon-ratings	Minesweeper	Tolokers	Actor	Texas	Wiki-cooc	Chameleon	Squirrel
Homophily Ratio	0.05	0.38	0.68	0.59	0.22	0.11	0.34	0.24	0.22
ResNet	$65.88{\scriptstyle\pm 0.38}$	$45.90{\scriptstyle\pm 0.52}$	$50.89{\scriptstyle\pm 1.39}$	$72.95{\scriptstyle\pm 1.06}$	$28.75{\scriptstyle\pm 0.88}$	$80.81{\scriptstyle\pm 4.75}$	$89.36{\scriptstyle\pm 0.71}$	$49.52{\scriptstyle\pm 1.73}$	$33.88{\scriptstyle\pm 1.79}$
GCN	$73.69{\scriptstyle\pm 0.74}$	$48.70{\scriptstyle\pm 0.73}$	$89.75{\scriptstyle\pm 0.52}$	$83.64{\scriptstyle\pm 0.67}$	$30.59{\scriptstyle\pm 0.23}$	$55.14{\scriptstyle\pm 5.16}$	$91.01{\scriptstyle\pm 0.69}$	$50.18{\scriptstyle\pm 3.29}$	$39.06{\scriptstyle\pm 1.52}$
GAT	$81.02{\scriptstyle\pm 0.46}$	$47.95{\scriptstyle\pm 0.58}$	$92.10{\scriptstyle\pm 0.67}$	$83.98{\scriptstyle\pm 0.57}$	$35.98{\scriptstyle\pm 0.23}$	$52.16{\scriptstyle\pm 6.63}$	$92.44{\scriptstyle\pm 0.80}$	$45.02{\scriptstyle\pm 1.75}$	$32.21{\scriptstyle\pm 1.63}$
SAGE	$85.74{\scriptstyle\pm 0.67}$	$53.63{\scriptstyle\pm 0.39}$	$93.51{\scriptstyle\pm 0.57}$	$82.43{\scriptstyle\pm 0.44}$	$36.37{\scriptstyle\pm 0.21}$	$79.03{\scriptstyle\pm 1.20}$	$93.60{\scriptstyle\pm 0.31}$	$50.18{\scriptstyle\pm 1.78}$	$35.83{\scriptstyle\pm 1.32}$
CDE-GRAND	$91.64{\scriptstyle\pm 0.28}$	$47.63{\scriptstyle\pm 0.43}$	${95.50{\scriptstyle\pm 5.23}}$	$83.98{\scriptstyle\pm 0.57}$	$34.72{\scriptstyle\pm 1.40}$	$86.22{\scriptstyle\pm 3.30}$	$97.99{\scriptstyle\pm 0.38}$	$68.45{\scriptstyle\pm 2.47}$	$55.04{\scriptstyle\pm 1.73}$

Table 1. Results of node classification tasks on different heterophilic datasets: mean ± std (%). The best result (

\alpha

) for each dataset is highlight in bold and the second best (

\beta

) underlined, where Promotion is defined between these two values, i.e.,

(\alpha-\beta)/\beta\times 100\%

Datasets	Cora	Citeseer	PubMed	Computer	Photo
Homophily Ratio	0.81	0.72	0.79	0.78	0.83
ResNet	$76.44{\scriptstyle\pm 0.30}$	$76.25{\scriptstyle\pm 0.28}$	$86.43{\scriptstyle\pm 0.13}$	$84.68{\scriptstyle\pm 0.78}$	$91.49{\scriptstyle\pm 0.30}$
GCN	$87.78{\scriptstyle\pm 0.96}$	$81.39{\scriptstyle\pm 1.23}$	$88.90\textpm{\scriptstyle\pm 0.32}$	$83.55{\scriptstyle\pm 0.38}$	$89.30{\scriptstyle\pm 0.44}$
GAT	$76.70{\scriptstyle\pm 0.42}$	$67.20{\scriptstyle\pm 0.46}$	$83.28{\scriptstyle\pm 0.12}$	$85.36{\scriptstyle\pm 0.50}$	$90.81{\scriptstyle\pm 0.22}$
SAGE	$86.58{\scriptstyle\pm 0.26}$	$78.24{\scriptstyle\pm 0.30}$	$86.85{\scriptstyle\pm 0.11}$	$83.11{\scriptstyle\pm 0.23}$	$90.51{\scriptstyle\pm 0.25}$
CDE-GRAND	$87.19{\scriptstyle\pm 1.44}$	$80.04{\scriptstyle\pm 1.75}$	$90.05{\scriptstyle\pm 0.64}$	$81.95{\scriptstyle\pm 0.43}$	$88.27{\scriptstyle\pm 1.94}$

Table 2. Results of node classification tasks on different homophilic datasets: mean ± std (%).

Panel of Figure 3 — Figure 3. Performance on node subgroups.

Figure 4. (a). Dirichlet energy of graph. Left: Minesweeper results; Right: Amazon-ratings results. (b.) Accuracy of CTQW-GNN. Figure a and b are the performance of GNN models with different depth. In Figure b , the metric is ROC-AUC for the Minesweeper dataset and accuracy for the other datasets. "w/o" represents the removal of the corresponding aggregation method. (c). Impact of information aggregation methods. The axes denote the accuracy of models on Minesweeper dataset.

$t$	$10^{-6}$	$10^{-5}$	$10^{-4}$	$10^{-3}$	$10^{-2}$	$10^{-1}$	$1$	$10$	$10^{2}$
Cora	86.74	87.05	87.62	88.93	90.27	91.31	91.18	88.52	84.81
Roman-empire	84.55	84.92	85.78	93.34	94.13	93.88	92.20	88.46	85.59
Amazon-ratings	50.71	51.04	51.92	53.59	54.07	53.90	53.21	50.93	48.66
Minesweeper	87.79	88.05	89.20	96.80	97.32	97.07	94.93	92.30	89.63

Table 3. Pserformance of CTQW-GNN under different walk time

t

Dataset	$10^{-4}$	$10^{-3}$	$5\!\times\!10^{-3}$	$10^{-2}$	$5\!\times\!10^{-2}$
Amazon-ratings	53.92	54.03	54.07	53.74	51.18
Minesweeper	97.28	97.21	97.32	96.95	94.40
Roman-empire	94.09	94.03	94.13	93.71	90.96
Wiki-cooc	99.56	99.58	99.65	99.22	96.48

Table 4. Effect of sparsification threshold

\epsilon

GNN Oversmoothing

See all 19 papers

May 10, 2026

CTQWformer: A CTQW-based Transformer for Graph Classification

Graph Neural Networks (GNN) and Transformer-based architectures have achieved remarkable progress in graph learning, yet they still struggle to capture both global structural dependencies and model the dynamic information propagation. In this paper, we propose CTQWformer, a hybrid graph learning framework that integrates continuous-time quantum walks (CTQW) with GNN. CTQWformer employs a trainable Hamiltonian that fuses graph topology and node features, enabling physically grounded modeling of quantum walk dynamics that captures rich and intricate graph structure information. The extracted CTQW-based representations are incorporated into two complementary modules:(i) a Graph Transformer module that embeds final-time propagation probabilities as structural biases in the self-attention mechanism, and (ii) a Graph Recurrent Module that captures temporal evolution patterns with bidirectional recurrent networks. Extensive experiments on benchmark graph classification datasets demonstrate that CTQWformer outperforms graph kernel and GNN-based methods, demonstrating the potential of integrating quantum dynamics into trainable deep learning frameworks for graph representation learning. To the best of our knowledge, CTQWformer is the first hybrid CTQW-based Transformer, integrating CTQW-derived structural bias with temporal evolution modeling to advance graph learning.

Zhan Li, Wuqing Yu, Yusen Wu +1

school of Artificial Intelligence, Beijing Normal University, Beijing, China

Graph Representation Learning Quantum-Inspired ML Graph Classification Graph Transformer

Ask PDF

Jun 25, 2026

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

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.

Snehal Raj, Brian Coyle, Léo Monbroussou +3

1LIP6, CNRS, Sorbonne Universit´e, Paris, France · 2QC Ware, Palo Alto, USA and Paris, France · School of Informatics, University of Edinburgh, Edinburgh, UK +3

GNN Expressivity Message Passing Neural Networks Quantum Neural Networks

Ask PDF

Sep 17, 2026

Quantum Graph Convolutional Networks: Implementation and Trainability Analysis

Graph Neural Networks (GNNs) achieve state-of-the-art performance on graph-structured data, but training and inference on large graphs are often bottlenecked by memory constraints and sparse linear-algebra workloads. Quantum computing offers an alternative set of primitives that may improve scalability for graph learning. Building on the quantum graph neural network (QGNN) framework of Liao et al., this work implements two representative architectures --- the Simplified Graph Convolution (SGC) and Linear Graph Convolution (LGC) models --- and evaluates them on open benchmark graph datasets and semi-supervised learning tasks using quantum simulation. We compare predictive performance and optimization behavior against classical baselines, showing that the quantum models achieve competitive performance with fewer parameters. Finally, we present a cost gradient analysis that identifies the tasks for which the models showcased are trainable. This is followed by a classical simulability study to find regimes in which the proposed circuits remain robust during training.

Paul San Sebastian Sein, Theodor Iosif, Tilen G. Limbäck-Stokin +2

Ikerlan Technology Research Centre, Basque Research and Technology Alliance (BRTA), Arrasate-Mondragon, Spain · University of the Basque Country/Euskal Herriko Unibertsitatea-EHU · Quantum Learning Labs, Department of Computer Science, University College London, London, United Kingdom +4

Graph-Based Semi-Supervised Learning Variational Quantum Circuits Quantum Circuit Trainability Quantum Neural Networks

Ask PDF

Abstract

GNN Oversmoothing

Explore similar work

CTQWformer: A CTQW-based Transformer for Graph Classification

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

Quantum Graph Convolutional Networks: Implementation and Trainability Analysis