Global Attention Improves Graph Networks Generalization
Authors: Omri Puny
Heli Ben-Hamu
Yaron Lipman
Venue:  (2021)
Keywords: Graph Neural Network
Self-Attention
Generalization of GNNs
Weisfeiler-Lehman

Abstract: This paper advocates incorporating a Low-Rank Global Attention (LRGA) module, a Computation and memory efficient variant of the dot-product attention (Vaswani et al., 2017), to Graph Neural Networks (GNNs) for improving their generalization power. 
To theoretically quantify the generalization properties granted by adding the LRGA module to GNNs, we focus on a specific family of expressive GNNs and show that augmenting it with LRGA provides algorithmic alignment to a powerful graph isomorphism test, namely the 2-Folklore Weisfeiler-Lehman (2-FWL) algorithm. In more detail we: (i) consider the recent Random Graph Neural Network (RGNN) (Sato et al., 2020) framework and prove that it is universal in probability; (ii) show that RGNN augmented with LRGA aligns with 2-FWL update step via polynomial kernels; and (iii) bound the sample complexity of the kernel's feature map when learned with a randomly initialized two-layer MLP.
From a practical point of view, augmenting existing GNN layers with LRGA produces state of the art results in current GNN benchmarks. Lastly, we observe that augmenting various GNN architectures with LRGA often closes the performance gap across different models.

