Towards Powerful Graph Neural Networks: Diversity Matters
Authors: Bingbing Xu
Huawei Shen
Qi Cao
Yuanhao Liu
Keting Cen
Xueqi Cheng
Venue:  (2021)
Keywords: GNNs
Expressive power
Diverse sampling
Injective

Abstract: Graph neural networks (GNNs) offer us an effective framework for graph representation learning via layer-wise neighborhood aggregation. Their success is attributed to their expressive power at learning representation of nodes and graphs. To achieve GNNs with high expressive power, existing methods mainly resort to complex neighborhood aggregation functions, e.g., designing injective aggregation function or using multiple aggregation functions. Consequently, their expressive power is limited by the capability of aggregation function, which is tricky to determine in practice. To combat this problem, we propose a novel framework, namely diverse sampling, to improve the expressive power of GNNs. For a target node, diverse sampling offers it diverse neighborhoods, i.e., rooted sub-graphs, and the representation of target node is finally obtained via aggregating the representation of diverse neighborhoods obtained using any GNN model. High expressive power is guaranteed by the diversity of different neighborhoods. We use classical GNNs (i.e., GCN and GAT) as base models to evaluate the effectiveness of the proposed framework. Experiments are conducted at multi-class node classification task on three benchmark datasets and multi-label node classification task on a dataset collected in this paper. Extensive experiments demonstrate the proposed method consistently improve the performance of base GNN models. The proposed framework is applicable to any GNN models and thus is general for improving the expressive power of GNNs.

Under review as a conference paper at ICLR 2021
TOWARDS POWERFUL GRAPH NEURAL NETWORKS: DIVERSITY MATTERS
Anonymous authors Paper under double-blind review
ABSTRACT
Graph neural networks (GNNs) offer us an effective framework for graph repre- sentation learning via layer-wise neighborhood aggregation. Their success is at- tributed to their expressive power at learning representation of nodes and graphs. To achieve GNNs with high expressive power, existing methods mainly resort to complex neighborhood aggregation functions, e.g., designing injective aggrega- tion function or using multiple aggregation functions. Consequently, their expres- sive power is limited by the capability of aggregation functiion which is tricky to determine in practice. To combat this problem, propose novel framework. namely diverse sampling, to improve the expressive power of GNNs. For a target node, diverse sampling offers it diverse neighborhoods, i.e., rooted sub-graphs, and the representation of target node is finally obtained via aggregating the rep- resentation of diverse neighborhoods obtained using any GNN model. High ex- pressive power is guaranteed by the diversity of different neighborhoods. We use classical GNNs (i.e., GCN and GAT) as base models evaluate the effective- ness of the proposed framework. Experiments are conducted at multi-class node classification task on three benchmark datasets and multi-label node classifica- tion task on a dataset collected in this paper. Extensive experiments demonstrate the proposed method consistently improve the performance of base GNN models. The proposed framework is applicable to any GNN models and thus is general for improving the expressive power of GNNs.
INTRODUCTION
Graph neural networks (GNNs) have been shown to be effective at graph representation learning and many predictive tasks on graph-structured data, e.g., node classification and graph classifica- tion (Kipf & Welling, [016 Xu et al.] 2018a). GNNs follow neighborhood aggregation scheme, where the representation of a node is obtained by recursively aggregating and transforming repre- sentation of its neighboring nodes (Gilmer et al., 2017). The success of GNNs believed to be attributed to their high expressive power at learning representation of nodes and graphs (Xu et al.) 2018a). Therefore, it is an important research problem to analyze and improve the expressive power of existing GNN models and design new GNNs with high expressive power.
Several recent works focus on the expressive power of GNNs. Xu et al. pointed out that the expres- sive power of GNNs depends the neighborhood aggregation function (Xu et al. 2018a). They develop a simple architecture, i.e., leveraging multi-layer perceptron (MLP) and a sum pooling as universal approximator defined multi-set, to achieve injective neighborhood aggregation function. With injective aggregation function in each layer, the proposed graph isomorphism network (GIN) has the expressive power as high as the Weisfeiler-Lehman (WL) graph isomorphism test (Weisfeiler & Lchman 1968). Similarly. Sato et al. implement powerful GNN via consistent port numbering. i.e., mapping edges to port numbering and neighbors are ordered by the port numbering (Sato al.) 2019). However, port ordering of CPNGNNs is not unique, and not all orderings can distinguish the same set of graphs (Garg et al. 2020). Principal neighborhood aggregation (PNA) defines multiple aggregation functions improve the expressive power of GNNs (Corso et al.) 2020 However, the number of required aggregation functions to discriminate multi-sets depends on the size of multi-set, which is prohibitive for real world networks with skewed degree distribution. In sum, existing meth- ods focus on designing an injective, often complex, aggregation function in each layer to achieve GNNs with high expressive power. However, injective functions are difficult to obtain and tricky to

---

