GFT: Graph Foundation Model with Transferable Tree Vocabulary

Authors: zehong  wang
zheyuan  zhang
nitesh v chawla
chuxu  zhang
yanfang  ye
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 03:25:13

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.

Main paper: 
 introduction: 
 Foundation models such as Large Language Models (LLMs) and Large Vision Models (LVMs) keep reshaping our view of the world [7, 100, 51, 112, 50] . These models are designed to be generalpurpose, adaptable across various tasks and domains through fine-tuning or prompting, such as GPT-4 [1] in Natural Language Processing (NLP) and Sora [46] in Computer Vision (CV). Research attributes the success of foundation models to the uniformity of tasks and a general vocabulary that defines basic transferable patterns across tasks [98, 76, 112, 3, 50] . For example, LLMs [1, 112] treat language tasks as question-answering or next-word prediction and deconstruct sentences using a word vocabulary. Similarly, LVMs [100, 98, 3] reformulate image tasks as image question-answering, converting images into discrete tokens using a vision vocabulary. Inspired by the success of LLMs 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 farreaching 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 been GFMs that can achieve desired performance on a wide range of graph-learning-related tasks. Unlike CV and NLP, as graphs represent complex, non-Euclidean relationships among entities [92, 48, 104, 58, 107] , a grand challenge of building GFMs lies in identifying transferable patterns across graphs [50, 93, 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 graph transferability using subgraph structures [114, 59, 50] : Zhu et al. [114] demonstrate that the transferability between graphs is linked to the ego-graph patterns of individual nodes and establish a 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 a single model to be applied to diverse tasks. Huang et al. [30] , Liu et al. [45] expand GFMs to cross-domain scenarios by unifying the node feature space across different graphs through LLMs [60, 76] . Despite these successes, the process of explicit subgraph extraction remains time and memory intensive [30] . More importantly, numerous studies such as [20, 10, 53, 103] show that message-passing 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-passing mechanism of GNNs, we 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 on graphs as computation trees -i.e., subtree structures derived from the 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 GNN process [20] , 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 [23] .(3) Learnability: As the information of computation trees is completely captured by message-passing 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 as graph vocabulary tokens, we 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 cross-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. 
rethinking transferable patterns on graphs 2.1 transferability on gnns: 
 Transferability refers to a model's capability to extract patterns from source tasks and apply this knowledge to enhance performance on related target tasks [5, 33, 90] . Understanding transferable patterns is essential for developing graph foundation models. Early research focuses on analyzing transferability through the perspectives of graph spectrum [41, 42] and subgraphs/substructures [114] , defining transferability as model invariance to minor permutations on the graph. A more recent study [50] investigates the transferable vocabulary in graphs by identifying key substructures relevant to various tasks. For instance, they find that triadic closure, homophily, and heterophily are vital for node classification; local and global structural proximities are crucial for link prediction; and certain motifs [103] , such as triangles, k-cliques, and stars, serve as fundamental components for graph classification. Another line of research [62, 8, 69] incorporates graphon theory to provide a theoretical basis for transferability. Specifically, Ruiz et al. [62] establish a bound on the embeddings of two graphs sampled from the same graphon. Cao et al. [8] expand this to include pre-training and fine-tuning scenarios, assessing the distance between graphs based on their alignment within the graphon space. However, the stringent assumptions of graphon theory limit its practical application in the design of graph foundation models.We identify two primary limitations in analyzing transferable patterns on graphs: (1) While certain domains [110, 87, 43, 108] or tasks [114, 111, 19] exhibit transferable patterns, the challenge of identifying universally transferable substructures is difficult. (2) More critically, basic messagepassing GNNs, constrained by the 1-WL test [94, 52] , fail to recognize certain subgraphs (or motifs) [20, 10, 103] , such as stars, conjoint cycles, and k-cliques, as well as heterophily patterns [113] . This limitation in recognizing substructures impedes using subgraphs as transferable tokens in graph vocabulary [68, 30, 45] . More related works are elaborated in Appendix A.Task-relevant Nodes and the corresponding computation trees (bottom). A virtual node can be added at the top to connect all task-relevant nodes, unifying different tasks as the tree-level task.In this paper, we rethink the transferable pattern in graphs as the computation tree -a specialized subtree pattern that emerges from unfolding the message-passing process [12] . This pattern is demonstrably effective at capturing critical localized information within the graph [20, 52, 94, 12] . Treating computation trees as tokens within a graph vocabulary offers two distinct advantages: (1) computation trees preserve the essential structural information of the graph, which is learnable through message-passing GNNs, and (2) the computation tree structure occurs across various graph-based tasks. These tasks can be unified as computation tree classification by integrating a virtual node, as shown in Figure 1 .Before diving into transferability analysis, we first establish the necessary notations. Consider a graph G = (V, E) composed of node set V and edge set E. Each node v ∈ V is associated with a feature vector x v ∈ R d and a computation tree T v with L layers. A GNN encoder ϕ processes these computation trees as inputs, producing embeddings for root nodes z = ϕ(T v ) ∈ R d ′ .Definition 2.1 (Computation Trees [12] ). Given a graph G = (V, E), defineT 1 v = v and T L vas 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 byT L G := {T L v } v∈V .Figure 1 demonstrates the construction of computation trees across various graph tasks, including node-, link-, and graph-level tasks. These trees capture essential localized subtree patterns within the graphs [55, 64, 12] . If the L-layer computation trees for two nodes are similar, it indicates that these nodes share similar neighborhoods, suggesting they represent analogous phenomena [42] . Thus, it is rational to assess transferability of computation trees by examining the stability of GNNs in producing analogous embeddings for similar trees [62, 42] .Theorem 2.2 (Transferability of Computation Tree ). Given two L-layer computation trees T v1 , T v2 derived from the graph G and a GNN encoder ϕ, the Euclidean distance between the tree embeddings ∆ ≜ ∥ϕ(T v1 ) -ϕ(T v2 )∥ 2 is bounded as follows:EQUATIONwhere ∆ L-1 v1,v2,j represents the distance between the (L -1)-layer subtrees of the j-th children of nodes v 1 and v 2 , C 1 , C 2 are constants, and B x denote bounded norm of x. The variable d l indicates the number of children in the l-layer subtrees, andD l = d l d l-1 ...d 1 .Proof. All proofs in the paper are detailed in Appendix D.Remark 2.3. Theorem 2.2 derives a recursive bound for computation tree similarity. In particular, the distance between two computation trees is closely correlated to the similarity of their subtrees, where higher subtree similarity results in a 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 to improved transferability.Supportive Observations -Synthetic Graphs. Figure 3 shows that high computation tree similarity between graphs correlates with improved transfer learning performance on synthetic graphs (Figure 2 ). Specifically, we construct three distinct graphs: G 1 and G 2 share similar motifs but differ in computation tree distributions, while G 1 and G 3 exhibit dissimilar motifs but similar computation tree distributions. We employ the WL subtree kernel [64] and the graphlet sampling kernel [57] to assess tree and motif similarity, respectively, and utilize the inverse of the Central Moment Discrepancy [102] to measure transferability. Further details on experimental settings and additional results are available in Appendix E.1. Our findings indicate that transferability is strongly associated with computation tree similarity rather than motif similarity, regardless of the scale of graphs (# blocks). Supportive Observations -Real-world Graphs. Table 1 validates the correlation between computation tree similarity and transferability in real-world graphs, including homophily Airport networks [61] and heterophily WebKB networks [56] . We evaluate transferability based on transfer learning performance in node classification tasks. Detailed experimental settings and additional results are available in Appendix E.2. Our findings in real-world graphs corroborate those in synthetic graphs: higher computation tree similarity enhances transferability, while the impact of motifs is marginal, no matter using original node features (Table 1 ) or randomized node features (Table 9 ). Question: Does the paper discuss the limitations of 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 in 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 on 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 a few datasets or with a 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, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a 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 be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
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 In fine-tuning, the learned tree vocabulary is applied to unify graph-related tasks as tree classification, adapting the general knowledge to specific tasks.pre-training through a computation tree reconstruction task to acquire general knowledge from a crossdomain graph database. Subsequently, GFT quantizes the embedding space of computation trees to form a 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.The pre-training stage focuses on learning general computation tree patterns on graphs, facing two primary challenges: (i) obtaining transferable patterns, and (ii) comprehensively capturing computation tree knowledge. For the first challenge, we learn a discrete tree vocabulary by quantizing the embedding space of computation trees [77] . For the second challenge, we introduce a computation tree reconstruction task that considers multiple aspects of computation trees.Learning Tree Vocabulary. The idea of learning a discrete computation tree vocabulary originates from the principles of sparse distributed memory in cognitive science [37, 38] , which stores and retrieves memory in a distributed manner. By adopting these principles, the tree vocabulary maintains a set of tokens that are reusable and adaptable across various tasks, improving model transferability.We adopt the Vector Quantization (VQ) [77] to develop the tree vocabulary. Given a graph database2 D = {G i } n i=1 , we randomly extract a set of computation trees T = {T i } m i=1 and employ a GNN encoder ϕ to generate the tree embeddings Z = {z i } m i=1 . We define the computation tree vocabulary as a set of learnable tokens C = {c 1 , ..., c K }. The tree embedding space is quantized by assigning each embedding to the nearest token, resulting in quantized tree embeddings q i = c j , where j = arg min j ∥z i -c j ∥ 2 . We optimize this projection by back-propagating the reconstruction error to the tree vocabulary C and applying a straight-through gradient estimator [6] to the encoder ϕ. 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 c 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 is thus defined as:L pretrain = L tree + 1 m m i=1 sg[z i ] -c i 2 2vocabulary lossEQUATIONwhere sg[•] denotes the stop-gradient operator and β 1 is the weight.Computation Tree Reconstruction. We introduce a computation tree reconstruction task designed to enable a deep understanding of the structural and semantical attributes of computation trees [36] .We use the tree tokens to reconstruct the original computation tree, retaining general knowledge while discarding irrelevant details. Specifically, we develop three reconstruction tasks: (i) reconstructing the features of the root node L f eat , (ii) reconstructing the connectivity among nodes in the computation trees L topo , and (iii) reconstructing the overall semantics of the computation trees L sem :EQUATIONEQUATION, where ẑi = φ(T i ) represents the semantics of the original computation trees, and φ is updated through a moving average of the tree encoder ϕ. The quantized tree embedding q is projected via different decoders defined by MLP, qj = δ j (q), γ is the scaling factor, and E and Ê represent sets of existing and non-existing connections in computation trees, respectively. e ij denotes the edge embedding between nodes i and j. By jointly optimizing these tasks, we establish a comprehensive reconstruction objective:EQUATIONwhere β i indicates the weights of respective losses. The philosophies under these loss functions separately correspond to existing works [39, 26, 74, 86] . For example, Kipf and Welling [39] reconstruct the graph structure, aligning to the philosophy of L topo , Hou et al. [26] reconstruct node feature that is similar to L f eat , and Thakoor et al. [74] , Wang et al. [86] employ contrastive learning to maximize the alignment between two views, aligning to L sem . Unlike existing methods that typically focus on reconstructing a single aspect of computation trees, GFT integrates multiple facets [85] to learn a general and transferable tree vocabulary.Enhancing the Quality of Tree Vocabulary. The effectiveness of GFT is correlated to the quality of the tree vocabulary, which should be both comprehensive and expressive. A comprehensive vocabulary is inclusive enough to accommodate new patterns, while an expressive vocabulary ensures that different tree tokens do not overlap in representation [50] . To enhance comprehensiveness, we augment the computation trees during pre-training, increasing the variety of observed computation trees through node feature augmentation and structural augmentation, as described by [115] . To improve expressiveness, we regularize the tree vocabulary space by intentionally increasing the distance between distinct tokens [65] . Specifically, we introduce an orthogonal regularizer designed to maintain tree tokens orthogonal to each other, effectively expanding the tree token space:EQUATIONwhere c i is tree token, I K is the identity matrix for K dimensions, and ∥ • ∥ F denotes the Frobenius norm. The orthogonal loss L ortho is integrated with Equation 2. More analysis is in Appendix C.2.The pre-training stage encodes general knowledge into the tree vocabulary, while the fine-tuning phase adapts this knowledge to specific tasks. This adaptation is challenging because identical patterns can have different meanings across domains and tasks [8] . For example, a triangular structure indicates stable relationships in social networks (node classification) but denotes unstable chemical properties in molecular networks (graph classification). To this end, we propose computation tree classification that utilizes the tree vocabulary to unify graph tasks as the tree-level task, ensuring the adaptation is applicable across diverse tasks and domains.Reformulate Graph Tasks as Computation Tree Classification. Graph-related tasks can be represented by task-specific computation trees, as illustrated in Figure 1 . Specifically, for node classification, the task-specific computation tree, denoted as T node = T i , is derived directly from the node itself, resulting in the embedding z = ϕ(T i ). For link prediction, the computation tree, T link = Combine(T s , T t ), merges the computation trees of two nodes of the edge, with the embedding z = mean(ϕ(T s ), ϕ(T t )). For graph classification, the task-specific computation tree T graph = Combine({T v } v∈V ) integrates the computation trees of all nodes within the graph, and computes the embedding as z = mean({ϕ(T v )} v∈V ). Subsequently, the embeddings of these task-specific trees are used to query the tree vocabulary and then make predictions, adapting the general knowledge encoded in the vocabulary to various tasks and domains.Prototype Classifier. The prototype classifier f proto constructs class prototypes using tokens from the tree vocabulary. Given a set of task-specific computation trees {(T i , y i )} n i=1 with |C| classes, we employ the pre-trained GNN encoder ϕ to generate tree embeddings Z = {z i } n i=1 . These embeddings are then used to query the tree vocabulary and produce quantized embeddings Q = {q i } n i=1 . Subsequently, we construct a class-wise memory bank S = {S 1 , ..., S |C| }, where S k = {q i ∈ Q|y i = k}, to store tree tokens of the same class. The memory bank typically includes all instances from the training set. From this, we derive a set of prototypes for each class {p k } |C| k=1 , calculated as p k = (1/|S k |) qi∈S k q i . These prototypes are then used for predictions:EQUATIONwhere sim(•) denotes the cosine distance and τ is a temperature scaling factor. We optimize the cross-entropy loss between the classifier's output and the ground truth to update the encoder ϕ.Linear Classifier. Different from the prototype classifier, which utilizes class prototypes to adapt to target tasks, the linear classifier f lin directly applies the knowledge encoded in each tree token. Specifically, given a task-specific computation tree T i , we use the encoder to generate tree embeddings z i and then query the tree vocabulary to retrieve q i . These embeddings are used for predictions as:EQUATIONWe optimize the cross-entropy loss between the prediction f lin (z) and the ground truth to update the parameters of the encoder and the linear classifier. During inference, predictions from both the prototype and linear classifiers are combined to form the final output. It is important to note that the tree vocabulary remains fixed during fine-tuning to preserve the integrity of the encoded knowledge.Tree Vocabulary Learns Generalizable Tokens. Learning tree vocabulary via VQ involves clustering within the embedding space of computation trees, utilizing a margin-aware classifier [14] that assigns each computation tree to a specific cluster. Assuming that each computation tree T is associated with an underlying clustering label y, and that each pair (T i , y i ) is sampled from the distribution P T , we derive the following theorem: Theorem 3.1. Given a set of computation trees {(T i , y i )} n i=1 sampled from the distribution P T , the VQ process functions as a margin-aware prototype classifier f that predicts the class of computation trees via a distance measure. The risk R(f ) of classifier f can be bounded with probability 1 -δ:EQUATIONwhere R(f ) is the empirical risk, p denotes the number of tokens, C is a constant, and ρ acts as 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 ρ, the number of observed computation trees n, and the number of tokens p. (i) A larger margin ρ results in a 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 a tighter generalization bound, which supports the use of augmentations to increase the diversity of computation trees. (iii) More tokens p may loose the upper bound of the generalization error, potentially due to a higher risk of overfitting. This aligns with our experimental findings that more tokens do not necessarily lead to improved performance (Section 4.4). Tree Vocabulary Mitigates Negative Transfer. Negative Transfer (NT) occurs when the pre-training process degrades model performance on a target task. This issue often results from misalignment between the pre-training and fine-tuning tasks [89, 8] . Following the approach in [89] , we characterize the NT gap, R(S, T ) -R(∅, T ), as the risk gap on task T with (R(S, T )) and without (R(∅, T )) pre-training on task S, where a smaller NT gap indicates improved transferability. As illustrated in Figure 5 , employing the learned tree vocabulary to align the tree reconstruction task in pre-training and tree classification task in fine-tuning can significantly mitigate negative transfer.Complexity Analysis. A comprehensive complexity analysis of GFT is provided in Appendix B. Notably, GFT employs a single GNN to decompose and encode computation trees, takingO(L • (|E| • d + |V| • d 2 )).In contrast, subgraph-based GFMs [30, 45] require the explicit extraction of subgraphs for each node, taking additional O(|V|3 ) using adjacency matrix-based BFS. This contrast highlights the efficiency of using computation trees as transferable patterns in terms of time complexity. More discussions are in Appendix C.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] Question: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? 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 NeurIPS code and data submission guidelines (https://nips.cc/ public/guides/CodeSubmissionPolicy) for more details. • While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. • Providing as much information as possible in supplemental material (appended to the paper) is recommended, but including URLs to data and code is permitted. 
experimental setting: 
 We employ cross-domain and cross-task graph datasets to evaluate the effectiveness of GFT. For node-level tasks, we utilize citation networks such as Cora, PubMed, Arxiv, and the web link network WikiCS. For edge-level tasks, we include two Knowledge Graphs (KGs), WN18RR and FB15K237. For graph-level tasks, we use molecule networks, including HIV, PCBA, and ChEMBL. All preprocessing steps follow [45] . We take various baselines, encompassing MLP, supervised GNNs such as GCN [40] , GAT [78] , GIN [94] , and self-supervised methods like BGRL [74] , GraphMAE [26] , GIANT [11] , and GFMs including Prodigy [30] and OFA [45] . We replicate each experiment ten times and report the average performance to minimize the influence of randomness. Further details on experimental settings are available in Appendix F.Pre-training and Fine-tuning. Table 2 demonstrates the model performance across cross-domain and cross-task datasets in pre-training and fine-tuning setting. We evaluate the effectiveness of graph foundation models [30, 45] in the following few-shot setting due their distinctive training mechanisms, such as in-context pre-training [30] and fully supervised training [45] . For supervised baselines, models are trained directly on the target graph; for self-supervised methods, we pre-train across all datasets before adapting to the specific target graph. Our approach demonstrates a substantial performance improvement, exceeding the best baseline by an average of over 6%. Specifically, our method outperforms the best baseline by 2% across three datasets and by 5% across another three datasets. This underscores the effectiveness of using computation trees as transferable patterns.Few-shot Learning Table 3 presents the few-shot learning performance of GFT compared to selfsupervised methods [74, 26, 11] and graph foundation models [30, 45, 25] . We randomly select k samples per way from the training set for fine-tuning 3 . This method is similar to Prodigy [30] , and is much more label-efficient than OFA [45] with supervised pre-training. Despite the extremely limited labels for fine-tuning, GFT significantly surpasses existing methods, showing the fast adaptation capability. Appendix H shows more fine-tuning instances can significantly improve performance.Table 5 shows the impact of different pre-training datasets under the pre-training and fine-tuning setting, where comprehensive results (including the following ablation studies) are available in Appendix I. The performance for specific tasks (node-, link-, graph-level) represent the average across all involved datasets. We examine three scenarios with distinct pre-training datasets: (i) all datasets, (ii) only the target dataset, and (iii) datasets excluding the target dataset. These variants are compared against GAT and GIANT, which represent the best supervised and self-supervised baselines, respectively. Notably, GFT consistently outperforms all baselines, regardless of the pre-training dataset utilized. Interestingly, performance improves when using datasets excluding the target dataset compared to pre-training solely on the target dataset. We hypothesize that the computation trees from the non-target datasets provide sufficient information to facilitate the learning of a transferable tree vocabulary, thereby promoting positive transfer.We further evaluate the impact of various combinations of pre-training datasets on the target tasks, as depicted in Figure 7 . For pre-training, we select FB15K237, Arxiv, and ChEMBL, while Cora, WikiCS, WN18RR, and HIV serve as the target datasets. Our findings indicate that an increased number of pre-training datasets consistently enhances performance across all target datasets. However, for existing GFMs, transferability closely correlates with the selection of pre-training datasets, with more datasets sometimes leading to negative transfer [25, 43] . This observation underscores the adaptability of using computation trees as transferable patterns in graph vocabulary.Tree Reconstruction and Classification. Table 4 shows the impact of various reconstruction tasks in pre-training and tree classifiers in fine-tuning. All reconstruction tasks enhance model performance compared to models without pre-training. Notably, semantic reconstruction is most effective for node-level and graph-level tasks due to its comprehensive consideration of node features and graph structures. Feature reconstruction is particularly beneficial for link-level tasks, as it preserves the original node semantics, which are crucial for KGs. The optimal performance is achieved when three tasks are jointly optimized, aligning with findings in Ju et al. [36] . Similarly, the combination of prototype and linear classifiers in tree classification leads to superior performance. Furthermore, removing strategies designed to enhance the quality of the tree vocabulary results in model degradation across all settings (Appendix I.3). Tree Vocabulary. Table 6 shows the importance of the vocabulary, where the use of vocabulary significantly enhances model performance, particularly in link-and graph-level tasks, which aligns to the theoretical analysis that the tree vocabulary improves generalization. However, we observe that increasing the number of tokens in the vocabulary does not necessarily enhance model performance; indeed, the improvements are often marginal. 
conclusion: 
 Conclusion. In this paper, we rethink the transferable pattern in graphs as computation trees and validate their transferability both empirically and theoretically. Building on this insight, we propose a cross-domain and cross-task GFM named GFT. This model 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. In future work, we aim to explore its capabilities for in-context learning and zero-shot learning.Limitations. In this paper, we focus primarily on message-passing GNNs, as message-passing 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. Additionally, message-passing GNNs may lack the expressiveness needed to address isomorphism problems in graphs. One can apply advanced techniques [105] to handle link isomorphism and use advanced expressive GNNs [103] to tackle graph isomorphism. Moreover, the deployment of 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 as in molecular discovery and financial fraud detection.  
experimental setting/details: 
 Question: Does the paper specify all the training and test details (e.g., data splits, hyperparameters, how they were chosen, type of optimizer, etc.) necessary to understand the results? Answer: [Yes] Justification: See Appendix F. 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 a 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. 
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 in the Appendix G, H, and I. 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, confidence 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.)• The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a 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 is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are 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 to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: Our work poses no such risks.Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a 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 to 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 a best faith effort.12. Licenses 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 use 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 a URL. • The name of the license (e.g., CC-BY 4.0) should be included for each asset.• For scraped data from a particular source (e.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, paperswithcode.com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of a 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. 
 
 Appendix: 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. [62] derive a 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 a 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 a fine-tuning method based on graphon theory. Although these studies consider graphon as a transferable pattern in graphs, the assumption is challenging to satisfy in cross-domain real-world graphs. Furthermore, graphon theory is generally limited to single-task applications, making it difficult to identify a shared graphon across node-, link-, and graph-level tasks. The send approach examines transferability through subgraphs [114] or graph spectrum [41, 42] . 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. [42] explore transferability through stability, demonstrating that transfer between graphs is feasible when they discretize the same underlying space in a generic sense. Zhu et al. [114] 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 et 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 tree perspectives. Furthermore, 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 et al. [44] offer a tighter generalization bound for GNNs compared to 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 [80] 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. [95] further adapt this model to an inductive setting, where the pre-training 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 a unified subgraph-level task. Instead of extensive model fine-tuning, they incorporate a learnable subgraph into the original graph. Other research focuses on aligning the domain space. Li et al. [43] introduce a zero-shot graph learning framework for cross-domain node classification, leveraging LLMs to unify node features across different graphs. In a similar vein, Zhao et al. [108] 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 identical due to the specialized in-context pre-training strategy. To address this constraint, Liu et al. [45] use LLMs to align the feature spaces of cross-domain graph datasets and introduce a prompt graph to align various tasks on graphs. Xia et al. [93] leverages a 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 LLMs 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 [17, 22, 81] .While GNNs require task-specific adjustments for model training, LLMs can accommodate a wide range of questions and generate appropriate answers. The primary challenge, though, lies in effectively translating graph structures into a 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 LLM. For example, Guo et al. [22] employ a self-prompting methods to utilize the context generated by LLM as input context; Chai et al. [9] used Build-a-Graph and Algorithmic prompting to faciliate LLM understanding. Zhao et al. [109] map a graph into tree-like tokens for designing LLM prompt, further enhancing learning capability. Additionally, another line of works [75, 73] follow Visual Language Models (VLMs) to process the graph into embeddings by GNNs first and then employ LLM as a translator to decode the graph embedding.It is noted that prior research such as Wang et al. [81] , Huang et al. [29] indicate that LLMs can indeed capture structural information from graphs, which enhances their performance on downstream tasks. However, while LLMs 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 of 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, 18, 70, 84] employ tree decomposition to develop advanced GNNs. Specifically, Jin et al. [34] treat the joint tree as complementary to the original graphs, while Fey et al. [18] introduce inter-modality message passing between joint trees and the original graphs. Talak et al. [70] 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 in learning node representations and design a framework to identify the most crucial trees in a graph. Additionally, Nikolentzos et al. [54] design a 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 distance, estimating distribution shifts between graphs. Wu et al. [91] utilizes a 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 transferability, thereby expanding the analysis for computation trees in graph learning.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 computation trees for each node and (ii) updating node embeddings within these trees from bottom to top. Utilizing a GraphSAGE-like architecture, as 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 computational complexity is linear to the number of edges in the graph G = (V, E), expressed(L • (|E| • d + |V| • d 2 )).For node-level tasks, we directly use the embeddings of computation trees of the target node, which incurs a constant time complexity of O(1). For link-level and graph-level tasks, we apply a nonparametric pooling function to aggregate subtree embeddings into a computation tree embedding, also with a time complexity of O(1).Current graph foundation models [30, 45] 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 O(|V| 3 ) when using an adjacency matrix for the BFS algorithm.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 × d) per instance. Then, determining the shortest distance from K measured distances can be achieved in O(K), and replacing the original instance embedding with the selected token requires O(1). Therefore, the predominant computational cost is distance measurement, leading to an overall complexity ofO(|T | • K • d),where |T | represents the number of computation trees.The computation tree reconstruction comprises three main tasks: feature reconstruction, semantic reconstruction, and topology reconstruction. 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 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. Notably, computation tree can be reinterpreted as a special pattern preserved on the ego-graph of the target node, differing from junction trees [34] or H-trees [70] , 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-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 [10, 103] , reducing the feasibility of using subgraphs to define graph vocabularies.We provide empirical analysis for better understanding. Efficiency analysis is presented in Figure 8 . 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 Table 7 , 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. Batch Size (log) Another challenge in developing a robust discrete vocabulary is 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 Euclidean distance to query tree tokens leads to vocabulary collapse. Consequently, 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 [101] or affine re-parameterization [32] (not evaluated in this paper) can also be employed to mitigate this problem.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 re-sampling. In the fine-tuning phase, subgraph sampling remains effective for the linear classifier, as it directly processes the computation tree. However, the prototype-based classifier, which requires the aggregation of instances with identical labels to form class prototypes, faces efficiency challenges in this mini-batch training setting. To address this, we randomly sample a small subset of the training set for each class to construct the memory bank S. Based on our empirical observations, a limited number of samples per class suffices to achieve desirable performance.Homophily and heterophily [49] are both critical properties for node-level tasks. The primary distinction between these types of graphs is that identical connectivity patterns can indicate different meanings. We consider our model is also effective for heterophily graphs. Although we only evaluate the performance of GFT on homophily graphs (Cora, PubMed, WikiCS, Arxiv), two considerations support its applicability to heterophily graphs: (i) The analysis of computation tree transferability shows that, similar to 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 fine-tuning 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.The major connection between GFT and VQGraph [96] 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.Recent researches [17, 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 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 a GNN as an encoder to analyze transferable patterns on graphs. We consider these LLM-based approaches as complementary to our work. 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 [20, 103] suggests that certain substructure or motif patterns within subgraphs are not learnable by basic message-passing GNNs. Unlike these methods, our 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 of 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 seen a unique subgraph structure, which is fully learnable by GNNs without information loss.In addition, we also compare the number of parameters of these GFMs in Table 8 . Considering the number of parameters, Prodigy [30] has 2 million parameters, while OFA [45] 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.See Figure 9 .(1) Feat. Recon. (3) Topo. Recon. We restate Theorem 2.2 from the main paper as below. Theorem D.1 (Transferability of Computation Tree). Given two L-layer computation trees T v1 , T v2 derived from the graph G and a GNN encoder ϕ with parameters W = (W 1 , W 2 ), the Euclidean distance between the tree embeddings ∆ ≜ ∥ϕ(T v1 ) -ϕ(T v2 )∥ 2 is bounded as follows:EQUATIONEQUATION)where ∆ L-1 v1,v2,j represents the distance between the L -1-layer subtrees of the j-th children of nodes v 1 and v 2 , and constantsC 1 = C σ B W1 and C 2 = C σ C ρ C g B W2 .Here C σ , C ρ , C g are Lipschitz terms for GNN components, and B W1 , B W2 , B x denote bounded norms of W 1 , W 2 , x, respectively. The variable d l indicates the number of children in the l-layer subtrees, with each d l ≤ d, andD l = d l d l-1 ...d 1 .Proof. We calculate the embedding distance between two L-layer computation trees generated from a single GNN encoder ϕ with parameters W = (W 1 , W 2 ). Here we use a GraphSAGE-like encoder, as described in the Appendix F.1, that W 1 transforms the target node, while W 2 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 x v represents the features of node v, and N (v) denotes the set of direct neighborhood in the graph, which correspond to the children of node v in the computation tree T v .With a bit of notation abuse, we define the GNN as:EQUATION)where σ as the non-linear activation function, ρ as the permutation-invariant aggregator function, and g as the update function (ρ and g are all based on neural networks). To simplify notation, we denote the computation tree embeddings by T (W) = ϕ(T ). Since these functions and neural networks exhibit Lipschitz continuity, we represent their Lipschitz constants as C σ , C ρ , and C g , respectively.Additionally, we assume that the norm of node features is bounded by ∥W 1 ∥ ≤ B W1 , and the norms of model weights by∥W 1 ∥ ≤ B W1 and ∥W 2 ∥ ≤ B W2 .Given the absence of constraints on the tree structures, we manually align the structures of the two trees by incorporating non-sense nodes and edges, as depicted in Figure 10 . Initially, the structures of tree 1 and tree 2 are entirely distinct, as 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 as 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 Following, we expand the stability term ∆:EQUATION)where R(W,T L v ) = ρ( j∈N (v) g(T L-1 j (W))).We can further bound the term as:EQUATIONAs we already align the structures of two computation trees by adding non-sense branches to ensure|N (v)| = |N (v 1 )| = |N (v 2)|, we can merge the two terms in the RHS:EQUATIONwhere ∆ L-1 v1,v2,j = ∥T L-1 v1,j (W) -T L-1 v2,j (W)∥ 2 . We now establish a bound on the distance between two computation trees of identical structure by analyzing the node-wise differences from bottom to top. Denote the number of branches (i.e., children) at each l-layer as d l , we simplify this bound as follows:EQUATIONThis bound prioritizes the most influential children of a node to dominate all other branches. By combining Equation 11with Equation 14, we recursively establish the bound of the distance between two computation trees:EQUATIONwhereC 1 = C σ B W1 and C 2 = C σ B W2 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 v 1 and v 2 , denoted as ∆ = ∆ L v1,v2 . This allows us to recursively bound the distance. Given that all x are bounded by ∥x∥ 2 ≤ B x , the distance between the node features x v1 and x v2 satisfies ∥x v1 -x v2 ∥ 2 ≤ 2B x by the triangle inequality. Consequently, we can further develop the recursion as follows:EQUATIONwhereD l = d l d l-1 ...d 1 .Assuming that the number of branches (i.e., children) at each l-layer does not exceed the maximum number of branches in the tree, such that d 1 , ..., d L ≤ d. We can further simplify the recursion by:EQUATION)D.2 Proof for Theorem 3.1Before proving Theorem 3.1, it is necessary to first establish a more general version of the theorem, as detailed below: Theorem D.2. Given a set of instances {(x i , y i )} n i=1 sampled from the distribution P, and a marginaware prototype classifier f that predicts the class of instances via a distance measure. The risk R(f ) can be bounded with probability 1 -δ:EQUATION)where R(f ) is the empirical risk, p denotes the number of tokens, C is a constant, B is the bounded norm of x and p, and ρ acts as the margin, serving as a 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 to the target instances. We denote the set of p tokens by {p i } p i=1 , each with a norm bounded by B, and the labels associated with each token by {c i } p i=1 . Given an instance (x i , y i ) sampled from a distribution P, the classifier can be defined as follows:EQUATIONwhere x ∈ R d is 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}. Consequently, the function can be represented as f : R d → {-1, 1}. Without loss of generality, this binary classification setting can be readily extended to multi-class scenarios using one-versus-all or one-versus-one strategies [4] . We then define a class of functions as follows:EQUATIONWe denote d c+ as the distance to the nearest tokens with the same label y i = c + and d c-as the distance to the closest tokens with the different label y i = c -. If d c+ is less than d c-, the instance is correctly classified. Thus, the classification margin is defined as:EQUATIONwhere a positive value indicates correct classification. Moreover, we introduce a penalty term to estimate the classification margin, defined as:EQUATIONwhere ρ > 0 is a pre-defined margin threshold.For this classifier, the risk R(f ) and the corresponding empirical risk R(f ) is defined as:EQUATIONEQUATIONWe can establish a Gaussian complexity bound by applying Theorem 7 from [4] , which holds with a probability of at least 1 -δ. This is expressed as:EQUATIONwhere C represents the Lipschitz constant, and ρ represents the margin. This formulation allows us to explicitly incorporate the prediction margin into the complexity analysis. The term G n (F) denotes the Gaussian complexity defined over the function class F, and an empirical Gaussian complexity can be estimated as:EQUATIONwhere σ = (σ 1 , σ 2 , ..., σ n ) are independent standard Gaussian random variables, σ i ∼ N (0, 1).It 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 [4] ). In our model, the token classifier leverages p tokens simultaneously; hence, it is logical to define sub-classes of F that utilize only two tokens for predictions. We define each sub-class as F ij , which specifically uses tokens p i and p j with differing labels c i ̸ = c j . Consequently, the total number of sub-classes is bounded by p • (p -1)/2. This allows us to simplify the complexity bound as follows:EQUATIONTo further simplify the bound, we must derive it for each G n (F ij ). It is important to note that F ij can be regarded as a binary classification function class for d i -d j , where the weights are bounded:EQUATIONBased on Lemma 22 in [4] , which establishes that the empirical Gaussian complexity is bounded by a kernel function defined by F ij , we can simplify the empirical Gaussian complexity of each sub-class as follows:EQUATIONThe difference between the Gaussian complexity and empirical Gaussian complexity is estimated to be ϵ with a probability of 2 • exp( -ϵ 2 n 8 ) (Theorem 11 from [4] ). We can simplify the risk as follows:EQUATIONWe 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 a 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 P T , where (T , y) ∼ P T . Thus, the vector quantization process employed in the main paper converts to a margin-based classification problem, consistent with Theorem D.2. Moreover, we can cancel the term B since the Cosine distance, used to measure the similarity between tree embeddings and tokens, ensures the bounded norm B = 1.Experimental Setting. We randomly sample node features from a uniform distribution with a dimension of 4 and conduct experiments 100 times using different seeds to report average performance.dimension is set to 64, and we use the AdamW optimizer with a weight decay of 1e-6. The pretraining learning rate is set at 1e-3 for all settings with 500 pre-train epochs, while the fine-tuning learning rate is set at 1e-2 for heterophily graphs and 5e-4 for homophily graphs. In the random feature setting, we sample node features from a 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 motifs 10,000 times, and the maximum motif size is set to 5. The maximum iteration of the subtree WL kernel is limited to 2, aligning with the number of GNN layers.Additional Results. See Table 9 for transfer learning performance on graphs with random features. Even though the node features are randomly initialized, we still observe that a high tree similarity correlates with improved transferability. We employ a GraphSAGE-like architecture to encode node and edge features in a graph G = (V, E), where node features are represented as X ∈ R |V|×d f and edge features as E ∈ R |E|×de . Considering a GNN with L layers, the (l + 1)-th layer node embedding for node v is given by:EQUATIONEQUATIONv represents the node embedding at the l-th layer, E u,v denotes the edge features between nodes u and v, and W 1 and W 2 are the learnable matrices. The function φ, used to align feature dimensions, is chosen as 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.Dataset Statistics. We utilize nine datasets from various domains and tasks, as detailed in Table 10 . 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. It 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.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 Arxiv, HIV, and PCBA, we follow the official splits, conducting experiments 10 times with random seeds to determine average accuracy. For WN18RR and FB15K237, we follow the splits outlined in Liu et al. [45] . Specifically, for FB15K237, the training set comprises 272,115 edges, the validation set 17,535 edges, and the test set 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.We compare GFT against a broad spectrum of baselines, encompassing supervised GNNs, selfsupervised GNNs, graph few-shot learning, and graph foundation models.Supervised GNNs/MLP. The supervised approaches include a basic MLP (Linear), GCN [40] , GAT [78] , and GIN [94] .Self-supervised GNNs. 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 [11] combines language models with graph neural networks in a self-supervised fashion, achieving state-of-the-art performance.Graph Few-shot Learning. To assess performance in few-shot learning scenarios, we evaluate GFT alongside methods such as GPN [15] , TENT [83] , GLITTER [82] , and TLP [71] . Experimental results are detailed in Appendix H.Graph Foundation Models. We 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 FB15K237. OFA [45] , in contrast, utilizes language models to align the feature spaces of different graphs and introduces a prompt graph to align task spaces, trained in a supervised manner.Baselines. For the baseline methods, we follow the hyper-parameters reported in [30, 45] . If specific hyper-parameters for a task are not reported, we set the learning rate to 5e-3 for Cora, PubMed, WikiCS, WN18RR, and HIV, and to 1e-4 for Arxiv, FB15K237, and PCBA. We configure all GNN encoders with two layers, a 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 to 128 with each token dimension at 768. We empirically determine the weights for different losses as β 1 = 10, β 2 = 100, β 3 = 1, and β 4 = 0.01. Additionally, we set the weight for the orthogonal regularizer, λ, to 1. AdamW is utilized as the optimizer with a learning rate of 1e-4 and a weight decay of 1e-5. The pre-training phase lasts for 25 epochs with a batch size of 1024. For data augmentation, we implement an edge drop rate and a 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-parameters for different datasets in Table 11 . λ proto and λ lin represent the weights of the losses for the prototype classifier and the linear classifier, respectively. We utilize an NVIDIA A40 with 48GB GPU memory for all experiments. Both the pre-training and fine-tuning phases can be conducted on a 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 in the main paper. The model results along with the standard deviations are presented in Table 12 . We present the extended few-shot learning performance across multiple tables: Table 13, 14, 15, 16, 17, 18, and 19. In 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 learning methods including GPN [15] , TENT [83] , GLITTER [82] , and TLP [71] . In terms of graph foundation models, we compare GFT to OFA across all datasets and to Prodigy on the Arxiv and FB15K237 datasets only, as Prodigy's application is limited to 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 a marked improvement in model performance, demonstrating significant adaptability to target tasks. Notably, even with extremely limited training instances, the model substantially outperforms the baselines, showcasing rapid adaptation capabilities. Our observations suggest that using only the target graph can still achieve desirable performance, as 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. 4 , demonstrating that all reconstruction tasks enhance model performance compared to models without pre-training. Optimal performance is achieved when three tasks are jointly optimized.Table 22 presents the ablation study on strategies for enhancing the quality of tree vocabulary, as described in Section 3.1. As previously stated, both the comprehension and expressiveness of the tree vocabulary are critical properties for its effectiveness, achieved through augmentation (aug.) and an orthogonal regularizer (ortho. reg.), respectively. We note that removing any component results in a degradation in model performance. We analyze the impact of different computation tree classification tasks for fine-tuning. The complete results are presented in Table 23 , which complements Table 4 . Specifically, GFT employs both a 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 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 in 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 domains, a 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 a 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.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 introduction.Guidelines:• The answer NA means that the abstract and introduction do not include the claims made in 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. • It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.We use text-attributed graphs in our experiments due to the data availability, and use textual encoder to align the node features, similar to Liu et al.[45]. Despite designing node feature alignment method is crucial in GFMs, it is beyond the scope of this paper.Cora & WN18RR: 1; Arxiv: 5; HIV & PCBA: 20; FB15K237: 30. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: -  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?
