Multi-hop Attention Graph Neural Network
Authors: Guangtao Wang
Zhitao Ying
Jing Huang
Jure Leskovec
Venue:  (2021)

Abstract: Self-attention mechanism in graph neural networks (GNNs) led to state-of-the-art performance on many graph representation learning task. Currently, at every layer, attention is computed between connected pairs of nodes and depends solely on the representation of the two nodes. However, such attention mechanism does not account for nodes that are not directly connected but provide important network context, which could lead to improved predictive performance. Here we propose Multi-hop Attention Graph Neural Network (MAGNA), a principled way to incorporate multi-hop context information into attention computation, enabling long-range interactions at every layer of the GNN.  To compute attention between nodes that are not directly connected,
MAGNA diffuses the attention scores across the network, which increases the ''receptive field'' for every layer of the GNN.
Unlike previous approaches, MAGNA uses a diffusion prior on attention values, to efficiently account for all paths between the pair of disconnected nodes. This helps MAGNA capture large-scale structural information in every layer, and learn more informative attention. Experimental results on node classification as well as the knowledge graph completion benchmarks show that MAGNA achieves state-of-the-art results: MAGNA achieves up to 5.7% relative error reduction over the previous state-of-the-art on Cora, Citeseer, and Pubmed. MAGNA also obtains the best performance on a large-scale Open Graph Benchmark dataset. On knowledge graph completion  MAGNA advances state-of-the-art on WN18RR and FB15k-237 across four different performance metrics.

Under review as a conference paper at ICLR 2021
MULTI-HOP ATTENTION GRAPH NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Self-attention mechanism in graph neural networks (GNNs) led to state-of-the- art performance on many graph representation learning task. Currently, every layer, attention is computed between connected pairs of nodes and depends solely on the representation of the two nodes. However, such attention mechanism does not account for nodes that are not directly connected but provide important net- work context, which could lead to improved predictive performance. Here we propose Multi-hop -hop Attention Graph Neural Network (MAGNA), a principled way to incorporate multi-hop context information into attention computation, enabling long-range interactions at every layer of the GNN. To compute attention between nodes that are not directly connected, MAGNA diffuses the attention scores across the network, which increases the "receptive field" for every layer of the GNN. Un- like previous approaches, MAGNA uses a diffusion prior on attention values, to efficiently account for all paths between the pair of disconnected nodes. This helps MAGNA capture large-scale structural information in every layer, and learn more informative attention. Experimental results on node classification well as the knowledge graph completion benchmarks show that MAGNA achieves state- of-the-art results: MAGNA achieves up to 5.7% relative error reduction over the previous sfate-of-thh-art on Cora, Citeseer, and Pubmed. MAGNA also obtains the best performance on large-scale Open Graph Benchmark dataset. On knowledge graph completion MAGNA advances state-of of-the-art on WNISRE and FB15k- 237 across four different performance metrics.
INTRODUCTION
The introduction of the self-attention mechanism (Bahdanau et al. 2015: Vaswani al. 2017
has pushed the statc-of-the-as in many domains including graph presentation learning Radford
al. 2019: Devlin et al. 2019 Liu al., 2019a Lan al. 2019). Graph Attention Network
(GAT) (Veličković et al. 2018) and related models Li et al.) 2018 Wang et al. 2019a Liu et al.)
2019b Oono& & Suzuki 2020 developed attention mechanism for Graph Neural Networks (GNNs),
which compute attention scores between nodes connected by edge, allowing the model to attend
to messages of node's 's direct neighbors according to their attention scores.
However, such attention computation on pairs of nodes connected by edges implies that node can only attend to its immediate neighbors to compute its (next layer) representation. This implies that receptive field of single GNN layer is restricted to one-hop network neighborhoods. Although stacking multiple GATs could in principle enlarge the receptive field and learn non-neighboring interactions, such deep GAT architectures suffer from the oversmoothing problem (Wang et al., 2019a Liu et al. 20196) Oono & Suzukil 2020) and do not perform well in practice. Furthermore, edge attention weights the single GAT layer are based solely on representations of the two nodes at the edge endpoints, and do not depend on their graph neighborhood context. In other words, the one-hop attention mechanism in GAT' limits their ability to explore the relationship between the broader graph structure and the attention weights While previous works (Xu et al.) [0188] Klicpera al. 2019b) have shown advantages in performing multi-hop pesssag--passing these approaches are not graph-attention based. Therefore, incorporating multi-hop neighboring context into the attention computation graph neural networks had not been explored.
single layer,
Here we present Multi-hop Attention Graph Neural Network (MAGNA), effective and efficient multi-hop self-attention mechanism for graph structured data. MAGNA uses a novel graph attention diffusion layer (Figure [], where first compute attention weights edges (represented by solid arrows), and then compute self-attention weights (dotted arrows) between disconnected pairs of nodes through an attention diffusion process using the attention weights on the edges.

---

Under review as a conference paper at ICLR 2021
Our model has two main advantages: 1) MAGNA captures long-range interactions between nodes that are not directly connected but may be multiple hops away. Thus the model enables effective long-range message passing, from important nodes multiple hops away. 2) The attention computa- tion in MAGNA is context-dependent. The attention value in GATs (Veličkovié et al., 2018) only depends node representations of the previous layer, and is zero between disconnected pairs of nodes. In contrast, for any pair of nodes within a chosen multi-hop neighborhood, MAGNA com- putes attention by aggregating the attention scores over all the possible paths (length z 1) connecting the two nodes.
Theoretically we demonstrate that MAGNA places a Personalized Page Rank (PPR) prior on the attention values. We further apply spectral graph analysis to show that MAGNA has the capability of emphasizing on large-scale graph structure and lowering high-frequency noise in graphs. Specif- ically, MAGNA enlarges the lower Laplacian eigen-values, which correspond to the large-scale structure in the graph, and suppresses the higher Laplacian eigen-vale values which correspond to more noisy and fine-grat tme-grained information in the graph.
We experiment on standard datasets for semi- supervised node classification well as knowl- edge graph completion. Experiments show that MAGNA achieves state-of-the-art results: MAGNA achieves up to 5.7% relative error reduc- tion over previous state-of-the-an on Cora, Cite- seer, and Pubmed. MAGNA also obtains better performance on large-scale Open Graph Bench- mark dataset. On knowledge graph completion, MAGNA advances state-of-the-art on WNI8RR and FB FB15k-237 across four metrics, with the largest gain of 7.1% the metric of Hit at 1.
GAD
a'
B
D.C.
A g( Vn) apc
a AB = [(aps. ((o))(())))
aoc f((go apul)
Figure 1: Multi-hop attention diffusion. Con- sider making a prediction at nodes A and D. Left: A single GAT layer only computes atten- tion scores a between directly connected pairs of nodes (i.e., edges) and thus QD.C thermore, the attention Q, between A and B only depends on their node representations. Right: A single MAGNA layer is able to: (1) capture the information of two-hop neighbor C to D via the diffused multi-hop attention a' D.C; And, (2) enhance graph structure learn- ing by considering all paths between nodes via diffused attention based on powers of graph ad- jacency matrix.
Furthermore, show that MAGNA with just 3 layers and 6 hop wide attention per layer signif- icantly out-performs GAT with 18 layers, even though both architectures have the same recep- tive field. Moreover, our ablation study reveals the synergistic effect of the essential components of MAGNA. including layer normalization and multi-hop diffused attention. We further observe that compared GAT, the attention values learned by MAGNA have higher diversity, indicating the ability to better pay attention important nodes.
Fur-
MULTI-HOP ATTENTION GRAPH NEURAL NETWORK (MAGNA)
We first discuss the background and then explain Multi-hop Attention Graph Neural Network's 's novel multi-hop attention diffusion module and its overall model architecture.
2.1 PRELIMINARIES
(V.E) be given graph, where V is the set of N₂, nodes, & C V x V is the set of Ne edges connecting M pairs of nodes in V. Each node e E V and each edge e E & are associated with their type mapping functions: o V + T and 1 + R. Here T and R denote the sets of node types (labels) and edge/relation types. Our framework supports learning on heterogeneous graphs with multiple elements in R.
A general Graph Neural Network (GNN) approach learns an embedding that maps nodes and/or edge types into a continuous vector space. Let X E N,,,, and R N. be the node embedding and edge/relation type embedding, where N₂, = [V] N, = (R], d, and d, represent the embedding dimension of node and edge/relation types, each row 2; X :] represents the embedding of node (1 < i < N,), and r; = R(j :] represents the embedding of relation r, (1 S S N,).
MAGNA builds on GNNs. while bringing together the benefits of Graph Attention and Diffusion techniques. The core of MAGNA is Multi-hop Attention Diffussion, a princi- pled way to learn attention between any pair of nodes in scalable way, taking into
2

