GFT: Graph Foundation Model with Transferable Tree Vocabulary

• Graph foundation models could support broad applications, but existing pre-trained GNNs have not achieved desired performance across varied graph-learning tasks.Source: §1 · p. 2
• Graph transferability is difficult to define because graph structures differ from image and language data, while graphon assumptions and explicit subgraph extraction limit existing vocabulary approaches.Source: §1 · p. 2
• Computation trees encode message-passing patterns and offer efficient extraction, localized expressiveness, and learnability within GNNs.Source: §1 · p. 2
• GFT treats computation trees as graph vocabulary tokens, using reconstruction during pre-training and tree classification during fine-tuning across tasks and domains.Source: §1 · p. 2

2.1 Transferability on GNNs

• Basic message-passing GNNs can miss stars, conjoint cycles, k-cliques, and heterophily patterns, limiting subgraphs as transferable graph-vocabulary tokens.Source: §2.1 · p. 3

2.2 Computation Tree as Transferable Pattern

• Computation trees are message-passing-derived subtrees that preserve localized graph information and can unify node-, link-, and graph-level tasks through a virtual node.Source: §2.2 · p. 3, Figure 1 · p. 3
• Theorem 2.2 bounds the distance between computation-tree embeddings using distances between their lower-level subtrees and encoder-related constants.Source: §2.2 · pp. 3–4
• Higher computation-tree similarity is associated with closer embeddings and improved transferability, matching the paper’s empirical observations.Source: §2.2 · p. 4, Figure 3 · p. 4, Table 1 · p. 4
• Synthetic graphs are built from two basic blocks, and additional blocks scale graph size for transferability experiments.Source: Figure 2 · p. 4

3 GFT: Graph Foundation Model with Transferable Tree Vocabulary

• GFT pre-trains on cross-domain graphs, quantizes computation-tree embeddings into reusable tokens, and fine-tunes by recasting node-, link-, and graph-level tasks as computation-tree classification.The learned vocabulary is kept fixed during fine-tuning to preserve encoded knowledge.Source: §3 · pp. 4–5, §3.1 · p. 5, §3.2 · pp. 6–7

3.1 Pre-training with Computation Tree Reconstruction

• GFT reconstructs root features, tree connectivity, and tree semantics jointly, retaining multiple structural and semantic facets instead of reconstructing only one aspect.The combined objective is L_tree = β2 · L_feat + β3 · L_sem + β4 · L_topo.Source: §3.1 · pp. 5–6
• Vector quantization assigns each computation-tree embedding to its nearest learnable token, while vocabulary and commitment losses align tokens with the quantized embeddings.The encoder is optimized with a straight-through gradient estimator alongside reconstruction loss.Source: §3.1 · p. 5
• Feature and structural augmentation broaden observed tree patterns, while an orthogonal regularizer separates distinct tokens to improve vocabulary comprehensiveness and expressiveness.The regularizer pushes tree tokens toward orthogonality in the vocabulary space.Source: §3.1 · p. 6

3.2 Fine-tuning with Computation Tree Classification

• Computation-tree classification adapts the shared vocabulary across tasks: node trees use individual nodes, link trees combine endpoint trees, and graph trees aggregate all node trees.Prototype and linear classifiers query the vocabulary for task-specific predictions.Source: §3.2 · pp. 6–7

3.3 Additional Analysis

• The analysis reports that larger margins and more observed trees tighten token generalization bounds, whereas more tokens may loosen the bound and fail to improve performance.The theoretical discussion supports orthogonal regularization and computation-tree augmentation.Source: §3.3 · p. 7
• Aligning pre-training tree reconstruction with fine-tuning tree classification significantly mitigates negative transfer, measured as the risk gap between pre-training and no pre-training.Figure 5 presents the negative-transfer gap on Cora node classification.Source: §3.3 · p. 8, Figure 5 · p. 8
• GFT encodes computation trees with time complexity O(L · (|E| · d + |V| · d^2)), avoiding the additional O(|V|^3) adjacency-matrix BFS cost of subgraph-based approaches.The comparison concerns computation-tree encoding versus explicit per-node subgraph extraction.Source: §3.3 · p. 8

4.2 Effectiveness on Cross-Domain and Cross-Task Datasets

