Graph Transformers for Large Graphs

Venue: KDD_org_2024_Workshop_DL4KG
Published: 2024-05-28 04:12:26

Abstract: Transformers have recently emerged as powerful neural networks for graph learning, showcasing state-of-the-art performance on several graph property prediction tasks. However, these results have been limited to small-scale graphs, such as ligand molecules with fewer than a hundred atoms, where the computational feasibility of the global attention mechanism is possible. The next goal is to scale up these architectures to handle very large graphs on the scale of millions or even billions of nodes. With large-scale graphs, global attention learning is proven impractical due to its quadratic complexity w.r.t. the number of nodes. On the other hand, neighborhood sampling techniques become essential to manage large graph sizes, yet finding the optimal trade-off between speed and accuracy with sampling techniques remains challenging. This work advances representation learning on single large-scale graphs with a focus on identifying model characteristics and critical design constraints for developing scalable graph transformer (GT) architectures. We argue such GT requires layers that can adeptly learn both local and global graph representations while swiftly sampling the graph topology. As such, a key innovation of this work lies in the creation of a fast neighborhood sampling technique coupled with a local attention mechanism that encompasses a 4-hop reception field, but achieved through just 2-hop operations. This local node embedding is then integrated with a global node embedding, acquired via another self-attention layer with an approximate global codebook, before finally sent through a downstream layer for node predictions. The proposed GT framework, named LargeGT, overcomes previous computational bottlenecks and is validated on three large-scale node classification benchmarks. We report a 3× speedup and 16.8% performance gain on ogbn-products and snap-patents compared to their nearest baselines respectively, while we also scale LargeGT on ogbn-papers100M with a 5.9% improvement in performance.

Main paper: 
 introduction: 
 Transformer networks (Vaswani et al., 2017) have revolutionized representation learning in various domains, particularly in the field of natural language processing (Devlin et al., 2018; Liu et al., 2019; Yang et al., 2019; Raffel et al., 2020; Brown et al., 2020; Dosovitskiy et al., 2020; Touvron et al., 2023; OpenAI, 2023) . Their unique ability to model intricate all-pair dependencies in sequential data (or sets of data tokens) has sparked interest in extending Transformer architectures beyond just sequential data, leading to promising research in the area of graph representation learning (Zhang et al., 2020; Dwivedi & Bresson, 2021; Kreuzer et al., 2021; Mialon et al., 2021; Ying et al., 2021; Rampášek et al., 2022; Shirzad et al., 2023) . However, these advances are not without their challenges. As graph-based learning tasks grow more complex and the scales of the graph data increase, the limitations of current Graph Transformer (GT) architectures become increasingly evident (Zhao et al., 2021; Chen et al., 2022; Kong et al., 2023) .On the other hand, traditional message-passing neural networks (MPNNs), including variants like GCN (Kipf & Welling, 2016) , GAT (Veličković et al., 2018) , and GatedGCN (Bresson & Laurent, 2017) , function effectively on small-scale graphs such as molecular structures, operating in the order of O(E), or O(N ) for sparse graphs (Gilmer et al., 2017) . However, their efficiency rapidly decreases when applied to larger graphs with even less than a million nodes. This is primarily because MPNNs consider all neighbors during their aggregation and update steps. To mitigate this, some approaches use neighborhood sampling (NS) to limit the number of sampled neighbors for each node up to a certain number of hops (Hamilton et al., 2017) . While this method keeps computational costs in check, it encounters intractability issues when the graph scales to hundreds of millions of nodes or more. Moreover, even if NS is computationally feasible for two or three hops, the MPNNs become confined to capturing only highly localized information, which might be insufficient for tasks on large graphs where more global context is crucial (Lim et al., 2021; Dwivedi et al., 2022; Kong et al., 2023) .Graph Transformers (GTs) could provide a potential solution, given their ability to model long-range dependencies and attend to global neighborhoods (Rampášek et al., 2022) . However, the intractability remains, given that GTs with all-pair attention, i.e., each node attending to every node, would be quadratic (O(N 2 )) computationally. When applied with NS, GTs inherit the same limitations, confining their effectiveness to localized regions. Without NS, the task of attending to global neighborhoods necessitates approximation (Wu et al., 2022; 2023; Shirzad et al., 2023) or sampling (Zhao et al., 2021; Zhang et al., 2022; Zhu et al., 2023) for computational feasibility, thus bringing us back to the original challenges of sampling and (in)efficient access to global information.Present Work. In this paper, we introduce a comprehensive approach to overcoming the aforementioned critical challenges in learning on large-scale graphs by focusing on two essential design principles: model capacity and scalability. We enhance model capacity by integrating both local and global graph information for building node representations, while ensuring scalability with an efficient sampling approach. The proposed framework is summarized as follows:1. Framework Design: We present LargeGT, a new framework that integrates both local and global graph representations while minimizing the computational cost incurred at both the stages.In consistency with recent working recipes in graph learning (Rampášek et al., 2022; Kong et al., 2023) LargeGT utilizes two distinct modules -LOCALMODULE and GLOBALMODULE -to handle local and global information exchange efficiently.2. Localized Representations: Within the LOCALMODULE, we present a novel tokenization strategy that prepares a fixed set of tokens for each graph node to be processed by a Transformer encoder, resulting in rich local feature representations. Importantly, this mechanism leverages a neighborhood sampling approach that consists of an offline sampling stage and incorporates local context features, enabling a broad 4-hop receptive field through just 2-hop operations. 
