GraphText: Graph Learning in Text Space

We sincerely appreciate your insightful comments. Below, we address each of your points:

W1.Heavy Parameter Tuning

We would kindly argue that in fact, GraphText has lighter parameter tuning compared with standard GNN framework. It has many advantages due to the training-free property of the framework for ICL:

1. Smaller search space: For a basic machine learning model, besides the model parameters, we typically have to determine the hyperparameters for training, including the number of epochs, learning rate, batch size, learning rate schedule, weight decay, and regularization term. Since there is no graph training, these hyperparameters related to model are not searched. The only two hyperparameters for GraphText to search are the choices of text information and relation information to construct graph-syntax trees. As the size of the hyperparameter search space grows exponentially in terms of the number of hyperparameters, GraphText enjoys a much smaller search space.
2. No need for training multiple models for multiple datasets: Only one model, i.e. ChatGPT is used, compared with 5 individual models trained for each dataset.
3. Less device requirement: Since there is no training, and we can leverage closed-end API calling of ChatGPT, no GPU is required to perform GraphText-ICL experiments.
4. Cheap inference: The cost is actually extremely low, for example, for each sample, empirically, it takes around a total of 2.5 hour (with 4 parallel workers) for the hyperparameter search on three heterophilic datasets (15 USD for 300 runs).

W2: Reliance on Domain Knowledge for Interactive Graph Reasoning

We acknowledge the importance of domain knowledge in interactive graph reasoning. However, it's worth noting that human feedback is an optional enhancement rather than a necessity for our model. Except for the experiments in Section 4.2, all other tests were conducted in a single-turn question-answering format without any human feedback. This setup demonstrates the robustness and versatility of GraphText in handling various graph-related tasks.

Q1: Number of Prompts/Training Samples in Experiments

In the ICL experiments presented in Table 1, we selected one example per class from the training set, ensuring a fair selection by choosing the example with the largest degree to avoid biased selection (e.g., orphan nodes). Please refer to Appendix C.1 for a concrete example.

Q2: K-means Parameter and Rationale

For transforming continuous features into a discrete space using K-means, we set K equal to the number of classes. This choice is based on the intuition that if raw or propagated features can be clustered into C distinct clusters representing each class, the LLM can easily learn a direct one-to-one match through in-context learning.

We hope that our detailed responses have satisfactorily addressed the concerns and questions raised by the reviewers.

We appreciate your insightful comments and enhanced our manuscript based on your feedback. Below, we address each of your points:

W1: Comparative Analysis with Existing Baselines

We understand the importance of benchmarking our method against established baselines in the field. Accordingly, we have added additional In-Context Learning (ICL) baselines, including GraphML and GML, in our updated results presented in Table 1. The comparative analysis demonstrates that GraphText not only holds its ground against these methods but also achieves state-of-the-art (SOTA) ICL performance. We report an absolute performance gain of 34.02% over the best ICL baselines, which significantly underscores the effectiveness and innovation of GraphText in the context of graph-based learning.

W2: Construction of Discrete Text from Continuous Features

The core objective of our research is to establish a bridge between the text and graph domains using a tree-based prompt framework. The task of discretizing continuous features into textual format, while vital, is a complex endeavor that we have identified as a potential avenue for future research. We acknowledge that the optimal settings in our current model are predominantly reliant on label propagation, and we aim to explore more advanced discretization techniques as future work.

W3: Time Complexity Analysis

The time complexity for obtaining a graph's label distribution reveals distinct operational differences is shown in the table below:

Specifically, a typical GNN, undergoes three stages: (1) Preprocessing the graph, (2) Training on the graph, and (3) Inference. For a graph with $N$ nodes and $E$ edges, where label, features, and hidden dimensions are uniformly dimension $F$, the time complexity for a $L$-layer GCN message passing on $F$ is $O(LEF + LNF^2)$, simplifying to $O(EF+NF^2)$. This complexity applies to both training and inference. However, training usually requires more wall time due to the need for repeated forward passes and gradient updates for multiple epochs until convergence.

