Towards Graph Foundation Models: Learning Generalities Across Graphs via Task-Trees

We thank the reviewer for acknowledging the soundness of our theoretical claims, evaluation criteria, and experimental setup. We address each point in detail below and are committed to improving clarity and rigor in future revisions.

More Related Works and Comparative Results

We thank the reviewer for this valuable comment. In response, we have expanded both the discussion and experiments to include several recent and relevant graph foundation models. Below is the updated discussion:

GraphPrompt [6] is the first graph prompt learning method that aligns graph tasks to subgraph-level tasks by extracting subgraphs for each graph instance. GraphPrompt+ [1] builds upon this by incorporating additional pretraining tasks and a more generalizable prompt design, enhancing the model’s ability to capture hierarchical information. All in One [2] further advances this line of work by introducing a learnable graph template and meta-learning techniques to better align pretraining with downstream tasks. OpenGraph [3] proposes a unified graph tokenizer and a scalable transformer to address token and structural differences across graphs, also leveraging LLM-based knowledge distillation to mitigate data scarcity. AnyGraph [4] extends OpenGraph by incorporating a Mixture-of-Experts (MoE) mechanism to handle feature and structure heterogeneity, using SVD for node feature alignment. Lastly, SAMGPT [5] introduces a prompt-based approach designed specifically for non-textual graphs, aligning both node semantics and structural knowledge. While most of these models aim to address multiple challenges in building graph foundation models, GIT focuses specifically on task alignment, similar in spirit to GraphPrompt, but with a novel formulation using task-trees.

To demonstrate the benefits of GIT, we conducted experiments comparing it against GraphPrompt+ [1], All in One [2], OpenGraph [3], and AnyGraph [4]. We exclude GraphPrompt [6] as it has been superseded by GraphPrompt+, and SAMGPT [5] due to its focus on non-textual graphs and the unavailability of official implementation. Nonetheless, we include both in the extended discussion.

We evaluate GIT-G and baselines across three domains—academic (node classification), knowledge graphs (edge classification), and molecules (graph classification)—under the pretrain-then-finetune setting. As shown below, GIT-G consistently outperforms all recent baselines.

[1] Generalized Graph Prompt: Toward a Unification of Pre-Training and Downstream Tasks on Graphs, TKDE 24.

[2] All in One: Multi-task Prompting for Graph Neural Networks, KDD 23

[3] OpenGraph: Towards Open Graph Foundation Models, EMNLP 24

[4] AnyGraph: AnyGraph: Graph Foundation Model in the Wild, Arxiv 24

[5] SAMGPT: Text-free Graph Foundation Model for Multi-domain Pre-training and Cross-domain Adaptation, WWW 25

[6] Graphprompt: Unifying pre-training and downstream tasks for graph neural networks, WWW 23

This paper is far from graph foundation models.

We appreciate this important point. Actually, we apply two light-weight approaches to solve these two challenges. We address feature heterogeneity by using text-attributed graphs, where textual descriptions are encoded via a text encoder to align node features. For structural heterogeneity, we design a regularizer (see Appendix B.2) to encourage structural consistency across graphs.

That said, we would like to emphasize that the primary focus of our work is on addressing task heterogeneity, rather than simultaneously tackling all challenges of graph foundation models. By focusing on this aspect, we are able to clearly isolate and demonstrate the effectiveness of task-trees for aligning node-, edge-, and graph-level tasks. However, for better readability, we will revise some statements to make the expression more precise.

The contribution of introducing task trees is limited.

Thank you for raising this concern. We would like to clarify that our major contribution lies in the theoretical foundation we provide for task-trees. To the best of our knowledge, this is the first work that formally derives theoretical results on handling task heterogeneity across graphs. Our analysis includes stability guarantees, transferability, and generalization bounds, providing a principled foundation for this new formulation. We believe this significantly advances the understanding of task alignment in graph learning.

We sincerely thank the reviewer for their thorough and thoughtful feedback. We appreciate the recognition of our contributions and also value the constructive suggestions. We address each point in detail below.

Theory

Q1: Imprecise Task-Tree Generality Assumption

A1: The generalities means the common substructures shared across graphs, as tree structure naturally serve as an approximation of substructure patterns. However, discovering exact common substructures is intractable due to the variety of graph data. We will revise the assumption for greater clarity.

Q2: Concerns about generalization bound

A2: It is true that graph data at the node level can violate the i.i.d. assumption due to inter-node dependencies. However, in our formulation, each task-tree is treated as an independent training instance. We assume that task-trees are i.i.d. sampled from a uniform distribution over the tree space, which makes the PAC-style generalization analysis applicable in our setting. We will explicitly add this assumption in the revised manuscript for clarity.

Q3: Domain shift in Theorem 3.3

A3: Theorem 3.3 are derived under the standard assumption that the pretraining (source) and downstream (target) task distributions are not completely disjoint. This reflects a core principle of transfer learning—there must be some semantic alignment between domains. Without such overlap, negative transfer can occur, where a pretrained model may underperform compared to one trained from scratch. We agree that in cases of severe domain shift, the bound may become loose or even vacuous. This is a known limitation of theoretical transfer bounds, which inherently depend on distributional similarity. We will revise the discussion to explicitly state this assumption and implications.

More Related Works

We have included the discussion: GCOPE addresses challenges in cross-domain graph pretraining by applying SVD for feature alignment and introducing virtual coordinator nodes to unify graph structures. It is designed for handling feature heterogeneity across graphs on node classification, whereas our method focuses on aligning different tasks (handling task heterogeneity) on graphs.

We run experiments to compare GCOPE and GIT-G on academic datasets. Both models are pretrained on Arxiv, Arxiv-23, and DBLP, and finetuned on Cora, Citeseer, and Pubmed. GIT-G achieves better performance on two out of three datasets.

Why use TAGs in experiments?

Our method does not rely on TAGs. We use TAGs because they allow node features to be aligned through a textual encoder. Since our primary contribution is a framework for addressing task heterogeneity, TAGs help us isolate this aspect by minimizing the confounding effects of feature heterogeneity. This design choice allows us to more clearly demonstrate the effectiveness of task-trees in aligning tasks across different levels.

Importantly, our method is fully applicable to non-textual graphs as well. To show this, we introduce a simple SVD-based module to align features across graphs. We pretrain the model on purely non-textual datasets—PubMed (node classification), Citeseer (link prediction), and IMDB-B (graph classification)—and finetune on Cora (link prediction), as shown below.

Additional Experiments

Q1: Heterophily Graphs

A1: We have already included heterophily graphs in our experiments (Table 15). Specifically, the Children and Ratings datasets in the e-commerce domain have homophily ratios of 0.42 and 0.38, respectively—lower than other datasets (greater than 0.60). GIT-G outperforms baselines on these heterophily graphs.

Q2: Few-shot Learning

A2: We evaluate GIT-G in few-shot learning settings within the academic domain, averaged over six graphs. We observe that increasing the number of shots significantly improves performance. GIT-G consistently outperforms GraphMAE across all settings, likely due to its ability to better transfer knowledge across domains via task-trees.

Visualization: Node Count

We have revised the figure to indicate that more nodes exist, using dotted edges to clarify that the figure is a partial illustration.

We sincerely thank the reviewer for the positive and encouraging feedback. We appreciate the recognition of our contributions in theory, methodology, and experimentation, as well as the thoughtful questions regarding model efficiency and fair comparisons—we have addressed these points in detail below.

The authors claim efficiency of task-tree based model compared to subgraph-based methods. How does this work? It is better to provide any complexity analysis and experiment to support this claim.

We appreciate the reviewer’s comment and the opportunity to clarify. Both subgraph-based and task-tree-based methods require GNNs for encoding. However, the computational bottleneck in subgraph-based approaches lies in the explicit extraction of subgraphs. Assuming a graph with $n$ nodes, extracting subgraphs using adjacency matrix-based BFS incurs a time complexity of $O(n^3)$. In contrast, our task-tree-based approach augments the original graph by appending virtual nodes, avoiding subgraph extraction. The time complexity of this augmentation is linear with respect to the number of nodes, edges, or graphs, depending on the task, making it efficient in practice.

