GRASPEL: GRAPH SPECTRAL LEARNING AT SCALE
Authors: Yongyu Wang
Zhiqiang Zhao
Zhuo Feng
Venue:  (2020)
Keywords: Spectral graph theory
graph learning
data clustering
t-SNE visualization

Abstract: Learning meaningful graphs from data plays important roles in many data mining and machine learning tasks, such as data representation and analysis, dimension reduction, data clustering, and visualization, etc. In this work, we present a  scalable spectral approach to graph learning from data. By limiting the precision matrix to be a graph Laplacian, our approach aims to estimate ultra-sparse weighted graphs and has a clear connection with the prior graphical Lasso method. By interleaving nearly-linear time spectral graph sparsification,  coarsening and embedding procedures, ultra-sparse yet spectrally-stable graphs can be iteratively constructed in a highly-scalable manner. Compared with prior graph learning approaches that do not scale to large problems, our approach is highly-scalable for constructing graphs that can immediately lead to substantially improved computing efficiency and solution quality for a variety of data mining and machine learning applications, such as spectral clustering (SC), and t-Distributed Stochastic Neighbor Embedding (t-SNE).  

Under review as a conference paper at ICLR 2020
GRASPEL: GRAPH SPECTRAL LEARNING AT SCALE
Anonymous authors
Paper under couble-blind review
ABSTRACT
Learning meaningful graphs from data plays important roles in many data mining and machine learning tasks, such data representation and analysis, dimension reduction, data clustering, and visualization, etc. In this work. for the first time we present a highly-scalable spectral approach (GRASPEL) for learning large graphs from data. By limiting the precision matrix to be a graph Laplacian, our approach aims to estimate ultra-sparse (tree-like) weighted undirected graphs and shows a clear connection with the prior graphical Lasso method. By interleaving the latest perforreformeccc nearly-linear time spectral methods for graph sparsification, coarsening and embedding, ultra-sparse yet spectrally-robut graphs can be learned by identifying and including the most spectrally-crine -citticll edges into the graph. Compared with prior state-of of-the-art graph learning approaches, GRASPEL is more scalable and allows substantially improving computing efficiency and solution quality of a variety of data mining and machine learning applications. such as spectral clustering (SC), and t-Distributed Stochastic Neighbor Embedding (t-SNE). For example, when comparing with graphs constructed using existing methods, GRASPEL achieved the best spectral clustering efficiency and accuracy.
INTRODUCTION
Graph construction is playing increasingly important roles in many machine learning and data mining applications. For example, key step of many existing machine learning methods requires converting potentially high-ddmensional data sets into graph representations: is common practice to represent each hiigh-dimensional) data point as a node, and assign each edge a weight to encode the similarity between the two nodes (data points). The constructed graphs can be efficiently leveraged to represent the underlying structure of data set or the relationship between data points (Jebara et al. [0099] Maier et al.. 2009 Liu et al.) 2018). However, how learn meaningful graphs from large data set at scale still remains a challenging problem.
In the past decades, considerable effort has been devoted to the development of graph construction methods. For example, constructing k-nearest-neighhor (kNN) graphs requires each node to be connected with its top-k nearest neighbors, while in construction of the e-neighborhood graphs all the neighbors within the range of distance will be connected: improve the capability of kNN graph in handling multi-scale data, (Zelnik-Manor & Perona 2005) introduced a self-tuning technique to adjust the local scaling parameter for similarity measurement; to find meaningful similarity measures between nodes, (Bach & Jordan (006) propose to learn the similarities from feature vectors in a supervised setting; (Zhu et al. 2014)) adopted an cotrmattion-theorede
definition of data similarity to capture subtle simularity information; (Jebara & Shchogolev (006) proposed to remove spurious edges from kNN graph via b-matching; (Pavan Pelllo 2007) introduced method for removing noisy edges by selecting the maximum cliques; (Premachandran & Kakarala, 2013) proposed to leverage collected consensus information form various neighborhoods to improve the robustness of the kNN graph; (Nie et al. 2014) proposed to learn the adjacency graph by adaptively assigning neighbors. However, the atorementioned nearest-neighhor (NN) based graph construction methods can only capture local manifold information and may not be able truthfully reveal the global structure of a given data set (Nie et al. 2016 Liu et al. 2018 Guo 2015). which can result in over complicated (with too many edges) or sometimes misleading graph representations. For example, choosing different numbers of nearest neighbors for constructing KNN graphs may lead to drastically different classification performance in spectral clustering tasks (Chen et al. 2018).
Several recent graph learning methods leverage emerging graph signal processing (GSP) techniques for estimating sparse graph Laplacians, which show very promising results (Dong et al. 2016 Egilmez et al. [ Dong et al. 2019 Kalofolias & Perraudin 2019). For example, (Egilmez et al. 2017) addresses the graph learning problem by restricting the precısion matrix to be graph Laplacıan and maximizing posterior estimation of Gaussian Markov Random Field (GMRF), while an 7.1- regularization term is used to promote graph sparsity; (Rabbai 2017) provides an error analysis for

---

Under review as a conference paper at ICLR 2020
leverages approximate nearest-neighbor (ANN) graphs reduce the number of variables for optumization. However, even the state-of-the-art Laplacian estimation methods for graph learning do not scale well for large data set due to their extremely high algorithm complexity. For example, solving the optimization problem
inferring sparse graphs from smooth signals; (Kalofolias & Perraudin 2019)
for Laplacian estimation in (Dong et al. 2016 Kalofolias 2016; Egilmez et al., 2017 Dong et al. 2019) requires O time complexity per iteration for N data entities and nontrivial parameters tuning for controlling graph sparsity which limits their applications to only very small data sets (e. g. with up to a few thousands of data points). The latest graph learning approach (Kalofolias & Perraudin 2019) takes advantages of AÑN graphs but can still run rather slowly for large data sets.
This work for the first time introduces a spectral method (GRASPEL) for learning ultra-sparse graphs from data by leveraging the latest results in spectral graph theory (Feng) 2016] 2018 /Zhao et al.
2018). There is a clear connection between our approach and the GSP-based Laplacian estimation
methods (Dong et al. 2016 Kalofohas 2016 Egilmez et al. 2017 Kalofolias & Perraudin 2019
Dong et a.. 2019). as well the classical graphical Lasso Iramework (Fredman et al. 2008)
Specifically, by treating p-dimensional data points as p graph signals, GRASPEL learns graph Laplacian by maximizing its first few eigenvalues as well as the smoothness of graph signals across edges, subject to a graph sparsity constraint. By iteratively interleaving recent nearly- linear time
spectral graph sparsification, coarsening and embedding methods (Feng 2016 2018 2018), GRASPEL enjoys nearly-linear runtime and space complexity.
Zhao et al.
GRASPEL is similar to the original graphical Lasso (Friedman et al., 20088 with the precision matrix
replaced by graph Laplacian. GRASPEL iteratively identifies and includes the most spectrally- critical edges into the latest graph, so that the first few Laplacian eigenvalues and eigenvectors can be most significantly perturbed by adding the minimum amount of edges. The iterative graph learning procedure will be terminated when the graph spectra become sufficiently stable (or graph signals become sufficiently smooth across the graph and lead rather small Laplacian quadratic forms). Comparing with state-of-the- methods. GRASPEL allows more scalable estimation of attractive Gaussian Markov Random Fields (GMRFs) for even very large data set. We show through extensive experiments that GRASPEL can learn high-quality ultra-sparse (tree-like) graphs that can be immediately leveraged to significantly improve the efficiency and accuracy of spectral clustering (SC) tasks; the proposed approach also leads to the development of multilevel t- t-Distributed Stochastic Neighbor Embedding (t-SNE) algorithm that shows significantly improved runtime over existing methods (Maaten & Hinton 2008 Van Der Maaten 2014).
2 BACKGROUND OF GRAPH LEARNING VIA LAPLACIAN ESTIMATION
Given M observations on N data entities stored in a data matrix X E TR N each column of X can be considered as signal on a graph. The recent graph learning method (Dong et al. 2016) aims to estimate graph Laplacian from X while achieving the following desired characteristics:
1) Smoothness of signals the graph. The graph signals corresponding to the real-world data should be sufficiently smooth on the learned graph structure: the signal values will only change gradu- ally across connected neighboring nodes. The smoothness of a signal x over a undirected graph G
(V. E, w) can be measured with Laplacian quadratic form xf La = Σ ( (p) - x (4)
(F-q)E
where L = D- - W denotes the Laplacian matrix of graph G with D and W demoting the degree and the weighted odjacency matrices of G. and up.q = (p. q) denotes the weight for edge (p. q). The smaller value of quadratic form indicates the smoother signals across the graph. It is also possible to quantify the smoothness (Q) of a set of signals X over graph G using the following matrix trace (Kalofolias 2016): Q(X, L) = Tr(XTTX), I.)), where Tr denotes the matrix trace.
2) Sparsity of the estimated graph (Laplacian). Graph sparsity is another critical consideration in graph learning. One of the most important motivations of learning graph is to use it for downstream data mining or machine learning tasks. Therefore, desired graph learning algorithms should allow better capturing and understanding the global structure (manifold) of the data set. while producing sufficiently sparse graphs that can be easily stored and efficiently manipulated in the downstream algorithms, such as graph clustering, partitioning, dimension reduction, data visualization, etc. To this end, the graphical Lasso algorithm (Friedman et al. 2008) has been proposed to learn the structure in an undirected Gaussian graphical model using Li regularization to control the sparsity of the precision matrix. Given a sample covariance matrix S and a regularization parameter B, graphical Lasso targets the following objective function:
max log dct(O) - TrS))) 31(011
(1)
2

---

Under review as a conference paper at ICLR 2020
over all non-negative definite precision matrices ④ The first two terms together can be interpreted the log-likelihood under Gaussian Markov Random Field (GMRF). B||@||, is the sparsity promoting regularization term. This model tries to learn the graph structure by maximizing the penalized log-likelihood. However, the log-determinant problems are very computationally expensive. The emerging GSP- -baded methods infer the graph by adopting the criterion of signal smoothness (Kalofolias] 2016: Dong al.) 2016; Egilmez et al. 2017 Kalofolias & Perraudin 2019). However, their extremely high complexıties do not allow for learning large-scale graphs involving millions or even hundred thousands nodes. Furthermore, these methods usually require nontrivial parameters tuning for controlling graph sparsity.
GRASPEL: A SPECTRAL APPROACH TO GRAPH LEARNING FROM DATA
At high level, GRASPEL gains insight from recent GSP-based Laplacian estimation methods (ong al. 2019). aiming to solve the following optimization problem that is similar to the graphical Lasso problem (Friedman al. 2008):
maximize: logdet de) aTTr("IXX) 3||
where denotes the set of valid Laplacian matrices. can be shown that the three terms in 2 are corresponding to log det(O), Tr(e.) and @||@|| in (1). respectively. When the precision matrix @ is restricted to be graph Laplacian, and each column vector in the original data matrix X is treated as graph signal vector, there is close connection between our formulation and the graphical Lasso problem. Since graph Laplacians are symmetric and positive definite (PSD) matrices (or M matrices) with non-positive off-diagonal entries, this formulation will lead to the estimation of attractive GMRFs (Dong et al. 2019).
3.1
OVERVIEW OF GRASPEL.
Step Spectral
graph embedding
Node embedding vectors
New edge
vectors
S
Gk
Step 3A. Check embedding distortion
P
GO
Step 1. Initial graph construction
Step 38. Add spectrally-critical edge
Step 4. Check embedding stability
Figure 1: The overview of the proposed GRASPEL framework.
To achieve good efficiency in graph learning that may involve millions of nodes, instead of solving directly, GRASPEL leverages spectral approach for solving (2) implicitly. Define spectrally-crittcc edges to be the ones that can most effectively perturb the graph spectral properties, such as the first few Laplacian eigenvalues and eigenvectors. GRASPEL aims to iteratively identify and add the most spectrally-criticn edges into the latest graph until no such edges be found, which consists of the following key steps as illustrated in F
Step (I): Initial graph construction. Similar to (Kalofolias & Perraudin) 2019), we start with constructing an ANN graph that can be achieved O log N) time, where each edge weight encodes the similarity (e.g. Gaussian kernel or cosine similarity) of two data entities; next, the ANN graph is converted into an ultra-sparse nearest-neighbor (uNN) graph with O(N log N) edges by leveraging nearly-linear-time spectral sparsification algorithm (Feng) 2018).
Step (2): Spectral graph embedding. We apply a nearly- lire--lin-r-ieeeee spectral embedding procedure (Zhao et al, 2018) to the current graph so that each node will be associated with a low-dimensional embedding vector (e.g. v. for node S in Figure [). where the embedding dimension (number of eigenvectors) can be determined based on the largest gaps of the first few (e.g. 100) Laplacian eigenvalues (Peng al. 2015).

---

Under review as a conference paper at ICLR 2020
Step (3): Spectrall--critical edge identification. We quickly check the embedding distortion for =mmb each candidate edge (node pair) defined as 1) = zdatu where gmm (zdota) denotes the distance in the embedding (data) vector space. The edges with the largest 1) are considered as the most spectrally-crittcal edges and will be added into the latest graph.
Step (4): Spectral stability checking. After repeating the Steps (2)-(3) multiple times for adding new edges, GRASPEL will return the final graph once the overall embedding distortion becomes sufficiently small or stable: if the first few Laplacian eigenvalues do not change much over iterations of adding extra edges, the graph spectra is considered stable (robust) since adding more edges does not significantly perturb the key (smallest) eigenvalues.
Connection between GRASPEL and the formulation 22 The original optimization objective function includes the following three components: (a) log det(L) corresponding to the sum of the logarithmic Laplacian eigenvalues,
(b) -oTr(XTTLL) LX) corresponding to the smoothness of signals across the graph] | and (c) - |L]1 corresponding to graph sparsity. Including spectrally-critical edges into the graph will significantly impact the first few Laplacian eigenvalues and eigenvectors key to graph spectral properties, thereby dramatically improving embedding distortion and the overall smoothness of signals across the graph. It can be shown that including any additional edge into the graph will monotonically increase (a) while monotonically decreasing both (b) and (c). Therefore, when the spectra of the learned graph is not stable adding any spectrally-critcca edges into the graph will dramatically increase (a) while slightly decreasing (b) and (c), since the improved graph signal smoothness will only result in slight change (increase) to Tr(X²LX).
Convergence analysis for the GRASPEL framework. The objective function in 2 will be ef- fectively maximized by including only a small amount of spectrally-critte -citticcll edges until the first few eigenvalues become sufficiently stable; when adding extra edges can no longer perturb the first few eigenvalues, (b) and (c) will start to dominate the objective function value, indicating that the iterations should be terminated. The stopping condition can be controlled by properly setting an embedding distortion threshold for 1j or parameters a and [3.
Complexity analysis for the GRASPEL framework. To achieve scalable spectral graph embedding edges in Steps (2)-(3), we will leverage the latest high- performance spectral graph algorithms. Since all the kernel functions involved in GRASPEL, such as ANN graph construction (Muja & Lowel 2009: 2014, Malkov & Yashunin 2018). spectral graph sparsification (Feng) [016)] 2018), spectral coarsening and embedding (Zhao al. (018), are all nearly-linear linear ON log N) time algorithms, the entire spectral graph learning approach GRASPEL also has a hearly-linees time complexity.
key to identification of spectrally-critic
3.2 DETAILED STEPS IN GRASPEL
3.2.1 INITIAL GRAPH CONSTRUCTION
As aforementioned, (approximate) KNN graphs can be used to construct the initial graphs in Step (1), since they can be created very efficiently (Muja & Lowe,2009) while being able to approximate the local data proximity (Roweis & Saul 2000). However, traditional kNN graphs have the following drawbacks: a) the KNN graphs with large K (the number of nearest neighbors) has the tendency of increasing the cut-ratio (Qian et al. 2012); the optimal i value is usually problem dependent and can be very difficult to find. In this work, we will start creating an (approximate) kNN graph with a relatively small & value (c.g. k = 5), and strive to significantly improve the graph quality by adding extra spectrally- critticll edges through implicitly solving the proposed optimization problem in (2) In the last, a spectral sparsification algorithm (GRASS) has been applied to further simplify the KNN graph into uNN graph with only O(N log N) edges Wang & Feng 2017).
3.2.2 SPECTRAL GRAPH EMBEDDING
Spectral graph embedding directly leverages the first few nontrivial eigenvectors for mapping nodes onto -ow-dimensional space (Belkin & Niyogi 2003). The eigenvalue decomposition of Laplacian matrix is usually the computational bottleneck spectral graph embedding, especially for large graphs (Shi & Malik| 2000; Von Luxburg 2007| Chen et al.) 2011). To achieve good scalability, we exploit multilevel spectrally graphs that allow for much faster eigenvector (eigenvalue) computations without loss of accuracy (Zhao et al. 2018). Specifically, the multilevel method first
I When graphs signals in X are sufficiently smooth, they will align well with the first few cigenvectors corresponding to the smallest few eigenvalues, leading to relatively small trace I Tr(x" Lxx). *GRASS can he downloaded at http:////.....ogg..oooo//mmtt//t
graphspar
4

---

Under review as a conference paper at ICLR 2020
spectrally coarsens the fine-level graph into much smaller ones with preservation of key spectral properties, and then maps the eigenvectors obtained on the coarse graphs back to the original graph: multilevel eigenvector refinement (smoothing) and orthogonalization procedures can be applied to further improve the approximation accuracy (Zhao et al. 2018
3.2.3
SPECTRALLY-CRITTER EDGE IDENTIFICATION
Once Laplacian cigenvectors are available for the current graph, we can identify spectrally-critical edges by looking at each candidate edge's s embedding distortion (1)). To this end, we exploit the following first-order spectral perturbation analysis to quantitatively evaluate each candidate edge's impact on the first few eigenvalues. Denote the edge weight by Wp.g and the Laplacian eigenvector corresponding to the eigenvalue X; by u4 We define ep E R" to be a standard basis vector with all zero entries except for the p-th being 1, and Ep.q Ep Eg- The following theorem will allow us to identify the most spectrally-critical edges leveraging the first few Laplacian eigenvectors.
Theorem The spectral criticality Cp. or embedding distortion Up.4 of candidate edge (p, q) on 3p.
the Laplacian eigenvalue X can be properly estimated by Cp.q wp.g (u, cpaa) 4p.4
adats
Proof: See the Appendix.
Edge identification with Fiedler vectors. The idea for identifying spectrally-critienn edges is to sort nodes according to the Fiedler vector. Only the node pairs with large embedding distances will be examined as candidate edges. Therefore, we are able to limit the search within the candidate edge connections between the top and bottom few nodes the 1D sorted node vector. Only the candidate edges with top spectral criticality or embedding distortion values will be added into the latest graph.
Edge identification with multiple eigenvectors. With i eigenvectors for spectral embedding, we can first project the graph nodes onto a k-dimensional space and perform spectral clustering to group the nodes into k clusters, where the embedding dimension k can be determined based on the largest gaps of the first few (e.g. 100) Laplacian eigenvalues (Peng et al.) (015). Next, we only have to examine the candidate edges that connect nodes between two distant clusters in the embedding space, and sort them based on embedding distortions.
To further reduce the computational cost, we first perform spectral graph coarsening (Zhao et al. 2018) and subsequently search for high-distortion candidate edges the coarsest graph. Once small set of top spectrally-crine critical edges has been identified, we will find their corresponding candidate edges in the original graph. Since each coarse-level candidate edge may correspond to multiple candidate edges in the original graph, we will sort them based on their embedding distortions, and only add the ones with largest distortions into the latest graph. The algorithms for spectrally-criticn edge identification using Fiedler vector and multiple eigenvectors have been described in Algorithm I and Algorithm 2 in the Appendix.
3.2.4 SPECTRAL STABILITY CHECKING
We employ an iterative procedure in GRASPEL repeatedly add new edges into the graph, thereby improving the approximation quality. Specifically, at each iteration new ppectrally-critica edges are
Smaller eigenvalue variation %))
400
identified and added to the current graph; we will ter-
300
minate the iterations when the graph spectra become
sufficiently stable. Alternatively, we can check if the embedding distortions of top candidate edges still
200
keep improving; if not, the iterations can be termi- nated, indicating that no additional spectrally- edges can be found significantly perturb the first few Laplacian eigenvectors and eigenvalues. In prac- tice, we observe that the number of spectrally-critte edges decreases rapidly within very few (two to four) iterations.
100
0
3
4
5
iteration
For GRASPEL we adopt the following scheme for checking the spectral stability of each graph learning iteration: 1) in each iteration, we compute and record the several smallest cigenvalues of the latest graph Laplacian according to the largest gap between eigenvalues (Peng et al., 2015): for example, the first (smallest) k nonzero eigenvalues that critical for spectral clustering will be stored; 2) we check
Figure 2: Variation ratio of bottom eigenvalues
with increasing number of iterations.
5

