GFT: Graph Foundation Model with Transferable Tree Vocabulary

We appreciate the reviewer’s recognition of our work and thank the reviewer for detailed feedback. We address your concerns as follows.

W1: The experiments are unconvincing and most likely unfair.

[W1.1] Outdated supervised baselines. The baselines are not outdated, as our primary comparisons are with graph foundation models (GFMs) such as Prodigy [1] and OFA [2], published in NeurIPS 23 and ICLR 24, respectively. For supervised and self-supervised baselines, we selected classic works including GCN, GAT, GIN, DGI, BGRL, GraphMAE, and GIANT, in line with existing GFMs [1-4]. Despite being compared to recent supervised methods, our GFT still achieves better average performance (79.92) compared to GATv2 (ICLR ’22) with 76.19 and RevGAT (NeurIPS ’22) with 74.97.

[W1.2] What features are used? We strictly followed the OFA [2] to generate node attributes using SentenceBERT and conducted experiments on all baselines based on the SentenceBERT features rather than original features, ensuring a convincing and fair comparison. Since all baselines use the same text embeddings, we can ensure that any improvement is not merely due to the text encoder.

[W1.3] Why the performance of baselines is lower than expected? It's becuase the text encoder does not always lead to better performance with three resaons: (1) Complexity of text-based continuous features. These features are more complex than manually designed (discrete) features, making it challenging to learn the underlying correlations between features and labels. References such as [6] indicate this issue, where the performance of GraphSAGE on Arxiv degrades from 71.49 to 70.97 when replacing the raw 128-dim features with 768-dim BERT embeddings. Another example is in Table 10 of [5], where performance on molecule graphs (HIV) degrades from 75.52 to 74.20 when using textual features. (2) Noisiness of text-based features. Text-based features can be noisier than manually designed features due to biases in the prompts fed into language models, which can impair the quality of generated features and lead to spurious correlations between features and labels. (3) Harder experimental setting. For example, we use standard splits with 20 labeled nodes per class for training on Cora and Pubmed, rather than the 10/10/80 train/val/test splitting.

The lower performance of self-supervised baselines is due to their pretraining on all graphs, which may introduce extra noise, confusing the models in identifying patterns needed for specific tasks or domains. For example, [5] indicates that models (GraphMAE, DGI) pretraining on multiple graphs perform significantly worse than pretraining on a single graph, and [4] shows that GIANT’s performance on Arxiv is 70.87 when the model is pre-trained on ogbn-Papers100M.

W2: Assumes a common feature space across different graphs, limiting its applicability to non-textual graphs.

Although we use text-attributed graphs in our experiments, our GFT can also be applied to non-textual graphs by employing techniques like [7] to align the feature space. Furthermore, this assumption does not significantly impact the contribution of our work, as our primary goal is to identify potential transferable structures across graphs.

W3: The method involves a board hyperparameter space.

We thank the reviewer for mentioning the potential efforts involved in hyperparameter tuning. However, our method does not require extensive hyperparameter tuning. For example, when balancing the weights of different losses, it is sufficient to adjust their scales. For other hyperparameters, we can follow existing papers to set the default value. This simplifies our efforts to tuning only a few hyperparameters, such as learning rate, weight decay, and batch size. Despite this, our GFT still achieves superior performance.

W4: The interpretation of y-axis in Figure 5.

This axis represents a metric (NT gap) used to measure the occurrence of negative transfer. The metric follows the principle: for a certain target task T, if the pretrained model (pretrained on S) performs worse than a randomly initialized model, negative transfer occurs. Therefore, we define this metric as $\text{NT gap} = R(S,T) - R(\emptyset, T)$, where $R(S,T)$ is the loss of the pretrained model and $R(\emptyset, T)$ is the loss of the initialized model for the downstream task T.

W5: The difference between computation trees and subgraphs. How to construct computation trees?

W6: The time complexity analysis should consider the size of subgraphs. The real-time consumption should be provided.

Please refer to [W1] of the general response, where we provide a detailed comparison between computation trees and subgraphs, including the construction and time consumption. We would like to further clarify why it is not necessary to consider the size of subgraphs. The reason is that matrix-based BFS has the same time complexity regardless of the size of the subgraphs. Moreover, given a node, the number of involved nodes within k-hop is the same, no matter in tree-like or subgraph-like structures. This makes the impact of the subgraph size marginal when comparing computation trees and subgraphs.

Best regards,

The authors

Reference:

[1] Huang, et al., PRODIGY: Enabling In-context Learning Over Graphs, NeurIPS, 2023.

[2] Liu, et al., One For All: Towards Training One Graph Model for All Classification Tasks, ICLR, 2024.

[3] Chen, et al., LLaGA: Large Language and Graph Assistant, ICML, 2024.

