Non-Local Graph Neural Networks
Authors: Meng Liu
Zhengyang Wang
Shuiwang Ji
Venue:  (2021)
Keywords: Graph Neural Networks
Non-Local Aggregation
Attention
Disassortative Graph

Abstract: Modern graph neural networks (GNNs) learn node embeddings through multilayer local aggregation and achieve great success in applications on assortative graphs. However, tasks on disassortative graphs usually require non-local aggregation. In addition, we find that local aggregation is even harmful for some disassortative graphs. In this work, we propose a simple yet effective non-local aggregation framework with an efficient attention-guided sorting for GNNs. Based on it, we develop various non-local GNNs. We perform thorough experiments to analyze disassortative graph datasets and evaluate our non-local GNNs. Experimental results demonstrate that our non-local GNNs significantly outperform previous state-of-the-art methods on six benchmark datasets of disassortative graphs, in terms of both model performance and efficiency.

Under review as a conference paper at ICLR 2021
NON- GRAPH NEURAL NETWORKS
Anonymous authors
Paper under double-blind review
ABSTRACT
Modern graph neural networks (GNNs) learn node embeddings through multi- layer local aggregation and achieve great success in applications on assortative graphs. However, tasks on disassortative graphs usually require non-local aggre- gation. In addition, we find that local aggregation is even harmful for some dis- assortative graphs. In this work, we propose simple yet effective non-local ag- gregation framework with an efficient attention-guide on it, we develop various non-local GNNs. We perform thorough experiments to analyze disassortative graph datasets and evaluate our non-local GNNs. Experi- mental results demonstrate that our non-local GNNs significantly outperform pre- vious state-offle aef-the-art art methods on six benchmark datasets of disassortative graphs, in terms of both model performance and efficiency.
sorting for GNNs. Based
INTRODUCTION
Graph neural networks (GNNs) process graphs and map each node to embedding vector (Zhang (ct al. 2018b; Wu et al. 2019). These node embeddings can be directly used for node-level applica-
tions, such as node classification
(Kipf & Welling 2017) and link prediction (Schütt et al. 2017).
In addition, they can be used to learn the graph representation vector with graph pooling (Ying
ett al.] 2018: Zhang al., [0188]
Lee et al., [019 Yuan & Ji. (020), in order fit graph-level 2015). Many variants of GNNs have been proposed. such as ChebNets (Defferrard et al.] (2016). GCNs (Kipf & Welling 2017), GraphSAGE (Hamilton al.,
tasks Yanardag & Vishwanathan
2017]. GAT's (Veličković et 2018)) LGCN (Gao et al.] (0188) and GINs (Xu et 2019). Their advantages have been shown on various graph datasets and tasks (Errica al.] 2020). However, these GNNs share multilayer local aggregation framework, which is similar to convolutional neu-
ral networks (CNNs) (LeCun et al. 1998) on grid-like data such as images and texts.
In recent years, the importance of noc-l aggregation has been demonstrated in many applications in the field of computer vision (Wang et al., (2018) 2020) and natural language processing (Vaswani et al. 2017). In particular, the attention mechanism has been widely explored to achieve non-local aggregation and capture long-range dependencies from distant locations. Basically, the attention mechanism measures the similarity between every pair of locations and enables information to be communicated among distant but similar locations. In terms of graphs, non-local aggregation is also crucial for disassortative graphs, while previous studies of GNNs focus assortative graph datasets (Section 2.2p. In addition, we find that local aggregation is even harmful for some disassortative graphs (Section 4.3). The recently proposed Geom-GCN (Pei al. 2020) explores to capture long- range dependencies in disassortative graphs. It contains an attention-like step that computes the Euclidean distance between every pair of nodes. However, this step computationally prohibitive for large-scale graphs, as the computational complexity is quadratic in the number of nodes. In addition, Geom-GCN employs pre-trained node embeddings (Tenenbaum et al., 2000; Nickel & Kiela 2017 Ribeiro et al. 2017) that are not task-specific, limiting the effectiveness and flexibility.
In this work, we propose a simple yet effective non-local aggregation framework for GNNs. At the heart of the framework lies an efficient attention-guider sorting, which enables non-local aggrega- tion through classic local aggregation operators in general deep learning. The proposed framework can be flexibly used to augment common GNNs with low computational costs. Based on the frame- work, we build various efficient non-local GNNs. In addition, we perform detailed analysis on existing disassortative graph datasets, and apply different non-local GNNs accordingly. Experimen- tal results show that our non-local GNNs significantly outperform previous state-of-the-an methods on node classification tasks on six benchmark datasets of disassortative graphs

---

Under review as a conference paper at ICLR 2021
2 BACKGROUND AND RELATED WORK
2.1 GRAPH NEURAL NETWORKS
We focus on learning the embedding vector for each node through graph neural networks (GNNs). Most existing GNNs are inspired by convolutional neural networks (CNNs) (LeCun al. 1998) and follow a local aggregation framework. In general, each layer of GNNs scans every node in the graph and aggregates local information from directly connected nodes, i.e., the 1-hop neighbors.
Specifically, a common layer of GNNs performs a two-step processing similar to the depthwise separable convolution (Chollet 2017): spatial aggregation and feature transformation. The first step updates each node embedding using embedding vectors of spatially neighboring nodes. For example, GCNs (Kipf & Welling 2017) and GAT' (Veličković et al. (2018) compute weighted sum of node embeddings within the 1-hop neighborhood, where weights come from the degree of nodes and the interaction between nodes, respectively. GraphSAGE (Hamilton et al. 2017) applies the max pooling, while GINs (Xu et al., 2019) simply sums the node embeddings. The feature transformation step is similar the 1 X convolution, where each node embedding vector mapped into a new feature space through a shared linear transformation (Kipf & Welling, 2017: Hamilton al. 2017 Veličković et al. 2018) or multilayer perceptron (MIP) (Xu et 2019). Different from these studies, I.GNN (Gao et al.) 2018) explores to directly apply the regular convolution through top-k: ranking.
Nevertheless, each layer of these GNNs only aggregates local information within the 1-hop neigh- borhood. While stacking multiple layers can theoretically enable communication between nodes across the multi-hop neighborhood, the aggregation is essentially local. In addition. deep GNNs usually suffer from the over-smoothing problem (Xu et al. 2018 Li et al. 2018 Chen et al. 2020
2.2 ASSORTATIVE AND DISASSORTATIVE GRAPHS
There are many kinds of graphs in the literature, such as citation networks (Kipf & Welling 2017). community networks (Chen et al. (020). co-occurrence networks (Tang al. 2009), and webpage linking networks (Rozemberezki et al. 2019). We focus on graph datasets corresponding to the node categorize graph datasets into assortative and disassortative ones (Newman) [002] [002] Ribeiro et al. 2017) according to the node homophily in terms of labels, i.e., how likely nodes with the same label are near each other in the graph.
classification tasks. In particular,
Assortative graphs refer to those with a high node homophily. Common assortative graph datasets citation networks and community networks. On the other hand, graphs in disassortative graph datasets contain more nodes that have the same label but are distant from each other. Example disassortative graph datasets are co-occurrence networks and webpage linking networks.
As introduced above, most existing GNNs perform local aggregation only and achieve good perfor- mance on assortative graphs (Kipf & Welling 2017: Hamilton et al., 2017] Veličković et al. 2018 Gao et al., 2018). However, they may fail on disassortative graphs, where informative nodes in the same class tend to be out of the local multi-hop neighborhood and non-local aggregation needed. Thus, in this work, we explore the non-local GNNs.
2.3
ATTENTION MECHANISM
The attention mechanism Vaswani et al., 2017) has been widely used in GNNs (Veličković et al.,
2018 Gao Ji 2019 Knyazev et al. 2019) as well as other deep learning models (Yang et al,,
2016 Wang et al., 2018 2020). A typical attention mechanism takes three groups of vectors as inputs, namely the query vector g. key vectors (k1, ..,, kn), value vectors (v1, u ,,)...,,,,...)..)......... Note that key and value vectors have one-to-one correspondence and can be the same sometimes. The attention mechanism computes the output vector as
a; = ATTEND k:) E R, i= 12;
0 Σ a,4;
where the ATTEND(-) function could be any function that outputs a scalar attention score o, from the interaction between q and k; such dot product (Gao & Ji 2019) even neural net-
2

