# Nearly-Optimal Hierarchical Clustering for Well-Clustered Graphs444A
preliminary version of the work appeared at the 40th International Conference
on Machine Learning (ICML ’23).

Steinar Laenen111School of Informatics, University of Edinburgh, UK.
<EMAIL_ADDRESS>Bogdan-Adrian Manghiuc222School of Informatics,
University of Edinburgh, UK<EMAIL_ADDRESS> He Sun333School of
Informatics, University of Edinburgh, UK<EMAIL_ADDRESS>This work is
supported by an EPSRC Early Career Fellowship (EP/T00729X/1).

###### Abstract

This paper presents two efficient hierarchical clustering (HC) algorithms with
respect to Dasgupta’s cost function. For any input graph $G$ with a clear
cluster-structure, our designed algorithms run in nearly-linear time in the
input size of $G$, and return an $O(1)$-approximate HC tree with respect to
Dasgupta’s cost function. We compare the performance of our algorithm against
the previous state-of-the-art on synthetic and real-world datasets and show
that our designed algorithm produces comparable or better HC trees with much
lower running time.

###### Contents

  1. 1 Introduction
  2. 2 Related Work
  3. 3 Preliminaries
    1. 3.1 Notation
    2. 3.2 Hierarchical Clustering
    3. 3.3 Contracted Graphs
    4. 3.4 Spectral Clustering
  4. 4 Hierarchical Clustering for Well-Clustered Graphs: Previous Approach
  5. 5 Algorithms
    1. 5.1 The First Algorithm
      1. 5.1.1 Overview of the Algorithm
      2. 5.1.2 Proof Sketch of Theorem 5.1
      3. 5.1.3 Proof Sketch of Lemma 5.2 and Lemma 5.3
    2. 5.2 The Second Algorithm
  6. 6 Experiments
    1. 6.1 Results on Synthetic Data
      1. 6.1.1 Stochastic Block Model
      2. 6.1.2 Hierarchical Stochastic Block Model
    2. 6.2 Result on Real-World Data
  7. A Additional Background
    1. A.1 Hierarchical Clustering
    2. A.2 Spectral Clustering
    3. A.3 Strong Decomposition Lemma
  8. B Omitted Details of Proof of Theorem 5.1
    1. B.1 Caterpillar Tree on Extended Critical Nodes
    2. B.2 Proof of Lemmas 5.2 and 5.3
    3. B.3 Proof of Theorem 5.1
  9. C Omitted Details of Proof of Theorem 5.4
    1. C.1 Overview of Main Techniques
    2. C.2 Algorithm Description
    3. C.3 Algorithm Analysis

##  1 Introduction

Hierarchical clustering (HC) is the recursive partitioning of a dataset into
increasingly smaller clusters via an effective binary tree representation, and
has been employed as a standard package in data analysis with widespread
applications in practice. Traditional HC algorithms are typically based on
agglomerative heuristics and, due to the lack of a clear objective function,
there was limited work on their analysis. Dasgupta [Das16] introduced a simple
cost function for hierarchical clustering, and this work has inspired a number
of algorithmic studies on hierarchical clustering.

In this paper we study efficient hierarchical clustering for graphs with a
clear structure of clusters. We prove that, under two different conditions of
an input graph $G$ that characterise its cluster-structure, one can construct
in nearly-linear time555We say that, for an input graph $G$ with $n$ vertices
and $m$ edges, an algorithm runs in nearly-linear time if the algorithm’s
running time is $O(m\cdot\log^{c}n)$ for some constant $c$. For simplicity we
use $\widetilde{O}(\cdot)$ to hide this $\log^{c}n$ factor. an
$O(1)$-approximate HC tree $\mathcal{T}$ of $G$ with respect to Dasgupta’s
cost. Our results show that, while it’s NP-hard to construct an
$O(1)$-approximate HC tree for general graphs assuming the Small Set Expansion
Hypothesis [CC17], an $O(1)$-approximate HC tree can be constructed in nearly-
linear time for a wide range of graph instances occurring in practice. This
nearly-linear time complexity of our designed algorithms represents a
significant improvement over the previous state-of-the-art on the same problem
[MS21].

Our designed two algorithms share the same framework at the high level: we
apply spectral clustering [NJW01] to partition an input graph $G$ into $k$
clusters $P_{1},\ldots,P_{k}$, and further partition each cluster by grouping
the vertices in every $P_{i}~{}(1\leqslant i\leqslant k)$ with respect to
their degrees. We call the resulting vertex sets _degree buckets_ , and show
that the Dasgupta cost of HC trees constructed on degree buckets is low. These
intermediate trees constructed on every bucket can therefore form the basis of
our final tree. To construct the final HC tree on $G$, we merge the degree
bucket trees based on the following two approaches:

  * •

Our first approach treats every degree bucket of vertices in $G$ as a single
vertex of another “contracted” graph $H$ with much fewer vertices. Thanks to
the small size of $H$, we apply the recursive sparsest cut algorithm and
construct a tree on $H$ in a top-down fashion. The structure of this tree on
$H$ determines how the degree bucket trees are merged when constructing our
final tree of $G$.

  * •

For our second approach, we show that under a regularity assumption on the
vertex degrees, it suffices to merge the clusters in a “caterpillar” style.
This simpler construction allows our second algorithm to run in nearly-linear
time for a larger number of clusters $k$ compared with the first algorithm.

To demonstrate the significance of our work, we experimentally compare our
first algorithm against the previous state-of-the-art and a well-known linkage
heuristic (AverageLinkage) on both synthetic and real-world datasets. Our
experimental results show that the trees constructed from our algorithm and
AverageLinkage achieve similar cost values, which are much lower than the ones
constructed from [CAKMT17] and [MS21]. Moreover, our algorithm runs
significantly faster than the other three tested algorithms.

##  2 Related Work

Addressing the lack of an objective function for hierarchical clustering,
Dasgupta [Das16] introduced a simple cost function to measure the quality of
an HC tree, and proved several properties of the cost function. Dasgupta
further showed that a recursive sparsest cut algorithm can be applied to
construct an $O(\log^{3/2}n)$-approximate HC tree. Charikar and Chatziafratis
[CC17] improved the analysis of constructing HC trees based on the sparsest
cut problem, and proved that an $\alpha$-approximate algorithm for the
sparsest cut problem can be employed to construct an $O(\alpha)$-approximate
HC tree. This implies that, by applying the state-of-the-art for the sparsest
cut problem [ARV09], an $O(\sqrt{\log n})$-approximate HC tree can be
constructed in polynomial-time.

It is known that, assuming the Small Set Expansion Hypothesis, it is NP-hard
to construct an $O(1)$-approximate HC tree for general graphs [CC17]. Hence,
it is natural to examine the conditions of input graphs under which an
$O(1)$-approximate HC tree can be constructed in polynomial-time. Cohen-Addad
et al. [CAKMT17] studied a hierarchical extension of the classical stochastic
block model (SBM) and showed that, for graphs randomly generated from this
model, there is an SVD projection-based algorithm [McS01] that, together with
linkage heuristics, constructs a $(1+o(1))$-approximate HC tree with high
probability. Manghiuc and Sun [MS21] studied hierarchical clustering for well-
clustered graphs and proved that, when there is a cluster-structure of an
input graph $G$, an $O(1)$-approximate HC tree of $G$ can be constructed in
polynomial-time; their designed algorithm is based on the graph decomposition
algorithm by Oveis Gharan and Trevisan [OGT14], and has high time complexity.

There are recent studies of hierarchical clustering in different models of
computation. For instance, Kapralov et al. [KKLM22] studied the problem of
learning the hierarchical cluster structure of graphs in a semi-supervised
setting. Their presented algorithm runs in sub-linear time and, under some
clusterability conditions of an input graph $G$ with $k$ clusters, their
algorithm $O(\sqrt{\log k})$-approximates Dasgupta’s cost of an optimal HC
tree. This work is incomparable to ours: the objective of their work is to
approximate Dasgupta’s cost of an HC tree, while the output of our algorithms
is a complete HC tree.

Finally, there are studies of hierarchical clustering under different
objective functions. Moseley and Wang [MW17] studied the dual of Dasgupta’s
cost function. This objective, and a dissimilarity objective by Cohen-Addad et
al. [CAKMTM19], have received considerable attention [AAV20, CCN19, CYL+20].
It is important to notice that an $O(1)$-approximate HC tree can be
constructed efficiently for general graphs under these objectives, suggesting
the fundamental difference in the computational complexity of constructing an
HC tree under different objectives. This is the main reason for us to entirely
focus on Dasgupta’s cost function in this work.

##  3 Preliminaries

This section lists the background knowledge used in our paper, and is
organised as follows: In Section 3.1 we list the basic notation and facts in
spectral graph theory. Section 3.2 discusses hierarchical clustering and
Dasgupta’s cost function. In Section 3.3 we introduce the notion of contracted
graphs, and we finish the section with a brief introduction to spectral
clustering in Section 3.4.

###  3.1 Notation

We always assume that $G=(V,E,w)$ is an undirected graph with $|V|=n$
vertices, $|E|=m$ edges, and weight function $w:V\times
V\rightarrow\mathbb{R}_{\geqslant 0}$. For any edge $e=\\{u,v\\}\in E$, we
write $w_{e}$ or $w_{uv}$ to express the weight of $e$. Let $w_{\mathrm{min}}$
and $w_{\mathrm{max}}$ be the minimum and maximum edge weight of $G$,
respectively; we further assume that
$w_{\mathrm{max}}/w_{\mathrm{min}}\leqslant c\cdot n^{\gamma}$ for some
constants $\gamma>0$ and $c$, which are independent of the input size.

For a vertex $u\in V$, we denote its _degree_ by $d_{u}\triangleq\sum_{v\in
V}w_{uv}$. We use $\delta_{G},\Delta_{G}$, and $d_{G}$ for the minimum,
maximum and average degrees in $G$ respectively, where
$d_{G}\triangleq\sum_{u\in V}d_{u}/n$. For any $S\subset V$, we use
$\delta_{G}(S),\Delta_{G}(S)$, and $d_{G}(S)$ to represent the minimum,
maximum, and average degrees of the vertices of $S$ in $G$.

For any two subsets $S,T\subset V$, we define the _cut value_ between $S$ and
$T$ by $w(S,T)\triangleq\sum_{e\in E(S,T)}w_{e}$, where $E(S,T)$ is the set of
edges between $S$ and $T$. For any $G=(V,E,w)$ and set $S\subseteq V$, the
_volume_ of $S$ is $\mathrm{vol}_{G}(S)\triangleq\sum_{u\in S}d_{u}$, and we
write $\mathrm{vol}(G)$ when referring to $\mathrm{vol}_{G}(V)$. Sometimes we
drop the subscript $G$ when it is clear from the context. For any non-empty
subset $S\subset V$, we define $G[S]$ to be the induced subgraph on $S$.

For any input graph $G=(V,E,w)$ and any $S\subset V$, let the conductance of
$S$ in $G$ be

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

We define the conductance of $G$ by

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

For any non-empty subset $S\subset V$ we refer to $\Phi_{G}(S)$ as the _outer
conductance_ of $S$ with respect to $G$, and $\Phi_{G[S]}$ as the _inner
conductance_ of $S$.

Our analysis is based on the spectral properties of graphs, and here we list
the basics of spectral graph theory. For a graph $G=(V,E,w)$, let
$\mathbf{D}\in\mathbb{R}^{n\times n}$ be the diagonal matrix defined by
$\mathbf{D}_{uu}=d_{u}$ for all $u\in V$. We denote by
$\mathbf{A}\in\mathbb{R}^{n\times n}$ the _adjacency matrix_ of $G$, where
$\mathbf{A}_{uv}=w_{uv}$ for all $u,v\in V$. The _normalised Laplacian matrix_
of $G$ is defined as
$\mathcal{L}\triangleq\mathbf{I}-\mathbf{D}^{-1/2}\mathbf{A}\mathbf{D}^{-1/2}$,
where $\mathbf{I}$ is the $n\times n$ identity matrix. The normalised
Laplacian $\mathcal{L}$ is symmetric and real-valued, and has $n$ real
eigenvalues which we write as
$\lambda_{1}\leqslant\ldots\leqslant\lambda_{n}$. It is known that
$\lambda_{1}=0$ and $\lambda_{n}\leqslant~{}2$ [Chu97].

For any integer $k\geqslant 2$, we call subsets of vertices
$A_{1},\ldots,A_{k}$ a $k$-way partition of $G$ if $\bigcup_{i=1}^{k}A_{i}=V$
and $A_{i}\cap A_{j}=\emptyset$ for different $i$ and $j$. We define the _$k$
-way expansion_ of $G$ by

$\rho(k)\triangleq\min_{\mathrm{partitions\>}A_{1},\dots,A_{k}}\max_{1\leqslant
i\leqslant k}\Phi_{G}(A_{i}).$

The celebrated higher-order Cheeger inequality [LOGT14] states that it holds
for any graph $G$ and $k\geqslant 2$ that

$\frac{\lambda_{k}}{2}\leqslant\rho(k)\leqslant O(k^{3})\sqrt{\lambda_{k}}.$
(3.1)

###  3.2 Hierarchical Clustering

A _hierarchical clustering ( HC) tree_ of a given graph $G$ is a binary tree
$\mathcal{T}$ with $n$ leaf nodes such that each leaf corresponds to exactly
one vertex $v\in V(G)$. Let $\mathcal{T}$ be an HC tree of a graph
$G=(V,E,w)$, and $N\in\mathcal{T}$ be an arbitrary internal node666We consider
any non-leaf node of $\mathcal{T}$ an _internal node_. We always use the term
_node(s)_ for the nodes of $\mathcal{T}$ and the term _vertices_ for the
elements of the vertex set $V$. of $\mathcal{T}$.

We denote $\mathcal{T}[N]$ to be the subtree of $\mathcal{T}$ rooted at $N$,
$\mathsf{leaves}\left(\mathcal{T}[N]\right)$ to be the set of leaf nodes of
$\mathcal{T}[N]$, and $\mathrm{parent}_{\mathcal{T}}(N)$ to be the parent of
node $N$ in $\mathcal{T}$.

In addition, each internal node $N\in\mathcal{T}$ induces a unique vertex set
$C\subseteq V$ formed by the vertices corresponding to
$\mathsf{leaves}(\mathcal{T}[N])$. For ease of presentation, we sometimes
abuse the notation and write $N\in\mathcal{T}$ for both the internal node of
$\mathcal{T}$ and the corresponding subset of vertices in $V$.

To measure the quality of an HC tree $\mathcal{T}$ with similarity weights,
Dasgupta [Das16] introduced the cost function defined by

$\mathsf{COST}_{G}(\mathcal{T})\triangleq\sum_{e=\\{u,v\\}\in
E}w_{e}\cdot\lvert\mathsf{leaves}\left(\mathcal{T}[u\vee v]\right)\rvert,$

where $u\vee v$ is the lowest common ancestor of $u$ and $v$ in $\mathcal{T}$.
Sometimes, it is convenient to consider the cost of an edge $e=\\{u,v\\}\in E$
in $\mathcal{T}$ as $\mathsf{cost}_{G}(e)\triangleq
w_{e}\cdot\lvert\mathsf{leaves}(\mathcal{T}[u\vee v])\rvert$. Trees that
achieve a better hierarchical clustering have a lower cost, and the objective
of HC is to construct trees with the lowest cost based on the following
consideration: for any pair of vertices $u,v\in V$ that corresponds to an edge
of high weight $w_{uv}$ (i.e., $u$ and $v$ are highly similar), a “good” HC
tree would separate $u$ and $v$ lower in the tree, thus reflected in a small
size of $|\mathsf{leaves}(\mathcal{T}[u\vee v])|$. We denote by
$\mathsf{OPT}_{G}$ the minimum cost of any HC tree of $G$, i.e.,
$\mathsf{OPT}_{G}=\min_{\mathcal{T}}\mathsf{COST}_{G}(\mathcal{T})$, and use
the notation $\mathcal{T}^{*}$ to refer to an _optimal_ tree achieving the
minimum cost. We say that an HC tree $\mathcal{T}$ is an _$\alpha$
-approximate_ tree if
$\mathsf{COST}_{G}(\mathcal{T})\leqslant\alpha\cdot\mathsf{OPT}_{G}$ for some
$\alpha\geqslant 1$.

###  3.3 Contracted Graphs

Our work is based on _contracted_ graphs, which were introduced by Kapralov et
al. [KKLM22] in the context of hierarchical clustering.

######  Definition 3.1 (Contracted Graph, [KKLM22]).

Let $G=(V,E,w)$ be a weighted graph, and $\mathcal{A}=\\{A\\}_{i=1}^{k}$ be a
partition of $V$. We say that the vertex and edge-weighted graph
$H=([k],\genfrac{(}{)}{0.0pt}{2}{[k]}{2},W^{*},w^{*})$ is a contraction of $G$
with respect to $\mathcal{A}$ if for every $i,j\in[k]$ we have that
$W^{*}(i,j)=w(A_{i},A_{j})$ and for every $i\in[k]$ we have
$w^{*}(i)=|A_{i}|$. We denote the contraction of $G$ with respect to
$\mathcal{A}$ as $G/\mathcal{A}$.

Note that contracted graphs are _vertex-weighted_ , i.e., every vertex $u\in
V(H)$ has a corresponding weight. To measure the quality of an HC tree
$\mathcal{T}$ on a vertex-weighted graph $H=(V,E,W,w)$, we define the
_weighted Dasgupta’s cost_ of $\mathcal{T}$ on $H$ as

$\mathsf{WCOST}_{H}(\mathcal{T})\triangleq\sum_{e=\\{u,v\\}\in
E}W(u,v)\sum_{z\in\mathsf{leaves}\left(\mathcal{T}[u\vee v]\right)}w(z).$

We denote by $\mathsf{WOPT}_{H}$ the minimum cost of any HC tree of $H$, i.e.,
$\mathsf{WOPT}_{H}=\min_{\mathcal{T}}\mathsf{WCOST}_{H}(\mathcal{T})$.

For any set $S\subset V(H)$ we define the sparsity of the cut $(S,V\setminus
S)$ in $H$ as

$\mathsf{sparsity}_{H}(S)\triangleq\frac{W(S,V\setminus S)}{w(S)\cdot
w(V\setminus S)},$ (3.2)

where $w(S)\triangleq\sum_{v\in S}w(v)$. The vertex-weighted sparsest cut of
$G$ is the cut with the minimum sparsity.

We call the vertex-weighted variant of the recursive sparsest cut algorithm
the WRSC algorithm, which is described as follows: Let $\alpha\geqslant 1$,
and $H=(V,E,W,w)$ be a vertex and edge-weighted graph. Let $(S,V\setminus S)$
be a vertex-weighted sparsest cut of $H$. The WRSC algorithm on $H$ is a
recursive algorithm that finds a cut $(T,V\setminus T)$ satisfying
$\mathsf{sparsity}_{H}(T)\leqslant\alpha\cdot\mathsf{sparsity}_{H}(S)$, and
recurs on the induced subgraphs $H[T]$ and $H[V\setminus T]$. Kapralov et al.
[KKLM22] showed that the approximation guarantee of this algorithm for
constructing HC trees follows from the one for non-vertex-weighted graphs
[CC17], and their result is summarised as follows:

######  Lemma 3.2 ([KKLM22]).

Let $H=(V,E,W,w)$ be a vertex and edge-weighted graph. Then, the WRSC
algorithm achieves an $O(\alpha)$-approximation for the weighted Dasgupta’s
cost of $H$, where $\alpha$ is the approximation ratio of the sparsest cut
algorithm used in WRSC.

We emphasise that we only use the _combinatorial_ properties of vertex-
weighted graphs. As such we don’t consider their Laplacian matrices and the
corresponding spectra.

###  3.4 Spectral Clustering

Another key component used in our analysis is spectral clustering, which is
one of the most popular clustering algorithms used in practice [NJW01, ST96].
For any input graph $G=(V,E,w)$ and $k\in\mathbb{N}$, spectral clustering
consists of the following three steps: (1) compute the eigenvectors
$f_{1}\ldots f_{k}$ of $\mathcal{L}_{G}$, and embed each $u\in V(G)$ to the
point $F(u)\in\mathbb{R}^{k}$ based on $f_{1}\ldots f_{k}$; (2) apply
$k$-means on the embedded points $\\{F(u)\\}_{u\in V(G)}$; (3) partition $V$
into $k$ clusters $P_{1}\ldots P_{k}$ based on the output of $k$-means.

To analyse the performance of spectral clustering, one can examine the
scenario in which there is a large gap between $\lambda_{k+1}$ and $\rho(k)$.
By the higher-order Cheeger inequality (3.1), we know that a low value of
$\rho(k)$ ensures that the vertex set $V$ of $G$ can be partitioned into $k$
subsets (clusters), each of which has conductance upper bounded by $\rho(k)$;
on the other hand, a high value of $\lambda_{k+1}$ implies that any
$(k+1)$-way partition of $V$ would introduce some $A\subset V$ with
conductance $\Phi_{G}(A)\geqslant\rho(k+1)\geqslant\lambda_{k+1}/2$.

Based on this observation, a sequence of works [Miz21, MS22, PSZ17] showed
that, assuming the presence of a large gap between $\lambda_{k+1}$ and
$\rho(k)$, spectral clustering returns clusters $P_{1},\ldots P_{k}$ of low
outer conductance $\Phi_{G}(P_{i})$ for each $1\leqslant i\leqslant k$. We
remark that spectral clustering can be implemented in nearly-linear time
[PSZ17].

##  4 Hierarchical Clustering for Well-Clustered Graphs: Previous Approach

Our presented new algorithms are based on the work of Manghiuc and Sun [MS21]
on the same problem, and this section gives a brief overview of their
approach. We consider a graph $G=(V,E,w)$ to have $k$ well-defined clusters if
$V(G)$ can be partitioned into disjoint subsets $\\{A_{i}\\}_{i=1}^{k}$ such
that (i) there’s a sparse cut between $A_{i}$ and $V\setminus A_{i}$,
formulated as $\Phi_{G}(A_{i})\leqslant\Phi_{\mathrm{out}}$ for any
$1\leqslant i\leqslant k$, and (ii) each $G[A_{i}]$ has high inner conductance
$\Phi_{G[A_{i}]}\geqslant\Phi_{\mathrm{in}}$. Then, for an input graph $G$
with a clear cluster-structure, the algorithm by [MS21], which we call the MS
algorithm in the following, constructs an $O(1)$-approximate HC tree of $G$ in
polynomial-time. At a very high level, the MS algorithm is based on the
following two components:

  * •

They first show that, when an input graph $G$ of $n$ vertices and $m$ edges
has high conductance, an $O(1)$-approximate HC tree of $G$ can be constructed
based on the degree sequence of $G$, and the algorithm runs in $O(m+n\log n)$
time. We use $\mathbb{T}_{\mathrm{deg}}$ to express such trees constructed
from the degree sequence of $G$.

  * •

They combine the first result with the algorithm proposed in [OGT14], which
decomposes an input graph into a set of clusters $A_{1},\ldots,A_{\ell}$,
where every $A_{i}$ has low outer-conductance $\Phi_{G}(A_{i})$ and high
inner-conductance $\Phi_{G[A_{i}]}$ for any $1\leqslant i\leqslant\ell$.

With these two components, one might intuitively think that an
$O(1)$-approximate HC tree of $G$ can be easily constructed by (i) finding
clusters $\\{A_{i}\\}$ of high conductance, (ii) constructing an
$O(1)$-approximate HC tree
$\mathbb{T}_{i}=\mathbb{T}_{\mathrm{deg}}(G[A_{i}])$ for every $G[A_{i}]$, and
(iii) merging the constructed $\\{\mathbb{T}_{i}\\}$ in an “optimal” way.
However, Manghiuc and Sun [MS21] show by counterexample that this is not
sufficient and, in order to achieve an $O(1)$-approximation, further
decomposition of every $\\{A_{i}\\}$ would be necessary. Specifically, they
adjust the algorithm of [OGT14], and further decompose every vertex set
$A_{i}$ of high-conductance into smaller subsets, which they call _critical
nodes_. They show that these critical nodes can be carefully merged to
construct an $O(1)$-approximate HC tree for well-clustered graphs. On the
downside, as the MS algorithm is heavily based [OGT14], the time complexity of
their algorithm is
$\widetilde{O}\left(k^{3}m^{2}n\cdot\left(w_{\max}/w_{\min}\right)\right)$,
which limits the application of their algorithm on large-scale datasets.

##  5 Algorithms

This section presents our hierarchical clustering algorithms for well-
clustered graphs. It consists of two subsections, each of which corresponds to
one algorithm.

###  5.1 The First Algorithm

In this subsection we present a nearly-linear time algorithm that, given a
well-clustered graph $G$ with a constant number of clusters as input,
constructs an $O(1)$-approximate HC tree of $G$ with respect to Dasgupta’s
cost. Our result is as follows:

######  Theorem 5.1.

Given a connected graph $G=(V,E,w)$ and some constant $k$ as input such that
$\lambda_{k+1}=\Omega(1)$, $\lambda_{k}=O(k^{-12})$, and
$w_{\mathrm{max}}/w_{\mathrm{min}}=O(n^{\gamma})$ for a constant $\gamma>1$,
there is a nearly-linear time algorithm that constructs an HC tree
$\mathcal{T}$ of $G$ satisfying
$\mathsf{COST}_{G}(\mathcal{T})=O\left(1\right)\cdot\mathsf{OPT}_{G}$.

In comparison to the previous algorithms for hierarchical clustering on well-
structured graphs [CAKMT17, MS21], the advantages of our algorithm are its
simplicity and nearly-linear time complexity, which is optimal up to a poly-
logarithmic factor.

####  5.1.1 Overview of the Algorithm

We first describe the algorithm behind Theorem 5.1. Our algorithm consists of
four steps. For any input graph $G=(V,E,w)$ and parameter $k$, our algorithm
first runs spectral clustering and obtains clusters $P_{1},\ldots,P_{k}$.

The second step of our algorithm is a degree-based bucketing procedure. We set
$\beta\triangleq 2^{k(\gamma+1)}$, and define for any $P_{i}$ returned from
spectral clustering and $u\in P_{i}$ the set

$B\left(u\right)\triangleq\left\\{v\in P_{i}:d_{u}\leqslant d_{v}<\beta\cdot
d_{u}\right\\}.$ (5.1)

Moreover, as $B(u)$ consists of all the vertices $v\in P_{i}$ with
$d_{u}\leqslant d_{v}<\beta\cdot d_{u}$, we generalise the definition of
$B(u)$ and define for any $j\in\mathbb{Z}$ that

$B^{j}(u)=\left\\{v\in P_{i}:\beta^{j}\cdot d_{u}\leqslant
d_{v}<\beta^{j+1}\cdot d_{u}\right\\}.$

By definition, it holds that $B(u)=B^{0}(u)$, and $\\{B^{j}(u)\\}_{j}$ forms a
partition of $P_{i}$ for any $u\in P_{i}$. We illustrate the bucketing
procedure in Figure 1. In our algorithm, we set $u^{(i)}~{}(1\leqslant
i\leqslant k)$ to be a vertex in $P_{i}$ with minimum degree and focus on
$\left\\{B^{j}\left(u^{(i)}\right)\right\\}_{j}$, the partition of $P_{i}$
which is only based on non-negative values of $j$. Let
$\mathcal{B}_{i}\triangleq\left\\{B^{j}\left(u^{(i)}\right)\right\\}_{j}$, and
$\mathcal{B}\triangleq\bigcup_{i=1}^{k}\mathcal{B}_{i}$.

$d_{u}$$d_{u}\beta$$d_{u}\beta^{-1}$$\delta_{G}(P_{i})$$d_{u}$$\Delta_{G}(P_{i})$$B(u)$

Figure 1: The illustration of our bucketing procedure induced by a vertex $u$.

In the third step, our algorithm constructs an arbitrary balanced binary tree
$\mathcal{T}_{B}$ for every bucket $B\in\mathcal{B}$, and sets $\mathbb{T}$ to
be the collection of our constructed balanced trees $\mathcal{T}_{B}$.

For the fourth step, our algorithm constructs the contracted graph $H$ defined
by $H\triangleq G\big{/}\mathcal{B}$, and applies the WRSC algorithm to
construct an HC tree $\mathcal{T}_{G/\mathcal{B}}$ of $H$. Our algorithm
finally replaces every leaf node of $\mathcal{T}_{G/\mathcal{B}}$
corresponding to a set $B\in\mathcal{B}$ by an arbitrary balanced tree
$\mathcal{T}_{B}$ on $G\left[B\right]$. See Algorithm 1 for the formal
description of our algorithm.

1

Data: $G=(V,E,w)$, $k\in\mathbb{N}$ such that $\lambda_{k+1}>0$

Result: $\mathcal{T}$

2

3$\\{P_{1},\ldots,P_{k}\\}\leftarrow\mathsf{SpectralClustering}(G,k)$

4 $\beta\leftarrow 2^{k(\gamma+1)}$

5 $\mathbb{T}\leftarrow\emptyset$

6

7for  _every $P_{i}$_ do

8 Order the vertices of $P_{i}$ increasingly with respect to their degrees

9 $u^{(i)}\leftarrow$ vertex $u\in P_{i}$ with minimum degree

10 $\mathcal{B}_{i}\leftarrow\left\\{B^{j}\left(u^{(i)}\right)\right\\}_{j}$

11

12 for  _every $B\in\mathcal{B}_{i}$ _ do

13 Construct an arbitrary balanced $\mathcal{T}_{B}$ of $G\left[B\right]$

14 $\mathbb{T}\leftarrow\mathbb{T}\cup\mathcal{T}_{B}$

15

16

17

18$\mathcal{B}=\bigcup_{i=1}^{k}\mathcal{B}_{i}$

19

20$H\leftarrow G\big{/}\mathcal{B}$

21 $\mathcal{T}\leftarrow\mathsf{WRSC}(H)$

22

23for  _every $\mathcal{T}_{B}\in\mathbb{T}$_ do

24 Replace the leaf node of $\mathcal{T}$ corresponding to $B$ by
$\mathcal{T}_{B}$

25

26

27return $\mathcal{T}$

28

Algorithm 1 Spectral Clustering with Degree Bucketing and WRSC (SpecWRSC)

It is important to notice that, as every output $P_{i}~{}(1\leqslant
i\leqslant k)$ from spectral clustering doesn’t necessarily have high inner-
conductance, our work shows that in general the inner-conductance condition of
vertex sets is not needed in order to construct an $O(1)$-approximate HC tree.
This is significant in our point of view, since ensuring the high inner-
conductance of certain vertex sets is the main reason behind the high time
complexity of the MS algorithm. Moreover, the notion of critical nodes
introduced in [MS21], which are subsets of a cluster with high conductance, is
replaced by the degree-based bucketing $\mathcal{B}$ of every output cluster
$P_{i}$ from spectral clustering; this $\mathcal{B}$ can be constructed in
nearly-linear time.

####  5.1.2 Proof Sketch of Theorem 5.1

We first analyse the approximation ratio of our constructed tree, and show why
these simple four steps suffice to construct an $O(1)$-approximate HC tree for
well-clustered graphs. By the algorithm description, our constructed
$\mathcal{T}$ is based on merging different $\mathcal{T}_{B}$, and it holds
that

$\displaystyle\mathsf{COST}_{G}\left(\mathcal{T}\right)$
$\displaystyle=\sum_{i=1}^{k}\sum_{B\in\mathcal{B}_{i}}\mathsf{COST}_{G\left[B\right]}\left(\mathcal{T}_{B}\right)+\sum_{\begin{subarray}{c}B,B^{\prime}\in\mathcal{B}\\\
B\neq B^{\prime}\end{subarray}}\sum_{\begin{subarray}{c}e=\\{u,v\\}\\\ u\in
B,v\in B^{\prime}\end{subarray}}\mathsf{cost}_{G}(e).$ (5.2)

The first step of our analysis is to upper bound the total contribution of the
internal edges of all the buckets, and our result is as follows:

######  Lemma 5.2.

It holds that

$\sum_{i=1}^{k}\sum_{B\in\mathcal{B}_{i}}\mathsf{COST}_{G[B]}\left(\mathcal{T}_{B}\right)=O\left(\beta\cdot
k^{23}/\lambda_{k+1}^{10}\right)\cdot\mathsf{OPT}_{G}.$

By Lemma 5.2, the total cost induced from the edges inside every bucket can be
_directly_ used when constructing the final tree $\mathcal{T}$. This is
crucial for our analysis since our defined buckets can be constructed in
nearly-linear time. In comparison to this step, the MS algorithm relies on
finding critical nodes, which is computationally much more expensive.

Next, we analyse the second term of (5.2). For ease of presentation, let
$\widetilde{E}$ be the set of edges crossing different buckets, and
$\mathcal{T}_{G/\mathcal{B}}$ the tree returned from the WRSC algorithm;
remember that every leaf of $\mathcal{T}_{G/\mathcal{B}}$ corresponds to a
vertex set in $\mathcal{B}$. By construction, we know that the weight of every
edge $e\in\widetilde{E}$ contributes to the edge weight in $G/\mathcal{B}$,
and it holds that

$\sum_{e\in\widetilde{E}}\mathsf{cost}_{G}(e)=\mathsf{WCOST}_{G/\mathcal{B}}(\mathcal{T}_{G/\mathcal{B}}).$
(5.3)

Moreover, since $\mathcal{T}_{G\setminus\mathcal{B}}$ is constructed by
performing the WRSC algorithm on $G\setminus\mathcal{B}$, we have by Lemma 3.2
that

$\mathsf{WCOST}_{G/\mathcal{B}}(\mathcal{T}_{G/\mathcal{B}})=O\left(\alpha\right)\cdot\mathsf{WOPT}_{G/\mathcal{B}},$
(5.4)

where $\alpha$ is the approximation ratio achieved by the WRSC algorithm.

Our next lemma is the key to the overall analysis, and upper bounds
$\mathsf{WOPT}_{G/\mathcal{B}}$ with respect to $\mathsf{OPT}_{G}$.

######  Lemma 5.3.

It holds that

$\mathsf{WOPT}_{G/\mathcal{B}}=O\left(\beta\cdot
k^{23}/\lambda_{k+1}^{10}\right)\cdot\mathsf{OPT}_{G}.$

Combining (5.3), (5.4) with Lemma 5.3, we have

$\sum_{e\in\widetilde{E}}\mathsf{cost}_{G}(e)=O\left(\alpha\cdot\beta\cdot
k^{23}/\lambda_{k+1}^{10}\right)\cdot\mathsf{OPT}_{G}.$ (5.5)

Next, we study $\alpha$, which is the only term in the approximation ratio of
(5.5) that is not necessarily a constant. Recall that our choice of $\gamma$
and $\beta$ satisfies

$\frac{w_{\max}}{w_{\min}}=O(n^{\gamma})$

and $\beta=2^{k(\gamma+1)}$. Hence, it holds that

$\frac{\Delta_{G}}{\delta_{G}}=O\left(n^{\gamma+1}\right),$

and the total number of buckets in $\mathcal{B}$ is upper bounded by

$k\cdot\max\\{1,\log_{\beta}n^{\gamma+1}\\}\leqslant
k+\frac{k(\gamma+1)}{\log\beta}\cdot\log n=k+\log n.$

Thanks to this, there are at most $k+\log n$ vertices in $G/\mathcal{B}$, and
a sparsest cut of $G/\mathcal{B}$ can be found in $O(n)$ time by enumerating
all of its possible subsets; as such we can set $\alpha=1$ in the analysis. We
highlight that this is another advantage of our bucketing step: with careful
choice of parameters, we only need to study a contracted graph with $O(\log
n)$ vertices, whose sparsest cut can be found in linear time. Since the WRSC
algorithm only computes the vertex-weighted sparsest cut $O(\log n)$ times,
the overall running time of WRSC is $O(n\cdot\log n)$. We remark that we don’t
need to deal with the general sparsest cut problem, for which most
approximation algorithms are based on complicated optimisation techniques
(e.g., [ARV09]).

Combining (5.2) with Lemmas 5.2, 5.3 as well as the fact that $\alpha=1$
proves the approximation guarantee of Theorem 5.1.

Next, we sketch the running time analysis of Algorithm 1. The first step (Line
1) applies spectral clustering, and takes $\widetilde{O}(m)$ time [PSZ17]. The
second step (Lines 1–1) is a degree-based bucketing procedure for all the
clusters, the time complexity of which is

$\sum_{i=1}^{k}O\left(|P_{i}|\log|P_{i}|\right)=O(n\log n).$

The third step (Lines 1–1) of the algorithm constructs an arbitrary binary
tree $\mathcal{T}_{B}$ for every bucket $B\in\mathcal{B}$, and we show that
this step takes $\widetilde{O}(m)$ time. The actual construction of the trees
in this step isn’t difficult, but we need to store several attributes for each
internal node as we build the tree, such that we can compute Dasgupta’s cost
in nearly-linear time as well. We refer the reader to the appendix for the
detailed discussion of this step. In the last step (Lines 1–1), the algorithm
merges the trees $\mathcal{T}_{B}$ based on the output of WRSC, which can be
implemented in $O(n\log n)$ time as discussed above. Combining all these steps
gives us the nearly-linear time complexity of Algorithm 1.

####  5.1.3 Proof Sketch of Lemma 5.2 and Lemma 5.3

Our key approach to breaking the running time barrier of [MS21] is that,
instead of approximating the optimal tree $\mathcal{T}^{*}$, we approximate
the tree $\mathcal{T}_{\textsf{MS}}$ constructed by the algorithm of [MS21].
We know from their result that one can upper bound the cost of
$\mathcal{T}_{\mathsf{MS}}$ with respect to $\mathsf{OPT}_{G}$, i.e.,

$\mathsf{COST}_{G}(\mathcal{T}_{\mathsf{MS}})=O\left(k^{22}/\lambda_{k+1}^{10}\right)\cdot\mathsf{OPT}_{G}.$

We take the existence of the tree $\mathcal{T}_{\mathsf{MS}}$ for granted, and
perform two transformations to construct a tree
$\mathcal{T}_{\mathsf{MS}}^{\prime\prime}$, while ensuring that the total
introduced cost from the two transformations can be upper bounded. In the
first step, we identify how every bucket $B\in\mathcal{B}$ is spread
throughout $\mathcal{T}_{\mathsf{MS}}$, and make sure that all the separate
components that make up $B$ are isolated in our new tree. We call the
resulting tree $\mathcal{T}_{\mathsf{MS}}^{\prime}$, and prove that

$\mathsf{COST}_{G}\left(\mathcal{T}_{\mathsf{MS}}^{\prime}\right)\leqslant\mathsf{COST}_{G}\left(\mathcal{T}_{\mathsf{MS}}\right)+O(k^{21}/\lambda_{k+1}^{10})\cdot\mathsf{OPT}_{G}.$

For the second transformation, we carefully adjust the tree
$\mathcal{T}_{\mathsf{MS}}^{\prime}$, such that the currently isolated
components that make up every bucket $B\in\mathcal{B}$ get grouped together
into the same subtree. We call the resulting tree
$\mathcal{T}_{\mathsf{MS}}^{\prime\prime}$, and bound its cost by

$\mathsf{COST}_{G}\left(\mathcal{T}_{\mathsf{MS}}^{\prime\prime}\right)\leqslant\mathsf{COST}_{G}\left(\mathcal{T}_{\mathsf{MS}}^{\prime}\right)+O(\beta\cdot
k^{23}/\lambda_{k+1}^{10})\cdot\mathsf{OPT}_{G}.$

Taking these transformations together, we get that

$\mathsf{COST}_{G}\left(\mathcal{T}_{\mathsf{MS}}^{\prime\prime}\right)\leqslant
O(\beta\cdot k^{23}/\lambda_{k+1}^{10})\cdot\mathsf{OPT}_{G}.$ (5.6)

Notice that we can perform these two transformations without an explicit
construction of $\mathcal{T}_{\mathsf{MS}}$, but we still end up with a tree
$\mathcal{T}_{\mathsf{MS}}^{\prime\prime}$ with bounded Dasgupta cost.
Moreover, since every bucket $B\in\mathcal{B}$ in
$\mathcal{T}_{\textsf{MS}}^{\prime\prime}$ is separated,
$\mathcal{T}_{\mathsf{MS}}^{\prime\prime}$ is also a tree on the contracted
graph $G/\mathcal{B}$; this allows us to upper bound
$\mathsf{WOPT}_{G/\mathcal{B}}$ with
$\mathsf{COST}_{G}(\mathcal{T}_{\mathsf{MS}}^{\prime\prime})$. Combining this
with (5.6) proves Lemma 5.3. With the same approach, we prove that Lemma 5.2
holds as well.

