GFT: Graph Foundation Model with Transferable Tree Vocabulary
Authors: Zehong Wang
Zheyuan Zhang
Nitesh V Chawla
Chuxu Zhang
Yanfang Ye
Venue: NeurIPS 2024 poster (2024)
Keywords: Graph Foundation Model
Transferability
Computation Tree
Graph Neural Network
Primary area: graph_neural_networks
TL;DR: We investigate the transferability of computation tree in the graph, and build a graph foundation model based on that.

Abstract: Inspired by the success of foundation models in applications such as ChatGPT, as graph data has been ubiquitous, one can envision the far-reaching impacts that can be brought by Graph Foundation Models (GFMs) with broader applications in the areas such as scientific research, social network analysis, drug discovery, and e-commerce. Despite the significant progress of pre-trained graph neural networks, there haven’t been GFMs that can achieve desired performance on various graph-learning-related tasks. Building GFMs may rely on a vocabulary that encodes transferable patterns shared among different tasks and domains. Unlike image and text, defining such transferable patterns for graphs remains an open question. In this paper, we aim to bridge this gap by rethinking the transferable patterns on graphs as computation trees -- i.e., tree structures derived from the message-passing process. Based on this insight, we propose a cross-task, cross-domain graph foundation model named GFT, short for Graph Foundation model with transferable Tree vocabulary. By treating computation trees as tokens within the transferable vocabulary, GFT improves model generalization and reduces the risk of negative transfer. The theoretical analyses and extensive experimental studies have demonstrated the transferability of computation trees and shown the effectiveness of GFT across diverse tasks and domains in graph learning. The open source code and data are available at https://github.com/Zehong-Wang/GFT.

GFT: Graph Foundation Model with Transferable Tree Vocabulary
Zehong Wang
Zheyuan Zhang University of Notre Dame Indiana, USA zzhang428nd, edu
University of Notre Dame
Indiana, USA
zwang43önd.en edu
Nitesh V Chawla
Chuxu Zhang"
Yanfang Ye*
University of Notre Dame
University of Connecticut Connecticut, USA chuxu. zhanguucnng edu
University of Notre Dame Indiana, USA yye70nd edu
Indiana, USA nchawla@nd.c edu
Abstract
Inspired by the success of foundation models in applications such as ChatGPT, as graph data has been ubiquitous, one can envision the far-reaching impacts that can be brought by Graph Foundation Models (GFMs) with broader applications in the areas such scientific research, social network analysis, drug discovery, and e-commerce. Despite the significant progress of pre-trained graph neural networks, there haven't 't been GFMs that can achieve desired performance on various graph-learning-relate tasks. Building GFMs may rely on vocabulary that encodes transferable patterns shared among different tasks and domains. Unlike image and text, defining such transferable patterns for graphs remains open question. this paper, we aim to bridge this gap by rethinking the transferable patterns on graphs as computation trees i.e., tree structures derived from the message-passe paasagg process. Based on this insight, we propose a cross-task, cross- domain graph foundation model named GFT, short for Graph Foundation model with transferable Tree vocabulary. By treating computation trees as tokens within the transferable vocabulary, GFT improves model generalization and reduces the risk negative transfer. The theoretical analyses and extensive experimental studies have demonstrated the transferability of computation trees and shown the effectiveness of GFT across diverse tasks and domains in graph learning. The open source code and data available at attttps:// ttthtps://githe h/tp:s////ttbbb..t cwt. Hean/ZZeonn--aaan Wannonn
Introduction
Foundation models such Large Language Models (LLMs) and Large Vision Models (LVMs) keep reshaping our view of the world 7 100 51 12 [0). These models are designed to be general- purpose, adaptable across various tasks and domains through fine-tuning
prompting, such as GPT-4 [T] in Natural Language Processing (NLP) and Sora [46] in Computer Vision (CV). Research attributes the success of foundation models the uniformity of tasks and general vocabulary that defines basic transferable patterns across tasks (98 76 [12 3 [50]. For example, LLMs [122 treat language tasks as aunestion-answeriine or next-word prediction and deconstruct sentences using word vocabulary. Similarly, LVMs [00 98 3 reformulate image tasks as image ceestion-answering converting images into discrete tokens using vision vocabulary. Inspired by the success of LLMs
"Corresponding Authors.
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

and LVMs, as graph-structured data (e.g., citation networks, social networks, computer networks, molecular structures, and recommender systems) have become ubiquitous, one can envision the far- reaching real-world impacts that can be brought by pre-trained Graph Foundation Models (GFMs).
Although there has been significant progress of pre-trained Graph Neural Networks (GNNs), there haven't It been GFMs that can achieve desired performance on a wide range of graph-learning-elle tasks. Unlike CV and NLP, as graphs represent complex, non-Euclidean relationships among entities 192 48
T04, 558 107 a grand challenge of building GFMs lies in identifying transferable patterns 25]. There have been extensive studies aiming to tackle this challenges. which can mainly be categorized into two groups: (1) Utilizing graphon theory: Ruiz et al. [62] provide theoretical evidence of transferability between two graphs generated from the same graphon. Cao et al. [8] further extend these findings by both empirically and theoretically analyzing graph transferability in pre-training and fine-tuning scenarios. Despite these theoretical guarantees, the stringent assumptions of graphon theory often prove difficult to satisfy in real-world, cross-domain datasets [42) thus limiting its applicability in defining transferable graph vocabularies. (2) Exploring Zhu et al. [114] demonstrate that the transferability between graphs is linked to the ego-graph patterns of individual nodes and establish stability bound using the graph Laplacian. They suggest that localized subgraphs could serve as transferable patterns within graph vocabularies. Building on this finding, Sun et al. [68] develop a GFM by reformulating graph tasks as subgraph classification, enabling single model to be applied to diverse tasks. Huang et al. [30], Liu et al. [45] expand GFMs to drossndomain scenarios by unifying the node feature space across different graphs through LLMs (60 76). Despite these successes, the
across graphs 50
graph transferability using subgraph structures [144 59 50
process of explicit subgraph extraction remains time and memory intensive 330. More importantly,
numerous studies such as 220 10 53 [03] show that cessage-passingg GNNs 40 24 21 fail to
detect critical substructures or motifs within subgraphs, reducing the feasibility of using subgraphs to define graph vocabularies.
How to identify a vocabulary that can encode transferable patterns shared among different tasks and domains for the construction of GFMs? In this paper, we aim to address the limitations of existing works by answering this question. Specifically, based on message- pasaagggganiinggggg mechanism of GNNs, have observed that the learned embeddings of each node can be essentially captured in the form of its computation tree. Based on this insight, we bridge the research gap by rethinking the transferable patterns graphs as computation trees i.e., subtree structures derived from the message-passing
message- passing process. Using computation tree as a transferable pattern across graphs will bring three primary advantages: (1) Efficiency: As the extraction and encoding of computation trees are integrated within a single message-passing passing GNN process 200) it eliminates the need for the explicit subgraph extraction for GFMs 30 45) (2) Expressiveness: Since computation trees are capable of capturing localized patterns 52 it's able to represent a graph as a multiset of computation trees [33 (3) Learnability: As the information of computation trees is completely captured by pesssage-passingg
GNNs. it can tackle the issue that certain motifs within subgraphs remain elusive. We theoretically investigate the transferability of computation trees and empirically demonstrate a strong correlation between computation tree similarity and transfer learning performance across various graphs
Based on the key idea above, by treating computation trees graph vocabulary tokens, develop a cross-task, cross-domain graph foundation model - namely GFT - short for Graph Foundation model with transferable Tree vocabulary. GFT consists of pre-training and fine-tuning phases, enabling it to handle datasets across different tasks and domains effectively. During pre-training, we introduce a computation tree reconstruction task to acquire generalized knowledge from rross-domain graphs. We obtain a discrete tree vocabulary of prototypical tree tokens by quantizing the embedding space of computation trees, which theoretically improves model generalization. In the fine-tuning phase, we utilize this learned tree vocabulary to unify various graph-related tasks into computation tree classification, thereby preventing negative transfer [89 87). Extensive experimental results demonstrate the effectiveness of GFT in graph learning on cross-task and cross-domain datasets.
2 Rethinking Transferable Patterns on Graphs
2.1 Transferability on GNNs
Transferability refers to 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
2

---

patterns is essential for developing graph foundation models. Early research focuses on analyzing transferability through the perspectives of graph spectrum 4 and subgraphs/aubsttrcturrss [T14]. defining transferabilitty 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 motif's [103), such triangles, k-cliques, and stars, serve as fundamental components for graph classification. Another line of research [62] S [6]] incorporates graphon theory to provide a theoretical basis for transferability. Specifically, Ruiz et al. [62 establish bound on the embeddings of two graphs sampled from the same graphon. Cao et al. [8] expand this to include pre-trate 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 [08] or tasks [14 III [9] exhibit transferable patterns, the challenge of
identifying universally transferable substructures is difficult. (2) More critically, basic message-
passing GNNs, constrained by the I-WL test [94] [22 fail to recognize certain subgraphs (or motifs) 20 10 [03], such as stars, conjoint cycles, and k-cliques, as well as heterophily patterns [13]. 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
2.2
Computation Tree as Transferable Pattern
In this paper, we rethink the transferable pattern in graphs as the computation tree specialized subtree pattern that emerges from unfolding the message-passingg process [1]. This pattern demon- strably effective at capturing critical localized information within Treating computation trees as tokens within a graph vocabulary offers two distinct advantages: (1) com- putation 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- tasks. These tasks can be unified as computation tree classification by integrating a virtual node, as shown in Figure !I
Task-relevant Nodes
Node
Link
Graph
the graph (20 52 94
Graph tasks (top) and the corresponding compu- tation trees (bottom). A vir- tual node can be added at the top to connect all task relevatt nodes, unifying different tasks as the tree-level task.
Figure 1:
Before diving into transferability analysis, we first establish the necessary notations. Consider graph G = (V,E) composed of node set V and edge set E. Each node v E V is associated with a feature vector x, E IRd and a computation tree T, with I. layers. GNN encoder á processes these computation trees as inputs, producing embeddings for root nodes ((T)) E Rdd..
Definition 2.1 (Computation Trees 122 Given graph G = (V, define T, v and T as the L-layer computation tree. This tree is constructed by recursively integrating the subtrees of neighborhoods. The multiset of L-layer computation trees on graph G is denoted by T == (T JOEv.
Figure I 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 [2]. If the L-layer computation trees for two nodes are similar, it indicates that these nodes share similar neighborhoods, suggesting they represent analogous phenomena [4) Thus, it is rational assess transferability of computation trees by examining the stability of GNNs in producing analogous embeddings for similar trees 62 42
Theorem 2.2 (Transferability of Computation Tree Given two L-layer computation trees T Toz
derived from the graph G and a GNN encoder de the Euclidean distance between the tree embeddings
& [[0(TT)) - o(Toz) ll2 112 is bounded as follows:
L
A < C111x,, - X22l12+ + C2
Σ JEA(()
S 2B + cd)
(1)
1=1
3

---

where A represents the distance between the (L - -l-layer subtrees of the j-th children of nodes U1 and U2. C₁, C2 are constants, and Bx denote bounded norm of x. The variable di indicates the number of children in the l-layer subtrees, and Di d:d1-1...d.
Proof. All proofs in the paper are detailed in Appendix D
Remark 2.3. Theorem 2.2 derives recursive bound for computation tree similarity. In particular, the distance between two computation trees closely correlated the similarity of their subtrees, where higher subtree similarity results in closer distance. This suggests that computation trees with similar structures are likely to have similar embeddings, which enhances their transferability 114 33 62]. This aligns with our empirical observations that higher computation tree similarity between two graphs leads improved transferability.
Supportive Observations- - Synthetic Graphs. Fioor that high computation tree similarity between graphs correlates with improved transfer learning performance on synthetic graphs (Figure 2}. Specifically, we construct three distinct graphs: 91 and 92 share similar motifs but differ in computation tree distributions, while G1 and G3 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 [022 to measure transferability. Further details on experimental settings and additional results are available in Appendix E.I] Our findings indicate that transferability is strongly associated with computation tree similarity rather than motif similarity, regardless the scale of graphs (# blocks).
91
G2
Transferabllty
Sim.
Molif Sim.
Gemph?
Gragh2
Figure 2: Synthetic graphs composed of two basic blocks. More blocks can scale up the graph sizes.
BBockss
Blocks
Figure 3: Transfer performance synthetic graphs with 9 as the target graph. Higher tree similarity correlates with enhanced transferability.
Supportive Observations Real-world Graphs. Table I validates the correlation between computation tree similarity and transferability in real-world graphs, including homophily Airport [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-works 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 L or randomized node features (Table 9..
networks [6] and heterophily WebKB networks
Table 1: Transfer learning performance on homophily (above) and heterophily (below) graphs. For any target graph, source graphs with higher tree similarity lead to improved accuracy, highlighted with Blue Conversely, the influence of motif similarity is marginal, marked by LightBlue.
Gearget
Brazil
Europe
USA
Gvource
Europe
USA
Brazil
USA
Brazil
Europe
Motif Sim.
99.01
92.65
99.00
96.81
92.68
96.81
Acc. / Tree Sim.
53.1 / 34.6
56.8 62.2
50.8 / 34.6
51.4 88.7
54.5 62.2
57.9 88.7
Gearget }
Cornell
Texas
Wisconsin
Gumucce
Texas
Wisconsin
Cornell
Wisconsin
Cornell
Texas
Motif Sim.
99.97
99.98
99.99
99.99
99.98
99.99
Acc. / Tree Sim.
46.5 65.3
42.4
56.0/65.3
53.1
4
48.2 / 41.7
3 GFT: Graph Foundation Model with Transferable Tree Vocabulary
We develop GFT, a cross-domain and cross-task graph foundation model that leverages computation trees as transferable patterns within graph vocabulary. As illustrated in Figure 4 GFT undergoes

---

(a) Pre-training with Tree Reconstruction
Tree Reconstruction Eq. (3)
Orthogonal Regularizer Eq. (5)
Graph
Computation
Encoder
Tree Vocabulary
Database
8
Appp
Query
Assign
o0o
Lymas
orcho
(b) Fine-tuning with Tree Classification
Freeze
Linear Classifier
Query
Assign
Single Token
Unify Graph Tasks as Tree Classification
Unseen
Fixed
8
Prototype Classifier
Graph
Tree Vocabulary
Memory Bank
Figure 4: During pre-training. GFT encodes general knowledge from graph database into tree vocabulary through tree reconstruction. fine-tuning, the learned tree vocabulary applied to unify graph-related tasks as tree classification, adapting the general knowledge to specific tasks.
pre-training through computation tree reconstruction task to acquire general knowledge from a cross- domain graph database. Subsequently, GFT quantizes the embedding space of computation trees to form discrete tree vocabulary, encapsulating fundamental, transferable computation tree patterns for diverse tasks. In the fine-tuning phase, GFT utilizes this tree vocabulary to unify graph-related tasks (including node-, link-, and graph-level tasks) as computation tree classification, adapting the general knowledge to specific target tasks.
3.1 Pre-training with Computation Tree Reconstruction
The pre-training stage focuses on learning general computation tree patterns graphs, facing two primary challenges: (i) obtaining transferable patterns, and (ii) comprehensively capturing computation tree knowledge. For the first challenge, we Iearn 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 a distributed manner. By adopting these principles, the tree vocabulary maintains set of tokens that are reusable and adaptable across various tasks, improving model transferability.
We adopt the Vector Quantization (VQ) 777 to develop the vocabulary. Given graph database D D= (G.) we randomly extract a set of computation trees T = {Ti)e and employ GNN encoder to generate the tree embeddings
{z, J We define the computation as set of learnable tokens C = {CI...., Cк The tree embedding space is quantized by assigning each embedding to the nearest token, resulting
vocabulary
quantized tree embeddings qi Cj. where j arg min, | - cl. We optimize this projection by back-propagating the reconstruction error to the tree vocabulary C and applying a straight- straight-through gradient estimator (6) the encoder 6. 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 using the fixed quantization 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 thus defined as:
1
m
m ca112 + m 2 lz. sgica]ll
Cpretrain Ltree + m
sg[z,]
(2)
vocabulary loss
commitment loss
where sg/-| denotes the stop- gradient operator and 31 the weight.
"e 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 beyond the scope of this paper.
5

---

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 feat. (ii) reconstructing the connectivity among nodes in the computation trees Loopo and (iii) reconstructing the overall semantics of the computation trees Leem:
I
1
m
1
m
q
feett
q
X;
Ssem
(3)
m
m
| |112211
Liopo Σ
log
(q
93)
log 1
(q T + E
q3:))
q [
eij
[
where 2; = (TT) represents the semanties of the original computation trees, and o is updated through a moving average of the tree encoder Φb. The quantized tree embedding is projected via different decoders defined by MLP. q' = ōj (q). 7 is the scaling factor, and & and & represent sets of existing and non-existing connections in computation trees, respectively. eiy denotes the edge embedding between nodes i and j. By jointly optimizing these tasks, we establish comprehensive reconstruction objective:
Stree = B2 feeat + A33 Lyem + B4 -topor
where 8; 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 Leopo. Hou et al. (26) reconstruct node
feature that is similar to Leent, and Thakoor et al. (74), Wang al. [86) employ contrastive learning
to maximize the alignment between two views, aligning to Lgem- Unlike existing methods that
typically focus on reconstructing a single aspect of computation trees, GFT integrates multiple facets [85] to learn general and transferable tree vocabulary.
Enhaneing 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 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 orthogonal regularizer designed to maintain tree tokens orthogonal to each other, effectively expanding the tree token space:
|CT
Im C= (ci,,,.. ck]" E Rxx''
Lartho
K2
where c; is tree token, IK is the identity matrix for K dimensions, and || || denotes the Frobenius norm. The orthogonal loss Lortho is integrated with Equation 2
More analysis is in Appendix C.2
3.2 Fine-tuning with Computation Tree Classification
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 Figure [ Specifically, for node classification, the task-specific computation tree, denoted as Trode Te, is derived directly from the node itself, resulting in the embedding z = ((T)). For link prediction, the computation tree, Trink Combine (T., Te), merges the computation trees of two nodes of the edge, with the embedding

---

= mean (e..) (T))). For graph classification, the task-specific computation tree graph Combine (T hev)) integrates the computation trees of all nodes within the graph, and computes the Subsequently, the embeddings of these task-specific trees are used query the tree vocabulary and then make predictions, adapting the general knowledge encoded in the vocabulary to various tasks and domains.
embedding as 2 mean( (T(T))
Prototype Classifier. The prototype classifier fproto constructs class prototypes using tokens from the tree vocabulary. Given a set of task-specific computation trees (4 with |C' classes, we J These embeddings
employ the pre-trained GNN encoder @ to generate tree embeddings are then used to query the tree vocabulary and produce quantized embeddings Q {q: 17 Subsequently, we construct a class-wise memory bank S = (.., J. where g = {q: E Qly: = k)., to store tree tokens of the same class. The memory bank typically includes all instances from the training set. From this, we derive set of prototypes for each class {p* calculated as P: (1/1s*1) Eq.es qi- These prototypes are then used for predictions:
exp(- p&)/T)
p(y=k(z) = = E. exp( Pe)/T)²
(6)
where sim(-) denotes the cosine distance and T is a temperature scaling factor. We optimize the cross-entropy loss between the classifier's output and the ground truth to update the encoder Φb.
Linear Classifier. Different from the prototype classifier, which utilizes class prototypes to adapt target tasks, the linear classifier Jiin directly applies the knowledge encoded in each tree token. Specifically, given a task-specific computation tree Tú, we use the encoder to generate tree embeddings z; and then query the tree vocabulary to retrieve q These embeddings are used for predictions as:
exp(Iin((a)))
p(u klz) Σ. exp(lin"(()) (q)/T)*
We optimize the cross-entropy loss between the prediction füi and the ground truth 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 note that the tree vocabulary remains fixed during fine-tuning to preserve the integrity of the encoded knowledge.
3.3 Additional Analysis
Tree Vocabulary Learns Generalizable Tokens. Learning tree vocabulary via VQ involves clus- tering within the embedding space of computation trees, utilizing margin-aware classifier [14] that assigns each computation tree specific cluster. Assuming that each computation tree T is associated with an underlying clustering label y, and that each pair (T;, ys) is sampled from the distribution Py, we derive the following theorem:
Theorem 3.1. Given a set of computation trees y:)), sampled from the distribution Pr, the VQ process functions as wurgin-awarr prototype classifier f that predicts the class of computation trees via a distance measure. The risk Rff) of classifier can be bounded with probability 8:
R()) S R(f) + 20 C.ply 1) vnn +
V 12(28/))
(8)
p.
2n
where R(f) is the empirical risk, p denotes the number of tokens, C is constant, and p acts the margin, serving as a penalty factor in evaluating the distance between computation trees and tokens.
Remark 3.2. The generalizability of tokens within the vocabulary highly correlates to the margin p, the number of observed computation trees n, and the number of tokens p. (i) A larger margin p results in tighter bound by ensuring higher inter-cluster distances and lower intra-cluster distances. This supports the use of an orthogonal regularizer (Equation 5) that explicitly pushes tokens apart, enhancing cluster distinction. (ii) An increased number of observed computation trees n leads to tighter generalization bound, which supports the use of augmentations to increase the diversity of computation trees. (iii) More tokens may loose the upper bound of the generalization error, potentially due to higher risk of overfitting. This aligns with our experimental findings that more tokens do not necessarily lead to improved performance (Section
7

---

Tree Vocabulary Mitigates Negative Transfer. Negative Trans- fer (NT) occurs when the pre-training process degrades model performance target task. This issue often results from mis- alignment between the pre-training and fine-tuning tasks [89 [] Following the approach in [89] we characterize the NT gap, T) R0, T), as the risk gap on task T with (R 2") and
0.0
NT Gap
-0.2
w/o Tree Vocab,
Our Method
-0.4
-0.6
without (R(0, T)) pre-training gap indicates improved transferabilityy As illustrated in Figure employing the learned tree vocabulary to align the tree reconstruc- tion task in pre-training and tree classification task in fine-tuning can significantly mitigate negative transfer.
task S. where smaller NT
500
1000
Epochs
Negative transfer gap on Cora in node classification.
Figure 5:
comprehensive complexity analysis of GFT is provided in Appendix B Notably, GFT employs single GNN to decompose and encode computation trees, taking (I. ([ε] - d + -d)). In contrast, subgraph-base GFMs 30 45 require the explicit extraction of subgraphs for each node, taking additional O(D))) 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
Complexity Analysis.
4 Experiments
4.1 Experimental Setting
We employ cross-domain and cross-task graph datasets 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, include two Knowledge Graphs (KGs), WN 8RR 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 44], GAT 778 GIN [94], and self-supervised methods like BGRL (74), GraphMAE (26). GIANT [ 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
4.2 Effectiveness on Cross-Domain and Cross-Task Datasets
Pre-training and Fine-tuning. Table 2 demonstrates the model performance across cross-domain and cross-task datasets pre-training and fine-tuning setting. We evaluate the effectiveness of graph foundation models [30 (55 in the following few-shot setting due their distinctive training mechanisms, such as in-context pre-training [30] and fully supervised training [5]. For supervised basclines, 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- We randomly select k samples per way from the training set for fine-tuning 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 shows more fine fine-tuning instances can significantly improve performance.
supervised methods 774 26 III and graph foundation models [3 45 255
4.3 Transferability
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 ! 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
CCora& & WN18RR: 1; Arxiv: 5; HIV & PCBA: 20; FB15K237: 30.

---

Table Model performance in pre-training and fine-tuning setting. Bold and underline highlight the best and sub-best performance, and and denote a 2% and 5% improvement over the best baseline. The model performance with standard deviation is in Appendix G
Node Classification
Link Classification
Graph Classification
Method
Cora
PubMed
Wiki-CS
Arxiv
WN18RR
FB15X237
HIV
PCBA
Avg.
Linear
58.03
68.66
70.36
66.50
78.50
87.39
66.37
72.30
71.01
GCN 40
75.65
75.61
75.28
71.40
73.79
82.22
64.84
71.32
73.76
GAT 78
76.24
74.86
76.78
70.87
80.16
88.93
65.54
70.12
75.44
GIN 94
73.59
69.51
49.77
65.05
74.02
83,21
66.86
72.69
69.34
DGI 79
72.10
73.13
75.32
69.15
75.75
81.34
59.62
63.31
71.22
BGRI. 74
71.20
75.29
76.53
71.19
75.44
80.66
63.95
67.09
72.67
GraphMAE
26
73.10
74.32
77.61
70,90
78.99
85,30
61.04
63,30
73.07
GIANT
75.13
72.31
76.56
70.10
84.36
87.45
65.44
61.49
74.11
GFT
78.62"
77.19*
79.39*
71.93
91.91
89.72
72.67!
77.901
79.92
Table 3: Few-shot learning performance. Additional results with more baselines are in Appendix
Arxiv
40 way
Arxiv
way
FB15X237
40
way
FB15K237
10 way
Method
shot
3-shot
I-shot
5 shot
3-shot
1 I-shot
5 Sishot
3-shot
I-shot
Shohot
3-shot
1-shot
BGRL 74
17.98
48.43
29.24
67.23
GraphMAF
12
GIANT
20.12
54.33
52.63
77.21
Prodigy
30
25.51
23.69
21.44
61.09
58.64
48.23
62.03
59.58
54.30
84,30
79.61
66.10
OFA
24.01
22. 13
21.34
59.92
58.68
52.80
66.51
65.76
63.48
83.64
83.14
83,46
GFT
36.29
34.36
26.49|
68.10)
66.00
58,20
75.01
74.56
74.97!
89.13/
88.53
88.07|
WK18RR
10-way
5-vay
HIV 2-way
PCBA 2-way
Method
5-shot
3-shot
I-shot
5-shot
3-shot
I-shot
10-shot
5-shot
1-shot
10-shot
5-shot
J-shot
OFA 455
32.64
30.56
25.82
42.28
31.28
23.68
54.36
57.56
57.17
54.58
54.80
54.92
GFT
35.50
35.50
35.33
$2.30
51.47#
49.80
58.67:
58.78
59.94
59.34
59.34
55.88
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 7 For pre- 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 negative transfer 225 This observation underscores the adaptability of using computation trees as transferable patterns in graph vocabulary.
4.4 Ablation Study
Tree Reconstruction and Classification. Table shows the impact of various reconstruction tasks in pre-training and tree classifiers in fine-tuning. All reconstruction tasks enhance model performance compared 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 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 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 1.3

---

y- 0.648x+ 77.310
0,340x 78.660
Table 4: Ablation on tree reconstruction
Accrrso)
Accurso
10
(above) and tree classification (bottom).
Node
Link
Graph
Avg.
Pretrain Dataset
Pretrsin Dataset
Different Pre-training Tasks
(a) Cora (Node)
(b) WikiCS (Node)
n/a
72.52
47.30
73.83
66.54
y y-0.121x +
y- 1.263x 70.638
w. Ssem 76.25
90.39
74.99
79.47
Accursay
Accursy
feat 75.85
90.42
74.42
79.13
Lropo 75.50
90.28
74.57
78.96
125/91227
1CHEMOL
CCHEMOL
Different Fine-tuning Classifiers
Protrain Dalasot
Protrain Datsset
w. fproto 76.64
38.71
59.89
62.97
(c) WN18RR (Edge)
(d) HIV (Graph)
Jiin 75.51
88.99
72.21
78.06
Figure 7: GFT consistently improves model perfor- mance with more pre-training datasets.
GFT
76.78
90.82
75.29
79.92
Table 5: The impact of pre-training datasets.
Table 6: The impact of tree vocabulary.
Node
Link
Graph
Avg.
Nade
Link
Graph
Avg.
GAT (78
74.69
84.55
67.83
75.44
Different Vocabulary Size
GIANT
73.53
85.91
63.47
74.11
Tokens = 128 76.78
90.82
75.29
79.92
Different Pre- Pre-training Datasets
Tokens 256
76.71
90.86
75.17
79.86
Tokens 512
76.94
90.86
75.21
79.99
All Datasets
76.78
90.82
75.29
79.92
Targel Dataset
76.12
90.67
74.08
79.25
Without Vocabulary
Remaining Datasets
75.94
90.71
74.86
79.36
w/o. Vocub. 75.90
86.70
69.17
76.91
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.
5 Conclusion
Conclusion. In this paper, we rethink the transferable pattern in graphs as computation trees and validate their transferability both empirically and theoretically. Building this insight, we propose a cross-domain and cross-task GFM named GFT. This model leverages computation tree reconstruction acquire general graph knowledge from cross-domain datasets and uses computation tree classification to facilitate adaptation to various target tasks. In future work, we aim to explore its capabilities for in-context learning and zero-shot learning.
Limitations. this paper, we focus primarily on message-passing GNNs, as message-passinn can be naturally unrolled as a tree-like structure. However, our analysis excludes graph transformers and expressive GNNs with specialized computational architectures. We plan to extend our analysis to understand the transferable patterns of these advanced learning algorithms in future work. Addition- ally, message-passing GNNs may lack the expressiveness needed to address isomorphism problems in graphs. One can apply advanced techniques [TO5] to handle link isomorphism and use advanced expressive GNNs [03] to tackle graph isomorphism. Moreover, the deployment GFT in real- world applications may encounter efficiency issues, which can be mitigated by techniques like [106] 88).
Boarder Impact. The proposed GFT is a cross-domain and cross-task graph foundation model, designed for rapid adaptation to target tasks with extremely limited labels. We wish our research can support applications where label acquisition is challenging and model training is time-consuming, such in molecular discovery and financial fraud detection.
10

---

Acknowledgments
This work was partially supported by the NSF under grants I1S-2321504, 1IS-2334193, IIS-2340346. IIS-220326,, IIS-2217239, CNS-2426514, CNS-2203261, and CMMI-2146778 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.
References
[1] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Igge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, al. Gpt-4 technical report. arXiv, 2023.
[2] Yushi Bai, Xin Lv, Juanzi Li, and Lei Hou. Answering complex logical queries on knowledge graphs via query computation tree optimization. In ICML., 2023.
[3] Yutong Bai, Xinyang Geng, Karttikeya Mangalam, Amir Bar, Alan Yuille, Trevor Darrell, Jitendra Malik, and Alexei Efros. Sequential modeling enables scalable learning for large vision models. arXiv, 2023.
[4] Peter Bartlett and Shahar Mendelson. Rademacher and gaussian complexities Risk bounds and structural results. JMLR, 2002.
[5] Yoshua Bengio. Deep learning of representations for unsupervised and transfer learning. In ICML Workshop, 2012.
[6] Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating propagating gradients through stochastic neurons for conditional computation. arXiv, 2013.
[7] Rishi Bommasani, Drew A Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx. Michael S Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, al. On the opportunities and risks of foundation models. arXiv, 2021.
[8] Yuxuan Cao, Jiarong Xu, Carl Yang, Jiaan Wang, Yunchao Zhang, Chunping Wang, Lei Chen, and Yang Yang. When to pre-train graph neural networks? from data generation perspective! In KDD, 2023.
[9] Ziwei Chai, Tianjie Zhang, Liang Wu, Kaiqiao Han, Xiaohai Hu, Xuanwen Huang, and Yang Yang. Graphllm: Boosting graph reasoning ability of large language model. arXiv, 2023.
[10] Zhengdao Chen, Lei Chen, Soledad Villar, and Joan Bruna. Can graph neural networks count substructures? In NeurlPS, 2020.
[11] Eli Chien, Wei-Cheng Chang, Cho-Jui Hsieh, Hsiang- Fu Yu, Jiong Zhang, Olgica Milenkovic, and Inderjit S Dhillon. Node feature extraction by self-supervised multi-scale neighborhood prediction. In ICLR, 2022.
[12] Ching- Yao Chuang and Stefanie Jegelka. Tree mover's distance: Bridging graph metrics and stability of graph neural networks. In NeurlPS, 2022.
[13] Weilin Cong, Morteza Ramezani, and Mehrdad Mahdavi. On provable benefits of depth in training graph convolutional networks. In NeurlPS, 2021.
[14] Koby Crammer, Ran Bachrach, Amir Navot, and Naftali Tishby. Margin analysis of the Ivq algorithm. In NewrIPS, 2002.
[15] Kaize Ding, Jianling Wang, Jundong Li, Kai Shu, Chenghao Liu, and Huan Liu. Graph prototypical networks for few-shot learning attributed networks. In CIKM, 2020.
[16] Pascal Esser, Leena Chennuru Vankadara, and Debarghya Ghoshdastidar. Learning theory can (sometimes) explain generalisation in graph neural networks. In NewrIPS, 2021.
[17] Bahare Fatemi, Jonathan Halcrow, and Bryan Perozzi. Talk like graph: Encoding graphs for large language models. In ICLR, 2024.

---

[18] Matthias Fey, Jan-Gin Yuen, and Frank Weichert. Hierarchical inter-message passing for learning on molecular graphs. In JCML Workshop, 2020.
[19] Mikhail Galkin, Xinyu Yuan, Hesham Mostafa, Jian Tang, and Zhaocheng Zhu. Towards foundation models for knowledge graph reasoning. In ICLR, 2024.
[20] Vikas Garg. Stefanic Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. ICML, 2020.
[21] Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George Dahl. Neural message passing for quantum chemistry. In ICML, 2017.
[22] Jiayan Guo, Lun Du, and Hengyu Liu. Gpt4graph: Can large language models understand graph structured data? an empirical evaluation and benchmarking. arXiv, 2023.
[23] Mridul Gupta. Sahil Manchanda, Sayan Ranu, and Hariprasad Kodamana. Mirage: Model- agnostic graph distillation for graph classification. In ICLR, 2024.
[24] Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurIPS, 2017.
[25] Yufei He and Bryan Hooi. Unigraph: Learning a cross-domain graph foundation model from natural language. arXiv, 2024.
[26] Zhenyu Hou, Xiao Liu, Yukuo Cen, Yuxiao Dong, Hongxia Yang. Chunjie Wang, and Jie Tang. Graphmae: Self-supervised masked graph autoencoders. In KDD, 2022.
[27] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In NeurlPS, 2020.
[28] Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec. Ogb-Ise: A large-scale challenge for machine learning on graphs. In NeurlPS, 2021.
[29] Jin Huang, Xingjian Zhang, Qiaozhu Mei, and Jiaqi Ma. Can ilms effectively leverage graph structural information: when and why. arXiv, 2023.
[30] Qian Huang, Hongyu Ren, Peng Chen, Gregor Kržmane, Daniel Zeng, Percy Liang, and Jure Leskovec. Prodigy: Enabling in-context learning over graphs. In NeurlPS, 2023.
[31] Zhongyu Huang, Yingheng Wang, Chaozhuo Li, and Huiguang He. Growing like a tree: Finding trunks from graph skeleton trees. TPAMI, 2023.
[32] Minyoung Huh, Brian Cheung, Pulkit Agrawal, and Phillip Isola. Straightening the straight-through estimator: Overcoming optimization challenges in vector quantized networks. In ICML, 2023.
[33] Junguang Jiang, Yang Shu, Jianmin Wang, and Mingsheng Long. Transferability in deep learning: A survey. arXiv, 2022.
[34] Wengong Jin, Regina Barzilay, and Tommi Jaakkola. Junction tree variational autoencoder for molecular graph generation. In ICML, 2018
[35] Haotian Ju, Dongyue Li, Aneesh Sharma, and Hongyang R Zhang. Generalization in graph neural networks: Improved pac-bayesian bounds on graph diffusion. AISTATS, 2023.
[36] Mingxuan Ju, Tong Zhao, Qianlong Wen, Wenhao Yu, Neil Shah, Yanfang Ye, and Chuxu Zhang. Multi-task self-supervised graph neural networks enable stronger task generalization. In ICLR, 2023.
[37] Pentti Kanerva. Sparse distributed memory. MIT press, 1988.
[38] Pentti Kanerva. Sparse distributed memory and related models. Technical report, 1992.
[39] Thomas Kipf and Max Welling. Variational graph auto-encoders. NewrIPS Workshop, 2016.
12

---

[40] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In ICLR, 2017.
[41] Ron Levie, Elvin Isufi, and Gitta Kutyniok. On the transferability of spectral graph filters. In SampTA, 2019.
[42] Ron Levie, Wei Huang, Lorenzo Bucci, Michael Bronstein, and Gitta Kutyniok. Transferability of spectral graph convolutional neural networks. JMLR, 2021.
[43] Yuhan Li, Peisong Wang, Zhixun Li, Jeffrey Xu Yu, and Jia Li. Zerog: Investigating cross- dataset zero-shot transferability in graphs. arXiv, 2024.
[44] Renjie Liao, Raquel Urtasun, and Richard Zemel. A pac-bayesian approach to generalization bounds for graph neural networks. In ICLR, 2021.
[45] Hao Liu, Jiarui Feng, Lecheng Kong, Ningyue Liang, Dacheng Tao, Yixin Chen, and Muhan Zhang. One for all: Towards training one graph model for all classification tasks. In ICLR, 2024.
[46] Yixin Liu, Kai Zhang, Yuan Li, Zhiling Yan, Chujie Gao, Ruoxi Chen, Zhengqing Yuan, Yue Huang, Hanchi Sun, Jianfeng Gao, et al. Sora: A review on background, technology. limitations, and opportunities of large vision models. arXiv, 2024.
[47] Zemin Liu, Xingtong Yu, Yuan Fang, and Xinming Zhang. Graphprompt: Unifying pre-training and downstream tasks for graph neural networks. In WWW, 2023.
[48] Tianyi Ma, Yiyue Qian, Chuxu Zhang, and Yanfang Ye. Hypergraph contrastive learning for drug trafficking community detection. In ICDM, 2023.
[49] Yao Ma, Xiaorui Liu, Neil Shah, and Jiliang Tang. Is homophily necessity for graph neural networks? In ICLR, 2022.
[50] Haitao Mao, Zhikai Chen, Wenzhuo Tang, Jianan Zhao, Yao Ma, Tong Zhao, Neil Shah, Michael Galkin, and Jiliang Tang. Graph foundation models. In ICML, 2024.
[51] Michael Moor, Oishi Banerjee, Zahra Shakeri Hossein Abad, Harlan M Krumholz, Jure Leskovec, Eric Topol, and Pranav Rajpurkar. Foundation models for generalist medical artificial intelligence. Nature, 2023.
[52] Christopher Morris, Martin Ritzert, Matthias Fey, William L Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and leman go neural: Higher-order graph neural networks, In AAAI, 2019.
[53] Christopher Morris, Floris Geerts, Jan Tönshoff, and Martin Grohe. WI meet vc. In ICML, 2023.
[54] Giannis Nikolentzos, Michail Chatzianastasiss and Michalis Vazirgiannis. Weisfeiler and leman go hyperbolic: learning distance preserving node representations. In AISTATS, 2023.
[55] Karl Pearson. The problem of the random walk. Nature, 1905.
[56] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In ICLR, 2020.
[57] Nataša Pržulj. Biological network comparison using graphlet degree distribution. Bioinformat- ics, 2007.
[58] Yiyue Qian, Tianyi Ma, Chuxu Zhang, and Yanfang Ye. Dual-level hypergraph contrastive learning with adaptive temperature enhancement. In WWW, 2024.
[59] Jiezhong Qiu, Qibin Chen, Yuxiao Dong. Jing Zhang, Hongxia Yang, Ming Ding, Kuansan Wang, and Jie Tang. Gee: Graph contrastive coding for graph neural network pre-training. In KDD, 2020.
13

---

[60] Nils Reimers and Iryna Gurevych. Sentence-bert Sentence embeddings using siamese bert- networks. In EMNLP, 2019.
[61] Leonardo FR Ribeiro, Pedro HP Saverese, and Daniel R Figueiredo. struc2vec: Learning node representations from structural identity. In KDD, 2017.
[62] Luana Ruiz, Luiz Chamon, and Alejandro Ribeiro. Graphon neural networks and the transfer- ability of graph neural networks. In NeurlPS, 2020.
[63] Franco Scarselli, Ah Chung Tsoi, and Markus Hagenbuchner. The vapnik-chervoneniis dimension of graph and recursive neural networks. Neural Networks, 2018.
[64] Nino Shervashidze, Pascal Schweitzer, Erik Jan Van Leeuwen, Kurt Mehlhorn, and Karsten M Borgwardt. Weisfciler-ehhmnn graph kernels. JMLR, 2011.
[65] Woncheol Shin, Gyubok Lee, Jiyoung Lee, Eunyi Lyou, Joonseok Lee, and Edward Choi. Exploration into iunslation-eqiivariaa image quantization. ICASSP, 2023.
[66] Jiawei Sun, Kailai Li, Ruoxin Chen, Jie LI, Chentao Wu, Yue Ding, and Junchi Yan. In- terpGNN: Understand and improve generalization ability of transdutive GNNs through the lens interplay between train and test nodes. ICLR, 2024.
[67] Mingehen Sun, Kaixiong Zhou, Xin He, Ying Wang, and Xin Wang. Gppt: Graph pre-training and prompt tuning to generalize graph neural networks. In KDD, 2022.
[68] Xiangguo Sun, Hong Cheng, Jia Li, Bo Liu, and Jihong Guan, All in one: Multi-task prompting for graph neural networks. In KDD, 2023.
[69] Yifei Sun, Qi Zhu, Yang Yang, Chunping Wang, Tianyu Fan, Jiajun Zhu, and Lei Chen. Fine-tuning graph neural networks by preserving graph generative patterns. AAAI, 2024.
[70] Rajat Talak, Siyi Hu, Lisa Peng, and Luca Carlone. Neural trees for learning on graphs. In NeurlPS, 2021.
[71] Zhen Tan, Song Wang, Kaize Ding, Jundong Li, and Huan Liu. Transductive linear probing: novel framework for few-shot node classification. In LoG, 2022.
[72] Huayi Tang and Yong Liu. Towards understanding generalization of graph neural networks. In ICML, 2023.
[73] Jiabin Tang, Yuhao Yang. Wei Wei, Lei Shi, Lixin Su, Suqi Cheng, Dawei Yin, and Chao Huang, Graphgpt: Graph instruction tuning for large language models. In SIGIR, 2024.
[74] Shantanu Thakoor, Corentin Tallec, Mohammad Gheshlaghi Azar, Mehdi Azabou, Eva L Dyer, Remi Munos, Petar Veličković, and Michal Valko. Large-scale representation learning on graphs via bootstrapping. In ICLR, 2022.
[75] Yijun Tian, Huan Song, Zichen Wang, Haozhu Wang, Ziqing Hu, Fang Wang, Nitesh V Chawla, and Panpan Xu. Graph neural prompting with large language models. In AAAI, 2024.
[76] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Ami Lachaux, Timo- thée Lacroix. Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv, 2023.
[77] Aaron Van Den Oord, Oriol Vinyals, et al. Neural discrete representation learning. In NeurIPS, 2017.
[78] Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
[79] Petar Veličković, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In ICLR, 2019.
[80] Saurabh Verma and Zhi-Li Zhang. Stability and generalization of graph convolutional neural networks. In KDD, 2019.
14

---

[81] Heng Wang, Shangbin Feng, Tianxing He, Zhaoxuan Tan, Xiaochuang Han, and Yulia Tsvetkov. Can language models solve graph problems in natural language? In NeurIPS, 2024.
[82] Song Wang. Chen Chen, and Jundong Li. Graph few-shot learning with task- structures. NeurIPS, 2022.
[83] Song Wang, Kaize Ding, Chuxu Zhang, Chen Chen, and Jundong Li. Task-adaptive few-shot node classification. In KDD, 2022.
[84] Yu Wang and Tyler Der. Tree decomposed graph neural network. In CIKM, 2021.
[85] Zehong Wang, Qi Li, Donghua Yu, Xiaolong Han, Xiao-Zhi Gao, and Shigen Shen. Heteroge- neous graph contrastive multi-view learning. In SDM, 2023.
[86] Zehong Wang, Donghua Yu. Shigen Shen, Shichao Zhang, Huawen Liu, Shuang Yao, and Maozu Guo. Select your own counterparts: Self-supervised graph contrastive learning with positive sampling. TNNLS, 2024.
[87] Zehong Wang, Zheyuan Zhang, Chuxu Zhang, and Yanfang Ye. Subgraph pooling: Tackling negative transfer on graphs. In IJCAI, 2024.
[88] Zehong Wang, Zheyuan Zhang, Chuxu Zhang, and Yanfang Ye. Training mips on graphs without supervision. In WSDM, 2025.
[89] Zirui Wang. Zihang Dai, Barnabás Póczos, and Jaime Carbonell. Characterizing and avoiding negative transfer. In CVPR, 2019.
[90] Qianlong Wen, Mingxuan Ju, Zhongyu Ouyang, Chuxu Zhang, and Yanfang Ye. From coarse to fine: Enable comprehensive graph self-supervised learning with multi-gran aulti-granular semantic ensemble. In ICML, 2024.
[91] Jun Wu, Jingrui He, and Elizabeth Ainsworth. Non-iid transfer learning on graphs. In AAAI, 2023.
[92] Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and S Yu Philip. A comprehensive survey on graph neural networks. TNNLS, 2020.
[93] Lianghao Xia, Ben Kao, and Chao Huang. Opengraph: Towards open graph foundation models. arXiv, 2024.
[94] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019.
[95] Yuchen Yan, Peiyan Zhang Zheng Fang, and Qingqing Long. Inductive graph alignment prompt: Bridging the gap between graph pre- pre-trainin and inductive fine-tuning from spectral perspective. In WWW, 2024.
[96] Ling Yang, Ye Tian, Minkai Xu, Zhongyi Liu, Shenda Hong, Wei Qu, Wentao Zhang, CUI Bin, Muhan Zhang, and Jure Leskovec. Vqgraph: Rethinking graph representation space for bridging gnns and mips. In ICLR, 2024.
[97] Jiahui Yu, Xin Li, Jing Yu Koh, Han Zhang, Ruoming Pang, James Qin, Alexander Ku, Yuanzhong Xu. Jason Baldridge, and Yonghui Wu. Vector image modeling with improved VQGAN. In ICLR, 2022.
[98] Lijun Yu, José Lezama, Nitesh B Gundavarapu, Luca Versari, Kihyuk Sohn, David Minnen, Yong Cheng, Agrim Gupta, Xiuye Gu, Alexander G Hauptmann, al. Language model beats diffusion-tokenizerr is key to visual generation. In ICIR, 2024.
[99] Xingtong Yu, Chang Zhou, Yuan Fang, and Xinming Zhang. Multigprompt for multi-task pre-training and prompting graphs. In WWW, 2024.
15

---

[100] Lu Yuan, Dongdong Chen, Yi-Ling Chen, Noel Codella, Xiyang Dai, Jianfeng Gao, Houdong Hu, Xuedong Huang, Boxin Li, Chunyuan Li, al. Florence: new foundation model for computer vision. arXiv, 2021.
[101] Neil Zeghidour, Alejandro Luebs, Ahmed Omran, Jan Skoglund, and Marco Tagliasacchi. Soundstream: An end-to-end neural audio codec. TASLP, 2021.
[102] Werner Zellinger, Thomas Grubinger, Edwin Lughofer, Thomas Natschläger, and Susanne Saminger-Platz. Central moment discrepancy (CMD) for domain-invarian representation learning. In ICLR, 2017.
[103] Bohang Zhang, Jingehu Gai, Yiheng Du, Qiwei Ye, Di He, and Liwei Wang. Beyond weisfeiler- lehman: quantitative framework for gnn expressiveness. ICLR, 2024.
[104] Chuxu Zhang, Dongjin Song, Chao Huang, Ananthram Swami, and Nitesh Chawla. Hetero- geneous graph neural network. In KDD, 2019.
[105] Muhan Zhang, Pan Li, Yinglong Xia, Kai Wang, and Long Jin. Labeling trick: A theory of using graph neural networks for multi-node representation learning. In NeurIPS, 2021.
[106] Shichang Zhang, Yozen Liu, Yizhou Sun, and Neil Shah. Graph-less neural networks: Teaching old MLPs new tricks via distillation. In ICLR, 2022.
[107] Zheyuan Zhang, Zehong Wang, Shifu Hou, Evan Hall, Landon Bachman, Jasmine White, Vincent Galassi, Nitesh V Chawla, Chuxu Zhang, and Yanfang Ye. Diet-odin: A novel framework for opioid misuse detection with interpretable dietary patterns. KDD, 2024.
[108] Haihong Zhao, Aochuan Chen, Xiangguo Sun, Hong Cheng, and Jia Li. All in one and one for all: A simple yet effective method towards cross-domain graph pretraining. In KDD, 2024.
[109] Jianan Zhao, Le Zhuo, Yikang Shen, Meng Qu, Kai Liu, Michael Bronstein, Zhaocheng Zhu, and Jian Tang. Graphtext: Graph reasoming in text space. arXiv, 2023.
[110] Shuxin Zheng, Jiyan He, Chang Liu, Yu Shi, Ziheng Lu, Weitao Feng, Fusong Ju, Jiaxi Wang, Jianwei Zhu, Yaosen Min, al. Towards predicting equilibrium distributions for molecular systems with deep learning. arXiv, 2023.
[111] Wenqing Zheng, Edward W Huang, Nikhil Rao, Zhangyang Wang, and Karthik Subbian. You only transfer what you share: innrsection-ndduced graph transfer learning for link prediction. TMLR, 2023.
[112] Ce Zhou, Qian Li, Chen Li, Jun Yu, Yixin Liu, Guangjing Wang, Kai Zhang, Cheng Ji, Qiben Yan, Lifang He, et al. A comprehensive survey on pretrained foundation models: A history from bert to chatgpt. arXiv, 2023.
[113] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. In NeurlPS, 2020.
[114] Qi Zhu, Carl Yang, Yidan Xu, Haonan Wang, Chao Zhang, and Jiawei Han. Transfer learning of graph neural networks with ego-graph information maximization. In NeurIPS, 2021.
[115] Yanqiao Zhu, Yichen Xu, Feng Yu, Qiang Liu, Shu Wu, and Liang Wang. Deep graph contrastive representation learning. ICMI. Workshop, 2020.
16

---

Appendix:
Table of Content
A
More Related Work
18
Complexity Analysis
20
B.1
Computation Tree Decomposition and Encoding
20
B.2
Subgraph Extraction
20
B.3
Vector Quantization
20
B.4
Tree Reconstruction
20
B.5
Tree Classification
20
More Analysis
C.1
The Difference Between Computation Tree and Subgraph
21
C,2
Preventing Vocabulary Collapse
22
C.3
Scaling Large-scale Graphs
22
C.4
Discussion on Homophily and Heterophily
22
C.5
Comparison to VQGraph
22
C.6
Comparison to LLM-based Methods
22
C.7
Comparison to Subgraph-based GFMs
C.8
Detailed Illustration of Computation Tree Reconstruction
23
D
Proofs
23
D.1
Proof for Theorem 2.2
23
D.2
Proof for Theorem
3.1
26
E
Detailed Analysis on Computation Tree Transferability
27
E.1
Synthetic Dataset
27
E.2
Real-world Dataset
28
F
Experimental Setup
29
F.1
GNN Encoder
29
F.2
Dataset
29
F3
Baseline
30
F.4
Hyper-parameter Setting
30
F.5
Running environment
Pre-training and Fine-tuning Results with std.
31
H
Additional Few-shot Learning Results
31
Complete Ablation Study
32
L.1
Pre-training Datasets
32
I.2
Pre-training Tasks
33
L3
Strategies for Enhancing Tree Vocabulary
33
I.4
Fine-tuning Tasks
34
I.5
Tree Vocabulary
34
17

---

A More Related Work
Transferability of GNNs. Early studies on the transferability of GNNs are based on two main approaches. The first approach utilizes graphon theory. Ruiz et al. [2] derive bound between the embeddings of two graphs sampled from the same graphon. However, identifying a common graphon in many real-world graphs is often unfeasible, limiting the direct application of this theorem in the design of graph foundation models. Cao et al. [8] employ the graphon theory to analyze transferability in pre-training and fine-tuning setting. They fit pre-trained graphs into graphon space, ensuring transferability if the target graph can be generated within this space. Like Ruiz et al. [62], the challenge lies in acquiring sufficient data to adequately represent the graphon space for graph foundation model. Following this, Sun et al. [69] designed fine-tuning method based on graphon theory. Although these studies consider graphon as a transferable pattern in graphs, the assumption is challenging satisfy in cross cross-domain real-world graphs. Furthermore, graphon theory is generally limited to single-tat taak applications, making it difficult to identify a shared graphon across node-, link-, and graph-level tasks. The send approach examines transferability through subgraphs [[14] or graph spectrum [4 [4). Specifically, Levie et al. [41] analyze transferability from the perspective of stability, positing that effective transferability minimizes the impact of small perturbations. Similarly, Levie et al. (2) explore transferability through stability, demonstrating that transfer hetween graphs feasible when they discretize the same underlying space in a generic sense. Zhu et al. 04 focus on transferability through ego-graphs, showing a higher similar ego-graph distribution leads to better transferability. In contrast to these two approaches, we treat computation trees as transferable patterns on graphs, and conduct both empirically and theoretically analysis to show their transferability. Additionally, we develop a graph foundation model that utilizes these computation tree patterns.
Generalization of GNNs. Generalization is a closely related topic to transferability. For instance, Scarselli al. [63 pioneer the analysis of GNNs' VC-dimension, focusing solely on the number of nodes. Garg et al. 20 leverage Rademacher complexity to evaluate GNN generalization through computation perspectives. Furthermone, the Rademacher complexity has been extended to transductive settings by Esser et al. [16) and Cong et al. [13]. Under the PAC-Bayesian framework, Liao al. [4] offer tighter generalization bound for GNNs compared Garg et al. [20]. and Ju et al. [35] further improve the bound. Additionally, Sun et al. [66] investigate these bounds through the lens of graph topology. Stability is another lens through which generalization is examined, with Verma and Zhang (8) focusing on 1-layer GNNs and linking generalization to the largest absolute eigenvalue of the graph convolution filter. Tang and Liu [72] further establish bounds for transductive node classification, highlighting the significance of graph structural information for different GNN architectures.
GNN-based Graph Foundation Models. Developing graph foundation models involves two
primary steps: (i) unifying the task space and (ii) unifying the domain space. Several studies focus on aligning the task space. Qiu et al. (59) introduce a self-supervised model that empirically demonstrates the transferability of subgraphs across tasks. Sun et al. (67]. Liu et al. [47] pinpoint the task gap between pre-training and fine-tuning as the primary performance bottleneck, addressing it through link prediction to unify these tasks. Yan et al. 995 further adapt this model to an inductive setting, where the pre- trainini and fine-tuning graphs differ, proposing methods to bridge both the graph signal and structure gaps. Yu et al. (99] implement multi-task pre-training to support various downstream tasks. Sun et al. [68] employ subgraphs as fundamental transferable patterns, integrating node-, link-, and graph-level tasks into unified subgraph-level task. Instead of extensive model fine-tuning, they incorporate learnable subgraph into the original graph. Other research focuses on aligning the domain space. Li et al. [43] introduce a zero-shot graph Icarning framework for cross-domain node classification, leveraging LLMs to unify node features across different graphs. In a similar vein, Zhao et al. [08]] propose a graph prompting method for cross-domain classification, utilizing singular value decomposition to align the feature space across various graphs. However, all of these methods are generally limited to single tasks or domains, and do not effectively address the complexities of datasets that span multiple domains and tasks.
To this end, Huang et al. 30 introduce a graph foundation model that utilizes LLMs to align the feature space of graphs and utilizes in-context learning to facilitate applications in node-level and link-level tasks. In particular, they extract the subgraphs for different tasks and conduct subgraph classification. However, this approach necessitates that the pre-training and fine-tuning tasks be
18

---

identical due to the specialized in-context pre-training strategy. To address this constraint, Liu et al. 45] use LLMs to aligm the feature spaces of cross-domain graph datasets and introduce prompt graph to align various tasks on graphs. Xia et al. [93 leverages graph tokenizer to convert the graph into sequence and propose to use transformer to handle such information. Following, He and Hooi [25] concurrently train GNNs and L.LMs to enhance performance further. Despite their empirical success, subgraph-based graph foundation models face challenges due to the GNNs' limitations in encoding substructures within subgraphs. Differently, we rethink computation trees as transferable patterns and propose a new graph foundation model based on that.
LLM-based Graph Foundation Models. LLMs present a promising avenue for the development of graph foundation models due to their ability to unify the output of various graph tasks [2] 8T]
While GNNs require task task-spec adjustments for model training, LLMs can accommodate wide range of questions and generate appropriate answers. The primary challenge. though, lies in effectively translating graph structures into natural language format that LLMs can comprehend. Current efforts in this domain focus on two main approaches. The first is to use natural language to describe the graph structure, such as what the nodes are and which pairs of nodes are connected [17. Such methods can be further enhanced with extra embedding [9] or prompt engineer techniques to enhance the understanding of L.M. For example, Guo et al. [22] employ a self self-prnop methods to utilize the context generated by LLM as input context; Chai et al. [ used Build-a-Graph and Algorithmic prompting to faciliate LLM understanding. Zhao et al. [09 map a graph into tree-like tokens for designing LLM prompt, further enhancing learning capability. Additionally, another line of works follow Visual Language Models (VLMs) to process the graph into embeddings by GNNs first and then employ LLM translator to decode the graph embedding.
77 73
noted that prior research such as Wang al. (T] Huang et [2] indicate that LLMs can indeed capture structural information from graphs, which enhances their performance on downstream tasks. However, while L.MSs show promise in basic graph reasoning tasks like connectivity checks and cycle detection, they struggle with complex graph patterns in graph learning tasks such as node and graph classification. Moreover, there is limited research on cross-domain graph foundation models, largely due to the diverse patterns and distributions of graphs across different domains. This underscores the importance our work in identifying transferable patterns within graphs to pave the way for future advancements in graph foundation models.
Computation Tree. The computation tree, or more broadly, the subtree, is a fundamental structure on graphs [20). It serves to (i) enhance the performance of existing GNNs and to (ii) measure graph similarity. Several studies [34 [8] 77, (84) employ tree decomposition to develop advanced GNNs. Specifically, Jin al. (34) treat the joint tree as complementary the original graphs, while Fey et al. [18] introduce inter-modality message passing between joint trees and the original graphs. Talak al. 77 construct an H-tree by organizing nodes and subgraphs hierarchically, developing a neural tree model capable of approximating any probability distribution on a probabilistic graphical model. Wang and Derr [84) propose a more efficient tree decomposition algorithm by separating the model layer and tree construction. Furthermore, Huang et al. (31) investigate the significance of trees learning node representations and design a framework to identify the most crucial trees in a graph. Additionally, Nikolentzos et al. [54] design hyperbolic learning framework to utilize the computation tree structure in creating expressive GNNs. Bai et al. (2] adapt the computation tree concept to knowledge graphs by optimizing the solution in query computation trees. Another avenue of research utilizes computation tree distributions to measure graph similarity. Notably, Shervashidze et al. [64] introduce the WL subtree kernel to measure discrepancies between graphs based on subtree structures. Chuang and Jegelka [12 employs optimal transport to propose the tree mover's 's distance, estimating distribution shifts between graphs. Wu et al. [91] utilizes hierarchical WL subtree kernel to assess graph discrepancies and derive a generalization bound for cross-domain classification.
Different from these approaches, our work rethink the role of computation trees. We consider computation tree as a transferable pattern on graphs and both empirically and theoretically validate its transfcrability, thereby expanding the analysis for computation trees in graph learning.
19

---

B Complexity Analysis
B.1 Computation Tree Decomposition and Encoding
The decomposition and encoding of computation trees can be jointly finished by message-passing GNNs. Specifically, the learning process in message passing GNNs involves (i) extracting computa- tion trees for each node and (ii) updating node embeddings within these trees from bottom to top. Utilizing GraphSAGE-lis architecture, detailed in Appendix F each layer's learning comprises both aggregation and updating operations. We will analyze these two operations in the following.
Aggregation is an edge-wise operation that propagates messages from neighboring nodes to the target node. Consequently, this operation's is computational complexity is linear to the number of edges in the graph g = (V, E). expressed as [[ d), where d is the embedding dimension. The update process, on the other hand, is a node-wise wide operation that updates the state of each node based on aggregated messages through neural network. Therefore, its time complexity is O(D] df), the complexity of the neural network operations per node (dd)). By integrating both aggregation and update processes in each layer, the overall complexity of our model is O (8) V/ dd)).
For node-level tasks, we directly use the embeddings of computation trees of the target node, which incurs a constant time complexity of (1).. For link-level and graph-level tasks, we apply a non- parametrie pooling function aggregate subtree embeddings into a computation tree embedding. also with time complexity of (1).
B.2 Subgraph Extraction
treat subgraphs as transferable patterns and explicitly extract subgraphs for each node. For a given graph G = (V,E), the extraction of ego-graph for all nodes results in a computational cost of ((VV))) when using an adjacency matrix for the BFS algorithm.
Current graph foundation models 30 45
B.3 Vector Quantization
Vector quantization assigns each instance to the nearest token in the vocabulary. This process involves measuring the distance between the instance and every token, then selecting the token with the minimum distance as the quantized embedding. Assuming there are K tokens, the complexity of distance measurement (no matter Euclidean or Cosine) is O(K x d) per instance. Then, determining the shortest distance from K measured distances can be achieved in (KK,, and replacing the original instance embedding with the selected token requires O(1). Therefore, the predominant computational cost is distance measurement, leading an overall complexity of O(T K K-)), where |T] represents the number of computation trees.
B.4 Tree Reconstruction
The computation tree reconstruction comprises three main tasks: feature reconstruction, semantic reconstruction, and topology reconstruction. Feature reconstruction utilizes a neural network-based decoder with a complexity of (dd) and mean squared enror (MSE) loss of ((T)), resulting in total complexity of (d + [T).. Topology reconstruction focuses on edge information and takes a computational cost of O(E) d). Semantic reconstruction involves an additional GNN and distance measurement, leading to a complexity of O(L (1ε) + [V] d²) + [T| d). Consequently, the
overall computational complexity is approximated O(L (1ε) d + | d2) + +TTI dd).
B.5
Tree Classification
The computation tree classification process employs both a prototype- classifier and linear classifier. The prototype-based classifier constructs prototypes from a memory bank, which incurs complexity of O(T]). It then classifies instances by measuring their distances to these prototypes, resulting in complexity of O([ (CI.d). where |C| represents the number of classes. On the other hand, the linear classifier incurs a complexity of ((T d). Consequently, the total computational complexity can be approximated as O(T)) -C'| d).
20

---

C More Analysis
C.1 The Difference Between Computation Tree and Subgraph
Our concept of computation trees is closely aligned with 12). representing tree-like patterns derived from unfolding the message passing process. Encoding the computation trees of a node equivalent to encoding the node itself via message passing GNNs, implying that the information in computation trees can be fully learned by basic GNNs, demonstrating both learnability and efficiency in encoding computation trees. Notably, computation tree can be reinterpreted as special pattern preserved on the ego-graph the target node, differing from junction trees [34] or H-trees [7],, which construct additional tree-like graphs to complement the original graph.
Subgraphs, on the other hand, are graph-like substructures within the original graph, such as motifs in molecule graphs. Sun et al. [68] identifies subgraphs as basic patterns across graph-related tasks and reformulates these tasks into subgraph-Ieve tasks. For example, node classification, they extract the ego-gret go-grpph around each node and assign the label of the induced graph as the label of the center node, converting node classification into subgraph classification. This process involves (1) extracting ego-graphs around task-relevant nodes and (2) using GNNs to learn graph-level embeddings for classification. However, this extraction process introduces additional time consumption and increased memory usage for storing induced subgraphs. More importantly, the information in subgraphs is not always learnable by basic GNNs, as they cannot detect some critical substructures necessary for learning graph-level embeddings [TO [03]. reducing the feasibility of using subgraphs to define graph vocabularies.
We provide empirical analysis for better understanding. Efficiency analysis is presented in Figure Subgraphs generally incur an extra 1/3 time consumption compared to computation trees and encounter out-of- mittof--emory errors when batch size exceeds 2048, compared to 8192 for computation trees. The performance comparison shown in Table where the subgraph version (GFT Subgraph) performs worse than the computation tree version (GFT). We use GAT and GraphMAE as additional baselines and apply linear classifiers on all models for fair comparison.
Table The comparison between computation trees and subgraphs.
Node
Link
Graph
Avg.
GAT
74.69
84.55
67.83
75.44
GraphMAE
73.98
82.15
62.17
73.07
GFT Subgraph
74.23
86.49
67.89
76.13
GFT Tree
75.51
88.99
72.21
78.06
Memory Usage (%)
GFT
-x- Gub-rabga
GrapMMEE
GFT
Subgrahg
GraphMAE
100
Time (8) Epoch
800
75
50
800
400
210
2
2
2
210
2
Batch Size (log)
Batch Size (log)
(a) The memory allocation in an A40 (48GB) GPU.
(b) The time consumption per epoch.
Figure 8: The efficiency analysis between computation trees and subgraphs. Our GFT is based on the computation trees and we further replace the computation trees with subgraphs called GFT-Subgraph. We compare their memory usage (a) and time consumption (b) during pretraining. With the increase of batch sizes, Subgraph- GFT encounters oft-oo-memory, yet computation tree-based GFT can still fit in the GPU.
21

---

C.2 Preventing Vocabulary Collapse
Another challenge in developing a robust discrete vocabulary known as vocabulary collapse (or codebook collapse in VQ). The commitment loss (Equation 2
effectively prevents this issue by aligning the quantized tree embeddings with the token space [77] Furthermore, we have empirically discovered that using Fuclidean distance to query tree tokens leads to vocabulary collapse. Con- sequently, we have switched to Cosine distance to enforce querying within a hyper-sphere space, thereby enhancing training stability [97]. Alternatively, other techniques such as expiring stale codes
[o1 or affine re-parameterization 32 (not evaluated in this paper) can also be employed to mitigate
this problem.
C.3
Scaling to Large-scale Graphs
Due to the emergence of large-scale graphs [27 28 efficient training often requires the use of mini-batches. We facilitate mini-batch training through subgraph sampling. In pre-training, we employ basic subgraph sampling techniques [24] to extract a smaller graph from the original graph and then extract computation trees for each node within this subgraph. This method serves as an additional topology augmentation, further enhancing the diversity of computation trees through sampling. In the fine-tuning phase, subgraph sampling remains effective for the linear classifier, as it directly processes the computation tree. However, the prototype-base based classifier, which requires the aggregation of instances with identical labels to form class prototypes, faces efficiency challenges in this mini-batch batch training setting. To address this, we randomly sample small subset of the training set for each class to construct the memory bank S. Based on our empirical observations, limited number of samples per class suffices to achieve desirable performance.
C.4 Discussion Homophily and Heterophily
Homophily and heterophily distinction between these types of graphs is that identical connectivity patterns indicate different meanings. We consider our model is also effective for heterophily graphs. Although we only evaluate the performance of GFT homophily graphs (Cora, PubMed, WikiCS, Arxiv), two considerations support its applicability to heterophily graphs: (i) The analysis of computation tree transferability shows that, similar homophily, higher computation tree similarity in heterophily graphs correlates with enhanced transferability, matching the principle of our GFT. (ii) Our proposed computation tree classification in inn-itning can adaptively reinterpret the patterns encoded in the tree vocabulary across various tasks. We will leave the experiments on heterophily graphs in the future work.
49 are both critical properties for node-level tasks. The primary
C.5 Comparison to VQGraph
The major connection between GFT and VQGraph [66] is the usage of vector quantization in learning a discrete vocabulary for downstream tasks. However, there are four major differences between GFT and VQGraph. (1) Model Objective: GFT focuses on building a general task reasoner, but VQGraph aims to train a structure- on cross-domain and cross-task datasets to acquire transferable patterns among graphs, but VQGraph is pre-trained
MLP for efficient inference. (2) Pretrain Dataset: GFT is pre-trained
single dataset to better capture the structural information. (3) Usage of Tokens: GFT treats tokens as specific transferable patterns, using them directly to build classifiers. VQGraph, on the other hand, treats tokens external structural knowledge complement the training of MLP classifiers. (4) Downstream Tasks: GFT can be applied to various graph-related tasks with different settings like few-shot and zero-shot learning. VQGraph is designed for node classification with basic pre-training and fine-tuning setting.
C.6 Comparison to LLM-based Methods
Recent researches 22 81 utilize LLMs to reformulate graph-related tasks as question answering. transforming graph datasets into sentence structures and leveraging the inference capabilities of LLMs to implicitly infer structural knowledge from the original graphs. This approach exploits the transferable patterns in the word vocabulary of LLMs to reinterpret the transferable patterns on graphs. The main challenges include (i) aligning the transformed graphs (sentences) with the word vocabulary of LLMs, and (ii) employing LLMs to infer essential structural knowledge for
22

---

graph-structured data. Due to these challenges, existing methods often fall short in handling graph datasets with LLMs, resulting in inconsistent performance. Unlike these approaches, which entirely abandon GNNs, we utilize GNN as encoder to analyze transferable patterns on graphs. We consider these L.LM-based approaches as complementary our work.
C.7 Comparison Subgraph-based GFMs
Several studies 30 45 identify subgraphs as transferable patterns across graphs, unifying graph-related tasks into subgraph classification tasks and explicitly extracting subgraphs for classification. However, this extraction process incurs additional time and memory costs due to overlapping nodes in the extracted subgraphs. Moreover, other research (00 [03 suggests that certain substructure or motif patterns within subgraphs are not learnable by basic message paassing GNNs. Unlike these methods, our
Table 8: Comparison
of number of parameters across different models
Model
# Params
Prodigy OFA
2M
GFT treats computation trees as transferable patterns, offering advantages over these GFMs in both respects. Firstly, GFT does not require the explicit extraction and encoding computation trees, instead employing message passing to inherently processes computation trees rooted at all nodes, ensuring efficiency in both time and memory. Furthermore, the computation tree can be information loss.
29M
UniGraph
180M
GFT
7M
unique subgraph structure, which is fully learnable by GNNs without
In addition, we also compare the number of parameters of these GFMs in Table g Considering
the number of parameters, Prodigy (30 has million parameters, while OFA 455 has 29 million
since the use of more GNN layers. UniGraph [25] has 180 million parameters, primarily due to its explicit integration with LLMs in encoding node features in an end-to-end way. Our GFT consistently maintains 7 million parameters during both pre-training and fine-tuning phases, making it comparable to Prodigy but significantly fewer than OFA and UniGraph.
C.8 Detailed Illustration Computation Tree Reconstruction
See Figure
Feat. Recon.
(2) Sem. Recon
Topo. Recon.
Dec
Dec
Dec
L
Figure The detailed illustration of reconstruction tasks at three levels.
D
Proofs
D.1
Proof for Theorem 2.2
We restate Theorem 2.2 from the main paper as below.
Theorem D.1 (Transferability of Computation Tree), Given two L-layer computation trees Tu, Toz derived from the graph G and GNN encoder I with parameters W = (W1, W2), the Euclidean distance between the embeddings A [((((TT)) <b((TT)))) )l| is bounded as follows:
Ca - (C2d)L
A C1 1|1 Xx2212+ C2
Σ
A A S 2Bx + Σ C.Di 2Bx
C2d
JEN(v)
where L-11 represents the distance between the L 1-layer subtrees of the j-th children of nodes vn and U2, and constants C₁ = C,Bw,, and C2 = C2 C, Here Cr, Cp, Cg are Lipschitz terms for GNN components, and BB,, By denote bounded norms of W,, W2, x, respectively. The variable indicates the number of children in the l-layer subtrees, with each di S d, and D, d:dj d,di-1...d.
23

---

Proof. We calculate the embedding distance between two L-layer computation trees generated from single GNN encoder o with parameters W (W,, W2). Here we use GraphSAGE- encoder, as described in the Appendix F.T. that W, transforms the target node, while W2 transforms the neighboring nodes. For simplicity, we assume that all GNN layers share the same parameters. Without loss of generality, this assumption does not affect the validity of our proofs. The term represents the features node v, and (v) denotes the set of direct neighborhood in the graph, which correspond to the children of node in the computation tree Tv
With a bit of notation abuse, we define the GNN as:
=o Z. xT,, o (WIX, + W2p E s(T," s(T,-'(W))) JEN(o)
(10)
where a as the non-linear activation fuunctinn, o the permutation-invaarint aggregator function, and as the update function (p and are all based on neural networks). To simplify notation, we denote the computation tree embeddings by T(W)= (TT). Since these functions and neural networks exhibit Lipschitz continuity, we represent their Lipschitz constants as C.. Cp. and Cg. respectively. Additionally, we assume that the norm of node features is bounded by || S Bw,, and the norms of model weights by ||ill & Bw, and W2 || S Bw..
Given the absence of constraints the structures, manually align the structures of the two trees by incorporating non-sense nodes and edges, as depicted in Figure TO Initially, the structures of tree 1 and tree 2 are entirely distinct, illustrated by solid lines. By integrating non-sense branches, we ensure both trees have the same structure, with three branches per node in the first layer and two in the second. These non-sense branches, considered virtual branches, are purely for theoretical analysis convenience and hold no inherent meaning, similar to the approach in [12. Consequently, we assume the node features of each non-sense node to be a zero vector. This alignment of tree structures enhances the coherence of subsequent analyses.
True Branch in Computation Tree
Non-sense Virtual Branch
Tree
Tree
Figure 10: Adding non-sense branches to computation trees to align their structures.
Following, we expand the stability term A:
A a T Th( (W) - (W)
(WIX,, + W2p( Σ
(W)] W2e( Σ
((T,--(())))
vEA((e))
jEA((es)
< C. W im
W2p( Σ
((T.L1(()) (W))) Wix,, War Σ
g(T (W)-)(W)))
(eA(m))
jEN(ma)
< C. Wix Wix02
Co
W2p( Σ
g(T, ((T.-'(())) War( Σ
-
iEN(vz)
JEN(22)
< C.Bw,
Xz. - Xx2
+ CCBB.
R(W. Try) R(W, Th
(11)
24

---

where R(W,7, T,. = R(W, T.y H(W, T
1-1 (W))). We can further bound the term as:
cc,
9(T (W))
Σ s(T)-'(
(12)
(E))
JEN(1))
As we already align the structures of two computation trees by adding non-sense branches to ensure [N(e]] ((t))) (V()))), we can merge the two terms in the RHS:
R(W, R(W, )
c
Σ
Σ
9 3(T
2
JEN(v)
JEN(
I c
Σ
g(T.5 015 (W)) - -T(T (W))
JEN(m)
S C.C.
Σ
T (W) Tobs (
jEN(e)
1
S CpC.
1-1
(13)
JEN(v)
where 14-1 0n [|T (W) - (W)
We now establish bound on the distance between two computation trees of identical structure by analyzing the node-wir wise differences from bottom to top. Denote the number of branches (i.e., children) at each I-layer as di, we simplify this bound follows:
R(W, T R(W, T S CpCgdlm1 max A L-1 2n.
(14)
(EN(M)
This bound prioritizes the most influential children of a node to dominate all other branches. By combining Equation [I] with Equation 14] two computation trees:
we recursively establish the bound of the distance between
A x C, Br. Xxx
X02
+
max AL AL-1 JEN(
2
S Sc Xm1 Xxs
+ C2d2-1 max L-1
(15)
U1.P2.J7
JEN(e)
where C₁ C. and C2 = C.C.g.
Without loss of generality, we consider the distance between the original computation trees as the distance between the L-layer computation trees rooted at nodes and 22, denoted as A = A L .02" This allows us to recursively bound the distance. Given that all x are bounded by ||x||2 < Ex the distance between the node features Xe, and X,, satisfies ||x,, Xvz ll2 S 2Bx by the triangle inequality. Consequently, we can further develop the recursion as follows:
A s C,
X=1
X
+ +2d1-1
max AL-1
JEN(m)
< (Cx + C.Di).
(16)
1=1
where D; = ded1-1
Assuming that the number of branches (i.c., children) at each l-layer does not exceed the maximum number of branches in the tree, such that dj, ..., dp S d. We can further simplify the recursion by:
A < C1
Xo1
X
+ C2
viraa
L-1
jEN(2)
< (Bx + Σ CDDi)
1=1
C1 (Czd)
< 28x
(17)
1 Czd
25

---

D.2 Proof for Theorem 3.1
Before proving Theorem 3.1 it is necessary to first establish general version of the theorem, as detailed below:
Theorem D.2. Given set of instances ((x; y:)) sampled from the distribution P, and margin- aware prototype classifier f that predicts the class of instances via distance measure. The risk
R(()) can be bounded with probability
R() S RRJ+ 20-C C. p(p 1) 1)
vn
In(2/6)
(18)
p.
2n
where R(f) is the empirical risk, p denotes the number of tokens, C is constant, B is the bounded norm of x and P. and p acts as the margin, serving as penalty factor in evaluating the distance between computation trees and tokens.
Proof. Given a set of tokens (prototypes), margin-based classification involves using instances to identify the nearest tokens and assigning the labels of these nearest tokens the target instances. We denote the set of p tokens by {p:)een each with a norm bounded by B, and the labels associated with each token by {c) Given instance (xi, v:) sampled from a distribution P, the classifier can be defined as follows:
fxx = Cjj where j arg min [p, x112:
(19)
where x E IRd a random variable with a norm also bounded by B, consistent with the norms of the tokens.
In this proof, we focus on a binary classification problem with only two classes, (-1,1}. Conse- quently, the function can be represented as f Rd {-1,1}. Without loss of generality, this binary classification setting can be readily extended to multi-class scenarios using ane-versus-all or one-versus-on strategies [4]. We then define a class of functions as follows:
F
{f R" + 11).
(20)
We denote de, the distance to the nearest tokens with the same label yi = C+ and de_ as the distance to the closest tokens with the different label y: = c_. If de, is less than de_, the instance is correctly classified. Thus, the classification margin is defined as:
My y) == dd. de_.
(21)
where positive value indicates correct classification. Moreover, introduce penalty term to estimate the classification margin, defined as:
1
ff
(m(()=
1
1-
(22)
ift> > p.
where p > a pre-defined margin threshold.
For this classifier, the risk R(f) and the corresponding empirical risk R(f) is defined as:
R(f) = P(f(x) + u),
(23)
R(ʃ) == 1 n. Σ c(M(T())v))
(24)
We can establish a Gaussian complexity bound by applying Theorem 7 from [4] which holds with a probability of at least 8. This is expressed as:
2C G.(F))+ +
In(2) (n(2)))
R() < R() +
(25)
2n
26

---

where C represents the Lipschitz constant, and p represents the margin. This formulation allows us to explicitly incorporate the prediction margin into the complexity analysis. The term G denotes the Gaussian complexity defined over the function class F, and empirical Gaussian complexity can be estimated as:
2 Σ (nf((z))
(F) =
sup SEF n
(26)
where (01, 22, .... Fn) are independent standard Gaussian random variables, ~ (O, 1).
is important to note that the Gaussian complexity of the function class F can be bounded by aggregating the complexities of all its sub-classes (Theorem 16 from ( In our model, the token classifier leverages p tokens simultaneously; hence, it is logical define sub-classes of ,F that utilize only two tokens for predictions. We define each sub-class as Fij. which specifically uses tokens p: and Py with differing labels a + cj. Consequently, the total number of sub-classes is bounded by p (p- 1)/2. This allows us to simplify the complexity bound as follows:
2C p (p 1),
In(2/8)
R(f) S R(f)
(27)
2n
To further simplify the bound, we must derive it for each Gz. (F.). can be regarded as binary classification function class for d; dj. where the weights are bounded:
)) It is important to note that Fig
d2 dj = ||x 1 |xx 1
(||x|12 |p:12 2x 2x'p.) p.) (1|x | -2x" P,)
=2x" (p) - -p.) + ||p:11 ||,;1E
4B² + + =5B².
(28)
Based on Lemma 22 44. which establishes that the empirical Gaussian complexity bounded by a kernel function defined by Fij, we can simplify the empirical Gaussian complexity of each sub-class as follows:
G.((Fi) < B
vn
(29)
The difference between the Gaussian complexity and empirical Gaussian complexity is estimated to be e with probability of 2 exp( 22 (Theorem 11 from We can simplify the risk as follows:
8
20 C. p(p 1) B vn p. n
(2/288)
R()) < R()) +
(30)
2n
We can readily extend the Theorem D.2 to Theorem
3.1 in the main paper.
Proof. Theorem D.2 establishes bounds on the generalization error of margin-based classifiers using Gaussian complexity. Analogously, vector quantization functions as margin-based classifier by assigning instances to the nearest tokens in the vocabulary. Specifically, vector quantization utilizes this classifier for clustering, where each cluster center corresponds to a token. We assume each computation tree has a corresponding ground-truth cluster index based on the latent distribution, denoted as Pr, where (T.y) ~ Pr. Thus, the vector quantization process employed in the main paper converts to margin-based classification problem, consistent with Theorem [D.2] Moreover, we cancel the term B since the Cosine distance, used to measure the similarity between tree embeddings and tokens, ensures the bounded norm B 1.
E Detailed Analysis on Computation Tree Transferability
E.1 Synthetic Dataset
Experimental Setting. We randomly sample node features from uniform distribution with dimension of 4 and conduct experiments 100 times using different seeds to report average performance.
27

---

Transferabilig
10
Tree Sim.
Motif Sim.
1.0
Source
0.8
Source
0.8
Source
Graph 3
Graph
Graph
Graph
0.7
Graph
0.8
Graph
20
80
80
100
40
100
60
# Blocks
#
Blocks
# Blocks
Figure 11: Transfer performance on synthetic graphs with G2 the target graph.
Transferabily
10
Tree Si..
0.9
Motif Sim.
0.8
Source
0.8
Source
Graph
Graph
Graph
6
Graph 2
Graph
0.6
Graph
20
80
100
20
40
100
40
60
80
100
Blocks
Blocks
#
Blocks
Figure 12: Transfer performance on synthetic graphs with G3 as the target graph.
Since the synthetic datasets do not have labels for each node, we employ graph auto-encoder [39 for self-suue training. The encoder is a basic 2-layer GCN model with a dimension of 4, and the decoder uses standard inner product approach, computing the inner product between the embeddings of two nodes to determine their linkage. We set the number of training epochs at 200 and use Adam as the optimizer with a learning rate 1e-3 and a weight decay O. To evaluate transferability, we use the inverse of the Central Moment Discrepancy (CMD) [102], measure that serves as an indicator transferability, defined as transferabilityy CMD number of blocks in the source and target graphs is the same.
We ensure that the
To compute the computation tree similarity (Tree Sim.), employ the Weisteiler-Lehman subtree kernel [64], which evaluate similarity between two graphs by considering the subtrees patterns in terms of both structure and features. To match the capabilities of the 2-layer GNN encoder used, we limit the maximum iterations of the WL subtree kernel to two. Additionally, we mitigate the impact of randomness by randomly sampling node features from a uniform distribution and repeating the process 100 times. For evaluating the motif similarity (Motif Sim.), we utilize the graphlet sampling kernel 57 with sampled graphlet size as 5.
We present additional results analyzing transferability on synthetic graphs Figure [ and [2 We observe that higher computation tree similarity correlates with better transferability when using G2 and Ga as target graphs. However, the impact of motif similarity is marginal. We plan to analyze link-level and graph-level tasks in future work.
Additional Results.
E.2 Real-world Dataset
Experimental Setting. We conduct transfer learning to evaluate the correlation between transfer- ability and specific graph patterns on real-world graphs. Similar to synthetic datasets, we utilize the Weisfeiler-Lehman subtree kernel and the graphlet sampling kernel to compute tree similarity and motif similarity, respectively. We include homophily Airport graphs, consisting of USA, Europe, and Brazil [61], where each node represents an airport and edges denote flight connections. Nodes are labeled based on airport connectivity levels. Additionally, we also use heterophily graphs (56) that represent web links from universities such Cornell, Texas, and Wisconsin, where nodes web pages and edges are hyperlinks. The objective is to classify nodes into five categories: categories, student, project, course, staff, and faculty. In our analysis of real graphs, consider two settings: (1) use randomly sampled node features and (2) use raw node features. This approach will offer more comprehensive insights, node features also related to homophily and heterophily.
The experimental settings are detailed as follows. We evaluate the transfer learning performance using a basic 2-layer GCN model with ReLU activation, running the experiments 20 times to report the average results. We pre-train the model on the source graph with 60% of nodes randomly selected and subsequently fine-tune it on the target graph with 10% of nodes randomly selected. The hidden
28

---

dimension is set to 64, and we use the AdamW optimizer with weight decay of 1e-6. The pre- training learning rate is set 1e-3 for settings with 500 pre-train epochs, while the fine-tuning learning rate is set at le-2 for heterophily graphs and 5e-4 for homophily graphs. In the random feature setting, we sample node features from uniform distribution across 64 dimensions. For computing graph similarity with randomly sampled node features, we conduct the experiments 100 times using different seeds. The graphlet kernel samples motifss 10,000 times, and the maximum motif size is set to 5, The maximum iteration of the subtree WL kernll is limited to 2, aligning with the number of GNN layers.
Additional Results. See Table 9 for transfer learning performance graphs with random features. Even though the node features are randomly initialized, we still observe that a high tree similarity correlates with improved transferability.
Table 9: Transfer learning performance homophily (above) and heterophily (below) graphs with random features.
Starget
Brazil
Europe
USA
Geource
Europe
USA
Brazil
USA
Brazil
Europe
Motif Sim.
99.01
92.65
99.00 42.6 / 52.4
96.81
92.68
96.81
Acc. / Tree Sim.
/ 52.3
/ 59.2
45.1 76.2
45.4/ 58.9
46.1 76.1
Grarget
Cornell
Texas
Wisconsin
Guoucce
Texas
Wisconsin
Cornell
Wisconsin
Cornell
Texas
Motif Sim.
99.99 99.97
99.98
99.99
99.99
99.98
99.99
Acc. / Tree Sim.
33.4/ 47.2
51.4
40.9/47..
42.1/51.9
51.4 51.4
51.4
F
Experimental Setup
F.1 GNN Encoder
We employ GraphSAGE-like architecture to encode node and edge features in a graph 9 = (V, where node features are represented as X E IR Vixd, and edge features E E B xd. Considering a GNN with L layers, the (1 + 1)-th layer node embedding for node is given by:
H (1+1) =a w H + ReLU
Σ NEN(
w (H + (((...))) =B(B..)))
(31)
where H represents the node embedding the I-th layer, Eg, denotes the edge features between nodes u and v. and W1 and W₂ are the learnable matrices. The function y. used to align feature dimensions, is chosen the identity function, Id(-), in this study. While we utilize the basic GraphSAGE-like framework as the encoder, alternative, more advanced encoders such as graph attention networks 78 or other expressive GNNs [52 could potentially enhance model performance.
F.2
Dataset
Dataset Statistics. We utilize nine datasets from various domains and tasks, as detailed in Table We follow the preprocessing method described in (45. using the Sentence Transformer [60] to convert raw textual descriptions of nodes and edges into 768-dimensional features. should be noted that for knowledge graphs (KGs), we do not transform edge textual information into edge features, as the textual information already provides sufficient knowledge for KG completion.
10
Dataset Splitting. For Cora and PubMed, we follow the common split setting with 20 labeled nodes per class for training, utilizing a predefined 10 splits with different seeds to report average performance. For WikiCS, we also employ the standard split, reporting average accuracy across 20 different training splits, each with 20 random seeds, and using 5% of nodes in each class for training. For Arxiy, HIV, and PCBA, we follow the official splits, conducting experiments 10 times
29

---

Table 10: Dataset statistics 45
Dataset
Domain
Task
Graphs
Avg. #Nodes
Avg. #Edges
Classes
Cora PubMed
Citation
Node
2,708
10,556
7
Citation
Node
19,717
44,338
3
Arxiv
Citation
Node
1
169.343
1,166,243
40
WikiCS
Web link
Node
11,701
216,123
10
FB15K237
Knowledge
Link
14,541
310,116
237
WN18RR
Knowledge
Link
40,943
93,003
11
PCBA
Molecule
Graph
437,929
26.0
28.1
128
HIV
Molecule
Graph
41,127
25.5
27.5
2
ChEMBL
Molecule
Graph
365,065
25.9
55.9
1,048
with random seeds to determine average accuracy. For WNISRR and FB15K237, follow the splits outlined in Liu et al. 45. Specifically, for FB15K237, the training set comprises 272,1 15 edges, the validation set 17,535 edges, and the test 20,466 edges; for WN18RR, the numbers are 86,835, 3,034, and 3, 134,, respectively. We repeat each experiment 10 times with random seeds and report the average accuracy.
E33 Baseline
We compare GFT against a broad spectrum of basclines, encompassing supervised GNNs, self- supervised GNNs, graph few-shot learning, and graph foundation models.
Supervised GNNs/MLP. GAT [78), and GIN 94).
The supervised approaches include a basic MLP (Linear), GCN 40
Our analysis also covers self-supervised methods for graph learning. DGI [79 utilizes contrastive learning between graph summaries and node patches. BGRL (74) employs bootstrapping to predict the same node in different views. GraphMAE (26) reconstructs node features using structural information. GIANT [T] combines language models with graph neural networks in a self-supervised fashion, achieving state-of-the-art performance.
Self-supervised GNNs.
Graph Few-shot I Learning. GFT alongside methods such as GPN [15), TENT 83) GLITTER 82), and TLP (71). Experimental results are detailed in Appendix H
To assess performance in few-shot learning scenarios, we evaluate
include two primary baselines: Prodigy (30], which specializes in pre-training for in-context learning, although it is not applicable in standard pre-training and fine-tuning scenarios. For this model, we pre-train on MAG240M and evaluate performance on Arxiv, and on Wiki for FB FB15K237. OFA [45), in contrast, utilizes language models align the feature spaces of different graphs and introduces a prompt graph to align task spaces, trained supervised manner.
Graph Foundation Models.
F44 Hyper- parametr Setting
Baselines. For the baseline methods, follow the hyper- ppper--rreeterss reported 30 45 If specific hyper-parameters for a task are not reported, we set the learning rate to 5e-3 for Cora, PubMed, WikiCS, WNISRR, and HIV, and to le-4 for Arxiv, FB15K237, and PCBA. We configure all GNN encoders with two layers, hidden dimension of 768, and incorporate batch normalization and ReLU activation. AdamW is used as the optimizer with a weight decay of 1e-5, For methods that utilize attention mechanisms, we specify four attention heads.
Pre-training of GFT. We configure our model with two layers, each having a dimension of 768, and use ReLU activation complemented by batch normalization. In vector quantization, we set the number of tokens 128 with each token dimension 768. We empirically determine the weights for different losses 8 10, 32 100, B3 1. and 81 0.01. Additionally, set the weight for
30

---

the orthogomal regularizer, X, to I. Adam is utiliized as the optimizer with learning rate of le-4 and weight decay of le-5. The pre-training phase lasts for 25 epochs with batch size of 1024. For data augmentation, we implement an edge drop rate and node feature drop rate, both set at 0.2. For topology reconstruction, we selectively reconstruct 10% of links and choose an equivalent number of negative samples. The sampling factor for semantic reconstruction is fixed at 1.
Fine-tuning of GFT. We detail the hyper-parametern for different datasets Table Aproto and Xtin represent the weights of the losses for the prototype classifier and the linear classifier, respectively.
Table 11: Hyper-paramelers in fine-tuning.
Hyper- parameters
Cora
Pubłee
Arxiv
Wikics
WN18RR
FB15K237
HIV
PCBA
Learning Rate
5e-4
5c-3
5e-4
lc-4
1c-3
5c-4
3c-4
lc-3
Epochs
1,000
1,000
1,000
2.000
1,000
3,000
100
50
Early Stop
200
200
200
500
200
200
20
10
Batch Size
0
0
0
0
1,024
1,024
1,024
Instances per Class in
n/a
n/a
n/a
n/a
50
1,500
in fproto
used for all datasets
in Jiin
used for all datasets
Aproto
1
0.1
1
0.1
0.1
0.1
Aiin
0.1
1
0.1
1
0.1
1
1
F.5 Running environment
We utilize NVIDIA A40 with 48GB GPU memory for all experiments. Both the pre-training and fine-tuning phases can be conducted on single Nvidia GeForce RTX 3090 with 24GB memory.
G Pre-training and Fine-tuning Results with std.
We report the average results of the pre-training and fine-tuning settings the main paper. The model results along with the standard deviations presented in Table 12
Table 12: Model performance in pre-training and fine-tuning setting with std.
Node Classification
Link Classification
Graph Classification
Method
Cora
Publed
Wiki-CS
Arxiv
WV18RR
FB15K237
HIV
PCBA
Avg.
Linear
58.03 2233
68
2124
70.36 sus
66.50 2014
78.50 2039
87.39 amm
66.37 a.
72.30 2034
71.01
GCN 40
75.65
75.28 31
73.79
82.22
71.32
GAT
78
76.24
74.86
76.78
70.87
80.16
88 93.99.mm
65.54
70.12
75.44
GIN
94
73.59 22.0
69.51 aaa
49.77 4412
65.05 2030
74.02 anss
83.21 2033
66.86 :::
72.69 20:2
69.34
DGI
79
72.10 4434
73.13 a0m
75.32 aaos
69.15 w030
75.75 aade
81.34 ac.r
59.62 a111
63.31 aaa
71.22
BGRL
71.20
75.29
76.53 an.9
71.19
75.44
80.66
63.95 21:6
67.09
72.67
GraphMAB 26
73.10 29.40
74.32
77.61 s0.99
70.90 s0:1
78. 99
85.30 st.16
61.04 205
63.30
73.07
GIANT
75.13 w0.6
72.31 J085
76.56 en.s
70.10 40
84.36 -038
87.45 a0
65.44 41734
61.49 -oww
74.11
GFT
78.62 a1:3
77.19 1139
79.39 an:42
71.93 a8.2
91.91 aa3a
89.72 amm
72.67 1.33
77.90 4864
79.92
H Additional Few-shot Learning Results
16 17 18 and 19 each run, we sample 20 few-shot tasks to mitigate the impact of randomness. The baselines consist of graph foundation models such as Prodigy 30 and OFA (45 alongside few-shot
We present the extended few-shot learning performance across multiple tables: Table 13
L4 15
learning methods including GPN 15 TENT 83, GLITTER 82], and TLP 771. terms of graph foundation models, we compare GFT to OFA across all datasets and to Prodigy on the Arxiv and 15K337 datasets only, as Prodigy's application is limited these datasets by its in-context training strategy. GFT not only significantly enhances performance over Prodigy and OFA but also surpasses a broad range of specialized few-shot learning methods. Furthermore, as the number of fine-tuning instances per class increases, there is marked improvement in model performance, demonstrating
31

---

significant udaptability to target tasks. Notably, even with extremely limited training instances, the model substantially outperforms the baselines, showeasing rapid adaptation capabilities.
Table 13: The few-shot learning performance on Arxiv (Part 1). We use the bold to indicate the performance of best baselines and best our methods. The term "# trains" indicates the number of fine-tuning instances per class.
5-way
3-way
Method
5-shnt
3-shot
I-shot
5-shot
3-shot
I-shot
GPN
15
50,53 ere
48.32 soa
38.58 sta
62.25 2454
58.52 1o
48.45 ex:)
TENT 83
60.83
56.03
45.62
74,20 2357
70.48 21:31
59.38
GLITTER 82
56,00 .44:
57.44 wom
47.12 amm
62.13 amas
60.93 212
59.20 4541
TIP-BBGRI.
7
50.13
46.21
35.81
62.93
58.37
46.30
TLP-SURGL
71
77.89 sxds
74.19 snas
61.75 soee
86.27 24
83.75 shas
73.46 st1/e
Prodigy (30
61,09 a.3
58.64 assa
48.23 sAis
73.64 41:3
71.43 at:s
61.59 4533
OFA 45
59.92
58.68
$2.80
72.18 #333
71.80 .1.50
60.47
GFT (# train = 5)
68.00 4:33
66.00 22:5
58,20 4415
78.56 4412
74.00 a2.10
66.22 6432
GFT (#
10)
71.73
62.40
78.78
76.22 +1:11
69.89
GFT (# main = 20)
73.13
71.67 mas
64.20 2017
80.67 +2:34
79.33 s0.34
72.89 #1cl
GFT (# train 30)
74.67 2258
73.27 25.8
65.13 1576
79.56 2137
76.78 22
73.22 2548
Table 14: The few-shot learning performance on Arxiv (Part 2).
40-way
20-way
10-way
Method
5-shot
3-shot
I-shot
5-shot
3-shot
I-shot
5-shot
3-shot
I-shot
Prodigy 30
25.51 2014
23.69 sun
21.44 s.22
34,29 .243
31.30 ao
29.21 aur
50.84 1.7
47,39 22
41.05 20.00
OFA
22.13 aur
21.34 41.30
36.33 a.
32.56
29.40 a121
49.59 2237
48.11 aa
39.53 4020
GFT (# train 5)
36.29
34.36
26.49 41:1
45.75
42.58
35.02
56.43 2545
52.43 2::3
44.40 11:0
GFT (# train = 10)
41.83 Joss
39.10 atar
30.82 aa.e
49.65 1s
46.85 4146
40.95 am7s
60.20 a112
57.57 2:
48.07 42.0
GFT train
45.07
43.90
35.02
53.25
50.85
42.97
63,47
61.37
53.25
GFT (# train 30)
46.68 sun
44.60 s1/
35.88 s1.24
53.97 :0:41
51.85 st.7
43.75 star
64.43 st.2
62.77 203
54.73 s158
Table 15: The few-shot learning performance on Cora.
7-way
5-way
2-way
Method
5-shot
3-shot
1-shot
5-shot
3-shot
1-shot
S-shot
3-shot
1-shot
GPN [5]
63,83 22:6
56.09 2i3e
TENT 83
58.97 12:0
54.33 a2.10
TLP
71
81,31
59.16 42:8
ILP-SURGL
92.49 41:2
81.52 2230
32.10 .17
36.03 4:11
30.38 .239
42,28 .235
31,28
72.20 -1:5
62.22 .13
$1.85 +1.3
GFT (4 train = 1)
43.55
43.31
41.40 4004
$2.30
51.47
49.80
75.00
76.33 335
72.92
GFT (# train 2)
56.48 .151
55.90 sive
53.64 4:50
63.67 -141
62.40 -116
60.47 +1st
82.25 -1a1
81.67 -1
78.00 -6.09
GFT train 5)
67.36
67.29
66.
74.10
74.37
72.70
87.00
86.00
86.00
GFT (# train 10)
74.02 2358
74.26 45770
72.55 13.9
78.53 2112
78.90
76.87
12
87.92
22:99
88.50
22:38
88.42 1100
Table 16: The few-shot learning performance on FB15K237.
40
10 way
5-way
Method
5 shot
3-shot
I-shot
5ishol
shot
1 1-shot
5 shot
3-shol
shot
Prodigy 30
62.03 -e-s
59.58 wi
54,30 wi
84.30 -.aa
79.61 4..4
66.10
88.05 -oss
88.02 a
87. 59 -084
OFA
66.51 20.11
65.76 mose
63.48 s0
83.64 20:3
83.14 21:4
83,46 2413
91.43 20ss
91.12 2839
91.01 200e
GFT
61.48 4132
60.79 41.41
78.83 11
79.13
86.27 a1.00
86.00
87.67
GFT (# train = 20)
70,36 2013
70.56 2:12
70.19 21.45
85.40 12
85.57 1125
85 85.93 11:2
91.80 2::77
91.80 2112
91.80 11:24
GFT
30)
75.01
74.56 aus
74.97 am
89.13 1135
88.53
88.07
91.93 1134
92.27 4130
92.40 4122
I Complete Ablation Study
L.1 Pre-training Datasets
The complete results detailing the impact of different pre-training datasets are presented in Table
20 which serves as complement to Table 5
We explore three variants: (1) pre-training all
32

---

Table 17: The few-shot learning performance on WN18RR.
10-way
5-way
3-way
Method
S-shot
3-shot
I-sbot
S-shot
3-shot
I-shot
5-shot
3-shot
1-shot
OFA
32.64
30.56 aua
25.82 aur
48.32
45.04
34.40
60.72
61.29 22.
51.77
GFT (# train 1)
35.50
35.50 ase
35,33 4420
48.80
48.53
48.13
62.56
60.67 1353
58.44 4234
GFT (# train 2)
42.43 a3m
42.50 aass
42.00 w0.0
55.87 2263
$4.80 a21
54.40 a22z
66.33 ..:1
66.44 a
64.89 a1:2
GFT train 5)
44.83
44.90
44.77
58.00
57.73
57,40
68.89
69.67
68.78
GFT (# train 10)
$1.20 2457
$1.30 1434
50.87 2415
62.67 2490
63.00 2520
63.60 sk.s
72.22 207
72.56 2439
72.56 2475
Table 18: The few-shot learning performance on HIV.
2-way
Method
10-shot
5-shot
3-shot
I-shot
OFA [45]
54.36 sase
57.56 22ue
59.30 22.4
57.17 aL92
GFT (# train 10)
53.22 a117v
54.17 amss
57.61 amas
58.28 20.1
GFT (# train 20)
58.67 a1s
58.78 1432
58.44 4725
59.94 4:.0
GFT (# train
58.11
58.56
58.33
59.11 2535
Table 19: The few-shot learning performance on PCBA.
2-way
Method
10-shot
5-shot
3-shot
1-shot
OFA 45
54.58 22.90
54,80 2375
54.67 2435
54.92 24.35
GFT (il train = 10)
55.98 sl.39
56.13 1133
56.29
$6.39 21.4
GFT (# train = 20)
59.34 44.9
59.34 14777
55.72 .542
$5.88 11
GFT (# train 30)
54.81 4m
55.14 mm
58.18 -211
55.33 +1.00
datasets, (2) pre- pre-training solely on the target dataset, and (3) pre pre-training on the remaining datasets. Our observations suggest that using only the target graph can still achieve desirable performance, it provides graph-specific information without spurious noise. More importantly, performance improves significantly when the target graph is excluded and the remaining datasets are utilized. We hypothesize that observing more computation trees generally enhances model performance. Even without the target graph, the presence of numerous computation trees shared across various domains provides sufficient information. Moreover, using all datasets typically yields the best performance, as it offers a more comprehensive approximation of the computation tree distribution.
Table 20: Complete results of the ablation study on pre-training datasets.
Node Classification
Link Classification
Graph Classification
Variant
Cora
Publed
Wiki-Cs
Arxiv
MB18ER
FB15X237
HIV
PCBA
Arg.
All Datasets
78.62 :1.11
77.19 aw
79.39 sa.
71.93 1012
91.91 20
89.72 2a:
72.67 1138
77.90 ausa
79.92
Target Dataset
78.05 2144
76.22 aum
78.67 a2
71.54 a030
91.67 aas
89.67 am
71.05 mM
77.10 aus
79.25
Remaining Datasets
77.60
75.73 ama
78.94
71.47 am
91.72 a018
89.70
72.28
77.44
79.36
I.2 Pre-training Tasks
Table 21 presents complete results of model performance across different pre-training tasks, serving as complement to Table The observations align fully with those in Table demonstrating that all reconstruction tasks enhance model performance compared models without pre-training. Optimal performance is achieved when three tasks are jointly optimized.
I.3 Strategies for Enhancing Tree Vocabulary
Table 22 presents the ablation study on strategies for enhancing the quality of tree vocabulary, as described Section 3.T As previously stated, both the comprehension and expressiveness of the tree vocabulary are critical properties for its effecctiveness, achieved through augmentation (aug.) and an
33

---

Table 21: Complete results of the ablation study on pre-training tasks.
Node Classification
Link Classification
Graph Classification
Variant
Cora
PubNed
Wiki-Ca
Arxiv
WN18RA
FB15K237
HIV
PCBA
Avg.
n/a
77.89 2204
76.11 21.7
70.98 2415
65.11 21.41
91.13 30
3,46 2215
71.67 22.11
75.99 20.5
66.54
w. Luem
78.20 2172
75.96 2la
79.16 a0si
71.68 20
91.47 s0
89.31 a0:
72.63 21.1
77.35 201o
79.47
reat
77.10
75.85
79.29
71.16
91.44
89.39
71.55
77.29
79.13
Lupu
76.42
75.82
77.95
71.81
91.08
89.48
72.02
77.11
78.96
All Tasks
78.62
77.19 2139
79.39 a0az
71.93 w0a1
91.91 19.34
89.72 J0.33
72.67
77.90 2044
79.92
orthogonal regularizer (ortho. reg.), respectively. We note that removing any component results in degradation in model performance.
Table 22: Complete results of the ablation study on strategies for enhancing tree vocabulary.
Node Classification
Link Classification
Graph Clussificution
Variant
Cora
PubNed
Wiki-CS
Arxiv
WV18RR
FB15K237
HIV
PCBA
Avg.
All Components
78.62 auM
77.19
79.39 a04
71.93 sun
91.91
89.72 201
72.67 11:3
77.90
79.92
w/o Aug.
77.44 a12s
76.00 4:30
78.76 am
71.50
91.11
89.07 w02:
71.54 2..0
77.50 acis
79.12 79.15
w/o Ortho. Reg.
77.64 a13
76.94 22ι1
78.81 a0ds
71.44 2043
91.23 2343
89.29 2012
70.84 1231
77.04 2031
1.4 Fine-tuning Tasks
We analyze the impact of different computation tree classification tasks for fine-tuning. The complete results are presented in Table 23] which complements Table Specifically, GFT employs both linear classifier and a prototype classifier to utilize information from various levels of the tree. The prototype classifier excels in node-level tasks, while the linear classifier performs better in the other two tasks. However, combining these two methods yields the best performance.
Table 23: Complete results of the ablation study on fine-tuning tasks.
Node Classification
Link Classification
Graph Classification
Variant
Cora
PubNed
Wiki-CS
Arxiv
WN1BRA
FB15K237
HIV
PCBA
Arg.
w. foroto
78.53 simi
77.13 +1.
79.36 aosi
71.53 a011
76.76 41
0.65 mm
56.21 4M
63.56 -ins
62.97 78.06
w. Juin
76.52 23.00
76.82 2195
78.35 s187
70.36 2057
90.05 1234
87.93 =1.50
69.06 24.8
75.36 :2:5
All Tasks
78.62 41.21
77.19 1130
79.39 40.12
71.93 4012
91.91 40.34
89.72 40.2
72.67 41.35
77.90 .04s
79.92
Table 24: Complete results of the ablation study on tree vocabulary.
Node Clussificution
Link Classification Graph Classification
Variant
Cora
PubMed
Wiki CS
Arxiv
WX1
FB15K237
HIV
PCBA
Avg.
Tokens 128
78.66
77.19
79.39
71.93
91.91
89,72 s030
72.67
77.90
79.92
# Tokens 256
78.
4185
77.26 4um
79.31 4ote
72.02 w023
91.90 a0
89.82 mm
72.22 -150
78.11 wa.s
79.86
Tokens 512
78.86 am
77.17 a120
79.54 as
72.19 wa2e
91.75 aver
89.96 wa1
72.36 aama
78.06 w13
79,99
wfo. Vocab. 78.27 213:
76.43 2230
78.06 20.25
70.82 20.s
81.52 2013
91.87 anas
56.12 2314
82.21 2013
76.91
1.5
Tree Vocabulary
Table 24 presents a detailed analysis of model performance with different numbers of tokens and without utilizing the tree vocabulary, complementing Table 6 Although increasing the number of codes can enhance performance to a certain extent, it is not necessarily effective all scenarios. Specifically, in only four out of eight scenarios, the maximum number of codes (512 tokens) yields the best results. This observation is consistent with our theoretical analysis, suggesting that more codes may increase the upper bound of generalization error, potentially due to overfitting risks. Furthermore, this phenomenon might also be attributed to the limited diversity of datasets; the eight utilized datasets originate from only four domains (citation, web link, knowledge graphs, and molecules). For these
34

---

domains, smaller number of codes may suffice. We hypothesize expanding the number of domains might necessitate more codes; we intend to explore in future work. Regarding the variant that does not use vocabulary, we bypass vocabulary training during pre-training, and directly append linear classifier behind the GNN for classification during fine-tuning. The results indicate that using the vocabulary significantly enhances model performance, particularly in link- and graph-level tasks, aligning with our theoretical considerations regarding the generalizability of tree tokens.
35

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
We clearly introduce the contribution of the paper in the abstract and introduc-
tion.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: See Section 5
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
36

---

Justification:
We provide proofs for each theorem in the paper and clearly present the assumptions. We also discuss how such assumptions can be satisfied. See Appendix
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We provide the code in the supplementary and also comprehensively discuss the experimental setup in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, it may be necessary either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how reproduce that algorithm. (b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
37

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes)
Justification:
We provide the anonymized code in the supplementary.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/ "pipsscc/puullc//uuu /ttee//guuddeeeeeSouuuuumbbbba ssionPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
See Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We present the error bar the Appendix G and
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
38

---

The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative emrr rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We provide the clear experimental setting in Appendix
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics
Answer: [Yes]
Justification:
We carefully read and follow the code of ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification:
See Section 5
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
39

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: Our work poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We clearly cite the papers if we follow their settings.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
40

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
It does not available for our work.
Guidelines:
The answer NA means that the paper does not release new assets,
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: does not available for our work.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: does not available for our work.
Guidelines:
The answer NA means that the paper does involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
41


Reviews:
[{"review_id": "kIm1DJPmVe", "reviewer": "Reviewer_H6gM", "summary": "The paper proposes a new graph foundation model based on the tree structure, which is called GFT. GFT leverages computation trees to define tokens within the transferable vocabulary, which improves model generalization and reduce the risk of negative transfers.  Comprehensive experiments and theoretical analyses are provided to demonstrate the effectiveness of GFT across diverse tasks and domains in graph learning. Overall, this is a good work with good motivation, a novel method with theoretical support, comprehensive experiments, and good writing.", "questions": "Please see the weaknesses.", "limitations": "None.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "+ The paper is well motivated by the fact that current graph learning models lack identification of a vocabulary that can encode transferable patterns shared among different tasks and domains. Filling the gap is challenging and meaningful. \n \n+ The proposed GFT model is novel. Unlike existing models, it introduces computation tree as transferable patterns and encodes general knowledge of graph into a tree vocabulary, which is new. It aims to improve the model generalization and reduce the risk of negative transfers.  The theoretical analyses are also provided to support the design of GFT model, which is solid. \n\n+ Extensive experiments over different graph learning tasks (e.g., node classification, link prediction, graph classification) are conducted across many datasets. The model outperforms SOTA baseline methods. As a graph foundation model, it is good to see experiments over cross-domain and cross-task datasets. Many more analytical experiments (including Appendix) are also provided, which is impressive. \n\n+ The paper presentation is good. The organization is clear and easy to follow.", "weaknesses": "-  The proposed model assumes tree structure as transferable patterns. Besides the examples (i.e., basic blocks in Fig. 2) shown in the paper, is there any other structures transferable? It is not clear whether these patterns are transferred during the model training or not. How to demonstrate this?\n-  As a graph foundation model, besides general and few-shot tasks, it would be better to see experiments on zero-shot task.  Can the proposed model be applied to this scenario and what is performance compared to baseline methods?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer H6gM, \n\nWe greatly appreciate your acknowledge of our contribution and insightful feedback to help us refine our work. We address your concerns as follows:\n\n> W1: Is there any other structures transferable? How to demonstrate what tokens learn exactly?\n> \n\nYes, there are other transferable structures. While we did not provide additional visualized examples due to the inherent complexity of graphs, we utilized the Weisfeiler-Lehman (WL) subtree kernel to directly measure the presence of such transferable structures across two graphs. Our experimental results (Figure 3 and Table 1) demonstrate a positive correlation between transferability and the WL subtree kernel value.\n\nAdditionally, each token in the vocabulary represents the embedding of certain transferable structures. To elucidate the potential meaning of these tokens, we propose measuring the density of token usage across different datasets. This approach is illustrated in ****Figure 1 of the attached PDF**** in the general response. In this figure, we observe a set of tokens used by all datasets, suggesting they capture general and transferable structures across graphs. Furthermore, some tokens are shared within specific domains or datasets, indicating they maintain domain-specific patterns. It is important to note that our visualization represents an initial step towards understanding the transferable patterns on graphs. Your review has inspired us to further explore this direction in our future work.\n\n> W2: Zero-shot learning setting\n> \n\nWe appreciate your suggestion for a comparison of zero-shot learning. Recognizing the importance of zero-shot scenarios for graph foundation models, we have implemented a zero-shot version of our model, GFT. Following current promising approaches [2-4], we use an additional LLM as the task reasoner, utilizing the learned embedding and specific prompts as input. Specifically, we follow the design in [4], using an MLP projector to map the learned embedding and fine-tuning the LLMs with LoRA.\n\nWe compare GFT with four baselines that also use LLM reasoners. Models such as GraphGPT [2] and LLAGA [3] focus on single tasks, converting node features and graph substructures for LLM processing. OFA [1] treats subgraphs as transferable patterns and applies graph prompt learning for zero-shot learning, although its performance is limited. Therefore, we implemented an LLM-based OFA (OFA + LLM) similar to our method (GFT + LLM). The results are presented below, with “*” indicating a slightly different experimental setting, such as different pre-training datasets. \n\n|  | Cora | Arxiv | WN18RR |\n| --- | --- | --- | --- |\n| GraphGPT | 18.13* | 64.76* | - |\n| LLAGA | 34.69* | - | - |\n| OFA | 19.31 | 46.19 | 19.98 |\n| OFA + LLM | 30.56 | 64.32 | 27.41 |\n| GFT + LLM | 34.66 | 67.80 | 30.30 |\n\nThe advantage of the baseline methods (GraphGPT, LLAGA) is primarily due to their pre-training on a single dataset (or datasets from the same domain), allowing them to learn domain-related patterns for downstream tasks. In contrast, OFA and our GFT are pre-trained on cross-domain and cross-task graphs, acting as general reasoners over graphs. Specifically, the basic OFA’s performance is relatively lower without directly leveraging the power of LLMs in reasoning. However, when using LLMs as reasoners, OFA’s performance significantly improves, though it remains lower than our GFT. This indicates the potential of using computation trees as transferable patterns in learning generalized embeddings.\n\nBest regards,\n\nThe authors\n\n---\n\nReferences: \n\n[1] Liu, et al., One For All: Towards Training One Graph Model for All Classification Tasks, ICLR, 2024. \n\n[2] Tang, et al., GraphGPT: Graph Instruction Tuning for Large Language Models, SIGIR, 2024. \n\n[3] Chen, et al., LLaGA: Large Language and Graph Assistant, ICML, 2024. \n\n[4] He, et al.,UniGraph: Learning a Cross-Domain Graph Foundation Model From Natural Language, Arxiv, 2024.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "OiWaKsLTDO", "reviewer": "Reviewer_U8xo", "summary": "This paper proposed a novel computation tree method to improve the transferability between the pre-train model and downstream tasks. This paper rethinks the transferable pattern in graphs as computation trees and validate their transferability both empirically and theoretically. The proposed GFT leverages computation tree reconstruction to acquire general graph knowledge from cross-domain datasets and uses computation tree classification to facilitate adaptation to various target tasks Comparing with other previous methods, the proposed GFT can improve model generalization and reduce the risk of negative transfer, which is suitable for the cross-domain and cross-task situation.", "questions": "1. In Appendix C.5, the paper argues that the subgraph method incurs additional time and memory costs. Why can the proposed computation tree avoid these problems? \n\n2. The Lfeat is to minimize the discrepancy between the local structure of a node and its feature. Why do you use Lfeat and is there any intrinsic connections between the local structure of a node and its feature? \n\n3. For Ltree, what are decoders used for q projection? \n\n4. In a graph, if node va and vb are isomorphic while the links (va, vc) and (vb, vc) are not isomorphic, the vanilla GNN with the same node representations va and vb gives the same prediction to links (va, vc) and (vb, vc). How does GFT address this issue in link prediction? \n\n5. What is the definition of R(f)? \n\n6. From the experimental results, GFT outperforms other methods. Is this due to the computation tree or the more comprehensive loss function? Would the overall performance be worse if the computation trees were replaced with subgraphs? 7. Is it possible for GFT to be applicable in zero-shot scenarios?", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "a. Originality: The computation tree has been proposed in several previous works that have been adequately cited in this paper. The author reconstructs the computation tree in a new way and combines it with Vector Quantization method, effective and preventing over-fitting. b. Quality: The paper is technically sound, and the loss function proposed is comprehensive, enabling a deep understanding of the structural and semantical attribute of computation trees. The experiments in the manuscript are very comprehensive and effectively demonstrate the superiority of GFT, and important claims are well supported by theoretical analysis. c. Clarity: The manuscript is well organized and clearly written, although some descriptions could be clearer. d. Significance: The experimental results advance the SOTA methods, and the computation tree method proposed is easy for other researchers to use.", "weaknesses": "It is not very clear how this work differs from previous contributions. The explanation of the superiority of computation trees over subgraphs is unconvincing because the computation tree in this paper is very different from some proposed computation trees (e.g. junction tree, H-tree, etc.) but more like the subgraph. It would be better if the author could provide detailed comparison and analysis between the computation tree and the subgraph; The quality is a bit limited. The Lfeat is to minimize the discrepancy between the local structure of a node and its feature, but is there any inherent relationship between the two? Besides, the method might not be able to deal with link prediction in a good manner. In a graph, if node va and vb are isomorphic while the links (va, vc) and (vb, vc) are not isomorphic, the vanilla GNN with the same node representations va and vb gives the same prediction to links (va, vc) and (vb, vc), but GFT does not address this issue; The clarity should be improved. The explanation for Ltree should be detailed. For example, what are decoders used for q projection? In line 269, the definition of R(f) is not given; The significance of the paper is slightly limited. It might be difficult to extend the GFT to zero-shot scenarios because the fine-tune process is necessary for GFT but it will be excluded in zero-shot scenarios.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Dear Reviewer U8xo, \n\nWe appreciate the reviewer’s recognition of originality, quality, clarity, and significance of our work, and thank the reviewer for detailed feedback. We address your concerns as follows.\n\n> W1: Differences between computation trees and subgraphs.\n\nPlease refer to the [W1] in the general response. \n\n> W2: How $L_{feat}$ works?\n\n$L_{feat}$ uses localized information to predict the original node features via a linear predictor. This can potentially model the positive or negative correlations between neighborhoods and the target node, corresponding to homophily and heterophily, respectively. Let $z$ be the learned embedding and $x$ be the raw features. If the neighborhood information is similar to the target node (homophily), the predictor might learn a nearly identical function since $z$ might be similar to $x$ . However, under heterophily, where $z$ and $x$ are far from each other, the linear predictor might learn a distinct mapping function to model such correlation. Empirically, [1] proposes a pre-training task similar to $L_{feat}$ and achieves desirable performance on node classification and graph classification. To elucidate this further, we provide a thorough ablation analysis to validate the effectiveness of $L_{feat}$ in our GFT:\n\n||Arxiv (Citation)|WN18RR (KG)|HIV (Molecule)|\n|---|:---:|:---:|:---:|\n|No Pretrain|65.11|91.13|71.67|\n|Only $L_{feat}$|71.16|91.44|71.55|\n|w.o. $L_{feat}$|70.41|91.33|72.04|\n|All Tasks|71.93|91.91|72.67|\n\nThe $L_{feat}$ is effective in node-level tasks (Arxiv) where papers tend to cite related papers, following the homophily principle. It also benefits link-level tasks (KG reasoning), where two entities sharing similar types of relationships may be connected. However, for graph-level tasks that may require a global understanding of patterns and motifs, $L_{feat}$ may be less important. Despite this, removing $L_{feat}$ still degrades model performance. These experiments emphasize the benefit of modeling the correlations between the local structures of a node and its features.\n\n> W3: What are decoders used for q projection?\n\nThe q projection is implemented by a basic fully-connected layer. We apologize for any confusion and sincerely thank you for identifying this issue. We will refine the paper to provide better clarification.\n\n> W4: How to handle the case that nodes are isomorphic but edges are not isomorphic.\n\nWe greatly appreciate this insightful feedback. Similar to previous GFMs with basic GNN encoders [2, 3], our GFT cannot enhance model expressiveness to handle such link-level isomorphism. However, this limitation arises primarily due to the limited expressiveness of the backbone model (GraphSAGE) rather than our model design, and thus **does not significantly impair the contribution of the overall framework**. We can address this issue by using more expressive GNN backbones as described in [4]. Moreover, such conditions may not always occur in real-world applications with rich node attributes, where two nodes are less likely to have the same embeddings, thereby preventing node isomorphism.\n\n> W5: What is the definition of R(f)?\n\nThe definition of R(f) is related to the VQ operation. Specifically, VQ clusters the input vectors by measuring the distance between the input vectors and token vectors in the vocabulary, where the process can be interpreted as a margin-aware prototype classifier $f$ [7]. The classifier $f$ aims to classify the inputs into their latent clusters $y$ , and the predictions are denoted as $\\hat{y}$. Based on that, R(f) measures the risk of the classifier $f$. Note that this analysis is based on the extension of the latent variable assumption, a general assumption in statistics and machine learning that variables are sampled from a latent distribution, where each input is assigned a label indicating its latent cluster.\n\n> W6: What’s the impact of the comprehensive loss functions? What will happen if computation trees are replaced by subgraphs?\n\nGFT surpasses baselines even with a single loss function, and replacing computation trees with subgraphs impairs model performance. We select two basic baselines, including GAT and GraphMAE, and implement a subgraph version of GFT (GFT - Subgraph) following [6]. We further extend our comprehensive objective to the subgraph version (GFT - Subgraph + Our Task) as another baseline. The results are as follows:\n\n|  | Node | Link | Graph | Avg. |\n|---|:---:|:---:|:---:|:---:|\n| *Model Performance with linear classifier* ||||| \n|GAT|74.69|84.55|67.83|75.44|\n|GraphMAE|73.98|82.15|62.17|73.07|\n|GFT - Subgraph|73.61|85.73|64.67|74.41|\n|GFT - Subgraph + Our Task|74.23|86.49|67.89|76.13|\n|GFT|**75.51**|**88.99**|**72.21**|**78.06**|\n| *Impact of Loss Objectives* |||||\n|Only $L_{sem}$|76.25|90.39|74.99|79.47|\n|Only $L_{feat}$|75.85|90.42|74.42|79.13|\n|Only $L_{topo}$|75.50|90.28|74.57|78.96|\n|GFT (All Tasks)|**76.78**|**90.82**|**75.29**|**79.92**|\n\nThe results demonstrates the benefit of using computation trees even without a comprehensive loss function, referring to *Impact of Loss Functions*. When the computation trees are replaced by subgraphs, the model performance degrades even with our comprehensive tasks, further supporting the advantage of using computation trees as basic patterns.\n\n> W7: Zero-shot learning.\n> \n\nPlease refer to [W2] in the general response. \n\nBest regards,\n\nThe authors\n\n---\n\nReference:\n\n[1] Hou, et al., GraphMAE: Self-Supervised Masked Graph Autoencoders, KDD, 2022. \n\n[2] Liu, et al., One For All: Towards Training One Graph Model for All Classification Tasks, ICLR, 2024. \n\n[3] Huang, et al., PRODIGY: Enabling In-context Learning Over Graphs, NeurIPS, 2023.\n\n[4] Mao, et al., Graph Foundation Models are Already Here, ICML, 2024. \n\n[5] Crammer, et al., Margin analysis of the LVQ algorithm, NeurIPS, 2002. \n\n[6] Sun, et al., All in One: Multi-Task Prompting for Graph Neural Networks, KDD 2023.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "13IwCMgUG5", "reviewer": "Reviewer_M9ZQ", "summary": "This paper explores the concept of the transferable token in graph foundation models. Specifically, the paper proposes to use the computation tree as the transferable token for graph learning and prove its efficiency from both theoretical and empirical perspectives. Then, the paper proposes GFT model, GFT first pretrain a graph tokenizer using vector quantization to tokenize text-attributed graphs across different domains through a computation tree. Next, it is fine-tuned on downstream tasks. The model shows great results on generalization ability, especially on few-shot and zero-shot experiments.", "questions": "1. I am curious about Table 23. Since the graph tokenizer needs to tokenize both structural and textual information. The token size should be much larger than 512 even within a single domain from my sense given the abundance of both the graph structure and textural information. Could authors explain more about it? Have authors explore what are these tokens learned exactly?\n\n2. The approach in this paper is somewhat similar to the VQGraph [1]. It is worth discussing the relation and difference between the two methods.\n\n3. The author claims the proposed method does not need to extract subgraphs. I am wondering how is the method deal with the case like the graph is too large to fit into one GPU? \n\n\n[1] Yang et al., VQGRAPH: RETHINKING GRAPH REPRESENTATION SPACE FOR BRIDGING GNNS AND MLPS, ICLR 2024.", "limitations": "There are no major limitations from my perspective. I encourage the authors to further explore the proposed methods, like using more expressive GNNs or pre-train on large-scale datasets, as discussed in the limitation section.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "1. Investigating transferable tokens in graph learning is important and fundamental to the community. This paper is the first one that demonstrates the potential existence of the transferable token in text-attributed graphs. \n2. The paper is well-structured with solid theoretical and experimental results to demonstrate the advantages of the proposed model.", "weaknesses": "1. In Theorem 2.2, the distance bound is associated with the distance between the $j$-th neighbor of node $v_1$ and $v_2$. How to define the $j$-th neighbor related to two nodes? What if the two nodes have different numbers of neighbors?\n2. In Theorem 2.2, the distance bound is related to the distance of the feature between two nodes (as well as the distance between node neighbors, as it is defined recursively). However, in the real world, the distance of the feature itself can be unbounded, which makes Theorem 2.2 only applicable when features are close and less useful in real scenarios (Even in text-attributed graphs, sentence embedding from different domains can still be too diverse). \n3. For Section 3.1, I am not sure if I understand it wrongly or if I missed something. There are a few parts I think it is not true. For Equation 2, should loss compute between $z_i$ and $c_i$, instead of $q_i$? Otherwise, it does not make sense to me. Meanwhile, what is the $\\delta_j$, I cannot find its definition in the paper. Please correct me if I am wrong.\n\n4. Although the authors did extensive ablation studies, there is one I am particularly interested in about cannot find in the paper. How well can be model be if the pretraining datasets are totally from different domains of the downstream tasks? For example, what is the performance if the model is pre-trained on molecular datasets but tested on citation networks or vice versa?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate Reviewer M9ZQ for the insightful feedback and are deeply inspired by your recognition of our contribution as “the first to demonstrate the potential existence of transferable tokens in text-attributed graphs.” We address your concerns as follows.\n\n> W1: How to define the 𝑗th neighbor related to two nodes in Theorem 2.2?\n> \n\nLet’s consider two cases. If the number of neighborhoods of the two nodes is the same, we can readily compare their corresponding neighbors. If the number of neighborhoods is different (e.g.,  n1,  n2  where  n1 > n2 ), we use a straightforward method for approximation. For the node with fewer neighborhoods (n2), we add virtual nodes in the number of (n1-n2) to ensure all nodes have n1 neighborhoods. It is true that a large gap in the number of neighborhoods between two nodes may lead to significant approximation error. However, we believe the approximation error would not be too large in real-world cases, where node degrees generally follow long-tail distributions. That is, most nodes have small degrees, while a small number of central nodes have high degrees. Therefore, it is not necessary to add too many virtual nodes when measuring the distance between computation trees, mitigating the approximation error. \n\n> W2: How to ensure the bounded distance measurement in Theorem 2.2?\n> \n\nWhile the distance between original node features might be unbounded, we employ a simple normalization technique (which is actually used in this paper) to manually bound the distance. Specifically, we normalize the features as $\\mathbf{x} / \\| \\mathbf{x} \\|$, converting the unbounded Euclidean distance into a bounded Cosine distance. This makes Theorem 2.2 more practical.\n\n> W3: The issue in Eq. 2 and the definition of 𝛿𝑗.\n> \n\nWe apologize for the confusion and sincerely thank you for identifying the typos in the paper. You are correct that the loss is computed between  $z_i$  and  $c_i$, consistent with the vanilla VQ-VAE. We will correct these typos. \n\nRegarding $\\delta(\\cdot)$ , it is a linear projection implemented by a basic fully-connected layer. We will refine the paper to provide better clarification.\n\n> W4: What’s the model performance when the pre-training domains are totally different from downstream tasks?\n> \n\nWe thank the reviewer for raising this important point. We conducted experiments on two citation networks, Cora and Arxiv, and two molecule networks, HIV and PCBA. The results are shown below:\n\n| Pretrain Data | Cora | Arxiv | HIV | PCBA |\n| --- | --- | --- | --- | --- |\n| Cora + Arxiv | 78.72 ± 1.62 | 71.85 ± 0.12 | 70.62 ± 3.06 | 78.10 ± 0.40 |\n| HIV + PCBA | 78.46 ± 1.42 | 71.76 ± 0.15 | 72.19 ± 2.04 | 78.43 ± 0.25 |\n\nEven when the pre-training and downstream datasets are from different domains, there is no significant model degradation. For example, the model performance on Cora is 78.72 when pre-trained on citation networks and 78.46 when pre-trained on molecule networks. Additionally, the performance on PCBA is 78.43 when pre-trained on molecule graphs and 78.10 when pre-trained on citation networks.\n\n> W5: Why the token size is smaller than expected? What are tokens learn exactly?\n> \n\nOne potential reason for the relatively lower number of tokens is the use of a prototype classifier. The construction of prototypes in this classifier involves combining different tokens in a memory bank, which can be interpreted as generating new tokens from previous tokens. In other words, the prototype classifier implicitly enlarges the vocabulary and enhances its diversity. Removing the prototype classifier degrades the average model performance from 79.92 to 78.06, while increasing the token size to 2048 provides only a marginal performance gain, reaching 80.38. \n\nWe also explored the meaning of tokens, as shown in Figure 1 of the attached PDF file in the general response. This figure reveals a set of tokens shared across datasets, each potentially maintaining general patterns across domains and tasks. Additionally, distinct tokens are used by individual domains or datasets, indicating domain-specific patterns. These well-separated tokens between different domains might provide a better source for the prototype classifier in creating prototypes.\n\n> W6: Comparison to VQGraph.\n> \n\nWe thank the reviewer for the suggestion to compare our GFT to VQGraph and discuss their relation and differences. The major connection between GFT and VQGraph is the usage of vector quantization in learning a discrete vocabulary for downstream tasks. However, there are four major differences between GFT and VQGraph. (1) Model Objective: GFT focuses on building a general task reasoner, but VQGraph aims to train a structure-aware MLP for efficient inference. (2) Pretrain Dataset: GFT is pre-trained on cross-domain and cross-task datasets to acquire transferable patterns among graphs, but VQGraph is pre-trained on a single dataset to better capture the structural information. (3) Usage of Tokens: GFT treats tokens as specific transferable patterns, using them directly to build classifiers. VQGraph, on the other hand, treats tokens as external structural knowledge to complement the training of MLP classifiers. (4) Downstream Tasks: GFT can be applied to various graph-related tasks with different settings like few-shot and zero-shot learning. VQGraph is designed for node classification with a basic pre-training and fine-tuning setting.\n\n> W7: How GFT fits on with large graphs?\n> \n\nGFT can still use mini-batch to fit to a large graph. Given a large graph, we extract the mini-graph through mini-batch and use GNNs to encode the computation trees preserved on the mini-graph. Please refer to [W1] of general response for details. \n\nBest regards,\n\nThe authors", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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": "WdEc9MM4eo", "reviewer": "Reviewer_hEws", "summary": "The paper proposes GFT, a graph foundation model based on computation tree. Extensive experiments and theoretical analyses are conducted to show the effectiveness of GFT across diverse tasks.", "questions": "How are baseline results obtained? What kind of features are leveraged?", "limitations": "NA", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. Addresses a significant challenge (identifying transferrable patterns) in graph foundation models.\n2. Includes both theoretical and empirical evaluations on synthetic and real-world graphs.\n3. Conducts extensive experiments including multiple graph tasks and domains.", "weaknesses": "1. The experiments are unconvincing (and most likely unfair): Only a few outdated supervised baselines are used, and their results are weaker than expected. For instance, the GCN's performance on Cora should surpass 80, and the results for GIANT on Arxiv are notably low. Are all baselines using SentenceBERT embedding? If not and the raw features are used, the improvements might be contributed to better text encoders.\n2. Assumes a common feature space across different graphs, limiting its applicability to non-textual graphs.\n3. The method is complex, involving a broad hyperparameter space, including computation tree parameters and the betas in Equation 3.\n4. Certain sections of the paper are unclear, such as the sampling/construction of the computation trees and the interpretation of the y-axis in Figure 5.\n5. The distinction between the computation tree and subgraph is not clearly defined.\n6. The analysis of time complexity should consider the size of subgraphs, similar to GraphSAGE. Furthermore, the discussion should focus on actual wall time to better demonstrate the efficiency of the GFT.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the reviewer’s recognition of our work and thank the reviewer for detailed feedback. We address your concerns as follows.\n\n> W1: The experiments are unconvincing and most likely unfair.\n\n[W1.1] *Outdated supervised baselines.* The baselines are not outdated, as our primary comparisons are with graph foundation models (GFMs) such as Prodigy [1] and OFA [2], published in NeurIPS 23 and ICLR 24, respectively. For supervised and self-supervised baselines, we selected classic works including GCN, GAT, GIN, DGI, BGRL, GraphMAE, and GIANT, in line with existing GFMs [1-4]. Despite being compared to recent supervised methods, our GFT still achieves better average performance (79.92) compared to GATv2 (ICLR ’22) with 76.19 and RevGAT (NeurIPS ’22) with 74.97.\n\n[W1.2] *What features are used?* We strictly followed the OFA [2] to generate node attributes using SentenceBERT and conducted experiments on all baselines based on the SentenceBERT features rather than original features, ensuring a convincing and fair comparison. Since all baselines use the same text embeddings, we can ensure that any improvement is not merely due to the text encoder.\n\n[W1.3] *Why the performance of baselines is lower than expected?* It's becuase the text encoder does not always lead to better performance with three resaons: (1) **Complexity of text-based continuous features.** These features are more complex than manually designed (discrete) features, making it challenging to learn the underlying correlations between features and labels. References such as [6] indicate this issue, where the performance of GraphSAGE on Arxiv degrades from 71.49 to 70.97 when replacing the raw 128-dim features with 768-dim BERT embeddings. Another example is in Table 10 of [5], where performance on molecule graphs (HIV) degrades from 75.52 to 74.20 when using textual features. (2) **Noisiness of text-based features.** Text-based features can be noisier than manually designed features due to biases in the prompts fed into language models, which can impair the quality of generated features and lead to spurious correlations between features and labels. (3) **Harder experimental setting.** For example, we use standard splits with 20 labeled nodes per class for training on Cora and Pubmed, rather than the 10/10/80 train/val/test splitting.\n\nThe lower performance of self-supervised baselines is due to their pretraining on all graphs, which may introduce extra noise, confusing the models in identifying patterns needed for specific tasks or domains. For example, [5] indicates that models (GraphMAE, DGI) pretraining on multiple graphs perform significantly worse than pretraining on a single graph, and [4] shows that GIANT’s performance on Arxiv is 70.87 when the model is pre-trained on ogbn-Papers100M.\n\n> W2: Assumes a common feature space across different graphs, limiting its applicability to non-textual graphs.\n\nAlthough we use text-attributed graphs in our experiments, our GFT can also be applied to non-textual graphs by employing techniques like [7] to align the feature space. Furthermore, this assumption does not significantly impact the contribution of our work, as our primary goal is to identify potential transferable structures across graphs.\n\n> W3: The method involves a board hyperparameter space.\n\nWe thank the reviewer for mentioning the potential efforts involved in hyperparameter tuning. However, our method does not require extensive hyperparameter tuning. For example, when balancing the weights of different losses, it is sufficient to adjust their scales. For other hyperparameters, we can follow existing papers to set the default value. This simplifies our efforts to tuning only a few hyperparameters, such as learning rate, weight decay, and batch size. Despite this, our GFT still achieves superior performance. \n\n> W4: The interpretation of y-axis in Figure 5.\n\nThis axis represents a metric (NT gap) used to measure the occurrence of negative transfer. The metric follows the principle: for a certain target task T, if the pretrained model (pretrained on S) performs worse than a randomly initialized model, negative transfer occurs. Therefore, we define this metric as $\\text{NT gap} = R(S,T) - R(\\emptyset, T)$, where $R(S,T)$ is the loss of the pretrained model and $R(\\emptyset, T)$ is the loss of the initialized model for the downstream task T. \n\n> W5: The difference between computation trees and subgraphs. How to construct computation trees? \n>\n> W6: The time complexity analysis should consider the size of subgraphs. The real-time consumption should be provided.\n\nPlease refer to [W1] of the general response, where we provide a detailed comparison between computation trees and subgraphs, including the construction and time consumption. We would like to further clarify why it is not necessary to consider the size of subgraphs. The reason is that matrix-based BFS has the same time complexity regardless of the size of the subgraphs. Moreover, given a node, the number of involved nodes within k-hop is the same, no matter in tree-like or subgraph-like structures. This makes the impact of the subgraph size marginal when comparing computation trees and subgraphs. \n\nBest regards,\n\nThe authors\n\n---\n\nReference:\n\n[1] Huang, et al., PRODIGY: Enabling In-context Learning Over Graphs, NeurIPS, 2023.\n\n[2] Liu, et al., One For All: Towards Training One Graph Model for All Classification Tasks, ICLR, 2024.\n\n[3] Chen, et al., LLaGA: Large Language and Graph Assistant, ICML, 2024.\n\n[4] He, et al.,UniGraph: Learning a Cross-Domain Graph Foundation Model From Natural Language, Arxiv, 2024.\n\n[5] Chen, et al., Text-space Graph Foundation Models: Comprehensive Benchmarks and New Insights, Arxiv, 2024.\n\n[6] Chien, et al., Node Feature Extraction by Self-Supervised Multi-scale Neighborhood Prediction, ICLR, 2022.\n\n[7] Zhao, et al., All in One and One for All: A Simple yet Effective Method towards Cross-domain Graph Pretraining, KDD, 2024.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "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:
Dear ACs and reviewers,

We thank the reviewers for their feedback and constructive suggestions. The positive feedback has truly inspired us, highlighting the importance of exploring transferable patterns on graphs (H6gM, M9ZQ, hEws), the novelty of our GFT (H6gM, U8xo, M9ZQ), the meaningfulness of cross-domain and cross-task settings (all reviewers), and the soundness of theoretical analysis (all reviewers). In particular, we appreciate Reviewer M9ZQ’s recognition as “the first one demonstrates the potential existence of transferable tokens in text-attributed graphs.” 

Here we address some common concerns. 

> W1: Differences between computation tree and subgraph

Some reviewers (U8xo, hEws) expressed confusion regarding the differences between computation trees and subgraphs. We provide an illustration in **Figure 2 in the attached PDF** for better clarification. Our concept of computation trees is closely aligned with [1], representing tree-like patterns derived from unfolding the message passing process. Encoding the computation trees of a node is equivalent to encoding the node itself via message passing GNNs, implying that the information in computation trees can be *fully* learned by basic GNNs, demonstrating both learnability and efficiency in encoding computation trees. Moreover, computation trees appear across graph-related tasks. For example, node classification involves classifying the computation tree of a node; edge classification involves classifying the computation tree of a virtual node connecting the end nodes of an edge (u, v); and graph classification involves classifying the computation tree of a virtual node connecting all nodes in the graph. In other words, graph-related tasks can be unified as computation tree-level tasks. Notably, our computation tree can be reinterpreted as a special pattern preserved on the ego-graph of the target node, differing from junction trees or H-trees, which construct additional tree-like graphs to complement the original graph.

Subgraphs, on the other hand, are graph-like substructures within the original graph, such as motifs in molecule graphs. Reference [2] identifies subgraphs as basic patterns across graph-related tasks and reformulates these tasks into subgraph-level tasks. For example, in node classification, they extract the ego-graph around each node and assign the label of the induced graph as the label of the center node, converting node classification into subgraph classification. This process involves (1) extracting ego-graphs around task-relevant nodes and (2) using GNNs to learn graph-level embeddings for classification. However, this extraction process introduces additional time consumption and increased memory usage for storing induced subgraphs. More importantly, the information in subgraphs is not always learnable by basic GNNs, as they cannot detect some critical substructures necessary for learning graph-level embeddings [3,4], reducing the feasibility of using subgraphs to define graph vocabularies.

We provide empirical analysis for better understanding. Efficiency analysis is presented in **Figure 3 of the attached PDF**. Subgraphs generally incur an extra 1/3 time consumption compared to computation trees and encounter out-of-memory errors when batch size exceeds 2048, compared to 8192 for computation trees. The performance comparison is shown in the table below, where the subgraph version (GFT - Subgraph) performs worse than the computation tree version (GFT). We use GAT and GraphMAE as additional baselines and apply linear classifiers on all models for a fair comparison.

||Node|Link|Graph|Avg.|
|---|:---:|:---:|:---:|:---:|
|GAT|74.69|84.55|67.83|75.44|
|GraphMAE|73.98|82.15|62.17|73.07|
|GFT - Subgraph|74.23|86.49|67.89|76.13|
|GFT|75.51|88.99|72.21|78.06|

[1] Chuang, et al., Tree mover’s distance: Bridging graph metrics and stability of graph neural networks, NeurIPS, 2022. 

[2] Sun, et al., All in One: Multi-Task Prompting for Graph Neural Networks, KDD 2023. 

[3] Chen, et al., Can Graph Neural Networks Count Substructures?, NeurIPS, 2020. 

[4] Zhang, et al., Beyond Weisfeiler-Lehman: A Quantitative Framework for GNN Expressiveness, ICLR, 2024

> W2: Zero-shot learning setting

Some reviewers (H6gM and U8xo) suggested a comparison of zero-shot learning. Thus, we follow existing approaches [2-4] by using an additional LLM as the task reasoner to enable zero-shot learning. Specifically, we follow the design in [4] to combine the learned embeddings and specific prompts as input for the LLM and finetune the LLM with LoRA. We select four baselines: GraphGPT [2] and LLAGA [3] designed for a single graph task, OFA designed for cross-tasks, and OFA + LLM leveraging the power of LLM based on OFA, similar to our GFT + LLM. The results are presented below.

||Cora|Arxiv|WN18RR|
|---|:---:|:---:|:---:|
|GraphGPT|18.13|64.76|-|
|LLAGA|34.69|-|-|
|OFA|19.31|46.19|19.98|
|OFA + LLM|30.56|64.32|27.41|
|GFT + LLM|34.66|67.80|30.30|

The advantage of GraphGPT and LLAGA is primarily due to their pre-training on a single dataset (or datasets from the same domain), allowing them to learn domain-related patterns for downstream tasks. In contrast, OFA and our GFT are pre-trained on cross-domain graphs, learning general knowledge rather than specialized knowledge. Specifically, the basic OFA’s performance is relatively lower due to the use of graph prompt learning, which might be less expressive than LLMs. When using LLMs as reasoners, OFA’s performance significantly improves, though it remains lower than our GFT.

[1] Liu, et al., One For All: Towards Training One Graph Model for All Classification Tasks, ICLR, 2024. 

[2] Tang, et al., GraphGPT: Graph Instruction Tuning for Large Language Models, SIGIR, 2024. 

[3] Chen, et al., LLaGA: Large Language and Graph Assistant, ICML, 2024. 

[4] He, et al.,UniGraph: Learning a Cross-Domain Graph Foundation Model From Natural Language, Arxiv, 2024. 

Best regards,

The authors

Meta-review: This paper proposes a graph foundation model that uses vector quantization techniques to promote GNN node embeddings (which encode the so-called "computation trees") to be assigned to a limited vocabulary of tree tokens each having a learnable embedding. The tree tokens are shared across different datasets to improve the transferrability of GFM and empirically perform well. Basically this is a good paper for the first time exploring how to enhance the transferrability of graph patterns learned by a GFM by learning a shared vocabulary across graphs. 

I have a few suggestions to further improve the readability of the paper: 

1. Only until I read all the reviews and rebuttals did I realize many key details of the paper, e.g., the proposed model uses OFA's sentence encoder to align the feature spaces across graph datasets, and that Equation (2) has serious typos, etc. These should be fixed, otherwise careful readers can be frustrated with consistent questions in mind while reading the paper. 

2. The statement "Since computation trees are capable of capturing localized patterns [ 51 ], it’s able to represent a graph as a multiset of computation trees without information loss" is incorrect. The WL test exactly represents a graph as a multiset of computation trees while cannot solve the graph isomorphism problem. The encoding of graph into trees is lossy.

3. In response to W4 of U8xo, the statement "However, this limitation arises primarily due to the limited expressiveness of the backbone model (GraphSAGE) rather than our model design... We can address this issue by using more expressive GNN backbones as described in [4]" is incorrect. As pointed out in [1], no matter how expressive the node-level GNN is, encoding nodes independently of each other cannot solve the link-level isomorphism. Therefore, the computation trees have their fundamental limitation in expressiveness. The authors are encouraged to discuss this point as well as other potential improvements in their limitation section (no one exists right now).

[1] Labeling trick: A theory of using graph neural networks for multi-node representation learning. NeurIPS 2021.
Decision: Accept (poster)