Title: ITERATIVE DEEP GRAPH LEARNING FOR GRAPH NEU-RAL NETWORKS

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.

1. INTRODUCTION:

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 N 2 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. 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 R dˆ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 R nˆn , underlying the set of objects, which will be consumed by a GNN-based model for a downstream prediction task.

2. AN ITERATIVE DEEP GRAPH LEARNING FRAMEWORK:

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 .

2.1. GRAPH LEARNING AS SIMILARITY METRIC LEARNING:

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.

2.1.1. SIMILARITY METRIC LEARNING:

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,

s ij " cospw d v i , w d v j q (1)

where d denotes the Hadamard product, and w is a learnable weight vector which has the same dimension as the input vectors v i and v j , 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) ; Veličković 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:

s k ij " cospw k d v i , w k d v j q, s ij " 1 m m ÿ k"1 s k ij (2)

Intuitively, s k ij computes the cosine similarity between the two input vectors v i and v j , 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 s ij 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 ε.

A ij " " s ij s ij ą ε 0 otherwise (3) 2.2 GRAPH REGULARIZATION

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 x 1 , . . . , x n P R d is usually measured by the Dirichlet energy (Belkin & Niyogi, 2002) ,

ΩpA, Xq " 1 2 ÿ i,j A ij ||x i ´xj || 2 " trpX T LXq (4)

where trp¨q denotes the trace of a matrix, L " D ´A is the graph Laplacian, and D " ř j A ij 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,

f pAq " ´β1 T logpA1q `γ||A|| 2 F (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.

L G " αΩpA, Xq `f pAq (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 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 " L pred `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 " ReLUp r AXW 1 q (7)

EQUATION

where r A 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 r A. 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 (Veličković 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,

r A " λL 0 `p1 ´λq A ij ř j A ij (10)

where L 0 is the normalized adjacency matrix of the initial graph, defined as, L 0 "

