Foundation models have emerged as a cornerstone of general-purpose machine learning, enabling cross-task and cross-domain generalization. Representative examples include large language models (LLMs) for text (Achiam et al., 2023;Touvron et al., 2023) and large vision models (LVMs) for images (He et al., 2022;Yuan et al., 2021). Pretrained on massive datasets, these models capture trans-ferable patterns-such as contours and textures in images, or tokens and sentences in text-that reflect modality-specific generalities. This broad knowledge base allows for efficient adaptation to downstream tasks via in-context learning (Xie et al., 2022;Chen et al., 2024c) and zero-shot generalization (Wei et al., 2021).
Despite the success of foundation models in text and vision, their extension to graph-structured data remains nascent (Liu et al., 2024a), primarily due to the high variability across graph datasets (Mao et al., 2024). Graphs from different domains often encode distinct phenomena-e.g., social networks model human relationships (Freeman, 2004), whereas molecular graphs represent chemical structures (Zeng et al., 2022)-leading to both feature (Wang et al., 2024b) and structural heterogeneity (Qiu et al., 2020;Wang et al., 2024c). Crucially, graph tasks operate on different learning units, such as nodes, edges, or entire graphs, limiting cross-task compatibility within a unified model (Wang et al., 2024b). These challenges hinder the development of graph foundation models capable of capturing transferable generalities. In this work, we specifically address the challenge of task heterogeneity.
Is it possible to identify cross-task generalities across graphs? Despite inherent challenges, prior work has explored this question via two main approaches. (1) A graphtheoretic perspective employs the concept of graphons (Ruiz et al., 2020) to model transferable patterns across graphs. If graphs are sampled from the same graphon, they are expected to share structural properties, enabling effective transfer (Ruiz et al., 2020;Cao et al., 2023). However, graphon-based methods rely on strong generative assumptions that rarely hold in real-world settings (Levie et al., 2021), and inferring a shared graphon from diverse graphs remains computationally intractable. (2) A substructurebased perspective seeks recurring motifs-such as triangles, stars, or k-cliques-across domains (Zhao et al., 2023;Mao et al., 2024). These motifs appear in various contexts (e.g., social, citation, and molecular networks), motivating methods that sample subgraphs consisting of substructures and encode them via GNNs (Sun et al., 2023;Liu et al., 2024a). However, message-passing GNNs are fundamentally limited in capturing such substructures (Garg et al., 2020;Esser et al., 2021;Zhang et al., 2024a), restricting their efficacy in learning transferable subgraph representations.
Given the limitations of prior approaches, we introduce a novel perspective centered on the learning dynamics of message-passing GNNs (Kipf & Welling, 2017;Hamilton et al., 2017). In such models, predictions are made based on task-relevant nodes: the target node in node-level tasks, edge endpoints in edge-level tasks, and all nodes in graphlevel tasks (Srinivasan & Ribeiro, 2020). Regardless of task type, GNNs aggregate embeddings over these task-relevant nodes, which can be conceptualized as introducing a virtual task node connected to all task-relevant nodes. We define the computation tree rooted at this virtual node as a tasktree (Figure 1). Task-trees offer three key advantages: (1) Learnability: tree-structured information can be effectively captured by message-passing GNNs (Gupta et al., 2024); (2) Uniformity: task-trees apply seamlessly across node-, edge-, and graph-level tasks, mitigating task heterogeneity; (3) Efficiency: encoding task-trees operationally equals to encoding the virtual nodes appended to original graphs. Analogous to images in vision or sentences in language, task-trees serve as unified learning instances and may encode transferable patterns across graph tasks, leading to the assumption:
Task-Tree Generality Assumption. The generalities shared across graphs are (at least partially) preserved within the task-trees of the involved graphs.
To evaluate this assumption, we conduct a theoretical analysis of task-trees with respect to stability, transferability, and generalization. Our main result shows that pretraining a GNN on diverse task-trees via a reconstruction objective yields transferable representations that adapt well to downstream tasks with moderate fine-tuning. Furthermore, the model can be specialized to specific domains via posttraining (Wei et al., 2021) on domain-specific task-trees.
To empirically validate our theoretical insights, we introduce Graph Generality Identifier on Task-Trees (GIT), a graph foundation model pretrained on task-trees extracted from diverse graphs spanning multiple domains and tasks. GIT is evaluated on 32 graphs across 5 domains under three paradigms: fine-tuning, in-context learning (few-shot without fine-tuning), and zero-shot learning. Results show that pretraining on a small set of graphs significantly improves performance on a broad range of downstream tasks, supporting the hypothesis that task-trees capture transferable generalities. Additionally, we propose an instruction tuning method to adapt the general model to specific domains, yielding performance comparable to or exceeding domainspecific expert models. Our key contributions are:
• We introduce task-trees as unified learning instances for aligning heterogeneous graph tasks, demonstrating advantages over conventional units such as subgraphs.
• We present the first theoretical framework addressing task heterogeneity in graph learning, establishing the effectiveness of task-trees for cross-task generalization.
• We propose GIT, a graph foundation model pretrained on task-trees to acquire generalizable knowledge and support domain specialization.
• Extensive experiments across 32 graphs and five domains validate the effectiveness of GIT under finetuning, in-context, and zero-shot settings.
2. Task-Trees: Rethinking Basic Learning Instances on Graphs
We begin with a brief introduction to message-passing GNNs and some related concepts. Let G = (V, E) represent a graph with node set V and edge set E, where each node v ∈ V is associated with a feature vector x ∈ R d .
A GNN encoder ϕ takes the graph as input and performs message passing to learn node embeddings Z = ϕ(V, E). Specifically, a GNN encoder can be defined as:
where N i denotes the 1-hop neighbors of node i, z (l) represents the node embedding at the l-th GNN layer with z (0) = x, and W 1 , W 2 are learnable matrices. The functions σ, ρ, and g are the activation function, aggregation function and update function, respectively. To simplify the analysis, we assume ρ is an averaging operation and g is the identity function. Without loss of generality (WLOG), these functions can be replaced with any permutation-invariant and Lipschitz-continuous functions, respectively, without affecting the analysis in the paper. Definition 2.1 (Task-Relevant Nodes). Graph tasks can be roughly categorized into node-level, edge-level, and graphlevel tasks, where the basic learning instances are nodes, edges, and entire graphs, respectively. For node classification, the task-relevant node v t i is the node to be classified. In edge classification, the task-relevant nodes are the start and end nodes {v t i , v t j } of the target edge e ij . For graph classification, the task-relevant nodes {v t i }
i=1 include all nodes in the target graph G.
For any graph task instance, the prediction relies solely on the embeddings of the corresponding task-relevant nodes. These node embeddings capture the surrounding subtree structures, which are also known as computation trees. Definition 2.2 (Computation Trees (Chuang & Jegelka, 2022)). Given a node v in graph G, the L-layer computation tree T L v is constructed by recursively expanding the subtrees of its neighboring nodes, starting with T 1 v = v.
The learning process of message-passing GNNs can be interpreted as recursive aggregation over computation trees, where the representation of a node v produced by an L-layer GNN corresponds to the embedding of its L-hop computation tree T L v . Since predictions in graph tasks rely exclusively on the embeddings of task-relevant nodes, and those embeddings are determined by their respective computation trees, we construct a unified task-tree for each learning instance-whether a node, edge, or entire graph-by merging the relevant computation trees, as illustrated in Figure 1. Definition 2.3 (Task-Trees). For any graph instancewhether a node, edge, or graph-we have a set of taskrelevant nodes {v t 1 , ..., v t n } and their corresponding L-layer computation trees {T 1 , ..., T n }. These computation trees can be reformulated into a larger task-tree T t by introducing a virtual node that connects all task-relevant nodes.
To encode a task-tree, we adopt a simple yet effective aggregation strategy. Given a task-tree T t composed of a virtual node v t and task-relevant nodes {v t 1 , . . . , v t n }, we compute its representation using a MEAN aggregator over the embeddings of the individual computation trees:
where T i denotes the computation tree rooted at v t i , and ϕ is a shared GNN encoder. This representation serves as the input for downstream objectives such as reconstruction, classification, or alignment.
Unlike our proposed task-trees, several existing approaches (Qiu et al., 2020;Sun et al., 2023;Huang et al., 2023;Liu et al., 2024a;He & Hooi, 2024) utilize k-hop subgraphs extracted from graphs as the basic learning instances. For instance, in node classification, ego-graphs are constructed around each node, where the label of the central node is assigned to the induced subgraph, effectively reformulating node classification as a subgraph classification task. A similar transformation can be applied to edge-level and graph-level tasks by converting them into subgraph-level learning problems. This method involves: (1) extracting ego-graphs centered around task-relevant nodes and (2) applying GNNs to learn graph-level embeddings for classification. However, this subgraph extraction process incurs substantial computational overhead, increasing both time and memory requirements due to the necessity of storing and processing induced subgraphs. Moreover, information within these subgraphs is not always effectively captured by message-passing GNNs, as GNNs may struggle to learn essential substructures preserved in graphs (Garg et al., 2020;Chen et al., 2020;Zhang et al., 2024a), thereby limiting the efficacy of subgraphs as learning instances. In contrast, our proposed task-trees offer both greater efficiency and improved learnability (Table 1). Specifically, encoding task-trees for node, link, or graph-level tasks involves: (1) augmenting the original graph by adding virtual task nodes and connecting them to task-relevant nodes and
(2) applying GNNs over the augmented graph to encode the embeddings of these virtual nodes for prediction. For example, in node classification, we first introduce virtual nodes connected to each node in the original graph and subsequently apply GNNs to this augmented structure, allowing virtual node embeddings to be learned for classification. Consequently, our method requires only the addition of nodes and edges to the existing graph, making it significantly more efficient than extracting and storing subgraphs. Furthermore, encoding task-trees is equivalent to directly encoding virtual nodes through message passing, ensuring that task-tree information remains fully learnable by standard GNNs. Empirically, task-trees consistently outperform subgraphs in both effectiveness and efficiency (Section 5.6 and Appendix I).
The most closely related work to our task-tree framework is GFT (Wang et al., 2024b), which introduces computation trees to align heterogeneous graph tasks. While both approaches share the core intuition of structuring task-specific trees, GFT adopts a model-centric perspective, featuring a learnable vocabulary, a multi-faceted reconstruction objective, and specialized adaptation classifiers. In contrast, our task-tree framework is theory-driven and emphasizes the design of learning instances rather than model complexity. Notably, GFT empirically demonstrates the potential of computation trees for transferability, while our work complements it with a formal theoretical foundation, offering a principled understanding of task alignment in graph learning. Together, these works represent complementary advances toward general-purpose graph foundation models. We present additional discussions on related work in Appendix A.
In this section, we present a theoretical analysis of task-trees, focusing on their stability, transferability, and generalization as foundational learning instances. This analysis provides formal support for the Task-Tree Generality Assumption, which posits that transferable patterns across graph tasks are preserved within task-tree structures.
Our goal is not to assert the universal superiority of tasktrees over other learning units such as subgraphs, but rather to establish the theoretical plausibility of using task-trees to capture cross-task generalities. By grounding the construction and use of task-trees in formal guarantees, we lay the foundation for principled pretraining and transfer learning across heterogeneous graph tasks.
We begin by examining the stability of GNNs in learning task-tree representations, showing that task-trees with similar subtree structures produce analogous embeddings. To facilitate this analysis, we first define the notation for describing subtree information:
(0) i = x i denotes the original node feature, and x (l) denotes the subtree information of nodes in l-th layer, as illustrated in Figure 2. In this figure, for l = 1, only the nodes in the first layer of the tree are considered, and for l = 2, only the nodes in the second layer are considered. Theorem 3.1 (Stability on Task-Trees). Given two L-layer task-trees T 1 t and T 2 t , with task-relevant nodes {v 1 , ..., v n } and {v 1 , ..., v m }, respectively. The distance between tasktrees is defined as
where ϕ is the GNN encoder, T i is the computation tree corresponding to node i, and C 1 , C 2 are constants related to the encoder, and B x represents the bounded norm of x.
Theorem 3.1 (proved in Appendix D.1) suggests that two task-trees are likely to have similar representations if their subtrees are similar. This theorem highlights the significance of similarity between pairs of subtrees, while downplaying the impact of the number of subtrees (i.e., the width of the task-trees), despite having more subtrees could potentially increase diversity and thus magnify discrepancy. The theorem also implies that increasing the number of GNN layers may lead to a loose bound, which aligns with previous analyses (Garg et al., 2020;Ju et al., 2023a).
Illustration 3.2. This theorem provides theoretical support for using task-trees as basic learning instances in graph tasks. Consider two task-trees: one representing a node (with a single subtree) and the other representing a graph
Avg.
𝑥 (") 𝑥 ($) Avg.
Avg. Avg. (with multiple subtrees). While the widths of these task-trees differ significantly, if their subtrees share some degree of similarity, they can produce similar representations. Thus, this theorem ensures that task-trees of nodes, edges, or graphs can potentially be similar, making it possible to use a GNN encoder to capture the shared patterns among them.
We now examine the transferability of task-trees. Specifically, assuming a model is pretrained on a task-tree reconstruction taskfoot_2 , we aim to quantify how the knowledge acquired during pretraining can be transferred to downstream tasks. The pretraining objective is defined as L P (g • ϕ) := E ( T ,T )∼P ∥g(ϕ( T )) -ϕ(T )∥ 2 , where P represents the task-tree distribution used for pretraining, ϕ ∈ Φ and g ∈ G are the GNN encoder and the reconstruction head, respectively. T denotes the task-tree and T is the corrupted version of T , generated using arbitrary augmentations. Note that the reconstruction head g is used only during pretraining and is discarded during fine-tuning. Then, we define the risk on downstream task as R T (f • ϕ) := E (T,y)∼T κ(f (ϕ(T )), y), where f ∈ F is a linear head for predictions, T represents the downstream task distribution with task-tree T and label y, and κ denotes the loss function.
Theorem 3.3 (Transferability on Task-Trees). Given two task-tree encoders ϕ, ϕ ′ ∈ Φ, we have
where C δ ≈ O(1) and δ = 1 2 .
The proof is provided in Appendix D.2. In summary, Theorem 3.3 demonstrates that knowledge gained through pretraining on task-tree reconstruction tasks is transferable to downstream tasks, and it quantifies the extent of this transfer. The left-hand side (LHS) of the theorem shows how different representations impact performance on downstream tasks, while the right-hand side (RHS) reflects the difference in pretraining losses between two encoders. Therefore, if two encoders exhibit similar losses during pretraining, their transferability to a new task should be comparable.
Illustration 3.4. To give a better understanding on why Theorem 3.3 imply the model pretrained on task-trees can bring transferable information to downstream tasks, we present an example. Let's consider the case where ϕ is the pretrained encoder and ϕ ′ is a randomly initialized encoder. The LHS term
) measures the amount of knowledge that is acquired during pretraining and is capable to be transferred to downstream tasks, and the RHS term min g∈G L P (g • ϕ) -min g ′ ∈G L P (g ′ • ϕ ′ ) measures the total knowledge acquired during pretraining. Thus, the constants C δ and δ quantify how much of this knowledge is transferable to downstream tasks. Since both C δ and δ are reasonably small, we conclude that pretraining on task-trees provides sufficient knowledge to benefit downstream tasks.
To further explain why the task-tree-based pretraining and fine-tuning framework is effective for downstream tasks, we derive the following generalization bound.
Theorem 3.5 (Generalization on Task-Trees). Given two task-tree distributions, P for pretraining and T for finetuning, suppose the encoder ϕ is pretrained on a set of task-trees {T i } m i=1 sampled from P and finetuned on tasktrees {T i } n i=1 sampled from T , the generalization bound of the finetuned model, with probability at least 1 -v, is
where ϕ * = arg min ϕ∈Φ min g∈G L P (g • ϕ) is the optimal task-tree encoder obtained on P, E P (g, ϕ) = L P (g • h)min g ′ ∈G,ϕ ′ ∈Φ L P (g ′ • ϕ ′ ) defines the excess risk during pretraining. Constants C 1 and C 2 are related to downstream tasks, while C δ ≈ O(1) and δ = 1 2 are the same as Theorem 3.3. X ϕ denotes the distribution of task-tree embeddings encoded via ϕ, and ∥T ϕ (x) -P ϕ (x)∥ measures the distance between task-tree distributions of pretraining and fine-tuning data.
The proof can be found in Appendix D.3. This theorem outlines key factors affecting model generalization on downstream tasks, such as the transferability of task-trees (C δ (E P (g, ϕ)) δ ) and the quality of the pretrained encoder (E P (g, ϕ)). With regard to the number of task-trees, we find that while increasing the number of fine-tuning samples contributes to more stable optimization ( 4C1 n n i=1 ∥ϕ(T i )∥ 2 ), it does not significantly reduce the generalization bound
). This provides theoretical evidence that a reasonable number of fine-tuning samples can be sufficient for training a model with strong generalization capabilities. Moreover, the discrepancy between the pretraining and fine-tuning distributions ( x∈X ϕ ∥T ϕ (x) -P ϕ (x)∥) is crucial-smaller distribution gaps lead to better generalization. This highlights the importance of increasing the diversity of pretraining data, which provides a boarder pretraining distribution P. It also supports the potential of developing specialized models for specific domains based on a pretrained general model, discussed in Section 4.2.
The theoretical analysis establishes the feasibility of constructing graph foundation models based on task-trees. Building on these insights, we develop the GIT model to empirically validate the Task-Tree Generality Assumption.
To focus on aligning task spaces across heterogeneous graph tasks, we adopt widely used text-attributed graph benchmarks (Chen et al., 2024b;Zhang et al., 2024b;Feng et al., 2024), which simplify feature alignment across datasets. Specifically, we follow Liu et al. (2024a) and encode all node features into a shared 768-dimensional embedding space using Sentence-BERT (Reimers & Gurevych, 2019). This design allows us to isolate and examine the effect of task-tree-based pretraining while holding node features consistent across domains.
We propose a task-tree reconstruction task as a pretext for pretraining. The key is to use two corrupted task-trees to reconstruct each other, thereby capturing corruptioninvariant semantics. Given a set of task-trees {T t 1 , ..., T t n } sampled from a graph database, we apply corruption techniques to generate two views of each task-tree, denoted as { T t 1 , ..., T t n } and { T t 1 , ..., T t n }. For corruption, we use random edge masking and random attribute masking (Zhu et al., 2020;Wang et al., 2025c) due to its computational efficiency. We then use an encoder ϕ to obtain embeddings for the corrupted task-trees, resulting in { ẑ1 , ..., ẑn } and { z1 , ..., zn }. Inspired by (Thakoor et al., 2022), we perform reconstruction as
where g is a non-linear MLP projector, ρ(z) = (z/∥z∥) serves for normalization, sg is the stop-gradient operation, and h is the average of all instances z. The reconstruction loss captures the semantics of the task-trees in a predictive manner, while the KL regularizer ensures the embeddings are projected into a shared space by minimizing the KL divergence between individual instances and their center.
Theorem 3.5 highlights the relationship between model generalization and the distribution gap between pretraining data P and fine-tuning data T , showing that a smaller gap leads to better generalization. Based on this finding, it is feasible to develop a specialized model for specific domains from a pretrained general model. This is based on the mild assumption that graphs from the same domain have similar task-tree distributions {T 1 , .., T n }. If the pretrained model is post-trained on a task-tree distribution P post sampled from {T 1 , .., T n }, the pretraining data distribution P can be adjusted towards these task-tree distributions. This reduces the discrepancy x∈X ϕ ∥T ϕ (x) -P ϕ (x)∥ in Theorem 3.5, thereby improving model generalization on the target domain. To achieve this, we propose an instruction-tuning method for post-training the pretrained model.
Instruction tuning is a supervised fine-tuning (SFT) technique designed to enhance the capabilities of a pretrained model by post-training it on a small dataset. Our goal is to fine-tune the model using instructions to specialize it for a particular domain of interest. Given a pretrained model ϕ * and a set of task-trees {T 1 , ..., T n } from the target domain, we post-train the model using the SFT loss:
where ψ is the instruction generation function for each tasktree, and κ is the corresponding loss function. In this paper, as we use text-attributed graphs in our experiments, we define instructions as the embeddings of label descriptions encoded by a LLM, which is similar to Liu et al. (2024a), and we use mean squared error as the loss function κ. Additional model analysis is provided in Appendix B.
Datasets. We conduct experiments on over 30 textattributed graphs spanning five domains: academic networks, e-commerce networks, knowledge graphs, molecular graphs, and temporal graphs. Pretraining is performed on a diverse subset including Arxiv (academic), Products (e-commerce), WN18RR and FB15K237 (knowledge), and Chemblpre and PCBA (molecular). Specialization is evaluated on representative datasets for each domain: Arxiv, Products, FB15K237, and PCBA. For temporal graphs, which are e-commerce temporal graphs, we also use Table 2: We report the model performance across five graph domains: academia, e-commerce, knowledge base, molecular, and temporal graphs, with results averaged over all graphs within each domain. Note that -G and -S represent the general and specialized versions of GIT, respectively. The comprehensive results can be found in Appendix F.
Domain Academic E-commerce KG Molecule Temporal Held-out Avg. Avg. 0-shot Sup. GNN -------GraphMAE 15.42 8.19 -47.19 -26.67 25.11 OFA 13.98 8.73 -50.49 -27.20 26.14 GIT -G 14.88 8.79 -53.34 -28.56 27.50 GIT -S 23.45 17.06 -62.83 -35.19 36.32 3-shot Sup. GNN -------GraphMAE 49.25 48.20 56.56 56.01 40.31 50.15 52.07 OFA 45.93 57.06 56.97 57.03 38.92 51.84 53.70 GIT -G 54.00 57.22 67.55 55.96 39.95 56.09 57.82 GIT -S 55.18 58.01 67.80 62.82 41.38 58.69 60.15 Finetune Sup. GNN 73.57 78.21 66.86 73.65 62.61 71.14 72.25 GraphMAE 73.81 76.57 72.61 71.41 62.75 71.37 72.79 OFA 72.18 76.64 72.38 74.03 62.31 71.48 73.08 GIT -G 75.82 78.55 75.73 74.57 64.59 73.84 75.37 GIT -S 75.88 78.83 76.15 75.20 64.68 74.19 75.72 Citeseer Cora Pubmed DBLP Arxiv Arxiv23 The model performance on all datasets in the fine-tuning setting. For GIT, the best result is selected between GIT-G and GIT-S, while the best baseline performance is chosen among GCN/GAT/GIN, BGRL, GraphMAE, and OFA.
Products for SFT to assess robustness under temporal distribution shifts. We provide the full dataset details in Appendix E.1.
Baselines. We compare against a broad spectrum of baselines, including supervised GNNs (GCN (Kipf & Welling, 2017), GAT (Veličković et al., 2018), GIN (Xu et al., 2019)), self-supervised models (BGRL (Thakoor et al., 2022), GraphMAE (Hou et al., 2022)), and graph foundation models (OFA (Liu et al., 2024a), GraphPrompt+ (Liu et al., 2023), All in One (Sun et al., 2023), OpenGraph (Xia et al., 2024), AnyGraph (Xia & Huang, 2024)). We also include domain-specific expert models for comparison. See Appendix E.2 for full descriptions.
Experimental Protocols. We use GraphSAGE (Hamilton et al., 2017) as the encoder and repeat each experiment five times with different random seeds. We evaluate three paradigms: fine-tuning, in-context learning, and zero-shot learning. Fine-tuning updates all model parameters on downstream data. In in-context learning (few-shot without finetuning), we randomly sample k instances per class, compute prototype embeddings via averaging, and classify using nearest-prototype inference.
Following Liu et al. (2024a); He & Hooi (2024), we sample 500 5-way 3-shot tasks; if the number of classes is fewer than 5, we use the actual number of classes as the number of ways. Zero-shot learning replaces prototypes with class description embeddings generated by an LLM. For evaluation, we report accuracy for node classification and edge classification, and AUC for graph classification and link prediction. Additional details are provided in Appendix E. Dataset-Wise Performance. Figure 3 shows fine-tuning performance across all datasets. GIT consistently outperforms the strongest baseline in the majority of cases, validating the effectiveness of task-trees as generalizable learning units across heterogeneous graph tasks.
Effect of Specialization. We summarize three key observations: (1) Specialization (GIT-S) enhances the performance of GIT-G across most settings (Table 2). However, the impact of specialization varies depending on the dataset used (Appendix Figure 9 and Table 25).
(2) Specialization does not significantly degrade model performance on other domains (Table 27).
(3) Applying the proposed specialization approach to other models also yields performance improvements in specific domains (Table 4), showing the generalization of post-training in enhancing model capacity.
To evaluate the effectiveness of GIT, we compare it against recent graph foundation models, including GraphPrompt+ (Liu et al., 2023), All in One (Sun et al., 2023), OpenGraph (Xia et al., 2024), and AnyGraph (Xia & Huang, 2024), under the pretrain-then-finetune paradigm. As shown in Table 3, we benchmark GIT-G and all baselines across three representative domains: academic networks (node classification), knowledge graphs (edge classification), and molecular graphs (graph classification). GIT-G consistently outperforms all competing methods across tasks and domains. While many existing models pursue broad generalization by addressing multiple aspects-e.g., domain shifts, modality fusion, and prompt engineering-GIT adopts a targeted approach centered on task alignment. Its core innovation lies in the use of task-trees, which provide a unified abstraction across graph tasks.
We conduct an ablation study on academic networks to evaluate the impact of different training strategies. Specifically, we examine four approaches: (1) Base Model: Pretraining on the target graph. ( 2) Expert Model: Pretraining on all academic networks. (3) General Model: Pretraining on the default pretraining datasets. (4) Specialized Model: Pretraining on the default datasets followed by specialization on Arxiv. The results, averaged across all academic graphs, are reported in Table 4. Notably, the general model of GIT maintains stable performance relative to both the base and expert models. In contrast, GraphMAE and OFA exhibit performance degradation when transitioning from the base and expert models to the general model. This finding underscores the potential of task-trees in mitigating such negative transfer. Furthermore, specialization in GIT allows its performance to closely approximate that of expert models trained exclusively on academic graphs.
We compare GIT to domain experts in molecular and knowledge graphs, as these domains require domain-specific knowledge. Our findings indicate that the specialized GIT (GIT-S) closely approximates the performance of these experts. In molecular graphs, GIT-S achieves an average performance of 62.83, ranking second to the state-of-the-art GIMLET (64.15) (Zhao et al., 2023) while outperforming other domain experts (Zeng et al., 2022;Su et al., 2022;Taylor et al., 2022), whose best performance is 55.82 (Table 24). Similarly, in knowledge graphs, GIT-S attains an average score of 67.80, approaching the KG expert ULTRA (68.53) (Galkin et al., 2024), as shown in Table 23 in Appendix. We compare the efficiency and effectiveness of task-trees against subgraph-based learning units in the fine-tuning setting, as shown in Figure 4 and Table 5. For a fair comparison, we implement a subgraph-based variant of our model, denoted GIT-SubG, by substituting task-trees with subgraphs while keeping all other components unchanged.
Experimental results across three domains-academic (node classification), knowledge graphs (edge classification), and molecular graphs (graph classification)-demonstrate that task-trees consistently outperform subgraphs in both computational efficiency (Figure 4) and predictive performance (Table 5). This highlights the advantage of task-trees in serving as compact, expressive, and structurally aligned learning instances, especially in cross-task and cross-domain generalization scenarios.
While prior experiments use text-attributed graphs, GIT does not inherently rely on textual information. We adopt textattributed datasets to isolate the impact of task heterogeneity, while sidestepping the confounding effects of feature heterogeneity. Textual attributes enable feature alignment across graphs via a shared encoder, allowing us to more clearly assess the benefits of task-tree generalization. Importantly, GIT is compatible with non-textual graphs. To demonstrate this, we introduce a lightweight module that addresses feature heterogeneity by applying SVD to project features into a shared space. As shown in
Table 6, we pretrain GIT-G on non-text-attributed datasets-PubMed (node classification), Citeseer (link prediction), and IMDB-50 100 Usage (%) Memory Usage 2 9 2 10 2 11 2 12 2 13 2 14 2 15 Batch Size (log) 200 250 Seconds Time (s) / Epoch GIT (Task-Tree) GIT (Subgraph) GraphMAE B (graph classification)-and fine-tune on Cora (link prediction). Results, evaluated via AUC, confirm that GIT-G remains effective without relying on textual information, validating its broader applicability.
We introduce task-trees as unified learning instances for aligning heterogeneous graph-based tasks, supported by both theoretical and empirical analyses. Based on this abstraction, we develop GIT, a pretrained graph foundation model that leverages a small set of source graphs to generalize across over 30 datasets spanning five diverse domains.
Our results demonstrate that task-trees preserve transferable patterns across tasks, offering a scalable and principled pathway for cross-domain generalization in graph learning.
Limitations and Future Work. While task-trees serve as a promising abstraction-analogous to images in vision and sentences in language-several challenges remain. First, although our results suggest that task-trees capture generalities across tasks, pinpointing the precise transferable patterns remains an open question. Future work should explore this from both theoretical and empirical perspectives. Second, transforming graph neighborhoods into tree structures may lead to information loss due to the limitations of message-passing GNNs. This can affect model expressiveness, especially for graphs with complex higher-order structures. Incorporating more expressive architectures, such as higher-order GNNs (Morris et al., 2019;2023) or advanced graph modeling (Wang et al., 2025b), may help mitigate this issue. Finally, while GIT demonstrates strong performance with a lightweight design, exploring more sophisticated variants-e.g., incorporating attention mechanisms, graph prompting, or task-conditioned decoders-offers exciting directions for extending the generality and adaptability of graph foundation models. We outline several of these opportunities in Appendix C.
Graph Neural Networks. GNNs are a class of learning models specifically designed to operate on graph-structured data and have demonstrated substantial success across a variety of domains. Their strength lies in their ability to perform relational learning, where information from neighboring nodes is aggregated and used to enhance node representations. For instance, GCN (Kipf & Welling, 2017) utilizes message-passing to aggregate information from neighboring nodes to central nodes.
Building on this, models such as GraphSAGE (Hamilton et al., 2017) and GAT (Veličković et al., 2018) introduce innovative techniques like neighborhood sampling and attention mechanisms, respectively, further advancing performance on graph learning tasks. However, these methods are limited to solving a single task by training from the scratch (Zhang et al., 2019;Fan et al., 2022;Qian et al., 2025;Ma et al., 2023;Qian et al., 2024).
Transferability of GNNs. Existing works that analyze the shared concepts (generalities) across different graphs primarily follow two approaches. The first is graphon theory, which provides bounds on the distance between graphs generated from the same graphon. This method has been used to study transferability in pretraining and fine-tuning settings (Cao et al., 2023), to develop more expressive fine-tuning techniques (Sun et al., 2024), and to design new model architectures (Ruiz et al., 2020). However, despite its theoretical advantages, graphon-based approaches face practical challenges, particularly the strong assumptions required and the difficulty of identifying graphons in large-scale graphs, which limits their applicability in building graph foundation models. The second approach involves leveraging substructures within graphs to identify transferable patterns (Mao et al., 2024). This method focuses on extracting subgraphs composed of meaningful substructures for prediction tasks. While this approach offers theoretical insights into stability (Levie et al., 2019;Zhu et al., 2021), it struggles to fully capture substructures that are beneficial for downstream tasks (Zhang et al., 2024a).
Graph Foundation Models. Foundation models are designed as general-purpose solvers capable of handling various tasks across different domains. For instance, LLMs, the foundation models in natural language processing, are capable of performing tasks such as summarization, translation, and entity recognition, as well as question-answering. However, building such versatile foundation models for graphs presents unique challenges due to the inherent feature, structural, and task heterogeneity across different graph domains and tasks. To address these challenges, Qiu et al. (2020) pretrained GNNs using subgraphs as basic units, mitigating structural heterogeneity. Building on this, Sun et al. ( 2023) reformulated node-, edge-, and graph-level tasks into subgraph-level tasks, tackling task heterogeneity. Additionally, Huang et al. (2023) and Liu et al. (2024a) applied LLMs to unify the feature spaces of cross-domain graphs, addressing feature heterogeneity. These approaches enable models to operate on cross-domain and cross-task graphs. Further advancements, such as He & Hooi (2024) and Li et al. (2024), improve node embeddings by jointly optimizing GNN and LLM encoders, facilitating various downstream tasks like few-shot learning and zero-shot learning. However, most of these approaches rely on subgraphs as the primary learning instances, which can result in inefficient training and reduced expressiveness, as discussed in the main paper. Other efforts to resolve feature heterogeneity include methods like singular vector decomposition (SVD) (Zhao et al., 2024a;Yu et al., 2024), non-parametric encoders (Zhao et al., 2024b), or synthesizing text-attributed graphs (Wang et al., 2025a). Notably, a recent study by Wang et al. (2024b) explores computation trees as transferable patterns in graphs. However, our work differs in three key aspects: (1) While Wang et al. (2024b) focus on identifying transferable patterns across graphs, our approach is centered on designing fundamental learning instances.
(2) Our theoretical framework also serves as a foundational basis for Wang et al. (2024b).
(3) Our proposed GIT significantly simplifies the model proposed by Wang et al. (2024b), demonstrating a minimally applicable design that retains effectiveness.
Another line of research focuses on designing GFMs for single tasks or domains, thereby avoiding the complexities of feature, structural, or task heterogeneity. For example, Galkin et al. (2024) propose a foundation model for reasoning tasks on knowledge graphs, using triplets as basic transferable patterns. 2024a) have explored using LLMs as graph reasoners to solve graph tasks, similar to their role in vision language models. While these methods excel at specific tasks or domains, they are not suitable as general graph solvers across diverse tasks. In contrast to these approaches, our proposed GIT model is pretrained on diverse task trees to acquire general reasoning capabilities, allowing it to quickly specialize in specific domains through instruction tuning. It is challenging for a single graph model to handle tasks across various domains due to pattern conflicts, where the same structural pattern can have different meanings in different domains. To illustrate this issue, we provide an intuitive examplefoot_3 . Consider a pretraining process involving datasets from multiple domains, such as social networks, molecular networks, academic networks, and knowledge graphs. Suppose the model learns triangle structures during pretraining. In social networks, the semantic meaning of these triangles is stable, following the principle of "the friend of my friend is my friend". However, in molecular graphs, the meaning of triangle patterns may be unstable due to chemical properties. This pattern conflict can significantly degrade the performance of graph models (Cao et al., 2023;Mao et al., 2024). Specialization helps resolve this issue by aligning the meanings of certain structural patterns with the semantics specific to the target domain.
The Necessity of Domain Alignment. Datasets from multiple domains are often projected into different subspaces, potentially due to misalignment of node attributes (Chen et al., 2024b) and the frequent patterns across domains. As a result, the model may "memorize" information specific to each domain rather than learning transferable patterns. This can lead to misunderstandings when the same pattern appeared across different graphs is projected into different subspaces.
Consequently, the model struggles to acquire transferable knowledge that would benefit unseen tasks and specialized domains. Properly aligning the embedding spaces of different domains is crucial for obtaining transferable knowledge and improving performance on unseen graphs and specialized domains.
We propose a domain regularizer to control domain distances by projecting crossdomain graphs with different characteristics into a shared embedding space. Specifically, we define a shared subspace across domains and pull the subspaces of other domains into alignment with this defined space. The shared subspace should be positioned at the center of the cross-domain datasets to minimize the effort required to adjust the subspaces of all domains.
In particular, the basis vector of the shared subspace is defined as the average of all instances:
where P (D) represents the domain distribution, T D is a distribution of task-trees within domain D, and ϕ(T i ) is the embedding of the task-tree T i . Given the shared subspace basis, we optimize the KL divergence between each instance and the basis. However, obtaining the global basis vector h Basis directly is impractical due to dataset size, so we approximate it by averaging the embeddings of all instances within a batch to compute the local basis ĥBasis . We then optimize the KL divergence for all instances in the batch. To mitigate randomness, we empirically use a relatively large batch size (4,096). Formally, the domain regularizer is defined as
where B denotes the batch, and H and Z i represent the distributions of the local basis vector ĥBasis and instance embedding z i , respectively.
How the Domain Regularizer Works? To better understand how the domain regularizer functions, we conduct an analysis to demonstrate its benefits in regulating domain distances while preserving task structures for each dataset. We use eight datasets provided by Liu et al. (2024a) for pretraining: Cora, Pubmed, Arxiv, WikiCS, WN18RR, FB15K237, CHEMHIV, and CHEMPCBA. The analysis results are presented in Figure 5.
In the figure, we display (a) a heatmap of similarity between different datasets with varying weights, and visualizations of the embedding space before (b) and after (c) applying the domain regularizer. The results show that the domain regularizer effectively adjusts the distances between datasets by pushing apart overly similar graphs and bringing closer those that are too distinct. Furthermore, we show that the regularizer does not significantly alter the task structures of each dataset, as illustrated in subfigure (d). In this subfigure, we apply k-means algorithm on each dataset, setting k to the number of classes, and compare to the ground-truth by using NMI as the metric. The assumption is that if two sets of vectors yield similar clustering results, the classification outcomes of the same classifier will be similar, indicating that the task structure across the two sets is consistent. The results demonstrate that changing the regularizer weight does not significantly affect task structures. This may be because the regularizer acts by translating vectors toward a central point without altering the relationships between individual pairs of vectors. To further evaluate the impact of domain regularizer for the downstream tasks, we present the model performance average over the used eight datasets across all settings in Table 7. We observe the use of domain regularizer can boost the model performance, especially in in-context and zero-shot settings. In addition, we empirically find that λ = 10 can lead to better performance. Thus, we set λ = 10 as the default weight in this paper.
In node-level tasks, it is important to consider both graph homophily and heterophily (Ma et al., 2022). Homophily describes the close relationships between connected entities, while heterophily refers to distant relationships between connected entities. Empirically, basic message-passing GNNs tend to perform well on homophily graphs but struggle with heterophily graphs (Luan et al., 2022). Despite using GraphSAGE as the backbone in our GIT, it still performs well on heterophily graphs, such as Children and Ratingsfoot_4 . The experimental results for node classification and link prediction on these two graphs are presented in Table 17 and Table 18, where GIT generally achieves the best performance. We hypothesize that the proposed task-tree structure captures not only homophily relationships but also heterophily relationships. A potential question is whether our message-passing GNN can effectively capture these heterophily relationships, despite Ma et al. (2022) suggesting that basic GNNs may handle heterophily graphs by memorizing the patterns between the target node and its neighbors. We plan to use more advanced GNNs capable of encoding heterophily structures to further validate our hypothesis.
observe a clear trend where more data led to better performance. We consider there are three potential reasons.
(1) From a model perspective, we use a GraphSAGE encoder with limited layers and parameters, which may not fully capture the knowledge contained in the pretraining data. Additionally, we apply basic mean pooling to derive task-tree embeddings from task-relevant node embeddings, which may prevent the model from identifying the relative importance of task-relevant nodes, thereby limiting its expressiveness.
(2) From a training paradigm perspective, we employ a negative-free contrastive learning framework similar to Thakoor et al. (2022), but this basic approach may not be expressive enough to extract meaningful knowledge from the pretraining graphs.
(3) From a data perspective, despite using over 30 graphs in this study, the number of instances is still significantly lower than that of textual or visual instances extracted from the Internet. Furthermore, the pretraining datasets may not be well-aligned. Although we used a textual encoder to align node features, we cannot guarantee that the encoded node features are in the same embedding space (Chen et al., 2024b).
C.1. Pretraining
How to Design Reconstruction Tasks? Theorem 3.5 suggests that a well-designed encoder, capable of effectively handling reconstruction tasks during pretraining, can improve the model's generalization ability. One approach is to use more powerful encoders to enhance reconstruction performance. Another approach is to introduce additional reconstruction losses to further refine the encoder. For example, methods such as those proposed by Qiu et al. (2020), and Hou et al. (2022), Ju et al. (2023b), and Wen et al. (2024), or designing more comprehensive reconstruction objectives could be explored.
How to Improve Transferability? The pretraining task, i.e., task-tree reconstruction, differs from the downstream task of task-tree classification, as the task heterogeneity may hinder model transferability (Hu et al., 2020). To mitigate this, one could develop more effective adaptation methods, such as graph prompt learning (Sun et al., 2022), to reduce task heterogeneity.
How to Define Instructions? In this paper, as we focus on experiments with text-attributed graphs, we define instructions as label descriptions encoded by LLMs. However, this approach is not applicable to non-textual graphs. Other methods could be explored to define instructions, such as using proxy models (Hu et al., 2019) or graph heuristics (Jin et al., 2020) to generate instructions.
How to Choose SFT Data? We manually select graphs as supervised fine-tuning datasets for each domain, though the selected graphs may not be fully representative. Unlike textual data, evaluating the quality of graph datasets poses a challenge. Improved dataset selection methods could enhance the SFT process by identifying more representative or diverse data from graph databases. Additionally, while we perform instruction tuning over entire graphs, it is possible that only specific subgraphs are beneficial (Hashemi et al., 2024). Developing data selection methods that focus on high-quality subgraphs within a single SFT dataset could improve task-tree selection. Another worthy research line is to select SFT data that aligns with user preferences (Song et al., 2024).
How to Leverage SFT Data? In scenarios with limited instructions, standard supervised fine-tuning may struggle to capture sufficient knowledge of the target domain. To address this, methods could be proposed to better utilize the unlabeled instances in the SFT dataset, thus enhancing model adaptation (Sohn et al., 2020;Ni et al., 2025).
How to Maintain General Inference Capability? While instruction tuning specializes the model for a specific domain, it may compromise the model's general inference capabilities across other domains. This could hinder the model's performance when it needs to function both as a domain expert and a general reasoner. To mitigate this, regularization techniques could be designed to preserve the general knowledge encoded in the model during the instruction tuning process.
Why SFT Works on Graphs? Instruction tuning is a common post-training process in modern large language models (e.g., LLAMA, GPT) that significantly improves instruction-following capabilities. The success of this method in LLMs may stem from the fact that natural language serves as an interface between humans and models (Wei et al., 2021). However, the reason instruction tuning works for graphs remains an open question and presents a potential direction for future research.
C.3. More Scenarios.
The paper leverages text-attributed graphs to align node features. However, the pre-processing of TAGs can be timeconsuming, raising the challenge of how to effectively apply the model to graphs without aligned node features. Furthermore, while we primarily focus on homogeneous graphs in this work, most real-world applications involve heterogeneous graphs.
Addressing the question of how to design a single model capable of handling various types of graphs remains an open challenge. Finally, applying the model to specific applications Zhang et al. (2024c), which may exhibit unique characteristics, is another important consideration for future research.
D. Proof D.1. Proof of Theorem 3.1
Proof. We begin by introducing the basic GNN architecture used in the proof. Given a GNN encoder ϕ(•) with parameters W = (W 1 , W 2 ), we use a GraphSAGE-like architecture, defined as follows (with some notation abuse):
where σ is the non-linear activation function, x i is the node feature of node i, and N i represents the neighbors of node i, corresponding to its children in the computation tree. T L i denotes the computation tree of node i with L layers. Neighborhood information is incorporated by averaging the embeddings of neighboring nodes. WLOG, the averaging operation can be replaced with any permutation-invariant set operation without affecting the analysis in this paper. For simplicity, we assume all GNN layers share the same parameters; this assumption does not affect the validity of our proofs. Since these functions and neural networks exhibit Lipschitz continuity, we denote the Lipschitz constant of σ(•) as C σ . Additionally, we assume the norm of node features is bounded by ∥x∥ ≤ B x , and the model weights by ∥W 1 ∥ ≤ B W1 and ∥W 2 ∥ ≤ B W2 . While real-world graphs typically exhibit varied node features, standard techniques (as employed in this paper) like normalization can ensure that B x remains a small value. We define the distance between task-trees T t 1 with n task-relevant nodes {v 1 , ..., v n } and T t 2 with m task-relevant nodes {v 1 , ..., v m } as:
where ∥ • ∥ is the L2 distance. Following, we expand the stability term ∆ as:
.
Then, we separately analyze the term (a) and term (b). The term (a) can be bounded as follows:
That is, term (a) is bounded by the distance between the average features of nodes in the first layer of the task-trees (i.e., the nodes directly connected to the root). Next, we bound term (b):
.
Term (c) describes the distance between the average features of nodes in the second layer of the task-trees, while term (d) follows a recursive formula, similar to term (b). By combining terms (a) and (b), we have:
We can extend the formula recursively through all layers until the final layer. The recursive nature of the formula allows us to more easily reformulate the bound:
where ∆ l denotes the distance between task-trees at the l-th layer. For clarity, we can interpret C 1 ∆ 1 as corresponding to Term (a) and C 2 ∆ 2 as corresponding to Term (c). Next, we explain how to determine C l and ∆ l for each layer.
By analyzing the recursive formula, we determine C l as follows:
We then define the ∆ l . For a concise definition, we introduce an additional notation for describing the subtree information:
By using the term, we can define the ∆ l as:
By using a formulation like expression 11, we can decompose the impact of different layers, facilitating further analysis of the upper bound on the distance between two task-trees. Next, we will analyze the upper bound of each term. To begin, we first introduce a lemma.
Lemma D.1. Given two sets of random vectors S 1 = {v 1 , ..., v n } and S 2 = {v 1 , ..., v m }, the following holds:
Proof. Let's consider two sets
We have:
WLOG, this analysis can be extended to cases where the size of A is n and the size of B is m.
Based on the Lemma, we have
which is displayed in Theorem 3.1.
We then use the Lemma to bound the ∆ l . For example, the upper bound of ∆ 1 is:
Similarly, the upper bound of ∆ 2 is:
where d i = |N i | and d j = |N j | represent the number of children (i.e., the degree) of nodes i and j, respectively. Thus, the upper bound of ∆ l is:
Now we can have the highest upper bound of ∆ as:
Note that this upper bound is an extreme case; the bound can be tightened by adding supplementary information or making additional assumptions. Additionally, the distance between task-trees can be reduced by applying techniques like normalization, which lowers the values of the constants.
Proof. We begin by restating the notations used in the theorem. Let P represent the task-tree distribution, T the downstream task distribution, ϕ ∈ Φ the GNN encoder, g ∈ G the predictor head used during pretraining, and f ∈ F the predictor head for the downstream task. The pretraining objective is defined as
, where T is the task-tree and T is the corresponding corrupted task-tree obtained via arbitrary corruption functions. The risk on the downstream task is defined as
where T is the task-tree, y is the associated label, and κ denotes the loss function. Before we begin the proof, we present an additional helper proposition.
Proposition D.2 (Ruhe's Trace Inequality (Ruhe, 1970)). If X and Y are positive semi-definite Hermitian matrices with eigenvalues,
x i y i .
Note that we are going to prove
where C δ ≈ O(1) and δ = 1 2 . The proof involves deriving the upper bound for the term
followed by the lower bound for min g∈G L P (g • ϕ) -min g ′ ∈G L P (g ′ • ϕ ′ ). To simplify the proof, we assume the downstream task is a binary classification task, though this approach can be extended to multi-classification scenarios.
where (T, y) ∼ T and κ(f (ϕ(T ))) is shorthand for κ(f (ϕ(T )), y) for notational convenience. Since we define f ∈ F as a linear predictor for binary classification, we can rewrite this equation in the following form:
Note that in the previous formula, we define θ Deng et al., 2024). We can select a sufficiently large B θ to ensure an adequately large function space. Additionally, we define θ ′ as the optimal head for the encoder ϕ ′ . The expression √ θ ′⊤ Λθ ′ is equivalent to tr(Λθ ′⊤ θ ′ ), which can be further simplified using Proposition D.2.
where σ i is the i-th eigenvalue for the matrix and σ max denotes the maximum eigenvalue.
Then, we are going to demonstrate the lower bound of min g∈G L P (g
where ( T , T ) ∼ P. Here we also consider the predictor g as a linear function, so that we have the following form:
where C P = E P ∥ϕ ′ (T ) -ϕ(T )∥ 2 is a constant, and W ′ is defined as the optimal transformation matrix for the encoder ϕ ′ . Based on this formula, we can further simplify the bound on
Now that we have the upper bound for
) and the lower bound for min g∈G L P (g • ϕ) -min g ′ ∈G L P (g ′ • ϕ ′ ), we can establish the relationship between them as follows:
Based on our definition, θ ′ and W ′ are optimal heads for the encoder ϕ ′ , the complexity term
would be a constant which in the order of O(1).
Proof. We begin by introducing some essential notations. Let P represent the pretraining task-tree distribution and T the downstream task-tree distribution. The pair (T, y) ∼ T denotes a task-tree and its corresponding label, where we define the labeling function as ψ, meaning y = ψ(T ). The GNN encoder is ϕ ∈ Φ, the pretraining predictor is g ∈ G, and the downstream predictor head is f ∈ F . As in the previous proof, we consider a binary classification task for simplicity, though this can be extended to multi-class settings. The downstream risk is given by R
where κ is a loss function.
Then, we define the excess risk on the downstream distribution T as
+ min
,
where ϕ and f represent encoder obtained during pretraining and the prediction head learned in downstream task, respectively, while ϕ ′ and f ′ are the optimal encoder and predictor head on the downstream distribution. ϕ * is the optimal encoder obtained during pretraining, defined as ϕ * = arg min ϕ∈Φ min g∈G L P (g • ϕ). We will analyze these four terms separately.
To bound the term (a), we need to introduce the empirical Rademacher complexity (Definition 1, (Deng et al., 2024)) as
where ε i is i.i.d., and P(ε = 1) = P(ε = -1) = 1 2 .
Using this definition, we can bound the term (a):
, where f * is the optimal predictor head over the distribution T , defined as f * = arg min f ∈F R T (f • ϕ). The term (a.3) represents the empirical risk gap between the learned head f and the best head f * , which implies that the term is a constant greater than or equal to 0. Term (a.1) and (a.2) describe the gap between the risk and the empirical risk. According to uniform convergence, these two terms can be expressed in terms of empirical Rademacher complexity. Thus, term (a) can be bounded as:
where B κ is the bound of the Lipschitz of loss function κ. We then further simplify the empirical Rademacher complexity for a more reasonable expression.
As the ε i are i.i.d. with zero mean as our definition, we cancel the term, thus
Then, we bound the term (b). To do this, we introduce a notation
where B κ represents the upper bound of the Lipschitz constant of κ, and X ϕ denotes the distribution of task-tree embeddings produced by the encoder ϕ. This term measures the distributional distance of task-trees between the pretraining and downstream distributions.
Following, we bound the term (c), as
The term L P (g • h) -min g ′ ∈G,ϕ ′ ∈Φ L P (g ′ • ϕ ′ ) describes the excess risk on pretraining task, which can be replaced by a notation E P (g, ϕ).
Lastly, we bound the term (d),
By combining the four terms, we obtain the generalization bound for a model pretrained on task-tree distribution P and fine-tuned on task-tree distribution T :
We can set C 1 = C κ C f and C 2 = B κ as two downstream task-related constants.
E.1. Datasets Dataset Statistics. We utilize 32 datasets spanning five domains in this paper. Since these datasets are text-attributed graphs, we use Sentence-BERT (Reimers & Gurevych, 2019) to align the node textual features into 768-dimensional vectors. The dataset statistics are presented in Table 8. For the temporal graphs, we split each graph into 10 snapshots, with the statistics shown in Figure 8. We classify Children and Ratings as heterophily graphs due to their relatively low homophily ratios (Chen et al., 2024b).
Splitter. For each dataset, we use the same splitting strategy as provided in the original paper (Chen et al., 2024b;Galkin et al., 2024;Feng et al., 2024;Zhang et al., 2024b). If multiple splits are provided, we evaluate model performance on each split using different random seeds. For datasets with a single split, we repeat the experiments five times with different random seeds. For GDELT and ICEWS1819, which are originally temporal knowledge graphs, we apply an 80%/10%/10% split based on timestamps for train/validation/test settings. For the temporal graphs Enron and Googlemap CT used for edge classification, we split each snapshot by timestamps, using the first 70% for training, the next 15% for validation, and the remaining 15% for testing.
GCN (Kipf & Welling, 2017). A supervised message-passing GNN trained from scratch for each task. As a result, it cannot be applied to in-context learning or zero-shot learning. GAT (Veličković et al., 2018). A supervised GNN that uses an attention mechanism to learn the importance of received messages.
GIN (Xu et al., 2019). A supervised GNN specifically designed for graph-level tasks.
BGRL (Thakoor et al., 2022). A popular self-supervised learning framework for graphs that employs a contrastive learning loss without negative samples.
GraphMAE (Hou et al., 2022). A graph learning framework pretrained in a masked auto-encoder fashion.
OFA (Liu et al., 2024a). A cross-task and cross-domain graph foundation model that treats subgraphs as the basic learning instances. It introduces a graph prompt learning framework to enable in-context and zero-shot learning.
EXPERT MODELS DESIGNED FOR SPECIFIC DOMAINS ULTRA (Galkin et al., 2024). A foundation model designed specifically for knowledge graphs, which we treat as the domain expert for KGs.
KVPLM (Zeng et al., 2022). A language model based on SMILES representations of molecules, serving as an expert model for molecular graphs.
MoMu (Su et al., 2022). Another expert model for molecules that leverages GNNs to improve molecular representations.
Galactica (Taylor et al., 2022). A foundation model for molecular graphs that utilizes multi-task learning with instructions. GIMLET (Zhao et al., 2023). A foundation model for molecules that incorporates advanced models and instruction-based learning.
Pretraining Datasets. We select six datasets for pretraining, including Arxiv, Products, WN18RR, FB15K237, Chemblpre, and PCBA, due to their diversity in domains and tasks. For self-supervised learning methods, these six datasets are used for pretraining unless otherwise specified.
SFT Datasets. For specialization via SFT in each domain, we use Arxiv for academic networks, Products for ecommerce networks, FB15K237 for knowledge graphs, and PCBA for molecular networks. For temporal graphs, which are e-commerce-based, we also use Products for SFT to evaluate robustness under temporal distribution shifts.
Backbone. We use a GraphSAGE-like encoder (Hamilton et al., 2017). Following the encoding of task-trees, we add an additional linear transformation as the projector. Note that we does not leverage edge features to make the task harder except for Enron and Googlemap CT where node features are IDs and edge contains messages. As the edge information may significantly benefit some tasks like knowledge graph completion and molecule property prediction.
Finetune. This is the basic setting that directly finetune the full parameters of the pretrained model by appending a linear classifier on the top of the model encoder. In-context Learning. This is a kind of few-shot learning without fine-tuning the model parameters. We randomly select samples from a certain class, and average the selected samples to form prototypes, which is used for classification. We follow existing GFM works (Liu et al., 2024a;He & Hooi, 2024) to conduct 500 randomly sampled 5-way 3-shot learning tasks. If the number of classes is less than 5, the number of ways is set to the number of classes.
Zero-shot Learning. The zero-shot learning is similar to in-context learning, yet we use the LLM-encoded class description embeddings as the prototypes for prediction. Similar to in-context learning, we also randomly sample 500 tasks for evaluation. Another zero-shot setting involves using an additional LLM for zero-shot inference (Chen et al., 2024a). We leave this in our future work.
Baselines. For the baseline methods, we follow the hyperparameters reported in (Liu et al., 2024a;Chen et al., 2024b). If the hyperparameters are not provided, we set the number of epochs to 1,000, the batch size to 4,096, early stopping at 200, and the hidden dimension to 768, using a 2-layer GraphSAGE as the backbone with batch normalization and ReLU activation. For optimization, we use AdamW with a weight decay of 1e-6 and tune the learning rate from 1e-3, 1e-4, 1e-5, reporting the best performance. For methods with attention mechanisms, we set 4 attention heads.
GIT. The model architecture and pretraining parameters of our GIT are presented in Table 9. The specific fine-tuning 10, 11, 12, 13, and 14. For in-context learning and zero-shot learning results without fine-tuning, the general model does not involve any hyperparameters. For the specialized model, we tune the hyperparameters of SFT epochs from 10 to 500, in steps of 10, the SFT learning rate from 1e-4, 1e-5, 1e-6, 1e-7, 1e-8, and the normalization method from None, BN.
F.1. Domain: Academia Node Classification. We perform node classification on academic networks across three settings: basic fine-tuning, 3-shot in-context learning, and zero-shot learning. The comprehensive node classification results on academic networks, measured in terms of accuracy, are presented in Table 15. Notably, the specialized model (GIT-S) does not always outperform the general model (GIT-G). This may be because the manually selected SFT data does not adequately capture the underlying distribution of the domain. It would be valuable to explore dataset selection or instance selection methods to better optimize the choice of SFT data. * indicates the results from paper (Zhao et al., 2023).
Ablation Study on SFT Data used for Specialization. We also evaluate the impact of the SFT dataset used for specialization. The model's zero-shot performance is reported in Table 25, comparing the default SFT dataset PCBA with another SFT dataset, HIV. We find that the model performance with HIV as the SFT data is lower than with PCBA. We hypothesize that this is due to HIV having fewer graphs and tasks, which may provide less information for reducing the distribution discrepancy. Nevertheless, HIV still improves the model's performance over the general model on 5 out of 8 datasets. Ablation Study on SFT Data used for Specialization. We analyze the impact of SFT data in the experiments, as shown in Figure 9. The results show that changes in SFT data do not significantly affect model performance, particularly in fine-tuning and in-context learning settings. Even when the SFT and downstream data are the same, the model does not necessarily outperform models fine-tuned on other SFT datasets. This observation supports the motivation behind our proposed specialization method, which aims to shift the pretraining distribution P toward the distribution of target domains. It also highlights the importance of designing an instance selection method to identify the most effective SFT data.
University of Notre Dame
University of Connecticut. Correspondence to: Zehong Wang <zwang43@nd.edu>, Yanfang Ye <yye7@nd.edu>.Proceedings of the 42 nd International Conference on MachineLearning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
The scope of reconstruction task is large. We consider contrastive learning is also a kind of reconstruction.
This example was first illustrated inCao et al. (2023)
Our collected graphs include two heterophily graphs, Children and Ratings, with homophily ratios of 0.42 and 0.38, respectively, whereas other graphs generally have a homophily ratio greater than 0.60 (Table12,(Chen et al., 2024b)).