A Simple Approach to Automated Spectral Clustering
Authors: Jicong Fan
Yiheng Tu
Zhao Zhang
Mingbo Zhao
Haijun Zhang
Venue: NeurIPS 2022 Accept (2022)

Abstract: The performance of spectral clustering heavily relies on the quality of affinity matrix. A variety of affinity-matrix-construction (AMC) methods have been proposed but they have hyperparameters to determine beforehand, which requires strong experience and leads to difficulty in real applications, especially when the inter-cluster similarity is high and/or the dataset is large.  In addition, we often need to choose different AMC methods for different datasets, which still depends on experience. To solve these two challenging problems,  in this paper, we present a simple yet effective method for automated spectral clustering. First, we 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 hyperparameters, where the reliability is quantified by the \textit{relative-eigen-gap} of graph Laplacian introduced in this paper. Second, we propose a fast and accurate AMC method based on least squares representation and thresholding and prove its effectiveness theoretically.  Finally, we provide a large-scale extension for the automated spectral clustering method, of which the time complexity is linear with the number of data points. Extensive experiments of natural image clustering show that our method is more versatile, accurate, and efficient than baseline methods.

A Simple Approach to Automated Spectral Clustering
Jicong Fan Yiheng Tu Zhao Zhang'; Mingbo Zhao", Haijun Zhang'
'The Chinese University of Hong Kong, Shenzhen SShenzhen Research Institute Big Data
3 CChnese Academy of Science, Beijing *University of Chinese Academy of Sciences, Beijing Heeei University of Techhology, Hefei DDonghua University, Shanghai HHrbiin Institute of Technology, Shenzhen
fanjicongêcuhk. edu. yihengtu@gmall mzhao4@dhu, edw.eddduuueuuu...e. cn hjzhang@hit.edd edu.tedduuucc cn
cszzhang@gmail
Abstract
The performance of spectral clustering heavily relies on the quality of affinity matrix. A variety of sannittymaarxx-consttttttii (AMC) methods have been pro- posed but they have hyperparameters to determine beforehand, which requires strong experience and leads to difficulty in real applications. especially when the inter-cluster similarity is high and/or the dataset is large. In addition, we often need to choose different AMC methods for different datasets, which still depends on experience. To solve these two challenging problems, in this paper, we present simple yet effective method for automated spectral clustering. First, we propose to find the most reliable affinity matrix via grid search or Bayesian optimization among set of candidates given by different AMC methods with different hyper- parameters, where the reliability is quantified by the relative-eigen- gap of graph Laplacian introduced in this paper. Second, we propose fast and accurate AMC method based on least squares representation and thresholding and prove its ef- fectiveness theoretically. Finally, we provide a large-scale extension for the auto- mated spectral clustering method, of which the time complexity is linear with the number of data points. Extensive experiments of natural image clustering show that our method is more versatile, accurate, and efficient than baseline methods.
Introduction
Clustering is an important approach to data mining and knowledge discovery. Particularly, spectral clustering [Weiss] 1999) Shi and Malik 22000, Ng et at.) 2002] Von Luxburg. [007] has superior
performance than k-means clustering [Steinhaus and others 1956). hierarchical clustering [Johnson] 1967]. DBSCAN [Ester al. 1996). and mixtures of probabilistic principal component analyzers Tipping and Bishop 1999] in many applications. Roughly speaking, spectral clustering consists of two steps: 1) construct affinity matrix in which each element denotes the similarity between two data points; 2) perform normalized cut [Shi and Malik 2000) on the graph corresponding to the affinity matrix. K-nearest neighbors (K-NN) and Gaussian kernel k= y) exp(-Ilæ: - p2l3/(2x²)) are two popular methods to construct affinity matrices, where & and < are hyperparameters.
As the performance of spectral clustering heavily relies the quality of affinity matrix, in recent years, a variety of methods have been proposed to construct or learn affinity matrices for spectral clustering. Many of them are in the framework of self-expressiv [Roweis and Saul FI0amiilaaiaa and Vidal 2013) model, i.c., minimizec 1 X XC + AR(C). Here the columns of X kmxx are the data points drawn from union of subspaces. E Raxx is a coefficient matrix. RCC)) denotes a regularization operator C. X is hyperparameter to be determined in advance.
"Correspondigg author
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Elhamifar and Vidal [0133] proposed to use R(C) = Giyl under a constraint
diag CJ = 0. In Elhamifar and Vidal 2013]. the affinity matrix for spectral clustering is given by
A = C CI The method is called Sparse Subspace Clustering (SSC). Some theoretical results
of SSC can be found in [Wang and Xu 2013: Soltanolkotabi et al. 2014].
Following the self-expressive framework, Liu et al. (0033) let R(C) ||]|| (nuclear norm of C) and proposed Low-Rank Representation (LRR) method for subspace clustering. [uu al. 2012
and Pan Ji et al. (2014) used the least squares representation (LSSR) model for subspace clu clustering.
A few variants of LRR and SSC can be found in PPtel and Vidal 2014 Li and Vidal 2015 Patel et
aa.] 2015 Shen and Li 2016 Li and Vidal 2016; Fan and Chow 2017 Fan et al.) 2018 Lu et al.
2018 Pan and Kang 2021 Kang et al. 2022]. Recently, deep learning methods were also used to
learn affinity matrices for spectral clustering jJi et al.) 2017, Zhang et al. 2019b a
Lv et al. 2021
and have achieved state-of-the of-the-art performance on many benchmark datasets.
One common limitation of these spectral or subspace clustering methods is that they have at least one hyperparameter to determine. In the codes of SSCP and its variants provided by their authors, there is usually one more thresholding parameter for affinity matrix, which affects the clustering accuracy lot. In the deep learning clustering methods such as (Ti et al.) 2017] and (Zhang el al.) (0T9h), we need to determine the network structures and regularization parameters, which is much more difficult. Since clustering an unsupervised learning problem, the hyperparameters cannot be tuned by cross-validation widely used in supervised learning. Thus we have to tune the hyperparameters in spectral clustering by experience, which difficult when the dataset is quite different from those in our experience and/or the inter-class similarity is high compared to the intra-clustes similarity. Note that SSC, LRR, and their kernel or deep learning extensions have quadratic or even cubic time complexity (per iteration), which further increases the difficulty of hyperparameter selection in clustering large datasets, though there have been a few works improving the computational efficiency
[Peng ef al. 20133 Cai and Chen 2014 Wang et al., 2014] Peng et al. 2013] You et al. [20 6a b Li
and Zhao [017]] ou ef al.) 2018 Matsushima and Brbie 2019]Li et al.) |020] [Cen ef al.) 2020)
Kang et al. |2200] Fan 202 Cai al.) 2022]. On the other hand, different datasets often require different AMC methods, which is hard to tackle by experience.
This paper aims at model and hyperparameter selection for spectral clustering and wants to improve the convenience, accuracy, and efficiency of spectral clustering. Our contributions are as follows.
We propose relative-eigen--aap based automated spectral clustering (AutoSC) method. It finds the Laplacian matrix with largest velative-eigen-ge among a set of candidates constructed by different models with different hyperparameters.
We also implement the AutoSC method via Bayesian optimization. The method can select the possibly best model and optimize the hyperparameters automatically. Note that any AMC methods (e.g. SSC) can be included in the framework of AutoSC.
To improve the accuracy and efficiency of AutoSC, propose a new AMC method based on least squares representation and thresholding and prove its effectiveness theoretically.
We provide an extension for AutoSC to cluster large-scale datasets.
Experiments on seven benchmark image datasets demonstrate the effectiveness of our method. Par- ticularly, our method outperforms state-of-the-art methods of large-scale clustering.
2 Related work
Exploiting cigenvalue information for clustering As the number of zero eigenvalues of Lapla- cian matrix is equal to the number of connected components of the graph [Von Luxburg 2007]. a few researchers took advantage of cigenvalue information in spectral clustering Meila et al. 2005
Meila and Shortreed] (2066] Di et al.) 2015 Hu et al.) [017] Lu et al.) 2018). .. For instance, Ji et al, [2015) utilized eigen-gap to determine the rank of the Shape Interaction Matrix. But the method requires determining another hyperparameter 7 beforehand and needs to perform spectral clustering multiple times. The methods of [Meila et al. 2005
Hu et al. 2017] Lu et al. 2018) are based on
Wang and Xu 2013 and Soltanolkotabi et al. 2014 provided lower and upper bounds for the À in SSC
theoretically, which however depend on the unknown noise level.

