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

Authors: yihong  luo
yuhan  chen
siya  qiu
yiwei  wang
chen  zhang
yan  zhou
xiaochun  cao
jing  tang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-07 13:35:17

Abstract: Graph Neural Networks (GNNs) have shown superior performance in node classification. However, GNNs perform poorly in the Few-Shot Node Classification (FSNC) task that requires robust generalization to make accurate predictions for unseen classes with limited labels. To tackle the challenge, we propose the integration of Sharpness-Aware Minimization (SAM)--a technique designed to enhance model generalization by finding a flat minimum of the loss landscape--into GNN training. The standard SAM approach, however, consists of two forward-backward steps in each training iteration, doubling the computational cost compared to the base optimizer (e.g., Adam). To mitigate this drawback, we introduce a novel algorithm, Fast Graph Sharpness-Aware Minimization (FGSAM), that integrates the rapid training of Multi-Layer Perceptrons (MLPs) with the superior performance of GNNs. Specifically, we utilize GNNs for parameter perturbation while employing MLPs to minimize the perturbed loss so that we can find a flat minimum with good generalization more efficiently. Moreover, our method reutilizes the gradient from the perturbation phase to incorporate graph topology into the minimization process at almost zero additional cost. To further enhance training efficiency, we develop FGSAM+ that executes exact perturbations periodically. Extensive experiments demonstrate that our proposed algorithm outperforms the standard SAM with lower computational costs in FSNC tasks. In particular, our FGSAM+ as a SAM variant offers a faster optimization than the base optimizer in most cases. In addition to FSNC, our proposed methods also demonstrate competitive performance in the standard node classification task for heterophilic graphs, highlighting the broad applicability.

Main paper: 
 introduction: 
 Graph Neural Networks (GNNs) have received significant interest in recent years due to their powerful ability in various graph learning tasks, e.g., node classification. Numerous GNNs have been developed accordingly [14, 19, 34] . Despite their successes, GNNs, like traditional neural networks, tend to be over-parameterized, often requiring extensive labeled data for training to ensure generalization. However, in real-world networks, many node classes have few labeled instances, which can lead to GNNs overfitting, resulting in poor generalization in these limited labeled classes. Recently, an increasing amount of research is focusing on developing superior GNNs, e.g., Meta-GCN [41] , AMM-GNN [36] , GPN [7] and TENT [37] , for Few-Shot Node Classification (FSNC) which aims to classify nodes from new classes with limited labelled instances.Intuitively, training GNNs for FSNC requires robust model generalization ability for recognizing unseen classes from a small number of labelled examples. Motivated by the success of the recently proposed Sharpness-Aware Minimization (SAM) for improving models' generalization in the vision domain [11] , we suggest incorporating SAM into training GNNs for addressing FSNC tasks. The core idea of SAM is to perturb the model parameters to find flat minima of the loss landscape, thereby making the model more generalizable. However, a key drawback of SAM is that it requires executing two forward-backward steps to complete one optimization step, resulting in twice the time consumption compared to general optimizers like Adam. Some works [8, 9, 22] have been proposed to accelerate SAM, but none of them are crafted for graphs, i.e., not leveraging the graph properties for accelerating SAM. This paper mainly focuses on efficient GNN training in FSNC scenarios by leveraging SAM for improving the generalization of GNNs on unseen classes. To tackle the high training cost issue of SAM, we utilize the connection between GNNs and MLPs-GNNs discarding Message-Passing (MP) are equivalent to MLPs with faster training and worse performance in general-to accelerate training. Specifically, we propose Fast Graph Sharpness-Aware Minimization (FGSAM) that uses GNNs for perturbing parameters and employs MLPs (i.e., GNNs discarding MP) to minimize perturbed training loss. This speeds up training at the cost of dropping graph topology information during minimizing the perturbed loss. Interestingly, we find that the gradient computed in parameter perturbation can be reused when minimizing loss to explicitly reintroduce topology information with negligible extra cost. Moreover, we can add back MP during inference to improve performance. To further reduce the computational cost, we propose FGSAM+ which conducts an exact FGSAM-update at every k steps. As shown in Fig. 1 , empirical results in FSNC tasks show that our proposed FGSAM and FGSAM+ methods outperform both Adam and SAM, and meanwhile FGSAM+ is even faster than Adam. In addition, we evaluate the proposed methods in node classification, showing strong results, especially in heterophilic graphs which are known to be challenging for GNNs [6, 29] . This indicates that our proposed methods can effectively improve the GNN's generalization capability for better performance.The contributions of this paper can be summarized as follows.• We study the application of SAM in FSNC tasks.• We propose FGSAM that improves generalization in an efficient way by leveraging GNNs for sharpness-aware perturbation parameters and employing MLPs to expedite training. • We further propose an enhanced version named FGSAM+, which conducts the actual FGSAM at every k steps and approximates it in the intermediate steps.• We demonstrate strong empirical results of the proposed methods across tasks. 
