Q1: 1) Novelty of the Main Contribution: Can the authors elaborate more on the novelty of their key conclusions, especially regarding the second point in the contribution list? 2) The observation that a strong GNN model might diminish the need for GSL methods feels intuitive and not surprising. 3) How does this work differentiate itself from previous studies in this area? Are there specific aspects of GSL not yet addressed by prior research that the authors are tackling?

For 1) and 2), please refer to our responses to W1.

For 3), we restate how this work differs from previous studies:

1. We are the first to propose a framework that de-compose GSL into 3 aspects, which helps us better understand GSL.
2. We first empirically and theoretically show that there is no mutual information gain for the GSL bases and labels $I(X;Y)$ after applying graph convolution on GSL graphs. This result indicates that GSL is unnecessary in improving graph representation learning in node classification in graphs, as verified by our experiments.
3. We analyze how different GSL components influence the performance of GSL in GNN, which help the model designs in GNNs in the future.

Q2: Theoretical Analysis vs. Derivation: In the introduction, the authors reference a theoretical analysis presented in Appendix B. However, the analysis appears to be more of a mathematical derivation rather than a comprehensive theoretical insight. Could the authors clarify why they classify it as a theoretical analysis? How does this analysis provide deeper understanding beyond the mere derivation of terms?

Please refer our responses to W2. Thank you.

References

[1] 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 In- ternational Conference on Knowledge Discovery & Data Mining, pp. 66–74, Virtual Event CA USA, August 2020. ACM. ISBN 978-1-4503-7998-4. doi: 10.1145/3394486.3403049.

[2] Ruijia Wang, Shuai Mou, Xiao Wang, Wanpeng Xiao, Qi Ju, Chuan Shi, and Xing Xie. Graph Structure Estimation Neural Networks. In Proceedings of the Web Conference 2021, pp. 342– 353, Ljubljana Slovenia, April 2021. ACM. ISBN 978-1-4503-8312-7. doi: 10.1145/3442381. 3449952

[3] Donghan Yu, Ruohong Zhang, Zhengbao Jiang, Yuexin Wu, and Yiming Yang. Graph-Revised Convolutional Network, December 2020. arXiv:1911.07123 [cs, stat].

[4] Yu Chen, Lingfei Wu, and Mohammed Zaki. Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings. In Advances in Neural Information Processing Systems, volume 33, pp. 19314–19326. Curran Asso- ciates, Inc., 2020.

W1: 1) The primary weakness of this work is its lack of novelty. The key conclusion (especially the second point in the contribution list) seems rather obvious, at least to those familiar with GSL methods. Even for those who haven't empirically tested GSL methods, the result isn't surprising. 2) If one assumes that the GNN model is sufficiently strong, it logically follows that the GSL method would be redundant. GSL appears more like an intermediate tool, and a good GNN model should outperform or make GSL unnecessary in an end-to-end training/inference.

1. Thanks for your valuable feedback. To the best of our knowledge, the conclusion, "GSL is unnecessary for improving GNN performance on node classification", is first proposed in our paper. This conclusion is not obvious, otherwise, there won't be so many papers [1, 2, 3, 4] that use GSL to improve GNN performance while adding tremendous computational complexity. While many approaches are trying to add more and more complex model designs in GNNs to get tiny improvement, we want to do reduction in the model design by rethinking the necessity of the GSL. Therefore, we think our work remains a high novelty in this area.

2. We clarify that, in our paper, the redundancy of GSL in improving GNN on node classification tasks is irrelevant to the performance of GNN, because there is no mutual information gain after the operation of graph convolution on GSL graphs, as shown by our empirical studies and theoretical analysis. Besides, for some heterophilous datasets, such as Squirrel, Chameleon, and Actor, where GNN performance is not strong, GSL still cannot improve model performance, as shown in Table 1.

W2: 1)In the last paragraph of the Introduction, the mentioned "theoretical analysis" (Appendix B) feels more like a derivation than a true theoretical analysis. Moreover, the analysis is too coarse-grained and offers little insight. 2) In line 83, the claim that "GSL bases serve as the upper bound" is poorly framed. 3) The GSL bases in this context refer to features, while the upper bound is a scalar term derived from these bases. The way this upper bound argued is a non-professional theoretical claim.

