Test-Time Training on Graphs with Large Language Models (LLMs)

Venue: acmmm_org_ACMMM_2024_Conference
Published: 2024-03-20 03:25:04

Abstract: Graph Neural Networks have demonstrated great success in various fields of multimedia. However, the distribution shift between the training and test data challenges the effectiveness of GNNs. To mitigate this challenge, Test-Time Training (TTT) has been proposed as a promising approach. Traditional TTT methods require a demanding unsupervised training strategy to capture the information from test  to benefit the main task. Inspired by the great annotation ability of Large Language Models (LLMs) on Text-Attributed Graphs (TAGs), we propose to enhance the test-time training on graphs with LLMs as annotators. In this paper, we design a novel Test-Time Training pipeline, LLMTTT, which conducts the test-time adaptation under the annotations by LLMs on a carefully-selected node set. Specifically, LLMTTT introduces a hybrid active node selection strategy that considers not only node diversity and representativeness, but also prediction signals from the pre-trained model. Given annotations from LLMs, a two-stage training strategy is designed to tailor the test-time model with the limited and noisy labels. 
A theoretical analysis ensures the validity of our method and extensive experiments demonstrate that the proposed LLMTTT can achieve a significant performance improvement compared to existing Out-of-Distribution (OOD) generalization methods.

Main paper: 
 introduction: 
 Graph is a kind of prevalent multi-modal data, consisting of modalities of both the topological structure and node features [30, 38] . Text-Attributed Graphs (TAGs) are graphs of which node attributes are described from the text modality, such as paper citation graphs containing paper descriptions and social network data including user descriptions. As a successful extension of Deep Neural Networks (DNNs) to graph data, Graph Neural Networks (GNNs) have demonstrated great power in graph representation learning, and have achieved revolutionary progress in various graph-related applications, such as social network analysis [16] , recommendation [39, 64] and drug discovery [8, 15] . Despite remarkable achievements, GNNs have shown vulnerability in Out-Of-Distribution (OOD) generalization, as it is observed that GNNs can confront significant performance decline when there exists distribution shift between the training phase and the test phase [19, 33] .Increasing efforts [56, 58] have been made to address the Out-Of-Distribution (OOD) challenge on graphs. A majority of these methods aim at increasing the models' capability and robustness via data augmentation techniques designed based on heuristics and extensive empirical studies [28, 55, 61] . Meanwhile, some researchers have investigated to improve the model's generalization capability via adversarial training strategies [58] and the principle of invariance [56] . Nevertheless, these approaches [56, 58] require interventions during the training phase and can hardly make the continuous adaptability to the real-time data within the constraints of privacy, resources, and efficiency. This gap has prompted the development of Test-Time Training (TTT) [31, 44] , which aims to dynamically adapt to continuously presented test data based on an unsupervised learning task during the test phase.Test-Time Training (TTT) have demonstrated great potential in alleviating OOD generalization problem. Fully Test-Time Training (FTTT) [25, 49] is the extension of TTT. This kind of post-hoc method is more suitable for real-world applications due to its plugand-play simplicity, which does not interfere with the expensive training process required for pre-trained backbones. Traditional FTTT aims at adapting the pre-trained model to accommodate test data from different domains within an unsupervised setting. However, the design of the unsupervised training phase entails stringent criteria: it must ensure that the unsupervised task complements the main task without causing overfitting to the model and neglecting the main task. Additionally, unsupervised tasks must implicitly capture the distribution of the test data. Devising such an unsupervised training strategy poses a significant challenge. A natural solution is to utilize the same training strategy as the main task in the test phase, i.e., supervised learning. Meanwhile, a recent study [12] has shown that incorporating a limited number of labeled test instances can enhance the performance across test domains with a theoretical guarantee. This motivates us to introduce a small number of labels at test time to further advance the model performance on OOD graphs.In the FTTT scenario, with continuous arrival of data during testing, human annotation cannot handle this situation flexibly and efficiently. Fortunately, Large Language Models (LLMs) have achieved impressive progresses in various applications [6, 14, 17] . including zero-shot proficiency in annotation on text-attributed graphs [7] . With the assistance of LLMs, only a few crucial nodes are chosen and assigned pseudo labels. Then, FTTT is executed using the same training approach as the main task. This method avoids the need for intricate unsupervised task designing. Therefore, in this work we propose a novel method to leverage the annotation capability of LLMs to advance test-time training, so as to alleviate the OOD problem on graphs. However, to achieve this goal, we face tremendous challenges: (1) How to select nodes for annotation with LLMs given a limited budget? The studied problem in this paper is different from that in [7] . For node selection, in addition to the importance of the characteristics of LLMs and the test data, the predictions of the pre-trained model on test nodes can also provide crucial signals. (2) How to effectively adapt the pre-trained model under the noisy and limited labels? The labels generated by LLMs are noisy [7] . Therefore, it is essential to design a training strategy which is able to simultaneously utilize a small number of noisy labeled nodes and the remaining unlabeled nodes during test time.To tackle these challenges, we introduce a Fully Test-Time Training with LLMs pipeline for node classification on graphs, LLMTTT . During the selection of node candidates, different from traditional graph active node selection methods, LLMTTT introduces a hybrid active node selection strategy, which considers node diversity, node representativeness, and the prediction capacity of the pre-trained GNN simultaneously. Meanwhile, to leverage both the noisy labeled nodes and unlabeled nodes, LLMTTT designs a two-stage test-time training strategy. Our main contributions can be summarized as follows:• We introduce a new pipeline, LLMTTT , from the graph OOD problem. In LLMTTT , we use LLMs as annotators to obtain pseudo labels. These labels are then used to fine-tune the pre-trained GNN model during test time.  
preliminary: 
 This section provides definitions and explanations of key notations and concepts in this paper. First, primary notations and the pipeline of traditional fully test-time training are introduced. Next, we illustrate the proposed LLMTTT pipeline for a more comprehensive understanding of our framework.In this study, we focus on the node classification task, where the goal is to predict the labels of nodes within a graph and we denote the loss function for this task as 𝐿 𝑚 (•). Given a training node set 𝐷 𝑠 = (𝑋 𝑠 , 𝑌 𝑠 ) and a test node set 𝑈 𝑡𝑒 = (𝑋 𝑡 ), where 𝑋 denotes the node samples and 𝑌 indicates the corresponding labels. Traditional FTTT pipeline. Assuming that the model for the node classification task has 𝐾 layers, which can be denoted as 𝜽 = {𝜽 1 , ..., 𝜽 𝐾 }. Given the test data 𝑈 𝑡𝑒 , the parameters of the learned model will be partially (typically the first 𝑘 layers of the model are fixed) updated by the SSL task during the fully testtime training phase. We can denote the updated part of model as (𝜽 ′ 𝑘+1 , ..., 𝜽 ′ 𝐾 ). In the inference phase, the model (𝜽 1 , ..., 𝜽 𝑘 , ..., 𝜽 ′ 𝐾 ) is used to make predictions for the test data. The proposed LLMTTT pipeline. Traditional FTTT pipeline aims at adapting a pre-trained model for streaming test-time data under unsupervised settings. However, it is not trivial to design such an appropriate and effective unsupervised task, which is supposed to be positively-correlated to the main training task [44] . In order to solve this problem, we introduce a novel pipeline named LLMTTT , which substitutes a semi-supervised task with the assistance of LLMs, for the unsupervised task during the test-time training phase. The proposed pipeline can be formally defined as follows:Given a model 𝑓 (𝑥; 𝜽 ), initialized with parameters 𝜽 𝑠 obtained by pre-training on train data. We select most valuable samples under a limited budget from test nodes by a carefully designed hybrid node selection method, denoted as 𝑋 𝑡𝑟 = 𝐴𝑐𝑡𝐴𝑙𝑔(𝑋 𝑡 ). Then the selected samples are given pseudo labels by LLMs, denoted as 𝐷 𝑡𝑟 = (𝑋 𝑡𝑟 , Ŷ𝑡𝑟 ) where Ŷ𝑡𝑟 = 𝐿𝐿𝑀 𝑎𝑛𝑛𝑜 (𝑋 𝑡𝑟 ). After obtaining the labeled test nodes, we employ a two-stage training strategy that incorporates both the labeled test nodes 𝐷 𝑡𝑟 and unlabeled test nodes 𝐷 𝑡𝑟𝑒 . The LLMTTT task aims to optimize the model as:EQUATIONwhereEQUATION𝐿 𝐶 is the cross entropy loss, 𝐿 𝑈 is an unsupervised learning loss, and 𝐵 is the budget. 𝐷 𝑡𝑒 are the unlabeled nodes in the test data 𝑈 𝑡𝑒 that have not been labeled. ŷ is the pseudo labels given by LLMs. 
method: 
 In this section, we will introduces the novel LLM-based fully testtime training framework ( LLMTTT ) for the graph OOD problem. We first delineate the overall framework and then detail the specific components of LLMTTT .The LLMTTT pipeline proposed in this paper is illustrated in the Fig. 1 that consists of three parts: pre-training phase, fully test-time training phase, and inference phase as follows: Pre-training phase. The objective of this phase is to acquire a pre-trained classification model with optimized parameters capable of accurately predicting labels for the train data 𝐷 𝑠 . It is worth noting that only the model parameters 𝜃 and the test data 𝑈 𝑡𝑒 are required for the subsequent test-time model adaptation. Therefore, LLMTTT is a model-agnostic framework. Fully test-time training phase. The objective of our proposed approach is to utilize the annotation capabilities of LLMs to enhance test-time training to handle the OOD problem on graphs. We encounter several challenges in achieving this goal: (1) How to select the most valuable nodes for annotation using LLMs within a constrained budget? To address this issue, LLMTTT proposes a hybrid active node selection method incorporating both the knowledge from the pre-trained model and the node characteristics. Detailed illustration is provided in Section 3.2. (2) How to obtain high-quality pseudo labels based on LLMs? Given the candidate set of nodes, the Node selection is crucial in the design of LLMTTT . To better prompt the model performance under a controllable budget, it is eager to select the most valuable nodes for the test-time training. To achieve this goal, we need to consider not only the characteristics of the test data, but the predictions of the pre-trained model on the test data. Thus, LLMTTT proposes a two-step hybrid active node selection method. It consists of uncertainty-based active learning to leverage the important signals from the pre-trained model, and distribution-based active learning that is able to exploit the data characteristics. The details of these two steps are illustrated in the following subsections.To fully exploit the potential of model improvement from the test-time model adaptation, LLMTTT targets at nodes that are most difficult for the pre-trained GNN model to predict. To achieve this, uncertainty-based active learning is designed, which makes use of the prediction uncertainty indicated by prediction entropy [43] to select potential annotation nodes. Unlike other metrics of uncertainty [37, 48] , entropy takes into account all class probabilities for a given 𝑥. Specifically, for each node 𝑣 𝑖 , LLMTTT computes its prediction entropy 𝑄 (𝑣 𝑖 ) based on the prediction results from the pretrained GNN model, and then the nodes with higher prediction entropy are more likely to be selected. The prediction entropy of node 𝑣 𝑖 , 𝑄 (𝑣 𝑖 ) is calculated as follows:EQUATIONwhere 𝑐 denotes the potential labels and 𝑦 is the predicted label given by GNNs.The nodes selected through uncertainty sampling often exhibit high correlation within the same neighborhood. As a result, the distribution of the selected node set deviates from the original distribution, significantly compromising the diversity and representativeness of the node candidate set [47] . With this rationale, LLMTTT proposes to further refine node selection using distribution-based methods to emphasize the crucial data distribution characteristics. To be specific, a combiantion of PageRank [32] and FeatProp [57] is employed to capture the node distribution from both the structural and feature perspective. Given the set of selected nodes, the quality of their pseudo labels plays an important role in the performance after test-time training, based on the empirical study in Section 5.3.1. Therefore, it is imperative to make full use of LLMs and the pretrained GNN to obtain high-quality annotations after acquiring the candidate node set via the hybrid active learning. Inspired by existent exploration of LLMs on graphs [6, 7, 14] , LLMTTT proposes to prompt based on the "few-shot" strategy, which is described in Appendix B. Specifically, information of some labelled nodes from the training set serves as a part of the prompt. Moreover, the prediction results from the pretrained GNNs are also included into the prompt. In addition, to evaluate the quality of LLM's annotations, we further request the prediction confidence for the pseudo labels from LLMs.After LLMs' annotation on the selected nodes, LLMTTT moves to the next phase, test-time training phase. The proposed LLMTTT creatively suggests utilizing pseudo labels for semi-supervised training during test time instead of an unsupervised training strategy. However, given the LLMs' annotation budget, the pseudo labels are too few to effectively adapt the model, which may even lead to a biased adaptation. To tackle this challenge, we propose to further design test-time training by integrating unsupervised learning with supervised learning to better leverage the information from all test nodes. In a nutshell, during test-time training phase, LLMTTT first trains the model with filtered nodes so as to reduce the impact from the noisy labels, and then leverages the self-training that can incorporate the information from the unlabeled data.Training with filtered nodes. The pseudo labels generated by LLMs may be noisy and consequently affect the model. The pseudo labels are not entirely accurate. Therefore, we obtain the confidence of the LLMs' prediction through confidence-aware high-quality annotation in Section 3.3. To mitigate the potential impact from the noisy pseudo labels, LLMTTT propose to do a node filtering by excluding nodes based on confidence scores. However, it may cause label imbalance in the annotated node set. To avoid this issue, LLMTTT proposes to take the label diversity into consideration during the node filtering process.To quantify the change in diversity, we adopt the Change of Entropy (COE), inspired by [7] . It measures the shift in entropy of labels when a node is removed from the set. Specifically, assuming that the current set of selected nodes is denoted as 𝑉 , COE can be defined as 𝐶𝑂𝐸 (𝑣 𝑖 ) = 𝑯 ŷ𝑉 -{𝑣 𝑖 } -𝑯 ( ŷ𝑉 ) where 𝑯 (•) is the Shannon entropy function [43] , and ŷ denotes the annotations generated by LLMs. A larger COE value indicates that the removal of a node from the node set has a more pronounced impact on the diversity of the node set. To conclude, we integrate COE with the confidence score provided by LLMs to effectively balance both diversity and annotation quality. The final filtering score of each label can be expressed as 𝑆𝑐𝑜𝑟𝑒 𝑓 𝑖𝑙𝑡𝑒𝑟 (𝑣 𝑖 ) = 𝑆𝑐𝑜𝑟𝑒 𝑐𝑜𝑛𝑓 (𝑣 𝑖 ) -𝛾 × 𝐶𝑂𝐸 (𝑣 𝑖 ). The annotated nodes with relatively-high filtering score are selected for the few-shot test-time learning. Then we Then the filtered nodes, along with their corresponding pseudo labels, are utilized as supervision for model adaption. In this case, the cross-entropy loss 𝐿 𝐶 is employed in stage 1. Inspired by Softmatch [5] , to fully leverage the unlabeled data information, we further perform self-training on the fine-tuned GNN model with the unlabelled test data. Specifically, an augmented view is generated via DropEdge. Next, a weighted cross-entropy loss are computed between the original view and augmented view. Intuitively, the more confident the prediction is, the more important role will this node make in the weighted cross-entropy loss. Formally, we denote the weighted cross-entropy loss 𝐿 𝑢 as follows:EQUATIONwhere 𝑝 (𝑦|𝑥) denotes the model's prediction, 𝑥 𝑖 is an unlabelled test node in 𝐷 𝑡𝑒 , 𝑥 𝑎 𝑖 represents the augmented view and 𝑥 𝑖 is the original data. 𝑦 is the prediction given by updated model. 𝜆(𝑝) is the sample weighting function where 𝑝 is the abbreviation of 𝑝 (𝑦|𝑥). 𝑁 is the size for unlabeled data.The uniform weighting function is vital to this process. An ideal 𝜆(𝑝) should accurately represent the original distribution while maintaining both high quantity and quality. Despite its importance, 𝜆(𝑝) is rarely explicitly or adequately defined in existing methods. Inherently different from previous methods, we assume that the weight function lambda follows a dynamically truncated Gaussian distribution followed by [5] . More detailed is provided in Appx. F. 
theoretical analysis: 
 Compared to the traditional TTT pipeline, LLMTTT introduces supervision into the model adaptation process. This section theoretically demonstrates that incorporating labelled test samples provided by LMMs during the test-time training phase can significantly improve the overall performance across the test domain. This also provides a theoretical guarantee for the proposed LLMTTT .To simplify the theoretical analysis, we consider the main task as a binary classification problem. Given a domain 𝑋 with two probability distributions 𝐷 1 and 𝐷 2 , ℎ : 𝑋 → {0, 1} is a hypothesis serving as the prediction function from domain 𝑋 to a binary label space. Let H denote a hypothesis class with VC-dimension 𝑑. We employ the H △H -distance as detailed in [1] , offering a fundamental metric to quantify the distribution shift between 𝐷 1 and 𝐷 2 over 𝑋 . The discrepancy between ℎ and the true labeling function 𝑔 under distribution 𝐷 is formally expressed as 𝑒 (ℎ, 𝑔) = E 𝑥∼𝐷 [|ℎ(𝑥) -𝑔(𝑥)|], commonly known as the domain error 𝑒 (ℎ).Building upon two lemmas [12] provided in Appx. G, we establish theoretical bounds under the LLMTTT setting when minimizing the empirical weighted error using the hypothesis ℎ. Thm. 1 characterizes the error bounds in the LLMTTT setting, which can be formally expressed to quantify the generalization error. Expanding on this, Thm. 2 establishes the upper bound of the error that can be effectively minimized by integrating a portion of the labeled test data compared with FTTT. Theorem 1. Considering data domains 𝑋 𝑠 , 𝑋 𝑡 , let 𝑆 𝑖 represent unlabeled samples of size 𝑚 𝑖 sampled from each of the two domains respectively. The total number of samples in 𝑋 𝑡𝑟𝑎𝑖𝑛 is 𝑁 , with a sample number ratio of 𝝀 = (𝜆 0 , 𝜆 1 ) in each component. If ĥ ∈ H minimizes the empirical weighted error ê𝝎 (ℎ) using the weight vector 𝝎 = (𝜔 0 , 𝜔 1 ) on 𝑋 𝑡𝑟𝑎𝑖𝑛 , and ℎ * 𝑗 = arg min ℎ∈ H 𝑒 𝑗 (ℎ) is the optimal hypothesis within the 𝑗-th domain, then for any 𝛿 ∈ (0, 1), with a probability exceeding 1 -𝛿, the following holds:EQUATION)where 𝐶 = 2√︄ 1 𝑖=0 𝜔 2 𝑖 𝜆 𝑖 𝑑 log(2𝑁 ) -log(𝛿 ) 2𝑁and𝜀 𝑖 𝑗 = min ℎ∈ H 𝑒 𝑖 (ℎ) + 𝑒 𝑗 (ℎ)Remark. The domain error is determined by three factor: the distribution of training data (𝐶), estimated distribution shift ( dHΔH 𝑆 𝑖 , 𝑆 𝑗 ) and the performance of the joint hypothesis (𝜀 𝑖 𝑗 ). The ideal joint hypothesis error 𝜀 𝑖 𝑗 assesses the intrinsic adaptability between domains. Additional theoretical analysis can be found in Appx. G. Furthermore, Thm. 1 can be used to derive bounds for the test domain error 𝑒 𝑇 . When considering the optimal test hypothesis ℎ * 𝑇 = arg min ℎ∈ H 𝑒 𝑇 (ℎ), we obtainEQUATIONThm. 1 formally defines the domain error 𝑒 𝑗 ( ĥ), and furthermore, we can utilize the test domain error 𝑒 𝑇 ( ĥ) to verify the significance of incorporating labeled data. The following theorem presents a direct theoretical guarantee that LLMTTT decreases the error bound on the test domain compared to traditional TTT in the absence of labeled test data.Theorem 2. Let H be a hypothesis class with a VC-dimension of 𝑑. Considering the LLMTTT data domains 𝑋 𝑠 and 𝑋 𝑡 , if ĥ ∈ H minimizes the empirical weighted error ê𝝎 (ℎ) using the weight vector 𝝎 on training set 𝑋 𝑡𝑟 , let the 𝜖 (𝝎, 𝝀, 𝑁 ) to denote the upper bound of 𝑒 ( ĥ) -𝑒 (ℎ * ) . In the FTTT scenario, no samples from the test domain are selected for labeling (𝑖.𝑒., for weight and sample ratio vectors 𝝎 ′ and 𝝀 ′ , 𝜔 ′ 0 = 𝜆 ′ 0 = 1 and 𝜔 ′ 1 = 𝜆 ′ 1 = 0). Then in LLMTTT , for any 𝝀 ≠ 𝝀 ′ , there exist a weight vector 𝝎 shuch that:EQUATIONRemark. Thm. 2 suggests that even a small number of labeled examples during the testing phase can improve the overall model performance, thereby validating the effectiveness of the proposed LLMTTT in addressing distribution shifts. All proofs are provided in Appx. G. 
