Joint Graph Rewiring and Feature Denoising via Spectral Resonance
Authors: Jonas Linkerhägner
Cheng Shi
Ivan Dokmanić
Venue: ICLR 2025 Oral (2025)
Keywords: GNNs
Rewiring
Denoising
Spectral Resonance
cSBM
Primary area: learning on graphs and other geometries & topologies
TL;DR: We introduce joint denoising and rewiring (JDR)—an algorithm to jointly rewire the graph and denoise the features, which improves the performance of downstream node classification GNNs.

Abstract: When learning from graph data, the graph and the node features both give noisy information about the node labels. In this paper we propose an algorithm to **j**ointly **d**enoise the features and **r**ewire the graph (JDR), which improves the performance of downstream node classification graph neural nets (GNNs). JDR works by aligning the leading spectral spaces of graph and feature matrices. It approximately solves the associated non-convex optimization problem in a way that handles graphs with multiple classes and different levels of homophily or heterophily. We theoretically justify JDR in a stylized setting and show that it consistently outperforms existing rewiring methods on a wide range of synthetic and real-world node classification tasks.

Published as a conference paper at ICLR 2025
JOINT GRAPH REWIRING AND FEATURE DENOISING VIA SPECTRAL RESONANCE
Jonas Linkerhägner'
Cheng Shi"
Ivan Dokmanić
Department of Mathematics and Computer Science
University of Basel
fi rsstnamme. wawtnameeeunnnnnm ch
ABSTRACT
When learning from graph data, the graph and the node features both give noisy information about the node labels. In this paper we propose an algorithm to jointly denoise the features and rewire the graph (JDR), which improves the performance of downstream node classification graph neural nets (GNNs). JDR works by aligning the leading spectral spaces of graph and feature matrices. It approximately solves the associated non-convex optimization problem in way that handles graphs with multiple classes and different levels of homophily heterophily. We theoretically justify JDR in a stylized setting and show that it consistently outperforms existing rewiring methods on wide range of synthetic and real-world node classification tasks.
INTRODUCTION
Graph neural networks (GNNs) are powerful deep learning tool for graph-structured data, with applications in physics (Mandal et al. 2022 Linkerhägner et al.] (202)), chemistry (Gilmer et al.) 2017). biology (Gligorijević et al.) 2021) and beyond (Zhou al.; 2020). Typical tasks across
disciplines include graph classification (Duvenaud et al. 2015 Xu et al. 2019). node classification
(Kipf and Welling 2017 Li al. 2019) and link prediction (Pan al. 2022).
Graph datasets contain two distinct types of information: the graph structure and the node features. The graph encodes interactions between entities and thus the classes or communities they belong to, similarly to the features. Recent work demonstrates that rewiring the graph by judiciously adding and removing edges may improve downstream GNN performance. That work argues that in a GNN, the graph serves not only to encode interactions but also to organize message passing computations (Battaglia et al. 2018). Even when it correctly encodes interactions may not be an effective computational graph rewiring it may then facilitate information flow.
Graph rewiring methods can be categorized into preprocessing and end-to-end. Preprocessing meth- ods rewire the graph by relating its geometric and spectral properties to information flow (Topping ct al. 2022 Nguyen et al. 2023 Karhadkar et al. (023). End-to-end methods (Giraldo et al. [2223] Gutteridge et al. 2023 Qian et al. 2024) dynamically rewire the graph during training, leveraging both the graph and the node features. Unlike preprocessing methods, they do not output an im- proved graph which restricts their interpretability and reusability. Our focus is the preprocessing methods.
There are thus two mechanisms that hurt performance of GNNs: (1) real-world graphs and features are noisy (the graph has spurious and missing links), and (2) geometric properties of the graph impede message passing. In this paper we focus on (1) and ask a natural question: can simple, joint feature and graph denoising improve performance of a downstream GNN?
We propose new rewiring scheme that also uses node features produce an enhanced graph. We leverage the fact that both the graph and the features are correlated with the labels. This is explicit in high-quality stylized models of graphs with features, including community models such as the contextual stochastic block model (cSBM) (Deshpande et al. 2018) and neighborhood graphs on
'These authors contributed equally.

---

Published as a conference paper at ICLR 2025
A VAV
Å ViRAA
Noley Graph
Rewired Gruph
Noisy
UPDATE
Demoised Features
Vig Vix-i
Vig
A
DENOISE
F.
r- Un.... U1g U(x)
UPDATE
Added
Removed
UEW
U0
Figure 1: Schematic overview of joint denoising and rewiring (JDR). In this example, we consider noisy graph as it occurs in many different real-world scenarios, in the sense that it contains edges between and within classes and its node features are not fully aligned with the labels. The graph's 's adjacency matrix A and binary node features X decomposed via spectral decomposition and singular value decomposition (SVD). The rewiring of A is performed by combining the information of its own eigenvectors V and the singular vectors U from X. The same applies vice versa for denoising, and both performed iteratively K times. We synthesize the rewired graph A and the denoised features X by multiplying back with the final V(K) and U(K)- To get specific properties like sparsity or binarity we can perform an UPDATE step, e.g. by thresholding (as done here). The resulting denoised and rewired graph is displayed on the right. Its structure now better represents the communities and the first entry of the features indicates the class assignment.
points from low-dimensional manifolds. This fact motivates various spectral clustering and non- linear dimensionality reduction methods (Shi and Malik 2000; Ng et al.] 200T). the cSBM, seminal theoretical work shows that jointly leveraging the graph (stochastic block model (SBM) and the features (a Gaussian mixture model (GMM)) improves over unsupervised clustering using either piece of information alone. However, the associated efficient inference algorithms based on belief propagation (Deshpande et al., 2018 Duranthon and Zdeborová (023) rely on perfect knowledge of the distribution of the cSBM and cannot be applied arbitrary real-world data.
Our contributions are as follows:
We take inspiration from work on the cSBM to design a practical algorithm for joint graph rewiring and feature denoising, which can improve the node classification performance of any downstream GNN on real-world data. We achieve this by adapting the graph and the features
maximize alignment between their leading eigenspaces. If these spaces are well-aligned we say that the graph and the features are in resonance.
2. We design an alternating optimization algorithm, joint denoising and rewiring (JDR), which approximates alignment maximization on spectrally-comples multiple classes, possibly homophilic or heterophilic. We prove that JDR improves align- ment between the graph and features, but also with the labels, on stylized generative model with noise from the Gaussian orthogonal ensemble (GOE); recent conjecture in the literature suggests that this generalizes to cSBM.
real-world graph data with
3. We run extensive experiments to show that JDR outperforms existing preprocessing rewiring strategies while being guided solely by denoising.
This last point suggests that although there exist graphs with topological and geometrical charac- teristics which make existing rewiring schemes beneficial, a greater issue in real-world graphs is noise the sense of missing and spurious links. This is true even when the graphs correctly flect the ground truth information. In a citation network, for example, citations that should exist may be missing because of incomplete scholarship. Conversely, citations that should not exist may be present because the authors engaged in bibliographic onnamentation. Our method is outlined in Figure I and the code repository is available online
https://githubs jnnniiiiii//// /JD/
2

---

Published as a conference paper at ICLR 2025
2 JOINT DENOISING AND REWIRING
2.1 PRELIMINARIES
We let 9 = EV) be an undirected graph with | = N nodes and an adjacency matrix A. To each node we associate f'-dimensional feature vector and collect these vectors in the rows of matrix X E I XNF We make extensive use of the graph and feature spectra, namely the eigendecomposi- tion A - VAV and the SVD X UEW", with eigen- and singular values ordered from largest to smallest. (As discussed below, in heterophilic graphs we order the eigenvalues of A according to their absolute value.) The graph Laplacian is L D A, where D is the diagonal node degree matrix. For to > 2 node classes, we use one-hot labels y E {0. 1..V.. x We write [T.] for the set (1, I.). In the balanced two-class case,
consider nodes be ordered so that the first half has label y; = -1 and the second half y: = 1. In semi-supervised node classification, the task is to label the nodes based on the graph (A and X) and a subset of the labels y. Homophilic graphs are those where nodes are more likely to connect with nodes with similar features or labels (e.g., friend- ship networks (McPherson et al. 200T)); heterophilic graphs are those where nodes more likely to connect with dissimilar nodes (e.g., protein interaction networks (Zhu et al. 2020
2.2 MOTIVATION VIA THE CONTEXTUAL STOCHASTIC BLOCK MODEL
For simplicity, we first explain our method for A = 2 classes and graphs generated from the cSBM. We then extend it real-world graphs with multiple classes and describe the full practical algorithm.
Contextual Stochastic Block Model. CSBMs (Deshpande et al. 2018) extend SBMs (Abbe) 2018),
a community graph model. by nigh-ddimessionl node features. They have become a key generative model for studying GNNs (Baranwal et al., 2021 Wu et al. 2023 Kothapalli et al. (023); for further pointers see Appendix A.2 We use cSBMs to build intuition about the graph rewiring and denoising problem. In balanced 2-class SBM, the nodes are divided into two equal-sized communities with node labels y: E {+1]. Pairs of nodes connect independently at random, with probability Gn/N inside communities and Conr /N across communities.
In the sparse regime (Abbe 2018), with average node degree = O(1), it is common to parameter- ize probabilities as Gm = d Avd and Cout = dd Xvd, where [^] can be seen as the signal-to-noise ratio (SNR) of the graph. The signal X; E RF node i comes from GMM,
H V N U.c
z VF
X;
(I)
where E ~ NN(.. (0, IF/F) (2) is the randomly drawn mean and z, ~ N' (O, IF) i.i.. Gaussian standard
noise. We set 7 = -/x and, following Chien et al. 2021), parameterize the graphs generated from the cSBM using / = arctan(>//1//1 A////)) For Φb - we get homophilic behavior; for 6 -> -1 we get heterophilic behavior. Close either extreme the node features contain little information. For á + 0 the graph is Erdōs-Rényi and only the features contain information.
Denoising and Rewiring the cSBM. In the cSBM, A and X offer different noisy views on the labels. One can show that up to a scaling and a shift, the adjacency matrix is approximately + + ZER; which means that it is approximately rank-one matrix with labels in the range, corrupted noise" " ZER (Erdōs and Rényi, 1959). Another way to see this is to note with 1 (Cin + Cout) 11
Zi CCin Cout Jyy' (Irom the definition of the SBM), Since A is close to EAA at high SNR, the eigenvectors contain information about the labels. It similarly follows directly from the definition that the feature matrix X is (up to a scaling) yu? + ZG where Zg is white Gaussian noise. It thus makes sense to use the information from X to enhance A and vice versa. Deshpande et al. (2018) show that analyzing the following optimization problem:
that EA
2N
maximize Av) + b(v, Xu)
wERR "ERR
(2)
subject to ||ll|2 ||a|||2 1, (v, 1) 5
for some carefully chosen value of b allows to characterize detection bounds in unsupervised community detection with k = 2. It is clear from the above reasoning that in the high-SNR regime (A and y far away from the detection threshold). the second leading eigenvector of A and the leading
3

---

Published as a conference paper at ICLR 2025
Feature Noise
1.0
Grnph Noiie
0.8
10.0
1.0
Graph Noise
Amplitde
20.1
0.8
0.6
10.
0.6
20.3
0.4
0.2
0.0
0.2
Amplitude
Grophh Stist
-0.2
0.0
0.4 0.2 0.0
0.0
Feature Noise
Feature Noise
0.2
0.4
0.2
Festure Gruph
Noise Noise
0.50
0.40
0.30
0.20
0.10
0.00
0.30
0.40
0.50
-0.50
0.00
0.10
0.50
(a)
(b)
Figure 2: An illustration of spectral alignment and resonance. In we plot r = x² Aa for different noise levels in A and æ E 11%, illustrated in the rows below. Without noise, a is exactly the label vector and A is block-diagonal. We apply multiplicative noise; namely, for each noise level, we flip the sign of proportion of values, resulting in random signal for =0.5. We that the value second leading eigenvector of A and the signal æ are perfectly aligned. In (b), we consider signal = Ax for different noise levels in and æ on a graph with 20 nodes; only quarter of edges are shown to reduce clutter; the intra-class edges are grey; the inter-class edges are black. The largest norm is obtained for noise-free A and æ (upper-left corner). The norm of ã and the separation of communities decrease along both noise axes. The inherent denoising capabilities of propagating æ on a high-SNR graph (Ma et al. 2021b) are also visible, particularly in the first two rows to the right.
depends on the noise level. The maximum is achieved for zero noise when the
left singular vector of X approximately coincide with the labels. The optimal v" is related to those vectors and aligned with the labels, since the quadratic and the bilinear form ( are individu- ally maximized by the mentioned vectors. The maximizer of the linear combination of both terms therefore combines the spectral information from both matrices the graph and the features. This suggests the following rationale for denoising: (1) We can interpret the value of as measure of alignment. Since v" corresponds to the labels, we can relate this measure to the quality of the label estimation. (2) We may leverage this alignment to rewire the graph and denoise the features. Namely, we could perturb A and X in a way that improves the alignment.
In real datasets, however, the optimal value of b is unknown, the scaling of X is arbitrary, and things are further complicated by having (many) more than classes Moreover. (2) is computationally hard. We thus define simple related measure of alignment which alleviates these issues.
Definition 1. Recall the decompositions A = VAVT, X UEWT, and let VL, UL denote the first columns of V and U and Il-Ilsp the spectral norm. We define graph-feature alignment as
Alignment, , (A, X) UZ
The logic of this definition is that for cBBM with high SNR and A classes, the information about labels is indeed contained in the leading L = i vectors of V and U. This follows directly by generalizing the formulation in to multiple classes and thus multiple eigenvectors (Decelle al. 2011 Lesieur et al. 2017). The quantity A Aligmment, (A, X) the cosine the angle between the subspaces spanned by the columns of Vz and U, To denoise the features and rewire the graph, we seek to improve the alignment.
Remark:
Given Aligumenty (A, X) and graph with Ao and Xo. the jointly denoised graph and features are the solution to
maximize Alignment, y, (A.X)
A.X
subject to ||A Aoll S Sv |X Xoll S 8x.
The parameters 6x > 0 modulate the strength of alignment. We will show empirically that
stronger alignment indicates better representation of the labels by A and X and thus better
4

---

Published as a conference paper at ICLR 2025
graph. Figure visualizes this connection. It shows that the response of the graph to features is maximized when the spectra of the graph and the features are aligned. We refer to the condition where the alignment is high spectral resonance; see Appendix A.1.1 for further discussion.
2.3 JOINT DENOISING AND REWIRING ALGORITHM
Maximizing the alignment 4 directly, e.g., using gradient descent, is computationally challenging. Here we propose a heuristic which alternates between spectral interpolation and graph synthesis. We later prove that the resulting algorithm indeed improves alignment, both with the labels and between the graph and the features, under a stylized noise model. The algorithm, illustrated in T comprises three steps. In Step I, we compute the spectral decompositions of A and X. To improve the alignment, we interpolate between the L largest eigenvectors in Step 2. Based on the new eigenvectors, we synthesize new graph in Step The three steps are iterated until stopping criterion is met. As is standard in the rewiring literature, the hyperparameters of the algorithm are tuned on a validation set. Formalizing this results in the JDR algorithm:
Step 1: Decomposition
= = VAV" with V (V11 , and X = UEW with =(11, U2 UN
Step 2: Interpolation: For every E [L].
ú; (1 - u; + 774 sign( (v), Uz))
ú = (1 - (]x u. + 77x sign( (u:; 1,) )
where j is chosen as argmax,e[r] (0 ug}l when updating and as argmax]e[1] (2,, wy)l when updating u; 74 and are hyperparameters that are tuned with a downstream algorithm on a validation set. We use sign() to handle sign ambiguities in decompositions.
Step 3: Graph Synthesis
À VAVT and X ÜEET
Step 4: Iterate steps K times with
A t- Ā and X - X.
Following 3 we consider the L leading eigenvectors of A and X for interpolation. Since these bases may be rotated with respect to each other (we note that (3) is insensitive to relative rotations, see Appendix A.1.2). when updating an eigenvector of A, we interpolate it with the most similar eigenvector X. We show empirically that this heuristic yields strong results, but also prove that it improves alignment with labels with a stylized noise model. We emphasize that the interpolation rates 77 and 7ι are the same across different eigenvectors and iterations K. After steps, we synthesize the final weighted dense graph À AK)AVTT A
(K)' To efficiently apply GNNs, we can
enforce sparsity, e.g., via thresholding or selecting the top-k entries per node. A detailed pseudocode given in Appendix A.I
An illustration. A simple edge case to illustrate how the algorithm works when either only A or X contains information. hyperparameter choice is = 0 and 4 simplifies to a maximization over A. Since there are only two classes, is sufficient to consider U1 of X is well-aligned with the labels. We thus replace the second leading eigenvector
cSBM with 0, X contains all the information, the best
1. From 22 we know that the leading left singular vector
in A = 1.0. After graph synthesis, the new of Á is not yet equal to u1. since u1 was not orthogonal to the other v,. We thus repeat the three steps K times. For Φ =1 all information is contained in the graph; similar argument can then be constructed mutatis mutandis.
by un by choosing
JDR Improves Alignment. We now show that JDR improves alignment, defined in ④ under stylized cSBM-like model. In fact, we show a stronger result: that the algorithm improves alignment with the true labels. Appealing universality arguments (Hu and Lu 2023), we study model with a spiked Gaussian matrix A yy" O where O is GOE noise instead of the binary matrix
5

---

Published as a conference paper at ICLR 2025
Table 1: Comparison of state-of-the-art preprocessing rewiring approaches. Note that we refer to the computational complexity per iteration. N denotes the number of nodes, m the number of edges and dmx is the maximum node degree. Additional details on the complexity of JDR are given in Appendix A.1 detailed runtime comparisons are in Appendix A.1.4
Method
Add edge
Remove edge
Use Features
Heterophilic?
Complexity
DIGL. (Gatteiger et al. 2019
X
X X
x
O(N)
FoSR (Krrhadkar et al. 2003
X
O(N2) Omma O(N)
BORF (gguyen et al. 2023
V
X
/
JDR (Ours)
as defined in In the cSBM context, a recent conjecture with strong empirical support states that replacing the binary A by A leads the same behavior in downstream tasks such as community detection (Deshpande et al. 2018 Lu and Sen 2023) and node classification (Shi et al. 2024). An iteration of JDR with L 1 applied this model, first interpolates between the leading eigenvector 1) (4 4. and leading left singular vector u (X) = ux Graph and feature synthesis then yields A = A + (Ar) (-VAVA + O and X,x X + (X) (-ux + (x Here U (1 MA)UA + sign( (U ux) (ux))mx MAu and åx (1 7xx Jxx sign (UA, ux ux))xx UA. where w² (X) uxx is the leading right singular y NV we have
A, and features X = U + +
vector of X. Denoting
Proposition 1. Let À > 1 and μ VT with N/F. There exist v/a nx all Пл E (0, 122) and yx E (0, m when N 0o, we have
E (0,1) such that for
(A,,)))))) 9) (A)
and (u1(X,) (X, xx ). 4) 2 (u) (X). 9g)
In words, interpolation improves alignment of the largest eigenvector with the labels for suffi- ciently large graphs. The proof, based on the BBP transition in the spiked covariance model (Baik) et al. 2005) and the fluctuation of the leading eigenvector, can be found in Appendix [A.e] It seems challenging but quite possible to extend this argument to binary A. One would then interpolate between ur and A's second leading eigenvector 22 A)), which has similar properties to ii (A9), especially in a dense graph regime (Nadakuditi and Newman 2012).
3 EXPERIMENTS
We extensively evaluate JDR on both synthetic data generated from the cSBM and real-world bench- mark datasets. We follow experimental setting from Chien et al.) (202T) and evaluate JDR for semi- supervised node classification with different downstream GNNs. We also adopt their data splits, namely the sparse splitting 2.5% 255% 22.52//55// 95% for training, validation and testing, respectively, or the dense splitting 60% 40%/20% 20%. For the general experiments, we perform 100 runs with dif- ferent random splits. For the scalability experiments, we use the experimental settings of the re- spective works (Lim al. 2021 Platonov et al. 2023). We report the average accuracy and the 95%-confidence interval calculated via bootstrapping with 1000 samples. All experiments are re- producible using the code provided.
Baselines. Following recent works on rewiring, we use graph convolution network (GCN) (Kipf and Welling 2017) as our downstream GNN. To obtain a more comprehensive picture, we addi- tionally evaluate the performance on the more recent generalized PageRank graph neural network (GPRGNN) (Chien al., al.] 2021). We compare our algorithm with the state-of-the-are rewiring meth- ods first-order spectral rewiring (FoSR) (Karhadkar et al., 2023). batch Ollivier-Rice flow (BORF) (Nguyen et al., [023) and diffusion improves graph learning (DIGL) (Gasteiger et al.) 2019). FoSR approximates which edges should be added to maximize the spectral gap to reduce oversquashing. BORF adds edges in regions negative curvature in the graph, which indicate bottlenecks that can lead to oversquashing of the messages passed along these edges. A positive curvature indicates that there are so many edges in this area that messages could be oversmoothed, which is why edges removed here. We compare computational and implementation aspects of JDR and basclines in Table [ On the cSBM, we compare to an optimal algorithm, namely the approximate mes- sage passing-belief propagation (AMP-BP) algorithm (Duranthon and 7deborová 2023). AMP-BP

---

Published as a conference paper at ICLR 2025
is asymptotically optimal (in the large dimension limit) for unsupervised semi-supervised com- munity detection in the cSBM. It relies on knowing the distribution of the cSBM and is thus not applicable to real-world graphs with unknown characteristics and complex features.
Hyperparameters. Unless stated otherwise, we use the hyperparameters from Chien et al. (2021) for the GNNS and optimize the hyperparameters of JDR using a mixture of grid and random search on the validation set. We use the top-64 values of Á to enforce sparsity and interpolation to update the features. For DIGL, FoSR and BORF, we tune their hyperparameters using grid search, closely following the given parameter range from the original papers. For all hyperparameter searches use GCN and GPRGNN as the downstream models on 10 runs with different random splits. A detailed list of all hyperparameters can be found in Appendix A.7 or in the code repository.
3.1 RESULTS ON SYNTHETIC DATA
We first test JDR on data generated from the cSBM, as we can easily vary the SNR of the graph and the features verify its denoising and rewiring capabilities. We focus the sparse splitting, since for the dense splitting GPRGNN already matches the performance of AMP-BP.
Does JDR Maximize Alignment? Before discussing Figure 4 which shows the results of baselines and JDR for different values of σ, we verify empirically that our alternating optimization algorithm indeed approximates solutions to 44. As shown in Figure 3. the quantity Aligument I A, X) improves significantly after running JDR, across all á. As we show next, this happens simulta- neously with improvements in downstream performance, which lends credence to the intuitive reasoning that mo- tivates our algorithm. For additional alignment results real-world data and baselines, refer to Appendix (A.5.5)
1.0
Algmmentt(AA x
0.8
0.6
JDR None
0.4
0.2
-1.0
00.7
00.5
0.25
0.0
0.25
0.5
0.75 1.0
Heterophilic Regime. For é -0.55, the predictions of GCN are only slightly better than random. GPRGNN performs much better, since it can learn higher order poly- nomial filters to deal with heterophily. GCN+JDR outperforms the baseline by very large margin; handles heterophilic data well. Using JDR for GPRGNN further improves its already strong performance in this regime. Both GNNs benefit less from the denoising in the weakly heterophilic setting where they exhibit the worst performance across all é. The difference between = 0 and the weakly heterophilic regime is that "optimal denoising" for & 0 is straightforward, since all the information is contained in X. We show similar findings for spectral clustering on the cSBM in Appendix A.5.6
Figure 3: Alignment of the leading eigenspaces according to (3) for graphs from the cSBM with different ø.
Weak Graph Regime. For |o] S 0.25, where the SNR of the graph is very low, both GNNs perform poorly. Intuitively, when the graph is very noisy, GNN is suboptimal model, since it leverages the graph structure. A simple MLP baseline, using only the node features, outperforms GNNs in this setting, with all three approaches lagging far behind AMP-BP BP. Using JDR, we see significant im- provements for both GNNs, which almost catch up with AMP-BP for & 0. Although all information was available in the node fea- tures, the GNN with JDR now clearly out- perform the MLP by a very large margin. We argue that this is because in the semi- supervised setting with few labels available, the GNN generalizes much better.
100
90
Accuracy %
80
70
AMP-BP
GPRGNK
60
GPREKA
GCN+JDR
50
MLP
Heterophilic
Weak
Homophilic
40
1.0
0.75
0.5
0.0
0.5
0.75
Figure 4: Test accuracy on graphs from the cSBM across different o The error bars indicate the 95% confidence interval. JDR improves the performance for both GNNs across all ø.
Homophilie Regime. For Φ > 0.25, GCN and GPRGNN perform similarly well, with