preliminary: 
 Graph Neural Networks. Let G = (V, E) denotes an undirected graph, V = {v i } n i=1 is the node set and E ⊆ V × V is the edge set. A ∈ R n×n is the adjacency matrix. Let X = {x i } n i=1 ∈ R n×d0 be the initial node feature matrix, where d 0 is the initial dimension, and Y = {y i } n i=1 ∈ R n×C denotes the ground-truth node label matrix, where C denotes the number of classes and y i is the one-hot encoding of node v i 's label y i . Let H (L) be the output of the last layer of an L-layer GCN, the prediction probability matrix Ŷ = softmax H (L) is the final output of node classification.Few-Shot Node Classification. In the FSNC task, the entire set of node classes C can be divided into two disjoint subsets: base classes set C base and novel classes set C novel , such that C = C base ∪ C novel and C base ∩ C novel = ∅. There are sufficient labeled nodes in C base , while there are only a limited number of labeled nodes in C novel . FSNC task aims to learn a model using the sufficient labeled nodes from C base , enabling it to accurately predict unlabeled nodes (i.e., query nodes Q) in C novel , with limited labeled instances (i.e., support nodes S) from C novel .Sharpness-Aware Minimization (SAM). SAM [11] EQUATIONwhere ρ is the radius of the ℓ p ball, and p ≥ 0 (usually p = 2). In this way, the model can converge to flat minima in loss landscape (w * ), making the model more generalizable [11] . For efficiency, SAM applies first-order Taylor expansion and classical dual norm problem to obtain the approximation:EQUATIONFinally, SAM computes the gradient w.r.t. perturbed model w + ε for update w in Eq. ( 1):EQUATIONAdditional Related Works. The effectiveness of SAMs and its variants have been widely verified in computer vision area [1, 8, 9, 11, 20, 22, 42] . Specifically, LookSAM [22] speeds up the SAM by periodically conducting exact perturbation, and Sharp-MAML [1] firstly focusing on meta-learning tasks. However, there is limited work on developing SAM for graphs. WT-AWP [38] is the first SAM-like work that applied to GNN and gives a theoretical analysis of generalization bound on graphs. Compared to these works, our proposed FGSAM is crafted for graphs by its unique property, enabling the first SAM-like algorithm that can be faster than the base optimizer. Our work also shares some similarities with existing works [16, 39] that explore the connection between GNNs and MLPs. However, they attributed the claim that introducing MP to MLP can improve performance during evaluation to the powerful generalization ability of MP. In contrast, we prove that for the linear case with synthetic graphs, whether there is MP or not, both will converge to the same optimal solution, taking a solid step toward understanding the underlying reasons. 
