arXiv:2608.20738 · ACM International Conference on Information and Knowledge Management (CIKM)
Continuous-Time Quantum Walks based Graph Neural Network
Yuliang Zhan, Zefeng Gao, Jian Li, Yang Liu, Hao sun
Abstract
Graph Neural Networks (GNNs) are widely used on graph-structured data. However, most GNNs suffer from two key weaknesses. First, message passing acts as a low-pass filter based on the homophily assumption, so it performs poorly on heterophilic graphs, where connected nodes differ. Second, stacking layers makes node features converge exponentially to constants, a problem known as oversmoothing. Existing work usually addresses the two weaknesses separately. The few methods that target both rely on empirical heuristics, and many over-smoothing solutions further sacrifice the expressive power of the model. To address both weaknesses with theoretical justification, we propose CTQW-GNN, a GNN built on Continuous-Time Quantum Walks (CTQW). The design is motivated by two properties of the CTQW propagator e-iHt. (i) It is unitary and its eigenvalues lie on the unit circle, so no frequency component is damped. This directly counters the low-pass bias. (ii) Unitarity preserves the feature norm, so the Dirichlet energy does not decay exponentially with depth. This directly counters oversmoothing. Guided by these properties, CTQW-GNN combines three aggregation modules, each motivated by a specific gap in prior work. CTQW-based Aggregation evolves node features through the unitary propagator. It captures the mid- and high-frequency signals needed for heterophilic graphs and provably keeps the Dirichlet energy from collapsing, so it addresses both weaknesses in a single branch. CTQW-Attention Aggregation builds a multi-hop neighbor graph from the CTQW amplitudes and applies attention over it, so distant homophilic nodes that single-hop aggregation misses can still be reached. LF Aggregation is a standard low-pass branch (GAT) that preserves accuracy on strongly homophilic graphs, where a pure CTQW branch is suboptimal. We further provide a spectralgap analysis that explains the energy preservation, and a Lieb– Robinson-type bound that gives a principled rule for choosing the walk-time t . Experiments on 14 benchmarks (9 heterophilic, 5 homophilic) show that CTQW-GNN reaches state-of-the-art accuracy on every dataset. Krylov propagation and Chebyshev-based sparsification keep the CTQW-related computation linear in the number of edges under the stated sparsification rule.