Learning Discrete Adaptive Receptive Fields for Graph Convolutional Networks
Authors: Xiaojun Ma
Ziyao Li
Lingjun Xu
Guojie Song
Yi Li
Chuan Shi
Venue:  (2021)
Keywords: Graph Neural Networks
Reinforcement Learning
Attention Mechanism
Adaptive Receptive Fields

Abstract: Different nodes in a graph neighborhood generally yield different importance. In previous work of Graph Convolutional Networks (GCNs), such differences are typically modeled with attention mechanisms. However, as we prove in our paper, soft attention weights suffer from over-smoothness in large neighborhoods. To address this weakness, we introduce a novel framework of conducting graph convolutions, where nodes are discretely selected among multi-hop neighborhoods to construct adaptive receptive fields (ARFs). ARFs enable GCNs to get rid of the over-smoothness of soft attention weights, as well as to efficiently explore long-distance dependencies in graphs. We further propose GRARF (GCN with Reinforced Adaptive Receptive Fields) as an instance, where an optimal policy of constructing ARFs is learned with reinforcement learning. GRARF achieves or matches state-of-the-art performances on public datasets from different domains. Our further analysis corroborates that GRARF is more robust than attention models against neighborhood noises.

Under review as a conference paper at ICLR 2021
LEARNING DISCRETE ADAPTIVE RECEPTIVE FIELDS FOR GRAPH CONVOLUTIONAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
Different nodes in graph neighborhood generally yield different importance. In previous work of Graph Convolutional Networks (GCNs), such differences are typically modeled with attention mechanisms. However, as we prove in our paper, soft attention weights suffer from over-smoothness in large neighborhoods. To address this weakness, we introduce novel framework of conducting graph convolutions, where nodes discretely selected among multi-hop neighborhoods to construct adaptive receptive fields (ARFs). ARFs enable GCNs to get rid of the over-smoothness of soft attention weights, well long-distance dependencies in graphs. We further propose GRARF (GCN with Reinforced Adaptive Receptive Fields) as an instance, where an optimal policy of constructing ARFs is learned with reinforcement learning. GRARF achieves or matches state-of-the-ee thet performances on public datasets from different domains. Our further analysis corroborates that GRARF is more robust than attention models against neighborhood noises.
efficiently explore
INTRODUCTION
After series of explorations and modifications (Bruna et al. 2014 Kipf & Welling 2017 Velickovic al. 2017) Xu et al. 2019 Li et al. 2019 [Au-EEl-Hija et al. 2019), Graph Convolutional Networks (GCNs) have gained considerable attention the machine learning community. Typically, graph convolutional model can be abstracted
message-passingg process (Gilmer et al. 2017) nodes in the neighborhood of central node are regarded as contexts, who individually pass their messages to the central node via convolutional layers. The central node then weighs and transforms these messages. This process is recursively conducted as the depth of network increases.
Neighborhood convolutions proved to be widely useful various graph data. However, some inconveniences also exist in current GCNs. While different nodes may yield different importance in the neighborhood, early GCNs (Kipf & Welling 2017 Hamilton et al. 2017) did not discriminate contexts in their receptive fields. These models either treated contexts equally, or used normalized edge weights as the weights of contexts. As a result, such implementations failed to capture critical contexts - contexts that pose greater influences on the central node, close friends among acquaintances, for example. Graph Attention Networks (GATs) (Velickovic al. 2017) resolved this problem with attention mechanisms (Bahdanau et al.) 2015 Vaswani et al. 2017). 7). Soft attention weights were used to discriminate importance of contexts, which allowed the model to better focus on relevant contexts to make decisions. With impressive performances, GATs became widely used in later generations of
GCNs including (Li et al. 2019: Liu et al.. 2019).
However, observe that using soft attention weights in hierarchical convolutions does not fully solve the problem. Firstly, we will show as Proposition] that under common conditions, soft attention weights almost surely approach 0 the neighborhood sizes increase. This smoothness hinders the discrimination of context importance in large neighborhoods. Secondly, we will show by experiments
I use the name GCN for a class deep learning approaches where information convolved among graph neighborhoods, including but not limited to the vanilla GCN (Kipf & Welling 2017).
We use the contexts to denote the neighbor nodes, and receptive field denote the of contexts that the convolutions refer to.
"The smoothness discussed in our paper is different to that in [Li et al. 2018), i.e. the phenomenon that representations of nodes converge in very deep GNNs.

---

Under review as a conference paper at ICLR 2021
Central Node
Critical Contexts
Common Contexts
Noiscs
Hicrarchical RF
Adaptive
Figure 1: A Comparison between hierarchical convolutions and convolutions with ARF. Left: GCNs with ARFs better focus on critical nodes and filter out noises in large neighborhoods. Right: ARFs more efficiently explore dingdnistncce dependencies.
in Section 4.2 that GATs cannot well distinguish true graph nodes from artificial noises: attention weights assigned to true nodes and noises are almost identical distribution, which further leads to a dramatic drop of performance.
Meanwhile, an ideal GCN architecture is often expected to exploit information on nodes with various distances. Most existing GCNs use hierarchical convolutional layers, in which only one-hop neighborhoods are convolved. As result, one must increase the model depth to detect long-distance dependencies (informative nodes that distant from the central nodes). This is particularly issue in large graphs, as the complexity of the graph convolutions is exponential to the model depth. F In large graphs, the model depths are often set as 1, 2 or 3 (Hamilton et al. 2017 Velickovic et al. 2017]. Accordingly, no dependencies longer than 3 hops are exploited in these models.
Motivated by the discussions above, we propose the idea of adaptive receptive fields (ARFs). Figure iillustrates the differences between hierarchical convolutions and convolutions with ARFs. An ARF is defined as a subset of contexts that are most informative for a central node, and constructed via selecting contexts among the neighborhood. Nodes in an ARF can be at various distances from the central node. The discrete selection process of contexts gets rid of the undesired smoothness of soft weights (see Section 2) In addition, by allowing ARFs to choose contexts different hops from the central node, one can efficiently explore dependencies with longer distances. Experiments also show that ARFs more robust noises (see Section 4 We further propose GRARF (GCNs with Reinforced Adaptive Receptive Fields) as an instance for using ARFs in node-level tasks. In GRARE, an optimal policy of constructing ARFS learned with reinforcement learning (RL). An RL agent (constructor) successively expands the ARF via two-stage process: a weteeedittllycoosrreeeee
contact node in the neighbors of the contact node is then added to the ARF. The reward of the constructor is defined as the performance of trained GCN (evaluator) on the constructed ARF.
ARF is firstly selected; context among the direct
GRARF is validated on datasets from different domains including three citation networks, one social network, and an inductive protein-protein interaction dataset. GRARE matches or improves performances on node classification tasks compared with strong baselines. Moreover, we design two tasks to test the models' abilities focusing on informative contexts and leveraging long-distance dependencies by injecting node noises in graphs with different strategies.
PRELIMINARIES AND THEORIES
Notations. In our paper, we consider node-level supervised learning tasks on attributed graphs. An attributed graph G is generally represented as G = (V, A, X), where V == {UI,.... ",,,",,,,,)), denotes the set nodes, E {0, 1] j denotes the (binary) adjacency matrix, and X E Rixdo denotes the input node features, T,, E Rd the features of node v. E is used as the set of edges. We use N(v;) to denote the one-hop neighborhood of node 2s with v, itself included. We use (!) E Ruxd; as the matrix containing di- di-dimensional hidden representations of nodes in the I-th layer, A!!") that of node
' With sparse adjacency matrices, the average complexity of graph convolutions is O(d2), ). where is the model depth and is the graph degree (or the brighborhood-smmllin sizes (Hamilton et al. (017)). We mainly show the results of node classification tasks in our paper, whereas GRARFis is intrinsically adapted all node-level supervised learning tasks.
2

---

Under review as a conference paper at ICLR 2021
Å denotes the symmetrically normalized adjacency matrix with Á D = diag(d): d; Σ, (A + In).s- We use bold letters for neural network parameters.
and
The smoothness Graph Attention Networks. As a pioneering work of simplifying architectures of graph neural networks, the vanilla GCN layers in (Kipf & Welling 2017) were defined as
H( (AH =o
Σ (EN(K))
(1) wit)) wii Aggh
1=
(1)
In each layer, the node representations in one-hop neighborhoods were transformed with W and averaged by normalized edge weights A.j. Graph Attention Networks (GAT') (Velickovic et al. 2017) elaborated the average scheme in Eq. ① with attention mechanisms (Bahdanau al. 2015 Vaswani al. 2017). Instead of using A.j. attention weight oij between node nn and fy was calculated in GAT layers
exp(erg)
Eij fo (he, 11),, aij- = softmax, (eiy) = ENEN(e)) exp(ea))
(2)
where so(-) is often called the energy function with parameter 0. GATs implicitly enabled specifying different weights in neighborhood. However, under some common assumptions and as the neigh- borhood size increases, these attention weights, normalized with the softmax function, suffer from over-smoothness: all attention weights approach 0 as the neighborhood size increases. We formally introduce and prove this claim as Lemma I and Proposition] 1
Lemma 1 (the smoothness of softmax). If random variables X2, are uniformly bounded with probability I, that is, for any and some C, P([X;] C*- = O, then the softmax values taking Xx) as inputs approach 0 almost surely when -> 00, i.e.
Xx
Σ
X
- a.
(3)
Proof. The proof is simple noting that e
/Ei= N, > 0. and that with probability 1,
exK, Σ Ee' <e //ne <
Proposition 1 (the smoothness of attention weights). If the representation of nodes (random vectors) H1, Hz.... E Rdd are uniformly bounded with probability I (for any i and some C, P[[ C*) 0), for any (fixed) node Un the energy function (h+ is continuous on any closed set E R then the attention weights in the neighborhood of 0; approach 0 almost surely when n 0o, i.e.
exp(Jo(hi, H2))
aij EXEN(U)) exp(fo(h,. H+), + 0 a.s.
Proof. Following the a.s. boundedness {H,}s and the continuity condition on (-)), the random energies Eij- = Jo(h; Hj) are also bounded a.s., The desired result then follows Lemma
Note that the continuity condition on (he, -) in Proposition can be satisfied with almost any commonly used non-linear functions and (regularized) parameters deep learning, specifically, those in the official version of GAT's (Eij = a [/ [h,,,, where || is the operator of concatenation). Also, the boundedness of inputs trivial in deep learning.
GCNs with ARFs overcome smoothness. What Proposition D shows that in large neighborhoods, attention weights are smoothed to O. thus hindering the discrimination of context importance. In addition, such smoothness can be immediately generated to any other form of normalized weights as long as aij > 0 uniformly and EjeN(e:) Qij incorporating discreteness. Specifically, let us denote the convolution the evaluator as
We alleviate the smoothness with ARFs by
( Σ
M
nggh Σ (e)
Tnghyy (EN
fij
{
Majs
j E Na(u), j $ (u),,,
(5)
0,
3

---

Under review as a conference paper at ICLR 2021
where Nu) is an ARF, l is the maximum hop that the ARF explores, and N is the entire k-hop neighborhood. Accordingly, fhy is not subjected to smoothness: if Thy has a uniform lower bound D > O, then for E (u) and & (u), we have 7/pp fig > D, regardless of the sizes of N Note that Tke > 0 uniformly can be guaranteed in most cases when the maximum ARF size is limited, for example, with uniform weights or softmax weights of bounded energies.
It should be noted that the discrimination of nodes in ARFs is different that in MixHop (Abu-El- Haija et al. 2019), which directly takes multi-hop nodes as inputs. MixHop can specify different parameters for contexts on different hops (hop-level discrimination). while it CANNOT specify different weights for contexts on the same hop (node-level discrimination) as they were uniformly treated (averaged). The two levels of discrimination are orthogonal, and we focus on the latter.
Deep reinforcement learning on graphs. As the discrete context selection process is non- differentiable, we apply deep reinforeement learning approaches to learn the policy of construting ARFs in GRARE, specifically, the Deep Q-Learning (DQN) (Mnih et al., 2015) algorithm. DQN uses deep neural networks to approximate the action value function (Q-function) and chooses the action that maximizes it in each step. The Q-function is defined iteratively
(st = R(st. ae, St41) + max Q" (8)+1,a), a
where s the state, R(-) the reward function, A is the action space, and y is a discount factor. A reward shaping technique (Ng et al., 1999| is also used in GRARF to alleviate the sparsity of rewards, which decorates the original reward R(.) with a potential energy F()). yielding an immediate reward R(-). Denoted in formula,
F(s, 0,,5,,)) -05'= (s), i(ss ass,a,s) R(s, a's + F(s,a,'))
where (--)) is a fixed potential function of states that does not change during training, (Ng et al. 1999) proved that the optimal policies of MDPs remain invariant if IT(-) is replaced by I((-).
There are other recent papers implementing reinforcement learning on graphs. For example, GCPN (You et al. (2088) proposed an RL agent for generating graph representations of biomedical molecules, and DGN (Jiang et al. 2020) introduced a multi-agent reinforcement learning approach where the agents in the system formed dynamic network. The successive molecule generation process in GCPN inspired us in designing the ARF constructor in GRARF, whereas the two models are of different motivations and applications.
ARFs and neighborhood sampling. It should be noted that GRARF can also be interpreted as a neighborhood sampling approach. Neighborhood sampling was proposed necessary process to apply GCNs to large graphs with arbitrarily large neighborhoods. GraphSAGE (Hamilton et al. 2017) proposed a general framework of neighborhood sampling and aggregation, where contexts were uniformly sampled. Later work improved the sampling strategy with importance sampling (Chen
al. 2018) and explicit variance reduction (Huang et al., 2018: Hamilton et al. 2017). Sub-graphs instead of subsets of neighborhoods were directly sampled in (Zeng et 2020). Indeed, selecting ARF nodes takes a specific form of neighborhood sampling. However, the aim of constructing ARFs is to ignore trivial information and to focus critical contexts, rather than to estimate the
neighborhood average as the primary target of neighborhood sampling. Therefore, despite the similarity, the two approaches are in different directions.
3 PROPOSED METHOD: GRARF
3.1 ARF CONSTRUCTION AS MARKOY DECISION PROCESS
An adaptive receptive field is defined as a set of nodes Na( with regard to a central node u. Nodes in Nu(u) can be at various distances from u, and itself should be contained in its ARF. We also assume that the induced subgraph of an ARF must be (weakly) connected, under the motivation that if a far context poses great influence on the central node, then least one path connecting central node should be included in the ARF. The ARF construction process is modeled as a Markov
the
Forr clarity, we use the term parameters for parameters in the transformation matrix W (see (q. in the original paper), and weights for the weights of different contexts (c.g. the attention weights).
4

---

Under review as a conference paper at ICLR 2021
Reward
Labels
loss
Predictions
a
81
Constructor
Evaluator
(S
Figure 2: The general architecture of GRARE. Red and blue arrows together demonstrate the training process. Blue arrows along demonstrate the prediction process.
Decision Process (MDP) M = (S, A. where S = {s;} is the state space of all possible ARFs; = {ar} describes all possible (two-stage) actions a = (a a²);; is the transition dynamies p(8++1 8t,, (z)) which describes how nodes are added to ARFs; R is the reward function of an ARF; and y the discount factor.
Figure introduces the general structure of our model. GRARF is composed of a constructor and an evaluator. The constructor implements an RL. agent to learn an optimal policy of the MDP with DQN, and the evaluator conducts graph convolutions phase, the constructor and the evaluator are trained alternately, where rewards of the constructor are derived from the performances of the evaluator; in the prediction phase, the evaluator convolves over the ARFs constructed for the target node by the constructor and then predicts the result. No gradient flows between the constructor and the evaluator.
constructed ARFs. Specifically, in the training
3.2 MODEL ARCHITECTURE
We hereby specify the MDP of ARF construction, the evaluator, and the training scheme.
States. At step the state s, is defined as the intermediately generated ARF, which is encoded as vector representation s by function fa. and then observed by the constructor. Formally,
8t A N (u), 5 (.( (u)),
(8)
We initialize the ARF as !o0 (u) = {u). The transition dynamics in GRARF is deterministic: nodes selected by the RL agent is added to the ARF, i.e. xr(-1)( = N:O0) (u) U
Actions. For each action, the constructor chooses node to add to the ARF among all nodes adjacent to the ARE The average complexity of directly choosing among all adjacent candidates is O(n, x d), where n, is the ARF size at step and is the graph degree. We reduce the complexity to O + d) by decomposing the action into two stages, denoted as a, = (a.. af). In the first stage, the constructor chooses a contact node af E (v(()
(w). who limits the candidates of the next stage its own direct neighborhood. In the second stage, the constructor searches among the neighborhood of of for node a? to add to the ARF. The optimal Q-function can accordingly be rewritten as
Qi at) max a2EN(a!)
(7,,
Q2(0, af at) R(s at 8141) +7
max (144)1,)1)
(10)
CIEN ( (a)
(1)
We do not design explicit stop actions, and the process stops after fixed number of steps (T). Meanwhile, we do not require that af & (x (u), so node may selected multiple times in an ARF Note that if node already in the ARF is selected, the state ceases to change, and no new nodes will be selected. Therefore, various ARF sizes are implicitly allowed. The actions (i.e. candidate nodes) in both stages are encoded with fax and the approximated Q-function in GRARF is parameterized as
Q1 at) = w/ [ff(a))]lf(ss.) + bb, Q2(5), a; at) = wi [fa(c))l((((())))((ss) + b2.
(11)
(12)
5

---

Under review as a conference paper at ICLR 2021
Rewards. The reward of the constructor is defined as the performance of the GCN evaluator. As conducting nep-wise evaluations is much time-costly, we sample the reward once the ARF is fully constructed, that is,
{
0, eval (No = loss
t< t t= T.
R(st, og 8141)
lloss (GCN (N)
(13)
The loss in Eq. 13) is specified by the downstream supervised node-level (or node-pair-level) tasks, such as node classification, link prediction, etc. We further adopt the reward shaping technique (Ng et al. 1999) to guide and accelerate the training process. Considering the desired properties of critical
contexts and ARFs, we propose the following heuristic potential functions: 2 ( |.va (w)).
the sizes of ARFs, to encourage the variety of contexts; ii) P2(s) = -' (u) deg(e), the sum of
degrees in the ARF, nodes with higher degrees intuitively more informative; iii) (3(s))
LvEN,()) sim v, u) = Eve (u) Zp . Lu, the inner product of input features between the central node and the ARF nodes, to empirically encourage more relevant contexts. According to Eq. 7 with so-defined Ds, the immediate rewards of the constructor is
0,
< and of E No N (u),
M[t, oi, S141) =
1 deg(a;) Fz Iuu - loss (GCN (No (u))
= T. of $ No (u),
< T
and
(14)
Evaluator: Given a central node u and the constructed ARF (u(u), the evaluator takes the ARF as neighborhood and convolves over it, generating the representation of the central node. An example of evaluator would be the one defined Eq. (5). The representation then used to conduct downstream tasks. Theoretically, any graph convolutional layers can be used as the evaluator. It is worth noting that although in our experiments we only perform a one-layer graph convolution on the constructed ARF, multiple convolutional layers can be applied on the subgraph induced by the ARF node set. We leave this as future work.
Training. In order to mutually train the constructor and the evaluator in GRARE, we propose an alternate training strutegy, somehow analogous to the training GAN (Goodfellow et al.) 2014). Specifically, the evaluator is first pre-trained for the given downstream task, taking direct neighborhoods as receptive fields. We then fix the evaluator to derive constant lask- rewards for the training of the constructor. The alternate process goes recursively until convergence. In details, as the training of the evaluator converges much faster than the constructor, we train the constructor with more steps in the alternate process. Empirically, 10 1 is promising choice of the ratio.
EXPERIMENTS
4.1 EXPERIMENT SETUP
Datasets. We evaluate GRARF public real-world datasets including 3 citation networks, social network, and a protein-protein interaction dataset. Some interesting statistics of the datasets are shown in Table In the citation networks (cora, citeseer and (aobmmm)).nnode.... correspond to publications in disjoint fields, and edges to (undirected) citation relationships. The social network (gi (hit consists of website users (nodes) and their friendships (edges). We reduce the number of input features of social networks to the figures in Table [ by selecting most frequent ones (all features binary and sparse). The protein-protedt interaction (ppi) [ataase"containn 24 graphs, each representing human tissue, where nodes denote different proteins and edges denotes the interactions in between. We use the preprocessed data of GraphSAGE (Hamilton al. 2017).
Baselines. We pick up 5 GCN baselines to compare GRARF against, including vanilla GCN (Kipf Welling 2017), GraphSAGE (Hamilton al. 2017). GAT (Velickovic et al. 2017). GIN (Xu ct al. 2019) and MixHop (Abu-El-Haij et al. 2019). For fairness, the dimensions of all hidden
Available atttts://ings..ee.eee
Available at http:///aa.asssanorrdlllllllbaaa

---

Under review as a conference paper at ICLR 2021
Table 1: Interesting statistics of the datasets used in this paper. (": multi-labe task)
citosser
pubmod
github
ppi"
# Nodes
2,708
3,327
19,217
57,700
56,944
1innss
5,420
4,753
44.338
289,003
818.716
# Classes
121
ef Features
1,433
3,703
500
600
50
Avg.
28.8
Table 2: Performances of GRARF and baselines on node classification tasks. (% micro-fl)
citoseer
puzmed
cithub
Vanilla GCN Kipf Welling 2017
87 10:00
+ 0. 0.36
78.09 + 0.35
86.18 + 0.10
81:72 + 0.14
59.26 + 0.03
Goy
70.23
0.51
0.33
56.97
0.94
Nelickonns
87.80
76.43
0.73
85.39 + 0.12
81.78
0.52
47.29
2.30
GIN Xureaa 33p9
85.U8
0.83
78.87
0.52
84.88
+ 0.17
79.05
0.88
60.35
4.15++11.144 1.14
Mixhoop Aln Rajja
2019
88.70
0.19
74.59 + 0.27
85.60 4: 0.10
79.68 + 1.00
58.55
0.14
Random RF
86.93
1: 1.22
77.31 4: 1.37
86.87 +: 1.30
79.61
7.82
63. 1 2.38
GRARF
88.34
0.82
79.24
0.88
88.20
4 0.33
87.30
2.54
66.54
1.12
representations are set as d 128 and an identical two-layer setup used all baselines. Hyper- parameters such as learning rates in all models are tuned to achieve best performances on the validation sets. All neural models are trained with adequate epochs with the early-stopping strategy. More details of baselines are included in the Appendix.
GRARF implementation. In the constructor, all graph nodes are first encoded with Graph- SAGE layer (h = elu WW W=(lll EveNiw Tol + be)). For the state encoder fs. we use linear transformations of concatenations of central node representations and ARF-averaged node rep- resentations, i.e. (u) = lll E directly use the hidden representations of nodes, i.c. (v) = -,.- The discount factor is chosen as 7 0.9. In the evaluator, simple GraphSAGE layer convolves over constructed ARFs as h = clu( W [W[ ll EveNa(u) x.]+ b.). The hidden representations ht are later used in node-level tasks with only one fully-connected layer. The same as all baselines, dimensions of all hidden representations in GRARF (h., h and 87) are 128. To demonstrate the effectiveness of ARFs, we also conduct experiments with random baseline, Random RF, where actions are chosen completely randomly, but strictly following the setup of GRARF.
ErEN, hg] + b,. For the action encoder fa, we
4.2 RESULTS
Performances of node classification tasks. Table Table[ishows the micro-fls of GRARF and baselines on the node classification tasks including means and standard deviations across 10 replicas. The datasets are uniformly split to 5 : as training, validation and test sets, except for ppí, where 20 graphs are used as training set, as validation set and as test set, identical that in (Hamilton et al., 2017). Tasks are transductive on citation and social network and inductive on ppi. GRARF shows very competitive performances on both types of tasks: on citation graphs where neighborhoods are small (degree Rs 2), GRARF matches or improves by margin the performances of other baselines; on github and ppi datasets with larger neighborhoods (degree > 7), GRARF displays a significant advantages over other baselines. This is in concordance with expectations, as we have shown that GRARF overcomes the smoothness and thus better focuses on informative contexts in larger neighborhoods.
Capturing informative contexts and long-distance dependencies (LDD). To demonstrate the benefits of using ARFs, we design two experiments through adding artifical noises in cora with different strategies. In the denoising setup, we generate r x [V] noise nodes and randomly connects them to true nodes. An amount of |E| edges between true nodes and noises are added, so that the proportion of noises in the neighborhood is approximately T In the LDD setup, we assign split number k drawn from Poisson(A) on each edge, and then split each edge to a (k- hhop path (do nothing k 0) by inserting & noises. The one-hop dependencies are hence stretched longer and more difficult for the models to detect. In both experiments, features of noises are drawn individual dimensions. We conduct experiments with 5 replicas per
from marginal distributions model and report the averaged performances and 95% confidence intervals. Figure 3 shows examples and performances of GRARE, vanilla GCNs under two setups. We also show the performances of raw-feature baseline for comparison (which fully ignores the noises).
7

---

Under review as a conference paper at ICLR 2021
01
mitem
03
0.5
0.
Tim Nedes
Natoes
True Nodes
Notoes
split
(b)
(c)
(d)
Figure 3: Examples and results of two designed experiments. (a)(b) The denoising experiment. (c)(d) The long-distance dependency experiment. GRARF displays robustness to noises in both experiments, whereas performances of vanilla GCNs and GAT' drop dramatically.
6:0
3 8
moda
000
00:1112
08
C2
0. 08
10
04
02
3.5
03
10
08
02
3G5
0.5
15
(8)
(b)
(c)
(d)
(0)
Figure 4: Analysis of behaviors GAT and GRARE (a) A box-plot of attention weights on cora with regard node degrees, where medians, Qls, Q3s and 95% intervals are displayed. (b)-(d) Histograms of attention weights assigned to true nodes and noises in the denoising experiments
(r = 1), with different node degrees (d 2, 10). (e) The ratios of noises in constructed ARFs with regard to node degrees, in the denoising experiments (r 1).
In the denoising experiment, GRARF displays a significantly better ability in capturing informative nodes while ignoring noises. The performances of vanilla GCNs and GATs drop dramatically increases and even below the raw baseline when r > 1, whereas the performances of GRARF drops only marginally. A similar phenomenon is observed in the LDD experiment, which corroborates that the constructed ARFs in GRARE better collect the information from far-hop neighbors through exploring the neighborhood in a more flexible manner.
We further analyzed the behavior of GATs and GRARF on real and noisy data. Figure 4 (a) shows the distributions of attention weights that GATs assign to neighbors ds) on original cora. The majority of attention weights lie in a very thin interval around 1/d which continues shrink d increases. This is empirical evidence of Proposition [ Figure (b)-(d) show distributions of attention weights assigned to true nodes and noises in the denoising experiment with 1 and d 2, 5, 10 (calculated true nodes' neighborhoods only.). Attention weights assigned to true nodes and noises are almost identical, especially with larger d. This indicates that GAT's cannot well distinguish noises from true nodes with attention weights. We also report the ratios of noises in constructed ARFs in the same experiment. The noise ratios in the ARFs stay far below the noise ratio in the graph, and remain almost invariant to the sizes neighborhoods. This suggests that the ARF constructor learns ignore noises in the graph neighborhoods.
central nodes (with degree
CONCLUSION & FUTURE WORK
In this paper, we proposed the idea of adaptive receptive fields and GRARF as an instance. We showed both theoretically and empirically that GCNs with ARFs address the smoothness of attention weights, and hence better focus on critical contexts instead of common ones or noises. Meanwhile, nodes in ARFs be various distances from the central node, GCNs with ARFs explore long-distance dependencies more efficiently. Nevertheless, the ARFs in our paper are simplified as sets of nodes, whose structures are mostly ignored.
For future work, a straight direction is to learn an optimal convolutional structures on constructed ARFs, to jointly learn both. Finding fast approximations of RL is also attracting. Another promising prospect to provide the constructor with more global-level information, for currently constructor only observes local neighborhoods.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Sami Abu-al-Haija, Bryan Perozzi, Amol Kapoor, Nazanin Alipourfard, Kristina Lerman, Hrayr Harutyunyan, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing, In Proceedings of the 36th International Conference on Machine Learning (ICML 2019), pp. 21-29, 2019.
Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. Neural machine translation by jointly learning to align and translate. In Proceedings of the 3rd International Conference on Learning Representations (ICLR 2015), 2015.
Joan Bruna, Wojeiech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. In Yoshua Bengio and Yann LeCun (eds.). Proceedings of the 2nd International Conference Learning Representations (ICLR 2014), 2014.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: Fast learning with graph convolutional networks via importance sampling. Proceedings of the 6th International Conference on Learning Representa- tions (ICLR 2018), 2018.
Justin Gilmer, Samuel Schoenholz, Patrick F. Riley, Oriol Vinyals, and George E. Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference Machine Learning (ICML 2017), pp. 1263-1272, 2017.
lan Goodfellow, Jean Pouget-Abadie. Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron C. Courville, and Yoshua Bengio. Generative adversarial networks. CoRR, abs/ 266,,,1, 2014.
William L. Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning large graphs. In Isabelle Guyon, Ulrike von Luxburg, Samy Bengio, Hanna M. Wallach, Rob Fergus, S. V. N. Vishwanathan, and Roman Garnett (eds.), Proceedings of the Annual Conference on Neural Information P Processing Systems 2017 (NeurIPS 2017), pp. 1024-1034, 2017.
Wen-bing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. In Proceedings of the Annual Conference Neural Information Processing Systems 2018 (NeurIPS 2018), pp. 4563-4572, 2018
Jiechuan Jiang, Chen Dun, Tiejun Huang, and Zongging Lu. Graph convolutional reinforcement learning. In Proceedings of the 8th International Conference on Learning Representations (ICLR 2020), 2020.
Thomas N. Kipf and Max Welling, Semi-supervised classification with graph convolutional networks. In Proceedings of the 5th International Conference on Leurning Representations (ICLR 2017), 2017.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi-supervised learning. In Proceedings of the Thirty-Second AAAI Conference Artificial Intelligence (AAAI 2018), pp. 3538-3545 2018.
Ziyao Li, Liang Zhang, and Guojie Song. GCN-LASE: towards adequately incorporating link attributes in graph convolutional networks. In Sarit Kraus (ed.), Proceedings of the Twenty-Eight International Joint Conference on Artificial Intelligence (IJCAI 2019), pp. 2959-2965, 2019.
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 Thirty-Third AAAI Conference on Artificial Intelligence (AAAI 2019), pp. 4424 4431. AAAI Press, 2019.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A. Rusu, Joel Veness, Marc G. Belle- mare, Alex Graves, Martin A. Riedmiller, Andreas Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, loannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, 518(7540):529-53, 2015.

---

Under review as a conference paper at ICLR 2021
Andrew Y. Ng. Daishi Harada, and Stuart J. Russell. Policy invariance under reward transformations: Theory and application to reward shaping. Proceedings of the Sixteenth International Conference Machine Learning (ICML 1999), pp. 278-287 1999.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In Proceedings of the Annual Conference on Neural Information Processing Systems 2017 (NeurIPS 2017). pp. 019555999999 2017.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. CoRR, abs/1710. 2017.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In Proceedings of the 7th International Conference on Learning Representations (ICLR 2019), 2019.
Jiaxuan You, Bowen Liu, Zhitao Ying, Vijay S. Pande, and Jure Leskovec. Graph convolutional policy network for goal-directed molecular graph generation. In Proceedings of the Annual Conference on Neural Information Processing Systems 2018 (NeurIPS 2018), pp. 6412 6422, 2018
Hanqing Zeng. Hongkuan Zhou, Ajitesh Srivastava, Rajgopal Kannan, and Viktor Prasanna. Graph- saint: Graph sampling based inductive learning method. In Proceedings of the 8th International Conference on Learning Representations (ICLR 2020), 2020.
10


Reviews:
[{"review_id": "weuJhfgNhZu", "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": "To address the over-smoothness in neighborhood caused by soft-attention in GNN, this paper presents an idea of adaptive receptive fields (ARFs), which can choose contexts on different hops from the central node, so as to efficiently explore dependencies with longer distances.  The construction of ARFs follows a reinforcement learning (RL) framework. \n\nThe adaptive selection of contextual neighbors is a promising solution, as not all the neighbors are equally important. It is an interesting idea to apply reinforcement learning to this problem. An RL agent first selects  a contact node in the direct neighbors, and then explores the neighbors of this contact node. \n \nAlthough the design of ARF with RL is a valuable practice,  the ARF construction process has several issues. It defines the state of a target node as a vector from f_s by taking the searched neighbors as input. How f_s is defined? The action is to select a neighbor of a target node u from its 1-hop or 2-hop neighbors. Even when the states transit from one to another, the action is always to select neighbors of u from its 1-hop or 2-hop neighbors, rather than going deep to explore the graph for more useful neighbors. After a fixed number of steps T, the added neighbors are still within the 2-nd order neighbors. Such an ARF construction process limits the region to explore in the graph. It cannot \"explore dependencies with longer distances\".\n\nThe presented approach shares a lot similarity with that in [1]. The constructor is analogous to the score network f_s, while the evaluator is analogous to the network f_h and f_c for accumulating the neighbor with recurrent attentions and for classification. However, [1] is not cited, and not used as a baseline to compare. \n\nIn addition, the over-smoothing problem for GNN has been recently studied in several papers, authors are suggested to cite and compare with them as well, such as [2] [3].\n\nSuggestions to the authors:\n1) The design of ARF should be improved, with a reasonable setting of the state function and actions. \n2) Recent work should be aware. Discussion and experimental comparison with them should be included.  \n\n[1] Akujuobi et al. Recurrent Attention Walk for Semi-supervised Classification. WSDM 2020\n\n[2] Chen et al. Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. AAAI 2020.\n\n[3] Xie et al. When Do GNNs Work: Understanding and Improving Neighborhood Aggregation. IJCAI 2020\n\n\nThanks to authors for the clarification.  I have updated my score. \nHowever, a easy search with the title of the paper \"Recurrent Attention Walk for Semi-supervised Classification\" in Google can find the code in GitHub. \n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "ljfq6983Leo", "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": "\n\n**Summary:**\n\nThe paper proposes a method for avoiding the oversmoothing happening in standard GNN methods. It defines a receptive field of a node, as the set of nodes that send messages to that node and proposes a method to create adaptive receptive fields specific to each node. Instead of using all the nodes in a multi-hop neighbourhood, an reinforcement learning method is proposed to select only a subset of these nodes. The RL problem is formalised such that each state represents a set of already selected nodes, while actions represent the next selected node. The goal of the RL agent (constructor) is to form an adaptive neighbourhood for each node, and the reward is given by the loss of a GNN method (evaluator) that uses this neighbourhood. \n\n**Strengths:**\n\n\nAdapting the receptive field of each node in a GNN is a good idea that could result in better modeling of the context, longer connections and also avoiding feature oversmoothing. \n\nThe proposed RL method to create adaptive receptive fields is sound and experiments show that it is indeed useful.\n\n\nThe experiments with noisy data are interesting and show that ARF selects important nodes and also helps for long-range connections.\n\n\n\n**Weaknesses**\n\nThe main weakness of the paper is that the proposed adaptive receptive field (ARF) is not properly motivated by the theory in section 2. It is a good idea to have an ARF as it has many advantages, but they are not properly explained in the theoretical section. ARF could achieve long-range connections while avoiding the standard node features oversmoothing problem (different than the presented attention smoothing), but this should be better motivated.\n\n\nThe smoothness of the weights should be more clearly defined. For example, are the weights $1 / n, 2 / n, 3 / n$ smooth? They respect Proposition 1 as they all approach 0 when $n \\to \\inf$, but they could be distinguished. Different from the usage in the paper, maybe the ratio $\\alpha_{i,j} / \\alpha_{i,k}, \\forall j,k \\in N(i)$ could be used.\n\nIt is not clear why small attention weights should be avoided. Weights that decrease with the number of nodes do not necessarily result in bad representations. All the attention weights could approach 0, but they could be sufficiently distinct and also result in proper node representations. \n\nThe computational complexity of the constructor should be discussed. What is the total inference time of GRARF, taking into account the construction of the adaptive fields? What percent of the total time is spent by the constructor and evaluator?\n\n\n\n\n\n**Additional comments and questions:**\n\nFair evaluation on cora, citeseer, pubmed datasets has been shown to be difficult [A]. The community seems to be moving forward to larger datasets like OGB [B] or [C].\n\nIt would be useful to make a connection and compare to other approaches that involve adaptive receptive fields, like Liu et al., 2019.  \n\nThe weight's smoothness should have a clearly presented definition, especially to avoid confusions to the smoothness of the node features, as pointed out by the authors in footnote 3.\n\nHow important is the reward shaping for good performance?\n\n*Minor*:\nIn Eq.1 the first part represents the whole graph H, while the last term represents a single node:  h_i.\nEq. 5: u == i ?\n\n\n[A] Shchur, Oleksandr, et al. \"Pitfalls of graph neural network evaluation.\" arXiv preprint arXiv:1811.05868 (2018).\n[B] Hu, Weihua, et al. \"Open graph benchmark: Datasets for machine learning on graphs.\" arXiv preprint arXiv:2005.00687 (2020).\n[C] Dwivedi, Vijay Prakash, et al. \"Benchmarking graph neural networks.\" arXiv preprint arXiv:2003.00982 (2020).\n\n\n**Conclusion:**\n\nWhile the proposed method is sound and interesting and the paper has some good evaluations. The main problem of the paper is represented by the unclear theoretical part that is detrimental to the paper and should be fixed. In this form, I tend to give a *5: marginally below*  rating.\n\n__________________________________________________________\n**After rebuttal**\n\nI thank the authors for their responses, but I will keep my original rating of the paper. I think this paper has potential and a new submission will have a better result.\n\nSuggestion for improvements:\n\n1. As the other reviewers pointed out, the proposed method is computationally expensive. Although this is a downside, it is not really a major one, as long as the authors have a proper analysis of the complexity and of the actual inference / training time. The authors pointed out that their contribution consists of proving that the adaptive receptive fields are useful, and I agree that an efficient method is not necessary for this, but the analysis should be made.\n\n2. I think that additional ablation studies are needed. For example, the experiment in Figure 4 a) supports Proposition 1 but only on Cora that is homophilic and where the mean of the nodes is a good aggregation. The experiments with added noise are a good start. Maybe also compare GRARF with GAT with a simple strategy of selecting the edges (top k according to $e_{i,j}$, or all with $\\alpha_{i,j} > 0.5$ ).\n\n3. Improve the motivation from Section 2. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "i0fZNDFBcA", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThe authors theoretically and empirically show that soft-attention mechanism uses in GCNs suffers from over-smoothness in large neighborhoods. For addressing this shortcoming, they propose a neighborhood sampling approach called adaptive receptive fields (ARFs) which discretely select nodes among the multi-hop neighborhood and allow to efficiently explore long-distance dependencies in graphs. The authors also propose GRARF (GCN with Reinforced ARF) which learns optimal policy of constructing ARFs with reinforcement learning. For a given node, an RL agent successively expands ARF via a two-stage process. Firstly, a contact node in an intermediately-constructed ARF is selected and then a context among the direct neighbors of the contact node is added to ARF. The reward is the performance of the trained GCN on constructed ARF. Overall, the results demonstrate the effectiveness of the approach on benchmark datasets. The authors also demonstrate that the method is quite effective at handling noise in the graph compared to GCN and GAT by evaluating them on the Cora dataset with synthetically added noise.  \n\nStrengths: \n1. The proposed idea of using reinforcement learning for selecting influence neighborhood of a node in GCNs is novel. The results show the effectiveness of the method. \n2. The method is more robust to noise and is capable of capturing information from distant neighbors for learning efficient representation. \n\nWeaknesses: \n1. The scalability of the method for larger graphs is not very explicit from the given experiments.\n2. Using RL might accompany multiple challenges involved with learning policy which might restrict the applicability of the approach. \n\n\nQuestions:\n1. In Figure 4(b)-(d), it is not clear which attention weight distribution corresponds to GCN and which corresponds to the GAT model. \n2. Please explain the reason behind the vast difference in the performance of the baseline models on cora, citeseer, and pubmed datasets. For instance, GAT reported around 83% on cora, however, here it has been given as 87.8. Also, on ppi dataset, the performance changes from 97.3 to 47.29. \n\n-----\nBased on the issues pointed out by the other reviewers. I have decided to reduce my score for the paper. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "a6dpzdlBsHg", "reviewer": "AnonReviewer3", "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\nThis paper proposes to construct adaptive receptive fields for graph convolution using reinforcement learning. This strategy can address the smoothness of attention weights issue, and capture long-distance dependencies in graphs. Considering the following pros and cons comprehensively, I decide to give a recommendation of weak reject to this work.\n\n#####Pros#####\n\n(1) The studied problem is very crucial and valuable. Aggregating information from neighborhood can capture useful information as well as introduce noise sometimes. How to construct an adaptive receptive field of each node is a significant direction that deserves more investigation.\n\n(2) This work points out the issue that the soft attention weights (such as in GAT) suffer from over-smoothness in large neighborhoods. Also, the impressive experimental result in Fig. 3 can verify this to some degree. This observation is insightful and might helpful for future exploration.\n\n#####Cons#####\n\n(1) The main shortcoming of this work is the high complexity of the method. This work utilizes the reinforcement learning to training the constructor, which is expected to be very complicated. Furthermore, there does not exist the experiments about running efficiency of the proposed method, which is very necessary to demonstrate the value of the proposed approach.\n\n(2) Also, the dataset used in this paper is relatively small and some of them are shown to have data quality issue [1]. More experiments on larger datasets, such as OGB [1], should be considered.\n\n[1] Hu et al. Open graph benchmark: Datasets for machine learning on graphs.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Four knowledgeable referees lean towards rejection because of the missing detailed complexity analysis [R1,R2,R3], the choice of rather small datasets which hinders the rigorous evaluation of GNN models [R3,R4], missing state-of-the-art comparisons [R2] and ablations [R4]. The rebuttal addressed some of the concerns raised by the reviewers, in particular, clarifications request by R2, smoothness of the weights questions of R4, and the difference in performance of the baseline methods of R1. However, after discussion, the reviewers are still concerned with the missing ablations, comparisons, and complexity analysis. I agree with their assessment and therefore must reject. However, I agree with the reviewers that this is an interesting approach and encourage the authors to consider the reviewer's suggestions for future iterations of their work. 
Decision: Reject