We remark that this is another conceptual contribution of our paper: although
[MS21] shows that a similar proof technique can be generalised to construct
$O(1)$-approximate HC trees for _expander_ graphs, we show that such proof
technique can be used to obtain $O(1)$-approximate HC trees for _well-
clustered_ graphs.

###  5.2 The Second Algorithm

In this subsection, we present another nearly-linear time hierarchical
clustering algorithm for well-clustered graphs. Here, we assume that the
degrees of vertices inside every cluster are _almost balanced_ , i.e., it
holds for an optimal partitioning $S_{1},\ldots S_{k}$ corresponding to
$\rho(k)$ that the degrees inside each $S_{i}$ are upper bounded by a
parameter $\eta_{S}\in\mathbb{R}^{+}$. With this condition, our second
algorithm achieves the same approximation guarantee as Algorithm 1 even with
$k=O(\log^{c}n)$ for some constant $c$. This result is summarised as follows:

######  Theorem 5.4.

Let $G=(V,E,w)$ be a graph with $k$ clusters $\\{S_{i}\\}_{i=1}^{k}$ such that
$\lambda_{k+1}=\Omega(1)$,
$\max_{i}(\Delta_{G}(S_{i})/\delta_{G}(S_{i}))\leqslant\eta_{S}$,
$\rho(k)\leqslant k^{-4}$, and $\Phi_{G[S_{i}]}\geqslant\Omega(1)$ for
$1\leqslant i\leqslant k$. Then, there is a nearly-linear time algorithm that
constructs an HC tree $\mathcal{T}_{\mathrm{SCB}}$ of $G$ satisfying
$\mathsf{COST}_{G}(\mathcal{T}_{\mathrm{SCB}})=O\left(1\right)\cdot\mathsf{OPT}_{G}$.

The algorithm behind Theorem 5.4 is similar with Algorithm 1, and is described
in Algorithm 2. However, our second algorithm has two significant changes
compared with Algorithm 1.

  1. 1.

We adjust the bucketing step by setting the bucketing parameter
$\beta=\eta_{S}$, where $\eta_{S}$ is an upper bound for
$\max_{i}\left(\Delta_{G}(S_{i})/\delta_{G}(S_{i})\right)$. Moreover, instead
of bucketing the vertices starting at the vertex $u^{(1)}$ of minimum degree
inside $P_{i}$, we carefully choose for each $P_{i}$ the vertex
$u_{i}^{*}\triangleq\operatorname{argmax}_{u\in
P_{i}}\mathrm{vol}\\!\left(\\!\,B\left(u\right)\,\\!\right)$ whose induced
bucket $B\left(u_{i}^{*}\right)$ has the highest volume inside $P_{i}$. Based
on this, we set
$\mathcal{B}_{u_{i}^{*}}\triangleq\left\\{B^{j}\left(u_{i}^{*}\right)\right\\}_{j}$
and $\mathcal{B}\triangleq\bigcup_{i=1}^{k}\mathcal{B}_{u_{i}^{*}}$.

  2. 2.

After constructing the balanced trees $\mathcal{T}_{B}$ for every
$B\in\mathcal{B}$, instead of applying WRSC, we concatenate the trees
$\mathcal{T}_{B}$ in a simple “caterpillar” style according to the sizes $|B|$
of the buckets $B\in\mathcal{B}$.

1

Data: $G=(V,E,w)$, $k\in\mathbb{N}$, $\eta_{S}\in\mathbb{R}^{+}$

Result: $\mathcal{T}_{\mathrm{SCB}}$

2

3$P=\\{P_{1},\ldots,P_{k}\\}\leftarrow\mathsf{SpectralClustering}(G,k)$

4 $\beta\leftarrow\eta_{S}$

5 Initialize $\mathbb{T}\leftarrow\emptyset$

6

7for  _$P_{i}\in P$_ do

8 Order the vertices of $P_{i}$ increasingly with respect to their degrees

9 $B\left(u\right)\leftarrow\left\\{v\in P_{i}:d_{u}\leqslant d_{v}<\beta\cdot
d_{u}\right\\}$

10 $u_{i}^{*}\leftarrow\operatorname{argmax}_{u\in P_{i}}\mathrm{vol}(B(u))$

11
$\mathcal{B}_{u_{i}^{*}}\leftarrow\left\\{B^{j}\left(u_{i}^{*}\right)\right\\}_{j}$

12

13 for  _$B\in\mathcal{B}_{u_{i}^{*}}$_ do

14 Let $\mathcal{T}_{B}$ be any balanced HC tree on $G[B]$

15 $\mathbb{T}\leftarrow\mathbb{T}\cup\mathcal{T}_{B}$

16

17

18

19Let $\mathbb{T}=\\{\mathcal{T}_{1},\dots,\mathcal{T}_{|\mathbb{T}|}\\}$ be
such that $|\mathcal{T}_{i}|\leqslant|\mathcal{T}_{i+1}|$, for all $1\leqslant
i<|\mathbb{T}|$

20

21Initialize $\mathcal{T}_{\mathrm{SCB}}\leftarrow\mathcal{T}_{1}$

22

23for  _ $i\leftarrow 2,\dots,|\mathbb{T}|$_ do

24
$\mathcal{T}_{\mathrm{SCB}}\leftarrow\mathcal{T}_{\mathrm{SCB}}\vee\mathcal{T}_{i}$

25

26

27return $\mathcal{T}_{\mathrm{SCB}}$

28

Algorithm 2 Spectral Clustering with Degree Bucketing and Caterpillar
Construction

To explain the first change, notice that every cluster $P_{i}$ returned by
spectral clustering has a large overlap with its corresponding optimal cluster
$S_{i}$. Moreover, the degrees of the vertices inside $S_{i}$ are within a
factor of $\eta_{S}$ of each other. Therefore, if an arbitrary vertex $u\in
P_{i}$ is chosen as representative, the bucketing $B\left(u\right)$ of $P_{i}$
might equally divide the vertices in $P_{i}\cap S_{i}$ into two consecutive
buckets, which is undesirable due to the high induced cost of the crossing
edges. To circumvent this issue, we choose $u_{i}^{*}$ as the vertex to induce
the bucketing and prove that this specific choice of $u_{i}^{*}$ guarantees
that the bucketing $\mathcal{B}_{u_{i}^{*}}$ contains one bucket
$B\in\mathcal{B}_{u_{i}^{*}}$ largely overlapping with $S_{i}$. This greatly
reduces the number of crossing edges in our constructed HC tree and hence
improves the approximation guarantee.

To explain the second change, we notice that the nearly-linear running time of
WRSC relies on the condition that $k=O(1)$, which might not hold necessarily
for the new setting. We prove that, as long as
$\max_{i}\left(\Delta_{G}(S_{i})/\delta_{G}(S_{i})\right)$ is upper bounded by
a constant, it is sufficient to construct a caterpillar tree based on the
sizes $|B|$ of the buckets $B\in\mathcal{B}$. We prove that our algorithm runs
in nearly-linear time, and the output tree achieves $O(1)$-approximation. See
the appendix for the detailed analysis of Algorithm 2 and the proof of Theorem
5.4

##  6 Experiments

We experimentally evaluate the performance of our designed SpecWRSC algorithm,
and compare it against the previous state-of-the-art and a well-known linkage
algorithm. Specifically, the SpecWRSC algorithm is compared against the
following three algorithms:

  1. 1.

the Linkage$++$ algorithm proposed in [CAKMT17];

  2. 2.

the MS algorithm proposed in [MS21];

  3. 3.

the AverageLinkage algorithm.

Even though there are no theoretical approximation guarantees of
AverageLinkage with respect to Dasgupta’s cost function, we include it in our
evaluation for reference due to its excellent performance in practice.

All the tested algorithms were implemented in Python 3.9 and experiments were
performed using a Lenovo ThinkPad T15G, with an Intel(R) Xeon(R) W-10855M
<EMAIL_ADDRESS>processor and 126 GB RAM. All of the reported costs and running
time below are averaged over $5$ independent runs. Our code can be downloaded
from https://github.com/steinarlaenen/nearly-optimal-hierarchical-clustering-
for-well-clustered-graphs.

###  6.1 Results on Synthetic Data

We first compare the performance of our algorithm against the others described
before on synthetic data.

####  6.1.1 Stochastic Block Model

We look at graphs generated according to the standard Stochastic Block Model
(SBM). We set the number of clusters as $k=5$, and the number of vertices in
each cluster $\\{P_{i}\\}_{i=1}^{5}$ as $n_{k}$. For each pair of vertices
$u\in P_{i}$ and $v\in P_{j}$, we add an edge $\\{u,v\\}$ with probability $p$
if $i=j$, and add an edge with probability $q$ if $i\neq j$.

To compare the running time, we incrementally increase the number of vertices
in each cluster $\\{P_{i}\\}_{i=1}^{5}$ from $n_{k}=100$ to $n_{k}=3{,}000$,
in increments of 200, and we fix $p=0.1$ and $q=0.002$. For each algorithm, we
measure the running time in seconds, and the results are plotted in Figure
2(a), confirming our algorithm’s low time complexity compared with our
competitors. To further highlight the fast running time of our algorithm, we
increase the size of each cluster to $20{,}000$, which results in the total
number of nodes $n=100{,}000$. We find that SpecWRSC returns an HC tree in
$14{,}437$ seconds ($\sim 4$ hours), while all the other algorithms timeout
after 12 hours of compute time.

To compare the quality of the constructed HC trees on SBMs, we fix the number
of vertices inside each cluster $\\{P_{i}\\}_{i=1}^{5}$ as $n_{k}=1{,}000$,
the value $q=0.002$, and consider different values of $p\in[0.06,0.2]$. As
shown in Figure 2(b), SpecWRSC performs better than all the other algorithms.

(a)

(b)

Figure 2: Results for SBMs. In Figure (a) the $x$-axis represents the number
of vertices inside each cluster, and the $y$-axis represents the algorithms’
running time in seconds. In Figure (b), the $x$-axis represents different
values of $p$, while the $y$-axis represents the cost of the algorithms’
returned HC trees normalised by the cost of SpecWRSC.

####  6.1.2 Hierarchical Stochastic Block Model

Next, we consider graphs generated according to a hierarchical stochastic
block model (HSBM) [CAKMTM19]. HSBM is similar to the SBM but assumes the
existence of a hierarchical structure between the clusters. We set the number
of vertices in each cluster $\\{P_{i}\\}_{i=1}^{5}$ as $n_{k}=600$. For each
pair of vertices $u\in P_{i}$ and $v\in P_{j}$, we assume that $u$ and $v$ are
connected by an edge with probability $p$ if $i=j$; otherwise $u$ and $v$ are
connected by an edge with probability $q_{i,j}$ defined as follows: (i) for
all $i\in\\{1,2,3\\}$ and $j\in\\{4,5\\},q_{i,j}=q_{j,i}=q_{\mathrm{min}}$;
(ii) for $i\in\\{1,2\\}$, $q_{i,3}=q_{3,i}=2\cdot q_{\mathrm{min}}$; (iii)
$q_{4,5}=q_{5,4}=2\cdot q_{\mathrm{min}}$; (iv) $q_{1,2}=q_{2,1}=3\cdot
q_{\mathrm{min}}$. We fix the value $q_{\mathrm{min}}=0.0005$ and consider
different values of $p\in[0.04,0.2]$. This choice of hyperparameters bears
similarity with the setting tested in [CAKMT17, MS21]. The result of our
experiments is plotted in Figure 3(a). Again, we find that our algorithm
outperforms MS and Linkage$++$, and has similar performance as AverageLinkage.

###  6.2 Result on Real-World Data

To evaluate the performance of our algorithm on real-world datasets, we first
follow the sequence of recent work on hierarchical clustering [ACAH19,
CAKMT17, MRS+19, MS21, RP17], all of which are based on the following 4
datasets from the Scikit-learn library [PVG+11] and the UCI ML repository
[DG17]: Iris (Ir), Wine (Wi), Cancer (Ca), and Newsgroup (Ng)777Due to the
large size of NewsGroup, we consider only a subset consisting of
“comp.graphics”, “comp.os.ms-windows.misc”, “comp.sys.ibm.pc.hardware”,
“comp.sys.mac.hardware”, “rec.sport.baseball”, and “rec.sport.hockey”.. For
each dataset, we construct the similarity graph based on the Gaussian kernel,
in which the $\sigma$-value is chosen according to the standard heuristic
[NJW01]. The setup of parameters for each dataset is listed in Table 1.

The cost of the HC trees returned by each algorithm is reported in Figure
3(b), and the figure shows that our algorithm performs better than MS and
Linkage$++$ and matches the performance of AverageLinkage. We further report
the running time of the tested algorithms in Table 1, and this shows that
SpecWRSC has the lowest running time among the four tested algorithms.
Moreover, we observe that SpecWRSC performs better when the spectral gap
$\lambda_{k+1}/\lambda_{k}$ is large, which is in line with our theoretical
analysis.

| Ir | Wi | Ca | Ng
---|---|---|---|---
Parameters |  |  |  |
$n$ | $50$ | $180$ | $558$ | $3{,}516$
$k$ | $3$ | $5$ | $5$ | $5$
$\sigma$ | $0.3$ | $0.88$ | $0.88$ | $130$
$\lambda_{k+1}/\lambda_{k}$ | 5.27 | 4.96 | 1.45 | 1.01
Running Time |  |  |  |
AvgLinkage | $0.14$ | $0.22$ | $2.49$ | $198.34$
MS | $0.88$ | $2.00$ | $20.36$ | $1{,}088.87$
Linkage++ | $0.61$ | $0.90$ | $9.18$ | $944.05$
SpecWRSC | $\mathbf{0.136}$ | $\mathbf{0.16}$ | $\mathbf{1.69}$ | $\mathbf{128.17}$
Table 1: Setup of the parameters for the tested real-world datasets, and the
running time of the tested algorithms. For each dataset, we list the number of
nodes $n$, the number of clusters $k$, the $\sigma$-value used to construct
the similarity graph based on the Gaussian kernel, and the spectral gap
$\lambda_{k+1}/\lambda_{k}$ of the constructed normalised Laplacian. The
running time is reported in seconds, and the lowest one is highlighted.

To further demonstrate the effectiveness of our algorithm on larger real-world
datasets, we evaluate our algorithm on the GEMSEC Facebook dataset [RDSS19].
This dataset represents a page-page graph of verified Facebook pages, in which
every vertex represents an official Facebook page, and every edge represents
the mutual likes between pages. We focus on the largest subset of this
dataset, i.e., the artist category. This graph contains $50{,}515$ nodes and
$819{,}306$ edges. Out of all the tested algorithms, SpecWRSC is the only one
that terminates within 12 hours of compute time. Setting $k=20$, SpecWRSC
returns a tree in $1{,}223$ seconds, with a Dasgupta cost of $1.62\cdot
10^{10}$.

(a)

(b)

Figure 3: (a) Results for HSBMs, and (b) results on the real-world datasets.
In Figure (a) the $x$-axis represents different values of $p$, while the
$y$-axis represents the cost of the algorithms’ returned HC trees normalised
by the cost of SpecWRSC. In Figure (b) the $x$-axis represents the different
real-world datasets we evaluate on.

These experimental results together demonstrate that our designed algorithm
not only has excellent running time but also constructs hierarchical
clustering with a cost lower than or similar to the ones constructed by the
previous algorithms.

## References

  * [AAV20] Noga Alon, Yossi Azar, and Danny Vainstein.  Hierarchical clustering: a 0.585 revenue approximation.  In 33rd Annual Conference on Learning Theory (COLT’20), pages 153–162, 2020.
  * [ACAH19] Amir Abboud, Vincent Cohen-Addad, and Hussein Houdrouge.  Subquadratic high-dimensional hierarchical clustering.  In Advances in Neural Information Processing Systems 33 (NeurIPS’19), pages 11576–11586, 2019.
  * [Alo86] N. Alon.  Eigenvalues and expanders.  Combinatorica, 6(2):83–96, 1986.
  * [ARV09] Sanjeev Arora, Satish Rao, and Umesh Vazirani.  Expander flows, geometric embeddings and graph partitioning.  Journal of the ACM, 56(2):1–37, 2009.
  * [BKV+81] Manuel Blum, Richard M. Karp, Oliver Vornberger, Christos H Papadimitriu, and Mihalis Yannakakis.  The complexity of testing whether a graph is a superconcentrator.  Information Processing Letters, 13(4-5):164–167, 1981.
  * [CAKMT17] Vincent Cohen-Addad, Varun Kanade, and Frederik Mallmann-Trenn.  Hierarchical clustering beyond the worst-case.  In Advances in Neural Information Processing Systems 31 (NeurIPS’17), pages 6201–6209, 2017.
  * [CAKMTM19] Vincent Cohen-Addad, Varun Kanade, Frederik Mallmann-Trenn, and Claire Mathieu.  Hierarchical clustering: Objective functions and algorithms.  Journal of the ACM, 66(4):1–42, 2019.
  * [CC17] Moses Charikar and Vaggos Chatziafratis.  Approximate hierarchical clustering via sparsest cut and spreading metrics.  In 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’17), pages 841–854, 2017.
  * [CCN19] Moses Charikar, Vaggos Chatziafratis, and Rad Niazadeh.  Hierarchical clustering better than average-linkage.  In 30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’19), pages 2291–2304, 2019.
  * [Chu97] Fan R. K. Chung.  Spectral Graph Theory.  American Mathematical Society, 1997.
  * [CYL+20] Vaggos Chatziafratis, Grigory Yaroslavtsev, Euiwoong Lee, Konstantin Makarychev, Sara Ahmadian, Alessandro Epasto, and Mohammad Mahdian.  Bisect and conquer: Hierarchical clustering via max-uncut bisection.  In 23rd International Conference on Artificial Intelligence and Statistics (AISTATS’20), pages 3121–3132, 2020.
  * [Das16] Sanjoy Dasgupta.  A cost function for similarity-based hierarchical clustering.  In 48th Annual ACM Symposium on Theory of Computing (STOC’16), pages 118–127, 2016.
  * [DG17] Dheeru Dua and Casey Graff.  UCI machine learning repository, 2017.
  * [KKLM22] Michael Kapralov, Akash Kumar, Silvio Lattanzi, and Aida Mousavifar.  Learning hierarchical structure of clusterable graphs.  Arxiv, 2207.02581, 2022.
  * [LOGT14] James R Lee, Shayan Oveis Gharan, and Luca Trevisan.  Multiway spectral partitioning and higher-order Cheeger inequalities.  Journal of the ACM, 61(6):1–30, 2014.
  * [McS01] Frank McSherry.  Spectral partitioning of random graphs.  In 42nd Annual IEEE Symposium on Foundations of Computer Science (FOCS’01), pages 529–537, 2001.
  * [Miz21] Tomohiko Mizutani.  Improved analysis of spectral algorithm for clustering.  Optimization Letters, 15(4):1303–1325, 2021.
  * [MRS+19] Aditya Krishna Menon, Anand Rajagopalan, Baris Sumengen, Gui Citovsky, Qin Cao, and Sanjiv Kumar.  Online hierarchical clustering approximations.  Arxiv, :1909.09667, 2019.
  * [MS21] Bogdan-Adrian Manghiuc and He Sun.  Hierarchical Clustering: O(1)-Approximation for Well-Clustered Graphs.  In Advances in Neural Information Processing Systems 35 (NeurIPS’21), pages 9278–9289, 2021.
  * [MS22] Peter Macgregor and He Sun.  A tighter analysis of spectral clustering, and beyond.  In 39th International Conference on Machine Learning (ICML’22), pages 14717–14742, 2022.
  * [MW17] Benjamin Moseley and Joshua Wang.  Approximation bounds for hierarchical clustering: Average linkage, bisecting $k$-means, and local search.  In Advances in Neural Information Processing Systems 31 (NeurIPS’17), pages 3094–3103, 2017.
  * [NJW01] Andrew Y. Ng, Michael I. Jordan, and Yair Weiss.  On spectral clustering: Analysis and an algorithm.  In Advances in Neural Information Processing Systems 15 (NeurIPS’01), pages 849–856, 2001.
  * [OGT14] Shayan Oveis Gharan and Luca Trevisan.  Partitioning into expanders.  In 25th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’14), pages 1256–1266, 2014.
  * [PSZ17] Richard Peng, He Sun, and Luca Zanetti.  Partitioning Well-Clustered Graphs: Spectral Clustering Works!  SIAM Journal on Computing, 46(2):710–743, 2017.
  * [PVG+11] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, J. Vanderplas, A. Passos, D. Cournapeau, M. Brucher, M. Perrot, and E. Duchesnay.  Scikit-learn: Machine learning in Python.  Journal of Machine Learning Research, 12:2825–2830, 2011.
  * [RDSS19] Benedek Rozemberczki, Ryan Davies, Rik Sarkar, and Charles Sutton.  Gemsec: Graph embedding with self clustering.  In 2019 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, pages 65–72, 2019.
  * [RP17] Aurko Roy and Sebastian Pokutta.  Hierarchical clustering via spreading metrics.  The Journal of Machine Learning Research, 18(1):3077–3111, 2017\.
  * [ST96] Daniel A. Spielman and Shang-Hua Teng.  Spectral partitioning works: Planar graphs and finite element meshes.  In 37th Annual IEEE Symposium on Foundations of Computer Science (FOCS’96), pages 96–105, 1996.

