Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 1: Reject
review_content: 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.

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

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

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

--------------
Reply to Rebuttal 

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

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

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

review_title: Official Blind Review #2

final_score: rating: 6: Weak Accept
review_content: 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.

Pros.
1. Scalable graph learning is an important research topic. This paper presents a practical solution to large-scale graph learning.
2. The connection between the proposed method and graphical Lasso is discussed. Also, theoretical analysis on spectral criticality is provided.
3. Overall the paper is well organized and clearly written. 

Cons.
1. 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.
2. 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.
[a] Accelerating t-SNE using Tree-Based Algorithms, JMLR 2014.
review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: 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.

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

It 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?

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

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

Minor concerns:
There is no content in section 3.2.5.

review_title: Official Blind Review #3

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