methodology: 
 In this section, we propose Fast Graph Sharpness-Aware Minimization (FGSAM), an efficient version of SAM for GNNs, aiming to reduce the training time when using SAM in FSNC tasks while improving model's generalization.SAMs are a series of new general training scheme used to improve the model's generalization, thus it is intuitive to use SAM in FSNC tasks. However, there is no work studying how to apply SAM to FSNC tasks. So our first question is: Q1: Can SAM benefit few-shot node classification tasks? A key property of FSNC is that the GNNs need to be generalized to unseen classes (i.e., novel classes), and the GNNs often converge to a relatively low loss on the training set, but the final performance depends on the GNNs' generalization ability. To demonstrate this intuitively, we plot the GNN's loss landscape of novel classes under the FSNC setting and of the test set under the NC setting (Fig. 2a ), following previous work [21] . The loss landscape of GNN under the FSNC setting is sharp and not smooth, with many local minima, in contrast to the flat and smooth loss landscape of GNN under the NC setting. This to some extent indicates that the FSNC setting poses a greater challenge to GNNs, which is consistent with our prior knowledge. Hence, applying SAM-like techniques can intuitively improve the generalization of GNN and enhance its performance. Inspired by previous work [16] , it is appealing to remove MP during training, but reintroduce it in inference (PeerMLP). Although reintroducing MP after training can improve the performance, it still cannot surpass GNNs' (Fig. 2b ). This may be because of the lack of graph topology information in training. Hence, we propose minimizing training loss on PeerMLPs but minimizing the sharpness according to GNNs, implicitly incorporating the graph topology information in training. This allows the model to quickly converge to the vicinity of local minima and further converge to flat GNN local minima through a GNN's sharpness-aware approach. By doing so, we not only introduce SAM to enhance the model's generalization ability and the information w.r.t graph topology but also leverage the intriguing connection between MLPs and GNNs to improve training speed.We elaborate our proposed method Fast Graph Sharpness-Aware Minimization (FGSAM). For the ease of reference, Fig. 3a visualizes the framework of FGSAM, so does to its enhanced version FGSAM+. There are two forward-backward steps in the FGSAM-update.Step 1: Graph sharpness-aware perturbation. The first forward-backward step is served for computing the maximum perturbation ε (Eq. ( 2)), where we propose to perturb parameters with MP (GNN), i.e., ε = ρEQUATIONStep 2: Minimizing perturbed loss. We propose to minimize the perturbed loss by removing the MP (PeerMLP) to speed up training, i.e., w * = arg minEQUATIONIt is clear that minimizing the loss on PeerMLPs is equivalent to minimizing the loss on GNNs ignoring the topology information. As demonstrated in Sec. 3.1, intuitively the proposed approach can make model convergence near the local minima easily due to the connection between MLPs and GNNs, and perturbing parameters with MP can find the good flat minima of GNNs (see Fig. 2a ).Reintroducing Graph Topology in Minimization with Free Lunch. While reintroducing the MP in evaluation can improve performance, its absence during the minimization process may result in ). It can be seen that g v and g G change much slower than g s and g h across the training process, thus can be reused in the intermediate steps.sub-optimal results. Incorporating MP directly into the minimization is computationally expensive, leading us to employ MLP to minimize the perturbed loss. Fortuitously, the gradient w.r.t. MP is computed during the perturbation step, offering an opportunity for computational savings. We propose to capitalize on the already available gradient information from the first step by reusing it in the optimization procedure, as formalized in the following optimization target:EQUATIONThis formulation implies that the computational cost of involving MP in the optimization is mitigated since the forward and backward passes are precomputed in the initial step. Thus, we effectively integrate graph topology into the minimization process almost without incurring additional computational expense, akin to receiving a free lunch. See detailed FGSAM in Algorithm 1.Adaptation to MAML Models. Model-Agnostic Meta-Learning (MAML) [10] is widely used in FSNC tasks [7, 37] , involving two separate update steps in one MAML-update: i) pre-training for learning task-relevant knowledge, and ii) meta-update for task-irrelevant update. This is different from standard gradient descent. Hence for integrating the FGSAM into the MAML models, we propose treating the MAML-update process as a single entity, and applying the FGSAM-update only once simplifies the implementation. This contrasts with the Sharp-MAML [1] , where the SAM-update is applied separately in the two stages.Although the training time of FGSAM can be largely faster than naïve SAM by ignoring the MP in minimizing perturbed loss, it still requires a full forward-backward step of GNN, which makes our approach need an extra computation cost for a forward-backward step of PeerMLP, compared to the base optimizer.Fortunately, the forward-backward step of GNN is mainly for perturbing parameters in FGSAM, thus we can further reduce the training time while maintaining performance, by employing FGSAM-update at every k step (i.e., perturb parameters at every k step) and reusing the preserved gradients from parameters perturbation into the intermediate steps [22] . Eq. ( 3) can be rewritten as:EQUATIONIn this way, SAM-gradient g s is composed by the vanilla gradient ∇ w L Dtr (w) and the gradient of the ℓ 2 -norm of vanilla gradient ∇ w ∥∇ w L Dtr (w)∥.This suggests that SAM-gradient g s = ∇ w L Dtr (w)| w+ε can be divided into two orthogonal parts [22] : g h (in the direction of vanilla gradient g = ∇ w L Dtr (w) ) is used to minimize the loss value, and flatness-gradient g v is used to adjust the updates towards a flat region. So g h and g v can be easily obtained if g s and g are given:EQUATION)where θ is the angle between g s and g h . As illustrated in [22] , g v changes much slower than g s and g h , thus we can compute and preserve g v at every k steps, and reuse it to approximate g s in intermediate steps.However, in our case, there exists a clear gap between the model used for perturbing (GNN) and for minimizing (PeerMLP). This is different from the approach in [22] , which uses the same model for both. Thus we use an extra PeerMLP forward-backward step to get another g mlp for computing g v to reduce the gap:EQUATIONNote that the ε is obtained by perturbing parameters with MP Eq. ( 4), g s and g mlp are obtained without MP, thus there still exists a gap.Moreover, since we reintroduce graph topology (Eq. ( 6)) in minimization, we propose to further use the extra PeerMLP step to reuse graph topology for better performance. Specifically, we conduct the gradient w.r.t. topology information by projection as follows:EQUATION)where θ ′ is the angle between g gnn and g mlp . This can be reused in a similar way as g v when approximating FGSAM-update in the intermediate steps. We further conduct experiments to verify whether the g G and g v will change slowly so that they can be reused for speed up in our approach.We plot the change of g s , g h , g v and g G (Fig. 3b ) and the results show that the projected gradient both g v and g G on parameters perturbed with MP shows a much more stable pattern and slower changes than g s and g h , indicating the feasibility of updating g v and g G every k steps and reusing it for the intermediate steps. We present the detailed FGSAM+ in Algorithm 1 in Appendix B.Since we need an extra PeerMLP forward-backward step at every k step, the overall computation cost of our approach, FGSAM+, will be 1 k × the computation cost of GNNs plus (1+ 1 k )× the computation cost of MLPs on average. 
