Rethinking Structure Learning For Graph Neural Networks

Authors: Yilun Zheng, Zhuofan Zhang, Ziming Wang, Xiang Li, Sitao Luan, Xiaojiang Peng, Lihui Chen
Primary area: learning on graphs and other geometries & topologies
Keywords: Graph Neural Networks, Graph Structure Learning

Abstract:
To improve the performance of Graph Neural Networks (GNNs), Graph Structure Learning (GSL) has been extensively applied to reconstruct or refine original graph structures. While GSL is generally thought to improve GNN performance, it often leads to longer training times and more hyperparameter tuning. Besides, the distinctions among current GSL methods remain ambiguous from the perspective of GNN training, and there is a lack of theoretical analysis to quantify their effectiveness. Recent studies further suggest that GSL does not consistently outperform baseline GNNs under the same hyperparameter tuning. This motivates us to ask a critical question: *Is GSL really useful for improving GNN performance?* To address this question, we first propose a new GSL framework, which includes three steps: GSL bases (i.e. node representations used to construct new graphs) construction, new structure construction, and view fusion, to better understand GSL. Then, our empirical studies and theoretical analysis show that the mutual information (MI) between node representations and labels does not increase after applying graph convolution on GSL graphs that are constructed by similarity, indicating GSL could be unnecessary in most cases. Our experiments fairly reassess the performance of GSL and reveal that adding GSL to GNN baselines or removing GSL in state-of-the-art models has negligible impact on node classification accuracy. We also report that pretrained GSL bases, parameter separation, and early fusion are effective designs within GSL. Our findings challenge the necessity of complex GSL methods and underscore the value of simplicity in GNN design.

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

Reviews and discussion:
<thread>
creation date:
1730008932756

thread_type:
official_review

<thread_object>
creator: reviewer_vcb5

<content>
summary:
This study examines critically on the role of Graph Structure Learning (GSL) in improving Graph Neural Networks (GNNs). 
Although GSL has been used to improve GNN performance by capturing semantically similar nodes, the authors claim that there is insufficient theoretical and empirical evidence to support its necessity. The authors also show GSL's training times and the need for extensive hyperparameter tuning.

the paper proposes a new framework for categorizing GSL methods into three components: GSL base generation, new structure construction, and view fusion, which provides a better understanding of GSL's elements.
According to the authors' empirical analysis, GSL does not consistently outperform standard GNN approaches. 
Their findings show that GSL fails to provide more mutual information gain than traditional methods. 
Finally, the authors conclude that non-optimization-based GSL methods are frequently unnecessary because the quality of the original GSL bases guarantees informative node representations. 
This calls into question the prevailing assumptions about GSL's role in effective GNN performance and suggests reassessing its importance in future GNN designs.

strengths:
1. The authors present a GSL framework, which is a valuable contribution. It provides a common terminology and aligns the community on the same page, facilitating clearer communication. Additionally, a unified framework benefits the subsequent empirical comparisons and discussions.

2. The empirical findings are solid. The observations in Section 4.1, particularly Observations 1-3, offer clear takeaways for practitioners. Furthermore, the empirical comparisons in Section 5.1 are thorough and comprehensive.

weaknesses:
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. 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.

2. 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. In line 83, the claim that "GSL bases serve as the upper bound" is poorly framed. 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.

questions:
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? The observation that a strong GNN model might diminish the need for GSL methods feels intuitive and not surprising. 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?

2. 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?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730685398687

thread_type:
official_review

<thread_object>
creator: reviewer_xwum

<content>
summary:
This paper summarizes the designs of graph structure learning (GSL) methods in graph neural networks (GNNs) using the proposed GSL framework. The author proposes to theoretically assess the effectiveness of the GSL methods by using mutual information. Both the empirical experiment results and the theoretical analysis conducted in this paper suggest that GSL methods do not enhance GNN performance when evaluated under the same GSL bases, that is, the representation used for GSL and hyperparameter tuning.

strengths:
1. The paper is clearly written and is generally easy to follow.

2. The paper conducts extensive empirical evaluations.

3. The paper conducts theoretical analysis, which leads to a similar conclusion as the empirical evaluations.

4. The conclusion obtained is interesting and can be helpful in designing efficient graph neural networks.

weaknesses:
1. 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.

2. Only small-scale datasets are studied in this work. 

3. 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.

4. 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.

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

questions:
1. Does the conclusion hold for large-scale graphs, such as ogbn-arxiv?

2. Does the conclusion hold for GNNs with GSL for graph-level learning tasks, such as those in [1]? 

3. Does the conclusion hold for node classification when the graph structure, node features, or class labels are adversarially perturbed as the settings in [1, 2]? 

4. How does the label ratio impact the effectiveness of GSL methods? Can you make the same conclusion when fewer nodes are labeled?