related work: 
 Challenges in MPNN Scaling. When learning on large graphs, the principal issue faced by message-passing based graph neural networks (MPNNs) is the neighbor explosion phenomenon (Hamilton et al., 2017; Zhao et al., 2021) , since the neighborhood sets of nodes at successive hops expand exponentially (Alon & Yahav, 2021) . Early efforts in scaling MPNNs employed the use of neighbor sampling (NS) to sample neighbors of nodes in a graph recursively that reduces the overall neighborhood sets sending messages for nodes' feature updates (Hamilton et al., 2017) . While this brings a reduction in memory and compute footprint, the MPNN is still intractable to (i) aggregate information at hops greater than 2 or 3 in very large graphs due to the fact that the the size of the successive neighborhood grows exponentially, and (ii) access global information in the graph, which is also a well-acknowledged limitation for several works along this line (Chen et al., 2017; 2018; Huang et al., 2018; Zeng et al., 2019) . Information propagation prior to or after the training stage (Gasteiger et al., 2018; Wu et al., 2019; Frasca et al., 2020) are also adopted as ways to address the intractability brought by neighborhood explosion, which follow the aforementioned limitations.Several works also propose pre-training (Han et al., 2022) or distillation strategies (Zhang et al., 2021; Guo et al., 2023) to mitigate these impacts.Graph Transformers and Scalability. The apparent access to global information is a driving factor behind the recent plethora of works on Graph Transformers (GTs) with all pair attention (Ying et al., 2021) . We refer to Müller et al. (2023) for a detailed taxonomy and component-wise study of GTs. 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. The use of sparse Transformers (Rampášek et al., 2022; Shirzad et al., 2023) or approximated global attention Wu et al. (2022; 2023) alleviate this issue to some extent to bring down the complexity to sub-quadratic.Yet, these methods remain unscalable on single large graphs due to the entire graph structure being operated upon. In order to address this limitation, either NS-like computational boundary is enforced for each node (Shi et al., 2020; Zhao et al., 2021) or a fixed length sequence or set is prepared for each node prior to training (Zhang et al., 2020; Chen et al., 2022) . Such solutions either inherit the limitations of NS as discussed above, or face infeasibility due to adjacency matrix multiplications as the graph size grows larger.Clustering based GTs. Orthogonally, several recent works use hierarchical clustering or partitioning to perform global attention on the coarsened or super nodes (Zhang et al., 2022; Zhu et al., 2023) . However, the coarsening step remains intractable for very large graphs with sizes in hundreds of millions or more. Finally, Kong et al. (2023) use a combination of NS based local module and a global module consisting of a trainable fixed-sized codebook that represents global centroids. While the sampling limitations remain, the global module based on the centroids is efficient and something that we consider in our proposed approach to compute global representations. 
global representations:: 
 For the GLOBALMODULE, we implement an approximate codebookbased approach, adapted from Kong et al. (2023) , to enable global graph attention with computational complexity linear to the codebook size. This design choice ensures that both modules can operate independently of the graph size, thereby ensuring scalability.4. Computational Efficiency: Our approach effectively mitigates computational bottlenecks traditionally associated with sampling techniques and global information flow. As a result, we enable incorporation of both local and global graph representations without compromising performance.In the previous sections, we identified critical limitations in existing graph learning models, specifically their inability to effectively merge local and global graph features when working with very large graphs. While MPNNs struggle with the 'neighbor explosion' problem, making it difficult to aggregate information beyond 2-3 hops GTs can capture global context, but are hampered by quadratic complexity in full graph attention. These challenges, although formidable, outline the essential criteria for a successful GT model tailored for large graphs. This leads us to present a recipe focusing on model capacity and scalability for building GTs for large graphs. In this section, we first discuss the design principles of model capacity1 and scalability. These factors play a crucial role in determining the design and feasibility of a Graph Transformer, particularly when it comes to managing extremely large graphs that have node counts in the millions or higher. Finally, following the design characteristics, we introduce our proposed framework -LargeGT.D1-Model Capacity. A graph learning model should possess the ability to incorporate both local and global information from the original large graph.Local Inductive Bias: A node's local connectivity presents a rich source of information that is essential to utilize even in a large graph setting. A straightforward local aggregation of all neighboring nodes followed by update equation in an MPNN is impractical due to which several works utilize sampling techniques (as discussed in Section 2). The incorporation of such local information, while remaining in a feasible computational boundary, is a key ingredient when building a graph learning model for larger graphs and helps immensely in homophilic tasks (Ma et al., 2021; Mao et al., 2023) .Access to Non-Local Information: A node's capability to incorporate features beyond near-local neighbors may be vital for long-range or non-homophilic tasks (Lim et al., 2021; Dwivedi et al., 2022) . The sampling strategies discussed in Section 2 fail to allow a model to access nodes' distant hops or global information, motivating the use of GTs (Rampášek et al., 2022; Shirzad et al., 2023) . GTs with all-pair attention alleviate this concern, however not all such mechanisms reviewed in Section 2 are scalable, which is a key concern. The recent global attention mechanism proposed in GOAT (Kong et al., 2023) uses dimensionality reduction scheme serving as a "conceptual" global context for a node to attend when looking for non-local information. Without exhaustive computation, a large graph learning model should allow access to global graph context (Cai et al., 2023) .D2-Scalability. Learning on large graphs become infeasible for several existing models due to hindrances in sampling mechanisms or global information modules (Ying et al., 2021; Rampášek et al., 2022; Zhao et al., 2021) . As such, we consider the following factors to be vital for computational feasibility and ensuring scalability of the GTs when graphs grow larger.Efficient Neighbor Node Set Retrieval: As reviewed in Section 2, despite the use of sampling techniques, it becomes intractable to retrieve neighbor node sets from hops greater than two or three if the graph in consideration is very large (Zhang et al., 2021; Guo et al., 2023) . In fact, even a third hop neighbor set retrieval takes a significant amount of time for graphs with hundreds of millions of nodes, as the computational complexity of retrieving a node's l hop neighborhood is O(d l ), where d is the average node degree. Therefore, for efficient retrieval for large graphs, we establish only two hops retrieval as a key constraint; this limit is commonly adopted in large-scale graph learning applications (Sankar et al., 2021; Ying et al., 2018; Tang et al., 2022) .Efficient Global Information Access. As much as the significance of global information is discussed as a key recipe in the Design D1, we reiterate that the global information flow should come at an inexpensive cost. There are multiple candidates for an efficient access to global information, such as sparse global attention (Shirzad et al., 2023) , use of virtual nodes (Cai et al., 2023) and use of an approximate centroid-based codebook (Kong et al., 2023) . Since we focus on large graphs where the former two candidates can be infeasible due to their dependency on the number of nodes in the graph, we aim for incorporating global information without bottlenecks due to a graph's large size, such as the method implemented in Kong et al. (2023) which depends on a dynamic codebook comprising of global centroid tokens.Distributed Training. Handling very large graphs will be impractical without taking advantage of the distributed computing infrastructure in which several of the real world graphs occur, eg. social networks, which are massive and are generally distributed over different machines. Ensuring efficient run times during both training and inference is vital to allow a GT to handle large graphs within acceptable time frames, keeping the cost feasible and lower. For a model to scale on large graphs, the training steps should do away with the bottlenecks brought by traditional MPNNs and sparse GTs. For instance, MPNNs usually sample nodes and their neighbors during the mini-batching step of the training process, which also applies in recent GTs (Zhao et al., 2021; Kong et al., 2023) . In principle, this translates to maintaining the adjacency matrix of a graph in one machine. This can be challenging given an example that a simple 3-layer GraphSAGE with NS requires around 350GB+ RAM on the 111.1M sized ogbn-papers100M following standard configurations of OGB Hu et al. (2020) . The single-machine memory requirement can be much larger than the availability on standard machines with on sophisticated models and on industry-scale graphs with billions of nodes and edges (Shi et al., 2023; Ying et al., 2018) . Thus, avoiding the need to maintain the entire graph data on a single machine when learning is desirable.Incorporating these desiderata jointly, we next introduce our proposed framework, LargeGT which is designed from first-principles to enable the application of GTs to massive large-scale graphs. We refer to Figure 1 for a sketch of the proposed architecture.Notations. We denote a given graph with G = (V, E) with V being the set of nodes and E the set of edges, and N = |V| and E = |E| being their cardinalities. The graph structure is represented by the adjacency matrix A ∈ R N ×N where A ij = 1 if there exists an edge between nodes i and j, otherwise A ij = 0. The features for a node i is denoted by H i ∈ R 1×D and for all nodes in the graph G is denoted by H ∈ R N ×D While we assume, for simplicity, that the graph G has no edge features, these can be incorporated using standard methods as done in the literature, such as using edge features during message passing to update node representations.Update Algorithm. We now define the equations which update the feature representations of a node using the LargeGT framework. Given a node i with its input feature H in i ∈ R 1×Din , the aim is to obtain its output features H out i ∈ R 1×Dout which can be passed to appropriate prediction heads and/or loss functions, subsequently, depending on the learning task. For simplicity, we will representEQUATIONEQUATIONEQUATIONEQUATIONEQUATION6) where, S i reflects the K sampled local nodes from LOCALNODES in Algorithm 1, and X i is the set of input tokens of size 3K prepared using INPUTTOKENS in Algorithm 2. Additionally, LO-CALMODULE consists of a standard Transformer encoder (Vaswani et al., 2017) which could be a stack of multiple layers to produce each token's representations, with a readout function at the end that converts the set of tokens to one feature vector as sketched in Figure 1 , and GLOBALMODULE consists of a single layer Transformer encoder adapted from Kong et al. (2023) that allows a node to attend to an approximate global representation of all nodes in the graph through a projection of all nodes' features in a codebook of a fixed size, that is updated at each iteration (see Section A.3). || denotes concatenation. C ∈ R N ×2×D is the context feature matrix which provides the 1 and 2 hop neighborhood context for all nodes in the graph and can be precomputed asC 0 = ÃH ∈ R N ×1×D and C 1 = Ã2 H ∈ R N ×1×Dwhere Ã is the normalized adjacency matrix (Chen et al., 2022) .Algorithm 1 LOCALNODES: Algorithm to fetch a multiset of local nodes from 1 and 2 hop neighbors for each node.Require: A graph with adjacency matrix A ∈ R N ×N , and the size of the multiset K. Ensure: Return the matrix with K-sized multisets for each node S ∈ R N ×K 1: Initialize: Multisets for all nodes S ∈ R N ×K 2: for i = 0 to N -1 do 3:T ← 1 and 2 hop neighbors of node i4: if | T| ≥ k -1 then 5: T ← Randomly sample K -1 nodes from T 6: else if | T| < K -1 and | T| > 0 then 7:T ← Randomly sample from T with replacement to make K -1 nodes 8: else 9:T ← Randomly sample K -1 nodes from {0, 1, 2, . . . , N -1} 10:end if 11:Si ← {i} + {T} ∈ R k 12: end for Algorithm 2 INPUTTOKENS: Algorithm for Mini-Batch Preparation for Local Module Require: Mini-batch of M samples S ∈ R M ×K where K is the total size of the multiset of nodes for each node, Feature matrixH ∈ R N ×D , Hop context features C ∈ R N ×2×D . Ensure: Return the input data of all nodes in mini-batch X ∈ R M ×3K×D . 1: Initialize: X ∈ R M ×3K×D 2: for i = 0 to M -1 do 3:for j = 0 to 3K with step 3 do 4:Xi,j ← H[Si,j] # node feature for node i from the feature matrix H 5:Xi,j+1 ← C[Si,j, 0] # 1 hop context feature for the node i from C 6:Xi,j+2 ← C[Si,j, 1] # 2 hop context feature for the node i from C 7:end for 8: end for Finally, FFN refers to a feed forward network used in Transformers, and NORM is normalization, which can be either of LayerNorm (Ba et al., 2016) or BatchNorm (Ioffe & Szegedy, 2015) . Additionally, we note here that the Algorithms 1 and 2 are defined for either all nodes or a mini-batch of nodes, while their respective outputs can be accessed index-wise in the above Eqns. 1 and 2.Step Prior to Training. The Algorithm 1 LOCALNODES is run on CPU prior to the training to sample local nodes for each node in the graph, and can be parallelized to multiple cores or machines. The parallelization is possible due to the fact that the fetch of 1-hop and 2-hop neighbors in Step 3 and the subsequent steps of Algorithm 1 is independent for each node and can be executed on different CPU cores in parallel. It's also worth mentioning that the graph is not required to be stored on a single machine's memory for this step. In line with our design principles, the graph can be distributed across multiple machines using techniques such as key-value stores or graph databases to circumvent the issue of memory limitations. This ensures that the offline step aligns with the scalability considerations of handling very large graphs.Mini-Batching for Local Module. The Algorithm 2 abstracts a mini-batching stage during the training, which prepares the input tokens for each node in the mini-batch with M node samples. This process contains a nested loop that can also be heavily parallelized across available cores. The mini-batch algorithm is implemented in a dataloader's preparation function, such as the PyTorch DataLoader collate (Paszke et al., 2019) . Besides, an important feature provided by INPUTTO-KENS is that it increases the receptive field of a node up to 4 hops, based on just 2-hop computations. To illustrate this, consider a node with its K sized sampled set of 1-hop and 2-hop neighbors. Since the steps 5-6 in Algorithm 2 allows for a nodes' 1-2 hop neighbors to retrieve their 1-hop and 2-hop neighborhood context, the node i in consideration will have access to information from up to 4 hops. We have included further elaboration of this feature in Figure A.2 in Section A.2.Characteristics of the Framework. The LargeGT framework fulfills the desired characteristics (D1-D2, Section 3.1) for a graph learning model to scale on large graphs. D1-Model Capacity: By incorporating both a local and global module, LargeGT can build node representations using information from local neighborhoods as well as global graph context. The local module leverages offline neighbor sampling and local context features to efficiently aggregate local structure up to 4 hops while the global module allows attending to the entire graph through a trainable codebook. D2-Scalability: The framework only samples up to 2-hop neighbors for each node, ensuring efficient neighbor set retrieval. The runtime is also efficient as the local module operates on sampled neighbors and the global module utilizes a fixed size codebook, which is already efficient as demonstrated in Kong et al. (2023) . Similarly, the offline neighbor sampling step allows the local node sets and neighborhood contexts to be prepared independently of the graph structure, essentially converting the graph learning task into a standard neural network training problem on the sampled nodes and contexts. This allows easy parallelization across machines like for other modalities such as image and text, alleviating bottlenecks caused in traditional GNN training that require adjacency matrix access on each machine, in principle. The input token preparation is also independent of the graph structure. In summary, LargeGT satisfies the key design principles of model capacity and scalability to effectively scale on large graph datasets. The local and global components allow it to learn both from local structure as well as model global dependencies in the graph, without any explicit bottleneck caused due to the size of a graph. In the next section, we will demonstrate that this model is not only scalable, but offers strongly competitive performance.Complexity. The computational complexity of the LOCALMODULE in LargeGT is O((3K) 2 ), while that of the GLOBALMODULE is O(B) where K is the size of the local nodes, 3K is the size of the tokens for the LOCALMODULE and B is the size of the codebook in GLOBALMODULE. As such, the framework is not bottlenecked with the size of nodes in the graph, as in prior literature. Note that the complexity of Algorithm 1, which is a one-time offline step, does not affect the computational complexity of LargeGT. 