1. Thank you for your constructive suggestions. We have revised "Theorem 1" to "Proposition 1" to enhance its rigor. Additionally, we have clarified the conditions of our proof, which include the independence assumption, Gaussian distribution, and the non-parametric GSL method. We believe these conditions contribute to a more rigorous analysis.
2. We have revised our paper to improve its readability and rigor: "the mutual information (MI) between node representations and labels does not increase after applying graph convolution on GSL graphs constructed by similarity."
3. To make the theoretical claim more professional, we have revised the proof to extend the analysis to multi-dimensional features:

Specifically, given the conclusion we get from a single feature $B_i'^k = \sum_{q=1}^C p_{k,q} B_i^q$ , we apply the chain rule of mutual information to extend this conclusion to multi-dimensional variables.

Due to the property that conditioning reduces entropy, we have

Thus, we have

where $\inf$ represents infimum. Since $I(Y;B'_i)\le I(Y,B_i)$ holds for each $i$, we have

This concludes the proof of Proposition 1.

Please let me know if our responses have addressed your concerns. Thank you!

W3: GSL methods are also widely used to improve the robustness of GNNs by purifying the perturbed graph structures. It would be interesting to see whether the observation and conclusion hold on adversarially perturbed graphs.

We further conduct experiments to investigate the robustness of GSL under noisy graph structures, by randomly adding or deleting edges in graphs following [1]. As shown in Table 16 and Table 17, we randomly add or remove $[0\%, 10\%,\dots, 80\%]$ edges in original graphs. The results show that, generally, GSL-enhanced GNNs are more robust to a higher ratio of noises in graph structures, which is consistent as the results in [1]. There are still some cases where GSL cannot improve the model robustness, such as GAug on CiteSeer. It will be interesting to empirically and theoretically investigate the robustness of GSL-enhanced models in the future. Thanks for your valuable comments.

Ablation study on model robustness by adding edges in GSL-enhanced methods.

Ablation study on model robustness by deleting edges in GSL-enhanced methods.

W4: Existing works suggest GSL algorithms achieve the best results in scenarios with fewer labels available [1]. However, this work only studied the setting of splitting 50%/25%/25% of the nodes in train/validation/test sets. This data split setting differs from what is used in some of the GSL papers evaluated. I would suggest the author study the impact of label ratio on the effectiveness of the GSL methods.

We further conduct an ablation study on the performance of GSL-enhanced methods. As shown in Table 18, the performance of these GSL-enhanced methods is comparable to their counterparts without GSL when there are $20$ labels per class. However, as we decrease the supervision ratio (such as in scenarios with $5$ or $3$ labels per class) the GSL-enhanced methods demonstrate improved performance compared to those without GSL. These results indicate that GSL can effectively enhance GNN performance in settings with low supervision. Thanks for your suggestions. We have revised the paper to include this valuable finding.

Q1:

See the above responses to W2.

Q2:

See the above responses to W1.

Q3:

See the above responses to W3.

Q4:

See the above responses to W4.

Reference

[1] Li, Zhixun, et al. "GSLB: the graph structure learning benchmark." NeurIPS 2023.

[2] Zhiyao, Zhou, et al. "Opengsl: A comprehensive benchmark for graph structure learning." NeurIPS 2023.

[3] Khoshraftar S, An A. A survey on graph representation learning methods[J]. ACM Transactions on Intelligent Systems and Technology, 2024, 15(1): 1-55.

[4] Ju W, Fang Z, Gu Y, et al. A comprehensive survey on deep graph representation learning[J]. Neural Networks, 2024: 106207.

[5] 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 In- ternational Conference on Knowledge Discovery & Data Mining, pp. 66–74, Virtual Event CA USA, August 2020. ACM. ISBN 978-1-4503-7998-4. doi: 10.1145/3394486.3403049.

[6] Ruijia Wang, Shuai Mou, Xiao Wang, Wanpeng Xiao, Qi Ju, Chuan Shi, and Xing Xie. Graph Structure Estimation Neural Networks. In Proceedings of the Web Conference 2021, pp. 342– 353, Ljubljana Slovenia, April 2021. ACM. ISBN 978-1-4503-8312-7. doi: 10.1145/3442381. 3449952

[7] Donghan Yu, Ruohong Zhang, Zhengbao Jiang, Yuexin Wu, and Yiming Yang. Graph-Revised Convolutional Network, December 2020. arXiv:1911.07123 [cs, stat].

[8] Yu Chen, Lingfei Wu, and Mohammed Zaki. Iterative Deep Graph Learning for Graph Neural Networks: Better and Robust Node Embeddings. In Advances in Neural Information Processing Systems, volume 33, pp. 19314–19326. Curran Asso- ciates, Inc., 2020.

[9] Derrick Blakely, Jack Lanchantin, and Yanjun Qi. Time and space complexity of graph convolutional networks. Accessed on: Dec, 31:2021, 2021.

W1: Only the node-level learning task, i.e., node classification, is studied in this work. However, GSL is also widely used for graph-level learning tasks, such as graph classification.

Thanks for your constructive comments. In our submission, we only test the performance on node classification because node classification has been widely used to quantify the performance of GNN on graph representation learning [3,4]. In addition to the node classification experiments, we further investigate whether GSL consistently improves GNN performance in graph classification. Specifically, we conduct ablation experiments by replacing the GSL graph with the original graph, following the methodology outlined in [1]. As shown in 15, removing GSL from $4$ state-of-the-art GNNs, including ProGNN [5], GEN [6], GRCN [7], and IDGL [8], results in significantly reduced training time. At the same time, the GNN performance remains comparable to that of the GSL-enhanced counterparts. This suggests that GSL does not consistently enhance GNN performance in graph classification. Due to page limitations, we only tested a few methods in this paper. We believe it would be valuable to explore additional state-of-the-art methods, datasets, and theoretical justifications for the effectiveness of GSL in graph classification in future work.

W2: Only small-scale datasets are studied in this work.

The reason why we only conduct our experiments only on small-scale graph is because most GSL methods face the issue of high computation complexity. As shown in Section 4.3 complexity analysis in our submission, the total additional complexity of GSL is $O(|\mathcal{V}|^2F+|\mathcal{V}|F^2)$. Compared with the complexity in normal GCN $O(|\mathcal{E}|F+|\mathcal{V}|^2)$ [9], this additional complexity $O((|\mathcal{V}|^2-|\mathcal{E}|F)$ adds tremendous training time and grows exponentially with the number of nodes in graphs. To address this issue, further adaptations in node sampling, mini-batch training, or graph partitioning are required, which can vary considerably within our framework. Consequently, recent GSL studies [1, 2, 5, 6, 7, 8] have primarily focused on small-scale graphs. Nonetheless, it remains an intriguing question to explore the effectiveness of GSL when considering these additional adaptations. Thank you for your insightful review.

Please let me know if our responses have addressed your concerns. Thank you!

We have added additional results for W3, where we investigate model robustness under noisy features. The findings indicate that as the amount of feature noise increases, GSL tends to outperform baseline GNNs. Please let us know if your concerns have been addressed. Thank you!

W1: 1) While this paper presents an interesting observation of GSL. It is not clear how this observation could help move GSL forward. The key observation is that GSL may not be the major contributor of model performance improvment but rather some other components are. 2) This is a huge claim that tries to deny the previous efforts in GSL. 3) I wonder if there is any certain scenario where GSL is still helpful?