##  Appendix A Additional Background

In this section we list additional background notion and facts used in our
analysis, and the section is organised as follows: In Section A.1 we introduce
additional background on hierarchical clustering. In Section A.2 we provide a
more detailed discussion on spectral clustering, and finally in Section A.3 we
present and prove a new decomposition lemma of well-clustered graphs.

###  A.1 Hierarchical Clustering

We first examine the upper and lower bounds of the cost of HC trees. The first
fact holds trivially by the fact that every edge’s contribution towards the
cost function is at most $n$.

######  Fact A.1.

It holds for any HC tree $\mathcal{T}$ of $G$ that

$\mathsf{COST}_{G}(\mathcal{T})\leqslant\frac{n\cdot\mathrm{vol}\\!\left(\\!\,G\,\\!\right)}{2}.$

Secondly, it is known that $\mathsf{OPT}_{G}$ can be lower bounded with
respect to the degree distribution of $G$.

######  Lemma A.1 ([MS21]).

It holds for any graph $G$ that

$\mathsf{OPT}_{G}\geqslant\frac{2\Phi_{G}}{9}\cdot\max\left\\{\frac{\mathrm{vol}(G)^{2}}{\Delta_{G}},\delta_{G}\cdot
n^{2}\right\\}=\frac{2\Phi_{G}}{9}\cdot
n\cdot\mathrm{vol}(G)\cdot\max\left\\{\frac{d_{G}}{\Delta_{G}},\frac{\delta_{G}}{d_{G}}\right\\}.$

Next, we introduce the notion of a _dense branch_ , which is a useful tool to
analyse the cost of HC trees.

######  Definition A.2 (Dense branch, [MS21]).

Given a graph $G$ with an HC tree $\mathcal{T}$, the _dense branch_ is the
path $(A_{0},A_{1},\dots,A_{k})$ in $\mathcal{T}$ for some
$k\in\mathbb{Z}_{\geqslant 0}$, such that the following hold:

  1. 1.

$A_{0}$ is the root of $\mathcal{T}$;

  2. 2.

$A_{k}$ is the node such that $\mathrm{vol}(A_{k})>\mathrm{vol}(G)/2$ and both
of its children have volume at most $\mathrm{vol}(G)/2$.

It is important to note that the dense branch of $\mathcal{T}$ is unique, and
consists of all the nodes $A_{i}$ with
$\mathrm{vol}(A_{i})>\mathrm{vol}(G)/2$. Moreover, for every pair of
consecutive nodes $A_{i},A_{i+1}$ on the dense branch, $A_{i+1}$ is the child
of $A_{i}$ of the _higher_ volume.

The next lemma presents a lower bound on the cost of a tree $\mathcal{T}$
using the dense branch, which will be extensively used in our analysis.

######  Lemma A.3 (Lower bound of $\mathsf{COST}_{G}(\mathcal{T})$ based on
the dense branch, [MS21]).

Let $G$ be a graph of conductance $\Phi_{G}$, and $\mathcal{T}$ an arbitrary
HC tree of $G$. Suppose $(A_{0},\dots,A_{k})$ is the dense branch of
$\mathcal{T}$ for some $k\in\mathbb{Z}_{\geqslant 0}$, and suppose each node
$A_{i}$ has sibling $B_{i}$, for all $1\leqslant i\leqslant k$. Then, the
following lower bounds of $\mathsf{COST}_{G}(\mathcal{T})$ hold:

  1. 1.

$\mathsf{COST}_{G}(\mathcal{T})\geqslant\frac{\Phi_{G}}{2}\sum_{i=1}^{k}|A_{i-1}|\cdot\mathrm{vol}(B_{i})$;

  2. 2.

$\mathsf{COST}_{G}(\mathcal{T})\geqslant\frac{\Phi_{G}}{2}\cdot|A_{k}|\cdot\mathrm{vol}(A_{k})$.

One of the two main results from [MS21] is an $O(1)$-approximation on
Dasgupta’s cost for expander graphs. Their result is stated in the following
theorem.

######  Theorem A.4 ([MS21]).

Given any graph $G=(V,E,w)$ with conductance $\Phi_{G}$ as input, there is an
algorithm that runs in $O(m+n\log n)$ time, and returns an HC tree
$\mathbb{T}_{\mathrm{deg}}(G)$ of $G$ that satisfies
$\mathsf{COST}_{G}(\mathbb{T}_{\mathrm{deg}})=O\left(1/\Phi_{G}^{4}\right)\cdot\mathsf{OPT}_{G}$.

Throughout our discussion, we always use $\mathbb{T}_{\mathrm{deg}}(G)$ to
represent the HC tree of $G$ that is constructed from Theorem A.4, i.e., the
tree constructed based on the degree sequence of $G$. In particular, for any
partition $\\{C_{1},\ldots,C_{\ell}\\}$, one can apply Theorem A.4 to every
induced graph $G[C_{i}]$ for any $1\leqslant i\leqslant\ell$, and for
simplicity we write
$\mathbb{T}_{i}\triangleq\mathbb{T}_{\mathrm{deg}}(G[C_{i}])$ in the following
discussion. We next define critical nodes with respect to every
$\mathbb{T}_{i}$.

######  Definition A.5 (Critical nodes, [MS21]).

Let $\mathbb{T}_{i}=\mathbb{T}_{\mathrm{deg}}(G[C_{i}])$ be defined as above
for any non-empty subset $C_{i}\subset V$. Suppose $(A_{0},\dots,A_{r_{i}})$
is the dense branch of $\mathbb{T}_{i}$ for some $r_{i}\in\mathbb{Z}_{+}$,
$B_{j}$ is the sibling of $A_{j}$, and let $A_{r_{i}+1},B_{r_{i}+1}$ be the
two children of $A_{r_{i}}$. We define
$\mathcal{S}_{i}\triangleq\\{B_{1},\dots,B_{r_{i}+1},A_{r_{i}+1}\\}$ to be the
set of _critical nodes_ of $C_{i}$. Each node $N\in\mathcal{S}_{i}$ is a
_critical node_.

We remark that each critical node $N\in\mathcal{S}_{i}~{}(1\leqslant
i\leqslant\ell)$ is an internal node of maximum size in $\mathbb{T}_{i}$ that
is not in the dense branch. Moreover, every $\mathcal{S}_{i}$ is a partition
of $C_{i}$.

The following lemma lists some facts of the critical nodes of the trees
constructed from Theorem A.4.

######  Lemma A.6 ([MS21]).

Let $\mathcal{S}_{i}=\\{B_{1},\dots,B_{r_{i}+1},A_{r_{i}+1}\\}$ be the set of
critical nodes of $\mathbb{T}_{i}$. Then the following statements hold:

  1. (Q1)

$|B_{j}|=2\cdot|B_{j+1}|$ for all $j\geqslant 2$,

  2. (Q2)

$\mathrm{vol}_{G[C_{i}]}(B_{j})\leqslant
2\cdot\mathrm{vol}_{G[C_{i}]}(B_{j+1})$ for all $j\geqslant 1$,

  3. (Q3)

$|A_{i_{\max}}|=|B_{i_{\max}}|$.

For convenience in our notation, we also define a _critical sibling_ node of
critical nodes.

######  Definition A.7 (Critical Sibling Node).

Let $\mathcal{S}_{i}=\\{B_{1},\dots,B_{r_{i}+1},A_{r_{i}+1}\\}$ be the set of
critical nodes of $\mathbb{T}_{i}$. We define a _sibling node_ of a critical
node $B_{j}$ as $\mathrm{sib}_{\mathbb{T}_{i}}(B_{j})\triangleq B_{j+1}$ for
$1\leqslant j\leqslant r_{i}$, and
$\mathrm{sib}_{\mathbb{T}_{i}}(B_{r_{i}+1})\triangleq A_{r_{i}+1}$ otherwise.

We remark that the only critical node without a sibling is $A_{r_{i}+1}$.
Furthermore, due to the degree based construction in Theorem A.4, it holds for
all the other critical nodes $N\in\mathcal{S}_{i}\setminus A_{r_{i}+1}$ that
$\mathrm{vol}\\!\left(\\!\,N\,\\!\right)\leqslant
2\cdot\mathrm{vol}\\!\left(\\!\,\mathrm{sib}_{\mathbb{T}_{i}}(N)\,\\!\right)$
and $|N|\leqslant 2\cdot|\mathrm{sib}_{\mathbb{T}_{i}}(N)|$.

Finally, the following inequality will be extensively in our proof of Theorem
5.4:

######  Lemma A.8.

Let $G=(V,E,w)$ be a graph with a partition $S_{1},\ldots,S_{k}$, such that
$\Phi_{\mathrm{out}}\leqslant 1/2$ and
$\Phi_{G[S_{i}]}\geqslant\Phi_{\mathrm{in}}$ for any $1\leqslant i\leqslant
k$. Then it holds that

$\sum_{i=1}^{k}|S_{i}|\cdot\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right)\leqslant\frac{18\cdot\eta_{S}}{\Phi_{\mathrm{in}}}\cdot\mathsf{OPT}_{G},$

where $\eta_{S}$ is an upper bound of $\max_{i}(\Delta(S_{i})/\delta(S_{i}))$.

###### Proof.

We can trivially lower bound $\mathsf{OPT}_{G}$ by only considering the
internal edges $e\in S_{i}$ of the individual clusters $G[S_{i}]$, and then
applying the lower bound from Lemma A.1:

$\displaystyle\mathsf{OPT}_{G}$
$\displaystyle\geqslant\sum_{i=1}^{k}\sum_{e\in
E[G[S_{i}]]}\mathsf{cost}_{G[S_{i}]}(e)\geqslant\sum_{i=1}^{k}\mathsf{OPT}_{G[S_{i}]}$
$\displaystyle\geqslant\sum_{i=1}^{k}\frac{2\cdot\Phi_{G[S_{i}]}}{9}\cdot|S_{i}|\cdot\mathrm{vol}\\!\left(\\!\,G[S_{i}]\,\\!\right)\cdot\frac{d_{G[S_{i}]}}{\Delta_{G[S_{i}]}}$
$\displaystyle\geqslant\frac{2\cdot\Phi_{\mathrm{in}}}{9}\cdot\sum_{i=1}^{k}|S_{i}|\cdot\frac{\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right)}{2}\cdot\frac{1}{2\cdot\eta_{S}}.$

Here, the second inequality follows by Lemma A.1 and the last inequality holds
because of the assumptions in the Lemma and the fact that

$\mathrm{vol}\\!\left(\\!\,S_{i}\,\\!\right)=\mathrm{vol}\\!\left(\\!\,G[S_{i}]\,\\!\right)+w(S_{i},V\setminus
S_{i})\leqslant 2\cdot\mathrm{vol}\\!\left(\\!\,G[S_{i}]\,\\!\right)$

when $\Phi_{\mathrm{out}}\leqslant 1/2$, and because

$\frac{d_{G[S_{i}]}}{\Delta_{G[S_{i}]}}\geqslant\frac{d_{G[S_{i}]}}{\Delta(S_{i})}\geqslant\frac{\delta(S_{i})}{\Delta(S_{i})\cdot
2}\geqslant\frac{1}{2\cdot\eta_{S}}.$

Rearranging the terms above proves the statement. ∎

###  A.2 Spectral Clustering

Another component used in our analysis is spectral clustering. To analyse the
theoretical performance of spectral clustering, one can examine the scenario
in which there is a large gap between $\lambda_{k+1}$ and $\rho(k)$. By the
higher-order Cheeger inequality (3.1), we know that a low value of $\rho(k)$
ensures that the vertex set $V$ of $G$ can be partitioned into $k$ subsets
(clusters), each of which has conductance upper bounded by $\rho(k)$; on the
other hand, a large value of $\lambda_{k+1}$ implies that any $(k+1)$-th
partition of $V$ would introduce some $A\subset V$ with conductance
$\Phi_{G}(A)\geqslant\rho(k+1)\geqslant\lambda_{k+1}/2$. Based on this, Peng
et al. [PSZ17] introduced the parameter

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

and showed that a large value of $\Upsilon(k)$ is sufficient to guarantee a
good performance of spectral clustering. The result of [PSZ17] has been
improved by a sequence of works, and the following result, which can be shown
easily by combining the proof technique of [PSZ17] and [MS22], will be used in
our analysis.

######  Lemma A.9.

There is an absolute constant $C_{\ref{lem:MS22+}}\in\mathbb{R}_{>0}$, such
that the following holds: Let $G$ be a graph with $k$ optimal clusters
$\\{S_{i}\\}_{i=1}^{k}$, and $\Upsilon(k)\geqslant C_{\ref{lem:MS22+}}\cdot
k$. Let $\\{P_{i}\\}_{i=1}^{k}$ be the output of spectral clustering and,
without loss of generality, the optimal correspondence of $P_{i}$ is $S_{i}$
for any $1\leqslant i\leqslant k$. Then, it holds for any $1\leqslant
i\leqslant k$ that

$\mathrm{vol}(P_{i}\triangle S_{i})\leqslant\frac{k\cdot
C_{\ref{lem:MS22+}}}{3\Upsilon(k)}\cdot\mathrm{vol}(S_{i}),$

where $A\triangle B$ for any sets $A$ and $B$ is defined by $A\triangle
B\triangleq(A\setminus B)\cup(B\setminus A)$. Moreover, these
$P_{1},\ldots,P_{k}$ can be computed in nearly-linear time.

###  A.3 Strong Decomposition Lemma

The objective of this subsection is to prove the following decomposition
lemma. The lemma shows that, under a certain eigen-gap condition, an input
graph $G$ can be partitioned into clusters with bounded inner and outer
conductance, and certain constraints on cut values. We remark that, while
obtaining the partition promised by the lemma below requires high time
complexity, we only need the existence of such partition in our analysis.

######  Lemma A.10 (Improved Strong Decomposition Lemma).

Let $G=(V,E,w)$ be a graph such that $\lambda_{k+1}>0$ and
$\lambda_{k}<\left(\frac{1}{270\cdot c_{0}\cdot(k+1)^{6}}\right)^{2}$, where
$c_{0}$ is the constant in Lemma A.12. Then, there is a polynomial-time
algorithm that finds an $\ell$-partition of $V$ into sets
$\\{C_{i}\\}_{i=1}^{\ell}$, for some $\ell\leqslant k$, such that for every
$1\leqslant i\leqslant\ell$ and every vertex $u\in C_{i}$ the following
properties hold:

  1. (A1)

$\Phi(C_{i})=O(k^{6}\sqrt{\lambda_{k}})$;

  2. (A2)

$\Phi_{G[C_{i}]}=\Omega(\lambda_{k+1}^{2}/k^{4})$;

  3. (A3)

$w(u,V\setminus C_{i})\leqslant 6(k+1)\cdot\mathrm{vol}_{G[C_{i}]}(u)$.

We remark that the first two properties of the partitioning promised by Lemma
A.10 are the same as the ones from [MS21]. However, the third property of our
lemma is stronger than theirs, as Property (A3) now holds for all vertices in
$u\in C_{i}$, instead of only the critical nodes $N\in\mathcal{S}_{i}$. We
emphasise that this improved decomposition is crucial for our final analysis.
In particular, we only use Lemma A.10 to show the _existence_ of a strong
decomposition with properties (A1), (A2), and (A3), and we use the
strengthened property (A3) in the analysis of the approximation factor of our
algorithm.

Before starting the analysis, by convention we set $\Phi_{G}(V)\triangleq 0$,
and $\Phi_{G}(\emptyset)\triangleq 1$. We also set $w(\emptyset,S)\triangleq
0$ for any non-empty subset $S\subset V$. The following two results will be
used in our analysis.

######  Lemma A.11 (Cheeger Inequality, [Alo86]).

It holds for any graph $G$ that
$\frac{\lambda_{2}}{2}\leqslant\Phi_{G}\leqslant\sqrt{2\lambda_{2}}$.
Furthermore, there is a nearly-linear time algorithm (i.e., the Spectral
Partitioning algorithm) that finds a set $S$ such that
$\mathrm{vol}(S)\leqslant\mathrm{vol}(V)/2$, and
$\Phi_{G}(S)\leqslant\sqrt{2\lambda_{2}}$.

######  Lemma A.12 (Lemma 1.13, [OGT14]).

There is an absolute constant $c_{0}>1$ such that for any $k\geqslant 2$ and
any $r$-way partition $C_{1},\ldots,C_{r}$ of $V$, where $r\leqslant k-1$, we
have that

$\min_{1\leqslant i\leqslant
r}\lambda_{2}\left(\mathcal{L}_{G[C_{i}]}\right)\leqslant 2c_{0}\cdot
k^{6}\cdot\lambda_{k}.$

Now we describe the underlying algorithm and show a sequence of claims, which
are used to prove Lemma A.10. At the very high level, our algorithm for
computing a stronger decomposition of a well-clustered graph can be viewed as
an adjustment to Algorithm 3 in [MS21], which itself is based on Algorithm 3
in [OGT14] The main idea can be summarised as follows: the algorithm starts
with the trivial $1$-partition of $G$, i.e., $C_{1}=V$; in every iteration,
the algorithm applies the Spectral Partitioning algorithm for every graph in
$\\{G[C_{i}]\\}_{i=1}^{r}$, and tries to find a sparse cut $(S,C_{i}\setminus
S)$ for some $S\subset C_{i}$.888We denote by $r$ the number of clusters in
the current run of the algorithm, and denote by $\ell$ the final number of
clusters output by the algorithm.

  * •

If such a cut is found, the algorithm uses this cut to either introduce a new
partition set $C_{r+1}$ of low conductance, or refine the current partition
$\\{C_{i}\\}_{i=1}^{r}$;

  * •

If no such cut is found, the algorithm checks if it is possible to perform a
local refinement of the partition sets $\\{C_{i}\\}_{i=1}^{r}$ in order to
reduce the overall weight of the crossing edges, i.e. $\sum_{i\neq
j}w(C_{i},C_{j})$. If such a refinement is not possible, the algorithm
terminates and outputs the current partition; otherwise, the partition sets
are locally refined and the process is repeated.

The output of the algorithm is guaranteed to satisfy Properties $(A1)$ and
$(A2)$ of Lemma A.10.

Our improved analysis will show that Property $(A3)$ holds as well, and this
will be proven with the two additional Properties $(A4)$ and $(A5)$ stated
later. We begin our analysis by setting the notation, most of which follows
from [OGT14]. We write $\\{C_{i}\\}_{i=1}^{r}$ as a partition of $V$ for some
integer $r\geqslant 1$, and every partition set $C_{i}$ contains some _core
set_ denoted by $\mathrm{core}(C_{i})\subseteq C_{i}$. For an arbitrary subset
$S\subset C_{i}$, we define

$S^{+}\triangleq S\cap\mathrm{core}(C_{i}),$

and

$S^{-}\triangleq S\setminus S^{+}.$

We further define

$\overline{S^{+}}\triangleq\mathrm{core}(C_{i})\setminus S,$

and $\overline{S^{-}}\triangleq C_{i}\setminus(S\cup\mathrm{core}(C_{i}))$.
Note that $\\{S^{+},\overline{S^{+}}\\}$ forms a partition of
$\mathrm{core}(C_{i})$, and $\\{S^{-},\overline{S^{-}}\\}$ forms a partition
of $C_{i}\setminus\mathrm{core}(C_{i})$. For the ease of presentation, we
always write $u^{+}$ and $u^{-}$ if the set $S$ consists of a single vertex
$u$. For any sets $S,T\subseteq V$ which are not necessarily disjoint, we
write