• GFT exceeds the best baseline by over 6% on average across cross-domain and cross-task datasets.It improves by 2% across three datasets and by 5% across another three.Source: §4.2 · p. 8, Table 2 · p. 9
• GFT significantly surpasses existing methods in few-shot learning, demonstrating fast adaptation with extremely limited fine-tuning labels.The evaluation compares self-supervised methods and graph foundation models under k-shot sampling.Source: §4.2 · p. 8, Table 3 · p. 9

4.3 Transferability

• GFT consistently outperforms GAT and GIANT whether pre-training uses all datasets, only the target dataset, or excludes the target dataset.Performance improves with excluded-target pre-training compared with target-only pre-training, which the authors hypothesize reflects positive transfer from non-target computation trees.Source: §4.3 · pp. 8–9, Table 5 · p. 10
• More pre-training datasets consistently improve GFT performance across target datasets, whereas existing GFMs can experience negative transfer from dataset selection.The comparison uses FB15K237, Arxiv, and ChEMBL for pre-training and Cora, WikiCS, WN18RR, and HIV as targets.Source: §4.3 · p. 9, Figure 7 · p. 10

4.4 Ablation Study

• Jointly optimizing feature, semantic, and topology reconstruction achieves the best ablation performance, while prototype-plus-linear tree classification also performs best.Semantic reconstruction is especially effective for node- and graph-level tasks, whereas feature reconstruction benefits link-level tasks; removing vocabulary-quality strategies degrades performance.Source: §4.4 · p. 9, Table 4 · p. 10
• Using a tree vocabulary significantly improves performance, particularly for link- and graph-level tasks, but increasing token count often yields only marginal gains.This aligns with the theoretical claim that the vocabulary improves generalization.Source: §4.4 · p. 10, Table 6 · p. 10

5 Conclusion

• GFT combines computation-tree reconstruction for cross-domain pre-training with computation-tree classification for adaptation across node-, link-, and graph-level tasks.The authors validate computation-tree transferability both empirically and theoretically.Source: §5 · p. 10
• The analysis focuses on message-passing GNNs and excludes graph transformers and expressive GNNs with specialized computational architectures.The authors also note possible isomorphism-related expressiveness limitations and deployment efficiency issues.Source: §5 · p. 10
• GFT is designed for rapid adaptation when labels are extremely limited, including applications such as molecular discovery and financial fraud detection.These applications are presented as areas where label acquisition is challenging and model training is time-consuming.Source: §5 · p. 10

A More Related Work

• Unlike graphon, spectrum, and subgraph-based approaches, this work treats computation trees as transferable patterns and validates their transferability empirically and theoretically.The paper positions computation trees as a distinct expansion of prior computation-tree analysis in graph learning.Source: A More Related Work · pp. 18–19
• Prior graph foundation models generally address task or domain alignment separately and do not effectively handle datasets spanning multiple domains and tasks.Related approaches use subgraphs, prompts, LLMs, or feature-space alignment, but remain limited in scope.Source: A More Related Work · pp. 18–19
• Computation trees are established graph structures used for GNN enhancement, graph similarity, and structural analysis before being repurposed here as a transferable vocabulary.Prior work includes tree decomposition, subtree kernels, and tree-based graph distances.Source: A More Related Work · p. 19

B.1 Computation Tree Decomposition and Encoding

• Each message-passing layer costs O(|E| · d + |V| · d^2), giving total model complexity O(L · (|E| · d + |V| · d^2)).Aggregation is edge-wise, while neural-network updates are node-wise.Source: §B.1 · p. 20
• Node-level embeddings and pooled link- or graph-level embeddings are obtained with O(1) task-specific aggregation complexity.Node tasks directly use target-node computation-tree embeddings; link and graph tasks use nonparametric pooling.Source: §B.1 · p. 20

B.2 Subgraph Extraction

• Explicit ego-graph extraction for all nodes can cost O(|V|^3) with an adjacency-matrix BFS implementation.This is the cost described for current subgraph-based graph foundation models.Source: §B.2 · p. 20

B.3 Vector Quantization

• Vector quantization costs O(|T| · K · d), dominated by measuring each computation tree against all K vocabulary tokens.Selecting the nearest token and replacing the embedding add lower-order costs.Source: §B.3 · p. 20

B.4 Tree Reconstruction

• Joint computation-tree reconstruction has approximate complexity O(L · (|E| · d + |V| · d^2) + |T| · d).Feature, topology, and semantic reconstruction contribute decoder, edge, and additional GNN costs.Source: §B.4 · p. 20

B.5 Tree Classification

• Tree classification has approximate complexity O(|T| · |C| · d) when prototype-based and linear classifiers are combined.The prototype classifier’s distance computations dominate the linear classifier cost.Source: §B.5 · p. 20

C.1 The Difference Between Computation Tree and Subgraph

• Subgraph-based GFT uses about 1/3 more time and runs out of memory above batch size 2048, whereas computation-tree GFT fits up to 8192.The subgraph version also performs worse than GFT in the reported comparison.Source: §C.1 · p. 21, Table 7 · p. 21

C.2 Preventing Vocabulary Collapse

• Cosine-distance token queries and commitment loss are used to prevent vocabulary collapse and stabilize discrete tree-token training.The authors report that Euclidean-distance querying caused collapse, while cosine distance constrains queries to a hypersphere.Source: §C.2 · p. 22

C.3 Scaling to Large-scale Graphs

• Subgraph sampling enables mini-batch training and augments computation-tree diversity, while prototype classification uses a per-class memory bank for efficiency.The memory bank samples a small subset from each class because the authors found that limited per-class samples suffice.Source: §C.3 · p. 22

C.4 Discussion on Homophily and Heterophily

• GFT is evaluated only on homophily graphs, although the authors argue that similarity-based transfer and adaptive tree classification support future heterophily applicability.Experiments on heterophily graphs are left for future work.Source: §C.4 · p. 22

C.5 Comparison to VQGraph

• Compared with VQGraph [96], GFT learns cross-domain, cross-task transferable tokens for varied settings, whereas VQGraph targets single-dataset node classification and structural assistance.Both methods use vector quantization, but GFT uses tokens directly to build classifiers.Source: §C.5 · p. 22

C.6 Comparison to LLM-based Methods

• Unlike LLM-based graph reformulations [17] [22], GFT retains a GNN encoder to analyze graph patterns, treating those approaches as complementary.The comparison identifies graph-to-sentence alignment and structural inference as challenges for LLM-based methods.Source: §C.6 · pp. 22–23

C.7 Comparison to Subgraph-based GFMs

• GFT avoids explicit subgraph extraction while preserving computation-tree information that basic GNNs can learn, addressing time, memory, and learnability concerns.GFT has 7 million parameters, compared with 2 million for Prodigy [30], 29 million for OFA [45], and 180 million for UniGraph.Source: §C.7 · p. 23, Table 8 · p. 23

C.8 Detailed Illustration of Computation Tree Reconstruction

• The reconstruction objective is illustrated at three levels as part of GFT’s computation-tree pretraining procedure.The supplied figure caption identifies the three-level reconstruction illustration but does not specify the individual levels.Source: Figure 9 · p. 23

D.1 Proof for Theorem 2.2

• Theorem 2.2 bounds the Euclidean distance between embeddings of two L-layer computation trees produced by one GNN encoder.The proof analyzes node-wise differences recursively from the leaves upward.Source: §D.1 · pp. 23–24
• The proof assumes bounded features and weights, Lipschitz GNN components, shared layer parameters, and aligned tree structures created with zero-feature virtual branches.Branch counts are bounded by a maximum d, enabling a simplified recursive bound.Source: §D.1 · pp. 24–25

D.2 Proof for Theorem 3.1

• The generalization analysis decomposes the token classifier into pairwise binary subclasses, yielding at most p · (p −1)/2 subclasses.The proof connects vector quantization with margin-based classification and uses Gaussian complexity to bound risk.Source: §D.2 · p. 27
• The margin-based token classifier has risk bounded by empirical risk plus 20 · C · p(p −1) · B3 · √n.Here p is the number of tokens, C is a constant, B bounds feature and token norms, and ρ is the margin penalty.Source: §D.2 · p. 26

E.1 Synthetic Dataset

• Synthetic transfer experiments sample four-dimensional node features and repeat runs 100 times, measuring transferability with inverse CMD.The source and target graphs contain the same number of blocks.Source: §E.1 · pp. 27–28
• Higher computation-tree similarity correlates with better transferability for synthetic targets G2 and G3, while motif similarity has marginal impact.The authors leave link-level and graph-level analyses for future work.Source: §E.1 · p. 28, Figure 11 · p. 28, Figure 12 · p. 28

E.2 Real-world Dataset

• The real-world study uses airport graphs for homophily and university-web graphs for heterophily, with node classification into five categories.It evaluates both randomly sampled and raw node features because features also relate to graph homophily and heterophily.Source: §E.2 · p. 28

F.1 GNN Encoder

• The encoder is a basic two-layer GCN with ReLU activation, while the implementation appendix notes that more expressive encoders could potentially improve performance.The experiments average results over repeated runs with separate fine-tuning rates for homophily and heterophily graphs.Source: §E.2 · pp. 28–29, §F.1 · p. 29

E.2 Real-world Dataset

• Higher tree similarity correlates with improved transferability even when node features are randomly initialized.The result is reported for homophily and heterophily graphs with random features.Source: §E.2 · p. 29, Table 9 · p. 29

F.2 Dataset

• The dataset suite contains nine datasets from various domains and tasks, using Sentence Transformer features for node and edge text except knowledge-graph edge text.Dataset statistics are summarized in Table 10.Source: §F.2 · p. 29, Table 10 · p. 30
• Dataset splits follow standard or official protocols, with repeated random-seed runs and explicitly reported edge counts for FB15K237 and WN18RR.Cora and PubMed use 20 labeled nodes per class, while WikiCS uses 5% of nodes per class.Source: §F.2 · pp. 29–30

F.3 Baseline

• Baselines span supervised GNNs, self-supervised GNNs, graph few-shot methods, and graph foundation models including Prodigy [30] and OFA [45].The supervised set includes Linear, GCN [40], GAT, and GIN.Source: §F.3 · p. 30

F.4 Hyper-parameter Setting

• GFT pretraining uses a two-layer 768-dimensional encoder, 128 tokens, AdamW, 25 epochs, batch size 1024, and 0.2 edge and feature drop rates.Topology reconstruction selects 10% of links and an equal number of negative samples.Source: §F.4 · pp. 30–31
• The experiments use an NVIDIA A40 with 48GB memory, while both phases can also run on a single 24GB RTX 3090.Fine-tuning hyperparameters are listed in Table 11.Source: §F.4 · p. 31, §F.5 · p. 31, Table 11 · p. 31

• Average model results are reported for the pre-training and fine-tuning settings.The section evaluates performance across these two settings.Source: G Pre-training and Fine-tuning Results… · p. 31
• The reported evaluation concerns model performance in both training settings.Source: G Pre-training and Fine-tuning Results… · p. 31, Table 12 · p. 31
• Table 12 contains the model results together with their standard deviations.Source: Table 12 · p. 31

H Additional Few-shot Learning Results

• Across the extended few-shot evaluations in Tables 13–19, with 20 tasks sampled per run, GFT significantly outperforms OFA across datasets and Prodigy on Arxiv and FB15K237, while surpassing specialized few-shot methods.Source: H Additional Few-shot Learning Results · p. 31, Table 13 · p. 32, Table 14 · p. 32
• Increasing the number of fine-tuning instances per class markedly improves GFT performance.Source: H Additional Few-shot Learning Results · pp. 31–32
• Even with extremely limited training instances, GFT substantially outperforms the baselines, demonstrating rapid adaptation to target tasks.Source: H Additional Few-shot Learning Results · pp. 31–32

I.1 Pre-training Datasets

• Using all pre-training datasets typically performs best, while excluding the target graph can outperform pre-training solely on that graph.The authors attribute this to shared computation trees across domains and a more comprehensive approximation of their distribution.Source: §I.1 · pp. 32–33, Table 20 · p. 33

I.2 Pre-training Tasks

• Jointly optimizing three reconstruction tasks achieves the best performance, and every reconstruction task improves performance over no pre-training.Source: §I.2 · p. 33, Table 21 · p. 34

I.3 Strategies for Enhancing Tree Vocabulary

• Removing either augmentation or the orthogonal regularizer degrades performance, supporting their roles in tree-vocabulary quality.Source: §I.3 · pp. 33–34, Table 22 · p. 34

I.4 Fine-tuning Tasks

• Combining linear and prototype classifiers performs best, with the prototype classifier strongest for node-level tasks and the linear classifier better for the other two tasks.Source: §I.4 · p. 34, Table 23 · p. 34

I.5 Tree Vocabulary

• The 512-token vocabulary is best in only four of eight scenarios, while using a vocabulary substantially improves link- and graph-level tasks.The authors relate the non-monotonic token-count effect to overfitting risks and limited domain diversity.Source: §I.5 · pp. 34–35, Table 24 · p. 34