Robust Graph Representation Learning via Neural Sparsification
Authors: Cheng Zheng
Bo Zong
Wei Cheng
Dongjin Song
Jingchao Ni
Wenchao Yu
Haifeng Chen
Wei Wang
Venue:  (2020)

Abstract: Graph representation learning serves as the core of many important prediction tasks, ranging from product recommendation in online marketing to fraud detection in financial domain. Real-life graphs are usually large with complex local neighborhood, where each node is described by a rich set of features and easily connects to dozens or even hundreds of neighbors. Most existing graph learning techniques rely on neighborhood aggregation, however, the complexity on real-life graphs is usually high, posing non-trivial overfitting risk during model training. In this paper, we present Neural Sparsification (NeuralSparse), a supervised graph sparsification technique that mitigates the overfitting risk by reducing the complexity of input graphs. Our method takes both structural and non-structural information as input, utilizes deep neural networks to parameterize the sparsification process, and optimizes the parameters by feedback signals from downstream tasks. Under the NeuralSparse framework, supervised graph sparsification could seamlessly connect with existing graph neural networks for more robust performance on testing data. Experimental results on both benchmark and private datasets show that NeuralSparse can effectively improve testing accuracy and bring up to 7.4% improvement when working with existing graph neural networks on node classification tasks.

