Diagonal Graph Convolutional Networks with Adaptive Neighborhood Aggregation
Authors: Jie Zhang
Yuxiao Dong
Jie Tang
Venue:  (2020)
Keywords: data mining
graph convolutional networks

Abstract: Graph convolutional networks (GCNs) and their variants have generalized deep learning methods into non-Euclidean graph data, bringing a substantial improvement on many graph mining tasks. In this paper, we revisit the mathematical foundation of GCNs and study how to extend their representation capacity. We discover that their performance can be improved with an adaptive neighborhood aggregation step. The core idea is to adaptively scale the output signal for each node and automatically train a suitable nonlinear encoder for the input signal. In this work, we present a new method named Diagonal Graph Convolutional Networks (DiagGCN) based on this idea. Importantly, one of the adaptive aggregation techniques—the permutations of diagonal matrices—used in DiagGCN offers a flexible framework to design GCNs and in fact, some of the most expressive GCNs, e.g., the graph attention network, can be reformulated as a particular instance of our model. Standard experiments on open graph benchmarks show that our proposed framework can consistently improve the graph classification accuracy when compared to state-of-the-art baselines.

Under review as a conference paper at ICLR 2020
DIAGONAL GRAPH CONVOLUTIONAL NETWORKS WITH ADAPTIVE NEIGHBORHOOD AGGREGATION
Anonymous authors
Paper under double-blind review
ABSTRACT
Graph convolutional networks (GCNs) and their variants have generalized deep learning methods into non-Euclidean graph data, bringing a substantial improve- ment on many graph mining tasks. In this paper, we revisit the mathematical foundation of GCNs and study how to extend their representation capacity. We discover that their performance can be improved with an adaptive neighborhood aggregation step. The core idea is to adaptively scale the output signal for each node and automatically train a suitable nonlinear encoder for the input signal. In this work, we present a new method named Diagonal Graph Convolutional Networks (DiagGCN) based on this idea. Importantly, one of the adaptive ag- gregation techniques- the permutations of diagonal matrices- in DiagGCN offers a flexible framework to design GCNs and in fact, some of the most expres- sive GCNs, e.g., the graph attention network, can be reformulated as a particular instance of our model. Standard experiments on open graph benchmarks show that our proposed framework can consistently improve the graph classification ac- curacy when compared to state-of-the-art baselines.
INTRODUCTION
The past decade has witnessed the remarkable success of deep neural networks across different domains, ranging from computer vision (Krizhevsky et al.) 2012 He et al. 2016). to speech recog- nition Hamdel et al., 2014). natural language processing (Gehring et al. 2017). These breakthroughs have provoked the interest to extend neural operations from linear or spatial domains to arbitrary graph structures, e.g., social networks, gene-protein networks, and knowledge graphs.
One challenge in learning with graph-structured data is how to represent each node or subgraph in neural networks. This is challenging, as graph data lies in the non-Euclidean space with com- plex structures and random size, making it infeasible to directly apply traditional neural network algorithms (Hamilton et al., 2017; Kipf & Welling, 2016). Recently, there have been attempts to generalize neural networks for handling graph-structured data. For example, graph neural networks (GNNs) are introduced as recursive neural networks in which node features are propagated itera- tively until equilibrium (Gori et al. 2005 Scarselli et al. 2009).
More recently, several studies show that it is natural for convolutional neural networks (CNNs) to model graph data structure by defining spatial localized convolutional filters over graph Laplacian spectral space (Bruna et al. [2013] Henaff et al. 2015 DDefferaard et al. (0166) or more directly, over graph neighborhoods (Duvenaud al.) 2015: Niepert al.] Monti et al. 2017). These techniques, named as graph convolutional networks (GCNs) (Kipf & Welling 2016), enable deep neural networks to effectively capture graph topology and properties. Over the past three years, various GCN based models, such as GraphSAGE (Hamilton et al.) 2017). FastGCN (Chen et al.) 2018), and GAT (Veliekovic al. 2018), have been rapidly developed, offering promising results for important graph mining tasks, such as, node classification and link prediction.
In theory, GCNs can be considered as simplification of the traditional graph spectral methods (Kipf & Welling 2016). The common strategy is to model node's 's neighborhood as the receptive field and then define the "graph convolution layer" as mean pooling aggregation followed by nonlin- earity encoder. Existing GCNs stack multiple layers and learn node representations by recursively aggregating information from neighbors, and the analysis of their representational capacity can be found in recent study et al. 2019). Essentially, the recursive convolutional aggregation process

---

