COARFORMER: TRANSFORMER FOR LARGE GRAPH VIA GRAPH COARSENING
Year: 2021

Abstract:
Although Transformer has been generalized to graph data, its advantages are mostly observed on small graphs, such as molecular graphs. In this paper, we identify the obstacles of applying Transformer to large graphs: (1) The vast number of distant nodes distract the necessary attention of each target node from its local neighborhood; (2) The quadratic computational complexity regarding the number of nodes makes the learning procedure costly. We get rid of these obstacles by exploiting the complementary natures of GNN and Transformer, and trade the fine-grained long-range information for the efficiency of Transformer. In particular, we present Coarformer, a two-view architecture that captures fine-grained local information using a GNN-based module on the original graph and coarse yet long-range information using a Transformer-based module on the coarse graph (with far fewer nodes). Meanwhile, we design a scheme to enable message passing across these two views to enhance each other. Finally, we conduct extensive experiments on real-world datasets, where Coarformer outperforms any singleview method that solely applies a GNN or Transformer. Besides, the coarse global view and the cross-view propagation scheme enable Coarformer to perform better than the combinations of different GNN-based and Transformer-based modules while consuming the least running time and GPU memory.

heading: 1 INTRODUCTION
text: In recent years, the Transformer architecture (Vaswani et al., 2017) has been derived into several variants, e.g., BERT (Devlin et al., 2019) and ViT (Dosovitskiy et al., 2021), which achieve unprecedented successes in natural language processing (NLP) and computer vision (CV), respectively. Some recent works (Kreuzer et al., 2021; Ye & Ji, 2021; Ying et al., 2021a) attempt to generalize Transformer for graph data by treating each node as a token and designing dedicated positional encoding for the nodes. These works’ performance has surpassed that of graph neural networks (GNN) on an increasing number of graph-related tasks, particularly molecular property prediction (Ying et al., 2021b).
These works, however, demonstrate their superiority on small graphs, such as molecules with tens of atoms (i.e., nodes). When applied to a large graph, these Transformer-based methods (Dwivedi & Bresson, 2021; Zhang et al., 2020) explicitly or implicitly restrict each node’s receptive field to its neighbors. Nevertheless, large graphs, such as Arxiv and Products in OGBN (Hu et al., 2020), also demand the global receptive field and the powerful expressiveness of the Transformer architecture. These graphs have more than hundreds of thousands of nodes and graph diameters larger than twenty, where the needed receptive field should be large, and the correlations among the nodes’ features are complex.
So, what limits the applicability of Transformer on large graphs? Here, we identify two main obstacles: (1) Transformer is built on a node-to-node attention mechanism. When applied to a large graph with numerous nodes, the massive distant nodes can divert a significant portion of the attention no matter whether they are indeed related. As a result, the target node can neglect its local neighborhood, which is indispensable for learning generalizable node representations. Hence, Transformer is prone to causing over-fitting on large graphs, which will be exacerbated for the semi-supervised node-level tasks where the number of labeled nodes is limited. We will provide some empirical evidences for this point in Sec. 5.1.1 and Appendix A.1. (2) The global receptive field of Transformer is
costly, where the pairwise interactions among tokens lead to quadratic computational complexity regarding the number of nodes. Although some Sparse Transformer methods (Roy et al., 2021; Kitaev et al., 2019; Ren et al., 2021) can improve the efficiency of the original Transformer, they have not exploited the unique characteristics of graph data and require a quadratic or at least sub-quadratic space complexity, which is still unaffordable in most practical cases.
We argue that both local and global information is useful for encoding each node in a large graph. Meanwhile, we notice that GNN and Transformer are proficient at capturing the local and global information, respectively, but neither of them can easily extract both kinds of information. Thus, a straightforward strategy is to employ them together to play to their strengths simultaneously. To this end, we propose to wipe out the discussed obstacles of applying Transformer by letting it work on a down-sampled graph that preserves both the sketch of global graph structure and the aggregated node features yet has much fewer nodes. And the similar idea is used in graph pooling (Ying et al., 2018; Baek et al., 2020) and hierarchical GNN (Fang et al., 2020; Sobolevsky, 2021). In this way, we essentially trade some fine-grained long-range information for the efficiency of Transformer.
To encode both local and global information for each node, we propose a two-view architecture Coarformer consisting of a fine-grained local view and a coarse global view. In the local view, we can apply a GNN-based module to the original input graph to encode each node by its local topological structures and the node features. In the global view, we apply a Transformer-based module to a coarse graph produced by an adopted graph coarsening algorithm. Such kinds of algorithms mimic a down-sampling to the original graph via grouping the nodes into a less number of super-nodes. The Transformer-based module makes pairwise interactions among these super-nodes, capturing the coarse but long-range dependencies of the original graph. Additionally, we design a cross-view propagation strategy for these two views in order to facilitate their interaction. As a result, Coarformer encodes each node by both its local and global information, combining GNN and Transformer’s merits. It is worth noting that the number of super-nodes balances the efficiency of the Transformer-based module and how coarse the global view is. In practice, a small number that reduces the computational complexity from quadratic to linear w.r.t. the number of original nodes can still provide helpful global information, making Coarformer applicable for large graphs.
We conduct extensive experiments on real-world datasets to study the proposed Coarformer. At first, the combinations of a GNN model with various Transformer-based methods consistently surpass a single GNN model, which supports our idea of encoding nodes by local and global information. More importantly, Coarformer achieves the best performances with the least running time and GPU memory consumption, compared to the related Sparse Transformer-based methods. Meanwhile, we empirically show that the local and global information is complementary, and our coarse global view can boost the performances of various kinds of GNNs.