Under review as a conference paper at ICLR 2020
ROBUST GRAPH REPRESENTATION LEARNING VIA NEURAL SPARSIFICATION
Anonymous authors Paper under double-blind review
ABSTRACT
Graph representation learning serves as the core of many important prediction tasks, ranging from product recommendation in online marketing to fraud detec- tion in financial domain. Real-life graphs are usually large with complex local neighhorhood, where each node is described by rich set of features and easily connects dozens or even hundreds of neighbors. Most existing graph learning techniques rely on neighborhood aggregation, however, the complexity on real- life graphs is usually high, posing non-trivial overfitting risk during model train- ing. In this paper, we present Neural Sparsification (NeuralSparse), a supervised graph sparsification technique that mitigates the overfitting risk by reducing the complexity of input graphs. Our method takes both structural and non-structural information input, utilizes deep neural networks parameterize the sparsi- fication process, and optimizes the parameters by feedback signals from down- stream tasks. Under the NeuralSparse framework, supervised graph sparsification could seamlessly connect with existing graph neural networks for more robust performance on testing data. Experimental results on both benchmark and private datasets show that, NeuralSparse can effectively improve testing accuracy and bring up to 7.4% improvement when working with existing graph neural networks node classification tasks.
INTRODUCTION
Representation learning has been in the center of many machine learning tasks on graphs, such as name disambiguation citation networks (Zhang et al., 2018c), spam detection social net- works (Akoglu et al., 2015), recommendations in online marketing (Ying et al., 201 8a), and many others (Hamilton et al., 2017; Li et al., 2018). As a class of models that can simultancously uti- lize non-structural (e.g., node and edge features) and structural information in graphs, Graph Neural Networks (GNNs) (Kipf& & Welling, 2017; Hamilton et al., 2017; Li et al., 2016) construct effective representations for downstream tasks by iteratively aggregating neighborhood information (Kipf & Welling, 2017: Hamilton et al., 2017). Such methods have demonstrated state-of-the-ard perfor- mance in classification and prediction tasks on graph data (Veličković al., 2018; Chen al., 2018; Xu et al., 2019; Veličković et al., 2019).
Meanwhile, graphs from real-life applications are usually large with complex local neighborhood, where each node has rich features and dozens or even hundreds of neighbors. As shown in Figure ((a), this subgraph from Transaction dataset (detailed in Section 5.1) consists of 38 nodes (i.e., promising organizations and other organizations) with average node degree 15 and node feature dimension 120. The GNNs are expected grasp useful patterns from neighboring nodes; however, as representative patterns are diluted by overwhelming information in local neighborhood, graph learning algorithms could be misled by neighborhood aggregation. Such complexity input graphs poses non-trivial overfitting risk to existing GNN based learning techniques.
While it is straightforward yet expensive (sometimes even impractical) to address this overfitting problem by increasing the number of labeled samples, we investigate cheaper alternative of re- ducing input graph complexity by graph sparsification in this work. Graph sparsification (Liu et al., 2018; Zhang& & Patone, 2017) aims to find smaller subgraphs from input large graphs that best pre- serve desired properties. Existing sparsification methods could lead to suboptimal performance for downstream prediction tasks: (1) these methods unsupervised such that the resulting sparsified

---

Under review as a conference paper at ICLR 2020
hroeaing Dig pastoders Orgamalleeo
0.5
Preninng Diga Viatees Otter Organ aalion
Originsl Geaph
Spanilled Grach NeuniSSpane
Spart And Graph
(a) Original Subgraph
(b) Sparsified Subgraph
(c) Testing AUC
Figure I: subgraph of 38 organizations from Transaction dataset: (a) The original subgraph sam- pled from the Transaction dataset, where nodes and edges represent organizations and their trans- actions, respectively; (b) The sparsified subgraph by NeuralSparse: (c) Testing AUC on identifying promising organizations.
graphs may not favor downstream tasks; and (2) they only consider structural information for sparsi- fication decision, while struucuull information in graphs, such node/edge features, could have non-trivial impact to the quality of sparsification. Recently, there have been GNN models attempt- ing sample subgraphs from predefined distributions (Leskovec & Faloutsos, 2006; Adhikari al., 2018; Hamilton et al., 2017; Chen et al., 2018). As the predefined distributions could be irrelevant subsequent tasks, the sparsified graphs may miss important information for downstream tasks, leading to suboptimal prediction performance.
Present work. We propose Neural Sparsification (NeuralSparse), a general framework that simulta- neously learns graph sparsification and graph representation by feedback signals from downstream tasks. The NeuralSparse consists of two major components: sparsification network and GNN. For the sparsification network, we utilize a deep neural network to parameterize the sparsification pro- cess: how to select edges from one-hop neighborhood given a fixed budget. In the training phase, the network learns to optimize sparsification strategy that favors downstream tasks. In the testing phase, the network sparsifies input graphs following the learned strategy, instead of sampling sub- graphs from predefined distribution. Unlike conventional sparsification techniques, our technique takes both structural and non-structural information as input and optimizes the sparsification strategy by feedback from downstream tasks, instead of using (possibly irrelevant) heuristics. For the GNN component, the NeuralSparse feeds the sparsified graphs to a GNN and learns a graph representation for subsequent prediction tasks.
Under the framework of NeuralSparse, we are able to leverage the standard stochastic gradient descent and backpropagation techniques simultaneously optimize graph sparsification and repre- sentation. As shown in Figure 1(b), the graph sparsified by the NeuralSparse has lower complexity with average node degree around 5. As result (illustrated in Figure I(c)), the testing classification accuracy on the sparsified graph is improved by 15%, compared with its counterpart in the orig- inal input graph, while conventional techniques could not offer competitive sparsification for the classification task.
Experimental results both public and private datasets show that the NeuralSparse is able con- sistently provide improved performance for existing GNNs node classification tasks, bringing up to 7% improvement.
RELATED WORK
Our work is related to two lines of research: graph sparsification and graph representation learning.
Graph sparsification. The goal of graph sparsification is find small subgraphs from input large graphs that best preserve desired properties. Existing techniques are mainly unsupervised and deal with simple graphs without node/edge features for preserving predefined graph metrics (Hübler et al.. 2008), information propagation traces (Mathioudakis et al., 2011), graph spectrum (Calan- driello et al., 2018; Chakeri al., 2016; Adhikari al., 2018), node degree distribution (Eden al.,
2

---

Under review as a conference paper at ICLR 2020
01
00
GNN
ML
Graph G
Spansifccation Network Qg (glG)
Sparsified Graph 8
Graph Neural Networks (g0rl))
Classification Results P
Figure 2: The overview of NeuralSparse
2018; Voudigari et al., 2016), node distance distribution (Leskovec & Faloutsos, 2006), clustering coefficient (Maiya & Berger- Wolf, 2010). Importance based edge sampling has also been studied in scenario where we could predefine edge importance (Zhao, 2015; Chen al., 2018).
Unlike existing methods that mainly work with simple graphs without node/edge features in an unsupervised manner, our method takes node/edge features parts of input and optimizes graph sparsification by supervision signals from errors made in downstream tasks.
Graph representation learning. Graph neural networks (GNNs) are the most popular techniques that enable vector representation learning for large graphs with complex node/edge features. All existing GNNs share a common spirit: extracting local structural features by neighborhood aggre- gation. Scarselli et al. (2009) explore how to extract multi-hop features by iterative neighborhood aggregation. Inspired by the success convolutional neural networks, multiple studies (Defferrard et al., 2016; Bruna et al., 2014) investigate how to learn convolutional filters in the graph spectral domain under transductive settings (Zhang et al., 2018b; Zhuang & Ma. 2018). To enable inductive learning, convolutional filters in the graph domain are proposed (Simonovsky & Komodakis, 2017; Niepert et al., 2016; Kipf& & Welling, 2017; Veličković et al., 2018; Xu et al., 2018) and a few stud- ies (Hamilton al., 2017: Lee al., 2018) explore how differentiate neighborhood filtering by sequential models. In addition, multiple recent works (Ying et al.. 2018b; Xu et al., 2019; Abu-El- Haíja al., 2019) investigate the expressive power of GNNs. Recently, (Franceschi al., 2019) study how to sample high-quality subgraphs from space of all possible graphs of a complete graph so that the sampled graphs enhance the prediction power in downstream learning tasks. In particular, the proposed method only focus on transductive tasks.
Our work contributes from a unique angle: by reducing the noise from input graphs, our technique can further boost testing performance of existing GNNs.
3 PROPOSED METHOD: NEURALSPARSE
In this section, we introduce the core idea of our method. We start with the notations that are frequently used in this paper. We then describe the theoretical justification behind NeuralSparse and our architecture to tackle the supervised node classification problem.
Notations. In this paper, we represent input graph of nodes as G -V (1) E R includes node features with dimensionality d,, (2) E E R"x" is a binary matrix where E(u, v) if there is edge between node u and node 2; (3) A Raxuxd, encodes input edge features of dimensionality d.. In addition, we use Y to denote the prediction target in downstream tasks (e.g., Y E Rax if we dealing with node classification problem with d, classes).
Theoretical justification. From the perspective statistical learning, the key of a defined prediction task is learn P(Y G.. where Y is the prediction target and G an input graph. Instead of directly working with original graphs, we would like to leverage sparsified subgraphs to mitigate overfitting risks. other words, we are interested the following variant,
P(Y G) RJ
P(Y
G),
(1)
BE30
where g is sparsified subgraph, and SG class of sparsified subgraphs of G.
3

---

Under review as a conference paper at ICLR 2020
In general, because of the combinatorial complexity in graphs. it is intractable to enumerate all possible as well as estimate the exact values of P(Y g) and P(g G). Therefore, we approximate the distributions by tractable functions,
Σ P(Y 99)((9 | g
G)
Qo 1 [9)
gEso
where Qo and Qo are approximation functions for P(Y 9) and P(g G) parameterized by 0 and 6, respectively.
Moreover, to make the above graph sparsification process differentiable, we employ reparameteri- zation tricks (Jang et al., 2017) make Qola G)) directly generate differentiable samples, such that
Σ
Qo 9)Q(( G) x
Σ
Qo
(3)
gESg
where o' ~ Qo(g G) means g' is random sample drawn from Qo(g | G).
To this end, the key is how to find appropriate approximation functions Qalg G) and Qx g))
Architecture. In this paper, we propose Neural Sparsification (NeuralSparse) to implement the theoretical framework discussed in Equation 3. As shown in Figure 2, NeuralSparse consists of two major components: sparsification network and GNNs.
The sparsification network is a multi-layer neural network that implements Q | G): Taking G as input, it generates random sparsified subgraph of G drawn from a learned distribution.
GNNs implement (Y g) that takes a sparsified subgraph as input, extracts node representa- tions, and makes predictions for downstream tasks.
Algorithm Training algorithm for NeuralSparse
Input: graph G (V, E, A), integer I, and training labels Y.
1: while stop criterion is not met do
2: Generate sparsified subgraphs (91, -2. : gi by sparsification network (Section 4);
3: Produce prediction (V1, Yg...., Vi) by feeding "" ,9t) into GNNs;
4: Calculate loss function J/
5: Update & and by descending J
6: end while
As the sparsified subgraph samples are differentiable, the two components can be jointly trained us- ing gradient descent based backpropagation techniques from supervised loss function, illustrated in Algorithm 1. While the GNNs have been widely investigated in recent works (Kipf & Welling, 2017: Hamilton et al., 2017; Veličković et al., 2018), we focus on the practical implementation for sparsification network in the remaining of this paper.
SPARSIFICATION NETWORK
Following the theory discussed above, the goal of sparsification network is to generate sparsified subgraphs for input graphs, serving as the approximation function Qo G). Therefore, we need to answer the following three questions in sparsification network. i). What is SG in Equation 1, the class of subgraphs we focus on? ii). How to sample sparsified subgraphs? iii). How to make sparsified subgraph sampling process differentiable for the end-to-end training? In the following, we address the questions one by one.
k-neighbor subgraphs. We focus on k-neighbor subgraphs for Sg (Sadhanala al., 2016): Given an input graph, a k-neighbor subgraph shares the same set of nodes with the input graph, and each select more than edges from its one-hop neighborhood. Although
node in the subgraph the concept of sparsification network is not limited to a specific class of subgraphs, we choose k- neighbor subgraphs for the following reasons.
4

---