Under review as a conference paper at ICLR 2021
GLOBAL ATTENTION IMPROVES GRAPH NETWORKS GENERALIZATION
Anonymous authors Paper under double-blind review
ABSTRACT
This paper advocates incorporating Low-Rank Global Attention (LRGA) mod- ule, a computation and memory efficient variant of the dot-product attention (Vaswani et al.) 2017). to Graph Neural Networks (GNNs) for improving their generalization power:
To theoretically quantify the generalization properties granted by adding the LRGA module to GNNs, we focus on specific family of expressive GNNs and show that augmenting with LRGA provides algorithmic aligmment to a powerful graph isomorphism test, namely the 2-Folklore Weisfeiler-Lehhman (2-FWI) algo- rithm. more detail we: (i) consider the recent Random Graph Neural Network (RGNN) (Sato et al. 2020) framework and prove that it is universal in probability; (ii) show that RGNN augmented with LRGA aligns with 2-FWL update step via polynomial kernels; and (iii) bound the sample complexity of the kernel's feature map when learned with a randomly initialized two-layer MLP.
From practical point of view, augmenting existing GNN layers with LRGA pro- duces state of the art results in current GNN benchmarks. Lastly, we observe that augmenting various GNN architectures with LRGA often closes the performance gap between different models.
INTRODUCTION
In many domains, data can be represented as graph, where entities interact, have meaningful relations and global structure. The need to be able to infer and gain better understanding such data rises in many instances such as social networks, citations and collaborations, chemoinformatics, epidemiology etc. In recent years, along with the major evolution of artificial neural networks, graph learning has also gained new powerful tool graph neural networks (GNNs). Since first originated (Gori et al. 2005| Scarselli et al. 2009) as recurrent algorithms, GNNs have become a central interest and the main tool in graph learning.
Perhaps the most commonly used family of GNNs are message-passiinn passing neural networks (Gilmer et al. 2017), built by aggregating messages from local neighborhoods at each layer. Since infor- mation only kept at the vertices and propagated via the edges, these models' complexity scales linearly with [V] [E), where [V| and [E] are the number of vertices and edges the graph, re- spectively. In a recent analysis of the expressive power of such models, (Xu et al., [019a] Morris) neural networks are most as powerful as the first
al. 2018) have shown that message-passinn Weisfeiler-Lehman (WL) test, also known as vertex coloring. The k-WL tests, are a hierarchy of increasing power and complexity algorithms aimed solving graph isomorphism. This bound on the expressive power of GNNs led to the design of new architectures (Morris et al. 2018 Maron al. 2019a) mimicking higher orders of the WL family, resulting more powerful, yet complex, models that scale super-lineatl in [V| + EE, hindering their usage for larger graphs.
Although expressive power bounds on GNNs exist, empirically in many datasets, GNNs are able to fit the train data well. This indicates that the expressive power of these models might not be the main roadblock to a successful generalization. Therefore, we focus our efforts in this paper on strengthening GNNs from generalization point of view. Towards improving the generalization of GNNs we propose the Low-Ram Global Attention (LRGA) module which can be augmented to any GNN. Standard dot-product global attention modules (Vaswani al. 2017) apply [V] x [V]

---

Under review as a conference paper at ICLR 2021
attention matrix to node data with (( computational complexity making them impractical for large graphs. To overcome this barrier, we define a k-rank attention matrix, where x is a parameter, that requires ((s(V]) memory and can be applied in (x<2(V)) computational complexity.
To theoretically justify LRGA we focus on a GNN model family possessing maximal expressiveness (i.e., universal) but vary in the generalization properties of the family members. (Murphy et al.] 2019 Loukas 2019; Dasoulas et al.] 2019 Loukas 2020) showed that adding node identifiers to GNNS improves their expressiveness, often making them universal. In this work, we prove that even adding random features to the network's 's input, as suggested in (Sato et al., 2020), a framework we call Random Graph Neural Network (RGNN), GNN models are universal probability.
The improved generalization properties of ARGA-augmmeted GNN models is then showcased for the RGNN framework, where we show that augmenting with LRGA algorithmically aligns with the 2-folklore WL (FWL) algorithm; 2-FWL is strictly more powerful graph isomorphism algorithm than vertex coloring (which bounds message passing GNNs) To do so, we adopt the notion of al- gorithmic alignment introduced in (Xu et al. (019b), stating that a neural network aligns with some algorithm if it can simulate it with simple modules, resulting in provable improved generalization. We opt to use monimials in the role of simple modules and prove the alignment using polynomial kernels. Lastly, we bound the sample complexity of the model when learning the 2-FWL update rule. Although our bound is exponential in the graph size, it nevertheless implies that RGNN aug- mented with LRGA can provably learn the 2-FWI. step, when training each module independently with two-layer MLP.
We evaluate our model on a set of benchmark datasets including tasks of graph classification and regression, node labeling and link prediction from (Dwivedi et al. 2020 Hu al.) 2020). LRGA improves state of the art performance in most datasets, often with a significant margin. We further perform ablation study in the random features framework to support our theoretical propositions.
2 RELATED WORK
Attention mechanisms. The first work to use an attention mechanism in deep learning was (Bah- danau et al. 2015) in the context of natural language processing. Ever since, attention has proven to be a powerful module, even becoming the only component in the transformer architecture (Vaswani et al. 2017). Intuitively, attention provides an adaptive importance metric for interactions between pairs of elements, e.g., words in a sentence, pixels in an image or nodes in graph. A natural draw- back of classical attention models is the quadratic complexity generated by computing scores among pairs. Methods to reduce the computation complexity were introduced by (Lee et al. (018b) which introduced the set-transformer and addressed the problem by inducing point methods used in sparse Gaussian processes. Linearized versions of attention were suggested by (Shen et al. 2020) factor- izing the attention matrix and normalizing separate components. Concurrently to the first version of this paper (Anonymous) 2020 Katharopoulos et al. (2020) formulated a linearized attention for sequential data.
Attention in graph neural networks. In the field of graph learning, most attention works (Li et al. 2016 Veličković et al. [0188] Abu-El-Haija et al. 2018 Bresson & Laurent 2017 Lee et al. 2018a) restrict learning the attention scores to the local neighborhoods of the nodes in the graph. Motivated by the fact that local aggregations cannot capture long range relations which may be important when node homophily does not hold, global aggregation in graphs using node embeddings have been suggested by (You et al., 2019 Pei et al. 2020). An alternative approach for going beyond the local neighborhood aggregation utilizes diffusion methods: (Klicpera et al.] 2019) use diffusion in
a pre-process to replace the adjacency with a sparsified weighted diffusion matrix, while (Zhuang & Ma 2018) add the diffusion matrix as an additional aggregation operator. LRGA allows global weighted aggregations via embedding of the nodes in a low dimension (i.c., rank) space.
Generalization in graph neural networks. Although being pillar stone of modern machine learning, the generalization capabilities of NN are still not very well understood, e.g., see (Bartlett ltt al., 2017] Golowich et al. 2019). Due to the irregular structure of graph data and the weight sharing nature of GNN, investigating their generalizing capabilities poses an even greater challenge. Despite the nonstandard setting, few works were able construct generalization bounds for GNN
2

---

Under review as a conference paper at ICLR 2021
via VC dimension (Scarselli et al. 2018). uniform stability (Verma & Zhang 2019). Rademacher Complexity (Garg et al. 2020) and Neural Tangent Kernel (Du et al. 2019).
PRELIMINARIES AND NOTATIONS
We denote a graph by G (V, E, X) where V vertex set size [V| = set, and adjacency A. X (.1,...,22 Tt, represents the input vertex features. A vertex v; V carries an input feature vector æ, E R2;; in turn, X E R=*d represents the output the 1 layer of neural network. We denote concatenation along the last dimension with brackets and stacking along a new last dimension with double brackets, i.e., for W, Z E Raxd [W, 2 E RRx22 and
n. E is the edge
[W, Z] E R2xxx2
common form of evaluating GNNs is by their ability to distinguish different graphs, described by graph isomorphism which is equivalence relation between graphs. The isomorphism type tensor of a graph G' is tensor Given a pair (i,j), which represents either an edge information this pair carries in graph G. More precisely put, isomorphism type is an equivalence relation defined by: (i,j) and (i' j") have the same isomorphism type iff the following conditions hold: (i) i-)=) j < = jJ;;; (ii) 2; = Zy and z; = Ty; and (iii) (i.j) E E > (f'5') J') E E. One way to build isomorphism type tensor for graph G is Y [I, & X, X & 1, A] where I is the identity matrix, (1 @ X) )a.j. =zj. and similarly (with slight abuse of notation) (X @ 1)5s = 24-
xd... which holds the isomorphism types all pairs (i,j) E [m] [n]]
node of graph G. Yi, summarizes all the
LOW-RANK GLOBAL ATTENTION (LRGA)
We propose the Low-Rank Global Attention (LRGA) module that can augment any graph neural network layer, denoted here generically GNN, in the following way:
x + x LRGA(X'), GNN(X')]
(1)
where the brackets denote concatenation along the feature dimension. The LRGA module is defined for an input feature matrix X E xd via
LRGA(X)
my (X) (m²(X) (xxmmmm((XX mx)))) mx(X))
(xX
where m., ,,,, ma, Bexda R are MLPs operating on the feature dimension, that is m(X) (0s...,,((,,, mmxx,)²² and E No is parameter representing the rank of the attention module. Lastly, 17 is normalization factor:
1 (1Tmi(X)) (m²(X)"1)
(Xx)
(3)
where 1 = (1.1....,,) 1)TH E R". The matrix (xX) ( m2)(m))))))) can be thought of as s-rank attention matrix that acts globally on the graph's 's node features.
Computational complexity. Standard attention models (Vaswani et al. 2017 Luong et al. 2015) require explicitly computing the attention score between all possible pairs in the set, meaning that its memory requirement and computational cost scales as On²²). This makes global- seem impractical for large sets, or large graphs in our case. We address the global attention computational challenge by working with bounded rank (i.e., x) attention matrices, and avoid the need to construct the attention matrix in memory by replacing the standard entry-wise normalization (softmax or tanh) with the global normalization 17. In turn, the memory requirement of LRGA is O(nx), and using low rank matrix-vector multiplications LRGA allows applying global attention in O(nx²) computation cost.
Permutation Equivariance. A common demand from GNN architectures is to respect the graph representation symmetries, namely the ordering of nodes (Maron et al.) 2019b). As shown in (Lee) al. 2018b) the set attention module is permutation equivariant. The same matrix product structure of the LRGA makes this module also permutation equivariant.
3

---

Under review as a conference paper at ICLR 2021
5 THEORETICAL ANALYSIS
In this section we establish the theoretical underpinning for LRGA. Since we want to analyse the generalization power added by LRGA, we focus on family of GNNs with unbounded expressive power in probability (RGNN). Under this model we show the benefit of augmenting GNNs with LRGA in terms of improved generalization via the notion of algorithmic alignment with a powerful graph isomorphism testing algorithm (2-FWL).
5.1 RANDOM GRAPII NEURAL NETWORKS
We analyse LRGA under the framework of Random Graph Neural Networks (RGNNs):
Definition 1 (Random Graph Neural Network). Let 'D be a probability distribution of zero mean and variance and G = (V, E, X) graph. RGNN is a GNN variant with random input features sampled at every forward puss i.e., the inpul to the network is [X, R) where R are i.i.d. samples R E Raxd ~ D.
2019 Murphy et al,, 2019) that use node identifiers or distinetive features, which can be viewed as constant random features, in order to break symmetry between isomorphic nodes. Such models are proven to be universal but lose their inherent equivariance due to arbitrary prescription of node identifiers. We choose work in the seemingly more limited setting of RGNN, which allows the network to dis- tinguish between different nodes but does not overfit specific identifiers. Our main claims regarding this framework is that RGNN is both universal in probability and equivariant in expectation.
RGNN, suggested by Saato et al. (2020), has related variants (Loukas, 2020
Proposition 1 (Universal). RGNN can approximate an arbitrary continuous graph function given random features sampled from a bounded distribution D.
Here approximation is in a probabilitic sense: Let Ω C Raxdo x RR. be a compact set of graphs, [X, .A] E Ω. where A E Rn² is the adjacency matrix. Then, given a continuous graph function f defined over Ω and arbitrary E, > 0, there exist network parameters and so that P(IGNN(X, R)) f([X, A)) < <) 1 - 6, for all graphs [X AA ft. Proposition I holds for GNN variants with a global attribute block such as (Battagla et al. 2018). The proof is based on the idea that random features allow the GNN transfer the graph ss connectivity information the node features. Once all graph information is encapsulated at the nodes, we exploit the universality of set functions (Zaheer et al. 2017) to get universality. The full proof is in Appendix A To the best of our knowledge this is the first result proving universality under the random feature assumption.
Proposition 2 (Equivariant in expectation). RGNN is permutation equivariant in expectation.
Changing the random features at each forward pass allows RGNN to preserve equivariance in ex- pectation. Indeed, equivariance of GNN implies that GNN(P [X, R)) = P GNN( [X, RR), for any permutation matrix P and input [X, Rt.. Taking the expectation of both sides w.r.t. R D, noting that PR ~ R and using linearity of expectation we get equivariance in expectation.
5.2 RGNN AUGMENTED WITH LRGA ALIGNS WITH 2-FWL
In this section we will formulate our main theoretical result, Theorem 1 stating that augmenting RGNN with LRGA algorithmically aligns with a powerful graph isomorphism testing algorithm called 2-Folklore Weisfeiler-Lehmanl (2-FWL) (Grohe & Otto 2015 Grohe 2017). We will first introduce the notion of algorithmic aligmment and the 2-FWL algorithm, then formulate our main theorem, and continue in the next section with proof.
Algorithmic alignment. The notion of algorithmic alignment was introduced in Xu et al. (019h) as framework for exploring effective neural architectures for certain tasks. A neural network N said to be aligned with an algorithm if A can simulate A by a composition of modules, and each module is "simple", or learnable, i.e., have bounded (hopefully low) sample complexity. For example, message passing networks can simulate the vertex coloring algorithm (Xu et al. 2019a Morris et al. 2018) and therefore message passing can be seen algorithmically aligned with vertex coloring. Intuitively, algorithmic alignment introduces an inductive bias that improves the sample complexity. Our definition of algorithmic alignment is slightly stricter version:
4

---

Under review as a conference paper at ICLR 2021
Definition 2 (Monomial Algorithmic Alignment). A neural network N aligns with algorithm A N can simulate A by learning only monomial functioon, function, i.e., f(x) = x", where a E R a N and x=x 1 x²
To motivate this choice of monomials as "simple" functions we note that (Arora et al. 2019
er al. 2019b) show sample complexity bound for even-power polynomials learned by (two-layer) MLPs and we extend to general monomials in the following proposition proved in Appendix [E] Proposition 3. Let two layer MLP trained with gradient descent be denoted as the learning algo- rithm A'. The monomial g(æ) = x x E Rd, of degree n, ax] S n, PAC learnable with A' with sample complexity bound:
=)) (Gnd log(1/6)
e2
Cn,d = 11) (n+1)/2 Cn.d. 0 is the error parameter and & E (0, 1) the failure probability.
The asymptotic behaviour of Ca is out of the scope of this paper. Therefore, monomial algorith- mic alignment of N to A means (under the assumptions and sequential training method of Theorem 3.6 in Xu al. (20196) that A learnable by N.
2-Folklore Weisfeiler-Lehhan (2-FWL.) Algorithm. 2-FWI. is part of the k-WL. hierarchy of polynomial-time (approximate) graph isomorphism iterative algorithms that recolor k-tuples of ver- tices at each step according to neighborhoods aggregation. Upon reaching a stable coloring, the algorithm terminates and the histograms of colors of two graphs are not same then the graphs are deemed not isomorphic. The 2-FWL algorithm is equivalent to 3 BL,, strictly stronger than vertex coloring (2-WL) which bounds the expressive power of GNNs.
In more detail, let Y E 1pnxxdu represent the isomorphism types of a given graph G = (V, X),, that is yo E Rd represents the isomorphism type of the pair j). The 2-FWL algorithm is initialized with y Let yi E I xd: denote the coloring tensor after the 1th update step. An update step in the algorithm aggregates information from the multiset of neighborhood colors for each pair. We represent the multiset of neighborhood colors of the tuple (i,j)
1.4
14
Z
with matrix Z E RRnx2d, That is, any permutation of the rows of (i,)) represent the same
multiset. The rows of Z (1.j)) which represent the elements in the multiset, are YY k Kall
2ed: k [m). See the inset for an illustration. The 2-FWI update step of pair (i.j) from Y' to yl+1 concatenates the previous pair's color and an encoding of the multiset of neighborhoods colors:
W,y,ENC ((..))
where ENC: Rax2d + Rd a multiset injective map invariant to the row-order of its input.
Main result. Consider the 2-FWL update rule in equation and let y RR. denote (arbitrary) single feature dimension pealed off y'+1 e " xdi12; we call y a single-head the update rule. Then,
Theorem 1. LRGA augmented RGNN algorithmicaaly aligns with a single head 2-FWL update step.
A corollary of this theorem is: Corollary 1. Multi-head LRGA augmented RGNN algorithmically aligns with 2-FWI.
LRGA, (X'), GNN( (X')], which is equivalent to multi- head self-attention. In practice, found single-head LRGA to be on par performance-wiss with multi-head LRGA and therefore we focus on the single-head version in the experimental section.
Multi-head LRGA a module of the form [X] LRRA, L.RAA
5.3 PROOF OF THEOREM
To prove Theorem I we need to show RGNN augmented with LRGA can simulate one head of the 2-FWL update step using only monomials as learnable functions. We achieve that by the following
5

