Memory Augmented Design of Graph Neural Networks
Authors: Tao Xiong
Liang Zhu
Ruofan Wu
Yuan Qi
Venue:  (2021)

Abstract: The expressive power of graph neural networks (GNN) has drawn much interest recently. Most existent work focused on measuring the expressiveness of GNN through the task of distinguishing between graphs. In this paper, we inspect the representation limits of locally unordered messaging passing (LUMP) GNN architecture through the lens of \emph{node classification}. For GNNs based on permutation invariant local aggregators, we characterize graph-theoretic conditions under which such GNNs fail to discriminate simple instances, regardless of underlying architecture or network depth. To overcome this limitation, we propose a novel framework to augment GNNs with global graph information called \emph{memory augmentation}. Specifically, we allow every node in the original graph to interact with a group of memory nodes. For each node, information from all the other nodes in the graph can be gleaned through the relay of the memory nodes. For proper backbone architectures like GAT and GCN, memory augmented GNNs are theoretically shown to be more expressive than LUMP GNNs. Empirical evaluations demonstrate the significant improvement of memory augmentation. In particular, memory augmented GAT and GCN are shown to either outperform or closely match state-of-the-art performance across various benchmark datasets. 

Under review as a conference paper at ICLR 2021
MEMORY-AUGMENTED DESIGN OF GRAPH NEURAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
The expressive power of graph neural networks (GNN) has drawn much interest recently. Most existent work focused on measuring the expressiveness GNN through the task of distinguishing between graphs. In this paper, we inspect the representation limits of locally unordered messaging passing (LUMP) GNN archi- tecture through the lens of node classification. For GNNs based on permutation invariant local aggregators, we characterize graph-theoreti, conditions under which such GNNs fail to discriminate simple instances, regardless of underlying architec- ture or network depth. To overcome this limitation, we propose a novel framework augment GNNs with global graph information called memory augmentation. Specifically, we allow every node in the original graph to interact with a group of memory nodes. For each node, information from all the other nodes in the graph can be gleaned through the relay of the memory nodes. For proper backbone archi- tectures like GAT and GCN, memory augmented GNNs are theoretically shown be more expressive than LUMP GNNs. Empirical evaluations demonstrate the sig- nificant improvement of memory augmentation. particular, memory augmented GAT and GCN are shown to either outperform or closely match state-of-the-an performance across various benchmark datasets.
INTRODUCTION
Graph neural networks (GNN) are powerful tool for learning with graph-sttr graph-structured data, and
has achieved great success on problems like node classification (Kipf & Welling 2016), graph
classification (Duvenaud al. 2015) and link prediction (Grover & 20010 GNNs typically follow a recursive neighborhood aggregation (or message passing) scheme (Xu et al.) 2019) such that within each aggregation step, each node collects information from its neighborhood (usually feature vectors), then apply aggregation and combination mechanism to compute its new feature vector. Typically, GNN architectures differ in their design of aggregation and combination mechanisms. Popular architectures like GCN (Kipf & Welling 2016), GraphSAGE (Hamilton al. 2017). and GAT (Veličković et al. 2018) fall into this paradigm.
Despite their empirical success, there are couple of limitations of GNNs that update node features only based on local information. One important issue is their limited expressive power. In the graph classification setting (Xu et al. (2019), it was shown that message passing neural networks as powerful as Weisfeiler Lehman graph isomorphism tests. A more recent line of work has suggested using variants of message passing scheme that incorporates the layout of local neighborhoods (Sato
at most
et al.
2019 Klicpera et al. 2020) or spatial information of the graph (You et al. 2019).
Another problem is due the phenomenon that the performance GNN does not improve, or even degrades when layer size increases (Kipf & Welling 2016 Xu et al.) 2018 Li et al.) 2018 Oono & Suzuki 2020), known as the problem of over-smoothing that makes extending the receptive path of message passing GNNs a difficult task. Many successful GNN architectures are based on stacking a few number of layers like or (Kipf & Welling 2016), which could be viewed as an implicit inductive bias that node labels are determined up neighborhoods that are few hops away. However this assumption may not hold for many real-world data -otaaafo&& example, structurally similar nodes may offer strong predictive power for very distant node pairs (Donnat al. 2018). Several techniques are proposed for aggregating node information from a wider range (Xu et al. 2018 Klicpera et al. 2019a b).

---