[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.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730745870266

thread_type:
official_review

<thread_object>
creator: reviewer_nzmd

<content>
summary:
This paper analyzes the graph structure learning methods from the perspectives of mutual information. The analysis suggests that no matter which type of GSL methods are used, after feeding the same GSL bases to the newly constructed graph, there is no mutual information gain compared to the original GSL bases. The paper then re-evaluates the graph structure learning using the same GSL bases. The results verify the the analysis.

strengths:
1. This paper approaches GSL from an interesting perspective of information gain.
2. This paper reevaluated GSL methods using the same GSL bases and show the GSL can not consistently improve the performance of GNNs.
3. The paper is overall well written.

weaknesses:
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. This is a huge claim that tries to deny the previous efforts in GSL. I wonder if there is any certain scenario where GSL is still helpful?
2. In Table 2, there is a difference between the result of the current paper and result from Zhiyao et al. (2024). Is there an explanation for this?

questions:
See waeknesses
</content>
</thread_object>

</thread>
<thread>
creation date:
1731278927189

thread_type:
official_review

<thread_object>
creator: reviewer_4unk

<content>
summary:
Paper summarizes the utility of Graph Structured Learning (GSL): Does inferring edges among nodes (when some edges or no edges are given) help classification tasks? For instance, given many examples, one can develop an MLP that can infer on all examples in parallel. Alternatively, one can induce edges among example pairs, and run a GNN on the features+induced graphs.

Authors show that: there are no cases where GSL is useful. In summary, either run an MLP or a GNN on the original graph. If edges are homophonous, then just use GNN on the real edges (no induced edges). If the edges are heterophilous, just ignore the edges altogether and just run an MLP.

strengths:
* It is nice to know this summary [do not induce any edges!]
* The paper's arguments are easy to follow [though writing can be improved]

weaknesses:
The mean weakness of the paper (reason for my rejection) is:

* The arguments are too general: GSL does not add information
* The construction is too-specific.

From reading the paper, I can only remove some generality from the main argument:

* GSL is not useful for **classification** settings where the graph construction function is set to non-learnable KNN.

Crucially, their edge function is the kNN graph. Their GNN is similar to GCN [Kipf&Welling], i.e., one that averages node features with their neighbors, at every layer. Using kNN edges and GCN should work well if neighbor nodes (i.e. k-nearest) have the same class as the center node. This assumption is not met for heterophilous graphs.

None of the findings seem to be surprising. I will make a few notes

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

* Why use untrainable kNN?

Many methods show that graph structure is indeed useful for their application, including https://arxiv.org/abs/2007.12002 or https://arxiv.org/abs/1711.04043 -- the first has more sophisticated edge-creation function and the second is trainable

# Final note

I do like the paper, but I think it can be greatly simplified to one small argument: dont induce kNN graph use in a GCN, instead use MLP -- noting that kNN+GCN is one instantiation of GSL.

questions:
* How did you calculate the mutual information? It seems that one must integrate over the input space.
</content>
</thread_object>

</thread>
<thread>
creation date:
1732532254769

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We would like to express our gratitude to all the reviewers for their valuable feedback. Our paper proposes a general framework for a better understanding of Graph Structure Learning (GSL) in Graph Neural Networks (GNNs). We show that GSL cannot improve GNN performance for node classification tasks, supported by empirical observations and theoretical justifications. Our experiments thoroughly reassess the performance of GSL, revealing that adding GSL to GNN baselines (across 360 combinations) or removing GSL from state-of-the-art models has a negligible impact on node classification accuracy. 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. We would like to clarify the following points during the rebuttal:

1. **Scope of Our Paper:** The primary focus of this paper is to study GNN performance on node classification tasks. This does not imply that we dismiss the broader GSL area. In fact, our findings also indicate that GSL could improve model robustness, an area worth investigating in the future.
2. **Additional Methods:** To explore stronger GNN backbones and more complex GSL methods, we conducted further experiments on two GNN baselines (MixHop[1] and ACMGNN[2], as shown in Table 13) and two GSL-based state-of-the-art methods (Grale[3] and MetricNN[4], as shown in Table 19). We also implemented a trainable GSL (Table 14). The results consistently support our original claim that GSL does not enhance model performance on node classification tasks.
3. **Additional Settings:**
(1) We further investigate the performance of GSL-based state-of-the-art methods on graph classification, as shown in Table 15. The results indicate that GSL does not consistently improve model performance in this context.
(2) We assess the robustness of GSL in Tables 16 and 17, where the results demonstrate that GSL can enhance the robustness of GNNs.
(3) We also conducted experiments on GSL under weakly supervised settings, showing that GSL-based methods outperform their counterparts without GSL in this scenario. However, the main focus of this paper is to determine whether GSL improves model performance on node classification, a question that our experiments have addressed. We believe that the additional settings warrant further investigation in the future.
4. **Improved Presentation:** We have carefully revised our paper to emphasize its contributions and enhance its rigor.

Thank you once again to all the reviewers. **We look forward to your response.**


**References**

[1] 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.

[2] 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.

[3] 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.

[4] Garcia V, Bruna J. Few-shot learning with graph neural networks[J]. arXiv preprint arXiv:1711.04043, 2017.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper studies Graph Structured Learning from the perspective of mutual information. The authors provided theoretical analysis and empirical results. The authors’ experimental results reveal that GSL methods fail to provide additional mutual information gain than the baselines. 

**Strengths:**

1. The paper is well-written with clear takeaway messages and is overall easy to follow
2. It provides terminology for discussion and presents a framework for comparing GSL/GNN methods.
3. The paper provides empirical evaluations and theoretical analysis.

**Weaknesses:**

1. The authors present a too huge (or general) claim “GSL does not provide any additional performance gain”  but the authors studied only a limited setting, classification and KNN graphs. More advanced graph structure learning methods need to be studied. Also, the claim needs to be verified across a wide range of tasks, including graph-level tasks. 
2. The main claim is inconsistent with recent efforts that demonstrate the benefits of GSL. 
3. Empirical results are provided only for small-scale datasets.
4. More thorough theoretical analysis is needed to support the main claim.

In sum, this paper studies the benefits of GSL from the perspective of mutual information and claims that GSL does not provide any additional performance gain. However, this claim is inconsistent with recent results, and the claim needs to be verified in more diverse settings, including advanced GSL methods, graph-level tasks, and larger datasets.