[4] He, et al.,UniGraph: Learning a Cross-Domain Graph Foundation Model From Natural Language, Arxiv, 2024.

[5] Chen, et al., Text-space Graph Foundation Models: Comprehensive Benchmarks and New Insights, Arxiv, 2024.

[6] Chien, et al., Node Feature Extraction by Self-Supervised Multi-scale Neighborhood Prediction, ICLR, 2022.

[7] Zhao, et al., All in One and One for All: A Simple yet Effective Method towards Cross-domain Graph Pretraining, KDD, 2024.

I have carefully reviewed the rebuttal and the attached PDF. I appreciate the authors' efforts in addressing the weaknesses I identified.

The main concern, namely that the improvement is largely due to a better text encoder, has been mostly addressed. However, the results still fall short of my expectations. For comparison, the performance on GCN and GAT reported in this paper is 82.20 ± 0.49 and 82.77 ± 0.59, respectively (see Table 1 for details).

The explanation provided for the GIANT performance is unconvincing and supports my earlier assumption that the experimental setup is biased toward the GFT model. GIANT was designed to train on a single graph and should be evaluated in that context.

Overall, since my primary concern has been sufficiently addressed, I have increased my score accordingly.

Dear Reviewer hEws,

Thank you for your comments and suggestions to improve our paper, we would like to check whether our response answers your questions. Following your comments, we comprehensively discuss the experimental settings and the results obtained, and also provide a point-to-point response to all of your questions. We look forward to your reply.

We greatly appreciate Reviewer M9ZQ for the insightful feedback and are deeply inspired by your recognition of our contribution as “the first to demonstrate the potential existence of transferable tokens in text-attributed graphs.” We address your concerns as follows.

W1: How to define the 𝑗th neighbor related to two nodes in Theorem 2.2?

Let’s consider two cases. If the number of neighborhoods of the two nodes is the same, we can readily compare their corresponding neighbors. If the number of neighborhoods is different (e.g., n1, n2 where n1 > n2 ), we use a straightforward method for approximation. For the node with fewer neighborhoods (n2), we add virtual nodes in the number of (n1-n2) to ensure all nodes have n1 neighborhoods. It is true that a large gap in the number of neighborhoods between two nodes may lead to significant approximation error. However, we believe the approximation error would not be too large in real-world cases, where node degrees generally follow long-tail distributions. That is, most nodes have small degrees, while a small number of central nodes have high degrees. Therefore, it is not necessary to add too many virtual nodes when measuring the distance between computation trees, mitigating the approximation error.

W2: How to ensure the bounded distance measurement in Theorem 2.2?

While the distance between original node features might be unbounded, we employ a simple normalization technique (which is actually used in this paper) to manually bound the distance. Specifically, we normalize the features as $\mathbf{x} / \| \mathbf{x} \|$, converting the unbounded Euclidean distance into a bounded Cosine distance. This makes Theorem 2.2 more practical.

W3: The issue in Eq. 2 and the definition of 𝛿𝑗.

We apologize for the confusion and sincerely thank you for identifying the typos in the paper. You are correct that the loss is computed between $z_i$ and $c_i$, consistent with the vanilla VQ-VAE. We will correct these typos.

Regarding $\delta(\cdot)$ , it is a linear projection implemented by a basic fully-connected layer. We will refine the paper to provide better clarification.

W4: What’s the model performance when the pre-training domains are totally different from downstream tasks?

We thank the reviewer for raising this important point. We conducted experiments on two citation networks, Cora and Arxiv, and two molecule networks, HIV and PCBA. The results are shown below:

Even when the pre-training and downstream datasets are from different domains, there is no significant model degradation. For example, the model performance on Cora is 78.72 when pre-trained on citation networks and 78.46 when pre-trained on molecule networks. Additionally, the performance on PCBA is 78.43 when pre-trained on molecule graphs and 78.10 when pre-trained on citation networks.

W5: Why the token size is smaller than expected? What are tokens learn exactly?

One potential reason for the relatively lower number of tokens is the use of a prototype classifier. The construction of prototypes in this classifier involves combining different tokens in a memory bank, which can be interpreted as generating new tokens from previous tokens. In other words, the prototype classifier implicitly enlarges the vocabulary and enhances its diversity. Removing the prototype classifier degrades the average model performance from 79.92 to 78.06, while increasing the token size to 2048 provides only a marginal performance gain, reaching 80.38.

We also explored the meaning of tokens, as shown in Figure 1 of the attached PDF file in the general response. This figure reveals a set of tokens shared across datasets, each potentially maintaining general patterns across domains and tasks. Additionally, distinct tokens are used by individual domains or datasets, indicating domain-specific patterns. These well-separated tokens between different domains might provide a better source for the prototype classifier in creating prototypes.

W6: Comparison to VQGraph.

