Graph Transformers for Large Graphs

We thank the reviewer for your time reading and evaluating our work, as well as highlighting the strengths of our paper. We would like to take this opportunity to justify some elements of our proposed method and explain the results as asked in your questions.

Reviewer: Despite the fluent presentation, some concerns arise in this paper. Firstly, the level of novelty in this framework appears limited. It is apparent that this paper heavily relies on the previous work, GOAT, particularly the global module, which encodes mini-batch nodes using global graph nodes. This component was introduced in a prior paper. The other aspects are mainly focused on aligning local and global features. The framework appears more like an updated version of GOAT than a fundamentally new invention.

Authors: We thank you for your question on comparison with GOAT. We would like to clarify here that GOAT’s global module is the only thing we adapt in LargeGT, while our local module is entirely different from GOAT, and addresses the bottleneck that was present in GOAT (we refer to page 7 of GOAT paper https://proceedings.mlr.press/v202/kong23a/kong23a.pdf) which explicitly claims “The neighbor sampling bottleneck is the major limitation of our method.” To contextualize this, if one were to use GOAT, the model would be severely limited when operating on large graphs. In contrast to this, our contributed model LargeGT would not be limited and would work efficiently on large graphs. To sum up, the main differences between LargeGT and GOAT are as follows: (i) LargeGT consists of a completely different local module compared to GOAT, which processes a fixed size of input tokens for local self-attention. (ii) LargeGT achieves a 4-hop receptive field through just 2-hop operations, whereas GOAT requires 4-hop operations to attain the same, often resulting in prohibitive computational costs in large graphs. (iii) The computational complexity of LargeGT is independent of the number of nodes in the graphs, unlike that of GOAT. (iv) Unlike GOAT, LargeGT implements sampling prior to training, addressing a significant computational bottleneck in GOAT’s local module.

Reviewer: Moreover, in the experimental section, the comparison between the LG transformer and other baselines reveals that the proposed framework doesn't consistently outperform GOAT-local, especially in the ogbn-products dataset. Furthermore, in the ogbn-papers100M dataset, the framework is only compared to a single baseline. It's possible that other methods struggle with extremely large graphs, but there are likely additional viable solutions that should be explored.

Authors: On ogbn-products, GOAT-local-δ shows better performance due to the dataset's homophilic nature, where local-only information aggregation is often sufficient. Conversely, for snap-patents, a non-homophilic dataset, LargeGT excels by incorporating both local and global neighbor information. This adaptability of LargeGT to different dataset characteristics explains the observed performances. We have included our observation to this regard in Section 4.2 under the heading “On Performance”. For ogbn-papers100M dataset, due to computational requirements, we compare our proposed architecture with the closest baseline which our work significantly improves, since we have provided a comparison of LargeGT with other baselines for the remaining two datasets. In other words, we use ogbn-products and snap-patents to verify our proposed model against a wide range of baselines, while for ogbn-papers100M, the objective translates to showing that it scales to such a dataset and also provides improved performance.

Reviewer: Additionally, the fusion of transformers and Graph Neural Networks (GNNs) is a dynamic research area with various ongoing studies, such as TransGNN and Graphformers. It would be valuable to understand how these methods perform when confronted with similar tasks.

Authors: We thank you for highlighting this connection, and refer to Section 2 in our paper where we have reviewed the classes of works on MPNNs scaling and Graph Transformers while sharing their respective limitations which build the motivations of our architecture. To summarize the key points here again: Fusions of GNNs with Transformers have produced several powerful Graph Transformer (GT) models, Graphormer being one of this class. However, an obvious barrier for GTs to scale to large graphs is the quadratic complexity brought by full-graph attention, i.e., O(N^2), with N being the number of nodes in a graph. There are other solutions which inject an extent of sparsity in the GTs to bring the quadratic complexity down, which work well on medium scale graphs. Yet, those remain unscalable on single large graphs due to the entire graph structure being operated upon.

We thank the reviewer for your time reading and evaluating our work, as well as pointing out our strengths. We would like to take this opportunity to justify some elements of our proposed method and answer your questions on baselines, experiments and the contribution with respect to the literature.

Reviewer: Baselines: LargeGT is compared to "constrained versions" of various baselines, notably all models are constrained to 2 hops only, while LargeGT has access to 4-hops worth of neighbors (in the local module). Including the non-constrained versions of these same baselines is critical for evaluation, even if they are more computationally demanding. Currently it is unclear whether adopting LargeGT leads to lower performance compared to state-of-the-art methods, at the expense of computational efficiency.

Authors: We appreciate your feedback on the selection of baselines for comparison. The decision to compare LargeGT with 2-hop constrained versions of various models was initially to maintain a consistent scope of expensive computation incurred across all models. For instance, the cost of fetching l-hop neighbors for a node in a very large graph would be the same and agnostic of any selected model. Nevertheless, below is a comparison of the baselines along with LargeGT scores on ogbn-products without restriction to 2-hop. For instance, GOAT models are run with original hyperparameters which samples 20, 10, 5 neighbors at the 3 hops.

We can observe that the best performing model remains the same while LargeGT (in both cases uses up to 2 hop operations) remains better and competitive compared to the best performing model. In the revised manuscript, we have included a section Appendix A.4 which details these comparisons to provide a clearer perspective on LargeGT's performance relative to state-of-the-art methods.

Reviewer: Additionally, no auxiliary label propagation or augmentations are used for the baseline methods, when they are used in methods reported in the OGB leaderboard. These enhancements are not altering the receptive field of the baselines, and thus shouldn't impact computational performance, but might improve classification performance. This should be taken into account when comparing with approaches that might still outperform the proposed method, even under constrained training (2-hop).

Authors: Thank you for pointing out the absence of auxiliary label propagation or augmentations for baseline methods. We acknowledge that including these enhancements could have a chance to provide improved performance for specific models. However, it has been observed in the leaderboards that the composition of several enhancement techniques blurs the dissection on which model components are critical and contributes highly to the performance of a model. For example, a label propagation technique known as Correct & Smooth (C&S) [1] is employed in various models on the OGB leaderboard for ogbn-products [2]. It demonstrates that MLP-based models with C&S perform both better and worse than TransformerConv [3] in different settings. This provides a somewhat blurred perspective on whether MLP or Transformer models are superior for ogbn-products from a neural network perspective. We mention our reasoning in Section 4.1 while GOAT, which we closely follow, also follow a similar experimental setting on not using enhancement tricks.

[1] Huang, Q., He, H., Singh, A., Lim, S.N. and Benson, A.R., 2020. Combining label propagation and simple models out-performs graph neural networks.
[2] https://ogb.stanford.edu/docs/leader_nodeprop/#ogbn-products.
[3] Shi, Y., Huang, Z., Feng, S., Zhong, H., Wang, W. and Sun, Y., 2020. Masked label prediction: Unified message passing model for semi-supervised classification.

We thank the reviewer for your time reading and evaluating our work, as well as pointing out the strengths of our paper. We would like to take this opportunity to clarify some elements of our proposed method and provide answers to your questions.

Reviewer: The efficiency analysis is incorrect. In Algorithm 1, it is required to gather 1/2-degree neighbors for each node, and then select k nodes. The process of selecting nodes is O(K), but if the graph is relatively dense, the complexity of gathering second-degree neighbors is O(N^2).

Authors: We appreciate your critical assessment of the efficiency analysis. The concern regarding the complexity of gathering second-degree neighbors in dense graphs is valid. However, Algorithm 1 is an offline step and does not affect the runtime during training and/or inference. We have written more on this under the heading “Offline Step Prior to Training” in Section 3.2. Our computational complexity analysis in Section 3.2 is based on the neural network module – local module and global module (Fig 1) — runtimes as usually done in the literature when reporting the computational complexity of a neural network layer. We have included a clarification on the complexity analysis of the offline step and of the LargeGT modules in our revised manuscript.

Reviewer: In Algorithm 1, some nodes are sampled with replacement, while some are sampled without replacement. It is uncertain whether this will introduce bias in the sampling.

Authors: Thank you for highlighting this aspect of our sampling method in Algorithm 1. We take this opportunity to clarify that the “sampling with replacement” only applies to those nodes whose 1 and 2 hop neighbors are less than K-1. This becomes a corner case and applies to only a small fraction of the nodes in general. As such it does not bias how we perform our overall sampling, except that we apply special handling of the nodes with lesser neighbors than K-1 . It is true that such corner cases can be handled differently as well, such as using padding nodes, instead of sampling with replacements.

Reviewer: It lacks some key baselines such as SGC[1], SIGN[2].

Authors: We thank you for pointing out the absence of comparisons with baselines like SGC and SIGN. The decision to exclude these baselines initially was based on their different focus compared to LargeGT. However, aspects of these works are closely related such as “offloading heavy computations away from the training stage” which we also follow in Algorithm 2 in the form of “Hop context features” . While we had already included SIGN in Section 2 of our paper, we have now also included SGC in the revised manuscript. This addition falls under the collection of related works that 'perform information propagation prior to the training stage', aiming to reduce the training cost of GCNs."

Authors: We hope our answers have addressed your concerns. Let us know if you have any other questions or concerns. In light of our answers to your concerns, we hope you consider raising your score. If you have any more concerns, please do not hesitate to ask and we'll be happy to respond.

We thank the reviewer for your time reading and evaluating our work, as well as highlighting the strengths of our paper. We would like to take this opportunity to justify some elements of our proposed method and explain the results as asked in your questions.

Reviewer: (In Summary of the review) “... Neighborhood sampling usually samples at most 2-hop neighbors as in GOAT (Kong et al., 2023).. ”

Authors: We would like to clarify that GOAT’s method DOES NOT usually do 2-hop sampling. In fact, their experiments use a 3-layer or 3-hop sampling, with an equal hop of receptive field. In our method, we perform at most 2-hop sampling and achieve a receptive field of 4-hop by the use of each sampled nodes’ 1-hop and 2-hop context features that are pre-computed offline (Figure 1; Algorithm 2). As such, we have an efficient sampling technique as a contribution as presented in the paper.

Reviewer: The mechanism of why LargeGT runs faster than baselines like GOAT is unclear. Since the proposed neighbor sampling has a bigger input matrix than a simple 2-hop neighbor sampling method, does it run longer than the traditional method?

Authors: There are two reasons for this. (i) Conceptually, LargeGT runs faster than baselines like GOAT due to the introduction of our local sampling technique that is performed offline and is restricted to 2-hop neighbors, as opposed to GOAT which performs sampling during mini-batching and frequently uses 3+ hop in practice. (ii) Experimentally, in our paper, we keep 2-hops for LargeGT and GOAT-δ. In such a case, the efficiency in LargeGT comes from the fact that these 2-hop neighbors are sampled offline and not during mini-batching. Although we have discussed the characteristics of LargeGT in terms of “Scalability” in Section 3 under the subheading “Characteristics of the framework”, we will elaborate further on these points in the revised manuscript for clarity. Additionally, the computational complexity of global module in both LargeGT and GOAT are the same. However, GOAT’s local module is dependent on the number of nodes in a graph and the sampling hop length, unlike LargeGT’s local module, which enables LargeGT to scale better. We refer to GOAT’s paper where they highlight their local module as a major limitation which is addressed in our work as part of our contribution.

Reviewer: The runtime highly depends on the hyperparameter K, which is the number of nodes for sampling. Authors need to provide a fair and solid comparison with the traditional 2-hop neighbor sampling method.

Authors: Since the computational complexity of LargeGT’s local module is dependent on K, the runtime depends on K. We would like to refer to Figure 1 and Eqns. 1-6 in our paper (further in Appendix A.2) which informs that the hyperparameter K determines the size of node sampled “prior to training” as well as the number of tokens for LargeGT’s local module, which is 3K (see “Complexity” in Section 3). As such, the hyperparameter K will influence the size of the data (or input tokens) the local module is operating on, thus affecting the runtime. Our sampling method prior to training is random sampling as outlined in Algorithm 1 – similar to how traditional sampling method is used. The only difference, say with GOAT’s sampling method or other similar sampling methods, is that Algorithm 1 is executed offline, as illustrated in Section 3 (“Offline Step Prior to Training”); while GOAT’s sampling is done during mini batching. In addition, unlike the sampling performed during mini-batching, Algorithm 1 paves the way for parallelizing the sampling of each graph on distributed computing resources.

Reviewer: In Table 2, why does GOAT-local-δ have better accuracy in ogbn-products? For snap-patents in Table 2, why does LargeGT have much better model accuracy than all baselines?

Authors: Thank you for pointing out these key observations from our experiments. On ogbn-products, GOAT-local-δ shows better performance due to the dataset's homophilic nature, where local-only information aggregation is often sufficient. Conversely, for snap-patents, a non-homophilic dataset, LargeGT excels by incorporating both local and global neighbor information. This adaptability of LargeGT to different dataset characteristics explains the observed performances. We have included our observation to this regard in Section 4.2 under the heading “On Performance”, which we will revise for more clarity in our next revision.