Under review as a conference paper at ICLR 2020
in GCNs, or the Neural Message Passing framework (Gilmer al., 2017), is also closely related to the Weisfeiler-Lcman (WL) graph isomorphism test (Weisfeiler & Lehman 1968).
Though GCNs have been extensively explored, how to better capture the graph structures through convolutions is still largely an open question. Particularly, the neighborhood aggregation step in GCNs can be seen as the diffusion process in real-world networks (Gilmer al., 2017), in which different nodes play different roles in the propagation. For example, for information diffusion in social networks, opinion leaders (Granovetter 1973) are more likely expose information asso- ciated communities and structural holes (Burt, 2009) can spread information across different groups. However, the neighborhood aggregation step most existing GCNs considers neither the different structural importance of nodes within each step nor the dynamics of node importance across differ- ent propagation steps (Kipf & Welling, 2016 Hamilton et al. 2017 Chen et al., 2018).
In light of this limitation, we propose an adaptive neighborhood aggregation strategy to model and aggregate the dynamics of node importance. The adaptive neighborhood aggregation step consists of two coupled operations: node adaptive rescaling and node adaptive encoder. The idea of node adaptive rescaling is to adaptively learn each node's importance and use it to automatically rescale the output signal of the original graph convolutional operator; In addition to this customized rescal- ing, each node can also adaptively choose its encoder function according to its importance, forming the concept of node adaptive encoder. With these two techniques in neighborhood aggregation, present the diagonal graph convolutional networks (DiagGiNN, which is able to dynamically depict and model nodes' importance in GCNs.
Importantly, there are several advantages of the proposed DiagGCN model. First, efficiency wise, the adaptive rescaling is achieved by simple diagonal matrix operation, making DiagGCN's com- plexity the same as the sparse version of GCNs, i.e., linear with the network volume. In addition, the rescaling step is also parallelizable across all nodes in the graph. Second, it naturally supports both transductive and inductive learning, meaning that the model can generalize inference to unseen nodes. Third, DiagGCN can be connected with graph attention with different mechanisms, includ- ing node attention, (multi-hop) edge attention, and path attention, providing a new perspective to understand graph attention. This flexible framework potentially offers a principled way to automat- ically choose good attention scheme, reasonable permutation diagonal matrices, and adaptive encoders (i.e., AutoML for graph convolution/attentionn) Specifi- cally, we show the GAT model (Velickovic et al. 2018) can be reformulated special case of the proposed DiagGCN model with edge attention. Finally, our extensive experiments on several graph benchmark datasets of different types, including Cora, Citeseer, Pubmed citation networks, and the protein-protein interaction network (PPI) show that the proposed framework consistently achieves performance superiority over existing state-of-art GCN based baselines.
the adjacency matrix, rescaling
2 DEFINITIONS AND PRELIMINARIES
Let G = EV,E, denote graph, where V is set of [V nodes, E is set of [E] edges between nodes, and X E Ra is a feature matrix recording d features associated with each node. Further let A E (0, 1 | denote the adjacency matrix of the graph G, with element Aij > indicating node v E V has a link to üj E V.
Our node representation framework is built upon graph convolutional networks. Here, we refer to the definition of graph convolution in spectral methods and it can be fast approximated by the multi- layer graph convolution networks (GCNs) (Kipf & Welling 2016) with the following layer-wise propagation rule:
H'=o
where A カー is the normalized adjacency matrix, À = A + I, is the adjacency matrix with augmented self-connections, I, is the identity matrix, D is the diagonal degree matrix with D = E, A.j. and W is a layer-specific learnable weight matrix. Function (.) denotes nonlinear activation function. H E RTxD is the matrix of activations, or the D-dimensional hidden node representation in the corresponding layer with (0)) = X.
2

---

Under review as a conference paper at ICLR 2020
3 THE DIAGONAL GRAPH CONVOLUTIONAL NETWORKS
In observation of different importance nodes in real network propagation processes, we present new graph convolution neural network framework (DiagGCN) with an adaptive neighborhood ag- gregation rule. The rule is coupled with the node adaptive information rescaling and encoder, where every node can process the graph information distinctly. We also show that the information pro- cessing capabilities of different nodes in different propagation steps can be formally implemented with series of diagonal matrices. Further, sophisticated propagation models (e.g.. the graph atten- tion networks with node attention, edge attention, and path attention) can also be formulated as the permutations the adjacency matrix and diagonal matrices the DiagGCN model.
3.1 BASIC IDEA
In general, our proposed model, DiagGGN, where Diag stands for diagonal matrix, mainly stacked by the following building block:
In each layer, compared with the original GCNs, we only add a diagonal matrix P and diagonal matrix Q to the left and right sides of the normalized adjacency matrix A. respectively. Importantly all P... Qui and the node- wiie activation function σ; are adaptively adjusted according to the input information on node and their concrete forms will be introduced in Sections 3.2 and 3.3
Intuition. Complex propagation diffusion processes over a network are driven by the diversity of nodes' status and influence (Kempe et al. 2003). Nodes play different roles and process the input information signal in different ways. For example, the structural hole nodes may amplify the information across different groups of nodes in social contagion (Burt 2009), and opinion leader nodes are more likely to have a broad spread of information to the public, thus may amplify most kinds of their information (Katz 1957).
However, in most existing GCN models (Kipf & Welling 2016; Hamilton al. 2017; Chen et al., 2018), the neighborhood aggregation step can be considered as a simple diffusion process over net- works, by ignoring the difference between nodes. To this end, we propose to bridge the gap between GCNs' simple neighborhood aggregation and real-world network diffusion. The proposed Diag- GCN model realizes different ways of processing information different nodes through the node adaptive rescaling factor and encoder functions. In other words, each node has an adaptive infor- mation gate, which is also simpler than sophisticated GCN models with parameterized adjacency matrices, such as MoNet (Monti et al.J (2017) and GAT (Velickovic et al. 2018). Furthermore, the permutations of the adjacency matrix and diagonal matrices DiagGCN offer general and flexible framework to design powerful GCNs.
Computationally, DiagGCN adds the diagonal matrices to the original GCN architecture, thus the computational complexity is also linear with the volume of the network, which is the same as the sparse version of GCNs. Meanwhile, the computation of node adaptive rescaling factors can be parallelized across all nodes.
3.2 NODE ADAPTIVE RESCALING
In Eq. we use the diagonal matrix Q to rescale the rows of the signal HW from the left. In particular, the signal (HW); ); on node i is rescaled by the factor Qu adaptively adjusted by node i.
Figure I illustrates the rescaling process. Basically, we use learnable vector š1 to denote the current network state, and the importance of node is the dot product similarity of its signal (HW); and the network state ø1, that is,
Tv (HW):
(3)
and the rescaling factor is the sigmoid function (or other monotonic like softplus and exponential function) of the node importance, i.e.,
Q2 = sigmoid(r.)
Dropout mechanism is also applied on Qn randomly removing the neighbor node in the aggre- gation step when training. After the rescaling of Q and the propagation of Å, the signal of node
3