---

iterative optimization (need to perform eigenvalue decomposition at every iteration) and hence are effective handling large-scale datasets. In addition. the BDR method of [Lu et al, 2018 has two hyperparameters (X, ?) to determine by experience, although it outperformed SSC and LRR on some datasets. A comparison is shown in Figure
Automated machine learning Automated model and hyperparameter selection for supervised learnigg have been extensively studied [Hutter al. 2019]. In contrast, the study for unsuper- vised learning is very limited. The reason is that in unsupervised learning there is no ground truth or reliable metric to evaluate the performance of algorithms. Concurrently to our work, Poulakis [2020] also attempted to do automated clustering. Specifically, [Poulakis] (2020) proposed to use meta-lcarning to select clustering algorithm and use a heuristic combination of some clustering va- lidity metries such Silhouette coefficient (Liu et al. 2010] and S_Dbw (Halkidi and Vazirgiannis 2001] as an objective to maximize via grid search or Bayesian optimization [Jones et al. 1998]. One problem is that these metrics are mainly based on Euclidean distance densities and hence may not be suitable to evaluate the clustering performance of non-distance or non-density based clustering algorithms. Another one is that there is unified metric to compare different clustering algorithms.
3 Automated Spectral Clustering (AutoSC)
3.1 Preliminary Knowledge
Let A Rax= be affinity matrix constructed from given data matrix X E R The corresponding graph is denoted by G = E), where V = {vi,.... Up is the vertex set and E = (ei,...,er] e is the edge The degree matrix of graph G is defined D diag( A1), where == Let = 1IT Our goal is to partition the vertices into k disjoint nonempty subsets CI....,C, Ca. is expected to find a partition that minimizes the following metric.
Definition 3.1 (MNCut). The multiway normalized cut (MNCut) MMeila 2001 is defined as
Cut(Cr, C2) Vol(C,)
MNCut(C) Σ
where Cut Cj) = Enec. Evec, Aur and Vol(C,) denotes the sum of vertex degrees of C..
The normalized graph Laplacian matrix is defined as
- D 1/2 AD 1/2
where is an identity matrix. The normalized graph Laplacian is often more effective than the unnormalized one in spectral clustering (some theoretical justification was given by (Von Luxburg 2007D. Let o, (L) 1) be the i-th smallest eigenvalue of L. The following claim shows the connection between MNCut(C) and L.
Claim 3.2. The sum of the k smallest singular values of L quantifies the potential connectivity among CI....,C,, Cy: MNCut(C) 2 (L).
The claim can be easily proved by using Lemma of Meila 2001]. We defer all proof of this paper the appendices. Because the multiplicity A: of the eigenvalue 0 of L equals the number of connected components in G [Von Luxburg 2007). we expect to construct an affin- ity matrix A from X such that L has k zero eigenvalues. Thus the optimal partition means MNCut(C) = Σ o
3.2 Relative Eigen-Gap Guided Search
In practice, we may construct an A such that Σ (L) as small as possible because guar- anteeing zero eigenvalues is difficult. But this is not enough because L may have le + 1 or more very small or even zero eigenvalues. The second smallest eigenvalue of the Laplacian matrix of graph G is called the algebraic connectivity of G (denoted by ac(G)) [Fiedler 1973). We have ae(G) = and only if G not connected. When has & disjointed components, there are ac(C))) Based on this, we have
algebraic connectivitics, denoted by
3

---

