Measuring and Improving the Use of Graph Information in Graph Neural Networks
Authors: Yifan Hou
Jian Zhang
James Cheng
Kaili Ma
Richard T. B. Ma
Hongzhi Chen
Ming-Chang Yang
Venue:  (2020)

Abstract: Graph neural networks (GNNs) have been widely used for representation learning on graph data. However, there is limited understanding on how much performance GNNs actually gain from graph data. This paper introduces a context-surrounding GNN framework and proposes two smoothness metrics to measure the quantity and quality of information obtained from graph data. A new, improved GNN model, called CS-GNN, is then devised to improve the use of graph information based on the smoothness values of a graph. CS-GNN is shown to achieve better performance than existing methods in different types of real graphs. 

Published as a conference paper at ICLR 2020
MEASURING AND IMPROVING THE USE OF GRAPH INFORMATION IN GRAPH NEURAL NETWORKS
Yifan Hou', Jian Zhang', James Cheng', Kaili Ma', Richard Ma? Hongzhi Chen', Ming-Chang Yang'
'Department of Computer Science and Engineering, The Chinese University of Hong Kong School of Computing, National University of Singapore {yfhou, jzhang, jcheng, k klmaj@es @cse. cuhk. edu. Öbma@comp nus www.uuuuuuuuuueeuuo (hzchen, mcyang 0 www.eccck....c...c....a.c..a.... edu. hk
ABSTRACT
Graph neural networks (GNNs) have been widely used for representation learning graph data. However, there is limited understanding on how much performance GNNs actually gain from graph data. This paper introduces context-surrounding GNN framework and proposes two smoothness metrics to measure the quantity and quality of information obtained from graph data. A new GNN model, called CS-GNN, is then designed to improve the use of graph information based on the smoothness values of graph. CS-GNN is shown to achieve better performance than existing methods in different types of real graphs.
INTRODUCTION
Graphs are powerful data structures that allow us easily express various relationships (i.c., edges) between objects (i.c., nodes). In recent years, extensive studies have been conducted on GNNs for
tasks such as node classification and link predication. GNNs utilize the relationship information in
graph data and significant improvements over traditional methods have been achieved on benchmark
datasets (Kipf & Welling 2017: Hamilton et al.] 2017 Velickovic et al., 2018 Xu al., 2019]
Hou et al. 2019). Such breakthrough results have led to the exploration of using GNNs and their variants different areas such as computer vision (Satorras & Estrach| 2018 Marino et al. 2017),
2015), natural language processing (Peng al. 2018 Yao et al. 2019), chemistry (Duvenaud al. biology (Fout et al., 2017). and social networks (Wang ct al. 2018). Thus, understanding why GNNs can outperform traditional methods that are designed for Euclidean data is important. Such understanding can help us analyze the performance of existing GNN models and develop new GNN models for different types of graphs.
In this paper, we make two main contributions: (7) two graph smoothness metrics to help understand the use of graph information in GNNs, and (2) new GNN model that improves the use of graph information using the smoothness values. We elaborate the two contributions as follows.
One main reason why GNNs outperform existing Euclidean-based methods is because rich informa- tion from the neighborhood of an object can be captured. GNNs collect neighborhood information with aggregators (Zhou et 2018), such the mean aggregator that takes the mean value of neigh- bors' feature vectors (Hamilton et al. 2017), the sum aggregator that applies summation (Duvenaud al. 2015), and the attention aggregator that takes the weighted sum value (Velickovic al.) 2018)) Then, the aggregated vector and a node's 's own feature vector are combined into new feature vector. After some rounds, the feature vectors of nodes can be used for tasks such as node classification. Thus, the performance improvement brought by graph data is highly related to the quantity and quality of the neighborhood information. To this end, we propose two smoothness metrics on node features and labels to measure the quantity and quality of neighborhood information of nodes. The metrics are used to analyze the performance of existing GNNs on different types of graphs.
In practice not all neighbors of node contain relevant information w.r.t. specific task. Thus, neighborhood provides both positive information and negative disturbance for given task. Simply aggregating the feature vectors of neighbors with manually-picked aggregators (i.e., users choose

---

Published as a conference paper at ICLR 2020
type of aggregator for different graphs and tasks by trial or by experience) often cannot achieve optimal performance. To address this problem. we propose a new model, CS-GNN, which uses the smoothness metrics selectively aggregate neighborhood information amplify useful information and reduce negative disturbance. Our experiments validate the effectiveness of our two smoothness metrics and the performance improvements obtained by CS-GNN over existing methods.
2 MEASURING THE USEFULNESS OF NEIGHBORHOOD INFORMATION
We first introduce a general GNN framework and three representative GNN models, which show how existing GNNs aggregate neighborhood information. Then we propose two smoothness metrics to measure the quantity and quality of the information that nodes obtain from their neighbors.
2.1 GNN FRAMEWORK AND MODELS
The notations used in this paper, together with their descriptions, are listed in Appendix A We use = E),E) to denote a graph, where V and represent the set of nodes and edges of g. We use Cu,e' E to denote the edge that connects nodes and v', and N₁, = {v' Ev,, E { to denote the set of neighbors of a node U E V. Each node e E V has a feature vector I, E X with dimension d. Consider node classification task, for each node e E V with a class label Vu. the goal is to learn a representation vector hr and a mapping function f(-) to predict the class label Ye of node v, i.e.,
de (hb) where Ov is the predicted label.
Table 1: Neighborhood aggregation schemes
Models
Aggregation and combination functions for round & (1 S k & K)
General GNN framework
COMBINE (2)
(1 AGGREGATE (K) ((h (1=1)) o E EN.))
GCN
11 EVENLLEO VINGI+T)-UUXIIEE) W(K-1), 1 11
A (()-1), (((t-1)) |GGREGATEE(1/ (1-1), E Na3)
GraphSAGE
GAT
he =
EoyeN,, 9i
(k-1), w(k- 1), (k-1))
GNNs are inspired by the Weisfeiler-Lehman test (Weisfeiler & Lehman 1968 Shervashidze et al. 2011] which is an effective method for graph isomorphism. Similarly, GNNs utilize a neighborhood aggregation scheme to learn representation vector h. for each node and then use neural networks to learn a mapping function f(.). Formally, consider the general GNN framework (Hamilton et al., 2017 Zhou et al. 2018, Xu et al. 2019) in Table I with K rounds of neighbor aggregation. In each round, only the features of hhh neighbors are aggregated, and the framework consists two functions, AGGREGATE and COMBINE. We initialize h. Tu. After K rounds of aggregation, each node u E V obtains its representation vector {KK We use (K( and a mapping function f()), e.g. fully connected layer, to obtain the final results for specific task such as node classification.
Many GNN models have been proposed. We introduce three representative ones: Graph Convolu- tional Networks (GCN) (Kipf & Welling (017)) GraphSAGE (Hamilton et al.) (017). and Graph Attention Networks (GAT) (Velickovic et al. (018). GCN merges the combination and aggregation functions, shown in Table [ where A(.) represents the activation function and W is a learnable parameter matrix. Different from GCN, GraphSAGE uses concatenation 'II' as the combination function, which can better preserve node's 's information. Different aggregators (e.g., mean, max pooling) are provided in GraphSAGE. However, GraphSAGE requires users to choose an ag- gregator use for different graphs and tasks, which may lead to sub-optimal performance. GAT addresses this problem by an attention mechanism that learns coefficients of neighbors for aggrega- tion. With the leamed coefficients d (k-1) all the edges (including self-loops), GAT aggregates neighbors with a weighted sum aggregator. The attention mechanism can learn coefficients of neigh- bors in different graphs and achieves significant improvements over prior GNN models.
2

---

Published as a conference paper at ICLR 2020
2.2 GRAPH SMOOTHNESS METRICS
GNNs usually contain an aggregation step to collect neighboring information and combination step that merges this information with node features. We consider the context C, of node o as the node's own information, which is initialized as the feature vector Ty of e. We use 8y to denote the surrounding of v. which represents the aggregated feature vector computed from v's neighbors. Since the neighborhood aggregation can be seen as convolution operation on a graph (Defferrard al. 2016). we generalize the aggregator as weight linear combination, which can be used to express most existing aggregators. Then, we can re-formulate the general GNN framework as context-surrounding framework with two mapping functions fi()) and f2(-) in round as:
(b) fi(ch 1)
(k-1) = f2( f2(E,, vy EN, Dz
(k-1) ai - (k-1))
(1)
From equation (1), the key difference between GNNs and traditional -ettrak- based methods for Euclidean data is that GNNs can integrate extra information from the surrounding of a node into its context. In graph signal processing (Ortega et al. 2018), features on nodes regarded signals and it is common to assume that observations contain both noises and true signals a standard signal processing problem (Rabiner & Gold 1975). Thus, can decompose context vector into two parts as Co. Ce. + ite. where Co. is the true signal and ile. is the noise.
Theorem 1. Assume that the noise We; follows the same distribution for all nodes. If the noise power of Re; is defined by its variance o², then the noise power of the surrounding input (o 1
(k)
E EeJEN., (i -Ca
(k-1) (k-1) is Ee,eN., (0
B Theorem shows that the surrounding input has less noise power than the context when proper aggregator (i.e., coefficient o.j (k-1)) is used. Specifically, the mean aggregator has the best denoising performance and the pooling aggregator (e.g., max-pooling) cannot reduce the noise power. For the sum aggregator, where all coefficients are equal to 1, the noise power of the surrounding input is larger than that of the context.
The proof can be found in Appendix
2.2.1 FEATURE SMOOTHNESS
We first analyze the information gain from the surrounding without considering the noise. In the treme case when the context is the same as the surrounding input, the surrounding input contributes no extra information to the context. To quantify the information obtained from the surrounding, present the following definition based on information theory.
Definition (Information Gain from Surrounding). For normalized feature space X₂ 10, 1]d,, if (l) (1)) is also in X₁ = [0, [0,1] The probability density function (PDF) of elhh) over Xx defined as C(k), which is the ground truth and can be estimated by nonparametric methods with set of samples. where each sample point e..) is sam- pled with probability 1/2E/ Correspondingly, the PDF of EujEN., d oll) is S(K), which (N) ((K)),
EV,eN., T = 1, the feature space of Ee,EN., 0,d
can be estimated with set of samples {EnjeN., 0,3 - where each point is sampled with
probability |/ The information gain from the surrounding round is can be computed by Kullback-Liibler divergence (Kullback & Leibler 1957)
5(k) = / ((x) log (x))(z) dx.
DKL(S(()IC()))
x
The Ballback-Leible divergence is measure of information loss when the context distribution is used to approximate the surrounding distribution (Kurt) 2017). Thus, we can use the divergence to measure the information gain from the surrounding into the context of a node. When all the context vectors are equal to their surrounding inputs, the distribution of the context is totally the same with that the surrounding. In this case, the divergence is equal to 0, which means that there is no extra information that the context the surrounding of a node have different distributions, the divergence value is strictly positive. Note that in practice, the ground-truth distributions of the context and surrounding signals are unknown.
obtain from the surrounding. On the other hand, if the context and
3

---

Published as a conference paper at ICLR 2020
In addition, for learnable aggregators, e.g., the attention aggregator, the coefficients are unknown. Thus, we propose a metric Xy to estimate the divergence. Graph smoothness (Zhou & Schölkopi 2004 is effective measure of the signal frequency in graph signal processing (Rabiner & Gold 1975.. Inspired by that, we define the feature smoothness on a graph.
Definition 3 (Feature Smoothness). Consider the condition of the first round, where Co Tu. we define the feature smoothness Xj over normalized space X =10, 1]d
A Evev (EVEN,(T x..e) ) 1
El.d
where| || - ||1 is the Manhattan norm.
According to Definition 3. larger 'y indicates that the feature signal of a graph has higher fre- quency, meaning that the feature vectors T. and Fy' are more likely dissimilar for two connected nodes and v' in the graph. In other words, nodes with dissimilar features tend to be connected. Intuitively, for a graph whose feature sets have high frequency, the context of node can obtain more information gain from its surrounding. This is because the PDFs (given in Definition 2 of the context and the surrounding have the same probability but fall in different places in space X. Formally, we state the relation between Xy and the information gain from the surrounding in the following theorem. For simplicity,
let X' No, = do. C = (()) and S S(O).
Theorem 4. For a graph 9 with the set of features X' in space [o, 1]d and using the mean aggre- gator, the information gain from the surrounding D ( (S|[C) is positively correlated to its feature smoothness Aj. i.e. (KL(S) ~ Xy. In particular, D (SIIC) = 0 when A --0.
The proof can be found in Appendix [ According to Theorem 4 a large X means that a GNN model can obtain much information from graph data. Note that D D (SIIC) here is under the condition when using the mean aggregator. Others aggregators, e.g., pooling and weight could have different DKL (SIIC) values, even if the feature smoothness Xy is a constant.
2.2.2 LABEL SMOOTHNESS
After quantifying the information gain with ',, we next study how to measure the effectiveness of information gain. Consider the node classification task, where each node u E V has a label yus we define = 1i if Ye; Voy. The surrounding input can be decomposed into two parts based on the node labels as EnjeN, (k-1)) ())(111111 Li.
E N.N.N I(0; (1y; (K- 1)
E (1II( (k-1) (x)))(-1))
where I(.) is an indicator function. The first term includes neighbors whose label Yoy is the same as Yor, and the second term represents neighbors that have different labels. Assume that the classifier has good linearity, the label of the surrounding input is shifted Ee,eN., Li Yuy (Zhang et al., 2018), where the label Yey is represented as a one-hot vector here. Note that in GNNs, even the context and surrounding of v are combined, the label of 22 is still yo:- Thus, for the node classification task, it is reasonable to consider that neighbors with the same label contribute positive information and other neighbors contribute negative disturbance.
(k-1).
Definition 5 (Label Smoothness). label smoothness as
To measure the quality of surrounding information, we define the
A =
Σ Eugory EE (1 (1-1(1; = vg))
According to Definition 5 larger \ implies that nodes with different labels tend to be connected together, in which case the surrounding contributes more negative disturbance for the task. In other words, a small A means that a node can gain much positive information from its surrounding. To use ê to qualify the surrounding information, graphs do not have many labeled nodes, we may use a subset of labeled data to estimate \₁ which is often sufficient for obtaining good results as we show for the BGP dataset used in experiments.
require labeled data for the training. When some
In summary, we propose a context-surroune surrounding framework, and introduce two smoothness metrics to estimate how much information that the surrounding can provide (i.e., larger A means more information) and how much information is useful (i.c., smaller x means more positive information) for given task given graph.
4

---

Published as a conference paper at ICLR 2020
3
GRAPH NEURAL NETWORKS
In this section, we present a new GNN model, called CS-GNN, which utilizes the two smoothness metrics to improve the use of the information from the surrounding.
3.1 THE USE OF SMOOTHNESS FOR SENTEXT-SURROUNDEEE GNNS
The aggregator used in CS-GNN is weighted sum and the combination function is concatenation. To compute the coefficients for each of the K rounds, we multiplicative attention mechanism similar to Vaswani et al. (2017). We obtain 2/ attention coefficients by multiplying the leveraged representation vector of each neighbor of node with the node's context vector, and applying the
softmax normalization. Formally, each coefficient dig in round k is defined as follows:
(8)
exp (A(pe)) (R)
(R)))
EEEN exp (A(pe) (R)
-i,1
where pe. (W
No:
)T
9 Pe. W (k) No, (x) and W (K) are two learnable matrices.
To improve the use of the surrounding information, we utilize feature and label smoothness fol- lows. First, we use A to drop neighbors with negative information, i.e., we set dig = 0 if ai is less than the value of the r-th (r = [2| {r]) smallest attention coefficient. As these neighbors contain noisy disturbance the task, dropping them is helpful to retain node's 's own features.
(k)
Second, as y is used to estimate the quantity of information gain, we use it to set the dimension (l)) of Pi; as [dg- /xyl, which obtained empirically to achieve good performance. Setting the appropriate dimension is important because large dimension causes the attention mechanism to fluctuate while a small one limits expressive power.
Third, we compute the attention coefficients differently from GAT (Velickovic et al. 2018 GAT uses the leveraged representation vector ((K). compute the attention coefficients. In contrast, in equation (2) we use R.,j
(M) which is the difference of the context vector of node v; and the leveraged
(A) representation vector of neighbor vj. The definition of Rif is inspired by the fact that larger \5 indicates that the features
node and its neighbor are more dissimilar, meaning that the neighbor (k) can contribute greater information gain. Thus, using q, we obtain a larger/smaller a when the
(k)
features of 0 and its neighbor 2j are more dissimilar/similar. For example, if the features of node and its neighbors are very similar, then T.j is small and hence a;,j is also small.
(k)
Using the attention coefficients, we perform rounds of aggregations with the weighted sum ag- gregator to obtain the representation vectors for each node
h (b) A (W (n(*-")) 1i4-"I "
(k-1) ai
where w(A) is learnable parameter matrix to leverage feature vectors. Then, for task such as node classification, we use a fully connected layer to obtain the final results be, = A(W h (K)). where W a learnable parameter matrix and Dr, the predicted classification result of node 2;-
),
3.2 SIDE INFORMATION ON GRAPHS
Real-world graphs often contain side information such attributes on both nodes and edges, local topology features and edge direction. We show that CS-GNN can be easily extended include rich side information improve performance. Generally speaking, side information can be divided into two types: context and surrounding. Usually, the side information attached on nodes belongs to the context and that edges neighbors belongs to the surrounding. To incorporate the side information into our CS-GNN model, we use the local topology features as an example.
We use method inspired by GraphWave (Donnat et al. 2018), which uses heat kernel in spectral graph wavelets to simulate heat diffusion characteristics as topology features. Specifically, we con- struct [V] subgraphs, G {Gry Gug..., Gryy }. from a graph = {V,E), where Go; is composed
5

---

Published as a conference paper at ICLR 2020
of e and its neighbors within K hops (usually K is small, K = 2 default in our algorithm), as well as the connecting edges. For each Ge, E G, the local topology feature vector tu, of node v; is obtained by a method similar to GraphWave.
Since the topology feature vector t, itself does not change during neighborhood aggregation, we do not merge it into the representation vector. In the attention mechanism, we regard te, part of the context information by incorporating it into pe; (W2%) (hre. ( I!(,)))" And in the last fully connected layer, we use fu, to obtain the predicted class label tr. A(W (K) (It.)))
3.3 COMPARISON WITH EXISTING GNN MODELS
The combination functions of existing GNNs are given in Table | The difference between addi- tive combination and concatenation is that concatenation can retain a node's own feature. For the aggregation functions, different from GCN and GraphSAGE. GAT and CS-GNN improve the per- formance of a task on given graph by an attention mechanism to learn the coefficients. However, CS-GNN differs from GAT in the following ways. First, the attention mechanism of CS-GNN fol- lows multiplicative attention, while GAT follows additive attention. Second, CS-GNN's attention mechanism utilizes feature smoothness and label smoothness to improve the use of neighborhood information as discussed in Section 3.1 This is unique in CS-GNN and leads to significant perfor- mance improvements over existing GNNs (including GAT) for processing some challenging graphs (to be reported in Section Third, CS-GNN uses side information such as local topology features to further utilize graph structure as discussed in Section 3.2
4 EXPERIMENTAL EVALUATION
We first compare CS-GNN with representative methods the node classification task. Then evaluate the effects of different feature smoothness and label smoothness on the performance of neural networks-based methods.
4.1 BASELINE METHODS, DATASETS, AND SETTINGS
Baseline. We selected three types of methods for comparison: topology-based methods, feature- based methods, and GNN methods. For each type, some representatives were chosen. The topology- based representatives are struc2vec (Ribeiro et al. 2017). GraphWave (Donnat et al. (018) and La- bel Propagation (Zhu & Ghahramani] 2002). which only utilize graph structure. struc2vec learns la- tent representations for the structural identity of nodes by random walk (Perozzi et al.] (014)). where node degree is used as topology features. GraphWave is a graph signal processing method (Ortega et al. 2018) that leverages heat wavelet diffusion patterns to represent each node and is capable of capturing complex topology features (e.g., loops and cliques). Label Propagation propagates labels from labeled nodes to unlabeled nodes. The feature-based methods are Logistic Regression and Multilayer Perceptron (MLP), which only use node features. The GNN representatives are GCN, GraphSAGE and GAT, which utilize both graph structure and node features.
Datasets. We used five real-world datasets: three citation networks (i.e.. Citeseer, Cora Sen al. 2008) PubMed (Namata et al. 2012)), one computer co-purchasing network in Amazon (ccAuley al. 2015), and one Border Gateway Protocol (BGP) Network (Luckie al. 2013). The BGP network describes the Internet's inter-domain structure and only about 16% of the nodes have labels.
Thus, we created two datasets: BGP (full), which the original graph, and BGP (small), which was obtained by removing all unlabeled nodes and edges connected to them. The details (e.g., statistics and descriptions) of the datasets are given in Appendix D
Settings. We use F1-Micro score measure the performance of each method for node classifica- tion. To avoid under-fitting, 70% nodes in each graph are used for training. 10% for validation and 20% for testing. For each baseline method, set their the parameters either their default values or the same as in CS-GNN. For the GNNs and MLP, the number of hidden layers (rounds) was set as K = 2 to avoid smottsnoo More detailed settings are given in Appendix [E]
Note that GraphSAGE allows users to choose an aggregator. We tested four aggregators for Graph- SAGE (details in Appendix and report the best result for each dataset in experiments below.

---

Published as a conference paper at ICLR 2020
4.2 PERFORMANCE RESULTS OF NODE CLASSIFICATION
Smoothness. Table Table2rrportt reports the two smoothness values of each dataset. Amazon has much larger A value (i.e., 89.67 x 10-2) than the rest, while PubMed has the smallest X value. This implies that the feature vectors of most nodes in Amazon are dissimilar and conversely for PubMed. For label smoothness A, BGP (small) has fairly larger value (i.e.. 0.71) than the other datasets, which means that 71% of connected nodes have different labels. Since BGP (full) contains many unlabeled nodes, we used BGP (small)'s X as an estimation.
Table 2: Smoothness values
Smoothness value"
Dataset
Citeseer
Cora
PubMed
Amazon
BGP (small)
BGP (full)
Metries
Feature Smoothness A (10-3)
2.76
4.26
0.91
89.67
7.46
5.90
Label Smoothness À
0.26
0.19
0.25
0.22
0.71
p=0.71
F1-Micro scores. Table 3 reports the F1-Micro scores of the different methods for the task of node classification. The Fi-Micro scores are further divided into three groups. For the topology- based methods, Label Propagation has relatively good performance for the citation networks and the co-purchasing Amazon network, which is explained as follows. Label Propagation effective in community detection and these graphs contain many community structures, which can be inferred from their small À values. This is because a small À value means that many nodes have the same class label as their neighbors, while nodes that are connected together and in the same class tend to form community. In contrast, for the BGP graph in which the role (class) of the nodes is mainly decided by topology features, struc2vec and Graph Wave give better performance. Graph Wave ran out of memory (512 GB) on the larger graphs as it is spectrum based method. For the canture-basee methods, Logistic Regression and MLP have comparable performance on the graphs.
For the GNN methods, GCN and GraphSAGG have comparable performance except the PubMed and BGP graphs, and similar results are observed for GAT and CS-GNN The main reason that PubMed has a small Xy. which means that small amount of information gain is obtained from the surrounding, and BGP has large λ meaning that most information obtained from the surrounding negative disturbance. Under these circumstances, using concatenation the combination function allows GraphSAGE and CS-GNN to retain a node's s own features. This is also why Logistic Regression and MLP also achieve good performance PubMed and BGP because they only the node features. However, for the other datasets, GAT and CS-GNN have considerably higher F1-Micro scores than all the other methods. Overall, CS-GNN the only method that achieves competitive performance on all the datasets.
Table 3: Node classification results
F1-Micro(S))
Dataset
Citeseer
Cora
PubMed
Amazon
BGP (small)
BGP (full)
Alg.
struc2vec
30.98
41.34
47.60
39.86
48.40
49.66
Graph Wave
28.12
31.66
OOM
37.33
50.26
OOM
Label Propagation
71.07
86.26
78.52
88.90
34.05
36.82
Logistic Regression
69,96
76.62
87.97
85.89
65.34
62,41
MLP
70.51
73.40
87.94
86.46
67.08
67.00
GCN
71.27
80.92
80,31
91.17
51.26
54,46
GraphSAGE
69.47
83.61
87.57
90.78
65.29
64.67
GAT
74.69
90.68
81.65
91.75
47.44
$8.87
CS-GNN (w/o LTF)
73.58
90.38
89.42
92.48
66.20
68.83
CS-GNN
75.71
91.26
89.53
92.77
66.39
68.76
We further examine the effects local topology features (LTF) on the performance. We report the results of CS-GNN without using LTF, denoted as CS-GNN (w/o LTF) in Table The results show that using LTF does not significantly improve the performance of CS-GNN. However, the results do reveal the effectiveness of the smoothness metrics in CS-GNN, because the difference between

---

Published as a conference paper at ICLR 2020
CS-GNN (w/o LTF) and GAT is mainly in the use of the smoothness metrics in CS-GNN's attention mechanism. As shown in Table 3, CS-GNN (w/o LTF) still achieves sigmificant improvements over GAT PubMed (by improving the gain of positive information) and BGP (by reducing negative noisy information from the neighhorhood).
non-GNN methods. We also evaluate whether GNNs always better meth- ods, in other words, whether graph information is always useful. Table X presents the improve- ments of existing GNNs (i.e., GCN, GraphSAGE, GAT) and CS-GNN over the topology-based and feature-based methods, respectively. The improvements (in %) are calculated based on the average F1-Micro scores of each group of methods. The results show that using the topology alone, even the surrounding neighborhood is considered, is not sufficient. This is true even for the BGP graphs for which the classes of nodes are mainly determined by the graph topology. Compared with feature- based methods, GNN methods gain more information from the surrounding, which is converted into performance improvements. However, for graphs with small 2y and large A existing GNN meth- ods fail to obtain sufficient useful information obtain too much negative noisy information, thus leading to even worse performance than purely feature-based methods. In contrast, CS-GNN utilizes smoothness increase the gain of positive information and reduce negative noisy information for given task, thus achieving good performance on all datasets.
Improvements
Table 4: Improvements of GNNs over non-GNN methods
Improvement (%)
Dataset
Citeseer
Cora
PubMed
Amazon
BGP (small)
BGP (full)
Alg.
Existing GNNs vs. topology-base methods
32%
65%
23%
CS-GNN vs. topology-
paase based methods
74%
42%
68%
50%
59%
Existing GNNs vs. feature-bass based methods
2%
-5%
6%
-17%
CS-GNN feature-hased methods
8%
22%
2%
8%
0%
6
4.3 SMOOTHNESS ANALYSIS
The results in Section 4.2 show that GNNs achieve good performance by gaining surrounding information in graphs with large ' and small dІ However, the experiments were conducted on different graphs and there could be other factors than just the smoothness values of the graphs. Thus, in this experiment we aim to verify the effects of smoothness using one graph only.
0.8
102
Smoothress
0.85
0.8
-GrphSSAE
.ZON
-M
Lutel Broothrees
0.75
0.2
0.4
0.8
0.8
logo2 BroadossiTimes) (og(2"0).00)
Dracout
Figure 1: The effects of smoothness
To adjust X graph, we broadcast the feature vector of each node to its neighbors in rounds. In each round, when node receives feature vectors, it updates its feature vector as the mean of its current feature vector and those feature vectors received, and then broadcast the new feature vector to its neighbors. If we keep broadcasting iteratively, all node features converge the same value due to over-smoothness. To adjust A we randomly drop a fraction edges that connect two nodes with different labels. The removal of such edges decreases the value of \ and allows nodes to gain more positive information from their neighbors. We used the Amazon graph for the evaluation because the graph is dense and has large Xy.
8

---

Published as a conference paper at ICLR 2020
Figure 1 reports the F1-Micro scores of the neural-netwerk-based methods (i.e., MLP and the GNNs). Figure (left) shows that as we broadcast from 2 to 2 rounds, 2y also decreases accord- ingly. As y decreases, the performance of the GNN methods also worsens due to over- wer-smoothness.. However, the performance of MIP first improves significantly and then worsens, and becomes the poorest at the end. This is because the GNN methods can utilize the surrounding information by their design but MLP cannot. Thus, the broadcast of features makes it possible for MLP to first at- tain the surrounding information. But after many rounds of broadcast, the effect of over-smoothness becomes obvious and MLP's performance becomes poor. The results are also consistent with the fact that GNN models cannot be deep due to the over-smoothness effect. Figure (right) shows that when Ar decreases, the performance of the GNN methods improves accordingly. On the contrary, since MLP does not use surrounding information, dropping edges has no effect on its performance. In summary, Figure fuurther verifies that GNNs can achieve good performance on graphs with large Ay and small AG where they can obtain more positive information gain from the surrounding.
CONCLUSIONS
We studied how to measure the quantity and quality of the information that GNNs can obtain from graph data. We then proposed CS-GNN to apply the smoothness measures improve the use of graph information. We validated the usefulness of our method for measuring the smoothness values of a graph for given task and that CS-GNN is able to gain more useful information to achieve improved performance over existing methods.
ACKNOWLEDGMENTS
We thank the reviewers for their valuable comments. We thank Mr. Ng Hong Wei for processing the BGP data. This work was supported in part by ITF 6904945 and GRF 14222816.
REFERENCES
Pengfei Chen, Weiwen Liu, Chang- Yu Hsich, Guangyong Chen, and Shengyu Zhang. Utilizing edge features in graph neural networks via variational information maximization. CoRR, 2019.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NeurlPS, pp. 3837-3845, 2016.
Claire Donnat, Marinka Zitnik, David Hallac, and Jure Leskovee. Learning structural node embed-
dings via diffusion wavelets. In SIGKDD, pp. 1320-1329, 2018.
David Duvenaud, Dougal Maclaurin, Jorge eguilera-Iparraguie Rafael Gómez-Bombarelli, Tim- othy Hirzel, Alán Espuru-Guzik and Ryan Adams. Convolutional networks on graphs for learning molecular fingerprints. In NeurIPS, pp. 2224 2224-2232, 2015.
Alex Fout, Jonathon Byrd, Basir Shariat, and Asa Ben-Hur. Protein interface prediction using graph convolutional networks. In NeurIPS, pp. 6530-6539, 2017.
William I.. Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. NeuriPS, pp. 1024-1034, 2017.
Yifan Hou, Hongzhi Chen, Changji Li, James Cheng, and Ming-Chang Yang. A representation learning framework for property graphs. In SIGKDD, pp. 65-73, 2019.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In ICLR, 2017.
Solomon Kullback and Richard A Leibler. On information and sufficiency. The annals of mathe- matical statisties, 22(1):79 86, 1951.
Will Kurt. Kullback-lcible divergence explained, 2017.
Matthew J. Luckie, Bradley Huffaker, Amogh Dhamdhere, Vasileios Giotsas, and ke claffy, AS relationships, customer cones, and validation. In IMC, pp. 243-256, 2013.

---

Published as a conference paper at ICLR 2020
Kenneth Marino, Ruslan Salakhutdinov, and Abhinav Gupta. The more you know: Using knowledge graphs for image classification. In CVPR, pp. 20-28, 2017.
Julian J. McAuley, Christopher Targett, Qinfeng Shi, and Anton van den Hengel. Image-based recommendations on styles and substitutes. In SIGIR, pp. 43-52, 2015.
Galileo Namata, Ben London, Lise Getoor, Bert Huang, and UMD EDU. Query-driven active surveying for collective classification. In 10th International Workshop on Mining and Learning with Graphs, pp. 8, 2012.
Antonio Ortega, Pascal Frossard, Jelena Kovacevic, José M. F. Moura, and Pierre Vandergheynst. Graph signal processing: Overview, challenges, and applications. Proceedings of the IEEE, 106 (5):808 088888888, 2018.
Hao Peng, Jianxin Li, Yu He, Yaopeng Liu, Mengjiao Bao, Lihong Wang, Yangqiu Song, and Qiang Yang. Large-scale hierarchical text classification with recursively regularized deep graph-cnn. In WWW. pp. 1063-1072, 2018.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: online learning of social representa- tions. In SIGKDD, pp. 701-710, 2014.
Lawrence R Rabiner and Bernard Gold. Theory and application of digital signal processing. Engle- wood Cliffs, NJ, Prentice-Houd Inc., 1975.
Leonardo Filipe Rodrigues Ribeiro, Pedro H. P. Saverese, and Daniel R. Figueiredo. struc2vec: Learning node representations from structural identity. In SIGKDD, pp. 385-394, 2017.
Victor Garcia Satorras and Joan Bruna Estrach. Few-shot learning with graph neural networks. In ICLR, 2018.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Gallagher, and Tina Eliassi-Rad. Collective classification in network data. AI Magazine, 29(3):33-106, 2008.
Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn, and Karsten M. Borgwardt. Weisfeiler-lehman graph kernels. J. Mach. Learn. Res., 12:2539-2561, 2011.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In NeurIPS, pp. 5998-6008, 2017.
Petar Veliekovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Petar Velickovic, William Fedus, William L. Hamilton, Pietro Liò, Yoshua Bengio, and R. Devon Hjelm. Deep graph infomax. In ICLR, 2019.
Zhouxia Wang, Tianshui Chen, Jimmy S. Ren, Weihao Yu, Hui Cheng, and Liang Lin. Deep reasoning with knowledge graph for social relationship understanding. In IJCAI, pp. 1021-1028, 2018.
Boris Weisfeiler and Andrei A Lehman. A reduction of a graph to a canonical form and an algebra arising during this reduction. Nanchno--Technicesskww Informatsia, 2(9):12-16, 1968.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? In ICLR, 2019,
Liang Yao, Chengsheng Mao, and Yuan Luo. Graph convolutional networks for text classification. In AAAI, pp. 7370-7377, 2019.
Hongyi Zhang, Moustapha Cissé, Yann N. Dauphin, and David Lopez-Paz. mixup: Beyond empiri- cal risk minimization. In ICLR, 2018.
Dengyong Zhou and Bernhard Schölkopf. A regularization framework for learning from graph data. In ICML workshop, volume 15, pp. 67-68, 2004.
10

---

Published as a conference paper at ICLR 2020
Jie Zhou, Ganqu Cui, Zhengyan Zhang, Cheng Yang, Zhiyuan Liu, and Maosong Sun. Graph neural networks: review of methods and applications. CoRR, 2018.
Xiaojin Zhu and Zoubin Ghahramani. Learning from labeled and unlabeled data with label propa- gation. 2002.

---

Published as a conference paper at ICLR 2020
A
NOTATIONS
The notations used in the paper and their descriptions are listed in Table 5
Table 5: Notations and their descriptions
Notations
Descriptions
g
A graph
V
The set of nodes in graph
o/ 0/v:
Node 1/1; in V/
The set of edges in a graph
Creryy X
An edge that connects nodes v and vy
The node feature space
Zy
The feature vector of node e
We/ He
The ground-truth / predicted class label of node
Ny
The of neighbors of node
he Ae/hs
The representation vector of node v (in round k)
A mapping function
W
A parameter matrix
A(-)
An activation function
(1)
The coefficient of node "2 to node vy (in round k)
The context vector of node v (in round k)
The ground ground-truth context vector of node v (in round k))
The noise the context vector of node (in round k))
The surrounding vector of node (in round k)
dx
The dimension a representation vector (in round k)
Probability density function (PDF) estimated by the term xfF) (in round k)
S(k)
Probability density function (PDF) estimated by the term Ev,eN, 0ij Co (in round k)
(k)
(SI(S)
The Kullhack-Leibler divergence between S and C
Xy
Feature smoothness
A
Label smoothness
Vector concatenation
Manhattan norm
I(-)
An indicator function
a
Attention parameters (vector)
fn
Topology feature of node
G.
subgraph built based node iN
G
The set of subgraphs G.,
B PROOF OF THEOREM
Proof. We use the variance of fh; to measure the power of noise. Without loss of generality, we assume that the signal 2ff-11) is uncorrelated to the noise m!ly (16-11) and noise is random, with a mean of zero and constant variance. If we define
(k=11)
Var(it (k 1) E ( -1)] =0?
then after the weight aggregation, the noise power of EnJeN., (ij
(k-1), (k-1) is
City
Var Σ v,EN
oi (k-1)
- E
1 EuyeNs
nip -1()-1)) 2 (k-1) (.-1)
'
Σ EnjeN,,
(k-1))
1102
0². E EnjeN,
(als 1/
12

---

Published as a conference paper at ICLR 2020
C PROOF OF THEOREM 4
Proof. For simplicity of presentation, let X' = X6, d = do. C C( and S = S(0), For DEL (S] since the PDFs of and S are unknown, we use a nonparametric way, histogram, to estimate the PDFs of C' and S. Specifically, we uniformly divide the feature space X = [0. 1]d ). whose length is & and dimension is To simplify the use of no- tations, we use |Hie and [His to denote the number of samples that are in bin H; Thus, we have
into yd bins {H1, H2,..., Ha
DRL(S|IC) DKL(S)IC)
H 2|
log
2
|i,le 2
1=1
1
|H
Hs log
2
|H,|c
1
Hils log |His
Hils log (Halc)
2|E]
nd
1
Hils log Hils Hils log ([H + A.))
2
where A, = HHlc HHlss Regard A, as an independent variable, we consider the term
EE HHis log (|Hi]s + A,) with second-order Taylor approximation point
H.ls log (HH +
Σ H.ls
(log Hals + In2 A.
ln2
4?)
[H 2(1H),ss²
1=1
Note that the numbers of samples for the context and the surrounding are the same, where we have
Σ H. =
Hils = 2 |8).
Thus, we obtain
y
A 0.
Therefore, the DKL(Š(()) can be written
(51(5) x (
1
H. log Hils
Hils log (HHlls + A.))
In2 A: Hils log Hals + H,ls
In
Hils log
Hi
2 2(HH.ss) A?)
2|
i=1
1
In
A
In 2- 4,
2
2 2
In
A?
Hils
which is the Chi-Square distance between |He and Ha If we regard |Hi as constant, then we have: if A? are large, the information gain D Dx (S((CC tends to be large. Formally, consider the
13

---

Published as a conference paper at ICLR 2020
samples of C' as {ar E V} and the samples of S as f IW.l EveN, Tol 2e Fot of node u, we have the expectation and variance their distance as
V) with counts [
Nual Fv - E
Fer 0,
Var (Wol Io
EVEN. xer)) [ Io EVEN. xer) 20. 0.
For simplicity, for the distribution of the difference between the surrounding and the context, Will Te En'N,, Fel, consider it as noises the "expected" signal as the surrounding, |AG. EVEN, Iv', where the context Zu is the "observed" signal. Apparently the power of the noise on the samples is positively correlated with the difference between their PDFs, which means that large Var (|Wol Iv EV',, Twe) would introduce large difference between |Hils and H:lc. Then, obtain
rd
Var Var(INol.c. -EeEx zw))
Hi|s
then it easy to obtain
DKL(S|IC) 2
A?
Var (Wall -00 Ewee, Fw))
H.
Recall the definition of X,, if Fv. and Bryy independent, have
, Ever (EveN, (I - (Fo- N.r)
18l-d
|| Evev (wol -x. -EVEN, zee )=0))1
18l.d
Var Varrlaall
To EVEN, Zne )}1
[V--181 .d
Var (Moo
-vees 2v)
Therefore, we obtain
pd
In 2
A
Var (INol (oVol-x0- Even, zv) Aç.
DKL(S
His
o = O, we have that nodes have the same feature vector T., Obviously, DRL(Š1(C) =0.
D DATASETS
Table 6: Dataset statistics
Dataset
Citeseer
Cora
PubMed
Amazon (computer)
BGP (small)
BGP (full)
3,312
2,708
19,717
13,752
10,176
63,977
4,715
5,429
44,327
245,861
206,7 799
349,606
Average degree
1.42
2.00
2,25
17.88
20.32
5.46
Teature dim.
3,703
1,433
500
767
287
287
classes num.
10
Xy (10 ?) A
2.7593
4.2564
0.9078
89.6716
7,4620
5.8970
0.2554
0.1900
0.2455
0.2228
0.7131
R00.133
Table presents some statistics of the datasets used in our experiments, including the number of
nodes > the number of edges E|, the average degree, the dimension of feature vectors, the number
14

---

Published as a conference paper at ICLR 2020
of classes, the feature smoothness Ay and the label smoothness A, The BGP (small) dataset was obtained from the original BGP dataset, i.c., BGP (full) in Table by removing all unlabeled nodes and edges connected to them. Since BGP (full) contains many unlabeled nodes, we used BGP (small)'s A as an estimation. As we can see in 6 the three citation networks are quite sparse (with small average degree), while the other two networks are denser. According to the feature smoothness, Amazon (computer) has much larger Ay than that of the others, which means that nodes with dissimilar features tend to be connected. As for the label smoothness A,, the BGP network has larger value than that of the others, meaning that connected nodes tend to belong to different classes. description of each of these datasets is given as follows.
Citeseer (Sen ct al. 2008) is a citation network of Machine Learning papers that are divided into 6 classes: (Agents, AI, DB, IR, MI., HCT). Nodes represent papers and edges model the citation relationships.
Cora (Sen et al. 2008 is citation network of Machine Learning papers that divided into 7 classes: {Case Based, Genetic Algorithms, Neural Networks, Probabilistic Methods, Re- inforcement Learning, Rule Learning, Theory). Nodes represent papers and edges model the citation relationships.
PubMed (Namata et al., 2012) is a citation network from the PubMed database, which contains set of articles (nodes) related to diabetes and the citation relationships (edges) among them. The node features are composed of TF/IDF- word frequencies, and the node labels are the diabetes type addressed in the articles.
Amazon Product (McAuley et al. 2015) is co-purchasing network derived from the Ama- zon platform. Nodes are computers and edges connect products that were bought together. Features are calculated from the product image, and labels are the categories of computers. We used the processed version by Alex Shchur GitHub.
Border Gateway Protocol (BGP) Network (Luckie et al. 2013) describes the Internet's inter-domain structure, where nodes represent the autonomous systems and edges are the business relationships between nodes. The features contain basic properties, e.g., the lo- cation and topology information (e.g., transit degree). and labels means the types of au- tonomous systems. We used the dataset that was collected in 2018 0018-122 8--31 and published in Center for Applied Internet Data Analysis.
E PARAMETERS
For struc2vec and GraphWave, we used their default settings to obtain the node embeddings for all nodes since they are unsupervised. For struc2vec, we set their three optimization as "True". The embedding dimension of struc2vec is 128 and that of GraphWave is 100. Then based those embeddings, we put them in a logistic model implemented by (Perozzi et al.] 2014). where the embeddings of the training set were used to train the logistic model and the embeddings of the test set were used to obtain the final F1-Micro score. Label Propagation is a semi-supervised algorithm, where nodes in the training set were regarded nodes with labels, and those nodes in the validation set and test set were regarded as unlabeled nodes.
The feature-based methods and GNN methods used the same settings: the batch size was set as 512; the learning rate was set as 0.01; the optimizer was Adam. Except GraphSAGE, which set the epoch number as 10, all the other methods were implemented with the early stop strategy with the patience number set as 100. Other parameters were slightly different for different datasets but still the same for all methods. Specifically, for Citeseer and Cora, the dropout was set as 0.2, and the weight decay was set as 0.01. And the hidden number was set as 8. For PubMed, the dropout was set as 0.3, but the weight decay was set as O. The hidden number was 16. For Amazon (computer), BGP (small) and BGP (full), the dropout was set 0.3, and the weight decay was set as O. The hidden number was 32. As for GAT and CS-GNN, the attention dropout was set as the same as the dropout. And the dimension of topology features in CS-GNI was set as 64. Note that the residual technique introduced in GAT was used for the GNN methods. As for the activation function in CS-GNN, ReLU was used for feature leveraging and ELU used for the attention mechanism.
15

---

Published as a conference paper at ICLR 2020
Table 7: The F1-Micro scores of GraphSAGE with different aggregators
FI-Micro (%)
Dataset
Citeseer
Cora
PubMed
Amazon
BGP (small)
BGP (full)
Aggregators
GCN
71.27
80.92
80.31
91.17
51.26
54,46
GraphSAGE-GG
68.57
83.61
81.76
88.14
49.64
48.54
GraphSAGE-mes
69.02
82.31
87.42
90.78
64.96
63.76
GraphSAGE-LLTMM
69.17
82.50
87.08
90.09
65.29
64.67
GraphSAGG-pooo (max)
69.47
82.87
87.57
87.39
65.06
64.24
F
THE PERFORMANCE OF GRAPHSAGE WITH DIFFERENT AGGREGATORS
Table the F1-Micro scores of GCN and GraphSAGE with four different aggregators: GCN, mean, LSTM and max-pooling. The results show that for GraphSAGE, except on PubMed and BGP, the four aggregators achieve comparable performance. The results of GCN and GraphSAGE-GCY are worse than the others for PubMed and the BGP graphs because of the small information gain (i.e.. small Xy) of PubMed and the large negative disturbance (i.e., large A₁) of BGP as reported in Table and Section 4.2 As explained in Section 3.3 GCN uses additive combination merged with aggregation, where the features of each node are aggregated with the features of its neighbors, As result, GCN has poor performance for graphs with small A and large Å because it merges the con- text with the surrounding with negative information for given task. This is further verified by the results of GraphSAGE using the other three aggregators, which still have comparable performance on all the datasets. Section 4 we report the best F1-Micro score among these four aggregators for each dataset as the performance of GraphSAGE.
G THE KULLBACK-LEIBLES DIVERGENCE MUTUAL INFORMATION
We use the Kullback-Leible Divergence (KLD), instead of using Mutual Information (MI), to mea- sure the information gain from the neighboring nodes Section [22.1] because of the following reason. In information diagram, mutual information T(X; Y) can be seen the overlap of two correlated variables X and Y, which a symmetric measure. In contrast, DxI(X ( the extra part brought by X Y. which is measure of the non-symmetric difference between two probability distributions. Considering the node classification task, the information contributed by neighbors and the information contributed neighbors are different (i.e., mommsmmmmtric).. Thus, we use the KLD instead of MI.
can be seen
We remark that, although some existing GNN works (Velickovic al., 2019; Chen et 2019 use MI in their models, their purposes are different from our work. MI can be written as 7(X, DEL (P(X, P(X) x P(Y)), where P(X, Y) the joint distribution of X and Y, and P(X), P(Y) are marginal distributions of X and Y. From this perspective, we can explain the mutual information of and Y as the information loss when the joint distribution is used to approximate the marginal distributions. However, this is not our purpose in node classification.
16


Reviews:
[{"review_id": "ryxJ4-ExqH", "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 proposes two smoothness metrics to measure the quantity and quality of the graph information that GNNs employ in the model. With the smoothness measures, this paper proposes a new GNN model to improve the use of graph information. Overall, the paper is well-organized and clearly written. The main concern is the novelty, since the proposed method is pretty close to the graph attention network (GAT), except using the two smoothness metrics and a slightly different way to compute the attention coefficients. Experimental results show marginal improvement over existing GNN methods on the node classification task. Given these aspects, it is not that convincing that the introduced smoothness metrics are necessary. I would like to recommend a weak reject for this paper.\n\n\nSuggestions to improve the paper:\n\n1) It would be better to provide more convincing evidence and motivation for the smoothness metrics, either in theory or empirical analysis.\n\n2) When describing the proposed method, organize the key differences in a more clear way. For example, add the proposed method directly in Table 1 and summarize the key differences in bullet points. Currently, this important part is deferred to Section 3.3, which may cause confusion for the readers to understand the paper.\n\n3) In Section 3.2, this paper claims that the proposed method can easily include side information on graphs to improve performance, by using the topology feature in the last fully connected layer for class prediction. However, this technique can also be used in existing GNN models, and it is not clear why this is described as something unique for the proposed method. Also, there is no corresponding ablation experiments to compare the performance of the proposed method with and without using local topology features.", "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 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": "SJlJQTncFH", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "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 study how neighbor information on graphs can be used in Graph Neural Networks. It proposes measures on whether the data in neighboring nodes are useful in terms of labels or features. It also provides a new Graph Neural Network algorithm that is a modification of attention-based models incorporating the derived label and feature smoothness measures. The paper demonstrates the usefulness of these measures and algorithms with several different baselines from different families. The writing is mostly smooth, and the authors seem to provide enough detail of the experiments performed.\n\nThe proposed measures look simple but effective (as demonstrated in Table 2). The paper compares different techniques and shows that when neighboring labels are not smooth, techniques such as label propagation does not help. I do recommend Table 4 Lambda f and Lambda l values to be included in the main paper (though text mentions). When incorporated into the attention-based GNNs, Figure 1 also shows that smoothness parameters of the techniques also improve. ", "extra_scores": {"experience_assessment": "I have read many 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 assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "H1ep9tkO9H", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Summary\n\nThe paper proposes two graph smoothness metrics for measuring the usefulness of graph information. The feature smoothness indicates how much information can be gained by aggregating neighboring nodes while the label smoothness assesses the quality of this information. The authors show that Graph Neural Networks (GNNs) work best for tasks with high features smoothness and low label smoothness by utilizing information from surrounding nodes which also tends to have the same label. Based on these two metrics, the authors introduce a framework, called Context-Surrounding Graph Neural Network (CS-GNN), that utilizes important information from neighboring nodes of the same label while reduce the disturbance from neighboring nodes from different classes. The results demonstrate considerable improvement across 5 different tasks. \n\nStrength\n\nThe authors advocate for better understanding of the use of graph information in learning, which is both an important and interesting problem. Two graph smoothness metrics appears to be intuitive and reflect common situations in graph-based data (1) features from neighboring nodes contribute differently to target node representation (2) neighboring nodes information sometimes causing disturbance if node with different labels tend to be connected. The paper provides some theoretical analysis that supports this claim and thorough experiments that show the correlation between the two proposed metrics with the performance of GNNs. \n\nWeakness\n\nWhile the paper is reasonably readable, there is certainly room for improvements in the clarity of the paper. First, I would suggest the authors to avoid too much word repetition as well as long, obscure sentences. For example, the first sentence of section 2.2 can  be rewritten as “GNNs usually contains an aggregation step to collect neighboring information and a combination step that merges this information with node features.” The flow of the paper is also hard to follow and need some rearrangement. For instance, paragraph 3 of section 2.1 can be pushed until section 3.3. Another suggestion about the flow is to separate section 2.2 into two subsections for features smoothness and label smoothness (also the title of this section need to be refined). Finally, the results would be more clear if separated into different tables or subsections/paragraphs.\n\nQuestions\n\n* Is there a particular reason for using the KLD instead of mutual information?\n* In 2nd sentence of section 2.2, what does “node’s own information” mean? If it is the individual node’s features then why it naturally the representation vector h_v (which is aggregated with neighboring nodes?)", "extra_scores": {"experience_assessment": "I have read many 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": {}}]

Author rebuttal:

Meta-review: Two reviewers are positive about this paper while the other reviewer is negative. The low-scoring reviewer did not respond to discussions. I also read the paper and found it interesting. Thus an accept is recommended.
Decision: Accept (Poster)