---

Under review as a conference paper at ICLR 2021
account the graph structure and enabling multi- hop context-dependen attention directly.
Output: Final node embedding Ht
The key challenge here is how to allow for flex- ible but scalable context-dependent multi-hop hop at- tention, where any node can influence embedding of any other node in a single GNN layer (even if they are far away in the underlying network). Sim- ply learning attention scores over all node pairs is infeasible and would lead to overfitting and poor generalization.
Layer & Add
Feed Forward
Layer Norm & Add
F1
Aggragation with Diflused Attention
2.2 MULTI-HOP ATTENTION DIFFUSION
Mutti-head Attention between Nodes
We first introduce attention diffusion to compute the multi-hop attention directly, which operates on the MAGNA's 's attention scores at each layer. The input to the attention diffusion operator is a set of triples (vi, T'k tt), where Ui, Vi are nodes and r' is the edge type. MAGNA first computes the all edges. The attention dif- fusion module then computes the attention values between pairs of nodes that are not directly con- nected by an edge, based on the edge attention scores, via diffusion process. The attention dif- fusion module can then be used as component in MAGNA architecture, which we will further elab- orate in Section 2.3
A,e
Inputs: Initial node and relation embeddings H", P
Figure 2: MAGNA Architecture. Each MAGNA block consists of attention computa- tion, attention diffusion, layer normalization, feed forward layers, and 2 residual connec- tions for each block. MAGNA blocks can be stacked to constitute deep model. As illus- trated on the right, context-dependent attention is achieved via the attention diffusion process. Here Us, U/ Up, Ug E V are nodes in the graph.
attention scores
Edge Attention Computation. At each layer I, vector message is computed for each triple (Wi, Tk, R/). To compute the representation of 1 at layer 1 7+ 1, all messages from triples incident to by are aggregated into single message, which is then used to update o/
In the first stage, the attention score of edge (e,, The v.) is computed by the following:
Si,k. = LeakyReLU((!" tanh( w(()) h 1 (W,")) n (1) (IW( (l
(1)
(1)
where wi(() w
E Rdd xd()) w E ad xd, and Va E IR xx1xad are the trainable weights shared
by 1-th layer. h E Rd represents the embedding of node the trainable relation embedding of the k-th relation type тı (1 < k S N,), and alib denotes con- catenation of embedding vectors a and For graphs with no relation type, we treat as a degenerate categorical distribution with 1 category|
I-th layer, and h = 2,, Ts is
Applying Eq. on each edge of the graph G, we obtain an attention score matrix S(D; (1)
k,k.j* if (u., appears in g
00, otherwise
Subsequently we obtain the attention matrix A by performing row-wised softmax over the score matrix 5(); A softmax(S")) A denotes the attention value layer I when aggregating message from node j to node i.
(I)
Attention Diffusion for Multi-hop Neighbors. In the second stage, we further enable attention between nodes that are not directly connected in the network. We achieve this via the following attention diffusion procedure. The procedure computes the attention scores of multi-hop neighbors via graph diffusion based on the powers of the I-hop attention matrix A:
A
Σ
0,A' where Σ 0, and 0, >
(3)
where 0; is the attention decay factor and 0: 0.+1- The powers of attention matrix, A', give the number of relation paths from node h to node t of length up to i, increasing the receptive field of the attention (Figure L). Importantly, the mechanism allows the attention between two nodes to not only depend on their previous layer representations, but also taking into account of the paths between the
In this case, we can view that there is only one "pseudo" relation type (category), i.c., N₂
3

---

Under review as a conference paper at ICLR 2021
nodes, effectively creating attention shortcuts between nodes that are not directly connected (Figure Ip. Attention through each path is also weighted differently, depending on and the path length. In our implementation choice is based on the inductive bias that nodes further away should be weighted less in message ag- gregation, and nodes with different relation path lengths to the target node are sequentially weighted in an independent manner. In addition, notice that if we define On- = a E (0, A I, then Eq. 3 gives the Personalized Page Rank (PPR) procedure on the graph with the attention matrix and teleport probability a. Hence the diffused attention weights, Asj. can be seen as the influence of node j to node i. We further elaborate the significance of this observation in Section
utilize the geometric distribution 8, a(1 a)', where (0, 1]. The
We can also view A,₃ as the attention value of node j to since Σ Aij- = graph attention diffusion based feature aggregation as
2
We then define the
(4) where θ is the set of parameters for computing attention. Thanks to the diffusion process defined in Eq. 3 MAGNA uses the same number of parameters as if we were only computing attention between nodes connected via edges. This ensures runtime efficiency as well as good model generalization.
AttDiffusion(( H ,) = AH
Approximate Computation for Attention Diffusion. For large graphs computing the exact atten- tion diffusion matrix A using Eq. B may be prohibitively expensive, due computing the powers of the attention matrix (Kliepera et al., 2019a). To resolve this bottleneck, we proceed as follows: Let (1) be the input entity embedding of the 1-th layer (H = X) and 0; = a(1 a)'. Since MAGNA only requires aggregation via AH (1) we can approximate (H by defining a sequence
( which converges to the true value of AH (Proposition) 1 as K - 0o: ( H z (k-1) (1 (x) AZ( + az where O
(5)
Proposition 1. 1im ((K) = AH (1)
In the Appendix we give the proof which relies on the expansion of Eq. 5
Using the above approximation, the complexity of attention computation with diffusion is still O(EE), with a constant factor corresponding to the number of hops K. In practice, we find that choosing the values of K such that 3 K 10 results in good model performance. Many real- world graphs exhibit small-world property, in which case even smaller value of K is sufficient. For graphs with larger diameter, we choose larger K, and lower the value of
2.3 DIRECT MULTI-HOP ATTENTION BASED GNN ARCHITECTURE
Figure provides an architecture overview of the MAGNA Block that can be stacked multiple times. Multi-head Graph Attention Diffusion Layer. Multi-head attention (Vaswani et al. 2017] Veličković et al. (2188) is used allow the model jointly attend information from different representation su sub-spaces at different viewpoints. In Eq. 6 the attention diffusion for each head i is
computed separately with Eq. and aggregated:
H (1) MultiHcad(G, (r (11-0 M
(Ic_, head.) W..
where
(6)
(T,)),)))) head, AtDiffusion(G H O.), H LayerNorm ("),,
where || denotes concatenation and O; are the parameters in Eq [ for the i-th head s M), and Wa represents a parameter matrix. Since we calculate the attention diffusion in recursive way in
Eq. 5
add layer normalization which helpful stabilize the recurrent computation procedure (Ba
et al. 2016).
Deep Aggregation. Moreover our MAGNA block contains fully connected feed-forward sub- layer, which consists of a two-layer feed-forward network. We also add the layer normalization and residual connection in both sub-layers, allowing for a more expressive aggregation step for each
block (Xiong et al. 2020):
H H+1
H (1)
(++1- W (
ReLU (W ( LayerNorm(E(( + A (1+1)
MAGNA generalizes GAT. MAGNA extends GAT via the diffusion process. The feature aggre- gation in GAT is (1+1) = (AH (()), where a represents the activation function. We can
OOtaiined by the attention definition A softmax(S(0)) and Eq.
4

---

Under review as a conference paper at ICLR 2021
divide GAT layer into two components follows:
H(++1) (
(1)
In component (I), MAGNA removes the restriction of attending to direct neighbors, without re- quiring additional parameters as A is induced from A. For component (2) MAGNA uses layer normalization and deep aggregation which achieves significant gains according to ablation studies in Table Compared to the "shallow" activation function elu in GAT, we can view deep aggrega- tion (i.c., two-layer MLP) as a learnable deep activation function as two layer MLP can approximate many different functions (Pinkus T999).
ANALYSIS OF GRAPH ATTENTION DIFFUSION
In this section, we investigate the benefits MAGNA from the viewpoint of discrete signal process- ing on graphs (Sandryhaila & Moura 2013). Our first result demonstrates that MAGNA can better capture large-scale structural information. Our second result explores the relation between MAGNA and Personalized PageRank (PPR).
3.1 SPECTRAL PROPERTIES OF GRAPH ATTENTION DIFFUSION
We view the attention matrix A of GAT, and A of MAGNA as weighted adjacency matrices, and apply Graph Fourier transform and spectral analysis (details in Appendix) to show the effect of MAGNA as graph low-pass filter, being able to more effectively capture large-scale structure in graphs. By Eq. 3 the sum of each row of either A or is 1. Hence the normalized graph
Laplacians are Leym = - and Lyym = A for A and A respectively. We can get the following proposition:
Proposition 2. Let Xg and X. be the i-th eigeinyalues of Lyym and Laym-
Xg
1- (1-a)(1120) X75
1
X
α + X I-a
Refer to Appendix for the proof. We additionally have X [0, 2] (proved by (Ng et 2002 Eq. 9 shows that when X is small such that - + X < 1, then X A whereas for large XY, X < Ag. This relation indicates that the use of A increases smaller eigenvalues and decreases larger eigenvalues See Section 4.3 for its empirical evidence. The low-pass effect increases with smaller
a.
The eigenvalues of the low-frequency signals describe the large- scale structure in the graph (Ng et al. 2002) and have been shown to be crucial in graph tasks (Klicpera et al.) (2019b). As X a [0,2] Ng et al. 2002) and I-a > O, the reciprocal format in Eq. 9 will amplify the ratio of lower eigenvalues the sum of all eigenvalues. In contrast, high eigenvalues corresponding noise are suppressed.
3.2 PERSONALIZED PAGERANK MEETS GRAPH ATTENTION DIFFUSION
We can also view the attention matrix A as random walk matrix on graph 9 since D A.j =1
N₂
and Ai,; 0. If we perform Personalized PageRank (PPR), with parameter E (0, on G with transition matrix A, the fully Personalized PageRank (Lofgren 2015) is defined as: Appr a(I (1 a)A)
(10)
Using the power series expansion for the matrix inverse, we obtain
A ppr Σ (1-
Σ a(1 a)
(11)
Comparing to the diffusion Equation with 0; a(1 a) we have the following proposition. Proposition 3. Graph attention diffusion defines a personalized page rank with parameter (o, 1] on G with transition matrix A, i.e., A= A=Appr-
The parameter a in MAGNA is equivalent the teleport probability of PPR. PPR provides good relevance score between nodes in a weighted graph (the weights from the attention matrix A). In
'The eigenvalues of A and correspond to the same eigenvectors, as shown in Proposition 2 in Appendix.
5

---

Under review as a conference paper at ICLR 2021
Table I: Node classification accuracy on Cora, Citeseer, Pubmed. MAGNA achieves state-of-
Models
Cora
Citeseer
Pubmed
GCN (Kipf & Welling 2016
81.5
70.3
79.0
Chebyshev (Deftcrrard ct al. 2016
81.2
69.8
74.4
Baselines
DualGCN (Zhuang & Ma 2018
83.5
72.6
80.0
JKNet (Xu et al. 2018
81.1
69.8
78.1
LGCN (Gao et al. 2018
83.3 + 0.5
73.0 + 0.6
79.5 0.2
Diffusion-GCN (Klicpera al. 2019b
83.6 1 0.2
73.4 0.3
79.6 0.4
APPNP (Klicpera et 2019a
84.3 0.2
71.1 0.4
79.7
g-U-Nets (Gao & Jr. 2019
84.4 0.6
73.2
7.2
GAT (Veličković et al. 2018
83.0 0.7
0.7
0.3
No LayerNorm
83.8 : 0.6
0.5
0.2
Abl.
No Diffusion
83.0
71.6
0.3
No Feed-Forward
84.9 0.4
7..2
0.3
No (LayerNorm + Feed-Forward)
84.3 + 0.6
72.6 0.4
79.6 0.4
MAGNA
85.4 + 0.6
73.7 0.5
81.4 + 0.2
based on the implementation in https//ggghuubcoo//pppe////////
replace the feed forward layer with elu used in GAT.
summary, MAGNA places PPR prior over node pairwise attention scores: the diffused attention between node and j depends on the attention scores on the edges of all paths between i and j.
EXPERIMENTS
(1) On node classification achieve average of 5.7% relative error reduction; (2) On knowledge graph completion we achieve 7.1% relative improvement in the Hit at metric We compare with numbers reported by baseline papers when available.
We evaluate MAGNA on two classical task
4.1 TASK 1: NODE CLASSIFICATION
Datasets. We employ four benchmark datasets for node classification: (1) standard citation network benchmarks Cora, Citeseer and Pubmed (Sen et al., 2008 Kipf & Welling 2016); and (2) a bench- mark dataset ogbn-arxiv on 170k nodes and 1.2m edges from the Open Graph Benchmark (Wei-) hua Hu 2020). We follow the standard data splits for all datasets. Further information about these datasets IS summarized in the Appendix.
Baselines. We compare against a comprehensive suite of state-of-the-ars GNN methods includ- ing: GCNs (Kipf & Welling, 2016), Chebyshev filter based GCNs (Defferrard et al. 2016). Du-
alGCN (Zhuang & Maj (2018), JKNet (Xu al.] 2018)). LGCN (Gao al. 2018). Diffusion-
GCN (klicpera et al.] (2019)), APPNP (Klicpera et al. 2019a), Graph U-Nets (g-U-Nen)
(Gao
& Ji 2019), and GAT (Veličković et al. 2018).
Experimental Setup. For datasets Cora, Citeseer and Pubmed, we use 6 MAGNA blocks with hid- den dimension 512 and 8 attention heads. For the large-scale ogbn-arxiv dataset, 2 MAGNA blocks with hidden dimension 128 and attention heads. Refer to Appendix for detailed description of all hyper--arraeeten and evaluation settings.
Table 2: Node classification accuracy the OGB Arxiv dataset.
OCN
Nodeinge
IKNe 2013
GuAN Zhung 2018 71JY=
Kipl Welling 2016 71.74 11.59
[amilton 2017
Grower
2016
MLP
MAGNA
71,97
70.07
+
72.66 B.T4
Results. We report node classification accuracies on the benchmarks. Results are summarized in MAGNA improves over all methods and achieves the new state-of-the-aa the on all
Tables and 2 datasets.
All datasets used are public, and the code will be released at the time of publication.
Please the definitions of these tasks in Appendix.

---

Under review as a conference paper at ICLR 2021
Table 3: KG Completion on WN18RR and FB15k-237. MAGNA achieves state of the art.
WNI8RR
-317
Models
MR
MRR
H@1
H@3
H@ 10
MR
MRR
H@1 1
H@3
H 10
Transt: Bordes et al
2013
3384
.26
.001
357
.294
.655
RotatE Sun et al. 2019
3340
.476
.428
.492
.571
177
.338
.241
.375
.533
OTE
Tanc ct 2020
.491
.442
-511
.583
.361
.267
.396
.550
ROTH
Chami or 3. 2020
.496
.449
.514
.586
.344
.246
.380
.535
ComplEx
(Irounloon ct
2016
5261
.44
.41
.46
.51
339
.247
.158
.255
.428
QuatE
Zhäng ct al.
2019
2314
.488
.438
.508
.582
.366
.271
.401
.556
CoKE
Wang ct al.
2019b
.475
.437
.490
.552
.361
.269
.398
.547
ConvE
Detmmer al. 20188
4187
.43
.40
.44
-52
244
.325
.237
.356
.501
DistMuli Yang el al. 2015
5110
.43
.39
.44
.49
254
.241
.155
.263
.419
TuckER (Balazevic et al. 2019
.470
.443
.42
.526
.358
.266
.392
.544
R-GCN Schlichikrull ct 2018
.249
.151
.664
.477
SACN (Shang et al. 2019
.47
.43
.48
.35
.26
.39
.54
A2N (Bansal ct al. 2019
.45
.42
.46
.317
.232
.488
.486
MAGNA + DistMull
2545
.502
.459
.519
.589
138
.369
.75
409
.563
Ablation study. We report (Table D the model performance after removing each component of MAGNA (layer normalization, attention diffusion and deep aggregation feed forward layers) from every layer of MAGNA. Note that the model is equivalent GAT without these three components. We observe that both diffusion and layer normalization play crucial role in improving the node classification performance for all datasets. While layer normalization alone does not benefit GNNs, its use in conjunction with the attention diffusion module significantly boosts MAGNA's ' perfor- mance. Since MAGNA computes many attention values, layer normalization is crucial in ensuring training stability (Ba et al. 2016). Meanwhile, we also remove both layer normalization and deep aggregation feed forward layer, and only keep the attention diffusion layer (see the next-to-last row of Table []. Comparing to GAT, attention diffusion allows multi-hop attention in each layer still benefits the performance of node classification.
4.2 TASK 2: KNOWLEDGE GRAPII COMPLETION
Datasets. We evaluate MAGNA on standard benchmark knowledge graphs: WN18RR (Dettmers)
al. 2018) and FB15K-237 (Toutanova & Chen 2015). See the statistics of these KGs in Appendix.
Baselines. We compare MAGNA with oftee-of-the-at baselines, including (1) translational dis- tance based models: TransE (Bordes et al. 2013) and its latest extension RotatE (Sun et al. 2019), OTE (Tang et al.) (2020) and ROTH (Chami et al. 22200) (2) semantic matching based mod- els: ComplEx (Trouillon et al. 2016). QuatE (Zhang et al.) 2019), CoKE (Wang et al.] 2019b),
ConvE (Dettmers et al.. (018)), DistMult (Yang al.] 2015) and TuckER (Balazevic et al. 2019
(3) GNN-based models: R-GCN (Schlichtkrull et al. 2018), SACN (Shang et al. 2019 9 and
A2N (Bansal al.] 2019).
Training procedure. We use the standard training procedure used in previous KG embedding mod- els (Balazevic et al. 2019 Dettmers et al. 2018) (Appendix for details). We follow an encoder- decoder framework: The encoder applies the proposed MAGNA model to compute the entity em- beddings. The decoder then makes link prediction given the embeddings, and existing decoders in prior models can be applied. To show the power of MAGNA, we employ the DistMult decoder (Yang ct al. 2015), a simple decoder without extra parameters.
Evaluation. We use the standard split for the benchmarks, and the standard testing procedure of predicting tail (head) entity given the head (tail) entity and relation type. We exactly follow the evaluation used by all previous works, namely the Mean Reciprocal Rank (MRR), Mean Rank (MR), and hit rate at K (H@ K). See Appendix for a detailed description of this standard setup.
Results. MAGNA achieves new ofte-of-the--e art in knowledge graph completion on all four met- rics (Table 33.. MAGNA compares favourably to both the most recent shallow embedding meth- ods (QuatEE, and deep embedding methods (SACN). Note that with the same decoder (DistMult), MAGNA using its own embeddings achieves drastic improvements over using the corresponding DistMult embeddings.
4.3 MAGNA MODEL ANALYSIS
Here we present (1) the spectral analysis results, (2) effect of the hyper-parameter on MAGNA performance, and (3) attention distribution analysis show the strengths of MAGNA.
7

---

Under review as a conference paper at ICLR 2021
Spectral Analysis: Why MAGNA works for node classification? We compute the eigenvalues of the graph Laplacian of the attention matrix A, X7 and compare to that of the diffused matrix A, X Figure (a) shows the ratio X / on the Cora dataset. Low eigenvalues corresponding to large- scale structure in the graph are amplified (up to factor of 8), while high eigenvalues corresponding to cigenvectors with noisy information are suppressed (Kliepera et al. 2019b).
MAGNA Model Depth. Here we conduct experiments by varying the number of GCN, GAT and our MAGNA layers to be 3, 6, 12, 18 and 24 for node classification on Cora. Results in Figure (b) show that both deep GCN and deep GAT (even with residual connection) suffer from degrading performance, due to the over-smoothing problem (Li et al., 2018 Wang et al. (019a).. In contrast, the MAGNA model achieves consistent best results even with 18 layers, making deep MAGNA model robust and expressive. Notice that GAT with 18 layers cannot out-perform MAGNA with 3 layers and K=6 hops, although they have the same receptive field.
alpha 0.1
NAGNA
GAT
S0I
BC
alpha 0.2
alpha 0.3
Accurcc (%)
Ccuraa (6g)
Accuracy (5g)
alpha 0.4
54
Lapladan eigenvalue X
Depih
GAN
Hop Number
Figure 3: Analysis of MAGNA. (a) Influence of MAGNA on Laplacian eigenvalues. (b) Effect of
depth on performance. (c) Effect of hop number K on performance. (d) Effect of teleport probability a.
Effect of K and a. Figures 3 (c) and (d) report the effect of hop number K and teleport probability on model performance. We observe significant increase in performance when considering multi- hop neighbors information (K' > 1). However, increasing the hop number K has a diminishing returns, for K 2 6. Moreover, we find that the optimal K is correlated with the largest node average shortest path distance (e.g., 5.27 for Cora). This provides guideline for choosing the best K.
0.25. This is because small increases the low-pass effect (Figure 3 (a)). However, a being too small results in the model only focusing on large-scale graph structure and ignores too much figh-freuuency information.
We also observe that the accuracy drops significantly for larger
Attention Distribution. Last we also analyze the learned attention scores of GAT and MAGNA. We first define discrepancy metric
the attention matrix A for -U, Shanthamallu et al. 2020), where U; is the uniform distribution score for the node v4 A, gives measure of how much the learnt attention deviates from an uninformative uniform distribution. Large A; indicates more meaningful attention scores. Fig. 4 shows the distribution of the discrepancy metric of the atten- tion matrix of the 1st head w.r.t. the first layer of MAGNA and GAT. Observe that attention scores learned in MAGNA have much larger discrepancy. This shows that MAGNA is more powerful than GAT in distinguishing important and non-important nodes and assigns atten- tion scores accordingly.
node U3 as A,- degree(u;)
40
MAGNA
30
GAT
20
#
10
0.0
0.2
0.4
Discrepancy metric A
Figure 4: Attention weights on Cora dataset.
RELATED WORK
Our proposed MAGNA belongs to the family of Graph Neural Network (GNN) models (Battaglia jet al. 2018 Wu et al. 2020 Kipf & Welling 2016 Hamilton et al. 2017). while taking advantage of graph attention and diffusion techniques.
Graph Attention Neural Networks (GATs) generalize attention operation to graph data. GATs allow for assigning different importance to nodes of the same neighborhood at the feature aggre- gation step (Veličković et al.] 2018). Based on such framework, different aatention-based GNNs have been proposed, including GaAN (Zhang al. 2018), AGNN (Thekumparampil et al. 2018 GeniePath (Liu et al., 2019b). However, these models only consider direct neighbors for each layer of feature aggregation, and suffer from over-smoothing when they go deep (Wang al. 2019a).
8

---

Under review as a conference paper at ICLR 2021
Diffusion based Graph Neural Network. Recently Graph Diffusion Convolution (GDC) (Klicperal et al., 2019b a) proposes to aggregate information from larger (multi-hopp neighborhood at each layer. by sparsifying a generalized form of graph diffusion. This idea was also explored in (Liao et al. 2019; Luan et al. 2019) Xhonneux et al. 2019 Klicpera et al. 2019a) for multi-scale deep Graph Convolutional Networks. However, these methods do not incorporate attention mechanisms which proves to have a significant gain in model performance, and do not make use of edge em- beddings (e.g., Knowledge graph) (Klicpera al. 2019b). Our approach defines novel multi-hop context-dependent self eelf-attention GNN which resolves the over-smoothing issue of GAT architec- tures (Wang et al., 2019a). EdgeNets (Isufi et al.) 2020) also extends attention mechanism for multi-hop information aggregation, but it needs more parameters to compute the attention scores of multi-hop neighbors. In contrast, our method infers the attention scores of multi-hop neighbors based on the one-hop neighbor attention scores via graph diffusion, and thus not only more param- eter efficiency but show better spectral property.
CONCLUSION
We proposed Multi-hop Attention Graph Neural Network (MAGNA), which brings together bene- fits of graph attention and diffusion techniques in single layer through attention diffusion, layer normalization and deep aggregation. MAGNA enables context-dependent attention between any pair of nodes the graph in a single layer, enhances large-scale structural information, and learns more informative attention distribution. MAGNA improves over all state-of-the-art methods on the standard tasks of node classification and knowledge graph completion.
REFERENCES
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey E Hinton. Layer normalization. arXiv preprint vrXiv:1607.0644 06007004500 2016.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In ICLR, 2015.
Ivana Balazevic, Carl Allen, and Timothy Hospedales. Tucker: Tensor factorization for knowledge graph completion. In EMNLP, 2019.
Trapit Bansal, Da-Cheng Juan, Sujith Ravi, and Andrew McCallum. A2n: Attending to neighbors for knowledge graph inference. In ACL, 2019.
Peter Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanzhez-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: 1806.0/21,,
2018.
Antoine Bordes, Nicolas Usunier, Alberto Garcia-Duran, Jason Weston, and Oksana Yakhnenko. Translating embeddings for modeling multi-relational data. In NeurlPS, 2013.
Ines Chami, Adva Wolf, Da-Cheng Juan, Frederic Sala, Sujith Ravi, and Christopher Ré. Low- dimensional hyperbolic knowledge graph embeddings. In ACL, 2020.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NewrIPS, 2016.
Tim Dettmers, Pasquale Minervini, Pontus Stenetorp, and Sebastian Riedel. Convolutional 2d knowledge graph embeddings. In AAAI, 2018.
Jacob Devlin, Ming-Wes Wei Chang. Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In NAACL, 2019.
Hongyang Gao and Shuiwang Ji. Graph u-nets. In ICML, 2019.
Hongyang Gao, Zhengyang Wang, and Shuiwang Ji. Lcrge-scale learnable graph convolutional networks. In KDD, 2018.

---

Under review as a conference paper at ICLR 2021
Aditya Grover and Jure Leskovee. node2vec: Scalable feature learnigg for networks. In KDD, 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In NeurIPS, 2017.
Elvin Isufi, Fernando Gama, and Alejandro Ribeiro. Edgenets: Edge varying graph neural networks. arXiv preprint oXiv:2001.07620, 2020.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In ICLR, 2016.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Predict then propagate:
Graph neural networks meet personalized pagerank. In ICLR, 2019a.
Johannes Klicpera, Stefan Weißenberger, and Stephan Günnemann. Diffusion improves graph learn- ing. In NeurIPS, 2019b.
Zhenzhong Lan, Mingda Chen, Sehastian Goodman, Kevin Gimpel, Piyush Sharma, and Radu Sori- cut. Albert: A lite bert for self supervied learning of language representations. In ICLR, 2019.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In AAAI, 2018.
Renjie Liao, Zhizhen Zhao, Raquel Urtasun, and Richard S. Zemel. Lanczosnet: Multi-scale deep graph convolutional networks. In ICLR, 2019.
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. Roberta: A robustly optimized bert pretraining approach. arXiv preprint arXiv: 1907. J 1692, 2019a.
Ziqi Liu, Chaochao Chen, Longfei Li, Jun Zhou, Xiaolong Li, Le Song, and Yuan Qi. Geniepath: Graph neural networks with adaptive receptive paths. In AAAI, 2019b.
Peter Lofgren. Efficient Algorithms for Personalized PageRank. PhD thesis, Stanford University, 2015.
Sitao Luan, Mingde Zhao, Xiao-Wen Chang, and Doina Precup. Break the ceiling: Stronger multi- scale deep graph convolutional networks. In NeurlPS, 2019.
Andrew Ng, Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. In NeurlPS, 2002.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In ICLR, 2020.
Allan Pinkus. Approximation theory of the mip model in neural networks. Acta numerica, 8(1): 143-195, 1999.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, and Ilya Sutskever. Language models are unsupervised multitask learners. OpenAl Blog, 2019.
Aliaksei Sandryhaila and José MF Moura. Discrete signal processing graphs: Graph fourier transform. In ICASSP. 2013.
Michael Schlichtkrull, Thomas N Kipf, Peter Bloem, Rianne Van Den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In ESWC, 2018.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, pp. 93-106, 2008.
Chao Shang, Yun Tang. Jing Huang. Jinbo Bi. Xiaodong He, and Bowen Zhou. End-to-end structure- aware convolutional networks for knowledge base completion. In AAAI, 2019.
Uday Shankar Shanthamallu, Jayaraman Thiagarajan, and Andreas Spanias. A regularized atten- tion mechanism for graph attention networks. In ICASSP, 2020.
10

---

Under review as a conference paper at ICLR 2021
Zhiqing Sun, Zhi-Hong Deng, Jian- Yun Nie, and Jian Tang. Rotate: Knowledge graph embedding by relational rotation in complex space. In ICLR, 2019.
Yun Tang, Jing Huang, Guangtao Wang, Xiaodong He, and Bowen Zhou. Orthogonal relation transforms with graph context modeling for knowledge graph embedding. In ACL, 2020.
Kiran K Thekumparampil, Chong Wang. Sewoong Oh, and Li-Jia Li. Attention-based graph neural network for supervisee learning. arXiv preprint
2018.
Kristina Toutanova and Danqi Chen. Observed versus latent features for knowledge base and text inference. In CVSC-WS, WS, 2015.
Théo Trouillon, Johannes Welbl, Sebastian Riedel, Éric Gaussier, and Guillaume Bouchard. Com- plex embeddings for simple link prediction. In /CML,, 2016.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In NeurlPS, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Guangtao Wang, Rex Ying, Jing Huang, and Jure Leskovec. Improving graph attention networks with large margin- based constraints. In NeurlPS-WS. 2019a.
Quan Wang. Pingping Huang, Haifeng Wang, Songtai Dai, Wenbin Jiang, Jing Liu, Yajuan Lyu, Yong Zhu, and Hua Wu. Coke: Contextualized knowledge graph embedding. arXiv preprint 19/102 2019b.
Marinka Zitnik Yuxiao Dong Hongyu Ren Bowen Liu Michele Catasta Jure Leskovec Weihua Hu, Matthias Fey. Open graph benchmark: Datasets for machine learning graphs. arXiv preprint arXiv:2005.00687, 2020.
Zonghan Wu, Shirui Pan, Fengwen Chen, Guodong Long, Chengqi Zhang, and Philip S Yu. A comprehensive survey graph neural networks. IEEE Trans Neural Netw Learn Syst, 2020.
Louis-Pascal C. Xhonneux, Meng Qu, and Jian Tang. Continuous graph neural networks. arXiv preprint ar arXiv:191.0005900 2019.
Ruibin Xiong, Yunchang Yang, Di Hc, Kai Zheng, Shuxin Zheng, Chen Xing. Huishuai Zhang, Yanyan Lan, Liwei Wang, and Tie-Ya Yan Liu. On layer normalization in the transformer architec- ture. In ICML, 2020.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In ICML, 2018.
Bishan Yang. Wen-tau Yih, Xiaodong He, Jianfeng Gao, and Li Deng. Embedding entities and relations for learning and inference in knowledge bases. In ICLR, 2015.
Jiani Zhang, Xingjian Shi, Junyuan Xie, Hao Ma, Irwin King, and Din Yeung. Gaan: Gated attention networks for learning on large and spatiotemporal graphs. arXiv preprint arXiv:1803.07294, 2018
Shuai Zhang, Yi Tay, Lina Yao, and Qi Liu. Quaternion knowledge graph embedding. In NeurlPS, 2019.
Chenyi Zhuang and Qiang Ma. Dual graph convolutional networks for graph- based semi-supervised classification. In WWW, 2018.
11


Reviews:
[{"review_id": "sRe4AiG3c6l", "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": "Summary:\n\n     Conventional Graph Neural Networks (GNNs) learn node representations that encode information from multiple hops away by iteratively aggregating information through their immediate neighbors. Self-Attention modules have been adopted to GNNs to selectively aggregate information coming through the immediate neighbors at different propagation stages. However, current self-attention mechanisms are limited to only attend over the nodes' immediate neighbors and not directly over their neighbors that are multiple hops away. Here in this work, the authors intend to address this issue and propose a means to obtain attention scores over indirectly connected neighbors. \n\n    The message passing paradigm is commonly adopted in GNNs because directly computing the higher powers of an adjacency matrix is not scalable. The same scalability concern is present for this work, which tries to obtain attention scores for indirect neighbors directly. Thus in order to solve this issue, the authors propose to diffuse the learned attention scores from their 1-hop neighbors to neighbors that are multiple hops away, thereby providing a means to directly obtain attention scores over indirect neighbors that are reachable from the nodes. \n\n——\nPros:\n\n\tThe paper is well written.\n\tThe paper provides experimental results for both homogenous and multi-relational graphs.\n\n——\nConcerns:\n\t(i) Proposed methodology being more powerful than GAT is arguable:\n\n\tWhen the attention scores for indirectly connected neighbors are still computed based on the immediate neighbors' attention scores, it is not convincing enough to be argued as more powerful than GAT, which learns attention scores over contextualized immediate neighbors.  Also, the approximate realization of the model described in Eqn: 5 follows a message-passing style to propagate attention scores. Suppose it is to be argued that standard message-passing-based diffusion is not powerful enough to get a good immediate neighbor representation that encodes neighbors' information from far away. In that case, it is not immediately clear how a similar diffusion, when used for propagating attention scores from immediate neighbors to neighbors multiple hops away, will be more powerful. \n\n(ii) Experimental results are not conclusive: \n\n\t\t(a) Effect of Layer-Norm and FeedForward \n\t\t\tOne of the important ablation model that is missing is MAGNA without feed-forward and layer-Norm components. Currently, it is not clear how much of an improvement is achieved because of these standard two components.  \n\t\t(b) Disentangling the effect of page-rank from the attention diffusion\n\t\t\tSince Diffusion-GCN is also based on Page-Rank based propagation, it would be helpful to compare with the Diffusion-GCN model with these two components appended to them, along with residual connection if already not present. This would help us clarify how much of the gain in performance depends on the page-rank-based propagation compared to the attention propagation. The teleport probability of Diffusion-GCN should also be similarly experimented with and the analysis should be compared with the plots in Figure 3. \n\n \t\t(c) Comparable or not significant gains achieved in Node classification tasks. \n\t\t\tIt is amendable that the authors have reported results for both single-relational and multi-relational graphs. However, the node classification results are not significantly better than GAT or Diffusion GCN on the reported smaller datasets (Table 1) with a single train/val/test split. And on OGB Arxiv dataset, GAT and Diffusion GCN numbers are not reported. Hence, it would be helpful to analyze additional datasets.\n  \t\t\t\t\tIgnoring the benefits of LayerNorm that the MAGNA can leverage, comparing its No-Feed-Fwd version with Diffusion-GCN, which is also based on a page-rank formulation, MAGNA gain ~1% improvement on Cora and Pubmed dataset whereas it falls behind by ~1% in Citeseer. \n\n\t\t(d) Disentangling the effect of Multi-scale diffusion from attention diffusion \n\t\t\tSince MAGNA uses a multi-scale diffusion at each layer, a comparison with a similar non-attentive multi-scale diffusion model like Lanczosnet that is also referred in the paper would be helpful to disentangle\tand understand the importance of the attention mechanism. \n\n\t\t(e) KG Completion: Missing baselines and model variations \n \n \t\t- Missing comparison with Self-attention (GAT) based knowledge graph embedding model, KBGAT. \n\t\t  Nathani et al., Learning Attention-based Embeddings for Relation Prediction in Knowledge Graphs, ACL 2019\n\t\t- Additionally, it would be helpful to have similar model ablation studies of MAGNA model as in Table 1 for KG Completion. \n\t\n\t\t(f) Depth Analysis:\n\t\t\t  Diffusion-GCN comparison missing. The performance stabilization over GAT might be arising because of the restart probability. MAGNA only has weights associated with 3 layers, unlike with GAT, which has weights for every propagation step. \n\t\t\t\n\n——\nQuestions during rebuttal:\n\n\t- Kindly clarify concern (i)\n\t- Check experimental concerns above for additional ablation and baseline variants that is required to disentangle and appreciate the usefulness of the primary contribution, the attention diffusion component. \n\t- Comparison with the KB-GAT model that is based on GAT for KG completion task, will strengthen the results on KG completion task.\n\t- Comparison with GAT and Diffusion-GCN with LayerNorm and FeedFwd components on multiple train/test/val splits for smaller datasets or for other datasets from OGB will strengthen the results for node classification. \n\n--- Post-rebuttal\nI thank the authors for responding to all the questions and getting back with additional experiment results.\n\nMajor concern: While I understand the motivation and how having attention scores over nodes multiple hops away can be powerful, I'm still not convinced with the approximate realization. It is not clear how diffusing attention defined over 1-hop neighbors is powerful over attention methods defined over immediate neighbors that contain k-hop information aggregated from diffusion.\n\nAlso, the performance drop and overfitting issue with GAT or diffusion-GCN can be combated similarly by sharing weights across GNN layers and also using a higher-order diffusion matrix at each GNN layer.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "XZh2oE3QW6y", "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": "The authors propose a novel attention-based GNN called MAGNA. The main contribution consists in considerably increasing the receptive field by considering a multi-hop neighborhood instead of the standard one hop. The technical challenge consists in obtaining attention scores for all relevant nodes in an efficient way. MAGNA solves this by using a diffusion-based technique combined with a geometric distribution. The authors show that the latter further allows for approximations, and also give interesting theoretical insights (e.g., show a relation to page rank). \n\nThe paper is overall well written, related work is considered adequately, the idea is interesting, and the results are convincing. The evaluation comprises several different datasets, domains, tasks, and competitive baselines. The ablation studies give interesting insights in the effects of different parameter choices. Altogether, I suggest to accept the paper.\n\n----------------------------------------------\nSmaller comments:\n- p.3: \"degenerate categorical distribution with 1 category\": I think this should be explained.\n- p.3: \"effectively creating attention shortcuts between nodes that are not connected (Figure 1).\": I assume you mean \"directly connected\" since the whole approach seems to consider only connected nodes?\n- p.4: \"as well as good model generalization.\": How does the diffusion process ensure good model generalization?\n- p.5: Footnote 2: ??\n- 4.2. Baselines: The paragraph mentions few what is not in the table, so maybe you can just drop it and use the space for more descriptions.\n- 4.2. Results.: The last sentence is unclear to me.\n\n----------------------------------------------\nUpdate after Rebuttal: I have read the other reviews and authors' responses. \n\nWhile I do think the novelty of the contribution is sufficient, given that  the paper referenced in another review has not been peer-reviewed yet, the new ablation results in Table 1 show that the paper's contribution is not outstanding. I adjusted my score.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "NeieF-6Ywo", "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": "==== Summary ====\nThis paper proposes MAGNA, a multi-hop self-attention mechanism for attention based graph neural networks. The proposed method increases the receptive field at each layer, requiring less layers to achieve a large receptive field. Also, with the proposed method the attention coefficient between two nodes is not just a function of the two nodes but also of their neighbourhood. The proposed MAGNA method is an extension of GAT networks that introduces a diffusion step on the computed attention coefficients, following a similar approach (Diffusion-GCNs) that has been used for GCNs.\n\n==== Pros: ====\n* The proposed method extends GAT layers to have multi-hop receptive fields without increasing the number of model parameters.\n* Even though the two main building blocks (Graph Attention and Graph Diffusion) of the paper are not novel, their combination is novel and it achieves state of the art empirical results in two different tasks.\n* The evaluation of MAGNA and comparison with previous approaches is well done, using two different tasks and the standard benchmarks for those tasks.\n* The paper is well written.\n\n\n#### Cons:\n* The proposed method MAGNA seems to be similar to the APPNP method proposed in [Klicpera 2019a] that also uses diffusion to increase the neighbourhood around each node in a GCN layer (without attention). However the two models are not compared and the later is not included in the Related Work section, even though it is cited previously.\n* The ablation study is a good idea, but it isn’t very clear how it is done.\n* The motivation behind including layer normalization and deep aggregation or why they are useful isn’t entirely clear.\n\n#### Questions:\n1) MAGNA has 3 main differences compared to GAT: layer normalization, diffusion and deep aggregation. In the ablation study in Table 1, which components are removed for each row? When it says “No LayerNorm”, does that mean that it uses diffusion and deep aggregation but no LayerNorm? If so, is there an ablation test where MAGNA just uses the diffusion step but without the other two components? That would be very relevant, since it would be like a GAT network with a larger receptive field at each layer, and would show how much improvement the increased receptive field brings without the other components.\n2) Since the paper puts a lot of emphasis in the multi-hop capability of MAGNA, and related to my previous question, it would be quite interesting to compare MAGNA against a GAT network that has a larger receptive field, for example by using a multi-hop adjacency matrix computed with the diffusion process from [Klicpera 2019b] (called sparsified matrix in that paper) instead of the 1-hop adjacency matrix used in the original GAT paper. With this comparison we could see the benefit of using the diffusion of the attention values instead of just increasing the receptive field of GAT by allowing each node to pay attention to nodes up to K hopes away.\n3) In section 4.1 the authors say that “Since MAGNA computes many attention values, layer normalization is crucial in ensuring training stability”. Doesn’t MAGNA compute the same number of attention values as GAT and it then diffuses them? Any ideas why layer normalization is crucial when diffusion is used but not without it? (as seen in the ablation study, when MAGNA doesn’t use diffusion the scores are on par with GAT, which suggests that layer normalization is only useful with diffusion).\n\n#### Minor comments\nIn the Edge Attention Computation paragraph in section 2.2, the authors say “To compute representation of” and probably meant “To compute the representation of”.\n\n$W_o$ in Equation 6 is not explained in the text.\n\nAcross the paper and in the caption for Figure 2, the text talks about MAGNA blocks, but the text in the Figure says “DAGN” Block. Is that the same? Same in the 2nd plot in Figure 3, it says DAGN, should it be MAGNA?\n\n#### Reasons for score\nThe authors give a solid justification for using a diffusion process to increase the receptive field of GNNs with attention, and along with previous papers on graph diffusion provide a good motivation and explanation of their method. Also, the experiments section shows that MAGNA achieves state of the art results in two different tasks. Because of these reasons, I vote for accept. My only concern is that some components don’t have a clear justification besides the empirical improvement in performance (layer normalization and deep aggregation) and that comparisons with other techniques (APPNP and GAT with k-hop adjacency matrix) would make the experiments section stronger.\n\n----- Post Rebuttal Update -----\nAfter the author's rebuttal and the discussion with other reviewers, I have decided to lower my score to 6.\nThe reason is that during the review and discussion process it was pointed out that the main contribution of the paper is more incremental than novel, as both multi-hop GATs and diffusion for GNNs have been explored before in similar ways. Additionally, even though the authors provide some theoretical grounding for their work, some of it is a bit disconnected from the rest of the paper, like the relation with PageRank introduced in section 3.2, which is not referenced or discussed in any other section.\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "CdS_VzRVA3v", "reviewer": "AnonReviewer2", "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": "Summary:\n\nThis paper mainly proposes to learn attention-based edge coefficients by incorporating information from farther away nodes by means of their shortest path (powers of the adjacency matrix). Furthermore, the authors show the spectral properties of the proposed algorithm and its equivalence to personalized page rank.\n\nStrong points:\n\nThe numerical experiments show slight improvement.\n\nThe spectral analysis is potentially interesting.\n\nWeak points:\n\nThe multi-hop attention network has been done before (see below). The novelty thus resides only in the spectral analysis and the page rank equivalence.\n\nRecommendation:\n\nThe paper is ok, but I do not consider it to have enough novelty to be considered for publication in ICLR.\n\nMajor comment:\n\n1) Assuming there is only a scalar assigned to each edge (i.e. \\mathcal{R} = \\mathbb{R}), then (1),(3),(4) are a particular case of (39)-(41) in Isufi et al, 2020, where A_{k} = alpha I for k<K and A_{K} = H (the H matrix in eq. 4). This renders (1), (3), (4)'s only novelty to be the potential for vector-valued edge weights. Please elaborate on the comparison with Isufi et al, 2020 in the paper.\n\nE. Isufi, F. Gama, and A. Ribeiro, \"EdgeNets: Edge Varying Graph Neural Networks,\" arXiv:2001.07620v2 [cs.LG], 12 March 2020. [Online]. Available: http://arxiv.org/abs/2001.07620\n\n2) Why is R in N_r x d_r? Shouldn't it have N_e as a dimension? So if we have 5 edge types (like in the QM9 molecule data set, with 4 bond types and an extra no-bond type, encoded as one hot vectors), that means that R has only 5 rows? And what does the number of columns represent? It's just that X is very straightforward: number of nodes x number of channels. But R is hard to interpret.\n\n3) The LHS of eq. (2) shows dependence with i, j and l. The RHS shows dependence with i, j, l, and also k. Where does k appear in the matrix indexing? Is there a different attention score matrix for each value of k?\n\n4) I believe the paper would benefit for an increased elaboration on the usefulness of proposition 2, since this is the main novelty. Let us say we are given a graph, and we choose to describe that graph by means of some matrix (either the adjacency or the Laplacian). The choice of graph description fixes the frequency interpretation of the graph. Different matrix choices lead to different frequency interpretations. Now, the attention mechanism changes this matrix description by learning a new matrix description. However, this new, learned, matrix description will most likely not even share the same eigenvectors as the original matrix description of the graph. So how do we know that the filters learned are actually low-pass filters in the graph? They maybe low-pass filters in the learned graph by attention mechanisms, but they may not be in the actual graph that was given by the problem. Please, clarify what's the interpretation of Proposition 2, since matrices A and \\mathcal{A} are being learned from data.\n\nMinor comments:\n\nDue to Cayley-Hamilton theorem, there is no need for (3) to go to infinity. It suffices for it to go to N_n-1.\n\nReference to Sandryhaila and Moura, 2013 is missing at the beginning of Section 3 when referring to discrete signal processing on graphs.\n\nA. Sandryhaila and J. M. F. Moura, \"Discrete signal processing on graphs,\" IEEE Trans. Signal Process., vol. 61, no. 7, pp. 1644–1656, 1 Apr. 2013.\n\nFootnote 2 on page 5 is missing a proposition reference.\n\n--- UPDATED SCORE ---\n\nFirst of all, I would like to thank the authors for carefully addressing my comments.\n\nIn light of the authors' response, and after a thorough and careful discussion with the other reviewers, I have decided to update my score to 5 (five).\n\nIn summary, I appreciate the authors' effort to signal the differences between their work and Elvin et al. While I agree with these, I still think this is only an incremental contribution. For further reference, after carefully discussing the paper with other reviewers, these two published papers were also pointed out where multi-hop attention is addressed. Namely,\nhttps://openreview.net/forum?id=rkKvBAiiz\nhttps://ieeexplore.ieee.org/document/8683050\nI apologize for not finding these papers in my first round of reviews, but it does not really alter my evaluation of the paper.\n\nI think that the most novel contribution is on the spectral analysis. But this is only stated, with no real insights developed, and not emphasized enough. More insight on this would definitely bring a novelty. More specifically, novelties that would have made the paper more interesting: (i) a different way of computing the attention coefficients, that would be more parameter efficient (as opposed to eq. (1)) in the paper, (ii) actual useful insights into what the frequency response of the learned filters look like in the attention matrix as opposed to the given support matrix of the graph, (iii) a comparison between the spectral basis of the learned attention matrix as compared to the support matrix.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: 
This paper has been reviewed by four knowledgeable referees. Two of them slightly leaned towards acceptance, whereas the other two suggested rejection. The main issues raised by the reviewers were (1) limited novelty [R1,R2], (2) missing baselines and ablations [R1,R3], (3) limited insights on the spectral analysis [R2], and (4) missing motivation behind modeling choices [R1,R3]. The rebuttal included a number of experiments requested by the reviewers (e.g. ablation with diffusion only [R1,R3], extended Diffusion GCN [R1], APPNP baseline [R3]), and adequately motivated some of the modeling choices. 

The central question of the reviewers' discussion was whether the contribution of this paper was significant enough or too incremental. The discussion emphasized relevant literature which already considers multi-hop attention (e.g. https://openreview.net/forum?id=rkKvBAiiz [Cucurull et al.], https://ieeexplore.ieee.org/document/8683050 [Feng et al.], https://arxiv.org/abs/2001.07620 [Isufi et al.]), and which should have served as baseline. In particular, the experiment suggested by R3 was in line with some of these previous works, which consider "a multi-hop adjacency matrix " as a way to increase the GAT's receptive field. This was as opposed to preserving the 1-hop adjacency matrix used in the original GAT and stacking multiple layers to enlarge the receptive field, which as noted by the authors, may result in over-smoothed node features. The reviewers acknowledged that there is indeed as slight difference between the formulation proposed in the paper and the one in e.g. [Cucurull et al.]. The difference consists in calculating attention and then computing the powers with a decay factor vs. increasing the receptive field first by using powers of the adjacency matrix and then computing attention. Still, the multi-hop GAT baseline of [Cucurull et al.] could be extended to use a multi-hop adjacency matrix computed with the diffusion process from [Klicpera 2019], as suggested by R3. In light of these works and the above-mentioned missing baselines, the reviewers agreed that the contribution may be viewed as rather incremental (combining multi-hop graph attention with graph diffusion). The discussion also highlighted the potential of the presented spectral analysis, which could be strengthened by developing new insights in order to become a stronger contribution (see R2's suggestions). 

To sum up, this was a very discussed paper, where the reviewers ultimately reached a consensus to reject, with no strong opposition. I agree with the reviewers' assessment and therefore must reject. I encourage the authors to follow the reviewers' suggestions and consider the multi-hop baselines as well as the hints provided by the reviewers about the spectral analysis to strengthen their work.

Decision: Reject