EPIC: Compressing Deep GNNs via Expressive Power Gap-Induced Knowledge Distillation

We thank the reviewer for the insightful and valuable comments. We respond to your comments as follows and sincerely hope that our rebuttal could properly address your concerns. If so, we would deeply appreciate it if you could raise your score. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission.

1. The motivation for studying the distillation for deep GNNs.

Thanks for your comments.

We summarize the motivation for studying the distillation for deep GNNs as follows.

• First, on large-scale datasets (e.g., ogbn-arxiv, ogbn-products, and ogbn-proteins), the deep teacher models that we distill in our paper (i.e., RevGCN-Deep, RevGNN-112, and RevGNN-Deep) outperform what existing KD4GNN works aim to distill, such as GCN, GraphSAGE, GAT, and APPNP. Compared with shallow GNNs, deep GNNs with more message passing layers are better at capturing long-range patterns [1, 2], which are critical for many downstream tasks such as search engine [3], recommendation systems [4], and molecular property prediction [5].

• Second, although some deep GNNs still face challenges such as over-fitting and over-squashing, there have been many efforts to solve these challenges, such as [6, 7, 8, 9, 10, 11]. We believe that the challenges are temporary obstacles to the development of deep GNNs, and we believe that deep GNNs will receive widespread attention in the future.

• Last but not least, the slow inference speed is also one of the important factors limiting the real applications of deep GNNs. Despite the great success in compressing and accelerating moderate-sized or shallow GNNs of existing KD techniques, it still remains a tough challenge to distill deep GNNs due to the huge expressive power gap between the teachers and students. Therefore, this paper aims to address the challenge of distilling deep GNNs that excel on large-scale graphs and possess numerous layers.

[1] Chen, Tianlong, et al. "Bag of tricks for training deeper graph neural networks: A comprehensive benchmark study." IEEE Transactions on Pattern Analysis and Machine Intelligence 45.3 (2022): 2769-2781.

[2] Cong, Weilin, Morteza Ramezani, and Mehrdad Mahdavi. "On provable benefits of depth in training graph convolutional networks." Advances in Neural Information Processing Systems 34 (2021): 9936-9949.

[3] Brin, Sergey, and Lawrence Page. "The anatomy of a large-scale hypertextual web search engine." Computer networks and ISDN systems 30.1-7 (1998): 107-117.

[4] Fan, Wenqi, et al. "Graph neural networks for social recommendation." The world wide web conference. 2019.

[5] Kearnes, Steven, et al. "Molecular graph convolutions: moving beyond fingerprints." Journal of computer-aided molecular design 30 (2016): 595-608.

[6] Li, Guohao, et al. "Training graph neural networks with 1000 layers." International conference on machine learning. PMLR, 2021.

[7] Chen, Ming, et al. "Simple and deep graph convolutional networks." International conference on machine learning. PMLR, 2020.

[8] Zhao, Lingxiao, and Leman Akoglu. "Pairnorm: Tackling oversmoothing in gnns." arXiv preprint arXiv:1909.12223 (2019).

[9] Guo, Xiaojun, et al. "Contranorm: A contrastive learning perspective on oversmoothing and beyond." arXiv preprint arXiv:2303.06562 (2023).

[10] Jaiswal, Ajay, et al. "Old can be gold: Better gradient flow can make vanilla-gcns great again." Advances in Neural Information Processing Systems 35 (2022): 7561-7574.

2. The experiments in the transductive setting.

Thanks for your comments. We conduct experiments in the setting of transductive training. The results are as follows.

3. The drop of the performance of NOSMOG compared to that reported in the original paper.

Thanks for your comments.

We train MLPs using the source code of NOSMOG in the inductive setting. We speculate that the reasons for the drop of performance of NOSMOG compared to that reported in the original paper are as follows.

In the original paper, the authors train NOSMOG in the transductive setting and a loose inductive setting (with only 20% of test nodes invisible to the models). In these settings, the teacher model's predictions on most test nodes are available to students, hence the students can directly fit the predictions of their teachers on test nodes to achieve comparable or even superior performance to the teachers. However, we conduct experiments in the strictly inductive setting, which is more challenging for student MLPs than the experiment settings in the original paper.

Dear Reviewer 8ZML,

Thank you again for your careful reading and insightful comments, which are of great significance for improving our work. The deadline for the discussion stage is approaching, and we are looking forward to your feedback and/or questions. We sincerely hope that our rebuttal has properly addressed your concerns. If so, we would deeply appreciate it if you could raise your score. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission.

Best,

Authors

We thank the reviewer for the insightful and valuable comments. We respond to your comments as follows and sincerely hope that our rebuttal could properly address your concerns. If so, we would deeply appreciate it if you could raise your score. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission.

1. The conclusion obtained from Theorem 1 is obvious.

Thanks for your comments.

Theorem 1 guarantees that we can distill a deep GNN into a shallow GNN, as there exist some shallow GNNs that have similar expressive power to the deep GNN. This conclusion is significant for the distillation of deep GNNs and is surprising in a way, as the numbers of neighbor hops included in the computation of each node in deep GNNs and shallow GNNs are very different.