Under review as a conference paper at ICLR 2021
determine in practice. Indeed, layer-wise injective function is not always required and what need an injective function defined over rooted sub-graphs or graphs as a whole.
In this paper. propose novel framework, namely diverse sampling, to improve the expressive power of GNNs. For a target node, diverse sampling offers diverse neighborhoods, i.c., rooted sub- graphs, and the representation of target node is finally obtained via aggregating the representation of diverse neighborhoods obtained using any GNN model. High expressive power is guaranteed by the diversity of different neighborhoods. For convenience, we denote with DS-GNN the GNN implemented under the proposed diverse sampling framework.
MLP
Aggrogation
Injective
MLP
Layer
Aggnegation
MIP
FC
MLP
Layer
Pag oeastio
Ouput
(4)
Simpll
One Injective Layar
GNN
Figure 1: The motivation of DS-GNN: constructing multiple sampled graphs rather than complex layer-wise aggregation functions (the node with red circle is the central node and "FC" represents fully connected layer).
Fig. fillustrates the main idea of the proposed DS-GNN, and compare it with two representative methods, i.e., GIN and PNA. Fig. (a) depicts the injective layer implemented via MLP or multi- ple aggregation functions, aggregating first-order neighboring nodes obtain the representation of central node. Injective layer are stacked to achieve overall injective function defined on rooted sub- uub-graphs. On the contrary. DS-GNN does not follow the line of designing complicated aggrega- tion functions in each layer. Instead, DS-GNN improve the expressive power of GNNs via obtaining diverse rooted aub-graphs for each node. Specifically, we sample nodes multiple times on the entire input graph based diverse sampling, and obtain multiple sampled sub-graphs for each node. After diverse sampling, we leverage the shared GNN model to get the representation for the central node, including its high-order neighbors. In this way, each node is represented by multi-set, consisting of the representations obtained from different sampled rooted sub-graphs. The final representation of central node is finally obtained via aggregating the representation of diverse neighborhoods.
Finally, we use classical GNNs (i.c., GCN (Kipf & Welling 2016) and GAT (Veličković et al. 2017) base models evaluate the effectiveness of the proposed framework. Experiments conducted at node-based multi-class classification task on three benchmark datasets and node-based multi- label classification task on dataset collected in this paper. Extensive experiments demonstrate the proposed method consistently improve the performance of base GNN models. The proposed framework is applicable any GNN models and thus is general for improving the expressive power of GNNs.
2 NOTATIONS AND PRELIMINARIES
We first introduce the general framework of GNNs.
2

---

Under review as a conference paper at ICLR 2021
G G= [V denotes undirected graph, where V is the set of nodes with |V| n. and A is the adjacency matrix with A,, = AA to define the connection between node and node j. E Ruxp denotes the feature matrix and the i-th row in X represent the attributes of i-th node. DS-GNN Modern GNNs follow a neighborhood aggregation scheme, which iteratively update each node's representation via aggregating the representation of its neighboring nodes. Formally, the k-th layer of GNN is
(1) where ((e) represents the neighbors of node v, Nh is the representation of node in the k-th layer, and ()) X Additionally, we introduce two representative base models: Graph Convolutional
(k) AGGGEGATE (h, u (u)),
h(4)) COM (aaa)
Network (GCN) (Kipf & Welling 2016) and Graph Attention Networks (GAT) (Veličković al.
2017) in Appendix A
3 DIVERSE SAMPLING BASED POWERFUL GRAPH NEURAL NETWORK
Considering that the injectivity each node with its neighbors making GNNs be possessed with the most powerful ability for node-level task, i.c., representations be distinguishable for two nodes when they have dissimilar attributes or different neighbors, we devote to designing powerful GNN reach such injectivity, thus increase its expressive power. Specifically, we propose novel framework, i.c., Diverse Sampling (DS-GNN), to increase the expressive power via constructing diverse rooted sub-graphs for each node. In this section, first give the framework of our DS- GNN. Then we will introduce the important parts of DS-GNN, including diverse sampling strategy that ensure the diversity among each sampling, as well as the part of model learning. We also theoretically analyze how the proposed DS-GNN can improve the expressive abilities when added to generic GNNs.
3.1 METHOD
Base GNN
MLP
Sample
Base GNN
MLP
Loss
Base
MLP
Figure 2: Architecture of DS-GNN.
The framework of DS-GNN is illustrated in Fig. For the input graph, instead of running GNN on the entire graph, we first do node sampling with K-times and then obtain K sampled graphs. During sampling, we calculate the sampling probability for each node and randomly retain the node based on the probability. If one node not sampled, means that the node and all edges connected with it will be removed from the graph. The updated adjacency matrix and feature matrix of each sampling are fed into the base GNN model, and the GNN is shared over all samplings. Then we obtain representation for each sampled node corresponded with one input sampled graph. Thus, one node is sampled more than one time, we will obtain multiple representations.
To get the final representation of each node, need to integrate these representations. To hold the injectivity when integrating representations, we adopt a multi-layer perceptrons (MLP) followed by the sum aggregation to achieve the injective multi-set aggregation function. Once getting the final representation for each node, we calculate the loss function and optimize the model.
Sampling Strategy

---

Under review as a conference paper at ICLR 2021
Intuitively, with a large number of sampling numbers, the sampling results are expected to retain the information of entire graph. Thus previous methods, e.g., Dropedge (Rong et al., 2019) which samples in each training epoch, do not need to carefully design the sampling strategy and they keep all edges when testing and validation. Meanwhile, they fail to achieve diverse sampled graphs in testing. Different from previous methods, we need to hold the K sampled graphs in testing and keep training and testing consistently. To solve this, we only sample the entire graph K-times, and leverage these sampled K graphs in all training epochs, well as the validation and testing. To guarantee the performance of the proposed DS-GNN when even small K is chosen, we carefully design the important diverse sampling strategy.
To ensure the reuse of sampling results, we propose node sampling to obtain K sampled graphs. In one sampling, the neighbors of each node are obtained from the same sampled graph. For the sampling probability of nodes, the most intuitive way is to set the same initial probability for each node, which is Pinit- However, this method may require a large number of sampling numbers K. In order to further speed up or get an effective sampling plan, we also propose three intuitive guidelines for sampling strategy: 1) to ensure the coverage of samples, each node should appears at least in one sampled graph; 2) to achieve the diversity among samples, of each node should decrease when its sampled times in previous is already large; 3) to retain the important node in the original network and adopting the node degree the importance indicator, we assume that the sampling probability of each node should increase when its degree in original network is large. Mcanwhile, we also considering the previous sampled results, discounting the sampling probability of cach node when the its degree in previous sampled graphs is already large. That's to say, the sampling probability of each node increase with the increase of node degree in original network, and decrease with the increase of node degree in previous sampled graphs. To achieve the above three guidelines, we need to relate the sampling probability of each node to the historical sampling results. Next, we will introduce in detail how we do.
assume that the sampling probability
Let represent the total number of samples, Po,i represent the probability of node w in the i-th sampling, and Ho, represent the number of times that the node r has been sampled before the i- th sampling. To achieve guideline 1), we should guarantee that the probability for a node, which has never been sampled in history K-1 samples, equals to at the K-th sampling. In other words, Pr.k = 1 when Hy.k = O. Additionally, to achieve the diversity guideline of 2), the sampling probability Po,s should decrease with the increase of historical sampled numbers H., Together, the sampling probability of node u for the i-th sampling is defined as:
Hp.
Pes = Pinst + (1 Pinit) x
K
To achieve guideline of 3), a new sampling strategy is designed. Specifically, we define sammpl as the degree of node in the j-th sampled graph, and D, the degree of node v in the original graph. To make the sampling probability increase with Da, as well as decrease with D Dammple mentioned in guideline 3), we define the coefficient D0a? as:
Dejj
0,5
E (D,, Daamle
Doep U,
(3)
Ej=1 Do
To achieve our three guidelines in total, we integrate the Eq and Eq probability for node v in the i-th sampling as:
3 and define the sampling
Hogi
Pv.i = Pixat + (1 - Pinse) x
x Doap
(4)
K
Note that our sampling strategy is different from previous methods, i.e., dropping features and drop- ping edges. The Dropout (Srivastava et al.) 2014) is proposed to prevent over-fitting by randomly dropping features. Dropping edges can be regarded tures to dropping edges. However, dropping edges may cause that two nodes who are the same with identical neighbors obtain different representations, since dropping edges may cause these two nodes result in different neighbors after edge sampling. In contrast, we propose node sampling strategy, ensuring that the nodes with the same input features and neighbors will still have the same
generation of Dropout from dropping fea-
4

