GFT: Graph Foundation Model with
Transferable Tree Vocabulary

Transferability refers to a model’s capability to extract patterns from source tasks and apply this knowledge to enhance performance on related target tasks [5, 33, 90]. Understanding transferable patterns is essential for developing graph foundation models. Early research focuses on analyzing transferability through the perspectives of graph spectrum [41, 42] and subgraphs/substructures [114], defining transferability as model invariance to minor permutations on the graph. A more recent study [50] investigates the transferable vocabulary in graphs by identifying key substructures relevant to various tasks. For instance, they find that triadic closure, homophily, and heterophily are vital for node classification; local and global structural proximities are crucial for link prediction; and certain motifs [103], such as triangles, $k$-cliques, and stars, serve as fundamental components for graph classification. Another line of research [62, 8, 69] incorporates graphon theory to provide a theoretical basis for transferability. Specifically, Ruiz et al. [62] establish a bound on the embeddings of two graphs sampled from the same graphon. Cao et al. [8] expand this to include pre-training and fine-tuning scenarios, assessing the distance between graphs based on their alignment within the graphon space. However, the stringent assumptions of graphon theory limit its practical application in the design of graph foundation models.

We identify two primary limitations in analyzing transferable patterns on graphs: (1) While certain domains [110, 87, 43, 108] or tasks [114, 111, 19] exhibit transferable patterns, the challenge of identifying universally transferable substructures is difficult. (2) More critically, basic message-passing GNNs, constrained by the 1-WL test [94, 52], fail to recognize certain subgraphs (or motifs) [20, 10, 103], such as stars, conjoint cycles, and $k$-cliques, as well as heterophily patterns [113]. This limitation in recognizing substructures impedes using subgraphs as transferable tokens in graph vocabulary [68, 30, 45]. More related works are elaborated in Appendix A.

In this paper, we rethink the transferable pattern in graphs as the computation tree — a specialized subtree pattern that emerges from unfolding the message-passing process [12]. This pattern is demonstrably effective at capturing critical localized information within the graph [20, 52, 94, 12]. Treating computation trees as tokens within a graph vocabulary offers two distinct advantages: (1) computation trees preserve the essential structural information of the graph, which is learnable through message-passing GNNs, and (2) the computation tree structure occurs across various graph-based tasks. These tasks can be unified as computation tree classification by integrating a virtual node, as shown in Figure 1.

Before diving into transferability analysis, we first establish the necessary notations. Consider a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$ composed of node set $\mathcal{V}$ and edge set $\mathcal{E}$. Each node $v\in\mathcal{V}$ is associated with a feature vector $\mathbf{x}_{v}\in\mathbb{R}^{d}$ and a computation tree $\mathcal{T}_{v}$ with $L$ layers. A GNN encoder $\phi$ processes these computation trees as inputs, producing embeddings for root nodes $\mathbf{z}=\phi(\mathcal{T}_{v})\in\mathbb{R}^{d^{\prime}}$.

Figure 1 demonstrates the construction of computation trees across various graph tasks, including node-, link-, and graph-level tasks. These trees capture essential localized subtree patterns within the graphs [55, 64, 12]. If the $L$-layer computation trees for two nodes are similar, it indicates that these nodes share similar neighborhoods, suggesting they represent analogous phenomena [42]. Thus, it is rational to assess transferability of computation trees by examining the stability of GNNs in producing analogous embeddings for similar trees [62, 42].

Supportive Observations — Synthetic Graphs. Figure 3 shows that high computation tree similarity between graphs correlates with improved transfer learning performance on synthetic graphs (Figure 2). Specifically, we construct three distinct graphs: $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ share similar motifs but differ in computation tree distributions, while $\mathcal{G}_{1}$ and $\mathcal{G}_{3}$ exhibit dissimilar motifs but similar computation tree distributions. We employ the WL subtree kernel [64] and the graphlet sampling kernel [57] to assess tree and motif similarity, respectively, and utilize the inverse of the Central Moment Discrepancy [102] to measure transferability. Further details on experimental settings and additional results are available in Appendix E.1. Our findings indicate that transferability is strongly associated with computation tree similarity rather than motif similarity, regardless of the scale of graphs (# blocks).

Supportive Observations — Real-world Graphs. Table 1 validates the correlation between computation tree similarity and transferability in real-world graphs, including homophily Airport networks [61] and heterophily WebKB networks [56]. We evaluate transferability based on transfer learning performance in node classification tasks. Detailed experimental settings and additional results are available in Appendix E.2. Our findings in real-world graphs corroborate those in synthetic graphs: higher computation tree similarity enhances transferability, while the impact of motifs is marginal, no matter using original node features (Table 1) or randomized node features (Table 9).

The pre-training stage focuses on learning general computation tree patterns on graphs, facing two primary challenges: (i) obtaining transferable patterns, and (ii) comprehensively capturing computation tree knowledge. For the first challenge, we learn a discrete tree vocabulary by quantizing the embedding space of computation trees [77]. For the second challenge, we introduce a computation tree reconstruction task that considers multiple aspects of computation trees.

Learning Tree Vocabulary. The idea of learning a discrete computation tree vocabulary originates from the principles of sparse distributed memory in cognitive science [37, 38], which stores and retrieves memory in a distributed manner. By adopting these principles, the tree vocabulary maintains a set of tokens that are reusable and adaptable across various tasks, improving model transferability.

We adopt the Vector Quantization (VQ) [77] to develop the tree vocabulary. Given a graph database¹¹1We use text-attributed graphs in our experiments due to the data availability, and use textual encoder to align the node features, similar to Liu et al. [45]. Despite designing node feature alignment method is crucial in GFMs, it is beyond the scope of this paper. ${\mathcal{D}}=\{{\mathcal{G}}_{i}\}_{i=1}^{n}$, we randomly extract a set of computation trees ${\mathcal{T}}=\{{\mathcal{T}}_{i}\}_{i=1}^{m}$ and employ a GNN encoder $\phi$ to generate the tree embeddings ${\mathcal{Z}}=\{{\mathbf{z}}_{i}\}_{i=1}^{m}$. We define the computation tree vocabulary as a set of learnable tokens ${\mathbf{C}}=\{{\mathbf{c}}_{1},...,{\mathbf{c}}_{K}\}$. The tree embedding space is quantized by assigning each embedding to the nearest token, resulting in quantized tree embeddings ${\mathbf{q}}_{i}={\mathbf{c}}_{j}$, where $j=\operatorname*{arg\,min}_{j}\|{\mathbf{z}}_{i}-{\mathbf{c}}_{j}\|_{2}$. We optimize this projection by back-propagating the reconstruction error to the tree vocabulary ${\mathbf{C}}$ and applying a straight-through gradient estimator [6] to the encoder $\phi$. In particular, we jointly optimize vocabulary loss and commitment loss [77], along with tree reconstruction loss (discussed later), where the former updates the token vectors ${\mathbf{c}}$ using the fixed quantization ${\mathbf{q}}$, and the latter ensures alignment between the tokens in the vocabulary and the quantized tree embeddings, serving as a regularizer. The pre-training objective is thus defined as:

where $\text{sg}[\cdot]$ denotes the stop-gradient operator and $\beta_{1}$ is the weight.

Computation Tree Reconstruction. We introduce a computation tree reconstruction task designed to enable a deep understanding of the structural and semantical attributes of computation trees [36]. We use the tree tokens to reconstruct the original computation tree, retaining general knowledge while discarding irrelevant details. Specifically, we develop three reconstruction tasks: (i) reconstructing the features of the root node ${\mathcal{L}}_{feat}$, (ii) reconstructing the connectivity among nodes in the computation trees ${\mathcal{L}}_{topo}$, and (iii) reconstructing the overall semantics of the computation trees ${\mathcal{L}}_{sem}$:

where $\hat{{\mathbf{z}}}_{i}=\hat{\phi}({\mathcal{T}}_{i})$ represents the semantics of the original computation trees, and $\hat{\phi}$ is updated through a moving average of the tree encoder $\phi$. The quantized tree embedding ${\mathbf{q}}$ is projected via different decoders defined by MLP, $\hat{{\mathbf{q}}}^{j}=\delta_{j}({\mathbf{q}})$, $\gamma$ is the scaling factor, and ${\mathcal{E}}$ and $\hat{{\mathcal{E}}}$ represent sets of existing and non-existing connections in computation trees, respectively. ${\mathbf{e}}_{ij}$ denotes the edge embedding between nodes $i$ and $j$. By jointly optimizing these tasks, we establish a comprehensive reconstruction objective:

where $\beta_{i}$ indicates the weights of respective losses. The philosophies under these loss functions separately correspond to existing works [39, 26, 74, 86]. For example, Kipf and Welling [39] reconstruct the graph structure, aligning to the philosophy of ${\mathcal{L}}_{topo}$, Hou et al. [26] reconstruct node feature that is similar to ${\mathcal{L}}_{feat}$, and Thakoor et al. [74], Wang et al. [86] employ contrastive learning to maximize the alignment between two views, aligning to ${\mathcal{L}}_{sem}$. Unlike existing methods that typically focus on reconstructing a single aspect of computation trees, GFT integrates multiple facets [85] to learn a general and transferable tree vocabulary.

Enhancing the Quality of Tree Vocabulary. The effectiveness of GFT is correlated to the quality of the tree vocabulary, which should be both comprehensive and expressive. A comprehensive vocabulary is inclusive enough to accommodate new patterns, while an expressive vocabulary ensures that different tree tokens do not overlap in representation [50]. To enhance comprehensiveness, we augment the computation trees during pre-training, increasing the variety of observed computation trees through node feature augmentation and structural augmentation, as described by [115]. To improve expressiveness, we regularize the tree vocabulary space by intentionally increasing the distance between distinct tokens [65]. Specifically, we introduce an orthogonal regularizer designed to maintain tree tokens orthogonal to each other, effectively expanding the tree token space:

where ${\mathbf{c}}_{i}$ is tree token, ${\mathbf{I}}_{K}$ is the identity matrix for $K$ dimensions, and $\|\cdot\|_{F}$ denotes the Frobenius norm. The orthogonal loss ${\mathcal{L}}_{ortho}$ is integrated with Equation 2. More analysis is in Appendix C.2.

The pre-training stage encodes general knowledge into the tree vocabulary, while the fine-tuning phase adapts this knowledge to specific tasks. This adaptation is challenging because identical patterns can have different meanings across domains and tasks [8]. For example, a triangular structure indicates stable relationships in social networks (node classification) but denotes unstable chemical properties in molecular networks (graph classification). To this end, we propose computation tree classification that utilizes the tree vocabulary to unify graph tasks as the tree-level task, ensuring the adaptation is applicable across diverse tasks and domains.

Reformulate Graph Tasks as Computation Tree Classification. Graph-related tasks can be represented by task-specific computation trees, as illustrated in Figure 1. Specifically, for node classification, the task-specific computation tree, denoted as ${\mathcal{T}}_{node}={\mathcal{T}}_{i}$, is derived directly from the node itself, resulting in the embedding ${\mathbf{z}}=\phi({\mathcal{T}}_{i})$. For link prediction, the computation tree, ${\mathcal{T}}_{link}=\text{Combine}({\mathcal{T}}_{s},{\mathcal{T}}_{t})$, merges the computation trees of two nodes of the edge, with the embedding ${\mathbf{z}}=\text{mean}(\phi({\mathcal{T}}_{s}),\phi({\mathcal{T}}_{t}))$. For graph classification, the task-specific computation tree ${\mathcal{T}}_{graph}=\text{Combine}(\{{\mathcal{T}}_{v}\}_{v\in{\mathcal{V}}})$ integrates the computation trees of all nodes within the graph, and computes the embedding as ${\mathbf{z}}=\text{mean}(\{\phi({\mathcal{T}}_{v})\}_{v\in{\mathcal{V}}})$. Subsequently, the embeddings of these task-specific trees are used to query the tree vocabulary and then make predictions, adapting the general knowledge encoded in the vocabulary to various tasks and domains.

Prototype Classifier. The prototype classifier $f_{proto}$ constructs class prototypes using tokens from the tree vocabulary. Given a set of task-specific computation trees $\{({\mathcal{T}}_{i},y_{i})\}_{i=1}^{n}$ with $|C|$ classes, we employ the pre-trained GNN encoder $\phi$ to generate tree embeddings ${\mathcal{Z}}=\{{\mathbf{z}}_{i}\}_{i=1}^{n}$. These embeddings are then used to query the tree vocabulary and produce quantized embeddings ${\mathcal{Q}}=\{{\mathbf{q}}_{i}\}_{i=1}^{n}$. Subsequently, we construct a class-wise memory bank ${\mathbb{S}}=\{{\mathbb{S}}^{1},...,{\mathbb{S}}^{|C|}\}$, where ${\mathbb{S}}^{k}=\{{\mathbf{q}}_{i}\in{\mathcal{Q}}|y_{i}=k\}$, to store tree tokens of the same class. The memory bank typically includes all instances from the training set. From this, we derive a set of prototypes for each class $\{{\mathbf{p}}_{k}\}_{k=1}^{|C|}$, calculated as ${\mathbf{p}}_{k}=(1/|{\mathbb{S}}^{k}|)\sum_{{\mathbf{q}}_{i}\in{\mathbb{S}}^{k}}{\mathbf{q}}_{i}$. These prototypes are then used for predictions:

where $\text{sim}(\cdot)$ denotes the cosine distance and $\tau$ is a temperature scaling factor. We optimize the cross-entropy loss between the classifier’s output and the ground truth to update the encoder $\phi$.

Linear Classifier. Different from the prototype classifier, which utilizes class prototypes to adapt to target tasks, the linear classifier $f_{lin}$ directly applies the knowledge encoded in each tree token. Specifically, given a task-specific computation tree ${\mathcal{T}}_{i}$, we use the encoder to generate tree embeddings ${\mathbf{z}}_{i}$ and then query the tree vocabulary to retrieve ${\mathbf{q}}_{i}$. These embeddings are used for predictions as:

We optimize the cross-entropy loss between the prediction $f_{lin}({\mathbf{z}})$ and the ground truth to update the parameters of the encoder and the linear classifier. During inference, predictions from both the prototype and linear classifiers are combined to form the final output. It is important to note that the tree vocabulary remains fixed during fine-tuning to preserve the integrity of the encoded knowledge.

Tree Vocabulary Learns Generalizable Tokens. Learning tree vocabulary via VQ involves clustering within the embedding space of computation trees, utilizing a margin-aware classifier [14] that assigns each computation tree to a specific cluster. Assuming that each computation tree ${\mathcal{T}}$ is associated with an underlying clustering label $y$, and that each pair $({\mathcal{T}}_{i},y_{i})$ is sampled from the distribution ${\mathcal{P}}_{\mathcal{T}}$, we derive the following theorem:

Tree Vocabulary Mitigates Negative Transfer. Negative Transfer (NT) occurs when the pre-training process degrades model performance on a target task. This issue often results from misalignment between the pre-training and fine-tuning tasks [89, 8]. Following the approach in [89], we characterize the NT gap, ${\mathcal{R}}(S,T)-{\mathcal{R}}(\emptyset,T)$, as the risk gap on task $T$ with (${\mathcal{R}}(S,T)$) and without (${\mathcal{R}}(\emptyset,T)$) pre-training on task $S$, where a smaller NT gap indicates improved transferability. As illustrated in Figure 5, employing the learned tree vocabulary to align the tree reconstruction task in pre-training and tree classification task in fine-tuning can significantly mitigate negative transfer.

Complexity Analysis. A comprehensive complexity analysis of GFT is provided in Appendix B. Notably, GFT employs a single GNN to decompose and encode computation trees, taking ${\mathcal{O}}(L\cdot(|{\mathcal{E}}|\cdot d+|{\mathcal{V}}|\cdot d^{2}))$. In contrast, subgraph-based GFMs [30, 45] require the explicit extraction of subgraphs for each node, taking additional ${\mathcal{O}}(|{\mathcal{V}}|^{3})$ using adjacency matrix-based BFS. This contrast highlights the efficiency of using computation trees as transferable patterns in terms of time complexity. More discussions are in Appendix C.

We employ cross-domain and cross-task graph datasets to evaluate the effectiveness of GFT. For node-level tasks, we utilize citation networks such as Cora, PubMed, Arxiv, and the web link network WikiCS. For edge-level tasks, we include two Knowledge Graphs (KGs), WN18RR and FB15K237. For graph-level tasks, we use molecule networks, including HIV, PCBA, and ChEMBL. All preprocessing steps follow [45]. We take various baselines, encompassing MLP, supervised GNNs such as GCN [40], GAT [78], GIN [94], and self-supervised methods like BGRL [74], GraphMAE [26], GIANT [11], and GFMs including Prodigy [30] and OFA [45]. We replicate each experiment ten times and report the average performance to minimize the influence of randomness. Further details on experimental settings are available in Appendix F.

Pre-training and Fine-tuning. Table 2 demonstrates the model performance across cross-domain and cross-task datasets in pre-training and fine-tuning setting. We evaluate the effectiveness of graph foundation models [30, 45] in the following few-shot setting due their distinctive training mechanisms, such as in-context pre-training [30] and fully supervised training [45]. For supervised baselines, models are trained directly on the target graph; for self-supervised methods, we pre-train across all datasets before adapting to the specific target graph. Our approach demonstrates a substantial performance improvement, exceeding the best baseline by an average of over 6%. Specifically, our method outperforms the best baseline by 2% across three datasets and by 5% across another three datasets. This underscores the effectiveness of using computation trees as transferable patterns.

Few-shot Learning Table 3 presents the few-shot learning performance of GFT compared to self-supervised methods [74, 26, 11] and graph foundation models [30, 45, 25]. We randomly select $k$ samples per way from the training set for fine-tuning²²2Cora & WN18RR: 1; Arxiv: 5; HIV & PCBA: 20; FB15K237: 30.. This method is similar to Prodigy [30], and is much more label-efficient than OFA [45] with supervised pre-training. Despite the extremely limited labels for fine-tuning, GFT significantly surpasses existing methods, showing the fast adaptation capability. Appendix H shows more fine-tuning instances can significantly improve performance.

Table 5 shows the impact of different pre-training datasets under the pre-training and fine-tuning setting, where comprehensive results (including the following ablation studies) are available in Appendix I. The performance for specific tasks (node-, link-, graph-level) represent the average across all involved datasets. We examine three scenarios with distinct pre-training datasets: (i) all datasets, (ii) only the target dataset, and (iii) datasets excluding the target dataset. These variants are compared against GAT and GIANT, which represent the best supervised and self-supervised baselines, respectively. Notably, GFT consistently outperforms all baselines, regardless of the pre-training dataset utilized. Interestingly, performance improves when using datasets excluding the target dataset compared to pre-training solely on the target dataset. We hypothesize that the computation trees from the non-target datasets provide sufficient information to facilitate the learning of a transferable tree vocabulary, thereby promoting positive transfer.

We further evaluate the impact of various combinations of pre-training datasets on the target tasks, as depicted in Figure 6. For pre-training, we select FB15K237, Arxiv, and ChEMBL, while Cora, WikiCS, WN18RR, and HIV serve as the target datasets. Our findings indicate that an increased number of pre-training datasets consistently enhances performance across all target datasets. However, for existing GFMs, transferability closely correlates with the selection of pre-training datasets, with more datasets sometimes leading to negative transfer [25, 43]. This observation underscores the adaptability of using computation trees as transferable patterns in graph vocabulary.

Tree Reconstruction and Classification. Table 4 shows the impact of various reconstruction tasks in pre-training and tree classifiers in fine-tuning. All reconstruction tasks enhance model performance compared to models without pre-training. Notably, semantic reconstruction is most effective for node-level and graph-level tasks due to its comprehensive consideration of node features and graph structures. Feature reconstruction is particularly beneficial for link-level tasks, as it preserves the original node semantics, which are crucial for KGs. The optimal performance is achieved when three tasks are jointly optimized, aligning with findings in Ju et al. [36]. Similarly, the combination of prototype and linear classifiers in tree classification leads to superior performance. Furthermore, removing strategies designed to enhance the quality of the tree vocabulary results in model degradation across all settings (Appendix I.3).

Tree Vocabulary. Table 6 shows the importance of the vocabulary, where the use of vocabulary significantly enhances model performance, particularly in link- and graph-level tasks, which aligns to the theoretical analysis that the tree vocabulary improves generalization. However, we observe that increasing the number of tokens in the vocabulary does not necessarily enhance model performance; indeed, the improvements are often marginal.