Under review as a conference paper at ICLR 2020
We are able to adjust the estimation the amount of task-relevant graph data by tuning the hyper-parameter k. Intuitively, when an under-estimate, the amount of task-relevant graph data accessed by GNNs could be inadequate, leading to inferior performance. When & is over- estimate, the downstream GNNs may overfit the introduced noise or irrelevant graph data, resulting in sub-optimal performance. It could be difficult to golden hyper-parameter that works all time, but one has the freedom to choose the A that is the best fit for a specific task.
k-neighbor subgraphs are friendly to parallel computation. As each node selects its edges in- dependently from its neighborhood, can utilize tensor operations in existing deep learning frameworks, such as tensorflow (Abadi et al., 2016), to speed up the sparsification process.
Sampling k-neighbor subgraphs. Given & and an input graph G (V, E, A), we obtain k- neighbor subgraph by repeatedly sampling edges for each node in the original graph. Without loss of generality, we sketch this sampling process by focusing on specific node graph G. Let N. be the set of one-hop neighbors of node u.
e a~ (V V(N.), A(u)), where f.(-) is a function that generates a one-hop neighbor v from the learned distribution based on node u's attributes, node attributes of u's neighbors V V(N.), and their edge attributes A(u). In particular, the learned distribution is encoded by parameters ø.
2. Edge Eu, v) is selected for node
3. The above two steps repeated times.
Note that the above process performs sampling without replacement. Given a node u, each of its adjacent edges is selected most once. Moreover, the sampling function fa(+) is shared among nodes; therefore, the number of parameters ø is independent of the input graph size.
Making samples differentiable. While conventional methods are able generate discrete sam- ples (Sadhanala et al., 2016), these samples are not differentiable such that it is difficult to utilize them to optimize sample generation. To make samples differentiable, we propose Gumbel-Softmax based multi-layer neural network to implement the sampling function f-(-) discussed in above.
To make the discussion self-contained. we briefly discuss the idea of Gumbel-Softmax, Gumbel- Softmax is reparameterization trick used to generate differentiable discrete samples (Jang et al., 2017; Maddison al., 2017). Under appropriate hyper-paramete settings, Gumbel-Softmax is able to generate continuous vectors that are as "sharp" as one-hot vectors widely used to encode discrete data.
Without loss of generality, focus specific node in graph G = (V, Let N., be the set of one-hop neighbors node u. We implement fo(-) as follows.
1. Ve N..
E MLP (V (v)), A(u,u),
(4)
where MLP is multi-layer neural network with parameters d.
2. Ve N,, we employ softmax function compute the probability sample the edge,
exp(Zu..))
Tu,
(5)
SWNN exp (Zu,w)
3. Using Gumbel-SSfttaxx generate differentiable samples
exp((log(Tw.o)) + Ew)/T)
Fn,0 SWEN, exp (log(( ew)/T)
(6)
where Ta,e is scalar, log( log(s)) with randomly drawn from Uniform(O, 1), and T is a hyper-parameter called temperature which controls the interpolation between discrete distribution and continuous categorical densities.
Note that when we sample k edges, the computation for 2,,v and nu only needs to be performed discuss how to tune it as follows.
once. For the hyper- paper--arrmeter
Discussion on temperature tuning. The behavior of Gumbel-Softmax is governed by a hyper- parameter called temperature. In general, when is small, the Suntee-Softmax distribution
5

---

Under review as a conference paper at ICLR 2020
resembles the discrete distribution, which induces strong sparsity; however, small also introduces high variance gradient that blocks effective backpropagation. A high value of т cannot produce expected sparsification effect. Following the practice in (Jang al., 2017). we adopt the strategy by starting the training with a high temperature and anneal to small value with a guided schedule.
Sparsification algorithm and its complexity. As shown in Algorithm 2, given hyper- parameter k, the sparsification network visits each node's one-hop neighbors k times. Let m be the total number of edges in the graph. The complexity sampling subgraphs by the sparsification network is OKkm). When k is small in practice, the overall complexity is ((m).
Algorithm 2 Sampling subgraphs by sparsification network
Input: graph G (V, F,, A) and integer k.
1: Edge set HI = /
2: for
do
3: for E Na do
4: Zn. + MLP (V (u), V()), A(u,
5: end for
6: for E No do
7:
Tu.e exp(zu,r) EwEN, exp(zu,w)
8:
end for
9:
for j L,... do
10:
for u E N. do
Fa.v exp((log(Ta.o) Eo)/T)/E exp((lg(TTnw) + ew)/T)
12: end for
Add the edge represented by vector [zu,e] into H 14: end for
end for
Comparison with multiple related methods. Unlike GraphSAGE (Hamilton et al.. 2017), Fast- GCN (Chen et al., 2018), and AS-GCN (Huang et al., 2018) that incorporate layer-wise node sam- plers to reduce the complexity of GNNs, NeuralSparse samples subgraphs before applying GNNs. As for the computation complexity, the sparsification in NeuralSparse is more friendly to paral- lel computation than the layer-conditioned approach in AS-GCN. Compared with GAT (Veličković al., 2018; Zhang al., 2018a), the NeuralSparse can produce sparser neighborhood, which ef- fectively mitigates overfitting risks. Unlike LDS (Franceschi et al., 2019), NeuralSparse leams inductive graph sparsification, and its graph sampling is constrained by input graph topology.
5 EXPERIMENTAL STUDY
In this section, we evaluate our proposed NeuralSparse node classification task, including induc- tive and transductive settings. We demonstrate that NeuralSparse achieves superior classification performance otate-of-the-art GNN models. Moreover, provide case study demonstrate how sparsified subgraphs generated by NeuralSparse could improve classification. The supplemen- tary material contains more detailed experimental information.
5.1 DATASETS
We employ five datasets from various domains and conduct node classification task following the settings as described in Hamilton et al. (2017); Kipf & Welling (2017). The dataset statistics are summarized in Table
Inductive datasets. We utilize the Reddit and PPI datasets and follow the same setting in Hamilton et al. (2017). The Reddit dataset contains post-to-post graph with word vectors as node features. The node labels represent which community Reddit posts belong to. The protein-protehi protein interaction (PPI) dataset contains graphs corresponding to different human tissues. The node features are positional gene sets, motif gene sets and immunological signatures. The nodes multi-labeled by gene ontology. The graph in the Transaction dataset contains real transactions between organizations in two years, with the first year for training and the second year for validation/testing. Each node

---

Under review as a conference paper at ICLR 2020
Table 1: Dataset statistics
Reddit
PPI
Transaction
Cora
Citeseer
Task
Inductive
Inductive
Inductive
Transductive
Transductive
Nodes
232,965
56,944
95,544
2.708
3,327
Edges
11,606,919
818,716
963,468
5,429
4,732
Features
602
50
120
1,433
3,703
Classes
41
121
2
7
6
Training Nodes
152,410
44,906
47,772
140
120
Validation Nodes
23,699
6,514
9,554
500
500
Testing Nodes
55,334
5,524
38,218
1,000
1,000
represents an organization and each edge indicates a transaction between two organizations. Node attributes are side information about the organizations such as account balance, cash reserve, etc. On this dataset, we aim classify organizations into two categories: promising others for investment in near future. The class distribution in the Transaction dataset highly imbalanced. During the training under inductive setting, algorithms have only access to training nodes' attributes and edges. In the PPI and Transaction datasets, the models have to generalize to completely unseen graphs.
Transductive datasets. We use citation benchmark datasets with transductive experimental set- ting Yang et al. (2016); Kipf& & Welling (2017). The citation graphs contain nodes corresponding documents and edges as citations. Node features are the sparse bag-of-words representations of documents and node labels indicate the topic class of the documents. In transductive learning, the training methods have access to all node features and edges, with a limited subset of node labels.
5.2 EXPERIMENTAL SETUP
Baseline models. We incorporate four state-of-the-ard methods the base GNN components, in- cluding GCN (Kipf & Welling, 2017), GraphSAGE (Hamilton et al., 2017), GAT (Veličković et al., 2018), and GIN (Xu et al., 2019). We evaluate proposed NeuralSparse with sparsification net- work and each of the four GNNs. Besides, we also implement variants of NeuralSparse by replacing the sparsification network with either the spectral sparsifier (SS, Sadhanala al., 2016) the Rank Degree (RD, Voudigari et al., 2016) method.
Temperature tuning. We anneal the temperature with the schedule max (0.05, exp(-rp)), where is the training epoch and r 10f-5,-4, 4,-,,,2,,11,, is updated every N steps and N E (50, 100,.., 500). Compared with MNIST VAE model in Jang et al. (2017), smaller hyper- parameter T fits NeuralSparse better in practice.
Metrics. We evaluate the performance on the transductive datasets with accuracy (Kipf & Welling, 2017). For inductive tasks on the Reddit and PPI datasets, we report micro-averaged Fl scores (Hamilton et al., 2017). Due to the highly imbalanced classes in the Transaction dataset, models are evaluated with AUC value (Huang & Ling, 2005). The results show the average of 10 runs.
5.3 CLASSIFICATION PERFORMANCE
Table summarizes classification performance of NeuralSparse and the baseline methods on all datasets. For Reddit, PPI, Transaction, Cora and Citeseer, the hyper- parameter k is set as 30, 15, 10, 5, and 3 respectively. The hyper-parameter GAT on Reddit is missing due to the out-of-memory error.
set as 1 in this experiment. Note that the result of
Overall, NeuralSparse able to help GNN techniques achieve competitive generalization perfor- mance with sparsified graph data. We make the following observations. (1) Compared with basic GNN models, NeuralSparse can enhance the generalization performance on node classification tasks by utilizing the sparsified subgraphs from sparsification network, especially in the inductive setting. Indeed, large neighborhood size in the original graphs could bring increased chance of introduc- ing noise into the convolutional operations, leading to sub-optimal performance. (2) With differ- ent GNN models, the NeuralSparse can consistently achieve comparable or superior performance, which demonstrates NeuralSparse is general and can be applied multiple classification models.

---

Under review as a conference paper at ICLR 2020
Table 2: Node classification performance
Reddit
PPI
Transaction
Cora
Citeseer
Sparsifier
Method
Micro-F1
Micro-F1
AUC
Accuracy
Accuracy
GCN
0.922 0.041
0.532 0.024
0.564 +: 0.018
0.810 0.027
0.694 0.020
GraphSAGE
0.938 + 0.029
0.600 + 0.027
0.574 + 0.029
0.825 + 0.033
0.710 + 0.020
N/A
GAT
0,917 = 0.030
0.616 + 0,022
0.821 0.043
0.721 + 0.037
GIN
0.928 + 0.022
0.703 = 0.028
0.607 = 0.031
0.816
0.709 0.037
GCN
0.912 + 0.022
0,521 + 0.024
0.562 + 0.035
0.780 1 0.045
0.684 = 0.033
SS/
GraphSAGE
0.907 + 0.018
0.576 = 0.022
0.565 + 0.042
0.806 + 0.032
0.701 + 0.027
RD
GAT
0.889 = 0.034
0.614 + 0.044
0.807 0.047
0.686 + 0.034
GIN
0.901 0.021
0.693
0.593 + 0.038
0.785 0.041
0.706 0.043
GCN
0.946 1 0.020
0,600 0.014
0.610 1 0.022
0.821 + 0.014
0.715 1 0.014
Neural Sparse
GraphSAGE
0.951
0.015
0.626 1 0.023
0.649 1 0.018
0.832 0.024
0.720
0.013 0.013
GAT
0.921 0.015
0.671 + 0.018
0.834 0.015
0.724 + 0.026
GIN
0.937 + 0.027
0,744 = 0.015
0.634 + 0.023
0.824 + 0.027
0.719 = 0.015
( Report the better performance with SS or RD)
0.055
0.655
Neara DAT
0.632
Neara Swc-Saarrrrrreee GrattS
3.12
15
City Hiatir
Hyper Seramearr
tope--ceareee sper-seramtter
(a) Spectral Sparsifier
(b) RD Sparsifier
(c) Hyperparameter
(d) Hyperparameter
Figure 3: Sparsified subgraphs and performance vs hyper-parametters
(3) In comparison with the two NeuralSparse variants SS Br-GaaahSAGEE and RD- AD-GrahSSAEE, Neu- ralSparse outperforms because of the automatically learned graph sparsification with both structural and non-structural information as input.
5.4 SENSITIVITY TO PYPER-PARAMETERS AND SPARSIFIED SUBGRAPHS
Figure 3(c) demonstrates how classification performance responds when increases on the Trans- action dataset. There exists an optimal & that delivers the best classification AUC score. When k is small, NeuralSparse can only make use of little relevant structural information in feature aggrega- tion, which leads to inferior performance. When & increases, the aggregation convolution involves more complex neighborhood aggregation with higher chance overfitting noise data, which nega- tively impacts the classification performance for unseen testing data. Figure 3(d) shows how hyper- parameter impacts classification performance on the Transaction dataset. When / increases from 5, we observe relatively small improvement in classification AUC score. As the parameters in the sparsification network are shared by all edges in the graph, the estimation variance from random sampling could already be mitigated to some extent by a number of sampled edges in sparsified subgraph. Thus, when we increase the number of sparsified subgraphs, the incremental gain could be small.
In Figure 3(a, b), we present the sparsified graphs output by two baseline methods, SS and RD. By comparing the two plots with Figure 1(b), we make the following observations. First, the Neu- ralSparse sparsified graph tends to select edges that connect nodes of identical labels, which favors the downstream classification task. The observed clustering effect could further boost the confidence of decision making. Second, instead of exploring all the neighbors. nections/edges in sparsified graphs, which could make it casier for human experts to perform model interpretation and result visualization.
focus selected
8

---

Under review as a conference paper at ICLR 2020
CONCLUSION
In this paper, we propose Neural Sparsification (NeuralSparse) to address the overfitting issues brought by the complexity in real-life large graphs. NeuralSparse consists of two major compo- nents: (1) The sparsification network sparsifies input graphs by sampling edges following a learned distribution; (2) GNNS take sparsified subgraphs as imput and extracts node representations for down- stream tasks. The two components in NeuralSparse can be jointly trained with supervised loss, gra- dient descent, and backpropagation techniques. The experimental study on real-life datasets show that the NeuralSparse consistently renders more robust graph representations, and brings up to 7% improvement accuracy over the state-of-the-ar GNN models.

---

Under review as a conference paper at ICLR 2020
REFERENCES
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. Tensorflow: system for large- scale machine learning. In OSDI, 2016.
Sami Abu-al-Haija, Bryan Perozzi, Amol Kapoor, Hrayr Harutyunyan, Nazanin Alipourfard, Kristina Lerman, Greg Ver Steeg, and Aram Galstyan. Mixhop: Higher-order graph convolu- tion architectures via sparsified neighborhood mixing. In ICML, 2019.
Bijaya Adhikari, Yao Zhang, Sorour E Amiri, Aditya Bharadwaj, and B Aditya Prakash. Propagation-based temporal network summarization. TKDE, 2018.
Leman Akoglu, Hanghang Tong, and Danai Koutra. Graph based anomaly detection and description: survey, Data mining and knowledge discovery, 2015.
Joan Bruna, Wojciech Zaremba, Arthur Szlam, and Yann LeCun. Spectral networks and locally connected networks graphs. In ICLR, 2014.
Daniele Calandriello, Ioannis Koutis, Alessandro Lazaric, and Michal Valko. Improved large-scale graph learning through ridge spectral sparsification. In JCML, 2018.
Alireza Chakeri, Hamidreza Farhidzadeh, and Lawrence O Hall. Spectral sparsification in spectral clustering. ICPR, 2016.
Jie Chen, Tengfei Ma, and Cao Xiao. Fastgen: fast learning with graph convolutional networks via importance sampling. In ICLR, 2018.
Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst. Convolutional neural networks on graphs with fast localized spectral filtering. In NIPS, 2016.
Talya Eden, Shweta Jain, Ali Pinar, Dana Ron, and C. Seshadhri. Provable and practical approxi- mations for the degree distribution using sublinear graph samples. In WWW, 2018.
Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. Learning discrete structures for graph neural networks. In ICML, 2019.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning large graphs. In NIPS, 2017.
Jin Huang and Charles X Ling, Using auc and accuracy in evaluating learning algorithms. TKDE, 2005.
Wenbing Huang, Tong Zhang, Yu Rong, and Junzhou Huang. Adaptive sampling towards fast graph representation learning. In NewrIPS, 2018.
Christian Hübler, Hans-Peter Kriegel, Karsten Borgwardt, and Zoubin Ghahramani. Metropolis algorithms for representative subgraph sampling. In ICDM, 2008.
Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. In ICLR, 2017.
Thomas Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. In ICLR, 2017.
John Boaz Lee, Ryan Rossi, and Xiangnan Kong. Graph classification using structural attention. In KDD, 2018
Jure Leskovec and Christos Faloutsos. Sampling from large graphs. In KDD, 2006.
Yaguang Li, Rose Yu, Cyrus Shahabi, and Yan Liu. Diffusion convolutional recurrent neural net- work: Data-driven traffic forecasting. In ICLR, 2018.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. In ICI.R 2016.
10

---

Under review as a conference paper at ICLR 2020
Yike Liu, Tara Safavi, Abhilash Dighe, and Danai Koutra. Graph summarization methods and applications: A survey, ACM Computing Surveys, 2018.
Chris J Maddison, Andriy Mnih, and Yee Whye Teh. The concrete distribution: A continuous
relaxation of discrete random variables. In ICLR, 2017.
Arun S Maiya and Tanya Y Berger- Wolf. Sampling community structure. In Www, 2010.
Michael Mathioudakis, Francesco Bonchi, Carlos Castillo, Aristides Gionis, and Antti Ukkonen. Sparsification of influence networks. In KDD, 2011.
Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov. Learning convolutional neural net- works for graphs. In ICML, 2016.
Veeru Sadhanala, Yu-Xiang Wang, and Ryan Tibshirani. Graph sparsification approaches for lapla- cian smoothing. In AISTATS, 2016.
Franco Scarselli, Marco Gori, Ah Chung Tsoi, Markus Hagenbuchner, and Gabriele Monfardini.
The graph neural network model. IEEE Transactions Neural Networks, 2009.
Martin Simonovsky and Nikos Komodakis. Dynamic edge-conditioned filters in convolutional neu- ral networks on graphs. In CVPR, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In ICLR, 2018.
Petar Veličković, William Fedus, William Hamilton, Pietro Liò, Yoshua Bengio, and R Devon Hjelm. Deep graph infomax. In ICLR, 2019.
Elli Voudigari, Nikos Salamanos, Theodore Papageorgiou, and Emmanuel J Yannakoudakis. Rank degree: An efficient algorithm for graph sampling. In ASONAM, 2016.
Keyulu Xu, Chengtao Li, Yonglong Tian, Tomohiro Sonobe, Ken-ichi Kawarabayashi, and Stefanie Jegelka. Representation learning on graphs with jumping knowledge networks. In ICML, 2018.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanie Jegelka. How powerful are graph neural
networks? ICLR, 2019.
Zhilin Yang. William w Cohen, and Ruslan Salakhutdinov. Revisiting semi-supervised learning with graph embeddings. In ICML, 2016.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In KDD, 2018a.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hi- erarchical graph representation learning with differentiable pooling. In NeurlPS, 2018b.
Jiani Zhang, Xingjian Shi, Junyuan Xie, Hao Ma, Irwin King, and Dit-Yan Yeung. Gaan: Gated attention networks for learning on large and spatiotemporal graphs. arXiv preprint 10Xi::8803.0724,, 2018a.
L--C Zhang and M Patone. Graph sampling. Metron, 2017.
Yizhou Zhang, Yun Xiong, Xiangnan Kong. Shanshan Li. Jinhong Mi, and Yangyong Zhu. Deep collective classification in heterogeneous information networks. In wwW, 2018b.
Yutao Zhang, Fanjin Zhang, Peiran Yao, and Jie Tang. Name disambiguation in aminer: Clustering, maintenance, and human in the loop. KDD, 2018c
Peixiang Zhao. gsparsify: Graph motif hased sparsification for graph clustering. In CIKM, 2015.
Chenyi Zhuang and Qiang Ma. Dual graph convolutional networks for graph-based semi-supervised classification. In WWW. 2018.
11

---

Under review as a conference paper at ICLR 2020
S1 DATASET DETAILS
In this section, we provide additional details about the Transaction datasets in our experiments. The Transaction dataset contains attributed graph that records transaction history between organizations in years: 2014 and 2015. Each node represents organization and each directed edge indi- cates transaction between two organizations, Node attributes include organization information like account balance, cash research, etc. Under the inductive experimental setting, We use the 47,772 organization data of the year 2014 for training and remaining data are hidden from the model. The 9,554 organizations are used for validation and 38,218 for testing. Validation and testing node sets from year 2015 and are not connected to the nodes in the training set. Like the PPI dataset, models need to generalize to unseen graph when testing on the Transaction dataset.
S2 EXPERIMENTAL SETTINGS
In this section, we provide more details about our implementation and experiments in favor of re- producibility.
$2.1 HARDWARE
All experiment run Linux machine with 16 Intel(R) Xeon(R) CPU (E5-2637 v4 @ 3.50GHz) and 128GB RAM. Some models (e.g. NeuralSparse and GCN) are accelerated by 4 NVIDIA GeForce GTXI0S0Ti GPU with 11GB RAM.
S2.2 IMPLEMENTATIONS OF NEURALSPARSE
We implement the proposed NeuralSparse in tensorflow framework for efficient GPU computation. In particular, the multi-layer neural network (Equation 4) in the sparsification network is imple- mented by two-layer feed-forward neural networks in all experiment, where the hyper-parameter k is searched between 2 and 50 for the optimal performance. We employ cross-entropy to formulate the loss function and apply Adam optimizer for training. The learning rate of Adam optimizer is initially set to be a = 1.0 x 10-3 We initial the weight matrices in the proposed NeuralSparse model with Xavier initialization.
In the following, we detail the network structures of NeuralSparse used on individual datasets. FC(a, f) means a fully- connecc layer with a input neurons and b output neurons activated by function ff (none means no activation function is used). GNN(a, b, f) means Graph Neural Network layer with input dimension a, output dimension b, and activation function f. We implement GNN layer with GCN, GraphSAGE, GAT, GIN in the experiments.
Reddit The sparsification network runs with: FC(1204, 16, ReLU))FC(16, 1, Suftex--oftmax). The structure of GNN is GNN(602, 128, ReLU)-GNN(128, 64, ReLU))FC(64, 41, softmax).
PPI The sparsification network runs with: FC(100, 16, ReL.U)FC(11, 1, Gumbel-Softman The structure of GNN is GNN(50, 128, Rel.U)-GNN(128, 128, Rel.U)-FC(128, 121, softmax).
Transaction The sparsification network runs with: FC(243, 16, ReLU))FC(16, 1, Gumbel- Softmax). The structure of GNN is GNN(121, 128, ReLU)-GNN(128, 32, ReLU)-FC(32, 2, soft- max). Note that there one-dimensional edge attribute indicating the transaction amount in this dataset.
Cora The sparsification network runs with: FC(2866, 32, ReLU)-FC(32, 1, Gumbel-Softmax). The structure of GNN is GNN(1433, 128, ReLU)-GNN(228, 64, ReLU)-FC(64, 7, softmax).
Citeseer The sparsification network runs with: FC(7406, 64, ReLU)-FC(64, 1, Sombbel-Sfftmx). The structure of GNN is GNN(3703, 128, ReLU)-GNN(12,, 28, 64, ReLU)-FC(64, 6, softmax).
As the spectral sparsification models cannot be jointly trained with subsequent GNN module, the sparsification process is treated as a preprocessing step. For Spectral Sparsifier (SS), is set to 0.4 in all datasets. For the Rank Degree algorithm (RD), we select 1% of nodes as the initial seeds and adopt p E (0.1, 0.2, 0.8) for the best results.
12

