latexCommand has changed latexCommand has changed

# On Learning the Structure of Clusters in Graphs

Peter Macgregor

###### Abstract

Graph clustering is a fundamental problem in unsupervised learning, with
numerous applications in computer science and in analysing real-world data. In
many real-world applications, we find that the clusters have a significant
high-level structure. This is often overlooked in the design and analysis of
graph clustering algorithms which make strong simplifying assumptions about
the structure of the graph. This thesis addresses the natural question of
whether the structure of clusters can be learned efficiently and describes
four new algorithmic results for learning such structure in graphs and
hypergraphs.

The first part of the thesis studies the classical spectral clustering
algorithm, and presents a tighter analysis on its performance. This result
explains why it works under a much weaker and more natural condition than the
ones studied in the literature, and helps to close the gap between the
theoretical guarantees of the spectral clustering algorithm and its excellent
empirical performance.

The second part of the thesis builds on the theoretical guarantees of the
previous part and shows that, when the clusters of the underlying graph have
certain structures, spectral clustering with fewer than $k$ eigenvectors is
able to produce better output than classical spectral clustering in which $k$
eigenvectors are employed, where $k$ is the number of clusters. This presents
the first work that discusses and analyses the performance of spectral
clustering with fewer than $k$ eigenvectors, and shows that general structures
of clusters can be learned with spectral methods.

The third part of the thesis considers efficient learning of the structure of
clusters with local algorithms, whose runtime depends only on the size of the
target clusters and is independent of the underlying input graph. While the
objective of classical local clustering algorithms is to find a cluster which
is sparsely connected to the rest of the graph, this part of the thesis
presents a local algorithm that finds a pair of clusters which are _densely_
connected to each other. This result demonstrates that certain structures of
clusters can be learned efficiently in the local setting, even in the massive
graphs which are ubiquitous in real-world applications.

The final part of the thesis studies the problem of learning densely connected
clusters in hypergraphs. The developed algorithm is based on a new heat
diffusion process, whose analysis extends a sequence of recent work on the
spectral theory of hypergraphs. It allows the structure of clusters to be
learned in datasets modelling higher-order relations of objects and can be
applied to efficiently analyse many complex datasets occurring in practice.

All of the presented theoretical results are further extensively evaluated on
both synthetic and real-word datasets of different domains, including image
classification and segmentation, migration networks, co-authorship networks,
and natural language processing. These experimental results demonstrate that
the newly developed algorithms are practical, effective, and immediately
applicable for learning the structure of clusters in real-world data.

###### Acknowledgements.

I must begin by thanking my supervisor, He Sun, for his invaluable support
throughout this process. I have immensely benefited from his encouragement,
experience, knowledge, and friendship. Sincere thanks are also due to the many
other friends I made along the way. Thanks are particularly in order for the
walks and online hang-outs which helped me through the COVID-19 lockdowns.
Their ongoing friendship makes life infinitely more enjoyable. I’d like to
thank my family for being as wonderful as anyone could reasonably hope for.
Thanks in particular to my parents. I would not be writing this thesis were it
not for their encouragement of my interest in mathematics from a young age and
for their continuing and unconditional support. Thanks to Dad for the endless
conversations about mathematical puzzles and curiosities [Mac90]. Thanks to
Mum for putting up with us, and for her uncanny ability to spot typos hidden
deep in the technical sections of my papers. Thanks to Granny for permission
to use her photo in the introduction. I extend to her all my love and
congratulations on the occasion of her 90th birthday on 17th August 2022.

###### Contents

  1. List of Algorithms
  2. 1 Introduction
  3. 2 Preliminaries
    1. 2.1 Basic Notation
    2. 2.2 Linear Algebra
    3. 2.3 Graphs
      1. 2.3.1 Spectral Graph Theory
      2. 2.3.2 The Stochastic Block Model
    4. 2.4 Hypergraphs
    5. 2.5 Asymptotic Notation
    6. 2.6 Clustering Metrics
  4. 3 Related Work
    1. 3.1 Spectral Graph Partitioning
      1. 3.1.1 Fiedler Vector
      2. 3.1.2 Cheeger Inequality
      3. 3.1.3 Higher-order Cheeger Inequality
      4. 3.1.4 Spectral Clustering
    2. 3.2 Clustering Structured Graphs
      1. 3.2.1 Partitioning Almost-Bipartite Graphs
      2. 3.2.2 Learning Clusters from Edge Directions
    3. 3.3 Local Graph Clustering
      1. 3.3.1 Pagerank Based Algorithm
      2. 3.3.2 Evolving Set Process
      3. 3.3.3 Other Local Clustering Techniques
    4. 3.4 Spectral Hypergraph Theory
  5. 4 A Tighter Analysis of Spectral Clustering
    1. 4.1 Stronger Structure Theorem
    2. 4.2 Analysis of Spectral Clustering
      1. 4.2.1 Properties of Spectral Embedding
      2. 4.2.2 Bounding the Misclassified Vertices
    3. 4.3 Future Work
  6. 5 Spectral Clustering with Meta-Graphs
    1. 5.1 Encoding the Cluster-Structure into Meta-Graphs
    2. 5.2 Spectral Clustering with Fewer Eigenvectors
    3. 5.3 Experimental Results
      1. 5.3.1 Results on Synthetic Data
      2. 5.3.2 Results on the BSDS Dataset
      3. 5.3.3 Results on the MNIST and USPS Datasets
    4. 5.4 Future Work
  7. 6 Finding Densely Connected Clusters Locally
    1. 6.1 Algorithm for Undirected Graphs
      1. 6.1.1 Reduction by Double Cover
      2. 6.1.2 Design of the Algorithm
      3. 6.1.3 Analysis of ApproximatePagerankDC
      4. 6.1.4 Analysis of LocBipartDC
    2. 6.2 Algorithm for Directed Graphs
      1. 6.2.1 Reduction by Semi-Double Cover
      2. 6.2.2 Design and Analysis of the Algorithm
    3. 6.3 Experimental Results
      1. 6.3.1 Results for Undirected Graphs
      2. 6.3.2 Results for Directed Graphs
    4. 6.4 Future Work
  8. 7 Finding Bipartite Components in Hypergraphs
    1. 7.1 Additional Notation
    2. 7.2 Baseline Algorithms
    3. 7.3 Diffusion Process and Algorithm
      1. 7.3.1 Diffusion Process in Graphs
      2. 7.3.2 Hypergraph Diffusion and our Algorithm
      3. 7.3.3 Dealing with the Diffusion Continuity Condition
    4. 7.4 Existence of Diffusion Process
      1. 7.4.1 Computing ${\bm{r}}$ by a Linear Program
      2. 7.4.2 Analysis of the Linear Program
    5. 7.5 Analysis of Algorithm 1
      1. 7.5.1 Convergence of the Diffusion Process
      2. 7.5.2 Cheeger-type Inequality for Hypergraph Bipartiteness
    6. 7.6 Further Study of the Hypergraph Laplacian Spectrum
      1. 7.6.1 Discussion on the Number of Eigenvectors of ${\mathbf{J}}_{H}$ and ${\mathbf{L}}_{H}$
      2. 7.6.2 Hardness of Finding the Minimum Eigenvalue of ${\mathbf{J}}_{H}$
    7. 7.7 Experimental Results
      1. 7.7.1 Synthetic Datasets
      2. 7.7.2 Real-world Datasets
    8. 7.8 Future Work

###### List of Figures

  1. 1.1 The MNIST dataset
  2. (a)
  3. (b)
  4. 1.2 Image segmentation based on graph clustering
  5. (a) Original Image
  6. (b) Segmented Image
  7. 1.3 Output of our algorithm on the interstate dispute dataset
  8. (a) 1900-1950
  9. (b) 1990-2010
  10. 2.1 A random graph from the stochastic block model
  11. 2.2 An example hypergraph
  12. 3.1 A hypercube graph and the cut with minimum conductance
  13. 3.2 A cycle graph and the cut with minimum conductance
  14. 3.3 Why does spectral clustering work?
  15. 3.4 A random walk
  16. 5.1 Example images from the MNIST dataset
  17. 5.2 The $k$ nearest neighbour graph of the MNIST dataset
  18. 5.3 Examples of image segmentation using spectral clustering
  19. (a) Original Image
  20. (b) $6$ clusters with $3$ vectors
  21. (c) $6$ clusters with $6$ vectors
  22. (d) Original Image
  23. (e) $45$ clusters with $7$ vectors
  24. (f) $45$ clusters with $45$ vectors
  25. 5.4 Spectral embedding of a graph whose clusters exhibit a cyclical structure
  26. (a)  Spectral embedding of $C_{6}$ with ${\bm{g}}_{2}$ and ${\bm{g}}_{3}$.
  27. (b) Spectral embedding of ${G}$ with ${\bm{f}}_{2}$ and ${\bm{f}}_{3}$.
  28. 5.5 Spectral embedding of a graph whose clusters exhibit a grid structure
  29. (a)  Embedding of $P_{4,4}$ with ${\bm{g}}_{2}$ and ${\bm{g}}_{3}$.
  30. (b) Embedding of ${G}$ with ${\bm{f}}_{2}$ and ${\bm{f}}_{3}$.
  31. 5.6 Illustration of the proof of Lemma 5.6
  32. 5.7 The performance of spectral clustering with fewer eigenvectors
  33. (a)  Meta-Graph $C_{10}$
  34. (b)  Meta-Graph $P_{4,4}$
  35. 5.8 Experimental results on the MNIST and USPS datasets
  36. (a)
  37. (b)
  38. (c)
  39. (d)
  40. 5.9 Additonal examples from the BSDS dataset
  41. (a) Original Image
  42. (b) Segmentation into $24$ clusters with $8$ eigenvectors; Rand Index $0.82$.
  43. (c) Segmentation into $24$ clusters with $24$ eigenvectors; Rand Index $0.77$.
  44. (d) Original Image
  45. (e) Segmentation into $18$ clusters with $6$ eigenvectors; Rand Index $0.77$.
  46. (f) Segmentation into $18$ clusters with $18$ eigenvectors; Rand Index $0.74$.
  47. 5.10 Additional examples from the BSDS dataset
  48. (a) Original Image
  49. (b) Segmentation into $7$ clusters with $3$ eigenvectors; Rand Index $0.76$.
  50. (c) Segmentation into $7$ clusters with $7$ eigenvectors; Rand Index $0.74$.
  51. (d) Original Image
  52. (e) Segmentation into $13$ clusters with $8$ eigenvectors; Rand Index $0.80$.
  53. (f) Segmentation into $13$ clusters with $13$ eigenvectors; Rand Index $0.77$.
  54. (g) Original Image
  55. (h) Segmentation into $8$ clusters with $5$ eigenvectors; Rand Index $0.86$.
  56. (i) Segmentation into $8$ clusters with $8$ eigenvectors; Rand Index $0.79$.
  57. (j) Original Image
  58. (k) Segmentation into $9$ clusters with $7$ eigenvectors; Rand Index $0.69$.
  59. (l) Segmentation into $9$ clusters with $9$ eigenvectors; Rand Index $0.61$.
  60. 6.1 Example output of the LocBipartDC algorithm
  61. (a) 1816-1900
  62. (b) 1900-1950
  63. (c) 1950-1990
  64. (d) 1990-2010
  65. 6.2 Example output of the EvoCutDirected algorithm
  66. (a) Ohio Seed
  67. (b) New York Seed
  68. (c) California Seed
  69. (d) Florida Seed
  70. 6.3 Construction of the double cover
  71. 6.4 A non-simple set in the double cover which has low conductance
  72. 6.5 An example of a directed graph and its semi-double cover
  73. 6.6 Runtime comparison of LocBipartDC and LP
  74. (a)
  75. (b)
  76. 6.7 Experimental results for LocBipartDC
  77. (a)
  78. (b)
  79. 6.8 The top $4$ pairs of clusters found by CLSZ on the US Migration dataset
  80. (a) CLSZ, Pair 1
  81. (b) CLSZ, Pair 2
  82. (c) CLSZ, Pair 3
  83. (d) CLSZ, Pair 4
  84. 6.9 Example showing that LocBipartDC cannot be used for directed graphs
  85. 7.1 Hypergraph signless Laplacian diffusion process
  86. 7.2 Hypergraphs illustrating the downside of simple reductions
  87. 7.3 Illustration of ${S}_{{\bm{f}}}(e)$ and ${I}_{{\bm{f}}}(e)$
  88. 7.4 Max-flow graph used in proof of Lemma 7.5
  89. (a)
  90. (b)
  91. 7.5 Graphs corresponding to hypergraph Laplacian eigenvalues
  92. 7.6 Graphs corresponding to hypergraph signless Laplacian eigenvalues
  93. 7.7 Experimental results of hypergraph partitioning on synthetic data
  94. (a) ${\beta}_{H}$-value
  95. (b) Runtime
  96. 7.8 Further experimental results of hypergraph partitioning on synthetic data
  97. (a) $\beta_{H}$-value
  98. (b) $F_{1}$-score

###### List of Tables

  1. 5.1 Experimental results for image segmentation with spectral clustering
  2. 6.1 Comparison between LocBipartDC and the previous state-of-the art
  3. 6.2 Comparison of ECD with CLSZ on synthetic data.
  4. 6.3 Comparison of EvoCutDirected with CLSZ on the US migration dataset.
  5. 7.1 The runtime of the FBCA and CC algorithms
  6. 7.2 The performance of the FBCA and CC algorithms on real-world datasets

### List of Algorithms

loa

## Chapter 1Introduction

Graphs are a natural tool to represent many datasets and have proved
invaluable in many diverse areas of data science such as recommendation
systems [ABC+08, AM07], image segmentation [SM00, SZ19, ZZL+21], and
bioinformatics [HdK21, GPP+22]. One of the most fundamental operations in
these applications is _graph clustering_ , in which the goal is to partition
the vertices of a graph into disjoint clusters. A cluster is usually defined
to be a set of vertices in the graph such that there are many edges connecting
vertices inside the cluster, while there are few edges connecting the cluster
to the rest of the graph. However, this definition fails to tell the whole
story. In many real-world applications, we find that the clusters also have a
significant high-level structure which is often overlooked in the design and
analysis of graph clustering algorithms. Throughout this thesis, we will
discuss several methods for learning this high-level structure of clusters,
and for exploiting this structure to develop improved algorithms for graph
clustering.

In order to better understand the structure of clusters in graphs, let us
consider some examples constructed from real-world data. We begin by
considering the well-known MNIST dataset which consists of 70,000 images of
handwritten digits from 0 to 9. Each image has $28\times 28$ greyscale pixels,
and each pixel takes a value from 0 to 255. This dataset is not given to us as
a graph, but we can employ a common tool to convert almost any generic dataset
into a graph: the _$k$ nearest neighbour graph_. To do this, we consider each
image in the dataset to be a vertex in the graph, and connect each vertex $v$
to the vertices representing the images which are the ‘most similar’ to the
image represented by $v$. This construction is described more formally in
Chapter 5. Figure 1.1 illustrates the $k$ nearest neighbour graph for a
randomly chosen subset of the data.

(a)

(b)

Figure 1.1: (a) Example images from the MNIST dataset. (b) The $k$ nearest
neighbour graph of a random subset of the MNIST dataset, for $k=3$. The graph
has a cluster corresponding to each digit.

Notice that in the constructed graph there are 10 clusters, which correspond
to the ground truth clusters of images representing each digit. A vertex in a
given cluster tends to be more strongly connected with other vertices inside
the same cluster than with vertices in other clusters. There is also
additional high-level structure due to the relative similarity of different
digits. For example, the cluster representing the digit 4 has more connections
with the cluster representing 9 than the one representing 6. This is the
_high-level structure_ which has been overlooked in previous clustering
algorithms, and we study such structures in more detail in Chapter 5.

We will also look at another learning task for image data: image segmentation.
In this case, we are given an arbitrary image, and the goal is to partition
the pixels into some number of clusters such that each cluster corresponds to
a different region of the image. This time, we will construct a graph from a
single image in the following way: we first represent each pixel in the image
by a point $(r,g,b,x,y)^{\intercal}\in\mathbb{R}^{5}$ where $r,g,b\in[1,255]$
are the red, green, and blue values of the pixel and $x$ and $y$ are the
coordinates of the pixel in the image. Then, we construct the similarity graph
by taking each pixel to be a vertex in the graph, and for every pair of pixels
${\bm{u}},{\bm{v}}\in\mathbb{R}^{5}$, we add an edge with weight
$\exp(-\left\|{\bm{u}}-{\bm{v}}\right\|^{2}/2\sigma^{2})$ for some parameter
$\sigma$. Notice that this graph combines the spatial and colour information
of each pixel, such that we might expect each region of the image to be a
separate cluster in the graph. We can then use a graph clustering algorithm to
find these regions and segment the image. Once again, we can reasonably expect
that the clusters in the graph constructed from the image will have some high-
level structure. For example, a cluster representing a given region of the
image will be more closely related to clusters of pixels with similar colours,
or clusters representing neighbouring regions. We will see in Chapter 5 that
this structure of clusters allows us to develop an improved graph-based image
segmentation algorithm than the ones previously studied in the literature, and
the results of this algorithm are also shown in Figure 1.2.

(a) Original Image

(b) Segmented Image

Figure 1.2: An example of image segmentation using the clustering algorithm in
Chapter 5.

Finally, we will consider a completely different example dataset in which we
are interested in learning the structure of clusters in a graph. The
_interstate dispute dataset_ records every military dispute between pairs of
countries during 1816–2010, including the level of hostility resulting from
the dispute and the number of casualties if applicable. This dataset already
has a natural graph structure: for a given time period, we can construct a
graph from the data by representing each country with a vertex and adding an
edge between each pair of countries weighted according to the severity of
their military disputes. Notice that since the edges in this graph represent a
‘negative’ relationship between countries, we would expect that a cluster of
allied countries would not contain many edges inside the cluster. On the other
hand, two different clusters might be densely connected to each other when
there are two groups of opposing countries. If we wish to develop an algorithm
for finding the clusters in this graph, clearly we must take the high-level
structure into account and most existing graph clustering algorithms will not
perform well. In Chapter 6, we will develop an algorithm capable of learning
the clusters in this dataset which correspond to the underlying geopolitical
relationships between countries. Figure 1.3 demonstrates that from this
dataset, our algorithm is able to identify changes in geopolitics over time,
including the changing roles of Russia, Japan, and Eastern Europe during the
20th century.

(a) 1900-1950

(b) 1990-2010

Figure 1.3:  Clusters found by the algorithm from Chapter 6 on the interstate
dispute dataset. For any given time period and using the USA as a ‘seed’, the
algorithm returns two densely connected clusters representing groups of allied
countries. The results are well explained by geopolitics, and capture the
changing political picture during the 20th century.

Although our highlighted examples come from different domains and the method
used to construct a graph is different in each case, their common theme is
that the clusters in the generated graphs have a significant high-level
structure. In this thesis we will see that these structures can be learned
efficiently through our newly developed algorithms and that the cluster
structure can be used to significantly improve the performance of spectral
clustering. Throughout the thesis, we will touch on a wide variety of
techniques from the field of algorithmic spectral graph theory, which studies
the matrix representations of graphs and applies the algebraic properties of
these matrices to design efficient algorithms. Along the way, we will examine
the classical spectral clustering algorithm (Chapters 4 and 5), random walks
and local algorithms (Chapter 6), and the recently emerging spectral
hypergraph theory based on non-linear heat diffusion operators (Chapter 7).
The newly developed techniques are all extensively evaluated on real-world
datasets including those introduced above, and the results demonstrate a wide
applicability for learning the structure of clusters in natural datasets. The
remainder of the thesis is organised as follows.

  * •

Chapter 2 introduces the basic mathematical concepts and notation which is
used throughout the thesis, including a brief introduction to linear algebra,
graphs, and hypergraphs. Additionally, this chapter introduces the field of
spectral graph theory, on which most of the results in this thesis are based.

  * •

Chapter 3 describes the previous work which is most related to the methods and
results presented in later chapters. This includes a detailed description of
the history of spectral graph partitioning, techniques for local graph
clustering, and spectral hypergraph theory. This chapter forms an important
reference in order to understand the technical material of the thesis.

  * •

Chapter 4 studies spectral clustering, and presents a tighter analysis on its
performance. This result explains why spectral clustering works under a much
weaker and more natural condition than the ones previously studied in the
literature, and helps to close the gap between the theoretical guarantees of
the spectral clustering algorithm and its excellent empirical performance.
This chapter is largely based on Sections 3 and 4 of Macgregor and Sun [MS22].

  * •

Chapter 5 builds on the theoretical guarantees of the previous chapter and
shows that, when the clusters of the underlying graph have certain structures,
spectral clustering with fewer than $k$ eigenvectors is able to produce better
output than classical spectral clustering in which $k$ eigenvectors are
employed, where $k$ is the number of clusters. This chapter includes
experiments on the MNIST dataset and the BSDS dataset for image segmentation,
and demonstrates improved clustering performance over previous methods. This
chapter is based on Sections 5 and 6 of Macgregor and Sun [MS22].

  * •

Chapter 6 considers efficient learning of the structure of clusters with local
algorithms, whose runtime depends only on the size of the target clusters and
is independent of the underlying input graph. The experimental part of the
chapter focuses on graphs like the interstate dispute dataset, in which
clusters are _densely_ connected to each other, and demonstrates that certain
structures of clusters can be learned efficiently in the local setting. This
chapter is based on Macgregor and Sun [MS21b].

  * •

Finally, Chapter 7 studies the problem of learning densely connected clusters
in hypergraphs. The developed algorithm is based on a new heat diffusion
process, whose analysis extends a sequence of recent work on the spectral
theory of hypergraphs. It allows the structure of clusters to be learned in
datasets modelling higher-order relations of objects and can be applied to
efficiently analyse many complex datasets occurring in practice. This chapter
is based on Macgregor and Sun [MS21a].

## Chapter 2Preliminaries

This chapter introduces the basic technical concepts which form the
prerequisites for understanding the material in this thesis. Although most of
the concepts listed here are standard, everything is included so that the
thesis is as self-contained as possible. The chapter is divided into six
sections. Section 2.1 defines some basic mathematical notation; Section 2.2
gives a brief introduction to concepts from linear algebra; Section 2.3
introduces graphs and spectral graph theory; Section 2.4 defines hypergraphs;
Section 2.5 defines asymptotic notation used in the analysis of algorithms;
finally, Section 2.6 defines the metrics used to evaluate clustering
algorithms.

###  2.1 Basic Notation

Let us first define some of the mathematical notation used throughout the
thesis. The set of real numbers is given by $\mathbb{R}$, the set of integers
is $\mathbb{Z}$, and the set of complex numbers is $\mathbb{C}$. Occasionally,
$\mathbb{R}_{\geq 0}$ or $\mathbb{Z}_{\geq 0}$ are used to restrict these sets
to have non-negative values. For any $n\in\mathbb{Z}_{\geq 0}$, the notation
$[n]$ is used to mean $\\{1,2,\ldots,n\\}$. For some logical proposition $X$,
the expression
$\boldsymbol{\left[\vphantom{X}\right.}X\boldsymbol{\left.\vphantom{X}\right]}$
is equal to $1$ if $X$ is true, or $0$ otherwise. For example, we say that
$\boldsymbol{\left[\vphantom{a=b}\right.}a=b\boldsymbol{\left.\vphantom{a=b}\right]}$
is equal to $1$ if $a=b$, and it is equal to $0$ otherwise. For any operators
$f,g:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$, we define $f\circ
g:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ by $\left(f\circ
g\right)(v)\triangleq f(g(v))$ for any $v$. Given two sets ${A}$ and ${B}$,
the set difference is expressed as ${A}\setminus{B}$. The symmetric difference
between the sets $A$ and $B$ is given by
${A}\triangle{B}\triangleq\left({A}\setminus{B}\right)\cup\left({B}\setminus{A}\right)$.
When ${A}$ is a subset of some universe ${U}$, the complement of ${A}$ is
given by $\overline{{A}}\triangleq{U}\setminus{A}$. For any set ${A}$, we use
$2^{A}$ to denote the power set of ${A}$; that is, $2^{A}$ is the set
consisting of all possible subsets of ${A}$.

###  2.2 Linear Algebra

The subject of this thesis lies at the intersection of linear algebra and
graph theory. As such, let us review some basic concepts in linear algebra. A
vector ${\bm{x}}\in\mathbb{R}^{n}$ is written as
$({\bm{x}}(1),{\bm{x}}(2),\ldots,{\bm{x}}(n))^{\intercal}$. Notice that we use
${\bm{x}}(i)$ to refer to the $i$-th element in the vector ${\bm{x}}$.
Subscripts, such as ${\bm{x}}_{i}$, are used to distinguish between different
vectors. For a vector ${\bm{x}}\in\mathbb{R}^{n}$ and a set ${A}\subseteq[n]$,
let ${\bm{x}}({A})=\sum_{i\in A}{\bm{x}}(i)$. For any vectors
${\bm{x}},{\bm{y}}\in\mathbb{R}^{n}$, we write ${\bm{x}}\preceq{\bm{y}}$ if it
holds for all $v$ that ${\bm{x}}(v)\leq{\bm{y}}(v)$. We will use
${\bm{1}}_{n}\in\mathbb{R}^{n}$ to represent the vector with
${\bm{1}}_{n}(i)=1$ for all $i\in[n]$ and ${\bm{0}}_{n}$ to represent the
vector with ${\bm{0}}_{n}(i)=0$. For any vector ${\bm{x}}$, we define the
support of ${\bm{x}}$ to be $\mathrm{supp}({\bm{x}})=\\{u:{\bm{x}}(u)\neq
0\\}$. Given any two vectors ${\bm{v}},{\bm{u}}\in\mathbb{R}^{n}$, the inner
product of ${\bm{v}}$ and ${\bm{u}}$ is written as
$\left\langle{\bm{v}},{\bm{u}}\right\rangle$ or ${\bm{v}}^{\intercal}{\bm{u}}$
and defined to be $\sum_{i=1}^{n}{\bm{v}}(i){\bm{u}}(i)$. Throughout the
thesis we will use the Euclidean norm, defined for any
${\bm{v}}\in\mathbb{R}^{n}$ as

$\left\|{\bm{v}}\right\|=\sqrt{\left\langle{\bm{v}},{\bm{v}}\right\rangle}=\sqrt{\sum_{i=1}^{n}{\bm{v}}(i)^{2}}.$

Given a set of vectors $\\{{\bm{v}}_{1},\ldots,{\bm{v}}_{n}\\}$, their span is
denoted by $\mathrm{span}({\bm{v}}_{1},\ldots{\bm{v}}_{n})$ and is defined to
be the set of vectors ${\bm{x}}$ which can be written as a linear combination
of ${\bm{v}}_{1},\ldots,{\bm{v}}_{n}$. That is,
${\bm{x}}\in\mathrm{span}({\bm{v}}_{1},\ldots,{\bm{v}}_{n})$ if and only if

${\bm{x}}=\sum_{i=1}^{n}c_{i}{\bm{v}}_{i}$

for some numbers $c_{1},\ldots,c_{n}\in\mathbb{R}$.

Given a matrix ${\mathbf{M}}\in\mathbb{R}^{n\times m}$, the expression
${\mathbf{M}}(i,j)$ is the element in the $i$-th row and $j$-th column of the
matrix. An eigenvector of a matrix ${\mathbf{M}}\in\mathbb{R}^{n\times n}$ is
any vector ${\bm{v}}\in\mathbb{R}^{n}$ such that ${\bm{v}}\neq{\bm{0}}_{n}$
and

${\mathbf{M}}{\bm{v}}=\lambda{\bm{v}}$

for some $\lambda\in\mathbb{R}$, and $\lambda$ is called an eigenvalue. When
discussing some matrix ${\mathbf{M}}\in\mathbb{R}^{n\times n}$, we often use
$\lambda_{1},\ldots,\lambda_{n}$ to denote the eigenvalues of ${\mathbf{M}}$
and ${\bm{f}}_{1},\ldots{\bm{f}}_{n}$ for the eigenvectors. Occasionally, we
consider matrices with complex-valued entries. Recall that for any complex
number $x=a+b\cdot\mathit{i}$, the complex conjugate of $x$ is given by
$\overline{x}=a-b\cdot\mathit{i}$. For any ${\mathbf{M}}\in\mathbb{C}^{n\times
n}$, the conjugate transpose of ${\mathbf{M}}$ is written as
${\mathbf{M}}^{\dagger}$, and is constructed by taking the transpose of
${\mathbf{M}}$ and replacing each entry with its complex conjugate. A matrix
${\mathbf{M}}$ is said to be Hermitian if
${\mathbf{M}}={\mathbf{M}}^{\dagger}$. A real matrix ${\mathbf{M}}$ is
positive semi-definite (PSD) if and only if it holds that

${\bm{x}}^{\intercal}{\mathbf{M}}{\bm{x}}\geq 0$

for all ${\bm{x}}\in\mathbb{R}^{n}$. It is equivalent to say that all of the
eigenvalues of ${\mathbf{M}}$ are non-negative.

The following theorem, known as the Courant-Fischer Theorem, characterises the
eigenvectors and eigenvalues of a symmetric matrix with respect to an
optimisation over $\mathbb{R}^{n}$.

######  Theorem 2.1 (Courant-Fischer Theorem).

Let ${\mathbf{M}}$ be a real symmetric matrix with eigenvalues
$\lambda_{1}\leq\ldots\leq\lambda_{n}$. Then

$\lambda_{k}=\min_{\begin{subarray}{c}S\subset\mathbb{R}^{n}\\\
\mathrm{dim}(S)=k\end{subarray}}\hskip
5.0pt\max_{\begin{subarray}{c}{\bm{x}}\in S\\\
{\bm{x}}\neq{\bm{0}}_{n}\end{subarray}}\frac{{\bm{x}}^{\intercal}{\mathbf{M}}{\bm{x}}}{{\bm{x}}^{\intercal}{\bm{x}}},$

where the minimisation is taken over all $k$ dimensional subspaces of
$\mathbb{R}^{n}$.

###  2.3 Graphs

An undirected graph ${G}=({V},{E},{w})$ is defined by a set of vertices ${V}$,
a set of edges ${E}$, and a weight function
${w}:{V}\times{V}\rightarrow\mathbb{R}_{\geq 0}$. Every edge $e\in{E}$ is an
unordered pair $\\{v,u\\}$ where $v,u\in{V}$ and $v{\sim}u$ is used to mean
that $\\{v,u\\}\in{E}$. The weight function ${w}$ is defined such that
${w}(v,u)>0$ if $\\{v,u\\}\in{E}$ and ${w}(v,u)=0$ otherwise. Sometimes, the
weight function $w$ is omitted when discussing a graph and in this case the
weight of every edge can be taken to be $1$. In this thesis, we consider only
graphs with non-negative edge weights. A directed graph is defined similarly
to an undirected graph, but in this case each edge $e\in{E}$ is an _ordered_
pair $(u,v)$. Unless otherwise specified, the graphs defined in this thesis
are undirected. Sometimes, the vertex and edge sets of different graphs are
distinguished by subscript, such as ${G}=({V}_{G},{E}_{G},{w}_{G})$ and
${H}=({V}_{H},{E}_{H},{w}_{H})$.

Given some graph ${G}=({V},{E},{w})$, the number of vertices in a graph is
commonly given by $n=\left\lvert{V}\right\rvert$. The degree of any vertex
$v\in{V}$ is defined by ${d}(v)\triangleq\sum_{u\in{V}}{w}(v,u)$, and the set
of neighbours of $v$ is ${N}(v)\triangleq\\{u\in{V}:\\{v,u\\}\in{E}\\}$. When
${G}=({V},{E})$ is a directed graph, for any $v\in{V}$ we use
${d}_{\mathrm{out}}(v)$ and ${d}_{\mathrm{in}}(v)$ to express the number of
edges with $v$ as the tail or the head, respectively. For any ${S}\subset{V}$,
we define
$\mathrm{vol}_{\mathrm{out}}({S})=\sum_{v\in{S}}{d}_{\mathrm{out}}(v)$, and
$\mathrm{vol}_{\mathrm{in}}({S})=\sum_{v\in{S}}{d}_{\mathrm{in}}(v)$.

For an undirected graph ${G}=({V},{E})$ and any ${S}\subseteq{V}$, the volume
of ${S}$ is defined by $\mathrm{vol}({S})\triangleq\sum_{v\in{S}}{d}(v)$, and
for two sets ${S}_{1},{S}_{2}\subseteq{V}$ let us define the weight between
${S}_{1}$ and ${S}_{2}$ by

${w}({S}_{1},{S}_{2})\triangleq\sum_{v\in{S}_{1}}\sum_{u\in{S}_{2}}{w}(v,u).$

The conductance of ${S}\subset{V}$ is given by

${\Phi}({S})\triangleq\frac{{w}({S},\overline{{S}})}{\min\\{\mathrm{vol}({S}),\mathrm{vol}(\overline{{S}})\\}}.$

Notice that if ${\Phi}({S})=0$, then ${S}$ is disconnected from the rest of
the graph. Loosely, if ${\Phi}({S})$ is low, then there are only a small
number of edges connecting ${S}$ to the rest of the graph and we can say that
${S}$ forms a cluster in the graph. The conductance of the graph
${G}=({V},{E})$ is given by

${\Phi}_{G}\triangleq\min_{\begin{subarray}{c}{S}\subsetneq{V}\\\
{S}\neq\emptyset\end{subarray}}{\Phi}({S}).$

The boundary of ${S}\subset{V}$ is given by

$\partial({S})\triangleq\\{\\{u,v\\}\in{E}:u\in{S},v\not\in{S}\\}.$

The indicator vector of a set ${S}\subseteq{V}$ is given by
${\bm{\chi}}_{S}\in\mathbb{R}^{n}$, where

${\bm{\chi}}_{S}(v)=\left\\{\begin{array}[]{ll}1&\mbox{if }v\in{S},\\\
0&\mbox{otherwise.}\end{array}\right.$

If ${S}$ contains only a single vertex $v$, we can write ${\bm{\chi}}_{v}$
instead of ${\bm{\chi}}_{\\{v\\}}$.

A graph ${G}=({V},{E})$ is said to be bipartite if the vertex set can be
decomposed into disjoint sets ${L}$ and ${R}$ such that every edge $e\in{E}$
connects a vertex in ${L}$ with a vertex in ${R}$. That is, for all $e\in{E}$,
it holds that $e\cap{L}\neq\emptyset$ and $e\cap{R}\neq\emptyset$. A connected
component of ${G}$ is any maximal set of vertices ${S}\subseteq{V}$ such that
there is a path from any vertex in ${S}$ to every other vertex in ${S}$.

####  2.3.1 Spectral Graph Theory

Having introduced linear algebra and graph theory, let us now take their
intersection. Spectral graph theory is the study of the eigenvalues and
eigenvectors of various matrices associated with a graph. This section gives a
brief introduction to the key concepts in spectral graph theory, and Chapter 3
includes several specific results which are used in this thesis. For a
comprehensive overview of the field, we refer the reader to Chung’s excellent
book [Chu97].

Given a graph ${G}=({V},{E},{w})$ with $n$ vertices, let us label the vertices
as ${V}=\\{v_{1},v_{2},\ldots,v_{n}\\}$. Then, the adjacency matrix of ${G}$
is given by ${\mathbf{A}}\in\mathbb{R}^{n\times n}$ where
${\mathbf{A}}(i,j)={w}(v_{i},v_{j})$. The degree matrix
${\mathbf{D}}\in\mathbb{R}^{n\times n}$ is a diagonal matrix whose non-zero
entries are ${\mathbf{D}}(i,i)={d}(v_{i})$ for $i\in[n]$. A key object of
study in spectral graph theory is the Laplacian matrix of ${G}$ which is
defined to be

${\mathbf{L}}={\mathbf{D}}-{\mathbf{A}}.$

The most useful property of this operator is the expression given by its
quadratic form. Given some vector ${\bm{x}}\in\mathbb{R}^{n}$, the Laplacian
quadratic form is given by

${\bm{x}}^{\intercal}{\mathbf{L}}{\bm{x}}=\sum_{\\{u,v\\}\in{E}}{w}(u,v)\left({\bm{x}}(u)-{\bm{x}}(v)\right)^{2}.$

It is also common to instead consider the normalised Laplacian matrix, which
is defined as

${\mathbf{N}}={\mathbf{D}}^{-\frac{1}{2}}{\mathbf{L}}{\mathbf{D}}^{-\frac{1}{2}}={\mathbf{I}}-{\mathbf{D}}^{-\frac{1}{2}}{\mathbf{A}}{\mathbf{D}}^{-\frac{1}{2}}.$

We also use the signless Laplacian operator defined as

${\mathbf{J}}\triangleq{\mathbf{D}}+{\mathbf{A}},$

and its normalised counterpart

${\mathbf{Z}}\triangleq{\mathbf{D}}^{-\frac{1}{2}}{\mathbf{J}}{\mathbf{D}}^{-\frac{1}{2}}.$

Many results in spectral graph theory focus on the eigenvectors and
eigenvalues of the normalised Laplacian matrix. The $n$ eigenvalues are often
given in order of increasing value, and are represented by
$\lambda_{1}\leq\lambda_{2}\leq\ldots\leq\lambda_{n}$. The corresponding
eigenvectors are often denoted by ${\bm{f}}_{1},\ldots,{\bm{f}}_{n}$. Notice
that the Laplacian matrix uniquely defines the original graph, and so the
eigenvectors and eigenvalues of the Laplacian fully describe the graph. A
recurring theme in spectral graph theory is that, in many cases, we can tell a
lot about a graph from only a small number of eigenvalues and eigenvectors.
The following basic results in spectral graph theory are not difficult to
prove, and can be found in [Chu97].

  1. 1.

The eigenvalues of ${\mathbf{N}}$ all lie between $0$ and $2$.

  2. 2.

The smallest eigenvalue of ${\mathbf{N}}$ is always equal to $0$.

  3. 3.

If the graph has $k$ connected components, then the smallest eigenvalue of
${\mathbf{N}}$ has multiplicity $k$.

  4. 4.

The largest eigenvalue of ${\mathbf{N}}$ is equal to $2$ if and only if the
graph has a bipartite connected component.

Figure 2.1:  A random graph sampled from $\mathrm{SBM}(60,3,0.9,0.05)$.

####  2.3.2 The Stochastic Block Model

It is useful to evaluate the performance of graph clustering algorithms on
graphs with a known ground-truth clustering. A popular model for generating
such random graphs is the stochastic block model (SBM), and we use several
variants of this model throughout the thesis. For $n,k\in\mathbb{Z}_{\geq 0}$
and $p,q\in[0,1]$ the model $\mathrm{SBM}(n,k,p,q)$ defines a random graph on
$n$ vertices in which the vertices are split evenly between $k$ clusters
${S}_{1},\ldots,{S}_{k}$. Every pair of vertices $u$ and $v$ are connected
with probability

  * •

$p$ if they are in the same cluster, and

  * •

$q$ otherwise.

Figure 2.1 shows an example graph drawn from the stochastic block model. When
$p>q$, the stochastic block model typically generates graphs with a ground-
truth cluster structure which makes it a useful model for evaluating the
performance of graph clustering algorithms. For the interested reader, there
is an extensive literature on several variants of the stochastic block model
[Abb17, KMS16].

###  2.4 Hypergraphs

A hypergraph ${H}=({V},{E},{w})$ is defined by a vertex set ${V}$, a set of
edges ${E}\subseteq 2^{V}$ and a weight function
$w:{E}\rightarrow\mathbb{R}_{\geq 0}$. The difference between a graph and a
hypergraph is that each edge in a graph connects exactly two vertices while
edges in a hypergraph can contain any number of vertices. Note that this means
a graph is a special case of a hypergraph. Figure 2.2 shows an example
hypergraph.

Figure 2.2:  An example of a $3$-uniform hypergraph with $6$ vertices and $4$
edges

Let ${H}=({V},{E},{w})$ be a hypergraph with $n=\left\lvert{V}\right\rvert$
vertices. For any vertex $v\in{V}$, the degree of $v$ is defined by
${d}(v)\triangleq\sum_{e\in{E}}{w}(e)\cdot\boldsymbol{\left[\vphantom{v\in
e}\right.}v\in e\boldsymbol{\left.\vphantom{v\in e}\right]}$, recalling that
$\boldsymbol{\left[\vphantom{X}\right.}X\boldsymbol{\left.\vphantom{X}\right]}=1$
if event $X$ holds and
$\boldsymbol{\left[\vphantom{X}\right.}X\boldsymbol{\left.\vphantom{X}\right]}=0$
otherwise. The rank of edge $e\in{E}$ is defined to be the total number of
vertices in $e$ and is written as $\mathrm{rank}(e)$. A hypergraph is said to
be $\bm{r}$-uniform if every edge $e\in{E}$ has rank $r$.

###  2.5 Asymptotic Notation

When studying the running time of algorithms, we are often interested in how
the running time grows as a function of the size of the algorithm’s input. A
useful tool to this end is asymptotic notation. Suppose we are given two
functions $f,g:\mathbb{R}\rightarrow\mathbb{R}$. Then, we say that

$f(x)=O\\!\left(g(x)\right)$

if there exist constants $c,t\in\mathbb{R}$ such that for all $x\geq t$, it
holds that $f(x)\leq c\cdot g(x)$. For example, if $f(n)$ gives the running
time of some algorithm for an input of size $n$, then
$f(n)=O\\!\left(n\right)$ tells us that for sufficiently large inputs, the
running time of the algorithm is at most linear in $n$. On the other hand,

$f(x)=\Omega\\!\left(g(x)\right)$

tells us that there exist constants $c,t\in\mathbb{R}$ such that for all
$x\geq t$, it holds that $f(x)\geq c\cdot g(x)$. In other words,
$f(x)=\Omega\\!\left(g(x)\right)$ if and only if $g(x)=O\\!\left(f(x)\right)$.
Finally, we can say that

$f(x)=\Theta\\!\left(g(x)\right)$

if $f(x)=O\\!\left(g(x)\right)$ and $f(x)=\Omega\\!\left(g(x)\right)$. When
discussing the running time of algorithms, it is common to use
$\mathrm{poly}(n)$ to represent some polynomial in $n$ and
$\mathrm{polylog}(n)$ for some polynomial in $\log(n)$. Intuitively,
$O\\!\left(\cdot\right)$ gives an upper-bound on some function, and hides a
constant factor. We can take this one step further and use
$\widetilde{O}\\!\left(\cdot\right)$ to hide constants and logarithmic
factors. For example, suppose $f(x)=100\cdot x\log(x)$. Then, we could say
that $f(x)=O\\!\left(x\log(x)\right)$ or
$f(x)=\widetilde{O}\\!\left(x\right)$.

Occasionally, we will use asymptotic notation in order to hide a fixed
constant when we are not discussing the asymptotic behaviour of a function.
For example, $x=\Omega(y)$ means that there exists a universal constant $c$
such that $x\geq cy$. This use of asymptotic notation is common throughout
theoretical computer science [LOGT14, PSZ17].

###  2.6 Clustering Metrics

When evaluating the performance of a clustering algorithm, we would like to
measure the similarity between the ground truth clusters and the clusters
returned by the algorithm. The Rand Index [Ran71], also referred to as the
clustering accuracy, is a common metric used for this purpose.

Suppose we are given a dataset with $n$ data points and $k$ clusters. The
ground truth clusters are given by ${C}_{1},\ldots,{C}_{k}$ and the clusters
returned by our algorithm are ${S}_{1},\ldots,{S}_{k}$. Let
$\sigma_{\mathrm{C}}:[n]\xrightarrow[]{}[k]$ be a function which maps each
data point to its ground truth cluster. That is, if $j\in{C}_{i}$ then
$\sigma_{\mathrm{C}}(j)=i$. Let $\sigma_{\mathrm{S}}:[n]\xrightarrow[]{}[k]$
be the equivalent function for the clusters ${S}_{1},\ldots,{S}_{k}$. Then,
let

$\mathrm{TP}\triangleq\left\lvert\\{(i,j)\in[n]\times[n]:i\neq
j\land\sigma_{\mathrm{C}}(i)=\sigma_{\mathrm{C}}(j)\land\sigma_{\mathrm{S}}(i)=\sigma_{\mathrm{S}}(j)\\}\right\rvert$

be the number of pairs of data points which are in the same ground truth
cluster and the same cluster returned by the algorithm. Similarly, let

$\mathrm{TN}\triangleq\left\lvert\\{(i,j)\in[n]\times[n]:i\neq
j\land\sigma_{\mathrm{C}}(i)\neq\sigma_{\mathrm{C}}(j)\land\sigma_{\mathrm{S}}(i)\neq\sigma_{\mathrm{S}}(j)\\}\right\rvert$

be the number of pairs of data points which the algorithm correctly identifies
as belonging to different clusters. Then, the Rand Index is

$\mathrm{RI}\triangleq\frac{\mathrm{TP}+\mathrm{TN}}{\binom{n}{2}}.$

That is, the Rand Index measures the proportion of pairs of data points which
the algorithm correctly classifies as belonging to the same cluster or
different clusters. While this is a natural definition, notice that even a
baseline algorithm which assigns data points to clusters at random will
achieve a non-zero Rand Index. To correct for this, the Adjusted Rand Index
[GA17] normalises the Rand Index by the expected value for a random
assignment. Further defining

$\mathrm{FP}\triangleq\left\lvert\\{(i,j)\in[n]\times[n]:i\neq
j\land\sigma_{\mathrm{C}}(i)\neq\sigma_{\mathrm{C}}(j)\land\sigma_{\mathrm{S}}(i)=\sigma_{\mathrm{S}}(j)\\}\right\rvert$

and

$\mathrm{FN}\triangleq\left\lvert\\{(i,j)\in[n]\times[n]:i\neq
j\land\sigma_{\mathrm{C}}(i)=\sigma_{\mathrm{C}}(j)\land\sigma_{\mathrm{S}}(i)\neq\sigma_{\mathrm{S}}(j)\\}\right\rvert,$

the Adjusted Rand Index is given by

$\mathrm{ARI}\triangleq\frac{2\left(\mathrm{TP}\cdot\mathrm{TN}-\mathrm{FP}\cdot\mathrm{FN}\right)}{(\mathrm{TP}+\mathrm{FN})(\mathrm{TN}+\mathrm{FN})+(\mathrm{TN}+\mathrm{FP})(\mathrm{TP}+\mathrm{FP})}.$

In contrast with the Rand Index, which gives a value between $0$ and $1$, the
Adjusted Rand Index can give negative values. A random assignment of data
points to clusters will give an expected Adjusted Rand Index of $0$.

## Chapter 3Related Work

The goal of this chapter is to provide a broad overview of the techniques
related to the algorithms developed later in the thesis, and to serve as an
introduction to spectral graph partitioning, local graph clustering, and
spectral hypergraph theory. As well as placing the novel work of this thesis
in the context of the related work in the field, this chapter also introduces
several technical concepts which are built on in the later chapters. The
structure of the chapter is given below.

  * •

Section 3.1 gives an introduction to spectral graph partitioning, and
describes several key points in the development of the field which underpins
this thesis.

  * •

Section 3.2 describes some recently developed techniques for finding clusters
in graphs with specific structures of clusters.

  * •

Section 3.3 introduces local graph clustering and describes two key algorithms
based on the personalised Pagerank and evolving set process, respectively.

  * •

Section 3.4 gives a brief overview of spectral hypergraph theory, with a focus
on the hypergraph Laplacian operator recently developed by Chan et al.
[CLTZ18].

###  3.1 Spectral Graph Partitioning

Spectral graph partitioning is the use of the eigenvectors of graph matrices
to help with finding partitions (or clusters) in graphs. The roots of this
idea stretch back to the 1970s, when Donath and Hoffman [DH72] first proposed
to use the eigenvectors of the adjacency matrix for partitioning, although
they gave no theoretical justification for this choice.

####  3.1.1 Fiedler Vector

In 1973, Fiedler [Fie73] proved a number of results relating the second
smallest eigenvalue of the graph Laplacian to the combinatorial connectivity
of the graph. This gave the first theoretical justification for using
eigenvectors in graph partitioning. Many authors refer to the eigenvector
corresponding to the second smallest eigenvalue of the Laplacian as the
Fiedler vector of the graph. The corresponding eigenvalue is sometimes
referred to as the algebraic connectivity of the graph.

####  3.1.2 Cheeger Inequality

In parallel to this, Cheeger [Che70] studied the connectivity of Riemannian
manifolds, and proved an inequality relating the second smallest eigenvalue of
the Laplacian operator to the connectivity of the manifold. The significance
of Cheeger’s result for graph partitioning was demonstrated several years
later, when Dodziuk [Dod84] and Alon [Alo86] independently proved (slightly
weaker) versions of Cheeger’s inequality in the graph setting. Chung [Chu96]
later tightened the result and proved the following theorem, which is commonly
referred to as the Cheeger inequality in the context of spectral graph theory.

######  Theorem 3.1 (Cheeger Inequality).

Let ${G}$ be a graph and ${\mathbf{N}}_{G}$ be its normalised Laplacian matrix
with eigenvalues $0=\lambda_{1}\leq\lambda_{2}\leq\ldots\leq\lambda_{n}$.
Then,

$\frac{\lambda_{2}}{2}\leq{\Phi}_{G}\leq\sqrt{2\lambda_{2}},$

where ${\Phi}_{G}$ is the conductance of $G$.

The theorem relates the second smallest eigenvalue of the graph Laplacian to
the conductance of the graph. While the theorem itself already provides
significant evidence that the Laplacian spectrum may be helpful when
partitioning graphs, its proof gives even more. The proof of the upper bound
of Theorem 3.1 is constructive: it presents an algorithm which, given a graph
${G}=({V},{E})$, finds a set ${S}\subset{V}$ such that
${\Phi}({S})\leq\sqrt{2\lambda_{2}}$. The algorithm is formally described in
Algorithm 1, and for any given graph the partition returned by this algorithm
is often called the Cheeger cut of the given graph.

1 Compute the second smallest eigenvalue $\lambda_{2}$ of ${\mathbf{N}}_{G}$,
and its eigenvector ${\bm{f}}_{2}$

2 Sort the vertices $v_{1},\ldots,v_{n}\in{V}_{G}$ such that
${\bm{f}}_{2}(v_{1})/\sqrt{{d}(v_{1})}\leq\ldots\leq{\bm{f}}_{2}(v_{n})/\sqrt{{d}(v_{n})}$

3 Let
$i=\operatorname*{arg\,min}_{i\in[n-1]}{\Phi}_{G}(\\{v_{1},\ldots,v_{i}\\})$

Return $\\{v_{1},\ldots,v_{i}\\}$

Algorithm 1 SweepSet$({G})$

It is worth noting that both sides of the Cheeger inequality are tight up to a
constant, as demonstrated in Examples 3.1 and 3.2.

######  Example 3.1 (Tightness of Cheeger Inequality lower bound).

Let ${G}$ be the $d$-dimensional hypercube graph. Then,

$\lambda_{2}=\frac{2}{d}$

and

${\Phi}({G})=\frac{2^{d-1}}{d\cdot
2^{d-1}}=\frac{1}{d}=\frac{\lambda_{2}}{2},$

which demonstrates that the lower bound is tight.

Figure 3.1:  A hypercube graph and the cut with minimum conductance.

######  Example 3.2 (Tightness of Cheeger Inequality upper bound).

Let ${G}$ be the cycle graph on $n$ vertices. Then,

$\lambda_{2}=2-2\cos\left(\frac{2\pi}{n}\right)=O\\!\left(\frac{1}{n^{2}}\right),$

using the fact that $1-\cos(x)=2\sin^{2}(x/2)$ and $\sin(x)\leq x$. Moreover,
we have that

${\Phi}_{G}=\frac{2}{n}=\Omega\\!\left(\sqrt{\lambda_{2}}\right),$

which shows that the Cheeger inequality is tight up to a constant.

Figure 3.2:  A cycle graph and the cut with minimum conductance.

Finally, Kwok et al. [KLL+13] gave the following improved version of the
Cheeger inequality, which shows that $\lambda_{2}$ better approximates the
conductance ${\Phi}_{G}$ when there is a large gap between $\lambda_{2}$ and
$\lambda_{3}$.

######  Theorem 3.2 (Improved Cheeger Inequality).

Let ${G}$ be a graph, and ${\mathbf{N}}_{G}$ be its normalised Laplacian
matrix with eigenvalues
$0=\lambda_{1}\leq\lambda_{2}\leq\ldots\leq\lambda_{n}$. Then, it holds for
any $2\leq k\leq n$ that

${\Phi}_{G}\leq O\\!\left(k\right)\frac{\lambda_{2}}{\sqrt{\lambda_{k}}},$

where ${\Phi}_{G}$ is the conductance of $G$.

####  3.1.3 Higher-order Cheeger Inequality

The Cheeger inequality clearly justifies the use of the second eigenvector of
the graph Laplacian for partitioning a graph into two parts. This raises a
natural question of whether the other eigenvalues give any information for
partitioning the graph into more than two parts. Lee et al. [LOGT14]
considered the $\bm{k}$-way expansion constant of a graph, which generalises
the conductance of a graph to a partitioning with more than two clusters.

######  Definition 3.1 ($k$-way expansion).

Given a graph ${G}$, the $k$-way expansion is defined as

${{\rho}_{G}}(k)\triangleq\min_{\mathrm{partition}~{}{S}_{1},\ldots,{S}_{k}}\max_{i\in[k]}{\Phi}_{G}({S}_{i}),$

where the minimum is taken over all sets
${S}_{1},\ldots,{S}_{k}\subset{V}_{G}$ where ${S}_{i}\cap{S}_{j}=\emptyset$
for all $i\neq j$ and $\bigcup_{i=1}^{k}{S}_{i}={V}_{G}$.

It is clear that ${{\rho}_{G}}(2)={\Phi}_{G}$, and so this generalises the
definition of graph conductance. Lee et al. [LOGT14] proved the following
theorem, which relates the $k$-way expansion of a graph to the $k$-th smallest
eigenvalue of the normalised Laplacian.

######  Theorem 3.3 (Higher-order Cheeger Inequality).

Let ${G}=({V},{E})$ be a graph, and ${\mathbf{N}}_{G}$ be its normalised
Laplacian matrix with eigenvalues
$0=\lambda_{1}\leq\lambda_{2}\leq\ldots\leq\lambda_{n}$. Then,

$\frac{\lambda_{k}}{2}\leq{{\rho}_{G}}(k)\leq
O\\!\left(k^{3}\right)\sqrt{\lambda_{k}},$

where ${{\rho}_{G}}(k)$ is the $k$-way expansion constant of ${G}$.

Once again, the proof of this theorem is constructive, and gives an algorithm
for finding clusters ${S}_{1},\ldots,{S}_{k}$ satisfying the inequalities. The
dependence on $k$ in the upper bound of Theorem 3.3 is needed, but it is not
known if the inequality is tight [LOGT14].

####  3.1.4 Spectral Clustering

The spectral clustering algorithm was proposed over a decade before the
higher-order Cheeger inequality [NJW01], and is widely used in practice due to
its simplicity and empirical effectiveness. There are several variants of this
algorithm since it is possible to use the adjacency matrix, Laplacian matrix,
or normalised Laplacian matrix for constructing the spectral embedding [vL07].
However, they are all composed of the same three steps:

  1. 1.

Compute $k$ eigenvectors of some graph matrix;

  2. 2.

Embed the vertices of the graph into $\mathbb{R}^{k}$ according to the values
of the eigenvectors;

  3. 3.

Apply a simple clustering algorithm, such as $k$-means, to obtain the final
clusters.

See Algorithm 2 for the formal description of spectral clustering.

1 Construct the normalised graph Laplacian matrix ${\mathbf{N}}_{G}$

2 Compute eigenvectors ${\bm{f}}_{1},\ldots,{\bm{f}}_{k}$ of
${\mathbf{N}}_{G}$ corresponding to the $k$ smallest eigenvalues

3 Embed each $v\in{V}_{G}$ to the point
$({\bm{f}}_{1}(v),\ldots,{\bm{f}}_{k}(v))^{\intercal}$

Apply $k$-means to the embedded vertices; partition ${V}_{G}$ based on the
output

Algorithm 2 SpectralCluster$({G},k)$

Although spectral clustering has been used in practice for several decades,
the theoretical justification for its good performance has seen some recent
progress [PSZ17] and deserves further study. There are two technical
approaches which are common when analysing spectral clustering. The first is
to see that the algorithm solves a relaxation of a natural optimisation
problem. For more details on this perspective, the reader can refer to the
excellent tutorial of Von Luxburg [vL07]. The second comes from considering
the structure of clusters in the eigenspace of the graph matrices. Ng et al.
[NJW01] introduced this idea with the following observations, which are
illustrated in Figure 3.3.

  1. 1.

If the clusters in the input graph $G$ are disconnected, then the normalised
Laplacian matrix ${\mathbf{N}}_{G}$ is block diagonal. Therefore, the first
$k$ eigenvectors of ${\mathbf{N}}_{G}$ are the indicator vectors of the
connected components.

  2. 2.

If the clusters are then connected by a small number of edges, then the
Laplacian matrix doesn’t change much, and accordingly the eigenvalues and
eigenvectors of the Laplacian do not change too much.

  3. 3.

As such, if a graph possesses a clear cluster structure, then the clusters are
well separated in the spectral embedding.

$\xrightarrow{}$$\begin{bmatrix}{\mathbf{B}}_{1}&{\mathbf{0}}&{\mathbf{0}}\\\
{\mathbf{0}}&{\mathbf{B}}_{2}&{\mathbf{0}}\\\
{\mathbf{0}}&{\mathbf{0}}&{\mathbf{B}}_{3}\end{bmatrix}$$\xrightarrow{}$Graph
${G}$Normalised Laplacian ${\mathbf{N}}$Spectral
Embedding$\xrightarrow{}$$\begin{bmatrix}{\mathbf{B}}_{1}&{\mathbf{C}}_{12}&{\mathbf{C}}_{13}\\\
{\mathbf{C}}_{12}^{\intercal}&{\mathbf{B}}_{2}&{\mathbf{C}}_{23}\\\
{\mathbf{C}}_{13}^{\intercal}&{\mathbf{C}}_{23}^{\intercal}&{\mathbf{B}}_{3}\end{bmatrix}$$\xrightarrow{}$Graph
${G}$Normalised Laplacian ${\mathbf{N}}$Spectral Embedding Figure 3.3:  An
illustration of the intuition behind spectral clustering. If the clusters are
disconnected, then the Laplacian is block diagonal and the spectral embedding
perfectly separates the clusters. If a small number of edges are added between
the clusters, then the embedding doesn’t change ‘too much’.

Peng et al. [PSZ17] built on this intuition and proved that, not only are the
clusters well separated in the spectral embedding, but the output of the
$k$-means algorithm is guaranteed to correctly cluster most of the vertices.
To quantify the ‘clusterability’ of a given graph $G$, they introduced the
parameter $\Upsilon(k)$ defined as follows:

######  Definition 3.2.

For a graph ${G}$, let $\lambda_{1}\leq\lambda_{2}\leq\ldots\leq\lambda_{n}$
be the eigenvalues of the normalised Laplacian matrix ${\mathbf{N}}_{G}$.
Then,

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

where ${\rho}(k)$ is the $k$-way expansion constant.

To understand the motivation behind this definition, suppose that a graph
${G}=({V},{E})$ contains _exactly_ $k$ clusters with low conductance. That is,

  1. 1.

there is a partition of ${V}$ into $k$ sets ${S}_{1},\ldots,{S}_{k}$ such that
$\max_{i\in[k]}{\Phi}({S}_{i})$ is low, and

  2. 2.

for _any_ partition of ${V}$ into $k+1$ sets ${S}_{1},\ldots,{S}_{k+1}$, there
is some $i\in[k+1]$ such that ${\Phi}({S}_{i})$ is high.

Then, by the definition of ${\rho}(k)$, the denominator of $\Upsilon(k)$ is
low, and by the higher-order Cheeger inequality (Theorem 3.3), the numerator
is high. Thus, a large value of $\Upsilon(k)$ indicates that there are exactly
$k$ low-conductance clusters in the graph. The definition of $\Upsilon(k)$
also closely resembles the widely-used eigen-gap heuristic for spectral
clustering [NJW01, vL07], which suggests that spectral clustering works when
the value of $\left\lvert\lambda_{k+1}-\lambda_{k}\right\rvert$ is much larger
than $\left\lvert\lambda_{k}-\lambda_{k-1}\right\rvert$.

Peng et al. [PSZ17] prove that for graphs with a high value of $\Upsilon(k)$,
the eigenvectors of the Laplacian are close to the indicator vectors of the
optimal clusters. Let ${S}_{1},\ldots,{S}_{k}\subset{V}$ be the optimal
clusters which achieve the $k$-way expansion ${\rho}(k)$, then the normalised
indicator vector of each cluster ${S}_{i}$ is defined as

$\bar{{\bm{g}}}_{i}=\frac{{\mathbf{D}}^{\frac{1}{2}}{\bm{\chi}}_{{S}_{i}}}{\left\|{\mathbf{D}}^{\frac{1}{2}}{\bm{\chi}}_{{S}_{i}}\right\|}.$

Their result is given in the following theorem.

######  Theorem 3.4 ([PSZ17], Theorem 1.1).

Let ${G}$ be a graph with $\Upsilon(k)=\Omega\\!\left(k^{2}\right)$, and let
${\bm{f}}_{1},\ldots,{\bm{f}}_{n}$ be the eigenvectors of ${\mathbf{N}}_{G}$
corresponding to eigenvalues $\lambda_{1}\leq\ldots\leq\lambda_{n}$. Then,

  1. 1.

for every $\bar{{\bm{g}}}_{i}$, there is a linear combination of
$\\{{\bm{f}}_{i}\\}_{i=1}^{k}$ called $\widehat{{\bm{f}}}_{i}$ such that
$\left\|\bar{{\bm{g}}}_{i}-\widehat{{\bm{f}}}_{i}\right\|\leq 1/\Upsilon(k)$;

  2. 2.

for every ${\bm{f}}_{i}$, there is a linear combination of
$\\{\bar{{\bm{g}}}_{i}\\}_{i=1}^{k}$, called $\widehat{{\bm{g}}}_{i}$, such
that $\left\|{\bm{f}}_{i}-\widehat{{\bm{g}}}_{i}\right\|^{2}\leq
1.1k/\Upsilon(k)$.

Peng et al. [PSZ17] used this to prove an upper bound on the number of
vertices misclassified by the $k$-means clustering step of the spectral
clustering algorithm.

######  Theorem 3.5 ([PSZ17], Theorem 1.2).

Let ${G}$ be a graph with $\Upsilon(k)=\Omega\\!\left(k^{3}\right)$. Let
${A}_{1},\ldots,{A}_{k}$ be the clusters found by spectral clustering, and let
the optimal correspondent of ${A}_{i}$ be ${S}_{i}$. Then, it holds for any
$i\in[k]$ that

$\frac{\mathrm{vol}({A}_{i}\triangle{S}_{i})}{\mathrm{vol}({S}_{i})}=O\\!\left(k^{3}/\Upsilon(k)\right).$

Kolev and Melhorn [KM16] and Mizutani [Miz21] developed similar results under
the weaker assumptions of $\Upsilon(k)=\Omega(k^{2})$ and
$\Upsilon(k)=\Omega(k)$ respectively, although their results are not directly
comparable since they use a slightly different definition of the gap
$\Upsilon(k)$.

###  3.2 Clustering Structured Graphs

Spectral clustering gives an excellent starting point for the subject of graph
partitioning; however, the classical analysis is usually based only on the
assumption that the clusters are sparsely connected to each other and does not
take into account the high-level structure of clusters. As demonstrated in
Chapter 1, graphs created from real-world data often exhibit a high-level
structure, and this section describes techniques for learning clusters in such
graphs.

####  3.2.1 Partitioning Almost-Bipartite Graphs

Let us start by considering the case of graphs exhibiting heterophily. That
is, graphs in which vertices have a tendency to share connections with those
in a _different_ cluster to their own.111For completeness, the opposite of
heterophily is homophily, in which vertices are more likely to share edges
with other vertices in the same cluster. An example of such a graph is the
inter-state dispute graph introduced in Chapter 1. More generally, graphs in
which edges represent ‘negative’ relationships tend to exhibit heterophily.

A bipartite graph is a ‘perfect’ example of a two-cluster graph with
heterophily. Of course, it is not difficult to separate a bipartite graph into
its two clusters, but what if the graph is only _almost_ bipartite? To answer
this, Bauer and Jost [BJ13] and Trevisan [Tre12] introduced the bipartiteness
of two sets ${L},{R}\subset{V}_{G}$, which measures how close the sets ${L}$
and ${R}$ are to forming a bipartite connected component.

######  Definition 3.3 (Bipartiteness).

Given a graph ${G}=({V},{E})$ and two clusters ${L},{R}\subset{V}$, the
bipartiteness of ${L}$ and ${R}$ is

${\beta}({L},{R})\triangleq 1-\frac{2{w}({L},{R})}{\mathrm{vol}({L}\cup{R})}.$

The bipartiteness of the graph ${G}$ is given by

${\beta}_{G}\triangleq\min_{\begin{subarray}{c}{L},{R}\subset{V}_{G}\\\
{L}\cap{R}=\emptyset\end{subarray}}{\beta}({L},{R}).$

Notice that ${\beta}({L},{R})=0$ if ${L}$ and ${R}$ form a bipartite and
connected component of ${G}$. Given a graph ${G}$, let
$0=\lambda_{1}\leq\lambda_{2}\leq\ldots\leq\lambda_{n}\leq 2$ be the
eigenvalues of the normalised Laplacian ${\mathbf{N}}_{G}$. It is a classical
result in spectral graph theory that $\lambda_{n}=2$ if and only if
${\beta}_{G}=0$, and so a natural question is whether there is an analogue of
the Cheeger inequality which connects the bipartiteness of a graph with the
largest eigenvalue $\lambda_{n}$. Bauer and Jost [BJ13] and Trevisan [Tre12]
independently showed that this is indeed the case with the following theorem.

######  Theorem 3.6.

Given a graph ${G}$, let $\lambda_{1}\leq\lambda_{2}\leq\ldots\leq\lambda_{n}$
be the eigenvalues of the normalised Laplacian ${\mathbf{N}}_{G}$. Then,

$\frac{2-\lambda_{n}}{2}\leq{\beta}_{G}\leq\sqrt{2(2-\lambda_{n})},$

where ${\beta}_{G}$ is the bipartiteness of the graph.

Trevisan used this result to develop a novel approximation algorithm for the
MAX-CUT problem. Soto [Sot15] improved Trevisan’s analysis and showed that the
algorithm achieves an approximation ratio of $0.614247$. Liu [Liu15]
generalised Theorem 3.6 and proved a higher-order version of this inequality
which links the top eigenvalues of a graph Laplacian to the bipartiteness of
multiple clusters in the graph.

The problem of learning the clusters in graphs exhibiting heterophily has also
been studied from a supervised and semi-supervised learning perspective, such
as in [MYZ+11, PWC+19, ZYZ+20]. These techniques are not covered in detail
here since the focus of this thesis is on algorithms for unsupervised
learning.

####  3.2.2 Learning Clusters from Edge Directions

In the preceding sections, we considered algorithms for learning clusters
which are defined by sparse (or dense) connections. In this section, we
consider directed graphs in which the clusters are defined by the _directions_
of their connecting edges.

Cucuringu et al. [CLSZ20] studied this problem and introduced the so-called
cut imbalance between two clusters ${S}_{1},{S}_{2}\subset{V}$, which measures
the imbalance of edge directions between the clusters. They proposed to use
the Hermitian adjacency matrix of a directed graph to find clusters with a
large cut imbalance. The Hermitian adjacency matrix of a directed graph ${G}$
is the matrix ${\mathbf{A}}_{h}\in\mathbb{C}^{n\times n}$ where
${\mathbf{A}}_{h}(u,v)=\overline{{\mathbf{A}}_{h}(v,u)}=\mathit{i}$ if ${G}$
contains an edge from $u$ to $v$ and
${\mathbf{A}}_{h}(u,v)={\mathbf{A}}_{h}(v,u)=0$ otherwise. They develop a
spectral clustering algorithm based on the complex-valued eigenvectors of
${\mathbf{A}}_{h}$. For graphs generated from a directed stochastic block
model, their algorithm provably recovers the ground truth clusters when the
cut imbalance between clusters is sufficiently large.

Laenen and Sun [LS20] further studied spectral clustering with the Hermitian
adjacency matrix, and proved that if the clusters form a directed path
structure, then they can be recovered using a _single_ complex-valued
eigenvector. In Chapter 5, we see that this can be generalised to undirected
graphs and arbitrary structures of clusters. Moreover, we prove that when the
clusters have a clearly defined structure, spectral clustering with fewer than
$k$ eigenvectors performs better than spectral clustering with $k$
eigenvectors.

###  3.3 Local Graph Clustering

Let us now turn our attention to the problem of local graph clustering, which
was first introduced by Spielman and Teng [ST13]. In the classical local
clustering problem, we are given as input a large graph ${G}=({V},{E})$ and
some starting vertex $v\in{V}$. Our aim is to find a low-conductance cluster
${S}\subset{V}$ which contains the vertex $v$. Moreover, the algorithm should
have running time which depends on $\mathrm{vol}({S})$ and is independent of
$\mathrm{vol}({V})$. This sublinear running time makes local clustering a
crucially important technique for studying massive datasets occurring in real-
world applications. This section introduces two techniques which form the
basis for several local clustering algorithms.

####  3.3.1 Pagerank Based Algorithm

The first key local clustering technique that we consider is known as the
personalised Pagerank. With its roots in the well-known Pagerank algorithm for
ranking web pages [PBMW99], personalised Pagerank can be used to find vertices
in a graph close to some starting vertex. This technique has proved useful for
many graph learning applications [ACL06, ACL07, AHN19, YBLG17, TMIY20].

###### Random walks.

Before coming to the personalised Pagerank, we first discuss random walks on
graphs. In a graph ${G}=({V},{E})$, a random walk is a sequence of vertices
$x_{1},x_{2},\ldots,x_{n}\in{V}$ where each $x_{t}$ is chosen uniformly at
random from the neighbours of $x_{t-1}$. See Figure 3.4 for an illustration.

$\xrightarrow{}$$\begin{bmatrix}{\mathbf{B}}_{1}&{\mathbf{0}}&{\mathbf{0}}\\\
{\mathbf{0}}&{\mathbf{B}}_{2}&{\mathbf{0}}\\\
{\mathbf{0}}&{\mathbf{0}}&{\mathbf{B}}_{3}\end{bmatrix}$$\xrightarrow{}$Graph
${G}$Normalised Laplacian ${\mathbf{N}}$Spectral
Embedding$\xrightarrow{}$$\begin{bmatrix}{\mathbf{B}}_{1}&{\mathbf{C}}_{12}&{\mathbf{C}}_{13}\\\
{\mathbf{C}}_{12}^{\intercal}&{\mathbf{B}}_{2}&{\mathbf{C}}_{23}\\\
{\mathbf{C}}_{13}^{\intercal}&{\mathbf{C}}_{23}^{\intercal}&{\mathbf{B}}_{3}\end{bmatrix}$$\xrightarrow{}$Graph
${G}$Normalised Laplacian ${\mathbf{N}}$Spectral
Embedding$\rightarrow$$v_{1}$$v_{3}$$v_{5}$$v_{4}$$v_{2}$$\rightarrow$$x_{1}=v_{1}$$x_{2}=v_{4}$$x_{3}=v_{5}$
Figure 3.4:  An example random walk starting with $x_{1}=v_{1}$. At each time
step, the current position is shown by the red vertex, and the next vertex of
the walk is chosen randomly from the neighbours highlighted in blue.

We can represent this process algebraically by defining the random walk matrix
to be

${\mathbf{X}}\triangleq{\mathbf{A}}{\mathbf{D}}^{-1}.$

Let ${\bm{p}}_{t}\in\mathbb{R}^{n}$ be the probability distribution at time
$t$, where ${\bm{p}}_{t}(v)$ is the probability that $x_{t}=v$. Define
${\bm{p}}_{0}\in\mathbb{R}^{n}$ to be some starting distribution such that
$\sum_{i=1}^{n}{\bm{p}}(i)=1$. It is common to use
${\bm{p}}_{0}={\bm{\chi}}_{v}$ for some vertex $v\in{V}$. Then, we can write
${\bm{p}}_{t+1}$ as

${\bm{p}}_{t+1}={\mathbf{X}}{\bm{p}}_{t}.$

In order to ensure that the random walk converges, we instead use the lazy
random walk defined by the matrix

${\mathbf{W}}\triangleq\frac{1}{2}\left({\mathbf{I}}+{\mathbf{X}}\right).$

This corresponds to a random walk process in which with probability $1/2$, the
next vertex $x_{t+1}$ is equal to $x_{t}$, and with probability $1/2$ the next
vertex $x_{t+1}$ is chosen uniformly at random from the neighbours of $x_{t}$.
If the graph is connected, this random walk process always converges to the
stationary distribution denoted by ${\bm{\pi}}$. 222Notice that this is not
guaranteed when using ${\mathbf{X}}$. For example, if ${G}$ is bipartite such
that every edge connects ${L}\subset{V}$ to ${R}\subset{V}$, then $x_{t}$
always alternates between ${L}$ and ${R}$. In particular, by setting

${\bm{\pi}}(v)=\frac{{d}(v)}{\mathrm{vol}({V})}$

for every $v\in{V}$, it is easy to verify that

${\mathbf{W}}{\bm{\pi}}={\bm{\pi}}.$

Many algorithms for local graph clustering are based on the fact that a random
walk starting inside some low conductance cluster is likely to stay inside the
cluster. We can study this through the escape probability, which is the
probability that a lazy random walk starting at $v$ leaves a set ${A}$ within
the first $T$ steps and is defined as

$\mathrm{esc}(v,T,{A})\triangleq\mathbb{P}\left[\bigcup_{j=0}^{T}x_{j}\not\in{A}\middle|x_{0}=v\right].$

Spielman and Teng [ST13] gave the following result which connects the escape
probability to the conductance of the set ${S}$.

######  Proposition 3.1 ([ST13], Proposition 2.5).

Let $G=(V,E)$ be a graph, and $A\subset V$. Then, there is a set
${A}_{T}\subseteq{A}$ with
$\mathrm{vol}({A}_{T})\geq\frac{1}{2}\mathrm{vol}({A})$, such that it holds
for any $x\in{A}_{T}$ that

$\mathrm{esc}(x,T,{A})\leq T{\Phi}({A}).$

###### Personalised Pagerank.

In the local clustering problem, we are interested in finding a cluster in the
graph ${G}$ which is close to some starting vertex $v$. In order to find such
a cluster, let us consider a new random walk process called the teleporting
random walk. We first define some starting distribution
${\bm{s}}\in\mathbb{R}^{n}$, and a teleport probability $\alpha$. Then, at
time $t$,

  1. 1.

with probability $\alpha$, the next vertex $x_{t+1}$ is chosen according to
the distribution ${\bm{s}}$;

  2. 2.

with probability $1-\alpha$, the vertex $x_{t+1}$ is chosen according to the
lazy random walk from $x_{t}$.

If we take ${\bm{s}}$ to be the indicator vector of some vertex $v$, then at
each step the random walk ‘teleports’ to $v$ with probability $\alpha$. We can
represent this walk with the following update rule:

${\bm{p}}_{t+1}=\alpha{\bm{s}}+\left(1-\alpha\right){\mathbf{W}}{\bm{p}}_{t}.$

The personalised Pagerank vector $\mathrm{ppr}(\alpha,{\bm{s}})$ is the
stationary distribution of this random walk for some specified $\alpha$ and
${\bm{s}}$. That is, one can view
$\mathrm{ppr}:\mathbb{R}\times\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ as a
function such that, for any $\alpha$ and ${\bm{s}}$,
$\mathrm{ppr}(\alpha,{\bm{s}})$ is the unique solution to the equation

$\mathrm{ppr}(\alpha,{\bm{s}})=\alpha{\bm{s}}+(1-\alpha){\mathbf{W}}\mathrm{ppr}(\alpha,{\bm{s}}).$

Andersen et al. [ACL06] showed that the personalised Pagerank vector can also
be written as

$\mathrm{ppr}(\alpha,{\bm{s}})=\alpha\sum_{t=0}^{\infty}(1-\alpha)^{t}{\mathbf{W}}^{t}{\bm{s}}.$

Therefore, we can also study $\mathrm{ppr}(\alpha,{\bm{s}})$ through the
following random process: pick some integer $t\in\mathbb{Z}_{\geq 0}$ with
probability $\alpha(1-\alpha)^{t}$, and perform a $t$-step lazy random walk,
where the starting vertex of the random walk is picked according to
${\bm{s}}$. Then, $\mathrm{ppr}(\alpha,{\bm{s}})$ describes the probability of
reaching each vertex in this process. Intuitively, we would expect the
vertices which are ‘close’ to the vertices in the starting distribution
${\bm{s}}$ to have a higher value in the $\mathrm{ppr}(\alpha,{\bm{s}})$
vector.

###### Approximate personalised Pagerank.

Our goal is to use the personalised Pagerank vector as the basis of local
graph clustering algorithms. However, computing a personalised Pagerank vector
$\mathrm{ppr}(\alpha,{\bm{s}})$ exactly is equivalent to computing the
stationary distribution of a Markov chain on the vertex set ${V}$, which has a
time complexity of $\Omega\\!\left(n\right)$. This is too slow for any local
clustering algorithm, whose running time is independent of the size of the
input graph.

The good news is that, since the probability mass of a personalised Pagerank
vector is concentrated around some starting vertex, it is possible to compute
a good approximation of the Pagerank vector in a local way. Andersen et al.
[ACL06] introduced the approximate Pagerank vector for this purpose.

######  Definition 3.4 (Approximate Pagerank).

A vector ${\bm{p}}=\mathrm{apr}(\alpha,{\bm{s}},{\bm{r}})$ is called an
approximate Pagerank vector if
${\bm{p}}+\mathrm{ppr}(\alpha,{\bm{r}})=\mathrm{ppr}(\alpha,{\bm{s}})$. The
vector ${\bm{r}}$ is called the residual vector.

###### The Lovász-Simonovits curve.

The Lovász-Simonovits curve was originally introduced by Lovász and Simonovits
[LS90] to reason about the mixing rate of Markov chains, and has been used
extensively in the analysis of local clustering algorithms based on the
personalised Pagerank [ACL06, ALM13]. For any vector
${\bm{p}}\in\mathbb{R}_{\geq 0}^{n}$, order the vertices such that

$\frac{{\bm{p}}(v_{1})}{{d}(v_{1})}\geq\frac{{\bm{p}}(v_{2})}{{d}(v_{2})}\geq\ldots\geq\frac{{\bm{p}}(v_{n})}{{d}(v_{n})},$

and define the sweep sets of ${\bm{p}}$ to be
${S}_{j}^{{\bm{p}}}=\\{v_{1},\ldots,v_{j}\\}$ for $1\leq j\leq n$. Then, the
Lovász-Simonovits curve, denoted by ${\bm{p}}[x]$ for
$x\in[0,\mathrm{vol}({V})]$, is defined by the points

${\bm{p}}[\mathrm{vol}({S}_{j}^{{\bm{p}}})]\triangleq{\bm{p}}({S}_{j}^{{\bm{p}}}),$

and is linear between those points for consecutive $j$. Lovász and Simonovits
also showed that

${\bm{p}}\\!\left[x\right]=\max_{\begin{subarray}{c}{\bm{w}}\in[0,1]^{n}\\\
\sum_{u\in{V}}{\bm{w}}(u){d}(u)=x\end{subarray}}\sum_{u\in{V}}{\bm{w}}(u){\bm{p}}(u),$
(3.1)

which leads immediately to the following proposition.

######  Proposition 3.2.

For any ${\bm{p}}\in\mathbb{R}_{\geq 0}^{n}$ and any ${S}\subseteq{V}$, it
holds that ${\bm{p}}({S})\leq{\bm{p}}\\!\left[\mathrm{vol}({S})\right].$

###### Proof.

We have that ${\bm{p}}({S})=\sum_{u\in{V}}{\bm{\chi}}_{{S}}(u){\bm{p}}(u).$
Hence, the statement follows by (3.1). ∎

It is worth taking time to understand this definition and gain some of the
intuition behind the Lovász-Simonovits curve. First of all, we have that
${\bm{p}}[0]=0$ and ${\bm{p}}[\mathrm{vol}({V})]=1$. Then, for some
$x\in[0,\mathrm{vol}(V)]$, the value of ${\bm{p}}[x]$ is the maximum
probability mass in ${\bm{p}}$ on any vertex set with volume $x$. Notice that
for the stationary distribution ${\bm{\pi}}$, we have

${\bm{\pi}}[x]=\frac{x}{\mathrm{vol}({V})}.$

Andersen et al. [ACL06] used the Lovász-Simonovits curve to prove that the
sweep sets of an approximate Pagerank vector can be used to find a low-
conductance cluster close to some starting vertex. Their proof is built around
the following two results.

  1. 1.

If there is a set ${S}\subset{V}$ with low conductance, then for most of the
vertices $v\in{S}$, the Lovász-Simonovits curve of the approximate Pagerank
vector ${\bm{p}}=\mathrm{apr}(\alpha,{\bm{\chi}}_{v},{\bm{r}})$ deviates from
that of the stationary distribution. That is, ${\bm{p}}[x]-{\bm{\pi}}[x]$ is
large for some $x\in[0,\mathrm{vol}({V})]$. This corresponds to our intuition
that a random walk is likely to stay inside a cluster with low conductance.

  2. 2.

If ${\bm{p}}[x]-{\bm{\pi}}[x]$ is large for some $x\in[0,\mathrm{vol}({V})]$,
then there is a sweep set of ${\bm{p}}$ with low conductance.

These two results lead to the following simple local graph clustering
algorithm, which takes as input a graph ${G}$, a seed vertex $v\in{V}$, and a
parameter $\alpha$.

  1. 1.

Compute vectors ${\bm{p}}$ and ${\bm{r}}$ satisfying
${\bm{p}}=\mathrm{apr}(\alpha,{\bm{\chi}}_{v},{\bm{r}})$.

  2. 2.

Compute
$j=\operatorname*{arg\,min}_{j\in[\left\lvert\mathrm{supp}(p)\right\rvert]}{\Phi}({S}_{j}^{{\bm{p}}})$
and return ${S}_{j}^{{\bm{p}}}$.

Andersen et al. [ACL06] also provided an algorithm for computing the
approximate Pagerank locally, which is used in the first step of the
clustering algorithm.

####  3.3.2 Evolving Set Process

The evolving set process (ESP) is another key technique for designing local
clustering algorithms [AC09, AOGPT16]. Given a graph ${G}=({V},{E})$, the ESP
is a Markov chain whose states are sets of vertices ${S}_{i}\subseteq{V}$.
Given a state ${S}_{i}$, the next state ${S}_{i+1}$ is determined by the
following process: (1) choose $t\in[0,1]$ uniformly at random; (2) let
${S}_{i+1}=\\{v\in{V}|{\bm{\chi}}_{{S}_{i}}^{\intercal}{\mathbf{W}}{\bm{\chi}}_{v}\geq
t\\}$, where ${\bm{\chi}}_{{S}}$ is the indicator vector defined in Section
2.3. To understand this update process, notice that
${\bm{\chi}}_{{S}_{i}}^{\intercal}{\mathbf{W}}{\bm{\chi}}_{v}$ is the
probability that a one-step random walk starting at $v$ ends inside ${S}_{i}$.
Since the ESP is based on a _lazy_ random walk, we have
${S}_{i}\subseteq{S}_{i+1}$ if $t\leq 1/2$, and ${S}_{i+1}\subseteq{S}_{i}$
otherwise.

If the graph ${G}$ is connected, then the ESP has two absorbing states:
$\emptyset$ and ${V}$. Given that the transition kernel of the evolving set
process is given by
$\mathbf{K}({S},{S}^{\prime})=\mathbb{P}[{S}_{i+1}={S}^{\prime}|{S}_{i}={S}]$,
the volume-biased ESP is defined by the transition kernel

$\mathbf{\widehat{K}}({S},{S}^{\prime})=\frac{\mathrm{vol}({S}^{\prime})}{\mathrm{vol}({S})}\mathbf{K}({S},{S}^{\prime}),$

and is guaranteed to absorb in the state ${V}$ rather than $\emptyset$.
Andersen and Peres [AP09] gave a local algorithm for undirected graph
clustering using the volume-biased ESP. As part of this, they described an
algorithm, $\textsc{GenerateSample}({G},u,T)$, which samples ${S}_{T}$ from
the volume-biased ESP with ${S}_{0}=\\{u\\}$ and has running time proportional
to the volume of the output set.

Andersen and Peres [AP09] gave two further results which are useful in the
analysis of the evolving set process. The first tells us that an evolving set
process running for sufficiently many steps is very likely to have at least
one state with low conductance.333Note that they use a slightly different
definition of conductance:
${\Phi}({S})={w}({S},\overline{{S}})/\mathrm{vol}({S})$. The difference in the
denominator does not impact our use of this theorem, since we guarantee that
the volume of ${S}$ is small.

######  Proposition 3.3 ([AP09], Corollary 1).

Let ${S}_{0},{S}_{1},\ldots,{S}_{T}$ be sets drawn from the volume-biased
evolving set process beginning at ${S}_{0}$. Then, it holds for any constant
$c\geq 0$ that

$\mathbb{P}\left[\min_{j\leq
T}{\Phi}({S}_{j})\leq\sqrt{\frac{4c}{T}\ln(\mathrm{vol}({V}))}\right]\geq
1-\frac{1}{c}.$

Secondly, they showed that the overlap between the sets generated by the
evolving set process and some target cluster ${A}$ is closely linked to the
escape probability of the lazy random walk.

######  Proposition 3.4 ([AP09], Lemma 2).

For any vertex $x$, let ${S}_{0},{S}_{1},\ldots,{S}_{T}$ be sampled from a
volume-biased ESP starting from ${S}_{0}=\\{x\\}$. Then, it holds for any set
${A}\subseteq{V}$ and $\lambda>0$ that

$\mathbb{P}\left[\max_{t\leq
T}\frac{\mathrm{vol}({S}_{t}\setminus{A})}{\mathrm{vol}({S}_{t})}>\lambda\mathrm{esc}(x,T,{A})\right]<\frac{1}{\lambda}.$

####  3.3.3 Other Local Clustering Techniques

Chung [Chu09] and Kloster and Gleich [KG14] developed local clustering
algorithms based on the heat-kernel diffusion process. Orecchia and Allen-Zhu
[OA14] developed an algorithm based on network flows which can be used to find
a low-conductance cluster close to some seed set. Li and Peng [LP13] developed
a local algorithm for finding densely connected clusters in graphs, based on
truncated random walks.

###  3.4 Spectral Hypergraph Theory

Given the usefulness of hypergraphs for modelling higher-order relationships
between data and the effectiveness of spectral graph theory for learning the
structure of graphs, it is natural to look for an extension of these
techniques to hypergraphs. Several authors have proposed different ways to
generalise the Laplacian matrix from graphs to hypergraphs [Chu93, HSJR13,
JM19, LM18]. This thesis focuses on the Laplacian operator proposed by Chan et
al. [CLTZ18] which has been applied for learning clusters in hypergraphs
[TMIY20].

Given some hypergraph ${H}$ on $n$ vertices, Chan et al. [CLTZ18] defined a
new _non-linear_ operator
${\mathbf{L}}_{H}:\mathbb{R}^{n}\rightarrow\mathbb{R}^{n}$ which describes a
heat diffusion process on hypergraphs: for any vector
${\bm{f}}_{t}\in\mathbb{R}^{n}$, the diffusion proceeds according to the
equation

$\frac{\mathrm{d}{\bm{f}}_{t}}{\mathrm{d}t}=-{\mathbf{L}}_{H}{\bm{f}}_{t}.$

Among many properties of ${\mathbf{L}}_{H}$, they proved that for any vector
${\bm{f}}$, the value of ${\mathbf{L}}_{H}{\bm{f}}$ can be computed in
polynomial time. Moreover, the heat diffusion process is guaranteed to
converge to an eigenvector of ${\mathbf{L}}_{H}$, and the corresponding
eigenvalue satisfies an analogue of the Cheeger inequality for the hypergraph
conductance.

######  Definition 3.5 (Hypergraph conductance).

Given a hypergraph ${H}=({V},{E},{w})$ and any set ${S}\subset{V}$, the
conductance of ${S}$ is

${\Phi}_{H}({S})=\frac{{w}({S},\overline{{S}})}{\mathrm{vol}({S})},$

where
${w}({S},\overline{{S}})=\sum_{e\in{E}}{w}(e)\cdot\boldsymbol{\left[\vphantom{e\cap{S}\neq\emptyset\land
e\cap\overline{{S}}\neq\emptyset}\right.}e\cap{S}\neq\emptyset\land
e\cap\overline{{S}}\neq\emptyset\boldsymbol{\left.\vphantom{e\cap{S}\neq\emptyset\land
e\cap\overline{{S}}\neq\emptyset}\right]}$ and
$\mathrm{vol}({S})=\sum_{v\in{S}}{d}(v)$.

######  Theorem 3.7 ([CLTZ18], Theorem 3.3).

For any hypergraph ${H}$, let $\lambda_{2}$ be the second smallest eigenvalue
of ${\mathbf{L}}_{H}$. Then,

$\frac{\lambda_{2}}{2}\leq{\Phi}_{H}\leq 2\sqrt{\lambda_{2}},$

where ${\Phi}_{H}$ is the hypergraph conductance.

Chan and Liang [CL20] generalised this result by considering a slightly
different diffusion process, and Chan et al. [CTWZ19] generalised the
hypergraph Laplacian operator to directed hypergraphs. Takai et al. [TMIY20]
showed that the hypergraph Laplacian operator can be used to compute the
personalised Pagerank vector in a hypergraph. They further used this to
develop a local clustering algorithm for hypergraphs. Finally, Yoshida [Yos19]
described a Laplacian operator for hypergraphs with _submodular cut functions_
, and posed the question of whether there is a hypergraph operator which
satisfies an inequality like Trevisan’s bipartiteness inequality given in
Theorem 3.6. We give an affirmative answer to Yoshida’s question in Chapter 7
and demonstrate that the new hypergraph signless Laplacian operator can be
used to find densely connected clusters in hypergraphs.

## Chapter 4A Tighter Analysis of Spectral Clustering

Spectral clustering, as described in Algorithm 2, has been widely applied over
the past two decades due to its simplicity and excellent empirical performance
[NJW01]. In this chapter we theoretically analyse the spectral clustering
algorithm, and develop a tighter guarantee for well-clustered graphs than the
ones previously given in the literature. Informally, we analyse the
performance guarantee of spectral clustering under a simple assumption on the
input graph. While all the previous work (e.g., [LOGT14, KM16, Miz21, PSZ17])
on the same problem suggests that the assumption on the input graph must
depend on $k$, we show that the performance of spectral clustering can be
rigorously analysed under a general condition independent of $k$. This is the
first result of its kind, and could have further applications in graph
clustering.

Given a graph ${G}=({V},{E})$, the goal of graph clustering is to partition
$V$ into $k$ clusters $S_{1},\ldots,S_{k}$ according to some objective
function. Recall that we can measure the quality of a cluster ${S}_{i}$ by its
conductance

${\Phi}({S}_{i})=\frac{{w}({S}_{i},\overline{{S}_{i}})}{\min\\{\mathrm{vol}({S}_{i}),\mathrm{vol}(\overline{{S}_{i}})\\}},$

and that the $k$-way expansion of ${G}$ is a measure of the quality of the
optimal partitioning:

${\rho}(k)=\min_{\mathrm{partition}~{}{S}_{1},\ldots,{S}_{k}}\max_{i\in[k]}{\Phi}({S}_{i}).$

Let ${\mathbf{N}}$ be the normalised Laplacian matrix of ${G}$, and
$\lambda_{1}\leq\lambda_{2},\ldots,\leq\lambda_{n}$ be the eigenvalues of
${\mathbf{N}}$. In this chapter, we study spectral clustering on ${G}$ in
terms of the function $\Upsilon(k)$ defined by

$\Upsilon(k)\triangleq\frac{\lambda_{k+1}}{\rho(k)},$ (4.1)

which was introduced in Section 3.1.4. The first result in this chapter
improves on the structure theorem of Peng et al. [PSZ17] given in Theorem 3.4.

######  Main Result 1 (See Theorem 4.1 for the formal statement).

Given any graph ${G}$, let ${S}_{1},\ldots,{S}_{k}$ be the clusters which
achieve ${\rho}(k)$. The normalised indicator vectors of
${S}_{1},\ldots,{S}_{k}$ are well-approximated by the $k$ eigenvectors of the
graph Laplacian ${\mathbf{N}}$ corresponding to
$\lambda_{1},\ldots,\lambda_{k}$. The approximation guarantee is parameterised
by $\Upsilon(k)$, and is stronger for larger values of $\Upsilon(k)$.

In the remainder of the chapter, we consider spectral clustering for graphs
with clusters of almost-balanced size.

######  Definition 4.1.

(Almost-balanced) Let ${G}$ be a graph with $k$ clusters $S_{1},\ldots,S_{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[k]$.

The second result of this chapter is a guarantee on the performance of
spectral clustering under the assumption that $\Upsilon(k)\geq C$ for some
constant $C$.

######  Main Result 2 (See Theorem 4.2 for the formal statement).

Let $G=(V,E)$ be a graph, and $S_{1},\ldots,S_{k}$ the $k$ clusters of almost-
balanced size that achieves $\rho(k)$. Given $G$ as the input, let the output
of spectral clustering be $A_{1},\ldots,A_{k}$ and the ’optimal’ correspondent
of $A_{i}$ be $S_{i}$ for any $i\in[k]$. Then,
$\sum_{i=1}^{k}\mathrm{vol}(A_{i}\triangle S_{i})\leq
C\cdot\mathrm{vol}(V)/\Upsilon(k)$ for some constant $C$.

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, our result is non-trivial as
long as $\Upsilon(k)$ is lower bounded by some constant111Note that we can
take any constant approximation in Definition 4.1 with a different
corresponding constant in the main result.. This significantly improves most
of the previous analysis 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 by Oveis Gharan
and Trevisan [OGT14] assumes that
$\lambda_{k+1}=\Omega\\!\left(\mathrm{poly}(k)\lambda^{1/4}_{k}\right)$, and
the one presented by 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, the result in this
chapter 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 Stronger Structure Theorem

Let $\\{{S}_{i}\\}_{i=1}^{k}$ be any optimal partition that achieves
$\rho(k)$. Recall that ${\bm{\chi}}_{{S}_{i}}$ is the indicator vector of
${S}_{i}$, and that $\bar{{\bm{g}}}_{i}$ is the corresponding normalised
indicator vector, which is formally defined in Section 3.1.4. Additionally,
let ${\bm{f}}_{1},\ldots{\bm{f}}_{n}$ be the eigenvectors of ${\mathbf{N}}$
corresponding to the eigenvalues $\lambda_{1},\ldots,\lambda_{n}$. 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({\bm{f}}_{1},\ldots,{\bm{f}}_{k}\right)=\mathrm{span}\left(\bar{{\bm{g}}}_{1},\ldots,\bar{{\bm{g}}}_{k}\right)$
[Chu97]. Hence, one would expect that, when ${G}$ consists of $k$ densely
connected components (clusters) connected by sparse cuts, the bottom
eigenvectors $\\{{\bm{f}}_{i}\\}_{i=1}^{k}$ of ${\mathbf{N}}$ are close to
$\\{\bar{{\bm{g}}}_{i}\\}_{i=1}^{k}$.

In their work, Peng et al. [PSZ17] assume $\Upsilon(k)=\Omega(k^{2})$, and
prove that the space spanned by $\\{{\bm{f}}_{i}\\}_{i=1}^{k}$ and the one
spanned by $\\{\bar{{\bm{g}}}_{i}\\}_{i=1}^{k}$ are indeed close to each
other. Specifically, they show that

  1. 1.

for every $\bar{{\bm{g}}}_{i}$, there is some linear combination of
$\\{{\bm{f}}_{i}\\}^{k}_{i=1}$, denoted by $\widehat{{\bm{f}}}_{i}$, such that
$\|\bar{{\bm{g}}}_{i}-\widehat{{\bm{f}}}_{i}\|^{2}\leq 1/\Upsilon(k)$; and

  2. 2.

for every ${\bm{f}}_{i}$ there is some linear combination of
$\\{\bar{{\bm{g}}}_{i}\\}_{i=1}^{k}$, denoted by $\widehat{{\bm{g}}}_{i}$,
such that $\|{\bm{f}}_{i}-\widehat{{\bm{g}}}_{i}\|^{2}\leq 1.1k/\Upsilon(k)$.

See Theorem 3.4 for the formal statement. In essence, their 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.,
[CPS15, CSWZ16, KM16, KUK17, LV19, Miz21, Pen20, PY20, SZ19]).

We show that a stronger statement of the original structure theorem holds
under a much weaker assumption, and this result is summarised as follows:

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

The following statements hold:

  1. 1.

For any $i\in[k]$, there is a vector $\widehat{{\bm{f}}}_{i}\in\mathbb{R}^{n}$
which is a linear combination of ${\bm{f}}_{1},\ldots,{\bm{f}}_{k}$, such that
$\|\bar{{\bm{g}}}_{i}-\widehat{{\bm{f}}}_{i}\|^{2}\leq 1/\Upsilon(k)$.

  2. 2.

There are vectors $\widehat{{\bm{g}}}_{1},\ldots,\widehat{{\bm{g}}}_{k}$, each
of which is a linear combination of
$\bar{{\bm{g}}}_{1},\ldots,\bar{{\bm{g}}}_{k}$, such that
$\sum_{i=1}^{k}\left\|{\bm{f}}_{i}-\widehat{{\bm{g}}}_{i}\right\|^{2}\leq
k/\Upsilon(k)$.

To examine the significance of Theorem 4.1, notice that the 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, obtaining
these statements for general $\Upsilon(k)$ is important. Secondly, the second
statement of Theorem 4.1 significantly improves Theorem 3.4. Specifically,
instead of stating $\|{\bm{f}}_{i}-\widehat{{\bm{g}}}_{i}\|^{2}\leq
1.1k/\Upsilon(k)$ for any $i\in[k]$, the second statement shows that
$\sum_{i=1}^{k}\left\|{\bm{f}}_{i}-\widehat{{\bm{g}}}_{i}\right\|^{2}\leq
k/\Upsilon(k)$; hence, it holds in expectation that
$\left\|{\bm{f}}_{i}-\widehat{{\bm{g}}}_{i}\right\|^{2}\leq 1/\Upsilon(k)$,
the upper bound of which matches the first statement. This implies that the
vectors ${\bm{f}}_{1},\ldots,{\bm{f}}_{k}$ and
$\bar{{\bm{g}}}_{1},\ldots,\bar{{\bm{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 new proof is simple and purely linear-
algebraic. Therefore, both the stronger theorem and its much simplified proof
are significant, and could have further applications in graph clustering and
related problems.

###### Proof of Theorem 4.1.

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

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

Now, let us consider the quadratic form

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

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{{\bm{g}}}_{i}^{\intercal}{\mathbf{N}}\bar{{\bm{g}}}_{i}$
$\displaystyle=\sum_{(u,v)\in{E}}{w}(u,v)\left(\frac{\bar{{\bm{g}}}_{i}(u)}{\sqrt{{d}(u)}}-\frac{\bar{{\bm{g}}}_{i}(v)}{\sqrt{{d}(v)}}\right)^{2}$
$\displaystyle=\sum_{(u,v)\in{E}}{w}(u,v)\left(\frac{{\bm{\chi}}_{i}(u)}{\sqrt{\mathrm{vol}({S}_{i})}}-\frac{{\bm{\chi}}_{i}(v)}{\sqrt{\mathrm{vol}({S}_{i})}}\right)^{2}$
$\displaystyle=\frac{{w}({S}_{i},\overline{{S}_{i}})}{\mathrm{vol}({S}_{i})}\leq\rho(k).$
(4.3)

Combining (4.2) with (4.3), we have that

$\left\|\bar{{\bm{g}}}_{i}-\widehat{{\bm{f}}}_{i}\right\|^{2}\leq\frac{\bar{{\bm{g}}}_{i}^{\intercal}{\mathbf{N}}\bar{{\bm{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{{\bm{g}}}_{i}=\sum_{j=1}^{k}\langle{\bm{f}}_{i},\bar{{\bm{g}}}_{j}\rangle\bar{{\bm{g}}}_{j}$
and have that, since ${\bm{f}}_{i}-\widehat{{\bm{g}}}_{i}$ is perpendicular to
$\widehat{{\bm{g}}}_{i}$,

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

where the inequality follows by the first statement of Theorem 4.1. ∎

###  4.2 Analysis of Spectral Clustering

For any input graph ${G}=({V},{E})$ and $k\in[n]$, we study the following
spectral clustering algorithm:

  1. 1.

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

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

  2. 2.

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

  3. 3.

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

In this rest of this section, we prove the following theorem, where APT is the
approximation ratio of the $k$-means algorithm used in spectral clustering.
Recall that we can take APT to be some small constant [CGKR21, KSS04].

######  Theorem 4.2.

Let ${G}=({V},{E})$ be a graph with $k$ clusters $S_{1},\ldots,S_{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 assume,
without loss of generality, that 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})}{\Upsilon(k)}.$

The most significant feature of Theorem 4.2 is that the lower bound of
$\Upsilon(k)$ is independent of the number of clusters $k$. The theorem gives
a non-trivial guarantee on the performance of spectral clustering so long as
the spectral gap, as measured by $\Upsilon(k)$, is at least a constant. This
improves on the previous analysis of graph clustering algorithms which make
stronger assumptions on the input graphs [PSZ17, Miz21, LOGT14].

####  4.2.1 Properties of Spectral Embedding

Let us first study the properties of the spectral embedding defined in (4.4),
and in the next subsection we use these properties to prove Theorem 4.2. For
every cluster ${S}_{i}$, define the vector ${\bm{p}}^{(i)}\in\mathbb{R}^{k}$
by

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

and we can view these $\\{{\bm{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)-{\bm{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)-{\bm{p}}^{(i)}\right\|^{2}$
$\displaystyle=\sum_{i=1}^{k}\sum_{u\in{S}_{i}}{d}(u)\left[\sum_{j=1}^{k}\left(\frac{{\bm{f}}_{j}(u)}{\sqrt{{d}(u)}}-\frac{\langle\bar{{\bm{g}}}_{i},{\bm{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({\bm{f}}_{j}(u)-\langle\bar{{\bm{g}}}_{i},{\bm{f}}_{j}\rangle\bar{{\bm{g}}}_{i}(u)\right)^{2}$
$\displaystyle=\sum_{i=1}^{k}\sum_{u\in{S}_{i}}\sum_{j=1}^{k}\left({\bm{f}}_{j}(u)-\widehat{{\bm{g}}}_{j}(u)\right)^{2}$
$\displaystyle=\sum_{j=1}^{k}\left\|{\bm{f}}_{j}-\widehat{{\bm{g}}}_{j}\right\|^{2}\leq\frac{k}{\Upsilon(k)},$

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

The importance of Lemma 4.1 is that, although the optimal centres for
$k$-means are unknown, the existence of $\\{{\bm{p}}^{(i)}\\}_{i=1}^{k}$ is
sufficient to show that the cost of an optimal $k$-means clustering on
$\\{F(u)\\}_{u\in{V}}$ 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}}$ is
$O\left(k/\Upsilon(k)\right)$. Next, we show that the length of
${\bm{p}}^{(i)}$ is approximately equal to $1/\mathrm{vol}({S}_{i})$, which is
used 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\|{\bm{p}}^{(i)}\right\|^{2}\leq\frac{1}{\mathrm{vol}({S}_{i})}.$

###### Proof.

By definition, we have

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

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

In the remainder of this subsection, we prove a sequence of lemmas showing
that any pair of ${\bm{p}}^{(i)}$ and ${\bm{p}}^{(j)}$ for $i\neq j$ are well
separated. Moreover, 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{\bm{p}}^{(i)}-\sqrt{\mathrm{vol}({S}_{j})}\cdot{\bm{p}}^{(j)}\right\|^{2}\geq
2-\frac{8}{\Upsilon(k)}.$

###### Proof.

By the definitions of ${\bm{p}}^{(i)}$ and $\widehat{{\bm{f}}}_{i}$, we have

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

Then, considering only the final term, we have

$\displaystyle\left\lvert\widehat{{\bm{f}}}_{i}^{\intercal}\widehat{{\bm{f}}}_{j}\right\rvert$
$\displaystyle=\left\lvert(\bar{{\bm{g}}}_{i}+\widehat{{\bm{f}}}_{i}-\bar{{\bm{g}}}_{i})^{\intercal}(\bar{{\bm{g}}}_{j}+\widehat{{\bm{f}}}_{j}-\bar{{\bm{g}}}_{j})\right\rvert$
$\displaystyle=\left\lvert\langle\bar{{\bm{g}}}_{i},\widehat{{\bm{f}}}_{j}-\bar{{\bm{g}}}_{j}\rangle+\langle\bar{{\bm{g}}}_{j},\widehat{{\bm{f}}}_{i}-\bar{{\bm{g}}}_{i}\rangle+\langle\widehat{{\bm{f}}}_{i}-\bar{{\bm{g}}}_{i},\widehat{{\bm{f}}}_{j}-\bar{{\bm{g}}}_{j}\rangle\right\rvert$
$\displaystyle=\left\lvert\langle\widehat{{\bm{f}}}_{i}-\bar{{\bm{g}}}_{i},\widehat{{\bm{f}}}_{j}-\bar{{\bm{g}}}_{j}\rangle+\langle\widehat{{\bm{f}}}_{j}-\bar{{\bm{g}}}_{j},\widehat{{\bm{f}}}_{i}-\bar{{\bm{g}}}_{i}\rangle+\langle\widehat{{\bm{f}}}_{i}-\bar{{\bm{g}}}_{i},\widehat{{\bm{f}}}_{j}-\bar{{\bm{g}}}_{j}\rangle\right\rvert\leq\frac{3}{\Upsilon(k)},$

where we use the fact that
$\left\langle\bar{{\bm{g}}}_{i},\bar{{\bm{g}}}_{j}\right\rangle=0$ for $i\neq
j$ and $\left\|\widehat{{\bm{f}}}_{i}-\bar{{\bm{g}}}_{i}\right\|^{2}\leq
1/\Upsilon(k)$. Then, since $\left\|\widehat{{\bm{f}}}_{i}\right\|^{2}\geq
1-1/\Upsilon(k)$, we have

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

######  Lemma 4.4.

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

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

###### Proof.

Assume without loss of generality that
$\sqrt{\mathrm{vol}({S}_{i})}\left\|{\bm{p}}^{(i)}\right\|\leq\sqrt{\mathrm{vol}({S}_{j})}\left\|{\bm{p}}^{(j)}\right\|$.
Let ${\bm{a}}_{i}=\sqrt{\mathrm{vol}({S}_{i})}{\bm{p}}^{(i)}$ and
${\bm{a}}_{j}=\sqrt{\mathrm{vol}({S}_{j})}{\bm{p}}^{(j)}$ and notice that
$\left\|{\bm{a}}_{i}\right\|\leq\left\|{\bm{a}}_{j}\right\|\leq 1$ by Lemma
4.2. Then, since ${\bm{a}}_{i}$ and
$(\left\|{\bm{a}}_{i}\right\|/\left\|{\bm{a}}_{j}\right\|){\bm{a}}_{j}$ are
scaled versions of ${\bm{p}}^{(i)}$ and ${\bm{p}}^{(j)}$ with smaller norm, we
have

$\displaystyle\left\|\frac{{\bm{p}}^{(i)}}{\left\|{\bm{p}}^{(i)}\right\|}-\frac{{\bm{p}}^{(j)}}{\left\|{\bm{p}}^{(j)}\right\|}\right\|$
$\displaystyle\geq\left\|{\bm{a}}_{i}-\frac{\left\|{\bm{a}}_{i}\right\|}{\left\|{\bm{a}}_{j}\right\|}{\bm{a}}_{j}\right\|$
$\displaystyle\geq\left\|{\bm{a}}_{i}-{\bm{a}}_{j}\right\|-\left(\left\|{\bm{a}}_{j}\right\|-\left\|{\bm{a}}_{i}\right\|\right)$
$\displaystyle\geq\sqrt{2-\frac{8}{\Upsilon(k)}}-\left(\sqrt{\mathrm{vol}({S}_{j})}\cdot\left\|{\bm{p}}^{(j)}\right\|-\sqrt{\mathrm{vol}({S}_{i})}\left\|{\bm{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)}\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 and Lemma 4.2. We also use the fact that it holds for
$x\leq 1$ that $\sqrt{1-x}\geq 1-x$. This gives

$\displaystyle\left\|\frac{{\bm{p}}^{(i)}}{\left\|{\bm{p}}^{(i)}\right\|}-\frac{{\bm{p}}^{(j)}}{\left\|{\bm{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 different $i,j\in[k]$ that

$\left\|{\bm{p}}^{(i)}-{\bm{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\|{\bm{p}}^{(i)}\right\|\geq\left\|{\bm{p}}^{(j)}\right\|$. Then, let
$\left\|{\bm{p}}^{(j)}\right\|=\alpha\left\|{\bm{p}}^{(i)}\right\|$ for some
$\alpha\in[0,1]$. By Lemma 4.2, it holds that

$\left\|{\bm{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{{\bm{p}}^{(i)}}{\left\|{\bm{p}}^{(i)}\right\|},\frac{{\bm{p}}^{(j)}}{\left\|{\bm{p}}^{(j)}\right\|}\right\rangle\leq\sqrt{2}-\frac{1}{2}\left\|\frac{{\bm{p}}^{(i)}}{\left\|{\bm{p}}^{(i)}\right\|}-\frac{{\bm{p}}^{(j)}}{\left\|{\bm{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 ${\bm{p}}^{(i)}/\left\|{\bm{p}}^{(i)}\right\|$ and another
edge given by
$({\bm{p}}^{(i)}/\left\|{\bm{p}}^{(i)}\right\|).({\bm{p}}^{(j)}/\left\|{\bm{p}}^{(j)}\right\|)$.
Then,

$\displaystyle\left\|{\bm{p}}^{(i)}-{\bm{p}}^{(j)}\right\|^{2}$
$\displaystyle=\left\|{\bm{p}}^{(i)}\right\|^{2}+\left\|{\bm{p}}^{(j)}\right\|^{2}-2\left\langle\frac{{\bm{p}}^{(i)}}{\left\|{\bm{p}}^{(i)}\right\|},\frac{{\bm{p}}^{(j)}}{\left\|{\bm{p}}^{(j)}\right\|}\right\rangle\left\|{\bm{p}}^{(i)}\right\|\left\|{\bm{p}}^{(j)}\right\|$
$\displaystyle\geq(1+\alpha)\left\|{\bm{p}}^{(i)}\right\|^{2}-\left(\sqrt{2}+\frac{7}{\Upsilon(k)}\right)\alpha\left\|{\bm{p}}^{(i)}\right\|^{2}$
$\displaystyle\geq\left(1-(\sqrt{2}-1)\alpha-\frac{7}{\Upsilon(k)}\right)\left\|{\bm{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. ∎

It is worth noting that, despite the similarity in their formulation, the
technical lemmas presented here are stronger than the ones in Peng et al.
[PSZ17]. These results are obtained through the stronger structure theorem
(Theorem 4.1), and are crucial for us to prove Theorem 4.2.

####  4.2.2 Bounding the Misclassified Vertices

Now we prove Theorem 4.2, and see why a mild condition like $\Upsilon(k)\geq
C$ for some constant $C\in\mathbb{N}$ 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)\\}_{u\in{A}_{i}}$ for any ${A}_{i}$ by ${\bm{c}}_{i}$. As the
starting point of the analysis, we show that every ${\bm{c}}_{i}$ is close to
its ‘optimal’ correspondent ${\bm{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\|{\bm{p}}^{(j)}-{\bm{c}}_{i}\right\|;$
(4.5)

that is, cluster ${A}_{i}$ should correspond to ${S}_{\sigma(i)}$ in which the
value of $\|{\bm{p}}^{(\sigma(i))}-{\bm{c}}_{i}\|$ is the lowest among all the
distances between ${\bm{c}}_{i}$ and all of the ${\bm{p}}^{(j)}$ for
$j\in[k]$. However, one needs to be cautious as (4.5) doesn’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.6)

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.5) and (4.6). 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 ground-truth 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.7)

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)-{\bm{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)-{\bm{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\|{\bm{p}}^{(j)}-{\bm{c}}_{i}\right\|^{2}}{2}-\left\|{\bm{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\|{\bm{p}}^{(j)}-{\bm{p}}^{(\sigma(i))}\right\|^{2}}{8}-\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\|{\bm{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\|{\bm{p}}^{(j)}-{\bm{p}}^{(\sigma(i))}\right\|^{2}}{8}-\sum_{i=1}^{k}\sum_{u\in{S}_{i}}{d}(u)\left\|{\bm{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\|{\bm{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

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

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

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}\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}$ which are equal to $\emptyset$ by one. We show
that one only needs to construct such $\sigma^{\prime}$ at most
$64(1+\textsf{APT})(k/\Upsilon(k))$ 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})}\leq
1088\cdot(1+\textsf{APT})\cdot\frac{k}{\Upsilon(k)}.$

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

###### Proof of Theorem 4.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 each
cluster ${A}_{i}$ to some ground-truth cluster ${S}_{\sigma(i)}$ such that
$\sigma(i)=\operatorname*{arg\,min}_{j\in[k]}\left\|{\bm{p}}^{(j)}-{\bm{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.8)

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

$\displaystyle\epsilon(\sigma^{\prime})-\epsilon(\sigma)$
$\displaystyle=\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.9)

Let us consider $4$ cases based on the sign 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\begin{multlined}\frac{1}{\min(\mathrm{vol}({S}_{i}),\mathrm{vol}({S}_{j}))}\Big{(}\mathrm{vol}({M}_{\sigma^{\prime},i}\triangle{S}_{i})-\mathrm{vol}({M}_{\sigma,i}\triangle{S}_{i})\qquad\\\
+\left\lvert\mathrm{vol}({M}_{\sigma^{\prime},j}\triangle{S}_{j})-\mathrm{vol}({M}_{\sigma,j}\triangle{S}_{j})\right\rvert\Big{)}\end{multlined}\frac{1}{\min(\mathrm{vol}({S}_{i}),\mathrm{vol}({S}_{j}))}\Big{(}\mathrm{vol}({M}_{\sigma^{\prime},i}\triangle{S}_{i})-\mathrm{vol}({M}_{\sigma,i}\triangle{S}_{i})\qquad\\\
+\left\lvert\mathrm{vol}({M}_{\sigma^{\prime},j}\triangle{S}_{j})-\mathrm{vol}({M}_{\sigma,j}\triangle{S}_{j})\right\rvert\Big{)}$
$\displaystyle=\begin{multlined}\frac{1}{\min(\mathrm{vol}({S}_{i}),\mathrm{vol}({S}_{j}))}\Big{(}\mathrm{vol}({M}_{\sigma^{\prime},i}\triangle{S}_{i})-\mathrm{vol}({M}_{\sigma,i}\triangle{S}_{i})\qquad\\\
+\mathrm{vol}({M}_{\sigma,j}\triangle{S}_{j})-\mathrm{vol}({M}_{\sigma^{\prime},j}\triangle{S}_{j})\Big{)}\end{multlined}\frac{1}{\min(\mathrm{vol}({S}_{i}),\mathrm{vol}({S}_{j}))}\Big{(}\mathrm{vol}({M}_{\sigma^{\prime},i}\triangle{S}_{i})-\mathrm{vol}({M}_{\sigma,i}\triangle{S}_{i})\qquad\\\
+\mathrm{vol}({M}_{\sigma,j}\triangle{S}_{j})-\mathrm{vol}({M}_{\sigma^{\prime},j}\triangle{S}_{j})\Big{)}$
$\displaystyle=\begin{multlined}\frac{1}{\min(\mathrm{vol}({S}_{i}),\mathrm{vol}({S}_{j}))}\big{(}\mathrm{vol}({A}_{x}\setminus{S}_{i})-\mathrm{vol}({A}_{x}\cap{S}_{i})\qquad\\\
+\mathrm{vol}({A}_{x}\setminus{S}_{j})-\mathrm{vol}({A}_{x}\cap{S}_{j})\big{)}\end{multlined}\frac{1}{\min(\mathrm{vol}({S}_{i}),\mathrm{vol}({S}_{j}))}\big{(}\mathrm{vol}({A}_{x}\setminus{S}_{i})-\mathrm{vol}({A}_{x}\cap{S}_{i})\qquad\\\
+\mathrm{vol}({A}_{x}\setminus{S}_{j})-\mathrm{vol}({A}_{x}\cap{S}_{j})\big{)}$
$\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\begin{multlined}\frac{1}{\min(\mathrm{vol}({S}_{i}),\mathrm{vol}({S}_{j}))}\big{(}\mathrm{vol}({M}_{\sigma^{\prime},i}\triangle{S}_{i})-\mathrm{vol}({M}_{\sigma,i}\triangle{S}_{i})\qquad\\\
+\mathrm{vol}({M}_{\sigma^{\prime},j}\triangle{S}_{j})-\mathrm{vol}({M}_{\sigma,j}\triangle{S}_{j})\big{)}\end{multlined}\frac{1}{\min(\mathrm{vol}({S}_{i}),\mathrm{vol}({S}_{j}))}\big{(}\mathrm{vol}({M}_{\sigma^{\prime},i}\triangle{S}_{i})-\mathrm{vol}({M}_{\sigma,i}\triangle{S}_{i})\qquad\\\
+\mathrm{vol}({M}_{\sigma^{\prime},j}\triangle{S}_{j})-\mathrm{vol}({M}_{\sigma,j}\triangle{S}_{j})\big{)}$
$\displaystyle=\begin{multlined}\frac{1}{\min(\mathrm{vol}({S}_{i}),\mathrm{vol}({S}_{j}))}\big{(}\mathrm{vol}({A}_{x}\setminus{S}_{i})-\mathrm{vol}({A}_{x}\cap{S}_{i})\qquad\\\
+\mathrm{vol}({A}_{x}\cap{S}_{j})-\mathrm{vol}({A}_{x}\setminus{S}_{j})\big{)}\end{multlined}\frac{1}{\min(\mathrm{vol}({S}_{i}),\mathrm{vol}({S}_{j}))}\big{(}\mathrm{vol}({A}_{x}\setminus{S}_{i})-\mathrm{vol}({A}_{x}\cap{S}_{i})\qquad\\\
+\mathrm{vol}({A}_{x}\cap{S}_{j})-\mathrm{vol}({A}_{x}\setminus{S}_{j})\big{)}$
$\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

$\left\lvert\\{i:{M}_{\sigma,i}=\emptyset\\}\right\rvert\leq\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)}.$

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

$\epsilon(\sigma^{\star})\leq\epsilon(\sigma)+1024\cdot(1+\textsf{APT})\cdot\frac{k}{\Upsilon(k)}\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. ∎

It is worth noting 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}$, in this proof we directly work with some
specifically defined function $\sigma$, and constructed our desired mapping
$\sigma^{\star}$ from $\sigma$. This is another key for us to obtain stronger
results than the previous work.

###  4.3 Future Work

Notice that the analysis presented in this chapter requires that the optimal
clusters have almost-balanced size, which is the only technical assumption of
our result. This raises a natural question on the necessity of such a
condition.

######  Open Question 1.

Is it possible for spectral clustering to theoretically achieve the same
approximation guarantee as Theorem 4.2 when the optimal clusters of an input
graph have arbitrary sizes? Alternatively, is there a hard instance showing
that our presented analysis is tight up to some constant factor?

Secondly, it would be very interesting to see whether one can theoretically
analyse the performance of spectral clustering with respect to
$\lambda_{k+1}/\lambda_{k}$, instead of $\Upsilon(k)$.

######  Open Question 2.

Is it possible to upper bound the number (or volume) of misclassified vertices
from spectral clustering with respect to the ratio between $\lambda_{k+1}$ and
$\lambda_{k}$?

Notice that, in contrast to $\Upsilon(k)$, the value of
$\lambda_{k+1}/\lambda_{k}$ can be computed in polynomial time; therefore, an
affirmative answer to the question will have more practical impact than our
current presented result. In addition, such an answer would further justify
the eigen-gap heuristic [vL07], helping to close the gap between the
theoretical analysis of spectral clustering and its empirical performance.

## Chapter 5Spectral Clustering with Meta-Graphs

In this chapter we build on the analysis of the last chapter and develop a
variant of spectral clustering which employs fewer than $k$ eigenvectors to
find $k$ clusters. We prove the surprising result 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. This presents the opportunity to
significantly speed up the runtime of spectral clustering in practice, since
fewer eigenvectors are used to construct the embedding.

The starting point of our new analysis is the following observation: in many
graphs arising from real-world data, the structure of clusters is not
symmetric. For example, let us consider the well-known MNIST dataset of
handwritten digits [Hul94]. This dataset consists of 70,000 images of
handwritten digits 0 to 9. Each image has $28\times 28$ pixels, and each pixel
has a greyscale value between 0 and 255. Figure 5.1 shows some example images
from the MNIST dataset.

Figure 5.1: Example images from the MNIST dataset.

Then, we can represent each image in the dataset by a vector
${\bm{x}}_{i}\in\mathbb{R}^{28\times 28}$ and construct the $\bm{k}$ nearest
neighbours graph, ${G}=({V},{E})$, in the following way:

  * •

for each data point ${\bm{x}}_{i}$ in the dataset, there is a corresponding
vertex $v_{i}\in{V}$;

  * •

for each $v_{i}$ there is an undirected edge to the $k$ vertices representing
the data points with the smallest distances to ${\bm{x}}_{i}$.

Figure 5.2 illustrates the $k$ nearest neighbour graph for a randomly chosen
subset of the data.

Figure 5.2: The $k$ nearest neighbour graph of a random subset of the MNIST
dataset, for $k=3$. The graph has a cluster corresponding to each digit.

Notice that some of the clusters in this graph are more similar than others.
For example, the cluster representing the digit $4$ has more connections with
the cluster representing $9$ than the one representing $6$. The central result
of this chapter is that this _asymmetry_ can be used to improve the
performance of spectral clustering, and allow us to recover all $10$ clusters
while using fewer than $10$ eigenvectors of the graph Laplacian.

######  Main Result 3 (See Theorem 5.2 for the formal statement).

Given a graph ${G}$, let ${S}_{1},\ldots,{S}_{k}$ be the clusters which
achieve ${\rho}(k)$ and suppose that ${S}_{1},\ldots,{S}_{k}$ are almost-
balanced. Additionally, suppose that the clusters ${S}_{1},\ldots,{S}_{k}$
exhibit some significant high-level structure. Then, spectral clustering with
fewer than $k$ eigenvectors performs better than spectral clustering with $k$
eigenvectors.

The significance of this result is further demonstrated by experiments on the
BSDS image segmentation dataset. It is well known that spectral methods are an
effective technique for image segmentation [SM00, TWC10, ZZL+21], and in this
chapter we see that spectral clustering is effective for image segmentation,
and that using fewer eigenvectors often results in a better segmentation.
Figure 5.3 shows examples in which, 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. Section 5.3 describes the full
experimental details.

(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 5.3: Examples of image segmentation using spectral clustering; the
original images are from the BSDS dataset. 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.

The result in this chapter is related to previous work on efficient spectral
algorithms to find cluster-structures. While it’s known that flow and path