TEDDY: Trimming Edges with Degree-based Discrimination Strategy

[Baseline Performance]

Q1. We believe that our experiment is conducted upon the fair setting. To demonstrate this, we have attached the source code for both our TEDDY and the baselines in supplementary.

It's important to note the issue of the official implementation of UGS [4] on GAT (https://github.com/VITA-Group/Unified-LTH-GNN/blob/main/NodeClassification/gnns/gat_layer.py). According to the code, edge masking is applied prior to the softmax normalization of attention coefficients. However, this implementation leads to a notable issue where pruned edges inevitably receive non-zero normalized attention coefficients, incurring the revival of pruned connections during the neighborhood aggregation phase (hence, the corresponding edge is NOT actually pruned).

Our experimental results using a revised implementation revealed a significant performance decrease compared to the results reported in [4]. However, we expect the performance enhancement of TEDDY as well as baselines if we adhere to the original implementation of UGS, since in this case, the amount of information received from neighbors also increases for our method. The same issue is pertinent on WD-GLT [5] as well, and we posit that this is due to the implementation on top of the UGS. Besides, we detailed the additional reproducing issue of WD-GLT in Appendix B.3.

References

[1] Pruning graph neural networks by evaluating edge properties, Knowledge-Based Systems 2022.

[2] Effective Sparsification of Neural Networks with Global Sparsity Constraint, CVPR 2021.

[3] Adversarial structured neural network pruning, CIKM 2019.

[4] A Unified Lottery Ticket Hypothesis for Graph Neural Networks, ICML 2021.

[5] Rethinking Graph Lottery Tickets: Graph Sparsity Matters, ICLR 2023.

[On Theoretical Substantiation]

W3. As we discuss in [Graph Sparsification], [1] introduce the concepts of bridge/non-bridge edges using graph spectral analysis, upon which the authors propose graph sparsification methods, but it is important to note that the notion of bridge/non-bridge edges in [1] does not entirely align with the low-degree/high-degree edges in our paper. As we note in Theoretical evidence of remarks in Section 4, the generalization error bounds of several GNN families heavily depends on the adjacency matrix rather than model parameter or node features. For the representative example, the error bound for GCN relies on the $\Vert A_{\text{sym}}\Vert_{\infty}$ for the symmetrically normalized adjacency matrix $A_{\text{sym}}$ and this norm can be further upper-bounded by $\sqrt{\frac{deg_{max}+1}{deg_{min}+1}}$. Note also that PGEP method introduced in [1] would be computationally intractable in practice since it should execute multiple times of graph search algorithm (such as DFS) for each node to identify bridge/non-bridge edges through a whole graph, which would be more problematic in a large-scale scenario. On the other hand, our approach TEDDY can practically identify to-be-pruned edges in a more computationally efficient way (please refer to the performance evaluation and time consumption on large-scale datasets in Section 6.2 and Appendix A.8, respectively).

[On Graph Sparsification]

W2-1. We appreciate your observation in drawing parallels between our work and the approach presented in [1]. However, we respectfully disagree with the view that our work, TEDDY, is closely related to [1].

There exist several clear differences and superiority of TEDDY from the methodology proposed in [1], which we believe are worthwhile to clarify:

1. No Direct Conceptual Alignment: Although [1] demonstrates the edge importance via spectral analysis, the concept of the bridge is NOT strictly aligned with our high-degree/low-degree edges. According to the Definition 2 in the paper [1], the bridge refers to an edge whose deletion increases the number of connected components in the graph, and the reverse corresponds to the non-bridge. However, the bridge in the paper does not correspond to neither low-degree edge nor high-degree edge, since there could be still a chance of the existence of common neighbors between node pairs of both high- and low-degree edges, or the between the receptive fields (multi-hop neighbors).
2. Training Pipeline Distinction: More importantly, the primary distinction between our method and [1] is in the training procedure. In practice, PGEP method proposed in [1] prunes two types of edges in a fully trained network: (i) edge $(i,j)$ with different predicted labels $\widehat{y}_i\neq \widehat{y}_j$ (specified as negative edge) and (ii) non-bridge edges. Hence, TEDDY is the first approach to achieve effective pruning by utilizing solely the structural information of graph data.

