Year: 2019

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 the learned graph structure approaches close enough to the optimal graph. Our extensive experiments demonstrate that the proposed IDGL model can consistently 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.

heading: 1 INTRODUCTION
text: Recent years have seen a 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., 2017a), graph classification (Ying et al., 2018b; Ma et al., 2019), and graph generation (Samanta et al., 2018; Li et al., 2018b; You et al., 2018). Encouraged 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 et 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 admit network-structured data like social networks or graph-structured data like chemical compounds. However, it is questionable if these intrinsic graph-structures are optimal for the supervised downstream 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 as those in natural language 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.
Independently, there has been an increasing amount of work studying the dynamic model of interacting systems utilizing implicit interaction models (Sukhbaatar et al., 2016; Hoshen, 2017; Van Steenkiste et al., 2018). There models can be viewed as message passage based graph nerual networks (Gilmer et al., 2017) that pass messages over the fully connected graph through the message 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 an explicit interaction structure using a variational graph autoencoder. 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.
More recently, Franceschi et al. (2019) presented a new approach for jointly learning the graph and the parameters of GNNs, where they learnt a 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 or not available.
However, this approach has severe scalability issue since it needs to learn N2 number of (Bernoulli) random variables to model joint probability distribution on the edges of 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 an Iterative Deep Graph Learning (IDGL) framework for jointly learning the graph structure and the GNN parameters that are optimized towards the prediction task at hand. Our IDGL framework consisting of five parts: 1) a 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) a graph embedding neural network 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 a downstream prediction task. In particular, we present a graph learning neural network that casts a 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) to 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 transductive 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 addition, the iterative method dynamically stops when the learned graph structure approaches close enough to the optimal graph based on our proposed stopping criterion.
• We 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.
• Our extensive experiments demonstrate that our model can consistently outperform or match state-of-the-art baselines.

heading: 2 AN ITERATIVE DEEP GRAPH LEARNING FRAMEWORK
text: With this paper we address the challenging problem of automatic graph structure learning for GNNs. We are given a set of n objects V associated with a feature matrix X P Rdˆn encoding the feature descriptions of the objects. The goal is to automatically learn the graph structure G, typically in the form of an adjacency matrix A P Rnˆn, underlying the set of objects, which will be consumed by a GNN-based model for a 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
the problem as an iterative learning problem that jointly learns the graph structure and the GNN parameters iteratively in an end-to-end manner. The overall model architecture is shown in Fig. 1.

heading: 2.1 GRAPH LEARNING AS SIMILARITY METRIC LEARNING
text: In traditional graph theory, various methods have been explored to construct a graph from data points. These methods usually apply a metric function to compute the similarity between pairs of nodes during preprocessing, and then consume the constructed graph in a downstream task. Unlike these methods, in this work, we design a learnable metric function for graph structure learning, which will be jointly trained with the prediction model dedicated to a downstream task.

heading: 2.1.1 SIMILARITY METRIC LEARNING
text: Common options for metrics include cosine similarity, radial basis function (RBF) kernel and attention mechanisms. A good metric function is supposed to be learnable and expressively powerful. We design a weighted cosine similarity as our metric function, defined as,
sij “ cospw d vi,w d vjq (1)
where d denotes the Hadamard product, and w is a learnable weight vector which has the same dimension as the input vectors vi and vj , and learns to highlight different dimensions of the vectors.
After preliminary experiments, we have found extending Eq. (1) to a multi-head version to be beneficial, similar to Vaswani et al. (2017); Veličković et al. (2017). Specifically, we use m weight vectors (each vector representing one perspective) to compute m independent similarity matrices using Eq. (1), and take their average as the final similarity S:
skij “ cospwk d vi,wk d vjq, sij “ 1
m
m ÿ k“1 skij (2)
Intuitively, skij computes the cosine similarity between the two input vectors vi 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 ε-NEIGHBORHOOD
An adjacency matrix (same for a metric) is supposed to be non-negative while sij ranges between r´1, 1s. 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 a symmetric sparse adjacency matrix A from S by considering only the ε-neighborhood for each node. Specifically, we mask off those elements in S which are smaller than certain non-negative threshold ε.
Aij “ " sij sij ą ε 0 otherwise (3)