---

Under review as a conference paper at ICLR 2020
whether a sufficiently stable spectra has been reached for graph learning by comparing them with the eigenvalues computed in the previous iteration: if the change significant, more iterations may be needed. To this end, we record the first Laplacian eigenvalues computed in the previous (current) iteration into vector Up (1p+1), and calculate the spectral variation ratio by:
11 Up+1
ratio
(3)
A greater spectral variation ratio indicates less stable cigenvalues within the latest graph, and thus justifies another iteration for adding more spectrally-critical edges into the graph. The spectral stability checking results for the USPS data set (see Appendix for details) have been shown in Figure 2 as observed, only four iterations will suffice for achieving rather stable graph spectra.
4 EXPERIMENTS
In this section, extensive experiments have been conducted to evaluate the performance of GRASPEL for a variety of public domain data sets. Note that all the graphs learned by GRASPEL have ultra- sparse tree-like structures with graph densities (defined as / between 1.1 to 1 1.3; our approach allows learning much sparser graphs when comparing with the latest approach that always produces graphs with densities much greater than 3.0 (Kalofolias & Perraudin 2019).
4.1 GRAPH LEARNING FOR SPECTRAL CLUSTERING
As shown in Algorithm 3 in Appendix, the the classical spectral clustering (SC) algorithm first constructs graph where each edge weight encodes similarities between different data points (entities); then SC calculates the eigenvectors of the graph Laplacian matrix and embeds data points into low- dimensional space (Belkin & Niyogi 2003): in the last, k-means algorithms are used to partition the data points into muluple clusters. The performance of SC strongly depends on the quality of the underlying graph (Guo 2013). In this section, we apply GRASPEL for graph construction, and show the learned graphs can result in drastically improved efficiency and accuracy in SC tasks. The detailed description of our evaluation metrics, data sets and experiment setup has been provided in Appendix.
Table D shows the ACC and NMI results of SC with graphs constructed by different methods with the best numbers highlighted, where graph construction time (Time-C) and spectral clustering time (Time-S) that involves eigendecomposition and kmeans clustering have also been reported. Note that the high computational and memory cost of recent GSP-based graph learning methods, such as GL-SigRep (Dong et al.) 2016). GL-Logdet (Dong et al.) 2016) and GLSC (Egilmez et al.) 2017) do not allow for processing data sets with more than a few thousands of data entities, thus can not be used for real-world SC tasks. We observe that GRASPEL can consistently lead to dramatic performance improvement in SC. Specifically, GRASPEL beats all competitors in clustering accuracy (ACC) across all data sets: GRASPEL achieves more than 18% accuracy gain USPS and 13% gain COIL20 over the second-best methods; for the MNIST data set GRASPEL also achieves over 14% accuracy gain over the SC with standard KNN graph and more than 6.X speedup in graph construction time. Note that the graphs learned by GRASPEL are ultra sparse and have tree-like structures, thereby allowing much faster eigendecompositions in SC when comparing with other methods (Wang & Feng 2017]: the SC of the MNIST data set with standard kNN takes over 6, 000 seconds, which will be dramatically improved to require less than three seconds (over 2, X00 speedup) using the graph learned by our method (GRASPEL).
The superior performance of GRASPEL is due to the following reasons: 1) In traditional kNN graphs, all the nodes have the same degrees: as a result, the clustering may strongly favor balanced cut, which may lead to improper cuts in high-density regions of the graph. In contrast, GRASPEL always learns ultra-sparse (tree-like) graphs that only include edges with the largest impact graph spectral (structural) properties; as a result, the corresponding cuts will always occur in proper regions of the graph, which enables to handle even unbalanced data. 2) Our approach is less susceptible to noise in similarity calculations, since it only connects two nodes according to its spectral criticality (embedding distortion). Based on matrix perturbation theory (Stewart & Sun 1990), eigenvectors corresponding small eigenvalues can be more influenced by noises in simlantties, which can lead to accuracy degradation when the number of desired clusters is not small (Hennig et al. (015). Although the consensus kNN (Premachandran & Kakarala, 2013) attempts to use consensus information for discarding noisy edges, the improvement can still be rather limited since it can be difficult to extract useful consensus information from kNN graphs with small neighborhood sizes.
4.2 RESULTS FOR GRAPH RECOVERY
We also quantitatively compare graph recovery performance of GRASPEL with state-of-the-an GSP-based graph learning methods, by comparing the graphs learned from observations to the ground
6

---

Under review as a conference paper at ICLR 2020
Table 1: Spectral Clustering Results
ACC NMI Time- (seconds) V Time------ S (seconds)
Daja Set
Standard KNN
ConSKNNN
LSGL
GRASPELTFIC..
GRASPELIMUI)
COIL-20 PenDigiis USPS
78.801 D. 0.36/0337
79.86/ 0.8 0.5400228
53/1 65/00 22/
0.96/ 1.400
85,39/ D 20,20
81,12/0.80 1.25/0.47
14 0& & 49/46,441
43.55A0.99 491622/15.66
85.96/ D.MO 4.5170.27
84. 0.806655/00 28
2.66/1022
789 1982774.77
92.5W 0.877 3.90021
0.85/ 0.06
MNIST
71.55/ 0.72/ 242 186785
81.67 0.75/ 59,27/2.00
79.05/ 0.74/ 18/300
indicates that the method is not capable for handling data sets of this scale.
Table 2: Graph Recovery Results
The Gaussian graph
The ER graph
Algorithm
F-measure
Precision
Recall
NMI
F-measure
Precision
Recall
NMI
GL-SigRep
0.8310
0.8120
0.8826
0.5272
0.7243
0.6912
0.8389
0.3600
GL-Log
0.8178
0.8193
0.8521
0.4701
0.7378
0.6983
0.8030
0.4012
GLSC
0.7203
0.6901
0.9000
0.3208
0.6609
0.5427
0,8224
0.3379
GRASPEL
0.8499
0.8394
0.8812
0.5397
0.7256
0.6990
0.8132
0.3607
truth. The experiments are performed for two widely-used synthetic graphs: 1) The Gaussian graph: the coordinates of the vertices are generated uniformly in the unit square randomly. Edge weights are determined by the Gaussian radial basis function. 2) The ER graph: the graphs generated by following the Erdos-Reny model (Erdōs & Rényi 1960).
Four widely adopted evaluation metries in information retrieval have been adopted: Precision, Recall, F-measure and Normalized Mutual Information (Dong et al., 2016). The Precision measures the percentage of correct edges (the edges that are present in the ground-truth graph) in the learned graph. The Recall measures the percentage of the edges in the ground -trtth graph that are also in the learned graph. F-measure measures the overall quality by taking both Precision and Recall into account. NMI measures the mutual dependence between the edge sets of the learned graph and the ground-truth graph. The best two F-measure and NMI results have been highlighted in Table 2 showing the effectiveness of GRASPEL. in learning graphs that are always close to the ground-truth graphs. Compared with other graph learning methods that can only deal with a few hundreds or thousands of data entities, GRASPEL has much better (nearly-linear runtime and space) scalability and thus will be more efficient for handling large data sets.
As shown in Figure 3 the graph recovery run- time results of GRASPEL has been compared with state-of-the-art graph learning methods, such as the Gl-SigRep. Gl.-LogDet and GLSCC algorithm proposed in (Dong et al.) 2016|Egilmae et al. (017). Since the graph learning method LSGL proposed in (Kalofo- lias & Perraudin 2019) can not produce com-
10
GL-SigRop
GL-LogDel
10a
GRASPEL
GLSC
run time(s)
10
parable quality of graph recovery results, we did not show the runtime results in the fig- ure. As observed, the proposed approach has a much better runtime scalability when com- paring with state-of -ftte--rttttttt methods.
10'
109
4.3 APPLICATIONS IN T-SNE
10
The t- t-Distributed Stochastic Neighbor Embed- ding (t-SNE) has become one of the most pop- ular visualization tools for high-dimensional data analytic tasks (Maaten & Hinton| 2008)
10'
10a
10a
number of data samples
Figure 3: Graph recovery time comparison.
Linderman & Steinerberger (017). However,
its high computational cost limits its applicability to large scale problems. An substantially improved I-SNE algorithm has been introduced based on tree approximation (Van Der Maaten 2014 However, for large data set the computational cost can still be very high.
A multilevel t-SNE algorithm has been proposed in (Zhao et al. 2018 to dramatically mitigate the computational burden by leveraging spectral graph coarseming as a pre- proceesccsing step applied to the original KNN graph. A much smaller set of representative data points can be then selected from the coarsened graph for t-SNE visualization. However, constructing the original kNN graph
7

---

Under review as a conference paper at ICLR 2020
still be costly while the performance may strongly depend on the selection of the number of nearest neighbors. In this work, we use GRASPEL learn ultra-sparse graphs that can be further reduced into much smaller ones using the spectral graph reduction (Zhao et al. 2018). Then more efficient t-SNE visualization can achieved based on the data points corresponding to the nodes in the coarsened graphs.
Figure 4 shows the visualization and runtime results of the standard t-SNE (with tree-based accel- eration) Van Der Maaten 2014) and the multilevel t-SNE algorithm (Zhao al. (2018) based on graphs learned by GRASPEL. runtime for the multi-level t-SNE method covers both the graph learning and t-SNE procedures. When using a 5.X graph reduction ratio, t-SNE can be dramatically accelerated (12.8X and 7X speedups for MNIST and USPS data sets, respectively) without loss of visualization quality.
USPS data set
20
20
-00
-00
-40
-20
-60
-40
standard t-SNE: 99.8s
5X reduction t-SNE: 14.1s
MNIST data set
0
-20
-20
40
standard t-SNE: 1921.7s
5X reduction t-SNE: 149.3s
Figure 4: t-SNE visualization results.
5 CONCLUSION
In this work, present scalable spectral approach to graph learning from data. By replacing the precision matrix with graph Laplacian, our approach aims estimate ultra-sparse weighted graphs and has a clear connection with the prior graphical Lasso method. Compared with prior graph learning approaches that do not scale to large problems, our approach is more scalable for constructing graphs that can immediately lead to substantially improved computing efficiency and solution quality for variety of data mining and machine learning applications, such as spectral clustering (SC), and t-Distributed Stochastic Neighbor Embedding (I-SNE).
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
Francis R Bach and Michael Jordan. Learning spectral clustering, with application to speech separation. Journal of Machine Learning Research, 7(0ct):1963-2000 2006.
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation, 1376)11333-139,, 2003.
George H Chen, Devavrat Shah, et al. Explaining the success of nearest neighbor methods in prediction. Foundations and Trends in Machine Learning, 10(5-6):337-588, 2018.
Wen-Yen Chen, Yangqiu Song. Hongjie Bai, Chih-Jen Lin, and Edward Y Chang. Parallel spectral
clustering in distributed systems. IEEE transactions pattern analysis and machine intelligence, 33(3):568-535 586, 2011.
Xiaowen Dong, Dorina Thanou, Pascal Frossard, and Pierre Vandergheynst. Learning laplacian matrix in smooth graph signal representations. IEEE Transactions on Signal Processing, 64(23): 6160-6175 2016.
Xiaowen Dong, Dorina Thanou, Michael Rabbat, and Pascal Frossard, Learning graphs from data: A signal representation perspective. IEEE Signal Processing Magazine, 36(3):44 63, 2019.
Hilmi Egilmez, Eduardo Pavez, and Antonio Ortega. Graph learning from data under laplacian and structural constraints. IEEE Journal of Selected Topics in Signal Processing, 1(6):825--8 8411 2017.
Paul Erdös and Alfréd Rényi. On the evolution of random graphs. Publ. Math. Inst. Hung. Acad. Sci, 5(1):17-60, 1960.
Zhuo Feng. Spectral graph sparsification in nearly-linear time leveraging efficient spectral perturbation analysis. In Proceedings of the 53rd Annual Design Automation Conference, pp. 57. ACM, 2016.
Zhuo Feng. Similarity-awee spectral sparsification by edge filtering. In 2018 55th ACM/ESDA/EEFF Design Automation Conference (DAC), pp. 1-6. IÉEE, 2018
Jerome Friedman, Trevor Hastie, and Robert Tibshirani. Sparse inverse covariance estimation with the graphical lasso. Biostatistics, 9(3):432-4444 2008
Xiaojie Guo. Robust subspace segmentation by simultaneously learning data representations and their affinity matrix. In /JCAI, pp. 3547-3553, 2015.
Christian Hennig, Marina Meila, Fionn Murtagh, and Roberto Rocci. Handbook of cluster analysis. CRC Press, 2015.
Tony Jebara and Vlad Shchogolev. B B-matching for spectral clustering. In European conference on machine learning. pp. 679-686. Springer, 2006.
Tony Jebara, Jun Wang, and Shih-Fu Chang. Graph construction and b-matching for semi-supervised learning. In Proceedings of the 26th annual international conference machine learning, pp- 441 441-448. ACM, 2009.
Vassilis Kalofolias. How to learn graph from smooth signals. In Artificial Intelligence and Statistics, pp.
2016.
Vassilis Kalofolias and Nathanaël Perraudin. Large scale graph learning from smooth signals. International Conference Learning Representations (ICLR 2019), 2019.
George C Linderman and Stefan Steinerberger. Clustering with t-sne, provably. arXiv preprint wwXiv:1706.0258. 2017.
Yang Liu, Quanxue Gao, Zhaohua Yang, and Shujian Wang. Learning with adaptive neighbors for image clustering. In IJCAI, pp. 2483-2489 2018.
Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-sne. Journal of machine learning research, 9(Nv)):2579 2605, 2008
Markus Maier, Ulrike V Luxburg, and Matthias Hein. Influence of graph construction graph-based clustering measures. In Advances neural information processing systems, pp. 1025-1032, 2009.
Yury A Malkov and Dmitry A Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE transactions on pattern analysis and machine intelligence, 2018

