Fast and Simple Spectral Clustering in Theory and Practice
Authors: Peter Macgregor
Venue: NeurIPS 2023 poster (2023)
Keywords: spectral clustering
power method
spectral graph theory
graph algorithms
TL;DR: We present and analyse a fast and simple spectral clustering algorithm based on an embedding of the graph vertices using O(log(k)) vectors.

Abstract: Spectral clustering is a popular and effective algorithm designed to find $k$ clusters in a graph $G$.
In the classical spectral clustering algorithm, the vertices of $G$ are embedded into $\mathbb{R}^k$ using $k$ eigenvectors of the graph Laplacian matrix.
However, computing this embedding is computationally expensive and dominates the running time of the algorithm.
In this paper, we present a simple spectral clustering algorithm based on a vertex embedding with $O(\log(k))$ vectors computed by the power method.
The vertex embedding is computed in nearly-linear time with respect to the size of the graph, and
the algorithm provably recovers the ground truth clusters under natural assumptions on the input graph.
We evaluate the new algorithm on several synthetic and real-world datasets, finding that it is significantly faster than alternative clustering algorithms,
while producing results with approximately the same clustering accuracy.

Fast and Simple Spectral Clustering in Theory and Practice
Peter Macgregor
School of Informatics University of Edinburgh peter macgregor@ed ac uk
Abstract
Spectral clustering is popular and effective algorithm designed to find k clusters in a graph In the classical spectral clustering algorithm, the vertices of G are embedded into I using & eigenvectors of the graph Laplacian matrix. However, computing this embedding is computationally expensive and dominates the running time of the algorithm. In this paper, we present simple spectral clustering algorithm based on a vertex embedding with Ollo(k)) vectors computed by the power method. The vertex embedding is computed in nearly-linear time with respect to the size of the graph, and the algorithm provably recovers the ground truth clusters under natural assumptions the input graph. We evaluate the new algorithm on several synthetic and real-world datasets, finding that it is significantly faster than alternative clustering algorithms, while producing results with approximately the same clustering accuracy.
Introduction
Graph clustering is important problem with numerous applications in machine learning, data science, and theoretical computer science. Spectral clustering is a popular graph clustering algorithm with strong theoretical guarantees and excellent empirical performance. Given graph G with vertices and clusters, the classical spectral clustering algorithm consists of the following two high-level steps 226 33
1. Embed the vertices G into R according to & eigenvectors of the graph Laplacian matrix.
2. Apply k-means clustering algorithm to partition the vertices into & clusters.
Recent work shows that if the graph has well-defined cluster structure, then the clusters well- separated in the spectral embedding and the k-means algorithm will return clusters which are close to optimal (1 28
The main downside of this algorithm is the high computational cost computing & eigenvectors of the graph Laplacian matrix. In this paper, address this computational bottleneck and propose new fast spectral clustering algorithm which avoids the need to compute eigenvectors while maintaining excellent theoretical guarantees. Moreover, proposed algorithm is simple, fast, and effective in practice.
1.1 Sketch of Our Approach
In this section, introduce the high-level idea of this paper, which is also illustrated in Figure 1 We begin by considering recent result of Makarychev et al. (23 who show that a random projection of data into (Iogg())) dimensions preserves the k-means objective function for all partitions of the
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Compute k Eigenvectors
Spectral Embedding
k-means
Random Projection
Graph
Clusters
Power
k-means
Method
Low-dim.
Embedding
An illustration of the steps of the spectral clustering algorithm, and the contribution of this paper. We are given graph as input. In classical spectral clustering follow the top path: compute the spectral embedding and apply a k-means algorithm to find clusters. Through the recent result of Makarychev al. 2X obtain approximately the same clustering. In this paper, we show that it is possible to compute the low-dimensional embedding directly with the power method, skipping the computationally expensive step of computing & eigenvectors.
Figure 1:
we can project the embedded points into (log(k)) dimensions and
data, with high probability. Since the final step of spectral clustering is to apply k-means, we might consider the following alternative spectral clustering algorithm which will produce roughly the same output as the classical algorithm.
1. Embed the vertices G into R according to k eigenvectors of the graph Laplacian matrix.
2. Randomly project the embedded points into (llo(()) dimensions.
3. Apply k-means clustering algorithm to partition the vertices into i clusters.
Of course, this does not avoid the expensive eigenvector computation and it is not immediately clear that this random projection can be used to improve the spectral clustering algorithm.
The key technical element of our paper is a proof that we can efficiently approximate random projection of the spectral embedding without computing the spectral embedding itself. For this, we use the power method, which is well-known technique in numerical linear algebra for approximating the dominant eigenvalue matrix described in Algorithm 2
propose the following simple algorithm (formally
1. Embed the vertices of G into ((lo(k)) dimensions using O(log(k)) random vectors computed with the power method.
2. Apply k-means clustering algorithm to partition the vertices into k clusters.
We prove that the projection obtained using the power method approximately equivalent random projection of the spectral embedding. Then, by carefully applying the techniques developed by Makarychev et 23 and Macgregor and Sun [21], we obtain a theoretical bound on the number of vertices misclassified by our proposed algorithm. Moreover, the time complexity of step 1 is nearly linear in the size of the graph, and the algorithm is fast practice, The formal theoretical guarantee
is given in Theorem 3.1

---

1.2 Related Work
This paper closely related to a sequence of recent results which prove an upper bound on the number of vertices misclassified by the classical spectral clustering algorithm [ [2 (2)). While we will directly compare our result with these in a later section, our proposed algorithm has much faster running time than the classical spectral clustering algorithm, and has similar theoretical guarantees.
Boutsidis et al. [ also study spectral clustering using the power method. Our result improves theirs two respects. Firstly, our algorithm is faster since we compute (log((A) vectors rather than vectors and their algorithm includes an additional singular value decomposition step. Secondly, we give a theoretical upper bound on the total number of vertices misclassified by our algorithm.
Makarychev et al. 233 generalise the well-known Johnson-Lindenstrann Lindenstrauss lemma [13 to show that random projections of data into (log(k)) dimensions preserves the k-means objective, and we make use of their result in our analysis.
Macgregor and Sun 21 show that for graphs with certain structures of clusters, spectral clustering with fewer than k eigenvectors performs better than using k eigenvectors. In this paper, we present the first proof that embedding with (l)g vectors is sufficient to find & clusters with spectral clustering.
Other proposed methods for fast spectral clustering include the Nystrom method [6] and using 'pre-clustering' step to reduce the number of data points to be clustered [35]. These methods lack rigorous theoretical guarantees on the accuracy of the returned clustering. Moreover, our proposed algorithm is significantly simpler to implement that the alternative methods.
2 Preliminaries
E, w) be graph with [V| and m |E| For any V, the degree of is given by d(v) = Enuo w(u, v). For any S C V, the volume of S is given by vol(S) = Enes d(u). The Laplacian matrix of G' is L = D - A where D is the diagonal matrix with D(i, i) = d(i) and A is the adjacency matrix of G. The normalised Laplacian is given by N D LD 3. We always use A1 I 22 I .... I A to be the eigenvalues of N and the corresponding eigenvectors are fi.....f f For any graph. it holds that À
Let G (V,
and An 2 77. We will also the signless Laplacian matrix M = 1 [1/2)N and will let 7/1 2 2 Yn be the eigenvalues of M. Notice that by the definition of M. we have %
(1/2)²; and the cigenvectors of M are also fi...., f For an integer k. we let [k] = (1....A, }} be the set of all positive integers less than or equal to k. Given two sets A and B, their symmetric difference given by AAB = (A B) (B \ A). We call {S:) a k-way partition of V if S. n Sj- = 0 for i # j and -._, V.
Throughout the paper, we big-O notation to hide constants. For example, use 1 ((n) to mean that there exists a universal constant such that I S en. We sometimes use Ö(n) in place of (n (og((n)) for some constant c. Following [2I], we say that partition {8 of V is almost-balanced if vol(S;) = ((vol(V)/H) for all i E [k].
2.1 Conductance and the Graph Spectrum
Given graph G = (V, E), and cluster S C V, the conductance of S is given by w (S.3))
(SS) min vS)
where -(,,)==vve Eves w(u, (u, v). Then, the k-way expansion of G is defined be p(k) partition C,....a
min max (C.).
Notice that p(k) is small if and only if G' can be partitioned into & clusters of low conductance. There a close connection between the k-way expansion of and the eigenvalues of the graph Laplacian matrix, as shown in the following higher-order Cheeger inequuality.
'The signless Laplacian is usually defined to be 2 N. We divide this by 2 so that the eigenvalues of M lie between 0 and 1.
3

---

Lemma 2.1 (Higher- Orderr Cheeger Inequality, (19].. For graph G, let x ... S An be the eigenvalues of the normalised Laplacian matrix. Then, for any k.
d S ((k) s ((()) V 2
From this lemma, we can see that an upper bound on p(k) and a lower bound on A&+1 are sufficient conditions to guarantee that G can be partitioned into & clusters of low conductance, and cannot clusters. This condition is commonly used in the analysis of graph
be partitioned into
clustering 15 24
2.2 The k-means Objective
For any matrix RRadd the k-meaas cost of a k-way partition {4.) of the data points given by
CO A&)
BB,,:) 14 11
1=1 WEA.
where B(u,;) :) is the uth row of B and μu; (1/1A:)) Eves, Bu,,:) :) the mean of the points A, Although optimising the k- d-means objective is NP-hard, there a polynomial-time constant factor
approximation algorithm [14), and an approximation scheme which is polynomial in and d with an
exponential dependency on k [6]. Lloyds algorithm (20). with k-means++ initialisation 3 an
algorithm which is fast and effective in practice.
2.3 The Power Method
The power method is an algorithm which most often used approximate the dominant eigenvalue of matrix 25). Given some matrix M E IR=x,, a vector 26 E IR"", and positive integer 4, the power method computes the value of M by repeated multiplication by M. The formal algorithm is given in Algorithm
Algorithm 1: POWERMETHOD(ME E Raxn 3o E RR", E Z20)
for [1....,t] do æ, Mr;-1
3 end
return 2t
3 Algorithm Description and Analysis
In this section, present newly proposed algorithm and sketch the proof of our main result. Omitted proofs can be found in the Appendix. We first prove that M has eigenvalues 7/ * close 1, then the power method can be used to compute random vector in the span of the eigenvectors corresponding to ;
We then apply this result to the signless Laplacian matrix of graph to develop fast spectral clustering algorithm and we bound the number of misclassified vertices when the algorithm is applied to well-clustered graph.
3.1 Approximating a Random Vector with the Power Method
Suppose we are given some matrix M E Raxa with eigenvalues 2 71 2 ... 2 Jn 2 and corresponding eigenvectors f Typically, the power method is used to approximate the dominant eigenvector, fi. In this section, we show that when n sufficiently close 1, the power method can be used to compute random vector in the space spanned by fi....,

---

Let E R" be random vector chosen according to the n-dimensional Gaussian distribution N I). We can write 2g as a linear combination of the eigenvectors:
Zg
a.fi.
where a; (Iro ft). Then, the vector at, computed by POWERMETHOD no can be written as
at Σ anks
Informally, if y 2 1- and Ne+1 < - C2 for sufficiently small and sufficiently large C22 then for a carefully chosen value of we have o 1 for i and 7/ x 0 for k 1. This implies that
Dt Σ a.fi
ΣE f.ft To.
3o is random vector distributed according a k-dimensional Gaussian distribution in the space spanned by fi....: fu. We make this intuition formal in Lemma 3.1 and specify the required conditions on Tk: 7k++ and f.
and we observe that (E
f.f!
Lemma 3.1. Let M E Rax" be matrix with eigenvalues 1 2 71 corresponding eigenvectors fI.... Let ao E Rn be drawn from the n-ddimensional Gaus- sian distribution I). Let Ht POWERMETHOD(MA xo, for t @(log(n/Ekk) If The 0 log(n//"k) and Y < 1 22(1,, then with probability least 1/(1k)),
2 00 and
||= - Pxoll2 I evk,
where P fif. is the projection onto the space spanned by the first k eigenvectors of M.
3.2 The Fast Spectral Clustering Algorithm
We now introduce the fast spectral clustering algorithm. The algorithm follows the pattern of the classical spectral clustering algorithm, with an important difference: rather than embedding the ver- tices according A eigenvectors of the graph Laplacian, embed the vertices with θ log(k) - random vectors computed with the power method for the signless graph Laplacian M. Algorithm 2 formally specifies the algorithm, and the theoretical guarantees given in Theorem 3.1
Theorem 3.1.
Let G be graph with λx+1 = 2(11 and p(k) = O(e log(n/e) Additionally, let
Ti= {S. Diii be the k-way partition corresponding to p(k) and suppose that {S.) )== almost balanced.
Let (A,) kk be the output of Algorithm 2
With probability at least 0.9 e, there exists permutation
k + [k] such that
vol vol(A, O vol(Ve))
Moreover, the running time of Algorithm 2
Óm 2 (RM k. k,
where m is the number of edges in and TrMin k. I) the running time of the k-means approxi- mation algorithm points in I dimensions.
The assumptions on Ae+1 and p(k) in Theorem 3.1 imply that the graph G can be partitioned into exactly k clusters of low conductance. This is related previous results which make an assumption on the ratio \s+1/p(k) [21 28 30J. Macgregor and Sun (2I) prove guarantee like Theorem 3.1 under the assumption that M (2()). We achieve a faster algorithm under slightly stronger assumption.
Remark 3.1.
Remark 3.2. The running time of Theorem 3.1 improves on previous spectral clustering algo- rithms. Boutsidis et al. [4] describe an algorithm with running time Õ(m k- k---?) + O n)) TRM(n, ki k). Moreover, their analysis does not provide any guarantee on the number of misclassifted vertices.
5

---

Algorithm 2: FASTSPECTTAACCLUSTTRR( (V, E),
Zza. c C 1))
M - (1/2) NG
1 < θ (ko
f (log(n//ckk) for (l...., do
Let 2; E R" be a random vector from Gaussian distribution N(0,1)
y: f POWERMETHOD
end
8 Y yii.... y1i....ihh yil A A1,..., A + IMEANS(DD 1/21/2
10 return AI...., Ar
Remark 3.3. The constants in the definition of I and t in Algorithm 2 are based on those in the analysis Makarychev al. [23) and this paper. In practice, we find that setting = loo and t = (Olog(n/)) works well.
Throughout the remainder of this section, we will sketch the proof of Theorem 3.1
We assume that (V, E) is graph with clusters {S.) of almost balanced size, A (11), and p(k) O( log(n/e)
In order to understand the behaviour of the k-means algorithm on the computed vectors, we will analyse the f--means cost of given partition under three different embeddings of the vertices. Let fi..... f& be the cigenvectors of M corresponding to the eigenvalues "i....., " and let yı,.... y be the vectors computed in Algorithm 2 We will also consider the vectors 21, 21,-.... : Σ fif!
given by
2, Pa,, where {a are the random vectors sampled in Algorithm 2 and
is the projection onto the space spanned by f Notice that each 2; is random vector distributed according the k-dimensional Gaussian distribution. Furthermore, let
Y F.
F
f
Y=
fA
yt
and
Z =
21
21
We will consider the vertex embeddings given by D D-1/2F, D 1-11/2 and D 1-1/2Y and show that the k-means objective for every k-way partition is approximately equal in each them. We will the following result shown by Makarychev et al. [23].
Lemma 3.2 ((33) Theorem 1.3). Given data X E &nnk let II Rext be random matrix with each column sampled from the k-dimensional Gaussian distribution N(0, Ix) and
1 1=0 log(k) + +log(1/c)
(=0( e²
Then, with probability at least e, holds for all partitions {A) of [n] that
COST (AI..... Av) E (1 =))SSTTTmxm xm ...
Applying this lemma with X D- 1F and II FTZ shows that the k-means cost approximately equal the embeddings given by D D- and D since FFTZ = and each of the entries of FTZ is distributed according to the Gaussian distribution N(0, 1) D By Lemma 3.1 can also show
that the k-means objective in D Y within an additive error of D 1 Z. This allows to prove the following lemma.
Lemma 3.3. With probability least 0.9 e, for any partitioning (A.) of the vertex set V,
have
COST (AI Ax) (1 - e)COSTD 1/2F [Ai..... .A) Au) ek
and
COST 1/28 (A1, Av) < + +OOST (1,, A+) + eki
"There is some interesting subtlety in this argument. If we ignore the D matrix. then is the data matrix, and FTZ represents the random projection. After projecting the data, we are left with the projection matrix Z itself. This happens only because the data matrix is the orthonormal basis F which is also used to project Z.

---

To complete the proof of Theorem 3.1 we will make use of the following results proved by Macgregor and Sun 21 Lemma 3.4 (21, Lemma 4.1). There exists partition {A:) of the vertex set V such that
COSTp-VappA1: A&) < k p(k)/ /x+11 Lemma 3.5 (211, Theorem 2). Given some partition of the vertices, {Ai)ezn such that
D-/aa-- Au) k;
then there exists a permutation a [k] + [k]] such that
Σ vol(A,,5. O vol(V))
Proof of Theorem 3.1 By Lemma 3.4 and Lemma 3.3 with probability at least 0.9 e, there exists
some partition {A: Ji=1 of the vertex Va such that
As) = log(n/e) + ek
ek
COSTD-1Ay
Since we use a constant-factor approximation algorithm for k-means, the partition { [4 returned by Algorithm 2 satisfies COST 1/ A&) O(ck). Then, by Lemma 3.5
3n5 and Lemma 3.3
for some permutation a : [k] + [k]. we have
(o = Oc vol(Ve)).
To bound the running time, notice that the number of non-zero entries in M is 2m, and the time complexity matrix multiplication proportional to the number non-zero entries. Therefore, the running time of POwER METHOD(M, zo 1) is (()) Since the loop in Algorithm 2 is executed O (log(k)) -)) times, the total running time of Algorithm 2 is Ōm -2)
2) + TKM (n,
4 Experiments
this section, we empirically study several variants of the spectral clustering algorithm. We compare the following algorithms:
k EIGENVECTORS: the classical spectral clustering algorithm which uses eigenvectors of the graph Laplacian matrix to embed the vertices. This is the algorithm analysed in [1 28
(k) EiGEnVECTORS: spectral clustering with log(k) eigenvectors the graph Laplacian embed the vertices.
KASP: the fast spectral clustering algorithm proposed by Yan et al. 35 The algorithm proceeds by first coarsening the data with ke-maans before applying spectral clustering.
PM & VECTORS (Power Method with & vectors): spectral clustering with k orthogonal vectors computed with the power method. This the algorithm analysed in 4
PM log(k) VECTORS: spectral clustering with log(k) random vectors computed with the power method. This is Algorithm
We implement all algorithms in Python, using the numpy
scipy 32 stag 22 and
scikit-learn [27]. libraries for matrix manipulation, eigenvector computation, graph process- ing, and k-means approximation respectively. We first compare the performance of the algorithms on synthetic graphs with range of sizes drawn from the stochastic block model (SBM). We then study the algorithms' performance on several real-world datasets. We find that our algorithm is significantly faster than all other spectral clustering algorithm, while maintaining almost the same clustering accuracy. The most significant improvement seen on graphs with large number of clusters. All experiments are performed an HP laptop with an 11th Gen Intel(R) Core(TM) 17-118001 2.30GHz processor and GB RAM. The code to reproduce the experiments is available at https:/ // /gi thub. com/pmacg/fast- http://fttssssetaaal -aaars---pperal-lcstttiinnn

---

120
BIGENVECTORS
100
log( EIGENVECTORS
60
PM VECTORS
Running time (s)
PM log(k) VECTORS
40
Running
60
40
20
20
0-
0
100
200
300
400
0.0
0.2
0.4
0.6
0.8
1.0
Number of clusters
Number of vertices
x 10"
(a)
(b)
Figure 2: The running time of spectral clustering variants on graphs drawn from the stochastic block model. (a) Setting n 1000 k and increasing the number of clusters, k, shows that A Algorithm 2 much faster than alternative methods for large values of k. (b) Setting 20 and increasing the number of vertices, n, shows that for fixed k, Algorithm 2 is faster than the alternatives by constant factor.
4.1 Synthetic Data
In this section, evaluate the spectral clustering algorithms synthetic data drawn from the stochastic block model. Given parameters Zoo. k: E Z20. E [0, 1]. and g E [0, 1]. we generate graph G (V, E') with vertices and k ground-truth clusters Si,..,, ,..--,,, S5 of size n/ For any pair of vertices u E S and v E Sj. we add the edge {u, 4 with probability p if and with probability q otherwise. We study the running time of the algorithms in settings.
In the first experiment, we set n 1000 k. p = 0.04, and g = 1/1000))) Then, we study the running time of spectral clustering for different values of k. The results shown in Figure 2(a) We observe that our newly proposed algorithm much faster than existing methods for large values of k and our algorithm is easily able to scale large graphs with several hundred thousand vertices.
In the second experiment, we running time of the spectral clustering algorithms for different values of n. The results are shown in Figure [ Empirically, we find that when & is fixed constant, our newly proposed algorithm faster than existing methods by constant factor. In every case, all algorithms successfully recover the ground truth clusters
20, p 40/ n, and q 1/(20n). Then, we study the
4.2 Real-world Data
In this section, we evaluate spectral clustering on real-world data with labeled ground truth clusters. We compare the algorithms on the following datasets from variety of domains.
each data point is an image with 28 x 28 greyscale pixels, representing hand-written digit from 0 to 9.
MNIST [18]
Pen Digits I data is collected by writing digits on digital pen tablet. Each data point corresponds to some digit from 0 to 9 and consists of 8 pairs of (æ, y) coordinates encoding the sequence of pen positions while the digit was written.
Fashion
each data point is an image with 28 x 28 greyscale pixels, representing one of 10 classes of fashion item, such 'shoe" 'shirt'.
34
HAR (Human Activity Recognition) 2 the dataset consists of pre-processed sensor data from a body-worn smartphone. Participants were asked to perform variety of activities,
Note that we cannot compare with the KASP algorithm on the stochastic block model since KASP is designed operate vector data rather than graphs.

---

Table 1: The performance of spectral clustering algorithms real-world datasets. The PM (k) algorithm corresponds to Algorithm 2 We perform 10 trials and report the average performance with one standard deviation of uncertainty. We observe that Algorithm 2 consistently very fast when compared to the other algorithms while achieving comparable clustering accuracy.
Dataset Fashion
Algorithm k FIGS
MNIST
Pen Digits
HAR
Letter
+.20
0.64 + 0.07
3.55 0.17
0.58 + 0.07
29.29 + 11.85
log(k) EIGS
0.20
1.01 0.05
3.79
0.83
24.99
11.58
Time
KASP
15.47
3.54
0.91 0.19
0.33 0.14
PMG & PM (kg(k:
3.23 0.15
2.40
0.38 0.01
1.14 0.02
1.99 0.05
0.36
0.09
0.30 0.02
0.39 0.02
EIGS
0.01
0.02
0.42
0.51 0.00
0.17
log(k) EIGS
0.49 1 0.03
0.63 0.06
0.32
0.30 + 0.01
0.17 0.00
ARI
KASP
0.33 + 0.03
0.04
0.30
0.48 0.03
0.13 0.01
PM &
0.55 0.03
0.60
0.50 0.02
0.02
0.00
PM (kg(k)
0.51 0.04
0.01
0.35-1.000
0.49 0.00
0.17 0.00
k EIGS
0.78 0.01
0.00
0.70
0.27 0.02
log(k) EIGS
0.68 0.01
0.77
0.55
0.48
0.13 0.02
NMI
KASP
0.48 1 0.02
0.60 0.003
0.46
0.61 0.03
0.35 1 0.01
PM &
0.73 1 0.03
0.76 1.00
0.6110.00
0.69 0.02
0.29 1 0.03
PM (k)
0.69 1 0.02
0.77 0.02
0.55
0.66 1 0.04
0.30 1 0.01
such 'walking'. 'walking upstairs', and 'standing'. The task is identify the activity from the sensor data.
Letter [9] each data point corresponds to upper-case letter from 'A' to 'Z'. The data was generated from distorted images of letters with a variety of fonts, and the features correspond to various statistics computed on the resulting images.
The datasets all made available by the OpenML 31 project, and can be downloaded with the scikit-learn library (27] We first pre-process each dataset by com- puting the k nearest neighbour graph from the data, for = 10. Table 2 shows the number of nodes and the number of ground truth clusters in each dataset.
Table 2: The number of vertices (n) and clusters (k) in each of the real-world datasets.
Dataset
π
k
MNIST
70000
10
For each dataset, report the performance of each spec- tral clustering algorithm with respect to the running time in seconds, and the clustering accuracy measured with the Adjusted Rand Index (ARI) 10
Pen Digits
7494
10
Fashion
70000
10
HAR
10299
6
29 and the Normalised
Letter
20000
26
Mutual Information (NMI) 17 Table T summarises the
results.
We find that Algorithm is consistently very fast when compared to the other spectral clustering algorithms. Moreover, the clustering accuracy similar for every algorithm.
5 Conclusion
In this paper, we introduced a new fast spectral clustering algorithm based on projecting the vertices of the graph into (lo)(k)) dimensions with the power method. We find that the new algorithm is faster than previous spectral clustering algorithms and achieves similar clustering accuracy.
This algorithm offers new option for the application of spectral clustering. If a large running time is acceptable and the goal is to achieve the best accuracy possible, then our experimental results suggest that the classical spectral clustering algorithm with & eigenvectors is the optimal choice. On the other hand, when the number of clusters or the number of data points very large, our newly proposed method provides significantly faster algorithm for small trade-off in terms of clustering accuracy. This could allow spectral clustering to be applied in regimes that were previously intractable, such as when & = (n))

---

Acknowledgements
This work is supported by EPSRC Early Career Fellowship (
References
[1] Fevzi Alimoglu and Ethem Alpaydin. Methods of combining multiple classifiers based on different representations for pen-based handwriting recognition. In Proceedings of the fifth Turkish artificial intelligence and artificial neural networks symposium (TAINN 96), 1996.
[2] Davide Anguita, Alessandro Ghio, Luca Oneto, Xavier Parra, and Jorge Luis Reyes-Ortiz, A public domain dataset for human activity recognition using smartphones. In 21st European Symposium on Artificial Neural Networks (ESANN' 13), 2013.
[3] David Arthur and Sergei Vassilvitskii. K-means++: the advantages of careful seeding. In Proceedings of the 18th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA '07),
pages 1027-1035, 2007.
[4] Christos Boutsidis, Prabhanjan Kambadur, and Alex Gittens. Spectral clustering via the power method-provably. In 32nd International Conference on Machine Learning (ICML' 15), pages
40-48. PMLR, 2015.
[5] Christos Boutsidis and Malik Magdon-Ismail. Deterministic feature selection for k-means clustering. IEEE Transactions on Information Theory, 59(9):609--611 10, 2013.
[6] Anna Choromanska, Tony Jebara, Hyungtae Kim, Mahesh Mohan, and Claire Monteleoni. Fast spectral clustering via the nyström method. In Algorithmic Learning Theory: 24th International Conference (ALT'13), pages 367-381, 2013.
[7] Fan R K Chung. Spectral graph theory. American Mathematical Society, 1997.
[8] Dan Feldman, Morteza Monemizadeh, and Christian Sohler. A PTAS for k-means clustering based on weak coresets. In Proceedings of the 23rd Annual Symposium on Computational Geometry (SoCG'07), pages 11-18, 2007.
[9] Peter W Frey and David Slate. Letter recognition using holland-style adaptive classifiers. Machine learning, 6:822 1991.
[10] Alexander J. Gates and Yong- Yeol Ahn. The impact of random models clustering similarity, The Journal of Muchine Learning Research, 18(1):004-30766 2017.
[11] Gene H Golub and Henk A Van der Vorst. Eigenvalue computation in the 20th century, Journal of Computational and Applied Mathematics, 123(1-2):35-6) 65, 2000.
[12] Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Cournapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fer- nández del Río. Mark Wiebe, Pearu Peterson, Pierre Gérard-Marchand Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis E, Oliphant. Array programming with NumPy. Nature, 585(7825):357-362 2020.
[13] William B Johnson. Extensions of lipschitz mappings into a hilbert space. Contemporary Mathematics, 26:189-206, 1984.
[14] Tapas Kanungo, David M Mount, Nathan S Netanyahu, Christine D Piatko, Ruth Silverman, and Angela Y Wu. A local search approximation algorithm for k-means clustering. In Proceedings of the 18th Annual Symposium on Computational Geometry (SoCG'02) pages 10-18, 2002.
[15] Pavel Kolev and Kurt Mchlhorn. A note spectral clustering. In 24th Annual European Symposium on Algorithums (ESA 16), pages 1-14, 2016.
[16] Amit Kumar, Yogish Sabharwal, and Sandeep Sen. simple linear time aprrxxiipooinnaii algorithm for k-means clustering in any dimensions. In 45th Annual IEEE Symposium on Foundations of Computer Science (FOCS'04), pages 454-462 IEFE, 2004.
[17] Andrea Lancichinetti, Santo Fortunato, and János Kertész. Detecting the overlapping and hierarchical community structure in complex networks. New Journal of Physics, 11(3), 2009.
[18] Yann LeCun. The mnist database of handwritten digits. ATT Labs [Online]. Available:
http://ymmm.ecc..cmm//ebbb////// 1998.
10

---

[19] James R Lee, Shayan Oveis Gharan, and Luca Trevisan. Multiway spectral partitioning and higher-order Cheeger inequalities. Journal of the ACM, 61(6):1-30, 2014.
[20] Stuart Lloyd. Least squares quantization in pem. IEEE transactions on information theory, 28(2):129-137, 1982.
[21] Peter Macgregor and He Sun. A tighter analysis of spectral clustering, and beyond. In 39th International Conference Machine Learning (ICML (22) pages 14717-14742, 2022.
[22] Peter Macgregor and He Sun. Spectral toolkit of algorithms for graphs: Technical report (1).
CoRR, abs/2304.03 2023.
[23] Konstantin Makarychev, Yury Makarychev, and Ilya Razenshteyn. Performance of Johnson- Lindenstrauss transform for k-means and k-medians clustering. In Proceedings of the s
Anmual ACM SIGACT Symposium on Theory of Computing (STOC' page 1027-1038, 2019.
[24] Tomohiko Mizutani. Improved analysis of spectral algorithm for clustering. Optimization Letters, 15(4):1033-1355 2021.
[25] Herman Müntz Solution directe de l'équation séculaire et de quelques problemes analogues transcendants. Comptes rendus de I' l'Académie des Sciences, 156:43-46, 1913.
[26] Andrew Ng. Michael Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm.
15th Advances in Neural Information Processing Systems (NeurIPS'O1), 14, 2001.
[27] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, Prettenhofer, R. Weiss, V. Dubourg. J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
[28] Richard Peng, He Sun, and Luca Zanetti. Partitioning well-clustered graphs: Spectral clustering works! SIAM Journal on Computing, 46(2):710-743 2017.
[29] William M. Rand. Objective criteria for the evaluation of clustering methods. Journal of the
American Statistical Association, 66(336):4468555 1971.
[30] He Sun and Luca Zanetti. Distributed graph clustering and sparsification. ACM Transactions on Parallel Computing (TOPC), 1-3):1-23, 2019.
[31] Joaquin Vanschoren, Jan N. van Rijn, Bernd Bischl, and Luis Torgo Openml: networked science in machine learning. SIGKDD Explorations, 15(2):49-60, 2013.
[32] Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, C Carey, ilhan Polat, Yu Feng, Eric W. Moore, Jake VanderPlas, Denis Laxalde, Josef Perktold, Robert Cimrman, Ian Henriksen, E. A. Quintero, Charles R. Harris, Anne M. Archibald, Antônio Ribeiro, Fabian Pedregosa, Paul van Mulbregt, and SciPy 1.0 Contributors. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261-272, 2020.
[33] Ulrike Von Luxburg. A tutorial on spectral clustering. Statistics and computing, 17:395-416. 2007.
[34] Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07744 2017.
[35] Donghui Yan, Ling Huang, and Michael Jordan. Fast approximate spectral clustering. In Proceedings of the 15th ACM SIGKDD international conference on Knowledge discovery and duta mining (KDD'09 '09), pages 907-916, 2009.
11

---

A Omitted detail from Section 3
In this section, we prove the main theoretical result of the paper. In order that this section is self- contained, we repeat some of the steps included in the main paper. We first show that the lengths of the random vectors 2; generated Algorithm 2 are close to their expected value. Notice that [1]a:]112] = vi and E. [P:l2ll = Vk. We use Chebyshev's inequality to show the following. Lemma A.1. Lel fi...., f& IR be orthogonal vectors and let = Σ f.f! be the projection onto the space spanned by fI...., fk. With probability at least 1 - (1/10k),
Rn be drawn from the n-dlmmensional Gaussian distribution N(O, I). Let
|Prll2 VGl, and
. | S 6n.
Proof of Lemma Since drawn from symmetric n--dimensional Gaussian distribution, ||>:|| distributed according to x² distribution with degrees of freedom. Similarly, since P is projection matrix, ||Px|| 2 is distributed according to x² distribution with & degrees of freedom. By the Chebyshev inequality, we have that
Pr
Pxx
6k
<
(5k))2
25k
and
Pr ||
12
Gn
S
(5n)²
25m
The lemma follows by the union bound and since k
We now show that the output of the POWERMETHOD algorithm is close to a random vector in the space spanned by fi...., fu-
Let M gax= be matrix with eigenvalues 1 711 ... > Tn 0 and corresponding eigenvectors fi.... Let ao E I2" be drawn from the n-dimensional Gaus- sian distribution NO.,I). Let Ia POWERMETHOD(MA No, for t θ @(lo(nn/²k)) Tik 2 1 (o((elog(//ek))) and 7++1 S 1 (2(1), then with probability least 1/(kk)).
Lemma 3.1
||.,
Parll2 S eVT.
where P = Ek fif! is the projection onto the space spanned by the first le eigenvectors of M.
Proof of Lemma 3.7
By the assumptions of the Lemma, we can assume that
74+1 S c1 < 1,
c log (2mm/ and
t = c3 (og(224//22k)
for constants C₁. c2 and c3. Fixing < 1, we will set
1
03
2 log
and
C2 2/66
Furthermore, by Lemma A.1 with probability at least (1/10k) holds that
P 2 - v6k
12

---

and
<oll2 S V6n,
and we assume that this holds in the remainder of the proof.
Now, we write zy in terms of its expansion in the basis given by the eigenvectors fi...., fn:
Gj affs:
Ø=1
where aj (wo, fz). Similarly, we have
Pao
agf$
j=1
and
a 2t Σ
anfsfz.
j=1
Then,
k
a P l2
(1n)) (g)) fj +
Σ antsss
j=1
j=++1
k
<
Σ
(aj7) aj) fz
+
Σ
==
j=++1
2
k
(1
7k
Σ
offt
+
nht1 Σ
azfs
Ø=1
j=k+1
71 Pooll 21 + 7/44 (I P) xoll2
< (1 %) P ll2 + 7 ||20ll22
where we used the fact that 1 2 2 2 nn- Now, we have
* 2 (1 C2e log (ogg22n/e2/ 1)
ea log(2an/cPk)
2 C2036
= 1 6
2/6'
Furthermore,
2h+1 S C1
<a log (2g(22n/e2k)
loggle
2
es log(1//e)
24n
<V
24n
Combining everything together, we have
k
| Pxoll2
<
P + +eV
|
2
24n
6kn
< 2
V6k + Ev
24n
$ kk,
which completes the proof.
13

---

remains to prove that the k-means cost is preserved in the embedding produced by the power method.
Recall that fi..... f& are the eigenvectors of M corresponding to the eigenvalues "...... 7 and y1..... are the vectors computed in Algorithmß We will also consider the vectors 21,.... given by 2, Pæ,, where {x; are the random vectors sampled in Algorithm
.
2 and P Σ f:f.
the projection onto the space spanned by fi..... fk. We also define
1 yt
fi
fk
y1
and Z
21
21
We will use the following result shown by Makarychev et al. 23
Lemma 3.2 [23), Theorem 1.3). Given data X gn*k let II E Rexi be random matrix with each column sampled from the k-dimensional Gaussian distribution N(0, I&) and
1 1 1 log(k) + (ogg(/e)) +b0((())))
2
Then, with probability at least it holds for all partitions {Ai]i=z of [n] that
COST (A1, A&) E (1 x) AA).
Applying this lemma with X = F and II = FTZ shows that the k-means cost is approximately equal in the embeddings given by F and D D-&Z, since FFTZ = Z and each of the entries of FTZ is distributed according the Gaussian distribution N(0, 1). By Lemma 3.1 we also show that the k- k-means objective in D 3 Y within an additive error of D Z. This allows to prove the following lemma.
Lemma
3.3
With probability at least 0.9 for any partitioning {A. of the vertex set V, we
have
COSTD-1AY(AI.... As) 2 (1 -)COSTp-///AAAA........ AA) - ek
and
(OSTD-I/AY(A1...... Ax) s (1 + C)CTT) A+) ck.
In order to prove this, will use the fact shown by Boutsidis and Magdon-Ismail that we can write the k-means cost as
COST BO A&) = B XXTBI|
where X E gaak is the indicator matrix the partition, defined by
if A otherwise
X(u,i)
VIAi
and B A (E., 1/2 is the Frobenius norm.
Proof of Lemma 3.3 Notice that FTZ E Rix! is random matrix with columns drawn from the
standard k-dimennional Gaussian distribution. Then, by Lemma 3.2 with probability at least 1 c, we have for any partition {A that
COSTD-1/ap(A, (A.... A&) (1 1 (
A&e
(2)
since D-1/2 1-1/2 D -1/22, where we use the fact that the columns of are in the span of fi
Furthermore, by the union bound, can assume with probability at least 0.9 that the conclusion of Lemma 3.J holds for every vector y: computed by Algorithm 2
Now, will establish that COST (OSTD-1/aY() (-) is close to COST (+) which will complete the proof. For some arbitrary partition (A let X be the indicator matrix of the partition. Then,
14

---

have
D 1-1/2 XXTD Y/2Y
D 1/22 - XXTD 1/22
F
(I- DI-XXIDD-1/2 1/2
(I-XTT) D -/1
(I- XXT) -Z))
(I XX 2)
Y Z
1 2:12
Vlekk
S ck:
Where use Lemma
3.1 and the fact that / k. Combining this with 2 completes the proof.
Now we come to the proof of the main theorem.
Theorem 3.1. Let G be graph with λR+1 =2(1) and p(k) O(c log(n/c)-1)) Additionally, let
{Sitez 1 be the k-way partition corresponding to p(k) and suppose that { are almost balanced.
Let (Ai k be the output of Algorithm 2
With probability least 0.9 E, there exists permutation
kk] + [k] such that
vol(A, O(e vol(V)))
Moreover, the running time of Al Algorithm 2
Óm 2 TKM(n, k. I),
where is the number of edges in G and TRM(n, k 1) is the running time of the k-means approxi- mation algorithm on n points in I dimensions.
To complete the proof, we will make use of the following results proved by Macgregor and Sun 21 which hold under the same assumptions as Theorem 3.1
Lemma
3.4
21
Lemma 4.1). There exists partition (A,) the vertex set V such that
COSTD-vap(AI.... Ax) < k p(k)//u+))
Lemma 3.5
(21]
Theorem 2). Given some partition of the vertices, {A, such that
COSTp-1/ap(A AA)
then there exists a permutation a [k] + [k] such that
vol (o, ((c-vol(V)))
Proof of Theorem 3.1 By Lemma 3.4 and Lemma 3.3 with probability at least 0.9 e, there exists
some partition {A of the vertex set VG such that
COSTD-WAY As) = - log(n/e)
ek + ek
Since we use constant-factor approximation algorithm for k-means, the partition (4,) returned by Algorithm 2 satisfies COST 1/2x(A1,
(Ai,..., AA) O(ck). Then, by Lemma 3.3 Lemmal 3.3
for some permutation a [k] + [k). we have
vol( (A,45)))))))) O(e vol(Ve))
15

---

To bound the rumning time, notice that the number of non-zero entries in M is 2m, and the time complexity of matrix multiplication proportional to the number of non-zero entries. Therefore. the running time of POWERMETHOD zo, t) is (m). Since the loop Algorithm 2 is executed (log(k)) E 2) times, the total running time of Algorithm 2 is O (m 2) + TKM (n, k. ().
16


Reviews:
[{"review_id": "Cgl7cnJiuw", "reviewer": "Reviewer_1Mto", "summary": "The paper proposes a new fast spectral clustering algorithm. The main idea of the algorithm is to, rather than embed the vertices according to the k eigenvectors of the graph Laplacian, use the power method to efficiently approximate a random projection of the spectral embedding. Then, as in the classical spectral clustering algorithm, a k-means clustering algorithm is used to partition the vertices into k clusters.\n\nThe paper starts by discussing relevant preliminaries such as conductance, a higher order Cheeger inequality, the k-means objective and the power method. Next, the result is proven that if the k-th eigenvalue of the matrix M is close to 1 then the power method can be used to compute a random vector in the span of the first k eigenvectors of M. The authors then present their fast spectral clustering algorithm. They proceed to give a bound on the number of misclassified vertices by their proposed algorithm, and analyze the time complexity of the method. Finally, the authors sketch the proof of their main result, building on a recent result by Makarychev et al [22] which states that a random projection of data onto O(log(k)) dimensions preserves the k-means objective function for all partitions of the data with high probability.\n\nIn the experimental section, the proposed algorithm is evaluated on synthetic data under the stochastic block model as well as some medium-sized real world datasets. The algorithm is compared to the classical spectral clustering algorithm using k as well as log(k) eigenvectors as well as the power method using k eigenvectors. The authors observe that the proposed method is much faster than competing methods when increasing the number of clusters and number of vertices in the stochastic block model. The same observation is done on the real world datasets, while achieving comparable clustering accuracy.", "questions": "How does the method perform against other fast spectral clustering techniques such as Choromanska et al [4] or Yan et al [34]?", "limitations": "The paper discusses the limitations of the proposed approach which is that it leads to a trade-off in terms of clustering accuracy compared to classical spectral clustering. There are no potential negative societal impacts of the work.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The paper proposes a new algorithm for fast spectral clustering which is simple and easy to implement. The key technical contribution is a proof that they can efficiently compute an approximation of a random projection on the spectral embedding without computing the spectral embedding itself. The proposed method improves on the algorithm by Boutsidis et al [4] both in theory (as it has better time complexity, and an upper bound on the total misclassified vertices is given), as well as in practice on a number of datasets. The improved efficiency of the algorithm allows it to be applied for problems with a large amount of vertices and clusters.", "weaknesses": "The main weakness of the paper is the limited experimental evaluation. The paper only compares to the method by Boutsidis et al [4] as well as the classical spectral clustering algorithm with k or log(k) eigenvectors. A plethora of algorithms have been proposed to do fast approximate spectral clustering. The paper even mentions the algorithms by Choromanska et al [4] and Yan et al [34] but an experimental comparison to these methods is missing. While the proposed method always outperforms the other considered methods in terms of runtimes, it is in some cases significantly worse in terms of ARI and NMI score (in particular for the MNIST, Fashion and HAR datasets). It would be interesting to see if some of the other competing methods achieve a better trade-off here. \n\nMoreover, one of the main selling points of the algorithm is its better time complexity and scalability compared to standard spectral clustering. However, the evaluation is done on relatively small datasets of up to 70000 vertices. The paper could be made stronger by also showing the results on some larger datasets where standard spectral clustering is not applicable any more. \n\nFinally, the paper might also benefit from an evaluation in terms of the conductance score since it is the underlying objective used in spectral clustering.\n\n\n====\nEdit after Rebuttal:\n\nIn their rebuttal, the authors have provided some additional experiments and pointed out some additional results in the paper. I have therefore increased my score.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful review. We respond to your questions regarding the experimental evaluation below.\n\n**Comparison with additional methods.**\nTable 1 in the attached PDF includes additional experimental results for the KASP algorithm proposed by Yan et al. [34].\nWe find that on real-world data, the Nystrom method proposed by Choromanska et al. [4] produces poor results with an ARI consistently below $0.01$.\nWe note that in the original paper [4], only small toy datasets are used to evaluate the algorithm and conclude that this method is not practical for real-world data.\nWe will include these results and some more discussion in the final version of the paper.\n\n**Comparison on larger datasets.**\nWe highlight the experiments on data drawn from the Stochastic Block Model (SBM).\nIn particular, Figure 2(a) compares the running time of spectral clustering on massive graphs with a large number of clusters.\nWe observe that on a graph with 400,000 vertices and 400 clusters, our newly proposed algorithm is able to recover the ground truth clusters in under 20 seconds, while classical spectral clustering cannot be applied in this instance.\n\n**Evaluation in terms of conductance.**\nWe include an evaluation in terms of conductance in Table 1 of the attached PDF.\n"}, {"review_id": "kiDkrqDNwn", "reviewer": "Reviewer_2unS", "summary": "The paper proposes a new spectral clustering algorithm that  instead of computing $k$-leading eigenvectors, the authors proposes to use power method to embed the nodes into a $\\log(k)$ dimension space, which saves computational time when $k$ is large. Theoretical guarantees on misclassification rate with constant probability is provided under balanced cluster setting. Experiments on simulated network and $k$-NN graphs on real datasets are provided to show the effectiveness of the proposed algorithm.", "questions": "- Could the authors have a study on why for Letter dataset $k$ and $\\log(k)$ EIGS takes so much more time than PM $k$/$\\log(k)$? Did you also use power method to compute the leading $k$-eigenvectors? Since Letter dataset has fewer nodes than other datasets, but slightly larger $k$, it is very strange that the competing time difference is so much than other datasets.\n- Why do you not use misclassification accuracy for the experiments since it is the main theoretical result you have?", "limitations": "I do not see a section stating or broader impact of the work. The authors discussed about the limitations in conclusion section.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The idea on projecting the nodes to $\\log(k)$ random space for spectral clustering is novel and interesting. \n- The paper is well written and easy to follow\n", "weaknesses": "- The theoretical guarantee is limited on balanced cluster case and it is not a high probability bound\n- The real data experiments are not convincible as \n  - The authors manually construct $k$-NN graphs from some real data, instead of directly using existing real graph data. \n  - The authors did not study how sparsity of the network may affect the results. For example, real networks are usually very sparse, will the accuracy be hurt more for the proposed methods under this case? For sparse networks, computing $k$-leading eigenvectors is not that expensive, and the advantage on the proposed method on computing speed may not be that significant, from Table 1, the computing speed up on most of the datasets are not that remarkable.\n  - It is not clear for real dataset how balanced are the clusters.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your time and thoughtful comments.\nWe respond to each of your questions below.\n\n**Further study of the Letter dataset.**\nFor computing the eigenvectors, we use the Implicitly Restarted Arnoldi Method (IRAM) provided by the eigsh method in the Python scipy library, which itself uses the ARPACK Fortran library.\nIt is not immediately clear why this performs so poorly on the Letter dataset, although we observe that the spectrum of the $k$ nearest neighbour graph has many eigenvalues very close to $0$.\nIt may be that this causes the IRAM algorithm to converge slowly, while our algorithm requires only to approximate a random vector in the space spanned by the bottom $k$ eigenvectors and does not need to distinguish between eigenvectors with very similar eigenvalues.\n\n**Evaluating with misclassification accuracy.**\nWhile the misclassification accuracy is used in the theoretical guarantee of the algorithm, it is difficult to compute since it requires iterating over $k!$ possible permutations of the clusters.\nInstead, we evaluate with the Adjusted Rand Index (ARI) and Normalised Mutual Information (NMI) which are the standard metrics for evaluating clustering tasks.\n\n**Balanced assumption.**\nWe address the balanced cluster assumption in our top-level comment.\n\n**Probability bound.**\nRegarding the probability bound, we report a probability of success of $0.8$ in the paper.\nNote that by running $O(\\log(1 / \\epsilon))$ copies of the algorithm, the success probability can be boosted to $1 - \\epsilon$, for any $\\epsilon$.\n\n**Evaluation on $k$-NN graphs.**\nIn practice, the most common application of spectral clustering is on similarity graphs constructed from real data, such as $k$-NN graphs or kernel similarity graphs.\nAs such, we feel that these experiments are a fair test of practical applications.\n\n**Sparsity.**\nWe address the effect of the network sparsity in our top-level comment."}, {"review_id": "rFTzDc3xdL", "reviewer": "Reviewer_8rfq", "summary": "The paper deals with the problem of spectral clustering in networks. The paper proposes a fast spectral clustering method by utilizing the power method and random projection. The paper also provides theoretical guarantee of cluster recovery.", "questions": "(1) How does the proposed algorithm depend on the sparsity of the network?\n\n(2) What should be the choice of the constants in Algorithms 1 and 2 in terms of O(log(n/k)) and O(log(k))?", "limitations": "N/A", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The main strengths of the paper are - \n\n(1) The paper provides a fast spectral clustering algorithm using the power method and random projections.\n\n(2) The paper provides theoretical results on cluster recovery based on the proposed method.\n\n(3) The paper provides a simulation study of the method and applies the proposed method to a few real-world networks.\n\n(4) The paper is well-written.", "weaknesses": "The main weaknesses of the paper are - \n\n(1) The paper extends the recent breakthrough on o(log(k))-embedding of vertices for cluster recovery. The use of the power method as a proxy for eigenvectors is not particularly novel.\n\n(2) The stopping criteria in Algorithms 1 and 2 are in terms of order of log(n/k). The dependence of the results on the constants is not clear.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your time and thoughtful review. We respond to your specific questions below.\n\n**Question 1.**\nWe address the effect of the network sparsity in our top-level comment.\n\n**Question 2.**\nThis is a good question, and it is an example of a place where theory and practice diverge.\nIn theory, the required constants are the ones from the analysis of Makarychev et al. [22] and as is common for a theoretical result, the constants in the big-O notation are not calculated explicitly (and are themselves based on previous theoretical results with non-explicit constants!).\n\nAs we mention in Remark 3.3, in practice we find that setting $l \\triangleq \\left\\lceil \\log(k) \\right\\rceil$ and $t \\triangleq \\left\\lceil 10 \\cdot \\log(n / k) \\right\\rceil$ works well."}, {"review_id": "RCGH8MlTox", "reviewer": "Reviewer_6nQB", "summary": "This paper proposed a new spectral-based graph clustering algorithm. The main novelty of this algorithm is a fast implementation of vertex embedding, built on the power method. \n\nPrevious algorithms achieved a low dimensional embedding via two steps: \n1) compute k eigenvectors of the graph Laplacian matrix; \n2) embed k dimension datapoint into (log k)-dimension via a random projection. \n\nUnder this approach, the first step may cost a lot of time, i.e., $O(kn^2)$ in a worst-case analysis. This paper simplifies this step with a power method. Concretely, their algorithm starts with (log k) random vectors $x_1,\\dots,x_r$, and calculates $M^{t} x_{i}$. The authors showed that the vectors obtained in this way can approximate random vectors from the eigenspace of $M$. For a sparse matrix $M$, this approach can be implemented much faster. Specifically, if $M$ is a graph matrix, this algorithm can be implemented in time linear in the size of $G$.\n\nPower methods are a very well known approach to approximate eigenvectors. We can usually approximate the first eigenvector very fast for sparse matrices. However, for the second eigenvector, the running time might be slower since the matrix is no longer sparse after removing the largest eigenvector. The beauty of this paper is that we can approximate all $k$ eigenvectors in one shot in some settings. However, there is no free lunch. The main theorem of this paper requires the size of clusters should be balanced. I think this assumption plays a crucial role in this algorithm.", "questions": "Could the authors address my concerns about the unbalanced cases?", "limitations": "I have included my suggestions in the weakness part.", "rating": 4, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "1. This paper provides a nice idea to approximate the eigenvectors of the graph Laplacian matrix. The running time of this algorithm is much faster than the previous algorithms.\n\n2. The theoretical analysis is solid and interesting!\n\n3. The power method has good potential. Beyond approximating top eigenvectors, it might have applications in different steps of clustering.", "weaknesses": "I first list some minor cons in this paper.\n\n1. It requires the knowledge of k\n\n2. The parameter q is too small in the SBM simulation.\n\n3. The authors used some subjective words to describe their algorithm, such as they call their algorithm a simple algorithm, and their assumptions in the main theorem are natural assumptions. I disagree with the second statement and find these assumptions to be not natural at all. However, I agree that this is a subjective viewpoint and thus put this as a minor con.\n\n4. In the real dataset experiments, it seems that none of the four algorithms are very exciting. For example, the highest NMI achieved for MNIST is 0.74 by spectral clustering through k eigenvectors. However, a quick online search shows that there are many  algorithms with NMI higher than 0.9. See the link: https://paperswithcode.com/sota/image-clustering-on-mnist-full \n\n5. My main concern in this paper is the balancedness assumption. This assumption is not true in many applications. In addition, I think this assumption is crucial for the performance of the algorithm (and not just the analysis), meaning this is an inherent barrier. If the authors want to make this algorithm useful in practice, I think this is a must-be-addressed issue. I am happy to increase my evaluation if the authors can address this barrier. Let me ask a concrete question. Let’s consider the following SBM setting with p = 0.01 and q=0.00001. We assume there is a large cluster of size n/2, and the rest of the clusters have size n^{0.99}/2. Could this power method-based algorithm recover these clusters? Regarding the experiments part, I know that MNIST and Pen Digits are balanced datasets. Are there any unbalanced datasets in the experiments? The authors did not mention the size of each cluster in the paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Many thanks for your detailed and thoughtful review and questions.\n\n**Balancedness assumption.**\nWe address the balancedness assumption in our top-level comment.\nFurthermore, in the attached PDF, we include the results of the requested SBM experiment. \nWe set $p = 0.01$ and $q = 0.00001$ as suggested, and let one cluster have size $n / 2$ and the others have size $n^{0.7} / 2$.\nNote that we use a smaller power of $n$ than suggested in order that the number of small clusters grows faster.\nWe find that our algorithm is able to successfully recover the imbalanced clusters under this regime.\n\nThank you for raising this question, and for the concrete suggestion. We will add some discussion on the imbalanced case to the next version of the paper, and include the additional experiment.\nWe hope that you will consider increasing your evaluation based on this and we are happy to continue the discussion if you have further questions.\n\n**Weakness 1.**\nNote that this is a weakness of spectral clustering in general.\nIn fact, our algorithm is less susceptible to this weakness than previous spectral clustering algorithms since it is easier to 'guess' a value for $\\log(k)$ - in practice, you can often just use a small constant.\nThen well-established heuristics for picking $k$ for the $k$-means step can be applied.\n\n**Weakness 2.**\nWe have chosen $q$ in the SBM experiments such that the expected conductance of the generated clusters remain constant while $k$ grows.\n\n**Weakness 3.**\nWe understand your point about the use of the phrase 'natural assumptions'. We follow many previous works in the graph clustering literature which make assumptions on the value of $\\lambda_{k+1}$ and $\\rho(k)$ [15, 19, 21, 23, 27].\n\n**Weakness 4.**\nWe agree that spectral clustering does not approach the state of the art on these datasets, and we cannot claim to compete with supervised methods.\n\n**Weakness 5.** See our answer above.\n"}, {"review_id": "msGIAEU9rw", "reviewer": "Reviewer_6vxh", "summary": "The paper is concerned with the spectral method for clustering vertices of graph. Specifically, the authors find that the classical spectral clustering methods need eigendecomposition of the graph Laplacian matrix which is computationally expensive, and that the authors propose to use a power method to bypass this computation-demanding part. The essence is that the power method is a random projection of the eigendecomposition into subembeddings. \n\nIn general, I do find that the idea of the paper is novel, and that the theoretical and experimental results are convincing.", "questions": "The authors claim that the codes are released. however, I don't see them anywhere mentioned in the paper.\n\npp. 3. l91. The definition of vol is not clear.\n\npp. 5. l132. Definition of the inner product is not clear. Is it a dot product, or E[<.,.>], since you have random variable?\n\npp. 5. l142. Is it 1/100k or 1/(100k)?\n\npp. 5. l143. Should it be bold face P?", "limitations": "No. The authors did not discuss the limitations of their method.", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "The proposed algorithm is very simple to understand and implement. Moreover, the authors have provided both theoretical and experimental results to prove that the algorithm is valid and novel.\n\nThe structure of the paper is engaging and is written easy to follow.", "weaknesses": "The experiments only compared to the classical eigendecomposition-based methods. It is true that the demanding computation of the embedding step motivates the authors to use a power method for the random project, however, I am not convinced that the eigendecomposition is the only method to do the graph clustering. The authors should add both empirical discussion and experiments to other such related methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your positive review. We address your questions below.\n\n**Code.**\nThe code to reproduce our experiments is included with the submission in the supplementary material.\nWhen the paper is published, we will make the code publicly available online.\n\n**Editorial points.**\nThank you for your editorial points, we will update the paper based on your feedback.\nOn line 132 it is a dot product not an expectation, and line 142 should be $1 / (100k)$ - we will make this clearer."}]

Author rebuttal:
We thank the reviewers for their time and thoughtful reviews.
Here we respond to questions which were shared by more than one reviewer, and we respond to other questions individually with reference to figures in the attached PDF.

**Balanced clusters assumption.**
The balanced cluster assumption is not integral to the proof of the theorem and without the assumption, we can obtain the same result under a slightly tighter assumption on the $k$-way conductance $\rho(k)$. Specifically, for a graph without balanced clusters, if $\rho(k) = O\left(\epsilon \cdot k^{-1} \cdot \log(n / \epsilon)^{-1} \right)$ then we obtain the same guarantee as stated in Theorem 3.1.
We will add some discussion to the next version of the paper.

In the attached PDF, we include some additional experimental results on an SBM with imbalanced clusters as requested by Reviewer 6nQB.
These results demonstrate that in practice, our algorithm is able to recover imbalanced clusters.

**Effect of network sparsity.**
The asymptotic running time of our algorithm for computing the vertex embedding is $\widetilde{O}\left(m \cdot \epsilon^{-3}\right)$, where $m$ is the number of *edges* in the graph.
Thus, the running time of our algorithm scales linearly with the sparsity of the graph.
Moreover, we highlight that in our experiments on real-world data, we use the $k$ nearest neighbour graph with $k = 10$, which results in a sparse graph with $m = \Theta(n)$.


Meta-review: This paper proposes an efficient approach for spectral clustering by projecting the graph's vertices into O(log(k)) dimensions with the power method. The reviewers appreciate the proposed approach's technical contribution and the paper's reliable experimental results. Since all the reviewers are positive for the paper, I recommend accepting the paper.
Decision: Accept (poster)