Furthermore, the aforementioned approach in [1] faces several practical issues. Firstly, to identify all non-bridge edges in the entire graph, one needs to execute graph algorithms such as DFS for each node, which can be highly time-consuming when it comes to large-scale datasets. Secondly, even if all non-bridge edges are identified, if the total number of non-bridge edges and negative edges is less than the target sparsity ratio, PGEP fails to achieve the desired pruning level. In consequence, this method may not be available in high sparsity regimes. On the other hand, given sparsity ratio for both graph and parameter, TEDDY can exactly achieve the target sparsity level in a more efficient way. Unfortunately, due to this cumbersome training procedure, we were not able to conduct the additional evaluation on [1] during the rebuttal period. Nevertheless, we will include the experiment in the final version.

Thus, while there are superficial similarities in the definition, conceptual alignment and underlying training procedure of TEDDY are markedly different from [1]. We believe these differences are significant and contribute to the distinctiveness and novelty of our work in the realm of GNN pruning.

[On Parameter Sparsification]

W2-2. The projected gradient descent (PGD) is a well-known optimization algorithm with rich properties that has been used in various machine learning literature for a long time. The characteristics of PGD depend on the appropriate setting of the constraint set. In this regard, the two mentioned works [2, 3] indeed utilize projected gradient descent, but each has a different constraint set from ours. In the case of [2], projection is performed onto the $\ell_1$-ball, while [3] utilizes a constraint set satisfying the RIP-like condition. Note that both [2, 3] introduce additional hyperparameters, and tuning these hyperparameters is inevitable to reach the target sparsity level. In contrast, our approach directly projects onto the $\ell_0$-ball without introducing additional hyperparameters, making it a novel attempt in sparsification.

We sincerely appreciate the reviewer’s helpful and constructive feedbacks. We would like to address the reviewer’s concerns as below.

[On Complexity]

W1. In practice, $T_{edge} \in |\mathcal{E}|$ is only computed for the existing edges, hence it requires only $O(|\mathcal V|+|\mathcal{E}|)=O(N+M)$ space complexity. The computation of $T_{edge}$ involves (1) degree computation for individual nodes by row-wise sparse summation of the adjacency matrix, (2) Mean-aggregating the degree vector with (sparse) adjacency matrix to obtain $\widetilde g$ in a sparse matrix multiplication manner, and (3) Element-wise multiplication between $\widetilde g(v)$ of nodes $v$ in rows (i.e., source nodes) and $\widetilde g(u)$ of nodes $u$ (i.e., destination nodes) in columns of the edge index. For better understanding, we attached the code snippet for computing $T_{edge}$ in the supplementary material (compute_edge_score function in pruning.py).

We sincerely appreciate the reviewer’s helpful and constructive feedbacks. We would like to address the reviewer’s concern as below.

[On Wall-clock Time]

Q1. In response to the the reviewer’s valuable recommendation, we compared the wall-clock time analysis of TEDDY against baselines, averaged over five runs in five distinct simulations. We conducted experiments in the same GPU and GPU models for baselines and our method for each setting, to ensure fair comparisons.

Overall, the results clearly substantiates that TEDDY consistently achieves a significant reduction in pruning time relative to the baselines. This is especially pronounced in GIN on the Pubmed dataset, where TEDDY outperforms WD-GLT [1] by a remarkable margin, displaying a maximum time saving of 220.72 seconds during the 15-th simulation. Similar trend is observed in large-scale datasets, where TEDDY’s time consumption is nearly half that of UGS [2]. The maximum duration gap is revealed in the Reddit dataset, with TEDDY concluding the last simulation 131.84 seconds quicker than UGS in GCN. For your convenience, we attached tables below in the revised manuscript, throughout Table 3-5.

References

[1] Rethinking Graph Lottery Tickets: Graph Sparsity Matters, ICLR 2023.

[2] A Unified Lottery Ticket Hypothesis for Graph Neural Networks, ICML 2021.

[On Smaller Graphs to Larger Graphs]

