YOSO: You-Only-Sample-Once via Compressed Sensing for Graph Neural Network Training

Authors: Yi Li, Zhichun Guo, Guanpeng Li, Bingzhe Li
Primary area: learning on graphs and other geometries & topologies
Keywords: Sampling, Graph Neural Network, Compressed Sensing

Abstract:
Graph Neural Networks (GNNs) have become essential tools for analyzing structured data across various domains.  In GNNs, sampling is critical for reducing training latency by limiting the number of nodes processed during training, especially for large-scale applications. However, as the demand for better prediction performance increases, existing sampling algorithms become more complex, introducing significant overhead in the training process. To address this issue, we introduce YOSO (You-Only-Sample-Once), an algorithm designed to achieve highly efficient training while preserving prediction accuracy in downstream tasks. YOSO proposes a compressed sensing-based sampling and reconstruction framework, where nodes are sampled once at the input layer, followed by a lossless reconstruction at the output layer during each epoch. This approach not only avoids costly computations, such as orthonormal basis, but also guarantees high-probability accuracy retention, equivalent to full node participation. Experimental results on both node classification and link prediction tasks demonstrate the effectiveness and efficiency of YOSO, reducing GNN training by an average of around 75% compared to state-of-the-art methods, while maintaining accuracy on par with top-performing baselines.

Decision: reject
Reviewer scores: 5, 6, 6, 6

Reviews and discussion:
<thread>
creation date:
1730097024190

thread_type:
official_review

<thread_object>
creator: reviewer_vrqu

<content>
summary:
This paper introduces YOSO, a novel algorithm for efficient GNN training using a compressed sensing approach. GNNs are crucial for analyzing structured data, but existing sampling methods often introduce significant computational overhead. YOSO addresses this by sampling nodes only once at the input layer and using a nearly lossless reconstruction at the output layer for each epoch. This method reduces training time by about 75% compared to state-of-the-art techniques while maintaining high accuracy.

strengths:
1. The concept of "sampling only once" presented in this paper is really interesting and novel, offering a fresh perspective on GNN sampling.
2. The author provides theoretical support to guarantee the effectiveness of YOSO, which is very convincing.
3. The author provides code to ensure the reproducibility of the paper's results.

weaknesses:
1. According to Formula 1, the generation of $\mathbf{T}$ is closely related to the feature matrix $\mathbf{H}$. However, in YOSO, $\mathbf{U}$ is randomly initialized, and the generation of $\mathbf{\Phi}$ is only related to the graph structure. Does this approach overlook too much feature information?
2. The methodology section of the paper lacks a description of critical steps. The resulting representations $\mathbf{Z}$  do not have the scale as the input matrix $\mathbf{X}$. So, how should the nodes in $\mathbf{X}$ correspond to the representations in $\mathbf{Z}$? How can we obtain the representations for all nodes in the entire graph? What nodes' loss does $L_{GNN}(\mathbf{Z})$ calculate? Does this mean that it is necessary to sample nodes from the training set?
3. Some important related works are missing. The paper only discusses related work on graph sampling, while relevant works on Compressed Sensing are not included. What are the objectives and common practices of this technique? Why can it be applied to the GNN sampling problem? These questions need further discussion.
4. The mathematical notation in the paper is confusing, making it difficult to understand. For example, in line 155, $\hat{\mathbf{H}}$ should be $\hat{\mathbf{H}}^{(l)}$; in line 159, $\mathbf{U}^{\top}$ should be ${\mathbf{U}^{(l)}}^\top$; and in Equation 2, $\min$ should be $\arg \min$.

questions:
Please refer to the points I mentioned in the weakness part.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730721489640

thread_type:
official_review

<thread_object>
creator: reviewer_9rsa

<content>
summary:
This paper presents YOSO (You-Only-Sample-Once), an efficient algorithm designed to streamline graph neural network (GNN) training while maintaining predictive accuracy in downstream tasks. YOSO addresses the high computational overhead in existing sampling methods by introducing a novel compressed sensing-based framework. In this framework, nodes are sampled once at the input layer and then losslessly reconstructed at the output layer each epoch, eliminating costly operations like orthonormal basis calculations and ensuring high-probability accuracy retention comparable to full-node sampling. Experimental evaluations demonstrate YOSO’s effectiveness in reducing GNN training time by approximately 75% on tasks such as node classification and link prediction, achieving accuracy levels similar to leading baselines. This approach positions YOSO as a resource-efficient alternative with potential for significant performance benefits in large-scale GNN training.