heading: 2 BACKGROUND AND MOTIVATIONS
text: In this section, we summarize GNN, Transformer for graphs, and graph coarsening, along with a discussion on their connections to motivate our method. Before that, we firstly present notations for graph data. Let G = (V, E) be a undirected unweighted graph, where V is the node set, E is the edge set. We denote the number of nodes (i.e., |V|) by n and use X ∈ Rn×k0 to denote the feature matrix whose i-th row Xi,: is the feature vector of node vi. We use A ∈ {0, 1}n×n to denote the adjacency matrix of G, where Aij = 1 if and only if (vi, vj) ∈ E . The degree of a node vi is denoted by di = ∑n j=1 Aij , and the degree matrix D is a diagonal matrix with di being its i-th diagonal entry.
GNN. To represent nodes based on their features (i.e., X) and topological structures (i.e., A), most GNN models stack the message passing layers to calculate node representations H(l) by recursively aggregating the representations of its neighbors. Taking GCN (Kipf & Welling, 2017) for example, it defines this procedure as H(0) = X,H(l) = D̃− 1 2 ÃD̃ 1 2H(l−1)W (l), where D̃ = D + In, Ã = A + In, and W (l) ∈ Rk(l−1)×kl is a learnable parameter. In such a way, an L-layer GNN model calculates H(L) to represent the nodes, where the receptive field for each node is its L-hop neighborhood. To capture long-range information, we need to increase L, where a large depth L is prone to causing over-smoothing (Li et al., 2018) and bottleneck (Alon & Yahav, 2021) issues.
Transformer for graphs. Therefore, some recent works apply the Transformer architecture to capture useful long-range information in the graph, which relies solely on the attention mechanism,
dispensing with the message passing used in GNN. Taking the scaled dot-product attention for example, the node representations are updated as the weighted sums of themselves:
H(l) = Softmax ( QKT√ m ) V = Softmax ( (H(l−1)W (l) Q )(H (l−1)W (l) K ) T √ m ) H(l−1)W (l), (1)
where WQ, WK ∈ Rk(l−1)×m, and W ∈ Rk(l−1)×kl are learnable parameters. Comparing Eq. 1 with the updating equation used in GCN, Softmax ( QKT√
m
) is usually allowed to be a dense n × n
matrix, while the (i, j)-th entry of D̃− 1 2 ÃD̃ 1 2 is non-zero only if Ãij 6= 0. Thus, one attention layer is sufficient for each h(l−1)j to attend to any h (l) i , no matter how far away vj is to vi. Although these pairwise interactions provide the global receptive field for Transformer to capture long-range information, they often distract the necessary attention of each node from its neighborhood, especially when n is large. Besides, these pairwise interactions requireO(n2) computational complexity, which further hinders the application of Transformer to large graphs.
Graph coarsening. To simplify a given graph (mainly reducing the number of nodes) while preserving its global information as much as possible, graph coarsening (Ron et al., 2011; Loukas, 2019) produces a partition P = {C1, . . . , Cn′} of V and regards each cluster Ci as a super-node. Consequently, we get a coarse graph G′ = (V ′, E ′), where |V ′| = n′ and (Ci, Cj) ∈ E ′ if and only if ∃vk ∈ Ci, vl ∈ Cj , s.t. (vk, vl) ∈ E . Meanwhile, this partition can be characterized by a matrix P̂ ∈ {0, 1}n×n′ , with P̂ij = 1 if and only if vi ∈ Cj . Then its normalized version can be defined by P = P̂C− 1 2 , where C is a n′×n′ diagonal matrix with |Ci| as its i-th diagonal entry. We can define the feature matrix and weighted adjacency matrix for G′ by X ′ = P TX and A′ = P TAP , which characterize a coarse global view of the original graph. We define the coarsening rate as c = n ′
n .