Q3. The reviewer's question raises a consideration about the scalability of TEDDY, which may be interpreted as its adaptability to an inductive semi-supervised node classification setting, where the fraction of the validation and test set is unobserved and larger than that of the training set. In this perspective, GNNs are trained on the partial set of the entire dataset while tested on the remaining unseen portions.

In response to the reviewer’s insightful question, we expanded our experiments to assess our model’s performance in inductive scenarios. We adjusted the Cora, Citeseer, and Pubmed datasets to a 20/40/40% split for training, validation, and testing, guaranteeing no exposure to the validation and test nodes as well as edges connected to them during training.

In the corresponding results, illustrated in Figure 15 and 16 of the revised manuscript, TEDDY achieves prominent pruning performance on inductive setting as well. This is especially pronounced on the Cora dataset with GCN and on the Citeseer dataset across all benchmark architectures, surpassing the accuracy of vanilla GNNs. Hence, the results affirm TEDDY’s capacity to generalize from smaller to larger graphs effectively.

[On Extreme Sparsity]

Q4. Following the reviewer’s insightful question, we believe that TEDDY strategically preserves low-degree nodes while pruning primarily focuses on high-degree nodes. This approach is rooted in the inherent design of GNNs, where neighborhood aggregation is a core component. Unlike vision domain, which often relies on complex, fully connected layers, GNNs typically employ lighter pre-aggregation embeddings. This characteristic is particularly crucial in such neural networks, where low-degree nodes have fewer neighbors to gather information from. Excessive pruning that drastically reduces the degree of these nodes, or in extreme cases, isolates them (equivalent to the forward pass of MLP), can severely hamper the model's ability to classify, since the amount of information they can obtain through the message-passing scheme becomes limited. By protecting these low-degree nodes, TEDDY ensures that even under extreme sparsity, there is sufficient local structure to facilitate effective classification, hence improving the performance of vanilla GNNs.

References

[1] Fast graph representation learning with PyTorch Geometric, ICLR 2019 (RLGM Workshop).

[2] A Unified Lottery Ticket Hypothesis for Graph Neural Networks, ICML 2021.

[3] Rethinking Graph Lottery Tickets: Graph Sparsity Matters, ICLR 2023.

We sincerely appreciate the reviewer’s helpful and constructive feedbacks. We would like to address the reviewer’s concerns as below.

[Computation of Edge Score]

W1-1. $T_{edge}\in\mathbb{R}^{|\mathcal{E}|}$ is only computed for node pairs that exist as edges, not for all possible node pairs. In practice, this is achieved by element-wise multiplication between $\widetilde g(v)$ of nodes $v$ in rows (i.e., source nodes) and $\widetilde g(u)$ of nodes $u$ (i.e., destination nodes) in columns of the edge index provided in Pytorch Geometric [1]. This ensures the obtainment of scores for only real edges. To clarify this, we have attached the code snippet of the edge score calculation in supplementary material (compute_edge_score function in pruning.py).

[Typo in Eq. (5)]

W1-2. Thank you for the reviewer’s correction. We modified the typo in Eq. (5) in the revised paper.

[On Degree Analysis]

W1-3. We apologize to the reviewer for confusion. We provide the clarification as follows. We empirically validated the necessity to consider higher-order edge degrees in Figure 17 in the appendix. As evidenced by the figure, the multi-level consideration of edge degree clearly improves the performance (specified as Ours), compared to the outcomes of pruning based solely on first-order degree information (specified as 1-hop Degree). While Figure 8 focuses on first-order degrees, the motivation behind Figure 8 is on the particular emphasis of TEDDY performing degree-aware pruning, reflecting the prior observation highlighted in Section 4. Conversely, baselines lacks the edge degree consideration, correlating with their less optimal performance as compared to our method.

[On Distillation]

W2. Our findings, as illustrated in Figure 17 and 18, do indicate performance improvement due to the model distillation. Note that, however, our analysis puts more emphasis on the significance of 2-hop degree based edge score, $T_{edge}$, in Figure 18 in revised paper. As demonstrated in the figure, the design of edge scores is more critical, since any configuration with the baseline including distillation fails to achieve better pruning performance than our method with a sole $T_{edge}$ (represented as Ours w/o $\mathcal L_{dt}$).

