Iterative Deep Graph Learning for Graph Neural Networks
Authors: Yu Chen
Lingfei Wu
Mohammed J. Zaki
Venue:  (2020)
Keywords: deep learning
graph neural networks
graph learning

Abstract: In this paper, we propose an end-to-end graph learning framework, namely Iterative Deep Graph Learning (IDGL), for jointly learning graph structure and graph embedding simultaneously. We first cast graph structure learning problem as similarity metric learning problem and leverage an adapted graph regularization for controlling smoothness, connectivity and sparsity of the generated graph. We further propose a novel iterative method for searching for hidden graph structure that augments the initial graph structure. Our iterative method dynamically stops when learning graph structure approaches close enough to the ground truth graph. Our extensive experiments demonstrate that the proposed IDGL model can consistently outperform or match state-of-the-art baselines in terms of both classification accuracy and computational time. The proposed approach can cope with both transductive training and inductive training. 

Under review as a conference paper at ICLR 2020
ITERATIVE DEEP LEARNING FOR GRAPH NEU- RAL NETWORKS
Anonymous authors Paper under double-blind review
ABSTRACT
In this paper, we propose an end-to-end graph learning framework, namely Iterative Deep Graph Learning (IDGL), for jointly learning graph structure and graph embedding simultaneously. We first cast graph structure learning problem as similarity metric learning problem and leverage an adapted graph regularization for controlling smoothness, connectivity and sparsity of the generated graph. We further propose novel iterative method for searching for hidden graph structure that augments the initial graph structure. Our iterative method dynamically stops when the learned graph structure approaches close enough to the optimal graph. Our extensive experiments demonstrate that the proposed IDGL model can consis- tently outperform or match state-of-the-art baselines in terms of both downstream task performance and computational time. The proposed approach can cope with both transductive training and inductive training.
INTRODUCTION
Recent years have seen significantly growing amount of interest in graph neural networks (GNNs), especially on efforts devoted to developing more effective GNNs for node classification (Li et al.
2016 Kipf& & Welling 2016 Hamilton et al. (0017)), graph classification (Ying et al. 8b18b] Ma ct al. 2019), and graph generation (Samanta et al. 2018 Li et al., 2018b You et 2018), Encour- aged by their huge success, GNNs have widely been used in a variety of domain specific applications such as machine reading comprehension (Chen et al. 2019a), semantic parsing (Xu al. 2018b), natural language generation (Chen et al. 2019b), and healthcare informatics (Gao et al.) 2019).
Despite GNNs' powerful ability of learning expressive node embeddings, unfortunately, GNNs can only be used when graph-structured data is available. Many real-world applications naturally ad- mit network-structtrred data like social networks or graph-structured data like chemical compounds. However, it is questionable if these intrinsic graph-structures stream tasks. This is partially because the raw graphs were constructed from the original feature space, which may not reflect the "true" graph topology after feature extraction and transformation. Another potential reason is that real-world graphs are often noisy due to the inevitably error-prone data measurement or collection. More importantly, many applications such those in natural lan- guage processing may only have non-graph structured data or even just the original feature matrix, requiring additional graph construction from the original data matrix to formulate graph data.
optimal for the supervised down-
Independently, there has been an increasing amount of work studying the dynamic model of in- teracting systems utilizing implicit interaction models (Sukhbaatar al., 2016 Hoshen, 2017 Van Steenkiste et al., 2018). There models can be viewed as message passage based graph nerual networks (Gilmer et 2017) that pass messages over the fully connected graph through the mes- sage passing function (Sukhbaatar et al. 2016) or the use of an attention mechanism (Hoshen) 2017]] Van Steenkiste et al., 2018). This has been further extended by Kipf et al. (2018), where they addressed the problem by inferring encoder. However, these methods cannot be directly applicable to joint learning the graph structure and graph representations when the graph is noisy or even not available.
explicit interaction structure using variational graph auto-
More recently, Franceschi et al. (2099) presented a new approach for jointly learning the graph and the parameters of GNNs, where they learnt discrete probability distribution on the edges of the graph by approximately solving a bilevel program. Their experimental results have shown promising performance in both cases where the input graph is either corrupted not available.

---

Under review as a conference paper at ICLR 2020
However, this approach has severe scalability issue since it needs to learn N number of (Bernoulli) random variables to model joint probability distribution on the edges the graph consisting of N number of vertices. More importantly, it can only be used for transductive setting, which means this method cannot consider new nodes during the testing.
To address these limitations, in this paper, we propose Iterative Deep Graph Learning (IDGL) framework for jointly learning the graph structure and the GNN parameters that are optimized to- wards the prediction task hand. Our IDGL framework consisting of five parts: graph learning neural network to generate a graph topology; 2) a graph regularization neural network for controlling the smoothness, connectivity and sparsity of the generated graph; 3) graph embedding neural net- work for generating node embeddings: 4) an iterative method to dynamically stop learning when the optimal graph is found; and 5) a prediction neural network for performing downstream prediction task. In particular, we present a graph learning neural network that casts graph learning problem as a data-driven similarity metric learning task for constructing a graph. We then adapt techniques for learning graphs from smooth signals (Kalofolias) 2016) serve as graph regularization. More importantly, we propose a novel iterative method to search for hidden graph structure that augments the initial graph structure toward an optimal graph for the supervised prediction tasks.
We highlight three contributions of our approach as follows:
We propose an end-to-end graph learning framework for jointly learning graph structure and graph embedding simultaneously. The proposed approach can cope with both trans- ductive training and inductive training.
We propose to iteratively learn a better graph structure with updated node embeddings, and in the meanwhile, learn better node embeddings with the updated graph structure. In addi- tion, the iterative method dynamically stops when the learned graph structure approaches close enough to the optimal graph based our proposed stopping criterion.
We cast graph structure learning problem as similarity metric learning problem and lever- age an adapted graph regularization for controlling smoothness, connectivity and sparsity of the generated graph.
Our extensive experiments demonstrate that our model can consistently outperform or match
baselines.
AN ITERATIVE DEEP GRAPH LEARNING FRAMEWORK
0 Alag [1-
(1
A)X
C ((0)
c
Σ, A
(t)
(X, Ag, Lo)
Similarity learning meel U. e
(X, A 10 [
Graph regularization
C
cit)
r())
prod
||
Data points
GNN
Prediction task
1-th iteration
Repeated until condition satisfied
Figure 1: Overview of the proposed model. Dashed lines in the leftmost data points indicate the
initial graph topology Ao either from the ground-truth graph if it exists or otherwise from the graph constructed using the kNN strategy. Best viewed in color.
With this paper address the challenging problem of automatic graph structure learning for GNNs. We are given a set n objects V associated with a feature matrix gdxn encoding the feature descriptions of the objects. The goal is automatically learn the graph structure G, typically in the form of an adjacency matrix A e = underlying the set of objects, which will be consumed by GNN-based model for downstream prediction task.
Unlike most existing methods that construct graphs based on hand-crafted rules or features as a preprocessing step, our proposed Iterative Deep Graph Learning (IDGL) framework formulates
2

---

Under review as a conference paper at ICLR 2020
the problem iterative learning problem that jointly learns the graph structure and the GNN parameters iteratively in an end-to-end manner. The overall model architecture shown in Fig. [
2.1 GRAPH LEARNING AS SIMILARITY METRIC LEARNING
In traditional graph theory, various methods have been explored construct a graph from data points. These methods usually apply metric function to compute the similarity between pairs of nodes during preprocessing. and then consume the constructed graph in downstream task. Unlike these methods, in this work, we design a learnable metric function for graph structure learning, which will jointly trained with the prediction model dedicated to a downstream task.
2.1.1 SIMILARITY METRIC LEARNING
Common options for metrics include cosine similarity, radial basis function (RBF) kernel and atten- tion mechanisms. A good metric function is supposed to be learnable and expressively powerful. We design weighted cosine similarity as our metric function, defined as,
Sij cos( w C Vc, W Vv))
where @ denotes the Hadamard product, and w is a learnable weight vector which has the same dimension as the input vectors and v,, and learns to highlight different dimensions of the vectors.
After preliminary experiments, we have found extending Eq. ( to multi-head version be ben- eficial, similar to Vaswani et al. (2017); Veličković et al. (017)) Specifically, we use m weight vectors (each vector representing one perspective) to compute m independent similarity matrices using Eq. (I). and take their average as the final similarity S:
m
cos( W: O V. We V3), 8ig
Intuitively, s computes the cosine similarity between the two input vectors V, and vj, for the k-th perspective where each perspective considers one part of the semantics captured in the vectors.
2.1.2 GRAPH SPARSIFICATION VIA E-NEIGHBORHOOD
An adjacency matrix (same for metric) is supposed to be non non-negative while Sty ranges between [-1,1]. In addition, many underlying graph structures are much more sparse than a fully connected graph, which is not only computationally expensive but also makes little sense for most applications. We hence proceed to extract symmetric sparse adjacency matrix from S by considering only the e-neighborhood for each node. Specifically, we mask off those elements in S which are smaller than certain non-negative threshold E.
Aij { Sij 0
Siy >
otherwise
2.2 GRAPH REGULARIZATION
In graph signal processing (Shuman et al. 2013), each column of the feature matrix X can be considered as graph signal. widely adopted assumption for graph signals that values change smoothly across adjacent nodes. Given an undirected graph with symmetric weighted adjacency matrix A, the smoothness of a set of graph signals x1...., Xn. e Rd is usually measured by the Dirichlet energy (Belkin & Niyogi 2002).
2 A x Lx
(4)
where tr(-) denotes the trace of matrix, L A is the graph Laplacian, and A,y the degree matrix. As can be seen, minimizing Ω X) forces adjacent nodes to have similar features, thus enforces smoothness of the graph signals on the graph associated A.
However, solely minimizing the above smoothness loss will result in the trivial solution A = 0. Also, it is desirable to have control of how sparse the resulting graph is. Following Kalofolias
3

---

Under review as a conference paper at ICLR 2020
2016), impose additional constraints to the learned graph,
S(A) -311 A1) + >
(5)
where || ||r denotes the Frobenius norm matrix. As we can see, the first term penalizes the formation of disconnected graphs via the logarithmic barrier, and the second term controls sparsity by penalizing large degrees due to the first term.
In this work, we borrow the above techniques, and apply them as regularization terms to the graph learned by Eqs. (2) and (3) As shown in Eq. (6). the overall graph regularization loss defined as the sum of the above losses, which is able to control the smoothness, connectivity and sparsity of the resulting graph where a, B and y are all non-negative hyperparameters.
LG= = al((, + f(A)
(6)
2.3 ITERATIVE METHOD FOR JOINT GRAPH STRUCTURE AND REPRESENTATION LEARNING
2.3.1 JOINT GRAPH STRUCTURE AND REPRESENTATION LEARNING
We expect the graph structure underlying a set of objects to serve two purposes: on the one hand, it should respect the semantic relations among the objects, which enforced by the metric func- tion (Eq. (2) and the smoothness loss (Eq. on the other hand, it should suit the needs of the downstream prediction task.
Compared to previous works which directly optimize the adjacency matrix based either some graph regularization loss (Kalofolias & Perraudin (017)) or some task-dependent prediction loss (Franceschi al., 2019), we propose to learn an optimal similarity metric function as well as the GNN parameters by minimizing a joint loss function combining both the prediction loss defined on the downstream task and the graph regularization loss, namely, L Lpred + Lg.
Note that our graph learning framework is agnostic to various GNNs and prediction tasks. In this paper, adopt two-layered GCN (Kipf & Welling (016) where the first layer maps the node features to the intermediate embedding space (Fqq. (7)), and the second layer further maps the inter- mediate node embeddings to the output space (Eq. (8))
Z ReLU (AXW,)
ý (AZW,)
(8)
fored E(}.y)
(9)
where Ä is the normalized adjacency matrix, a(.) is a task-dependent output function, and E(.) desk-dependent loss function. For instance, for node classification problem, a(-) softmax function for predicting a probability distribution over set of classes, and 2(-) is a cross-entropy function for computing the prediction loss.
We now discuss how to obtain the normalized adjacency matrix A. For some problems when an initial graph is available, our preliminary experiments showed that it is harmful totally discard the initial graph structure. Previous works (Veličković et al., (017)) Jiang et al. 2019) inject the initial graph structure into the graph learning mechanism by performing masked attention, which might limits its graph learning ability. This is because there is no way for their methods to learn weights for those edges that do not exist in the initial graph, but carry useful topological information. With the assumption that the optimal graph structure is potentially a small shift from the initial graph structure, we combine the learned graph structure with the initial graph structure as follows,
Aij
À ALa (1
Σ, Aij
(10)
where Lo is the normalized adjacency matrix of the initial graph, defined as, Lo D A,,, 1/2 and Dy is its degree matrix. The adjacency matrix learned by Eqs. (2) and (3) is row normalized such that each sums to 1. A hyperparameter À is used to balance the trade-off between the learned graph structure and the initial graph structure. If such an initial graph structure not available, we instead use kNN graph constructed based on cosine similarity.
4

---

Under review as a conference paper at ICLR 2020
Algorithm 1: IDGL: Iterative Deep Graph Learning Framework
Input: X. Ao]
Parameters : m, E, a, 3. A, 6, T, m[
Output: O A (+) y
[A. KNN(X, k)]
Init.
Ao to KNN graph if Ag is unavailable // Learn the adj. matrix // Compute node embeddings // Compute prediction loss Compute graph regularization loss // Compute joint loss
A [0) A (0) - [X, Ao) using Eqs. 2
and
10
7 < {A X] using Eq.
(Ä (0) 7 .y) using Eqs. 8 and 9
C - {A (0), X] using Eqs.
( - ppd + (0)
t +-0 O
while (1 == 0 or ||A(0) A A > 6) A
(1
and < T do
1-t+1
10
A A() A - (Z Ao using Eqs.
and 10
1/ Refine the adj. matrix
A [AA(0 A 1 using Eq.
11
Z - (A(), X] using Eq.
11 Refine node embeddings
ÿ (A (") using Eq.
8
// Compute task output
cit) (f.y) } using Eq.
C + {A()) (0) X using Eqs.
15
L (1) C
16
17 end
18
< _(0) + Σi= C
/t
19 Training then
Back- propaare L to update model weights e
21 end
2.3.2 ITERATIVE METHON FOR GRAPH LEARNING
Some previous works (Veličković al. 2017) rely solely on raw node features learn the graph structure based on some attention mechanism, which we think have some limitations since raw node features might not contain enough information to learn good graph structures. Our preliminary experiments showed that simply applying some attention function upon these raw node features does not help learn meaningful graphs (i.e., attention scores are kind of uniform). Even though we train the model jointly using the task-dependent prediction loss, we are limited by the fact that the similarity metric computed based on the potentially inadequate raw node features.
To address the above limitation, we propose an Iterative Deep Graph Learning (IDGL) framework. A sketch of the IDGL framework is presented Algorithm [ Inputs and operations squared brack- ets are optional. Specifically, besides computing the node similarity based on their raw features, we further introduce another learnable similarity metric function Eq. (2h that is rather computed based on the intermediate node embeddings, demonstrated in Line Compared to the raw node features, these intermediate node embeddings usually reside on a low-dimensional manifold of the raw node feature space, and optimized towards the downstream prediction task. The aim is that the metric function defined on this node embedding space able to learn topological information supplementary the one learned solely based on the raw node features. order to combine the advantages of both the raw node features and the intermediate node embeddings, we make the final learned graph structure as linear combination of both of them,
A (4) 7 (6)
A (0)
(11)
where ( and À are the two normalized adjacency matrices learned by Eq. 10 at the t-th iteration and the initialization step before the iterative loop. respectively.
Furthermore, we can see from Line 10 to Line 12 the algorithm repeatedly refines the adjacency
matrix À with the updated node embeddings Z (-1), and in the meanwhile, refines the node
embeddings Z with the updated adjacency matrix Ä (0) The iterative procedure dynamically stops
5

---

Under review as a conference paper at ICLR 2020
when the learned adjacency matrix converges (with certain threshold 5) the maximal number of iterations is reached Line (). Compared to using a fixed number of iterations globally, the advantage of applying this dynamical stopping strategy becomes more clear when are doing mini-hatch training since we can adjust when to stop dynamically for each example graph in the mini-batch. At each iteration, joint loss combining both the task-dependent prediction loss and the graph regularization loss is computed Line [6).. After all iterations, the overall loss will be paok-propagated through all previous iterations update the model parameters (Line 20
2.4
FORMAL ANALYSIS
2.4.1
CONVERGENCE OF THE ITERATIVE LEARNING PROCEDURE
While it is challenging theoretically prove the convergence of the proposed iterative learning pro- cedure due to the arbitrary complexity of the involved learning model, here we want to conceptually understand why it works in practice. Fig. 2 shows the information flow of the learned adjacency matrix A and the intermediate node embedding matrix Z during the iterative procedure. For the sake of simplicity, we omit some other variables such A. As we can see, at 1-th iteration, A(1) is computed based on (t-1) (Line 10), and (c) is computed based À (0) (Line 12) which is com- puted based on A (*) (Eq. (10 We further denote the difference between the adjacency matrices at the t-th iteration and the previous iteration by ( Similarly, we denote the difference between the node embedding matrices the t-th iteration and the previous iteration by 8
If we assume that 5(2) ( then we can expect that (² ((L) because conceptually more similar node embedding matrix (i.e., smaller 82) supposed to produce more similar adjacency matrix (i.e., smaller d.A) given the fact that model parameters keep the same through iterations. Similarly, given that 6(2) 6
(1) we can expect that ( (1) Following this chain of reasoning, can easily
extend it to later iterations. In order to see why the assumption 5 < s(0) makes sense in practice,
we need to recall the fact that (0 measures the difference between ( and X, which is usually larger than the difference between (11) and ())), namely 5/2) We will empirically examine the convergence property of the iterative learning procedure in the experimental section.
A
(0)
11)
A
(2)
X
0
Z
Z
Z
33
Z
Figure 2: Information flow of the proposed iterative learning procedure.
2.4.2 MODEL COMPLEXITY
The cost of learning an adjacency matrix is (n?hh) for n nodes and data in R², while computing node embeddings costs O(n2d d + ndh), computing task output costs O(n²h). and computing the total loss costs (n) We set the maximal number of iterations to T, hence the overall complexity is (T + nd + hd)). If we assume that d z h and n >> d, the overall complexity is (Tdn"))
3 EXPERIMENTS
In this section, we conducted series of experiments to answer three main questions. First, when the graph topology is available, can IDGL further improve performance on downstream tasks by learning additional topological information supplementary the given topology? We also wanted to examine IDGL is robust to noisy graphs with random edge deletions or additions. Second, can IDGL achieve reasonably good results semi- supervise learning problems for which graph is not available. Third, what is the performance of IDGL on inductive learning problems where there new nodes during the testing?

---

Under review as a conference paper at ICLR 2020
In addition to answering the above three questions, we also analyzed the proposed model in multiple dimensions. First, we conducted an ablation study to assess the impact of different model com- ponents. Second, empirically examine whether the iterative learning procedure in practice. Third, we explored and compared different stopping strategies that can be used in the iterative learning framework. Finally, we empirically compared IDGL with LDS (Franceschi al.) 2019) in terms of training efficiency. The details on model settings are provided in Appendix [C] The implementation of our model will be made publicly available upon the acceptance of this paper.
converge
3.1 DATASETS
The benchmarks used in our experiments include two network benchmarks, three data point bench- marks and two text benchmarks. Cora and Citeseer are two commonly used network benchmarks for evaluating graph-based learning algorithms (Sen et al., 2008). The imput features are bag of words and the task node classification. In addition to Cora and Citeseer where the graph topology is available, we evaluate IDGL on three data point benchmarks (i.e., Wine, Breast Cancer (Cancer) and Digits from the UCI machine learning repository (Dua & Graff] 2017)). The task is also node classification. Finally, to demonstrate the effectiveness of IDGL inductive learning problems, we conduct document classification and regression tasks on the 20Newsgroups data (20News) and the movie review data (MRD) (Pang & Lee, 2004), respectively. In this setting, regard each document as a graph containing each word as node. Please refer to Appendix [B for data statistics.
3.2 SETUP AND BASELINES
For Cora and Citeseer, we follow the experimental setup of previous works (Kipf & Welling 2016 Veličković et al. 2017 Franceschi et al., 2019). For Wine, Cancer and Digits, we follow the ex- perimental setup of Franceschi et al. 10.1). For 20News, we randomly select 30% examples from the training data as the development set. For MRD, we split the data to train/dev/test sets using a 60%/20%/20% split. The reported results are averaged over 5 runs with different random seeds.
Our main baseline in the transductive setting is LDS. Similar to our work, LDS also jointly learns the graph structure and the parameters of GNNs. However, LDS is incapable of handling inductive learning problems since it aims at directly optimizing the discrete probability distribution on the edges of the underlying graph, which makes it unable to handle unseen nodes/graphs in the test- ing phase. The experimental results of several semi-supervised (e.g.. label propagation (LP) (Zhu) (et al., 2003), manifold regularization (ManiReg) (Belkin et al. 2006), semi-supervised embedding (SemiEmb) (Weston et al.) ) and supervised learning (logistic regression (LogReg), support vector machines (Linear and RBF SVM). random forests (RF), and feed-forward neural networks (FFNN)) baselines reported in the LDS paper. For the sake of completeness, their results here. For ease of comparison, we also copy the reported results of LDS even though we rerun the experiments of LDS using the official code released by the authors.
directly copy
In addition, for Cora and Citeseer, we include GCN (Kipf & Welling, 2016) and GAT (Veličković et al.) 2017) as baselines. In order to evaluate the robustness of IDGL to noisy graphs, we also compare IDGL with GCN on graphs with edge deletions or additions. For data point benchmarks where the graph topology not available, we conceive a kNN-GCN baseline where kNN affinity graph on the data set is first constructed as preprocessing step before applying a GCN. For 20News and MRD in the inductive setting, we compare IDGL with BiLSTM (Hochreiter Schmidhuber, 1997) baseline and kNN-GCN.
3.3
EXPERIMENTAL RESULTS
The results of transductive and inductive experiments are shown in Table Table First of all, we can see that IDGL outperforms all baseline methods in 6 out of 7 benchmarks, which demon- strates the effectiveness of the proposed method. Besides, by comparing the results of GCN, GAT and IDGL Cora and Citeseer, and considering the fact that our method is actually based on GCN, we can conclude that our graph learning method can greatly help the node classification task even when the graph topology is given. When the graph topology is not given, we observe that kNN- GCN works well and provides competitive results compared to the supervised baselines that do not leverage graph structures. This indicates the benefits of learning and exploiting underlying graph
7

---

Under review as a conference paper at ICLR 2020
Table 1: Test accuracy (#t standard deviation) in percentage on various classification datasets in the transductive setting. The star symbol means that run the experiments and report the results.
Methods
Cora
Citeseer
Wine
Cancer
Digits
Logkeg
60.8 (0.0)
62.2 (0.0)
92.1 (1.3)
93.3 (0.5)
85.5 (1.5)
Linear SVM
58.9 (0.0)
58.3 (0.0)
93.9 (1.6)
90.6
87.1 (1.8)
RBF SVM
59.7 (0.0)
60.2 (0.0)
94.1
(3.1)
86.9 (3.2)
RF
58.7 (0.4)
60.7 (0.7)
93.7
(1.7
83.1 (2.6)
FENN
56.1 (1.6)
56.7 (1.7)
(1.7
(1.2
36.3 (10.3)
LP
(0.2)
(6.7)
(3.7)
76.6 (0.5)
(3.1)
ManiReg
62.3 (0.9)
(1.6
(0.1
81.8 (0.1)
(0.9
SemiEmb
63.1 (0.1)
68.1 (0.1)
(019
89.7 (0.1)
90.9 (0.1)
LDS
84.1 (0.4)
75.0 (0.4)
91.9 (0.3)
92.5 (0.7)
GCN
81.0 (0.2)
70.9 (0.3)
GAT
82.5 (0.4)
70.9 (0.4)
ANN-GCN
95.9 (0.9)
94.7 (1.2)
89.5 (1.3)
LDS*
83.9 (0.6)
74.8 (0.3)
96.9 (1.4)
93.4 (2.4)
90.8 (2.5)
IDGL
84.5 (0.3)
74.1 (0.2)
97.8 (0.6)
95.1 (1.0)
93.1 (0.5)
Table Test scores (# standard deviation) in percentage on classification (accuracy) and regression (RP) datasets in the inductive setting.
Methods
20News
MRD
BiLSTM
80.0 (0.4)
53.1 (1.4)
kNN-GCN
81.3 (0.6)
60.1 (1.5)
IDGL.
83.6 (0.4)
63.7 (1.8)
structures. Compared to KNN-GCN, IDGL consistently achieves much better results on all datasets, which shows the power of jointly learning graph structures and GNN parameters. Compared to out of benchmarks. Unlike LDS which can only
LDS, IDGL achieves better performance handle transductive setting, IDGL can easily handle inductive setting without modification of the algorithm. This is because IDGL aims at optimizing a metric function instead the discrete proba- bility distribution on the edges. The good performance on 20News and MRD verifies the capability of IDGL on inductive learning problems.
To evaluate the robustness of IDGL noisy graphs, construct graphs with random edge dele- tions or additions. Specifically, we randomly remove or add 25%, 50% and 75% of the edges in the original graphs. The results the edge deletion graphs and edge addition graphs are shown in Fig. 3 and Fig. [ respectively. As we can clearly see, compared to GCN, IDGL achieves better results in all scenarios and much more robust noisy graphs. While GCN completely fails in the edge addition scenario, IDGL is still able to perform reasonably well. We conjecture this is because Eq. (1O) is formulated in form of skip-connection, by lowering the value of X, we enforce the model to rely less on the initial noisy graph that contains too much additive random noise.
85
75.0
GCN
72.5
Accuraci
70.0
75
67.5
65.0
70
62.5
0
25
50
75
25
50
75
Missing edges (%)
Missing edges (%)
(a) Cora
(b) Citesecr
Figure 3: Test accuracy (# standard deviation) in percentage for the edge deletion scenario.
85
75
70
60
55
45
40
25
30
10
15
25
25
50
75
Added edges (%)
Added edges (%)
(a) Cora
(b) Citeseer
Figure 4: Test accuracy (t: standard deviation) in percentage for the edge addition scenario.
8

---

Under review as a conference paper at ICLR 2020
3.4 ABLATION STUDY
We perform an ablation study to assess the impact of different model components. As shown in Ta- ble[3] we can see significant performance drop consistently all datasets (e.g., 3.1% % Citeseer) by turning off the iterative learning component, which demonstrates the effectiveness of the pro- posed iterative learning framework for the graph learning problem. We can also see the benefits of jointly training the model with the graph regularization loss. For instance, when training the model without the graph regularization loss, the performance on Citeseer drops from 74. I to 71.5%. %.
Table Ablation study on various classification datasets.
Methods IDGL w/o graph reg.
Cora
Citeseer
Wine
Cancer
Digits
20News
84.5 (0.3)
74.1 (0.2)
97.8 (0.6)
(1.0)
93.1 (0.5)
83.6 (0.4)
84.3 (0.4)
71.5 (0.9)
97.3 (0.8)
94.9 (1.0)
91.5 (0.9)
83.4 (0.5)
w/o IL
83.5 (0.6)
71.0 (0.8)
97.2 (0.8)
94.7 (0.9)
92.4 (0.4)
83.0 (0.4)
3.5 MODEL ANALYSIS
In Fig. 5 we show the evolution of the learned adjacency matrix and accuracy through iterations in the iterative learning procedure in the testing phase. We compute the difference between adjacency
which typically ranges from 0 to 1. As we can see, both the adjacency matrix and accuracy converge quickly through iterations.
matrices at consecutive iterations 8(4) ||A (*) A (t- / /I 19
This empirically verifies the analysis we made on the convergence property of the iterative learning procedure in Section 2.4.1
1.00
1.00
6A
Accuracy 85.2
6a
Accuracy
74.2
0.75
85.0 0.75
74.0
0.50
84.8 0.50
73.8
0.25
84.6 0.25
73.6
84.4 0.00
73.4
0.00
2
Num. iterations
Num. of iterations
(a) Cora
(b) Citeseer
Figure 5: Evolution of the learned adjacency matrix and test accuracy (in %) through iterations in the iterative learning procedure.
There are two natural ways of designing the stopping strategy for iterative learning methods. We either use fixed number of iterations, dynamically determine if the learning procedure already converges or not based on some stopping criterion. Fig. 6 we empirically compare the effectiveness of the above two strategies. We run IDGL Cora (left) and Citeseer (right) using different stopping strategies with 5 runs, and report the average accuracy. As we can see, dynamically adjusting the number of iterations using the stopping criterion works better in practice.
74.00
of iter.
# of iter. Converge
Accuracy
Converge
73.75
84.2
73.50
73.25
84.0
73.00
83.8
72.75
2 3
4
Num. of iterations (a) Cora
Num. of iterations
(b) Citeseer
Performance comparison (i.e., test accuracy in %) of different stopping strategies: i) using a fixed number of iterations (blue line), and ii) using a stopping criterion to dynamically determine the convergence (red line).
Figure 6:

---

Under review as a conference paper at ICLR 2020
3.6 TIMING
Finally, we compare the training efficiency of IDGL, LDS and other classic GNNs (e.g.. GCN and GAT) on various benchmarks. All experiments are conducted on the same machine which has an Intel 17-2700K CPU, an Nvidia Titan Xp GPU and 16GB RAM, and are repeated 5 times with different random seeds. Results are shown in Table 4 As we can see, both IDGL and LDS slower than GCN and GAT, which is expected since GCN and GAT do not need to learn graph structures simultancously. IDGL is consistently faster than LDS, but in general, they are comparable. We also find that the iterative learning part is the most time consuming in IDGL.
Table 4: Mean and standard deviation of training time on various benchmarks (in seconds).
Benchmarks
Cora
Citeseer
Wine
Cancer
Digits
GCN
(1)
(())
GAT
(5)
28 (5)
LDS
390 (82)
585 (181)
33 (15)
25 (6)
72 (35)
IDGL
237 (21)
563 (100)
(7)
(11)
65 (12)
IDGL w/o IL
49 (8)
61 (15)
3 (2)
(1)
2(1)
RELATED WORK
In the field of graph signal processing, researchers have explored various ways of learning graphs from data (Dong et al. 2016 Kalofolias [016 Kalofolias & Perraudin 2017 Egilmez al. (017], with certain assumptions (e.g., smoothness) on the graph signals or structural constraints (e.g., con- nectivity and sparsity) on the underlying graphs. Notably, these works in general do not consider any downstream task that will consume the learned graph structures.
Over the past few years, graph neural networks (GNNs) (Kipf & Welling 2016 Gilmer al. 2017
Hamilton et al. 2017b Li et al. 2015) have drawn increasing attention, and have many success- computer vision (Noreliffe-Brown al. 2018)) natural language processing (Xu et al., 201 8a b and recommender systems (Ying et al., (018a). How to apply GNNs to applica- tions where the underlying graph structures are unavailable becomes an emergent and challenging problem. However, manually constructing graphs from data heavily relies on domain knowledge and is not very scalable. Very recently, researchers have explored methods to automatically con- struct graph of objects -Noreliffe-Browe
Tul applications
et al. 2018 Choi et al. 2019 Franceschi et al. 2019 Li jet al., 2018a) or words (Liu et al. 20188] Chen et al. 2019a b) when applying GNNs to non-graph structured data. However, these methods merely optimize the graphs towards the downstream tasks without utilizing the techniques which have proven to be useful in graph signal processing.
More recently, Franceschi et al. (2019) proposed the LDS model for jointly learning the graph and the parameters of GNNs by leveraging the bilevel optimization technique. Unlike LDS, in our model, optimize a joint loss combining both task-specific prediction loss and graph regularization loss. Moreover, we propose to repeatedly refine the learned adjacency matrix and the node embeddings via an iterative deep graph learning framework. will be interesting see if our model can benefit from adopting the bilevel optimization technique, which can motivate future work. However, one big limitation of the LDS work that it optimizes the discrete probability distribution on the edges of the graph, which makes it unable to handle the inductive setting.
CONCLUSION
In this paper, we proposed an Iterative Deep Graph Learning (IDGL) framework for jointly learning the graph structure and the GNN parameters that are optimized towards the prediction task. The pro- posed method is able to iteratively search for hidden graph structures that better help the downstream prediction task. We cast graph structure learning problem similarity metric learning problem and leverage an adapted graph regularization for controlling smoothness, connectivity and sparsity of the generated graph. Our extensive experiments demonstrate that the proposed IDGL model can consistently outperform or match state-of-ther baselines in terms of both classification accuracy and computational time. We leave how to design better metric functions future work.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps and spectral techniques for embedding and clustering. Advances in neural information processing systems, pp. 585-591, 2002.
Mikhail Belkin, Partha Niyogi, and Vikas Sindhwani. Manifold regularization: A geometric frame- work for learning from labeled and unlabeled examples. Journal of machine learning research, (Nov):2399-22) 24344, 2006.
Yu Chen, Lingfei Wu, and Mohammed J Zaki. Graphflow: Exploiting conversation flow with graph neural networks for conversational machine comprehension. arXiv preprint arXiv:1906 00059, 2019a.
Yu Chen, Lingfei Wu, and Mohammed J Zaki. Reinforcement learning based graph-to-sequence model for natural question generation. arXiv preprint 1tt.:v:/900.094422 2019b.
Edward Choi, Zhen Xu, Yujia Li, Michael W Dusenberry, Gerardo Flores, Yuan Xue, and An- drew M Dai. Graph convolutional transformer: Learning the graphical structure of electronic health records. arXiv preprint 1rXiv::906.047/01 2019.
Xiaowen Dong, Dorina Thanou, Pascal Frossard, and Pierre Vandergheynst. Learning laplacian matrix in smooth graph signal representations. IEEE Transactions on Signal Processing, 64(23); 6160-6173, 2016.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. http::::///achhi ics uci edu/ml
Hilmi E Egilmez, Eduardo Pavez, and Antonio Ortega. Graph learning from data under laplacian and structural constraints. IEEE Journal of Selected Topics in Signal Processing, 11(6):825-84) 841, 2017.
Luca Franceschi, Mathias Niepert, Massimiliano Pontil, and Xiao He. Learning discrete structures for graph neural networks. arXiv preprint arXiv: //600, 2019.
Yuyang Gao, Lingfei Wu, Houman Homayoun, and Liang Zhao. Dyngraph2seq: Dynamic-graph-e sequence interpretable learning for health stage prediction in online health forums. arXiv preprint arXiv:1908.08499 2019.
Justin Gilmer, Samuel Schoenholz, Patrick F Riley, Oriol Vinyals, and George E Dahl. Neural message passing for quantum chemistry. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pp. 1263-1272. JMLR. org, 2017.
Will Hamilton, Zhitao Ying, and Jure Leskovec. Inductive representation learning on large graphs.
In Advances in Neural Information Processing Systems, 2017a.
Will Hamilton, Zhitao Ying, and Jure Leskovee. Inductive representation learning on large graphs. In Advances in Neural Information Processing Systems, pp. 1024-1034, 2017b.
Sepp Hochreiter and Jürgen Schmidhuber. Long short-term memory. Neural computation, 9()): 1735-1780, 1997.
Yedid Hoshen. Vain: Attentional multi-agent predictive modeling. Advances in Neural Informa- fion Processing Systems, pp. 2701-2711, 2017.
Bo Jiang, Ziyan Zhang. Doudou Lin, Jin Tang, and Bin Luo. Semi-supervised learning with graph learning connolttoon networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pp. 11313-11320. 2019.
Vassilis Kalofolias. How to learn a graph from smooth signals. In Artificial Intelligence and Statis- tics, pp. 920-929, 2016.
Vassilis Kalofolias and Nathanaël Perraudin. Large scale graph learning from smooth signals. arXiv preprint 1r.0v./7100.5666 2017.
11

---

Under review as a conference paper at ICLR 2020
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.6990, 2014.
Thomas Kipf, Ethan Fetaya, Kuan-Chieh Wang. Max Welling, and Richard Zemel. Neural relational inference for interacting systems. arXiv preprint arXiv: 2018.
Thomas N Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. arXiv preprint arXiv: /609,02907, 2016.
Ruoyu Li, Sheng Wang, Feiyun Zhu, and Junzhou Huang. Adaptive graph convolutional neural networks. In Thirty-Second AAAI Conference on Artificial Intelligence, 2018a.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. arXiv preprini arXiv: 2015.
Yujia Li, Daniel Tarlow, Mare Brockschmidt, and Richard Zemel. Gated graph sequence neural networks. International Conference on Learning Representations, 2016.
Yujia Li, Oriol Vinyals, Chris Dyer. Razvan Pascanu, and Peter Battaglia. Learning deep generative models of graphs. arXiv preprint arXiv:1803.033: 130.03334, 2018b.
Pengfei Liu, Shuaichen Chang, Xuanjing Huang, Jian Tang, and Jackie Chi Kit Cheung. Contextu- 1,08600, 2018.
alized non-local neural networks for sequence learning. arXiv preprint
Yao Ma, Suhang Wang, Charu C Aggarwal, and Jiliang Tang. Graph convolutional networks with eigenpooling. arXiv preprint arXiv: 13107, 2019.
Will -Noreliffe-Broww Stathis Vafeias, and Sarah Parisot. Learning conditioned graph structures for interpretable visual question answering. In Advances in Neural Information Processing Systems, pp. 8344-8353, 2018.
Bo Pang and Lillian Lee. A sentimental education: Sentiment analysis using subjectivity summa- rization based on minimum cuts. In Proceedings of the 42nd annual meeting on Association for Computational Linguistics, pp. 271, Association for Computational Linguisties, 2004.
Bidisha Samanta, Abir De, Niloy Ganguly, and Manuel Gomez- Gomez-Rodriguez Rodriguez. Designing random graph models using variational autoencoders with applications to chemical design. arXiv preprint 1802. 2018.
Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi-Rad. Collective classification in network data. Al magazine, 29(3):93-93, 2008.
David Shuman, Sunil K Narang, Pascal Frossard, Antonio Ortega, and Pierre Vandergheynst. The emerging field of signal processing on graphs: Extending nigh-dimensional data analysis net- works and other irregular domains. IEEE signal processing magazine, 30(3):83-9) 98, 2013.
Sainbayar Sukhbaatar, Rob Fergus, et al. Learning multiagent communication with backpropaga- tion. In Advances Neural Information Processing Systems, pp. 2244 2252, 2016.
Sjoerd Van Steenkiste, Michael Chang, Klaus Greff, and Jürgen Schmidhuber. Relational neural ex- pectation maximization: Unsupervised discovery of objects and their interactions. arXiv preprint arXiv: 10353, 2018.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Eukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances in neural information processing systems, pp. 0998-6008, 2017.
Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. arXiv preprint 1700 2017.
Jason Weston, Frédéric Ratle, Hossein Mobahi, and Ronan Collobert. Deep learning via semi- supervised embedding. In Neural Networks: Tricks of the Trade, pp. 639-655. Springer, 2012.
Kun Xu, Lingfei Wu, Zhiguo Wang, and Vadim Sheinin. Graph2seq: Graph to sequence learning with attention-based neural networks. arXiv preprint arXiv: 1804.0882. 2018a.
12

---

Under review as a conference paper at ICLR 2020
Kun Xu, Lingfei Wu, Zhiguo Wang. Mo Yu, Liwei Chen, and Vadim Sheinin. Exploiting rich syntactic information for semantic parsing with graph-to-sequence model. arXiv preprint DrXhv:1808.07624 2018b.
Kun Xu, Lingfei Wu, Zhiguo Wang, Mo Yu, Liwei Chen, and Vadim Sheinin. Sql-to-text generation with graph-to graph-to-sequence model. arXiv preprint arXiv:/809005255 2018c.
Rex Ying, Ruining He, Kaifeng Chen, Pong Eksombatchai, William L Hamilton, and Jure Leskovec. Graph convolutional neural networks for web-scale recommender systems. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp. 974 983. ACM, 8a.
Zhitao Ying, Jiaxuan You, Christopher Morris, Xiang Ren, Will Hamilton, and Jure Leskovec. Hi- erarchical graph representation learning with differentiable pooling. In Advances in Neural Infor- mation Processing Systems, pp. 4800-4810 10, 2018b.
Jiaxuan You, Rex Ying, Xiang Ren, William L Hamilton, and Jure Leskovec. Graphrnn: Generating realistic graphs with deep auto-regressive models. arXiv preprint arXiv:1802 08773, 2018.
Xiaojin Zhu, Zoubin Ghahramani, and John Lafferty. Semi-supervised learning using gaussian fields and harmonic functions. In Proceedings the 20th International conference Machine learning (ICML-03), pp. 912-919, 2003.
A
EFFECT OF X
Table 5: Test scores (# standard deviation) with different values of À on the Cora data.
Methods / À
0.9
0.8
0.7
0.6
0.5
IDGL
83.6 (0.4)
84.5 (0.3)
83.9 (0.3)
82.4 (0.1) 80.9 (0.2)
B DATA STATISTICS
Table 6: Data statisties.
Benchmarks
Train/Dev/Test
Task
Setting
Cora
140/500//,000 1,000
node classification
transductive
Citeseer
120/500/1,00
node classification
transductive
Wine
10/20/158
node classification
transductive transductive
Cancer
10/20/539
node classification
Digits
50/100/1,647
node classification graph elassification graph regression
transductive
20News
7,919/3.395/7.532
inductive
MRD
3,003/1,001/1,002
inductive
C MODEL SETTINGS
In all our experiments, we apply dropout ratio of 0.5 after GCN layers except for the output GCN layer. During the iterative learning procedure, we also apply a dropout ratio of 0.5 after the intermediate GCN layer, except for Citeseer (no dropout) and Digits (0.3 dropout). For experiments on text benchmarks, we keep and fix the 300-dim GloVe vectors for words that appear more than 10 times in the dataset. For long documents, for the sake of efficiency, we cut the text length to maximal 1,000 words. We apply dropout ratio of 0.5 after word embedding layers and BiLSTM layers. The batch size is set to 16. And the hidden size is set to 128 and 64 for 20News and MRD, respectively. For all other benchmarks, the hidden size is set 16 follow the original GCN paper. We use Adam (Kingma & Ba 2014) as the optimizer. For the text benchmarks, we set the learning rate to le-3, For all other benchmarks, decay set to 5e-4. Below we show the hyperparameter associated to IDGL for all benchmarks. All hyperparameters tuned on the development set.
set the learning rate to 0.01 and apply L2 norm regularization with weight
13

---

Under review as a conference paper at ICLR 2020
Table Hyperparameter associated IDGL all benchmarks.
Benchmarks
X
"1
B
5
Cora
0.9
0.1
0.2
0.0
0.0
0
4e-5
10
Citeseer
0.6
0.5
0.4
0.0
0.2
0.3
le-3
10
Wine
0.8
0.7
0.1
0.1
0.3
20
0.75
1e-3
10
Cancer
0.25
0.1
0.4
0.2
40
0.9
1e-3
10
Digits
0.4
0.1
0.4
0.1
0.0
24
0.65
8
1e44
10
20News
0.1
0.2
0.5
0.01
0.2
450
0.3
le-3
10
MRD
0.5
0.9
0.4
0.05
0.2
350
0.3
1e-3
10
14


Reviews:
[{"review_id": "rJlSbRu6tH", "reviewer": "AnonReviewer1", "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 paper introduces an iterative method called IDGL for learning both the graph structure (more precisely adjacency matrix) and parameters of the graph neural network.\n\nThe idea of iteratively refining an adjacency matrix A to obtain sparsity and smoothness is interesting and the experimental results are quite supportive. The main issue here is that the regularization terms in Eqs. 4, 5, 6 (which should be considered to be the most important in the paper) are exactly similar to those in [1] (see Eq. 12 in [1]).  This reduces the novelty of the paper.\n\nOther parts in the paper such as using similarity between nodes (e.g. self-attention) to compute adjacency matrix or using the learned adjacency matrix with graph neural network is not new and have been done by many other works. There is also the rich related literature on graph generation (e.g., as in drug design), graph transformation (e.g., as in chemical reaction), structure learning in classical probabilistic graphical models, graph pooling (which is essentially building new latent graphs from an original graph), knowledge-graph completion, etc. This is not to say that the problem is solved (it isn't), but it is fair to place this work in a broader context.\n\nAbout the experiments, I have several concerns. First, I am not sure why the authors say that LDS [2] does not support inductive learning? LDS uses input node features to learn the unknown graph structure so I think it should be able to do inductive learning. DeepWalk or Node2Vec are examples of transductive methods because they do not use the node features. Second, for the running time comparison between IDGL and LDS, what are the size and number of parameters used in each model since they greatly affect the running time.\n\nMinor point: please clean up duplicates in the reference list.\n\n[1] How to learn a graph from smooth signals, Kalofolias et. al. 2016\n[2] Learning discrete structures for graph neural networks, Franceschi et. al. 2019.\n\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "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": "S1xl73mpYB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper leverages metric learning to learn graph structure jointly with the learning of graph embedding. Firstly, it defines the similarity between any pair of nodes as the cosine similarity of nodal representations learned from attributes from nodes. Some tricks such as multi-head and sparsification are applied to learned cosine similarity to enhance the performance. Secondly, the authors introduce several graph regularizations to make the learned graph smooth, connected, sparse and non-trivial. Finally, the learned graph is linearly combined with the existing graph, using a hyperparameter \\lambda. The convergence and time complexity are analyzed. The authors design experiments on five datasets. The paper also contains some issues:\n\n1. Actually, the proposed framework is learning an extra graph adjacency matrix from nodal features, and further train GNN jointly on those two graphs. Therefore, the analysis of \\lambda is necessary. However, this part is missing in the paper.\n\n2. The improvements comparing with LDS is not significant. Besides, LDS only uses the optimized graph structure to train GNN, while the proposed framework use both learning structure and the original one (or the kNN result). It raises the question if the proposed framework can still out-perform LDS if LDS also takes the original graph as input to train GNN.\n\n3. The learned graph should be better interpreted. For example, the cosine similarity on citation graphs with sparse features is very likely to be zero. As a result, the learned graph can be extremely sparse with very few non-zero entries. It would be interesting.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory."}, "extra_text": {}}, {"review_id": "Bkxq-J6pFr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper proposes an extension of learning graph structure and GNN concurrently, by considering that real-world graphs are often noisy and incomplete. The idea of optimizing the intrinsic graph structure iteratively for down-stream prediction tasks is interesting. Experimental results demonstrate the effectiveness of proposed method. \n\nStrengths:\n1）the paper proposes a learnable similarity metric function and a graph regularization for learning an optimal graph structure for prediction.\n2）Besides raw node features, the paper attempts to optimize graph structures via learned node embeddings in an iterative manner. \n3）The paper is easy to read, and experiments show that the proposed method performs well.\n\nWeaknesses:\n1）Compared with LDS [1], this work seems to overlook the bi-level optimization problem for learning model parameters based on the optimal graph structure. The reason behind this method is expected. \n2）Although the paper claims that the dependence of raw node features for learning graph structure has been weakened,  empirical analysis on this point is not given. The feature matrices in experiments are not strictly independent with graph structures.\n3) As shown in Appendix B, too many hyper-parameters are involved. I conjecture it will be difficult to reproduce the experimental results.\n4) Eqs.(2), (3) and (10) are problematic. Node embeddings Z should be included in them. Eq.(10) does not have theoretical proof. According to Eq.(10), the method cannot handle graphs with noisy edges. In experiments, there are edge deletions, but no edge addings. Experiments with attacked graph are expected.\n5) Although this method is claimed efficient, it is indeed slower than the classic GNNs due to the iterative operation. The details of training time comparison between this method and GNNs such as GCN and GAT will be helpful. I was wondering why this method is faster than LDS. Is it due to removing the bi-level optimization problem ? \n6) Although the method can handle inductive training, it is hardly scale to big networks. Pubmed is an open citation network with around 20,000 nodes similar to Cora and Citeseer. Those three datasets are popularly used in GNNs as testbed. However, Pubmed is not used in this work. I conjecture that the new method cannot handle such a big dataset efficiently.\n\nOverall, this proposed method is well motivated, but the technical novelty is limited. \n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "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": {}}]

Author rebuttal:

Meta-review: The submission proposes a method for learning a graph structure and node embeddings through an iterative process. Smoothness and sparsity are both optimized in this approach. The iterative method has a stopping mechanism based on distance from a ground truth. 

The concerns of the reviewers were about scalability and novelty. Since other methods have used the same costs for optimization, as well as other aspects of this approach, there is little contribution other than the iterative process. The improvement over LDS, the most similar approach, is relatively minor. 

Although the paper is promising, more work is required to establish the contributions of the method. Recommendation is for rejection.

Decision: Reject