datasets and experimental setup: 
 Datasets. We evaluate the proposed LargeGT model architecture on single large graph datasets with node classification tasks. Since we particularly focus on large graphs, we do not conduct evaluations on smaller benchmarks with lesser than million nodes as the limitations of scaling a model are not present. We use ogbn-products and snap-patents for our model prototyping and experiments, while we also scale our model on ogbn-papers100M. The datasets' summary is presented in Table 1 . ogbn-products is a dataset containing Amazon co-purchasing network (Bhatia et al., 2016) with nodes representing products and edges representing the products being purchased together. We use the Open Graph Benchmark (Hu et al., 2020) version of the dataset with their standard splits and available features. snap-patents is a network of US patents (Leskovec & Krevl, 2014) where each node represents a patent and an edge represents patent nodes which cite each other. We use the snap-patents dataset from Lim et al. (2021) with their default splits and features. Finally, we use ogbn-papers100M dataset (Hu et al., 2020) which is one of the largest publicly available single large graph benchmarks. Nodes in the graph denote an arXiv paper while directed edges denote papers which cite other papers (Wang et al., 2020) . As with the former dataset, we use the default splits and features provided by OGB. Among the three datasets, snap-patents is a non-homophilic dataset, while the rest are homophilic.Scalable Baselines. We design our experiments in a way to ensure scalability with efficient neighbor node set retrieval (D2, Section 3.1) on large graphs, with sizes even beyond the benchmarks we use for the demonstration in this work. As such, we use constrained versions of existing MPNNs or GT baselines, denoted by Model-δ and call them 'Scalable Baselines'. We select GraphSAGE (Hamilton et al., 2017) , GAT (Veličković et al., 2018) , GT-sparse (Shi et al., 2020; Dwivedi & Bresson, 2021) , NAGphormer (Chen et al., 2022) and GOAT (Kong et al., 2023) as the baselines which encompass fundamental GNNs as well as recent scalable GTs. Following D2, we constrain the graph propagation related operations in all these baselines to 2 hops only. The goal of our exper- GOAT-full-δ 61.12±0.10LargeGT-full 64.73±0.05imental setup is to show how the scalability constraints affect existing models' capabilities, which can be addressed by LargeGT; for this reason, we do not use enhanced techniques for obtaining top leaderboard results such as auxiliary label propagation (Shi et al., 2020; Huang et al., 2020) or augmentations (Kong et al., 2020) . We apply similar restrictions in our proposed LargeGT as well.For hyperparameters, architectural and training setup of the baselines, we adopt the hyperparameters available in the original model papers or the OGB examples repository (see Section A.5). We refer to Section A.4 for a comparison of scalable and original baselines.LargeGT Models. We train and evaluate two versions of LargeGT in our experiments, denoted as LargeGT-local and LargeGT-full. In local version we omit the GLOBALMODULE (Eqn 4) and only use local representations in Eqn. 5. In the full version, we use both the local and global modules and follow the entire formulation as in Eqns. 1-6. We implement single layer of Transformer encoder in the local and global modules. 2 Other hyperparameter details are included in Section A.5.We now present the numerical results in this section. Table 2 presents the main comparison of the baselines Model-δ with the LargeGT models. For ogbn-papers100M, we only report the best performing baseline on the homophilic task of ogbn-products due to computational constraints. Figure 2 shows the training time per epoch incurred by the models, while Figure 3 shows the sensitivity analysis of the number of nodes sampled (K) in Algorithm 1 which is used by LOCALMODULE in LargeGT. We present our observations as follows.On Performance. On comparison with the scalable baselines in Table 2 consisting of both GNNs and GTs, we observe LargeGT to attain competitive performance to the best baseline GOAT-localδ on ogbn-products, while on snap-patents, LargeGT beats all the baselines. The lower scores of GraphSAGE-δ and GAT-δ models reveal, in part, how the constraint D2 brings down the model capacity and such a network with a 2-hop graph receptive field may not incorporate necessary information required to build useful node representations. Among all the models on ogbn-products, GOAT-local-δ is the best performing, which on snap-patents ranks the lowest, understandably due to the latter's non-homophilic characteristic where local-only information aggregation may not be enough. All results considered, LargeGT ranks among the best models on both the datasets, suggesting the capacity to work well in both homophilic and non-homophilic settings. Finally, we report the results of LargeGT-full on ogbn-papers100M together with GOAT-full-δ which is the best performing baseline on a similar homophilic task ogbn-products on a computational budget of 48h. We observe LargeGT-full to be significantly better (5.9%) in performance compared to GOAT-full-δ, hence showing the ability to scale to massive graphs.On Design Characteristics. The scores of LargeGT indicate the need to incorporate both local and global neighbor information, as well as the suitability of such architecture to perform both in homophilic and non-homophilic tasks. The absolute gain in performance of LargeGTfull against LargeGT-local which is around 1% and 2% respectively for ogbn-products and snap-patents demonstrates how LargeGT satisfies D1 design characteristic. D2 which ne- On Node set sizes K. In Figure 3 , we show results of LargeGT-full experiment on an important hyperparameter in our proposed framework, the number of nodes to be sampled from LOCALNODES (Algorithm 1). The value of K is chosen from a list of [20, 40, 50, 60, 80, 100, 150, 200] . We observe best performance on K = 100 and K = 50 for ogbn-products and snap-patents respectively, which somewhat aligns with the extent of their tasks being non-homophilic since a lower K would reflect lesser tokens from the local neighborhood.  