---

Under review as a conference paper at ICLR 2021
work (Veličković et al. 2018). The definition of the three groups of input vectors depends the models and applications.
Notably, cxisting GNNs usually use the attention mechanism for local aggregation (Veličković et al, 2018 Gao & Ji 2019). Specifically, when aggregating information for node v. the query vector is the embedding vector of while the key and value vectors come from node embeddings of v's directly connected nodes. And the process is iterated for each E V. It is worth noting that the attention mechanism can be easily extended for non-local aggregation (Wang et al. 2018 2020), by letting the key and value vectors correspond to all the nodes in the graph when aggregating information for each node. However, each node in graph of n nodes requires (n²)) time. In this work, we propose novel non-local aggregation method that only requires (n log n) time.
computationally prohibitive given large-scale graphs, iterating it for
THE PROPOSED METHOD
3.1 NON-LOCAL AGGREGATION WITH ATTENTION-GUDDE SORTING
We consider a graph 9 = (V, F.), where V is the set of nodes and E is the set of edges. Fach edge E E connects two nodes so that E' _ V x V. Each node u V has node feature vector Fe R The k-hop neighborhood of v refers to the set of nodes (v, that can reach v within & edges. For example, the set v's directly connected nodes is its 1-hop neighborhood (1))).
Our proposed non-local aggregation framework is composed of three steps, namely local embedding, attention- guided sorting, and non-local aggregation. the following, we describe them one by one.
Local Embedding: Our proposed framework is built upon a local embedding step that extracts local node embeddings from the node feature vectors. The local embedding step can be as simple as
(2) The MLP(-) function is multilayer perceptron (MLP), and f is the dimension of the local node embedding 2,, Note that the MLP(-) function is shared across all the nodes in the graph. Applying MLP only takes the node itself into consideration without aggregating information from the neigh- borhood. This property very important on some disassortative graphs, as shown in Section 4.3
MLP(xx)) E R,, Vu E V.
On the other hand, graph neural networks (GNNs) can be used as the local embedding step as well, so that our proposed framework can be easily employed to augment existing GNNs. As introduced in Section 2.1 modern GNNs perform multilayer local aggregation. Typically, for each node, one layer of a GNN aggregates information from its l-hop neighborhood. Stacking such local aggregation layers allows each node to access information that is L hops away. To be specific, the f-th layer of L-layer GNN (f = 1,2,..., L) can be described as ......,,,, (8) TRANSFORM (AGGREGATE( (I=(-") : E IR', Vu VEEV,
(3)
where 20 Jay and zu (1) represents the local node embedding. The AGGREGATE!
and TRANSFORM())() functions represent the spatial aggregation and feature transformation step introduced in Section 2.1 respectively. With the above framework, GNNs can capture the node feature information from nodes within a local neighborhood as well as the structural information.
When either MIP or GNNs is used the local embedding step, the local node embedding 2, only contains local information distant but informative nodes are likely to have similar node features and local structures. Based on this intuition, we propose the attention-guide sorting to enable the non-local aggregation.
node v. However, 2, can used to guide non-local aggregation, as
Attention-Guided Sorting: The basic idea of the iiventioonguidddn sorting is to learn ordering of nodes, where distant but informative nodes are put near each other. Specifically, given the local node embedding 2u obtained through the local embedding step, compute one of attention scores by
ag ATTEND(C, 2.)) R, Ye E
where e is a calibration vector that is randomly initialized and jointly learned during training (Yang al. 2016). In this attention operator, e serves the query vector and 2, are the key vectors. In
3

---

Under review as a conference paper at ICLR 2021
addition, also treat 2, as the value vectors. However, unlike the attention mechanism introduced in Section 2.3 we use the attention scores to sort the value vectors instead of computing a weighted sum to aggregating them. Note that originally there is no ordering among nodes in a graph. To be specific, as dy and 2, have one-to-one correspondence through Equation (4) sorting the attention scores in non-decreasing order into (#1, (22, Ma,....,00 On, provides ordering among nodes, where n [V] is the number of nodes in the graph. The resulting sequence of local node embeddings can be denoted as (Z1, 22,...,, 2n).
The attention process in Equation can be also understood as a projection of local node embed- dings onto a 1-dimensional space. The projection depends on the concrete ATTEND(-) function and the calibration vector c. As indicated by its name, the calibration vector e is used to calibrate the I-dimensional space, in order to push distant but informative nodes close each other this space. This goal is fulfilled through the following non-local aggregation step and the training of the calibration vector c, as demonstrated below.
Non-Local Aggregation: We point out that, with the attention-guides sorting, the non-local ag- gregation can he achieved by convolution, the most common local aggregation operator in deep learning. Specifically, given the sorted sequence of local node embeddings (21, 22........5 zn), compute
(5) where the CoNv(-) function represents ID convolution with appropriate padding. Note that the CoNv(-) function can be replaced by a ID convolutional neural network as long as the number of input and output vectors remains the same.
(8,, 22 22, 2n, = CONV(21, 22, 2n),
To see how the CONV(.) function performs non-local aggregation with the attention- sorting, we take an example where the CoNY(.) function is ID convolution of kernel size 2s 1. In this case, &; is computed from (Zi+s:.... =i-s), corresponding to the receptive field of the CONV(.) function. As a result, if the irrention-guicedd sorting leads to (zi+s:.... 24-x) containing nodes that are distant but informative to 24. the output & aggregates non-local information. Another view is that we can consider the attention -nuutid sorting as re-connects nodes in the graph, where (Zitas.... , =)=s) can be treated as the I-hop neighborhood of 2, After the CONV(.) function, & and 2 are concatenated as the input to a classifier to predict the label of the corresponding node, where both non-local and local dependencies can be captured. In order to enable the end-to-en training of the calibration vector e, we modify Equation (5) into
(81, 82 .., 2n) = CONV 22 anān);
(6)
where we multiply the attention score with the corresponding local node embedding. As a result, the calibration vector receives gradients through the attention scores during training.
The remaining question is how to make sure that the iitention-guides sorting pushes distant but informative nodes together. The short answer is that it is not necessary to guarantee this, as the re- quirement non-local aggregation depends on the concrete graphs. In fact, our proposed framework grants GNNs the ability of non-local aggregation but lets the end-to-end training process determine whether to use non-local information. The back teek--rppaggtion from the supervised loss will tune the calibration vector and encourage 2 to capture useful information that is not encoded by 24. In the case of disassortative graphs, & usually needs to aggregate information from distant but informative nodes. Hence, the calibration vector tends arrange the attention- eitention-guided sorting to put distant but informative nodes together, as demonstrated experimentally in Section[4.5) On the other hand, nodes within the local neighborhood are usually much more informative than distant nodes in assortative graphs. In this situation, & may simply perform local aggregation that is similar to GNNs.
In Section 4 demonstrate the effectiveness of our proposed non-local aggregation framework on six disassortative graph datasets. In particular, we achieve the state-of-tt -tate-of-the-ar performance on all the datasets with significant improvements over previous methods.
3.2 TIME COMPLEXITY ANALYSIS
We perform theoretical analysis of the time complexity of our proposed framework. As discussed in Section 2.3, using the attention mechanism (Vaswani et al.] 2017 Wang et al.) 2018) (020) to achieve non-local aggregation requires O(n²) time for graph of nodes. Hssentially, the O(n))
4