1. Thanks for your valuable review. To help move GSL forward, in our submission, we demonstrate how different components in GSL influence model performance: 1) Figure 5 and Figure 6 show that using pertained node representations, e.g. MLP($X$,$A$), GCN($X$,$A$), or GCL($X$,$A$), as GSL bases significantly improve GNN performance on heterophilous datasets. 2) Figure 7 shows that kNN-based GSL graphs construction slightly outperforms other types of construction methods. 3) Figure 8 shows that that late fusion with no parameter sharing achieves the best performance compared with other types of fusion strategies. 4) Figure 9 shows that early fusion is better than late fusion for the fusion stage. Finally, we conduct extension experiments by removing GSL in GNN to show that it is the good quality of GSL bases instead of GSL graph construction that improves GNN performance, which is verified by extensive experiments that adding GSL to GNN baselines or removing GSL in SOTA GSL methods.
2. The reason why we make such a claim is because we have carefully reviewed most GSL methods and analyzed how they are different from each other in our proposed GSL framework as shown in Figure 2 and Table 3. Since it is impossible to implement all types of GSL methods in the experiments, we implement the most representative GSL components, which derive 360 combinations in our experiments. We believe these methods could cover the most representative GSL methods, plus with the SOTA-GSL experiments, which verifies our claim. Admittedly, we also revise our claim to make it more specific and accurate. Thank you.
3. We only show that GSL is not necessary for improving the quality of graph representation learning by node classification in our experiments. To see if GSL is still helpful in other scenarios, we conduct additional experiments on graph classification (Appendix E.7), perturbed graphs (Appendix E.8), and few-shot learning (Appendix E.9). Our results show that GSL is also unnecessary in graph classification, but it is more effective than baseline GNNs in perturbed graphs and few-shot learning.

