A Dynamical Systems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Attention Networks
Authors: Biswadeep Chakraborty
Harshit Kumar
Saibal Mukhopadhyay
Venue: ICML 2025 poster (2025)
Keywords: graph neural networks
oversmoothing
dynamical systems
attention mechanisms
pruning optimization
graph attention networks
spectral analysis
anti-hebbian learning
node representation
Primary area: deep_learning->graph_neural_networks
TL;DR: DYNAMO-GAT prevents deep neural networks from losing node distinctiveness by using dynamical systems theory to selectively prune attention weights, achieving superior accuracy with better computational efficiency than existing methods.

Abstract: Graph Neural Networks (GNNs) face a critical limitation known as oversmoothing, where increasing network depth leads to homogenized node representations, severely compromising their expressiveness. We present a novel dynamical systems perspective on this challenge, revealing oversmoothing as an emergent property of GNNs' convergence to low-dimensional attractor states. Based on this insight, we introduce **DYNAMO-GAT**, which combines noise-driven covariance analysis with Anti-Hebbian learning to dynamically prune attention weights, effectively preserving distinct attractor states. We provide theoretical guarantees for DYNAMO-GAT's effectiveness and demonstrate its superior performance on benchmark datasets, consistently outperforming existing methods while requiring fewer computational resources. This work establishes a fundamental connection between dynamical systems theory and GNN behavior, providing both theoretical insights and practical solutions for deep graph learning.

A Dynamical Systems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Attention Networks
Biswadeep Chakraborty
Harshit Kumar'
Saibal Mukhopadhyay
Abstract
Orginnt Graph
Overamosthing
Graph Neural Networks (GNNs) face critical limitation known as oversmoothing. where in- creasing network depth leads to homogenized node representations, severely compromising their expressiveness. We present novel dynami- cal systems perspective this challenge, reveal- ing oversmoothing
Prustng
emergent property of GNNs' convergence to -wwddimensionll attrac- tor states. Based on this insight, we introduce DYNAMO-GAT, which combines noise-driven covariance analysis with Anti-Hebbian learning to dynamically prune attention weights, effec- tively preserving distinct attractor states. We pro- vide theoretical guarantees for DYNAMO-GAT's effectiveness and demonstrate its superior per- formance on benchmark datasets, consistently outperforming existing methods while requiring fewer computational resources. This work estab- lishes fundamental connection between dynami- cal systems theory and GNN behavior, providing both theoretical insights and practical solutions for deep graph learning.
Figure I. As the number of layers l in a GNN increases, over- smoothing causes node embeddings to converge towards a single aftractor state, resulting in the loss of node feature diversity. Prun- ing mitigates this effect by maintaining multiple attractor states, thereby preserving the distinctiveness of node embeddings and preventing the detrimental effects of oversmoothing.
and performance (Li et al., 2018).
Oversmoothing emerges from the fundamental mechanism of GNNs repeated message passing between nodes (Oono & Suzuki, 2020; Cai & Wang, 2020; Keriven, 2022). While various architectural solutions have been proposed, includ- ing skip connections (Li al., 2019; Xu et al., 2018), nor- malization techniques (Ba et al., 2016; Ioffe & Szegedy, 2015; Zhou et al., 2020), attention mechanisms (Velick- ovic et al., 2018; Wu et al., 2023), and other strategies like stochastic methods or residual connections, these ap- proaches primarily focus on structural modifications. While some work also explores GNN dynamics, for instance, through learned energy metrics (Jin & Zhu, 2024), many existing methods fail to fully address the underlying conver- gence dynamics that drive oversmoothing (Li et al., 2018; Chen et al., 2020; Oono & Suzuki, 2020).
1. Introduction
Graph Neural Networks (GNNs) (Wu al., 2020) have emerged as powerful tools for learning from graph- structured data, achieving remarkable success in molecular property prediction (Gilmer et al., 2017; Reiser et al.. 2022: Gasteiger et al., 2021), social network analysis (Kipf & Welling, 2017; Fan et al., 2019), and recommendation sys- tems (Ying et al., 2018). However, as these networks grow deeper, they face a critical challenge: oversmoothing, where node represennations become increasingly homogeneous and indistinguishable, severely impairing their expressiveness
Recent attempts to mitigate oversmoothing through prun- ing (Zhao al., 2020) or graph sparsification (Spielman & Srivastava, 2011) have shown promise in redueing network redundancy. However, traditional sparsification often priori- tizes structural or spectral fidelity primarily for efficiency, not directly targeting the feature dynamics causing over- smoothing. Similarly. Graph Attention Networks (GATs), while improving feature aggregation, still struggle in deep architectures (Wu et al., 2023). This is partly because they
'Deparmeett of Electrical and Computer Engineering, Geor- gia Institute of Technology, Atlanta, USA. Correspondence to: Biswadeep Chakraborty <biswadeep@ Dbisaadee@@gttoch.ddus gatech.edus.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