heading: 3 METHODOLOGY
text: In this section, we introduce a two-view architecture Coarformer composed of a fine-grained local view and a coarse global view. We present the overview of Coarformer in Figure 1. At first, we preprocess an input graph G via graph coarsening to generate a coarse graph G′. Then a GNN-based module and a Transformer-based module work on G and G′, respectively, which can be interpreted as encoding the nodes from the fine-grained local view and the coarse yet global view. We further design a scheme for Coarformer to enable neural messages to propagate across these two views, so the resulting node representations synthesize both the local and the global information.
In the fine-grained local view, any GNN model (e.g., GCN) can be adopted, which recursively calculates the node representations H(l), l = 1, . . . , L. As for the coarse global view, the details about the Transformer-based module are presented in Sec. 3.1. Then we elaborate on how to enhance the communication between these two views in Sec. 3.2. Lastly, we present how Coarformer makes inference and how to optimize Coarformer in Sec. 3.3.

heading: 3.1 COARSE GLOBAL VIEW
text: We apply a Transformer-based module to the coarse graph G′, where each super-node is regarded as a token. Thus, we use X ′ as the initial token representation H(0)c , where the subscript “c” stands for “coarse” to distinguish a matrix from its counterpart in our fine-grained local view. Then H(0)c is fed into the Transformer-based module, which consists ofL′ layers of multi-head attention and produces H (l) c , l = 1, . . . , L′. In each multi-head attention layer, we use h heads, i.e., h scaled dot-product attention, each of which has its specific parameters and processes its input as Eq. 1: head(l)i =
Softmax ( (H(l−1)c W (l,i) Q )(H (l−1) c W (l,i) K ) T
√ m
) H (l−1) c W (l,i), i = 1, . . . , h. The outputs of the heads are
concatenated and fed into a fully-connected feed-forward network (FFN) with ReLU activation in between its linear layers. We set the FFN of each layer to ensure the token representation at each layer has the same dimension, i.e., k1 = · · · = kL′ , which allows us to consider a residual connection between each consecutive layer. Finally, a layer normalization (LN) is applied, and then the output of the l-th multi-head attention layer is: H(l)c = LN(FFN(Concat(head (l) 1 , . . . , head (l) h ))+H (l−1) c ).
Up to now, H(l)c , l = 1, . . . , L′ depend only on the node features X ′. To utilize the topological structures of G′, we employ personalized page rank (PPR) (Page et al., 1999) as a bias term for our attention weight matrix. Specifically, we first calculate the PPR matrix R′ ∈ Rn′×n′ based on the adjacency matrix A′, where R′i,j denotes the probability of starting a random walk with super-node Ci and stopping at Cj . Then for each head at each layer, we calculate the attention weight matrix based on not only the inner products between queries and keys but also the PPR
matrix: head(l)i = Softmax ( (H(l−1)c W (l,i) Q )(H (l−1) c W (l,i) K ) T √ m + β (l) i R ′ ) H (l−1) c W (l,i), where β (l) i is
a learnable parameter for adjusting the contribution of the PPR matrix.
Computational complexity. It is worth noting that the graph coarsening algorithms allow to control the size of coarse graph (i.e., n′). In essence, n′ balances the efficiency of the Transformer-based module and how coarse the global view is. We will empirically show in Sec. 5 that the useful global information can still be extracted from the coarse global view, even though n′ is as small as √ n. Accordingly, the time complexity of our Transformer-based module is quadratic w.r.t. the number of super-nodes and thus linear w.r.t. the original number of nodes, i.e., O(n′2) = O( √ n 2 ) = O(n). Meanwhile, the space complexity of our Transformer-based module is also O(n), as the dominant attention weight matrix has size n′ × n′, which can fit into the GPU for most practical large graphs.