---

Under review as a conference paper at ICLR 2021
steps: (i) introduce the notion of node factorization to encode n X tensor data node features; (ii) show that RGNN can approximate node factorization of the graph's ' isomorphism type tensor with a single GNN layer using learnable monomial functions; (ii) show that 2-FWL update step can be formulated using matrix multiplication of monomial functions; and (iv) show LRGA can approximate single head 2-FWI. update step using learnable monomials.
Part (i), We start with the definition of node feature factorization:
Definition (Node factorization). Let E R=²xd be a tensor. X E R is called node factorization of Y if there exists block structure X [x].... ..... x*] that Y [X 91 (X"1) ..... X X (X where (s1,t)),... (sa. ta) E [b:] [Ki] are index pairs.
"ef",xz) , Rd. Lets illustrate the Note that for all i.j E [n] we have Y1. = [[ 20), )..,)...... j definition with example. Let A 10,1) be the adjacency matrix of some graph G, and for simplicity assume that there are no node features. Then, the isomorphism type tensor of G is Yo = [I, A] E Ra x22 One possible way of node factoring Y is using the SVD decomposition of adjacency matrix A. Note that node factorization not unique.
Part (ii).
Proposition 4. RGNN with skip connection can approximate node factorization of the isomorphism type tensor yo
Proof. We will prove the case of graph G = EV, i.e. with no vertex features; the general case can found in Appendix D Let R E Raxd be a random node features matrix sampled i.i.d. from D. A single layer of standard message passing can represent GNN(R) = d A R. RJ., which requires learning only first degree (linear) monomials in the GNN's learnable parts. Furthermore, GNN R) is an approximate node factorization of Y since d RRR" ARRR ~ [| Y where the approximation error d-1 RRR ~ I can be bounded using the result in Appendix
0
Part (iii). As shown in (Maron al. 2019a the encoding function ENC from the 2-FWL update rule (see equation can be expressed as follows (derivation can be found in Appendix B
y = Y, y (B, 7) E NO", | Iy/
(5)
where for notational simplicity we denote Y Y' and dr. By S we mean that we apply the mowei-power to the feature dimension, i.e., (V Jag y&, Therefore, computing the multisets encoding amounts to calculating monomials S Y and their matrix multiplications y
Part (iv).
Proposition The node factorization of each head of Vl41, the resuli of 2-FWL update step, can be approximated via LRGA module applied to node factorization of Y Y'. The MLPs in the LRGA approximation need to learn only monomial functions.
Proof. Let X = [X!.... x+1 D be node factorization of Y Y'. The 2-FWL update Using the node
step requires computation of polynomials of the form y shown in equation
factorization of Y, YiJ = [xx ah) (a ( E Rdd, we can write:
3
II (o aa) 1=1
II (x "),, ). (x)))
II (va(a))) 1=1
(+)) (p)())))
where the second equality is using the feature maps P9. of the (homogeneous) polynomial kernels Vapnik 1998), (x), x2) ; the third equality reformulating the feature maps 9P, on the vectors 2 x w.d], and of [a]"...... add] and the last equality is due to the closure of kernels to multiplication. We denote the final feature map by Paa.
Now, let (a,) = (a(") and ) ) = (xxx) then we have:
y who x))a(X)

---

Under review as a conference paper at ICLR 2021
where (X) is applying d every row of X. Therefore, arbitrary head of y .i.., of the form y&y,, can be written directly as a function of X using the feature maps ΦB, Dss My: 4y: (X)
y = (
(7)
A node factorization of the head yo is therefore () by (X), By (X)].
Re-
calling the structure of the LRGA module introduced in equation 2 LRGA(X)
[n(( (X) (m2(X) my mm((X)), mx(X),, to implement the 2-FWL head the MLPs m1, m2, ma, my need to learn the polynomial feature maps formulated in equation 7 my ~ vhg m2 R (3, mi R My,, and m4 R Φ7. Every coordinate of these feature maps is a monomial (proof of this fact in Appendix (C). Lastly, note that 2-FWL. tensors Y' are insensitive to global scaling and therefore the normalization 1y has theoretical influence (it is assumed non-zero).
6 EXPERIMENTS
We evaluated our method on various tasks including graph regression, graph classification, node classification and link prediction. The datasets we used are from two benchmarks: (i) benchmarking GNNs (Dwivedi et al. 2020); and (ii) Open Graph Benchmark (OGB) (Hu et al., 2020).. Each benchmark has its own evaluation protocol designed for a fair comparison among different models. These protocols define consistent splits of the data to train/val/tess sets, set budget on the size of the models (OGB), define stopping criterion for reporting test results and require training with several different initializations to measure the stability of the results. We followed these protocols. Baselines. We compare performance with the following state of the art baselines: GCN (Kipf & | 2016), GraphSAGE (Hamilton et 2017), GIN (Xu et al. 2019a), GAT (Veličković et al.) 2018). GatedGCN (Bresson & Laurent 2017). Node2Vec (Grover Leskovec 2016). Deep Walk (Perozzi et al.) 2014) and MATRIX FACTORIZATION (Hu et 20200).
Attention Ablation. We compared the performance of different versions of global attention modules. The experiment was conduced on the ZINC dataset and compared performance on the GCN, GAT and GatedGCN models.
Random Features Evaluation. In addition, we also conducted set of experiments with the random feature framework. In this experiment we focused on the PATTERN node classification dataset from (Dwivedi et al. 2020) and evaluated variety of models under the RGNN framework. Rank Ablation Study. In this experiment we examined the relation between the rank parameter K, which can limit the expressiveness of the attention module, and the network performance. Results are presented in Appendix G
Implementation details of LRGA. We implemented the LRGA module according to the descrip- tion in Section 4 (equations 2 3} using the pytorch framework and the DGL (Wang et al.) (019)) and Pytorch geometric (Fey & Lenssen 2019) libraries. Each LRGA module contains MLPs mi, M2, My, M4. Each m, IRd I² is a single layer MLP (linear with ReLU activation). The implementation of a layer is according to equation 2] where in practice we added another single Rd, for the purpose of reducing the feature dimension size. In the OGB benchmark dataset we did not use the skip connections (better performance), and as advised
layer MLP, mis : dd+2
in (Wang et al. 2019), we used batch and graph normalization each layer.
6.1 BENCHMARKING GRAPH NEURAL NETWORKS (DWIVEDI ET AL., 2020
Datasets. This benchmark contains 6 main datasets (full description in appendix H.I (i) ZINC, graph regression task of molecular dataset evaluated with MAE metric; (ii) MNIST and CIFAR 10, the image classification problem converted to graph classificatinn using super-pixel representation (Knyazev et al. 2019); (ii) CLUSTER and PATTERN, node classification tasks which aim to clas- sify embedded node structures (Abbe 2017:: : (iv) TSP, link prediction variation of the Traveling Salesman Problem (Joshi et al., 2019) on 2D Euclidean graph.
Evaluation protocol. All models were evaluated with two different sets of parameter budgets and restrictions. The first set restricted to have roughly 100K parameters and 4 layers, while the second set of experiments has a budget of roughly 500K parameters and up to 16 layers. The learning rate and its decay are set according to predetermined scheduler using the validation loss. The stopping criterion is set to when the learning rate reaches a specified threshold. All results are averaged over set of predetermined fixed seeds and standard deviation is reported well.
7

---

Under review as a conference paper at ICLR 2021
Table 1: Performance the benchmarking GNN datasets. In bold: better performance between LRGA aug- mented and vanilla models; note the parameter (if) budget. Blue represents best performance with the 100K budget and red with the 500K budget.
PATTERN
CLUSTER
ZINC
MNIST
CIFARIO
Model
Ace
MAE
100K
+ 0.07
$3.44
105K
0,459
0.006
101K
+ 0.21
95K
0.630
0.001
ERGA GEN
90K
83,09 + 0.73
91K
68.44 = 0.16
0.448
0.009
91K
97.63
+ 0.11
91K 65.80 +
97K
0.702
0.001
109K
75.87
110K
57.73
=
102K
0.478
0.007
110K
95.53
11 0.20
64.22
96K
0:671
0.002
LRGA GAT
90K
82.54
+- 0.71
91K
69.05
0.421
0.020
90K
+:
68.00
978
GatedGCN
103K
84.45
+ 0.12
00:40
105K
0.375
0.003
104K
97.34
+
67.31
978
0.003
LRGA GatedGCN
93K
85.09
+ 0.11
69.28
0.355
0.010
93K
98.20
+ 0.03
70.65
0.18
978
0.807
0.001
GCN
500K
71.89 1: 0.33
SOLK
68.49 1E: 0.97
505K
0.367
0.011
500K
91.39
1: 0.25
500K
54.84 0.46
ERGA + GEN
400K
84.55 +: 0.57
400K
76.01 = 0167
501K
0.377
0.009
463K
98.34
+: 0.06
463K
68.27
0.46
GAT
526K
78.27 4: 0.18
528K
70.58 =:: 531K
0.007
441K
96.50
0.18
442K
66,11
0.98
LRGA + GAT
533K
85,82 1: 0.42
2671K
76.16 =1: 0.34
536K
0.369
0.004
476K
98.41
1: 0.08
476K
71.57
01:01:00000 0.26
GatedGCN
502K
85.56
1: 0.01
502K
73.84
1: 0.32
50HK
0.282
0.015
500K
98.24
1: 0.04
500K
71.33
:1: 0.39
IRGA + GatedGCN
486K
885.81
+ 0.31
4388
0:13 76.39
446K
0.349 1: 0.011
486K
98.47
+: 0.16
73.48
0.29
Results. Table [ summarizes the results of training and evaluating our model according to the evaluation protocol; We observe that LRGA improves GNN performance, often by large margin, across all models and datasets, besides GCN on ZINC and GatedGCN in TSP, supporting for improved generalization. We further note that SOTA in all datasets except TSP is achieved with LRGA augmented GNNs. In some datasets, such as CLUSTER and PATTERN, LRGA reaches top and roughly equivalent performance for all models it augmented, which emphasizes the empirical contribution of LRGA independently of the GNN variant.
claim
6.2 LINK PREDICTION DATASETS FROM THE OGB BENCHMARK (HU ET AL. 2020
Datasets. We further evaluate LRGA
Table 2: Performance the link prediction tasks from the
on semi-supervised learning tasks includ- ing graphs with hundreds of thousands of nodes, from the OGB benchmark: (i) ogbl- ppa, a graph of proteins and biological connections as edges :(ii) ogbl-collab, an
OGB benchmark
oghi-ppa
oghi-collab
oghi-ddi
# Parsm
Hise 100:g-td
2 Param
Paramn
Hit
20:bvtal
Node2vee
73M
0.223 : 0,008
3004
0.459
0,005
645K
0.233
0,021
DeepWalk
150M
0.015
0.50
MP
147M
0,323
0.009
60M
0.389
0.003
1.2M
0.137
0.047
authors collaborations graph; (iii) ogbl-ddi drug interaction network. The evaluation
GraphSage
424K
0.365
#: 0.024
450K
0.451
0,005
1.4M
0.339 4: 0,047
GCN
278K
0.087
1: 0.013
296K
0.447
0.13
1.2M
0.310
0.050
metric for all of the tasks is Hits K; more details in appendix H..2
R14K
8.016
IM
(.623
Evaluation protocol. All models have a hidden layer of size 256 and the number of layers is 3 in ogbl-ppa and ogbl-collab and in ogbl-ddi. Test results are reported by the best validation epoch averaged over 10 random seeds.
Results. Table 2 summarizes the results on the link prediction tasks. should be noted that the first three rows correspond to node embedding methods where the rest are GNNs. Augmenting GCN with LRGA achieves SOTA results on those datasets, while still using order of magnitude less parameters than the node embedding runner-up method.
6.3 ATTENTION ABLATION
Table 3: Attention ablation table. Various GNNs augmented with attention variants on the ZINC datasct. Bold represent best performance and blue represent second best.
LRGA
LRGA
Polynomial kernel (degree
Poly kernel (degree
Exponential kernel
RBF kernel
Model
MAR 4: std
MAE sdd
MAR std
MAR std
MAF + st
MAR +: st
GCN
0.445 0.009
0.440 0.006
0.664 0.011
0.467 0.088
0.450 0.011
0:457 0.007
GAT
0.421 :: 0,020
0.435 0.026
0,450 0.011
0,475 0.14
0.439 0.16
0.452
GatedGCN
0.355 0,010
0.363 0.008
0,363 0.008
0,370 0011
0,351 0
0.371 0.005
The LRGA model (equation 2 applies the low-rank attention matrix S = (X) m2 (X) m)ymm(X (X)T to the node features mx(X), that, together with mx(X), align with node factorization of 2-FWL head. In this experiment we have tested two variations of LRGA: First, removing the m4 component; and second, replacing S with standard, kernel-based attention matrices (Tsai et al. 2019). Results of
8

---

Under review as a conference paper at ICLR 2021
incorporating the different attention mechanisms to GCN, GAT, and GatedGCN and experimenting with the ZINC dataset are summarized Table 3 First, it seems incorporating m, explicitly in the LRGA module compares mostly favorably to LRGA model with m4. We attribute that mainly to the algorithmic alignment of the full LRGA model with 2-FWL, and in particular to the encoding of 2-FWI. neighborhood multisets. Second, indicated in (T'ai et al. 2019), the attention matrix could be expressed using a kernel function, S.j = -Ei= k( xe) "k(,,, æ;) We replace the low-rank attention matrix S in the LRGA module with attention matrices defined via different kernels k: polynomial kernel (of degree 2 and 4); exponential kernel (which is equivalent to the classical self-attention (Vaswani et al. 2017)) and radial basis function (RBF) kernel. full definition of the different kernels is provided in Appendix F Note that the proof of Theorem utilizes kernel defined by a polynomials feature map to align with the 2-FWI head. As the table shows, with the expection of the exponential kernel on GatedGCN, LRGA achieve superior result across all the models. The major advantage LRGA over the other kernels in that does not require to explicitly compute and store in memory the attention matrix, and exploit the low rank structure for fast multiplication.
6.4 RANDOM FEATURES ABLATION
In this experiment we wanted validate the theoretical analysis pre- sented at section 5 The dataset for this evaluation is the PATTERN dataset, which is originally equipped with random features, but in con- trast to the RGNN framework those features are sampled only once at the dataset creation stage. We evaluated the different models according to the RGNN framework, i.e., resample the features with every forward pass. The features were sampled from zero mean Gaussian distribution with variance J. where d is the input feature dimension. The evaluation protocol is the same as the one used in section 6. and we followed the 500K budget. As seen from table 4 using alternating random features improves performance for all the models. GIN and GraphSage do not appear in the main table but according (Dwivedi al. (2220) achieves 85.39% and 50.49% respectively. The LRGA augmented RGNN models maintain their superiority (even presenting small improvement com- pared to Table I and serve as an empirical validation to our main theorem.
Table 4: Random Features Evaluation
PATTERN
Model
Acc +
74.391 0.715
84.118 + 1216
GAT
81.79 +:
GraphSage
85.039 +: 0.068
LRGA GruphSuge
85,229
GatedGCN
85.848 : 0.065
LRGA GatedGCN
85.944 +
85,760 +
LRGA
86.765 :
7 CONCLUSIONS
In this work, we set ourself in a path for improving the generalization power of GNNs. To do so, we introduced the LRGA module, global self attention module, which is a variant of the dot-product self-attention with linear complexity. In order to theoretically evaluate the contribution of LRGA we analyzed our model under the RGNN framework, which is proved to be universal in probability. Under this framework we were able to show that RGNN augmented with LRGA can align with the powerful 2-FWL isomorphism test by learning simple monomial functions, which have known sample complexity bound. Under certain conditions the latter provides concrete generalization guar- antees for RGNN augmented with LRGA. Empirically, demonstrated augmenting GNN models with LRGA improves their performance significantly, often achieving SOTA performance.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Emmanuel Abbe. Community detection and stochastic block models: recent developments, 2017.
Sami Abu- Abu-El-Haija, Rami AI-Rfou, Bryan Perozzi, and Alex Alemi. Watch your step: Learning node embeddings via graph attention. In Advances Neural Information Processing Systems, volume 2018-Decem pp. 91 9180-9190, 2018.
Anonymous. From graph low-rank global attention 2-fwl approximation, 2020.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-gra fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. arXiv preprint arXiv:1901.08584 2019.
Dzmitry Bahdanau, Kyung Hyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In 3rd International Conference on Learning Representations, ICLR 2015, 2015.
Peter Bartlett, Dylan J. Foster, and Matus Telgarsky. Spectrally- margin bounds for neural networks, 2017.
Peter W Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:180..0111 01261, 2018.
Xavier Bresson and Thomas Laurent. Residual Gated Graph Convnets. Technical report, 2017.
George Dasoulas, Ludovic Dos Santos, Kevin Scaman, and Aladin Virmaux. Coloring graph neural networks for node disambiguation, 2019.
Simon S. Du, Kangcheng Hou, Barnabás P6czos, Ruslan Salakhutdinov, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels, 2019.
Vijay Prakash Dwivedi, Chaitanya K. Joshi, Thomas Laurent, Yoshua Bengio, and Xavier Bresson. Benchmarking graph neural networks, 2020.
Matthias Fey and Jan Eric Lenssen. Fast Graph Representation Learning with Py PoTch Geometric. arXiv preprint 1903::9990000000 2019.
Vikas K. Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks, 2020.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural Message Passing for Quantum Chemistry. In International Conference on Machine Learning, pp- 1263-1272, 2017.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks, 2019.
Marco Gori, Gabriele Monfardini, and Franco Scarselli. new model for learning in graph domains. In Proceedings of the International Joint Conference on Neural Networks, volume 2, pp 729-734, 2005. ISBN 0780390482. doi: 10. 100.119CNNNNN000.... 1555942.
Martin Grohe Descriptive complexity, canonisation, and definable graph structure theory, vol- ume 47, Cambridge University Press, 2017.
Martin Grohe and Martin Otto. Pebble games and linear equations. The Journal of Symbolic Logic, 80(3):797-844, 2015.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks, 2016.
William L Hamilton, Rex Ying. and Jure Leskovec. Inductive representation learning on large graphs. Advances in Neural Information Processing Systems, volume 2017-Decem, pp. 1025- 1035, 2017.
10

---

Under review as a conference paper at ICLR 2021
Weihua Hu, Matthias Fey, Marinka Zitik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open Graph Benchmark: Datasets for Machine Learning on Graphs. may 2020. httt:tttpa/x.v.coo
als 201.//055..000
Chaitanya K. Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem, 2019.
Angelos Katharopoulos, Apoorv Vyas, Nikolaos Pappas, and François Fleuret. Transformers are Inns: Fast autoregressive transformers with linear attention, 2020.
Thomas N. Kipf and Max Welling. Semi-Supervised Classification with Graph Convolutional Net- works. 5th International Conference on Learning Representations, ICLR 2017, sep 2016. URL
http://arxiv/ wttgg/ab///aaa 02907
Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann, Diffusion improves graph learn- ing, 2019.
Boris Knyazev, Graham W. Taylor, and Mohamed R. Amer. Understanding attention in graph neural networks. CoRR, abs/1905.02850, 2019. http://axxx..../g////////// hblp://bs/11900 /905.. 02850
John Boaz Lee, Ryan Rossi, Sungchul Kim, Nesreen K Ahmed, and Eunyee Koh. Attention Models in Graphs: A Survey. Technical report, 2018a. URL/tttps://dbi.org/
Juho Lee, Yoonho Lee, Jungtack Kim, Adam R. Kosiorek, Seungjin Choi, and Yee Whye Teh. Set transformer: A framework for attention- permutation-invariaan neural networks, 2018b.
Yujia Li, Richard Zemel, Mare Brockschmidt, and Daniel Tarlow. Gated graph sequence neural networks. In 4th International Conference on Learning Representations, ICLR 2016 Conference Track Proceedings, 2016.
Andreas Loukas. What graph neural networks cannot learn: depth vs width, 2019.
Andreas Loukas. How hard is graph isomorphism for graph neural networks?, 2020.
Minh-Thang Luong, Hieu Pham, and Christopher D Manning. Effective Approaches to Attention- based Neural Machine Translation. Technical report, 2015. URL BRR[:ttt:////p.ta....tt
edu/projects s/mm..
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably pow- erful graph networks. In Advances Neural Information Processing Systems 32, pp. 2156-2167. Curran Associates, Inc., 2019a. URL htttp://papers. nips. 8488
wew.eaul-sgg...--ett............ pdff
Haggai Maron, Heli Ben-Hamu, Nadav Shamir, and Yaron Lipman. Invariant and equivariant graph networks. In 7th International Conference Learning Representations, ICLR 2019, 2019b.
Christopher Morris, Martin Ritzert, Matthias Fey, William L. Hamilton, Jan Eric Lenssen, Gaurav Rattan, and Martin Grohe. Weisfeiler and Leman Go Neural: Higher-order Graph Neural Net- works. arXiv preprint 1rXiv.1810.02244, 2018
Ryan I. Murphy, Balasubramaniam Srinivasan, Vinayak Rao, and Bruno Ribeiro. Relational Pooling for Graph Representations. arXiv preprint arXiv: met::/9034.4444 2019.
Hongbin Pei, Bingzhe Wei, Kevin Chen- Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-GCN: Geomet- ric Graph Convolutional Networks. 2020. URL htthttttp/aaatti org/ 2002 05287
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. Deepwalk. Proceedings of the 20th ACM
SIGKDD international conference on Knowledge discovery and data mining KDD '14
2014. doi: 10.1145722233302222333 URL http::tpp//eec /xx. 222g/10.1145/2623333 2623732
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks, 2020.
11

---

Under review as a conference paper at ICLR 2021
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 2009. ISSN 10459227. doi: 10.1 1ALL100TTN.2200820555500000
Franco Scarselli, Ah Tsoi, and Markus Hagenbuchner. The vapnik-chervonenkee dimension of graph and recursive neural networks. Neural Networks, 108, 09 2018. doi: 10. (0.1016/ 010.
Zhuoran Shen, Mingyuan Zhang, Haiyu Zhao, Shuai Yi, and Hongsheng Li. Efficient attention: Attention with linear complexities, 2020.
Yao-Hung Hubert Tsai, Shaojie Bai, Makoto Yamada, Louis-Philippe Morency, and Ruslan Salakhutdinov. Transformer dissection: A unified understanding of transformer's attention via the lens of kernel, 2019.
Vladimir N. Vapnik. Statistical Learning Theory. Wiley-Interscience, 1998.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 1998-6008 2017.
Petar Veličković, Arantxa Casanova, Pietro Liò, Guillem Cucurull, Adriana Romero, and Yoshua Bengio. Graph attention networks. In 6th International Conference on Learning Representations, ICLR 2018, 2018. ISBN 1710. 109033..
Saurabh Verma and Zhi-Li Zhang. Stability and generalization of graph convolutional neural net- works, 2019.
Minjie Wang, Lingfan Yu, Da Zheng, Quan Gan, Yu Gai, Zihao Ye, Mufei Li, Jinjing Zhou, Qi Huang, Chao Ma, Ziyue Huang. Qipeng Guo, Hao Zhang, Haibin Lin, Junbo Zhao, Jinyang Li, Alexander Smola, and Zheng Zhang. Deep graph library: Towards efficient and scalable deep learning on graphs. ICLR Workshop on Representation Learning on Graphs and Manifolds, 2019.
org abs 91t. 01315
Holger Wendland. Scattered data approximation, volume 17. Cambridge university press, 2004.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How Powerful are Graph Neural Networks? In International Conference on Learning Representations, 2019a. URL https: //openzeview. wwt.:nee//oonoee hwtp://eeeetotdddeteeeeeeoo ryss:111dd
Keyulu Xu, Jingling Li, Mozhi Zhang, Simon S Du, Ken-ichi Kawarabayashi, and Stefanie Jegelka. What Can Neural Networks reason About? Technical report, 2019b.
Jiaxuan You, Rex Ying, and Jure Leskovec. Position-aware graph neural networks. CoRR, abs/1906.04817, 2019.
http/bbb/11900 04817
Manzil Zaheer, Satwik Kottur, Siamak Ravanbakhsh, Barnabas Poczos, Ruslan R Salakhutdinov, and Alexander J Smola. Deep sets. In Advances in Neural Information Processing Systems, pp. 3391-3401, 2017.
Chenyi Zhuang and Qiang Ma. Dual graph convolutional networks for graph- based semi- cemi-supervised classification. WWW '18, pp. 499-508, Republic and Canton of Geneva, CHE, 2018. In- ternational World Wide Web Conferences Steering Committee. ISBN 978 4781450356398. doi: 10.1145/3178896.31666 16.
http:///...............01/111..0 318661
A PROOF OF PROPOSITION 1
Proof. We will now prove the universality in probability over the distribution D of RGNNs. Let Ω do x pax be compact set of graphs, [X, A. Ω where X are the node features and A is the adjacency matrix and we assume that n is fixed. Consider f. a continuous graph function. is permutation invariant where the permutation acts all dimensions, namely,
12

---

Under review as a conference paper at ICLR 2021
f([PX, PAP")) f((X, A)) for all permutation matrices P R=x". RGNN is defined as RGNN((X) = GNN((X, ( Ri) where E R"xd are i.id. samples from D.
To prove universality in probability need to show that RGNN can approximate f to an arbitrary precision E with high probability -:
Ve, d 0 = s.t. P(IRGNN(X) f((x, A)) < E) > 1-5
where ④ are the RGNN network parameters and d the dimension of the random features RGNN.
In fact, simple RGNN composed of single message passing layer and global attribute block, a DeepSets network (Zaheer et al. 2017). suffices. The message passing layer first transfers the graph structural information to the node features by creating a factorized representation of A. This means that all the graph information is now stored in set. Then, using the universality of DeepSets network for invariant set functions can approximate f an arbitrary precision.
Let us denote the output of the message passing layer of RGNN by h1 The structural information of the graph can be transferred the node features using the message passing layer by choosing parameters such that h1 X R. AR). h1 is then fed to the DeepSets network, so we have RGNN((X) DeepSets((A) [X. R. AR)..
Observing the approximation error:
[RGNN(X) [[X, AJ) DDepSSess( ([X, R, AR) [((X,
= #DeepSets( [X, R. AR) f((x, ARR f(X,, ARR")) f(XX, A))
S [DeepSets((X, R. AR) f(x,, ARR ARRRDI+INN +I[(X, ARR") 5(XX, A))
d
We can now bound the two terms in the last inequality above. Since is defined on the compact set Ω we first make sure that *RRR" remains bounded (we assume f can be extended continuously
this domain). Since we assume D is bounded (given D. |2|| < M/2). we get:
1 ARR"
S
1 |1Al|
RR
S
1 d
|A| F
M² 4
For the second term we can achieve a bound in probability. Since f is continuous function on compact set, by the
theorem, is uniformly continuous, meaning that
VE' > 0 3E s.t A VQSEE E (Q. < = dz(f(Q), f(S)) <
Setting
E/2 we can now choose d such that with probability 1 we have ARR [X. A)) < &. Let dg be the euclidean metric, then, assume graph of fixed size n, ||Al| n and we are left
de( X
A) <
I|| p. Since with bounding | I||= in probability. Using Hoeffding's inequality we will be able to find d satisfying the conditions.
||
RRR
single entry in has mean and variance c, for simplicity we set c An entry in RRT is of the form RRR") ); = E'= Rg Note that all elements of the sum are statistically independent and bounded. Using Hoeffding's inequality:
2dt2
P
Σ
Ra
R,
-E
d
R
Ri
jj
26
2eepp
M11
(8)
1m1
For i * j:
R3
= and for i j: E
1
=1
Using union bound over all entries of R.R..:
2d112
P
RRR..
Iig 2
2n exp
-
1.jE/m]
13

---

Under review as a conference paper at ICLR 2021
Setting g/n² || and requiring 2n exp
(-2dr² 2dr² å we get M L
e² log
2n
M
8
where MM' accumulates all constant factors. Lastly, ||
r bounded by n, so the we should take
M' log 2n Finally, we have that for large enough R I|
arbitrarily
small with high probability.
For the first term, we note that S([x; AARR") F([X, R. AR) is a continuous invariant set function over bounded domain. Therefore the first term can be bounded by invoking the universal approximation theorem of invariant set functions (Zaheer et al. 20177. i.c., exist a set of parameters and model size such that the approximation error is less than 2/2.
This concludes the proof. We found that exists set network parameters and such that the approximation error is arbitrarily small.
B MULTISET ENCODING
As shown in Maron et al. (0199) the multiset encoding function, ENC, can be defined using the
collection of Power-sum Mulii-yymmeticc Polynomials (PMPs). That is, given multiset Z (Z)...., )² E Rnnxdd the encoding is defined by
ENC(Z)
Σ 2k
a
AEN
|al S
where (a1..... 0.2a), and n²
2d
Let us focus on computing a single output coordinate a of the ENC function applied to particular multiset (i.)). This can be efficiently computed using matrix multiplication Maron al. (2019)):
Let (B, 7) Nod where B,y Nd.. Then,
E (Z(.))
B 1.k k. (V
By y mean that we apply the multi-power 3 to the feature dimension, i.e.. (Y )ijj ".j" This implies that computing the multisets encoding amounts to calculating monomials y Y and their matrix multiplications y Thus the 2-FWL update rule, equation 4 can be written in the following matrix form, where for notational simplicity we denote Y = Y':
y
Y, y (B, E Nor | + In| S
C 2-FWL VIA POLYNOMIAL KERNELS
In this section, we give full characterization of feature maps, y3, of the final polynomial kernel use formulate the 2-FWL algorithm. A key tool for the derivation of the final feature map is the multinomial theorem, which we state here a slightly different form to fit our setting.
Multinomial theorem. Let us define set of variables #191, Zm composed of products of corresponding x and y's. Then.
(r19) +... Fmyya )
Σ +/=n
II (
where 1 E No. and the notation (3) in total (n+m-11 elements.
n!
The sum is over all possible a which sum to n,
14

---

Under review as a conference paper at ICLR 2021
Recall that we wish to compute y as in equation in the paper:
v II (1 2))"
II (Pa (a (a)
(0
(+)(a))) pp(a)))
We will now follow the equalities in equation to derive the final feature map. The second equality using the feature maps 9a, of the (homogeneous) polynomial kernels (Vapnik 1998) ( 222 9x which can be derived from the multinomial theorem.
Suppose the dimensions of X X are x Dj where Ei= 2Dr = D. Then, P9s consists of Dj - o7 =v(0)== | Bt. In total the
monomials of degree of the form pa. (a)
size of the feaure map PP is
D. (1))
The third equality is reformulating the feature maps (9,, on the vectors x = [20]] and a [0 "="""
x E P/2
RD//2
The last equality is due to the closure of kernels to multiplication. The final feature map, which the product kernel, is composed of all possible products of elements of the feature maps, i.e.,
d = III
Bi
| = 33. Aj E [d]
where x = [21 .2...... nb E RP/22 and æ, E Rt for all / E [d]. The size of the final feature map is I ( D:+
D1 S N where N = (*+D).
D EXTENSION OF PROPOSITION
In this section we would like to extend the proof of proposition to the case where the graph is equipped with prior node features X m s.t the network's input is [X R). As mentioned in Section 3 the isomorphism type of a graph equipped with node features claim that the node factor- [1, R. AR), where
Y [I, X, X I, A]. Following this description ization representation of the graph will be of the form R' (1.1...., 1)" R". To build the isomorphosm tensor we can use the sequence of outer products [x,17 X,1T, IXT.... ...... 1X]], where X IRD is the (-th column of X. This sequence could be represented using the first components of R'. The last two components, R and AR allow to approximate in probability phism tensor construction and conclude that [1, X, R, AR) Lastly, we have to show that we can construct this structure using RGNN, and actually we are left explain how add the vector the representation. This could be done using global attribute block as used to proof Proposition [
and I as shown in Appendix A which complete the isomor- node factorization representation.
E SAMPLE COMPLEXITY BOUND OF MONOMIALS
Corollary 6.2 in AAroa et al. 2019) provides a bound on the sample complexity, denoted C (g, 8), of polynomial F + R of the form
g(x) Σ a, x)",
(9)
where P5 E (1,2,4,6,8,...)) R. B, RD: é are the relevant PAC learning constants, and A' represents an over-parameterized, randomly initialized two-layer MLP trained with gradient descent.
C) (E, la ||3, 13 (1/()
22
15

---

Under review as a conference paper at ICLR 2021
It is not immediately clear, however, how to this theorem to learn arbitrary monomial œ since g has the above particular form. Nevertheless we show how it can be generalized to this case.
Let = (3 E No [8] I n), and note that there are N = = elements B. We assume some fixed ordering in B is prescribed. Define the sample matrix (multivariate Vandemonde) V E NRN by Va.3 3 Lemma 2.8 in (Wendland 2004) implies that V is non-singular. Let Cn.D |V- (i.e., the induced Lo matrix norm); note that Cn is dependant only upon n, D.
Lemma 1. Fix D,n E N. and let 8 E B be arbitrary. Then, there exist coefficients a E RR ||a|| S D. that x EBEB ag (3( + for Sorall
all æ E RR..
Proof. Using the multinomial theorem we have: ((3,z) + =1= Eags d,,3x² where da are positive multinomial coefficients. This equation defines linear relation between the monomial basis σ. and ((3, æ) + 1)", for 3 E B. The matrix of this system is V multiplied by positive diagonal matrix with da on its diagonal. By inverting this matrix and solving this system for œ6 the lemma is proved.
We can use this Lemma in the following way: Assume n is even or otherwise consider 2[n/2]. Further assume that the MLP m PR + R is two-layer, over- perapaarmeterieee of the form m(z, 1) (i.e., we assume there is constant plugged in an extra D + 1 coordinate). We consider training m with random initialization and gradient descent using data (æ, x²) ) TR. RR where is sampled i..d. from some distribution over R.P.
Let 9 PD+1 R defined g( g(+1) ΣBEn Og ((B, x) + In+1)", where
RN
as promised by Lemma] I Then, the learning setup described above is equivalent to training
the MLP m(x. m(x.ID+1) using data of the form ((x, 1), ((x = x²), where (æ, 1) is sampled i..dd from distribution D' over DR1 concentrated
the hyperplane ED+1
1. Now
ing the Corollary 6.2 from (Arora et al. 2019) in our case where RD+1 - is defined as g(r, DD1) EBEB ag ((3, x) + xD+1)" where B {BE E No | S n and by Lemma there exist a such that g(x, 1) = x². The sample complexity bound expression by Corollary 6.2 is therefore:
|0//| ||]| |
log(1/0)
())
Ô= (3,1)
2
Let us bound the first term in the numerator of the sample complexity expression:
D
n/2
Σ n lasl | nn. BEB
Σ lasl
Σ
3
+1
Sn. (1² + +1) n/2
Σ
laal S (n² + 1)(x11/22 CD
BEB
BEB
The first inequality due 11-112 S ||- the second by Lemma and uniting n into the main term. From the above, the bound follows.
16

---

Under review as a conference paper at ICLR 2021
F KERNEL DEFINITION
Let 2, y.y. E I2 the kernel function were defined in the following manner
Polynomial Kernel km (2, v) (12,, v) 1)
Exponential Kernel k(z, y) exp( (mrvi)
iii)
RBF Kernel k(æ, v) = exp( --p(-Ilzww1("
(iii
vd
Lets Xx, gaxd where XQ [(=b)* ...... (+²)²) and Xv {(+))".... ..... ..... (xt))" de-
notes the attention Query and Key matrices. For given kernel function i define the attention matrix S E Ruxn in the following way-
A okk S. Ei=1 Kr
G RANK ABLATION STUDY
We investigated the affects of the attention's rank the performance of GNNs augmented with LRGA on the CLUSTER dataset. The dataset contains graphs of 40 190 nodes (117 nodes in average). Our experimental setting included fixing the GNN's hidden dimensions size and changing K. Figure [ shows that ac- curacy increases with the rank values until reaches plateau around z 30 (x/77 = 0.25 where π7 is the average graph size), a fact that could be attributed to saturating the expressive- ness of the LRGA module. Moreover, the max- imal accuracy is achieved at value that corre- sponds to the maximal graph size in the dataset, smaller than what the theory predicts as func- tion of the graph size n. This rank value is enough compute any attention function on this graph collection.
Accurncy (%g
0.0
05
2.0
25
K/TZ
Figure 1: Ablation study on CLUSTER dataset. The X-axis represent the ratio between the rank parameter and the average graph size 117. The Y-axis represent network's accuracy
H IMPLEMENTATION DETAILS
In this section we describe the datasets on which we performed our evaluation. addition, we specify the hyperparameters for the experiments section in the paper. The of the model figurations are determined directly by the evaluation protocols defined by the benchmarks. It is worth noting that most of our experiments ran a single Tesla V-100 GPU, if not stated other- wise. We performed our parameter search only on and d (except for CIFAR 10 and MNIST were we searched over different dropout values), since the rest of the parameters were dictated by the evaluation protocol. The models sizes were restricted by the allowed parameter budget.
H.1 BENCHMARKING GRAPH NEURAL NETWORKS DWIVEDI ET AL. 2020
Datasets.
This benchmark contains 6 main datasets:
(i) ZINC, molecular graphs dataset with graph regression task where each node represents an atom and each edge represents a bond. The regression target is a property known as the constrained solubility (with mean absolute error evaluation metric). Additionally, the node features represent the atom's 's type (28 types) and the edge features represents the type of con- nection (4 types). The result reported for GCN used d = 60 for the 100K budget and d 90
17

---

Under review as a conference paper at ICLR 2021
(network's depth is L 12) for the 500K budget. For the GAT network used d = 60 (4 attention heads of dimension 15) for the 100K budget and = 120 (4 attention heads of di- mension 30) with L = 8 for the 500K budget. For the GatedGCN network we used d 45 for the 100K budget and d = 60 with L. = 12 for the 500K budget. All the models used K: = 30.
(ii) MNIST and CIFA R10, the known image classification problem is converted sification task using Super-pixel representation (Knyazev et al. 2019). which represents small regions of homogeneous intensity as nodes. The edges in the graph are obtained by applying k-nearest neighbor algorithm on the nodes coordinates. Node features are a concatenation of the Super-pixel intensity (RGB for CIFARIO and greyscale for MNIST) and its image coor- dinate. Edges features are the k-nearest distances. The result reported for GCN used d = 60 for the 100K budget and d = 110 with L = 8 for the 500K budget. For the GAT network we used d = 60 (4 attention heads of dimension 15) for the 100K budget and d = 122 (4 attention heads of dimension 28) with L = 8 for the 500K budget. For the GatedGCN network we used d 45 for the 100K budget and d 80 with L for the 500K budget. All the models used K = 30.
graph clas-
(iii) CLUSTER and PATTERN, node classification tasks which aim to identify embedded node structures in stochastic block model graphs [Abbe] 2017). The goal of the task is to assign each node the stochastic block it was originated from, while the structure of the graph is governed by two probabilities that define the inner-structure and cross-structure edges. A single representative from each block assigned with an initial feature that indicates its block while the rest of the nodes have no features (CLUSTER), while in the PATTERN dataset nodes are assigned with random value as input feature at the creation stage. The result reported for GCN used d 60 for the 100K budget and d = 100 with L 8 for the 500K budget (PATTERN, CLUSTER respectively). For the GAT network we used = 60 (4 attention heads of dimension 15) for the 100K budget and d = 120, 60 (8 attention heads of dimension 15, 4 attention heads of dimension 15) with L = 8, 12 for the 500K budget (PATTERN, CLUSTER respectively). For the GatedGCN network we used d = 45 for the 100K budget and d = 80, 50 with T. = 8, 12 for the 500K budget (PATTERN, CLUSTER respectively). All the models used x: = 30.
(iv) TSP, a link prediction task that tries to tackle the NP-hard classical Traveling Salesman Prob- lem (Joshi al.) 2019). Given 2D Fuclidean graph the goal is choose the edges that participate in the minimal edge weight tour of the graph. The evaluation metric for the task Fl score for the positive class. The result reported for GCN used d 60 For the GAT network we used d = 60 (4 attention heads of dimension 15). For the GatedGCN network we used d = 45. All the models used i = 30.
H.2 LINK PREDICTION DATASETS FROM THE OGB BENCHMARK (HU ET AL.. 2020
Datasets. In order to provide a more complete evaluation of our model we also evaluate it on semi-supervised learning tasks of link prediction. We searched over the same hyperparameter range E (25, 50, 100), d E {150, 256} and used k 50, d = 256 in all tasks. The three datasets were:
ogbl-ppa, an undirected unweighted graph. Nodes represent types of proteins and the edges signify biological connections between proteins. The initial node feature is a 58-dimensional one-hot-vector that indicates the origin specie of the protein. The learning task is to predict new connections between nodes. The prann/validaiion/tes: split sizes are 21M/6M/3M The evaluation metric is called Hits @ K (Hu al. 2020).
(ii) ogbl-collab, is a graph that represents a network of collaborations between authors. Every au- thor in the network is represented by a node and each collaboration is assigned with an edge. Initial node features are obtained by combining word embeddings of papers by that author (128- dimensional vector). Additionally, each collaboration described by the year of collab- oration and the number of collaborations in that year as weight. The rain/validation/test split sizes are 1/ Similarly to the previous dataset, the evaluation metric is Hits K.
(ii) ogbl-ddi- undirected unwighted graph which represent drug-drug interaction. Each Node represents FDA approved or experimental drug. The edges represent interactions between drugs and represent the joint effect of taking both drugs together. The learning task is to predict new drug to drug interactions. The train/validation/tss split sizes are 1M/150K/150K. The evaluation here is also Hits@K.
18


Reviews:
[{"review_id": "wrQyrtU53y", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "**Post-discussion update:**\n\nThe authors have addressed all my comments. It is unfortunate that a comparison with diffusion graph augmentation could not be added, but I understand the reason provided by the authors and this anyway does not significantly detract from the presented results. Since my original score already marked this as a good paper recommending acceptance, it is left unchanged.\n\n---\n\n**Original review:**\n\nThis work proposes to enhance graph neural networks to incorporate global relations between nodes together with local relations learned from the neighborhood structure of the graph. In principle, these global relations are formulated as being computed directly from node features, thus considering the graph as a set of nodes and ignoring the edges between them, but it should be noted that when applied in deeper layers, the node features would encode some edge (or graph) information propagated from the GNN component that still exist in the augmented architecture. To avoid learning or training an unfeasible number of pairwise relations (essentially quadratic in the number of nodes in the graph), the authors propose here to only consider low rank matrices, fixing an upper bound on the rank and thus limiting the learned weights to a reasonable amount. Next, the learned relations between nodes are used together with the ones coming from the graph edges to apply the typical message propagation seen in GNNs (with several such architectures considered here - showing the versatility of the approach as a generally useful module), which establishes the method as implementing an attention mechanism and justifying the name \"low rank global attention\". \n\nOn the theoretical side, the authors establish a relation between their LRGA-augmented approach and the 2-FWL test, which considers coloring of node pairs to produce histograms that encode and compare graph structures. Interestingly, instead of making strict assumptions on the node features provided with the graph, the authors rely here on random features, thus letting the edge composition of the graph dictate the information extracted by the network. Along the way, they also provide interesting insights into the universality of random GNNs, which I must say, may be a bit lost when only presented as a sidenote that is not directly related to the main point of the paper here. Nevertheless, it is an interesting contribution. On the applicative side, the LRGA augmentation is applied to several dominant GNN architectures and generally shows effective benefits in several tasks, benchmarked by carefully following the guidelines provided by recent increasingly-popular attempts (such as the OGB) to standardize comparison protocols in the field of graph representation learning.\n\nThe proposed approach here is interesting, well motivated, and supported by solid theoretical and empirical evidence, and therefore I recommend accepting it to the conference. That being said, I have two main suggestions for improvement:\n\n- First, it seems to me that the low rank attention matrix here can also be regarded through the lens of kernel learning. It may be interesting to consider this relation here, and compare (certainly in discussion, or maybe even empirically) the proposed approach to learning attention weights via popular kernel learning methods that also address tractable optimization over what would naively require O(n^2) kernel entries to be learned.\n\n- Second, an alternative approach to attention-based incorporation of less local information, somewhat bypassing edge-based neighborhoods, in GNNs is to a priori modify the structure of the graph to augment it with additional weighted edges. This type of approach can be seen, for example, in \"Diffusion Improves Graph Learning\" (Klicpera et al., NeurIPS 2019). How does LRGA compare to using such diffusion augmentation? A comparison seems highly warranted here.\n\nFinally, a minor remark: the notations in this paper are a bit difficult to follow when considering concatenations and matrix operations over 3-order tensors. It would be good to properly clarify the relevant notations and operations a bit more rigorously, even though with enough effort one can infer what is going on from context.", "extra_scores": {}, "extra_text": {}}, {"review_id": "GdtaTecdUus", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The paper proposes the Low-Rank Global Attention (LRGA) module augmented to GNNs to improve generalization power. In particular, given an input graph, the model runs the LRGA module and the GNN module to aggregate node representations on this graph. The input and the outputs of these two modules are concatenated at each layer, followed by a single fully-connect layer (m5) to produce input for the next layer. The LRGA module applies the self-attention mechanism [1], but replacing the softmax layer by the global normalization. \n\nPros. The results are promising.\n\nCons. \n\ni) The motivation to propose LRGA by replacing the softmax layer in the self-attention mechanism [1] by the global normalization is not well enough. The graph self-attention networks (such as [3,4]) show competitive results, and they can be applied for large graphs. Thus, LRGA is incremental and not technically sound.\n\nii) The paper does not discuss the most closely related work, Dual Graph Convolutional Networks (DualGCN) [2]. The architecture LRGA+GNN is similar to DualGCN. Changing from using GCN to another GNN is straightforward, thus the work lacks novelty.\n\niii) The roles of m1, m2, and m3 are similar to the query, key, and value matrices in the self-attention mechanism, respectively. But why LRGA employs m4? m4 does not have a specific role as it can be placed outside LRGA and put inside Equation 1. \nNote that [5] shows that using the vector concatenation/sum-pooling/LSTM over different layers can improve the performance. But, I do not see the role of X^l in Equation 1. What is it?\n\niv) Given the same GNN module with the same hidden size, the proposed LRGA+GNN has much larger parameters than GNN. This limitation restricts to use of deeper layers. \n\nMinor things: Parentheses in Equation 2 should use between m1 and m2, not m2 and m3.\n\n[1] Attention is all you need. NIPS 2017.\n[2] Dual Graph Convolutional Networks for Graph-Based Semi-Supervised Classification. WWW 2018.\n[3] Graph-Bert: Only Attention is Needed for Learning Graph Representations. https://arxiv.org/abs/2001.05140\n[4] Hyper-SAGNN: a self-attention based graph neural network for hypergraph. ICLR 2020.\n[5] Representation Learning on Graphs with Jumping Knowledge Networks. ICML 2018.\n\n=======================\nAfter reading the authors' response:\n\ni. As shown in (new) Table 3 in the revised version, the results of using the global normalization are not better than that of using the softmax layer in the self-attention mechanism. Hence the motivation is not enough.\n\nii. To have the faster computation, we have SGC[1], FastGCN[2]. To have powerful GNNs, we have GIN[3]. Inspired by DualGCN, we can build a new combination (e.g., SGC+GIN) together with using the vector concatenation/sum-pooling/LSTM over different layers [5] to further improve the performance and have a faster computation. That's reason why the novelty of LRGA+GNN is weak.\n\n[1] Simplifying Graph Convolutional Networks. ICML 2019. [2] Fastgcn: Fast learning with graph convolutional networks via importance sampling. ICML 2018. [3] How Powerful are Graph Neural Networks? ICLR 2019. [5] Representation Learning on Graphs with Jumping Knowledge Networks. ICML 2018.\n\nI keep my score unchanged.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "6sJ3ohpW6K-", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "This work proposes a Low-Rank Global Attention (LRGA) module for GNN which is more efficient in terms of computation and memory than the dot-product attention. Then the authors prove that LRGA augmented RGNN algorithmically aligns with a single head 2-FWL update step. The authors claim that if one network has algorithmically alignment with an algorithm, then the network has good generalization guarantee. Based on this, the network with the proposed LRGA can enjoy better generalization performance. \n\nTo be honest, I am not familiar to GNN and its related theory. For a general reader, I have the following questions. \n\nMetric:\n1)\tGood theoretical guarantees. The authors well prove the algorithmically alignment of LRGA. To be honest, I am not familiar to GNN and its related theory. So if as claimed by the authors that if one network has algorithmically alignment with an algorithm, the network has good generalization guarantee, then the theoretical results in this work can guarantee better performance of the proposed LRGA.\n2)\tThe experimental results also show the superiority of LRGA. When equipped with LRGA, the GNN baselines can enjoy much better results. But as I mentioned, I am not familiar to GNN, and am not very sure whether the compared methods are state-of-the-arts in this field. \n\nSome issues.\n1)\tThe low-rank based attention is not novel actually. Low-rank based models are well studied in model compression, data structure modeling, in which most of the works also aim to improve the generalizations by reducing redundant parameters. So here the authors use the low-rankness to improve the generalization is not new.\n2)\tThe authors claim that if one network has algorithmically alignment with an algorithm, the network has good generalization guarantee. This is hard to understand intuitively. Since this is the main basic claim in this work, the authors should well explain it. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "0OzX0mXG9Jx", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "##########################################################################\n\nSummary\n\nThe paper presents the Low-Rank Global Attention module that can be incorporated into Graph Neural Networks (GNN) to improve their generalization power. It analyses and proves the Random Graph Neural Network is universal in probability but with limited generalization, while the RGNN augmented with LRGA aligns with a powerful graph isomorphism test, namely the 2-FolkloreWeisfeiler-Lehman (2-FWL) algorithm. The results validate the effectiveness of augmenting existing GNN layers with LRGA.\n\n##########################################################################\n\nPros:\n+ Overall, the paper is well written and structured. The theoretical analysis of RGNN and its augmentation with LRGA is interesting. \n+ Extensive experiments are conducted, and the results show the effectiveness of LRGA.\n\n##########################################################################\n\nCons:\n- The main concern of this paper is its similarity to a missing reference [Puny et al., 2020]. In that paper, the exact same low-rank global attention module is proposed and incorporated into GNN to improve the performance. A similar theoretical analysis is also conducted in [Puny et al., 2020]. A detailed comparison with [Puny et al., 2020] is expected. \n\n- From Table 1, we can see that the argumentation with LRGA has different effects on different GNNs and with different parameter budget. For example, the improvement on GatedGCN is less compared to that on the others. The reasons behind this are expected. \n\nMissing reference:\nPuny et al. From Graph Low-Rank Global Attention to 2-FWL Approximation. In Proc. of ICML Workshop Graph Representation Learning and Beyond, 2020.\n\n##########################################################################\n\nMinor issue:\n* In Section 6.3, it is claimed that GraphSage achieves an accuracy of 50.49%, and it seems a typo. It should be 81.25%.  \n\n##########################################################################\nAfter discussion:\nSince the authors and other reviewers have addressed my concerns, I would like to change my score. The introduction of LRGA into the RGNN is interesting with the theoretical analysis, although the network design is incremental. I am now leaning towards borderline acceptance. \n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper provides some contribution to the field by exploiting in an unexplored  way background knowledge already covered by relevant literature. Presentation of the proposal is well structured and clear. The paper is also providing interesting theoretical and experimental results. The theoretical results, however, could be better explained. 
Overall the proposed work seems to be incremental. Perhaps a deeper investigation into the relationships with diffusion augmentation would add more value to the contribution.

Decision: Reject