[On Zero-shot Performance]

Q1. In the development of TEDDY, we specifically focused on a one-shot edge sparsification approach, which inherently differs from zero-shot pruning strategies. Consequently, evaluating TEDDY in a zero-shot setting falls outside the scope of our current research. This distinction aligns with the methodology used in previous studies on GNN pruning [2, 3], which typically employ pretrained models as a foundation for iterative pruning. While zero-shot sparsification offers an interesting perspective, our method gains significant efficacy on one-shot mechanism, by eliminating the need for repeated retraining each pruning level adopted in [2, 3] (Please refer to the wall-clock time analysis of TEDDY against baselines in Appendix A.8 in the revised paper).

[On Distillation Component Removal]

Q2. In response, we present the ablation study in Figure 17. As illustrated in the figure, removing distillation term in TEDDY (specified as Ours w/o $\mathcal L_{dt}$) consistently achieves superior performance compared to baselines, even with those integrated with distillation component.

Further ablation on all benchmark datasets is detailed in Figure 18 in the revised paper. In the figure, the performance UGS [2] attached with distillation loss remains suboptimal compared to TEDDY without $\mathcal L_{dt}$, regardless of benchmark datasets. This underscores the significant influence of our degree-based pruning component. Additional studies to further evaluate this effect on other architectures will be included in the later revision.

[On Theoretical Claim]

Q4. Note that the generalization error bound for GNN [10] is not our contribution, but we can offer theoretical evidences for our TEDDY based on the results in [10]. In fact, the most challenging component in computing the Lipschitz constant for practical GNN families is the non-smooth ReLU function. Theoretically, [10] considered a slightly relaxed ReLU function that makes ReLU continuously differentiable. In such cases, since every part of the function becomes smooth, it is possible to compute the Lipschitz constant. It is anticipated that the Lipschitz constant of the original GNN can also be approximated to some extent through this relaxed activation function. Regarding the quantity $\frac{deg_{max}+1}{deg_{min}+1}$, the action of removing low-degree edges (not nodes) tends to increase the generalization bound by consistently making $deg_{min}$ monotonically decreasing, thereby inducing worse generalization. Similarly, removing high-degree edges also consistently makes $deg_{max}$ monotonically decreasing. In contrast to the previous case, this tends to reduce the generalization gap, encouraging better generalization.

We sincerely appreciate the reviewer’s helpful and constructive feedbacks. We would like to address the reviewer’s concerns as below.

[On Experiments for Recent GNNs]

Q1. In response to the reviewer’s insightful suggestion, we expanded our experiments to encompass recent Transformer-based GNN architectures. While integrating TEDDY with these advanced models, we encountered several issues with some architectures suggested by the reviewer.

To begin with, PGNN [1] utilizes a dense adjacency matrix in the input tensor, resulting in an $N\times N$ matrix for a graph with $N$ nodes. In general, adjacency matrix in GNNs are encoded as a sparse format, where the computation can be highly dependent on the number of edges. This is where the graph sparsification can offer a benefit. However, in the case of dense matrix representations as PGNN, both zero and non-zero elements are treated equally in terms of storage and computational overhead. Consequently, the inherent characteristics of PGNN's dense matrix approach do not align well with the advantages offered by graph sparsification.

Regarding GraphGPS [2], its primary efficacy is demonstrated in graph-level tasks, diverging from our focus on node classification. Similarly, Specformer [3], while benchmarked against GraphGPS in graph-level tasks, was evaluated against other baselines in node-level tasks. In our experiments, we observed that GraphGPS did not yield satisfactory performance on Cora and Citeseer compared to classic GNNs.

Consequently, we explore alternative graph transformers, specifically UniMP [4], NAGphormer [5], and Specformer [3], which have demonstrated strong performance in node classification without significant degradation on our benchmark datasets. However, both Specformer and NAGphormer replace the input adjacency matrix with eigenvectors and eigenvalues from eigendecomposition. The baselines’ differentiable mask for the adjacency matrix requires backpropagation through eigenvectors and eigenvalues, introducing a practical challenge with high complexity of $O(N^3)$ for the number of node $N$ per iteration. Given these constraints, we conducted the evaluation of these two transformer architectures only on TEDDY, whereas including experiments on TEDDY and all baselines for UniMP [4], which has also been recognized as a graph transformer benchmark in [6].