Under review as a conference paper at ICLR 2021
In this paper, we investigate the expressive power of GNNs through the task of node classification. We characterize cases where GNNs that builds on LUMP protocol fail, regardless of underlying implementation aggregation range. We then propose novel architecture that aggregates infor- mation beyond the local neighborhood. Through making use of global feature information, we can distinguish a wide range of cases that LUMP type GNNs inherently fail. Our main contributions summarized as follows:
We discuss the expressive power of GNNs for node classification tasks under the premise that node labels are not solcly determined by first-order neighborhood information, and show an indistinguishable scenario where LUMP algorithms fail to discriminate nodes in structurally different graphs even infinite rounds of message passing is performed.
We develop novel framework that extends GNN with global graph information called memory augmentation, motivated by memory networks (Graves et al. [2014) Wesston et al. 2014). With proper choice of backbone architectures like GAT or GCN, the augmented architectures are provably more expressive than LUMP type GNNs in that they discriminate a wide range of cases that LUMP type GNNs fail with a compact architecture of two layers.
We derive two representative memory augmented architectures, MemGAT and MemGCN, and evaluate their performance on standard datasets. Empirical results show that the memory augmented architectures significantly improves their corresponding backbone architectures across all tasks, either outperforming or closely matching state-of- of-thee-rt performance.
2 REPRESENTATION LIMITS OF LOCALLY UNORDERED MESSAGE PASSING
In this paper we consider the task of node classification over an undirected graph G (V, E) with node set V and edge set E. Let N = [V] be the number of nodes and A, D be its associated adjacency matrix and degree matrix. For each node v V, let Nr {u uu E EE be its neighborhood set and X, E X' C Fd be its associating feature. Each node E V is associated with label Y,. Node classification algorithms make predictions of Y, based on the information given by G and the node feature matrix X. In this paper we will be interested in situations where node labels are not determined solely by their first order neighborhood information. i.e., IP (Y.|G. X)= # P (Y, [X,,, X., u E A..), Vu E V. For a collection of elements C' that are not necessarily distinct, we use {C} to denote its set representation and {C} to denote its multiset representation. For each E {C}. let re(c) be the multiplicity of c in {C}. A popular tool for encoding higher order graph information is to utilize the locally unordered message passing (LUMP) protocol (Garg et al. 2020)
is updated using an aggregation and to build GNNs. For node u, its (hidden) representation h1
combine strategy:
h COMBINE (6( (((-"),AGG (f (Ag-") "u
(1)
The protocol is unordered in the sense that no spatial information (like the relative orientation of neighbors) is used throughout the message passing procedure, and the aggregator AGG is often chosen as a permutation invariant function. After k rounds of message passing, each node will have feature vector that encodes the information of its height ls rooted subtree. Aggregation strategies that extend to arbitrary node were suggested in pioneering works of GNNs (Scarselli et al., (009) that use a learnable, contractive aggregator, and perform infinite rounds of message passing till convergence.
Next we discuss the expressive power of the above mentioned mechanisms. Let G(v) be the subgraph of G that contains v. V. and their associated edges. We consider two graphs, G = (V, E) and G (V', , E"), with corresponding feature matrices X and X'.
Definition 1. (Gross & Tucker 2001 A graph map f : + G' is called a local isomorphism if for every node E V. the restriction of f to G(v) is an isomorphism onto G(f(v)).
Local isomorphism could be understood two isomorphic graphs, the isomorphism map is also a local isomorphism but the converse is not true (see figure [. Next we use the notion of local isomorphism to help characterize the expressive power of GNNs in node classification context. We say graph G' is locally indistingnishable to graph G", if there exists a surjective local isomorphism ff from G to G', and if in addition the feature matrices are related X. = foy- The following theorem states a specific situation where LUMP type GNNs fail to distinguish between nodes in different graph contexts.
relaxed version of graph isomorphism. In particular, for
2

---

Under review as a conference paper at ICLR 2021
Theorem 1. If G is locally indistinguishabbe graph G' under map f. then under the LUMP for any v E V and E E..
protocol equation we have 1: = -
f(n) (
The proof will be given in appendix A.2
We
give pictorial illustration in figure with node
color indicating feature value. The local iso- morphism is constructed [(a1) f(a4)
b1. fa2) = {as) = b2, f(a3) f(as) = by.
Theorem implies that representations of nodes with same color remain identical for arbitrary rounds of LUMP. Hence for the node label as- signment la 1. lb, = 0, GNNs based on LUMP fail express this difference.
de
0
1
G
G
Remark 1. Figure contrived case that sel- dom happens in practice. Note that such cases correspond to the worst case under which infi- nite depth LUMP architecture fails. For a more realistic setup. we may consider relaxing the surjectivity requirement in the definition of local indistinguishable graphs: if two nodes from different graphs have their induced k--hop neighhorhood being isomorphic, it follows that any depth-k: LUMP architectures fail to distinguish these two nodes. Locally isomorphic subgraphs are frequently observed in chemistry and bioinformatics (Raymond & Willet 2002 Cao et al. (008). Although locally isomorphic subgraphs from globally distinct graphs may get discriminated using deep LUMP architectures,
Figure 1: Graph structures that LUMP GNNs fail discriminate in terms of node classification tasks. (with respect to the assignment annotated near the corresponding node)
non-trivial scale GNNs to deep architectures without losing expressivity due to the phenomenon of over- over-smoothing Xu et al. (2018).
3
OUR MODEL
3.1 MEMORY AUGMENTATION
Our model is constructed via augmenting backbone GNN whose updating rule could be written as a simplified version equation | the hidden representation in the /th layer satisfies ([+1). AGG,r h0 1 }). The aggregation function AGG is parameterized by g(t) We will assume
the set X' to be countable, then by (Xu et al. 2019 Lemma 4), the range of h denoted H(0 is also countable for any given parametenization and any layer I.
Augmentation Inspired by memory networks (Graves et al. 2014: Weston et al. 2014). the memory auxiliary M d
component is formulated as a collection of learnable objects corresponding to M nodes, called memory nodes. Let VM be the set of memory nodes. We define memory matrix m with row vector m, serving as the memory embedding of memory node e. We allow every node in the original graph interact with the memory component. In particular, augment the original graph G into a slightly larger graph G* = (V*, EE), where V* -V-VUU VUM and
Eaj. 1,
if V if V,j VM o VMijEV if VM
Eig
0,
so that each memory node is connected to every node in the original graph G. Performing message passing using the backbone architecture would thus allow every node in the original graph to aggregate information from both its neighbors and the memory component, while the memory component aggregates information from the whole graph:
Vu E V, (1-1 = AGG gG) (f (no,n mym })
Yu E VM, m (+1) AGG (fm), ()))
F illusstates how memory augmentation does "symmetry breaking" in locally indistinguishable graphs: although the height k rooted subtree remains identical for Ga and Gn for any k. starting
3

---

Under review as a conference paper at ICLR 2021
R6
ha
Figure 2: Illustration of memory augmentation applied to the two graphs in figure | G. (right). Both graphs are augmented with one memory node. Aggregation paths of and b are presented as two hop subtree structures, corresponding to two round message passing using the memory augmented attention mechanism. Memory connections original connections as solid lines. The figure implies that, although the local subtree structures rooted d1 and b identical, the message carried by the memory node distinguishes dj from b1, provided that the message passing is performed for more than one round.
G, (left) and
drawn dashed lines and
from the second layer, messages from the memory component would become distinct thus makes discrimination possible. More rigorously, we characterize conditions for the backbone architecture under which the memory augmented architecture achieves stronger expressive power:
Definition 2. We say two multisets {X} } and {X'} are distributionally equivalent if they share same underlying set, i.e. {X} = {X'). and the corresponding multiplicities are proportional each other: for Vx E {X}, Fx /xx = m, m E Z...
Note that distributional equivalence is well defined equivalence relation. We require the following condition on the backbone GNN:
[C1] The backbone GNN identifies bounded size multisets in X' up to distributional equivalence.
Using single memory node w, we have the following result:
Lemma 1. Under condition Ct, there exists vector my such that if the memory embedding is initialized with m..G for any graph G. then the following holds:
(0)
(i) For any 1 Z4, there exists parameter configuration 1.!)) such that the map AGG g is injective over all multisets that takes the form: { C m subset of X
}. where {C} is a bounded
(ii) For graph pairs (G.G') with {X} + {X'}, the updated memory representations after 1 (1)
(1)
round of message passing are different, i.e. W.G + m W.G"
then follows from (uu et al. 2019 Theorem 3) that memory augmentation enhances proper backbone architectures to achieve the strongest expressive power among LUMP GNNs. Lemma I suggests that as long as the overall network architecture contains more than one layer, starting from the second layer, nodes in the original graph would receive messages that contain some kind of aggregated global information that identifies the multiset feature representation of the original graph. This could be also viewed as a graph specific bias term that discriminates that message passing protocol from LUMP. As consequence, we have the following theorem for binary node labels:
Theorem 2. For locally indistinguishable gruphs (G,G") under map f. there exists a two layer memory augmented GNN with its backbone architecture satisfying condition C1 such that with proper memory initialization (i.e. the one in lemma 7), the final output h satisfies: if [X} # {X'}, then h, > 0.5 and h (() & 0.5 for any v V.
Theorem 2 suggests that memory augmentation helps to identify locally indistinguishable graphs with different multiset feature representations. The following corollary justifies using two most popular
4

---

Under review as a conference paper at ICLR 2021
GNN architecture as the backbone architecture for memory augmentations. We adopt the formulation in Xu et al. (2019):
Corollary 1. Both GAT and GCN satisfies condition C₁.
We defer all proofs appendix A.2 For an empirical verification, we conducted simple experiment corresponding to the setup in figure 1 We use categorical features (with cardinality of three) and compared memory augmented GAT with GAT. We use the reference GAT' architecture in (Veličković et a (208)) and augment it with one memory node. We use a learnable multi-layer perceptron as the nonlinear readout function for both models. Figure 3 shows the result. It could be seen from the figure that the training accuracy of GAT never exceeds 2/3, which is its theoretical limit in this example. While memory augmented GAT fits the data perfectly after sufficient rounds gradient updates, thereby verifies theoretical findings.
3.2 TWo CANONICAL DESIGNS: MEMGAT AND MEMGCN
Now derive two canonical architectures that enhances Two popular GNNs GAT (Veličković et al.) 2018) and GCN (Kipf & Welling. 2016). The resulting architectures are termed MemGAT and MemGCN. For both designs, we introduce several improvements the vanilla memory augmentation described in section to balance the contri- bution from the original graph and the memory component. We also make a discussion on architectures that may not benefits from memory augmentation, see appendix A.4 for details.
GAT MemGAT
training accuracy
0.8
0.6
0.4
MemGAT We enhance attention-based GNNs (Veličković et al., 2018) via using a modified attention mechanism. The attention weights are calculated as:
0.2
60
80
100
120
140
160
180
200
training step
Xaisy exp 1-A exp M
(0))
1
if EVV if fiiE, if E VM.jEV
Figure 3: Comparison of memory aug- mented GAT with GAT on synthesized data, performance measured in training accuracy, results for initial 50 gradient iterations are discarded
(1)
aij
(((1) exp
/Y
1/
1 (i=))
exp
(
if
(3)
where (1(0) E Rdi denotes the hidden feature of node and 8 (a"( (((")))))((())))))))))) (( with g()) (possibly) nonlinear function for the th layer. higeev edge weights the original graph, and À (0, 1) is a parameter that balances the contribution between information provided by the original neighbor and the memory component.
in the th layer with 1())) X,,
(!) 1, vl. We write separately (z hev, (Y,")) JyEV normalizing factors such that Σ, 0
the updating equation for hidden representations corresponding to nodes in the original graph and memory embeddings:
Vu V,
((+1)
Σ
a
Σ VEVM
( ( (m (1)
(READ)
kE
Vu E VM.
m. (1-1)
1
m. ()) + Σ
(WRITE)
jEV
Connections memory based network design The above equations interprets the memory com- ponent content addressing memory design in memory-based neural networks (Graves et al. 2014 Weston et al. 2014): For nodes the original graph, the aggregation step is interpreted as a reading step with selective focus over both its immediate neighbors and the memory obtained from the previous layer. Alternatively, for the memory nodes, aggregation operations are hence interpreted as writing step.
5

---

Under review as a conference paper at ICLR 2021
MemGCN The augmented GCN adopts similar design aspects MemGAT with balancing param- eter A. We adopt the GCN formulation in Dehmamy et al. (2019), by using edge weights fely hu.ev to characterize the aggregation scheme:
VVEV,
h ((+)) =
Vi (0 + E
+
1- M
Σ Wm! BEVM
JEN;
Vo E VM. my (1+1) mw (m ))
Σ JEV
w (0
M
where S are learnable weight matrices. We identify two canonical types GCN: Kipf Welling (0166) uses by /d/ ()d 1), and a slightly modified method of Hamilton et al. (0117) uses Vij = (/(d, 1).
Remark 2. Recently several variants of LUMP that take ordered information into account are proposed, among which CPCGNN (Sato et al. 2019) and DimeNet (Klicpera et al.) 2020) are based on modifications to the first-order message passing scheme, and are provably more expressive than LUMP rype GNNs (Garg et al. 2020). We give a detailed comparison of memory augmented GNN architectures with CPCGNN and DimeNet in appendix A.33 We found that regarding node classification, there's 's no dominating choice between these methods. And it would be of interest to extend the idea of memory augmentation to other kinds of message passing schemes. We leave this direction to fulure research.
4 OTHER RELATED WORK
The expressive power of GNNs has been extensively studied recently (Xu et al. 2019; Maron et al. 2019: Garg al. 2020 Sato et al.) 2020 Zhang & Xie 2020), with the majority of these works defining the expressive power of GNN with its ability to distinguish different graphs. (Xu et al.
2019) proposed the GIN model that is theoretically as powerful as the first order Weisfeiler Lehman (1-WL.) test and is thus the most powerful among LUMP GNNs. (Zhang & Xie 2020) suggests accounting for cardinality information for attention based GNNs. More powerful GNN architectures are then proposed via extending the message passing formulation: higher order GNNs or k-GNNs (Morris et al. 2019 Maron et al. 2019) operate on k- tuple of nodes and aggregate information from neighborhoods defined on k- tuples of nodes. While such kind of GNN variants could be shown to be as powerful as k- k- test, they are not directly applicable to node level tasks. Another line of work (Sato et al. 2019 Klicpera et al. (020) generalizes the LUMP protocol to allow nodes passing messages depending on their relative position their belonging neighborhoods. Such kind of variants also provably more powerful than LUMP GNNs and are applicable to node level tasks. See section for a more detailed comparison between our approach and these variants. Position aware GNN (PGNN) YYou et al.) 2019) is another class of powerful GNN variants that uses random anchor sets to break local structural symmetry, and integrates positional information into a modified message passing architecture, with inductive bias suitable for relational classification. rGIN (Sato et al.. 2020) pairs each node with a random feature, thereby breaks locally indistinguishable subgraphs. Our method different from previous approaches in that we exploit the information of entire graphs' node features, achievable with a minimal network depth of 2.
based neural networks date back to the 1990s (for example (Schmidhuber 1992)) ). Notable recent developments include Neural Turing Machine (Graves et al. 2014) and Memory Networks (Weston et al., 2014). Our memory augmentation mechanism could be viewed as a GNN implementa- tion of the design principle in (Weston et al. 2014). There has been a couple of works on GNNs that adopted memory-based design lately (Khasahmadi et al. 2020 Ma et al. 2019a), under different problem contexts.
5 EXPERIMENTS
In this section we evaluate the performance of memory augmented GNNs using two canonical architectures MemGAT and MemGCN. We also conduct an ablation study to decompose performance gains under different design aspects. We use four types of benchmark datasets, with their characteristic statistics summarized in appendix A.1

---

Under review as a conference paper at ICLR 2021
Citation networks Cora, Citeseer, and Pubmed are standard citation network benchmark datasets. For all the three datasets, graphs are constructed by treating documents as nodes and citation links as edges, the task is to classify academic papers into different subjects using the papers' bag-of-wordh representation as features
Actor co-occurrence networks This dataset is the actor-only induced subgraph of the film-director- actor-writer network. Where nodes correspond to actors, and an edge between two nodes denotes co-occurrence on the same Wikipedia page. Node features correspond to some keywords in the Wikipedia pages and labels are actors categories
Web networks We use Cornell, Texas, and Wisconsin dataset (Pei et al. 2020). where nodes and edges represent web pages and hyperlinks, respectively. The feature of each node is the bag-of-worde
representation of the corresponding page, and labels are categories web pages.
Protein-prosd proteen interaction (PPI) This is dataset containing 24 graphs, with each graph corre- sponding to a human tissue. (Hamilton et al. 2017). The task is to classify protein functions based on features containing positional gene sets, motil gene sets and immunological signatures. This setting inductive in that at test time, algorithms shall make prediction with respect to completely unseen graphs. We will present the details of the PPI experiment in appendix A.6
5.1 EXPERIMENTAI. SETUP
Architecture and parameters We mostly adopt parameters for backbone architectures from their original implementation, respectively GAT' (Veličković et al.) (008)) and GCN (Kipf & Welling 2016), detailed in [A. We applied entropy regularization (Grandvalet & Bengio (2005) with tuning
parameter 0.6 for Cora and Citeseer datasets and 0.1 for Pubmed dataset. We use the following truncated diffusion matrix (Klicpera et al. (201b) to generate edge weights:
K
S = S(0,K,))))
Σ 0
(4)
In our experiments we use two sets As: personalized page rank: 02 = a(1 - ai* with a 0.15
and heat kernel: 02- = the श with t = 5. We choose the transition matrix T to be either Arw
(D 1) I) or Asm (D + () + I) + 1)-1/3 We report the best performing combination for each experiment. We tune the number of random walk steps K E N. Note that for large K, the resulting matrix is approximation to the diffusion matrix (Klicpera al. 2019b).
For the memory component, we used À = 0.9, we choose the number of memory nodes to be the number of classes across all tasks, study of this hyperparameter is presented in appendix AA.3 Finally, we applied skip connection using the form proposed in Zhang & Meng 2019) to stabilize training. The detailed tuning strategies are listed in appendix I For a better understanding of performance gains corresponding to different modifications to the backbone architecture, we provide an ablation study on the citation datasets. For the rest of the datasets, we additionally report performances without using edge weights, which we termed MemGAT-NE and MemGCN-NE.
Baseline comparisons We compare MemGAT and MemGCN with their backbone architectures across all benchmarks. We also report two -tate-of-the-art models that are able to aggregate neigh- borhood information from distant nodes: APPNP (Kliepera et al., (009a) and GCNII (Chen et al.) 2020). For the citation networks, we additionally report GraphSage (Hamilton et al. 2017) with max-pooling aggregation and GIN (Xu et al. 2019) and GºNN (a et al. 2019b). For actor and wiki networks, we additionally report GEOM-GCN (Pei et al. 2020) with its best performing variant. Besides, we report the performance of two-layer MLP with 256 hidden units on these datasets, as was recently noted that MLP performs very well on actor and wiki networks (Zhu et al. 2020).
Evaluation strategy it reported in (Shchur al. 2018 that the performance of current state- oh-the-art graph neural networks are typically unstable with respect to different train/validation/tes: split of the dataset. Hence for fair comparison of algorithm performances, in addition to results the original, standard split, we provide extensive results over 10 random splits of Cora, Citeseer and Pubmed datasets.
5.2 RESULTS
We use accuracy for performance metrics across all the tasks. The results of our evaluation experi- ments are summarized in Tables I [nd We report training details in appendix A.T As shown in
7

---

Under review as a conference paper at ICLR 2021
Table 1: Summary of results (%mean %standard deviation test set accuracy) for the citation datasets, with 10 random train/validation/eess split of datasets as well as the standard split. We annotate the original paper where we take the results from aside the algorithm name
Algorithm
Cora
Citeseer
Pubmed
Random split
GCN (Shchur al.
2018
81.5 1.3
1.99
77.8 2.9
SraphSago(maxpp pool)
(Shchur
2018
76.6
2.3
76.1
GAT (Shchur et al.
2018
81.8 1.3
1.9
78.7
GIN (Klıppraa et al
20T9b)
73.96 - 0.46
61.09 + 0.58
72.38 + 0.63
APPNP (our run)
82.45 + 1.89
70.60 + 1.31
77.28 + 3.14
MemG.AT(ours)
83.94 + 1.04
74.07 1.1
79.18 2.11
MemGCNNours)
82.94 + 1.61
72.87 1.69
78.53 + 1.91
Standard split
GCN (Shchur et al.
2018
81.9
69.5
0.5
GraphSagelmaxpool
(Shchur al. 2018
77.4 1.0
6.00
7..6
GAT (Shchur et al.
2018
82.8
0.6
7.30
APPNP (our rum)
83.60 0.61
0.52
7..04
G'NN(GAT) (Ma et al.
2019h
82.9 0.3
0.3
0.44
G'NN(GNN) (M 2019h
82.2 + 0.3
74.5 0.3 73.4
7..4
GCNIT (Chen et al.
85.5
80.3
(emGATTours)
84.65 + 0.52
74.20 0.73
79.18 0.56
MemGCN(ours)
84.30 1: 0.53
75.12 1: 0.22
80.46 1 0.27
Table 2: Summary of results (&mean + Østaadardd deviation test set accuracy) for actor co-occurence and web network datasets, with 10 random train/validation/tes split of datasets. We annotate the original paper where we take the results from aside the algorithm name
Algorithm
Actor
Cornell
Texas
Wisconsin
GCN Pei et al.
2020
26.86
52.70
52.16
45.88
GAT (Pe el al.
2020)
28.45
54.32
58.38
49.41
APPNP
2020
31.31
73.51
65.41
69.02
GEOM-GCN (Pei
2020
31.63
60.81
67.57
64.12
GCNII (Chen al.
2020
NA
76.49
77.84
81.57
MLP (our run)
37.01 + 1.02
80.65 + 6.34
80.84 + 4.21
84.31 = 3.41
MemGAT(ours)
31.93 +: 1.69
70.37 1 7.57
72.08 1 8.02
73.80 - 5.05
MemGCN(ours)
36.95 + 0.95
81.92 1 6.00
82.19 5.199
84.96 1 3.59
MemGAT-NE(ome))
34.93 = 0.74
2.994
61.75
65.14 5.41
MemGCN-NB(oul)
36.44 0.53
80.76 + 0.99
82.76 2.14
83.35 1.12
8

---

Under review as a conference paper at ICLR 2021
Table 3: Summary of the ablation study results (%mean + %standard deviation test set accuracy) for the citation datasets over 100 trials. For MemGCN, we did not use skip connection on the citation datasets; for MemGAT, we did not incorporate edge weights on the pubmed dataset.
Model
MemGAT
MemGCN
Dataset
Cora
Citeseer
Pubmed
Cora
Citeseer
Pubmed
(I)
82.32 + 0.57
71.11 + 0.97
77.00 + 0.30
81.99 + 0.52
69.50 + 0.90
79.00 + 0.50
(II)
83.54 + 0.55
71.76 + 0.48
N/A 78.97 1.05 79.18 + 0.56
82.26 + 0.88
72.68 0.27
79.95 + 0.23
(III) 83.77 0.72
73.21 0.66
N/A
N/A
N/A 80.46 + 0.27
(IV)
84.65 1 0.52
74.20 + 0.73
84.30 1 0.53
75.12 0.22
table T MemGAT and MemGCN consistently outperforms GAT and GCN by significant margin and is competitive to current state-of-the aart algorithms for graph learning. In particular, on the web network datasets, MemGCN improves GCN with a relative accuracy gain of over 50% while using the same network depth, and outperforms GCNII, which uses deep architectures (16 and 32 layers) on these datasets. Moreover the gain of using edge weights appears marginal on the web datasets, suggesting that the incorporation of memory component is highly beneficial. Results from random split experiments demonstrate that memory augmented architectures have fairly stable performance.
Ablation study We analyze the contribution of different components of MemGAT MemGCN in a progressive way, with (I) backhone GNN (original GAT or GCN) (II) backbone GNN with edge weights. (III) backbone GNN with edge weights and skip connections. (IV) full MemGAT
MemGCN, which corresponds to adding memory component to the setup in (III). results on the citation datasets. The results demonstrate significant improvement provided by incorpo- rating the memory component.
6 CONCLUSIONS
We introduced memory augmentation, a framework that extends GNNs with a memory component that aims at incorporating global information of the graph. Our method has the advantage of stronger expressive power than GNNs based on LUMP protocol and is applicable to standard GNN architectures like GAT and GCN. Experimental results reflect our theoretical motivations.
REFERENCES
Yiqun Cao, Tao Jiang, and Thomas Girke. maximum common substructure- algorithm for searching and predicting drug-like compounds. Bioinformatics, 24(13):i366-13) 2008
Ming Chen, Zhewei Wei, Zengfeng Huang, Bolin Ding, and Yaliang Li. Simple and deep graph convolutional networks. arXiv preprint arXiv:2007.02133, 2020.
Djork-Aréé Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and accurate deep network
learning by exponential linear units (elus). arXiv preprint 1511.07289, 2015.
Nima Dehmamy, Albert-László Barabási, and Rose Yu. Understanding the representation power of graph neural networks in learning graph topology. In Advances in Neural Information Processing Systems, pp. 15413-15423, 2019.
Claire Donnat, Marinka Zitnik, David Hallac, and Jure Leskovec. Learning structural node embed- dings via diffusion wavelets. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 1320-1329 2018
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. Convolutional networks graphs for learning molecular fingerprints. In Advances in neural information processing systems, pp. 2222-22222222 2015.
Vikas K Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. arXiv preprint arXiv:2002.06157 2020.

---

Under review as a conference paper at ICLR 2021
Xavier Glorot and Yoshua Bengio. Understanding the difficulty of training deep feedforward neural networks. In Yee Whye Teh and Mike Titterington (eds.), Proceedings of the Thirteenth International Conference Artificial Intelligence and Statistics, volume 9 of Proceedings of Machine Learning Research, pp. 249-256, Chia Laguna Resort, Sardinia, Italy, 13-15 May 2010. PMLR.
.ww.s.mmlrr.. press wwwp://loooli.... htm
Yves Grandvalet and Yoshua Bengio. Semi-supervised learning by entropy minimization. In Advances in neural information processing systems, pp. $29-536,10 2005.
Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines.
arXiv preprint
crXiv:1410.5444 2014.
Jonathan Gross and Thomas W Tucker. Topological graph theory. Courier Corporation, 2001.
Aditya Grover and Jure Leskovec. node2vec: Scalable feature learning for networks. Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 855-864, 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovee. Inductive representation learning on large graphs. In Advances in neural information processing systems, pp. 1024-1034, 2017.
Amir Hosein Khasahmadi, Kaveh Hassani, Parsa Moradi, Leo Lee, and Quaid Morris. Memory- based graph networks. In International Conference on Learning Representations, 2020. URL
net /tto/ooododmmmoaaaaaaa
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 142.69:4/2.69900 2014.
Thomas Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. arXiv preprint arXiv:1609.02900 2016.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Combining neural networks with personalized pagerank for classificaation on graphs. In International Conference on Learning Representations, 2019a. URL /
Horum?id--lgg--2220 2m9
Johannes Klicpera, Stefan WeiB enberger, and Stephan Günnemann. Diffusion improves graph learning. In Advances in Neural Information Processing Systems 32, pp. 13354- 13366. Curran Associates, Inc., 2019b. URL http: / /ttp:://ppppr...ee nips cc/paper/ wtt---ifffuiioo-mmmmoooooo grapoovees-gapp--ae 1eapph--earnigg....
Johannes Klicpera, Janek Groß, and Stephan Günnemann. Directional message passing for molecular
graphs. In International Conference on Learning Representations, 2020. URL https://
openreview net/ htte///orrnnnddBBeeeeeeee
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018.
Ziqi Liu, Chaochao Chen, Longfei Li, Jun Zhou, Xiaolong Li, Le Song, and Yuan Qi. Geniepath: Graph neural networks with adaptive receptive paths. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pp. 4424-4431, 2019.
Chen Ma, Liheng Ma, Yingxue Zhang. Jianing Sun, Xue Liu, and Mark Coates. Memory augmented graph neural networks for sequential recommendation, 2019a.
Jiaqi Ma, Weijing Tang, Ji Zhu, and Qiaozhu Mei. A flexible generative framework for graph- sumi-supervised learning. In Advances in Neural Information Processing Systems 32, pp. Curran Associates, Inc., 2019b. URL based- samed-semdddeddddeeeeee semi -emb--uperrrsrrryy sessedlleee learning. ve fete-ffrawwor--ff -rr
nips. ccpppper///p//pp/pe/e/e
pdf
Haggai Maron, Heli Ben-Hamu, Hadar Serviansky, and Yaron Lipman. Provably pow- erful graph networks. In Advances in Neural Information Processing Systems 32, pp. Curran Associates, Inc., 2019. URL
8488 1488-provably-powee wwwp:rffulllgaaa---a--eee hhapphhnetworss.po
10

---

Under review as a conference paper at ICLR 2021
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 networks. In Proceedings of the AAAI Conference Artificial Intelligence, volume 33, pp.
2019.
Kenta Oono and Taiji Suzuki. Graph neural networks exponentially lose expressive power for node classification. In International Conference on Learning Representations, 2020. URL
https://openrev/
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- performance deep learning library. In Advances in Neural Information Processing Systems 32, pp. 8024 8024-8035. Curran Associates, Inc., 2019. URL http::ttt:///aat// /ttp:::/ppppr..eem httpppppprrs..rrppp.cceepaaaeeee
9015 hrg.raaeeeeerrrrrreeeeeeeeeeeeer
ibrary.
pdf
Hongbin Pei, Bingzhe Wei, Kevin Chen-Chuan Chang, Yu Lei, and Bo Yang. Geom-gen: Geometric graph convolutional networks. In International Conference on Learning Representations, 2020.
URL htttps://pperrevieet n forum iid=$le2ggFFVS
John W Raymond and Peter Willett. Maximum common subgraph isomorphism algorithms for the matching of chemical structures. Journal of computer-aided molecular design, 16(7):521-533, 2002.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Approximation ratios of graph neural networks for combinatorial problems. In Advances in Neural Information Processing Systems, pp. 4083- 4092. 2019.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Random features strengthen graph neural networks, 2020.
F. Scarselli, M. Gori, A. C. Tsoi, M. Hagenbuchner, and G. Monfardini. The graph neural network model. IEEE Transactions on Neural Networks, 20(1):61-80) 2009.
Jürgen Schmidhuber. Learning to control fast-weight memories: An alternative to dynamic recurrent networks. Neural Computation, 4(1):131-139, 1992.
Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann. Pitfalls of graph neural network evaluation. arXiv preprint arXiv:1811.0586 2018
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: A simple way prevent neural networks from overfitting. Journal of Machine Learning Research, 1999-):99991998 2014. URL
9rivastaval4a.htm.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In International Conference on Learning Representations, 2018.
Jason Weston, Sumit Chopra, and Antoine Bordes. 1rX.v:1410.3916, 2014.
Memory networks.
arXiv preprint
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning graphs with jumping knowledge networks. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning. volume 80 of Proceedings of Machine Learning Research, pp. 5453 5462, Stockholmsmäisaan Stockholm Sweden, 10-15 Jul 2018. PMLR. URL htttp::/proceeedd ngs. ml press/ v80/ xu Bc. html
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In International Conference on Learning Representations, 2019. URL https? //openrevier net./ httt/oorum2.doryeeee A55km

---

Under review as a conference paper at ICLR 2021
Jiaxuan You, Rex Ying, and Jure Leskovec. Position- aware graph neural networks. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 7134-7143, Long Beach, California, USA, 09-15 Jun 2019. PMLR. URL http::://///cceeeiiiii ngs. ngs.m.
press/v97/you 19..u11b.bbttt htmm
Jiawei Zhang and Lin Meng. Gresnet: Graph residual network for reviving deep gnns from suspended animation. ArXiv, abx/1909.05529, 2019.
Shuo Zhang and Lei Xie. Improving attention mechanism in graph neural networks via cardinality preservation. International Joint Conferences on Artificial Intelligence, 2020.
Jiong Zhu, Yujun Yan, Lingxiao Zhao, Mark Heimann, Leman Akoglu, and Danai Koutra. Generaliz- ing graph neural networks beyond homophily, 2020.
A APPENDIX
A.1 EXPERIMENTAL DETAILS
Dataset summary given in Table 4
An overview of the characteristics of the datasets we used for our experiments
Table Summary of the datasets used our experiments.
Cora
Citeseer
Pubmed
Actor
Cornell
Texas
Wisconsin
Nodes(# Graphs)
2708 (1)
3327 (1)
19717 (1)
7600 (1)
183 (1)
183 (1)
251 (1)
Edges
5429
4732
44338
33544
295
309
499
# Features/Node
1433
3703
500
931
1703
1703
1703
# Classes
7
3
5
5
5
Training Nodes
140
120
60
60%
60%
60%
60%
Validation Nodes
500
500
500
20%
20%
20%
20%
# Test Nodes
1000
1000
1000
20%
20%
20%
20%
For Actor, Cornell, Texas and Wisconsin datasets, we used the available split given in htw.://iiiioooogeeeeeeeemmmsssis to ensure fair comparison.
Backbone architecture Here we specify setups of the backbone architectures.
MemGAT We mostly adopted the original architecture GAT. Specifically, we used two-layer GAT across all tasks. For all but the PubMed dataset, the first layer consists of 2 attention heads and 256 features each. The second layer is used for classification with a single attention head that computes C' features (with C' being number of classes), followed by softmax activation. For Pubmed dataset, we used 8 output attention heads as in Veličković et al. (2018). For the edge weights, we picked the = Sig where is the edge weight matrix, and g(0) (h, h²) = LeakyRelu (Siy (a, [W7O I| WOR )) The nonlinear function o( (1) was chosen identically across all models and all layers the ELU function Clevert et al. (2015), with the exception that we did not use nonlinear transform of the input features.
MemGCN We used a two-layer GCN across all tasks with 256 hidden features.
Training We applied L2 regularization with tuning parameter 0.001 and a dropout (Srivastava et al. (2014) operation of probability 0.6 to each layer's 's inputs for all transductive tasks. We applied entropy regularization Grandvalet & Bengio 20055) with tuning parameter 0.6 for Cora and Citeseer datasets (but not for the ablation study) and 0.1 for Pubmed dataset. All models used Glorot initialization Glorot & Bengio (2010) and cross entropy loss optimized using Adam Kingmna & Ba (2014) with an initial learning rate of 0.01 for Pubmed dataset, and 0.005 for all the other datasets. We used an early stopping strategy on both the cross-entrop loss and accuracy on the validation nodes, with a patience of 100 epochs.
12

---

Under review as a conference paper at ICLR 2021
Optimal hyperparameters
We report the optimal choice of hyperparameters in table
Table 5: Optimal choice of hyperparameters, namely the incorporation of skip connection, the number of random walk steps K, and the type of transition matrix T. We tune K over the set {0, 1, 5, 10, 30).
MemGAT
MemGCN
Dataset
Cora
Citeseer
Pubmed
Cora
Citeseer
Pubmed
skip connection
/
V
/
X
X
K
30
0
3
30
T
Asm
Asym
Asym
Asym
Asym
Asy
MemGAT
MemGCN
Dataset
Actor
Cornell
Texas
Wisconsin
Actor
Cornell
Texas
Wisconsin
skip connection
/
/
/
/
/
/
/
/
K
0
3
3
3
3
Asym
Asm
Asym
Asym
Asym
Asya
Asym
Asym
Implementation
We implemented MemGAT based on the open source PyTorch Paszke al. (2019)
implementation of GAT Veličković al. (2018) at https: / htt/ggttuuu github..... www/potaaa.aaecooooooocooooee.ae GATT
and MemGCN based on the open source Py Torch implementation of GCN (Kipf Welling 2016 at /ictpa://gie cow wttpt//tt/ttcccccccccccee
A.2 PROOF OF THEOREMS
Proof of theorem 1. We show by induction on I, for | = 0 follows trivially since X, = X'(()) Vo V. suppose for L we have 1!44) (2)
f(w)) Vv V. for | = L + 1, consider any E V, since STAR(e) is isomorphic to STAR(f(u)) and the map f is surjective, it follows that the multiset representation of the feature vector XN. is identical to XN thus unordered aggregation
function would produce T((2)) = ( we conclude that 11 (2+1) COMBINE (1) (. =
f())
COMBINE (L) ((t) h f(()
(L+1)r
Proof of lemma For part (i), under condition C₁ there exists a parameter (hereafter referred to as identifier) 07 (x') that identifies every bounded subset (with subset in the of multiset) of X' up to distributional equivalence. The map & hence maps feature set to an "identifier" parameter. Since X' is a countable subset of some euclidean space, it's easy to find an element mo & X, and we let X' = X' Ummo). it follows immediately that if we augment every {X} into {X (mo)) 11. the identifier 05 (x2) over X identifies {X (m } and [X' U{ for any {X} + [X'}. since ma always has a multiplicity one and distinct from elements X.
The injectivity is therefore defined in the following sense: for any multiset { {
satisfying:
(i) underlying set X represented x {mo} UX where X is subset of X' with bounded size.
(ii) The multiplicity of mo is restricted to be one, and the multiplicities of other elements uniformly bounded from above.
Then under identifier 0g. GNN a; ({ ({x}) GNN, ({x+) if and only if { {x} {x}
}
which is equivalent to { {X'}. }. Applying the previous argument iteratively, we obtain identifier for each layer 07, E N and injectivity could be defined in similar ways. Part (ii) is consequence of part (i) in that we choose and X to be the corresponding graph feature of and G'
13

---

Under review as a conference paper at ICLR 2021
Proof of theorem 2. By lemma 1, the output of the second MemGAT layer would be different for h h hey Vu E V, since the underlying feature space is countable, there exists nonlinear function "(w)'
(n! < 0.5. h ((t)) 2 0.5, Ve V. Picking the readout function finishes the proof. Note also that this function could be approximated by universal approximators like multi layer perceptrons.
satisfying
Proof of corollary We first show for GCN. Note that GCN has several different definitions, we will follow the general definition in Dehmamy et al. (019) without bias term:
H(++1) = a ( (T())
(5)
where (1)) is the matrix stacked by hidden representations of each node in the /th layer, and RNXN XN + NNN is matrix transformation operation. With D (lag(Alx), two popular
forms of GCN are defined as
Kipf& & Welling 2016) uses (4) IN) IN) and a is RELU.
Xu et al. (2019) uses 72 (A) = =D (D+ (A IN) which reduces to mean pooling, and o RELU.
The fact that GCN formulated by 72 satisfied condition C₁ is directly implied by Xu et al. (2019 Corollary 8). But for GCN induced by Ti. the identifiability result need not hold since the aggregation process of each node E V is determined not solely by its neighborhood information, but also by the degree of its neighborhoods which could be arbitrary. Nevertheless, we could still gain insights from this (more popular) design by noting that with respect to regular graphs. the identifiability issue of both formulations are the same, and are mitigated via memory augmentation.
For GAT, consider the worst case of two multisets with their underlying set identical with a single element but different in multiplicities. identical to mean pooling. Hence it suffices to choose the identifier obtained from (Xu et al. 2019 Corollary 8) over mean pooling that makes GAT identify multisets up to distributional equivalence.
this case, regardless of the attention mechanism, GAT is
A.3 ON THE EFFECT OF NUMBER MEMORY NODES
In this section we present a study on training MemGAT on the Cora dataset using different number of
memory nodes M. The tuning range is (1. 3, 5, 7, 9, 11, 11, 13, 15, 17). The rest the hyperparameters are the same the one reported in table The results are reported in table The result shows little performance difference using different number of memory nodes.
A.4 ARCHITECTURES UNSUITABLE FOR MEMORY AUGMENTATION
GNN architectures that utilize max pooling for aggregating operation may not identify distributionally equivalent instances (Xu et al. 2019 Corollary 9), hence the max max-pooling version of GraphS AGE (Hamilton et al. 2017) not proper backbone architecture for memory augmentation. GIN (Xu et al. 2019) uses sum pooling that is strictly more expressive than mean pooling hence satisfies condition C, However, summing up feature vectors of the whole graph increases numerical instability and is empirically found hard to train.
A.S COMPARISONS WITH OTHER MESSAGE PASSING VARIANTS
Comparison with CPCGNN CPCGNN Sato et al. 2019) utilizes a consistent port numbering that numbers the neighbors each node by an integer E [degree(v)], according to a port numbering function p such that i) = (u. j) identifies the neighboring node labeled and port number j E (degree(z), u). The port numbering rule is said to be consistent p(p(v, i)) = (v. i) for any valid (v, i) pairs. CPCGNN allows node sending messages to node depending both its own feature and the port number of u, thus forms a certain kind of locally ordered message passing framework that is strictly more expressive than locally unordered GNNs. However was shown in
14

---

Under review as a conference paper at ICLR 2021
1
b2
2
2
1
1
2
b1
2
2
2
2
2
1
Ga
Gb
Figure 4: Consistent port numberings for G2 and Go that makes them locally distinguishable
1
2
b2
2
1
2
1
1
1
11
2
2
2
1
2
45
2
Ga
Go
Figure 5: Consistent port numbering for G. and G₁ that fails to distinguish 01 a1 and bj
Garg et al. (2020) that since consistent port numbering functions are non-unique, there exists some port numbering functions that does not strengthen expressiveness, we illustrate this phenomenon using the construction in figure and figure Figure shows port numbering that makes a, Q4 receiving different messages with that of bT Meanwhile in figure 5 the port numbering can not distinguish (1, and bj. Finding consistent port numbering that succeeds in distinguishing local structures yet another challenging task, MemGAT thus offers an easier choice when the two graphs have different global features.
Comparison with DimeNet DimeNet Klicpera et al. (2020) directional message passing model that ex- ploits the relative layout of local neighborhood through angles. Specifically DimeNet computes node embedding ho as the summation of its incoming message embed- dings 1!!h) EuEN, mi)) and the update rule is defined
Table 6: Study on number of memory nodes on the Cora dataset using Mem GAT model. Results (%mean = %stan- dard deviation test set accuracy) are com- puted over 100 trials
as
M
Performance
84.60 + 0.58
ml)) fupdate
(l-1)
Σ
fintegrate (m(11) cluv) a (wa,u))
3
84.62 + 0.58
84.70 + 0.52
7
84.64 + 0.52
(6)
84.71 + 0.54
11
84.69 = 0.67
13
+ 84.78 0.59
where Jintegrate and Supdate are analogs aggregate and combine as LUMP protocol, c(ur) is representation vector measuring the distance from u to v, and (w)), The choice
15
84.78 + 0.59
17
84.76 0.60
combines Zwwv with the distance from of metric problem dependent, and we presume a suitable exists. Consider the following construction:
15

---

Under review as a conference paper at ICLR 2021
GS
67
11
bg
bs
Gb
Ga
Figure 6: Two graphs G. = (Va, Ea) and G. (V6, Es) that DimeNet cannot distinguish locally: for any (Va, V.} and w, u, v V satisfying (u, w) E E, (u, v) E, the graph is constructed such that Lwwv 2/2 and for any (u, v) E E, the distance between u and is identical.
Figure 6 shows construction that DimeNet fails to distinguish with the local isomorphism map defined as f(a1) f (as) bi ((2) = s(as) b2, (ag) = f(07) = b3, f((4) f(as) = b4- while MemGAT is able distinguish them.
The above contrived examples suggest that the optimal choice of GNN architecture shall be problem dependent.
A.6 EXPERIMENT ON THE PPI DATASET
A.6.1 EXPERIMENTAL SETUP
We evaluated the results of MemGAT and MemGCN in the PPI dataset. For MemGAT, we used three-layer network architecture, the first two layers consist of 4 attention heads computing 256 features, and final layer uses attention heads computing 121 features each. For MemGCN, we used a two-layer network with 256 hidden features. Since the construction process of PPI dataset already includes diffusion like mechanisms, and was previously reported to have no improvements Klicpera al. (2019b), we did not apply diffusion in this experiment. The training setup is identical to those used in transductive tasks.
Baseline comparisons Aside from backbone architectures, we report GCN/GAT version of JK-Net Xu et al. (2018) with the best result (LSTM aggregation) and GeniePath Liu et al. 2019) that utilizes attention style design in the breadth search phase.
A.6.2 RESULTS
We present results the PPI dataset table The result provides strong evidence that incorporating global graph information significantly improves node classification. Moreover, since diffusion not used, the captured local structure is the same with that of backbone architectures, and smaller than the other variants. Therefore we think the contribution of memory mechanism is significant in this case, suggesting evidence that the global information helps for inductive node classification.
16

---

Under review as a conference paper at ICLR 2021
Table 7: Summary of the results (% test set micro-averaged Fi score) for the inductive setting,
performance metric averaged over 100 trials, with standard deviations also reported
Algorithm
PPI
GCN Hamilton et al. (0017)
50.00
GraphiSgee(LSTTM Veličković et (2018)
76.8
GAT Veličković al. (2018)
96.80 + 0.20
JK-LSTMIGCN Xu ct al. (2188
81.8
GGAT Xu et al.
2018
97.60 + 0.7
GeniePathL.in iu et al. 2019
97.9
MemG MemGAT(ours)
98.47 + 0.15
MemGCN(ours)
88.01 0.40
17


Reviews:
[{"review_id": "gtay4hJRePO", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "\nThe paper proposes a new class of neural networks augmented by memory nodes. The authors studied variants of GCN, and GAT with memory nodes and specifically designed edge attention functions and aggregators. The proposed models achieved competitive performance compared to state-of-the-art methods. \n\nClarity. \nOverall, the paper is well-written. Theoretical results are introduced with concise discussions and pictorial examples. They made the results more accessible. \n\nQuality/significance (pros)\n\t1. The authors found the cases where LUMP-GNNs fail and they prove it in theorem 1. \n\t2. The authors theoretically and empirically prove that memory-augmentation helps to identify locally indistinguishable graphs with different multiset feature representations in theorem 2 and Figure 3. \n\t3. The ablation study shows that the proposed modules are effective and provide significant improvement in some settings.\n\t\nWeaknesses (cons)\n\t1. The authors should compare their work with GNNs with non-local operations, e.g., LatentGNN [1]. The paper also studies the limitations of local GNNs (not specifically LUMP) but the resulting model is similar to memory augmented GNNs and it has skip connections and augmented by convolution in the latent node space.\n\t2. It's an interesting technique to improve the expressive power of GNNs but the augmentation requires significant modifications of the original GNNs. If the technique is applicable to general GNNs in a plug-and-play manner, it would be more useful.\n\t3. Depending on the edge weights, the models may behave differently. The handcrafted edge weights from the truncated diffusion matrix naturally raise the question of whether they are necessary to show the effectiveness of the proposed technique.\n\t\nQuestion. \n\t1.  In the aggregation scheme of MemGCN, $M_v^{(l=1)} = \\lambda W^{(l)} m_v{(l)} \\cdots$, \n'$m_v``$' has no nonlinear function whereas MemGAT has a nonlinear function for WRITE, .e.g,  $\\alpha_{vv}^{(l)} \\sigma^{(l)} (m_v^{(l)})$. Is this a typo? Otherwise, provide intuition why MemGCN should not use nonlinear activation functions for messages from memory nodes. \n\t2. Unlike memGCN, memGAT adjusts the effect of messages from memory nodes within the attention mechanism. Is the main reason why the MemGAT significantly underperforms MemGCN in table 2 even though the vanilla GAT consistently outperforms the vanilla GCN?\n\n[1] Zhang, Songyang, Xuming He, and Shipeng Yan. \"Latentgnn: Learning efficient non-local relations for visual recognition.\" International Conference on Machine Learning. 2019.\n\n--- Post Rebuttal ---\nI read the author feedback.  The typo in Question 1 is fixed and the issue with the edge weights is addressed. However, the proposed method requires model-specific modifications and cannot be applicable to other tasks on graphs, e.g., link prediction. Due to the limitations, I will keep the original rating.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Xkme65EMlk", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "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==========\n\nIn this paper, the authors study how to enhance the expressive power of GNNs by memory augmentation. In particular, the authors focus on the cases of the \"locally indistinguishable\" property, demonstrate why existing GNNs fail to differentiate such structures, and propose a memory augmentation strategy to break the tie. Starting from theoretical analysis, the authors suggest how to apply memory augmentation to GCN and GAT. Empirical results on public benchmark datasets suggest the effectiveness of the proposed method.\n\n==========Reason for the rating==========\n\nAt this moment, I am standing between 5 and 6. Overall, the authors tackle the expressive power enhancement problem from an interesting angle, and the technical insights are well presented. My main concern is on the gap between real-life data distribution and theoretical assumptions. While it is theoretically interesting, it is unclear how much difference \"locally indistinguishable\" structures make in reality. \n\n==========Strong points==========\n\n1. The authors investigate how to enhance the expressive power of GNNs from a unique perspective.\n\n2. The core idea is well presented with logical reasoning based on theoretical and concrete evidences.\n\n3. Empirical results suggest the proposed technique is promising in node classification tasks.\n\n==========Weak points==========\n\n1. The authors may need to clarify the scope of the theoretical results. Do the theoretical result still hold for the cases where node attributes are multi-dimensional numerical values? For the assumption in Section 3.1 \"We will assume the set $\\mathcal{X}$ to be countable, then by (Xu et al., 2019, Lemma 4), the range of $h^{(l)}_v$ , denoted $\\mathcal{H}^{(l)}$, is also\ncountable for any given parameterization and any layer l.\", what is the exact implication?\n\n2. The authors may share a few concrete examples from real-life data that suggest it is valuable to differentiate locally indistinguishable structures. Although the prediction results suggest the effectiveness, it is critical to confirm it is locally indistinguishable structures that make this difference.\n\n3. For the results presented in Table 1 and Table 2, the authors may need to consider identical train/validation/test splits for all the baseline methods for fair comparison.\n\n==========Questions during rebuttal period==========\n\nPlease address and clarify the weak points above. \n\n==========Post rebuttal==========\n\nI appreciate the authors' effort on answering my questions. Meanwhile, the authors' response does not fully address my concerns. I keep my rating as it is. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "U0aQ5KXTy0s", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 paper proposes to augment graph neural networks with awareness of global graph information based on memory neural networks.\n\nWhile this work attempts to leverage the memory networks for latent representation transformation, so as to preserve global graph structural information, there exist many recent developed graph neural models which aims to inject global-level graph structure into the embedding generation. To name a few for reference:\nDeep Graph Infomax, ICLR.\nPosition-aware Graph Neural Network, ICML.\nHowever, the proposed models (MemGAT and MemGCN) are mainly compared to some representative graph neural network architectures, like GCN and GAT, which is insufficient to demonstrate the effectiveness of the new graph neural method.\n\nAs a general graph neural network model, the evaluation experiments on only the node classification task can hardly comprehensively justify the rationality of the proposed approach. Other benchmark tasks, such as link prediction or node clustering, could be considered in the evaluation section. Additionally, it would be interesting to discuss the latent influence between memory dimensions and graph network depth.\n\nAnother important dimension of evaluation lies in the model efficiency study. How is the computational cost of the proposed MemGNN (MemGCN and MemGAT) framework as compared to other alternatives, such as GCN and GAT, can be investigated. Due the pairwise relation learning with attention mechanism, the GAT-based neural architecture could be more time-consuming. What is the additional cost brought by the designed memory neural network with multi-dimensional latent representation projection.\n\nFrom the evaluation results, we can observe that GAT- and GCN-based graph neural networks provide different performance with respect to split methods (e.g., random split and standard split). It would be interesting to provide some insights and clarifications to discuss this point, in order to understand the memory graph neural network better.", "extra_scores": {}, "extra_text": {}}, {"review_id": "-T-QHMz9P6s", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "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 paper proposes to enhance GNNs with memory networks. The authors prove that existing GNNs cannot distinguish two nodes in two graphs which are local isomorphic, then they propose introducing additional nodes for a graph that connect to all existing nodes, which help distinguish neighborhood structure for the given two nodes. This paper is basically well written and easy to follow. The idea of combining memory networks and GNNs is also novel and interesting. The experimental results demonstrate the efficacy of the proposed method. However, I have the following concerns:\n\n1. How should we understand local isomorphism intuitively? What are the connection and difference between the conventional isomorphism and local isomorphism? Can the proposed analysis be generalized to the conventional graph isomorphism? I think the paper goes a little quick from Definition 1 to Theorem 1. It would be better to put more words here to clearly demonstrate the concept of local isomorphism.\n\n2. The authors provide an example in Figure 1 and 2 to show the limit of existing GNNs and that an additional memory node is able to distinguish the two subtrees. However, the example only works in the case of two graphs. In a single graph, adding an additional node that connects to all nodes does not provide such ability to distinguish two nodes. Since the used datasets are all single graph, I was wondering what the benefit of introducing an additional node is.\n\n3. The theoretical part is nice to read, however, they are all existence theorems, which neither tells us how to find such solutions or provides performance guarantees for the proposed method. The proposed method seems more likely to address a very special case where two nodes (in two graphs respectively) cannot be distinguished, but this case rarely happens in practice.\n\n4. In experiments, I was wondering why the authors uses diffusion matrix rather than the original adjacency matrix, since it makes readers unclear that the performance gain is brought by the memory mechanism or the diffusion matrix. It would be more convincing to use original adjacency matrix in the proposed method, or add (Klicpera et al., 2019) as a baseline.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: In this paper, the authors proposed a method to handle the problem of LUMP GNN architecture. This problem is indeed important and the proposed method has some merits. However, the proposed approach is only applicable to node classification.  Moreover, the proposed approach shows the similar theoretical results of Sato et al 2020. In the paper, it can be applicable to any GNN tasks because it only adds random features to each node. Therefore, the novelty of the proposed method is limited.  I encourage authors to revise the paper based on the reviewer's comments and resubmit it to a future venue. 
Decision: Reject