-  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?
questions: questions: Please see the weaknesses.
limitations: limitations: None.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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? 

2. 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? 

3. For Ltree, what are decoders used for q projection? 

4. 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? 

5. What is the definition of R(f)? 

6. 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: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: 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?
2. 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). 
3. 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.

4. 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?
questions: 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?

2. The approach in this paper is somewhat similar to the VQGraph [1]. It is worth discussing the relation and difference between the two methods.

3. 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? 


[1] Yang et al., VQGRAPH: RETHINKING GRAPH REPRESENTATION SPACE FOR BRIDGING GNNS AND MLPS, ICLR 2024.
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
2. Assumes a common feature space across different graphs, limiting its applicability to non-textual graphs.
3. The method is complex, involving a broad hyperparameter space, including computation tree parameters and the betas in Equation 3.
4. 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.
5. The distinction between the computation tree and subgraph is not clearly defined.
6. 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.
questions: questions: How are baseline results obtained? What kind of features are leveraged?
limitations: limitations: NA

Comments: title: Official Comment by Reviewer U8xo
Keep my score
Response to rebuttal
comment: Thanks for your constructive comments and for raising your score! Your review is really supportive of our work!
Thank you for the detailed response. I raise my score to 6.
Thanks for your support and constructive comments again! Your review is really helpful for our work!
I thank the authors' responses, which have addressed my concerns. I would like to keep my acceptance score.
Thanks for your constructive comments again and for raising your score! Your review is really helpful for our work!
Thanks for your constructive comments again! Your review inspires us to refine our Theorem 2.2 to have a better approximation for handling real-world graphs with different distributions in our future work!
I would like to thank the authors for their detailed reply to all my concerns. Most of my concerns are clarified after rebuttal and I would like to maintain my original score. Overall, Although after the rebuttal I still think the theoretical analysis has some flaws (particularly the neighbor part in Theorem 2.2 as graphs in different domains could indeed have very different distributions even in the real world), I do believe the merits of the paper outweigh the limitations.
I have carefully reviewed the rebuttal and the attached PDF. I appreciate the authors' efforts in addressing the weaknesses I identified.

The main concern, namely that the improvement is largely due to a better text encoder, has been mostly addressed. However, the results still fall short of my expectations. For comparison, the performance on GCN and GAT reported in [this paper](https://arxiv.org/pdf/2307.03393) is 82.20 ± 0.49 and 82.77 ± 0.59, respectively (see Table 1 for details).

The explanation provided for the GIANT performance is unconvincing and supports my earlier assumption that the experimental setup is biased toward the GFT model. GIANT was designed to train on a single graph and should be evaluated in that context.

Overall, since my primary concern has been sufficiently addressed, I have increased my score accordingly.
Dear Reviewer hEws, 

Thank you for your comments and suggestions to improve our paper, we would like to check whether our response answers your questions. Following your comments, we comprehensively discuss the experimental settings and the results obtained, and also provide a point-to-point response to all of your questions. We look forward to your reply.
Dear Reviewer M9ZQ, 

Thank you for your comments and suggestions to improve our paper, we would like to check whether our response answers your questions. Following your comments, we provide detailed responses to your questions and present a comparison to VQGraph based on your recommendation. We look forward to your reply.
Dear Reviewer U8xo, 

Thank you for your comments and suggestions to improve our paper, we would like to check whether our response answers your questions. Following your comments, we comprehensively discuss the relations and differences between computation trees and subgraphs and provide an extensive quantitative study. We look forward to your reply.
Dear Reviewer H6gM, 

Thank you for your comments and suggestions to improve our paper, we would like to check whether our response answers your questions. Following your comments, we provide more analysis on transferable structures and conduct experiments on zero-shot settings. We look forward to your reply.