---

Under review as a conference paper at ICLR 2020
network state
network state
information from / to
$
f of (HW),
n $ (PAQHH))
other nodes
qo = otj))
xx)) = fx(ln))
rescale
convolution
renormalize
(HW) (QHW),
(AQHW);
(PAQHW);
Hi of (P (PAQHW);
node
node i
Figure 1: The DiagGCN model. The signal propagation from source node to the target neighbor i involves j's rescaling function according to its importance, i's convolutional operation which sums over the signals in its neighborhood and again rescales (renormalizes) the resulting signal, and finally i choosing an encoder according to its current importance.
i is transformed as (ÅQHW); We then use the diagonal matrix P, which defined below, to renormalize the signals, i.e.,
Ps
(5)
AnJ Note that P can also have the same rescaling form as Q. We will show later how different definitions of P can be characterized various graph attention mechanisms.
3.3 NODE ADAPTIVE ENCODER
At present, the signal node is transformed as (PÂQHW);. Similarly, we use a new learnable vector 52 to represent the new state of the whole network, and the network importance of node can be then updated as,
A (PÂQHW);
82
Different from previous GCNs (Bruna et al. 2013 Henaff et al. 2015 Defferrard et al. 2016 Kipi & Welling/ 2016, Velickovic et al., 2018), we assume that each node can even choose the encoder according to their importance in the network, that is,
x > 0
(x) s( 1) . 50
where node importance rescales the activation in the negative axis. The idea is similar the param- eterized ReLu (pReLu) function (He et al.] (2015). The difference between pReLu and our setting that pReLu is shared by the input while control factor is adaptively adjusted according the node's 's importance, which enables the encoder to be node-wise operation.
3.4 MODEL ENIIACEMEETSS
We now introduce several possible improvements to DiagGCN.
Multi-head Propagation Mechanism. For i's convolutional operation, it first sums over the signals in its neighborhood, and then rescales (renormalizes) the resulting signal adaptively, and finally chooses an encoder based on its current network importance. Since nodes may have different importance under various situations, we can leverage the multi-head mechanism to further improve the modeling capacity, formally,
H = || of (k) (P(K) AQ(A) HW()))
(8)
4

---