---

Under review as a conference paper at ICLR 2021
time complexity is due to the fact that the ATTEND(-) function needs to be computed between every pair of nodes. In particular, the recently proposed Geom-GCN (Pei et al. 2020) contains similar non-local aggregation step. For each E V. Geom-GCN finds the set of nodes from which the Fuclidean distance to e is less than a pre-defined number, where the Fuclidean distance between every pair of nodes needs to be computed. As the computation of the the Fuclidean distance between two nodes can be understood as the ATTEND(.) function, Geom-GCN has at least O(n²) time complexity.
In contrast, our proposed non-local aggregation framework requires only Onn log time. To see this, note that the ArTEND(-) function in Equation 4 only needs be computed once, instead of iterating it for each node. As a result, computing the attention scores only takes ((n) time. Therefore, the time complexity of sorting, i.e. (n log n), dominates the total time complexity of our proposed framework. In Section 4.6 we compare the real running time different datasets among common GNNs, Geom-GCN, and our non-local GNNs as introduced in the next section.
3.3 EFFICIENT NON- GRAPH NEURAL NETWORKS
We apply our proposed non-local aggregation framework to build efficient non-local GNNs. Recall that our proposed framework starts with the local embedding step, followed by the attention-guided sorting and the non-local aggregation step.
In particular, the local embedding step can be implemented by either MLP or common GNNs, such as GCNs (Kipf & Welling 2017) or GATs (Veličković et al. 2018). MLP extracts the local node embedding only from the node feature vector and excludes the information from nodes within the local neighborhood. This property can be helpful on some disassortative graphs, where nodes within the local neighborhood provide more noises than useful information. On other disassortative graphs, informative nodes locate in both local neighborhood and distant locations. In this case, GNNs are more suitable as the local embedding step. Depending on the disassortative graphs in hand, we build different non-local GNNs with either MIP or GNNs as the local embedding step. In Section 4.3 show that these two categories of disassortative graphs can be distinguished through simple experiments, where we apply different non-local GNNs accordingly. Specifically, the number of layers is set 2 for both MLP and GNNs.
In terms of the attention geceidd sorting, we only need to specify the ATTEND(-) function in Equa- tion In order to make it as efficient as possible, we choose the ATTEND(-) function as
a (TTEND(C, =.) c" 2o E R. V.
where e is part of the training parameters, as described in Section 3.1
With the eecention-uuided sorting, we can implement the non-local aggregation step through convo- lution, as explained in Section 3.1 and shown in Equation (6). Specifically, CONV(-) function is set as a 2-layer convolutional neural network composed of two ID convolutions. The kernel size is set to 3 or depending on the datasets. The activation function is ReLU (Krizhevsky et al. 2012).
Finally, we use a linear classifier that takes the concatenation of 2, and z as inputs and makes prediction for the corresponding node. Depending on the local embedding step. we build three efficient non-local GNNs, namely non-local MLP (NLMLP), non-local GCN (NLGCN), and non- local GAT (NLGAT). The models can be end-to-end trained with the classification loss.
4 EXPERIMENTS
4.1 DATASETS
We perform experiments on six disassortative graph datasets (Rozemberczki et al. 2019 Tang et al.) 2009 Pei et al. 2020) (Chameleon, Squirrel, Actor, Cornell, Texas, Wisconsin) and three assortative graph datasets Sen et al. 2008) (Cora, Citeseer, Pubmed). These datasets are commonly used to evaluate GNNs on node classification tasks (Kipf & Welling 2017 Veličković et al.) 2018 Gao jet al. 2018 Pei et al. 2020). We provide detailed descriptions of disassortative graph datasets in Appendix A. In order to distinguish assortative and disassortative graph datasets, Pei et al. (2020)
5

---

Under review as a conference paper at ICLR 2021
propose metric to measure the homophily of graph G, defined as H(g) =
Number v's directly connected nodes who have the same label as v Number of u's directly connected nodes
(8)
DEV
Intuitively, large H() indicates an assortative graph, and vice versa. The (G) and other statistics are summarized in T
Table I: Statistics of the nine datasets used in our experiments. The definition (g) is provided
in Section 4.1 HG) can be used distinguish assortative and disassortative graph datasets.
Assortative Citeseer
Disassortative
Datasets
Cora
Pubmed
Chameleon
Squirrel
Actor
Cornell
Texas
Wisconsin
Hg)
0.83
0.71
0.79
0.25
0.22
0.21
0.11
0.06
0.16
#Nodes
2708
3327
19717
2277
5201
7600
183
183
251
#Edges
5429
4732
44338
36101
217073
33544
295
309
499
#Features
1433
3703
500
2325
2089
931
1703
1703
1703
#Classes
7
3
5
5
5
5
5
5
In our experiments, we focus on comparing the model performance on disassortative graph datasets, in order to demonstrate the effectiveness of our non-local aggregation framework. 'he performances on assortative graph datasets are provided for reference, indicating that the proposed framework will not hurt the performance when non-local aggregation is not strongly desired.
4.2 BASELINES
We compare our proposed non-local MLP (NLMLP), non-local GCN (NLGCN), and non-local GAT (NLGAT) with various baselines: (1) MLP the simplest deep learning model. It makes prediction solely based on the node feature vectors, without aggregating any local or non-local in- formation. (2) GCN (Kipf & Welling 2017 and GAT (Veličković al. 2018) are the most common GNNs. As introduced in Section 2. they only perform local aggregation. (3) Geom-GCN (Pei et al.) 2020 is a recently proposed GNN that can capture long-range dependencies. It is the current state- of-the-art model on several disassortative graph datasets. Geom-GCN requires the use of different node embedding methods, such as Isomap (Tenenbaum et al., 2000). Poincare (Nickel & Kicla 2017]. and strue2vec (Ribeiro et al. 2017). We simply report the best results from Pei et al. (2020)
for Geom-GCN and the tollowing two variants without specifying the node embedding method. (4)
Geom-GCN- (Pei et al. 2020) is variant of Geom-GCN that performs local aggregation only. It is similar to common GNNs. (5) Geom-GCN-s (Pei et al. 2020) is a variant of Geom- Geom-GCN that does force local aggregation. The designed functionality similar our NLMLP.
We implement MLP, GCN, GAT, and our methods using Pytorch (Adam et al., 2017) and Pytorch 2019). As has been discussed in fair settings, the results of GCN and GAT differ from those in Pei et al. (2020).
Geometric (Fey & Lenssen
On each dataset, we follow Pei and 20% for training, validation, and testing. The experiments are repeatedly run 10 times with different random splits and the average test accuracy over these 10 runs are reported. Testing per- formed when validation accuracy achieves maximum on each run. Apart from the details specified Section 3.3 we tune the following hyperparameters individually for our proposed models: (1) the number of hidden unit E {16, 48, 96). (2) dropout rate (0, 0.5, 0.8), (3) weight decay E {0. 5e-4, 5e-5, 56-6), and (4) learning rate E (0.01, 0.05}.
(2020) and randomly split nodes of each class into 60%. 20%,
4.3 ANALYSIS OF D GRAPH DATASETS
As discussed in Section 3.3 the disassortative graph datasets can be divided into two categories.
Nodes within the local neighborhood provide more noises than useful information in disassortative graphs belonging the first category. Therefore, local aggregation should be avoided in models on such disassortative graphs. As for the second category, informative nodes locate in both local neighborhood and distant locations. Intuitively, a graph with lower H()) more likely to be in the first category. However, it is not an accurate way to determine the two categories.
8t.kV 1052Cr oS2CC

---

Under review as a conference paper at ICLR 2021
Knowing the exact category of a disassortative graph is crucial, as we need apply non-local GNNs accordingly. As analyzed above, the key difference lies in whether the local aggregation is useful. Hence, can distinguish two categories of disassortative graphs by comparing the performance between MLP and common GNNs (GCN, GAT) on each of the six disassortative graph datasets.
Table 2: Comparisons between MLP and common GNNs. These analytical experiments are used to determine the two categories of disassortative graph datasets, as introduced in Section 43
Assortative Citeseer
Disassortative
Datasets
Cora
Pubmed
Chameleon
Squirrel
Actor
Corell
Texas
Wisconsin
MLP
76.5-1.3
73.6
87.5
48.523.0
31.3214
81.626.3
21.3
84.9
GCN
88.2 122
75.7113
88.4
67.612.4
54,911.
30.3116
54.217.3
61.117.0
59.614.5
GAT
88.4 76.1
87.0
65.0=3.7
51.3+25
29.4=1.2
56.3+4.
57.9
57.8+1.
The results are summarized in Table 2 into the first category, while Chameleon and Squirrel belong to the second category. We add the performance on assortative graph datasets for reference, where the local aggregation effective so that GNNs tend to outperform MLP.
We see that Actor, Cornell, Texas, and Wisconsin fall
4.4 COMPARISONS WITH BASELINES
According the insights from Section we apply different non-local GNNs according to the category of disassortative graph datasets, and make comparisons with corresponding baselines.
Specifically, employ NLMLP on
Table Comparisons between our NLMLP and strong baselines on the four disassortative graph datasets be-
Actor, Cornell, Texas, and Wisconsin. The corresponding baselines are MLP, and Geom-GCN-s, as Ta- ble has shown that GCN and GAT per- form much worse than MLP on these datasets. And Deom-GCN+ is similar to GCN and has worse performance than Geom-GCN-s, which is shown in Ap-
longing to the first category as defined in Section 4.3
Datasets
Actor
Cornell
Texas
Wisconsin
MLP
35.110.8
81.616.
81.3171
84.9
Geom-GCM
31.6
60.8
67.6
64.1
Geom-GCN-s
34.6
75.4
73.5
80.4
NLMLP
37.9
84.9
85.4
87.3
pendix A.2] The comparison results are reported in Table 3 While Geom GCN-s are the previous state-of-the-ar GNNs on these datasets (Pei et al. 2020), we find that MLP consistently outperforms Geom-GCN: by large margins. In particular, although Geom-GCN-s does not explicitly perform local aggregation, it is still outperformed by MLP. A possible explanation is that Geom-GCh uses pre-trained node embeddings, which aggregates information from the local neighborhood implicitly. In contrast, our NLMLP is built upon MLP with the proposed non-local aggregation framework, which excludes the local noises and collects useful information from non-local informative nodes. The NLMLP sets the new state-of-the-a performance on these disassortative graph datasets.
On Chameleon and Squirrel that belong to the second category of disassortative graph datasets, we apply NL- GCN and NLGAT accordingly. The baselines are GCN, GAT, Geom-GCN, and -CN-g. On these datasets, these baselines that explicitly perform local aggregation show advantages over MLP and Geom-GCN-s, as shown in Appendix A.2 As shown in Table 4 our proposed both datasets.
Table 4: Comparisons between our NI- GCN, NLGAT and strong baselines on the two disassortative graph datasets belonging to the second category as de- fined Section 4.3
Datasets
Chameleon
Squirrel
GCN GAT
67.6=2.4
54.9+19
NLGCN achieves the best performance In addition, is worth noting that our NLGCN and NL- GAT are built upon GCN and GAT, respectively. They show improvements over their counterparts, which indi- cates that the advantages of our proposed non-local aggre- gation framework are general for common GNNs.
65.0
51.3+2.
Geom-GCM
60.9
38.1
Geom-GCN-g
68.0
46.0
NLGCN NLGAT
70.1
59.0+1.2
65.7+1.4
56.842.5
We provide the results of all the models on all datasets in Appendix A.2 for reference.
4.5 ANALYSIS OF THE ATTENTION-GUIDER SORTING
We analyze the results of the attention- guided sorting in our proposed framework, in order to show that local GNNs indeed perform non-local aggregation.
7

---