---

Under review as a conference paper at ICLR 2020
Marius Muja and David G Lowe. Fast approximate nearest neighbors with automatic algorithm configuration. VISAPP (1), 2(331-340):2, 2009.
Marius Muja and David G Lowe. Scalable nearest neighbor algorithms for high dimensional data.
IEFE Transactions on Pattern Analysis and Machine Intelligence, 36(1 36(11)::227-22240 2014.
Feiping Nie, Xiaoqian Wang, and Heng Huang, Clustering and projected clustering with adaptive
neighbors. In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 977-986. ACM, 2014.
Feiping Nie, Xiaoqian Wang, Michael I Jordan, and Heng Huang. The constrained laplacian rank algorithm for graph-based clustering. In AAAI, pp. 1969-197777 2016.
Christos H Papadimitrou and Kenneth Steiglitz. Combinatorial optimization: algorithms and com- plexity. 1982.
Massimiliano Pavan and Marcello Pelillo. Dominant sets and pairwise clustering. IEEE transactions on pattern analysis and machine intelligence, 291):167--172, 2007.
Richard Peng, He Sun, and Luca Zanetti. Partitioning well-clustered graphs: Spectral clustering works. In Proceedings of The 28th Conference on Learning Theory (COLT), pp. 1423-1455, 2015.
Vittal Premachandran and Ramakrishna Kakarala. Consensus of k-nns for robust neighborhood selection on graph-based manifolds. In Proceedings of the IEEE Conference on Computer Vision and Puttern Recognition, pp. 1594-1601, 2013.
Jing Qian, Venkatesh Saligrama, and Manqi Zhao. Graph-based learning with unbalanced clusters. arXiv preprint /205. /496, 2012.
Michael G Rabbat. Inferring sparse graphs from smooth signals with theoretical guarantees. In 2017 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 6533 6537. IEEE, 2017.
Sam Roweis and Lawrence K Saul. Nonlinear dimensionality reduction by locally linear embedding. science, 290(5500):2323-23333 22223,222,2222 2000.
Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on pattern analysis and machine intelligence, 22(8):888-905 2000.
GW Stewart and JG Sun. Matrix perturbation theoryacademic press. San Diego, 1990.
Alexander Strehl and Joydeep Ghosh. Cluster ensembles a knowledge reuse framework for combin- ing multiple partitions. Journal of machine learning research, 3(Dec):583-617, 2002.
Laurens Van Der Maaten. Accelerating t-sne using tree-based algorithms. The Journal of Machine Learning Research, 15())3322-33255, 2014.
Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17(4))395-416 2007.
Yongyu Wang and Zhuo Feng. Towards scalable spectral clustering via spectrum- sparsifi- cation. arXiv preprint 1710:0171004488. 2017.
Lihi Zeinik-Manor and Pietro Perona. Self-tuning spectral clustering. In Advances in neural information processing systems, pp. 1601-1608, 2005.
Zhiqiang Zhao, Yongyu Wang, and Zhuo Feng. Nearly-linear time spectral graph reduction for scalable graph partitioning and data visualization. arXiv preprint arXiv: / 2018.
Xiatian Zhu, Chen Change Loy, and Shaogang Gong. Constructing robust affinity graphs for spectral clustering. In Proceedings of the IEEE Conference Computer Vision and Pattern Recognition, pp. 1450-1457, 2014.
10