Specifically, Theorem 1 shows that the minimum approximation error of $\mathbf{H}_S^{(M)}$ to $\mathbf{H}_T^{(L)}$ in terms of the Frobenius norm has an upper bound that decreases monotonically with respect to $M$. Furthermore, we empirically demonstrate that the upper bound converges exponentially to zero as $M$ increases.

2. How to apply the EPIC bound and select the hyperparameter $\gamma$ in practice?

Thanks for your comments.

After reading your comments, we remove the hyperparamter $\gamma$ and instead use the EPIC bounds to narrow the range of tuning the number of student layers as follows.

1. We compute the EPIC bounds $(u_{\rm EPIC}(M;L))_{M=1}^{L-1}$ .
2. We plot $u_{\rm EPIC}(M;L)$ as a function of $M$, as shown in Figure 1.
3. By observing the plot, we find the maximum value $M_{\max}$ such that $u_{\rm EPIC}(M;L)$ decreases slowly when $M>M_{\max}$.
4. We tune the hyperparamter $M$ in $[1, M_{\max}]$.

Because $u_{\rm EPIC}(M;L)$ converges exponentially to zero as $M$ increases, $M_{\rm max}$ is usually much smaller than $L$. Thus, we can significantly reduce the range of tuning $M$.

3. The complexity of computing the EPIC bound is high.

Thanks for your comments.

Please note that we do not need to compute EPIC bounds in the inference stage of GNNs, hence the computation of EPIC bounds does not affect the inference speed of GNNs, which is the focus of this paper and most knowledge distillation methods.

Dear Reviewer G7rf,

Thank you again for your careful reading and insightful comments, which are of great significance for improving our work. The deadline for the discussion stage is approaching, and we are looking forward to your feedback and/or questions. We sincerely hope that our rebuttal has properly addressed your concerns. If so, we would deeply appreciate it if you could raise your score. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission.

Best,

Authors

We thank the reviewer for the insightful and valuable comments. We respond to your comments as follows and sincerely hope that our rebuttal could properly address your concerns. If so, we would deeply appreciate it if you could raise your score. If not, please let us know your further concerns, and we will continue actively responding to your comments and improving our submission.

1. The selection of the hyperparameter $\gamma$ and the corresponding cost.

Thanks for your comments.

After reading your comments, we remove the hyperparamter $\gamma$ and instead use the EPIC bounds to narrow the range of tuning the number of student layers as follows.

1. We compute the EPIC bounds $(u_{\rm EPIC}(M;L))_{M=1}^{L-1}$ .
2. We plot $u_{\rm EPIC}(M;L)$ as a function of $M$, as shown in Figure 1.
3. By observing the plot, we find the maximum value $M_{\max}$ such that $u_{\rm EPIC}(M;L)$ decreases slowly when $M>M_{\max}$.
4. We tune the hyperparamter $M$ in $[1, M_{\max}]$.

Because $u_{\rm EPIC}(M;L)$ converges exponentially to zero as $M$ increases, $M_{\rm max}$ is usually much smaller than $L$. Thus, we can significantly reduce the range of tuning $M$.

2. The complexity of computing the EPIC bound is high.

Thanks for your comments.

Please note that we do not need to compute EPIC bounds in the inference stage of GNNs, hence the computation of EPIC bounds do not affect the inference speed of GNNs, which is the focus of this paper and most knowledge distillation methods.

3. The relationship of our linear-based theory to non-linear graph models.

Thanks for your comments.

The reason why we analyze the expressive power of GNNs from a linear perspective is that this is a standard practice [1, 2], and that existing works [1, 3] have demonstrated that the theoretical analysis under the linear assumption is applicable to general non-linear GNNs.

[1] Xu, Keyulu, et al. "Optimization of graph neural networks: Implicit acceleration by skip connections and more depth." International Conference on Machine Learning. PMLR, 2021.

[2] Wang, Xiyuan, and Muhan Zhang. "How powerful are spectral graph neural networks." International Conference on Machine Learning. PMLR, 2022.

[3] Thekumparampil, Kiran K., et al. "Attention-based graph neural network for semi-supervised learning." arXiv preprint arXiv:1803.03735 (2018).

4. The comparison between EPIC and existing GNNs-to-MLPs distillation frameworks is unfair.

Thanks for your comments.

Because we focus on how to select an appropriate student that is lightweight, while expressive, and MLP is currently a popular student structure for distilling GNNs, we compare our proposed EPIC with state-of-the-art GNNs-to-MLPs distillation frameworks. As mentioned in Section 6.2, we attribute the reason for the unsatisfactory performance of GNNs-to-MLPs frameworks to the weak expressive power of MLPs. The experiments support our claim in Introduction that "MLPs are not 'good students' for distilling deep GNNs".

5. Experiments of baselines that train the GNN with fewer layers from scratch.

Thanks for your comments.

We conduct experiments of training student GNNs with fewer layers from scratch on the three OGB datasets. The results are as follows.