heading: 3.2 CROSS-VIEW PROPAGATION
text: As a two-view architecture, the node representations H(l), l = 1, . . . , L, calculated by the GNNbased module, encode the fine-grained local information of the nodes, while the representations of the super-nodes H(l)c , l = 1, . . . , L′ capture long-range dependencies among the nodes but with a coarse granularity. We argue that, to predict for the nodes, both their local and global information are helpful, and thus we should synthesize these representations encoded from the two views.
To this end, we design a scheme of cross-view propagation for Coarformer, where the encoded representations are allowed to propagate across these two views. At first, due to its pairwise interaction nature, the Transformer-based module does not need to be deep, thus it is safe to assume L′ ≤ L. Then we denote the outputs of each layer in these two modules by Z(l) and Z(l ′) c , respectively, and define their forward propagation as follow:
Z(l) = { H(l) + P̂C−1H (l/b L L′ c) c if l mod b LL′ c = 0,
H(l) elsewise;
Z(l ′) c = H (l′) c + (P̂C −1)TH(l ′b L L′ c).
(2)
For simplicity, we do not explicitly re-define H(l+1) and H(l ′+1) c based on Z(l) and Z (l′) c , respectively, but please keep in mind that Z(l) and Z(l ′)
c do serve as the inputs to their corresponding next layers. With this cross-view propagation, the outputs of our two modules depend on each other.
Thus, once we have properly optimized them, their outputs would properly synthesize both local and global information from the two views, leading to more discriminative node representations.
Sampling-based cross-view propagation on large graphs. Generally, full-batch training is infeasible on large graphs. With mini-batch training, only the rows of H(l ′b L L′ c) that correspond to the target nodes sampled at that layer are available, and thus we cannot calculate Z(l ′)
c exactly. Luckily, a more careful look at Eq. 2 shows that, ∀i = 1, . . . , n′, the i-th row of Z(l ′) c can be written as:
(Z(l ′) c )i,: = (H (l′) c )i,: +
1 |Ci| ∑ vj∈Ci H (l′b L L′ c) j,: = (H (l′) c )i,: + Evj∼Uniform(Ci)[H (l′b L L′ c) j,: ]. (3)
Suppose the nodes in each mini-batch are sampled by a widely adopted GraphSAINT sampler (Zeng et al., 2020) that is random walk-based with a “teleporting” probability α. Let’s denote the nodes sampled at l-th layer by B(l). We can pre-compute the probability distributions for vi ∈ V: P (l)(vi) = 1 n (αIn + (1− α)D −1A)L−l1n)i, l = 1, . . . , L, and approximate Z (l′) c as follow:
Proposition 1 Denoting B(l)i = {v|v ∈ Ci ∩B(l)}, ∀i ∈ {1, . . . , n′}, l′ = {1, . . . , L′}, (H (l′) c )i,: +∑
vj∈B (l′b L L′ c) i
1 |Ci|
∑ vk∈B (l′b L L′ c)
i
P (l′b L L′ c)(vk)
P (l′b L L′ c)(vj) H
(l′b L L′ c) j,: is an unbiased estimator for (Z (l′) c )i,:.
The proof is simple: P (l)(vi) is the sampling probability of vi at the l-th layer, and
1 |Ci|
∑ vk∈B (l′b L L′ c)
i
P (l′b L L′ c)(vk)
P (l′b L L′ c)(vj) serves as the likelihood ratio used in importance sampling. Thus,
Coarformer can cooperate with mini-batch training and thus is viable on large graphs.

heading: 3.3 INFERENCE AND OPTIMIZATION
text: Without loss of generality, we consider using Coarformer for node classification task. We denote node labels by Y ∈ {0, 1}n×|Y| where Y is the label set, Yi,: is a one-hot row vector, and Yi,j = 1 indicates vi belongs to the j-th class. We can naturally deduce the labels of the super-nodes by Y ′ = P TY for our coarse graph G′. To predict Y and Y ′, we can simply stack a linear output layer upon the final node representations. Specifically, the predictions made from our two views are Ŷ = Softmax(Z(L)W + 1nbT) and Ŷ ′ = Softmax(Z (L′) c W ′ + 1n′b
′T), respectively, where W ∈ RkL×|Y|, W ′ ∈ RkL′×|Y|, b ∈ R|Y|, and b′ ∈ R|Y| are learnable parameters. Denoting the loss function, e.g., Cross-Entropy loss, by L(·, ·), we can learn the parameters of Coarformer by minimizing γL(Ŷ ,Y ) + (1− γ)L(Ŷ ′,Y ′) with γ ∈ [0, 1] as a hyper-parameter for balancing the impacts of our two views. As our cross-view propagation scheme has enabled Z(L) to contain both the local and the global information, we adopt γ = 1 in our experiment for simplicity, where the Transformer-based module is still optimized to cooperate with the GNN-based module.