Claim 3.3. The 1+1 smallest eigenvalue of L quantifies the least potential connectivity of parti- tions Cr...., C, of C:
min MNCut(Ci) 2 (I))(L).
1SiSk
In other words, 0k++1 (L) measures the difficulty in segmenting each C; into two subsets. Hence, when (Z) is large, the partitions C1...., Ck are stable. Based on Claim 3.2 and Claim we
may construct an A that has small Σ (L( and large r simultaneously, by solving
1
maximize 1
(L))
0
h: i=1
(4)
subject to L - 1/2 AD 1/2 A = fx())
where fo Rmmx + R=** is function with parameter 9, e.g. A = |exp(- ( 11, - 12/((2)))
It difficult to solve 44) because of the composition of fe. symmetric normalized Laplacian, and eigenvalue decomposition. On the other hand, in (4), we have to choose f in advance, which requires domain expertise or strong experience because different dataset usually needs different f.
Note that different/ f can result in very different distributions of eigenvalues and the small eigenval- ues are sensitive f, 0, and noise. Hence the objective in ( is not effective to compared different f and 0. In this paper, we define new metric relative-eigen--ee gap as follows
reg(L) = Ok+1(L) Σ (L) k. (D)
(5)
where is small constant (e.g. 10-6) avoid zero denominator: reg L) is not sensitive to the scale of the small eigenvalues. Therefore, instead of (4) we propose to solve
maximize reg(L), (f.))Fxx
(6)
subject to --I-D-1/2 10-1//A-22 1/2 A = fo()),
where F is set of pre-defined functions and θ is set of hyperparameters. In fact, (6 is equivalent to choosing one A (or L) from set of candidates constructed by different f with different 0, of which the relative-eigen-gap largest. The best 0 can be found using grid search (or even random search). For convenience, we call the method AutoSC-GD. Table shoows a few examples of f and its parameters. One may use weighted sum of affinity matrices given by different f, like (Huang et al. 2012]. which however will introduce more hyperparameters.
Table 1: A few examples of f and its 0 for AMC (AASC: K-NN c-neighborhood Gaussian kernel K
(Huang et al. LSR
2012)
SSC
LRR
KSSC
AASC 01. .....
A X
X
A.
The following theorem Secorremshorr shows the connection between reg( [) and the stability of the clustering C.
Theorem 3.4. Let C and C' be two partitions of the vertices of G, where |C] = C'I = k. De-
( Sup- fine the distance between C. and C' as dist(C, C") = 1111- Eciec Ecyeer Volcy.Vol
pose Tike 2 o(L) 2 ke and reg(L) (k- 1)n/2. Let 8 max (MNCut(C)
Σ I MNC,))))) -kh , Then
dist(C,C') <
1.56e reg( (1-kk/
It indicates that when reg(D) L) is large and 8 is small, the partitions C and C' are close to each other. Thus, the clustering has high stability. When Σt (L ka, we have dist(C, C')
68
which means the larger a (L) the more stable clustering.
This theorem is a modified version of Theorem 1 in Meila et al. 2005 which is for the eigen-gap d% of L. Here consider reg( L) instead.

---

Compare reg(D) L) with Meela and Shortreed 2006 It is worth noting that Meila and Shortreed
(2006) proposed minimize J(L) == Σ o,(L) (L) a ( ok)) find good affin- ity matrix for spectral clustering. Although reg L)) and J(L) seem similar, they are essentially different. As mentioned before, different AMC methods may lead to different scales for the small eigenvalues, which makes it difficult to compare different AMC methods using J().. In addition. () has hyperparameter a determine beforehand, which violates our goal of searching models and hyperparameters. A comparative study (a S 0) is in Section 4.1 (Table 3).
3.3 AutoSC via Bayesian Optimization
Bayesian optimization (BO) (Jones al. 1998 has become promising tool for hyperparameter optimization of supervised machine learning algorithms [Snoek et al.) 2012 Klein et al. [017]] Given black-box function g X' R. BO aims to find an x E X that globally minimizes g and usually has three steps. The first step is finding the most promising point 2 E arggax (p(g) (a) by numerical optimization, where dp(g) X + R is acquisition function (e.g. Expected Im- provement) relying on prior p(g) (c.g. Gaussian processes [Williams and Rasmussen, 2006 The second step evaluating the expensive and possibly noisy function V/+1 ~ g(x) + (0, o and adding the new sample (æt+1, V1+1) to the observation set D, {((11, (1)1,,)))--.0 y.),.... (zt, ye) The last step is updating p(g) and Ap(n) using Dz+1-
As an alternative to the grid search for (6). we can maximize reg( via BO. Suppose we have set M. let
of different AMC models, i.e., F = {f1, far....fa For i =
( reg(L X)))
where ((() denotes the hyperparameters in f, and X denotes the dataset. Then we use BO find
argmin ()(%))
(8)
gt0) g
where S19 denotes the set of constraints. Finally we get the best model with its best hyperparameters
fa (a x), where *
argmin gi (0!)).
For convenience, we denote the method by AutoSC-BO -B.. Note that F can include any AMC methods such those in Table [ and even DSC [Ji et al. 2017 (see Appendix(D.3
In AutoSC-BO, we use Expected Improvement (EI) acquisition function
agr(s s D.) Ep [max(gmin g(s), 0)],
(10)
where Jmin is the best function value known. The closed-form formulation
a D.) = (gmin =) 9min - /1 +
9min - /1
(11)
σ
where μ Dr, 0x) and
(s D., 0K) are the mean value and variance of the Gaussian process, Φ and d are standard Gaussian cumulative density function and probability density func- tion respectively, and 0x denotes the hyperparameters of the Gaussian process. For the covariance function, we use the automatic relevance determination (ARD) Matérn 5/2 kernel Matémn 2013
(M,2(8, -6 (+ V (r 3
5 )((( x exp (-Vor?(s,s)))
(12)
where (3, = (s - - 5//22/03.
3.4 Discussion on AMC Methods for AutoSC and LSR with Thresholding
In AutoSC, the size of searching space is |F x II, [yyl. which should be large enough to include effective models and their hyperparameters. A large number of works have shown that the self- expressive models [llaamifar and Vidal 2013 Liu el af.) 2013) [u el al. 2018 [i al. (017]] often outperform other AMC models such Gaussian kernel. However, the exffeexpressive model based
5

---

AMC methods often require iterative optimization and has at least quadratic time complexity per iteration, which leads to huge time cost AutoSC. Although LSR (Lu et al. [012] has closed-form solution, the clustering accuracy is not satisfactory (Luu el al. [2018] In this work, we will show that
LSR with a simple post-processing operation can be a good AMC method and can outperform SSC, LRR, and BDR (Lu et al. 2018). Specifically, the LSR model is given as
minimize
|||
XCI
+ IC
(13)
-1 x X. Let diag(C) 0 and C - |C|, the affinity matrix can be constructed as A (C 1/2 One problem is that the off-diagonal elements of A are dense (leading to connected graph), which can result in low clustering accuracy. Therefore, we propose to truncate C by keeping only the largest r elements of each column of C. Nevertheless, it is not easy to determine T beforehand. When is too small, the corresponding graph will have k + 1 or more connected components. When T is too large, the corresponding graph will have k- - or less connected components. However, can be automatically determined by our AutoSC-GD and AutoSC-BO.
of which the closed-form solution C = (X -
In the case that the data have some low-dimensional nonlinear structures, the similarity between pair-wise columns of X cannot be well recognized by the linear regression (l3) Therefore, we also consider the following nonlinear regression model
minimize
1 ) (X)) IIC
(14)
where & denotes a nonlinear feature map performed each column of the matrix, i.e. 6(X)
(é(x)),.... <(x,)). )]. In (14). letting & be some feature map induced by a kernel function k(,,)) (e.g.
polynomial kernel k( xzy) = (a: By + 6)s and Gaussian kernel), we get the kernel LSR (KLSR):
minimize Tr (K 2KC C KC) + IIC
(15)
where K = 6(X) Tx and [] k(x,, x))). The closed-form solution is C = (K+ -1 K. The post-processing is the same as that for the solution of L.RR.
(XX)
We introduce the following property, a necessary condition of successful subspace clustering, which is similar to the one used in [aang and Xu 2013; Soltanolkotabi et al. 20144.
Definition 3.5 (Subspace Detection Property). A symmetric affinity matrix A obtained from X has subspace detection property if for all the nonzero elements of a, correspond to the columns of X in the same subspace as W4
For convenience, let (i) be the index of the subspace æ; belongs to and C, be the index set of the columns of X in subspace We consider the following deterministic model.
Definition 3.6 (Deterministic Model). The columns of X E Rmxx are drawn from a union of k different subspaces and are further corrupted by noise, where dim(S; U .... U Sx) = < m S n. diag(o)..... on) and 0 2 02 2 on Let
Let X UEVT be the SVD of X, where / Denote v; = (W/1..... Vin)) the i-th row of V and let 0; (Ei,.... Pia). Suppose
the following conditions hold 1) for every i E [n]. the 7-th largest element of {10, 0, :. E Cz(1)
greater than a; 2) max4e(x) maxje(nl\Crca j0 05 < 3) max |Rares S μ.
Then the following theorem verifies the effectiveness of 13 followed by the truncation (threshold- ing) operation in subspace detection.
Theorem 3.7. Suppose X is given by Definition 3.6 and C is given by 13 with
(p- Vo- 4(2pd A)(2pm 2pd A) 2))aa
(otVez 4[2ad () Bnd -1)
(16)
4pd
4nd 22
where p = 2pm-?? detection property.
A(1 + +2) and A = a - B. Then the C truncated by T S T has the subspace
'y measures the noise level, B is dominated by the difference between subspaces, and quantifies the incoherence in the singular vectors.

---

In Theorem 3.7 the width of the range of À is UP--1(2ud 21ppmm Ajo We see that
2
larger dd A, smaller y, d leads to wider range of X, which corresponds
simper clustering
problem. When p² v 4(2yd= - 2pd - A), À does not exist. Theorem 3.7 can be extended to the kernel case 15 without the restriction of d <, m even when the columns of X are drawn from
a union of nonlinear low-dimensional manifolds. See Definition C.T Definition C.2 and Theorem
Appendix [ Based on Theorem 3.7 and Theorem C.3
the follow proposition indicates that
AutoSC can cluster the data correctly.
Proposition 3.8. Suppose the affinity matrix A given by AutoSC has the subspace or manifold
detection property (defined in Appendix C and reg(L) _k-1 > 0. Then each component of G consists of all columns of X in the same subspace or manifold.
Now that LSR and KLSR with thresholding can provide effective self-expressive affinity matrices for AutoSC without performing iterative optimization. On the other hand, the relative- eigen-gap is able to compare LSR with KLSR, compare different kernels, and evaluate X, т, and kernel parameters. Note that we use SSC and KSSC instead of LSR and KLSR, AutoSC will be very cone-consumnng If we use LSR and KLSR without thresholding, AutoSC may not provide high clustering accuracy. We hope that AutoSC is not only automatic but also accurate and efficient.
3.5 AutoSC+NSE for Large-Scale Data
Since the time and space complexity of AutoSC are quadratic with it cannot be directly applied to large-scale datasets. To solve the problem, we propose to perform Algorithm | on a set of s landmarks of the data (denoted by X) to get a Ž. The landmarks can be generated by k-means or randomly. Then we regard Z as a feature matrix and learn a map Rm + R from X to 2. According to the universal approximation theorem [Sonoda and Murata 2017 of neural networks, we approximate by a two-layer neural network and solve
2 WzReLU(W; X +b11,) 1 ? (1111 W2ll))) (17)
minimize
Wi.Wabb.bbz b2 2s
where W1 E Rd W2 E Rxd by E Rd and b2 E RR.. Since A is sparse, & is often less than m, and neural network is used, call (17) Neural Sparse Embedding (NSE). We mini-batch Adam Kingma and Ba 2014] to solve NSE, It is worth noting that NSE is different the method proposed by [Li el al. 2020). In (Li el al. 2020), the regression is for an affinity matrix, which leads to high computational cost. The network learned from 17 is applied to X to extract a k- dimensional feature matrix Z:
Z = 0(X) W5ReLU + +,,,,) b,1
(18)
Finally, we perform k-means on Z to get the clusters. The procedures are summarized into Algo- rithm 2 (see Appendix B) Note that the time complexity of AutoSC#NSE is O(dmn + ds?), where depends on the specific AMC method. When < n. the time complexity of AutoSC+NSE is lin- ear with the number of data points n. Proposition C.4 Appendix C.2 shows that a small number of hidden nodes in NSE are sufficient to make the clustering succeed.
4 Experiments
We test our AutoSC on Extended Yale B Face (Kuang-Chih el af.) 2005), ORL Face Samaria and Harter 1994]. COIL.20 (Nene el al.) 1996). AR Face [Martinez and Kak 200T]. MNIST LeCun et al. 1998). Mushion-MNISY [Xiao et al. 2017). GTSRB [Stalkammp er al. [0122]. sub- sets and extracted features of MNIST and MaSH. The descriptions for the datasets are
in Appendix D.I Our MATLAB codes are available at /https://gitae //gg: http:/gttttcoo//..oeee com/jicongfan/
4.1 Intuitive validation of AutoSC
Performance Gaan First, we use LSS and KLSS to show the effectiveness of the proposed reg reg(L). Figure 1 (i) shows an intuitive example of the performance of LSR and KLSR
7

---

in clustering a subset of the Extended Yale B database, where for [15) we use Gaussian kernel with < nº Eij ||=; - T,ll- We see that: 1) LSR and KLSR, for a fixed (or 7), the (or A) with larger reg (L) provides higher clustering accuracy; 2) for a fixed À and a fixed т, if LSR has a larger reg( L). its clustering accuracy is higher than that of KLSR, and vice versa. We conclude that roughly a larger (L) indeed leads to a higher clustering accuracy, which is consistent with our theoretical analysis in Section 3.2
(A.0.01)
(1:0.11
01-11
0.8
0.8
0.8
0.4
0.4
0.4
90
0.0
0.2
0.2
03
5
5
12 15
9
11
13
10
LIFT
LAR 2.250 00 1000
00-
Clynering a000 moyy
KLSR 0.-0.01)
KL5R(4-211
KL55 p-11
(ii) Clustering accuracies of SSC, LRR, and BDR- with different hyperparameter in comparison to AutoSC-GD with LSR and KLSR on the Extended Yale Face B database. The value of À used in BDR- B has been divided by 10. The in BDR-B -RR-Bl is cho- from {0.01, 0.1, } and the best each X. Case (h), the time costs of SSC, LRR, BDR-B, and AutoSC-GD are 9.5s, 33.0s, 7.6s, and 1.6s respectively.
0.6
0.0
0.4
0.4
0.4
0.
is used for
(i) Clustering accuracy and reg( L) (rescaled between 0 and 1) and clustering accuracy of LSR and KLSR on the first subjects of the Extended Yale Face B database.
Figure 1: Examples about reg(L), ()). clustering accuracy, and hyperparameters on Extended Yale B.
Now we show the superiority LSR and KLSR compared to few important AMC methods. Figure Tii) shows the clustering accuracy of SSC [Elhamifar and Vidal 2013). LRR (Liu et al. 2013). 3) and BDR-B [Lu et al. 2018)] with different hyperparameters and our method Auto-GD with LSR and KLSR (detailed by Algorithm in the supplementary material) on the Extended Yale Face B subset. SSC and BDR-B are sensitive the value of X, especially for the relatively difficult task, say Figure ii-b). LRR is not sensitive to the value of À but its accuracy is low. LSR and KLSR are more accurate and efficient than other methods.
The performance of AutoSC-BO We show the performance of AutoSC-BO with many AMC methods such as SSC [Elhamifar and Vidal 2013) and LSR, Taking the KLSR model (15) with
polynomial kernel as an example, the parameters are 0 = (2, and the constraints are given
by S = {> E R Amin < X < Amazi b E R 4mnn < < Umazi
2+ Qmin < S
amazi T Zz Tmin TTS Tmar): More details are in Appendix D.5 Shown Table 2 larger
reg corresponds to higher clustering accuracy and KLSR with polynomial kernel (the optimal is 1)
performs best. Figure Shouss shows the performance of KSSC (Patel and Vidal 2014) and KLSR each iteration of AutoSC-BO.
Table 2: Clustering accuracy of AutoSC-BO with many methods on Yale Face B dataset (first 10
subjects). All hyperparameters of the kernel functions were optimized via Bayesian optimization.
e-ncigh
Polynomial
Gaussian
KSSC
KSSC
KLSR
KLSR
AMC
borhood
kernel
kemel
(Gauss)
(Poly)
(Gauss)
(Poly)
regmax
0.776
1.294
1.307
0.892
1.388
2.217
2.379
Accuracy
0.325
0.389
0.393
0.584
0.859
0.963
0.966
Relative-Eigen-Gap versus Eigen-Gap We compare the proposed relative-eigen gap (reg( L)) with eigen-gap (denoted by eg(L)), and the regularizer J(L, a) proposed by [Meila and Shortreed, 2006) with different a. Note that in AutoSC, we need to minimize (LL, a:) instead. The clustering results of AutoSC-GD are reported in Table 3 (details about the datasets are Section 4 We see that our LL) outperforms eL) and [L, a) in all cases except AR.
8

