Learning Discrete Structures for Graph Neural Networks

Introduction

Relational learning is concerned with methods that cannot only leverage the attributes of data points but also their relationships. Diagnosing a patient, for example, not only depends on the patient’s vitals and demographic information but also on the same information about their relatives, the information about the hospitals they have visited, and so on. Relational learning, therefore, does not make the assumption of independence between data points but models their dependency explicitly. Graphs are a natural way to represent relational information and there is a large number of learning algorithms leveraging graph structure. Graph neural networks (GNNs) (Scarselli et al., 2009) are one such class of algorithms that are able to incorporate sparse and discrete dependency structures between data points.

While a graph structure is available in some domains, in others it has to be inferred or constructed. A possible approach is to first create a $k$-nearest neighbor ($k$NN) graph based on some measure of similarity between data points. This is a common strategy used by several learning methods such as LLE (Roweis & Saul, 2000) and Isomap (Tenenbaum et al., 2000). A major shortcoming of this approach, however, is that the efficacy of the resulting models hinges on the choice of $k$ and, more importantly, on the choice of a suitable similarity measure over the input features. In any case, the graph creation and parameter learning steps are independent and require heuristics and trial and error. Alternatively, one could simply use a kernel matrix to model the similarity of examples implicitly at the cost of introducing a dense dependency structure.

With this paper, we follow a different route with the aim of learning discrete and sparse dependencies between data points while simultaneously training the parameters of graph convolutional networks (GCN), a class of GNNs. Intuitively, GCNs learn node representations by passing and aggregating messages between neighboring nodes (Kipf & Welling, 2017; Monti et al., 2017; Gilmer et al., 2017; Hamilton et al., 2017; Duran & Niepert, 2017; Velickovic et al., 2018). We propose to learn a generative probabilistic model for graphs, samples from which are used both during training and at prediction time. Edges are modelled with random variables whose parameters are treated as hyperparameters in a bilevel learning framework (Franceschi et al., 2018). We iteratively sample the structure while minimizing an inner objective (a training error) and optimize the edge distribution parameters by minimizing an outer objective (a validation error).

To the best of our knowledge, this is the first method that simultaneously learns the graph and the parameters of a GNN for semi-supervised classification. Moreover, and this might be of independent interest, we adapt gradient-based hyperparameter optimization to work for a class of discrete hyperparameters (edges, in this work). We conduct a series of experiments and show that the proposed method is competitive with and often outperforms existing approaches. We also verify that the resulting graph generative models have meaningful edge probabilities.

Background

We first provide some background on graph theory, graph neural networks, and bilevel programming.

A graph $G$ is a pair $(V,E)$ with $V=\{v_{1},...,v_{N}\}$ the set of vertices and $E\subseteq V\times V$ the set of edges. Let $N$ and $M$ be the number of vertices and edges, respectively. Each graph can be represented by an adjacency matrix $A$ of size $N\times N$: $A_{i,j}=1$ if there is an edge from vertex $v_{i}$ to vertex $v_{j}$, and $A_{i,j}=0$ otherwise. The graph Laplacian is defined by $L=D-A$ where $D_{i,i}=\sum_{j}A_{i,j}$ and $D_{i,j}=0$ if $i\neq j$. We denote the set of all $N\times N$ adjacency matrices by $\mathcal{H}_{N}$.

2 Graph Neural Networks

by minimizing some regularized empirical loss

3 Bilevel Programming in Machine Learning

Bilevel programs arise in numerous situations such as hyperparmeter optimization, adversarial, multi-task, and meta-learning (Bennett et al., 2006; Flamary et al., 2014; Muñoz-González et al., 2017; Franceschi et al., 2018).

Solving Problem (3) is challenging since the solution sets of the inner problem are usually not available in closed-form. A standard approach involves replacing the minimization of $L$ with the repeated application of an iterative optimization dynamics $\Phi$ such as (stochastic) gradient descent (Domke, 2012; Maclaurin et al., 2015; Franceschi et al., 2017). Let $w_{\theta,T}$ denote the inner variables after $T$ iterations of the dynamics $\Phi$, that is, $w_{\theta,T}=\Phi(w_{\theta,T-1},\theta)=\Phi(\Phi(w_{\theta,T-2},\theta),\theta)$, and so on. Now, if $\theta$ and $w$ are real-valued and the objectives and dynamics smooth, we can compute the gradient of the function $F(w_{\theta,T},\theta)$ w.r.t. $\theta$, denoted throughout as the hypergradient $\nabla_{\theta}F(w_{\theta,T},\theta)$, as