analysis of toy case: 
 In this section, we employ the Contextual Stochastic Block Model (CSBM) to analyze why minimizing perturbed training loss without MP can work to some extent, which is the underlying mechanism of FGSAM. The CSBM has been widely used to analyze of the properties of GNN [25, 26] . Specifically, we focus on a CSBM model that contains K distinct classes c 1 , c 2 , . . . , c K . The nodes within the resulting graphs are grouped into n non-overlapping sets C 1 , C 2 , . . . , C K , each set representing one of the K classes. The generation of edges is governed by a probability p within the same class and a probability q between different classes. For any given node i, we sample its initial features x i ∈ R l from a Gaussian distribution denoted by x i ∼ N (µ, I), where the mean µ = µ k ∈ R l corresponds to node i belonging to set C K , and k is an element of {1, 2, . . . , K}. Furthermore, the condition ||µ i -µ j || 2 = D holds true for all i, j belonging to {1, 2, . . . , K}, with D being a positive constant. Graphs that arise from this specified CSBM model are referred to as K-classes CSBM. After applying a MP operation, the resultant features for node i are denoted by h i . The neighborhood label distribution D i of node i is a K-dimensions vector, whereD i [j] = I(i ∈ C j )p + (1 -I(i ∈ C j ))q.Based on the neighborhood label distribution, consider the MP operationas h i = 1 deg(i) j∈N (i) x i , we have: h i ∼ N (p-q)µ k +qK μ p+(K-1)q , I deg(i) , where i ∈ C k and μ = K j=1 µj K. Based on the distribution of h i and x i , we can obtain following theorem: Theorem 4.1 (The effectiveness of removing MP in minimization). Consider a K-classes CSBM, the optimal linear classifiers for both original features x i and filtered features h i are the same.Detailed proof is in Appendix C. The theorem tells us that under the linear case, whether the MP layer is used or not, the optimal decision bound is the same. Hence, this encourages us to learn the weight of transformation layers without MP to speed up training. However, the real graph is more complex and we do not use a linear classifier, thus we propose to perform the graph sharpness-aware perturbation which implicitly involves the information of neighbors. 
