# A Tighter Analysis of Spectral Clustering, and Beyond111A preliminary
version of this work appeared at ICML 2022. This work is supported by a
Langmuir PhD Scholarship, and an EPSRC Early Career Fellowship (EP/T00729X/1).

Peter Macgregor
University of Edinburgh  He Sun
University of Edinburgh

###### Abstract

This work studies the classical spectral clustering algorithm which embeds the
vertices of some graph $G=(V_{G},E_{G})$ into $\mathbb{R}^{k}$ using $k$
eigenvectors of some matrix of $G$, and applies $k$-means to partition $V_{G}$
into $k$ clusters. Our first result is a tighter analysis on the performance
of spectral clustering, and explains why it works under some much weaker
condition than the ones studied in the literature. For the second result, we
show that, by applying fewer than $k$ eigenvectors to construct the embedding,
spectral clustering is able to produce better output for many practical
instances; this result is the first of its kind in spectral clustering.
Besides its conceptual and theoretical significance, the practical impact of
our work is demonstrated by the empirical analysis on both synthetic and real-
world datasets, in which spectral clustering produces comparable or better
results with fewer than $k$ eigenvectors.

(a) Original Image

(b) $6$ clusters with $3$ vectors

(c) $6$ clusters with $6$ vectors

(d) Original Image

(e) $45$ clusters with $7$ vectors

(f) $45$ clusters with $45$ vectors

Figure 1: Examples of image segmentation using spectral clustering; the
original images are from the BSDS. The Rand Index of segmentation (b) is
$0.83$, while (c) has Rand Index $0.78$. Segmentation (e) has Rand Index
$0.92$, and (f) has Rand Index $0.80$. Hence, it’s clear that spectral
clustering with fewer than $k$ eigenvectors suffices to produce comparable or
better output.

##  1 Introduction

Graph clustering is a fundamental problem in unsupervised learning, and has
comprehensive applications in computer science and related scientific fields.
Among various techniques to solve graph clustering problems, spectral
clustering is probably the easiest one to implement, and has been widely
applied in practice. Spectral clustering can be easily described as follows:
for any graph ${G}=({V}_{G},{E}_{G})$ and some $k\in\mathbb{Z}^{+}$ as input,
spectral clustering embeds the vertices of ${V}_{G}$ into $\mathbb{R}^{k}$
based on the bottom $k$ eigenvectors of the Laplacian matrix of ${G}$, and
employs $k$-means on the embedded points to partition ${V}_{G}$ into $k$
clusters. Thanks to its simplicity and excellent performance in practice,
spectral clustering has been widely applied over the past three decades
[ST96].

In this work we study spectral clustering, and present two results. Our first
result is a tighter analysis of spectral clustering for well-clustered graphs.
Informally, we analyse the performance guarantee of spectral clustering under
a simple assumption222This assumption will be formally defined in Section 3.
on the input graph. While all the previous work (e.g., [LGT14, KM16, Miz21,
PSZ17]) on the same problem suggests that the assumption on the input graph
must depend on $k$, our result demonstrates that the performance of spectral
clustering can be rigorously analysed under a general condition independent of
$k$. To the best of our knowledge, our work presents the first result of its
kind, and hence we believe that this result and the novel analysis used in its
proof are important, and might have further applications in graph clustering.

Secondly, we study the clustering problem in which the crossing edges between
the optimal clusters $\\{{S}_{i}\\}_{i=1}^{k}$ present some noticeable
pattern, which we call the _meta-graph_ in this work. Notice that, when
viewing every cluster ${S}_{i}$ as a “giant vertex”, our meta-graph captures
the intrinsic connection between the optimal clusters, and could be
significantly different from a clique graph. We prove that, when this is the
case, one can simply apply classical spectral clustering while employing fewer
than $k$ eigenvectors to construct the embedding and, surprisingly, this will
produce a better clustering result. The significance of this result is further
demonstrated by our extensive experimental analysis on the well-known BSDS,
MNIST, and USPS datasets [AMFM11, LBBH98, Hul94]. While we discuss the
experimental details in Section 6, the performance of our algorithm is
showcased in Figure 1: in order to find $6$ and $45$ clusters, spectral
clustering with $3$ and $7$ eigenvectors produce better results than the ones
with $6$ and $45$ eigenvectors according to the default metric of the BSDS
dataset.

#### Related work.

Our first result on the analysis of spectral clustering is tightly related to
a number of research that analyses spectral clustering algorithms under
various conditions (e.g., [LGT14, KM16, Miz21, GT14, NJW01, PSZ17]). While we
compare in detail between these works and ours in later sections, to the best
of our knowledge, our work presents the first result proving spectral
clustering works under some general condition independent of $n$ and $k$. Our
work is also related to studies on designing local, and distributed clustering
algorithms based on different assumptions (e.g., [CPS15, OA14, ALM13]); due to
limited computational resources available, these works require stronger
assumptions on input graphs than ours.

Our second result on spectral clustering with fewer eigenvalues is linked to
efficient spectral algorithms to find cluster-structures. While it’s known
that flow and path structures of clusters in digraphs can be uncovered with
complex-valued Hermitian matrices [CLSZ20, LS20], our work shows that one can
apply real-valued Laplacians of undirected graphs, and find more general
patterns of clusters characterised by our structure theorem. Rebagliati and
Verri [RV11] propose using more than $k$ eigenvectors for spectral clustering,
although their assumptions on the input graph are different to ours and so the
result is not directly comparable.

##  2 Preliminaries

Let ${G}=({V}_{G},{E}_{G},{w})$ be an undirected graph with $n$ vertices, $m$
edges, and weight function
${w}:{V}_{G}\times{V}_{G}\rightarrow\mathbb{R}_{\geq 0}$. For any edge
$e=\\{u,v\\}\in{E}_{G}$, we write the weight of $\\{u,v\\}$ by ${w}_{uv}$ or
${w}_{e}$. For a vertex $u\in{V}_{G}$, we denote its _degree_ by
${d}_{G}(u)\triangleq\sum_{v\in{V}}{w}_{uv}$. For any two sets
${S},{T}\subset{V}_{G}$, we define the _cut value_
${w}({S},{T})\triangleq\sum_{e\in{E}_{G}({S},{T})}{w}_{e}$, where
${E}_{G}({S},{T})$ is the set of edges between ${S}$ and ${T}$. For any set
${S}\subseteq{V}_{G}$, the _volume_ of ${S}$ is
$\mathrm{vol}_{G}({S})\triangleq\sum_{u\in{S}}{d}_{G}(u)$, and we write
$\mathrm{vol}({G})$ when referring to $\mathrm{vol}({V}_{G})$. For any
nonempty subset ${S}\subseteq{V}_{G}$, we define the _conductance_ of ${S}$ by

$\Phi_{G}({S})\triangleq\frac{{w}({S},{V}\setminus{S})}{\mathrm{vol}_{G}({S})}.$

Furthermore, we define the conductance of the graph ${G}$ by

$\Phi_{G}\triangleq\min_{\begin{subarray}{c}{S}\subset{V}\\\
\mathrm{vol}({S})\leq\mathrm{vol}({V})/2\end{subarray}}\Phi_{G}({S}).$

We call subsets of vertices ${A}_{1},\ldots,{A}_{k}$ a _k-way partition_ of
${G}$ if ${A}_{i}\cap{A}_{j}=\emptyset$ for different $i$ and $j$, and
$\bigcup_{i=1}^{k}{A}_{i}={V}$. Generalising the definition of conductance, we
define _$k$ -way expansion constant_ by

$\rho(k)\triangleq\min_{\mathrm{partition}\ {A}_{1},\ldots,{A}_{k}}\max_{1\leq
i\leq k}\Phi_{G}({A}_{i}).$

Next we define the matrices of any ${G}=({V}_{G},{E}_{G},{w})$. Let
${D}_{G}\in\mathbb{R}^{n\times n}$ be the diagonal matrix defined by
$({D}_{G})_{uu}={d}_{G}(u)$ for all $u\in{V}_{G}$, and we denote by
${A}_{G}\in\mathbb{R}^{n\times n}$ the _adjacency matrix_ of ${G}$, where
$({A}_{G})_{uv}={w}_{uv}$ for all $u,v\in{V}_{G}$. The _normalised Laplacian
matrix_ of ${G}$ is defined by
${\mathcal{N}}_{G}\triangleq{I}-{D}^{-\frac{1}{2}}_{G}{A}_{G}{D}^{-\frac{1}{2}}_{G}$,
where ${I}$ is the $n\times n$ identity matrix. Since ${\mathcal{N}}_{G}$ is
symmetric and real-valued, it has $n$ real eigenvalues denoted by
$\lambda_{1}\leq\ldots\leq\lambda_{n}$; we use ${f}_{i}\in\mathbb{R}^{n}$ to
denote the eigenvectors corresponding to $\lambda_{i}$ for any $1\leq i\leq
n$. It is known that $\lambda_{1}=0$ and $\lambda_{n}\leq 2$ [Chu97].

For any sets ${S}$ and ${T}$, the symmetric difference between ${S}$ and ${T}$
is defined by

${S}\triangle{T}=({S}\setminus{T})\cup({T}\setminus{S}).$

For any $k\in\mathbb{Z}^{+}$, we define $[k]\triangleq\\{1,\ldots,k\\}$. We
sometimes drop the subscript ${G}$ when it is clear from the context. The
following higher-order Cheeger inequality will be used in our analysis.

######  Lemma 2.1 ([LGT14]).

It holds for any $k\in[n]$ that

$\lambda_{k}/2\leq\rho(k)\leq O\left(k^{3}\right)\sqrt{\lambda_{k}}.$

##  3 Encoding the Cluster-Structure into the Eigenvectors of
${\mathcal{N}}_{G}$

Let $\\{{S}_{i}\\}_{i=1}^{k}$ be any optimal $k$-way partition that achieves
$\rho(k)$. We define the indicator vector of cluster ${S}_{i}$ by

${\chi}_{i}(u)\triangleq\left\\{\begin{array}[]{ll}1&\mbox{if }u\in{S}_{i},\\\
0&\mbox{otherwise},\end{array}\right.$ (3.1)

and the corresponding _normalised indicator vector_ by

$\bar{{g}}_{i}\triangleq\frac{{D}^{\frac{1}{2}}{\chi}_{i}}{\|{D}^{\frac{1}{2}}{\chi}_{i}\|}.$

One of the basic results in spectral graph theory states that ${G}$ consists
of at least $k$ connected components if and only if $\lambda_{i}=0$ for any
$i\in[k]$, and
$\mathrm{span}\left(\\{{f}_{i}\\}_{i=1}^{k}\right)=\mathrm{span}\left(\\{\bar{{g}}_{i}\\}_{i=1}^{k}\right)$
[Chu97]. Hence, one would expect that, when ${G}$ consists of $k$ densely
connected components (clusters) connected by sparse cuts, the bottom
eigenvectors $\\{{f}_{i}\\}_{i=1}^{k}$ of ${\mathcal{N}}_{G}$ are close to
$\\{\bar{{g}}_{i}\\}_{i=1}^{k}$. This intuition explains the practical success
of spectral methods for graph clustering, and forms the basis of many
theoretical studies on various spectral clustering algorithms (e.g., [KLL+13,
LGT14, NJW01, vL07]).

Turning this intuition into a mathematical statement, Peng et al. [PSZ17]
study the quantitative relationship between $\\{{f}_{i}\\}_{i=1}^{k}$ and
$\\{\bar{{g}}_{i}\\}_{i=1}^{k}$ through the function $\Upsilon(k)$ defined by

$\Upsilon(k)\triangleq\frac{\lambda_{k+1}}{\rho(k)}.$ (3.2)

To explain the meaning of $\Upsilon(k)$, we assume that ${G}$ has $k$ well-
defined clusters $\\{{S}_{i}\\}_{i=1}^{k}$. By definition, the values of
$\Phi({S}_{i})$ for every ${S}_{i}$, as well as $\rho(k)$, are low; on the
other hand, any $(k+1)$-way partition of ${V}_{G}$ would separate the vertices
of some ${S}_{i}$, and as such $\rho(k+1)$’s value will be high. Combining
this with the higher-order Cheeger inequality, some lower bound on
$\Upsilon(k)$ would be sufficient to ensure that ${G}$ has exactly $k$
clusters. In their work, Peng et al. [PSZ17] assumes
$\Upsilon(k)=\Omega(k^{2})$, and proves that the space spanned by
$\\{{f}_{i}\\}_{i=1}^{k}$ and the one spanned by
$\\{\bar{{g}}_{i}\\}_{i=1}^{k}$ are close to each other. Specifically, they
show that

  1. 1.

every $\bar{{g}}_{i}$ is close to some linear combination of
$\\{{f}_{i}\\}^{k}_{i=1}$, denoted by $\widehat{{f}}_{i}$, i.e., it holds that

$\|\bar{{g}}_{i}-\widehat{{f}}_{i}\|^{2}\leq 1/\Upsilon(k);$

  2. 2.

every ${f}_{i}$ is close to some linear combination of
$\\{\bar{{g}}_{i}\\}_{i=1}^{k}$, denoted by $\widehat{{g}}_{i}$, i.e., it
holds that

$\|{f}_{i}-\widehat{{g}}_{i}\|^{2}\leq 1.1k/\Upsilon(k).$

In essence, their so-called structure theorem gives a quantitative explanation
on why spectral methods work for graph clustering when there is a clear
cluster-structure in ${G}$ characterised by $\Upsilon(k)$. As it holds for
graphs with clusters of different sizes and edge densities, this structure
theorem has been shown to be a powerful tool in analysing clustering
algorithms, and inspired many subsequent works (e.g., [CSWZ16, CPS15, KUK17,
KM16, LV19, Miz21, Pen20, PY20, SZ19]).

In this section we show that a stronger statement of the original structure
theorem holds under a much weaker assumption. Our result is summarised as
follows:

######  Theorem 1 (The Stronger Structure Theorem).

The following statements hold:

  1. 1.

For any $i\in[k]$, there is $\widehat{{f}}_{i}\in\mathbb{R}^{n}$, which is a
linear combination of ${f}_{1},\ldots,{f}_{k}$, such that

$\|\bar{{g}}_{i}-\widehat{{f}}_{i}\|^{2}\leq 1/\Upsilon(k).$

  2. 2.

There are vectors $\widehat{{g}}_{1},\ldots,\widehat{{g}}_{k}$, each of which
is a linear combination of $\bar{{g}}_{1},\ldots,\bar{{g}}_{k}$, such that

$\sum_{i=1}^{k}\left\|{f}_{i}-\widehat{{g}}_{i}\right\|^{2}\leq
k/\Upsilon(k).$

###### Proof.

Let
$\widehat{{f}}_{i}=\sum_{j=1}^{k}\langle\bar{{g}}_{i},{f}_{j}\rangle{f}_{j}$,
and we write $\bar{{g}}_{i}$ as a linear combination of the vectors
${f}_{1},\ldots,{f}_{n}$ by
$\bar{{g}}_{i}=\sum_{j=1}^{n}\langle\bar{{g}}_{i},{f}_{j}\rangle{f}_{j}$.
Since $\widehat{{f}}_{i}$ is a projection of $\bar{{g}}_{i}$, we have that
$\bar{{g}}_{i}-\widehat{{f}}_{i}$ is perpendicular to $\widehat{{f}}_{i}$ and

$\displaystyle\left\|\bar{{g}}_{i}-\widehat{{f}}_{i}\right\|^{2}$
$\displaystyle=\left\|\bar{{g}}_{i}\right\|^{2}-\left\|\widehat{{f}}_{i}\right\|^{2}$
$\displaystyle=\left(\sum_{j=1}^{n}\langle\bar{{g}}_{i},{f}_{j}\rangle^{2}\right)-\left(\sum_{j=1}^{k}\langle\bar{{g}}_{i},{f}_{j}\rangle^{2}\right)$
$\displaystyle=\sum_{j=k+1}^{n}\langle\bar{{g}}_{i},{f}_{j}\rangle^{2}.$

Now, let us consider the quadratic form

$\displaystyle\bar{{g}}_{i}^{\intercal}\mathcal{N}_{G}\bar{{g}}_{i}$
$\displaystyle=\left(\sum_{j=1}^{n}\langle\bar{{g}}_{i},{f}_{j}\rangle{f}_{j}^{\intercal}\right)\mathcal{L}_{G}\left(\sum_{j=1}^{n}\langle\bar{{g}}_{i},{f}_{j}\rangle{f}_{j}\right)$
$\displaystyle=\sum_{j=1}^{n}\langle\bar{{g}}_{i},{f}_{j}\rangle^{2}\lambda_{j}$
$\displaystyle\geq\lambda_{k+1}\left\|\bar{{g}}_{i}-\widehat{{f}}_{i}\right\|^{2},$
(3.3)

where the last inequality follows by the fact that $\lambda_{i}\geq 0$ holds
for any $1\leq i\leq n$. This gives us that

$\displaystyle\bar{{g}}_{i}^{\intercal}{\mathcal{N}}_{G}\bar{{g}}_{i}$
$\displaystyle=\sum_{(u,v)\in{E}_{G}}{w}(u,v)\left(\frac{\bar{{g}}_{i}(u)}{\sqrt{{d}(u)}}-\frac{\bar{{g}}_{i}(v)}{\sqrt{{d}(v)}}\right)^{2}$
$\displaystyle=\sum_{(u,v)\in{E}_{G}}{w}(u,v)\left(\frac{{\chi}_{i}(u)}{\sqrt{\mathrm{vol}({S}_{i})}}-\frac{{\chi}_{i}(v)}{\sqrt{\mathrm{vol}({S}_{i})}}\right)^{2}$
$\displaystyle=\frac{{w}({S}_{i},{V}\setminus{S}_{i})}{\mathrm{vol}({S}_{j})}$
$\displaystyle\leq\rho(k).$ (3.4)

Combining (3.3) with (3.4), we have that

$\left\|\bar{{g}}_{i}-\widehat{{f}}_{i}\right\|^{2}\leq\frac{\bar{{g}}_{i}^{\intercal}{\mathcal{N}}_{G}\bar{{g}}_{i}}{\lambda_{k+1}}\leq\frac{\rho(k)}{\lambda_{k+1}}\leq\frac{1}{\Upsilon(k)},$

which proves the first statement of the theorem.

Now we prove the second statement. We define for any $1\leq i\leq k$ that
$\widehat{{g}}_{i}=\sum_{j=1}^{k}\langle{f}_{i},\bar{{g}}_{j}\rangle\bar{{g}}_{j}$,
and have that

$\displaystyle\sum_{i=1}^{k}\left\|{f}_{i}-\widehat{{g}}_{i}\right\|^{2}$
$\displaystyle=\sum_{i=1}^{k}\left(\left\|{f}_{i}\right\|^{2}-\left\|\widehat{{g}}_{i}\right\|^{2}\right)$
$\displaystyle=k-\sum_{i=1}^{k}\sum_{j=1}^{k}\langle\bar{{g}}_{j},{f}_{i}\rangle^{2}$
$\displaystyle=\sum_{j=1}^{k}\left(1-\sum_{i=1}^{k}\langle\bar{{g}}_{j},{f}_{i}\rangle^{2}\right)$
$\displaystyle=\sum_{j=1}^{k}\left(\left\|\bar{{g}}_{j}\right\|^{2}-\left\|\widehat{{f}}_{j}\right\|^{2}\right)$
$\displaystyle=\sum_{j=1}^{k}\left\|\bar{{g}}_{j}-\widehat{{f}}_{j}\right\|^{2}$
$\displaystyle\leq\sum_{j=1}^{k}\frac{1}{\Upsilon(k)}$
$\displaystyle=\frac{k}{\Upsilon(k)},$

where the last inequality follows by the first statement of Theorem 1. ∎

To examine the significance of Theorem 1, we first highlight that these two
statements hold for any $\Upsilon(k)$, while the original structure theorem
relies on the assumption that $\Upsilon(k)=\Omega(k^{2})$. Since
$\Upsilon(k)=\Omega(k^{2})$ is a strong and even questionable assumption when
$k$ is large, e.g., $k=\Omega\\!\left(\mathrm{polylog}(n)\right)$, obtaining
these statements for general $\Upsilon(k)$ is important. Secondly, our second
statement of Theorem 1 significantly improves the original theorem.
Specifically, instead of stating $\|{f}_{i}-\widehat{{g}}_{i}\|^{2}\leq
1.1k/\Upsilon(k)$ for any $i\in[k]$, our second statement shows that
$\sum_{i=1}^{k}\left\|{f}_{i}-\widehat{{g}}_{i}\right\|^{2}\leq
k/\Upsilon(k)$; hence, it holds in expectation that
$\left\|{f}_{i}-\widehat{{g}}_{i}\right\|^{2}\leq 1/\Upsilon(k)$, the upper
bound of which matches the first statement. This implies that the vectors
${f}_{1},\ldots,{f}_{k}$ and $\bar{{g}}_{1},\ldots,\bar{{g}}_{k}$ can be
linearly approximated by each other with _roughly the same_ approximation
guarantee. Thirdly, rather than employing the machinery from matrix analysis
used by Peng et al. [PSZ17], to prove the original theorem, our proof is
simple and purely linear-algebraic. Therefore, we believe that both of our
stronger statements and much simplified proof are significant, and could have
further applications in graph clustering and related problems.

##  4 Tighter Analysis of Spectral Clustering

In this section, we analyse the spectral clustering algorithm. For any input
graph ${G}=({V}_{G},{E}_{G})$ and $k\in[n]$, spectral clustering consists of
the three steps below:

  1. 1.

compute the eigenvectors ${f}_{1},\ldots{f}_{k}$ of ${\mathcal{N}}_{G}$, and
embed each $u\in{V}_{G}$ to the point $F(u)\in\mathbb{R}^{k}$ according to

$F(u)\triangleq\frac{1}{\sqrt{{d}(u)}}\left({f}_{1}(u),\ldots,{f}_{k}(u)\right)^{\intercal};$
(4.1)

  2. 2.

apply $k$-means on the embedded points $\\{F(u)\\}_{u\in{V}_{G}}$;

  3. 3.

partition ${V}_{G}$ into $k$ clusters based on the output of $k$-means.

We will consider spectral clustering for graphs with clusters of _almost-
balanced_ size.

######  Definition 1.

Let ${G}$ be a graph with $k$ clusters $\\{{S}_{i}\\}_{i=1}^{k}$. We say that
the clusters are almost-balanced if
$(1/2)\cdot\mathrm{vol}({V}_{G})/k\leq\mathrm{vol}({S}_{i})\leq
2\cdot\mathrm{vol}({V}_{G})/k$ for all $i\in\\{1,\ldots,k\\}$.

Our main result is given in Theorem 2, where we take APT to be the
approximation ratio of the $k$-means algorithm used in spectral clustering.
Recall that we can take APT to be some small constant [KSS04].

######  Theorem 2.

Let ${G}$ be a graph with $k$ clusters $\\{{S}_{i}\\}_{i=1}^{k}$ of almost
balanced size, and $\Upsilon(k)\geq 2176(1+\textsf{APT})$. Let
$\\{{A}_{i}\\}_{i=1}^{k}$ be the output of spectral clustering and, without
loss of generality, the optimal correspondent of ${A}_{i}$ is ${S}_{i}$. Then,
it holds that

$\sum_{i=1}^{k}\mathrm{vol}\left({A}_{i}\triangle{S}_{i}\right)\leq
2176~{}(1+\textsf{APT})~{}\frac{\mathrm{vol}({V}_{G})}{\Upsilon(k)}.$

Notice that some condition on $\Upsilon(k)$ is needed to ensure that an input
graph ${G}$ has $k$ well-defined clusters, so that misclassified vertices can
be formally defined. Taking this into account, the most significant feature of
Theorem 2 is its upper bound of misclassified vertices with respect to
$\Upsilon(k)$: our result holds, and is non-trivial, as long as $\Upsilon(k)$
is lower bounded by some constant333Note that we can take any constant
approximation in Definition 1 with a different corresponding constant in
Theorem 2.. This significantly improves most of the previous results of graph
clustering algorithms, which make stronger assumptions on the input graphs.
For example, Peng et al. [PSZ17] assumes that
$\Upsilon(k)=\Omega\\!\left(k^{3}\right)$, Mizutani [Miz21] assumes that
$\Upsilon(k)=\Omega\\!\left(k\right)$, the algorithm presented in Gharan and
Trevisan [GT14] assumes that
$\lambda_{k+1}=\Omega\\!\left(\mathrm{poly}(k)\lambda^{1/4}_{k}\right)$, and
the one presented in Dey et al. [DPRS19] further assumes some condition with
respect to $k$, $\lambda_{k}$, and the maximum degree of ${G}$. While these
assumptions require at least a linear dependency on $k$, making it difficult
for the instances with a large value of $k$ to satisfy, our result suggests
that the performance of spectral clustering can be rigorously analysed for
these graphs. In particular, compared with previous work, our result better
justifies the widely used eigen-gap heuristic for spectral clustering [NJW01,
vL07]. This heuristic suggests that spectral clustering works when the value
of $|\lambda_{k+1}-\lambda_{k}|$ is much larger than
$|\lambda_{k}-\lambda_{k-1}|$, and in practice, the ratio between the two gaps
is usually a constant rather than some function of $k$.

###  4.1 Properties of Spectral Embedding

Now we study the properties of the spectral embedding defined in (4.1), and
show in the next subsection how to use these properties to prove Theorem 2.
For every cluster ${S}_{i}$, we define the vector ${p}^{(i)}\in\mathbb{R}^{k}$
by

${p}^{(i)}(j)=\frac{1}{\sqrt{\mathrm{vol}({S}_{i})}}\langle{f}_{j},\bar{{g}}_{i}\rangle,$

and view these $\\{{p}^{(i)}\\}_{i=1}^{k}$ as the approximate centres of the
embedded points from the optimal clusters $\\{{S}_{i}\\}_{i=1}^{k}$. We prove
that the total $k$-means cost of the embedded points can be upper bounded as
follows:

######  Lemma 4.1.

It holds that

$\sum_{i=1}^{k}\sum_{u\in{S}_{i}}{d}(u)\left\|F(u)-{p}^{(i)}\right\|^{2}\leq\frac{k}{\Upsilon(k)}.$

###### Proof.

We have

$\displaystyle\sum_{i=1}^{k}\sum_{u\in{S}_{i}}{d}(u)\left\|F(u)-{p}^{(i)}\right\|^{2}$
$\displaystyle=\sum_{i=1}^{k}\sum_{u\in{S}_{i}}{d}(u)\left[\sum_{j=1}^{k}\left(\frac{{f}_{j}(u)}{\sqrt{{d}(u)}}-\frac{\langle\bar{{g}}_{i},{f}_{j}\rangle}{\sqrt{\mathrm{vol}({S}_{i})}}\right)^{2}\right]$
$\displaystyle=\sum_{i=1}^{k}\sum_{u\in{S}_{i}}\sum_{j=1}^{k}\left({f}_{j}(u)-\langle\bar{{g}}_{i},{f}_{j}\rangle\bar{{g}}_{i}(u)\right)^{2}$
$\displaystyle=\sum_{i=1}^{k}\sum_{u\in{S}_{i}}\sum_{j=1}^{k}\left({f}_{j}(u)-\widehat{{g}}_{j}(u)\right)^{2}$
$\displaystyle=\sum_{j=1}^{k}\left\|{f}_{j}-\widehat{{g}}_{j}\right\|^{2}$
$\displaystyle\leq\frac{k}{\Upsilon(k)},$

where the final inequality follows by the second statement of Theorem 1 and it
holds for $u\in{S}_{x}$ that
$\widehat{{g}}_{i}(u)=\sum_{j=1}^{k}\langle{f}_{i},\bar{{g}}_{j}\rangle\bar{{g}}_{j}(u)=\langle{f}_{i},\bar{{g}}_{x}\rangle\bar{{g}}_{x}(u)$.
∎

The importance of Lemma 4.1 is that, although the optimal centres for
$k$-means are unknown, the existence of $\\{{p}^{(i)}\\}_{i=1}^{k}$ is
sufficient to show that the cost of an optimal $k$-means clustering on
$\\{F(u)\\}_{u\in{V}_{G}}$ is at most $k/\Upsilon(k)$. Since one can always
use an $O(1)$-approximate $k$-means algorithm for spectral clustering (e.g.,
[KMN+04, KSS04]), the cost of the output of $k$-means on
$\\{F(u)\\}_{u\in{V}_{G}}$ is $O\left(k/\Upsilon(k)\right)$. Next, we show
that the length of ${p}^{(i)}$ is approximately equal to
$1/\mathrm{vol}({S}_{i})$, which will be useful in our later analysis.

######  Lemma 4.2.

It holds for any $i\in[k]$ that

$\frac{1}{\mathrm{vol}({S}_{i})}\left(1-\frac{1}{\Upsilon(k)}\right)\leq\left\|{p}^{(i)}\right\|^{2}\leq\frac{1}{\mathrm{vol}({S}_{i})}.$

###### Proof.

By definition, we have

$\displaystyle\mathrm{vol}({S}_{i})\left\|{p}^{(i)}\right\|^{2}$
$\displaystyle=\sum_{j=1}^{k}\langle{f}_{j},\bar{{g}}_{i}\rangle^{2}=\left\|\widehat{{f}}_{i}\right\|^{2}=1-\left\|\widehat{{f}}_{i}-\bar{{g}}_{i}\right\|^{2}\geq
1-\frac{1}{\Upsilon(k)},$

where the inequality follows by Theorem 1. The other direction of the
inequality follows similarly. ∎

In the remainder of this subsection, we will prove a sequence of lemmas
showing that any pair of ${p}^{(i)}$ and ${p}^{(j)}$ are well separated.
Moreover, notice that their distance is essentially independent of $k$ and
$\Upsilon(k)$, as long as $\Upsilon(k)\geq 20$.

######  Lemma 4.3.

It holds for any different $i,j\in[k]$ that

$\left\|\sqrt{\mathrm{vol}({S}_{i})}\cdot{p}^{(i)}-\sqrt{\mathrm{vol}({S}_{j})}\cdot{p}^{(j)}\right\|^{2}\geq
2-\frac{8}{\Upsilon(k)}.$

###### Proof.

We have

$\displaystyle\left\|\sqrt{\mathrm{vol}({S}_{i})}\cdot{p}^{(i)}-\sqrt{\mathrm{vol}({S}_{j})}\cdot{p}^{(j)}\right\|^{2}$
$\displaystyle=\sum_{x=1}^{k}\left(\langle{f}_{x},\bar{{g}}_{i}\rangle-\langle{f}_{x},\bar{{g}}_{j}\rangle\right)^{2}$
$\displaystyle=\left(\sum_{x=1}^{k}\langle{f}_{x},\bar{{g}}_{i}\rangle^{2}\right)+\left(\sum_{x=1}^{k}\langle{f}_{x},\bar{{g}}_{j}\rangle^{2}\right)-2\sum_{x=1}^{k}\langle{f}_{x},\bar{{g}}_{i}\rangle\langle{f}_{x},\bar{{g}}_{j}\rangle$
$\displaystyle\geq\left\|\widehat{{f}}_{i}\right\|^{2}+\left\|\widehat{{f}}_{j}\right\|^{2}-2\left\lvert\widehat{{f}}_{i}^{\intercal}\widehat{{f}}_{j}\right\rvert$
$\displaystyle\geq
2\left(1-\frac{1}{\Upsilon(k)}\right)-2\left\lvert(\bar{{g}}_{i}+\widehat{{f}}_{i}-\bar{{g}}_{i})^{\intercal}(\bar{{g}}_{j}+\widehat{{f}}_{j}-\bar{{g}}_{j})\right\rvert$
$\displaystyle=2\left(1-\frac{1}{\Upsilon(k)}\right)-2\left(\left\lvert\langle\bar{{g}}_{i},\widehat{{f}}_{j}-\bar{{g}}_{j}\rangle+\langle\bar{{g}}_{j},\widehat{{f}}_{i}-\bar{{g}}_{i}\rangle+\langle\widehat{{f}}_{i}-\bar{{g}}_{i},\widehat{{f}}_{j}-\bar{{g}}_{j}\rangle\right\rvert\right)$
$\displaystyle\geq
2\left(1-\frac{1}{\Upsilon(k)}\right)-6\cdot\frac{1}{\Upsilon(k)}$
$\displaystyle\geq 2-\frac{8}{\Upsilon(k)}.\qed$

######  Lemma 4.4.

It holds for any different $i,j\in[k]$ that

$\left\|\frac{{p}^{(i)}}{\left\|{p}^{(i)}\right\|}-\frac{{p}^{(j)}}{\left\|{p}^{(j)}\right\|}\right\|^{2}\geq
2-\frac{20}{\Upsilon(k)}.$

###### Proof.

Assume without loss of generality that

$\sqrt{\mathrm{vol}({S}_{i})}\left\|{p}^{(i)}\right\|\leq\sqrt{\mathrm{vol}({S}_{j})}\left\|{p}^{(j)}\right\|.$

Let ${a}_{i}=\sqrt{\mathrm{vol}({S}_{i})}{p}^{(i)}$ and
${a}_{j}=\sqrt{\mathrm{vol}({S}_{j})}{p}^{(j)}$ and notice that
$\left\|{a}_{i}\right\|\leq\left\|{a}_{j}\right\|\leq 1$. Then, using Lemma
4.2 we have

$\displaystyle\left\|\frac{{p}^{(i)}}{\left\|{p}^{(i)}\right\|}-\frac{{p}^{(j)}}{\left\|{p}^{(j)}\right\|}\right\|$
$\displaystyle\geq\left\|{a}_{i}-\frac{\left\|{a}_{i}\right\|}{\left\|{a}_{j}\right\|}{a}_{j}\right\|$
$\displaystyle\geq\left\|{a}_{i}-{a}_{j}\right\|-\left(\left\|{a}_{j}\right\|-\left\|{a}_{i}\right\|\right)$
$\displaystyle\geq\sqrt{2-\frac{8}{\Upsilon(k)}}-\left(\sqrt{\mathrm{vol}({S}_{j})}\cdot\left\|{p}^{(j)}\right\|-\sqrt{\mathrm{vol}({S}_{i})}\left\|{p}^{(i)}\right\|\right)$
$\displaystyle\geq\sqrt{2}\left(1-\frac{4}{\Upsilon(k)}\right)+\sqrt{1-\frac{1}{\Upsilon(k)}}-1$
$\displaystyle\geq\sqrt{2}-\frac{4\sqrt{2}}{\Upsilon(k)}-\frac{1}{\Upsilon(k)}$
$\displaystyle\geq\sqrt{2}-\frac{7}{\Upsilon(k)},$

where the second inequality follows by the triangle inequality, and the third
and fourth use Lemma 4.3. We also use the fact that for $x\leq 1$, it is the
case that $\sqrt{1-x}\geq 1-x$. This gives

$\displaystyle\left\|\frac{{p}^{(i)}}{\left\|{p}^{(i)}\right\|}-\frac{{p}^{(j)}}{\left\|{p}^{(j)}\right\|}\right\|^{2}$
$\displaystyle\geq 2-\frac{14\sqrt{2}}{\Upsilon(k)}\geq
2-\frac{20}{\Upsilon(k)},$

which proves the lemma. ∎

######  Lemma 4.5.

It holds for any $i,j\in[k]$ with $i\neq j$ that

$\left\|{p}^{(i)}-{p}^{(j)}\right\|^{2}\geq\frac{1}{\min\\{\mathrm{vol}({S}_{i}),\mathrm{vol}({S}_{j})\\}}\left(\frac{1}{2}-\frac{8}{\Upsilon(k)}\right).$

###### Proof.

Assume without loss of generality that
$\left\|{p}^{(i)}\right\|\geq\left\|{p}^{(j)}\right\|$. Then, let
$\left\|{p}^{(j)}\right\|=\alpha\left\|{p}^{(i)}\right\|$ for some
$\alpha\in[0,1]$. By Lemma 4.2, it holds that

$\left\|{p}^{(i)}\right\|^{2}\geq\frac{1}{\min\\{\mathrm{vol}({S}_{i}),\mathrm{vol}({S}_{j})\|}\left(1-\frac{1}{\Upsilon(k)}\right).$

Additionally, notice that by the proof of Lemma 4.4,

$\left\langle\frac{{p}^{(i)}}{\left\|{p}^{(i)}\right\|},\frac{{p}^{(j)}}{\left\|{p}^{(j)}\right\|}\right\rangle\leq\sqrt{2}-\frac{1}{2}\left\|\frac{{p}^{(i)}}{\left\|{p}^{(i)}\right\|}-\frac{{p}^{(j)}}{\left\|{p}^{(j)}\right\|}\right\|\leq\frac{\sqrt{2}}{2}+\frac{7}{2\Upsilon(k)},$

where we use the fact that if $x^{2}+y^{2}=1$, then $x+y\leq\sqrt{2}$. One can
understand the equation above by considering the right-angled triangle with
one edge given by ${p}^{(i)}/\left\|{p}^{(i)}\right\|$ and another edge given
by
$({p}^{(i)}/\left\|{p}^{(i)}\right\|).({p}^{(j)}/\left\|{p}^{(j)}\right\|)$.
Then,

$\displaystyle\left\|{p}^{(i)}-{p}^{(j)}\right\|^{2}$
$\displaystyle=\left\|{p}^{(i)}\right\|^{2}+\left\|{p}^{(j)}\right\|^{2}-2\left\langle\frac{{p}^{(i)}}{\left\|{p}^{(i)}\right\|},\frac{{p}^{(j)}}{\left\|{p}^{(j)}\right\|}\right\rangle\left\|{p}^{(i)}\right\|\left\|{p}^{(j)}\right\|$
$\displaystyle\geq(1+\alpha)\left\|{p}^{(i)}\right\|^{2}-\left(\sqrt{2}+\frac{7}{\Upsilon(k)}\right)\alpha\left\|{p}^{(i)}\right\|^{2}$
$\displaystyle\geq\left(1-(\sqrt{2}-1)\alpha-\frac{7}{\Upsilon(k)}\right)\left\|{p}^{(i)}\right\|^{2}$
$\displaystyle\geq\frac{1}{\min\\{\mathrm{vol}({S}_{i}),\mathrm{vol}({S}_{j})\\}}\left(\frac{1}{2}-\frac{7}{\Upsilon(k)}\right)\left(1-\frac{1}{\Upsilon(k)}\right)$
$\displaystyle\geq\frac{1}{\min\\{\mathrm{vol}({S}_{i}),\mathrm{vol}({S}_{j})\\}}\left(\frac{1}{2}-\frac{8}{\Upsilon(k)}\right),$

which completes the proof. ∎

We remark that, despite the similarity in their formulation, the technical
lemmas presented in this subsection are stronger than the ones in Peng et al.
[PSZ17]. These results are obtained through our stronger structure theorem
(Theorem 1), and are crucial for us to prove Theorem 2.

###  4.2 Proof of Theorem 2

In this subsection, we prove Theorem 2, and explain why a mild condition like
$\Upsilon(k)=\Omega\\!\left(1\right)$ suffices for spectral clustering to
perform well in practice. Let $\\{{A}_{i}\\}_{i=1}^{k}$ be the output of
spectral clustering, and we denote the centre of the embedded points
$\\{F(u)\\}$ for any ${A}_{i}$ by ${c}_{i}$. As the starting point of our
analysis, we claim that every ${c}_{i}$ will be close to its “optimal”
correspondent ${p}^{(\sigma(i))}$ for some $\sigma(i)\in[k]$. That is, the
actual centre of embedded points from every ${A}_{i}$ is close to the
approximate centre of the embedded points from some optimal ${S}_{i}$. To
formalise this, we define the function $\sigma:[k]\rightarrow[k]$ by

$\sigma(i)=\operatorname*{arg\,min}_{j\in[k]}\left\|{p}^{(j)}-{c}_{i}\right\|;$
(4.2)

that is, cluster ${A}_{i}$ should correspond to ${S}_{\sigma(i)}$ in which the
value of $\|{p}^{(\sigma(i))}-{c}_{i}\|$ is the lowest among all the distances
between ${c}_{i}$ and all of the ${p}^{(j)}$ for $j\in[k]$. However, one needs
to be cautious as (4.2) wouldn’t necessarily define a permutation, and there
might exist different $i,i^{\prime}\in[k]$ such that both of ${A}_{i}$ and
${A}_{i^{\prime}}$ map to the same ${S}_{\sigma(i)}$. Taking this into
account, for any fixed $\sigma:[k]\rightarrow[k]$ and $i\in[k]$, we further
define ${M}_{\sigma,i}$ by

${M}_{\sigma,i}\triangleq\bigcup_{j:\sigma(j)=i}{A}_{j}.$ (4.3)

The following lemma shows that, when mapping every output ${A}_{i}$ to
${S}_{\sigma(i)}$, the total ratio of misclassified volume with respect to
each cluster can be upper bounded:

######  Lemma 4.6.

Let $\\{{A}_{i}\\}_{i=1}^{k}$ be the output of spectral clustering, and
$\sigma$ and ${M}_{\sigma,i}$ be defined as in (4.2) and (4.3). If
$\Upsilon(k)\geq 32$, then

$\sum_{i=1}^{k}\frac{\mathrm{vol}({M}_{\sigma,i}\triangle{S}_{i})}{\mathrm{vol}({S}_{i})}\leq
64(1+\textsf{APT})\frac{k}{\Upsilon(k)}.$

###### Proof.

Let us define ${B}_{ij}={A}_{i}\cap{S}_{j}$ to be the vertices in ${A}_{i}$
which belong to the true cluster ${S}_{j}$. Then, we have that

$\displaystyle\sum_{i=1}^{k}\frac{\mathrm{vol}({M}_{\sigma,i}\triangle{S}_{i})}{\mathrm{vol}({S}_{i})}$
$\displaystyle=\sum_{i=1}^{k}\sum_{\begin{subarray}{c}j=1\\\
j\neq\sigma(i)\end{subarray}}^{k}\mathrm{vol}({B}_{ij})\left(\frac{1}{\mathrm{vol}({S}_{\sigma(i)})}+\frac{1}{\mathrm{vol}({S}_{j})}\right)$
$\displaystyle\leq 2\sum_{i=1}^{k}\sum_{\begin{subarray}{c}j=1\\\
j\neq\sigma(i)\end{subarray}}^{k}\frac{\mathrm{vol}({B}_{ij})}{\min\\{\mathrm{vol}({S}_{\sigma(i)}),\mathrm{vol}({S}_{j})\\}},$
(4.4)

and that

$\displaystyle\mathrm{COST}({A}_{1},\ldots{A}_{k})$
$\displaystyle=\sum_{i=1}^{k}\sum_{u\in{A}_{i}}{d}(u)\left\|F(u)-{c}_{i}\right\|^{2}$
$\displaystyle\geq\sum_{i=1}^{k}\sum_{\begin{subarray}{c}1\leq j\leq k\\\
j\neq\sigma(i)\end{subarray}}\sum_{u\in{B}_{ij}}{d}(u)\left\|F(u)-{c}_{i}\right\|^{2}$
$\displaystyle\geq\sum_{i=1}^{k}\sum_{\begin{subarray}{c}1\leq j\leq k\\\
j\neq\sigma(i)\end{subarray}}\sum_{u\in{B}_{ij}}{d}(u)\left(\frac{\left\|{p}^{(j)}-{c}_{i}\right\|^{2}}{2}-\left\|{p}^{(j)}-F(u)\right\|^{2}\right)$
$\displaystyle\geq\sum_{i=1}^{k}\sum_{\begin{subarray}{c}1\leq j\leq k\\\
j\neq\sigma(i)\end{subarray}}\sum_{u\in{B}_{ij}}\frac{{d}(u)\left\|{p}^{(j)}-{p}^{(\sigma(i))}\right\|^{2}}{8}-\sum_{i=1}^{k}\sum_{\begin{subarray}{c}1\leq
j\leq k\\\ j\neq
i\end{subarray}}\sum_{u\in{B}_{ij}}{d}(u)\left\|{p}^{(j)}-F(u)\right\|^{2}$
$\displaystyle\geq\sum_{i=1}^{k}\sum_{\begin{subarray}{c}1\leq j\leq k\\\
j\neq\sigma(i)\end{subarray}}\mathrm{vol}({B}_{ij})\frac{\left\|{p}^{(j)}-{p}^{(\sigma(i))}\right\|^{2}}{8}-\sum_{i=1}^{k}\sum_{u\in{S}_{i}}{d}(u)\left\|{p}^{(i)}-F(u)\right\|^{2}$
$\displaystyle\geq\sum_{i=1}^{k}\sum_{\begin{subarray}{c}1\leq j\leq k\\\
j\neq\sigma(i)\end{subarray}}\frac{\mathrm{vol}({B}_{ij})}{8\min\\{\mathrm{vol}({S}_{\sigma(i)}),\mathrm{vol}({S}_{j})\\}}\left(\frac{1}{2}-\frac{8}{\Upsilon(k)}\right)-\sum_{i=1}^{k}\sum_{u\in{S}_{i}}{d}(u)\left\|{p}^{(i)}-F(u)\right\|^{2}$
$\displaystyle\geq\frac{1}{16}\cdot\left(\sum_{i=1}^{k}\frac{\mathrm{vol}({M}_{\sigma,i}\triangle{S}_{i})}{\mathrm{vol}({S}_{i})}\right)\left(\frac{1}{2}-\frac{8}{\Upsilon(k)}\right)-\frac{k}{\Upsilon(k)},$

where the second inequality follows by the inequality of

$\left\|{a}-{b}\right\|^{2}\geq\frac{\left\|{b}-{c}\right\|^{2}}{2}-\left\|{a}-{c}\right\|^{2},$

the third inequality follows since ${c}_{i}$ is closer to ${p}^{(\sigma(i))}$
than ${p}^{(j)}$, the fifth one follows from Lemma 4.5, and the last one
follows by (4.4).

On the other side, since
$\mathrm{COST}({A}_{1},\ldots,{A}_{k})\leq\textsf{APT}\cdot k/\Upsilon(k)$, we
have that

$\frac{1}{16}\cdot\left(\sum_{i=1}^{k}\frac{\mathrm{vol}({M}_{\sigma,i}\triangle{S}_{i})}{\mathrm{vol}({S}_{i})}\right)\left(\frac{1}{2}-\frac{8}{\Upsilon(k)}\right)-\frac{k}{\Upsilon(k)}\leq\textsf{APT}\cdot\frac{k}{\Upsilon(k)}.$

This implies that

$\displaystyle\sum_{i=1}^{k}\frac{\mathrm{vol}({M}_{\sigma,i}\triangle{S}_{i})}{\mathrm{vol}({S}_{i})}$
$\displaystyle\leq
16\cdot(1+\textsf{APT})\cdot\frac{k}{\Upsilon(k)}\cdot\left(\frac{1}{2}-\frac{8}{\Upsilon(k)}\right)^{-1}$
$\displaystyle\leq 64\cdot(1+\textsf{APT})\cdot\frac{k}{\Upsilon(k)},$

where the last inequality holds by the assumption that $\Upsilon(k)\geq 32$. ∎

It remains to study the case in which $\sigma$ isn’t a permutation. Notice
that, if this occurs, there is some $i\in[k]$ such that
${M}_{\sigma,i}=\emptyset$, and different values of $x,y\in[k]$ such that
$\sigma(x)=\sigma(y)=j$ for some $j\neq i$. Based on this, we construct the
function $\sigma^{\prime}:[k]\rightarrow[k]$ from $\sigma$ based on the
following procedure:

  * •

Set $\sigma^{\prime}(z)=i$ if $z=x$;

  * •

Set $\sigma^{\prime}(z)=\sigma(z)$ for any other $z\in[k]\setminus\\{x\\}$.

Notice that one can construct $\sigma^{\prime}$ in this way as long as
$\sigma$ isn’t a permutation, and this constructed $\sigma^{\prime}$ reduces
the number of ${M}_{\sigma,i}$ being $\emptyset$ by one. We show one only
needs to construct such $\sigma^{\prime}$ at most
$O\\!\left(k/\Upsilon(k)\right)$ times to obtain the final permutation called
$\sigma^{\star}$, and it holds for $\sigma^{\star}$ that

$\sum_{i=1}^{k}\frac{\mathrm{vol}({M}_{\sigma^{\star},i}\triangle{S}_{i})}{\mathrm{vol}({S}_{i})}=O\\!\left(\frac{k}{\Upsilon(k)}\right).$

Combining this with the fact that
$\mathrm{vol}({S}_{i})=\Theta(\mathrm{vol}({V}_{G})/k)$ for any $i\in[k]$
proves Theorem 2.

###### Proof of Theorem 2.

By Lemma 4.1, we have

$\mathsf{COST}({S}_{1},\ldots,{S}_{k})\leq\frac{k}{\Upsilon(k)}.$

Combining this with the fact that one can apply an approximate $k$-means
clustering algorithm with approximation ratio APT for spectral clustering, we
have that

$\mathsf{COST}({A}_{1},\ldots,{A}_{k})\leq\textsf{APT}\cdot\frac{k}{\Upsilon(k)}.$

Then, let $\sigma:[1,k]\rightarrow[1,k]$ be the function which assigns the
clusters ${A}_{1},\ldots,{A}_{k}$ to the ground truth clusters such that

$\sigma(i)=\operatorname*{arg\,min}_{j\in[k]}\left\|{p}^{(j)}-{c}_{i}\right\|.$

Then, it holds by Lemma 4.6 that

$\epsilon(\sigma)\triangleq\sum_{i=1}^{k}\frac{\mathrm{vol}({M}_{\sigma,i}\triangle{S}_{i})}{\mathrm{vol}({S}_{i})}\leq
64\cdot(1+\textsf{APT})\cdot\frac{k}{\Upsilon(k)}.$ (4.5)

Now, assume that $\sigma$ is not a permutation, and we’ll apply the following
procedure inductively to construct a permutation from $\sigma$. Since $\sigma$
isn’t a permutation, there is $i\in[k]$ such that $M_{\sigma,i}=\emptyset$.
Therefore, there are different values of $x,y\in[k]$ such that
$\sigma(x)=\sigma(y)=j$ for some $j\neq i$. Based on this, we construct the
function $\sigma^{\prime}:[k]\rightarrow[k]$ such that $\sigma^{\prime}(z)=i$
if $z=x$, and $\sigma^{\prime}(z)=\sigma(z)$ for any other
$z\in[k]\setminus\\{x\\}$. Notice that we can construct $\sigma^{\prime}$ in
this way as long as $\sigma$ isn’t a permutation. By the definition of
$\epsilon(\cdot)$ and function $\sigma^{\prime}$, the difference between
$\epsilon(\sigma^{\prime})$ and $\epsilon(\sigma)$ can be written as

$\epsilon(\sigma^{\prime})-\epsilon(\sigma)=\underbrace{\left(\frac{\mathrm{vol}({M}_{\sigma^{\prime},i}\triangle{S}_{i})}{\mathrm{vol}({S}_{i})}-\frac{\mathrm{vol}({M}_{\sigma,i}\triangle{S}_{i})}{\mathrm{vol}({S}_{i})}\right)}_{=:\alpha}+\underbrace{\left(\frac{\mathrm{vol}({M}_{\sigma^{\prime},j}\triangle{S}_{j})}{\mathrm{vol}({S}_{j})}-\frac{\mathrm{vol}({M}_{\sigma,j}\triangle{S}_{j})}{\mathrm{vol}({S}_{j})}\right)}_{=:\beta}.$
(4.6)

Let us consider $4$ cases based on the signs of $\alpha,\beta$ defined above.
In each case, we bound the cost introduced by the change from $\sigma$ to
$\sigma^{\prime}$, and then consider the total cost introduced throughout the
entire procedure of constructing a permutation.

Case 1: $\alpha<0,\beta<0$. In this case, it is clear that
$\epsilon(\sigma^{\prime})-\epsilon(\sigma)\leq 0$, and hence the total
introduced cost is at most $0$.

Case 2: $\alpha>0,\beta<0$. In this case, we have

$\displaystyle\epsilon(\sigma^{\prime})-\epsilon(\sigma)$
$\displaystyle\leq\frac{1}{\min(\mathrm{vol}({S}_{i}),\mathrm{vol}({S}_{j}))}\left(\mathrm{vol}({M}_{\sigma^{\prime},i}\triangle{S}_{i})-\mathrm{vol}({M}_{\sigma,i}\triangle{S}_{i})+\left\lvert\mathrm{vol}({M}_{\sigma^{\prime},j}\triangle{S}_{j})-\mathrm{vol}({M}_{\sigma,j}\triangle{S}_{j})\right\rvert\right)$
$\displaystyle=\frac{1}{\min(\mathrm{vol}({S}_{i}),\mathrm{vol}({S}_{j}))}\left(\mathrm{vol}({M}_{\sigma^{\prime},i}\triangle{S}_{i})-\mathrm{vol}({M}_{\sigma,i}\triangle{S}_{i})+\mathrm{vol}({M}_{\sigma,j}\triangle{S}_{j})-\mathrm{vol}({M}_{\sigma^{\prime},j}\triangle{S}_{j})\right)$
$\displaystyle=\frac{1}{\min(\mathrm{vol}({S}_{i}),\mathrm{vol}({S}_{j}))}\left(\mathrm{vol}({A}_{x}\setminus{S}_{i})-\mathrm{vol}({A}_{x}\cap{S}_{i})+\mathrm{vol}({A}_{x}\setminus{S}_{j})-\mathrm{vol}({A}_{x}\cap{S}_{j})\right)$
$\displaystyle\leq\frac{2\cdot\mathrm{vol}({A}_{x}\setminus{S}_{j})}{\min(\mathrm{vol}({S}_{i}),\mathrm{vol}({S}_{j}))}$
$\displaystyle\leq\frac{8\cdot\mathrm{vol}({A}_{x}\setminus{S}_{j})}{\mathrm{vol}({S}_{j})},$

where the last inequality follows by the fact that the clusters are almost
balanced. Since each set ${A}_{x}$ is moved at most once in order to construct
a permutation, the total introduced cost due to this case is at most

$\displaystyle\sum_{j=1}^{k}\sum_{{A}_{x}\in{M}_{\sigma,j}}\frac{8\cdot\mathrm{vol}({A}_{x}\setminus{S}_{j})}{\mathrm{vol}({S}_{j})}\leq
8\cdot\sum_{j=1}^{k}\frac{\mathrm{vol}({M}_{\sigma,j}\triangle{S}_{j})}{\mathrm{vol}({S}_{j})}\leq
512\cdot\left(1+\textsf{APT}\right)\cdot\frac{k}{\Upsilon(k)}.$

Case 3: $\alpha>0,\beta>0$. In this case, we have

$\displaystyle\epsilon(\sigma^{\prime})-\epsilon(\sigma)$
$\displaystyle\leq\frac{1}{\min(\mathrm{vol}({S}_{i}),\mathrm{vol}({S}_{j}))}\left(\mathrm{vol}({M}_{\sigma^{\prime},i}\triangle{S}_{i})-\mathrm{vol}({M}_{\sigma,i}\triangle{S}_{i})+\mathrm{vol}({M}_{\sigma^{\prime},j}\triangle{S}_{j})-\mathrm{vol}({M}_{\sigma,j}\triangle{S}_{j})\right)$
$\displaystyle=\frac{1}{\min(\mathrm{vol}({S}_{i}),\mathrm{vol}({S}_{j}))}\left(\mathrm{vol}({A}_{x}\setminus{S}_{i})-\mathrm{vol}({A}_{x}\cap{S}_{i})+\mathrm{vol}({A}_{x}\cap{S}_{j})-\mathrm{vol}({A}_{x}\setminus{S}_{j})\right)$
$\displaystyle\leq\frac{1}{\min(\mathrm{vol}({S}_{i}),\mathrm{vol}({S}_{j}))}\left(2\cdot\mathrm{vol}({S}_{x}\cap{S}_{j})\right)$
$\displaystyle\leq\frac{2\cdot\mathrm{vol}({S}_{j})}{\min(\mathrm{vol}({S}_{i}),\mathrm{vol}({S}_{j}))}$
$\displaystyle\leq 8,$

where the last inequality follows by the fact that the clusters are almost
balanced. We will consider the total introduced cost due to this case and Case
4 together, and so let’s first examine Case 4.

Case 4: $\alpha<0,\beta>0$. In this case, we have

$\displaystyle\epsilon(\sigma^{\prime})-\epsilon(\sigma)$
$\displaystyle\leq\frac{1}{\mathrm{vol}({S}_{j})}\left(\mathrm{vol}({M}_{\sigma^{\prime},j}\triangle{S}_{j})-\mathrm{vol}({M}_{\sigma,j}\triangle{S}_{j})\right)$
$\displaystyle\leq\frac{1}{\mathrm{vol}({S}_{j})}\left(\mathrm{vol}({A}_{x}\cap{S}_{j})-\mathrm{vol}({A}_{x}\setminus{S}_{j})\right)$
$\displaystyle\leq\frac{\mathrm{vol}({S}_{j})}{\mathrm{vol}({S}_{j})}$
$\displaystyle=1.$

Now, let us bound the total number of times we need to construct
$\sigma^{\prime}$ in order to obtain a permutation. For any $i$ with
${M}_{\sigma,i}=\emptyset$, we have

$\frac{\mathrm{vol}({M}_{\sigma,i}\triangle{S}_{i})}{\mathrm{vol}({S}_{i})}=\frac{\mathrm{vol}({S}_{i})}{\mathrm{vol}({S}_{i})}=1,$

so the total number of required iterations is upper bounded by

$\displaystyle\left\lvert\\{i:{M}_{\sigma,i}=\emptyset\\}\right\rvert$
$\displaystyle\leq\sum_{i=1}^{k}\frac{\mathrm{vol}({M}_{\sigma,i}\triangle{S}_{i})}{\mathrm{vol}({S}_{i})}$
$\displaystyle\leq 64\cdot(1+\textsf{APT})\cdot\frac{k}{\Upsilon(k)}.$

As such, the total introduced cost due to Cases 3 and 4 is at most

$8\cdot
64\cdot(1+\textsf{APT})\cdot\frac{k}{\Upsilon(k)}=512\cdot(1+\textsf{APT})\cdot\frac{k}{\Upsilon(k)}.$

Putting everything together, we have that

$\displaystyle\epsilon(\sigma^{\star})$
$\displaystyle\leq\epsilon(\sigma)+1024\cdot(1+\textsf{APT})\cdot\frac{k}{\Upsilon(k)}$
$\displaystyle\leq 1088\cdot(1+\textsf{APT})\cdot\frac{k}{\Upsilon(k)}.$

This implies that

$\sum_{i=1}^{k}\mathrm{vol}({M}_{\sigma^{\star},i}\triangle{S}_{i})\leq
2176\cdot(1+\textsf{APT})\cdot\frac{\mathrm{vol}({V}_{G})}{\Upsilon(k)}$

and completes the proof. ∎

We remark that this method of upper bounding the ratio of misclassified
vertices is very different from the ones used in previous references, e.g.,
[DPRS19, Miz21, PSZ17]. In particular, instead of examining all the possible
mappings between $\\{{A}_{i}\\}_{i=1}^{k}$ and $\\{{S}_{i}\\}_{i=1}^{k}$, we
directly work with some specifically defined function $\sigma$, and construct
our desired mapping $\sigma^{\star}$ from $\sigma$. This is another key for us
to obtain stronger results than the previous work.

##  5 Beyond the Classical Spectral Clustering

In this section we propose a variant of spectral clustering which employs
fewer than $k$ eigenvectors to find $k$ clusters. We prove that, when the
structure among the optimal clusters in an input graph satisfies certain
conditions, spectral clustering with fewer eigenvectors is able to produce
better results than classical spectral clustering. Our result gives a
theoretical justification of the surprising showcase in Section 1, and
presents a significant speedup on the runtime of spectral clustering in
practice, since fewer eigenvectors are used to construct the embedding.

###  5.1 Encoding the Cluster-Structure into Meta-Graphs

Suppose that $\\{{S}_{i}\\}_{i=1}^{k}$ is a $k$-way partition of ${V}_{G}$ for
an input graph ${G}$ that minimises the $k$-way expansion $\rho(k)$. We define
the matrix ${A}_{{M}}\in\mathbb{R}^{k\times k}$ by

${A}_{M}(i,j)=\left\\{\begin{array}[]{ll}{w}({S}_{i},{S}_{j})&\mbox{if }i\neq
j,\\\ 2{w}({S}_{i},{S}_{j})&\mbox{if }i=j\end{array}\right.$

and, taking ${A}_{M}$ to be the adjacency matrix, this defines a graph
${M}=({V}_{M},{E}_{M},{w}_{M})$ which we refer to as the _meta-graph_ of the
clusters. We define the normalised adjacency matrix of ${M}$ by

${\mathcal{A}}_{M}\triangleq{D}^{-\frac{1}{2}}_{M}{A}_{M}{D}^{-\frac{1}{2}},$

and the normalised Laplacian matrix of ${M}$ by

${\mathcal{N}}_{M}\triangleq{I}-{\mathcal{A}}_{M}.$

Let the eigenvalues of ${\mathcal{N}}_{M}$ be
$\gamma_{1}\leq\ldots\leq\gamma_{k}$, and ${g}_{i}\in\mathbb{R}^{k}$ be the
eigenvector corresponding to $\gamma_{i}$ for any $i\in[k]$.

The starting point of our novel approach is to look at the structure of the
meta-graph ${M}$ defined by $\\{{S}_{i}\\}_{i=1}^{k}$ of ${G}$, and study how
the spectral information of ${\mathcal{N}}_{M}\in\mathbb{R}^{k\times k}$ is
encoded in the bottom eigenvectors of ${\mathcal{N}}_{G}$. To achieve this,
for any $\ell\in[k]$ and vertex $i\in{V}_{M}$, let

$\bar{{x}}^{(i)}\triangleq\left({g}_{1}(i),\ldots,{g}_{\ell}(i)\right)^{\intercal};$
(5.1)

notice that $\bar{{x}}^{(i)}\in\mathbb{R}^{\ell}$ defines the spectral
embedding of $i\in{V}_{M}$ through the bottom $\ell$ eigenvectors of
${\mathcal{N}}_{M}$.

######  Definition 2 ($(\theta,\ell)$-distinguishable graph).

For any ${M}=({V}_{M},{E}_{M},{w}_{M})$ with $k$ vertices, $\ell\in[k]$, and
$\theta\in\mathbb{R}^{+}$, we say that ${M}$ is
$(\theta,\ell)$-distinguishable if

  * •

it holds for any $i\in[k]$ that
$\left\|\bar{{x}}^{(i)}\right\|^{2}\geq\theta$, and

  * •

it holds for any different $i,j\in[k]$ that

$\left\|\frac{\bar{{x}}^{(i)}}{\left\|\bar{{x}}^{(i)}\right\|}-\frac{\bar{{x}}^{(j)}}{\left\|\bar{{x}}^{(j)}\right\|}\right\|^{2}\geq\theta.$

In other words, graph ${M}$ is $(\theta,\ell)$-distinguishable if (i) every
embedded point $\bar{{x}}^{(i)}$ has squared length at least $\theta$, and
(ii) any pair of embedded points with normalisation are separated by a
distance of at least $\theta$. By definition, it is easy to see that, if ${M}$
is $(\theta,\ell)$-distinguishable for some large value of $\theta$, then the
embedded points $\\{\bar{{x}}^{(i)}\\}_{i\in{V}_{M}}$ can be easily separated
even if $\ell<k$. The two examples below demonstrate that it is indeed the
case and, since the meta-graph ${M}$ is constructed from
$\\{{S}_{i}\\}_{i=1}^{k}$, this well-separation property for
$\\{\bar{{x}}^{(i)}\\}_{i\in{V}_{M}}$ usually implies that the clusters
$\\{{S}_{i}\\}_{i=1}^{k}$ are also well-separated when the vertices are mapped
to the points $\\{F(u)\\}_{u\in{V}_{G}}$, in which

$F(u)\triangleq\frac{1}{\sqrt{{d}(u)}}\cdot\left({f}_{1}(u),\ldots{f}_{\ell}(u)\right)^{\intercal}.$
(5.2)

######  Example 1.

Suppose the meta-graph is $C_{6}$, the cycle on $6$ vertices. Figure 2(2(a))
shows that the vertices of $C_{6}$ are well separated by the second and third
eigenvectors of ${\mathcal{N}}_{C_{6}}$.444Notice that the first eigenvector
is the trivial one and gives no useful information. This is why we visualise
the second and third eigenvectors only. Since the minimum distance between any
pair of vertices in this embedding is $2/3$, we say that $C_{6}$ is
$\left(2/3,3\right)$-distinguishable. Figure 2(2(b)) shows that, when using
${f}_{2},{f}_{3}$ of ${\mathcal{N}}_{G}$ to embed the vertices of a
$600$-vertex graph with a cyclical cluster pattern, the embedded points
closely match the ones from the meta-graph.

(a) Spectral embedding of $C_{6}$ with ${g}_{2}$ and ${g}_{3}$.

(b) Spectral embedding of ${G}$ with ${f}_{2}$ and ${f}_{3}$.

Figure 2: The spectral embedding of a large graph ${G}$ whose clusters exhibit
a cyclical structure closely matches the embedding of the meta-graph $C_{6}$.

######  Example 2.

Suppose the meta-graph is $P_{4,4}$, which is the $4\times 4$ grid graph.
Figure 3(3(a)) shows that the vertices are separated using the second and
third eigenvectors of ${\mathcal{N}}_{P_{4,4}}$. The minimum distance between
any pair of vertices in this embedding is roughly $0.1$, and so $P_{4,4}$ is
$(0.1,3)$-distinguishable. Figure 3(3(b)) demonstrates that, when using
${f}_{2},{f}_{3}$ of ${\mathcal{N}}_{G}$ to construct the embedding, the
embedded points closely match the ones from the meta-graph.

(a) Embedding of $P_{4,4}$ with ${g}_{2}$ and ${g}_{3}$.

(b) Embedding of ${G}$ with ${f}_{2}$ and ${f}_{3}$.

Figure 3:  The spectral embedding of a large $1600$-vertex graph ${G}$ whose
clusters exhibit a grid structure closely matches the embedding of the meta-
graph $P_{4,4}$.

From these examples, it is clear to see that there is a close connection
between the embedding $\\{\bar{{x}}^{(i)}\\}$ defined in (5.1) and the
embedding $\\{F(u)\\}$ defined in (5.2). To formally analyse this connection,
we study the structure theorem with meta-graphs.

We define vectors $\bar{{g}}_{1},\ldots,\bar{{g}}_{k}\in\mathbb{R}^{n}$ which
represent the eigenvectors of ${\mathcal{N}}_{M}$ “blown-up” to $n$
dimensions. Formally, we define $\bar{{g}}_{i}$ such that

$\bar{{g}}_{i}=\sum_{j=1}^{k}\frac{{D}^{\frac{1}{2}}{\chi}_{j}}{\left\|{D}^{\frac{1}{2}}{\chi}_{j}\right\|}\cdot{g}_{i}(j),$

where ${\chi}_{j}\in\mathbb{R}^{n}$ is the indicator vector of cluster
${S}_{j}$ defined in (3.1). By definition, it holds for any $u\in{S}_{j}$ that

$\bar{{g}}_{i}(u)=\sqrt{\frac{{d}(u)}{\mathrm{vol}({S}_{j})}}\cdot{g}_{i}(j).$

The following lemma shows that $\\{\bar{{g}}_{i}\\}_{i=1}^{k}$ form an
orthonormal basis.

######  Lemma 5.1.

The following statements hold:

  1. 1.

it holds for any $i\in[k]$ that $\left\|\bar{{g}}_{i}\right\|=1$;

  2. 2.

it holds for any different $i,j\in[k]$ that
$\langle\bar{{g}}_{i},\bar{{g}}_{j}\rangle=0$.

###### Proof.

By definition, we have that

$\displaystyle\left\|\bar{{g}}_{i}\right\|^{2}=\bar{{g}}_{i}^{\intercal}\bar{{g}}_{i}$
$\displaystyle=\sum_{j=1}^{k}\sum_{u\in{S}_{j}}\bar{{g}}_{i}(u)^{2}=\sum_{j=1}^{k}\sum_{u\in{S}_{j}}\left(\frac{\sqrt{{d}(u)}}{\sqrt{\mathrm{vol}({S}_{j})}}\cdot{g}_{i}(j)\right)^{2}=\sum_{j=1}^{k}{g}_{i}(j)^{2}=\left\|{g}_{i}\right\|^{2}=1,$

which proves the first statement.

To prove the second statement, we have for any $i\neq j$ that

$\displaystyle\langle\bar{{g}}_{i},\bar{{g}}_{j}\rangle$
$\displaystyle=\sum_{x=1}^{k}\sum_{u\in{S}_{x}}\bar{{g}}_{i}(u)\bar{{g}}_{j}(u)$
$\displaystyle=\sum_{x=1}^{k}\sum_{u\in{S}_{x}}\frac{{d}(u)}{\mathrm{vol}({S}_{x})}\cdot{g}_{i}(x){g}_{j}(x)$
$\displaystyle=\sum_{x=1}^{k}{g}_{i}(x){g}_{j}(x)$
$\displaystyle={g}_{i}^{\intercal}{g}_{j}$ $\displaystyle=0,$

which completes the proof. ∎

We will later use the following important relationship between the eigenvalues
of ${\mathcal{N}}_{M}$ and ${\mathcal{N}}_{G}$.

######  Lemma 5.2.

It holds for any $1\leq i\leq k$ that $\lambda_{i}\leq\gamma_{i}$.

###### Proof.

Notice that we have for any $j\leq k$ that

$\displaystyle\bar{{g}}_{j}^{\intercal}{\mathcal{N}}_{G}\bar{{g}}_{j}$
$\displaystyle=\sum_{(u,v)\in{E}_{G}}{w}_{G}(u,v)\left(\frac{\bar{{g}}_{j}(u)}{\sqrt{{d}(u)}}-\frac{\bar{{g}}_{j}(u)}{\sqrt{{d}(v)}}\right)^{2}$
$\displaystyle=\sum_{x=1}^{k-1}\sum_{y=x+1}^{k}\sum_{a\in{S}_{x}}\sum_{b\in{S}_{y}}{w}(a,b)\left(\frac{\bar{{g}}_{j}(a)}{\sqrt{{d}(a)}}-\frac{\bar{{g}}_{j}(b)}{\sqrt{{d}(b)}}\right)^{2}$
$\displaystyle=\sum_{x=1}^{k-1}\sum_{y=x+1}^{k}{w}({S}_{x},{S}_{y})\left(\frac{{g}_{j}(x)}{\sqrt{\mathrm{vol}({S}_{x})}}-\frac{{g}_{j}(y)}{\sqrt{\mathrm{vol}({S}_{y})}}\right)^{2}$
$\displaystyle={g}_{j}^{\intercal}{\mathcal{N}}_{M}{g}_{j}$
$\displaystyle=\gamma_{j}.$

By Lemma 5.1, we have an $i$-dimensional subspace
${S}_{i}\subset\mathbb{R}^{n}$ such that

$\max_{{x}\in{S}_{i}}\frac{{x}^{\intercal}{\mathcal{N}}_{G}{x}}{{x}^{\intercal}{x}}=\gamma_{i},$

from which the statement of the lemma follows by the Courant-Fischer theorem.
∎

Next, similar to the function $\Upsilon(k)$ defined in (3.2), for any input
graph ${G}=({V}_{G},{E}_{G},{w}_{G})$ and $(\theta,\ell)$-distinguishable
meta-graph ${M}$, we define the function $\Psi(\ell)$ by

$\Psi(\ell)\triangleq\sum_{i=1}^{\ell}\frac{\gamma_{i}}{\lambda_{\ell+1}}.$

Notice that we have by the higher-order Cheeger inequality that
$\gamma_{i}/2\leq\rho_{M}(i)$ holds for any $i\in[\ell]$, and
$\rho_{M}(i)\leq\rho_{G}(k)$ by the construction of matrix ${A}_{M}$. Hence,
one can view $\Psi(\ell)$ as a refined definition of $\Upsilon(k)$.

We now show that the vectors ${f}_{1},\ldots,{f}_{\ell}$ and
$\bar{{g}}_{1},\ldots,\bar{{g}}_{\ell}$ are well approximated by each other.
In order to show this, we define for any $i\in[\ell]$ the vectors

$\widehat{{f}}_{i}=\sum_{j=1}^{\ell}\langle\bar{{g}}_{i},{f}_{j}\rangle{f}_{j}~{}\mbox{\
\ \ and\ \ \
}~{}\widehat{{g}}_{i}=\sum_{j=1}^{\ell}\langle{f}_{i},\bar{{g}}_{j}\rangle\bar{{g}}_{j},$

and present the structure theorem with meta-graphs.

######  Theorem 3 (The Structure Theorem with Meta-Graphs).

The following statements hold:

  1. 1.

it holds for any $i\in[\ell]$ that

$\left\|\bar{{g}}_{i}-\widehat{{f}}_{i}\right\|^{2}\leq\gamma_{i}/\lambda_{\ell+1};$

  2. 2.

it holds for any $\ell\in[k]$ that

$\sum_{i=1}^{\ell}\left\|{f}_{i}-\widehat{{g}}_{i}\right\|^{2}\leq\sum_{i=1}^{\ell}\frac{\gamma_{i}}{\lambda_{\ell+1}}.$

###### Proof.

For the first statement, we write $\bar{{g}}_{i}$ as a linear combination of
the vectors ${f}_{1},\ldots,{f}_{n}$, i.e.,
$\bar{{g}}_{i}=\sum_{j=1}^{n}\langle\bar{{g}}_{i},{f}_{j}\rangle{f}_{j}.$
Since $\widehat{{f}}_{i}$ is a projection of $\bar{{g}}_{i}$, we have that
$\bar{{g}}_{i}-\widehat{{f}}_{i}$ is perpendicular to $\widehat{{f}}_{i}$, and
that

$\displaystyle\left\|\bar{{g}}_{i}-\widehat{{f}}_{i}\right\|^{2}$
$\displaystyle=\left\|\bar{{g}}_{i}\right\|^{2}-\left\|\widehat{{f}}_{i}\right\|^{2}=\left(\sum_{j=1}^{n}\langle\bar{{g}}_{i},{f}_{j}\rangle^{2}\right)-\left(\sum_{j=1}^{\ell}\langle\bar{{g}}_{i},{f}_{j}\rangle^{2}\right)=\sum_{j=\ell+1}^{n}\langle\bar{{g}}_{i},{f}_{j}\rangle^{2}.$

Now, we study the quadratic form
$\bar{{g}}_{i}^{\intercal}{\mathcal{N}}_{G}\bar{{g}}_{i}$ and have that

$\displaystyle\bar{{g}}_{i}^{\intercal}{\mathcal{N}}_{G}\bar{{g}}_{i}$
$\displaystyle=\left(\sum_{j=1}^{n}\langle\bar{{g}}_{i},{f}_{j}\rangle{f}_{j}^{\intercal}\right){\mathcal{N}}_{G}\left(\sum_{j=1}^{n}\langle\bar{{g}}_{i},{f}_{j}\rangle{f}_{j}\right)=\sum_{j=1}^{n}\langle\bar{{g}}_{i},{f}_{j}\rangle^{2}\lambda_{j}\geq\lambda_{\ell+1}\left\|\bar{{g}}_{i}-\widehat{{f}}_{i}\right\|^{2}.$

By the proof of Lemma 5.2, we have that
$\bar{{g}}_{i}^{\intercal}{\mathcal{N}}_{G}\bar{{g}}_{i}\leq\gamma_{i}$, from
which the first statement follows.

Now we prove the second statement. We define the vectors
$\bar{{g}}_{k+1},\ldots,\bar{{g}}_{n}$ to be an arbitrary orthonormal basis of
the space orthogonal to the space spanned by
$\bar{{g}}_{1},\ldots,\bar{{g}}_{k}$. Then, we can write any ${f}_{i}$ as
${f}_{i}=\sum_{j=1}^{n}\langle{f}_{i},\bar{{g}}_{j}\rangle\bar{{g}}_{j}$, and
have that

$\displaystyle\sum_{i=1}^{\ell}\left\|{f}_{i}-\widehat{{g}}_{i}\right\|^{2}$
$\displaystyle=\sum_{i=1}^{\ell}\left(\left\|{f}_{i}\right\|^{2}-\left\|\widehat{{g}}_{i}\right\|^{2}\right)$
$\displaystyle=\ell-\sum_{i=1}^{\ell}\sum_{j=1}^{\ell}\langle{f}_{i},\bar{{g}}_{j}\rangle^{2}$
$\displaystyle=\sum_{j=1}^{\ell}\left(1-\sum_{i=1}^{\ell}\langle\bar{{g}}_{j},{f}_{i}\rangle^{2}\right)$
$\displaystyle=\sum_{j=1}^{\ell}\left(\left\|\bar{{g}}_{j}\right\|^{2}-\left\|\widehat{{f}}_{j}\right\|^{2}\right)$
$\displaystyle=\sum_{j=1}^{\ell}\left\|\bar{{g}}_{j}-\widehat{{f}}_{j}\right\|^{2}$
$\displaystyle\leq\sum_{j=1}^{\ell}\frac{\gamma_{j}}{\lambda_{{\ell}+1}},$

where the final inequality follows by the first statement of the theorem. ∎

###  5.2 Spectral Clustering with Fewer Eigenvectors

In this section, we analyse spectral clustering with fewer eigenvectors. Our
presented algorithm is essentially the same as the standard spectral
clustering described in Section 4, with the only difference that every
$u\in{V}_{G}$ is embedded into a point in $\mathbb{R}^{\ell}$ by the mapping
defined in (5.2). Our analysis follows from the one from Section 4 at a very
high level. However, since we require that $\\{F(u)\\}_{u\in{V}_{G}}$ are well
separated in $\mathbb{R}^{\ell}$ for some $\ell<k$, the proof is more
involved.

For any $i\in[k]$, we define the approximate centre
${p}^{(i)}\in\mathbb{R}^{\ell}$ of every cluster ${S}_{i}$ by

${p}^{(i)}(j)=\frac{1}{\sqrt{\mathrm{vol}({S}_{i})}}\cdot\sum_{x=1}^{\ell}\langle{f}_{j},\bar{{g}}_{x}\rangle\cdot{g}_{x}(i),$

and prove that the total $k$-means cost for the points
$\\{F(u)\\}_{u\in{V}_{G}}$ can be upper bounded.

######  Lemma 5.3.

It holds that

$\sum_{i=1}^{k}\sum_{u\in{S}_{i}}{d}(u)\left\|F(u)-{p}^{(i)}\right\|^{2}\leq\Psi(\ell).$

###### Proof.

By definition, it holds that

$\displaystyle\sum_{i=1}^{k}\sum_{u\in
S_{i}}{d}(u)\left\|F(u)-{p}^{(i)}\right\|^{2}$
$\displaystyle=\sum_{i=1}^{k}\sum_{u\in{S}_{i}}{d}(u)\left[\sum_{j=1}^{\ell}\left(\frac{{f}_{j}(u)}{\sqrt{{d}(u)}}-\left(\sum_{x=1}^{\ell}\langle{f}_{j},\bar{{g}}_{x}\rangle\frac{{g}_{x}(i)}{\sqrt{\mathrm{vol}({S}_{i})}}\right)\right)^{2}\right]$
$\displaystyle=\sum_{i=1}^{k}\sum_{u\in{S}_{i}}\sum_{j=1}^{\ell}\left({f}_{j}(u)-\left(\sum_{x=1}^{\ell}\langle{f}_{j},\bar{{g}}_{x}\rangle\bar{{g}}_{x}(u)\right)\right)^{2}$
$\displaystyle=\sum_{i=1}^{k}\sum_{u\in{S}_{i}}\sum_{j=1}^{\ell}\left({f}_{j}(u)-\widehat{{g}}_{j}(u)\right)^{2}$
$\displaystyle=\sum_{j=1}^{\ell}\left\|{f}_{j}-\widehat{{g}}_{j}\right\|^{2}\leq\Psi(\ell),$

where the final inequality follows from the second statement of Theorem 3. ∎

We now prove a sequence of lemmas which will establish that the distance
between different ${p}^{(i)}$ and ${p}^{(j)}$ can be lower bounded with
respect to $\theta$ and $\Psi(\ell)$.

######  Lemma 5.4.

It holds for $i\in[k]$ that

$\left(1-\frac{4\sqrt{\Psi(\ell)}}{\theta}\right)\frac{\left\|\bar{{x}}^{(i)}\right\|^{2}}{\mathrm{vol}({S}_{i})}\leq\left\|{p}^{(i)}\right\|^{2}\leq\frac{\left\|\bar{{x}}^{(i)}\right\|^{2}}{\mathrm{vol}({S}_{i})}\left(1+\frac{2\sqrt{\Psi(\ell)}}{\theta}\right).$

###### Proof.

It holds by definition that

$\displaystyle\mathrm{vol}({S}_{i})\cdot\left\|{p}^{(i)}\right\|^{2}$
$\displaystyle=\sum_{x=1}^{\ell}\left(\sum_{y=1}^{\ell}\langle{f}_{x},\bar{{g}}_{y}\rangle{g}_{y}(i)\right)^{2}$
$\displaystyle=\sum_{x=1}^{\ell}\sum_{y=1}^{\ell}\sum_{z=1}^{\ell}\langle{f}_{x},\bar{{g}}_{y}\rangle\langle{f}_{x},\bar{{g}}_{z}\rangle{g}_{y}(i){g}_{z}(i)$
$\displaystyle=\sum_{x=1}^{\ell}\sum_{y=1}^{\ell}\langle{f}_{x},\bar{{g}}_{y}\rangle^{2}{g}_{y}(i)^{2}+\sum_{x=1}^{\ell}\sum_{y=1}^{\ell}\sum_{\begin{subarray}{c}z=1\\\
z\neq
y\end{subarray}}^{\ell}\langle{f}_{x},\bar{{g}}_{y}\rangle\langle{f}_{x},\bar{{g}}_{z}\rangle{g}_{y}(i){g}_{z}(i)$
$\displaystyle=\sum_{x=1}^{\ell}\sum_{y=1}^{\ell}\langle{f}_{x},\bar{{g}}_{y}\rangle^{2}{g}_{y}(i)^{2}+\sum_{x=1}^{\ell}\sum_{y=1}^{\ell}\sum_{\begin{subarray}{c}z=1\\\
z\neq
y\end{subarray}}^{\ell}{g}_{y}(i){g}_{z}(i)\cdot\left(\widehat{{f}}_{y}^{\intercal}\widehat{{f}}_{z}\right).$
(5.3)

We study the two terms of (5.3) separately. For the second term, we have that

$\displaystyle\sum_{x=1}^{\ell}\sum_{y=1}^{\ell}\sum_{\begin{subarray}{c}z=1\\\
z\neq
y\end{subarray}}^{\ell}{g}_{y}(i){g}_{z}(i)\cdot\left(\widehat{{f}}_{y}^{\intercal}\widehat{{f}}_{z}\right)$
$\displaystyle\leq\sum_{y=1}^{\ell}\left\lvert{g}_{y}(i)\right\rvert\sum_{\begin{subarray}{c}1\leq
z\leq\ell\\\ z\neq
y\end{subarray}}\left\lvert{g}_{z}(i)\right\rvert\left\lvert\widehat{{f}}_{y}^{\intercal}\widehat{{f}}_{z}\right\rvert$
$\displaystyle=\sum_{y=1}^{\ell}\left\lvert{g}_{y}(i)\right\rvert\sum_{\begin{subarray}{c}1\leq
z\leq\ell\\\ z\neq
y\end{subarray}}\left\lvert{g}_{z}(i)\right\rvert\left\lvert\left(\bar{{g}}_{y}+\widehat{{f}}_{y}-\bar{{g}}_{y}\right)^{\intercal}\left(\bar{{g}}_{z}+\widehat{{f}}_{z}-\bar{{g}}_{z}\right)\right\rvert$
$\displaystyle=\sum_{y=1}^{\ell}\left\lvert{g}_{y}(i)\right\rvert\sum_{\begin{subarray}{c}1\leq
z\leq\ell\\\ z\neq
y\end{subarray}}\left\lvert{g}_{z}(i)\right\rvert\left\lvert\langle\widehat{{f}}_{y}-\bar{{g}}_{y},\bar{{g}}_{z}\rangle+\langle\widehat{{f}}_{z}-\bar{{g}}_{z},\bar{{g}}_{y}\rangle+\langle\widehat{{f}}_{y}-\bar{{g}}_{y},\widehat{{f}}_{z}-\bar{{g}}_{z}\rangle\right\rvert$
$\displaystyle=\sum_{y=1}^{\ell}\left\lvert{g}_{y}(i)\right\rvert\sum_{\begin{subarray}{c}z=1\\\
z\neq
y\end{subarray}}^{\ell}\left\lvert{g}_{z}(i)\right\rvert\left\lvert\langle\widehat{{f}}_{y}-\bar{{g}}_{y},\bar{{g}}_{z}\rangle\right\rvert$
$\displaystyle\leq\sqrt{\left(\sum_{y=1}^{\ell}{g}_{y}(i)^{2}\right)\sum_{y=1}^{\ell}\left(\sum_{\begin{subarray}{c}1\leq
z\leq\ell\\\ z\neq
y\end{subarray}}\left\lvert{g}_{z}(i)\right\rvert\left\lvert\langle\widehat{{f}}_{y}-\bar{{g}}_{y},\bar{{g}}_{z}\rangle\right\rvert\right)^{2}}$
$\displaystyle\leq\sqrt{\sum_{y=1}^{\ell}\left(\sum_{\begin{subarray}{c}1\leq
z\leq\ell\\\ z\neq
y\end{subarray}}{g}_{z}(i)^{2}\right)\left(\sum_{\begin{subarray}{c}1\leq
z\leq\ell\\\ z\neq
y\end{subarray}}\langle\widehat{{f}}_{y}-\bar{{g}}_{y},\bar{{g}}_{z}\rangle^{2}\right)}$
$\displaystyle\leq\sqrt{\sum_{y=1}^{\ell}\sum_{\begin{subarray}{c}1\leq
z\leq\ell\\\ z\neq
y\end{subarray}}\langle\widehat{{f}}_{y}-\bar{{g}}_{y},\bar{{g}}_{z}\rangle^{2}}$
$\displaystyle\leq\sqrt{\sum_{y=1}^{\ell}\left\|\widehat{{f}}_{y}-\bar{{g}}_{y}\right\|^{2}}\leq\sqrt{\Psi(\ell)},$

where we used the fact that $\sum_{y=1}^{k}{g}_{y}(i)^{2}=1$ for all
$i\in[k]$. Therefore, we have that

$\displaystyle\mathrm{vol}({S}_{i})\left\|{p}^{(i)}\right\|^{2}$
$\displaystyle\leq\sum_{y=1}^{\ell}\left(\sum_{x=1}^{\ell}\langle{f}_{x},\bar{{g}}_{y}\rangle^{2}\right){g}_{y}(i)^{2}+\sqrt{\Psi(\ell)}\leq\sum_{y=1}^{\ell}{g}_{y}(i)^{2}+\sqrt{\Psi(\ell)}\leq\left\|\bar{{x}}^{(i)}\right\|^{2}+\sqrt{\Psi(\ell)}$
$\displaystyle\leq\left\|\bar{{x}}^{(i)}\right\|^{2}\left(1+\frac{2\sqrt{\Psi(\ell)}}{\theta}\right).$

On the other hand, we have that

$\displaystyle\mathrm{vol}({S}_{i})\left\|{p}^{(i)}\right\|^{2}$
$\displaystyle\geq\sum_{y=1}^{\ell}\left(\sum_{x=1}^{\ell}\langle{f}_{x},\bar{{g}}_{y}\rangle^{2}\right){g}_{y}(i)^{2}-2\sqrt{\Psi(\ell)}\geq\sum_{y=1}^{\ell}\left\|\widehat{{f}}_{y}\right\|^{2}{g}_{y}(i)^{2}-2\sqrt{\Psi(\ell)}$
$\displaystyle\geq\left(1-\Psi(\ell)\right)\left\|\bar{{x}}^{(i)}\right\|^{2}-2\sqrt{\Psi(\ell)}\geq\left\|\bar{{x}}^{(i)}\right\|^{2}\left(1-\frac{4\sqrt{\Psi(\ell)}}{\theta}\right),$

where the last inequality holds by the fact that
$\left\|\bar{{x}}^{(i)}\right\|\leq 1$ and $\Psi(\ell)<1$. Hence, the
statement holds. ∎

######  Lemma 5.5.

It holds for $i\neq j$ that

$\left\|\frac{\sqrt{\mathrm{vol}({S}_{i})}}{\left\|\bar{{x}}^{(i)}\right\|}\cdot{p}^{(i)}-\frac{\sqrt{\mathrm{vol}({S}_{j})}}{\left\|\bar{{x}}^{(j)}\right\|}\cdot{p}^{(j)}\right\|^{2}\geq\theta-3\sqrt{\Psi(\ell)}.$

###### Proof.

By definition, it holds that

$\displaystyle\left\|\frac{\sqrt{\mathrm{vol}({S}_{i})}}{\left\|\bar{{x}}^{(i)}\right\|}\cdot{p}^{(i)}-\frac{\sqrt{\mathrm{vol}({S}_{j})}}{\left\|\bar{{x}}^{(j)}\right\|}\cdot{p}^{(j)}\right\|^{2}$
$\displaystyle=\sum_{t=1}^{\ell}\left(\sum_{y=1}^{\ell}\langle{f}_{t},\bar{{g}}_{y}\rangle\left(\frac{{g}_{y}(i)}{\left\|\bar{{x}}^{(i)}\right\|}-\frac{{g}_{y}(j)}{\left\|\bar{{x}}^{(j)}\right\|}\right)\right)^{2}$
$\displaystyle=\sum_{t=1}^{\ell}\sum_{y=1}^{\ell}\langle{f}_{t},\bar{{g}}_{y}\rangle^{2}\left(\frac{{g}_{y}(i)}{\left\|\bar{{x}}^{(i)}\right\|}-\frac{{g}_{y}(j)}{\left\|\bar{{x}}^{(j)}\right\|}\right)^{2}$
$\displaystyle\qquad\qquad+\sum_{t=1}^{\ell}\sum_{y=1}^{\ell}\sum_{\begin{subarray}{c}1\leq
z\leq\ell\\\ z\neq
y\end{subarray}}\langle{f}_{t},\bar{{g}}_{y}\rangle\langle{f}_{t},\bar{{g}}_{z}\rangle\left(\frac{{g}_{y}(i)}{\left\|\bar{{x}}^{(i)}\right\|}-\frac{{g}_{y}(j)}{\left\|\bar{{x}}^{(j)}\right\|}\right)\left(\frac{{g}_{z}(i)}{\left\|\bar{{x}}^{(i)}\right\|}-\frac{{g}_{z}(j)}{\left\|\bar{{x}}^{(j)}\right\|}\right).$

We upper bound the second term by

$\displaystyle\sum_{y=1}^{\ell}\left\lvert\frac{{g}_{y}(i)}{\left\|\bar{{x}}^{(i)}\right\|}-\frac{{g}_{y}(j)}{\left\|\bar{{x}}^{(j)}\right\|}\right\rvert\sum_{\begin{subarray}{c}1\leq
z\leq\ell\\\ z\neq
y\end{subarray}}\left\lvert\frac{{g}_{z}(i)}{\left\|\bar{{x}}^{(i)}\right\|}-\frac{{g}_{z}(j)}{\left\|\bar{{x}}^{(j)}\right\|}\right\rvert\sum_{t=1}^{\ell}\left\lvert\langle{f}_{t},\bar{{g}}_{y}\rangle\langle{f}_{t},\bar{{g}}_{x}\rangle\right\rvert$
$\displaystyle=$
$\displaystyle\sum_{y=1}^{\ell}\left\lvert\frac{{g}_{y}(i)}{\left\|\bar{{x}}^{(i)}\right\|}-\frac{{g}_{y}(j)}{\left\|\bar{{x}}^{(j)}\right\|}\right\rvert\sum_{\begin{subarray}{c}1\leq
z\leq\ell\\\ z\neq
y\end{subarray}}\left\lvert\frac{{g}_{z}(i)}{\left\|\bar{{x}}^{(i)}\right\|}-\frac{{g}_{z}(j)}{\left\|\bar{{x}}^{(j)}\right\|}\right\rvert\left\lvert\widehat{{f}}_{y}^{\intercal}\widehat{{f}}_{z}\right\rvert$
$\displaystyle=$
$\displaystyle\sum_{y=1}^{\ell}\left\lvert\frac{{g}_{y}(i)}{\left\|\bar{{x}}^{(i)}\right\|}-\frac{{g}_{y}(j)}{\left\|\bar{{x}}^{(j)}\right\|}\right\rvert\sum_{\begin{subarray}{c}1\leq
z\leq\ell\\\ z\neq
y\end{subarray}}\left\lvert\frac{{g}_{z}(i)}{\left\|\bar{{x}}^{(i)}\right\|}-\frac{{g}_{z}(j)}{\left\|\bar{{x}}^{(j)}\right\|}\right\rvert\left\lvert\left(\bar{{g}}_{y}+\widehat{{f}}_{y}-\bar{{g}}_{y}\right)^{\intercal}\left(\bar{{g}}_{z}+\widehat{{f}}_{z}-\bar{{g}}_{z}\right)\right\rvert$
$\displaystyle=$
$\displaystyle\sum_{y=1}^{\ell}\left\lvert\frac{{g}_{y}(i)}{\left\|\bar{{x}}^{(i)}\right\|}-\frac{{g}_{y}(j)}{\left\|\bar{{x}}^{(j)}\right\|}\right\rvert\sum_{\begin{subarray}{c}1\leq
z\leq\ell\\\ z\neq
y\end{subarray}}\left\lvert\frac{{g}_{z}(i)}{\left\|\bar{{x}}^{(i)}\right\|}-\frac{{g}_{z}(j)}{\left\|\bar{{x}}^{(j)}\right\|}\right\rvert\left\lvert\langle\widehat{{f}}_{y}-\bar{{g}}_{y},\bar{{g}}_{z}\rangle\right\rvert$
$\displaystyle\leq$
$\displaystyle\sqrt{\left(\sum_{y=1}^{\ell}\left(\frac{{g}_{y}(i)}{\left\|\bar{{x}}^{(i)}\right\|}-\frac{{g}_{y}(j)}{\left\|\bar{{x}}^{(j)}\right\|}\right)^{2}\right)\sum_{y=1}^{\ell}\left(\sum_{\begin{subarray}{c}1\leq
z\leq\ell\\\ z\neq
y\end{subarray}}\left\lvert\frac{{g}_{z}(i)}{\left\|\bar{{x}}^{(i)}\right\|}-\frac{{g}_{z}(j)}{\left\|\bar{{x}}^{(j)}\right\|}\right\rvert\left\lvert\langle\widehat{{f}}_{y}-\bar{{g}}_{y},\bar{{g}}_{z}\rangle\right\rvert\right)^{2}}$
$\displaystyle\leq$
$\displaystyle\sqrt{2\sum_{y=1}^{\ell}\left(\sum_{\begin{subarray}{c}1\leq
z\leq\ell\\\ z\neq
y\end{subarray}}\left(\frac{{g}_{z}(i)}{\left\|\bar{{x}}^{(i)}\right\|}-\frac{{g}_{z}(j)}{\left\|\bar{{x}}^{(j)}\right\|}\right)^{2}\right)\left(\sum_{\begin{subarray}{c}1\leq
z\leq\ell\\\ z\neq
y\end{subarray}}\langle\widehat{{f}}_{y}-\bar{{g}}_{y},\bar{{g}}_{z}\rangle^{2}\right)}$
$\displaystyle\leq$ $\displaystyle
2\sqrt{\sum_{y=1}^{\ell}\sum_{\begin{subarray}{c}1\leq z\leq\ell\\\ z\neq
y\end{subarray}}\langle\widehat{{f}}_{y}-\bar{{g}}_{y},\bar{{g}}_{z}\rangle^{2}}$
$\displaystyle\leq$ $\displaystyle
2\sqrt{\sum_{y=1}^{\ell}\left\|\widehat{{f}}_{y}-\bar{{g}}_{y}\right\|^{2}}\leq
2\sqrt{\Psi(\ell)},$

from which we can conclude that

$\displaystyle\left\|\frac{\sqrt{\mathrm{vol}({S}_{i})}}{\left\|\bar{{x}}^{(i)}\right\|}\cdot{p}^{(i)}-\frac{\sqrt{\mathrm{vol}({S}_{j})}}{\left\|\bar{{x}}^{(j)}\right\|}\cdot{p}^{(j)}\right\|^{2}$
$\displaystyle\geq$
$\displaystyle\left(1-\Psi(\ell)\right)\theta-2\sqrt{\Psi(\ell)}$
$\displaystyle\geq$ $\displaystyle\theta-3\sqrt{\Psi(\ell)}.$

With this we proved the statement. ∎

######  Lemma 5.6.

It holds for any different $i,j\in[k]$ that

$\left\|\frac{{p}^{(i)}}{\left\|{p}^{(i)}\right\|}-\frac{{p}^{(j)}}{\left\|{p}^{(j)}\right\|}\right\|^{2}\geq\frac{\theta}{4}-8\sqrt{\frac{\Psi}{\theta}}.$

###### Proof.

To follow the proof, it may help to refer to the illustration in Figure 4.

$\|\cdot\|=1$$p^{(i)}$$p^{(j)}$$\frac{p^{(i)}}{\|p^{(i)}\|}$$\frac{p^{(j)}}{\|p^{(j)}\|}$$\alpha_{i}$$\alpha_{j}$$\frac{\|\alpha_{i}\|}{\|\alpha_{j}\|}\alpha_{j}$
Figure 4:  Illustration of the proof of Lemma 5.6. Our goal is to give a lower
bound on the length of
$\left(\frac{{p}^{(i)}}{\left\|{p}^{(i)}\right\|}-\frac{{p}^{(j)}}{\left\|{p}^{(j)}\right\|}\right)$,
which is the blue dotted line in the figure. We instead calculate a lower
bound on the length of
$\left({a}_{i}-\frac{\left\|{a}_{i}\right\|}{\left\|{a}_{j}\right\|}\right)$,
which is the green dotted line, and use the fact that by construction,
$\left\|{a}_{i}\right\|\leq 1$ and $\left\|{a}_{j}\right\|\leq 1$.

We set the parameter $\epsilon=4\sqrt{\Psi}/\theta$, and define

${a}_{i}=\frac{\sqrt{\mathrm{vol}({S}_{i})}}{\left(1+\epsilon\right)\left\|\bar{{x}}^{(i)}\right\|}\cdot{p}^{(i)},\qquad\hskip
30.00005pt{a}_{j}=\frac{\sqrt{\mathrm{vol}({S}_{j})}}{\left(1+\epsilon\right)\left\|\bar{{x}}^{(j)}\right\|}\cdot{p}^{(j)}.$

By the definition of $\epsilon$ and Lemma 5.4, it holds that
$\left\|{a}_{i}\right\|\leq 1$, and $\left\|{a}_{j}\right\|\leq 1$. We can
also assume without loss of generality that
$\left\|{a}_{i}\right\|\leq\left\|{a}_{j}\right\|$. Then, as illustrated in
Figure 4, we have

$\left\|\frac{{p}^{(i)}}{\left\|{p}^{(i)}\right\|}-\frac{{p}^{(j)}}{\left\|{p}^{(j)}\right\|}\right\|^{2}\geq\left\|{a}_{i}-\frac{\left\|{a}_{i}\right\|}{\left\|{a}_{j}\right\|}{a}_{j}\right\|^{2},$

and so it suffices to lower bound the right-hand side of the inequality above.
By the triangle inequality, we have

$\displaystyle\left\|{a}_{i}-\frac{\left\|{a}_{i}\right\|}{\left\|{a}_{j}\right\|}{a}_{j}\right\|$
$\displaystyle\geq\left\|{a}_{i}-{a}_{j}\right\|-\left\|{a}_{j}-\frac{\left\|{a}_{i}\right\|}{\left\|{a}_{j}\right\|}{a}_{j}\right\|$
$\displaystyle=\frac{1}{1+\epsilon}\left\|\frac{\sqrt{\mathrm{vol}({S}_{i})}}{\left\|\bar{{x}}^{(i)}\right\|}\cdot{p}^{(i)}-\frac{\sqrt{\mathrm{vol}({S}_{j})}}{\left\|\bar{{x}}^{(j)}\right\|}\cdot{p}^{(j)}\right\|-\left(\left\|{a}_{j}\right\|-\left\|{a}_{i}\right\|\right).$

Now, we have that

$\displaystyle\left\|{a}_{j}\right\|-\left\|{a}_{i}\right\|$
$\displaystyle=\frac{\sqrt{\mathrm{vol}({S}_{j})}}{(1+\epsilon)\left\|\bar{{x}}^{(j)}\right\|}\cdot\left\|{p}^{(j)}\right\|-\frac{\sqrt{\mathrm{vol}({S}_{i})}}{(1+\epsilon)\left\|\bar{{x}}^{(i)}\right\|}\cdot\left\|{p}^{(i)}\right\|$
$\displaystyle\leq 1-\frac{1-\epsilon}{1+\epsilon}$
$\displaystyle=\frac{2\epsilon}{1+\epsilon},$

and have by Lemma 5.5 that

$\displaystyle\left\|\frac{\sqrt{\mathrm{vol}({S}_{i})}}{\left\|\bar{{x}}^{(i)}\right\|}\cdot{p}^{(i)}-\frac{\sqrt{\mathrm{vol}({S}_{j})}}{\left\|\bar{{x}}^{(j)}\right\|}\cdot{p}^{(j)}\right\|$
$\displaystyle\geq\sqrt{\theta-3\sqrt{\Psi(\ell)}}\geq\sqrt{\theta}-\sqrt{2\epsilon}\geq\sqrt{\theta}-2\epsilon.$

since $\epsilon=4\sqrt{\Psi}/\theta<1$ by the assumption on $\Psi$. This gives
us that

$\displaystyle\left\|{a}_{i}-\frac{\left\|{a}_{i}\right\|}{\left\|{a}_{j}\right\|}{a}_{j}\right\|$
$\displaystyle\geq\frac{\sqrt{\theta}-2\epsilon}{1+\epsilon}-\frac{2\epsilon}{1+\epsilon}\geq\frac{1}{2}\left(\sqrt{\theta}-4\epsilon\right).$

Finally, we have that

$\displaystyle\left\|\frac{{p}^{(i)}}{\left\|{p}^{(i)}\right\|}-\frac{{p}^{(j)}}{\left\|{p}^{(j)}\right\|}\right\|^{2}$
$\displaystyle\geq\frac{1}{4}\left(\sqrt{\theta}-16\frac{\sqrt{\Psi(\ell)}}{\theta}\right)^{2}\geq\frac{\theta}{4}-8\sqrt{\frac{\Psi(\ell)}{\theta}},$

which completes the proof. ∎

######  Lemma 5.7.

It holds for different $i,j\in[k]$ that

$\left\|{p}^{(i)}-{p}^{(j)}\right\|^{2}\geq\frac{\theta^{2}-20\sqrt{\theta\cdot\Psi(\ell)}}{16\min\left\\{\mathrm{vol}({S}_{i}),\mathrm{vol}({S}_{j})\right\\}}.$

###### Proof.

We assume without loss of generality that
$\left\|{p}^{(i)}\right\|^{2}\geq\left\|{p}^{(j)}\right\|^{2}$. Then, by Lemma
5.4 and the fact that $\|\bar{{x}}^{(i)}\|^{2}\geq\theta$ holds for any
$i\in[k]$, we have

$\left\|{p}^{(i)}\right\|^{2}\geq\left(1-\frac{4\sqrt{\Psi(\ell)}}{\theta}\right)\cdot\frac{\left\|\bar{{x}}^{(i)}\right\|^{2}}{\mathrm{vol}({S}_{i})},$
$\left\|{p}^{(j)}\right\|^{2}\geq\left(1-\frac{4\sqrt{\Psi(\ell)}}{\theta}\right)\cdot\frac{\left\|\bar{{x}}^{(j)}\right\|^{2}}{\mathrm{vol}({S}_{j})},$

which implies that

$\left\|{p}^{(i)}\right\|^{2}\geq\frac{\theta-4\sqrt{\Psi(\ell)}}{\min\left\\{\mathrm{vol}({S}_{i}),\mathrm{vol}({S}_{j})\right\\}}.$

Now, we will proceed by case distinction.

Case 1: $\left\|{p}^{(i)}\right\|\geq 4\left\|{p}^{(j)}\right\|$. In this
case, we have

$\left\|{p}^{(i)}-{p}^{(j)}\right\|\geq\left\|{p}^{(i)}\right\|-\left\|{p}^{(j)}\right\|\geq\frac{3}{4}\left\|{p}^{(i)}\right\|$

and

$\displaystyle\left\|{p}^{(i)}-{p}^{(j)}\right\|^{2}$
$\displaystyle\geq\frac{9}{16}\cdot\frac{\theta-4\sqrt{\Psi(\ell)}}{\min\left\\{\mathrm{vol}({S}_{i}),\mathrm{vol}({S}_{j})\right\\}}$
$\displaystyle\geq\frac{\theta\left(\theta-20\sqrt{\Psi(\ell)/\theta}\right)}{16\min\left\\{\mathrm{vol}({S}_{i}),\mathrm{vol}({S}_{j})\right\\}}$
$\displaystyle=\frac{\theta^{2}-20\sqrt{\theta\cdot\Psi(\ell)}}{16\min\left\\{\mathrm{vol}({S}_{i}),\mathrm{vol}({S}_{j})\right\\}},$

since $\theta<1$.

Case 2: $\left\|{p}^{(j)}\right\|=\alpha\left\|{p}^{(i)}\right\|$ for some
$\alpha\in\left(\frac{1}{4},1\right]$. By Lemma 5.6, we have

$\displaystyle\left\langle\frac{{p}^{(i)}}{\left\|{p}^{(i)}\right\|},\frac{{p}^{(j)}}{\left\|{p}^{(j)}\right\|}\right\rangle$
$\displaystyle\leq
1-\frac{1}{2}\left(\frac{\theta}{4}-8\sqrt{\frac{\Psi}{\theta}}\right)$
$\displaystyle\leq 1-\frac{\theta}{8}+2\sqrt{\frac{\Psi}{\theta}}.$

Then, it holds that

$\displaystyle\left\|{p}^{(i)}-{p}^{(j)}\right\|^{2}$
$\displaystyle=\left\|{p}^{(i)}\right\|^{2}+\left\|{p}^{(j)}\right\|^{2}-2\left\langle\frac{{p}^{(i)}}{\left\|{p}^{(i)}\right\|},\frac{{p}^{(j)}}{\left\|{p}^{(j)}\right\|}\right\rangle\left\|{p}^{(i)}\right\|\left\|{p}^{(j)}\right\|$
$\displaystyle\geq\left(1+\alpha^{2}\right)\left\|{p}^{(i)}\right\|^{2}-2\left(1-\frac{\theta}{8}+2\sqrt{\frac{\Psi(\ell)}{\theta}}\right)\alpha\left\|{p}^{(i)}\right\|^{2}$
$\displaystyle\geq\left(1+\alpha^{2}-2\alpha+\frac{\theta}{4}\alpha-4\sqrt{\frac{\Psi(\ell)}{\theta}}\alpha\right)\left\|{p}^{(i)}\right\|^{2}$
$\displaystyle\geq\left(\frac{\theta}{4}-4\sqrt{\frac{\Psi(\ell)}{\theta}}\right)\cdot\alpha\cdot\frac{\theta-4\sqrt{\Psi(\ell)}}{\min\left\\{\mathrm{vol}({S}_{i}),\mathrm{vol}({S}_{j})\right\\}}$
$\displaystyle\geq\left(\frac{\theta}{16}-\sqrt{\frac{\Psi(\ell)}{\theta}}\right)\left(\theta-4\sqrt{\Psi}\right)\cdot\frac{1}{\min\left\\{\mathrm{vol}({S}_{i}),\mathrm{vol}({S}_{j})\right\\}}$
$\displaystyle\geq\left(\frac{\theta^{2}}{16}-\frac{5}{4}\sqrt{\theta\Psi(\ell)}\right)\cdot\frac{1}{\min\left\\{\mathrm{vol}({S}_{i}),\mathrm{vol}({S}_{j})\right\\}}$
$\displaystyle=\frac{\theta^{2}-20\sqrt{\theta\Psi(\ell)}}{16\min\left\\{\mathrm{vol}({S}_{i}),\mathrm{vol}({S}_{j})\right\\}}$

which completes the proof. ∎

It is important to recognise that the lower bound in Lemma 5.7 implies a
condition on $\theta$ and $\Psi(\ell)$ under which ${p}^{(i)}$ and ${p}^{(j)}$
are well-spread. With this, we analyse the performance of spectral clustering
when fewer eigenvector are employed to construct the embedding and show that
it works when the optimal clusters present a noticeable pattern.

######  Lemma 5.8.

Let $\\{{A}_{i}\\}_{i=1}^{k}$ be the output of spectral clustering with $\ell$
eigenvectors, and $\sigma$ and ${M}_{\sigma,i}$ be defined as in (4.2) and
(4.3). If $\Psi(\ell)\leq\theta^{3}/1600$, then

$\sum_{i=1}^{k}\frac{\mathrm{vol}({M}_{\sigma,i}\triangle{S}_{i})}{\mathrm{vol}({S}_{i})}\leq
64(1+\textsf{APT})\frac{\Psi(\ell)}{\theta^{2}}.$

###### Proof.

Let us define ${B}_{ij}={A}_{i}\cap{S}_{j}$ to be the vertices in ${A}_{i}$
which belong to the true cluster ${S}_{j}$. Then, we have that

$\displaystyle\sum_{i=1}^{k}\frac{\mathrm{vol}({M}_{\sigma,i}\triangle{S}_{i})}{\mathrm{vol}({S}_{i})}$
$\displaystyle=\sum_{i=1}^{k}\sum_{\begin{subarray}{c}j=1\\\
j\neq\sigma(i)\end{subarray}}^{k}\mathrm{vol}({B}_{ij})\left(\frac{1}{\mathrm{vol}({S}_{\sigma(i)})}+\frac{1}{\mathrm{vol}({S}_{j})}\right)$
$\displaystyle\leq 2\sum_{i=1}^{k}\sum_{\begin{subarray}{c}j=1\\\
j\neq\sigma(i)\end{subarray}}^{k}\frac{\mathrm{vol}({B}_{ij})}{\min\\{\mathrm{vol}({S}_{\sigma(i)}),\mathrm{vol}({S}_{j})\\}},$
(5.4)

and that

$\displaystyle\mathrm{COST}({A}_{1},\ldots{A}_{k})$
$\displaystyle=\sum_{i=1}^{k}\sum_{u\in{A}_{i}}{d}(u)\left\|F(u)-{c}_{i}\right\|^{2}$
$\displaystyle\geq\sum_{i=1}^{k}\sum_{\begin{subarray}{c}1\leq j\leq k\\\
j\neq\sigma(i)\end{subarray}}\sum_{u\in{B}_{ij}}{d}(u)\left\|F(u)-{c}_{i}\right\|^{2}$
$\displaystyle\geq\sum_{i=1}^{k}\sum_{\begin{subarray}{c}1\leq j\leq k\\\
j\neq\sigma(i)\end{subarray}}\sum_{u\in{B}_{ij}}{d}(u)\left(\frac{\left\|{p}^{(j)}-{c}_{i}\right\|^{2}}{2}-\left\|{p}^{(j)}-F(u)\right\|^{2}\right)$
$\displaystyle\geq\sum_{i=1}^{k}\sum_{\begin{subarray}{c}1\leq j\leq k\\\
j\neq\sigma(i)\end{subarray}}\sum_{u\in{B}_{ij}}\frac{{d}(u)\left\|{p}^{(j)}-{p}^{(\sigma(i))}\right\|^{2}}{8}-\sum_{i=1}^{k}\sum_{\begin{subarray}{c}1\leq
j\leq k\\\ j\neq
i\end{subarray}}\sum_{u\in{B}_{ij}}{d}(u)\left\|{p}^{(j)}-F(u)\right\|^{2}$
$\displaystyle\geq\sum_{i=1}^{k}\sum_{\begin{subarray}{c}1\leq j\leq k\\\
j\neq\sigma(i)\end{subarray}}\mathrm{vol}({B}_{ij})\frac{\left\|{p}^{(j)}-{p}^{(\sigma(i))}\right\|^{2}}{8}-\sum_{i=1}^{k}\sum_{u\in{S}_{i}}{d}(u)\left\|{p}^{(i)}-F(u)\right\|^{2}$
$\displaystyle\geq\sum_{i=1}^{k}\sum_{\begin{subarray}{c}1\leq j\leq k\\\
j\neq\sigma(i)\end{subarray}}\frac{\mathrm{vol}({B}_{ij})}{16\cdot\min\\{\mathrm{vol}({S}_{\sigma(i)}),\mathrm{vol}({S}_{j})\\}}\left(\theta^{2}-20\sqrt{\theta\cdot\Psi(\ell)}\right)-\sum_{i=1}^{k}\sum_{u\in{S}_{i}}{d}(u)\left\|{p}^{(i)}-F(u)\right\|^{2}$
$\displaystyle\geq\frac{1}{32}\cdot\left(\sum_{i=1}^{k}\frac{\mathrm{vol}({M}_{\sigma,i}\triangle{S}_{i})}{\mathrm{vol}({S}_{i})}\right)\left(\theta^{2}-20\sqrt{\theta\cdot\Psi(\ell)}\right)-\Psi(\ell),$

where the second inequality follows by the inequality of
$\left\|{a}-{b}\right\|^{2}\geq\frac{\left\|{b}-{c}\right\|^{2}}{2}-\left\|{a}-{c}\right\|^{2}$,
the third inequality follows since ${c}_{i}$ is closer to ${p}^{(\sigma(i))}$
than ${p}^{(j)}$, the fifth one follows from Lemma 5.7, and the last one
follows by (5.4).

On the other hand, since
$\mathrm{COST}({A}_{1},\ldots,{A}_{k})\leq\textsf{APT}\cdot\Psi(\ell)$ by
Lemma 5.3, we have that

$\displaystyle\sum_{i=1}^{k}\frac{\mathrm{vol}({M}_{\sigma,i}\triangle{S}_{i})}{\mathrm{vol}({S}_{i})}$
$\displaystyle\leq
32\cdot(1+\textsf{APT})\cdot\Psi(\ell)\cdot\left(\theta^{2}-20\sqrt{\theta\cdot\Psi(\ell)}\right)^{-1}\leq
64\cdot(1+\textsf{APT})\cdot\Psi(\ell),$

where the last inequality follows by the assumption that
$\Psi(\ell)\leq\theta^{3}/1600$. Therefore, the statement follows. ∎

Combining this with other technical ingredients, including our developed
technique for constructing the desired mapping $\sigma^{*}$ described in
Section 4.2, we obtain the performance guarantee of our designed algorithm,
which is summarised as follows:

######  Theorem 4.

Let ${G}$ be a graph with $k$ clusters $\\{{S}_{i}\\}_{i=1}^{k}$ of almost
balanced size, with a $(\theta,\ell)$-distinguishable meta-graph that
satisfies $\Psi(\ell)\leq\left(2176(1+\textsf{APT})\right)^{-1}\theta^{3}$.
Let $\\{{A}_{i}\\}_{i=1}^{k}$ be the output of spectral clustering with $\ell$
eigenvectors, and without loss of generality let the optimal correspondent of
${A}_{i}$ be ${S}_{i}$. Then, it holds that

$\sum_{i=1}^{k}\mathrm{vol}\left({A}_{i}\triangle{S}_{i}\right)\leq
2176(1+\textsf{APT})\frac{\Psi(\ell)\cdot\mathrm{vol}({V}_{G})}{k\cdot\theta^{2}}.$

###### Proof.

This result can be obtained by using the same technique as the one used in the
proof of Theorem 2, but applying Lemma 5.3 instead of Lemma 4.1 and Lemma 5.8
instead of Lemma 4.6 in the analysis. ∎

Notice that if we take $\ell=k$, then we have that $\theta=1$ and
$\Psi(\ell)\leq k/\Upsilon(k)$ which makes the guarantee in Theorem 4 the same
as the one in Theorem 2. However, if the meta-graph corresponding to the
optimal clusters is $(\theta,\ell)$-distinguishable for large $\theta$ and
$\ell\ll k$, then we can have that $\Psi(\ell)\ll k/\Upsilon(k)$ and Theorem 4
gives a stronger guarantee than the one from Theorem 2.

##  6 Experimental Results

In this section we empirically evaluate the performance of spectral clustering
for finding $k$ clusters while using fewer than $k$ eigenvectors. Our results
on synthetic data demonstrate that for graphs with a clear pattern of
clusters, spectral clustering with fewer than $k$ eigenvectors performs
better. This is further confirmed on real-world datasets including BSDS,
MNIST, and USPS. The code used to produce all experimental results is
available at

https://github.com/pmacg/spectral-clustering-meta-graphs.

We implement the spectral clustering algorithm in Python, using the scipy
library for computing eigenvectors, and the $k$-means algorithm from the
sklearn library. Our experiments on synthetic data are performed on a desktop
computer with an Intel(R) Core(TM) i5-8500 CPU @ 3.00GHz processor and 16 GB
RAM. The experiments on the BSDS, MNIST, and USPS datasets are performed on a
compute server with 64 AMD EPYC 7302 16-Core Processors.

###  6.1 Results on Synthetic Data

We first study the performance of spectral clustering on random graphs whose
clusters exhibit a clear pattern. Given the parameters $n\in\mathbb{Z}^{+}$,
$0\leq q\leq p\leq 1$, and some meta-graph ${M}=({V}_{M},{E}_{M})$ with $k$
vertices, we generate a graph with clusters $\\{{S}_{i}\\}_{i=1}^{k}$, each of
size $n$, as follows. For each pair of vertices $u\in{S}_{i}$ and
$v\in{S}_{j}$, we add the edge $(u,v)$ with probability $p$ if $i=j$ and with
probability $q$ if $i\neq j$ and $(i,j)\in{E}_{M}$. The metric used for our
evaluation is defined by
$\frac{1}{nk}\sum_{i=1}^{k}\left\lvert{S}_{i}\cap{A}_{i}\right\rvert$, for the
optimal matching between the output $\\{{A}_{i}\\}$ and the ground truth
$\\{{S}_{i}\\}$.

In our experiments, we fix $n=1,000$, $p=0.01$, and consider the meta-graphs
$C_{10}$ and $P_{4,4}$, similar to those illustrated in Examples 1 and 2; this
results in graphs with $10,000$ and $16,000$ vertices respectively. We vary
the ratio $p/q$ and the number of eigenvectors used to find the clusters. Our
experimental result, which is reported as the average score over 10 trials and
shown in Figure 5, clearly shows that spectral clustering with fewer than $k$
eigenvectors performs better. This is particularly the case when $p$ and $q$
are close, which corresponds to the more challenging regime in the model.

(a) Meta-Graph $C_{10}$

(b) Meta-Graph $P_{4,4}$

Figure 5:  A comparison of the performance of spectral clustering with
different numbers of eigenvectors for clustering graphs with meta-structures
$C_{10}$ and $P_{4,4}$.

###  6.2 Results on the BSDS Dataset

In this experiment, we study the performance of spectral clustering for image
segmentation when using different numbers of eigenvectors. We consider the
Berkeley Segmentation Data Set (BSDS) [AMFM11], which consists of $500$ images
along with their ground-truth segmentations. For each image, we construct a
similarity graph on the pixels and take $k$ to be the number of clusters in
the ground-truth segmentation555 The BSDS dataset provides several human-
generated ground truth segmentations for each image. Since there are different
numbers of ground truth clusterings associated with each image, in our
experiments we take the target number of clusters for a given image to be the
one closest to the median. . Given a particular image in the dataset, we first
downsample the image to have at most $20,000$ pixels. Then, we represent each
pixel by the point $(r,g,b,x,y)^{\intercal}\in\mathbb{R}^{5}$ where
$r,g,b\in[1,255]$ are the RGB values of the pixel and $x$ and $y$ are the
coordinates of the pixel in the downsampled image. We construct the similarity
graph by taking each pixel to be a vertex in the graph, and for every pair of
pixels ${u},{v}\in\mathbb{R}^{5}$, we add an edge with weight
$\exp(-\left\|{u}-{v}\right\|^{2}/2\sigma^{2})$ where $\sigma=20$. Then we
apply spectral clustering, varying the number of eigenvectors used. We
evaluate each segmentation produced with spectral clustering using the Rand
Index [Ran71] as implemented in the benchmarking code provided along with the
BSDS dataset. For each image, this computes the average Rand Index across all
of the provided ground-truth segmentations for the image. Figure 1 shows two
images from the dataset along with the segmentations produced with spectral
clustering, and Appendix A includes some additional examples. These examples
illustrate that spectral clustering with fewer eigenvectors performs better.

We conduct the experiments on the entire BSDS dataset, and the average Rand
Index of the algorithm’s output is reported in Table 1: it is clear to see
that using $k/2$ eigenvectors consistently out-performs spectral clustering
with $k$ eigenvectors. We further notice that, on $89\%$ of the images across
the whole dataset, using fewer than $k$ eigenvectors gives a better result
than using $k$ eigenvectors.

Number of Eigenvectors | Average Rand Index
---|---
$k$ | 0.71
$k/2$ | 0.74
Optimal | 0.76
Table 1: The average Rand Index across the BSDS dataset for different numbers
of eigenvectors. Optimal refers to the algorithm which runs spectral
clustering with $\ell$ eigenvectors for all possible $\ell\in[k]$ and returns
the output with the highest Rand Index.

###  6.3 Results on the MNIST and USPS Datasets

We further demonstrate the applicability of our results on the MNIST and USPS
datasets [Hul94, LBBH98], which consist of images of hand-written digits, and
the goal is to cluster the data into $10$ clusters corresponding to different
digits. In both the MNIST and USPS datasets, each image is represented as an
array of grayscale pixels with values between $0$ and $255$. The MNIST dataset
has $60,000$ images with dimensions $28\times 28$ and the USPS dataset has
$7291$ images with dimensions $16\times 16$. In each case, we consider each
image to be a single data point in $\mathbb{R}^{(d^{2})}$ where $d$ is the
dimension of the images and construct the $k$-nearest neighbour graph for
$k=3$. For the MNIST dataset, this gives a graph with $60,000$ vertices and
$138,563$ edges and for the USPS dataset, this gives a graph with $7,291$
vertices and $16,715$ edges. We use spectral clustering to partition the
graphs into $10$ clusters. We measure the similarity between the found
clusters and the ground truth using the Adjusted Rand Index (ARI) [GA17],
accuracy (ACC) [Ran71], and Normalised Mutual Information (NMI) [LFK09], and
plot the results in Figure 6. Our experiments show that spectral clustering
with just $7$ eigenvectors gives the best performance on both datasets.

(a) MNIST ARI

(b) MNIST NMI

(c) MNIST ACC

(d) USPS ARI

(e) USPS NMI

(f) USPS ACC

Figure 6:  Experimental results on the MNIST and USPS datasets. These
experiments show that spectral clustering with $7$ eigenvectors gives the best
partition of the input into $10$ clusters.

##  7 Future Work

Our work leaves a number of interesting questions for future research. For
spectral clustering, the only non-trivial assumption remaining in our analysis
is that the optimal clusters have almost balanced size. It is unclear whether,
under the regime of $\Upsilon(k)=\Omega(1)$, this condition could be
eventually removed, or if there’s some hard instance showing that our analysis
is tight. For spectral clustering with fewer eigenvectors, our presented work
is merely the starting point, and leaves many open questions. For example,
although one can enumerate the number of used eigenvectors from $1$ to $k$ and
take the clustering with the minimum $k$-way expansion, we are interested to
know whether the optimal number of eigenvectors can be computed directly, and
rigorously analysed for different graph instances. We believe that the answers
to these questions would not only significantly advance our understanding of
spectral clustering, but also, as suggested in our experimental studies, have
widespread applications in analysing real-world datasets.

## References

  * [ALM13] Zeyuan Allen-Zhu, Silvio Lattanzi, and Vahab Mirrokni.  A local algorithm for finding well-connected clusters.  In 30th International Conference on Machine Learning (ICML’13), pages 396–404, 2013.
  * [AMFM11] Pablo Arbelaez, Michael Maire, Charless C. Fowlkes, and Jitendra Malik.  Contour detection and hierarchical image segmentation.  IEEE Trans. Pattern Anal. Mach. Intell., 33(5):898–916, 2011.
  * [Chu97] Fan R K Chung.  Spectral Graph Theory.  American Mathematical Soc., 1997.
  * [CLSZ20] Mihai Cucuringu, Huan Li, He Sun, and Luca Zanetti.  Hermitian matrices for clustering directed graphs: Insights and applications.  In 23rd International Conference on Artificial Intelligence and Statistics (AISTATS’20), pages 983–992, 2020.
  * [CPS15] Artur Czumaj, Pan Peng, and Christian Sohler.  Testing cluster structure of graphs.  In 47th Annual ACM Symposium on Theory of Computing (STOC’15), pages 723–732, 2015.
  * [CSWZ16] Jiecao Chen, He Sun, David Woodruff, and Qin Zhang.  Communication-optimal distributed clustering.  In 30th Advances in Neural Information Processing Systems (NeurIPS’16), pages 3727–3735, 2016.
  * [DPRS19] Tamal K. Dey, Pan Peng, Alfred Rossi, and Anastasios Sidiropoulos.  Spectral concentration and greedy k-clustering.  Comput. Geom., 76:19–32, 2019.
  * [GA17] Alexander J. Gates and Yong-Yeol Ahn.  The impact of random models on clustering similarity.  The Journal of Machine Learning Research, 18(1):3049–3076, 2017\.
  * [GT14] Shayan Oveis Gharan and Luca Trevisan.  Partitioning into expanders.  In 25th ACM-SIAM Symposium on Discrete Algorithms (SODA’14), pages 1256–1266, 2014.
  * [Hul94] Jonathan J. Hull.  A database for handwritten text recognition research.  IEEE Trans. Pattern Anal. Mach. Intell., 16(5):550–554, 1994.
  * [KLL+13] Tsz Chiu Kwok, Lap Chi Lau, Yin Tat Lee, Shayan Oveis Gharan, and Luca Trevisan.  Improved Cheeger’s inequality: Analysis of spectral partitioning algorithms through higher order spectral gap.  In 45th Annual ACM Symposium on Theory of Computing (STOC’13), pages 11–20, 2013.
  * [KM16] Pavel Kolev and Kurt Mehlhorn.  A note on spectral clustering.  In 24th Annual European Symposium on Algorithms (ESA’16), volume 57, pages 1–14, 2016.
  * [KMN+04] 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.  Comput. Geom., 28(2-3):89–112, 2004.
  * [KSS04] Amit Kumar, Yogish Sabharwal, and Sandeep Sen.  A simple linear time (1+$\epsilon$)-approximation algorithm for k-means clustering in any dimensions.  In 45th Symposium on Foundations of Computer Science (FOCS’04), pages 454–462, 2004.
  * [KUK17] Isabel M. Kloumann, Johan Ugander, and Jon M. Kleinberg.  Block models and personalized PageRank.  Proceedings of the National Academy of Sciences, 114(1):33–38, 2017\.
  * [LBBH98] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner.  Gradient-based learning applied to document recognition.  Proceedings of the IEEE, 86(11):2278–2324, 1998.
  * [LFK09] 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.
  * [LGT14] James R Lee, Shayan Oveis Gharan, and Luca Trevisan.  Multiway spectral partitioning and higher-order cheeger inequalities.  Journal of the ACM (JACM), 61(6):1–30, 2014.
  * [LS20] Steinar Laenen and He Sun.  Higher-order spectral clustering of directed graphs.  34th Advances in Neural Information Processing Systems (NeurIPS’20), 33, 2020.
  * [LV19] Anand Louis and Rakesh Venkat.  Planted models for k-way edge and vertex expansion.  In 39th Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS’19), volume 150, pages 23:1–23:15, 2019.
  * [Miz21] Tomohiko Mizutani.  Improved analysis of spectral algorithm for clustering.  Optimization Letters, 15(4):1303–1325, 2021.
  * [NJW01] Andrew Y Ng, Michael I Jordan, and Yair Weiss.  On spectral clustering: Analysis and an algorithm.  In 15th Advances in Neural Information Processing Systems (NeurIPS’01), pages 849–856, 2001.
  * [OA14] Lorenzo Orecchia and Zeyuan Allen-Zhu.  Flow-based algorithms for local graph clustering.  In 25th ACM-SIAM Symposium on Discrete Algorithms (SODA’14), pages 1267–1286, 2014.
  * [Pen20] Pan Peng.  Robust clustering oracle and local reconstructor of cluster structure of graphs.  In 31st Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’20), pages 2953–2972, 2020.
  * [PSZ17] Richard Peng, He Sun, and Luca Zanetti.  Partitioning well-clustered graphs: Spectral clustering works!  SIAM Journal on Computing, 46(2):710–743, 2017.
  * [PY20] Pan Peng and Yuichi Yoshida.  Average sensitivity of spectral clustering.  In 26th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD’20), pages 1132–1140, 2020.
  * [Ran71] William M. Rand.  Objective criteria for the evaluation of clustering methods.  Journal of the American Statistical Association, 66(336):846–850, 1971.
  * [RV11] Nicola Rebagliati and Alessandro Verri.  Spectral clustering with more than k eigenvectors.  Neurocomputing, 74(9):1391–1401, 2011.
  * [ST96] Daniel A. Spielman and Shang-Hua Teng.  Spectral partitioning works: Planar graphs and finite element meshes.  In 37th Conference on Foundations of Computer Science (FOCS’96), pages 96–105, 1996.
  * [SZ19] He Sun and Luca Zanetti.  Distributed graph clustering and sparsification.  ACM Trans. Parallel Comput., 6(3):17:1–17:23, 2019.
  * [vL07] Ulrike von Luxburg.  A tutorial on spectral clustering.  Statistics and computing, 17(4):395–416, 2007.

##  Appendix A Examples from the BSDS Dataset

Figures 7 and 8 give some additional examples of our results from the BSDS
dataset. These examples further illustrate that spectral clustering with fewer
than $k$ eigenvectors performs better than spectral clustering with $k$
eigenvectors on the BSDS image segmentation dataset.

(a) Original Image

(b) Segmentation into $24$ clusters with $8$ eigenvectors; Rand Index $0.82$.

(c) Segmentation into $24$ clusters with $24$ eigenvectors; Rand Index $0.77$.

(d) Original Image

(e) Segmentation into $18$ clusters with $6$ eigenvectors; Rand Index $0.77$.

(f) Segmentation into $18$ clusters with $18$ eigenvectors; Rand Index $0.74$.

Figure 7: Examples of the segmentations produced with spectral clustering on
the BSDS dataset.

(a) Original Image

(b) Segmentation into $7$ clusters with $3$ eigenvectors; Rand Index $0.76$.

(c) Segmentation into $7$ clusters with $7$ eigenvectors; Rand Index $0.74$.

(d) Original Image

(e) Segmentation into $13$ clusters with $8$ eigenvectors; Rand Index $0.80$.

(f) Segmentation into $13$ clusters with $13$ eigenvectors; Rand Index $0.77$.

(g) Original Image

(h) Segmentation into $8$ clusters with $5$ eigenvectors; Rand Index $0.86$.

(i) Segmentation into $8$ clusters with $8$ eigenvectors; Rand Index $0.79$.

(j) Original Image

(k) Segmentation into $9$ clusters with $7$ eigenvectors; Rand Index $0.69$.

(l) Segmentation into $9$ clusters with $9$ eigenvectors; Rand Index $0.61$.

Figure 8: Examples of the segmentations produced with spectral clustering on
the BSDS dataset.