heading: 4 RELATED WORK
text: Transformer for graphs. Recently, models based on the Transformer architecture have shown their superiority in more and more domains, e.g., BERT (Devlin et al., 2019) in NLP and ViT (Dosovitskiy et al., 2021) in CV. Existing works that attempt to generalize the Transformer architecture for graph data mainly focus on two problems: (1) How to design the positional encoding for nodes? (2) How to make the pairwise interactions computationally tractable on large graphs? For the positional encoding, Laplacian eigenvectors (Dwivedi & Bresson, 2021; Kreuzer et al., 2021), hop-based relative distance (Zhang et al., 2020; Ying et al., 2021a), and Weisfeiler-Lehman code (Zhang et al., 2020) have been studied from both theoretical and empirical aspects. For the scalability issue, an immediate workaround is to restrict the receptive field of each node, e.g., GAT (Veličković et al., 2018) and GT-sparse (Dwivedi & Bresson, 2021) consider just the 1-hop neighbors, which yet sacrifices one of the main advantages of Transformer. To make a better trade-off, ADSF (Zhang et al., 2019) relaxes this restriction to include high-order neighbors based on random walks. SGAT (Ye &
Ji, 2021) and SAC (Li et al., 2020) learn to select a subset of each node’s high-order neighborhood. Graph-Bert (Zhang et al., 2020) restricts the receptive field of each node to the nodes with top-k intimacy scores (e.g., Katz and PPR). However, all these restrictions possess a strong bias towards a node’s local neighbors. Instead, Coarformer conducts the regular pairwise interactions for supernodes, where long-range information can be easily captured and lifted back to the original nodes via our designed cross-view propagation.
Sparse Transformer for NLP. In parallel, many sparse Transformer methods have been proposed to reduce the computational complexity of the Transformer in the field of NLP. Longformer (Beltagy et al., 2020) applies block-wise or strode patterns, just like the GAT only focuses on specific neighbors. Reformer (Kitaev et al., 2019) introduces a hash-based similarity measure to cluster tokens into chunks efficiently. Routing Transformer (Roy et al., 2021) employs online k-means clustering on the tokens. Combiner (Ren et al., 2021) introduces a bi-level factorization of the attention weights, unifying the expression of most of the existing sparse transformers. However, these factorizationbased methods often require a quadratic or sub-quadratic space complexity regarding the number of nodes, still making them infeasible on large graphs. By running a Transformer-based module on a coarse graph with n′ ≈ √ n nodes, Coarformer decreases this space complexity and thus saves a lot of GPU memory, as Figure 2 demonstrates.

heading: 5 EXPERIMENTS
text: In this section, we conduct extensive experiments on real-world datasets to evaluate the performance of Coarformer. All the experiments are conducted on a machine with an NVIDIA RTX 2080ti GPU (11GB), Intel Xeon Platinum 8163 CPU (2.50GHz), and 400GB of RAM.

heading: 5.1 PERFORMANCE COMPARISON
text: Datasets. Following GPR-GNN (Chien et al., 2020), we conduct our experiments on ten real-world datasets, including five homophilic graphs Cora, CiteSeer, PubMed (Sen et al., 2008; Yang et al., 2016), Computers, Photo (McAuley et al., 2015; Shchur et al., 2018), and five heterophilic graphs, Chameleon, Squirrel, Actor, Texas, Cornell (Rozemberczki et al., 2021; Tang et al., 2009; Pei et al., 2019). A detailed description of these datasets is provided in Appendix A.2.
Protocol. To conduct the experiments uniformly and fairly, we split the nodes into train/valid/test sets, where the ratio is 60%:20%:20%, and we randomly generate ten such splits for each dataset. Each method is evaluated with these ten splits for each dataset, and we report the averaged metric. To compare the performances and resource requirements of the considered methods, we choose accuracy, training time, and consumed GPU memory as the metrics. We perform hyperparameter optimization (HPO) for all methods, where the details can be found in Appendix A.3.1.

heading: 5.1.1 OVERALL RESULTS
text: First, we aim to verify the benefits of combining a Transformer-based module working in the global view and a GNN-based module working in the local view. Second, we compare Coarformer with several related Transformer-based methods working in the global view without coarsening under our two-view architecture.
Baselines. For simplicity and generality, we consider GraphSAGE (Hamilton et al., 2017) working in the local view to accommodate full batch training and mini-batch training with which Transformer-based modules cooperate in the global view. Meanwhile, we use Graph Transformer (GT) as local model, which attends only to its neighbors, as an alternative model in the finegrained local view for comparison. And for global model, we adapt the Transformer-based module Graphormer, which achieves excellent results in OGB-LSC (Hu et al., 2021), with different positional encoding and attentional bias: None, PPR, distance of the shortest path (SPD), PPR+SPD. Besides, under our two-view architecture, we select several related Transformer-based modules in the global view without coarsening combined with GraphSAGE in the local view as baselines to compare their performance with Coarformer and Coarformer without cross-view propagation called Coarformer (-CP): Graphormer with quadratic complexity; Graph-Bert, which uses top-k PPR of each node as candidate set; Reformer, which uses locality sensitive hash (LSH) to reduce compu-
tational complexity; and Routing Transformer, which uses online k-means clustering to reduce the candidate set.
Results and analysis. We present the results about performance comparisons on Cora, CiteSeer, Pubmed, Chameleon, Actor, and Squirrel in Table 1. Results on the other datasets are presented in Appendix A.5.1. (1) Overall, the methods with two views (i.e., “Local+Global”) outperform both the local view alone and the global view alone methods on almost all the datasets. This phenomenon suggests that the Transformer-based modules are skilled in capturing long-range information, which complements what the local view focuses on. (2) Among these “Local+Global” methods, Coarformer achieves the best performance on most of the datasets, demonstrating its effectiveness. Interestingly, although its Transformer-based module works on the original graph that provides more fine-grained global information than a coarse graph, +Graphormer (all) leads only on one dataset, less than Coarformer. Taking this comparison and the relatively poor performances of global view alone methods into consideration, we attribute the advantage of Coarformer to the coarse graph, which might implicitly regularize the Transformer-based module. Meanwhile, Coarformer outperforms the +Sparse Transformer methods. On the one hand, +Graph-Bert determines the candidate set for each target node by Top-k PPR in the global view, which restricts the receptive field of Transformer-based module. On the other hand, +Reformer and +Routing do not incorporate the graph structure, making their captured information overly dependent on node features. Consequently, their extracted information might be less complementary to the local view. (3) The performance of Coarformer (-CP) is slightly weaker than that of Coarformer since the lack of information exchange between the local view and the global view, which confirms the necessity of our proposed cross-view propagation scheme.
We present the results concerning efficiency in Table 2, where the total training time excludes the time for data pre-processing (e.g., on Cora 4s, on Chameleon 5s) and inference. Time consumed by mini-batch training is significantly increased by more than 100 times, which is often intolerable in practice. As a result, when Transformer adapts to large graphs, it either exceeds the memory limit with full batch training or consumes too much time with mini-batch training. It is worth emphasizing that Coarformer significantly reduces the training time concerning the quadratic Transformer, such as Graphormer. In contrast to +Graphormer, the time consumption increases linearly with the number of nodes (given a coarsening rate of √ n), which does not change the time complexity of the GNN-based module by order of magnitude, as shown in Figure 2.

heading: 5.1.2 EFFECTIVENESS AND ROBUSTNESS OF COARFORMER’S GLOBAL VIEW
text: In the previous section, we have shown the superiority of Coarformer, where GraphSAGE is adopted as the module working in Coarformer’s local view. To verify the generality of the benefits brought
in by the global view of Coarformer, we employ different GNNs and compare them to Coarformer with each of them as the module working in the local view of Coarformer. For this purpose, GCN, GIN (Xu et al., 2018), GAT, Graph Transformer (GT), APPNP (Klicpera et al., 2018), and GPRGNN are considered.
Results and Analysis. We present the results about effectiveness in Table 3 on Cora, CiteSeer, PubMed, Chameleon, Actor, and Squirrel, where all the instances of Coarformer outperform their corresponding GNN models on most datasets. Results on other datasets are presented in Appendix A.5.2. Particularly, GIN performs much worse than other GNN models on several datasets, but with the global view of Coarformer, the gap is significantly reduced. Furthermore, Coarformer achieves the best performance on Cora, PubMed, Computers, Photo, Chameleon, Actor, and Squirrel. All these results confirm that the global view of Coarformer can boost the performance of an arbitrary GNN model, which further justifies the complementary natures of Coarformer’s two views. Similarly, we conduct experiments on efficiency, where the detailed experimental results can be found in Appendix A.4. Whatever GNN-based module is in the local view, the time consumed by Coarformer remains in the same order of magnitude, where the increase is negligible.