empirical validation:: 
 We validate the competitiveness and scalability of LargeGT with baselines in a scalable setting using ogbn-products, snap-patents and ogbn-papers100M datasets which are among the largest benchmarks with node in ranges 2.5M, 2.9M and 111.1M, respectively. Notably, we obtain a 3× speedup and 16.8% performance gain on ogbn-products and snap-patents compared to their best baselines respectively, while on ogbn-papers100M we scale LargeGT with a 5.9% improvement in performance.Overall, our work not only investigates on the key challenges and presents design elements for GTs at scale but also provides a robust framework for future research in this area.In this work, we propose the LargeGT framework for designing Graph Transformers on very large graphs, such at those with at least millions nodes. We studied the characteristics and constraints necessary for a learning model to effectively scale on large graphs, namely model capacity, computational feasibility, and distributed training ability. We design LargeGT to satisfy the intended criteria, and show a proof of concept of how these components can be incorporated into a GT model to obtain competitive results in an improved runtime compared to architectures in prior literature.Further research. In our LargeGT framework, we focus on key design elements that offer both a robust model and the ability to scale on large graphs. We believe some features of this framework are worth further study. The main goal of this work is to demonstrate the core components like the sampling and tokenization steps (LOCALNODES, INPUTTOKENS), as well as the update modules (LOCALMODULE, GLOBALMODULE). However, these can be further optimized for specific types of graphs. For instance, our current tokenization approach allows a wide 4-hop receptive field through simpler 2-hop operations. Yet, other sampling techniques could be more efficient in capturing complex relationships. Same applies for exploration on GLOBALMODULE's efficiency.We build LargeGT primarily on PyTorch (Paszke et al., 2019) leveraging PyTorch Geometric (Fey & Lenssen, 2019) , DGL (Wang et al., 2019) and their dependent open-source libraries to perform some of the graph processing steps. We also make use of the codebase generously released by Kong et al. (2023) as we adapt some of their functionalities. While we will release the code repository of our work after this manuscript is peer-reviewed, we provide important dataset information and experimental setup in Section 4 and include necessary hyperparameter information in Section A.5. hop context features for all nodes using C 0 = ÃH and C 1 = Ã2 H, respectively, where Ã is the normalized adjacency matrix and H is the node feature matrix.In the figure, where K is set to 5 for simple illustration, we can observe that there are K -1 = 4 sampled nodes for the node i, where the nodes sampled from 1 hop are represented as j1 and from 2 hop are represented as j2. The 2-hop context feature for j2 will also form part of the token set for the node i, following INPUTTOKENS Algorithm 2. As such, the set of tokens of size 3K will include vectors which represent the a node i's 4 hop neighborhood information.The algorithm GLOBALMODULE in LargeGT is adapted from Kong et al. (2023) which uses a single layer Transformer encoder to allow every node in a mini-batch to global graph nodes, conceptually through a fixed sized B centroids. The B centroid tokens are stored in a codebook which is defined as µ ∈ R B×D and are updated using an Exponential Moving Average (EMA) K-Means algorithm (Kong et al., 2023) at every mini-batch step. In Algorithm 3, MLP a and MLP b are two multi-layer perceptron modules with separate learnable parameters, while W Q , W K , W V are the learnable parameters of the Transformer encoder.Algorithm 3 GLOBALMODULE: Algorithm to output global representations of nodes in mini-batchRequire: Hidden features H in ∈ R M ×D for M nodes in a mini-batch, µ is the centroid computed by the K-Means algorithm, P is the centroid assignment index for each node. Ensure: Return the output representations of all nodes in the mini-batch H global .1: for i = 0 to M -1 do 2:x ← MLP a (H in i )3:q ← xW Q 4:K ← µW K 5:V ← µW V Update µ using x through Exponential Moving Average (EMA) K-Means algorithm. 9: end forAs mentioned in Section 4.1, we compare LargeGT with 'Scalable Baselines' which are constrained versions of existing MPNNs or GT baselines, denoted by Model-δ. The decision to compare LargeGT with 2-hop constrained versions of the baselines was 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, in this section, we provide an extended comparison of LargeGT with both 'Scalable Baselines' as well as their original models, for ogbn-products. Note that for the original models, we adopt hyperparameters in their respective papers. From Table A .1, we can observe that the best performing model remains the same while LargeGT, which only use up to 2-hop operations, remains better and competitive compared to the best performing model. Additionally, it is obvious that the 'Original Baselines' that employ greater than 2-hop operations are computationally demanding (upto 4× in some cases), as compared to the 'Scalable Baselines'. In our experiments, we use the baselines GraphSAGE (Hamilton et al., 2017) , GAT Veličković et al. (2018) , GT-sparse (Dwivedi & Bresson, 2021; Shi et al., 2020) , NAGphormer (Chen et al., 2022) and GOAT (Kong et al., 2023) to compare with our proposed architecture LargeGT. We follow the setup of the respective codebase of NAGphormer3 and GOAT4 to conduct the baseline experiments, whileNote that in this work, we do not contextualize a model's capacity in terms of Weisfeiler-Leman (WL)'s expressiveness(Weisfeiler & Leman, 1968;Morris et al.,2019;Xu et al., 2019) as it is known that almost all of non-isomorphic graphs (or subgraphs) are distinguishable by a 1-WL equivalent model (MPNN) in the presence of node features(Cotta et al., 2021), and we do not consider graphs with anonymous nodes.We observed decreased performance when stacking multiple layers, in consistent with recent works such asChen et al. (2022);Kong et al. (2023), and leave the exploration of multi-layered version for later.https://github.com/JHL-HUST/NAGphormerhttps://github.com/devnkong/GOAThttps://github.com/snap-stanford/ogb 
 
 Appendix:  



