A bi-diffusion based layer-wise sampling method for deep learning in large graphs
Authors: Yu He
Shiyang Wen
Wenjin Wu
Yan Zhang
Siran Yang
Yuan Wei
Di Zhang
Guojie  Song
Wei Lin
Liang Wang
Bo Zheng
Venue:  (2020)
Keywords: Layerwise Sampling
Graph Neural Networks
Attention Mechanism

Abstract: The Graph Convolutional Network (GCN) and its variants are powerful models for graph representation learning and have recently achieved great success on many graph-based applications. However, most of them target on shallow models (e.g. 2 layers) on relatively small graphs. Very recently, although many acceleration methods have been developed for GCNs training,
it still remains a severe challenge how to scale GCN-like models to larger graphs and deeper layers due to the over-expansion of neighborhoods across layers. In this paper, to address the above challenge, we propose a novel layer-wise sampling strategy, which samples the nodes layer by layer conditionally based on the factors of the bi-directional diffusion between layers. In this way, we potentially restrict the time complexity linear to the number of layers, and construct a mini-batch of nodes with high local bi-directional influence (correlation). Further, we apply the self-attention mechanism to flexibly learn suitable weights for the sampled nodes, which allows the model to be able to incorporate both the first-order and higher-order proximities during a single layer propagation process without extra recursive propagation or skip connection. Extensive experiments on three large benchmark graphs demonstrate the effectiveness and efficiency of the proposed model.

Under review as a conference paper at ICLR 2020
A BI-DIFFUSION BASED LAYER-WISE SAMPLING METHOD FOR DEEP LEARNING IN LARGE GRAPHS
Anonymous authors Paper under double-blind review
ABSTRACT
The Graph Convolutional Network (GCN) and its variants are powerful models for graph representation learning and have recently achieved great success on many graph-based applications. However, most of them target on shallow models (e.g. 2 layers) on relatively small graphs. Very recently, although many acceleration methods have been developed for GCNs training, still remains severe chal- lenge how to scale GCN-like models to larger graphs and deeper layers due to the over-expansion of neighborhoods across layers. In this paper, to address the above challenge, the nodes layer by layer conditionally based on the factors of the bi-directional diffusion between layers. In this way, potentially restrict the time complexity linear to the number of layers, and construct a mini-batch of nodes with high local bi-directional influence (correlation). Further, we apply the self-attention mech- anism to flexibly learn suitable weights for the sampled nodes, which allows the model be able to incorporate both the first-order and higher-order proximities during a single layer propagation process without extra recursive propagation or skip connection. Extensive experiments on three large benchmark graphs demon- strate the effectiveness and efficiency of the proposed model.
propose novel layer-wiss wise sampling strategy, which samples
INTRODUCTION
In recent years, extending deep learning approaches graph domain has attracted increasing re- search attention. One of the successful attempts is the Graph Convolutional Network (GCN) (Kipf Welling 2016), which has become a crucial tool for representation learning graph nodes. Given graph, GCN applies the connectivity structure of the graph as the convolution filter (also known as the neighborhood aggregator (Hamilton et al. (017)) to compute node representations layer by layer. At each layer, the representation of each node is obtained by mixing the features of its neigh- bors. Then, the final output representations can be used for various downstream applications. There have been many GCN- -CN-d attempts in the literature which have achieved the state-of of-the-art per- formance on many graph-based applications, such as node classification (Kipf & Welling) 2016)] Hamilton al. 2017: Veličković et al., 2017), link prediction (Zhang & Chen 2018), and recom- mender systems (Ying et al. 2018), etc.
Although numerous GCN-like models have been developed, most of them only focus shallow models (e.g. 2 layers) on relatively small graphs. In practice, it still remains a severe challenge how scale GCN-like models larger graphs and deeper layers, due the uncontrollable neighborhood expansion across layers. On the one hand, since the graph convolution (or say neighborhood aggre- gation) on each node needs to gather the features of its neighbors, and recursively the convolution computation on each of these neighbors also requires to gather the features of their own neighbors, will incur the "neighbor-explosion" problem. When training deep-layers model, the number of "neighbors" (and thus the training time) can grow exponentially with respect to the number of layers. Even with a usual mini-batch training, it will also involve a large amount of data for every batch and make the training computationally infeasible. On the other hand, the graph convolution is essentially a smoothing operation (Li et al. 2018: Xu et al. 201 8a) by mixing the features of a node and its nearby neighbors, and thus makes the representations of nodes in the same cluster similar. However, the recursively expansion of neighborhoods layer by layer will quickly cover a large por- tion of the graph, leading many distant nodes from irrelevant clusters be overly smoothed. Such

---