heading: 5.2 COMPARISONS ON OGB
text: This experiment aims to verify the effectiveness of Coarformer on extremely large graphs.
Datasets. We adopt ogbn-arxiv and ogbn-products, wherein there are 169,343 and 2,449,029 nodes, respectively. We use the official train/valid/test splits for each dataset. Conventionally, we convert the directed graph ogbn-arxiv into an undirected graph. Details can be found in Hu et al. (2020).
Protocol. We largely follow the experimental setup in Sec. 5.1.1, yet all models are learned with mini-batch training due to the scale of the adopted datasets. Specifically, we employ GCN to cap-
ture the local information in the fine-grained local view, where random walk-based GraphSAINT is used to sample subgraphs for training the GCN. Then, we regard GCN as our testbed for comparing Coarformer with several Transformer-based methods under our two-view architecture, including Reformer and Routing Transformer (RT). Graphormer is excluded because calculating the PPR matrix and the SPD matrix for such huge graphs is intolerable. In addition, we perform HPO for all these methods. Please see Appendix A.3.2 for details.
Results and Analysis We present the results about effectiveness in Table 4, where Coarformer surpasses all the methods significantly (p-values = 0.02). The experimental results show that Coarformer can also improve performance of capturing long-range information significantly compared to GCN on extremely large graphs, wherein long-range information in the global view contributes. Moreover, we have to make the candidate set smaller because of the GPU memory limitation so that +Reformer and +RT even underperform GCN. These results remain consistent with the section 5.1.1.

heading: 5.3 SENSITIVITY ANALYSIS
text: Since Coarformer applies the Transformer-based module on a coarse graph, a question naturally comes up—Are the performances of Coarformer sensitive to the choice of coarsening algorithm as well as the adopted coarsening rate? Therefore, we evaluate Coarformer with different coarsening algorithms and different coarsening rates. Considered coarsening algorithms include Variation Neighborhoods (VN) (Loukas, 2019), Variation Edges (VE) (Loukas, 2019), and Algebraic JC (Alg JC) (Ron et al., 2011). Experimental settings are deferred to Appendix A.3.3.
Results and Analysis. We present the results in Table 5, where there is no apparent difference between different coarsening algorithms, indicating the robustness of Coarformer w.r.t. them. Overall, VN usually leads to higher accuracy on the test set compared to other coarsening algorithms, but other coarsening algorithms are also acceptable. Interestingly, the best performance on Cora is obtained when the coarsening rate is 1.00, with which Coarformer becomes equivalent to +Graphormer and still performs well. Meanwhile, the performance drops slightly as the coarsening rate decreases. However, even when the coarsening rate decreases to that corresponding to a coarse graph with size n′ ≈ √ n, the performance of Coarformer still surpasses that of GCN/GAT. As for Chameleon, VN performs best when the corresponding n′ is close to √ n. As for VE and Alg JC, they also show competitive results. Based on these results, we recommend attempting the coarsening rate corresponding to a n′ around √ n when applying Coarformer for large graphs.

heading: 6 CONCLUSION
text: In this paper, we propose a novel two-view architecture Coarformer, which employs a GNN-based module and a Transformer-based module to encode nodes from the local and global view, respectively. The global view is constructed by graph coarsening, which implicitly regularizes the applied Transformer-based module and improves its efficiency. To enable the mutual enhancement between these two views, we further develop a cross-view propagation scheme that is consistent with minibatch training. Extensive experiments conducted on large real-world graphs verify the advantages of Coarformer against existing Transformer-based methods in terms of both performance and resources (i.e., running time and GPU memory consumption). In summary, Coarformer extends the scope of usage of Transformer, paving the road towards a fully Transformer-based model for graph data.

heading: A APPENDIX

heading: A.1 STUDY ABOUT SAMPLE COMPLEXITY
text: In Sec. 5.1.1, we compare different methods with a so-called dense split of the node set (i.e., 60%:20%:20%). To assess the sample complexity of considered methods, we further compare several of them on Cora with a sparse split, i.e., 2.5%:2.5%:95%. Except for these ratios, other settings are kept the same as Sec. 5.1.1. The results are shown in Table 6. As expected, the performances of all the methods decrease when the size of the training set is reduced. With the sparse split, GraphSAGE and Coarformer exhibit a decrease of less than 20%, while the performance of the pure Transformer-based method Graphormer almost drops to only a half of that with the dense split. This phenomenon suggests a higher sample complexity of Transformer compared with GNN. We also present the performances of Graphormer with different hyper-parameter configurations in Table 7. Unlike the conventional cases where there are four or five heads and a hidden dimension of 128/256, a relatively small capacity is suitable for Graphormer on Cora.