We have revised our paper. Thank you for your valuable feedback.

W2: In Table 2, there is a difference between the result of the current paper and result from [1]. Is there an explanation for this?

We follow the same setting as in [1]. In some datasets, we can get higher results than the reported results, such as GEN in pubmed and GRCN in amazon-ratings. While in other datasets, the results are slightly lower than the reported results, such as GAUG in citeseer and GRCN in roman-empire. Thanks for your suggestions, we have revised the table to get a higher performance of GSL-based SOTA methods. As shown in Table 1, this result still supports our conclusion that by removing GSL in SOTA methods we can still get comparable performance.

Thank you again for your valuable feedback.

References

[1] Zhiyao Z, Zhou S, Mao B, et al. Opengsl: A comprehensive benchmark for graph structure learning[J]. Advances in Neural Information Processing Systems, 2024, 36.

References

[1] Khoshraftar S, An A. A survey on graph representation learning methods[J]. ACM Transactions on Intelligent Systems and Technology, 2024, 15(1): 1-55.

[2] Ju W, Fang Z, Gu Y, et al. A comprehensive survey on deep graph representation learning[J]. Neural Networks, 2024: 106207.

[3] Luan S, Hua C, Lu Q, et al. Revisiting heterophily for graph neural networks[J]. Advances in neural information processing systems, 2022, 35: 1362-1375.

[4] Abu-El-Haija S, Perozzi B, Kapoor A, et al. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing[C]//international conference on machine learning. PMLR, 2019: 21-29.

[5] Halcrow J, Mosoi A, Ruth S, et al. Grale: Designing networks for graph learning[C]//Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining. 2020: 2523-2532.

[6] Garcia V, Bruna J. Few-shot learning with graph neural networks[J]. arXiv preprint arXiv:1711.04043, 2017.

[7] Alexander Kraskov, Harald Stogbauer, and Peter Grassberger. Estimating mutual information. ¨ Physical Review E—Statistical, Nonlinear, and Soft Matter Physics, 69(6):066138, 2004.

[8] Brian C Ross. Mutual information between discrete and continuous data sets. PloS one, 9(2): e87357, 2014.

[9] Lyudmyla F Kozachenko and Nikolai N Leonenko. Sample estimate of the entropy of a random vector. Problemy Peredachi Informatsii, 23(2):9–16, 1987

[10] Abramowitz, M.; Stegun, I. A., eds. (1972). "6.3 psi (Digamma) Function.". Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables (10th ed.). New York: Dover. pp. 258–259.

[11] Kraskov A, Sto¨gbauer H, Grassberger P (2004) Estimating mutual information. Physical Review E 69: 066138.

W5: Many methods show that graph structure is indeed useful for their application, including GSL approaches with more sophisticated edge-creation functions [5] or trainable graphs [6].

Thanks for your suggestions. We further conducted experiments on two GSL-enhanced GNNs, Grale [5] and MetricNN [6], using the same settings as in our previous experiments. As shown in Table 19, removing GSL from these methods resulted in improved model performance on most datasets, along with reduced training time. These findings further support the conclusion drawn in this paper that GSL is unnecessary for enhancing model performance in node classification.

For more scenarios, we conduct additional experiments to investigate the effectiveness of GSL under more settings: graph classification (Appendix E.7), perturbed graphs (Appendix E.8), and few-shot learning (Appendix E.9). We find that GSL is also unnecessary in graph classification, but it is more effective than baseline GNNs in perturbed graphs and few-shot learning. We have revised our paper. Thank you.

Q1: How did you calculate the mutual information? It seems that one must integrate over the input space.

In the Preliminary Section, we describe how mutual information is calculated: we measure the mutual information $I(X;Y)$ based on entropy estimation from k-nearest neighbors distances following [7,8,9]. Here, we further clarify the calculation of mutual information.