D ´1{2 0 A 0 D ´1{2 0

, and D 0 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. 

L p0q Ð L p0q pred `Lp0q G // Compute joint loss t Ð 0 while pt "" 0 or ||A ptq ´Apt´1q || 2 F ą δ||A p0q || 2 F q and t ă T do t Ð t `1

A ptq , r A ptq Ð tZ pt´1q , A0u using Eqs. ( 2), ( 3) and ( 10) // Refine the adj. matrix s A ptq Ð t r A ptq , r A p0q u using Eq. ( 11)

Z ptq Ð t s A ptq , Xu using Eq. ( 7) // Refine node embeddings p y Ð t s A ptq , Z ptq u using Eq. ( 8) // Compute task output L ptq pred Ð tp y, yu using Eq. ( 9)

L ptq G Ð tA ptq , Xu using Eqs. ( 4)-( 6)

L ptq Ð L ptq pred `Lptq G end L Ð L p0q `řt i"1 L piq {t if Training then

Back-propagate L to update model weights Θ end 2.3.2 ITERATIVE METHOD FOR GRAPH LEARNING Some previous works (Veličković 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,

EQUATION

where r A ptq and r A p0q 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 r

A ptq with the updated node embeddings Z pt´1q , and in the meanwhile, refines the node embeddings Z ptq with the updated adjacency matrix r A ptq . 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).

2.4. FORMAL ANALYSIS:



2.4.1. CONVERGENCE OF THE ITERATIVE LEARNING PROCEDURE:

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 r A. As we can see, at t-th iteration, A ptq is computed based on Z pt´1q (Line 10), and Z ptq is computed based on r A ptq (Line 12) which is computed based on A ptq (Eq. ( 10)). We further denote the difference between the adjacency matrices at the t-th iteration and the previous iteration by δ Z measures the difference between Z p0q and X, which is usually larger than the difference between Z p1q and Z p0q , namely δ p1q Z . We will empirically examine the convergence property of the iterative learning procedure in the experimental section. 

2.4.2. MODEL COMPLEXITY:

The cost of learning an adjacency matrix is Opn 2 hq for n nodes and data in R h , while computing node embeddings costs Opn 2 d `ndhq, computing task output costs Opn 2 hq, and computing the total loss costs Opn 2 dq. We set the maximal number of iterations to T , hence the overall complexity is OpT npnh `nd `hdqq. If we assume that d « h and n " d, the overall complexity is OpT dn 2 q.

3. EXPERIMENTS:

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.

3.1. DATASETS:

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.

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 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 (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 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.

3.3. EXPERIMENTAL RESULTS:

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 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 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. 

3.4. ABLATION STUDY:

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%. 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 matrices at consecutive iterations as δ ptq A " ||A ptq ´Apt´1q || 2 F {||A ptq || 2 F 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. 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. 

4. RELATED WORK:

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.

5. 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 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.

:



Figures and Tables:

Figure 1: Overview of the proposed model. Dashed lines in the leftmost data points indicate the initial graph topology A 0 either from the ground-truth graph if it exists or otherwise from the graph constructed using the kNN strategy. Best viewed in color.

ptqA . Similarly, we denote the difference between the node embedding matrices at the t-th iteration and the previous iteration by δ 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 δ p2q A ă δ 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 δ p1q Z ă δ p0q Z makes sense in practice, we need to recall the fact that δp0q

Figure 2: Information flow of the proposed iterative learning procedure.

Figure 3: Test accuracy (˘standard deviation) in percentage for the edge deletion scenario.

Figure 4: Test accuracy (˘standard deviation) in percentage for the edge addition scenario.

Figure 5: Evolution of the learned adjacency matrix and test accuracy (in %) through iterations in the iterative learning procedure.

Figure6: Performance comparison (i.e., test accuracy in %) of two 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).

Algorithm 1: IDGL: Iterative Deep Graph Learning Framework

Table content: <table><tr><td colspan="2">Input: X, yr, A0s</td><td/></tr><tr><td colspan="3">Parameters : m, ε, α, β, γ, λ, δ, T , ηr, ks</td></tr><tr><td colspan="2">Output: Θ, r A ptq , p y</td><td/></tr><tr><td colspan="2">rA0 Ð kNNpX, kqs</td><td colspan="2">// Init. A0 to kNN graph if A0 is unavailable</td></tr><tr><td colspan="3">A p0q , r A p0q Ð tX, A0u using Eqs. (2), (3) and (10)</td><td>// Learn the adj. matrix</td></tr><tr><td colspan="2">Z p0q Ð t r A p0q , Xu using Eq. (7)</td><td/><td>// Compute node embeddings</td></tr><tr><td>L</td><td colspan="2">p0q pred Ð t r A p0q , Z p0q , yu using Eqs. (8) and (9)</td><td>// Compute prediction loss</td></tr><tr><td>L</td><td>p0q G Ð tA p0q , Xu using Eqs. (4)-(6)</td><td/><td>// Compute graph regularization loss</td></tr></table>

Test accuracy (˘standard deviation) in percentage on various classification datasets in the transductive setting. The star symbol means that we run the experiments and report the results.

Table content: <table><tr><td>Methods</td><td>Cora</td><td>Citeseer</td><td>Wine</td><td>Cancer</td><td>Digits</td></tr><tr><td>LogReg</td><td colspan="5">60.8 (0.0) 62.2 (0.0) 92.1 (1.3) 93.3 (0.5) 85.5 (1.5)</td></tr><tr><td>Linear SVM</td><td colspan="5">58.9 (0.0) 58.3 (0.0) 93.9 (1.6) 90.6 (4.5) 87.1 (1.8)</td></tr><tr><td>RBF SVM</td><td colspan="5">59.7 (0.0) 60.2 (0.0) 94.1 (2.9) 91.7 (3.1) 86.9 (3.2)</td></tr><tr><td>RF</td><td colspan="5">58.7 (0.4) 60.7 (0.7) 93.7 (1.6) 92.1 (1.7) 83.1 (2.6)</td></tr><tr><td>FFNN</td><td colspan="5">56.1 (1.6) 56.7 (1.7) 89.7 (1.9) 92.9 (1.2) 36.3 (10.3)</td></tr><tr><td>LP</td><td colspan="5">37.8 (0.2) 23.2 (6.7) 89.8 (3.7) 76.6 (0.5) 91.9 (3.1)</td></tr><tr><td>ManiReg</td><td colspan="5">62.3 (0.9) 67.7 (1.6) 90.5 (0.1) 81.8 (0.1) 83.9 (0.1)</td></tr><tr><td>SemiEmb</td><td colspan="5">63.1 (0.1) 68.1 (0.1) 91.9 (0.1) 89.7 (0.1) 90.9 (0.1)</td></tr><tr><td>LDS</td><td colspan="5">84.1 (0.4) 75.0 (0.4) 97.3 (0.4) 94.4 (1.9) 92.5 (0.7)</td></tr><tr><td>GCN</td><td colspan="2">81.0 (0.2) 70.9 (0.3)</td><td>-</td><td>-</td><td>-</td></tr><tr><td>GAT</td><td colspan="2">82.5 (0.4) 70.9 (0.4)</td><td>-</td><td>-</td><td>-</td></tr><tr><td>kNN-GCN</td><td>-</td><td>-</td><td colspan="3">95.9 (0.9) 94.7 (1.2) 89.5 (1.3)</td></tr><tr><td>LDS*</td><td colspan="5">83.9 (0.6) 74.8 (0.3) 96.9 (1.4) 93.4 (2.4) 90.8 (2.5)</td></tr><tr><td>IDGL</td><td colspan="5">84.5 (0.3) 74.1 (0.2) 97.8 (0.6) 95.1 (1.0) 93.1 (0.5)</td></tr></table>

Test scores (˘standard deviation) in percentage on classification (accuracy) and regression (R 2 ) datasets in the inductive setting.

Table content: <table><tr><td>Methods</td><td>20News</td><td>MRD</td></tr><tr><td>BiLSTM</td><td colspan="2">80.0 (0.4) 53.1 (1.4)</td></tr><tr><td>kNN-GCN</td><td colspan="2">81.3 (0.6) 60.1 (1.5)</td></tr><tr><td>IDGL</td><td colspan="2">83.6 (0.4) 63.7 (1.8)</td></tr></table>

Ablation study on various classification datasets.

Table content: <table><tr><td>Methods</td><td>Cora</td><td>Citeseer</td><td>Wine</td><td>Cancer</td><td>Digits</td><td>20News</td></tr><tr><td>IDGL</td><td colspan="6">84.5 (0.3) 74.1 (0.2) 97.8 (0.6) 95.1 (1.0) 93.1 (0.5) 83.6 (0.4)</td></tr><tr><td>w/o graph reg.</td><td/><td/><td/><td/><td/><td/></tr></table>

Mean and standard deviation of training time on various benchmarks (in seconds).

Table content: <table><tr><td>Benchmarks</td><td>Cora</td><td>Citeseer</td><td>Wine</td><td colspan="2">Cancer Digits</td></tr><tr><td>GCN</td><td>3 (1)</td><td>5 (1)</td><td>-</td><td>-</td><td>-</td></tr><tr><td>GAT</td><td>26 (5)</td><td>28 (5)</td><td>-</td><td>-</td><td>-</td></tr><tr><td>LDS</td><td colspan="4">390 (82) 585 (181) 33 (15) 25 (6)</td><td>72 (35)</td></tr><tr><td>IDGL</td><td colspan="3">237 (21) 563 (100) 20 (7)</td><td colspan="2">21 (11) 65 (12)</td></tr><tr><td>IDGL w/o IL</td><td>49 (8)</td><td>61 (15)</td><td>3 (2)</td><td>3 (1)</td><td>2 (1)</td></tr></table>

Peer review (iclr2020):
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: 1. 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. 2. 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. 3. 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.