Reviews: review: title: title: Carefully written, interesting contribution
main_review: main_review: The paper presents an approach to train transformer models on graphs in combination with sampling. 

The paper is well written, with extensive related work and carefully designed notation. The method is competitive, but not state-of-the-art. Overall, I think the contribution is interesting, and the paper should be accepted. 

However, I have the following questions and comments that the chair may not, and that the authors should strive to address. 

1) The paper does not specifically address knowledge or knowledge graphs in any way (only general graphs). This puts it outside the call for this workshop as it is on the website. I leave it to the chair to decide whether the paper is in scope, or whether a sufficiently interesting out-of-scope paper, may still be a nice addition to the workshop.
2) Despite the extensive literature list, some methods should still be mentioned and compared against (at least conceptually if not experimentally). For example, LADIES does not appear to be cited, and FastGCN is only mentioned in passing. The proposed method is very similar to these more general sampling methods, and it would be good to see explicitly what the differences and similarities are. For instance, if I took two layers of LADIES sampling (which would sample randomly from a 2-hop neighborhood), and then added a transformer layer on top as the MPNN, how close would I be to the LargeGT network? I guess the key difference is the global update, in combination with sampling, but that would be good to spell out. 
3) It isn't clear to me why the section "On comparison fwith SGC and SIGN is kept separate from the rest of the results. It seems that these numbers could easily be added to table 1. Placing them in the running text of a separate section gives the appearance of trying to hide them (which I'm sure isn't the idea, since they aren't damaging to the general message of the paper).