experiments: 
 We verify the effectiveness of our proposed FGSAM and FGSAM+ in this section. We first conduct experiments to demonstrate that our proposed algorithms achieve better performance compared to SAM which requires twice the training time. Then we show that our proposed algorithms can achieve faster training speed compared to base optimizers (e.g., Adam). Next, we also conduct extra studies and an extra task to show the robustness and potential applications of our proposed algorithms. Baseline. We evaluate our proposed FGSAM and FGSAM+ on SOTA models. The existing models can be divided into two main categories: MAML and non-MAML methods. Two representative models are selected from each category, respectively, as baselines for evaluation (Meta-GCN [41] and AMM-GNN [36] for MAML models, and GPN [7] and TENT [37] for non-MAML models).Datasets. We conduct evaluations on three widely used real-world benchmark node classification datasets: CoraFull [5] , DBLP and ogbn-arXiv [17] , and we use the train/val/test split as in [33] and [23] . The comprehensive statistics of datasets are shown in Tab. 5 in Appendix D.1.Implementation Details. We implement our model by PyTorch [28] and conduct experiments on an RTX-3090Ti. We use Optuna [2] to search the hyper-parameters for each setting. See Appendix D.2 for detailed FSNC learning protocol.The results of different models across datasets are summarized in Tab. 2. All the models share a 2layers architecture with 16 hidden channels. It can be seen that our proposed algorithms FGSAM and FGSAM+ provide better performance than Adam in most cases, and provide comparable performance with SAM. These results support our claim that FGSAM and FGSAM+ can find local minima with better generalization properties. Note that message-passing is only used in perturbing parameters, not involved in parameters update (i.e., MLPs). The results further indicate that implicitly involving graph topology in training can make PeerMLPs outperform GNNs. See Appendix D.3 for details.To demonstrate the training speed advantage of our proposed algorithm, we summarize the training time for different models using various optimization methods across three datasets (Tab. 2). The results indicate that our proposed algorithm FGSAM demonstrates only a slight increase in training cost compared to Adam in most cases. Furthermore, our enhanced version FGSAM+ outperforms Adam in terms of speed in the majority of scenarios. It is worth mentioning that our proposed algorithms achieve superior or comparable performance when compared to both Adam and SAM. See Appendix D.4 for detailed results.Limitation. For models composed of many non-GNN components (e.g., TENT), the training time on FGSAM+ may be still longer than that on Adam, since it is hardly further reduced. , LookSAM [22] , AE-SAM [18] , our proposed FGSAM and FGSAM+ (Tab. 3). We observe an anomalous phenomenon where ESAM, as an efficient variant of SAM, actually trains slower than SAM. This is because ESAM sorts the sample losses and selects a suitable subset at each iteration, an operation that is negligible for image tasks; however, for graph tasks, since GNNs are relatively smaller, the proportion of time consumed by the sorting step is significant, leading to an increase in training time. As shown in Tab. 3, our proposed method greatly reduces the training time, based on the relationship between GNN and MLP, while maintaining and even achieving superior performance, compared to other optimizers, indicating ours' high efficiency and effectiveness.The Impact of Perturbing Parameters with Message-Passing. A key point of our work is that we perform parameter perturbation using GNNs, while PeerMLPs (i.e., without message-passing) are used to minimize the perturbed loss. This is significantly distinct from previous SAM methods which shared the same model for both parameter perturbation and loss minimization. So a natural question arises: to what extent does our approach benefit from performing parameter perturbation using GNNs? We thus compare our approach to PeerMLPs training with Adam and vanilla SAM. Note that message-passing would be reintroduced during validation and test. From Tab. 3, although the training time of PeerMLPs is shorter than that of GNNs, GNNs outperform their PeerMLPs in most cases. Despite that using PeerMLPs can accelerate the training of GNNs, the topology information is still very important for learning node representations. Thus our proposed FGSAM+ is a better solution, achieving a better trade-off between efficiency and performance.We further verify the consistent effectiveness of our method compared to Adam across different settings regarding model implementation and graph property. Due to the computational resource restriction, all experiments here were conducted using GPN on the CoraFull with the 5-way 3-shot setting. We provide additional experiments (e.g., the effect of update interval k) in the Appendix E.The Impact of Network Structure. Here we investigate the effect of hidden dimension and the number of layers on the performance (on the left of Fig. 4 ). GPN with Adam requires a higher hidden dimension (128) to achieve relatively high accuracy, whereas GPN with FGSAM+ can attain SOTA even with a small hidden dimension (16) . With respect to the number of layers, GPN with FGSAM+ consistently performs better within the range of 1∼8 compared to GPN with Adam, demonstrating the effectiveness of our proposed method (middle left of Fig. 4 ).The Impact of Noisy Features and Edges. Here we investigate the effect of randomly adding Gaussian noise to features and randomly adding edges during testing (on the middle right and the right of Fig. 4 ). Specifically, for noisy features, we randomly add Gaussian noise with varying standard deviations to the node features. Meanwhile, for noisy edges, we uniformly and randomly introduce additional edges into the original structure. The results show that GPN with FGSAM+ method can still achieve relatively high performance, compared to GPN with Adam. These results effectively verify the robustness of our proposed method.Our proposed FGSAM+ also has the potential to be extended to other domains. To demonstrate this, we evaluate the performance of the FGSAM+ on the standard node classification task on both homophilic and heterophilic graphs. For homophilic graphs, we utilize three well-established citation networks: Cora, Citeseer, and Pubmed [12, 31] . For heterophilic graphs, we include page-page networks from Wikipedia, specifically the Chameleon and Squirrel datasets [30] , actor-network, namely Actor [29] , and web pages networks, namely Cornell, Texas and Wisconsin [29] . See Appendix E.1 for statistics of these datasets. We use data splits (48%/32%/20%) provided by [29] , and set k = 2 for FGSAM+. We select three representative baselines, namely the classical GCN [19] ,GAT [34] with learnable MP operation, and GraphSAGE [15] with complex MP operation, to demonstrate the effectiveness of FGSAM and FGSAM+.As shown in Tab. 4, both FGSAM and FGSAM+ generally outperform Adam and SAM across base models, indicating the potential wide application of our method. We observed that the proposed method achieves greater improvement on heterophilic graphs compared to homophilic graphs, and heterophilic graphs are generally considered more challenging. This indicates that our method can effectively enhance the generalization capability of GNNs. We also provide additional experiments of integrating FGSAM+ with prompt-based FSNC [32] in the Appendix E.3. We observe that both FGSAM and FGSAM+ generally outperform the standard SAM across tasks (FSNC and standard node classification). This is an interesting finding, as our FGSAM and FGSAM+ algorithm remove message-passing during the minimization of the perturbed loss, which is expected to hurt performance. We attribute these counterintuitive results to the mitigation of the imbalance adversarial game. The training process of SAM-like algorithms entails an adversarial game similar to that in Generative Adversarial Nets (GANs) [13] .Prior studies [3, 4, 27] have demonstrated that imbalanced adversarial games in GANs can give rise to worse results. Both FGSAM and FGSAM+ employ distinct models for perturbation and minimization, which can help alleviate the extent of imbalance. These factors may explain the observed performance discrepancies among the compared algorithms. To verify the explanation, we conduct experiments varying the hyper-parameter ρ. Specifically, we graphically illustrate the comparative training loss of SAM and FGSAM+ over a range of ρ values in Fig. 5 , which reveals that while SAM struggles to converge with higher ρ values, FGSAM+ consistently achieves convergence. Moreover, it is established that a higher ρ value is conducive to a tighter generalization bound, suggesting that a larger ρ could potentially enhance performance. Consequently, FGSAM+ is capable of mitigating the imbalanced games issue and tolerating a larger ρ, which contributes to its enhanced performance. 
conclusion: 
 In this work, we study the application of Sharpness-Aware Minimization (SAM) in FSNC to improve model's generalization, since the key for FSNC is to generalize the model to unseen samples. In order to alleviate the heavy computation cost of SAM, we utilize the connection between MLPs and GNNs and use MLPs to accelerate the training of GNNs. However, the low generalization and lack of using graph topology of MLPs also limit its performance. Hence we propose to apply GNNs to perturb parameters for generalization and use MLPs to minimize the perturbed training loss for conducting the proposed FGSAM. Moreover, we reuse the GNN gradient in perturbation in minimization for better including topology information. We further reduce the training time by conducting exact FGSAM update at every k steps and approximate FGSAM's gradient with reusing information in the intermediate steps. Finally, the extensive experiments demonstrate the effectiveness and efficiency of our proposed methods.Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?Answer: [Yes]Justification: Detailed are provided in the paper (main body and appendix).Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [Yes] Justification: Due to the page limit, the standard deviation is provided in the appendix (Tab. 7).Guidelines:• The answer NA means that the paper does not include experiments.• The authors should answer "Yes" if the results are accompanied by error bars, confidence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper. • The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions). • The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.) • The assumptions made should be given (e.g., Normally distributed errors).• It should be clear whether the error bar is the standard deviation or the standard error of the mean. • It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have a 96% CI, if the hypothesis of Normality of errors is not verified. • For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates). • If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text. 
experiments compute resources: 
 Question: For each experiment, does the paper provide sufficient information on the computer resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?Answer: [Yes]Justification: The information is provided in Sec. 5.1 and Sec. 5.3.Guidelines:• The answer NA means that the paper does not include experiments.• The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage. • The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute. • The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper). 
code of ethics: 
 Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https://neurips.cc/public/EthicsGuidelines? 
broader impacts: 
 Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?Answer: [Yes]Justification: We have discussed the potential broader impacts in Appendix A.Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? 
 
 Appendix: This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here. The linear classifier for K-classification problems can be formulated as K(K-1) 2 binary classification problems.Hence we study the classification between class C o and C p without loss of generality.The distribution of original features from different classes follows:EQUATION)The distribution of filtered features from different classes follows:EQUATIONFor simplicity, we denote μ0 = (p-q)µo+qK μ p+(K-1)q and μp = (p-q)µp+qK μ p+(K-1)q . Following [26] , the optimal classifier of original features constructs a decision bound P = {x|w T xw T b}, where w = . Similarly, the optimal classifier of filtered features constructs a decision boundP ′ = {h|w ′T h -w ′T b}, where w ′ = μo-μp 2 /|| μo-μp 2 ||, b ′ = μo+ μp 2 .And we have μoμp = p-q p+(K-1)q (µ o -µ p ), hence we have w = w ′ . Then we verify whetherEQUATIONwhere λ = p-q p+(K-1)q .Then we show(µ o -µ p ) T μ - µo+µp 2 = 0.From ||µ i -µ j || 2 = D, we have:EQUATIONwhich gives:EQUATIONHence we have:EQUATIONCombining Eq. ( 13) and Eq. ( 16), we have:EQUATIONwhich means P = P ′ . This completes the proof. • CoraFull is an extension of the prevalent dataset 'Cora' [40] , a citation network dataset. On this graph, nodes represent papers and edges represent citation links. The nodes are labeled on the paper topics. Node attributes are obtained using bag-of-words for the title and abstract of the paper.• DBLP is also a citation network, where nodes represent papers and edges represent the citation between papers. Specifically, the node attributes are generated by the abstract and the node labels are based on the paper venues.• ogbn-arXiv is a citation network among all Computer Science arXiv papers based on MAG [35] . Node represent papers and edges are citations links. The node attributes are obtained using skip-gram on abstract of papers. The nodes are labeled by the subject area.Specifically, we implement our model by PyTorch [28] and conduct experiments on 24GB Nvidia RTX3090Ti, according to the training protocol Algorithm 2. Repeat number R = 5, patience P = 10, SAM update interval k = 2, validation interval I = 10, validation number V = 20, test number W = 100. For MAML models max epochs T = 500, and for non-MAML model max epochs T = 1000. We evaluate our method under various settings, i.e., N = {5, 10}, K = {3, 5}, but we set N = {2, 5} for Coauthor-CS dataset. We use Optuna [2] for hyper-parameters searching for all models with various optimizers, the search space is shown in Tab. 6. Here we study the effect of update interval k in FGSAM+. It can be observed from Tab. 11 that as k increases, the performance decreases, but meanwhile training time also decreases. This indicates that the possibility of choosing k to achieve a better trade-off between performance and efficiency. We note that the performance drop with increasing k seems to be larger compared to LookSAM [22] in computer vision tasks. This indicates the importance of the perturbation step in FGSAM+, as it not only introduces information about flat minima, but also incorporates neighbor information in training. Therefore, we recommend setting k = 2 as the prior optimal update interval to avoid large information loss.Recently, there are many prompt-based methods [24, 32] have been developed, showing promising performance in FSNC. Hence, we investigate how our method performs in such a prompt-based FSNC task. Note that under this setting, the proposed method is used in prompt tuning instead of training. As shown in Tab. 12, our method improves the baseline [32] with a remarkable margin.Justification: Data is publicly available and code is also available.Guidelines:• The answer NA means that paper does not include experiments requiring code. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted.Justification: We confirm that we have adhered to the NeurIPS Code of Ethics.Guidelines:• The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.• If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction).Justification: There are no high-risk issues in our model trained for FSNC tasks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?Answer: [Yes]Justification: We have cited all the related papers, the papers of models and datasets we use.Guidelines:• The answer NA means that the paper does not use existing assets.• The authors should cite the original paper that produced the code package or dataset.• The authors should state which version of the asset is used and, if possible, include a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided. • If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a dataset. • For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. 


Decision: This paper is concerned with few shot node classification setting of graph neural networks. The difficulty of such task lies in quick and generalizable adaptation of the model using only few labels. To enhance such generalization, authors propose to incorporate sharpness aware minimization (finding flat local optima in the loss surface) during GNN adaptation. Direct application of SAM is computationally expensive (2x), and authors propose new modifications to SAM. Namely, substitution GNNs with multilayer perceptrons (for loss minimization)  and a setting when perturbations are approximated for few iterations and subsequently recalculated exactly. Provided experiments demonstrate that the method is not only significantly faster than the original SAM but also outperforms it in terms of accuracy.
This paper is clearly and well written and the proposed method was extensively evaluated via carefully crafted experiments and ablations, demonstrating superior performance. Reviewers found that this method has a clear practical application and while not very "novel", it is witty at applying tried and tested technique in a new setting (GNN) in a way that significantly reduces the computational burden.

Reviews: review: paper_summary: paper_summary: The paper proposes a method for few-shot learning on graphs leveraging sharpness-aware minimization (SAM) from the vision community. The paper explains SAM as a technique for gradient perturbation during training to push the parameters to "flatter" regions of the loss space in hopes of achieving better generalization in the few shot setting. However, SAM is inherintely slower, requiring two backward/forward passes during training; one to compute the loss gradient and a second to determine the perturbation direction. The authors propose multiple ideas to overcome the added computation and to leverage graph topology. The authors strategically substitute Graph Neural Networks (GNNs) with Multilayer Perceptions (MLPs) to avoid the burden of message passing in some parts of their algorithm while preserving graph topologies in others. The authors propose a second scheme that leverages iterations of an approximate perturbation scheme with periodic exact evaluations of SAM. The authors present ablation studies on multiple SOTA models and 9 datasets and show improvements in training times and accuracy.
strength_weakness: strength_weakness: 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.

(1) In the abstract (line 14) Moreover, our method ingeniously reutilizes... is a bit grandiose; I would prefer a more scientific tone and delete "Moreover" and "ingeniously"; "Our method reutilizies...

(2) Remove "for the first time" in 20. It is clear that the ideas are novel.

(3) Line 50 is the first time Message Passing is abbreviated as MP. I would follow the convention used in the paper for the introduction of other abbreviations where the first letter of the abbreviated character is in bold and capitalized.

(4) Line 93 "as follows" is not followed by an equation but another sentence. Maybe the equation should be presented after the "as follows" text and the next sentence come after the equation?
questions: questions: (1) 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 significanly 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.

(2) 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?
limitations: limitations: No limitations.
paper_summary: paper_summary: This paper focuses on efficient graph neural network (GNN) training in few-shot node classification (FSNC) problem by extending sharpness-aware minimization (SAM) for reducing the computational cost and improving the generalization of GNNs on unseen classes. The training phase is accelerated by perturbing the parameters of GNN and then minimizing the perturbation loss of GNN without the message passing mechanism (MLP). Experiments have been conducted to verify the effectiveness and efficiency of the proposed method.
strength_weakness: strength_weakness: 1. 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.

[1] Sharp-maml: Sharpness-aware model-agnostic meta learning. ICML, 2022

[2] Towards efficient and scalable sharpness-aware minimization. CVPR, 2022

2. The experiments only compare with small-sample node classification models and variants of SAM from 2022, lacking comparisons with the latest baseline methods of FSNC.
questions: questions: 1. Since this work focuses on solving FSNC problems, the authors should provide a comparison with the state-of-the-art FSNC methods, such as COSMIC [3] and COLA [4], in theoretical analysis and experiments.

[3] Contrastive meta-learning for few-shot node classification. SIGKDD, 2023

[4] Graph contrastive learning meets graph meta learning: A unified method for few-shot node tasks. WWW, 2024

2. Why adding 25% noisy edges yields better results than adding only 15%? in Figure 4? The authors should discuss or explain this issue in details.
limitations: limitations: The authors describe some limitations of the proposed method in time consumption section.
paper_summary: paper_summary: The paper introduces an innovative approach to improve the generalization capabilities of Graph Neural Networks (GNNs) in few-shot node classification tasks. The authors propose a novel algorithm, Fast Graph Sharpness-Aware Minimization (FGSAM), which incorporates sharpness-aware minimization (SAM) techniques into GNN training but reduces the typical computational overhead by integrating multilayer perceptrons (MLPs) for efficiency. This method not only demonstrates superior performance on few-shot learning tasks compared to traditional techniques but also offers significant computational advantages, particularly in reducing training times.
strength_weakness: strength_weakness: Some experiments are missing and the proof need to be double checked carefully.
questions: questions: 1. What is the standard deviations for the results in table 4? Are the improvements significant?

2. Is there any theoretical justification for PeerMLP?

3. What is g in equation (8)?

4. The proof of theorem 4.1 is confusing. Do you assume all nodes have the same degree deg(i)?
limitations: limitations: the authors adequately addressed the limitations

Comments: title: Addressed concerns
comment: We thank you for acknowledging our work. Thanks again for your time and effort in reviewing our work.
We thank you for acknowledging our work and for raising the score. Thanks again for your time and effort in reviewing our work.
Thanks for the response. The authors addressed  some of my concerns and I will increase  my score to 5
Thanks for your feedback, which has addressed my concerns on the comparison methods and the results of adding noisy edges. Thus, I will maintain my score.
We sincerely thank you for acknowledging our work. Thanks again for your time and effort in reviewing our work.
Thank you for addressing the concerns. Best of luck with the conference.
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