Towards Graph Foundation Models: Learning Generalities Across Graphs via Task-Trees
Authors: Zehong Wang
Zheyuan Zhang
Tianyi Ma
Nitesh V Chawla
Chuxu Zhang
Yanfang Ye
Venue: ICML 2025 poster (2025)
Keywords: Graph Neural Network
Foundation Model
Transferability
Theoretical Basis
Tree Structure
Primary area: deep_learning->foundation_models

Abstract: Foundation models are pretrained on large-scale corpora to learn generalizable patterns across domains and tasks---such as contours, textures, and edges in images, or tokens and sentences in text. In contrast, discovering such generalities in graph-structured data, especially across heterogeneous graph tasks, remains an open challenge. To address this, we propose a novel approach to cross-task generalization in graphs via task-trees, which serve as unified learning instances aligning node-, edge-, and graph-level tasks. We theoretically analyze the stability, transferability, and generalization properties of task-trees, showing that pretraining a graph neural network (GNN) on diverse task-trees with a reconstruction objective induces transferable knowledge. This enables efficient adaptation to downstream tasks with minimal fine-tuning. To validate our framework, we introduce Graph Generality Identifier on Task-Trees (GIT), a graph foundation model that demonstrates strong performance on over 30 graphs across five domains via fine-tuning, in-context learning, and zero-shot generalization. Code and data are available at https://github.com/Zehong-Wang/GIT.

Towards Graph Foundation Models: Learning Generalities Across Graphs via Task-Trees
Zehong Wang's Zheyuan Zhang'
Tianyi Ma
Nitesh V Chawla Chuxu Zhang? Yanfang Ye
Abstract
ferable pattems-sucee as contours and textures in images, tokens and sentences in text that reflect modality-specinf 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).
Foundation models are pretrained on large-scale corpora to learn generalizable patterns across domains and tasks-such as contours, textures, and edges in images, or tokens and sentences in text. In contrast, discovering such generalities in graph-structured data, especially across het- erogeneous graph tasks, remains open chal- lenge. To address this, we propose a novel ap- proach to cross-task generalization in graphs via task-trees, which serve as unified learning in- stances aligning node-, edge,, and graph-level tasks. We theoretically analyze the stability, trans- ferability, and generalization properties of task- trees, showing that pretraining a graph neural net- work (GNN) on diverse task-trees with a recon- struction objective induces transferable knowl- edge. This enables efficient adaptation to down- stream tasks with minimal fine-tuning. To validate our framework, we introduce Graph Generality Identifier Task-Trees (GIT), graph founda- tion model that demonstrates strong performance over 30 graphs across five domains via fine- tuning, in-context learning, and zero-shot gener- alization. Code and data are available at https: //git com Zehong WanggWannnggee /GIT.
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 dif- ferent domains often encode distinct phenomena- e... so- cial 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, limit- ing cross cross-task compatibility within a unified model (Wang et al., 2024b). These challenges hinder the development of graph foundation models capable of capturing transfer- able 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 ex- plored this question via two main approaches. (1) A graph- theoretic 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 expected to share structural properties, enabling effective transfer (Ruiz et al., 2020; Cao et al., 2023). However, graphon-based methods rely on strong generative assump- tions that rarely hold in real-world settings (Levie et al., 2021), and inferring shared graphon from diverse graphs remains computationally intractable. (2) A substructure- based perspective seeks recurring motifs-such as triangles, stars, 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 meth- ods that sample subgraphs consisting of substructures and encode them via GNNs (Sun et al., 2023; Liu et al., 2024a). However, message-par passiin GNNs are fundamentally lim- ited in capturing such substructures (Garg al., 2020; Esser
1. Introduction
Foundation models have emerged as a cornerstone of general-purpose machine learning, enabling cross-task and cross-domain generalization. Representative examples in- clude large language models (LLMs) for text (Achiam al., 2023; Touvron et al., 2023) and large vision mod- els (LVMs) for images (He et al., 2022; Yuan et al., 2021). Pretrained on massive datasets, these models capture trans-
Univerrsity of Notre Dame Uniiversity of Connecticut. Corre- spondence to: Zehong Wang <2wang443@dd @dd.u Yanfang Ye <yye7 @
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Learning Generalities Across Graphs via Task-Trees
al., 2021; Zhang et al., 2024a), restricting their efficacy in learning transferable subgraph representations.
We present the first theoretical framework addressing task heterogeneity in graph learning, establishing the effectiveness of task-trees for cross-task generalization.
Given the limitations of prior approaches, we introduce a novel perspective centered on the learning dynamics of message-passta passinngg 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 graph- level 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 task- tree (Figure 1). Task-trees offer three key advantages: (1) Learnability: tree-structured information can be effectively captured by meessage-pssingg GNNs (Gupta et al., 2024); (2) Uniformity: task-trees apply seamlessly across node-, edge- and graph-level tasks, mitigating task heterogeneity; (3) Effi- ciency: 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:
We propose GIT, graph foundation model pretrained on task-trees to acquire generalizable knowledge and support domain specialization.
Extensive experiments across 32 graphs and five do- mains validate the effectiveness of GIT under fine- tuning, in-context, and zero-shot settngs
2. Task- Rethinking Basic Learning Instances on Graphs
2.1. Preliminary
We begin with a brief introduction to message-passing GNNs and some related concepts. Let g = (V,E) rep- resent a graph with node set and edge set E, where each node v E V is associated with a feature vector x E R 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:
=!"' =o o (Wiz (1 + Wap (Ejenc)) 0(2) ((e o)) (1)
Task-Tre Tree Generality Assumption. The generalities shared across graphs are (at least partially) preserved within the task-trees of the involved graphs.
where N; denotes the 1-hop neighbors of node i, 20) rep- resents the node embedding at the I-th GNN layer with 2()) = x, and W1, W₂ are learnable matrices. The func- tions a, p. and g are the activation function, aggregation function and update function, respectively. To simplify the analysis. we assume p 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 tipshitz-continnee affecting the analysis in the paper.
To evaluate this assumption, we conduct a theoretical anal- ysis of task-trees with respect to stability, transferability, and generalization. Our main result shows that pretraining a GNN on diverse task-trees via reconstruction objec- tive yields transferable representations that adapt well to downstream tasks with moderate fine-tuning, Furthermore, the model can be specialized to specific domains via post- training (Wei al., 2021) on Somainn-peeificc task-trees.
functions, respectively, without
Nodes). Graph tasks can be roughly categorized into node-level, edge-level, and graph- level tasks, where the basic learning instances are nodes, edges, and entire graphs, respectively. For node classifica- tion, the task-relevant node of is the node to be classified. In edge classification, the task-relevant nodes are the start and end nodes (u,, u/} of the target edge egg- For graph classification, the task-relevant nodes (1() include all nodes in the target graph G.
Definition 2.1
To empirically validate our theoretical insights, intro- duce Graph Generality [dentifier on Task-Trees (GIT), 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 with- out fine-tuning), and zero-shot learning. Results show that pretraining on small set of graphs significantly improves performance on a broad range of downstream tasks, sup- porting the hypothesis that task-trees capture transferable generalities. Additionally, we propose an instruction tun- ing method to adapt the general model to specific domains, yielding performance comparable to or exceeding domain- specific expert models. Our key contributions are:
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 compu- tation tree T is constructed by recursively expanding the subtrees of its neighboring nodes, starting with T. = v.
We introduce task-rrees as unified learning instances for aligning heterogeneous graph tasks, demonstrating advantages over conventional units such as subgraphs.
2

---

Learning Generalities Across Graphs via Task-Treee
2.2. Task-Tree Construction and Encoding
Node Task
Append Task Nodes
The learning process of pressage-passingg GNNs can be in- terpreted recursive aggregation over computation trees, where the representation of a node e produced by L-layer GNN corresponds to the embedding of its L--hop computa- tion tree TV. Since predictions in graph tasks rely exclu- sively on the embeddings of tusk-relevant nodes, and those embeddings are determined by their respective computation trees, we construct unified task-tree for each learning in- stance-whether a node, edge, or entire graph-by merging the relevant computation trees, as illustrated in Figure 1.
Nade Property: ?
Edge Task
o Task Node
Virual Link
Task-Tree Tree Space
(Derived by Encoding Task Nodes via GNNs)
Edge Exist:
Graph Task
Definition 2.3 (Task- Trees). For any graph instance- whether a node, edge, or graph-we we have a set of task- relevant nodes {eî } and their corresponding L-layer computation trees (T,,.., T. These computation trees can be reformulated into a larger task-tree T" by introduc- ing virtual node that connects all task-relevant nodes.
Graph Property:
What's the property of trsk-
Figure 1: The formulation of task-
In contrast, our proposed task-trees offer both greater ef- ficiency and improved learnability (Table 1). Specifically, encoding task-trees for node, link, or graph-level tasks in- volves: (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 exam- plc, in node classification, we first introduce virtual nodes connected each node in the original graph and subse- quently 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 signifi- cantly more efficient than extracting and storing subgraphs. Furthermore, encoding encoding virtual nodes through message passing, ensuring that task-tree information remains fully learnable by stan- dard GNNs. Empirically, task-trees consistently outperform subgraphs in both effectiveness and efficiency (Section 5.6 and Appendix 1).
To encode task-tree, we adopt a simple yet effective ag- gregation strategy. Given a task-tree T composed of a virtual node of and task-relevan nodes ..i..... ) we compute its representation using a MEAN aggregator over the embeddings of the individual computation trees:
z' = ((T)) = + (TT))
where T; denotes the computation tree rooted at of. and is a shared GNN encoder. This representation serves as the input for downstream objectives such as reconstruction, classification, or alignment.
2.3. Comparison to Existing Works
is equivalent to directly
Unlike our proposed task-trees, several existing approaches (Qiu et al., 2020; Sun al., 2023; Huang 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 reformulat- ing 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) ap- plying GNNs to learn graph-level embeddings for classifi- cation. 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 bassaag--passing GNNs, as GNNs may struggle to learn es- sential 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.
The most closely related work to our task-tree framework is GFT (Wang et al., 2024b), which introduces computation trees align heterogeneous graph tasks. While both ap- proaches share the core intuition of structuring task-specific trees, GFT adopts a model-centri perspective, featuring learnable vocabulary, a multi- mautt--facetd reconstruction ob- jective, and specialized adaptation classifiers. In contrast, our task-tree framework is theory-driven and emphasizes the design of learning instances rather than model complex- ity. Notably, GFT empirically demonstrates the potential of computation trees for transferability, while our work com- plements it with a formal theoretical foundation, offering a principled understanding of task alignment in graph learning. Together, these works represent complementary advances to- ward -urposse graph foundation models. We present additional discussions on related work in Appendix A.
3

---

Learning Generalities Across Graphs via Task-Trees
Table I: Comparison of task alignment methods on graphs.
Without Task Alignment
Alignment via Subgraph Tasks
Alignment via Task-Tree Tasks (Ours)
@ Tunk Nade
oon Vinaa
Nork Tisk
Task
Graghh Tick
Node Tink
File Tack
Grophi Task
Nod: Task
Edge Tisk
Graph Task
Inppayy
Bdge later?
Gmphi Imppary
(Sahimmph Propory:?
Tank-Tre Propony: 2
Input
Original graphs
Extracted subgraphs
Original graphs with task nodes
Pre-processing
N/A
Extract subgraphs for each learning
Append task nodes the original graphs,
instance (mode/link/graph)
connecting each to task-relevanl nodes
Encoding
Apply GNNs to learn node embeddings
Apply GNNs on induced subgraphs to
Apply GNNs directly on original graphs
obtain subgraph embeddings
to learn task node embeddings
Prediction
Use node embeddings to derive mode/link/graph representations
Use subgraph embeddings as representations for correspunding instances (node/link/graphh
Use task node (task-tree) embeddings as
instance representations (node/link/graph)) (graph)) for predictions
Learnability
GNNs struggle to capture fundamental substructures preserved in (sub)graphs
GNNs inherently leam from structures, such computation trees
Efficiency
Storing and encoding subgraphs introduce additional computational
Encoding task-trees involves encoding augmented virtual nodes in the original graphs with minimal computational cost
overhead
Theoretical Basis
Lack of well-cstablished thcorctical foundation
Supported by rigorous thcoretical framework
3. Theoretical Analysis of Task-Trees
task- T3 and T?. with task-relevant nodes (ui, ..., Vn) and {ui,... Um J. respectively. The distance between task- trees is defined as A == (Ix(()) <(T)))l with
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.
Σ (T; 1
A (=11(177) - -
oTT)I
==1
C 1 (0) - 2
(0) +
(4)
Our goal is not to assert the universal superiority of task- trees over other learning units such as subgraphs, but rather to establish the theoretical plausibility of using task-trees to capture cross-tast task generalities. By grounding the construc- tion and use of task-trees in formal guarantees, we lay the foundation for principled pretraining and transfer learning across heterogeneous graph tasks.
j=
+ Ccc--1l11 (1-1) - 2 ( S 2B C1 C -1
C2 11'
where o is the GNN encoder, T, is the computation tree corresponding to node i, and Ci, are constants related to the encoder, and B2 represents the bounded norm of x.
We begin by examining the stability of GNNs in learning task-tree representations, showing that task-trees with sim- ilar subtree structures produce analogous embeddings. To facilitate this analysis, we first define the notation for de- scribing subtree information:
Theorem 3.1 (proved in Appendix D.I) suggests that two task-trees are likely to have similar representations if their subtrees are similar. This theorem highlights the signifi- cance of similarity between pairs of subtrees, while down- playing the impact of the number of subtrees (i.e., the width of the task-trees), despite having more subtrees could poten- tially 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).
1111 5
x
(3)
JEN
where 2!!" x; denotes the original node feature, and (0(1) denotes the subtree information of nodes in 1-th layer, as illustrated in Figure 2. In this figure, for i = 1, only the nodes in the first layer of the tree are considered, and for 1= 2, only the nodes in the second layer are considered.
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
Theorem 3.1 (Stability on bask-Trees.. Given two I--layer
4

---

Learning Generalities Across Graphs via Task-Trees
x (1)
two encoders exhibit similar losses during pretraining, their transferability to new task should be comparable.
Avg.
Avg-
Illustration 3.4. To give better understanding on why The- orem 3.3 imply the model pretrained on task-trees can bring transferable information to downstream tasks, we present an example. Let's 's consider the case where & is the pretrained encoder and ø' is a randomly initialized encoder. The LHS term minjer RT 6) mingrr RT(f oo') measures the amount of knowledge that is acquired during pretraining and is capable to be transferred to downstream tasks, and the RHS term mingge Lp(g 6) EG Lp(g' o') measures the total knowledge acquired during pretraining. Thus, the constants Cs and 5 quantify how much of this knowledge is transferable to downstream tasks. Since both Cs and are reasonably small, we conclude that pretrain- ing on task-trees provides sufficient knowledge to benefit downstream tasks.
x
x
Avg.
Avg.
Figure 2: subtree information examples.
(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 transfcrability of trsk-trees. Specif- ically, assuming a model is pretrained on a task-tree re- construction task', we aim to quantify how the knowl- edge acquired during pretraining can be transferred to downstream tasks. The pretraining objective is defined as Cg Φ) pxt. ((T)II, where P represents the task-tree distribution used for pretrain- ing, Φ E & and g E 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 ar- bitrary augmentations. Note that the reconstruction head g is used only during pretraining and is discarded during fine-tuning. Then, define the risk downstream task as (J Φ) == [<r_a)-T<<[[<(((T))), y). where J E F is a linear head for predictions, TT represents the downstream task distribution with task-tree T and label and x denotes the loss function.
To further explain why the task-tree- 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 TT for fine- tuning, suppose the encoder & pretrained on a set of task-trees mm sampled from P and finetuned on task- trees {Ti) sampled from T, the generalization bound of the finetuned model, with probability at least 1 U, is
Ry o 6) S min R PEF
log(1/u
+ 2C2
Σ - -Pa(t) + +21
n
4C1 +
n
+ Ca (E)()
(TT))
(6)
Theorem 3.3 (Transferability on Task-Trees) Given two trek-tree encoders o, o' E 4. we have
where "== arg aig mingeG Lp(g o Φ) is the optimal
=
minR Φ)) JEF
min RT o6) IEE
lask-tree encoder obtained on P. Eply, x) = [g o h) eing''G.e''e Lplg' Φ¹) defines the excess risk during pretraining. Constants C1 and C2 related to downstream tasks, while Cs RS O(1) and ê = are the same The- orem 3.3. Xg denotes the distribution of task-tree embed- dings encoded via o. and [[To(z)) -o(x)) measures the distance between task-tree distributions of pretraining and fine-tuning data.
C CC min Cr(g の)
min Cg o C o
(5)
gEG
eG
where Cs x 0(1) and 5
The proof is provided in Appendix D.2. In summary, Theo- rem 3.3 demonstrates that knowledge gained through pre- training 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 dif- ferent representations impact performance on downstream tasks, while the right-hand side (RHS) reflects the difference in pretraining losses between two encoders. Therefore, if
The proof can be found in Appendix D.3. This theo- rem outlines key factors affecting model generalization on downstream tasks, such as the transferability of task-trees (Cs(Ep(g, Φ))²) and the quality of the pretrained encoder (Ep(g, 6)). With regard to the number of task-trees, we find that while increasing the number of fine- fine-tuning samples con- tributes to more stable optimization 4C1 VE [lo())) it does not significantly reduce the generalization bound
'The scope of reconstruction task is large. We consider con- trastive learning is also kind of reconstruction.
5

