You Only Spectralize Once: Taking a Spectral Detour to Accelerate Graph Neural Network
Authors: Yi Li
Zhichun Guo
Guanpeng Li
Bingzhe Li
Venue: NeurIPS 2025 poster ()
Keywords: Graph Neural Network
Acceleration
Compressed Sensing
Graph Fourier
Primary area: deep_learning

Abstract: Training Graph Neural Networks (GNNs) often relies on repeated, irregular, and expensive message-passing operations over all nodes (e.g., $N$), leading to high computational overhead. To alleviate this inefficiency, we revisit the GNNs training from a spectral perspective. In many real-world graphs, node features and embeddings exhibit sparse representation in the Graph Fourier domain. This inherent spectral sparsity aligns well with the principles of Compressed Sensing, which posits that signals sparse in one transform domain can be accurately reconstructed from a significantly reduced number of measurements. This observation motivates the design of a more efficient GNNs that operates predominantly in compressed spectral subspace. Thus, we propose You Only Spectralize Once (YOSO), a GNN training scheme that performs single Graph Fourier Transformation to project features onto a learnable orthonormal Fourier basis, retaining only $M$ spectral coefficients ($M \ll N$). The entire GNN computation is then carried out in reduced spectral domain. Final full-graph embeddings are recovered only at output layer by solving a bounded $\ell_{2,1}$-regularized optimization problem. Theoretically, drawing upon Compressed Sensing theory, we prove stable recovery throughout training by showing that the projection onto our learnable Fourier basis can satisfy the Restricted Isometry Property when $M=\mathcal{O}(k \log N)$ for $k$-row-sparse spectra, acting as the measurement process. Empirically, YOSO achieves an average 74\% reduction in training time across five benchmark datasets compared to state-of-the-art methods, while maintaining competitive accuracy.

You Only Spectralize Once: Taking a Spectral Detour to Accelerate Graph Neural Network
Yi Li", Zhichun Guo Guanpeng Li", and Bingzhe Li University of Texas at Dallas
@ University of Washington
University of Florida
(Yi.Li3 bingghe. @eli@eeuuallll @utdallas.edu
zeguo uw.edu liguanpeng @ ufl.edu
Abstract
Training Graph Neural Networks (GNNs) often relies on repeated, irregular, and expensive message-passinng operations over all nodes (e.g., N),, leading high computational overhead. To alleviate this inefficiency, we revisit the GNNs training from the spectral perspective. Node features and embeddings in many graph exhibit sparse representation in Graph Fourier domain. This inherent sparsity aligns well with the Compressed Sensing principles, which posits that sparse signals can be accurately reconstructed from significantly fewer measurements (e.g.. M and M < N). This observation motivates designing efficient GNNs that operates predominantly in compressed spectral subspace. In this paper, propose You Only Spectralize Once (YOSO), a GNN training scheme that first performing a single projection of features onto learnable orthonormal Graph Fourier basis Ur. and after compressed sensing is used, retaining only M spectral coefficients where M & N. The entire GNN computation then performs in this reduced/comppeesee spectral domain. Finally, the full graph embeddings are recovered back to original domain output layer by solving compressed sensing bounded bg, regullarized optimization problem. Theoretically, drawing upon the compressed sensing theory, we prove that stable recovery by showing that this whole process satisfy the Restricted Isometry Property when M Okk(log N/k)). Empirically, YOSO achieves average 74% training time reduction across five benchmark datasets compared to state-of-the-art baseline schemes, while maintaining the competitive model accuracy.
Introduction
Graphs effectively capture the relational structures in diverse data 27 39] offering advantages
leverage this via localized message passing (LMP) [19], achieving state-of-the-aar (SOTA) performance in tasks such as link prediction [25), (67 and node classification [71] 69]. However, LMP on the large-scale graphs leads prohibitively long training time, e.g., billion-scale graphs can demand hours or even days of computation 338 58 To mitigate these costs, prior works explored the strategies like graph
over Euclidean representations 7 Graph Neural Networks (GNNs) [36 28 72 15)
pruning/condeesstion [50] 60 and various sampling techniques [ 31
66 [5]. By discarding
parts of the graph limiting nodes neighbors exploration, these methods might miss crucial relational
information, thus often leading notable degradation in model accuracy 12 Consequently, GNN training faces fundamental efficiency- accuracy trade-off.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

1,00
4000
YOSO
Total Tminnng Time (5)
@ Non-Compuuttion Time Computation Time
Model Accuracy
0.98
(Micro-F1)
0.96
GOGAAAANTRRGGE
3000
Goophags CanNsGNN
0.94
2000
0.92
1000
0.90
1000
2000
3000
1000
Training (s)
VG
9_6G s_Rw
(a) Total training time V.S. Model accuracy
(b) Total training time breakdown
Figure 1: Total training time and model accuracy of different schemes, including GraphSage (GS) 28 VR-GCN (VG) [2]. FastGCN (FG) [3]. AS-GCN (AG) BM.. LADIES (LA) [72), Cluster-GCN (CG) [5] and two different versions of GraphSAINT (S EG and $_RW) [66). on Reddit [28]. Total training time is broken into two parts: (1) Non-computation time, includes mini- batih construction (e.g., indexing. sampling) and data transfer between host and device memory; and (2) Computation time, which covers computation the GPU (i.e., forward and backward propagation, and weight updates). The seven-pointed red star marks the desired operational point targeted by this paper.
Fig. la illustrates this trade-off: methods such GraphSAINT [66] and AS-GCN [1 achieve high accuracy with comprehensive neighborhood data but suffer long training times (top-right of Fig. ITp. Conversely, schemes like FastGCN [3] and LADIES 72 offer speed-ups but sacrifice accuracy (bottom-left of Fig. Ta) due to the information loss from aggressive sampling [55]. These existing methods form Pareto frontier: reducing non-computational overheads (e.g., host-side sampling, host-device data migration etc.) impairs accuracy, while preserving accuracy inflates these overheads. We performed breakdown analysis, as illustrated in Fig. Tb The results reveal that non-computation time dominate the overall training time relative to the computation time (i.e., computation in devices), highlighting a key opportunity for optimization.
Our goal is to transcend this trade-off, achieving both high accuracy and low training time (reaching seven-pointed red star indicated in Fig. Tap. To this end, draw inspiration from the Graph Fourier analysis (22 44 [7] where node features are viewed as signals defined on graph structure [45] Orthonormal eigenvectors of graph Laplacian 442 21 24 366 (e.g., Lymm) serve the fundamental frequency components [35 61). Graph Fourier transform matrix U (composed of these eigenvectors) projects original features X into spectral domain via U X (46). This initial transformation is, in principle, infformttion-preserviiii features and intermediate GNN embeddings) exhibit spectral sparsity [32 48). This means that the most important information in these graph signals can be captured by just a few dominant frequencies or spectral components 12, while many others carry little significant information. Retaining only these critical coefficients is principle central to Compressed Sensing (CS). CS posits that if a signal sparse in some domain, we don't 't need to measure all its components to reconstruct accurately; a much smaller number of "smart" measurements can suffice to recover the essential information. By operating only on these few critical spectral coefficients, we could drastically reduce the amount of data the GNN needs to process, store, and move, directly tackling the non-conputational bottlenecks (Fig. Tbb and potentially speeding up the GNN's computations themselves.
44 42 A crucial observation is that graph signals (both initial
However, directly integrating Graph Fourier and compressed sensing principles into GNN training presents several significant challenges: (a) Prohibitive U Construction Cost: To use Graph Fourier, it is typically need a fixed U, which involves eigendecomposition of graph Laplacian (e.g.. Lyym) that typically has complexity of (NN3) 53 5) where N is total number of nodes in the graph. This makes pre-computing suitable U substantial overhead itself for large graphs 32 57 48 14).
(b) Inaccurate Reconstruction from the Spectral Domain: GNNs iteratively apply the non-linear activation functions. If transform embeddings into spectral domain and later convert them back to original domain (for performing the downstream task), but only use a simple inverse transform (c.g.. )- thus, these non-linearities prevent perfect recovery of original embeddings. This information loss can be accumulated layer-by-laye and degrade final model accuracy 2. (c) Costly Layer- wise Sensing and Recovery: While compressed sensing [00 9 can, in principle, help achieve more accurate reconstruction from fewer measurements and potentially counteract some effects of non-linearities 63 62] applying the full sequence of Graph Fourier transform, compressed sensing measurement and recovery at every GNN layer to maintain embedding fidelity would introduce its own significant computational overhead, negating any time benefits we try to introduce. To address these challenges, we propose the YOSO (You Only Spectralize Once).

---

To overeome challenge of fixed basis U, YOSO does not cre-cot it but using a learnable U which is learned as part of the GNN training process via backpropagation. Crucially, this potentially complex transformation is performed only once on initial input features. For compressed sensing (CS) to be effective, data needs to be sparse in chosen transform domain, YOSO's unified training objective includes the terms (in total loss 1otal that encourage Ug to naturally induce sparse representations from the input data, denoted X = H RN where d is the dimension of feature vector. After this one-time Graph Fourier transformation U X and the selection of only M (where M < N) significant spectral coefficients, all subsequent GNN computations proceed entirely in this highly compact, -fddimensional, CS-informed spectral domain. To tackle inaccurate reconstruction and costly layer-wise sensing, YOSO applies CS principles for the final output reconstruction only. It employs a fixed sensing matrix + (designed to work effectively with the learned U, and satisfy key condition called the Restricted Isometry Property (RIP) [I0], which ensures stable recovery from few measurements). Then, a CS recovery algorithm (bounded ε2 .rgguulaarzzziion reconstructs the full-graph node embeddings from the GNN's compact M -dimensiional output. This one-time spectral projection at the input and one-time CS-based reconstruction at the output layer significantly reduces computational complexity. Our main contributions are:
We propose YOSO, a GNN training scheme that leverages a once-per-eeeeee per--enn- learnable orthonormal spectral transformation to operate in Compressed Sensing-informee compressed spectral domain, thereby mitigating expensive computations (e.g., full message passing), circumventing complex spatial sampling, and significantly reducing training time while maintaining competitive accuracy.
Experiments show YOSO reduces training time by ~74% on average, preserving accuracy compa- rable to SOTA methods, with robust performance and high-fidelity embedding reconstruction.
2 Background and Preliminaries
Graph Neural Networks. GNNs operate on graph G = (V, A, X). where V = (wi,................. ux) is the node set, E C V x the edge set, A E RNN the adjacency matrix, and X E Nxd is node feature matrix. GNNs learn node embeddings H E R Nxd for layer 1 parameterized by (00) via: H = fac (I-1,,, A), for layer / = L...., L. We denote H = X.
Graph Fourier (GF) Analysis. One important concept in GF Analysis is GF transform, which often uses graph symmetric normalized Laplacian Lym
[7 36 14, where D the diagonal degree matrix. Lyy has eigendecomposition Lyym U AUT T where E NxN is an orthonormal matrix of eigenvectors (GF basis) and A = diag (Jo.. ...; AN 1 contains corresponding non-negative eigenvalues (graph frequencies). The GF transform of H is ( (U+)) H (1)
D AD
with the inverse (1)
N x (called spectral coefficients) is sparse for real- 29 32 meaning that most energy or information is store in few coefficients, reconstruction.
( (1) ( H E
world graphs 2
14 17
enabling compressed sensing-bast
Compressed Sensing (CS) can reconstruct signals with few measurements, based on two prerequi- sites 110. First, the reconstructed signals need to exhibit sparsity in the transform domain (9. and Graph Fourier analysis provides guarantee for this: k-row-sparse H (1) in transform domain. The sec- ond is Restricted Isometry Property (RIP). CS acquires compressed measurements T R x using the sensing matrix (() E R MxN (M < N) such that ( ( (1) (0) ()) Operating on the measurements (1) e xx00 instead of (!) E R-
N xd is more efficient since M & N 15 22]. A successful recovery of F from T()) relies on the matrix ((), defined as Φ (4) ()) ( should satisfy the Restricted Isometry Property (RIP) [T0] with a constant &2 E (0,1) 1)
for all k-row-sparse (1)) E (xd") (1 ]x] 1 <
i ( | (1+ 6z) ( 11 If RIP
holds, ( can be estimated from measurements T This estimation, denoted ! is found by an optimization problem that promotes row-sparsity, commonly via 6,, -inimizzation:
H (1) Solver(T T " x) A argmin to (; [ 1
A "0 1| +
2,1
(1)
Solver(-) represents a determinative algorithm like FISTA 4 adapted for the f,, - and À is a regularization parameter. The asterisk in H (0) denotes this is an estimated approximation of the
true sparse coefficients. The f,, norm is H (0) 112,1 Σ (1) ||2 (where (0) is the i-th row
3

---

of H)) Once the specific H value is solved, then the original domain signal can be computed and reconstructed as H = U Crucially, the number of measurements M required for successful recovery is primarily dictated by the sparsity level k (e.g., M = (kklog(N/k))) not the number nodes N (see Appendix B.2 for the detailed statement).
Benefits and Obstacles of Integrating GF and CS in GNNs
Integrating Graph Fourier transform and compressed sensing layer-wise in GNNs seems promising, since training process can be performed with dimension M N) instead of original N. node
embeddings H E Ig xxx at each GNN layer could be represented sparsely via a U E RRNN
as H U " one could use a sensing matrix & ((() compress: T()) a H E Rx
One potential successful recovery would involve solving Eq 1 and (t) ( is required to satisfy Restricted Isometry Property (RIP). This offers two theoretical benefits:
Benefit I: Reduced Data Representation. Compressed H < Nxd") to T()) Rxx where
M < N, could reduce computational/memoryy needs, if subsequent GNN computation could be adapted to work directly with ( e.g., use T as GNN input to perform the forward propagation. Benefit II: Faithful Signal Recovery. Compressed sensing provides the guarantee via Restricted
Isometry Property, such that ())) E N xx can accurately recovered from T(), This suggests that the full expressive power of the original embedding space could be restored for downstream tasks, for example, node classification and link prediction.
However, integrating Graph Fourier and compressing sensing with layer-wise GNN (superscript (4)), aligning with the above description (ideal scenario Eq 2
is impractical due two obstacles:
H (!) fecr (1)c))
Obstacle I: Prohibitive Costs and Complexity of Layer-Specific Transformations. A layer-wise application of Graph Fourier and compressed sensing would necessitate distinet orthonormal basis U()) and corresponding sensing matrix b(() for each GNN layer 1. Determining the optimal (?)) typically requires costly eigendecomposstiions (O(N3) complexity [53] 5). as a single fixed basis unlikely to maintain the sparsity for embeddings across all non-linear GNN layers. Furthermore, designing and verifying L distinct (()) matrices to pair with each (+)) and satisfy the Restricted Isometry Property adds significant complexity, rendering this layer-by-layer approach impractical. This motivates strategy using single, efficiently obtained (e.g., learnable) transformation and universal sensing matrix, denoted 4 (without superscript l).
Obstacle II: Impracticality of Layer-Wise Reconstruction and the Resulting Efficieney-Accuracy Dilemma. Even layer-specific transformations were feasible, reconstructing full N-dimensional embeddings from compressed measurements at each of the L total GNN layers is computationally prohibitive. Solving the required optimization problem (Eq. ( repeatedly (e.g., with complexity related to O (NNd per layer (41) would negate any efficiency gains from compressed format.
Therefore, a successful integration should reap the benefits of compression without paying the penalty of expensive reconstructions at every layer. This necessitates a framework that carefully balances the depth of spectral processing against the fidelity of information required for high GNN performance, ideally through a single and efficient transformation and reconstruction pipeline.
4 Methodology
We present the design of YOSO in this section. Section 4.1 introduces YOSO's overall architecture and computational workflow. Section |4.2 specifically describe how YOSO Icarns U, (addressing Obstacle I) and performs GNN computations (addressing Obstacle II). Finally, the universal sensing matrix + (further addressing Obstacle I) details in Section 4.3
4.1 Overall Process of YOSO
As illustrated in Fig. 2 YOSO introduces novel GNN training pipeline that integrates a learnable transformation U2 with compressed sensing principles. The core idea is that to project features into learnable, sparse spectral domain defined by Uz. perform GNN computations significantly

---

Graph Domain
Spectral Domain
Graph Domain
T g
T U
I(W)) g.xddor
Gruph Fourier(U,)
Compressed Sensing(#)
GNN Message Passing
Reconstruct
Overall architecture of YOSO. The model first uses a learnable Graph Fourier transform Ug to project the input H (0) E [g xd into a sparse representation H E IR Then applies fixed sensing matrix & E RM x (M < .N) to compress the features. YOSO perform the Message Passing directly the compressed M d representation T()), At output layer, it reconstructs the full-resolution embeddings (1)) I2-Nx to produce task-specific predictions. We should note that, during the training process, Graph Fourier transform U/ is Icarnable, while the compressed sensing matrix & remains fixed.
Figure 2:
compressed M-row representation T (2 = [0, 1,... LJ) within this domain, and then reconstruct the full N --dimensional embeddings H only at the output layer for task-specific predictions and loss calculation. This approach contrasts with the traditional GNNs by primarily operating in a much lower-dimensional space. The key stages are:
Initialization. Two sets of parameters are initialized: (1) The learnable orthonormal transformation matrix U2 E N This matrix aims to form Graph Fourier basis where feature matrix become sparse. Thereby U2 can be initialized as a random orthogonal matrix (c.g., via QR decomposition of Gaussian matrix) or using other Stiefel manifold initialization techniques [Л]. and (2) The GNN model weights e (W()) Rd xa00 H= These are initialized using standard practices.
Learnable Spectral Projection (via Up). The input feature matrix (0) E R xd is projected into the spectral domain defined by the current learnable basis Uz:
(0) U, (
where (0) E R.Nxd represents the spectral coefficients of features ( To overcome the high cost of using fixed U (as discussed in Obstacle I, Section 3), in YOSO, U, is learned jointly with the GNN parameters O, subject to an orthonormality constraint (U, U₂ = I). This learning process (detailed in Section 4.2) guides U2 to become a suitable basis that can project node signals (input features and, implicitly, subsequent embeddings) into effectively sparse representations, facilitating efficient compression and high-fidelity reconstruction.
Compressed Measurement (via 2). After obtaining the spectral representation (0), YOSO applies a carefully designed sensing matrix T E TR M (where M < N) to generate a compressed version of these spectral coefficients, which forms the initial input (D) for the GNN layers:
T
(o) E RMdd is a compressed feature matrix, representing M measurements or intuitively, a sketches of N spectral components. The construction of & is detailed in Section 4.3 The sequence
()) U. ()) (0) $1), (T))) is performed at the beginning of each training iteration, as U2 updates.
Forward Propagation in Compressed Domain. Given compressed representation (T))) E R&M xd as input, YOSO performs L layers of message passing entirely within this M-dimensional compressed space. For layers 1 = 1,...,, L., the compressed embeddings T()) E Mxd0 are updated as:
xd(
T(() = a (Ao
(5)
where ( is trainable weight matrix for layer (r)) is non- activation, and Ag R MMMMM is graph propagation operator in the compressed domain. A principled choice for As is T where Ánom a normalized adjacency matrix of the original graph (e.g., GCN's D- ÄD 1 (361). This operator allows structural information from the original graph to influence propagation within compressed M x M space. The weight matrices (l)) thus learn the transformations (analogous to spectral filtering when U, captures frequency components) these compressed embeddings. After L layers, obtain the final compressed output (T.) E xdd
A nuem $ T
Reconstruction, Loss Computation, and Joint Optimization Objective. The compressed GNN output ((L) (Fq. (). being -ddimensional, does not directly correspond to the N original nodes. To bridge this gap and compute a meaningful task-specific loss, YOSO reconstructs estimate of
5

---

the full N N-dimensional node embeddings ! E RR-x This reconstruction and the subsequent loss calculation are integrated within a joint optimization objective. Total loss Lota is defined as:
Liotal mLisk ( Yme) + ( Φ U2, H (
(6)
where H!!- = -UHH! (1)- and term H r*)* represents the estimated sparse spectral coefficients of not a parameter learned via direct backpropagation in the same way as U₁ or O. Instead, for current training iteration's 's GNN output T(2) and Uz. H is directly computed by solving the compressed sensing recovery problem (Eqq. (T) The two components of the Cioual are then:
the final layer's embeddings.
Task-specific Loss Lassk. This term directly relates to the GNN's predictive performance on the downstream task (c.g., cross-entropy for node classification), computed using the reconstructed
N-dimensional embeddings H. U (D) and ground true labels Yime-
Compressed Sensing Reconstruction Loss Lrecon- This term evaluates how well the GNN output
TLL) and the learned basis U2 conform the compressed sensing model using the computed H (4)* is defined as:
T - (1)
2 + H
2.1
The first part is the data consistency term, measuring how well the sensed version of the recovered sparse coefficients matches the GNN's compressed output T The second part is the sparsity- promoting regularizer. Both parts of freem explicitly depend on H!("), which itself is a function of T(,), &, Ug. The hyperparameters 3, X, balance these objectives. The overall objective (Eq. function is then minimized subject to the constraint U, U I.
4.2 Learning the Orthonormal Transformation U, and GNN Parameters
As established in Section 4.1
YOSO's training driven by the joint optimization objective presented in (7. This section further clarifies how the gradients of this total loss are used to concurrently update the the learnable orthonormal basis U, and GNN parameters θ.
In each training iteration, after the GNN produces the compressed output T(4,, H!!")* are directly computed by applying FISTA 4 algorithm (Eq. 1)). This H:! is then used to calculate the values for both Lins (via H ()) U² ! and Crecom Consequently, the total loss Low becomes differentiable function of + (through (L) which is an input the Eq.(1) and U2 (which is an input to the (T. and also used in Lissk and frecom). Automatic differentiation can then compute VeLuall and Vu, Liotal. encouraging the GNN to produce compressed outputs (L) that lead to low task error and are well-suited for sparse recovery. Theoretical analysis concerning error bounds is in Appendix B.3.
4.3 Constructing the Universal Sensing Matrix T
A central challenge (Obstacle I, Section in YOSO is designing the fixed sensing matrix + E M to be effective with the learned, evolving basis U, (in Section (.2)). + must robustly capture salient information from the spectral coefficients (0) = U. (0) and ensure that the combined operation @U, satisfies favorable compressed sensing properties like RIP.
YOSO constructs & by combining a graph-structure-wwar component S E M with a randomized component Erand E M using element-wise product: + = Saruci & Erund- The matrix Sanua is determined once during pre-processing based on graph structure and remains fixed. Construction of the Structural Matrix Sxtrct. The matrix Sance aims to guide sensing towards structurally important parts of the graph, which are assumed to correspond to important spectral information. Its construction based on sampling nodes according importance scores derived from the eigenvalues of the symmetric normalized Laplacian Lyym
D ADD Let the N cigenvalues of Lym be 0 < Ao < \ < ... S AN-1- A probability P(i) is defined for each spectral mode (associated with the eigenvalue A₂) as P(i) MXー m{1,) where w().) is
w(A:)
weighting function reflecting the importance of the i-th spectral mode. To construct the M rows of S E (0, 1) J for each row k = 1...., M: (1) Sample spectral index i, E NN. 1}

---

900
10900
250
@Cverpaatice Time
@CCoppaztinn
@NanCterpiiin Time
Total Trininn Time 631
200
Total Training Time,
2000
(x)
400
Total Training Lime
8280
150
Traiming
8000
200
200
x980
20
100
2380
180
VG
A
SRW YONO
XX
10
SWW
$.80 Y050
5
(a) ogbn-arxiv
(b) Reddit
(c) ogbn-grbnned products
(d) ogbl-ppl
(c) ogbl-citation2
Figure 3: The total training time comparison (with breakdown). The evaluation covers two learning tasks across five datasets 30 28 : (a) to (c) represent the results for the node classification task on
ogbn-arxiv, Reddit, and ogbn-products, respectively; while (d)-(e) correspond to the link prediction task on ogbl-ppa and ogbl-citation2. The schemes are GS (GraphSage (28). VG (VR-GCN (12).
FG (FastGCN (3), AG (AS-GCN (3I)). LA (LADIES (72) D. CG (Cluster-GCN (1S). two versions of GraphSAINT 666 (S EG and S S_RW), and our proposed YOSO.
according to the probability distribution P(t), and (2) The k-th row (M is set to be i row of x identity matrix IN. That is, (Samaa) = 1 if j = it. and O otherwise. This construction means each row of Saruei selects exactly one spectral coefficient based the eigenvalue-weighted sampling. Thus, Saruct is a binary matrix where each row has exactly one non-zero entry. This inherently ensures that Street has no all-zero rows (provided M 0). This structural property is important for the full rank characteristic of 4, as detailed in Appendix I.I B.
Construction of the Random Matrix Erand. Randomness introduced via Erand E RR to help satisfy RIP-like conditions (3. The construction of Erand is coordinated with S For each column j = -l.... N of Sttret: let g(j)= = Σ k=nl (Satmat).. be the number of non-zero elements in that column (i.e., how many sampled "sensor neighborhoods" node j is part of). The elements of Fand are defined as: for each entry (Eran))
[NO0, oG)
if (Satmaa): 1 and g(j)
(rand) Mus
if (Sauuet):s =
If g()) = O for some j (meaning node j is not in any sampled neighborhood), then (Erand) = 0 for all k. This implies the j-th column of 4 will be all zeros. The specific design for 4 S Erand combines the traph-aware structural selection (via node importance and neighborhoods encoded in Sanee) with scaled randomness (in Eyand). It aims create fixed sensing matrix that is effective for capturing information from spectrally sparse signals generated by the evolving Up. The claim that this construction satisfies Restricted Isometry Property detailed in Appendix B.2
5 Experiments
We evaluate YOSO and other baselines with across two most widely used tasks: node classification and link prediction. For the detailed description of experimental setting, such as the datasets (Please refer to Table 55 for the detailed descriptions of the datasets), baselines and hyperparameter, are provided in Appendix
5.1 Overall Comparison
We evaluate baselines and YOSO with two core metrics: model accuracy and total training time.
Node Classification Task. YOSO achieves the shortest training time with an average of 74% reduc- tion among all baselines as shown in Fig. 3 For most of the cases, YOSO can achieve more than 60% training time reduction. For two cases with less than 40% reduction compared to FG and LA on Red- dit. The training time reduced from around 490s with FG and around 501s with LA to around 341s with YOSO (with 36% and 37% time reduction, respectively). The main reason is that YOSO can sig- nificantly reduce the Non-computation time while introducing a little reconstruction overhead. On av- erage. YOSO reduces non-computation time by approximately 95.7% compared to all other baselines. For model accuracy shown Table I YOSO consistently matches or closely approaches the top per- formers. For example, YOSO obtains accuracy of 0.71 7 ogbn- arxiy, just 0.01 below GraphSage.
7

---

Traiung Les
1.5
1.2
Trinun
100 150 300
0.2
25
300
225
150
375
Fpeck
Fgrwt
(a) ogbn-arxine -axiv
(b) ogbl-ppa
Figure 4: Training loss and epoch curves for YOSO and baselines on two benchmark datasets.
Link Prediction Task. For total training time, similar to the node classification task, YOSO achieves the best training time with around 72% average training time decrease across all datasets for the link prediction. This improvement is con- sistent with the node classification task, where YOSO achieves considerable reductions in non- computation time while introducing minimal reconstruction overhead. As shown Fig. dd-- (e). YOSO achieves an average non-computation time reduction of about 81 % across all datasets. As for model accuracy, in Table YOSO main- tained results with only a very small gap: 0.003 on ogbn-arxiv and ogbl-citation2, compared to the best results.
Table 1: Model accuracy results for different meth-
ods on node classification and link prediction tasks. Accuracy metrics on each dataset are in Table 5
Datasets
Node Classification
Link Prediction
arxiv
Reddit
products
ppa
citation2
GraphSage
0.720
0.949
0.772
0,170
0.805
VR-GCN
0.697
0.962
0.699
0.170
0.796
FasGGN
0.438
0.927
0.404
0.108
0.655
AS-GCN
0.687
0,964
0.510
0.124
0.659
LADIES
0.649
0.927
0,501
0.113
0.669
Cluster-GOS GCN
0.653
0.966
0.769
0.205
0.790
GrapSSAINT.FG
0.792
0,214
GrapbSAINT-RV
0,701
0.967
0.783
0,226
0.805
YOSO
0.720
0.787
0.223
0.802
In summary. for both tasks of node classification and link prediction, by combining high accuracy with substantial reductions in sampling and total training time, YOSO demonstrates its efficiency in GNN training and significantly improves both sampling and total training times across all datasets while maintaining competitive accuracy, highlighting its effectiveness compared to the baselines on the node classification task.
5.2 Convergence Comparison
We investigate YOSO convergence performance compared to other baselines on ogbn-arxiv (node classification) and ogbl-ppa (link prediction). The training loss-epoch curves are shown in Fig. 4 In two different learning tasks, YOSO consistently outperformed the baselines in terms convergence speed and stability. For ogbn-arxiv, YOSO reached a lower training loss more rapidly than Graph- and FastGCN, with significantly fewer oscillations, indicating a more stable and efficient training process. Similarly, for ogbl-ppa, YOSO demonstrated faster convergence and maintained a smoother training loss curve compared to other baselines. These results suggest that YOSO not only accelerates the convergence process but also ensures a more stable training path compared to existing sampling methods, highlighting its effectiveness in GNN training.
SAGE, GraphSAINT-EDDG
5.3 Ablation Study
We explore three main aspects of YOSO design: (i) How YOSO's total training time and model accuracy vary with different size of M, (ii) Reconstruction effectiveness by comparing the H (L) and (L) and (iii) The parameterization strategy of & (layer-wise vs. universal) (see Section 4.3
Varying M value. We examine how total training time (including breakdown) and model accuracy vary with M values, specifically AM = [64, 128, 256, 1024, 2048), as shown in Fig. 5 The results indicate that YOSO's sampling time remains stable across different M, ranging from 107.94 to 111.53 seconds on grondctsducts and 143.56 to 149.65 seconds on ogbl-citation2, showing minimal impact from M. contrast, as .M decreases, computation time increases, reflecting more iterations needed for convergence (e.g., rising from 275.98s at M 2048 to 301.94s at M 64 on ogbn- products, with a similar trend on ogbl-citation2). Model accuracy improves with larger M, eventually stabilizing: it rises from 0.597 to 0. 0.7873 on ogbn-products and from 0.312 to 0.8025 on oghl-citation2. These findings highlight YOSO's ' efficient sampling and improved accuracy and convergence with larger M.
8

---

NenCoorpiition Time
Compatatoon
-le-Moddl Acoracy
Nen-Coeppration
Compaaaion
- -i--Midd Anoracy
600
600
Toul Tuiika Tane
0.8
babits Tuee
500
0.8
300
300
0.4
2
0.4
200
100
100
M+44
M-128
M-256
M-1044
M-2668
M1-44
M-128
M5
M-1024
M 2848
(a) ogbn-productss
(b) ogbl-citation2
Figure 5: Total training time (including its breakdown) and model accuracy for YOSO with different sampling sizes: (a) for the node classification learning task on the egbn-producte dataset, and (b) for the link prediction learning task on the ogbl-citation2 dataset.
M-64
M--188
M--26
M--12
M-1024
10
62
Figure 6: Reconstruction effectiveness visualized via heatmap. Using the ogbn-prooee products dataset, 10 nodes are randomiy selected from the training set, and for each node, 10 embedding dimensions are randomly picked. The heatmap shows the absolute differences between original and reconstructed embeddings for these elements. M is the size of the sampling set.
Table 2: Total training time and model accuracy under different configurations.
Dataset
ogbn-arxiv
ogbl-ppa
Type of Φ
Layer-wise
Universal
Layer-wise
Universal
Total Training Time (s)
59.22
10.93
145.50
21.46
Model Accuracy
0.730
0.727
0.2254
0.2235
Reconstruction effectiveness: Fig. shows the reconstruction effectiveness for different sampling sizes M. Each 10 10 block represents the absolute difference between reconstructed embeddings from our two-layer GNN sampling and those computed with all neighbors (without sampling). As M increases, reconstruction accuracy improves, enhancing overall model accuracy. However, beyond a certain point, such as M 512 in Fig. 66 further increases in M offer diminishing returns in both reconstruction quality and model accuracy. This suggests there is an optimal M that balances reconstruction quality and computational efficiency.
Layer-wise vs. Universal. We compare two parameterization strategies: layer-wist wise variant, where each GNN layer maintains its own transformation matrix, and a universal variant that shares a single & across layers. As shown in Table 2 the layer-wise + notably increases computational overhead: by approximately 5x on ogbn-arxiv and 7x on ogbl-ppa, while providing only marginal accuracy improvements (within 0.001). This indicates that universal & achieves nearly equivalent accuracy at substantially lower cost, offering favorable efficiency-accuracy trade-off.
5.4 Comparisons to Graph Condensationn/iistllatan and Linearization
To further contextualize YOSO's efficiency, compare it with two other families of graph optimization schemes that also aim to reduce the training cost: (i) Graph Condensation//istillaee methods, which synthesize smaller representative graphs for training, and (ii) Linearization methods, which approximate message passing through pre-computed feature propagation.
YOSO vs. Graph Condensation/Dissillatioo Both Graph Condensation and Graph Distillation introduce the substantial preprocessing overhead and risk discarding informative structural signals, which can degrade model performance. To quantify this, we compare YOSO against two most widely used condensation schemes: GCond (4 and GC-SNTK [60), on the ogbn-arxiv dataset with a 0.25% reduction ratio. As shown in the Table YOSO achieves higher accuracy (0.7169) while requiring

---

Table 3: Comparison of preprocessing time and model accuracy on the ogbn-arxiv dataset
Dataset
ogbn-arxiv
Schemes
GCond
GC-SNTK
YOSO
Preprocessing Time (s)
20615.6
11066.89 89
1643.32
Model Accuracy
0.6172
0.6219
0.7169
Table 4: Comparison between YOSO with linearization schemes.
Dataset
ogbn-products
ogbn-arxiv
Schemes
SIGN-2
SIGN-4
SIGN-6
SIGN-8
YOSO
iSVD
iSVD-best
YOSO
Total Training Time (s)
421.79
584.07
831.94
1052.96
499.02
9.94
982.12
10.74
Model Accuracy
0.761
0.778
0.776
0.783
0.788
0.685
0.746
0.720
far less preprocessing time (12x faster than GCond and 6x faster than GC-SNTK), demonstrating superior efficiency and information retention.
YOSO vs. Linearization. We also compare YOSO with multiple linearized GNN variants, including SIGN 22 and iSVD [ on ogbn-pnt agbn-products and ogbn-arxiv. As summarized the Table SIGN-2 achieves slightly lower training time but at the cost of 2.7% accuracy drop. The low-accuracy iSVD variant reduces runtime by 8% yet loses 4% accuracy, whereas the high-accuracy version (iSVD-best) increases runtime by 91 x for only 0.014 gain. YOSO consistently delivers a better balance between accuracy and total training time.
Related Work
Numerous approaches have been proposed to enhance GNN training efficiency. Sampling-basee methods, including node-wise, layer-wise, and subgraph-based techniques [28] 13 15), aim to reduce computational load by training on smaller portions of the graph. While effective in certain scenarios, node-wiss wise sampling can suffer from exponentially growing receptive fields, layer-wise methods may introduce bias or complex variance reduction schemes, and subgraph- based approaches often incur significant pre-processing overhead for graph partitioning or dynamic subgraph generation, sometimes at the cost of accuracy (e.g., layer-wise schemes) or increased complexity (e.g., subgraph- based). Other strategies such as graph condensation and distillation 34 (6) focus on creating smaller graph proxies or simpler models, which can be effective but may lose fine-grained information or require careful tuning of the condensation/ddistilatiion process itself. Meanwhile, historical embed- ding [12] and linearization techniques (22] seek to optimize specific aspects of GNN computation or simplify model architecture, often by removing non-linearities which can limit expressive power. YOSO distinguishes itself by uniquely combining once-pere pecc-pee-training learnable orthonormal spectral transformation with Compressed Sensing principles for one-shot projection and reconstruction. This approach primarily targets the reduction of non-computational overheads (like extensive data handling for sampling and repeated transformations) without resorting to complex graph sampling strategies repeated costly operations during the GNN's forward and backward passes. A more detailed discussion of related work is provided Appendix C
7 Conclusion
In this paper, we introduce YOSO (You Only Spectralize Once), a novel training scheme aimed at significantly enhancing the efficiency of GNN training without sacrificing prediction accuracy. By leveraging a Graph Fourier and compressed sensing-based reconstruction framework, YOSO performs a spectral transformation only once at the input layer, followed by an error-bounded reconstruction at the output layer during each training iteration. Our experimental results demonstrate that YOSO can achieve an average 74% reduction of existing state-of-the-e schemes while preserve model accuracy comparable to top-performing baselines.
10

---

Acknowledgment
This work was partially supported by NSF 2204656, 2343863, 2413520 and 2440611, 1. Any opinions, conclusions, or the recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the NSF.
References
[1] Sami Abu-El-Haija, Hesham Mostafa, Marcel Nassar, Valentino Crespi, Greg Ver Steeg, and Aram Galstyan. Implicit svd for graph representation learning. Advances Neural Information Processing Systems, 34:8419 10-119-811,, 2021.
[2] Basheer Alwaely and Charith Abhayaratne. Graph spectral domain features for static hand gesture recognition. 2019 27th European Signal Processing Conference (EUSIPCO), pages 1-5, 2019.
[3] Richard Baraniuk, Mark Davenport, Ronald Vore, and Michael Wakin. A simple proof of the restricted isometry property for random matrices. Constructive approximation, 28:253-263, 2008.
[4] Amir Beck and Mare Teboulle. A fast iterative Shrinkago-thresholdig algorithm for linear inverse problems. SIAM journal on imaging sciences, 2(1):183-202, 2009.
[5] Florian Bernard, Daniel Cremers, and Johan Thunberg. Sparse quadratic optimisation over the stiefel manifold with application permutation synchronisation. In Neural Information Processing Systems, 2021.
[6] Deyu Bo, Xiao Wang, Yang Liu, Yuan Fang, Yawen Li, and Chuan Shi. A survey on spectral graph neural networks. arXiv preprint arXiv:2302.056311 2023.
[7] Michael M Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond euclidean data. IEEE Signal Processing Magazine, 34(4):18 42, 2017.
[8] Aydın Buluç, Henning Meyerhenke, llya Safro, Peter Sanders, and Christian Schulz. Recent advances graph partitioning. Springer, 2016.
[9] Emmanuel Candes and Terence Tao. Decoding by linear programming. IEEE transactions information theory, (1(12):4033-4255 2005.
[10] Emmanuel J Candes and Terence Tao. Near-optimal signal recovery from random projections:
Universal encoding strategies? IEEE transactions on information theory, 52(12):5406-5425 2006.
[11] Rudrasis Chakraborty and Baba Vemuri. Statistics on the stiefel manifold: Theory and applications. 2019.
[12] Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduction. arXiv preprint 17Xiv:1710.105500 2017.
[13] Jie Chen, Tengfei Ma. and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling. arXiv preprint arXiv: 1801.10247 2018.
[14] Siheng Chen, Rohan Varma, Aliaksei Sandryhaila, and Jelena Kovačević. Discrete signal processing on graphs: Sampling theory<? pub newline=""? IEEE transactions on signal processing, 63(24):6510-66)) 66200, 2015.
[15] Wei-Lin Chiang, Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pages 257-266, 2019.
11

---

[16] Hanjun Dai, Zomitsa Kozareva, Bo Dai, Alex Smola, and Le Song. Learning steady-states of iterative algorithms over graphs. In International conference on machine learning, pages 1106-1114 PMLR, 2018.
[17] Joya Deri and José MF Moura. Spectral projector-based graph fourier transforms. IEEE Journal of Selected Topics in Signal Processing, 11(6):785-795, 2017.
[18] George H Dunteman. Principal components analysis, volume 69. Sage, 1989.
[19] Jiarui Feng, Yixin Chen, Fuhai Li, Anindya Sarkar, and Muhan Zhang. How powerful are k-hop message passing graph neural networks. Advances in Neural Information Processing Systems, 35:4776 4790, 2022.
[20] Matthias Fey. Jan E Lenssen, Frank Weichert, and Jure Leskovec. Gnnautoscale: Scalable and expressive graph neural networks via historical embeddings. International conference on machine learning, pages 3294-3304. PMLR, 2021.
[21] Miroslav Fiedler. A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czechoslovak mathematical journal, 25(4):619-633 1975.
[22] Fabrizio Frasca, Emanuele Rossi, Davide Eynard, Ben Chamberlain, Michael Bronstein, and Federico Monti. Sign: Scalable inception graph neural networks. arXiv preprint 11X1 2020.
[23] Xinyi Gao, Junliang Yu, Tong Chen, Guanhua Ye, Wentao Zhang, and Hongzhi Yin. Graph condensation: A survey. arXiv preprint arXiv:240..11220, 2024.
[24] Robert Grone, Russell Merris, and Viakalathur Shankar Sunder. The laplacian spectrum of graph. SIAM Journal matrix analysis and applications, 11(2):218-22 1990.
[25] Zhichun Guo, William Shiao, Shichang Zhang, Yozen Liu, Nitesh Chawla, Neil Shah, and Tong Zhao. Linkless link prediction via relational distillation. In International conference on machine learning, pages 12012-12033, PMLR, 2023.
[26] Zhichun Guo, Chuxu Zhang, Wenhao Yu, John Herr, Olaf Wiest, Meng Jiang, and Nitesh V Chawla. Few-shot graph learning for molecular property prediction. Proceedings of the web conference 2021, pages 2559-2567, 2021.
[27] Zhiwei Guo and Heng Wang. A deep graph neural network-based mechanism for social recommendations. IEEE Transactions on Industrial Informatics, 17(4):277--2783, 2020.
(28) Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. Advances in neural information processing systems, 30, 2017.
[29] Jarvis Haupt, Waheed U Bajwa, Michael Rabbat, and Robert Nowak. Compressed sensing for networked data. IEEE Signal Processing Magazine, 25(2):22-001, 2008
[30] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. Advances in neural information processing systems, 33:22118 1222133,,,, 2020.
[31] Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. Advances in neural information processing systems, 31, 2018.
[32] Elvin Isufi, Fermando Gama, David I Shuman, and Santiago Segarra. Graph filters for signal processing and machine learning on graphs. IEEE Transactions on Signal Processing, 2024.
[33] Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In Proceedings of the 26th ACM SIGKDD international conference knowledge discovery & data mining, pages 66-74, 2020.
[34] Wei Jin, Lingxiao Zhao, Shichang Zhang, Yozen Liu, Jiliang Tang, and Neil Shah, Graph condensation for graph neural networks. arXiv preprint arXiv:2110.07580 2021.
12

---

[35] Kyusoon Kim and Hee-Seok Oh. Principal component analysis in the graph frequency domain. 2024.
[36] Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv: 1609.0290700 2016.
[37] Takashi Kurokawa, Taihei Oki, and Hiromichi Nagao. Multi-dimensional graph fourier trans- form, arXiv preprint arXiv:1712.07811 2017.
[38] Yi Li, Tsun- Yu Yang, Ming-Chin Ming-Chang Yang, Zhaoyan Shen, and Bingzhe Li. Celeritas: Out-of-core based unsupervised graph neural network via cross-layer computing 2024. In 2024 IEEE International Symposium on Perf-Peeforeance Computer Archilecture (HPCA), pages 91-107. IEFE, 2024.
[39] Hao Liu, Qiyu Wu, Fuzhen Zhuang, Xinjiang Lu, Dejing Dou, and Hui Xiong. Community- aware multi-task transportation demand prediction. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 320-327, 2021.
[40] Xin Liu, Mingyu Yan, Lei Deng, Guoqi Li, Xiaochun Ye, and Dongrui Fan. Sampling meth- ods for efficient training of graph convolutional networks: A survey. IEEE/CAA Journal of Automatica Sinica, 9()):005-23 234, 2021.
[41] Arian Malcki. Approximate message passing algorithms for compressed sensing. PhD thesis, Stanford University, 2010.
[42] Russell Merris. Laplacian graph eigenvectors. Linear algebra and its applications, 278(1- 3):221-236, 1998.
[43] Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. Distributed repre- sentations of words and phrases and their compositionality. Advances in neural information processing systems, 26, 2013.
[44] Benjamin A Miller, Nadya T Bliss, and Patrick J Wolfe. Toward signal processing theory for graphs and non-euclidean data. In 20/0 IEEE International Conference on Acoustics, Speech and Signal Processing, pages 5414-5417. IEEE, 2010.
[45] Alan Oppenheim and Donald H Johnson. Discrete representation of signals. Proceedings of the IEEE, 60(6):68 1691, 1972.
[46] Shan-Chen Pang, Kuijie Zhang, Gan Wang, Chun-Wei Lin, Fu-Yan Wang, Xiangyu Meng, Shudong Wang, and Yuanyuan Zhang. Af-gen: Completing various graph tasks efficiently via adaptive quadratic frequency response function in graph spectral domain. Inf. Sci., 623:469-480, 2022.
[47] Jeffrey Pennington, Richard Socher, and Christopher D Manning. Glove: Global vectors for word representation. In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP), pages 1532-1543, 2014.
[48] Gilles Puy, Nicolas Tremblay, Rémi Gribonval, and Pierre Vandergheynst. Random sampling of handlimited signals on graphs. Applied and Computational Harmonic Analysis, 44(2):446-475, 2018.
[49] Hassan Ramchoun, Youssef Ghanou, Mohamed Ettaouil, and Mohammed Amine Janati Idrissi. Multilayer perceptron: Architecture optimization and training. 2016.
[50] Arash Rasti-Meymandi,, Ahmad Sajedi, Zhaopan Xu, and Konstantinos N. Plataniotis. Gstam: Efficient graph distillation with structural iitention-matching ArXiv, abs/2408.16871. 2024.
[51] Manon Réau, Nicolas Renaud, Li C Xue, and Alexandre MJJ Bonvin. Deeprank-gnn: graph neural network framework to learn patterns in protein-protedd interfaces. Bioinformatics, 39()):btac759 2023.
[52] Aliaksei Sandryhaila and José MF Moura. Discrete signal processing on graphs: Graph fourier transform. In 2013 IEEE International Conference on Acoustics, Speech and Signal Processing, pages 6167-6170. IEEE, 2013.
13

---

[53] Rishi Raj Sharma and Ram Bilas Pachori. Eigenvalue decomposition of hankel matrix-based freeefrr representation for complex signals. Circuits, Systems, and Signal Processing. 37:3313 3329, 2018.
[54] Wuzhen Shi, Feng Jiang, Shaohui Liu, and Debin Zhao. Image compressed sensing using convolutional neural network. IEEE Transactions on Image Processing, 29:375-388, 2019.
[55] Zhihao Shi, Xize Liang, and Jie Wang. Lme: Fast training of gnns via subgraph sampling with provable convergence. arXiv preprint arXiv:2302.00924, 2023.
[56] Yijun Tian, Shichao Pei, Xiangliang Zhang, Chuxu Zhang, and Nitesh V Chawla. Knowledge distillation on graphs: A survey. arXiv preprint urXiv:2302.002199 2023.
[57] Mikhail Tsitsvero, Sergio Barbarossa, and Paolo Di Lorenzo. Signals on graphs: Uncertainty principle and sampling. IEEE Transactions on Signal Processing, 64(1 (4(18):4845-488 2016.
[58] Roger Waleffe, Jason Mohoney, Theodoros Rekatsinas, and Shivaram Venkataraman, Marius- gnn: Sessource-effciiens out-of-core training of graph neural networks. In Proceedings of the Eighteenth European Conference on Computer Systems, pages 144-161, 2023.
[59] Kuansan Wang. Zhihong Shen, Chiyuan Huang, Chich-Han Han Wu, Yuxiao Dong, and Anshul Kanakia. Microsoft academic graph: When experts are not enough. Quantitative Science Studies, 1(1):396-413, 2020.
[60] Lin Wang, Wengi Fan, Jiatong Li. Yao Ma, and Qing Li. Fast graph condensation with structure- based neural tangent kernel. In Proceedings of the ACM on Web Conference 2024, pages 4439 4448, 2024.
[61] Tingting Wang, Haiyan Guo, Xue Yan, and Zhen Yang. Speech signal processing on graphs: The graph frequency analysis and an improved graph wiener filtering method. Speech Commun., 127:82-92 91, 2021.
[62] Xiaohan Wang, Jiaxuan Chen, and Yuantao Gu. Generalized graph signal sampling and reconstruction. In 2015 IEEE Global Conference Signal and Information Processing (GlobalSIP), pages 567-571. IEEE, 2015.
[63] Xiaohan Wang, Pengfei Liu, and Yuantao Gu. Local-set-based graph signal reconstruction. IEEE transactions on signal processing, 63(9):2432-2444, 2015.
[64] Lirong Wu, Haitao Lin, Yufei Huang, and Stan Z Li. Knowledge distillation improves graph structure augmentation for graph neural networks. Advances in Neural Information Processing Systems,
2022.
[65] Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD international conference on knowledge discovery & data mining, pages 974-983 2018
[66] Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graphsaint: Graph sampling based inductive learning method. arXiv preprint arXiv:1907.0423 04931, 2019.
[67] Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. Advances in neural information processing systems, 31, 2018.
[68] Shichang Zhang, Atefeh Sohrabizadeh, Cheng Wan, Zijie Huang, Ziniu Hu, Yewen Wang, Jason Cong. Yizhou Sun, et al. A survey on graph neural network acceleration: Algorithms, systems, and customized hardware. arXiv preprint arXiv:2306. 14052, 2023.
[69] Tianxiang Zhao, Xiang Zhang, and Suhang Wang. Graphsmote: Imbalanced node classification on graphs with graph neural networks. In Proceedings of the 14th ACM international conference on web search and data mining, pages 933-841, 2021.
14

---

[70] Xin Zheng, Miao Zhang. Chunyang Chen, Quoe Viet Hung Nguyen, Xingquan Zhu, and Shirui Pan. Structure-free graph condensation: From large-scale graphs condensed graph-free data. Advances in Neural Information Processing Systems, 36, 2024.
[71] Fan Zhou, Chengtai Cao, Kunpeng Zhang, Goce Trajcevski, Ting Zhong, and Ji Geng. Meta- gnn: On few-shot node classification in graph meta-learning. In Proceedings of the 28th ACM International Conference Information and Knowledge Management, pages 2357-2360 2019.
[72] Difan Zou, Ziniu Hu, Yewen Wang, Song Jiang, Yizhou Sun, and Quanquan Gu. Layer- dependent importance sampling for training deep and large graph convolutional networks. Advances in neural information processing systems, 32, 2019.
15

---

A Experimental Setting
A.1 Hardware and Software Configuration
We evaluate all baselines and YOSO Ubuntu 18.04.6 LTS, equipped with an NVIDIA GTX 1060Ti (6GB memory), using CUDA version 11.8 and PyTorch version 2.0.0. The system features a AMD Ryzen 5 5900 CPU with 128 GB DDR4 RAM, and the Python version used is 3.9.0.
Table 5: Statistics and metrics of the dataset.
Dataset
#node
#edge
#dim.
Metric
ogbn-arxiv Reddit
169,343
1,166,243
128
Accuracy
Node Property Prediction
232,965
11,606,919
602
Micro-Fi
ogbn-products
2,499,029
61,859,140
100
Accuracy
ogbl-ppa
576,289
30,326,273
128
Hits@ 100
Link Property Prediction
ogbl-citation2
2,927,963
30,561,187
128
MRR
A.2 Datasets
For node classification, use Reddit [28 ogbn-arxiv and ogbnnproducee [30 and for link prediction, we use ogbl-ppa, and ogbl-citation2 [30] The basic summary information the datasets we use is provided in T and detailed descriptions as follows:
ogbn-arxiv: This dataset is a directed citation network of Computer Science (CS) arXiv papers from the Microsoft Academic Graph (MAG) [59]. Each node represents paper, with directed edges indicating citations. The task to classify unlabeled papers into primary categories using labeled papers and node features, which are derived by averaging word2vec embeddings 43) of paper titles and abstracts.
Reddit: Originally from GraphSage (28), this Reddit dataset is pest-to-post- graph where each node represents post, and edges indicate shared user comments. The task is to classify posts into communities using GloVe word vectors [7 from post titles and comments, along with features such as post scores and comment counts.
This undirected, unweighted graph represents an Amazon product co-purchasing network, where nodes products and edges indicate frequent co-purchases. Node features derived from bag-of-words features of product descriptions, reduced to 100 dimensions via Principal Component Analysis [8]
ogbn-products:
ogbl-ppa:
This undirected, unweighted graph has nodes representing proteins from 58 species, with edges indicating biologically meaningful associations. Each node features 58-dimensional one-hot vector for the protein's species. The task is to predict new association edges, evaluated by ranking positive test edges over negative ones.
This dataset a directed graph representing a citation network among subset of papers from Microsoft Academic Graph (MAG), similar to ogbn-arxiv. For each source paper, two references are randomly removed, and the task rank these missing references above 1,000 randomly selected negative references, which are sampled from all papers not cited by the source paper.
oghl-citation2:
Data splitting: We adopt strategies consistent with previous works 28
Specifically, for the 30
Reddit dataset, we follow the data splitting used in GraphSage [28 and for the OGB series (ogbn and ogbl), we maintain the splitting described in [30].
A.3 Baselines and Implementation
The baselines used cover all major methods designed to address the off between efficiency and accuracy, including: GraphSage (28) (GS), VR-GCN [2] (VG), FastGCN 13 (FG), AS-GCN [1 (AG), LADIES [72] (noted by LA), Cluster-GCN [5] (CG), and GraphSAINT (66) (two versions noted as S_EG and $_RW). Detailed information on the source code for these baselines, the YOSO implementation, and other related materials can be found in Appendix A.3
16

---

Table 6: Baselines and their public available souree code link
Scheme
Available Link
GraphSage
VR-GCN
FastGCN
AS-GCN
LADIES
https//giiabb.ccom//bbbllLLLLDDS
Cluster-GCh http://gihbbooom//eeedccccoccccc
GraphSAINT
Table 7: Node classification hyperparamter setting for baselines and YOSO different datasets.
Scheme
ogbn-arxiv
Reddit
ugbn-produse
GraphSage
25& Adam 0.7
25& 10 Adam / 0.01
50&20 Adam 0.01
VR-GCN
8 Adam / 0.01
16 / Adam / 0.01
32 Adam / 0.01
FastGCN
64 / Adam 0.01
128 / Adam 0.001
256 Adam 0.001
AS-GCN
128 / Adam 0.001
512 Adam / 0.01
1000 / Adam / 00001
LADIES
64 Adam 0.001
128 / Adam 0.001
256 Adam 0.001
Cluster-GCI
-/ Adam 0.01
-/ Adam/ 0.005
-/ Adam / 0.005
GraphS
300 / Adam 0.01
600 Adam / 0.01
4000 / Adam 0.01
GraphSAINT-RW
4000 / Adam / 0.01
8000 Adam / 0.01
10000 / Adam / 0.01
YOSO
128 / Adam 0.01
256 Adam / 0.01
512 Adam 0.01
Table pooesentsesents the baselines used in this paper along with their publicly available source code links. Since some baselines were not originally implemented in Py Torch, we standardized the framework for fair comparison. If PyTTorch version involved the original authors, we selected that source code (e.g., FastGCN (13). Otherwise, we chose the most popular implementation based on the number of stars. Notably, the repository linked for AS-GCN (3 in the table includes implementations of both FastGCN and AS-GCN, but we only used the AS-GCN version, while the FastGCN implementation was taken from the source listed in the table.
YOSO's Implementation: The base code of YOSO is built on GCN (36), with the link available at https://github..om httpp/uu..ooomkpp//yyeeeeee
The sampling stage YOSO occurs on the CPU and main memory since it involves calculations related to the entire feature matrix and the regularized Laplacian matrix. After sampling, the relevant data is migrated to GPU memory for computation. Throughout the training process, multiple data exchanges occur between main memory and GPU memory, such as in link prediction tasks where node embeddings need be updated.
Modification; All baselines support updating node embeddings and performing node classification tasks. For node classification, if baseline did not originally use the cross-entropy loss function, we adjusted it to adopt this loss function. For the link prediction task, the following loss function is applied:
C=
1 N+ (L.))R+
Σ
(1
h (T)
(T) h
Σ max (0, (0.7-(1)
(1
||n I 1 ))
1 h
(EJ)ER
where N and N represent the number of positive and negative samples, respectively, and E+ and E denote the sets of positive and negative edges. The parameter y is a hyperparameter, set to 0.5 in this study. As the ogbl-ppa and ogbl- ciblicitation2 datasets provide corresponding negative edges by default, we used these pre-defined negative edges for our calculations.
A.4 Hyper-parameter Setting
All experiments are conducted with two layers. The hyperparameter settings for both YOSO and the baselines are provided in Tad Table g for node classification and link prediction datasets, respectively. All experiments were conducted using two-layer GCN with official configurations.
17

---

Table Link prediction hyperparamter setting for baselines and YOSO on different datasets.
Scheme
ogbl-ppa
ogbl-citation2
GraphSage
25& Adam / 0.7
50&20 Adam / 0,011
VR-GCN
8 Adam 0.01
32 Adam / 0.01
FastGCN
64 / Adam 0.01
256 Adam / 0.001
AS-GCN
128 / Adam 0.001
1000 Adam 0.01
LADIES
64 / Adam 0.001
256 Adam / 0.001
Cluster-GCN
-/ Adam / 0.01
-/ Adam / 0.005
GraphSAINNTEE
300 / Adam / 0.01
4000 / Adam / /0.0
GraphSAINT-RW
4000 Adam / 0.01
10000 / Adam 0.01
YOSO
128 / Adam / 0.01
512/ Adam / 0.01
When certain parameters were not clearly specified some papers, we fine-tuned them for optimal accuracy. The recorded hyperparameters include the sampling size (per node/layer/subgraphh) the optimizer, and the learning rate. For YOSO, the sampling size is denoted as M; for example, on the ogbl-ppa dataset (Table 8 M 128.
B Formal Proof
B.1 Full Rank of +
Theorem 1 (Full Rank of +): Let Setruct MXN be the structural matrix where each of its M rows, k is constructed by sampling a spectral index i E O...., (N - -1) according to the probability distribution P(t) = w(x))/ Lソ= N-1 w(2,) (with w(A;) >; as proposed in Section 4.3 and setting (Satruct)ss if j and 0 otherwise. Assume the M sampled spectral indices distinct (ic., sampling without replacement, requiring M N). Let Erand E RMXN be random matrix where entries (Erand)k.s are defined as (Erand)ks ~ (0 1/g(i)) if (Sstruct)s.) = and g( O, and (Erand)s, = if (S (Sstruct):: = O, where g(j) = Ex (Sstruct) RR.j. Define the sensing matrix + Strruct 69 Drand: where @ denotes element-wise multiplication. Then, with probability 1, the matrix & has full row rank M.
Proof: The structure of & is such that for each row E I,..,, only one entry is non-zero. Specifically, if the spectral index is was chosen for row l (so (Sstruct) for jor * it), then &k.i = (S (tttruct)a R2.i2 (Erand) = 1, and all other entries (Eran))k. for j * is are O. Since assume the M sampled spectral indices é1, é2 .... is are distinct, it follow that for M (Sstruct)r.s.
and (Sstruct)
0
(as only row k has "1' in column ig). Thus, Brand)ki ~ A 1/1) = (0, To show that & has full row rank .M, we need demonstrate that its M rows are linearly independent. Consider linear combination of the rows of & that equals the zero row vector 0 E IR IIINN
each selected index ia. g(ix) Σn
for the non-zero entry in row k, is
Σ Ca( k. = O
(8)
where cg scalars and (b),, is the k-th row of Φ. This vector equation implies that for each column j E O......N -V-1.
Σ k=1
ch kgj
(9)
Consider one of the M distinct spectral indices that were sampled, say ip (where p E 1,... M) the row for which this index was chosen). For the column ip. the sum becomes:
Cp 4b k: + pck
RR.,, = 0
(10)
since ( ) = 0 for all k + (because the sampled indices in are distinct, so only row has its non-zero entry in column ip), the equation simplifies to:
Cp p. =
(1I)
18

---

as (+) p. (O, 1), it is non zero with probability 1. Therefore, for the equation cp (p( p.i, 0 to hold, we must have Cp 0. Since this argument applies each of the M distinct sampled indices i1 .1.... AM. it follows that all coefficients 6,, .2,..., CM must be zero. This demonstrates that the rows of + are linearly independent with probability 1. Thus, rank ( M.
B.2 Sensing Matrix +, Learnable Ug, and RIP Satisfaction
Theorem 2 (RIP Satisfaction for eU,): Let U₃ E RN*N be an orthonormal matrix. Let + e RMxN be constructed as Theorem (effectively selecting M distinct rows of U₃ and multiplying them by independent. (0, 1) scalars). If U, is sufficiently incoherent with the standard basis (in which H is k-rowss then for any 8x < 1, there exists constant Crip > 0 such that if M 2 CRIP- k (og((/k)), the matrix xp +U, satisfies the k-row-RIP for matrices H E Rxx with constant 6g with high probability:
(1 - 6+] < (UHH S (1 (1+ 6%) H
Proof. Let A UU,,. The k-th row of A is (E),, ((Ur)...)) where (.)))
T is the ig row of U.. The core idea is to show that for any k-row-sparse matrix H. ||| concentrates
around |
Step 1: Expectation of the Squared Norm. Let X' U.H. The k-th row of 4x' is (æX))
(E)x (X)) Ke..
E
HUU
E
Σ II
I(:
As
Σ
E
[((U),,)) THE
Since mi) ~ ~N
1
M Σ (((()))
E
THE
This is the sum of energies of H projected onto the M selected rows of Ug. For this sum to be equal to || = | (as U, is orthonormal), the M selected rows must effectively form a basis for the k-row-sparse H. This is where incoherence and random selection are crucial. If the selection of ip were uniformly random and U, were incoherent with the sparsity basis of H, this sum would be proportional to (M/N) [| [| The matrix d needs to be appropriately scaled (e.g.. by 1/VM or N/M) this expectation to be exactly || 1/ The current construction with (0 1) weights results in expectation that is the sum of energies in M selected components. Standard RIP proofss often assume a sensing matrix A such that ||| Az | = |xx]]" For our U we'd d typically need a scaling factor of /N/M or similar for the random entries if we were constructing a dense random projection, ensure the sum of energies of selected components approximates the total energy.
Step 2: Concentration for Fixed k-row-sparse H. For a fixed k-row-sparse H. one uses matrix concentration inequalities (e.g., Matrix Bernstein, Hanson-We Hanson-Wright for quadratic forms of random variables, or specific results for random sampling from orthonormal systems) to show that UU tightly concentrated around its expectation.
P P ([ - [U,
& (2) S 2cxp(-c
(The exact form of the exponent depends on the specific inequality and properties of U, and the sam- pling P(i).) Assuming [E[| [U|H R || (which requires careful normalization or argument about the selection process effectively capturing the energy of k-sparse signals), this step shows that for a single sparse signal, the norm preserved with high probability M large enough.
Step 3: Covering Argument and Union Bound. The RIP must hold for all k-row-sparse matrices.
19

---

The set of k-dimmnniinnal sow-subspaces (where the non-zero rows of H can reside) is finite, number- ing (N) An e-net argument is used to discretize the unit sphere in each &o x d-dimensional subspace of row-sparse matrices. The size of such net is bounded by (C/e))at kdd Let P/uil Pjaii_suespace be the probability from Step that the RIP condition fails for a fixed k-row-sparse matrix (or subspace). Using union bound over all (K) choices of k row locations and then over the points in the E-net for each such subspace:
P(RIP fails for any k-row-sparse H) < (
(C/6) 2exp(-eppeee Mog/k)
We want this total failure probability to be small (e.g., < 11). Taking logarithms and using (x) S (eN/k))
A (ln(eN/k) + kdln(C/)) ci M < In(n/2)
For fixed og, C, and desired probability, this implies M Z c, (In(N/k) + dlIn(//c). is considered small or constant, the dominant term is k In(N/k). The learnable nature of U2 means we assume behaves like generic orthonormal system that is incoherent with the sparsity structure for these results to apply directly.
B.3 Error Bound
Theorem 3: Let ( be the output embeddings obtained by the standard GNN computation with full reconstruction at each layer. Let HLL) be the output embeddings, which performs sampling once at the input layer and reconstructs only at the output layer. Assume that the activation function a is Lipschitz continuous with Lipschitz constant Las and U satisfies the Restricted Isometry Property (RIP) of order & with constant 6% (i.e., 0 < 6x 1). Then, the error between HL) and ( can be bounded as:
H -H S (1
Lo En
|
where E T(L) (L)(L) is the reconstruction error at the output layer, and T. is the number of layers in the GNN.
between the output embeddings of the standard GNN computation. Assume the activation function is Lipschitz continuous with constant La such that
Proof: We aim to bound the error
( H
()) )
L.
H
x
A
H (0) Y.
F
Further, let the sampling matrix U satisfy the RIP of order ls with constant 8y, meaning
TUAH 2
(1 8k) H S
(1+5p) H
for all H with
H
< k. We also have H = U, (!) where H has at most non-zero rows.
1.sow We will prove by induction on / ..2,..., that
H H ||- S
Los 8x
H H
For the base case = 0, at the input layer, we have H0) ( and H HHO), The initial
error (0) (0) )
is assumed. Assume that for some / 2 0,
HHO 1
H0|
S 1
Los
O
H
Ox
We aim to show that
Lo
1+1
H (+1)
(+1)
(0)
H 00
F
0z
20

---

For YOSO, at the output layer 1 = L, we perform reconstruction: H = U,H( where H is obtained by solving
- $ +
H
min H
2
Due to the optimization and the RIP condition, have [H())
H
true
(b)
Cree | where
He is the true sparse representation of H and Cre 1-bb" H
26g
Since U is orthonormal,
implying Lipschitz continuity o, the error accumulates multiplicatively through L layers:
have H -
H trve
- H()) S
2 I-6u | Given the
| - H
H
{11_
La
L
H
H
8k
If the initial error H ( output layer, yielding
0, the primary source of error is from the reconstruction the
H
H
$
T.g
L
|
1 8x
C Detailed Related Work and Discussion
To address the efficiency issue of large-scale GNN training, schemes from different optimization perspectives have been proposed the algorithmic level [68] such as Historical Embedding [12] 20),
Linearization [I, Graph Condensation & Distillation [70, 64], and sampling-basee methods. The
scope of this paper focuses sampling-based methods.
Sampling-based Methods. A widely accepted criterion 40 divides current different sampling meth-
ods into three categories: node-wise sampling, layer-wise sampling, and subgraph-based sampling. depending on the granularity of the sampling operation during mini-batch generation.
(28) and others [65] [2] involves sampling at the individual node level. Each node's 's neighbors are selected according to one specific probability distribution. For example, GraphSage samples k hop neighbors at varying depths with the sampling sizes, for each depth tailored to optimize model performance. This approach, while simple and effective, has been criticized for its exponential increase in sampling time complexity as the number of GNN layers grows.
Node-wise Sampling. Pioneered by works such as GraphSage
Layer-wise Sampling. Developed to address the issue of exponential growth in computational complexity as GNNs depth increases in node-wise sampling, this method samples multiple nodes simultaneously in one layer. Techniques like FastGCN [13] reframe GNN loss functions as integral transformations and utilize importance sampling and Canto approximation to manage vari- ance. Following works, such as AS-GCN [31) and LADIES (72), focus on maintaining the sparse connections between sampled nodes to aid the convergence performance. However, these methods tend to introduce additional complexity and computational cost.
Subgraph-based Sampling. Forming mini-bacch through subgraph using expensive graph partition- ing { Cluster-GCN [15] partitions the full graph into clusters, sampling these clusters to create subgraphs for training batches. GraphSAINT [66] dynamically estimates sampling probabilities for nodes and edges to form subgraphs over which the full GNN model is trained. While these techniques typically improve model accuracy, they also lead longer training time.
Graph Condensation Distillation: Graph Condensation 23 and Graph Distillation [56] are methods designed to enhance computational efficiency. They achieve this by shrinking large-scale graphs into smaller ones while preserving essential structural and feature information. Alternatively, they replace complex GNN models with approximate and computationally simpler models, such as MLPs 44). However, these kinds of processes introduce additional computational overhead and may result in the loss of important information, potentially leading to a decrease model performance. For example, GCond [34) leverages a gradient matching framework to condense large graphs into significantly smaller synthetic graphs. optimizes node features as free parameters and models synthetic graph structures as functions of these features, ensuring that training trajectories on the condensed graph mimic those on the original graph. Another work, GC-SNTK (60), reformulates graph condensation as Kernel Ridge Regression (KRR) task, replacing computationally intensive
21

---

GNN training with Structure- basee Neural Tangent Kernel (SNTK). This approach captures both node feature interactions and structural relationships, enabling efficient graph condensation while maintaining strong generalization across GNN architectures.
Historical Embedding. This class of methods is not independent of sampling. Instead, they are often integrated with existing sampling strategies to improve specific aspects of sampling performance, such as estimated variance [[],, or expressiveness (0)] For example, VR-GCN [[2] utilizes historical embeddings within node-wise sampling. GNeeutoScale [20] incorporates the concept of historical sampling. Although historical embedding can be effective in terms of accuracy, it often comes with high computational complexity.
embeddings within subgraph-band
Linearization. This stream works [ [22 aims to simplify the training and inference processes by removing the nonlinear components (e.g., activation functions deep iterative propagation) inherent in traditional GNN models. This simplification achieves computational efficiency while preserving essential graph structure and feature information through linear transformations, i.e., SIGN [22 precomputations, i.e., iSVD [ Linearization techniques often involve precomputing wraph-based transformations (e.g., matrix products embeddings) and applying efficient optimization methods (e.g., truncated Singular Value Decomposition (SVD) or matrix factorization) to enable scalable training, particularly for large graphs.
22

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: Our main claim summarized in last paragraph in Section Section offer detailed explanations.
Section 3 and
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We state the limitations of our work in Section 4.2 and Appendix B.2
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
23

---

Justification:
All proofs are in Appendix B
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Please refer Appendix A
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
24

---

Answer: [Yes]
Justification: http://ghh....cooo//aaaoootataaa
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.cm
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ /pipp/.cc/pullc//uuuii wwwtii/gguie///eeeeceoocc CoodeSubeiiie ssi ssionnolli onnolicy)))) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Please refer to Section 5
Appendix
A
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, at least for the experiments that support main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation the standard error of the mean.
25

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of enrors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative eтror rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: Please refer to Appendix A.1
Guidelines:
The answer NA means that the paper does include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We respect the NeurIPS Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our work involves open- peen-source models and datasets. It does no impact the society at large, beyond improving our understanding of certain aspects of deep learning.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
26

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work poses no risk of misuse.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We are not shipping our code with any source code or binary files from any other existing libraries, there are no concerns over getting permission or including license. We did cite open-sourced libraries, e.g. PyTorch, in our paper.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URI.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g.. website). the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms use in package should be provided. For popular datasets, paperswithcone com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
27

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We released our code base with included readme files. We do not ship any source code or binary files from any other existing libraries.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: This work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: This work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
28

---

For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: LLM only used polish the text.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non standaad components.
Please refer to our LLM policy (https: for what should or should not be described.
29


Reviews:
[{"review_id": "23HHy2NQ5X", "reviewer": "Reviewer_tUDz", "summary": "The paper proposes a GNN training framework called You Only Spectralize Once (YOSO). They first project the features into a learnable orthonormal graph Fourier basis, and then use compressed sensing, which retains a subset of the spectral coefficients. Then the GNN computation is performed in the compressed spectral domain. Finally, they recover the full graph embeddings to the original domain at the output layer.", "questions": "1. The proposed method relies on the assumption that the graph features are sparse in the spectral basis. I am curious whether this assumption applies to graphs with noises or heterogeneous features. Is there any evidence or analysis to support this assumption?\n2. Can this method be adapted to the dynamic graphs? For example, after the matrix $U_l$ is trained, can it be reused or transferred when the graph is changing over time?", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n1. The proposed method achieves consistent training time reductions without major accuracy loss. The experiments are extensive and well-controlled.\n2. The paper offers a clear and well-motivated explanation of the problem and the solution. The background on spectral graph theory and compressed sensing makes it easier for readers to understand the core concepts.\n3. I appreciate Figure 2, which effectively summarizes YOSO.\n4. Each step in the framework is well-motivated and thoughtfully designed. For example, the method is grounded in compressed sensing theory and spectral graph signal processing. The RIP-based analysis provides a solid theoretical justification for the design. Also, the idea of using FISTA is a clever choice, effectively integrating traditional compressed sensing techniques with modern learning-based approaches.\n\nWeakness:\nSee questions.\n\n\nMinor:\n1. Line 17 ‘we prove that stable recovery by….’\n2. Line 156 ‘Eq (??)’", "was_revised": true, "final_justification": "I have read the rebuttal and other reviews. I maintain the original score.", "rebuttal": "We are grateful for your thorough review. We address your specific questions below.\n*****\n### Question 1: Assumption of Sparsity for Graphs\nWe would like to clarify that our proposed scheme, YOSO, does not rely on the assumption that graph features are sparse in pre-known spectral basis. This is a key distinction that enables YOSO to be applicable to any type of static graphs, including those with noisy or heterogeneous features. \n\nYOSO is designed to learn an optimal orthonormal basis $\\mathbf{U}_{l}$ that actively constructs a sparse representation of the graph features. This learning process is entirely data-driven and does not pre-suppose any inherent sparsity in the input graphs. As a result, YOSO remains effective even when such sparsity assumptions fail to hold.\n\nTheoritical analysis has been provided in the paper to indicate:\n- How the learning process of $\\mathbf{U} _ {l}$ is independent of feature sparsity?\n\nAs established in Theorem 2, this is achievable because our learned $\\mathbf{U} _ {l}$ is regularized and guided to be sufficiently incoherent with the sparsity basis. The learning of $\\mathbf{U} _ {l}$ is guided by our joint optimization objective $\\mathcal{L} _ {\\text{total}}$, which ensures that the sparse representation retains sufficient information for (mostly) lossless reconstruction of the original graph features. A key component of this objective is the reconstruction loss $\\mathcal{L} _ {\\text{recon}}$, which incorporates an $l _ {2,1}$-norm regularization term: $\\lambda || \\hat{\\mathbf{H}} _ {c} ^ {(L)*} || _ {2,1}$. This regularizer encourages the model to discover a transformation $\\mathbf{U} _ {l}$ that maps the input features into a sparse representation by penalizing non-sparse outputs. As a result, the training process explicitly promotes sparsity while preserving the fidelity of the original signal.\n- Why YOSO can recover the sparse graph representation back to original graphs?\n\nThe key insight is that successful reconstruction via Compressed Sensing (CS) depends on the Restricted Isometry Property (RIP) of the combined sensing and transformation operator $\\mathbf{\\Psi} = \\mathbf{\\Phi}\\mathbf{U} _ {l}$. As shown in Theorem 3, if the RIP condition holds, the error between our reconstructed output embeddings ($\\tilde{\\mathbf{H}} ^ {(L)}$) and the idealized full-graph embeddings $\\mathbf{H} ^ {(L)}$ is bounded: $|| \\tilde{\\mathbf{H}} ^ {(L)} - \\mathbf{H} ^ {(L)} ||_ F \\leq \\frac{L _ {\\sigma}}{1-\\delta_k}||E|| _ F$. This means the final error is controllably proportional to the CS solver's reconstruction error ($E$), which is directly minimized during training.\n*****\n### Question 2: On Applicability to Dynamic Graphs\nYOSO could be extended to dynamic graphs, depending on how the graph evolves over time.\n\nFor discrete-time dynamic graphs (snapshot-based) [1,2], where the dynamic graph is represented as a sequence of static snapshots, YOSO can be applied independently to each snapshot. This allows us to accelerate GNN training at each time step, making YOSO applicable to many real-world dynamic graph scenarios that process data in temporal batches.\n\nFor continuous-time dynamic graphs (event stream-based) [3,4], where graph structure and node features change continuously, applying YOSO may not improve the training efficiency. Since the core matrices $\\mathbf{U} _ {l}$ and $\\mathbf{\\Phi}$ are defined based on the global node set $N$, every change in the graph requires re-computation or adaptation of these matrices, which would introduce large overhead and diminish the computational advantages of YOSO.\n\nWe appreciate the reviewer’s insight and will incorporate this discussion into the limitations section of the paper to clarify the scope and potential extensions of our method.\n******\n### Minors\nThank you for catching these typos. We will add the following corrections in the final version:\n\nLine 17: The grammatical error will be corrected to read, \"...we prove that stable recovery is possible by showing that this whole process can satisfy the Restricted Isometry Property...\"\nLine 156: The reference to Eq.(??) refers to Eq.(1).\n\n*******\n### Reference\n[1] Pareja, Aldo, et al. \"Evolvegcn: Evolving graph convolutional networks for dynamic graphs.\" Proceedings of the AAAI conference on artificial intelligence. Vol. 34. No. 04. 2020.\n\n[2] You, Jiaxuan, Tianyu Du, and Jure Leskovec. \"ROLAND: graph learning framework for dynamic graphs.\" Proceedings of the 28th ACM SIGKDD conference on knowledge discovery and data mining. 2022.\n\n[3] Trivedi, Rakshit, et al. \"Dyrep: Learning representations over dynamic graphs.\" International conference on learning representations. 2019.\n\n[4] Rossi, Emanuele, et al. \"Temporal graph networks for deep learning on dynamic graphs.\" arXiv preprint arXiv:2006.10637 (2020)."}, {"review_id": "oQWae6sSgM", "reviewer": "Reviewer_mhBm", "summary": "This paper introduces YOSO (You Only Spectralize Once), a novel and practical approach to accelerating GNN training by avoiding repeated message passing. The core idea is to project graph signals into a learned spectral basis and use compressed sensing techniques to sparsely sample and reconstruct signals for downstream tasks like node classification and link prediction. The approach provides strong theoretical guarantees (RIP, error bounds), achieves \\~74% training time reduction, and matches or slightly underperforms baselines in accuracy across five benchmark datasets.", "questions": "1. How can a practitioner assess whether their dataset satisfies the spectral sparsity assumption needed for successful reconstruction? Are there any heuristics or automatic checks?\n2. Given that \\$\\mathbf{U}\\_l\\$ is learned during training, how do you ensure that the RIP condition is preserved or approximately satisfied?\n3. Have you considered whether the learned spectral basis can adapt incrementally to graph topology changes, or would retraining be required?", "limitations": "1. The method assumes spectral sparsity in the node feature signals, which may not generalize well to graphs with dense or noisy spectral representations (e.g., social networks, small-world graphs). The paper would benefit from practical guidance or automatic checks for this assumption before deployment.\n\n2. While the method excels on static graphs, its extension to dynamic or evolving graphs remains unclear. If the graph topology changes over time, the learned spectral basis may no longer be valid, potentially requiring full retraining. This could limit real-world applicability in streaming or online settings.\n\n3. The current evaluation is restricted to transductive learning. It is not evident how the framework would perform on inductive node classification or in few-shot graph scenarios, where node embeddings need to generalize to unseen subgraphs.\n\n4. The reconstruction module (decoder) plays a crucial role in performance, but its architecture and training stability are underexplored. In particular, the decoder’s ability to recover clean signals across different graph structures is not analyzed in depth.\n\n5. The approach requires the initial spectralization step to be performed once, but this may still involve expensive eigen decomposition or approximation for large graphs, depending on the implementation. Further analysis on this one-time cost would improve transparency.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 3, "strengths_and_weaknesses": "### **Strengths:**\n\n#### **Technical Quality:**\n\n* Provides rigorous theoretical backing for the reconstruction process, including proofs for the sensing matrix’s full-rank property and RIP satisfaction.\n* The integration of learnable GFTs with compressed sensing is implemented carefully and supported by mathematical justification and empirical results.\n* Training speed improvements are consistent and significant across tasks and datasets.\n\n#### **Significance:**\n\n* The work directly addresses a major bottleneck in large-scale GNN training — computational inefficiency — with a conceptually novel and practical solution.\n* Proposes a new paradigm shift from spatial-domain sampling (used in methods like GraphSAINT or Cluster-GCN) to spectral-domain sparse sampling.\n\n#### **Originality:**\n\n* While compressed sensing and GFTs are established fields, their combination with learnable spectral bases in GNNs is novel.\n* The “you only spectralize once” conceptually reframes how feature propagation is handled — offering a fresh direction for GNN efficiency research.\n\n\n* The paper is well-organized and the core idea is clearly presented.\n* Appendices provide implementation details and proofs, supporting reproducibility.\n\n---\n\n### **Weaknesses:**\n\n* The method relies on spectral sparsity, which may not hold in all graph types (e.g., complete graphs, random graphs). More guidance or diagnostics for real-world practitioners would help.\n* There is limited discussion on dynamic or time-evolving graph settings, where spectral bases may evolve.\n* Ablation experiments isolating the contributions of GFT learning vs. sampling vs. decoder reconstruction could strengthen the empirical section.\n* A minor typo: Equation reference on line 156 is not rendered correctly in the PDF.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the insightful review. We address the weaknesses, questions and the limitations as below.\n\n***\n### Weakness 1: On the Assumption of Sparsity for Graphs and Practical Guidance\nAs our response to Reviewer tUDz's Question 1, YOSO does not rely on pre-known spectral sparsity. This is a key distinction that enables YOSO applied any type of static graphs. On the contrary, YOSO learns an optimal orthonormal basis $\\mathbf{U}_l$ that actively constructs a sparse representation of the graph features. Learning process is entirely data-driven and does not pre-suppose any inherent sparsity in the input graphs. Therefore, even on a graph with a dense spectrum (like a complete or random graph), if node features themselves have a compressible structure (e.g., nodes belong to a few classes), YOSO is designed to learn a basis that captures this structure sparsely.\n\nGuidance for Practitioners: People do not need to pre-diagnose graph for spectral sparsity due to the above discussion. YOSO is designed to automatically discover compressible data structures during training. Its applicability is broad, precisely because it creates an efficient compressed domain rather than assuming one exists beforehand.\n\n***\n### Weakness 2: On Applicability to Dynamic Graphs\nYOSO is possible to accelerate training for dynamic graphs, depending on how the graph evolves over time (Please also refer to Reviewer tUDz's Question 2).\n\nYOSO can achieve shorter training time for discrete-time (snapshot-based) dynamic graphs [1,2,3,4], which covers a wide range of real-world scenarios [5]. YOSO can be applied independently to each snapshot, which accelerates the training process.\n\nWhile for continuous-time (event-based) graphs [6,7], YOSO may not be able to obtain the training time reduction since every change in the graph requires re-computation of global basis.\n\nThanks for raising this question, and we will add the discussion to the limitation section.\n\n***\n### Weakness 3: On an Ablation Study of YOSO's Components\nWe appreciate the reviewer’s suggestion that ablation experiments isolating the contributions of GFT learning ($\\mathbf{U}_{l}$), sampling (sensing $\\mathbf{\\Phi}$), and decoder (reconstruction process) could strengthen the empirical section. However, in our current formulation, these three components are tightly coupled, and their contributions cannot be meaningfully disentangled without fundamentally altering the method, as explained below:\n- GFT learning ($\\mathbf{U}_l$) is driven by the reconstruction loss, which is computed by the decoder. The gradients from this loss directly update $\\mathbf{U}_l$, meaning the learned basis is specifically optimized to facilitate faithful reconstruction by the decoder. Without the decoder, the GFT learning objective becomes ill-defined.\n- Decoder (reconstruction, using our FISTA-based solver) solves the inverse problem induced by the compressed measurements produced by the sensing matrix $\\mathbf{\\Phi}$. Its performance is intrinsically tied to how $\\mathbf{\\Phi}$ samples the sparse representation, and thus cannot be evaluated independently.\n- The GFT $\\mathbf{U}_{l}$ and sensing matrix $\\mathbf{\\Phi}$ are dependent with each other. The GFT learns to make the signal sparse, which is the necessary precondition for the compressed sensing via $\\mathbf{\\Phi}$ to be effective. One component creates the condition (sparsity) that the other is designed to exploit.\n\n***\n### Weakness 4: Typo\nThe reference on line 156 should point to Eq.(1). We'll fix this.\n\n***\n### Question 1: Assessing Sparsity and Reconstruction of Datasets\nPractitioners do not need to perform any pre-assessment of their datasets/graphs for spectral sparsity. Our method is designed to be broadly applicable without such checks. The reason is that YOSO does not rely on the input graph having an inherently sparse structure. Instead, it learns an optimal orthonormal basis ($\\mathbf{U}_{l}$) that creates a sparse representation of the node features for the specific task at hand (Please also refer to our response to Reviewer tUDz's Question 1 and the response to Weakness 1).\n\nSuccessful reconstruction is guaranteed by satisfying the Restricted Isometry Property (RIP), which is a core part of YOSO's design, as explained below:\n- The GFT learning process, guided by the $l_{2,1}$ regularization in our loss function, explicitly trains $\\mathbf{U}_{l}$ to find a basis where the node features can be represented sparsely.\n- Our specialized sensing matrix ($\\mathbf{\\Phi}$), which combines graph-aware structure and randomness, is designed to work in concert with the learned $\\mathbf{U}_{l}$. As established in our Theorem 2, this joint design ensures that the RIP condition is satisfied with high probability.\n\n***\n### Question 2: Preserving the RIP Condition with a Learned Basis\nRIP is satisfied by co-adapting the learnable basis with the fixed sensing matrix. This co-adaptation is achieved through our proposed joint optimization objective:\n- The sensing matrix $\\mathbf{\\Phi}$ is constructed once with a random component. This design ensures it has good RIP-like properties for generic orthonormal bases, making it a robust all-purpose sensor.\n- The basis  $\\mathbf{U} _ {l}$ does not evolve randomly and it is updated via gradients from the total loss $\\mathcal{L} _ {\\text{total}}$. Two key components of this loss guide its evolution: (a) The sparsity regularizer ($l_{2,1}$-norm) pushes $\\mathbf{U} _ {l}$ to become a basis that makes the signal sparse; (b) The data consistency term ($||\\mathbf{T} ^ {(L)} - \\mathbf{\\Phi}\\mathbf{U} _ {l}\\hat{\\mathbf{H}} _ {c} ^ {(L)*}|| _ {F}^{2}$) penalizes any changes to $\\mathbf{U}_{l}$ that make the signal difficult to reconstruct from the measurements taken by the fixed $\\mathbf{\\Phi}$.\n\n***\n### Question 3: Incremental Adaptation vs. Retraining for Topology Changes\nPlease refer to the response to Weakness 2.\n\n***\n### Limitation 1: Assumption of spectral sparsity in node features\nPlease refer to the response to Weakness 1 and Question 1.\n\n***\n### Limitation 2: Applicability to dynamic or evolving graphs\nPlease refer to the response to Weakness 2.\n\n***\n### Limitation 3: Generalization to inductive and few-shot scenarios\nThank you for raising this point. YOSO is currently transductive. Both $\\mathbf{U}_{l}$ and $\\mathbf{\\Phi}$ depend on the full node set of size $N$, so they cannot process new nodes at inference.\nTransductive settings still cover many important applications [8–11], which motivated our design.\nGeneralizing YOSO to inductive settings is an important future direction, and we will discuss this in the paper.\n\n***\n### Limitation 4: Underexplored decoder design and stability\nWe're happy to provide more details on the reconstruction module's design and its robustness.\n- Ability of Recover Clean Signals vs. Graph Structure\n\nThe decoder's (reconstruction process) ability to recover clean signals is not directly dependent on the graph's structure but on a more fundamental condition: whether the Restricted Isometry Property (RIP) is satisfied. Our framework is designed to ensure this holds true with high probability regardless of the graph topology. We have formally proven this with Theorem 2 in Appendix C.2.\nBesides, we also provide direct empirical evidence in Figure 6. The heatmap visualizes the near-zero absolute difference between original and reconstructed embeddings on the ogbn-products dataset, confirming the decoder's ability to achieve high-fidelity recovery in practice.\n- Decoder Architecture and Stability\n\nIt's important to clarify that our decoder is not a learnable function but an implementation of the FISTA algorithm [7], a well-established and provably convergent iterative solver. This directly addresses the architecture and stability concerns: (a) Architecture: The architecture is a standard optimization algorithm, widely used for solving $l_{2,1}$-regularized problems like the one in our framework; (b) Stability: As FISTA is a stable and convergent algorithm [7], its stability during training is not a primary concern.\n***\n### Reference\n[1] Pareja, Aldo, et al. \"Evolvegcn: Evolving graph convolutional networks for dynamic graphs.\" Proceedings of the AAAI conference on artificial intelligence. Vol. 34. No. 04. 2020.\n\n[2] You, Jiaxuan, et al.. \"ROLAND: graph learning framework for dynamic graphs.\" Proceedings of the 28th ACM SIGKDD conference on knowledge discovery and data mining. 2022.\n\n[3] Seo, Youngjoo, et al. \"Structured sequence modeling with graph convolutional recurrent networks.\" International conference on neural information processing. Cham: Springer International Publishing, 2018.\n\n[4] Bonner, Stephen, et al. \"Temporal neighbourhood aggregation: Predicting future links in temporal graphs via recurrent variational graph convolutions.\" 2019 IEEE international conference on big data (Big Data). IEEE, 2019.\n\n[5] Zheng, Yanping, Lu Yi, and Zhewei Wei. \"A survey of dynamic graph neural networks.\" Frontiers of Computer Science 19.6 (2025): 196323.\n\n[6] Trivedi, Rakshit, et al. \"Dyrep: Learning representations over dynamic graphs.\" International conference on learning representations. 2019.\n\n[7] Rossi, Emanuele, et al. \"Temporal graph networks for deep learning on dynamic graphs.\" arXiv preprint arXiv:2006.10637 (2020).\n\n[8] Zhu, Xiaojin, et al. \"Semi-supervised learning using gaussian fields and harmonic functions.\" Proceedings of the 20th International conference on Machine learning (ICML-03). 2003.\n\n[9] Zhang, Yan-Ming, et al. \"Transductive learning on adaptive graphs.\" Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 24. No. 1. 2010.\n\n[10] Wang, Jun, et al. \"Active microscopic cellular image annotation by superposable graph transduction with imbalanced labels.\" 2008 IEEE Conference on Computer Vision and Pattern Recognition. IEEE, 2008.\n\n[11] Valko, Michal, et al. \"Online semi-supervised learning on quantized graphs.\" arXiv preprint arXiv:1203.3522 (2012)."}, {"review_id": "TpRb5zvnX6", "reviewer": "Reviewer_zwBn", "summary": "This paper introduces YOSO (You Only Spectralize Once), a novel training scheme for GNNs that leverages spectral sparsity and compressed sensing to accelerate training while maintaining competitive accuracy. The key insight is that node features/embeddings in real-world graphs exhibit sparse representations in the Graph Fourier domain. YOSO projects input features onto a learnable orthonormal Graph Fourier basis Uℓ only once, retaining only M≪N spectral coefficients via a fixed sensing matrix Φ. All GNN computations occur in this compressed M-dimensional subspace. At the output layer, full-graph embeddings are reconstructed.", "questions": "- In line 156, unknown equation indicator.\n- The authors should elaborate \"Uℓ can be initialized as a random orthogonal matrix (e.g., via QR decomposition of a Gaussian matrix) or using other Stiefel manifold initialization techniques\".\n- The construction of Uℓ still needs matrix decomposition like QR decomposition? Please explain why this is a better choice over eigendecomposition.\n- Around line 242, the element-wise product is better denoted by \\odot.\n- The statement \"GNNs iteratively apply the non-linear activation functions. If transform embeddings into spectral domain and later convert them back to original domain (for performing the downstream task), but only use a simple inverse transform (e.g., U^−1), thus, these nonlinearities prevent perfect recovery of original embeddings.\" seems problematic. Please explain why nonlinearities prevent perfect recovery?\n\n\n[1] Specformer: Spectral Graph Neural Networks Meet Transformers\n[2] A New Perspective on the Effects of Spectrum in Graph Neural Networks", "limitations": "Yes", "rating": 3, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "#### Strengths\n\n- The integration of learnable spectral transformations with compressed sensing for GNN acceleration is novel. Unlike prior sampling/pruning methods, YOSO avoids repeated spatial operations by operating entirely in a compressed spectral domain after a one-time projection.\n- Demonstrates significant speedups while preserving accuracy across diverse tasks (node/link classification) and datasets. Ablation studies confirm robustness w.r.t. M.\n\n#### Weaknesses\n\n- Existing GNNs that require explicit (truncated) eigendecomposition also do eigendecomposition only once at the data preprocessing step, e.g. Specformer [1] and Spec-GN [2]. Given so, the authors need to clarify their main argument \"You Only Spectralize Once\".\n- Experiments focus on GCN. Extensions to other SOTA GNN architectures is not validated.\n- The spectral sparsity assumption may not hold for all graph types. The authors are encouraged to provide empirical or theoretical evidence of spectral sparsity assumption.\n- The Universal Sensing Matrix $\\Phi\\in\\mathbb R^{M\\times N}$ is essential to the main goal of this paper, i.e., compression. But the construction of $\\Phi$ in Section 4.3 is not well motivated.", "was_revised": true, "final_justification": "Although the proposed approach aims to speed up GNN training, it still relies on $O(n^3)$ matrix decomposition in preprocessing, which is the main restriction of computational efficiency rather than the layer-wise GNN computations in training. The so-called \"You Only Spectralize Once\" is misleading, given that existing approaches, like Specformer, etc, also do spectral decomposition once in preprocessing. Also, the proposed learnable basis is also extensively studied by existing work. The authors need to properly contextualize their work with existing work.", "rebuttal": "Thank you for valuable comments. Please find our response to the listed weaknesses and questions in order.\n******\n### Weakness 1：Clarification on the “You Only Spectralize Once”\nWe thank the reviewer for pointing out the need to clarify our central message. While it is true that prior works like Specformer and Spec-GN also perform spectralization (i.e., eigendecomposition) once during preprocessing, our use of “You Only Spectralize Once” (YOSO) differs in two key ways:\n\n1. Avoiding Truncated or Fixed Spectral Bases: YOSO does not rely on a precomputed, truncated eigenbasis. Instead, it employs a learnable orthonormal basis $\\mathbf{U}_{l}$ that is jointly optimized with the GNN during training. This addresses the limitations of fixed eigenvectors, which may not align well with the learning objective or generalize across layers.\n2. One-Time Spectral Projection with Compact Processing: YOSO’s pipeline includes a single spectral projection at the input layer and a single reconstruction at the output layer: entire GNN processing happens in a compressed domain, eliminating repeated transformations or spectral filtering at intermediate layers. In contrast, works like Spec-GN still operate in the spectral domain layer-wise, incurring higher computational complexity during training.\n\nWe will clarify this distinction in the final version and revise the wording to emphasize our contribution as a learnable one-time projection and reconstruction framework, as opposed to static preprocessing-based spectralization.\n******\n### Weakness 2：Limited evaluation beyond GCN\nYOSO can be applied to any types of transductive GNN architecture like GAT.\n\nThe reason is that YOSO's core mechanism is decoupled from the GNN's specific message-passing function. The YOSO pipeline operates as follows:\n1. Pre-Processing: At the input layer, YOSO takes the full $N\\times d$ feature matrix and projects it into a compressed $M\\times d$ representation, where $M\\ll N$.\n2. GNN Computation: The GNN model then performs all its layer-wise computations (e.g., aggregation, non-linearities) entirely within this compact $M$-dimensional space.\n3. Post-Processing: At the output layer, YOSO reconstructs the full $N$-dimensional embeddings from the GNN's final M-dimensional output.\n\nThis wrapper approach means that the specific architecture of the GNN does not matter. The GNN simply needs to operate on an input tensor of size $M\\times d_{in}$ and produce an output of size $M\\times d_{out}$. This is compatible with virtually any transductive architecture.\n*******\n### Weakness 3: Assumption of graph sparsity\nYOSO's design does not depend on pre-known spectral sparsity of graphs. Instead, our framework is designed to learn an optimal basis that actively creates a sparse representation for the node features (Please also refer to our response to Reviewer tUDz's Question 1, Reviewer mhBm's Weakness 1 and Question 1).\n\nThe followings are the theoretical and empirical evidence supporting our claim:\n- Theoretical Justification. The core of our method is a joint optimization objective (Eq.(6)) that includes an $l_{2,1}$-norm regularizer on the spectral coefficients. This regularizer explicitly penalizes non-sparse solutions, forcing the model to learn a basis $\\mathbf{U}_{l}$, that is uniquely tailored to sparsify the features of the given dataset. This makes our framework adaptive and robust, even on graph types that do not have an inherently sparse spectrum.\n- Empirical Evidence. In our ablation study, particularly Figure 6. This figure shows the high-fidelity reconstruction of node embeddings from a highly compressed representation ($M\\ll N$). According to compressed sensing theory, such an accurate recovery is only possible if the node embeddings were successfully transformed into a sparse-enough representation by our learned basis.\n*****\n### Weakness 4: Motivation of the construction of $\\mathbf{\\Phi}$\nThank you for your comments on the motivation description\n\nThe central challenge is to create a single, fixed sensing matrix $\\mathbf{\\Phi}$ that works robustly with a spectral basis that is learned and evolves during training. Since we cannot know the optimal basis ahead of time, we need a universal sensor. Our solution is a hybrid construction: $\\mathbf{\\Phi}=\\mathbf{S} _ {struct}\\otimes \\mathbf{\\Sigma}_{rand}$, which is designed to satisfy two crucial and complementary objectives:\n1. Theoretical Guarantees via Randomness ($\\mathbf{\\Sigma} _ {rand}$): This random component ensures that the reconstruction is theoretically sound. Compressed sensing theory proves that random matrices are excellent universal sensors because they are incoherent with any sparse basis with high probability. This randomness is essential for satisfying the Restricted Isometry Property (RIP), which guarantees that we can faithfully recover the signal regardless of the specific basis $\\mathbf{U}_{l}$ the model ultimately learns.\n2. Graph-Aware Efficiency via Structure ($\\mathbf{S}_{struct}$): A purely random approach can be inefficient. To capture the most important information with a smaller number of measurements ($M$), this structural component provides graph-awareness. It guides the compression process by sampling spectral modes based on importance scores derived from the graph Laplacian's eigenvalues. This ensures that high-energy, information-rich spectral components are more likely to be preserved.\n\nIn summary, this two-part design creates a single, fixed sensing matrix that is both provably robust (from randomness) and structurally informed (from graph-aware sampling). This hybrid approach is what enables efficient and accurate reconstruction, which is central to YOSO's success. We will revise Section 4.3 in the final version to make this motivation explicit.\n******\n### Question 1 and Question 4\nThank you for pointing them out. The reference on line 156 should be referred to Eq.(1). We will correct the equation reference and notation in the final version.\n******\n### Question 2: Initialization of $\\mathbf{U}_{l}$\nWe thank the reviewer for requesting further elaboration on the initialization of the learnable spectral basis $\\mathbf{U}_{l}$. \n\nBecause $\\mathbf{U} _ {l}$ is constrained to be an orthonormal matrix (i.e., $\\mathbf{U} _ {l}^{\\top}\\mathbf{U}=\\mathbf{I}=\\mathbf{U}\\mathbf{U} _ {l}^{\\top}$), its parameters must be initialized on the Stiefel manifold. In our work, we use a simple and standard procedure to achieve this: We first generate a random matrix $\\mathbf{A}\\in \\mathbb{R}^{N \\times N}$ by sampling its entries from a standard normal distribution. We then perform a QR decomposition to get $\\mathbf{A} = \\mathbf{QR}$, where $\\mathbf{Q}$ is an orthonormal matrix. We initialize our learnable basis by setting $\\mathbf{U}_{l} = \\mathbf{Q}$. This is a well-established technique for uniformly sampling from the space of orthogonal matrices.\n\nWe will revise the manuscript to include this clarification for completeness and reproducibility.\n*******\n### Question 3: QR vs. Eigendecomposition\nAlthough both QR decomposition and eigendcomposition can be used in $\\mathbf{U}_{l}$ construction, QR decomposition provide the following advantages for our YOSO design. \n- Numerical Stability and Accuracy for Linear Systems. The Graph Fourier Transform can be viewed as a linear operation. For solving problems related to linear systems, QR decomposition is well-regarded for its numerical stability and accuracy, particularly when dealing with matrices that may be ill-conditioned [1].\n- Applicability to General Matrices. Eigendecomposition, especially the Spectral Theorem which guarantees an orthonormal basis of eigenvectors, applies only to specific classes of matrices (e.g., symmetric or normal matrices). However, the optimal basis $\\mathbf{U}_{l}$ learned by YOSO is not constrained to follow such a pattern, it is a general orthonormal matrix adapted for the task. Therefore, QR decomposition, which can be applied to any matrix to produce an orthonormal basis, is a more suitable and general tool for our initialization purposes [2].\n*******\n### Question 5: Effect of Nonlinearities on Spectral Recovery\nThank you for this question regarding the impact of nonlinearities on the recovery of original embeddings from the spectral domain. We are happy to clarify the reasoning behind our statement.\n\nPerfect reconstruction after a forward Graph Fourier Transform, a non‑linear activation, and a simple inverse transform is impossible, because the non‑linearity breaks the algebraic symmetry that guarantees invertibility for purely linear operations.\n\nThe Graph Fourier Transform (GFT) $\\mathbf {U}^{\\top}$ and its inverse $\\mathbf{U}$ are linear.  All classic reconstruction guarantees hold only when every step between the forward and inverse transforms remains linear.  The moment a non‑linear activation $\\sigma(\\cdot)$ intervenes, the transform and the activation cease to commute: $\\mathbf{U}^{\\top}\\sigma(\\mathbf{H})\\neq \\sigma(\\mathbf{U}^{\\top}\\mathbf{H})$.\n\nThis inequality means that non-linearities mix information across frequencies in a complex way. If we compress the signal in the spectral domain (by discarding coefficients), this mixed information is irretrievably lost. A simple linear inverse transform ($\\mathbf{U}$) cannot undo this non-linear mixing to perfectly recover the original signal. This accumulating information loss is precisely what YOSO avoids by performing all non-linear operations within the compressed domain and only reconstructing once at the very end.\n\nWe will revise the manuscript to clarify this point more explicitly and avoid any misleading interpretation.\n*******\n### Reference\n[1] Higham, Nicholas J. Accuracy and stability of numerical algorithms. Society for industrial and applied mathematics, 2002.\n\n[2] Gander, Walter. \"Algorithms for the QR decomposition.\" Res. Rep 80.02 (1980): 1251-1268."}]

Author rebuttal:

Meta-review: After reading the paper, the reviews, and the discussion, I have decided to recommend accepting this submission. One of the main concerns raised by the reviewers was the sparsity assumption, and it seems to be addressed during the rebuttal period. While I agree with the reviewer zwBn that the paper can be further improved, I think that there is enough novelty to warrant acceptance.
Decision: Accept (poster)