$w(S\rightarrow T)\triangleq w(S,T\setminus S),$

For any subsets $S\subseteq C\subseteq V$, we follow [OGT14] and define the
_relative conductance_ as

$\varphi(S,C)\triangleq\frac{w(S\rightarrow C)}{\frac{\mathrm{vol}(C\setminus
S)}{\mathrm{vol}(C)}\cdot w(S\rightarrow V\setminus C)},$

whenever the right-hand side is defined and otherwise we set $\varphi(S,C)=1$.
To explain the meaning of $\varphi(S,C)$, suppose that $C\subset V$ is the
vertex set such that $\Phi_{G}(C)$ is low and $\Phi_{G[C]}$ is high, i.e., $C$
is a cluster. Then, we know that most of the subsets $S\subset C$ with
$\mathrm{vol}(S)\leqslant\mathrm{vol}(C)/2$ satisfy the following properties:

  * •

Since $\Phi_{G[C]}(S)$ is high, a large fraction of the edges adjacent to
vertices in $S$ would leave $S$;

  * •

Since $\Phi_{G}(C)$ is low, a small fraction of edges adjacent to $S$ would
leave $C$.

Combining the above observations, one could conclude that $w(S\rightarrow
C)\gtrsim w(S\rightarrow V\setminus C)$ if $C$ is a good cluster, which means
that $\varphi(S,C)$ is lower bounded by a constant. Moreover, Oveis Gharan and
Trevisan [OGT14] showed a converse of this fact: if $\varphi(S,C)$ is large
for all $S\subset C$, then $C$ has high inner conductance. These facts suggest
that the relative conductance provides a good quantitative measure of the
quality of a cluster.

Input: $G=(V,E,w)$, $k>1$ such that $\lambda_{k+1}>0$

Output: A $\left(\phi_{\mathrm{in}}^{2}/4,\phi_{\mathrm{out}}\right)$
$\ell$-partition $\\{C_{i}\\}_{i=1}^{\ell}$ of $G$ satisfying $(A1)-(A3)$, for
some $\ell\leqslant k$

1 Let $r=1$, $\mathsf{CORE}(C_{1})=C_{1}=V$

2 Let $\phi_{\mathrm{in}}=\frac{\lambda_{k+1}}{140(k+1)^{2}}$, and
$\phi_{\mathrm{out}}=90c_{0}\cdot(k+1)^{6}\sqrt{\lambda_{k}}$

3 Let
$\rho^{*}=\min\left\\{\frac{\lambda_{k+1}}{10},30c_{0}\cdot(k+1)^{5}\cdot\sqrt{\lambda_{k}}\right\\}$

4 while  _At least one of the following conditions holds 1. $\exists
1\leqslant i\leqslant r$ s.t. $w(C_{i}\setminus\mathsf{CORE}(C_{i})\rightarrow
C_{i})<w(C_{i}\setminus\mathsf{CORE}(C_{i})\rightarrow C_{j})$ for some $j\neq
i$; 2. Spectral Partitioning finds $S\subseteq C_{i}$ with 999If the set
$S\subset C_{i}$ returned by Spectral Partitioning has
$\mathrm{vol}(S^{+})>\mathrm{vol}(G)/2$, swap $S$ with $C_{i}\setminus S$.
$\mathrm{vol}(S^{+})\leqslant\mathrm{vol}(\mathrm{core}(C_{i}))/2$, such that
$\max\left\\{\Phi_{G[C_{i}]}(S),\Phi_{G[C_{i}]}(C_{i}\setminus
S)\right\\}<\phi_{\mathrm{in}}$; _ do

5 Order the sets $C_{1},\ldots,C_{r}$ such that
$\lambda_{2}(\mathcal{L}_{G[C_{1}]})\leqslant\ldots\leqslant\lambda_{2}(\mathcal{L}_{G[C_{r}]})$

6 Let $1\leqslant i\leqslant r$ the smallest index for which item $2$ of the
while-condition is satisfied, and let $S\subset C_{i}$ be the corresponding
set

7

8 if
_$\max\left\\{\Phi_{G}(S^{+}),\Phi_{G}\left(\overline{S^{+}}\right)\right\\}\leqslant\left(1+\frac{1}{k+1}\right)^{r+1}\cdot\rho^{*}$_
then

9 Let $C_{i}=C_{i}\setminus\overline{{S^{+}}}$, $\mathsf{CORE}(C_{i})=S^{+}$,
$C_{r+1}=\mathsf{CORE}(C_{r+1})=\overline{S^{+}}$, $r=r+1$ and go to Line 3

10

11 if
_$\min\left\\{\varphi(S^{+},\mathsf{CORE}(C_{i})),\varphi\left(\overline{S^{+}},\mathsf{CORE}(C_{i})\right)\right\\}\leqslant\frac{1}{3(k+1)}$_
then

12 Update $\mathsf{CORE}(C_{i})$ to either $S^{+}$ or $\overline{S^{+}}$ with
the lower conductance, and go to Line 3

13

14 if
_$\Phi_{G}(S^{-})\leqslant\left(1+\frac{1}{k+1}\right)^{r+1}\cdot\rho^{*}$_
then

15 Let $C_{i}=C_{i}\setminus S^{-}$, $C_{r+1}=\mathsf{CORE}(C_{r+1})=S^{-}$,
set $r=r+1$ and go to Line 3

16

17 if  _$w(C_{i}\setminus\mathsf{CORE}(C_{i})\rightarrow C_{i})
<w(C_{i}\setminus\mathsf{CORE}(C_{i})\rightarrow C_{j})$ for some $j\neq i$_
then

18 Let $C_{i}=\mathsf{CORE}(C_{i})$, merge
$(C_{i}\setminus\mathsf{CORE}(C_{i}))$ with
$\mathrm{argmax}_{C_{j}}\\{w(C_{i}\setminus\mathsf{CORE}(C_{i})\rightarrow
C_{j})\\}$, and go to Line 3

19

20 if  _$w(S^{-}\rightarrow C_{i}) <w(S^{-}\rightarrow C_{j})$ for some $j\neq
i$_ then

21 Let $C_{i}=C_{i}\setminus S^{-}$, merge $S^{-}$ with
$\mathrm{argmax}_{C_{j}}\\{w(S^{-}\rightarrow C_{j})\\}$, and go to Line 3

22

23

24 end while

25For every partition set $C_{i}$

26

27if  _ $\exists u\in C_{i}$ such that
$\mathrm{vol}(u^{+})\leqslant\mathrm{vol}(\mathsf{CORE}(C_{i}))/2$ and
$\varphi(u^{+},\mathsf{CORE}(C_{i}))\leqslant\frac{1}{3(k+1)}$_ then

28 Update $\mathsf{CORE}(C_{i})$ to either $u^{+}$ or $\overline{u^{+}}$ with
the lower conductance, and go to Line 3

29

30 if  _ $\exists u\in C_{i}$ such that
$\mathrm{vol}(u^{-})\leqslant\mathrm{vol}(C_{i})/2$ and $w(u^{-}\rightarrow
C_{i})<w(u^{-}\rightarrow C_{j})$ for some $j\neq i$_ then

31 Let $C_{i}=C_{i}\setminus u^{-}$, merge $u^{-}$ with
$\mathrm{argmax}_{C_{j}}\\{w(u^{-}\rightarrow C_{j})\\}$, and go to Line 3

32

return _the partition $\\{C_{i}\\}_{i=1}^{r}$._

Algorithm 3 Algorithm for partitioning $G$ into $\ell\leqslant k$ clusters

Now we explain the high-level idea of the proposed algorithm, and refer the
reader to Algorithm 3 for the formal description. Our algorithm starts with
the partitioning algorithm (Algorithm 3 in [OGT14]), and obtains an
intermediate partition $\\{C_{i}\\}_{i=1}^{r}$ (Lines 3–3). For every
$C_{i}~{}(1\leqslant i\leqslant r)$, the algorithm further checks if the
following conditions are satisfied:

  1. $(A4)$

For every vertex $u\in C_{i}$ with
$\mathrm{vol}(u^{+})\leqslant\mathrm{vol}(\mathsf{CORE}(C_{i}))/2$, it holds
that

$\varphi(u^{+},\mathsf{CORE}(C_{i}))\geqslant\frac{1}{3(k+1)};$

  2. $(A5)$

For every vertex $u\in C_{i}$ with
$\mathrm{vol}(u^{-})\leqslant\mathrm{vol}(C_{i})/2$, it holds that

$w(u^{-}\rightarrow C_{i})\geqslant w(u^{-}\rightarrow V\setminus
C_{i})\cdot\frac{1}{k+1}.$

If (A4) is violated by some vertex $u\in C_{i}$ for some $i$, then the
algorithm uses $u$ to refine the core set $\mathrm{core}(C_{i})$ (Line 3). If
$(A5)$ is not satisfied, then the algorithm further refines the partition
(Line 3). The algorithm repeats this local refinement process until no such
update is found anymore. In the following analysis, we set

$\rho^{*}\triangleq\min\left\\{\frac{\lambda_{k+1}}{10},30c_{0}\cdot(k+1)^{5}\cdot\sqrt{\lambda_{k}}\right\\},$

where $c_{0}$ is the constant specified in Lemma A.12, and

$\phi_{\mathrm{in}}\triangleq\frac{\lambda_{k+1}}{140(k+1)^{2}},\qquad\phi_{\mathrm{out}}\triangleq
90c_{0}\cdot(k+1)^{6}\sqrt{\lambda_{k}}.$ (A.2)

Notice that, by assuming $\lambda_{k}<\left(\frac{1}{270\cdot
c_{0}\cdot(k+1)^{6}}\right)^{2}$ in Lemma A.10, it holds that
$\phi_{\mathrm{out}}<1/3$. This fact will be used several times in our
analysis.

Following the proof structure in [OGT14], we will prove Lemma A.10 via a
sequence of claims. Notice that, during the entire execution of the algorithm,
the sets $\\{C_{i}\\}_{i=1}^{r}$ always form a partition of $V$, and each
$\mathsf{CORE}(C_{i})$ is a subset of $C_{i}$. Firstly, we show that, at any
point during the execution of the algorithm, the core sets
$\mathsf{CORE}(C_{i})~{}(1\leqslant i\leqslant r)$ always have low
conductance.

######  Claim A.1.

Throughout the algorithm, we always have that

$\max_{1\leqslant i\leqslant
r}\Phi_{G}(\mathsf{CORE}(C_{i}))\leqslant\rho^{*}\cdot\left(1+\frac{1}{k+1}\right)^{r}.$

The following result will be used in our proof:

######  Lemma A.13 (Lemma 2.2, [OGT14]).

Let $G=(V,E,w)$ be a graph, and let $S,W$ be two subsets such that $S\subset
W\subseteq V$. Suppose that the following two conditions are satisfied for
some $\varepsilon>0$:

  1. 1.

$\varphi(S,W)\leqslant\varepsilon/3$ and

  2. 2.

$\max\left\\{\Phi_{G}(S),\Phi_{G}(W\setminus
S)\right\\}\geqslant(1+\varepsilon)\cdot\Phi_{G}(W)$.

Then it holds that

$\min\left\\{\Phi_{G}(S),\Phi_{G}(W\setminus S)\right\\}\leqslant\Phi_{G}(W).$

###### Proof of Claim A.1.

Let $r$ be the current number of clusters generated by the algorithm, and we
prove by induction that the claim holds during the entire execution of the
algorithm. First of all, for the base case of $r=1$, we have that
$\mathsf{CORE}(C_{1})=C_{1}=V$, which gives us that
$\Phi_{G}(\mathsf{CORE}(C_{1}))=0$; hence, the statement holds trivially.

Secondly, for the inductive step, we assume that the statement holds for some
fixed configuration of the core sets $\\{\mathrm{core}(C_{i})\\}_{i=1}^{r}$
and we prove that the statement holds after the algorithm updates the current
configuration. Notice that $\\{\mathsf{CORE}(C_{i})\\}_{i=1}^{r}$ are updated
through Lines 3, 3, 3, and 3 of the algorithm, so it suffices to show that the
claim holds after executing these lines. We continue the proof with case
distinction.

  * •

When executing Lines 3, 3, the algorithm introduces some new set
$\mathsf{CORE}(C_{r+1})$ such that

$\Phi_{G}(\mathsf{CORE}(C_{r+1}))\leqslant\rho^{*}\cdot\left(1+\frac{1}{k+1}\right)^{r+1}.$

Combining this with the inductive hypothesis, which assumes the inequality
holds for $\mathsf{CORE}(C_{i})~{}(1\leqslant i\leqslant r)$, we have that

$\max_{1\leqslant i\leqslant
r+1}\Phi_{G}(\mathsf{CORE}(C_{i}))\leqslant\rho^{*}\cdot\left(1+\frac{1}{k+1}\right)^{r+1}.$

  * •

The case for executing Lines 3 and 3 is similar, and we prove this by applying
Lemma A.13. We first focus on Line 3 here, dealing with Line 3 next. When
executing Line 3, we know that the if-condition in Line 3 does not hold, so we
have that

$\max\left\\{\Phi_{G}(S^{+}),\Phi_{G}\left(\overline{S^{+}}\right)\right\\}>\left(1+\frac{1}{k+1}\right)^{r+1}\cdot\rho^{*}\geqslant\left(1+\frac{1}{k+1}\right)\cdot\Phi_{G}(\mathsf{CORE}(C_{i})),$

where the last inequality follows by the inductive hypothesis. Moreover, when
executing Line 3, we also know that the if-condition in Line 3 holds, i.e.,

$\min\left\\{\varphi\left(S^{+},\mathsf{CORE}(C_{i})\right),\varphi\left(\overline{S^{+}},\mathsf{CORE}(C_{i})\right)\right\\}\leqslant\frac{1}{3(k+1)}.$

Therefore, by applying Lemma A.13 with $S^{+}\subset\mathrm{core}(C_{i})$ and
$\varepsilon=1/(k+1)$ and using the inductive hypothesis, we conclude that

$\min\left\\{\Phi_{G}(S^{+}),\Phi_{G}\left(\overline{S^{+}}\right)\right\\}\leqslant\Phi_{G}(\mathsf{CORE}(C_{i}))\leqslant\rho^{*}\cdot\left(1+\frac{1}{k+1}\right)^{r}.$

  * •

Now we look at Line 3. When executing Line 3, we know that $u^{+}=u$; since
otherwise $u^{+}=\emptyset$ and $\varphi(\emptyset,\mathsf{CORE}(C_{i}))=1$.
Therefore, it holds that

$1=\max\left\\{\Phi_{G}(u^{+}),\Phi_{G}\left(\overline{u^{+}}\right)\right\\}>\left(1+\frac{1}{k+1}\right)^{r+1}\cdot\rho^{*}\geqslant\left(1+\frac{1}{k+1}\right)\cdot\Phi_{G}(\mathsf{CORE}(C_{i})),$

where the first inequality holds because $\Phi_{G}(u^{+})=1$, and the last
inequality follows by the inductive hypothesis. Moreover, when executing Line
3, we also know that the if-condition in Line 3 holds, i.e.,

$\varphi\left(u^{+},\mathsf{CORE}(C_{i})\right)\leqslant\frac{1}{3(k+1)}.$

Therefore, by applying Lemma A.13 with $u^{+}\subset\mathrm{core}(C_{i})$ and
$\varepsilon=1/(k+1)$ and using the inductive hypothesis, we conclude that

$\min\left\\{\Phi_{G}(u^{+}),\Phi_{G}\left(\overline{u^{+}}\right)\right\\}=\Phi_{G}\left(\overline{u^{+}}\right)\leqslant\Phi_{G}(\mathsf{CORE}(C_{i}))\leqslant\rho^{*}\cdot\left(1+\frac{1}{k+1}\right)^{r},$

where the first equality holds because $\Phi_{G}(u^{+})=1$ holds for
$u^{+}=u$.

Combining the two cases above, we know that the claim always holds during the
entire execution of the algorithm. This completes the proof. ∎

Next, we show that the number of partition sets cannot exceed $k$. This proof
is identical to Claim $3.2$ in [OGT14], and we include the proof here for
completeness.

######  Claim A.2.

The total number of clusters returned by the algorithm satisfies that
$\ell\leqslant k$.

###### Proof.

Suppose for contradiction that the number of clusters becomes $r=k+1$ at some
point during the execution of the algorithm. Then, since
$\mathsf{CORE}(C_{1}),\ldots,\mathsf{CORE}(C_{k+1})$ are disjoint, by the
definition of $\rho(k+1)$ and Claim A.1 we have that

$\rho(k+1)\leqslant\max_{1\leqslant i\leqslant
k+1}\Phi_{G}(\mathrm{core}(C_{i}))\leqslant\left(1+\frac{1}{k+1}\right)^{k+1}\cdot\rho^{*}\leqslant\mathrm{e}\cdot\rho^{*}\leqslant\mathrm{e}\cdot\frac{\lambda_{k+1}}{10}<\frac{\lambda_{k+1}}{2},$

which contradicts the higher-order Cheeger inequality (3.1). Therefore, the
total number of clusters at any time satisfies $r<k+1$, and the total number
of returned clusters satisfies $\ell\leqslant k$. ∎

Now we are ready to show that the output $\\{C_{i}\\}_{i=1}^{\ell}$ of
Algorithm 3 and its core sets $\\{\mathsf{CORE}(C_{i})\\}_{i=1}^{\ell}$
satisfy Properties $(A4)$ and $(A5)$, which will be used in proving Lemma
A.10.

######  Claim A.3.

Let $\\{C_{i}\\}_{i=1}^{\ell}$ be the output of Algorithm 3 with corresponding
core sets $\\{\mathsf{CORE}(C_{i})\\}_{i=1}^{\ell}$. Then, the following hold
for any $1\leqslant i\leqslant\ell$:

  1. 1.

$\Phi_{G}(\mathsf{CORE}(C_{i}))\leqslant\phi_{\mathrm{out}}/(k+1)$;

  2. 2.

$\Phi_{G}(C_{i})\leqslant\phi_{\mathrm{out}}$;

  3. 3.

$\Phi_{G[C_{i}]}\geqslant\phi_{\mathrm{in}}^{2}/4$;

  4. 4.

For every $u\in C_{i}$ with
$\mathrm{vol}(u^{+})\leqslant\mathrm{vol}(\mathsf{CORE}(C_{i}))/2$, we have
that

$\varphi(u^{+},\mathsf{CORE}(C_{i}))\geqslant\frac{1}{3(k+1)};$

  5. 5.

For every $u\in C_{i}$ with
$\mathrm{vol}(u^{-})\leqslant\mathrm{vol}(C_{i})/2$, we have that

$w(u^{-}\rightarrow C_{i})\geqslant w(u^{-}\rightarrow V\setminus
C_{i})\cdot\frac{1}{k+1}.$

###### Proof.

First of all, by Claim A.1 we have for any $1\leqslant i\leqslant\ell$ that

$\Phi_{G}(\mathsf{CORE}(C_{i}))\leqslant\rho^{*}\cdot\left(1+\frac{1}{k+1}\right)^{\ell}\leqslant\mathrm{e}\cdot\rho^{*}\leqslant
30\cdot\mathrm{e}\cdot
c_{0}\cdot(k+1)^{5}\sqrt{\lambda_{k}}\leqslant\frac{\phi_{\mathrm{out}}}{k+1},$

where the second inequality holds by the fact that $\ell\leqslant k+1$, the
third one holds by the choice of $\rho^{*}$, and the last one holds by the
choice of $\phi_{\mathrm{out}}$. This proves Item (1).

To prove Item (2), we notice that the first condition of the while-loop (Line
3) doesn’t hold when the algorithm terminates, hence we have for any
$1\leqslant i\neq j\leqslant\ell$ that

$w(C_{i}\setminus\mathsf{CORE}(C_{i})\rightarrow C_{i})\geqslant
w(C_{i}\setminus\mathsf{CORE}(C_{i})\rightarrow C_{j}).$

By applying the averaging argument, we have that