where the symbol $\partial$ denotes the partial derivative (the Jacobian) and $\nabla$ either the gradient (for scalar functions) or the total derivative. The first term can be computed efficiently in time $O(T(d+m))$ with reverse-mode algorithmic differentiation (Griewank & Walther, 2008) by unrolling the optimization dynamics, repeatedly substituting $w_{\Phi,t}=\Phi(w_{\theta,t-1},\theta)$ and applying the chain rule. This technique allows to optimize a number of hyperparameters several orders of magnitude greater than classic methods for hyperparameter optimization (Feurer & Hutter, 2018).

Learning Discrete Graph Structures

With this paper we address the challenging scenarios where a graph structure is either completely missing, incomplete, or noisy. To this end, we learn a discrete and sparse dependency structure between data points while simultaneously training the parameters of a GCN. We frame this as a bilevel programming problem whose outer variables are the parameters of a generative probabilistic model for graphs. The proposed approach, therefore, optimizes both the parameters of a GCN and the parameters of a graph generator so as to minimize the classification error on a given dataset. We developed a practical algorithm based on truncated reverse-mode algorithmic differentiation (Williams & Peng, 1990) and hypergradient estimation to approximately solve the bilevel problem. A schematic illustration of the resulting method is presented in Figure 1.

Let us suppose that information about the true adjacency matrix $A$ is missing or incomplete. Since, ultimately, we are interested in finding a model that minimizes the generalization error, we assume the existence of a second subset of instances with known target, $V_{\mathtt{Val}}$ (the validation set), from which we can estimate the generalization error. Hence, we propose to find $A\in\mathcal{H}_{N}$ that minimizes the function

where $w_{A}$ is the minimizer, assumed unique, of $L$ (see Eq. (1) and Sec. 2.3) for a fixed adjacency matrix $A$. We can then consider Equations (1) and (5) as the inner and outer objective of a mixed-integer bilevel programming problem where the outer objective aims to find an optimal discrete graph structure and the inner objective the optimal parameters of a GCN given a graph.

By taking the expectation, both the inner and the outer objectives become continuous (and possibly smooth) functions of the Bernoulli parameters. The bilevel problem given by Eqs. (6)-(7) is still challenging to solve efficiently. This is because the solution of the inner problem is not available in closed form for GCNs (the objective is non-convex); and the expectations are intractable to compute exactlyThis is different than e.g. (model free) reinforcement learning, where the objective function is usually unknown, depending in an unknown way from the action and the environment.. An efficient algorithm, therefore, will only be able to find approximate stochastic solutions, that is, $\theta_{i,j}\in(0,1)$.

Before describing a method to solve the optimization problem given by Eqs. (6)-(7) approximately with hypergradient descent, we first turn to the question of obtaining a final GCN model that we can use for prediction. For a given distribution $P_{\theta}$ over graphs with $N$ nodes and with parameters $\theta$, the expected output of a GCN is

Unfortunately, computing this expectation is intractable even for small graphs; we can, however, compute an empirical estimate of the output as

2 Structure Learning via Hypergradient Descent

The bilevel programming formalism is a natural fit for the problem of learning both a graph generative model and the parameters of a GNN for a specific downstream task. Here, the outer variables $\theta$ are the parameters of the graph generative model and the inner variables $w$ are the parameters of the GCN.

We now discuss a practical algorithm to approach the bilevel problem defined by Eqs. (6) and (7). Regarding the inner problem, we note that the expectation

is composed of a sum of $2^{N^{2}}$ terms, which is intractable even for relatively small graphs. We can, however, choose a tractable approximate learning dynamics $\Phi$ such as stochastic gradient descent (SGD),

Now, in our setting, we simply use the identity mapping $A=\mathtt{sp}(\theta,\varepsilon)=\theta$ and approximate

noting that $w_{\theta,T}$ depends on the distribution of $A$ through the optimization dynamics (11). We then take the single sample Monte Carlo estimator of (15) to update the parameters $\theta$, projecting on the unit hypercube. We refer to this last quantity as the STE hypergradient, or simply hypergradient. We provide additional details about the computation of the term $\nabla_{A}w_{\theta,T}$ and the STE in the appendix.

Computing the STE hypergradient by fully unrolling the dynamics may be too expensive both in time and memoryMoreover, since we rely on biased estimations of the gradients, we do not expect to gain too much from a full computation.. We propose to truncate the computation and estimate the hypergradient every $\tau$ iterations, where $\tau$ is a parameter of the algorithm. This is essentially an adaptation of truncated back-propagation through time (Werbos, 1990; Williams & Peng, 1990) and can be seen as a short-horizon optimization procedure with warm restart on $w$. A sketch of the method is presented in Algorithm 1, while a more complete version that includes details on the STE hypergradient computation can be found in Appendix A. Inputs and operations in squared brackets are optional.

The algorithm contains stopping conditions at the outer and at the inner level. While it is natural to implement the latter with a decrease condition on the inner objectiveWe continue optimizing $L$ until $L(w_{t-1},A)(1+\varepsilon)\geq L(w_{\theta,t},A)$, for $\varepsilon>0$ ($\varepsilon=10^{-3}$ in the experiments). Since $L$ is non-convex, we also use a patience window of $p$ steps., we find it useful to implement the first with a simple early stopping criterion. A fraction of the examples in the validation set is held-out to compute, in each outer iteration, the accuracy using the predictions of the empirically expected model (9). The optimization procedure terminates if there is no improvement for some consecutive outer loops. This helps avoiding overfitting the outer objective (6), which may be a concern in this context given the quantity of (hyper)parameters being optimized and the relative small size of the validation sets.

The STE hypergradients estimated with Algorithm 1 at each outer iteration are biased. The bias stems from both the straight-trough estimator and from the truncation procedure introduced in lines 11-13 (Tallec & Ollivier, 2017). Nevertheless, we find empirically that the algorithm is able to make reasonable progress, finding configurations in the distribution space that are beneficial for the tasks at hand.

Experiments

We conducted a series of experiments with three main objectives. First, we evaluated LDS on node classification problems where a graph structure is available but where a certain fraction of edges is missing. Here, we compared LDS with graph-based learning algorithms including vanilla GCNs. Second, we wanted to validate our hypothesis that LDS can achieve competitive results on semi-supervised classification problems for which a graph is not available. To this end, we compared LDS with a number of existing semi-supervised classification approaches. We also compared LDS with algorithms that first create $k$-NN affinity graphs on the data set. Third, we analyzed the learned graph generative model to understand to what extent LDS is able to learn meaningful edge probability distributions even when a large fraction of edges is missing.

Cora and Citeseer are two benchmark datasets that are commonly used to evaluate relational learners in general and GCNs in particular (Sen et al., 2008). The input features are bag of words and the task is node classification. We use the same dataset split and experimental setup of previous work (Yang et al., 2016; Kipf & Welling, 2017). To evaluate the robustness of LDS on incomplete graphs, we construct graphs with missing edges by randomly sampling $25\%$, $50\%$, and $75\%$ of the edges. In addition to Cora and Citeseer where we removed all edges, we evaluate LDS on benchmark datasets that are available in scikit-learn (Pedregosa et al., 2011) such as Wine, Breast Cancer (Cancer), Digits, and 20 Newsgroup (20news). We take $10$ classes from 20 Newsgroup and use words (TFIDF) with a frequency of more than $5\%$ as features. We also use FMA, a dataset where $140$ audio features are extracted from 7,994 music tracks and where the problem is genre classification (Defferrard et al., 2017). The statistics of the datasets are reported in the appendix.

2 Setup and Baselines

For the experiments on graphs with missing edges, we compare LDS to vanilla GCNs. In addition, we also conceived a method (GCN-RND) where we add randomly sampled edges at each optimization step of a vanilla GCN. With this method we intend to show that simply adding random edges to the standard training procedure of a GCN model (perhaps acting as a regularization technique) is not enough to improve the generalization.

When a graph is completely missing, GCNs boil down to feed-forward neural networks. Therefore, we evaluate different strategies to induce a graph on both labeled and unlabeled samples by creating (1) a sparse Erdős-Rényi random graph (Erdos & Rényi, 1960) (Sparse-GCN); (2) a dense graph with equal edge probabilities (Dense-GCN); (3) a dense RBF kernel on the input features (RBF-GCN); and (4) a sparse $k$-nearest neighbor graph on the input features ($k$NN-GCN). For LDS we initialize the edge probabilities using the $k$-NN graph ($k$NN-LDS). We further include a dense version of LDS where we learn a dense similarity matrix ($k$NN-LDS (dense)). In this setting, we compare LDS to popular semi-supervised learning methods such as label propagation (LP) (Zhu et al., 2003), manifold regularization (ManiReg) (Belkin et al., 2006), and semi-supervised embedding (SemiEmb) (Weston et al., 2012). ManiReg and SemiEmb are given a $k$-NN graph as input for the Laplacian regularization. We also compare LDS to baselines that do not leverage a graph-structure such as logistic regression (LogReg), support vector machines (Linear and RBF SVM), random forests (RF), and feed-forward neural networks (FFNN). For comparison methods that need a $k$NN graph, $k\in\{2,3,\dots,20\}$ and the metric (Euclidean or Cosine) are tuned using validation accuracy. For $k$NN-LDS, $k$ is tuned from $10$ or $20$.

where $y_{v}$ is the one-hot encoded target vector for the $v$-th instance, $\circ$ denotes the element-wise multiplication and $\rho$ is a non-negative coefficient. As additional regularization technique we apply dropout (Srivastava et al., 2014) with $\beta=0.5$ as in previous work. We use Adam (Kingma & Ba, 2015) for optimizing $L$, tuning the learning rate $\gamma$ from {$0.005$, $0.01$, $0.02$}. The same number of hidden neurons and the same activation is used for SemiEmb and FFNN.

For LDS, we set the initial edge parameters $\theta_{i,j}$ to except for the known edges (or those found by $k$NN) which we set to $1$. We then let all the parameters (including those initially set to $1$) to be optimized by the algorithm. We further split the validation set evenly to form the validation (A) and early stopping (B) sets. As outer objective we use the un-regularized cross-entropy loss on (A) and optimize it with stochastic gradient descent. with exponentially decreasing learning rate. Initial experiments showed that accelerated optimization methods such as Adam or SGD with momentum underperform in this setting. We tune the step size $\eta$ of the outer optimization loop and the number of updates $\tau$ used to compute the truncated hypergradient. Finally, we draw $S=16$ samples to compute the output predictions (see Eq. (9)). For LDS and GCN, we apply early stopping with a window size of $20$ steps.

LDS was implemented in TensorFlow (Abadi et al., 2015) and is available at https://github.com/lucfra/LDS. The implementations of the supervised baselines and LP are those from the scikit-learn python package (Pedregosa et al., 2011). GCN, ManiReg, and SemiEmb are implemented in Tensorflow. The hyperparameters for all the methods are selected through the validation accuracy.

3 Results

The results on the incomplete graphs are shown in Figure 2 for Cora (left) and Citeseer (center). For each percentage of retained edges the accuracy on validation (used for early stopping) and test sets are plotted. LDS achieves competitive results in all scenarios and accuracy gains of up to $7$ percentage points. Notably, LDS improves the generalization accuracy of GCN models also when the given graph is that of the respective dataset (100% of edges retained), by learning additional helpful edges. The accuracy of 84.1% and 75.0% for Cora and Citeseer, respectively, exceed all previous state-of-the-art results. Conversely, adding random edges does not help decreasing the generalization error. GCN and GCN-RND perform similarly which indicates that adding random edges to the graph is not helpful.

Figure 2 (right) depicts the impact of the number of iterations $\tau$ to compute the STE hypergradients. Taking multiple steps strongly outperforms alternating optimizationFor $\tau=0$, one step of optimization of $L$ w.r.t. $w$, fixing $\theta$ is interleaved with one step of minimization of $F$ w.r.t. $\theta$, fixing $w$. Even if computationally lighter, this approach disregards the nested structure of (6)-(7), not computing the first term of Eq. (4). (i.e. $\tau=0$) in all settings. Increasing $\tau$ further to the value of $20$, however, does not yield significant benefits, while increasing the computational cost.

In Table 2 we computed the expected number of edges in a sampled graph for Cora and Citeseer, to analyze the properties of the graphs sampled from the learned graph generator. The expected number of edges for LDS is higher than the original number which is to be expected since LDS has better accuracy results than the vanilla GCN in Figure 2. Nevertheless, the learned graphs are still very sparse (e.g. for Cora, on average, less than $0.2\%$ edges are present). This facilitates efficient learning of the GCN in the inner learning loop of LDS.