---

KLBP Counsion
28
-440
0.2
22
0.
3.4
10
20
50
50
20
30
2.5
2.5
MMM
Am
1.5
0000
(i) reg L) and clustering accuracy of KLSR and KSSC each iteration of BO.
(ii) reg L) and hyperparameters of KLSR and KSSC each iteration of BO.
Figure 2: AutoSC-BO with KSSC and KLSR on the first 10 subjects of YaleB Face dataset.
Table 3: The comparison AutoSC-GD with reg L). eg LL. and J(L, a)
YaleB
ORL
COIL20
AR
MNIST
F-NNIST
eg(L]
0.790
0.768
0.619
0.805
0.663
0.562
J[L, 0)
0.823
0.795
0.750
0.804
0.726
0,516
J(L, -0.1)
0.818
0.788
0.768
0.826
0.718
0.519
-1L
0.812
0.785
0.769
0.817
0.722
0.523
J[L,
0.804
0.788
0.768
0.832
0.731
0.539
J[L 100)
0.788
0.765
0.769
0.817
0.735
0.545
reg (L)
0.897
0.795
0.782
0.786
0.755
0.595
4.2
Comparative studies of AutoSC and baselines
First compare AutoSC with SSC, LRR [Liu al. 2013 LSR (Lu al. 2012]. EDSC PPan
Ji et af.) 2014), KSSC, SSC-OMP You el al., 2016b). BDR-Z [Lu et al.) 2018). and BDR-B Lu al. 2018 six smaller datasets. The clustering accuracy and time ble 4 AutoSC-GD and AutoSC-BO outperformed other methods significantly in almost all cases.
reported in Ta-
SSC-OMP and AutoSC-GD are more efficient than SSC, LRR, EDSC, and KSSC, The time cost of AutoSC-BO is much higher than that of AutoSC-GD because the former optimizes all hyperparam- eters including x, T, and kernel parameters (e.g. b, q).
Table Clustering performance on the six small datasets. For the MNIST-IK and Fahsion-MNIS, Ik. we report the average results of 20 trials because the subset is formed randomly. AutoSC chose LSR for Yale and AR and chose KLSR for others datasets. The NMI results are in Table 7 (See Appendix D.3
SSC
LRR
LSR
EDSC
KSSC
SSC-OMP
BDR-Z
BDR-B AutoSC-GD AutoSC-BO
0.723
0.643
0.592
0.806
0.649
0.768
0.596
0.719
0.897
0.909
Yale
time
273.8
928.1
7.3
58.6
464.3
368.8
368.8
78.3
ORL
acc
0.711
0.762
0.680
0.712
0.707
0.665
0,739
0.735
0.795
0,803
time
2.7
8.8
0.5
2.0
2.6
0.4
3,9
3.9
2.3
20.5
COIL20
acc
0.871
0.729
0.695
0.759
0.912
0.658
0.713
0.791
0.782
0.878
time
61.8
221.2
1.4
15.4
100.6
86.8
86.8
7.6
39.2
acc 0.718
0.769
0.665
0.673
0.726
0.669
0.745
0.751
0.786
0.826
time
317.5
1220.6
14.5
69.1
627.4
57.6
578.7
578.7
43.4
130.6
0.596
0.513
0.554
0.536
0.577
0.542
0.576
0.578
0.615
0.619
MNIST
acc
(0.054)
(0.037)
(0.041)
(0.035)
(0.053)
(0.038)
(0.037)
(0.043)
(0.041)
(0.038)
-1k
time
24.9
69.1
0.8
5.2
32.8
1.3
26,9
26.9
2.5
21.7
0.553
0.515
0.563
0.544
0.548
0.566
0.574
0.563
0.581
0.584
Fashion- MNIST-IK
acc
(0.025)
(0.014)
(0.023)
(0.017)
(0.016)
(0.034)
(0.019)
(0.031)
(0.025)
(0.021)
time
24.1
68.5
0.7
5.1
35,9
1.2
25.7
25.7
2.6
22.7

---

We compare our method with LSR, LSC-K [Chen and Cai 2011 OMC- You et al. 2016b), and S*C Mattssshim and Brbic 2019 and C'MMP-CC Chen et al. 2020 on the larger datasets. The parameter settings are in Appendix D.6 Table 5 shows the clustering accuracy and standard deviation of 10 repeated trials on the raw-pixel data of MNIST and Mashion-MNIST. fable6sshows the results on MNIST and FasHion-MNIST features and GTSRB. Our methods have the highest clustering accuracy in every case, Note that if NSE is ablated, the accuracy of AutoSC-GD on MNIST(features)) -O0,, -20k, and -30k are 0.9772, 0.9783 and 0.9864 respectively, higher than those of AutoSC-GD++NE, though the time costs increased.
It is worth mentioning that, to the best of our knowledge, the deep clustering method of (Zhang et al., 2019a] has SOTA performance on Yale B (acc=0.98) and ORL (acc=0.89), the method proposed by [Zhang et al. 2019b] has SOTA performance on Fashion-MNIST (uc)= the method proposed by [Mahon and Lukasiewiez. 2021] has SOTA performance on MNIST (acc=0,99) and our method has SOTA performance on GTSRB. Nevertheless, we focus on automated spectral clustering.
Table 5: Clustering accuracy and time cost (second) on MNIST and Fashion MNIST. " means the computation is out of memory.
LSR
LSC-K
SSC OMP
SCC
C'COMP
AutoSC GD+NSE
AutoSC BO+NSE
acc 0.583(0.0U7)
0.652(0.037)
0.33(00.14)
0.6160000045
0.623(0.028)
0.687(0.035)
0.67900.03)
MNIST- 10k
lime
154.9
18.9
26.4
82.3
710.4/20
16.2
48,3
MNIST
900
0.665(0.021)
045300017)
0.627(0.025)
0.755(0.022)
0.750K0.009)
time
329.2
1178.3
961.5
86,9
123.6
Fashion-
acc
(0.00))
0.571(0.0255
0.509(0.038)
0.565(0.021)
0.569(0.024)
0.576(0.01 I)
0.572(0.019)
MNIST- 10k
time
107.3
707.2/20
Fashion-
0.561(0.015)
0.359(0.017)
0.559(0.013)
0.586(0.008)
0.578(0.012)
MNIST
time
335.1
1156.6
932.6
88.7
122.8
Table 6: Clustering accuracy (mean value and standard deviation) and time cost (second) on MNIST and Mashion-MNIST with feature extraction. "I" means the algorithm was performed on a computa- tional platform not comparable to ours. The underlined values are from (Chen et al. 2020].
LSC-K
SSC-OMP
C
COMMPCC
AuboSC-GD-NSE
AstoSC-BO-NS
MNIST
acc 0.8659(002115)
0,8159
0.7829/0.0283)
0,9632
(.9775(0.0033)
0.974100.0044)
time
273.6
280.6
907.5
4168
59.2
115.3
Fashion- MNIST
800
0.6131(0.0298)
0.3 (.3796(0.0217)
(0.057)
0.639%(00133)
0.4661000104)
time
251.8
1013.9
913.2
GTSRB
a0c
0.87 (88711000810)
0,2222
0,90440002667
0.9544
(..873000026)
O. (.88(000088)
time
31.2
98.7
16.8
69.4
5
Conclusion
We have proposed automated spectral clustering method. Extensive experiments showed the ef- fectiveness and superiority of our methods over baseline methods. The efficiency improvement is from the doosed-oorm solutions of the least squares regressions. The accuracy improvement is from the effectiveness of LSR and KLSR with thresholding and the automation of model and hyperparam- eter selection. One limitation of this work is that we only considered automated spectral clustering while there are many other clustering methods (c.g. Fan 202l]) not relying on affinity matrix.
Acknowledgments
The work of Jicong Fan was supported in part by the Youth program 6210621 of the National Nat- ural Science Foundation of China and the research funding T001202 of Shenzhen Research Institute of Big Data. The work of Yiheng Tu was supported in part by the National Natural Science Foundation of China under Grant no. 32171078. The work of Zhao Zhang was supported in part by the National Natural Science Foundation of China under Grant no. 62072151 and Anhui Provincial Natural Science Fund for the Distinguished Young Scholars (2008085130). The work of Mingbo Zhao supported in part by the National Natural Science Foundation of China under Grant 61971121. The work of Haijun Zhang was supported in part by the National Natural Science Foun- dation of China under Grant no. 619721 12 and no. 61832004, the Guangdong Basic and Applied Basic Research Foundation under Grant no. 2021B 0021B1515022 1115020088.
The authors appreciate the reviewers' comments and time.
10