---

Under review as a conference paper at ICLR 2020
APPENDIX A PROOF OF THEOREM 1
Let Lp denote the Laplacian matrix of undirected graph P, and u, denote the i-th eigenvector of Lp corresponding to the i-th eigenvalue X that satisfies:
A
(4)
then we have the following eigenvalue perturbation analysis:
(Lp 5Lp) (u: + òu,) = (A, 5x,) 0u,),
(5)
where perturbation p that includes new edge connection applied Lp, resulting in perturbed eigenvalues and eigenvectors X; SA, and u, + ou, for 1,.,, n, respectively.
Keeping only the first-order terms leads to:
Lpdu, 8Lpu, λ;du, + 8d2
(6)
Write dug in terms of the original eigenvectors uy for = ,,,,, m
ou,- Σ ag4.
Substituting
7 into 6 leads to:
Lp
oan; + 8Lpu, = A Σ aa4; + 8AZ44-
(8)
Multiplying uf to both sides of results in:
n a, + dA.uf u4
u LP a, uf 88pp, \uoy Σ
(9)
Since un for for i I,... n are unit-length, mutually- eigenvectors, we have:
T a,u; anu? Auu4.
of Lp a,u auu Lpus,
(10)
Substituting into 10 we have:
0,44 Lpu; an Xa4.
(11)
According to 10 we have:
u Lp
0g44 = Aou T Σ a,u,
(12)
Substituting
122 into 9 leads to:
o 8Lru, dx,su u, 8A,
(13)
Then the eigenvalue perturbation due to öLp is given by:
5i; upa (uf pp.))
(14)
If each edge weight Wn.a encodes the similarity of data vectors Tp and xy nodes and g, it can be shown that Wp.g _ where ddaaa denotes the distance between Tp and zigi the other find edge with large Wp.g (uf cp.a)² or Tp.. including this edge into the current graph will significantly perturb the Laplacian 2y.0 eigenvalue X; and eigenvector u4.
hand, (u. ep.g) emb, Therefore, as long
11

