Enhancing Spectral GNNs: From Topology and Perturbation Perspectives
Authors: Taoyang Qin
Ke-Jia CHEN
Zheng Liu
Venue: ICML 2025 poster (2025)
Keywords: spectral GNNs
perturbation theory
expressiveness
sheaf Laplacian
Primary area: deep_learning->graph_neural_networks
TL;DR: We propose a sheaf Laplacian, which has more distinct eigenvalues and preserves the graph's topological information, enhancing the expressive power of spectral GNNs.

Abstract: Spectral Graph Neural Networks process graph signals using the spectral properties of the normalized graph Laplacian matrix. However, the frequent occurrence of repeated eigenvalues limits the expressiveness of spectral GNNs. To address this, we propose a higher-dimensional sheaf Laplacian matrix, which not only encodes the graph's topological information but also increases the upper bound on the number of distinct eigenvalues. The sheaf Laplacian matrix is derived from carefully designed perturbations of the block form of the normalized graph Laplacian, yielding a perturbed sheaf Laplacian (PSL) matrix with more distinct eigenvalues. We provide a theoretical analysis of the expressiveness of spectral GNNs equipped with the PSL and establish perturbation bounds for the eigenvalues. Extensive experiments on benchmark datasets for node classification demonstrate that incorporating the perturbed sheaf Laplacian enhances the performance of spectral GNNs.