As depicted in Figure 13 and 14, TEDDY accomplishes stable pruning performance, surpassing all baselines when equipped with UniMP as a backbone. In particular, UGS and WD-GLT show significant degradation as the sparsity increases, whereas the performance of TEDDY is stable across all benchmark datasets. Note that differentiable mask approach from baselines may prune edges more than pre-defined ratio, due to the possibility of multiple mask elements having the same value. Our method also yields decent performance in NAGphormer and Specformer, notably in NAGphormer on the Pubmed dataset, with a marginal accuracy loss of 0.56. Overall, these results demonstrate TEDDY's versatility across diverse foundational architectures.

[On Efficiency of PGD]

Q8. The existing iterative approaches to parameter sparsification involve the full training of an $\ell_1$-regularized mask to identify crucial parameter coordinates. After training, $p_\theta$% of coordinates with the smallest signals in the mask are zeroed out, and the obtained mask is used to train a subnetwork to obtain the graph lottery ticket. Therefore, iterative methods inevitably require two rounds of training to obtain the mask, and achieving the desired target sparsity ratio necessitates multiple times of training process. In contrast, TEDDY can obtain sparse parameters in a single training pass using Projected Gradient Descent on the $\ell_0$-ball for any parameter initialization. Furthermore, since the parameters are already sparse during the training process, TEDDY can also reduce the training time. To validate this, we conduct wall-clock time comparisons for parameter sparsification across each method. Toward this, we use the original dense adjacency matrix while pruning only model parameters for fair comparisons. For your convenience, we attached the below tables in Table 6-8 in the revised paper.

References

[1] Provably Powerful Graph Networks, NeurIPS 2019.

[2] Recipe for a general, powerful, scalable graph transformer, NeurIPS 2022.

[3] Specformer: Spectral Graph Neural Networks Meet Transformers, ICLR 2023.

[4] Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification, IJCAI 2021.

[5] NAGphormer: A Tokenized Graph Transformer for Node Classification in Large Graphs, ICLR 2023.

[6] Towards Deep Attention in Graph Neural Networks: Problems and Remedies, ICML 2023.

[7] A Unified Lottery Ticket Hypothesis for Graph Neural Networks, ICML 2021.

[8] Rethinking Graph Lottery Tickets: Graph Sparsity Matters, ICLR 2023.

[9] Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks, AAAI 2019.

[10] Towards Understanding Generalization of Graph Neural Networks, ICML 2023.

[On Superiority over Iterative Methods]

Q7. Our experimental results demonstrate superior performance compared to baselines across various graph sizes, underscoring our method's robust generalization ability. This is particularly evident in Section 6.1, where TEDDY, when utilizing GAT as the base architecture, shows a performance enhancement ranging from 12.8% to 20.4% over the optimal performances of baseline models. Additionally, TEDDY consistently exhibits stable performance across different datasets, as highlighted in our inductive semi-supervised node classification experiments. For instance, on the Pubmed dataset, TEDDY maintains decent accuracy despite the significant scarcity in the ratio of training nodes (20% for training vs. 80% for inference). These results confirm TEDDY's outstanding generalization abilities, marking it as a superior choice across diverse datasets compared to conventional iterative baselines.

[On distillation]

Q6. We thank the reviewer for raising an important point. Our findings, as illustrated in Figure 17 and 18, do indicates an enhancement in performance due to the model distillation. However, our analysis emphasizes the significance of 2-hop degree based edge score, $T_{edge}$, in Figure 18 in revised paper. As demonstrated in the figure, the design of edge scores is more critical, since any configuration with the baseline including distillation fails to achieve better pruning performance than our method with a sole $T_{edge}$ (represented as Ours w/o $\mathcal L_{dt}$).

