NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification
Authors: Qitian Wu
Wentao Zhao
Zenan Li
David Wipf
Junchi Yan
Venue: NeurIPS 2022 Accept (2022)
Keywords: Graph Neural Networks
Graph Transformers
Large Graphs
Node Classification
Scalability
Graph Structure Learning

Abstract: Graph neural networks have been extensively studied for learning with inter-connected data. Despite this, recent evidence has revealed GNNs' deficiencies related to over-squashing, heterophily, handling long-range dependencies, edge incompleteness and particularly, the absence of graphs altogether. While a plausible solution is to learn new adaptive topology for message passing, issues concerning quadratic complexity hinder simultaneous guarantees for scalability and precision in large networks. In this paper, we introduce a novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes, as an important building block for a new class of Transformer networks for node classification on large graphs, dubbed as NodeFormer. Specifically, the efficient computation is enabled by a kernerlized Gumbel-Softmax operator that reduces the algorithmic complexity to linearity w.r.t. node numbers for learning latent graph structures from large, potentially fully-connected graphs in a differentiable manner. We also provide accompanying theory as justification for our design. Extensive experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs (with up to 2M nodes) and graph-enhanced applications (e.g., image classification) where input graphs are missing. The codes are available at https://github.com/qitianwu/NodeFormer.

NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification
Qitian Wu', Wentao Zhao', Zenan Li', David Wipf', Junchi Yan'-
Department of Computer Science and Engineering, Shanghai Jiao Tong University
AAmazon Web Service, Shanghai Al Lab {echo740, perrannent,emiyann , yanjunchi unchi]@e @s jsjtu. edu. cn, davidwipf@gmail..om
Abstract
Graph neural networks have been extensively studied for learning with inter- connected data. Despite this, recent evidence has revealed GNNs' deficiencies related to over-squashing, heterophily, handling long-range dependencies, edge incompleteness and particularly, the absence of graphs altogether. While a plausible solution is to learn new adaptive topology for message passing, issues concerning quadratic complexity hinder simultaneous guarantees for scalability and precision in large networks. In this paper, we introduce novel all-pair message passing scheme for efficiently propagating node signals between arbitrary nodes, as an important building block for a pioneering Transformer-style network for node classification on large graphs, dubbed as NODEFORMER. Specifically, the efficient computation is enabled by kernerlized Gumbel-Softmax operator that reduces the algorithmic complexity to linearity w.r.t. node numbers for learning latent graph structures from large, potentially fully-connected graphs in a differentiable manner. We also provide accompanying theory as justification for our design. Extensive experiments demonstrate the promising efficacy of the method in various tasks including node classification on graphs (with up to 2M nodes) and graph graph-enhanced applications (c.g.. image classification) where input graphs are missing. The codes are available at
Introduction
Relational structure inter-connecting instance nodes as graph is ubiquitous from social domains (e.g., citation networks) to natural science (protein-protein interaction), where graph neural networks (GNNs) 22 T9
[4] 36 have shown promising power for leveraging such data dependence as geometric priors. However, there arises increasing evidence challenging the core GNN hypothesis that propagating information along observed graph structures will necessarily produce better node- level representations for prediction on each individual instance node. Conflicts with this premise lead to commonly identified deficiencies with GNN geessag-passsiggg rules w.r.t. heterophily (53) etc.
over-squashing 2 long-range dependencies
[ and graph incompleteness
Moreover, in graph-enhanced applications, e.g., text classification 46, vision navigation 12] physics simulation 60] etc., graph structures are often unavailable though individual instances are strongly inter-correlated. A common practice is to artificially construct graph via some predefined rules (e.g.. k-NN), which is agnostic to downstream tasks and may presumably cause the misspecification of GNNs' inductive bias input geometry (induced by the local feature propagation design).
Natural solutions resort to organically combining learning optimal graph topology with message passing. However, one critical difficulty is the scalability issue with O(N2) (where N denotes
Wentao Zhao and Zenan Li contribute equally. The SJTU authors are also with MoE Key Lab of Artificial Intelligence, SJTU. Junchi Yan is the correspondence author who is also with Shanghai AI Laboratory.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

#nodes) computational complexity, which is prohibitive for large networks (with 10K ~ 1M nodes). Some existing approaches harness neighbor sampling [5], anchor-based adjacency surrogates and hashing schemes 4 to reduce the overhead; however, these strategies may sacrifice model precision and still struggle to handle graphs with million-level nodes. Another obstacle lies in the increased degrees of freedom due to at least an N x N all-pair similarity matrix, which may result in large combinatorial search space and vulnerability to over-fitting.
In this work, we introduce a novel all-pair message passing scheme that can scale to large systems without compromising performance. We develop a kernelized Gumbel-Softmax operator that seam- lessly synthesizes random fa feature map [77 and approximated sampling strategy [16), for distilling latent structures among all the instance nodes and yielding moderate gradients through differentiable optimization. Though such combination of two operations involving randomness could potentially result in mutual distortion, we theoretically prove that the new operator can still guarantee well- posed approximation for concrete variables (discrete structures) with the error bounded by feature dimensions. Furthermore, such a design can reduce the algorithmic complexity of learning new topology per layer to O(N) by avoiding explicit computation for the cumbersome all-pair similarity,
The proposed module opens the door to a new class of graph networks, i.e., NODEFORMER (Scalable Transformers for Node Classification), that is capable of efficiently propagating messages between arbitrary node pairs in flexible layer-specific latent graphs. And to accommodate imput graphs (if any), we devise two simple techniques: a relational bias and an edge-level regularization loss, as guidance for properly learning adaptive structures. We evaluate our approach on diverse node classification tasks ranging from citation networks to images/texts. The results show its promising power for tackling heterophily, long-range dependencies, large-scale graphs, graph incompleteness and the absence of input graphs. The contributions of this paper are summarized as follows:
We develop a kernelized Gumbel--Sftmax operator which is proven to serve as a well-posed approximation for concrete variables, particularly the discrete latent structure among data points. The new module can reduce the algorithmic complexity for learning new message-passingg topology from quadratic to linear w.r.t. node numbers, without sacrificing the precision. This serves as pioneering model that successfully scales graph structure learning to large graphs with million-level nodes.
We further propose NODEFORMER, a new class of graph networks with layer-wise message passing as operated over latent graphs potentially connecting all nodes. The latter are optimized in an end-to-end differentiable fashion through a new objective that essentially pursues sampling optimal topology from a posterior conditioned node features and labels. To our knowledge, NODEFORMER is the first Transformer model that scales all-pair message passing to large node classification graphs.
We demonstrate the model's efficacy by extensive experiments over a diverse set of datasets, in- cluding node classification benchmarks and image/text classification, where significant improvement over strong GNN models and SOTA structure learning methods is shown. Besides, it successfully scales to large graph datasets with up to 2M nodes where prior arts failed, and reduces the time/space consumption of the competitors by up to 93.1 93.1%/80.666 %/80.6% moderate sized datasets.
2 Related Works
Graph Neural Networks. Building expressive GNNs is a fundamental problem in learning over graph data. With Graph Attention Networks (GAT) 36 as an early attempt, there are many follow-up works, e.g., [2 42, considering weighting the edges in input graph for enhancing the expressiveness. Other focus on sparsifying input structures to promote robust representations. There are also quite a few approaches that propose scalable GNNs through, c.g., subgraph sampling 4 linear feature mapping 39,, and channel-wise transformation 49, etc. However, these works cannot learn new edges out of the scope of input geometry, which may limit the model's receptive fields within local neighbors and neglect global information.
studies, e.g.,
28 52
Graph Structure Learning. Going beyond observed topology, graph structure learning targets learning new graph for message passing among all the instances [54]] One line of work is similarity- driven where the confidence of edges are reflected by some similarity functions between node pairs,
e.g., Gaussian kernels 4.). cosine similarity 4 attention networks [17], non-linear MLP 7 etc. Another line of work optimizes the adjacency matrix. Due to the increased optimization difficulties.
some sophisticated training methods are introduced, such as bi-level optimization [I], variational

---

Table 1: Comparison of popular graph structure learning approaches for node-level tasks where in particular, the graph connects all instance nodes and one's 's target is for prediction on each individual node. For parameterization, 'Function' means learning through functional mapping and 'Adjacency' means directly optimizing graph adjacency. For expressivly, 'Fxedd' means learning one graph shared by all propagation layers and 'Layer-wise' means learning graph structures per layers. The largest demo means the largest # nodes of datasets used. i yn denotes anchors (i.e., a subset of nodes).
Models
Parameterization
Expressivity
Ioput Graphs
Inductive
Complexity
Largest Demo
LDS-GNN
1B1
Adjaceney
Fixed
Requized
No
O(N2)
0.01M
ProGNN
Adjacenyy
Fixed
Required
O(N2)
0.02M
VGCN 10
Adjaceney
Fixed
Roquired
No
OLN2)
0.02M
BGCN
51
Adjaceney
Fixed
Required
No
O(N2)
0.02M
GLCCN
Function
Fixed
necessary
O(N2)
IDGL
!
Function
Fixed
Required
Yos
O(N)) O(Nm))
0.IM
NODEFORMER (Ours)
Function
Layen-wise
Not necessary
Yes
O(N) O(E))
2M
To push further the limits of structure learning, this paper proposes a new model NODEFORMER (for enabling scalable node-level Transformers) whose merits are highlighted via a high-level comparison in Table | In particular, NODEFORMER enables efficient structure learning in each layer, does not require input graphs and successfully scales graphs with 2M nodes.
approaches 10 20 Bayesian inference [T] and projected gradient descent [
Node-Level v.s. Graph-Level Prediction. We emphasize upfront that our focus is on node-level prediction tasks involving a single large graph such that scalability is paramount, especially if we are to consider arbitrary relationships across all nodes (each node is an instance with label and one treat all the nodes non-i.i.d. generated due to the -eterddepend)cce) for structure-learning purposes. Critically though, this scenario is quite distinct from graph-level classification tasks whereby each i.i.d. instance is itself small graph and fully connecting nodes within each graph is computationally inexpensive. While this latter scenario has been explored in the context of graph structure learning KS and all-pair message passing design, e-g., graph Transformers [ existing efforts do not scale to the large graphs endemic to node-level prediction.
3 NODEFORMER: A Transformer Graph Network at Scale
Let G = EN) denote graph with .' node set ([V N) and E C N N edge set (1E) E). Each node u E N is assigned with node features x., E RR and a label yu- We define an adjacency matrix A }aue} {0, NxN where due 1 if edge (u, loss of generality, E could be an empty set in case of no input structure. There are two common settings: transductive learning, where testing nodes are within the graph used for training, and inductive learning which handles new unseen nodes out of the training graph. The target is to learn a function for node-level prediction, i.e., estimate labels for unlabeled or new nodes in the graph.
E and aue 0 otherwise. Without
General Model and Key Challenges. We start with the observation that the input structures may not be the ideal one for propagating signals among nodes and instead there exist certain latent structures that could facilitate learning better node representations. We thus consider the updating rule
( = g(A, ;ww,,
(++ = A( A, Z (000).
(1)
where (0() = {zu JUEN and A (all) JUNENN denotes the node representations and the estimated
latent graph of the (-th layer, respectively, and g. h are both differentiable functions aiming at I) structure estimation for layer-specific latent graph Á (1) based on node representations and 2) feature propagation for updating node representations, respectively. The model defined by Eqn. D follows the spirit of Transformers 335 (where in particular A (1) can be seen as an attentive graph) that potentially enables message passing between any node pair in each layer, which, however, poses two challenges:
(Scalability): How to reduce the prohibitive quadratic complexity for learning new graphs?
(Differentiability): How to enable end-to-end differeeniablee optimization for discrete structures?
Notice that the first challenge is non-trivial in node-level prediction tasks (the focus of our paper), since the latent graphs could potentially connect all the instance nodes (e.g., from thousands to millions, depending on dataset sizes), which is fairly hard to guarantee both precision and scalability.
3

---

3.1 Efficient Learning Discrete Structures
We describe our new message- paassagepassing scheme with an efficient kemelized Gumbel-Softmax operator to resolve the aforementioned challenges. We assume zi Xx as the initial node representation.
Kernelized Message Passing. We define full-graph attentive network that estimates latent in- teractions among instance nodes and enables corresponding densely-connetted message passing:
exp((W ) (W ( 2) K 20
Q 20 EN w=1 exp( 2i (2)) (T 222)
(4+1) Z
Σ
a (W 2 ()),
where W W and w are learnable parameters in I-th layer. We omit non-linearity activation (after aggregation) for brevity. The updating for N nodes in one layer using Eqn. requires prohibitive O(V2) complexity. Also, given large N, the normalization in the denominator would shrink attention weights to zero and lead to gradient vanishing. We call this problem as over-normalizing.
())
To accelerate the full- full-graph model, we observe that the dos-then-exponentiate operation in Eqn. can be converted into a pairwise similarity function:
N
x(W-l)
(1) (0)
11) !!) W
(1+1)
Z
(W ( 2!!)),
(
(1)
(1)
-
K Zu
where ni(:;)) Rd xR + R is positive-definie kernel measuring the pairwise similarity. The kernel function be further approximated by random features (RF) which serves unbiased estimation via k(a, b) = (a), b(b))y R ((a) T "(b), where the first equation is by Mercer's theorem with Φ : Rd + V a basis function and a high-dimensional vector space, and 6(.) : Rd > RT is low-dimensional feature map with random transformation. There many potential choices for o, e.g., Positive Random Features (PRF) 6
1 2
exp
(x)
[exp(w] x), ... exp (T,))),
(4)
Vm
where We ~ (O Ia) is i.idd. sampled random transformation. The RF converts dot-then- exponentiate operation into inner-product in vector space, which enables re-write Eqn.
(assuming qu = We Zu (1)
(!) k. = ( Zu and v. = w. Zu for simplicity):
(t)
( (kkk)
Vv ((qu) Ex o(k,) V..
(++1)
(5)
- (qq.) 6(kw)
(qqu) Ex= 6kkw)
The key advantage of Eqn. is that the two summations are shared by each needs to compute them once and re-used for others. Such a property enables ((N) computational complexity for full-graph message passing, which paves the way for learning graph structures among large-scale instances. Moreover, one can notice that Eqn. 5 avoids computing the N N similarity matrix, i.e., (ale) J x required by Eqn. thus also reducing the learning difficulties.
that one only
Nevertheless, Eqn. still suffers what mentioned the over-normalizing issue. The crux is that the message passing is operated on weighted fully-connected graph where, in fact, only partial edges are important. Also, such a deterministic way of feature aggregation over all the instances may increase the risk for over-fitting, especially when N is large. We next resolve the issues by distilling a sparse structure from the fully-connected graph.
Differentiable Stochastic Structure Learning. The difficultly lies in how to enable differentiable optimization for discrete graph structures. The weight =(I) given by Eqn. 2 could be used to define a categorical distribution for generating latent edges from distribution Cat( where (!) (() (1) N uu and = = p(t|2) duv- Then in principle, we can sample over the categorical distribution multiple times for each node to obtain its neighbors. However, the sampling process would introduce discontinuity and hinders back- pack-propagation. Fortunately, we notice that the Eqn. B
can be modified to incorporate the reparametrization trick (16) to allow differentiable learning:
exp((q, k. + go)/T) Vo
k(qu\/ /T, k./ TTT,KK//TTe.... (89/T
2
(1+1)
w=1 exp((q k. + g//)/T) 1=1 D k(qw// VT, kw/ VF)es Vur (6)

---

where Iu is i..dd sampled from Gumbel distribution and 7 is temperature coefficient. Equ. 6 continuous relaxation of sampling one neighbored node for u over Cat n closeness to hard discrete samples 23 Following similar reasoning as Eqn. and we can yield
(2) and T controls the
N
o(qu// (Tl / Dea 1==1 0lqu/ VF) o(kw/ VT)eoo/T
6(qu/ VT) T Ee= e (loTTo(ko/VT) V. s(qu/ (Bl//VTTTT VF)TEW e caa/T (kk// VTT
(1+1)
Zu
Eqn. achiives message passing a sampled latent graph (where we only sample once for each node) and still guarantees linear complexity as Eqn. 5 In practice, we can sample K times (e.g.. K = 5) for each node and take an average of the aggregated results. Due to space limit, we defer more details concerning the differentiable sampling-base
message passing to Appendix A Besides, in Fig. and Alg. of Appendix A we present an illustration for node embedding updating each layer, from a matrix view that is practically used for implementation.
3.2 Well-posedness of the Kernelized Gumbel-Softtax Operator
One reasonable concern for Eqn. 7 is whether the RF approximation for kernel functions maintains the well- pols-ddssdesss of Gumbel approximation for the target discrete variables. As justification for the new message-pasaeeeee -aaagggggggnngggggg function, we next answer two theoretical questions: 1) How is the approximation capability of RF for the original Does Eqn. still guarantee a continuous relaxation of the categorical distributions? We formulate the results as follows and defer proofs to Appendix B
operation with Gumbel variables in Eqn. 6 2)
Theorem 1 (Approximation Error for Softmax- Kernel). Assume |lqull and [Iooll2 are bounded by then with probability at least 1 the gap A 6 /T) o( /v// /V) - k0qu// VT, ko/ /T) ),
where d is defined by Eqn. will be bounded by O /exp((rr/m exp(Gr/T)
We can see that the error bound of RF for approximating original softmax- kernel function depends on both the dimension of feature map and temperature т. Notably, the error bound is independent of node number N, which implies that the approximation ability is insensitive to dataset sizes.
The second question is non-trivial since Eqn. 7 involves randomness of Gumbel variables Φ, which cannot be decoupled apart. We define Cue
and random transformation
o(q./vF)) olkk/ (o(k///Feeeett
Ee olqu/ /FF olkm/ VF)ee// as the result from the kernelized Gumbel-Softmax and cu.
(Guv) LV denotes the sampled edge vector for node u. We can arrive at the result as follows.
Theorem (Property of Kernelized Gumbel-Softmar Random Variables). Suppose m is sufficiently large, we have the convergence property for the kernelized Gumbel-Softmad operator
exp(qT. ko)
exp(q k.)
lim P(cue > Cuo', Vol v) +-
lim P(Ccu = 1) ΣN exp(q kw)) T-+
-== exp(q kw)
shows that when the dimension of feature map is large enough and ii) the temperature goes to zero, the distribution from which latent structures are sampled would converge to the original categorical distribution.
Remark. The two theorems imply a trade-off between RF approximation and Humbel-Softmal approximation w.r.t. the choice of A large 7 would help to reduce the burden on kernel dimension m, and namely, small 7 would require very large m guarantee enough RF approximation precision. On the other hand, if 7 is too large, the weight on each edge will converge to +. i.e., the model nearly degrades to mean pooling, while small would endow the kernelized Gumbel-Softmax with better approximation to the categorical distribution. Empirical studies on this are presented in Appendix
3.3 Input Structures as Relational Bias
Eqn. does not leverage any information from observed geometry which, however, is often recognized
important for modeling
data [3]. We therefore accommodate input topology
(if any) relational bias via modifying the attention weight as -(l) =!)) I[au. (b))).
5

---

O
((N)
C, A)
MLP
(
All-Pair
())
All-Pair
(4)
MLP
L
MP
MP
(b
(B((2)
L Y
(
Figure 1: Illustration for the data flow of NODEFORMER which takes node embedding matrix X and (optional) graph adjacency matrix as input. There are three components NODEFORMER. The first one is the all-pair message passing (MP) module (colored red) which adopts our proposed kernelized Gumbel-Softmax operator to update node embeddings in each layer with (NN) complexity. The other two components are optional based on the availability of input graphs: 1) relational bias (colored green) that reinforces the propagation weight on observed edges; 2) edge regularization loss (colored blue) that aims to maximize the probability for observed edges. These two components require (E)) complexity. The final training loss the weighted sum of the standard supervised classification loss and the edge regularization loss.
where ((4) is a learnable scalar as relational bias for any adjacent node pairs (u, v) and a a certain (bounded) activation function like sigmoid. The relational bias aims at assigning adjacent nodes in g with proper weights, and the node representations could be accordingly updated by
(L+1) zu
((+1) zu
(b")) V..
0.0
Eqn. g increases the algorithmic complexity for message passing to O(N + E), albeit within the common GNNs operating input graphs. Also, can consider higher-order adjacency as relational bias for better expressiveness at some expense efficiency, as similarly done by [1]. We summarize the feed-forward computation of NODEFORMER in Alg. 1.
same order-of-mann ofaen----magnitude
3.4 Learning Objective
Given training labels Yrr = (yu Jue,,,,,.. where Nor denotes the set labeled nodes, the common practice is maximize the observed data log-likelihood which yields supervised loss (with C classes)
C
(Y tr Y
NEr Σ
Σ
1/ log Ju.e.
where [[[-] is an indicator function. However, it may not suffice to generalize well due to that the graph topology learning increases the degrees of freedom and the number training labels is not comparable to that. Therefore, we additionally introduce an edge-level regularization:
C. = NL 1=1 (u,v)EE
Σ
du log π
(l) Nunt
(10)
where du denotes the in-degree of node u and Rue is the predicted probability for edge (u, v) at the 1-th layer. Eqn. 10 maximum likelihood estimation for edges in E, with data distribution defined
po(t|u) = -
J. aue =
(11)
0,
otherwise.
We next show how to efficiently obtain Tun- Although the feed- forward NODEFORMER computation defined by Eqn. does not explicitly produce the value for each mub.
query their values by
((W ( (W 2!!)
(4)
Q Zu
K
(12)
(W()) (1) (() IN
((W 4
(0)) K

---

GON
GAT
MaHopp
KKie
DropEdge
LDB
IDGL
NodeFormer
Cora
CiteSeer
Deazer
Actor
89
73.0
25.0
Ancuracy
Apouracy
ROC-AUG
87.5
32.5
65.0
30.0
70
60.0
Figure 2: Experimental results for node classification in transductive setting on four common datasets. The missing results on Deezer is caused by out-of outoof-mmmory (OOM).
Table 2: Testing ROC-AUC and training memory
Table 3: Testing Accuracy and training memory cost on Amazon2M with batch size 100K.
cost on NCB-Proteins with batch size 10K.
Method
ROC-AUC (%)
Train Mem
Method
Accuracy (%)
Train Mem
MLP
72.04 0:8
2.0 GB
MLP
63,46
1.4 GB
GCN
72.51 035
2,5 GB
GCN
83,90 2010
5.7 GB
SGC
70,31 025
1.2 GB
SGC
81.21 2012
1.7 GB
GraphSAINT-GCN
73.51 1.11
2.3
GraphSAINT-GGCN
83.84 0.42
2.1 GB
GraphSAINT-GAT
74.63
5.2
GraphSAINT--GAT
85.17 0.32
2.2 GB
NODEFORMER
77.45
3.2
NODEFORMER
87.85 0.24
4,0 GB
NODEFORMER-dI
75.50 0.6
3.1 GB
NODEFOR MER-dt
87.02 007
2.9 GB
NODEFORMER-ip
76.18 0.009
3,2
NODEFORMER-Ip
87.55 2011
4.0 GB
where the summation term can be re-used from once computation, is done by Eqn. and Eqn. Therefore, after once computation for the summation that requires O(N,, the computation for each Tae requires (11) complexity, yielding the total complexity controlled within ((F) (since we only need to query the observed edges). The final objective can be the combination of two: L = L. + ALe. where λ controls how much emphasis is put on input topology. We depict the whole data flow of NODEFORMER'S 's training in Fig.
4
Evaluation
We consider diverse set of datasets for experiments and present detailed dataset information in set as sigmoid function and 0.25 for all datasets. The
Appendix D For implementation, output prediction layer is one-layer MLP. More implementation details are presented in Appendix C All experiments are conducted on NVIDIA V100 with 16 GB memory.
As baseline models, we basically consider GCN 10 and GAT 36 Besides, we compare with some advanced GNN models, including JKNet and MixHop | These GNN models all rely on input graphs. We further consider DropEdge
2 and two SOTA graph structure learning methods, LDS-GNN [11 and IDGL 4 for comparison. For large-scale datasets, we additionally compare and graph-sampling model GraphSAINT [48
with two scalable GNNs, linear model SGC 39 More detailed information about these models are presented in Appendix C All the experiments are repeated five times with different initializations.
4.1 Experiments on Transductive Node Classification
We study supervised node classification in transductive setting on common graph datasets: Cora, Citeseer, Deezer and Actor. The first two have high homophily ratios and the last two are identified as heterophilic graphs [53] 21. These datasets are of small or medium sizes (with 2K~200 nodes). We use random splits with malin/valid/tssttt ratios as 50%/25%/255% For evaluation metrics, we use ROC-AUC for binary classification on Deezer and Accuracy for other datasets with more than 2 classes. Results are plotted in Fig. P and NODEFORMER achieves the best mean Accuracy/ROC- AUC across four datasets and in particular, outperforms other models by large margin on two heterophilic graphs. The results indicate that NODEFORMER can handle both homophilious and non- homophilious graphs. Compared with two structure learning models LDS and IDGL, NODEFORMER yields significantly better performance, which shows its superiority. Also, for Deezer, LDS and IDGL suffers from out-of-memory (OOM). In fact, the major difficulty for Deezer is the large
7

---

Table 4: Experimental results on semi-supervised classficiation Mini- ImageNet and 20News -Cruups where we use k-NN (with different k's) for artificially constructing an input graph.
Method
Mini-nnagalie
20Mexa-Group k
k- 10
15
20
k 5
k 15
h 20
GCN
84.86 u4z
85.61 a.a
85,93
103
85.96 a.
65.98 1 aas
64.13 cas
62.95 1
62 62.59 0.2
GAT
84.70 : 048
85.24
85.41
#:4
85.37
64.06
62.51
61.38 0s5
60.80
DropEdge
83,91 +02
85.35
2.4
85,25
85.81 =00
64.46 +0.4
64.01 =642
62,46
62.68 0.71
IDGI.
83.63 2:33
84.41
0:355
85.50
85.66
65:09 1:333
63.41 =1
61,57
2:13
62.21 2079
LDS
0OM
00M
0OM
0OM
64.70
63.51
63.51
NODEFORMER
86.77 4445
86.74
86.87 1441
86.64 0:42
66.01
1:18
65.21
64.69
1:31
64.55 0.93
MODEl'ORMER w/o graph
0:36
64.71
1
IDGL
LDS
Nodel-orme
training time (4)
10000
800
Testing time
GPU Usago
8000
0.75
6000
230
0.00
0.00
2000
2000
1000
2000
1000
2000
3000
removed nodes
removed nodes
removed nodes
Figure 3: Comparison of training/inferrnce time and GPU memory cost w.r.t. different instance
numbers (by removing a certain portion of nodes) on 20News-Groups.
dimensions of input node features (nearly 30K), which causes OOM for IDGL even with the anchor approximation. In contrast, NODEFORMER manages to scale and produce desirable accuracy.
4.2 Experiments on Larger Graph Datasets
To further test the scalability, we consider two large-sized networks, OGB-Proteins and Amazon2M, with over 0.1 million and million of nodes, respectively. DGB-Proteins is a multi-task dataset with 112 output dimensions, while Amazon2M is extracted from the Amazon Co-Purchasing network that
entails long-range dependence 13). For DGB-Proteins, we use the protocol of [15] and ROC-AUC for evaluation. For Amazon2M, adopt random splitting with 50% nodes for training, validation and testing, respectively. Due to the large dataset size, we adopt mini-but batch partition for training, which case, for NODEFORMER we only consider structure learning among nodes in random mini-batch. We use batch size 10000 and 100000 for Proteins and Amazon2M, respectively, While the mini-batch partition may sacrifice the exposure to all instances, we found using large batch size can yield decent performance, which is also allowable thanks to the O(N) complexity of our model. For example, even setting the batch size as 100000, we found NODEFORMER costs only 4GB GPU memory for training on Amazon2M. Table presents the results on OE--Proteins where for fair comparison mini-batch training is also used for other models except GraphSAINT. We found that NODEFORMER yields much better ROC-AUC and only requires comparable memory as simple GNN models. Table 3 reports the results on Amazon2M which shows that NODEFORMER outperforms baselines by large margin and the memory cost is even fewer than GCN. This shows its practical efficacy and scalability on large-scale datasets and also the capability for addressing long-range dependence with shallow layers (we use L = 3).
4.3 Experiments on Graph-Enhanced Applications
We apply our model to semi-supervised image and text classification on Mini-ImageNeet and 20News-Grone -Groups datasets, without input graphs. The instances of Mini -mageNet [37]]] are 84x84 RGB images and we randomly choose 30 classes each of which contains 600 samples for experiments. 20News -Grops e consists of nearly 10K texts whose features are extracted by TF-IDF. More details for preprocessing are presented in Appendix D Also, for each dataset, we randomly split instances into 50%/25%//25% for train/valid/test. Since there is no input graph. we use N--N (over input node features) for artificially constructing graph for enabling GNN's 's message passing and the graph-based components (edge regularization and relational bias) of NODEFORMER. Table presents the comparison results under different k's. We can see that NODEFOR MER achieves the best performance in seven cases out of eight. The performance of GNN competitors varies significantly with different & values, and NODEFORMED is much less sensitive. Intriguingly, when we do not use
8

---

the input graph, i.e., removing both the edge regularization and relational bias, NODEFORMER can still yield competitive even superior results on Mini- -maggeNet. This suggests that the k-NN graphs are not necessarily informative and besides, our model learns useful latent graph structures from data.
4.4 Further Discussions
Comparison of Time/Space Consumption. Fig. 3 plots training/inference time and GPU memory costs of NODEFORMER and two SOTA structure learning models. Compared with LDS,, NODE- FORMER reduces the training time, inference time, memory cost by up to 93.1%, 1%, 97.9%. 75.6%, respectively; compared with IDGL (using anchor-based approximation for speedup). NODEFORMER reduces the training time, inference time, memory cost by up to 61.8%, 80.8%, 80.6%, respectively.
Ablation on Stochastic Components. Table 2 and 3 also include two variants of NODEFORMER for ablation study. 1) FOREERRM replace Gumbel-Softmal by original Softmax (with temperature 1.0) for deterministic propagation; 2) NODEFORMER-DH tp:: use original Softmax with temperature set as 0.25 (the same as NODEFORMER). There is performance drop when removing the Gumbel components, which may be due to over-normalizing or over-fitting that are amplified in large datasets, as we discussed in Section 3.1 and the kernelized Humbel-Sofftas operator shows its effectiveness.
Ablation Edge Loss and Relational Bias. We study the effects of edge-level regularization and relation bias as ablation study shown in Table located in Appendix E where the results consistently show that both components contribute to some positive effects and suggest that our edge-level loss and relation bias can both help to leverage useful information from input graphs.
Impact of Temperature and Feature Map Dimension. We study the effects of 7 and m in Fig. located in Appendix E and the variation trend accords with our theoretical analysis in Section 3.2 Specifically, the result shows that the test accuracy increases and then falls with the temperature changing from low to high values (usually achieves the peak accuracy with a temperature of 0.4). that when the temperature is relatively small, the test accuracy goes high with the dimension of random features increasing. However, when the temperature is large, the accuracy would drop even with large feature dimension m. Such a phenomenon accords with the theoretical result presented in Section 3.2 For low temperature which enables desirable approximation performance for Gumbel-Softmaat then larger random feature dimension would help to produce better approximation to the original exponentiate-then-dn operator. In contrast, high temperature could not guarantee precise approximation for the original categorical distribution, which deteriorates the performance.
Besides, we
Visualization and Implications. Fig. visualizes node embeddings and edge connections (filter out the edges with weights larger than a threshold) on 20News Groups and Mini- Imagenet, which show that NODE tends to assign more weights for nodes with the same class and sparse edges for nodes with different classes. This helps to interpret why NODEFORMER improves the performance on downstream node-level prediction: the latent structures can propagate useful information to help the model learn better node representations that can be easily distinguished by the classifier. We also compare the learned structures with original graphs in Fig. 7 located in Appendix D We can see that the latent structures learned by NODEFORMER show different patterns from the observed ones, especially for heterophilic graphs. Another interesting phenomenon is that there exist some dominant nodes which are assigned large weights by other nodes, forming some vertical 'lines' in the heatmap. This suggests that these nodes could contain critical information for the learning tasks and play as pivots that could improve the connectivity of the whole system.
5 Why NODEFORMER Improves Downstream Prediction?
There remains a natural question concerning our learning process: how effective can the learned latent topology be for downstream tasks? We next dissect the rationale from a Bayesian perspective. In fact, our model induces predictive distribution p( YY A X, A) = p( A X, A A))(( X, A) where can treat the estimated graph À latent variable Specifically, p(A A) is instantiated with the structure estimation module and p( (Y| X, A) is instantiated with the feature propagation module. In principle, ideal latent graphs should account for downstream tasks and maximize the potentials
We assume one latent graph to simplify the illustration though we practically learn layer-specific graphs for each layer of NODEFORMER. The analysis can be trivially extended to such a case.

---

(a) 20Meua-Groups
(b) Mini-ImageNes
Figure 4: Visualization of node embeddings and edge connections produced by NODEFORMER on graph-enhanced application datasets. We mark the nodes with particular class with color. More comparison between the learned structures and original input graphs is presented Appendix E
of message passing for producing informative node representations. Thus, optimal latent graphs presumably come from the posterior pl Y, X, = PCYIX.AA/ppAAII... Bayes theorem. Unfortunately, such a posterior is unknown and intractable for the integration.
which given by
A Variational Perspective. An intriguing conclusion stems from another view into the learning process: we can treat the structure estimation as variational distribution of A A A) and our learning objective Section 3.4 can be viewed the embodiment of minimization problem over the predictive and variational distributions via
p g arg min - By (log poppp((Y//. A,A,X, + X, P.g
(13)
L.
where denotes the Kullback-Leible divergence. Specifically, the predictive term is equivalent to minimizing the supervised loss (with Gumbeel-Softmax surrogate for compling-basedd estimates
over (A X, A)), and the KL regularization term is embodied with the edge-level MLE loss (Eqn. 10
(if we define the prior distribution po (A|X, A) following Eqn. 11p. One may notice that Eqn. 13 essentially the Evidence Lower Bound (ELBO) for the log-like log-likelhhood log p(Y|,,A))) A).
Proposition 1. Assume can exploit arbitrary distributions over Å. When Equ. 13 achieves the optimum,, we have 1) D(g( A)] X, A)) = 0 and 2) log P A) is maximized.
The proposition indicates that our adopted learning objective intrinsically minimizes the divergence between latent graphs generated by the model and the samples from the posterior p( ((A Y X, A) that ideally helps to propagate useful adjacent information w.r.t. downstream tasks. Therefore, well-trained network of NODEFORMER on labeled data could produce effective latent topology that contributes to boosting the downstream performance.
6 Conclusion
This paper proposes a scalable and efficient graph Transformer (especially for node level) that can propagate layer-wise node signals between arbitrary pairs beyond input topology. The key module, a kernelized Gumbel-Softmax operator, enables us to learn layer-specific latent graphs with linear algorithmic complexity without compromising the precision. The results diverse graph datasets and situations verify the effecttieness,, scalability, and stability. We provide more discussions on the limitations and potential impacts Appendix
Acknowledgement
This work was partly supported by National Key Research and Development Program of China A210000))))7000), National Natural Science Foundation of China (61972250, 72061127003) and Shanghai Municipal Science and Technology (Major) Project (22511105100, 2021SHZDZX0102,,
10

---

References
[1] Sami Abu-al-Haija, 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 International Conference on Machine Learning, pages 21-29, 2019.
[2] Uri Alon and Eran Yahav. On the bottleneck of graph neural networks and its practical implications. In International Conference on Learning Representations, 2021.
[3] Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst. Geometric deep learning: going beyond euclidean data. CoRR, abs/1611 2016.
[4] Yu Chen, Lingfei Wu, and Mohammed J. Zaki. Iterative deep graph learning for graph neural networks: Better and robust node embeddings. In Advances Neural Information Processing Systems, 2020.
[5] Wii-Lin Chiang. Xuanqing Liu, Si Si, Yang Li, Samy Bengio, and Cho-Jui Hsich. Cluster-gen: An efficient algorithm for training deep and large graph convolutional networks. In ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pages 257-266, 2019.
[6] 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 Colwell, and Adrian Weller. Rethinking attention with performers. In International Conference on Learning Representations, 2021.
[7] Luca Cosmo, Anees Kazi, Jeyed-Ahmaa Ahmadi, Nassir Navab, and Michael M. Bronstein. Latent patient network learning for automatic diagnosis. CoRR, abs/2003. 2020.
[8] Hanjun Dai, Zornitsa Kozareva, Bo Dai, Alexander J. Smola, and Le Song. Learning steady- states of iterative algorithms over graphs. In International Conference on Machine Learning. pages 1114-11 122, 2018.
[9] Vijay Prakash Dwivedi and Xavier Bresson. A generalization of transformer networks to graphs. CoRR,
2020.
[10] Pantelis Elinas, Edwin V. Bonilla, and Louis C. Tiao. Variational inference for graph convolu- tional networks in the absence of graph data and adversarial settings. In Advances in Neural Information Processing Systems, 2020.
[11] Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. Learning discrete structures for graph neural networks. In International Conference Machine Learning, pages 1972-1982, 2019.
[12] Chen Gao, Jinyu Chen, Si Liu, Luting Wang. Qiong Zhang, and Qi Wu. Room-and-object aware knowledge reasoning for remote embodied referring expression. In IEEE Conference Computer Vision and Pattern Recognition, pages 3064-3073, 2021.
[13] Fangda Gu, Heng Chang, Wenwu Zhu, Somayeh Sojoudi, and Laurent El Ghaoui, Implicit graph neural networks. In Advances in Neural Information Processing Systems, 2020.
[14] William L. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In Advances in Neural Information Processing Systems. pages 1024-1034, 2017.
[15] 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 Advances in Neural Information Processing Systems, 2020.
[16] Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparamcterization with gumbel-softmat In International Conference on Learning Representations, 2017.
[17] Bo Jiang, Ziyan Zhang, Doudou Lin, Jin Tang, and Bin Luo. Semi-supervie learning with graph canningnconvolutiional networks. In IEEE Conference on Computer Vision and Pattern Recognition, pages 11313-11320, 2019.

---

[18] Wei Jin, Yao Ma, Xiaorui Liu, Xianfeng Tang, Suhang Wang, and Jiliang Tang. Graph structure learning for robust graph neural networks. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 66-74, 2020.
[19] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICIRR, 2017.
[20] Danning Lao, Xinyu Yang, Qitian Wu, and Junchi Yan. Variational inference for training graph neural networks in low-data regime through joint structure-label estimation. In ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 824-834, 2022.
[21] Derek Lim, Xiuyu Li, Felix Hohne, and Ser-Nam Lim. New benchmarks for learning on non-homophilous graphs. CoRR, abs/2104.01404, 2021.
[22] Dongsheng Luo, Wei Cheng, Wenchao Yu, Bo Zong, Jingchao Ni, Haifeng Chen, and Xiang Zhang. Learning to drop: Robust graph neural network via topological denoising. In ACM International Conference Web Search and Data Mining, pages 779-787, 2021.
[23] Chris J. Maddison, Andriy Mnih, and Yee whye Tch. The concrete distribution: A continuous re- laxation of discrete random variables. In International Conference on Learning Representations. 2017.
[24] Julian J. McAuley, Rahul Pandey, and Jure Leskovec. Inferring networks of substitutable and complementary products. In ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 785-794, 2015.
[25] Fabian Pedregosa, Gaäl Varoquaux, Alexandre Gramfort, Vincent Michel, Bertrand Thirion, Olivier Grisel, Mathieu Blondel, Peter Prettenhofer, Ron Weiss, Vincent Dubourg, et al. Scikit- learn: Machine learning in python. the Journal of machine Learning research, 12:2825-2830 2011.
[26] Hongbin Pei, Bingzhe Wei, Kevin Chen-Chune Chang, Yu Lei, and Bo Yang. Geom-gen: Geo- metric graph convolutional networks. In International Conference on Learning Representations, 2020.
[27] Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Advances in Neural Information Processing Systems, pages 1177-1184, 2007.
[28] Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In International Conference on Learning Representations, 2020.
[29] Benedek Rozemberczki and Rik Sarkar. Characteristic functions on graphs: Birds of a feather, from statistical descriptors to parametric models. In ACM International Conference on Informa- tion and Knowledge Management, pages 1325-1334, 1334, 2020.
[30] Alvaro Gonzalez, Jonathan Godwin, Tobias Pfaff, Rex Ying, Jure Leskovec, and Peter W. Battaglia. Learning to simulate complex physics with graph networks. In International Conference on Machine Learning, pages 8459-8468, 2020.
[31] Victor Garcia Satorras and Joan Bruna Estrach. Few-shot learning with graph neural networks. In International Conference on Learning Representations, 2018
[32] Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE transactions on neural networks, 20(1):61-80, 2008
[33] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi- Rad. Collective classification in network data. Mag., 29(3):93-106, 2008
[34] Rakshith Sharma Srinivasa, Cao Xiao, Lucas Glass, Justin Romberg, and Jimeng Sun. Fast graph attention networks using effective resistance based graph sparsification. CoRR, abs/2006.087%. 2020.
12

---

[35] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. Advances in neural information processing systems, 30, 2017.
[36] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representatons (ICLR), 2018
[37] Oriol Vinyals, Charles Blundell, Tim Lillicrap, Koray Kavukcuoglu, and Daan Wierstra. Match- ing networks for one shot learning. In Advances in Neural Information Processing Systems, pages 3630-3638, 2016.
[38] Yue Wang, Yongbin Sun, Ziwei Liu, Sanjay E. Sarma, Michael M. Bronstein, and Justin M. Solomon. Dynamic graph CNN for learning on point clouds. ACM Trans. Graph., 38(5):146:11 146:12, 2019.
[39] Felix Wu, Amauri H. Souza Jr., Tianyi Zhang, Christopher Fifty, Tao Yu, and Kilian Q. Wein- berger. Simplifying graph convolutional networks. In International Conference on Machine Learning, pages 6861-6871, 2019.
[40] Qitian Wu, Chenxiao Yang, and Junchi Yan. Towards open-world feature extrapolation: An inductive graph learning approach. Advances in Neural Information Processing Systems, pages 19445- 2021.
[41] Qitian Wu, Hengrui Zhang, Xiaofeng Gao, Junchi Yan, and Hongyuan Zha. Towards open- world recommendation: An inductive model-based collaborative filtering approach. In International Conference on Machine Learning, pages 11329-1123 11399, 2021.
[42] Tailin Wu, Hongyu Ren, Pan Li, and Jure Leskovec. Graph information bottleneck. In Advances in Neural Information Processing Systems, 2020.
[43] Xuan Wu, Lingxiao Zhao, and Leman Akoglu. A quest for structure: Jointly learning the graph structure and semi-supervised classification. In ACM International Conference on Information and Knowledge Management, pages 87-96, 2018.
[44] Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In International Conference on Machine Learning, pages 5449-5458, 2018
[45] Chenxiao Yang, Qitian Wu, and Junchi Yan. Geometric knowledge distillation: Topology compression for graph neural networks. In Advances in Neural Information Processing Systems, 2022.
[46] Liang Yao, Chengsheng Mao, and Yuan Luo. Graph convolutional networks for text classifica- tion. In AAAI Conference on Artificial Intelligence, pages 7370-7377, 2019.
[47] Rex Ying, Dylan Bourgeois, Jiaxuan You, Marinka Zitnik, and Jure Leskovec. GNN explainer: tool for post-hoe explanation of graph neural networks. In Advances in Neural Information Processing Systems, 2019.
[48] Hanqing Zeng. Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graphsaint: Graph sampling based inductive learning method. In International Conference on Learning Representations, 2020.
[49] Tianqi Zhang, Qitian Wu, Junchi Yan, Yunan Zhao, and Bing Han. Scalegen: Efficient and effective graph convolution via channel-wise scale transformation. IEEE Transactions on Neural Networks and Learning Systems, 2022.
[50] Xiang Zhang and Marinka Zimik, Gunguard: Defending graph neural networks against adversarial attacks. In Advances in Neural Information Processing Systems, 2020.
[51] Yingxue Zhang, Soumyasundar Pal, Mark Coates, and Deniz Üstebay. Bayesian graph convo- lutional neural networks for semi-supervised classification. In AAAI Conference on Artificial Intelligence, pages 5829-5836, 2019.
13

---

[52] Cheng Zheng, Bo Zong, Wei Cheng, Dongjin Song, Jingchao Ni. Wenchao Yu, Haifeng Chen, and Wei Wang. Robust graph representation learning via neural sparsification. International Conference on Machine Learning, pages 11458-11468 1468, 2020.
[53] Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Beyond homophily in graph neural networks: Current limitations and effective designs. In Advances in Neural Information Processing Systems, 2020.
[54] Yanqiao Zhu, Weizhi Xu, Jinghao Zhang, Qiang Liu, Shu Wu, and Liang Wang. Deep graph structure learning for robust representations: A survey. CoRR, abs/2103.03036, 2021.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes] See Appendix B
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] The codes are public available. See Appendix D for dataset information.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Appendix C
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] See the experiment section
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [Yes] See Appendix C
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] See Appendix D
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material as URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're 're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "hZ5pM96kpOk", "reviewer": "Reviewer_N5pw", "summary": "The authors proposed a GNN framework named ALIGNS that can simultaneously learn the latent topology and missing labels of nodes. They came up with a two steps approximation to first kernelize the softmax function used in latent node structures, then a continues relaxation of the categorical distribution over all pairs of edges to enable end-to-end back propagation. In the experimentation section they tested on various datasets with up to 2M nodes, in both transductive and inductive setting, given clean, noisy, and even no graph information. Results show not only ALIGNS has a performance gain against SOTA models, but also it scales with increasing number of nodes. ", "questions": "- I feel like the same approximation can be applied to GAT or other attention based methods. What is the benefits on doing it for all pair-wise then using existing structures? Are we missing out on informations we already have in this case?\n- Why is k-NN still needed in Graph-enhanced applications? Is observed adjacency strictly needed or we can use the current layer's latent structure as adjacency? \n- Again in Eq(8) on the right side, is \\z and \\v of the same dimension? Is there no dimension changes during feature transformation? ", "limitations": "I didn't see a negative societal impact of this work. ", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros: \n- The paper is well-written and easy to read. \n- Method has potential for used in much wider range without constraining on graph-structured input. \n- Scalability of model is very impressive. The kernelization and continues relaxation seems to hold up pretty well in real world task. \n- Performance in transductive setting with standard benchmarks in homophily and heterophily graphs are on par or outperform SOTA. \n- In inductive setting even after adding noise to edges, the model still performs very stable. \n\nCons: \n- Typo in line 331, ELBO, not EBLO.\n- Eq (8) is not the same as in Algorithm 1. Shouldn't it be \\z_u^{(l)} on the right side?  \n- I don't get why all datasets have a fix \\tau = 0.25. Shouldn't it based on the feature size/graph structures? \n- From my personal perspective, I would like to see the learned latent structure in main text, and have a comparison to the original graphs. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "cJtLS5ok9Q8", "reviewer": "Reviewer_Xhvj", "summary": "This paper considers to overcome the deficiencies of over-squashing, heterophily, long-range dependencies, edge incompleteness etc. by proposing a new structure to learn the topology of the input graphs. Specifically, it proposes to incorporate the learned topology into the attention matrix through the Softmax Gumbel operator. To reduce the runtime complexity, a kernelized version of attention computation is developed using random feature decomposition. Also, convergence properties of the approximation are derived. Extensive experiments are conducted on different types of node classification tasks.", "questions": "1. In Section 3.4, there is a comment stating that Eqn. (12) can be computed in $\\mathcal{O}(1)$ because the summation term is computed in Eqn. (7). However, it seems that the summation terms are \n\\begin{equation}\n\\sum_{v=1}^{N} e^{g_v / \\tau} \\phi( \\mathbf{k}_v / \\sqrt{\\tau})  \\cdot  \\mathbf{v}_v, \\text{and} \n\\end{equation}\n\n\\begin{equation}\n\\sum_{w=1}^{N} e^{g_w / \\tau} \\phi( \\mathbf{k}_w / \\sqrt{\\tau})\n\\end{equation}\n\ninstead of  $\\sum_{w = 1}^{N} \\phi(\\mathbf{k}_w)$ . Could the authors elaborate more about this?\n\n\n2. According to the error bound for Softmax Gumbel RF decomposition in theorem 1, the bound grows exponentially in terms of the length of embedded vector $q_u$ and $k_v$, but shrinks polynomially in terms of the number of random features. Have the authors measured the gap between the approximation and the truth value when working on the experiments? As the norm grows, is a large number of random features required?\n", "limitations": "The limitations and negative social impacts are not addressed in the paper.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. Theoretical analysis is comprehensive. Convergence results are developed to study the quality of the fast computation of the Softmax Gumbel operator. \n2. The variational perspective of the proposed method is motivating. \n3. Numerical experiments are comprehensive as well, which includes testing on small graphs, large graphs, transductive and inductive task, and graph-enhanced applications etc. \n\nWeaknesses:\n\n1. The paper mentions that the new method is proposed to tackle problems like over-squashing, heterophily, long-range dependencies etc. However, in the main body of the paper, it is hard to realize how the development of the new structure helps to resolve these issues accordingly. It would be great if the authors could point this out more clearly.\n2. Since the method is proposed for scalable GNN, the authors are encouraged to review and discuss more about SOTA scalable GNNs and compare with the proposed model in the related works section, such as subgraph-wise sampling: GraphSAINT [1]; Kernelized masked attention: GKAT [2]; Linearized GNN: [3][4] etc. Also, those models could be reasonable baselines in the Section 4.2, Experiments on Larger Graph Datasets, where currently only MLP and GCN are compared.\n\n[1] Zeng, Hanqing, et al. \"Graphsaint: Graph sampling based inductive learning method.\" arXiv preprint arXiv:1907.04931 (2019).\n\n[2] Choromanski, Krzysztof, et al. \"Graph kernel attention transformers.\" arXiv preprint arXiv:2107.07999 (2021).\n\n[3] Wu, Felix, et al. \"Simplifying graph convolutional networks.\" International conference on machine learning. PMLR, 2019.\n\n[4] Bojchevski, Aleksandar, et al. \"Scaling graph neural networks with approximate pagerank.\" Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining. 2020.\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "c8Ht5EOnttr", "reviewer": "Reviewer_bJ9T", "summary": "This work performs message passing over any pairs of nodes in the graph, while avoiding the N^2 time complexity by using kernelized operator. The key technique is to use random feature to estimate the kernel function. The authors conduct experiments on various node-level tasks to evaluate the method.", "questions": "(1) For the edge loss (Eq. (10)), can we consider both observed edges and non-observed relationships. If we only consider existing edges, the loss could lead to all \\pi_{uv} to be large.", "limitations": "Not applicable.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "#### Pros ####\n(1) Using random feature technique to approximate the kernel function is impressive and reduces the complexity significantly.\n\n(2) The presentation flow of this paper is clear and easy to follow.\n\n#### Cons ####\n(1) More convincing benchmark comparison should be considered. Actually, I was surprised by the effectiveness of the random feature approximation. I think more rigorous benchmark comparison should be used to evaluate the empirical performance. In the current experiments, except ogb-proteins, other experiments are mainly using the setting defined by this paper, which might be less convincing to me. For example, for the citation networks, we have well-established benchmark setup in the community. The setup used in this paper is different, and the results of the baselines are not consistent with prior works. For example, on Citeseer, the accuracy of JKNet (~72) is much lower than GCN (~76), which indicates that the reproduced results of baselines might not be convincing.\n\n\n\n\n+++++++++ Post-rebuttal +++++++++\n\nAfter reading the response from authors, my original concerns are addressed. ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3VpvrjkZnbk", "reviewer": "Reviewer_CYMK", "summary": "This paper introduces an all-pair message passing scheme based on a kernelized Gumbel-Softmax operator to reduce the complexity of message passing from quadratic (in number of nodes N) to linear time at the cost of some approximation error. The authors provide an analysis of the incurred error and present empirical comparisons with state-of-the-art methods.", "questions": "Please see Weaknesses section above.\n\n\n### Post Rebuttal\nThank you for your response. This addresses my concern and my decision remains the same (Accept).", "limitations": "Yes (in the Appendix)", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n* The paper is very well-written and organized\n* The problem of efficient graph learning is highly relevant to the ML community \n* Sound theoretical results are provided that bound the approximation error of the proposed scheme (Sec. 3.2)\n* The presented method combines existing techniques (random features, reparameterization trick, Gumbel distribution sampling) in a novel way\n* Empirical results and comparisons (Sec. 4) on common graph datasets support the improved effectiveness of the proposed approach\n* Visualizations and sensitivity analysis of relevant variables (\\tau) are provided in the appendix\n\n## Weaknesses\n* The method requires a parameter \\tau to be tuned in advance. Is there any way to learn or automatically set \\tau based on the theoretical analysis (e.g., mathematically balance the tradeoff mentioned in Line 178) so that ablation studies are not needed on an application specific basis?\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept