Continuous-Time Quantum Walks based Graph Neural Network

# Continuous-Time Quantum Walks based Graph Neural Network
Source: [https://arxiv.org/html/2608.20738](https://arxiv.org/html/2608.20738)
## Continuous\-Time Quantum Walks based Graph Neural NetworkDOI:[XXXXXXX\.XXXXXXX](https://doi.org/XXXXXXX.XXXXXXX)Conference:Make sure to enter the correct conference title from your rights confirmation email; June 03–05, 2018; Woodstock, NYISBN:978\-1\-4503\-XXXX\-X/2018/06CCS:Computing methodologies Machine learning

,Zefeng Gaoemail:[zfgao@ruc\.com](mailto:[email protected])Affiliation:Renmin University of China,Beijing,China,Jian Liemail:[lijian2022@ruc\.edu\.cn](mailto:[email protected])Note:Corresponding author\.Affiliation:Renmin University of China,Beijing,China,Yang Liuemail:[Liuyang22@ucas\.ac\.cn](mailto:[email protected])Affiliation:Renmin University of China,Beijing,ChinaandHao sunemail:[haosun@ruc\.edu\.cn](mailto:[email protected])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 proposeCTQW\-GNN, a GNN built on Continuous\-Time Quantum Walks \(CTQW\)\. The design is motivated by two properties of the CTQW propagatore−i​H​te^\{\-\\mathrm\{i\}Ht\}\. \(i\) It is unitary and its eigenvalues lie on the unit circle, so no frequency component is damped\. This directly counters the low\-pass bias\. \(ii\) Unitarity preserves the feature norm, so the Dirichlet energy does not decay exponentially with depth\. This directly counters over\-smoothing\. Guided by these properties, CTQW\-GNN combines three aggregation modules, each motivated by a specific gap in prior work\.CTQW\-based Aggregationevolves 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 Aggregationbuilds 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 Aggregationis 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\-timett\. Experiments on1414benchmarks \(99heterophilic,55homophilic\) 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](https://arxiv.org/html/2608.20738#bib.bib3)\), traffic networks\([32](https://arxiv.org/html/2608.20738#bib.bib45)\)and recommendation systems\([42](https://arxiv.org/html/2608.20738#bib.bib1)\)\. This is primarily attributed to the capability of GNN to capture node features and graph topology information\. Despite these significant advancements\([14](https://arxiv.org/html/2608.20738#bib.bib2);[49](https://arxiv.org/html/2608.20738#bib.bib4)\), 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](https://arxiv.org/html/2608.20738#bib.bib5);[27](https://arxiv.org/html/2608.20738#bib.bib6)\), which preserves similarities and filters out differences among connected nodes, thereby promoting feature uniformity\([4](https://arxiv.org/html/2608.20738#bib.bib9)\)\. 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](https://arxiv.org/html/2608.20738#bib.bib10);[25](https://arxiv.org/html/2608.20738#bib.bib8)\)\. To improve GNN performance on heterophilic graphs, many researchers are attempting to construct high\-frequency filters to capture high\-frequency information\([4](https://arxiv.org/html/2608.20738#bib.bib9);[35](https://arxiv.org/html/2608.20738#bib.bib15)\)\. This approach is motivated by findings that high\-frequency information is useful for learning on heterophilic graph\([4](https://arxiv.org/html/2608.20738#bib.bib9)\)\. Another prevalent approach attempt involves aggregating multi\-hop neighbor nodes to capture long\-range homophilic dependencies\([59](https://arxiv.org/html/2608.20738#bib.bib13);[29](https://arxiv.org/html/2608.20738#bib.bib14)\)\.

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](https://arxiv.org/html/2608.20738#bib.bib17);[15](https://arxiv.org/html/2608.20738#bib.bib16)\)\. 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](https://arxiv.org/html/2608.20738#bib.bib19)\), normalization\([60](https://arxiv.org/html/2608.20738#bib.bib20);[61](https://arxiv.org/html/2608.20738#bib.bib21)\), and modifying the dynamical systems of GNNs\([45](https://arxiv.org/html/2608.20738#bib.bib22);[51](https://arxiv.org/html/2608.20738#bib.bib23)\)\. 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](https://arxiv.org/html/2608.20738#bib.bib18)\)\.

Heterophily and over\-smoothing are often studied as separate problems\([6](https://arxiv.org/html/2608.20738#bib.bib25);[10](https://arxiv.org/html/2608.20738#bib.bib26)\), but recent evidence suggests that they are closely related\([54](https://arxiv.org/html/2608.20738#bib.bib27)\)\. Recent works have found that methods addressing heterophily can also alleviate over\-smoothing\([7](https://arxiv.org/html/2608.20738#bib.bib11);[11](https://arxiv.org/html/2608.20738#bib.bib24)\), and vice versa\([45](https://arxiv.org/html/2608.20738#bib.bib22);[51](https://arxiv.org/html/2608.20738#bib.bib23)\)\. 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 proposeContinuous\-TimeQuantumWalks based onGraphNeuralNetwork, namelyCTQW\-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](https://arxiv.org/html/2608.20738#bib.bib28)\)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](https://arxiv.org/html/2608.20738#bib.bib30)\)\. Furthermore, mid\-frequency information has been shown to enhance GNN performance in such mixed\-pattern graphs\([35](https://arxiv.org/html/2608.20738#bib.bib15)\)\. 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](https://arxiv.org/html/2608.20738#bib.bib29)\)\. 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:

∙\\bulletCTQW\-inspired aggregations\.We design CTQW\-based and CTQW\-Attention aggregations that preserve quantum superposition and phase\-driven interference\.

∙\\bulletCTQW\-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 boundreff​\(t\)=2​λmax​t/πr\_\{\\mathrm\{eff\}\}\(t\)\\\!=\\\!2\\lambda\_\{\\max\}t/\\pithat together explain why CTQW avoids exponential energy decay and how to choosett\.

∙\\bulletExtensive 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](https://arxiv.org/html/2608.20738#bib.bib12);[29](https://arxiv.org/html/2608.20738#bib.bib14)\)\. 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](https://arxiv.org/html/2608.20738#bib.bib44);[49](https://arxiv.org/html/2608.20738#bib.bib4)\), since the high\-frequency information was helpful to address the heterophily problem\([4](https://arxiv.org/html/2608.20738#bib.bib9)\)\. The second type of methods expanded the neighborhood of nodes to aggregate distant homophilic information\([28](https://arxiv.org/html/2608.20738#bib.bib12);[29](https://arxiv.org/html/2608.20738#bib.bib14)\)\. 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](https://arxiv.org/html/2608.20738#bib.bib19)\), Normalization\([61](https://arxiv.org/html/2608.20738#bib.bib21)\), and modifying the dynamical systems of GNNs\([45](https://arxiv.org/html/2608.20738#bib.bib22)\)\. Despite notable progress, there is a trade\-off in existing methods that can limit GNN expressiveness\([44](https://arxiv.org/html/2608.20738#bib.bib18)\)\. 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𝒢=\(𝒱,ℰ\)\\mathcal\{G\}=\(\\mathcal\{V\},\\mathcal\{E\}\), with𝒱\\mathcal\{V\}as the node set of sizeNNandℰ\\mathcal\{E\}as the edge set\. The adjacency matrix isA∈ℝN×NA\\in\\mathbb\{R\}^\{N\\times N\}\. The degree matrixDDis diagonal withDi​i=∑jAi​jD\_\{ii\}=\\sum\_\{j\}\{A\_\{ij\}\}\. The normalized graph LaplacianL=I−D−12​A​D−12L=I\-D^\{\-\\frac\{1\}\{2\}\}AD^\{\-\\frac\{1\}\{2\}\}\(whereIIis the identity matrix\) is symmetric and expressed asU​Λ​UTU\\Lambda U^\{T\}\. Here,Λ=d​i​a​g​\(\[λ1,λ2,…,λN\]\)\\Lambda=diag\(\[\\lambda\_\{1\},\\lambda\_\{2\},\.\.\.,\\lambda\_\{N\}\]\)represents graph signal frequencies andU=\{ui\}i=1NU=\{\\\{u\_\{i\}\\\}\}\_\{i=1\}^\{N\}denotes the frequency components\.

#### Graph Fourier Transform

We treatUUas the base in graph Fourier transform\. The transform of a graph signalx∈ℝnx\\in\\mathbb\{R\}^\{n\}on𝒢\\mathcal\{G\}isx^=UT​x\\hat\{x\}=U^\{T\}x, and the inverse isx=U​x^x=U\\hat\{x\}\. The convolution of the graph signalxxwith the kernelffis:

\(1\)\(f∗x\)𝒢=U⁡\(\(UT​f\)⊙\(UT​x\)\)=U​gθ​UT​x\.\(f\*x\)\_\{\\mathcal\{G\}\}=U\(\(U^\{T\}f\)\\odot\(U^\{T\}x\)\)=Ug\_\{\\theta\}U^\{T\}x\.where⊙\\odotdenotes the hadamard product, andgθg\_\{\\theta\}is a learnable filter which can adjust the frequency response of the graph signal\.For example, GCN defines the convolutional kernelgθ=I−Λg\_\{\\theta\}=I\-\\Lambda, whereλgθ,i=1−λi\\lambda\_\{g\_\{\\theta\},i\}=1\-\\lambda\_\{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](https://arxiv.org/html/2608.20738#bib.bib18)\)\. TheDirichlet energyEEdefined on an undirected graph𝒢\\mathcal\{G\}with node featuresXXis :

\(2\)E⁡\(X\)=1N​∑i∈𝒱∑j∈𝒩i‖Xi−Xj‖22E\(X\)=\\frac\{1\}\{N\}\\sum\_\{i\\in\\mathcal\{V\}\}\{\\sum\_\{j\\in\\mathcal\{N\}\_\{i\}\}\\left\\\|X\_\{i\}\-X\_\{j\}\\right\\\|^\{2\}\_\{2\}\}With Dirichlet energy, we can define over\-smoothing like\([45](https://arxiv.org/html/2608.20738#bib.bib22)\)as following:

###### Definition 0\.

LetXnX^\{n\}denote the node feature at thenn\-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\)≤a​e−b​n,E\(X^\{n\}\)\\leq ae^\{\-bn\},whereaaandbbare constants anda,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 vectorp⁡\(t\)∈ℝ≥0Np\(t\)\\\!\\in\\\!\\mathbb\{R\}^\{N\}\_\{\\geq 0\}by the diffusion equationp˙=−L​p\\dot\{p\}=\-Lpwith solutionp⁡\(t\)=e−L​t​p​\(0\)p\(t\)=e^\{\-Lt\}p\(0\)\([9](https://arxiv.org/html/2608.20738#bib.bib31)\)\. A*quantum walk*\(QW\), introduced by[1](https://arxiv.org/html/2608.20738#bib.bib57)and surveyed by[22](https://arxiv.org/html/2608.20738#bib.bib56), replaces real probabilities with complex amplitudesψ⁡\(t\)∈ℂN\\psi\(t\)\\\!\\in\\\!\\mathbb\{C\}^\{N\}and the dissipative generator−L\-Lwith a Hermitian HamiltonianHH\. The walk evolves by the Schrödinger equationi​ψ˙=H​ψ\\mathrm\{i\}\\dot\{\\psi\}=H\\psi, whose solutionψ⁡\(t\)=e−i​H​t​ψ​\(0\)\\psi\(t\)=e^\{\-\\mathrm\{i\}Ht\}\\psi\(0\)is*unitary*: it preserves theℓ2\\ell\_\{2\}norm ofψ\\psirather than theℓ1\\ell\_\{1\}norm ofpp\. Its continuous\-time variant was developed by[13](https://arxiv.org/html/2608.20738#bib.bib32)\. Two intuitive advantages over CRW motivate our use: \(i\) eigenmodes acquire*different phases*e−i​λl​te^\{\-\\mathrm\{i\}\\lambda\_\{l\}t\}instead of different decay ratese−λl​te^\{\-\\lambda\_\{l\}t\}, so high\-frequency content is preserved \(Section[4\.2](https://arxiv.org/html/2608.20738#S4.SS2)\); and \(ii\) phase\-coherent superposition spreads the walker*ballistically*\(distance∝t\\propto t\) rather than*diffusively*\(distance∝t\\propto\\\!\\sqrt\{t\}\), yielding exponential separation in hitting time on certain graphs\([13](https://arxiv.org/html/2608.20738#bib.bib32);[8](https://arxiv.org/html/2608.20738#bib.bib48)\)\. We use QW purely as a unitary linear operator onℂN\\mathbb\{C\}^\{N\}, classically simulated \(Section[4](https://arxiv.org/html/2608.20738#S4)\); no quantum hardware is required\.

![Refer to caption](https://arxiv.org/html/2608.20738v1/main2.png)Figure 1\.The overview of CTQW\-GNN for heterophilic graphs and over\-smoothing problem\.\(a\)\.We define an undirected graph𝒢=\(𝒱,ℰ\)\\mathcal\{G\}=\(\\mathcal\{V\},\\mathcal\{E\}\), with𝒱\\mathcal\{V\}as the node set of sizeNNandℰ\\mathcal\{E\}as the edge set\.\(b\)\.We conduct a CTQW on the original graph𝒢\\mathcal\{G\}to obtain a new edge setℰC​T​Q​W\\mathcal\{E\}\_\{CTQW\}with edge weightsWℰC​T​Q​WW\_\{\\mathcal\{E\}\_\{CTQW\}\}; both connectivity relationsℰ\\mathcal\{E\}andℰC​T​Q​W\\mathcal\{E\}\_\{CTQW\}share the same node featuresX\(n\)X^\{\(n\)\}\.\(c\)\.We employ three distinct information aggregation methods proposed in this paper to derive three types of node information:XL​F\(n\)X^\{\(n\)\}\_\{LF\},XC​T​Q​W\(n\)X^\{\(n\)\}\_\{CTQW\}andXA​t​t​e​n​t​i​o​n\(n\)X^\{\(n\)\}\_\{Attention\}\. through the three types of features, we obtain the node featuresX\(n\+1\)X^\{\(n\+1\)\}for the next layer\. The details of the formula are provided in Section[4](https://arxiv.org/html/2608.20738#S4)\.
#### 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](https://arxiv.org/html/2608.20738#bib.bib55)\)\. We measure homophily at the graph and node level\.

###### Definition 0 \(Graph Homophily Ratio\)\.

LetC∈ℝ\|y\|×\|y\|C\\in\\mathbb\{R\}^\{\\left\|y\\right\|\\times\\left\|y\\right\|\}where\|y\|\\left\|y\\right\|is the number of node categories andCi​j=\|\{\(u,v\):\(u,v\)∈ℰ∧yu=i∧yv=j\}\|C\_\{ij\}=\|\\\{\(u,v\):\(u,v\)\\in\\mathcal\{E\}\\wedge y\_\{u\}=i\\wedge y\_\{v\}=j\\\}\|\. The Graph Homophily Ratio is

\(4\)h=∑iN∑ji==jCi​j∑iN∑ji≠jCi​j\.h=\\frac\{\\sum\_\{i\}^\{N\}\\sum\_\{j\}^\{i==j\}\{C\_\{ij\}\}\}\{\\sum\_\{i\}^\{N\}\\sum\_\{j\}^\{i\\neq j\}\{C\_\{ij\}\}\}\.

Homophilic graphs have a highhh; heterophilic graphs have a lowhh\. The node\-level analogue measures the local pattern around each node:

###### Definition 0 \(Node Homophily Ratio\)\.

Lety∈ℝNy\\in\\mathbb\{R\}^\{N\}be the node labels and𝒩⁡\(vi\)\\mathcal\{N\}\(v\_\{i\}\)the neighborhood ofviv\_\{i\}with degreedvid\_\{v\_\{i\}\}\. The Node Homophily Ratio is

\(5\)hvi=\|\{u∈𝒩⁡\(vi\):yu=yvi\}\|dvi\.h\_\{v\_\{i\}\}=\\frac\{\\left\|\\\{u\\in\\mathcal\{N\}\(v\_\{i\}\):y\_\{u\}=y\_\{v\_\{i\}\}\\\}\\right\|\}\{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 Aggregationcan 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 asCTQW\-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 termedLow\-FrequencyAggregation\(LF Aggregation\)\. An overview of our approach is depicted in Figure[1](https://arxiv.org/html/2608.20738#S3.F1)\. The three aggregators address distinct failure modes of message passing\. \(1\)*Over\-smoothing*: dampinge−λl​te^\{\-\\lambda\_\{l\}t\}is replaced by the unitary multipliere−i​λl​te^\{\-\\mathrm\{i\}\\lambda\_\{l\}t\}on the unit circle, so the Dirichlet energy of theXC​T​Q​WX\_\{CTQW\}branch is layer\-invariant \(Prop\.[2](https://arxiv.org/html/2608.20738#S4.Thmtheorem2), Lemma[2](https://arxiv.org/html/2608.20738#Thmlemmaapp2)\)\. \(2\)*Heterophily*: the same eigenmode preservation gives CTQW\-based Aggregation an all\-pass filter, while theϵ\\epsilon\-thresholded\|e−i​H​t\|\|e^\{\-\\mathrm\{i\}Ht\}\|exposes a Lieb–Robinson\-bounded long\-range graph𝒢C​T​Q​W\\mathcal\{G\}\_\{CTQW\}of radiusreff​\(t\)r\_\{\\mathrm\{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](https://arxiv.org/html/2608.20738#S4.E12)\) ensures one branch’s failure cannot collapse the representation \(Prop\.[1](https://arxiv.org/html/2608.20738#S4.Thmtheorem1)\)\.

### 4\.2\.CTQW\-based Aggregation

Continuous Time Quantum Walks\.The CTQW on graph𝒢\\mathcal\{G\}represents the evolution of node states in anNN\-dimensional Hilbert space with orthonormal basis\|a⟩\{\\ket\{a\}\}wherea=1,2,3,…,Na=1,2,3,\.\.\.,Nand⟨a\|b⟩=δa​b\\braket\{a\|b\}=\\delta\_\{ab\}, withδa​b=1\\delta\_\{ab\}=1if and only ifa=ba=b, and00otherwise\. Node states\|ψ⁡\(t\)⟩\\ket\{\\psi\(t\)\}at timettevolve according to the Schrödinger equation:

\(6\)i​ℏ​dd​t​\|ψ⁡\(t\)⟩=H​\|ψ⁡\(t\)⟩,\\mathrm\{i\}\\hbar\\frac\{d\}\{dt\}\\ket\{\\psi\(t\)\}=H\\ket\{\\psi\(t\)\},whereHHis the Hamiltonian matrix of the CTQW system andi\\mathrm\{i\}is the imaginary unit, which is different from the previous equationii\.ℏ\\hbaris Planck’s constant, which is commonly considered to be 1\. The state of nodes evolves from the initial state\|ψ⁡\(0\)⟩\\ket\{\\psi\(0\)\}as:

\(7\)\|ψ⁡\(t\)⟩=e−i​H​t​\|ψ⁡\(0\)⟩,\\ket\{\\psi\(t\)\}=e^\{\-\\mathrm\{i\}Ht\}\\ket\{\\psi\(0\)\},Previous works show that a finite graph is given where classical and quantum walks give an exponential separation in expected hitting time\([13](https://arxiv.org/html/2608.20738#bib.bib32);[8](https://arxiv.org/html/2608.20738#bib.bib48)\)\. Continuous\-Time Random Walk \(CTRW,*i\.e\.,*x⁡\(t\)=e−L​t​x​\(0\)x\(t\)=e^\{\-Lt\}x\(0\), whereLLdenotes the graph Laplacian matrix\.\) is a diffusion process and serves as the primary information propagation mechanism in most existing homophilic GNN\.

Figure[2](https://arxiv.org/html/2608.20738#S4.F2)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](https://arxiv.org/html/2608.20738#S4.E7)\. 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\)XC​T​Q​W\(n\)=f⁡\(e−i​H​t​X\(n\)\),X\_\{CTQW\}^\{\(n\)\}=f\(e^\{\-\\mathrm\{i\}Ht\}X^\{\(n\)\}\),whereX\(n\)X^\{\(n\)\}andXC​T​Q​W\(n\)X\_\{CTQW\}^\{\(n\)\}are the feature of nodes at thenn\-th layer of the GNN and the output ofnn\-th layer of CTQW\-based Aggregation, respectively\. Thettine−i​H​te^\{\-\\mathrm\{i\}Ht\}is a hyperparameter that influences the range of neighbors obtained through the quantum walk\. The functionf⁡\(⋅\)f\(\\cdot\)concatenates the imaginary and real parts of the input\.

Choice of HamiltonianHH\.Either the adjacency matrixAAor the normalised LaplacianL=I−D−1/2AD−1/2L=I\-D^\{\-1/2\}AD^\{\-1/2\}is a valid Hermitian Hamiltonian, related by an eigenvalue translation \(λlL=1−λlA/d\\lambda^\{L\}\_\{l\}=1\-\\lambda^\{A\}\_\{l\}/dondd\-regular graphs\), so they generate the same family of unitaries up to a global phase\. We useAAby default for three reasons: \(i\)AAhas the lowest constant innnz\\mathrm\{nnz\}, minimising every Krylov mat\-vec; \(ii\) the trivial mode ofLLis the constant “smoothing” directionλ=0\\lambda\\\!=\\\!0, which we wish to avoid privileging; \(iii\)AAmatches the tight\-binding Hamiltonian in solid\-state physics\([5](https://arxiv.org/html/2608.20738#bib.bib33)\)\.

Practical Simulation ofe−i​H​t​X\(n\)e^\{\-\\mathrm\{i\}Ht\}X^\{\(n\)\}\.A natural concern is whether the quantum state\|ψ⁡\(0\)⟩\\ket\{\\psi\(0\)\}in Eq\.[7](https://arxiv.org/html/2608.20738#S4.E7)entails a2N2^\{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 theNN\-dimensional vertex spaceℂN\\mathbb\{C\}^\{N\}\(one amplitude per node\), not in the2N2^\{N\}Fock space ofNNqubits\. Hencee−i​H​te^\{\-\\mathrm\{i\}Ht\}is anN×NN\\\!\\times\\\!Nunitary that we simulate classically with no quantum hardware\. We never materialise the dense matrix; for each feature columnX\(n\):,k∈ℝNX^\{\(n\)\}\_\{:,k\}\\\!\\in\\\!\\mathbb\{R\}^\{N\}we applye−i​H​te^\{\-\\mathrm\{i\}Ht\}via akiter≤20k\_\{\\text\{iter\}\}\\\!\\leq\\\!20\-step Lanczos Krylov\-subspace approximation\([24](https://arxiv.org/html/2608.20738#bib.bib53);[2](https://arxiv.org/html/2608.20738#bib.bib59);[38](https://arxiv.org/html/2608.20738#bib.bib58)\): \(1\) build a Krylov basisVkiterV\_\{k\_\{\\text\{iter\}\}\}ofHHfromX\(n\):,kX^\{\(n\)\}\_\{:,k\}by Lanczos; \(2\) form thekiter×kiterk\_\{\\text\{iter\}\}\\\!\\times\\\!k\_\{\\text\{iter\}\}projectionT=V†​H​VT\\\!=\\\!V^\{\\dagger\}HV; \(3\) compute the small dense exponentiale−i​T​te^\{\-\\mathrm\{i\}Tt\}; \(4\) returnVe−i​T​tV†X\(n\):,kVe^\{\-\\mathrm\{i\}Tt\}V^\{\\dagger\}X^\{\(n\)\}\_\{:,k\}\. Total cost is𝒪⁡\(kiter⋅nnz⁡\(H\)⋅d\)\\mathcal\{O\}\(k\_\{\\text\{iter\}\}\\\!\\cdot\\\!\\mathrm\{nnz\}\(H\)\\\!\\cdot\\\!d\)per layer, and Appendix[A\.5](https://arxiv.org/html/2608.20738#A1.SS5)gives an exponential error bound that makes the approximation indistinguishable from the exact unitary atkiter=20k\_\{\\text\{iter\}\}\\\!=\\\!20\. The “initial state”ψ⁡\(0\)\\psi\(0\)is simply the GNN feature column; after evolution we keep both real and imaginary parts viaf⁡\(⋅\)f\(\\cdot\)\.

Performing the spectral decomposition ofHHyields:

\(9\)H=U​Λ​U†,H=U\\Lambda U^\{\\dagger\},where,UUis the matrix formed by the eigenvectors ofHHandΛ\\Lambdais 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](https://arxiv.org/html/2608.20738#bib.bib34);[28](https://arxiv.org/html/2608.20738#bib.bib12)\)\. 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](https://arxiv.org/html/2608.20738#bib.bib30)\)\. 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](https://arxiv.org/html/2608.20738#bib.bib15)\)\.

According to Eq\.[1](https://arxiv.org/html/2608.20738#S3.E1)and Eq\.[9](https://arxiv.org/html/2608.20738#S4.E9), We can found that CTQW\-based Aggregation defines the convolutional kernegθ=e−i​Λ​tg\_\{\\theta\}=e^\{\-\\mathrm\{i\}\\Lambda t\}, where\|λgθ\|=\|e−i​Λ​t\|=1\\left\|\\lambda\_\{g\_\{\\theta\}\}\\right\|=\\left\|e^\{\-\\mathrm\{i\}\\Lambda t\}\\right\|=1on every eigenmode \(Appendix[A\.6](https://arxiv.org/html/2608.20738#A1.SS6), Proposition[3](https://arxiv.org/html/2608.20738#A1.Thmtheorem3)\)\. 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](https://arxiv.org/html/2608.20738#S4.SS4)\)\.

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 columnX\(n\):,k=∑lαl,kulX^\{\(n\)\}\_\{:,k\}\\\!=\\\!\\sum\_\{l\}\\alpha\_\{l,k\}u\_\{l\}is a coherent linear combination over the eigenbasis\{ul\}\\\{u\_\{l\}\\\}ofHH, and the unitary propagatore−i​H​t=∑le−i​λl​t​ul​ul†e^\{\-\\mathrm\{i\}Ht\}=\\sum\_\{l\}e^\{\-\\mathrm\{i\}\\lambda\_\{l\}t\}u\_\{l\}u\_\{l\}^\{\\dagger\}rotates*all*eigenmodes by data\-dependent phases while preserving their magnitudes\|αl,k\|\|\\alpha\_\{l,k\}\|\. This realises \(i\)*superposition*—features evolve as coherent combinations of eigenmodes—and \(ii\)*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\)](https://arxiv.org/html/2608.20738#S4.F2.sf1)\)\. The operatorf⁡\(⋅\)f\(\\cdot\)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\. Let0=μ1≤⋯≤μN0=\\mu\_\{1\}\\leq\\cdots\\leq\\mu\_\{N\}be the eigenvalues ofLLand denote byΔ:=μ2\\Delta:=\\mu\_\{2\}its spectral gap\. Classical diffusione−L​te^\{\-Lt\}damps thell\-th eigenmode bye−μl​te^\{\-\\mu\_\{l\}t\}, so every non\-trivial mode decays at rate≥e−Δ​t\\geq e^\{\-\\Delta t\}and embeddings collapse onto the leading eigenvector—the origin of over\-smoothing\. CTQW propagatione−i​L​te^\{\-\\mathrm\{i\}Lt\}instead has eigen\-multiplierse−i​μl​te^\{\-\\mathrm\{i\}\\mu\_\{l\}t\}on the unit circle:*no*mode is attenuated regardless ofΔ\\Delta, mathematically guaranteeing that high\- and mid\-frequency content is preserved across layers\. The gap instead governs the*interference pattern*: largerΔ\\Deltadesynchronises the leading modes’ phases faster, yielding the sharp ballistic peaks of Figure[2\(a\)](https://arxiv.org/html/2608.20738#S4.F2.sf1)\.

Walk\-Time Hyperparametertt\.The time parameterttrescales each spectral phaseλl​\(H\)​t\\lambda\_\{l\}\(H\)t; withλmax=‖H‖2\\lambda\_\{\\max\}=\\\|H\\\|\_\{2\}and the above gapΔ\\Delta, this leads to three regimes\. Whent≪1/λmaxt\\\!\\ll\\\!1/\\lambda\_\{\\max\},e−i​H​t≈I−i​H​te^\{\-\\mathrm\{i\}Ht\}\\\!\\approx\\\!I\-\\mathrm\{i\}Ht, so propagation remains local\. Whent∼π/Δt\\\!\\sim\\\!\\pi/\\Delta, the leading modes accumulate an approximatelyπ\\piphase difference, producing long range ballistic peaks that are useful for heterophilic graphs\. Whent≫π/Δt\\\!\\gg\\\!\\pi/\\Delta, the phases become densely mixed and the walk approaches its long time average\. This analysis suggests a practical initialization range,t∈\[π/\(4​λmax\),π/Δ\]t\\\!\\in\\\!\[\\pi/\(4\\lambda\_\{\\max\}\),\\pi/\\Delta\], which we use across all datasets and validate in Section[5\.3](https://arxiv.org/html/2608.20738#S5.SS3)\.

### 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𝒢\\mathcal\{G\}\. The adjacency of the new graph𝒢C​T​Q​W\\mathcal\{G\}\_\{CTQW\}thresholds the CTQW amplitudes:

\(10\)Ai​j=\{1\|ei​j−i​H​t\|≥ϵ,0otherwise,A\_\{ij\}=\\begin\{cases\}1&\\left\|e^\{\-\\mathrm\{i\}Ht\}\_\{ij\}\\right\|\\geq\\epsilon,\\\\ 0&\\text\{otherwise\},\\end\{cases\}*Selectingϵ\\epsilon\.*We useϵ=×10−3\\epsilon\\\!=\\\!5\\\!\\times\\\!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ϵ\\epsilonsuch thatd¯​\(𝒢C​T​Q​W\)≤20​d¯​\(𝒢\)\\bar\{d\}\(\\mathcal\{G\}\_\{CTQW\}\)\\\!\\leq\\\!20\\bar\{d\}\(\\mathcal\{G\}\)\. The Lieb–Robinson bound \(Appendix[A\.4](https://arxiv.org/html/2608.20738#A1.SS4)\) ensures that anyϵ∈\[10−3,10−2\]\\epsilon\\\!\\in\\\!\[10^\{\-3\},10^\{\-2\}\]filters the same structurally meaningful edges \(accuracy varies<0\.7%<\\\!0\.7\\%across this range, Section[5\.3](https://arxiv.org/html/2608.20738#S5.SS3)\)\.

Attention from Graph Transformer aggregates information over𝒢C​T​Q​W\\mathcal\{G\}\_\{CTQW\}only:

\(11\)XA​t​t​e​n​t​i​o​n\(n\)=∑j∈𝒩ie​x​p​\(qiT​kj\)∑u∈𝒩ie​x​p​\(qiT​ku\)​vj,X\_\{Attention\}^\{\(n\)\}=\\sum\_\{j\\in\\mathcal\{N\}\_\{i\}\}\{\\frac\{exp\(q^\{T\}\_\{i\}k\_\{j\}\)\}\{\\sum\_\{u\\in\\mathcal\{N\}\_\{i\}\}\{exp\(q^\{T\}\_\{i\}k\_\{u\}\)\}\}v\_\{j\}\},where𝒩i\\mathcal\{N\}\_\{i\}is the set of neighbor nodes for nodeiiin the graph𝒢C​T​Q​W\\mathcal\{G\}\_\{CTQW\}\. The terms Query \(qiq\_\{i\}\), key \(kik\_\{i\}\) and value \(viv\_\{i\}\) respectively denote the outcomes derived for the feature of nodeiiXi\(n\)X^\{\(n\)\}\_\{i\}innn\-th layer of GNN after processing through a Multilayer Perceptron\.XA​t​t​e​n​t​i​o​n\(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𝒢C​T​Q​W\\mathcal\{G\}\_\{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 thenn\-th layer LF Aggregation asXL​F\(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𝒢C​T​Q​W\\mathcal\{G\}\_\{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𝒢\\mathcal\{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](https://arxiv.org/html/2608.20738#bib.bib35)\)\. 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\)=σ⁡\(\[XL​F\(n\)​‖XC​T​Q​W\(n\)‖​XA​t​t​e​n​t​i​o​n\(n\)\]​Wθ\)X^\{\(n\+1\)\}=\\sigma\\left\(\\left\[X^\{\(n\)\}\_\{LF\}\|\|X^\{\(n\)\}\_\{CTQW\}\|\|X^\{\(n\)\}\_\{Attention\}\\right\]W\_\{\\theta\}\\right\)where\|⁣\|\|\|means the concatenation along the feature dimension,WθW\_\{\\theta\}is a learnable weight matrix\.σ\\sigmais a nonlinear activation function\. Based on Definition[1](https://arxiv.org/html/2608.20738#S3.Thmtheorem1), we first obtain a branch\-wise criterion \(proved in Appendix[A\.1](https://arxiv.org/html/2608.20738#A1.SS1)\):

###### Proposition 0 \(Branch\-wise over\-smoothing criterion\)\.

LetY\(n\)=\[XL​F\(n\)​‖XC​T​Q​W\(n\)‖​XA​t​t​e​n​t​i​o​n\(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 featureX\(n\+1\)X^\{\(n\+1\)\}, the same conclusion holds under the non\-degenerate mixer condition in Appendix[A\.7](https://arxiv.org/html/2608.20738#A1.SS7); in particular, any branch with non\-decaying energy prevents over\-smoothing wheneverWθW\_\{\\theta\}does not annihilate that branch\.

In other words, the concatenated representation can collapse only whenXC​T​Q​W\(n\)X^\{\(n\)\}\_\{CTQW\},XA​t​t​e​n​t​i​o​n\(n\)X^\{\(n\)\}\_\{Attention\}andXL​F\(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](https://arxiv.org/html/2608.20738#A1.SS2)\):

###### Proposition 0 \(Non\-decay of the CTQW branch\)\.

IfHHcommutes with the Laplacian used in Dirichlet energy \(e\.g\.,H=LH=L, orH=AH=Aon regular graphs\),E⁡\(XC​T​Q​W\(n\)\)E\(X^\{\(n\)\}\_\{CTQW\}\)is invariant across layers\. With the default sparse\-adjacency HamiltonianH=AH=A,E⁡\(XC​T​Q​W\(n\)\)E\(X^\{\(n\)\}\_\{CTQW\}\)has a positive Cesàro lower bound under the mild non\-resonance condition stated in Appendix[A\.2](https://arxiv.org/html/2608.20738#A1.SS2); 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 \(α\\alpha\) for each dataset is highlight in bold and the second best \(β\\beta\) underlined, where Promotion is defined between these two values, i\.e\.,\(α−β\)/β×100%\(\\alpha\-\\beta\)/\\beta\\times 100\\%\.Table 2\.Results of node classification tasks on different homophilic datasets: mean ± std \(%\)\.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](https://arxiv.org/html/2608.20738#bib.bib51)\), Citeseer\([46](https://arxiv.org/html/2608.20738#bib.bib52)\), PubMed\([39](https://arxiv.org/html/2608.20738#bib.bib37)\), Computers, Photo\([39](https://arxiv.org/html/2608.20738#bib.bib37)\)\) and nine heterophilic datasets: the classical four \(Chameleon, Squirrel, Actor, Texas\)\([40](https://arxiv.org/html/2608.20738#bib.bib7)\)and the five new datasets of[41](https://arxiv.org/html/2608.20738#bib.bib36)\(Roman\-empire, Amazon\-ratings, Minesweeper, Tolokers, Wiki\-cooc\)\. Splits follow\([59](https://arxiv.org/html/2608.20738#bib.bib13)\)for homophilic data,\([54](https://arxiv.org/html/2608.20738#bib.bib27)\)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](https://arxiv.org/html/2608.20738#bib.bib38)\); classical GNNs \(GCN\([23](https://arxiv.org/html/2608.20738#bib.bib39)\), GAT\([50](https://arxiv.org/html/2608.20738#bib.bib40)\), SAGE\([17](https://arxiv.org/html/2608.20738#bib.bib41)\)\); heterophily\-specific \(CDE\-GRAND\([57](https://arxiv.org/html/2608.20738#bib.bib42)\), GloGNN\([28](https://arxiv.org/html/2608.20738#bib.bib12)\), EG\-GCN\([33](https://arxiv.org/html/2608.20738#bib.bib50)\), PCNet\([25](https://arxiv.org/html/2608.20738#bib.bib8)\)\); both\-problem\-aware \(GPR\-GNN\([7](https://arxiv.org/html/2608.20738#bib.bib11)\), FSGNN\([36](https://arxiv.org/html/2608.20738#bib.bib43)\), ACMP\-GCN\([51](https://arxiv.org/html/2608.20738#bib.bib23)\), FLODE\([35](https://arxiv.org/html/2608.20738#bib.bib15)\), F\-GRAND\([21](https://arxiv.org/html/2608.20738#bib.bib46)\), D\-CDE\([58](https://arxiv.org/html/2608.20738#bib.bib47)\), UniFilter\([20](https://arxiv.org/html/2608.20738#bib.bib49)\), CGNN\([63](https://arxiv.org/html/2608.20738#bib.bib63)\), AMP\([12](https://arxiv.org/html/2608.20738#bib.bib62)\), and HeroFilter\([56](https://arxiv.org/html/2608.20738#bib.bib61)\)\)\. CTQW\-GNN uses the adjacency matrix asHHand 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](https://arxiv.org/html/2608.20738#S5.T1), while the results on homophilic graphs are reported in Table[2](https://arxiv.org/html/2608.20738#S5.T2)\.

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\.

![Refer to caption](https://arxiv.org/html/2608.20738v1/DE_ACC_radar.png)Figure 4\.\(a\)\.Dirichlet energy of graph\. Left: Minesweeper results; Right: Amazon\-ratings results\.\(b\.\)Accuracy of CTQW\-GNN\. Figureaandbare the performance of GNN models with different depth\. In Figureb, 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](https://arxiv.org/html/2608.20738#bib.bib36)\), 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](https://arxiv.org/html/2608.20738#S4.SS4)\) 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](https://arxiv.org/html/2608.20738#bib.bib30)\)\. 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](https://arxiv.org/html/2608.20738#S5.F3)\.

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[4](https://arxiv.org/html/2608.20738#S5.F4)a\)\.

Figure[4](https://arxiv.org/html/2608.20738#S5.F4)a 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 StudyOur 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[4](https://arxiv.org/html/2608.20738#S5.F4)c\.

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[4](https://arxiv.org/html/2608.20738#S5.F4)a illustrates, removing CTQW\-based aggregation also reintroduces over\-smoothing\.

Sensitivity to Walk Timett\.Walk timettcontrols the propagation range of the CTQW branch\. We evaluate its influence by sweeping nine values from10−610^\{\-6\}to10210^\{2\}on four representative datasets, as shown in Table[3](https://arxiv.org/html/2608.20738#S5.T3)\. Whenttis extremely small \(10−610^\{\-6\}–10−410^\{\-4\}\), the CTQW propagation is weak and the performance is relatively low\. Asttincreases 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 within1%1\\%of their best scores across this range, while Cora also keeps a stable plateau from10−210^\{\-2\}to11\. The results indicate that CTQW\-GNN is not sensitive to a precise choice oftt\. The best performance does not appear at a single isolated value; instead, each dataset has a broad stable region where differentttvalues lead to very similar accuracy\. Performance only drops clearly whenttis 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 timett\.Sensitivity to the Sparsification Thresholdϵ\\epsilon\.The thresholdϵ\\epsiloncontrols how many CTQW edges are kept: a smallerϵ\\epsilonkeeps more long\-range connections, while a largerϵ\\epsilonprunes more connections\. We test five values ofϵ\\epsilonon four representative datasets, and the results are shown in Table[4](https://arxiv.org/html/2608.20738#S5.T4)\.

Overall, CTQW\-GNN is robust toϵ\\epsilon\. Whenϵ\\epsilonchanges from10−410^\{\-4\}to10−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ϵ\\epsilonis too small, many weak CTQW connections are retained, which brings more computation but gives little or no accuracy improvement\. Whenϵ\\epsilonis too large, too many useful long\-range connections are removed, and the performance drops clearly\. Therefore, a moderate threshold such as×10−35\\\!\\times\\\!10^\{\-3\}provides a good balance between performance and sparsity\.

Table 4\.Effect of sparsification thresholdϵ\\epsilon\.
### 5\.4\.Time Complexity Analysis

Althoughe−i​H​te^\{\-\\mathrm\{i\}Ht\}appears dense, CTQW\-GNN never forms this operator explicitly\. The graph𝒢C​T​Q​W\\mathcal\{G\}\_\{CTQW\}is built once via a sparse degree\-KKChebyshev expansion \(K=20K\\\!=\\\!20\) at cost𝒪⁡\(K​\|ℰ\|\)\\mathcal\{O\}\(K\|\\mathcal\{E\}\|\), amortised over all epochs\. Per layer, the CTQW branch appliese−i​H​t​X\(n\)e^\{\-\\mathrm\{i\}Ht\}X^\{\(n\)\}via akk\-step Krylov projection \(k=20k\\\!=\\\!20\) at𝒪⁡\(k​\|ℰ\|​d\)\\mathcal\{O\}\(k\|\\mathcal\{E\}\|d\); the LF and CTQW\-Attention branches each cost𝒪⁡\(\|ℰ\|​d\+N​d2\)\\mathcal\{O\}\(\|\\mathcal\{E\}\|d\+Nd^\{2\}\), the same as GCN\([23](https://arxiv.org/html/2608.20738#bib.bib39)\)and GAT\([50](https://arxiv.org/html/2608.20738#bib.bib40)\)\. Since the sparsification rule \(Section[5\.3](https://arxiv.org/html/2608.20738#S5.SS3)\) keeps\|ℰC​T​Q​W\|=𝒪⁡\(\|ℰ\|\)\|\\mathcal\{E\}\_\{CTQW\}\|\\\!=\\\!\\mathcal\{O\}\(\|\\mathcal\{E\}\|\), the total per\-layer cost is𝒪⁡\(\(k\+1\)​\|ℰ\|​d\+N​d2\)\\mathcal\{O\}\\\!\\big\(\(k\{\+\}1\)\|\\mathcal\{E\}\|d\+Nd^\{2\}\\big\)—linear in\|ℰ\|\|\\mathcal\{E\}\|and matching GCN/GAT up to a small constant factork\+≤21k\{\+\}1\\\!\\leq\\\!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](https://arxiv.org/html/2608.20738#S4.Thmtheorem2), Lemma[2](https://arxiv.org/html/2608.20738#Thmlemmaapp2)\); 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 AProof

#### Notation\.

𝒢=\(𝒱,ℰ\)\\mathcal\{G\}=\(\\mathcal\{V\},\\mathcal\{E\}\),N=\|𝒱\|N\\\!=\\\!\|\\mathcal\{V\}\|,L=I−D−1/2AD−1/2L\\\!=\\\!I\\\!\-\\\!D^\{\-1/2\}AD^\{\-1/2\}\. The HamiltonianHHis Hermitian \(defaultH=AH\\\!=\\\!A\)\.L=V​ΛL​V†L\\\!=\\\!V\\Lambda\_\{L\}V^\{\\\!\\dagger\}with eigenvalues=μ1≤μ2≤⋯≤μN0\\\!=\\\!\\mu\_\{1\}\\\!\\leq\\\!\\mu\_\{2\}\\\!\\leq\\\!\\cdots\\\!\\leq\\\!\\mu\_\{N\}and gapΔ:=μ2\\Delta\\\!:=\\\!\\mu\_\{2\}\. LetP⟂=I−v1​v1†P\_\{\\perp\}\\\!=\\\!I\-v\_\{1\}v\_\{1\}^\{\\dagger\}be the projection onto the non\-constant Laplacian subspace\. ForX∈ℂN×dX\\\!\\in\\\!\\mathbb\{C\}^\{N\\times d\}define spectral coordinatesX~:=V†​X\\tilde\{X\}\\\!:=\\\!V^\{\\\!\\dagger\}X\(rows indexed by modeℓ\\ell\)\. The matrix\-form Dirichlet energy

\(S\.1\)E⁡\(X\)=tr⁡\(X†​L​X\)=∑ℓ=1Nμℓ​‖X~ℓ‖22E\(X\)\\;=\\;\\mathrm\{tr\}\(X^\{\\\!\\dagger\}LX\)\\;=\\;\\sum\_\{\\ell=1\}^\{N\}\\mu\_\{\\ell\}\\,\\\|\\tilde\{X\}\_\{\\ell\}\\\|\_\{2\}^\{2\}agrees with Eq\.[2](https://arxiv.org/html/2608.20738#S3.E2)up to a constant fixed by𝒢\\mathcal\{G\}\([9](https://arxiv.org/html/2608.20738#bib.bib31)\)\. Standing assumptions \(verified on every benchmark\):\(A1\)Δ\>0\\Delta\\\!\>\\\!0;\(A2\)‖P⟂​X\(0\)‖F\>0\\\|P\_\{\\perp\}X^\{\(0\)\}\\\|\_\{F\}\\\!\>\\\!0\. For the defaultH=AH\\\!=\\\!Awe 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−i​n​H​t​X\(0\)‖F2\>0\\liminf\_\{T\\to\\infty\}T^\{\-1\}\\sum\_\{n<T\}\\\|P\_\{\\perp\}e^\{\-\\mathrm\{i\}nHt\}X^\{\(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[4](https://arxiv.org/html/2608.20738#S5.F4)a\.

### A\.1\.Proof of Proposition[1](https://arxiv.org/html/2608.20738#S4.Thmtheorem1)

###### Proof\.

LetY\(n\)=\[XL​F\(n\)​‖XC​T​Q​W\(n\)‖​XA​t​t\(n\)\]∈ℂN×3​dY^\{\(n\)\}\\\!=\\\!\[X^\{\(n\)\}\_\{LF\}\\\!\\,\\\|\\,\\\!X^\{\(n\)\}\_\{CTQW\}\\\!\\,\\\|\\,\\\!X^\{\(n\)\}\_\{Att\}\]\\\!\\in\\\!\\mathbb\{C\}^\{N\\times 3d\}be the pre\-mixing concatenation\. By Eq\.[S\.1](https://arxiv.org/html/2608.20738#A1.E1)and the column\-block structure ofY\(n\)Y^\{\(n\)\},

\(S\.2\)E\(Y\(n\)\)=tr\(Y\(n\)†LY\(n\)\)=EL​F\(n\)\+EC​T​Q​W\(n\)\+EA​t​t\(n\),E\(Y^\{\(n\)\}\)=\\mathrm\{tr\}\(Y^\{\(n\)\\dagger\}LY^\{\(n\)\}\)=E\_\{LF\}^\{\(n\)\}\+E\_\{CTQW\}^\{\(n\)\}\+E\_\{Att\}^\{\(n\)\},sincetr\(\[P∥Q\]†L\[P∥Q\]\)=tr\(P†LP\)\+tr\(Q†LQ\)\\mathrm\{tr\}\(\[P\\,\\\|\\,Q\]^\{\\dagger\}L\[P\\,\\\|\\,Q\]\)=\\mathrm\{tr\}\(P^\{\\\!\\dagger\}LP\)\+\\mathrm\{tr\}\(Q^\{\\\!\\dagger\}LQ\)for any pair of matricesP,QP,Q\. Because all three terms are non\-negative,E⁡\(Y\(n\)\)≤a​e−b​nE\(Y^\{\(n\)\}\)\\leq ae^\{\-bn\}holds iff each branch energy is bounded by an exponential envelope \(with rate at leastbbin 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 featuresX\(n\+1\)=σ⁡\(Y\(n\)​Wθ\)X^\{\(n\+1\)\}\\\!=\\\!\\sigma\(Y^\{\(n\)\}W\_\{\\theta\}\), Lemma[1](https://arxiv.org/html/2608.20738#Thmlemmaapp1)gives the always\-valid upper bound, and Lemma[3](https://arxiv.org/html/2608.20738#Thmlemmaapp3)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](https://arxiv.org/html/2608.20738#S4.Thmtheorem1)\. ∎

###### Lemma 1\.

LetY∈ℂN×mY\\\!\\in\\\!\\mathbb\{C\}^\{N\\times m\},W∈ℝm×dW\\\!\\in\\\!\\mathbb\{R\}^\{m\\times d\}, andσ\\sigmabe entrywiseρ\+\\rho\_\{\+\}\-Lipschitz withσ⁡\(0\)=0\\sigma\(0\)\\\!=\\\!0\. ThenE⁡\(σ⁡\(Y​W\)\)≤ρ\+2​‖W‖22​E​\(Y\)E\(\\sigma\(YW\)\)\\\!\\leq\\\!\\rho\_\{\+\}^\{2\}\\\|W\\\|\_\{2\}^\{2\}E\(Y\)\. If, on the subspace spanned by layer\-wise edge differences, the mapz↦σ⁡\(z​W\)z\\mapsto\\sigma\(zW\)has gain at leastρ−\>0\\rho\_\{\-\}\>0, thenE⁡\(σ⁡\(Y​W\)\)≥ρ−2​E​\(Y\)E\(\\sigma\(YW\)\)\\\!\\geq\\\!\\rho\_\{\-\}^\{2\}E\(Y\)on that subspace\.

###### Proof\.

WriteE⁡\(Z\)=∑\(i,j\)∈ℰ‖zi/di−zj/dj‖22E\(Z\)=\\sum\_\{\(i,j\)\\in\\mathcal\{E\}\}\\\|z\_\{i\}/\\\!\\sqrt\{d\_\{i\}\}\-z\_\{j\}/\\\!\\sqrt\{d\_\{j\}\}\\\|\_\{2\}^\{2\}\. For each edge term, entrywise Lipschitzness gives‖σ⁡\(u\)−σ⁡\(v\)‖2≤ρ\+​‖u−v‖2\\\|\\sigma\(u\)\\\!\-\\\!\\sigma\(v\)\\\|\_\{2\}\\\!\\leq\\\!\\rho\_\{\+\}\\\|u\\\!\-\\\!v\\\|\_\{2\}, and‖\(u−v\)⊤​W‖2≤‖W‖2​‖u−v‖2\\\|\(u\-v\)^\{\\top\}W\\\|\_\{2\}\\\!\\leq\\\!\\\|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](https://arxiv.org/html/2608.20738#S4.Thmtheorem2)

###### Proof\.

LetUt:=e−i​H​tU\_\{t\}\\\!:=\\\!e^\{\-\\mathrm\{i\}Ht\}andf\(z\)=\[Re\(z\)∥Im\(z\)\]f\(z\)\\\!=\\\!\[\\mathrm\{Re\}\(z\)\\\|\\mathrm\{Im\}\(z\)\]\. The mapffis an isometry fromℂN×d\\mathbb\{C\}^\{N\\times d\}toℝN×2​d\\mathbb\{R\}^\{N\\times 2d\}, so it does not change Dirichlet energy except for this real representation\.

Commuting case\.IfHHcommutes withLL\(in particularH=LH=L, orH=AH=Aon regular graphs after normalization\),UtU\_\{t\}andLLare simultaneously diagonalizable\. Each non\-trivial Laplacian coefficient is multiplied by a unit\-modulus phase, hence

\(S\.3\)E⁡\(f⁡\(Utn​X\(0\)\)\)=∑ℓ=1Nμℓ​‖X~ℓ\(0\)‖22=E⁡\(X\(0\)\)\.E\(f\(U\_\{t\}^\{n\}X^\{\(0\)\}\)\)=\\sum\_\{\\ell=1\}^\{N\}\\mu\_\{\\ell\}\\\|\\tilde\{X\}^\{\(0\)\}\_\{\\ell\}\\\|\_\{2\}^\{2\}=E\(X^\{\(0\)\}\)\.By Lemma[2](https://arxiv.org/html/2608.20738#Thmlemmaapp2), this constant is positive whenever the initial features have a non\-constant component\.

DefaultH=AH=A\.NowHHandLLneed not commute, so pointwise invariance is not claimed\. Instead, Lemma[2](https://arxiv.org/html/2608.20738#Thmlemmaapp2)givesE⁡\(f⁡\(Utn​X\(0\)\)\)≥Δ​‖P⟂​Utn​X\(0\)‖F2E\(f\(U\_\{t\}^\{n\}X^\{\(0\)\}\)\)\\geq\\Delta\\\|P\_\{\\perp\}U\_\{t\}^\{n\}X^\{\(0\)\}\\\|\_\{F\}^\{2\}\. Averaging over layers and applying \(A3\) yields

\(S\.4\)lim infT→∞1T​∑n<TE⁡\(f⁡\(Utn​X\(0\)\)\)≥Δ​η0\>0,\\liminf\_\{T\\to\\infty\}\\frac\{1\}\{T\}\\sum\_\{n<T\}E\(f\(U\_\{t\}^\{n\}X^\{\(0\)\}\)\)\\geq\\Delta\\eta\_\{0\}\>0,whereη0=lim infT→∞T−1​∑n<T‖P⟂​Utn​X\(0\)‖F2\\eta\_\{0\}\\\!=\\\!\\liminf\_\{T\\to\\infty\}T^\{\-1\}\\sum\_\{n<T\}\\\|P\_\{\\perp\}U\_\{t\}^\{n\}X^\{\(0\)\}\\\|\_\{F\}^\{2\}\. IfE⁡\(f⁡\(Utn​X\(0\)\)\)≤a​e−b​nE\(f\(U\_\{t\}^\{n\}X^\{\(0\)\}\)\)\\leq ae^\{\-bn\}for somea,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 anyX∈ℂN×dX\\in\\mathbb\{C\}^\{N\\times d\},E⁡\(X\)≥Δ​‖P⟂​X‖F2E\(X\)\\\!\\geq\\\!\\Delta\\\|P\_\{\\perp\}X\\\|\_\{F\}^\{2\}\. In the commuting CTQW case this givesE⁡\(f⁡\(Utn​X\(0\)\)\)≥Δ​‖P⟂​X\(0\)‖F2\>0E\(f\(U\_\{t\}^\{n\}X^\{\(0\)\}\)\)\\\!\\geq\\\!\\Delta\\\|P\_\{\\perp\}X^\{\(0\)\}\\\|\_\{F\}^\{2\}\\\!\>\\\!0for everyn≥0n\\\!\\geq\\\!0\.

###### Proof\.

SinceP⟂P\_\{\\perp\}removes only the zero eigenvector ofLL,E⁡\(X\)=∑ℓ≥2μℓ​‖X~ℓ‖22≥Δ​∑ℓ≥2‖X~ℓ‖22=Δ​‖P⟂​X‖F2E\(X\)=\\sum\_\{\\ell\\geq 2\}\\mu\_\{\\ell\}\\\|\\tilde\{X\}\_\{\\ell\}\\\|\_\{2\}^\{2\}\\geq\\Delta\\sum\_\{\\ell\\geq 2\}\\\|\\tilde\{X\}\_\{\\ell\}\\\|\_\{2\}^\{2\}=\\Delta\\\|P\_\{\\perp\}X\\\|\_\{F\}^\{2\}\. IfHHcommutes withLL,‖P⟂​Utn​X\(0\)‖F=‖P⟂​X\(0\)‖F\\\|P\_\{\\perp\}U\_\{t\}^\{n\}X^\{\(0\)\}\\\|\_\{F\}=\\\|P\_\{\\perp\}X^\{\(0\)\}\\\|\_\{F\}, and \(A2\) makes the bound strictly positive\. ∎

Classical diffusione−L​te^\{\-Lt\}admits the matching*upper*boundE⁡\(X\(n\+1\)\)≤e−2​Δ​t​E​\(X\(n\)\)E\(X^\{\(n\+1\)\}\)\\\!\\leq\\\!e^\{\-2\\Delta t\}E\(X^\{\(n\)\}\), decaying exponentially at rateΔ\\Delta\. The same spectral quantity drives diffusion over\-smoothing but yields aΔ\\Delta\-linear floor for CTQW\.

### A\.4\.Walk\-Timettand Effective Propagation Radius

###### Proposition 0\.

Let‖H‖2=λmax\\\|H\\\|\_\{2\}\\\!=\\\!\\lambda\_\{\\max\}andd𝒢​\(i,j\)d\_\{\\mathcal\{G\}\}\(i,j\)the geodesic distance\. For anyt\>0t\\\!\>\\\!0,

\(S\.5\)\|\(e−i​H​t\)i​j\|≤exp⁡\(λmax​t\)​\(λmax​t\)d𝒢​\(i,j\)d𝒢​\(i,j\)\!\.\|\(e^\{\-\\mathrm\{i\}Ht\}\)\_\{ij\}\|\\;\\leq\\;\\exp\(\\lambda\_\{\\max\}t\)\\frac\{\(\\lambda\_\{\\max\}t\)^\{d\_\{\\mathcal\{G\}\}\(i,j\)\}\}\{d\_\{\\mathcal\{G\}\}\(i,j\)\!\}\.Consequently, amplitudes beyond a radius linear inλmax​t\\lambda\_\{\\max\}tare factorially small; the implementation uses the conservative screening radiusreff​\(t\)=⌈2​λmax​t/π⌉r\_\{\\mathrm\{eff\}\}\(t\)\\\!=\\\!\\lceil 2\\lambda\_\{\\max\}t/\\pi\\rceiland then applies the empiricalϵ\\epsilonthreshold\.

###### Proof\.

Expande−i​H​t=∑k≥0\(−i​t\)k​Hk/k\!e^\{\-\\mathrm\{i\}Ht\}\\\!=\\\!\\sum\_\{k\\geq 0\}\(\-\\mathrm\{i\}t\)^\{k\}H^\{k\}/k\!\. BecauseHHis supported on graph edges,\(Hk\)i​j=0\(H^\{k\}\)\_\{ij\}=0wheneverk<d𝒢​\(i,j\)k<d\_\{\\mathcal\{G\}\}\(i,j\)\. Thus only walks of length at leastd𝒢​\(i,j\)d\_\{\\mathcal\{G\}\}\(i,j\)contribute\. Bounding\|\(Hk\)i​j\|≤‖Hk‖2≤λmaxk\|\(H^\{k\}\)\_\{ij\}\|\\leq\\\|H^\{k\}\\\|\_\{2\}\\leq\\lambda\_\{\\max\}^\{k\}gives

\|\(e−i​H​t\)i​j\|≤∑k≥d𝒢​\(i,j\)\(λmax​t\)kk\!≤exp⁡\(λmax​t\)​\(λmax​t\)d𝒢​\(i,j\)d𝒢​\(i,j\)\!,\|\(e^\{\-\\mathrm\{i\}Ht\}\)\_\{ij\}\|\\leq\\sum\_\{k\\geq d\_\{\\mathcal\{G\}\}\(i,j\)\}\\frac\{\(\\lambda\_\{\\max\}t\)^\{k\}\}\{k\!\}\\leq\\exp\(\\lambda\_\{\\max\}t\)\\frac\{\(\\lambda\_\{\\max\}t\)^\{d\_\{\\mathcal\{G\}\}\(i,j\)\}\}\{d\_\{\\mathcal\{G\}\}\(i,j\)\!\},which is a graph Lieb–Robinson\-type bound\([30](https://arxiv.org/html/2608.20738#bib.bib54)\)\. Stirling’s formula shows factorial decay onced𝒢​\(i,j\)d\_\{\\mathcal\{G\}\}\(i,j\)exceeds a constant multiple ofλmax​t\\lambda\_\{\\max\}t, justifying a linear truncation radius\. On a path, the exact amplitude is\|J\|i−j\|​\(2​t\)\|\|J\_\{\|i\-j\|\}\(2t\)\|\([8](https://arxiv.org/html/2608.20738#bib.bib48)\), whose ballistic front is also linear intt; this motivates the constant used byreff​\(t\)r\_\{\\mathrm\{eff\}\}\(t\)\. ∎

### A\.5\.Krylov Implementation Error

###### Proposition 0\.

LetU^t\(k\)\\hat\{U\}\_\{t\}^\{\(k\)\}denote thekk\-step Lanczos approximation ofe−i​H​te^\{\-\\mathrm\{i\}Ht\}\. For anyx∈ℂNx\\\!\\in\\\!\\mathbb\{C\}^\{N\}and anyk≥4​λmax​tk\\\!\\geq\\\!4\\lambda\_\{\\max\}t,

\(S\.6\)‖e−i​H​t​x−U^t\(k\)​x‖2≤12​‖x‖2​exp⁡\(−k216​λmax​t\)\.\\\|e^\{\-\\mathrm\{i\}Ht\}x\-\\hat\{U\}\_\{t\}^\{\(k\)\}x\\\|\_\{2\}\\;\\leq\\;12\\,\\\|x\\\|\_\{2\}\\,\\exp\\\!\\Big\(\\\!\-\\tfrac\{k^\{2\}\}\{16\\lambda\_\{\\max\}t\}\\Big\)\.Hence the discretised CTQW branch satisfies

\(S\.7\)EC​T​Q​Wapprox​\(X\(n\)\)≥EC​T​Q​Wexact​\(X\(n\)\)−ϵkry,E\_\{CTQW\}^\{\\mathrm\{approx\}\}\(X^\{\(n\)\}\)\\;\\geq\\;E\_\{CTQW\}^\{\\mathrm\{exact\}\}\(X^\{\(n\)\}\)\-\\epsilon\_\{\\mathrm\{kry\}\},withϵkry≤144μmaxB2exp\(−k2/\(8λmaxt\)\)\\epsilon\_\{\\mathrm\{kry\}\}\\\!\\leq\\\!144\\,\\mu\_\{\\max\}B^\{2\}\\,\\exp\\\!\\big\(\\\!\-k^\{2\}/\(8\\lambda\_\{\\max\}t\)\\big\)whenever the layer input satisfies‖X\(n\)‖F≤B\\\|X^\{\(n\)\}\\\|\_\{F\}\\leq B\.

###### Sketch\.

Eq\.[S\.6](https://arxiv.org/html/2608.20738#A1.E6)is Theorem 4 of[19](https://arxiv.org/html/2608.20738#bib.bib60)specialised to the skew\-Hermitian generator−i​H\-\\mathrm\{i\}Hof spectral radiusλmax\\lambda\_\{\\max\}; constants12,1612,16track through their proof\. For Eq\.[S\.7](https://arxiv.org/html/2608.20738#A1.E7), write the one\-application error asΞ\\Xiwith∥Ξ∥F≤12Be−k2/\(16λmaxt\)\\\|\\Xi\\\|\_\{F\}\\\!\\leq\\\!12Be^\{\-k^\{2\}/\(16\\lambda\_\{\\max\}t\)\}\. SinceL⪯μmax​IL\\preceq\\mu\_\{\\max\}I,\|E⁡\(X\+Ξ\)−E⁡\(X\)\|≤μmax​‖Ξ‖F2\+2​μmax​‖Ξ‖F​‖X‖F\|E\(X\+\\Xi\)\-E\(X\)\|\\leq\\mu\_\{\\max\}\\\|\\Xi\\\|\_\{F\}^\{2\}\+2\\mu\_\{\\max\}\\\|\\Xi\\\|\_\{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\. ∎

Atk=20k\\\!=\\\!20and the selectedttrange, 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\.

LetHHadmit the spectral decompositionH=U​Λ​U†H\\\!=\\\!U\\Lambda U^\{\\dagger\}with real eigenvalues\{λl\}l=1N\\\{\\lambda\_\{l\}\\\}\_\{l=1\}^\{N\}\. For any inputX∈ℂN×dX\\\!\\in\\\!\\mathbb\{C\}^\{N\\times d\}, writeX=∑lul​αl⊤X\\\!=\\\!\\sum\_\{l\}u\_\{l\}\\alpha\_\{l\}^\{\\top\}withαl∈ℂd\\alpha\_\{l\}\\\!\\in\\\!\\mathbb\{C\}^\{d\}the spectral coefficients\. Then the CTQW propagator preserves the magnitude of every spectral component:

\(S\.8\)‖\(e−i​H​t​X\)mode​l‖2=\|e−i​λl​t\|​‖αl‖2=‖αl‖2∀l=1,…,N\.\\\|\(\\,e^\{\-\\mathrm\{i\}Ht\}X\\,\)\_\{\\text\{mode \}l\}\\\|\_\{2\}\\;=\\;\|e^\{\-\\mathrm\{i\}\\lambda\_\{l\}t\}\|\\,\\\|\\alpha\_\{l\}\\\|\_\{2\}\\;=\\;\\\|\\alpha\_\{l\}\\\|\_\{2\}\\qquad\\forall\\,l\\\!=\\\!1,\\ldots,N\.Hence CTQW\-based Aggregation realises an exact all\-pass filter on the eigenbasis ofHH\.

###### Proof\.

ExpandX=∑lul​αl⊤X\\\!=\\\!\\sum\_\{l\}u\_\{l\}\\alpha\_\{l\}^\{\\top\}\. Since\{ul\}\\\{u\_\{l\}\\\}is orthonormal ande−i​H​t​ul=e−i​λl​t​ule^\{\-\\mathrm\{i\}Ht\}u\_\{l\}\\\!=\\\!e^\{\-\\mathrm\{i\}\\lambda\_\{l\}t\}u\_\{l\},e−i​H​t​X=∑le−i​λl​t​ul​αl⊤e^\{\-\\mathrm\{i\}Ht\}X\\\!=\\\!\\sum\_\{l\}e^\{\-\\mathrm\{i\}\\lambda\_\{l\}t\}\\,u\_\{l\}\\alpha\_\{l\}^\{\\top\}, so thell\-th mode coefficient becomese−i​λl​t​αle^\{\-\\mathrm\{i\}\\lambda\_\{l\}t\}\\alpha\_\{l\}\. Asλl∈ℝ\\lambda\_\{l\}\\\!\\in\\\!\\mathbb\{R\},\|e−i​λl​t\|=1\|e^\{\-\\mathrm\{i\}\\lambda\_\{l\}t\}\|\\\!=\\\!1, giving Eq\.[S\.8](https://arxiv.org/html/2608.20738#A1.E8)\. In contrast, classical diffusione−L​te^\{\-Lt\}multiplies thell\-th coefficient bye−λl​t<1e^\{\-\\lambda\_\{l\}t\}\\\!<\\\!1forλl\>0\\lambda\_\{l\}\\\!\>\\\!0, attenuating every non\-trivial mode at rate≥e−Δ​t\\geq\\\!e^\{\-\\Delta t\}per layer; this strictly contradicts the all\-pass property of CTQW\. ∎

Proposition[3](https://arxiv.org/html/2608.20738#A1.Thmtheorem3)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](https://arxiv.org/html/2608.20738#S4.Thmtheorem2)\.

### A\.7\.Branch\-Mixing Floor

###### Lemma 3\.

Let𝒮\(n\)\\mathcal\{S\}^\{\(n\)\}be the set of normalized full edge differencesδ=\[δL​F,δC​T​Q​W,δA​t​t\]\\delta=\[\\delta\_\{LF\},\\delta\_\{CTQW\},\\delta\_\{Att\}\]at layernn\. Assume the learned mixer has conditional CTQW gaincC​T​Q​W\>0c\_\{CTQW\}\>0on this subspace, meaning‖σ⁡\(δ​Wθ\)‖2≥cC​T​Q​W​‖δC​T​Q​W‖2\\\|\\sigma\(\\delta W\_\{\\theta\}\)\\\|\_\{2\}\\geq c\_\{CTQW\}\\\|\\delta\_\{CTQW\}\\\|\_\{2\}for allδ∈𝒮\(n\)\\delta\\in\\mathcal\{S\}^\{\(n\)\}\. Then

\(S\.9\)E⁡\(X\(n\+1\)\)≥cC​T​Q​W2​EC​T​Q​W\(n\)\.E\(X^\{\(n\+1\)\}\)\\;\\geq\\;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](https://arxiv.org/html/2608.20738#S4.Thmtheorem2)shows that a retained CTQW branch prevents exponential decay of the mixed representation\. ∎

## References

- Aharonovet al\.\(1993\)Y\. Aharonov, L\. Davidovich, and N\. ZaguryQuantum random walks\.Physical Review A48\(2\),pp\. 1687–1690\.Cited by:[§3](https://arxiv.org/html/2608.20738#S3.SS0.SSS0.Px4.p1.1)\.
- Al\-Mohy and Higham \(2011\)A\. H\. Al\-Mohy and N\. J\. HighamComputing the action of the matrix exponential, with an application to exponential integrators\.SIAM Journal on Scientific Computing33\(2\),pp\. 488–511\.Cited by:[§4\.2](https://arxiv.org/html/2608.20738#S4.SS2.p5.1)\.
- Aubryet al\.\(2011\)M\. Aubry, U\. Schlickewei, and D\. CremersThe wave kernel signature: a quantum mechanical approach to shape analysis\.In2011 IEEE International Conference on Computer Vision Workshops \(ICCV Workshops\),Vol\.,pp\. 1626–1633\.External Links:[Document](https://dx.doi.org/10.1109/ICCVW.2011.6130444),ISSNCited by:[§1](https://arxiv.org/html/2608.20738#S1.p5.1)\.
- Boet al\.\(2021\)D\. Bo, X\. Wang, C\. Shi, and H\. ShenBeyond low\-frequency information in graph convolutional networks\.InProceedings of the AAAI conference on artificial intelligence,Vol\.35,pp\. 3950–3957\.Cited by:[§1](https://arxiv.org/html/2608.20738#S1.p2.1),[§2](https://arxiv.org/html/2608.20738#S2.p1.1)\.
- Bose \(2003\)S\. BoseQuantum communication through an unmodulated spin chain\.Physical review letters91\(20\),pp\. 207901\.Cited by:[§4\.2](https://arxiv.org/html/2608.20738#S4.SS2.p4.1)\.
- Chamberlainet al\.\(2021\)B\. Chamberlain, J\. Rowbottom, M\. I\. Gorinova, M\. Bronstein, S\. Webb, and E\. RossiGRAND: graph neural diffusion\.InProceedings of the 38th International Conference on Machine Learning,M\. Meila and T\. Zhang \(Eds\.\),Proceedings of Machine Learning Research, Vol\.139,pp\. 1407–1418\.External Links:[Link](https://proceedings.mlr.press/v139/chamberlain21a.html)Cited by:[§1](https://arxiv.org/html/2608.20738#S1.p4.1)\.
- Chienet al\.\(2021\)E\. Chien, J\. Peng, P\. Li, and O\. MilenkovicAdaptive universal generalized pagerank graph neural network\.InInternational Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=n6jl7fLxrP)Cited by:[§1](https://arxiv.org/html/2608.20738#S1.p4.1),[§5\.1](https://arxiv.org/html/2608.20738#S5.SS1.p2.1)\.
- Childset al\.\(2002\)A\. M\. Childs, E\. Farhi, and S\. GutmannAn example of the difference between quantum and classical random walks\.Quantum Information Processing1,pp\. 35–43\.Cited by:[§A\.4](https://arxiv.org/html/2608.20738#A1.SS4.p1.2.1),[§3](https://arxiv.org/html/2608.20738#S3.SS0.SSS0.Px4.p1.1),[§4\.2](https://arxiv.org/html/2608.20738#S4.SS2.p1.3)\.
- Chung \(1997\)F\. R\. ChungSpectral graph theory\.Vol\.92,American Mathematical Soc\.\.Cited by:[Appendix A](https://arxiv.org/html/2608.20738#A1.SS0.SSS0.Px1.p1.2),[§3](https://arxiv.org/html/2608.20738#S3.SS0.SSS0.Px4.p1.1)\.
- Eliasofet al\.\(2021\)M\. Eliasof, E\. Haber, and E\. TreisterPde\-gcn: novel architectures for graph neural networks motivated by partial differential equations\.Advances in neural information processing systems34,pp\. 3836–3849\.Cited by:[§1](https://arxiv.org/html/2608.20738#S1.p4.1)\.
- Eliasofet al\.\(2024\)M\. Eliasof, E\. Haber, and E\. TreisterFeature transportation improves graph neural networks\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.38,pp\. 11874–11882\.Cited by:[§1](https://arxiv.org/html/2608.20738#S1.p4.1)\.
- Erricaet al\.\(2025\)F\. Errica, H\. Christiansen, V\. Zaverkin, T\. Maruyama, M\. Niepert, and F\. AlesianiAdaptive message passing: a general framework to mitigate oversmoothing, oversquashing, and underreaching\.InProceedings of the 42nd International Conference on Machine Learning,PMLR, Vol\.267,pp\. 15490–15515\.Cited by:[§5\.1](https://arxiv.org/html/2608.20738#S5.SS1.p2.1)\.
- Farhi and Gutmann \(1998\)E\. Farhi and S\. GutmannQuantum computation and decision trees\.Physical Review A58\(2\),pp\. 915\.Cited by:[§3](https://arxiv.org/html/2608.20738#S3.SS0.SSS0.Px4.p1.1),[§4\.2](https://arxiv.org/html/2608.20738#S4.SS2.p1.3)\.
- Gaoet al\.\(2023\)Y\. Gao, X\. Wang, X\. He, Z\. Liu, H\. Feng, and Y\. ZhangAddressing heterophily in graph anomaly detection: a perspective of graph spectrum\.InProceedings of the ACM Web Conference 2023,pp\. 1528–1538\.Cited by:[§1](https://arxiv.org/html/2608.20738#S1.p1.1)\.
- Giraldoet al\.\(2023\)J\. H\. Giraldo, K\. Skianis, T\. Bouwmans, and F\. D\. MalliarosOn the trade\-off between over\-smoothing and over\-squashing in deep graph neural networks\.InProceedings of the 32nd ACM International Conference on Information and Knowledge Management,CIKM ’23,New York, NY, USA,pp\. 566–576\.External Links:ISBN 9798400701245,[Link](https://doi.org/10.1145/3583780.3614997),[Document](https://dx.doi.org/10.1145/3583780.3614997)Cited by:[§1](https://arxiv.org/html/2608.20738#S1.p3.1)\.
- Guo and Wei \(2023\)Y\. Guo and Z\. WeiGraph neural networks with learnable and optimal polynomial bases\.InProceedings 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,pp\. 12077–12097\.External Links:[Link](https://proceedings.mlr.press/v202/guo23i.html)Cited by:[§2](https://arxiv.org/html/2608.20738#S2.p1.1)\.
- Hamiltonet al\.\(2017\)W\. L\. Hamilton, R\. Ying, and J\. LeskovecInductive representation learning on large graphs\.InNIPS,Cited by:[§5\.1](https://arxiv.org/html/2608.20738#S5.SS1.p2.1)\.
- Heet al\.\(2016\)K\. He, X\. Zhang, S\. Ren, and J\. SunDeep residual learning for image recognition\.InProceedings of the IEEE conference on computer vision and pattern recognition,pp\. 770–778\.Cited by:[§5\.1](https://arxiv.org/html/2608.20738#S5.SS1.p2.1)\.
- Hochbruck and Lubich \(1997\)M\. Hochbruck and C\. LubichOn krylov subspace approximations to the matrix exponential operator\.SIAM Journal on Numerical Analysis34\(5\),pp\. 1911–1925\.Cited by:[§A\.5](https://arxiv.org/html/2608.20738#A1.SS5.p1.1.1)\.
- Huanget al\.\(2024\)K\. Huang, Y\. G\. Wang, M\. Li, and P\. LioHow universal polynomial bases enhance spectral graph neural networks: heterophily, over\-smoothing, and over\-squashing\.InInternational Conference on Machine Learning,pp\. 20310–20330\.Cited by:[§5\.1](https://arxiv.org/html/2608.20738#S5.SS1.p2.1)\.
- \[21\]Q\. Kang, K\. Zhao, Q\. Ding, F\. Ji, X\. Li, W\. Liang, Y\. Song, and W\. P\. TayUnleashing the potential of fractional calculus in graph neural networks with frond\.InThe Twelfth International Conference on Learning Representations,Cited by:[§5\.1](https://arxiv.org/html/2608.20738#S5.SS1.p2.1)\.
- Kempe \(2003\)J\. KempeQuantum random walks: an introductory overview\.Contemporary Physics44\(4\),pp\. 307–327\.Cited by:[§3](https://arxiv.org/html/2608.20738#S3.SS0.SSS0.Px4.p1.1)\.
- Kipf and Welling \(2017\)T\. N\. Kipf and M\. WellingSemi\-supervised classification with graph convolutional networks\.InInternational Conference on Learning Representations \(ICLR\),Cited by:[§5\.1](https://arxiv.org/html/2608.20738#S5.SS1.p2.1),[§5\.4](https://arxiv.org/html/2608.20738#S5.SS4.p1.1)\.
- Lanczos \(1950\)C\. LanczosAn iteration method for the solution of the eigenvalue problem of linear differential and integral operators\.Journal of Research of the National Bureau of Standards45\(4\),pp\. 255–282\.Cited by:[§4\.2](https://arxiv.org/html/2608.20738#S4.SS2.p5.1)\.
- Liet al\.\(2024\)B\. Li, E\. Pan, and Z\. KangPc\-conv: unifying homophily and heterophily with two\-fold filtering\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.38,pp\. 13437–13445\.Cited by:[§1](https://arxiv.org/html/2608.20738#S1.p2.1),[§5\.1](https://arxiv.org/html/2608.20738#S5.SS1.p2.1)\.
- Liet al\.\(2018\)Q\. Li, Z\. Han, and X\. WuDeeper insights into graph convolutional networks for semi\-supervised learning\.InProceedings 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\-8Cited by:[§1](https://arxiv.org/html/2608.20738#S1.p3.1)\.
- Liet al\.\(2019\)Q\. Li, X\. Wu, H\. Liu, X\. Zhang, and Z\. GuanLabel efficient semi\-supervised learning via graph filtering\.InProceedings of the IEEE/CVF conference on computer vision and pattern recognition,pp\. 9582–9591\.Cited by:[§1](https://arxiv.org/html/2608.20738#S1.p2.1)\.
- Liet al\.\(2022\)X\. Li, R\. Zhu, Y\. Cheng, C\. Shan, S\. Luo, D\. Li, and W\. QianFinding global homophily in graph neural networks when meeting heterophily\.InInternational Conference on Machine Learning,pp\. 13242–13256\.Cited by:[§2](https://arxiv.org/html/2608.20738#S2.p1.1),[§4\.2](https://arxiv.org/html/2608.20738#S4.SS2.p7.1),[§5\.1](https://arxiv.org/html/2608.20738#S5.SS1.p2.1)\.
- Lianget al\.\(2024\)L\. Liang, X\. Hu, Z\. Xu, Z\. Song, and I\. KingPredicting global label relationship matrix for graph neural networks under heterophily\.Advances in Neural Information Processing Systems36\.Cited by:[§1](https://arxiv.org/html/2608.20738#S1.p2.1),[§2](https://arxiv.org/html/2608.20738#S2.p1.1)\.
- Lieb and Robinson \(1972\)E\. H\. Lieb and D\. W\. RobinsonThe finite group velocity of quantum spin systems\.Communications in Mathematical Physics28\(3\),pp\. 251–257\.Cited by:[§A\.4](https://arxiv.org/html/2608.20738#A1.SS4.p1.2.1)\.
- Limet al\.\(2021\)D\. Lim, F\. Hohne, X\. Li, S\. L\. Huang, V\. Gupta, O\. Bhalerao, and S\. N\. LimLarge scale learning on non\-homophilous graphs: new benchmarks and strong simple methods\.Advances in Neural Information Processing Systems34,pp\. 20887–20902\.Cited by:[§4\.2](https://arxiv.org/html/2608.20738#S4.SS2.p7.1)\.
- Liuet al\.\(2021\)C\. Liu, L\. Wen, Z\. Kang, G\. Luo, and L\. TianSelf\-supervised consensus representation learning for attributed graph\.InProceedings of the 29th ACM international conference on multimedia,pp\. 2654–2662\.Cited by:[§1](https://arxiv.org/html/2608.20738#S1.p1.1)\.
- Liuet al\.\(2025\)S\. Liu, D\. He, Z\. Yu, D\. Jin, Z\. Feng, and W\. ZhangIntegrating co\-training with edge discrimination to enhance graph neural networks under heterophily\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.39,pp\. 18960–18968\.Cited by:[§5\.1](https://arxiv.org/html/2608.20738#S5.SS1.p2.1)\.
- Maoet al\.\(2024\)H\. Mao, Z\. Chen, W\. Jin, H\. Han, Y\. Ma, T\. Zhao, N\. Shah, and J\. TangDemystifying structural disparity in graph neural networks: can one size fit all?\.Advances in neural information processing systems36\.Cited by:[§1](https://arxiv.org/html/2608.20738#S1.p5.1),[§4\.2](https://arxiv.org/html/2608.20738#S4.SS2.p7.1),[§5\.3](https://arxiv.org/html/2608.20738#S5.SS3.p1.1)\.
- Maskeyet al\.\(2024\)S\. Maskey, R\. Paolino, A\. Bacho, and G\. KutyniokA fractional graph laplacian approach to oversmoothing\.Advances in Neural Information Processing Systems36\.Cited by:[§1](https://arxiv.org/html/2608.20738#S1.p2.1),[§1](https://arxiv.org/html/2608.20738#S1.p5.1),[§4\.2](https://arxiv.org/html/2608.20738#S4.SS2.p7.1),[§5\.1](https://arxiv.org/html/2608.20738#S5.SS1.p2.1)\.
- Mauryaet al\.\(2022\)S\. K\. Maurya, X\. Liu, and T\. MurataSimplifying approach to node classification in graph neural networks\.Journal of Computational Science62,pp\. 101695\.Cited by:[§5\.1](https://arxiv.org/html/2608.20738#S5.SS1.p2.1)\.
- McCallumet al\.\(2000\)A\. K\. McCallum, K\. Nigam, J\. Rennie, and K\. SeymoreAutomating the construction of internet portals with machine learning\.Information Retrieval3,pp\. 127–163\.Cited by:[§5\.1](https://arxiv.org/html/2608.20738#S5.SS1.p1.1)\.
- Moler and Van Loan \(2003\)C\. Moler and C\. Van LoanNineteen dubious ways to compute the exponential of a matrix, twenty\-five years later\.SIAM Review45\(1\),pp\. 3–49\.Cited by:[§4\.2](https://arxiv.org/html/2608.20738#S4.SS2.p5.1)\.
- Namataet al\.\(2012\)G\. Namata, B\. London, L\. Getoor, B\. Huang, and U\. EduQuery\-driven active surveying for collective classification\.In10th international workshop on mining and learning with graphs,Vol\.8,pp\. 1\.Cited by:[§5\.1](https://arxiv.org/html/2608.20738#S5.SS1.p1.1)\.
- Peiet al\.\(2020\)H\. Pei, B\. Wei, K\. C\. Chang, Y\. Lei, and B\. YangGeom\-gcn: geometric graph convolutional networks\.arXiv preprint arXiv:2002\.05287\.Cited by:[§5\.1](https://arxiv.org/html/2608.20738#S5.SS1.p1.1)\.
- Platonovet al\.\(2023\)O\. Platonov, D\. Kuznedelev, M\. Diskin, A\. Babenko, and L\. ProkhorenkovaA critical look at evaluation of gnns under heterophily: are we really making progress?\.InThe Eleventh International Conference on Learning Representations,Cited by:[§5\.1](https://arxiv.org/html/2608.20738#S5.SS1.p1.1),[§5\.2](https://arxiv.org/html/2608.20738#S5.SS2.p3.1)\.
- Quanet al\.\(2023\)Y\. Quan, J\. Ding, C\. Gao, L\. Yi, D\. Jin, and Y\. LiRobust preference\-guided denoising for graph based social recommendation\.InProceedings of the ACM Web Conference 2023,pp\. 1097–1108\.Cited by:[§1](https://arxiv.org/html/2608.20738#S1.p1.1)\.
- Ronget al\.\(2019\)Y\. Rong, W\. Huang, T\. Xu, and J\. HuangDropedge: towards deep graph convolutional networks on node classification\.arXiv preprint arXiv:1907\.10903\.Cited by:[§1](https://arxiv.org/html/2608.20738#S1.p3.1),[§2](https://arxiv.org/html/2608.20738#S2.p2.1)\.
- Ruschet al\.\(2023\)T\. K\. Rusch, M\. M\. Bronstein, and S\. MishraA survey on oversmoothing in graph neural networks\.arXiv preprint arXiv:2303\.10993\.Cited by:[§1](https://arxiv.org/html/2608.20738#S1.p3.1),[§2](https://arxiv.org/html/2608.20738#S2.p2.1),[§3](https://arxiv.org/html/2608.20738#S3.SS0.SSS0.Px3.p1.1)\.
- Ruschet al\.\(2022\)T\. K\. Rusch, B\. Chamberlain, J\. Rowbottom, S\. Mishra, and M\. BronsteinGraph\-coupled oscillator networks\.InInternational Conference on Machine Learning,pp\. 18888–18909\.Cited by:[§1](https://arxiv.org/html/2608.20738#S1.p3.1),[§1](https://arxiv.org/html/2608.20738#S1.p4.1),[§2](https://arxiv.org/html/2608.20738#S2.p2.1),[§3](https://arxiv.org/html/2608.20738#S3.SS0.SSS0.Px3.p1.2)\.
- Senet al\.\(2008\)P\. Sen, G\. Namata, M\. Bilgic, L\. Getoor, B\. Galligher, and T\. Eliassi\-RadCollective classification in network data\.AI magazine29\(3\),pp\. 93–93\.Cited by:[§5\.1](https://arxiv.org/html/2608.20738#S5.SS1.p1.1)\.
- Shiet al\.\(2016\)C\. Shi, Y\. Li, J\. Zhang, Y\. Sun, and P\. S\. YuA survey of heterogeneous information network analysis\.IEEE Transactions on Knowledge and Data Engineering29\(1\),pp\. 17–37\.Cited by:[§3](https://arxiv.org/html/2608.20738#S3.SS0.SSS0.Px5.p1.1)\.
- Shiet al\.\(2020\)Y\. Shi, Z\. Huang, S\. Feng, H\. Zhong, W\. Wang, and Y\. SunMasked label prediction: unified message passing model for semi\-supervised classification\.arXiv preprint arXiv:2009\.03509\.Cited by:[§1](https://arxiv.org/html/2608.20738#S1.p5.1)\.
- Tuet al\.\(2024\)G\. Tu, T\. Xie, B\. Liang, H\. Wang, and R\. XuAdaptive graph learning for multimodal conversational emotion detection\.InProceedings of the AAAI Conference on Artificial Intelligence,Vol\.38,pp\. 19089–19097\.Cited by:[§1](https://arxiv.org/html/2608.20738#S1.p1.1),[§2](https://arxiv.org/html/2608.20738#S2.p1.1)\.
- Veličkovićet al\.\(2018\)P\. Veličković, G\. Cucurull, A\. Casanova, A\. Romero, P\. Liò, and Y\. BengioGraph Attention Networks\.International Conference on Learning Representations\.Note:accepted as posterExternal Links:[Link](https://openreview.net/forum?id=rJXMpikCZ)Cited by:[§5\.1](https://arxiv.org/html/2608.20738#S5.SS1.p2.1),[§5\.4](https://arxiv.org/html/2608.20738#S5.SS4.p1.1)\.
- Wanget al\.\(2023\)Y\. Wang, K\. Yi, X\. Liu, Y\. G\. Wang, and S\. JinACMP: allen\-cahn message passing with attractive and repulsive forces for graph neural networks\.InThe Eleventh International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=4fZc_79Lrqs)Cited by:[§1](https://arxiv.org/html/2608.20738#S1.p3.1),[§1](https://arxiv.org/html/2608.20738#S1.p4.1),[§5\.1](https://arxiv.org/html/2608.20738#S5.SS1.p2.1)\.
- Wuet al\.\(2019\)F\. Wu, A\. Souza, T\. Zhang, C\. Fifty, T\. Yu, and K\. WeinbergerSimplifying graph convolutional networks\.InInternational conference on machine learning,pp\. 6861–6871\.Cited by:[§1](https://arxiv.org/html/2608.20738#S1.p2.1)\.
- Wuet al\.\(2024\)X\. Wu, A\. Ajorlou, Z\. Wu, and A\. JadbabaieDemystifying oversmoothing in attention\-based graph neural networks\.Advances in Neural Information Processing Systems36\.Cited by:[§4\.4](https://arxiv.org/html/2608.20738#S4.SS4.p3.1)\.
- Yanet al\.\(2022\)Y\. Yan, M\. Hashemi, K\. Swersky, Y\. Yang, and D\. KoutraTwo sides of the same coin: heterophily and oversmoothing in graph convolutional neural networks\.In2022 IEEE International Conference on Data Mining \(ICDM\),pp\. 1287–1292\.Cited by:[§1](https://arxiv.org/html/2608.20738#S1.p4.1),[§5\.1](https://arxiv.org/html/2608.20738#S5.SS1.p1.1)\.
- Yuet al\.\(2023\)H\. Yu, Z\. Xu, X\. Qian, X\. Qian, and S\. JiEfficient and equivariant graph networks for predicting quantum hamiltonian\.InInternational Conference on Machine Learning,pp\. 40412–40424\.Cited by:[§1](https://arxiv.org/html/2608.20738#S1.p1.1)\.
- Zhanget al\.\(2025\)S\. Zhang, H\. Wang, J\. Lin, X\. Guo, Y\. Zhu, S\. Zhang, D\. Fu, and D\. ZhouHeroFilter: adaptive spectral graph filter for varying heterophilic relations\.InAdvances in Neural Information Processing Systems,Cited by:[§5\.1](https://arxiv.org/html/2608.20738#S5.SS1.p2.1)\.
- Zhaoet al\.\(2023\)K\. Zhao, Q\. Kang, Y\. Song, R\. She, S\. Wang, and W\. P\. TayGraph neural convection\-diffusion with heterophily\.InProc\. International Joint Conference on Artificial Intelligence,Macao, China\.Cited by:[§5\.1](https://arxiv.org/html/2608.20738#S5.SS1.p2.1)\.
- \[58\]K\. Zhao, X\. Li, Q\. Kang, F\. Ji, Q\. Ding, Y\. Zhao, W\. Liang, and W\. P\. TayDistributed\-order fractional graph operating network\.InThe Thirty\-eighth Annual Conference on Neural Information Processing Systems,Cited by:[§5\.1](https://arxiv.org/html/2608.20738#S5.SS1.p2.1)\.
- Zhenget al\.\(2023\)Y\. Zheng, H\. Zhang, V\. Lee, Y\. Zheng, X\. Wang, and S\. PanFinding the missing\-half: graph complementary learning for homophily\-prone and heterophily\-prone graphs\.InInternational Conference on Machine Learning,pp\. 42492–42505\.Cited by:[§1](https://arxiv.org/html/2608.20738#S1.p2.1),[§5\.1](https://arxiv.org/html/2608.20738#S5.SS1.p1.1)\.
- Zhouet al\.\(2020\)K\. Zhou, X\. Huang, Y\. Li, D\. Zha, R\. Chen, and X\. HuTowards deeper graph neural networks with differentiable group normalization\.Advances in neural information processing systems33,pp\. 4917–4928\.Cited by:[§1](https://arxiv.org/html/2608.20738#S1.p3.1)\.
- Zhouet al\.\(2021\)K\. Zhou, Y\. Dong, K\. Wang, W\. S\. Lee, B\. Hooi, H\. Xu, and J\. FengUnderstanding and resolving performance degradation in deep graph convolutional networks\.InProceedings of the 30th ACM International Conference on Information & Knowledge Management,pp\. 2728–2737\.Cited by:[§1](https://arxiv.org/html/2608.20738#S1.p3.1),[§2](https://arxiv.org/html/2608.20738#S2.p2.1)\.
- Zhuet al\.\(2020\)J\. Zhu, Y\. Yan, L\. Zhao, M\. Heimann, L\. Akoglu, and D\. KoutraBeyond homophily in graph neural networks: current limitations and effective designs\.Advances in neural information processing systems33,pp\. 7793–7804\.Cited by:[§1](https://arxiv.org/html/2608.20738#S1.p2.1)\.
- Zhuoet al\.\(2025\)W\. Zhuo, H\. Yu, G\. Tan, and X\. LiCommute graph neural networks\.InProceedings of the 42nd International Conference on Machine Learning,PMLR, Vol\.267,pp\. 80612–80628\.Cited by:[§5\.1](https://arxiv.org/html/2608.20738#S5.SS1.p2.1)\.