Enhancing Spectral GNNs: From Topology and Perturbation Perspectives
Taoyang Qin Ke-Jia CHEN
Zheng Liu
Abstract
Qee
Spectral Graph Neural Networks process graph signals using the spectral properties of the nor- malized graph Laplacian matrix. However, the frequent occurrence of repeated eigenvalues lim- its the expressiveness of spectral GNNs. To address this, we propose nigher-dimeesiooal sheaf Laplacian matrix, which not only encodes the graph's 's topological information but also in- creases the upper bound on the number of dis- tinct eigenvalues. The sheaf Laplacian matrix derived from carefully designed perturbations of the block form of the normalized graph Lapla- cian, yielding a perturbed sheaf Laplacian (PSL) matrix with more distinct eigenvalues. We pro- vide a theoretical analysis of the expressiveness of spectral GNNs equipped with the PSL and es- tablish perturbation bounds for the eigenvalues. Extensive experiments on benchmark datasets for node classification demonstrate that incorpo- rating the perturbed sheaf Laplacian enhances the performance of spectral GNNs.
14
2
graph (V,5)
Block gragh Laplorian
perturded shouf Lophasion By (noersttio))
Live L
Figure The perturbed sheaf Laplacian DF can be viewed as special perturbation of Latock (C is the normalized graph Lapla- cian, denotes the Kronecker product, I is the d x d identity matrix, and all restriction maps are orthogonal). Specifically, for each (v, 2) E, if e+ slightly deviates from the identity I while satisfying the sheaf Laplacian constraints, the resulting matrix is both valid normalized sheaf Laplacian and perturbed version of Lstock-
Wang and Zhang (Wang & Zhang, 2022) highlight the issue of repeated eigenvalues and propose an orthogonal Jacobi basis approach in which each prediction dimension has a flexible filter design. However, the individual filter design does not fully resolve the performance degeneracy caused by different eigenvectors sharing the same eigenvalue. Lu et al. (Lu al., 2024) tackle the issue by adding a diagonal matrix of uniformly sampled eigenvalues the normalized Laplacian matrix. The polynomial filters integrated with the corrected eigenvalues yield improved node classifica- tion results. Although this method helps mitigate repeated cigenvalues, it also compromises the original topological information encoded in the normalized Laplacian matrix by reducing the operator's 's spectral gap. which reflects graph's connectivity and information flow (see Appendix F.2).
1. Introduction
Both spatial and spectral Graph Neural Networks (GNNs) have shown outstanding performance in various graph tasks (Kipf & Welling, 2017; Gilmer et al., 2017: Huang et al., 2023; Jin et al., 2024). Unlike spatial GNNs, spectral GNNs conduct frequency-domale convolution on normal- ized Laplacian matrices of graphs. However, in most graph datasets, the multiplicity of eigenvalues of the normalized graph Laplacian matrices is not small. The repeated eigen- values limit the expressive power of spectral GNNs, result- ing in a deteriorated performance (Wang & Zhang, 2022; Lu et al., 2024).
Besides the above issues, both works focus only linear settings, leaving the impact of nonlinear activation function unexplored.
We focus on the challenge of repeated eigenvalues a non- linear context. We propose to utilize a higher dimensional sheaf Laplacian matrix, which guarantees a higher upper bound on the number of distinct eigenvalues (Hansen & Ghrist, 2018; Hansen, 2020). Specifically, we normalize the sheaf Laplacian matrix by applying perturbation on the block form of the normalized graph Laplacian matrix. The designed perturbation of the identity matrix serves as the restriction map, which increases the diversity of eigenvalue
School of Computer Science, Nanjing University of Posts and Telecommunications. Nanjing, China Jiangsu Key Laboratory of Big Data Security & Intelligent Processing, Nanjing, China. Cor- respondence to: Ke-Jia CHEN <chenkj @ww.er.cuu.uu......... Zheng Liu <zliu@njjpt.edu.cn>>
Proceedings of the 1nnd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Enhancing Spectral GNNs: From Topology and Perturbation Perspectives
while retaining the topological information of the normal- ized Laplacian matrix (as shown in Figure 1). To summa- rize, our contributions are as follows:
where g is the filter function, W is learnable weight ma- trix, Og is trainable coefficient for the k-th order poly- nomial approximation, and yp is function like multi-layer perceptrons (MLPs).
We propose a perturbed sheaf Laplacian (PSL) matrix which has more distinct eigenvalues by carefully de- signing the perturbation on the basis of perturbation theory.
Note that, if is a linear function, spectral GNNs are termed linear spectral GNNs; if yp is a nonlinear function, they are termed nonlinear spectral GNNs.
We achieve optimal model performance by applying the PSL matrix on popular spectral GNNs architec- tures and optimizing the perturbation process.
2.2. Theory of Cellular Sheaves
The theory of cellular sheaves, rooted in algebraic topol- ogy, has been incorporated into GNNs additionally aug- ment the graph's topological structure and thereby improve the performance of GNNs (Bodnar al., 2022; Duta et al., 2023a).
We theoretically analyze the expressiveness of the PSL-based GNNs, and characterize the impact of the perturbations by establishing the perturbation bounds for the eigenvalues.
Definition 2.1. A cellular sheaf (G,F) over undirected graph G (V, consists of:
Experiments on benchmark datasets demonstrate the supe- riority of PSL-based spectral GNNs. The increased num- ber of distinct eigenvalues of the learned perturbed sheaf Laplacian matrices validates the effectiveness of the pro- posed perturbation method.
vector space F(v) associated with each node v E V.
vector space F(e) associated with each edge e E E.
2. Preliminaries
linear map Fuge for each incident node-edge pair v I mapping vectors from F(v) to F(e).
This section provides brief introduction to spectral GNNs and highlights the key aspects of the theory of cellular sheaves. All important notations are given in Appendix A.
Here, the vector spaces for nodes and edges are termed stalks, and the linear maps between them are termed re- striction maps. We set all the stalks to be Bd and confine all restriction maps to orthogonal mappings. The restriction map Fuge F(v) to edge stalk and FT "gge F(e)) F(v) maps vectors from edge stalk to node stalk. It follows that FT Fos((a)) F maps vectors from F(u) to F(u), where (u, u) E E.
2.1. Spectral Graph Neural Networks
Spectral GNNs build on spectral graph theory (Chung, 1997), which applies the graph Fourier transform de- fine frequency-domain convolutions. For a graph G = EV,E) with nodes, the normalized Laplacian is L = -- 2-D2AAD AD- E. Its eigendecomposition is L UAUT. where A is diagonal and U holds the eigenvectors. The graph Fourier transform of signal X E RF is X = U"X, with each row of X representing a distinct fre- quency component. The output of a spectral convolution can be expressed as:
F(e) maps vectors from node stalk
Definition 2.2. The sheaf Laplacian matrix of a sheaf over an undirected graph G = (V,E) is a block matrix Ly. The diagonal blocks are LF. = Evge F. while the non-diagonal blocks are LI -FT Fuges where (c, u) E.
Z - g * X
OUTX)) UÊUTX (1)
The sheaf Laplacian matrix is positive semidefinite, which means that the eigenvalues non-negative (Hansen, 2020; Bodnar et al., 2022). Additionally, when all the re- striction maps are identity maps, the sheaf Laplacian ma- trix degenerates into the block form of the graph Laplacian matrix.
where g is the spatial kernel, and & = diag(g),.... Bn)
denotes the spectral kernel coefficients. For spectral GNNs, a polynomial function is commonly used approximate different kernels, which can be expressed as follows:
Z ((Ug(A))*XXW)
Definition 2.3. The normalized form of the sheaf Lapla- cian matrix is given by Σ5 = D C 2, where D, = LF,ve and the diagonal matrix of the sheaf Laplacian ma- trix is diag( DD....,D, D,))
= P(U
Σ k=
U ("XW)
K
= p
L² xXW,,
In the following, we will refer to the normalized sheaf Laplacian matrix simply as the sheaf Laplacian.
k km0
2

---

Enhancing Spectral GNNs: From Topology and Perturbation Perspectives
x,1
Xx
s(A)
1.45A
s(A)x
0.69 1883
apply a(A)
m
mouldiply by
Oa Bas
0:2 01.
0.03
apply
filtering out
0.69
Jon Rus
s(A)
a(A)X
filter fanction
0.65A
0.09 1.8 A
(a) Limited predictive ability.
(b) Loss of frequency components.
Figure 2. X is the graph data, and Xx its Fourier-transformec matrix. is the filter function. (a) Because the graph has only two distinct nonzero eigenvalues, each element in Z is linear combination of just two types of frequency components, thereby limiting the expressive power of spectral GNNs. (b) Poorly designed filter functions can lead to the loss of frequeney components, thereby limiting the expressive power of spectral GNNs.
3. Motivation
ues of the normalized graph Laplacian matrix. The proof is in Appendix B.
In this section, we summarize and extend the discussion of repeated eigenvalue issues as presented by Wang and Zhang (Wang& & Zhang, 2022) and Lu et al. (Lu et al., 2024), which contribute to the motivation for our work.
3.2. Loss of Frequency Components
Another issue caused by repeated eigenvalues is that if the filter function g(A) poorly designed, setting a specific eigenvalue to zero can lead to the disappearance of cor- responding frequency components (As shown in Figure 2 (b)).
3.1. Limited Predictive Ability
The phenomenon of repeated eigenvalues limits the predic- tive ability of spectral GNNs, thus affecting their expres- sive power (as shown in Figure (a)). Firstly, we use lemma to describe this issue.
Interestingly, for many commonly used graph datasets, the eigenvalue 1 of the corresponding normalized graph Lapla- cian matrix has the highest multiplicity (see Appendix F.5 for details). This observation may also provide new per- spective on why adding self-loops to the adjacency matrix leads to better GCN performance certain datasets (Kipf & Welling, 2017; Wu et al., 2019). Given that the filter function of GCN is 1 >, it filters out all frequency com- ponents associated with the eigenvalue 1. By introducing self- the distribution of eigenvalues is altered, thereby causing GCN to lose fewer frequency components.
Lemma 3.1. When there are only k distinct eigenvalues of the normalized Laplacian matrix, linear spectral GNNs can produce most k different filter coefficients, and thus can only generate oie-dimensional predictions with max- imum of k arbitrary elements.
The proof of this lemma can be found in Appendix A.1 of Lu et al. (Lu et al., 2024). This lemma reveals key problem: the predictive ability of linear Spectral GNNs is limited by the number of distinct eigenvalues of the nor- malized graph Laplacian matrix.
3.3. Restricted Frequency Processing Capability
In this paper, we extend the lemma to the case of nonlinear spectral GNNs which use an activation function (Rosen- blatt, 1958; Nair & Hinton, 2010: Goodfellow et al., 2016). Theorem 3.2. When there are only k distinct eigenvalues the normalized Laplacian matrix, and the nonlinear real- valued function satisfies ozx) # O for + O, nonlinear spectral GNNs can produce at most k different filter coeffi- cients, and thus can only generate one mindinensio predic- tions with a maximum of k arbitrary elements.
The phenomenon of repeated eigenvalues also restricts the frequency processing capability of spectral GNNs. Con- sider X = U XW, where g(A) represents the filter- ing function, with A being the eigenvalue matrix of the normalized Laplacian. Evidently, g(A) is equivalent to g(A:)o where g(A:) scales each X; element-by- element. Thus, for identical eigenvalues A = Aj. the asso- ciated frequency components X; and X, are scaled by the same factor, which limits the expressiveness of the spectral GNNs.
Theorem 3.2 shows that, even with real-valued activation functions such as tanh and sigmoid, the predictive ability of nonlinear spectral GNNs remains equivalent to that of linear spectral GNNs, both of which are similarly limited. This limitation arises from the issue of repeated eigenval-
3.4. Why Perturbed Sheaf Laplacian
The solution to the above issues is to construct Laplacian matrix with more distinct eigenvalues. The sheaf Lapla-
3

---

Enhancing Spectral GNNs: From Topology and Perturbation Perspectives
Preproceading of Graph Data
Construction of Perturbed Sheaf Laplacion
X1
X
perforlanon
Cuuck C Ta
Node Fenturea X
XW;
Converted X
PSL
CNN
X,
nggregation.
X
reshape
orgin
X3
map
X,
f1
f2 d f5
fs
Converted
based EF
Figure 3. Model workflow: The convert operation initially reduces feature dimensionality and reshapes the input to X E Rudx The I-th aggregation step, "v is performed as Combine(Z,=" X(),, W After final aggregation, and the convert operation means reshaping the output back to n rows of x columms, followed by linear transformation to yield with columns equal the number of node classes.
cian is from the theory of cellular sheaves. When applied to graphs, the sheaf Laplacian naturally provides a larger set of eigenvalues while maintaining positive semidefinite nature and the eigenvalue range in [0, 2] (Hansen, 2020).
4.2. Construction of Perturbed Sheaf Laplacian
When there exists a restriction map that is not an identity map, Cx can be viewed as the result of a special pertur- bation applied to the block form of the normalized graph Laplacian matrix Loteck- For each block element Lytock the corresponding perturbation matrix Qij Fise is applied, resulting in Cy. According to Section 3.4, when F Fige slightly deviates from the identity matrix, the corresponding sheaf Laplacian matrix regarded as per- turbed sheaf Laplacian matrix.
We carefully design the restriction map slight pertur- bation of the identity matrix in order to construct sheaf Laplacian with more distinct eigenvalues. We call it the perturbed sheaf Laplacian (PSL). The perturbed sheaf Laplacian matrix achieves two advantages: (1) By align- ing with perturbation theory, the PSL matrix increases the eigenvalue diversity; (2) the PSL matrix is structurally close to the normalized graph Laplacian matrix, retaining its topological information.
Based on this, Qij can be viewed as a perturbation applied to Loteck To ensure that the overall perturbation effect increases the number of distinct eigenvalues of Ly, we pro- pose the following theorem to guide the perturbations.
4. Method
Theorem 4.1. Let P = IF Lbtock be the perturbation matrix applied to Litock, and let & = mink iæt where d the eigenvalues of Lotock- If |||| J. then the multiplicity of eigenvalues of L will decrease.
This section introduces the proposed PSL-GNN model (with its general workflow illustrated in Figure 3). The complexity of our method is illustrated in Appendix F.l.
|A; Ayl-
The proof is in Appendix B. According to Theorem 4.1, to reduce the multiplicity of eigenvalues, the orthogonal matrices of different blocks should be restricted to slightly deviate from the identity matrices. Considering that the flection matrix deviate from the identity matrix to vary- ing extents by adjusting the reflection vector, we constrain every restriction map to the reflection matrix. Specifically, u.
4.1. Preprocessing of Graph Data
To make the first dimension of the input matrix Xo E gaxfi compatible with the second dimension of the sheaf Laplacian matrix Ly E Rnndxnd, we first apply linear projection:
XoW, E fo
(3)
where W1 E Rfx with fa d fo. Next, reshape the resulting matrix:
we assign every restriction map to Fig(t.J) = - 2 || where Uy is vector of dimensions d (d represents the dimension of the stalks). Here, Ui is parameterized and learnable, allowing Qij to deviate from the identity matrix. To ensure that the applied perturbations remain minimal, we constrain each component of u.j within [ ni for the reflection matrix, where 7) is sufficiently small value.
= R(XWi, fd)
(4)
where R(Xg f represents reshaping W, into a matrix with nd rows and fa columns.

---

Enhancing Spectral GNNs: From Topology and Perturbation Perspectives
4.3. PSI.-GNN: Perturbed Sheaf Laplacian-Based Graph Neural Network
5. Theoretical Analysis
In this section, we conduct a theoretical analysis of the ex- pressive power of PSL-GNN and establish the perturbation bounds of the eigenvalues. All proofs are in Appendix and Appendix D.
The proposed perturbed sheaf Laplacian matrix can be in- tegrated with any spectral GNNs. In this section, apply it within the GCN (Kipf& & Welling, 2017) and GPRGNN (Chien et al., 2021) respectively as examples.
5.1. Expressiveness of PSL-GNN
4.3.1. PSL-GGN
We first discuss the expressive power of the block matrix form Lolock of the normalized graph Laplacian matrix L. Proposition 5.1. The number of distinct eigenvalues of Lstock E Rndxxd is the same as that of L E IR"x", where C is the normalized graph Laplacian matrix and Litock = L @ I, with I E TRuxd being the identity matrix. Also, their corresponding GNNs, which share the same ar- chitecture, are mutually equivalent.
The architecture of GCN often represented as:
x = a(T (T- A)x;"W).
(5)
where A represents the normalized graph Laplacian ma-
trix, 7 denotes the layer index, and ( represents the fea- ture matrix at layer l. Through integration, we obtain PSL- GCN, which can be expressed as follows:
(6) where ((+1) E Ran fa and (1) E Radxfa AF E Radxnd is the PSL matrix, and W2 E R is the pa- rameter matrix used for linear transformations within the network.
( ((1 - - W
Proposition 5.1 indicates that when the applied orthogonal
matrices the identity matrices, PSL-GNN is equivalent to the corresponding GNN.
Corollary 5.2. PSL-GNN has stronger one-dimensional prediction ability.
We need reshape the output of the last layer and perform series of transformations such as Winst E RR X and R to obtain the final prediction matrix Z:
For a given normalized graph Laplacian matrix, its PSL. possesses a greater number of distinct eigenvalues, which underpins its enhanced predictive ability.
Z = R(x (last) p Baxdfist W Wiast-
Corollary 5.3. PSL-GNN loses fewer frequency compo- nents.
4.3.2. PSL-GPR
With fewer repeated eigenvalues than the normalized Laplacian, PSL-GNN remains robust even if high- multiplicity frequency components are discarded.
The structure of GPRGNN is represented as follows:
K
7
Σ aI -.)* Xo:
Corollary 5.4. PSL-GNN has a stronger capability in pro- cessing frequency components.
where Xo E Raxsi represents the feature matrix, and L represents the normalized graph Laplacian matrix. Accord- ing to Equation (4), we have the converted feature matrix X fs, Following the architecture of GPRGNN, our model, namely PSI.-PR, is expressed as:
The PSL possesses a greater number of distinct eigenval- ues, allowing a more diverse treatment of frequency com- ponents.
5.2. Perturbation Bounds of Eigenvalues
K
We establish the perturbation bounds for the eigenvalues based on perturbation theory (Weyl, 1912; Dailey et al., 2014).
Y - - xx
(9)
In this equation, Y E Radx represents the output feature matrix, I Radxnd is the identity matrix, Ey Radxnd is the PSL matrix, K is the order of the polynomial, and os are the trainable coefficients.
Theorem 5.5. Let Lotack and Cy = = Lotock be N N symmelric positive semidefinite matrices, with eigenvalues Ai,..., AN and Ai....,As, respectively, where Lotock is diagonally dominant. Suppose the perturbation matrix P satisfies |Pyll S e((Loiock))) for all i + j for all i, where 0 <<< <<< J. Hence, for each i, A7 - >4 S T Xmax-
We reshape Y into R=x and apply a linear transforma- tion with W3 E xe to obtain the final prediction matrix Z E gaxe, where e represents the number of classes. This process can be expressed as:
2x
As the size of the perturbation 77 decreases, the correspond- ing e also decreases, resulting in a smaller range of eigen- value perturbations.
R(Y, TR. n Ws
(10)
5

---

Enhancing Spectral GNNs: From Topology and Perturbation Perspectives
6. Experiment
of frequency components: Unlike the variable filter func- tions in other baselines, the GCN filter function is fixed, ie., g(A) 1 X, where À represents the eigenvalue of the normalized graph Laplacian matrix. The multiplicity of À = 1 is relatively high (see Figure 5 for details), which leads to a significant loss of frequency components corre- sponding to À = 1, thereby severely affecting the expres- sive power of spectral GNNs, In contrast, the perturbed sheaf Laplacian can reduce the multiplicity of À 1, re- sulting in higher average gain.
In this section, we give the results of the performance com- parison between PSL-GNN and GNN baselines on the node classification task. Besides, we validate the effectiveness of the proposed perturbed sheaf Laplacian matrix through ablation studies. We also perform a statistical analysis of the independent eigenvalues of the final learned perturbed sheaf Laplacian matrices. The experimental setup is in Ap- pendix E. Additional experimental studies can be found in Appendix F.
6.2. Ablation Study
6.1. Evaluation on Real-World Datasets
To further study the effectiveness of the perturbed sheaf Laplacian matrix, we compare it with both the general sheaf Laplacian matrix (GSL) (Bodnar et al., 2022) and the normalized graph Laplacian matrix.
We conduct experiments on 7 benchmark graph datasets (all information about the datasets is summarized Ap- pendix E.2.), and the results are presented in Table I. We evaluate the accuracy of the PSL-GNNs by compar- ing them with their corresponding GNN models. We also calculate the vertical average gain (VAG) of the perturbed sheaf Laplacian matrix for all models on each dataset. The formula for VAG is given as follows:
The construction of the GSL involves using d(d-1) param- eters to generate each restriction map Fuse. Besides, cach parameter is no longer constrained by 17. Based on the above setup, the restriction maps are allowed to fully ex- plore the orthogonal group. For the construction of normal- ized graph Laplacian matrix, we set 1) O, which means no perturbation is applied. Consequently, the perturbed sheaf Laplacian matrix degenerates into the block matrix form of the normalized graph Laplacian matrix. We integrate these three types of Laplacian into vanilla GNN, creating PSL- GNN, GSL-GNN, GNN (vanilla). Subsequently, we com- pare their performance on node classification. All mod- els share the same parameters, except 1), which is tuned for PSL-GPR and PSL-GCN (fle-1, le 1e-2, 1, le-4)) and set to 0 for GPR-GNN and GCN. This ensures fair and reliable comparisons.
VAG
1 M
Σ M.EM
(ACC(m(()))ACC(m( - (CC(),
(11) where M is the set of GNN models, ACC is the short form of accuracy, G is the original graph, and F is a sheaf over the graph. We also calculate the horizontal average gain (HAG) of the perturbed sheaf Laplacian matrix for all datasets on each model. The formula for HAG is given as follows:
HAG Σ - (12) d,DD
D
We conduct multiple training runs and averaged various metrics to obtain the reliable results in Table 2. The re- sults demonstrate that: (1) GSL-GNN outperforms vanilla GNN, probably because the general sheaf Laplacian gen- eralizes the graph Laplacian, offering greater learnability and flexibility for downstream tasks; (2) The performance of PSL-GNN is comparable to that of GSL-GNN. It indi- cates that the structure learned by the general sheaf Lapla- cian might align closely with that learned by the perturbed sheaf Laplacian.
where 'D is the set of used datasets.
By analyzing the results in Table 1, we have the follow- ing observations: (1) All models are enhanced by the per- turbed sheaf Laplacian matrices. This improvement can be attributed to the fact that the perturbed sheaf Laplacian ma- trices have more distinct eigenvalues. Consequently, the PSL-GNNs have stronger capability to handle various fre- quency components, thereby improving their performance in the node classification task; (2) For Texas and Cornell, which are characterized by a relatively small number of nodes, the performance improvement is particularly sig- nificant. The observed phenomenon can be attributed to the inherently lower structural stability of smaller graphs, which makes them more sensitive to perturbations. This heightened sensitivity facilitates the splitting of eigenval- ues into distinct values, thereby significantly increasing the number of distinct eigenvalues; (3) The GCN shows the highest average gain compared to other basclines. This can be explained from the perspective of suppressing the loss
6.3. The Number of Distinct Eigenvalues
We measure the number of distinct eigenvalues for both the normalized graph Laplacian matrix and the final learned perturbed sheaf Laplacian matrix when 17 2 1e-3, respec- tively. In Table 3, No denotes the number of distinct eigen- values of the normalized graph Laplacian matrix, while the other entries represent the number of distinct eigenvalues of the learned perturbed sheaf Laplacian matrix. As the
6

---

Enhancing Spectral GNNs: From Topology and Perturbation Perspectives
Table I. Experimental results on node classification task: mean accuracy (%) +95% confidence interval.
Datasets
Cora
Pubmed
Citeseer
Photo
Corell
Texas
Actor
HAG
GCN
66.62+1.06
20.51
75.32+1.91 76.75+2.32
87.52+0.58
75.32=1.98
18.12
34.23+1.54
1.93
PSL-GCN
88.09
88.21
90.12a0.90
77.89=2.45
80,45a2.21
35.67
APPNP
88. 11
87.39 8.89
76,34
90.23++0.00
78. 78,56=2.01
80.122183
34.89&1.73
1.05
PSL-APPNP
89.03+1.79
88,23+2.79
76.92+2.36
90.58+0.94
79.89+2.37
82.34+2 19
36.01+2.11
Graph-Heat
86.85+1.29
87.1221.69
74.75+2.44
89.3220.74
75.78=1.88
79.4521.72
34.01=1.62
1.22
Hea-
87.38s1.75
88.74=2.42
76.72+2.52
89 29.44
77.34:2.29
80.67=2.14
35.5621.94
BernNet
88,29 38.2920.63
88.50 18.50
76.78200.49
94.02+1.26
86,23a2.14
85.67=1.99
36.12a1.49
1.13
PSL-BernNet
89.67a1.79
89.54=2-40
77.4612.38
94.1920.94
88,34
86,8922.32
37.45a1.91
GPRGNN
87.59x1.31
88.01a1.14
76,8321.67
92.98a1.09
86,32a2.11
85,17a1887
36.42a1165
1.21
PSL-GPR
88,45s1.48
89.11s1.89
77.42x2.02
94.23
88.6742.33
86,4522.04
37.45x1,92
Jacobi
88.8 1.66
88, 03:0.75
76.89+1.44 84
93.72+1.53
87,11 =22.07
84,45=1196
36,56+1.78 37.78a2.05
1.08 1
PSL-Jacobi
89.01
89.02a2.42
77.71+2.50
94.43+0.96
88.98:2.42
86,23
VAG
0.89
1.22 f
1.01 f
0.86 1
1.96 f
1.68 1
1.28 1
table shows, the number of distinct eigenvalues of the per- turbed sheaf Laplacian matrix significantly exceeds that of the normalized graph Laplacian matrix.
values of normalized graph Laplacian matrix.
7.2. Sheaf Neural Networks on Graphs
Sheaf Neural Networks (SNNs). introduced by Hansen and Gebhart (Hansen & Gebhart, 2020), extend graph neural networks by using the sheaf Laplacian matrix for dealing with non-constant, heterogeneous, and signed node rela- tionships. Building on this foundation, Bodnar et al. (Bod- nar et al., 2022) apply sheaf Laplacian matrix to address heterophily and oversmoothing problems in graph neural networks. This is achieved by concatenating node features as parameters, which are then used construct restriction maps. Barbero et al. (Barbero et al., 2022) generate sheaf Laplacian matrix through pre-trained approach, which is suitable for manifold data and effectively incorporates the underlying geometric characteristics of the data. Duta et al. (Duta et al., 2023b) construct the hyper sheaf Laplacian to capture both linear and non-linear diffusion by selecting the most discrepant feature pairs within hyperedges. Bat- tiloro et al. (Battiloro et al., 2024) use VDM (Singer & Wu, 2012) to construct the sheaf Laplacian and design tangent bundle filter. This method requires a large amount of spe- cialized data and involves high complexity. Our method simplifies the process by perturbing the block form of the normalized graph Laplacian, which has been proven both efficient and effective.
7. Related work
In this section, we outline the research developments re- lated to the issues of interest, along with the background and tools employed.
7.1. Expressiveness of GNNs
The research on expressive power of GNNs originates from the Weisfeiler-Lehman (WL) test for graph isomorphism (Weisfeiler & Leman, 1968). Building on this foundation, GIN (Xu et al., 2019b) establishes a direct connection be- tween the expressive power of GNNs and the I-WL test. Since then, various works have attempted to analyze GNNs with the WI. test and graph isomorphism testing (Morris et al., 2019; Maron et al., 2019a; Chen et al., 2019; Zhang et al., 2021). Besides, some studies measure the expres- sive power of GNNs by using alternative approaches, such as expressing universal invariant functions (Maron et al., 2019b) and counting graph's substructures (Chen et al., 2020). Balcilar et (Balciar et al.. 2021) first analyze the expressive power of GNNs from a spectral perspec- tive. Wang and Zhang (Wang& & Zhang, 2022) show that the number of distinct eigenvalues in the normalized graph Laplacian matrix impacts the expressive power of linear spectral GNNs. Besides, they also build bridge between the expressive power of spectral GNNs and 1-WL test. Lu et al. (Iu et al., 2024) further analyze that the presence of repeated eigenvalues imposes limitations on the predictive ability of linear spectral GNNs. In this paper, we summa- rize and extend the work of Wang and Zhang, as well Lu et al., to address the limitations posed by repeated eigen-
7.3. Eigenvalue Perturbation Theory
Early research mainly focuses on eigenvalue perturbation of general symmetric matrices. Tools such as Weyl's the- orem (Weyl, 1912) and Gershgorin's disk theorem (Ger- schgorin. 1931) are applied to derive the fundamental ef- fects of perturbations on eigenvalues. Due to the stability of semidefinite matrices and diagonally dominant matrices,
7

---

Enhancing Spectral GNNs: From Topology and Perturbation Perspectives
Table Comparison of models based on three Laplacian matrices (GNN GSL--GNN PSI-GNN): accuracy (%) #95 (%)
on seven datasets.
Datasets
Cora
Pubmed
Citeseer
Photo
Texas
Cornell
Actor
GCN
86.81111
86.4110.8
75.4
87.6.1.5
1.
75.2
34.1
GSL-GGN PSL-GCN
87.6100.
86.91220
76.4
89.4
80.1 13
77.7
35.3
88.1+008
87.9+18
77.4+18
90.1=1.1
80.2=1.7
77.8+14
35.5+22.2
APPNP
88.0+1.5
87.4+0.9
76.2+1.5
90.1=0.6
78.5+2.0
80.1+1.6
34.9+1.5
GSL-APPNP
89.011.4
88.
77.022.6
90.620.9
79.9=2.1
82,4:2.5
36.022.
PSL-APPNP
89.0a1.1
88.0a2.6
77.0a2.3
90.3=1.0
79.7a2.1
82.3a1.9
36.0216
Graph- Heat
86.6+1.4
87.1+1.6
74.8+2.5
89. 89.2=1.1
75.8+2.0
79.3+1.
34.0+1.6
GSL-Hleat
87.4+1.8
88.7.2.5
76.612.2
89.4=1.3
77.4=1.9
80.7a2.1
35.622.1
PSL-HHeat
87.2+1.4
88.3+1.8
76.712.4
89.1
76.6=2.9
80.4
35.3a1.9
BerNeet
88.2+0
88.4+1.3
76.640.7
94,0=1.2
86.3+1.9
85.8+1.4
36.0=1.6
GSL-BernNet
89.7+1.6
89.5+2.4
77.6+2.0
94.1=1.0
88.3=2.4
86.8=1.7
37.3+2.2
PSL-BerNNet
89.9
89.7+1.9
77.3+1.8
94.2a1.0
88.4=2.8
86.9=1.2
37.5+2.3
GPRGNN
10.9
87. 87.9+1.1
76.721.5
92.8=1.2
85 $5.2=1.7
86.2+2.1
36.321.5
GSL-GGR
88.1+1.1
88.6+2.2
76,8+1.9
93.6=1.0
86.1=1.8
87.8=2.0
36.7+2.4
PSL-GPR
88.4+1.2
89.3+1.6
77.4+1.8
93.2=1.6
86.7=1.5
88.2+2.4
37.0+2.5
Jacobi
88. 7+1.4
88.0+0.7
76.7+18
93.6=1.3
87 97.4+1.
84.2+2.1
36.5+1.7
GSI-JJccbi
89.0+1.8
89.142.2
77.7+2.2
94.4=1.0
89.0+2.3
86.3+2.0
37.7+20
PSI--Jacoii
89.0+1.4
89.3+1.9
77.8+2.3
94.2=1.3
88.9=2.4
86.6=1.1
37.8+1.5
Table 3. Distinct cigenvalues statistics of normalized Laplacian on real-world datasets across multiple training runs using PSL-GNN models (95% confidence interval).
Datasets
Cora
Pubmed
Citeseer
Photo
Texas
Cornell
Actor
|
2708
19717
3327
7650
7600
NG
2262
7647
1969
7511
73
60
4837
NPSL GCN
2389233
9031
2339a43
7604a19
147=11
142216
6181a42
NPSL-APPNP
2408+31
8977+60
2300s41
7602+15
145#6
147=10
6234+37
NpsL.Hoa
2376+25
8981+54
2301=37
7604=13
145+8
148+9
6225:40
Nest-BenNa
2434236
9018a56
2308a35
7609a10
144a13
14926
6240246
NPSL-GPR
2436:35
9024a57
2311434
7603219
145+12
148+7
6243245
2442436
9030+58
2316435
7567430
147a13
15048
6249246
some works focus on establishing perturbation bounds of these two matrices. Dailey et al. (Dailey et al., 2014) con- duct in-depth research on the perturbation bounds sym- metric positive semidefinite matrices and propose strong relative perturbation bounds. For diagonally dominant trices, a strong relative perturbation bound is proposed by Bai et al. (Ye, 2009). In this paper, we primarily focus symmetric positive semidefinite and also diagonally dom- inant matrices, aiming to study the changes in their eigen- values after perturbation.
graph Laplacian, thereby improving the expressive power of GNNs. Extensive experiments on benchmark datasets demonstrate effectiveness our method, showing no- table improvements in node classification performance. Al- though approach has been validated through both the- oretical analysis and experiments, further exploration is quired to fully reduce the multiplicity of eigenvalues and refine the matrix construction methods. Additionally, we have not yet investigated the impact the perturbed sheaf Laplacian (PSL) on graph-level tasks, which remains an in- teresting direction for future research.
8. CONCLUSION
A Acknowledgements
In this paper, propose novel sheaf Laplacian by per- turbing the normalized graph Laplacian, which enhances the spectral GNNs. Our approach addresses the limi- tations posed by repeated eigenvalues in the normalized
We sincerely thank the anonymous reviewers for their con- structive comments and thoughtful suggestions.
8

---

Enhancing Spectral GNNs: From Topology and Perturbation Perspectives
Impact Statement
Duta, I., Cassará, G., Silvestri, F., and Lió, Sheaf hyper- graph networks. In Oh, A., Neumann, T., Globerson, A., Saenko, K., Hardt, M., and Levine, S. (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 12087-12099. Curran Associates, Inc., 2023b.
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Gerschgorin, S. Uber die abgrenzung der eigenwerte einer matrix. Izvestija Akademii Nauk SSSR, Serija Matem- atika, 7(3):749-775 1931.
References
Balcilar, M., Renton, G., Héroux, P., Gaüizèee B., Adam, S., and Honeine, P. Analyzing the expressive power of graph neural networks in spectral perspective. In Pro- ceedings of the International Conference on Learning Representations, 2021.
Giles, C. L., Bollacker, D., and Lawrence, S. Citeseer: automatic citation indexing system. In Proceedings of the third ACM conference Digital libraries, pp. 89- 98, 1998.
Barbero, F., Bodnar, C., de Oca riz Borde, H. S., Bronstein, M., Veličković, P., and Liò, P. Sheaf neural networks with connection laplacians. In ICML 2022 Workshop on Tooolooy, Algebra, and Geometry in Machine Learning, pp. 28-36, 2022.
Gilmer, J., Schoenholz, S., Riley, F., Vinyals, O., and Dahl, G. E. Neural message passing for quantum chem- istry. In Proceedings of the International Conference on Machine Learning, pp. 1263-1272, 2017.
Goodfellow, I., Bengio, Y., and Courville, A. Deep Learning. MIT Press, 2016. http:/ //ww:.
Battiloro, C., Wang, 7.,, Riess, H., Di Lorenzo, P., and Ribeiro, A. Tangent bundle convolutional learning: from manifolds to cellular sheaves and back. IEEE Transac- tions on Signal Processing, 2024.
deeplearninghook.co
Hansen, Laplacians of Cellular Sheaves: Theory and Applications. PhD thesis, University of Pennsylvania, 2020.
Bodnar, C., Giovanni, D., Chamberlain, B. P., Lio', P., and Bronstein, M. M. Neural sheaf diffusion: A topo- logical perspective heterophily and oversmoothing in gnns. In Advances in Neural Information Processing Systems, pp. 18527-18541, 2022.
Hansen, J. and Gebhart, T. Sheaf neural networks. ArXiv, abs/2012.06333, 2020.
Hansen, J. and Ghrist, R. Toward spectral theory of cel-
Chen, Z., Villar, S., Chen, L., and Bruna, J. On the equiv- alence between graph isomorphism testing and function approximation with gnns. In Proceedings of the Neural Information Processing Systems, 2019.
lular sheaves. Journal of Applied and Computational
Topology, 3:315 - 358, 2018.
He, M., Wei, Z., Huang. Z., and Xu, H. Bernnet: Learn- ing arbitrary graph spectral filters via bernstein approx- imation. In Advances in Neural Information Processing Systems, volume 34, pp. 14239-14251, 2021.
Chen, Z.,, Chen, L.,, Villar, S., and Bruna, J. Can graph neural networks count substructures? In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M. F., and Lin, H. (eds.), Advances in Neural Information Processing Sys- tems, volume 33, pp. 10383-10395. Curran Associates, Inc., 2020.
Huang, Q., Yamada, M., Tian, Y.. Singh, D., and Chang, Y. Graphlime: Local interpretable model explanations for graph neural networks. IEEE Transactions Knowl- edge and Data Engineering, 35(7))6968-699 2023. doi: 10.1 N0.1109/KKDE..22..31444444
Chien, E., Peng, J., Li, P., and Milenkovic, O. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, 2021.
Jamadandi, A., Rubio-Madrige C., and Burkholz, R. Spectral graph pruning against over-squashing and over- smoothing. In Globerson, A., Mackey, I.., Belgrave, D., Fan, A., Paquet, U., Tomczak, J., and Zhang, C. (eds.), Advances in Neural Information Processing Sys- tems, volume 37, pp. 10348-10379, Curran Associates, Inc., 2024.
Chung, F. R. K. Spectral Graph Theory, volume 92, Amer- ican Mathematical Soc.. 1997.
Dailey, M., Dopico, F. M., and Ye, Q. Relative perturbation theory for diagonally dominant matrices. SIAM J. Matrix Anal. Appl., 35:1 300--328, 2014.
Jin, G., Liang, Y., Fang. Y., Shao, Z., Huang, J., Zhang, J., and Zheng, Y. Spatio-temporal graph neural net- works for predictive learning in urban computing: A sur- vey. IEEE Transactions on Knowledge and Data Engi-
Duta, I., Cassarà, G., Silvestri, F., and Liò, P. Sheaf hy- pergraph networks. In Advances in Neural Information Processing Systems, volume 36, 2023a.

---

Enhancing Spectral GNNs: From Topology and Perturbation Perspectives
neering, 36(10):5388-5400 2024. doi: 10. 1099/D.. 2023.3333824.
Rosenblatt, F. The perceptron:
probabilistic model for information storage and organization in the brain. Psy- chological review, 65 6:386-408, 1958.
Kipf, T. and Welling, M. Semi-supervised classification with graph convolutional networks. In Proceedings of the International Conference on Learning Representa- tions, pp. 1-14,220 2017.
Sen, P., Namata, G., Bilgic, M., Getoor, L.,, Gallagher, B., and Eliassi-Rad, T. Collective classification in network data. In The Al Magazine, pp. 93-93, 2008.
Kipf, T. N. and Welling, M. Variational graph auto- encoders. NIPS Workshop on Bayesian Deep Learning, 2016.
Shchur, O., Mumme, M., Bojchevski, A., and Günnemann, S. Pitfalls of graph neural network evaluation. ArXiv, abs/181 2018.
Klicpera, J., Bojchevski, A., and Günnemann, Predict then propagate: Graph neural networks meet personal- ized pagerank. In International Conference on Learning Representations, 2018.
Singer, A. and Wu, H.-T. Vector diffusion maps and the connection laplacian. Communications on pure and ap- plied mathematics, 65(8):1067-1144, 2012.
Wang, X. and Zhang, M. How powerful are spectral graph neural networks. In Proceedings of the International Conference on Learning Representations, pp. 23341- 23362, 2022.
Lu, K., Yu, Y., Fei, H., Li, X., Yang, Z., Guo, Z., Liang, M., Yin, M., and Chua, T.-S. Improving expressive power of spectral graph neural networks with eigenvalue correc- tion. In Proceedings of the AAAI Conference on Artifi- cial Intelligence, volume 38, pp. 14158-14166, 2024.
Weisfeiler, B. and Leman, A. The reduction of a graph to canonical form and the algebra which appears therein. nti, Series, 129):12-16, 1968.
Maron, H., Ben-Hamu, H., Serviansky, H., and Lipman, Y. Provably powerful graph networks. In Wallach, H., Larochelle, H., Beygelzimer, A., d'Alché-Buc, F., Fox, E., and Garnett, R. (eds.), Advances in Neural Informa- tion Processing Systems, volume 32. Curran Associates, Inc., 2019a.
Weyl, H. V. Das asymptotische verteilungsgessez der eigenwerte linearer partieller differentialgleichuneen (mit einer anwendung auf die theorie der hohlraum- strahlung). Mathematische Annalen, 71:441-479, 1912.
Maron, H., Fetaya, E., Segol, N., and Lipman, Y. On the universality of invariant networks. In Chaud- huri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Conference on Machine Learning. volume 97 of Proceedings of Machine Learning Research, pp. 4371. PMLR, 09-15 Jun 2019b. URL https: http///pccceengg.ee mir. press/v97 /ma ron1 9a html.
Wu, F., Souza, A., Zhang, T., Fifty, C., Yu, T., and Wein- berger, K. Simplifying graph convolutional networks. In International conference on machine learning, pp. 6861-6871. PMLR, 2019.
Xu, B., Shen, H., Cao, Q., Cen, K., and Cheng, X. Graph convolutional networks using heat kernel for semi-supervised learning. In Proceedings of the 28th In- ternational Joint Conference on Artificial Intelligence, pp. 1928 1934..99..4411 AAAI Press, 2019a
McCallum, A., Nigam, K., Rennie, D. M., and Seymore, K. Automating the construction of internet portals with machine learning. Information Retrieval, 3:127-163, 2000.
Xu, K., Hu, W. Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In International Conference on Learning Representations, 2019b. URL https:// openreview net wwr.mr/rumm//mm////oooeeoo i dwd.de-rGGaasssass
Morris, C., Ritzert, M., Fey, M., Hamilton, W. I.., Lenssen, J. E., Rattan, G., and Grohe, M. Weisfeiler and leman neural: Higher-order graph neural networks. In Proceed- ings of the AAAI conference on artificial intelligence, volume 33, pp. 4602-4609 2019.
Ye, Q. Relative perturbation bounds for eigenvalues of symmetric positive definite diagonally dominant matri- ces. SIAM J. Matrix Anal. Appl., 31:11-17, 2009.
Nair, V. and Hinton, G. E. Rectified linear units improve restricted boltzmann machines. In Proceedings the In- ternational Conference Machine Learning, pp. 807- 814, 2010.
Zhang, M., Li, P., Xia, Y., Wang, K., and Jin, L. La- beling trick: A theory of using graph neural networks for multi-node representation learning. In Advances in Neural Information Processing Systems, volume 34, pp. 9061-9073, 2021.
Obukhov, A. Efficient householder transformation in pytorch, 2021. URL www.githure www.cooosssssoo toshas/
sarch-householle Version: 1.0.1. DOI: 22281///eoooo.0000
10

---

Enhancing Spectral GNNs: From Topology and Perturbation Perspectives
A. IMPORTANT NOTATIONS.
Table IMPORTANT NOTATIONS
Symbol
Definition
G,F
a graph, vector spaces over the graph
V.E
set of nodes, set of edges adjacency matrix, degree matrix
A, D
L,
normalized graph laplacian, sheaf laplacian
Lylock Ef
block form of normalized graph laplacian, perturbed sheaf laplacian the dimension of C, the dimension of Σy, the dimension of stalks the eigenvalue of Lsocks the eigenvalue of L
n, .. d
X
X,
feature matrix (input matrix), the input matrix after the Fourier transform the output matrix after the Laplace transform, the final predication matrix the applied perturbation matrix, the transport matrix (the transpose product of the restriction maps) the filter function, the reshape operation
Y,Z
P.Q
g.R
reflection vector
6.40
the minimum eigenvalue gap in Cotock function like multi-layer perceptrons
6
the maximum perturbation ratio for every block, the upper limit of perturbations for all parameters in
B. Proofs.
B.1. Proof of Theorem 3.2
Theorem B.1. When there are only h distinct eigenvalues of the normalized Laplacian matrix, and the nonlinear real- valued function functiin a satisfies (xx) + ffror x + O, nonlinear spectral GNNs can produce at most k different filter coefficients, and thus can only generate one-dimensional predictions with a maximum of k arbitrary elements.
Proof. Let Z = [=,,...,,,,," =,," be the output, where 2; E R and z, * O for = 1,2,.... n. Here, k is the number of distinct eigenvalues of the normalized graph Laplacian matrix. Assume that the filter function is g(A), where À is the eigenvalue of the normalized graph Laplacian matrix. When X; = >i, g(),) = g(2,). Therefore, when the number of distinct eigenvalues of the Laplacian matrix k. there are only ic different filter coefficients.
For the Fourier transform Z U diag(o XW, assume that all elements of X are non-negative. Let the vector m = U XW and diag(g(A)) m. Then Z U'q. where Z E 1ax1 Xf Aj. then q; Qj my independent eigenvalues, there are only & arbitrary elements in the vector q. Therefore, any element in the vector q can be represented linear combination of these k arbitrary elements, that
mi, Since there are k
/: = a14s + 0249, + aulee
E [1,n]
(13)
where 9r,.....4h are the l arbitrary elements in Then we can use a matrix U with n rows and k columns, and a vector q' with & elements to represent Z, ie. U'q'= = Z. To illustrate this process, we group all eigenvectors according to their ....,,)) corresponding eigenvalues. For each distinct eigenvalue Xτ, (where & = 1, ..., k), define the set: S, = {i > )x,)

---

Enhancing Spectral GNNs: From Topology and Perturbation Perspectives
Z could be expressed follow:
my U1
mi U1 mi4 U2.J
mei
JESI
Σ
U2
mL
Σ
mi
mi
g&2
22
JES1
jESt
(14)
Σ JES1
mi Un
Σ
m² Und
mej
mez
JESk
Since U has rank at most spans a subspace of dimension most k. Thus, Z U'q' is confined within this subspace. We can choose up to A linearly independent elements 26, 2dg.-... ... 26g basis. Therefore, any can be expressed as linear combination:
= 31 + 822t, + ... + Sezt, for 33 E R
(15)
Let the activation function (xx) be a real-valued function, where (xx) A 0 for æ + O. Since the elements Z are nonzero, let Z' = (Z) and rank(U' = k; then z/ = ri Zi, where r; E R. According to Equation (15), we have:
Ti The
2 B1 Th
=e, ....
(16)
8 t ... 8k tle
Therefore with the nonlinear activation function, spectral GNNs can still only generate at most k arbitrary elements.
B.2. Proof of Theorem 4.1
Theorem B.2. Let P = Li- Lbtock be the perturbation matrix applied to Lotock. and let 6 minag; [A dzln where
X; are the eigenvalues of Litock Pll2 < G. then the eigenvalue multiplicity of L.F will decrease.
Proof. When the perturbation matrix P is applied to Lstock, the new eigenvalues μ4i and fj of Ef corresponding to A and Aj will lie within a neighborhood of these eigenvalues. According to Weyl's inequality, we have: | Asl < ||I|| and |pj - Ayl I ||12. This implies that μu lies in the interval: [>; - P|12. A + [|]|]], and μy lies in the interval: [>, || 21. X + Pll2].
Now, since Ø = min j > - xyl and we assume |||| < 2. the length of each interval is 2 P|]2, which is strictly less than Φ The distance between the centers of these intervals is Φ, which is greater than the sum of the half-lengths of the intervals, Pl12- Thus, [X, ||l|2, A; [[2] and [Λy || A + ||||]]] do not overlap. This guarantees that the perturbed eigenvalues (u; and μı, remain distinct.
Since A; and A represent the pair of eigenvalues with the smallest distance d, if their perturbation intervals do not overlap, then for any other pair of eigenvalues A and x (where & + 1). their perturbation intervals will also not overlap due to |Ax A 2 db
Therefore, no two perturbation intervals overlap, ensuring that the eigenvalue multiplicity of ZF will decrease as eigenval- ues associated with higher multiplicities split into distinct values within their respective intervals.
C. Expressiveness of PSL-GNN
C.1. Proof of Proposition 5.1
Proposition C.1. The number of distinct eigenvalues of Lstock E Budxxnd is the same as that of L E R=*x" where L. is the normalized graph Laplacian matrix and Lstock = C & I, with I e Rdxdd being the identity matrix. Also, their corresponding GNNs, which share the same architecture, are mutually equivalent.
Proof. We prove the first part of the proposition as follows. Let L have eigenvalues {Ai, A2..... d,). .....,,,)) and let I E ddd be the identity matrix with eigenvalues (1,1....,1) 1}. According to the eigenvalue property of the Kronecker product, the eigenvalues of Lokec L & are \; = X; for each i 1,2....,7 n. Since only introduces eigenvalues of 1, the
12

---

Enhancing Spectral GNNs: From Topology and Perturbation Perspectives
Kronecker product does not add new eigenvalues. Each eigenvalue X of C is repeated d times, meaning the number of distinct eigenvaluss of Latuck is the same that of L.
Consider an input matrix X E R where f = d x k. Reshape X into X' E Bnd Let Y = LX and Y' = X'. We partition into n row blocks: X [(X(]))_ ..... ....,
(X where each x E RRIX Reshape each X(1 into block matrix X E Rddk The reshaped matrix X' E lkndxk is formed by stacking these blocks.
The
Now compute Y' = X'llock'', The Kronecker product Lolock = & la implies that each element Lij of L is multiplied by the d x identity matrix la- Thus, Y' can be expressed as:Y" D GizX'
ΣE=1 Laz x
Next, reshape Y' back to Y reshhaped Raxs, For each i, s, t, the element Y2 1))44) in Y corresponds to Y in Y Thus, we have: (i(s-1)d+t = Y reshaapa (V, (s 1)d + t).
Since this holds for all i, s, t, we conclude that Y Y
reshaped
C.2. Proof of Corollary 5.2
Corollary C.2. PSI-GNN has stronger one-dimensional prediction ability.
Proof. Consider a block form matrix Litock and its corresponding perturbed sheaf Laplacian matrix Zy. Let the input matrix be X R=x1 Their outputs are given as Zı U1g(A) XW1 and Zz = (2) XW2, respectively. Define vectors m; XW, and m2 XW2, and let qi = =(A) mi and q2 = g(( m2.
Suppose the number of distinct cigenvalues of L5 and L are kı and k2, respectively. According the Proposition 5.1, the number of distinct eigenvalues of Litock is equal to that of L, so the number of distinct eigenvalues of Lotock is lz When X; = >ラ. (Ax) = 9(>z)-
Therefore, the outputs can be expressed as 11 = U'ql and Z₂ = Ujgb. where Ui is an n x K1 matrix, Uù is an n x k2 matrix, and qi and q/2 are vectors with hą and ky elements, respectively.
Since the ranks of U/ and U/2 are at most k and k2, Z1 and Zz each have at most k and l2 arbitrary elements, respectively. Given that k > k2, the number of arbitrary elements in Zi is greater than that in Zz.
C.3. Proof of Corollary 5.3
Corollary C.3. PSL-GNN loses fewer frequency components.
Proof. Consider a block form matrix Lotockk and its corresponding perturbed sheaf Laplacian matrix Cy. Let the maximum multiplicity of the eigenvalues of Lstock be m, and the maximum multiplicity of the eigenvalues of Cf be m. Since m < m, PSL-GNN able to lose fewer frequency components even in the worst-case design of the filtering function. O
C.4. Proof of Corollary 5.4
Corollary C.4. PSL-GNN has stronger capability in processing frequency components.
Proof. Consider a block form matrix Loock and its corresponding perturbed sheaf Laplacian matrix Σ,. Let the number of distinct eigenvalues of Lstock and Ey be kj and k2, respectively. Since k < k2, the PSL-GNN filter has more coefficients, implying that can handle frequency components in more diverse manner. Remark C.5. We explain Corollary 5.4 more clearly: the eigenvalues of L are divided into k1 groups, while those of CF= are divided into 2 groups, with k2 > kj, Accordingly, the filter coefficients are divided into k and k2 groups, with identical coefficients within each group. This means that the frequency components associated with each eigenvalue in group scaled by the same factor. Since h > k,, PSL-GNN can independently scale more frequency components.
D. Perturbation Bounds of Eigenvalues
Theorem D.I. Let Lotoey and L = LMteck + P be N x N symmetric positive semidefinite matrices, with eigenvalues Agy..., Ay and Xi...., AN. respectively, where Lotock is diagonally dominant. Suppose the perturbation matrix P satisfies
[Pyll S <(((Toockis) for all i + j for all i, where O < c < 2. Hence, for each i, |>x Au S 1-26 Xmax
2c
13

---

Enhancing Spectral GNNs: From Topology and Perturbation Perspectives
Proof. First, we bound the spectral norm of P. For each row i, we have:
Σ ==1
Pol = Pa +
Σ
Piyl S CU + Σ
(Cstock) = +
Σ
[CConna)ssl = <(Colocc)at
(17)
j+1
8
Therefore:
|| Se max (Lo 15i5n
(18)
Since Lbtock diagonally dominant and positive semidefinite:
|| [bbockk /oo = max
( )ayl 2 max (Lolock S 2/ Calcokkck| 1515h
(19)
15i5
where ||Coockl|2 denotes the spectral norm of Lolock. Thus:
pll & || S <|| S 2x Sbblock 1|2-
(20)
Next, we apply Weyl's theorem, which states that for symmetric matrices Lotock and P: 13, - Aal S || Substituting the norm bound derived above:
17, - Ar ||l|2 S 2e Crtockle
(21)
We now relate || 1/2 to A₁. Since Ly Ditock + P:
Colookll2 & || ||||| 1 || 1a + 22|1
Catock
(22)
Rearranging gives:
| Cr
Coooockl2 x
(23)
1 - 2E
Given that ||2 Amax 2 7r follows that:
2c
2c
1I, Arl S 2E|1 Cetck 112 5
|1
Amax
(24)
2e
1 - 2c
Thus, the bound is proven.
E. Experimental Setup
E.1. Experimental Details
We construct every reflection matrix Fig(t.)) based on the method in (Obukhov. 2021). For downstream task, we update the perturbed sheaf Laplacian matrix every 10 epochs. Given its high dimensionality, employ sparse matrix storage reduce computational overhead. Additionally, we apply early stopping mechanism with maximum of 1500 epochs and a patience threshold of 100. For each PSI.-GNN and its corresponding GNN, we train them for the same number of times and take the average of their respective accuracies as the final result for each model. For model training, we use the Adam optimizer to optimize all models on an NVIDIA GeForce RTX 4090 GPU.
E.2. Datasets
We use seven benchmark datasets, categorized as follows: (1) Citation Networks: Cora (McCallum et al., 2000), Citeseer (Giles et al., 1998), and Pubmed (Sen et al., 2008) are citation networks with nodes as publications, edges as citation links, and labels indicating topics or fields; (2) Co- Co-purchase Networks: Photo (Shchur et al., 2018) is a co-purchase network with nodes as products, edges as co-purchases, and labels categorizing products; (3) Webpage Networks: Texas and Cornell
14

---

Enhancing Spectral GNNs: From Topology and Perturbation Perspectives
(Shchur al., 2018) webpage networks with nodes as webpages, edges as hyperlinks, and labels indicating categories; (4) Actor Co-occurrence Network: Actor (Shchur et al., 2018) is co-occurrence network with nodes actors, edges as co-occurrences, and labels classifying actors.
The information of each dataset is shown in Table 5, Additionally, due to the diagonal dominance of the normalized graph Laplacian L, its eigenvalue = has higher multiplicity. Thus we also compute the proportion Px=1 of this multiplicity for analysis.
Table 5. The statistical information of the datasets.
Datasets
Cora
Pubmed
Citeseer
Photo
Texas
Cornell
Actor
Nodes
2708
19717
3327
7650
183
183
7600
Edges
5278
44324
4552
245861
287
278
26705
Features
1433
500
3703
745
1703
1703
932
Classes
7
3
8
5
5
PA-1
0.125
0.639
0.171
0,048
0.362
0.349
0.155
E.3. GNN Baselines
To evaluate the performance of our proposed method, we choose six different spectral GNNs as follows.
GCN (Kipf& & Welling, 2016) is a spectral graph neural network that uses a mean aggregator to combine information from neighboring nodes, bridging the gap between spectral and spatial GNN methods. APPNP (Klicpera et al., 2018) employs personalized PageRank to propagate node features, addressing the oversmoothing problem deep networks. Graph- Heat (Xu et al., 2019a) incorporates the heat kernel for graph signal filtering, providing natural mechanism smooth or diffuse signals over the graph. BernNet (He et al., 2021) improves spectral graph convolutions using Bernstein polyno- mials, offering better flexibility to handle varying graph structures. GPRGNN (Chien et al., 2021) generalizes PageRank algorithms to enhance performance on graphs with heterophilic structures. Lastly, JacobiCony (Wang & Zhang, 2022) leverages orthogonal Jacobi polynomials to enhance expressiveness and optimization in spectral graph neural networks.
For all baseline models, we use either their official implementations or implementations provided by PyTorch Geometric to ensure fair comparisons.
E.4.
To ensure a fair comparison, we keep hyper-parameters the same for each PSL-GNN and its corresponding baseline GNN, except for 77 and d. Specifically, for all models, we set the learning rate 0.05, weight decay to 5e 4, and the number of hidden units to 64. We the order of the polynomial 10. For all PSL-GNN models, search 17 within {le 1, le 2, le 3, le 4) and d within {2, 3, 4) to achieve the best model performance.
APPNP, Graph-Heat, and Jacobi-to
F. Additional Experimental Studies
F.I. Complexity Analysis
We first analyze the space and time costs constructing the perturbed sheaf Laplacian, then the per-epoch cost of PSL.- GCN (with and without PSL reconstruction), and finally report empirical runtimes.
F.1.1. SPACE COMPLEXITY & PARAMETERS.
Each restriction map uses d free parameters, forming the edge-incidence matrix B, (with two entries per edge) requires space O2E . d + n d).
1.2 PSL CONSTRUCTION TIME.
We build the signed incidence matrix By (size nd x nnzg), then compute Σf = BB BJ. Since By has nzzg nonzeros, this sparse-sparse product costs O (
15

---

Enhancing Spectral GNNs: From Topology and Perturbation Perspectives
F.1.3. PER-EPOCH COST OF PSL-GCN.
Every 10 epochs we rebuild the PSL; thus per-epoch we either include or omit the ((unz))) term:
Including PSL construction: ((n)))) (m(fiddss)) ((ndd// f4)) + O(d (ws
Amortized (excluding PSL constructionn: fs) O2nd (r fa) + ( fusa c).
1.4, EMPIRICAL RUNTIMES.
Table reports average epoch time (ms) total runtime per fold (s) for PSL-GCN vs. Neural Sheaf Diffusion (Diag-NSD, O(d)-NSD, Gen-NSD) (Bodnar et al., 2022):
Table 6. Average epoch time (ms) / total runtime fold (s).
Dataset
Cora
Pubmed
Citeseer
Photo
Texas
Cornell
Actor
Diag-NSD
26.4/5.9
124.3/34.7
25.2/5.8
90.6/17.4
8.3/1.6
8.1/1.5
98.4/21.5
O(d)-NSD
57.0/12.3
204.5/66.3
64.1/13.6
143.5/26.3
26.8/6.7
27.4/7.2
128.2/31.9
Gen-NSD
85.3/17.6
231.1/74.3
92.4/20.6
166.7/34.6
34.3/14.4
31.4/14.2
177.6/45.2
PSL-GCN
16.0/..6
83.7/17.4
18.3/5.2
65.3/15.8
6.3/1.1
6.4/1.1
72.7/17.3
F.2. Comparison of Spectral Gap
The Laplacian spectrum measures graph connectivity. Cheeger's inequality 2hg > A hi shows that larger spectral gap implies better connectivity (Jamadandi al., 2024). The Cheeger constant he quantifies the tightest connectivity bottleneck in graph. In (Lu et al., 2024), the new operator's (H) eigenvalues are defined as BA: (1 3)v, where 2i/n 2. When < λ₁. it follows that < aı (because - a1 (1 3)( - A1) with 8 < 1), which reduces the spectral gap and impairs information flow, especially large graphs, where U1 = 22nn is very, very small. However, our approach perturbs the normalized Laplacian in way that maintains subtle eigenvalue differences regardless of graph size, thereby preserving the topological information.
2
Below, verify our argument above by presenting the spectral gaps' orders of magnitude for the normalized graph Laplacian and PSL across various datasets. As shown in the Table 7, for each dataset, Å1, ii λ and λι S d which indicates that Lu et al.'s approach (Lu et al., 2024) indeed reduces the spectral gap, thus compromising the original topological information encoded in the normalized Laplacian matrix.
Table 7, Comparison of spectral gap
Cora
Pubmed
Citeseer
Photo
Texas
Cornell
Actor
2708
19717
3327
7650
183
183
7600
Ui
7e-4
le-4
6e-4
2e-4
le-2
le-2
2e-4
A
4e-3
1e-2
le-3
1e-3
5e-2
7e-2
3e-2
Å
5e-3
le-2
2e-3
le-3
Se-2
7e-2
3e-2
F.3. Node Classification A Fully-Supervised Split
We train all models a super-sue split (60% 20% / 20%). For each baseline (including the EC-GNN variants), we adopt the best hyperparameter settings reported in the original paper. For all PSL-GNN variants, we use the same settings as their corresponding baselines, with 7) = 10-5 and d The results are summarized in Table 8 and Table 9.
16

---

Enhancing Spectral GNNs: From Topology and Perturbation Perspectives
Table Results on real-world datasets in the dense splitting (60% / /00% 20%)..
Datasets
Cora
Citeseer
PubMed
Computers
Photo
GCN
87.16+1.03
79.8420.73 80.63+1.00
86.79=0.32 87.68=0.83
83.31=1.01
88.2440.78
EC-GCN
88.73=00.9
83.94
90.45+1.20
PSL-GCN
89.09:1.14
81.04=0.63
88.75#1.24
84.12+1.65
91.48+0.81
APPNP
88.23+1.00 .05
80.61#0.94
88. 88.17=0.38
85.35=a038
90.48+0.57
EC-APPNP
89.54+1.43
81.48=1.23
88.42=1.36
86. 16.1001.07 1.07
90.75+1.000 1.66
PSI-APPNP
90.91=1.14
81.92:1.36
88.88=1.42
86.43=0068
91.82++0.6
Graph-Heat
87.34+1.41
78.82+1.26
87.52=0.89
83.23+1..33
89.97=0.82
EC-Hcat
88.13+1.02
79.44+1.12
88.93=0.91
83.86ct 2,24
90.57=0.88
PSL--eatt
88.51+1.38
80.02+1.31
89.21=1.57
84.64:1.55
90.87=0.91
BerNeet
88.48 14
80.08+1.07
88.73#1.42
87.68=0.53
94.31=0.88
EC-BernNet
38.64+0.55
80.30=0.98
89.07=1.37
88.34tt 1.03
94.50=1.00
PSL-BernNet
90.01=0.93
80.86*1.15
90.13=11.4
88.74=0.56
94.79+1.03
GPRGNN
88. 0.24
80.09:1.03
88.52:0.46
87.01=0.74
93.87=0.33
EC-GPR
89.41+0.69
80.66#1.00
89,64=0.53
$9.91=0.00
94.76tt 1.02
PSL-GPR
90.13+0.92
81.11
89.82+1899
89.93=1.70
94.87=0.96
Jacobi
88, 28.96+0.66
80.73=2..C
89.67=0.82
90.42+0.31
95.52.0.33
EC-Jacobi
89 39.0610.67
81.2820.96
89.87=0.42
90.33+0.28
95.5420.36
PSI.-Jacobi
90.73+1.34
8..5
90.42+1.13
90.83=0.61
95.69=0.52
Table Results on real-world datasets in the dense splitting (60%
20% 20%).
Datascts
Chameleon
Actor
Squirrel
Texas
Cornell
GCN
59.65+2.52
34.63+1. 62
46.64=1.28 50.31=0.84
78.65#2.98
76.42+5.22
EC-GCN
61.81+1.94
36.12+1.44
80.72+2.39
77.38+4.37
PSL-GCN
62.04+2.71
36.74#1.43
52.73+1.54
81.45=2..4
78.13+4.32
APPNP
51.78+1.91
39.59=0.83
34.74=0.60
90.89#1 1.53
91.84+2.1 122
EC-APPNP
52.93+2.12
40.32+0.94
35.33=0.84
91.32+
91.97+1.64
PSL-APPNP
54.49&1.74
40.6740.91
35.6320.58
91.53*1149
92.07+1.94
Graph-Heat
63.46+0.92
35.74+1.31
44.35=2.14
80.06=0094
76.87=0.85
EC-Heat
64.86+1.22
36.51+0.94
45.01=1.87
81.25# 1,36
77.91+0.63
PSL-Heet
65.60+1.23
36.93+1.45
45.32+1.89
81.49#1.10
80.94+1005
BernNet
68.25+1.59
41.82+0.99
51.37=0.75
94.14:11.67
92.16
EC-BernNet
7..20+1.33
41.87+1.02
62.7920.78
94.37=1.44
93.77+1.26
PSL-BernNet
75.09:1.46
41.93+1.30
63,82+1.33
94.54+1.80
94.01=0.93
GPRGNN
67.14+1.10
39.92+0.65
50.08:1.95
92.97=1.41
91.32+2.02
BC-GPR
74.24+1.06
40.42+0.77
62.48+2.03
92.27+1.92
90.79+2.22
PSI-GPR
74.78+1.34
41.17+0.96
63.6520.87
94.74=1.65
92.44+1.85
Jacobi
74.23+1.45
41.1620.70
57.38+1.24
93.45=2.03
92.9442.38
EC-Jacohi
75.64+1.51
41.01+0.74
59.87=0.91
93.48
93.29+2.33
PSI.-Jacobi
75.87+1.44
41.94+0.75
61.47=0.98
94.20=1.75
93.91+1.96
From the above results, PSL-GNNs consistenty outperform the baselines, which validates the effectiveness of the perturbed sheaf Laplacian (PSL).
F.4. Eigenvalue Perturbation Study
Every restriction map Fuge. is generated using parameters, and is bounded by where represents the dimension of the stalks. To evaluate the impact of different perturbation scales on the eigenvalues, we compare the maximum relative eigenvalue perturbation between the resulting sheaf Laplacian matrix and the normalized graph Laplacian matrix. The
17

---

Enhancing Spectral GNNs: From Topology and Perturbation Perspectives
maximum relative perturbation is defined as:
A A
A max
for i = 1,2,...,N N,
(25)
A;
where N the dimension of the matrix, Å denotes the eigenvalues the sheaf Laplacian matrix, and X represents the
0.0
0.45
0.40
4.
0.55
0.55
0.30
0.5
0.5
0.2
0.0
015
36-3
144
16-3
164
165
Ie1
9
9
AA: d =
AA: d =
AA: AA:d=A
1.5
0.6
08
303
0.5
206
0.
64
0.4
proportion: =
proportion d 3
proportion d ===
Figure 4. The relative eigenvalue perturbations and the proportion of distinct eigenvalues of the perturbed shcaf Laplacian across different datasets under varying y and d.
eigenvalues of the normalized graph Laplacian matrix. We also examine how the proportion of distinct eigenvalues, defined as k//vl (where k is the number of distinct eigenvalues), varies with different 1). The results for each dataset are shown in the Figure
As shown in Figure 4, when 1) decreases, AA also decreases, which is consistent with the theoretical analysis for the perturbation of eigenvalues in Theorem 5.5. A) le-3, the number of distinct eigenvalues peaks but decreases for 7 1e-3, larger perturbations may cause eigenvalues to overlap, violating Theorem 4.1. Furthermore, the impact of d negligible.
E55. Visualization of Eigenvalues Distribution
To better illustrate whether the multiplicities of eigenvalues in the perturbed sheaf Laplacian Ey are reduced across differ- ent datasets, we visualize its eigenvalue distribution alongside that of the normalized graph Laplacian L. Figure 5 shows the eigenvalues distributions under perturbation scale of 1e-3, where the vertical axis (density) represents the pro- portion of each distinct eigenvalue relative to the total, and the horizontal axis (A) represents the eigenvalues. Based on the analysis of these figures, we observe the following:
1. For almost every graph dataset, the perturbed sheaf Laplacian matrix consistently exhibits fewer repeated eigenvalues compared to the corresponding normalized graph Laplacian matrix.
2. On small graph datasets, the reduction in eigenvalue multiplicity is more pronounced, which aligns with the greater average performance gains observed in Table 1.
3. For every graph dataset, the eigenvalue always has the highest multiplicity. This explains why GCN performs worse than other baselines, as its filtering function removes frequency components associated with eigenvalue 1. In contrast, CF reduces the multiplicity of cigenvalue 1, which explains the highest average improvement for GCN, as it preserves the frequency components.
18

---

Enhancing Spectral GNNs: From Topology and Perturbation Perspectives
1300
0383
667
2004
3600
640
008
13
20
50
33
140
on
on Pubmed
on Citeseer
on Photo
660
66-
6.0
0330
0393
660
$8:00
Pun
30333
3100
000
0085
660
Zf on Cora
Z on Pubmed
E on Citeseer
Zy on Photo
0440
3:40
6330
Pemm-
305
3.5
00
L. on Texas
L on Comell
L on Actor
033
3.90
83300
3330
533
310
60700
3.0g3
C on Texas
EJ on Actor
Figure 5. Eigenvalues distribution of normalized graph Laplacian matrices and perturbed sheaf Laplacian matrices.
F.6. Hyyer-Paraaeete Study
To demonstrate how parameters of PSL-GPF and PSL-GCN, i.e. perturbation size and stalk dimension d. For the remaining parameters, we set the same configuration across Cora, Texas, and Actor.
influence the performance of the model, we study the effect of the two main hyper-
The results are shown the Figure 6. From the results, we have the following observations:
1.
These models perform best when 1 1c - and 1c 2. This could be explained by Figure 5: when r) 1c 3. the proportion of distinct eigenvalues in the fixed perturbed sheaf Laplacian matrix is maximized. Parameters of the restriction mapping are constrained within the range [le - 4, 1e 3). and the parameters might gradually approach the upper bound of le - 3. When = 1c 2, 2, the performance is similar, as the parameters are constrained within the range [ee 3, le - 2], they might gradually approach the lower bound of le 3.
2. When le 4, the model's performance is similar to that when perturbation is applied (i.e., v 0). As shown in Figure 5, the perturbation effect is nearly negligible in this case, and the perturbed sheaf Laplacian matrix becomes almost identical to the normalized graph Laplacian matrix.
F.7. Comparison between PSL and GSL
In the sully-supervised split, we compared the performance of PSL. and GSL. The results are shown below:
19

---

Enhancing Spectral GNNs: From Topology and Perturbation Perspectives
18.30
B1144
13:33
20:3
2133
00:11
19.29
60-44
96 60-22
K.5
X14
X:30
2039
06:4
10.41
64
20
PSL-GPR on Cora
PSL-GPR on Texas
PSL-GPR on Actor
5017
16:9
16.15
5442
14,00
34155
VAM
10.90
01.11
20:3
P32
PG1
2437
PSL-GCN on Cora
PSI-GGNN on Texas
PSL-GCN on Actor
11.B5
11:24
10:10
I0:3
20:10
2511
PSL-APPNP on Cora
PSL-APPNP on Texas
PSL-APPNP on Actor
PLD
A111
0731
85:33
272
60:38
80:00
W011
W12
01:31
30.11
40
40-3
8
0.32
0.15
66.30
14.17
10.0
9449
34
PSL- Heat on Cora
PSL-Heat on Texas
--e.- Actor
1820
10:0
6021
09
08.11
4175
45
30311
2013
X15
PSL-BernNed on Cora
PSL-BernNet on Texas
PSL-BerNNet on Actor
ICLL
INDi
14:21
M-35
14.23
ph-pp
20:44
2013
3015
2012
PSI--Jacohi on Cora
PSI.-Jacobi on Texas
Pacobi on Actor
Figure 6. Soper-Paramettrs Study.
20

---

Enhancing Spectral GNNs: From Topology and Perturbation Perspectives
Table 10. Comparison of models based on three Laplacian matrices (GNN vs. GSL-GGNN PSI.-GNN): Mean accuracy (%) #95 (%)
on seven datasets (in dense splitting: 60% / 20% 20%)
Datasets
Cora
Pubmed
Citeseer
Photo
Texas
Cornell
Actor
GCN
87.16t1.0 1.33
86.79+0.32
79.84+0.73
88.24+0.78
78.65+2.96
76,42+5.21
34.63=1.63
GSL-GCN
88.73 +0.98
87.04 #0.97
80.89 =0.51
89.67 =0.88
80.75 +2.64
77.93 +4.37
35.94 +1.29
PSL-GCN
89.09=1.14
88.75+1.24
81.04+0.63
91.48=0.81
81.45+2.43
78.1324.32
36.74+1.43
APPNP
88.23+1.00
88.17#0.38
80.61
90.48:0.57
90.89+1.53
91.84+2.12
39,59=0.83
GSL-APPNP
89.88=0,95
08.4611.34
81.52+1.
90.89+0,93
91.19#1.4
91.93+2.23
39.81
PSL-APPNP
90.91=1.14
88.88=1.42
81.92+1.36
91.82+0.96
91.533+.49
92.07=1.94
40.67=0.91
Graph-Heat
87.34=1
87 $7.5240.88 2.9
78.82+1.22 .26
89.9740.82
80.0620.94 94
76.84+0.85
35.74=1.31
GSt.-Heat
87.71+1.22
89. 89.14+0.88
79.23+1.000
90.34+1.31
80.79+1.9
80.87=0.70
36,36=1.88
PSL--Haat
88.51=1.38
19.7
80.02+1.31
90.87=0.91
81.49=1.10
80.94=1.05
36.93#1.45
BernNet
18,48+1.14
88. 38.73+1.44 .42
80.08+1.00 1.07
94.31+0.86
94.14+1.67
92. 12.1671.77
41.82=0.99
GSL-BernNet
$9.96+1.11
89 1.50
80.77+0.81
94.67=1.10
94.23=1.76
92.68=1.07
41.88=1.44
PSL-BemNNt
90.01=0.93
1..13+1.44
80.86
94.79=1.03
94.54+1.80
94.01=0.93
41.93=1.30
GPRGNN
88.54+0.82
88.52+0.46
80.09=1.03
93.87=0.34
92.97=1.41
91.32+2.02
39.92=0.65
GSL-GPR
89.82+1
89.0 $9.04+1.01
80.56+0.95
94.12+1.25
93,47
91.87=1.72
40. 40.6420.82
PSL-GPR
90.13=0.92
19.82+1.89
81.11=0.76
94.87+0.96
94.74=1.65
92.44=185
41.17=0.96
Jacobi
88.96+0.66
89.67+0.83
80.73+0.88
95.5240.33
93.4542.03
92.9442.38
41.16=0.70
GSL-Jacobi
89.43+0..9 94
89.9 89.92
81.24+1.16
95.55+0.36
93.84+1.97
93.45=1.71
41.21=0.45
PSL-Jacobi
90.73+1.34
90.42*1.13
81.54+1.12
95.69+0.52
94.20=1.75
93.91=1.96
41.94+0.75
It can be observed that PSL outperforms GSL, further validating the effectiveness of the perturbed sheaf Laplacian.
21


Reviews:
[{"review_id": "mTtB7H21DS", "reviewer": "Reviewer_QU1C", "summary": "This paper presents a novel solution to the repeated eigenvalue problem in Spectral GNNs.\n\nThrough the formal definition of cellular sheaf on graphs, \nthe paper formally introduces the definition of cellular sheaf,\nwhich essentially specifies that when a signal with dimension $d$ propagates from node $i$ along edge $(i,j)$ to another node $j$,\nit is not directly added but first undergoes a linear transformation, which can be denoted as $Q_{ij}$.\nEach $Q_{ij}$ contains $d\\times 1$ learnable parameters.\n\n\nAssuming this linear transformation is Identity, the operating matrix only changes from L to $L \\otimes I_d$,\nwith the same number of distinct eigenvalues\n(this operation can be viewed as expanding the dimension of $L$).\nNow, since this linear transformation is not Identity, it actually brings a slight perturbation, \nwhich increases the number of distinct eigenvalues. \nThe paper combines Weyl's theorem to show that when this perturbation is small enough, it guarantees an increase in distinct eigenvalues.\nAnd through experiments, it verifies that indeed more eigenvalues are obtained.\n\nThe paper compares with state-of-the-art polynomial-filter-based GNNs with almost no hyperparameter tuning,\nand shows that the Sheaf Laplacian method brings a slight advantage.", "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": "Thank you for your valuable suggestion. \n\n**Response to the raised issues in Experimental Designs or Analyses**\n\nWe reconducted the experiments by adding four new datasets (10 total) and using a full-supervised split (60%/20%/20%), which follows Wang & Zhang’s (*How Powerful are Spectral Graph Neural Networks*). It is worth noting that our previous experiments use the split (48\\%/32\\%/20\\%), which is only recommended by Bondar et al. in *Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNs*. \n\nThe partial experimental results are as follows, in which each baseline algorithm uses the best parameter settings in their original paper. We also tuned the parameters in our proposed method. It shows that PSL-GNN still yields improvements over all baselines and performs better than EC-GNN.\n\nThe complete experimental results are available at <https://anonymous.4open.science/r/exp1-DF26/exp1.pdf>.\n\n\n| Datasets    | Cora          | Citeseer      | PubMed        | Computers     | Photo         | Chameleon      | Actor         | Squirrel      | Texas         | Cornell       |\n|-------------|---------------|---------------|---------------|---------------|---------------|----------------|---------------|---------------|---------------|---------------|\n| GPRGNN      | 88.54±0.82    | 80.09±1.03    | 88.52±0.46    | 87.01±0.74    | 93.87±0.34    | 67.14±1.10     | 39.92±0.65    | 50.08±1.95    | 92.97±1.41    | 91.32±2.02    |\n| EC-GPR      | 89.41±0.69    | 80.66±1.01    | 89.64±0.53    | 89.91±0.68    | 94.76±1.02    | 74.24±1.06     | 40.42±0.77    | 62.48±2.03    | 92.27±1.92    | 90.79±2.22    |\n| PSL-GPR     | **90.13±0.92** | **81.11±0.76** | **89.82±1.89** | **89.93±1.70** | **94.87±0.96** | **74.78±1.34** | **41.17±0.96** | **63.65±0.87** | **94.74±1.65** | **92.44±1.85** |\n| Jacobi      | 88.96±0.68    | 80.73±0.88    | 89.67±0.82    | 90.42±0.31    | 95.52±0.33    | 74.23±1.45     | 41.16±0.70    | 57.38±1.24    | 93.45±2.03    | 92.94±2.38    |\n| EC-Jacobi   | 89.06±0.67    | 81.28±0.96    | 89.87±0.42    | 90.33±0.28    | 95.54±0.36   | 75.64±1.51     | 41.01±0.74    | 59.87±0.91    | 93.48±1.49    | 93.29±2.33    |\n| PSL-Jacobi  | **90.73±1.34** | **81.54±1.12** | **90.42±1.13** | **90.83±0.61** | **95.69±0.52** | **75.87±1.44** | **41.94±0.75** | **61.47±0.98** | **94.20±1.75** | **93.91±1.96** |\n\n**Response to Question 1**\n\nWe design a metric $S(k,m)$ to quantify the difference in response values of $g(\\lambda)$ before and after perturbation. Assuming the filtering coefficients for frequency components $U^T X_i W$ before and after perturbation are $k$ and $m$, respectively, the similarity metric is defined as:\n$$\nS(k,m)=\n\\begin{cases}\n1, & \\text{if } k = m = 0, \\\\\n1 - 2\\frac{|k-m|}{|k|+|m|}, & \\text{otherwise}.\n\\end{cases}\n$$\nSpecifically, $S(k,m)=1$ indicates identical coefficients ($k=m$), including when both are zero. We measured the response difference for PSL-GCN and PSL-GPR in the Cora dataset. The figure showing the results is at  <https://anonymous.4open.science/r/exp1-DF26/response.pdf>. Only about 1/10 of all nodes exhibit no change ($S=1$) in their filtering coefficients before and after perturbation, which aligns with the results reported in Table 3 of our paper. \n\n**Response to Question 2**\n\nPlease refer to Response to the raised issues in Experimental Designs or Analyses.\n\n**Response to Question 3**\n\nWe guess you mean $\\phi$. Recall that in Theorem 4.1, $\\phi$ is defined as the minimum eigenvalue gap of the normalized Laplacian matrix before perturbation. When a perturbation matrix $P$ is applied, Weyl’s inequality tells us that the eigenvalue change is bounded by its spectral norm, $||P||_2$. So if $||P||_2 < \\phi$, then the eigenvalue variation intervals do not overlap, resulting in no eigenvalue multiplicity. Otherwise, the new eigenvalues might coincide.\n\nWhile Theorem 4.1 describes a strict condition for ensuring fully distinct eigenvalues, in practice, it is not required to adhere to this condition strictly. We only need $||P||_2$ to be sufficiently small (but not too small. $||P||_2$ approaching zero would alleviate the perturbation effects.). \nTo address this, we introduce the learnable perturbation restriction maps to achieve a controllable and appropriate perturbation matrix $P$. Empirically, this approach maintains a sufficiently small spectral norm such that more eigenvalues split without generating identical new eigenvalues.", "claims_and_evidence": "- The part about introducing Sheaf Laplacian and the perturbation method to bring more distinct eigenvalues is very interesting and clear and convincing.\n\n- It undoubtedly makes a contribution to the multiple eigenvalue problem. \n\n\n- However, I'm not entirely convinced that the experiments sufficiently support the claim that ``solving the multiple eigenvalue problem can improve node classification performance''. Please see section (5. Experimental Designs Or Analyses) in the Review table.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "I roughly checked Theorem 4.1 and Prop 5.2 - Corollary 5.4.", "experimental_designs_or_analyses": "The paper's experiments are the common node classification tasks in the Spectral GNN series of work,\nincluding both homophilic and heterophilic graph datasets.\nHowever, I'm concerned that the way authors conducted the experiments seems too rough.\n\nSpectral GNNs, including GCN, are sensitive to hyperparameters (of course, the tendency to over-tune hyperparameters is a bad problem),\nbut this paper, according to Appendix E.4., seems to have done no hyperparameter tuning at all.\nTherefore, the experimental data reported in the paper is significantly **lower** than elsewhere. \nMeanwhile, the method presented in the paper only brings quite **slight** improvements,\nand the number of datasets compared is also relatively small.\n\nSo, although I appreciate the ideas in this work,\nI'm skeptical about whether solving the repeated eigenvalue problem can truly bring improvements to downstream tasks, and think the experiments are insufficient.", "relation_to_broader_scientific_literature": "This paper mainly responds to the discussion about repeated eigenvalues' impact on spectral GNNs expressiveness in Wang & Zhang (2022).", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Please check the former review form(2. Claims And Evidence)", "other_comments_or_suggestions": "None.", "questions_for_authors": "I mainly care the issues raised in section (5. Experimental Designs Or Analyses).\n\n1. I suggest the authors report the difference in response values of $g(\\lambda)$ before and after perturbation.\n\n2. I suggest the authors use Optuna for light hyperparameter tuning to confirm whether the method indeed has advantages (empirically).\n\n3. Could the authors explain more on the correspondence between $\\nu$ and $\\|P\\|$ in Thm.4.1? If there is theoretical justification, that would be great. If not, empirical evidence would also be helpful to understand this relationship.", "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": "IWM1mYDa5t", "reviewer": "Reviewer_oqeP", "summary": "This paper aims to solve the repeated eigenvalues of graph Laplacian by proposing a novel perturbed sheaf Laplacian (PSL). The authors claim that PSL can increase the number of distinct eigenvalues and improve the expressive power of spectral GNNs. Experiments on the node classification task validate the effectiveness of PSL on different spectral GNNs.", "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": "Thank you for your valuable suggestion.\n\n**Response to C1**\n\nWe apologize for the confusion.\nBriefly, the Laplacian spectrum measures graph connectivity. Cheeger's inequality $2h_G > \\lambda_1 > \\frac{h_G^2}{2}$ shows that a larger spectral gap $\\lambda_1$ implies better connectivity (More details can be found in: Spectral Graph Pruning Against Over-Squashing and Over-Smoothing). The Cheeger constant $h_G$ quantifies the tightest connectivity bottleneck in a graph. In Lu et al.'s method, the new operator's ($H$) eigenvalues are defined as $u_i = \\beta \\lambda_i + (1-\\beta)v_i$, where $v_i = 2i/n - 2$. When $v_1 < \\lambda_1$, it follows that $u_1 < \\lambda_1$ (because $u_1 - \\lambda_1 = (1 - \\beta)(v_1 - \\lambda_1)$ with $\\beta < 1$), which reduces the spectral gap and impairs information flow, especially in large graphs, where $v_1 = 2/n - 2$ is very, very small. However, our approach perturbs the normalized Laplacian in a way that maintains subtle eigenvalue differences regardless of graph size, thereby preserving the topological information.  \n\nBelow, we verify our argument above by presenting the spectral gaps' orders of magnitude for the normalized graph Laplacian and PSL across various datasets. As shown in the following table, for each dataset, $v_1 < \\lambda_1$, $u_1 < \\lambda_1$ , and $\\hat{\\lambda}_1 \\leq \\lambda_1$, which indicates that Lu et al.'s approach indeed reduces the spectral gap, thus compromising the original topological information encoded in the normalized Laplacian matrix.\n\n|   | Cora  | Pubmed | Citeseer | Photo | Texas | Cornell | Actor |\n|-------------|-------|--------|----------|-------|-------|---------|-------|\n| **n**     | 2708  | 19717  | 3327     | 7650  | 183   | 183     | 7600  |\n| **v₁**    | 7e-4  | 1e-4   | 6e-4     | 2e-4  | 1e-2  | 1e-2    | 2e-4  |\n| **λ₁**    | 4e-3  | 1e-2   | 1e-3     | 1e-3  | 5e-2  | 7e-2    | 3e-2  |\n| **λ̂₁**  | 5e-3  | 1e-2   | 2e-3     | 1e-3  | 5e-2  | 7e-2    | 3e-2  |\n\n**Response to C2**\n\nAccording to Reviewer QU1C's suggestion, we reconducted comprehensive experiments by adding four new datasets (10 in total). All baseline algorithms use the best parameter settings in their original papers. The results demonstrate PSL achieves better performance than GSL, which are available at <https://anonymous.4open.science/r/exp1-DF26/exp2.pdf>.\n\n**Response to Q1 in Methods And Evaluation Criteria**\n\nIt's insightful to point out the relevance of graph-level tasks in [1]. The primary focus of our paper was to address a specific known limitation inherent to spectral GNNs: the performance degradation and limited expressiveness caused by repeated eigenvalues in the standard graph Laplacian. We chose node classification to demonstrate direct evidence that our proposed PSL method successfully overcomes the targeted limitation in a practical application for spectral GNNs. \n\nStandard spectral GNN approaches face inherent challenges when applied across datasets containing graphs of varying sizes and structures, which are common in graph-level tasks. It's difficult to directly learn a single spectral filter that works across different $\\Lambda$ and $U$ matrices from different graphs.\n\nRigorously evaluating PSL's impact on graph-level tasks might involve developing novel ways to combine PSL-based spectral features with appropriate graph pooling mechanisms. While valuable, we considered this beyond the primary scope of introducing and validating the core PSL concept.\n\n**Response to Q2 in Methods And Evaluation Criteria**\n\nWe included Lu et al.'s method in the baselines. The results in the following table show our method outperforms Lu et al.'s method. The full results are available at <https://anonymous.4open.science/r/exp1-DF26/exp1.pdf>.\n| Datasets    | Cora          | Citeseer      | PubMed        | Computers     | Photo         | Chameleon      | Actor         | Squirrel      | Texas         | Cornell       |\n|-------------|---------------|---------------|---------------|---------------|---------------|----------------|---------------|---------------|---------------|---------------|\n| Jacobi      | 88.96±0.68    | 80.73±0.88    | 89.67±0.82    | 90.42±0.31    | 95.52±0.33    | 74.23±1.45     | 41.16±0.70    | 57.38±1.24    | 93.45±2.03    | 92.94±2.38    |\n| EC-Jacobi (Lu et al.'s method)   | 89.06±0.67    | 81.28±0.96    | 89.87±0.42    | 90.33±0.28    | 95.54±0.36   | 75.64±1.51     | 41.01±0.74    | 59.87±0.91    | 93.48±1.49    | 93.29±2.33    |\n| PSL-Jacobi (Our method) | **90.73±1.34** | **81.54±1.12** | **90.42±1.13** | **90.83±0.61** | **95.69±0.52** | **75.87±1.44** | **41.94±0.75** | **61.47±0.98** | **94.20±1.75** | **93.91±1.96** |\n\n**Response to comments in Essential References Not Discussed**\n\nSpecformer requires eigenvalue encoding. If PSL is integrated into Specformer, we have to encode the learned PSL, which implies the encoding process would involve training a PSL-GNN. The computation cost would be substantially increased.", "claims_and_evidence": "Some of the claims have been confirmed, but others remain unconvincing.\n\n- C1: **It also compromises the original topological information encoded in the normalized Laplacian matrix.** It is unclear why previous methods fail to use the topological information. This paper claims that \"PSL can retain the topological information of the normalized Laplacian matrix\", implying that it has the same topological information of the original graph Laplacian. As a result, I think previous methods can also leverage the topological information.\n\n- C2: **Comparion between PSL and GSL**. The proposed PSL is a perturbed version of the general sheaf Laplacian (GSL). However, in the ablation studies, the performance of PSL does not outperform GSL by a large margin. Therefore, the audience may doubt the effectiveness of PSL.", "methods_and_evaluation_criteria": "1. This paper only conducts experiments on the node classificiation datasets, which is unconvincing. In practice, we often use graph-level tasks, such as structure counting, to evaluate the expressive power of GNNs. See [1] for more details.\n\n2. This paper does not report the performance of Lu et al., 2024 [2], making the results less convincing.\n\n[1] Graph as Point Set. ICML 2024.\n\n[2] Improving expressive power of spectral graph neural networks with eigenvalue correction. AAAI 2024.", "theoretical_claims": "Roughly checking but not confident.", "experimental_designs_or_analyses": "This paper should add graph-level experiments. See Methods And Evaluation Criteria.", "relation_to_broader_scientific_literature": "This paper introduces PSL, which is a model-agnostic method to improve the expressive power of spectral GNNs. PSL consistently improves the performance of polynomial GNNs, which may benefit some downstream applications.", "essential_references_not_discussed": "This paper only applies PSL to the polynomial GNNs, which is a part of spectral GNNs. It would be better if the authors can try different architectures of spectral GNNs, such as Specformer [3].\n\n[3] Specformer: Spectral Graph Neural Networks Meet Transformers. ICLR 2023.", "other_strengths_and_weaknesses": "See the above comments.", "other_comments_or_suggestions": "See the above comments.", "questions_for_authors": "See the above comments.", "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": "PX45b9ZEcc", "reviewer": "Reviewer_nURk", "summary": "This paper claims that the presence of repeated eigenvalues limits the expressive power of spectral GNNs. To address this issue, this paper proposes perturbed sheaf Laplacian, which achieves optimal model performance due to its more distinct eigenvalues.", "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": "Thank you for your valuable suggestion. \n\n**Response to Comment 1 in Experimental Designs or Analyses**\n\nWe reconducted the experiments by adding four new datasets (10 in total). All baseline algorithms use the best parameter settings in their original paper. Additionally, we also tuned the parameters in our proposed method.\n\n\nFollowing are the partial experimental results,  and the complete experimental results are available at <https://anonymous.4open.science/r/exp1-DF26/exp2.pdf>.\n\n| Datasets    | Cora         | Pubmed       | Citeseer     | Photo        | Texas        | Cornell      | Actor        |\n|-------------|--------------|--------------|--------------|--------------|--------------|--------------|--------------|\n| Jacobi      | 88.96±0.68   | 89.67±0.82   | 80.73±0.88   | 95.52±0.33   | 93.45±2.03   | 92.94±2.38   | 41.16±0.70   |\n| GSL-Jacobi  | 89.43±0.94   | 89.92±1.33   | 81.24±1.16   | 95.55±0.36   | 93.84±1.97   | 93.45±1.71   | 41.21±0.45   |\n| PSL-Jacobi  | **90.73±1.34** | **90.42±1.13** | **81.54±1.12** | **95.69±0.52** | **94.20±1.75** | **93.91±1.96** | **41.94±0.75** |\n\nThe results show that PSL performs better than GSL. Nonetheless, we believe that GSL merits further investigation, as it can theoretically learn a new operator with fewer or even no repeated eigenvalues. In this paper, PSL is a special case of GSL, which uses perturbation to achieve more distinct eigenvalues, effectively alleviating the problem of repeat eigenvalues. However, our current perturbation method is not refined enough to completely eliminate repeated eigenvalues—a task that would require a deeper understanding of the sheaf Laplacian's properties, a challenging problem we aim to address in future, as mentioned in the conclusion of our paper.\n\n\n**Response to Comment 2 in Experimental Designs or Analyses**\n\nWe included the eigenvalue correction method in the baselines and compared vanilla GNN, EC-GNN, and PSL-GNN in the new experimental settings.The results can be found at <https://anonymous.4open.science/r/exp1-DF26/exp1.pdf>. The experiments show that our method improves all baselines including EC-GNN.\n\n**Response to Comments 3 in Experimental Designs or Analyses**\n\nPlease refer to the following Response to Q2 in Questions For Authors.\n\n\n**Response to Q1 in Questions For Authors**\n\nCompared with the eigenvalue correction method, our proposed PSL does not compromise the original topological information encoded in the normalized Laplacian matrix. Here, we briefly explain why the eigenvalue correction method will lead to this issue. The spectral gap of the normalized Laplacian often measures the quality of graph connectivity. The eigenvalue correction method, however, reduces the spectral gap of the new operator H (i.e., u₁ = βλ₁ + (1-β)v₁< λ₁, when v₁ < λ₁), which in turn affects information propagation (please see [3]: Spectral Graph Pruning Against Over-Squashing and Over-Smoothing for details). We also experimentally validated this effect:\n\n|             | Cora  | Pubmed | Citeseer | Photo | Texas | Cornell | Actor |\n|-------------|-------|--------|----------|-------|-------|---------|-------|\n| **n**     | 2708  | 19717  | 3327     | 7650  | 183   | 183     | 7600  |\n| **v₁**    | 7e-4  | 1e-4   | 6e-4     | 2e-4  | 1e-2  | 1e-2    | 2e-4  |\n| **λ₁**    | 4e-3  | 1e-2   | 1e-3     | 1e-3  | 5e-2  | 7e-2    | 3e-2  |\n| **λ̂₁**  | 5e-3  | 1e-2   | 2e-3     | 1e-3  | 5e-2  | 7e-2    | 3e-2  |\n\nHere,  $\\hat{\\lambda}_1$ denotes the spectral gap of PSL.  The comparison between EC-GNN and PSL-GNN is available at <https://anonymous.4open.science/r/exp1-DF26/exp1.pdf>. The results show that PSL-GNN outperforms EC-GNN, demonstrating the superiority of our work.\n\n**Response to Q2 in Questions For Authors**\n\nWe compared the efficiency of PSL-GNN with a representative work ([4] *Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNs*). Following the experimental setup in [4], we compared PSL-GCN with the three GCN-based sheaf models proposed in [4] and reported the average epoch runtime (ms) and the total runtime per fold (s). The results are shown in the table below:\n\n| Datasets   | Cora       | Pubmed      | Citeseer   | Photo      | Texas    | Cornell  | Actor      |\n|------------|------------|-------------|------------|------------|----------|----------|------------|\n| Diag-NSD   | 26.4/5.9   | 124.3/34.7  | 25.2/5.8   | 90.6/17.4  | 8.3/1.6  | 8.1/1.5  | 98.4/21.5  |\n| O(d)-NSD   | 57/12.3    | 204.5/66.3  | 64.1/13.6  | 143.5/26.3 | 26.8/6.7 | 27.4/7.2 | 128.2/31.9 |\n| Gen-NSD    | 85.3/17.6  | 231.1/74.3  | 92.4/20.6  | 166.7/34.6 | 34.3/14.4| 31.4/14.2| 177.6/45.2 |\n| PSL-GCN    | 16/4.6     | 83.7/17.4   | 18.3/5.2   | 65.3/15.8  | 6.3/1.1  | 6.4/1.1  | 72.7/17.3  |\n\nAs we can see our approach is significantly more efficient than the other sheaf models.", "claims_and_evidence": "The occurrence of repeated eigenvalues does indeed limit the expression ability of spectral GNN, as evidenced by many previous literature. However, this paper claims that eigenvalue correction [1] damages the topological information of the original graph, but does not provide any analysis or basis.\n\n[1]Lu, K., Yu, Y., Fei, H., Li, X., Yang, Z., Guo, Z., Liang, M., Yin, M., and Chua, T.-S. Improving expressive power of spectral graph neural networks with eigenvalue correc\u0002tion. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 14158–14166, 2024.", "methods_and_evaluation_criteria": "Yes, the proposed method helps alleviate the problem of limited expressiveness caused by repeated eigenvalues.", "theoretical_claims": "No", "experimental_designs_or_analyses": "1.According to Table 2, the performance of PSL-GNN is comparable to that of GSL-GNN. Does this indicate that PSL-GNN is sufficient to achieve optimal performance without the need for GSL-GNN?\n2. Obviously, this paper improves based on eigenvalue correction, but does not compare it with eigenvalue correction.\n3.Although this paper provides a complexity analysis, the actual runtime is helpful for readers to understand the scalability of the proposed method.", "relation_to_broader_scientific_literature": "Previous literature has shown that repeated eigenvalues can limit the expressive power of spectral neural networks and hinder model performance. This paper adopts a novel approach (perturbed sheaf Laplacian) to solve this problem.", "essential_references_not_discussed": "The eigenvalue correction method [1] can also solve the problem of duplicate eigenvalues, but this paper did not compare it with it.\n[1]Lu, K., Yu, Y., Fei, H., Li, X., Yang, Z., Guo, Z., Liang, M., Yin, M., and Chua, T.-S. Improving expressive power of spectral graph neural networks with eigenvalue correction. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 14158–14166, 2024.", "other_strengths_and_weaknesses": "Compared to eigenvalue correction, this paper does not require expensive eigenvalue decomposition.", "other_comments_or_suggestions": "No", "questions_for_authors": "1.What are the advantages of this paper compared to eigenvalue correction? Although the paper mentions that eigenvalue correction damages the topological information of the original graph, it does not provide a detailed explanation. And this paper did not compare it with eigenvalue correction.\n2.What is the training efficiency of the proposed method? Obviously, this paper introduces more intensive matrix operations, so providing actual training time is beneficial.", "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": "auVMwgie7M", "reviewer": "Reviewer_wYZy", "summary": "This paper proposes a higher-dimensional sheaf Laplacian matrix based on perturbation theory and the theory of cellular sheaves. The perturbation is controlled from the block form of the normalized graph Laplacian matrix, and can contain more distinct eigenvalues. The paper provides theoretical analyses on the expressiveness of spectral GNNs and perturbation bounds for the eigenvalues. Node classification experiments demonstrate the efficacy of the proposed Laplacian.", "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": "Thank you for your valuable suggestion.\n\n**Response to Q1**\n\nWe apologize for any confusion caused. To clarify: Table 1 demonstrates the performance gains achieved by integrating PSL into various models, while Table 2 highlights the comparison between PSL, GSL, and the conventional normalized graph Laplacian.  Table 2 shares some information with Table 1, but with different performance values. It is because we retrained all the models separately under the same experimental environment. Therefore, although the experimental results differ slightly, these variations fall within the normal fluctuation range. As suggested by other reviewers, we reconducted comprehensive experiments by adding four new datasets (10 in total). All baselines use their optimal parameter settings as reported in their original papers. The new Table 1 is available at <https://anonymous.4open.science/r/exp1-DF26/exp1.pdf>, and the new  Table 2  is available at <https://anonymous.4open.science/r/exp1-DF26/exp2.pdf>, ensuring the robust validation of the proposed method.\n\n**Response to Q2**\n\nNext, we will explain the reason for not comparing the previous Sheaf Laplacian-based GNNs in Sec. 7.2. \n\nSheafNN by Hansen and Gebhart was designed under the settings with a known sheaf structure, but real-world datasets typically lack this information.\n\nBodnar et al. adapted the sheaf Laplacian into a learnable form that is suitable for graph learning, making it applicable for graph learning. Our GSL indeed follows Bodnar et al.'s approach, so we have already compared our approach with their proposed Sheaf Laplacian-based GNN.\n\nThe hypergraph sheaf Laplacian proposed by Duta et al. is explicitly designed for hypergraphs, making it inapplicable to our benchmark datasets.\n\nBoth Conn-NSD by Barbero et al. and D-TNN by Battiloro et al. impose restrictive assumption on high node degrees, which are not satisfied by most benchmark graph datasets.\n\n\n**Response to Q3**\n\n**Notation:**  \n- $n$: Number of nodes  \n- $f_1$, $f_3$, $f_4$: Feature dimensions  \n- $d$: Stalk dimension  \n- $c$: Number of classes  \n- $\\text{nnz}_{\\mathcal{B}}$: Number of nonzeros in the edge incidence matrix (approximately $2E$, where $|E|$ is the number of edges)  \n- $r$: Average number of nonzeros per row in the PSL matrix  \n- $f_{last}$: Feature dimension of the last layer  \n\nFor PSL-GCN, we generate a new PSL every 10 epochs; therefore, for efficiency analysis per epoch, we consider the following two cases. In the first case we include PSL construction time. The preprocessing stage has a complexity of $O\\big(n \\cdot f_1 \\cdot d \\cdot f_3\\big)$. \n\nThe PSL construction has a complexity of $O\\big(\\text{nnz}_{\\mathcal{B}}^2\\big)$. \n\nThe forward propagation for 2 layers has a complexity of $O\\big(2 \\cdot nd \\cdot f_3 \\cdot (r + f_4)\\big)$ (with $r$ representing the average number of nonzeros per row in the PSL matrix). \nThe final output transformation has a complexity of $O\\big(n \\cdot d \\cdot f_{last} \\cdot c\\big)$. \n\nThus, the total complexity is \n$$O\\Big(\\text{nnz}_{\\mathcal{B}}^2 + n \\cdot f_1 \\cdot d \\cdot f_3 + 2 \\cdot nd \\cdot f_3 (r + f_4) + n \\cdot d \\cdot f_{last} \\cdot c\\Big).$$\n\nIn the second case, we exclude PSL construction time, and the complexity per epoch is \n$$O\\Big(n \\cdot f_1 \\cdot d \\cdot f_3 + 2 \\cdot nd \\cdot f_3 (r + f_4) + n \\cdot d \\cdot f_{last} \\cdot c\\Big).$$\n\nIn order to empirically validate the efficiency of our method, we compare it with the representative work [4] *Neural Sheaf Diffusion: A Topological Perspective on Heterophily and Oversmoothing in GNNs*. We report the average epoch runtime (ms) and the total runtime per fold (s) in the table below:\n\n| Datasets   | Cora       | Pubmed      | Citeseer   | Photo      | Texas    | Cornell  | Actor      |\n|------------|------------|-------------|------------|------------|----------|----------|------------|\n| Diag-NSD   | 26.4/5.9   | 124.3/34.7  | 25.2/5.8   | 90.6/17.4  | 8.3/1.6  | 8.1/1.5  | 98.4/21.5  |\n| O(d)-NSD   | 57/12.3    | 204.5/66.3  | 64.1/13.6  | 143.5/26.3 | 26.8/6.7 | 27.4/7.2 | 128.2/31.9 |\n| Gen-NSD    | 85.3/17.6  | 231.1/74.3  | 92.4/20.6  | 166.7/34.6 | 34.3/14.4| 31.4/14.2| 177.6/45.2 |\n| PSL-GCN    | 16/4.6     | 83.7/17.4   | 18.3/5.2   | 65.3/15.8  | 6.3/1.1  | 6.4/1.1  | 72.7/17.3  |", "claims_and_evidence": "The claims seem clear and convincing.", "methods_and_evaluation_criteria": "The proposed method seems valid, but may have much larger complexity. The paper mentions the construction complexity for the Laplacian, but not the GNN complexity induced by using a more complex Laplacian.", "theoretical_claims": "The theorems and propositions seem correct.", "experimental_designs_or_analyses": "1. Table 2 shares some information with Table 1, but with different performance values. Is this due to execution variation? Could you merge the table instead?\n2. Why do you not compare your proposed PSL with the previous Sheaf Laplacian based GNNs mentioned in Sec. 7.2?\n3. The ablation study part does not discuss model complexity (which may offer another angle of why PSL-GNN performs better, but may not be an advantage). I think adding runtime comparison may be useful.", "relation_to_broader_scientific_literature": "The contribution is related to the other Sheaf Neural Networks on graphs but seems to have some advantages (not numerically compared though).", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The paper is generally well-written and flows well.", "other_comments_or_suggestions": "It may be better if you first write out Proposition 5.1 to motivate the need of perturbation, then introduce perturbations.", "questions_for_authors": "1. What is the relationship between Tables 1 and 2?\n2. Why do you not compare your proposed PSL with the previous Sheaf Laplacian based GNNs mentioned in Sec. 7.2?\n3. What is the model complexity in terms of GNN computation, not just construction of the Laplacian?", "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: The reviewers unanimously recommend acceptance of the paper with varying degrees of strength. I agree with their assessment and am happy to recommend acceptance of this paper. 

The reviewers have highlighted a need for more benchmark datasets, raised questions about the hyperparameter tuning, noticed a lack of comparison to an existing eigenvalue correction method and discussed the computational complexity of the proposed method. In my view, these topics were all convincingly resolved by the reviewers in their rebuttal. The only unaddressed point is a lack of evaluation on graph-level learning tasks. However, the authors argue that graph-level learning tasks present a challenge for many spectral GNNs. So, while this comment remains open. I do not think that it justifies a rejection decision, as it indeed is a problem that is not specific to the submitted work. I want to nonetheless encourage the authors to mention this limitation in their manuscript.
Decision: Accept (poster)