---

References
Stephen Boyd, Neal Parikh, Eric Chu, Borja Pelcato, and Jonathan Eckstein. Distributed optimiza- tion and statistical learning via the alternating direction method of multipliers. Found. Trends Mach. Learn. 3(1):1-122, 2011.
Joan Bruna and Stéphane Mallat, Invariant scattering convolution networks. IEEE transactions on pattern analysis and machine intelligence, 35(8):1872-1888) 2013.
Deng Cai and Xinlei Chen. Large scale spectral clustering via landmark landmark-based sparse representation.
IEEE transactions on cybernetics, 45(8):1669-1680, 2014.
Jinyu Cai, Jicong Fan, Wenzhong Guo, Shiping Wang, Yunhe Zhang, and Zhao Zhang. Efficient deep embedded subspace clustering. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR), pages 1-10, June 2022.
Xinlei Chen and Deng Cai. Large scale spectral clustering with landmark-bar -based representation. In Tweety-fifth AAAI conference artificial intelligence. Citeseer, 2011.
Ying Chen, Chum-Guame Li, and Chong You. Stochastic sparse subspace clustering. In Proceedings of the IEEF/CVF Conference on Computer Vision and Pattern Recognition, pages 4155-4164, 2020.
E. Elhamifar and R. Vidal. Sparse subspace clustering: Algorithm, theory, and applications. IEEE Transactions on Pultern Analysis and Machine Intelligence, 35(11):2765-2788 2013.
Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu, et al. A density-based algorithm for discovering clusters in large spatial databases with noise. In kdd, volume 96, pages 226-231, 1996.
Jicong Fan and Tommy W.S. Chow. Sparse subspace clustering for data with missing entries and high-rank matrix completion. Neural Networks, 93:36-44, 2017.
Jicong Fan, Zhaoyang Tian, Mingbo Zhao, and Tommy W.S. Chow. Accelerated low-rank repre- sentation for subspace clustering and semi-supervised classification on large-scale data. Neural Networks, 100:39-48. 2018.
Jicong Fan, Yuqian Zhang, and Madeleine Udell. Polynomial matrix completion for missing data imputation and transductive learning. In Proceedings of the AAAI Conference on Artificial Intel- ligence, volume 34, pages 3842-3849, 2020.
Jicong Fan. Large-scale subspace clustering via k-factorization. In Proceedings of the 27th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, KDD '21, page 342-352, New York, NY, USA, 2021. Association for Computing Machinery.
Miroslav Fiedler. Algebraic connectivity graphs. Czechoslovak mathematical journal, 23(2):298- 305, 1973.
M. Halkidi and M. Vazirgiannis. Clustering validity assessment: finding the optimal partitioning of data set. In Proceedings 2001 IEEE International Conference on Data Mining, pages 187-194, 2001.
N. Halko, P. G. Martinsson, and J. A. Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions. SIAM Review, 53(2):217-288, 2011.
Harold V Henderson and Shayle R Searle. On deriving the inverse of a sum of matrices. Siam Review, 23(1);53-60, 1981.
Juhua Hu, Qi Qian, Jian Pei, Rong Jin, and Shenghuo Zhu. Finding multiple stable clusterings. Knowledge and Information Systems, 51(3):991-102,, 2017.
Hsin-Chien Huang, Yung-Yu Yu Chuang, and Chu-Song Chen. Affinity aggregation for spectral clus- tering. In 2012 IEEE Conference on Computer Vision and Pattern Recognition, pages 773-780. IEEE, 2012.