strengths:
1. The paper introduces a fairly novel method to train the GNNs, which is a significant as per the details provided.
2. The mathematical representation provided is fair enough to make the readers understand.
3. The results and the studies are significant to show the efectiveness of the framework. As per the problem, large-scale datasets are considered for the study, which is also appreciable.

weaknesses:
1. The work is evaluated for only two tasks, i.e., Node classification and link prediction, in which the link prediction results are also just comparable to the baselines.
2. The performance metrics considered is accuracy and loss only. There should me more like F1-score as there may be data bias in case of such datasets.

questions:
1. According to the article, YOSO operates on sparse data rather than the original dataset. Could this approach lead to potential information loss?
2. If there is data bias, how will it handle the same?
3. As the framework is tested for just two tasks, will it be generic for all type of graph related downstream tasks?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730797937807

thread_type:
official_review

<thread_object>
creator: reviewer_zwan

<content>
summary:
This paper introduces YOSO, a novel compressed sensing-based sampling approach for Graph Neural Networks (GNNs) that samples nodes only once per training. By performing a one-time sampling at the input layer and a lossless reconstruction at the output layer, YOSO aims to minimize the computational burden associated with repeated sampling in GNN training. The proposed method is evaluated on node classification and link prediction tasks, demonstrating significant training time reduction (up to 75%) while maintaining comparable accuracy to several baselines.

strengths:
1.	The paper is well-organized and easy to follow. It provides a thorough background on GNNs and compressed sensing, equipping readers with the necessary foundational knowledge. Additionally, the authors offer a detailed discussion on the use of compressed sensing for sampling and the proposed YOSO algorithm.
2.	The compressed sensing-based sampling method is both novel and effective in reducing computational overhead associated with sampling.
3.	The authors present experiments demonstrating YOSO's efficiency on large-scale graph datasets across multiple tasks, supporting the practical impact of their approach.

weaknesses:
1.	The motivation for using compressed sensing-based sampling is unclear. Graph distillation or condensation methods could also be feasible for generating smaller graph datasets while preserving data distribution. What specific advantages does compressed sensing sampling offer over graph condensation?
2.	Compressed sensing relies on the Restricted Isometry Property (RIP) for accurate reconstruction. In the context of graph neural networks, it is unclear if RIP holds for the input feature matrix, representation matrix, and output matrix. Preliminary experiments would be beneficial to validate RIP applicability within GNNs.
3.	This paper proposes using an unknown $U^{(l)}$ and an universal $\Phi$ to enhance the efficiency. However, a key question remains: does the universal $\Phi$ really exist? More justification is needed. Additionally, what’s the disadvantage compared with layer-wise $\Phi$? Is the accuracy loss significant? 
4.	For Line 257, I am confused on the forward propagation. Suppose the shape of $\Phi$ is M*N, the normalized Laplacian matrix is N*N, trainable parameters W is d*d, $T^{(l-1)}$ is M*d. It seems that the forward equation is incorrect with an unmatched shape. Is it like $\Phi A \Phi^\top$ to transform the adjacency matrix?
5.	The limitation discussion of YOSO is missing. (1) is YOSO robust over the initialization of sampling matrix $\Phi$? What’s the performance on a random initialized measurement matrix? Why do the authors design a handcraft sampling matrix? (2) YOSO requires more memory during GNN training? What’s the memory consumption of YOSO compared with other methods? 

I am open to revising my score if the authors can address my concerns.

---------------------------------------Post Rebuttal----------------------------------

After reading the response, I increase the score to 6.

questions:
Please see the weakness part.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730864087455

thread_type:
official_review

<thread_object>
creator: reviewer_yg8e

<content>
summary:
Paper is interested in sampling graphs, for the purpose of training graph neural networks, in cases where the input graph is large. Rather than taking gradient-steps using entire graphs, sampling-based training of GNNs can take gradient steps using subgraphs (more compute efficient).

Paper shows while indeed existing graph-sampling methods *can* scale learning onto larger graphs, *however*, they significant time in sampling itself (i.e., data prep) rather than on gradient calculation (i.e., training).

strengths:
* GNNs are indeed popular architectures, solving problems across many domains. Even though there are many methods are proposes to speed-up training of GNNs, making things even faster, should realize some advantages.

* Their sampling method takes less time than competition, yet reaches SOTA metrics.

* Their sampling is computed only once, whereas competing methods draw subgraph samples for every input example every epoch. Since sampling time is significant (often the dominant), then sampling only once significantly saves resources.

weaknesses:
# Related Work

* Paper does not address non-sampling-based methods for speeding-up GNNs. At least, they should be mentioned in related work (IMO). One missed family is historical embeddings (e.g., https://arxiv.org/abs/1710.10568, https://arxiv.org/abs/2106.05609, https://arxiv.org/abs/2305.12322), another family is some "linearization" of models (a.k.a "decoupled" GNNs), e.g., https://arxiv.org/pdf/1902.07153, https://arxiv.org/abs/2004.11198, https://arxiv.org/abs/2111.06312)

* Other methods also sample-once. E.g., ClusterGCN.

# Sampling is inherently parallelizable
 
Paper is founded upon a statement that sampling takes more time than the actual training step. I believe the statement is correct (because the graph may be large and does not fit in memory). However, sampling is trivially distributable -- in fact, many papers, such as, PinSAGE, TFGNN, ..., propose and implement distributed or multi-threaded sampling. I think this could also be mentioned in the related work.


# Possible Writing Improvements

* First line of Intro: "analyzing" should probably become "modeling"
* The abstract says "lossless" compression but line 90 says "nearly lossless". It is better to be consistent.
* The term "embedding matrix" is used a few times in the first 2 pages, without clear definition of what it is -- is it the node input features? is it the hidden representations (between layers)? Is it the output of the GNN? I feel that it is all of those [but only after reading a couple of more pages].


# Missing analysis

The paper talks about bias and variance. This is usually done **either** in the forward pass -- let $\widetilde{z}$ be the latent values obtain via the graph sample and $\mathbf{z}$ be the latent values when full graph is used, the zero-biased analysis should show $\mathbb{E}[\widetilde{z}] = \mathbf{z}$; or in the backward pass e.g. $\mathbb{E}[\frac{\partial loss(\widetilde{z})}{\partial \theta}] = \frac{\partial loss(\mathbf{z})}{\partial \theta}$. This paper does neither of those, nor it shows bounds on the variance of these quantities. I suggest the authors remove bias&variance arguments or else show some analysis to back the arguments.

# Math inaccuracies
* Adjacency matrix is square (N x N). How is it multiplied on the right by the model parameter matrix? Are GNN parameters a function of the input graph? This happens in Eq6 and Lines 5&7 in Alg1.

* Line 1 in Alg1 does not explain the initialization process. Crucially, is $U$ initialized to be a(n orthonormal) basis?

* line 161 "exists" must be a function of k and/or the rank of $\widehat{H}$ -- for example, what if I choose $k=0$, then there is no orthonormal basis $U$ that can recover $H$. In fact, $rank(\widehat{H})$ must be at least equal the rank of $H$ for recovery to be possible.

* The sampling matrix (described below Eq1) can be better described. Can you explain its structure? or its motive? Even a google search on "compressed sensing sampling matrix" does not pull-up the answer immediately. What is its rank?

* Most-crucially, Eq2, which the rest of the work is founded upon, reads wrong/incomplete. Most-likely, *there are trivial typos, however, I will not do deductions and I expect all authors to ensure correctness of their **main** equation*. $\widetilde{H}$ reads as a scalar (the minimum norm).

* Line 339: eigenvalues do not correspond to nodes. They correspond to eigenvectors. For instance, one can do a low-rank representation of the adjacency matrix (effectively using few eigenvalues).

questions:
+ Does the (sparse reconstruction) optimization problem have to be solved at every layer, for every new graph? Or is the assumption that the graph is always fixed (between training and inference)?

+ If the parameters of the model significantly change, isn't the re-sampling necessary? Why not sample with some periodicity (as model drifts), instead of sample only once at-start?

+ Is it at-all possible to think about the GNN in the inductive setting in your framework?
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper proposes a new sampling algorithm for efficient GNN training using compressed sensing. Although there has been extensive work in this area, the proposed sampling method is different from previous ones and has the benefit of sampling only once. Although this is an important area and the proposed method seems promising, there’s plenty of clarification issues in the paper, and as reviewers pointed out in the final discussion, even the revision submitted by the authors contain many errors in key formulas and symbols. Therefore, we think the current paper does not meet the ICLR standard.