Theoretical Analyses of Hyperparameter Selection in Graph-Based Semi-Supervised Learning

We would like to thank the reviewer for carefully reading our submission and providing insightful comments. Please find our responses below.

Other Hyperparameters: Thank you for raising this question. In our work, we only consider the model hyperparameter, such as weights for regularization terms and architecture hyperparameter in GNN-based models. The hyperparameters used in learning and optimization, such as learning rate and weight decay, are outside the scope of this work. We have modified the abstract and introduction of our paper to clarify this.

Assumption for GNN-based Models: Our assumption is given in the description of Proposition 4.1. Here, the independence assumption is made for the problem instance (i.e. the original $m$ problem instances, each with $n$ nodes), not the computation trees. Moreover, the assumption that the computation trees follow the distribution defined in line 382 is simply an analytical technique, saying that the mean of loss of these computation trees is the same as the mean of loss of the whole graph.

Our work indeed adopts the transductive learning setting within each graph, where labeled and unlabeled nodes are interdependent due to their shared structure. However, when it comes to evaluating the generalizability of the learned hyperparameter, we transition to an inductive setting. Specifically, we learn the hyperparameter from $m$ graphs, each containing labeled and unlabeled nodes, and then investigate how well this hyperparameter performs on entirely new graphs.

Additional Experiment for Theoretical Results: Thank you for your suggestion. In response, we have added a new set of experiments (in Section 5.1) to validate the theoretical results in Section 3. For the GNN families, however, directly verifying our theoretical results empirically is challenging. The derived bounds involve multiple constants that are difficult to compute explicitly, making direct validation infeasible at this stage. However, we want to emphasize that we already included the complete proofs of all theoretical results in the file, ensuring clarity and transparency.

Mistake in Proof: Thank you for pointing it out. We have revised the proof accordingly. However, this update does not affect the result of Theorem 4.2 presented in the main body.

We hope we have addressed most of your concerns. If you have any questions, please don't hesitate to reach out to us.

We would like to thank the reviewer for their time and insightful comments. Please find our responses below.

Multiple Hyperparameters: Exploring the tuning of multiple hyperparameters is indeed an important direction for future work. As mentioned in the conclusion section (Lines 537–539), this is a topic we recognize as an intriguing area for further research. While tuning multiple hyperparameters introduces additional complexity, we anticipate that our proposed techniques could still be valuable. For GNN-based algorithms, we believe that Rademacher Complexity could still serve as an appropriate complexity measure. Following a similar strategy, we would aim to bound the change in predicted values as hyperparameter values vary and then apply a covering argument. For label propagation-based methods, our approach would focus on analyzing changes in predicted classes by examining the scoring matrix. This lays a foundation for extending our techniques to address the challenges of multi-hyperparameter tuning in various algorithmic contexts, although they are outside the scope of this work.

Generalize to Other Algorithms: We used unified proof techniques for all three label propagation-based methods, and used a unified proof outline for both SGC and GCAN. Therefore, we believe our proof strategy could be useful when investigating other label propagation-based and GNN-based methods.

Scale with Different Dataset Size and Graph Structure: The dependency on the graph size and graph structure are already indicated in the theoretical results. The graph size is denoted by $n$, the number of labeled and unlabeled nodes. The graph structure is indicated by the degree matrix $D$ and adjacency matrix $W$. In the bounds, they are captured by the lower and upper bounds of the degree matrix, $C_{dl}$ and $C_{dh}$.

Interpolating Other GNN Architecture: As long as the two architectures share the same structure in part of their calculation (e.g. the update equations of GAT and GCN both have the form of activation and a summation over the feature of all neighboring vertices in the graph), we can introduce a new variable to interpolate between the two.

We hope we have addressed most of your concerns. If you have any questions, please don't hesitate to reach out to us.

We thank the reviewer for carefully reading our submission and providing many insightful suggestions. We are happy to address ALL your comments as below:

Rademacher Complexity proof: We would like to highlight that the problem setting in our work is fundamentally different from that of Garg et al. Their study focuses on graph classification with fixed hyperparameters, while our work addresses node classification with the simultaneous learning of both model parameters and hyperparameters. To the best of our knowledge, our work is the first to provide a theoretical guarantee for hyperparameter tuning in GNNs. We have discussed this distinction in Lines 361-365 of the paper. While the proofs share a similar underlying approach, the inclusion of hyperparameters—i.e. the self-loop weight $\beta$ in SGC and the interpolation parameter $\eta$ in GCAN—adds substantial complexity to the problem we tackle.