Under review as a conference paper at ICLR 2021
Suppose the attention-guuded sorting leads to the sorted sequence (21, 22,.... ..... 2n), which goes through a convolution or CNN into (21, 2n.,,,,,,...) As discussed in Section 3.1 we can consider the sequence 22,........ ) as re-connected graph G. where we treat nodes within the receptive field of &; as directly connected 24, i.e. z,'s I-hop neighborhood. The information within this new 1 1-hop neighborhood will be aggregated. If our non-local GNNs indeed perform non-local aggrega- tion, the homophily of the re-connected graph should be larger than the original graph. Therefore, we compute (g) for each dataset to verify this statement. Following Section 4.4 we apply NLMLP on Actor, Cornell, Texas, and Wisconsin and NLGCN on Chameleon and Squirrel.
Figure D compares (G) with HG) for each dataset. We can observe that H()) is much larger than (G),, indicating that distant but informative nodes are near each other in the re-connected graph g. We also provide the visualizations of the sorted sequence for Cornell and Texas. We can see that nodes with the same label tend to be clustered together. These facts indicate that our non-local
GNNs perform non-local aggregation with the attention-guided sorting.
Homophily
Original graph
graph
Homophily
connected greph
grash
0.66
0.72
0.65
docercteinng
Comell
0.42
0.31
0.22
0.16
0:11
0.06
Non decnoviing
Chameleon Squirrel
Actor
Corell
Texas
Wisconsin
Texas
(n)
(e)
Figure I: (a) Comparisons of the homophily between the original graph and the re-connected graph given by our NLGCN on Chameleon and Squirrel. (b) Comparisons of the homophily between the original graph and the re-connected graph given by our NLMLP on Actor, Cornell, Texas, and Wisconsin. (c) Visualization sorted node sequence after the attention-guided sorting for Cornell
and Texas. The colors denote node labels. Details are explained in Section 4.5
4.6 EFFICIENCY COMPARISONS
proposed non- local aggregation framework is more efficient than previous methods based on the original at- tention mechanism, such as Geom-GCN (Pei al. 2020). Concretely, our method requires only On log computation time in contrast to O In this section, compare the real running time to verify our analysis. Specifi- cally, we compare NLGCN with Geom-GCN as well GCN and GAT. For Geom-GCN, we use the code provided in Pei et al. (2020). Each model is trained for 500 epochs on each dataset and the average training time per epoch is reported.
As analyzed in Section 3.2
Table 5: Comparisons in terms of real running time (milliseconds).
Chamelcon
Squirrel
GCN GAT Geom-GCN
22.2 (1.0x)
14.3 (1.0x)
33.2 (155x)
163.3 (11.4x)
3615.0 (163.1x)
10430.0 (727.3x)
NLGCN
26.3 (1.2x)
39.6 (2.8x)
The results are shown in Tables5] Although our NLGCN is built upon GCN, it is just slightly slower than GCN and faster than GAT, showing the efficiency of our non-local aggregation framework. On the other hand, Geom-GCN is significantly slower due to the fact that it has O(n²) time complexity.
CONCLUSION
In this work, we propose a simple yet effective non-local aggregation framework for GNNs. The core of the framework is an efficient iitention-guiden sorting, which enables non-local aggregation through convolution. The proposed framework can be easily used to build non-local GNNs with low computational costs. We perform thorough experiments on node classification tasks to evaluate our proposed method. In particular, we experimentally analyze existing disassortative graph datasets and apply different lon-local GNNs accordingly. The results show that our non-local GNNs significantly outperform previous sfate-of-the-a methods on six benchmark datasets of disassortative graphs, in terms of both accuracy and speed.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Paszke Adam, Gross Sam, Chintala Soumith, Chanan Gregory, Yang Edward. D Zachary, Lin Zem- ing, Desmaison Alban, Antiga Luca, and Lerer Adam. Automatic differentiation in pytorch. In Proceedings of Neural Information Processing Systems Autodiff Workshop, 2017.
Deli Chen, Yankai Lin, Wei Li, Peng Li, Jie Zhou, and Xu Sun. Measuring and relieving the over- smoothing problem for graph neural networks from the topological view. In ThirryyFFuurth AAAI Conference on Artificial Intelligence, 2020.
François Chollet. Xception: Deep learning with depthwise separable convolutions. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp. 1251-1258, 2017.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering. In Advances in Neural Information Processing Systems, pp. 3844-3852, 2016.
Federico Errica, Marco Podda, Davide Bacciu, and Alessio Micheli. A fair comparison of graph neu- ral networks for graph classification. In International Conference on Learning Representations, 2020.
Matthias Fey and Jan E. Lenssen. Fast graph representation learning with PyTorch Geometric. In ICLR Workshop Representation Learning Graphs and Manifolds, 2019.
Hongyang Gao and Shuiwang Ji. Graph representation learning via hard and channel-wise attention networks. In Proceedings of the 25th ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 741-749, 2019.
Hongyang Gao, Zhengyang Wang, and Shuiwang Ji. Large-scale learnable graph convolutional networks. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1416-1424, 2018.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pp. 1024-1034 2017.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In International Conference on Learning Representations, 2017.
Boris Knyazev, Graham W Taylor, and Mohamed Amer. Understanding attention and generalization in graph neural networks. In Advances in Neural Information Processing Systems, pp. 4204-4214, 2019.
Alex Krizhevsky, Iyy Sutskever, and Geoffrey Hinton. Imagenet classification with deep convo- lutional neural networks. In Advances in Neural Information Processing Systems, pp. 1097-1105, 2012.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEFE, 86(11):2278-233) 1998.
Junhyun Lee, Inyeop Lee, and Jaewoo Kang. Self-attention graph pooling. In International Confer- ence on Machine Learning, pp. 3734-3743, 2019.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Mark EJ Newman. Assortative mixing in networks. Physical review letters, 89(20):208701, 2002.
Maximillian Nickel and Douwe Kiela. Poincaré embeddings for learning hierarchical representa- tions. In Advances in Neural Information Processing Systems, pp. 6338-6347, 2017.
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-GCN: Geo- metric graph convolutional networks. International Conference on Learning Representations, 2020.

---