Moreover, the use of pretrained models is a common initial step in iterative pruning approaches as well, since they fully exploit the dense graph and GNNs at the initial pruning stage. Our method is tailored for practical scenarios in mind: for example, facilitating the deployment of GNNs on local devices with performance equivalent to fully trained models on central servers. Hence, the term “single training” in our paper refers to the elimination of the iterative cycle of retraining GNNs for each pruning level. Instead, our TEDDY accomplishes the sparsification in a single training phase when given the sparsity levels and trained GNNs, promoting a significant efficiency, as displayed in Table 3-5 in the revised version.

[On Eq. (5)]

Q5. As we explicitly stated in Section 3.1, TEDDY is specifically tailored for undirected graphs, and thus does not directly address directed graphs. Although $T_{edge}$ is symmetric in directed graphs as the reviewer pointed out, directed graphs were out of scope for the design of $T_{edge}$.

[On Ablation Study]

Q3-1-a. (On graph sparsification) We sincerely appreciate the reviewer’s constructive feedback. However, we would like to clarify that the purpose of graph sparsification is to preserve the original GNN’s accuracy, rather than improving it as a form of regularization. Hence, we respectfully disagree in that our graph pruning method doesn’t seem to improve empirical performance at all. And in fact, according to a sole graph sparsification performance comparison between our pruning approach and baselines, illustrated in Figure 19, our approach consistently achieves superior performance to baselines. Thus, this clearly substantiates that our graph sparsification indeed well-preserves, and in most cases even surpasses (7 out of 9 settings in Figure 19) the original GNNs’ performance.

Furthermore, following the reviewer’s thoughtful opinion that components TEDDY can be applied separately, we provide comprehensive ablation studies for diverse combinations of our components. Utilizing GAT as a backbone architecture, we evaluated 7 distinct scenarios detailed in Figure 18:

(Scenario 1) TEDDY with all components (specified as Ours),

(Scenario 2) TEDDY without distillation loss (specified as Ours w/o $\mathcal L_{dt}$),

(Scenario 3) TEDDY with magnitude-based weight mask pruning (specified as Ours w/ $m_\theta$),

(Scenario 4) TEDDY without weight sparsification, i.e., our graph sparsification method with dense weights (specified as Ours w/o weight spar.)

(Scenario 5) UGS [7] with all components (specified as UGS),

(Scenario 6) UGS with distillation loss (specified as UGS w/ $\mathcal L_{dt}$),

(Scenario 7) UGS with $\ell_0$-based projected gradient descent (specified as UGS w/ $\ell_0$ PGD).

Q3-1-b. (On distillation loss) The results, as depicted, do indicate performance improvement due to the model distillation. However, the results also clearly demonstrate that even when UGS is augmented with or without $\mathcal L_{dt}$ (scenario 6 and 5), it fails to match the performance of our framework without $\mathcal L_{dt}$ (scenario 2). Similar results regarding WD-GLT [8] are illustrated in Figure 17. This demonstrates that our edge sparsification method rooted in low edge degree possesses more significant impact than the distillation component in GNN pruning.

Q3-1-c. (On weight sparsification) Furthermore, our method including $\ell_0$ PGD (scenario 1) shows comparable performance to that of TEDDY with dense weights (scenario 4), across varying pruning simulations, underscoring the robustness of our weight sparsification method. Additional studies to further evaluate this effect on other architectures will be included in the later revision.

[On Novelty of Multi-hop Consideration]

Q3-2. We acknowledge that multi-hop subgraph analysis is a well-established concept in graph learning. Nevertheless, the application of leveraging a sole degree information in multi-level consideration in node classification task has been under-explored. The referenced work [9] provided mainly addresses the performance enhancement on graph-level tasks by incorporating a broader range of neighborhood features and structural complexities, rather than concentrating on the pruning aspect of GNNs to preserve the original performance. Our approach, which specifically considers multi-hop edge degree for GNN pruning, introduces a novel angle within this domain.

[On Figure 1]

Q2. In the analysis of Figure 1, we define the edge score of each edge $(i,j)$ as $T_{edge}(i, j) =(|\mathcal N(i)|+|\mathcal N(j)|)/{2}$, where $\mathcal N(k)$ denotes the set of neighboring nodes connected to node $k$. For our experiments, we conduct 20 simulations where GNNs are trained after pruning edges based on their scores. Specifically, given a graph sparsity ratio $p_g$ for each simulation, we pruned $p_g\%$ of edges having the highest edge score $T_{edge}$ in the high degree pruning scenario (represented as blue lines in the figure), and pruned edges with the lowest scores in the low-degree scenario (represented as orange lines in the figure). Hence, our TEDDY does not involve any stochastic procedures such as random sampling.

However, to address the reviewer’s suggestion, we conduct additional simulations with 5 different random seeds (0 to 4) and reported the average performance in Table 2. In the table, deg_low refers to pruning based on the lowest degree, while deg_high corresponds to the highest degree-based pruning. The results clearly demonstrate that pruning low-degree edges, i.e., low $T_{edge}$, can significantly deteriorate the performance, especially in GAT on the Pubmed dataset, where the performance between deg_low and deg_high reaches the maximum gap of 24.1% in the final simulation. For convenience, we attach the below tables in Table 2 in the revised manuscript.

[Additional Insights on Training Noise]

In response to the reviewer’s constructive feedback, we reported average pruning performance of our TEDDY and baselines across all sparsities, represented in Figure 13 and 14 in the revised manuscript. To ensure fair comparisons, we adopted uniform random seeds to all methods for each setting. Owing to the constraints of the rebuttal period, we present performance results of NAGphormer [1] and Specformer [2] on Cora and Citeseer datasets, averaged over 3 runs (Note that the eigendecomposition of Pubmed dataset required prohibitive time consumptions). Meanwhile, we adopted uniform five random seeds for UniMP [3].

As depicted in the figures, our TEDDY still accomplishes prominent performance, surpassing all baselines when equipped with UniMP as a backbone. In particular, UGS [4] and WD-GLT [5] exhibit severe unstability as the sparsity increases, whereas the performance of TEDDY remains stable across all simulations with notably small standard deviations. Our method also achieves decent performance in NAGphormer and Specformer, notably in NAGphormer on the Cora dataset, with considerable performance enhancement over the original result. Hence, the results clearly demonstrate our method’s versatility and robustness across diverse foundational architectures.

References

[1] NAGphormer: A Tokenized Graph Transformer for Node Classification in Large Graphs, ICLR 2023.

[2] Specformer: Spectral Graph Neural Networks Meet Transformers, ICLR 2023.

[3] Masked Label Prediction: Unified Message Passing Model for Semi-Supervised Classification, IJCAI 2021.

[4] A Unified Lottery Ticket Hypothesis for Graph Neural Networks, ICML 2021.

[5] Rethinking Graph Lottery Tickets: Graph Sparsity Matters, ICLR 2023.

[On Table 1]

W4. We appreciate the reviewer’s helpful feedback. In response to the reviewer’s suggestion, we present the results of our method on GIN under extreme sparsity as a heatmap in Figure 20, in the revised paper. The performance in each heatmap element is an average performance over 5 random seeds.

Overall, the performance of TEDDY is not uniformly affected by increased sparsity. In the Cora dataset, our method demonstrates resilience to higher graph sparsity levels, surpassing the vanilla GIN’s accuracy of 76.34%. This suggests that a sparser graph generated from our method has a potential to mitigate overfitting and achieve generalization. For the Citeseer dataset, the performance remains relatively stable across a range of weight sparsity levels, underscoring a robustness to parameter reduction. Furthermore, all configurations exceed the vanilla GIN's accuracy of 68.1%, strongly indicating the effectiveness of TEDDY across diverse sparsities. The similar efficacy is observed in the Pubmed dataset, where all elements surpasses the vanilla GIN’s performance of 77.9%. Interestingly, we observe a trend in the Pubmed where the performance generally improves with increased sparsity, with the highest accuracy achieved under the most extreme sparsity ($p_g=p_\theta=85$%).

[On parameter reinitialization at the end of the pruning stage]

Q1. Our method does not adhere to the standard lottery ticket hypothesis framework, where parameters are reinitialized to their original values during the post-pruning. Instead, our approach is agnostic to the initial parameter values. Following the graph sparsification, we do not revert to the original initialization but continue training from the current initialized state of the parameters, which may be randomly initialized or pre-trained. Hence, TEDDY can obtain robust performance as the original GNNs, irrespective of the initial starting points of the parameters.