Paper's Position: The primary focus of our work is the theoretical analysis of hyperparameter selection. This is clearly indicated by our title. Also, we mentioned in line 444 that the proposed interpolation architecture GCAN is not our main contribution.

GCAN Experiments: The purpose of GCAN is not to outperform both GCN and GAT significantly. GCAN is an initial step towards solving the more complex problem of automatically selecting from multiple model architecture. It is not surprising that, when GAT and GCN perform similarly, the improvement of GCAN with optimal $\eta$ does not differ from that of other $\eta$ values by much. Additionally, we want to emphasize that, regardless of the practicability of GCAN, the theoretical guarantees provided in our Theorem 4.1 and 4.2 are themselves novel.

Definition of $n$: $n$ refers to the "total labeled and unlabeled nodes", which is equivalent to the "number of instances per problem". Note that $n$ is different from $m$. $m$ is defined as the total number of problem instances (graphs), where each problem instance contains $n$ nodes.

Dependence on $n$ in Theorem 4.2, 4.3: There are no direct dependences on $n$, but the dependence on the number of nodes is implicitly captured by the more fine-grained value $C_{dl}, C_{dh}$, and $C_Z$. Here, $C_{dl}$ and $C_{dh}$ are the lower and upper bounds of the degree of the nodes. For a larger $n$, $C_{dl}$ and $C_{dh}$ should be larger in general. $C_Z$ is the Frobenius norm of the feature matrix $Z \in \mathbb{R}^{n \times d}$. Since the size of $Z$ scales with $n$, the value of $C_Z$ is generally larger for larger $n$. We really appreciate this question. We have added a Remark to clarify this.

Rationale for GCAN's Hyperparameter: In practice, neither GAT nor GCN consistently outperforms the other, as demonstrated by Dwivedi et al. (2023). To address this, we introduce the hyperparameter $\eta$, which enables the automatic selection between GAT and GCN, effectively combining their strengths. This motivation was included at the beginning of Section 4.2.

Vijay Prakash Dwivedi, Chaitanya K Joshi, Anh Tuan Luu, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks. Journal of Machine Learning Research, 24(43):1–48, 2023.

Extension to Node and Graph Classification: We are indeed investigating hyperparameter selection for node classification in GNN. The analysis in Garg et al. is for graph classification with fixed hyperparameters. We agree that extending analysis on hyperparameter tuning to graph classification is an interesting direction for future research. We believe our approach could serve as a valuable foundation or inspiration for tackling such problems.

Methods Beyond GNN: We would like to highlight that we have already explored label propagation-based methods in section 3 of our paper, which is fundamentally different from GNN. Label propagation-based algorithms and GNN-based algorithms are two major graph-based semi-supervised learning methods. We believe that the insights and arguments presented in our work are applicable and valuable for any algorithms of these two types as well as other related methods.

CIFAR10 as Graph Dataset: For CIFAR10, we first calculate the Euclidean distance between the feature vectors of each pair of nodes and then put an edge between the two nodes if their distance is smaller than a threshold. We apologize for this confusion. We have added this clarification to the description of the experiment setup in Appendix D.

We would like to thank the reviewer for their time and insightful comments. Please find our responses below.

Experiments in the main body (Weakness 1 & 2): Thank you for your suggestion. We have added two sets of experiments in the main body. One experiment is to validate the bound we derived for label propagation-based algorithms, and the other is to show the effectiveness of our hyperparameter selection framework using GCAN. However, we do want to emphasize that the primary focus of our work is the theoretical analysis of hyperparameter selection, as emphasized in our title. We also noted in Line 444 that the proposed interpolation architecture, GCAN, is not the main contribution of our work.

Question: Our primary contribution lies in the theoretical analysis. We provide upper and lower bounds on the sample complexity of any algorithm for tuning the hyperparameters. Therefore, we did not directly compare our method with standard approaches such as grid search or Bayesian optimization. However, we agree that testing and benchmarking hyperparameter tuning methods would be an interesting avenue for future work. The results in Table 1 show the prediction error of GCAN across different $\eta$ values, so it effectively captures the outcomes of a grid search approach.

We hope we have addressed most of your concerns. If you have any questions, please don't hesitate to reach out to us.