---

Published as a conference paper at ICLR 2025
Table Results on real-world homophilic datasets the sparse splitting (2.5%/2..%//9%% Mean
accuracy across runs (%) + 95% confidence interval. Best average accuracy in bold.
Method
Cora
CiteSeer
PubMed
Computers
Photo
GCN
77.2610.35
67.16110.37
84.2210.09
84.4210.31
91.33
GIN+
79.27+0.26
68.03+00.33
84.60++.099
86.00++0.24
92.00+0.23
FCN+
77.23+0.34
67.03+0034
84.21+0.09
84.34+0.27
91.36++0.28
GCN+BORF
77.23=0.35
66.9610.38
84.22:10.09
84.46:10.30
91.26:10.30
GCN+JDR
79.96:10.26
69.35-0.28
84.79=0.08
85.66:0.36
92.52:0.23
GPRGNN
79.65=10.33
0..50
84.33110.00
84.06=0..4
92.01=0.41
GPRGNN+DIGL
79.77=0.30
07.50
84.72:10.10
86.25::0.88
92.31
GORGNN+FOSR 79.22:4031
67.30+00.8
84.32+4.09
84.21=0.46
92.07
GPRGNN+BORF 09.43=00.30
67.48
84.36+10.10
84.08=0.43
92.11+0.38
GPRGNN+JDR
80.77+0.29
69.17
85.05+0.08
84.77=0.35
92.68=0.255
Table 3: Results real-world heterophilic dataset in the dense splitting (60%/20%%/20%) Mean
accuracy across runs (%) + 95% confidence interval. Best average accuracy in bold.
Method
Chamelcon
Squirrel
Actor
Texas
Cornell
GCN
67.65:10.12
57.94+0.31
34.00+00311
75.62+1.122
64.68:+1.25
GCN+DIGL
58.04=0.48
39.64410.34
39.5710.29
91.05:10.73
88.49:10.74
GCN+FoSR
67.67=0.39
58.12:40.35
33.98:0.300
78.31+1.07
65. 65.64+1.06
GCN+BORF
67.78=00.3
OOM
33.95++0331
76.66=11.10
68. 1.11
GCN+JDR
69.76:10.50
61.76:0.39
40.47:10.11
85.12:0.74
84.51+1.06
GPRGNN
69.15:10.51
03.444+0.77
39.52:0.22
92.82+0.67
87.79+0.899
GPRGNN+DIGL
66.57-0.46
42.9811.37
39.6110.21
91.1110.72
88.06-10.81
GPRGNN+FOSR
68.96=00.45
52.34+00377
39.47+0.21
93.16+0.66
8..51+1.04
GPRGNN+BORF
69.44=0.56
OOM
39.55+0.20
93.53+0.68
88.8 88.83+1.06
GPRGNN+JDR 71.00+0.50
60.62+0.38
41.89+0.24
93.85+0.54
89.45=0084
GPRGNN achieving better results for 6 1.0. With JDR, they become much more comparable to each other and closer to AMP-BP. Even though the hyperparameters of JDR were tuned using only GCN as a downstream model, it also improves the performance GPRGNN for all Φ.. The general robustness to hyperparameter changes is also analyzed in detail in Appendix A.6
3.2 RESULTS WORLDWORLD DATA
We evaluate JDR on five common homophilic benchmarks datasets, namely the citation graphs Cora, CiteSeer, PubMed (Sen et al.) 2008) and the Amazon co-purchase graphs Computers and Photo (McAuley et al. 2015). For heterophilic datasets, we rely on the Wikipedia graphs Chameleon and
Squirrel (Rozemberezki et al. (202), the WebKB datasets Texas and Cornell used in et al.) (2020) and the actor co-occurence network Actor (Tang et al.) 2009). To show the scalability of JDR on larger heterophilic datasets, we further report the results for the Yandex Q network Questions (Platonov et al., 2023) and the social networks Penn94 and Twitch-Gamers (Lim et al. 2021). Fur- ther details about all datasets are in Appendix [..4 Following [Chinn et al.) (2021) l. we evaluate the homophilic datasets in the sparse splitting, staying close to the original setting of Kipf and Welling
(2077) and the heterophilic datasets in dense splitting (Pei et al. (020). The remaining larger graphs
evaluated using their original splits. For further results and splits, see Appendix A.5
Homophilic Datasets. Table Tables shows the results JDR compared to the baselines. For both GNNs, JDR achieves the best results four out of five datasets. GCN and GPRGNN with JDR achieve similar performance here, which is consistent with the findings for the homophilic cSBM. DIGL also performs strongly on the datasets and ranks first on Computers. However, with GPRGNN downstream model, the improvements are quite small. FoSR and BORF only marginally improve the performance of the GNNs in this setting.
8

---

Published as a conference paper at ICLR 2025
Heterophilic Datasets. The results in Table 3 show that GCN+JDR can catch up significantly compared to GPRGNN, but GPRGNN+JDR generally performs better. This is in line with the findings for the heterophilic cSBM. DIGL performs well on Actor, Texas and Coreell despite its inherent homophily assumption. The reason for this is the chosen smoothing kernel, which results in graph that is evenly connected everywhere with small weights. GCN then largely ignores the graph and thus performs very similarly to an MLP, which performs already quite well on these datasets (Chien al. (02T). However, this fails for GPRGNN, which can make better use of the weak, complex graph structures. FoSR and BORF also improve performance here in most cases, but they are outperformed by JDR in all cases, often by large margin. The out-of out-of-memory error on Squirrel for BORF results from its computational complexity of O (medma)) because the dataset has a large number of edges m and a high maximum node degree dmax.
Larger Graphs. Scalability is prob- lem for preprocessing rewiring methods because applying them to large graphs requires significant amounts of memory and compute (see complexity in Table T). Since the decompositions needed for JDR can be truncated to the largest L vec- tors, it is still applicable to larger graphs. The experimental results on larger het- erophilic datasets in Table 4 verify this, They show that JDR can significantly improve performance for these larger graphs, while FoSR only achieves marginal improvements. BORF ran out of memory on all of these datasets and DIGL is unable to improve due to its inherent homophily assumption. While scaling JDR to even larger graphs with millions of nodes is possible in principle, requires more optimized and efficient implementations and is therefore left for future work.
Table 4: Results on large datasets. Mean accuracy (ROC
AUC for imbalanced Questions) across runs (%) = 95% confidence interval. Best results in bold.
Method
Questions
Penn94
Twitch- gamees
nodes edges
48, 08,921
41,554 554
168, 114 6.8M
0.15M
1.36M
GCN
75.31 0.81
80,40 0.18
64.56 + 0.19
GCN+DIGL
73.35 + 0.64
74.70 0.32
61.64 + 0.14
GCN+FoSR
75.51 + 0.73
80.54
+ 0.31
64.65 + 0.15
GCN+JDR
77.52 + 0.63
82.30 :: 0.61
65.14 = 0.19
4 RELATION TO PRIOR WORK
JDR is most related to preprocessing rewiring methods which we thus use as baselines. To provide a more thorough overview, we also place it within the extended literature.
Graph Rewiring. Recent work show that even when a graph correctly encodes interactions it may not be an effective computational graph for GNN due to conditions such as oversquashing (Alon Giovaani Giovanni
and Yahav] [
al.) (203)) and oversmoothing (Chen et al. [0220)). Recently many methods have been proposed to address this, notably graph rewiring methods. They can be divided into preprocessing and end-to-end methods. Preprocessing methods rewire the graph using geomet- ric and spectral properties, including curvature (Topping et al. 2022 Nguyen et al., [ Fesser and
Weber 2024 Bober et al. (024)), expansion (Deac et al. 2022 Banerjee et al. (2022). effective resis- tance Bllckk al. 2023] Shen al. 2024). and spectral gap Karhadkar al. 2023). Conceptually related is difffusion-hasee rewiring (Gasteiger et al. 2019) that smooths the graph with a diffusion
kernel. This can be interpreted as graph denoising, but is only suitable for homophilic graphs Our approach is related to rewiring but with several key differences (see Table D Our rewiring strategy aims to denoise the graph (rather than control some geometric property) with the goal improve downstream performance, while the classical rewiring literature focuses on optimizing the graph for message passing computations.
Early end-to-end methods randomly drop edges during training to reduce oversmoothing (Rong et al. 2020). Subsequent work (Gutteridge et al. 2023 Qian et 2024) incorporates latent features to dynamically rewire the graph. Ji et al. (2023) use the estimated labels of a GNN to rewire the graph during training of the same GNN, Giraldo et al. (2023) use curvature information for dynamic rewiring. Graph Transformers (Dwivedi and Bresson 202 Rampasek et al. 2022) aim to overcome oversquashing in GNNs via global attention. In order to handle large graphs, these works still need to revert to sparse, non-global attention (Gabrielsson et al. 2023 SSiizad et al., 2023). Unlike preprocessing methods, end-to-end methods cannot output an improved graph which restricts their interpretability and reusability.

---

Published as a conference paper at ICLR 2025
Graph Denoising. There is extensive literature on denoising signals graphs using graph filters (Chen et al.) 2014; Ma et al. 2021b Liu et al. 2022). However, we are interested in modifying the structure of the graph itself (rewiring), in way that benefit any downstream algorithm. [Dong and Kluger 2023) recently proposed a new metric to measure graph noise that correlates well with GCN performance. Based this, they develop a method for graph denoising via self-supervised learning and link prediction. We discuss the relation to our work in detail in Appendix IA.5.7 also evaluate our rewired graphs using their ESNR metric there. More broadly, link prediction (Zhang and Chen 2018) Pan et al. 2022) can be seen as a tool for graph denoising; this perspective has been applied, for instance, to denoising neighborhood graphs arising in molecular imaging (Debarnot et al. 2022).
Graph Structure Learning. The aim of graph structure learning (GSL. (Zhu et al.
2022) to make
GNNs more robust against adversarial perturbations of the graph or to learn a graph for data where there is no graph to start with [Jin et al. 2020; Chen et al.) 2020b Wang et al. 2024 Zhu et al.) 2024). Lv ct al. (2023) build a neighborhood graph over features and interpolate between it and the input graph, which is a form of alignment. Unlike our method, they do not use spectral information, unable to deal with noisy features and are only suitable for homophilic graphs where similarity- based connection rules apply. Even though both our work and GSL consider noisy graph settings, they are conceptually very different. We do not add noise to graph datasets which corresponds to perturbation rate of 0 ("clean data") in GSL nomenclature. Instead, we acknowledge that in every real world dataset, there is noise in the graph structure and the node features, and one manifestation of this noise is misalignment of their leading eigenspaces. We then use this to rewire the graph (and denoise features) so as improve the overall node classification performance of downstream GNNs. Naturally, GSL methods have difficulties to improve over baselines in this setting (Jin et al.) 2020 Dong and Kluger 2023). Our method, on the other hand, is not designed to handle strong per- turbations and therefore cannot compete with GSL methods developed for specifically this purpose.
Graph Regularization. Laplacian regularization (Ando and Zhang 2006), originally stemming from semi-supervised representation learning, has been adapted by recent methods (Yang et al.) 2021 Ma et al.] 202 to also improve the performance of GNNs. An extra loss term is added during the GNNs training, which contains additional information about the graph structure to reduce oversmoothing. Their main limiting factor is the underlying homophiliy assumption: is assumed that connected nodes are more likely to share the same label.
CONCLUSION AND LIMITATIONS
Our experimental results clearly show that spectral resonance is a powerful principle on which to build graph rewiring (and feature denoising) algorithms. JDR consistently outperforms existing rewiring methods DIGL, FoSR and BORF on both synthetic and real-world graph datasets. The smaller performance gains of GPRGNN suggest that this more powerful GNN is already able to leverage the complementary spectra of graphs and features to some extent.
The main limitation of JDR is that it cannot be used without node features. The preprocessing rewiring methods that we compare with do not have this limitation as they only use the graph for rewiring, but in turn, they cannot take advantage of features. Since JDR is the first method to jointly denoise the graph and the features, there are no other methods to which it could be directly compared. Our experiments thus highlight what advantage features bring to rewiring.
Furthermore, our results suggest that noise in real-world graphs is an important limiting factor for the performance of GNNs. would be interesting to see whether feature-agnostic rewiring from a denoising perspective, for example using link prediction, could be used to improve the downstream performance. related idea that we tested but could not get to work well is to combine existing geometric rewiring algorithms with JDR. Intuitively, there should be way to benefit from both removing noise and facilitating computation, but we have to leave that exploration for future work.
We also note that most current rewiring methods be applied to graph level tasks, while JDR is currently limited to node classification. is an open question how to extend the cSBM idea to graph-level problems.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGMENTS
JL, CS and ID were supported by the European Research Council (ERC) Starting Grant 852821 SWING.
REFERENCES
E. Abbe. Community detection and stochastic block models: Recent developments. Journal of Machine Learning Research, 18(177):1-86, 2018. URUnttp:://mL....r////ppees
16-480. html
U. Alon and E. Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021. hnttps://opeereeeeee
net/forue www.rrummiiiiiiie 1d=11000PhCCVHH
R. Ando and Zhang. Learning on Graph with Laplacian Regularization. In Schölkopf, J. Platt, and T. Hoffman, edvtons in Neural Information Processing Systems, volume 19. MIT Press, 2006. utt./ttpes/ppppoeeddissnerrr.iep
2006/ 20007///177777555000002222222233
Baik, G. B. Arous, and Péché. Phase transition of the largest eigenvalue for nonnull complex sample covariance matrices. The Annals of Probability, 33(5); 1643 1697, 2005, doi: 10.1214/ 0091 19915000000003,33. URL https: /oii wttg/1...11.0000111........ /
K. Banerjee, K. Karhadkar, Y. G. Wang. U. Alon, and G. Montúfar. Oversquashing in gnns through the lens of information contraction and graph expansion. In 2022 58th Annual Aller- ton Conference on Communication, Control, and Computing (Allerton), page 1-8. IEEE Press, 2022. doi: 10.1 2t.1199/llectom/993.220022929999
URL https::/aci..oree http:////eo..oo11011111000/
A Allerton4 99w.mm92222........ 2022..929326 9929363
A. Baranwal, K. Fountoulakis, and A. Jagannath. Graph convolution for semi-supervised classi- fication: Improved linear separability and out-of-distribution generalization. In M. Meila and T. Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, vol- ume 139 of Proceedings of Machine Learning Rexearch, pages 684-693. PMLR, 07 2021. URL https: /ttp://rroceeeeeee ngs ml w.w.sp..ss/se........... 39/ 21a.html
W. Battaglia, J. B. Hamrick, V. Bapst, A. Sanchez-Gonzater V. Zambaldi, M. Malinowski. A. Tacchetti, D. Raposo, A. Santoro, R. Faulkner, C. Gulcehre, F. Song, A. Ballard, J. Gilmer, G. Dahl, A. Vaswani, K. Allen, C. Nash, V. Langston, C. Dyer, N. Heess, D. Wierstra, P. Kohli, M. Botvinick, O. Vinyals, Y. Li, and R. Pascanu. Relational inductive biases, deep learning, and graph networks, 2018.
Benaych-Georgee and R. Nadakuditi. The singular values and vectors of low rank perturbations of large rectangular random matrices. Journal of Multivariate Analysis, 111:120-133 2012.
Benaych-Georges, A. Guionnet, and M. Maida. Fluctuations of the extreme eigenvalues of finite rank deformations of random matrices. Electronic Journal of Probability, 16:1611-166, 2011.
M. Black, Z. Wan, A. Nayyeri, and Y. Wang. Understanding oversquashing in GNNs through the lens effective resistance. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, Sabato, and J. Scarlett, editors, Proceedings the 40th International Conference Machine Learning, volume 202 Proceedings of Machine Learning Research, pages 2528-2547. PMLR, 7 2023. URL
mlr.
html
Bober, Monod, E. Saucan, and N. Webster. Rewiring networks for graph neural network training using discrete geometry. In H. Cherifi, L. M. Rocha, C. Cherifi, and M. Donduran, edi- tors. Complex Networks Their Applications XII. pages 225-236. Cham, 2024. Springer Nature Switzerland. ISBN 978-3-031 118-3-031-534662 -534683-.
S. Chanpuriya and C. Musco. Simplified graph convolution with heterophily. In S. Koyejo, S. Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 271 27184-27197. Curran Associates, Inc.,