Table 1 lists the results for semi-supervised classification problems. The supervised learning baselines work well on some datasets such as Wine and Cancer but fail to provide competitive results on others such as Digits, Citeseer, Cora, and 20News. The semi-supervised learning baselines LP, ManiReg and SemiEmb can only improve the supervised learning baselines on $1$, $3$ and $4$ datasets, respectively. The results for the GCN with different input graphs show that $k$NN-GCN works well and provides competitive results compared to the supervised baselines on all datasets. $k$NN-LDS significantly outperforms $k$NN-GCN on $4$ out of the $7$ datasets. In addition, $k$NN-LDS is among the most competitive methods on all datasets and yields the highest gains on datasets that have an underlying graph. Moreover, $k$NN-LDS performs slightly better than its dense counterpart where we learn a dense adjacency matrix. The added benefit of the sparse graph representation lies in the potential to scale to larger datasets.

In Figure 3, we show the evolution of mean edge probabilities during optimization on three types of nodes (train, validation, test) on the Cora dataset. LDS is able to learn a graph generative model that is, on average, attributing $10$ to $100$ times more probability to edges between samples sharing the same class label. LDS often attributes a higher probability to edges that are present in the true held-out adjacency matrix (green lines in the plots). In Figure 4 we report the normalized histograms of the optimized edges probabilities for the same nodes of Figure 3, sorted into six bins in $\log_{10}$-scale. Edges are divided in two groups: edges between nodes of the same class (blue) and between nodes of unknown or different classes (orange). LDS is able to learn highly non-uniform edge probabilities that reflect the class membership of the nodes.

Figure 5 shows similar qualitative results as Figure 4, this time for three Citeseer test nodes, missclassified by $k$NN-GCN and correctly classified by $k$NN-LDS. Again, the learned edge probabilities linking to nodes of the same classes is significantly different to those from different classes; but in this case the densities are more skewed toward the first bin. On the datasets we considered, what seems to matter is to capture a useful distribution (i.e. higher probability for links between same class) rather than pick exact links; of course for other datasets this may vary.

Related work

Semi-supervised learning. Early works on graph-based semi-supervised learning use graph Laplacian regularization and include label propagation (LP) (Zhu et al., 2003), manifold regularization (ManiReg) (Belkin et al., 2006), and semi-supervised embedding (SemiEmb) (Weston et al., 2012). These methods assume a given graph whose edges represent some similarity between nodes. Later, (Yang et al., 2016) proposed a method that uses graphs not for regularization but rather for embedding learning by jointly classification and graph context prediction. Kipf & Welling (2017) presented the first GCN for semi-supervised learning. There are now numerous GCN variants all of which assume a given graph structure. Contrary to all existing graph-based semi-supervised learning approaches, LDS is able to work even when the graph is incomplete or missing.

Graph synthesis and generation. LDS learns a probabilistic generative model for graphs. The earliest probabilistic generative model for graphs was the Erdős-Rényi random graph model (Erdos & Rényi, 1960), where edge probabilities are modelled as identically distributed and mutually independent Bernoullis. Several network models have been proposed to model well particular graph properties such as degree distribution (Leskovec et al., 2005) or network diameter (Watts & Strogatz, 1998). Leskovec et al. (2010) proposed a generative model based on the Kronecker product that takes a real graph as input and generates graphs that have similar properties. Recently, deep learning based approaches have been proposed for graph generation (You et al., 2018; Li et al., 2018; Grover et al., 2018; De Cao & Kipf, 2018). The goal of these methods, however, is to learn a sophisticated generative model that reflects the properties of the training graphs. LDS, on the other hand, learns graph generative models as a means to perform well on classification problems and its input is not a collection of graphs. More recent work proposed an unsupervised model that learns to infer interactions between entities while simultaneously learning the dynamics of physical systems such as spring systems (Kipf et al., 2018). Contrary to LDS, the method is specific to dynamical interacting systems, is unsupervised, and uses a variational encoder-decoder. Finally, we note that Johnson (2017) proposed a fully differentiable neural model able to process and produce graph structures at both input, representation and output levels; training the model requires, however, supervision in terms of ground truth graphs.

Link prediction. Link prediction is a decades-old problem (Liben-Nowell & Kleinberg, 2007). Several survey papers cover the large body of work ranging from link prediction in social networks to knowledge base completion (Lü & Zhou, 2011; Nickel et al., 2016). While a majority of the methods are based on some similarity measure between node pairs, there has been a number of neural network based methods (Zhang & Chen, 2017, 2018). The problem we study in this paper is related to link prediction as we also want to learn or extend a graph. However, existing link prediction methods do not simultaneously learn a GNN node classifier. Statistical relational learning (SRL) (Getoor & Taskar, 2007) models often perform both link prediction and node classification through the existence of binary and unary predicates. However, SRL models are inherently intractable and the structure and parameter learning steps are independent.

Gradient estimation for discrete random variables. Due to the intractable nature of the two bilevel objectives, LDS needs to estimate the hypergradients through a stochastic computational graph (Schulman et al., 2015). Using the score function estimator, also known as REINFORCE (Williams, 1992), would treat the outer objective as a black-box function and would not exploit $F$ being differentiable w.r.t. the sampled adjacency matrices and inner optimization dynamics. Conversely, the path-wise estimator is not readily applicable, since the random variables are discrete. LDS borrows from a solution proposed before (Bengio et al., 2013), at the cost of having biased estimates. Recently, Jang et al. (2017); Maddison et al. (2017) presented an approach based on continuous relaxations to reduce variance, which Tucker et al. (2017) combined with REINFORCE to obtain an unbiased estimator. Grathwohl et al. (2018) further introduced surrogate models to construct control variates for black-box functions. Unfortunately, these latter methods require to compute the function in the interior of the hypercube, possibly in multiple points (Tucker et al., 2017). This would introduce additional computational overheadRecall that $F$ can be computed only after (approximately) solving the inner optimization problem..

Conclusion

We propose LDS, a framework that simultaneously learns the graph structure and the parameters of a GNN. While we have used a specific GCN variant (Kipf & Welling, 2017) in the experiments, the method is more generally applicable to other GNNs. The strengths of LDS are its high accuracy gains on typical semi-supervised classification datasets at a reasonable computational cost. Moreover, due to the graph generative model LDS learns, the edge parameters have a probabilistic interpretation.

The method has its limitations. While relatively efficient, it cannot currently scale to large datasets: this would require an implementation that works with mini-batches of nodes. We evaluated LDS only in the transductive setting, when all data points (nodes) are available during training. Adding additional nodes after training (the inductive setting) would currently require retraining the entire model from scratch. When sampling graphs, we do not currently enforce the graphs to be connected. This is something we anticipate to improve the results, but this would require a more sophisticated sampling strategy. All of these shortcomings motivate future work. In addition, we hope that suitable variants of LDS algorithm will also be applied to other problems such as neural architecture search or to tune other discrete hyperparameters.

References

Appendix A Extended algorithm

In this section we provide an extended version of the Algorithm 1 that includes the explicit computation of the STE hypergradient by truncated reverse mode algorithmic differentiation. Recall that the inner objective is replaced by an iterative dynamics $\Phi$ such as stochastic gradient descent. Hence, starting from an initial point $w_{0}$, the iterates are computed as

Let $D_{t}$ and $E_{t}$ denote the Jacobians of the dynamics:

and recall that, because of our reparameterization choice (for the backward pass), we have $\nabla_{\theta}A=\nabla_{\theta}\theta=\mathbf{I}.$ We report the pseudocode in Algorithm 2, where the letter $p$ is used to indicate the adjoint variables (Lagrangian multipliers). Note that for $\tau=0$ the algorithm does not enter in the loop at line 15. Finally, note also that at line 16, we re-sample the adjacency matrices instead of reusing those computed in the forward pass (lines 8-10).

Algorithm 2 was implemented in TensorFlow as an extension of the software package Far-HO, freely available at https://github.com/lucfra/FAR-HO.

Appendix B On the Straight-through Estimator

whereas the corresponding straight-through estimator, which is a random variable, is given by

resulting in $\hat{g}$ to be biased for $\theta\neq\frac{1}{2}$.

Appendix C Additional Tables

Table 3 contains the list of datasets we used in the experimental section, with relevant statistics.

We report in Table 4 the numerical results relative to the experiments with various percentages of edges retained on Citeseer and Cora datasets. We refer to Section 4 for a complete description.

Appendix D Visualization of Embeddings

We further visualize the embeddings learned by GCN and LDS using T-SNE (Maaten & Hinton, 2008). Figure 6 depicts the T-SNE visualizations of the embeddings learned on Citeseer with Dense-GCN (left), $k$NN-GCN (center), and $k$NN-LDS (right). As can be seen, the embeddings learned by $k$NN-LDS provides the best separation among different classes.