Empirically, we have provided a runtime and memory comparison in Figure 4. Specifically, we implemented GIT-SubG, a variant of our model that replaces task-trees with subgraphs. Below is the comparison of time per epoch and GPU memory usage during pretraining (on ~1.7 million instances) between GIT-Task-Tree and GIT-SubG. For reference, GraphMAE, using a batch size of 2048, requires 193 seconds per epoch and 35% memory allocation on a 48GB GPU.

The model GIT-S includes a supervised fine-tuning step and outperforms all models. For a fair comparison, it is necessary to compare the results of the baseline methods with the same step.

Thank you for this insightful comment. We agree and have already included the fair comparison in Table 3 of the paper. Below is a summary of the results on academic networks, showing performance across three settings: 0-shot, 3-shot, and finetuning. As shown, specialization through fine-tuning improves performance for all models. Notably, GIT outperforms both GraphMAE and OFA in both general and specialized forms across all evaluation settings.

We sincerely thank the reviewer for the thoughtful and constructive feedback. We are encouraged by the positive recognition of our contributions, including the unified task-tree representation, theoretical grounding, and strong empirical performance across diverse settings. In the following, we address each comment point-by-point.

More comparing results

We thank the reviewer for this valuable comment. In response, we have updated our experiments to include several recent and relevant graph foundation models, including GraphPrompt+ [1], All in One [2], OpenGraph [3], AnyGraph [4]. We compare our GIT-G to these method across three domains, including academic (node classification), knowledge graph (edge classification), and molecules (graph classification), in the pretrain-then-finetune setting, where our GIT-G consistently outperforms these recent baselines. The results are shown in the following table.

[1] Generalized Graph Prompt: Toward a Unification of Pre-Training and Downstream Tasks on Graphs, TKDE 24.

[2] All in One: Multi-task Prompting for Graph Neural Networks, KDD 23

[3] OpenGraph: Towards Open Graph Foundation Models, EMNLP 24

[4] AnyGraph: AnyGraph: Graph Foundation Model in the Wild, Arxiv 24

Discussion on node-of-interest and graph prompt

We appreciate the reviewer’s comment and the opportunity to clarify the distinction. As discussed in Section 2.3 of our paper, our proposed method is fundamentally different from node-of-interest (NOI) and graph prompt-based approaches, such as All in One [2] and OFA [1], which rely on subgraph extraction paradigms.

Specifically, All in One constructs task-specific subgraphs (e.g., ego-graphs centered on task-relevant nodes) and then applies GNNs to these subgraphs. Similarly, OFA formalizes the concept of NOI to further unify various tasks, but it ultimately follows the same principle—extracting and operating on subgraphs derived from nodes of interest.

In contrast, our method introduces task-trees, which are more efficient and learnable structures that augment the original graph rather than extract subgraphs. Task-trees provide an efficient and learnable way of encoding task semantics. This difference is empirically validated in our paper (Table 4 and Figure 4), and further supported by the updated results shown above, where GIT-G consistently outperforms subgraph-based baselines.

Questions about the textual encoder.

Q1: Does the method rely on text encoder?

A1: No, the method does not necessarily rely on a text encoder. We use text-attributed graphs in our experiments to focus solely on our main contribution—handling task heterogeneity—and avoid introducing additional components for addressing feature heterogeneity. Textual attributes allow node features across graphs to be aligned using a textual encoder, helping us isolate and demonstrate the effectiveness of task-tree generalization.

Q2: Can the method be applied to non-text-attributed graphs?

A2: Yes, our method can be applied to non-text-attributed graphs. To demonstrate this, we introduced a simple module to handle feature heterogeneity by applying SVD to align features into a shared space. We pretrain on pure non-textual graphs—PubMed (node classification), Citeseer (link prediction), and IMDB-B (graph classification)—and finetune on Cora (link prediction). The results, reported below using AUC as metric, show that GIT-G remains effective without textual attributes.

Q3: The task-tree generality assumption is only validated on text-attributed graphs.

A3: As shown in the discussion and results above, our method is generalizable to both text-attributed and non-text-attributed graphs. Therefore, the task-tree generality assumption does not depend on the presence of text information.

The ablation on textual encoder

We further evaluate the impact of different textual encoders on model performance, including MiniLM, MPNet, and SentenceBERT (our default choice), on the academic domain in the finetuning setting.