VCR-Graphormer: A Mini-batch Graph Transformer via Virtual Connections
Authors: Dongqi Fu
Zhigang Hua
Yan Xie
Jin Fang
Si Zhang
Kaan Sancak
Hao Wu
Andrey Malevich
Jingrui He
Bo Long
Venue: ICLR 2024 poster (2024)
Keywords: Graph Representation Learning
Graph Transformer
Primary area: learning on graphs and other geometries & topologies

Abstract: Graph transformer has been proven as an effective graph learning method for its adoption of attention mechanism that is capable of capturing expressive representations from complex topological and feature information of graphs. Graph transformer conventionally performs dense attention (or global attention) for every pair of nodes to learn node representation vectors, resulting in quadratic computational costs that are unaffordable for large-scale graph data. Therefore, mini-batch training for graph transformers is a promising direction, but limited samples in each mini-batch can not support effective dense attention to encode informative representations. Facing this bottleneck, (1) we start by assigning each node a token list that is sampled by personalized PageRank (PPR) and then apply standard multi-head self-attention only on this list to compute its node representations. This PPR tokenization method decouples model training from complex graph topological information and makes heavy feature engineering offline and independent, such that mini-batch training of graph transformers is possible by loading each node's token list in batches. We further prove this PPR tokenization is viable as a graph convolution network with a fixed polynomial filter and jumping knowledge. However, only using personalized PageRank may limit information carried by a token list, which could not support different graph inductive biases for model training. To this end, (2) we rewire graphs by introducing multiple types of virtual connections through structure- and content-based super nodes that enable PPR tokenization to encode local and global contexts, long-range interaction, and heterophilous information into each node's token list, and then formalize our $\underline{\textbf{V}}$irtual $\underline{\textbf{C}}$onnection $\underline{\textbf{R}}$anking based $\underline{\textbf{Graph}}$ Trans$\underline{\textbf{former}}$ (VCR-Graphormer). Overall, VCR-Graphormer needs $O(m+klogk)$ complexity for graph tokenization as compared to $O(n^{3})$ of previous works. The [code](https://github.com/DongqiFu/VCR-Graphormer) is provided.

Published as a conference paper at ICLR 2024
VCR-GRAPHORMER, A MINI-BATCH GRAPH TRANS- FORMER VIA VIRTUAL CONNECTIONS
Dongqi Fu", Zhigang Hual, Yan Xie Jin Fang', Si Zhang', Kaan Sancak Hao Wu!, Andrey Malevichi, Jingrui He', Bo Long'
"University of Illinois Oabbnn-Chaamaigny 'Meta AI, GGeorgia Institute of Technology
fdongqif2, Jingrui pebruijee11ng wttrii/eeiinoois.. edu, (kaan]egateo edu, { {zhua, yanxie, fangjin, si sizhang, haowul, analevich, bolong (along)emee Ameta.coo
ABSTRACT
Graph transformer has been proven as an effective graph learning method for its adoption of attention mechanism that is capable of capturing expressive represen- tations from complex topological and feature information of graphs. Graph trans- former conventionally performs dense attention (or global attention) for every pair of nodes to learn node representation vectors, resulting in quadratic computational costs that are unaffordable for large-scale graph data. Therefore, mini-batch train- ing for graph transformers is a promising direction, but limited samples each mini-batch can not support effective dense attention to encode informative repre- sentations. Facing this bottleneck, (1) we start by assigning each node token list that is sampled by personalized PageRank (PPR) and then apply standard multi- head self-attention only on this list to compute its node representations. This PPR tokenization method decouples model training from complex graph topolog- ical information and makes heavy feature engineering offline and independent, such that mini-batch training of graph transformers is possible by loading each node's token list in batches. We further prove this PPR tokenization is viable as a graph convolution network with a fixed polynomial filter and jumping knowl- edge. However, only using personalized PageRank may limit information carried by a token list, which could not support different graph inductive biases for model training. To this end, (2) we rewire graphs by introducing multiple types of virtual connections through structure- and content- based super nodes that enable PPR tokenization to encode local and global contexts, long-range interaction, and het- crophilous information into each node's token list, and then formalize our Virtual Connection Ranking based Graph Transformer (CCR-Graphormer), Overall, VCR- (CR-Graphormer needs (logk))gk)) complexity for graph tokenization as com- pared to O(z²) ) of previous works. The code is provided
INTRODUCTION
Transformer architectures have achieved outstanding performance in various computer vision and natural language processing tasks (Khan et al.) [021 Lin et al.] 2022). Then, for non-grid graph data, developing effective graph transformers attracts much research attention, and some nascent works obtain remarkable performance in graph tasks for encoding complex topological and feature information into expressive node representations via attention mechanisms, like GT (Dwivedi and Bresson 2020), Gophormer (Zhao et al. (021). Coarformer (Kuang et al. (22TI). Graphormer (Ying SAN (Kreuzer al. 2021), ). ANS-GT (Zhang al. 2022). 2022). GraphGiS (Rampásek al., NAGphormer (Chen et al. 2023). Exphormer (Shirzad et al. 2023) and etc.
al. 2021 |
2022
Viewing each node as token, most graph transformers need token-wise dense attention (or global attention) to extract expressive node embedding vectors (Müller et al.] (023). i.e., most graph trans- formers typically need to attend every pair of nodes the input graph (Dwivedi and Bresson 2020)
Mialon et al. 2021 Ying et al. 202 Kreuzer al. [02 Wu et al.) [ Chen et all] 2022 Kim
ct al. 2022 Rampásek et al. 2022; Bo et al. 2023 Ma ct al. 2023). As a consequence, dense atten- tion induces unaffordable computational resource consumption for large-scale graph data due to this quadratic complexity, which hinders graph transformers from scaling up their effectiveness. In the meanwhile, mini-batch training provides a promising direction for graph transformers. Nonetheless,
https://gii thw.. com/ Donggi Fu wt//CH-Graphoome

---

Published as a conference paper at ICLR 2024
few node (or token) samples in each batch could not fully enable the dense attention mechanism to capture enough information for each node's is representation vector, given the complex topologiaa and feature information of the whole large graph data. NAGphormer (Chen et al., 2023) is a very recent work targeting mini-batch training, which utilizes self-attention only on multiple hop aggre- gations for node's embedding vector and gets good experimental results. On the other side, the hop aggregation may not deal with global, long-range interactions, and heterophilous information well; also relies on the time-consuming eigendecomposition for the positional encoding.
To deal with this bottleneck, first, we assign each target node a token list that is sampled by person- alized PageRank (PPR). The token list consists of PPR-ranked neighbors with weights and will be self-attended by the standard transformer (Vaswani et al. 2017) to output the target node represen- tation vector. This graph tokenization operation, based on PPR, separates the complex topological data from the model training process, allowing independent offline graph feature engineering for each node, such that the mini-batch training manner for graph transformers becomes possible by loading a few node token lists in each batch and leveraging self-attention separately. We demon- strate the feasibility graph convolutional neural network, leveraging fixed polynomial filter as described in (Kipf and Welling, 2017). and incorporating the concept of "jumping knowledge' from (Xu et al., 2018). How- ever, only using personalized PageRank sample nodes can copy limited topological information into each token list, which could not support different graph inductive biases for model training. To this end, we propose to rewire the input graph by establishing multiple virtual connections for personalized PageRank to transfer local, global, long-range, and heterophilous information of the entire graph into each token list. Then, self-attention on this comprehensive token list enables good approximation of the whole graph data during each batch of training. Wrapping personalized PageRank based graph tokenization and virtual connection based graph rewiring, we obtain an effec- tive mini-batch graph transformer, called Virtual Connection Ranking based Graph Transformer
utilizing this graph tokenization-base
graph transformer as an effective
(VCR- (CC-Grrahoorme)). Comparing the (n²² complexity of NAGphormer (Chen et al. 2023) due to the eigendecomposition. the complexity of VCR VCR-Graphormer is O + klogk), where m is the number of edges in the graph and k can be roughly interpreted as the selected neighbors for each node that is much smaller than m or n.
2 PRELIMINARIES
Notation. We first summarize within context. Given an undirected and attributed graph G = (V, with [V| = n nodes and |F| = edges, denote the adjacency matrix as A E Mx the degree matrix D Rax,, the node feature matrix as X E R and the node label matrix as Y E Raxe, For indexing, we denote X(v,:) :) as the row vector and X(:,) u) as the column vector, and we use parenthesized superscript for index ( and unparenthesized superscript for power operation X
common notations here, and detailed notions will be explained
Self-Attention Mechanism. According to Vaswani et al. (2017), the standard self-attention mecha- nism deep learning module that can be expressed as follows.
QKT Vd
H' = Attention(Q.... K, V) = softmax
V Rd
(2.1)
where queries Q HWQ: Q, keys K HW k and values V HWv. H E Raxd is the input feature matrix. W Q, WK. Wr dxdd are three learnable weight matrices. H' E Roxd is the output feature matrix.
Personalized PageRank. Targeting node of interest, the personalized PageRank vector stores the relative importance of the other existing nodes by exploring the graph structure through sufficient random walk steps. The typical personalized PageRank formula can be expressed below.
== oPr + (1 (1-a)q a)q
(2.2)
where P E R is the transition matrix, which can be computed as AD (column normal- ized (Yoon et al. 2018 D AD (symmetrically normalized Klicpera et al. 2019)). is a one-hot stochastic vector (or personalized vector), and the element corresponding to the target node equals while others are O. is the stationary distribution of random walks, i.e., personalized
2

---

Published as a conference paper at ICLR 2024
PageRank vector, and a is the damping constant factor, which is usually set 0.85 for personal- ized PageRank and I for PageRank. One typical way of solving a personalized PageRank vector is power iteration, i.e. multiplying the PageRank vector with the transition matrix by sufficient times r((+1) - aPr( + (1 a)qq until convergence reaching the error tolerance.
3 EFFECTIVE MINI-BATCH TRAINING AND VCR-GRAPHORMER
In this section, we first propose a promising mini-batch way for graph transformer training and give theoretical analysis of its effectiveness. Then, we discuss its limitation and formalize an ad- vanced version, Virtual Connection Ranking based Graph Transformer (VCR-Graphormer)) De- tailed proof of the proposed theory can be found in the appendix.
3.1 PPR TOKENIZATION FOR MINI-BATCH TRAINING
To project non-Euclidean topological information into expressive embedding vectors, most graph transformers need to use dense attention on every pair of nodes in the input graph. Set the O(n²) attention complexity aside, these graph transformers need to pay attention every existing node that jeopardizes the mini-batch training for large-scale input graphs, because only few samples in each batch are hard allow dense attention to capture enough topological and feature information.
To achieve mini-batch training, graph topological and feature information should be effectively wrapped into each individual batch, and then the graph learning model can start learn on each batch. Thus, an inevitable way is to first disentangle the message passing along the topology before the model training and place the disentanglement properly in each batch. Motivated by this goal, we propose mini- batch training paradigm based on personalized PageRank (PPR) tokenization. The logic of this paradigm easy follow, which tokenizes the input graph by assigning each target node with token list Tu, This list Tv consists of tokens (nodes) that are related to the target node u. Here, we use personalized PageRank (PPR) to generate the token list. Set node u as the target, based on Eq. 2.2 we can get the personalized PageRank vector, denoted as ru- Then, we sample the top nodes in rus denoted as R. Basically, nodes in R2 together form the token list Tu. Yet, the list Tu will feed to the transformer (Vaswani et al. 2017). then the positional encoding is necessary. Otherwise, two target nodes that share the same based neighbors but differ in ranking orders will result in the identical representation vector by self-attention. Actually, PPR ranking scores (i.e., the probability mass stored in the PPR vector r..) can provide good positional encoding information. Moreover, the PPR ranking scores are personalized, which means token lists that share exactly the same entries can be discriminated by different PPR ranking scores from different target nodes. Mathematically, our general Tu more expressed as aggregated form T, T. and discrete form T Dis as follows.
T-A99- ((PX)) (u, s.t. for E [I....,L} L}
(3.1)
where X E Rg is the feature matrix, and P'X is the I-th step random walk. At the I-th step, if we decompose the summarization, the discrete form is expressed as follows.
T (X(,.)) (()),, for i R
(3.2)
where rw is the (personalized) PageRank vector at the I-th step starting from node and RS is the set containing the top is entries from r..
Based on Eq. 3.1 (or Eq. 3.2) we can reorganize the set Tu into a matrix T, E Rixd in the aggre- input T, into the standard self-attention mechanism stated in Eq. 1 and a pooling function (e.g., mean or sum) get the representation vector h, for node u. This kind of graph tokenization with the standard self-attention mechanism is viable for approximating a graph convolution neural network as stated in Theorem 3.1
gated form (or T, Rl in the discrete form) by stacking entries. Then,
Theorem 3.1 Sampling token lists through (personalized) PageRank and using token-wise self- attention on each token list, this operation equivalent to a fixed pol polmialaal filter graph convolution operation Kipf and Welling 2017) with jumping knowledge Xu et al. 2001
As stated in Theorem 3.1 the graph tokenization operation in Eq. 3.1 is viable for approximating GCN (Kipf and Welling 2017), but it is prone to have the latent incapabilities of GCN, such like
3

---

Published as a conference paper at ICLR 2024
Table 1: Four Metrics from Inductive Bias and Efficiency for Graph Tokenization Methods
Hop2Token
A Good Graph Tokenization Could
Personalized PageRank
VCR-Graphormer
Chen et al.
2023
Reflect the input graph topology
1. (local and global)
2. Support long-range interaction
3. Handle heterophily property
4. Be efficiently realized
shallow network or low-pass filter can only preserve local and homophilous information (Bo et al.) 202T but the deeper network can suffer from over-squashing problem (Topping et al., (022). Hence, the next direction is how to warp good input graph information into the token list to alleviate the aforementioned problems.
3.2 PRINCIPLES OF A "GOOD" TOKENIZATION
To solve the problems mentioned in the above subsection, in general, a good token list should contain enough information that can be generalizable to different graph inductive biases, whereas graph inductive bias refers the assumptions or preconceptions that machine learning model makes about the underlying distribution of graph data. Because we have compressed the entire graph topology and features (that are easily accessible for each node in the dense or global attention graph transformers (Dwivedi and Bresson] 2020; Mialon et al.] 2021 Ying et al., 2021] Kreuzer et al.)
2021 Wu Wu et al. [222] [hen et al. | Kim et al. 2022 Rampásek et al.) 2022 Bo et al. 2023 Ma need to enable a good approximation of the whole graph data in each sampled token list. By attending to this good approximation, the
et al. 2023)) into the token list for the mini-batch training,
self-attention mechanism can produce representative node embeddings. To define the goodness of the sampled token list, we propose at least four principles that need to be satisfied.
First, the token list of each node should reflect the local and global topological information of the input graph. For instance, starting from a target node, personalized PageRank can sample the top neighbor nodes, whose ranking can be regarded as local topology (Andersen et al. 2006). Also, if we eigendecompose the graph Laplacian matrix, the eigenvalues and eigenvectors can preserve the global topological information (Spielman 2007). Second, the information in the token list should preserve long-range interactions of the input graph. The long-range interaction problem refers to the expressive node representation sometimes relying on relatively long-distance message passing path in GNNs (Alon and Yahav [021 Dwivedi et al.) 2022; Yan et al., (023b), and just stacking more layers in GNNs is found not solving the long-range interaction need but inducing over-squashing problem due to the compressed receptive field for each node (Alon and Yahav 2021 Topppng et al. 2022 Karhadkar et al. 2023). Third, the information in the token list should have the ability to contain possible heterophilous information of the graph. The heterophily property of graphs can be interpreted as the close neighbors (c.g., connected nodes) not sharing similar content (e.g., node labels) (Bo al. 2021 Platonov et al. 2023] Yan et al. 2023a), such that structure- based message passing in GNNs alone may not fully meet downstream tasks when the topological distribution and feature distribution do not conform. Fourth, the token list should be efficiently obtained. For example, although eigendecomposition preserves graph topology, it needs O(n") computational complexity (Shi and Malik 1997). In general, the design of graph tokenization for graph transformers should avoid the problems discovered previously in GNNs. To be more specific, the list should be efficiently obtained but contain comprehensive information provide sufficient graph inductive biases for model training.
The four metrics are listed in Table where we then analyze if the related works satisfy the require- ments. The nascent graph transformer NAGphormer (Chen et al., 2023) proposes the Hop2Token method, which first performs eigendecomposition of the Laplacian matrix of the input graph and at- taches the eigenvector to each node input feature vector. Then, for a target node, the summarization of the 1-hop neighbors' feature vectors serves as the first entry in the target node's 's token list. Finally, NAGphormer uses self-attention the k-lengt token list to output the representation vector for the target node. Due to the k-hop aggregation and eigendecomposition, Hop2Token could preserve the local and global topological information of the input graph. But for the long-range interaction aware-
4

---

Published as a conference paper at ICLR 2024
super node
ardinary nade
vituaal connection
roal connection
parthlooiig
Ppt
Cane
8.4
9.5
0,100
0.8
0.10
2-3
S-hops neighbor neighbor
4-hops neightor neighoor
label
shrints nodes
lal structure oware super nodes and virtual connections
content- aware super nodes and virtual connections
Figure 1: (a) Strue and (b) Content-Aware Virtual Connections on the Same Input Graph.
ness, hop-based aggregation may diminish node-level uniqueness, and computing the polynomial of the adjacency matrix costly when k needs be considerably large. Moreover, Hop2Token pays attention to structurally close neighbors and ignores possible heterophily properties of graphs. Also, additional eigendecomposition costs cubic complexity to obtain higher performance. Personalized PageRank (as discussed in Sec.3.1) samples local neighbors for target node and overlooks global contexts, also can not support long-range interaction when necessary. Although it ignores the heterophily, the personalized ranking list can be obtained in constant time complexity (Andersen) al. 2006). Our proposed VCR- CCR-Graphormer can satisfy these four metrics in its sampled token list. Next, we introduce it with theoretical analysis.
3.3 VCR-GRAPHORE
Here, we first introduce how the token list of each node in VCR- VCR-Graphormer gets formed, and then give the theoretical analysis. In general, the token list of VCR- VCR-Graphormer consists of four components. For a target node u, the token list Tú is expressed as follows.
L 1-1+1 (EI,)) X(..).
To = (((u,)))l (P'X)(u,))) )lI
EL
(3.3)
s.t. for lE (I,...,,,,, R E R
where these four components have different views of the input graph, and each component has an initial scalar weight, i.e., 1. Also, [Tal + + k. We then introduce details of the four components. {} operator means a list. The concatenation operator applies to both scalars and vectors, i... the scalar will be converted to single-clement vector before concatenation.
The first component, X(u, :)I|1 E I2++1 is straightforward, which is the input feature of the tar- get node associated with the weight 1. The second component is designed capture the local topological information around the target node u, based on the aggregated form PPR sampling as expressed in Eq 3.1 Matrix P'X X is the 1-th step of random walks, since one more random walk step accesses 1 --hop away neighbors (Klicpera et al. (2019), those neighbors' features are aggregated based on random walk probability distribution to encode the local topological information for node u. Moreover, the given weight for P'X is distributed among walk steps by EE,
L-I+1 which means
the closer neighbors' aggregation occupies more weights.
So far, the first two components are proposed to meet the half part of the first metric in Table [ i.e., the local graph topology gets preserved in the token list. After that, the third component is responsible for recording long-range interactions and partial global information (i.c., from the node connections perspective), and the fourth component is designed to record the heterophily informa- tion and partial global information (i.e., from the node content perspective).
The third component motivated by graph rewiring, but our goal is to let the token list preserve structure-basse global information and extend the narrow receptive field of over-squashing (Alon and Yahav/ 2021) in an efficient manner. To be specific, we break the original structure by inserting several virtual super nodes into the graph adjacency matrix. To differentiate from the inserted super
5

---

Published as a conference paper at ICLR 2024
nodes, the originally existing nodes are named ordinary nodes. To do this, the input graph G is first partitioned into & clusters (e.g., using METIS partitioning algorithm (Karypis and Kumar 1998)). For each cluster, we assign super node that connects every member in this cluster, where the new edges are called structure-aware virtual connections, as shown in Figure Ta). After that,
the original adjacency matrix is transferred from A E g to A [²(==5)((++>) (m+ Note that, in A, the inter-cluster edges are retained. Comespondingly, the transition matrix for PPR is denoted as P. Then, based on P. we can get the personalized PageRank vector Fu through Eq. 2.2 Again, we sample top & items in Fu to form the set R Finally, we can obtain the complete vector of the third component, i.e., X(i, (t) E IR++1, for each node i E R. Compared with the second component, we adapt the discrete form as stated in Eq. 3.2 the third component for the following two reasons. (1) We assume the long-range interaction between nodes is represented in the form of paths other than broadcasts. Then, still concatenating all nodes from far-away hops can induce noise, but personalized PageRank is more suitable for sampling paths with corresponding weights. (2) Multiplying matrices PX as the second component will at least cost ((m) time complexity, which is linear to the number of edges. On the contrary, personalized PageRank can be completed in a constant time, which is independent of the input graph size (Andersen et al., (006). The above two reasons also apply to the design of the following fourth component.
The fourth component is designed to capture the content-based global information and encode the heterophily information into the token list. The content here refers to the labels of nodes or pseudo- labels like feature clustering and prototypes (Snell et al.) (017) when labels are not available. The realization of the fourth component is quite similar the third component. The difference is that a super node here is assigned to one kind of label in the input graphs, and then it connects every node that shares this label. Those new edges are called content-aware virtual connections, as shown in Figure [b). Note that, when the input training set has labels, the number of content-aware super nodes & equals the number of node labels c, otherwise is a hyperparameter, e.g., feature-based clusters in K -mmeass. Also, adding content-aware super nodes is based on the original adjacency matrix, i.c., A E x to A E R ((*++))((*+)))) Then, given P. the procedure of getting fu.. R and X(J, F) E Rd+1 for j E Rk. is identical to the third component.
After stacking elements in the set Tu, we get the matrix T  E (1 +)) as the input of the standard transformer, i.e., for node u, the initial input Z!! T., Then, for the t-th layer,
( (F (D)) + ? Z = MHA(LN(Z!! + - (t-1)
(3.4)
where LN stands for layer norm, FFN is feedforward neural network, and MHA denotes multi-head self-attention. To get the representation vector for node u, readout function (e.g.. mean, sum, attention) will be applied on ((1). We give the analysis of our proposed techniques in Appendix.
EXPERIMENTS
4.1
SETUP
Totally, we have 13 publicly available graph datasets included in this paper. First, as shown in Table 2 9 graph datasets are common benchmarks for node classification accuracy per- formance, 6 of them are relatively small, and 3 of them are large-scale datasets. Small datasets like PubMed, CoraFull, Computer, Photo, CS, and Physics can be accessed from the DGL library [ Reddit, Aminer, and Amazon2M are from (Fen et al. 2022] can be accessed by this link 3 Second,
Datasets.
Table 2: Graph Datasets and Statisties
PubMed
CoraFull
Computer
Photo
CS
Physics
Reddit
Aminer
Amazon2M
Nodes
19.717
19,793
13,752
7,650
18,333
34,493
232,965
593,486
2,449,029
Edges
88.651
126,842
491.722
238,163 163
163,788
495,924
11,606.919
6,217,004
31,859,140
Features
500
8,710
767
745
6.805
8,415
602
100
100
Labels
70
10
15
15
41
18
we also have 3 small heterophilous graph datasets, Squirrel, Actor, and Texas, where the connected
data. html
https://gi https///ggtthhbbboooo///////a///

---

Published as a conference paper at ICLR 2024
neighbors mostly do not share the same label (i.e., measured by node heterophily in Zhang al. 2.23)) They can also be accessed from the DGL library. For small-scale datasets and heterophilous datasets, apply 60%/20%/20% train/val/test random splits. For large-scale datasets, we follow the random splits from (Feng et al. 2022 Chen et al. 2023). Third, we also include the large-scale heterophious graph dataset, Xiv- eaa, from the benchmark (Lim al. 202T).
Baselines. Our baseline algorithms consist of 4 categories. For GNNs. we have GCN (Kipf and Welling
Table 3: Heterophilous Graph Datasets and Statistics
2017). GAT (Velickovic et al.) 2018). APPNP (Klicpera et al., (2019). and GPR-
Squirrel
Actor
Texas
Nodes
5,201
7,600
183
GNN (Chenn al.j (021). For scalable
Edges
216,933
33,544
295
GNNs, we include GraphSAINT (Zeng
Features
2,089
931
1,703
al. 2020). PPRGo (Bojchevski al. 2020 and GRAND+ (Feng et al.
Labels
Node Heterophily
0.78
0.76
0.89
2022 For graph transformers, we
have GT Dwivedi and Bresson 2020), Graphormer (Ying al., 2021). SAN (Kreuzer et al. 2021), and GraphGPS (Rampásek et al.] (2022.. As for scalable graph transformers, we have NAGPhormer (Chen al., (023) discussed above, and Exphormer (Shirzad et al. (2023) is new scalable graph transformer, which also needs relative dense attention. Additionally, we also include various baselines from (Lim al. 2021) as shown Appendix.
4.2 PERFORMANCE ON DIFFERENT SCALE DATASETS
The node classification accuracy on small-scale graph datasets and large-scale datasets among vari- ous baseline algorithms is reported in Table and Table respectively Containing more structure- aware neighbors (i.e., larger k) and more content-awe anntent-wwareeee neighbors (i.e., larger k) in the token list has the potential to increase the node classification performance. For attention efficiency, we constrain A and A to be less than 20 in VCR-Graphormer, even for large-scale datasets.
Table 4: Node Classification Accuracy on Small-Scale Datasets
PubMed
CoraFull
Computer
Photo
CS
Physies
GCN
61.76 0.14
89.63 = 0.32
92.70 = 0.20
92.92
0.12
96.18 1 0.07
GAT
86.32
64.47
0.13
93.87
0.11
93.61 0.14
96.17
GNN
APPNP
38.43-10.115
65.16 0.28
90.18 0.17
94.32
0.14
94.49:0..0
96.54 0.07
0.25
67.12
89.32
94.49 0.14
95.13
GraphSAINT
$8.9610.01
67.85
90.22
91.7221
94.41 0.09
96.43 1..0
Scalable
PPRGo
0.11
88.69 + 0.21
93.61
92.52
95.51 0.08
GNN
GRAND+
88.64 0.09
71.37
94.75
93.92
0.04
GT
0.17
61.05
91.18
94.74 0.13
94.64=0.15
97.05 0.05
Graph
Graphormer
00M
00M
OOM
92.74 0.14
0.15
OOM
Transtormer
SAN
88.22 0.15
$9.01
0.34
89,93 1: 0.16
94,86 1 0.10
94.51
OOM
GraphGPS
88.94
55.76 0.23
0OM
95.06
0.15
OOM
Scalable Graph
NAGphormer
71.51 0.19
91.22 0.14
95.75 0.1
97.34 0.03
Exphormer
89.52
69.09
0.72
91.59
0.31
95.27
0.42
95.77 = 0.15
97.16 0.13
Transformer
VCR Graphorre
89.77 1: 0.15
71.67
0.10
91.75 1 0.15
95.53 1 0.14
95.37 = 0.04
97.34 0.04
From Table our VCR-Graphormer shows the competitive performance among all baseline meth- ods. Moreover, VCR-Grrphormer does not need the consuminn eigendeconposition as another scalable graph transformer NAGPhormer Chen et al. (2023). and the corresponding structure-awant neighbors and content-aware neighbors via virtual connections can help preserve the global infor- mation. For Table 5]. VCR GraGorrphrrrrr also achieves very competitive performance with limited token length, which also demonstrates that several sampled global neighbors may not bridge the effectiveness of eigendecomposition.
4.3 PERFORMANCE ON HETEROPHHILOUS DATASETS
Since heterophilous datasets are small, we only allow CCR-Grrahoomer to take less than 10 global neighbors for Squirrel and Actor datasets, and less than 5 for Texas dataset. In Figure 2 the a-axis denotes how many hops' information can be aggregated and leveraged for the baseline algorithm. The performance in Figure F demonstrates the analysis in Table T that hop-aggregation and eigen-

---

Published as a conference paper at ICLR 2024
Table 5: Node Classification Accuracy on Large-Scale Datasets
Reddit
Aminer
Amazon2M
PPRGo
90.38 + 0.11
49,47 = 0.19
66.12 + 0.59
Scalable GNN
GraphSAINT
92.35 0.08
51.86 =
75.21 = 0.15
GRAND+
92.81 0.03
54.67 + 0.25
75.49 + 0.11
NAGphormer
93.38 = 0.05
54.04 0.16
77.43 = 0.11
Scalable Graph
Exphormer
0OM
NA4HETERO
OOM 76.09 + 0.16
Transformer
VCR- -CR-Graphormer
93.69 0.08
53.59 0.10
decomposition could not preserve the latent heterophily information very well, and content-aware neighbors though virtual connections can alleviate this problem.
0.2
Tegas
Top-4
Hagen
Popes
fop-2
Popeo
Scpm4
1pp45
Figure 2: Node Classification Accuracy on Heterophilous Datasets
4.4 ABLATION STUDY AND PARAMETER ANALYSIS
After showing the performance above, we would verify the following research questions. RQI: Does structure-awan neighbors and content-aware neighbors contribute to the performance? RQ2: Are the meaning and function of structure-aware neighbors and content-aware neighbors different and complementary? RQ3: What is the relationship among the number of structure-aware super nodes, the number of hops, and the number structure- and content-aware neighbors?
2.400
2325
2300
Craphome sructare conton: naihhors
neightoee
5225
N0-
h
tep-4
N00-5
hopm2
hcp-3
topm4
hope5
Figure 3: Ablation Study Squirrel and Actor
For RQI and RQ2, we need to investigate the role of structure- and content-aware neighbors. The het-
Group A cid, am400, 2--00 Avao
Group & L. 5-400. 20. A-20
erophilous datasets are a good fit. For example, we can see from Figure not sampling structure- and content- aware neighbors (i.c., (0, 0)) or only sampling structure- aware neighbors (i.e., (10, 0)) could not achieve the per-
mode caaoiiteronn MOUII
Eulto
43
Friss, (oaa
formance as having both (i.e., (10, 10)). For RQ3, we se- lect the large-scale dataset. Reddit. From Figure 4 we decrease I, we lose the local information and performance reduces from 93.36 to 93.02. To mitigate this local infor- mation, need to shrink the scope of structure-aware super node (i.c., increasing 3) and sample more neigh- bors, the performance increases from 93.02 93.16.
GmipA A
Seoup R
Gminn
Cosup
Figure 4: Parameter Analysis on Reddit
8

---

Published as a conference paper at ICLR 2024
5 RELATED WORK
Graph data and representation learning techniques have wide scope of applications like recom-
mendation QQi ct al. 2023 Ban et al., 2022, Wei ct al. 202I), query answering (Li et al. 2023 Liu
ct al. 2021 I Yan et al. 2021). misinformation detection (Fu et al. 2022a), time series analysis (Jing eet al. 2021). J. protein classification and generation (Fu et al. 2022b Zhou et al.) 2022). etc. Recently,
graph transformers emerged one kind of effective graph representation learning model (Müller jet al. 2023), which adapts the self-attention mechanism from transformers (Vaswani et al. (017))
graph data representation learning. For example, GT (Dwivedi and Bresson 2020) views each node in the input graph as a token and uses the self-attention mechanism to attend every pair of nodes to get the representation vectors. Then, various graph transformers are proposed following the dense attention mechanism with different positional encodings for node tokens (Mialon et al. 2021 Ying et al., 2021 Kreuzer et al., 2021 Wu et al. 2021 Chen et al. 2022 Kim et al., 2022 Rampásek et al. 2022 Bo et al. 2023 Ma et al. (023). such that the standard transformer can learn topological information during the model training. For example, in TokenGT (Kim et al. 2022). each node token is assigned augmented features from orthogonal random features and Laplacian eigenvectors, such that the edge existence can be identified by the dot product two token vec- tors. Also, GraphTrans (Wu et al. 2021) connects GNN module with the standard transformer and utilizes the GNN to provide topology-prit preseervig features to the self-attention mechanism. To re- duce the quadratic attention complexity of dense attention (or global attention). some recent works propose approximation methods (Rampásek et al.) 2022 (hirzad et al., 2023 Kong et al.) 2023). In GraphGPS (Rampásck al. 2022), the linear attention layer of Performer (Choromanski al., 2021] is proposed to replace the standard transformer layer in graph transformers but the perfor- mance gain is marginal, where the authors hypothesized that the long-range interaction generally important and cannot be easily captured in the linear attention mechanism. Exphormer (Shirzad al.] 2023) proposes using sparse attention in graph transformers, which intentionally selects sev- eral edges (e.g.. by establishing expander graphs) to execute the node-wise attention. To address the quadratic complexity, GOAT (Kong al., 2023) follows the dense attention but targets to reduce the feature dimension by finding a proper projection matrix, in order to save the efficiency. Among the above, if not all, most graph transformers are designed for graph-level tasks like graph classi- fication and graph regression (Hu et al. 2020). Targeting node-level tasks like node classification, some works are deliberately proposed (Wu et al.] [022] Chen et al.] (023). For example, NAG- phormer Chen et al. (2023) is proposed to assign each node token list, and then the self-attention mechanism is only needed for this list to get the node embedding instead of handling all existing node pairs. This paradigm promises scalability for mini-batch training of graph transformers. Based on that, in this paper, we first show why this paradigm can work well, propose the criteria of good token list for carrying various graph inductive biases, and propose the efficient and effective graph transformer, VCR- CCa-Grrahormmr.
CONCLUSION
In this paper, we propose the PageRank based node token list can support graph transformers with mini-batch training and give the theoretical analysis that the token list based graph transformer equivalent to GCN with fixed polynomial filter and jumping knowledge. Then, we propose criteria for constructing a good token list encode enough graph inductive biases for model training. Based on the criteria, we propose the corresponding techniques like virtual connections to form good token list. Finally, the proposed techniques are wrapped into an end-to-end graph transformer model, VCR- CCR-Graphormer, which can achieve outstanding effectiveness in an efficient and scalable manner.
ACKNOWLEDGEMENT
This work was partially done when the first author was research scientist intern at Meta AI. This work was also partially supported by National Science Foundation under Award No. IIS-2117902, and the U.S. Department of Homeland Security under Grant Award Number, 17STQAC00001-00 00. The views and conclusions are those of the authors and should not be interpreted as representing the official policies of the funding agencies or the government.

---

Published as a conference paper at ICLR 2024
REFERENCES
Sami Ha-aaa, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. In Kamalika Chaudhuri and Ruslan Salakhutdi- the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beuch, California, USA, volume 97 of Proceedings of Machine Learning Research. pages 29. PMLR, 2019. URL http: hattp:/pproceedinngg mir. wtw.s//ss/// abu el- hai al 9a. html
nov, editors, Pruceedings the
Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. URL
wwt.:/iwwwweeeeeeeeeeee.ee..ee forum?
18COPhOCVH2
Reid Andersen, Fan R. K. Chung, and Kevin J. Lang. Local graph partitioning using pagerank vectors. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 475-486. IEEE Computer doi: O01109/FOCS.2006 2006.44
Society, 2006.
URL https: htt////....//..111//////.//////.
Yikun Ban, Yuchen Yan, Arindam Banerjee, and Jingrui He. Ee-net: Exploitation-explrraiiee neural networks in contextual bandits. In The Tenth International Conference Learning Representations, ICLR 2022, Viriual Event, April 25-29, 2022. OpenReview.net, 2022. URL https://cppnrev///
net/ wor.morr-xxxx-oo ch3VNS
Deyu Bo, Xiao Wang. Chuan Shi, and Huawei Shen. Beyond low-frequency information in graph convolutional networks. In Thirty- Fifth AAAI Conference on Artificial Intelligence, AAAI 2021, Thirt Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Symposium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, February 2-9, 2021, pages 3950-3957 AAAI Press, 2021. doi: 10.1609/auai. htt.://aai.v355.116666. 1655.. URL https: // org 1111111111600 1609 aaal www......1111111....
Deyu Bo, Chuan Shi, Lele Wang, and Renjie Liao. Specformer: Spectral graph neural networks meet transformers. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL
het/padfidd-0past3300
Aleksandar Bojehevski, Johannes Klicpera, Bryan Perozzi, Amol Kapoor, Martin Blais, Benedek Rózemberczki, Michal Lukasik, and Stephan Günnemann. Scaling graph neural networks with approximate pagerank. In Rajesh Gupta, Yan Liu, Jiliang Tang, and B. Aditya Prakash, editors, KDD '20: The 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, CA, USA, August 23-27, 2020, pages 2464 2473. ACM, 2020. doi: 10. 00.1145/3394486.400333
URL htt.h:tts:/// :/ttps://ooi.. httgg//..11////00...... 01444/33994466343333994
Dexiong Chen, Leslie O' O'Bray, and Karsten M. Borgwardt. Structure transformer for graph representation learning. In Kamalika Chaudhuri, Stefanie Jegelka, Le Song, Csaba Szepesvári, Gang Niu, and Sivan Sabato, editors, International Conference Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 of Proceedings of Machine Learning Research. pages 3469-3488 PMLR, 2022. URL https::/ppoceeddinnnn ml .tt.ssssss./ppr..//eppm. v162 /1/2/chaee chtne2r.n22222 html
Jinsong Chen, Kaiyuan Gao, Gaichao Li, and Kun He. Nagphormer: A tokenized graph transformer for node classification in large graphs In The Eleventh International Conference on Learning Representations, ICLR 2023. Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL httts:://ppereett Bet.e//eee...eeeeooooee./.11..1.
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph con- volutional networks. In Proceedings of the 37th International Conference on Machine Learning, (CML2020 13-18 July 2020, Virtual Event, volume 119 of Proceedings of Machine Learning Re- search, pages 1725 1735. PMLR, 2020. URL BRLhttp: http://ppoceeeeng..eee mlr press/v119/ chen20v hlmll
10

---

Published as a conference paper at ICLR 2024
Eli Chien, Jianhao Peng, Pan Li, and Olgica Milenkovic. Adaptive universal generalized pagerank graph neural network. In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021.
net/ 1 d=n6 LxxP
Krzysztof Marcin Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamás Sarlós, Peter Hawkins, Jared Quincy Davis, Afroz Mohiuddin, Lukasz Kaiser, David Benjamin Belanger, Lucy J. Colwell, and Adrian Weller. Rethinking attention with per- formers, In 9th International Conference on Learning Representations, ICLR 2021, Virtual Event, Austria, May 3-7, 2021. OpenReview.net, 2021. /tt/ttps::/ /ttp:/://///peeeeeeeeeee net/ forum? CoRR, [d=Ua6zukkOWRH
Vijay Prakash Dwivedi and Xavier Bresson. generalization of transformer networks graphs. 2020.
pictts://arxtoe wttp://wwwww/////////0.5555
Vijay Prakash Dwivedi, Ladislav Rampásek, Michael Galkin, Ali Parviz, Guy Wolf, Anh Tuan Luu, and Dominique Beaini. Long range graph benchmark. In Sanmi Koyejo, S. Mo- hamed, A. Agarwal, Danielle Belgrave, K. Cho, and A. Oh, editors. Advances in Neural Information Processing Systems 35: Annual Conference on Neural Information Process- ing Systems 2022, NeurIPS 2022, New Orleans, LA. USA. November 28 December wiw.rr...iiissoom oc cc/paper files/paper/202: _nd
9. 2022, 2022.
URL
Benchmarks html
Wenzheng Feng, Yuxiao Dong, Tinglin Huang, Ziqi Yin, Xu Cheng, Evgeny Kharlamov, and Jie
Tang. GRAND+: scalable graph random neural networks. In Frédérique Laforest, Raphaël Troncy, Elena Simperl, Deepak Agarwal, Aristides Gionis, Ivan Herman, and Lionel Médini,
editors, WWW '22: The ACM Web Conference 2022, Virtual Event, Lyon, France, April 25 29, 2022, pages 3248-3258. ACM, 2022. doi: 10.14453488447.3512444
URL https:
7/doi. org. 10. 11441148554477 3512044
Dongqi Fu and Jingrui He. SDG: A simplified and dynamic graph neural network. In Fernando Diaz, Chirag Shah, Torsten Suel, Pablo Castells, Rosie Jones, and Tetsuya Sakai, editors, SIGIR '21: The 44th International ACM SIGIR Conference on Research and Development Information Retrieval, Virtual Event, Canada, July 11-15, 2021, pages 2273-2277 ACM, 2021. doi: 10.1145/ 3404835. 3463059, htttht::: 11tp://///11.111/3110001 34630559334499999
Dongqi Fu, Yikun Ban, Hanghang Tong, Ross Maciejewski, and Jingrui He. DISCO: compre- hensive and explainable disinformation detection. In Mohammad Al Hasan and Li Xiong, editors, Proceedings of the 31st ACM International Conference on Information Management, Atlanta, GA, USA, October 17-21, 2022, pages 4848 4852. ACM, 2022a. doi: TtLBttps:://et //oii. org. 144111455555 00145/55518885 3557202
Knowledge
011144//51188.35572222
Dongqi Fu, Liri Fang, Ross Maciejewski, Vetle I. Torvik, and Jingrui He. Meta-learned metrics over multi-evolution temporal graphs. In Aidong Zhang and Huzefa Rangwala, editors, KDDD '22: The 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, August 14 18, 2022, pages 367-377. ACM, 2022b. doi: (0.1145/3534678.5533333 URL https: // /oi. org 10. wttp://....1.1.33311 011114///333378835553 353933
Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs. In Hugo Larochelle, Mare' Aurelio Ranzato, Raia Hadsell, Maria-Florina Balcan, and Hsuan- Tien Lin, editors, Advances in Neural Information Processing Systems 33: Annual Conference Neural Information Processing Systems 2020, NeurIPS 2020, December 6-12, 2020, virtual, 2020. URL
wtwp://ooeeeednnn..e...e..ie...e neurips wwwpeuurpss...pppeeeeeeeeo cC/ wwtppppppe//22//aaae... html
Baoyu Jing, Hanghang Tong, and Yada Zhu. Network of tensor time series. In Jure Leskovec, Marko Grobelnik, Marc Najork, Jie Tang, and Leila Zia, editors, WWW '21: The Web Conference 2021, Virtual Event/ / Ljubljana. Slovenia, April 19-23, 2021, pages 2425-2433 ACM IW3C2, 2021. doi: 0t5.5/3444238.34449999 URL https:
3449969
11

---

Published as a conference paper at ICLR 2024
Kedar Karhadkar, Pradeep Kr. Banerjee, and Guido Montúfar. Fosr: First-order spectral rewiring for addressing oversquashing in gnns. In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL
htttps://ppenrev/ eww. net do
George Karypis and Vipin Kumar. A fast and high quality multilevel scheme for partitioning inreg- ular graphs. SIAM Sei. Comput., 20(1):55 1998. doi: 10. 10.1137/5504447755587777 URL https://do weaaii.org/i... wtt. 11..11//1114777755577777777
Salman H. Khan, Muzammal Naseer, Munawar Hayat, Syed Waqas Zamir, Fahad Shahbaz Khan, and Mubarak Shah. Transformers in vision: A survey. CoRR, abs/2101.01169 2021. URL
https: //pps:/aat //tpx/aaavvvv./.. btrg/abs/a 2201101111
Jinwoo Kim, Dat Nguyen. Seonwoo Min, Sungjun Cho, Moontae Lee, Honglak Lee, and Seunghoon Hong. Pure transformers are powerful graph learners. In NeurIPS, 2022. URL 5d8 00123116eea00005550000-0-oooooo0
html
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26. 2017, Conference Track Proceedings. OpenReview.net, 2017. URL htLhttss:
//openreview.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate: Graph neural networks meet personalized pagerank. In 7th International Conference on Learn- ing Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
URL /tRlitttpp:::/ppneeeeiie httpe/ewwwwwwwweeefeeeeeeeeeee
-
Kezhi Kong, Jiuhai Chen, John Kirchenbauer, Renkun Ni, C. Bayan Bruss, and Tom Goldstein. GOAT: global transformer on large-scale graphs. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt, Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning, ICMI. 2023, 23-29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 17375-17390, PMLR, 2023. URL press /aleess/222/// 2htmmmmma...mlm
ht https://proceeddnng
Devin Kreuzer, Dominique Beaini, William L.. Hamilton, Vincent Létourneau, and Prudencio Tossou. Rethinking graph transformers with spectral attention. In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, edi- tors, Advances in Neural Information Processing Systems 34: Annual Conference on Neu- ral Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 21618 21618-21629, 21629, 2021. URL ptLp www.inngs..uuiisi.comm cc/psscccpppeeee pttpcc/pppppe/22/////// -ttp://7777AAAbtaarataaaa
Abstract html
Weirui Kuang, WANG Zhen, Yaliang Li, Zhewei Wei, and Bolin Ding. Coarformer: Transformer for large graph via graph coarsening. 2021.
Xiang Li, Renyu Zhu, Yao Cheng, Caihua Shan, Siqiang Luo, Dongsheng Li, and Weining Qian. Finding global homophily in graph neural networks when meeting heterophily. In International Conference on Machine Learning, ICML 2022, 17-23 July 2022, Baltimore, Maryland, USA, volume 162 Proceedings of Machine Leurning Research, pages 13242-13256. PMLR, 2022. URL httt:s::/prooeeciiiii
ml.. www.pp..s.......mm.mmmmmmm 62/1122112222 html
Zihao Li, Dongqi Fu, and Jingrui He. Everything evolves in personalized pagerank. In Ying Ding, Jie Tang, Juan F. Sequeda, Lora Aroyo, Carlos Castillo, and Geert-Jan Houben, editors, Proceedings of the ACM Web Conference 2023, WWW 2023, Austin, TX. USA, 30 April 2023 4 May 2023, pages 3352-3352, ACM. 2023, doi: 10.1 00.1445/543357735844744 URL httt:p:://oi../// orq/ 10.1145/332 30055/5533530 3583474
Derek Lim, Felix Hohne, Xiuyu Li, Sijia Linda Huang, Vaishnavi Gupta, Omkar Bhalerao, and Ser-Nam Lim. Large scale learning simple methods. Advances in Neural Information Processing Systems 34: Annual Conference Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual,
homooooopilous graphs: New benchmarks and strong
12

---

Published as a conference paper at ICLR 2024
htt.::///proeedingg...ooooo..o/p hash/ http:///....11.ccc22222111111111
pages 20887- 2021. URL
Tianyang Lin, Yuxin Wang, Xiangyang Liu, and Xipeng Qiu. A survey of transformers. A/ Open, www.jaaippnn222..100. URL
3:111-132, 2022. doi:
j.aiopen. 2022 12.022.110 10.001
Lihui Liu, Boxin Du, Heng Ji, ChengXiang Zhai, and Hanghang Tong. Neural-answering logical queries on knowledge graphs. In Feida Zhu, Beng Chin Ooi, and Chunyan Miao, editors, KDD 21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtaal Event, Singapore, August 14-18, 2021, pages 1087-1097. ACM, 2021. doi: 10. 14513444447548. 3467375. URL https::/ddo org/ 0 0011444/444555 3467377777
Sitao Luan, Chenqing Hua, Qincheng Lu, Jiaqi Zhu, Mingde Zhao, Shuyuan Zhang, Xiao-Wap Chang. and Doina Precup. Is heterophily A real nightmare for graph neural networks to do node classification? CoRR, 0abs/2109.05641 2021. URL/tttts://aaxiv. http://aaaaiii..or//////2/550
05641
Liheng Ma. Chen Lin, Derek Lim, Adriana Romero-Soriano, Puneet K. Dokania, Mark Coates, Philip H. H. S. Torr, and Ser-Nam Lim. Graph inductive biases in transformers without message pass- ing. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt. Sivan Sabato, and Jonathan Scarlett, editors. International Conference on Machine Learning. ICML 2023, 23- 29 July 2023, Honolulu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Re- search, pages 23321-23337. PMLR, 2023.
URL https: httttps://prooceddingg
press/
2202/ma23c..lmm
Grégoire Mialon, Dexiong Chen, Margot Selosse, and Julien Mairal. Graphit: Encoding graph structure in transformers. CoRR, abs/2106.05667,, 2021. URL fttps://arxxv..rrt
2106.05667
Luis Müller, Mikhail Galkin, Christopher Morris, and Ladislav Rampásek. Attending to graph transformers. CoRR, abs/2302.041811 2023. doi: 1044555MarXi.22322.41111.. URL https:
//doi.org/10. 4ww.0/48555....... 2302.
2302.04181 04181
Naoto Ohsaka, Takanori Maehara, and Ken-ichi Kawarabayashi. Efficient pagerank tracking in evolving networks. In Longhing Cao, Chengqi Zhang, Thorsten Joachims, Geoffrey I. Webb, Dragos D. Margineantu, and Graham Williams, editors, Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, NSW, Australia, August 13, 2015, pages 875 884. ACM, 2015. doi: (0.114552783258.27882222 URL https: 7/doi oooi.org/10000 10. 1ee.e11111111511111 2783297
Oleg Platonov, Denis Kuznedelev, Michael Diskin, Artem Babenko, and Liudmila Prokhorenkova. A critical look at the evaluation of gnns under heterophily: Are we really making progress? In The Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1-5, 2023. OpenReview.net, 2023. URL http:::/ net/ / id=tJbbQfw-5wz 5ww
Yunzhe Qi, Yikun Ban, and Jingrui He. Graph neural bandits. In Ambuj Singh, Yizhou Sun, Le- man Akoglu, Dimitrios Gunopulos, Xifeng Yan, Ravi Kumar, Fatma Ozcan, and Jieping Ye, edi- tors, Proceedings of the 29th ACM SIGKDD Conference on Knowledge Discovery and Data Min- ing, KDD 2023, Long Beach, CA. USA, August 6-10, 2023, pages 1920-1931. ACM, 2023. doi: 10.1145//5800055359933 URL hatlhttp:://// //op::://do...// org/ / 10. 1145/ 3505555555000... 05144//3338305.55997777 3599371
Ladislav Rampásek, Michael Galkin, Vijay Prakash Dwivedi, Anh Tuan Luu, Guy Wolf, and Dominique Beaini. Recipe for general, powerful, scalable graph transformer. In NeurIPS, 2022. URL htlLhttt://pppeee wip...s...ipsppomm cc/pape Files//pperr2022/haaa 5d4834a15 11.33411191115. Tr1.5aal52111222200aaa222eeeeee3
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. In 1997 Conference Computer Vision and Pattern Recognition (CVPR '97), June 17-19, 1997, San Juan. Puerto Rico, pages 731-737. IEEE Computer Society, 1997. doi: 10. 10.1 1091//// 1997. 609407. URL https://doi org/ / 10. 1109 /0T0///PP.... 1997.609407
13

---

Published as a conference paper at ICLR 2024
Hamed Shirzad, Ameya Velingker, Balaji Venkatachalam, Danica J. Sutherland, and Ali Kemal Sinop. Exphormer: Sparse transformers for graphs. In Andreas Krause, Emma Brunskill, Kyunghyun Cho, Barbara Engelhardt. Sivan Sabato, and Jonathan Scarlett, editors, International Conference on Machine Learning, ICMI. 23-29 July 2023, Honoluuu, Hawaii, USA, volume 202 of Proceedings of Machine Learning Research, pages 31613-31633 PMLR, 2023. URL
ht https: Ttttps://proceedingg
mlr press wtt.e//ww///eeeeeeeeeeee 20202//hirzad2aaa. htm_
Jake Snell, Kevin Swersky, and Richard S. Zemel. Prototypical networks for few-shot learning. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. Vish- wanathan, and Roman Gamett, editors, Advances in Neural Information Processing Systems 30: Annual Conference on Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 4077 2017. URL |tt http:tppss//prrcceeddnngggg neur seeerrips.com cc/ html
Daniel Spielman. Spectral graph theory and its applications. 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings, pages 29-38. IEEE Computer Society, 2007. doi: N0.1109/FOCS.2000 2007.66. URL
attps://dol: org/10 1109/FOCS 2007. 66
Susheel Suresh, Vinith Budde, Jennifer Neville, Pan Li, and Jianzhu Ma. Breaking the limit of graph neural networks by improving the assortativity of graphs with local mixing patterns. In KDD '21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, Singapore, August 14-18, 2021, pages 1541- ACM, 2021. doi: 40.1145/34445443347773.
URL
Jake Topping, Francesco Di Giovanni, Benjamin Paul Chamberlain, Xiaowen Dong, and Michael M. Bronstein. Understanding over-squashing and bottlenecks on graphs via curvature. In The Tenth International Conference on Learning Representations, ICLR 2022, Virtual Event, April http://wwwwwww...rr..eeeeee wtr.morrmmmmm
25-29, 2022. OpenReview.net, 2022. URL
70m JRG
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett, editors, Advances in Neural Information Processing Systems 30: Annual Conference Neural Information Processing Systems 2017, December 4-9, 2017, Long Beach, CA, USA, pages 5998 6008, 2017. URL /tR//httpp::/prrcedinngg neur neur ips. cc pttppp//pp1///aaa////// Abseee4aaaeaaaabssaaaaaaae html
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Liò, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Representations, ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018. URL wwt.hhtpp/...
Tianxin Wei, Fuli Feng, Jiawei Chen, Ziwei Wu, Jinfeng Yi, and Xiangnan He. Model-agnostic counterfactual reasoning for eliminating popularity bias in recommender system. In Feida Zhu, Beng Chin Ooi, and Chunyan Miao, editors, KDD '21: The 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Virtual Event, Singapore, August 14-18, 2021, pages 1791-1800. ACM, 2021. doi: 10.1145/344558.3447799 URL httpt:::////mm /oii orq/10. 7145/3447548.4 3467289
Felix Wu, Amauri H. Souza Jr., Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q. Weinberger. Simplifying graph convolutional networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov, editors, Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, volume 97 of Proceedings of Machine Learn- ing Research, pages v97 /wt//w/leee html
PMLR, 2019. URLhttt:://oooeeaaaee mlr press/
Qitian Wu, Wentao Zhao, Zenan Li, David P. Wipf. and Junchi Yan. Node- former: A scalable graph structure learning transformer for node classification. In NeurIPS, 2022. URL
at URL http::///pppeee......oppp
14

---

Published as a conference paper at ICLR 2024
Zhanghao Wu, Paras Jain, Matthew A. Wright, Azalia Mirhoseini, Joseph E. Gonzalez, and lon Stoica. Representing long-range context for graph neural networks with global attention. In Mare' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 13266-13279, 2021, URL https: http::::://ccceeeddeeeee neurips htcplipp..ccppppee cc/paper/2021/ hash/ hts5://6e771bb1000ee433333333333
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In Jennifer G. Dy and Andreas Krause, editors, Proceedings of the 35th International Conference
Machine Learning, ICML 2018, Stockholmsmüssaan, Stockholm, Sweden, July 10-15, 2018, volume 80 of Proceedings of Machine Learning Research, pages 5449-5458. PMLR, 2018. URL http:// proceedi ngs ml r.ll.. www.presssvee. vvnsss/vv/// / xu 2c.
Yuchen Yan, Lihui Liu, Yikun Ban, Baoyu Jing, and Hanghang Tong. Dynamic knowledge graph alignment. In Thirty-Fifth AAAI Conference on Artificial Intelligence, AAAI 2021. Thirty-Third Conference on Innovative Applications of Artificial Intelligence, IAAI 2021, The Eleventh Sym- posium on Educational Advances in Artificial Intelligence, EAAI 2021, Virtual Event, Febru- ary 2-9, 2021, pages 4572-4572. AAAI Press, 2021. doi: 10.1609/AAALLV3355...66 URL https: /ww. /ttt::://dooooog/1000 1609 aaai. 135515165583
Yuchen Yan, Yuzhong Chen, Huiyuan Chen, Minghua Xu, Mahashweta Das, Hao Yang, and Hang- hang Tong. From trainable negative depth to edge heterophily in graphs. Alice Oh, Tris- tan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Ad- vances in Neural Information Processing Systems 36: Annual Conference on Neural Infor- mation Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023a. URL
n http://pppppcppppeeeeeeeeeeeeeee fi wwtp://fweeeeeeeeeeeeeeeeeaaeeee /hahh/ html]
Yuchen Yan, Baoyu Jing, Lihui Liu, Ruijie Wang, Jinning Li, Tarek F. Abdelzaher, and Hang- hang Tong. Reconciling competing sampling strategies of network embedding. In Alice Oh, Tristan Naumann, Amir Globerson, Kate Saenko, Moritz Hardt, and Sergey Levine, editors, Advances in Neural Information Processing Systems 36: Annual Conference on Neural Infor- mation Processing Systems 2023, NeurIPS 2023, New Orleans, LA, USA, December 10 16, 2023, 2023b. URL http: http:: pwwprsappappsaaappaaa wtwppppccppppppep files/ htt.apppeeeiieeeeeppe/////////// 15dc2344ea
html]
Yujun Yan, Milad Hashemi, Kevin Swersky, Yaoqing Yang, and Danai Koutra. Two sides of the
same coin: Heterophily and oversmoothing in graph convolutional neural networks. In IEEE International Conference on Data Mining, ICDM 2022, Orlando, FL, USA, November 28 Dec. 1, 2022, pages 1287-1292, IEEE, 2022. doi: 10. 110/ICDM554444222000000 URL https: 7/dei.org 10. 1109/ ICDM5 2022. 00169
Chengxuan Ying, Tianle Cai, Shengjie Luo, Shuxin Zheng, Guolin Ke, Di He, Yanming Shen, and Tie-Yan Liu. Do transformers really perform badly for graph representation? In Marc' Aurelio Ranzato, Alina Beygelzimer, Yann N. Dauphin, Percy Liang, and Jennifer Wortman Vaughan, editors, Advances in Neural Information Processing Systems 34: Annual Conference on Neural Information Processing Systems 2021, NeurlPS 2021, December 6-14, 2021, virtual, pages 28877-28888 2021. URL wtttttt:t////ooeoee ngs neurips. cc/ htcc/paper/222111 ohtpaaaaeeeeccccedddeeeeeaaaaaaa Abstract.htm.
Minji Yoon, Woojeong Jin, and U Kang. Fast and accurate random walk with restart on dy- namic graphs with guarantees. In Pierre-Antoine Champin, Fabien Gandon, Mounia Lalmas, and Panagiotis G. Ipeirotis, editors, Proceedings of the 2018 World Wide Web Conference on World Wide Web, WWW 2018, Lyon, France, April 23-27, 2018, pages 409 418. ACM. 2018a. doi: 10. 02.11453317887..2 3166177 TRR.htts:: 118888888888111118888 1186107
Minji Yoon, Jinhong Jung, and Kang. TPA: fast, scalable, and accurate method for approximate random walk with restart on billion scale graphs. In 34th IEFE International Conference on
15

---

Hierarchi- Published as a conference paper at ICLR 2024
Data Engineering, ICDE 2018, Paris, France, April 16-19, 20/8. pages 1132-1143 IEEE Com- puter Society, 2018b. doi: 10.1009/CDDE2218.000055 URL hatpss:/ wttp://.rrr..........0
ICDE.2018.. 00103
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor K. Prasanna. Graphsaint: Graph sampling based inductive learning method. In 8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26-30, 2020. OpenRe-
view.net, 2020.
net httt://orrummm..ddeBp......
Shuaicheng Zhang, Haohui Wang, Si Zhang, and Dawei Zhou. Gpatcher: A simple and adaptive MLP model for alleviating graph heterophily. CoRR, abss2330.114400 2023. doi: 10.48550/arXiv. 2306.14340. URL https::t////// org/ 185550arrXi 2306. 14340
Zaixi
Zhang, Qi Liu, Qingyong Hu, and Chee-Kong Lee. graph
cal
transformer with adaptive node sampling. http:/ppppr...is.ccoom htppppppccccppee..ieee////////// http://///...oo......aaaaaaaaaaa html
In NewrIPS, 2022.
URL
854
Jianan Zhao, Chaozhuo Li, Qianlong Wen, Yiqi Wang, Yuming Liu, Hao Sun, Xing Xie, and Yan- fang Ye. Gophormer: Ego-graph. transformer for node classification. CoRR, abs/2110.13094 2021. URL wtthttt///axii....t.
abs 22100.10313
Dawei Zhou, Lecheng Zheng, Dongqi Fu, Jiawei Han, and Jingrui He. Mentorgnn: Deriving cur- riculum for pre- pre-training gnns. In Mohammad Al Hasan and Li Xiong, editors, Proceedings of the 31st ACM International Conference on Information Knowledge Management, Atlanta, GA, ACM, 2022. doi: 10.1145/351 101333333388.33.333... URL
USA, October 17-21, 2022, pages
APPENDIX
6.1 PROOF OF THEOREM 3.1
According to (Kipf and Welling 2017), given undirected graph G with nodes, the correspond- ing graph convolution operation on a signal matrix X E Ruxdd defined as
Xgs(A)U'x= U _ U
(6.1)
where L = I- E R is the normalized Laplacian matrix, A E Raxa is the adjacency matrix, and D Rxx the diagonal degree matrix. Then, U Raxa is the matrix containing cigenvectors of Laplacian matrix L and A e R=x" is the diagonal matrix storing the corresponding cigenvalues.
Based on ( UT extending the above equation can get
Ugj(A R
(6.2)
k=
Then, Kipf and Welling (011)) approximately take K = 1, Ou 20, and 02 -0, obtain
Ugo 0(I + D 3 AD X
(6.3)
Finally, replacing I + D D AD above by P = (D 1) (A + I)(D + 1)- -, the final format
of graph convolution operation is
H ((+1) = (PH
(6.4)
where t is the index of the graph convolution layer, H X. and o is a non-linear activation function.
16

---

Published as a conference paper at ICLR 2024
Removing the linerinear activation function at each intermediate layer (Wu al. 2019). the final representation output Z of a T -layer graph convolution neural network can be rewritten as
Z = o (P"xe ..... e ) oo(p'
(6.5)
which shows the above-approximated equation is GCN with fixed polynomial filter, which is also the second component our Eq. 3.3 The only difference is that, the second component of Eq. 3.3 keeps multiple t {1 {1..... T), Le., IP'X,''X, P'X], which corresponding to Jumping Knowledge (Xu et al. 2018) to learn representations of different orders for different graph substructures through the attention pooling.
Moreover, for personalized PageRank, P'X can be replaced as a(I - (1 (A + -))- if sufficiently large for convergence; otherwise, it can be obtained iteratively by H(t+1) (1 a))HH( + aX, where H = X, which is
(1-a) + (1 (pr)-pp-lx- +1-
(6.6)
6.2 THEORITICAL ANALYSIS OF VCR- OCR-GRAPHORMER
Remark 6.1 After inserting (structure- or content-aware) super nodes, towards a target ordinary node, the remaining ordinary nodes can be classified into two categories. The first category consists of the nodes whose shorlest puth to the larget node gets decreased. The second category consists of the nodes whose shortest path to the targel node remains. We name the first category as brightened ordinary nodes and the second category faded ordinary nodes. Faded ordinary nodes denote the local neighbors of the target node, because they are originally two-hop accessible nodes. Brightened ordinary nodes consist of the remaining ordinary nodes in the graph.
After inserting (structure- or content- -waae)) super nodes and changing the original transition matrix P into new P, the probability mass of personalized (e.g. starting from node u) PageRank transforming from faded ordinary nodes to brightened ordinary nodes is the summation of all negative entries in the vector a Li a² a'Pi(P- P)r, where x is the PageRank vector on the original graph P. Correspondingly, all the positive entries are received mass for brightened ordinary nodes. Vector will converge to constant vector and the sum of vector c is O.
Theorem 6.1
The general insights from Theorem 6.1 show the probability mass transfer from faded ordinary nodes to brightened ordinary nodes, which further illustrates that previous hardly-reachable nodes obtaining weight extend the narrow receptive field.
6.2.1 1 PROOF OF THEOREM 6.
We first introduce solution for exactly solving personalized PageRank vector, called cumulative power iteration (Yoon et al. 2018b), which is expressed as follows.
( = (a:P)(1 a)) a)q
(6.7)
0=0
where P = AD- is the column normalized transition matrix, is the one-hot stochastic vector, and r is the personalized PageRank vector. The exactness proof of the above solution can be referred to (Yoon et al. 2018b).
Now, suppose we have an original graph whose transition matrix is denoted as P. After inserting some super nodes, we have the new graph whose transition matrix denoted as P. For dimension consistency, view the added super nodes as dangling nodes in the original graph, which has no connecting edges.
For the original transition matrix P, can have the personalized PageRank vector denoted Also, for the new transition matrix P. we can have the personalized PageRank vector denoted as ř. Next, given our vector E a' PP P)r, we need to prove that F + Since vectors and are non negative personalized PageRank vector, i..., [|]] = |||||] = 1, then the sum of vector is 0.
17

---

Published as a conference paper at ICLR 2024
Motivated by Theorem 3.2 in Yoon et al. 20188), we next expand vector Ei c'Pi(P-P))
a c PP P)r
(PP)tt)
Σ
(1P)(1 (1))(1-a)q)
7 (aPiit) (1)(())))-(())))))))))))))))))))
- -oaa)a (1
1=0
/=
20 -
(aP) [1 (1PP)-
(aP) +
aPP) (aP) - -ajg)a
Y=U
j=0
aPP
(aP) a)q
Σ
(aP) Σ (oP Σ (aP) aag
j=0
1=0
2 Σ
0 (aP) aaq
(aP) a)q
(aP)
Σ (ap) aqq Σ (PP) aaq
j=0
5=
j=0
8
Σ =
(aP)(1
ooq +
(aP)(11-)))
==
(6.8)
Then, based Eq. 6.7 it can be observed that r= Moreover, since |P| |||]| 1, then converge to a constant.
Theorem 6.2 The efficiency of getting the token list in VCR-Graphormer is O(m + klogk), where
m is the number of edges the inpul graph G, and k mar(NNN((..) NNZ((f)), where NNZ(-) denotes the number of non-zero entries in a vector The complexity of self-attention in VCR-
Graphormer is O((1 + + k k))) based on Eq. 3.3
The general insights from Theorem 6.2 state the computational complexity of the proposed graph transformer, which is less than the quadratic attention complexity of most graph transformers.
6.2.2 PROOF OF THEOREM 6.2
For getting the token list stated in Eq, 3.3 computing the second component i.e., PX costs ((m), where m is the number edges in the input graph. Then, for computing the third and the fourth components, the analysis is similar. Taking the third component computation have below analysis. First, using Metis (Karypis and Kumar 1998) to partition the input graph into arbitrary clusters costs (m), suppose the number of nodes n. is smaller than the number of edges m, and the number of partitions s is way smaller than the number of edges m
example,
Second, approximately solving the personalized PageRank with Push Operations complexity (Lemma 2 in (Andersen et al., 2006) and Proposition 2 in (Ohsaka et al. 2015)) which constant is only related to error tolerance and dumping factor a but the size of the input graph. We denote the constant as с in the following. Since Push Operation (Andersen et al., (006) is local operation, most entries in the PageRank vector r, are zero (or near zero and can omitted). Denote the number of non-zero entries in as k. then sorting them costs Okklogk). For each node E (1...., n). we totally need O(n c klogk). Since each node's personalized PageRank computation is independent, we can parallelize the computation (Fu and He, 2021). Denote we have w parallel workers, the final complexity O e klogk). When number workers is sufficient, can have (klogk).
constant time
6.3 HETEROPHILOUS EXPERIMENTS ON LARGE-SCALE DATASETS
The heterophilous arxiv-year data is from the benchmark (Lim et al. 202T), the performance is based on the given split of the benchmark. In addition the baselines provided by the benchmark like
http: //gl: aros. dtc. umn wttp://ee/////hcc/////////111/11
18

---

Published as a conference paper at ICLR 2024
MixHop (Abu-El-Haijal al. 2019), GCNII (Chen al.
2020). GPR-GNN (Chien et al. 2021
include other heterophilous graph deep learning methods WRGAT (Suresh et al. (021), GGCN Yan
et al. )022), ACM-GCN (Luan et al. 2021). GloGNN (Li et al. 2022) and GloGNN++ (Li al.
2022
Table 6: Node Classification Accuracy Large- Scale Heterophilous Graph Dataset (Without Minibatching)
arXiv-year
Edge Homophily
0.22
#Nodes
169.343
#Edges
1,166,243
Table 7: Node Classification Accuracy on Large- Scale Heterophilous Graph Dataset (With Mini- batching)
#Features
128
#Classes
5
MLP
36.70 0.21
L Prop 1-hop
43.42 + 0.17
arXiv-year
L Prop 2-hop
46.07 + 0.15
Edge Homophily
0.22
LINK
53.97 0.18
#Nodes
169,343
SGC 1-hop
32.83 0.13
#Edges
1,166,243
SGC 2-hop
9.00
#Teatures
128
C&S I-hop
44.51
#Classes
5
C&S 2-hop
49.78 0.26
MI.P Minibatch
36.89 0.11
GCN
46.02 + 0.26
LINK Minibatch
53.76 + 0.28
GAT
4
SCNJK-Cluste
44.05 - 0.11
GCNJK
46.28 0.29
44.30 1:00:000 0.22
GATJK
3.80
47.40
APPNP
38.15 = 0.26
MixHop-Cluse -luustrrr
48.41 1
G₂GCN
49.09 0.10
44.84 0.18
MixHop
51.81 + 0.17
MiXHop-SAINTTRRW
50.55 + 0.20
GPR-GNN
45.07 + 0.21
LINKX Minibatch
53.74 + 0.27
GCNII
47.21 + 0.28
VCR- CCR-Graphormer
54.15 + 0.09
WRGAT
OOM
GGCN
OOM
ACM-GCN
47.37 + 0.59
LINKX (Minibatch)
53.74 + 0.27
GloGNN
54.68 +: 0.34
GloGNN+
54.79 0.25
VCR- (CR-Graphormeer
54.15 + 0.09
6.4 EFFICIENCY COMPARISON
On the largest dataset Amazon2M, we did the efficiency comparison. The eigendesompostion is based on DGL. library. DGL. itself a Python library, but its underlying computations may involve languages like C and C++ and high-performance linear algebra libraries like SciPy and Fortran to ensure efficient numerical computations. Even without strong support, our PageRank sampling realized by Python (with parallel computing theoretically designed in the paper) is slightly faster. Moreover, the reason why the content- based virtual node sampling is faster (i.e., ~~60 v.s. 4409) that the number of content-based based virtual super nodes depends on the number of labels, which is usually less than the number of structure- based virtual super nodes. Hence, its PPR convergence is faster. The below time consumption contains the METIS partitioning time realized by DGL.
Table 8: Time Consumption on Amazon2M Dataset
Method
Time (8)
Eigendecomposition (by DGL library)
~682
Virtual Structure Node based Parallel PageRank Sampling for Each Node (by Python)
~620
Virtual Content Node based Parallel PageRank Sampling for Each Node (by Python)
400
19

---

Published as a conference paper at ICLR 2024
6.5 IMPLEMENTATION DETAILS
For the second component in Eq. 3.3 we used the symmetricalyy normalized transition matrix D- AD- For the thrid and fourth component in Eq. 3.3 we used row normalized transition matrix P D-1A A. Also, for connecting content-based super nodes, we only use the label of the training set. The experiments are performed on Linux machine with single NVIDIA Tesla V100 32GB GPU.
Reddit dataset is previously existing dataset extracted and obtained by third party that contains preprocessed comments posted on the social network Reddit and hosted by Pushshift.i..
20


Reviews:
[{"review_id": "RiwKbPUaaj", "reviewer": "Reviewer_jsyZ", "summary": "The paper proposes VCR-Graphormer, which resolves the computational challenges of graph transformers in large-scale graphs. The authors tokenize nodes using personalized PageRank (PPR), enabling mini-batch training. Additionally, they introduce virtual connections in the graph to encode local and global contexts, long-range interactions, and heterophilous signals. This approach reduces computational complexity and outperforms or is on par with existing methods in node classification across 12 datasets.", "questions": "N/A", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "The scalable graph transformer is a hot, interesting, and important field in our research community. Training with mini-batches is memory-efficient by nature. The experiments are extensive (but focus on homophilous datasets). The proposed method outperforms baselines by a large margin, especially for heterophilous graphs.", "weaknesses": "- The paper is hard to follow. Abuse of notations in Eq 3.1, 3.2, and 3.3 might be confusing for readers. Please formally define the operations or use well-known operations. Is {.} a set or a list? Please proper set-builder notations. Please put l (l-th step) to the name of the variable, r_u? Is the concatenation operator applied to both scalars and vectors? The cardinality of T_u in Eq 3.3 is 4 when you note it like this. Plus, it would be nice if the authors explained what insights we can see in a series of theorems 3.2 and 3.3.\n- The eigendecomposition is not a core component in NAGphormer. NAGphormer without structural encoding has shown no bad results. We can choose other cheap structural encodings rather than eigendecomposition, for example, PPR vectors as the authors say. Thus, the superiority of the proposed method against NAGphormer (e.g., cubic complexity) should be rewritten focusing on the core components (Hop2Token).\n- The performance increase in homophilous and large-scale datasets is marginal. VCR-Graformer's additional modules do not seem to be effective for these datasets. Instead, the proposed method is effective for heterophilous datasets. However, these datasets are small-scale thus, only evaluating small parts of this model (that targets large-scale graphs). It would be nice if the authors can use large-scale heterophilous datasets [Lim, Derek, et al.]. In addition, experiments to evaluate modeling long-range dependency (the third component) are not conducted.\n- Runtime evaluation on efficiency is required. Although the time complexity is decreased in theory, the actual computations can be increased by METIS and PPR on three types of graphs.\n\n## References \n- [Lim, Derek, et al.] Lim, Derek, et al. \"Large scale learning on non-homophilous graphs: New benchmarks and strong simple methods.\" Advances in Neural Information Processing Systems 34 (2021): 20887-20902.", "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": "", "extra_scores": {}}, {"review_id": "rma2mxozH0", "reviewer": "Reviewer_82Qp", "summary": "In this work the authors propose a way for effective mini-batch training of graph transformers. In their approach, namely Virtual Connection Ranking Graph Transformer (VCR-Graphformer), they build a special token list for each input target node as input to a transformer. This list consists of four components including: \n- (1) the node features of the target node, \n- (2) propagated features for a number of random walk steps and features of nodes with top Personalized PageRank (PPR) when PPR is run on extended graphs (rewiring) with extra virtual nodes connected to original nodes either \n- (3) in the same cluster (structure-based global information) or\n- (4) carrying the same label (content-based global information). \n\nThey provide theoretical justification for their direction, experiment with their mini-batching approach over a collection of small, large and heterophilous graph datasets, employing various Graph Neural Network (GNN) and Graph Transformer (GT) architectures as baselines, and report on (a) superior competitive node classification accuracies for their VCR-Graphormer and (b) ablation studies clarifying the role of components in the token list and parameter choices.", "questions": "- VCR-Graphormer seems to be an input preprocessing technique (preparation of the token list for input to standard transfromer layers as in Eq (3.4)) that is compatible with the target training mode (mini-batching) rather than a graph transformer architecture (which is what the reader would possibly expect when coming across the term \"VCR-Transformer\"). Perhaps emphasizing this view early in the presentation would be beneficial in comprehending the overall idea?\n\n- Do you identify any obstacles for this technique being effective for other (large-scale) graph learning tasks (not node classification)? \n\n- VCR-Graphormer supports effective heterophilous graph node label learning through one of its token list components. Would this also promote homophilous graph learning?\n\nMinor/typos\n- Page 3: share the exactly same -> share exactly the same\n- Page 7: eigendecompostion -> eigendecomposition\n- Page 9: strcuture -> structure\n- Page 9: Targeting node-level tasks like graph classification -> ? (graph classification is not a node-level task)", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The presentation is easy to follow and the intuition of the approach well supported.\n\n- Types, number of datasets and baseline models are adequate for demonstrating the efficacy of the approach for the node classification task in particular. Ablation studies are very informative (Figures 3 and 4).", "weaknesses": "- The inclusion of additional graph learning tasks (edge/graph classification) would further establish the validity/generality of the token list preparation approach proposed.", "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": "", "extra_scores": {}}, {"review_id": "2DiiXPCYAN", "reviewer": "Reviewer_5Wvh", "summary": "To scale the Transformer to large graphs, this paper proposes a new graph Transformer, called VCR-Graphormer. The key idea of the proposed method is to sample a token list constructed by related nodes on graphs for each target node. In this way, the mini-batch training strategy could be adopted to reduce the training cost. Moreover, the authors leverage techniques like PPR and virtual connections to preserve both local, global, long-range, and heterophilous information.", "questions": "1.\tI think the proposed method belongs to the line of designing scalable graph Transformers via node sampling. Hence, several necessary studies [1,2,3] on this research topic should be cited and discussed in the paper. [1] and [3] leverage various node sampling strategies to obtain the token list for each node, where a super node-based strategy is also adopted in [3] to preserve the global information. [2] leverage the graph partition-based strategy to reduce the training cost of the Transformer model. These researches are highly related to the proposed method, especially [1] and [3]. \n2.\tBased on Q1, I think it is necessary to compare the performance of the proposed method with [1] and [3] to demonstrate the superiority of the proposed method for constructing the node sequence.\n3.\tI think the results on heterophilous graph datasets are inefficient in demonstrating that the proposed method can handle graphs with heterophily. Important baselines [4,5,6] and datasets [7, 8] are not considered in the experiment. In addition, [8] has revealed the drawbacks of the Squirrel dataset. Hence, experiments on heterophilous graph datasets need to be reorganized to support the claim of handling heterophily property. \n4.\tSimilarly, the authors have highlighted that efficiency is one of the important metrics for graph tokenization methods. So, the necessary experiment is required to support the above claim.\n5. Does the sampling node set of the third component contain super nodes? If the answer is yes, how do you initialize the features of super nodes?\n\n\n\n[1] Zhao et al. Gophormer: Ego-Graph Transformer for Node Classification. arXiv 2021.\n\n[2] Kuang et al. Coarformer: Transformer for large graph via graph coarsening. arXiv 2021.\n\n[3] Zhang et al. Hierarchical graph transformer with adaptive node sampling. NeurIPS 2022. \n\n[4] Bo et al. Beyond Low-frequency Information in Graph Convolutional Networks. AAAI 2021.\n\n[5] Chien et al. Adaptive universal generalized pagerank graph neural network. ICLR 2022.\n\n[6] Li et al. Finding Global Homophily in Graph Neural Networks When Meeting Heterophily. ICML 2022.\n\n[7] Lim et al. Large Scale Learning on Non-Homophilous Graphs: New Benchmarks and Strong Simple Methods. NeurIPS 2021.\n\n[8] Platonov et al. A critical look at the evaluation of GNNs under heterophily: are we really making progress? ICLR 2023.", "limitations": "", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "1.\tThis paper summarizes four metrics for graph tokenization methods.\n2.\tThis paper leverages existing techniques, like PPR and the graph partition method, to generate the token list for each target node.\n3.\tThis paper provides several theoretical analyses for the proposed method.\n4.\tEmpirical results on different scale datasets seem to indicate the promising performance of the proposed method.", "weaknesses": "1.\tSeveral recent studies on designing graph Transformers with node sampling or node clustering are ignored.\n2.\tExperimental results are inefficient in demonstrating the merits of the proposed method.", "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": "", "extra_scores": {}}, {"review_id": "NaY5wkwUFG", "reviewer": "Reviewer_QU1U", "summary": "This work try to combine PPR and transformer together to perform mini-batch training.", "questions": "1. The novelty of this work is not high, as it mainly combines random walk with attention. Tokenize the graph to sequence use random walk is common used. \n\n2. The code is not provided, its reproducibility is unclear.", "limitations": "", "rating": 5, "confidence": 5, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "1. The paper aims to solve the mini-batch training of graph transformer.\n\n2. the paper is well written and easy to follow.\n\n3. The performance of this work is good, comparing to the baseline.", "weaknesses": "1. The novelty of this work is not high, as it mainly combines random walk with attention. Tokenize the graph to sequence use random walk is common used. \n\n2. The code is not provided, its reproducibility is unclear.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)