---

Under review as a conference paper at ICLR 2020
S3 QUALITATIVE EDGE SAMPLING EVALUATION
In this section, we qualitatively demonstrate the difference by Figure ((a) original graph, Figure 1(b) NeuralSparse, Figure 3(a) SS, and Figure 3(b) RD. In addition, we provide quantitative analysis in Table $1, where we report the percentage of edges that connect nodes of same class labels in sparsified graphs. Both qualitative and quantitative results suggest common trend: NeuralSparse prefers to select neighbors with the same labels compared with the baseline methods.
Table S1: Percentage of edges connecting nodes of the same labels
Reddit
PPI
Transaction
Cora
Citeseer
Original SS
53.1%
55.0%
67.3%
82.2%
73.1% 75.6%
50.9%
52.8%
62.8%
79.8%
RD 49.8%
53.5%
63.4%
72.3% 84.8%
NeuralSparse 59.6%
61.5%
76.8%
93.1%
87.4%
S4 EXPERIMENT WITH SIMILAR NUMBERS OF TRAINABLE PARAMETERS
In this section, we evaluate the impact brought by reducing the number of parameters in a GNN with NeuralSparse that the numbers of trainable parameters in NeuralSparse GNN and an original GNN are similar. In particular, we focus on GCN in this set of experiment. Using the same notation in S2.2, NeuralSparse-GCNY GCN-GGMNNCCCC is implemented as follows.
Reddit. NeuralSparse-GGer SaaesseeGG--CCCC GCN-Compact runs with: FC(1204, 8, ReLU)-FC(8, 1, Gumbel-Softtmax and GCN(602, 112, ReL.U-GCN(( 12, 64, Rel.U)-CC(64, 41, softmax). The total number of train- able parameters 86,856 in the SorralSpareeGCCN-ooompe while it is 87,872 in the original GCN.
PPI. SawpalSpppreeGN-Coomooe GCN(50, 118, ReLU)-GCN(1 18, 128, ReLU)-FC(128, 121, softmax). 'he total number of trainable while it is 38,272 in the original GCN.
runs with: FC(100, 16, ReLU)-FC(16, 1, Gumbel-Softmax) and
parameters is 38,108 108 in the SourallpaseeGGN--ommee
Transaction. NeuralSparse-GCNN GCN-Compaet runs with: FC(243, 16, ReLU)-FC(16, Softmax) and GCN(121, 100, ReLU)-GCN(100, 32, ReLU)-FC(32, 2, softmax). The total num- ber of trainable parameters 19,268 the NeuralSparse GCN-CCCmppan while is 19,648 in the original GCN.
Gumbel-
Cora NeuralSparse GCN- CCN-Compact runs with: FC(2866, 8, ReLU)-FC(8, Gumbel-SSfftan and GCN(1433, 115, ReLU)-GCN(I 32. ReLU)-FC(32, 7, softmax). The total number of trainable parameters 191, 1355 in the NeuralSparse GCreaarre-------eee GCN-GCNN---I Compact, while it is 192,064 in the original GCN.
runs with: FC(7406, 32, ReLU))FC(32, 1, Gumbel-SSftmax) and GCN(3703, 64, ReLU)-GCN(64, 32, ReLU)-FC(32, 6, softmax). The total number of trainable while it is 482,560 in the original GCN.
Citeseer SaaerralSSarr-GGG--CCCoC
parameters is 476,256 in the Saenallpprre-GGN-CCOO
Table S2: Node classification performance with similar numbers of trainable parameters
Dataset
Reddit
PPI
Transaction
Cora
Citeseer
Metries
Micro-F1
Micro-F1
AUC
Accuracy
Accuracy
GCN
0.922 0.041
0.532 + 0.024
0.564 0.018
0.810 + 0.027
0.694 + 0.020
NeuralSparse- GCN
0.946 + 0.020
0.600 = 0.014
0,610 + 0.022
0.821 + 0.014
0.715 + 0.014
NeuralSparse-
0.943 + 0.018
0.601 + 0.021
0.605 + 0.013
0.820 + 0.012
0.713 + 0.009
GCN-Compact
From the evaluation results shown in Table S2 we draw the following observations. First, both NeuralSparse-GGr and NeunISpaneeGGCN-CCoppet consistently outperform GCN on all the
13

---

Under review as a conference paper at ICLR 2020
datasets. Second, compared with NeuralSparse- GCC. GCN, parable prediction accuracy with smaller variance most cases.
achieves com-
SS How PERFORMANCE EVOLVES AS PAPEE-PRR & CHANGES?
0.66
AUC
0.64
NeuralSparre-GAT Testing
NeuralSparsee GAT Validation
NeuralSparse GraphSAGE in Testing
NeuralSparse GraphSAGE
0.62
12
15
18
Hyper parameter
Figure S1: Impact from hyper-parameter on validation and testing on the Transaction dataset
In this section, we demonstrate how the hyper-parameter k impacts the performance of in both validation and testing the Transac- tion dataset. terms validation, as shown in Figure S1, the validation performance increases when ranges from 2 to 10 with more available graph data. After k exceeds 10, the increase in validation performance slows down and turns to be saturated. In terms of testing performance, shares a similar trend when ranges from 2 10. Mcanwhile, the testing performance drops more after & exceeds 10.
NeuralSparse- GAT and SeurraSparse-GraphhS..
S6
EMPIRICAL COMPARISON BETWEEN NEURALSPARSE AND LDS
$6.1
EVALUATION RESULTS
In this section, we compare NeuralSparse and LDS (Franceschi et al., 2019) with the datasets in transductive setting. Here, we utilize three ways to prepare the input graphs of Cora and Citeseer datasets.
Setting A: k-NN graphs (Franceschi et al., 2019). In this setting, the graph structures
are completely missing. The input graphs are replaced with k-nearest neighbor graphs initialized from node features. The kNN graph is selected from (10, 20).
Setting original input graphs Cora and Citeseer datasets with the same random split as Kipf& & Welling (2017).
Setting C: edge union of original input graphs and k-NN graphs with k fixed as 10.
Table S3: Node classification performance in setting A
Cora(10)
Cora(20)
Citeseer(10) 10)
Citeseer(20)
GCN
0.641 + 0.009
0.631 + 0.013
0.653 + 0.012
0.671 + 0.019
LDS-GCN
0.715 + 0.008
0.703 0.011
0.691 + 0.021
0.715 + 0.011
NeuralSparse-GCN
0.723 + 0.012
0.719 + 0.008
0.731 + 0.011
0.724 +:2 0.017
Our observation is summarized as follows. In general, NeuralSparse and LDS achieves comparable node classification accuracy. Specifically, NeuralSparse has relatively better performance in Setting
14

---

Under review as a conference paper at ICLR 2020
Table S4: Node classification performance in setting
Cora
Citeseer
GCN
0,810 = 0.027
0.694 = 0.020
LDS NeuralSparse-GGr -CNN
0,831 0.017
0.727 = 0.021
0.821 + 0.014
0.724 + 0.014
Table S5: Node classification performance in setting C
Cora kNN
Citeseer + kNN
GCN
0.631 0.014
0.646 = 0.009
LDS
0.731 0.019
0.725 + 0.013
NeuralSparse-GGN
0.751 0.013
0.743 + 0.007
and Setting C. LDS performs slightly better Setting B. From the above observation, we conjec- ture that NeuralSparse is more robust to graphs with more random edges while LDS is more suitable in graph of relatively less noise by adding additional edges. We will verify the conjecture in the next subsection.
S6.2 RANDOM EDGE ADDITION CORA AND CITESEER
We further compare NeuralSparse and LDS (Franceschi et al., 2019) on the node classification tasks where original graph structure is available but more random edges introduced noise. Starting from the original graphs, we add edges by randomly sampling two nodes u, v from node set and connecting them.
The results are shown in Figure $2. both datasets, NeuralSparse achieves better performance compared with LDS the noise level goes beyond 200%. When the amount of noise increases, the classification accuracy of LDS drops significantly.
This result confirms our conjecture that NeuralSparse is more robust random edges, compared LDS.
0.8
Accuracy
0.7
Accuracy
0.6
0.5
GCN
GCN
0.5
NeuralSparse-GGN
NeuralSparse GCN
100%
300% 400% 500%
100% 200% 300% 400% 500% Total Edges / Original Edges
Total Edges Original Edges
(a) Cora
(b) Citeseer
Figure S2: Node classification performance when adding noise to graph structure.
With the above comments and experimental results, we hope to clarify the difference between the two models and demonstrate that our proposed NeuralSparse is more robust to noises in real-life graphs.
15

---

Under review as a conference paper at ICLR 2020
S7 HOW DO TASK-IRRELEVANT EDGES COULD NEGATIVELY IMPACT THE PERFORMANCE OF GCN?
In this section, we use am example to demonstrate how an imput graph with task-irrelevant edges could impact the performance of GCN. For the ease of discussion and visualization, we focus on a GCN with a simple architecture and synthetic graphs where we could adjust graph topology by prper-pprameters in graph generators.
In terms of GCN, we investigate a one-layer GCN
Jw Softmastt (AXW) Softmar(ZW)
where Å is normalized adjaceney matrix, X is the input node feature matrix, W is the GCN parameters, and ÁX denotes node representations in the aggregation space. Intuitively, the quality of Z has direct impact to this GCN's performance.
In terms of input graphs, we generate them for node classification tasks as follows.
1. Nodes and their labels. 2,000 nodes are generated, where 1,000 nodes are assigned with positive labels and the rest are assigned with negative labels.
2. Node features. Each node has two-dimensional feature vector. For positive nodes, the node features are generated from a Gaussian distribution, where Mpos (-0.5, 0) and Epos is a diagonal matrix with Epos (0, 0 Eos [1, 1] 0.3. For negative nodes, the node features are generated from another Gaussian distribution, where Unng (0.5, 0) and Eneg is a diagonal matrix with Eneg(0, = Enegl 1] 0.3.
3. Edges. Given hyper-parameter d, for each node, randomly selects d nodes its hop neighbors. With respect to this node classification task, an edge that connects two nodes of different labels could be irrelevant, bringing noise to the GCN.
625
-022
-02
-0.0
-64
(a)
(b) 2 10
(c) = 20
Figure S3: Distributions of in graphs with different
In Figure S3, the distributions node representation Z are demonstrated at different d. When 0, Å is an identity matrix so that we simply use input node features in model learning. As shown in Figure S3(a), it difficult find good boundary that well separates the positive and negative nodes by using node features only. However, when we adjusts d to 10 or 20 with richer connections, the situation doesn't It get better. Because of the noise introduced by irrelevant edges, becomes harder to find the classification boundary. While deep learning may still be able to find a complex boundary that well separates the training data, the boundary could overfit the introduced noise, resulting in low generalization power.
In Figure S4, we illustrate how NeuralSparse enhances the prediction accuracy of the GCN. In particular, we focus the graph with = 20, and sparsify this graph by NeuralSparse. As shown Figure S4, ranging the hyper-parameter from I to 15, the distributions is I, there is significant change compared with the distribution in Figure S3(a), as the amount of accessible relevant graph data still small. When & is increased to 5 or 10, the classification boundary becomes much clearer. As the edge generation process is uniformly random, the expected number relevant edges per node is roughly 10. When & 15, this could be an over-estimatt on the amount of relevant edges, making bit harder to find good separation.
Z vary. When
16

---

Under review as a conference paper at ICLR 2020
675
0.
6A-
62
-0.0
-144
-1.0
(a)
(b) k 5
(c) 10
(d) k
Figure S4: Distributions of Z in sparsified subgraphs by NeuralSparse
-34
-06
-25
60
35
(a)
(b) k 5
(c)
(d) k
Figure S5: Distributions of Z in sparsified subgraphs by random downsampling
In Figure S5, we demonstrate how random downsampling could impact the prediction accuracy of the GCN. In general, we could not see any significant improvement. Indeed, is crucial to perform a task-driven sparsification as NeuralSparse does.
17


Reviews:
[{"review_id": "ryeIwujgcB", "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": "The paper proposes a trainable graph sparsification mechanism that can be used in conjunction with GNNs. This process is parameterized using a neural network and can be trained end-to-end (by using the Gumbel softmax reparameterization trick) with the loss given by the task at hand. Experimental results on node classification tasks are presented.\n\nThe paper is well written and easy to follow. I think that overall the method is sound and well executed. \n\nEmpirical results are convincing as the method consistently improves performance (compared to not applying the sparsification) over several GNNs. I feel that the claim of the improvement could be softened a bit. Please correct me if I'm reading Table 2 wrongly, with the exception of the Transaction dataset, most differences are below 3%. I am not familiar with these datasets so I cannot judge the significance of the improvement. In any case, the reduction in computation with the improved performance is a strong result.\n\nThe baselines that include unsupervised graph sparsification as a pre-processing make the results worse (with respect to not applying it) in all cases. This shows that for this problem, a task driven specification is crucial for maintaining performance. \n\nNeural Sparse model has more parameters than the version that does not use a sparsifier. Do you think that this could influence the performance? Would it be possible to compare using similar number of trainable parameters? I assume that using more parameters would not imply better performance for the baseline, but it would be good to clarify.\n\nI can understand that the performance of the model depends critically on k, and that k might vary significantly over datasets. In my view, it would be informative to include (maybe in the supplementary material) the performance variations on the corresponding validation sets as one changes k for the different datasets (as done in Figure 3 (c)).\n\nIn Algorithm 2 it would be better to use a different letter for the edge set (as currently looks like the real numbers).", "extra_scores": {"experience_assessment": "I have read many 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": "r1xkiEt2Fr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "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 argue that existing GCN-based approaches may pose non-trival overfitting risk during the training phase, especially when high-dimensional features and high-degree entities are observed in the graphs. To address the issue, the authors integrate graph sparsification with conventional graph neural nets. Experimental results show the efficacy of the proposed model in a series of benchmark datasets. In general, the paper is easy-to-follow and well-organized. My main concern is there lack some insightful discussion regarding the problem motivation and the proposed algorithm. In particular,\n(1) It is unclear why existing GCN-based approaches can not handle the cases shown in Fig. 1. Is there any evidence (either theoretical or empirical) or reference to support this argument? \n(2) The motivation example shown in Fig. 1 is confusing. Conventionally, graph sparsification aims to find smaller subgraphs from the input graphs that preserve the key structures. However, in Fig. 1 (b), the sparsified subgraph seems only downsampling the edges while preserving all the nodes as the original graph. The authors may want to clarify whether the sparisified subgraph has the identical size as the input graph.\n(3) Some notations are not formally defined before using them. In Eq. 2, what do Q_\\theta and Q_\\phi denote? \n(4) The statement of \"trade-off between model accuracy and graph complexity by tuning the hyperparameter k\" is vulnerable. If the overfitting exists, larger k may result in lower accuracy in the testing phase. \n(5) What is the complexity of f_\\Phi()?  \n(6) The complexity (i.e., f(km)) of the proposed model is problematic. As stated at the beginning of this paper, the paper targets the graph with \"complex local neighborhood\", where each node is described by rich features and neighbors. In other words, the target graph is not sparse. In this case,  the complexity of the proposed algorithm can be intractable, especially when k is large and m is close to n^2. ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "r1ei61PDYr", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The authors propose a supervised graph sparsification technique that \"mitigates the overfitting risk by reducing the\ncomplexity of input graphs.\"\n\nThe idea is as follows: there is a sparsification network which samples subgraphs (adjacency matrices) by computing a probability distribution for each edge and drawing the existence of each edge from this distribution. The sparsified graph is then fed to a GNN that computes a classification loss. Since the authors use the Gumbel-softmax trick the method is end-to-end differentiable and the output consists of a node classifier and a graph generative model that can be used to sample sparsified graphs. \n\nThe paper covers an interesting topic and results in some good numbers on standard benchmark datasets. I also like the idea to use the Gumbel-softmax trick to make the entire model differentiable. \n\nUnfortunately, the authors miss to cite and discuss highly related work [1] (ICML 2019). In this work, the authors also maintain a graph generative model (also by parameterizing edges but with iid Bernoulli RVs), also sampling graphs from this generative model, and also using these sampled graphs to train a GNN for semi-supervised node classification. The resulting model is also end-to-end differentiable. Instead of using a Gumbel-softmax to keep the method differentiable (given that we have discrete random variables) the authors propose a novel way to compute gradients for the parameters of the Bernoulli RVs by posing the problem as a bilevel optimization problem. In [1] the graph cannot only be sparsified but also enriched with edges that might be beneficial for the classification accuracy. Indeed, it was shown that adding edges is more beneficial than removing edges. The results on Cora and Citeseer are better than the results reported by the authors in this submission. At the very least, the authors should familiarize themselves, discuss, and compare empirically to [1]. \n\nThe existence of this previous work also reduces the novelty of the proposed approach. However, if a  comparison to [1] would be added, the submission could be seen as an alternative instance of the framework presented in [1]. I would be willing to increase my score to accept, if the authors provide such a comparison in an updated version. \n\n\n[1] https://arxiv.org/abs/1903.11960\n\n\n-----\n\nI've read the rebuttal and while I don't agree necessarily with all statements made by the authors, I am happy to increase my score based on the discussion of previous work. ", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This submission proposes a graph sparsification mechanism that can be used when training GNNs.

Strengths:
-The paper is easy to follow.
-The proposed method is sound and effective.

Weaknesses:
-The novelty is limited.

Given the limited novelty and the number of strong submissions to ICLR, this submission, while promising, does not meet the bar for acceptance.
Decision: Reject