PaperlayerView exact revision on arXiv

Source-linked AI summary

Continuous-Time Quantum Walks based Graph Neural Network

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

arXiv:2608.20738v1cs.AI

TL;DR

GNNs struggle with heterophily and over-smoothing, and existing joint remedies often lack theoretical guarantees or sacrifice expressiveness. CTQW-GNN combines unitary CTQW-based, CTQW-attention, and low-frequency aggregations with spectral and propagation analyses. It achieves state-of-the-art accuracy across all 14 benchmarks while providing a non-decaying energy component for theoretical over-smoothing mitigation.

  • Problem

    Existing GNNs face low-pass bias on heterophilic graphs and exponential over-smoothing, while joint remedies often rely on empirical heuristics or sacrifice expressiveness.

  • Method

    CTQW-GNN combines CTQW-based, CTQW-Attention, and low-frequency aggregations to capture diverse frequencies and long-range information through a unitary, norm-preserving propagator.

  • Results

    State-of-the-art accuracy is achieved on all 14 benchmarks, outperforming strong baselines by 1.07% on average.

  • Takeaways & Limitations

    The model provides a unified approach to heterophily and over-smoothing with spectral-gap and Lieb–Robinson analyses supporting energy preservation and walk-time selection.

  • Takeaways & Limitations

    Prior over-smoothing remedies can mitigate the problem at the cost of sacrificing GNN expressive performance.

Abstract