Given a continuous variable $X$ and a discrete variable $Y$, we start with $N$ data points $(x_i, y_i)$. To compute the mutual information $I(X;Y)$, for each point $i$, we find the k-th nearest neighbor in $X$-space, considering only points where $y = y_i$. We denote the distance to this neighbor as $d$. Next, we count the total number of points in the dataset within this distance $d$, denoting this count as $m_i$, and the total number of points where $y = y_i$ as $N_{y_i}$. We then use the formula $I_i = \psi(N) - \psi(N_{y_i}) + \psi(k) - \psi(m_i)$ where $\psi$ is the digamma function [10], to calculate the contribution of each point to the mutual information. The overall mutual information is then given by the average of all $I_i$: $I(X, Y) = \frac{1}{N} \sum_{i=1}^{N} I_i$ This method avoids binning [11] and works efficiently for both scalar and vector data, while addressing a small k-balancing detail and noise.

Thanks for your review, we have carefully revised our manuscript with respect to your concerns.

W4: Why use untrainable kNN?

1. We clarify that kNN is one implementation of similarity-based GSL: As shown in Table 1, we further include Cos-graph and Cos-node as the GSL graph construction approaches.
2. Only the results in Table 1 are conducted with untrainable GSL, while in Table 2 GSL graphs in SOTA methods are trainable.

In addition to the non-learnable kNN, we further conduct experiments on trainable GSL graphs on $6$ GNN backbones as shown in Table 14. Specifically, we select the best-performing GSL variants, as shown in Tables 1 and 13, for each backbone GNN. The best-performing method is highlighted in bold, while the runner-up is highlighted in Italic. "OOM" refers to "out of memory." The results demonstrate the following

1. The average rank indicates that trainable GSL improves GNN performance on 5 out of 6 GNN backbones.
2. Although trainable GSL outperforms non-trainable GSL, it remains inferior to GNN backbones without GSL, indicating that GSL could be unnecessary in improving GNN performance on node classification.

W1: The arguments are too general: GSL does not add information.

Thanks for your valuable comments on improving our paper. We have revised the claim to make it more specific: Similarity-based GSL cannot improve GNN performance on node classification. The reason why we claim this in our submission is because:

1. Similarity-based GSL are the most dominant approaches to construct new graphs. As the representative methods listed in Table 3, 18 out of 22 GSL methods are similarity-based GSL, showing that the analysis of GSL in this paper has more generality.
2. Node classification has been widely used to quantify the performance of GNN on graph representation learning [1,2].

Admittedly, even though we tried our best to consider the most representative approaches in GSL in this paper, there are still some cases cannot be covered. Therefore, we have carefully revise the manuscript to make it more specific. Thank you!

W2: The construction is too-specific.

First, we admit that GSL has been developed for many years and many new methods are proposed. Since it is impossible to implement all the GSL methods in our paper, that's why we first propose a framework to de-composite each component of GSL and then implement the most representative GSL approaches for each component. As shown in Appendix D in our submission, our implementation includes: 4 GNN backbones: GCN, GAT, GraphSAGE, and SGC, 5 GSL bases: $X$, $\hat{A}X$, MLP($X$), GCN($X$,$A$), and GCL($X$,$A$), 3 GSL graph construction approaches: Cos-graph, Cos-node, and kNN, 3 view fusion methods: $\{\mathcal{G}'\}$, $\{,\mathcal{G},\mathcal{G}'\},\theta_1=\theta_2$, $\{,\mathcal{G},\mathcal{G}'\},\theta_1\neq \theta_2$, and 2 types of fusion strategies: early fusion and late fusion. This implementation covers most GSL approaches as shown in Table 3. The combination of these components derives 360 different methods of GSL, which has never been explored in previous studies.

Besides, to consider more sophisticated GSL methods, in our submission, we further conduct an ablation study by removing GSL components in 8 state-of-the-art (SOTA) GSL-based GNNs in Table 2, the results also support our claim that GSL cannot improve GNN performance on node classification.

W3: Why use GCN if you are connecting on-purpose heterophilous edges? Why not use something like MixHop which (promises to) handle heterophilous edges?

Thanks to your suggestions, we further implement ACMGNN [3], MixHop [4] in our experiments that incorporate GSL into GNN baselines. These experiments follow the same setup as described in Table 1. The results, presented in Table 13, demonstrate that, under fair comparison conditions, both ACMGNN and MixHop outperform their GNN+GFS counterparts. This suggests that adding GSL to these heterophily-oriented GNNs cannot improve model performance on node classification.

Please let me know if our responses have addressed your concerns. Thank you!