$\displaystyle
w(C_{i}\setminus\mathsf{CORE}(C_{i})\rightarrow\mathsf{CORE}(C_{i}))$
$\displaystyle=w(C_{i}\setminus\mathsf{CORE}(C_{i})\rightarrow C_{i})$
$\displaystyle\geqslant\frac{w(C_{i}\setminus\mathsf{CORE}(C_{i})\rightarrow
V)}{\ell}$
$\displaystyle\geqslant\frac{w(C_{i}\setminus\mathsf{CORE}(C_{i})\rightarrow
V\setminus C_{i})}{k}.$ (A.3)

We apply the same analysis used in [OGT14], and have that

$\displaystyle\Phi_{G}(C_{i})$ $\displaystyle=\frac{w(C_{i}\rightarrow
V)}{\mathrm{vol}(C_{i})}$
$\displaystyle\leqslant\frac{w\left(\mathrm{core}(C_{i})\rightarrow
V\right)+w\left(C_{i}\setminus\mathrm{core}(C_{i})\rightarrow V\setminus
C_{i}\right)-w(C_{i}\setminus\mathrm{core}(C_{i})\rightarrow\mathrm{core}(C_{i}))}{\mathrm{vol}(\mathrm{core}(C_{i}))}$
$\displaystyle\leqslant\Phi_{G}(\mathrm{core}(C_{i}))+\frac{(k-1)\cdot
w(C_{i}\setminus\mathrm{core}(C_{i})\rightarrow\mathrm{core}(C_{i}))}{\mathrm{vol}(\mathrm{core}(C_{i}))}$
$\displaystyle\leqslant k\cdot\Phi_{G}(\mathrm{core}(C_{i}))$
$\displaystyle\leqslant\phi_{\mathrm{out}},$

where the second inequality uses equation (A.3). This proves Item (2).

Next, we analyse Item (3). Again, we know that the second condition within the
while-loop (Line 3) does not hold when the algorithm terminates. By the
performance of the Spectral Partitioning algorithm (i.e., Lemma A.11), it
holds for any $1\leqslant i\leqslant\ell$ that
$\Phi_{G[C_{i}]}\geqslant\phi_{\mathrm{in}}^{2}/4$. With this, we prove that
Item (3) holds.

Similarly, when the algorithm terminates, we know that for any node $u\in
C_{i}$ the if-condition in Line 3 does not hold. Hence, for any $1\leqslant
i\leqslant\ell$ and any $u\in C_{i}$ with
$\mathrm{vol}(u^{+})\leqslant\mathrm{vol}(\mathsf{CORE}(C_{i}))/2$, we have
that

$\varphi(u^{+},\mathsf{CORE}(C_{i}))\geqslant\frac{1}{3(k+1)}.$

This shows that Item (4) holds as well.

Finally, since there is no $u\in C_{i}$ satisfying the if-condition in Line 3
of the algorithm, it holds for any $1\leqslant i\neq j\leqslant\ell$ and every
vertex $u\in C_{i}$ that $w(u^{-}\rightarrow C_{i})\geqslant
w(u^{-}\rightarrow C_{j})$. Therefore, by the same averaging argument we have
that

$w(u^{-}\rightarrow C_{i})\geqslant\frac{w(u^{-}\rightarrow
V)}{\ell}\geqslant\frac{w(u^{-}\rightarrow V\setminus C_{i})}{k+1},$

which shows that Item (5) holds. ∎

It remains to prove that the algorithm does terminate. To prove this, we first
show that, in each iteration of the while-loop (Lines 3–3), at least one of
the if-conditions will be satisfied, and some sets are updated accordingly.
This fact, stated as Claim A.4, is important, since otherwise the algorithm
might end up in an infinite loop. The following result will be used in our
proof.

######  Lemma A.14 (Lemma 2.6, [OGT14]).

Let $\mathrm{core}(C_{i})\subseteq C_{i}\subseteq V$, and $S\subset C_{i}$ be
such that
$\mathrm{vol}(S^{+})~{}\leqslant~{}\mathrm{vol}(\mathrm{core}(C_{i}))/2$.
Suppose that the following hold for some parameters $\rho$ and
$0<\varepsilon<1$:

  1. 1.

$\rho\leqslant\Phi_{G}(S^{-})$ and
$\rho\leqslant\max\\{\Phi_{G}(S^{+}),\Phi_{G}(\overline{S^{+}})\\}$;

  2. 2.

If $S^{-}\neq\emptyset$, then $w(S^{-}\rightarrow C_{i})\geqslant
w(S^{-}\rightarrow V)/k$;

  3. 3.

If $S^{+}\neq\emptyset$, then
$\varphi(S^{+},\mathrm{core}(C_{i}))\geqslant\varepsilon/3$ and
$\varphi\left(\overline{S^{+}},\mathrm{core}(C_{i})\right)\geqslant\varepsilon/3$.

Then, it holds that

$\Phi_{G[C_{i}]}(S)\geqslant\varepsilon\cdot\frac{\rho}{14k}.$

######  Claim A.4.

If at least one condition of the while-loop is satisfied, then at least one of
the if-conditions (Lines 3,3,3,3 or 3) is satisfied.

###### Proof.

First of all, notice that if the first condition of the while-loop is
satisfied, then the if-condition in Line 3 will be satisfied and the claim
holds. Hence, we assume that only the second condition of the while-loop is
satisfied, and we prove the claim by contradiction. That is, we show that, if
none of the if-conditions holds, then the set $S$ returned by the Spectral
Partitioning algorithm would satisfy that
$\Phi_{G[C_{i}]}(S)\geqslant\phi_{\mathrm{in}}$. The proof is structured in
the following two steps:

  1. 1.

We first prove that

$\Phi_{G[C_{i}]}(S)\geqslant\frac{\max\\{\rho^{*},\rho(r+1)\\}}{14(k+1)^{2}};$

  2. 2.

Using Item $(1)$ we prove that $\Phi_{G[C_{i}]}(S)\geqslant\phi_{\mathrm{in}}$
and reach our desired contradiction.

##### Step 1:

We prove this fact by applying Lemma A.14 with parameters

$\rho\triangleq\max\\{\rho^{*},\rho(r+1)\\}\quad\text{and}\quad\varepsilon\triangleq\frac{1}{k+1}.$

Let us show that the conditions of Lemma A.14 are satisfied, beginning with
the first one. If $S^{-}=\emptyset$, then we trivially have that
$1=\Phi_{G}(S^{-})\geqslant\rho$; so we assume that $S^{-}\neq\emptyset$. As
the if-condition in Line 3 is not satisfied, we have that

$\Phi_{G}(S^{-})\geqslant\left(1+\frac{1}{k+1}\right)^{r+1}\cdot\rho^{*},$

and combining this with Claim A.1 gives us that

$\Phi_{G}(S^{-})=\max\left\\{\Phi_{G}(\mathsf{CORE}(C_{1})),\dots,\Phi_{G}(\mathsf{CORE}(C_{r})),\Phi_{G}(S^{-})\right\\}\geqslant\rho(r+1).$

Therefore, we have that

$\Phi_{G}(S^{-})\geqslant\max\\{\rho^{*},\rho(r+1)\\}=\rho.$ (A.4)

Similarly, if $S^{+}=\emptyset$, then we trivially have that
$1=\max\\{\Phi_{G}(S^{+}),\Phi_{G}(\overline{S^{+}})\\}\geqslant\rho$; so we
assume that $S^{+}\neq\emptyset$. Moreover, since we have chosen $S^{+}$ such
that $\mathrm{vol}(S^{+})\leqslant\mathrm{vol}(\mathrm{core}(C_{i}))/2$, we
know that $\overline{S^{+}}=\mathrm{core}(C_{i})\setminus S^{+}\neq\emptyset$.
As the if-condition in Line 3 is not satisfied, we have that

$\max\left\\{\Phi_{G}(S^{+}),\Phi_{G}\left(\overline{S^{+}}\right)\right\\}\geqslant\left(1+\frac{1}{k+1}\right)^{r+1}\cdot\rho^{*}.$

Combining this with Claim A.1 gives us that

$\displaystyle\max\left\\{\Phi_{G}(S^{+}),\Phi_{G}\left(\overline{S^{+}}\right)\right\\}$
$\displaystyle=\max\\{\Phi_{G}(\mathsf{CORE}(C_{1})),\dots,\Phi_{G}(\mathsf{CORE}(C_{i-1})),\Phi_{G}(S^{+}),\Phi_{G}(\overline{S^{+}}),$
$\displaystyle\qquad\Phi_{G}(\mathsf{CORE}(C_{i+1})),\dots,\Phi_{G}(\mathsf{CORE}(C_{r}))\\}$
$\displaystyle\geqslant\rho(r+1).$

Therefore we have that

$\max\left\\{\Phi_{G}(S^{+}),\Phi_{G}\left(\overline{S^{+}}\right)\right\\}\geqslant\max\\{\rho^{*},\rho(r+1)\\}=\rho.$
(A.5)

Combining (A.4) and (A.5), we see that the first condition of Lemma A.14 is
satisfied. Since the if-condition in Line 3 is not satisfied, it follows by an
averaging argument that

$w(S^{-}\rightarrow C_{i})\geqslant\frac{w(S^{-}\rightarrow V)}{k},$

which shows that the second condition of Lemma A.14 is satisfied. Finally,
since the if-condition in Line 3 is not satisfied, we know that

$\min\left\\{\varphi(S^{+},\mathsf{CORE}(C_{i})),\varphi\left(\overline{S^{+}},\mathsf{CORE}(C_{i})\right)\right\\}\geqslant\frac{1}{3(k+1)},$

which shows that the third condition of Lemma A.14 is satisfied as well.
Hence, by Lemma A.14 we conclude that

$\Phi_{G[C_{i}]}(S)\geqslant\frac{\varepsilon\cdot\rho}{14(k+1)}=\frac{\max\\{\rho^{*},\rho(r+1)\\}}{14(k+1)^{2}},$
(A.6)

which completes the proof of the first step.

##### Step 2:

We prove this step with a case distinction as follows:

_Case 1: $r=k$._ By (A.6) and (3.1), we have that

$\Phi_{G[C_{i}]}(S)\geqslant\frac{\rho(r+1)}{14(k+1)^{2}}=\frac{\rho(k+1)}{14(k+1)^{2}}\geqslant\frac{\lambda_{k+1}}{28(k+1)^{2}}\geqslant\phi_{\mathrm{in}},$

which leads to the desired contradiction.

_Case 2: $r<k$._ Recall that the partition sets $\\{C_{i}\\}_{i=1}^{r}$ are
labelled such that
$\lambda_{2}(\mathcal{L}_{G[C_{1}]})\leqslant\ldots\leqslant\lambda_{2}(\mathcal{L}_{G[C_{r}]})$,
and the algorithm has chosen the lowest index $i$ for which the set $S\subset
C_{i}$ returned by the Spectral Partitioning algorithm satisfies the second
condition of the while-loop. Our proof is based on a further case distinction
depending on the value of $i$.

_Case 2a:_ $i=1$ (i.e., the algorithm selects $S\subseteq C_{1}$). We combine
the performance of the Spectral Partitioning algorithm (Lemma A.11) with Lemma
A.12, and obtain that

$\Phi_{G[C_{1}]}(S)\leqslant\sqrt{2\lambda_{2}(\mathcal{L}_{G[C_{1}]})}=\min_{1\leqslant
j\leqslant
r}\sqrt{2\lambda_{2}(\mathcal{L}_{G[C_{j}]})}\leqslant\sqrt{4c_{0}\cdot
k^{6}\cdot\lambda_{k}}.$ (A.7)

Combining (A.6) and (A.7) we have that

$\rho^{*}\leqslant 28c_{0}\cdot(k+1)^{5}\sqrt{\lambda_{k}}.$

Thus, by the definition of $\rho^{*}$ we have that

$\rho^{*}=\frac{\lambda_{k+1}}{10}.$

We combine this with (A.6), and have that

$\Phi_{G[C_{i}]}(S)\geqslant\frac{\lambda_{k+1}}{140(k+1)^{2}}=\phi_{\mathrm{in}},$

which gives our desired contradiction.

_Case 2b: $i>1$_ (i.e., the algorithm selects $S\subset C_{i}$ for some
$i\geqslant 2$). Let $S_{1}\subset C_{1}$ be the set obtained by applying the
Spectral Partitioning algorithm to the graph $G[C_{1}]$. Since the algorithm
did not select $S_{1}\subset C_{1}$, we know that
$\Phi_{G[C_{1}]}(S_{1})\geqslant\phi_{\mathrm{in}}$. Combining the performance
of the Spectral Partitioning algorithm (Lemma A.11) with Lemma A.12, we have
that

$\phi_{\mathrm{in}}\leqslant\Phi_{G[C_{1}]}(S_{1})\leqslant\min_{1\leqslant
j\leqslant r}\sqrt{2\lambda_{2}(\mathcal{L}_{G[C_{j}]})}\leqslant 2c_{0}\cdot
k^{3}\cdot\sqrt{\lambda_{k}}.$

This gives us that

$\frac{\lambda_{k+1}}{10}=14(k+1)^{2}\cdot\phi_{\mathrm{in}}<30c_{0}\cdot(k+1)^{5}\cdot\sqrt{\lambda_{k}},$

and it holds by the definition of $\rho^{*}$ that

$\rho^{*}=\frac{\lambda_{k+1}}{10}.$

Therefore, by (A.6) we have that

$\Phi_{G[C_{i}]}(S)\geqslant\frac{\lambda_{k+1}}{140(k+1)^{2}}=\phi_{\mathrm{in}}.$

Combining the two cases above gives us the desired contradiction. With this,
we complete the proof of the claim. ∎

Next, we will show that the total number of iterations that the algorithm
runs, i.e., the number of times the instruction “go to Line 3” is executed, is
finite.

######  Claim A.5.

For any graph $G=(V,E,w)$ with the minimum weight $w_{\min}$ as the input,
Algorithm 3 terminates after executing the while-loop $O\left(k\cdot
n\cdot\mathrm{vol}(G)/w_{\min}\right)$ times.

###### Proof.

Notice that the algorithm goes back to check the loop conditions (Line 3)
right after any of Lines 3, 3, 3, 3, 3, 3 and 3 is executed, and each of these
commands changes the current structure of our partition
$\\{C_{i}\\}_{i=1}^{r}$ with core sets $\mathsf{CORE}(C_{i})\subseteq C_{i}$.
We classify these updates into the following three types:

  1. 1.

The updates that introduce a new partition set $C_{r+1}$. These correspond to
Lines 3, and 3;

  2. 2.

The updates that contract the core sets $\mathsf{CORE}(C_{i})$ to a strictly
smaller subset $T\subset\mathsf{CORE}(C_{i})$. These correspond to Lines 3 and
3;

  3. 3.

The updates that refine the partition sets $\\{C_{i}\\}_{i=1}^{r}$ by moving a
subset $T\subseteq C_{i}\setminus\mathsf{CORE}(C_{i})$ from the partition set
$C_{i}$ to a different partition set $C_{j}$, for some $C_{i}\neq C_{j}$.
These correspond to Lines 3, 3, and 3.

We prove that these updates can occur only a finite number of times. The first
type of updates can occur at most $k$ times, since we know by Claim A.2 that
the algorithm outputs $\ell\leqslant k$ clusters. Secondly, for a fixed value
of $\ell$, the second type of updates occurs at most $n$ times, since each
update decreases the size of some $\mathsf{CORE}(C_{i})$ by at least one.
Finally, for a fixed $\ell$ and a fixed configuration of core sets
$\mathsf{CORE}(C_{i})\subseteq C_{i}$, the third type of updates occurs at
most $O(\mathrm{vol}(G)/w_{\min})$ times. This is due to the fact that,
whenever every such update is executed, the total weight between different
partition sets, i.e., $\sum_{i\neq j}w(C_{i},C_{j})$, decreases by at least
$w_{\min}$. Combining everything together proves the lemma. ∎

Finally, we combine everything together and prove Lemma A.10.

###### Proof of Lemma A.10.

We first show that Properties $(A1),(A2)$ and $(A3)$ hold, and in the end we
analyse the runtime of the algorithm. Combining Items (2) and (3) of Claim A.3
with the choices of $\phi_{\mathrm{in}},\phi_{\mathrm{out}}$ in (A.2), we
obtain for all $1\leqslant i\leqslant\ell$ that
$\Phi_{G}(C_{i})\leqslant\phi_{\mathrm{out}}=O\left(k^{6}\cdot\sqrt{\lambda_{k}}\right)$
and
$\Phi_{G[C_{i}]}\geqslant\phi_{\mathrm{in}}^{2}/4=\Omega\left(\lambda_{k+1}^{2}/k^{4}\right)$.
Hence, Properties $(A1)$ and $(A2)$ hold for every $C_{i}$.

To analyse Property (A3), we fix an arbitrary node $u\in C_{i}$ that belongs
to the partition set $C_{i}$ with core set $\mathsf{CORE}(C_{i})$. By
definition, we have that

$w(u,V\setminus C_{i})=w(u^{+},V\setminus C_{i})+w(u^{-},V\setminus C_{i}).$

We study $w(u^{+},V\setminus C_{i})$ and $w(u^{-},V\setminus C_{i})$
separately.

##### Bounding the value of $w(u^{+},V\setminus C_{i})$:

We analyse $w(u^{+},V\setminus C_{i})$ by the following case distinction.

Case 1: $\mathrm{vol}(u^{+})\leqslant\mathrm{vol}(\mathsf{CORE}(C_{i}))/2$. By
Item (4) of Claim A.3 we know that

$\varphi(u^{+},\mathsf{CORE}(C_{i}))\geqslant\frac{1}{3(k+1)},$

which is equivalent to

$3(k+1)\cdot\frac{\mathrm{vol}(\mathsf{CORE}(C_{i}))}{\mathrm{vol}(\overline{u^{+}})}\cdot
w(u^{+}\rightarrow\mathsf{CORE}(C_{i}))\geqslant w(u^{+}\rightarrow
V\setminus\mathsf{CORE}(C_{i})).$

This implies that

$6(k+1)\cdot w(u^{+}\rightarrow\mathsf{CORE}(C_{i}))\geqslant
w(u^{+}\rightarrow V\setminus\mathsf{CORE}(C_{i})),$

and we have that

$\displaystyle w(u^{+},V\setminus C_{i})$ $\displaystyle\leqslant
w(u^{+}\rightarrow V\setminus\mathsf{CORE}(C_{i}))$ $\displaystyle\leqslant
6(k+1)\cdot w(u^{+}\rightarrow\mathsf{CORE}(C_{i}))$ $\displaystyle\leqslant
6(k+1)\cdot\mathrm{vol}_{G[C_{i}]}(u^{+}).$

Case 2: $\mathrm{vol}(u^{+})>\mathrm{vol}(\mathsf{CORE}(C_{i}))/2$. We have
that

$\displaystyle w(u^{+},V\setminus C_{i})$ $\displaystyle\leqslant
w(\mathsf{CORE}(C_{i}),V\setminus C_{i})\leqslant
w(\mathsf{CORE}(C_{i}),V\setminus\mathsf{CORE}(C_{i}))$
$\displaystyle=\mathrm{vol}(\mathsf{CORE}(C_{i}))\cdot\Phi_{G}(\mathsf{CORE}(C_{i}))\leqslant\mathrm{vol}(\mathsf{CORE}(C_{i}))\cdot\frac{\phi_{\mathrm{out}}}{k+1}$
$\displaystyle<\frac{2\phi_{\mathrm{out}}}{k+1}\cdot\mathrm{vol}(u^{+}),$
(A.8)

where the third inequality follows by Item (1) of Claim A.3. Therefore, we
have that

$\mathrm{vol}_{G[C_{i}]}(u^{+})=\mathrm{vol}(u^{+})-w(u^{+},V\setminus
C_{i})>\mathrm{vol}(u^{+})\left(1-\frac{2\phi_{\mathrm{out}}}{k+1}\right),$
(A.9)

where the last inequality follows by (A.8). We further combine (A.8) with
(A.9), and obtain that

$w(u^{+},V\setminus
C_{i})\leqslant\frac{2\phi_{\mathrm{out}}}{k+1}\cdot\frac{1}{1-\frac{2\phi_{\mathrm{out}}}{k+1}}\cdot\mathrm{vol}_{G[C_{i}]}(u^{+})\leqslant\frac{2\phi_{\mathrm{out}}}{k}\cdot\mathrm{vol}_{G[C_{i}]}(u^{+}),$

where the last inequality holds by our assumption that
$\phi_{\mathrm{out}}<1/3$.

