GFT: Graph Foundation Model with Transferable Tree Vocabulary

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.

Strengths

1. Addresses a significant challenge (identifying transferrable patterns) in graph foundation models. 2. Includes both theoretical and empirical evaluations on synthetic and real-world graphs. 3. Conducts extensive experiments including multiple graph tasks and domains.

Weaknesses

1. The experiments are unconvincing (and most likely unfair): Only a few outdated supervised baselines are used, and their results are weaker than expected. For instance, the GCN's performance on Cora should surpass 80, and the results for GIANT on Arxiv are notably low. Are all baselines using SentenceBERT embedding? If not and the raw features are used, the improvements might be contributed to better text encoders. 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

How are baseline results obtained? What kind of features are leveraged?

Rating

5

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

NA

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.

Strengths

1. Investigating transferable tokens in graph learning is important and fundamental to the community. This paper is the first one that demonstrates the potential existence of the transferable token in text-attributed graphs. 2. The paper is well-structured with solid theoretical and experimental results to demonstrate the advantages of the proposed model.

Weaknesses

1. In Theorem 2.2, the distance bound is associated with the distance between the $j$-th neighbor of node $v_1$ and $v_2$. How to define the $j$-th neighbor related to two nodes? What if the two nodes have different numbers of neighbors? 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

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.

Rating

6

Confidence

4

Soundness

3

Presentation

2

Contribution

3

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.

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.

Strengths

a. Originality: The computation tree has been proposed in several previous works that have been adequately cited in this paper. The author reconstructs the computation tree in a new way and combines it with Vector Quantization method, effective and preventing over-fitting. b. Quality: The paper is technically sound, and the loss function proposed is comprehensive, enabling a deep understanding of the structural and semantical attribute of computation trees. The experiments in the manuscript are very comprehensive and effectively demonstrate the superiority of GFT, and important claims are well supported by theoretical analysis. c. Clarity: The manuscript is well organized and clearly written, although some descriptions could be clearer. d. Significance: The experimental results advance the SOTA methods, and the computation tree method proposed is easy for other researchers to use.

Weaknesses

It is not very clear how this work differs from previous contributions. The explanation of the superiority of computation trees over subgraphs is unconvincing because the computation tree in this paper is very different from some proposed computation trees (e.g. junction tree, H-tree, etc.) but more like the subgraph. It would be better if the author could provide detailed comparison and analysis between the computation tree and the subgraph; The quality is a bit limited. The Lfeat is to minimize the discrepancy between the local structure of a node and its feature, but is there any inherent relationship between the two? Besides, the method might not be able to deal with link prediction in a good manner. In a graph, if node va and vb are isomorphic while the links (va, vc) and (vb, vc) are not isomorphic, the vanilla GNN with the same node representations va and vb gives the same prediction to links (va, vc) and (vb, vc), but GFT does not address this issue; The clarity should be improved. The explanation for Ltree should be detailed. For example, what are decoders used for q projection? In line 269, the definition of R(f) is not given; The significance of the paper is slightly limited. It might be difficult to extend the GFT to zero-shot scenarios because the fine-tune process is necessary for GFT but it will be excluded in zero-shot scenarios.

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?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A

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.

Strengths

+ The paper is well motivated by the fact that current graph learning models lack identification of a vocabulary that can encode transferable patterns shared among different tasks and domains. Filling the gap is challenging and meaningful. + The proposed GFT model is novel. Unlike existing models, it introduces computation tree as transferable patterns and encodes general knowledge of graph into a tree vocabulary, which is new. It aims to improve the model generalization and reduce the risk of negative transfers. The theoretical analyses are also provided to support the design of GFT model, which is solid. + Extensive experiments over different graph learning tasks (e.g., node classification, link prediction, graph classification) are conducted across many datasets. The model outperforms SOTA baseline methods. As a graph foundation model, it is good to see experiments over cross-domain and cross-task datasets. Many more analytical experiments (including Appendix) are also provided, which is impressive. + The paper presentation is good. The organization is clear and easy to follow.

Weaknesses

- The proposed model assumes tree structure as transferable patterns. Besides the examples (i.e., basic blocks in Fig. 2) shown in the paper, is there any other structures transferable? It is not clear whether these patterns are transferred during the model training or not. How to demonstrate this? - 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

Please see the weaknesses.

Rating

7

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

None.

Keep my score

I thank the authors' responses, which have addressed my concerns. I would like to keep my acceptance score.