Graph Neural Networks (GNNs) excel on graph-structured data but typically suffer from two drawbacks: under the homophily assumption, message passing acts as a low‑pass filter, harming performance on heterophilic graphs; stacking many layers drives node features toward constants, causing over‑smoothing. Existing works usually tackle these issues separately, and the few joint solutions rely on empirical heuristics while often sacrificing expressiveness.
We propose CTQW‑GNN, a GNN built on Continuous‑Time Quantum Walks (CTQW) that theoretically mitigates both problems. The CTQW propagator $e^{-\mathrm{i}Ht}$ has two key properties: its unitarity places eigenvalues on the unit circle, so no frequency component is damped, counteracting the low‑pass bias; unitarity also preserves feature norms, preventing the Dirichlet energy from decaying exponentially with depth and thus alleviating over‑smoothing.
CTQW‑GNN combines three complementary aggregation modules: CTQW‑based Aggregation evolves node features via the unitary propagator, retaining mid‑ and high‑frequency signals and avoiding energy collapse; CTQW‑Attention Aggregation constructs a multi‑hop neighbor graph from CTQW amplitudes and applies attention, reaching distant homophilic nodes missed by single‑hop aggregation; LF Aggregation adds a standard low‑pass GAT branch to maintain strong performance on homophilic graphs where pure CTQW aggregation may be suboptimal. We further provide a spectral‑gap analysis explaining energy preservation and a Lieb‑Robinson‑type bound that offers a principled rule for selecting the walk time $t$.
Blogger's Review: By embedding the unitary dynamics of quantum walks into GNNs, CTQW‑GNN balances the needs of heterophilic and homophilic graphs, offering a theoretically grounded and practically effective advance in graph learning.