experiment: 
 This section presents extensive experiments to evaluate the performance of the proposed LLMTTT . Firstly, we provide a detailed explanation of the experimental setup. Then, the investigation aims to answer the following research questions: RQ1. How effective is LLMTTT on OOD generalization scenario? RQ2. How to design prompts to obtain high-quality pseudo labels? RQ3. How does the node set used for training affect LLMTTT performance? RQ4. What are the contributions of the two-stage training strategy in LLMTTT framework?5.1.1 Datasets. We adopt the following TAGs datasets for node classification: CORA [34] , PUBMED [40] , CITESEER [10] , WIKICS [35] and OGBN-ARXIV [22] . Inspired by GOOD [13] , we explicitly make distinctions between covariate and concept shifts and design data splits that accurately reflect different shifts. We used two domain selection strategies combined with covariate and concept, then obtain 4 different splits. For specific details regarding the OOD datasets, please refer to Appendix A. Subsequently, we present the results for concept_degree and covariate_word in Table 1 . Additional experimental results can be found in Table 9 in Appendix E.We adopt the wide-used metric, i.e., accuracy (ACC) to evaluate the model performance. All experiments were conducted five times using different seeds and the mean performance is reported. GPT-3.5-turbo-0613 is adopted to generate annotations. Regarding the prompting strategy for generating annotations, the integration of cost and accuracy led to the adoption of the few-shot strategy. The budget for active selection was detailed in Table 4 in Appendix A. The pipeline can be applied to any GNN model, with the most popular GCN [27] being adopted in this experiment. The results of other GNN backbones (GAT and To answer RQ1, we conduct a comparative analysis with other four OOD generalization methods. The ACC results are reported in Table 1 . From the comparison results, we make some findings. (1) The results in Table 1 display that the proposed LLMTTT performs exceptionally well in the node classification task on the OOD datasets, surpassing all baseline methods. (2) EERM exhibits good performance compared with Tent, but it is constrained by computing resources. This further suggests that post-hoc methods (i.e. FTTT) are better suited for real-world applications due to their plug-andplay simplicity, which does not interfere with the costly training process associated with pre-trained models. (3) GTrans and Ho-moTTT are both FTTT-based methods. The superior performance of LLMTTT over them illustrates that even a limited number of labeled test instances can significantly enhance test-time training performance.More results under other split methods are presented in Table 9 in Appendix E. This further demonstrates the effectiveness of the proposed LLMTTT .It is intuitively believed that higher quality pseudo labels can more effectively assist in model fine-tuning during TTT. However, LLMs cannot always produce high-quality labels. Therefore, it is necessary to subsequently obtain better quality labels comparing the accuracy of labels generated by LLMs under different prompts. Before proceeding, we can evaluate this conjecture with a simple experiment.The Importance of Pseudo Label Accuracy. At this part, the relationship between LLMTTT performance and LLM accuracy is explored. After securing a fixed node candidate set, the accuracy of the selected nodes is artificially controlled. The experimental results in Fig. 2 confirm our conjecture, which states that pseudo label accuracy decide the celling of LLMTTT accuracy under a fixed node selection method 5.3.2 LLM and TTT Accuracy under Different Prompts. In this part, we test the accuracy of pseudo labels provided by LLM under different prompts on test samples. Specifically, we used the following prompts: (1) zero-shot; (2) few-shot; (3) few-shot with GNN; (4) few-shot with 2-hop summary. Briefly speaking, "zero-shot" denotes there is no ground-truth label information, while "few-shot" represents that there are some ground-truth labels from the training set. In addition, "few-shot with GNN" further incorporate the information from the pre-trained GNN model based on "few-shot". "few-shot with 2-hop summary" refers to a twice-request prompt strategy [6] , which include both the target node information and the aggregation information from its neighboring nodes.We conducted a comparative study to identify strategies that are effective in terms of both accuracy and cost-effectiveness. Observation 1. The benefits of neighborhood summary are not universal across all datasets. The results presented in Table 2 demonstrate that using a few-shot prompt to aggregate neighbor information can result in performance improvements. However, prompts incorporating structural information may also be adversely affected by heterogeneous neighboring nodes, as evident by the significant degradation of LLM's performance on PUBMED and WIKICS after incorporating structural information. The integrated prompt, which combines the predictive information from a pre-trained GNN model, does not consistently yield positive results across all datasets. Additionally, its performance in this scenario is intricately tied to the effectiveness of the pre-trained model.Given the aforementioned information and the cost under different prompts shown in Table 2 , we adopt the few-shot prompt approach with the aim of attaining a more generalized and superior performance. Meanwhile, the failure of "few-shot with 2-hop summary" also motivated us to design a prompt that can accurately represent the graph structure. Thus, LLMs can be more effectively employed to solve graph level tasks.The nodes utilized for model training undergo two selection processes. Initially, a hybrid active node selection strategy is employed, followed by a post-filtering strategy that leverages the prediction results obtained from LLMs.Strategies. Initially, we explore various components of hybrid active node selection, including Pagerank, FeatProp, and entropy. Secondly, we compared our hybrid node selection strategy with traditional active learning methods, such as density and degree, as well as random node selection methods.From Table 3 , we find that traditional active learning methods are not applicable and effective as expected in our scenarios. Based on the empirical results, the study makes the following observation: Observation 2. Some research [7] has demonstrated that nodes in proximity to cluster centers often demonstrate higher annotation quality. Consequently, the node set selected by density-based active strategy will be assigned high-quality annotations. However, the density-based active selection strategy does not achieve the optimal performance. This gives us an intuition that improvement not only depends on LLM accuracy, but also the node selection.The Appendix C further substantiates our conjecture through the control of accuracy of labels annotated by LLMs.In this part, we examine the effectiveness of the proposed post-filtering strategy. Given that the proposed post-filtering strategy incorporates confidence scores and takes into account the diversity of nodes (COE), we also perform ablation experiments in this section. The experimental results are presented in Figure 3 . Observation 3. The proposed post-filtering strategy demonstrates significant effectiveness. Furthermore, aligning with our previous observation, although the node selected by "conf_COE" does not possess the most accurate labels, they demonstrate the best model performance. This verification from another perspective suggests that model performance is not fully positively correlated with pseudo label accuracy.  
distribution shift in gnns: 
 Graph Neural Networks (GNNs) have demonstrated exceptional capabilities in graph representation learning [36, 59] , achieved revolutionary progress in various graph-related tasks [51] , such as social network analysis [24, 45] , recommendation systems [9, 18, 53] , and natural language processing [3, 23, 29] . However, a distribution shift has been observed in various graph-related applications [20, 21] , where the graph distribution in the training set differs from that in the test set. Such discrepancy could substantially degrade the performance of both node level [56, 66] and graph level tasks [56, 66] . This distribution shift frequently occurs between the testing and training graphs [20, 21] . Therefore, enhancing the out-of-distribution (OOD) generalization capabilities of GNNs is crucial. Several solutions have been proposed to tackle this issue, such as EERM [56] , which trains GNNs to be adaptable to multiple environments by introducing environmental variables, and GTrans [25] , which enhances generalization ability by modifying the input feature matrix and adjacency matrix during test time.Test-time training (TTT) is a technique recently proposed for partially adapting a model based on test samples, to account for distribution shifts between the training and test sets. TTT was first introduced by [44] . To address the unexpected adaptation failures in TTT, TTT++ [31] employs offline feature extraction and online feature alignment to enable regularization adaptation without the need to revisit the training data. However, in some cases, the training data may be unavailable during test time or the training process may be computationally demanding, which can reduce the applicability of these methods. To overcome this limitation, Tent [49] introduces a method for fully test-time training that relies solely on test samples and a trained model. They propose an online setting after the TTT task to achieve fully test-time training through the minimization of the model's test entropy. While the aforementioned studies focus on test-time training within the image domain, the TTT framework has also been implemented in the realm of graphs, including GTrans [25] , GT3 [52] , GraphTTA [4] , and TeSLA [46] .Graph active learning aims to optimize test performance through the strategic selection of nodes within a constrained query budget, effectively addressing the challenges of data labeling. The most prevalent approach in active learning is uncertainty sampling [37, 43, 48, 54] , wherein nodes that the current model has the least certainty about are selected during the training phase. Another significant strand within active learning approaches involves distributionbased selection strategies. These methods [2, 11, 41, 42, 65, 65] evaluate samples based on their positioning within the feature distribution of the data. Representativeness and diversity represent two commonly utilized selection criteria, both of which rely on the data distribution. Generally, active learning primarily focuses on selecting representative nodes; however, it faces additional challenges in real world scenarios. Furthermore, active learning needs to address two key issues: assigning pseudo-labels to the selected nodes and effectively utilizing a limited number of labels for training. In the proposed LLMTTT , these two problems are well solved.Large language models (LLMs) with massive knowledge demonstrate impressive zero-shot and few-shot capabilities. Considerable research [14, 17] has begun to apply LLMs to graphs, enhancing performance on graph-related tasks. Utilizing LLMs as enhancers [14] presents a viable approach, leveraging their power to enhance the performance of smaller models more efficiently. Compared to shallow embeddings, LLMs offer a richer commonsense knowledge base that could potentially enhance the performance of downstream tasks. Relying solely on LLMs as predictors [6, 50, 60] represents another viable approach, with GPT4Graph [14] evaluating the potential of LLMs in performing knowledge graph (KG) inference and node classification tasks. NLGraph [50] introduced a comprehensive benchmark to assess graph structure reasoning capabilities. Distinct from these approaches, we employ LLMs as annotators as [7] , combining the advantages of the two aforementioned methods to train an efficient model without relying on any true labels. 
conclusion: 
 We introduce a novel TTT pipeline LLMTTT which introduces LLM as an annotator to provide a limited number of pseudo labels for fine-tuning the pre-trained model. To select a candidate set that is both representative and diverse, the proposed pipeline LLMTTT designs a hybrid active selection that also considers the pre-trained model signal. Following this, we generate high-quality labels with corresponding confidence scores with the help of LLMs. Finally, we present a two-stage training strategy that maximises the use of the test data. The strategy includes confidence-based post-filtering to mitigate the potential impact from the noisy labeled test data. Additionally, a weighting function is used to introduce a large amount of unlabeled test data into the training process. Comprehensive experiments and theoretical analysis demonstrate the effectiveness of LLMTTT . 
 
 Appendix:  


Decision: The paper proposes LLMTTT, a novel pipeline for test-time training of Graph Neural Networks (GNNs) using Large Language Models (LLMs) to generate pseudo-labels for out-of-distribution (OOD) generalization. Reviewers appreciated the detailed experimental analysis, theoretical support, and innovative use of LLMs for enhancing GNN adaptability. However, concerns were raised regarding the lack of experiments on multimodal datasets, potential biases from LLM training data, limited baseline comparisons, and the absence of ablation studies. Additionally, the computational overhead and scalability of LLMTTT were not thoroughly analyzed. The consensus leaned towards borderline acceptance, acknowledging the method's potential despite some limitations in experimental scope and relevance to multimodal information processing.

There is a significant debate about this paper's relevance to the MM community. While graph is not directly an MM topic, it surely connects important research areas such as multi-modal data application. Thus, we should not solely judge the paper based on the relevance. The final decision is borderline acceptance.

Reviews: review: paper_summary: paper_summary: This paper proposes a pipeline LLMTTT, which incorporates LLM as an annotator to generate  pseudo labels for test-time training. LLMTTT incorporates a hybrid active selection method and generate high-quality labels along with confidence scores. Additionally, a two-stage training strategy is introduced to maximize the use of the test data.
strength_weakness: strength_weakness: - This paper is well-written and it provides a detailed experimental analysis.
- Theoretical analyses are provided to support the effectiveness of labelled test samples
- The proposed LLMTTT is a novel pipeline that offers valuable insights into LLM for graph OOD.
limitations: limitations: - In **The Selection Algorithm**, the authors don’t specify whether the PageRank and FeatProp scores are calculated over all samples or $\beta B$ samples. If the scores are calculated within the $\beta B$ samples, it may not guarantee the diversity of the resulting $B$ samples.
- There are some errors in the paper, “incorporates both the labeled test nodes $D_{tr}$ and unlabeled test nodes **$D_{\text {tre}}$**”, “This section theoretically demonstrates that incorporating labelled test samples provided by **LMMs** during the test-time training phase can significantly improve the overall performance across the test domain.”
- The topic may be not relevant to the MM conference since the tasks in this paper do not include multi-modal information.
- The inference time in TTT could be a concern.
- LLM may have trained on some data that are adopted for testing, e.g., arxiv. Therefore, it could be unfair to compare the OOD performance for this method (w/ llms) and baselines (w/o llms).
paper_summary: paper_summary: The paper introduces a novel method called LLMTTT (Test-Time Training on Graphs with Large Language Models) to address the challenge of Out-of-Distribution (OOD) generalization in Graph Neural Networks (GNNs). LLMTTT leverages Large Language Models (LLMs) to provide pseudo-labels for a carefully selected set of nodes during the test-time adaptation phase, avoiding the need for intricate unsupervised task designing. The paper proposes a hybrid active node selection strategy that considers node diversity, representativeness, and prediction signals from the pre-trained model, and a two-stage training strategy to utilize both the noisy labeled nodes and the remaining unlabeled nodes during test-time adaptation. Extensive experiments and theoretical analysis demonstrate the effectiveness of LLMTTT in improving OOD generalization on various graph datasets.
strength_weakness: strength_weakness: Strengths:

- The paper introduces a novel method called LLMTTT that leverages LLMs to provide pseudo-labels for a carefully selected set of nodes during the test-time adaptation phase, avoiding the need for intricate unsupervised task designing. This approach allows the model to benefit from the annotation capabilities of LLMs to enhance test-time training and handle the Out-of-Distribution (OOD) problem on graphs.
- The paper proposes a hybrid active node selection strategy that considers node diversity, representativeness, and prediction signals from the pre-trained model. This strategy helps to select the most valuable nodes for annotation using LLMs within a constrained budget. 
- The paper provides theoretical analysis that demonstrates the effectiveness of LLMTTT in improving OOD generalization on various graph datasets. Specifically, Theorem 2 presents a direct theoretical guarantee that LLMTTT decreases the error bound on the test domain compared to traditional Test-Time Training (TTT) in the absence of labeled test data.
limitations: limitations: Weakness:
- The author does not provide the source codes of LLMTTT, so the experimental results can not be reproduced. Additionally, the baselines are not strong enough, and the number of baselines is limited. More effective, latest, and novel GNN methods for OOD need to be considered, such as OOD-GNN[1], OODGAT-ATT[2], and OOD-GMixup[3].
- Compared with EERM, the experimental results from LLMTTT in Cora and Wikics are not obviously enhanced compared to those in Citeseer in Table 1, and the author does not provide a detailed explanation for this phenomenon.
- The author only evaluates LLMTTT on a limited set of graph datasets, such as Cora, PubMed, Citeseer, and WikiCS. While these are commonly used benchmarks, evaluating the method on a more diverse range of graph datasets, including larger and more complex graphs, would provide a more comprehensive understanding of its generalization capabilities.
- The paper also does not provide the ablation studies about the key components of the LLMTTT framework, such as the hybrid active node selection strategy and the two-stage training approach.

References:

- [1] Li H, Wang X, Zhang Z, et al. Ood-gnn: Out-of-distribution generalized graph neural network[J]. IEEE Transactions on Knowledge and Data Engineering, 2022.
- [2] Song Y, Wang D. Learning on graphs with out-of-distribution nodes[C]//Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2022: 1635-1645.
- [3] Lu B, Zhao Z, Gan X, et al. Graph out-of-distribution generalization with controllable data augmentation[J]. IEEE Transactions on Knowledge and Data Engineering, 2024.
paper_summary: paper_summary: This paper presents LLMTTT, which leverages LLM as an annotator to improve a set of pseudo labels for model fine-tuning. To curate a candidate set that embodies both representation and diversity, LLMTTT employs a hybrid active selection method that takes into account the signal from the pre-trained model. Subsequently, LLM produces higher quality labels. And a two-stage training approach is adopted for optimizing test utilization.
strength_weakness: strength_weakness: Test time training on graph is an excellent entry point; even as research on TTT has progressed, there are very few studies on improving TTT with LLM. I believe out-of-distribution generalization is a highly significant topic.

The extensive experiments validate the effectiveness of the proposed method over other SOTA methods.
limitations: limitations: 1. I am not sure about the correctness of proof for Theorem 1 since I cannot find the Appx from the submission. I still have some confusion here, for example, the how you estimated distribution shift in theorem 1 and the derivation of boundness of this term.


2. Why the nodes with higher prediction entropy are useful for test-time training? If the test-time input graph/node is out-of-distribution, are you assuming that some information from in-distribution graph could still help? What if this assumption does not hold anymore?

3. Is the LLM here really an effective design? It is better to prove this with a simple experiment.
paper_summary: paper_summary: This paper proposes novel methods for testing out-of-distribution generalization. It introduces LLMTTT (Large Language Models Test-Time Training), a method aimed at improving the effectiveness of Graph Neural Networks (GNNs) in handling distribution shifts between training and test data. LLMTTT leverages the annotation capabilities of Large Language Models (LLMs) on Text-Attributed Graphs for test-time adaptation.     It introduces a hybrid active node selection strategy and a two-stage training strategy to tailor the test-time model using limited and noisy labels obtained from LLM annotations. The method is supported by theoretical analysis and extensive experiments demonstrating significant performance improvements compared to existing approaches.
strength_weakness: strength_weakness: S1. The paper introduces a novel method, LLMTTT, which addresses the challenge of distribution shifts in GNNs by leveraging LLMs for test-time adaptation. This approach is innovative and demonstrates a new direction in improving GNN generalization performance.  By leveraging the annotation capabilities of LLMs on TAG, LLMTTT taps into the rich contextual understanding provided by these models, enhancing the adaptability of GNNs.

S2. LMT is supported by extensive experimental results demonstrating significant performance improvements compared to existing approaches. This empirical validation strengthens the credibility and applicability of the proposed method.

S3. The paper provides theoretical analysis to support the validity of the proposed method, enhancing the understanding of its underlying principles and mechanisms.
limitations: limitations: W1. The paper does not provide a detailed analysis of the computational overhead and scalability implications of LLMTTT resulting from its reliance on LLMs.

W2. The two-stage training strategy of LLMTTT relies on annotations from LLMs, which may introduce noise or inaccuracies, especially in cases where LLMs struggle with understanding complex graph structures or context.  Noisy annotations could negatively impact the performance of LLMTTT, particularly in scenarios with limited labeled data.

W3. There are some grammar errors, such as, "Appendix" is used in the first part of the paper, and "Appx" is used in the second part of the paper. Please pay attention to the consistency of the statement before and after the paper, which will greatly improve the readability of the paper.

W4. The notation in Algorithm 1 is not stated. Providing more notation for formulas in the paper will improve the clarity of the paper.

W5. The code is not provided in the supplementary material, which affects the reproducibility of the paper.