heading: A.2 DATASETS DESCRIPTION
text: See Table 8 for a detailed description of the medium-sized dataset and Table 9 for the OGB extremely large dataset. These datasets come from different domains, and the nodes and edges from different datasets represent different meanings, including citation graph (Cora, CiteSeer, and PubMed), copurchase graph (Computers and Photo), Wikipedia graph (Chameleon and Squirrel), actors collaborating graph (Actor), Website graph (Texas and Cornell), and extremely large datasets (ogbn-arxiv and ogbn-products) provided by OGB team.

heading: A.3 EXPERIMENTAL DETAILS

heading: A.3.1 DETAILS ABOUT PERFORMANCE COMPARISONS
text: In this section, we describe the details of the experiment with parameter settings. It is worth noting that, unlike the GPR-GNN setup, we report the accuracy of the test set when the model achieves the highest accuracy in the validation set. In contrast, GPR-GNN reports the accuracy of the test set when the loss function is lowest in the validation set. We use accuracy with a 95% confidence interval, equal to the micro-f1 score when it is a single-label classification, as an evaluation metric of effectiveness and the average training time as an evaluation metric of efficiency. In addition, we
perform HPO for all models with weight decay in {0.0, 0.0005}, coarsening rate in {0.1, 0.01}, dropout rate in {0.0, 0.5}, and learning rate in {0.002, 0.01, 0.05}. The number of head is all set to 4. The sizes of the hidden layers are all set to 64. Also, we set the depth of the GNN model to be two so that it is encouraged to focus on the local information of each node and avoid oversmoothing.In particular, for APPNP and GPR-GNN, we use their optimal hyper-parameters as given in the paper(Chien et al., 2020). In addition, each model is trained 1,000 epochs with early stops if the accuracy on the validation set does not decrease within 200 epochs.

heading: A.3.2 DETAILS ABOUT COMPARISONS ON OGB
text: We perform HPO for all models with weight decay in {0.0, 0.0005}, dropout rate in {0.0, 0.5}, batch size in {256, 512}, and learning rate in {0.002, 0.003, 0.01}. And hidden dim is set to 256, the depth of GNN-based module are all set to 3, the coarsening rate is 0.01 on ogbn-arxiv and 0.001 on ogbn-products.

heading: A.3.3 DETAILS ABOUT SENSITIVITY ANALYSIS
text: We conduct experiments on a typical homophilic graph, Cora, and a typical heterophilic graph, Chameleon. For each coarsening algorithm, we specify different coarsening rates, where the coarsening rate, noted as c, takes value from {0.01, 0.1, 0.5, 1}. Meanwhile, to ensure the generality of our analysis, we consider both GCN and GAT as the GNN-based module in the fine-grained local view of Coarformer.

heading: A.4 EFFICIENCY COMPARISONS
text: These are the results of the efficiency of different local views of GNN-based module, the average training time per epoch (ms) and average total training time (s) are reported on Table 10 and Table 11.

heading: A.5 SUPPLEMENTARY DATASETS EXPERIMENTAL RESULTS
text: In this section, we provide experimental results on the Computers, Photo, Texas and Cornell. All experimental settings are consistent with section 5.1.

heading: A.5.1 PERFORMANCE COMPARISONS BETWEEN DIFFERENT TRANSFORMER-BASED METHODS ON SUPPLEMENTARY DATASETS
text: Due to space limitations, we summarize the experimental results about performance comparisons between different Transformer-based methods for more datasets at Table 12.

heading: A.5.2 PERFORMANCE COMPARISONS ON DIFFERENT GNN-BASED MODULE ON SUPPLEMENTARY DATASETS
text: Due to space limitations, we summarize the experimental results about performance comparisons on different GNN-based module for more datasets at Table 13.

Review summaries:
This paper proposes to use the transformer architecture on the coarse graph obtained from the graph coarsening algorithm.  To be more specific, * Since directly using the transformer architecture to the large-scale graph is computationally prohibitive, the authors use the existing graph coarsening algorithms to the large graphs, and then use the transformer on the coarse graphs, which can capture the global information of the given graph in contrast to the GNNs capturing local information. * To simultaneously use both local and global structures of the graph, the authors first separately capture the local and global information of the given graph with GNNs on the original graph and transformers on the coarse graph, respectively, and then propagate information of local and global to each other with the cross-view propagation scheme. * The authors show that the proposed Coarformer outperforms baselines on node classification tasks, and also show that the proposed model is highly efficient against the global transformer models for graphs.