[The number of hops considered for multi-level degree consideration]

Q2. In our method, as outlined in Eq. 3-5, we considered two-hop degree information to calculate edge-wise scores $T_{edge}$ for all settings. There could be other options for the choice of the number of hops, but we fixed it as two, since two hop degree consideration is sufficient to yield prominent performance. Consequently, the number of hops in our pruning criterion is a predetermined choice.

References

[1] Dropedge: Towards deep graph convolutional networks on node classification, ICLR 2020.

[2] A Unified Lottery Ticket Hypothesis for Graph Neural Networks, ICML 2021.

[3] Soft threshold weight reparameterization for learnable sparsity, ICML 2020.

[4] Learning Sparse Neural Networks through L_0 Regularization, ICLR 2018.

We sincerely appreciate the reviewer’s helpful and constructive feedbacks. We would like to address the reviewer’s concerns as below.

[On Motivation]

W1-1. While we agree with the reviewer that considering aspects such as spectral information or centrality is an appealing approach, it is worth noting that in case of large graphs, such as Reddit or ArXiv dataset, understanding the spectral properties of the graph Laplacian/adjacency matrix is often computationally infeasible. To consider spectral information, one would require information for spectrums (e.g. eigenvectors/eigenvalues), and exploiting such information necessitates algorithms like eigendecomposition, which requires a expensive time complexity of $O(|V|^3)$. Thus, our primary goal is to design a pruning algorithm that can quickly identify to-be-pruned edges even for large graphs. As an initial step toward our goal, we focus on considering degree information and believe that we successfully demonstrated that even with only degree information, our TEDDY could effectively maintain the performance of dense graphs/GNNs through extensive experiments (Section 6). However, in line with the reviewer's suggestion, we acknowledge the potential to incorporate a more diverse range of graph information and consider it as our future avenue.

[On Comparison with Random Edge Pruning]

W1-2. In response to the reviewer’s insightful suggestion, we expanded our experiments including random dropping strategy in DropEdge [1]. In this experiment, we solely conducted a graph sparsification to directly compare the impacts of diverse edge pruning approaches, including our TEDDY.

According to the results illustrated in Figure 19, TEDDY consistently surpasses baseline approaches including DropEdge. Notably, our method not only preserves but outperforms the accuracy of vanilla GNNs in the Citeseer and Pubmed datasets across all benchmark GNNs. Figure 19 also demonstrates that utilizing DropEdge technique results in suboptimal performance, underscoring the necessity of sophisticated pruning strategy. Interestingly, in a distinct graph sparsification scenario, UGS [2] tends to exhibit the similar performance with that of the DropEdge.

[On Parameter Sparsification]

W2. The most crucial aspect of our PGD on $\ell_0$-ball is its capability for one-shot pruning at any given sparsity level. For example, the previous approaches like UGS and WD-GLT require sensitive tuning of the $\ell_1$ regularization parameter due to an iterative process to reach the target sparsity level, while our method enables one-shot pruning without any regularization parameter. In a similar sense, references [3], [4], as the reviewer brings to us, also necessitate tuning of the regularization parameter to achieve the target sparsity level, which may be burdensome in practice. Additionally, by encouraging sparsity during training, we can gain computational advantages in terms of actual number of operations even during the training phase.

[On Architectures]

W3. In addressing the differences between GATs and GCNs in our experiments, it's important to note the issue of the public code of UGS [2] on GAT (https://github.com/VITA-Group/Unified-LTH-GNN/blob/main/NodeClassification/gnns/gat_layer.py). According to the code, edge masking is applied prior to the softmax normalization of attention coefficients. However, this implementation leads to a notable issue where pruned edges inevitably receive non-zero normalized attention coefficients, incurring the revival of pruned connections during the neighborhood aggregation phase. Our experimental results using a revised implementation revealed a significant performance decrease compared to the results reported in [2]. This suggests that the removal of edges before forwarding GAT layer, may not significantly impact the performance if the attention mechanism inherently captures degree information beneficial for pruning. Given these observations, it remains unclear whether the attention mechanism in GATs offers a substantial advantage over GCN in encoding degree information.