Fast Graph Sharpness-Aware Minimization for Enhancing and Accelerating Few-Shot Node Classification

Thank you for your valuable comments and reviews. We provide a point-by-point response below. Hope this can address your concern and make things clearer.

Q1: What is the standard deviations for the results in table 4? Are the improvements significant?

Response to Q1: The detailed standard deviations for the results presented in Table 4 are provided in Table 8, located in Appendix D.3. In order to assess the significance of the observed improvements, we performed paired t-tests on the results obtained from ten repeated trials comparing SAM with FGSAM and FGSAM+, respectively, across each dataset. The null hypothesis for these tests was that the performance of SAM would not be inferior to that of FGSAM or FGSAM+. The outcomes of these statistical tests are encapsulated in the Table A and Table B. In these tables, the plus symbol denotes levels of statistical significance, with +, ++, and +++ corresponding to significance levels of 5%, 1%, and 0.1%, respectively. The results indicate that both FGSAM and FGSAM+ achieve statistically significant improvement compared with SAM in most cases.

Table A. FGSAM vs SAM

Table B. FGSAM+ vs SAM

Q2: Is there any theoretical justification for PeerMLP?

Response to Q2: Our Theorem 4.1 in the paper demonstrates that under the linear case, whether the MP layer is used or not, the optimal decision bound is the same in the context of K-classes CSBM. We believe this theorem can give some valuable insight in using PeerMLP. Moreover, our approach reintroduces the graph topology in minimization. This is essentially different from PeerMLP which does not involve any graph topology information in training.

Q3: What is g in equation (8)?

Response to Q3: The term $g$ is defined as $\nabla_w L_{D_{\text{tr}}}(w)$, referred to line 189 in page5. This represents the vanilla gradient of the loss function $L$ with respect to the weights $w$, computed on the training dataset $D_{\text{tr}}$.

Q4: The proof of theorem 4.1 is confusing. Do you assume all nodes have the same degree deg(I)?

Response to Q4: We do not assume all nodes having the same degree. The theorem and its proof are based on the definition of the K-classes CSBM, as detailed between Lines 218 and 226 of our manuscript. In the context of CSBM, while it is true that the expected degree of nodes within the same class is identical, it is crucial to note that this does not necessitate uniformity in the actual degrees across all nodes.

Dear Reviewer phcW,

We hope our rebuttal sufficiently addressed your concerns. Is there any additional information we can provide that might lead you to increase your rating? We look forward to your feedback.

Many thanks,

Author

We thank you for acknowledging our work and for raising the score. Thanks again for your time and effort in reviewing our work.

Thank you for your valuable comments and reviews. We provide a point-by-point response below. Hope this can address your concern and make things clearer.

W1: There are related work on applying SAM to few-shot tasks (Sharp-MAML) [1] and performing SAM every k steps [2], and the innovation of this work is not significant compared with the above work.

Response to W1: Both Sharp-MAML [1] and LookSAM [2] focus on vision data, while our work is crafted in the context of graph data. Specifically, we utilize GNNs for parameter perturbation while employing MLPs to minimize the perturbed loss. Our experimental results demonstrate that directly applying SAM-like algorithms from the vision domain to graphs does not yield satisfactory performance (refer to Table 2, Table 3, and Figure 5), while our method is not only faster but also better. This indicates the necessity for SAM variants that are specifically designed for graph data. Furthermore, although sharp-MAML applies SAM to few-shot tasks, their algorithm is only designed for MAML models. In contrast, our work can be applied to both MAML and non-MAML methods in GNN-based FSNC tasks. Most notably, from the perspective of SAM, our work is crafted for graphs by its unique property, enabling the first SAM-like algorithm that can be faster than the base optimizer. This effectively turns SAM's core drawback of slower training speed into an advantage, distinguishing our work from previous SAM-like works.

Q1: Lacking comparisons with the latest baseline methods of FSNC such as COSMIC [3] and COLA [4], in theoretical analysis and experiments.

Response to Q1: Our proposed FGSAM is fundamentally orthogonal to GNN-based FSNC models, such as COSMIC and COLA, due to its unique positioning as a SAM-like optimizer designed to leverage the intrinsic properties of GNNs. We selected classical and widely used FSNC models and NC models for evaluation. The strategy is borrowed from previous SAM works, where they also select classical and widely used models in the vision domain. We believe the selected baseline is diverse enough to verify the effectiveness of our proposed methods.

However, we are glad to provide additional experiments on integrating FGSAM with state-of-the-art FSNC methods, such as COSMIC [3].

Due to the time limitations, we evaluate our proposed method on COSMIC with 5N3K setting only on CoraFull and DBLP. As shown in the above table, FGSAM/FGSAM+ can effectively improve the performance of COSMIC, demonstrating the superiority of our proposed method.

Q2: Why adding 25% noisy edges yields better results than adding only 15%? in Figure 4?

Response to Q2: Firstly, we found a typo in the coordinate axis labels in the original manuscript. The correct coordinate axis should be 0%, 1%, 5%, 10%, 15%, not as previously misstated. Consequently, the observed phenomenon is that adding 10% noisy edges yields better results than adding only 5%.

We appreciate the reviewer's interest in this intriguing phenomenon. In response, we conduct similar experiments on the AMM-GNN to validate the consistency of this phenomenon across different models. The results are presented in the following table:

It can be seen that adding 10% noisy edge also yields better results than adding 5%, similar to the results on GPN. Hence, we suppose that this phenomenon may be attributed to the uniform introduction of a 10% noisy edge, which perhaps aligns more closely with certain inherent characteristics of the dataset, thereby mitigating the extent of performance degradation.

We thank you for acknowledging our work. Thanks again for your time and effort in reviewing our work.

We sincerely appreciate your constructive feedback and valuable comments on our manuscript. We found that your comments are really valuable to further improve our manuscript. Below, we address each of your concerns and questions:

Q1: I think the paper is very good and clear in most cases. The only weaknesses I would note (and this may be subjective) would be to make some style improvements in the beginning of the paper.

Response to Q1: Thanks for your careful pointing out. We will improve our writing in the revision.

Q2: I find the paragraph containing lines 137-145 hard to read due to how the ideas are presented: "Inspired by previous work...we propose to remove MP during training, but reintroduce it..Reintroducing MP after training can improve the performance significantly but still cannot surpass GNNs...""Henve we propose minimizing training loss on PeerMLPs but minimizing the sharpness according to GNNs. There seems to be some logical oscillation in the text. First it seems that a scheme similar to PeerMLP is uses where the GNN is removed during training and injected back during inference. In the next few sentences, this seems to be abandoned and the GNN brought back for the SAM portion of training. I believe the experiments and ideas really did implement the latter formulation but either I'm misunderstanding or this paragraph could use some work to be clearer.

Response to Q2: Thank you for your valuable feedback, which has highlighted an area of our text that could benefit from greater clarity. In response, we would like to clarify that our approach indeed adopts the latter formulation mentioned, wherein MP is partially removed during training, with the reintroduction of GNN for the SAM portion of the training. The intent of our original discussion was to illustrate the relative performance of PeerMLP, acknowledging its merits yet also its limitations, thereby motivating our proposed method. To address the issue raised, we will revise the mentioned text to ensure the presentation of our idea is more clear and logical.

Q3: In Table 8 in the Appendix, I don't believe the best results are actually in boldface. Maybe this was due to my printer or perhaps the table needs to be reformatted?

Response to Q3: Thanks for pointing out this! Upon review, we found that the boldfacing issue in Table 8 was indeed a formatting oversight on our part. We will correct this in the revised manuscript.