---

For these two tasks, the loss function is defined as the cross-entropy over all labeled nodes as Under review as a conference paper at ICLR 2021
representation. We give the detailed introduction of some previous methods, included in dropping edges in Appendix
Model Learning
In the following, we describe detail how DS-GNN can be applied to any base GNN to achieve a more powerful GNN model. Specifically, first do K samplings the input graph A via the above introduced diverse sampling, getting the sampled graphs [A1, A2, ... Ax in a pre- pre-procsssing step. Then we applied a base GNN model to obtain the representations of nodes in sampled graphs spectively, each layer is formulated as.
(5) where h is the representation of node at the 1-th layer in the k-th sampled graphs, and N&(v) denotes the neighbors of node v in the k-th sampled graphs Ag.. For each node, we obtain K repre- sentations {he (1.)) Ate (2.1)
A (k.)) COMBINE ! (1(4-111, AGGREGATE" (n (hik.-1), (x))),
he (K.))) } from the L-th layer of base GNN based on the K sampled graphs. Note that if a node not sampled in one sampling, we fill its representation with to ensure that each node has K representations. In order to integrate them into one representation. we fed them into a MLP with two fully connected layers, and then sum the transferred representations after MLP. Note that the MLP is shared over all samplings. Let O, denote the output representation of node v, O, calculated as
O, Σ MLP(H.)P))
To verify the ability of DS-GNN model, we adopt node-level tasks, i.e., node based multi-class classification and node-based multi-label classification, the target task. Note that in multi-label classification, each node has multiple labels. Let LLabel denote the set of labeled nodes and m is the number of total labels. Y,. equals if node has label c, otherwise O. For node-based multi-class classification, the output probability vector 2, is calculated by applying "Softmax" funtion to the output representations O,;
Z, Softmax(O.).
For node-based multi-label classification, 2, is calculated by applied "Sigmoid" funtion instead:
2. Sigmoid(O.).
m
Σ
Σ
Yve In Zuc.
LEVaabel
3.2 TOWARDS HIGH EXPRESSIVE POWER
Recall that, in this work we devote to achieving injectivity on nodes increase the expressive power of GNN, i.e., for any two nodes with different attributes or different neighbors, the model can output different representations for them. In this section, we theoretically analyze whether our proposed DS-GNN method can achieve this goal. Note that the MIP applied to the K representations in Fig. 2 followed by the sum operator can achieve injectivity when integrating the multi-sets (Hornik al. 1989 Xu et al.) 2018a). As result, to prove the injectivity nodes of the proposed DS-GNN, we only need prove that two nodes with different neighbors have different multi-sets of the K representations.
For simplicity, we denote the representation of node u on the i-th sampled graph under layers base GNN model, i.e., 1 (t,L)
Formally, for two nodes, i.e., node and node v, with different attributes or different neighbors on the original graph, the multi-sets their representations based on the K sampled graphs under L layers base GNN model are:
Multi set(u) {u1, ... ugk ).
Multi set(v) (er, u2.... UK
(10)
We provide the following theorem and prove in Appendix C to demonstrate that we can obtain different multi-sets for these two nodes with high probability.
5

---

Under review as a conference paper at ICLR 2021
Theorem As the number of samples increases, the probability that the multi-sets for two nodes with different attributes or different neighbors are different can be close to
On the basis of the high probability of obtaining different multi-sets and the proven injective multi- set function, i.c., MLP followed by "Sum", , the injectivity can be achieved among nodes.
Note that for the two nodes who are the same, i.e., they have the same attributes and neighbors, DS- DS-GNN also ensure that they have the same representation. This is because that we adopt node sampling instead of edge sampling. Under node sampling, the two identical nodes will lose this neighbor at the same time, otherwise, keeping the neighbor, as well as the representations obtained by base GNN model stay the same.
EXPERIMENTS
We use GCN and GAT as our base models and implement them under our proposed DS-GNN framework respectively, referred DS-GCN and DS-GAT. The effectiveness of DS-GCN and DS- GAT is evaluated on three benchmark datasets via multi-class classification. Detailed analysis of sampling times and sampling strategy are also provided. In addition, to enrich the type of node-level tasks, we also offer an multi lablll classification task on newly collected dataset from DouBan website namely DBMovie.
4.1 EXPERIMENTAL SETTINGS
We use Tensorflow to implement the proposed model and take Adam with an initial learning rate of 0.01 as optimizer. For the three benchmark datasets, set weight decay of 0.0005. For DBMovic, we do not use weight decay. Note that for the i-th sampling, we sample 10 times and take the average of these 10 sampled garphs the result of the i-th sampling, preventing the instability of a single sampling. All GNN models has two layers and leverage Relu as the activation function of hidden layers. We add ResNet (He et al. 2016) between the second GNN layer and the output layer. We run 1000 epochs and choose the model that performs the best on validation.
4.2 BASELINES
For the three benchmark datasets, GNNs have achieved large improvements than traditional meth- ods. As a result, we choose the the representative GNN models, i.e., GCN (Kipf & Welling 2016).
GAT (Veličković et al. 2017). the base GNN models and apply our DS-G DS-GNN to these two models. Additionally, we compare against the SOTA GNNs, including GraphSAGE (Hamilton et al.) 2017] GIN (Xu et al. 2018a) and DropEdge (Rong et al. 2019). For the newly collected DBMovie dataset, we first consider traditional node classification methods as our baselines, including Multi-Layer Per- ceptrons (MLP), which only node features, and graph embeddings (DeepWalk) (Perozzi al.) 2014), which only use graph structures. Since GNNs are proved to be effective in graph-based learning, also compare against GCN and GAT.
Table 1: The Statistics of Datasets
Datasets
Nodes
Edges
Classes
Features
Train/ SaainValidation//ee
Node-level Task
Cora
2,708
5,429
7
1,433
1,208/500/1 1,000
Multi-class
CiteSeer
3,327
4,732
6
3,703
1.812/500/1.0 1,000
Multi-class
PubMed
19,717
44,338
3
500
18,217/500/1 ,000
Multi-class
DBMovie
21,659
221,138
28
3,000
20.159/500/ 1,0000/0000000000000000000000000
Multi-label
4.3 BASED MULTI-CLASS CLASSIFICATION
To evaluate the proposed method on node-based multi-class classification, we conduct experiments on the three benchmark datasets, namely, Cora, CiteSeer, PubMed. The first three rows in Table [ show an overview of these three multi-class datasets. To better verify the ability of each model and
http:://mmovic.ouuaa.coomm

---

Under review as a conference paper at ICLR 2021
eliminate the effect of other factors such as data insufficiency, we follow the data split in DropE- dge (Rong et al. 2019).
Performance Node-based Multi-class Classification
Method
Cora
CiteSeer
PubMed
Sampling Number
GIN
85.7%
76.4%
89.7%
GraphSAGE
87.8%
78.4%
90.1%
PropEdge-GCN
86.5%
78.7%
91.2%
GCN
86.1%
75.9%
90.2%
DS-GCN
88.0%
79.9%
90.5%
GAT
87.4%
77.8%
87.9%
DS-GAT
88.2%
80.0%
91.0%
0.00
Table 2: Results of Node-based Multi-class Classifica- tion
Figure 3: The impact of sampling time K
Experimental results are reported in Table 2 Additionally, we provide the corresponding standard deviation in Appendix [D] Similar to previous research, report the mean classification accuracy over nodes test set for quantitative evaluation. DS-GNN methods all achieve improvements over base models (indicated by the bold numbers), e.g-- in CiteSeer, DS-GCN (79.9%) achieves large improvement over GCN (75.9%). Furthermore, applying our proposed method to the base GNN models can achieve the better performance, outperforming the state-of-the-art models. Compared with DropEdge which takes GCN as base model, our DiverseSample (DS) mechanism achieves better or comparable results.
Analysis of Sampling Numbers K
To analyze the impact of sampling times K, we show the accuracy of Cora with different K in Fig. It is observed that the accuracy increases as K becomes larger at the beginning. This is owing to the increasing probability of achieving injectivity. When continues to increase, the injective probability becomes stable and close to 1, resulting in the accuracy also showing a stability. The results show that we can achieve better experimental results with small K, e.g., = 5 in Fig. 3 which proves the practicability of our method.
Analysis Sampling Strategy
CituSeer
0.00
6.0
0.77
6.76
8.7
Random Diversa Sample
Random
Diverse Sample
Figure 4: Diverse sampling VS Random sampling
To evaluate the effectiveness the proposed diverse sampling strategy, we compare with random sampling strategy. Fig. show the accuracy of Cora and CiteSeer with different initial node sampling probability Pinét respectively when sampling times K = 5. The results demonstrate that: 1) the performance of random sampling will be significantly affected by Pinit- The model performs poor with a relatively small Pinats while the model effect is significantly improved when Pinit increases. Thus, random sampling requires relatively large Pinit maintain the sampling effect and model

---

Under review as a conference paper at ICLR 2021
performance. 2)
The performance of Diverse sampling is relatively stable, obtaining comparable performance even with a small Pinit- This is owing to diverse sampling considers the three guidelines mentioned earlier, which proves the effectiveness of the diverse sampling strategy proposed.
Furthermore, under diverse sampling, we observe that the best Piait are different among datasets. better results achieved under smaller Pinit, diverse sampling random sampling. Also, it is observed that Cora performs well with a larger Pinits while CiteSeer achieves better performance when Pinit is smaller, i.e., Cora tends to keep more edges in sampled graphs. Similarly, PubMed also performs better when Pivit is smaller. The reason may be related to the property of label smoothness "X" proposed in CS- CS-GNN (Hou et al., 2019). which measures the quality of surrounding informations. A larger À implies that nodes with different labels are connected in the graph. CS-GNN, Cora has smaller X 0.19, while Citeseer with a larger A 0.26 well as PubMeb with À = 0.5. These values indicate that the surrounding informations are of higher quality in Cora, which explain why Cora prefers to keep more edges.
achieve improvements over
4.4 NODE-BASED MULTI-LABEL CLASSIFICATION
To enrich the type of node-level tasks, we collect a new dataset from the DouBan website and offer an multi-label classification task. Each sample in this dataset has its descriptions (features), genres (labels), and similar movies (edges), as illustrated in Fig. These similar movies (edges) are directly provided by DouBan website based on user co-preference. This dataset has 28 labels and each movie may have more than one label. We define the task as tagging the movie with its own labels. The last row in Table shows an overview of the newly collected DBMovie dataset.
Labels: Drama: Romance; Disaster
Method
MAP
F1@3
NDCG@3
Feature: 100 year-old named Rose tells the story to her granddaughter about life on ship called Titanic...
MLP
54.9%
39.4%
50.6%
DeepWalk
61.6%
44.7%
59.1%
THIIC
GCN
83.2%
60.2%
82.1%
DS-GCN 83.6%
60.5%
82.6%
GAT 83.3%
60.5%
82.6%
DS-GAT 84.0%
61.0%
83.0%
Table 3: Results of Node-based Multi-label Clas- sification
Figure 5: One Sample of DBMovie
Performance on Node-based Multi-label Classification
We now validate the effectiveness of DS-GCN and DS-GAT. For node-based multi-label classifica- tion, we leverage the widely used ranking metrics evaluate method, including Mean Average Precision (MAP), F1, and Normalized Discounted Cumulative Gain (NDCG). These metrics en- courage the correct label be placed ahead of irrelevant labels, and a larger value indicates better performance. Experimental results on DBMovie are reported in Table 3 In the multi-label clas- sification task, GNN models, i.e., both GCN and GAT, also perform much better than traditional methods, including MLP (only using attributes) and DeepWalk (only using only). GAT performs better than GCN, owing to its attention mechanism to learn edge weight. Under all evaluation met- rics, our proposed method achieves consistently improvement over GCN and GAT, showing an increased expressive power of model.
CONCLUSION
We proposed DS-GNN to improve the expressive power of graph neural networks. Different from previous methods that aim to implement injectivity via designing complicated layer-wise aggrega- tion functions, we focus on designing the diverse rooted sub-graphs for each node. To enhance the diversity of rooted sub-graphs, we design the diverse sampling strategy. As the number of sam- ples increases, we can achieve injectivity with higher probability. Extensive experiments on node- based multi-class classification and mode-based lulti-label classification prove that method can achieve improvements over the baselines. In the future, we consider to extend our method to graph classification scenarios.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Gabriele Corso, Luca Cavalleri, Dominique Beaini, Pietro Liò, and Petar Veličković. Principal neighbourhood aggregation for graph nets, arXiv preprint arXiv:2004.0577 05718. 2020.
Vikas K Garg, Stefanie Jegelka, and Tommi Jaakkola. Generalization and representational limits of graph neural networks. arXiv preprini arXiv:2002.06157 2020.
Justin Gilmer, Samuel S Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. arXiv preprint
2017.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs. In Advances in neural information processing systems, pp. 1024 1034, 2017.
Arman Hasanzadeh, Ehsan Hajiramezanali, Shahin Boluki, Mingyuan Zhou, Nick Duffield, Krishna Narayanan, and Xiaoning Qian. Bayesian graph neural networks with adaptive connection sam- pling. arXiv preprint arXiv:2006. 04064, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. In Proceedings of the IEEE conference on computer vision and pattern recognition, pp- 770-778, 2016.
Kurt Hornik, Maxwell Stinchcombe, Halbert White, et al. Multilayer feedforward networks are universal approximators. Neural networks, 2(5):359-3366 366, 1989.
Yifan Hou, Jian Zhang, James Cheng, Kaili Ma, Richard TB Ma, Hongzhi Chen, and Ming-Chang Yang. Measuring and improving the use of graph information in graph neural networks. In International Conference Learning Representations, 2019.
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. In Advances in neural information processing systems, pp. 4558 4567, 2018.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: 16X9.006090 2016.
Bryan Perozzi, Rami Al-Rfou, and Steven Skiena. Deepwalk: Online learning of social repre- sentations. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710, 2014.
Yu Rong, Wenbing Huang, Tingyang Xu, and Junzhou Huang. Dropedge: Towards deep graph convolutional networks on node classification. In International Conference on Learning Repre- sentations, 2019.
Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Approximation ratios of graph neural networks for combinatorial problems. In Advances in Neural Information Processing Systems, pp- 408 1- 4090, 2019.
Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: simple way prevent neural networks from overfitting. The journal of machine learning research, 15(1):1929-1958, 2014.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Lio, and Yoshua Bengio. Graph attention networks. arXiv preprint arXiv: 10903, 2017.
Boris Weisfeiler and Andrei A Lehman. reduction of a graph to canonical form and algebra arising during this reduction. Suuchmo-Teccnicheskayy Informatsia, 2(9):12-16, 1968.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural networks? arXiv preprint arXiv: 1810. 1810.00826, 2018a.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning graphs with jumping knowledge networks. arXiv preprint arXiv:1806.03336, 2018b

