Paper deep dive
Continuous-Time Quantum Walks based Graph Neural Network
Yuliang Zhan, Zefeng Gao, Jian Li, Yang Liu, Hao sun
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 8/24/2026, 5:10:29 AM
Summary
The paper introduces CTQW-GNN, a Graph Neural Network architecture designed to simultaneously address the heterophily problem and over-smoothing. It utilizes Continuous-Time Quantum Walks (CTQW) to create a unitary propagation mechanism that preserves high-frequency signals and feature norms. The model combines three aggregation modules: CTQW-based Aggregation for mid/high-frequency signals, CTQW-Attention Aggregation for long-range dependencies, and Low-Frequency (LF) Aggregation for homophilic structures.
Entities (9)
Relation Signals (8)
CTQW-GNN → addresses → Over-smoothing
confidence 95% · CTQW-GNN... to address both issues [heterophily and over-smoothing] with theoretical justification.
CTQW-GNN → addresses → Heterophilic Graphs
confidence 95% · preserving mid- and high-frequency signals for heterophilic graphs
CTQW-based Aggregation → ispartof → CTQW-GNN
confidence 92% · CTQW-GNN combines three complementary aggregation modules. CTQW-based Aggregation...
CTQW-Attention Aggregation → ispartof → CTQW-GNN
confidence 92% · CTQW-GNN combines three complementary aggregation modules. CTQW-Attention Aggregation...
LF Aggregation → ispartof → CTQW-GNN
confidence 90% · CTQW-GNN combines three complementary aggregation modules. LF Aggregation...
CTQW → provides → Unitary Propagator
confidence 90% · It is unitary and has eigenvalues on the unit circle, so no frequency component is damped
Unitary Propagator → prevents → Over-smoothing
confidence 88% · unitarity preserves feature norms and prevents the Dirichlet energy from decaying exponentially with depth, thereby mitigating over-smoothing.
CTQW-Attention Aggregation → uses → Attention Mechanism
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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 \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$.
Tags
Links
- Source: https://arxiv.org/abs/2608.20738v1
- Canonical: https://arxiv.org/abs/2608.20738v1
Trouble viewing inline? Open PDF directly →
Full Text
84,691 characters extracted from source content.
Expand or collapse full text
Continuous-Time Quantum Walks based Graph Neural NetworkDOI: X.XXXXXXXConference: Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NYISBN: 978-1-4503-X-X/2018/06CCS: Computing methodologies Machine learning Yuliang Zhan email: zhanyuliang@ruc.com Affiliation: Renmin University of China , Beijing , China , Zefeng Gao email: zfgao@ruc.com Affiliation: Renmin University of China , Beijing , China , Jian Li email: lijian2022@ruc.edu.cn Note: Corresponding author. Affiliation: Renmin University of China , Beijing , China , Yang Liu email: Liuyang22@ucas.ac.cn Affiliation: Renmin University of China , Beijing , China and Hao sun email: haosun@ruc.edu.cn Affiliation: Renmin University of China , Beijing , China 2018© , 2018; 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 over-smoothing. 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−iHte^-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. (i) Unitarity preserves the feature norm, so the Dirichlet energy does not decay exponentially with depth. This directly counters over-smoothing. 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 spectral-gap 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 1414 benchmarks (99 heterophilic, 55 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. Keywords: Deep Graph Neural Networks, Over-smoothing, Heterophilic Graph, Continuous-Time Quantum Walks 1. Introduction Graph Neural Networks (GNNs) have seen widespread application across numerous important fields, such as quantum physics (55), traffic networks (32) and recommendation systems (42). This is primarily attributed to the capability of GNN to capture node features and graph topology information. Despite these significant advancements (14; 49), most of existing GNN models still have two inherent weaknesses (i.e., homophily assumption and over-smoothing) that can diminish their performance. The first weakness of GNNs is the homophily assumption, as they update node or edge features by aggregating information from neighbors. This aggregation method acts as a low-pass filter (52; 27), which preserves similarities and filters out differences among connected nodes, thereby promoting feature uniformity (4). However, recent studies indicate that while this filtering mechanism excels in homophilic graphs with similar connected nodes, it reduces GNNs performance in learning node representations on heterophilic graph where connected nodes differ (heterophily problem) (62; 25). To improve GNN performance on heterophilic graphs, many researchers are attempting to construct high-frequency filters to capture high-frequency information (4; 35). This approach is motivated by findings that high-frequency information is useful for learning on heterophilic graph (4). Another prevalent approach attempt involves aggregating multi-hop neighbor nodes to capture long-range homophilic dependencies (59; 29). The second weakness of GNNs is the over-smoothing problem where increasing the number of layers in GNN causes the features of all nodes exponentially converge towards constant values (26; 15). This leads to most applied GNNs being shallow, limiting their capabilities. Recently, researchers have primarily focused on mitigating over-smoothing by implementing drop operation (43), normalization (60; 61), and modifying the dynamical systems of GNNs (45; 51). However, previous study posits that while some methods can mitigate over-smoothing, this comes at the cost of sacrificing the expressive performance of GNNs (44). Heterophily and over-smoothing are often studied as separate problems (6; 10), but recent evidence suggests that they are closely related (54). Recent works have found that methods addressing heterophily can also alleviate over-smoothing (7; 11), and vice versa (45; 51). These methods, however, rely on empirical observation rather than theoretical guarantees. A reliable solution requires an aggregation method that captures diverse frequencies and expands node neighborhoods while provably preventing the node features from converging to constants across many layers. In this paper, we propose Continuous-Time Quantum Walks based on Graph Neural Network, namely CTQW-GNN, to theoretically addressing both weaknesses. We first derive multi-hop node connectivity and edge weights through CTQW. Then, we utilize one-hop connectivity to aggregate low-frequency information and multi-hop connectivity to capture information from distant nodes. This enables CTQW-GNN to effectively learning in both homophilic and heterophilic graphs. Specifically, we adopt the attention mechanism from Graph Transformer (48) to aggregate distant nodes via CTQW-induced multi-hop connectivity, thereby capturing long-range homophilic relationships. Note that previous study points that most graphs are not purely homophilic or heterophilic, but rather fall somewhere in between (34). Furthermore, mid-frequency information has been shown to enhance GNN performance in such mixed-pattern graphs (35). CTQW-derived edge weights naturally enable the aggregation of mid- and high-frequency information, so we can use CTQW effectively capturing mid-range spectral components in the graph (3). Finally, we combine the information aggregated from one-hop and multi-hop connectivity with that aggregated through CTQW-derived edge weights. This combined feature serves as the input for the next layer of CTQW-GNN. Since the norm-preserving property of CTQW, the Dirichlet energy of graph does not exponentially converge to zero, preventing over-smoothing in the CTQW-GNN model. The contributions of this paper are three fold: ∙ CTQW-inspired aggregations. We design CTQW-based and CTQW-Attention aggregations that preserve quantum superposition and phase-driven interference. ∙ CTQW-GNN with provable guarantees. The model combines three aggregations to capture low-, mid-/high-frequency, and long-range information. We provide a spectral-gap analysis and a Lieb–Robinson bound reff(t)=2λmaxt/πr_eff(t)\!=\!2 _ t/π that together explain why CTQW avoids exponential energy decay and how to choose t. ∙ Extensive experiments. CTQW-GNN attains state-of-the-art accuracy on all 14 benchmarks, outperforming strong baselines on every dataset (+1.07%+1.07\% on average; +1.06+1.06–3.31%3.31\% on saturated homophilic datasets). 2. Related Work Heterophilic GNN. To address the heterophily problem, many works focused on designing Heterophilic GNNs without the homophily assumption (28; 29). These works can mainly be divided into two types: the first type of methods combined high-pass and low-pass filters to capture information from neighboring nodes (16; 49), since the high-frequency information was helpful to address the heterophily problem (4). The second type of methods expanded the neighborhood of nodes to aggregate distant homophilic information (28; 29). Our model distinguishes from existing methods by offering a hybrid integration of approaches. It adeptly utilizes classic aggregation methods, such as Graph Convolutional Networks (GCN), for the aggregation of low-frequency information. Meanwhile, for mid-range and high-frequency information aggregation, it employs the advanced CTQW strategy, thereby combining the best of both parts to enhance performance and efficiency. Furthermore, our model leverages the connectivity derived from CTQW to adeptly capture long-range homophilic dependencies. This innovative application of CTQW significantly enhances the expressive power of GNNs, allowing for a more nuanced and comprehensive representation of complex graph structures. Over-smoothing. Over-smoothing is a well-known problem in GNNs, characterized by node features exponentially converging towards a same constant value as the number of layers increases. Numerous methods have been proposed to mitigate it mainly from Drop Operation (43), Normalization (61), and modifying the dynamical systems of GNNs (45). Despite notable progress, there is a trade-off in existing methods that can limit GNN expressiveness (44). We introduce CTQW-based aggregation to counteract over-smoothing. Unlike most research that treats over-smoothing and heterophily separately, our model tackles both issues concurrently, enhancing GNN performance on complex graph tasks. Furthermore, we substantiate the reliability of this approach theoretically. 3. Preliminary Notations We define an undirected graph =(,ℰ)G=(V,E), with V as the node set of size N and ℰE as the edge set. The adjacency matrix is A∈ℝN×NA ^N× N. The degree matrix D is diagonal with Dii=∑jAijD_i= _jA_ij. The normalized graph Laplacian L=I−D−12AD−12L=I-D^- 12AD^- 12 (where I is the identity matrix) is symmetric and expressed as UΛUTU U^T. Here, Λ=diag([λ1,λ2,…,λN]) =diag([ _1, _2,..., _N]) represents graph signal frequencies and U=uii=1NU=\u_i\_i=1^N denotes the frequency components. Graph Fourier Transform We treat U as the base in graph Fourier transform. The transform of a graph signal x∈ℝnx ^n on G is x^=UTx x=U^Tx, and the inverse is x=Ux^x=U x. The convolution of the graph signal x with the kernel f is: (1) (f∗x)=U((UTf)⊙(UTx))=UgθUTx.(f*x)_G=U((U^Tf) (U^Tx))=Ug_θU^Tx. where ⊙ denotes the hadamard product, and gθg_θ is a learnable filter which can adjust the frequency response of the graph signal.For example, GCN defines the convolutional kernel gθ=I−Λg_θ=I- , where λgθ,i=1−λi _g_θ,i=1- _i. It shows that the convolutional kernel of GCN is low-pass filter. Over-smoothing and Dirichlet Energy Recent literature mainly employ graph Dirichlet energy (DE) to measure the similarity of features between nodes, thereby defining over-smoothing(44). The Dirichlet energy E defined on an undirected graph G with node features X is : (2) E(X)=1N∑i∈∑j∈i‖Xi−Xj‖22E(X)= 1N _i _j _i \|X_i-X_j \|^2_2 With Dirichlet energy, we can define over-smoothing like (45) as following: Definition 0. Let XnX^n denote the node feature at the n-th layer of GNN. Over-smoothing is defined as the exponential convergence to zero of the layer-wise Dirichlet energy as a function of n: (3) E(Xn)≤ae−bn,E(X^n)≤ ae^-bn, where a and b are constants and a,b>0a,b>0 In other words, the node features will exponentially converge to a constant value as the number of layers increases. Quantum Walks: a Primer A classical random walk (CRW) on a graph propagates a probability vector p(t)∈ℝ≥0Np(t)\!∈\!R^N_≥ 0 by the diffusion equation p˙=−Lp p=-Lp with solution p(t)=e−Ltp(0)p(t)=e^-Ltp(0) (9). A quantum walk (QW), introduced by 1 and surveyed by 22, replaces real probabilities with complex amplitudes ψ(t)∈ℂNψ(t)\!∈\!C^N and the dissipative generator −L-L with a Hermitian Hamiltonian H. The walk evolves by the Schrödinger equation iψ˙=Hψi ψ=Hψ, whose solution ψ(t)=e−iHtψ(0)ψ(t)=e^-iHtψ(0) is unitary: it preserves the ℓ2 _2 norm of ψ rather than the ℓ1 _1 norm of p. Its continuous-time variant was developed by 13. Two intuitive advantages over CRW motivate our use: (i) eigenmodes acquire different phases e−iλlte^-i _lt instead of different decay rates e−λlte^- _lt, so high-frequency content is preserved (Section 4.2); and (i) phase-coherent superposition spreads the walker ballistically (distance ∝t t) rather than diffusively (distance ∝t \! t), yielding exponential separation in hitting time on certain graphs (13; 8). We use QW purely as a unitary linear operator on ℂNC^N, classically simulated (Section 4); no quantum hardware is required. Figure 1. The overview of CTQW-GNN for heterophilic graphs and over-smoothing problem. (a). We define an undirected graph =(,ℰ)G=(V,E), with V as the node set of size N and ℰE as the edge set. (b). We conduct a CTQW on the original graph G to obtain a new edge set ℰCTQWE_CTQW with edge weights WℰCTQW_E_CTQW ; both connectivity relations ℰE and ℰCTQWE_CTQW share the same node features X(n)X^(n). (c). We employ three distinct information aggregation methods proposed in this paper to derive three types of node information: XLF(n)X^(n)_LF, XCTQW(n)X^(n)_CTQW and XAttention(n)X^(n)_Attention. through the three types of features, we obtain the node features X(n+1)X^(n+1) for the next layer. The details of the formula are provided in Section 4. Homophily Ratio We use a single term homophily—the tendency of connected nodes to share the same label—throughout the paper; the words “homogeneity” and “heterogeneity” are avoided to prevent confusion with the graph-theoretic notion of node/edge type homogeneity (in which all nodes/edges share a single type) (47). We measure homophily at the graph and node level. Definition 0 (Graph Homophily Ratio). Let C∈ℝ|y|×|y|C |y |× |y | where |y| |y | is the number of node categories and Cij=|(u,v):(u,v)∈ℰ∧yu=i∧yv=j|C_ij=|\(u,v):(u,v) y_u=i y_v=j\|. The Graph Homophily Ratio is (4) h=∑iN∑ji==jCij∑iN∑ji≠jCij.h= _i^N _j^i==jC_ij _i^N _j^i≠ jC_ij. Homophilic graphs have a high h; heterophilic graphs have a low h. The node-level analogue measures the local pattern around each node: Definition 0 (Node Homophily Ratio). Let y∈ℝNy ^N be the node labels and (vi)N(v_i) the neighborhood of viv_i with degree dvid_v_i. The Node Homophily Ratio is (5) hvi=|u∈(vi):yu=yvi|dvi.h_v_i= |\u (v_i):y_u=y_v_i\ |d_v_i. 4. Method In this section, we describe CTQW-GNN. We first outline our approach, then introduce the details of CTQW-based Aggregation and CTQW-Attention Aggregation. Finally, we present how the model in this paper integrates the three methods of information aggregation and justify why our approach can mitigate over-smoothing and enhance the ability to handle heterophilic graphs. 4.1. Overview Existing methods typically address Over-smoothing and heterophily problem as separate problem. To address both problems concurrently, we further augment the capability of model to aggregate information by employing a novel method of information aggregation inspired by CTQW. This approach helps prevent the aggregated node information from exponentially converging to a constant value as the number of layers increases, thereby avoiding over-smoothing. Forthemore, the novel aggregation method can aggregate information from various frequency and, based on the higher-order neighbor connectivity information derived from CTQW, aggregate information from distant neighbors, thus improving performance on heterophilic graphs. To achieve this goal, we first get a new graph along with the weights of edges by CTQW. Based on the node connection weights of the new graph, CTQW-based Aggregation can be performed. This method aggregates mid-range and high-frequency information to improve performance on heterophilic graphs. Furthermore, due to the unitary norm preservation of CTQW, the CTQW-based branch provides a non-decaying energy component that mitigates over-smoothing during information aggregation. Subsequently, we use the new graph obtained by CTQW to aggregate higher-order neighbor information broadens the neighborhood size, thereby capturing more homophilic node. To find homophilic nodes among a large set of neighbors, we employs the attention mechanism of Graph Transformers during the aggregation of higher-order neighbors; hence, this method is referred to as CTQW-Attention Aggregation. Furthermore, to ensure that the model maintains strong performance on homophilic graphs, this paper also utilizes a low-pass GNN to aggregate homophilic information. This method is termed Low-Frequency Aggregation (LF Aggregation). An overview of our approach is depicted in Figure 1. The three aggregators address distinct failure modes of message passing. (1) Over-smoothing: damping e−λlte^- _lt is replaced by the unitary multiplier e−iλlte^-i _lt on the unit circle, so the Dirichlet energy of the XCTQWX_CTQW branch is layer-invariant (Prop. 2, Lemma 2). (2) Heterophily: the same eigenmode preservation gives CTQW-based Aggregation an all-pass filter, while the ϵε-thresholded |e−iHt||e^-iHt| exposes a Lieb–Robinson-bounded long-range graph CTQWG_CTQW of radius reff(t)r_eff(t). (3) Saturated homophilic graphs: an LF branch (GAT) handles regimes where low-pass aggregation is already optimal. Concatenating the three branches (Eq. 12) ensures one branch’s failure cannot collapse the representation (Prop. 1). 4.2. CTQW-based Aggregation Continuous Time Quantum Walks. The CTQW on graph G represents the evolution of node states in an N-dimensional Hilbert space with orthonormal basis |a⟩ a where a=1,2,3,…,Na=1,2,3,...,N and ⟨a|b⟩=δab a|b= _ab, with δab=1 _ab=1 if and only if a=ba=b, and 00 otherwise. Node states |ψ(t)⟩ ψ(t) at time t evolve according to the Schrödinger equation: (6) iℏdt|ψ(t)⟩=H|ψ(t)⟩,i ddt ψ(t)=H ψ(t), where H is the Hamiltonian matrix of the CTQW system and ii is the imaginary unit, which is different from the previous equation i. ℏ is Planck’s constant, which is commonly considered to be 1. The state of nodes evolves from the initial state |ψ(0)⟩ ψ(0) as: (7) |ψ(t)⟩=e−iHt|ψ(0)⟩, ψ(t)=e^-iHt ψ(0), Previous works show that a finite graph is given where classical and quantum walks give an exponential separation in expected hitting time (13; 8). Continuous-Time Random Walk (CTRW, i.e., x(t)=e−Ltx(0)x(t)=e^-Ltx(0), where L denotes the graph Laplacian matrix.) is a diffusion process and serves as the primary information propagation mechanism in most existing homophilic GNN. Figure 2 illustrates the diffusion behavior and probability distribution of quantum walks and classical random walks on the same graph structure (a path graph) under identical time conditions. We can see that under the same time duration, the propagation range of CTQW is significantly larger than that of classical CTRW. Furthemore, it can be intuitively observed that CTRW-based information aggregation tends to assign higher weights to nearby nodes, which will lead to the over-smoothing. In contrast, CTQW places more emphasis on both higher-order neighboring nodes and mid-order neighboring nodes. This observation motivates us to leverage CTQW as the foundation for designing an information propagation mechanism that mitigates over-smoothing while effectively addressing heterophily. (a) CTQW: Interference-Driven Spread with Sharp Peaks. (b) CTRW: Classical Diffusion Centered Near Origin. Figure 2. Probability Distribution Comparison Between CTQW and CTRW on a Path (starting from node 126, t=40t=40). Aggregation via CTQW. We propose CTQW-based Aggregation, a novel aggregation method based on Eq. 7. Different from the original CTQW, in order to accommodate the multi-layer structure of GNNs, the CTQW-based Aggregation discretizes time, evolving with layers rather than with continuous time. The evolution of node features is governed by the following equation: (8) XCTQW(n)=f(e−iHtX(n)),X_CTQW^(n)=f(e^-iHtX^(n)), where X(n)X^(n) and XCTQW(n)X_CTQW^(n) are the feature of nodes at the n-th layer of the GNN and the output of n-th layer of CTQW-based Aggregation, respectively. The t in e−iHte^-iHt is a hyperparameter that influences the range of neighbors obtained through the quantum walk. The function f(⋅)f(·) concatenates the imaginary and real parts of the input. Choice of Hamiltonian H. Either the adjacency matrix A or the normalised Laplacian L=I−D−1/2AD−1/2L=I-D^-1/2AD^-1/2 is a valid Hermitian Hamiltonian, related by an eigenvalue translation (λlL=1−λlA/dλ^L_l=1-λ^A_l/d on d-regular graphs), so they generate the same family of unitaries up to a global phase. We use A by default for three reasons: (i) A has the lowest constant in nnznnz, minimising every Krylov mat-vec; (i) the trivial mode of L is the constant “smoothing” direction λ=0λ\!=\!0, which we wish to avoid privileging; (i) A matches the tight-binding Hamiltonian in solid-state physics (5). Practical Simulation of e−iHtX(n)e^-iHtX^(n). A natural concern is whether the quantum state |ψ(0)⟩ ψ(0) in Eq. 7 entails a 2N2^N-dimensional Hilbert space and consequently requires exponential-time simulation. This holds for general many-body quantum systems but not for single-particle CTQW: the walker lives in the N-dimensional vertex space ℂNC^N (one amplitude per node), not in the 2N2^N Fock space of N qubits. Hence e−iHte^-iHt is an N×N\!×\!N unitary that we simulate classically with no quantum hardware. We never materialise the dense matrix; for each feature column X(n):,k∈ℝNX^(n)_:,k\!∈\!R^N we apply e−iHte^-iHt via a kiter≤20k_iter\!≤\!20-step Lanczos Krylov-subspace approximation (24; 2; 38): (1) build a Krylov basis VkiterV_k_iter of H from X(n):,kX^(n)_:,k by Lanczos; (2) form the kiter×kiterk_iter\!×\!k_iter projection T=V†HVT\!=\!V HV; (3) compute the small dense exponential e−iTte^-iTt; (4) return Ve−iTtV†X(n):,kVe^-iTtV X^(n)_:,k. Total cost is (kiter⋅nnz(H)⋅d)O(k_iter\!·\!nnz(H)\!·\!d) per layer, and Appendix A.5 gives an exponential error bound that makes the approximation indistinguishable from the exact unitary at kiter=20k_iter\!=\!20. The “initial state” ψ(0)ψ(0) is simply the GNN feature column; after evolution we keep both real and imaginary parts via f(⋅)f(·). Performing the spectral decomposition of H yields: (9) H=UΛU†,H=U U , where, U is the matrix formed by the eigenvectors of H and Λ is the diagonal matrix with the corresponding eigenvalues arranged along its diagonal. Recent studies indicate that real-world homophilic graphs consist of homophilic nodes as the majority structural pattern and heterophilic nodes in the minority (31; 28). Conversely, the situation is reversed in heterophilic graphs. However, it has been found that existing GNN model designed for homophilic graphs or heterophilic graphs only focus on one pure pattern(34). In this context, mid-range frequency plays a more significant role compared to low and high-frequency in a mixture of homophilic and heterophilic graph (35). According to Eq. 1 and Eq. 9, We can found that CTQW-based Aggregation defines the convolutional kerne gθ=e−iΛtg_θ=e^-i t, where |λgθ|=|e−iΛt|=1 | _g_θ |= |e^-i t |=1 on every eigenmode (Appendix A.6, Proposition 3). Compared to previous approaches that designed high-pass filters for heterophilic graphs, this method is capable of aggregating not only high-frequency but also mid-range frequency. Theoretically, this would result in superior performance in real-world mixed graphs than previous methods. And due to the norm-preserving property of CTQW, the Dirichlet energy of the graph does not decay exponentially to zero, thereby preventing over-smoothing in the CTQW-GNN model (details are provided in Section 4.4). Quantum Properties Preserved in CTQW-based Aggregation. A natural concern is whether CTQW-based Aggregation genuinely inherits quantum properties—superposition and interference—or only borrows the vocabulary. Each column X(n):,k=∑lαl,kulX^(n)_:,k\!=\! _l _l,ku_l is a coherent linear combination over the eigenbasis ul\u_l\ of H, and the unitary propagator e−iHt=∑le−iλltulul†e^-iHt= _le^-i _ltu_lu_l rotates all eigenmodes by data-dependent phases while preserving their magnitudes |αl,k|| _l,k|. This realises (i) superposition—features evolve as coherent combinations of eigenmodes—and (i) interference—distinct phases let amplitudes add coherently when projected back to the node basis, producing cancellation at near neighbours and constructive build-up at distant nodes (Figure 2(a)). The operator f(⋅)f(·) concatenates real and imaginary parts and therefore preserves phase information rather than collapsing to a modulus. Spectral-Gap View of Information Propagation. The reason CTQW-based Aggregation avoids over-smoothing while still propagating information becomes transparent through the Laplacian spectral gap. Let 0=μ1≤⋯≤μN0= _1≤·s≤ _N be the eigenvalues of L and denote by Δ:=μ2 := _2 its spectral gap. Classical diffusion e−Lte^-Lt damps the l-th eigenmode by e−μlte^- _lt, so every non-trivial mode decays at rate ≥e−Δt≥ e^- t and embeddings collapse onto the leading eigenvector—the origin of over-smoothing. CTQW propagation e−iLte^-iLt instead has eigen-multipliers e−iμlte^-i _lt on the unit circle: no mode is attenuated regardless of Δ , mathematically guaranteeing that high- and mid-frequency content is preserved across layers. The gap instead governs the interference pattern: larger Δ desynchronises the leading modes’ phases faster, yielding the sharp ballistic peaks of Figure 2(a). Walk-Time Hyperparameter t. The time parameter t rescales each spectral phase λl(H)t _l(H)t; with λmax=‖H‖2 _ =\|H\|_2 and the above gap Δ , this leads to three regimes. When t≪1/λmaxt\! \!1/ _ , e−iHt≈I−iHte^-iHt\!≈\!I-iHt, so propagation remains local. When t∼π/Δt\! \!π/ , the leading modes accumulate an approximately π phase difference, producing long range ballistic peaks that are useful for heterophilic graphs. When t≫π/Δt\! \!π/ , the phases become densely mixed and the walk approaches its long time average. This analysis suggests a practical initialization range, t∈[π/(4λmax),π/Δ]t\!∈\![π/(4 _ ),π/ ], which we use across all datasets and validate in Section 5.3. 4.3. CTQW-Attention Aggregation While CTQW-based aggregation captures mid-range frequencies well for mixed-pattern graphs, it can underperform on graphs that are distinctly homophilic or heterophilic. We therefore add a spatial CTQW-Attention branch that exploits CTQW-induced long-range edges to recover homophilic neighbours that are several hops away in G. The adjacency of the new graph CTQWG_CTQW thresholds the CTQW amplitudes: (10) Aij=1|eij−iHt|≥ϵ,0otherwise,A_ij= cases1& |e^-iHt_ij |≥ε,\\ 0&otherwise, cases Selecting ϵε. We use ϵ=×10−3ε\!=\!5\!×\!10^-3 as the default, chosen once on the Amazon-ratings validation set and reused unchanged everywhere; a parameter-free fallback is to pick the smallest ϵε such that d¯(CTQW)≤20d¯() d(G_CTQW)\!≤\!20 d(G). The Lieb–Robinson bound (Appendix A.4) ensures that any ϵ∈[10−3,10−2]ε\!∈\![10^-3,10^-2] filters the same structurally meaningful edges (accuracy varies <0.7%<\!0.7\% across this range, Section 5.3). Attention from Graph Transformer aggregates information over CTQWG_CTQW only: (11) XAttention(n)=∑j∈iexp(qiTkj)∑u∈iexp(qiTku)vj,X_Attention^(n)= _j _i exp(q^T_ik_j) _u _iexp(q^T_ik_u)v_j, where iN_i is the set of neighbor nodes for node i in the graph CTQWG_CTQW. The terms Query (qiq_i), key (kik_i) and value (viv_i) respectively denote the outcomes derived for the feature of node i Xi(n)X^(n)_i in n-th layer of GNN after processing through a Multilayer Perceptron. XAttention(n)X_Attention^(n) is the output of n-th layer of CTQW-Attention Aggregation. With CTQW-Attention Aggregation, nodes can more effectively aggregate homophilic information from the neighbor nodes in CTQWG_CTQW. 4.4. CTQW-GNN and Over-smoothing We introduces LF Aggregation for aggregating low-frequency information, thereby compensating for the shortcoming of CTQW Aggregation methods in strongly homophilic graphs. LF Aggregation can be implemented using any homophilic GNN, such as GCN, GAT, SAGE, etc. In this paper, unless specifically stated otherwise, LF Aggregation refers to the use of GAT. We define the output of the n-th layer LF Aggregation as XLF(n)X_LF^(n). With these three aggregation methods, CTQW-GNN can aggregate mid-range frequency information through CTQW-based Aggregation,allowing it to manage mixed homophilic and heterophilic graphs, unlike most specialized GNNs. Additionally, CTQW-GNN utilize CTQW-Attention Aggregation to access a broader range of neighbor relationships in CTQWG_CTQW obtained through CTQW, thereby acquiring long-distance homophilic information. Furthermore, CTQW-GNN also aggregates low-frequency information of neighbor nodes on the original graph G by LF Aggregation, thus maintaining the performance of model in graphs with high homophily ratio. Thus, utilizing these three aggregation methods effectively addresses the issues of heterogeneous graphs; however, GNNs still face another significant challenge: Over-smoothing. Recent studies indicate that the graph attention mechanism is unable to prevent over-smoothing and results in an exponential loss of expressive capability (53). Therefore, if relying solely on LF Aggregation and CTQW-Attention Aggregation, GNNs will not be able to avoid the over-smoothing problem. CTQW-based Aggregation plays an important role in mitigating the problem of over-smoothing. Consequently, we define the input and output of each layer of the GNN as follows: (12) X(n+1)=σ([XLF(n)‖XCTQW(n)‖XAttention(n)]Wθ)X^(n+1)=σ ( [X^(n)_LF||X^(n)_CTQW||X^(n)_Attention ]W_θ ) where |||| means the concatenation along the feature dimension, WθW_θ is a learnable weight matrix. σ is a nonlinear activation function. Based on Definition 1, we first obtain a branch-wise criterion (proved in Appendix A.1): Proposition 0 (Branch-wise over-smoothing criterion). Let Y(n)=[XLF(n)‖XCTQW(n)‖XAttention(n)]Y^(n)=[X^(n)_LF||X^(n)_CTQW||X^(n)_Attention] be the pre-mixing representation. Y(n)Y^(n) over-smooths if and only if the Dirichlet energies of all three branches decay exponentially to zero. For the post-mixing feature X(n+1)X^(n+1), the same conclusion holds under the non-degenerate mixer condition in Appendix A.7; in particular, any branch with non-decaying energy prevents over-smoothing whenever WθW_θ does not annihilate that branch. In other words, the concatenated representation can collapse only when XCTQW(n)X^(n)_CTQW, XAttention(n)X^(n)_Attention and XLF(n)X^(n)_LF all independently converge towards constant values. Thus, as long as one retained branch does not exponentially converge, the CTQW-GNN can avoid over-smoothing. Given this characterization, the key question is whether the CTQW branch itself has a non-decaying energy floor. We answer it with the following proposition based on the unitary property of CTQW (proof in Appendix A.2): Proposition 0 (Non-decay of the CTQW branch). If H commutes with the Laplacian used in Dirichlet energy (e.g., H=LH=L, or H=AH=A on regular graphs), E(XCTQW(n))E(X^(n)_CTQW) is invariant across layers. With the default sparse-adjacency Hamiltonian H=AH=A, E(XCTQW(n))E(X^(n)_CTQW) has a positive Cesàro lower bound under the mild non-resonance condition stated in Appendix A.2; therefore it cannot exponentially converge to zero. We can observe that the CTQW-based Aggregation method plays a crucial role in mitigating the over-smoothing problem. The information aggregated through CTQW-based Aggregation is unitary rather than diffusive; it preserves non-trivial spectral content and provides a branch-level energy floor that LF or attention alone does not guarantee. 5. Experiment Table 1. Results of node classification tasks on different heterophilic datasets: mean ± std (%). The best result (α) for each dataset is highlight in bold and the second best (β) underlined, where Promotion is defined between these two values, i.e., (α−β)/β×100%(α-β)/β× 100\%. 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±0.3865.88 ± 0.38 45.90±0.5245.90 ± 0.52 50.89±1.3950.89 ± 1.39 72.95±1.0672.95 ± 1.06 28.75±0.8828.75 ± 0.88 80.81±4.7580.81 ± 4.75 89.36±0.7189.36 ± 0.71 49.52±1.7349.52 ± 1.73 33.88±1.7933.88 ± 1.79 GCN 73.69±0.7473.69 ± 0.74 48.70±0.7348.70 ± 0.73 89.75±0.5289.75 ± 0.52 83.64±0.6783.64 ± 0.67 30.59±0.2330.59 ± 0.23 55.14±5.1655.14 ± 5.16 91.01±0.6991.01 ± 0.69 50.18±3.2950.18 ± 3.29 39.06±1.5239.06 ± 1.52 GAT 81.02±0.4681.02 ± 0.46 47.95±0.5847.95 ± 0.58 92.10±0.6792.10 ± 0.67 83.98±0.5783.98 ± 0.57 35.98±0.2335.98 ± 0.23 52.16±6.6352.16 ± 6.63 92.44±0.8092.44 ± 0.80 45.02±1.7545.02 ± 1.75 32.21±1.6332.21 ± 1.63 SAGE 85.74±0.6785.74 ± 0.67 53.63±0.3953.63 ± 0.39 93.51±0.5793.51 ± 0.57 82.43±0.4482.43 ± 0.44 36.37±0.2136.37 ± 0.21 79.03±1.2079.03 ± 1.20 93.60±0.3193.60 ± 0.31 50.18±1.7850.18 ± 1.78 35.83±1.3235.83 ± 1.32 CDE-GRAND 91.64±0.2891.64 ± 0.28 47.63±0.4347.63 ± 0.43 95.50±5.2395.50 ± 5.23 83.98±0.5783.98 ± 0.57 34.72±1.4034.72 ± 1.40 86.22±3.3086.22 ± 3.30 97.99±0.3897.99 ± 0.38 68.45±2.4768.45 ± 2.47 55.04±1.7355.04 ± 1.73 GloGNN 59.63±0.6959.63 ± 0.69 36.89±0.1436.89 ± 0.14 51.08±1.2351.08 ± 1.23 73.39±1.1773.39 ± 1.17 37.35±1.3037.35 ± 1.30 84.32±4.1584.32 ± 4.15 88.49±0.4588.49 ± 0.45 70.04±2.1270.04 ± 2.12 61.21±1.9661.21 ± 1.96 PCNet 61.63±0.7161.63 ± 0.71 36.77±0.1636.77 ± 0.16 80.84±0.9680.84 ± 0.96 78.25±0.3978.25 ± 0.39 37.02±0.8737.02 ± 0.87 88.11±2.1788.11 ± 2.17 87.35±0.2987.35 ± 0.29 73.55±1.2673.55 ± 1.26 63.53±0.2663.53 ± 0.26 EG-GCN 63.32±0.3263.32 ± 0.32 38.33±0.7838.33 ± 0.78 79.67±0.8979.67 ± 0.89 81.41±1.1681.41 ± 1.16 37.80±0.6037.80 ± 0.60 88.92±3.3088.92 ± 3.30 85.56±0.8385.56 ± 0.83 71.93±2.5871.93 ± 2.58 61.24±1.9761.24 ± 1.97 GPRGNN 64.85±0.2764.85 ± 0.27 44.88±0.3444.88 ± 0.34 86.24±0.6186.24 ± 0.61 72.94±0.9772.94 ± 0.97 34.63±1.2234.63 ± 1.22 78.38±4.3678.38 ± 4.36 91.90±0.7891.90 ± 0.78 47.26±1.7447.26 ± 1.74 33.39±2.0533.39 ± 2.05 FSGNN 79.92±0.5679.92 ± 0.56 52.74±0.8352.74 ± 0.83 90.08±0.7090.08 ± 0.70 82.76±0.6182.76 ± 0.61 35.38±0.8135.38 ± 0.81 87.57±4.7187.57 ± 4.71 91.83±0.5391.83 ± 0.53 77.85±0.4677.85 ± 0.46 68.93±1.6968.93 ± 1.69 ACMP-GCN 71.27±0.5971.27 ± 0.59 44.76±0.5244.76 ± 0.52 76.15±1.1276.15 ± 1.12 75.03±0.9275.03 ± 0.92 37.57±0.3137.57 ± 0.31 86.23±3.0586.23 ± 3.05 92.68±0.3792.68 ± 0.37 69.04±1.7469.04 ± 1.74 58.02±1.8658.02 ± 1.86 FLODE 74.97±0.5374.97 ± 0.53 48.75±0.8248.75 ± 0.82 92.43±0.5192.43 ± 0.51 84.17±0.5884.17 ± 0.58 37.16±1.4237.16 ± 1.42 71.08±0.7271.08 ± 0.72 92.51±0.9792.51 ± 0.97 73.60±1.5573.60 ± 1.55 64.23±1.8464.23 ± 1.84 UniFilter 63.45±0.2363.45 ± 0.23 43.42±0.6543.42 ± 0.65 76.58±2.1376.58 ± 2.13 78.26±0.6778.26 ± 0.67 37.79±1.1137.79 ± 1.11 81.12±1.6381.12 ± 1.63 83.85±0.6583.85 ± 0.65 73.66±2.4473.66 ± 2.44 64.26±1.4664.26 ± 1.46 F-GRAND 93.06±0.5593.06 ± 0.55 49.01±0.5649.01 ± 0.56 96.04±0.2596.04 ± 0.25 82.68±0.8682.68 ± 0.86 38.28±0.7438.28 ± 0.74 92.97±4.3992.97 ± 4.39 98.73±0.6898.73 ± 0.68 71.45±1.9871.45 ± 1.98 60.86±1.0560.86 ± 1.05 D-CDE 93.87±0.4193.87 ± 0.41 49.43±1.2649.43 ± 1.26 96.47±1.8996.47 ± 1.89 83.02±0.8683.02 ± 0.86 38.37±1.5538.37 ± 1.55 91.83±5.4791.83 ± 5.47 98.58±0.1298.58 ± 0.12 64.88±2.1864.88 ± 2.18 45.62±2.1245.62 ± 2.12 CGNN 92.16±0.4692.16 ± 0.46 50.32±0.4150.32 ± 0.41 95.18±0.5595.18 ± 0.55 83.65±0.4683.65 ± 0.46 37.92±1.2737.92 ± 1.27 90.27±3.6290.27 ± 3.62 98.21±0.5198.21 ± 0.51 75.64±1.3175.64 ± 1.31 66.18±1.4566.18 ± 1.45 AMP 92.45±0.5592.45 ± 0.55 51.18±0.5851.18 ± 0.58 95.89±0.4395.89 ± 0.43 83.46±0.4183.46 ± 0.41 37.90±0.9337.90 ± 0.93 89.46±4.3189.46 ± 4.31 98.30±0.2798.30 ± 0.27 73.84±1.9573.84 ± 1.95 63.21±1.7863.21 ± 1.78 HeroFilter 94.02±0.3694.02 ± 0.36 52.13±0.4152.13 ± 0.41 96.51±0.3196.51 ± 0.31 84.30±0.3984.30 ± 0.39 38.59±1.0938.59 ± 1.09 93.51±3.1093.51 ± 3.10 98.81±0.4198.81 ± 0.41 76.78±1.6576.78 ± 1.65 67.45±1.4167.45 ± 1.41 CTQW-GNN (ours) 94.13±0.4294.13 ± 0.42 54.07±0.6354.07 ± 0.63 97.32±0.3497.32 ± 0.34 85.22±0.4385.22 ± 0.43 38.92±2.5538.92 ± 2.55 93.93±2.7893.93 ± 2.78 99.65±0.2299.65 ± 0.22 79.23±1.6379.23 ± 1.63 70.82±1.3170.82 ± 1.31 Promotion ↑ (%) 0.120.12 0.820.82 0.840.84 1.091.09 0.850.85 0.450.45 0.850.85 1.77 2.74 Table 2. Results of node classification tasks on different homophilic datasets: mean ± std (%). Datasets Cora Citeseer PubMed Computer Photo Homophily Ratio 0.81 0.72 0.79 0.78 0.83 ResNet 76.44±0.3076.44 ± 0.30 76.25±0.2876.25 ± 0.28 86.43±0.1386.43 ± 0.13 84.68±0.7884.68 ± 0.78 91.49±0.3091.49 ± 0.30 GCN 87.78±0.9687.78 ± 0.96 81.39±1.2381.39 ± 1.23 88.90±0.3288.90 ± 0.32 83.55±0.3883.55 ± 0.38 89.30±0.4489.30 ± 0.44 GAT 76.70±0.4276.70 ± 0.42 67.20±0.4667.20 ± 0.46 83.28±0.1283.28 ± 0.12 85.36±0.5085.36 ± 0.50 90.81±0.2290.81 ± 0.22 SAGE 86.58±0.2686.58 ± 0.26 78.24±0.3078.24 ± 0.30 86.85±0.1186.85 ± 0.11 83.11±0.2383.11 ± 0.23 90.51±0.2590.51 ± 0.25 CDE-GRAND 87.19±1.4487.19 ± 1.44 80.04±1.7580.04 ± 1.75 90.05±0.6490.05 ± 0.64 81.95±0.4381.95 ± 0.43 88.27±1.9488.27 ± 1.94 GloGNN 88.31±1.1588.31 ± 1.15 77.41±1.6577.41 ± 1.65 89.62±0.3589.62 ± 0.35 87.69±0.3387.69 ± 0.33 92.81±0.1392.81 ± 0.13 PCNet 82.81±0.5082.81 ± 0.50 69.92±0.7069.92 ± 0.70 80.01±0.8880.01 ± 0.88 83.29±1.5383.29 ± 1.53 89.51±1.0489.51 ± 1.04 EG-GCN 88.07±1.1688.07 ± 1.16 78.09±1.2078.09 ± 1.20 89.64±0.3889.64 ± 0.38 85.67±2.3285.67 ± 2.32 85.33±1.6885.33 ± 1.68 GPRGNN 79.51±0.3679.51 ± 0.36 67.63±0.3867.63 ± 0.38 85.07±0.0985.07 ± 0.09 87.63±0.4887.63 ± 0.48 94.60±0.3094.60 ± 0.30 FSGNN 87.73±1.3487.73 ± 1.34 77.19±0.8177.19 ± 0.81 89.73±3.1689.73 ± 3.16 91.53±1.0391.53 ± 1.03 95.07±0.5395.07 ± 0.53 ACMP-GCN 84.87±0.6784.87 ± 0.67 75.96±1.0775.96 ± 1.07 78.93±1.0178.93 ± 1.01 83.56±1.4283.56 ± 1.42 91.83±1.1791.83 ± 1.17 FLODE 86.44±1.1786.44 ± 1.17 78.07±1.6278.07 ± 1.62 89.02±0.3889.02 ± 0.38 88.44±0.4388.44 ± 0.43 93.86±0.8593.86 ± 0.85 UniFilter 89.12±0.8789.12 ± 0.87 80.28±1.3180.28 ± 1.31 90.19±0.4190.19 ± 0.41 87.98±0.5687.98 ± 0.56 94.03±0.7894.03 ± 0.78 F-GRAND 83.15±1.1983.15 ± 1.19 73.96±1.5273.96 ± 1.52 79.38±1.5579.38 ± 1.55 84.40±1.5084.40 ± 1.50 92.80±0.6092.80 ± 0.60 D-CDE 84.17±1.2284.17 ± 1.22 74.03±2.1374.03 ± 2.13 79.52±1.1879.52 ± 1.18 87.30±1.3087.30 ± 1.30 94.10±0.7094.10 ± 0.70 CGNN 87.62±1.3487.62 ± 1.34 78.93±1.5078.93 ± 1.50 89.51±0.4589.51 ± 0.45 88.42±0.6188.42 ± 0.61 93.84±0.4593.84 ± 0.45 AMP 88.30±0.9288.30 ± 0.92 79.71±1.2879.71 ± 1.28 89.86±0.3889.86 ± 0.38 89.04±0.5389.04 ± 0.53 94.21±0.4094.21 ± 0.40 HeroFilter 88.85±1.0588.85 ± 1.05 80.31±1.1880.31 ± 1.18 90.42±0.3690.42 ± 0.36 90.71±0.4290.71 ± 0.42 94.86±0.3194.86 ± 0.31 CTQW-GNN (ours) 91.31±2.1291.31 ± 2.12 82.97±1.3782.97 ± 1.37 91.38±0.7991.38 ± 0.79 92.48±0.1392.48 ± 0.13 95.87±0.3595.87 ± 0.35 Promotion ↑ (%) 2.46 3.31 1.06 1.041.04 0.840.84 We validate CTQW-GNN on homophilic and heterophilic node classification, then probe node subgroups, ablations, and hyperparameter sensitivity. 5.1. Experimental Setup Datasets and Metrics. We use five homophilic datasets (Cora (37), Citeseer (46), PubMed (39), Computers, Photo (39)) and nine heterophilic datasets: the classical four (Chameleon, Squirrel, Actor, Texas) (40) and the five new datasets of 41 (Roman-empire, Amazon-ratings, Minesweeper, Tolokers, Wiki-cooc). Splits follow (59) for homophilic data, (54) for the classical heterophilic four, and the original papers otherwise. We report ROC-AUC for the binary-class Minesweeper/Tolokers and accuracy elsewhere. Baselines and Implementation. We compare with five categories: graph-agnostic ResNet (18); classical GNNs (GCN (23), GAT (50), SAGE (17)); heterophily-specific (CDE-GRAND (57), GloGNN (28), EG-GCN (33), PCNet (25)); both-problem-aware (GPR-GNN (7), FSGNN (36), ACMP-GCN (51), FLODE (35), F-GRAND (21), D-CDE (58), UniFilter (20), CGNN (63), AMP (12), and HeroFilter (56)). CTQW-GNN uses the adjacency matrix as H and GAT as the LF Aggregation. 5.2. Main Experimental Results (a) Results on Amazon-ratings. (b) Results on Computer. Figure 3. Performance on node subgroups. We conduct extensive experiments in homophilic and heterophilic graph. We present the node classification results on heterophilic graphs in Table 1, while the results on homophilic graphs are reported in Table 2. Firstly, it is evident that CTQW-GNN model consistently performs best across all homophily ratio. This advantage arises from our proposed information aggregation methods. In cases of low homophily ratio, CTQW-Attention Aggregation captures long-range dependencies and CTQW-based Aggregation accesses high-frequency information, enhancing GNN performance on heterophilic graphs. For highly homophilic scenarios, LF Aggregation gathers low-frequency information, improving GNN performance on homophilic graphs. When the graph presents a mix of homophilic and heterophilic partern, mid-frequency information from CTQW-based Aggregation becomes critical. 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. Secondly, In the new dataset introduced by (41), most heterophily-specific GNNs significantly underperform compared to classic homophilic GNNs (e.g., SAGE achieves an average rank of 4.4, placing it second). Some methods even perform worse than graph-agnostic ResNet. This underscores the significant role of this new dataset in validating the effectiveness of heterophilic GNNs. Under these conditions, CTQW still outperforms most baseline models (outperforming the nearest rival by 1.48% on average). This outcome further demonstrates the efficacy of CTQW-GNN in tackling the critical challenge of heterophilic. Finally, it is evident that most GNNs designed to address both over-smoothing and heterophily problem underperform compared to those heterophily-specific models. This observation suggests that these methods sacrifice performance to mitigate over-smoothing. However, CTQW-GNN demonstrates superior results across all datasets, indicating a successful resolution of this challenge. CTQW-GNN not only effectively mitigates over-smoothing problem (Section 4.4) but also improves GNN efficacy on heterophilic graphs. 5.3. Further Analysis Performance on Node Subgroups. Recent studies criticize existing methods for focusing solely on purely homophilic or heterophilic graphs, ignoring the fact that real-world graphs typically exhibit a mixture of homophilic and heterophilic patterns (34). This means that homophilic graphs may contain heterophilic nodes, and vice versa; these nodes can often become bottlenecks that limit GNN performance. To further validate the superiority of CTQW-GNN in handling these mixed graphs, we divided the nodes of Computers and Amazon-ratings into Node Subgroups based on node homophily ratio, and then tested the performance of various GNN models on these different Node Subgroups. The results are shown in Figure 3. On heterophilic nodes, heterophily-specific GNNs outperform classic GNNs and vice versa for homophilic nodes; nodes that deviate from a graph’s typical pattern are the dominant performance bottleneck. CTQW-GNN outperforms existing methods on any node homophily ratio in both regimes, thanks to its simultaneous aggregation of low-, mid-, and high-frequency neighbor information together with long-range dependencies. Evolution of Dirichlet Energy. The norm-preserving property of CTQW prevents node features from collapsing to a constant. We track the Dirichlet energy on Minesweeper and Amazon-ratings (Figure 4a). Figure 4a demonstrates that the Dirichlet energy calculated from layer-wise node features via classic GNN methods (i.e., GCN, GAT) converges exponentially with the increasing layers. In contrast, the Dirichlet energy in CTQW consistently stabilizes around a constant value. Notably, when the CTQW-based Aggregation is not utilized (i.e., w/o CTQW), the Dirichlet energy of the graph initially remains stable for a period; however, it still rapidly converges exponentially. This further substantiates the efficacy of CTQW-based Aggregation in mitigating the over-smoothing problem. Ablation Study Our approach consists of three information aggregation methods: (1) CTQW-based Aggregation, (2) CTQW-Attention Aggregation, (3) LF Aggregation. To verify the function of each module and its efficacy in enhancing model performance, we conducted ablation experiments on the Minesweeper dataset to analyze the impact of these aggregation methods on GNN performance. We consider removing the three aggregation, respectively, and the ablation results on node Subgroups are shown in Figure 4c. Firstly, it is evident that the removal of any aggregation method results in a reduction of the radar chart area, indicating that all three information aggregation methods significantly enhance model performance. Secondly, the removal of LF, CTQW-based, and CTQW-Attention aggregations leads to different degrees of performance degradation across GNN node subgroups. Specifically, omitting CTQW-Attention hurts low-homophily subgroups (00–0.40.4) the most because long-range homophilic retrieval is crucial there, while omitting LF hurts high-homophily subgroups (0.60.6–1.01.0) where low-pass aggregation is beneficial. Removing CTQW-based aggregation causes the largest drop on mixed-pattern nodes (0.40.4–0.60.6), where mid-frequency information is most important. Furthermore, as Figure 4a illustrates, removing CTQW-based aggregation also reintroduces over-smoothing. Sensitivity to Walk Time t. Walk time t controls the propagation range of the CTQW branch. We evaluate its influence by sweeping nine values from 10−610^-6 to 10210^2 on four representative datasets, as shown in Table 3. When t is extremely small (10−610^-6–10−410^-4), the CTQW propagation is weak and the performance is relatively low. As t increases to the middle range (10−310^-3–10−110^-1), the performance improves substantially and remains close to the best result on all four datasets. For example, the results on Roman-empire, Amazon-ratings, and Minesweeper all stay within 1%1\% of their best scores across this range, while Cora also keeps a stable plateau from 10−210^-2 to 11. The results indicate that CTQW-GNN is not sensitive to a precise choice of t. The best performance does not appear at a single isolated value; instead, each dataset has a broad stable region where different t values lead to very similar accuracy. Performance only drops clearly when t is too small or too large. Therefore, CTQW-GNN shows robust performance with respect to the walk time hyperparameter. Table 3. Pserformance of CTQW-GNN under different walk time t. t 10−610^-6 10−510^-5 10−410^-4 10−310^-3 10−210^-2 10−110^-1 11 1010 10210^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 Sensitivity to the Sparsification Threshold ϵε. The threshold ϵε controls how many CTQW edges are kept: a smaller ϵε keeps more long-range connections, while a larger ϵε prunes more connections. We test five values of ϵε on four representative datasets, and the results are shown in Table 4. Overall, CTQW-GNN is robust to ϵε. When ϵε changes from 10−410^-4 to 10−210^-2, the performance on all four datasets remains very stable and close to the best result. This shows that the model does not rely on one specific sparsification threshold. When ϵε is too small, many weak CTQW connections are retained, which brings more computation but gives little or no accuracy improvement. When ϵε is too large, too many useful long-range connections are removed, and the performance drops clearly. Therefore, a moderate threshold such as ×10−35\!×\!10^-3 provides a good balance between performance and sparsity. Table 4. Effect of sparsification threshold ϵε. Dataset 10−410^-4 10−310^-3 ×10−35\!×\!10^-3 10−210^-2 ×10−25\!×\!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 5.4. Time Complexity Analysis Although e−iHte^-iHt appears dense, CTQW-GNN never forms this operator explicitly. The graph CTQWG_CTQW is built once via a sparse degree-K Chebyshev expansion (K=20K\!=\!20) at cost (K|ℰ|)O(K|E|), amortised over all epochs. Per layer, the CTQW branch applies e−iHtX(n)e^-iHtX^(n) via a k-step Krylov projection (k=20k\!=\!20) at (k|ℰ|d)O(k|E|d); the LF and CTQW-Attention branches each cost (|ℰ|d+Nd2)O(|E|d+Nd^2), the same as GCN (23) and GAT (50). Since the sparsification rule (Section 5.3) keeps |ℰCTQW|=(|ℰ|)|E_CTQW|\!=\!O(|E|), the total per-layer cost is ((k+1)|ℰ|d+Nd2)O\! ((k+1)|E|d+Nd^2 )—linear in |ℰ||E| and matching GCN/GAT up to a small constant factor k+≤21k+1\!≤\!21. 6. Conclusion Existing GNN methods predominantly address over-smoothing and heterophily separately, or mitigate over-smoothing at the cost of expressiveness. We propose CTQW-GNN, integrating three aggregators—two CTQW-inspired and one classical—to tackle both issues by aggregating low-, mid-, high-frequency, and long-range information through a unitary, norm-preserving propagator. Theoretically, the CTQW branch has a positive spectral/Cesàro energy floor and therefore cannot decay exponentially (Prop. 2, Lemma 2); empirically, CTQW-GNN reaches state-of-the-art accuracy on all 14 benchmarks at a per-edge cost asymptotically equal to GCN/GAT. Future work will study learnable low-pass companions and graph-Hamiltonian design. 7. Acknowledgments The work is supported by the National Natural Science Foundation of China (No. 62276269 and No. 62576331), which is greatly appreciated. Appendix A Proof Notation. =(,ℰ)G=(V,E), N=||N\!=\!|V|, L=I−D−1/2AD−1/2L\!=\!I\!-\!D^-1/2AD^-1/2. The Hamiltonian H is Hermitian (default H=AH\!=\!A). L=VΛLV†L\!=\!V _LV^\! with eigenvalues =μ1≤μ2≤⋯≤μN0\!=\! _1\!≤\! _2\!≤\!·s\!≤\! _N and gap Δ:=μ2 \!:=\! _2. Let P⟂=I−v1v1†P_ \!=\!I-v_1v_1 be the projection onto the non-constant Laplacian subspace. For X∈ℂN×dX\!∈\!C^N× d define spectral coordinates X~:=V†X X\!:=\!V^\! X (rows indexed by mode ℓ ). The matrix-form Dirichlet energy (S.1) E(X)=tr(X†LX)=∑ℓ=1Nμℓ‖X~ℓ‖22E(X)\;=\;tr(X^\! LX)\;=\; _ =1^N _ \,\| X_ \|_2^2 agrees with Eq. 2 up to a constant fixed by G (9). Standing assumptions (verified on every benchmark): (A1) Δ>0 \!>\!0; (A2) ‖P⟂X(0)‖F>0\|P_ X^(0)\|_F\!>\!0. For the default H=AH\!=\!A we additionally use the standard non-resonance condition (A3) that the CTQW orbit does not concentrate all feature energy in the constant Laplacian mode; equivalently, lim infT→∞T−1∑n<T‖P⟂e−inHtX(0)‖F2>0 _T→∞T^-1 _n<T\|P_ e^-inHtX^(0)\|_F^2>0. This excludes a measure-zero set of walk times and initial features, and is directly checked by the branch-energy diagnostic in Figure 4a. A.1. Proof of Proposition 1 Proof. Let Y(n)=[XLF(n)‖XCTQW(n)‖XAtt(n)]∈ℂN×3dY^(n)\!=\![X^(n)_LF\!\,\|\,\!X^(n)_CTQW\!\,\|\,\!X^(n)_Att]\!∈\!C^N× 3d be the pre-mixing concatenation. By Eq. S.1 and the column-block structure of Y(n)Y^(n), (S.2) E(Y(n))=tr(Y(n)†LY(n))=ELF(n)+ECTQW(n)+EAtt(n),E(Y^(n))=tr(Y^(n) LY^(n))=E_LF^(n)+E_CTQW^(n)+E_Att^(n), since tr([P∥Q]†L[P∥Q])=tr(P†LP)+tr(Q†LQ)tr([P\,\|\,Q] L[P\,\|\,Q])=tr(P^\! LP)+tr(Q^\! LQ) for any pair of matrices P,QP,Q. Because all three terms are non-negative, E(Y(n))≤ae−bnE(Y^(n))≤ ae^-bn holds iff each branch energy is bounded by an exponential envelope (with rate at least b in the “only-if” direction and the minimum branch rate in the “if” direction). This proves the exact branch-wise criterion for the representation before the learned mixer. For the post-mixing features X(n+1)=σ(Y(n)Wθ)X^(n+1)\!=\!σ(Y^(n)W_θ), Lemma 1 gives the always-valid upper bound, and Lemma 3 gives the corresponding lower bound whenever the learned projection keeps a non-zero CTQW component. Thus the criterion transfers to the actual layer output under the non-degenerate mixer condition stated in Proposition 1. ∎ Lemma 1. Let Y∈ℂN×mY\!∈\!C^N× m, W∈ℝm×dW\!∈\!R^m× d, and σ be entrywise ρ+ _+-Lipschitz with σ(0)=0σ(0)\!=\!0. Then E(σ(YW))≤ρ+2‖W‖22E(Y)E(σ(YW))\!≤\! _+^2\|W\|_2^2E(Y). If, on the subspace spanned by layer-wise edge differences, the map z↦σ(zW)z σ(zW) has gain at least ρ−>0 _->0, then E(σ(YW))≥ρ−2E(Y)E(σ(YW))\!≥\! _-^2E(Y) on that subspace. Proof. Write E(Z)=∑(i,j)∈ℰ‖zi/di−zj/dj‖22E(Z)= _(i,j) \|z_i/\! d_i-z_j/\! d_j\|_2^2. For each edge term, entrywise Lipschitzness gives ‖σ(u)−σ(v)‖2≤ρ+‖u−v‖2\|σ(u)\!-\!σ(v)\|_2\!≤\! _+\|u\!-\!v\|_2, and ‖(u−v)⊤W‖2≤‖W‖2‖u−v‖2\|(u-v) W\|_2\!≤\!\|W\|_2\|u-v\|_2 yields the upper bound after summing over edges. The lower bound is exactly the stated non-degenerate gain condition applied to the same edge-difference terms. Degenerate projections that cancel an entire branch are therefore excluded explicitly rather than hidden inside an invalid full-rank assumption. ∎ A.2. Proof of Proposition 2 Proof. Let Ut:=e−iHtU_t\!:=\!e^-iHt and f(z)=[Re(z)∥Im(z)]f(z)\!=\![Re(z)\|Im(z)]. The map f is an isometry from ℂN×dC^N× d to ℝN×2dR^N× 2d, so it does not change Dirichlet energy except for this real representation. Commuting case. If H commutes with L (in particular H=LH=L, or H=AH=A on regular graphs after normalization), UtU_t and L are simultaneously diagonalizable. Each non-trivial Laplacian coefficient is multiplied by a unit-modulus phase, hence (S.3) E(f(UtnX(0)))=∑ℓ=1Nμℓ‖X~ℓ(0)‖22=E(X(0)).E(f(U_t^nX^(0)))= _ =1^N _ \| X^(0)_ \|_2^2=E(X^(0)). By Lemma 2, this constant is positive whenever the initial features have a non-constant component. Default H=AH=A. Now H and L need not commute, so pointwise invariance is not claimed. Instead, Lemma 2 gives E(f(UtnX(0)))≥Δ‖P⟂UtnX(0)‖F2E(f(U_t^nX^(0)))≥ \|P_ U_t^nX^(0)\|_F^2. Averaging over layers and applying (A3) yields (S.4) lim infT→∞1T∑n<TE(f(UtnX(0)))≥Δη0>0, _T→∞ 1T _n<TE(f(U_t^nX^(0)))≥ _0>0, where η0=lim infT→∞T−1∑n<T‖P⟂UtnX(0)‖F2 _0\!=\! _T→∞T^-1 _n<T\|P_ U_t^nX^(0)\|_F^2. If E(f(UtnX(0)))≤ae−bnE(f(U_t^nX^(0)))≤ ae^-bn for some a,b>0a,b>0, its Cesàro average would converge to zero, contradicting the positive lower bound. Therefore the CTQW branch cannot exponentially over-smooth. ∎ A.3. Spectral-Gap Lower Bound Lemma 2. For any X∈ℂN×dX ^N× d, E(X)≥Δ‖P⟂X‖F2E(X)\!≥\! \|P_ X\|_F^2. In the commuting CTQW case this gives E(f(UtnX(0)))≥Δ‖P⟂X(0)‖F2>0E(f(U_t^nX^(0)))\!≥\! \|P_ X^(0)\|_F^2\!>\!0 for every n≥0n\!≥\!0. Proof. Since P⟂P_ removes only the zero eigenvector of L, E(X)=∑ℓ≥2μℓ‖X~ℓ‖22≥Δ∑ℓ≥2‖X~ℓ‖22=Δ‖P⟂X‖F2E(X)= _ ≥ 2 _ \| X_ \|_2^2≥ _ ≥ 2\| X_ \|_2^2= \|P_ X\|_F^2. If H commutes with L, ‖P⟂UtnX(0)‖F=‖P⟂X(0)‖F\|P_ U_t^nX^(0)\|_F=\|P_ X^(0)\|_F, and (A2) makes the bound strictly positive. ∎ Classical diffusion e−Lte^-Lt admits the matching upper bound E(X(n+1))≤e−2ΔtE(X(n))E(X^(n+1))\!≤\!e^-2 tE(X^(n)), decaying exponentially at rate Δ . The same spectral quantity drives diffusion over-smoothing but yields a Δ -linear floor for CTQW. A.4. Walk-Time t and Effective Propagation Radius Proposition 0. Let ‖H‖2=λmax\|H\|_2\!=\! _ and d(i,j)d_G(i,j) the geodesic distance. For any t>0t\!>\!0, (S.5) |(e−iHt)ij|≤exp(λmaxt)(λmaxt)d(i,j)d(i,j)!.|(e^-iHt)_ij|\;≤\; ( _ t) ( _ t)^d_G(i,j)d_G(i,j)!. Consequently, amplitudes beyond a radius linear in λmaxt _ t are factorially small; the implementation uses the conservative screening radius reff(t)=⌈2λmaxt/π⌉r_eff(t)\!=\! 2 _ t/π and then applies the empirical ϵε threshold. Proof. Expand e−iHt=∑k≥0(−it)kHk/k!e^-iHt\!=\! _k≥ 0(-it)^kH^k/k!. Because H is supported on graph edges, (Hk)ij=0(H^k)_ij=0 whenever k<d(i,j)k<d_G(i,j). Thus only walks of length at least d(i,j)d_G(i,j) contribute. Bounding |(Hk)ij|≤‖Hk‖2≤λmaxk|(H^k)_ij|≤\|H^k\|_2≤ _ ^k gives |(e−iHt)ij|≤∑k≥d(i,j)(λmaxt)k!≤exp(λmaxt)(λmaxt)d(i,j)d(i,j)!,|(e^-iHt)_ij|≤ _k≥ d_G(i,j) ( _ t)^kk!≤ ( _ t) ( _ t)^d_G(i,j)d_G(i,j)!, which is a graph Lieb–Robinson-type bound (30). Stirling’s formula shows factorial decay once d(i,j)d_G(i,j) exceeds a constant multiple of λmaxt _ t, justifying a linear truncation radius. On a path, the exact amplitude is |J|i−j|(2t)||J_|i-j|(2t)| (8), whose ballistic front is also linear in t; this motivates the constant used by reff(t)r_eff(t). ∎ A.5. Krylov Implementation Error Proposition 0. Let U^t(k) U_t^(k) denote the k-step Lanczos approximation of e−iHte^-iHt. For any x∈ℂNx\!∈\!C^N and any k≥4λmaxtk\!≥\!4 _ t, (S.6) ‖e−iHtx−U^t(k)x‖2≤ 12‖x‖2exp(−k216λmaxt).\|e^-iHtx- U_t^(k)x\|_2\;≤\;12\,\|x\|_2\, \! (\!- k^216 _ t ). Hence the discretised CTQW branch satisfies (S.7) ECTQWapprox(X(n))≥ECTQWexact(X(n))−ϵkry,E_CTQW^approx(X^(n))\;≥\;E_CTQW^exact(X^(n))- _kry, with ϵkry≤144μmaxB2exp(−k2/(8λmaxt)) _kry\!≤\!144\, _ B^2\, \! (\!-k^2/(8 _ t) ) whenever the layer input satisfies ‖X(n)‖F≤B\|X^(n)\|_F≤ B. Sketch. Eq. S.6 is Theorem 4 of 19 specialised to the skew-Hermitian generator −iH-iH of spectral radius λmax _ ; constants 12,1612,16 track through their proof. For Eq. S.7, write the one-application error as Ξ with ∥Ξ∥F≤12Be−k2/(16λmaxt)\| \|_F\!≤\!12Be^-k^2/(16 _ t). Since L⪯μmaxIL _ I, |E(X+Ξ)−E(X)|≤μmax‖Ξ‖F2+2μmax‖Ξ‖F‖X‖F|E(X+ )-E(X)|≤ _ \| \|_F^2+2 _ \| \|_F\|X\|_F, yielding the stated perturbation bound after absorbing constants. Thus Krylov approximation can only reduce the CTQW energy floor by a controllable, exponentially small term. ∎ At k=20k\!=\!20 and the selected t range, the exponential term is negligible in all benchmarks; the implementation therefore preserves the qualitative non-decay guarantee up to numerical precision. A.6. All-Pass Spectral Response of CTQW-based Aggregation Proposition 0. Let H admit the spectral decomposition H=UΛU†H\!=\!U U with real eigenvalues λll=1N\ _l\_l=1^N. For any input X∈ℂN×dX\!∈\!C^N× d, write X=∑lulαl⊤X\!=\! _lu_l _l with αl∈ℂd _l\!∈\!C^d the spectral coefficients. Then the CTQW propagator preserves the magnitude of every spectral component: (S.8) ‖(e−iHtX)mode l‖2=|e−iλlt|‖αl‖2=‖αl‖2∀l=1,…,N.\|(\,e^-iHtX\,)_mode l\|_2\;=\;|e^-i _lt|\,\| _l\|_2\;=\;\| _l\|_2 ∀\,l\!=\!1,…,N. Hence CTQW-based Aggregation realises an exact all-pass filter on the eigenbasis of H. Proof. Expand X=∑lulαl⊤X\!=\! _lu_l _l . Since ul\u_l\ is orthonormal and e−iHtul=e−iλltule^-iHtu_l\!=\!e^-i _ltu_l, e−iHtX=∑le−iλltulαl⊤e^-iHtX\!=\! _le^-i _lt\,u_l _l , so the l-th mode coefficient becomes e−iλltαle^-i _lt _l. As λl∈ℝ _l\!∈\!R, |e−iλlt|=1|e^-i _lt|\!=\!1, giving Eq. S.8. In contrast, classical diffusion e−Lte^-Lt multiplies the l-th coefficient by e−λlt<1e^- _lt\!<\!1 for λl>0 _l\!>\!0, attenuating every non-trivial mode at rate ≥e−Δt≥\!e^- t per layer; this strictly contradicts the all-pass property of CTQW. ∎ Proposition 3 formalises the magnitude-preserving filter claim made in the method section: no frequency component is damped, which is precisely the structural reason CTQW-based Aggregation supplies the energy floor used in Proposition 2. A.7. Branch-Mixing Floor Lemma 3. Let (n)S^(n) be the set of normalized full edge differences δ=[δLF,δCTQW,δAtt]δ=[ _LF, _CTQW, _Att] at layer n. Assume the learned mixer has conditional CTQW gain cCTQW>0c_CTQW>0 on this subspace, meaning ‖σ(δWθ)‖2≥cCTQW‖δCTQW‖2\|σ(δ W_θ)\|_2≥ c_CTQW\| _CTQW\|_2 for all δ∈(n)δ ^(n). Then (S.9) E(X(n+1))≥cCTQW2ECTQW(n).E(X^(n+1))\;≥\;c_CTQW^2\,E_CTQW^(n). Proof. Apply the gain assumption to each normalized edge difference of the CTQW block and sum over edges. This rules out the only degenerate failure mode in which the learned projection intentionally maps all CTQW differences to zero. Combining this lemma with Proposition 2 shows that a retained CTQW branch prevents exponential decay of the mixed representation. ∎ References Aharonov et al. (1993) Y. Aharonov, L. Davidovich, and N. Zagury Quantum random walks. Physical Review A 48 (2), p. 1687–1690. Cited by: §3. Al-Mohy and Higham (2011) A. H. Al-Mohy and N. J. Higham Computing the action of the matrix exponential, with an application to exponential integrators. SIAM Journal on Scientific Computing 33 (2), p. 488–511. Cited by: §4.2. Aubry et al. (2011) M. Aubry, U. Schlickewei, and D. Cremers The wave kernel signature: a quantum mechanical approach to shape analysis. In 2011 IEEE International Conference on Computer Vision Workshops (ICCV Workshops), Vol. , p. 1626–1633. External Links: Document, ISSN Cited by: §1. Bo et al. (2021) D. Bo, X. Wang, C. Shi, and H. Shen Beyond low-frequency information in graph convolutional networks. In Proceedings of the AAAI conference on artificial intelligence, Vol. 35, p. 3950–3957. Cited by: §1, §2. Bose (2003) S. Bose Quantum communication through an unmodulated spin chain. Physical review letters 91 (20), p. 207901. Cited by: §4.2. Chamberlain et al. (2021) B. Chamberlain, J. Rowbottom, M. I. Gorinova, M. Bronstein, S. Webb, and E. Rossi GRAND: graph neural diffusion. In Proceedings of the 38th International Conference on Machine Learning, M. Meila and T. Zhang (Eds.), Proceedings of Machine Learning Research, Vol. 139, p. 1407–1418. External Links: Link Cited by: §1. Chien et al. (2021) E. Chien, J. Peng, P. Li, and O. Milenkovic Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, External Links: Link Cited by: §1, §5.1. Childs et al. (2002) A. M. Childs, E. Farhi, and S. Gutmann An example of the difference between quantum and classical random walks. Quantum Information Processing 1, p. 35–43. Cited by: §A.4, §3, §4.2. Chung (1997) F. R. Chung Spectral graph theory. Vol. 92, American Mathematical Soc.. Cited by: Appendix A, §3. Eliasof et al. (2021) M. Eliasof, E. Haber, and E. Treister Pde-gcn: novel architectures for graph neural networks motivated by partial differential equations. Advances in neural information processing systems 34, p. 3836–3849. Cited by: §1. Eliasof et al. (2024) M. Eliasof, E. Haber, and E. Treister Feature transportation improves graph neural networks. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 38, p. 11874–11882. Cited by: §1. Errica et al. (2025) F. Errica, H. Christiansen, V. Zaverkin, T. Maruyama, M. Niepert, and F. Alesiani Adaptive message passing: a general framework to mitigate oversmoothing, oversquashing, and underreaching. In Proceedings of the 42nd International Conference on Machine Learning, PMLR, Vol. 267, p. 15490–15515. Cited by: §5.1. Farhi and Gutmann (1998) E. Farhi and S. Gutmann Quantum computation and decision trees. Physical Review A 58 (2), p. 915. Cited by: §3, §4.2. Gao et al. (2023) Y. Gao, X. Wang, X. He, Z. Liu, H. Feng, and Y. Zhang Addressing heterophily in graph anomaly detection: a perspective of graph spectrum. In Proceedings of the ACM Web Conference 2023, p. 1528–1538. Cited by: §1. Giraldo et al. (2023) J. H. Giraldo, K. Skianis, T. Bouwmans, and F. D. Malliaros On the trade-off between over-smoothing and over-squashing in deep graph neural networks. In Proceedings of the 32nd ACM International Conference on Information and Knowledge Management, CIKM ’23, New York, NY, USA, p. 566–576. External Links: ISBN 9798400701245, Link, Document Cited by: §1. Guo and Wei (2023) Y. Guo and Z. Wei Graph neural networks with learnable and optimal polynomial bases. In Proceedings of the 40th International Conference on Machine Learning, A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett (Eds.), Proceedings of Machine Learning Research, Vol. 202, p. 12077–12097. External Links: Link Cited by: §2. Hamilton et al. (2017) W. L. Hamilton, R. Ying, and J. Leskovec Inductive representation learning on large graphs. In NIPS, Cited by: §5.1. He et al. (2016) K. He, X. Zhang, S. Ren, and J. Sun Deep residual learning for image recognition. In Proceedings of the IEEE conference on computer vision and pattern recognition, p. 770–778. Cited by: §5.1. Hochbruck and Lubich (1997) M. Hochbruck and C. Lubich On krylov subspace approximations to the matrix exponential operator. SIAM Journal on Numerical Analysis 34 (5), p. 1911–1925. Cited by: §A.5. Huang et al. (2024) K. Huang, Y. G. Wang, M. Li, and P. Lio How universal polynomial bases enhance spectral graph neural networks: heterophily, over-smoothing, and over-squashing. In International Conference on Machine Learning, p. 20310–20330. Cited by: §5.1. [21] Q. Kang, K. Zhao, Q. Ding, F. Ji, X. Li, W. Liang, Y. Song, and W. P. Tay Unleashing the potential of fractional calculus in graph neural networks with frond. In The Twelfth International Conference on Learning Representations, Cited by: §5.1. Kempe (2003) J. Kempe Quantum random walks: an introductory overview. Contemporary Physics 44 (4), p. 307–327. Cited by: §3. Kipf and Welling (2017) T. N. Kipf and M. Welling Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), Cited by: §5.1, §5.4. Lanczos (1950) C. Lanczos An iteration method for the solution of the eigenvalue problem of linear differential and integral operators. Journal of Research of the National Bureau of Standards 45 (4), p. 255–282. Cited by: §4.2. Li et al. (2024) B. Li, E. Pan, and Z. Kang Pc-conv: unifying homophily and heterophily with two-fold filtering. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 38, p. 13437–13445. Cited by: §1, §5.1. Li et al. (2018) Q. Li, Z. Han, and X. Wu Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the Thirty-Second AAAI Conference on Artificial Intelligence and Thirtieth Innovative Applications of Artificial Intelligence Conference and Eighth AAAI Symposium on Educational Advances in Artificial Intelligence, AAAI’18/IAAI’18/EAAI’18. External Links: ISBN 978-1-57735-800-8 Cited by: §1. Li et al. (2019) Q. Li, X. Wu, H. Liu, X. Zhang, and Z. Guan Label efficient semi-supervised learning via graph filtering. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, p. 9582–9591. Cited by: §1. Li et al. (2022) X. Li, R. Zhu, Y. Cheng, C. Shan, S. Luo, D. Li, and W. Qian Finding global homophily in graph neural networks when meeting heterophily. In International Conference on Machine Learning, p. 13242–13256. Cited by: §2, §4.2, §5.1. Liang et al. (2024) L. Liang, X. Hu, Z. Xu, Z. Song, and I. King Predicting global label relationship matrix for graph neural networks under heterophily. Advances in Neural Information Processing Systems 36. Cited by: §1, §2. Lieb and Robinson (1972) E. H. Lieb and D. W. Robinson The finite group velocity of quantum spin systems. Communications in Mathematical Physics 28 (3), p. 251–257. Cited by: §A.4. Lim et al. (2021) D. Lim, F. Hohne, X. Li, S. L. Huang, V. Gupta, O. Bhalerao, and S. N. Lim Large scale learning on non-homophilous graphs: new benchmarks and strong simple methods. Advances in Neural Information Processing Systems 34, p. 20887–20902. Cited by: §4.2. Liu et al. (2021) C. Liu, L. Wen, Z. Kang, G. Luo, and L. Tian Self-supervised consensus representation learning for attributed graph. In Proceedings of the 29th ACM international conference on multimedia, p. 2654–2662. Cited by: §1. Liu et al. (2025) S. Liu, D. He, Z. Yu, D. Jin, Z. Feng, and W. Zhang Integrating co-training with edge discrimination to enhance graph neural networks under heterophily. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 39, p. 18960–18968. Cited by: §5.1. Mao et al. (2024) H. Mao, Z. Chen, W. Jin, H. Han, Y. Ma, T. Zhao, N. Shah, and J. Tang Demystifying structural disparity in graph neural networks: can one size fit all?. Advances in neural information processing systems 36. Cited by: §1, §4.2, §5.3. Maskey et al. (2024) S. Maskey, R. Paolino, A. Bacho, and G. Kutyniok A fractional graph laplacian approach to oversmoothing. Advances in Neural Information Processing Systems 36. Cited by: §1, §1, §4.2, §5.1. Maurya et al. (2022) S. K. Maurya, X. Liu, and T. Murata Simplifying approach to node classification in graph neural networks. Journal of Computational Science 62, p. 101695. Cited by: §5.1. McCallum et al. (2000) A. K. McCallum, K. Nigam, J. Rennie, and K. Seymore Automating the construction of internet portals with machine learning. Information Retrieval 3, p. 127–163. Cited by: §5.1. Moler and Van Loan (2003) C. Moler and C. Van Loan Nineteen dubious ways to compute the exponential of a matrix, twenty-five years later. SIAM Review 45 (1), p. 3–49. Cited by: §4.2. Namata et al. (2012) G. Namata, B. London, L. Getoor, B. Huang, and U. Edu Query-driven active surveying for collective classification. In 10th international workshop on mining and learning with graphs, Vol. 8, p. 1. Cited by: §5.1. Pei et al. (2020) H. Pei, B. Wei, K. C. Chang, Y. Lei, and B. Yang Geom-gcn: geometric graph convolutional networks. arXiv preprint arXiv:2002.05287. Cited by: §5.1. Platonov et al. (2023) O. Platonov, D. Kuznedelev, M. Diskin, A. Babenko, and L. Prokhorenkova A critical look at evaluation of gnns under heterophily: are we really making progress?. In The Eleventh International Conference on Learning Representations, Cited by: §5.1, §5.2. Quan et al. (2023) Y. Quan, J. Ding, C. Gao, L. Yi, D. Jin, and Y. Li Robust preference-guided denoising for graph based social recommendation. In Proceedings of the ACM Web Conference 2023, p. 1097–1108. Cited by: §1. Rong et al. (2019) Y. Rong, W. Huang, T. Xu, and J. Huang Dropedge: towards deep graph convolutional networks on node classification. arXiv preprint arXiv:1907.10903. Cited by: §1, §2. Rusch et al. (2023) T. K. Rusch, M. M. Bronstein, and S. Mishra A survey on oversmoothing in graph neural networks. arXiv preprint arXiv:2303.10993. Cited by: §1, §2, §3. Rusch et al. (2022) T. K. Rusch, B. Chamberlain, J. Rowbottom, S. Mishra, and M. Bronstein Graph-coupled oscillator networks. In International Conference on Machine Learning, p. 18888–18909. Cited by: §1, §1, §2, §3. Sen et al. (2008) P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Galligher, and T. Eliassi-Rad Collective classification in network data. AI magazine 29 (3), p. 93–93. Cited by: §5.1. Shi et al. (2016) C. Shi, Y. Li, J. Zhang, Y. Sun, and P. S. Yu A survey of heterogeneous information network analysis. IEEE Transactions on Knowledge and Data Engineering 29 (1), p. 17–37. Cited by: §3. Shi et al. (2020) Y. Shi, Z. Huang, S. Feng, H. Zhong, W. Wang, and Y. Sun Masked label prediction: unified message passing model for semi-supervised classification. arXiv preprint arXiv:2009.03509. Cited by: §1. Tu et al. (2024) G. Tu, T. Xie, B. Liang, H. Wang, and R. Xu Adaptive graph learning for multimodal conversational emotion detection. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 38, p. 19089–19097. Cited by: §1, §2. Veličković et al. (2018) P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio Graph Attention Networks. International Conference on Learning Representations. Note: accepted as poster External Links: Link Cited by: §5.1, §5.4. Wang et al. (2023) Y. Wang, K. Yi, X. Liu, Y. G. Wang, and S. Jin ACMP: allen-cahn message passing with attractive and repulsive forces for graph neural networks. In The Eleventh International Conference on Learning Representations, External Links: Link Cited by: §1, §1, §5.1. Wu et al. (2019) F. Wu, A. Souza, T. Zhang, C. Fifty, T. Yu, and K. Weinberger Simplifying graph convolutional networks. In International conference on machine learning, p. 6861–6871. Cited by: §1. Wu et al. (2024) X. Wu, A. Ajorlou, Z. Wu, and A. Jadbabaie Demystifying oversmoothing in attention-based graph neural networks. Advances in Neural Information Processing Systems 36. Cited by: §4.4. Yan et al. (2022) Y. Yan, M. Hashemi, K. Swersky, Y. Yang, and D. Koutra Two sides of the same coin: heterophily and oversmoothing in graph convolutional neural networks. In 2022 IEEE International Conference on Data Mining (ICDM), p. 1287–1292. Cited by: §1, §5.1. Yu et al. (2023) H. Yu, Z. Xu, X. Qian, X. Qian, and S. Ji Efficient and equivariant graph networks for predicting quantum hamiltonian. In International Conference on Machine Learning, p. 40412–40424. Cited by: §1. Zhang et al. (2025) S. Zhang, H. Wang, J. Lin, X. Guo, Y. Zhu, S. Zhang, D. Fu, and D. Zhou HeroFilter: adaptive spectral graph filter for varying heterophilic relations. In Advances in Neural Information Processing Systems, Cited by: §5.1. Zhao et al. (2023) K. Zhao, Q. Kang, Y. Song, R. She, S. Wang, and W. P. Tay Graph neural convection-diffusion with heterophily. In Proc. International Joint Conference on Artificial Intelligence, Macao, China. Cited by: §5.1. [58] K. Zhao, X. Li, Q. Kang, F. Ji, Q. Ding, Y. Zhao, W. Liang, and W. P. Tay Distributed-order fractional graph operating network. In The Thirty-eighth Annual Conference on Neural Information Processing Systems, Cited by: §5.1. Zheng et al. (2023) Y. Zheng, H. Zhang, V. Lee, Y. Zheng, X. Wang, and S. Pan Finding the missing-half: graph complementary learning for homophily-prone and heterophily-prone graphs. In International Conference on Machine Learning, p. 42492–42505. Cited by: §1, §5.1. Zhou et al. (2020) K. Zhou, X. Huang, Y. Li, D. Zha, R. Chen, and X. Hu Towards deeper graph neural networks with differentiable group normalization. Advances in neural information processing systems 33, p. 4917–4928. Cited by: §1. Zhou et al. (2021) K. Zhou, Y. Dong, K. Wang, W. S. Lee, B. Hooi, H. Xu, and J. Feng Understanding and resolving performance degradation in deep graph convolutional networks. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, p. 2728–2737. Cited by: §1, §2. Zhu et al. (2020) J. Zhu, Y. Yan, L. Zhao, M. Heimann, L. Akoglu, and D. Koutra Beyond homophily in graph neural networks: current limitations and effective designs. Advances in neural information processing systems 33, p. 7793–7804. Cited by: §1. Zhuo et al. (2025) W. Zhuo, H. Yu, G. Tan, and X. Li Commute graph neural networks. In Proceedings of the 42nd International Conference on Machine Learning, PMLR, Vol. 267, p. 80612–80628. Cited by: §5.1.