Under review as a conference paper at ICLR 2020
"over-smoothing" problem makes it hard for GCN-like models to maintain consistently resonable results in deep layers.
To mitigate the neighborhood expansion, some state-of-the-arr methods (e.g.. (Hamilton et al. 2017 Chen et al, 2018a| Ying et al., ) use the stochastic mini-batche training and node-wise sampling optimization, which ensure that only small fixed number of neighbors are selected by one node in each layer. While these methods significantly speed up the GCNs training on large-scale graphs, the time complexity still grows exponentially with the GCN depth even if the sampling number is small, and thus the overhead of these methods can be very large when the layers go deep. Further, Chen al.) (2018b) and Huang al. (2018) propose to accelerate the training of GCNs by using the layer-wise sampling instead of node-wise sampling, which ensures a total fixed number of nodes are sampled together by each layer instead of each node, restricting the time complexity linear to the GCN depth. However, although efficiently solving the "neighbor explosion" problem, these existing layer-wise sampling algorithms still suffer from the "over-smoothingg" issue in practice. Their constructed mini-batches potentially become too sparse to achieve high accuracy (see Section for details).
In this paper, to address the above challenges, we first show that a desirable layer-wise sampler should simultancously considers both the influence of parent nodes of upper layer on the candidate nodes of lower layer and the reverse influence of lower candidates on the upper parents, Motivated by that, we then propose a novel layer-wise sampling strategy, which samples the nodes layer by layer conditionally based on the factors of the bi-directional diffusion between layers. By sampling nodes with high bi-directional influence between neighbor layers, our layer-wise sampler tends to con- struct closely-associates mini-batch, and thus elegantly and naturally tackles both the "neighbor explosion" and "over-smoothing"" problem, as well as the sparsity issue suffered in current layerwise sampling algorithms. Furthermore, since the layer-wise sampler mixes different-hon tefpereetthhppoae neighborhoods in each single layer, we apply the self-attention mechanism as the aggregator to flexibly learn suit- able weights for different-hop neighbors during the training, which allows the model to be able to in- corporate both the first-order and higher-order proximities during single layer propagation process without extra recursive propagation or skip connection. Finally, we conduct extensive experiments on three large benchmark graphs under the inductive, supervised learning setting. The experimental results demonstrate that our proposed model consistently and considerably outperforms the compar- ative state-of-the oftte-of-theaan aht baselines and exhibit that our model can be efficiently and effectively scaled to very deep layers on very large graphs.
2 RELATED WORK
In the past few years, inspired by the convolutional neural network (CNN), which has revolution- ized various machine learning tasks with grid-like data, how to extend the convolution operation on graph-structured data has attracted increasing research attention. Among the existing graph-based convolution network models, important stream of work is built spectral graph theory (Bruna jet al. 2013). The pioneer spectral approach proposed by Bruna et al. (2013) first defines the pa- rameterized convolution operation in Fourier domain, inspired by graph Fourier transform. Later, Henaff et al. 2015) apply efficient spectral filter to realize localized filtering operation, andDeefer rard al. (0166) further speed up the graph convolution computation by fast localized filters based on Chebyshev expansion of the graph Laplacian. Recently, GCN (Kipf & Welling (0166) is proposed to simplify the aforementioned spectral methods with first-order expansion and re- prrammtttrrittoonn trick, which has achieved state-of-the-arr the--artt performance on supervised/semi soperviseddemi-suppevissed node classifi- cation task and has motivated many GCN-based variants and applications. For example, Veličkovid et al. 2017) replace the convolution operation by applying the attention mechanism (Vaswani et al. 2017) as the aggregator to capture neighbor features with adjustable trainable weights. Klicpera et al. (2018) combine PageRank with GCN to enable efficient information propagation from mul- tiple hops away. Xu et al. (2018b) borrow the idea of "skip-com "skip-connection" " (He et al. 2016) into the GCN context improve the accuracy of GCNs with more than two layers.
Although numerous GCN variants have been developed, most of them conduct the training in full batch, which limits the application of these methods only to small graphs. In order to scale GCNs baseed based algorithms have been recently proposed for efficient mini-batee training. For example, the node-wise sampling based algorithm GraphSAGE proposed by Hamilton
to large graphs, the sampling
2

---