from arXiv · show

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 \textbf{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. \textit{CTQW-based Aggregation} evolves node features through the unitary propagator, preserving mid- and high-frequency signals for heterophilic graphs while preventing Dirichlet-energy collapse. \textit{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. \textit{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$.

1 Introduction

GNNs face heterophily and over-smoothing weaknesses, while existing joint solutions often lack theoretical guarantees. CTQW-GNN combines complementary aggregations with theoretical analysis and achieves strong benchmark performance.

  • Motivation: Neighbor aggregation acts as a low-pass filter, reducing performance on heterophilic graphs where connected nodes differ.High-frequency filters and multi-hop aggregation are common responses.
  • Motivation: Increasing GNN depth causes node features to converge exponentially toward constants, producing over-smoothing and limiting practical depth.Some remedies mitigate over-smoothing while sacrificing expressive performance.
  • Research gap: Heterophily and over-smoothing are related, but existing joint approaches generally rely on empirical observations rather than theoretical guarantees.A reliable solution should capture diverse frequencies, expand neighborhoods, and prevent convergence to constants.
  • Approach: CTQW-GNN combines CTQW-based and CTQW-Attention aggregations with complementary low-frequency aggregation to capture low-, mid-/high-frequency, and long-range information.The CTQW-inspired modules preserve quantum superposition and phase-driven interference.
  • Results: All 14 benchmarks show state-of-the-art accuracy, with CTQW-GNN outperforming strong baselines by 1.07% on average.On saturated homophilic datasets, the reported improvement is +1.06–3.31%.

2 Related Work

Related work addresses heterophily through frequency-selective filters or expanded neighborhoods and addresses over-smoothing through architectural modifications. CTQW-GNN differs by hybridizing these strategies while targeting both problems concurrently.

  • Heterophily: Heterophilic GNNs use high-pass and low-pass filters or expanded neighborhoods to capture differing or distant node information.High-frequency information is reported as useful for heterophily, while expanded neighborhoods capture distant homophilic information.
  • Heterophily: CTQW-GNN combines classical low-frequency aggregation with CTQW aggregation for mid-range and high-frequency information.This hybrid integration distinguishes the model from methods focused on a single graph pattern.
  • Over-smoothing: Existing over-smoothing remedies include drop operations, normalization, and modified GNN dynamical systems, but may limit expressiveness.CTQW-based aggregation is introduced to address over-smoothing while handling heterophily concurrently.

3 Preliminary

The preliminary section defines graph spectral representations, low-pass filtering, Dirichlet energy, homophily ratios, and the distinction between classical and quantum walks. These concepts establish the paper’s analysis of frequency preservation and over-smoothing.

  • Graph spectrum: The normalized adjacency matrix is symmetric and decomposed into eigenvectors and eigenvalues that represent graph signal frequencies.The eigenvectors provide the basis used for graph Fourier analysis.
  • Graph spectrum: Graph Fourier transform represents a graph signal in the eigenvector basis, where learnable convolution kernels determine frequency responses.GCN uses g_θ = I − Λ, which is identified as a low-pass filter.
  • Over-smoothing: Over-smoothing is defined as exponential convergence of layer-wise Dirichlet energy to zero as GNN depth increases.This corresponds to node features exponentially converging toward a constant value.
  • Quantum walks: A classical random walk evolves probabilities dissipatively, whereas a quantum walk evolves complex amplitudes under a Hermitian Hamiltonian.The continuous-time quantum walk solution is ψ(t) = e^-iHt ψ(0) and preserves the ℓ2 norm.
  • Homophily: Homophily measures the tendency of connected nodes to share labels, with graph-level and node-level ratios capturing global and local patterns.High homophily ratios indicate homophilic graphs, while low ratios indicate heterophilic graphs.

4 Method

CTQW-GNN combines three aggregation branches to address heterophily and over-smoothing: CTQW propagation preserves diverse spectral information, CTQW-induced attention reaches distant neighbors, and LF aggregation supports homophilic graphs.

  • Overview: CTQW-GNN derives a CTQW-induced graph with edge weights, then uses its connectivity for information aggregation.The CTQW constructs higher-order connectivity that supports subsequent aggregation modules.
  • CTQW-based Aggregation: CTQW-based Aggregation uses unitary propagation to aggregate mid-range and high-frequency information while providing a non-decaying energy component.The branch preserves non-trivial spectral content rather than using diffusive aggregation.
  • CTQW-Attention Aggregation: CTQW-Attention Aggregation applies Graph Transformer attention on CTQW-induced long-range edges to capture distant homophilic neighbors.The new graph broadens the neighborhood beyond the original local connectivity.
  • Over-smoothing: CTQW propagation places eigenmode multipliers on the unit circle, so no mode is attenuated and the CTQW branch's Dirichlet energy cannot exponentially decay under stated conditions.The non-decay proposition assumes that H commutes with the Laplacian used in the Dirichlet energy and a mild non-resonance condition.
  • LF Aggregation: LF Aggregation uses a low-pass GNN branch, implemented as GAT here, to retain low-frequency information on strongly homophilic graphs.The branch compensates for CTQW aggregation's shortcoming in strongly homophilic settings.

5 Experiment

Experiments evaluate CTQW-GNN across homophilic and heterophilic benchmarks, node subgroups, ablations, and sensitivity settings. CTQW-GNN performs strongly across graph regimes while its aggregation modules contribute complementary benefits.

  • Main Results: In new heterophilic datasets, CTQW-GNN outperforms the nearest rival by 1.48% on average despite weak performance from many heterophily-specific baselines.
  • Performance on Node Subgroups: CTQW-GNN outperforms existing methods across node homophily ratios by combining low-, mid-, and high-frequency information with long-range dependencies.
  • Evolution of Dirichlet Energy: CTQW-based aggregation stabilizes Dirichlet energy, whereas classic GNNs and the model without CTQW aggregation exhibit exponential energy convergence with depth.
  • Ablation Study: Removing CTQW-Attention, LF, or CTQW-based aggregation reduces performance, with each module affecting different node-homophily subgroups.
  • Sensitivity Analysis: Performance remains stable across a broad middle walk-time range, while moderate sparsification such as 5×10−3 balances accuracy and sparsity.

6 Conclusion

CTQW-GNN combines CTQW-inspired and classical aggregation to address heterophily and over-smoothing. It achieves state-of-the-art accuracy across 14 benchmarks while retaining asymptotic per-edge cost comparable to GCN/GAT.

  • CTQW-GNN integrates CTQW-based, CTQW-Attention, and LF aggregation to combine low-, mid-, high-frequency, and long-range information.
  • The CTQW branch has a positive spectral/Cesàro energy floor and therefore cannot decay exponentially under the stated theoretical results.
  • CTQW-GNN reaches state-of-the-art accuracy on all 14 benchmarks at a per-edge cost asymptotically equal to GCN/GAT.

A Proof

The proof framework defines the graph Laplacian spectrum, isolates the non-constant feature subspace, and states assumptions supporting the CTQW energy analysis.

  • The graph Laplacian has eigenvalues 0 = μ_1 ≤ μ_2 ≤ ··· ≤ μ_N, with spectral gap Δ := μ_2.
  • P_⊥ projects onto the non-constant Laplacian subspace, and spectral coordinates are defined by X̃ := V†X.
  • The analysis assumes a positive spectral gap and nonzero initial non-constant feature energy.
  • For H = A, a non-resonance condition excludes cases where the CTQW orbit concentrates all feature energy in the constant Laplacian mode.

A.1 Proof of Proposition 1

The proof establishes branch-wise Dirichlet-energy bounds before mixing and Lipschitz-based bounds after the learned mixer, while explicitly excluding degenerate branch cancellation.

  • Before the learned mixer, total Dirichlet energy is the sum of non-negative branch energies, yielding an exact branch-wise exponential-envelope criterion.
  • For entrywise ρ_+-Lipschitz activation with σ(0)=0, post-mixing energy is bounded above by ρ_+^2 times the pre-mixing energy.
  • A lower energy bound holds when the map z ↦ σ(zW) has gain at least ρ_- on the layer-wise edge-difference subspace.
  • The proof explicitly excludes degenerate projections that cancel an entire branch rather than hiding them behind a full-rank assumption.

A.2 Proof of Proposition 2

The proof shows that, under the commuting case, CTQW evolution preserves the non-constant Laplacian components through unit-modulus phase changes. This rules out exponential decay of Dirichlet energy and hence exponential over-smoothing.

  • A.2 Proof of Proposition 2: When H commutes with L, CTQW and the Laplacian are simultaneously diagonalizable, so each non-trivial Laplacian coefficient receives only a unit-modulus phase.The real-imaginary representation is an isometry, so it does not alter Dirichlet energy.
  • A.2 Proof of Proposition 2: For the default H = A, pointwise invariance is not claimed because H and L need not commute, but the positive lower bound still excludes exponential over-smoothing.The argument relies on the Cesàro energy bound rather than simultaneous diagonalization.
  • A.2 Proof of Proposition 2: The CTQW branch cannot exponentially over-smooth because exponential energy decay would contradict its positive Cesàro lower bound.The contradiction follows by comparing hypothetical exponential decay with the positive lower bound established by Lemma 2.

A.3 Spectral-Gap Lower Bound

The spectral-gap analysis establishes a positive CTQW energy floor whenever the initial features contain a non-constant component. This contrasts with classical diffusion, whose Dirichlet energy decays exponentially at a rate set by the spectral gap.

  • A.3 Spectral-Gap Lower Bound: The proof uses P⊥ to remove only the zero Laplacian eigenvector, linking Dirichlet energy to the non-constant component of the features.This projection-based decomposition supplies the positive lower bound used in the proposition.
  • A.3 Spectral-Gap Lower Bound: The CTQW energy lower bound is strictly positive whenever the initial features have a non-constant component.The projection onto the nonzero Laplacian eigenspace retains positive Frobenius norm under the stated assumptions.
  • A.3 Spectral-Gap Lower Bound: Classical diffusion decays exponentially at rate Δ, whereas CTQW retains a Δ-linear energy floor.The same spectral quantity governs diffusion over-smoothing but yields preservation rather than exponential decay for CTQW.

A.4 Walk-Time 𝑡and Effective Propagation Radius

The paper relates CTQW walk time to an effective propagation radius through a Lieb–Robinson-type bound and uses Krylov approximation to implement the propagator efficiently. The spectral response remains all-pass, while a non-degenerate mixer preserves the CTQW branch’s energy-floor guarantee.

  • A.4 Walk-Time t and Effective Propagation Radius: Amplitudes beyond a radius linear in λmax t are factorially small, motivating the effective screening radius r_eff(t) = ⌈2λmax t/π⌉.The bound follows because walks shorter than the graph distance cannot contribute to the propagator amplitude.
  • A.5 Krylov Implementation Error: At k = 20, Krylov approximation introduces a negligible exponential error over the selected t range, preserving the qualitative non-decay guarantee up to numerical precision.The approximation can reduce the CTQW energy floor only by a controllable, exponentially small term.
  • A.6 All-Pass Spectral Response of CTQW-based Aggregation: CTQW preserves the magnitude of every spectral component, realizing an exact all-pass filter on H’s eigenbasis.Each mode is multiplied by e^-iλ_l t, whose magnitude is one.
  • A.4 Walk-Time t and Effective Propagation Radius: A non-degenerate learned mixer with positive conditional CTQW gain prevents the mixed representation from losing the CTQW branch’s non-decaying energy.This excludes the failure mode in which the learned projection maps all CTQW differences to zero.
Loading 2608.20738v1…