Therefore, combining the two cases above gives us that

$w(u^{+},V\setminus C_{i})\leqslant
6(k+1)\cdot\mathrm{vol}_{G[C_{i}]}\left(u^{+}\right).$ (A.10)

##### Bounding the value of $w(u^{-},V\setminus C_{i})$:

We analyse $w(u^{-},V\setminus C_{i})$ based on the following two cases.

Case 1: $\mathrm{vol}(u^{-})\leqslant\mathrm{vol}(C_{i})/2$. By Item (5) of
Claim A.3, we know that

$w(u^{-}\rightarrow C_{i})\geqslant w(u^{-}\rightarrow V\setminus
C_{i})\cdot\frac{1}{(k+1)},$

which gives us that

$w(u^{-},V\setminus C_{i})\leqslant(k+1)\cdot w(u^{-}\rightarrow
C_{i})\leqslant(k+1)\cdot\mathrm{vol}_{G[C_{i}]}(u^{-}).$

Case 2: $\mathrm{vol}(u^{-})>\mathrm{vol}(C_{i})/2$. In this case, we have
that

$w(u^{-},V\setminus C_{i})\leqslant w(C_{i},V\setminus
C_{i})=\Phi_{G}(C_{i})\cdot\mathrm{vol}(C_{i})\leqslant\phi_{\mathrm{out}}\cdot\mathrm{vol}(C_{i})\leqslant
2\phi_{\mathrm{out}}\cdot\mathrm{vol}(u^{-}),$ (A.11)

where the second inequality follows by Item (2) of Claim A.3. This implies
that

$\mathrm{vol}_{G[C_{i}]}(u^{-})=\mathrm{vol}(u^{-})-w(u^{-},V\setminus
C_{i})\geqslant(1-2\phi_{\mathrm{out}})\cdot\mathrm{vol}(u^{-}),$ (A.12)

where the last inequality follows by (A.11). Finally, combining (A.11) and
(A.12) gives us that

$w(u^{-},V\setminus
C_{i})\leqslant\frac{2\phi_{\mathrm{out}}}{1-2\phi_{\mathrm{out}}}\cdot\mathrm{vol}_{G[C_{i}]}(u^{-})\leqslant
2\cdot\mathrm{vol}_{G[C_{i}]}(u^{-}),$

where the last inequality follows by our assumption that
$\phi_{\mathrm{out}}<1/3$. Therefore, combining the two cases together gives
us that

$w(u^{-},V\setminus C_{i})\leqslant(k+1)\cdot\mathrm{vol}_{G[C_{i}]}(u^{-}).$
(A.13)

Our claimed property $(A3)$ follows by summing the inequalities in (A.10) and
(A.13) and the fact that

$\mathrm{vol}_{G[C_{i}]}(u)=\mathrm{vol}_{G[C_{i}]}(u^{+})+\mathrm{vol}_{G[C_{i}]}(u^{-}).$

Finally, we analyse the runtime of the algorithm. By Claims A.4 and A.5, we
know that the algorithm does terminate, and the total number of iterations of
the main while-loop executed by the algorithm is upper bounded by $O(k\cdot
n\cdot\mathrm{vol}(G)/w_{\min})$. Notice that this quantity is upper bounded
by $O(\operatorname{poly}(n))$ given our assumption that
$w_{\max}/w_{\min}=O(\operatorname{poly}(n))$. This completes the proof. ∎

##  Appendix B Omitted Details of Proof of Theorem 5.1

This section presents omitted details of the proof of Theorem 5.1. Our key
approach of breaking the running time barrier of [MS21] is that, instead of
approximating the optimal tree $\mathcal{T}^{*}$, we approximate the tree
constructed by the algorithm of [MS21].

At a very high level, we first slightly adjust the tree construction by
[MS21], and show that the cost of this adjusted variant is the same as their
original tree construction. We call the adjusted tree
$\mathcal{T}_{\textsf{MS}}$. Then, we perform a sequence of changes to
$\mathcal{T}_{\textsf{MS}}$, such that the total induced cost of these changes
is not too high. After this sequence of changes, we end up with a tree
$\mathcal{T}_{\textsf{MS}}^{\prime\prime}$, whose cost can be approximated in
nearly-linear time with the output of Algorithm 1. In particular, we only
require the _existence_ of the tree $\mathcal{T}_{\textsf{MS}}$, and not its
explicit construction.

The section is organised as follows: In Section B.1 we introduce a variant of
the algorithm and tree construction from [MS21]. In Section B.2 we prove Lemma
5.2 and Lemma 5.3. Finally, we prove Theorem 5.1 in Section B.3.

###  B.1 Caterpillar Tree on Extended Critical Nodes

Now we present an adjusted version of the result on well-clustered graphs from
[MS21]. Their original algorithm first uses their variant of Lemma A.10 to
explicitly construct a partition $\\{C_{1},\ldots,C_{\ell}\\}$, and then
decomposes every $C_{i}$ into critical nodes $\mathcal{S}_{i}$. These critical
nodes are used to construct their final tree.

In our adjusted form, instead of using the critical nodes $\mathcal{S}_{i}$ as
the building blocks, we use the “extended” critical nodes as building blocks,
which are described below.

Let $C_{1},\ldots C_{\ell}$ be the partition returned by Lemma A.10. We assume
for every $C_{i}$ that $(A_{0},\ldots,A_{r})$ is the dense branch of
$\mathbb{T}_{i}=\mathbb{T}_{\mathrm{deg}}(G[C_{i}])$ for some
$r\in\mathbb{Z}_{+}$, and we extend the dense branch to
$(A_{0},\ldots,A_{i_{\max}-1})$ with the property that, for every
$i\in[r,i_{\max}-1]$, $A_{i}$ is the child of $A_{i-1}$ with the higher
volume, and $A_{i_{\max}-1}$ having children $A_{i_{\max}}$ and $B_{i_{\max}}$
such that $|A_{i_{\max}}|\leqslant 2$ and let
$\mathcal{S}_{i}\triangleq\\{B_{1},\ldots,B_{i_{\max}},A_{i_{\max}}\\}$ be the
set of all _extended_ critical nodes.

Based on this new notion of extended critical nodes, Algorithm 4 gives a
formal description of our adjusted tree called $\mathcal{T}_{\mathsf{MS}}$,
which consists of three phases: Partition, Prune and Merge. In the Partition
phase (Lines 4–4), the algorithm employs Lemma A.10 to partition $V(G)$ into
sets $\\{C_{i}\\}_{i=1}^{\ell}$, and applies Theorem A.4 to obtain the
corresponding trees $\\{\mathbb{T}_{i}\\}_{i=1}^{\ell}$. The Prune phase
(Lines 4–4) consists of a repeated pruning process: for every such tree
$\mathbb{T}_{i}$, the algorithm prunes the subtree $\mathbb{T}_{i}[N]$, where
$N\in\mathcal{S}_{i}$ is the extended critical node closest to the root in
$\mathbb{T}_{i}$, and adds $\mathbb{T}_{i}[N]$ to $\mathbb{T}$, which is the
collection of all the pruned subtrees (Line 4). The process is repeated until
$\mathbb{T}_{i}$ is completely pruned. Finally, in the Merge phase (Lines 4–4)
the algorithm combines the trees in $\mathbb{T}$ in a “caterpillar style”
according to an increasing order of their size, where we define the size of a
tree $\mathcal{T}$ as $|\mathcal{T}|\triangleq|\mathsf{leaves}(\mathcal{T})|$.
We call the final constructed tree $\mathcal{T}_{\mathsf{MS}}$, and the
performance of this algorithm is summarised in Lemma B.1. We emphasise _again_
that in our algorithm we do not explicitly run Algorithm 4 to construct our
tree. Instead, we use it to show the _existence_ of tree
$\mathcal{T}_{\mathsf{MS}}$, and our final analysis is to approximate the cost
of $\mathcal{T}_{\mathsf{MS}}$.

Data: A graph $G=(V,E,w)$, a parameter $k\in\mathbb{Z}_{+}$ such that
$\lambda_{k+1}>0$;

Result: An HC tree $\mathcal{T}_{\mathsf{MS}}$ of $G$;

1

2Apply the partitioning algorithm (Lemma A.10) on input $(G,k)$ to obtain
$\\{C_{i}\\}_{i=1}^{\ell}$ for some $\ell\leqslant k$;

3Let $\mathbb{T}_{i}=\mathrm{\texttt{HCwithDegrees}}(G[C_{i}])$;

4Initialise $\mathbb{T}=\emptyset$;

5for  _All clusters $C_{i}$_ do

6 Let $\mathcal{S}_{i}$ be the set of extended critical nodes of
$\mathbb{T}_{i}$;

7 for  _$N\in\mathcal{S}_{i}$_ do

8 Update $\mathbb{T}\leftarrow\mathbb{T}\cup\mathbb{T}_{i}[N]$.

9

10

11Let $t=|\mathbb{T}|$, and
$\mathbb{T}=\\{\widetilde{\mathbb{T}_{1}},\dots,\widetilde{\mathbb{T}_{t}}\\}$
be such that
$|\widetilde{\mathbb{T}}_{i}|\leqslant|\widetilde{\mathbb{T}}_{i+1}|$ for all
$1\leqslant i<t$;

12Initialise $\mathcal{T}_{\mathsf{MS}}=\widetilde{\mathbb{T}}_{1}$;

13for  _$i=2,\ldots,t$_ do

14 Let $\mathcal{T}_{\mathsf{MS}}$ be the tree with
$\mathcal{T}_{\mathsf{MS}}$ and $\widetilde{\mathbb{T}}_{i}$ as its two
children;

15

16return $\mathcal{T}_{\mathsf{MS}}$

Algorithm 4 Merge Extended Critical Nodes

######  Lemma B.1.

Let $G=(V,E,w)$ be a graph, and $k>1$ such that $\lambda_{k+1}>0$ and
$\lambda_{k}<\left(\frac{1}{270\cdot c_{0}\cdot(k+1)^{6}}\right)^{2}$, where
$c_{0}$ is the constant in Lemma A.12. Then, the tree
$\mathcal{T}_{\mathsf{MS}}$ returned by Algorithm 4 satisfies
$\mathsf{COST}_{G}(\mathcal{T}_{\mathsf{MS}})=O\left(k^{22}/\lambda_{k+1}^{10}\right)\cdot\mathsf{OPT}_{G}$.

The remaining part of this subsection is to analyse Algorithm 4, and prove
Lemma B.1. First of all, notice that, since $\\{C_{i}\\}_{i=1}^{\ell}$ is the
output of our partitioning algorithm, it holds for every $u\in C_{i}$ for any
$1\leqslant i\leqslant\ell$ that

  1. $(A1)$

$\Phi(C_{i})=O(k^{6}\sqrt{\lambda_{k}})$;

  2. $(A2)$

$\Phi_{G[C_{i}]}=\Omega(\lambda_{k+1}^{2}/k^{4})$;

  3. $(A3)$

$w(u,V\setminus C_{i})\leqslant 6(k+1)\cdot\mathrm{vol}_{G[C_{i}]}(u)$.

Generalising Property (A3), it is easy to see that it holds for every extended
critical node $N\in\mathcal{S}_{i}~{}(1\leqslant i\leqslant\ell)$ that

  1. $(A3^{enumi})$

$w(N,V\setminus C_{i})\leqslant 6(k+1)\cdot\mathrm{vol}_{G[C_{i}]}(N)$.

Moreover, with the parameter
$\phi_{\mathrm{in}}=\Theta\left(\lambda_{k+1}/k^{2}\right)$, we have that
$\Phi_{G[C_{i}]}=\Omega(\phi_{\mathrm{in}}^{2})$ holds for any $1\leqslant
i\leqslant\ell$. Let $\mathbb{T}_{i}=\mathbb{T}_{\mathrm{deg}}(G[C_{i}])$ with
the corresponding set of extended critical nodes $\mathcal{S}_{i}$ for all
$1\leqslant i\leqslant\ell$, and
$\mathcal{S}=\bigcup_{i=1}^{\ell}\mathcal{S}_{i}$ be the set of all extended
critical nodes. Now we group the edges of $G$ into two categories: let $E_{1}$
be the set of edges in the induced subgraphs $G[C_{i}]$ for all $1\leqslant
i\leqslant\ell$, i.e.,

$E_{1}\triangleq\bigcup_{i=1}^{\ell}E\left[G[C_{i}]\right],$

and $E_{2}$ be the remaining crossing edges. Therefore, we write the cost of
our tree $\mathcal{T}_{\mathsf{MS}}$ as

$\mathsf{COST}_{G}(\mathcal{T}_{\mathsf{MS}})=\sum_{e\in
E_{1}}\mathsf{cost}_{\mathcal{T}_{\mathsf{MS}}}(e)+\sum_{e\in
E_{2}}\mathsf{cost}_{\mathcal{T}_{\mathsf{MS}}}(e),$ (B.1)

and analyse each sum individually in Lemmas B.3 and B.4.

Our first result bounds the size of the parent of an extended critical node
$N\in\mathcal{S}_{i}$ in $\mathcal{T}_{\mathsf{MS}}$, with respect to the size
of its parent in the tree $\mathbb{T}_{i}$. This result will be extensively
used when analysing the cost of the edges adjacent to $N$.

######  Lemma B.2.

It holds for every $1\leqslant i\leqslant\ell$ and every extended critical
node $N\in\mathcal{S}_{i}$ that

$\left|\mathrm{parent}_{\mathcal{T}_{\mathsf{MS}}}(N)\right|\leqslant
6k\cdot\left|\mathrm{parent}_{\mathbb{T}_{i}}(N)\right|.$

###### Proof.

Suppose the extended dense branch of $\mathbb{T}_{i}$ is
$(A_{0},\dots,A_{i_{\mathrm{max}}-1})$ for some
$i_{\mathrm{max}}\in\mathbb{Z}_{\geqslant 0}$, with $B_{j}$ being the sibling
of $A_{j}$ and $A_{i_{\mathrm{max}}-1}$ having children
$A_{i_{\mathrm{max}}},B_{i_{\mathrm{max}}}$. Recall that the set of extended
critical nodes is
$\mathcal{S}_{i}=\\{B_{1},\dots,B_{i_{\mathrm{max}}},A_{i_{\mathrm{max}}}\\}$.
By construction of the degree-based tree, we know from Lemma A.6 that it holds
for all $1\leqslant j\leqslant i_{\mathrm{max}}-1$ that
$|A_{j}|=2\cdot|A_{j+1}|$, which implies that $|B_{j+1}|=|A_{j+1}|$ and
$|B_{j}|=2\cdot|B_{j+1}|$ for all $j\geqslant 2$. Thus, we conclude that for
every interval $\left(2^{s-1},2^{s}\right]$, for some
$s\in\mathbb{Z}_{\geqslant 0}$, there are at most $3$ critical nodes101010We
remark that, in the worst case, all three nodes $B_{1},B_{i_{\mathrm{max}}}$
and $A_{i_{\mathrm{max}}}$ could have size in $(2^{s-1},2^{s}]$.
$N\in\mathcal{S}_{i}$ of size $|N|\in\left(2^{s-1},2^{s}\right]$. Now let us
fix $N\in\mathcal{S}_{i}$. By construction, we have that

$\left|\mathrm{parent}_{\mathbb{T}_{i}}(N)\right|\geqslant 2\cdot|N|.$ (B.2)

On the other hand, by the construction of $\mathcal{T}_{\mathsf{MS}}$ we have
that

$\displaystyle\left|\mathrm{parent}_{\mathcal{T}_{\mathsf{MS}}}(N)\right|$
$\displaystyle=\sum_{j=1}^{\ell}\sum_{\begin{subarray}{c}M\in\mathcal{S}_{j}\\\
|M|\leqslant|N|\end{subarray}}|M|\leqslant\sum_{j=1}^{\ell}\sum_{s=0}^{\lceil\log{|N|}\rceil}\sum_{\begin{subarray}{c}M\in\mathcal{S}_{j}\\\
2^{s-1}<|M|\leqslant 2^{s}\end{subarray}}|M|$
$\displaystyle\leqslant\sum_{j=1}^{\ell}\sum_{s=0}^{\lceil\log{|N|}\rceil}3\cdot
2^{s}\leqslant\sum_{j=1}^{k}3\cdot 2^{\lceil\log{|N|}\rceil+1}\leqslant
12k\cdot|N|.$ (B.3)

By combining (B.2) and (B.3), we have that

$\left|\mathrm{parent}_{\mathcal{T}_{\mathsf{MS}}}(N)\right|\leqslant
12k\cdot|N|\leqslant 6k\cdot\left|\mathrm{parent}_{\mathbb{T}_{i}}(N)\right|,$

which proves the statement. ∎

Now we prove the two main technical lemmas of this subsection.

######  Lemma B.3.

It holds that $\sum_{e\in
E_{1}}\mathsf{cost}_{\mathcal{T}_{\mathsf{MS}}}(e)=O\left(k/\phi_{\mathrm{in}}^{8}\right)\cdot\mathsf{OPT}_{G}$.

###### Proof.

Notice that

$\sum_{e\in
E_{1}}\mathsf{cost}_{\mathcal{T}_{\mathsf{MS}}}(e)=\sum_{i=1}^{\ell}\sum_{e\in
E[G[C_{i}]]}\mathsf{cost}_{\mathcal{T}_{\mathsf{MS}}}(e).$

We prove that, for every $1\leqslant i\leqslant\ell$ and $e\in E[G[C_{i}]]$,
the cost of $e$ in $\mathcal{T}_{\mathsf{MS}}$ and the one in $\mathbb{T}_{i}$
differ by at most a factor of $O(k)$. Combining this with Theorem A.4 will
prove the lemma.

To prove this $O(k)$-factor bound, we fix any $1\leqslant i\leqslant\ell$ and
let $\mathcal{S}_{i}$ be the set of extended critical nodes of $C_{i}$. As the
nodes of $\mathcal{S}_{i}$ form a partition of the vertices of $G[C_{i}]$, any
edge $e\in E[G[C_{i}]]$ satisfies exactly one of the following conditions: (i)
$e$ is inside a critical node; (ii) $e$ is adjacent to a critical node.
Formally, it holds that

$\sum_{e\in
E[G[C_{i}]]}\mathsf{cost}_{\mathcal{T}_{\mathsf{MS}}}(e)=\sum_{\begin{subarray}{c}N\in\mathcal{S}_{i}\\\
e\in
E(N,N)\end{subarray}}\mathsf{cost}_{\mathcal{T}_{\mathsf{MS}}}(e)+\sum_{\begin{subarray}{c}N\in\mathcal{S}_{i}\\\
M\in\mathcal{S}_{i}\setminus\\{N\\}\\\
\left|\mathrm{parent}_{\mathbb{T}_{i}}(M)\right|\leqslant\left|\mathrm{parent}_{\mathbb{T}_{i}}(N)\right|\end{subarray}}\sum_{e\in
E(N,M)}\mathsf{cost}_{\mathcal{T}_{\mathsf{MS}}}(e)$

We first examine the case in which the cost of $e$ in both trees are the same,
i.e., Case (i). Since we do not change the structure of the tree inside any
critical node, it holds that

$\displaystyle\sum_{\begin{subarray}{c}N\in\mathcal{S}_{i}\\\ e\in
E(N,N)\end{subarray}}\mathsf{cost}_{\mathcal{T}_{\mathsf{MS}}}(e)$
$\displaystyle=\sum_{\begin{subarray}{c}N\in\mathcal{S}_{i}\\\ e\in
E(N,N)\end{subarray}}\mathsf{cost}_{\mathbb{T}_{i}}(e).$

