Graph Convolutional Attention: A Spectral Perspective on Graph Denoising and Diffusion
Shervin Khalafi∗ University of Pennsylvania [email protected]
Igor Krawczuk∗ [email protected]
Charilaos Kanatsoulis Stanford University [email protected]
Sergio Rozada King Juan Carlos University [email protected]
Antonio G. Marques King Juan Carlos University [email protected]
arXiv:2607.06546v1 [cs.LG] 7 Jul 2026
Alejandro Ribeiro University of Pennsylvania [email protected]
Abstract Denoising graphs is a fundamental problem in graph learning and the core operation of graph diffusion models. Attention-based architectures like graph transformers have recently shown promise in denoising graphs. However, our principled understanding of attention-based graph denoising remains limited, making it unclear whether standard attention is the right mechanism for this task. Here we show that, under a denoising objective, linear attention is suboptimal and can only learn an average spectral denoising filter over the training distribution. This creates a fundamental limitation as graphs often vary spectrally across the distribution. To overcome this limitation, we introduce Spectral Attention, which directly utilizes the input graph spectrum and provably outperforms linear attention by a margin governed by the spectral diversity of the distribution. We then derive Graph Convolutional Attention (GCA), a practical and permutation-equivariant realization of this idea that implements spectral denoising through graph-filtered queries and keys. For stochastic block models, GCA provably matches the idealized Spectral Attention mechanism. We further show that the softmax operation, that follows the attention, provides additional denoising by approximately projecting noisy eigenvectors onto the clean eigenspace. Empirically, replacing linear attention with GCA consistently improves graph denoising and diffusion on synthetic and real datasets, with gains strongly correlated with spectral diversity. In DiGress, GCA matches standard graph-transformer performance without computing expensive structural features, and when combined with the recently proposed PEARL positional encodings, avoids explicit eigendecomposition computations resulting in faster inference without degrading quality. The code can be found here: github.com/shervinkhalafi/graph_conv_att
1
Introduction
Denoising is a fundamental problem in machine learning [29], both in its own right and as the central learning primitive behind denoising diffusion models [39, 40]. Graph denoising introduces a unique ∗ Equal contribution.
Preprint.
challenge: the object to be denoised is not merely a signal on a known domain, but the domain itself. In image and audio denoising, the underlying grid or temporal axis is fixed, so models can exploit geometry through convolutions [28]. In graphs, by contrast, the geometry and spectral frequency is corrupted and must itself be recovered. Classical approaches address graph denoising through regularized optimization [46, 38], but the parametric perspective has received comparatively little attention. Interest has grown recently, driven by graph diffusion models [14, 44], where the dominant approach is graph transformers that take the eigenvectors of the graph, and optionally additional structural features, as input. Yet a theoretical understanding of how such parametric models learn to denoise graphs remains limited. In this work, we aim to provide insight into the mechanisms underlying parametric graph denoising through theoretical analysis. We proceed in four steps. First, we (i) analyze linear attention, the outer product of linear query-key projections, as it underlies every attention-based graph denoiser. We show it learns an average of the spectral properties across the graph distribution, which is suboptimal when those spectra vary. To address this sub-optimality, we (ii) introduce and analyze the spectral attention, an abstract class in which the attention mechanism depends arbitrarily on the input eigenvalues. The loss with respect to spectral attention is strictly smaller than that of linear attention, and the gap depends on the concept of spectral diversity, i.e., how diverse the spectra are across the distribution. Spectral attention, however, is abstract and in general not permutation equivariant. To turn the insight into something usable, we (iii) introduce graph convolutional attention (GCA), in which the attention pattern is a pointwise function of the eigenvalues. This makes the mechanism permutation equivariant and expressible as a graph convolutional filter. For asymptotically large Stochastic Block Models (SBMs), we show that under suitable conditions GCA matches spectral attention and therefore strictly improves on linear attention. Finally, we (iv) analyze the nonlinearity, typically a softmax, that follows linear attention. We show that once the clean eigenvalues are known, e.g., recovered by GCA, the softmax denoises the eigenvectors by acting like an approximate projection onto the subspace spanned by the clean eigenvectors, which provably reduces noise. Experimentally, across real and synthetic datasets, a graph transformer using GCA in place of the standard query-key projections outperforms the standard graph transformer at denoising, and the perdataset improvement correlates strongly with a surrogate of the spectral diversity metric, validating the theory. For diffusion models, GCA improves training loss and, on many datasets, sample quality both qualitatively and under standard metrics. Finally, drop-in augmentation of DiGress with GCA + R-PEARL[16] is competitive with the standard DiGress without any hyperparameter tuning, slightly improving on some MMDs without its usual expensive to compute spectral features. We summarize our contributions as follows: C1 Theoretical analysis of attention-based denoising. We show linear attention only learns an average of spectral properties over the graph distribution, which is suboptimal when graphs have varying spectra. We introduce spectral attention, and show that its improvement over linear attention is captured by the spectral diversity of the graph distribution. C2 Graph Convolutional Attention (GCA). Motivated by the analysis, we propose GCA, where the attention pattern can be expressed as a graph convolutional filter, making it permutation equivariant. For asymptotically large SBMs, we show GCA matches the optimal loss of spectral attention, and thus strictly outperforms linear attention. C3 Role of the softmax. In the SBM setting, we show that softmax can further improve the denoising of graph by comparing it to a projection of the noisy eigenvectors onto the eigenbasis spanned by the clean eigenvectors. C4 Empirical validation. Across real and synthetic datasets, replacing standard query-key projections with GCA consistently improves denoising, and the per-dataset gain correlates with a surrogate of our spectral diversity metric, directly validating the theory. The gains transfer to discrete diffusion: GCA yields lower training loss and better samples. C5 Implications for modern diffusion models. Plugging GCA into DiGress we observe that we can match DiGress performance with hand-crafted features while avoiding their cost. Combined with R-PEARL, it can even sidestep eigenvector computation entirely leading to a reduction in training and inference time on larger graphs. 2
1.1
Literature review
Graph denoising. Existing graph denoising methods can be broadly divided into optimizationbased and learned approaches. The former recover a clean graph by solving an inverse problem regularized with structural priors such as edge-error models [46, 15], spectral consistency [38, 34, 42], or low-rank, sparse, and smooth graph structure [51, 45, 24]. The latter replace instance-wise optimization with a parametric denoiser, either as a preprocessing or jointly trained module for downstream GNNs [7, 4, 49], or as the core component of diffusion and flow-based generative models that iteratively remove graph corruption [19, 14, 44]. Overall, prior work spans from hand-crafted regularization to fully learned graph restoration, but most methods are not designed to explicitly exploit spectral structure within the denoising mechanism itself. Spectral attention. A parallel line of work incorporates graph spectral information into Transformer architectures. Early methods use Laplacian eigenvectors or eigenvalues as spectral features or positional encodings for attention-based models [11, 18, 6, 31], while later approaches address eigenvector ambiguities through invariant spectral encoders such as SignNet and BasisNet [21]. More recent models integrate spectral structure directly into the attention mechanism or the learned operator. GIST reweights attention using inner products of random filtered spectral features [35], whereas Specformer, PolyFormer, and Eigenformer use Transformer blocks to parametrize spectral filters using attention [2, 25, 10]. These works show that spectral information can be embedded into attention in several ways, but they are mainly aimed at representation learning and prediction rather than graph denoising.
2
Denoising Graphs with a Linear Model
Problem Setup. We start with the graph denoising problem as it is fundamental to graph diffusion. In particular, the next two sections analyze how attention-based neural networks perform denoising from a spectral perspective. We first show that the linear part of the network can learn to denoise the eigenvalues of a noisy graph. Then, in Section 3, we show that the nonlinearities help remove noise from the eigenvectors. We consider unweighted, undirected graphs G sampled from a distribution over graphs which we denote DG . For a given graph G, we denote by A ∈ Rn×n the symmetric adjacency e = A + E, where E ∈ Rn×n is a symmetric noise matrix matrix. Denote the noisy adjacency A sampled from a noise distribution. We note that depending on the noising method this distribution could depend on the input graph for example when flipping edges in an unweighted graph, or it could be independent e.g., Gaussian noise. We write the eigendecomposition of the adjacency as e=U eΛ eU e ⊤. A = U ΛU ⊤ , and that of the noisy adjacency as A 2.1
Using Eigenvalue Information Improves Denoising.
Consider an arbitrary denoising function f (·) : Rn×n → Rn×n that takes the noisy adjacency as input and returns a prediction of the denoised graph. We define the following loss functional characterizing the denoising capability of f over different graphs and noise samples from the distribution: 2
e −A ℓ(f ) = EA, E f (A)
F
(1)
A common candidate for implementing the denoising map is attention [44, 32]. For a sequence of d-dimensional input tokens X ∈ Rn×d , standard attention computes ⊤ ⊤ gAtt (X) = softmax(XWQ WK X )XWV
(2)
where WQ ∈ Rd×dk , WK ∈ Rd×dk , and WV ∈ Rd×dv are learnable query, key, and value matrices, respectively. In graph denoising, attention-based estimators of the adjacency can be built as an outer product of representations [44]: ⊤ e⊤ ⊤ e⊤ ⊤ e = gAtt (U e )gAtt (U e )⊤ = softmax(U e W Q WK e WV WV⊤ U e ⊤ · softmax(U e W Q WK f (A) U )·U U ) . (3) e to recover a clean spectral representation of the underlying graph In this view, attention acts on U e WQ W ⊤ U e ⊤ can be A. We analyze this mechanism as a two-stage process. First, the score matrix U K
3
interpreted as a linear spectral estimator that seeks to recover a denoised graph with clean eigenvalues. e to approach the clean Second, the softmax operation further denoises the noisy eigenvectors U noiseless adjacency. To study the first step, in this section we restrict our focus to three classes of simplified graph-denoising maps: ⊤ 1. Linear Attention: We define W = WQ WK and consider the function class FLA : n o e W) = U eW U e ⊤ | W ∈ Rn×n FLA = f (A;
(4)
2. Spectral Attention: The broader class of functions FSA where the attention pattern can depend on the eigenvalues of the noisy input graph via any arbitrary function g(·): n o e g(·)) = U e g(Λ) e U e ⊤ | g(·) : Rn → Rn×n FSA = f (A; (5) 3. Graph Convolutional Attention: We consider the class of functions FGCA where the attention pattern is replaced by a function η(·) acting point-wise on the eigenvalues of the graph: n o e η(·)) = U e η(Λ) e U e ⊤ | η(·) : R → R , FGCA = f (A; (6) e denotes the pointwise application of η to the where, with a slight abuse of notation, η(Λ) e entries of the diagonal matrix Λ. Note that the linear attention model is in general not permutation equivariant, due to the nonuniqueness of the eigenvectors. Similarly, the spectral attention model is also in general not permutation equivariant since FLA ⊂ FSA . The graph convolutional attention model, however, is permutation ei )vi v T which is a permutation equivariant e h(·)) = Pn h(λ equivariant as it can be written as f (A; i i=1 aggregation of the eigenvectors each processed individually by the function h(·). Next, in Propositions 1, and 2 we characterize the minimum achievable loss for the linear and spectral attention classes respectively. The proofs can be found in Appendices C.3, and C.4. Proposition 1. The minimum loss achievable with linear attention, ℓ⋆LA := minf ∈FLA ℓ(f ), can be characterized as: ℓ⋆LA = tr (Cov(vec(B))) + c, (7) ⊤ e AU e . Furthermore, the minimizer is given by f (· ; W ⋆ ) where: where B := U W ⋆ = EA, E [B] (8) Proposition 2. The minimum loss achievable with spectral attention, ℓ⋆SA := minf ∈FSA ℓ(f ), can be characterized as: e +c ℓ⋆SA = tr Cov(vec(B) | Λ) (9) e ⊤ AU e . Furthermore, the minimizer is given by f (· ; g ⋆ ) where: where B := U h i e e = EA, E B Λ g ⋆ (Λ)
(10)
By the law of total variance, conditioning can only reduce variance, so ℓ⋆SA is going to be smaller or equal to ℓ⋆LA . We formalize this in Theorem 1, proven in Appendix C.5. Theorem 1. The improvement in the minimum achievable loss by the spectral attention class compared to the linear attention class is given by: 2 e − E[B] e ℓ⋆SA − ℓ⋆LA = SD(DG ) := E E[B | Λ] = tr(Cov(E[vec(B) | Λ])), (11) F
where we define SD(DG ) as the ’Spectral Diversity’ which depends on the graph data distribution and, implicitly, on the noise distribution. Remark 1. The Spectral Diversity SD(DG ) essentially quantifies how much information we gain about the clean graph by observing the noisy spectrum. For more intuition on this, if we assume the noise is sufficiently small such that the noisy eigenvectors are close to the clean ones, then from (11) e k ])) ≈ tr(Cov(E[Λ | Λ])) e which is akin to the variance of the we can write tr(Cov(E[vec(B) | Λ e On one extreme, if the graph distribution is degenerate, expected value of Λ having observed Λ. e = E[Λ], and its variance and therefore the i.e., its support is only a single graph, then E[Λ | Λ] e can also spectral diversity are 0. On the other hand, the more varied Λ is across graphs, E[Λ | Λ] vary significantly leading to a larger variance and spectral diversity. 4
2.2
From Spectral Attention to Graph Convolutional Attention
The Spectral Attention class is quite abstract as it includes any arbitrary function of the eigenvalues. Graph Convolutional Attention on the other hand, is practically realizable with graph convolutional filters. In this section we aim to bridge the gap between these two classes under certain settings. We begin by defining a graph convolutional filter bank acting on input graph features X ∈ Rn×d as: h(X) =
L−1 X
S l XH (l)
(12)
l=0
where S is the shift operator (e.g., Adjacency or Laplacian of the graph) and H (l) ∈ Rd×d are a set of learnable weights. In our case the input features are the eigenvectors of the graph, i.e., X = U , thus (12) simplifies to: ! L−1 L−1 X X h(U ) = U Λl U ⊤ U H (l) = U Λl H (l) (13) l=0
l=0
By replacing the linear projections in self-attention with graph convolutional filter banks as in (13) we get the following function of the adjacency:
f (A; H) = U
L−1 X
! (l) Λl HQ
l=0
L−1 X
!⊤ (l) Λl HK
U⊤
(14)
l=0
Eq. (14) is not permutation equivariant in its most general form. Equivariance is recovered when (l) (l) HK and HQ are constant diagonal matrices, so that Eq. (14) reduces to a product of graph filters. (l)
(l)
Accordingly, in the rest of the analysis we restrict HK and HQ to this setting. In our experiments, however, we primarily use the more general graph-filter-bank formulation. Lemma 1, proven in Appendix C.2, connects the graph convolutional filter to the GCA class defined in (6). P P ⊤ L−1 l (l) L−1 l (l) Lemma 1. A graph convolutional filter bank, i.e., gfilt (Λ) = Λ H Λ H , for Q K l=0 l=0 sufficiently large L, can approximate any function acting pointwise on the eigenvalues η(λ) : R → R, if η is continuous on any compact interval [a, b] ⊂ R. With the preceding discussions and Lemma 1 we have established a practical way to realize the functions in FGCA . Still in general there could be a gap between the minimum achievable loss of the graph convolutional attention model and the spectral attention model because the minimizer of the loss in FSA is not necessarily a pointwise function of the eigenvalues. In other words since FGCA ⊂ FSA , it follows that in general ℓ⋆SA ≤ ℓ⋆GCA . Thus, it is not obvious whether GCA also improves upon linear attention. In order to bridge this gap we show in this section that under certain conditions we have ℓ⋆GCA = ℓ⋆SA . Stochastic Block Model (SBM). Consider the general SBM of size n with k communities. A given graph sampled from this model can be written as: A = E [A] + (A − E [A]) | {z }
(15)
∆
where E [A] is a deterministic rank k matrix with block structure and the matrix ∆ := A − E [A] e = A + E which we can write as: encodes the randomness. Now consider our noisy observation A e = E [A] + ∆ + E A
(16)
Assumption 1. We assume the variance of ∆ is small compared to eigenvalues of E [A]. In this setting we can ignore ∆ and focus on recovering the low rank signal A ≈ E [A] from the noisy observation A + E. We further consider E to be a standard Wigner matrix scaled by σ. A Wigner matrix is a symmetric random matrix with independent zero-mean entries on and above the diagonal. This assumption is not overly restrictive in our setting, since it captures independent entrywise perturbations of a graph. Gaussian noise with independent entries is a Wigner perturbation. 5
Additionally, edge-flipping noise in the SBM setting, can be decomposed into a zero-mean Wignertype component plus a deterministic bias term (See C.8 for proof). Hence the edge flip setting is also reduced to low-rank deterministic matrix plus Wigner-type noise matrix. Theorem 2 (Outlier Shrinkage). Under the setting of Assumption 1, we have: h i e ⊤ AU e Λ e = ηout (Λ) e lim E U n→∞
(17)
where ηout (·) : R → R is a function acting pointwise on the noisy eigenvalues, as a result ηout (·) ∈ FGCA . More precisely, we have: (p e2 − 4σ 2 if |λ| e > 2σ λ e ηout (λ) = (18) e ≤ 2σ 0 if |λ| See Appendix C.1 for proof. Remark 2. It follows immediately from Theorem 2 and Lemma 1 that in this asymptotic regime considered above, ℓ⋆GCA = ℓ⋆SA . As such, the graph convolutional attention model can approximate the optimal spectral attention model in this asymptotic regime and lead to an improvement in the minimum achievable loss over the linear attention model according to Theorem 1.
3
How Softmax Can Help Denoise Further
e ) can learn to denoise the In Section 2 we saw how a model that is linear (in the input tokens U eigenvalues. Building on this observation, we now study how applying an additional nonlinearity, specifically the softmax often used in attention-based models, can further improve denoising. We will see that from a spectral view, this corresponds to denoising the eigenvectors, beyond the eigenvalue denoising of Section 2. Problem Setup. Consider A ∈ Rn×n to be block diagonal with k blocks of size m1 , . . . , mk respectively. The entries within each block are all one and outside of the blocks are all zero. This leads to A being a rank k matrix with Uk denoting the matrix of the top k eigenvectors. We denote b=U e ΛU e ⊤ the matrix with clean eigenvalues and noisy eigenvectors. by A Consider the attention-based estimator introduced in (3). We idealize the spectral denoising step ⊤ studied in Section 2 as exact, and set WV WV⊤ = α1 WQ WK = Λ. With this choice of WQ , QK , WV , the attention-based denoising map from (3), simplifies into an analytically tractable surrogate, which b are known: we use to study denoising under the assumption that the clean eigenvalues (and hence A) b α) = softmax(αA) b ·A b · (softmax(αA)) b ⊤ fsm (A;
(19)
where softmax(·) applies a row-wise softmax operation. The model in (19) isolates the role of the softmax, with the parameter α controlling how sharp the softmax is. Loss definitions and goal.
We define the denoising loss dependent on α as: 2
b α) − A ℓsoft (α) = EE f (A;
F
(20)
where E is the noise matrix. Our goal is to show that the minimum of this loss is smaller than the loss when we have the clean eigenvalues with the noisy eigenvectors. The latter we denote as ℓbasis since e and the original U : it is essentially the loss caused by the mismatch between the noisy eigenbasis U 2
b−A ℓbasis = EE A
F
(21)
Next, we will show that the softmax denoiser approximates projection onto the clean eigenbasis, which itself improves over ℓbasis . Concretely, we proceed in two steps. First, in Lemma 2 we show projection onto the clean eigenbasis strictly improves over ℓbasis . Then, in Theorem 3 we show that for the correct choice of α, the softmax denoiser approximates this projection well enough to inherit the improvement. 6
The connection between softmax and the aforementioned projection is more clear if we note that by b in the softmax denoiser with the clean adjacency matrix A, we get replacing A lim softmax(αA) = PU ,
(22)
α→∞
where PU = Uk Uk⊤ is the projection matrix onto the space of the principal eigenvectors of A. This motivates studying the loss attained by projecting onto the clean eigenbasis: b U⊤ − A ℓproj = EE PU AP
2
(23)
F
The following lemma shows that this projection strictly reduces the loss, since it removes the components of the noise caused by the eigenbasis rotating outside of the initial subspace. Lemma 2 (Projection improves denoising). Projecting onto the principal eigenbasis of the original graph strictly reduces the loss, i.e., ℓproj < ℓbasis (24) b The Of course, when denoising we do not have access to the clean adjacency matrix A, only to A. b is b softmax denoiser softmax(αA) can therefore be viewed as an approximate projection: when A close to A, applying softmax with sufficiently large α should produce something close to PU . The gap between ℓsoft (α) and ℓproj depends on the choice of α: for very small or very large α the gap is large, but the following theorem shows that there exist intermediate choices of α for which the gap is smaller than the improvement gained by projection i.e., ℓbasis − ℓproj , which in turn means that the softmax denoiser strictly improves upon ℓbasis . m2 Theorem 3. Assume that the noise is sufficiently small, i.e., E ∥E∥2F ≪ min 1, log . Then, 2k ⋆ there exists α > 0 such that we have: ℓsoft (α⋆ ) − ℓproj < ℓbasis − ℓproj
4
(25)
Experiments
Our experiments serve three purposes. We first demonstrate that replacing the standard linear query– key projections with graph convolutional attention improves graph denoising, with the per-dataset improvement tracking the spectral diversity predicted by Theorem 1. We then establish that these denoising gains carry over to generative diffusion. Finally, we show that combining our variant with R-PEARL matches vanilla DiGress generative performance while removing its expensive spectral node features resulting in faster inference. 4.1
Models and Baselines
As a baseline in both denoising and generative experiments, we use a standard graph transformer consisting of multiple layers of multi-head self-attention. The input tokens are positional encodings only — specifically, the top k eigenvectors of the noisy adjacency matrix. Given a noisy adjacency e ∈ Rn×n the denoiser predicts adjacency logits A b ∈ Rn×n in a stack of L multi-head attention A b are produced by a learned linear combination of the final block’s per-head blocks; the logits A attention scores. See Appendix B.3.1 for the full description. We compare this baseline, which we refer to as Graph Transformer (GT), to a variant which differs only in the Query and Key projections inside each block. Graph Transformer (GT): (ℓ)
(ℓ)
Q(ℓ) = X (ℓ) WQ ,
K (ℓ) = X (ℓ) WK .
(26)
Graph Convolutional Attention Transformer (GCAT): Q(ℓ) =
P −1 X
(ℓ)
A p X (ℓ) HQ,p ,
K (ℓ) =
p=0
P −1 X p=0
7
(ℓ)
A p X (ℓ) HK,p .
(27)
For GCAT, the queries and keys become learnable polynomials of the noisy adjacency of order P , allowing two nodes to attend on the basis of their P -hop neighborhoods in the adjacency A. DiGress and Spectral Variants. In order to validate the merit of GCA on a more recent graph diffusion baseline, we use DiGress. We also study the effect of incorporating spectral information explicitly into the architecture via 2 ablations: we replace the attention Q, K projections with 1) a spectral attention layer realised by a polynomial filter in the noisy Laplacian eigenvalues and 2) a graph convolutional attention layer realised by polynomial filters in the adjacency itself i.e., the same construction used in GCAT above, now applied to the DiGress backbone while keeping the rest of the recipe unchanged. See Appendix B.3.4 for architectural details. Independently of the attention variant, we also replace DiGress’s eigendecomposition-based node features with R-PEARL, the random-feature variant of the PEARL positional encoding [16]. RPEARL learns positional encodings that are simultaneously expressive, stable, and scalable by processing a random noise signal with a GNN. Crucially, this lets us sidestep the instability and expense of directly computing eigenvectors on large graphs. See Appendix B.3.3 for details.
4.2
Datasets
We use a mix of real benchmark graph datasets from PyTorch Geometric’s TUDataset collection, the SPECTRE stochastic block model (SBM) benchmark of [27], and synthetic SBMs sampled with controllable block-size heterogeneity. All graphs are treated as undirected and unattributed: we keep only the adjacency structure and discard any node or edge labels supplied by the source dataset. Synthetic Datasets. We construct synthetic SBM datasets with controllable graph diversity. Each graph has n = 200 nodes, with block count sampled uniformly from K ∈ {2, 3, 4} and maximum block sizes of 50 and 60. Block-size heterogeneity is governed by a Dirichlet concentration α ∈ {0.1, 1.0, 10.0}; larger α yields more homogeneous block sizes and thus less diversity across graphs. Real Datasets. We use five collections of variable-size unattributed graphs, all from TUDataset except DEEZER-EGO-NETS. PROTEINS [3] has 1,113 protein-structure graphs (up to 620 nodes) with secondary-structure elements as nodes. ENZYMES [3] has 600 enzyme tertiary-structure graphs (up to 126 nodes) across six EC classes. IMDB-BINARY [48] provides 1,000 movie coappearance ego networks (up to 136 nodes, small and dense), and COLLAB [48] provides 5,000 scientific-collaboration ego networks from three physics communities (up to 492 nodes, heavy-tailed). DEEZER-EGO-NETS [36] contains 9,629 Deezer user ego networks with mutual-friendship edges (up to 363 nodes).
4.3
Denoising Experiments
For our denoising experiments, we sample clean graphs from the training set, add noise to the adjacency matrix, and then pass the noisy adjacency as input to the denoising model. We then train to minimize the loss between the model’s prediction and the original noiseless graph; the validation loss we report throughout is this reconstruction error against the clean adjacency over graphs sampled from a validation subset not used in training. The noising process is discrete, similar to [44], wherein each edge is flipped with some probability ε, independently from the other edges. The probability ε, which determines the noise level, is sampled for each graph in the batch from a list of values ranging from 0.05 to 0.5. As we observe in Figure 1c, GCAT has improved denoising performance compared to the GT baseline consistently across all the datasets, as evidenced by the lower validation loss. Figures 1a and 1b show the corresponding qualitative comparison on ENZYMES and SPECTRE, where GCAT’s reconstructions more faithfully recover the structure of the original graph than GT’s. Furthermore, Figure 1c shows that the margin of improvement for each dataset is strongly correlated with the estimated spectral diversity of the dataset, which is in line with our expectation from Theorem 1. This validates the idea that our proposed spectral diversity metric is indeed a strong predictor of the improvement gained by utilizing spectral information directly in the attention mechanism. We approximate the spectral diversity using a KNN approach detailed in Appendix B.5 to estimate e k ]. E[B | Λ 8
(a) ENZYMES dataset
(b) SPECTRE dataset
(c) Diversity vs Improvement
Figure 1: Quantitative and Qualitative Denoising comparison of GT and GCAT.
4.4
Generative Experiments
We evaluate the GCAT architecture in two generative settings. (1) Our main setting mirrors the denoising experiments and our theoretical results: we use the same diffusion training and inference pipeline as DiGress [44], but with the GT or GCAT architecture as the denoiser. (2) We additionally integrate GCAT into the full DiGress recipe, keeping all architecture, hyperparameters, and implementation details as in the published code base — except training steps, which we cap at 88k for SPECTRE-SBM and 300k for ENZYMES (from the published 550k) due to computational and time constraints. MMDs are evaluated every 4,400 optimiser steps for SPECTRE-SBM, matching upstream’s 100-epoch × sample-every-4 cadence, and every 75,000 for ENZYMES. Recon LogP ↑
NLL ↓
SBM (α = 0.1)
-101.76 -30.37
532.35 505.94
0.0346 0.0214
0.0233 0.0257
0.0496 0.0268
0.0433 0.0416
SBM (α = 1.0)
-112.70 -31.66
576.67 544.44
0.0721 0.0247
0.0157 0.0163
0.0954 0.0135
0.0240 0.0220
SBM (α = 10)
-70.31 -30.88
565.66 548.21
0.0562 0.0186
0.0166 0.0156
0.0047 0.0025
0.1233 0.0495
SPECTRE
-1925.37 -1024.65
5044.54 4885.99
0.0172 0.0801
0.0743 0.0718
0.0151 0.0075
0.1405 0.1553
ENZYMES
-182.88 -28.26
530.31 424.79
0.0502 0.0458
0.0478 0.0431
0.0956 0.0458
0.0541 0.2692
PROTEINS
-354.86 -122.28
968.25 838.50
0.0885 0.0310
0.0993 0.0514
0.1949 0.0257
0.0616 0.0331
IMDB
-55.13 -13.39
275.21 208.99
0.1249 0.0278
0.3591 0.2608
0.1405 0.0319
0.3800 0.4133
COLLAB
-1489.94 -1189.15
3588.22 3136.62
0.1465 0.3429
0.0270 0.3399
0.1337 0.3593
0.2144 0.9954
DEEZER
-177.88 -49.26
502.30 414.70
0.0147 0.0289
0.0226 0.0568
0.0235 0.0370
0.3136 0.5548
Dataset
Spec MMD ↓ Clust MMD ↓ Deg MMD ↓ Orbit MMD ↓
Table 1: Comparison of generation metrics between GT (white rows) and GCAT (grey rows). Bold marks the better value within each pair. ↑/↓ indicate higher/lower is better.
GCAT vs GT Results. As the results in Table 1 show, the gains in denoising loss translate to uniform improvement in logP and NLL across datasets, when using GCAT in generative diffusion. With the exception of COLLAB and DEEZER, these improved training metrics typically also translate to 9
improved structural metrics in the generated samples. This improvement can also qualitatively be seen in generated graphs when compared to reference graphs from the datasets in Figure 2. Deezer Ego Net Graphs
Two-Community SBM Graphs (α = 10)
Figure 2: Top: Reference graphs sampled from the dataset, Middle: Graphs generated using with GCAT, Bottom: Graphs generated using GT, Left: two-community SBM graphs, and Right: and ego-network graphs. DiGress Results. We evaluate on SPECTRE-SBM [27] and ENZYMES [3], two standard literature benchmarks. On SPECTRE-SBM we follow the protocol of DiGress [44]: the fixture contains 200 graphs of up to 200 nodes drawn from a 2–5-community stochastic block model. On ENZYMES we follow HiGen [17]. Following HiGen, we report raw MMD2 on the degree, clustering-coefficient, orbit-count, and normalised-Laplacian-spectrum distributions. Each evaluation samples 40 graphs on both datasets. We observe that the variants leveraging spectral and graph convolutional attention roughly achieve parity with vanilla DiGress in generation quality as measured by MMDs, including when using R-PEARL instead of the eigen-decomposition based features. This gives some evidence that it is indeed sufficient to incorporate the spectral information via GCA + R-PEARL, and expensive eigen-decomposition is not required. Full numbers and qualitative samples are in Appendix B.1; per-metric training trajectories in Table 8, Appendix B.4. Crucially, we see in Table 2 that this parity comes with a noticeable speedup in inference (up to 19% for the PEARL + GCA variant on SBM) from eliminating the node feature computation and eigendecomposition cost. Because wall-clock time here is dominated by whether an eigendecomposition is computed per step, the payoff scales with graph size: on the larger SBM graphs (nmax =200) all R-PEARL variants are faster, whereas on the small ENZYMES graphs (nmax =126) the fixed overhead of the random-feature GNN can swamp the saving (e.g. PEARL is +14%). This suggests that as graph size grows, using our variant with R-PEARL and Graph Convolutional attention could potentially lead to even larger gains in inference time without sacrificing generation quality. Dataset SBM (nmax =200)
ENZYMES (nmax =126)
Variant
Params
Inference vs base
DiGress (eigh) PEARL PEARL + GCA
7.1M 7.2M 11.9M
— -6% -19%
DiGress (eigh) PEARL PEARL + GCA
7.1M 7.2M 11.9M
— +14% -14%
Table 2: Inference-cycle wall time relative to vanilla DiGress (negative % = faster). Inference-cycle time is wall-clock-derived per validation cycle (sampling + scoring + I/O). Params are total model parameters.
10
5
Conclusions
We studied graph denoising from a spectral perspective and used this view to clarify why attentionbased architectures such as DiGress can perform well in graph denoising and diffusion. Our analysis shows that standard linear attention is fundamentally limited under a denoising objective, since it can only learn an average spectral denoising rule over the training distribution, which becomes suboptimal when graphs exhibit heterogeneous spectra. In contrast, for graph distributions with community-like spectra and sufficiently high spectral diversity, attention mechanisms that adapt to the noisy input spectrum can implement an optimal shrinkage-like estimator, thereby provably improving over estimators that are agnostic to the observed spectrum. We formalized this ideal through Spectral Attention, identified spectral diversity as the quantity governing its advantage, and proposed Graph Convolutional Attention (GCA) as a practical permutation-equivariant realization based on graphfiltered query and key projections. In the SBM regime, we showed that GCA asymptotically matches the ideal spectral mechanism, while the softmax nonlinearity can provide additional denoising by approximately projecting noisy eigenvectors onto the clean eigenspace. Empirically, the theory is reflected in practice: replacing standard attention with GCA consistently improves graph denoising across synthetic and real datasets, and the gains scale with spectral diversity. The same phenomenon transfers to diffusion models, where preserving this shrinkage-style capacity makes it possible to remove costly spectral node features while remaining competitive, as in the DiGress ablations, and to improve performance on suitable datasets by explicitly incorporating this inductive bias. Overall, our results suggest that spectral adaptation is a key ingredient for effective graph denoising and generative diffusion, and provide both a theoretical explanation and a practical architectural principle for designing stronger graph diffusion models.
11
References [1] F. Benaych-Georges and R. R. Nadakuditi. The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices, 2010. [2] D. Bo, C. Shi, L. Wang, and R. Liao. Specformer: Spectral graph neural networks meet transformers. arXiv preprint arXiv:2303.01028, 2023. [3] K. M. Borgwardt, C. S. Ong, S. Schönauer, S. V. N. Vishwanathan, A. J. Smola, and H.-P. Kriegel. Protein function prediction via graph kernels. In Proceedings of the Thirteenth International Conference on Intelligent Systems for Molecular Biology (ISMB), pages 47–56, 2005. [4] E. Dai, W. Jin, H. Liu, and S. Wang. Towards robust graph neural networks for noisy graphs with sparse labels. In Proceedings of the fifteenth ACM international conference on web search and data mining, pages 181–191, 2022. [5] H. Deng and B. Liu. Gadpn: Graph adaptive denoising and perturbation networks via singular value decomposition. arXiv preprint arXiv:2601.08230, 2026. [6] V. P. Dwivedi and X. Bresson. A generalization of transformer networks to graphs, 2021. [7] B. Fatemi, L. El Asri, and S. M. Kazemi. Slaps: Self-supervision improves structure learning for graph neural networks. Advances in Neural Information Processing Systems, 34:22667–22681, 2021. [8] S. Feizi, D. Marbach, M. Médard, and M. Kellis. Network deconvolution as a general method to distinguish direct dependencies in networks. Nature biotechnology, 31(8):726–733, 2013. [9] H. R. Frost. Denoising deterministic networks using iterative fourier transforms. arXiv preprint arXiv:2602.00790, 2026. [10] A. Garg. Graph transformers without positional encodings. arXiv preprint arXiv:2401.17791, 2024. [11] R. He, K. Gopinath, C. Desrosiers, and H. Lombaert. Spectral graph transformer networks for brain surface parcellation. In 2020 IEEE 17th International Symposium on Biomedical Imaging (ISBI), pages 372–376. IEEE, 2020. [12] 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 on knowledge discovery & data mining, pages 66–74, 2020. [13] J. Jo, D. Kim, and S. J. Hwang. Graph generation with diffusion mixture. arXiv preprint arXiv:2302.03596, 2023. [14] J. Jo, S. Lee, and S. J. Hwang. Score-based generative modeling of graphs via the system of stochastic differential equations. In International conference on machine learning, pages 10362–10383. PMLR, 2022. [15] N. Josephs, W. Li, and E. D. Kolaczyk. Network recovery from unlabeled noisy samples. In 2021 55th Asilomar Conference on Signals, Systems, and Computers, pages 1268–1273. IEEE, 2021. [16] C. I. Kanatsoulis, E. Choi, S. Jegelka, J. Leskovec, and A. Ribeiro. Learning efficient positional encodings with graph neural networks. arXiv preprint arXiv:2502.01122, 2025. [17] M. Karami. HiGen: Hierarchical graph generative networks. In Advances in Neural Information Processing Systems (NeurIPS), 2023. [18] D. Kreuzer, D. Beaini, W. Hamilton, V. Létourneau, and P. Tossou. Rethinking graph transformers with spectral attention. Advances in neural information processing systems, 34:21618–21629, 2021. 12
[19] J. Li, M. Liu, H. Zhang, P. Wang, Y. Wen, L. Pan, and H. Cheng. Mask-gvae: Blind denoising graphs via partition. In Proceedings of the Web Conference 2021, pages 3688–3698, 2021. [20] R. Liao, Y. Li, Y. Song, S. Wang, W. L. Hamilton, D. Duvenaud, R. Urtasun, and R. S. Zemel. Efficient graph generation with graph recurrent attention networks. In Advances in Neural Information Processing Systems (NeurIPS), volume 32, pages 4257–4267, 2019. [21] D. Lim, J. Robinson, L. Zhao, T. Smidt, S. Sra, H. Maron, and S. Jegelka. Sign and basis invariant networks for spectral graph representation learning. arXiv preprint arXiv:2202.13013, 2022. [22] Y. Liu, C. Du, T. Pang, C. Li, M. Lin, and W. Chen. Graph diffusion policy optimization. In Advances in Neural Information Processing Systems (NeurIPS), 2024. [23] J. Luo, Q. Sun, H. Yuan, X. Fu, and J. Li. Robust graph learning against adversarial evasion attacks via prior-free diffusion-based structure purification. In Proceedings of the ACM on Web Conference 2025, pages 2098–2110, 2025. [24] H. Lyu, Y. H. Kureh, J. Vendrow, and M. A. Porter. Learning low-rank latent mesoscale structures in networks. Nature Communications, 15(1):224, 2024. [25] J. Ma, M. He, and Z. Wei. Polyformer: Scalable node-wise filters via polynomial graph transformer. In Proceedings of the 30th ACM SIGKDD conference on knowledge discovery and data mining, pages 2118–2129, 2024. [26] F. Marcoccia, C. Adjih, and P. Mühlethaler. Netdiff: Deep graph denoising diffusion for ad hoc network topology generation. arXiv preprint arXiv:2410.08238, 2024. [27] K. Martinkus, A. Loukas, N. Perraudin, and R. Wattenhofer. SPECTRE: Spectral conditioning helps to overcome the expressivity limits of one-shot graph generators. In Proceedings of the 39th International Conference on Machine Learning (ICML), volume 162 of Proceedings of Machine Learning Research, pages 15159–15179. PMLR, 2022. [28] P. Milanfar. A tour of modern image filtering: New insights and methods, both practical and theoretical. IEEE signal processing magazine, 30(1):106–128, 2012. [29] P. Milanfar and M. Delbracio. Denoising: a powerful building block for imaging, inverse problems and machine learning. Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, 383(2299), 2025. [30] A. Q. Nichol and P. Dhariwal. Improved denoising diffusion probabilistic models. In Proceedings of the 38th International Conference on Machine Learning (ICML), volume 139 of Proceedings of Machine Learning Research, pages 8162–8171. PMLR, 2021. [31] Z. Pengmei and Z. Li. Technical report: The graph spectral token–enhancing graph transformers with spectral information. arXiv preprint arXiv:2404.05604, 2024. [32] Y. Qin, M. Madeira, D. Thanou, and P. Frossard. Defog: Discrete flow matching for graph generation. arXiv preprint arXiv:2410.04263, 2024. [33] S. Rey, V. Tenorio, S. Rozada, L. Martino, and A. G. Marques. Overparametrized deep encoderdecoder schemes for inputs and outputs defined over graphs. In 2020 28th European Signal Processing Conference (EUSIPCO), pages 855–859. IEEE, 2021. [34] S. Rey, V. M. Tenorio, and A. G. Marqués. Robust graph filter identification and graph denoising from signal observations. IEEE Transactions on Signal Processing, 71:3651–3666, 2023. [35] M. Rigotti, N. Thumiger, and T. Frick. Gist: Gauge-invariant spectral transformers for scalable graph neural operators. arXiv preprint arXiv:2603.16849, 2026. [36] B. Rozemberczki and R. Sarkar. Characteristic functions on graphs: Birds of a feather, from statistical descriptors to parametric models. In Proceedings of the 29th ACM International Conference on Information and Knowledge Management (CIKM), pages 1325–1334. ACM, 2020. 13
[37] W. Rudin. Principles of Mathematical Analysis. McGraw-Hill, 3rd edition, 1976. [38] S. Segarra, A. G. Marques, G. Mateos, and A. Ribeiro. Network topology inference from spectral templates. IEEE Transactions on Signal and Information Processing over Networks, 3(3):467–483, 2017. [39] J. Song, C. Meng, and S. Ermon. Denoising diffusion implicit models. arXiv preprint arXiv:2010.02502, 2020. [40] Y. Song, J. Sohl-Dickstein, D. P. Kingma, A. Kumar, S. Ermon, and B. Poole. Score-based generative modeling through stochastic differential equations. arXiv preprint arXiv:2011.13456, 2020. [41] V. M. Tenorio, S. Rey, and A. G. Marques. Robust graph neural network based on graph denoising. In 2023 57th Asilomar Conference on Signals, Systems, and Computers, pages 578–582. IEEE, 2023. [42] V. M. Tenorio, S. Rey, and A. G. Marques. Blind deconvolution of sparse graph signals in the presence of perturbations. In ICASSP 2024-2024 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pages 9406–9410. IEEE, 2024. [43] P. Trivedi, R. Rossi, D. Arbour, T. Yu, F. Dernoncourt, S. Kim, N. Lipka, N. Park, N. K. Ahmed, and D. Koutra. Leveraging graph diffusion models for network refinement tasks. arXiv preprint arXiv:2311.17856, 2023. [44] C. Vignac, I. Krawczuk, A. Siraudin, B. Wang, V. Cevher, and P. Frossard. Digress: Discrete denoising diffusion for graph generation. arXiv preprint arXiv:2209.14734, 2022. [45] H. Wang, Z. Qin, Z. Sun, Q. Yang, and J. Shao. Unsupervised graph denoising via feature-driven matrix factorization. Information Sciences, 661:120156, 2024. [46] Y.-J. Wu, E. Levina, and J. Zhu. Generalized linear models with low rank effects for network data. arXiv preprint arXiv:1705.06772, 2017. [47] H. Xu, L. Xiang, J. Yu, A. Cao, and X. Wang. Speedup robust graph structure learning with low-rank information. In Proceedings of the 30th ACM International Conference on Information & Knowledge Management, pages 2241–2250, 2021. [48] P. Yanardag and S. V. N. Vishwanathan. Deep graph kernels. In Proceedings of the 21st ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD), pages 1365–1374. ACM, 2015. [49] T. Yang, J. Meng, M. Zhou, Y. Yang, Y. Wang, X. Li, and Y. Tong. You can’t ignore either: Unifying structure and feature denoising for robust graph learning. In Proceedings of the 33rd ACM International Conference on Information and Knowledge Management, pages 4178–4182, 2024. [50] J. You, R. Ying, X. Ren, W. L. Hamilton, and J. Leskovec. GraphRNN: Generating realistic graphs with deep auto-regressive models. In Proceedings of the 35th International Conference on Machine Learning (ICML), volume 80 of Proceedings of Machine Learning Research, pages 5694–5703. PMLR, 2018. [51] B. Zhou, R. Li, X. Zheng, Y. G. Wang, and J. Gao. Graph denoising with framelet regularizers. IEEE Transactions on Pattern Analysis and Machine Intelligence, 46(12):7606–7617, 2024.
14
Supplementary Materials for “Understanding Graph Denoising” A
Limitations and Future Directions
Expanding the scope of the experiments to more graph benchmark datasets, both real and synthetic could potentially help further validate the merit of GCA and illuminate its potential failure modes. Furthermore, the exact role of R-PEARL (and in general other types of positional encodings that could be used instead of eigenvectors) can be explored further both theoretically and in practice. Studying the interaction between R-PEARL embeddings and the GCA architecture is a promising direction. On the theoretical side, parts of our analysis are limited to Stochastic Block Models. Considering families of graphs in future work could further strengthen the theoretical message ad our understanding of graph denoising and diffusion. Finally, our empirical comparisons on SOTA graph diffusion is limited in number of training seeds, dataset variety and hyperparameter ablations. More computational resources and time is required to make these results more statistically meaningful and the results should therefore be seen as exploratory evidence, and cannot support definitive conclusions.
B
Experimental Details and Additional Results
B.1
DiGress generative ablation results
The headline numbers and generated samples for the DiGress ablation panel referenced in Section 4 are reproduced below. Table 3 reports the best per-metric value per variant within the per-panelminimum step horizon (88k for SPECTRE-SBM, 300k for ENZYMES); Figure 3 shows reference graphs alongside generated samples from the upstream DiGress baseline and the R-PEARL + GCAT variant. Hyperparameters, optimisation, and evaluation cadence shared across these runs are documented in Appendix B.3.4. Spec MMD2 ↓ Clust MMD2 ↓ Deg MMD2 ↓ Orbit MMD2 ↓ SBM acc. ↑
Dataset
Variant
SPECTRE-SBM
DiGress (baseline) DiGress + R-PEARL DiGress + R-PEARL + Spec. Attn. DiGress + R-PEARL + GCAT
0.2102 0.2102 0.2088 0.2081
0.1306 0.1297 0.1303 0.1292
0.1803 0.1813 0.2001 0.1833
0.0909 0.0991 0.0948 0.0962
0.5625 0.5312 0.4062 0.2500
ENZYMES
DiGress (baseline) DiGress + R-PEARL DiGress + R-PEARL + Spec. Attn. DiGress + R-PEARL + GCAT
0.1960 0.1881 0.1876 0.1993
0.1042 0.0967 0.0974 0.0981
0.1803 0.1814 0.1852 0.1924
0.1056 0.0971 0.1332 0.2384
— — — —
Table 3: DiGress ablations across the four viable variants over training steps up to 88k (SPECTRESBM) / 300k (ENZYMES), following HiGen [17] in reporting the best value per metric across all logged validation cycles for each run. Bold marks the best value per dataset × metric.
B.2
Datasets
We evaluate on a mix of real benchmark graphs drawn from PyTorch Geometric’s TUDataset collection, the SPECTRE stochastic block model (SBM) benchmark [27], and synthetic SBMs sampled with controllable block-size heterogeneity. All graphs are treated as undirected and unattributed: we keep only the adjacency structure and discard any node or edge labels supplied by the source dataset. Unless stated otherwise, we use a 70/10/20 train/validation/test split with a fixed seed. B.2.1
Real datasets
We use five collections of variable-size unattributed graphs. 15
SPECTRE-SBM
ENZYMES
Figure 3: Top: Reference graphs from the dataset, Middle: Generated with the DiGress + R-PEARL + GCAT variant. Bottom: Generated with DiGress baseline.
• PROTEINS [3], from TUDataset: 1 113 protein-structure graphs in which nodes are secondary-structure elements connected when they are neighbours in the amino-acid sequence or in 3D space. Graph size ranges up to 620 nodes, with most graphs in the few-tens to low-hundreds range. • ENZYMES [3], from TUDataset: 600 enzyme tertiary-structure graphs spanning the six EC top-level classes. Graph size ranges up to 126 nodes, typically ≈ 30–60 nodes per graph. • IMDB-BINARY [48], from TUDataset: 1 000 movie-collaboration ego networks in which nodes are actors/actresses and edges connect those that appeared together in a film. Graph size ranges up to 136 nodes with a strongly skewed distribution toward smaller, dense ego networks. • COLLAB [48], from TUDataset: 5 000 scientific-collaboration ego networks built from three physics communities. Graph size ranges up to 492 nodes, with heavy-tailed size and degree distributions. • DEEZER-EGO-NETS [36]: 9 629 ego networks of Deezer users, with edges representing mutual-friend relationships in the ego’s neighbourhood. Graph size ranges up to 363 nodes; the distribution is dominated by ego networks of a few dozen nodes. In all five cases we drop the original node and edge attributes and predict the binary adjacency only. This matches the unconditional graph-generation setting used in prior work [50, 20, 44]. Splits use the PyG-default ordering with a fixed seed of 42 and a 70/10/20 train/val/test ratio. B.2.2
SPECTRE SBM benchmark
We additionally use the SBM benchmark released with the SPECTRE evaluation suite [27] and adopted as the canonical SBM evaluation setting by DiGress [44]. The fixture contains 200 SBM graphs generated with 2–5 communities of variable size, intra-block edge probability pintra ≈ 0.30, and inter-block edge probability pinter ≈ 0.005; node counts range over 44 ≤ n ≤ 187. We use the upstream 128/32/40 train/val/test split (torch.randperm(200) with seed 0) so that our results are byte-comparable with published DiGress numbers. Quantitative evaluation reports the SPECTREstyle maximum mean discrepancy (MMD) over degree, clustering, and orbit-count distributions, plus the SBM-likelihood Wald-test accuracy whose null distribution uses the same (pintra , pinter ) parameters. B.2.3
Synthetic SBMs with controllable block-size heterogeneity
To probe how each method handles community structure under controlled conditions, we generate synthetic SBM datasets at two graph sizes, n = 100 and n = 200 (presets sbm_n100, sbm_n200). Block counts are sampled uniformly from K ∈ {2, 3, 4}, with maximum block sizes of 50 and 60 respectively. Edge probabilities default to pintra = 1.0 and pinter = 0.0 (i.e. disjoint cliques), but can be varied along ranges to expose the model to a spectrum of community contrast. 16
The key controlled axis is block-size heterogeneity, governed by a Dirichlet concentration parameter α (in code: graph_config.block_size_alpha). For each synthetic graph we sample a block-size partition (s1 , . . . , sK ) ∼ n · Dirichlet(α, . . . , α),
(28)
rounded to integers summing to n, with a minimum block size of one. The concentration α smoothly interpolates between two regimes: small α (e.g. α → 0+ ) concentrates mass on a single block and produces strongly unbalanced communities, while large α (e.g. α ≫ 1) flattens the simplex and recovers near-equal-sized blocks (the limit α → ∞ matches the equal-partition baseline). This single knob lets us study how generative models behave under increasing block-size imbalance while holding n, K, and (pintra , pinter ) fixed. We sweep α over a logarithmic grid in the experiments of Section 4. Block sizes are re-sampled per graph; intra- and inter-block edges are then drawn independently from Bernoulli(pintra ) and Bernoulli(pinter ) as in the standard SBM definition. B.3 B.3.1
Architectural details Graph Transformer and Graph Convolutional Attention Transformer
Shared pipeline. We extract the top-k eigenvectors V ∈ Rn×k of A and lift them to the model dimension d: X (0) = V Win ,
Win ∈ Rk×d .
(29)
Each of the first L − 1 blocks applies a residual multi-head attention update with h heads of dimension dk = dv = d/h: X (ℓ+1) = LN X (ℓ) + MHA(ℓ) A, X (ℓ) , ℓ = 0, . . . , L − 2, (30) where, given queries, keys, and values Q(ℓ) , K (ℓ) , V (ℓ) , each head computes (ℓ) (ℓ)⊤ Qi Ki (ℓ) √ Si = , dk
(ℓ)
Attni
(ℓ)
= softmax Si
(ℓ)
Vi ,
i = 1, . . . , h,
(31)
The final block produces no node features; its per-head scores S (L−1) ∈ Rh×n×n are mixed into the edge logits by a learned linear combination, b= A
h X
(L−1)
wi Si
+ b,
w ∈ Rh .
(32)
i=1
The two models differ only in the Q/K projections inside each block. Graph Transformer (ℓ)
(ℓ)
Q(ℓ) = X (ℓ) WQ ,
K (ℓ) = X (ℓ) WK .
(33)
Graph Convolutional Transformer Q(ℓ) = LN
P −1 X
! (ℓ) A p X (ℓ) WQ,p
K (ℓ) = LN
,
p=0
P −1 X
! (ℓ) A p X (ℓ) WK,p
.
(34)
p=0
The queries and keys become learnable polynomials of the noisy adjacency, allowing two nodes to attend on the basis of their P -hop neighborhoods in A. B.3.2
Generative Experiments with GT and GCAT Denoisers
The setup is similar to the one described in B.3.4. The hyperparameters specific to these runs are provided in Table 4. 17
Table 4: Hyperparameters shared across all GCAT and GT runs in our generative experiments
B.3.3
Block
Setting
Value
Architecture
model class embedding source embedding dimension k depth L model width dmodel attention heads dropout graph-conv filter taps timestep conditioning
GT/GCAT top-k eigenvectors 16 3 128 8 0.0 2 none (time-unconditional)
Diffusion
forward process noise schedule timesteps T limit distribution sampler
categorical cosine-iDDPM [30] 500 empirical marginal of train loader ancestral
Optimisation
optimiser learning rate weight decay LR scheduler gradient clipping EMA loss
AdamW with AMSGrad 2 × 10−4 10−12 none none none categorical CE + VLB, λE = 5
Evaluation
val-loss cadence sample/MMD cadence samples per generative eval clustering kernel σ
every 1,000 steps once at end of training 128 0.1
R-PEARL
The encoder samples s = 32 standard Gaussian features per node, propagates them through three e −1/2 , and projects message-passing layers over the symmetrically normalised adjacency D−1/2 AD the result to a dPEARL = 16-dimensional per-node embedding. Each message-passing layer applies a two-layer MLP with ReLU activation, hidden width 64, and LayerNorm, adding a residual connection where input and output widths match. The resulting embedding is concatenated to per-node cycle counts at lengths 3, 4, 5 to form the per-node features; per graph we keep the normalised graph size nvalid /nmax and cycle counts at lengths 3, 4, 5, 6. Total widths ∆(dX , dE , dy ) = (3 + dPEARL , 0, 5), compared with (6, 0, 11) for DiGress’s eigendecomposition path. To make evaluation deterministic, we fix the eval-time features to a single seeded Gaussian draw of shape (1, nmax , s), shared across each evaluation batch. Training continues to draw fresh features per forward pass, so the model sees the full R-PEARL feature distribution during optimisation; at evaluation we therefore report one specific R-PEARL realisation rather than a Monte Carlo average over draws. B.3.4
DiGress and variants
Our generative DiGress runs reproduce the upstream SPECTRE-SBM recipe of DiGress [44] and cross-validate against the publicly available SBM checkpoint shipped with GDPO [22], which was retrained from the upstream recipe verbatim and provides an independent set of weights for sanity checks. Architecture. The denoiser is the upstream DiGress XEy graph transformer: a stack of L = 8 blocks that jointly update node features X, edge features E, and a global vector y, with FiLM-style cross-modulation between the three streams. Hidden widths are dX = 256, dE = 64, dy = 64 with 8 attention heads, point-wise feed-forward widths (dffX , dffE , dffy ) = (256, 64, 2048) for SPECTRESBM and (256, 64, 256) for ENZYMES, input/output MLP widths (128, 64, 128), and a learned timestep channel concatenated to y. We use the K = 1 abstract-node convention (one node class, two edge classes) for both datasets. The SPECTRE-SBM choice dffy = 2048 matches the actual shape of the GDPO SBM checkpoint, which was trained at this width despite the value 256 recorded in 18
Vignac’s published config; we adopt the checkpoint’s shape so the released weights remain loadable into our model. ENZYMES, where no comparable checkpoint is released, uses Vignac’s dffy = 256. Structural augmentation. For the vanilla DiGress runs we follow upstream DiGress in augmenting the inputs with hand-crafted structural features. Per node, we concatenate cycle counts at lengths 3, 4, 5 (scaled by 1/10 and clipped at 1), an indicator that the node does not lie in the largest connected component, and the two lowest non-trivial eigenvectors of the noisy graph Laplacian evaluated at the node. Per graph, we add the normalised graph size nvalid /nmax , cycle counts at lengths 3, 4, 5, 6 (also scaled and clipped), the number of connected components, and the five lowest non-trivial Laplacian eigenvalues. Total feature widths ∆(dX , dE , dy ) = (6, 0, 11). Cycle counts are computed from powers of the binary noisy adjacency; the spectral channels require an eigendecomposition of the noisy Laplacian at every diffusion step. The R-PEARL alternative described in Section B.3.3 drops the spectral channels and replaces them with the R-PEARL embedding. Diffusion process. A categorical forward process with the IDDPM cosine schedule [30] on T = 1000 steps and an empirical-marginal limit distribution measured from the training loader at setup. We use the unmodified IDDPM cosine schedule (DiGress’s edge-class-dependent variant for molecular datasets is not used here, since SBM and ENZYMES are binary-edge graphs). The reverse process predicts class probabilities at each step; sampling is ancestral. Optimisation. AdamW with learning rate 2 × 10−4 , weight decay 10−12 , AMSGrad enabled, no learning-rate scheduler, no gradient clipping, and no EMA. The training loss is categorical cross-entropy with edge weight λE = 5 on top of the standard variational lower bound. Seed 666 matches the GDPO retrain so the run lands in a basin comparable to the released checkpoint; Vignac’s repository defaults to seed 0. Batch size is 12, and the published 128/32/40 train/validation/test split of the 200-graph SPECTRE fixture matches the upstream byte-for-byte. Schedule. 5.5 × 105 optimiser steps. Upstream specifies 50,000 epochs at batch size 12 on 128 training graphs, equivalent to ≈ 5.5 × 105 steps; we adopt the step-based form. Reported runs reach ≈ 88k steps for SPECTRE-SBM and ≈ 300k for ENZYMES under our compute budget (Section 4). Validation and full sampling/MMD evaluation share a step-based gate: every 4,400 steps for SPECTRE-SBM (matching upstream Vignac’s 100-epoch validation × sample-every-4 cadence) and every 75,000 steps for ENZYMES (panel-calibrated for evaluation cost). Each evaluation samples 40 graphs at clustering kernel σ = 0.1. Variants. We sweep two architectural axes: the input-augmentation choice (DiGress’s structural augmentation above or the R-PEARL embeddings of Section B.3.3) and the attention-projection choice. The first attention-side replacement substitutes Q/K/V with polynomial spectral filters in the noisy Laplacian eigenvalues using kspec = 16 eigenpairs and three polynomial taps. The second replaces Q/K/V with three-tap polynomials in the adjacency itself, run in two normalisations: the symmetrically normalised adjacency D−1/2 AD−1/2 and the raw adjacency A. Of the six combinations on this 2 × 4 grid (two augmentations × four projection choices), five are evaluated; the cross of DiGress’s structural augmentation with the graph-convolution attention is not currently run. Per-step wall-clock. Table 7 reports the mean per-step optimiser wall-clock time logged by each post-fix run. The relative cost depends strongly on graph size: on the n = 200 SPECTRE-SBM fixture the O(n3 ) Laplacian eigendecomposition that DiGress’s structural augmentation performs at every diffusion step dominates, and replacing it with R-PEARL gives a ∼5% per-step speedup; on ENZYMES, where graphs typically have ≤ 60 nodes, the eigendecomposition is cheap, the R-PEARL message-passing fixed cost is not amortised, and every R-PEARL variant is slower per step than the DiGress baseline. B.4
Additional DiGress results
Table 3 in the main body reports the per-metric best across validation cycles up to the per-panel minimum step (88k for SPECTRE-SBM, 300k for ENZYMES) so longer-running variants do not gain extra “best” attempts. Table 8 below removes that cap and instead annotates each best with the optimiser step at which it occurred (as a superscript), so the trajectory of each metric across training is visible at a glance. 19
Table 5: Hyperparameters shared across all DiGress runs in our generative experiments. Datasets only differ at the points marked in Table 6. Block
Setting
Value
Architecture
depth L hidden widths (dX , dE , dy ) attention heads input/output MLP widths (X, E, y) input/output class dims (CX , CE , Cy ) timestep injection
8 (256, 64, 64) 8 (128, 64, 128) (1, 2, 0) t/T ∈ [0, 1] appended to y
Diffusion
forward process noise schedule timesteps T limit distribution sampler
categorical cosine [30] 1,000 empirical marginal of train loader ancestral
Optimisation
optimiser learning rate weight decay LR scheduler gradient clipping EMA loss
AdamW with AMSGrad 2 × 10−4 10−12 none none none categorical CE + VLB, λE = 5
Schedule
total optimiser steps (target) reached: SPECTRE-SBM / ENZYMES val + sample/MMD cadence (SPECTRE-SBM) val + sample/MMD cadence (ENZYMES) samples per evaluation clustering kernel σ
5.5 × 105 ≈ 88k / ≈ 300k every 4,400 steps every 75,000 steps 40 0.1
Data
batch size seed
12 666 (matches GDPO)
Table 6: Settings that differ across the attention-projection ablations and the two datasets. The input-augmentation axis (DiGress’s structural augmentation versus R-PEARL) is described separately in Section B.3.3 and combines with each row of the attention table. Attention-projection ablations Variant
Q/K/V projection
Polynomial taps
Linear attention Spectral attention Graph-conv attention (normalised) Graph-conv attention (raw)
linear e (kspec = 16 eigenpairs of A) e polynomial in Λ polynomial in D−1/2 AD−1/2 polynomial in A
— 3 3 3
Dataset-specific overrides Setting
SPECTRE-SBM
ENZYMES
dffy nmax Train/val/test split
2048 (matches GDPO checkpoint) 200 128/32/40 on the published 200-graph fixture
256 (Vignac default) 126 70/10/20 percentage split with fixed seed
On SPECTRE-SBM, MMDs and the SBM-accuracy Wald test peak at different points along training. Most MMD bests sit in the first ≈ 22–88k optimiser steps; the SBM accuracy of three of the four variants only peaks at 88–110k. The R-PEARL + GCAT variant illustrates the asymmetry: best spectral MMD by step 44k but best SBM accuracy at step 110k. The pattern is suggestive rather than universal – the vanilla DiGress run reaches its best clustering MMD only at 110k, and pearl + spectral attention peaks SBM accuracy at 44k. We read the table as evidence that MMD-style sample quality and Wald-test community structure are not perfectly co-monotone in training, and leave a more careful longitudinal analysis to future work. 20
Dataset
nsteps Mean (s) Median (s) Speedup vs vignac
Variant
DiGress (baseline) DiGress + R-PEARL SPECTRE-SBM DiGress + R-PEARL + Spec. Attn. DiGress + R-PEARL + GCAT
2254 2372 2200 2390
0.5184 0.4937 0.5345 0.4933
0.5127 0.4857 0.5277 0.4875
— +4.8% -3.1% +4.8%
DiGress (baseline) DiGress + R-PEARL DiGress + R-PEARL + Spec. Attn. DiGress + R-PEARL + GCAT
9977 7404 6207 8768
0.1218 0.1647 0.1962 0.1391
0.1068 0.1498 0.1813 0.1277
— -35.2% -61.1% -14.2%
ENZYMES
Table 7: Per-step optimiser wall-clock time for the four DiGress variants on each dataset, computed as the mean and median of impl-perf/train/step_time_s over all logged training steps in the run. “Speedup vs vignac” is (tvignac − tvariant )/tvignac ; negative values mean the variant is slower than the DiGress baseline. Validation-step wall-clock is not logged separately in our runs and is therefore omitted. Spec MMD2 ↓ Clust MMD2 ↓ Deg MMD2 ↓ Orbit MMD2 ↓
SBM acc. ↑
DiGress (baseline) SPECTRE-SBM DiGress + R-PEARL DiGress + R-PEARL + Spec. Attn. DiGress + R-PEARL + GCAT
0.2102(22k) 0.2102(44k) 0.2088(88k) 0.2081(44k)
0.1292(110k) 0.1297(66k) 0.1303(44k) 0.1292(88k)
0.1803(88k) 0.1813(22k) 0.2001(44k) 0.1833(44k)
0.0909(22k) 0.0991(88k) 0.0948(88k) 0.0962(66k)
0.6250(110k) 0.5312(88k) 0.4062(44k) 0.3750(110k)
DiGress (baseline) DiGress + R-PEARL DiGress + R-PEARL + Spec. Attn. DiGress + R-PEARL + GCAT
0.1960(150k) 0.1881(150k) 0.1876(225k) 0.1993(225k)
0.0961(375k) 0.0967(75k) 0.0974(75k) 0.0981(75k)
0.1803(150k) 0.1814(225k) 0.1852(225k) 0.1818(375k)
0.1037(375k) 0.0971(300k) 0.1332(150k) 0.1171(375k)
— — — —
Dataset
ENZYMES
Variant
Table 8: DiGress ablations, best per metric across all logged validation cycles for each post-fix run, with the optimiser step at which the best was achieved as a superscript ((step) ). No panel-minimum cap is applied here (contrast Table 3), so each variant is scored over its full training horizon. The annotation exposes when each metric peaks during training. Bold marks the best value per dataset × metric.
B.5
Spectral diversity metric
We estimate the improvement-gap surrogate of Theorem 1 non-parametrically and report it on a normalised scale that supports cross-dataset comparison. The estimand, the plug-in estimator that approximates it from a finite sample, the frame-alignment step that makes the cross-graph average meaningful, the bias floor introduced by the plug-in, and the permutation-null calibration that removes it are detailed below. ei = Ai + Ei Population estimand. For each graph i in a dataset, let Ai be its clean adjacency, A e k,i ) the noisy top-k eigenpair of A ei . Define Bi = Vb ⊤ Ai Vbk,i , the a noisy observation, and (Vbk,i , Λ k,i clean adjacency expressed in the noisy top-k eigenbasis. Theorem 1 identifies the gap between lineare k ] − E[B]∥2 , the variance of the optimal spectral and spectral-attention losses with g = E∥E[B | Λ F ⋆ e e predictor f (Λk ) = E[B | Λk ]. Dividing by the total variance tr(Cov B) = E∥B − E[B]∥2F yields the fraction of variance explained, g FVE = ∈ [0, 1], (35) tr(Cov B) e k — equivwhich by the law of total variance equals the R2 of f ⋆ when used to predict B from Λ alently, the relative loss improvement of optimal spectral attention over optimal linear attention (Propositions 1–2). Plug-in estimator. The population quantities f ⋆ , g, and tr(Cov B) are inaccessible; we replace e k,i )}N , we each by a finite-sample plug-in. Given N graphs with paired observations {(Bi , Λ i=1 estimate the optimal predictor by kNN regression on the noisy eigenvalues, X bi = 1 B Bj , (36) m j∈Nm (i)
21
e k,i in where Nm (i) is the set of m graphs other than i whose eigenvalue vectors are closest to Λ Euclidean distance. The plug-in estimates of g and the total variance use the same sample, N
gb = with B̄ = N1
1 X b ∥Bi − B̄∥2F , N i=1
N
X \B) = 1 ∥Bi − B̄∥2F , tr(Cov N i=1
(37)
P
i Bi . The sample-level statistic is their ratio
[ = FVE
gb . \B) tr(Cov
(38)
The estimator is non-parametric: no analytic form for f ⋆ is assumed. Frame alignment. The matrix Bi is not invariant to the gauge of Vbk,i : replacing Vbk,i by Vbk,i Qi for any Qi ∈ O(k) maps Bi → Q⊤ i Bi Qi . Averaging matrices across different per-graph frames adds e k,i (both derive incommensurable quantities and inflates gb, because Qi is partly predictable from Λ b from the same noisy decomposition). We therefore align every Vk,i via orthogonal Procrustes against a single dataset-wide reference frame, the extrinsic Grassmannian mean of the clean top-k eigenbases (top-k left singular vectors of the stacked clean eigenvector blocks). With one common frame, the e k , and the convention-artefact channel that would otherwise residual rotation cannot co-vary with Λ feed a spurious signal into the estimator closes. e k , the neighbours Nm (i) are effectively a random subsample of Bias floor. Under the null B ⊥ Λ b [ acquires a floor the Bj , so Var(Bi ) ≈ Var(B)/m and FVE ek ≈ 1 − 1 . [ B⊥Λ E FVE m N −1
(39)
[ directly to zero is therefore For (m, N ) = (10, 200) this is approximately 0.095. Comparing FVE uninformative. Permutation-null calibration. We estimate the bias floor on each dataset by shuffling the conditioning vectors with a uniformly random permutation π and recomputing the same plug-in ratio, e k,π(i) )} . [ null = FVE [ {(Bi , Λ FVE (40) The shuffle preserves both marginals and breaks only the joint, so its expectation matches the kNN [ real − FVE [ null , computed bias to leading order. The reported quantity is the calibrated margin FVE per seed before averaging across seeds (paired differencing reduces variance because real and null [ null to remain below 0.30; share the same kNN bias). We require this margin to exceed 0.10 and FVE the latter rules out small-N regimes in which the estimator’s variance grows faster than the signal. Hyperparameters. We use m = 10 neighbours and sweep k ∈ {4, 8, 16, 32}. The bias-floor [ null ≈ 0.10, which is empirically observed across the eight datasets. formula at N ≈ 200 gives FVE Noise levels are ε ∈ {0.01, 0.05, 0.1, 0.15, 0.2}, matching the denoising-experiment grid. Five seeds are used for the paired margin and its standard error. The headline figure reports the Gaussian-noise condition at ε = 0.1; the DiGress-noise variant produces the same qualitative ordering. Cross-checks. Two estimator variants run alongside the kNN estimator. A binning estimator partitions graphs into quantile buckets of the spectral gap λ1 − λ2 and computes the classical between-group variance; it agrees with kNN when both are restricted to the 1-D feature, providing an independent estimate of the leading-eigenvalue contribution to the gap. A frame-invariantestimator replaces Bi with its orthogonal-conjugation invariants tr(Bi ), ∥Bi ∥2F , sorted eigvals(Bi ) and runs through the same kNN pipeline; the Procrustes-aligned and per-graph paths must agree on this target by construction. Both cross-checks track the headline ordering across the eight datasets in the study. 22
Datasets and results. We compute the calibrated FVE margin on a sweep of four synthetic stochastic block models with controlled diversity and four real graph benchmarks (spectre_sbm, enzymes, proteins, collab). The synthetic-diversity result shown in Figure 1c is monotone across all k and replicates under both noise models; on the real benchmarks the calibrated margin exceeds the calibration threshold on seven of eight datasets, with the failure being the designed null control (the diversity = 0 synthetic SBM). B.6
Compute resources
Hardware overview. The denoising experiments of Section 4 (Figure 1) and the denoising-metric runs feeding Figure 1c were trained on a single workstation with two NVIDIA RTX A5000 GPUs (24 GB GDDR6 VRAM each), 64 physical / 128 logical CPU cores, and ≈ 270 GB host RAM; each run is a single-GPU job. The DiGress generative experiments (Tables 3 and 7) were trained on Modal (modal.com) using its fast GPU tier, which provisions a single NVIDIA A100 (40 GB HBM2) per container with ≈ 32 GB host RAM. The spectral-diversity FVE estimation (Appendix B.5) is CPU-only and runs on a local workstation; the full sweep (8 datasets × 5 seeds × 2 frame modes × 2 noise types × 5 noise levels × 4 estimators × 4 values of k × real/null) completes in ≈ 60 minutes. Wall-clock and total compute (reported runs). The denoising panel (W&B projects graph-denoising-final-2 and graph-denoising-final-3, 127 runs total) ran in median ≈ 1.6 minutes and at most ≈ 32 minutes per run, for a cumulative budget of ≈ 6 single-GPUhours on the RTX A5000s. The eight reported DiGress configurations (four variants × two datasets) each accumulated ≈ 17.8 h of Modal A100 wall-clock at the data freeze, with preempt-resume across the 24 h container timeout, reaching ≈ 110k–120k optimiser steps on SPECTRE-SBM and ≈ 310k–500k on ENZYMES (the ENZYMES graphs are an order of magnitude smaller in node count, so the per-step cost is correspondingly smaller; see Table 7). Cumulatively the eight DiGress runs consume ≈ 142 single-A100-hours. Discarded compute. Initial exploration and iteration until the GDPO baseline was matched amounted to an additional ≈ 370 single-A100-hours, with no further details.
C
Proofs
C.1
Proof of Theorem 2
e ⊤ AU e tends to a deterministic matrix as Proof. We first show that for a given graph A, B := U n → ∞. We begin by writing B as: e ⊤ AU e =U e ⊤ U ΛU ⊤ U e B=U
(41)
Consider that A is low rank therefore we can write: r X A= λi ui u⊤ i
(42)
i=1
Thus we have: Bij =
r X
λl (e u⊤ u⊤ i ul )(e j ul )
(43)
l=1
According to Lemma 3 we have: lim Bii = lim
n→∞
n→∞
r X l=1
2 2 λl |e u⊤ u⊤ i ul | = λi lim |e i ui | + n→∞
r X
2 λl lim |e u⊤ i ul |
l=1,l̸=i
n→∞
(44)
The sum over l ̸= i tends to zero almost surely, thus we have: lim Bii = λi α(λi ) = λi (1 −
n→∞
23
σ2 σ2 ) = λi − 2 λi λi
(45)
for the off-diagonal elements we have: lim Bij = lim
n→∞
n→∞
r X
λl (e u⊤ u⊤ i ul )(e j ul ) = 0,
(46)
l=1
where since i ̸= j, one of the inner products will almost surely tend to zero regardless of the value of l. So, in summary we have for a given fixed graph A, B tends to a deterministic matrix as n → ∞: lim B = α(Λ)
(47)
n→∞
Furthermore, from Lemma 3 we have the deterministic relationship between the noisy and clean eigenvalues: 2 ei = λi + σ ρ(λi ) = λ (48) λi Thus we have: q e2 − 4σ 2 ei + λ λ i (49) λi = 2 Finally we can write: q q e2 − 4σ 2 ei + λ λ σ2 i e2 − 4σ 2 =1− = λ (50) α(λi ) = α 2 √ 2 i 2 ei + λ e −4σ 2 λ i
2
Finally we define the function ηout (·) as: e = ηout (λ)
(p e2 − 4σ 2 λ 0
e > 2σ if λ e ≤ 2σ if λ
(51)
Thus in the limit almost surely we have: e lim B = ηout (Λ)
n→∞
(52)
The following is a restatement of Theorem 2.1 and Theorem 2.2 from [1]. Lemma 3 (Leading-order overlap for spiked Wigner). Let Wn be an n × n real symmetric (or complex Hermitian) Wigner matrix with i.i.d. entries (up to symmetry) satisfying E[Wij ] = 0 and E[Wij2 ] = σ 2 /n for i ̸= j, with finite fourth moment. The empirical spectral distribution of Wn converges almost surely to the semicircle law on [−2σ, 2σ], with edge b = 2σ and Stieltjes transform √ Z 1 z − z 2 − 4σ 2 dµsc (x) = g(z) := , z ∈ R, |z| > 2σ, (53) z−x 2σ 2 where the branch of the square root is chosen so that g(z) → 0 as z → ∞. Let An be a deterministic (or random, independent of Wn ) symmetric matrix of fixed rank r, with spectral decomposition r X ⊤ An = λi ui u⊤ (54) i = U ΛU , i=1
where λ1 > λ2 > · · · > λr > 0 are fixed (distinct) and u1 , . . . , ur ∈ Rn are orthonormal. (Negative spikes are handled symmetrically.) e1 ≥ λ e2 ≥ · · · ≥ λ en be its eigenvalues with en := Wn + An , and let λ Define the perturbed matrix A corresponding orthonormal eigenvectors u e1 , . . . , u en . Let r+ ∈ {0, 1, . . . , r} denote the number of supercritical spikes, i.e., the number of indices i with λi > σ. Then the following hold almost surely as n → ∞: 24
(i) Outlier eigenvalue locations. For each i ∈ {1, . . . , r+ }, 2
σ a.s. ei − λ −→ ρ(λi ) := λi + = g −1 (1/λi ), λi
(55)
ei → 2σ. and ρ(λi ) > 2σ. For i > r+ , λ (ii) Eigenvector overlap — diagonal. For each i ∈ {1, . . . , r+ }, σ2 −1 = 1 − . λ2i g ′ (ρ(λi )) λ2i
a.s.
|⟨e ui , ui ⟩|2 −−→ α(λi ) :=
(56)
(iii) Eigenvector overlap — cross terms. For i, j ∈ {1, . . . , r+ } with i ̸= j, a.s.
⟨e ui , uj ⟩ −−→ 0. C.2
(57)
Proof of Lemma 1
We start by setting K−1 X
e l H (l) = I. Λ Q
l=0 (0)
(l)
This choice is feasible, for instance by taking HQ = I and HQ = 0 for all l ≥ 1. Next, choose (l)
(l)
(l)
each HK to be a constant diagonal matrix, i.e., HK = hk I. Under these choices, Eq. (14) reduces to the spectral filter !⊤ L−1 X (l) l f (U ) = U hk Λ U ⊤. l=0
Since Λ is diagonal, the matrix L−1 X
(l)
hk Λl
l=0
acts independently on each eigenvalue. Equivalently, it implements the pointwise polynomial filter w(λ) =
L−1 X
(l)
hk λl .
l=0
It remains to show that such a polynomial filter can approximate ηout . Although ηout is not analytic at the thresholds λ = ±2σ, it is continuous on any compact interval [a, b] ⊂ R. Therefore, by the Weierstrass approximation theorem [37], for every ε > 0 there exists a real polynomial P such that sup |P (λ) − ηout (λ)| < ε. λ∈[a,b]
Writing P (λ) =
L−1 X
(l)
hk λl
l=0 (l)
for sufficiently large L, we obtain a choice of coefficients {hk }L−1 l=0 such that the corresponding graph filter approximates ηout uniformly on [a, b]. This completes the proof. C.3
Proof of Proposition 1
We begin by expanding the loss using the fact that ∥M ∥2F = tr(M ⊤ M ): h i eW U e ⊤ )2 − 2A U eW U e ⊤ + A2 ℓ(W ) = E tr (U e ⊤U e = I and the cyclic property of trace: Further, using U 25
(58)
eW U e ⊤ )2 ] = tr[U e W 2U e ⊤ ] = tr[W 2 ] • tr[(U eW U e ⊤ ] = tr[W U e ⊤ AU e] • tr[A U So the loss reduces to: e ⊤ AU e where B = U
ℓ(W ) = E tr(W 2 ) − 2 tr(W B) + tr(A2 ) ,
(59)
which we can write as: ℓ(W ) = E tr(W 2 ) − 2 tr(W B) + tr(B 2 ) + tr(A2 − B 2 )
(60)
h i 2 2 2 ℓ(W ) = E ∥W − B∥F + ∥A∥F − ∥B∥F
(61)
The minimization reduces to: h i 2 W ∗ = argmin E ∥W − B∥F = EA, E [B]
(62)
W
h i 2 2 Define c := E ∥A∥F − ∥B∥F . Then the minimum achievable loss is: h i 2 ℓLA := ℓ(W ∗ ) = E ∥E[B] − B∥F + c = tr(Cov(vec(B))) + c C.4
(63)
Proof of Proposition 2 ℓ(f ) = E
e g(Λ) e U e⊤ − A U
2
(64)
F
Similarly to the linear case, we can write the loss as: 2 e − B + ∥A∥2 − ∥B∥2 ℓ(f ) = E g(Λ) F F F
(65)
The minimization reduces to:
∗
g (·) = argmin E g
2
e −B g(Λ)
(66)
F
Apply the tower property (law of iterated expectations): h i h h e − B∥2 = E e E ∥g(Λ) e − B∥2 E ∥g(Λ) F F Λ
ii e Λ
(67)
e is deterministic given Λ, e the inner conditional expectation is a pointwise squared-error Since g(Λ) e e over a constant c is the problem for each realization of Λ. The minimizer of E[∥c − B∥2F | Λ] conditional mean: h i h i e =E B Λ e =E U e ⊤A U e Λ e g ∗ (Λ) (68) In contrast to the minimizer in the linear attention class which was the unconditional mean W ∗ = E[B], e = E[B | Λ], e i.e., the conditional mean given the noisy with spectral attention the minimizer is g ∗ (Λ) eigenvalues. Then the minimum achievable loss becomes: h i e 2F + c ℓ⋆SA := ℓ(g ⋆ ) = EA, E ∥B − E[B | Λ]∥ (69)
h i e 2 ⇒ ℓ⋆SA = EΛe EB|Λe ∥B − E[B | Λ]∥ F +c | {z } e tr(Cov(vec(B)|Λ)) 26
(70)
C.5
Proof of Theorem 1
By the law of total variance: h i e + Cov(E[vec(B) | Λ]) e Cov(vec(B)) = EΛe Cov(vec(B) | Λ)
(71)
Taking the trace of both sides, we have: e ℓ⋆LA = ℓ⋆SA + tr(Cov(E[vec(B) | Λ]))
(72)
e ℓ⋆LA − ℓ⋆SA = tr(Cov(E[vec(B) | Λ]))
(73)
Thus, the improvement is:
which can also be written as: ℓ⋆LA − ℓ⋆SA = E C.6
2
e − E[B] E[B | Λ]
F
(74)
Proof of Lemma 2
ek = Proof. We work in the equal block case: mℓ = m for all ℓ, n = km, λmax = m. Write U Uk R + U⊥ S where U⊥ ∈ Rn×(n−k) collects the eigenvectors orthogonal to the principal eigenspace, ek ). The matrix S measures R ∈ Rk×k , S ∈ R(n−k)×k , and R⊤ R + S ⊤ S = Ik (orthonormality of U the eigenvector leakage out of the true principal eigenspace. We first characterize ℓbasis and ℓproj in terms of S. Characterization of ℓbasis .
Recall that 2
b−A ℓbasis = EE A
. F
(75)
In the equal block case Λk = mIk , so b − A = m(U ek U ek⊤ − Uk Uk⊤ ) = m(Pe − PU ) A
(76)
ek U e ⊤ is the projector onto the noisy principal eigenspace. Substituting U ek = Uk R + where Pe = U k ⊤ ⊤ ⊤ U⊥ S and using Uk Uk = Ik , Uk U⊥ = 0, U⊥ U⊥ = In−k , we expand ⊤ ⊤ ek U ek⊤ = Uk RR⊤ Uk⊤ + Uk RS ⊤ U⊥ U + U⊥ SR⊤ Uk⊤ + U⊥ SS ⊤ U⊥ ,
(77)
⊤ ⊤ Pe − PU = Uk (RR⊤ − Ik )Uk⊤ + Uk RS ⊤ U⊥ + U⊥ SR⊤ Uk⊤ + U⊥ SS ⊤ U⊥ .
(78)
and therefore
The four terms in (78) are mutually Frobenius-orthogonal, since their row and column spaces lie in either range(Uk ) or range(U⊥ ), which are orthogonal. Hence ∥Pe − PU ∥2F = ∥RR⊤ − Ik ∥2F + 2∥RS ⊤ ∥2F + ∥SS ⊤ ∥2F .
(79)
Using R⊤ R = Ik − S ⊤ S and the cyclic property of the trace, ∥RR⊤ − Ik ∥2F = tr((R⊤ R)2 ) − 2 tr(R⊤ R) + k = ∥S ⊤ S∥2F ,
(80)
∥RS ⊤ ∥2F = tr(R⊤ R S ⊤ S) = tr((Ik − S ⊤ S) S ⊤ S) = ∥S∥2F − ∥S ⊤ S∥2F ,
(81)
Substituting into (79) gives ∥Pe − PU ∥2F = 2∥S∥2F .
(82)
h i ℓbasis = m2 E ∥Pe − PU ∥2F = 2m2 E ∥S∥2F
(83)
Taking expectations,
27
b ⊤ with PU = Uk U ⊤ . Since A b= Characterization of ℓproj . The projected estimator is PU AP U k ⊤ ⊤ ek U e and U U ek = R, mU k
k
b U⊤ = m Uk (Uk⊤ U ek )(U ek⊤ Uk )Uk⊤ = m Uk RR⊤ Uk⊤ . PU AP
(84)
The clean matrix is A = m Uk Uk⊤ = Uk (mIk )Uk⊤ , so b U⊤ − A = m Uk (RR⊤ − Ik )Uk⊤ . PU AP
(85)
Since Uk has orthonormal columns, b U⊤ − A∥2F = m2 ∥RR⊤ − Ik ∥2F = m2 ∥S ⊤ S∥2F , ∥PU AP where the last equality is (80). Taking expectations, ℓproj = m2 E ∥S ⊤ S∥2F . The Improvement.
(86)
(87)
Combining (83) and (87), ∆ℓproj = ℓbasis − ℓproj = m2 E 2∥S∥2F − ∥S ⊤ S∥2F .
(88)
Since R⊤ R + S ⊤ S = Ik with R⊤ R ⪰ 0, we have S ⊤ S ⪯ Ik , so all eigenvalues of S ⊤ S lie in [0, 1]. Letting s1 , . . . , sk ∈ [0, 1] denote these eigenvalues, 2∥S∥2F − ∥S ⊤ S∥2F =
k X
si (2 − si ) ≥
i=1
k X
si = ∥S∥2F ,
(89)
i=1
and thus we have
∆ℓproj ≥ m2 E ∥S∥2F > 0. (90) Therefore, projecting onto the true principal eigenspace strictly decreases the denoising loss which concludes the proof. C.7
Proof of Theorem 3
b − PU and λmax = maxi mi = ∥A∥ b 2 . Then we have: Proof. Let E(α) = sm(αA) b α) − A = (PU + E) A b (PU + E)⊤ − A f (A; b U⊤ + PU AE b ⊤ + E AE b ⊤ b U⊤ − A) + E AP = (PU AP | {z } {z } |
(91)
δ1
δ0
b ⊤−A = where we used PU APU⊤ = Uk Uk⊤ (Uk Λk Uk⊤ )Uk Uk⊤ = Uk Λk Uk⊤ = A, so that PU AP U b − A)P ⊤ = δ0 . Expanding the squared Frobenius norm: PU ( A U b α) − A∥2F = ∥δ0 ∥2F + 2⟨δ0 , δ1 ⟩F + ∥δ1 ∥2F ∥f (A;
(92)
Taking expectations and noting E[∥δ0 ∥2F ] = ℓproj gives (93). ℓ(α) = ℓproj + 2 E[⟨δ0 , δ1 ⟩F ] + E ∥δ1 ∥2F Applying Cauchy–Schwarz to the cross term: q q q p |E[⟨δ0 , δ1 ⟩F ]| ≤ E[∥δ0 ∥F ∥δ1 ∥F ] ≤ E[∥δ0 ∥2F ] E[∥δ1 ∥2F ] = ℓproj E[∥δ1 ∥2F ] Thus we have:
(93)
(94)
q p ℓproj E[∥δ1 ∥2F ] + E ∥δ1 ∥2F
(95)
It remains to bound E[∥δ1 ∥2F ] and show that: q p 2 ℓproj E[∥δ1 ∥2F ] + E ∥δ1 ∥2F < ℓbasis − ℓproj
(96)
ℓ(α) ≤ ℓproj + 2
Bounding E[∥δ1 ∥2F ]. 28
b=U ek Λk U e ⊤ and PU = Uk U ⊤ , denoting Ω = U e ⊤ Uk ∈ Rk×k (which satisfies ∥Ω∥2 ≤ 1), Since A k k k ek : every term in δ1 factors through E U b U⊤ = (E U ek ) Λk Ω Uk⊤ , E AP b ⊤ = Uk Ω⊤ Λk (E U ek )⊤ , PU AE
(97)
b ⊤ = (E U ek ) Λk (E U ek )⊤ . E AE
(99)
ek ∥F + ∥E U ek ∥2F ∥δ1 ∥F ≤ λmax 2∥E U
(100)
(98)
Therefore, by sub-multiplicativity:
ek ∥F . Now we turn to bounding ∥E U ek ∥F . Write U ek = Uk + ∆Uk . Then we have: Bounding ∥E U ek ∥F = ∥E(Uk + ∆Uk )∥F = ∥EUk ∥F + ∥E∆Uk ∥F ∥E U
(101)
The Following Lemma allows us to bound ∥E∆Uk ∥F : b − A∥∞ := maxi,j |A bij − Aij | and γ = 1 − 2η. Assume Lemma 4 (Bound on EUk ). Define η = ∥A b are separated). Then γ > 0 (i.e., the noise is small enough that in-block and cross-block entries of A k 2 X X 1 (n − m ) ℓ . ∥EUk ∥2F ≤ e−2αγ + mℓ (102) m2ℓ mℓ′ ′ ℓ ̸=ℓ
ℓ=1
In the equal block case (mℓ = m, n = km), this simplifies to √ ∥EUk ∥F ≤ k k − 1 e−αγ .
(103)
Using Lemma 4 we can write in the equal block case: √ ek ∥F ≤ k k − 1 e−αγ + ∥E∆Uk ∥F ∥E U
(104)
Now we will write the LHS and RHS of the inequality (96) up to leading order in ∥S∥F . RHS of (96) to leading order. From Lemma 2 we recall, ℓbasis = 2m2 E ∥S∥2F , ℓproj = m2 E ∥S ⊤ S∥2F .
(105)
Since the eigenvalues of S ⊤ S lie in [0, 1], ∥S ⊤ S∥2F ≤ ∥S∥4F . Hence, to leading order in ∥S∥F , ℓbasis − ℓproj = 2m2 E ∥S∥2F + O E∥S∥4F . (106) ek ∥F . Decompose E = E1 + E2 with LHS of (96) to leading order. We first bound ∥E U E1 = sm(αA) − PU ,
b − sm(αA). E2 = sm(αA)
(107)
E1 is deterministic (independent √ of noise) and captures the finite-α bias of the softmax; a direct calculation shows ∥E1 ∥F = O( n e−α ), decaying exponentially in α. The noise term E2 is controlled by the following Lemma (See Section C.7.2 for proof). Lemma 5 (Linearized softmax bound). In the equal-block case, to leading order in ∥S∥F , √ ∥E2 ∥F ≤ 2 α ∥S∥F + O(∥S∥2F ).
(108)
Since ∥E1 ∥F decays exponentially in α (and is dominated by ∥E2 ∥F for αγ ≫ log k and ∥S∥F > 0), √ ∥E∥F ≤ ∥E1 ∥F + ∥E2 ∥F = 2 α ∥S∥F + O(∥S∥2F ). (109) 29
Furthermore, ∥∆Uk ∥F = ∥S∥F + O(∥S∥2F ) to leading order (the within-eigenspace component ∥R − Ik ∥F is O(∥S∥2F )). Substituting into (104), √ √ ek ∥F ≤ k k − 1 e−αγ + 2 α∥S∥2 + o(∥S∥2 ). ∥E U (110) F F Assume αγ ≫ log k so the exponential term is negligible; then √ ek ∥F = 2 α∥S∥2 + o(∥S∥2 ), ∥E U F F
(111)
ek ∥2 = O(∥S∥4 ) is higher order. Plugging into (100) with λmax = m, and the quadratic term ∥E U F F √ ek ∥F + ∥E U ek ∥2 = 2 2 mα∥S∥2 + o(∥S∥2 ), ∥δ1 ∥F ≤ m 2∥E U (112) F F F so
E∥δ1 ∥2F ≤ 8m2 α2 E∥S∥4F + o E∥S∥4F .
Since
p
p ℓproj ≤ m E∥S∥4F (using ∥S ⊤ S∥2F ≤ ∥S∥4F ), the cross term satisfies q √ p 2 ℓproj E∥δ1 ∥2F ≤ 4 2 m2 α E∥S∥4F + o E∥S∥4F .
Combining,
√ LHS of (96) ≤ m2 α 4 2 + 8α E∥S∥4F + o E∥S∥4F .
(113)
(114)
(115)
Resulting condition. Combining (106) and (115), the bound (96) holds to leading order whenever E∥S∥4 √ F < 2. (116) α 4 2 + 8α E [∥S∥2F ] E ∥S∥2F . Then the condition (116) becomes E∥S∥4F √ α 4 2 + 8α < β. √ Solving the quadratic 8α2 + 4 2 α − β = 0, the condition holds for α ∈ (0, α+ ) where √ p 2 α+ = −1 + 1 + β . 4
Denote β := 2
(117)
(118)
Compatibility of the two conditions on α. The proof so far rests on two conditions on the parameter α: (A) α ∈ (0, α+ ), so that the LHS leading-order bound (115) is dominated by the RHS leadingorder bound (106) (this is the bound (117)). √ (B) αγ ≫ log k, so that the exponential term k k − 1 e−αγ in (104) is negligible compared to the noise term. These conditions pull in opposite directions: (A) caps α from above, while (B) requires α to grow at least like log k. To show that they can be met simultaneously, we make the following assumption on the noise. Assumption 2. There exists s such that ∥S∥F ≤ s almost surely, with 1 1 s ≪ min , . m log k
(119)
b − A∥∞ is not an independent quantity: by the entry-wise bound ∥M ∥∞ ≤ ∥M ∥F Note that η = ∥A √ b together with ∥A − A∥F = m 2∥S∥F from (83), √ √ b − A∥F = m 2 ∥S∥F ≤ m 2 s. η ≤ ∥A (120) 30
Therefore Assumption 2 caps both ∥S∥F and η. The two bounds in (119) will turn out to control γ (via η ≲ ms) and the exponential term (via αγ ≳ 1/s), making (A) and (B) compatible. Lower bound on α+ . Since ∥S∥2F ≤ s2 a.s., we have the pointwise bound ∥S∥4F ≤ s2 ∥S∥2F . Taking expectations, E∥S∥2F 2 E∥S∥4F ≤ s2 E∥S∥2F =⇒ β = 2 ≥ 2. (121) 4 E∥S∥F s √ √ Since = α+ = 42 ( 1 + β − 1) is monotone increasing in β we can write: √ p √ √ √ 1 α+ ≥ 42 − 42 , (122) 1 + 2/s2 − 1 ≥ 42 s2 − 1 = 2s where we used Assumption 2.
p
1 + 2/s2 ≥
√
2/s. Thus the cap α+ is at least of order 1/s, which is large under
Lower bound on γ. Combining γ = 1 − 2η with (120), √ γ ≥ 1 − 2m 2 s. (123) √ The condition ms ≪ 1 from Assumption 2 ensures 2m 2 s ≤ 1/2 for s small enough, hence γ ≥ 1/2. Choosing α⋆ to satisfy both (A) and (B). Set α⋆ :=
1 . We verify each condition: 4s √
1 1 • Condition (A): α⋆ < α+ . By (122) this reduces to 4s < 2s − 42 , i.e., s < √12 , which is automatic since s ≪ 1/ log k.
• Condition (B): α⋆ γ ≫ log k. By (123), once ms ≪ 1 so that γ ≥ 1/2 we have, 1 1 α⋆ γ ≥ 4s · 21 = 8s ≫ log k,
(124)
where the last step uses s ≪ 1/ log k. This is precisely why both parts of (119) are needed: ms ≪ 1 guarantees γ stays bounded away from 0, and s log k ≪ 1 then makes α⋆ γ large compared to log k. Hence α⋆ lies in (0, α+ ) and makes the exponential term in (104) negligible, so all the leading-order bounds derived in the proof apply at α = α⋆ . Conclusion. At α = α⋆ , the condition (117) holds strictly, which by (115) and (106) is equivalent to the gap bound (96). Therefore ϵ(α⋆ ) = ℓsoft (α⋆ ) − ℓproj < ℓbasis − ℓproj = ∆ℓproj ,
(125)
proving the theorem. Translation to the noise scale. We close by translating Assumption 2 into a condition on the e − A. In the equal-block case the spectral gap of A between the k-th adjacency-level noise E := A principal eigenvalue and the trivial part of the spectrum equals ∆ = m. By the Davis–Kahan theorem (in sin Θ form), ∥P⊥ E Vk ∥F ∥E∥F ∥S∥F ≤ ≤ . (126) ∆ m Squaring and taking expectations, σ 2 = E∥S∥2F ≤
E∥E∥2F . m2
(127)
Translating the two parts of (119) (with s2 scaling like E∥E∥2F := σ 2 , assuming concentration of ∥S∥2F around its mean): • s ≪ 1/m becomes σ 2 ≪ 1/m2 , i.e., E∥E∥2F ≪ 1. 31
• s ≪ 1/ log k becomes σ 2 ≪ 1/ log2 k, i.e., E∥E∥2F ≪ m2 / log2 k. Combining, Assumption 2 holds provided E∥E∥2F ≪ min 1,
m2 log2 k
.
(128)
which is the assumption stated in the theorem. 2 For independent edge flips with probability p, E[Eij ] = p(1 − p) for each entry, so E∥E∥2F = n(n − 1) p(1 − p) ≈ n2 p. Substituting and using n = km, 1 1 p ≪ min 2 , 2 . (129) n k log2 k
C.7.1
Proof of Lemma 4
Proof. We bound (Euℓ )i separately for i in-block (i ∈ Bℓ ) and cross-block (i ∈ Bℓ′ , ℓ′ ̸= ℓ). Write b = PU + E and Zi = Pn′ eαAbij′ for the softmax normalizer. S = sm(αA) j =1 Case 1: i ∈ Bℓ . Since
P
/ Bℓ : j Eij = 0 and (PU )ij = 0 for j ∈ X
Eij = −
j∈Bℓ
X
Eij = −
j ∈B / ℓ
X
Sij .
(130)
j ∈B / ℓ
bij ≤ η (cross-block), so eαAbij ≤ eαη . For j ′ ∈ Bℓ : A bij ′ ≥ 1 − η (same-block), so For j ∈ / Bℓ : A α(1−η) Zi ≥ mℓ e . Therefore X
Eij ≤
j∈Bℓ
n − mℓ −αγ (n − mℓ ) eαη = e mℓ mℓ eα(1−η)
(131)
−αγ ℓ . and |(Evℓ )i | ≤ n−m 3/2 e mℓ
P P Case 2: i ∈ Bℓ′ , ℓ′ ̸= ℓ. Now (PU )ij = 0 for all j ∈ Bℓ , so j∈Bℓ Eij = j∈Bℓ Sij . For j ∈ Bℓ : bij ≤ η (cross-block relative to i). For j ′ ∈ Bℓ′ : Zi ≥ mℓ′ eα(1−η) . Thus A X
Sij ≤
j∈Bℓ
mℓ eαη mℓ −αγ e = mℓ′ mℓ′ eα(1−η)
(132)
√ m
and |(Evℓ )i | ≤ m ′ℓ e−αγ . ℓ
Combining. We have 2 X 1 (n − m ) ℓ . (Evℓ )2i ≤ e−2αγ + mℓ m2ℓ m ℓ′ ′
∥Evℓ ∥2 =
X
(Evℓ )2i +
i∈Bℓ
X X ℓ′ ̸=ℓ i∈Bℓ′
(133)
ℓ ̸=ℓ
Summing over ℓ = 1, . . . , k gives (102). Setting mℓ = m and n = km yields (103). C.7.2
Proof of Lemma 5
Proof. Let σ : Rn → Rn denote the row-wise softmax with Jacobian J(x) = diag(σ(x)) − σ(x)σ(x)⊤ . For row i ∈ Bℓ of A, σ(αAi,: ) = a 1Bℓ + b 1Bℓc with a = 1/(m + (n − m)e−α ) and b = a e−α . The eigenvalues of J(αAi,: ) are 0 (on 1), a (multiplicity m − 1, on sum-zero perturbations within Bℓ ), b (multiplicity n − m − 1, on sum-zero perturbations within Bℓc ), and nab (on span{(n − m)1Bℓ − m 1Bℓc }). For α ≥ 0, a ≥ b and a ≥ nab, so 1 ∥J(αAi,: )∥2 = a ≤ m .
32
(134)
Taylor-expanding σ around αAi,: row-wise (the second-order remainder is controlled by the uniformly bounded Hessian of softmax), squaring, and summing over rows, 2 4 2 4 α2 b b b ∥E2 ∥2F ≤ α2 max ∥J(αAi,: )∥22 ·∥A−A∥ F +O(∥A−A∥F ) ≤ m2 ∥A−A∥F +O(∥S∥F ). (135) i
√ b − A∥F = m 2∥S∥F in (83). The claim follows from ∥A C.8
Edge-flipping noise
eij = Aij with prob. 1 − ε and For Digress noise, we consider the edge-flipping model where A e − A. A direct computation gives eij = 1 − Aij with prob. ε, so that A e = A + E1 with E1 = A A ⊤ e E[A | A] = (1 − 2ε)A + ε11 , hence e = (1 − 2ε)A + ε11⊤ + Ξ, A
(136)
e − E[A e | A] has zero mean independent entries and is thus a Wigner-type matrix. where Ξ := A
D
Related Work
D.1
Optimization-based graph denoising
A large body of work formulates graph denoising as a model-based inverse problem in which the clean graph is obtained as the minimizer of a cost regularized by hand-crafted structural priors, with no learned mapping involved. From a network-statistics angle, [8] invert in closed form a convolutional model of direct and indirect edge effects, while [46, 15] recover a clean adjacency under Type-I/II edge errors, low-rank parameter matrices, or unlabeled noisy samples, respectively. Within the graph signal processing (GSP) framework, the topology is denoised jointly with a process defined on it: [38] recover a graph shift operator from possibly corrupted spectral templates, and [33, 34, 42] progressively extend this idea to robust filter identification and blind deconvolution under joint perturbations of inputs, filter, and topology. A third and particularly influential family exploits the low-rank, sparse, and smooth nature of real-world graphs, with Pro-GNN [12] as the canonical formulation and a number of follow-ups [47, 51, 45] that improve scalability and avoid over-smoothing through truncated-SVD reparametrizations, framelet regularizers, or feature-driven matrix factorization. Related approaches obtain the clean graph from low-rank motifs [24] or via iterative Fourier thresholding of the adjacency [9]; in the same spirit, [41] extends the Pro-GNN-style joint optimization by replacing its low-rank and sparsity priors with a GSP-style denoising regularizer that is alternated with gradient updates of the downstream GNN. D.2
Graph denoising via learned estimators
A complementary family of methods abandons the optimization viewpoint altogether and instead trains a parametric mapping from a noisy graph to a clean one, so that denoising amounts to a forward pass through a neural network rather than the solution of an instance-specific inverse problem. The first group of such methods uses the learned denoiser as a component of, or a preprocessing for, a downstream GNN. GADPN [5] performs the denoising step itself with a non-learned rank-adaptive SVD whose rank is chosen by Bayesian optimization, and feeds the cleaned adjacency to a standard GNN classifier. UGD [49] couples a non-parametric high-order proximity score for edge pruning with a GCN-based graph autoencoder that reconstructs corrupted features, and alternates between the two. RS-GNN [4] parametrizes the denoiser as an MLP edge predictor that re-weights the adjacency from pairs of node features and is trained jointly with a downstream GCN, while SLAPS [7] pairs an MLP-kNN graph generator with a separate GNN denoising autoencoder that recovers masked features through the learned structure. A second group places the parametric denoiser at the core of a denoising diffusion or flow-matching model, where a forward process gradually corrupts a clean graph and the learned denoiser is applied iteratively to invert it. Mask-GVAE [19] is the earliest of these, with a partition-based GCN variational autoencoder that performs blind denoising without paired supervision. GDSS [14] parametrizes the score of a system of SDEs over node features and adjacency with a graph convolution / graph transformer backbone, while DiGress [44] introduces a discrete diffusion in which a graph transformer is trained to predict the clean graph from a noisy input 33
at every step; GruM [13] and DeFoG [32] reuse essentially the same graph transformer architecture but replace the noise-prediction objective by, respectively, endpoint prediction in a diffusion mixture and discrete flow matching. NetDiff [26] augments the DiGress-style graph transformer with crossattentive modulation tokens to enforce global topological constraints in ad-hoc network generation, DiffSP [23] repurposes such graph diffusion models as adversarial structure purifiers on top of a GCN classifier, and SGDM [43] operates at the subgraph level and is in fact backbone-agnostic, instantiated on top of DiGress, GDSS or EDGE. D.3
Spectral graph transformers
A line of research orthogonal to standard message-passing GNNs builds graph neural architectures by routing the spectrum of the graph Laplacian through Transformer-style modules. The earliest works inject the spectrum as input features. SpGAT [11] first constructs spectral node features from the graph Laplacian eigenvectors and eigenvalues with an MLP on top. These features are then used as input for a GCN, which performs node-wise classification by assigning a label to each surface vertex. SAN [18] constructs spectral positional features from the graph Laplacian spectrum and adds them to the node features. These enriched features are then processed by a fully connected Transformer. The Graph Transformer of [6] is an earlier instance of this same template, using truncated Laplacian eigenvectors directly as a positional encoding for a sparse-attention Transformer. This idea of using spectral information as feature is also investigated in [31] by processing Laplacian eigenvalues with an MLP and usesing the result to initialize the Transformer’s global [CLS] token, with the resulting architecture still being a graph Transformer. A second sub-line removes the eigenvector ambiguities (sign flips, basis rotations within an eigenspace) before they reach the Transformer. SignNet and BasisNet [21] are parametric encoders that produce sign- and basis-invariant embeddings of the eigenvectors, and are routinely plugged in as the positional-encoding module of a downstream graph Transformer. GIST [35] addresses the same problem from a different angle: it builds random spectral features by feeding Gaussian noise through a precomputed graph filter, and then uses the inner product matrix of the resulting features as a reweighting mechanism. Specifically, the architecture is a Transformer whose attention scores are reweighted by this spectral inner product matrix. A third subline uses the Transformer not as a pose-processing module of the spectrum but as the parametrization of a graph filter itself. Specformer [2] learns a graph filter by feeding the graph eigenvalues into a Transformer, which produces frequency responses, and then converts those responses back into a graph operator using the eigenvectors. This learned operator is then used as the propagation layer inside a GNN, so the rest of the model behaves like a graph neural network for prediction. PolyFormer [25] avoids eigendecomposition altogether by representing each node with a sequence of polynomial-basis tokens of the Laplacian, and then learning a node-wise filter through self-attention over those tokens. Eigenformer [10] pushes this idea further by dispensing with explicit positional encodings and instead designing a spectrum-aware attention mechanism whose biases depend directly on the Laplacian spectrum, so that the Transformer block itself acts as a learnable spectral operator.
34