Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposes to find the most reliable affinity matrix for clustering using Bayesian optimization and grid search. The reliability is measured using the relative eigen-gap of the graph laplacian. Additionaly, a clustering method based on least squares is presented.

The main argument for proposing the new methodology is that a method for generating the affinity matrix for spectral clustering is still an open problem. Especially when one considers the hyperparameter tuning involved. 
strengths_and_weaknesses: Strengths
- A new method for comparing the eigenvalues of the Laplacian of an affinity matrix could influence the direction of spectral clustering research. 
- The idea of direct comparison of different affinity matrix construction using grid search or bayesian optimization is interesting and could prove to be an efficient approach in real world clustering problems.
- The experiment section is extensive and shows that the method performs strongly. 

Weaknesses:
- The papers is perhaps lacking in focus. Several different contributions are packed into the same paper, and it is not too obvious why they belong together. This leads to a confusing presentation which is sometimes quite difficult to read. 
- The connection between the theoretical results and the contributions are not entirely clear in my opinion.
- The connection to current state of the art in clustering is somewhat lacking. It is fine to compare with similar methods of clustering (e.g. affinity based methods), but at least a mention of the best clustering method for the datasets used should be included.
questions: Is there any connection between the "AMC using Least Squares Representation with Thresholding" and the relative eigen-gap method?
limitations: The paper has many different contributions and lacks real focus. The relative eigengap could be focused more on, and with removal of some of the other parts of the paper, the proofs could have been included to give a complete representation.

The connection to relatex work is quite limited as far as I can tell.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper presents a simple yet effective method for automated spectral clustering. In specific, the authors propose to find the most reliable affinity matrix via grid search or Bayesian optimization among a set of candidates given by different AMC methods with different hyper-parameters. Then, they propose a fast and accurate AMC method based on least squares representation and thresholding and prove its effectiveness theoretically. Finally, they extend the method to large-scale datasets.
strengths_and_weaknesses: 1. The idea is interesting to build the affinity matrix of spectral clustering by modeling its eigenvalue distribution.
2. The authors provide rich theories about the proposed criterion and method.
3. The large-scale problem is also considered.

questions: 1. The second contribution is the proposal of Least Squares Representation (LSR) with Thresholding. However, LSR is commonly adopted in past decades and far from novel (Line 178 to 211).
2. The large-scale solution is fully shown in appendix with nothing in the manuscript. Please note that appendix is only a supplementary file to the manuscript. The readers have not responsibility to check out the appendix.
3. The manuscript format is out of order, such as Table 3.
4. From my opinion, the manuscript is not well organized. The authors want to emphasize Automated Spectral Clustering (AMC) which is imputed with a set of affinity matrices and outputs a selected one. So AMC is a process after the construction of affinity matrix (LSR in this paper). It means Section 4 is an application or showcase of the proposed method in section 3. But the authors pay a lot of attention on introducing LSR in section 4 and only leave a short sentence (line 195) to tell the connection between the two sections/points. This will easily confuse the reader. 
5. In the abstract, the authors claim that the runtime is less than 90s. This is meaningless, since no one knows the runtime is recorded from any settings (which cpu, gpu, etc. ?). Please use computational complexity instead.
6. In table 3, why the runtimes of baselines, such as SSC and LRR,  are longer than the proposed AutoSC-GD and AutoSC-BO. In common sense, AutoSC-GD and AutoSC-BO requires extra time to search the optimal affinity matrix, leading to a longer runtime.
7. LSR, a very important baseline, is missing in experiment. Since the proposed method is developed upon LSR. So it is crucial to compare them to validate your add-on (AMC).
8. The limitations are not mentioned.

In conclusion, the proposed idea is interesting but the manuscript is far from prepared, including expression, organization and experiment validation.

limitations: No
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper aims at automated spectral clustering. It has the following contributions: 1) it provided a relative eigen gap with some theoretical analysis for model and parameter selection in spectral clustering; 2) it proposed to use least square regression and truncation to obtain affinity matrices and showed that the method has subspace detection property; 3) it provided a method called NSE to improve the scalability of AutoSC on large datasets. Besides the theoretical analysis, the paper used extensive numerical results to show the effectiveness of the proposed methods. In general, the paper is interesting and easy to follow.
strengths_and_weaknesses: Strengths:

1. The paper is interesting and the problem here addressed is important for the machine learning community.
2. The overall approach is well described and seems novel.
3.  The proposed method works well on the evaluated datasets.

Weaknesses:
1. The notation in Section 3.3 can be improved.
2. Some important results (e.g. Theorem C.3) are in the supplementary material rather than in the main paper.
3. The authors only reported the clustering accuracy, it should be better to have more commonly used clustering metrics such as NMI and ARI.
4. The text in Figure 2(ii) is too tiny.

questions: In addition to the weaknesses mentioned above, it would be helpful if the authors could address the following questions.

1. In the current paper, the authors only studied the deterministic cases (e.g. Definition 4.3). A few previous works such as [Wang and Xu, 2013] and [Matsushima and Brbic, 2019] have studied the non-deterministic cases of subspace clustering. Is there any difficulty to provide some theoretical results for the non-deterministic cases?
2. Can the authors explain more about the meaning of $\gamma$ and $\beta$ defined in Definition 4.3? Is there any assumption about the noise? 
3. In Proposition 4.5, is reg(L)>0 necessary? 
4. In Figure 1(i), what does the green circle mean?
5. In Table 2, what’s the meaning of reg_max? In addition, it is not clear how the authors use ‘Polynomial kernel’ to construct the affinity matrix. The polynomial kernel may lead to negative values if the degree is odd.
6. In Table 3, AutoSC-BO is much slower than AutoSC-GD. The authors mentioned that they optimized all hyperparameters. What hyperparameters are? Please provide some details.
7. In Line 290, if NSE is ablated, what’s the accuracy of AutoSC-GD on the full MNIST?

limitations: The authors did not mention the limitation.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper proposes a method of automated spectral clustering that is able to adaptively select hyper-parameters for spectral clustering. Specifically, the authors first present an optimization metric called relative eigen-gap and then use Bayesian optimization to maximize the metric to find suitable models and hyper-parameters for spectral clustering. To improve the efficiency as well as the accuracy, the authors propose to use least squares representation with thresholding to construct the adjacency matrix and prove the effectiveness. The experiments show that the proposed method is able to outperform a few baselines such as SSC and BDR.
strengths_and_weaknesses: Strengths:
1. Model and hyper-parameter selection for unsupervised learning especially clustering is a challenging problem. Previous work on this problem is very limited. The paper provided a simple yet effective method, which is interesting and practical. The authors also proved the effectiveness of the relative-eigen-gap using Theorem 3.4.

2. The authors proved the effectiveness of least squares representation with thresholding in subspace (or manifold) detection, though least squares representation has been used in previous work of subspace clustering. To my knowledge, the theoretical results of Theorem 4.4 and Theorem C.3 look solid. They verified the roles of $\lambda$ and $\tau$.

3. The authors provided a novel method NSE for large-scale clustering.

4. The literature is sufficient and the related work has been clearly discussed.

5. The experiments were well designed and the results are plentiful. For instance, Figure 1 showed the impact of $\lambda$, $\tau$, and kernel in least squares representation. Table 2 compared different adjacency matrices and verified the connection between clustering accuracy and relative eigen-gap. Tables 4 and 5 demonstrated the effectiveness of the proposed methods in large-scale clustering.

In sum, the paper is well-written and has both theoretical guarantees and numerical verification. In my opinion, it solved a challenging problem in clustering.

Weaknesses:
1. Some notations (e.g. $\sigma_1,\sigma_2,\ldots$ in Table 1 and $L_s$ in Section 3.3) were not clearly explained.

2. It is not clear how efficient when AutoSC is applied to deep learning based clustering.

3. The conclusion section is a little bit short. Please provide more discussion.


questions: 1. In equation (4), the definition of $f_{\theta}$ is not very clear or intuitive. The authors may provide an example for $f$ and $\theta$.

2. It was claimed that the $\varepsilon$ in equation (6) is a small constant such as 1e-6. What if it is too big?

3. In line 154, J(L) is different from the one defined by (Meila and Shortreed 2006), unless $\alpha\leq 0$. In line 159, J(L) with $\alpha=0$ is just a special case of (Meila and Shortreed 2006). I guess it is a typo and should be $\alpha\leq 0$, according to Table 3 in the appendix. 

4. In line 175, the authors claimed that the DSC [Ji et al., 2017] method can be incorporated into the proposed AutoSC-BO. Do the authors mean that we can update the hyperparameter $\lambda$ of DSC using AutoSC-BO? How about the network structure and learning rate? I think it would be very time-consuming when inserting DSC into AutoSC-BO.

5. In Theorem 4.4, it seems that $\lambda$ does not exist if $2\mu d\leq \Delta$. The authors may provide more explanation for this.

6. In Tables 4 and 5, did the authors use the same NSE network structure for different datasets? If not, one may worry that NSE increases the difficulty of model and hyper-parameter selection in clustering.

limitations: None
review_title: null

Meta-review: metareview: The paper considers the problem of the choice of affinity matrix and associated hyperparameters for spectral clustering. The main contributions are a notion of relative eigen-gap to measure the quality of a clustering, the use of least squares representation with thresholding to construct the affinity matrix, and a novel method for large scale clustering. Extensive numerical results show the effectiveness of the proposed methods. In sum the paper provides an effective approach to automated hyperparameter selection for affinity-based spectral clustering.
confidence: Less certain
Decision: Accept