We thank the reviewer for the suggestion to compare our GFT to VQGraph and discuss their relation and differences. The major connection between GFT and VQGraph is the usage of vector quantization in learning a discrete vocabulary for downstream tasks. However, there are four major differences between GFT and VQGraph. (1) Model Objective: GFT focuses on building a general task reasoner, but VQGraph aims to train a structure-aware MLP for efficient inference. (2) Pretrain Dataset: GFT is pre-trained on cross-domain and cross-task datasets to acquire transferable patterns among graphs, but VQGraph is pre-trained on a single dataset to better capture the structural information. (3) Usage of Tokens: GFT treats tokens as specific transferable patterns, using them directly to build classifiers. VQGraph, on the other hand, treats tokens as external structural knowledge to complement the training of MLP classifiers. (4) Downstream Tasks: GFT can be applied to various graph-related tasks with different settings like few-shot and zero-shot learning. VQGraph is designed for node classification with a basic pre-training and fine-tuning setting.

W7: How GFT fits on with large graphs?

GFT can still use mini-batch to fit to a large graph. Given a large graph, we extract the mini-graph through mini-batch and use GNNs to encode the computation trees preserved on the mini-graph. Please refer to [W1] of general response for details.

Best regards,

The authors

Dear Reviewer M9ZQ,

Thank you for your comments and suggestions to improve our paper, we would like to check whether our response answers your questions. Following your comments, we provide detailed responses to your questions and present a comparison to VQGraph based on your recommendation. We look forward to your reply.

Dear Reviewer U8xo,

We appreciate the reviewer’s recognition of originality, quality, clarity, and significance of our work, and thank the reviewer for detailed feedback. We address your concerns as follows.

W1: Differences between computation trees and subgraphs.

Please refer to the [W1] in the general response.

W2: How $L_{feat}$ works?

$L_{feat}$ uses localized information to predict the original node features via a linear predictor. This can potentially model the positive or negative correlations between neighborhoods and the target node, corresponding to homophily and heterophily, respectively. Let $z$ be the learned embedding and $x$ be the raw features. If the neighborhood information is similar to the target node (homophily), the predictor might learn a nearly identical function since $z$ might be similar to $x$ . However, under heterophily, where $z$ and $x$ are far from each other, the linear predictor might learn a distinct mapping function to model such correlation. Empirically, [1] proposes a pre-training task similar to $L_{feat}$ and achieves desirable performance on node classification and graph classification. To elucidate this further, we provide a thorough ablation analysis to validate the effectiveness of $L_{feat}$ in our GFT:

The $L_{feat}$ is effective in node-level tasks (Arxiv) where papers tend to cite related papers, following the homophily principle. It also benefits link-level tasks (KG reasoning), where two entities sharing similar types of relationships may be connected. However, for graph-level tasks that may require a global understanding of patterns and motifs, $L_{feat}$ may be less important. Despite this, removing $L_{feat}$ still degrades model performance. These experiments emphasize the benefit of modeling the correlations between the local structures of a node and its features.

W3: What are decoders used for q projection?

The q projection is implemented by a basic fully-connected layer. We apologize for any confusion and sincerely thank you for identifying this issue. We will refine the paper to provide better clarification.

W4: How to handle the case that nodes are isomorphic but edges are not isomorphic.

We greatly appreciate this insightful feedback. Similar to previous GFMs with basic GNN encoders [2, 3], our GFT cannot enhance model expressiveness to handle such link-level isomorphism. However, this limitation arises primarily due to the limited expressiveness of the backbone model (GraphSAGE) rather than our model design, and thus does not significantly impair the contribution of the overall framework. We can address this issue by using more expressive GNN backbones as described in [4]. Moreover, such conditions may not always occur in real-world applications with rich node attributes, where two nodes are less likely to have the same embeddings, thereby preventing node isomorphism.

W5: What is the definition of R(f)?

The definition of R(f) is related to the VQ operation. Specifically, VQ clusters the input vectors by measuring the distance between the input vectors and token vectors in the vocabulary, where the process can be interpreted as a margin-aware prototype classifier $f$ [7]. The classifier $f$ aims to classify the inputs into their latent clusters $y$ , and the predictions are denoted as $\hat{y}$. Based on that, R(f) measures the risk of the classifier $f$. Note that this analysis is based on the extension of the latent variable assumption, a general assumption in statistics and machine learning that variables are sampled from a latent distribution, where each input is assigned a label indicating its latent cluster.

W6: What’s the impact of the comprehensive loss functions? What will happen if computation trees are replaced by subgraphs?

GFT surpasses baselines even with a single loss function, and replacing computation trees with subgraphs impairs model performance. We select two basic baselines, including GAT and GraphMAE, and implement a subgraph version of GFT (GFT - Subgraph) following [6]. We further extend our comprehensive objective to the subgraph version (GFT - Subgraph + Our Task) as another baseline. The results are as follows:

The results demonstrates the benefit of using computation trees even without a comprehensive loss function, referring to Impact of Loss Functions. When the computation trees are replaced by subgraphs, the model performance degrades even with our comprehensive tasks, further supporting the advantage of using computation trees as basic patterns.

W7: Zero-shot learning.

Please refer to [W2] in the general response.

Best regards,

The authors

Reference:

[1] Hou, et al., GraphMAE: Self-Supervised Masked Graph Autoencoders, KDD, 2022.

[2] Liu, et al., One For All: Towards Training One Graph Model for All Classification Tasks, ICLR, 2024.

[3] Huang, et al., PRODIGY: Enabling In-context Learning Over Graphs, NeurIPS, 2023.

[4] Mao, et al., Graph Foundation Models are Already Here, ICML, 2024.

[5] Crammer, et al., Margin analysis of the LVQ algorithm, NeurIPS, 2002.

[6] Sun, et al., All in One: Multi-Task Prompting for Graph Neural Networks, KDD 2023.

Dear Reviewer U8xo,

Thank you for your comments and suggestions to improve our paper, we would like to check whether our response answers your questions. Following your comments, we comprehensively discuss the relations and differences between computation trees and subgraphs and provide an extensive quantitative study. We look forward to your reply.

Thanks for your constructive comments and for raising your score! Your review is really supportive of our work!

Dear Reviewer H6gM,

We greatly appreciate your acknowledge of our contribution and insightful feedback to help us refine our work. We address your concerns as follows:

W1: Is there any other structures transferable? How to demonstrate what tokens learn exactly?

Yes, there are other transferable structures. While we did not provide additional visualized examples due to the inherent complexity of graphs, we utilized the Weisfeiler-Lehman (WL) subtree kernel to directly measure the presence of such transferable structures across two graphs. Our experimental results (Figure 3 and Table 1) demonstrate a positive correlation between transferability and the WL subtree kernel value.

Additionally, each token in the vocabulary represents the embedding of certain transferable structures. To elucidate the potential meaning of these tokens, we propose measuring the density of token usage across different datasets. This approach is illustrated in Figure 1 of the attached PDF in the general response. In this figure, we observe a set of tokens used by all datasets, suggesting they capture general and transferable structures across graphs. Furthermore, some tokens are shared within specific domains or datasets, indicating they maintain domain-specific patterns. It is important to note that our visualization represents an initial step towards understanding the transferable patterns on graphs. Your review has inspired us to further explore this direction in our future work.

W2: Zero-shot learning setting

We appreciate your suggestion for a comparison of zero-shot learning. Recognizing the importance of zero-shot scenarios for graph foundation models, we have implemented a zero-shot version of our model, GFT. Following current promising approaches [2-4], we use an additional LLM as the task reasoner, utilizing the learned embedding and specific prompts as input. Specifically, we follow the design in [4], using an MLP projector to map the learned embedding and fine-tuning the LLMs with LoRA.

We compare GFT with four baselines that also use LLM reasoners. Models such as GraphGPT [2] and LLAGA [3] focus on single tasks, converting node features and graph substructures for LLM processing. OFA [1] treats subgraphs as transferable patterns and applies graph prompt learning for zero-shot learning, although its performance is limited. Therefore, we implemented an LLM-based OFA (OFA + LLM) similar to our method (GFT + LLM). The results are presented below, with “*” indicating a slightly different experimental setting, such as different pre-training datasets.

The advantage of the baseline methods (GraphGPT, LLAGA) is primarily due to their pre-training on a single dataset (or datasets from the same domain), allowing them to learn domain-related patterns for downstream tasks. In contrast, OFA and our GFT are pre-trained on cross-domain and cross-task graphs, acting as general reasoners over graphs. Specifically, the basic OFA’s performance is relatively lower without directly leveraging the power of LLMs in reasoning. However, when using LLMs as reasoners, OFA’s performance significantly improves, though it remains lower than our GFT. This indicates the potential of using computation trees as transferable patterns in learning generalized embeddings.

Best regards,

The authors

References:

[1] Liu, et al., One For All: Towards Training One Graph Model for All Classification Tasks, ICLR, 2024.

[2] Tang, et al., GraphGPT: Graph Instruction Tuning for Large Language Models, SIGIR, 2024.

[3] Chen, et al., LLaGA: Large Language and Graph Assistant, ICML, 2024.

[4] He, et al.,UniGraph: Learning a Cross-Domain Graph Foundation Model From Natural Language, Arxiv, 2024.

Dear Reviewer H6gM,

Thank you for your comments and suggestions to improve our paper, we would like to check whether our response answers your questions. Following your comments, we provide more analysis on transferable structures and conduct experiments on zero-shot settings. We look forward to your reply.