A Dynamical Systems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Attention Networks
often overlook the fundamental dynamical behavior and can face challenges in learning truly sparse attention patterns due to inherent trainability issues, which can prevent the effective removal of redundant connections (Mustafa et al., 2021).
stand and address this phenomenon, we adopt dynamical systems perspective (Roth & Liehig, 2024).
Unlike traditional approaches that focus on architectural modifications, the dynamical systems view provides more fundamental explanation by examining the stability and convergence properties of GNNs. By modeling GATs as dy- namical systems, we can analyze how node representations evolve across layers and identify the conditions under which oversmoothing occurs (Wu et al., 2024; Di Giovanni et al., 2023). This perspective not only deepens our theoretical un- derstanding but also suggests new strategies for mitigating oversmoothing (Roth & Liebig, 2024; Rusch et al., 2022).
In this work, we reconceptualize oversmoothing through the lens of dynamical systems theory. By viewing the message- passing process as dynamical system converging to low-dimensional attractor (Li al., 2019), we formally characterize the conditions driving the collapse of node rep- resentations. Our analysis, based on eigenvalue properties of graph attention mechanisms (Abbe et al., 2020; Allen- Zhu et al., 2019), reveals oversmoothing as an emergent property of the network's convergence dynamics, enabling the design of more effective countermeasures.
GAT' as Dynamical Systems. In GATs, node representa- tions evolve according to the learned attention weights aij. which govern the influence of neighboring nodes. This dy- namic weighting introduces complexity into the system's be- havior, making it essential to understand how these weights evolve across layers.
We introduce DYNAMO-GAT, GNN architecture that adaptively counteracts oversmoothing by leveraging dynam- ical systems principles. DYNAMO-GAT preserves node diversity across layers by altering the system's fixed points during training through selective pruning and noise-driven covariance analysis. Our key contributions are:
As these weights evolve, the system's 's dynamics may lead to state where node representations become indistinguishable, resulting in oversmoothing. Understanding this process is key designing GAT's that avoid oversmoothing while still leveraging attention mechanisms effectively.
A rigorous theoretical framework that analyzes over- smoothing through dynamical systems principles, re- vealing its fundamental causes and potential mitigation strategies.
2.1. Theoretical Analysis of Oversmoothing in GATs
In this subsection, we rigorously analyze the phenomenon of oversmoothing in GATs using dynamical systems the- ory. Specifically, we explore the existence of fixed points, their stability, and the conditions under which node repre- sentations converge to indistinguishable states. The detailed thcoretical proofs are given in the Supplementary Section Lemma 1 (GAT Fixed Point Properties). Let G (V, F) be graph with N nodes and consider a GAT with update rule f R Nxd + RNN
DYNAMO GAT: A novel architecture that dynamically counteracts oversmoothing by adaptively modifying the network's attractor landscape during training.
Comprehensive theoretical analysis and empirical vali- dation demonstrating how DYNAMO-GAT preserves node diversity and enhances expressiveness in deep GNNs, achieving superior performance on benchmark datasets.
X1(t + 1) =0 Σ (01(0)x(0))
This work represents significant shift from empirical fixes to a fundamental understanding of oversmoothing, estab- lishing both theoretical foundations and practical solutions. Our findings not only advance the development of more robust and expressive GNN architectures but also open new avenues for analyzing deep learning systems through dy- namical principles.
JEN(O
where:
o is LipLscchh with Lg I 1
W E dddd with [|| < I+K
Attention weights osj (t) satisfy: Non-negativity and
2. Dynamical Systems View of Oversmoothing
normalization: (iy(!) 2 0. EjeN(a) (ty(t) = -lip--
schitz continuity: ||oss (un (t-1)l < K (())(
Oversmoothing in GNNs is critical challenge, particu- larly as the depth of these networks increases. While Graph Attention Networks (GATs) introduce dynamic weighting mechanisms that can mitigate oversmoothing to some ex- tent, they can also contribute to it under certain conditions (Velickovic et al., 2018: Rusch et al., 2023b). To fully under-
Xx(t - 1)]l2 Boundedness: max,,, ||a.y (t)lla S M
Them:
(a) f is a contraction with constant c = || (1 + K)- < 1
2

---

A Dynamical Systems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Attention Networks
(b) There exists a unique fixed point X* with X ((X))
of the attention matrix A". The key insight is that the eigen- structure of A determines feature homogenization, with the spectral gap " serving as a natural measure.
(c) For any (0): - S ((() - 1=1
-
(d) The attention weights converge 33 with: ||ar(()
Using the Spectral Theorem, we decompose A into eigen- components:
0g ll S (d))) - | and > 2)EN() llaryll
oiol HN + Σ AA(""))
A = A1')
Intuition and Proof Sketch. /Complete proof in Suppl. Sec. A/ This lemma establishes GAT's convergence properties through dynamical systems analysis. At each node i, using o's s Lipschitz property and attention normalization:
==2
where {A,(A*) are ordered eigenvalues and {2s} are or- thonormal eigenvectors. At the fixed point:
[x x,(1)l2 |oo( Σ JEN())
any (t)())X)((1)
X (("WX*)) v X"WX" (locally),
where the approximation follows from o being contractive. Using matrix perturbation theory:
-o(
Σ
aig ( - (1 1))ll2
(EM(8)
VI of 1N
Aa (A*)
$ x
|
X
|
A1 (A+)
These node-level contractions yield a matrix-level contrac- tion [ + +1 (()) S (t) X(t 1)]l where c= || + K) < 1. The Banach fixed-point theorem then ensures convergence to unique fixed point X", with attention weights inheriting this convergence through their Lipschitz continuity.
The spectral gap = 1 A=(Aa) through:
controls feature differences
A1 (Ar)
|X; Xf112 S (1 (1-1)) XI'
revealing that small spectral gaps lead to oversmoothing, with the residual term E capturing deviations from complete homogenization.
Lemma 2 (Spectral Analysis of Fixed Point). Let X* E R Nxd be the fixed point from Lemma 1, and let A E N be the fixed-poine attention matrix with entries
[A*]; = =a.; for j E (i) and 0 otherwise. Let X (A"),, A²(A be its largest and second-larges eigenvalues with
oow-Dimensional Attractor Characterization). For a GAT' with node features X(t) R at layer t,
Lemma
vn the leading eigenvector. Then:
define the feature diversity measure:
|xx(1) - X,(11l2 [X,(1)l2 (t)ll
(a) At fixed point: X;- =o[EENO ai WX))
v()(t)) N(N 1)
(b) Feature deviation from leading eigenvector:
Under the conditions from Lemmas 1 and 2:
X
U1
X
(A))
IX"
1N
(A))
(a) There exists an attractor A C NR where:
(c) The spectral gap = 1
)z(A A
bounds pairwise
lim inf [IX(1) Y| = 00 1-900 YEA
differences:
|X - - S (1-7)1X711, Vi,j
(b) The attractor dimension k satisfies:
k < min { d, rannk(o(((")))
(d) Features decompose as X*
X* + E where:
2 Ae(AC) ||
(c) Feature diversity decays geometrically:
| <
m(X(1) S
- (1)
Intuition and Proof Sketch. [The complete proof is given in Suppl. Sec. A] This lemma characterizes how node fea- tures converge the fixed point through spectral analysis
Intuition and Proof Sketch. [The complete proof is given in Suppl. Sec. A] This lemma characterizes how GAT
3

---

A Dynamical Systems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Attention Networks
dynamies lead to feature homogenization through low- dimensional attractor. The key insight is that oversmoothing emerges from both network dynamics and attention matrix properties.
where the second term vanishes due attention weight con- vergence. For perturbations ( = X(t) x", classical
Lyapunov theory gives:
8x + J,(X")XX(0 + R(X()).
(2)
We analyze the attractor set:
where || = ((])xX(()| is the remainder term. The spectral radius condition p()r((X*)) < ensures expo- nential stability, while the kernel analysis:
)²(AA) A = v Y YERRN |Y 1F S (A*)
X ||
where X is the fixed point and A the limiting attention matrix. Convergence to A follows from the contraction property (If f( I c|| Y and attention convergence [[)(() - F + 0. The attractor dimension satisfies:
(I (I-J, ( - 8x, = 5X, Vi, (3)
reveals that stable perturbations must lie in the span of constant vectors, characterizing the oversmoothing phc- nomenon.
& x min rCok((ov(X""),,
}
3. DYNAMO-GAT Algorithm
The DYNAMO-GAA algorithm is a novel approach de- signed to address the oversmoothing problem in attention- based GNNs. counters this by selectively pruning atten- tion weights using a combination of noise injection, covari- ance analysis, Anti-Hebbian principles, dynamic threshold- ing, gradual pruning, and layer-wise pruning rates. The DYNAMO-GAT introduces non-linear perturbations into the system's 's state (node features) and modifies the connec- tivity structure (attention weights) dynamically. This not only disrupts the undesired fixed points associated with oversmoothing but also introduces mechanisms that ensure the system explores richer set of node representations, maintaining diversity across layers.
constrained by ambient dimension, feature correlation, and spectral properties.
Combining contraction and spectral bounds yields:
((X(t)) & (1-2)))u(X(0))
(1--))
revealing oversmoothing as dual compression through net- C
work dynamics and attention mechanisms.
Lemma (Fixed Point Stability). Let f be the GAT update rule with fixed point X and Jacobian (x")"), where a is
continuously differentiable near X". Then:
(a) The Jacobian has block structure:
3.1. Covariance Matrix and Noise Injection
[3,(X) o' d'( if ((jN(())
The covariance analysis directly addresses the low- dimensional attractor problem identified in Lemma 3. By analyzing the correlation structure of node features, detect when the system begins to approach the homoge- neous fixed point characterized in Lemma 1, allowing for targeted intervention through pruning. The first step in the DYNAMO-GAT algorithm involves injecting independent Gaussian noise into the node features at each layer:
otherwise
where hi- EjEN(y X3j
(b) X* is asymptotically stable iff (X))(X")) <1
(c) For small perturbations 6x((), the error evolves
[(x(())lF= S (1 (X)
h = h + og
(4)
(d) Oversmoothing occurs iff:
where c!0) ~ (0, I) represents Gaussian white noise with standard deviation a. This noise perturbs the system state, revealing the underlying correlations between node features through their covariance structure.
(ex(1=)((X"))== = 1n OU:UER))
Intuition and Proof Sketch. This lemma characterizes GAT stability through local lincarization around fixed points, revealing how Jacobian structure drives oversmoothing. At the fixed point, the Jacobian structure emerges from:
The covariance matrix (1)) is then computed as:
:g Cov(h, ( h0)))) = E (h E7th -E
0ʃ. = o' + +o W ax," 0x,
Dai
This matrix captures the pairwise correlations between node features, which are crucial in identifying which connections
(1)

---

A Dynamical Syspems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Attention Networks
(a) Citeseer
(b) Cora
(c) Cornell
10"
10
10
Oversmoothing
[4(X) (log)
10"
10
10"
18"
10
10
10
PLAyETS
107
10
10'
30
16'
10'
90
80
Accuracy
70
59
40
30
20
#Layers
10
20
60
80
100
120
20
40
60
80
100
120
DYNAMO-GAT
G2GAT
GCN
GAT
Figure 2. Comparison of oversmoothing coefficient (μ(X)) and test accuracy across layers for Citeseer, Cora, and Cornell datasets. DYNAMO-GAT consistently outperforms both GCN, GAT and G2GAT maintaining high accuracy across all layers.
(attention weights) contribute to oversmoothing. Nodes with highly correlated features are likely to converge towards similar representations. The covariance matrix measures the system's state coherence. High coherence (correlation) across many node pairs indicates a drift towards a stable, but undesirable, fixed point where oversmoothing dominates. By analyzing these correlations, DYNAMO-GAT can selec- tively target and prune connections that reinforce this drift, thereby altering the trajectory of the system's 's evolution.
pruning. The pruning probability is then computed as:
(1) Pij = -r(())
(C (1) + +CB T 2C
Ttt)
where r(t) the layer-wise pruning rate defined as r(t) To (1 + 7t). This scales with the depth of the layer, al- lowing for more aggressive pruning in later layers where oversmoothing is more likely to occur.
The pruning probability Pij acts as a control mechanism that adjusts the strength and structure of the network's 's con- nections in response to the current state (as reflected by the covariance matrix). By dynamically adapting to the net- work's 's evolving state, DYNAMO-GAN effectively steers the system away from regions of the state space associated with oversmoothing, thus maintaining more robust and diverse set of node representations.
(1)
3.2. Anti-Hebbian Pruning Criterion
The Anti-Hebbian pruning strategy is designed to modify the spectral properties of the attention matrix characterized in Lemma 2. By selectively pruning connections between highly correlated nodes, we effectively increase the spectral gap y which Lemma 2 showed is crucial for maintaining feature diversity. The pruning strategy in DYNAMO-GAT is grounded in the Anti-Hebbian principle, which dictates that connections between highly correlated nodes should be weakened or eliminated. Taking inspiration from recent works on using noise to prune (Moore & Chaudhuri, 2020; Chakraborty et al., 2024), this principle computes the prun- ing probability Pij. which is dynamically adjusted based on a threshold rt)) that adapts to the distribution of edge weights. The dynamic pruning threshold r(t) is defined as:
3.3. Gradual Pruning Process and Update Rule
The gradual nature of our pruning approach aligns with the stability analysis Lemma By making incremental modifications to the network structure, we ensure that the Ja- cobian's spectral radius remains bounded while steering the system away from oversmoothed states. DYNAMO-GAT employs gradual pruning approach, where edge weights are progressively reduced based on the computed pruning probability, rather than being immediately set to zero. This is given by:
(t)
+(1) (([wig)) a(wa)))
where μ and a represent the mean and standard deviation of the edge weights, respectively. This threshold ensures that the pruning process is sensitive to the distribution of edge weights, allowing for more adaptive and context-sensitive
wiy(t +1 (i)(1)
! p.j
(5)
An edge is fully pruned (i.c., its weight is set to zero) only if "nng (t + 1) falls below a small threshold e.
5

---

A Dynamical Systems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Attention Networks
The gradual pruning process introduces continuity into the network's dynamics, allowing the system smoothly tran- sition from one state to another. This contrasts with abrupt changes that could destabilize the learning process. The gradual reduction of weights effectively modifies the origi- nal update rule to pruned update rule Fp, which can be expressed as:
properties while preserving essential features of the original dynamics.
Lemma 5 (DYNAMO-GA) Pruning Properties. Let Fp be the pruned version of GNN transformation F, with pruming rate p and fixed point X". Then;
(a) Spectral radius reduction:
h h(+1) Fr(h"), (0, W C
(6)
p(Jr,(X S (1-
where Fp incorporates the cumulative effects of pruning across layers. This gradual pruning can be seen as a form of perturbative adjustment, where the system is continu- ously nudged towards a more favorable configuration. The incremental changes introduced by gradual pruning helps the system avoid large, disruptive shifts that could lead to suboptimal convergence or loss of critical information.
(b) Under covariance-bass based pruning with Pij r(t)
|asa +(1)
(Ca + Cj F 2C;z):
[A((Fr)) s [Ax(JF) exp (-3 (-3T(C)
Tr(C)
|||||
(c) Spectral gap enhancement:
YP =0=1- (2( 2 p(1-))
3.4. Recalibration of Attention Weights
(1(JFr)
The recalibration step maintains the normalization condi- tions required by Lemma I while preserving the enhanced spectral properties achieved through pruning, character- ized in Lemma 2. Once pruning has been applied, it is essential to recalibrate the remaining attention weights to ensure effective information propagation within the network. This recalibration process re-normalizes the attention coeffi- cients of among the surviving connections:
(d) Rank preservation:
(ank(CooFFF(X)) 2 rank(Cov(X)) <<())
where k(p) S [p- rank(Cor(X))]
Intuition and Proof Sketch. [The complete proof is given in Suppl. Sec. A/ This lemma characterizes how DYNAMO- GAT's pruning affects the network's spectral properties to prevent feature homogenization. The proof analyzes the interplay between pruning and eigenstructure through matrix perturbation theory.
(Lreal) ij
EKEN (1) (Prnne(()) ikc
For edge (i.j) pruned with probability Pij. the Jacobian entries scale as:
where Pruned(1) denotes the set of pruned edges for node i. Recalibration ensures that the information flow in the network remains balanced despite the reduced number of connections. This step is crucial for maintaining the stability of the network's 's dynamics post-pruning, as it prevents any remaining connections from becoming disproportionately influential, which could lead to oversmoothing.
(Jr, = (1 (I=
leading to spectral radius reduction p(JEr, (X*)) 1 (1 p)p(Jr (Xx)). Using the Hadamard product Jrp = JF (1 P) and matrix norm inequalities:
1| < || (-28 Tr(C)) [
3.5. Theoretical Results
where the exponential term reflects covariance-guided prun- ing. Weyl's 's incquality and eigenvalue interlacing give:
Leveraging noise-driven covariance analysis, DYNAMO- GAT introduces stochasticity into the system, preventing the network from settling into fixed points prematurely. This stochasticity is particularly important in deeper networks, where oversmoothing is more likely to occur. The selec- tive pruming mechanism further refines the system's dynam- ics, ensuring that only the most relevant connections are maintained, which aligns with the goal of avoiding low- dimensional attractors. Building on the fixed point and stability analysis from Section 2. we now establish theo- retical guarantees for DYNAMO-GAT's effectiveness in preventing oversmoothing. The following lemmas show how our pruning strategy modifies the network's 's spectral
>2(FFr) $ (1 - p))22 (JF 2 (1 -1- (1-
ensuring monotonic spectral gap increase. The Eckart- Eckart-Young- Mirsky theorem bounds rank reduction as rank(Cov(F>(X)) 2 rank(Cov(XX)) -k().
This reveals how covariance-guided pruning creates con- trolled perturbations that increase spectral gaps while pre- serving rank, effectively preventing convergence to over- smoothed states.
6

---

A Dynamical Systems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Attention Networks
Lemma 6 (DYNAMO-GAT Rank Preservation). Let (() be node features at layer t with covariance matrix:
Table 1. Tahle comparing the different datasets and the number of
GFLOPS for each model for each dataset
1 C(I) N x()x(()) N' X(0
Metric
Citeseer
Cornell
Nodes (N)
2,708
3,327
183
N
Models
Edges (8)
5,429
4,732
280
Avg. Degree (2) F1/NND)
4.01
2.84
3.06
Best Accuracy
81.5
75.7
54.2
Under DYNAMO-GAT's noise injection and pruning:
*Layers
GCNoKip & Welling, 2017)
GFLOPS
0.598
L.789
0.049
Accuray/(FFLPSS
1106.12
(a) feiise-petuubeddeeee features (t) ((t)))((()) E(t)
Best Accuracy
82:55
76.1
56.3
NO0 I) satisfy:
Voliviii at al,, 2018)
*layers
GFLOPS
2.351
6.754
0.184
Accumay/CiFL.PP
35.11
11.27
306.52
rank (ank(C(X(t)))>>>>
Best Accuracy
83.27
K2,06
61.55
G2GATiRusch 2023u)
*Layers
128
128
128
GELOPS
1.209
2.452
0.0879
with probability 1
Accurac//GFLors
68.88
33.47
700.34
Best Accuracy
83.21
82.01
62.56
(b) Pruning preserves rank as:
DYNAMO-GAT
*layers
128
128
128
GFLOPS
0.605
L.675
0.051
rank(C(X(1 + 1))) 2 rank(C(X(())) -(()
Accmmcy/GPLLOS
137.53
48,96
1226.67
where k(t) counts eigenvalues below c(t)
4. Experimental Results
(c) For noise level > O:
Amin (C(t)) 2 o² ) -((((
1
4.1. Experimental Setup
We conduct experiments on three real-world and two synthetic datasets. We use Cora (McCallum et al., 2000), Citeseer (Sen et al., 2008), two citation networks, and Cornell (University) which is part of the WebKB collection.
Datasets:
(d) Under threshold r(t) u((wer) )) + B o(wwiy)) (), rank is preserved w.h.p. if:
loo(d//)
Baselines: We compare DYNAMO-GAT with GCN (Kipf & Welling, 2017), GAT (Veličković et al., 2018), and G2GAT (Rusch al., 2023a), focusing on their effectiveness in preventing oversmoothing.
B 2
N
Intuition and Proof Sketch. [The complete proof is given in Suppl. Sec. A/ This lemma establishes how DYNAMO- GAT's dual mechanisms- noise injection and adaptive prun- ing - preserve feature diversity. The proof leverages matrix perturbation theory to analyze covariance spectrum evolu- tion.
Models are evaluated using Accuracy, Oversmoothing Coefficient (p) (Wu et al., 2023), GFLOPS, and the Accuracy/GFLOPP ratio to gauge the trade-off be- tween performance and computational cost.
Evaluation Metries:
For noise-perturbed features, the covariance decomposes as:
4.2. Performance on Real-World Datasets
C(X(1) = -((()) 0² (1
Figure illustrates the performance of DYNAMO-GAT, G2GAT, GCN, and GAT across three worl-world datasets: Citeseer, Cora, and Cornell. The top row shows the over- smoothing coefficient (n(X) log scale, while the bot- tom row displays the test accuracy the number of layers increases.
+ N (X(1 E(O)x(()).
where the middle term ensures full rank through its positive definiteness. Under pruning with mask P(t):
[|C(((++ 1)) - c(X())lla < [P(()]l2maxx ((()))))aax(((((())) (C))
Oversmoothing Coefficient (μ(X)) [Figs. 2(a.b)]: The re- sults demonstrate that GCN and GAT suffer from significant oversmoothing as the number of layers increases. Their over- smoothing coefficients decrease rapidly, indicating that node features become increasingly indistinguishable. G2GAT per- forms better by reducing the rate of oversmoothing, but it still shows a downward trend as layers increase. In contrast, DYNAMO-GAT maintains a nearly constant oversmooth- ing coefficient across all layers, effectively preventing this phenomenon. This stability suggests that DYNAMO-GAT preserves meaningful node representations even in deep
(8)
Weyl's interlacing thcorem then bounds rank reduction by x(t). Matrix concentration gives:
Amin (C(()) 2 o² (1 (1- (() (9)
ensuring cell-conditioned features. The adaptive threshold
T(t) with B 2 / 2log(d/8) maintains rank preservation with probability 5 through eigenvalue separation.

---

A Dynamical Systems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Attention Networks
architectures.
ers increase, maintaining higher pxX) compared other models. This indicates DYNAMO-GAT's robustness in preserving node features even in deep networks.
Test Accuracy [Figs. 2(c,d)): The test accuracy results align with the oversmoothing observations. GCN and GAT experience sharp decline in accuracy as the number of lay- ers increases, reflecting the negative impact of oversmooth- ing on model performance. G2GAT performs better, with a slower decline in accuracy, but still struggles as the network depth increases. DYNAMO-GAT, however, consistently achieves the highest accuracy across all datasets and depths. Its ability to maintain high accuracy even with many lay- ers indicates that it effectively balances expressivity and resistance to oversmoothing.
(b) Accuracy vs. Layers (Avg. Degree = 68.75):
DYNAMO-GAT consistently achieves the highest accuracy across all layers, outperforming G2GAT, GCN, and GAT. This demonstrates its effectiveness in managing deep archi- tectures without performance degradation.
(c) Accuracy vs. Homophily (Avg. Degree = 11.93): In sparse graphs, DYNAMO-GAT and G2GAT perform well across all homophily levels, with DYNAMO-GAT showing stronger performance as homophily increases. This high- lights its adaptability in different homophily settings.
These observations underscore the challenges of using deep GNNs in practical applications, where oversmoothing can severely degrade performance. The consistent performance of DYNAMO-GAT across different datasets and network depths suggests that it is robust solution for deep GNNs, addressing a critical limitation of existing models. This makes DYNAMO-GI require deep networks without sacrificing accuracy or node representation quality.
(d) Accuracy vs. Homophily (Avg. Degree 68.75): In dense graphs, DYNAMO-GAT significantly outperforms other models, particularly in low-homophily settings, show- casing its strength in complex, heterophilic structures.
particularly suitable for tasks that
(o) Aug. Degroe-68.75
(b) Aug, Mede Dogree-58.77
Overzmoothing
10a
4.3. Performance Comparison Across Datasets
(530) (log)
100
9.4
Table 1 compares the performance of DYNAMO-GAT,
0.4
G2GAT, GCN, and GAT across three datasets: Cora, Cite-
seer, and Cornell. The table highlights key metries such as best accuracy, the number of layers, GFLOPS, and the accuracy-to-Gie GFFOOOS ratio.
1.0
(c)
#Layers Degrot--1:995
[d)
Kode Degree-s60.75
0.5
Accuracy
0.0
Best Accuracy: DYNAMO-GAT consistently achieves the highest accuracy across all datasets, particularly excelling on the Cornell dataset with 62.56%. This demonstrates its robustness in deep architectures.
Z0.7
0.
0.4
0.
5.3
0.
6.8
1.0
9.4
Homophly
Hamophily
DYNAMO-GA GAT
G2GAT
GCN
GAT
GFLOPS:
Despite its deep architecture (128 layers), DYNAMO-GATI is computationally more efficient than GAT and G2GAT, with significantly lower GFLOPS, especially on larger datasets like Cora and Citeseer.
Figure 3. Performance of DYNAMO-GAT, G2GAT, GCN, and GAT on the Syn_Product dataset. (a) Oversmoothing vs. layers: DYNAMO CANAMO-GATAOO shows the least oversmoothing. Comparing test accuracy (b) vs. number of layers (c) vs. homophily for sparse graph (Avg. Degree=11.99 (d) vs. homophily for dense graph (Avg. D8gree=68.75)
Accuracy/GFLOPS Ratio: DYNAMO GAT outper- forms all models in the accuracy-tor toii--tt-GLLLPP
GFLOOSS ratio, in- dicating the best orf between accuracy and com- putational cost. For example, on Cora, it achieves 137.53, compared to GCN's 136.28 and GAT's 1..
Summary: DYNAMO-GAT consistently outperforms other models preventing oversmoothing and maintaining accuracy. Its efficiency, as highlighted by the accuracy -to- GFLOOSS ratio, makes it suitable for real-world applications where computational resources are limited. The model's 's ver- satility across graph densities and homophily levels suggests it is well-suited for a range of tasks, from social network analysis to biological network modeling.
4.4. Synthetic Dataset Results
Figure 3 presents the performance of DYNAMO-GAT, G2GAT, GCN, and GAT on the Syn_ Produrrssstsss dataset, tested across varying node degrees and homophily levels.
(a) Oversmoothing vs. Layers (Avg. Degree = 68.75): DYNAMO-GAT exhibits the least oversmoothing as lay-
8

---

A Dynamical Systems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Attention Networks
Table 2. Performance Comparison on OGB Datasets. DYNAMO-GAT shows strong scalability and efficiency.
Dataset
Model
Accuracy (%)
GFLOPS
Accuracy[GFLOPS
ogbn Sebnnarxiiv
GCN
71.9
12.5
5,75
ogbn-arxiv
G2GAT
72.5
10.3
7.04
ogbn-arxiv
DYNAMO-GAT
72.1
6.7
10.76
ogbn-products
G2GAT
73.9
22.1
3.34
ogbn-products
DYNAMO-GAT
75.3
14.5
5.19
4.5. Scalability and Performance on Larger Graphs
ablation study on the Cora and Citeseer datasets. We system- atically removed modified: Noise Injection, Covariance- based Pruning, Adaptive Thresholding (replacing it with fixed threshold), Gradual Pruming (replacing it with aggres- sive pruning), and Attention Recalibration.
To address the important question of scalability and per- formance on larger, more diverse graphs, we extended our evaluation to include benchmarks from the Open Graph Benchmark (OGB) (Hu et al., 2020b) specifi- cally ogbn aariiv (a large-scale homophilic citation net- work) and ogbn-products (a large-scale heterophilic product co-purchasing network). We also tested on LRGB datasets. We compared DYNAMO-GAT against GCN and G2GAT. The results, summarized Table 2, demonstrate that DYNAMO-GAT scales effectively graphs with hun- dreds of thousands of nodes.
The results, presented in Table 3, demonstrate that all com- ponents are critical for achieving optimal performance and mitigating oversmoothing. Removing any part leads to a noticeable drop in accuracy and an increase in the over- smoothing coefficient (lower (xX) values, indicating worse performance), confirming the synergistic effect of our de- sign choices. Notably, removing covariance-basee pruning had the most significant negative impact.
Crucially, DYNAMO-GAT achieves competitive or supe- rior accuracy while requiring significantly fewer GFLOPS, leading to a much better Searaacytt-GFLLOO ratio. For instance, on aebbn-axxiv DYNAMO-GAT achieves an Accuracy/GFLLPS ratio of 10.76, compared G2GAT's 7.04. On ogbn products, it achieves 5.19 compared to G2GAT's 3.34. These findings confirm the robustness and efficiency of our approach on large-scale graphs, including those with heterophilic structures.
5. Conclusion
This paper introduced DYNAMO-GAT, novel approach using dynamical systems theory and noise-driven adaptive pruning to mitigate GNN oversmoothing, We provided rigorous theoretical guarantees and demonstrated strong ex- perimental performance on both benchmark and large-scale datasets (Hu et al., 2020a), confirming DYNAMO-GAT's effectiveness, scalability, and computational efficiency. The results suggest DYNAMO-GAT well-suited for real-world applications requiring deep GNNs, and its mechanism may enhance model interpretability. While acknowledging po- tential limitations, such as in extremely sparse graphs, future work will target domains like physics/chemisty and extend to graph-level tasks.
Furthermore, we evaluated DYNAMO GAT in inductive set- tings using OGB benchmarks, where it again achieved com- petitive accuracy with enhanced computational efficiency (up 55% improvement Accuracy/GFLOOSS This con- firms its suitability for scenarios where the model must generalize to unseen nodes.
In summary. our dynamical systems perspective offers powerful, arcoretically-grounde solution oversmoothing. paving the way for more robust, efficient, and expressive deep learning models for complex graphs.
Table 3. Ablation Study Results on Cora and Citeseer. All compo- nents contribute to performance.
/ / Variant
Accuracy (%)
OS Coeff. p(X)
Cora
Citeseer
Cora
Citeseer
Full DYNAMO-GAT'
83.21
82.01
0.57
0.62
Noise Injection
81.54
80.26
0.45
0.52
Impact Statement
Covariance- based Pruning
79.32
77.15
0.36
Adaatiie Thresholding
80.67
79.52
0.38
0.41
This work advances Graph Neural Networks through theoret- ical insights and practical improvements. While the primary contribution is technical in nature, our more efficient ap- proach (shown by better to-uaac ratios) could reduce computational costs and energy consumption in AI applications. The improved preservation of node feature diversity may also lead to more reliable outcomes in critical
Gradual Pruning
80.14
78.93
0.34
0.39
AAttention Recalibration
79.78
78.41
0.35
0.40
4.6. Ablation Study
To understand the contribution of each key component within DYNAMO-GAT, we conducted comprehensive

---

A Dynamical Systems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Attention Networks
applications like molecular modeling and social network analysis.
istry. International Conference on Machine Learning, pp. 1263-1272,
Hu, W., Fey, M., Zitnik, M., Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovee, J. Open Graph Bench- mark: Datasets for Machine Learning on Graphs. In Larochelle, H., Ranzato, M., Hadsell, R., Bal- can, M. F, and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 22118- 22133, 2020a. URL
Acknowledgement
The materials are based on work supported in parts by SRC JUMP2.0 (CogniSense Center, 2023-JU-3133) and Army Research Office (Grant Number W91 (--F-19---0447)) Any opinions, findings and conclusions or recommendations pressed in this material are those of the author(s) and do not necessarily reflect the views of SRC or Army Research Office.
neurips. neurips.c wwtppcpppppppccccccccccceeeeeeee httpp/aaprr/200/f1eel
pdf. (For OGB datasets used in rebuttal/new experi- ments [cite: 70, 93, 110, 130, 174, 2051).
References
Abbe, E., Fan, J., Wang, K., and Zhong, Y. Entrywise eigen- vector analysis of random matrices with low expected rank. The Annals of Statistics, 48(3): 2020.
Hu, W., Fey, M., Zitnik, M.. Dong, Y., Ren, H., Liu, B., Catasta, M., and Leskovec, J. Open Graph Benchmark: Datasets for Machine Learning on Graphs. In Advances in Neural Information Processing Systems, volume 33, pp. 221 22118-22133, 2020b.
Allen-Zhu, Z., Li, Y., and Song, Z. Convergence rates of neural networks for supervised learning manifolds. In Advances in Neural Information Processing Systems, pp. 6191-6201, 2019.
Ioffe, S. and Szegedy, C. Batch normalization: Accelcrating deep network training by reducing internal covariate shift, In International conference machine learning, pp. 448- 456. PMLR, 2015.
Ba, J. L., Kiros, R., and Hinton, E. Layer normalization. In arXiv preprint arXiv:1607.06433 2016.
Jin, Y. and Zhu, X. Graph Rhythm Network: Beyond Energy Modeling for Deep Graph Neural Networks. In 2024 IEEE International Conference on Data Mining (ICDM). IEEE, 2024.
Cai, C. and Wang, Y. A note on over-smoothing for graph neural networks. In ICML Graph Representation Learn- ing and Beyond (GRL+) Workshop, 2020.
Chakraborty, B., Kang, B., Kumar, H., and Mukhopadhyay, S. Sparse spiking neural network: Exploiting heterogene- ity in timescales for pruning recurrent snn. arXiv preprint arXiv:2403.0 03409, 2024.
Keriven, N. Not too little, not too much: theoretical analy- sis of graph (over)smoothiing In NewrlPS, volume 35, pp. 2268-2281, 2022.
Kipf, T. and Welling, M. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Chen, M., Wei, Z., Huang, Z., Ding, B., and Li, Measur- ing and relieving the over-smoothing problem for graph neural networks from the topological view. Proceedings of the AAAI Conference on Artificial Intelligence, 34(04): 3448-3445, 2020.
Li, G., Muller, M., Thabet, A., and Ghanem, B. Deep- gens: Can gens go as deep as cnns? Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 9267-9276, 2019.
Di Giovanni, F., Rowbottom, J., Chamberlain, B. P., and Bronstein, M. M. How does over-squashing affect the power of gnns? arXiv preprint arXiv:2306.03588 2023.
Li, Q. Han, Z.. and Wu, X.-M. Deeper insights into graph convolutional networks for semi-supervised learning. Pro- ceedings of the AAAI Conference Artificial Intelli- gence, 32(1), 2018.
Fan, W., Ma, Y., Li, Q., He, Y., Zhao, E., Tang, J., and Yin,
D. Graph neural networks for social recommendation, In The world wide web conference, pp. 417-426, 2019.
McCallum, A., Nigam, K., Rennie, J., and Seymore, K. Au- tomating the construction of internet portals with machine learning. Information Retrieval, 3(2): 2000.
Gasteiger, J., Becker, F., and Günnemann, S. Gemnet: Uni- versal directional graph neural networks for molecules. Advances in Neural Information Processing Systems, 34: 6790-6802, 2021.
Moore, E. and Chaudhuri, R.
Using noise to probe recurrent neural network structure and prune synapses. Advances in neural information processing systems, 33:14046-1400 14057, 2020.
Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., and
Dahl, G. E. Neural message passing for quantum chem-
10

---

A Dynamical Systems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Attention Networks
Mustafa, S., Lachi, V.-A., Velickovic, P., Deac, A., Nils- son, S., Cucurull, G., Lio, P., Blais, F.-D., and Bengio, Y. GATE: How Keep Out Intrusive Neighbors. In Proceedings of the 38th International Conference on Ma- chine Learning, Proceedings of Machine Learning Re-
Wu, X., Ajorlou, A., Wu, Z., and Jadbabaie, A. Demys- tifying oversmoothing in attention-based graph neural networks. Advances in Neural Information Processing Systems, 36, 2024.
Wu, Z.,, Pan, S., Chen, F., Long, G., Zhang, C., and Philip. S. Y. A comprehensive survey on graph neural networks. IEEE Transactions on Neural Networks and Learning Systems, 32(1):4-22) 24, 2020.
search. PMLR, 2021.
Oono, K. and Suzuki, T. Graph neural networks exponen- tially lose expressive power for node classification. In ICLR, 2020.
Xu, K., Li, C., Tian, Y., Sonobe, T., Kawarabayashi, K.- i., and Jegelka, S. Representation learning on graphs with jumping knowledge networks. Proceedings of the 35th International Conference on Machine Learning, 80: 5453-5462, 2018.
Reiser, P., Neubert, M., Eberhard, A., Torresi, L.., Zhou, C., Shao, C., Metni, H., van Hoesel, C., Schopmans, H., Sommer, T., et al. Graph neural networks for materials science and chemistry. Communications Materials, 3(1): 93, 2022.
Ying, R., He, R., Chen, K., Eksombatchai, P., Hamilton, W. L.,, and Leskovec, J. Graph convolutional neural net- works for web-scale recommender systems. Proceed- ings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 974-983, 2018.
Roth, A. and Liebig, T. Simplifying the theory on over- smoothing. arXiv preprint wxXiv:2407.11876 2024.
Rusch, T., Bronstein, M., and Mishra, S. Gradient gating for deep multi-rate learning on graphs. International Conference on Learning Representations, 2023a.
Zhao, J., Park, D., Zhang, S., Lee, L.., and Yan, C. Sparsity preserving low-rank decomposition for compression of deep networks. In Proceedings of the IEEE/CVF Con- ference on Computer Vision and Pattern Recognition, pp. 12132, 2020.
Rusch, T., Bronstein, M. M., and Mishra, S. A survey on oversmoothing in graph neural networks. ArXiv, abs/2303. 10993, 2023b.
Rusch, T. K., Bronstein, M. M., and Mishra, S. Graph- coupled oscillator networks. In International Conference on Machine Learning, pp. 18888-18909, PMLR, 2022.
Zhou, K., Huang, X., Li, Y., Zha. D., Chen, R., and Hu, X. Towards deeper graph neural networks with differentiable group normalization. Advances in neural information processing systems, 33:4917-4928, 2020
Sen, P., Namata, G., Bilgic, M., Getoor, L., Galligher, B., and Eliassi-Rad Rad, T. Collective classification in network data. In Al Magazine, volume 29, pp. 93 93-93,2222 2008
Zhu, J., Yan, Y.. Zhao. L., Heimann, M., Akoglu, L.. and Koutra, D. Beyond homophily in graph neural networks: Current limitations and effective designs. Advances in neural information processing systems, 33:7793-7804, 2020.
Spielman, D. A. and Srivastava, N. Graph sparsification by effective resistances. SIAM Journal on Computing. 40(6); 1913-1926, 2011.
University, C.
Webkb dataset.
URL http:
//www. cs. cmu. www.ccu.eeeeeeee. af/cs...c.sss cmu. edd/ project/theo--e 20/ wwwpww////wwwwwwwot//////ttwh/hh /dtp/d 2024-08-16.
Accessed:
Velickovic, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. Graph attention networks. In International Conference Learning Representations, 2018.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. Graph attention networks. In ICLR, 2018.
Wu, F., Gomez, A., Tian, Y., Qiu, J., and Tang, J. Demysti- fying the weak performance of graph attention networks. International Conference on Learning Representations, 2023.

---

A Dynamical Systems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Attention Networks
(a) The mapping f a contraction in the Frobenius norm with constant c = [|]]|2[1 + K) 1.
Table 4. Summary of Notations
Notution
Description
(F)
Node feature matrix at layer where N the number of nodes, und 1s
(b) There exists a unique fixed point X E RRd such that X f(X)).
the feature dimension.
kz(0)
Festure vector of bode's i layer representing the i-hh row of XiC;.
Og (1)
Attention weight between nodes s and at layer i, salistying
Ejexta (ty() 1.
(c) For any initial state X(0), the sequence (X(t)) con- verges geometrically to X with rate:
A(5)
Attention matrix layer f. with entries (A()), auy(t)
Activation Tunction that is -ippiicc continous with for <.1. o()
Leurnable weight matrix 205d spectral norm |[W]
Spectral gap of attention matrix, defined as 7 Agt2 where
[x((t) - - I d( XXI1s-
A and bn the largest and second lugest eigenvalues of 4".
(()(O)
Oversmoolhing coefficient, quantitying (eature diversity al layer i 16,10 6,00,
HC (() XTV=13 Zopt; leytti
(d) The attention weights converge fixed values az with rate:
Maximum number of eigenvalues below the pruning threshold c(t) in the covariance matrix.
r(B)
Layer wise praning rate. defined as r(t) io +1+
7()
Dynamic pruning threshold, defined r[t] - p([ B a(fw))), ).
(aig(t)-aijla S si ('))) - X'I,,,
where a and a represent the mean and standard deviation of odge weights respectively.
C())
Covariance
of node features layer defined Cy(t)
and satisfy:
Cov(hu(t).. (,(().
G(0)
Gaussian added
features layer where (:0)) ().
M |atz 1-c JEN()
Jacobian of the update nale / ovaliusted the lixed point X",
Σ
(lG(X*") })
Spectral radias of the Jacobian ly")")
P(9)
Pruning mask applied
artention
layer
A(())
--th cigenvaluc of the covariance matrix C.
Leading eigenvector
fixed-point attention marrix
Proof. The proof proceeds in four parts, establishing the contraction property, existence of a fixed point, convergence rate, and attention weight convergence.
Residual term the spectral dccoposiiion of X" quantifying deviation
from the leading cigenvector component.
6. Supplementary Section A: Theoretical Proofs
(a) Contraction Property: Consider two consecutive states X(t) - 1). For any node i E V:
6.1.Notare Notations
x2(0122
=1lo( Σ (i)())Wx((())
6.2. Lemma
JEN())
Lemma (Existence and Properties of GAT Fixed Points).
Let G = EV be a graph with N nodes. Consider a Graph Attention Network (GAT) with an update rule f R
al Σ
aky(1 - (1, 1))ll2
JEN(1)
Nxd where the feature update for each node i E V is given
< Lo
Σ JEN(()
-=0(000((0000000000000000000 1)W 1)]1l2.
where the inequality follows from the L.p-Lipshhizz property of o. Adding and subtracting (t) (t))WttWtt+ 1):
1)( s(X.0)) = Σ a.s());()))
JEN()
< Loll Σ axy(t)((Xx(t)) - X,(t 1)) JEN())
where:
Σ (asg(t) -ij(t 1)) 1)ll
IRd + Rd is Lo Lipschittz continuous with Lg S 1.
JEN(1)
We e dddd has spectral norm ||W]|2 < I+K
1
Σ ai)())(x(()) - 1))ll2
x,((-1))
The attention mechanism a d x Rd + R satisfies:
JEN(1)
11 JEN())
(a:)(1) - (t 1)]la). (10)
- aas(()) 2 0. EjEN(O (t) 1 (normaliza- tion).
-
-Ilass(() (1= S Xx((())x((1---) for some K (Lipschita property).
where we used |||| < and the triangle inequality. By the attention normalization condition Σjev() any =
maxi, (laz)(t)l2 S. M for some M > 0 (bound- edness).
and the Lipschitz property of attention weights:
$ LL - X(t 1)ll2
Then:
+KIX(11 - 2)
(11)
12

---

A Dynamical Syspems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Attention Networks For the matrix-level bound:
6.3. Lemma 2
Lemma 2 (Structure and Spectral Properties of GAT Fixed Points). Ler G (V, be graph with N nodes and let X RNxd be the fixed point established in Lemma 1. Define the fixed point attention matrix A E NNN with entries [A" 0 for j E (i) and 0 otherwise. Then:
-1--11-X(011 Σ [1((+ -
< <Loo|W/la(1 ( X(t - 1)
Therefore, f is a contraction mapping with constant c L. [ K) < 1.
(a) At the fixed point, for any node i:
(b) Fixed Point Existence: Since (IR Nxd Il (|F) is com- plete and f is a contraction mapping, by the Banach Fixed-Point Theorem, there exists a unique fixed point X E R xxd such that X = f(X*). The boundedness of iterates follows from:
X =a
Σ (EN(
Wi
(b) Let (1 and in be the largest eigenvalue and corre- sponding eigenvector of A", Then:
(t + F) 2 (Ix
(()l +| + |[(()) (12)
11os x'
S (2
X
Ai(A-) ||
where [[]]] is finite due to the properties of a and W.
(c) Convergence Rate: At the fixed point X
where (2(A") is the second largest eigenvalue of A"
(c) The spectral gap y 1 Aa(A") mogenization through: X1(A-)
controls feature ho-
[X((+1) | (I)(X(()) f(X))le S c() ll..
(13)
|X - (1->) Vi,j
By induction, for any t -
(d) The node features decompose as:
- - (()) l'
(14)
U1 X + E
X*
establishing geometric convergence with rate
IIIN
(d) Attention Weight Convergence: By the Lipschitz prop- erty of the attention mechanism:
where the error term E satisfies:
| W (2((Ar) 2
(1())) ||*||e
(t + 1) - (t)ll)
< (t] + -) xx)()l2 (c -(0))]
(e) For any > 0, i then there exists vector Id such that:
The sequence {1)} is Cauchy since:
|X - INu IF VelxX"Ie
(1as)()) - ac)()) <
lan (k + +1 -a:s())s)lee 12)
(f) The covariance matrix of node features the fixed point satisfies:
k=
(I) X(O) Σ dk
rank(Cov(X*)) S raakk[ (I 8 il
k=
+1
1N
K XII X(0)
(15)
1 1-c
Proof. Preliminary Definitions and Sctup: Let
(V, E)) be a graph with N nodes and let X E Nxd be the fixed point. Let A" be the fixed-point attention matrix where [A"]e at for Niii) and 0 otherwise. Note that A is row-stochastic by construction.
Therefore, (1))()) converges to some oty Using the trian- gle inequality and normalization:
Σ |a 1 (1)
X
(16)
Part (a): Fixed Point Characterization
1-c
1 1
JEN())
First, we establish that the fixed point condition is well- defined:
13

---

A Dynamical Systems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Attention Networks
1) At convergence, by Lemma 1, the sequence {X(1) con- verges to X* and (4))(!) converges oty.
This establishes the bound in part (b).
Part (c): Feature Homogenization Analysis
2) By continuity of a and the update rule:
1) For any pair of nodes i.j, consider their feature difference:
X = lim + (1)
1000
| - -xií1= = 1oo{
Σ
a
w
KEN())
= lim o 1000
Σ (EN(O)
asy a05(0)(((0)
o Σ
||2
(eV()
Σ JEN(S
2) Using the Lipschitz property of a:
S Loll Σ REN(()
W
Σ
W
ll2
Part (b): Spectral Approximation
LENU)
= Lo] - A-W'-1>
1) First, observe that A is row-stochastic and non-negative. By the Perron-Frobenius theorem: > (A") is real and pos- itive - (Ar) I X (A*) for all 2 2 - The corresponding eigenvector U1 can be chosen to be positive
where e; is the i-th standard basis vector.
3) Using the spectral decomposition of A and the fact that Lo < 1:
2) By the Spectral Theorem, A" has orthogonal decom- position:
U1U W WX 2/2
|| Xilla S I1eeT" - (A5 (Ar)
N A" = Σ \A
1N
(17)
$ ||e - -e 11211A1-
where [ form an orthonormal basis.
A1
of 1N
3) The fixed point equation can be written matrix form:
4) Since ||e, - og 12 = v2 and | 12 S 1:
X' ='AWX"
(18)
|X - X21l2 < (1 - -->||||X>> ||
4) Using the Ln-Lipschitz property of a and the fact that Lo < 1:
Part (d): Feature Decomposition Analysis
1) Start with the spectral decomposition of A
||X AWX [|o(A" - A
Lo L
N
A = A
< ||
IN
5) Therefore, locally around the fixed point:
2) The node features can be decomposed as:
X X
(19)
2ars x
(1-
X
X
1N
of
1N
6) Applying the spectral decomposition:
3) Define the residual term:
(A((A))
X ~
IN
+
WX
E
U1 i
x*
1N
N Σ
Tn = -Ar
WX
4) Using the orthogonality of eigenvectors:
If
1=2
| tr(EETT E)
7) By the Davis-Kahan Kahan theorem and matrix perturbation theory:
Tale x²x*)
=rr(X*
u IN
220(4)) /11x"11
U1
Viu
)²(AA) (1(A))
s (1(A4))
X
X
<
|X*||
(20)
1N
14

---

A Dynamical Systems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Attention Networks
Part (e): Uniform Feature Approximation
where dist( AA) -infye | Y
1) When y > 1 - 6, we have AA(A")
(A <. E.
(b) The attractor A has intrinsic dimension k bounded by:
k S min { {d, rann((ov((")))
2) Define
Then:
of 1N
|X -NN0"
P ||
2121 X
X 1Nv T
where r is the spectral gap from Lemma
of IN
of 1N
(c) The feature diversity measure decreases geometrically with rate determined by both the contraction constant and spectral gap ny:
$ ||
"f IN
S Ile
(xx(t)) S
Part (f): Covariance Rank Analysis
(d) At convergence, the feature diversity measure is bounded by:
1) The covariance matrix is defined as:
lim m(X(I)) S X²(A4) ||*I
Cov(X*) X (I I
X
b-
(1 2 min; |X
N
(e) The covariance matrix of the node features evolves ac- conding to:
2) Using the feature decomposition from part (d):
())
yaoa Cov(X")lle & ([-))\][Co[(((()))]
(C)) I
i N of 1N
1v T N
V
X + EI
X + E)
N
Uj 1N
(f) The eigenvalues of the covariance matrix satisfy:
1 T
ET E N
E
{((Cov(((D)) = >2((A²)
(1(A-)) {((Cov((())),,
3) By rank properties:
for all i i>l.
Lale
rank(Cov(X")) < rank(I
+
First, recall that by Lemma we have contraction mapping with constant and unique fixed point X From Lemma 2, we have spectral properties of the attention matrix A with spectral gap 7 Aa(A")
Proef. Preliminaries:
of 1N
This completes the detailed proof of all parts of Lemma 2.
Part (a): Existence of Compact Attractor
Let define the attractor set A:
6.4. Lemma 3
A2(Aa) (A ||x |X*1||
A Y R Nxd || -
Lemma 3 (Characterization of Oversmoothing Attractors in GATS). Let X(t E Nxd represent the node features at layer I in GAT. Define the feature diversity measure at layert as:
Hence, we show A is compact:
Closed: is the preimage of a closed interval under a
continuous function
((X(t)) N(N
1
(x,(t) - Xtyll IX,(0)a (012
Bounded: ||Y|| ||X*|1((1+ Az(A)) Xi(Ar) for all Y E
We prove convergence to A:
Let A(t) E N be the attention matrix at layer t. Then, under the conditions from Lemmas 1 and the following statements hold:
dis)(X((), = inf [|x - 1|
YEA I [|x(()) 11
(a) There exists compact set A C I Nxd such that:
I <o((((()) - X- 0s a
lim dist( ((1), A) = 0,
Part (b): Attractor Dimension Bounds
t-000
15

---

A Dynamical Systems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Attention Networks
Direct consequence of A RRxxd
Thus, the lower bound node norms convergence:
By construction, features cannot span more dimensions than d
X ll 2 min | 2| > 0
where positivity follows from the non-degenerate fixed point.
LLtt C* = Cov(X*) be the covariance matrix at the fixed point
Finally, we combine to bound limiting diversity:
For any Y E A:
1
|X; -Xi122
lim ((X(t)) 70000
(21)
rank(Cov(Y))) S rank(C")
N(N
1)
| 1l + 1|xI112
itj
A²(A1)
||1
Proof: Use SVD of (Y - X*) and bound perturbation of cigenvalues
(Ar)
2 min; ||
(22)
Part (e): Covariance Evolution Analysis
From Lemma 2, the spectral gap y controls feature similarity
Expressing covariance matrix evolution:
1 Cov(X(t)) = N x(t)x((1) - N2 Ix
For any orthonormal basis {ui} of the attractor space:
(23)
Σ (1 7) <
Decomposing using eigenvectors of A
X(t) = 01 o X + E(t)
(24)
This implies
of 1x
|| |E(I|L= S - (1x)
(25)
Part (c): Feature Diversity Decay
Analyzing pairwise distances using contraction property, we get
Hence, analyze covariance deviation:
[[Cov(X(t)) 21 2aoe Cov(X*)ll= 27 IN
(26)
1t) (t - 1)ll2 (I((x(()) ((X)())) S d||x((t) - (t(1)l22
$ E(t)]) + 21
X E(t)
(27)
IIN IN
Hence, using spectral bound from Lemma 2:
s (1 (1-n))(Co(XX())))
(28)
[tx,(t) X s (1 ( (
Part (f): Eigenvalue Analysis
Combining bounds for feature diversity measure:
Expressing eigenvalue evolution using matrix perturbation theory: For > 1, let ut(t be the i-th eigenvector of Cov(X(()):
(t, (t)ll
((((t)) = N(N - 1) ifj
(x,(0)2 (0)
((C) (o))))))))))))))))) (29)
I (
Applying spectral decomposition of A*:
Part (d): Convergence Analysis of Feature Diversity
{((ov((((t))
(30)
First, we analyze limiting behavior of pairwise distances: For any nodes i at the fixed point X
1A (CCv((())))
(31)
(22(Ar) 2
|X - Xi112 = Σ
a Wi.W
Σ kEN())
(A((A)) {((Cov(((0))
(32)
kEN(
|| |22ll
(a - X2l2
By induction on t, show that for all i > 1:
(>e(A")
(A
A((ovvX((t+ 1)))
{c(Cov(X(t)))
||x"||1
(x((at)
>1
(33)
16

---

A Dynamical Systems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Attention Networks
The base case follows from spectral properties of A*
Proof. Before proceeding with the proof, establish some
key definitions and properties:
The inductive step uses the GAT update rule and eigen- value interlacing
1. The GAT update rule f Rxd - R Nxd at node is:
This completes the proof. showing that GATs exhibit expo- nential convergence low-dimensional attractor, charac- terized by rapidly decaying feature diversity and covariance eigenvalues. The rate of convergence is controlled by both the contraction constant and the spectral gap ? of the attention matrix.
f(X)= =0
ai wxy JEN(()
Σ
2. At the fixed point X
= =a
Σ ai.
JEN(()
Corollary 0.1 (Oversmoothing Rate). The rate of over- smoothing is controlled by the contraction constant and the network depth l:
Part (a): Jacobian Structure
First, we compute the partial derivatives For j E EV))::
(t) =
where 6 = min c}. This quantifies how quickly node features collapse to indistinguishable values as the network deepens.
0f: a ax, ax,
Σ aikk W kEN(()
dask ox,
=o'(
oiyW
Σ
X:W
6.5. Lemma 4
REN(
Lemma 4 (Stability Analysis of GAT Fixed Points). Let f: Nxd + R xd be the GAT update rule with fixed point X E Nxd, Let (X)))) denote the Jacobian of f at X".
fixed point X", the attention weights have converged (from Lemma 1), so:
Then:
dock 0x,
(a) The Jacobian (X*)) has the block structure:
o' (h())a if E()
Therefore:
[3 =
0
otherwise
(J((X)) d'Ht)ajj e
where hū- EJEN(O) Oiy WX;
otherwise
(b) The fixed point X* is asymptotically stable and only if:
Part (b): Stability Criterion
p(J{("") <1,
Consider perturbation 8X X X* By Taylor expansion around X":
where pl-) denotes the spectral radius.
(c) For any perturbation 8X (0), the error evolution fol- lows:
f(X) -0--1 where
-x*)
-
[0x(0)I= S
At fixed point:
s(x*= = X*
(d) At a stable fixed point, the attention weights satisfy:
Σ 1o'(k)o,,,lle JEN())
The perturbation evolves as:
( + = +XX(1) x"
for all nodes i.
= =X((X')XX(() R(6X(t)
(e) The oversmoothing condition lim;-500 1X; X
By Lyapunov's linearization theorem, asymptotic stability requires:
O occurs when:
ker(T [T - (X())) Oo:
p(J{(*)) <1
17

---

A Dynamical Systems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Attention Networks
Part (c): Error Evolution
By assumption, X* span @u:r RR),
For sufficiently small perturbations, linearization dominates:
X = 1 N @ v for some E Rd
[tx F)
This means X; e for all E (I....,, N}. Substituting
back:
Using triangle inequality:
== d'{ Σ
aiyWe
[ 1) < |
JEN(()
For small enough (
=o((h)
Σ oij We
[[)( s (()lx
JENTO
for any E
='(h))
Therefore:
where we used the normalization condition ΣjeN() of 1.
[(0x(()) & (I) + +0)
Therefore:
Part (d): Attention Weight Condition
|X X21xi = ||0 - v112 =0 Vi,
The spectral norm satisfies:
JJ max
Σ
110 Wol
This confirms that any solution in ker(/ - Jj,((")) exhibits oversmoothing, as all node features converge to the same value v. The stability of this solution is guaranteed by the spectral radius condition from part (b).
JEN(()
For stability:
[o'(h))a Wil2 <1 Vi
6.6. Lemma
JEN(
Lemma (Spectral Properties of DYNAMO-GAT Pruning). Let (V, F)) be a graph, and let F, Fp RR + R- xd represent the original and pruned GNN transforma- tions, respectively. Let X E RNNe be oversmoothing fixed point. Then:
Part (e): Oversmoothing Characterization
At oversmoothing:
X; = Vi,j
for some E Rdd
(a) The spectral radius satisfies:
This implies:
p(Jr, (1 (1-11)(paal) p))(J=(X"),,
X =1=1 &
where is the effective pruning rate.
By fixed point property:
(b) For the covariance-bac pruning strategy in DYNAMO-GAT:
(x'x(())) =0
Pij r(() |aig! (Cu: Cjs 2Ctj), T(t)
Therefore:
ker(T (T J((X))) 11 Gu:ve [R)
the pruned Jacobian eigenvalues (x(FFp) satisfy:
To show sufficiency, consider any X e ker(1 (X*))
(R(JFr) [Ax(JF) exp (-8 [TCC)
Then:
(7 (x')((x')x**= =
where B is praning adaptation parameter.
X = J(
(c) The pruned spectral gap increases monotonically:
d'(hi) EjeNay WXj
PP 1p=1- >a(Jrr)
(1(FF)) 27+ +
((i))))ENIIN) 05N WX;
where 7y the original spectral gap from Lemma
18

---

A Dynamical Systems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Attention Networks
(d) The rank of pruned feature representations is pre- served:
Using the submultiplicative property of matrix norms:
|| 112 < || 12 - P)ll
(41)
rank(Cov(Fp(X))) 2 rank(Cov(X)) k(p);
The norm of (1 P) relates the covariance through:
where k(p)= S [p- rank(Cov(X))]-
Tr(C)
(e) The pruned attention weights maintain featuree diversity through:
[[ - P) 1 exp
-23
(42)
|
((F((X)) 2 (1+ ()+)))(XX,
By eigenvalue interlacing:
(-8 Tr(C)
where p(-) is the feature diversity measure from Lemma
(Rx(),)) & (Ax(JE) exp
exp
(43)
|||||
2.
(f) The eigenvalues of the pruned covariance matrix sat- isfy:
Part (c): Spectral Gap Analysis
By Weyl's inequality and the structure of P:
M(Cov(Fp(X))) 2 (1 (1- (Coo-))))(CCo())))
(2(FF)) S (1 - p)A2(JF)
(44)
for all rank(Cov(X)) k(p).
(1 2 (1 - - Aai
(45)
Proof. Part (a): Spectral Radius Reduction
The spectral gap 7/ becomes:
First, observe that pruning modifies each Jacobian entry as:
A2(JFr)
PP Yp =
(46)
(X (1 Pt))(F>(X"))
(34)
(J(p))
2 1 - (1 (JF2(JF)
where Psj is the pruning probability for edge (i.j).
(47)
(1 ())((FF)
By the Perron-Frobenius theorem, since Jr (X*) has non-
1 - (1 - (1-p)(1 +000)))(11))
(48)
negative entries:
2 2 + 101pp(111) (1)
(49)
(()((X)) lim | 1/K
(35)
k0000
Part (d): Rank Preservation Analysis
where ||. any matrix norm.
Consider the covariance matrix before and after pruning:
Using the element-wise inequality and non-negativity of (i-P)):
Cov(X) N X N2
X X ININ
(50)
|Jr, < - (()*)))
(36)
1 No IN
(37)
Cov(Fp(X)) N
1NT
(51)
where p avg(p:)) is the effective pruning rate.
By the pruning operation:
Taking the k-th root and limit:
Fp(X)
-p), (52)
(X+r(X')) S - (x)))
(38)
where Dr a diagonal matrix with entries from P.
Part (b): Covariance-Bani Based Pruning Effect
Using the rank-nullity theorem:
First, we express the pruned Jacobian using Hadamard prod- uct:
(ank(CooF>((X)) = rank(Cov(X)) - dim(ker(1 Dp))
(53)
JFP JF (1-11 (1-P),
(39)
2 rank(Cov(X))) - 1ii [ = 1}
where is the matrix of pruning probabilities.
(54)
For the covariance-basee pruning:
By the definition of k(p):
lais 7(L)
Ps r(t)
(Ca + Cj 1 2CCi),
(40)
1(i : P: 1}1 S [p rank(CCv((X)) k(p) (55)
19

---

A Dynamical Systems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Attention Networks
Part (e): Feature Diversity Maintenance
(a) For the peateep X(1) x(1))+ where g(t) NN r):
First, let us express the feature diversity measure after prun- ing:
rank( =
(67)
1 ((Fr(X))= N(N 1)
E i41
(X,, - Fp(x)))l2
with probubility 1.
|FF((X))l2 + 1|Ex(xx))l2
(b) The pruned update preserves rank:
(56)
ra + 1))) 2 rank(C(X(I))) - -k(),, (68)
1 N(N 1) ifj
I1(1 (1--P))) ((1-D;))(F(X; - F(X,))ll where te(t) is the maximum number of eigenvalues
(111 P(x)) + [111 Pss F (eelliv a threshold c(t).
(57)
(c) For noise level -0 the minimum eigenvalue satis- fies:
Using the spectral gap property from part (c):
Amin Amin (C(t)) 2 0² (C(t))2
N - (69)
[[Fp(X.)) Fx(X))l12 (1 (1-11pp) p1) +
F(x))122
(58)
(d) Under the adaptive pruning threshold:
[F (1 ((xx))]F(Xx)]l
(59)
r(t) = p(())) + 3 (lwis)),
(70)
Combining these inequalities:
rank is preserved with high probability if:
((F((X)) 2 (1+ (x)
(60)
2 2log(d/5)
B
(71)
N
Part (f): Covariance Figenvalue Analysis
where 8 is the failure probability.
First, we express the pruned covariance matrix eigenvalues using perturbation theory:
Detailed proof of Lemma 6. We prove cach part of the lemma separately, showing how noise injection and pruning affect the covariance structure and rank properties.
(CC)((FF(XX) = Ac(Cov(X)) + 6,
(61)
where 6 is the perturbation term.
(a) Full Rank Property of Noise- Features:
By Weyl's ss perturbation theorem:
First, expand the covariance of noise-perturbed features:
1 N (X(t++ + (X (x(t)+
|6,1 s |Pl| [[Cov(X)]la S pCX((Co(XX))
(62)
C(X(+)) =
For preserved eigenvalues (i 5 rank(Cov(X))) - x(p)):
N2 (X(t) + " 1N
{((Cov(F((X)) 2 {:(Cov(X)) - - POX (63)
C(X(0)++ +02 (1=
(1 (1-p5) p5) (Cov((
(64)
(X(1) +E(1)xx(1))
By the aeoietric-arithmetii mean inequality:
o²
7 IN1
(72)
x(Coo(F)(X))) 2 (1 (1- >1))>
(65)
Let's analyze each term: 1. C(X(t)) is the original covari- ance 2. o² - + 1N is positive semidefinite with rank d d 13. & (X + g(t)T((( ((()) is random with mean zero 4. The last term is of order O(02/N)
6.7. Lemma 6
Lemma (Rank Preservation Under DYNAMO-GAT),, Let (t) E R.d be the node features at layer t. Define the covariance matrix C(t) E Rdxd as:
For any unit vector e E Rdd
?7 ''((((()) 2 o' C(X())) - o² (1-
1
N
1 C(I) - - X(0"X()---- IN (66)
1
+ ((X())E(()+ ((())))))(((((())) X(t))
N
where 1 is the all-ones vector. Under the DYNAMO-GAY noise injection and pruning strategy:
No (FFE1) ((E(0)=I)((E((0))))
(73)
20

---

A Dynamical Systems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Attention Networks
By the properties of Gaussian random matrices, with proba- bility 1: ran)( = min(N, d)
(d) Rank Preservation Under Adaptive Threshold:
The adaptive threshold rtt) ensures that with high probabil-
(74)
ity:
log(d/6)
Therefore, (t)( is full rank with probability 1.
[P(()l2 S BV
(83)
N
(b) Rank Preservation Under Pruning:
Let P(t) be the pruning mask at layer f. The pruned update can be written as:
For B 2
2log(d/6)
by union bound:
N
((raan(((((()) 1))) rank(C(X(()))
= o I(X())
(75)
P() (C(X(I+1)) <(())))))))))))))) <<(())
(84)
For the covariance difference:
This completes the proof that rank is preserved with proha- bility at least 1 - 8.
- 1 -1 - - X(I)x(())
7. Supplementary Section B: Experimental Section
N2 (X( (x00++11))))0011"100000000
(76)
7.1. Experimental Setup
By Weyl's interlacing theorem:
Datasets We conduct our experiments on three real-world datasets and two synthetic datasets
(xCC(X((11))-A(C(x(()) s [1(0)l2 (|(()) (C((()((((
(77)
Cora Dataset (McCallum et al., 2000): The Cora cita- tion network consists of 2,708 nodes and 5,429 edges. Each node represents document, and each edge rep- resents a citation link between two documents. The dataset commonly used for semi-supervised node classification tasks.
Therefore:
rCnk(C((((++)))) 1))) 2 (an)(C(X(())) - -x(()
(78)
where <(t) counts eigenvalues that could fall below <(t).
(c) Minimum Eigenvalue Bound:
Citeseer Dataset (Sen et al., 2008): The Citeseer cita- tion network consists of 3,327 nodes and 4,732 edges. Similar Cora, each node represents document, and the edges represent citation links. This dataset is also widely used for evaluating GNN performance.
For the minimum eigenvalue, we use matrix concentration:
Amin (C(t)) 2 Amin Amin(C(X (C(X(I)) + (1-N)
Cornell Dataset (University): The Cornell dataset is a small graph with 183 nodes and 295 edges. part of the WebKB network collection and is commonly used for node classification tasks.
I ((0))
- -1 In)
(79)
Synthetic Datasets (Syn Products and Cyn_C (Zhu et al., 2020): To further test the advan- tages of DYNAMO-GAT, we use synthetic datasets. _yn_uroducts is designed simulate product co- purchasing networks, and Syn_Cora mimics citation networks. We vary the graph density and homophily levels to analyze the performance of different GNN models under controlled conditions. For space limita- tions, we give the syn_cora results in the appendix.
By sub-gaussian concentration inequalities:
(Xtt) + ((t)) ((0) ((]) (()x))) (80)
And:
|| NZ 1() s o
(81)
Therefore:
Xmai (C())) 20² 22-111111 N - -O(Ix(t))lem)
(82) Baselines We compare DYNAMO-GAT against several baseline models to assess its effectiveness:
21

---

A Dynamical Systems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Attention Networks
GCN (Graph Convolutional Network) (Kipf & Welling, 2017): A widely used GNN model that ap- plies graph convolutions aggregate information from neighboring nodes.
GAT (Graph Attention Network): A GNN model that attention mechanisms weigh the importance of neighboring nodes during ag- gregation.
G2GAT: A recent model that introduces gradi- ent gating to prevent oversmoothing in attention- based GNNs.
GAT (Graph Attention Network) (Veličković al., 2018): A model that incorporates attention mecha- nisms to weigh the importance of neighboring nodes during message passing.
Experimental Setup:
G2GAT (Rusch et al., 2023a): A recent method that introduces gradient gating to prevent oversmoothing in attention-based GNNs.
The number of layers is varied from 2 to 128 to observe how the models behave as the network depth increases.
The training parameters are kept consistent across models for fair comparison, including the use of the Adam optimizer and fixed learning rate.
Evaluation Metries We evaluate the performance of all models using the following metrics:
Accuracy: The classification accuracy the test set.
Results (Figure 'real_data"):
Oversmoothing Coefficient (μ): A measure of the degree which node representations become indistin- guishable network depth increases.
Oversmoothing Coefficient (p(X)):
Citeseer (Figure a): As the number of layers increases, GCN and GAT exhibit significant over- smoothing, with their oversmoothing coefficients rapidly decreasing. G2GAT mitigates this effect better than GCN and GAT, but still shows a de- cline. DYNAMO-GAT, however, maintains consistent oversmoothing coefficient, effectively preventing oversmoothing across all layers.
GFLOPS:
The computational efficiency, measured in Giga Floating Point Operations Per Second.
Accuracy/GFLOPS: A ratio indicating the trade-off between accuracy and computational cost.
7.2. Experiment World Dataset Evaluation
Cora (Figure b): Similar trends are observed, with GCN and GAT experiencing substantial over- smoothing the number of layers increases. DYNAMO-GAT demonstrates its robustness by keeping the oversmoothing coefficient stable, while G2GAT also shows improved performance compared to GCN and GAT but not as strong as DYNAMO-GAT.
This experiment aims to evaluate the effec- tiveness of DYNAMO-GAT in mitigating oversmoothing and maintaining high test accuracy across varying network depths three real-world datasets: Citeseer, Cora, and Cornell. The performance of DYNAMO-GAT is com- pared with that of three baseline models: GCN, GAT, and G2GAT.
Objective:
Cornell (Figure c): Again, DYNAMO-GAT out- performs the other models in controlling over- smoothing, maintaining a stable coefficient across all layers. GCN and GAT display rapid declines, indicating severe oversmoothing.
Methodology:
Metrics:
Oversmoothing Coefficient (u(X)): This metric quantifies the degree of oversmoothing, where lower values indicate greater oversmoothing. It is plotted on a logarithmic scale to better capture the dynamics across a wide range of values.
2. Test Accuracy:
Citeseer (Figure a): GCN and GAT suffer from significant drop in accuracy the number of lay- ers increases, correlating with their high levels of oversmoothing. DYNAMO-GAT maintains con- sistently high accuracy, even deep networks, highlighting its effectiveness in mitigating over- smoothing. G2GAT also shows relatively stable accuracy but still declines with increasing layers. Cora (Figure b): Similar patterns are observed, with DYNAMO-GAT achieving the highest ac- curacy across all layers. GCN and GAT see their
Test Accuracy: This metric measures the clas- sification accuracy of the models on the test set. The objective is to assess how well the models perform as the number of layers increases.
Baselines:
- GCN (Graph Convolutional Network): A stan- dard graph neural network model that aggregates node features through graph convolutions.
22

---

A Dynamical Systems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Attention Networks
accuracy decline sharply layers increase, while G2GAT performs better but still experiences decrease.
tional cost, indicating how efficiently the model achieves its performance.
Comparison Setup:
Cornell (Figure c): DYNAMO-GAT once again demonstrates superior performance by maintain- ing high accuracy, while GCN and GAT show considerable drop in accuracy as the number of layers increases. G2GAT performs better than GCN and GAT but still shows a downward trend accuracy.
The models were trained on the three datasets (Cora, Citeseer, Cornell), each with different graph structures and node/edge counts.
GCN and GAT were tested with relatively shal- low architectures, while G2GAT and DYNAMO- GAT were evaluated with deeper networks (128 layers).
The results clearly demonstrate the superiority of DYNAMO-GAT in preventing oversmoothing and main- taining high test accuracy across deep network architectures. In contrast, GCN and GAT suffer from severe oversmooth- ing, leading significant decline in accuracy as the num- ber of layers increases. G2GAT mitigates oversmoothing to some extent but is still not as effective DYNAMO-GAT. This consistent performance across three different datasets underscores the robustness of DYNAMO-GAT in handling deep graph neural networks, making a promising approach for tasks that require deep architectures.
Analysis:
The results were compiled to highlight the effi- ciency of each model terms of accuracy and GFLOPS.
Results (Table 1):
1. Best Accuracy:
DYNAMO-GAT achieves the best accuracy across all datasets, particularly excelling the Cornell dataset with an accuracy of 62.56
G2GAT also performs well, particularly on Citeseer and Cornell, where closely matches DYNAMO-GAT.
The effectiveness of DYNAMO-GAT can be attributed to its ability preserve meaningful node representations even in deep networks, as evidenced by its stable oversmoothing coefficient and high accuracy. This experiment highlights the potential of DYNAMO-GAT to overcome one of the sig- nificant challenges in deep GNNs oversmoothing while delivering strong performance on real-world datasets.
GCN and GAT show lower performance com- pared to the deeper models, particularly on the more challenging Cornell dataset.
# Layers:
GCN and GAT achieve their best accuracy with only 2-4 layers, indicating their limitations in deeper architectures due to oversmoothing.
7.3. Experiment Performance Comparison Table
This experiment aims to compare the perfor- mance of DYNAMO-GAT with other baseline models (GCN, GAT, and G2GAT) in terms of accuracy, computa- tional efficiency (GFLOPS), and the -FOLLPS ratio across three datasets: Cora, Citeseer, and Cornell. The goal is to highlight both the effectiveness and efficiency of DYNAMO-GAT, particularly in deeper network architec-
Objective:
In contrast, G2GAT and DYNAMO-GAT are able to sustain performance across 128 layers, highlighting their robustness deeper networks.
3. GFLOPS:
DYNAMO-GAT exhibits lower GFLOPS com- pared GAT and G2GAT, indicating that it is computationally more efficient.
tures.
Methodology:
For example, on the Cora dataset, DYNAMO- GAT uses 0.605 GFLOPS, which is significantly lower than GAT's 2.351 GFLOPS.
Metrics:
Bestt Accuracy: The highest classification accu- racy achieved by each model on the test
Accuracy/GFLOPS:
-
Layers: The number of layers used by the
DYNAMO-GAT consistently outperforms other models in the accuracy-to-GHi GFLLOPS ratio, demon- strating its superior efficiency.
model achieve its best accuracy.
GFLOPS: The computational cost measured Giga Floating Point Operations Per Second, which provides an indication of the model's effi- ciency.
-
For instance, on the Cora dataset, DYNAMO- GAT achieves an Accuracy/GFLOPS ratio of 137.53, which is the highest among all models, in- dicating that it provides the best trade-off between accuracy and computational cost.
Accuracy/FLLPS:: This metric represents the trade-off between accuracy and computa-
-
23

---

A Dynamical Systems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Attention Networks
Similarly, on the Citeseer and Cornell datasets, DYNAMO-GAT achieves the highest ratios, with 48.96 and 1226.67, respectively, far surpassing the other models.
While G2GAT performs well, its accuracy de- creases slightly with deeper layers. GCN and GAT see sharp decline in accuracy as the net- work depth increases.
The stability of DYNAMO-GAT in maintaining high accuracy, even with large number of layers, indicates its effectiveness in managing deeper architectures without suffering from oversmoothing, unlike the other models.
Implication:
Analysis: The results highlight the advantages of DYNAMO-GAT in both accuracy and efficiency. Despite using deep architectures (128 layers), DYNAMO-GAT manages to maintain high accuracy while keeping computa- tional costs low. This is particularly evident when compar- ing the Accuracy/GFLOPS ratio, where DYNAMO-GAT significantly outperforms GCN, GAT, and even G2GAT. This indicates that DYNAMO-GAT is not only effective in mitigating oversmoothing but also highly efficient in terms of resource usage, making it a superior choice for applica- tions that require deep graph neural networks with limited computational resources.
3. Accuracy vs. Homophily (Sparse Graph Figure c)
Observation: This plot examines accuracy across varying homophily levels (from to 1) for sparse graph with an average node degree of 11.93.
Key Result: DYNAMO-GAT and G2GAT out- perform GCN and GAT across all homophily lev- els. DYNAMO-GAT achieves particularly strong performance homophily increases, indicating its ability to leverage node similarity effectively.
7.4. Experiment 3: Synthetic Dataset Evaluation
The goal of this experiment is to assess the per- formance of DYNAMO-GAT under controlled synthetic conditions. Specifically, we vary the graph density (aver- age node degree) and homophily to observe how different models handle oversmoothing and accuracy in these envi- ronments.
Objective:
Implication: This suggests that DYNAMO-GAT is versatile and can adapt well to different ho- mophily settings, making it suitable for graphs with varying levels of node similarity.
4. Accuracy vs. Homophily (Dense Graph Figure d):
Results:
Observation: Similar to Figure c, but for a dense graph with an average node degree of 68.75.
1. Oversmoothing vs. Layers (Figure a):
Key Result: DYNAMO-GAT significantly out- performs all other models, especially in low- homophily settings. As homophily increases, DYNAMO-GAT maintains its lead, showcasing its robustness across all homophily levels.
The figure shows the oversmooth- ing coefficient (xX) on a logarithmic scale as the number of layers increases, with an average node degree of 68.75.
Observation:
Key Result: As the network depth increases, DYNAMO-GAT shows the least amount of over- smoothing, maintaining higher p(X) values com- pared to G2GAT, GCN, and GAT. GAT and GCN exhibit rapid oversmoothing, with μ(X) decreasing significantly as layers increase.
Implication: This result highlights DYNAMO- GAT's strength in dense graphs, where can handle more complex interactions and still main- tain high accuracy. Its performance in low- homophily conditions also suggests it is well- suited for graphs with more heterophilic struc- tures.
Implication: This result demonstrates that DYNAMO-GAT is more robust to oversmooth- ing, especially in dense graphs. This suggests that it can preserve meaningful node features bet- ter than the other models the network depth increases.
The synthetic dataset results confirm that DYNAMO-GAT excels in both dense and sparse graphs, effectively handling oversmoothing and maintaining high accuracy across varying network depths and homophily lev- els. Its ability to outperform other models, particularly in dense graphs and how-homphhlly settings, underscores its robustness and versatility. These findings demonstrate that DYNAMO-GAT is powerful tool for tackling oversmooth- ing while delivering strong performance in diverse graph structures, making it ideal for complex real- weal-world applica- tions.
Analysis:
2. Accuracy vs. Layers (Figure b):
Observation:
This plot shows accuracy func- tion of the number of layers for the same dense graph (average node degree= 68.75).
Key Result: DYNAMO-GAT consistently achieves the highest accuracy across all layers.
24

---

A Dynamical Systems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Attention Networks
Table Pruning Statistics and Cosine Similarity Analysis. DYNAMO-GAT prunes a significant portion of edges. Crucially, edges connecting nodes with lower feature similarity (lower cosine similarity) are preferentially pruned, empirically supporting our approach to mitigating oversmoothing.
Dataset
Pruning Ratio (%)
Cosine Sim. (Retained)
Cosine Sim. (Pruned)
Cora
18.3
0.81
0.52
Citeseer
15.7
0.78
0.48
to Graphormer and SAN on the Cora and Citeseer datasets. The results (Table 7) show improvements in both accuracy and OS coefficient, along with reduction in GFLOPS, demonstrating the potential generalizability of our approach.
Table 6. Hyperparameter Sensitivity Analysis Cora.
Noise Level o
Threshold 3
Accuracy (%)
0.01
0.5
82.9
0.05
1.0
83.5
0.1
2.0
83.2
7.8. Results and Discussion
The experimental results across both real-world and syn- thetic datasets consistently demonstrate the effectiveness of DYNAMO-GAT in addressing the oversmoothing problem in deep graph neural networks (GNNs).
7.5. Analysis of Pruning Ratios and Feature Similarity
To provide further insight into the structural impact of DYNAMO-GAT's pruning mechanism, we analyzed the pruning ratio (percentage of edges removed) and the cosine similarity of node features for both retained and pruned edges on the Cora and Citeseer datasets. The cosine similar- ity was calculated between the final layer node embeddings of connected nodes just before pruning decisions.
From the real-world datasets (Figure 2), we observe that DYNAMO-GAT maintains a stable oversmoothing coeffi- cient (p())) across varying network depths, outperforming GCN, GAT, and G2GAT, which exhibit significant over- smoothing as the number of layers increases. Correspond- ingly, DYNAMO-GAT consistently achieves the highest accuracy across all layers, whereas GCN and GAT suffer a sharp decline in accuracy due oversmoothing, and G2GAT shows moderate performance.
As shown in Table ??, DYNAMO-GAT prunes significant portion of edges (18.3% on Cora, 15.7% on Citeseer). More importantly, the average cosine similarity for pruned edges considerably lower than for retained edges (e-g.. 0.52 vs. 0.81 on Cora). This empirically validates our theoretical insight: DYNAMO-GAT preferentially prunes edges con- necting nodes with lower feature similarity (and thus likely contributing more to noise/homogenization than meaningful signal), thereby preserving structural information crucial for preventing oversmoothing.
The performance comparison table (Table 1) further high- lights the efficiency of DYNAMO-GAT. It achieves the best accuracy across all datasets while maintaining lower GFLOPS compared to GAT and G2GAT, The high accuracy- to- GFLOPS ratio underscores DYNAMO-GAT superior trade-off between computational cost and performance, mak- ing it the most efficient model among the tested baselines.
7.6. Hyperparameter Sensitivity
In the synthetic dataset experiments (Figure 3), DYNAMO- GAT again demonstrates its robustness. It shows the least oversmoothing in dense graphs (Figure 3a) and maintains the highest accuracy across layers (Figure 3b). When vary- ing homophily, DYNAMO ure 3c) and dense (Figure 3d) graphs, particularly in low- homophily settings, showcasing its adaptability different graph structures.
DYNAMO-GAT introduces two primary hyperparameters: the noise level (a) and the pruning threshold adaptation parameter (3). We conducted experiments to assess the model's sensitivity these parameters. As shown in Ta- ble 6, DYNAMO-GAT demonstrates robust performance across reasonable range of values for both and B. The accuracy remains stable within +0.6%, indicating that our method is not overly sensitive to hyperparameter choices and simplifies the tuning process for practical deployment.
excels in both sparse (Fig-
The results show a clear trend where models generally per- form better as the average degree increases. This is par- ticularly evident in higher homophily settings, where the additional connections help to reinforce the graph structure. leading more accurate node classification. For instance, in the syn-products dataset, the accuracy of GCN improves from 0.567 to 0.762 as the average degree increases from 11.93 to 36. 14 at a homophily level of 0.4.
7.7. Generalizability to Other Attention-Based GNNs
While the main experiments focused on GAT, we posited that the core DYNAMO mechanism is attention-agnostic and applicable to other attention-based GNNs. To sup- port this, we applied DYNAMO-GAT's pruning strategy
25

---

A Dynamical Systems-Inspired Pruning Strategy for Addressing Oversmoothing in Graph Attention Networks
Table 7. Applying DYNAMO Pruning Graphormer and SAN.
Model
Dataset
Acc. (%)
OS Coeff.
GFLOPS
Graphormer (base)
Cora
83,92
0.51
2.1
SONAMM--Graphommne
Cora
85.13
0.64
1.41
SAN (base)
Citeseer
80.23
0.47
2.35
DYNAMO-SAN
Citeseer
81.74
0.59
1.52
Interestingly, models like G2GAT and DYNAMO-GAT, which incorporate additional mechanisms for graph pro- cessing, consistently outperform simpler models such GCN and GAT, particularly in low homophily settings. This suggests that these models better able to leverage the graph structure even when the nodes are less similar to their neighbors.
These findings have significant implications for the develop- ment and deployment of GNNs real-world applications. The ability of DYNAMO-GAT maintain high accuracy while mitigating oversmoothing, especially in deep architec- tures, addresses a critical challenge faced by many existing GNN models. Its superior efficiency, evidenced by the accuracy-to-GFLLPP ratio, makes it viable option for resource-constraamed environments where both performance and computational cost are important considerations.
Moreover, DYNAMO-GAT's strong performance across varying graph densities and homophily levels suggests that it is well-suited for wide range of graph structures, from sparse networks with high node similarity to dense, het- erophilic graphs. This versatility makes DYNAMO-TAT an attractive solution for complex graph-based tasks domains such social network analysis, recommendation systems, and biological network modeling.
26


Reviews:
[{"review_id": "WSiH1gvTXs", "reviewer": "Reviewer_KMUB", "summary": "The paper introduces **DYNAMO-GAT**, a **pruning strategy** for **Graph Attention Networks (GATs)** to mitigate **oversmoothing** using a **dynamical systems perspective**. The authors propose:\n1. **Noise-driven covariance analysis** to detect oversmoothing.\n2. **Anti-Hebbian learning** to selectively prune attention weights.\n3. **A theoretical framework** linking oversmoothing to attractor dynamics in GNNs.\n4. **Experimental validation** showing **improved performance and efficiency** across standard benchmark datasets.\n\nThe approach shifts from architectural modifications (e.g., skip connections, normalization) to **dynamically altering attention weights** based on system stability analysis.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "1. **Performance on Heterophilic/Dense Graphs:** Our theory—based on spectral gap & fixed-point stability—does not assume homophily or sparsity, generalizing across diverse graph types.\n* Empirical validation:\n  * Fig. 3 (Syn-Products): DYNAMO-GAT (DGAT) DGAT performs well as edge density increases, showing resilience to OverSmoothing (OS)\n  * As noted in our reply to Reviewer kxJk, we test on OGBN-Arxiv (homophilic) &OGBN-Products (heterophilic); DGAT performs robustly across both, confirming robustness across varying homophily & density levels.\n\n2. **Generality to Other Architectures:** While our main experiments focus on standard GATs, the core mechanism—noise-driven covariance-based pruning is attention-agnostic and applies to broader attention-based GNNs.\n* In Transformer-style GNNs, evolving attention layers can lead to OS—our dynamical framework models this & supports adaptive mitigation.\n* In hierarchical GNNs, aggregation levels map to time scales; our method identifies feature mixing points and enables multi-scale pruning.\n* To show generalization, we applied DYNAMO pruning to Graphormer & SAN on Cora & Citeseer:\n\n|Model|Dataset|Acc.(%)|OS Coeff|GFLOPs|\n|--|--|--|--|--|\n|Graphormer (base)|Cora|83.92|0.51|2.1|\n|DYNAMO-Graphormer|Cora|85.13| 0.64|1.41|\n|SAN (base)|Citeseer|80.23|0.47|2.35|\n|DYNAMO-SAN|Citeseer|81.74|0.59|1.52|\n\n3. **Runtime Analysis:** We report GFLOPS as a proxy for computational complexity. While actual training & inference times depend on hardware, we introduce a little training overhead (due to covariance computation) while substantially reducing inference complexity.   \n     \n4. **Pruning Thresholds:** DGAT uses ***adaptive thresholds*** based on feature covariance (Eq. 40), removing the need for fixed pruning rates. This adaptivity aligns pruning with evolving node representations, minimizing hyperparameter tuning.\n     \n5. **Ablation:** We ablated each core component—noise injection, covariance pruning, adaptive thresholds, gradual pruning, attention recalibration. Results show that all parts are critical: removing any causes performance drops and increased OS.\n|Model|Acc.% (Cora)|Acc.% (Citeseer)|OS Coeff. (Cora)|OS Coeff. (Citeseer)|\n|--|--|--|--|--|\n|Full DGAT|83.21|82.01|0.57|0.62|\n|–Noise Injection (σ=0)|81.54|80.26|0.45|0.52|\n|–Covariance-based Pruning|79.32|77.15|0.31|0.36|\n|–Adaptive Thresholding (fixed threshold)|80.67|79.52|0.38|0.41|\n|–Gradual Pruning (aggressive pruning)|80.14|78.93|0.34|0.39|\n|–Attention Recalibration|79.78|78.41|0.35|0.40|\n6. **Theoretical Assumptions & Failure Cases:** We agree that theoretical guarantees often rest on simplifying assumptions. Our analysis assumes Lipschitz continuity and bounded attention weights—standard in GNN theory—and we empirically validate its predictions (e.g., spectral gap improvement, robustness to OS) across diverse datasets and structural regimes.\nPotential failure modes reflected in our experiments:\n* Low-degree graphs: In Fig. 3, performance drops when node degrees are very low—pruning can limit already sparse message passing.\n* Excessive pruning: Our ablation includes “Gradual Pruning” variant, simulating aggressive, non-adaptive pruning. This leads to significant accuracy drops & increased OS, confirming that premature pruning can remove essential edges. We plan to explore mitigation strategies like pruning warm-up & degree-aware regularization in future work.\n\n7. **Stability:** Our stability analysis (Lemmas 4 & 5) shows covariance-based pruning reduces the Jacobian’s spectral radius, thereby enhancing long-term model robustness rather than causing instability. Experimental observations suport these predictions.\n\n8. **Scalability:**  As detailed in our response to Reviewer kxJk, we have evaluated DGAT on larger-scale benchmarks (e.g., ogbn-arxiv & ogbn-products). These results demonstrate that our method scales efficiently to graphs with hundreds of thousands of nodes while maintaining a superior accuracy/GFLOPS trade-off.\n\n9. **Varying Homophily Levels:**  Fig. 3 shows consistent performance across a wide homophily spectrum, including low-homophily regimes.\n\n10. **Energy Efficiency:** By pruning low-value attention edges, DGAT significantly reduces inference FLOPs, translating into lower computational & energy costs. Although the training overhead is slightly increased due to covariance computations, the overall efficiency gains are substantial. \n\n11. **Real-World Deployment:** DGAT is well-suited for real-world applications—such as recommendation systems, fraud detection, or molecular modeling—where OS limits model depth. Its reduced inference cost & compatibility with standard practices like incremental pruning, retraining, & recalibration make it practical for deployment in compute-constrained environments.\n\n12. **Interpretability:** DGAT prunes edges with low feature covariance (often low attention weights), potentially enhancing the interpretability of the resulting attention maps by reducing noise.", "claims_and_evidence": "### **Supported Claims**\n1. **Oversmoothing in GNNs can be analyzed via dynamical systems.**  \n    The paper provides **theoretical proofs** on **fixed points and spectral analysis**, explaining how oversmoothing occurs.  \n\n2. **DYNAMO-GAT effectively mitigates oversmoothing.**  \n    Empirical results show **higher accuracy** across deeper networks compared to standard **GCN, GAT, and G2GAT**.  \n    The **oversmoothing coefficient (µ(X)) remains stable**, indicating better node representation preservation.  \n\n3. **Pruning reduces computational cost without degrading performance.**  \n    The model achieves **higher accuracy-to-GFLOPS ratios** than existing baselines, showing **efficiency improvements**.  \n\n### **Potentially Overstated or Weakly Supported Claims**\n1. **Theoretical guarantees ensure robustness across all graph structures.**  \n    The theory **mainly focuses on spectral gap analysis**; however, performance may still degrade in **highly heterophilic or dense graphs**.  \n\n2. **DYNAMO-GAT generalizes to all attention-based GNNs.**  \n    The method is **only tested on standard GATs**. Its applicability to **Transformer-like GNNs or hierarchical architectures** remains uncertain.", "methods_and_evaluation_criteria": "###  **Strengths**\n- **Dynamical systems perspective** provides a new theoretical view on oversmoothing.  \n- **Effective pruning strategy** improves both expressiveness and efficiency.  \n- **Empirical validation** across multiple datasets confirms effectiveness.  \n\n### **Areas for Improvement**\n- **No runtime analysis** – How does pruning impact training/inference time?  \n- **Limited discussion on pruning thresholds** – How are optimal pruning rates determined?  \n- **Ablation study missing** – How does each component (e.g., noise injection vs. pruning) contribute separately?", "theoretical_claims": "###  **Strengths**\n- Provides a **mathematical formulation** of oversmoothing using **eigenvalue properties** of GATs.  \n- Shows how **pruning increases spectral gaps** and **prevents feature collapse**.  \n\n###  **Limitations**\n- **Fixed-point analysis assumes ideal conditions** – Real-world GNNs might not satisfy all assumptions.  \n- **No analysis of pruning-induced instability** – Could pruning negatively affect long-term model robustness?", "experimental_designs_or_analyses": "###  **Strengths**\n- **Uses benchmark datasets (Cora, Citeseer, Cornell) for fair comparisons.**  \n- **Compares against competitive baselines (GAT, GCN, G2GAT).**  \n- **Analyzes oversmoothing using both accuracy and feature diversity metrics.**  \n\n###  **Weaknesses**\n- **No failure case analysis** – When does DYNAMO-GAT fail?  \n- **Scalability not tested** – How does it perform on larger graphs?  \n- **Impact on node classification under different homophily levels is not explored.**", "relation_to_broader_scientific_literature": "### **New Contributions**\n **Introduces dynamical systems principles** to analyze **GAT oversmoothing**.  \n **Proposes noise-driven pruning** for dynamically adjusting attention weights.  \n **Provides theoretical guarantees** for pruning’s impact on network expressiveness.  \n\n### **Missing Comparisons**\n **No evaluation on deeper Transformers** (e.g., **Graphormer, SAN**).  \n **Limited discussion on energy efficiency trade-offs** (e.g., pruning vs. FLOP savings).", "essential_references_not_discussed": "NO", "other_strengths_and_weaknesses": "###  **Strengths**\n- **Combines theory and practice effectively.**  \n- **Proposes a well-motivated pruning strategy with strong empirical results.**  \n- **Demonstrates practical impact on deep GNN scalability.**  \n\n###  **Weaknesses**\n- **No real-world deployment discussion** – How would this method work in industry applications?  \n- **Impact of pruning on interpretability is unclear** – Does removing attention weights affect explainability?", "other_comments_or_suggestions": "Please refer to the above section", "questions_for_authors": "Please refer to the above section", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2AufvU34MH", "reviewer": "Reviewer_1eSc", "summary": "The paper  presents a dynamical systems take on GNNs and proposes dynamically pruning edges based on learnt attention weights in GAT to combat oversmoothing.\n\n## update after rebuttal: \nI thank the authors for their detailed response to my questions and their effort in providing further experiments. While results on larger heterophilic datasets in [1] would add further value to the paper, I believe that the additional discussion and experiments in the rebuttal are sufficient for the paper to be of value to the community, particularly the method used for learning sparse attention patterns. Therefore, I have raised my score.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**Weakness 1: Limited evaluation on small-scale real-world datasets**\n    \nAs discussed in our response to Reviewer kxJk (see the table provided therein), we have extended our experiments to larger-scale benchmarks such as ogbn-arxiv and ogbn-products. These additional results confirm that DYNAMO-GAT not only scales effectively—with a significantly lower GFLOPS count—but also offers a superior accuracy/GFLOPS trade-off relative to baselines. \n\n**Weakness 2: Missing discussion on connection to graph sparsification**\n\nWe appreciate this valuable suggestion. While traditional graph sparsification techniques (e.g., spectral sparsification and effective resistance methods) primarily focus on reducing redundancy to enhance computational efficiency, our pruning strategy differs in its dynamical-systems-inspired rationale. Specifically, our method targets edges based on noise-driven covariance analysis, directly addressing the oversmoothing issue by pruning structurally redundant edges linked to highly correlated node features. We will thoroughly clarify these distinctions and similarities in our revised manuscript.\n\n**Weakness 3: Lack of pruning ratio metrics and structural insights**\n\nWe thank the reviewer for this valuable suggestion. Following your recommendation, we performed additional experiments analyzing both the **pruning ratio** (fraction of edges removed) and the **cosine similarity** of node features for retained versus pruned edges. Specifically, we computed the cosine similarity directly between the corresponding node embeddings at the final layer before the pruning decisions.\n\n**Empirical Results (Cora & Citeseer datasets):**\n\n| Dataset | Pruning Ratio | Cosine Sim. (Retained Edges) | Cosine Sim. (Pruned Edges) |\n| ----- | ----- | ----- | ----- |\n| Cora | 18.3% | 0.81 | 0.52 |\n| Citeseer | 15.7% | 0.78 | 0.48 |\n\nThese results indicate that edges connecting nodes with lower feature similarity (lower cosine similarity) are preferentially pruned, empirically supporting our theoretical analysis of the role of structural redundancy in oversmoothing.\n\n**Question 1: Inductive node classification and graph classification applicability**\n\nWe thank the reviewer for highlighting this aspect. To confirm DYNAMO-GAT’s suitability for inductive scenarios, we performed additional experiments on inductive benchmarks from OGB (**ogbn-arxiv**, **ogbn-products**).\n\nDYNAMO-GAT achieves competitive or superior inductive accuracy with significantly greater computational efficiency (up to 55% improvement in Accuracy/GFLOPS), directly addressing the reviewer's question. We will further explore graph-level tasks in future work.\n\n**Question 2: Additional hyperparameter tuning requirements**\n\nDYNAMO-GAT introduces two hyperparameters: the noise level (σ) and the pruning threshold adaptation parameter (β). Our extensive hyperparameter sensitivity analysis demonstrates robust model performance across a wide range of values:\n\n| Noise Level σ | Threshold β | Accuracy (%) |\n| ----- | ----- | ----- |\n| 0.01 | 0.5 | 82.9 |\n| 0.05 | 1.0 |83.5|\n| 0.1 | 2.0 | 83.2 |\n\nModel accuracy remains consistently stable within ±0.6% across these ranges, significantly simplifying the hyperparameter tuning process required for deployment.\n\n**Question 3: Addressing GAT attention mechanism trainability issues (Mustafa et al. \\[2\\])**\n\nMustafa et al. (2021) show that GAT attention coefficients struggle to effectively learn zero-valued weights due to trainability issues inherent in the standard attention mechanism. This aligns well with our dynamical systems perspective, where attention coefficients that fail to reach zero prevent the pruning of edges and thus contribute to oversmoothing.\n\nFrom a dynamical systems viewpoint (as detailed in our paper), GAT's convergence to fixed points (low-dimensional attractors) can cause node representations to become homogeneous. Mustafa et al. illustrate a similar phenomenon, noting the attention coefficients' tendency to remain away from zero, effectively retaining redundant edges and promoting oversmoothing.\n\nOur method, DYNAMO-GAT, explicitly addresses this issue by incorporating noise-driven covariance analysis and Anti-Hebbian pruning. Dynamically adjusting the network's attractor landscape during training allows for attention coefficients to more readily achieve near-zero values, thus effectively pruning irrelevant edges. This dynamically adaptive strategy mitigates the trainability issues described by Mustafa et al. by actively perturbing the system away from stable attractors that prevent the learning of sparse attention patterns. Consequently, our approach not only overcomes the inherent training difficulty but also preserves distinct attractor states, directly targeting the fundamental cause of oversmoothing from a dynamical systems perspective. We will clarify this connection in the revised manuscript, highlighting explicitly how DYNAMO-GAT addresses the trainability limitations analyzed by Mustafa et al.", "claims_and_evidence": "The authors supports their theoretical claims with proofs and empirical evidence from experiments on synthetic data.", "methods_and_evaluation_criteria": "While the theoretical claims are supported by empirical evidence on synthetic datasets, evaluation on real-world datasets is rather weak in my opinion. While the predictive accuracy achieved by DYNAMO-GAT is very similar to its main competitor i.e. G2GAT, it is shown to be computationally more efficient with a better trade-off between accuracy and cost. However, this is shown on three small datasets. If the main advantage of DYNAMO-GAT over G2GAT is lower computational cost, it should be evaluated on larger datasets such as on OGB datasets, LRGB datasets that may benefit from deeper models, and also larger benchmark heterophilic datasets in [1] that could also potentially benefit more from DYNAMO-GAT as the authors show on synthetic data. \n\n[1] Platonov et al. A critical look at the evaluation of GNNs under heterophily: Are we really making progress?", "theoretical_claims": "The theoretical claims seem correct but the mathematical details were not checked in detail.", "experimental_designs_or_analyses": "See methods and evaluation criteria section of review.", "relation_to_broader_scientific_literature": "The paper makes an interesting connection between dynamical systems and GNNs via theoretical analysis to address the widely-studied oversmoothing problem in GNNs. While other solutions such as structural modifications for oversmoothing are mentioned, a discussion of the proposed pruning-based method in the context of graph sparsification particularly to tackle oversmoothing and for efficiency gains is missing.", "essential_references_not_discussed": "None that I can recall.", "other_strengths_and_weaknesses": "Strengths: The paper presents an effective combination of existing techniques rooted in theoretical analysis. \n\nWeaknesses: The tradeoff between accuracy and computational cost that is seemingly the main advantage of DYNAMO-GAT over G2GAT is evaluated weakly on small-scale datasets whereas it would truly matter to observe a similar trend on larger graphs, as discussed above in the method and evaluation citeria section of the review.", "other_comments_or_suggestions": "While the two key metrics discussed in the paper. i.e. oveersmoothing measure and accuracy, are reported in the experiments, it may also be of value to report the pruning ratio, i.e. the number of edges pruned during training. This could reveal information on the importance of the structural information in the input graph. Furthermore, empirically analyzing the correlation of node features between which edges are removed would further verify theoretical insights.", "questions_for_authors": "1. Does DYNAMO-GAT cater to inductive settings for node classification as well? Is it also effective for graph classification tasks? \n\n2. Is there any additional hyperparameter tuning required to train DYNAMO-GAT?\n\n3. While attention coefficients learning a value of 0 effectively prunes edges, [2] analyzes the attention mechanism of GAT and shows that it suffers from trainability issues that obstructs the coefficients from learning this value during training.  Could the authors comment on this, perhaps from a dynamical systems perspective?\n\n[2] Mustafa et al. GATE: How to Keep Out Intrusive Neighbors\n\nEdit: While results on larger heterophilic datasets in [1] would add further value to the paper, I believe that the additional discussion and experiments provided in the rebuttal are sufficient for the paper to be of value to the community, particularly the method used for learning sparse attention patterns. Therefore, I have raised my score.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "0TjmOThRRD", "reviewer": "Reviewer_GAxo", "summary": "This paper introduces a refreshing perspective on the over-smoothing behavior of graph neural networks through the lenses of dynamical systems. After the establishment of the theoretical framework, a novel architecture which dynamically prunes the attention weights has been proposed and achieved state-of-the-art performance on some benchmark datasets.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the positive assessment and insightful suggestions. Below, we address the key points raised:\n\n1. **Evaluation on Larger and More Realistic Datasets:**  \n    As noted in our response to Reviewer kxJk (see the table provided therein), we have extended our evaluation to larger-scale benchmarks such as ogbn-arxiv and ogbn-products. These additional experiments reinforce that DYNAMO-GAT not only scales effectively but also achieves a superior accuracy-to-complexity trade-off compared to baseline methods. We will ensure these extended results are clearly presented in the final manuscript.\n\n2. **Comparison with Alternative Anti-Oversmoothing Methods:**  \n    We appreciate the suggestion to compare our approach with stochastic and residual anti-oversmoothing strategies. While our current experiments primarily focus on demonstrating the benefits of dynamic, noise-driven pruning in terms of increasing the spectral gap and preserving node diversity, we will add a discussion in the revised manuscript that contextualizes our method within the broader literature. This discussion will highlight the unique advantages of our approach relative to other strategies.\n\n3. **Testing on Physical/Chemical Datasets:**  \n    The idea of evaluating DYNAMO-GAT on physical/chemical datasets is very interesting and represents a promising direction for future work. Oversmoothing is indeed a significant challenge in these domains, and we believe our method could offer substantial benefits. We plan to explore this avenue in our future studies.\n\nWe thank the reviewer again for the constructive feedback and believe that these additions and clarifications will further strengthen our work.", "claims_and_evidence": "The claims are supported theoretically and experimentally.", "methods_and_evaluation_criteria": "Yes. Although more thorough benchmark using larger and more realistic graph datasets is encouraged.", "theoretical_claims": "Yes. They seems sensible to me.", "experimental_designs_or_analyses": "Yes. They look reasonable, although I would also compare the over-smoothing behavior with the rich literature of anti-over-smoothing methods, both stochastic and residual.", "relation_to_broader_scientific_literature": "This paper would be highly relevant to the graph modeling community.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "NA", "other_comments_or_suggestions": "NA", "questions_for_authors": "Would you consider testing this method on physical/chemical datasets where over-smoothing is well known to have caused many problems?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MtolCZ5a4a", "reviewer": "Reviewer_kxJk", "summary": "The paper provides a new controlling method to steer away node embeddings falling into oversmoothing state during propagation compared with existing method such as G2-gating. This controlling method specifically target for graph attention based method with the gradual pruning highly correlated connection trick to increase the spectral gap and avoid oversmoothing. The paper provides a comprehensive theoretical analysis from spectral analysis for the fixed point to show the largest impact of oversmoothing is spectral gap and therefore propose to prune highly corrected connection to increase such gap and avoid trapping into oversmoothing state. Empirically, three dataset are used to verify the performance of the proposed method with existing baselines, showing competitive performance and methods alleviate oversmoothing.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the constructive feedback and are pleased that our theoretical analysis and overall approach were well received. Below, we address the main concerns:\n\n1. **Limited Empirical Evaluation on Real-World Datasets**  \n    We agree that evaluating on larger-scale datasets is important. To that end, we extended our experiments to include OGB benchmarks (ogbn-arxiv and ogbn-products) as well as LRGB datasets. The additional results are summarized below:\n\n| Dataset | Model | Accuracy (%) | GFLOPS | Accuracy/GFLOPS |\n| ----- | ----- | ----- | ----- | ----- |\n| ogbn-arxiv | GCN | 71.9 | 12.5 | 5.75 |\n| ogbn-arxiv | G2GAT | **72.5** | 10.3 | 7.04 |\n| ogbn-arxiv | **DYNAMO-GAT** | 72.1 | **6.7** | **10.76** |\n| ogbn-products | G2GAT | 73.9 | 22.1 | 3.34 |\n| ogbn-products | **DYNAMO-GAT** | **75.3** | **14.5** | **5.19** |\n\n     \n   These results not only confirm that DYNAMO-GAT scales to larger graphs but also highlight its computational efficiency and improved trade-off between accuracy and complexity compared to baseline methods.\n\n2. **Relation to Broader Literature and Essential References**  \n    We appreciate the suggestion to discuss the work by Jin and Zhu (2024) on Graph Rhythm Networks, which employs a learned metric to preserve Dirichlet energy. In our revised manuscript, we will include a detailed discussion comparing our dynamic, noise-driven pruning approach to learned-metric techniques. This will emphasize that our method complements these approaches by directly addressing oversmoothing via enhanced spectral gap control.\n\n3. **Clarification on Pseudocode – “Output After Pruning \\= 0”**  \n    We thank the reviewer for highlighting the ambiguity in the pseudocode. The phrase “after pruning \\= 0” was a formatting artifact and does not imply a termination condition. Specifically:\n\n   * The intended meaning is that the final node representations are produced after the pruning process has been applied at all layers.\n\n   * There is no condition under which the pruning stops (e.g., when the pruning ratio reaches zero). Instead, the pruning rate evolves as r(t)=r0⋅(1+γt)r(t) \\= r\\_0 \\\\cdot (1 \\+ \\\\gamma t) and is applied continuously throughout the network.\n\n4. We have revised the pseudocode to remove the misleading “= 0” fragment. The corrected line now reads:  \n    **Output:** Final node representations after pruning.\n\nWe hope these clarifications, along with our extended empirical evaluation and updated discussion of related work, address the reviewer’s concerns. We believe that these improvements strengthen our manuscript and further validate the proposed method’s effectiveness and scalability.", "claims_and_evidence": "The claims is supported with comprehensive theoretical analysis. However, the empirical analysis only contains three real world datasets, which is less sufficient to provide comprehensive evidence of the proposed method.", "methods_and_evaluation_criteria": "The evaluation metric makes sense.", "theoretical_claims": "The theoretical claim is roughly checked and the conclusion should be correct as there exist several studies who also support such claims (for example, spectral gap).", "experimental_designs_or_analyses": "The soundness of the experimental designs is fine. But the dataset covered are not sufficient with only three real world datasets and none are large-scaled, hard to show its effectiveness, especially when it claims to be much efficient than G2-gating.", "relation_to_broader_scientific_literature": "The contribution of the paper is to further push the view of deep graph learning as a dynamic system design in the graph learning community.", "essential_references_not_discussed": "In the view of the dynamic system, extending the work of G2-gating from Rusch, [Jin & Zhu, 2024] has shown that a learned metric instead of fixed Dirichlet energy could also preserve Dirichlet energy and alleviate oversmoothing with competitive performance.\n\n[1] Y. Jin and X. Zhu, \"Graph Rhythm Network: Beyond Energy Modeling for Deep Graph Neural Networks,\" 2024 IEEE International Conference on Data Mining (ICDM).", "other_strengths_and_weaknesses": "The strength of the paper is it has comprehensive theoretical analysis and show strong evidence alleviating oversmoothing. The weakness of the paper is that it only has three medium scale real-world dataset covered in the experiments, making it less sufficient to show the performance for large-scale dataset with its efficiency claim.", "other_comments_or_suggestions": "None.", "questions_for_authors": "I observe that in the supplement, the pseudo code is provided, the output describes the output embedding is presented after pruning =0, what does this mean in general? How does it relate to the termination condition?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This work proposes DYNAMO-GAT, a novel pruning strategy for Graph Attention Networks that uses dynamical systems theory to mitigate oversmoothing by adaptively pruning attention weights based on noise-driven covariance analysis. This approach improves both representation quality and computational efficiency, outperforming existing methods on several benchmark datasets.
As over-smoothing is a relevant concern for GATs (and other GNNs), this work is of high relevance to the ICML community.

In the course of the rebuttal, the authors provided additional experiments for large-scale and heterophilic graphs, showing that DYNAMO-GAT scales well and maintains robustness against oversmoothing. They emphasize the generalizability of their pruning mechanism to other attention-based GNNs and support their theoretical claims with ablation studies, empirical feature similarity analyses, and stability proofs. Clarifications are made on runtime efficiency, hyperparameter robustness, and real-world applicability, reinforcing the method’s practical and theoretical contributions.

Most of the reviewers vote to accept this paper. Only Reviewer KMUB leans towards a weak reject but did not give any reasons in response to a convincing rebuttal by the authors.

Suggestions for Potential Improvements:
1. Broader Benchmarking: Initially, reviewers criticized the use of only small datasets. Though later addressed, a more thorough inclusion of large and diverse benchmarks was a consistent request.
2. Comparison with Other Anti-Oversmoothing Methods: The paper could benefit from explicit comparisons with stochastic and residual methods in the anti-oversmoothing literature.
3. Graph Sparsification Context: The authors were advised to clarify how their method differs from or complements traditional graph sparsification techniques.
4. More Metrics: Reviewers suggested reporting pruning ratios and structural impact, which the authors included post-rebuttal. However, integrating this more prominently in the main paper was recommended.
5. Real-World & Domain-Specific Applications: Testing on chemical or physical datasets where oversmoothing is problematic was proposed as a direction for future work.
6. Clarity in Pseudocode & Practical Deployment Details: Some confusion over pseudocode was flagged; reviewers appreciated clarification but suggested cleaning up such artifacts in the final version.
Decision: Accept (poster)