---

Learning Generalities Across Graphs via Task-Trees
This provides theoretical evidence that a rea- sonable number of fine-tuning samples can be sufficient for training a model with strong generalization capabili- ties. Moreover, the discrepancy between the pretraining and fine-tuning distributions (zex, [T) (z) is mruiil--mallle distribution gaps lead to better general- ization. This highlights the importance of increasing the diversity of pretraining data, which provides a boarder pre- training 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.
log(1/12), (2 a
loss captures the semantics of the task-trees in a predictive manner, while the KL. regularizer ensures the embeddings are projected into shared space by minimizing the KL divergence between individual instances and their center.
4.2. GIT-S: Specification via Instruction Tuning
Theorem 3.5 highlights the relationship between model gen- eralization 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 as- sumption that graphs from the same domain have similar task-tree distributions (Tr.... Tn.. If the pretrained model is post- trainer on task-tree distribution Ppner sampled from [Ti... Ta J. the pretraining data distribution P can be adjusted towards these trsk-tree distributions. This reduces the discrepancy Σxex, (1 - -a)())l in Theorem 3.5, thereby improving model generalization on the target do- main. To achieve this, we propose instruction-tuning method for post-training the pretrained model.
4. Graph Generality Identifier on Task-Trees
The theoretical analysis establishes the feasibility of con- structing graph foundation models based on task-trees. Building on these insights, we develop the GIT model to empirically validate the Tree Generality Assumption.
To focus aligning task spaces across heterogeneous graph tasks, we adopt widely used text-attributed graph bench- marks (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 Mentence-BERT (Reimers & Gurevych, 2019). This design allows to isolate and examine the effect of task-tree-based pretraining while holding node features con- sistent across domains.
Instruction tuning is supervised fine-tuning (SFT) tech- nique 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 o* and set of task-trees {T ...., T, from the target domain, we post-train the model using the SFT loss:
4.1. GIT-G:
Pretraining to Acquire General Knowledge
CSFT = Σ (T))
(8)
We propose task-tree reconstruction task as a pretext for pretraining. The key is to use two corrupted task-trees to reconstruct each other, thereby capturing corruption- invariant semantics. Given a set of task-trees (Ti,.., sampled from a graph database, we apply corruption tech- niques generate two views of each task-tree, denoted as {2T ..., (., and ("f,... T.). 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 6 to obtain embeddings for the corrupted task- trees, resulting in {E,,.., &n} and {ž1,.... }. Inspired by (Thakoor et al., 2022), we perform reconstruction as
where vp is the instruction generation function for each task- tree, and x is the corresponding loss function. In this paper, as we use text-attributed graphs in our experiments, we de- fine instructions as the embeddings of label descriptions encoded by LLM, which is similar to Liu et al. (2024a), and we use mean squared error as the loss function K. Addi- tional model analysis is provided in Appendix B.
5. Experiment
5.1. Experimental Setup
Datasets. We conduct experiments on over 30 text- attributed graphs spanning five domains: academic net- works, e-commerce networks, knowledge graphs, molecular graphs, and temporal graphs. Pretraining is performed on diverse subset including Arxiv (academic), Products (e-commerce), WN1 8RR and FB1 5K237 (knowledge), and Chemblpre and PCBA (molecular). Specialization is eval- uated on representative datasets for each domain: Arxiv, Product s, FB1 5K237, and PCBA. For temporal graphs, which are e-commerce temporal graphs, we also use
1 n
L 2n [I((o(E))) sg(p(&))]1
n
Σ -[(p(((E))) sg(p( 1
where g is a non-lineat MLP projector, p(z) = (=/[|=]]) serves for normalization, sg is the stop-gradient operation, and h is the average of all instances z. The reconstruction
6

---

Learning Generalities Across Graphs via Task-Trees
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 Appendix
Domain
Academic
E-commerce
KG
Molecule
Temporal
Held-out Avg.
Avg.
Sup. GNN
GraphMAE
15.42
8.19
47.19
26.67
25.11
O-shot
OFA
13.98
8.73
50.49
27.20
26.14
GIT
14.88
8.79
53.34
28.56
27.50
GIT S
23.45
17.06
62.83
35.19
36.32
Sup. GNN
GraphMAE
49.25
48.20
56.56
56.01
40.31
50.15
52.07
3-shot
OFA
45.93
57.06
56.97
57.03
38.92
51.84
53.70
GIT
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
Sup. GNN
73.57
78.21
73.65
62.61
71.14
72.25
GraphMAE
73.81
76.57
72.61
71.41
62.75
71.37
72.79
Finetune
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
ACADEMIA
KG
MOLECULE
E-COMMERCE
TEMPORAL
GIT
90
67
Model Performance
Best Baseline
80
86
70
65
60
64
40
70
30
62
2
86
30
81
70
10
60
20
60
Choseer
Con
Pubroos
Anaz2
Codox-
Codaxdi
CodeaLL
BELL99
18151237
ICEW91619
CYP450
POSA
HN
TOX21
MUV
BRBP
TOXGAST
Sportalt
Producte
Photo
Hostry
Children
Emoon
Googlemap
Figure 3: 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/GATIGIN, BGRL, GraphMAF, and OFA.
Products for SFT to assess robustness under temporal distribution shifts. We provide the full dataset details in Appendix E.I.
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 down- stream data. In in-context learning (few-shot without fine- tuning), we randomly sample instances per class, compute prototype embeddings via averaging, and classify using nearest-prototype inference. Following Liu 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 learn- ing replaces prototypes with class description embeddings generated by an L.M.M 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.
Baselines. We compare against broad spectrum base- lines, including supervised GNNs (GCN (Kipf & Welling, 2017), GAT (Veličković al., 2018), GIN (Xu al., 2019)), self-supervised models (BGRL (Thakoor et al., 2022), GraphMAE (Hou et al., 2022)), and graph foun- dation 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 GraphSAGE (Hamilton et al., 2017) the encoder and repeat each experiment

---

Learning Generalities Across Graphs via Task-Trees
Table 3: Performance comparison to SOTA methods.
Table 4: Ablation study on training strategies, where the performance is averaged across all academic networks.
Academic
KG
Molecule
GraphPrompt+
74.80
74.78
72.99
Base Model
Expert Model
All in one
75.25
74.92
71.87
0-shot
3-shot
Finetune
0-shot
3-shot
Finetume
OpenGraph
74.64
71.38
72.84
GraphMAB
15,30
51.51
75.57
17.89
55.88
75.26
AnyGraph
75.01
74.30
72.49
OFA
14.19
50.15
75.12
17.26
54.88
75.97
GIT
15.36
53.31
75.53
18.38
55.10
75.47
GIT-
75.82
75.73
74.57
General Model
Specialized Model
0-shot
3-shot
Finetune
0-shot
3-shot
Finetume
GraphMAR
15.42
49.25
73.81
20.31
51.21
74.05
5.2. Main Results
OFA GIT
13.98
45.93
72.18
20.05
46.87
73.04
14.88
54,00
75.82
23.45
55.18
75.88
Domain- Wise Performance. Table 2 reports average per- formance across five domains, with detailed per-dataset results provided in Appendix F. The "held-out avg." de- notes the average score on all graphs excluded from pre- training and specialization, offering an unbiased evaluation of generalization. Notably, the general-purpose model GIT- G already outperforms strong baselines in several domains. With domain-specifit specialization, GIT-S achieves fur- ther gains- especially in zero-shot and in-context settings highlighting the benefits of post-training in adapting pre- trained models to specific domains. These results align with our theoretical findings, demonstrating enhanced adaptabil- ity through specialization.
addressing multiple aspects- e.g., domain shifts, modality fusion, and prompt engineering- GIT adopts targeted ap- proach centered on task alignment. Its core innovation lies in the use of task-trees, which provide unified abstraction across graph tasks.
5.4. Ablation on Training Strategies
We conduct an ablation study academic networks to eval- uate the impact of different training strategies. Specifically, we examine four approaches: (1) Base Model: Pretrain-
Dataset- Wise Performance. Figure 3 shows fine-tuning performance across all datasets. GIT consistently outper- forms the strongest baseline the majority of cases, validat- ing the effectiveness of task-trees generalizable learning units across heterogeneous graph tasks.
ing 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 specializa- tion 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. contrast, GraphMAE and OFA exhibit performance degradation when transitioning from the base and expert models to the general model. This find- ing 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.
Effect of Specialization. We summarize three key observa- tions: (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 special- ization approach to other models also yields performance improvements in specific domains (Table 4), showing the generalization of post-training in enhancing model capacity.
5.5. Comparison to Domain Experts
5.3. Comparison to Shate-of-The-Arr Methods
We compare GIT to domain experts in molecular and knowl- edge graphs, as these domains require domain-speciff knowledge. Our findings indicate that the specialized GIT (GIT-S) closely approximates the performance of these ex- perts. In molecular graphs. GIT-S achieves an average per- formance of 62.83, ranking second to the slate-of-the-an GIMLET (64.15) (Zhao et al., 2023) while outperforming other domain experts (Zeng et al., 2022; Su et al., 2022; Tay- lor 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 al., 2024), as shown in Table 23 Appendix.
To evaluate the effectiveness of GIT, we compare it against recent graph foundation models, including GraphPrompt+ (Liu et al., 2023), All One (Sun et al., 2023), OpenGraph (Xia al., 2024), and AnyGraph (Xia & Huang, 2024), under the mnetrain-then-fince Table 3, we benchmark GIT-G and all baselines across three representative domains: academic networks (node classifica- tion), knowledge graphs (edge classification), and molecular graphs (graph classification). GIT-G consistently outper- forms all competing methods across tasks and domains. While many existing models pursue broad generalization by
paradigm. As shown in
8

---

Learning Generalities Across Graphs via Task-Trees
Table 5: Performance comparison between methods with
GIT (Task-Tree)
GIT (Subgraph)
GraphMAE
different basic learning instances.
Memory Usage
Usage (%)
100
Instances
Subgraph
Tree
50
Domains
OFA
SubG
GIT Gree
Time (s) Epoch
Academia
72.18
73.48
75.82
Seconds
KG
72.38
73.59
75.73
250
Molecule
74.03
72.67
75.73
200
Held-out Avg.
71.31
70.88
73.81
2²
2
2
212
21
2
Avg.
72.93
73.01
75.33
Batch Size (log)
Figure 4: Training efficiency between task-tree and sub- graph versions of GIT.
Table 6: Results on non-text-attributed graphs.
Setting
GraphMAE
GIT-G
w/o SVD + w/o pretrain
95.02
94.27
SVD+ w/o pretrain
94.89
95.50
B (graph classification) and fine-tune on Cora (link pre- diction). Results, evaluated via AUC, confirm that GIT-G remains effective without relying on textual information, validating its broader applicability.
SVD+ pretrain
95.10
95.70
5.6. Task-Trees vs. Subgraphs: Efficiency and Performance
6. Conclusion and Limitations
We compare the efficiency and effectiveness of task-trees against subgraph-based learning units in the fine-tuning set- ting, as shown in Figure and Table 5. For a fair comparison, we implement a subgraph-based variant of our model, de- noted GIT-SubG, by substituting task-trees with subgraphs while keeping all other components unchanged.
We introduce task-trees as unified learning instances for aligning heterogeneous graph-based tasks, supported by both theoretical and empirical analyses. Based on this ab- straction, we develop GIT, a pretrained graph foundation model that leverages small set of source graphs to general- ize across over 30 datasets spanning five diverse domains. Our results demonstrate that task-trees preserve transfer- able patterns across tasks, offering a scalable and principled pathway for cross-domain generalization graph learning.
Experimental results across three coomains-acadeie (node classification), knowledge graphs (edge classification), and molecular graphs (graph task-trees consistently outperform subgraphs in both com- putational efficiency (Figure 4) and predictive performance (Table 5). This highlights the advantage of fask-trees in serv- ing compact, expressive, and structurally aligned learning instances, especially in cross-task and cross-domain gener- alization scenarios.
defiiiattiion-ddmmmsrssrrtet that
Limitations and Future Work. While task-trees serve as promising abstraction-analogae sentences in language sanuaageseveral although our results suggest that task-trees capture gen- cralities across tasks, pinpointing the precise transferable patterns remains an open question. Future work should ex- plore this from both theoretical and empirical perspectives. Second, transforming graph neighhorhoods into tree struc- tures may lead to information loss due to the limitations of message- paaaningg GNNs. This can affect model expressive- ness, especially for graphs with complex higher-order struc- tures. Incorporating more expressive architectures, such as higher-order GNNs (Morris et al., 2019; 2023) or advanced graph modeling (Wang al., 2025b), may help mitigate this issue. Finally, while GIT demonstrates strong performance with lightweight design, exploring more sophisticated variants-ed e.g., incorporating attention mechanisms, graph prompting, or task-conditioned decoders-offie exciting directions for extending the generality and adaptability of graph foundation models. We outline several of these op- portunities in Appendix C.
images in vision and several challenges remain. First,
5.7. Results on Non- Non-Text-Attributer Graphs
While prior experiments use text-attributed graphs, GIT does not inherently rely on textual information. We adopt text- attributed datasets to isolate the impact of task heterogene- ity, while sidestepping the confounding effects of feature heterogeneity, Textual attributes enable feature alignment across graphs via shared encoder, allowing us to more clearly assess the benefits of task-tree generalization. Im- portantly, 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-attribuee datasets-Pubbl (node classification), Citeseer (link prediction), and IMDB-

---

Learning Generalities Across Graphs via Task-Trees
Acknowledgments
Esser, P., Chennuru Vankadara, L.,, and Ghoshdastidar, D. Learning theory can (sometimes) explain generalisation in graph neural networks. In NeurIPS, 2021.
This work was partially supported by the NSF under grants IIS-2321504, IIS-2334193, IIS -S-2240346, IIS- IIS-2217239, CNS- CNS-2426514, and CMMI-2146076, and Notre Dame Strategic Framework Research Grant (2025). Any opinions, findings, and conclusions or recommendations expressed in this material are those of the authors and do not necessarily reflect the views of the sponsors.
Fan, Y., Ju, M., Zhang, C., and Ye, Y. Heterogeneous temporal graph neural network. In SDM, 2022.
Feng, J., Liu, H., Kong, L., Chen, Y., and Zhang, M. Taglas: An atlas of text-attributed graph datasets in the era of large graph and language models. arXiv, 2024.
Impact Statement
Freeman, L.
The development of social network analysis. Study in the Sociology of Science, 2004.
From an industry perspective, offer GIT founda- tional tool for graph-structured data. Additionally, since GIT can be quickly adapted to specific domains, we hope it will support applications where label acquisition is difficult and model training is time-consuming. There is no clear ethical considerations on the model architecture itself.
Galkin, M., Yuan, X., Mostafa, H., Tang, J., and Zhu, Z. To- wards foundation models for knowledge graph reasoning. In ICLR, 2024.
Garg, V. Jegelka, S., and Jaakkola, T. Generalization and representational limits of graph neural networks. In ICML, 2020.
References
Achiam, J., Adler, S., Agarwal, S., Ahmad, L., Akkaya, I.,
Guo, J., Du, I.., and Liu, H. Gpt4graph: Can large language models understand graph structured data? an empirical evaluation and benchmarking. arXiv, 2023.
Aleman, F. L., Almeida, D., Altenschmidt, J., Altman, S.,
Anadkat, S., al. Gpt-4 technical report. arXiv, 2023.
Cao, Y., Xu, J., Yang, C., Wang, J., Zhang, Y., Wang, C., Chen, L., and Yang, Y. When to pre-train graph neural networks? from data generation perspective! In KDD, 2023.
Gupta, M., Manchanda, S., Ranu, S., and Kodamana, H. Mirage: Model-agnostic graph distillation for graph clas- sification. In ICLR, 2024.
Hamilton, W., Ying. Z., and Leskovec, Inductive repre- sentation learning large graphs. In NeurlPS, 2017.
Chen, R., Zhao, T., JAISWAL, A. K., Shah, N., and Wang, Z. Llaga: Large language and graph assistant. In ICML, 2024a.
Hashemi, M., Gong, S., Ni, J., Fan, W., Prakash, B. A., and Jin, W. A comprehensive survey graph reduction: Sparsification, coarsening, and condensation. In ICCAI, 2024.
Chen, Z. Chen, L., Villar, S., and Bruna, J. Can graph neural networks count substructures? In NeurIPS, 2020.
Chen, Z., Mao, H., Liu, J., Song, Y., Li, B., Jin, W., Fatemi, B., Tsitsulin, A., Perozzi, B., Liu. H., et al. Text-space graph foundation models: Comprehensive benchmarks and new insights. arXiv, 2024b.
He, K., Chen, X., Xie, S., Li, Y., Dollár, P., and Girshick, Masked autoencoders are scalable vision learners. In CVPR, 2022.
Chen, Z., Wang, S., Shen, C., and Li, Fastgas: Fast graph-based annotation selection for in-context learning. In ACL 2024 (Findings), 2024c.
He, Y. and Hooi, B. Unigraph: Learning a cross-domain graph foundation model from natural language. arXiv preprini arXiv:2402.136633 2024.
Chuang, C.-Y. and Jegelka, S. Tree mover's distance: Bridg- ing graph metrics and stability of graph neural networks. In NeurlPS, 2022.
Hou, Z.,, Liu, X., Cen, Y., Dong, Y., Yang, H., Wang, C., and Tang, J. Graphmae: Self-supervised masked graph autoencoders. In KDD, 2022.
Deng, Y., Hong. J., Zhou, J., and Mahdavi, M. On the generalization ability of unsupervised pretraining. In AISTATS, 2024.
Hu, W., Liu, B., Gomes, J., Zitnik, M., Liang, P., Pande, V., and Leskovec, J. Strategies for pre-training graph neural networks. In ICLR, 2020.
Ding, K., Wang, J., Li, J., Shu, K., Liu, C., and Liu, H. Graph prototypical networks for few-shot learning on attributed networks. In CIKM, 2020.
Hu, Z., Fan, C., Chen, T., Chang, K.-W., and Sun, Y. Pre- training graph neural networks for generic structural fea- ture extraction. arXiv, 2019.
10

---

Learning Generalities Across Graphs via Task-Trees
Huang, Q., Ren, H., Chen, P., Kržmanc, G., Zeng, D., Liang, P. S., and Leskovee, J. Prodigy: Enabling in-context learning over graphs. In NeurIPS, 2023.
Morris, C., Geerts, F., Tönshoff, J., and Grohe, M. WI meet vc. In ICMI., 2023.
Ni, B., Liu, Z., Wang, L., Lei, Y., Zhao, Y., Cheng. X., Zeng.
Jin, W. Denr, T., Liu, H., Wang, Y., Wang, S.. Liu, Z., and Tang, J. Self-supervised learning on graphs: Deep insights and new direction. arXiv, 2020.
Q., Dong, L.., Xia, Y., Kenthapadi, K., al. Towards trust- worthy retrieval augmented generation for large language models: A survey. arXiv, 2025.
Ju, H., Li, D., Sharma, A., and Zhang, H. R. Generalization in graph neural networks: Improved pac-bayesian bounds on graph diffusion. In AISTATS, 2023a.
Qian, Y., Ma, T., Zhang, C., and Ye, Y. Dual-level hy- pergraph contrastive learning with adaptive temperature enhancement. In WwW, 2024.
Ju, M., Zhao, T. Wen, Q. Yu, W., Shah, N., Ye, Y., and Zhang, C. Multi-task self-supervised graph neural net- works enable stronger task generalization. In ICI.,, 2023b.
Qian, Y., Ma, T., Zhang, C., and Ye, Y. Adaptive graph en- hancement for imbalanced multi-relation graph learning. In CIKM, 2025.
Qiu, J., Chen, Q., Dong, Y., Zhang, J., Yang, H., Ding, M., Wang, K., and Tang, J. Gee: Graph contrastive coding for graph neural network pre-training. In KDD, 2020.
Kipf, T. N. and Welling, M. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
Levie, R., Isufi, E., and Kutyniok, G. On the transferability of spectral graph filters. In SampTA, 2019.
Reimers, N. and Gurevych, I. Sentence-bert: Sentence embeddings using siamese bert-networks. In EMNLP, 2019.
Levie, R., Huang, W., Bucci, L., Bronstein, M., and Ku- tyniok, G. Transferability of spectral graph convolutional neural networks. JMLR, 2021.
Rube, A. Perturbation bounds for means of eigenvalues and invariant subspaces. BIT Numerical Mathematics, 1970.
Li, Y., Wang, P., Li, Z., Yu, J. X., and Li, J. Zerog: Inves- tigating cross-dataset zero-shot transferability in graphs. In KDD, 2024.
Ruiz, L.,
Chamon, L., and Ribeiro, A. Graphon neural networks and the transferability of graph neural networks. In NeurlPS, 2020.
Liu, H., Feng. J., Kong, L., Liang, N., Tao, D., Chen, Y., and Zhang, M. One for all: Towards training one graph model for all classification tasks. In ICLR, 2024a.
Sohn, K., Berthelot, D., Carlini, N., Zhang, Z., Zhang, H., Raffel, A., Cubuk, E. D., Kurakin, A., and Li, C.-L. Fixmatch: Simplifying semi-supervised learning with consistency and confidence. In NeurlPS, 2020.
Liu, Z., Yu, X., Fang, Y., and Zhang, X. Graphprompt: Unifying pre-training and downstream tasks for graph neural networks. In WWW, 2023.
Song, F., Yu, B., Li. M., Yu, H., Huang, F., Li, Y., and Wang. H. Preference ranking optimization for human alignment. In AAAI, 2024.
Liu, Z., He, X., Tian, Y.. and Chawla, N. V. Can we soft prompt Ilms for graph learning tasks? In wWW, 2024b.
Srinivasan, B. and Ribeiro, B. On the equivalence between positional node embeddings and structural graph repre- sentations. In ICLR, 2020.
Luan, S., Hua, C., Lu, Q. Zhu, J., Zhao, M., Zhang, S., Chang, X.-W., and Precup. D. Revisiting heterophily for graph neural networks. In NeurlPS, 2022.
Su, B., Du, D., Yang, Z., Zhou, Y., J., Rao, A., Sun, H., Lu, Z., and Wen, J.-R. A molecular multimodal foun- dation model associating molecule graphs with natural language. arXiv, 2022.
Ma, T., Qian, Y., Zhang, C., and Ye, Y. Hypergraph con- trastive learning for drug trafficking community detection. In ICDM, 2023.
Ma, Y., Liu, X., Shah, N., and Tang, J. Is homophily necessity for graph neural networks? In ICLR, 2022.
Sun, M., Zhou, K., He, X., Wang, Y., and Wang. X. Gppt: Graph pre-training and prompt tuning to generalize graph neural networks. In KDD, 2022.
Mao, H., Chen, Z., Tang, W. Zhao, J., Ma, Y., Zhao, T., Shah, N., Galkin, M., and Tang, J. Graph foundation models are already here. In ICML, 2024.
Sun, X., Cheng, H., Li, J., Liu, B., and Guan, J. All in one: Multi-task prompting for graph neural networks. In KDD, 2023.
Morris, C., Ritzert, M., Fey, M., Hamilton, W. L., Lenssen, E., Rattan, G., and Grohe, M. Weisfeiler and leman go neural: Higher-order graph neural networks. In AAAI, 2019.
Sun, Y., Zhu, Q., Yang, Y., Wang, C., Fan, T., Zhu, J., and Chen, L. Fine-tuning graph neural networks by preserv- ing graph generative patterns. In AAAI, 2024.

---

Learning Generalities Across Graphs via Task-Trees
Tan, Z., Wang, S., Ding, K., Li, J., and Liu, H. Transductive linear probing: novel framework for few-shot node classification. In LoG, 2022.
Wen, Q. Ju, M., Ouyang, Z., Zhang, C., and Ye, Y. From coarse to fine: enable comprehensive graph self- supervised learning with multi-granular semantic ensem- ble. In ICML, 2024.
Tang, J., Yang, Y. Wei, W., Shi, L., Su, L., Cheng, S., Yin, D., and Huang, C. Graphgpt: Graph instruction tuning for large language models. SIGIR, 2024.
Xia, L. and Huang, C. Anygraph: Graph foundation model in the wild. arXiv, 2024.
Taylor, R., Kardas, M., Cucurull, G., Scialom, T., Hartshorn, A., Saravia, E., Poulton, A., Kerkez, V., and Stojnic, R. Galactica: A large language model for science. arXiv, 2022.
Xia, L., Kao, B., and Huang, C. Opengraph: Towards open graph foundation models. arXiv, 2024.
Xie, S. M., Raghunathan, A., Liang, P., and Ma, T. An explanation of in-context learning implicit bayesian inference. In ICLR. 2022.
Thakoor, S., Tallec, C., Azar, M. G., Azabou, M., Dyer, E. L., Munos, R., Veličković, P., and Valko, M. Large- scale representation learning on graphs via bootstrapping. In ICLR, 2022.
Xu, K., Hu, W., Leskovec, J., and Jegelka, S. How powerful are graph neural networks? In ICLR, 2019.
Yu, X., Zhou, C.,, Fang, Y., and Zhang, X. Text-free multi- domain graph pre-training: Toward graph foundation models. arXiv, 2024.
Touvron, H., Lavril. T., Izacard, G., Martinet, X., Lachaux, M.-A., Lacroix, T., Rozière, B., Goyal, N., Hambro, E., Azhar, F,, et al. Llama: Open and efficient foundation language models. arXiv, 2023.
Yuan, I.., Chen, D., Chen, Y.-I.,, Codella, N., Dai, X., Gao, J., Hu, H., Huang, X., Li, B., Li, C., et al. Florence: A new foundation model for computer vision. arXiv, 2021.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., and Bengio, Y. Graph attention networks. In ICLR, 2018.
Zeng, Z., Yao, Y., Liu, Z., and Sun, M. A deep-learning system bridging molecule structure and biomedical text with comprchension comparable to human professionals. Nature communications, 2022.
Wang, H., Feng, S., He, T., Tan, Z., Han, X., and Tsvetkov, Y. Can language models solve graph problems in natural language? In NeurIPS, 2024a.
Zhang, B., Gai, J., Du, Y., Ye, Q. He, D., and Wang. L. Beyond weisfeiler-lehman: quantitative framework for gan expressiveness, In ICLR, 2024a.
Wang, S., Chen, C., and Li, J. Graph few-shot learning with task-specific structures. NeurlPS, 2022a.
Zhang, C., Song. D., Huang, C., Swami, A., and Chawla, N. V. Heterogeneous graph neural network. In KDD, 2019.
Wang, S., Ding, K., Zhang, C., Chen, C., and Li, J. Task- adaptive few-shot node classification. KDD, 2022b.
Wang, Z., Zhang, Z., Chawla, N. V., Zhang, C.,, and Ye, Y. Gft: Graph foundation model with transferable tree vocabulary. In NeurlPS, 2024b.
Zhang, J., Chen, J., Yang, M., Feng, A., Liang, S., Shao, J., and Ying, R. Digh: A comprehensive benchmark for dynamic text-attributed graphs. arXiv, 2024b.
Wang, Z., Zhang, Z., Zhang, C., and Ye, Y. Subgraph pooling: Tackling negative transfer on graphs. In IJCAI, 2024c.
Zhang, M., Li, P., Xia, Y.. Wang. K., and Jin, L. Labeling trick: A theory of using graph neural networks for multi- node representation learning. NeurIPS, 2021.
Wang, Z., Liu. S., Zhang, Z., Ma. T., Zhang, C., and Ye, Y. Can llms convert graphs to text-attributed graphs? In NAACL, 2025a.
Zhang, Z., Wang, Z., Hou, S., Hall, E., Bachman, L., White, J., Galassi, V., Chawla, N. V., Zhang, C., and Ye, Y. Diet- odin: A novel framework for opioid misuse detection with interpretable dietary patterns. In KDD, 2024c.
Wang, Z., Zhang, Z., Ma, T., Chawla, V., Zhang, C., and
Ye, Y. Neural graph pattern machine, arXiv, 2025b.
Zhao, H., Liu, S., Chang, M., Xu, H., Fu, J., Deng, Z., Kong, L., and Liu, Q. Gimlet: A unified graph-text model for instruction-based molecule zero-shot learning. In NeurIPS, 2023.
Wang, Z., Zhang. Z., Zhang, C., and Ye, Y. Training mlps graphs without supervision. In WSDM, 2025c.
Wei, J., Bosma, M., Zhao, V. Y., Guu, K., Yu, A. W., Lester, B., Du, N., Dai, A. M., and Le, Q V. Finetuned language models are zero-shot learners. arXiv, 2021.
Zhao, H., Chen, A., Sun, X., Cheng, H., and Li, J. All in one and one for all: A simple yet effective method towards cross-domain graph pretraining. In KDD, 2024a.
12

---

Learning Generalities Across Graphs via Task-Trees
Zhao, J., Mostafa, H., Galkin, M., Bronstein, M., Zhu, Z., and Tang, J. Graphany: A foundation model for node classification on any graph. arXiv, 2024b.
Zhu, Q. Yang, C., Xu, Y., Wang. H., Zhang, C., and Han, Transfer learning of graph neural networks with ego- graph information maximization. In NeurIPS, 2021.
Zhu, Y., Xu, Y., Yu, F. Liu, Q. Wu, S., and Wang, L. Deep graph contrastive representation learning. In ICMI. Workshop, 2020.
13

---

Learning Generalities Across Graphs via Task-Trees
A. Related Work
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 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 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).
aggregate information from neighboring nodes to central nodes.
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 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 peneral-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 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- 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- non-parametric encoders (Zhao et al., 2024b), or synthesizing text- anttibtrr graphs (Wang et al., 2025a). Notably, 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 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 foundation model for reasoning tasks on knowledge graphs, using triplets as basic transferable patterns. Zhao et al. (2023) introduce a foundation model for molecular graphs, employing LLMs to align semantics between datasets and encode key motifs. In node classification, Li et al. (2024) propose a zero-shot learning foundation model, while Zhao et al. (2024a) present a feature alignment method based on SVD for node-level graph foundation models. Recently, Zhao ct al. (2024b) designed a foundation model for node classification using a non- parammeratricc classifier. Meanwhile, Chen et al. (2024a), Tang et al. (2024), Guo et al. (2023), Liu et al. (2024b), and Wang al. (2024a) have explored using LLMS as graph reasoners to solve graph tasks, similar their role in vision language models. While these methods excel at specific tasks or domains, they are not suitable 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.
14

---

Learning Generalities Across Graphs via Task- Bask-Trees
00407
NIN
(a) Similiarity between different datasets with varying weights.
(b) w.o. Reg
(c) Reg
==
A=1
1=10
0.50
NM
0.25
0.00
CORA
PUBMED
ARXIV
WIKICS
WN18RR
FB15K237
CHEMHIV CHEMPCBA
(d) The regularizer marginally affects the task structures for each datasct.
Figure 5: The domain regularizer controls the distance between datasets while preserving the structure within each of them.
Table Model performance across settings with different scaling weights of domain regularizer.
X = 0
À 10
O-shot
20.39
27.55
29.60
3-shot
53.10
57.53
60.21
Finetune
74.78
75.41
75.37
B. Additional Model Discussion
B.1. Why Does the General Model Need Specialization?
It is challenging for 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 example?. 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. networks, the semantic meaning of these triangles stable, following the principle of "the friend of my friend my friend"". However, in molecular graphs, the meaning of triangle patterns may be unstable due chemical properties. This pattern conflict can significantly degrade the performance of graph models (Cao et al., 2023; Mao al., 2024). Specialization helps resolve this issue by aligning the meanings of certain structural patterns with the semantics specific to the target domain.
social
B.2. More Analysis on Domain Regularizer
The Necessity of Domain Alignment. Datasets from multiple domains often projected into different subspaces, potentially due to misalignment of node attributes (Chen et al., 2024b) and the frequent patterns across domains. As 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.
TThis example was illustrated Cao et al. (2023)
15

---

Learning Generalities Across Graphs via Task-Trees
How to Regulate Domain Distances? We propose a domain regularizer to control domain distances by projecting cross- domain graphs with different characteristies 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:
h Basis = EED-PP (T.),
where P(D) represents the domain distribution, To is a distribution of task-trees within domain D, and ((T)) is the embedding of the task-tree T; Given the shared subspace basis, we optimize the KL divergence between each instance and the basis. However, obtaining the global basis vector Basis directly is impractical due to dataset size, so we approximate by averaging the embeddings of all instances within a batch compute the local basis Busis. We then optimize the KL divergence for all instances in the batch. To mitigate randomness, we empirically use relatively large batch size (4,096). Formally, the domain regularizer is defined as
Calign A Σ
(L) - 1 ΣΣ
H()
log
H() Z
(10)
[B]
BB
iEB
iEB
where B denotes the batch, and H and Z; represent the distributions of the local basis vector Basis and instance embedding Zi, 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 al. (2024a) for pretraining: Cora, Pubmed, Arxiv, Wikics, WN1 NRR, FB15K237, CHEMHIV, and CHEMPCEA. The analysis results are presented in Figure 5.
In the figure, we display (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 & 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 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 seootshot settings. In addition, we empirically find that 10 can lead to better performance. Thus, we set 10 as the default weight in this paper.
B.3. Discussion on Homophily and Heterophily
In node-level tasks, is important to consider both graph homophily and heterophily (Ma et al., 2022). Homophily describes the close relationships between connected entities, while heterophily refers distant relationships between connected entities. Empirically, basic paasagg GNNs tend to perform well on homophily graphs but struggle with heterophily graphs (Luan et al., 2022). Despite using GraphSAGE the backbone in our GIT, it still performs well on heterophily graphs, such as Children and Rat Ratinggs in 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 hest performance. We hypothesize that the proposed task-tree structure captures not only homophily relationships but also heterophily relationships. A potential question whether our pressage-passingg 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.
*Our collected graphs include two heterophily graphs, Chi Idren and Rat i ngs, with homophily ratios of 0.42 and 0.38, respectively, whereas other graphs generally have a homophily ratio greater than 0.60 (Table 12, (Chen et al., 2024b)).
16

---

Learning Generalities Across Graphs via Task-Trees
B.4. Discussion Model Expressiveness
Node-level Task. The task-tree structure is an approximation of the original graph structure, but converting graphs into tree structures inevitably results in some loss of information. To better preserve the structural details of the original graph, one could use more expressive advanced GNNs, thereby expanding the potential tree vocabulary (Mao al., 2024).
Edge-Ievel Task. Existing message-passing passing GNNs struggle with the edge isomorphism problem (Srinivasan & Ribeiro, 2020). For instance, in Figure 6, the links (0), v2) and (13, v14) are isomorphic, while (v1, U2) and (v), va) are not. However, when using& a mean aggregator to learn edge embeddings, the embeddings of (v1, U2) and (U1, v3) become indistinguishable. We consider that GIT may still encounter this issue, as the task-tres encoding currently averages the embeddings of task- relevant nodes. Addressing this challenge could involve techniques like Zhang al. (2021), which ensure that isomorphic edges have distinct embeddings without impairing the model's basic inductive learning capabilities.
Figure 6: Edge Isomorphic (Figure 1, (Zhang et al., 2021)).
Graph-level Task. passagg GNNs are limited by the 1-WL test (Xu et al., 2019), which can restrict their performance on graph-Ievel tasks. As we apply GraphSAGE the backbone, our GIT also encounters this limitation. Zhang al. (2024a) analyze the ability of different GNNs to detect graph substructures and conclude that more expressive GNNs, beyond the 1-WL test, learn graph embeddings with richer information. Therefore, improve model expressiveness, one can employ more expressive GNNs in our GIT. Additionally, techniques like Zhang et al. (2021) can be used to further enhance the model's 's discriminative capabilities.
B.5. Scaling Law
Model Size. We evaluated the model's performance with different hidden dimensions, with results by domain presented in Figure 7. The results cover both basic fine-tumin tt-innnng and in-context learning, and comprehensive details are provided in Appendix K. We observe that increasing the number hidden dimensions from 128 to 2,048 significantly improves model performance across all domains. We hypothesize that this improvement is due to the additional parameters, which enhance the model's ability to memorize shared patterns across graphs. The observation indicates the potential existence of scaling laws when using tase-trees as the basic learning instances.
Academia E-commerce
KG
Academia E-commarce
KG Molecule
Molecute
-00-
70
60
Performance
Performance
55
78
50
75
74
45
73
128
1024
Hidden Dimension
Hidden Dimension
(a) In-context Learning
(b) Finetune
Figure 7: The impact of model sizes on performance.
Data Size. We attempted to evaluate the scaling law by increasing the pretraining data, but unfortunately, we did not
17

---

Learning Generalities Across Graphs via Task-Trees
observe a clear trend where more data led to better performance. We consider there are three potential reasons. (1) From model perspective, we use 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 telk-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 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. Potential Model Extensions
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 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.c., 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.
C.2. Specialization via Instruction Tuning
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-textuaa graphs. Other methods could be explored to define instructions, such as using proxy models (Hu 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, 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 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 domain expert and 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.. ILAMA, GPT) that significantly improves catruction-folloiing capabilities. The success of this method in LLLMs 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.
18

---

Learning Generalities Across Graphs via Task-Trees
C.3. More Scenarios.
The paper leverages text-attributed graphs to align node features. However, the pre-processing of TAGs can be time- consuming, 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 GNN encoder d(-) with parameters W (W1, W2), we use GraphS architecture, defined as follows (with some notation abuse):
zi ((T a (W1 + W2 W PIGI
Σ () AEN;
where a is the non-linear activation function, xy is the node feature of node i, and M₁ represents the neighbors of node i, corresponding its children in the computation tree. The denotes the computation tree of node with layers. Neighborhood information is incorporated by averaging the embeddings of neighboring nodes. WLOG, the averaging operation can be replaced with any permutation invvrriinn set operation without affecting the analysis in this paper. For simplicity, 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 || S Br, and the model weights by || || S Bw, and ||2l S Bw:-- While real-world graphs typically exhibit varied node features, standard techniques (as employed in this paper) like normalization can ensure that B. remains small value. We define the distance between task-trees Ti with n task-relevant nodes {Ui,-.,, ) and T3 with m task-relevant nodes {ui,,., Um) as:
A = (TT)) (T)) = 1
Σ
(T))
where || ||||| is the L2 distance. Following, expand the stability term A as:
1 n
m O
(T.) Σ
A =
j=1
W + W2
Σ o(T+-11)
Σ о (WIT, + W2 Ny
Σ 6(T2-1)
Ni
REN,
j=l
REN
m
C,
W + We IN
Σ ((((-1)
Wia, W. W
Σ Q(T(-1))
kEAs
KEN,
< C.
Wiz:
WI x
j=1
(a)
+ C,
W
((TL-1)
W
Σ
-(T(-1)
KEN:
KEA;
(6)
Then, we separately analyze the term (a) and term (b).
The term (a) can be bounded as follows:
Term (a) C,
1
W1
1 Σ
Wi
<
C.Bwi
1
Σ
1
n
n 1=1
1=1
1=1
j=1
19

---

Learning Generalities Across Graphs via Task-Trees
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 the root). Next, we bound term (b):
Term (b) Co
Σ
Σ KEENG
((T(2-1)
Nil
m
KIEN
m
S CoBwa
(TT
Wil
N
KIEM.
j=l
K2EN,
BC
E o (WIEH + W2
E
Wi
N
KIEN;
sIENN
Σ K2EA
of WWi0N2 + W2
Σ
(TL2
Wi2
82EN22
m
$ CC
Wil
kIEN:
Ikl
m j=1
[
AREN,
D22
Co
1
Σ kIEN,
Σ
Σ
O(TLL
M
WEl
Wik
sle
k2E,N
s2EN22
(d)
Term (c) describes the distance between the average features of nodes in the second layer of the task-trees, while term (d) follows recursive formula, similar term (b). By combining terms (a) and (b), we have:
a
A C.Bwi
x2
m
+ C.BwwcCBB.
Σ
F&l
322
W
m
1=1
MEEM
j=1
12EN;
+ C.,Bw,C.Bw.
Σ
Σ
2(T2-2)
M
WKl
51
W
KIEM
sleNM
K2EN,
82E
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:
ACCAI +... CL-IIA--I.
(1I)
where A denotes the distance between task-trees at the 1-th layer. For clarity, can interpret A corresponding to Term (a) and C2 as corresponding to Term (c). Next, we explain how to determine C₁ and A for each layer.
By analyzing the recursive formula, we determine C₁ as follows:
Ci = C,Bwi1
C₂ C,Bw, x C.Bw.i
C1 = (CoBw,)' x C.Bwi-
20

---

Learning Generalities Across Graphs via Task-Trees
We then define the A,. For concise definition, we introduce an additional notation for describing the subtree information:
(0) Bis
2 I...T 2jEN, a. (2) INTT EjEN, anj
(2)
2 Wi ΣJEN, 2) (1-1))
By using the term, we can define the A as:
(0)
1 m
1=
j=1 2
42
D F.
(1) Eド=1
A =
E (t-1)
1 m
1== (11)
By using 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 {vI,..., Un and S2 = {ui,... Dm the following holds:
1
m
n
m
12
Uj
Us U/
m
nm
Proof. Let's consider sets {a), a2) and B {bi, b2). and
(a. a2)) b (b) b2)/2. We have:
a
bl = (aa + +22)/2 /2 (b) + b2)/21
|2a| + 2a - 2b + 2b //4
[(a b1) + (a1 b2) + (a2 b1) + (a2 b2)
S (Ila: bill + ||a bell + || b, || a| b b2
WLOG, this analysis can be extended to cases where the size of n and the size of B is m.
Based on the Lemma, we have
A
C1
m Σ 2
1
(0)
|| + ... C.C.
Σ x (1-11)
1 (I. D1
Σ a
n
m
C
(0)
8. (0)
+ ... +ick (4-1)
x0
(0(4-1111 11)
which is displayed in Theorem 3.1.
We then use the Lemma to bound the A, For example, the upper bound of A is:
m
A
(0)
(0)
m
1=1
(0)
7m
<1
(0)
+ 12 (0))) S 2B..
1=
21

---

Learning Generalities Across Graphs via Task-Tree
Similarly, the upper bound of Ag is:
17 71
A2
(1)
(1) j=1
m
2
nm
ΣΣ
Σ
ا
(0)
(1)
=1
ΣΣ nm =ر d.d,
Σ
x.
(0) 2B.
S
EN,, EN
where d; = JV] and d3 = MV] represent the number of children (i.e., the degrec) of nodes and respectively. Thus, the upper bound of A is:
Σ EN,
Σ
Σ
(0)
x (0 k5c
|| S 2B
mm
d,jj
d duaidagw by
E. gp
(1-1)x
Now we can have the highest upper bound of A as:
A (C1 + C2 +... + Cr)2B2
(C,Bw: +... + Bw,)
Cy )2Bx
2B, CoBw, (C, -
B.
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.
D.2. Proof of Theorem 3.3
Proof. We begin by restating the notations used in the theorem. Let represent the task-tree distribution, the downstream task distribution, O the GNN encoder, G the predictor head used during pretraining, and f E F the predictor head for the downstream task. The pretraining objective is defined as Lp(g Φ) == E (T) (l(()(T)) - (T)) where T is the task-tree and / is the corresponding corrupted task-tree obtained via arbitrary corruption functions. The risk on the downstream task is defined as Rf(f o d) := (ETT,))xx((((((T)) y). where T is the task-tree, 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 's Trace Inequality (Ruhe, 1970)). If and Y are positive semi-definite Hermitian matrices with eigenvalues, Φ 22 2 2 In 2 0 and y1 2 82 2 Un 2 then
n
Jdhn-441 S tr(XY) <
Eahi
Note that we are going to prove
min (f(
min R o0) s Co fezF
(mi Lr(g Φ))
min
Lg o )
JEF
D'EG
22

---

Learning Generalities Across Graphs via Task-Trees
where C3 ((1) and 6 = 3.2 The proof involves deriving the upper bound for the term minjer R Φ) min r d followed by the lower bound for mingeG L (g 6) ming'eG Lp Φ¹). To simplify the proof, we assume the downstream task is binary classification task, though this approach can be extended to multi-clasiffcatiinn scenarios.
We analyze the upper bound of sin (f o minger R o @ as follows:
min RT Φ) min PEF (
JEF (Tx(F(((T)) min
min
JEF (F)(((((()))
JEF
where (T. ~ T and k(f(((T))) is shorthand for (T))) y) for notational convenience. Since we define f E F as linear predictor for binary classification, we can rewrite this equation in the following form:
min B
Erx(O) o(T)) min Eyx(eT (T(()T)T((T) B
< min ET T ((T) - 00 d(T)
ET (T) - o OTT(T)²
< min
[
min = (BT(TT((T)) ( ((
= min
V (0)0
A A E(((T) 3X00-01.--B30000001---0000011110
B[o(T)((TT]
Note that the previous formula, we define = the minimum of 0 ( 3 2024). We can select sufficiently large Bg ensure an adequately large function space. Additionally, we define O' the optimal head for the encoder ø'. The expression v rr A0' is equivalent to (r((ATTT)) 0"), which can be further simplified using Proposition D.2.
Under the unconstrained setting, 20 o reduces to 0"T A0' (Deng al.,
0' 0' (T))
tt((OTT))
Σ (A)) s /o (a) (A)
where o, is the i-th eigenvalue for the matrix and maax denotes the maximum eigenvalue.
Then, we are going to demonstrate the lower bound of mingeg Lp(g o Φ) mingee Cr o d').
min o σ) gEG
min Lr(g' d') min Ep (((())))())))))))))))) - ([T) min Ep - gEG
g'EG
g'EG
where (i, P. Here we also consider the predictor g linear function, so that have the following form:
min EW
EpllWo(T) <(T)]I
min Wi
EpIlW' 2(T))12
min WW
[ 2'
min Ep w o(T) :./ 2'(2)11
min Ep (())) w. + wtJ o w. 2w, o(T)o'( Tw()
(
2
23

---

Learning Generalities Across Graphs via Task-Trees
where Cp = (T) (T)]l
is constant, and W is defined as the optimal transformation matrix for the encoder ø'. Based on this formula, can further simplify the bound
w T Aw, tr(A Σ w.
w 2 Tmax min
w ww
Now that we have the upper bound for mir (y o minyer ( o o') お) EG Lp(g's o )¹), we can establish the relationship between them as follows:
and the lower bound for mingee (g
min RT oO) min RT (f
fef
fe
do (0'O')
0
(min Lr(g o Φ) min Lr(s' o²)). 9EG
Ex= w w
g'EG
Umin
Based on our definition, 0' and W' are optimal heads for the encoder Ø', the complexity term o V dd would be constant which in the order (())
Voonn whe
D.3. Proof of Theorem 3.5
Proof. We begin by introducing some essential notations. Let represent the pretraining task-tree distribution and the downstream task-tree distribution. The pair (T, y) TT denotes task-tree and its corresponding label, where define the labeling function as vh, meaning y (T"). The GNN encoder is á E Φ the pretraining predictor is G, and the downstream predictor head is f E 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 (f o Φ) = =F where k is a loss function.
Then, define the excess risk on the downstream distribution T as
&( () RT( ob)
min ME
RT(s' o0))
- -Rr oo)
RT )0')
min Rf o) min R o6) feeF
min
r'F
J'EF
mmn Rp o x)
min
Rp o v))
min Rp o x
min Rp ( )04))
PeF
Pet
fet
RT(fo o o)
min Per
Rr (f' o 6) + min R RT o) - min Rp (f' o))
Pet
eeer
(a)
+
Ro(f' Φ) min R R o x*) + min Rolf' )0)) Per
min
Rr(F'o0) meF
min
Per
Per
where o and represent encoder obtained during pretraining and the prediction head learned in downstream task, respectively, while o' and f' are the optimal encoder and predictor head on the downstream distribution. o* is the optimal encoder obtained during pretraining, defined as 6* arg min mingeg Lr(g 6). 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
Σ ex ((T)) ((T))
Ri EeE(+1]"
sup fEF n
where E i.d. and P(e = 1) P(s -1) =
24

---

Learning Generalities Across Graphs via Task-Trees
Using this definition, can bound the term (a):
Term (a) Rf o)
min R ( o6)
F'EF
- - o RT o6) min RT o ))( RT oo).
y'et
10.1)
(a.3)
(a.2)
where f the optimal predictor head over the distribution T, defined as f = arg minjer Rf o o). 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 constant greater than or equal to Term (a.1) and (a.2) describe the gap between the risk and the empirical risk. According to uniform convergence, these terms be expressed in terms of empirical Rademacher complexity. Thus, term (a) be bounded as:
log(1/o)
Term (a) 4 + 4B,
where Bx the bound of the Lipschitz of loss function We then further simplify the empirical Rademacher complexity for reasonable expression.
1
log(1/v)
Term (a) S4B
sup fEF i=1
Σ ex o ((T:), ((T)), + 4B,
ff ((T:)) + +4B,1 log(1/0)
<AC,Bee(L1)=
sup fEF
1=1
+ +4BB log(1/v)
-
(ip(Ti)
1=1
4
fog(1/v)
C.C,Bee(+11)
(T:(
+4B,
As the & are i.i.d. with zero mean as our definition, we cancel the term, thus
Σ o(T))) 2 + 4B,
log(1/v)
Term (a) S C,C,
n
Then, we bound the term (b). To do this, we introduce notation f3 arg Rp(s h).
Term (b) min RT(l' ②) - min Rp oΦ)
PEF
fet
SR - RR Φ)
=BTuT
k o (T), (T)) - ETTP k(55 (TT) (17
-ENTT
((f((z).0(1))
-EENPo o(f((z).
<B. Σ xE
-P)
where B,, represents the upper bound the Lipschitz constant of K, and Xx denotes the distribution task-tree embeddings produced by the encoder ø. This term measures the distributional distance of task-trees between the pretraining and downstream distributions.
25

---

Learning Generalities Across Graphs via Task-Trees
Following, we bound the term (c),
Term (c) = min Rp o6) - min Pee
Rx (f o
Pe
SCs min Cplg' hh)
min WEEG
min Crlg o x))) d'EG
<Cs (C g'EG,
min
Crld' )
The term (g(g o h) mineee, (g o ) describes the excess risk on pretraining task, which can be replaced by notation (g, Ø).
Lastly, we bound the term (d),
Term (d) min Rp o x²)
min RT o o')
P'FF
FEF
min Rp / o oΦ)) PeB
min PeE
R o x*)
min RT o0))
min Pet,EE
RT(F'
feet
<BR
Σ x
To(x) -
min R7 (f' o x¹) f'FF
min J'EFWee
RT(F'o
By combining the four terms, obtain the generalization bound for model pretrained on task-tree distribution P and fine-tuned on task-tree distribution T:
Rr( < Co (E) AC,C,
|CTD)|
+ min Pet
RT( ( x8)
+2B,
Σ
To( - Po(l)]| + 2/
log(1/u)
n
xEN
We can C1 CzCy and C2 B, as two downstream task-related constants.
E. Experimental Settings
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 Rat ings as heterophily graphs due to their relatively low homophily ratios (Chen al., 2024b).
Splitter. For each dataset, we the same splitting strategy as provided in the original paper (Chen al., 2024b; Galkin et al., 2024; Feng et al., 2024; Zhang al., 2024b). If multiple splits are provided, we evaluate model performance on each split using different random seeds. For datasets with single split, we repeat the experiments five times with different random seeds. For GDELT and ICEWS1811 which are originally temporal knowledge graphs, we apply an 80%/10% split based on timestamps for train/validationneest settings. For the temporal graphs Enron and Googl emap 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.
E.2. Baselines
BASELINES APPLICABLE FOR ALL GRAPHS
GCN (Kipf Welling, 2017). A supervised message- paasaigg GNN trained from scratch for each task. As a result, cannot be applied to in-context learning or zero-shot learning.
26

---

Learning Generalities Across Graphs via Task-Trees
Table 8: Statistics of 32 graphs used in the paper.
Dataset
Domain
Task
# Nodes
Edges
# Classes
Task- Trees
Source
Products
E-commerce
Node, Link
316.513
19,337,745
39
316.513
(Chen et al., 2024b)
History
H-commerce
Node, Link
41,551
503, 180
12
41,551
(Chen et al., 2024h)
Children
E-commerce
Node, Link
76.875
2,325,044
24
76,875
(Chen et al., 2024b)
Computer
R-commerce
Node, Link
87,229
1,256,548
10
87,229
(Chen et al., 2024h)
Photo
E-commerce
Node. Link
48,362
873.793
12
48,362
(Chen et al., 2024b)
Sportsfit
E-commerce
Node, Link
173,055
3,020, 134
13
173,055
(Chen et al., 2024h)
Ratings
E-commerce
Node, Link
24,492
186,100
24,492
(Chen et al., 2024h)
Arxiv
Academia
Node, Link
169.343
2,315,598
40
169,343
(Chen et al., 2024b)
Cora
Academia
Node, Link
2,708
10,556
2,708
(Chen et al., 2024b)
Citeseer
Academia
Node, Link
3,186
8,450
6
3,186
(Chen et al., 2024b)
Pubmed
Academia
Node, Link
19,717
88,648
19,717
(Chen et 2024h)
Arxiv 23
Academia
Node, Link
46,198
77.726
40
46,198
(Chen et al., 2024b)
DRLP
Academia
Node, Link
14,376
431,326
4
14,376
(Chen et al., 2024b)
WN18RR
knowledge Base
Link
40,943
93,003
11
93,003
(Galkin al., 2024)
FB15K237
knowledge Base
Link
14,541
310,116
237
310,116
(Galkin et al., 2024)
Codex Small
knowledge Base
Link
2,034
36,543
42
36,543
(Galkin al., 2024)
Codex Median
knowledge Base
Link
17,050
206,205
206,205
(Galkin et al., 2024)
Codex Large
knowledge Base
Link
77,951
612,437
69
612,437
(Galkin et al., 2024)
NELL995
knowledge Base
Link
74,536
153,039
200
153,039
(Galkin al., 2024)
GDELT
knowledge Base
Link
5,849
943,956
237
943,956
(Zhang et al., 2024b)
ICEWS1819
knowledge Base
Link
31,796
1,100,071
266
1,100,071
(Zhang et al., 2024b)
Chemblpre
Molecule
Graph
8,845.648
19,123,034
1,295
341.952
(Feng et al., 2024)
PCBA
Molecule
Graph
11,349,235
24,566,048
128
437,092
(Feng et al., 2024)
HIV
Molecule
Graph
1,049.163
2,259,376
41,127
(Feng al., 2024)
BBBF
Molecule
Graph
49,068
105,842
2,039
(Feng et al., 2024)
BACE
Molecule
Graph
51,577
111,536
1,513
(Feng et al., 2024)
TCXCAST
Molecule
Graph
161,002
330,180
588
8,575
(Feng et al., 2024)
CYP450
Molecule
Graph
414,367
895,886
5
16,896
(Feng et al., 2024)
TCX21
Molecule
Graph
145,459
302,190
12
7,831
(Feng al., 2024)
MUV
Molecule
Graph
2,255,846
4,892,252
17
93,087
(Feng et al., 2024)
Enron
Temporal
Link
42,712
797,907
10
797,907
(Zhang el al., 2024b)
Googl emap
Temporal
Link
111,169
1,380,623
1,380,623
(Zhang al., 2024b)
GAT (Veličković et al., 2018). A supervised GNN that uses an attention mechanism to learn the importance of received messages.
GIN (Xu 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 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 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 expert model for molecular graphs.
MoMu (Su al., 2022). Another expert model for molecules that leverages GNNs to improve molecular representations.
Galactica (Taylor et al., 2022). foundation model for molecular graphs that utilizes multi-task learning with instructions.
27

---

Learning Generalities Across Graphs via Task-Trees
15000
200000
Nodes
Edges
100000
Snapshot Index
Snapshot Index
Max degree
Density
0.006
20000
0.004
10000
0.002
0.000
3
2
Snapshot Index
Snapshot Index
(a) Enron
60000
Nodes
Edges
200000
100000
20000
2
Snapshot Index
Snapshot Index
Max degree
300
0.00010
Density
200
0.00005
100
0.00000
2
Snapshot Index
Snapshot Index
(b) Googlemap CT
Figure& 8: The statistics of temporal graphs.
GIMLET (Zhao et al., 2023). A foundation model for molecules that incorporates advanced models and instruction-based learning.
E.3. Evaluation Protocol
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 commerce networks, FB15K237 for knowledge graphs, and PCBA for molecular networks. For temporal graphs, which eccommerce-based we also use Products for SFT to evaluate robustness under temporal distribution shifts.
Backbone. We use a GraphSAGE-lik 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 Googlemay 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.
E.4. Evaluation Settings
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.
28

---

Learning Generalities Across Graphs via Task-Trees
Table 9: The hyper-parameters used in the pretraining.
Hidden Dim
Layers
Dropout
Activation
Epochs
LR
768
2
0.15
ReLU
10
le-7
Feature Drop
Edge Drop
X
Decay
BS
Fanout
0.2
0.2
10
1e-8
4,096
10
Table 10: The hyper-parameters used in fine-tuning academic networks.
Academia
Cora
Citeseer
Pubmed
Arxiv23
DBLP
Arxiv
Normalize
None
BN
None
None
None
BN
Learning Rate
le-4
le-4
le-5
le-4
le-4
le-3
Weight Decay
le-6
1e-6
le-6
Epochs
1000
1000
1000
1000
1000
1000
Early Stop
200
200
200
200
200
200
SFT Learning Rate
1e-7
le-4
le-6
1e-5
le-7
1e-6
SFT Epochs
100
100
100
100
100
100
Table 11: The hyper-parametters used in fine-tuning e-commerce networks.
E-commerce
History
Children
Computer
Photo
Sportsfit
Ratings
Products
Normalize
None
None
None
None
BN
BN
BN
Learning Rate
1e-3
le-4
1e-3
le-4
le-4
le-4
le-4
Weight Decay
1e-6
1e-6
le-6
1e-6
1e-6
Epochs
1000
1000
1000
1000
1000
1000
1000
Early Stop
200
200
200
200
200
200
200
SFT Learning Rate
le-5
le-7
1e-7
1e-7
1e-8
1e-7
1e-7
SFT Epochs
100
100
100
100
100
100
100
In-context Learning. This is kind of few-shot learning without fine-tuning the model parameters. We randomly select k samples from 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 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 in-context learning, yet we use the I.MMMencoded class description embeddings the prototypes for prediction. Similar in-context learning, also randomly sample 500 tasks for evaluation. Another zero-shot setting involves using an additional LLM for zero-shot inference (Chen al., 2024a). We leave this in our future work.
E.5. Slype-Parameete
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 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 weight decay of le-6 and tune the learning rate from le-3, 1e-4, le-5, reporting the best performance. For methods with attention mechanisms, we set attention heads.
GIT. The model architecture and pretraining parameters of our GIT are presented Table 9. The specific fine-tuning
29

---

Learning Generalities Across Graphs via Task-Trees
Table 12: The hyper-parameters used in fine-tuning on knowledge graphs.
KG
WN18RR
Codex-S
Codex-M
Codex-L
NELL995
GDELT
ICENS1811
FB15K237
Normalize
BN
BN
BN
BN
BN
BN
BN
BN
Learning Rate
le-4
le-4
le-3
le-3
le-3
le-3
Weight Decay
Ie-6
Ic-6
lc-6
Ic-6
0
lc-6
1c-6
Epochs
1000
1000
1000
1000
1000
1000
1000
1000
Early Stop
200
200
200
200
200
200
200
200
SFT Learning Rate
le-8
le-7
le-5
lc-7
le-8
lc-4
1e-8
lc-7
SFT Epochs
100
100
100
100
100
100
100
100
Table 13: The hyper-parameters used in fine-tuning on molecule graphs.
Molecule
BBBP
BАCE
TOXCAST
TOX21
CYP450
HIV
MIV
PCBA
Normalize
BN
BN
BN
BN
BN
BN
None
BN
Learning Rate
le-3
le-4
le-4
le-4
le-4
le-5
le-4
le-5
Weight Decay
1e-6
0
1e-6
1e-6
1e-6
0
0
Epochs
300
300
300
300
300
300
300
300
Early Stop
30
30
30
30
30
30
30
30
SFT Learning Rate
1c-7
1c-6
1c-8
1e-7
1c-7
1e-7
1e-6
1c-7
SFT Epochs
10
10
10
10
10
10
10
10
Table 14: The hyper-parameters used fine-tuning on temporal graphs.
Temporal
Enron
Googlemap CT
Normalize
None
None
Learning Rate
le-3
1e-3
Weight Decay
le-6
le-6
Epochs
1000
1000
Early Stop
200
200
SFT Learning Rate
le-6
1e-6
SFT Epochs
100
100
hyperparameters, categorized by domain, are shown in Tables 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 Ie-4, le-5, le-6, le-7, 1e-8, and the normalization method from None, BN.
F. Comprehensive Model Results
F.1. Domain: Academia
Node Classification. We perform node classification 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.
30

---

Learning Generalities Across Graphs via Task-Trees
Table 15: Node classification results on academic networks in terms of accuracy.
Cora
Citeseer
Pubmed
Arxiv23
DBLP
Arxiv
Avg.
GCN
BGRL
14.37 = 0.38
15.09 = 0.40
33.94 0.46
2.44 0.23
25.53 0.27
2.10
15.58
GraphMAE
13.88 = 0.41
13.48 = 0.83
32.62 0.67
2.51 = 0.37
27.83 0.40 0.40
2.17
15,42
0-shot
OFA
14.58 + 0.43
13.28 = 0.12
30.89 0.10
2.08 = 0.03
21.00
2.05
13.98
GIT
15.31 = 0.27
16.04 = 0.31
29.66 0.60
2.89 0.25
21.80 = 0.35
3.57 = 0.18
14.88
GIT
18.26 0.29
20.35 0.29
39.12 0.55
9.08 0.32
36.40 = 0.58
17.50 0.66
23.45
GCN
BGRL
61.24 0.50
44.97 =: 0.43
54.55 0.81
43.17 = 0.93
42.89 = 0.61
59.09 = 0.24
50.99
GraphMAE
62.02 + 0.58
44.08 0.59
55.98 0.68
31.64 0.28
38.16 0.54
63.62 0.79
49.25
3-shot
OFA
55.92 = 0.40
0.32
40.89 = 0.79
37.01 = 0.41
33.08
57.08 0.48
45,93
GIT G
60.93 = 0.47
48.32 = 0.53
60.30 = 0.76
45.62 = 0.35
44.76 0.54
64.07 # 0.50
54,00
GIT S
63.23 + 0.29
49.55 0.33
59.62 0.54
47.21 = 0.31
47.40 = 0.43
64.06 = 0.58
55.18
GCN
77.40 + 1.36
80.19 1.30
72.44 2.08
71.61 0.02
68.15 = 0.14
71.65 0.02
73.57
BGRL
71.06 + 2.84
80.56 = 1.59
68.75 3.669
6.19
#.00
67.6220..1
68.81
GraphMAE
76.34 + 1.49
79.19 1.32
73.88 1.16
71118 7..46
0.00
73.81
Finetune
OFA
70.63 = 1.03
79.13 = 2.53
70.95 1.02
7..43
70.67
72.18
GIT G
78.74 = 1.12
81.03 0.78
75.26 2.81
2.81
72.49 0.07
74.42 0.15
72.99 0.10
75.82
GIT -
78.90 # 1.44
81.97 # 0.80
76.17 1.70
71.50 = 0.08
73.59 = 0.08
73.13 # 0.11
75.88
Link Prediction. We present the link prediction results, measured by AUC, academic networks. in Table 16. The train/val/test sets randomly split in a 70%/15% ratio. GIT outperforms all baselines across all settings. Additionally, the specialized GIT surpasses the general GIT, highlighting the potential of specialization to enhance performance other tasks within the same domain. This finding underscores the cross-task transferability of the proposed specialization process.
Table 16: Link prediction results on academic networks in terms of AUC.
Cora
Citeseer
Pubmed
Arxiv23
DBLP
Arxiv
Avg.
GCN
87.34 # 0.88
87.52 + 0.98
84.41 0.17
89.67 # 0.24
98.29 + 0.07
97.50 0.08
90.79
BGRL
83.96 # 0.36
81.51 # 0.85
84.01 0.60
86.42 # 0.08
97.24 # 0.06
96.80 # 0.04
88.32
GraphMAE
85.57 # 0.27
84.55 # 0.69
89.83 0.35
91.45 = 0.44
98.05 = 0.06
96.31 0.02
90.96
OFA
82.82 = 0.72
81.52 # 1.16
84.78 + 1.08
85.40 = 0.62
97.23 + 0.14
96.46 0.05
88.04
GIT G
87.79 + 2.07
87.59 0.96
84.35 0.26
91.47 0.46
98.25 + 0.09
97.14 0.06
91.10
-
88.58 + 1.88
88.50 + 1.15
87.78 0.13
91.86 # 0.38
98.27 + 0.05
97.30 0.05
92.05
F22 Domain: E-Commerce
Node Classification. The comprehensive node classification results on e-commerce datasets are presented in Table 17. Our proposed GIT model outperforms the baselines in most settings, particularly for the specialized version. Specialization significantly improves performance in zero-shot and in-context learning, highlighting the advantages of using task-trees as the basic learning instances. the basic fine-tuning setting, we also observe that supervised methods (GCN and GAT) generally outperform self-supervised methods, such as GraphMAE (Hou et al., 2022) and OFA (Liu et al., 2024a), indicating the occurrence of negative transfer. However, GIT surpasses these supervised methods on 5 out of 7 datasets, further demonstrating the benefits of task-trees as basic learning instances. It it important note that we consider Chi ldren and Rat i ing as heterophily graphs (Chen et al., 2024b) due to their low homophily ratio.
Link Prediction. The link prediction results on e-commerce networks (Hi (History Photo, Ratings are presented in Table 18. We randomly select 70% the edges for training, 15% for validation, and the remaining 15% for testing. Our GIT model achieves the best average performance across these three e-commerce graphs. However, other baselines like BGRL,

---

Learning Generalities Across Graphs via Task-Trees
Table 17: Node classification results on e-commerce networks in terms of accuracy.
History
Children
Computer
Photo
Sportsfit
Ratings
Products
Avg.
GCN
GAT
BGRL
0.18
4.14
9.30
6.32 +
+.31
17.50
0.19
7.58
O-shot
GraphMAE
9.20
4.15
7.86
8.02 0.40
7.70
20.26
0.07
8.19
OFA
0.52
4.22
1..83
8.46
0.28
18.4
3.33
8.73
GIT
0.32
0.19
11.78 0.26
0.10
2.06
3.24
8.79
GIT
9.94 0.54
7.49 0.12
= 0.40
9.69 = 0.22
9.23 0.65
21.55
46.62 = 1.06
17.06
GCN
GAT
BGRL
0.53
32.93 = 0.75
50.90 0.82
61.64 0.51
21.67 0.21
71.71 = 0.23
45.74
3-shot
GraphMAE
42.28 0.38
38.71 + 0.49
58.24 + 0.79
59.47 a 0.25
46.57 + 0.46
21.11 + 0.56
71.01 = 0.67
48.20
OFA
48.87 d: 0.26
47.13
6.49
75.73 0.24
6 0.57
21.38 0.16
57.06
GIT
50.78 0.41
47.55 # 0.26
66.64 = 0.50
75.43 +
64.56 + 0.43
21.21 # 0.37
74,35 = 0.48
57.22
G
50.99 + 0.64
47.65 0.36
69.29 = 0.48
76.32 + 0.55
65.84 + 0.53
21.17 0.40
74.80
0.54
58.01
GCN
84.62 0.06
58.08 0.08
88.41 0.06
86.39 + 0.11
92.07 0.02
50.99 #
86,91 = 0.05
78.21
59.09 8.05
89.00 0.04
86.70 0.07
91.12
87.22 5.119
78.41
GraphMAR
82.51 # 0.05
0.09
84.31 0.06
83.26 + 0.06
90.47 0.03
0.299
86.30 0.07
76.57
Finetune
OFA
55.43 82.81 + 0.11
85.78 0.13
83.21 + 0.25
91.23
51.79
86.23
76.64
GIT
84.94
0..19
85.66 0.100
0.06
92.17
5.245
87.75 0.04
78.61
GIT
85.18 = 0.11
5.17
88.05 0.18
85.66 + 0.05
92.44 = 0.02
52.56
88.20 = 0.05
78.83
GraphMAE, and OFA fail outperform the basic GCN. This may because they struggle to acquire useful knowledge during pretraining for tasks that require structural insight, such link prediction. These results underscore the advantages of using task-trees as the basic learning instances.
Table 18: Link prediction results e-commerce networks in terms of AUC.
History
Photo
Ratings
Avg.
GCN
97.87 = 0.06
97.37 # 0.03
97.77 + 0.07
97.67
BGRL
96.40 = 0.08
97.58 # 0.04
98.05 + 0.04
97.34
GraphMAE
97.59 = 0.06
95.35 98.09 # 0.05
97.01
OFA
95.86 # 0.09
97.05 # 0.06
0.12
96.90
GIT G
96.55 0.07
96.24 # 0.05
98.45 0.07
97.08
GIT
97.08 0.05
97.80 # 0.06
98.49 0.10
97.79
F.3. Domain: Knowledge Base
Edge Classification. The edge classification results on knowledge graphs are presented in Table 19, In this domain, our GIT model significantly outperforms the existing baselines, demonstrating the advantages of using task-trees as the basic learning instances for knowledge bases, even though these KGs represent different scenarios. We hypothesize that this improvement stems from the nature of relation triplets in KGs, where each relation inherently describes the aggregation of the head and tail nodes, aligning with the concept of task-trees.
F4. Domain: Molecule
Graph Classification. We evaluate fine-tuning, in-context learning, and zero-shot learning in this domain. The fine-tuning and in-context learning settings are consistent with those used in previous domains. For zero-shot learning, however, we follow the approach Zhao et al. (2023) by assessing zero-shot performance on the original test set. The graph classification results are presented Table 20, Our GIT model achieves the best average performance across the three evaluated settings. We also observe that specialization consistently improves performance across different graphs, aligning with our theoretical
32

---

Learning Generalities Across Graphs via Task-Trees
Table 19: Edge classification results on knowledge graphs in terms of accuracy.
NNI 8RR
Codex-5 5
Codex-K
Codax-I.
NELL995
GDSLT
ICEW51819
FB15K237
Avg.
GCN
GraphMAE
55.20 + 0.52
61.41 0.86
54.30 + 0.42
61.01 0.55
86.42 0.53
32.43 0.48
31.58 0.39
70.15 0.75
56.56
3-shot
OFA
55,27 a 0.64
55.14 i 0.34
50.20 0.68
62,40 a 0.46
88.41 0.38
30.23 0.50
34,94 1 0.32
79.15 0.45
56.97
GIT G
55,80 0.32
76.96
0.43
73.79 0.43
78.54 0.51
89.13 0.48
34.30 0.68
42,07 0.75
89.78 0.46
67.55
GIT
57.90 0.97
77.19 0.32
72.14 = 0.84
76,99 0.72
90.80 0.51
34.85 0.69
42.02 0.65
90.49 0.32
67.80
GCN
86,77 + 0,30
93.56 2.11
85.73 # 1.84
84.45 + 0.18
79.06 0.32
11.72 0.05
27.53 + 0.06
66.07 + 0.26
66.86 86
GraphMAE
93.87 4 0.35
97.09
0.72
94.07 0.60
94.18 0.19
16.10 0.42
13.12 0.04
28.91 1: 0.06
73.52 0.12
72.61
Finetune
OFA
93.10 0.31
90.78 5.46
93.83 3.28
0.526
86.91 : 1,50
14.48 0.03
30.60 + 0.63
76.08 1.95
72.38
G
94.16 0.11
98.08 0.08
97.89 0.04
96.85 0.03
90.10 0.23
14.86 0.12
33.49 + 0.06
80.39 0.13
75.73
GIT
95.15
0.04
0.04
0.04
0.41
14.89 0.05
33.61
0.07
76.15
analysis.
Table 20: Graph classification results on molecule graphs in terms of AUC.
HIV
BBBP
TOXCAST
CYP450
TCX21
MUV
PCBA
Avg.
GIN
BGRL
$5.27
53.72
33.74
60.99
46.40
39.90
42.39
47.68
GriphMAE
46.48
49,08
30.76
48.22
60.55
49.17
48.17
45,10
47.19
O-shot
OFA
47.96
50.61
34.35
49.70
61.96
52.73
52.48
54.14
50.49
GIT
56.76
54.76
33.66
51.55
63.21
56.83
53.71
56.25
53.34
GIT S
66.14
62.16
52.27
58.30
69.75
63.45
65.32
65.26
62.83
GIN
BGRL
52.72 # 1.84
49.12 19.122: 0.78
59.58 + 0.89
57.27 = 0.05
67.49 + 0.56
$9.26 + 0.19
52.61 + 0.23
51 0.22
56.19 16.19
GraphMAE
54.40 1.04
48.41 1 1.34
60.78 1 1.01
56.99 : 0.06
66.93 1: 0.91
58.40
51.95 4 0.18
50.24
0.23
56.01
3-shot
OFA
56.04 1.49
50.69 1.36
60.21 # 0.64
56.40
68.76 0.16
57.18
56.17
50.77 0.30
57.03
GIT G
52.42 1.74
48.22 1.14
59.32 a: 0.91
56.32 = 0.04
66.77 a: 0.45
58.53 0.36
55.98 a: 0.19
50.09 0.30
55.96
GIT
54.12 1.66
66.74 1.34
0.92 61.76
55.53 0.03
81.50 + 0.23
65.16 0.27
66.14 0.30
$1.58
0.30
62.82
GIN
76.83 1.32
67.36
1.39
75.55 4: 2.91
62.92 = 0.42
85.82 a 0.77
72.26 0.24
70.12 0.39
78.34 0.51
73.65
BGRL
72.18 1.24
67.40 1.45
73.75 3.69
62.52 = 0.10
83.10 0.26
0.54
68.46 0.63
76.69 1.40
72.13
GraphMAB
69.54 2.544+22.59 2,59
66.43
2.48
66.56 + 4.73
62.52 = 0.14
86.64 + 0.27
74.13 0.41
70,12 0.40
75.34 1.33
71.41
Finetune
OFA
76.48 2.11
65.79 0.96
77.88 4: 1.08
63.49 11.49:00.00 0.61
85.77 4: 0.32
73.00
69.53 A 0.56
80.31
1.20
74.03
GrT G
73.63 0.77
68.33 + 1.06
79.28 * 2.71
63.00 = 0.43
86.86 + 11:22
73.81 0.33
70.49
+ 0.51
+1.13+0..5
74.57
GIT S
74.75 0.42
68.72 1.13
81.10 a 0.61
63.63 = 0.61
87.00 + 0.37
73.78 4 0.77
71.16 0.51
81.43 a 0.34
75.20
F.5. Domain: Temporal E- E-Commerce
Edge Classification. We report the experimental results two temporal graphs, Enron and Googlemay CT, in Table 21 and Table 22, respectively. The original graph is split into ten snapshots based timestamps, and the model performance is evaluated separately on each snapshot. Since we fine-tuned the pretrained model on P Products, these experiments assess the model's robustness to temporal distribution shifts. The results demonstrate GIT's capability to effectively handle temporal information in graphs.
Table 21: Edge classification results on temporal graph Enron.
Rnmon
Reron
Faron
Enron
Rnron 5
Remon
Earon
Faron 8
Rnrrnn
Foron 10
Avg.
GAT
81.36 + 0.08
60:00
62.40 1,83
83.49 0.25
45.88 0.34
65.97 + 1.07
48.14 0.23
59.15 0.65
82,39 + 1.88
45:35
63.47
Finetune
GmphMMEE
59.52
66.13
82.84
64.46
GIT -G
81.48 x 0.28
61.25 a 0.25
67.56 2.16
84.50
84.50=0.22
0.21
52.52 a 0.80
67.69 0.54
50.32 a 0.17
68.35 a 0.51
76.92 1.16
48.28 0.15
65.89
GIT-S
0
69.15 0.12 0.43
84.51
$1.930044
66.74 1.24
50.12 0.332
68,89
77,03 2:05
48.35 0.02
65.94
GAT
OFA
08.140.31
58.27 4 0.41
62.43
0.60
$5.48 = 0.50
6
50.35 0.75
53.44 a 0.37
49.01 = 0.55
56.43 0.70
59.01 0.19
57.48
3-shol
GrapiMAE
73.23 0.76
58.53 0.66
61.66 0.61
58.15 0.52
59.81 1.500
50.59 0.60
56,89 0.74
56,08 0.45
59.69 0.14
63.63 0.662
59.83
GIT
60.31
0.59
57.62
50.82
0.58
60.61
62.17
GIT -
73.73 a 0.50
$8.96 0.43
60.08 a 0.45
59.38 = 0.56
61.84 a 0.78
50.43 a 0.72
54.92 : 0.22
$6.03 a 0.43
61.99 0.80
64.85 : 0.50
60.22
33

---

Learning Generalities Across Graphs via Task-Trees
Table 22: Edge classification results on temporal graph Googlemap CT.
GCT
GCT
GCT 3
GCT 4
GCT
GCT
GCT 7
GCT
GCT
GC7 10
Avg.
GAT
61.29
$6.29
56.13
0.08
60.12
0.13
63.37
0.06
64.71
67.08 0.06
69.46
GmphMAR
64.60 + 0.42
37.61 0.32
55.63 - 0.24
57.08 = 0.25
60.36 0.19
60.99 + 108
62.00 + 0.06
63.8 + 0.09
66.89
68.35+0000
61.82
Finelane
GIT G
61.21 4 1.10
59.06 0.20
$7.12 0.23
59.85
0.20
6
62.91 0.10
64.02
0.04
6
70.51
63.29
GIT 5
66.52 a 0.29
58.63 0.69
56.82 a 0.23
59.77 a 0.46
61.93 a 0.22
62.72.1000
64.08 a 0.07
0.11 65.56
67.49 0.18
70,62 x 0.11
6341
GAT
OFA GrahMMAE
0,34
21.22 0:56
20.10 0.32
00.1600211
20.25 0.36
20.39 0.50
20.13 0.14
20.21 = 0.25
19.90
20.59 0.22
20.36
3-shot
21.03
21.73
49.73
19.63
GIT -G
21.81 0.229
21:94 0.23
20.78 a 0.31
20.61 = 0.40
20.73 0.37
20:35 0.56
20,00 + 0.32
20.57 = 0.46
20.58 0.33
20.28 0.31
20:5
G
2
24.21 0.43
23.43 0.44
22.41 #1.14
21.83 0.59
21.65 0.33
21.41 + 0.50
21.76
21.72 0.22
21.72 0.550
22.54
G. Comparison to Domain Experts
G.1. Domain: Knowledge Base
In addition to comparing GIT to standard basclines applicable for all graphs, we also evaluate it against ULTRA, foundation model specifically designed for knowledge graphs. As a domain expert, ULTRA is compared to Expert GIT (pretrained on all KGs) and Specialized GIT (pretrained on default datasets and fine-tuned on FB15K237), with the results presented in Table 23. We find that the two domain experts, ULTRA and Expert GIT, achieve comparable performance, though UI.TRA significantly outperforms Expert GIT in certain settings. This may due to ULTRA learning more fine-grained relational information within KGs. Notably, Specialized GIT also performs comparably both domain experts, highlighting the potential of specialization. We believe this is because the distributions of KGs are more similar to each other compared to graphs from other domains.
Table 23: Comparison between GIT and ULTRA, foundation model designed for knowledge graphs. The Expert GIT pretrained on all KGs used in the paper.
3-shot
Finetune
ULTRA
Expert GIT
Specialized GIT
ULTRA
Expert GIT
Specialized GIT
WN18RR
60.69 # 0.82
55.83 # 0,44
57.90 + 0.97
96.35 # 0.22
95.12 # 0.05
95.15 + 0.07
Codex-S
82,45 = 0.53
76.07 = 0.41
77.19 + 0.32
98.27 + 0.36
99.14 + 0.07
99.19 + 0.04
Codex-M
74.35 = 0.23
0.44
72.14 + 0.84
96.90 = 0.11
97.90 = 0.06
97.92 # 0.04
Codex-L
75.98 + 0.48
78.13 = 0.36
76.99 + 0.72
96.84 # 0.04
96.83 = 0.04
NELL995
90.22 + 0.46 0.46
+.29
90.80 + 0.51
89.46
90.55
91.28 + 0.41
GDELT
33.89 + 0.33
34.92
34.85 + 0.69
14.63 0.02
14.91 0.10
14.89 0.05
ICEWS188 9
41.37 # 0.53
42.42 0.64
42.02 + 0.65
35.95 # 0.03
33.62 0.13
33.61 + 0.10
FB15K237
89.29 + 0.40
90.83 + 0.30
90.49 + 0.32
82.28 + 0.08
80.18 0.29
80.32 0.07
Average
68.53
67.72
67.80
76.26
76.03
76.15
G.2. Domain: Molecule
In addition to general GNN baselines applicable across various graphs. we compare our GIT model to domain experts specifically designed for molecules, including KVPLM (Zeng et al., 2022), MoMu (Su al., 2022), Galactica (Taylor et al., 2022), and the recent SOTA model, GIMLET (Zhao et al., 2023). The results are presented in Table 24. We find that the general model pretrained on large-scale graphs generally underperforms compared to these domain experts. However, after specialization, the specialized model surpasses 3 out of 4 domain experts on average and outperforms the best expert model, GIMLET, on out of 8 datasets. This observation demonstrates that post- cost-training the general model with a reasonable number domain- specific instances can enable to match or even surpass expert models designed for that domain. These results strongly support the effectiveness of task-trees designing graph foundation models.
34

---

Learning Generalities Across Graphs via Task-Trees
Table 24: Comparison between our GIT and domain experts of molecule graphs in zero-shot setting,
HIV
ВBBP
BАCE
TOXCAST
CYP450
TOX21
MUV
PCBA
Avg.
KVPLM
61.20
60.20
51.26
50,96
59.22
49.17
61.72
48.11
55.23
MoMu
50.26
49.81
66.36
52.38
57.98
57.57
60.51
51.50
53.82
Galactica-1.33 1.3B* 1.33
33.85
53.94
56.48
51.23
46.86
49.46
57.15
52.02
50.12
GIMLET
66.24
59.39
69.57
59.04
71.25
61.19
64.39
62.11
64.15
GIT G
56.76
54.76
33.66
51.55
63.21
56.83
53.71
56.25
53.34
GIT - S
66.14
62.16
52.27
58.30
69.75
63.45
65.32
65.26
62.83
indicates the results from paper (Zhao et al., 2023).
H. Ablation on Specialization (SFT)
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 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, still improves the model's performance over the general model on out of 8 datasets.
Table 25: The impact of SFT datasets in zero-shot setting.
SFT Data
HIV
BBBP
BACE
TOXCAST
CYP450
TOX21
MUV
PCBA
Avg.
PCBA
66.14
62.16
52.27
58.30
69.75
63.45
65.32
65.26
62.83
HIV
66.28
45.97
43.35
52.78
64.50
57.86
53.46
46.57
53.85
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 not significantly affect model performance, particularly in fine-tuning and in-context learning settings. Even when the SFT and downstream data the same, the model does necessarily outperform models fine-tuned other SFT datasets. This observation supports the motivation behind 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.
70
ARXV
ARXVV
ARXIV
60
ARX1233
ARXIV23
ARX1233
50
SFT Dataress
76
SFT Daraness
40
-50
30
DRU
DBLP
DBLP
20
-45
FUBMED
72
PUBMED
PUBMED
10
4R0023
PURNED
ARRV
CONA
PURNED
ARVV
OTESEE
DBLP
PURNTO
Downstream Datasets
Downstream Datasets
Downstream Datasets
(a) Finetune
(b) In-context
(c) Zero-shot
Figure 9: The impact of different SFT datasets used for specialization in academic networks.
35

---

Learning Generalities Across Graphs via Task-Trees
I. Efficiency Analysis on Industry-scale Data
In order to further evaluate the efficiency of task-trees over subgraphs, we conduct experiments on a synthetic graph, termed as ogbn-products x50. This dataset is derived from the existing ogbn-products graph, which contains 316.513 nodes and 19,337,745 edges (we use subset of original ogbn-products our experiments). Specifically, we replicate the graph 50 times, reindex the nodes in each replicated graph, and combine them into single dataset. This synthetic dataset contains 5,825,650 nodes (there are 111 956,956 nodes in ogbn-papers Sipvers1000, 100M) and 966,887,28 280,250 edges (there are 1,615,685,87 8,2 edges in ogbn-papers papppsappess..... (00M). To ensure connectivity among these replicated graphs, we randomly flip 5% of the edges to connect the individual components, creating a more realistic large-scale graph structure.
We evaluated the time consumption per epoch on the ogbn-products x50 dataset and compared the efficiency of our proposed method, GIT-task-tree, against GIT-SubG (a variation that replaces task-trees with subgraphs). With a batch size of 512-sclected avoid out-of-memory issues subgraph-based methods-tth results are follows:
Table 26: Efficiency comparison between subgraphs and task-trees in ogbn-products x50 (15,825,650 nodes and 966,887,25 edges).
GIT-SubG
GIT-Task-Tres
Sampling Subgraph/ Tree Extraction
546s
546s
948s
Os
Encoding All
5,717s
2,429s
7,211s
2,975s
These results underscore the significant efficiency advantages of our method. Notably, the efficiency gap between GIT- task-tree and GIT-SubG on this dataset is larger than what we observed during pretraining (i.e., 208 seconds per epoch for GlT-task-tree versus 280 seconds per epoch for GIT-SubG). We attribute this to the substantial overlap between subgraphs in this dataset, which increases the space and time required for processing.
J. General Reasoning Capability of Specialized Models
We further analyze the performance of specialized models on general reasoning tasks beyond their specific domains. We assess the model's performance on other domains as a measure of its general reasoning ability. For example, a model is specialized for academic networks, its general reasoning capability refers to its performance on graphs from other domains, such as e-commerce networks, knowledge graphs, and molecular graphs. The results are presented in Table 27. We report in-context learning performance rather than basic fine-tuning due to computational efficiency. Additionally, we include the performance of the pretrained general model without specialization as a baseline. If the specialized model performs worse than the general model, it suggests that specialization may diminish GIT's general reasoning capability. From the table, it is clear that while specialized models excel in their specific domains, they struggle in other domains. This degradation of general inference capability, often referred to as the specialization tax, is a common challenge in building specialized large language models. The specialization tax can limit the model's practicality scenarios requiring both domain-specific knowledge and the ability to handle general tasks. Thus, balancing domain-specific performance with maintaining general reasoning capability is an important research direction.
Table 27: The in-context learning performance of GIT with different specialization datasets (SFT Data) four domains.
The results of each domain is the average of all datasets within the domain.
SFT Data
Academia
E-commerce
KG
Molecule
General Model
54.00
57.22
67.55
55.96
Arxiv (academia)
55.18
57.63
66.80
54.42
Products (E-com)
50.09
58.01
65.06
55.75
Specialized Model
FB15K237 (KG)
54.70
56.57
67.80
55.37
PCBA (Mol)
50.49
56.87
61.49
62.82
36

---

Learning Generalities Across Graphs via Task-Trees
K. More Parameters Enhance Model Performance
We present comprehensive results of general GIT with different hidden dimensions in Figure 10. For computational efficiency, we does not report results on datasets needing intensive computing resources. We observe that increasing the number of model parameters consistently improves performance across both basic fine-tuning and in-context learning settings. Notably, the performance improvement is more pronounced in in-context learning the model size increases. This may be because, in in-context learning, the model is not fine-tuned on downstream tasks, making the knowledge retained in the original model more crucial. Larger hidden dimensions allow the model to preserve more knowledge. However, when the model is fine-tuned on downstream tasks, the pretraining knowledge is adapted to the specific task, reducing the reliance on the original model's knowledge and leading to a relatively smaller performance gap.
DRLP
Hakey
Congudar
Ralige
WYBERR
10ON91815
HV
BACE
T0K21
Cadou
ODELT
ACADEMIA
ECCOMNERGE
KG
MOL SOULE
Model Purformant
1944
1236
Hidden Dimersion
Hidden D mimmiiion
Hiddwn Dimension
Hidden Dimamison
(a) In-context Learning
Conser
400k2
NCLLS95
1219
TOWGAST
TOA21
Compuar
COELT
ACADENIA
ECOMNNERE
MOLECULE
Modal
922
1844
150
BG
512
1224
155
912
1024
Hidden Dimersion
Hiddee Dimersioo
Hidden Dimersion
Hidden Dimension
(b) Finetune
Figure 10: The comprehensive results of the impact of hidden dimensions on model performance.
L. Comparison to Few-Shot Learning Methods
We compare the performance of GIT with methods designed for few-shot learning on Arxiv in Table 28. We include a wide range of baselines: GPN (Ding et al., 2020) framework that leverages GNN and meta-learning to address few-shot node classification by learning transferable metric space. TENT (Wang et al., 2022b) introduces three levels of nodel-eeeee.eeee class-level, and task-level-to mitigate task variance and improve the model's generalization performance across different meta-tasks. GLITTER (Wang et al., 2022a) enhances few-shot node classification by learning task-specific graph structures for each meta-task using node influence and mutual information. TLP (Tan et al., 2022) transfers pretrained node embeddings fine-tunes a simple linear classifier on novel classes. Prodigy (Huang et al., 2023) enables in-context learning over graphs by designing graph prompt learning template. It important to note that we implement an in-context version of few-shot learning without fine-tuning GIT on the few-shot task, whereas the other methods require fine-tuning. Despite this, GIT achieves the second-best performance across all settings, outperforming 5 out of 6 fhw-shot learning methods. This highlights GIT's strong potential in scenarios with limited instances and labels.
37

---

Learning Generalities Across Graphs via Bask-Trees
Table 28: The few-shot performance on Arxiv, comparing few-shot learning methods.
5-way
3-way
5-shot
3-shot
1-shot
5-shot
3-shot
1-shot
GPN
50.53 + 3.07
48.32 + 3.80
38.58 + 1.61
62.25 + 4.94
58.52 +: 3.00
48.45 + 5.60
TENT
60.83 7.45
56.03 = 8.90
45.62 # 10.70
74.20 + 9.93
70.48 11.50
59.38 = 13.55
GLITTER
56.00 + 4.40
57.44
4.73
62.13 10.85
60.93 12.12
59.20 + 5.48
TLP-BGRL
50.13
46.21 = 7.92
35.81 # 8.58
62.93 # 11.74
58.37
11.34
46.30 10.83
TUP-SURGL
77.89 + 6.46
74.19 # 7.55
61.75 # 10.07
86.27 + 7.54
83.75 8.86
73,46 + 12.68
Prodigy
61.09 + 5.85
58.64 = 5.84
48.23 + 6.18
73.64 + 6.93
71.43 7.28
61.59 + 8.53
GIT G
70.50 # 0.47
64.07 + 0.50
49.18 # 0.56
80.20 + 0.67
74.65 + 0.54
61.93 + 0.18
G
70.70 + 0.28
64.06 = 0.58
50.94 # 0.57
80.51 + 0.68
76.05 = 0.53
63.42 + 0.46
38


Reviews:
[{"review_id": "zvZXc2c5Zj", "reviewer": "Reviewer_Bjq8", "summary": "This paper introduces a novel approach for learning generalities across graphs via task-trees, which unify node-, edge-, and graph-level tasks by introducing virtual task nodes. The theoretical analysis demonstrates the stability, transferability, and generalization properties of task-trees. Empirically, the proposed pretrained model GIT achieves strong performance across 32 graphs from 5 domains via fine-tuning, in-context learning, and zero-shot learning. Specialization through instruction tuning further enhances domain-specific performance.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n> More comparing results\n> \n\nWe 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. \n\n| **Domain** | **Task** | **GraphPrompt+ [1]** | **All in one [2]** | **OpenGraph [3]** | **AnyGraph [4]** | **GIT - G (ours)** |\n| --- | --- | --- | --- | --- | --- | --- |\n| **Academic -  (avg. over 6 graphs)** | Node Classification | 74.80 | 75.25 | 74.64 | 75.01 | **75.82** |\n| **KG -  (avg. over 8 graphs)** | Edge Classification | 74.78 | 74.92 | 71.38 | 74.30 | **75.73** |\n| **Molecule (avg. over 8 graphs)** | Graph Classification | 72.99 | 71.87 | 72.84 | 72.49 | **74.57** |\n\n[1] Generalized Graph Prompt: Toward a Unification of Pre-Training and Downstream Tasks on Graphs, TKDE 24. \n\n[2] All in One: Multi-task Prompting for Graph Neural Networks, KDD 23\n\n[3] OpenGraph: Towards Open Graph Foundation Models, EMNLP 24\n\n[4] AnyGraph: AnyGraph: Graph Foundation Model in the Wild, Arxiv 24\n\n> Discussion on node-of-interest and graph prompt\n> \n\nWe 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. \n\nSpecifically, **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.\n\nIn 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.\n\n> Questions about the textual encoder. \n> \n\n**Q1: Does the method rely on text encoder?** \n\n**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.\n\n**Q2: Can the method be applied to non-text-attributed graphs?** \n\n**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. \n\n| **Setting** | **GraphMAE** | **GIT-G** |\n| --- | --- | --- |\n| w/o SVD + w/o pretrain | **95.02** | 94.27 |\n| w. SVD + w/o pretrain | 94.89 | **95.50** |\n| **w. SVD + w. pretrain** | 95.10 | **95.70** |\n\n**Q3: The task-tree generality assumption is only validated on text-attributed graphs.** \n\n**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.\n\n> The ablation on textual encoder\n> \n\nWe 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. \n\n| **Domain** | **MiniLM** | **MPNet** | **SentenceBERT (default)** |\n| --- | --- | --- | --- |\n| Academic | 75.42 | 75.75 | **75.82** |", "claims_and_evidence": "The key claims are supported by experiments and theory, but issue remains:\n\nTask-Tree Generality: The assumption that task-trees capture cross-graph generalities is validated only on text-attributed graphs. Non-textual graphs  are not tested.", "methods_and_evaluation_criteria": "The proposed methods and evaluation criteria generally make sense.", "theoretical_claims": "The theoretical claims are generally correct.", "experimental_designs_or_analyses": "Baselines: The baselines is outdated. OFA[1] is published in 2023. Recent graph foundation models are missing.\n[1]Liu, Hao, et al. \"One for all: Towards training one graph model for all classification tasks.\" arXiv preprint arXiv:2310.00149 (2023).", "relation_to_broader_scientific_literature": "The key contributions of this paper are closely tied to the literature on Graph Foundation Models (GFMs) and cross-task alignment:\n\nGraph Foundation Models: Prior works like OFA (Liu et al., 2024) align tasks using subgraphs as basic units. This paper proposes task-trees as a more efficient and learnable alternative, directly addressing the computational overhead and limited expressiveness of subgraph-based methods.\n\nTask Heterogeneity: Earlier studies (e.g., Sun et al., 2023) align tasks through reformulation (e.g., converting node classification to subgraph classification). However, this work is the first to theoretically justify the superiority of task-trees in terms of stability and transferability.\n\nInstruction Tuning: Inspired by instruction tuning in large language models (e.g., LLaMA), the authors extend this paradigm to graphs, complementing graph in-context learning frameworks like Prodigy (Huang et al., 2023).\n\nThe novelty of this work lies in:\n\nUnified Task Representation: Unlike subgraphs or graphon-based methods, task-trees unify node-, edge-, and graph-level tasks into a tree structure via virtual nodes, achieving structural alignment across tasks for the first time.\n\nTheoretical Grounding: Existing GFMs (e.g., GraphMAE, BGRL) lack theoretical explanations for task heterogeneity. This paper fills the gap with stability theorems (Theorem 3.1) and generalization bounds (Theorem 3.5).", "essential_references_not_discussed": "The references are generally comprehensive.", "other_strengths_and_weaknesses": "Although the authors propose task-trees, they do not differentiate this method from node-of-interest[1] or graph prompt[2] approaches.\n[1]Liu, Hao, et al. \"One for all: Towards training one graph model for all classification tasks.\" arXiv preprint arXiv:2310.00149 (2023).\n[2]Sun, Xiangguo, et al. \"All in one: Multi-task prompting for graph neural networks.\" Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Mining. 2023.", "other_comments_or_suggestions": "1. It is recommended that the authors include a comparison between their method and node-of-interest or graph prompt approaches, as well as add relevant baselines for evaluation.\n2. It is recommended to conduct ablation studies on the choice of text encoder.", "questions_for_authors": "1. Does your method rely on a text encoder?\n2. Can your method be transferred to non-text-attributed graphs (non-TAGs)?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "EFRoKmc1le", "reviewer": "Reviewer_g6zE", "summary": "The paper proposes a graph foundation model called GIT for multiple graph learning tasks across various domains. GIT introduces task-trees as basic learning instances to align task spaces (node, link, graph) on graphs, acquire transferable knowledge, and effective adaptation to downstream tasks.  A series of theoretical analyses is provided to demonstrate the stability, transferability, and generalization of GIT. Comprehensive experiments over 30 graphs in five domains are conducted to demonstrate the effectiveness of GIT for multiple graph learning tasks.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n> 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.\n> \n\nWe 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.\n\nEmpirically, 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.\n\n| **Batch Size** | **512** | **1024** | **2048** | **4096** | **8192** | **16384** | **32768** |\n| --- | --- | --- | --- | --- | --- | --- | --- |\n| *GIT - Task-Tree* |  |  |  |  |  |  |  |\n| **Time / Epoch (s)** | 208 | 180 | 176 | 172 | 172 | 163 | 162 |\n| **Memory Allocation (%)** | 6 | 8 | 18 | 41 | 75 | 93 | 98 |\n| *GIT - SubG* |  |  |  |  |  |  |  |\n| **Time / Epoch (s)** | 280 | 243 | 234 | 223 | OOM | OOM | OOM |\n| **Memory Allocation (%)** | 21 | 39 | 74 | 97 | OOM | OOM | OOM |\n\n> 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.\n> \n\nThank 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.\n\n| **Method** | **0-shot** | **3-shot** | **Finetune** |\n| --- | --- | --- | --- |\n| *General Model* |  |  |  |\n| **GraphMAE-G** | 15.42 | 49.25 | 73.81 |\n| **OFA-G** | 13.98 | 45.93 | 72.18 |\n| **GIT-G** | **14.88** | **54.00** | **75.82** |\n| *Specialized Model* |  |  |  |\n| **GraphMAE-S** | 20.31 | 51.21 | 74.05 |\n| **OFA-S** | 20.05 | 46.87 | 73.04 |\n| **GIT-S** | **23.45** | **55.18** | **75.88** |", "claims_and_evidence": "Most claims and evidence are well provided. The proposed idea is interesting, the theoretical analysis is sufficient. The experiments are solid and comprehensive. \n\nQuestion/issue: 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.", "methods_and_evaluation_criteria": "Make sense.", "theoretical_claims": "The theoretical claims to demonstrate the stability, transferability, and generalization of GIT are sufficient. The authors have provided detailed proofs in the appendix.", "experimental_designs_or_analyses": "The experiments and analyses are comprehensive. The authors conduct experiments over 30 datasets across five domains. The results are sufficient and significant. \nQuestion/issue: 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.", "relation_to_broader_scientific_literature": "This paper develops a graph foundation model that can benefit various graph learning studies and applications.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The paper writing and presentation are good.", "other_comments_or_suggestions": "N/A", "questions_for_authors": "Questions are included in the above comments.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "17gLEzD9tc", "reviewer": "Reviewer_sWNJ", "summary": "The authors propose a various task alignment method based on task trees.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n> More Related Works and Comparative Results\n> \n\nWe 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:\n\n**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**. \n\nTo 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.\n\nWe 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.\n\n| **Domain** | **Task** | **GraphPrompt+ [1]** | **All in one [2]** | **OpenGraph [3]** | **AnyGraph [4]** | **GIT - G (ours)** |\n| --- | --- | --- | --- | --- | --- | --- |\n| **Academic -  (avg. over 6 graphs)** | Node Classification | 74.80 | 75.25 | 74.64 | 75.01 | **75.82** |\n| **KG -  (avg. over 8 graphs)** | Edge Classification | 74.78 | 74.92 | 71.38 | 74.30 | **75.73** |\n| **Molecule (avg. over 8 graphs)** | Graph Classification | 72.99 | 71.87 | 72.84 | 72.49 | **74.57** |\n\n[1] Generalized Graph Prompt: Toward a Unification of Pre-Training and Downstream Tasks on Graphs, TKDE 24. \n\n[2] All in One: Multi-task Prompting for Graph Neural Networks, KDD 23\n\n[3] OpenGraph: Towards Open Graph Foundation Models, EMNLP 24\n\n[4] AnyGraph: AnyGraph: Graph Foundation Model in the Wild, Arxiv 24\n\n[5] SAMGPT: Text-free Graph Foundation Model for Multi-domain Pre-training and Cross-domain Adaptation, WWW 25\n\n[6] Graphprompt: Unifying pre-training and downstream tasks for graph neural networks, WWW 23\n\n> This paper is far from graph foundation models.\n> \n\nWe 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.\n\nThat 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. \n\n> The contribution of introducing task trees is limited.\n> \n\nThank 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.", "claims_and_evidence": "See weaknesses part.", "methods_and_evaluation_criteria": "The evaluation criteria makes sense for the problem.", "theoretical_claims": "I check the correctness of theoretical claims.", "experimental_designs_or_analyses": "I check the experimental setting.", "relation_to_broader_scientific_literature": "See weaknesses part.", "essential_references_not_discussed": "Other graph foundation models [1,2,3,6] should be discussed or compared with.\n\nThe idea of using subgraph as the basic instances is proposed in previous works [1,2]，which can also be applied to solve various tasks. These methods should be discussed and compared with.\n\n[1] Xia et al. Anygraph: Graph foundation model in the wild. arXiv 2024.\\\n[2] Xia et al. Opengraph: Towards open graph foundation models. arXiv 2024.\\\n[3] Yu et al. SAMGPT: Text-free Graph Foundation Model for Multi-domain Pre-training and Cross-domain Adaptation. WWW 2025.\\\n[4] Liu et al. Graphprompt: Unifying pre-training and downstream tasks for graph neural networks. WWW 2023.\\\n[5] Yu et al. Generalized graph prompt: Toward a unification of pre-training and downstream tasks on graphs. IEEE Transactions on Knowledge and Data Engineering, 2024.", "other_strengths_and_weaknesses": "Strength:\n1. The authors conduct extensive experiments.\n2. The paper is overall well written.\n\nWeaknesses:\\\n1.This paper is far from graph foundation models. A key challenge in developing such models is bridging the feature and structure gaps across domains. However, this work primarily proposes a unified instance for various tasks, leaving these challenges unresolved.\\\n2. Although the authors discuss the differences between using task trees and subgraphs as unified instances, the contribution of introducing task trees is limited, making the work lack novelty.", "other_comments_or_suggestions": "See weaknesses part.", "questions_for_authors": "See weaknesses part.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "sMbH1tTEkb", "reviewer": "Reviewer_xh4d", "summary": "This paper introduces an approach to enhance the generalization of GNNs across diverse tasks, which typically vary in their inductive biases, such as node classification, link prediction, and graph classification. The authors propose the concept of Task-Trees, a framework designed to align task spaces at different levels (node, edge, and graph) by introducing virtual task nodes that connect task-related components.  The paper presents Graph Generality Identifier on Task-Trees (GIT), a pre-trained model that leverages Task-Trees to learn generalized representations. Theoretical analysis confirms the framework's stability, transferability, and generalization potential. Extensive experiments demonstrate the effectiveness of GIT in fine-tuning, in-context learning, and zero-shot learning tasks, showcasing superior generalization and computational efficiency compared to subgraph-based methods.\n\n## update after rebuttal\nI have improved the score according to the rebuttal.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "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.\n\n> Theory\n> \n\n**Q1: Imprecise Task-Tree Generality Assumption**\n\n**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.\n\n**Q2: Concerns about generalization bound**\n\n**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.\n\n**Q3: Domain shift in Theorem 3.3**\n\n**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. \n\n> More Related Works\n> \n\nWe 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.\n\nWe 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. \n\n|  | Cora | Citeseer | Pubmed |\n| --- | --- | --- | --- |\n| GCOPE | 76.39 | 78.75 | **75.39** |\n| GIT-G | **77.84** | **80.87** | 74.80 |\n\n> Why use TAGs in experiments?\n> \n\nOur 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. \n\nImportantly, 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.\n\n| Setting | GraphMAE | GIT-G |\n| --- | --- | --- |\n| w/o SVD + w/o pretrain | **95.02** | 94.27 |\n| w. SVD + w/o pretrain | 94.89 | **95.50** |\n| **w. SVD + w. pretrain** | 95.10 | **95.70** |\n\n> Additional Experiments\n> \n\n**Q1: Heterophily Graphs**\n\n**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.\n\n|  | GraphMAE | OFA | GIT-G |\n| --- | --- | --- | --- |\n| Children | 56.76 | 55.43 | **59.09** |\n| Ratings | 52.39 | 51.79 | **52.45** |\n\n**Q2: Few-shot Learning**\n\n**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.\n\n|  | GraphMAE | GIT-G |\n| --- | --- | --- |\n| *5-way* |  |  |\n| 10-shot | 45.27 | **49.61** |\n| 50-shot | 53.49 | **55.60** |\n| 100-shot | 59.73 | **60.13** |\n| *10-way* |  |  |\n| 10-shot | 37.73 | **40.09** |\n| 50-shot | 48.04 | **50.26** |\n| 100-shot | 53.02 | **56.09** |\n\n> Visualization: Node Count\n> \n\nWe have revised the figure to indicate that more nodes exist, using dotted edges to clarify that the figure is a partial illustration.", "claims_and_evidence": "Most claims are supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "The proposed method in this paper   bridges the differences between tasks.", "theoretical_claims": "1. The definition of the Task-Tree Generality Assumption here is quite imprecise. What specific generalities shared across graphs should be included?\n2. I am somewhat concerned about the generalization bound proven in Section 3.5. Its form is similar to the generalization bounds in PAC learning, but for models like GNNs, which deal with non-i.i.d. data, such bounds may not be directly applicable.\n3. In Theorem 3.3, it seems that the domain shift issue in downstream tasks is overlooked. If the distribution gap between the pretraining and fine-tuning tasks is too large, the bound may completely fail.", "experimental_designs_or_analyses": "This paper provides abundant experiments on diverse downstream tasks, which is a lightspot of the paper. However, most datasets are homophilc, I advise the authors to conduct some experiments on heterophilc graphs.", "relation_to_broader_scientific_literature": "The key contributions of this paper build upon prior work in graph representation learning, graph foundation models, and multi-task learning, providing a perspective on generalization across graph-based tasks. Existing approaches often use graphon-based methods or contrastive learning, but they may struggle to align tasks effectively. Task-Trees bridge this gap by introducing a unified structure for task representation, enabling the pre-trained GIT model to transfer knowledge more effectively across datasets. This aligns with broader trends in task-agnostic pretraining, similar to foundation models in NLP and vision. Additionally, the work contributes to multi-task learning and representation alignment, where prior approaches in graphs have mainly relied on adversarial training or knowledge distillation. By introducing a tree-based structure to connect different task levels, this paper offers a fresh approach to improving the transferability of graph models, advancing the study of generalization in graph learning.", "essential_references_not_discussed": "Some research on graph foundation models are not discussed, e.g., All in One and One for All: A Simple yet Effective Method towards Cross-domain Graph Pretraining published in SIGKDD 2024.", "other_strengths_and_weaknesses": "By leveraging a tree-like structure, the approach transfers different types of tasks to a task node, thereby enhancing its generalization capability. However, the paper contains numerous unclear descriptions regarding both the methodology and experiments, revealing certain shortcomings in academic writing.", "other_comments_or_suggestions": "One limitation of this work is that it does not account for the reliability of information across different domains. We observe that most experiments are conducted on homophily graphs, with little consideration of graph noise. It would be beneficial to include additional experiments on heterophily graphs to enhance the analysis.", "questions_for_authors": "1. Some diagrams appear to be inconsistent. For example, in Figure 1, the task-tree corresponding to the graph-level task should ideally connect all nodes. However, in the first layer, only three nodes are connected. It may be helpful to add some textual clarification to improve understanding.\n2. Another question is based on your selected datasets. Why all experiments are conducted on TAGs? Does it mean that your method relies on text attributes?\n3. How is the performance when the number of shots increase to 10,100, or more? Provided experiments only focus on few-shot scenarios.\n4. See the experiment part.\n5. See the theory part.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper investigates the problem of identifying generalities across graph-structured data. To address this challenge, the authors propose a novel approach for learning cross-task generalities in graphs. Specifically, they introduce task-trees as basic learning instances to align task spaces—including node, edge, and graph-level tasks—within a unified structural framework. To empirically validate their method, the authors develop a pretrained graph model based on task-trees. Experimental results on several datasets demonstrate the effectiveness of the proposed model.


Strengths:
1. The paper’s key contributions are well-aligned with recent advancements in Graph Foundation Models (GFMs) and the challenge of cross-task alignment.
2. The proposed task-tree structure effectively unifies node-, edge-, and graph-level tasks by introducing virtual nodes, enabling structural alignment across different learning objectives.
3. The theoretical analysis supporting the stability, transferability, and generalization capabilities of GIT is sound and well-motivated.



Weaknesses:

1. The experimental evaluation could be improved by including a broader range of baselines for discussion and comparison.
2. The current framework does not consider the varying reliability of information across domains, such as in heterophily graphs, which may limit its applicability in real-world heterophily settings.


Overall, this paper presents a novel and compelling approach to unifying learning paradigms across graph tasks. For the camera-ready version, I recommend the authors further refine some aspects, particularly by incorporating more competitive baselines. Additionally, exploring more challenging settings—-such as unifying a wider range of graph properties or addressing heterophily structures—-is also recommended to enhance the generality and applicability of the proposed method.
Decision: Accept (poster)