Under review as a conference paper at ICLR 2020
where || is the concatenation operation, p()), Q(h,, and (()) are the corresponding matrices in the k-th head of the propagation mechanism.
Multiple-hop Variants. The propagation layer (Eq. 2 can be generalized to the k-hop situation with small modifications, i.e.,
(9) Compared with Eq. Eq. 9 exxands the receptive field to k-hop neighborhood. Compared with stacking 1-hop propagation layer & times, Eq. only considers the network importance of the start node and the end node
propagation path, and omits the intermediates.
We will show later that, when the diagonal matrix P rescales signals in the normalization way. Eq. 9 functions as k-hop edge attention mechanism; when the rescaling function of the immediate nodes along the path between two nodes is considered, Eq. functions as k-step path attention mechanism.
To summarize, DiagGCN is a flexible framework as the propagation rule can be defined as arbitrary permutations of the adjacency matrices and diagonal matrices. The elements in the diagonal matrices are defined similarly as Eq. + rescaling the information signal, or Eq. [] renormalizing the signal to avoid information vanishing or explosion.
3.5 CONNECTION TO GRAPHI ATTENTION
Here we discuss DiagGCN's s connection with graph attention (e.g., GAT) and show that applying the attention mechanism nodes, edges and even paths can be regarded as special matrix permutation case in our DiagGCN model.
Note that when Q and A process signals for different times and P normalizes signals in different range, the model can function as node, edge, and path attention mechanisms. For narration conve- nience, we temporarily denote the mathematical expression between P' and H S. For example, Eq. can be rewritten as H; ((((S)W) We also denote an all-one vector as I, the diagonal element of P and Q forms the vector p and respectively. The division in this subsection is an element-wise operation.
Node Attention. When P normalizes the output signals over the global node set, the propagation mechanism functions as the node attention mechanism. S and p are expressed below,
1
S == p. = हां
(10)
Edge Attention. When P normalizes the output signals over its neighbors, the propagation mecha- nism functions as edge attention, i.e.,
S A= Ø= Si
(11)
With this, we show that the GAT model (Velickovic et al., 2018) can be considered as special implementation of edge attention in our model. Note that the coefficient of edge attention in GAT can be rewritten as
LeakyReLU exp
(HH + + Hwi,)
Oij ELEN, exp
(12)
LeakyReLU 56 Wh, $ Whe
Since LeakyReLU is monotonic and piece- piece-wise linear, the effect of 5y Wh, can be roughly reduced. Thus GAT is approximately our edge attention instance without the adaptive activation encoder, with
Qj exp(r,) = exp(=f' W Wh;). ). In other words, GAT implicitly considers the network importance and can be reformulated our diagonal matrix form, and the edge attention transformed as node- wise rescaling. In this sense. GAT can be considered as special case of DiagGCN with edge attention, demonstrating the generalization flexibility of the proposed model.
k-hop Edge Attention. When P normalizes the output signals over its k-hop neighbors, the propa- gation mechanism functions as the k-hop edge attention mechanism,
== A*Q i
(13)
ST
5

---

Under review as a conference paper at ICLR 2020
Table 1: Dataset Statistics
Cora
Citeseer
Pubmed
PPI
Task
Transductive
Transductive 3,327 graph)
Transductive
Inductive
Nodes
2,708 (1 graph)
19,717 (1 graph)
56,944 (24 graphs)
Edges
5,429
4,732
44,338
818,716 121 (multilabel)
Classes
7
6
3
Features
1,433
3,703
500
50
Traning Nodes
140
120
60
44,906 (20 graphs) 6,514 (2 graphs)
Validation Nodes
500
500
500
Test Nodes
1,000
1,000
1,000
5,524 (2 graphs)
Label Rate
0.052
0.036
0.003
0.789
k-hop Path Attention. When P normalizes the output signals which have been rescaled and convo- luted multiple times by the nodes along the path, the propagation mechanism functions the path attention mechanism. The k-step path attention mechanism is expressed in our framework below,
S = AQ
p
(14)
Si
After normalization of P. the signal (PSHW); of node is fed into our node-wise adaptive encoder d;- The k-hop edge attention and path attention mechanisms are generalizations of Eq.
4 EXPERIMENTS
Hamilton et al., 2017) to conduct both the transductive learning and inductive learning experiments on open bench- mark datasets and baselines. The experimental results suggest the strong expressive power of the simple DiagGCN framework.
We follow the common procedure /Velickovic et al. 2018 Kipf & Welling 2016:
4.1 EXPERIMENTAL SETUP
Benchmark Datasets. We conduct the transductive experiments three benchmark citation net- works: Cora, Citeseer, and Pubmed, and the inductive experiments on the PPI (protein-protein in- teraction) dataset. T consist of papers as nodes and citation links as directed edges. Each node has human annotated topic as the corresponding label and cantent-based features. The semi-supervised learning task these citation networks to predict the topic of each paper, given the content features and the ci- tation relationships other papers. For fair comparison, we follow exactly the same data splits as Yang et al.) (2016). Kipf & Welling) (2016), and Velickovic et al.) (2018), with 20 nodes per class for training, 500 overall nodes for validation, and 1000 nodes for evaluation. The Protein- -rotein Interaction dataset (PPI), as processed and described by Hamilton et al. (2017), consists of 24 dis- joint subgraphs, each corresponding to a different human tissue. 20 those subgraphs are used for training. 2 for validation, and 2 for testing, as partitioned by Hamilton et al. (2017).
the dataset statistics. The Cora, Citeseer, & Pubmed datasets
Baselines. For transductive experiments, We compare against both traditional methods without graph convolutions as well as state-of-the-art graph convolution baselines. The non-GCN base- lines include Multilayer Perceptron (MLP), manifold regularization (ManiReg) (Belkin et al., 2006). semi-supervised embedding (SemiEmb) (Weston al.) 2012), label propagation (LP) (Zhu al.
2003 DeepWalk (Perozzi et al.) 2014). Iterative Classification Algorithm (ICA) (Lu & Getoor
2003 and Planetoid (Yang et al. 2016).
We consider the following graph convolution networks as strong baselines: Chebyshev (Deffer- rard et al., (0166) designs fast localized convolutional filters on graph via Chebyshev polynomial expansion. GCN (Kipf & Welling 2016) uses efficient layer-wise propagation rule that is based on a first-order approximation of spectral convolutions on graphs. MoNet (Monti et al. 2017) parametrizes the edge weight in graph and defines the convolution weighted sum in neighbor- hood. DPFCNN (Monti et al.] 2018) generalizes MoNet and defines the convolution operations both on the graph and its dual graph. GAT (Velickovic al. 2018 uses self-attention mecha-

---

Under review as a conference paper at ICLR 2020
Table 3: Summary of classification results
Table 2: Summary of classification accuracy (transductive learning) (%)
terms F1 (inductive learning) (%)
Category
Method
Cora
Citeseer
Pubmed
Non-GCN Methods
MLP
55.1
46.5
71.4
Method
PP1
ManiReg
59.5
60.1
70.7
SemiEmb
59.0
59.6
71.1
Random
39.6
I.P
68.0
45.3
63.0
MLP
42.2
DeepWalk
67.2
43.2
65.3
GraphSAGB-GOr
50.0
ICA
75.1
69.1
73.9
GraphSAGF-
59.8
Planctoid
75.7
64.7
77.2
GraphS AGE-LSTM
61.2
GraphS SaatSSAGE-poool
Chebyshev
81.2
69.8
74.4
GraphSAGF
76.8
GCN
81.5
70.3
79.0
GAT
97.3 +0.2
MoNet
81.7+0.5
78.8+0.3
Graph Convolution
DPFCNN
83.3:0.55
72.6+0.8
DiagGCN (Rescaling alone)
98.410.2
GAT
83.0.10.7
7..51.07
79.0:10.3
DiagGCN (Fncoddr alone)
97.2++0.2
GAT-16"
83.3:0.66
72.4=0.7
78.8+0.3
DiagGCN (1/2)
98,420.22
DiagGCN (1/4)
97,910.33
DiagGCN (Rescaling alone)
83.5:0.6
72.940.7
79.1+0.33
DiagGCN (1/8)
97.4+0.33
DiagGCN (Encoder alone)
83.5.10.6
7..91.088
79.11:0.4
DiagGCN
98.5 +0.1
DiagGCN (1/2)
83.6++0.7
72.9=0.7
79.0+00.5
DiagGCN (1/4)
83.3.0.77
72.5+0.9
78.910.5
p-value (DiagGCN GAT)
2e-12
DiagGCN (1/8)
82.4++0.9
1.2
78.9+-0.6
DiagGCN
83.6:10.6
73,2=00.6
79.1=0.3
p-value (DiagGCN GAT-16")
5e-4
1c-15
3e-11
nism to parametrize the edge weight and do the convolution via the weighted sum neighborhood. Finally, GAT-16 sets the number of attention heads in the first layer of GAT to 16.
For inductive learning experiments, where test data unseen during training, GAT and several GraphSAGE variants considered baselines.
Parameters On Cora, Citeseer, and Pubmed datasets, employ two-layer DiagGCN. The archi- tecture and seper-parameters of models on Cora and Citeseer are exactly the same. The learning rate is 0.005 and 12 weight decay is 0.0005. The first layer consists of 16 propagation mechanisms with 1-hop and 2-hop propagation layers; the hidden dimension is 8; and the last layer only uses propagation mechanism. Dropout mechanism with drop rate 0.6 is applied to the elements of the first layer diagonal matrix, and the adjacency matrix and inputs of each layer. On Pubmed, the learn- ing rate is 0.01 and weight decay 0.001, the first layer consists of 16 propagation mechanisms with only 1-hop propagation layers, and the hidden dimension is 8. The output of the last layer is averaged over 8 propagation mechanisms.
On PPI, a three-layer DiagGCN is employed, with four propagation mechanism and 256 hidden dimension the first and the second layers, and the output of the last layer is averaged by six propagation mechanisms.
4.2 EXPERIMENTAL RESULTS.
Following the procedure in the original GCN and GAT papers, the reported accuracy results of our methods are averaged over 100 runs with random weight initializations. addition, we also report the standard deviations and statistical test results.
Table 2 summarizes the prediction accuracy of node classification for the transductive learning task. It shows that our DiagGCN significantly outperforms GCN and its variants, MoNet, DPFCNN, GAT and GAT with 16 attention mechanism. Thus the explicit consideration nodes and adaptive neighborhood aggregation step in GCNs can perform better than other sophisti- cated models due to its capacity to capture the propagation process networks.
network importance of
The results of inductive learning in PPI are shown in Table 3, where the results of different versions of GraphSAGE in the original paper (Hamilton et al. 2017) and the result of GraphSAGE modified by Velickovic al. (2018) are all reported. GAT (Velickovic al. 2018 is also added as base- line. The table suggests that DiagGCN significantly outperforms state-of taaee-of-th-aate the-art art cocelines-vaiionn GraphSAGE models and the latest GAT model.

---

Under review as a conference paper at ICLR 2020
Ablation Study. In the ablation experiments, the results show that DiagGCN with only node adap- tive rescaling or with only node adaptive encoders still performs better than baselines.
To further evaluate the importance of the rescaling matrices and encoders in the proposed DiagGCN model. we reduced #heads (#rescaling diagonal matrices and encoders) to 1/2, 1/4, and 1/8 of the original, and found that the performance gradually decreases. DiagGCN (1/4) is comparable to GAT (16 heads). This indicates that adding rescaling matrices/encoders into DiagGCN is very helpful. On the other hand, we can also observe that the model is still robust. Even removing (or keeping only) 1/2 of rescaling matrices and encoders causes a little loss of performance. In addition, it also suggests that the performance of using rescaling or encoder alone comparable to the model with 1/2 of rescaling matrices and encoders, indicating that rescaling matrices and adaptive encoders play a similar role.
Statistical Significance. We did the significance test for the comparison between DiagGCN and GAT. All reported results are averaged over 100 repeated experiments with p-values consistently and significantly << 0.05, which verifies the significance of the proposed model. Additionally, the standard deviation reported indicates the robustness of the results.
5 RELATED WORK
With the advances in deep learning, there have been tremendous attempts to generalize neural net- works to graph-structured data. Graph Neural Networks (GNNs) (Gori et al. 2005) [Scarselli et al.] 2009) are introduced as recursive neural networks, where node features are propagated iteratively until equilibrium. GG-NNs (Li et al. 2015) applies gated recurrent units and modern optimization to GNN to evade the requirement of the convergence the equilibrium.
The convolutional networks in graph-structured data, differently from the general GNNs, can better capture the inherent graph topology by defining the spatial localized convolutional filter in graph
Laplacian spectral space (Bruna et al. 2013. Henaff et al., 2015; Defferrard et al.] 2016 Kipf & Welling, 2016) directly graph neighborhoods (Duvenaud et al. 2015 Niepert al.) [016] Monti et al. 2017 Hamilton et al.) 2017). Among these graph convolutional methods, graph con- volutional networks (GCNs) (Kipf & Welling 2016) have been widely applied semi-supervised
node classification (Kipl & Welling, 2016). link prediction (van den Berg et al.) (017) and knowl-
edge graphs (Schlichtkrull et al.) 20088/2hang al., 2019) with promising results.
As for many expressive GCN variants, an intuition behind them is to capture complicated pair-wise dependencies between network nodes. In MoNet (Monti al., (017). the node relationship is ex- pressed by the parametric kernel with learnable parameters. DPFCNN (Monti et al.) 2018) further generalize MoNet and elaborate the relationship both on the graph and its dual graph. graph attention network (GAT) (Velickovic et al.) 20188). multi-head self-attention mechanism is applied on edges. These methods have achieved the state-of-the-art performance. In this paper, we revisit GCNs' neighborhood aggregation step and enhance the representation capacity by adaptively mod- eling the propagation mechanism into graph convolutions. The Unsupervised loss of maximizing mutual information in Deep Graph Infomax (Veličković et al. 2019) may further help our aggrega- tion step to encode globally relevant information into the node representation.
6 CONCLUSIONS
In this work, we study graph convolutional networks (GCNs) with a focus on neighborhood ag- gregation. We generate insights into the understanding of GCNs, inspired by which we propose the adaptive neighborhood aggregation technique to advance GCNs. Extensive and standard experi- ments on benchmark datasets suggest that the presented technique offers GCNs with more expressive power than -fate-of-the-ar GCN variants, such as GraphSAGE, GAT, and Chebyshev, benefiting the downstream graph mining tasks. Importantly, our GCN model offers flexible framework where the permutations of adjacency matrices and diagonal matrices help to design different kinds of GCNs and it can also be connected with graph attention networks, including node attention, edge attention, and path attention. For future work, we would like to examine the other components in GCNs and broadly, to design more powerful neural architectures for modeling graph data structure.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Ossama Abdel-Hamid, abdel-Rahman Mohamed, Hui Jiang, Li Deng, Gerald Penn, and Dong Yu. Convolutional neural networks for speech recognition. ACM Trans. Audio, Speech and Lang. Proc., 22(10):1533-1555 October 2014.
Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric frame- work for learning from labeled and unlabeled examples. JMLR, 7(Nov):2399-2434, 2006.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. 1311v.132..60000 2013.
Ronald S Burt. Structural holes: The social structure of competition. Harvard university press, 2009.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling. arXiv: 10247, 2018.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NIPS' 16, pp. 3844-,852, 2016.
David K Duvenaud, Dougal Maclaurin, Jorge Iparraguirre, Rafael Bombarell, Timothy Hirzel, Alán Aspuru-Guzik, and Ryan P Adams. Convolutional networks on graphs for learning molecular fingerprints. In NIPS' 15. pp. 2224-2222222 2232.. 2015.
Jonas Gehring, Michael Auli, David Grangier. Denis Yarats, and Yann Dauphin. Convolutional sequence sequence learning. arXiv:1705.03125 2017.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. arXiv:1704.01211 2017.
Marco Gori, Gabriele Monfardini, and Franco Scarselli, new model for learning in graph domains. In !JCNN'05, volume pp. 729-734, 2005.
Mark Granovetter. The strength of weak ties. American Journal of Sociology, 78(6): 1300-1300 1973.
Will Hamilton, Zhitao Ying. and Jure Leskovec. Inductive representation learning on large graphs. In N7, pp. 1025-1035, 2017.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In CVPR'15, pp. 1026-1034, 2015.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In CVPR' 16, pp. 770-778, 2016.
Mikael Henaff, Joan Bruna, and Yann LeCun. Deep convolutional networks on graph-structured data. arXiv:1506.0516. 2015.
Elihu Katz. The two-step flow of communication: An up-to-date report on an hypothesis. Public Opinion Quarterly, (1))): 78, 1957.
David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. In KDD '03, pp. 137-146, 2003.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv: 1609:.06000090 2016.
Alex Krizhevsky, Ilya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. In NIPS' pp. 1097-1105, 2012.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. arXiv:1511.0544 2015.
Qing Lu and I Lise Getoor. Link-based classification. In ICML'03, pp. 496-503, 2003.