---

Under review as a conference paper at ICLR 2020
APPENDIX B ALGORITTMM
Algorithm 1 GRASPEL with Fiedler-vector based ppectrally-critices edge identification
Input: data set D with N data points 21,=2N E IRd, window size e, edge selection ratio Ç.
Output: The spectrally-eeamed graph.
I: Construct an initial ANN graph G. as in (Chen et al. 2011
2: Initialize: Terminate=0:
while 1eerminate=00 do
Embed G; with the Fiedler vector and sort data points (nodes);
5: Evaluate the embedding distortions of candidate edges connecting the top and bottom e/ sorted nodes;
6: Select top (N edges based on the evaluation result and add them G.;
7: Check the spectral stability and update Terminate.
8: end while
Algorithm 2 GRASPEL with eigenvectors based peecttally-critiiee edge identification
Input: A data D with N data points æ1 G..EN R and that denote the numbers of edges to be added in the spectrally-coarsenned graph and the original graph in each iteration, respectively. Output: The spectrally-Ieammel graph.
I: Construct an initial ANN graph G. as in CChnn et al. 2011
2: Initialize: Terminate=0;
3: while TideeTrrae Terminate=00 do
4: Perform spectral graph coarsening G, to obtain its coarsened graph Gei
5: Spectral clustering of G. with multiple eigenvectors;
6: Select edges with largest distortion between distant clusters of Ges
7: for Each selected edge in G. do
8:
for Each of its two nodes do
9:
Find its corresponding set of nodes in Gt:; end for Form the edge set Eorig between the above two sets nodes;
10:
12:
if Eorigl S - then
13:
Add all edges E Eorig G.; else
14:
15:
for Each edge Borin do Evaluate its embedding distortion; end for
16:
17:
18:
Sort edges E Eorig based on their embedding distortions and add the top | ones to G;; end if
19:
20:
end for
21: Check the spectral stability and update Terminate.
22:
end while
Algorithm 3 Spectral Clustering Algorithm
Input: A graph = (V, E, w) and the number of clusters k. Clusters Cj..C
Output:
1: Compute the adjacency matrix Ac. and diagonal matrix Do;
2: Ohtain the unnormalized Laplacian matrix Lo=De-AA:
3: Compute the eigenvectors uu....u that correspond to the bottom nonzero eigenvalues of LG;
4: Construct * with eigenvectors of Le stored as columns;
5: Perform k-means algorithm partition the of U into clusters and return the result.
APPENDIX C DATA SETS DESCRIPTION
COIL20: A data contains 1, 440 gray-scale images of 20 objects. and each object on turntable has 72 normalized gcay-scale images taken from different degrees. The image size is 32x 32 pixels.
PenDigits: A data set consists of 7,494 images of handwritten digits from 44 writers, using the sampled coordination information. Each digit is represented by 16 attributes.
USPS: A data set includes 9, 298 scanned hand-written digits on the envelops from U.S. Postal Service with 256 attributes.
12

---

Under review as a conference paper at ICLR 2020
MNIST: A data set consists of 70,000 images of handwritten digits. Each image has 28-by-28 pixels in size. This database can be found from Prof.Yann Yann LeCun's website
http://yammleecun.co////////////
APPENDIX D COMPARED ALGORITHMS
Standard kNN: the most widely used affinity graph construction method. Each node connected to its k nearest neighbors.
Consensus of KNN (cons-kNN) (Premachandran & Kakarala 2013): adopts the state-of-the-ar neighborhood selection methods construct the afhinity graphs. It selects strong neighborhoods to improve the robustness the graph by using the consensus information from different neighborhoods in given kNN graph.
LSGL (alofolias & Perraudin 2019) a method to automatically select the parameters of the model introduced in (Kalotolias) 2016) given desired graph sparsity level.
GL-SigRep (Dong et al., 20166: construct graph from signals that assumed to be smooth with graph. graph.
respect the corresponding
GL-LogDet (Dong al. 2016): encodes the information about the partial correlations between the variables without the constrant to form a valid Laplacian.
Graph Learning under structural constraints (GLSC) (Egilmez et al. 2017): formulated the problem to maximum posterior estimation of Gaussian Markov Random Field (GMRF) when the precision matrix is chosen to be graph Laplacian.
APPENDIX E EVALUATION METRIC
Σ (1), map(e;))
ACC
(15)
n
where the number of samples in the data set, Yi is the ground-truth label provided by the data sets, and o is clustering result obtained from the algorithm. d(z, y) is delta function defined as: 8(z, y)=1 for y. and 6(x, =0, otherwise. map( () is permutation function that maps each cluster index C, to a ground truth label, which can be realized using the Hungarian algorithm (Papadimitrou & Steiglitz. (982). ACC measures agreement between the clustering results generated by clustering algorithms and the ground-truth labels. A higher value of ACC indicates better clustering quality.
2)
For two random variables P and Q, normalized mutual information is defined as (trehh & Ghoshh 2002
T(P.Q)
NMI
(16)
(H(P)H(Q)
where [(P, Q) denotes the mutual information between and Q while H(P) and H()) are entropies of and Q. In practice, the NMI metric can be calculated as follows (Strehl & Ghosh] 2002
Σ ni. log( ny-
NMI
(17)
k E n. 1o, 4
n:log )(
where n is the number data points in the data set, is the number of clusters, n& is the number of data points in cluster C; according to the clustering result generated by algorithm, ny is the number of data points in class Cj according to the ground truth labels provided by the data set, and ni.j is the the clustering result well as in class C₁ according
number of data points in cluster C; according the ground truth labels. The NMI value is in the range of [0. 1]. while higher NMI value indicates a better matching between the algorithm generated result and ground truth result.
13


Reviews:
[{"review_id": "rkeVRxoCFB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper presents a scalable spectral approach for graph learning. In particular, the authors use graph Laplacian as precision matrix, and show the connection between the proposed method and graphical Lasso. Three tasks, including spectral clustering, graph recovery and t-SNE visualization, are considered in experiments.\n\nPros.\n1. Scalable graph learning is an important research topic. This paper presents a practical solution to large-scale graph learning.\n2. The connection between the proposed method and graphical Lasso is discussed. Also, theoretical analysis on spectral criticality is provided.\n3. Overall the paper is well organized and clearly written. \n\nCons.\n1. My major concern is about the experiments. The authors claim that the proposed graph learning approach is highly scalable. It would be more convincing if the authors can evaluate the proposed method on larger datasets.\n2. One of the tasks in experiments is t-SNE visualization. There are also some faster versions of t-SNE with a complexity of O(NlogN), such as [a]. For t-SNE, the authors may justify what's the advantage of using the proposed method over other fast t-SNE algorithms.\n[a] Accelerating t-SNE using Tree-Based Algorithms, JMLR 2014.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "S1e5fAq6tS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a scalable approach for graph learning from data. At a high-level, it begins with a k-NN graph construction, then node features are embedded to spectral space (embedding to space spanned by eigenvectors of Laplacian). Next, edges that have a large distortion are additionally added to the latest graph. And these steps are repeated until the output graph is stable (i.e., the embedding distortion becomes small). Experimental result for spectral clustering shows that the proposed method can achieve the best accuracy compared to kNN-based methods. For graph recovery, the algorithm also performs better than other Laplacian-based graph learning methods. In addition, the proposed approach runs up to 5 times faster for t-SNE.\n\nThe authors demonstrate that their algorithm is scalable and faster than Laplacian-based methods requiring O(N^2). However, the proposed method also requires to compute eigenvectors of Laplacian thus it seems not to be faster compared to the previous algorithm. It would be better to provide the time complexity of each step in section 3.2 and that of the overall algorithm.\n\nIt is unclear that the proposed algorithm (section 3.2) is optimized the objective function in equation (9). And it is possible to theoretically guarantee that the algorithm finds a spectrally optimized graph?\n\nFor experiments, although the authors argue that the proposed algorithm is scalable, datasets that they used are not large-scale. And it is needed to provide runtimes of other algorithms for graph recovery tasks (section 4.2).\n\nOverall, this paper develops a new approach, but its novelty and intuition are unclear. Moreover, it does not seem to be scalable under the bar of acceptance. \n\nMinor concerns:\nThere is no content in section 3.2.5.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "HJx9csHQ5H", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper, the authors present a method that transforms data into graph. They emphasize on the fact that the proposed method is scalable, using a spectral embedding to construct the graph.\n\nWe think that the paper is not of enough quality to be accepted in ICLR. Without going in detail in the derivations, we give below some major issues in this submitted paper.\n\nThe studied problem has been widely investigated in the literature. Many methods have been proposed within the same objective, including taking care of the scalability issue. The authors fail to provide the state of the art, as well as describe the contributions with respect to previous work. As a consequence, the contributions are not clear. Maybe the proposed framework is original, but the there has been plenty of methods that have considered the same problem.\n\nExperiments are poor and not convincing. The authors compare the proposed method to only two spectral clustering methods, which as the standard kNN and the Consensus kNN from 2013. These two methods are pretty old and many more recent methods have been introduced in the literature. Moreover, the results in Table 1 are somehow misleading, as the standard kNN is faster that the proposed method on 3 out of 4 datasets. Experiments in graph recovery are not clear, starting from the fact that the datasets are not defined (what are the Gaussian graph and ER graph?), neither the experimental setting (what is the problem at hand?). The same goes to the application of t-SNE which is also very weak.\n\n--------------\nReply to Rebuttal \n\nThe authors have modified the paper to take into consideration our previous comments and suggestions. However, we think that it is still of not sufficient quality. We give below some elements, without providing a thorough review.\n\nIt is pretty pretentious to say that \"this is the first work that introduces a spectral method for learning ultra-sparse (tree-like) graphs from data\", while not comparing to the state of the art. There have been many spectral methods in graph learning for large-scale datasets.\n\nIn experiments, the only added method is the one of Kalofolias and Perraudin (submitted in 2017 to ArXiv). However, results show that this method is the worst of all methods. It is even the worst compared to the simple standard knn. It is not clear how the authors get such results; It looks like something is wrong in experiments, or they are cherrypicking.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper proposes a scalable approach for graph learning from data. The reviewers think the approach appears heuristic and it is not clear the algorithm is optimizing the proposed sparse graph recovery objective. 
Decision: Reject