Under review as a conference paper at ICLR 2020
et al. (017)) computes node representations by randomly sampling neighborhoods of each node and performing a specific aggregator for information smoothing. in which the neighborhood aggregation operation can be regarded as an another perspective of graph convolution. YYigg et al. (2018) enhance the sampler of GraphSAAGt by introducing an importance score to each neighbor node, and thus lead to less information loss due to the preference towards influential neighbors. Although these methods ensure that only small fixed number of neighbors are selected for each node in the next layer, they still require the recursive expansion of neighborhoods across layers, which leads the total number of support nodes (and thus the training time) exponential with the GCN depth. To further restrict the neighborhood size of deep layers, Chen et al. (2018a) propose to use the historical activations in the previous layer to avoid redundant re-evaluation and thus reduce to only two neighbors to support the computation of next layer activations. However, it requires storing all the intermediate embeddings of all the nodes in memory, leading hefty memory requirement. [Chen et al. (2018b) interpret graph convolutions as integral transforms of embedding functions and sample the nodes in each layer independently. They apply importance sampling for explicit variance reduction, and remarkably, their method leads to constant number of samples in all layers. Then, Huang et al. (2018) follow the idea of layer-wise sampling proposed in (Chen et al., (2018b) to extend to neural network to sample nodes for the lower layer conditionally based on the nodes of upper layer instead of sampling independently. However, these layerwise sampling based methods potentially build up very sparse bainib especially when the GCN layers grow deeply. In addition. Zeng al. (2019a) present a subgraph based training algorithm that is scalable with respect to GCN depth, and Chiang et al. (2019) propose to build mini-batches based on (topological) clusters of the training graph. These subgraph based methods, although empirically demonstrate the effectiveness on deep models, essentially tackle the scalability issue by dividing the original large graph into series of small graphs, which inherently results in biased estimation the full batch loss. In summary, with numerous GCN variants being developed, it still remains a question how to train these models (with very deep layers) efficiently on very large graphs.
additional sampling
NOTATIONS AND PRELIMINARIES
In this section, we first introduce some notations used throughout this paper and then explain the problem our model solves.
This paper mainly focuses undirected attributed graphs Let G E) denote the undirected graph with nodes U; E V, edges (w;, 12) E E, and n = [V] defines the numher of the nodes, m = |g] defines the number of the edges. Let A Rnxa denote the adjacency matrix of the graph with each entry Ai, equaling to 1 if there is an edge between u; and U; and 0 otherwise. Á = A In denotes the adjacency matrix with added self-loops. Also, the graph G is attributed by a feature/attribute matrix X Rx with X2 denoting the d-dimensional feature/attribute vector for node 14.
Given the undirected attributed graph, the problem we consider in this paper is representation learn- ing for graph nodes by aggregating (or propagating) their features/atrriutess. The closest work to this vein is the Graph Convolution Network (GCN) (Kipf & Welling 2016) and its variants. A GCN kind of multi-layer convolutional network, and it uses the connectivity structure of the graph as the convolution filter to perform neighborhood aggregation//ropaaation layer by layer. At each layer, the hidden representation of a node is obtained by aggregating the last hidden representations of its neighbors (and itself), followed by one or few layers of linear transformations and nonlinear activations. The final output representations can then be used for downstream tasks. For example, in node classification task, the final output representations are fed to classifier to predict node labels,
and thus the parameters of GCN can be trained in an end-to-end manner. Let h,!") e gixd") denote the hidden representation (with dimensionality d()) of node v in the I-th layer, the feed forward propagation rule of single layer in GCN is defined as follows:
1 = al Σ
VEV,1=1,2
#EN())
where (w)) is the set of neighbors of node v, and note that we always consider the node itself as its self-loop neighbor: å = カ is the symmetrically normalized adjacency matrix with self-loops, with the diagonal degree matrix D. = E,,A, A.g: W(O E (dd"=")xa") is the trainable weight matrix in the 1-th layer; a(-) is the activation function (e.g. ReLUU. Note that we use the
3

---

Under review as a conference paper at ICLR 2020
graph attributes as the initial representations, i.e. h X.. As result, both the input graph attributes and structure are "embedded" into the final output representations in the L-th layer.
Since the GCN needs recursively perform neighhorhood aggregation across layers, there is an obvious challenge for applying current GCN model with deep layers--veereepaasiio of neigh- borhoods. In practice, the "over-expansion" issue incurs two severe problems in GCN training: "neighbor explosion" and "over-smoothingg" First, considering the width of the neighborhood ex- pansion layer by layer, it will incur the neighbor explosion problem. As the representation of a node at layer is computed recursively by aggregating the representations of its neighbors at layer - 1, is easy to see that the more layers we applied, the more multi-hop neighbors we need to support the computation of the root node. The number of support nodes can grow exponentially with respect to the number of layers. Particularly for dense graphs and powerlaw graphs, the expansion of the neighborhoods for single root node will quickly involve large number of support nodes, and thus incur expensive computations and memory footprints. Second, considering the depth of the over- expansion, it will lead to the over-smoothing problem. As highlighted in (Li al., (018) and (Xu) iet al. 2018a) 8a). the graph convolution (neighborhood aggregation) in GCN is simply a special form of Laplacian smoothing, which mixes the features of node and its nearby neighbors. The smoothing operation makes the features of nodes in the same cluster similar, thus greatly easing the classifica- tion task. However, adding more layers to a GCN will make more distant "neighbors" which actually are irrelevant nodes. Even for single node, it will quickly cover large portion of the graph due to the neighborhood expansion layer by layer. As a result, the output representations with too many layers in GCN may be over-smoothed and nodes from different clusters may become indistinguishable.
be mixed,
To mitigate the above "over-expansion" issue, many sampling -based algorithms are very recently proposed to control the expansion of the neighborhoods. |Hamilton et al. (2017) firstly attempt to use nodewise sampling strategy to approximate the GCN model. Instead of the full expansion of neighborhoods for the feed forward computation of each node, the nodewise sampling strategy uniformly samples a small number of neighbors for each node at each layer. Then, the propagation rule of Eq. (T) is approximated as:
0 = o [N() (..( (E)
Σ (o)) u
V V VEV, 12,1=110 112,
(2)
where each element u E NN(w)) is uniformly sampled from the whole neighbor set N(v). Although clearly reduces the receptive field size of graph convolution and achieves competitive performance, such nodewise sampling is still computationally expensive for deep networks, because the number of sampled neighbors still grows exponentially with the number of layers. Assuming the sample size for all layers is fixed as s, the number of sampling neighbors in the l-th layer will increase to Oss'), Even with a very small s, this will also lead significant computational burden for large
FastGCN (Chen et al. 2018b) and AS-GCN (Huang et al. 2018) are another state-of-the-a sampling- algorithms, which use layerwise sampling strategy to avoid the neighborhood ex- pansion. As opposed to the nodewise method in Eq. (2) which samples a fixed-size set of neighbors (v) for each parent node e of upper layer independently. the layerwise sampling directly samples fixed number of nodes for each layer altogether, i.e., the sampling for all the parent nodes of upper layer is jointly performed only once, and the sampled nodes are shared by all upper parent nodes. Formally, let y(111) denote the set of nodes of (1-1)-th layer, which are generated by layerwise sampling to support the computations of nodes y(1 of I-th layer, and the top layer nodes V(L) are the pre-selected nodes (e.g. the stochastic mini- of nodes) whose final representations are used in downstream tasks. The propagation rule of GCN based on layerwise samlping is defined as:
[Vv D
60 = a
Σ BEVR 1)
111-1) ~ g(ulD()), 1= 1,2, L,, (3)
where ((ulV()) is defined as the probability of sampling u given all the parent nodes of upper layer (i.e. Vill), and y0111) are all the nodes of lower layer sampled according to quu D(U).. In FastGCN. (())))) is simply designed as: q(u(D(() x प Σ EaeN(w) |Najj- In AS-GCN, q(x()()) =
Eeeves (oxx)))
Evevio [N()))o(X.)) where (Xx.)) is linear function to compute the self-dependent factor based
4

---

Under review as a conference paper at ICLR 2020
on the node feature X.. Simply, FastGCN contructs each layer independently according to an identical distribution, AS-GCN builds up the network layer by layer in a top-down way, where the nodes in the lower layer are sampled conditionally based on the upper layer's.
Based on the layerwise sampling, is easy to fix the size of each layer to avoid the "neighbor explosion", the total number of nodes only grows linearly with the network depth. Nonetheless, the current layerwise sampling strategies used in FastGCN and AS-GCN still confront the "over- smoothing" problem and potentially build up very sparse mini-batchs. Formally, FastGCN and AS- GCN only sparsely subsample the potential "neighbors" during the expansion of the neighborhood across layers. As result, although the neighbor explosion problem easily solved by potentially restricting the factor of the width of expansion to I, it can also quickly reach the very deep part of the graph due to the "over expansion" of the depth layer by layer, and thus overly smooth the irrelevant nodes from distant clusters. Moreover, by only subsampling the potential neighbors in each layer without controlling the depth of "over-expansion", the above layerwise sampling strategies will contruct very sparse minibatchs in practice. As the correlations among nodes will decrease rapidly with the increasing of the depth, in very deep layers, the between-layer connectivity will be very sparse and many parent nodes of upper layer may have connected neighbors, which makes the GCN difficult to achieve high accuracy.
In the rest of this paper, we present a desirable layerwise sampling algorithm, elegantly and naturally tackling the above problems of existing layerwise samping.
PROPOSED METHOD: BLS-GAN
To mitigate the over-expansion issue in deep graph neural networks, in this section, we present novel layerwise sampling strategy, which samples the nodes layer by layer conditionally based on the factors from the bi-directional diffusion processes between layers. Next, we leverage the self- attention mechanism flexibly aggregate the sampled nodes in each layer with adaptive learnable weights, and finally propose our Bi-diffusion guided Layer-wise Sampling based Graph Attention Network (called BLS-GAN) model.
4.1 BI-DIFFUSION BASED LAYERWISE SAMPLING
As analyzed in Section 3 desirable sampling algorithm should not only control the width of neigh- borhood expansion across layers, i.c., the size of sampled nodes in each layer to avoid the "neighbor explosion", but also restrict the depth of neighborhood expansion, i.e., the distance among nodes of inter-layers to avoid the "over-smoothing" and the sampling naturally meets the first requirement, as the nodes of the lower layer are sampled as a whole. However, the current layerwise sampling strategies either contruct each layer independently according to an identical distribution (Chen et al. 2018b), or oie-sidedly sample nodes in the lower layer proportionally to the connections to the upper layer's 's (Huang et al. 2018).. Such layer samplers could not satisfy the second requirement and potentially return overly sparse minibatchs when the network is deep (Zeng al., (009b)). To address the above problems, in this paper, we present novel desirable layerwise sampling strategy, which satisfies both the two requirements.
The idea of layerwise
To control the depth of neighborhood expansion in layerwise sampling, is natural and reasonable to sample nodes with high local correlation. However, we highlight that, the connected edges, which used in current layerwise sampling algorithms, do not proportionally reflect the real correlation among nodes. When sampling nodes in the lower layer conditioned on the upper layer's, the cur- rent start-of-the-as layer sampler usually uses higher probabilities to sample nodes who have more connected edges to the parent nodes of upper layer. However, the sampled nodes with many con- nections can have weak correlation. For example, in biological and citation networks, the majority of the nodes have few connections, whereas some core nodes and hub nodes are usually connected to many other nodes. That is, such cores or hubs, although have many connected edges to the parent nodes of upper layer, do not have a strong correlation with the upper layer's, s, because there is few "influence" " of the upper parent nodes on those cores or hubs. In practice, due to the weak influence (i.e. correlation), such cores or hubs are not worthwhile candidates. Specially, if sampling them, in next layers, the sampler will quickly expand onto a very large portion the graph, where many nodes are irrelevant.
5

---

Under review as a conference paper at ICLR 2020
The bias between the correlation and connections is due to the fact that correlation (or say influ- ence) is bi-directional. The aforementioned connections to the parent nodes of upper layer can only indicate the influence from the sampling nodes of lower layer to the upper layer's, ss but not reflect the reverse influence. Therefore, a desirable layer sampler should select nodes in the lower layer conditionally based the bi-directional influences on the parent nodes of upper layer. Below describe a principled way to achieve it.
We define the "influence" (also corelation) from the graph connectivity perspective and estimate by developing the diffusion process (i.e. the random walk simulation) on the graph. Formally, Let P E R=** denote the diffusion matrix (i.e. the transition probability matrix of random walk) of the graph, we have P = D- A where A is the adjacency matrix of the graph, D is the diagonal degree matrix with Di, Ej At,- Then, given all the parent nodes in the upper layer (denoted Vt), the diffusion factor from an arbitrary node u in the lower layer to the upper nodes V is defined as:
(u, v()= = Σievo) Puçe
Σ
Pa.e-
(4)
Evey Pa.v
NEVE)
Inversely, the diffusion factor from D to the candidate node is defined as:
EsEri Pe.u
Eeevo Po.u
X u) Σievo) Evev Ps.e
(5)
[V0]
Intuitively, the diffusion factor from the candidate node of lower layer to the parent nodes of upper layer indicates the influence from the upper layer nodes to the candidate node. The larger the factor, the higher the influence of the upper layer's on the candidate. Reversely, the diffusion factor from the parent nodes of upper layer to a candidate node reflects the influence from the candidate to the upper layer's, s. and the larger the factor, the higher the influence of the candidate on the upper layer's. s. Clearly, desirable layerwise sampler should incorporate the factors the above bi-directional diffusion processes to sample nodes with high bi-directional influence on each other. Therefore, define the probability distribution of sampling a node in the lower layer given all the nodes (i) of the upper layer as:
P(up(()) 7u, DU)) A(V(), u)
(6)
Evev 7(0, V(0) A(V()
Then, according to this probability distribution, we can easily sample an arbitrary number of nodes to build up the lower layer, and the feed forward propagation between layers can be consistently computed as the Eq. (3) by updating the ((n()/() in Eq. (3) as the P(u()()) of Eq. (6).
We term the above sampling as the bi-diffusion (bi-directional diffusion) based layerwise sam- pling strategy. By sampling the nodes layer by layer according to the bi-diffusion factors between layers, the sampler tends to construct a mini-batch of nodes with high local bi-directional influ- ence/correlation, and thus naturally tackle the "over-expansion" issue across layers, in view of both the width and the depth of neighborhood expansion. The former view can speed up training of a deep-layers model by avoiding the "neighbor-exploste The latter view potentially enhances the model's 's performance by mitigating the "over-smoothing" and the "sparse- copneti-onn.ettivity..........".
4.2 SELF-ATTENTION AGGREGATOR
Although the idea of training by the layerwise sampling is applicable to many GCN variants, in this section, we leverage the self-attention mechanism to flexibly aggregate the sampled nodes in each layer with adaptive learnable weights, which allows the model be able to simultaneously exploit both the first-order and higher-order proximities during a single layer propagation process.
By applying the layer-wise sampling layer by layer, the nodes of lower layer are sampled together and the sampled nodes are shared by all parent nodes of upper layer. That is, the sampled nodes are not always the I-hop neighbors (with direct connnections) of the upper parent nodes. There- fore, the bi-diffusion based layerwise sampling proposed in Section 4.1 is essentially a bi-diffusion based mix-hop sampling approach, which samples the highly relevant nodes from both 1-hop and multi-hop neighborhoods by jointly treating the upper parent nodes whole. As result, the higher-order proximity is maintained in each single layer without extra recursive propagation or skip connection. When perform bottom-up propagations update the hidden features for the nodes of

---

Under review as a conference paper at ICLR 2020
upper layers (like Eq. (3), the updater for each node in each layer always simultaneously aggregates messages passed from both 1hhop neighborhood and multi-hop neighborhood, thus enabling more efficient layer propagation and model training. Further, considering that the proximities of different orders measure the corelation of nodes from different levels of scope, the neighbors of different hops should not be treated equivalently during the layer aggregation. However, the aggregation weight
in GCN aggregator (i.c. the term Åe,u in Eq. (3)) is strictly designed some normalization of the graph adjacency matrix, which can be only suitable for expressing the first-order proximity. In- tuitively, the aggregation weights for k-hop neighbors are supposed to be some normalization of the k-th power of the adjacency matrix, which is computationally infeasible. Therefore, to avoid the expensive computation of mixing powers of the adjacency matrix, we follow (Veličković al.) 2017) to apply the self-attention mechanism as the aggregator, which is able to flexibly learn suitable weights for different-hop nodes during the training. Concisely, we replace the aggregation weight A in Eq. (3) with specific self-attention scores, and update the propagation rule
4 = o
Σ DEV
((hh-1)) ( D -0- WW"),, y(- ~ P(u/V()), 1= 1,2, .. ,, (7)
where ani!--) )) measures the self-attention scores between the parent node v and the layer-
wise sampled node according to their hidden features in layer - 1, and is defined as:
exp(LeakyReLU(I4s (1-1) W (j())
a(h (1,
Eveya Dufe) exp(Leaky (e ( W || I (Wo))
where is the concatenation operation, W E Rd x and O E R2d x1 are trainable parameters.
Overall, given a mini-batch of nodes as the top layer and the number of layers L, we can apply the bi-diffusion based layerwise sampling (Eq. (6) to recursively construct L layers of support nodes in top-down way, and then stack I. self-attention aggregators (Eq. (7) between each two layers to perform bottom-up propagations. At each layer, the hidden representation of a node is updated by flexibly aggregating the features of its multi-hop neighbors (and itself) with trainable weights. The final output representations in the top layer are then used for downstream applications. As a result, we obtain novel deep graph neural network model, which could efficiently and effectively embed both the graph attributes and structure into the output representations. We call the proposed model as BLS-GAN (Bi-diffusion guided Layer-wise Sampling based Graph Attention Network). Finally, as an example practice, we apply the BLS-GAN for node classification in this paper, which the most popular application of graph neural network. In this setting, the final output representations of nodes are fed to a classifier to predict node labels, and the parameters of BLS-GAN are trained in an end-to-end manner by using iterative algorithms (e.g. mini-batch SGD) to minimize the following loss function:
1 Σ Colve, E( f(h(")), VI
C
DEV
where 1n(2) the final output representation of node learned by BLS-GAN, f(-) a simple single- layer feed-forward neural network classifier, L. is the classification loss (e.g., the crossing entropy) for node v to predict its ground-truth label yo.
EXPERIMENTS
In this section, we report experimental results to demonstrate the effectiveness and efficiency of our proposed BLS-GAN model. The code will be released in the camera-ready version due to the double-blind review policy.
5.1 EXPERIMENTAL SETUP
We follow the experiment setup in GraphSAGE (Hamilton al. 2017) and FastGCN (Chen et al. 2018b) to compare with the offte-of-the-ar GCN training algorithms under the inductive, supervised learning setting. We use three large graph datasets: Reddit, PPI, and Pubmed, which are publicly
7

---

Under review as a conference paper at ICLR 2020
Table 1: Statistics of the datasets used in experiments.
Dataset
Nodes
Edges
Classes
Features
Trriming/Valddatioon/ees
Reddit
232,965
11,606,919
41
602
152,410/23,699//5522
PPI
56,944
818,716
50
121
14.906/6.514/5.524
Pubmed
19,717
44,338
3
500
18,217/500/1,000
available in the aforementioned references. In the Reddit graph, a node represents a post on Reddit, and an edge is formed if the posts share common user in their comments. The node features (attributes) are the concatenation of word vectors of their title and comments. The classes are the community of the posts. In the PPI prooeinn-roteii interaction) graph, the features correspond to positional gene sets, motif gene sets and immunological signatures (Zitnik& & Leskoved 2017). The classes are gene ontology sets. In the Pubmed dataset, nodes are documents, edges citation links, and classes are research topics of documents. Node features correspond to elements of a bag- of-words representation of documents. Under the inductive setting, all three datasets are splited into three partitions sraiiing//alidaaiioneess and FastGCN. Critically, all the testing nodes (including their edges and features) remain completely unobserved during training. Under the supervised learning (node classification) setting, all labels of the training nodes are used for training. The statistic of the datasets are summarized in Table []
and such a split is coherent with that used in GraphSAGE
We compare the proposed BLS-GAN model with five state-of-thh-aar baselines, including the vanilla GCN (Kipf & Welling/ 2016) and GAT (Veličkovié et al.) 2017) models (with their mini-batched implementations), the nodewise sampling based method: GraphSAGE (Hamilton et al. 2017). and the layer-wise sampling based algorithms: FastGCN (Chen et al.) 2018b) and AS-GCN (Huang et al. 2018). As introduced in Section 3 GraphSAGE randomly samples fixed-size neighbors for each node at each layer, FastGCN contructs each layer independently according to an identical distribution, AS-GCN samples nodes of lower layer conditionally based on the upper layer's. s. Note that to make the comparisons more fair, we re-implement all the baselines based on our framework and all the codes will be released after reviw.
For all datasets, we train both our BLS-GAN and the baselines by minimizing the cross-entropy on the training nodes using the mini-batch Adam SGD optimizer with the batch size of 256 and the ini- tial learning rate of 0.005. We set the maximum of training epochs as 200 and use an early stopping strategy with a window size of 10 on the Micro-F1 scores on the validation nodes. After training, we compare BLS-GAN with baselines by evaluating the Micro-FI scores of classification/preiittoo on the test nodes. For all models, we implement them with adjustable depth (layers) of [2,3,4.5] to detailly demonstrate their performance by stacking different layers. The hidden dimensions in all layers are fixed as 256. We also equalize the sample size on all layers: the nodewise sample size for each node in GraphSAGE is fixed as 10, the layerwise sample size for each layer in our BLS- GAN and FastGCN and AS-GCN is fixed as 100. Specially, we follow GAT to employ multi-head attention to stabilize the learning process of self-attention and the head size are 4.
5.2 RESULTS
We compare our proposed BLS-GAN model with the state-of-the-arr baselines by evaluating both the effectiveness (classification Micro-F1 score) and efficiency (training time) on all the three bench- mark datasets. The results are shown in Table and Table
Table 2hoows the Micro-Fl scores for node classification using different models with different lay- ers. We can observe that the proposed BLS-GAN consistently outperforms all the of-rt-of-the-an baselines on all datasets, and particularly in deep layers (c.g. 5), BLS-GAN achieves significant gains compared to other approaches. In most cases, the deeper the layers, the greater the gains. For example, on the Reddit dataset, BLS-GAN achieves the improvements by 0.01-0.04 (relatively 1%-5%) over all the five ofart-of-the-art baselines in the setting of 2 layers, and by 0.03-0.08 (rel- atively 3%-10%) over all baselines in the setting of 5 layers. Consistently, on the PPI dataset, among different layers, we can find that (relatively 26%-35%) over GCN, by 0,005-0.0 (relatively 0.5% (%) over GAT, by 0.20-0.30 (rel- atively 26%-45%) over GraphSAGE, by 0.30-0.46 (relatively 47%-87%) over FastGCN, and by 0.21-0.24 (relatively 28%-33% over AS-GCN, Specially, it is easy see that by stacking more
improves the Micro-Fi scores by 0.20-0.25 0.25
8

---

Under review as a conference paper at ICLR 2020
Table 2: The Micro-Fl Fl scores for node classification using different models with different layers.
Dataset
#Layers
GCN
GAT
GraphSAGE
FastGCN
AS-GCN
BLS-GAN
2
0.9381
0.9356
0.9297
0.9109
0.9289
0.9507
Reddit
0.9468
0.9485
0.9386
0.9023
0.9307
0.9542
4
0.9335
0.9423
0,9312
0.8809
0.9247
0.9564
5
0.9020
0.9264
0.9185
0.8732
0.9138
0.9569
0.7130
0.8851
0.6671
0.6539
0.7325
0.9637
PPI
0.7541
0.9547
0.7191
0.6260
0.7619
0.9755
4
0.7780
0.9779
0.7789
0,5860
0.7675
0.9835
0.7407
0.9461
0.7520
0.5256
0.7408
0.9850
0.8788
0.8786
0.8765
0.8582
0.8724
0,8856
Pubmed
3
0.8854
0.8863
0.8843
0.8512
0.8815
0.8923
4
0.8714
0.8894
0.8746
0.8491
0.8755
0.8977
0.8546
0.8769
0.8718
0.8173
0.8621
0.8981
Table 3: The speedups compared with GCN on the three benchmark datasets.
Dataset
#Layers
GCN
GAT
GraphSAGE
FastGCN
AS-GCN
BLS-GAN
1.00
0.89
4.32
3.50
3.79
3.63
Reddit
3
1.00
0.90
3.16
11.08
11.67
10,26
4
1.00
0.93
2.98
34.56
30.48
28.75
5
1.00
0.92
1.53
66.88
53.36
48.91
2
1.00
0.94
1.00
0.81
0.74
0.71
PPI
3
1.00
0.97
0.76
1.98
1.62
1.53
4
1.00
0.96
0.70
9.16
7.43
6.90
1.00
0.95
0.43
31.91
25.83
22.76
2
1.00
0.86
0.75
0.75
0.67
0.67
Pubmed
1.00
0.91
0.47
1.24
1.11
1.05
1.00
0.89
0.18
2.07
1.87
1.81
5
1.00
0.87
0.07
4.21
3.85
3.62
layers, the baseline models (including the current layerwise sampling methods FastGCN and AS- GCN) can hardly maintain consistently resonable results, and their results drop significantly in deep layers. Their performances provides the possible explanations. Overall, the comparation results Table clearly demonstrate the effectiveness of our proposed BLS-GAN model and especially exhibit that our model has the elegant potential to be applied with very deep layers.
in concordance with expectations analyzed in Section which
Table 3 shows the speedups of all the comparative methods on all the three benchmark datasets by comparing with the training time per epoch of GCN (One training epoch means a complete pass of all training nodes). We can find that by using the idea of layerwise sampling, our proposed BLS- GAN model is computationally efficient with the training time growing linearly with the depth of layers. detail, on the Reddit dataset, compared with the vanilla models (GCN and GAT) and the nodewise sampling based model (GraphSAGE), our BLS-GAN can achieve about 3x-53x speedup in terms of the training time with different depths of propagation layers, and the deeper the layers, the greater the speedup. Compared with the existing layerwise sampling based models (FastGCN and AS-GCN), although the training time of our model has a slight increase, it desirable to achieve significant improvements in effectiveness with slight decrease in efficiency, especially when the model layer deep.
5.3 CASE STUDY
The proposed method BLS-GAN consists of two cores: the bi-diffusion based layer-wise sampling (abbreviated BL.S) and the learnable aggregator based graph attention mechanism (abbreviated

---

Under review as a conference paper at ICLR 2020
Table 4: The Micro-Fl scores for node classification by using the bi-diffusion based layer-wise sampling (abbreviated as BLS) and the learnable aggregator based on graph attention mechanism (abbreviated as GAN), respectively.
Dataset
Reddit
PPI
Pubmed
#Layers
BLS-GCN
AS-GAN
BLS-GCN
AS-GAN
BLS-GCN
| AS-GAN
2
0.9457
0.9384
0.8928
0.9243
0.8864
0.8825
3
0.9498
0.9434
0.9378
0.9551
0.8905
0.8866
0,9512
0.9448
0.9602
0,9489
0.8926
0.8865
5
0.9536
0.9402
0.9668
0.9027
0.8942
0,8809
as GAN). In this section, we conduct extra experiments disentangle the effects of the two parts of BLS-GAN. We implement two variants of the proposed
BLS-GCN bi-diffusion based sampling. but the constant weights of GCN instead of the attention mechanism) and AS- GAN(using the adaptive sampling of AS-GCN instead of the bi-diffusion based sampling, but the learnable weights of graph attention mechanism). The results are shown in Table
We can see that both the bi-diffusion based sampling and the graph attention mechanism can improve the performance of graph neural networks. For the bi-diffusion based sampling, we can observe that BLS- could achieve significant gains compared to all the baselines on all the datasets, particularly if the layers go deeply. In most cases, the deeper the layers, the greater the gains. For example, compared with the Micro-F1 scores of all the five baselines shown in Table 2). BLS-GCN achieves the improvements by about 1 1%-7% with the setting of layers, and about 5% with the setting of 5 layers. The bi-diffusion based sampling strategy has the elegant potential to be applied with very deep layers. For the graph attention mechanism, we can see that compared with other approaches, AS-GAN can only achieve slight improvements on the Reddit dataset and Pubmed dataset, but can achieve significant gains on the PPI dataset. The results indicate that the attention mechanism obviously helpful for the embedding learning but the effect may depend on the peculiarity of target dataset. Nonetheless, we can find that the graph attention mechanism is desirable because can consistently alleviate the decline of results deep layers on all the three datasets.
the Reddit dataset (as
6 CONCLUSION
In this paper, we first present a novel "bi-diffusion" based layerwise sampling strategy. Distinguish- ing from existing layerwise sampling algorithms, we sample the nodes layer by layer conditionally based the factors of the bi-directional diffusion between layers, considering both the influence of parent nodes of upper layer on the candidate nodes of lower layer and the reverse influence of lower candidates on the upper parents. As result, the sampler tends construct mini-batch of nodes with high local bi-directional influence/correlation and thus elegantly and naturally mit- igates both the "neighbor explosion" and "over-smoothing" problem, as well the sparsity issue of current layerwise sampling algorithms. After sampling, we also apply the self-attention mecha- nism as the aggregator flexibly learn suitable weights for different-hop nodes during the training, which allows the model to be able to simultaneously exploit both the first-order proximity and the higher-order proximity during a single layer propagation process. Finally, we conduct extensive experiments three large graphs and the results demonstrate the superiority of our model.
REFERENCES
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks on graphs. arXiv preprint 1312 2013.
Jianfei Chen, Jun Zhu, and Le Song. Stochastic training of graph convolutional networks with variance reduc- tion. In JCML, pp. 941-949, 2018a.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling. arXiv preprint arXiv:1801. 10247, 2018b.
Wei-Lin Chiang, Xuanqing Liu, Si Si. Yang Li, Samy Bengio, and Cho-Jui Hsieh. Cluster-gen gen: An efficient algorithm for training deep and large graph convolutional networks. In KDD, pp. 257-266, 2019.
10

---

Under review as a conference paper at ICLR 2020
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks graphs with fast localized spectral filtering In NewrIPS, pp. 3844 3852, 2016.
Will Hamilton, Zhitao Ying, and Jure Leskovee. Inductive representation learning on large graphs. In NewrIPS, pp. 1024-1034, 2017.
Kaiming He. Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In CVPR, pp. 770-778, 2016.
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured data, arXiv preprint arXiv:/506.05166 2015.
Wenbing Huang. Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph represen- lation learning. In NeurlPS, pp. 4558-4567, 2018.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. arXiv preprint 16X.:: 2016.
Johannes Klicpera, Aleksandar Bojchevski, and Stephan Günnemann. Personalized embedding propagation: Combining neural networks on graphs with personalized pagerank. arXiv preprint arXiv: 1eXiv:1810.059900 2018.
Qimai Li, Zhichao Han, and Xiao-Ming Wu. Deeper insights into graph convolutional networks for semi- supervised learning. In AAAI, pp. 1538-3545. 2018.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention all you need. In NeurlPS, pp. 5998-6008, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint 1rXiv:1710.10900 2017.
Keyulu Xu. Chengtao Li. Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning graphs with jumping knowledge networks. In ICML, pp. 3449-5458, 2018a.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. arXiv preprint wxXiv//80.003522 2018b.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William Hamilton, and Jure Leskovee, Graph convolutional neural networks for web-scale recommender systems. In KDD, pp. 974-983. ACM, 2018.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava. Rajgopal Kannan, and Viktor K. Prasanna. Accurate, efficient and scalable graph embedding. In IPDPS, pp. 462 471, 2019a.
Hanqing Zeng, Hongkuan Zhou, Ajitesh Srivastava, Raigopal Kannan, and Viktor K. Prasanna. Graphsaint: Graph sampling based inductive learning method. arXiv preprint arXiv:1907.04931, 2019b.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In NewrIPS, pp. 5175-5175, 2018.
Marinka Zitmik Jure Leskovee. Predicting multicellular function through multi multi-layer tissue networks, Bioin- formatics, 33(14)) (3(14)1190-ii10 2017.


Reviews:
[{"review_id": "HyekiqqfiH", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "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 aims at improving the computational efficiency of GCNs to effectively capture information from the larger multi-hop neighborhood. Conventionally, GCNs use information from all the neighbors up to a certain depth; in which case, with consideration of each further hop, the neighborhood size increases exponentially. To avoid the exponentially increasing memory and computational footprints of GCNs as a result of an exponential neighborhood expansion, this paper proposes a (hop) layer-wise sampling procedure that reduces the complexity to a linear factor. The sampling of nodes at a layer, ‘l’ is based on the transmission probabilities of the nodes at layer ‘l’ and their immediate neighbors sampled earlier in layer ‘l+1’ from both directions of diffusion. The proposed model is based on Graph ATtention Network (GAT) which is adopted here to aggregates neighborhood information only over the nodes sampled with their bi-diffusion sampler. \n\nStrengths of the paper: The paper intuitively suggests that some of the popular sampling-based scaling approaches for GCN may not be powerful enough as they don’t consider bi-directional influences. \n\nWeaknesses of this paper:\n- Novelty: The idea is incremental. The paper is similar to the layer-wise sampling model, AS-GCN where instead of the base GCN model this paper uses GAT coupled with its proposed bi-diffusion sampler. \n- Experimental results: \n    - (a) Inconsistent baseline results: The performance of baselines reported here on standard train/test/val splits are significantly lower than the ones reported in the original papers. For ex: with FastGCN the original papers report 0.88 and 0.937 on PPI and Reddit which is ~0.03 more than what is reported here. With the case of AS-GCN, the original performance scores are superior to the proposed model in the paper, however here they are reported ~0.04 scores lower. Since the codes for all these baselines are available, it is only fair to use the original implementation; if not, it is important to replicate the original results before using a different implementation. \n    - (b) Variance and statistical significance results are missing\n    - (c) Cluster-GCN though discussed, an experimental comparison with it is missing. Reported results from Cluster-GCN paper on Reddit and PPI suggests a superior performance over BLS-GAT. \n    - (d) BLS-GCN missing. This would be a fair comparison to FastGCN and AS-GCN. \n    - (e) Experimental comparison with Jumping Neural network (Xu et al) is missing to understand how the proposed solution improves over existing solutions for over-smoothing. It would be helpful to even couple it with Fast-GCN/AS-GCN sampler to better understand the benefits of this paper. \n- Writing:\n    - The paper is not well written. Though there are only minor grammatical mistakes, multiple sections of the paper are not clear and are hard to read because of complex sentences and long paragraphs. \n    - Some of the terminologies used are not clearly described and are not explained prior to the usage. Some of them are neighbor-explosion, over-expansion, the width of neighborhood expansion, local correlations, etc, In some places, over-expansion is used to refer only neighbourhood explosion or only over-smoothing and both. It will be comprehensive if it is grounded. \n    - Numerous claims/ideas put forth in this paper are abstract and intuitive. The intuitions should be backed with proper support. Some of the major concerns are:-\n        - (a) proof/arguments to show that layer-wise sampling may lead to sparse mini-batches and how does that in-turn impact over-smoothing \n        - (b) how does the proposed model avoid over-smoothing?\n        - (c) why sub-graph methods are not effective ? .. etc\n    - It is true that using a fixed neighborhood weightage function as with GCNs may not be optimal. However, the discussion made on GCN and its lack of an appropriate normalization/ neighbourhood weightage function is incorrect. GCNs aggregate information from further neighborhoods according to the respective higher-order diffusion laplacian matrix entries. You can see that by simply removing the nonlinearity+weights and recursively expanding the GCN equation. \n- Other comments:\n    - Provide the complexity of the proposed model (GCN + sampler) and compare it with other sampling approaches. \n    - The connectivity structure + signal on the nodes of the graphs is the data that is being convolved and they are not the filters. The weights being learned are the filters. \n    - In Eqn: 2, I believe you are providing an equation for GS-GCN. In which case the fraction should be N(v)+1/ (N_s(V)+1) to match the original model/implementation for GraphSAGE (GS) paper. \n    - I think the summation in the denominator for AS-GCN following Eqn: 3 should run over V instead of V_l.\n    - It will be helpful to run the model on directed datasets to see improved benefits of bi-diffusion sampling. \n    - Need more discussion about AS-GCN, Cluster-GCN and Jumping Neural networks (Xu 2018b)\n   ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "H1eTO6VRYS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose a sampling method for graph neural networks which is applicable to very large graphs (where not all nodes can be kept in memory at the same time). The method uses the transition probabilities of a random walk to construct a sampling probability of the nodes in the lower layer given the nodes in the upper layer. Since this samples nodes which can be one or multiple hops away, an attention mechanism is used to weight updates from connected nodes. Experiments show that this method is promising.\n\nIn its current state I would be inclined to reject this paper, but I could be convinced otherwise. The idea, although relatively straightforward, seems powerful and the experiments seem to support it. My main concern is that paper is not well written. It contains long meandering paragraphs (e.g., all of section 2 is a single paragraph) with high-level intuitions and ill-defined terms, making it hard to read. Similarly, results are badly presented. For example, table 3 should probably be given as relative speedups with the best results bold-faced rather than a long table with numbers. Illustrations would also be very helpful to provide an intuition about formulas 4, 5, and 6. Moreover, a simple ablation study is necessary (e.g., using bi-diffusion based sampling, but using constant weights instead of the attention mechanism, or vice-versa, using the attention mechanism with other types of sampling). It is currently impossible to disentangle the effects of the two parts of BLS-GAN.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJezS00aYH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 was an interesting read. The idea of this paper is to challenge the use of Laplacian matrix in GCN. Indeed, typical GCNs use the same adjacency matrix across different layers. In particular, this typically leads in Euclidean case to learning isotropic filters (because the euclidean Laplacian is isotropic). Consequently, such filters have no selectivity at all.(in the Euclidean case, that could correspond to the selectivity to orientations - no selectivity would lead to a difference of Gaussians) Furthermore, for non-sparse graphs, computing the iterations of the Laplacian matrix can require a significant computational power.\n\nIn order to tackle this problem, the authors introduced a diffusion factor to sample a set of nodes to build some GCN filters with finite support. At a given layer, the diffusion factors is based on the interaction with other layers of the GCN. Then, a layer-wise attention mechanism that will allow to weight the graph connectivity of the sampled nodes is used, which is supervisedly learned. Each numerical experiments lead to a significantly better accuracy, while the method trains in reasonable time. This is thus numerically convincing. Furthermore, this method is, to my knowledge, new.\n\nThe paper is clearly written, the numerical experiments are convincing and the authors address a difficult problem with a simple method: I'm leaning toward an \"Accept\".\n\nMinor: \n- Tables 2/3 are hard to read.\n- The paper is 10 pages long, yet this was an interesting read.\n\nPost-discussion:\nThe other reviewers have made some good point, and thus I decided to lower my score. I still find the paper address an interesting problem.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper addresses the challenge of time complexity in aggregating neighbourhood information in GCNs. As we aggregate information from larger hops (deeper neighbourhoods) the number of nodes can increases exponentially thereby increasing time complexity. To overcome this the authors propose a sampling method which samples nodes layer by layer based on bidirectional diffusion between layers. They demonstrate the effectiveness of their approach on 3 large benchmarks.

While the ideas presented in the paper were interesting the reviewers raised some concerns which I have summarised fellow:

1) Novelty: The reviewers felt that the techniques presented were not very novel and is very similar to one existing work as pointed out by R4
2) Writing: The writing needs to be improved. The authors have already made an attempt towards this but it could be improved further
3) Comparisons with baselines: R4 has raised some concerns  the settings/configurations used for the baseline methods. In particular, the results for the baseline methods are lower than those reported in the original papers. I have read the author's rebuttal for this but I am not completely convinced about it. I would suggest that the authors address this issue in subsequent submissions

Based on the above reasons I recommend that the paper cannot be accepted. 

 
Decision: Reject