---

Published as a conference paper at ICLR 2025
2022. URL htttss//proeedd..ss..eersrssss.s http://aerrriilllpaaaaa///////
D. Chen, Y. Lin, W. Li, P. Li, J. Zhou, and X. Sun. Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. Proceedings of the AAAI Confer- ence on Artificial Intelligence, 3(04))3438-344) 2020a. doi: 10. (t1.//9/aaaa.33444.55.. URL
https: //t:s////jjj..////// aaai. org/ index http:///wwppaa.aaarr.../////////
S. Chen, A. Sandryhaila, J. M. F. Moura, and J. Kovacevic. Signal denoising on graphs via graph filtering. In 2014 IEEE Global Conference on Signal and Information Processing (GlobalSIP), pages 872-876, 2014. doi: 10.1 11109//iobbISIP2224470002244
Y. Chen, L. Wu, and M. Zaki. Iterative deep graph learning for graph neural networks: Better and ro- bust node embeddings. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural Information P Processing Systems, volume 33, pages 19314-19326. Curran Associates, Inc., 2020b. URL https://rroceeeeigggssoot new.eng...eeuiggno eeweeeeeeeeeeeeeeeeeeeeeee www.e
files/
paper htt.0////0../0eeceeeeeeeeee12222
E. Chien, J. Peng, P. Li, and O. Milenkovic. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, 2021. URL https://
openreview 1ettreeeeee//oou211/
E. Chien, W.-C. Chang, C.-J Hsieh, H.-F. Yu, Zhang, O. Milenkovic, and I. Dhillon. Node feature extraction by self-supervised multi-scale neighborhood prediction. In International Con- ference on Learning Representations, 2022. URL Id=KJqgliHbsB
A. Deac, M. Lackenby, and P. Veličković. Expander graph propagation. In NeurlPS 2022 Workshop on Symmetry and Geometry Neural Representations, 2022. URL /ttL/httpps::/ppeeeewiee net/ hir.rummm.d-ccchhhhhhh....
V. Debarnot, V. Kishore, C. Shi, and I. Dokmanić. Manifold rewiring for unlabeled imaging. In 2022 Asia- sicaffccific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC), pages 1-8, 2022.
doi: 10.239 (02299//AASPPAAAS555999220000009
A. Decelle, F. Krzakala, C. Moore, and L. Zdeborová. Asymptotic analysis of the stochastic block model for modular networks and its algorithmic applications. Phys. Rev. E, 84:066106, Dec 2011. doi: 10.1103/pyy.eee..8..000 R...0..0.........6... URL httpt/tt/////iitii aps.nnkkp...... owtp////ooo////oo///ooooooo////. 11 TTC3/PhysRee
84. 066106
Y. Deshpande, S. Sen, A. Montanari, and E. Mossel. Contextual stochastic block models. Advances in Neural Information Processing Systems, 31, 2018
Di Giovanni, L. Giusti, Barbero, G. Luise. P. Lio, and M. M. Bronstein. On over-squashing in message passing neural networks: The impact of width, depth. and topology. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, Sabato, and J. Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning. volume 202 of Proceedings of Machine Learning Research, pages 7865 7885. PMLR, 07 2023. TRR/httpps//pprceeiii molg..mmr..... .ml. press// v2C2/d www.ggiivannninnn 23a. html
M. Dong and Y. Kluger. Towards understanding and reducing graph structural noise for GNNs. In A. Krause, Brunskill, K. Cho, Engelhardt, S. Sabato, and J. Scarlett, editors, Proceedings of the 40th International Conference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 8202-8226. PMLR, 07 2023. URL httpp::/prrocedd.. ing.s.
mlr. www.pressssse.. w21//2222////// /ttp///2222d/dgg222 dong/oa.......m html
O. Duranthon and I.. Zdeborová. Optimal inference in contextual stochastic block models, 2023.
D. K. Duvenaud, D. Maclaurin, J. Iparraguirre, R. Bombarell, T. Hirzel, A. Aspuru-Guzik, and R. P. Adams. Convolutional networks on graphs for learning molecular finger- prints. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett, editors, Ad- vances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015. URL
(ttaaeeeffiee//pppe///1111 file/f Fee//9be31111 1eebe3111e6881111111 oal.f
12

---

Published as a conference paper at ICLR 2025
V. P. Dwivedi and X. Bresson. A generalization of transformer networks to graphs. AAAI Workshop on Deep Learning on Graphs: Methods and Applications, 2021.
P. Erdös and A. Rényi. On random graphs i. Publicationes Mathematicae Debrecen, 6:290-297, 1959.
L. Fesser and M. Weber. Mitigating over-smoothing and over-squashing using augmentations of forman-ricci curvature. In S. Villar and B. Chamberlain, editors, Proceedings of the Second Learning on Graphs Conference, volume 231 of Proceedings of Machine Learning Research, pages 19:1-19:28. PMLR, 11 2024. URL https:: htttps:/pproceeding wttp.gggs......s//233333 Fesser htm
M. Fey and J. E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
R. B. Gabrielsson, M. Yurochkin, and J. Solomon. Rewiring with positional encodings for graph neural networks. Transactions on Machine Learning Research, 2023. ISSN 2835-8856. URL
https: /ttp///eeeeieweeeeeeee forum? dtrrmmmddddd322gg222
Gasteiger, S. WeiB enberger, and S. Günnemann. Diffusion improves graph learning. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Gameet,, edi- tors. Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https:: File/ (tlee3333322722c25333 2t114/76622221114477744434444443 8d73 b4g.
ngs www.ins.rr..... cc/paper. fi files/paper/20199
J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML'17 17, page 1263-1272 1272. JMLR.org, 2017.
Giraldo, K. Skianis, Bouwmans, and F. D. Malliaros. On the trade-off between over- smoothing and over- svur-squahhing in deep graph neural networks. CIKM '23, page 566-576, New York, NY. USA, 2023. Association for Computing Machinery. doi: 10. 10.1145//583388.36649977 URL https: / /055///00..0911..111/////// 2144/35833388888 3614997
V. Gligorijević, D. Renfrew, Kosciolek, K. Leman, D. Berenberg, Vatanen, Chandler, B. C. Taylor, I, M. Fisk, H. Vlamakis, R. J. Xavier, R. Knight, K. Cho, and R. Bonneau. Structure- based protein function prediction using graph convolutional networks. Nature Communications, 1261))3168, 2021. ISSN 2041-1723. doi: 10. 0008///41467-021-23330000 org/10 1038/1300000 //14//441677 021 23303-3
URLhttps:///do
B. Gutteridge, X. Dong, M. M. Bronstein, and F. Di Giovanni. DRew: Dynamically rewired message passing with delay. In Krause, E. Brunskill, Cho, B. Engelhardt, S. Sabato, and Scarlett, editors, Proceedings of the 40th International Conference Machine Learning. volume 202 of Proceedings of Machine Learning Rexearch, pages 12252-12267. PMLR, 07 2023. URL https: http://pooceeee....eeepp/o mlr.
www.gngs.m......s.....ee press v22//v22/////222 http:////2//ttttttgeeeeeeeee htm
H. Hu and Y. M. Lu. Universality laws for figh-dimensional learning with random features. IEEE
Transactions on Information Theory, 69(3): 1933) 1964, 2023. doi: 10. D00110991.2202232116666
Ji, S. H. Lee, H. Meng, K. Zhao, Yang, and W. P. Tay. Leveraging label non-uniformity for node classification in graph neural networks. In Proceedings of the 40th International Conference on Machine Learning, ICML'23. JMLR.org, 2023.
W. Jin, Y. Ma, X. Liu, X. Tang, S. Wang, and J. Tang. Graph structure learning for robust graph neural networks. In Proceedings of the 26th ACM SIGKDD International Conference Knowl- edge Discovery & Data Mining, KDD '20, page 66-74, New York, NY, USA, 2020. Associa- tion for Computing Machinery. ISBN 9781450379984.
doi: 01145/3394446.3403044 URL
ht https: //dos doi. /tt.://...115333444886 3403049
K. Karhadkar, P. K. Banerjee, and G. Montufar. FoSR: First-order spectral rewiring for addressing oversquashing in GNNs. In The Eleventh International Conference on Learning Representations, 2023. URL htt.hhtttss/ppeeeeeee wtt.ee/wwww.....e.ooo.ooeeeeaaae
13

---

Published as a conference paper at ICLR 2025
T. N. Kipf and M. Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations, 2017. UtL net/ met//orze F
Kothapalli, T. Tirer, and J. Bruna. A neural collapse perspective on feature evolution in graph neural networks. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
URL https://ppeereviee net. 2twp:enreeeiiee..tttoooo.2m2.2. sx
T. Lesieur. F. Krzakala, and L. Zdeborová. Constrained low-rank matrix estimation: phase transi- tions, approximate message passing and applications. Journal of Statistical Mechanics: Theory and Experiment, 2017(7):073033, jul 2017. doi: 10. 10.188/1742-546//aa 10011110008800222-4400222 1/dx. 17
URL https:
aa
P. Li, I. Chien, and O. Milenkovic. Optimizing generalized pagerank methods for seed -xed-expansion community detection. In Advances in Neural Information Processing Systems, volume 32. Cur- ran Associates, Inc., 2019. URL http:::ttt.cctssseeseeeee ngs. nwwrips wctppaap..cppppprrr.........pp fi / pappr/2201///1ee/aaea33222211110 Paa
D. Lim, F. M. Hohne, X. Li, S. I.. Huang, V. Gupta, O. P. Bhalerao, and S.-N. Lim. Large scale learn- ing on non-homophilous graphs: New benchmarks and strong simple methods. A. Beygelzimer, Y. Dauphin, P. Liang, and J. W. Vaughan, editors, Advances in Neural Information Processing Systems, 2021. URL https: pettps://pperreview
f d==D FGuBWWTOd
J. Linkerhägner, N. Freymuth, P. M. Scheikl, F. Mlthis-Ullrich, and G. Neumann. Grounding graph network simulators using physical sensor observations. In The Eleventh International Confer- ence on Learning Representations, 2023. URL ]sZsEdBVEY
S. Liu, R. Ying, H. Dong, L. Lin, J. Chen, and D. Wu. How powerful is implicit denoising in graph neural networks, 2022.
C. Lu and Sen. Contextual stochastic block model: Sharp thresholds and contiguity. Journal of Machine Learning Research, 24(54):1-33) 2023.
Luan, C. Hua, M. Xu, Q. Lu, Zhu, X.-W. Chang, J. Fu, Leskovec, and D. Precup. When do graph neural networks help with node classification? inves- tigating the homophily principle on node distinguishability. A. Globerson, K. Saenko, M. Hardt, and S. Levine, editors, Advances in Neural In- formation Processing Systems, volume 36, pages 28748-28760. Curran Associates, Inc., 2023. URL ht https://ppoceedddggg wwwrinuuriss. cc wwpperppppppppp.ppappeeeoeec...e files/paper/2023/ pdff
Oh, Naumann,
File/
S. Lv, G. Wen, S. Liu, L. Wei, and M. Li. Robust graph structure learning with the alignment of features and adjacency matrix, 2023.
X. Ma. H. Chen, and G. Song. Lereg: Empower graph neural networks with local energy regular- ization. In Proceedings of the 30th ACM International Conference on Information Knowl- edge Management, CIKM '21, page 1191-1201, New York, NY. USA, 2021a. Association for Computing Machinery. ISBN 4503446944
doi: 10.1145/3456637.344838 3482244 URL
pettps://do..orgee www.roro...... htt.:/00.001111111555515111 110111441133333111 3482447
Y. Ma, X. Liu, T. Zhao, Y. Liu, J. Tang, and N. Shah. A unified view on graph neural networks as graph signal denoising. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management. CIKM '21, page 1202-1211, New York, NY, USA, 2021b. ISBN 9781450384469, doi: 10.1 145/3459637.348222
Y. Ma, X. Liu, N. Shah, and J. Tang. Is homophily a necessity for graph neural networks? In International Conference on Learning Representations, 2022. URL MRLLittps///ppeeeiiiee met//ooun: www.uiiddddisssPss
R. Mandal, C. Casert, and P. Sollich. Robust prediction of force chains in jammed solids using graph neural networks. Nature Communications, 13:4424, 07 2022. doi: 10.1038/<41467-222 1467-02--1173--3.
14

---

Published as a conference paper at ICLR 2025
J. McAuley, C. Targett. Q. Shi, and A. den Hengel. Image- based recommendations styles and substitutes. In Proceedings of the 38th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 11, page 43-52, New York, NY, USA. 2015. Association for Computing Machinery. ISBN 97814 9781450336215. doi: 10.1 10.114522766466227777555
URL U //doi 0tt.0////0..111177666..60.20. 2767755
M. McPherson, Smith-Lovin and J. M. Cook. Birds of feather: Homophily in social networks.
Annual Review of Sociology, 27:415 444, 2001. ISSN 03600572, 15452115. URL http://
www. htt.sttr.rrggttableeeeeeeeeee
R. R. Nadakuditi and M. E. Newman. Graph spectra and the detectability of community structure in networks. Physical review letters, 108(18):18870) 2012.
A. Ng. M. Jordan, and Y. Weiss. On spectral clustering: Analysis and an algorithm, In T. Dietterich, S. Beeker, and Z. Ghahramani, editors, Advances in Neural Information Processing Systems, vol- ume 14. MIT Press, 2001. URL httpp:
ngs. nwwr cc/ppper fileis les/
K. Nguyen, N. M. Hieu, V. D. Nguyen, N. Ho, S. Osher, and T. M. Nguyen. Revisiting over- smoothing and over-squashing using ollivier-ricci curvature. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and J. Scarlett, editors, Proceedings of the 40th International Con- ference on Machine Learning, volume 202 of Proceedings of Machine Learning Research, pages 25979. PMLR, 7 2023. URL
wtl.ggs..r.....s... pt...preee//222//
nquyen23c. html
L. Pan, C. Shi, and I. Dokmanić. Neural link prediction with walk pooling, In International Confer- ence on Learning Representations, 2022. URL httpppps///peeeeee......eeeee/ee hwtp://wwwwwi.t.eeeeeeeeeeeeeeee ftt.rrummmtooo CCu6RcUMwKO.
D. Paul. Asymptotics of sample eigenstructure for large dimensional spiked covariance model. Statistica Sinica, pages 1617-1642, 2007.
H. Pei, B. Wei, K. C.-C. Chang, Y. Lei, and B. Yang. Geom-gen: Geometric graph convolutional networks. In International Conference on Learning Representations, 2020. URL https:// openreview n forum? deddsellleeeee lew.rruumiidssleaagrrrre
O. Platonov, D. Kuznedelev, M. Diskin, Babenko, and L. Prokhorenkova. critical look at the evaluation of GNNs under heterophily: Are really making progress? In The Eleventh International Conference on Learning Representations, 2023. huttpp:://ppereeysss
C. Qian, A. Manolache, K. Ahmed, Z. Zeng. den Broeck, M. Niepert, and Morris. Prob- abilistically rewired message-passing neural networks. In The Twelfth International Confer- ence on Learning Representations, 2024. URL
net/ / forum?rrmnmo ?id=
T 35Wcx7gVV
L. Rampasek, M. Galkin, V. P. Dwivedi, T. Luu, G. Wolf, and D. Beaini. Recipe for general, powerful, scalable graph transformer. In A. H. Oh, A. Agarwal, D. Belgrave, and K. Cho, editors, Advances Neural Information Processing Systems, 2022. URL hntpps://openeeview
ftt::/ormmmfdc MMaNE 6oxXM
Y. Rong, W. Huang, T. Xu, and Huang. Dropedge: Towards deep graph convolutional networks on node classification. In International Conference on Learning Representations, 2020. URL
net/ For.mm?dd--Hxxllccceee
B. Rozemberczki, C. Allen, and R. Sarkar. Multi-Scale attributed node embedding. Journal of Complex Networks, 9())cnab014, 05 2021. ISSN 2051-1329. doi: 10. 00.109//comnet/cnab00 4.
URL http:://.o...ooo0...0.0ooo////ap wwt./t/ cnabell
P. Sen, G. Namata, M. Bilgic, L. Getoor, B. Galligher, and T. Eliassi-Rad. Collective classification in network data. A/ Magazine, 29(3),33, 9 2008. doi: 10. 222.6699aaimag.2223322 URL https:
magaz ne/ //ojs. aas ot
15

---

Published as a conference paper at ICLR 2025
X. Shen, P. Lio, L. Yang, R. Yuan, Y. Zhang, and C. Peng. Graph rewiring and preprocessing for graph neural networks based on effective resistance. IEEE Transactions on Knowledge and Data Engineering, pages 1-14, 2024. doi: 10. 10.1109/TKDDEE202433976659
C. Shi, L. Pan, H. Hu, and I. Dokmanić. Homophily modulates double descent generalization in graph convolution networks. Proceedings of the National Academy of Sciences, 121(8): c2309504121, 2024. doi: 00.1073/pnas.2309004444 URL htthhtts::/
httptttps://wwppeptt... hwtp:///wwwww..mmmmmm..m. pnas arg/doi/
abs/10 10..0..173/paa. / 205.//0022.22295112111
J. Shi and J. Malik. Normalized cuts and image segmentation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2888))888-990 2000. doi: 11100934.866688
H. Shirzad, A. Velingker, B. Venkatachalam, D. Sutherland, and A. K. Sinop. Exphormer: Sparse transformers for graphs. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, and Machine Learning, vol-
J. Scarlett, editors, Proceedings of the 40th International Conference ume 202 of Proceedings of Machine Learning Research, pages 31613-31632. PMLR, 07 2023. URL wttpps://ppptt http::///occeeeeeeeeemmm mlr wrw.pprssspee.eee
v http:///////////22222aaaa html
J. Tang. Sun, C. Wang, and Z. Yang. Social influence analysis in large-scale networks. In Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD '09, page 807-816, New York, NY, USA, 2009. Association for Com- puting Machinery. ISBN 9781605584959,
doi: 10.1145/1557019.555110..
URL https:
7/ oaa..org/100 1111/11550019.155722
Topping, D. Giovanni, P. Chamberlain, X. Dong, and M. M. Bronstein. Understanding over- squashing and bottlenecks on graphs via curvature. In International Conference on Learning Representations, 2022. URL httptpsss//pppeeeeeeeeeee
net/ (oruummm==UmmRRG222
J. Wang, J. Guo, Y. Sun, J. Gao, S. Wang. Y. Yang. and B. Yin. DGNN: Decoupled Graph Neural Networks with Structural Consistency between Attribute and Graph Embedding Representations, 2024.
X. Wu, Z. Chen, W. W. Wang, and A. Jadbabaie. non-asymptotic analysis of oversmoothing in graph neural networks. In The Eleventh International Conference on Learning Representations, 2023. /RRLttt://///eeeeveee netp:/ewwweeeeeeeeeeeeeeeeeeeeee
K. Xu, W. Hu, J. Leskovec, and S. Jegelka. How powerful are graph neural networks? In Interna- tional Conference on Learning Representations, 2019. URL
net/ http:/aaa...rrr/eeeeeee.p///aaaa
forum?1d=ryGs6iA550
H. Yang, K. Ma, and J. Cheng, Rethinking graph regularization for graph neural networks. Pro- ceedings of the AAAI Conference on Artificial Intelligence, 3565)4553-4581,, 05 2021. doi: 1609/aaai.v355 13355.116886. URL view/16586
M. Zhang and Y. Chen. Link prediction based on graph neural networks. In S. Ben- gio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018. URL ht
neuripss....ruus..orr...r...... httpeeecpppppppeeeeeeeeeeeeeeeee files/paper/2018 FLL1://E00dcc3337889333322232322
J. Zhou, G. Cui, S. Hu, Z. Zhang, C. Yang, Z. Liu, L. Wang, C. Li, and M. Sun. Graph neural networks: review of methods and applications. Al Open, 11, 2020. ISSN 2666-6510. doi: https://dii.rr/// 101 w/j.a//............. www.app...22........ 2021..0..0..11..
Zhu, Y. Yan, L. Zhao, M. Heimann, L. Akoglu, and D. Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. In H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin, editors, Advances in Neural In- formation Processing Systems. volume 33. pages 7793-7804. Curran Associates, Inc., 2020. URL https:
http:p/prrrrllleepppp///2/222/ file/ flc.5aacc2a777770002228888288223
16

---

Published as a conference paper at ICLR 2025
Y. Zhu, W. Xu, J. Zhang, Y. Du, J. Zhang. Q. Liu, C. Yang, and S. Wu. A survey graph structure learning: Progress and opportunities, 2022.
Y. Zhu, R. Amor, Y. Chen, Z. Deng, L. Feng, and M. Witbrock. Robust node classification on graph data with graph and label noise. Proceedings of the AAAI Conference Artificial Intelligence, 2024.
17

---

Published as a conference paper at ICLR 2025
A
APPENDIX
A.1 THE JDR ALGORITHM
Algorithm Joint Denoising and Rewiring
1: procedure REWIRE(X, A)
For DENOISE just exchange and A
2:
X UEWT
3: A VAVI
4: for in range (LA) do
Loop over LA eigenvectors in A
5: Va < V|:.i]
6: for j in range LA)
do
Loop over LA eigenvectors in X
7:
uh < Ul []
8:
0 Ug Vol
Find angle between eigenvectors
9:
if 0 mmax then
i m
11:
max t Uh
end if
13:
end for
V 7 + (1 nA)v, + (asign(0maa) y
Interpolation between eigenvectors
15: end for
16:
A + VAVT
17: end procedure
18: X,A+ + A
19: for in range do
Main loop
X' < DENOISE( X, A)
20:
21:
A' + REWIRE A)
22: X, - A'
end for
24: X UPDATE X(X,X X)
Sparsify and binarize if needed
25: Á UPDATE (IPDATELA(A,AA
A.1.1 LOW-DIMENSIONAL GRAPHS AND RELATION TO RESONANCE
low-dimensional coordinates, finally mention that al- though algorithm is motivated by the cSBM, it could have cquivalently been motivated by ubiquitous low- dimensional graphs. In such graphs, node labels lated to the which are in turn given by the eigenvectors of the graph Laplacian; this illustrated in Figure 5 If, for example, the labels are given by the sign of the first non-constant eigenfunction (the slowest-changing normal mode), our notion of alignment with L = clearly re- mains meaningful.
Figure 5: Visualization of the first six eigenmodes of L of the x grid graph. where driving system with a frequency corresponding to an cigenvalue of the Laplacian yields diverging response. Importantly, the shape the response then an eigenfunction. In broad sense, resonance signifies alignment with Laplacian eigenfunc- tions, which are the natural modes. For graphs, this is closely related to alignment with eigenvectors of the adjacency matrix (it is equivalent for d-regular graphs). As Figure 2b shows, maximizing alignment between feature and graph spectra indeed leads to the largest response of the graph to the features.
This also further motivates our terminology of resonance. In a purist sense, resonance dynamical phenomenon
18

---

Published as a conference paper at ICLR 2025
A.1.2 ROTATIONAL INVARIANCE OF ALIGNMENT
We show that the alignment measure is invariant rotations of the subspaces for non-unique cigenvalues. Let A E R be the adjacency matrix and X E NxF the feature matrix. Let the eigendecomposstion of A be
A= AU-T + XOUUUP
where p - N. U, E Nx with being the multiplicity of the eigenvalue A, Ei N, UTU I, and U, 0 for i j. Let similarly the SVD of X be
X x= + ................................ Vvy,""
where Vi E RNC, W; E FR E, = F. with analogous orthogonality conditions. As- sume both (A:) and (a:) are sorted from largest to smallest. Assume also for simplicity that = Σ - by the columns of the block matrix U2 = [U1 ... ...Upp)) Jpr Of course it is also spanned by the columns of Ü, = =I Qp where invertible matrices Q; E RRxx*e reflect the fact that the eigen- solver may return any of the infinitely many (when s; 1) orthogonal bases for the subspaces spanned by the columns of U.. The Q: are orthogonal since U,Q; are orthogonal. Similarly the leading T-dimensional subspace of the features is spanned by the columns of Vy [V1 ..... Vg']] but also of V, = [VG R1 Vq R for any orthogonal (Rt). Now
Ei= & so that the leading L-dimensional subspace of the graph is spanned
| Velbpp ||blockdiag(Pf... ....,, 02) UEV2 blockdiag(R1, (R1, Ryy Mbsp
[|UVVlllg
for any choice of Qs and Rs since both block diagonal matrices are orthogonal and the spectral norm is unitarily-invariant.
A.1.3 COMPUTATIONAL COMPLEXITY
The complexity of JDR results mainly from the SVD and eigendecomposition, which is of order O(FN minnmin(F) N)) for SVD and O(N3) for the eigendecompositiin (F N). Since we only need the leading eigenvectors this reduces to (F) .. If the matrix is additionally sparse as is often the case for real-world graphs with binary node features this reduces further to ((nzz()) where nn)(A) is the number of non-zer elements in A. Since usually neither the average degree d nor k scaled by N, the complexity actually scales with O(N).
A.1.4 RUNTIME COMPARISON
In addition to computational complexity, report measurements of running time of the different algorithms. We run JDR and baseline methods on the real-world datasets, using GCN as downstream model. All algorithms We emphasize that we did not explicitly optimize the timing code and we kept the outputs and logging turned on. But this influences all methods in the same way so the relative comparisons meaningful. The results in do not show a clear "winner". The ambiguity is especially visible on the large heterophilic graphs, where JDR is slower than DIGL., but significantly faster than FoSR on two datasets. On the Twitch-gamers dataset, on the other hand, it is faster than DIGL but not as fast as FOSR. The main reason for this is that different hy hyperparameters choices the rewiring methods lead to dramatically different run times (even when applying the same method on the same dataset). For example on Computers, JDR very fast since it only requires denoising iterations, compared to 15 on Citeseer. The same holds true for FoSR which only require 5 iterations on Twitch- Twitch-gamers, but 700 on Questions. So one wants to optimize for speed, one should constrain the hyperparameters of the methods that significantly impact execution speed. Of course, there is trade-off between any such constraint and accuracy, as our experiments on the denoising iterations of JDR in Figure 16 (b) and Figure 17 (b) in Appendix A.6
Nvidia A100 with 80GB and we time their Python processes.
A.2 CONTEXTUAL STOCHASTIC BLOCK MODELS
SBMs and GMMs are landmark theoretical models for studying clustering, classification problems and developing algorithmic tools. The cSBM (Deshpande al., 2018), combination of the two,
19

---

Published as a conference paper at ICLR 2025
Table 5: Timing experiments in seconds for different rewiring methods using GCN downstream GNN. Smaller is better. We record the time of the preprocessing and training and evaluating the GNN on 100 random splits. The results do show clear winner; JDR generally requires
comparable or less time compared to baselines. For more discussion see A.1.4
Dataset
Base
DIGL
FoSR
BORF
JDR
Cora
182
228
187
201
246
Citeseer
258
360
291
290
433
PubMed
291
692
416
897
858
Computers
274
444
516
718
465
Photo
213
299
220
801
330
Chameleon
372
239
396
483
545
Squirrel
1263
302
1282
1659
Actor
166
286
171
225
319
Texas
163
200
169
174
203
Cornell
167
202
164
240
208
Questions
93
804
11053
3707
Penn94
164
232
3198
1779
Twitch-gamers
1579
6729
1618
5165
has become key model for studying node classification problems on graphs, inspiring numerous designs of GNNs like GPRGNN (Chien et al.) (2021). GIANT (Chien al. (2022) or ASGC (Chan-) puriya and Musco 2022). Many theoretical studies of node-level GNN problems are based on the cSBM, e.g. on double descent (Shi et al., 2024). neural collapse (Kothapalli al.] (023). OOD generalization (Baranwal et al. (021), or oversmoothing (Wu et al. (023). Beyond being a standard synthetic benchmark, the cSBM is also used to to verify hypotheses about GNNs (Ma et al. 2022 Luan et al. 2023).
As for any model, the cSBM also comes with limitations. One possible limitation our work is that cSBM assumes that the features linear in GMM, which makes linear classifier optimal. If the class boundaries are highly nonlinear, this is no longer true, and the spectrum of X may need to be "linearized", c.g. via Laplacian eigenmaps diffusion maps. Still, the results real-world data show that the cSBM model is already highly transferable, suggesting that the high- nigh-dimensional features in real-world graph datasets often quite linear.
A.3 PROOF OF PROPOSITION
Notation. We order the eigenvalues and singular values from largest smallest and denote the eigenvector associated with the eigenvalue Xy by v, (A"). For the leading eigenvalue and eigenvec- tors of A we write A dA and V1 (At) VA. We use analogous notation for the singular values and corresponding singular vectors of X. For simplicity and without loss of generality we assume that the angles between these vectors are accute, i.e., (M ux) (ÿ: v.) (ūj ux) ) 2 0.
Proof. When À > 1, based on the Baik-Ben Arous-Péches (BBP) transition (Baik et al. 2005 2007), the leading eigenvalue of A lies outside the spectral bulk,
Paul
AA= A O
and the fluctuation of the leading eigenvector satisfies
d Haar (S (S No-3
aA = A
(5)
g= where Haar(S is the uniform distribution on the sphere orthogonal to 3. 3ー
{v: ( R nf 0, ||||| 1}. and the convergence is in distribution N Similarly,
20

---

Published as a conference paper at ICLR 2025
for the rectangular matrix X we have Senaych-Georgee and Nadakuditi 2012).
( (1++ + Op
1
ox
1
VN
and the fluctuation of the leading singular vector satisfies
ux V 1
re (1 + 7 +
=1 ( - ạ/
d
Haar (S-- 2).
qx ==
To denoise A we adjust the leading eigenvector towards the direction of ux
Ú = (1 - 7A) VA + 7A4X
where 7/ 0 is small constant. The corresponding perturbation in the matrix reads
A - \u - vAV
=AAZA (V + uxx3) + 0 (1/2)
The first-order perturbation of the leading eigenvector yields
(A (N^u + = Vs 0y + (
1i (A( (A() XANA
-1
j#1
Since v)(A") 0A = 0 for j > 1, we have
(vI(A ) - U1 (A'),
J'O,
Us (A (A T 01ia)
AATA Σ
AA ~
if1
(i7 0y (A)))
D" og (A")), (A9)* qx + + (11))
AANACI
+ AATAN2
(6)
da >3
da X3
##1
#
where
v x(++)) m(m+>) and 02 = ((P-)) From the BBP transition we know that when
70-#]
we have (ý, vA)²
= 1 -/4 + (1). Consequently, it follows that Σjø1 (5 (A'))
x² + (1). Since the edge of the bulk of spiked matrices still follows the Tracy-Widon Widom distribu- tion
Cenaych-Georger al. 2011 ie., d2 + Op (N-$) and AN 2 Op (N-$) 8)
have
X+2 Op (N (N < AA ~
1
1 < 1 + +0p (N-3) for 1> 1.
a. 1 (D" (v"v)(A)))
Therefore the first term in 6 can be bounded as E5Ø1
23 + when N + 0o. >
da Ax-A;
For the second term, we note that the vector qx is independent of 2 = Ejx1 ,"o,(A9)
λa- n (A9).
Each eigenvector vy(4 (A)) is uniformly distributed on s-y2 and (A))) [1)) is an orthogonal basis
of IR N (v: e E R-N oz U 0}. Therefore, for large N. 5" 0, (A is approximately inde- 0
pendent of each element in Uy (At). More precisely, the entries of are of the order of O VN (gx; 2) = Op (
and thus Ejj1
: (A")), Aa
Summarizing, we get
2(++ mett)
(A+1 1IA + O (1:2)
when N 0o.
A similar strategy be used to show that (iy (X ), 0.s >
(X),
21

---

Published as a conference paper at ICLR 2025
Table 6: Properties the real-world benchmark datasets. For directed graphs we transform the graph to undirected in all experiments. H()) indicates the homophily measure.
Dataset
Classes
Features
Nodes
Edges
Directed
H(())
Cora
7
1, 433
2, 708
5, 278
False
0.810
Citeseer
703
3,327
5,552
False
0.736
PubMed
500
19, 717
44,324
False
0.802
Computers
767
13, 752
245,860
False
0.777
Photo
745
7,650
119, 081
False
0.827
Chameleon
2,325
2, 2,7
31,371
True
0.231
Squirrel
2, 089
5, 201
198, 353
True
0.222
Actor
932
7,600
26, 659
True
0.219
Texas
1, 703
183
279
True
0.087
Cornell
1, 703
183
277
True
0.127
Roman-empire
18
300
22, 662
32, 927
False
0.047
Amazon-ratings
300
24,492
93, 050
False
0.380
Minesweeper
2
10, 100
39, 402
False
0.683
Tolokers
758
519, 000
False
0.595
Questions
2
301
48, 921
153, 540
False
0.840
Penn94
2
4,814
41, 554
1, 362, 229
False
0.470
Twitch-gamers
168, 114
6, 797,
False
0.545
A.4 DATASETS
Table 6 shows the properties of the real-world datasets used. We also provide the homophily mea- sure HG) proposed in Pei al. 20020). which we compute using the build-in function of Pytorch Geometric (Fey and Lenssen 2019). For the cSBM, following (Chien et al. (02I), we choose 2000 and thus have 7 cSBM X2 + /²² 7 > (Deshpande et al. 2018), we use a margin such that X2 + 1²2/7 + e. We choose the same 3.25 as Chien et al. (202T) in all our experiments to be above the detection threshold and
N 5000,
2.5. Since the threshold to recover communities in
to obtain sparse graph to close to the propertics of real-world graphs. From the recovery threshold,
parameterize the resulting of ellipse with À 2 and μ 2 0 using & = (oattan(Ay////a Table 7 shows the parameters μ and x and the homophily measure for the different values of db
A.5 ADDITIONAL. RESULTS
We provide a number of additional experiments which did not fit in the main text. These include more experiments on additional heterophilic datasets from Platonov al. (2023), results for the homophilic datasets in the dense splitting, more experiments with DIGL (Gasteiger et al., 2019). more alignment results and results for synthetic and real-world data using spectral clustering with and w/o JDR. The clustering experiments in particular allow an interpretation of how JDR works: Applying to a graph increases its "spectral clusterability".
A.5.1 ADDITIONAL HETEROPHILIC DATASETS
In order to get a more comprehensive picture of the performance of JDR, we also test JDR on all the datasets proposed there by Platonoov et al. (202)). Table & shows the results on these datasets using their original splits and comparing DIGL. FOSR, BORF and JDR. In general, the performance increases are relatively small for all methods, but overall JDR still performs best. It achieves sig- nificant performance increases on Tolokers and Questions. For Minesweeper none of the methods really able to improve performance. The reason for this is in the synthetic design of its graph and the features: The graph does not contain any information about the labels, as only connects neighboring cells (it is solely computational graph). The same is partially true for node features which indeed contain information about neighboring mines, but only for 50% of the nodes. This renders JDR unsuitable, which is also reflected in an interesting way in the experiments: We found
22

---

Published as a conference paper at ICLR 2025
Table Properties of the synthetic datasets generated from the cSBM with 3.25. H(()) indicates the homophily measure.
Φ
nr
X
H(G)
1.0
0.0
-206
0.039
-0.875
0.40
-2.02
0.049
-0.75
1.56
-1.9
0.076
-0.625
3.28
-1.71
0.119
-0.5
5.31
-146
0.170
-0.375
7.35
-1.15
0.241
-0.25
9.07
-0.99
0.325
0.125
10.22
0.40
0.408
0.0
10.63
0.0
0.496
0.125
10.22
0.40
0.583
0.25
9.07
0.79
0.671
0.375
7.35
1.15
0.751
0.5
5.31
1.46
0.837
0.625
3.28
1.71
0.879
0.75
1.56
1.90
0.925
0.875
0.40
2.02
0.955
1.0
0.0
2.06
0.963
Table 8: Comparison of DIGL, FOSR, BORF and JDR on real-world heterophilic datasets from
Platonov et (2023): Mean accuracy (%) and ROC AUC for imbalanced Minesweeper, Tolokers and Questions= 95% confidence interval. Best average accuracy in bold. OOM indicates an out-of- memory emror.
Method
Roman-empire
Amazon-ratings
Minesweeper
Tolokers
Questions
GCN
78.64+0042
16.19=0.58
90.08:0.31
81.61+0.59
75.31+0.81
GCN+DIGL
75.32:10.61
45.9210041
88.16.10.57
81. $1.62.10.59
73.3510064
GCN+FoSR
78.58:10.43
46.30-1044
90.0710.51
84.50-10.47
75.51
GCN+BORF
78,66:10.42
46.44=10.54
90.06:10.38
0OM
00M
GCN+JDR
78.86=00.48
46.47+0067
90.01 +0.32
84.73+0.45
77.52+00.3
GPRGNN
71.46++0.29
45.81=0.21
87.80+0.51
72.01+0065
65.30+
GPRGNN+DIGL
11.59
46.43.10.34
87.9610.50
73.08 13.09911.16
69.9810.49
GPRGNN+FOSR 11.44-0.30
45.94
87.83-10.58
72.7240.60
65.45-10.68
GPRGNN+BORF
71.46:10.26
45.79-0.33
87.8110.51
OOM
00M
GPRGNN+IDR
71.85+0.31
16.1940.24
87.91+0.49
75.54+0.73
73.60+0.86
that the choice of hyperparameters has hardly any influence on performance. But also the results of the other rewiring methods indicate that they cannot be applied here. The graph is standard grid- graph, which should not exhibit any interesting geometric properties and not contain any insights about the labels. Overall, this typical еттог case for any rewiring method. But it could also be discussed to what extent this dataset is interesting graph dataset for node classification at all, since the connectivity does not contain any information about the labels.
A.5.2 HOMOPHILIC DATASETS IN THE DENSE SPLITTING
Table 9 shows the results of DIGL, FOSR, BORF and JDR on real-world homophilic datasets in the dense splitting. The improvements of rewiring are smaller overall compared to the sparse splitting, but all four methods are able to improve in most cases. With GCN as the downstream model, DIGL now performs best. JDR can still achieve the best result two out of five data sets. When using GPRGNN as downstream model. JDR performs best on three out of five datasets. DIGL and FoSR still able achieve small performance improvements on one dataset. BORF, on the other hand, is not able to improve the performance in most cases. This suggests that more powerful GNN architecture benefits less from DIGL,, FoSR BORF, while
most datasets and both rank first place
23

---

Published as a conference paper at ICLR 2025
Table 9: Comparison of DIGL, BORF and JDR on real-world homophilic datasets using the dense splitting: Mean accuracy (%) + 95% confidence interval. Best average accuracy in bold.
Method
Cora
CiteSeer
PubMed
Computers
Photo
GCN
08.1410.22
79.02=0.25
86,1410.10
89.0310.12
94.07=0.10
GIN+
88.74+0.228
79.13-0.27
87.81+0.09
90.34+0.12
94.87+0010
FON+
88.09++0.28
79.23=0.25
06.14+0.10
88.98+0.12 12
94.04=0.09
GCN+BORF
88.1810.22 24
79.17=0.24
86.14=0.10
89.14::.111
94.00=0.10
GCN+JDR
88.76:10.28
80.25-10.27
86.20=10.10
88.93-10.13
94.20=00088
GPRGNN
88.57
79.4
89.16=+0115
88.95:10.18
94.49=0.11
GPRGNN+DIGL
88.49+0.24
79.62=0.29
88.89=0.16
90.15=0.14
94.27=0.10
GPRGNN+FOSR
08.37+0.25
79.75=0.31
89.28+0.17
88.85++0.19
94.50=0.10
GPRGNN+BORF
88.56
79.39=0.31
89.04+0.18
88.90+40.19
94.52-0.10
GPRGNN+JDR
89.33+0.225
81.00+0.28
89.24
87.35++0.32
94.78+0008
JDR can still improve it even further. The computer dataset an exception for both downstream GNNs, JDR is not really able to improve the performance at all, while DIGL can clearly improve it.
A.5.3 MLP WITH JDR
We design JDR with the aim to denoise the (possibly) complementary information in graph and features. This is based the claim that GNN is the method of choice when both the graph and the features contain valuable information, as can utilize both. The experiments on cSBM in the main text show the ability of JDR transfer information between the two. This becomes visible especially in the corner cases, were either the graph or the features do not contain any information this case the only way to improve by transferring label information from
about the labels. one source to the other. To investigate this further, we test an MLP with JDR and compare the results with only the MLP and the GNNs. Since JDR can transfer the information from the graph to the features, an MLP should be able to perform similar to the GNNs. Therefore, we tune the hyperparameters of JDR with the MLP downstream model on synthetic cSBM datasets and the real-world datasets from the main text.
The results on the cSBM data are shown in Figure They show that combining an MLP with JDR clearly outperforms GCN in the heterophilic regime and performs very similar to GPRGNN, If the GNNs are also combined with JDR, they generally again provide superior performance compared to MLP+JDR. In the weak graph regime they have huge performance advantage of about 20%, since JDR cannot improve the feature quality for the MLP in these cases. In the heterophilic regime, MLP+JDR is still comparable to GCN+JDR, which not the case for the homophilic regime. A similar behavior (without JDR) has been observed in the literature before, e.g. by Ma et al. (2022) and is related to the limited ability of GCN deal with heterophilic graphs. GPRGNN, however, does not show this limitation and provides superior performance across all datasets. Notably, all these findings do directly translate to the real-world datasets. The results on the real-world data can be found in Table TO in the homophilic case and in Table [1 for the heterophilic case. For the homophilic datasets, MLP+JDR shows clear performance increases but cannot beat any of the GNN or GNN+JDR baselines. On the heterophilic graph, the MLP already outperforms GCN on three out of five datasets and with JDR on all datasets. GCN+JDR regains superior performance on three of the five datasets, but only GPRGNN+JDR outperforms the MLP+JDR on all datasets. Overall, this supports the claim that a GNN like GPRGNN the method of choice when both the graph and the features contain valuable information.
24

---

Published as a conference paper at ICLR 2025
Accuracy
Accuracy
GPRENN
NHRGGN-JOOK
GCN
GCN+JDR
MUP+JUR
MLP+JDR
MLP
MLP
40
40
-1.0
-0.75
-0.5
-.25
0.0
0.25
0.5
0.75
1.0
-1.0
-0.75
-0.5
-0225
0.0
0.25
0.5
0.75
1.0
(a)
Figure 6: Comparison of MLP and the GNNs the cSBM datasets in the sparse splitting. Compar- isons of MLP and MLP+JDR with the GNNs @ and GNN+JDR (b). The error bars indicate the 95% confidence interval. The MLP outperforms the GNNs in the very weak graph regime. Combining with JDR clearly beats GCN (especially in the heterophilic regime) and performs very similar to GPRGNN. If the GNNs are combined with JDR, they generally again provide superior performance compared to MLP+JDR.
Table 10: Results of MLP and JDR on real-world homophilic dataset using the sparse splitting: Mean accuracy (%) + 95% confidence interval. Best average accuracy bold.
Method
Cora
CiteSeer
PubMed
Computers
Photo
MLP
50.79:10.73
50.29-1048
79.73:10.13
73.17:0.31
80.8810.33
MLP+JDR
62.66=0.61
61.55=0.32
80.86+0.12
80.65+0.24
88.34+0.45
GCN
77.26=+0.35
67.16=0.37
84.22+00.99
84.42+0.31
91.33++029
GCN+JDR
79.96=1.226
69.3511.22
84.7910.08
85.66-0..36
92.52-0.23
GPRGNN
79.65=10.3
67.50=0.35
84.3311010
84.06100.48
92.0110.41
GPRGNN+JDR
00.77+0.29
69.17+0.30
85.05+0.08
84.77+00.3
92.68+00.25
Table 11: Results ML.P and JDR on real-world heterophilic dataset using the dense splitting: Mean accuracy (%) + 95% confidence interval. Best average accuracy in bold.
Method
Chameleon
Squirrel
Actor
Texas
Comell
MLP
49.07-0.57
20.19
38.5410.30
91.16110.79
88.1940.74
MLP+JDR
70.48=0.46
59.18+00.1
39.50+0.26
91.16++0.77
88.47+0.77
GCN
67.65=0.42
57.94+0.31
34.00+0.31
75.62+1.12
64.68+1.25
GCN+JDR
69.76=0.50
61.76+0..9
40.47++031
85.12+00.4
84.51+1.06
GPRGNN
69.15=0.51
53.44+0.37
39.52+0.22
92.82+t0.67
87.7940.89
GPRGNN+JDR
71.00.1..50
60.6210.38
41.8910.24
93.85.10.54
89.45510.8
25

---

Published as a conference paper at ICLR 2025
90
90
Accurecy %
80
Accuracy %
80
60
AMP UP
60
AMP UP
GCN+IDR GDN+
GERGNN-JDR
GPRGNN+ D OPRENN
50
50
MLP
MLP
-1.0
-0.75
-0.5
-0.25
0.0
0.25
0.5
0.75
1.0
-1.0
-0.75
-0.5
-0.25
0.0
0.25
0.5
0.75
1.0
(a)
(b)
Figure 7: Comparison of DIGL Gasteiger et al. 2019 and JDR the cSBM datasets in the sparse splitting. Results for (a) GCN and bb) GPRGNN as downstream models. The error bars indicate the 95% confidence interval. As expected, DIGL is not really able to improve the performance of the GNNs the heterophilic regime. It achieves the greatest improvement in the weak-graph regime and for strongly homophilic graphs, especially using GCN as downstream model. Another interesting observation is that for GCN and & < 0.25 the curve of MLP corresponds exactly to the one of GCN+DIGL. The reason for this is that the hyperparameters found for DIGL ensure that the graph is ignored (a- 1.0), which means that the GCN then collapses to simple MLP. For the more powerfull GPRGNN, on the other hand, DIGI. is generally hardly able to improve performance, while JDR clearly increases the performance across all db.
A.5.4 COMBINING JDR AND DIGL
We compare method to DIGL (Gasteiger et al., 2019) in the main text. We the personalized PageRank (PPR) diffusion kernel and the same top-64 values sparsening method as in JDR in all experiments. Figure 7 shows the additional results for DIGL on the synthetic datasets from the cSBM Table [22 shows the results on the real-world homophilic datasets in the sparse splitting and 13 on the heterophilic datasets in the dense splitting. Here, in addition to the individual results for JDR and DIGL,, the results for combination of the two methods are also shown. For this purpose, the graph was first denoised with JDR and then diffused with DIGL. To do this, we fixed the hyperparameters of JDR and then tuned the parameter a of DIGL.. We think this is interesting as both methods enhance the graph in different ways and thus should be combinable. should also be possible for combination of JDR with BORF or FOSR, but so far we have not been able to get this to work.
principle, this
Homophilic datasets. For the homophilic datasets, both DIGL and JDR can improve the results when GCN is used as a downstream model. Still, DIGL is outperformed by JDR on four out the five datasets. The two methods better results. This gives empirical support for the assumption that the two methods use a distinct way of performing rewiring this case and a combination therefore can further increase accuracy. The picture is somewhat different for GPRGNN as a downstream model. The improvements for DIGL are significantly smaller here, whereas JDR shows clear improvements across all datasets. This suggests that more powerful GNN architecture benefits less from DIGL, while JDR can still improve it even further. A combination of the two methods does not lead an increase in performance here. Although the performance is still significantly better compared to no rewiring or just DIGI,, JDR alone usually performs better.
be combined three of the five data sets to achieve even
Heterophilic datasets. Since DIGL rewires the graph by adding edges between nodes with short diffusion distance, it is expected to perform poorly on the heterophilic datasets. The results using GCN show that this is only true for Chameleon and Squirrel, while for Actor, Texas and Cornell there are still considerable improvements. For the datasets Texas and Cornell, DIGL even achieve the best results. JDR, on the other hand, improves performance across datasets and GNNs. This is also in line with the finding on the cSBM in Figure 7a However, we can also see that DIGL can not really improve performance of GPRGNN. JDR, on the other hand, can still achieve an improvement
26

---

Published as a conference paper at ICLR 2025
Table 12: Comparison of DIGL and JDR real-world homophilic dataset using the sparse splitting: Mean accuracy (%) + 95% confidence interval. Best average accuracy in bold.
Method
Cora
CiteSeer
PubMed
Computers
Photo
GCN
07.26=0.335
67.16=0.37
84.22+0.09
84.42+-0331
91.33:+0.29
GCN+DIGL
79.27=10.26
68.03=00333
84.60:10009
86.00=1.244
92.00:1:.23
GCN+JDR
79.96=10.26
69.35-10.28
84.79:10.08
85. 85.66:0.330
92.52:1:.23
GCN+JDR+DIGL.
80.48:10.26
69.19=0.229
84.83+00.10
84.78:+00.1
92.69-10.22
GPRGNN
79.65=#0.33
67.50-0.35
$4.33+0.10
$1.06=0.415
92.01=0041
GPRGNN+DIGI.
79.77+0.30
67.50-0.35
84.72+-0.16 1.10
86.25+0.28
92.31+0.25
GPRGNN+JDR
80.77:0.29
69.17=0.30
85.05:10.08
84.77110.35
92.68.10.25
GPRGNN+JDR+DIGI
80.55=00.27
69.47+0.27
84.87=0.10
85.98+0.21
92.67+0.27
1.0
Alignment. (A.X) X)
0.8
0.6
JDR
DIGL
0.4
None
0.2
1.00
00.75
00.5
0.25
0.0
0.25
0.5
0.75
1.0
Figure 8: Alignment of the leading eigenspaces according for graphs from the cSBM with different ø. We compare JDR to DIGL and no rewiring.
across all datasets. A combination of DIGL and JDR is generally not particularly useful in this scenario, likely because DIGL has difficulties on the heterophilic datasets anyway.
Table 13: Comparison of DIGL and JDR on real-world heterophilic dataset using the dense splitting: Mean accuracy (%) + 95% confidence interval. Best average accuracy in bold.
Method
Chameleon
Squirrel
Actor
Texas
Comeel
GCN
67.65++0.42
57.94-0.31
34.00-00.31
1.162+11112
64.68+ 1.25
GCN+DIGL
58.04
39.64=0.34
39.57+0.29
91.05-+0.73
88.49+00.4
GCN+JDR
69. 7..000
61.76:10.39
40.47-1031
85. 85.1240.74
84.51
GCN+JDR+DIGL
66.06=+0.43
36.62=0.29
40.30=0.27
88.90=:0.73
88 88.06:t0.77
GPRGNN
69.15
53.44=0.37
39. 39.52::.22
92.82++0.6 6.67
87. 77.79:0.880 0.99
GPRGNN+DIGL
66.57=0.46
12.98=0.37
39.61=0.21
91.11+:0.72
88. 88.06+0.81
GPRGNN+JDR
71.00:0.50
60.6210.38
41.8910.24
93.85-10.54
89.45-10.84
GPRGNN-JDR+DICI
70.07+00.44
59.37=0035
41.57+0.20
91.52+0.70
87.77+1.81
A.5.5 ALIGNMENT
Here, we give a more detailed view on how much JDR actually increases alignment on cSBM and real-world datasets compared the baseline methods. For cSBM, we can see Figure that DIGL only increases alignment in the homophilic regime. In the heterophilic regime it clearly decreases alignment. We expect this because it promotes connections among nodes at short diffusion distance. Also the random teleport probability found these datasets is 1.0, which results in random uniformly connected graph. Similar to the results on the real-world datasets Cornell and Texas from the main text, we can see this in the classification performance in Figure 7 In the heterophilic regime, the performance of DIGL matches exactly the MLP, while the homophilic regime,
performance increases. With GPRGNN, DIGL is not really able to improve performance at all (except for = 0). In Figure we can see that JDR increases alignment across all settings and more strongly than the baseline methods the real-world graphs (except for Citeseer).
27

---

Published as a conference paper at ICLR 2025
1.0
1.0
Aligament
None To5R
None
Aligamenta
JDR
JDR
0.2
0.0
Coca
C.teseer
PubMedd
Computers
Photo
0.0
Chomelecn
Squirrel
Actor
Twees
Cocnoll
(a) Homophilic Datasets
(b) Heterophilic Datasets
Figure 9: Alignment of the leading eigenspaces of graphs from homophilic (a) and heterophilic (b) real-world datasets. We compare the original graph (None) to the output of DIGL,, BORF and JDR with the hyperparameters found on GCN. JDR increases the alignment in settings and achieves the maximum alignment among rewiring algorithms in all settings except on the Citeseer dataset.
DIGL also increases alignment on many homophilic graphs and on heteophilic Texas. We would like to note that when only rewiring a graph, increasing the alignment might not always be the best thing to do: If the graph is very good, it would be the features that should be made more aligned to the graph. But only JDR able to do this, as it also denoises the features as well. It is also interesting that DIGL decreases the alignment for Cora and PubMed, but still achieves a good performance. This indicates that DIGL this case improves the graph in different way than JDR. So here, should be possible combine both methods achieve even better performance. And indeed, A.3.4 shows that this is exactly the case for Cora, PubMed and Photo on GCN. FoSR and BORF do not visibly change the alignment, since their modifications to the graph are usually too small.
A.5.6 SPECTRAL CLUSTERING
In addition to the GNNs as downstream algorithm, we also experimente with spectral clustering (SC). Spectral clustering either works with existing graph, k-nearest neighbor graph is cre- ated from given hiig--dimensional node features. Then the h: largest eigenvectors of the graph are calculated (the first is usually omitted it is constant vector) and their entries are then used as coordinates for a k-means clustering the nodes into classes. We show that JDR using the hyperparameters found with GCN downstream model, improves the performance of spectral clustering algorithm acting directly on A or X. This indicates a close connection between GCNs and spectral clustering such that a good denoised graph for GCN also good graph for spectral clustering. Intuitively, since spectral clustering is related to the graph cut, this means that in this case the classes are connected with fewer edges, making them easier cluster based on the cut.
Table 14: Results real homophilic datasets using spectral clustering: Mean accuracy (%) and best result in bold. Here, all methods use the hyperparameters found using GCN as downstream algorithm.
Method
Cora
CiteSeer
Pubmed
Computers
Photo
SC(A)
33.83
24.16
58.94
37.35
30.58
SC(A))DIGL
29.54
22.18
59.65
61.55
25.41
SC(A
33.83
24.61
58.72
36.97
30.54
SC(A)+BORF
35.01
25.22
58.90
37.35
33.37
SC(A)+JDR
67.76
63.36
72.90
62.29
65.67
SC(X)
29.76
45.57
60.45
28.53
48.46
SC(X)+JRR
34.68
45.90
60.47
28.55
48.58
28

---

Published as a conference paper at ICLR 2025
100
Accuracy
Accuracy
AMP-D2
AMP BP
-
SCOD- -DD0+JJRR
40
-1.0
-0.75
-0.5
-.25
0.0
0.25
0.5
0.75
1.0
40
-1.0
-0.75
-0.5
-0225
0.0
0.25
0.5
0.75
1.0
(b)
Figure 10: Separate results for using spectral clustering rewriting only A (al and denoising only X (b) compared to full JDR. Note that for & E (0.5, 0. 62., 0.875) we had to use additional graphs generated using cSBM with average node degree of d 10 for spectral clustering of A to work in general and for ø = 0.875 also for JDR. The reason for this is that the graph is very sparse so it is necessarily connected such that there is no guarantee that spectral clustering works. However larger node degree does not improve the performance of spectral clustering in general, while it may for GNNs.
Table 15: Results on real heterophilic datasets using spectral clustering: Mean accuracy (%) and best result in bold. Here, all methods use the hyperparameters found using GCN as downstream algorithm.
Chameleon
Squirrel
Actor
Texas
Cornel
SC(A)
31.71
22.40
25.92
48.09
39.89
SC(A))DIGL
32.06
22.69
25.91
43.72
40.44
SC(A))FoSR
31.44
24.46
25.93
55.19
38,80
SC(A)+BORF
31.97
OOM
25.97
56.83
43.17
SC(A)+JDR
31.36
22.15
28.63
52.46
44.26
SC(X)
23.54
20.17
31.01
49.18
45.36
SC(X)+JRR 24.59
21.03
23.99
55.74
49.73
cSBM. Figure 10 displays the results of spectral clustering with and w/o JDR. Figure 10a indicates expected behavior that spectral clustering using performs particularly poorly in the weak graph regime, since in this case there is hardly any information about the labels in A. By using JDR, this limitation is completely removed and the performance close to AMP-BP BP across all ø. The rewired graph contains more information about the labels, which was previously only available in X. For spectral clustering of X in Figure TOb) the relation is exactly the other way around. In the strong heterophilic or homophilic regime the performance is poor since most information is contained in the graph structure. Using JDR this limitation is removed and the performance becomes closer to AMP-BP across all Φ. Although a slight denoising of X by A would be possible for +0.375, there is no performance advantage here and these settings now show the weakest performance across all Ø.
Real-world Datasets. For the real world datasets, we compare the spectral clustering of A using the different rewiring methods DIGL, FoSR BORF and JDR. For the spectral clustering of X we can only evaluate JDR. Again we use the hyperparameters found using GCN as downstream model. The results Table 14 on homophilic datasets show a significant benefit of using JDR across all datasets. FOSR, BORF and DIGL are also able to improve the performance in some settings but not very consistently. There are also performance improvements across all datasets for the spectral clustering of X with JDR, but these significantly smaller. This indicates that the rewiring of the graph has a significantly greater influence on performance here than the denoising of the features. It also gives indication of how JDR works real-world data: It increases "spectral
29

---

Published as a conference paper at ICLR 2025
100
Accuracy
Accuracy
AMP-BP
AMP.
GCR+JDR
GPRGNN --DR SPRGNN-JDRLL
(DRI)
GCN +DRXX
GPRGNN -DRCX
GCN
GPRGNN
40
40 -1.0
-1.0
-0.75
-0.5
-.25
0.0
0.25
0.5
0.75
1.0
-0.75
-0.5
-.25
0.0
0.25
0.5
0.75
1.0
Figure 11: Separate results for rewiring only A and denoising only X compared full JDR. Results for a GCN and (b) GPRGNN. The error bars indicate the 95% confidence interval.
0.5
0.4
ESNR
0.3
0.2
JDR
DIGL
11.0
00.75
-0.5
0.25
0.0
0.25 0.5 0.75 1.0
Figure 12: ESNR for graphs from the cSBM with different σ. We compare JDR to DIGL and no rewiring.
clusterability" of the graph. Table 15 shows the results for the heterophlic datasets. The results here are much more inconsistent. It is striking that DIGL improves Chameleon and Squirrel, while it has actually worsened performance for GCN. BORF Cornell by a large margin, although DIGL and JDR perform better with the GCN. FoSR improves the performance of Squirrel. For the results of JDR, it is worth looking them together with the spectral clustering of X. On Chameleon and Squirrel the performance decreases for A but clearly increases for X. On Texas and Cornell it improved in all cases, but BORF. On Actor, the performance for X has dropped, while JDR is also the only method that really improves the result for A. To summarize, the improvements for JDR can assigned to one of the two sources of information, either A or X, for each dataset.
improve the performance Texas and
not as strongly as for
A.5.7 EVALUATING GRAPH DENOISING VIA ESNR
As described in the main text, the Graph Propensity Score (GPS) algorithm (Dong and Kluger 2023), together with the edge signal-to-noise ratio (ESNR) metric introduced in the same paper, are related to our work. Similar to the GPS algorithm, which uses the ESNR to denoise the graph, JDR denoises the graph but also the features. These two strategies are different, but they are both based on the cSBM. The main drawback of GPS is that it does not consider the possibility to also denoise the features using the graph and it is further limited low-SNR graphs and to GCN as downstream model. We are interested in the the ESNR metric it quantifies the noise in the graph.
In Figure 12 Table and Table 17 we compare the achieved ESNR values JDR with the baselines and the original graphs. The results for cSBM in Figure 12 show that JDR is able to denoise the graph in all cases and DIGL in the strongly homophilic regime. However, comparing the ESNR curve the actual GCN performance in Figure / there is no clear connection apart from the general trend. This was claimed to more visible in the paper by Dong and Kluger (2023). especially for cSBM which it is based on. The results homophilic real-world datasets in Table 16 follow
30

---

Published as a conference paper at ICLR 2025
Table 16: ESNR results of the original and rewired homophilic real-world graphs using JDR and the baseline rewiring methods. Largest value in bold.
Method
Cora
CiteSeer
PubMed
Computers
Photo
None 0.2964
0.1976
0.2701
0.6502
0.7145
DIGL
0.6888
0.5989
0.5490
0.7368
0.7407
FoSR 0.2965
0.1988
0.2700
0.6500
0.7145
BORF 0.2958
0.1948
0.2700
0.6502
0.7144
JDR 0.6160
0.5754
0.5291
0.7069
0.7155
Table 17: ESNR results of the original and rewired heterophilic real-world graphs using JDR and the baseline rewiring methods. Largest value in bold.
Method
Chameleon
Squirrel
Actor
Texas
Cornell
None 0.5199
0.4680
0.0546
0.0585
0.0388
DIGL 0.5082
0.3884
0.0244
0.1442
0.1195
FoSR 0.5199
0.4679
0.0546
0.0620
0.0389
BORF 0.5199
0.0545
0.0593
0.0423
JDR
0.4473
0.2156
0.1703
0.2729
0.2828
this trend. Indeed both JDR and DIGL are able decrease the noise in the graph, but DIGL does so best on all five datasets, while the GCN results show a benefit of JDR over DIGL on four out of five datasets (see Table [ For the heterophilic real-world datasets the results are even more inconsistent. JDR is able decrease the graph noise three datasets, but two of them not being the ones where GCN performs best (see Table 3). Also on Chameleon on Squirrel, no method is able to improve the ESNR. We suspect that this behavior occurs due the role of features which is not captured by the ESNR. Checking the results the paper by Dong and Kluger (2023). there cases where the ESNR is not sensitive, e.g. the Chameleon dataset, which suggests that in such cases, denoising the features more beneficial than focusing only on the graph structure. In fact, this is in line with findings in the ablations in Figure [3 and Figure where the denoising of the features improves more than the denoising of the graph on the Chameleon dataset. Overall, the ESNR generally able quantify the denoising of the graphs in most cases, but a more direct connection to GCN performance requires further research.
Finally, there are significant differences between the GPS approach by Dong and Kluger (2023) and our work, most importantly in that we consider both graph and feature information. Moreover, JDR improves performance of GNNs on woal-world graph datasets where GPS does not provide any improvements (homophilic datasets). Ablations on these datasets (again Figure [33 and Figure [4] indicate that JDR still achieves the most improvement by denoising the graph rather than the features in way that does not seem to be captured by the ESNR. We think that this is because ESNR does not consider the SNR the features. dropout real-world data, the performance barely decreases for datasets like PubMed. The reason for this is that the features already contain a lot of information and making the graph noisier via edge dropout does not spoil this. This is also related the discussion of GNN vs. MLP (see A.5.3) where an MIP on PubMed already performs reasonably well (see e.g. Table 10
the experiments of Dong and Kluger (2023) with edge
A.6 ABLATIONS
We perform several ablations of our method to investigate what happens in different scenarios and what effects changes in parameters have. First, we present our ablations of the JDR method. We show separate results for denoising only the graph JDR(A) the features JDR(X) using the GNNs on the cSBM and real-world data. Also, we show several ablations of the hyperparameters of JDR. We therefore dataset Chamelcon. Ablations on the real-world datasets are performed for all hyperparameters of JDR and show its robustness change in these parameters.
dataset created from cSBM, the homophilic dataset Cora and the heterophilic
31

---

Published as a conference paper at ICLR 2025
Cora
Citeseer
PubMed
Computers
Photo
70
90
90
100
None
JDRX)
66
86
86
96
JDRAA)
80-
64
84
84
94
JDR
75-
62
82
82-
92-
Chameleon
Squirrel
Film
Texas
Cornell
80
70
50
90
90
75
65
45
85
Accuaracy
70
60
40
70-
60
50
30
70
60
Figure 13: Average accuracy of GCN on all real-world datasets tested for denoising only the features JDR(X), rewiring only the graph JDR(A) and joint denoising and rewiring JDR.
Cora
Citeseer
PubMed
Computers
Photo
50
90
90
100
88
88
98
JDRXX
JDR(A)
JDR
75
62
82
82-
70
60
80
80
90
Chameleon
Squirrel
Film
Texas
Cornell
100
Accuaraey
96
70
60
40
50
94
65
55-
35-
92-
Figure 14: Average accuracy of GPRGNN all real-world datasets tested for denoising only the features JDR(X), rewiring only the graph JDR(A) and joint denoising and rewiring JDR. It can be observed that for most datasets, the major improvement is achieved by JDR(A). Only for Squir- rel and Chameleon it is JDR(X). In most cases using JDR on both X and A achieves the best performance.
JDR. The main motivation for these ablations is show how much impact the denoising of A and respectively have on the results for a dataset and how big the additional benefit is to do this jointly. Therefore
look at the results if denoise only the graph JDR(A) or the features (X)(X). Doing this for the cSBM in Figure TT we can observe the expected behavior, which particularly pronounced for GCN in Figure Ia In the weak graph regime, the performance increase results purely from denoising A, so JDR(A) achieves the same performance as JDR. The same holds for JDR(X) in the strong homophilic regime and for 1.0. In the remaining intermediate regimes, we can often observe performance benefit of both JDR(A) and JDR(X), which becomes much stronger when we combine both. This benefit of combining both is particularly pronounced for e -0.375, where JDR(X) alone even reduces performance, while JDR clearly improves performance. In Tigure[TTb we can basically observe the same behavior, less strongly pronounced. Moreover, it happens several cases here, again especially in the intermediate regime, that the performance is reduced by JDR(X), but improved for the joint denoising.
Figure 13 and Figure 14 show the same investigation for the real-world datasets using GCN and GPRGNN. respectively. In most cases, the greater performance gain results from JDR(A) and the joint denoising performs best. Only for the datasets Chameleon for both GNNs and Squirrel for GPRGNN, the denoising of X has the greater influence. Also the case where the denoising of X reduces the performance, but joint denoising performs best, occurs here, e.g. for Citeseer
32

---

Published as a conference paper at ICLR 2025
Table 18: Comparison for JDR using hyperparameters tuned on different downstream models. The "*" indicates that the hyperparameters of JDR where tuned using the same GNN as downstream model, no symbol mean that the respective other GNN model was used. Results on real-world homophilic datasets using sparse splitting (2.5%/..54/95%) Mean accuracy (%) - 95% confidence interval. Best average accuracy bold.
Method
Cora
CiteSeer
PubMed
Computers
Photo
Gain
GCN
77.26110.35
67.16.0.37
84.22.0009
84.4210.31
91.33.10.29
GCN+JDR*
79.96=0026
69.35+0.28
84.79:00.08
85.66+0.36
92.52=0.28
1.59
GCN+JDR
78.85=+0.29
69.11+0028
84.20=00.99
85.61+0.21
92.25=0025
1.13
GPRGNN
79.65-10.33
67.50
84.33:10.10
84.06:10.48
92.01
GPRGNN+IDR
80.47:40.33
68.94
84.644:0.25
92.6440.21
0.86
GPRGNN+JDR*
80.77 +0.29
69.17
85.05=0.08
84.77=00.3
92.68=0.22
0.98
Cornell. Overall, this confirms that our method indeed performs joint denoising, especially when both graph and node contain relevant information both benefit from denoising.
Hyperparameters. In Table 18 we show how the downstream GNN performs JDR was tuned on different downstream GNN. We use GCN and GPRGNN for this. The results show that the hyperparameters of JDR are quite robust to different GNN downstream models as it achieves similar gains using the respective other hyperparameters. Another way to show the robustness of JDR is to perform ablations of the actual hyperparameters. To do this, we first look at data set generated from the cSBM and examine the influence of the number of denoising iterations K and the number of entries of the adjacency matrix to be retained Ag. Figure 15| show the results of this study. As expected increase both results in better performance but will also increase the computational complexity. Based on this, we choose A₁ = 64 for all experiments as a good trade-off between computational and memory cost and accuracy over different numbers of denoising iterations. We also investigate this effect together with the rest of the hyperparameters for the real-world datasets Cora in Figure I6]and Chamelcon in Figure 17 We again examine the number of denoising iterations K and the number of entries of the adjacency matrix to be retained Ag. Additionally, we study the interpolation ratios 1)x and 774 and the number of eigenvectors for the denoising Lx and LA. Both analyzed relative to the value found by random search and for both A and X at the same time. For the interpolation ratios fix and 1/4, we show the influence of using only a reduced number of digits of the best found value (0 corresponds no denoising) and for the number of eigenvectors Lx and La we test different offsets (0 corresponding to the best value found using random search). Overall, we con observe a strong robustness to changes in the hyperparameters. Only the number of denoising iterations K should not be too high for the heterophilic data set Chamelcon.
A.7 HYPERPARAMETERS
In this section we list all the hyperparameters used for the experiments to ensure the reproducibility of the results. They are also included in the code. all experiments we use the Adam optimizer and the standard early stopping after 200 epochs from (Chien et al. (021). Whenever we use GCN, it uses two layers, a hidden dimension of 64 and dropout with 0.5. Whenever we use GPRGNN, we use polynomial filter of order 10 (corresponding to 10 hops) and a hidden dimension of 64. For JDR, we always keep the 64 largest entries of the rewired adjacency matrix A per node. We justify this choice by the ablation in Figure 15
cSBM. For synthetic data from the cSBM, we generally follow the hyperparameters from (Chien al. 2021). GCN uses a learning rate of 0.01 and weight decay with X = 0.0005. GPRGNN also uses 0.0005 and both use ReLU non-linearity. On homophilic graphs (ó > 0), GPRGNN uses a learning rate of 0.01, a weight initialization a = 0.1 and dropout with 0.5. For heterophilic graphs, it uses learning rate of 0.05,
1.0 and dropout 0.7. The hyperparameters for JDR on the cSBM are shown in Table 22 We only tuned them using GCN as a downstream model, so for GPRGNN+JDR we use the same ones.
Real-world Datasets, For the real-world datasets, the remaining hyperparameters for GCN are displayed in Table 19 and for GPRGNN in Table 21 The hyperparameters for JDR be found
33

---

Published as a conference paper at ICLR 2025
Aceuracy in %
A=1
65
A
A,=
A2-
A A1-128
A =252
20
40
100
Denoise iterations
Figure 15: Average accuracy of GCN cSBM with 0.0 for different numbers of denoise iterations and different numbers of entries A to keep for each node in the rewired adjacency matrix. Error bars indicating the 95% confidence interval 100 runs.
82
80
80
80
80
78
78
78
78
GCN+JDR
GCN
74
25
50
75
100
74
10
20
30
74
6
10
12
14
16
30
20
10
30
Au
Denoise Iberations K
Digits in T3x
and Q4
Change in La and LA
(a)
(b)
(c)
(d)
Figure 16: Ablations of GCN+JDR on the homophilic dataset Cora compared to the result for GCN. The light shaded ares indicate the 95% confidence interval. Ablations on the number number of entries chosen per node for the adjacency Ak. the number of denoise iterations K, the number of interpolations digits for the values and the number of eigenvectors 4n used. All other parameters kept constant. In all cases we can see that JDR is quite robust changes in all of its hyperpa- rameters.
72
72
68
66
GCN+JDR
66
66
66
64
64
16
30
Change and
(b)
(d)
Figure 17: Ablations of GCN+JDR on the heterophilic dataset Chameleon compared to the result for
GCN. The light shaded ares indicate the 95% confidence interval. We perfrom the same ablations as for Cora. In all cases except the number of denoising iterations, we can see that JDR is quite robust changes in all of its hyperparameters.
34

---

Published as a conference paper at ICLR 2025
in Table 23 and Table 24 For the rewiring method BORF, list its hyperparameters in Table 25 and Table 26 For DIGL, we always use the PPR kernel and sparsify the result by keeping the top- 64 values for weighted adjacency matrix. The values for the random-telepont probabililty and number iterations for FoSR are listed in Table 2nd and Table
Table 19: Hyperparameters of GCN. All models use 2 layers, hidden dimension of 64 and dropout with 0.5. Different type of weight decay and early stopping from (Gasteiger et al. 2019) was used, if these provided better performance then using the standard setting in Chien al. (2021). The same holds for feature normalization, which was used by default in Chien et al. (2021 for GPRGNN.
Dataset
Lr
Normalize X
A layer
Early stopping
Cora
0.01
False
0.05
First
GPRGNN
Citeseer
0.01
True
0.0005
All
GPRGNN
PubMed
0.01
True
0.0005
All
GPRGNN
Computers
0.01
False
0.0005
All
GPRGNN
Photo
0.01
False
0.0005
AII
GPRGNN
Chameleon
0.05
True
0.0
AII
DIGL
Squirrel
0.05
True
0.0
AII
DIGL
Actor
0.01
False
0.0005
All
DIGL
Texas
0.05
True
0.0005
All
GPRGNN
Cornell
0.05
True
0.0005
All
GPRGNN
Table 20: Hyperparameters of GCN for the larger heterophilic datasets. All models use hidden dimension of 64, batch norm, no weight decay and the early stopping from Chien et (20TT)
Dataset
Lr
layers
Dropout
Residuals
Questions
0.005
0.2
True
Penn94
0.001
0.5
False
Twitch-gamers
0.01
0.5
False
Table 21: Hyperparameters of GPRGNN. All models 10 hops and hidden dimension of 64.
Dataset
Lr
Normalize X
A1
Dropout
Early stopping
Cora
0.01
True
0.1
0.0005
0.5
GPRGNN
Citeseer
0.01
True
0.1
0.0005
0.5
GPRGNN
PubMed
0.05
True
0.2
0.0005
0.5
GPRGNN
Computers
0.01
False
0.1
0.0005
0.5
GPRGNN
Photo
0.01
False
0.5
0.0
0.5
GPRGNN
Chameleon
0.05
False
1.0
0.0
0.7
DIGL
Squirrel
0.05
True
0.0
0.0
0.7
GPRGNN
Actor
0.01
True
0.9
0.0
0.5
GPRGNN
Texas
0.05
True
1.0
0.0005
0.5
GPRGNN
Cornell
0.05
True
0.9
0.0005
0.5
GPRGNN
Questions
0.005
False
1.0
0.0
0.2
GPRGNN
Penn94
0.01
False
0.1
0.0001
0.2
GPRGNN
Twitch-gamers
0.001
False
0.5
0.0001
0.2
GPRGNN
35

---

Published as a conference paper at ICLR 2025
Table 22: Hyperparameters for GCN on the cSBM the sparse splitting. For all homophilic datasets the eigenvalues are ordered by value and for all heterophilic datasets they are ordered by absolute value. In all setting we keep the 64 largest entries of the rewired adjacency matrix A per node. Interpolation ratios y are rounded to three digits from the best values found by the random search.
JDR
DIGL
K
LA
Lx
7A
T/X
7/X2
1.0
28
10
0.482
0.916
1.0
0.875
0.101
0.479
0.858
1.0
-0.75
40
6
9
0.042
0.498
0.846
1.0
-0.625
0.036
0.453
0.862
1.0
-0.5
50
9
10
0.189
0,412
0.991
1.0
0..75
48
10
0.879
0.973
0.773
1.0
-0.25
80
1.000
1.0
-0.125
80
1.000
1.0
0.0
80
1.000
0.95
0.125
76
0.650
1.0
0.25
33
0.951
0.5
0.375
18
10
10
0.856
0.023
0.228
0.05
0.5
18
10
0.415
0.263
0.880
0.05
0.625
22
8
7
0.264
0.340
0.807
0.05
0.75
15
0.056
0.474
0.778
0.05
0.875
16
10
0.035
0.228
0.981
0.05
1.0
80
1.000
1.000
0.05
Table 23: Hyperparameters of JDR for all real-world datasets the dense splitting. Following the findings from cSBM for all homophilic datasets the eigenvalues are ordered by value and for all heterophilic datasets they are ordered by absolute value. In all setting we keep the 64 largest entries of the rewired adjacency matrix Á per node. Interpolation ratios are rounded to three digits from the best values found by the random search.
GNN
GPRGNN
Dataset
LA
Lx
77A
7x1
7|X2
K
IA
Lxx
7A
TXx;
T1Xa
Cora
1853
38
0.066
0.173
0.071
10
772
76
0.027
0.434
0.005
Citeseer
1330
0.460
0.173
0.049
1390
1169
0.345
0.099
0.585
PubMed
0.316
0.004
0.187
1772
0.197
0.893
0.034
Computers
0.398
0.068
7
583
1533
0.468
0.062
0.127
Photo
467
1867
0.479
0.071
0.344
4
433
1719
0.413
0.115
0.231
Chameleon
41
1099
0.066
0.375
0.975
3
31
1331
0.063
0.486
0.755
Squirel
1941
0.404
0.011
0.022
2
53
1210
0.234
0.495
0.964
Actor
896
0.298
0.235
0.219
11
1171
791
0.476
0.028
0.251
Texas
21
183
0.514
0.028
0.836
109
36
0.182
0.004
0.214
Cornell
0.794
0.298
39
0.482
0.424
0.068
Questions
248
284
0.218
0.199
0.841
2
89
2
0.974
0.106
0.311
Penn94
20
60
71
0.445
0.005
0.902
5
172
1851
0.422
0.094
0.138
Twitch gamers
0.235
0.286
0.806
5
2
2
0.165
0.329
0.003
36

---

Published as a conference paper at ICLR 2025
Table 24: Hyperparameters of JDR for all the homophilic datasets in the sparse splitting. Following the findings from cSBM for all homophilic datasets the eigenvalues are ordered by value and for all heterophilic datasets they are ordered by absolute value. In all setting we keep the 64 largest entries of the rewired adjacency matrix A per node. Interpolation ratios rounded three digits from the best values found by the random search.
GNN
GPRGNN
Dataset
K
LA
Ixx
74
1|X1
TJX²
K
LA
1.X
![X1
TX22
Cora
10
1853
38
0.066
0.173
0.071
10
772
76
0.027
0.434
0.005
Citeseer
15
578
1330
0.460
0.173
0.049
4
1390
1169
0.345
0.099
0.585
PubMed
12
8
53
0.316
0.004
0.187
1772
919
0.197
0.893
0.034
Computers
3
718
975
0.398
0.021
0.068
583
1533
0.468
0.062
0.127
Photo
6
467
1867
0.479
0.071
0.344
433
1719
0.413
0.115
0.231
Table 25: Hyperparameters for BORF for all real-world datasets in the dense splitting. OOM indi- an out-of-memory error.
GNN
GPRGNN
Dataset
iterations
added
removed
# iterations
added
removed
Cora
30
10
10
40
Citeseer
3
30
40
10
50
PubMed
2
0
30
3
20
40
Computers
20
40
20
30
Photo
2
40
20
3
50
50
Chameleon
2
50
30
10
30
Squirrel
OOM
OOM
Actor
2
40
50
2
10
50
Texas
40
10
40
50
Cornell
1
20
50
20
50
Table 26: Hyperparameters for BORF for the homophilic real-world datasets in the sparse splitting.
GNN
GPRGNN
Dataset
# iterations
# added
# removed
# iterations
# added
# removed
Cora
10
40
2
30
50
Citeseer
3
50
40
1
20
50
PubMed
30
3
20
40
Computers
20
40
3
20
30
Photo
50
3
20
37

---

Published as a conference paper at ICLR 2025
Table 28: Values of the hyperparameter a of DIGL and the number of iterations (# iter) of FoSR for the homophilic real-world datasets in the sparse splitting.
a DIGL
a DIGL+JDR
#iter FoSR
Dataset
GCN
GPRGNN
GCN
GPRGNN
GCN
GPRGNN
Cora
0.10
0.30
0.10
0.30
5
75
Citeseer
0.30
0.45
0.20
0.45
500
600
PubMed
0.35
0.60
0.40
0.60
50
75
Computers
0.05
0.65
0.15
0.30
250
800
Photo 0.20
0.50
0.10
0.50
5
500
Table 27: Values of the hyperparameter of DIGL and the number of iterations (# iter) of FoSR for the real-world datasets the dense splitting.
a DIGL
DIGL+JDR
#iter FoSR
Dataset
GCN
GPRGNN
GCN
GPRGNN
GCN
GPRGNN
Cora
0.25
0.60
0.20
0.60
150
Citeseer
0.60
0.50
0.25
0.25
1000
1000
PubMed
0.60
0.50
0.60
0.65
10
5
Computers
0.05
0.60
0.10
0.65
500
600
Photo
0.30
0.70
0.20
0.75
25
250
Chameleon
0.15
0.50
0.55
0.40
10
Squirrel
0.05
0.15
0.10
0.20
5
10
Actor
1.00
0.60
0.20
0.05
10
150
Texas
1.00
0.00
0.20
0.20
50
75
Cornell
1.00
1.00
0.95
0.00
25
Questions
0.05
1.0
700
700
Penn94
0.2
0.1
200
150
gritch
0.15
0.25
5
100
A.8 HARDWARE SPECIHICATIONS
Experiments cSBM, Cora, Citeseer and Photo conducted internal cluster with Nvidia Tesla V100 GPUs with 32GB of VRAM. The experiments on the remaining datasets (PubMed, Computers, Chameleon, Squirrel, Actor, Cornell and Texas) GPUs with 40GB or 80GB of VRAM. The larger VRAM is only necessary for GNN+JDR on PubMed and the larger heterophilic datasets from Lim cause they have larger numbers of nodes in the graph (and we choose the top-64 edges per node after rewiring). Note that this could be reduced by sacrificing only a little bit of performance as shown in A.6 One experiment of training and testing on 100 random splits typically takes about min. For standard benchmark graphs, the longest experiments with GPRGNN+JDR and different early stopping condition take about 40 min. The experiments the large Twitch-gamers dataset take around 60 min (for 10 splits), but similar to DIGL they require a lot of standard memory (around 500GB) while performing the decompositions.
performed using Nvidia A A100
(202I): Platonov et al. (2023), be-
A.9 INSIGHTS FROM RANDOM MATRIX THEORY FOR ONE-LAYER GCNS
Following the derivation from Shi et al. 2024), we show empirically how denoising reduce the empirical risk for a lne-layer GCN without non-linearity. When the number of nodes N goes to infinity and the average node degree satisfies adjacency equivalence conjecture. This allows us to replace the binary adjacency in the cSBM with spiked non-symmetric Gaussian random matrix without changing the training and test loss in the
assumptions,
apply the Gaussian
38

---

Published as a conference paper at ICLR 2025
# 0.0
# #10
0.35
0.45
#.0
p²=
0.30
1 4.0
MSB
0.35
0.20
0.25
0.15
0.20
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
0.00
0.25
0.50
0.75
1.00
1.25
1.50 1.75
2.00
7/a
(a) 0
(b) A = 1.0
Figure 18: Experimental results on a non-symmetric gaussian cSBM with N = 1000 and
with denoising of A. We plot the MSE for different μ² and À 0.0 18a and À 1.0 18b Each data point is averaged over 10 independent trials and the standard deviation is indicated by the light shaded area.
limit. The equivalent adjacency reads
A yy
+ +
N
where with gnn has i..d. centered normal entries with variance 1/N. Similarly, build the features matrix as
X N yu
=
Compared to the standard cSBM formulation we rescale the variables VIT l and v u. Additionally, we define 1/7 F/N and for simplicity, we consider the case Itrasn = I. The mean squared error (MSE) loss reads
L(w) N |AX ull r N IW
(9)
where is the parameter for the ridge part, the weights of the GCN and ||le indicates the Frobenius norm. For + oo, the MSE concentrates, which means it is only a function μ. À and For denoising A do
Aden A 7AXX7
(10)
The idea is that although this leads to more noise terms, the signal strength of yy² is increased more. Instead of weighting of 2 yy" we now have ( + 17.4 NN yy"" The new MSE also concentrates on value determined by 77 So, numerically, as shown in Figure [8] for any μe |\| > 0 we can always find values of 1), such that the MSE decreased. For denoising X
X den X 7/ AX
(11)
and show in Figure 19 with the same argumentation for A that 1)x exists so that the MSE is reduced. Proof of both cases has yet to be provided and will be the subject of future work.
39

---

Published as a conference paper at ICLR 2025
0.5
1=
1.0
3=0
3=00
MSE
0.3
MSE
0.2
0.00
0.25
0.30
0.75
1.00
1.25
1.50
1.75
2.00
0.00
0.25
0.50
0.75
1.00
1.25
1.50
1.75
2.00
17x
(a) μl
(b) 1.0
Figure 19: Experimental results on a non-symmetric gaussian cSBM with N 1000 and =
with denoising of X. We plot the MSE for different À and μ 0.0 in 19a l 1.0 in 19b Fach data point is averaged over 10 independent trials and the standard deviation is indicated by the light shaded area.
40


Reviews:
[{"review_id": "f7GrjCuEuW", "reviewer": "Reviewer_FthW", "summary": "The paper presents Joint Denoising and Rewiring (JDR), a novel algorithm designed to simultaneously address noisy graph structures and node features, thereby enhancing node classification performance in graph neural networks (GNNs). The work proposed aims to address the issue of graph datasets that suffer from noise due to missing or spurious edges and misaligned node features. JDR counters this by iteratively refining both the graph structure and features to maximize the alignment between their leading eigenspaces, achieving what the authors call “spectral resonance,” which improves data representation for downstream GNN performance. The algorithm operates in three iterative steps: first, it decomposes the graph’s adjacency matrix and node feature matrix into eigen and singular vectors; then, it aligns the leading eigenvectors of the graph with the primary singular vectors of the feature matrix, creating a more cohesive representation; and finally, it synthesizes the updated graph for subsequent GNN tasks. The authors argue this iterative approach effectively enhances graph quality and feature clarity, especially in datasets exhibiting mixed homophily and heterophily, which are often challenging for GNNs. The proposed work provides extensive experiments show that JDR consistently outperforms existing rewiring methods on synthetic and real-world datasets, yielding better alignment and improved node classification accuracy. Additionally, JDR’s preprocessing method produces an enhanced graph that supports interpretability and reusability, unlike other methods that modify graphs solely during training. The paper highlights JDR’s scalability and versatility across different graph types, underscoring its potential in handling noisy real-world data and establishing it as a valuable advancement in preprocessing techniques for GNNs.", "questions": "could timing comparisons of the proposed methods, more explicitly and beyond just complexity comparison, be provided to observe computational benefits/limitations?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The primary novelty of JDR lies in its combined optimization of graph structure and node feature alignment, enhancing data quality by maximizing alignment between the spectral components of the graph and feature matrices. This unified approach addresses both structural and feature-level noise simultaneously, which is rare among existing methods that typically target these types of noise separately. A key concept introduced is “spectral resonance,” where optimal alignment between the graph’s leading eigenvectors and the feature matrix’s singular vectors is achieved, providing a measurable target for denoising and boosting node classification performance. To manage the challenging non-convex optimization, the paper presents an iterative heuristic based on alternating optimization, which simplifies alignment maximization and enables efficient processing of large, real-world graph datasets with multiple classes. Another advantage of JDR is that it outputs a modified graph in the preprocessing stage, enhancing interpretability and reusability for subsequent GNN applications—a contrast to end-to-end methods that alter the graph only during training. Lastly, JDR’s design allows it to adapt effectively to both homophilic and heterophilic graphs, expanding its applicability beyond previous methods, which often work best with specific types of graph structures, such as those with high homophily.\n\nThe paper is well-organized, systematically guiding the reader through the challenges, methodology, and outcomes of the proposed Joint Denoising and Rewiring (JDR) algorithm. It begins with an introduction that effectively frames the problem of noisy graph structures and features, establishing the need for an approach that addresses both in unison. The methodology section details the concept of spectral resonance and the iterative optimization heuristic that drives JDR, using clear mathematical definitions and visual aids to support understanding. Following this, a comprehensive experimental section validates the algorithm's effectiveness across synthetic and real-world datasets, offering detailed comparisons with state-of-the-art methods and highlighting the algorithm’s robustness across homophilic and heterophilic graph types. Finally, the paper provides an insightful discussion on related works, situating JDR within the broader landscape of graph preprocessing techniques, before concluding with a summary of contributions and potential directions for future research. Overall, the structure flows logically, with each section building on the previous one to reinforce the practical relevance and theoretical underpinnings of JDR.\n\nAddressing the limitations of the proposed approach is appreciated\n\nThe illustrations provided in the work, both in the body and abstract, are informative and well done as well as qualitatively informative.\n\n The use of the appendix is also well done in providing explicit discussion of the proposed algorithm \n\nThe paper has a robust experimental section with compelling results working in favor of the approaches proposed", "weaknesses": "JDR depends on the availability of informative node features for effective rewiring and denoising, which restricts its applicability to settings with substantial node feature information; this reliance could limit its effectiveness in networks that primarily encode structural data. The algorithm’s design is also tailored to node-level tasks, making it less suited for graph-level tasks like graph classification, where global structure matters more than node-specific features", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "FCFyoS1Uv0", "reviewer": "Reviewer_VArZ", "summary": "The paper proposes to  jointly consider graph rewiring and feature denoising to improve the performance of GNNs for downstream classification tasks.  The proposed method improves the performance of a numer of GNNs on a number of popular datasets in the experiments.", "questions": "My main concern with this work is that although the proposed method looks to be sound, there is really no theorectical ground on its effectiveness in general when applied to a wider range of datasets. Also, the datasets used are very small and I'm not sure how useful and how scalable the method is in practice. It would significantly strengthen the work if the authors can either theoretically show how much improvement can be obtained using their method or empirically demonstration the effectiveness on a wide range of datasets, not just on common datasets that we have already seen too many papers claiming their effectiveness over others. I believe the contributions of such work are rather limited.", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed method is general and can be applied to a wide range of GNNs for downstream classification tasks. \n\n2. The proposed method jointly considers graph rewiring and feature denoising.\n\n3. The proposed method improves the performance of a numer of GNNs on a number of popular datasets in the experiments.", "weaknesses": "1. The solution is somewhat incremental and its novelty is low, although it appears to be sound.\n\n2. There is no theoretical guarantee on the degree of improvement using JDR.\n\n3. The experiments were conducted on a small number of datasets that cannot be considered as an evidence that the proposed method is really effective.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "DJsVe9zbhO", "reviewer": "Reviewer_PNCZ", "summary": "This paper considers the graph rewiring problem and feature denoising problem to improve the graph node classification task.\nThis paper utilizes cSBM modeling to optimize both graph structures and graph features to make them have better alignment, then proposes the JDR method to effectively optimize the alignment function.", "questions": "- As the computation overhead of the proposed method seems large, can it be applied to large graphs, e.g. ogbn-products?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- This paper uses cSBMs as a key framework to build intuition about the graph rewiring and denoising problem, providing the theoretical foundation for the alignment target.\n- The empirical verification using synthetic data is clear.\n- The method is evaluated on both homophilic graphs and heterophilic graphs, showing its generalizability.", "weaknesses": "- The proposed method involves graph structure matrix and graph feature matrix decomposition, which can be computationally challenging on extremely large real-world graph data, limiting the practicability of the proposed method.\n- As the SVD decomposition can have time complexity of $O(N^3)$, it may be not accurate to say the proposed JDR has time complexity of $O(N)$", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "2AHjMSv0ka", "reviewer": "Reviewer_Pd13", "summary": "This work presents a structural rewiring algorithm, with consideration of structural alignment with node features, supported by theoretical investigation on cSBM model.", "questions": "1. In Figure 2, why do the two subgraphs compare w.r.t. amplitude and normalized amplitude, respectively?\n2. Regarding section 2.2, can you explain more about how the structure is revealed parametrically? In line 137, $|\\lambda|$ is considered the signal-to-noise ratio, when it can also be considered the degree of homophility?\n3. The remark below definition 1, ''the information about the labels is indeed contained in the leading vectors of V and U'', is unclear.Because usually the decomposition of a matrix gives a support space, the weights of each support, and the coefficient of reconstructing the matrix using the support, which leads to the insufficiency of the leading support vectors to be representative.\nThis should be relevant for W2.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1.The overall structure is well organized and easy to understand, especially the diagram demonstrations are very helpful.\n2.The problem formulation is clearly presented.\n3.Experiments are comprehensive and convincing.", "weaknesses": "1. The theoretical framework seems convincing to me, while how the real data sets fit the parametric model needs further investigation, otherwise the heuristic of denoising features might not be applicable.\n2. More explanation is needed on the insights of where the rationale of denoising comes from, e.g. lines 159-190.\n3. Since the eigendecomposition is applied on adjacency, the comparison of training and inference time costs between the vanilla GNN and with the add-on of the proposal is needed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "c3Au0fS4tE", "reviewer": "Reviewer_Fauu", "summary": "The work proposes a method (JDR) to jointly perform graph rewiring and feature denoising. The method is derived from cSBM to maximize alignment between the eigenspaces of features and the graph. The authors tested the performance of the methods in various datasets and showed the advantages of the proposed JDR method.", "questions": "See above.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The method is well inspired and can achieve better performance than several other graph rewiring methods.\n2. An impressive amount of experiments were implemented.", "weaknesses": "1. The paper should better discuss previous works on GNN versus MLP, and the connection between heterophily and graph noise. [1-4] investigated the phenomena that MLP sometimes perform better than GNN (especially GCN) for heterophilic graphs. In particular, [4] proposed a metric that well correlates with empirical GNN performance, and also discussed the connection between heterophily and graph noise. A better discussion (acknowledgement?) of [4] is needed due to its high relevance to this paper.\n\n2. The comparison between JDR and graph rewiring methods seems not perfectly fair as the authors also mention themselves. Moreover, if JDR indeed achieves optimal denoising, then the graph may no longer be needed in later training. This (JDR(X) + MLP) seems uncovered by the ablation settings. \n\n3. The authors should check if the rewired graph structures degenerate, which may be a natural consequence of combining matrix factorization scheme and thresholding. \n\n4. The hyperparameter tuning was not performed for the GNN backbone. This is questionable as the optimal backbone hyperparameter is anticipated to vary across different rewired graphs (and potentially different denoised features). This may matter because the performance gap between JDR and other methods seems small in most cases.\n\n5. Some paragraphs are unclear and not readable. In particular, it is unclear what “findings” in the sentence “The Gaussian adjacency equivalence conjecture (Shi et al., 2024) suggests a generalization of the findings to the true binary adjacency case.” is referring to. The whole section (as well as the proof) needs to be polished.\n\n[1] Ma, Yao, et al. \"Is Homophily a Necessity for Graph Neural Networks?.\" International Conference on Learning Representations.\n\n[2] Gomes, Diana, et al. \"When Are Graph Neural Networks Better Than Structure-Agnostic Methods?.\" I Can't Believe It's Not Better Workshop: Understanding Deep Learning Through Empirical Falsification. 2022.\n\n[3] Luan, Sitao, et al. \"Revisiting heterophily for graph neural networks.\" Advances in neural information processing systems35 (2022): 1362-1375.\n\n[4] Dong, Mingze, and Yuval Kluger. \"Towards understanding and reducing graph structural noise for GNNs.\" International Conference on Machine Learning. PMLR, 2023.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:

Decision: Accept (Oral)