Large-Scale Spectral Graph Neural Networks via Laplacian Sparsification

Thanks for your time and efforts spent on our work and detailed feedback!

Reply to weaknesses

• Our model applies a spectral sparsification method to random-matrix polynomials and extends the theorem to include arbitrary (dynamic and learnable) polynomial coefficients. Additionally, we introduce a more intuitive method for enhancing efficiency in semi-supervised tasks, which functions as spectral sparsification. We acknowledge that the performance of GNN models can be empirical, particularly with the inclusion of a linear layer. Previous works like GraphSAINT and Cluster-GNN have provided substantial analysis on estimation and approximation, though not directly on the GNNs' performance. Our model's approximation capability has been demonstrated both theoretically and empirically.

• We appreciate your input regarding the focus of most spectral sparsification methods on the original graph. Our work, however, concentrates on approximating the equivalent propagation matrix of spectral methods, $L_K=\sum_{k=0}^K w_k\tilde{L}^k$. We initially consider that our model differs from these past methods since our target is not the same. Recognizing the distinction, we will promptly include these methods in our study for relevant comparisons.

• We appreciate your reminding us of the model GDC. The design of GDC is based on the homophily assumption, which may not perform as well on heterophilous datasets compared to popular spectral methods. We will incorporate GDC into our paper for a more comprehensive discussion and applicable comparisons.

• We will instantly complement and clarify statements about the time and memory complexity. If processed with a single thread, the time complexity of running SLSGC is $O(K n\log n)$, and for GLSGC, it is $O(K^2n\log n)$. Besides, our method can be highly parallel processed with GPU. The memory consumption, dependent on the number of edges sampled, is $O(n \log n)$ for SLSGC and $O(Kn\log n)$ for GLSGC. Our experimental results show that the training time and memory consumption are lower than the base models, and here are some preliminary results for preview. The detailed version will be soon updated in our paper.

• Detaching models like SGC often show lower performance due to their simpler architecture, in comparison with GCN. Another defect of detaching models is that the graph propagation of raw features is inapplicable when the dimension of raw features is high. We will conduct and complete related experiments to provide a thorough comparison, and here are some experimental results for preview.

• We will add scalable methods like Cluster-GCN and FastGCN to our paper for a more comprehensive comparison with relevant works. Here are some experimental results for preview.

The current paper uses effective resistance for sparsification, which is quite generic and does not need any special assumption. N Keriven’s paper is based on many assumptions and does not consistent with the current work. How can N Keriven’s paper related and the first one in the three important papers? I need more help to understand this.

The current paper shows that you can approximate GNNs by randomly sampling edges. N Keriven shows that you can approximate GNNs by randomly sampling nodes. These are two related approaches, both related to scalability of GNNs by subsampling graphs. This is why the current approach should be compared to Keriven et al. Practitioners would want to choose between these two approaches, and they would like to see a comparison between them. What is the advantage in sampling edges over sampling nodes?

Note that there is a full asymptotic analysis in Keriven et al, so the rate of approximation should be compared to the current paper.

This paper uses Spielman et al.'s sparsification for general graphs. How is the paper "N Keriven, A Bietti, S Vaiter. Convergence and Stability of Graph Convolutional Networks on Large Random Graphs" related? Can Reviewer FyWK or N Keriven comment on this and make it more clear? I thank the reviewer of N Keriven in advance.

Practitioners reading this paper, who want to use a scalability method, would want to know what are the advantages and disadvantages in sampling edges vs sampling nodes. If the paper proposes a new sampling method - sampling edges - it should compare against past sampling methods. Especially since past works developed approximation rates, so you can compare to the approximation rates of the current paper. This is the standard way of writing papers.

Regarding papers that Keriven cited, I don't see how this is relevant. We are reviewing the current paper. Moreover, Keriven did not have a gnn paper about sampling edges to compare against. The current paper does have a gnn paper about sampling nodes to compare against.

Thanks for your time and efforts spent on our work and detailed feedback!

Reply to weaknesses.

• Our model employs a spectral sparsification method for the random-matrix polynomial and extends the theorem to include arbitrary polynomial coefficients, both static and dynamic. Furthermore, we propose an intuitive method to enhance efficiency in semi-supervised tasks, functioning as spectral sparsification.

• We are thankful for the comprehensive recommendations regarding related works. While we recognize the importance of these scalability-motivated subsampling efforts, we note that most existing scalable GNN frameworks, are based on message-passing principles, such as GCN, GCNII, and GAT. These methods require only one-hop neighbor information at each propagation layer, differing from spectral methods. Scalable methods like GraphSAGE, LADIES, and GNNAutoScale are not compatible with spectral approaches. Similarly, subgraph sampling methods like Cluster-GCN and GraphSAINT do not adequately preserve the spectral properties of the original graph, making them unsuitable for spectral methods. We initially perceived a gap between methods designed for GCN-like networks and our work, potentially leading to unfair comparisons. Despite these, a more extensive survey and comparison with existing scalable GNNs based on subsampling will be conducted. Here are some experimental results for preview.

• Our sparsification targets the equivalent propagation matrix of spectral methods, $L_K=\sum_{k=0}^K w_kL^K$, a dense matrix. Unlike previous works that focus on making the original graph sparser, our method aims to transform a dense matrix into a sparse one suitable for GNN training. The superiority of spectral methods in handling complex benchmarks, like heterophilous graphs, is evident both theoretically and empirically. While our methods are primarily designed for spectral approaches, a thorough comparison with classic scalable methods will be included.

• Matrix sketching methods are effective with real-world graphs, typically sparse. However, sampling rows of $L_K$ results in a dense submatrix, still unsuitable for our purposes. We plan to conduct an extensive review of these techniques and incorporate comparisons in our upcoming paper.

• In our paper, one of our main ideas is to enhance the theorem proposed in [Spectral sparsification of random-walk matrix polynomials], and then sparsify the equivalent propagation matrix of spectral methods, i.e. $L_K=\sum_{k=0}^K w_k\tilde{L}^k$. We turn the polynomial filter operating on the signal into the corresponding format, i.e. the polynomial of the random-walk matrix, and thus make the training of spectral methods on large graphs applicable. The mentioned direct method has two defects, which are all reflected in our empirical results: 1) high-dimensional original features can cause GPU memory overload during initial graph propagation (e.g., $LX$ in dataset Penn94 on SGC), and 2) extremely large graphs like Ogbn-papers100M exceed GPU capacity, preventing graph propagation on hidden layers.

• We appreciate the reviewer's advice on improving our writing and theoretical proofs. We commit to a thorough examination and enhancement of our theoretical framework.

Reply to questions.

• Yes, and that is how most spectral methods like BernNet improve their scalability. In our paper, we refer to these as "detached methods" and highlight their limitations. One of our contributions is enabling the spectral filtering operations applicable on hidden layers, even on large graphs.

• We appreciate your scrutiny and will correct our paper accordingly. The mentioned "non-zeros of the approximated $L_K$" will be more clearly defined.

Unfortunately, since the authors did not submit a revised version of the paper, and since an extensive revision is required, I cannot reevaluate the paper. As I understand the review process, a revised version could/should have been uploaded as part of the discussion period.

I hope to see a revised version of this paper published in the future.

Thanks for your time and efforts spent on our work and detailed feedback!

Reply to weaknesses

1. We acknowledge that our explanation of the model's fitting ability on various datasets, particularly heterophilous ones, could be more comprehensive. Our approach, which approximates the equivalent propagation matrix of established spectral methods, generally inherits the fitting capabilities of these base models. Models like GPRGNN, APPNP, and others, including unimplemented single-layer methods in our work like BernNet, have shown effectiveness on heterophilous datasets. Due to space limitations in the main paper, our focus was on performance and scalability. However, a more detailed analysis concerning heteophilous datasets and complex filters will be included in the appendix soon.

2. Our method expands upon the foundational theory established by Cheng et al., extending it to include dynamic (learnable) polynomial coefficients. This theoretical backing has enabled us to devise two graph sparsification methods for both static and learnable coefficients, thereby broadening the applicability of spectral methods. Additionally, we introduce a node-centric approach to improve efficiency in sparse-labeled graphs, which can be substantiated as a form of spectral sparsification independent of Cheng et al.'s work.

3. Regarding the hyperparameter setup, our framework introduces only one additional parameter, --ec, compared to the baseline spectral methods. This controls the sampling density. What may introduce the misunderstanding may stem from our code's simplification from a larger training framework supporting various baselines. As clarified in Appendix A.4, only a fraction of the hyperparameters in the file train.py are employed for training a single model.

4. We will instantly check and refine any confusion, misinterpretation, or errors in our paper. We are committed to integrating all writing suggestions and will conduct a thorough review to enhance the quality and clarity of our paper.