For Case (ii), the cost of any such edge increases by at most a factor of
$O(k)$ due to Lemma B.2 and the construction of $\mathcal{T}_{\mathsf{MS}}$.
Formally, let $N\in\mathcal{S}_{i}$ be an arbitrary extended critical node,
and $M\in\mathcal{S}_{i}\setminus\\{N\\}$ be an extended critical node such
that
$\left|\mathrm{parent}_{\mathbb{T}_{i}}(M)\right|\leqslant\left|\mathrm{parent}_{\mathbb{T}_{i}}(N)\right|$.
Firstly, notice that if $\mathrm{parent}_{\mathbb{T}_{i}}(N)$ is the root node
of $\mathbb{T}_{i}$, then for any edge $e\in E(N,M)$ it holds that
$\mathsf{cost}_{\mathbb{T}_{i}}(e)=w_{e}\cdot|\mathbb{T}_{i}|.$ On the other
hand, by the construction of $\mathcal{T}_{\mathsf{MS}}$, we know that
$\mathsf{cost}_{\mathcal{T}_{\mathsf{MS}}}(e)\leqslant 6k\cdot
w_{e}\cdot|\mathbb{T}_{i}|$, so we conclude that
$\mathsf{cost}_{\mathcal{T}_{\mathsf{MS}}}(e)\leqslant
6k\cdot\mathsf{cost}_{\mathbb{T}_{i}}(e)$. Secondly, if
$\mathrm{parent}_{\mathbb{T}_{i}}(N)$ is not the root node of $\mathbb{T}_{i}$
and since
$\left|\mathrm{parent}_{\mathbb{T}_{i}}(M)\right|\leqslant\left|\mathrm{parent}_{\mathbb{T}_{i}}(N)\right|$,
we know that $|M|\leqslant|N|$. Therefore it holds for any edge $e\in E(N,M)$
that

$\mathsf{cost}_{\mathcal{T}_{\mathsf{MS}}}(e)=w_{e}\cdot\left|\mathrm{parent}_{\mathcal{T}_{\mathsf{MS}}}(N)\right|\leqslant
6k\cdot
w_{e}\cdot\left|\mathrm{parent}_{\mathbb{T}_{i}}(N)\right|=6k\cdot\mathsf{cost}_{\mathbb{T}_{i}}(e),$

where the inequality follows by Lemma B.2. Combining the above facts, we have
that

$\sum_{e\in
E_{1}}\mathsf{cost}_{\mathcal{T}_{\mathsf{MS}}}(e)\leqslant\sum_{i=1}^{\ell}6k\cdot\sum_{e\in
E[G[C_{i}]]}\mathsf{cost}_{\mathbb{T}_{i}}(e)\leqslant\sum_{i=1}^{\ell}6k\cdot\mathsf{COST}_{G[C_{i}]}(\mathbb{T}_{i}).$
(B.4)

On the other side, let $\mathcal{T}^{*}$ be any optimal HC tree of $G$ with
cost $\mathsf{OPT}_{G}$, and it holds that

$\mathsf{OPT}_{G}\geqslant\sum_{i=1}^{\ell}\mathsf{OPT}_{G[C_{i}]}=\sum_{i=1}^{\ell}\Omega\left(\Phi_{G[C_{i}]}^{4}\right)\cdot\mathsf{COST}(\mathbb{T}_{i})=\sum_{i=1}^{\ell}\Omega\left(\phi_{\mathrm{in}}^{8}\right)\cdot\mathsf{COST}(\mathbb{T}_{i}),$
(B.5)

where the last equality follows by Property (A2) of Lemma A.10 and Theorem A.4
applied to every $G[C_{i}]$. Finally, by combining (B.4) and (B.5) we have
that

$\sum_{e\in
E_{1}}\mathsf{cost}_{\mathcal{T}_{\mathsf{MS}}}(e)=O(k/\phi_{\mathrm{in}}^{8})\cdot\mathsf{OPT}_{G},$

which proves the lemma. ∎

######  Lemma B.4.

It holds that

$\sum_{e\in
E_{2}}\mathsf{cost}_{\mathcal{T}_{\mathsf{MS}}}(e)=O\left(k^{2}/\phi_{\mathrm{in}}^{10}\right)\cdot\mathsf{OPT}_{G}.$

###### Proof.

For the edges $e\in E_{2}$, we bound the cost with the help of Lemma B.2
similar as before. Specifically, we have that

$\displaystyle\sum_{e\in E_{2}}\mathsf{cost}_{\mathcal{T}_{\mathsf{MS}}}(e)$
$\displaystyle\leqslant\sum_{i=1}^{\ell}\sum_{\begin{subarray}{c}N\in\mathcal{S}_{i}\\\
M\in\mathcal{S}\setminus\mathcal{S}_{i}\\\
|M|\leqslant|N|\end{subarray}}\sum_{\begin{subarray}{c}e\in
E(N,M)\end{subarray}}\mathsf{cost}_{\mathcal{T}_{\mathsf{MS}}}(e)$
$\displaystyle\leqslant\sum_{i=1}^{\ell}\sum_{N\in\mathcal{S}_{i}}\left|\mathrm{parent}_{\mathcal{T}_{\mathsf{MS}}}(N)\right|\cdot
w(N,V\setminus C_{i})$
$\displaystyle\leqslant\sum_{i=1}^{\ell}\sum_{N\in\mathcal{S}_{i}}36k(k+1)\cdot\left|\mathrm{parent}_{\mathbb{T}_{i}}(N)\right|\cdot\mathrm{vol}_{G[C_{i}]}(N)$
(B.6) $\displaystyle\leqslant
36k(k+1)\cdot\sum_{i=1}^{\ell}\frac{4}{\Phi_{G[C_{i}]}}\cdot\mathsf{COST}_{G[C_{i}]}(\mathbb{T}_{i})$
(B.7)
$\displaystyle=O(k^{2})\cdot\sum_{i=1}^{\ell}\frac{1}{\Phi_{G[C_{i}]}^{5}}\cdot\mathsf{OPT}_{G[C_{i}]}$
(B.8) $\displaystyle=O(k^{2}/\phi_{\mathrm{in}}^{10})\cdot\mathsf{OPT}_{G},$

where (B.6) follows from Property $(A3^{*})$ of Lemma A.10 and Lemma B.2,
(B.7) follows by Lemma A.3, and (B.8) follows by Theorem A.4 applied to every
induced subgraph $G[C_{i}]$. ∎

Finally, we are ready to prove Lemma B.1.

###### Proof of Lemma B.1.

Let $C_{1},\ldots C_{\ell}$ be the partitioned returned by the algorithm from
Lemma A.10. Let $\mathcal{S}\triangleq\bigcup_{i=1}^{k}\mathcal{S}_{i}$ be the
set of all critical nodes, and $\mathcal{T}_{\mathrm{CC}}$ be the
“caterpillar” style tree on the critical nodes according to an increasing
order of their sizes. We have that

$\displaystyle\mathsf{COST}_{G}(\mathcal{T}_{\mathsf{MS}})$
$\displaystyle=\sum_{e\in
E_{1}}\mathsf{cost}_{\mathcal{T}_{\mathsf{MS}}}(e)+\sum_{e\in
E_{2}}\mathsf{cost}_{\mathcal{T}_{\mathsf{MS}}}(e)$
$\displaystyle=O(k/\phi_{\mathrm{in}}^{8})\cdot\mathsf{OPT}_{G}+O(k^{2}/\phi_{\mathrm{in}}^{10})\cdot\mathsf{OPT}_{G}$
$\displaystyle=O(k^{2}/\phi_{\mathrm{in}}^{10})\cdot\mathsf{OPT}_{G}$
$\displaystyle=O(k^{22}/\lambda_{k+1}^{10})\cdot\mathsf{OPT}_{G},$

where the second equality follows by Lemmas B.3 and B.4, and the last equality
follows by the definition of $\phi_{\mathrm{in}}$. ∎

###  B.2 Proof of Lemmas 5.2 and 5.3

Now we prove Lemma 5.2 and Lemma 5.3, which allow us to approximate the cost
of $\mathcal{T}_{\mathsf{MS}}$. To sketch the main proof idea for Lemma 5.3,
we construct a tree $\mathcal{T}_{\mathsf{MS}}^{\prime\prime}$ and upper bound
its weighted Dasgupta cost on the bucketing $B$, i.e.,
$\mathsf{WCOST}_{G/\mathcal{B}}\left(\mathcal{T}_{\mathsf{MS}}^{\prime\prime}\right)$,
with respect to $\mathsf{OPT}_{G}$. To construct
$\mathcal{T}_{\mathsf{MS}}^{\prime\prime}$, we start with the tree
$\mathcal{T}_{\mathsf{MS}}$ on $G$, whose upper bound with respect to
$\mathsf{OPT}_{G}$ is known because of Lemma B.1. We then transform
$\mathcal{T}_{\mathsf{MS}}$ into $\mathcal{T}_{\mathsf{MS}}^{\prime\prime}$ in
two steps, such that there is only a small induced cost for both
transformations. This allows us to upper bound
$\mathsf{COST}_{G}(\mathcal{T}_{\mathsf{MS}}^{\prime\prime})$ with respect to
$\mathsf{COST}_{G}(\mathcal{T}_{\mathsf{MS}})$. Crucially, we can approximate
the tree $\mathcal{T}_{\mathsf{MS}}$ with Algorithm 1 _without_ explicitly
constructing tree $\mathcal{T}_{\mathsf{MS}}$. The proof for Lemma 5.2 follows
from the proof for Lemma 5.3.

In order to analyse the constructed trees $\mathcal{T}_{\mathsf{MS}}^{\prime}$
and $\mathcal{T}_{\mathsf{MS}}^{\prime\prime}$, we analyse the properties of
the buckets in the context of the entire graph $G$, and not just on every set
$P_{i}$ returned by spectral clustering. We denote by $\mathcal{B}$ the set
containing all the buckets obtained throughout all sets $P_{i}$, i.e.,

$\mathcal{B}\triangleq\bigcup_{i=1}^{k}\mathcal{B}_{i};$

notice that $\mathcal{B}$ is a partition of $V$. We use

$\kappa\triangleq|\mathcal{B}|$

to denote the total number of buckets. For convenience, we label the buckets
$\mathcal{B}=\\{B_{1},\dots,B_{\kappa}\\}$ arbitrarily, and in general we
always refer to a bucket $B_{j}\in\mathcal{B}$ with the subscript $j$.

Next, we also analyse the properties of the extended critical nodes in the
context of the entire graph $G$, not just from every set $\mathcal{S}_{i}$.
Therefore, let

$\mathcal{S}=\bigcup_{i=1}^{\ell}\mathcal{S}_{i}$

be the set of all extended critical nodes, and we label them as
$\mathcal{S}=\\{N_{1},\ldots N_{k_{1}}\\}$ in the order they appear in if one
would travel upwards starting from the bottom of the caterpillar tree
$\mathcal{T}_{\mathsf{MS}}$. In general, we always refer to an extended
critical node $N_{i}\in\mathcal{S}$ with the subscript $i$. We use $C(N_{i})$
to denote the original cluster that $N_{i}$ belongs to, i.e, the cluster
$C(N_{i})$ is the $C_{s}$ such that $N_{i}\in\mathcal{S}_{s}$. We also use
$\mathbb{T}_{\mathrm{deg}}(N_{i})$ to denote the tree
$\mathbb{T}_{\mathrm{deg}}$ that $N_{i}$ originally corresponds to. To avoid
confusion, we remind the reader that $\mathbb{T}_{i}$ is the degree-based tree
constructed on the induced graph $G[C_{i}]$, i.e.,
$\mathbb{T}_{i}=\mathbb{T}_{\mathrm{deg}}(G[C_{i}])$.

Next, we define

$X_{j}\triangleq\\{N_{i}\in\mathcal{S}|N_{i}\cap B_{j}\neq\emptyset\\}$

as the set of critical nodes that have non-empty intersection with bucket
$B_{j}\in\mathcal{B}$. Note that the subscript of $X_{j}$ matches the one of
the corresponding bucket $B_{j}$. We then define the _anchor_ (critical) node
$N_{i^{\prime}}\in\mathcal{S}$ of the set $X_{j}$ as the largest critical node
inside $X_{j}$. i.e., we have that

$N_{i^{\prime}}\triangleq\operatorname{argmax}_{N_{i^{\prime\prime}}\in
X_{j}}|N_{i^{\prime\prime}}|,$

where ties are broken by choosing $N_{i^{\prime}}$ to be the critical node
highest up in $\mathcal{T}_{\mathsf{MS}}$. These anchor nodes corresponding to
the sets $X_{j}$ – and therefore the buckets $B_{j}\in\mathcal{B}$ – are the
key in our proof of the approximation factor of our algorithm; they determine
the locations in the tree $\mathcal{T}_{\mathsf{MS}}$ where we group together
the buckets $B_{j}\in\mathcal{B}$. It is also important to note that for every
$X_{j}$ its anchor node is determined _uniquely_. On the other hand, any
$N_{i}\in\mathcal{S}$ might be the anchor node for multiple $X_{j}$’s.

Now we’re ready to describe the two transformations.

_Step 1: Splitting the Critical Nodes._ In this first step, we transform the
tree $\mathcal{T}_{\mathsf{MS}}$ such that all the sets $N_{i}\cap B_{j}$ for
$1\leqslant i\leqslant k_{1}$ and $1\leqslant j\leqslant\kappa$ are separated
and restructured to form a caterpillar tree. This is done by splitting every
$N_{i}$ into $N_{i}\cap B_{j}$ for all $1\leqslant j\leqslant\kappa$ and
appending them next to each other arbitrarily in the caterpillar tree in the
original location of $N_{i}$ in $\mathcal{T}_{\mathsf{MS}}$.

More formally, we consider the partition of every $N_{i}\in\mathcal{S}$ into
$\\{N_{i}\cap B_{j}\\}_{j=1}^{\kappa}$. Then, for every internal node
$\mathrm{parent}(N_{i})$ in the tree $\mathcal{T}_{\mathsf{MS}}$, we create
new internal nodes $\mathrm{parent}(N_{i}\cap B_{j^{\prime}})$ for every
$N_{i}\cap B_{j^{\prime}}\in\\{N_{i}\cap B_{j}\\}_{j=1}^{\kappa}$, and let one
of the children of each of these be a new internal node corresponding to
$N_{i}\cap B_{j^{\prime}}$, and let the other child be another node
$\mathrm{parent}(N_{i}\cap B_{j^{\prime\prime}})$ for $j^{\prime}\neq
j^{\prime\prime}$. Moreover, we ensure that the ordering (starting from the
bottom) of the new nodes $\mathrm{parent}(N_{i}\cap B_{j})$ along the back of
the caterpillar tree will be such that the first all the ones corresponding to
$N_{1}$ will appear, then $N_{2}$ etc., up until $N_{k_{1}}$.

We call the resulting tree $\mathcal{T}_{\mathsf{MS}}^{\prime}$, whose cost is
bounded in the lemma below.

######  Lemma B.5.

It holds that

$\mathsf{COST}_{G}\left(\mathcal{T}_{\mathsf{MS}}^{\prime}\right)\leqslant\mathsf{COST}_{G}\left(\mathcal{T}_{\mathsf{MS}}\right)+O(k/\phi_{\mathrm{in}}^{10})\cdot\mathsf{OPT}_{G}.$

###### Proof.

First of all, notice that for any edge crossing critical nodes, i.e., $e\in
E(N_{i},N_{i^{\prime}})$ for $i\neq i^{\prime}$, we have that

$\mathsf{cost}_{\mathcal{T}_{\mathsf{MS}}^{\prime}}(e)\leqslant\mathsf{cost}_{\mathcal{T}_{\mathsf{MS}}}(e).$

This is because splitting up the critical nodes cannot increase the size of
the lowest common ancestor of any crossing edge between critical nodes, due to
the caterpillar tree construction. So we don’t need to consider the increase
in the cost of crossing edges between critical nodes.

Next, we study the edges inside critical nodes $e\in E(N_{i},N_{i})$ for any
$i$. These edges’ cost could be increased compared with the one in
$\mathcal{T}_{\mathsf{MS}}$, since they can span across nodes $N_{i}\cap
B_{j}$. However, the increase in size of their lowest common ancestor is by
construction _at most_ $|\mathrm{parent}_{\mathcal{T}_{\mathsf{MS}}}(N_{i})|$,
and therefore the total cost of this transformation can be upper bounded as

$\displaystyle\sum_{i=1}^{k_{1}}\sum_{\begin{subarray}{c}e\in
E(N_{i},N_{i})\end{subarray}}\mathsf{cost}_{\mathcal{T}_{\mathsf{MS}}^{\prime}}(e)\leqslant$
$\displaystyle\sum_{i=1}^{k_{1}}\sum_{\begin{subarray}{c}e\in
E(N_{i},N_{i})\end{subarray}}w(e)\cdot\left|\mathrm{parent}_{\mathcal{T}_{\mathsf{MS}}}(N_{i})\right|$
$\displaystyle\leqslant$
$\displaystyle\sum_{i=1}^{k_{1}}6k\cdot\left|\mathrm{parent}_{\mathbb{T}_{\mathrm{deg}}(N_{i})}(N_{i})\right|\cdot\mathrm{vol}_{G[C(N_{i})]}(N_{i})$
(B.9) $\displaystyle\leqslant$ $\displaystyle
6k\cdot\sum_{s=1}^{\ell}\frac{4}{\Phi_{G[C_{s}]}}\cdot\mathsf{COST}_{G[C_{s}]}(\mathbb{T}_{s})$
(B.10) $\displaystyle=$ $\displaystyle
O(k)\cdot\sum_{s=1}^{\ell}\frac{1}{\Phi_{G[C_{s}]}^{5}}\cdot\mathsf{OPT}_{G[C_{s}]}$
(B.11) $\displaystyle=$ $\displaystyle
O(k/\phi_{\mathrm{in}}^{10})\cdot\mathsf{OPT}_{G},$

where (B.9) follows from Lemma B.2, (B.10) follows from Lemma A.3, and (B.11)
follows from Theorem A.4 applied to every induced subgraph $G[C_{i}]$. This
proves the statement.

∎

$d_{u}$$d_{u}\beta$$d_{u}\beta^{-1}$$\delta_{G}(P_{i})$$d_{u}$$\Delta_{G}(P_{i})$$B(u)$$\mathcal{T}_{\mathsf{MS}}^{\prime}$$N_{i}\cap
B_{1}$$N_{i}\cap B_{2}$$N_{i}\cap B_{\kappa}$

$d_{u}$$d_{u}\beta$$d_{u}\beta^{-1}$$\delta_{G}(P_{i})$$d_{u}$$\Delta_{G}(P_{i})$$B(u)$$\mathcal{T}_{\mathsf{MS}}^{\prime}$$N_{i}\cap
B_{1}$$N_{i}\cap B_{2}$$N_{i}\cap
B_{\kappa}$$\mathcal{T}_{\mathsf{MS}}^{\prime\prime}$$N_{i}\cap
B_{1}$$N_{i}\cap B_{\kappa}$$N_{2}\cap B_{2}$$N_{1}\cap B_{2}$$N_{k_{1}}\cap
B_{2}$

Figure 4: Visualisation of a part of the transformation described in step 2,
where the buckets are grouped. On the left we visualise a section of the tree
$\mathcal{T}_{\mathsf{MS}}^{\prime}$, corresponding to a single critical node
$N_{i}$. For illustration, we assume here that $N_{i}$ is the anchor node for
$X_{2}$. This means that all $N_{i^{\prime}}\cap B_{2}$ for $N_{i^{\prime}}\in
X_{2}\setminus N_{j}$ are moved up into the same subtree, as illustrated on
the right in the new tree $\mathcal{T}_{\mathsf{MS}}^{\prime\prime}$.

_Step 2: Grouping Degree Buckets._ In this second step, we move around the
sets $N_{i}\cap B_{j}$, such that the buckets $B_{1},\ldots,B_{\kappa}$ are
separated after this step.

We do this by traversing the tree $\mathcal{T}_{\mathsf{MS}}^{\prime}$ from
the bottom to the top, and visiting every node $\mathrm{parent}(N_{i}\cap
B_{j})$ up along the “back” of the caterpillar construction. This means we
first visit all the nodes $\mathrm{parent}(N_{i}\cap B_{j})$ corresponding to
$N_{1}$, then $N_{2}$ etc. up to $N_{k_{1}}$. When visiting
$\mathrm{parent}(N_{i}\cap B_{j})$ we check whether $N_{i}$ is an anchor node
of $X_{j}$. If not, we continue travelling up. _If it is_ , we transform the
tree $\mathcal{T}_{\mathsf{MS}}^{\prime}$ by moving up all the internal nodes
$N_{i^{\prime}}\cap B_{j}$ for $N_{i^{\prime}}\in X_{j}\setminus N_{i}$ and
placing them in the same subtree as the internal node corresponding to
$N_{i}\cap B_{j}$. We do so by creating a new root node $R_{B_{j}}$, and we
loop through each $N_{i^{\prime}}\cap B_{j}$ for $N_{i^{\prime}}\in X_{j}$ in
an arbitrary order. In the first iteration, we set the children of $R_{B_{j}}$