---

Under review as a conference paper at ICLR 2021
A DESCRIPTION OF BASE MODELS
The two basic models Graph Convolutional Networks (GCN) and Graph Attention Networks (GAT) output the probability distributions Z over labels for all the nodes. Formally, the probability distri- butions are calculated as follows
Z = f(X, A) = -
(11)
where W E RRxdd and W E Rdxm are weight matrices with d as the dimension of the hidden layer. The first layer leverages rectified linear umit (ReLU), and the second layer leverages softmax to obtain a probability distribution E Rax= Z row-normalized matrix, where each row represents the probability that the node belongs corresponding labels.
In GCN, Å = D à AD- à is the symmetric normalized adjacency matrix with À = A + I, and I is the identity matrix. D goxn is the diagonal degree matrix with Di: E3 Asj-
While, GAT modifies A by introducing the attention mechanism:
cxp(LeakyRollU(o (hulll (hillhy))
AU EkEN(.)) exp(LeakyReLU(( [hil[ha]))
(12)
where N(v)) is the set of neighboring nodes of node 14 E IR2d is the attention vector, h4 E Rd is the representation of the i-th node, and is the concatenation operator.
B THE DIFFERENCES BETWEEN NODE SAMPLING AND OTHER RELATED CONCEPTS
We contrast the differences between node sampling and other related concepts including dropping features and dropping edges. The Dropout (Srivastava et al.) 2014) is proposed to prevent over- fitting by randomly dropping features. Dropping edges can be regarded as generation of dropout from dropping features to dropping edges. DropEdge (Rong al. 2019) proposed randomly setting the elements in the adjacency matrix to be zeros. Also, some recent methods, including Graph- SAGE (Hamilton al., 2017). ASGCN (Huang et 2018), can be seen as dropping edges. These methods extend GNN to large graphs by sampling neighbors for each node, i.e., sampling neighbor equivalent to sampling an edge. Hasanzadeh (Hasanzadeh et al., 2020) propose a general frame- work for these methods. However, for our method, dropping edges may cause that two nodes who are the same with identical neighbors obtain different representations, since dropping edge cannot guarantee that these two nodes still have identical neighbors after edge sampling. Thus we leverage node sampling, ensuring that the nodes with the same input features and identical neighbors will still have the same representation.
C PROOF OF THBOREM
Theorem As the number of samples increases, the probability that the multi-sets for two nodes with different attributes or different neighbors are different can be close to
Proof: Let denote the probability that representations of node u and node are same on the i-th sampled graph, i.e.,
Probability(u4 = vx).
(13)
Let q denote the the probability that representations of node u and node v are same on two different sampled graphs, i.e.,
= Probabilityy = m;) for i i
(14)
It's reasonable to assume that such probability based on different sampled graphs is smaller than base on the same sampled graph, i.e., q <= p.
For the two multi-sets, without losing generality, we can sort the element in each multi-set by de- scending order based on a specified uniform ordering rules. After sorting, the two multi-sets can be written as
Multi set(ūi
(Miy Vigz" -igg
Multi set(o) {(1j (Uj "ix, (15)
10

---

Under review as a conference paper at ICLR 2021
where ig represent the original index of ui in Multi - set(u), as jk- For these two sorted multi- sets, if and only their elements be equal at each position, these two sorted multi-sets can be the same, otherwise they are different.
As we defined, the probability of "U; = "j is smaller than p. thus the probability that two multi- sets are the same can be defined following based on Bayesian Equation:
probabilityMullti set(ū) = Multi - set( ()) -
(16)
p p(u;, 2/a l4, v,
p(uix 2/x Ma U/ dix-1 U)n-1)-
Therefore, the probability that the injectivity can be achieved between the multi-sets is larger than probability (Multi set(ú) (u) = Multi - (e). Since a and v have different attributes or neighbors, each item in Eq. T6 can be smaller than 1. Thus, with large number of samplings, we can achieve injectivity with a high probability.
D STANDARD DEVIATION OF NODE-BASED MULTI-CLASS CLASSIFICATION
Table 4: Results with Standard Deviation of Node-based Multi-class Classification
Method
Cora
CiteSeer
PubMed
DS-GCN
88.0%
79.9% 8..6%
90.5%=10199%
DS-GAT
88.2%:10.319
91.0%


Reviews:
[{"review_id": "eB32BJqEXl", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors propose to sample nodes of a given graph multiple times to form a set of K sub-graphs. GNNs are then applied on each sampled graph for learning node representations. For each node, all representations are combined for the downstream tasks. The idea of doing multiple sampling is to increase the chance that nodes with different neighborhoods can be more different in the set of sampled graphs, than only considering the original single graph. In contrast, nodes with same neighborhood will remain the same over all sampled graphs. This mechanism helps discriminate node representations better.\n\nThe key technical contribution of the paper is the proposed sampling strategy, which, with several proposed guidelines, is designed to reduce the possible number of samples K. The strategy is mostly an empirical design. It is good to see some analysis on how do the sample times affect the difference of node representations, but it seems to be very intuitive.\n\nAs such, the technical contribution of this paper is limited. The idea to use multiple samples to improve performance seems also a straightforward way to improve the coverage of nodes' local structures.\n\nIn the experiments, it is interesting to compare with GraphSage by sampling nodes' neighborhoods multiple times. Perhaps with a small number of sampling times, GraphSage's performance can be further improved. Especially, its performance in Table 2 is close to the proposed method.\n\nIn Fig. 3, the decrease of accuracy with increased K remains to be analyzed. Intuitively, the performance should be stable as K increase.\n\nFrom Fig. 4, the improvements brought by the proposed sampling strategy is small compared with the random sampling, which questions the importance of the proposed strategy. In addition, the results cannot show how does the proposed strategy maintain superior performance with a smaller K compared with the random sampling.\n\nIn Table 3, it is not clear on why do the three GNN methods in Table 2, GIN, GraphSage and DropEdge-GCN are excluded. It is better to make all comparison consistent.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "ZUXzuNxuC_i", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 3, "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": "**Review Summary**\n\nI have a question about the correctness of this paper because I do not think the statement and proof of the main theorem are mathematically rigorous nor correct. Regarding empirical evaluation, I think this paper correctly evaluates the proposed diverse sampling enhances the performance of base GNNs in the multi-class and multi-label node classification problems. However, I have several questions about the discussion about the ablation studies.\n\n**Summary**\n\nThis paper proposed DS-GNN, a GNN augmented with plug-in diverse sampling methods. It conducts node sampling to construct multiple subgraphs and apply base GNNs to them. Theoretically, they claimed to show that DS-GNN has high expressive power when the number of sampled subgraphs are sufficiently large. Empirically, they applied DS-GNN to multi-class and multi-label node classification problems and claimed to demonstrate that the proposed sampling method enhances the performance of base GNNs and that DS-GNN is comparable to the state-of-the-art GNN models. Finally, this paper constructs a new dataset, DBMovie, which can be used for multi-label node classification problems.\n\n**Claim**\n\nIf I understand correctly, this paper's claims are as follows:\n\n- [1-1] Claim 1: The proposed DS-GNN has theoretically powerful expressive power.\n- [1-2] Claim 2: The proposed DS-GNN empirically performs well.\n- [1-3] Claim 3: Practically, DS-GNN applies to any GNNs.\n\n**Soundness of the claims**\n\nCan theory support the claim?\n\n- [2-1] Claim 1: This paper justified this claim by proving that the proposed method is injective in the sense that \"any two nodes that have either different features or different neighborhood structures are mapped to different values\" (I call this property as Property A in this review). I agree with this paper in that it is one way to prove the expressive power of GNNs. However, I question the correctness of the main theorem for establishing this result (see Correctness section).\n- [2-2] Claim 2 is not a theoretical one.\n- [2-3] The model described in Section 3 supports Claim 3.\n\nCan empirical evaluation support the claim?\n\n- [3-1] Claim 1 is not an empirical one.\n- [3-2] Claim 2: Experiments in Tables 2 and 3 support this claim for node classification tasks. The ablation studies in Figures 3 and 4 are appropriate to confirm if the proposed sampling strategy works as expected. \n- [3-3] (This is not a requirement but a suggestion) I think it would be beneficial to claim the proposed method's strength if this paper compares it experimentally with CPNGNN and PNA, which the authors mentioned in the introduction. By doing so, I think this paper could claim that the tricky design (according to this paper) of CPNGNN and PNA is harmful to empirical performance.\n- [3-4] Claim 3: They applied the proposed diverse sampling to two types of GNNs: GCN and GCT, which empirically support Claim 3.\n\n**Significance and novelty**\n\nNovelty\n\n- [4-1] This paper has constructed a new dataset, DB-Movie, for multi-label node classification problems.\n\nRelation to previous work\n\n- [5-1] I think this paper discuss the relation with previous work well. \n  - [5-1-1] The idea of sampling the input graph itself has been employed in existing studies, such as DeepWalk, DeepEdge, and GraphSage. The proposed method differs from them because they are random-walk-based (DeepWalk) or edge-sampling-based (DeepEdge and GraphSage), while DS-GNN is node-sampling-based. I think it is better to mention FastGCN [Chen et al. 2018], another edge-sampling-based GNN.\n  - [5-1-2] Designing GNNs that have the maximal expressive power has been investigated by previous studies, such as CPNGNN and PNA. The proposed method took a strategy different from these methods.\n\n[Chen et al. 2018] Chen, J., Ma, T., & Xiao, C. FastGCN: Fast Learning with Graph Convolutional Networks via Importance Sampling. ICLR2018.\n\n**Correctness**\n\nIs the theorem correct?\n\n- [6-1] If I understand correctly, the statement nor proof of the main Theorem is not appropriate mathematically.\n\n  - [6-1-1] I am not confident I understand what \"can be close to 1\" correctly. Does it mean that the probability tends to 1 as some parameters (such as K) goes to infinity? I think \"can be close to 1\" in the statement is not a popular mathematical term, so I would recommend writing what it means mathematically. Also, the term \"with high probability\" in the proof has several meanings depending on the context. So, it is better to clarify what it means mathematically.\n  - [6-1-2] Assuming that my understanding of \"can be close to 1\" is correct (the limit is in terms of $K\\to \\infty$), I think the proof does not prove it. Specifically, the proof claims that from the assumption that \"$u$ and $v$ have different attributes or neighbors, each item in Eq. 16 can be smaller than 1.\", it is true that the injectivity holds with high probability. However, it is not true in general that $0\\leq a_i < 1$ for all $i$ implies $\\prod_{i=0}^\\infty a_i = 0$. ~~For example we have $(1-1/n)^n→e^{-1} > 0$ as $n\\to \\infty$.~~  [Nov. 11, 2020 edit]: Since I found this example is not appropriate, I gave another example. See the reply to this comment.\n  - [6-1-3] $p$ in (13) implicitly depends on the index $i$. Does (13) mean that the probability is the same for all $i$ ? Same is true of (14), in which $q$ implicitly depends on $i$ and $j$.\n  - [6-1-4] The proof says that \"it is reasonable to assume that [...], $q\\leq p$\". I recommend explictly writing the assumption not in the proof but in the statement.\n- [6-2] Even if the main Theorem is true, I think we cannot show that DS-GNNs has the Property A. If I understand correctly, the proof assumes that the probability that $h_u^{i, L} = h_v^{i, L}$ is not 1 for some $i$, where $h_\\ast^{i, L}$'s are the outputs of the base GNN. In order to prove that DS-GNN has Property A, this paper seems to assume implicitly the following assumption (Assumption B) and apply the main Theorem. However, I think Assumption B is almost equivalent to assuming that the base GNN is sufficiently strong, which is what we want the desired GNN to have.\n    - [6-2-1] Assumption B: The base GNN can output different representations with non-zero probability if $u$ and $v$ has either different features or different neighborhoods.\n\nIs the experimental evaluation correct?\n\n- [7-1] Multi-class node classification problems in Section 4.3\n  - [7-1-1] Table 2: Basically, OK. However, I wonder why only DS-GCN and DS-GAT have standard deviations (Table 4), while others not.\n  - [7-1-2] Figure 3: This paper discussed that accuracy is stabilized when the injectivity probability is close to 1. However, I have several questions about this statement. First, the accuracy in Figure 3 is not stabilized: the performance peaks at K=5 and drops at K=6. Second, since this experiment does not measure the injectivity probability, we cannot say the injectivity probability is truly close to 1. Finally, we do not know that the injectivity probability is truly correlated with performance accuracy. \n  - [7-1-3] Figure 4: This paper discussed that \"[Furthermore], under diverse sampling, we observe that the best $p_{init}$ are different among datasets.\" However, we cannot check whether it is correct because the concrete values of $p_{init}$ are not shown. I would recommend this paper to show the values of $p_{init}$ if this paper wants to claim this sentence.\n\n- [7-2] Multi-label node classification problem in Section 4.4\n\n  - [7-2-1] I did not find any critical problems. I think it was good that this paper compared the proposed method with not only GNNs but also MLP and DeepWalk to show that the task needs both node features and graph topologies.\n\nIs the experiment reproducible\n\n  - [8-1] Experiment code is not provided. However, hyperparameters and train/validation/test splits are written.\n  - [8-2] Since the DBMovie is not available, we cannot reproduce the results in Section 4.4.\n\n**Clarity**\n\nCan I understand the main point of the paper easily?\n- [9-1] Yes. However, the main theorem and its proof is not clear.\n\nIs the organization of paper well?\n- [10-1] Yes\n\nAre figures and tables appropriately made?\n  - [11-1] Yes\n\n**Additional feedback**\n\n- [12-1] It is better to discuss the computational complexity of the proposed methods. If I understand correctly, the time and space complexity is multiplied by K. Is my understand correct?\n- [12-2] The new dataset, DBMovie, is interesting. Do you have a plan to publish the dataset?\n\nMinor comments\n\n- [13-1] Page 1, Abstract: L.10: For a target node, diverse sampling offers it diverse neighborhoods, i.e., [...] → For a target node, diverse samling offers diverse neightborhoods to it., i.e., [...]\n- [13-2] Page 2, Paragraph 3: For convenience, we denote with DS-GNN ... → we denote by DS-GNN \n- [13-3] Page 3, L.3: Remove DS-GNN\n- [13-4] Page 4, paragraph after (4): I could not understand what this paper intended to mean by \"a generation of Dropout from dropping features to dropping edges\"\n- [13-5] Page 6, Section 4.1, Note that [...] 10 sampled garphs [...] → graph\n- [13-6] Page 6, Section 4.1, All GNN models [...] leverage Relu as [...] → ReLU\n- [13-7] Page 8 Section 4, Last Paragraph: [...] Deep Walk (only using only) [...]: → only using graph structures\n- [13-8] K is not writen in italic in some places (e.g., Page4 Sampling Strategy, last sentence)\n- [13-9] Appendix, after (14): $q <= p$→$q\\leq p$", "extra_scores": {}, "extra_text": {}}, {"review_id": "YJNi6_sPi2t", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper claims that existing GNNs often suffers from the limited capability of the aggregation function. This paper proposes a new framework of a diverse sampling of the graph to solve this problem. Specifically, this paper first samples several different graphs and use GNN on each graph to generate features, and finally use a type of injective multi-set aggregation function to obtain the final representation. The experimental results show that adding this module to GCN and GAT can further boost node-based multi-class classification performance. \n\nOverall, I think it is crucial to design how to choose neighbors and aggregate the neighbors' information. However, I did not find theoretical support or scenario support for the proposed diverse sampling method. \n\nConcerns: \n1. The problem that the authors focus on is interesting. Different graphs can result in different features of one node. However, I did not find theoretical support of the method design (like [1]) or scenarios to illustrate why we need to subsample the graphs. \n2. The sampling methods are also designed based on intuitions without further theoretical analysis of the sampling method's design. \n3. GAT can also learn different weights on different neighbors, which can be regarded as adaptively and softly select the neighbors. Could the author further illustrate why GAT cannot capture the features that the proposed method can? In other words, what is the fundamental difference?\n4. The Theorem in this paper show that the probability that the multi-sets for two nodes with different attributes or different neighbors are different can be close to 1. As I understand it, [2] can also achieve this goal. Can the authors provide theoretical and experimental comparison?  \n5. Diversity may also lead to the weakening of generalization, could the author further claim on that point? \n6. Important baselines are missing. How to sample informative neighbors to improve GNN has been widely studied. For example, Chen et al. proposed a node importance sampling algorithm [3], which has been proven effective in accelerating model convergence. These closed related baselines should be carefully discussed and evaluated in experiments.  Besides, the performance gain over vanilla GNN is tiny in many cases. More importantly, Figure 4 shows that diverse sampling does not outperform random sampling when the initial sampling probability is reasonably large.\n\n[1] Xu, Keyulu, et al. \"How powerful are graph neural networks?.\" arXiv preprint arXiv:1810.00826 (2018).\n\n[2] You, Jiaxuan, Rex Ying, and Jure Leskovec. \"Position-aware graph neural networks.\" arXiv preprint arXiv:1906.04817 (2019).\n\n[3]. Chen J, Ma T, Xiao C. Fastgcn: fast learning with graph convolutional networks via importance sampling[J]. arXiv preprint arXiv:1801.10247, 2018.", "extra_scores": {}, "extra_text": {}}, {"review_id": "RH2YuZE6e5-", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents a method that should increase the expressive power of GNN. This method includes sampling subgraphs out of the input graph using a novel diverse sampling method and calculating the output of each node by using a shared GNN on each sampled graph and summing over the outputs. The empirical evidence presented shows that this method outperforms other GNN architectures such as GCN and GAT on several node classification tasks.\n\nI think the diverse sampling (DS) method is interesting and well-motivated so that the sampled subgraphs are diverse, each node appears at least once and high degree nodes have a higher probability to appear in each sample.  The DS method is also applicable to any GNN architecture which is an advantage. The experiments show that a 2-layer DS combined with GCN or GAT improves on the base models with the DS. Another contribution of this paper is presenting a new dataset, namely DBMovie, and showing that DS slightly improves performance on this dataset compared to the base models.\n\nI have a couple of concerns regarding this paper, especially the theoretical grounding, whether the model is invariant, and the experimental setup. In more details:\n1)\t The theorem (page 6) is written in a very informal manner, and I am concerned it doesn’t show that using DS actually increase the expressive power of GNN: stating that a probability “can be close to 1” is very unclear, it can also be *not* close to 1, so in this sense, the theorem doesn’t state anything. \n2)\tI have some concerns about the correctness of the proof of this theorem, as there are a couple of handwaving arguments there (appendix C). Some examples: “It’s reasonable to assume that such a probability based on different sampled graphs is smaller than the base on the same sampled graph, i.e., q <= p.”, this statement is unclear. In order to claim this, p and q should be exactly calculated, they might depend on the structure of the graph, on the nodes that are chosen, etc. In equation (16), it is not clear why each item is smaller than 1, and even if each item is smaller than 1, still each item can be arbitrarily close to 1 so that this probability might be very large. \n3)\tThe authors claim that the DS method improves the expressive power of GNNs, while the theorem only states (informally) that w.h.p two nodes with different attributes can be distinguished. On the other hand, it is not clear why two nodes with the exact same neighborhood will have the same output. I am concerned that using this sampling method might make GNNs not invariant – so that two nodes with the exact local structure will have different outputs. This might be OK in general if the probability for this to happen is small (which is believe is the case here) but should be shown formally, or at least discussed.\n4)\tMy main concern about the experiment is that they were done with a very shallow GNN (2-layer), which represents a very small neighborhood of each node. I think it is important to test deeper GNN in order to show the robustness of the DS method.\n5)\tThe paper is missing a related work section, so it is hard to situate the novelty of the sampling method compared to other graph sampling methods that are also used in modern GNNs. Some examples:\nhttps://arxiv.org/abs/1907.04931\nhttps://arxiv.org/abs/1806.01973\nhttps://arxiv.org/abs/1801.10247\nhttps://arxiv.org/abs/1905.07953\nAlso, since it is claimed that DS-GNN increases expressive power, there should be a clearer discussion about works related to the expressive power of GNN (there are many such recent works), the only relevant paper mentioned is Xu et al 2018.\n6)\tThe new DBMovie dataset that is presented is not clear enough. What are the features of each node? According to Figure 5, this is a sentence representing each movie, so how each sentence is represented as a node feature? It would also be beneficial to state how many movies (nodes) are there of each genre (label). Lastly, I highly advise the authors to upload this dataset as supplementary material for the paper, so it would be possible to verify the results.\n\nSome minor typos:\n-\tPage 4, second paragraph, 5th sentence from the end “when its degree”\n-\tSection 4.4 “an multi-label” -> “a multi-label”\n-\tSection 4.2 second sentence “we choose the the”\n-\tSection 4.4 “DeepWalk (only using only)”\n\nTo conclude, although the DS method seems interesting, the theoretical aspect of the paper is not clear enough, more experiments should be done with deeper networks (more than 2 layers), and a clear related work should be added in order to situate more clearly this method with respect to other known methods.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Ef0H5XSp-re", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents diverse sampling to improve the expressive power of GNNs.The key idea is to construct diverse rooted sub-graphs for each node and obtain the target node representation by aggregating the representation of diverse neighborhoods. The experiment results on 4 different datasets justified the effectiveness of the proposed method.\n\nStrengths:\n+ This paper is well written and organized.\n+ Enhancing the diversity of neighborhood sampling is an interesting idea to investigate in GNNs\n\nWeaknesses:\n- It is not clear whether this idea can generalize to other GNNs, e.g., ResGCN, IncepGCN, etc. \n- No theoretical justification is provided for the proposed diverse sampling.\n- Some details of the proposed technique are missing.\n\nQuestions:\n\n1. What’s the relationship between the proposed technique and graph sparsification or DropNode?\n\n2. Why are GraphSAGE and DropEdge GCN not compared for multi-label classification?\n\n3. In Table 2, the performance improvement over baseline is limited. It is difficult to determine whether the performance \nimprovement really comes from the diverse sampling strategy.\n\n4. What’s the computational complexity of GCN based on a diverse sampling strategy?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers, including me, agreed that considering sampling diversity is interesting and reasonable when designing GNNs. However, the proposed method is too heuristic and empirical. Without the authors' feedback, I tend to reject this work.
Decision: Reject