GOFA: A Generative One-For-All Model for Joint Graph Language Modeling

W1: The authors suggest that integrating GNN layers into LLMs offers a theoretical advantage over standard LLMs when it comes to modeling graph structures. However, I did not find any accompanying mathematical formulations or equations to substantiate this claim in the appendix.

Thanks for the advice. Here we provide additional discussion on the theoretical advantage. Define $g \in \mathcal{G}$ as the permutation operation in the permutation group $\mathcal{G}$. We say a function is permutation invariant if $\forall g \in \mathcal{G}$, we have:

$$f(x) = f(gx).$$

In graph, a typical permutation operation $g$ can permute the order of nodes in the graph. Let a graph input be $G=(V, E)$, where $V$ is the set of nodes and $E$ is the set of edges. We denote a permutation operation on the graph as $gG=(gV, gE)$. As for LLM, the graph is first flattened and then input into LLM with positional encoding on each token or token pair, it is easy to prove that:

$$\text{LLM}(\text{flatten}(V, E)) \neq \text{LLM}(\text{flatten}(gV, gE)), \forall g\in \mathcal{G}$$

Instead, GNNs are designed with permutation invariant in mind and naturally hold that $\text{GNN}(G) = \text{GNN}(gG), \forall g\in \mathcal{G}$. Finally, we show that GOFA that integrate GNN into LLM are permutation invariant to node order. In LLM layer, each node and edge are fed into the model independently. That is:

$h^{l+1}_{v}$ $=$ $\text{LLM}_l$ $(h_v^l)$ $,\forall v \in V,$

and

$h^{l+1}_{e}$ $=$ $\text{LLM}_l$ $(h_e^l)$ $,\forall e \in E.$

The permutation of the graph will not affect the process of each individual node or edge. Thus, the permutation invariant holds for LLM layers. For GNN layers, the permutation is held as we discussed above, which concludes that the GOFA is permutation invariant to the node order of the graph.

Finally, we can directly leverage Theorem 7 in [1] to show the generalization gap between LLM and GOFA in modeling graph related problems. The Theorem is as follows:

Let $\mathcal{X}=\mathbb{R}^d$ denote the input space and $\mathcal{X} \sim \mathcal{N}(0, \sigma^2_{\mathcal{X}}I)$, $\mathcal{Y} = \mathbb{R}$ be the output space. Let $\mathcal{G}$ be a compact group with an orthogonal representation $\phi$ on $\mathcal{X}$. Let the function we want to predict be $Y=h_{\theta}(X) + \xi$ where $h_{\theta}(x)=\theta^Tx$ is $\mathcal{G}$-invariant with $\theta\in \mathbb{R}^d$ and $\xi$ is the noise factor with mean 0, variance $\sigma^2_{\xi}< \infty$ and is independent of $X$. Let $w$ and $\hat{w}$ be the least-squares estimate of $\theta$ from i.i.d examples $\{(X_i, Y_i)|i=1,...,n\}$ with respect to model with and without $\mathcal{G}$-invariant property . let $A$ be the orthogonal complement of the subspace of $\mathcal{G}$-invariant linear predictors. If $n > d+1$, the generalization gap $\Delta(h_w, h_{\hat{w}})$ can be measured by:

$$\mathbb{E}[\Delta(h_w, h_{\hat{w}})]=\sigma^2_{\xi}\frac{\text{dim} A}{n-d-1},$$

where $\text{dim}A$ is a measurement of how significant the symmetry is to the problem. A larger $\text{dim}A$ will result in a larger generalization gap and indicate the importance of using a $\mathcal{G}$-invariant function and weight $w$. We refer the reviewer to [1] for more details of the Theorem.

Since the permutation group is a special case of a compact group, we can directly replace the $h_w$ with GOFA and $h_{\hat{w}}$ with LLM, and the theorem still holds. That means if the function $h_{\theta}(x)$ we want to model requires permutation invariant ability, GOFA will have better generalization ability than LLM with a theoretical guarantee. The only thing left is that the real-world data and function we want to model may not be i.i.d and also non-linear, which adds additional complexity to the problem. However, it is natural to expect the gap would be further expanded in such cases. We omit the proof here as it is extremely complex and beyond the scope of our work.

W1: It is unclear whether the results in Table 2 of the paper represent a true zero-shot setting, since the authors mention in Section 5.2 and Appendix F.4 that the model is instruction-finetuned on node classification and link prediction examples. The datasets in Table 2 are unseen, however samples of the same task on other datasets has been seen by the model during instruction finetuning, making it seem like this is a generalization task to unseen datasets rather than a zero-shot setting where the model has never seen node classification samples before.

We believe our instruction-tuning and zero-shot evaluation protocol is valid as it exactly follows that of LLMs. An LLM model will also need instruction fine-tuning first to understand the tasks, otherwise it can hardly produce meaningful responses. To be more concrete, LLM is first pre-trained on large corpus to acquire general knowledge of human language. At this stage, the model has minimal question-answering ability, and can hardly generalize to unseen tasks or unseen formats (it is now an autoregressive model that completes sentences only). Next, the model is instruction fine-tuned on a small amount of data with diverse tasks to learn different task formats (these datasets include Alpaca, ColossalChat, etc.). In this step, the purpose is to learn the task format instead of gaining new knowledge [1]. Only after this process, the LLM can be used to answer free-form questions. For example, LLMs are often instruction-tuned on MATH dataset, seeing numerous math problem patterns during training (e.g. determining the number of a type of fruit), yet a new math problem of very similar format is still considered zero-shot learning during evaluation (determining the number of a particular type of colored balls).

In GOFA, this is the same scenario, where the purpose of instruction tuning is to learn the format of the task (e.g. classify paper into categories in a citation network) instead of gaining new knowledge, and we only use a small amount of data compared to pre-training for this purpose. Then, the experiment is conducted on various datasets that the model has never seen before but may share similar task formats to seen datasets (e.g. determine the most likely product type in a product network; both are node classification tasks). Therefore, the evaluation of GOFA is consistent with LLMs and is a true zero-shot setting. This zero-shot setting is also widely accepted by graph foundation model literature such as LlaGA [2], ZeroG [3], etc.

Moreover, we believe the requirement that a graph foundation model never sees any node classification samples might be overly strict and even infeasible since node classification is the most common type of task for graphs—probably analogous to requiring an LLM to not see any question-answering tasks. We hope this clarifies the rationale behind our methodology and reinforces the validity of our zero-shot evaluation protocol.

W2: Additionally, given that the authors emphasize GOFA as a graph foundation model, more comprehensive benchmarking across more graph datasets would better support this claim. Examples include Amazon Products, molecular graph datasets such as OGBN-molhiv, or protein-protein interaction datasets such as OGBN-proteins. Further benchmarks would better support the claim that GOFA supports diverse downstream tasks on graph-structured data across a variety of graph datasets.

Thanks for the suggestion. We have already included Amazon product dataset (Table 2) in our experiment. In general response 1, we additionally conduct zero-shot experiments on protein-protein interaction datasets and molecular graph datasets.

We would like to also point out that, while we are already excited about GOFA’s potential to generalize to unseen domains, a ChatGPT-level graph foundation model still needs to be trained or fine-tuned on much more diverse data in order for the model to generalize to broader domains [4]. The LLM’s generalizability to a particular subject area also comes from the fact that its pre-training process includes data from the proximal area or even the area itself, and it is difficult for LLM to generalize to completely unseen subjects. For example, without including code corpus from open-source platforms, LLMs struggled to solve code-related problems. We believe in the current stage, the proposed graph-language joint modeling problem and the GOFA architecture lay a promising path to a stronger and more generalized model. We will continue improving GOFA with more diverse and comprehensive data.

W3: The authors do not benchmark against any traditional GNN baselines. The main comparison remains other LLM and LLM-based graph models, however a graph foundation model should compare against traditional GNN baseline models to indicate performance relative to much lower capacity GNN models on the same tasks.

Thanks for the advice. In general response 2, we add zero-shot GNN baselines for reference.

Dear reviewer sGjN,

As the discussion period ends soon, we would like to check whether our responses answer your questions. Following your insightful comments, we have provided a more detailed discussion on the zero-shot capabilities of our model, demonstrating its alignment with the same settings as LLMs. Additionally, we have conducted new experiments on protein-protein and molecule graphs and included more GNN baselines for comparison. Thank you again for your comments and suggestions to improve our paper, and we look forward to your reply.

Best,

Authors

W1-1: Evaluation of Graph Structure Utilization. In Figure 1 and Section 3.4, the authors outline four pre-training tasks: (a) sentence completion, (b) question answering, (c) structural understanding, and (d) information retrieval. However, apart from the structural understanding task, it is somewhat unclear how these tasks benefit from graph information. For instance, tasks like sentence completion and question answering might be achievable by directly providing the raw text input to a generic LLM, possibly yielding similar outcomes. Similarly, in Figure 2, the sentence completion and question-answering tasks are primarily language-oriented and may not require graph-based augmentation. Even in Figure 3, the abstract completion task appears somewhat independent of the graph structure.

We appreciate the reviewer’s insightful feedback and would like to clarify the broader motivation and necessity behind our pre-training tasks. The primary goal of these tasks—graph sentence completion, question answering, structural understanding, and information retrieval—is not solely to enable GOFA to perform well on these tasks or to use graph information to enhance them. Instead, these tasks serve a more significant purpose: enriching the model's understanding of general graph knowledge and leveraging this enriched understanding to improve downstream graph tasks.

For example, the graph sentence completion task allows the model to query information from graph neighbors, enhancing its graph context understanding and resulting in better performance compared to pure LLMs, as demonstrated in Table 1, where GOFA with graph inputs achieves lower perplexity than both LLMs and GOFA with single-node inputs. We would also like to provide some intuition why graph information helps using the sentence completion task as an example. For target nodes, we randomly split its text into two parts, where the first part (can be of length as small as 0) and the neighbors’ full text are used to predict the second part. Consider citation network, where a node represents an article. Without information from its citing articles, it is hard to predict its title accurately, while with graph information, the model can infer the subject, topic, method, etc. much more accurately based on the vast amount of related articles in its neighborhood. This example intuitively demonstrates the usefulness of graph information for sentence completion.

Similarly, the question answering task trains GOFA to handle free-form queries by utilizing graph context, enabling it to generalize to diverse tasks. For instance, as shown in Figure 7, GOFA successfully outputs the most common product category in a graph even when such tasks were not explicitly seen during training stages. Furthermore, the information retrieval task significantly boosts the model’s generalization ability on graph-based tasks, as evidenced by the results in Figure 5, where pre-training on this task improves GOFA’s zero-shot performance on FB15K237, Products, and Cora-link datasets.

Overall, these tasks collectively enable GOFA to outperform LLMs on language-oriented tasks when graph information is included, while also ensuring the model’s robust transferability and effectiveness on unseen graphs and downstream graph-related tasks.

W1-2: It would be helpful if the authors could include a comparison where an LLM alone performs these tasks, highlighting any areas where it falls short. Alternatively, if GOFA matches or surpasses the LLM’s performance while adding distinct capabilities, this would serve as a compelling justification for GOFA’s design. Currently, the experimental section primarily focuses on comparing GOFA to LLMs in the structural understanding task (Q3), where graph augmentation evidently improves performance. Additionally, introducing more graph-relevant questions, as seen in recent works (e.g., Fatemi et al.), could further substantiate the advantages of incorporating graph structure in the evaluations.

For all zero-shot evaluations (Q2), we include pure LLMs, LLama2-7B, and Mistral-7B, as baselines (see Table 2 and Table 3). We can see that for most of datasets, GOFA achieves better results than LLMs. Particularly, Cora-node dataset asks the model to classify the category of the paper; WikiCS asks the model to classify the category of a Wikipedia page; Product asks the model to select the best product category. For all these tasks, only providing LLM with the context of the node can already achieve great results. However, by adding graph context, GOFA can further improve the performance. For tasks like Cora-link, where the graph structure are critical for reasoning the existence of edge, LLM shows only about random guess performance. Instead, GOFA achieves much higher performance than LLMs, showing the great graph structure understanding ability of GOFA. All these results demonstrate the distinct capability of GOFA compared to LLMs.

Thank you for your response. However, you did not answer my question, and, the evaluation procedure you described above shows that you performed an unfair comparison with the baselines.

Imagine a typical LLM model performing sentence completion, and assume you want to predict a paper's abstract or title. If I just provide a part of the paper's abstract to the LLM, it will probably perform mediocre to the task. Now imagine I, using a citation network, find all related works of that paper and provide also their abstracts/titles to the LLM. For instance, creating a prompt like:

paper 1 - title: ...., abstract: .....,
paper 2 - title: ...., abstract: .....,
paper 3 - title: ...., abstract: .....,
paper 4 - title: ..... abstract:

and letting the LLM fill in the last paper's abstract. Obviously, the results will be better, right? Notice, that the LLM is totally frozen and all I changed was my prompt to include related papers. How is this approach any different than the one you describe in GOFA? Because it appears there is no difference. Hence, my original question: "However, apart from the structural understanding task, it is somewhat unclear how these tasks benefit from graph information. For instance, tasks like sentence completion and question answering might be achievable by directly providing the raw text input to a generic LLM, possibly yielding similar outcomes." which you answered by saying that an LLM that sees only that one paper is performing worse, which is totally expected since it is an unfair comparison as you provide less information to it.

If the whole argument of your work is that extra information is needed (which can be found from another source like a graph), then how is it different from works like this https://arxiv.org/abs/2405.20139 that first extracts all the related information and then provides it to a frozen LLM? If GOFA is indeed a general-purpose Graph Language Model then it should be able to answer questions about the graph, just like in the case of the shortest path task in Figure 1.

W1: The model is designed more for the tasks where nodes/edges are rich in text. It would be interesting and more impactful to include tasks (in the pretraining and/or eval) that are more numeric, e.g. molecule prediction/generation such as ZINC or from open graph benchmark. While the SOTA specialized GNNs are probably going to work better in those cases, it would be interesting to see the gap.

Thanks for bringing this interesting point. In general response 1, we evaluate GOFA on molecule datasets that is more numeric-style. Although the performance is not as good at supervised methods, GOFA still achieve comparable results to other zero-shot baselines.

W2: Related to above, one potential issue of this approach is that representing node/edge features can be extremely inefficient when the features are high-dimensional (e.g. a node is an image or some other array data).

Thank you for raising this insightful concern. This is indeed a unique challenge when node/edge features are not purely textual-based. However, while our work primarily focuses on graphs within the text or textualized space, which covers most graph-based tasks studied in the research community, we believe that extending this framework to handle general multi-modal graphs is a promising and valuable direction for future research. In particular, GOFA has the potential to serve as a solid foundation for integrating multi-modal models. For instance, high-dimensional node features such as images could be encoded into the text space using vision-language models like BLIP-2 [1] or Flamingo [2], allowing GOFA to seamlessly incorporate these embeddings. Similarly, for array data such as tabular inputs, recent advancements like TableGPT [3] demonstrate the potential to generate robust representations that could be adapted for GOFA. These specialized models can effectively transform diverse modalities into a shared embedding space, enabling GOFA to capture interactions between multi-modal node representations and leverage them for enhanced learning. We appreciate your suggestion and will explore this promising direction in subsequent works.

W3: What's the SOTA GNN results in Table 2? It's not a direct comparison, but useful to know for reference.

In general response 2, we provide SOTA GNN baselines on zero-shot setting, we also refer you to Appendix B.1 for the supervised experiments as a reference.

W4: The examples in Fig 2 do not seem to require much knowledge of the graph, i.e. a plain LLM should be able to solve these tasks well. The example does not show what are the nodes and what is the meaning of edges and why those are important for the tasks. It seems like all the information exists within the node.

Thanks for the suggestion. The example shown in Fig 2 is mainly for demonstrating the functionality of Node-Of-Generation (NOG). We have updated Fig 2 to include a task that better utilizes graph structure for sentence completion (see the revised PDF, page 4, with changes marked in blue).

Additionally, we have included further examples from real-world graphs in Fig 7 (Appendix, page 19). For instance, in the product graph example, nodes represent different products and their descriptions, while edges indicate co-purchase relationships. By connecting an NOG and asking GOFA to find the majority category in the graph, the GOFA can correctly answer the corresponding category. In this example, without information from all nodes in the graph, it is hard for the model to generate the correct answer.

W5: In Table 4, it's unclear if LLM-N and GOFA-F trained on the same data? Also does LLM-N have the complexity of O((V k)^2) as discussed in L298?

In Table 4, the input to LLM-N and GOFA contains exactly the same amount of information and this experiment is to show that GOFA’s power does not solely come from the extra neighborhood information but also comes from its strong structural modeling ability. The LLM here is not fine-tuned. The main reason we didn’t tune the LLM is that if we input the same amount of information, the tuning of the LLM will result in OOM even if we use a very small $r$ in LoRA. This again demonstrates the memory efficiency of the GOFA compared to the original LLM.

And you are correct that LLM-N has the complexity of $O((V k)^2)$, where $V$ is the number of nodes and $k$ is the average number of tokens per node. This complexity arises from the self-attention mechanism, which scales quadratically with the input sizes.

Dear reviewer 5txS,

We sincerely appreciate your positive opinions and constructive review of our paper. As the discussion period is near its end, we would like to ensure our response aligns with your expectations and addresses your concerns. In our response, we conduct additional experiments on molecule datasets and add baselines for zero-shot GNN methods. We further clarified the importance of graph context in the graph task and explained the scenarios of how GOFA can be applied to much broader multi-modalities. We appreciate your feedback and look forward to any further comments.

Best,

Authors

Reference:

[1] Zhao, Haiteng, et al. “GIMLET: A Unified Graph-Text Model for Instruction-Based Molecule Zero-Shot Learning”, ICLR24.

[2] Pan, Xiao-Yong, et al. “Large-scale prediction of human protein-protein interactions from amino acid sequence based on latent topic features”, Journal of Proteome Research.

[3] Veličković, Petar, et al. “Deep Graph Informax”, ICLR19.

[4] Hou, Zhenyu, et al. “GraphMAE2: A Decoding-Enhanced Masked Self-Supervised Graph Learner”, WWW23.

[5] Liu, Hao, et al. “One For All: Towards Training One Graph Model for All Classification Tasks”, ICLR24.

[6] Su, Bing, et al. “A Molecular Multimodal Foundation Model Associating Molecule Graphs with Natural Language”, Arxiv22.

[7] Taylor, Ross, et al. “Galactica: A large language model for science.”, Arxiv22.