---

Under review as a conference paper at ICLR 2020
Federico Monti, Davide Boscaini, Jonathan Masci, Emanuele Rodola, Jan Svoboda, and Michael M Bronstein. Geometric deep learning on graphs and manifolds using mixture model cnns. In CVPR' 17, volume 1, pp. 3, 2017.
Federico Monti, Oleksandr Shchur, Aleksandar Bojchevski, Or Litany, Stephan Günnemann, and Michael M Bronstein. Dual-primal graph convolutional networks. arXiv preprint arXiv:1806.00770 2018.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural net- works for graphs. In ICML'16, pp. 2014-2023, 2016.
Bryan Perozzi, Rami AI-Rfou, and Steven Skiena. Deepwalk: Online learning of social representa- tions. In KDD' 14, pp. 701-710, 2014.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini. The graph neural network model. IEEE Transactions Neural Networks, 20(1):61-80, 2009.
Michael Schlichtkrull, Thomas Kipf, Peter Bloem, Rianne van den Berg, Ivan Titov, and Max Welling. Modeling relational data with graph convolutional networks. In ESWC 18, pp. 593-607, 2018.
Rianne van den Berg, Thomas N Kipf, and Max Welling. Graph convolutional matrix completion. stat, 1050:7, 2017.
Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR' 18, 2018.
Petar Veličković, William Fedus, William L Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. ICLR'19 19, 2019.
Boris Weisfeiler and AA Lehman. A reduction a graph to a canonical form and an algebra arising during this reduction. Nauchno--eccmnichessayy Informatsia, 209):12-16, 1968.
Jason Weston, Frédéric Ratle, Hossein Mobahi, and Ronan Collobert. Deep learning via semi- supervised embedding. In Neural Networks: Tricks of the Trade, pp. 639-655, Springer, 2012.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? ICLR' 19, 2019.
Zhilin Yang, William W Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. arXiv:1603.0880 2016.
Fanjin Zhang, Xiao Liu, Jie Tang, Yuxiao Dong, Peiran Yao, Jie Zhang, Xiaotao Gu, Yan Wang, Bin Shao, Rui Li, et al. Oag: Toward linking large-scale heterogeneous entity graphs. 2019.
Xiaojin Zhu, Zoubin Ghahramani, and John D Lafferty. Semi cumi-supervieed learning using gaussian fields and harmonic functions. In ICML. (3,, pp. 912-919, 2003.
10


Reviews:
[{"review_id": "rkxOTkZg5S", "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": "This work proposes node adaptive rescaling and node adaptive encoder to enhance GCN. The proposed method is well explained and simple to implement. The experimental results indicate improvement and use t-test to show it's statistically significant.\n\nCons:\n1. I am not convinced that GCN does not consider node importance. When aggregating information, the degree information is used. In the example of opinion leaders, the nodes corresponding to opinion leaders usually have large degree.\n2. The proposed method is very similar to the attention method in \"Hierarchical Attention Networks for Document Classification\", where the query vector is a learnable vector. The authors should at least cite it and make appropriate discussion.\n3. The node adaptive encoder is more suitable to be called a new activation function. Then ablation study on different activation functions should be made.\n4. The experiments should cover comparison to more recent works, as well as graph classification tasks. For example, comparison to GIN or extending the proposed method to GIN would be interesting.\n5. Examples of how the proposed method learn the node importance correctly should be provided.\n\nMinor Cons:\n1. Figure 1 has a part of low resolution.\n2. The updated node importance in eqn.(6) should use a modified notation to differ from eqn.(3).\n3. The position of Table 2&3 is strange.", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "S1gSMbtpuH", "reviewer": "AnonReviewer3", "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 proposed  a so-called diagonal GCN method with adaptive neighborhood aggregation rules., namely, each node will be associated with an individual importance factor to re-scale the output signal  of the graph convolutional operator, and also an adaptive encoder function is adopted. This is achieved by adding a left diagonal matrix P and a right diagonal matrix Q to the standard message passing of GCN H’ = sigma(AHW), as H’(PAQHW); P and Q are parameterized based on the HW part (node features). Multihead attention and multi-hop versions are also derived. Connection of this formulation to the existing GAT method is also discussed. Empirical results on transductive node classification and inductive node classification are reported against state-of-the-arts.  \n\nOverall I feel that the novelty of the proposed method is quite limited. Adding a rescaling on each node seems a minor structural change based on existing GCN framework. Although the authors claim that the GAT method can be deemed as a special case of the proposed methods, the main contribution of inductive attention in GAT should not become a credit of the proposed method. Actually the empirical performance of the proposed method has only a small margin compared with the GAT, on the three node classification benchmark datasets, where the accuracies are around 80%, the improvement of the best version of the proposed methods is only around 0.3%, 0.7%, and 0.1%, respectively. This is somehow predictable since the proposed method does not exploit any extra useful information (such as graph structure) but simply base the new parameters on the existing components of the GCN message passing procedure. \n\nThe motivation of the paper is that the diffusion process on the graph should depend on the nodes’ status and influence (for example, some opinion leader nodes should have an amplified spread than other nodes), while existing GCN dies bit examine such ``difference’’ between the nodes. However, the roles or status of the nodes in a network are usually unavailable in practice; and if they can be ever be inferred, one has to use structural clues, Unfortunately, the extra parameters added here, namely the matrix P, Q, are dependent only on the features of the nodes (namely HW part), but not the graph structures,  therefore I do not think such parametrization would lead to significant benefit in improving the diffusion process. Indeed,  the original Gat method (graph attention network) has already achieved adaptive aggregation of the neighborhood information, by learning an inductive attention function  based on the node features; therefore the authors claim that existing GCN “ignores the difference between nodes” sounds very vague, since their new parameters are not capable enough to reflect “node differences” either (as a function of the node features).\n\nSome minor comments \n(1)\tFigure~1 is not easy to read while it is supposed to visualize the main idea clearly in one picture\n(2)\tIs there proof that if multi-hop version is used, the results can be improved?\n(3)\tWhat is the extra number of parameters compared with the standard GCN message passing？", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "H1lFVxr0Fr", "reviewer": "AnonReviewer2", "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 is well-written. The authors propose a new graph convolution neural network framework (DiagGCN) with an adaptive neighborhood aggregation step to adaptively scale the output signal for each node. In addition, they also propose an adaptive nonlinear encoder for the node's signal. Interestingly, sophisticated propagation models like graph networks \n with node/edge/path attention can also be formulated as the permutations of the adjacency matrix and diagonal matrices in the DiagGCN.\n\nGenerally, from my perspective, the idea in the paper is to reformulate the attention mechanism used in the GCN and this new diagonal mechanism is simpler and more general. One of my concerns is the \"node adaptive encoder\". Based on the experimental results, I did not see an obvious improvement between DiagGCN and DiagGCN with rescaling alone in Table 2 and Table 3. The classification improvement is 0, 0.1, 0.1, 0.3 with the node adaptive encoder. In addition, when comparing DiagGCN with baseline GAT, which is proposed in 2018, the performance approvement is also limited for the transductive learning tasks. \n\nIn conclusion, the idea proposed in the paper is interesting to me but the effectiveness of each module is not very well-supported by the experiments.\n\n", "extra_scores": {"experience_assessment": "I do not know much about this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: All three reviewers are consistently negative on this paper. Thus a reject is recommended.
Decision: Reject