5. Our model is approximate, and its performance has a connection to the base method used. Most current scalable methods, including Cluster-GCN, GraphSAGE, GraphSAINT, LADIES, GNNAutoScale, etc., exhibit some performance loss compared to their base model, particularly as the scale of the benchmark grows. These methods typically balance efficiency, performance and applicability. Our model not only increases the applicability of spectral methods but also demonstrates comparable or superior performance even against robust base models like GPR-GNN, effectively addressing the issue of performance loss in scalability.

Reply to questions.

1. Our primary goal in sparsification is to approximate the equivalent propagation matrix of spectral methods, denoted as $L_K=\sum_{k=0}^K w_k L^k$, which is inherently a dense matrix. Taking the dataset twitch-gamer as an example, with $K=2$, the non-zeros in $L_K$ amount to $6,827,688,588$. In contrast, our approximated graph contains only $12,136,808(1.7\%)$ in GPR-LS and $6,068,404(0.9\%)$ in APPNP-LS with --ec=3. The number of sampled edges in our method increases linearly with $K$, while the non-zeros in $L_K$ grow exponentially, with an upper bound of $n^2$. The proportion of retained edges remains below $2\%$ in all cases.

2. Yes, our method reduces the training time of the base models. We will provide a detailed wall-clock time comparison of GNN training in the updated version of our paper, and here is the preliminary results for preview.

3. Our theoretical framework outlines the asymptotic complexity of the required sample edges. In our implementation, we set the number of sampled edges to $n\cdot\log n\cdot ec$, where $ec$ is the hyperparameter controlling the constant of sampling numbers. The larger $ec$ is, the more accurate our approximation will be (i.e. smaller $\varepsilon$).

Thanks for your time and efforts spent on our work and detailed feedback!

Reply to weaknesses.

• We will refine any ambiguity previously introduced regarding the application of our concept. Our definition of polynomial filters aligns with the broader theme of representation learning This is evident as the output delineates the learned representation of nodes, adaptable for various downstream tasks. For example, in our implementation, we use $Z=f_{\theta'}(\sigma(Y))$ to denote the predicted labels, where $\sigma(\cdot)$ represents the nonlinear activation function. The structure of $Y$ aligns with prevalent spectral methods employing a single layer of polynomial filters, such as GPR-GNN, BernNet, JacobiConv, and others. We posit that the standard 2-layer GCN diverges from the typical framework of spectral GNNs.

• Our primary experimental findings focus on comparing the performance of our methods against established baselines. We observe scalability issues, particularly regarding 1) the substantial memory requirements for graph propagation of raw features in the Penn94 dataset, and 2) the extensive storage demands of the Ogbn-papers100M dataset. Our methods demonstrate effective scalability in these contexts, underscoring their advantages. A detailed analysis of time and memory consumption will be provided in our forthcoming paper, along with a demo version for preliminary feedback. Additionally, we will soon update the error bars in our paper.

• We choose APPNP and GPRGNN for their soundness in the realm of spectral GNNs with static and learnable coefficients. Further experiments comparing our methods with other spectral GNNs like JacobiConv are underway and will soon be updated in our paper.

• Our approach is centered on developing an approximation of the equivalent propagation matrix in spectral GNNs, specifically $L_K = \sum_{k=0}^K w_k L^k$. While approximation inherently involves some level of randomness and potential inaccuracy, we ensure practical performance by maintaining spectral properties as detailed in Theorem 3.2

Previous studies often rely on subsampling, historical embedding, or some other techniques to achieve satisfactory practical performance. However, these methods frequently fall short of providing robust support for gradient estimation. The incorporation of linear layers and non-linear activations in these models makes their final performance challenging to analyze, often rendering the results more empirical. Our model demonstrates impressive practical performance, thereby validating the effectiveness of our proposed methods.

A novel aspect of our approach is the extension of the original theorem in a more generalized manner, incorporating dynamic (learnable) polynomial coefficients. This theoretical foundation has enabled us to devise two versatile graph sparsification techniques, tailored for both static and learnable coefficients, enhancing the applicability of spectral methods. Furthermore, we introduce an intuitive node-centric approach to improve efficiency in sparsely-labeled graphs.

Reply to questions.

1. Our approach innovatively replaces the conventional propagation layer with a one-time propagation mechanism, which is also applicable to multiple filter layers. To substantiate this, we will present experimental results from several 2-layer spectral models in our paper, and we will present a demo version of our results ahead.

Our theoretical analysis still confirms its effectiveness, independent of the number of filter layers used. In fact, those typical spectral GNNs tend to avoid stacking multiple filter layers due to concerns about time and memory overhead, with unequal performance elevation.