---

Frank Hutter, Lars Kotthoff, and Joaquin Vanschoren. Automated machine learning: methods, sys- tems, challenges. Springer Nature, 2019.
Pan Ji, Mathieu Salzmann, and Hongdong Li. Shape interaction matrix revisited and robustified: Efficient subspace clustering with corrupted and incomplete data. In Proceedings of the IEEE International Conference Computer Vision (ICCV), December 2015.
Pan Ji, Tong Zhang, Hongdong Li, Mathieu Salzmann, and lan Reid. Deep subspace clustering networks. In Advances in Neural Information Processing Systems, pages 24-33, 2017.
Stephen Johnson. Hierarchical clustering schemes. Psychometrika, 32(3):241-252 1967.
Donald R Jones, Matthias Schonlau, and William J Welch. Efficient global optimization of expensive black-box functions. Journal of Global optimization, 13(4):455-49) 1998.
Zhao Kang, Wangtao Zhou, Zhitong Zhao, Junming Shao, Meng Han, and Zenglin Xu. Large-scale multi-view subspace clustering in linear time. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 4412-4415 2020.
Zhao Kang, Zhiping Lin, Xiaofeng Zhu, and Wenbo Xu. Structured graph learning for scalable sub- space clustering: From single view to multiview. IEEE Transactions Cyhernetics, 52(9))8976 8986, 2022.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization, arXiv preprint orXiv:1412.6988, 2014.
Aaron Klein, Stefan Falkner, Simon Bartels, Philipp Hennig, and Frank Hutter. Fast bayesian op- timization of machine learning hyperparameters on large datasets. In Artificial Intelligence and Statistics, pages 528-536. PMLR, 2017.
Lee Kuang-Chibe J. Ho, and D. J. Kriegman. Acquiring linear subspaces for face recognition under variable lighting. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(5))684- 698, 2005.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):227822324 1998.
Chun-Guang Li and Rene Vidal. Structured sparse subspace clustering: unified optimization framework. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 277-286, 2015.
Chun-Guang Li and Rene Vidal. A structured sparse plus structured low-rank framework for sub- space clustering and completion. IEEE Transactions on Signal Processing, 64(24))6557-6557, 2016.
Jun Li and Handong Zhao. Large-scale subspace clustering by fast regression coding. In IJCAI, 2017.
Jun Li, Hongfu Liu, Zhiqiang Tao, Handong Zhao, and Yun Fu. Learnable subspace clustering. IEEE Transactions Neural Networks and Learning Systems, pages 1-15, 2020.
Yanchi Liu, Zhongmou Li, Hui Xiong, Xuedong Gao, and Junjie Wu. Understanding of internal clustering validation measures. In 2010 IEEE international conference on data mining, pages 911-916. IEEE, 2010.
G. Liu, Lin. S. Yan, Sun. Y. Yu, and Y. Ma. Robust recovery of subspace structures by low-rank representation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(1):171-184 2013.
Can-Yi Lu, Hai Min, Zhong-Qiu Zhao, Lin Zhu, De-Shuang Huang, and Shuicheng Yan. Robust and efficient subspace segmentation via least squares regression. European conference on computer vision, pages 347-360. Springer, 2012.
12