Under review as a conference paper at ICLR 2021
Leonardo FR Ribeiro, Pedro HP Saverese, and Daniel R Figueiredo. struc2vec: Learning node representations from structural identity. In Proceedings of the 23rd ACM SIGKDD International Conference Knowledge Discovery & Data Mining, pp. 385-394, 2017.
Benedek Rozemberezki, Carl Allen, and Rik Sarkar. Multi-scale attributed node embedding, arXiv preprint arXivv1909.13002 2019.
Kristof Schütt, Pieter-Jan Kindermans, Huziel Enoc Sauceda Felix, Stefan Chmiela, Alexandre Tkatchenko, and Klaus-Robert Müller. Schnet: A continuous-filter convolutional neural network for modeling quantum interactions. In Advances in Neural Information Processing Systems, pp- 991-1001, 2017.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93-92 2008
Jie Tang, Jimeng Sun, Chi Wang, and Zi Yang. Social influence analysis in large-scale networks. In Proceedings of the 15th ACM SIGKDD international conference Knowledge discovery and data mining, pp. 807-816, 2009.
Joshua Tenenbaum, Vin De Silva, and John C Langford. global geometric framework for nonlinear dimensionality reduction. science, 29065500):2319-2333, 2000.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in Neural Infor- mation Processing Systems, pp. 5998-6008, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pictro Lio, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Xiaolong Wang, Ross Girshick, Abhinav Gupta, and Kaiming He. Non-local neural networks. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 7794-7803, 2018.
Zhengyang Wang, Na Zou, Dinggang Shen, and Shuiwang Ji. Non-local U-Nets for biomedical image segmentation. In Chirry-Fourthe AAAI Conference on Artificial Intelligence, 2020.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip $ Yu. A comprehensive survey on graph neural networks. arXiv preprint (:Xiv:9011.00566 2019.
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, pp. 5449-5458, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovee, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference Learning Representations, 2019.
Pinar Yanardag and SVN Vishwanathan. Deep graph kernels. Proceedings of the 21th ACM SIGKDD International Conference Knowledge Discovery and Data Mining, pp. 1365-1374. ACM, 2015.
Zichao Yang. Diyi Yang, Chris Dyer, Xiaodong He, Alex Smola, and Eduard Hovy. Hierarchical attention networks for document classification. In Proceedings of the 2016 Conference of the North American chapter of the Association for Computational Linguistics: Human Language Technologies, pp. 1489, 2016.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hi- erarchical graph representation learning with differentiable pooling. In Advances in Neural Infor- mation Processing Systems, pp. 4800-4810 2018
Hao Yuan and Shuiwang Ji. StructPool: Structured graph pooling via conditional random fields. In International Conference Learning Representations, 2020.
10

---

Under review as a conference paper at ICLR 2021
Muhan Zhang, Zhicheng Cui, Marion Neumann, and Yixin Chen. An end-to-end deep learning architecture for graph classification. In Thirty-Secone AAAI Conference on Artificial Intelligence, 2018a.
Si Zhang, Hanghang Tong, Jiejun Xu, and Ross Maciejewski. Graph convolutional networks: Algo- rithms, applications and open challenges. In International Conference on Computational Social Nenworks, pp. 79-91. Springer, 2018b.

---

Under review as a conference paper at ICLR 2021
A APPENDIX
A.1
DETAILS OF DISASSORTATIVE GRAPH DATASETS
Here the details of disassortative graph datasets used in our experiments:
Chameleon and Squirrel are Wikipedia networks (Rozemberczki et al. 2019) where nodes represent web pages from Wikipedia and edges indicate mutual links between pages. Node feature vectors are bag-of-word representation of informative nouns in the corresponding pages. Each node is labeled with one of five classes according to the number of the average monthly traffic of the web page.
Actor is actor co-occurrence network, where nodes denote actors and edges indicate occurrence on the same web page from Wikipedia. It is extracted from the film-director- actor-writer network proposed by Tang al. (Tang al.) 2009). Node feature vectors are bag-of-word representation keywords in the actors' Wikipedia pages. Each node is labeled with one of five classes according the topic of the actor's Wikipedia page.
Cornell, Texas, and Wisconsin come from the WebKB dataset collected Carnegie Mellon University. Nodes represent web pages and edges denote hyperlinks between them. Node feature vectors bag-of wo-d representation of the corresponding web pages. Each node is labeled with one student, project, course, staff, and faculty.
A.2 FULL EXPERIMENTAL RESULTS
Table 6: Comparisons between our NLMLP, NLGCN, NLGAT and baselines on all the nine datasets.
Assortative Citeseer
Disassortative Actor
Datasets
Cora
Pubmed
Chameleon
Squirrel
Coreell
Texas
Wisconsin
MLP
76.5=1.3
73.6&1.
$7.5e0.4
315+14
35. 1
81.6e6.a
81.+7711
84.9
GCN
88.2+1.2
75.7
88.42n.6
67.622.4
54.921.9
30.3+16
54.2=7.
611170
59.6+4.5
GAT
88.421.4
76.121.0
87.020.3
65.0a3.7
51.322.5
29.4
56.3243
57.926.1
57.821.3
Geom- Geom-GCN
85.3
78.0
90.1
60.9
38.1
31.6
60.8
67.6
64.1
Geom- B
87.0
80.6
90.7
68.0
46.0
32.0
67.0
73.1
69.4
Geom-GCN-s
73.3
72.2
87.0
61.6
38.0
34.6
75.4
73.5
80.4
MLMLP
76.9
73.4+:19
88.220.5
50.7=2.2
33.7
37.9
84.9
85.4
87.3
NLGCN
88.12110
75.2
89.0.0.5
70.1
59.0
31.61110
57.625.5
65.5.10.6
60.225.3
NLGAT
88.5
76.2.1.6
88, 23.3
65.7.114
56.812.5
29.5.1.3
54.727.
62.617.1
56.917.3
12


Reviews:
[{"review_id": "WVCNrKCO2X", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThe goal of the paper is to perform node classification for graphs. The authors propose a strategy to augment message passing graph neural networks with information from non-local nodes in the graph - with a focus on dis-assortative graphs. Dis-assortative graphs are graph datasets - where nodes with identical node labels are distant from each other in terms of edge connectivity. \n\nWith node representation learnt from standard graph neural networks, etc., the authors propose to use an attention guided sorting mechanism, to create a proxy graph, where nodes which may have identical node labels be connected to each other (analogous to creating a k-nearest neighbor graph). Message passing is then employed on the proxy graph to learn final representations for the nodes.  Since the authors employ a single vector, namely 'c' (which they call calibration vector), to capture the 'importance of information' shared across different nodes  - there is a speedup in comparison to strategies which employ a pairwise comparison between all nodes in the graph.\n\nPros:\n1. The idea to create a proxy graph to capture non local information is interesting\n2. The proposed technique can be augmented with almost any existing GNN\n\nMy Concerns:\n1. (Dis-assortative or i.i.d.): - The authors in Figure 1 - show that homophily of the created proxy graph is a value larger than that of the original graph. However, from table A.2 in the appendix - it is clear to see that MLP's outperform GNN's with or without the attention sorting in the dis-assortative graphs - and the performance of the MLP's and proposed augmented NLMLP are well within one standard deviation from each other. This questions the need to employ a proxy graph construction on top of MLP's for these datasets as it appears like the data can be treated as i.i.d (and not relational). Moreover, these datasets (used from Pei et al. 2020) are extremely small to draw any significant conclusion. Also almost no gains are seen on the assortative datasets Citeseer, Cora, Pubmed (Please add datasets from OGB) - and their running times (when augmented with a proxy graph - are the gains worthy of increased run times?).\n2. (Baselines): Since the authors propose a strategy to construct a proxy graph (and the number of neighbors of each node in the proxy graph is the same??) - baselines such as creating graphs where nodes with identical labels are connected are also connected to each other / GNN on simple k-Nearest neighbors created using initial features (While a simple k-NN might appear more expensive - but the computation here is a single time effort) appears crucial. Also add a baseline, where adjacency structure of the graphs are iteratively updated during training such as - Learning discrete structures for graph neural networks (Franceschi, et al. ICML 2019)\n3. (Sufficiency, lack of details): The use of a single calibration vector may not be sufficient to sort the nodes - there are no guarantees in the paper to say when a single calibration vector would suffice. Also, the number of classes of nodes in each of the datasets used here are very small - and also does not trivially extend to multi-label classification of nodes. Also how do you also determine the number of neighbors in a proxy graph and do all nodes need to have the same number of neighbors in the proxy graph??? There are missing equations about how the calibration vector 'c' is learnt (what are the objective, etc) and the effect of running time when there are a large number of neighbors considered in the proxy graph -  without any equations its hard to argue against the case that the number of gradients to be computed would explode, when the number of neighbors are increased in the proxy graph (especially when jointly learning the GNN and the proposed augmentation).\n\n\nOther minor concerns:\nIf possible, please include the difference between assortative and non-assortative graphs in the introduction - it makes it easier for a reader.\n\nIf details are added and the concerns are addressed, I will be happy to improve my score.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Pg48FelWiR", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper targets on addressing the node embedding problem in disassortative graphs. A non-local aggregation framework is proposed, since local aggregation may be harmful for some disassortative graphs. To address the high computational cost in the recent Geom-GCN model that has an attention-like step to compute the Euclidean distance between every pair of nodes, an idea of attention-guided sorting is introduced. It learns an ordering of nodes, such that distant but informative nodes are put near each other. The sorting order depends on the attention scores computed with the local embedding vector of a node. Then Covn(.) function is applied on the sorted sequence of local node embeddings to obtain the non-local embedding. The final node embedding is then the concatenation of the local and non-local embedding, which is used for node classification. \n\nThe presented simple approach is an interesting idea to “push” the distant but informative nodes together. However, it is unclear how the “attention-guided sorting” is aware of the “distant” nodes. The local node embedding vectors z can be obtained either by the node content, or by GNN. If z is from the node content only, the attention score a is calculated without consideration how nodes are close or distant on the graph. The whole approach works purely for node content classification. If z is from GNN,  nodes close on the graph have similar z embedding vectors and thus will be sorted next to each other. Then, the sorting doesn’t take “distant” nodes close. \n\nAlthough the experimental results show the proposed approach performs better than several baselines, more and stronger GNN models are expected to be compared with, e.g., GINs. Especially on Chameleon and Squirrel datasets, theses two “disassortative” graphs can be handled by GNN kinds of models. The node classification in other four “disassortative” graphs in fact can be treated as a standard class classification task by ignoring the graph structures, as MLP on node features is already good. \n\nThanks for the clarifications from the authors. The discussion was very helpful. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "NU4cggIX4DC", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper points out an interesting and important issue of GNNs, i.e., local aggregation is harmful for some disassortative graphs. It further proposes non-local GNNs by first sorting the nodes followed by aggregation. The paper is well written and easy to follow.\n\n+ Positives\n1. The paper studies an important problem. The proposed Non-local GNNs by first sorting the nodes followed by aggregation is interesting and makes sense.\n2. The paper is well written and easy to follow.\n3. Experiments well support the claim of the paper. The results demonstrated the effectiveness of the proposed method for disassortative graphs for node classification. In addition, the authors show the running time to demonstrate its efficiency and analyze the sorted nodes to demonstrate that the proposed method can learn non-local graphs.\n\n-Negative\n1. It seems that for some disassortative graphs such as Actor, Cornell, Texas and Wisconsin, using the node attributes to build the non-local graph is much effective than using the attributed graph. The authors may also need to compare a baseline that simply use MLP to learn node embedding, then construct the graph by calculating pairwise node similarity, followed by GNN for node classification. This can be treated as a variants of the proposed NLMLP to show that sorting the nodes is more efficient and more effective.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "KwtALQwC5T", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a way of speeding up non-local aggregation on graph convolutional neural networks based on sorting the nodes into an ordering, and performing a 1-D convolution on this resulting ordering. This algorithm has the advantage of being asymptotically faster than other non-local aggregation schemes, and the paper demonstrates that empirically it can do at least as well as some of the other methods.\n\nStrengths:\n+ the proposed approach is simple, quite general, and rather different from other tools for graph neural nets that I'm aware of.\n+ the experimental evaluation methodology is sound, and comparisons with several previous works are made\n\nWeaknesses:\n- the approach is difficult to interpret: it's difficult to convince someone working on GCNs why it would work.\n- on some of the data sets, the gains observed as inconclusive. The experiments also focused on small data sets: it's unclear how such gains extend to more general settings.\n\nI work mostly on graph algorithms, and only know a little about neural networks. So I'm evaluating this paper mostly as a practical graph algorithms. The effectiveness of such global sorting schemes based on a single score is very surprising, almost too surprising. On the other hand, my general impression is that graph algorithms is full of such surprises: many by now classical algorithms are arrived at by analyzing strange phenomenon that happen to work well. So I'm quite willing to suspend disbelief about why something like this would work, as that's a much more detailed process.\n\nFrom the discussions, it seems that there are quite a bit of concerns raised about the experimentation process. On the other hand, the responses, and presentations in the paper, are also quite convincing to me. So I believe this result is ready to appear in the conference, if anything for the further discussion/interest it will generate, and would still like to recommend acceptance of this paper.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper is right at the borderline: the reviewers agree it is well written, proposing a simple but interesting idea. However, there was a feeling among the reviewers (especially reviewer 1) that the paper could be strengthened considerably with a better discussion/some theory on the sufficiency of the calibration vectors, as well as experiments on larger datasets. Doing one of these would have substantially strengthened the paper. Due to the remaining shortcomings, the recommendation is not to accept the paper in its present state.
Decision: Reject