If issues 2 and 3 are properly addressed, and issue 1 is fine with the chair(s), I think the paper would make a fine contribution.

For minor points: the language is readable, but the authors often skip articles like "the" and "a" showing that the paper was not written by a native speaker. It would be to address these issue. As a personal pet peeve, I strongly suggest replacing all occurrences of the verbs "utilize" and "leverage" with "use".
title: title: Merging local and global features while maintaining scalability in the context of graph transformers
main_review: main_review: Overview: The paper highlights the limitations of existing graph learning models in integrating local and global graph features, especially when dealing with very large graphs. It proposes a method that effectively merges both local and global features while maintaining scalability. The proposed method involves pre-computing neighborhood sampling and utilizes a model that combines a graph transformer (for local features) and a global codebook (for global features). The authors claim that their model demonstrates good performance and significantly reduces training time compared to existing methods.

Relevance: Learning on large graphs is a highly relevant topic as many models struggle to scale effectively. The paper addresses important motivations. → (5/5)

Position with respect to SOTA: The approach is not compared to state-of-the-art (SOTA) models but only against simplified versions of baseline models. The authors explicitly exclude SOTA models, citing their primary goal of evaluating scalability. We do not consider this a valid justification. → (1/5)

Novelty: The integration of local and global features in the proposed model might be novel. The second contribution appears to be the pre-processing of neighborhood sampling, which seems more like an engineering improvement rather than a novel research contribution. Further, the neighborhood sampling is not sufficiently described. → (2/5)

Potential Impact: While the topic is highly relevant, the paper does not provide a substantial research contribution. → (2/5)

Text:
The paper is difficult to follow and contains numerous typos. The first three pages focus excessively on motivation, with design principles repeated in the introduction and the "Recipe for Building Transformers for Large Graphs" section. This redundancy could be reduced to allow more space for explaining the foundational concepts and model architecture. The functionality of the global codebook, a critical component of the model, is not clearly explained. Additionally, the algorithms are inadequately described.

The paper repeatedly claims a 16.8% performance gain on ogbn-products and snap-patents, which contradicts the values reported in Table 2. Unfortunately, only accuracy (Acc) is reported, with no mention of F1, Precision, or Recall.

The claim that the proposed model is three times faster than existing models is not substantiated by the figures. Figure 2, which plots epoch time against test accuracy, is not a representative measure of overall training time and speedup, as different models require varying numbers of epochs. Moreover, Figure A.1 (a) and (b) suggest that the proposed model trains slower than existing ones, while only (c) and (d) show a significant improvement. Moreover, the claim of faster training cannot be concluded from these plots.

Open Questions:

In the abstract: “finding the optimal trade-off between speed and accuracy with sampling techniques remains challenging” → What does accuracy mean in the context of sampling?
It is unclear what features are provided to the local transformer model. Are node IDs or other node features included?
In the Introduction, under "Local Representations": “We represent a novel tokenization strategy that prepares a fixed set of tokens for each graph node to be processed by a Transformer encoder.” This is never explained in the text. What does this mean?
It is unclear how performing neighborhood sampling in a preprocessing step reduces memory requirements. The sum of sampled neighborhood graphs should be larger than the total graph. Even if these neighborhoods can be distributed across multiple nodes, the benefit is questionable. Moreover, this design decision lacks practical evaluation on a computing cluster with multiple nodes.
“For simplicity, we will represent H_i in the following equations” → What does this mean? Furthermore, H_i^in is not consistently replaced by H_i.
title: title: Potentially interesting for graphs, limited impact for knowledge graphs
main_review: main_review: This paper introduces LargeGT, a novel Graph Transformer (GT) framework designed to address the computational challenges associated with large-scale node classification tasks. The authors propose a neighborhood sampling technique that is pre-computed, which is then combined with local and global attention mechanisms. By conflating 1- and 2-hop neighbourhoods in their sampling approach, the method is able to go up to 4-hops with less computational demands. The local and global attention mechanisms are adapted from state-of-the-art works.
LargeGT is evaluated on three popular node classification benchmarks, and compared to a few relevant baselines, which the authors slightly adapted to consider fewer neighbours and thus be more scalable (although this was not necessary in many cases and results in decreased performance for the baselines). LargeGT surpasses baseline performance in 2 out of 3 datasets and is faster than the best-performing baselines. 


My major concern with the paper is that it is not a very good fit for the workshop. It focuses only on GNNs and graphs, and does not specifically address KGs. 
While scalability is definitely a challenge for GNNs over KGs, the work does not particularly focus on KGs nor on the more standard KG completion task (link prediction). Interestingly, OGB does provide a very large Wikidata link prediction challenge: WikiKG90Mv2, a Knowledge Graph (KG) extracted from the entire Wikidata knowledge base.
This dataset is part of the OGB Large Scale Challenge datasets. https://ogb.stanford.edu/docs/lsc/, which are definitely a more suitable challenge to the proposal of the paper. 
While this is a major flaw --- and behind my less positive rating --- I leave below some suggestions and discussion points.

The proposed approach is methodologically sound, with its major contribution being a smart approach to offloading the issues of graph scalability to a pre-computation step that determines the context of each node based on a sampling of the neighbourhood. The other aspects of the methodology are based on existing approaches.
However, the implications of the neighbourhood sampling are not properly discussed or analysed. LargeGT conflates the 1-hop and 2-hop neighbourhoods. It would go a long way towards understanding the impact of this step to perform studies that compare defining a neighbourhood at just 1-hop with 1- and 2-hop. 


The experimental design is somewhat limited. 

First, as stated above, the benchmark datasets selected are not the most suitable. Moreover, it is unclear why LargeGT is focused only on node classification.

Second, the choice of baselines does not include the best performing systems in the OGB leaderboards for the selected benchmarks. While authors state “The goal of our experimental setup is to show how the scalability constraints affect existing models’ capabilities, which can be addressed by LargeGT; for this reason, we do not use enhanced techniques for obtaining top leaderboard results such as auxiliary label propagation [44, 67] or augmentations [68].”, the fact remains that LargeGT would rank 44th on OGB leaderboard for ogbn-products and 15th for ogbn-papers100M. The less than stellar results on these benchmarks should be discussed in more detail.

Third, the choice of “constraining” the baselines to ensure they are scalable is questionable. The text is very unclear on what these constrained versions are, which is only briefly explained in a table caption. But more importantly, some of the models used as baselines are able to run fully on the datasets. The GOAT paper includes results for both ogbn-products and snap-patents, and in the first case the results surpass those of the constrained version (82.00 ± 0.43). The ogbn-products leaderborad has GraphSage at 0.7850 and GAT with neighbour sampling at 0.7945 (which would be 3rd place behind GOAT). I do not think it is a fair evaluation to "constrain" models that do not appear to need it. The standard results are presented in the appendix, but by showing only constrained versions, LargeGT appears to perform better than it actually does. Moreover, LargeGT can access a neighbourhood of up to 4-hops, while others were constrained to only 2. 

Finally, the analysis on computational time is not entirely fair. Since LargeGT pre-computes the neighbourhood sampling, the time spent on this task is not considered for model training. However, this aspect should definitely be discussed. The reader must be made aware if the neighbourhood sampling is very costly to run, and since you cannot train the model without it.

The paper’s title is a bit too broad in meaning: Graph Transformers for Large Graphs. There are several methods that could be described by this title.