---

Canyi Lu, Jiashi Feng, Zhouchen Lin, Tao Mei, and Shuicheng Yan. Subspace clustering by block diagonal representation. IEEE transactions on pattern analysis and machine intelligence, 41(2):887-511 2018.
Juncheng Lv, Zhao Kang, Xiao Lu, and Zenglin Xu. Pseudo-supervised deep subspace clustering. IEEE Transactions on Image Processing, 30:5252-5263, 2021.
Louis Mahon and Thomas Lukasiewicz. Selective pseudo-label clustering. In German Conference Artificial Intelligence (Kiünstliche Intelligenz), pages 158-178, Springer, 2021.
Aleix M Martínez and Avinash C Kak. PCA versus LDA. IEEE transactions on pattern analysis and machine intelligence, 23(2):228-22)) 233, 2001.
Bertil Matérn. Spatial variation, volume 36. Springer Science & Business Media, 2013.
Shin Matsushima and Maria Brbic. Selective sampling-basee scalable sparse subspace clustering. In Advances Neural Information Processing Systems, pages 12416-12425, 2019.
Marian Mcila and Susan Shortreed. Regularized spectral learning. Journal of machine learning research, 1(1):1-20, 2006.
Marian Meila, Susan Shortreed, and Liang Xu. Regularized spectral learning. In AISTATS, PMLR, 2005.
Marina Meila. The multicut lemma. UW Statistics Technical Report, 417, 2001.
S. A. Nene, S. K. Nayar, and H. Murase. Columbia object image library (coil-20), Report, Columbia University, 1996.
Andrew Ng. Michael I Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. In Advances in neural information processing systems, pages 849-856, 2002.
Erlin Pan and Zhao Kang. Multi-view contrastive graph clustering. Advances in Neural Information Processing Systems, 34, 2021.
Pan Ji, M. Salzmann, and Hongdong Li. Efficient dense subspace clustering. In IEEE Winter Conference on Applications of Computer Vision, pages 461-465 2014.
V. M. Patel and R. Vidal. Kernel sparse subspace clustering. In 2014 IEEE International Conference on Image Processing (ICIP), pages 2849 2849,2853, Oct 2014.
V. M. Patel, Nguyen Hien Van, and R. Vidal. Latent space sparse and low-rank subspace clustering. Selected Topics Signal Processing, IEEE Journal of. 94)):9117711 2015.
Xi Peng, Lei Zhang, and Zhang Yi. Scalable sparse subspace clustering. In Proceedings the IEEE conference on computer vision and pattern recognition, pages 430-437, 2013.
Xi Peng, Huajin Tang, Lei Zhang, Zhang Yi, and Shijie Xiao. A unified framework for representation--asee subspace clustering of out-of-sample and large-scale data. IEEE transac- lions neural networks and learning systems, 27(12):249-25512 2015.
Giannis Poulakis. Unsupervised automl: study automated machine learning in the context of clustering. Master's thesis, HavεmιoTíuu Πεςaańςs, 2020.
Sam T Roweis and Lawrence Saul. Nonlinear dimensionality reduction by locally linear embed- ding. Science, 29065500):2333-253333 2326, 2000.
S. Samaria and A. C. Harter. Parameterisation of a stochastic model for human face identification. In Proceedings of 1994 IEEE Workshop on Applications of Computer Vision, pages 138-142, Dec 1994.
Jie Shen and Ping Li. Learning structured low-rank representation via matrix factorization. Pro- ceedings of the 19th International Conference Artificial Intelligence and Statistics, volume 51 of Proceedings of Machine Learning Research, pages 500-509, Cadiz, Spain, 09-11 May 2016. PMLR.
13

---

Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. IEEE Transactions on pattern analysis and machine intelligence, 22(8):888 9008,90552000 2000.
Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization of machine learning algorithms, Advances in neural information processing systems, 25, 2012.
Mahdi Soltanolkotabi, Ehsan Elhamifar, and Emmanuel Candes. Robust subspace clustering. The Annals of Statistics, 42(2):669-693 2014.
Sho Sonoda and Noboru Murata. Neural network with unbounded activation functions is universal approximator. Applied and Computational Harmonic Analysis, 43(2):233 - 268, 2017.
Johannes Stallkamp, Mare Schlipsing, Jan Salmen, and Christian Igel. Man vs. computer: Bench- marking machine learning algorithms for traffic sign recognition. Neural networks, 32:323-333 332, 2012.
Hugo Steinhaus et al. Sur la division des corps matériels parties. (804)):01, 1956.
Bull. Acad. Polon. Sci,
Michael E Tipping and Christopher M Bishop. Mixtures of probabilistic principal component ana- lyzers. Neural computation, 1(2)):43-4433 1999.
Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17(4):395 2007.
Yu-Xiang Wang and Huan Xu. Noisy sparse subspace clustering. In International Conference on Machine Learning, pages 89-97. PMLR, 2013.
Shusen Wang, Bojun Tu, Congfu Xu, and Zhihua Zhang. Exact subspace clustering in linear time. In Proceedings of the Eivent-Eightt AAAI Conference Artificial Intelligence, pages 2113-2122 2014.
Y. Weiss. Segmentation using eigenvectors: unifying view. In Proceedings of the Seventh IEEE International Conference Computer Vision, volume 2, pages 975-982 vol.2, 1999.
Christopher K Williams and Carl Edward Rasmussen. Gaussian processes for machine learning, volume MIT press Cambridge, MA, 2006.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmark- ing machine learning algorithms, 2017.
Chong You, Chun-Guang Li, Daniel Robinson, and René Vidal. Oracle based active set algorithm for scalable elastic net subspace clustering. In Proceedings of the IEEE conference computer vision and pattern recognition, pages 3928-3937, 2016.
Chong You, Daniel Robinson, and René Vidal. Scalable sparse subspace clustering by orthogo- nal matching pursuit. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 3918-3927, 2016.
Chong You, Chi Li. Daniel P Robinson, and René Vidal. Scalable exemplar- based subspace clus- tering on imsslannadn data. In Proceedings of the European Conference on Computer Vision (ECCV), pages 67-83, 2018
Junjian Zhang, Chun-Guang Li, Chong You, Xianbiao Qi, Honggang Zhang, Jun Guo, and Zhouchen Lin. Self-supervised convolutional subspace clustering network. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 5473-5482, 2019.
Tong Zhang. Pan Ji, Mehrtash Harandi, Wenbing Huang, and Hongdong Li. Neural collabora- tive subspace clustering. In International Conference on Machine Learning, pages 7384-739) PMLR. 2019.
14

---

Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information on how to answer these questions. For each question, change the default [TODO] to [Yes], [No], or [N/A] You are strongly encouraged to include justification your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section.
Did you include the license the code and datasets? [No] The code and the data proprietary.
Did you include the license to the code and datasets? [N/A]
Please do modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below,
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [N/A]
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]
3. If you experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you are using existing assets (c.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're re using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifi- able information or offensive content? [N/A]
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
15


Reviews:
[{"review_id": "qA-kRL2jXI1", "reviewer": "Reviewer_37XY", "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.", "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$.\n\n2. It was claimed that the $\\varepsilon$ in equation (6) is a small constant such as 1e-6. What if it is too big?\n\n3. 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. \n\n4. 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.\n\n5. 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.\n\n6. 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.\n", "limitations": "None", "rating": 8, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n1. 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.\n\n2. 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$.\n\n3. The authors provided a novel method NSE for large-scale clustering.\n\n4. The literature is sufficient and the related work has been clearly discussed.\n\n5. 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.\n\nIn sum, the paper is well-written and has both theoretical guarantees and numerical verification. In my opinion, it solved a challenging problem in clustering.\n\nWeaknesses:\n1. Some notations (e.g. $\\sigma_1,\\sigma_2,\\ldots$ in Table 1 and $L_s$ in Section 3.3) were not clearly explained.\n\n2. It is not clear how efficient when AutoSC is applied to deep learning based clustering.\n\n3. The conclusion section is a little bit short. Please provide more discussion.\n\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "KfDwPLgCBuJ", "reviewer": "Reviewer_uYf6", "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.", "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).\n2. 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.\n3. The manuscript format is out of order, such as Table 3.\n4. 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. \n5. 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.\n6. 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.\n7. 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).\n8. The limitations are not mentioned.\n\nIn conclusion, the proposed idea is interesting but the manuscript is far from prepared, including expression, organization and experiment validation.\n", "limitations": "No", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 1, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. The idea is interesting to build the affinity matrix of spectral clustering by modeling its eigenvalue distribution.\n2. The authors provide rich theories about the proposed criterion and method.\n3. The large-scale problem is also considered.\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "BgrQU1eoSP", "reviewer": "Reviewer_rahg", "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.\n\nThe 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. ", "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.\n\nThe connection to relatex work is quite limited as far as I can tell. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n- A new method for comparing the eigenvalues of the Laplacian of an affinity matrix could influence the direction of spectral clustering research. \n- 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.\n- The experiment section is extensive and shows that the method performs strongly. \n\nWeaknesses:\n- 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. \n- The connection between the theoretical results and the contributions are not entirely clear in my opinion.\n- 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.", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "-79ecSbdw2l", "reviewer": "Reviewer_uu35", "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.", "questions": "In addition to the weaknesses mentioned above, it would be helpful if the authors could address the following questions.\n\n1. 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?\n2. Can the authors explain more about the meaning of $\\gamma$ and $\\beta$ defined in Definition 4.3? Is there any assumption about the noise? \n3. In Proposition 4.5, is reg(L)>0 necessary? \n4. In Figure 1(i), what does the green circle mean?\n5. 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.\n6. 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.\n7. In Line 290, if NSE is ablated, what’s the accuracy of AutoSC-GD on the full MNIST?\n", "limitations": "The authors did not mention the limitation.", "rating": 7, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. The paper is interesting and the problem here addressed is important for the machine learning community.\n2. The overall approach is well described and seems novel.\n3.  The proposed method works well on the evaluated datasets.\n\nWeaknesses:\n1. The notation in Section 3.3 can be improved.\n2. Some important results (e.g. Theorem C.3) are in the supplementary material rather than in the main paper.\n3. The authors only reported the clustering accuracy, it should be better to have more commonly used clustering metrics such as NMI and ARI.\n4. The text in Figure 2(ii) is too tiny.\n", "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": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept