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

CTQWformer: A CTQW-based Transformer for Graph Classification
May 10, 2026Zhan Li, Wuqing Yu, Yusen Wu +1Graph Representation Learning Quantum-Inspired ML
school of Artificial Intelligence, Beijing Normal University, Beijing, China
Scalable Message-Passing Quantum Graph Neural Networks in the Weisfeiler-Leman Hierarchy
Jun 25, 2026Snehal Raj, Brian Coyle, Léo Monbroussou +3GNN Expressivity Message Passing Neural Networks
1LIP6, CNRS, Sorbonne Universit´e, Paris, France · 2QC Ware, Palo Alto, USA and Paris, France · School of Informatics, University of Edinburgh, Edinburgh, UK +3
Quantum Graph Convolutional Networks: Implementation and Trainability Analysis
Sep 17, 2026Paul San Sebastian Sein, Theodor Iosif, Tilen G. Limbäck-Stokin +2Graph-Based Semi-Supervised Learning Variational Quantum Circuits
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

May 10, 2026J/K move · Enter open · S save

CTQWformer: A CTQW-based Transformer for Graph Classification

Zhan Li, Wuqing Yu, Yusen Wu, Chuan Wang

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

Graph Representation Learning Quantum-Inspired ML Graph Classification Graph Transformer

Open paper AskPDF arXiv

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.

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