In contrast, the GraphText framework, being training-free, eliminates training time entirely. It operates in two phases: a preprocessing phase, where synthetic textual and relational data are generated to construct graph-syntax trees, and an inference phase, where LLM inference is carried out.

The time complexity of preprocessing depends on the chosen synthetic text and relation information for the graph-syntax tree. For synthetic text, feature propagation in the synthetic text information phase takes $O(LEF)$ time. The $K$-means algorithm, used here, has a time complexity of $O(NKFI)$ ($I$ being the number of iterations).

For synthetic relations, calculating row-wise similarity of the feature matrix requires $O(N^2F)$ time. Finding the Shortest Path Distance (SPD) with a maximum hop $H$ (empirically set to $H \leq 4$), optimally solved using Bellman Ford [1], results in $O(EH)$ time complexity for one node and $O(NEH)$ for all nodes.

Thus, the total time complexity for preprocessing, combining all synthetic relations, is $O(LEF+NKFI+N^2F+NEH)$, simplifying to $O(N^2F+NE)$. This is manageable since preprocessing is a one-time process.

The inference time depends solely on the LLM's inference time, influenced by the context length $T$, model size, inference speedup techniques, and API response time (if using an API like OpenAI models). For instance, using ChatGPT for 600 tokens approximately takes 1 second.

In conclusion, GraphText, unlike GNNs, has no training time, with its primary time complexity bottleneck in preprocessing. Users can adjust and select less computationally intensive synthetic text/relations for graph-syntax trees, enabling GraphText's application on large graphs.

We appreciate your valuable feedback and have addressed each of your points as follows:

W1: Comparison with Large Text-Attributed Graph Datasets

General graphs with continuous features are much more common and challenging for LLM to perform reasoning on compared with text-attributed graphs (TAGs), which demand a text description for each node. For example, for Cora, the problem of classification of a paper’s topic becomes much easier once the node's text attributes (title and abstract) are given compared with using only the continuous feature and observed labels. Hence, we believe that general graphs are better datasets for evaluating LLM’s graph reasoning ability than TAGs. In addition, we also have TAG experiments on Section 4.4, showing that GraphText is effective in TAGs.

Regarding large-scale datasets, the experimental setting of in-context learning (ICL) distincts itself from standard supervised finetuned (SFT) GNNs. Due to the limitation of OpenAI API calling, hundreds/thousands of samples are evaluated in standard ICL literature [3,4,5] and are enough to prove the concept. The recent endeavor [1] also leverages 100 samples in their experiments. In our main experiments, we are presenting the full test set results of Cora and Citeseer (1000 nodes) along with three heterophilic datasets.

W2: Questions

• Variance of Heterophilic Datasets: The mean and variance of results (5 different seeds) are: Texas: (75.7, 0.0) Wisconsin(67.9, 0.9) Cornell (57.8, 1.5), which is similar to GCN’s: Texas (59.5, 4.1), Wisconsin (49.0, 0.6), Cornell (37.8, 1.2).
• Comparison with Supervised Baselines, e.g. MLP: While we acknowledge that In-Context Learning (ICL) approaches typically do not outperform Supervised Fine-Tuning (SFT) methods, the primary objective of GraphText is to enhance ICL capabilities for Large Language Models (LLMs) in graph reasoning tasks. Our focus was not to surpass all existing SFT GNN baselines but to demonstrate the effectiveness of GraphText in an ICL setting. Notably, GraphText achieves state-of-the-art performance in this domain, realizing a significant absolute performance gain of 34.0% over the best existing ICL baselines. This advancement is noteworthy, especially considering that in some cases, GraphText even manages to outperform certain SFT GNN methods, highlighting its potential in ICL for graph-related tasks.
• Inconsistency in Accuracy on Cora: We apologize for the discrepancy in the accuracy figures for Cora in Tables 3 and 1. The correct performance for Cora should be 68.3%. We have corrected it in the updated version.
• Hyper-parameter Study: While Table 1 and 3 includes several ablation studies, a comprehensive hyper-parameter study was beyond our scope due to time constraints and will be considered for future research.
• Utilizing LLMs with General Graphs: As our focus is on general graphs without text attributes, the proposed experiment comparing the direct use of LLMs on text attributes while ignoring graph structure is not feasible in our study.

W3: Time Complexity Analysis

Please see the other response for details.

W4: Applicability to Other Graph Tasks

Yes, GraphText can be applied to a range of graph-related tasks. By constructing graph-syntax trees tailored to specific tasks, the LLM can effectively address various scenarios. For instance, in link prediction tasks like recommendation systems, a graph-syntax tree can be formed with users and candidate items as nodes, enabling the LLM to predict user preferences.

References

[1] Chen, Zhikai, et al. "Exploring the potential of large language models (llms) in learning on graphs." arXiv preprint arXiv:2307.03393 (2023).

[2] Polak, Adam. "Bellman-Ford is optimal for shortest hop-bounded paths." arXiv preprint arXiv:2211.07325 (2022).

[3] Wei, Jason, et al. "Chain-of-thought prompting elicits reasoning in large language models." Advances in Neural Information Processing Systems 35 (2022): 24824-24837.

[4] Wang, Xuezhi, et al. "Self-consistency improves chain of thought reasoning in language models." arXiv preprint arXiv:2203.11171 (2022).

[5] Yao, Shunyu, et al. "Tree of thoughts: Deliberate problem solving with large language models." arXiv preprint arXiv:2305.10601 (2023).

We appreciate your insightful comments and concerns. Below, we address each of the weaknesses you highlighted:

W1: Performance on Cora/CiteSeer

We acknowledge the good performance of Cora and Citeseer reported in [1]. However, it is essential to clarify that [1] leverages text-attributed graphs, which inherently simplify LLM reasoning due to the presence of raw text attributes. For citation graphs like Cora and Citeseer, classifying a paper’s topic becomes a much easier problem once the node's text attributes (title and abstract) are given compared with using only the continuous feature and observed labels. Our approach, on the other hand, targets a more complex scenario—general graphs (where only continuous features, i.e. bag of words in Cora and Citeseer, are available). This distinction is crucial as it places our method in a more challenging context compared to the text-attributed graph setting. To further ease the concerns, we include [1], denoted as NeighborText, as a baseline in the updated paper and leverage the observed label as raw text attributes. We can see that GraphText shows an average absolute improvement of 50.26%, which clearly shows the effectiveness of our design.

W2: Comparison with MLP and Heterophily Graph Methods

Your suggestion that MLP could achieve better heterophily results is true. However, it is important to consider the unique ICL setting of GraphText, where a single LLM for text generation addresses graph problems via reasoning from only one sample per class without any specific graph training. This ICL framework significantly differs from the supervised learning settings employed by GNN/MLP, where multiple nodes (up to 20 per class) are used for training, and different models are trained for each graph. Hence, it is unfair to compare SFT baselines with ICL baselines. Nevertheless, GraphText not only outperforms other ICL baselines significantly (by 34.02%) but also shows competitive results against several GNN baselines, achieving a 6.64% absolute performance gain over GCN, even without graph-specific training.

W3: Clarification on Pseudo Labels and Human Interaction

We apologize for the confusion, the pseudo labels are generated from $k$-hop propagated labels, i.e. $\boldsymbol{A}^{k}\boldsymbol{Y}_L$, (as discussed in Appendix A.3). The ‘human feedback’ states the definition of PPR, as illustrated in Figure 2, and let LLM re-evaluate the problem. To provide further clarity, we have included a detailed analysis of interactive graph reasoning in Appendix C. This analysis includes detailed prompts, human feedback, and sample reasoning from ChatGPT and GPT-4.

W4: In-Context Learning Performance of GPT-4 vs. ChatGPT

The short answer is: as shown in Table 2, for the same prompt of a graph reasoning problem, GPT-4 (73.3 accuracy) outperforms ChatGPT (26.7 accuracy) which indicates GPT-4 outperforms ChatGPT. For an in-depth discussion on this topic and how GPT-4 outperforms ChatGPT with better reasoning, we refer you to the expanded discussion in Appendix C.

[1] Chen, Zhikai, et al. "Exploring the potential of large language models (llms) in learning on graphs." arXiv preprint arXiv:2307.03393 (2023).