Coarformer: Transformer for large graph via graph coarsening
Authors: Weirui Kuang
Zhen WANG
Yaliang Li
Zhewei Wei
Bolin Ding
Venue: ICLR 2022 Submitted (2022)
Keywords: Graph Neural Networks
Transformer
Graph Coarsening

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 single-view 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.

Under review as a conference paper at ICLR 2022
COARFORMER: TRANSFORMER FOR LARGE GRAPH VIA GRAPH COARSENING
Anonymous authors Paper under double-blind review
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 num- ber 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 obsta- cles by exploiting the complementary natures of GNN and Transformer, and trade the fine- fine-graneed long-range information for the efficiency of Transformer. In par- ticular, present Coarformer, two-view architecture that captures fine-grained local information using GNN-based module on the original graph and coarse yet long-range information using Transformer-based module the coarse graph (with far fewer nodes). Mcanwhile, we design scheme to enable message pass- ing across these two views to enhance each other. Finally, we conduct extensive experiments real-world datasets, where Coarformer outperforms any single- view method that solely applies a GNN or Transformer. Besides, the coarse global view and the cross-view view propagation scheme enable Coarformer to perform better than the combinations of different GNN-based and Transformer-ban modules while consuming the least running time and GPU memory.
INTRODUCTION
In recent years, the Transformer architecture Vaswaani et al. 2017) has been derived into several variants, e.g., BERT (Devlin al. 2019) and ViT (Dosovitskiy al. 2021). which achieve un- precedented successes in natural language processing (NLP) and computer vision (CV), respec- tively. Some recent works (Kreuzer et al. 2021 Ye & Ji 2021 Ying et al. 202 attempt to generalize Transformer for graph data by treating each node as token and designing dedicated positional encoding for the nodes. These works' performance has surpassed that of graph neural networks (GNN) on increasing number of graph-related tasks, particularly molecular property prediction (Ying et al. 2021b).
These works, however, demonstrate their superiority small graphs, such molecules with tens of atoms (i.e., nodes). When applied to a large graph, these Transformer-based methods (Dwivedi implicitly restrict each node's '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 archi- tecture. 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.
& Bresson [021 Zhang al. 2020) explicitly
So, what limits the applicability of Transformer on large graphs? Here, we identify two main obsta- cles: (1) Transformer is built on node-to-node attention mechanism. When applied to 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 neighbor- hood, which is indispensable for learning generalizable node representations. Hence, Transformer is prone to causing over-fitting node-level tasks where the number of labeled nodes is limited. We will provide some empirical evi- dences for this point in Sec. 5.1.T and Appendix A.T (2) The global receptive field of Transformer is
large graphs, which will be exacerbated for the semi-supervised

---

Under review as a conference paper at ICLR 2022
costly, where the pairwise interactions among tokens lead to quadratic computational complexity garding the number of nodes. Although some Sparse Transformer methods (Roy et al. [021] Kitaev et al. 2019; Ren et al., (021) 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 (021). In this way, 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 fine-grained local view and coarse global view. In the local view, we can apply a GGN-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 Transformer-basee module to a coarse graph produced by an adopted graph coarsening algorithm. Such kinds of algo- rithms mimic down-sampling the original graph via grouping the nodes into less number of super-nodes. The Transformer-basse 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 's merits. It is worth noting that the number of super-nodes balances the efficiency of the Transformer-basee module and how coarse the global view is. 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-basee 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-basee methods. Meanwhile, empirically show that the local and global information is complementary, and our coarse global view can boost the performances of various kinds of GNNs.
2 BACKGROUND AND MOTIVATIONS
In this section, we summarize GNN, Transformer for graphs, and graph coarsening, along with a discussion their connections to motivate our method. Before that, we firstly present notations for graph data. Let G = (V,E) be undirected unweighted graph, where V is the node set, & is the edge set. We denote the number of nodes (i.e., (VD) by n and use X Ro denote the feature matrix whose i-th row X,,; is the feature vector of node Us. We use A E {0, 1]mX= to denote the adjacency matrix of G, where Aij 1 if and only if (v,, v,) E. The degree of a node vs is denoted by d, Σド= A.j. and the degree matrix D is a diagonal matrix with d, 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 (1) by recursively aggregating the representations of its neighbors. Taking GCN (Kipf & Welling, 2017) for example, it defines this procedure as (0) X, ()) D AD H ((1)) where D D + In.
Ā A+ In. and ( E R is learnable parameter. In such a way, an T.-layer GNN model calculates H 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 al. 2018) and bottleneck (Alon & Yahav| 2021) issues.
Transformer for graphs. Therefore, some recent works apply the Transformer architecture to cap- ture useful long-range information in the graph, which relies solely the attention mechanism,
2

---

Under review as a conference paper at ICLR 2022
Message passing
2 H
H
Cross-view propagation
Fine-grainee local view
Linear
Message
Message passing
passing
Aggregate
HH
Graph coarsening
Cross-view Propagation
P
X
Multi-hedd attention
X
Linear
K
Scaled dot-product attention
Concal
(1)
Mult--had attention
1
Linear
FFN
LN
A'
P
AP
Linear
PPR
Coarse global view
PC
Figure I: Overview of the Coarformer architecture.
dispensing with the message passing used in GNN. Taking the scaled dot-product attention for ex- ample, the node representations are updated as the weighted sums of themselves:
QK?
(H (1) (HH
H Softmax
V
-Softmax
H H (1)
mm
m
where Wo. Wx E Rha-an xy, and W E R&a xy are learnable parameters. Comparing Eq.
with the updating equation used in GCN, Softmax [KK matrix, while the (tt entry of D- ADA is non-zero only Å. * O. Thus, one attention layer is sufficient for each h (1111) to attend to any h, matter how far away vj is Us. 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, espe- cially when n large. Besides, these pairwise interactions require ( computational complexity. which further hinders the application of Transformer large graphs
is usually allowed to be dense
vm
Graph coarsening. To simplify a given graph (mainly reducing the number of nodes) while pre- serving its global information much possible, graph coarsening (Ron et al. 2011 Loukas of V and regards each cluster C₁ as super-node.
2019) produces partition P = =CcI...,, Consequently, we get a coarse graph G' = (V' E'), where | n' and (C,,C,) E E' if and only if Bep E C. E S.t (Uk, vi) E &. Mcanwhile, this partition can be characterized by matrix P E (0, 1) 1xx'' with P. P= -C 2, where C is n n' diagonal matrix with |C,| as its i-th diagonal entry. can define the feature matrix and weighted adjacency matrix for G' by X' PT X and A' PT AP,, which characterize coarse global view of the original graph. We define the coarsening rate n',
if and only if e E Cj. Then its normalized version can be defined by
3 METHODOLOGY
In this section, introduce a two-view architecture Coarformer composed of a fine-grained local view and a coarse global view. We present the overview of Coarformer Figure [ At first, we preprocess input graph G via graph coarsening to generate coarse graph G'. Then GNN-based module and a Transformer based module work on G and g', respectively, which can be interpreted yet global view. We further
encoding the nodes from the fineggrained local view and the design 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 1,... L. As for the coarse global view, the details about the Transformer-baseee module are presented in Sec. 3.1 Then elaborate how to enhance Lastly, we present how Coarformer makes
the communication between these two views in Sec, 3.2
inference and how optimize Coarformer in Sec. 3.3

---

Under review as a conference paper at ICLR 2022
3.1 COARSE GLOBAL VIEW
We apply a Transformer-based module to the coarse graph g", where each super-node is regarded as
token. Thus, we use X' as the initial token representation H. (0) where the subseript "c" stands for "coarse" to distinguish a matrix from its counterpart in our fine-grained local view. Then H is fed into the Transformer-basee module, which consists of L' layers of multi-head attention and produces H | = 1,.... ,..,,,'' L'. In each multi-head attention layer, we use h heads, i.c., scaled dot-product attention, each of which has its specific parameters and processes its input as Eq. head!
H H W(..)) 1,.... h. The outputs of the heads are ( ((H "wg
Softmax
vm
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 = = kyz, which allows us to consider a residual connection between each consecutive layer. Finally, layer normalization (LN) is applied, and then the output of the 1-th multi-heas attention layer is: H LN(FFN(CCncaa(heeet
,...,, he.dd
)) H H-!!-))..
(1) , I,...,''' 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' E R xn' based on the adjacency matrix A', where R2 denotes the probability of starting random walk with super-node C; and stopping at Cy. 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 (((")) wwil B R' H. ((111) where 3!0) is
Up to now, He
matrix: head! (1) Softmax
Vm
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.c., 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. Sec. thatt the useful global information can still be extracted from the coarse global view, even though n' is as small as vn. 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²)) = O(vn²) = (n)) Meanwhile, the space complexity of our Transformer-base attention weight matrix has size n' x n', which can fit into the GPU for most practical large graphs.
module is also O(n). as the dominant
3.2 CROSS-VIEW PROPAGATION
As two-view architecture, the node representations H I....,,, L, calculated by the GNN- based module, encode the fine-grained local information of the nodes, while the representations of the super-nodes H!") I,...,L' L' capture long-range dependencies among the nodes but with coarse granularity. We argue that, to predict for the nodes, both their local and global information are helpful, and thus should synthesize these representations encoded from the two views.
To this end, we design a scheme of cross- cross-view propagation for Coarformer, where the encoded rep- resentations allowed propagate across these views. At first, due to its pairwise interaction nature, the Transformer-baase -based module does not need to be deep, thus is safe to assume T,' S L.
Then we denote the outputs of each layer in these modules by Z and (("), respectively, and define their forward propagation as follow:
z = { H + PC-1 H O
(L if mod | O, elsewise;
(2)
For simplicity, we do not explicitly re-define (I+1) and H (1'+1) based Z and Z respec- tively, but please keep in mind that ( and ~ do serve as the inputs to their corresponding next layers. With this cross-view propagation, the outputs of our two modules depend each other.
4

---

Under review as a conference paper at ICLR 2022
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.
camplinng-bssed cross-view propagation large graphs. Generally, full--atch training is infea- sible on large graphs. With mini-batch training. only the rows of H ( ( that correspond the
target nodes sampled at that layer are available, and thus we cannot calculate z exactly. Luckily, a more careful look Eq. shows that, Vi =,...., n', the i-th row of z(()) can be written as:
(Z - (H + C.l
Σ H (( 0yEC,
(H! Js: + - H J::
(L
(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 a. Let's denote the nodes sampled at 1-th layer by BO) We can pre-compute the probability distributions for v E V: pl (v:) At (aIn (1 a) 11)--1))) = L..... and approximate _ as follow:
Proposition 1 Denoting Blx {uly E C, NBU), Vi E n.,...,,'),,'' =0),1=(11.-- (1....,T7) L', (H 1a+
ucc,, ( ple ((m)
Σ
(L is unbiased estimator for (Ze )i
E
"yEE!" "
2 &D 16.1
plll (
H3
The proof is simple: (1) is the sampling probability of oe at the 1-th layer, and Σ
pol'l ((w)
(1 nEe
serves as the likelihood ratio used in importance sampling. Thus, Coarformer can cooperate with mini-batch training and thus is viable on large graphs.
p (my)
3.3 INFERENCE AND OPTIMIZATION
Without loss of generality, we consider using Coarformer for node classification task. We denote node labels by E {0, 11mx "x where y is the label set, Y,, a one-hot row vector, and Y indicates ;; belongs to the j-th class. We can naturally deduce the labels of the super-nodes by Y' = Y 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 (1.) W + 17, and Y = Softmax ( W + bTT respectively, where W R X|>|, W' E (gf0/x("") E RP and b' R are Iearnable parameters.
Denoting the loss function, e.g., Cross-Entropy loss, by L(:,)), we can learn the parameters of Coarformer by minimizing L((, Y)+ 1011-11 C("" Y') with 7 E [0, 1] hyper-parameter for balancing the impacts of our two views. As our cross-view propagation scheme has enabled (L) to contain both the local and the global information, we adopt = I in our experiment for simplicity, where the Transformer-basee module still optimized to cooperate with the GNN-based module.
RELATED WORK
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 (Dosovit- skiy et al. 202T) in CV. Existing works that attempt 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 rel- ative distance (Zhang et al.) 2020 Ying et al., 2021a)) aa), and Weisteiler-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 (Veličković et al. 2018) and GT-sparse (Dwivedi & Bresson 2021 consider just the 1-hop neighbors, which yet sac- rifices 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 random walks. SGAT (Ye &
5

---

Under review as a conference paper at ICLR 2022
Ji 2021 l) and SAC (Li et al. 2020) learn select subset of each node's high-order neighborhood. Graph-Ber Bert (Zhang et al. 2020) restricts the receptive field of each node to the nodes with top-k intimacy scores (c.g., Katz and PPR). However, all these restrictions possess strong bias towards a node's local neighhors. Instead, Coarformer conducts the regular pairwise interactions for super- nodes, 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 al. 2020) applies block-wise or strode patterns, just like the GAT only focuses on specific neigh- bors. Reformer (Kitaev et al., 2019) introduces
baash-baedd 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. (021) introduces a bi-level factorization of the attention weights, unifying the expression of most of the existing sparse transformers. However, these factorization- based methods often require quadratic or sub-quadratic space complexity regarding the number of nodes, still making them infeasible on large graphs. By running a Transformer-baa module on coarse graph with n' z /ni nodes, Coarformer decreases this space complexity and thus saves lot of GPU memory, as Figure demonstrates.
EXPERIMENTS
In this section, we conduct extensive experiments on real-world datasets to evaluate the performance of Coarformer. All the experiments conducted on machine with NVIDIA RTX 2080ti GPU (11GB), Intel Xeon Platinum 8163 CPU (2.50GHz), and 400GB of RAM.
5.1 PERFORMANCE COMPARISON
Datasets. Following GPR-GNN Chien al. 2020), we conduct experiments 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 al. 2018). and five heterophilic graphs. Chameleon, Squirrel, Actor, Texas, Cornell (Rozemberezki et al. 2021 Tang et al. 2009 Pei et al.
2019 A detailed description of these datasets is provided 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%:2054 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.
5.1.1 OVERALL RESULTS
First, we aim 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) work- ing in the local view to accommodate full batch training and mini-batch training with which Transformer- based modules cooperate the global view. Meanwhile, we use Graph Transformer (GT) as local model, which attends only to its neighbors, as an alternative model in the fine- grained local view for comparison. And for global model, we adapt the Transformer-basee based module Graphormer, which achieves excellent results in OGB-LSC (Hu et al. (021), with different posi- tional 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-basee 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-Ben Bert, which uses top-k PPR of each node as candidate set; Reformer, which uses locality sensitive hash (LSH) to reduce compu-

---

Under review as a conference paper at ICLR 2022
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 | Results on the other datasets are presented in Appendix A.55T] (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 in- formation, 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 ef- fectiveness. Interestingly, although its Transformer- based module works on the original graph that provides more fine-gran ane-grained global information than 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, Coar- former outperforms the +Sparse Transformer methods. On the one hand, +Graph- Beraph-Berttt determines the candidate set for each target node by Top-k PPR in the global view, which restricts the receptive module. On the other hand, +Reformer and +Routing do not incor- field of Transformer-base porate the graph structure, making their captured information overly dependent 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 infor- mation 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- 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 consumes too much time with mini-batch training. It is worth emphasiz- ing that Coarformer significantly reduces the training time concerning the quadratic Transformer, such 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
Table I: Performance comparisons between different Transformer-ban based modules: Mean accuracy (%) + 95% confidence interval. Boldface letters are used to mark the best results. Results on more datasets are summarized at Table I Appendix AA.5.I
Cora
CiteSeer
PubMed
Chameleon
Actor
Squirrel
GraphSAGE
87.42=0.78
78.47#1.08
88.88=0.30
1..40=1.39
38.7920.66
43,9421.58
Local
GT
86.42+0.82
78.80=0.5
88.75=0.16
57.86
40.23+0.69
52.89
Graphormer (W/o)
65.29*2.35
77.54
85.35.0044
37.68&1.09
37.8840.83
25.82a1).44
Graphormer (PPR)
66.70+1.12
76.59+0.48
85.95=0.31
37.29+2.19
40.20+1.38
25.61+0.46
Global
Graphormer (SPD)
71.76+5.26
76.62+0.54
88.01=1.29
36.98+2.34
38.71+1.36
25.57=0.61
Graphormer (All)
77.41=4.30
16.1841.16
88.24=1.50
1..81+1.96
38.21=0.52
25.13=0.33
+Graphurmer (All)
88.03=00.99 98
81.23+0.555
09.65=0.37
64.20>0.57
40.05=0062
42. 10.00.007
Local
(GraphSAGE)
+Grph-Bert Bert
88, 10=0.229
80 46.061
88. 28.7000.12 12
66.54:1.09
39 99.6620.52
48.38:0.99 9.9
+Reformer
87.21=0.63
78.57+0.90
88. 78.7330.33
1.816
39 99.39=1.01
13.36=1.04
Global (Xformer)
+RT
80.31=0.34
70.6320.38
76.57=0.26
63.8340.60
40.1320.39
42.4420.64
Coarformer (-CP)
87,0020.75
77.52+0.44
88.91=0.21
60.63+1.46
38.95=0.87
40,3420.83
Coarformer
88.6920.82
79.
89.75.0.31
66.48+1.46
40.70+1.12
54.27+1.15
Table 2: Efficiency comparisons between different Transformer-basee modules: average training
time per epoch (ms)/total training time (s). Underlined letters imply results with mini-bare batch training.
Cora
CiteSeer
PubMed
Chameleon
Actor
Squirel
GripSAGGE: 3.01/0.94
4.09/1 09
4,8k/297
7.19/1 67
4.45/0.90
32,85/6. 64
+Graphormer(AIl) (All
10.09/2.11
15.22/3.17
23319. 70/6999/99999 .1
14.34/2.91
37.27/7.54
48.41/9.8. 81
+Reformer
13.71/3.84
15.57/4.05
37.05/18.46
21.53/4.85
23.72/4.79
46.82/9.51
+RT
572.48/226.31
149.96/186.34
349.41/121.71
860/4//301077
720.47/256.76
Coarformer
7.61/2.28
9.14/2.13
8.81/5.21
10.95/2.52
8.14/1.64
34.00/6.88
5.1.2 EFFECTIVENESS AND ROBUSTNESS OF COARFORMER'S GLOBAL VIEW
In the previous section, we have shown the superiority of Coarformer, where GraphSAGE is adopted as the module working in Coarformer's 's local view. To verify the generality of the benefits brought
7

---

Under review as a conference paper at ICLR 2022
GP. CranCIAC
Used GPU memory (M8)
Hox
GRU memory
10000
0
10000
GrpttAAE
3000
3000
1000
1000
-Gruph-Sent
Cuaflemnt
Drupherme +GrupheBer
(a) on Cora
(b) on Chameleon
Figure 2: Comparisons about GPU memory usage.
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 GPR- GNN are considered.
Results and Analysis. We present the results about effectiveness in Table 3 Cora, CiteSeer, PubMed, Chameleon, Actor, and Squirrel, where all the instances of Coarformer outperform their corresponding GNN models most datasets. Results other datasets presented in Ap- pendix A.5.2 Particularly, GIN performs much worse than other GNN models on several datasets, but with the global view of Coarformer, the gap significantly reduced. Furthermore, Coarformer achieves the best performance on Cora, PubMed, Computers, Photo, Chameleon, Actor, and Squir- rel. All these results confirm that the global view of Coarformer 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-baser module is in the local view, the time consumed by Coarformer remains the same order of magnitude, where the increase is negligible.
Table 3: Performance comparisons on different GNN-based module: Mean accuracy (%) 95% confidence interval. Boldface letters are used to mark the improvements. Results on more datasets are summarized at Table 13 in Appendix A.5.2
GCN
GIN
GAT
GT
APPNP
GPR-GNN
87.0640.63
84.1120.82
87.1840.66
86.42+0.82
88.10+0.73
88.48
Cora
w/
87.64+0.65
85.63+0.83
87.83+0.76
86.91=0.62
88.78+0.62
88.93+0.31
0.58
1.52
0.65
0.49
0.68
0.45
w/o
79. 29.261
74.92+1.33
79.60 79.60+0.80
78.8020.50
79.58+0.70
78.49+1.15
CiteSeer
w/
78, 78.91#1.02
78.9620.7
78.34+0.59
78.72+0.94
79.44=0,80
78.24+1.00
-0.27
4.04
-1.26
-0.08
-0.14
-0,25
w/o
86.86+0.28
88.57=0.44
12+00.2
88.75=0.16
88.35+0.25
90.90
PubMed
89.7640.41
88.5720.40
87.96+0.52
90.08+0.21
88.72+0.46
91, 91.26:40.48
2,90
0.00
1.84
1.33
0.37
0.36
w/o
58,8020.90
38 8442.55
59,41+1.55
57.8621.2
53.76
61.6311.41
Chameleon
67. 1.24
63.8542.36
67. 67.59+1.88
66.59+0.86
59.85+0.99
67.09+1.53
8.84
25.01
8.18
8.73
6.09
0.46
w/o 33.61
34.07=0.46
35. 35.7940.66 6.64
40.2320.69
39.55+1.01 00
40.7420.53
Actor
37.18+0.74
34.12+0.42
35.85+0.67
41.37=0.60
40.21+0.73
41.67+0.70
3.57
0.05
0.06
1.14
0.66
0.93
w/o 46.46+0.92
19.3240.56
48.2+1.85
52.89+0.51
36.4+1.50
52.31+1.09
Squirrel
w/ 54.75+1.12
43.13+0.69
56.23+1.22 .22
53.18+0.40
46.80+0.91
11.85
8.29
23.81
8.03
0.29
10.40
-0.46
5.2 COMPARISONS ON OGB
This experiment aims to verify the effectiveness of Coarformer on extremely large graphs.
Datasets. We adopt ogbn-arxiv and ogbn-products wherein there 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 undirected graph. Details can be found in Hu et al. (2020).
Protocol. We largely follow the experimental setup in Sec. [.I.I yet all models are learned with mini-batch training due to the scale of the adopted datasets. Specifically, employ GCN cap-
8

---

Under review as a conference paper at ICLR 2022
ture the local information in the fine- aineggrained local view, where random walk-basee GraphSAINT is used to sample subgraphs for training the GCN. Then, we regard GCN as our testbed for compar- ing Coarformer with several Transformer-based methods under our two-view architecture, including Reformer and Routing Transformer (RT). Graphormer is excluded because calculating the PPR ma- trix and the SPD matrix for such huge graphs 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 where Coarformer surpasses all the methods significantly (p-values = 0.02). The experimental results show that Coar- former 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
Table 4: Performance comparison on OGB: Mean accuracy (%) + 95% confidence interval. Boldface letters are used to mark the best results.
GCN
+Reformer
+RT
Coarformer
ogbn-arxiv ogbn-products 78.70+0.34
71.32+0.25
69.62#0.24 74.09=0.23
67.07=0.12 OOM
71.66#0.24 79.18+0.20
5.3 SENSITIVITY ANALYSIS
Since Coarformer applies the Transformer-based module on a coarse graph, a question naturally comes up 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 coarsen- ing 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 Appendix A.3.3
Results and Analysis. We present the results in Table 5 where there is no apparent difference be- tween 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 ob- tained 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 coarse graph with size n' vn, the performance of Coarformer still surpasses that of GCN/GAT. As for Chameleon, VN performs best when the corresponding n' is close to vn. As for VE and Alg JC, they also show com- petitive results. Based on these results, we recommend attempting the coarsening rate corresponding to n' around /n when applying Coarformer for large graphs.
Table 5: Sensitivity analysis: Mean accuracy (%) + 95% confidence interval. Boldface letters are used to mark the best results.
Datasets
Algorithm
GCN
0.01
GAT
GCN
GAT
GCN
GAT
GCN
GAT
88.1420.65
87.4410.62
87.772087
87.6420.57
87.8240.70
87.8720.50
89.2620.75
68.1620.62
Cora
VE
87,5920.63
87. 83
87.4420.57
87.7250.40
87.59=1.33
88.08:0.59
88 $8.9340.74
88.49:0.50
Alg. JC
87.93=0.55
$7.88+0.53
88.08=0.75
87,88:0.64
87.3240.70
88.01=0.62 62
88 88.6440.64
89.26=0.34
VN
66.9621.05
68.95+1.74
68.1821.44
67.35t1.24
63.8021.04
65.78=1.64
63.8021.23
65.80:1.27
Chameleon
VE
14.11=1.33
65. 65.27+1.61
64.5111665
64.97+1.42
65.32+1.29
65.82+1.83
66.08+1.33
66.50e 1.59
Alg JC
66.32+1.37
65.56+0.52
65.93+1440
65.8000.75
63.8621.20
65.91=1448
66.19:1.22
1..15.1.62
CONCLUSION
In this paper, we propose a novel two-view architecture Coarformer, which employs GNN-based module and Transformer-based module to encode nodes from the local and global view, respec- tively. 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 mini- batch training. Extensive experiments conducted on large real-world graphs verify the advantages of Coarformer against existing Transformer- baased 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 fully Transformer-based model for graph data.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Uri Alon and Fran Yahav. On the bottleneck of graph neural networks and its practical implications.
In International Conference on Learning Representations, 2021.
Jinheon Baek, Minki Kang, and Sung Ju Hwang. Accurate learning of graph representations with graph multiset pooling. In International Conference on Learning Representations, 2020.
Iz Beltagy, Matthew E Peters, and Arman Cohan. Longformer: The long-document transformer. arXiv preprint arXiv:2004.05/4 2020.
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovie. Adaptive universal generalized pagerank graph neural network. In International Conference on Learning Representations, 2020.
Jacob Devlin, Ming-Wes Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of NAACL-HLT, 2019.
Alexey Dosovitskiy, Lucas Beyer, Alexander Kolesnikov, Dirk Weissenborn, Xiaohua Zhai, Thomas Unterthiner, Mostafa Dehghani, Matthias Minderer, Georg Heigold, Sylvain Gelly, Jakob Uszko- reit, and Neil Houlsby. An image worth 16x16 words: Transformers for image recognition at scale. International Conference on Learning Representations, 2021.
Vijay Prakash Dwivedi and Xavier Bresson. generalization of transformer networks graphs. AAAI Workshop on Deep Learning on Graphs: Methods and Applications, 2021.
Yuwei Fang, Siqi Sun, Zhe Gan, Rohit Pillai, Shuohang Wang, and Jingjing Liu. Hierarchical graph network for multi-hop question answering. Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pp. 8823 8838, 2020.
William L Hamilton, Rex Ying, and Jure Leskovec. Inductive representation learning on large graphs. Advances in neural information processing systems, 2017.
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning graphs. Neural Information Processing Systems (NeurIPS), 2020.
Weihua Hu, Matthias Fey, Hongyu Ren, Maho Nakata, Yuxiao Dong, and Jure Leskovec. Ogb-Ise: A large-scale challenge for machine learning on graphs. arXiv preprint arXiv:2103.09430, 2021.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net-
works. In International Conference on Learning Representations, 2017.
Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. In International Conference Learning Representations, 2019.
Johannes Klicpera, Aleksandar Bojehevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In International Conference on Learning Representations, 2018.
Devin Kreuzer, Dominique Beaini, William Hamilton, Vincent Létoumeau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. arXiv preprint arXiv:2106.0388 03899, 2021.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for supervieer learning. In Thirty-Second AAAI conference on artificial intelligence, 2018.
Xiaoya Li, Yuxian Meng, Mingxin Zhou, Qinghong Han, Fei Wu, and Jiwei Li. Sac: Accelerating and structuring self-attention via sparse adaptive connection. Advances in Neural Information Processing Systems, 33, 2020.
Andreas Loukas. Graph reduction with spectral and cut guarantees. Journal of Machine Learning Research. 2019.
Julian McAuley, Christopher Targett, Qinfeng Shi, and Anton Van Den Hengel. Image- based rec- ommendations on styles and substitutes. In Proceedings of the 38th international ACM SIGIR conference on research and development in information retrieval, pp. 43-52, 2015.
10

---

Under review as a conference paper at ICLR 2022
Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford InfoLab, 1999.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In International Conference Learning Representations, 2019.
Hongyu Ren, Hanjun Dai, Zihang Dai, Mengjiao Yang, Jure Leskovec, Dale Schuurmans, and Bo Dai. Combiner: Full attention transformer with sparse computation cost. arXiv preprint arXiv:2107.05768, 2021.
Dorit Ron, Ilya Safro, and Achi Brandt. Relaxation-based coarsening and multiscale graph organi- zation. Multiscale Modeling & Simulation, 2011.
Aurko Roy, Mohammad Saffar, Ashish Vaswani, and David Grangier. Efficient content- sparse attention with routing transformers. Transactions of the Association for Computational Linguis- tics, 2021.
Benedek Rozemberczki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding. Journal of Complex Nenworks, 9())cnabb01, 2021.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Race Collective classification in network data. Al magazine, 29(3):93-93, 2008.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv:
2018
Stanislav Sobolevsky. Hierarchical graph neural networks. CoRR, abs/2105.03388, 2021. URL
https://arxiv: http//axxii.rr.reaeeeeeee/eseeee htrg//bs//211 03388
Jie Tang, Jimeng Sun, Chi Wang, and Yang. Social influence analysis in large-scale networks. In Proceedings of the 15th ACM SIGKDD international conference Knowledge discovery and data mining, pp. 807-816, 2009.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference Learning Representations, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanic Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2018.
Zhilin Yang, William Cohen, and Ruslan Salakhudinov. Revisiting semi-supervised learning with graph embeddings. In International conference on machine learning. pp. 40-48. PMLR, 2016.
Yang Ye and Shihao Ji. Sparse graph attention networks. IEEE Transactions on Knowledge and
Data Engineering, 2021.
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie Liu. Do transformers really perform bad for graph representation? arXiv preprint
arXiv:2/06.05234 05.3044 2021a.
Chengxuan Ying, Mingqi Yang, Shuxin Zheng, Guolin Ke, Shengjie Luo, Tianle Cai. Chenglin Wu, Yuxin Wang, Yanming Shen, and Di He. First place solution of kdd cup 2021 & ogb large-scale challenge graph prediction track. 2021b.
Rex Ying, Jiaxuan You, Christopher Morris, Xiang Ren, William L Hamilton, and Jure Leskovec. Hierarchical graph representation learning with differentiable pooling. In Proceedings of the 32nd International Conference Neural Information Processing Systems, pp. 4805-4815 2018.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- SAINT: Graph sampling based inductive learning method. In International Conference on Learn ing Representations, 2020.
11

---

Under review as a conference paper at ICLR 2022
Jiawei Zhang, Haopeng Zhang, Congying Xia, and Li Sun. Graph-bert: Only attention is needed for learning graph representations. arXiv preprint arXiv:2001.05140, 2020.
Kai Zhang, Yaokang Zhu, Jun Wang, and Jie Zhang. Adaptive structural fingerprints for graph attention networks. In International Conference on Learning Representations, 2019.
12

---

Under review as a conference paper at ICLR 2022
A APPENDIX
A.1 STUDY ABOUT SAMPLE COMPLEXITY
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 sev- eral them on Cora with a sparse split, i.e., 35%%%.%%:99% Except for these ratios, other settings are kept the same Sec. 5.1.1 The results are shown in Table 6 As expected, the performances of all the methods decrease when the size 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-ban based method Graphormer almost drops to only a half of that with the dense split. This phenomenon suggests higher sample complexity of Transformer compared with GNN. We also present the performances Graphormer with different Unlike the conventional cases where there are four or five heads and hidden dimension of 128/256, a relatively small capacity is suitable for Graphormer on Cora.
configurations in Table 7
Table 6: Performance comparisons on Cora with different splits: Mean accuracy (%) = 95% confi- dence interval. Boldface letters are used to mark the best results.
Split
GraphSAGE
Coarformer Graphormer
Sparse 73.72+0.89
12.47=1.40
39.67=5.66
Dense
87.42+0.78
88.69#0.82
77.41+4.30
Table 7: Details about HPO for Graphormer Cora.
(a) With sparse split (255%:2.59:959)
(b) With dense split (60%:209::0%)
#head hidden
32
64
#head hidden
32
64
39.6745.66
37.40=5.25
77.14+4.80
74.75+4.30
36.37+5.67
37.43+6.13
2
77.41+4.30
71.53+5.89
A.2 DATASETS DESCRIPTION
See Table a detailed description of the medium-sized dataset and Table 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), co- purchase graph (Computers and Photo), Wikipedia graph (Chameleon and Squirrel), actors collab- orating graph (Actor), Website graph (Texas and Cornell,, and extremely large datasets (ogbn-arxiv and ogbn- products) provided by OGB team.
Table 8: Dataset statisties
Cora
CiteSeer
PubMed
Computers
Photo
Chameleon
Actor
Squirrel
Texas
Cornell
#Nodes
2,708
3,327
19.717
13.752
7,650
2,277
7,600
5,201
183
183
#Edges
5,278
4,522
44,324
245.861
119,081
31,371
26,659
198 ,53
279
277
#Features
1,433
3,703
500
767
767
2,325
932
2,089
1,703
1,703
#Classes
7
5
5
5
A.3 EXPERIMENTAL DETAILS
A.3.1 DETAILS ABOUT PERFORMANCE COMPARISONS
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 95% confidence interval, equal to the micro-fl score when it a single-label classification, as an evaluation metric of effectiveness and the average training time evaluation metric of efficiency. In addition,
13

---

Under review as a conference paper at ICLR 2022
Table 9: OGB dataset statistics.
#Nodes
#Train
#Validation
#Test
#Edges
eeatures
#Classes
ogbn-arxiv
169,343
90,941
29,799 39,323
48,603 2,213,091
1,166,243
128
rebn-products
2,449,029
196,615
123,718,280
100
47
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 smoothing.J In particular, for APPNP and GPR-GNN, we use their optimal typer-parametee as given in the paper(Chien al. 2020). In addition, each model is trained 1,000 epochs with early stops the accuracy on the validation set does not decrease within 200 epochs.
that it is encouraged to focus the local information of each node and avoid over-
A.3.2 DETAILS ABOUT COMPARISONS ON OGB
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 GNN-based module are all the coarsening rate 0.01 on ogbn-arxiv and 0.001 on agbn-products.
A.3.3 DETAILS ABOUT SENSITIVITY ANALYSIS
We conduct experiments on typical homophilic graph, Cora, and typical heterophilic graph, Chameleon. For each coarsening algorithm, we specify different coarsening rates, where the coars- ening rate, noted c, takes value from {0.01, 0. 0.5, 1}. Meanwhile, 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.
A.4 EFFICIENCY COMPARISONS
These are the results of the efficiency of different local views of GNN- module, the average training time per epoch (ms) and average total training time (s) are reported on Table TO Table
Table[oaand
Table 10: Efficiency comparisons on homophilic graphs: Average training time per epoch (ms /total training time (s). Underlined letters indicate results under mini-batch training.
Cora
Checeerr
PunMell
Commuteers
W7
9/7
W7
WTo
970
W7
W75
W7
GCN
3.818083
10.36/2 28
4.32/0.95
7.28/1 54
4,46/0.94
10.87/233
5.3/1.25
8.62/206
4,4471.14 14
7.64/1.77
GIN
4.720099
10.41/2.21
12.36/2.99
9.92/2.11
10.29/2.11
GT
9,05/1877
14.23/2.96 96
12/2.51
18.934400 09
16.75/3.51
214464661
2512.29/520.8
2639 13/537
43.13/10.01
48.27/12.42
APPNP
5.69/1.22
8.8122066
5.81/1.77
8.712 32
5.881.28 26
9.34/2 17
6.18/18
9.38/3.2
6.061.7
8.93/3.03
GPR-GINN
6.4/1311
9.34/1.94
6.54/1.34
9.72/2.05
6.87/1.47
9.42/2.18
7,56/188
10:44/2.44 48
6,56/1.45
9.61/2.28
Table 11: Efficiency comparisons on heterophilic graphs: Average training time per epoch (ms)average total training time (s). Underlined letters indicate results under mini-batch training.
Chameleon
Actor
Squirral
Texas
Carnell
w/o
w/
w/o
w/
w/o
w
w/o
w7
w/o
GCN
4,261.011
7.151.45
4.250.87
11 11.34/2.50
4.81/1.14
7.711.56
4.358038
10.38/2.2 26
4.41.099
10.25/2.17
GIN
7,57/1.79
10.2/2.19
4.92/1_
11.32/3.09
1./199
32.79/7.98
3.28/0.67
6.96/1.41
3.3/0.68
10.57/2.33
GAT
641/1.511
10:29/2.8
13.07/2.65
13.71/2.77
6.56/1355
12.5/2.76
12.11/2.45
GT
31.46/5.36
35.64/7.2
16.29/3.3
22.08/4.59
669. 13/51440
689.16/164.63
8.86/1822
10.53/2.17
8.54/1.76
10.46/2.27
APPNP
5.65/1.16
9.582.1
6818/125 25
9/05/1 99
3,891.2
8.23/1 95
57761.18
83477 80
5.77/1 18
8.692233 39
GPR-GNN
6.72/1.54
10.15/2.05
7.19/1.59
10.3/2.5
6.35/3.81
9,07/3
6.69/1.46
9.72/2.13
6.74/1.3
9.84/2.12
A.5 SUPPLEMENTARY DATASETS EXPERIMENTAL RESULTS
In this section, we provide experimental results on the Computers, Photo, Texas and Cornell. All experimental settings consistent with section 5.1
14

---

Under review as a conference paper at ICLR 2022
A.5.1 PERFORMANCE COMPARISONS BETWEEN DIFFERENT TRANSFORMER BASED METHODS ON SUPPLEMENTARY DATASETS
Due to space limitations, we summarize the experimental results about performance comparisons between different Transformer-base methods for more datasets Table 12
Table 12: Performance comparisons between different Transformer-basel methods: Mean accuracy
(%) + 95% confidence interval. Boldface letters are used mark the best results.
Computers
Photo
Texas
Cornell
GraphSAGE
89.65=0.26
93.84+0.44 40
89.18+2.58
85.08+4.66
Local
GT
85.28+0.22
93.77:0.46
93.77+1.63
88.03+4.04
Graphormer (w/o)
80.95+2.29
82.26+1.08
37.70=29.85
54.75=31.003
Graphormer (PPR)
81.98+2.07
78.05#7.51
37.70=29.85
53.77433.21
Global
Graphormer (SPD)
80.36+1.05
80.61+4.17
38.36429.26
55.08
Graphormer (All)
80.92+1.58
83.38+2.12
37.70+29.85
55.08+31.27
+Graphommer (All)
89.18+0.20
94.8940.12
88.03+1.02
85.57+1.18
Local
+Graph-Ber
89.43+0.24
95.18=0.15
88.3620.84
83.11+2.80
(GraphSAGE)
+Reformer
88.59+0.52
94.59+0.48
86.56+2.64
83.11+4.29
+RT
88.5320.43
94.4440.26
85.57+0.76
85.9042.62
Global
Coarformer (-CP)
88 88.63+0.20
93. 93.85+0.35
86.56+3.01
84.5943.28
(Xformer)
Coarformer
89.78+0.26
94.69+0.39
89.18+2.04
88.52+2.23
A.5.2 PERFORMANCE COMPARISONS ON DIFFERENT GNN-BASED MODULE ON SUPPLEMENTARY DATASETS
Due to space limitations, we summarize the experimental results about performance comparisons on different GNN-based module for more datasets at Table [3
Table 13: Performance comparisons on different GNN-based module: Mean accuracy (%) 95% confidence interval. Boldface letters are used to mark the improvements.
GCN
GIN
GAT
GT
APPNP
GPR-GNN
w/o 83.75=0.47
58.16#1.
87.21
85.28+0.22
86.38+0.39
88.70=0.45
Computers
w/
90.0440.30
77.56+0.65
89, $9.9440.26
90.0540.33
86.8040.42
89.2440.36
6.29
19.40
2.73
4.77
0,42
0.54
w/o
90.52+0.42
39.76#1.11
91,9+0073
93.77+0044
93.38+0.40
93.90=0.43
Photo
w/
93.68+0.38
90.77+0.49
93.67+0.37
94.59+0.34
93.73+0.49
94.24=0.35
3.16
51.01
1.77
0.73
0.35
0.34
w/o
73.28+2.45
80.00#1.56
79.18+2.49
93.77+1 63
88. 88.36+2.59
91 1,4422202
Texas
w/
89.02+11.58
87.54
88.69+1.79
91.80+2.05
89.67+4.26
93.11=1.75
A
15.74
7.54
9.51
-1.97
1.31
1.63
w/o
68.03+6.33
78.69+2.36
75.90+4.48
88.03+4.044
90.00+2.7 2
89.67+2.65
Comelll
87.38+3.43
88.20+2.07
87.54+2.73
90.49+2.02
89.6 89.69+2.42
90.00+2.93
A
19.35
9.51
11.64
2.46
-0.31
1.63
15


Reviews:
[{"review_id": "e-GOZi1Hxoq", "reviewer": "Reviewer_ErXY", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "strengths\n\n1. The paper is easy to follow, the ideas combine the GNNs and Transformer is interesting, take benefits of the GNN, local aggregation and Transformer, global aggregation.\n\n2. The coarsening part is good, to reduce the complexity of the self-attention in the Transformer.\n\n3. A sampling techniques are also adopted for mini-batch training.\n\n\nWeakness:\n1. The novelty of this work is not very high, it combines a lot of existing of techniques, for example GNN, Transformer, Graph Coarsening, Sampling, PPR etc. These methods are widely explored[1, 2].  The overall design is very straightforward. Somehow I feel the model is a little heavy with more model parameters.\n\n[1] https://openreview.net/forum?id=uxpzitPEooJ\n[2] https://arxiv.org/pdf/2106.05150.pdf\n\n2. The idea of the global and long range dependecies is also widely expolited, For example \n[1] Geom-GCN: Geometric Graph Convolutional Networks\n[2] Improving Breadth-Wise Backpropagation in Graph Neural Networks Helps Learning Long-Range Dependencies\n", "summary_of_the_paper": "In this work, the authors mainly combine the GNN and Transformer to learn both local and global information in large-scale graph.", "summary_of_the_review": "In summary, I think the idea of combine GNN and Transformer is very interesting. However, the novelty of this work is very straightforward, a mixture of many existing work.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "OxULdeM7B69", "reviewer": "Reviewer_ZeUY", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strong points\n* I find the empirical part of the paper solid. Training is performed over many splits. The model is tested on several datasets and many baselines and ablations are presented.\n* The model is more memory efficient than other baselines which might be important in practical applications.\n\nWeak points:\n* Most of the results where Coarformer outperforms other baselines are not statistically significant (e.g. in Tab 1 and 3), there is usually some baseline that has mean value inside the confidence interval of Coarformer. However overall the model performs strongly and it is great that authors report the confidence intervals. \n* The idea of using hierarchical graph representations to bridge long range dependencies isn't new, however I feel that prior work isn't properly discussed, other hierarchical graph models are missing in the Related Work section. Papers like DiffPool https://arxiv.org/abs/1806.08804 are highly relevant in my opinion. Other relevant papers are e.g. https://aclanthology.org/2020.emnlp-main.710.pdf or https://arxiv.org/pdf/2105.03388.pdf \n\nQuestion:\n* Sec 3.1 --- Is use of PPR as attention bias in graph transformers new? No citation is in that paragraph.\n* Loss on coarse graph is just auxiliary, correct?\n* How does the number of Coarformer's parameters compare to other compared models? Is lower memory consumption just a function of fewer parameters or is it solely due to the different structure of the computation graph?\n* Why are you testing just transformer based architectures on the global scale? E.g. GraphSAGE can be used for both local and global level.\n\n\nPresentation improvements:\n\n* BERT (Kenton & Toutanova, 2019) is a strange citation for BERT, I was expecting Devlin et al.\n* Cite PPR.\n* Sec 3.1 says that \\Beta is a learnable param, however Sec 3.3 says it is set to 1 for simplicity. I would omit \\Beta completely since I don't see any value in it. In every formula one can add similar hparams that are set to 1 and they don't add any value to the model.\n* Related Work (no S)\n* Define HPO, I get that it is hyper param optimization but it isn't explicitly stated.\n* Cite SPD.\n* Add at least one sentence describing VN, VE and Alg JC and cite them.\n* Instead of Tab 5 a graph with 'c' on the x axis would be more appropriate. It will be easier to interpret the data and see possible trends in it.\n* Table 12, Cornell column: Coarformer is in bold even though GT has better result.", "summary_of_the_paper": "The paper proposes hierarchical neural network model for processing graphs. The lower level can use any GNN model suitable for processing smaller subgaphs of the original graph while the higher level part realized by a transformer operates on an abstracted 'coarse' graph.", "summary_of_the_review": "I am slightly leaning towards acceptance. While I think that related work should be better discussed I think that many people can be interested in low memory overhead of the model and the whole community can benefit from that.\n\n--------------- Post Rebuttal -------------------\nAfter the latest round of improvements I believe the paper is above the acceptance bar.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "IIxaTDr-WPR", "reviewer": "Reviewer_QYtX", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "### Strengths\n* Application of transformer on large-graphs with graph coarsening is a relatively undiscovered problem (though not entirely novel, see below weaknesses).\n* Information propagation across GNNs and transformer to capture both local and global information on graphs is novel and valuable.\n* The paper is well-written and easy to understand.\n\n### Weaknesses\n* Using transformer on the compressed graph is already discovered idea [1]. Specifically, [1] captures the local information on the original graph with GNNs, and then further captures the global information on the compressed graph with transformer. Also, the idea of alleviating computational complexities, both memory and time, in the paper is similar to the mentioned previous work [1].\n* In Table 2, it seems the authors do not incorporate the time for graph coarsening. If the authors compress the large graph, then the resulting computational cost for coarsening is likely to be large. What relative cost does the proposed method needs for graph coarsening?\n* In Figure 2, the authors only display the GPU memory usage of small size graphs, namely Cora and Chameleon. I think the extra memory usage required for the proposed method is relatively increasing, when we use the large-size graphs that authors tackle. Thus, since the authors target the large graphs, I recommend the authors to change the datasets in Figure 2 to larger ones, such as OGB or PubMed.\n* In Table 4, I think the experimental comparisons against baselines are not enough or entirely fair. The authors exclude the powerful transformer-based baseline, namely Graphormer, but also it seems the authors use a small number of batches for baselines (Correct me if I misunderstand).\n\n### Typos\n* In Section 3.3, I think the $\\beta$ in the sentence \"we adopt $\\beta=1$ in our experiment\" should be changed to the $\\gamma$. The $\\beta$ is already defined as the learnable parameter for the PPR matrix in Section 3.1.\n* In the caption of Table 1, \".\" is missing at the end.\n\n---\n[1] Baek et al., Accurate Learning of Graph Representations with Graph Multiset Pooling, ICLR 2021.\n\n---\n**-------------------- After rebuttal --------------------**\n\nSumming up all my reviews and follow-up comments, I think this paper is above the borderline, and I lean towards an acceptance of this work.", "summary_of_the_paper": "This paper proposes to use the transformer architecture on the coarse graph obtained from the graph coarsening algorithm.\n\nTo be more specific,\n* 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.\n* 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.\n* 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.", "summary_of_the_review": "I think this is a borderline paper, as graph coarsening to use the transformer on large graphs is not entirely novel, however, it also has clear merits: a novel scheme of information propagation across original and coarse graphs; an almost complete piece of work except for some minor issues in the weaknesses above.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "75iIFTjWJx3", "reviewer": "Reviewer_1q2q", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, this paper tackles an important question on scaling Transformer to large graphs.\nThe proposed method is technically sound. \nThe experimental results are not very strong (performance gain over baselines are marginal).\n\nWith that being said, I have the following concerns for the paper:\n\n1 The proposed Coarformer is not well motivated and seems overly complicated. \nIt seems that the main contribution is to operate the Transformer on a coarsened graph. \nThe rest of the method is quite standard.\nI think a simpler model to discuss is to use the GNN node embeddings as the input to the coarsened graph, or directly combine the predictions from both models.\n\n2 Proposition 1 is not well explained. I'm not sure why it can lead to the claim that \"Coarformer can cooperate with mini-batch training and thus is viable on large graphs\".\n\n3 How important is the graph coarsening algorithm? How scalable is the algorithm being used?\n\n", "summary_of_the_paper": "This paper proposes Coarformer, a two-view architecture that consists of a standard GNN learning pipeline, and a Transformer over a coarsened graph.\n\nThis paper represents an interesting idea that scales Transformer to large graphs.", "summary_of_the_review": "Overall, I like the motivation of the paper. The proposed methodology should be improved though. And the experimental results are not very strong.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper aims to scale transformers to large graphs. In this regard, authors propose to first obtain a "coarse" version of the large graph using existing algorithms. With reduced number of nodes in the coarse graph, we can employ the transformer efficiently to capture the global information. To capture the local information, GNNs are employed. Finally, authors carry out extensive experiments on a range of graph datasets. Also, reviewers do appreciate reporting the confidence intervals. We thank the reviewers and authors for engaging in an active discussion. Unfortunately, the reviewers are in a consensus that novelty of the proposed method is limited: it is combination of existing techniques and similar ideas have been widely used in the literature. Also, the empirical results are not very significant. Thus, unfortunately I cannot recommend an acceptance of the paper in its current form.
Decision: Reject