heading: 2.2 GRAPH REGULARIZATION
text: In graph signal processing (Shuman et al., 2013), each column of the feature matrix X can be considered as a graph signal. A widely adopted assumption for graph signals is 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 P Rd is usually measured by the Dirichlet energy (Belkin & Niyogi, 2002),
ΩpA,Xq “ 1 2 ÿ
i,j
Aij ||xi ´ xj ||2 “ trpXTLXq (4)
where trp¨q denotes the trace of a matrix, L “ D´A is the graph Laplacian, and D “ ř
j Aij is the degree matrix. As can be seen, minimizing ΩpA,Xq forces adjacent nodes to have similar features, thus enforces smoothness of the graph signals on the graph associated to 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
(2016), we impose additional constraints to the learned graph,
fpAq “ ´β1T logpA1q ` γ||A||2F (5)
where || ¨ ||F denotes the Frobenius norm of a 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 is defined as the sum of the above losses, which is able to control the smoothness, connectivity and sparsity of the resulting graph where α, β and γ are all non-negative hyperparameters.
LG “ αΩpA,Xq ` fpAq (6)

heading: 2.3 ITERATIVE METHOD FOR JOINT GRAPH STRUCTURE AND REPRESENTATION LEARNING

heading: 2.3.1 JOINT GRAPH STRUCTURE AND REPRESENTATION LEARNING
text: 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 is enforced by the metric function (Eq. (2)) and the smoothness loss (Eq. (4)); 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 on either some graph regularization loss (Kalofolias & Perraudin, 2017), or some task-dependent prediction loss (Franceschi et 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, we adopt a two-layered GCN (Kipf & Welling, 2016) where the first layer maps the node features to the intermediate embedding space (Eq. (7)), and the second layer further maps the intermediate node embeddings to the output space (Eq. (8)).
Z “ ReLUprAXW1q (7) py “ σprAZW2q (8) Lpred “ `ppy,yq (9)
where rA is the normalized adjacency matrix, σp¨q is a task-dependent output function, and `p¨q is a task-dependent loss function. For instance, for node classification problem, σp¨q is a softmax function for predicting a probability distribution over a set of classes, and `p¨q is a cross-entropy function for computing the prediction loss.
We now discuss how to obtain the normalized adjacency matrix rA. For some problems when an initial graph is available, our preliminary experiments showed that it is harmful to totally discard the initial graph structure. Previous works (Veličković et al., 2017; 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,
rA “ λL0 ` p1´ λq Aij ř
j Aij (10)
where L0 is the normalized adjacency matrix of the initial graph, defined as, L0 “ D´1{20 A0D ´1{2 0 , and D0 is its degree matrix. The adjacency matrix learned by Eqs. (2) and (3) is row normalized such that each row 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 is not available, we instead use a kNN graph constructed based on cosine similarity.
Algorithm 1: IDGL: Iterative Deep Graph Learning Framework Input: X, yr,A0s Parameters : m, ε, α, β, γ, λ, δ, T , ηr, ks Output: Θ, rAptq, py
1 rA0 Ð kNNpX, kqs // Init. A0 to kNN graph if A0 is unavailable 2 Ap0q, rAp0q Ð tX,A0u using Eqs. (2), (3) and (10) // Learn the adj. matrix 3 Zp0q Ð t rAp0q,Xu using Eq. (7) // Compute node embeddings 4 Lp0qpred Ð t rA
p0q,Zp0q,yu using Eqs. (8) and (9) // Compute prediction loss 5 Lp0qG Ð tA
p0q,Xu using Eqs. (4)–(6) // Compute graph regularization loss 6 Lp0q Ð Lp0qpred ` L p0q G // Compute joint loss 7 tÐ 0 8 while pt ““ 0 or ||Aptq ´Apt´1q||2F ą δ||Ap0q||2F q and t ă T do 9 tÐ t` 1
10 Aptq, rAptq Ð tZpt´1q,A0u using Eqs. (2), (3) and (10) // Refine the adj. matrix 11 sAptq Ð t rAptq, rAp0qu using Eq. (11) 12 Zptq Ð t sAptq,Xu using Eq. (7) // Refine node embeddings 13 pyÐ t sAptq,Zptqu using Eq. (8) // Compute task output 14 Lptqpred Ð tpy,yu using Eq. (9) 15 LptqG Ð tA
ptq,Xu using Eqs. (4)–(6) 16 Lptq Ð Lptqpred ` L ptq G 17 end 18 LÐ Lp0q `
řt i“1 L piq{t 19 if Training then 20 Back-propagate L to update model weights Θ 21 end

heading: 2.3.2 ITERATIVE METHOD FOR GRAPH LEARNING
text: Some previous works (Veličković et al., 2017) rely solely on raw node features to 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 is 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 in Algorithm 1. Inputs and operations in squared brackets are optional. Specifically, besides computing the node similarity based on their raw features, we further introduce another learnable similarity metric function ( Eq. (2)) that is rather computed based on the intermediate node embeddings, as demonstrated in Line 10. Compared to the raw node features, these intermediate node embeddings usually reside on a low-dimensional manifold of the raw node feature space, and are optimized towards the downstream prediction task. The aim is that the metric function defined on this node embedding space is able to learn topological information supplementary to the one learned solely based on the raw node features. In order to combine the advantages of both the raw node features and the intermediate node embeddings, we make the final learned graph structure as a linear combination of both of them,
sAptq “ η rAptq ` p1´ ηqrAp0q (11)
where rAptq and rAp0q 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, as we can see from Line 10 to Line 12, the algorithm repeatedly refines the adjacency matrix rAptq with the updated node embeddings Zpt´1q, and in the meanwhile, refines the node embeddings Zptq with the updated adjacency matrix rAptq. The iterative procedure dynamically stops
when the learned adjacency matrix converges (with certain threshold δ) or the maximal number of iterations is reached ( Line 8). Compared to using a fixed number of iterations globally, the advantage of applying this dynamical stopping strategy becomes more clear when we are doing mini-batch training since we can adjust when to stop dynamically for each example graph in the mini-batch. At each iteration, a joint loss combining both the task-dependent prediction loss and the graph regularization loss is computed ( Line 16). After all iterations, the overall loss will be back-propagated through all previous iterations to update the model parameters (Line 20).

heading: 2.4 FORMAL ANALYSIS

heading: 2.4.1 CONVERGENCE OF THE ITERATIVE LEARNING PROCEDURE
text: While it is challenging to theoretically prove the convergence of the proposed iterative learning procedure 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 as rA. As we can see, at t-th iteration, Aptq is computed based on Zpt´1q (Line 10), and Zptq is computed based on rAptq (Line 12) which is computed based on Aptq (Eq. (10)). We further denote the difference between the adjacency matrices at the t-th iteration and the previous iteration by δptqA . Similarly, we denote the difference between the node embedding matrices at the t-th iteration and the previous iteration by δptqZ .
If we assume that δp1qZ ă δ p0q Z , then we can expect that δ p2q A ă δ p1q A because conceptually more similar node embedding matrix (i.e., smaller δZ) is supposed to produce more similar adjacency matrix (i.e., smaller δA) given the fact that model parameters keep the same through iterations. Similarly, given that δp2qA ă δ p1q A , we can expect that δ p2q Z ă δ p1q Z . Following this chain of reasoning, we can easily extend it to later iterations. In order to see why the assumption δp1qZ ă δ p0q Z makes sense in practice, we need to recall the fact that δp0qZ measures the difference between Z p0q and X, which is usually larger than the difference between Zp1q and Zp0q, namely δp1qZ . We will empirically examine the convergence property of the iterative learning procedure in the experimental section.

heading: 2.4.2 MODEL COMPLEXITY
text: The cost of learning an adjacency matrix is Opn2hq for n nodes and data in Rh, while computing node embeddings costs Opn2d ` ndhq, computing task output costs Opn2hq, and computing the total loss costsOpn2dq. We set the maximal number of iterations to T , hence the overall complexity is OpTnpnh` nd` hdqq. If we assume that d « h and n " d, the overall complexity is OpTdn2q.

heading: 3 EXPERIMENTS
text: In this section, we conducted a 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 to the given topology? We also wanted to examine if IDGL is robust to noisy graphs with random edge deletions or additions. Second, can IDGL achieve reasonably good results on semi-supervised learning problems for which a graph is not available. Third, what is the performance of IDGL on inductive learning problems where there are new nodes during the testing?
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 components. Second, we empirically examine whether the iterative learning procedure can converge 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 et 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.

heading: 3.1 DATASETS
text: The benchmarks used in our experiments include two network benchmarks, three data point benchmarks and two text benchmarks. Cora and Citeseer are two commonly used network benchmarks for evaluating graph-based learning algorithms (Sen et al., 2008). The input features are bag of words and the task is 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 on 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, we regard each document as a graph containing each word as a node. Please refer to Appendix B for data statistics.

heading: 3.2 SETUP AND BASELINES
text: For Cora and Citeseer, we follow the experimental setup of previous works (Kipf & Welling, 2016; Veličković et al., 2017; Franceschi et al., 2019). For Wine, Cancer and Digits, we follow the experimental setup of Franceschi et al. (2019). 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 testing 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., 2012)) and supervised learning (logistic regression (LogReg), support vector machines (Linear and RBF SVM), random forests (RF), and feed-forward neural networks (FFNN)) baselines are reported in the LDS paper. For the sake of completeness, we directly copy 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.
In addition, for Cora and Citeseer, we include GCN (Kipf & Welling, 2016) and GAT (Veličković 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 is not available, we conceive a kNN-GCN baseline where a kNN affinity graph on the data set is first constructed as a preprocessing step before applying a GCN. For 20News and MRD in the inductive setting, we compare IDGL with a BiLSTM (Hochreiter & Schmidhuber, 1997) baseline and kNN-GCN.

heading: 3.3 EXPERIMENTAL RESULTS
text: The results of transductive and inductive experiments are shown in Table 1 and Table 2. First of all, we can see that IDGL outperforms all baseline methods in 6 out of 7 benchmarks, which demonstrates the effectiveness of the proposed method. Besides, by comparing the results of GCN, GAT and IDGL on 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 kNNGCN 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
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 LDS, IDGL achieves better performance in 4 out of 5 benchmarks. Unlike LDS which can only handle transductive setting, IDGL can easily handle inductive setting without a modification of the algorithm. This is because IDGL aims at optimizing a metric function instead of the discrete probability 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 on noisy graphs, we construct graphs with random edge deletions or additions. Specifically, we randomly remove or add 25%, 50% and 75% of the edges in the original graphs. The results on the edge deletion graphs and edge addition graphs are shown in Fig. 3 and Fig. 4, respectively. As we can clearly see, compared to GCN, IDGL achieves better results in all scenarios and is much more robust to 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. (10) is formulated in a form of skip-connection, by lowering the value of λ, we enforce the model to rely less on the initial noisy graph that contains too much additive random noise.

heading: 3.4 ABLATION STUDY
text: We perform an ablation study to assess the impact of different model components. As shown in Table 3, we can see a significant performance drop consistently on all datasets (e.g., 3.1% on Citeseer) by turning off the iterative learning component, which demonstrates the effectiveness of the proposed 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.1% to 71.5%.

heading: 3.5 MODEL ANALYSIS
text: 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 matrices at consecutive iterations as δptqA “ ||Aptq´Apt´1q||2F {||Aptq||2F which typically ranges from 0 to 1. As we can see, both the adjacency matrix and accuracy converge quickly through iterations. This empirically verifies the analysis we made on the convergence property of the iterative learning procedure in Section 2.4.1.
There are two natural ways of designing the stopping strategy for iterative learning methods. We can either use a fixed number of iterations, or dynamically determine if the learning procedure already converges or not based on some stopping criterion. In Fig. 6, we empirically compare the effectiveness of the above two strategies. We run IDGL on 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.

heading: 3.6 TIMING
text: 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 i7-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 are slower than GCN and GAT, which is as expected since GCN and GAT do not need to learn graph structures simultaneously. 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.

heading: 4 RELATED WORK
text: In the field of graph signal processing, researchers have explored various ways of learning graphs from data (Dong et al., 2016; Kalofolias, 2016; Kalofolias & Perraudin, 2017; Egilmez et al., 2017), with certain assumptions (e.g., smoothness) on the graph signals or structural constraints (e.g., connectivity 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 et al., 2017; Hamilton et al., 2017b; Li et al., 2015) have drawn increasing attention, and have many successful applications in computer vision (Norcliffe-Brown et al., 2018), natural language processing (Xu et al., 2018a;b;c) and recommender systems (Ying et al., 2018a). How to apply GNNs to applications 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 construct a graph of objects (Norcliffe-Brown et al., 2018; Choi et al., 2019; Franceschi et al., 2019; Li et al., 2018a) or words (Liu et al., 2018; 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, we 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. It will be interesting to 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 is that it optimizes the discrete probability distribution on the edges of the graph, which makes it unable to handle the inductive setting.

heading: 5 CONCLUSION
text: 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 proposed method is able to iteratively search for hidden graph structures that better help the downstream prediction task. We 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. 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. We leave how to design better metric functions as future work.

heading: B DATA STATISTICS

heading: C MODEL SETTINGS
text: In all our experiments, we apply a 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 a 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 to 16 to follow the original GCN paper. We use Adam (Kingma & Ba, 2014) as the optimizer. For the text benchmarks, we set the learning rate to 1e-3. For all other benchmarks, we set the learning rate to 0.01 and apply L2 norm regularization with weight decay set to 5e-4. Below we show the hyperparameter associated to IDGL for all benchmarks. All hyperparameters are tuned on the development set.

Review summaries:
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: