# Dynamic Spectral Clustering with Provable Approximation Guarantee

Steinar Laenen  He Sun

###### Abstract

This paper studies clustering algorithms for dynamically evolving graphs
$\\{G_{t}\\}$, in which new edges (and potential new vertices) are added into
a graph, and the underlying cluster structure of the graph can gradually
change. The paper proves that, under some mild condition on the cluster-
structure, the clusters of the final graph $G_{T}$ of $n_{T}$ vertices at time
$T$ can be well approximated by a dynamic variant of the spectral clustering
algorithm. The algorithm runs in amortised update time $O(1)$ and query time
$o(n_{T})$. Experimental studies on both synthetic and real-world datasets
further confirm the practicality of our designed algorithm.

graph clustering, spectral graph theory

##  1 Introduction

For any graph $G=(V,E)$ and parameter $k\in\mathbb{N}$ as input, the objective
of graph clustering is to partition the vertex set of $G$ into $k$ clusters
such that vertices within each cluster are better connected than to the rest
of the graph. Since large-scale graphs are commonly used to model practical
datasets, designing efficient graph clustering algorithms is an important
problem in machine learning and related fields.

In practice, these large-scale graphs usually evolve over time: not only are
new vertices and edges added into a graph, but the graph’s clusters could also
change gradually, resulting in a new cluster-structure in the long term.
Instead of periodically running a clustering algorithm from scratch, it is
important to design algorithms that can quickly identify and return the new
clusters in dynamically evolving graphs.

In this paper we study clustering for dynamically evolving graphs, and obtain
the following results. As the first and conceptual contribution, we propose a
model for dynamic graph clustering. In contrast to the classical model for
dynamic graph algorithms (Thorup, 2007; Beimel et al., 2022), our proposed
model considers not only edge insertions but also vertex insertions; as such
the underlying graph can gradually form a new cluster-structure with a
different number of clusters from the initial graph.

As the second and algorithmic result, we design a randomised graph clustering
algorithm that works in the above-mentioned model, and our result is as
follows:

######  Theorem 1.1 (Informal statement of Theorem 4.6).

Let $G_{1}=(V_{1},E_{1})$ be a graph of $n_{1}$ vertices and
$k=\widetilde{O}(1)$ clusters.111We use $\widetilde{O}(n)$ to represent
$O(n\cdot\log^{c}(n))$ for constant $c$. Assume that new edges, which could be
adjacent to new vertices, are added to $G_{t}$ at each time $t$ to obtain
$G_{t+1}$, and there are $O(\operatorname{poly}(n_{1}))$ added edges in total
at time $T=O(\operatorname{poly}(n_{1}))$ to form $G_{T}$ of $n_{T}$ vertices
and $k^{\prime}$ clusters. Then, there is a randomised algorithm such that the
following hold with high probability:

  * •

The initial $k$ clusters of $G_{1}$ can be approximately computed in
$\widetilde{O}(|E_{1}|)$ time.

  * •

The new $k^{\prime}$ clusters of $G_{T}$ can be approximately computed with
amortised update time $O(1)$ and query time $o(n_{T})$.

To examine the result, we notice that, although the number of clusters $k$ in
$G_{1}$ can be identified with the classical eigen-gap heuristic (Ng et al.,
2001; von Luxburg, 2007), computing an eigen-gap is expensive and cannot be
directly applied to determine the change of $k$ in dynamically evolving
graphs. Our result shows that the new number of clusters $k^{\prime}$ can be
computed by a dynamic clustering algorithm with sublinear query time.
Secondly, as the running time of a clustering algorithm is at least linear in
the number of edges in $G_{T}$ and it takes $\Omega(n_{T})$ time to output the
cluster membership of all the vertices, obtaining an $o(n_{T})$ amortised
query time222Throughout the paper we use $T$ to denote query time, and $t$ as
arbitrary time throughout the sequence of graphs $\\{G_{t}\\}$. is
significant. To the best of our knowledge, our work presents the first such
result with respect to theoretical guarantees of the output clusters, and time
complexity.

Our algorithm not only achieves strong theoretical guarantees, but also works
very well in practice. For instance, for input graphs with 300,000 vertices
and up to 490,000,000 edges generated from the stochastic block model, our
algorithm runs more than 100 times faster than repeated execution of spectral
clustering on the updated graphs, while obtaining a comparable clustering
result.

###  1.1 Overview of the Algorithm

For any input graph $G_{1}$ with a well-defined cluster structure, we first
construct a _cluster-preserving sparsifier_ $H_{1}$ of $G_{1}$, which is a
sparse subgraph of $G_{1}$ that maintains its cluster-structure, and employ
spectral clustering on $H_{1}$ to obtain the initial $k$ clusters of $G_{1}$.
After this, with a new edge arriving at every time $t$, our designed algorithm
applies two components to track the cluster-structure of $G_{t}$.

The first component is a dynamic algorithm that maintains a cluster-preserving
sparsifier $H_{t}$ for $G_{t}$. Our designed algorithm is based on sampling
edges with probability proportional to the degrees of their endpoints, and
these edges get resampled if their degrees have significantly changed. We show
that $H_{t}$ always preserves the cluster-structure of $G_{t}$, and the
algorithm’s amortised update time complexity is $O(1)$.

Our second component is an algorithm that dynamically maintains a _contracted
graph_ $\widetilde{G}_{t}$ of $G_{t}$, and this contracted graph is used to
sketch the cluster-structure of $G_{t}$. For the first input graph $G_{1}$ and
the output of spectral clustering on $H_{1}$, our initial contracted graph
$\widetilde{G}_{1}$ consists of $k$ super vertices with self-loops: these
super vertices correspond to the $k$ clusters in $G_{1}$, and are connected by
edges with weight equal to the cut values of the corresponding clusters in
$H_{1}$. After that, when new edges (and potentially new vertices) arrive over
time, our algorithm updates $\widetilde{G}_{t}$ such that (new) clusters are
represented by either the same super vertices, newly added vertices, or a
combination of both. The algorithm further updates the edge weights between
the super vertices. With slight increase in the number of vertices of
$\widetilde{G}_{t}$ over time, we prove that the cluster-structure in $G_{t}$
is approximately preserved in $\widetilde{G}_{t}$. In particular, when new
clusters are formed in $G_{t}$, this new cluster-structure of $G_{t}$ can be
identified by the eigen-gap of $\widetilde{G}_{t}$’s Laplacian matrix. See
Figure 1 for the illustration of our approach.

###  1.2 Related work

Our work directly relates to a number of works on incremental spectral
clustering algorithms (e.g., (Dhanjal et al., 2014; Martin et al., 2018; Ning
et al., 2007)). These works usually rely on analysing the change of
approximate eigenvectors and don’t show the approximation guarantee of the
returned clusters. Many works along this direction further employ matrix
perturbation theory in their analysis, requiring that the total number of
vertices in a graph is fixed.

Our work is also linked to related dynamic graph algorithm problems (e.g.,
(Bernstein et al., 2022; Saranurak & Wang, 2019)). However, most works in
dynamic graph algorithms focus on the design of dynamic algorithms in a
_general_ graph, while for dynamic clustering one needs to assume the presence
of cluster-structures in the initial and final graphs, such that the
algorithm’s performance can be rigorously analysed. Nevertheless, some of our
presented techniques, like the adaptive sampling, are inspired by the dynamic
graph algorithms literature.

##  2 Preliminaries

$G_{t}$$G_{t^{\prime}}$$H_{t}$$\widetilde{G}_{t}$Sparsify$H_{t^{\prime}}$$\widetilde{G}_{t^{\prime}}$Cluster
+ contractGraph updateDynamic sparsifierDynamic contracted graph(a)(b)(c)

Figure 1: Illustration of our technique. The black and red edges in Figure (a)
are the edges in $G_{t}$ and the added ones in $G_{t^{\prime}}$; the dashed
black and red edges in Figure (b) are the ones added in $H_{t}$ and
$H_{t^{\prime}}$; the black and red edges in Figure (c) are the ones in
$\widetilde{G}_{t}$ and $\widetilde{G}_{t^{\prime}}$.

###  2.1 Notation

Let $G=(V,E,w)$ be 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_{G}(u,v)$ or $w_{G}(e)$ to express the
weight of $e$. For a vertex $u\in V$, we denote its _degree_ by
$\mathrm{deg}_{G}(u)\triangleq\sum_{v\in V}w_{G}(u,v)$, and the volume for any
$S\subseteq V$ is defined as $\mathrm{vol}_{G}(S)\triangleq\sum_{u\in
S}\mathrm{deg}_{G}(u)$. For any $S,T\subset V$, we define the _cut value_
between $S$ and $T$ by $w_{G}(S,T)\triangleq\sum_{e\in E_{G}(S,T)}w_{G}(e)$,
where $E_{G}(S,T)$ is the set of edges between $S$ and $T$. Moreover, for any
$S\subset V$, the conductance of $S$ is defined as

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

if $S\neq\emptyset$, and $\Phi_{G}(S)=1$ if $S=\emptyset$. 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_{G}(k)\triangleq\min_{\mathrm{partitions\>}A_{1},\dots,A_{k}}\max_{1\leqslant
i\leqslant k}\Phi_{G}(A_{i}).$

Our analysis is based on the spectral properties of graphs, and we list the
basics of spectral graph theory. For a graph $G=(V,E,w)$, let
$D_{G}\in\mathbb{R}^{n\times n}$ be the diagonal matrix defined by
$D_{G}(u,u)=\mathrm{deg}_{G}(u)$ for all $u\in V$. We denote by
$A_{G}\in\mathbb{R}^{n\times n}$ the _adjacency matrix_ of $G$, where
$A_{G}(u,v)=w_{G}(u,v)$ for all $u,v\in V$. The _normalised Laplacian matrix_
of $G$ is defined as $\mathcal{L}_{G}\triangleq
I-D_{G}^{-1/2}A_{G}D_{G}^{-1/2}$, where $I$ is the $n\times n$ identity
matrix. The normalised Laplacian $\mathcal{L}_{G}$ is symmetric and real-
valued, and has $n$ real eigenvalues which we write as
$0=\lambda_{1}(\mathcal{L}_{G})\leqslant\ldots\leqslant\lambda_{n}(\mathcal{L}_{G})\leqslant
2$; we use $f_{i}\in\mathbb{R}^{n}(1\leqslant i\leqslant n)$ to express the
eigenvector of $\mathcal{L}_{G}$ corresponding to $\lambda_{i}$.

######  Lemma 2.1 (Higher-order Cheeger inequality, (Lee et al., 2014)).

There is an absolute constant $C_{\ref{lem:Higher Cheeger}}$ such that it
holds for any graph $G$ and $k\geqslant 2$ that

$\frac{\lambda_{k}(\mathcal{L}_{G})}{2}\leqslant\rho_{G}(k)\leqslant
C_{\ref{lem:Higher Cheeger}}\cdot k^{3}\sqrt{\lambda_{k}(\mathcal{L}_{G})}.$
(1)

###  2.2 Spectral Clustering

Spectral clustering is a popular clustering algorithm used in practice (Ng et
al., 2001), and it can be described with a few lines of code (Algorithm 1).

Algorithm 1 $\mathsf{SpectralClustering}(G,k)$

1: Input: Graph $G=(V,E,w)$, number of clusters $k\in\mathbb{N}$

2: Output: Partitioning $P_{1},\ldots,P_{k}$

3: Compute eigenvectors $f_{1},\ldots,f_{k}$ of $\mathcal{L}_{G}$

4: for $u\in V$ do

5:
$F(u)\leftarrow\frac{1}{\sqrt{\mathrm{deg}_{G}(u)}}\cdot(f_{1}(u),\ldots,f_{k}(u))^{\intercal}$

6: end for

7: $P_{1},\ldots,P_{k}\leftarrow k\mbox{-means}(\\{F(u)\\}_{u\in V},k)$

8: Return $P_{1},\ldots,P_{k}$

To analyse the performance of spectral clustering, we examine the scenario in
which there is a large gap between $\lambda_{k+1}(\mathcal{L}_{G})$ and
$\rho_{G}(k)$. By the higher-order Cheeger inequality, a low value of
$\rho_{G}(k)$ ensures that $V$ can be partitioned into $k$ clusters, each of
which has conductance at most $\rho_{G}(k)$; on the other hand, a large value
of $\lambda_{k+1}(\mathcal{L}_{G})$ implies that any $(k+1)$ partition of $V$
would introduce some $A\subset V$ with
$\Phi_{G}(A)\geqslant\rho_{G}(k+1)\geqslant\lambda_{k+1}(\mathcal{L}_{G})/2$.
Based on this, Peng et al. (2017) introduced the parameter

$\Upsilon_{G}(k)\triangleq\frac{\lambda_{k+1}(\mathcal{L}_{G})}{\rho_{G}(k)},$
(2)

and showed that a large value of $\Upsilon_{G}(k)$ is sufficient to guarantee
a good performance of spectral clustering. They further showed that, for a
graph $G$ with $m$ edges, spectral clustering runs in $O(m\cdot\log^{\beta}m)$
time for constant $\beta\in\mathbb{R}^{+}$.

For convenience of notation, we always order the output of spectral clustering
by $P_{1},\ldots,P_{k}$ such that
$\mathrm{vol}_{G}(P_{1})\leqslant\ldots\leqslant\mathrm{vol}_{G}(P_{k})$.

###  2.3 Model for Dynamic Graph Clustering

We assume that the initial graph $G_{1}=(V_{1},E_{1})$ with $n_{1}$ vertices
satisfies $\lambda_{k+1}(\mathcal{L}_{G_{1}})=\Omega(1)$ and
$\rho_{G_{1}}(k)=O(k^{-8}\log^{-2\gamma}(n_{1}))$ for some constant
$\gamma\in\mathbb{R}^{+}$. This condition is similar to lower bounding
$\Upsilon_{G_{1}}(k)$, and ensures that the initial input graph $G_{1}$ has
$k$ well-defined clusters. After this, the underlying graph is updated through
an edge insertion at each time, and let $G_{t}=(V_{t},E_{t})$ be the graph
constructed at time $t$. We assume that every edge insertion introduces at
most one new vertex; as such the underlying graph is always connected, and the
number of vertices $n_{t}\triangleq|V_{t}|$ could increase over time. We
further assume that, after every $\Theta(\log^{\gamma}(n_{t}))$ steps, there
is time $t^{\prime}$ such that
$G_{t^{\prime}}=(V_{t^{\prime}},E_{t^{\prime}})$ presents a well-defined
structure of $k^{\prime}$ clusters, which is characterised by
$\lambda_{k^{\prime}+1}(\mathcal{L}_{G_{t^{\prime}}})=\Omega(1)$ and
$\rho_{G_{t^{\prime}}}(k^{\prime})=O(k^{\prime-8}\cdot\log^{-2\gamma}(n_{t^{\prime}}))$
for some $k^{\prime}\in\mathbb{N}$.

Notice that, since both the number of vertices $n_{t}$ in time $t$ and the
number of clusters could change, our above-defined _dynamic gap assumption_
allows the underlying graph to gradually form a new cluster structure, e.g.,
$O(\log^{\gamma}(n_{1}))$ newly added vertices and their adjacent edges could
initially form a small new cluster which gradually “grows” into a large one.
On the other side, our assumption prevents the disappearance of the underlying
graph’s cluster-structure throughout the edge updates, which would make the
objective function of a clustering algorithm ill-defined.

##  3 Dynamic Cluster-Preserving Sparsifiers

A graph sparsifier is a sparse representation of an input graph that inherits
certain properties of the original dense graph, and their efficient
construction plays a key role in designing a number of nearly-linear time
graph algorithms. However, typical constructions of graph sparsifiers are
based on fast Laplacian solvers, making them difficult to implement in
practice. To overcome this, Sun & Zanetti (2019) studied a variant of graph
sparsifiers for graph clustering, and introduced the notion of a cluster-
preserving sparsifier:

######  Definition 3.1 (Cluster-preserving sparsifier).

Let $G=(V,E)$ be any graph with $k$ clusters, and $\\{S_{i}\\}^{k}_{i=1}$ a
$k$-way partition of $G$ corresponding to $\rho_{G}(k)$. We call a re-weighted
subgraph $H=(V,F\subset E,w_{H})$ a cluster-preserving sparsifier of $G$ if
(i) $\Phi_{H}(S_{i})=O(k\cdot\Phi_{G}(S_{i}))$ for $1\leqslant i\leqslant k$,
and (ii)
$\lambda_{k+1}(\mathcal{L}_{H})=\Omega(\lambda_{k+1}(\mathcal{L}_{G}))$.

To examine the two conditions of Definition 3.1, notice that graph $G=(V,E)$
has exactly $k$ clusters if (i) $G$ has $k$ disjoint subsets
$S_{1},\ldots,S_{k}$ of low conductance, and (ii) any $(k+1)$-way partition of
$G$ would include some $A\subset V$ of high conductance, which would be
implied by a lower bound on $\lambda_{k+1}(\mathcal{L}_{G})$ due to (1). With
the well-known eigen-gap heuristic and theoretical analysis on spectral
clustering (Peng et al., 2017), these two conditions ensure that the $k$
optimal clusters in $G$ have low conductance in $H$ as well.

###  3.1 The SZ Algorithm

We first present the algorithm in (Sun & Zanetti, 2019) for constructing a
cluster-preserving sparsifier; we call it the SZ algorithm for simplicity.
Given any input graph $G=(V,E)$, the algorithm computes

$p_{u}(v)\triangleq\min\left\\{C\cdot\frac{1}{\lambda_{k+1}(\mathcal{L}_{G})}\cdot\frac{\log
n}{\mathrm{deg}_{G}(u)},1\right\\}$
$p_{v}(u)\triangleq\min\left\\{C\cdot\frac{1}{\lambda_{k+1}(\mathcal{L}_{G})}\cdot\frac{\log
n}{\mathrm{deg}_{G}(v)},1\right\\},$

for every $e=\\{u,v\\}$, where $C\in\mathbb{R}^{+}$ is some constant.

Then, the algorithm samples $e=\\{u,v\\}$ with probability $p_{e}\triangleq
p_{u}(v)+p_{v}(u)-p_{u}(v)\cdot p_{v}(u)$, and sets the weight of every
sampled $e=\\{u,v\\}$ in $H$ as $w_{H}(u,v)\triangleq 1/p_{e}$. By setting $F$
as the set of the sampled edges, the algorithm returns $H=(V,F,w_{H})$. Sun &
Zanetti (2019) proved that, with high probability, $H$ has $\widetilde{O}(n)$
edges and is a cluster-preserving sparsifier of $G$.

On the other side, while Definition 3.1 shows that the optimal clusters
$S_{i}~{}(1\leqslant i\leqslant k)$ of $G$ have low conductance in $H$, it
doesn’t build the connection _from_ the vertex sets of low conductance in $H$
_to_ the ones in $G$. In this paper, we prove that such a connection holds as
well; this allows us to apply spectral clustering on $H$, and reason about the
conductance of its returned clusters in $G$.

######  Lemma 3.2.

Let $G$ be a graph with $\Upsilon_{G}(k)=\Omega(k)$ for some $k\in\mathbb{N}$
with optimal clusters $\\{S_{i}\\}_{i=1}^{k}$, and $H$ its cluster preserving
sparsifier. Let $\\{P_{i}\\}_{i=1}^{k}$ be the output of spectral clustering
on $H$, and without loss of generality let the optimal correspondence of
$P_{i}$ be $S_{i}$ for any $1\leqslant i\leqslant k$. Then, it holds with high
probability for any $1\leqslant i\leqslant k$ that

$\mathrm{vol}_{G}(P_{i}\triangle
S_{i})=O\left(\frac{k^{2}}{\Upsilon_{G}(k)}\right)\cdot\mathrm{vol}_{G}(S_{i}),$
$\Phi_{G}(P_{i})=O\left(\Phi_{G}(S_{i})+\frac{k^{2}}{\Upsilon_{G}(k)}\right),$

where $A\triangle B\triangleq(A\setminus B)\cup(B\setminus A)$.

###  3.2 Construction of Dynamic Cluster-Preserving Sparsifiers

Now we design an algorithm that constructs a cluster-preserving sparsifier
under edge and vertex insertions, and our algorithm works as follows.
Initially, for the input $G_{1}$ with $n_{1}$ vertices, a well-defined
structure of $k$ clusters and

$\tau\geqslant\frac{C}{\lambda_{k+1}(\mathcal{L}_{G_{1}})}$ (3)

for some constant $C\in\mathbb{R}^{+}$, we run the SZ algorithm and obtain a
cluster-preserving sparsifier of $G_{1}$. In addition to storing the
sparsifier $H_{1}$ of $G_{1}$, the algorithm employs the vector
$\mathbf{sp}^{*}_{1}$ to store the values
$\log{n_{1}}/\mathrm{deg}_{G_{1}}(u)$ for every vertex $u$, which are used to
sample adjacent edges of vertex $u$. See Algorithms 2 and 3 for formal
description.

Algorithm 2 $\mathsf{SampleEdge}(e,G,\tau)$

1: Input: edge $e=\\{u,v\\}$, graph $G=(V,E)$ of $n$ vertices, parameter
$\tau\in\mathbb{R}^{+}$ Output: edge $e^{\prime}$ with weight $w(e^{\prime})$
$p(u,v)\leftarrow p_{u}(v)+p_{v}(u)-p_{u}(v)\cdot p_{v}(u)$ Sample $e$ with
probability $p(u,v)$

2: if $e$ is sampled then

3: $e^{\prime}\leftarrow e$, $w(e^{\prime})\leftarrow 1/p(u,v)$

4: else

5: $e^{\prime}\leftarrow\emptyset$, $w(e^{\prime})\leftarrow 0$

6: end if

7: Return $e^{\prime}$, $w(e^{\prime})$

Algorithm 3 $\mathsf{StaticSZSparsifier}(G,\tau)$

1: Input: $G=(V,E)$ of $n$ vertices, parameter $\tau\in\mathbb{R}^{+}$

2: Output: Cluster preserving sparsifier $H=(V,F,w_{H})$, degree list
$\mathbf{sp}^{*}$

3: $F\leftarrow\emptyset$

4: for $e\in E$ do

5: $e^{\prime},w(e^{\prime})\leftarrow\mathsf{SampleEdge}(e,G,\tau)$

6: $F\leftarrow F\cup e^{\prime}$, $w_{H}(e)\leftarrow w(e^{\prime})$

7: end for

8: $\mathbf{sp}^{*}\leftarrow\left\\{\frac{\log{n}}{\mathrm{deg}_{G}(u)}\mid
u\in V\right\\}$

9: Return $H$, $\mathbf{sp}^{*}$

Algorithm 4
$\mathsf{UpdateSparsifier}(G_{t},H_{t},\mathbf{sp}^{*}_{t},e,\tau)$

1: Input: $G_{t}=(V_{t},E_{t})$, $H_{t}=(V_{t},F_{t},w_{H_{t}})$,
$\mathbf{sp}^{*}_{t}$, incoming edge $e=\\{u,v\\}$, parameter $\tau$

2: Output: $H_{t+1}=(V_{t+1},F_{t+1},w_{H_{t+1}})$, $\mathbf{sp}^{*}_{t+1}$

3: $V_{\mathrm{new}}\leftarrow\\{u,v\\}\setminus V_{t}$

4: $G_{t+1}\leftarrow(V_{t}\cup V_{\mathrm{new}},E_{t}\cup e)$

5: $H_{t+1}\leftarrow(V_{t}\cup V_{\mathrm{new}},F_{t},w_{H_{t}})$

6: $\mathbf{sp}^{*}_{t+1}\leftarrow\mathbf{sp}^{*}_{t}$

7: if $V_{\mathrm{new}}\neq\emptyset$ then

8: $e^{\prime},w(e^{\prime})\leftarrow\mathsf{SampleEdge}(e,G_{t+1},\tau)$

9: $F_{t+1}\leftarrow F_{t+1}\cup e^{\prime}$, $w_{H_{t+1}}(e)\leftarrow
w(e^{\prime})$

10: if $u\in V_{\mathrm{new}}$ then

11:
$\mathbf{sp}^{*}_{t+1}(u)\leftarrow\frac{\log{n_{t+1}}}{\mathrm{deg}_{G_{t+1}}(u)}$

12: end if

13: if $v\in V_{\mathrm{new}}$ then

14:
$\mathbf{sp}^{*}_{t+1}(u)\leftarrow\frac{\log{n_{t+1}}}{\mathrm{deg}_{G_{t+1}}(v)}$

15: end if

16: end if$V_{\mathrm{doubled}}\leftarrow\Big{\\{}\hat{v}\in V_{t+1}\setminus
V_{\mathrm{new}}\mid\frac{\log{n_{t+1}}}{\mathrm{deg}_{G_{t+1}}(\hat{v})}>2\cdot\mathbf{sp}^{*}_{t}(\hat{v})\text{
or
}\frac{\log{n_{t+1}}}{\mathrm{deg}_{G_{t+1}}(\hat{v})}<\frac{\mathbf{sp}^{*}_{t}(\hat{v})}{2}\Big{\\}}$

17: if $|V_{\mathrm{doubled}}|>0$ then

18: for $\hat{u}\in V_{\mathrm{doubled}}$ do

19: $F_{t+1}\leftarrow F_{t+1}\setminus E_{H_{t+1}}(\hat{u})$

20: for $\hat{e}\in E_{G_{t+1}}\mathrm{\ adjacent\ to\ }\hat{u}$ do

21:
$\hat{e}^{\prime},w(\hat{e}^{\prime})\leftarrow\mathsf{SampleEdge}(\hat{e},G_{t+1},\tau)$

22: $F_{t+1}\leftarrow F_{t+1}\cup\hat{e}^{\prime}$,
$w_{H_{t+1}}(\hat{e})\leftarrow w(\hat{e}^{\prime})$

23: end for

24:
$\mathbf{sp}^{*}_{t+1}(\hat{u})\leftarrow\frac{\log{n_{t+1}}}{\mathrm{deg}_{G_{t+1}}(\hat{u})}$

25: end for

26: else

27: $e^{\prime},w(e^{\prime})\leftarrow\mathsf{SampleEdge}(e,G_{t+1},\tau)$

28: $F_{t+1}\leftarrow F_{t+1}\cup e^{\prime}$, $w_{H_{t+1}}(e)\leftarrow
w(e^{\prime})$

29: end if

30: Return $H_{t+1}$, $\mathbf{sp}^{*}_{t+1}$

Next, given the graph $G_{t}$ currently constructed at time $t$, its
sparsifier $H_{t}$, and edge insertion $e=\\{u,v\\}$, the algorithm compares
for every vertex $w$ the parameter $\log{n_{t+1}}/\mathrm{deg}_{G_{t+1}}(w)$
with $\mathbf{sp}^{*}_{t}(w)$, the quantity used to sample the adjacent edges
of $w$ the last time, and checks whether the two values change significantly.
If it is the case, then the used sampling probability is too far from the
“correct” one when running the static SZ algorithm on $G_{t+1}$, and hence we
resample all the edges adjacent to $w$ with the right sampling probability.
Otherwise, we simply use the values stored in $\mathbf{sp}^{*}_{t}$ to sample
the upcoming edge $e$, and include it in $H_{t+1}$ if $e$ is sampled. See
Algorithm 4 for formal description333Notice that, since
$\lambda_{k+1}(\mathcal{L}_{G_{t}})=\Omega(1)$ for any graph $G_{t}$
exhibiting a well-defined structure of $k$ clusters and it holds for $G_{T}$
at time $T=O(\operatorname{poly}(n_{1}))$ that
$n_{T}=O(\operatorname{poly}(n_{1}))$, i.e., $\log{n_{T}}=O(\log{n_{1}})$, by
setting $C$ to be a sufficiently large constant, $\tau\cdot\log{n_{1}}$ is the
right parameter for defining the sampling probability at time
$T=O(\operatorname{poly}(n_{1}))$., and Theorem 3.3 for its performance:

######  Theorem 3.3.

Let $G_{1}=(V_{1},E_{1})$ be a graph with $n_{1}$ vertices and a well-defined
structure of $k=\widetilde{O}(1)$ clusters, and $\\{G_{t}\\}$ the sequence of
graphs of $\\{n_{t}\\}$ vertices constructed sequentially through an edge
insertion at each time. Assuming graph $G_{T}$ at time
$T=O(\operatorname{poly}(n_{1}))$ has a well-defined structure of
$\widetilde{O}(1)$ clusters and $n_{T}=O(\mathrm{poly}(n_{1}))$, Algorithm 4
returns a cluster-preserving sparsifier $H_{T}=(V_{T},F_{T},w_{H_{T}})$ of
$G_{T}$ with high probability, and $|F_{T}|=\widetilde{O}(n_{T})$. The
algorithm’s amortised running time is $O(1)$ per edge update.

##  4 Dynamic Spectral Clustering Algorithm

This section presents our main dynamic spectral clustering algorithm, and is
organised as follows: In Section 4.1, we present the construction and update
procedure of a contracted graph, which is the data structure that summarises
the cluster structure of an underlying input graph and allows for quick
updates to the clusters. The properties of dynamic contracted graphs are
analysed in Section 4.2. We present the main algorithm and analyse its
performance in Section 4.3.

###  4.1 Construction and Update of Contracted Graphs

For any input graph $G_{t}=(V_{t},E_{t})$ of $n_{t}$ vertices, its dynamic
cluster-preserving sparsifier $H_{t}=(V_{t},F_{t},w_{H_{t}})$, and its $k$
clusters $P_{1},\ldots,P_{k}$ returned from running spectral clustering on
$H_{t}$, we apply Algorithm 5 to construct a contracted graph
$\widetilde{G}_{t}=(\widetilde{V}_{t},\widetilde{E}_{t},w_{\widetilde{G}_{t}})$
of $G_{t}$. Notice that we introduce the set of _non-contracted vertices_
$\widetilde{V}_{t}^{\mathrm{nc}}=\emptyset$, which will be used later.

Algorithm 5 $\mathsf{ContractGraph}(H_{t},\mathcal{P})$

1: Input: Cluster preserving sparsifier $H_{t}=(V_{t},F_{t},w_{H_{t}})$,
partition $\mathcal{P}=\\{P_{1},\ldots P_{k}\\}$

2: Output: Contracted graph
$\widetilde{G}_{t}=(\widetilde{V}_{t},\widetilde{E}_{t},w_{\widetilde{G}_{t}})$

3: Let $p_{i}$ be a representative super vertex for each cluster
$P_{i}\in\mathcal{P}$.

4: $\widetilde{V}_{t}^{\mathrm{c}}\leftarrow\\{p_{i}\mid
P_{i}\in\mathcal{P}\\}$, $\widetilde{V}_{t}^{\mathrm{nc}}\leftarrow\emptyset$

5:
$\widetilde{V}_{t}\leftarrow\widetilde{V}_{t}^{\mathrm{nc}}\cup\widetilde{V}_{t}^{\mathrm{c}}$

6: $\widetilde{E}_{t}\leftarrow\emptyset$

7: for
$\\{p_{i},p_{j}\\}\in\widetilde{V}_{t}^{\mathrm{c}}\times\widetilde{V}_{t}^{\mathrm{c}}$
do

8: $\widetilde{E}_{t}\leftarrow\widetilde{E}_{t}\cup\\{p_{i},p_{j}\\}$

9: $w_{\widetilde{G}_{t}}(p_{i},p_{j})\leftarrow w_{H_{t}}(P_{i},P_{j})$

10: end for

11: Return
$\widetilde{G}_{t}=(\widetilde{V}_{t},\widetilde{E}_{t},w_{\widetilde{G}_{t}})$

######  Lemma 4.1.

The algorithm $\mathsf{ContractGraph}(H_{t},\mathcal{P})$ returns
$\widetilde{G}_{t}=(\widetilde{V}_{t},\widetilde{E}_{t},w_{\widetilde{G}_{t}})$
in $O\left(|F_{t}|\right)$ time.

Next we discuss how the contracted graph is updated under edge and vertex
insertions. Given the graph $G_{t}=(V_{t},E_{t})$ with $n_{t}$ vertices that
satisfies $\lambda_{k+1}(\mathcal{L}_{G_{t}})=\Omega(1)$ and
$\rho_{G_{t}}(k)=O(k^{-8}\log^{-2\gamma}(n_{t}))$ for some constant
$\gamma\in\mathbb{R}^{+}$, its cluster-preserving sparsifier
$H_{t}=(V_{t},F_{t},w_{H_{t}})$, the corresponding contracted graph
$\widetilde{G}_{t}=(\widetilde{V}_{t},\widetilde{E}_{t},w_{\widetilde{G}_{t}})$,
and the upcoming edge insertion $e=\\{u,v\\}$, we construct
$\widetilde{G}_{t+1}$ from $\widetilde{G}_{t}$ as follows:

  * •

If either $u$ or $v$ is a new vertex, the algorithm adds the vertex to
$\widetilde{G}_{t}$ as a non-contracted vertex. The algorithm sets
$V_{\mathrm{new}}=\\{u,v\\}\setminus V_{t}$, and $V_{t+1}=V_{t}\cup
V_{\mathrm{new}}$.

  * •

For every existing vertex $w\in\\{u,v\\}\setminus V_{\mathrm{new}}$ that
belongs to some $P_{i}$, the algorithm checks whether
$\mathrm{deg}_{G_{t+1}}(w)>2\cdot\mathrm{deg}_{G_{r}}(w)$, where
$\mathrm{deg}_{G_{r}}(w)$ for $r\leqslant t$ is the degree of $w$ when the
contracted graph was constructed. If it is the case, the algorithm pulls $w$
out of $p_{i}$, and adds it to $\widetilde{V}_{t+1}$, i.e., the uses a single
vertex in $\widetilde{G}_{t+1}$ to represent $w$.

  * •

The algorithm adjusts the edge weights in the contracted graph based on the
type of the vertices. For instance, the algorithm sets
$w_{\widetilde{G}_{t+1}}(u,v)=1$ if both of $u$ and $v$ are non-contracted
vertices, and decreases the value of $w_{\widetilde{G}_{t+1}}(P_{u},P_{u})$ if
vertex $u$ pulls out of $P_{u}\in\mathcal{P}$.

See Algorithm 7 in the appendix for the formal description of the algorithm
$\mathsf{UpdateContractedGraph}(G_{t},\widetilde{G}_{t},e)$.

######  Lemma 4.2.

The amortised time complexity of
$\mathsf{UpdateContractedGraph}(G_{t},\widetilde{G}_{t},e)$ is $O(1)$.

###  4.2 Properties of the Contracted Graph

Now we analyse the properties of the contracted graph. Since the amortised
time complexity for every edge update (Theorem 3.3 and Lemma 4.2) remains
valid when we consider a sequence of edge updates at every time, without loss
of generality let $G_{t^{\prime}}=(V_{t}\cup V_{\mathrm{new}},E_{t}\cup
E_{\mathrm{new}})$ be the graph after a sequence of edge updates from
$G_{t}=(V_{t},E_{t})$ with $n_{t}$ vertices, and $\widetilde{G}_{t^{\prime}}$
be the contracted graph of $G_{t^{\prime}}$ constructed by sequentially
running $\mathsf{UpdateContractedGraph}$ for each $e\in E_{\mathrm{new}}$. We
assume that $|E_{\mathrm{new}}|\leqslant\log^{\gamma}(n_{t})$ for some
$\gamma\in\mathbb{R}^{+}$.

We first prove that the clusters returned by spectral clustering on $H_{t}$
also have low conductance in $G_{t}$. Notice that, as the underlying graph
$G_{t}$ could be dense over time, running a clustering algorithm on its
sparsifier $H_{t}$ with $\widetilde{O}(n_{t})$ edges is crucial to achieve the
algorithm’s quick update time.

######  Lemma 4.3.

It holds with high probability that
$\Phi_{H_{t}}(P_{i})=O\left(k^{2}\cdot\rho_{G_{t}}(k)\right)$ and
$\Phi_{G_{t}}(P_{i})=O\left(k^{2}\cdot\rho_{G_{t}}(k)\right)$ for all
$P_{i}\in\mathcal{P}$.

Next, we define the event $\mathcal{E}_{1}$ that

$\Phi_{H_{t}}(P_{i})=O\left(k^{-6}\cdot\log^{-2\gamma}(n_{t})\right)$

and

$\Phi_{G_{t}}(P_{i})=O\left(k^{-6}\cdot\log^{-2\gamma}(n_{t})\right)$

hold for all $P_{i}\in\mathcal{P}$. By the fact that
$\lambda_{k+1}(G_{t})=\Omega(1)$,
$\rho_{G_{t}}(k)=O(k^{-8}\cdot\log^{-2\gamma}(n_{t}))$ and Lemma 4.3,
$\mathcal{E}_{1}$ holds with high probability. We further define the event
$\mathcal{E}_{2}$ that

$(1/2)\cdot\mathrm{deg}_{G_{t}}(u)\leqslant\mathrm{deg}_{H_{t}}(u)\leqslant(3/2)\cdot\mathrm{deg}_{G_{t}}(u)$

hold for all $u\in V_{t}$, and know from the proof of Theorem 3.3 that
$\mathcal{E}_{2}$ holds with high probability. In the following we assume that
both of $\mathcal{E}_{1}$ and $\mathcal{E}_{2}$ happen.

Next, we study the relationship between the cluster-structure in
$G_{t^{\prime}}$ and the one in $\widetilde{G}_{t^{\prime}}$. Recall that the
number of vertices in $\widetilde{G}_{t^{\prime}}$ is much smaller than the
one in $G_{t^{\prime}}$. We first prove that there are $\ell$ disjoint vertex
sets of low conductance in $G_{t^{\prime}}$ if and only if there are $\ell$
such vertex sets in $\widetilde{G}_{t^{\prime}}$.

######  Lemma 4.4.

The following statements hold:

  * •

If $\rho_{G_{t^{\prime}}}(\ell)\leqslant\log^{-\alpha}(n_{t^{\prime}})$ holds
for some $\ell\in\mathbb{N}$ and $\alpha>0$, then
$\rho_{\widetilde{G}_{t^{\prime}}}(\ell)=\max\left\\{O\left(\log^{-0.9\alpha}(n_{t^{\prime}})\right),O\left(k^{-6}\cdot\log^{-\gamma}(n_{t^{\prime}})\right)\right\\}$.

  * •

If
$\rho_{\widetilde{G}_{t^{\prime}}}(\ell)\leqslant\log^{-\delta}(n_{t^{\prime}})$
holds for some $\ell\in\mathbb{N}$ and $\delta>0$ , then
$\rho_{G_{t^{\prime}}}(\ell)=\max\left\\{O\left(\log^{-\delta}(n_{t^{\prime}})\right),O\left(k^{-6}\cdot\log^{-\gamma}(n_{t^{\prime}})\right)\right\\}$.

Secondly, we show that there is a close connection between
$\lambda_{\ell+1}(\mathcal{L}_{G_{t^{\prime}}})$ and
$\lambda_{\ell+1}(\mathcal{L}_{\widetilde{G}_{t^{\prime}}})$ for any
$\ell\in\mathbb{N}$.

######  Lemma 4.5.

The following statements hold:

  * •

If $\lambda_{\ell+1}(\mathcal{L}_{\widetilde{G}_{t^{\prime}}})=\Omega(1)$ for
some $\ell\in\mathbb{N}$, then
$\lambda_{\ell+1}\left(\mathcal{L}_{G_{t^{\prime}}}\right)=\Omega\left(\log^{-\alpha}(n_{t^{\prime}})/{\ell^{6}}\right)$
for constant $\alpha>0$.

  * •

If $\lambda_{\ell+1}\left(\mathcal{L}_{G_{t^{\prime}}}\right)=\Omega(1)$ holds
for some $\ell\in\mathbb{N}$, then
$\lambda_{\ell+1}(\mathcal{L}_{\widetilde{G}_{t^{\prime}}})=\Omega(1)$.

Lemmas 4.4 and 4.5 imply that the cluster-structures in $G_{t^{\prime}}$ and
$\widetilde{G}_{t^{\prime}}$ are approximately preserved.

###  4.3 Main Algorithm

Our main algorithm consists of the preprocessing stage, update stage, and
query stage. They are described as follows:

_Preprocessing Stage._ For the initial input graph $G_{1}=(V_{1},E_{1})$, we
apply (i) $\mathsf{StaticSZSparsifier}(G_{1},\tau)$ to obtain
$H_{1}=(V_{1},F_{1},w_{H_{1}})$, (ii) $\mathsf{SpectralClustering}(H_{1},k)$
to obtain initial partition $\mathcal{P}=\\{P_{1},\ldots P_{k}\\}$, and (iii)
$\mathsf{ContractGraph}(H_{1},\mathcal{P})$ to obtain
$\widetilde{G}_{1}=(\widetilde{V}_{1},\widetilde{E}_{1})$.

_Update Stage._ When a new edge arrives at time $t$, we apply Algorithm 4 and
the update procedure of the contracted graph (Section 4.1) to dynamically
maintain $H_{t}$ and $\widetilde{G}_{t}$.

_Query Stage._ When a query for a new clustering starts at time $T$, the
algorithm performs the following operations, where $\gamma$ is the constant
satisfying $\gamma>\beta$ and $\gamma>0.9\alpha$:

  * •

For $r$ being the last time at which $\widetilde{G}_{t}$ is recomputed, the
algorithm checks if $T-r\leqslant\log^{\gamma}(n_{r})$, i.e., the number of
added edges after the last reconstruction of the contracted graph is less than
$\log^{\gamma}(n_{r})$. If it is the case, then the algorithm runs spectral
clustering on the contracted graph $\widetilde{G}_{T}$.

  * •

Otherwise, the algorithm runs spectral clustering on $H_{T}$. It also
recomputes $\widetilde{G}_{T}$, by first computing
$\widetilde{G}_{r^{\prime}}$, where $r^{\prime}$ is the last time at which the
dynamic gap assumption holds, and updating $\widetilde{G}_{r^{\prime}}$ to
$\widetilde{G}_{T}$ with the edge updates between time $r^{\prime}$ and $T$.

See Algorithm 6 for formal description.

Algorithm 6
$\mathsf{QuerySpecClustering}(G_{T},H_{T},\widetilde{G}_{T},\gamma,\ell)$

1: Input: Graphs $G_{T}$, $H_{T}$, and $\widetilde{G}_{T}$,
$\gamma\in\mathbb{R}^{+}$, and $\ell\in\mathbb{N}$

2: Output: Partition $\mathcal{P}=\\{P_{1},\ldots P_{\ell}\\}$

3: Let $r$ be the last time at which $\widetilde{G}_{T}$ is recomputed.

4: if $T-r\leqslant\log^{\gamma}(n_{r})$ then

5:
$P_{1},\ldots,P_{\ell}\leftarrow\mathsf{SpectralClustering}(\widetilde{G}_{T},\ell)$

6: Return $\\{P_{1},\ldots,P_{\ell}\\}$

7: else

8: $P_{1},\ldots,P_{\ell}\leftarrow\mathsf{SpectralClustering}(H_{T},\ell)$

9: Recompute $\widetilde{G}_{r^{\prime}}$, where $r^{\prime}$ is the last time
at which the dynamic gap assumption holds

10: Update $\widetilde{G}_{r^{\prime}}$ to $\widetilde{G}_{T}$ with the edge
updates between time $r^{\prime}$ and $T$

11: Return $\\{P_{1},\ldots,P_{\ell}\\}$

12: end if

######  Theorem 4.6.

Let $G_{1}=(V_{1},E_{1})$ be a graph with $n_{1}$ vertices and
$k=\widetilde{O}(1)$ clusters, and $\\{G_{t}\\}$ the sequence of graphs of
$\\{n_{t}\\}$ vertices constructed through an edge insertion at each time
satisfying the dynamic gap assumption. Assume that $G_{T}$ at query time $T$
has $\ell$ clusters, i.e., $\lambda_{\ell+1}(\mathcal{L}_{G_{T}})=\Omega(1)$
and $\rho_{G_{T}}(\ell)=O(\ell^{-1}\log^{-\alpha}(n_{T}))$ for
$\alpha\in\mathbb{R}^{+}$. Then, with high probability Algorithm 6 returns
$P_{1},\ldots P_{\ell}$ with
$\Phi_{G_{T}}(P_{i})=O\left(\ell\cdot\log^{-0.9\alpha}(n_{T})\right)$ for
every $1\leqslant i\leqslant\ell$. The algorithm’s running time for returning
the clusters of $G_{1}$ is $\widetilde{O}(|E_{1}|)$. Afterwards, the
algorithm’s amortised update time is $O(1)$, and amortised query time is
$o(n_{T})$.

###### Proof.

The algorithm’s running time and approximation guarantee on $G_{1}$ follows
from (Macgregor & Sun, 2022), so we only need to analyse the dynamic update
stage. We first analyse the conductance of every output $P_{i}$. Notice that,
if Lines 4–6 of Algorithm 6 are executed, then by Lemmas 3.2, 4.4 and 4.5 the
approximation guarantee holds. Otherwise, Lines 7–12 are executed, then by the
dynamic gap condition and Lemma 3.2 the approximation guarantee holds as well.

Next, we prove the running time guarantee. The $O(1)$ amortised update time of
$H_{t}$ and $\widetilde{G}_{t}$ follows by Theorem 3.3 and Lemma 4.2. For the
query at time $T$, notice that if Lines 4–6 are executed, then the query time
is at most
$O(|\widetilde{V}_{T}|^{3})=O((k+\log^{\gamma}(n_{T}))^{3})=\widetilde{O}(1)$.
Note, the super vertices are used as sketches to quickly update the cluster
assignment of each vertex; otherwise, Lines 7–12 are executed, and the query
time is dominated by spectral clustering’s time complexity of
$O\left(n_{T}\cdot\log^{\beta}(n_{T})\right)$. Since this only happens every
$\log^{\gamma}(n_{r})=O(\log^{\gamma}(n_{T}))$ edge updates, the amortised
query time is $O(n_{T}\cdot\log^{\beta-\gamma}(n_{T}))=o(n_{T})$.

Finally, we show that the number of clusters $\ell$ can be identified with our
claimed time complexity. Notice that, if Lines 4–6 of the algorithm are
executed, then by Lemmas 4.4 and 4.5 we can detect the spectral gap in $G_{T}$
using $\widetilde{G}_{T}$; hence we can choose $\ell$ in $o(n_{t})$ time.
Otherwise, Lines 7–12 are executed. In this case, we run spectral clustering
with different values of $\ell^{\prime}$ and find the correct value of $\ell$
(The same procedure is done to recompute $\widetilde{G}_{r^{\prime}}$). Since
there are $\widetilde{O}(1)$ clusters in total, we achieve the same query time
guarantee. ∎

Figure 2: Results on the two versions of our dynamic SBM. Figures (a) and (b)
report the average ARI score at each time $T$ for the clustering results on
$G_{T}$, $H_{T}$, and $\widetilde{G}_{T}$; Figures (c) and (d) report the
running time in seconds at each time $T$. Shaded regions indicate the standard
deviation.

##  5 Experiments

We experimentally evaluate the performance of our algorithm on synthetic and
real-world datasets. We report the clustering accuracy of all tested
algorithms using the Adjusted Rand Index (ARI) (Rand, 1971), and compute the
average and standard deviation over 10 independent runs. Algorithms were
implemented in Python 3.12.1 and experiments were performed using a Lenovo
ThinkPad T15G, with an Intel(R) Xeon(R) W-10855M<EMAIL_ADDRESS>processor and 126
GB RAM. Our code can be downloaded from
https://github.com/steinarlaenen/Dynamic-Spectral-Clustering-With-Provable-
Approximation-Guarantee.

###  5.1 Results on Synthetic Data

We study graphs generated from the stochastic block model (SBM), and introduce
two dynamic extensions to generate new clusters and merge existing clusters.

_SBM with increasing number of clusters._ We generate the first graph $G_{1}$
based on the standard SBM, and set $k=10$ and the number of vertices in each
cluster $\\{S_{i}\\}_{i=1}^{k}$ as $n_{k}=10,000$. For every pair of $u\in
S_{i}$ and $v\in S_{j}$ we include edge $\\{u,v\\}$ with probability $p$ if
$i=j$, and with probability $q$ if $i\neq j$.

To update the graph, we generate a batch of edge updates in two steps: first,
we randomly select a subset $Q\subset V(G_{1})$ such that
$|Q|=n_{\mathrm{new}}=400$, and for any $u,v\in Q$ we include edge
$e=\\{u,v\\}$ in the graph with probability $r_{1}$; setting $r_{1}$
sufficiently large ensures that the set $Q$ forms a new cluster in the graph.
Second, for any $u,v\in V(G_{1})$ we include edge $e=\\{u,v\\}$ with
probability $s$. The edges sampled from these two processes form one edge
update batch. We sample 10 such batches (ensuring no new clusters overlap),
each inducing a new cluster and additional noise.

To cluster each $G_{T}$, we run spectral clustering (SC) on three graphs:

  1. 1.

We run spectral clustering on the full graph $G_{T}$.

  2. 2.

We construct the contracted graph $\widetilde{G}_{1}$ at time $T=1$, and
incrementally update $\widetilde{G}_{1}$ using the procedure described in
Section 4.1. Then, we run spectral clustering on each $\widetilde{G}_{T}$.

  3. 3.

We construct a cluster-preserving sparsifier $H_{1}$ using Algorithm 3, which
we dynamically update using Algorithm 4 with sampling parameter $\tau=3$, and
cluster each subsequent $H_{T}$.

At each time $T$, we run spectral clustering with $k=10+T-1$ on all three
graphs, and report the running times and ARI scores. We set $p=0.1$, $q=0.01$,
$r_{1}=0.95$, and $s=0.00001$, and plot the results in the left plots of
Figure 2. We can see that at every time $T$, spectral clustering on $G_{T}$
returns the perfect clustering, and spectral clustering on $\widetilde{G}_{T}$
and $H_{T}$ returns marginally worse clustering results. On the running time,
we see that running spectral clustering on $G_{T}$, $H_{T}$ and
$\widetilde{G}_{T}$ takes around $100$ seconds, $50$ seconds, and less than
$1$ second respectively. This highlights that our algorithm returns nearly-
optimal clusters with much faster running time than running spectral
clustering on $G_{T}$ or $H_{T}$.

Figure 3: Results on MNIST and EMNIST. Figures (a) and (b) report the average
ARI scores at each time $T$ for the clustering results on $G_{T}$, $H_{T}$,
and $\widetilde{G}_{T}$; Figures (c) and (d) report the average cumulative
running time in seconds at each time $T$. Shaded regions indicate the standard
deviation.

Next, we compare the spectral gaps of $\mathcal{L}_{G_{T}}$ and
$\mathcal{L}_{\widetilde{G}_{T}}$ for every $T$, and Table 1 reports that
these gaps are well preserved. This demonstrates that, as what we prove
earlier, the new cluster-structure of $G_{T}$ can be indeed identified from
$\widetilde{G}_{T}$.

Table 1: Spectral gaps in $\mathcal{L}_{G_{T}}$ and
$\mathcal{L}_{\widetilde{G}_{T}}$ for SBM with increasing number of clusters.
We report
$\lambda_{k+T}(\mathcal{L}_{G_{T}})/\lambda_{k+T-1}(\mathcal{L}_{G_{T}})$ and
$\lambda_{k+T}(\mathcal{L}_{\widetilde{G}_{T}})/\lambda_{k+T-1}(\mathcal{L}_{\widetilde{G}_{T}})$
at each time $T$.

$T$ | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11
---|---|---|---|---|---|---|---|---|---|---
$G_{T}$ | $6.3$ | $5.8$ | $5.8$ | $5.7$ | $5.7$ | $5.7$ | $5.6$ | $5.6$ | $5.6$ | $5.5$
$\widetilde{G}_{T}$ | $9.3$ | $9.2$ | $9.0$ | $8.7$ | $8.5$ | $8.1$ | $7.8$ | $7.5$ | $7.1$ | $6.8$

_SBM with decreasing number of clusters._ We set $k=25$, and the first graph
$G_{1}$ is generated based on the standard SBM with parameters $p$ and $q$.
For clusters $\\{S_{i}\\}_{i=1}^{5}$ we set $|S_{i}|=20,000$, and for
$\\{S_{i}\\}_{i=6}^{25}$ we set $|S_{i}|=500$; hence there are $5$ large and
$20$ small clusters.

To update the graph, we generate a batch of edge updates as follows: we
randomly choose two clusters $S_{i}$ and $S_{j}$ such that
$|S_{i}|=|S_{j}|=500$, and for any $u\in S_{i}$ and $v\in S_{j}$ we include
edge $e=\\{u,v\\}$ in the graph with probability $r_{2}$. Setting $r_{2}$
sufficiently large ensures that clusters $S_{i}$ and $S_{j}$ merge. Similarly
as before, for any $u,v\in V(G_{1})$ we also include edge $e=\\{u,v\\}$ with
probability $s$. All the edges sampled by these two processes form a single
batch update. We sample $10$ such batches, and there are $k=15$ clusters at
final time $T=11$. At each time $T$, we run spectral clustering with
$k=25-T+1$ on all three graphs. We set $p=0.1$, $q=0.001$, $r_{2}=0.95$, and
$s=0.00001$, and plot the results in the right plots of Figure 2.

Similar to the SBM with increasing number of clusters, at every time $T$,
spectral clustering on all three graphs returns similar results. We further
see that spectral clustering on $\widetilde{G}_{T}$ has lower running time
than the one on $G_{T}$ and $H_{T}$. The spectral gaps in $G_{T}$ and
$\widetilde{G}_{T}$ are reported in Table 2.

Table 2: Spectral gaps in $\mathcal{L}_{G_{T}}$ and
$\mathcal{L}_{\widetilde{G}_{T}}$ for SBM with decreasing number of clusters.
We report
$\lambda_{k-T+2}(\mathcal{L}_{G_{T}})/\lambda_{k-T+1}(\mathcal{L}_{G_{T}})$
and
$\lambda_{k-T+2}(\mathcal{L}_{\widetilde{G}_{T}})/\lambda_{k-T+1}(\mathcal{L}_{\widetilde{G}_{T}})$
at each time $T$.

$T$ | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11
---|---|---|---|---|---|---|---|---|---|---
$G_{T}$ | $4.5$ | $4.4$ | $4.2$ | $4.0$ | $4.0$ | $3.9$ | $3.8$ | $3.8$ | $3.8$ | $3.6$
$\widetilde{G}_{T}$ | $8.3$ | $8.0$ | $7.5$ | $7.4$ | $7.4$ | $7.0$ | $6.8$ | $6.3$ | $5.8$ | $5.4$

###  5.2 Results on Real-World Data

We further evaluate our algorithm on the MNIST dataset (Lecun et al., 1998),
which consists of 10 classes of handwritten digits and has $70,000$ images,
and the “letter” subset of the EMNIST dataset (Cohen et al., 2017), which
consists of 26 classes of handwritten letters and has $145,600$ images. We
construct a $k$-nearest neighbour graph for each dataset, and set $k=100$
(resp. $k=200$) for MNIST (resp. EMNIST).

We select four classes (clusters) at random; the chosen vertices and adjacent
edges in the $k$-nearest neighbour graph form $G_{1}$. To construct the
sequence of updates, we select one new cluster (resp. two) at random for MNIST
(resp. EMNIST), and add the edges inside the new cluster as well as the ones
between the new and existing clusters. We randomly partition these new edges
into 10 batches of equal size, and add these to the graph sequentially. We
recompute $\widetilde{G}_{T}$ after one class (resp. two) is streamed for
MNIST (resp. EMNIST), and report the results in Figure 3. The
update/reconstruction time is included in the running time.

Our experiments on real-world data further confirm that, as the size of the
underlying graph and its number of clusters increase over time, our designed
algorithm has much lower running time compared with repeated execution of
spectral clustering, while producing comparable clustering results.

## Impact Statement

This paper presents work whose goal is to advance the field of Machine
Learning. There are many potential societal consequences of our work, none of
which we feel must be specifically highlighted here.

## Acknowledgements

This work is supported by an EPSRC Early Career Fellowship (EP/T00729X/1).
Part of this work was done when He Sun was visiting the Simons Institute for
the Theory of Computing in Fall 2023.

## References

  * Beimel et al. (2022) Beimel, A., Kaplan, H., Mansour, Y., Nissim, K., Saranurak, T., and Stemmer, U.  Dynamic algorithms against an adaptive adversary: generic constructions and lower bounds.  In _54th Annual ACM Symposium on Theory of Computing (STOC’22)_ , pp. 1671–1684, 2022.
  * Bernstein et al. (2022) Bernstein, A., van den Brand, J., Gutenberg, M. P., Nanongkai, D., Saranurak, T., Sidford, A., and Sun, H.  Fully-dynamic graph sparsifiers against an adaptive adversary.  In _49th International Colloquium on Automata, Languages, and Programming (ICALP’22)_ , pp. 20:1–20:20, 2022.
  * Chung & Lu (2006) Chung, F. and Lu, L.  Concentration inequalities and martingale inequalities: a survey.  _Internet mathematics_ , 3(1):79–127, 2006.
  * Cohen et al. (2017) Cohen, G., Afshar, S., Tapson, J., and Schaik, A. V.  Emnist: Extending MNIST to handwritten letters.  In _2017 International Joint Conference on Neural Networks (IJCNN)_ , pp. 2921–2926, 2017.
  * Dhanjal et al. (2014) Dhanjal, C., Gaudel, R., and Clémençon, S.  Efficient eigen-updating for spectral graph clustering.  _Neurocomputing_ , 131:440–452, 2014.
  * Lecun et al. (1998) Lecun, Y., Bottou, L., Bengio, Y., and Haffner, P.  Gradient-based learning applied to document recognition.  _Proceedings of the IEEE_ , 86(11):2278–2324, 1998.
  * Lee et al. (2014) Lee, J. R., Gharan, S. O., and Trevisan, L.  Multiway spectral partitioning and higher-order Cheeger inequalities.  _Journal of the ACM_ , 61(6):1–30, 2014.
  * Macgregor & Sun (2022) Macgregor, P. and Sun, H.  A tighter analysis of spectral clustering, and beyond.  In _39th International Conference on Machine Learning (ICML’22)_ , pp. 14717–14742, 2022.
  * Martin et al. (2018) Martin, L., Loukas, A., and Vandergheynst, P.  Fast approximate spectral clustering for dynamic networks.  In _35th International Conference on Machine Learning (ICML’18)_ , pp. 3420–3429, 2018.
  * Ng et al. (2001) Ng, A. Y., Jordan, M. I., and Weiss, Y.  On spectral clustering: Analysis and an algorithm.  In _Advances in Neural Information Processing Systems 15 (NeurIPS’01)_ , pp. 849–856, 2001.
  * Ning et al. (2007) Ning, H., Xu, W., Chi, Y., Gong, Y., and Huang, T.  Incremental spectral clustering with application to monitoring of evolving blog communities.  In _Proceedings of the 2007 SIAM International Conference on Data Mining (SDM)_ , pp. 261–272, 2007.
  * Peng et al. (2017) Peng, R., Sun, H., and Zanetti, L.  Partitioning Well-Clustered Graphs: Spectral Clustering Works!  _SIAM Journal on Computing_ , 46(2):710–743, 2017.
  * Rand (1971) Rand, W. M.  Objective criteria for the evaluation of clustering methods.  _Journal of the American Statistical Association_ , 66(336):846–850, 1971.
  * Saranurak & Wang (2019) Saranurak, T. and Wang, D.  Expander decomposition and pruning: Faster, stronger, and simpler.  In _30th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA’19)_ , pp. 2616–2635, 2019.
  * Sun & Zanetti (2019) Sun, H. and Zanetti, L.  Distributed graph clustering and sparsification.  _ACM Transactions on Parallel Computing_ , 6(3):17:1–17:23, 2019.
  * Thorup (2007) Thorup, M.  Fully-dynamic min-cut.  _Combinatorica_ , 27(1):91–127, 2007.
  * Tropp (2012) Tropp, J. A.  User-friendly tail bounds for sums of random matrices.  _Foundations of Computational Mathematics_ , 12(4):389–434, 2012.
  * von Luxburg (2007) von Luxburg, U.  A tutorial on spectral clustering.  _Statistics and Computing volume_ , 17(4):395–416, 2007.

##  Appendix A Omitted Details from Section 3

The section presents the details omitted from Section 3, and is organised as
follows. We prove Lemma 3.2 in Section A.1, and prove Theorem 3.3 in Section
A.2.

###  A.1 Proof of Lemma 3.2

We first prove a structure theorem. We define the vectors
$\chi_{1},\ldots\chi_{k}$ to be the indicator vectors of the optimal clusters
$S_{1},\ldots,S_{k}$ in $G$, where $\chi_{i}(u)=1$ if $u\in S_{i}$, and
$\chi_{i}=0$ otherwise. We further use $\bar{g}_{1},\ldots,\bar{g}_{k}$ to
denote the indicator vectors of the optimal clusters $S_{1},\ldots S_{k}$ in
$G$, normalised by the degrees in $H$, i.e.,

$\bar{g}_{i}\triangleq\frac{D_{H}^{\frac{1}{2}}\chi_{i}}{\|D_{H}^{\frac{1}{2}}\chi_{i}\|}.$
(4)

######  Theorem A.1.

Let $S_{1},\ldots,S_{k}$ be a $k$-way partition of $G$ achieving
$\rho_{G}(k)$, and $\Upsilon_{G}(k)=\Omega(k)$, and $\\{f_{i}\\}_{i=1}^{k}$ be
first $k$ eigenvectors of $\mathcal{L}_{H}$ and let
$\\{\bar{g}_{i}\\}_{i=1}^{k}$ be defined as in (4) above. Then, the following
statements hold:

  1. 1.

For any $i\in[k]$, there is $\widehat{f}_{i}\in\mathbb{R}^{n}$, which is a
linear combination of $f_{1},\ldots,f_{k}$, such that
$\|\bar{g}_{i}-\widehat{f}_{i}\|^{2}=O\left(k/\Upsilon_{G}(k)\right)$ .

  2. 2.

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

###### Proof.

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

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

Now, let us consider the quadratic form

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

where the second to last inequality follows by the fact that
$\lambda_{i}(\mathcal{L}_{H})\geqslant 0$ holds for any $1\leqslant i\leqslant
n$, and the last inequality follows because $H$ is a cluster preserving
sparsifier of $G$. This gives us that

$\displaystyle\bar{g}_{i}^{\intercal}\mathcal{L}_{H}\bar{g}_{i}$
$\displaystyle=\sum_{(u,v)\in
E_{H}}w_{H}(u,v)\left(\frac{\bar{g}_{i}(u)}{\sqrt{\mathrm{deg}_{H}(u)}}-\frac{\bar{g}_{i}(v)}{\sqrt{\mathrm{deg}_{H}(v)}}\right)^{2}$
$\displaystyle=\sum_{(u,v)\in
E_{H}}w_{H}(u,v)\left(\frac{\chi_{i}(u)}{\sqrt{\mathrm{vol}_{H}(S_{i})}}-\frac{\chi_{i}(v)}{\sqrt{\mathrm{vol}_{H}(S_{i})}}\right)^{2}$
$\displaystyle=\frac{w_{H}(S_{i},V\setminus S_{i})}{\mathrm{vol}_{H}(S_{j})}$
$\displaystyle=O\left(k\cdot\rho_{G}(k)\right),$ (6)

where the last line holds because $H$ is a cluster preserving sparsifier of
$G$. Combining (5) with (6), we have that

$\left\|\bar{g}_{i}-\widehat{f}_{i}\right\|^{2}\leqslant\frac{\bar{g}_{i}^{\intercal}\mathcal{L}_{H}\bar{g}_{i}}{\Omega\left(\lambda_{k+1}(\mathcal{L}_{G})\right)}\leqslant\frac{O\left(k\cdot\rho_{G}(k)\right)}{\Omega\left(\lambda_{k+1}(\mathcal{L}_{G})\right)}=O\left(\frac{k}{\Upsilon_{G}(k)}\right),$

which proves the first statement of the theorem.

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

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

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

###### Proof Sketch of Lemma 3.2.

The proof follows Theorem 1.2 of (Peng et al., 2017) and Theorem 2 of
(Macgregor & Sun, 2022), which imply that every returned cluster
$P_{i}~{}(1\leqslant i\leqslant k)$ from spectral clustering on $G$ satisfies
that

$\mathrm{vol}_{G}(P_{i}\triangle
S_{i})=O\left(k\cdot\frac{\mathrm{vol}_{G}(S_{i})}{\Upsilon_{G}(k)}\right)$

and

$\Phi_{G}(P_{i})=O\left(\Phi_{G}(S_{i})+\frac{k}{\Upsilon_{G}(k)}\right),$

where $S_{i}$ is the optimal correspondence of $P_{i}$ in $G$. Since $H$ is a
cluster-preserving sparsifier of $G$, we know that
$\rho_{H}(k)=O(k\cdot\rho_{G}(k))$ and
$\lambda_{k+1}(\mathcal{L}_{H})=\Omega(\lambda_{k+1}(\mathcal{L}_{G}))$, which
implies that

$\Upsilon_{H}(k)=\frac{\lambda_{k+1}(\mathcal{L}_{H})}{\rho_{H}(k)}=\frac{\Omega(\lambda_{k+1}(\mathcal{L}_{G}))}{O(k\cdot\rho_{G}(k))}=\Omega\left(\frac{1}{k}\cdot\Upsilon_{G}(k)\right).$
(7)

On the other side, compared with their work, we need to apply the bottom $k$
eigenvectors of $\mathcal{L}_{H}$ instead of $\mathcal{L}_{G}$ to run spectral
clustering. As such, combining (7) with the adjusted structure theorem
(Theorem A.1) one can prove Lemma 3.2 using the proof technique from
(Macgregor & Sun, 2022) and (Peng et al., 2017). ∎

###  A.2 Proof of Theorem 3.3

Let

$E_{\mathrm{resampled}}\triangleq e~{}\bigcup~{}\Big{\\{}\\{u,v\\}\in
E_{G_{t+1}}~{}|~{}u\in V_{\mathrm{doubled}}\Big{\\}}$

be the set of all the edges that have been (re)-sampled by Algorithm 4, and

$E_{\mathrm{old}}\triangleq E_{t+1}\setminus E_{\mathrm{resampled}}.$

Moreover, let

$p^{(t+1)}_{u}(v)\triangleq\min\left\\{\frac{\tau\cdot\log(n_{t+1})}{\mathrm{deg}_{G_{t+1}}(u)},1\right\\}$

be the “ideal” sampling probability of an edge $\\{u,v\\}$ if one runs the
$\mathsf{SZ}$ algorithm from the scratch on $G_{t+1}$, and let

$q^{(t+1)}(u,v)\triangleq
p^{(t+1)}_{u}(v)+p^{(t+1)}_{v}(u)-p^{(t+1)}_{u}(v)\cdot p^{(t+1)}_{v}(u)$

be the probability that edge $e$ is sampled if one runs the $\mathsf{SZ}$
algorithm from scratch at time $t+1$. For any edge $\\{u,v\\}$, we use

  * •

$\widetilde{q}(u,v)\triangleq q^{(r)}(u,v)$

  * •

$\widetilde{p}_{u}(v)\triangleq p^{(r)}_{u}(v)$

  * •

$\widetilde{p}_{v}(u)\triangleq p^{(r)}_{v}(u)$

for some $1\leqslant r\leqslant t+1$ to denote the sampling probability last
used for edge $\\{u,v\\}$ throughout the sequence of edge updates. Hence, we
have $\widetilde{q}(u,v)=q^{(t+1)}(u,v)$ if $\\{u,v\\}\in
E_{\mathrm{resampled}}$, and $\widetilde{q}(u,v)=q^{(r)}(u,v)$ for some
$1\leqslant r\leqslant t+1$ if edge $\\{u,v\\}\in E_{\mathrm{old}}$. By the
algorithm description (Line 16 in Algorithm 4), we know that

$\frac{\tau\cdot\log(n_{t+1})}{2\cdot\mathrm{deg}_{G_{t+1}}(u)}\leqslant\frac{\tau\cdot\log(n_{r})}{\mathrm{deg}_{G_{r}}(u)}\leqslant\frac{2\cdot\tau\cdot\log(n_{t+1})}{\mathrm{deg}_{G_{t+1}}(u)}.$
(8)

The following two concentration inequalities will be used in our analysis.

######  Lemma A.2 (Bernstein’s Inequality (Chung & Lu, 2006)).

Let $X_{1},\ldots,X_{n}$ be independent random variables such that
$|X_{i}|\leqslant M$ for any $i\in\\{1,\ldots,n\\}$. Let
$X=\sum_{i=1}^{n}X_{i}$, and
$R=\sum_{i=1}^{n}\mathbb{E}\left[X_{i}^{2}\right]$. Then, it holds that

$\mathbb{P}\left[|X-\mathbb{E}\left[X\right]|\geqslant t\right]\leqslant
2\exp\left(-\frac{t^{2}}{2(R+Mt/3)}\right).$

######  Lemma A.3 (Matrix Chernoff Bound (Tropp, 2012)).

Consider a finite sequence $\\{X_{i}\\}$ of independent, random, PSD matrices
of dimension $d$ that satisfy $\|X_{i}\|\leqslant R$. Let
$\mu_{\mathrm{min}}\triangleq\lambda_{\mathrm{min}}(\mathbb{E}\left[\sum_{i}X_{i}\right])$
and
$\mu_{\mathrm{max}}\triangleq\lambda_{\mathrm{max}}(\mathbb{E}\left[\sum_{i}X_{i}\right])$.
Then, it holds that

$\mathbb{P}\left[\lambda_{\mathrm{min}}\left(\sum_{i}X_{i}\right)\leqslant(1-\delta)\mu_{\mathrm{min}}\right]\leqslant
d\left(\frac{\mathrm{e}^{-\delta}}{(1-\delta)^{1-\delta}}\right)^{\mu_{\mathrm{min}}/R}$

for $\delta\in[0,1]$, and

$\mathbb{P}\left[\lambda_{\mathrm{max}}\left(\sum_{i}X_{i}\right)\geqslant(1+\delta)\mu_{\mathrm{max}}\right]\leqslant
d\left(\frac{\mathrm{e}^{\delta}}{(1+\delta)^{1+\delta}}\right)^{\mu_{\mathrm{max}}/R}$

for $\delta\geqslant 0$.

We first prove the following result on the relationship of cut values between
$G_{t+1}$ and $H_{t+1}$.

######  Lemma A.4.

Let $G_{t+1}$ be a graph, and $H_{t+1}$ the sparsifier returned by Algorithm
4. Suppose for every $\\{u,v\\}\in E_{t+1}$ that $\widetilde{p}_{u}(v)<1$,
then it holds for any non-empty subset $A\subset V_{t+1}$ that

$\displaystyle\mathbb{P}\left[|w_{H_{t+1}}(A,V_{t+1}\setminus
A)-w_{G_{t+1}}(A,V_{t+1}\setminus A)|\geqslant\frac{1}{2}\cdot
w_{G_{t+1}}(A,V_{t+1}\setminus A)\right]$ $\displaystyle\qquad\leqslant
2\cdot\exp\left(\frac{-\tau\cdot\log n_{t+1}\cdot
w_{G_{t+1}}(A,V_{t+1}\setminus A)}{10\cdot\mathrm{vol}_{G_{t+1}}(A)}\right)$

###### Proof.

For any edge $e=\\{u,v\\}$, we define the random variable $Y_{e}$ by

$Y_{e}\triangleq\begin{cases}\frac{1}{\widetilde{q}(u,v)}&\text{with
probability $\widetilde{q}(u,v)$}\\\ 0&\text{otherwise.}\end{cases}$

We also define

$Z\triangleq\sum_{e\in E_{G_{t+1}}(A,V_{t+1}\setminus A)}Y_{e},$

and have that

$\mathbb{E}[\,Z\,]=\sum_{e=\\{u,v\\}\in E_{G_{t+1}}(A,V_{t+1}\setminus
A)}\mathbb{E}[\,Y_{e}\,]=\sum_{e=\\{u,v\\}\in E_{G_{t+1}}(A,V_{t+1}\setminus
A)}\widetilde{q}(u,v)\cdot\widetilde{q}(u,v)^{-1}=w_{G_{t+1}}(A,V_{t+1}\setminus
A).$

To prove a concentration bound on this degree estimate, we apply the Bernstein
inequality (Lemma A.2), for which we need to bound the second moment

$R\triangleq\sum_{e=\\{u,v\\}\in E_{G_{t+1}}(A,V_{t+1}\setminus
A)}\mathbb{E}[\,Y_{e}^{2}\,].$

We get that

$\displaystyle R$ $\displaystyle=\sum_{e=\\{u,v\\}\in
E_{G_{t+1}}(A,V_{t+1}\setminus
A)}\widetilde{q}(u,v)\cdot\left(\frac{1}{\widetilde{q}(u,v)}\right)^{2}=\sum_{e=\\{u,v\\}\in
E_{G_{t+1}}(A,V_{t+1}\setminus A)}\frac{1}{\widetilde{q}(u,v)}$
$\displaystyle\leqslant\sum_{e=\\{u,v\\}\in E_{G_{t+1}}(A,V_{t+1}\setminus
A)}\frac{1}{\widetilde{p}_{u}(v)}$ (9) $\displaystyle=\sum_{e=\\{u,v\\}\in
E_{G_{t+1}}(A,V_{t+1}\setminus
A)}\frac{2\cdot\mathrm{deg}_{G_{t+1}}(u)}{\tau\cdot\log(n_{t+1})}$ (10)
$\displaystyle\leqslant\frac{2\cdot\Delta_{G_{t+1}}(A)}{\tau\cdot\log(n_{t+1})}\cdot\sum_{e=\\{u,v\\}\in
E_{G_{t+1}}(A,V_{t+1}\setminus A)}1$
$\displaystyle=\frac{2\cdot\Delta_{G_{t+1}}(A)\cdot
w_{G_{t+1}}(A,V_{t+1}\setminus A)}{\tau\cdot\log(n_{t+1})},$

where $\Delta_{G_{t+1}}(A)\triangleq\max_{u\in A}\mathrm{deg}_{G_{t+1}}(u)$,
(9) holds since
$\widetilde{q}(u,v)=\widetilde{p}_{u}(v)+\widetilde{p}_{v}(u)-\widetilde{p}_{u}(v)\cdot\widetilde{p}_{v}(u)\geqslant\widetilde{p}_{u}(v)$,
and (10) holds because of (8).

Note, by (8), for any edge $e=\\{u,v\\}\in E_{G_{t+1}}(A,V_{t+1}\setminus A)$
we have that

$0\leqslant
Y_{e}=\frac{1}{\widetilde{q}(u,v)}\leqslant\frac{1}{\widetilde{p}_{u}(v)}\leqslant\frac{2\cdot\Delta_{G_{t+1}}(A)}{\tau\cdot\log
n_{t+1}}.$

Then, by applying Bernstein’s inequality, we have that

$\displaystyle\mathbb{P}\left[|Z-\mathbb{E}[\,Z\,]|\geqslant\frac{1}{2}\mathbb{E}[\,Z\,]\right]$
$\displaystyle\leqslant 2\cdot\exp\left(-\frac{w_{G_{t+1}}(A,V_{t+1}\setminus
A)^{2}/4}{\frac{\Delta_{G_{t+1}}(A)\cdot w_{G_{t+1}}(A,V_{t+1}\setminus
A)}{\tau\cdot\log(n_{t+1})}+\frac{\Delta_{G_{t+1}}(A)\cdot
w_{G_{t+1}}(A,V_{t+1}\setminus A)}{3\cdot\tau\cdot\log(n_{t+1})}}\right)$ (11)
$\displaystyle=2\cdot\exp\left(-\frac{\tau\cdot\log(n_{t+1})\cdot 3\cdot
w_{G_{t+1}}(A,V_{t+1}\setminus A)}{16\cdot\Delta_{G_{t+1}}(A)}\right)$ (12)
$\displaystyle\leqslant 2\cdot\exp\left(-\frac{\tau\cdot\log(n_{t+1})\cdot
w_{G_{t+1}}(A,V_{t+1}\setminus A)}{10\cdot\mathrm{vol}_{G_{t+1}}(A)}\right),$
(13)

which proves the lemma. ∎

###### Proof of Theorem 3.3.

We first analyse the number of edges in $H_{t+1}$, i.e., the size of
$F_{t+1}$. We have that

$\sum_{u\in V_{t+1}}\sum_{e=\\{u,v\\}\in
E_{G_{t+1}}}\widetilde{p}_{u}(v)\leqslant\sum_{u\in
V_{t+1}}\sum_{e=\\{u,v\\}\in E_{G_{t+1}}}\frac{2\cdot\tau\cdot\log
n_{t+1}}{\mathrm{deg}_{G_{t+1}}(u)}=2\cdot\tau\cdot n_{t+1}\cdot\log n_{t+1},$

where the first inequality holds by (8). Therefore, it holds by the Markov
inequality that the number of edges $\\{u,v\\}$ with
$\widetilde{p}_{u}(v)\geqslant 1$ is $O\left(\tau\cdot n_{t+1}\log
n_{t+1}\right)$. Without loss of generality, we assume that these edges are
included in $F_{t+1}$, and we assume for the remaining part of the proof that
it holds that $\widetilde{p}_{u}(v)<1$.

We now show that the degrees of the vertices in $G_{t+1}$ are approximately
preserved in $H_{t+1}$. Let $u$ be an arbitrary vertex of $G_{t+1}$. Observing
that $\mathrm{vol}_{G_{t+1}}(u)=w_{G_{t+1}}(u,V\setminus
u)=\mathrm{deg}_{G_{t+1}}(u)$ and $w_{H_{t+1}}(u,V_{t+1}\setminus
u)=\mathrm{deg}_{H_{t+1}}(u)$, by Lemma A.4 it holds that

$\displaystyle\mathbb{P}\left[|\mathrm{deg}_{H_{t+1}}(u)-\mathrm{deg}_{G_{t+1}}(u)|\geqslant\frac{1}{2}\mathrm{deg}_{G_{t+1}}(u)\right]$
$\displaystyle=2\exp\left(-(1/10)\cdot\tau\cdot\log n_{t+1}\right)$
$\displaystyle=2\exp\left(-(1/10)\cdot(\log{n_{t+1}}\cdot
C)/\lambda_{k+1}(\mathcal{L}_{G_{t+1}})\right)$
$\displaystyle=o(1/n_{t+1}^{2}).$

Hence, by taking $C$ to be sufficiently large and the union bound, it holds
with high probability that the degrees of all the vertices in $G_{t+1}$ are
preserved in $H_{t+1}$ up to a constant factor. Throughout the rest of the
proof, we assume this is the case. This implies for any subset $A\subseteq
V_{t+1}$ that $\mathrm{vol}_{H_{t+1}}(A)=\Theta(\mathrm{vol}_{G_{t+1}}(A))$.

Secondly, we prove it holds that
$\Phi_{H_{t+1}}(S_{i})=O(k\cdot\Phi_{G_{t+1}}(S_{i}))$ for any $1\leqslant
i\leqslant k$, where $S_{1},\ldots,S_{k}$ are the optimal clusters
corresponding to $\rho_{G_{t+1}}(k)$. For any $1\leqslant i\leqslant k$, it
holds that

$\mathbb{E}[\,w_{H_{t+1}}(S_{i},V_{t+1}\setminus
S_{i})\,]=\sum_{\begin{subarray}{c}e=\\{u,v\\}\in E_{t+1}\\\ u\in
S_{i},v\notin
S_{i}\end{subarray}}\widetilde{q}(u,v)\cdot\frac{1}{\widetilde{q}(u,v)}=w_{G_{t+1}}(S,V_{t+1}\setminus
S_{i}).$

Hence, by Markov’s inequality and the union bound, it holds with constant
probability that $w_{H_{t+1}}(S_{i},V_{t+1}\setminus S_{i})=O(k\cdot
w_{G_{t+1}}(S_{i},V_{t+1}\setminus S_{i}))$. Therefore, it holds with constant
probability that

$\rho_{H_{t+1}}(k)\leqslant\max_{1\leqslant i\leqslant
k}\Phi_{H_{t+1}}(S_{i})=\max_{1\leqslant i\leqslant
k}O(k\cdot\Phi_{G_{t+1}}(S_{i}))=O(k\cdot\rho_{G_{t+1}}(k)).$

Next, we prove that
$\lambda_{k+1}(\mathcal{L}_{H_{t+1}})=\Omega(\lambda_{k+1}(\mathcal{L}_{G_{t+1}}))$.
Let $\overline{\mathcal{L}}_{G_{t+1}}$ be the projection of
$\mathcal{L}_{G_{t+1}}$ on its top $n_{t+1}-k$ eigenspaces, and notice that
$\overline{\mathcal{L}}_{G_{t+1}}$ can be written as

$\overline{\mathcal{L}}_{G_{t+1}}=\sum_{i=k+1}^{n_{t+1}}\lambda_{i}(\mathcal{L}_{G_{t+1}})\cdot
f_{i}f_{i}^{\intercal}$

where $f_{1},\ldots,f_{n_{t+1}}$ are the eigenvectors of
$\mathcal{L}_{G_{t+1}}$. Let $\overline{\mathcal{L}}_{G_{t+1}}^{-1/2}$ be the
square root of the pseudoinverse of $\overline{\mathcal{L}}_{G_{t+1}}$. We
prove that the top $n_{t+1}-k$ eigenvalues of $\mathcal{L}_{G_{t+1}}$ are
preserved, which implies that
$\lambda_{k+1}(\mathcal{L}_{H_{t+1}})=\Theta(\lambda_{k+1}(\mathcal{L}_{G_{t+1}}))$.

To prove this, for each edge $e=\\{u,v\\}\in E_{G_{t+1}}$ we define a random
matrix $X_{e}\in\mathbb{R}^{n_{t+1}\times n_{t+1}}$ by

$X_{e}=\begin{cases}w_{H_{t+1}}(u,v)\cdot\overline{\mathcal{L}}_{G_{t+1}}^{-1/2}b_{e}b_{e}^{\intercal}\overline{\mathcal{L}}_{G_{t+1}}^{-1/2}&\text{if
$e=\\{u,v\\}$ is sampled by the algorithm}\\\ 0&\text{otherwise,}\end{cases}$

where $b_{e}\triangleq\chi_{u}-\chi_{v}$ is the edge indicator vector and
$\chi_{v}\in\mathbb{R}^{n}$ is defined by

$\chi_{v}(a)\triangleq\begin{cases}\frac{1}{\sqrt{\mathrm{deg}_{G_{t+1}}(v)}}&\text{if
$a=v$ }\\\ 0&\text{otherwise.}\end{cases}$

Notice that

$\sum_{e\in E_{G_{t+1}}}X_{e}=\sum_{\begin{subarray}{c}e=\\{u,v\\}\\\ e\in
E_{G_{t+1}}\end{subarray}}w_{H_{t+1}}(u,v)\cdot\overline{\mathcal{L}}_{G_{t+1}}^{-1/2}b_{e}b_{e}^{\intercal}\overline{\mathcal{L}}_{G_{t+1}}^{-1/2}=\overline{\mathcal{L}}_{G_{t+1}}^{-1/2}\mathcal{L}_{H^{\prime}_{t+1}}\overline{\mathcal{L}}_{G_{t+1}}^{-1/2},$

where

$\mathcal{L}_{H^{\prime}_{t+1}}\triangleq\sum_{e\in
E_{G_{t+1}}}w_{H_{t+1}}(u,v)\cdot b_{e}b_{e}^{\intercal}$

is $\mathcal{L}_{H_{t+1}}$ normalised with respect to the degree of the
vertices in $G_{t+1}$. We prove that, with high probability, the top
$n_{t+1}-k$ eigenvalues of $\mathcal{L}_{H^{\prime}_{t+1}}$ and
$\mathcal{L}_{G_{t+1}}$ are approximately the same. Then, to finish the proof,
we also show that this is the case for the top $n_{t+1}-k$ eigenvalues of
$\mathcal{L}_{H_{t+1}}$ and $\mathcal{L}_{H^{\prime}_{t+1}}$, from which we
get that
$\lambda_{k+1}(\mathcal{L}_{H_{t+1}})=\Omega\left(\lambda_{k+1}(\mathcal{L}_{G_{t+1}})\right)$.

First, from (8) we get that for any edge $e$ it holds that

$\widetilde{q}(u,v)\leqslant\widetilde{p}_{u}(v)+\widetilde{p}_{v}(u)\leqslant
2\cdot\left(\frac{\tau\cdot\log(n_{t+1})}{\mathrm{deg}_{G_{t+1}}(u)}+\frac{\tau\cdot\log(n_{t+1})}{\mathrm{deg}_{G_{t+1}}(v)}\right),$
(14)

and

$\widetilde{q}(u,v)\geqslant\frac{1}{2}\cdot\left(\widetilde{p}_{u}(v)+\widetilde{p}_{v}(u)\right)\geqslant\frac{1}{4}\cdot\left(\frac{\tau\cdot\log(n_{t+1})}{\mathrm{deg}_{G_{t+1}}(u)}+\frac{\tau\cdot\log(n_{t+1})}{\mathrm{deg}_{G_{t+1}}(u)}\right).$
(15)

We start by calculating the first moment of $\sum_{e\in E_{G_{t+1}}}X_{e}$,
and have that

$\displaystyle\mathbb{E}\left[\sum_{e\in E_{G_{t+1}}}X_{e}\right]$
$\displaystyle=\sum_{\begin{subarray}{c}e=\\{u,v\\}\\\ e\in
E_{G_{t+1}}\end{subarray}}\widetilde{q}(u,v)\cdot
w_{H_{t+1}}(u,v)\cdot\overline{\mathcal{L}}_{G_{t+1}}^{-1/2}b_{e}b_{e}^{\intercal}\overline{\mathcal{L}}_{G_{t+1}}^{-1/2}\overline{\mathcal{L}}_{G_{t+1}}^{-1/2}$
$\displaystyle=\sum_{\begin{subarray}{c}e=\\{u,v\\}\\\ e\in
E_{G_{t+1}}\end{subarray}}\widetilde{q}(u,v)\cdot\frac{1}{\widetilde{q}(u,v)}\cdot\overline{\mathcal{L}}_{G_{t+1}}^{-1/2}b_{e}b_{e}^{\intercal}\overline{\mathcal{L}}_{G_{t+1}}^{-1/2}$
$\displaystyle=\overline{\mathcal{L}}_{G_{t+1}}^{-1/2}\mathcal{L}_{G_{t+1}}\overline{\mathcal{L}}_{G_{t+1}}^{-1/2}.$

Moreover, for any sampled $e=\\{u,v\\}$ we have that

$\displaystyle\|X_{e}\|$ $\displaystyle\leqslant w_{H_{t+1}}(u,v)\cdot
b_{e}^{\intercal}\overline{\mathcal{L}}_{G_{t+1}}^{-1/2}\overline{\mathcal{L}}_{G_{t+1}}^{-1/2}b_{e}$
$\displaystyle=\frac{1}{\widetilde{q}(u,v)}\cdot
b_{e}^{\intercal}\overline{\mathcal{L}}_{G_{t+1}}^{-1/2}\overline{\mathcal{L}}_{G_{t+1}}^{-1/2}b_{e}$
$\displaystyle\leqslant\frac{1}{\widetilde{q}(u,v)}\cdot\frac{1}{\lambda_{k+1}(\mathcal{L}_{G_{t+1}})}\cdot\|b_{e}\|^{2}$
$\displaystyle\leqslant\frac{4\lambda_{k+1}(\mathcal{L}_{G_{t+1}})}{C\cdot\log{n_{t+1}}\cdot\left(\frac{1}{\mathrm{deg}_{G_{t+1}}(u)}+\frac{1}{\mathrm{deg}_{G_{t+1}}(v)}\right)}\cdot\frac{1}{\lambda_{k+1}(\mathcal{L}_{G_{t+1}})}\cdot\left(\frac{1}{\mathrm{deg}_{G_{t+1}}(u)}+\frac{1}{\mathrm{deg}_{G_{t+1}}(v)}\right)$
(16) $\displaystyle=\frac{4}{C\cdot\log{n_{t+1}}},$

where the second inequality follows by the min-max theorem of eigenvalues, and
(16) holds by (15). Now we apply the matrix Chernoff bound (Lemma A.3) to
analyse the eigenvalues of $\sum_{e\in E_{G_{t+1}}}X_{e}$. We set
$\lambda_{\mathrm{max}}\left(\mathbb{E}\left[\sum_{e\in
E_{G_{t+1}}}X_{e}\right]\right)=\lambda_{\mathrm{max}}\left(\overline{\mathcal{L}}_{G_{t+1}}^{-1/2}\mathcal{L}_{G_{t+1}}\overline{\mathcal{L}}_{G_{t+1}}^{-1/2}\right)=1$,
$R=\frac{4}{C\cdot\log{n_{t+1}}}$ and $\delta=1/2$, and have that

$\mathbb{P}\left[\lambda_{\mathrm{max}}\left(\sum_{e\in
E_{G_{t+1}}}X_{e}\right)\geqslant\frac{3}{2}\right]\leqslant
n_{t+1}\cdot\left(\frac{e^{1/2}}{(1+1/2)^{3/2}}\right)^{C\cdot\log{n_{t+1}}/4}=O(1/n_{t+1}^{c})$

for some constant $c$. Therefore we get that

$\mathbb{P}\left[\lambda_{\mathrm{max}}\left(\sum_{e\in
E_{G_{t+1}}}X_{e}\right)<\frac{3}{2}\right]=1-O(1/n_{t+1}^{c}).$ (17)

Similarly, since $\lambda_{\mathrm{min}}\left(\mathbb{E}\left[\sum_{e\in
E_{G_{t+1}}}X_{e}\right]\right)=\lambda_{\mathrm{min}}\left(\overline{\mathcal{L}}_{G_{t+1}}^{-1/2}\mathcal{L}_{G_{t+1}}\overline{\mathcal{L}}_{G_{t+1}}^{-1/2}\right)=1$,
the other side of the matrix Chernoff bound gives us that

$\mathbb{P}\left[\lambda_{\mathrm{min}}\left(\sum_{e\in
E_{G_{t+1}}}X_{e}\right)>\frac{1}{2}\right]=1-O(1/n_{t+1}^{c}).$ (18)

Combining (17) and (18), it holds with probability $1-O(1/n_{t+1}^{c})$ for
any non-zero $x\in\mathbb{R}^{n_{t+1}}$ in the space spanned by
$f_{k+1},\ldots,f_{n_{t+1}}$ that

$\frac{x^{\intercal}\overline{\mathcal{L}}_{G_{t+1}}^{-1/2}\mathcal{L}_{H_{t+1}}^{{}^{\prime}}\overline{\mathcal{L}}_{G_{t+1}}^{-1/2}x}{x^{\intercal}x}\in(1/2,3/2).$

Since
$\operatorname{dim}(\operatorname{span}\\{f_{k+1},\ldots,f_{n_{t+1}}\\})=n_{t+1}-k$,
there exist $n_{t+1}-k$ orthogonal vectors whose Rayleigh quotient with
respect to $\mathcal{L}_{H_{t+1}}^{{}^{\prime}}$ is
$\Omega\left(\lambda_{k+1}\left(\mathcal{L}_{G_{t+1}}\right)\right)$. The
Courant-Fischer Theorem implies that
$\lambda_{k+1}(\mathcal{L}_{H_{t+1}}^{\prime})=\Omega\left(\lambda_{k+1}\left(\mathcal{L}_{G_{t+1}}\right)\right)$.

It only remains to show that
$\lambda_{k+1}(\mathcal{L}_{H_{t+1}})=\Omega(\lambda_{k+1}(\mathcal{L}_{H_{t+1}}^{\prime}))$,
which implies that
$\lambda_{k+1}(\mathcal{L}_{H_{t+1}})=\Omega\left(\lambda_{k+1}\left(\mathcal{L}_{G_{t+1}}\right)\right)$.
By definition of $\lambda_{k+1}(\mathcal{L}_{H_{t+1}}^{\prime})$, we have that

$\mathcal{L}_{H_{t+1}}=D_{H_{t+1}}^{-1/2}D_{G_{t+1}}^{1/2}\mathcal{L}_{H_{t+1}}^{{}^{\prime}}D_{G_{t+1}}^{1/2}D_{H_{t+1}}^{-1/2}.$

Therefore, for any $x\in\mathbb{R}^{n_{t+1}}$ and $y\triangleq
D_{G_{t+1}}^{1/2}D_{H_{t+1}}^{-1/2}x$, it holds that

$\frac{x^{\intercal}\mathcal{L}_{H_{t+1}}x}{x^{\intercal}x}=\frac{y^{\intercal}\mathcal{L}_{H_{t+1}}^{{}^{\prime}}y}{x^{\intercal}x}=\Omega\left(\frac{y^{\intercal}\mathcal{L}_{H_{t+1}}^{{}^{\prime}}y}{y^{\intercal}y}\right),$

where the final guarantee follows from the fact that the degrees in $H_{t+1}$
are preserved up to a constant factor. The conclusion of the theorem follows
from the Courant-Fischer Theorem.

Finally, it remains to analyse the amortised update time of the algorithm.
Notice that, if one only needs to sample the incoming edge at time $t+1$, then
the update time is $O(1)$. Otherwise, all the edges adjacent to some vertex
$w$ need to be resampled, and the running time for this step is
$O(\mathrm{deg}_{G_{t+1}}(w))$. However, this means that either
$\mathrm{deg}_{G_{t+1}}(w)>2\cdot\mathrm{deg}_{G_{t}}(w)$ or
$\log(n_{t+1})>2\cdot\log(n_{t})$. In the first case, this only occurs at most
every $\mathrm{deg}_{G_{t}}(w)$ edge updates, which results in the amortised
update time of $O(1)$. The second case only happens after every $n_{t}^{2}$
vertex additions, and in the worst case we only have to resample all the edges
in present in $G_{t}$ every $n_{t}^{2}$ edge updates, which again leads to the
amortised update time of $O(1)$. ∎

##  Appendix B Omitted Details from Section 4

This section contains the omitted details from Section 4, and is organised as
follows. In Section B.1 we introduce additional notation to analyse our
constructed contracted graphs. In Section B.2 we present the omitted proofs
for Lemmas 4.1, 4.2, 4.3, 4.4, and 4.5, and we formally describe the
$\mathsf{UpdateContractedGraph}$ procedure.

###  B.1 Notation

For any subset $A\subset V_{t^{\prime}}$, let $\widetilde{A}\triangleq
A\cap\widetilde{V}^{\mathrm{nc}}_{t^{\prime}}$ be the representation of $A$
among the non-contracted vertices of $\widetilde{G}_{t^{\prime}}$. Recall that
for any subset of vertices $A\subset V_{t^{\prime}}$, we use
$A^{(t)}\triangleq A\cap V_{t}$ to denote the set of vertices present at time
$t$. Let

$E_{\mathrm{added}}\triangleq E_{\mathrm{new}}\cup\Big{\\{}\\{u,v\\}\in
E_{t}~{}\mid~{}\mathrm{deg}_{G_{t^{\prime}}}(u)>2\cdot\mathrm{deg}_{G_{r}}(u)\text{
or }\mathrm{deg}_{G_{t^{\prime}}}(v)>2\cdot\mathrm{deg}_{G_{r}}(v)\Big{\\}}$

be the set of edges that have been directly added into $\widetilde{G}_{t}$,
where $\mathrm{deg}_{G_{r}}(w)$ for $r\leqslant t$ is the degree of $w$ used
to construct the contracted graph. These edges are the ones directly added as
new edges or their endpoints are pulled out from clusters in
$\widetilde{G}_{t}$. For a subset $B\subset\widetilde{V}_{t^{\prime}}$, let
$\hat{B}$ be the representation of the set $B$ in $G_{t^{\prime}}$, i.e.,

$\hat{B}\triangleq B^{\mathrm{nc}}\bigcup\left(\bigcup_{p_{i}\in
B^{\mathrm{c}}}P^{(t^{\prime})}_{i}\right),$

where $P^{(t^{\prime})}_{i}\triangleq
P_{i}\setminus(P_{i}\cap\widetilde{V}^{\mathrm{nc}}_{t^{\prime}})$,
$B^{\mathrm{nc}}\triangleq B\cap V^{\mathrm{nc}}_{t^{\prime}}$, and
$B^{\mathrm{c}}\triangleq B\cap V^{\mathrm{c}}_{t^{\prime}}$. One can see
$P^{(t^{\prime})}_{i}$ as the vertices in $P_{i}$ that are still represented
by the respective super vertex in $\widetilde{G}$.

###  B.2 Omitted Proofs

Our analysis is based on approximation guarantee of spectral clustering. The
following result, which can be shown easily by combining the proof technique
of (Peng et al., 2017) and the one of (Macgregor & Sun, 2022), will be used in
our analysis.

######  Lemma B.1.

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_{G}(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}_{G}(P_{i}\triangle S_{i})\leqslant\frac{k\cdot
C_{\ref{lem:MS22+}}}{3\Upsilon_{G}(k)}\cdot\mathrm{vol}_{G}(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)$. It also holds that

$\Phi_{G}(P_{i})=O\left(\Phi_{G}(S_{i})+\frac{k}{\Upsilon_{G}(k)}\right).$

Moreover, these $P_{1},\ldots,P_{k}$ can be computed in nearly-linear time.

Algorithm 7 $\mathsf{UpdateContractedGraph}(G_{t},\widetilde{G}_{t},e)$

1: Input: Graph $G_{t}=(V_{t},E_{t})$, contracted graph
$\widetilde{G}_{t}=(\widetilde{V}_{t},\widetilde{E}_{t},w_{\widetilde{G}_{t}})$,
incoming edge $e=\\{u,v\\}$.

2: Output: Contracted graph
$\widetilde{G}_{t+1}=(\widetilde{V}_{t+1},\widetilde{E}_{t+1},w_{\widetilde{G}_{t+1}})$

3: $V_{\mathrm{new}}\leftarrow\\{u,v\\}\setminus V_{t}$

4: $G_{t+1}\leftarrow(V_{t}\cup V_{\mathrm{new}},E_{t}\cup e)$

5: $\widetilde{G}_{t+1}\leftarrow(\widetilde{V}_{t}\cup
V_{\mathrm{new}},\widetilde{E}_{t},w_{\widetilde{G}_{t}})=(\widetilde{V}_{t+1},\widetilde{E}_{t+1},w_{\widetilde{G}_{t+1}})$

6:
$\widetilde{V}_{t+1}^{\mathrm{nc}}\leftarrow\widetilde{V}_{t+1}^{\mathrm{nc}}\cup
V_{\mathrm{new}}$

7: for $w\in\\{u,v\\}\setminus V_{\mathrm{new}}$ do

8: Let $G_{r}$ be the graph at time $r$ when the contracted graph is
constructed, and $H_{r}=(V_{r},F_{r},w_{H_{r}})$ the cluster preserving
sparsifier at time $r$.

9: if $w\notin\widetilde{V}_{t+1}^{\mathrm{nc}}$ and
$\mathrm{deg}_{G_{t+1}}(w)>2\cdot\mathrm{deg}_{G_{r}}(w)$ then

10: Let $p_{j}$ be the super node such that $w\in P_{j}$

11:
$\widetilde{V}_{t+1}^{\mathrm{nc}}\leftarrow\widetilde{V}_{t+1}^{\mathrm{nc}}\cup
w$

12: $\widetilde{E}_{t+1}\leftarrow\widetilde{E}_{t+1}\cup
E_{G_{t+1}}(w,\widetilde{V}_{t+1}^{\mathrm{nc}})$

13: for $\hat{v}\in\widetilde{V}^{\mathrm{nc}}_{t+1}$ adjacent to $w$ do

14: $w_{\widetilde{G}_{t+1}}(p_{j},\hat{v})\leftarrow
w_{\widetilde{G}_{t+1}}(p_{j},\hat{v})-1$

15: end for

16: for $\\{w,p_{i}\\}\in w\times\widetilde{V}_{t+1}^{\mathrm{c}}$ do

17: $\widetilde{E}_{t+1}\leftarrow\widetilde{E}_{t+1}\cup\\{w,p_{i}\\}$

18: $w_{\widetilde{G}_{t+1}}(w,p_{i})\leftarrow w_{G_{t+1}}(w,P^{(t+1)}_{i})$

19: $w_{\widetilde{G}_{t+1}}(p_{i},p_{j})\leftarrow
w_{\widetilde{G}_{t+1}}(p_{i},p_{j})-w_{H_{r}}(w,P^{(t+1)}_{i})$

20: end for

21: end if

22: end for

23: if $u\in\widetilde{V}_{t+1}^{\mathrm{nc}}$ and
$v\in\widetilde{V}_{t+1}^{\mathrm{nc}}$ then

24: $\widetilde{E}_{t+1}\leftarrow\widetilde{E}_{t+1}\cup\\{u,v\\}$

25: else if $u\in\widetilde{V}_{t+1}^{\mathrm{nc}}$ or
$v\in\widetilde{V}_{t+1}^{\mathrm{nc}}$ then

26: Without loss of generality, let $u\in\widetilde{V}_{t+1}^{\mathrm{nc}}$
and $v\notin\widetilde{V}_{t+1}^{\mathrm{nc}}$. Let $p_{j}$ be the supernode
such that $v\in P_{j}$

27: $\widetilde{E}_{t+1}\leftarrow\widetilde{E}_{t+1}\cup\\{u,p_{j}\\}$

28: $w_{\widetilde{G}_{t+1}}(u,p_{j})\leftarrow
w_{\widetilde{G}_{t+1}}(u,p_{j})+1$

29: else

30: Let $p_{i}$ and $p_{j}$ be the supernodes such that $u\in P_{i}$ and $v\in
P_{j}$

31: $w_{\widetilde{G}_{t+1}}(p_{i},p_{j})\leftarrow
w_{\widetilde{G}_{t+1}}(p_{i},p_{j})+1$

32: end if

33: Return
$G_{t+1}=(\widetilde{V}_{t+1},\widetilde{E}_{t+1},w_{\widetilde{G}_{t+1}})$

###### Proof of Lemma 4.1.

The running time of the algorithm is dominated by computing the total weight
$w_{H_{t}}(P_{i},P_{j})$ between every $P_{i},P_{j}\in\mathcal{P}$ (Lines
7–10), which takes $O(|F_{t}|)$ time as there are $|F_{t}|$ edges in $H_{t}$.
∎

###### Proof of Lemma 4.2.

The running time of the update operation is dominated by the case in which a
vertex is pulled out from a contracted vertex (Lines 7–22). It’s easy to see
that, if this does not happen, then the running time is $O(1)$ as the edge is
just added into $\widetilde{G}_{t}$.

Let $\\{u,v\\}$ be the added edge, and we assume Lines 7–22 are triggered. The
running time for this case is
$O(\mathrm{deg}_{G_{t+1}}(u)+\mathrm{deg}_{G_{t+1}}(v))$, since at least one
of $u$ and $v$ is pulled out from their respective contracted vertices and all
the adjacent edges are placed into the contracted graph. Notice that this only
happens if $\mathrm{deg}_{G_{t+1}}(u)>2\cdot\mathrm{deg}_{G_{t}}(u)$ or
$\mathrm{deg}_{G_{t+1}}(v)>2\cdot\mathrm{deg}_{G_{t}}(v)$. Since at least
$\mathrm{deg}_{G_{t}}(u)$ or $\mathrm{deg}_{G_{t}}(v)$ edge insertions are
needed before running Lines 7–22, the amortised per edge update time is
$O(1)$. ∎

###### Proof of Lemma 4.3.

Notice by Lemma B.1 we know it holds with high probability for all $1\leqslant
i\leqslant k$ that $\Phi_{H_{t}}(P_{i})=O\left(k\cdot\rho_{H_{t}}(k)\right)$.
By applying Theorem 3.3, it holds with high probability that
$\Phi_{H_{t}}(P_{i})=O\left(k^{2}\cdot\rho_{G_{t}}(k)\right)$. By Lemma 3.2,
we also have with high probability that
$\Phi_{G_{t}}(P_{i})=O\left(k^{2}\cdot\rho_{G_{t}}(k)\right)$. This proves the
statement. ∎

The next lemma shows that, starting from $G_{t}$ and $H_{t}$, one can easily
construct a cluster preserving sparsifier of $G_{t^{\prime}}$.

######  Lemma B.2.

Let $H^{\prime}_{t^{\prime}}\triangleq(V_{t^{\prime}},F_{t}\cup
E_{\mathrm{added}},w_{H^{\prime}_{t^{\prime}}})$ be a graph, where

$w_{H^{\prime}_{t^{\prime}}}(e)\triangleq\begin{cases}1&\text{$e\in
E_{\mathrm{added}}$}\\\ w_{H_{t}}(e)&\text{$e\in F_{t}\setminus
E_{\mathrm{added}}$}\\\ 0&\text{otherwise.}\end{cases}$

Then, it holds with high probability that $H^{\prime}_{t^{\prime}}$ is a
cluster preserving sparsifier of $G_{t^{\prime}}$.

###### Proof.

First, for any $e\in E_{\mathrm{added}}$ we know that it is included in
$H^{\prime}_{t^{\prime}}$ with probability 1. For any other edge
$e=\\{u,v\\}\in F_{t}\setminus E_{\mathrm{added}}$, we know by the
construction of $H_{t}$ using the dynamic cluster-preserving sparsifier that
the parameter used to sample $e$ from the perspective of $u$ is

$\frac{\tau\cdot\log(n_{t})}{2\cdot\mathrm{deg}_{G_{t}}(u)}\leqslant\frac{\tau\cdot\log(n_{r})}{\mathrm{deg}_{G_{r}}(u)}\leqslant\frac{2\cdot\tau\cdot\log(n_{t})}{\mathrm{deg}_{G_{t}}(u)},$

for some $1\leqslant r\leqslant t$. We also know by construction that for any
$e=\\{u,v\\}\in F_{t}\setminus E_{\mathrm{added}}$ that

$\mathrm{deg}_{G_{t^{\prime}}}(u)\leqslant 2\cdot\mathrm{deg}_{G_{t}}(u).$

Finally, it holds that $\log(n_{t})\leqslant\log(n_{t^{\prime}})\leqslant
2\log(n_{t})$. From this we get that $e$ is sampled from vertex $u$ with the
following parameter

$\frac{\tau\cdot\log(n_{t^{\prime}})}{4\cdot\mathrm{deg}_{G_{t^{\prime}}}(u)}\leqslant\frac{\tau\cdot\log(n_{r})}{\mathrm{deg}_{G_{r}}(u)}\leqslant\frac{4\cdot\tau\cdot\log(n_{t^{\prime}})}{\mathrm{deg}_{G_{t^{\prime}}}(u)}.$

Following almost the same analysis as the proof of Theorem 3.3, it holds with
high probability that $H^{\prime}_{t^{\prime}}$ is a cluster preserving
sparsifier of $G_{t^{\prime}}$. ∎

Our next lemma proves several useful properties about the contracted graph as
it is updated.

######  Lemma B.3.

The following statements hold:

  1. (C1)

It holds for any subset $B\subset
V_{t^{\prime}}\setminus\widetilde{V}_{t^{\prime}}^{\mathrm{nc}}$ that
$\mathrm{vol}_{G_{t^{\prime}}}(B)\leqslant 2\cdot\mathrm{vol}_{G_{t}}(B)$.

  2. (C2)

Suppose for a subset $A\subset V_{t^{\prime}}$ with
$\mathrm{vol}_{G_{t^{\prime}}}(A)\leqslant\mathrm{vol}({G_{t^{\prime}}})/2$ we
have that $\Phi_{G_{t}}(A^{(t)})\geqslant 1/c_{1}$ and
$\Phi_{G_{t^{\prime}}}(A)\leqslant\log^{-\varepsilon}(n_{t^{\prime}})$ for any
positive $c_{1},\varepsilon$ such that $4\cdot
c_{1}\leqslant\log^{\varepsilon}(n_{t^{\prime}})$, then it holds that

$\Phi_{\widetilde{G}_{t^{\prime}}}(\widetilde{A})\leqslant\frac{21\cdot
c_{1}}{\log^{\varepsilon}(n_{t^{\prime}})}.$

  3. (C3)

For any super node $p_{i}\in\widetilde{V}_{t}^{\mathrm{c}}$, it holds that

$\Phi_{\widetilde{G}_{t}}(p_{i})=O\left(k^{-6}\cdot\log^{-2\gamma}(n_{t})\right),$

and

$\Phi_{\widetilde{G}_{t^{\prime}}}(p_{i})=O\left(k^{-6}\cdot\log^{-\gamma}(n_{t})\right).$

Informally speaking, Property (C1) of Lemma B.3 shows that the volume of any
vertex set $B\subset V_{t^{\prime}}$ that are not directly represented in
$\widetilde{G}_{t^{\prime}}$ remains approximately the same in $G_{t}$ and
$G_{t^{\prime}}$; Property (C2) states that, if the conductance of any set
$A\subset V_{t^{\prime}}$ in $G_{t^{\prime}}$ becomes much lower than the one
in $G_{t}$, then its representative set
$\widetilde{A}\subset\widetilde{V}_{t^{\prime}}$ has low conductance; Property
(C3) further shows that the conductance of all the contracted vertices doesn’t
change significantly over time.

###### Proof of Lemma B.3.

For (C1), by construction we have that for any $u\in
V_{t^{\prime}}\setminus\widetilde{V}_{t^{\prime}}^{\mathrm{nc}}$ it holds that
$\mathrm{deg}_{G_{t^{\prime}}}(u)\leqslant 2\cdot\mathrm{deg}_{G_{t}}(u)$,
from which the statement follows.

Next, we prove (C2). The following two claims will be used in our analysis.

######  Claim B.3.1.

It holds that
$\mathrm{vol}_{E_{\mathrm{new}}}(A)\geqslant\frac{\mathrm{vol}_{G_{t}}(A^{(t)})\cdot\log^{\varepsilon}(n_{t^{\prime}})}{2\cdot
c_{1}}$.

###### Proof.

Assume by contradiction that
$\mathrm{vol}_{E_{\mathrm{new}}}(A)<\frac{\mathrm{vol}_{G_{t}}(A^{(t)})\cdot\log^{\varepsilon}(n_{t^{\prime}})}{2\cdot
c_{1}}$. We have that

$\displaystyle\Phi_{G_{t^{\prime}}}(A)$
$\displaystyle=\frac{w_{G_{t}}(A^{(t)},V_{t}\setminus
A^{(t)})+w_{E_{\mathrm{new}}}(A,V_{t}\setminus
A)}{\mathrm{vol}_{G_{t}}(A^{(t)})+\mathrm{vol}_{E_{\mathrm{new}}}(A)}$
$\displaystyle\geqslant\frac{w_{G_{t}}(A^{(t)},V_{t}\setminus
A^{(t)})}{\mathrm{vol}_{G_{t}}(A^{(t)})+\mathrm{vol}_{E_{\mathrm{new}}}(A)}$
$\displaystyle\geqslant\frac{1}{2}\min\left\\{\frac{w_{G_{t}}(A^{(t)},V_{t}\setminus
A^{(t)})}{\mathrm{vol}_{G_{t}}(A^{(t)})},\frac{w_{G_{t}}(A^{(t)},V_{t}\setminus
A^{(t)})}{\mathrm{vol}_{E_{\mathrm{new}}}(A)}\right\\}$
$\displaystyle\geqslant\frac{1}{2}\min\left\\{\Phi_{G_{t}}(A^{(t)}),\frac{\mathrm{vol}_{G_{t}}(A^{(t)})}{c_{1}\cdot\mathrm{vol}_{E_{\mathrm{new}}}(A)}\right\\}$
$\displaystyle>\frac{1}{\log^{\varepsilon}(n_{t^{\prime}})},$

where on the last line we used the contradictory assumption. This contradicts
the condition of
$\Phi_{G_{t^{\prime}}}(A)\leqslant\log^{-\varepsilon}(n_{t^{\prime}})$, and
hence the statement holds. ∎

Notice that this claim implies that

$\displaystyle\mathrm{vol}_{G_{t^{\prime}}}(A)$
$\displaystyle=\mathrm{vol}_{G_{t}}(A^{(t)})+\mathrm{vol}_{E_{\mathrm{new}}}(A)$
$\displaystyle\geqslant\left(1+\frac{\log^{\varepsilon}(n_{t^{\prime}})}{2\cdot
c_{1}}\right)\cdot\mathrm{vol}_{G_{t}}(A^{(t)})$
$\displaystyle\geqslant\left(1+\frac{\log^{\varepsilon}(n_{t^{\prime}})}{4\cdot
c_{1}}+\frac{\log^{\varepsilon}(n_{t^{\prime}})}{4\cdot
c_{1}}\right)\cdot\mathrm{vol}_{G_{t}}(A^{(t)})$
$\displaystyle\geqslant\left(2+\frac{\log^{\varepsilon}(n_{t^{\prime}})}{4\cdot
c_{1}}\right)\cdot\mathrm{vol}_{G_{t}}(A^{(t)})$ (19)

where the last inequality follows from the fact that $4\cdot
c_{1}\leqslant\log^{\varepsilon}(n_{t^{\prime}})$.

######  Claim B.3.2.

It holds that
$\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(\widetilde{A})\geqslant\frac{\log^{\varepsilon}(n_{t^{\prime}})}{4\cdot
c_{1}}\cdot\mathrm{vol}_{G_{t}}(A^{(t)})$.

###### Proof.

Assume by contradiction that
$\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(\widetilde{A})<\frac{\log^{\varepsilon}(n_{t^{\prime}})}{4\cdot
c_{1}}\cdot\mathrm{vol}_{G_{t}}(A^{(t)})$. Then, it holds that

$\displaystyle\mathrm{vol}_{G_{t^{\prime}}}(A)$
$\displaystyle=\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(\widetilde{A})+\mathrm{vol}_{G_{t^{\prime}}}(A\setminus\widetilde{A})$
$\displaystyle\leqslant\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(\widetilde{A})+2\cdot\mathrm{vol}_{G_{t}}(A\setminus\widetilde{A})$
$\displaystyle<\frac{\log^{\varepsilon}(n_{t^{\prime}})}{4\cdot
c_{1}}\cdot\mathrm{vol}_{G_{t}}(A^{(t)})+2\cdot\mathrm{vol}_{G_{t}}(A^{(t)}),$

where the first inequality holds by statement (C1). Hence, we reach a
contradiction with (19), and the claim holds. ∎

Now we are ready to prove statement (C2). We have that

$\displaystyle\Phi_{\widetilde{G}_{t^{\prime}}}(\widetilde{A})$
$\displaystyle=\frac{w_{\widetilde{G}_{t^{\prime}}}(\widetilde{A},\widetilde{V}_{t^{\prime}}\setminus\widetilde{A})}{\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(\widetilde{A})}$
$\displaystyle\leqslant\frac{w_{G_{t^{\prime}}}(A,V_{t}\setminus
A)+w_{G_{t^{\prime}}}(A\setminus\widetilde{A},\widetilde{A})}{\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(\widetilde{A})}$
$\displaystyle\leqslant\frac{\log^{-\varepsilon}(n_{t^{\prime}})\cdot\mathrm{vol}_{G_{t^{\prime}}}(A)+\mathrm{vol}_{G_{t^{\prime}}}(A\setminus\widetilde{A})}{\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(\widetilde{A})}$
$\displaystyle\leqslant\frac{\mathrm{vol}_{G_{t^{\prime}}}(A)}{\log^{\varepsilon}(n_{t^{\prime}})\cdot\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(\widetilde{A})}+\frac{8\cdot
c_{1}\cdot\mathrm{vol}_{G_{t}}(A^{(t)})}{\mathrm{vol}_{G_{t}}(A^{(t)})\cdot\log^{\varepsilon}(n_{t^{\prime}})}$
(20)
$\displaystyle\leqslant\frac{\mathrm{vol}_{G_{t}}(A^{(t)})+\mathrm{vol}_{E_{\mathrm{new}}}(A)}{\log^{\varepsilon}(n_{t^{\prime}})\cdot\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(\widetilde{A})}+\frac{8\cdot
c_{1}}{\log^{\varepsilon}(n_{t^{\prime}})}$
$\displaystyle\leqslant\frac{3\cdot\mathrm{vol}_{G_{t}}(A^{(t)})+\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(\widetilde{A})}{\log^{\varepsilon}(n_{t^{\prime}})\cdot\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(\widetilde{A})}+\frac{8\cdot
c_{1}}{\log^{\varepsilon}(n_{t^{\prime}})}$ (21)
$\displaystyle\leqslant\frac{3\cdot\mathrm{vol}_{G_{t}}(A^{(t)})\cdot
c_{1}\cdot
4}{\log^{2\varepsilon}(n_{t^{\prime}})\cdot\mathrm{vol}_{G_{t}}(A^{(t)})}+\frac{\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(A)}{\log^{\varepsilon}(n_{t^{\prime}})\cdot\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(\widetilde{A})}+\frac{8\cdot
c_{1}}{\log^{\varepsilon}(n_{t^{\prime}})}$ (22)
$\displaystyle\leqslant\frac{12\cdot
c_{1}}{\log^{2\varepsilon}(n_{t^{\prime}})}+\frac{1}{\log^{\varepsilon}(n_{t^{\prime}})}+\frac{8\cdot
c_{1}}{\log^{\varepsilon}(n_{t^{\prime}})}$
$\displaystyle\leqslant\frac{1+20\cdot
c_{1}}{\log^{\varepsilon}(n_{t^{\prime}})}\leqslant\frac{21\cdot
c_{1}}{\log^{\varepsilon}(n_{t^{\prime}})},$

where (20) holds by Claim B.3.2 and the fact that
$\mathrm{vol}_{G_{t^{\prime}}}(A\setminus\widetilde{A})\leqslant
2\cdot\mathrm{vol}_{G_{t}}(A\setminus\widetilde{A})\leqslant
2\cdot\mathrm{vol}_{G_{t}}(A^{(t)})$ by statement (C1). (21) holds because by
construction
$\mathrm{vol}_{E_{\mathrm{new}}}(A)\leqslant\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(\widetilde{A})+\mathrm{vol}_{G_{t^{\prime}}}(A\setminus\widetilde{A})\leqslant\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(\widetilde{A})+2\cdot\mathrm{vol}_{G_{t}}(A^{(t)})$,
and (22) holds because of Claim B.3.2.

Finally, we prove statement (C3). For any $P_{i}\in\mathcal{P}$, we have by
construction that

$\displaystyle\Phi_{\widetilde{G}_{t}}(p_{i})=\Phi_{H_{t}}(P_{i})=O\left(k^{-6}\cdot\log^{-2\gamma}(n_{t})\right),$
(23)

where the last equality holds by Lemma 4.3. This proves the first part of the
statement. Next, notice that for any $p_{i}\in\widetilde{V}_{t}^{\mathrm{c}}$,
because $G_{t}$ is connected and each $P_{i}$ has almost identical volume as
the corresponding optimal $S_{i}$ in $G_{t}$ (Lemma 3.2), by construction it
holds that

$\mathrm{vol}_{\widetilde{G}_{t}}(p_{i})=\Omega(k^{6}\cdot\log^{2\gamma}(n_{t})),$
(24)

and

$\mathrm{vol}_{\widetilde{G}_{t}}(\widetilde{V}_{t}\setminus
p_{i})=\Omega(k^{6}\cdot\log^{2\gamma}(n_{t})).$ (25)

Taking this into account, we get that

$\displaystyle
w_{\widetilde{G}_{t^{\prime}}}(p_{i},\widetilde{V}_{t^{\prime}}\setminus
p_{i})$ $\displaystyle\leqslant
w_{\widetilde{G}_{t}}(p_{i},\widetilde{V}_{t}\setminus
p_{i})+|E_{\mathrm{new}}|+w_{G_{t^{\prime}}}\left(P_{i}\cap\widetilde{V}_{t^{\prime}}^{\mathrm{nc}},P_{i}\setminus(P_{i}\cap\widetilde{V}_{t^{\prime}}^{\mathrm{nc}})\right)$
$\displaystyle\leqslant w_{\widetilde{G}_{t}}(p_{i},\widetilde{V}\setminus
p_{i})+\log^{\gamma}(n_{t})+\mathrm{vol}_{G_{t^{\prime}}}\left(P_{i}\cap\widetilde{V}_{t^{\prime}}^{\mathrm{nc}}\right)$
$\displaystyle\leqslant\Phi_{\widetilde{G}_{t}}(p_{i})\cdot\min\\{\mathrm{vol}_{\widetilde{G}_{t}}(p_{i}),\mathrm{vol}_{\widetilde{G}_{t}}(\widetilde{V}\setminus
p_{i})\\}+\log^{\gamma}(n_{t})+2\cdot\log^{\gamma}(n_{t})$ (26)
$\displaystyle=O\left(k^{-6}\cdot\log^{-2\gamma}(n_{t})\right)\cdot\min\\{\mathrm{vol}_{\widetilde{G}_{t}}(p_{i}),\mathrm{vol}_{\widetilde{G}_{t}}(\widetilde{V}\setminus
p_{i})\\}+3\cdot\log^{\gamma}(n_{t}),$ (27)

where (26) holds because
$\mathrm{vol}_{G_{t^{\prime}}}(P_{i}\cap\widetilde{V}_{t^{\prime}}^{\mathrm{nc}})\leqslant
2\cdot\log^{\gamma}(n_{t})$ as every vertex that is pulled out of $p_{i}$
needs to at least double in degree, so adding $|E_{\mathrm{new}}|$ edges
ensures at most $2\cdot|E_{\mathrm{new}}|$ volume can be pulled out of
$p_{i}$, (27) holds because of (23). Moreover, we also have that

$\displaystyle\min\\{\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(p_{i}),\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(\widetilde{V}_{t^{\prime}}\setminus
p_{i})\\}$
$\displaystyle\geqslant\min\\{\mathrm{vol}_{\widetilde{G}_{t}}(p_{i})-2\cdot\log^{\gamma}(n_{t}),\mathrm{vol}_{\widetilde{G}_{t}}(\widetilde{V}_{t}\setminus
p_{i})\\}$ (28)
$\displaystyle=\Omega\left(\min\\{\mathrm{vol}_{\widetilde{G}_{t}}(p_{i}),\mathrm{vol}_{\widetilde{G}_{t}}(\widetilde{V}_{t}\setminus
p_{i})\\}\right),$ (29)

where (28) holds because
$\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(p_{i})\geqslant\mathrm{vol}_{\widetilde{G}_{t}}(p_{i})-\mathrm{vol}_{G_{t^{\prime}}}(P_{i}\cap\widetilde{V}_{t^{\prime}}^{\mathrm{nc}})\geqslant\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(p_{i})-2\cdot\log^{\gamma}(n_{t})$,
and (29) holds because of (24) and (25). Combining (27) and (29), we have for
any $p_{i}\in\widetilde{V}_{t}^{\mathrm{c}}$ that

$\Phi_{\widetilde{G}_{t^{\prime}}}(p_{i})=\frac{w_{\widetilde{G}_{t^{\prime}}}(p_{i},\widetilde{V}_{t^{\prime}}\setminus
p_{i})}{\min\\{\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(p_{i}),\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(\widetilde{V}_{t^{\prime}}\setminus
p_{i})\\}}=O\left(k^{-6}\cdot\log^{-\gamma}(n_{t})\right),$

which proves the second part of statement (C3). ∎

######  Corollary B.4.

Suppose for a subset $A\subset V_{t^{\prime}}$ with
$\mathrm{vol}_{G_{t^{\prime}}}(A)\leqslant\mathrm{vol}({G_{t^{\prime}}})/2$,
it holds that $\Phi_{\widetilde{G}_{t^{\prime}}}(\widetilde{A})>(21\cdot
c_{1})\cdot\log^{-\varepsilon}(n_{t^{\prime}})$ and
$\Phi_{G_{t^{\prime}}}(A)\leqslant\log^{-\varepsilon}(n_{t^{\prime}})$ for any
positive $c_{1},\varepsilon$ satisfying $4\cdot
c_{1}\leqslant\log^{\varepsilon}(n_{t^{\prime}})$. Then, it holds that
$\Phi_{G_{t}}(A^{(t)})<1/c_{1}.$

###### Proof of Corollary B.4.

Assume by contradiction that $\Phi_{G_{t}}(A^{(t)})\geqslant 1/c_{1}$. Then,
by statement (C2) in Lemma B.3 and the fact that
$\Phi_{G_{t^{\prime}}}(A)\leqslant\log^{-\varepsilon}(n_{t^{\prime}})$, it
holds that $\Phi_{\widetilde{G}_{t^{\prime}}}(\widetilde{A})\leqslant(21\cdot
c_{1})\cdot\log^{-\varepsilon}(n_{t^{\prime}})$, which is a contradiction.
Hence, it holds that $\Phi_{G_{t}}(A^{(t)})<1/c_{1}$. ∎

Before analysing the spectral gap in the contracted graph
$\widetilde{G}_{t^{\prime}}$ with respect to the spectral gap in the full
graph $G_{t^{\prime}}$, we show that for any small subset of vertices
$A\subset V$ with a low value of $\Phi_{G_{t^{\prime}}}(A)$, the conductance
of its corresponding set in the contracted graph
$\Phi_{\widetilde{G}_{t^{\prime}}}(\widetilde{A})$ is low as well.

######  Lemma B.5.

Let $C\subset V_{t^{\prime}}$ be a subset of vertices such that
$\mathrm{vol}_{G_{t^{\prime}}}(C)\leqslant k^{6}\cdot\log^{2\gamma}(n_{t})$
and $\Phi_{G_{t^{\prime}}}(C)\leqslant\log^{-\varepsilon}(n_{t^{\prime}})$ for
some constant $\varepsilon>0$. Then, it holds that

$\Phi_{\widetilde{G}_{t^{\prime}}}(\widetilde{C})=O(\log^{-0.9\varepsilon}(n_{t^{\prime}})).$

###### Proof.

We prove this by contradiction. Assume by contradiction that

$\Phi_{\widetilde{G}_{t^{\prime}}}(\widetilde{C})>\frac{21}{4}\cdot\log^{0.1\varepsilon}(n_{t^{\prime}})\cdot\log^{-\varepsilon}(n_{t^{\prime}})=\frac{21}{4}\cdot\log^{-0.9\varepsilon}(n_{t^{\prime}}).$

Setting $c_{1}\triangleq(1/4)\cdot\log^{0.1\varepsilon}(n_{t^{\prime}})$, it
holds by Corollary B.4 that

$\Phi_{G_{t}}(C^{(t)})<4\cdot\log^{-0.1\varepsilon}(n_{t^{\prime}}).$ (30)

We will show that $C^{(t)}$ can be used to create a $(k+1)$-partition in
$G_{t}$ with low outer conductance, contradicting with the fact that
$\lambda_{k+1}(G_{t})=\Omega(1)$.

Let $S_{1},\ldots S_{k}$ be the optimal clusters in $G_{t}$ corresponding to
$\rho_{G_{t}}(k)$. Given that $G_{t}$ is a connected graph and
$\rho_{G_{t}}(k)=O\left(k^{-8}\cdot\log^{-2\gamma}(n_{t})\right)$, it holds
that
$\mathrm{vol}_{G_{t}}(S_{i})=\Omega\left(k^{8}\cdot\log^{2\gamma}(n_{t})\right)$
for all $1\leqslant i\leqslant k$. We then create the following
$(k+1)$-partition:

$\mathcal{A}\triangleq C^{(t)}\cup\left\\{S_{1}\setminus
C^{(t)},\ldots,S_{k}\setminus C^{(t)}\right\\},$

which is a valid partition as we know that
$\mathrm{vol}_{G_{t}}(C^{(t)})\leqslant\mathrm{vol}_{G_{t^{\prime}}}(C)\leqslant
k^{6}\cdot\log^{2\gamma}(n_{t})$ by the conditions of the lemma. Now we will
compute the conductance of each cluster in $\mathcal{A}$.

First of all, we have from (30) that

$\Phi_{G_{t}}(C^{(t)})<4\cdot\log^{-0.1\varepsilon}(n_{t^{\prime}}).$ (31)

Second, for any cluster $S_{j}\setminus C^{(t)}$ we have that

$\Phi_{G_{t}}(S_{j}\setminus C^{(t)})=\frac{w_{G_{t}}(S_{j}\setminus
C^{(t)},V_{t}\setminus(S_{j}\setminus
C^{(t)}))}{\min\\{\mathrm{vol}_{G_{t}}(S_{j}\setminus
C^{(t)}),\mathrm{vol}_{G_{t}}(V_{t}\setminus(S_{j}\setminus C^{(t)}))\\}}.$

Our proof is by the following case distinction:

Case 1: $\min\\{\mathrm{vol}_{G_{t}}(S_{j}\setminus
C^{(t)}),\mathrm{vol}_{G_{t}}(V_{t}\setminus(S_{j}\setminus
C^{(t)}))\\}=\mathrm{vol}_{G_{t}}(V_{t}\setminus(S_{j}\setminus C^{(t)}))$.

$\displaystyle\Phi_{G_{t}}(S_{j}\setminus C^{(t)})$
$\displaystyle=\frac{w_{G_{t}}(S_{j}\setminus
C^{(t)},V_{t}\setminus(S_{j}\setminus
C^{(t)}))}{\mathrm{vol}_{G_{t}}(V_{t}\setminus(S_{j}\setminus C^{(t)}))}$
$\displaystyle\leqslant\frac{w_{G_{t}}(S_{j},V_{t}\setminus
S_{j})+w_{G_{t}}(C^{(t)},V_{t}\setminus
C^{(t)})}{\mathrm{vol}_{G_{t}}(V_{t}\setminus
S_{j})+\mathrm{vol}_{G_{t}}(C^{(t)}\cap S_{j})}$ $\displaystyle\leqslant
2\cdot\max\left\\{\frac{w_{G_{t}}(S_{j},V_{t}\setminus
S_{j})}{\mathrm{vol}_{G_{t}}(V_{t}\setminus
S_{j})},\frac{w_{G_{t}}(C^{(t)},V_{t}\setminus
C^{(t)})}{\mathrm{vol}_{G_{t}}(V_{t}\setminus S_{j})}\right\\}$
$\displaystyle\leqslant
2\cdot\max\left\\{\Phi_{G_{t}}(S_{j}),\Phi_{G_{t}}(C^{(t)})\right\\}$ (32)
$\displaystyle\leqslant\max\\{O\left(k^{-8}\cdot\log^{-2\gamma}(n_{t})\right),4\cdot\log^{-0.1\varepsilon}(n_{t^{\prime}})\\},$

where for (32) it holds that
$\min\\{\mathrm{vol}_{G_{t}}(S_{j}),\mathrm{vol}_{G_{t}}(V_{t}\setminus
S_{j})\\}=\mathrm{vol}_{G_{t}}(V_{t}\setminus S_{j})$ because we know that
$\mathrm{vol}(G_{t})/2\geqslant\mathrm{vol}_{G_{t}}(V_{t}\setminus(S_{j}\setminus
C^{(t)}))\geqslant\mathrm{vol}_{G_{t}}(V_{t}\setminus S_{j})$, and we also
know that $\mathrm{vol}_{G_{t}}(V_{t}\setminus
S_{j})\geqslant\mathrm{vol}_{G_{t}}(C^{(t)})$.

Case 2: $\min\\{\mathrm{vol}_{G_{t}}(S_{j}\setminus
C^{(t)}),\mathrm{vol}_{G_{t}}(V_{t}\setminus(S_{j}\setminus
C^{(t)}))\\}=\mathrm{vol}_{G_{t}}(S_{j}\setminus C^{(t)})$.

$\displaystyle\Phi_{G_{t}}(S_{j}\setminus C^{(t)})$
$\displaystyle=\frac{w_{G_{t}}(S_{j}\setminus
C^{(t)},V_{t}\setminus(S_{j}\setminus
C^{(t)}))}{\mathrm{vol}_{G_{t}}(S_{j}\setminus C^{(t)})}$
$\displaystyle\leqslant\frac{w_{G_{t}}(S_{j},V_{t}\setminus
S_{j})+w_{G_{t}}(C^{(t)},V_{t}\setminus
C^{(t)})}{\mathrm{vol}_{G_{t}}(S_{j})-\mathrm{vol}_{G_{t}}(C^{(t)})}$
$\displaystyle\leqslant\frac{w_{G_{t}}(S_{j},V_{t}\setminus
S_{j})+w_{G_{t}}(C^{(t)},V_{t}\setminus
C^{(t)})}{\Omega\left(\mathrm{vol}_{G_{t}}(S_{j})\right)}$ (33)
$\displaystyle=O\left(\Phi_{G_{t}}(S_{j})\right)+O\left(\Phi_{G_{t}}(C^{(t)})\right)$
(34)
$\displaystyle=2\cdot\max\left\\{O\left(k^{-8}\cdot\log^{-2\gamma}(n_{t})\right),O\left(\log^{-0.1\varepsilon}(n_{t^{\prime}})\right)\right\\}$
(35)

where (33) holds because
$\mathrm{vol}_{G_{t}}(S_{i})=\Omega\left(k^{8}\cdot\log^{2\gamma}(n_{t})\right)$
and
$\mathrm{vol}_{G_{t}}(C^{(t)})=O\left(k^{6}\cdot\log^{2\gamma}(n_{t})\right)$,
(34) holds because $w_{G_{t}}(S_{j},V_{t}\setminus
S_{j})\leqslant\Phi_{G_{t}}(S_{j})\cdot\mathrm{vol}_{G_{t}}(S_{j})$ and
$w_{G_{t}}(C^{(t)},V_{t}\setminus
C^{(t)})\leqslant\Phi_{G_{t}}(C^{(t)})\cdot\mathrm{vol}_{G_{t}}(C^{(t)})$.

Combining both cases, we have for every $1\leqslant j\leqslant k$ that

$\Phi_{G_{t}}(S_{j}\setminus
C^{(t)})=2\cdot\max\left\\{O\left(k^{-8}\cdot\log^{-2\gamma}(n_{t})\right),O\left(\log^{-0.1\varepsilon}(n_{t^{\prime}})\right)\right\\}.$
(36)

Therefore, by combining (31) and (36), we have shown that

$\rho_{G_{t}}(k+1)\leqslant\max_{A_{j}\in\mathcal{A}}\Phi_{G_{t}}(A_{j})=2\cdot\max\left\\{O\left(k^{-8}\cdot\log^{-2\gamma}(n_{t})\right),O\left(\log^{-0.1\varepsilon}(n_{t^{\prime}})\right)\right\\},$

which contradicts the fact that
$\rho_{G_{t}}(k+1)\geqslant\frac{\lambda_{k+1}(\mathcal{L}_{G_{t}})}{2}=\Omega(1)$.
Hence, the statement of the lemma follows. ∎

###### Proof of Lemma 4.4.

We first prove the first statement. Let $\mathcal{S}=S_{1},\ldots,S_{\ell}$ be
a set of clusters that achieve $\rho_{G_{t^{\prime}}}(\ell)$. For ease of
notation we set

$\mathcal{S}_{\mathrm{small}}\triangleq\mathcal{S}^{(t^{\prime})}_{\mathrm{small}}\left(k^{6}\cdot\log^{2\gamma}(n_{t})\right)$

to be the clusters in $\mathcal{S}$ with volume at most
$k^{6}\cdot\log^{2\gamma}(n_{t})$, and similarly

$\mathcal{S}_{\mathrm{large}}\triangleq\mathcal{S}^{(t^{\prime})}_{\mathrm{large}}\left(k^{6}\cdot\log^{2\gamma}(n_{t})\right).$

We will use the partition $\mathcal{S}$, which has low outer conductance in
$G_{t^{\prime}}$, to create an $r$-way partition in
$\widetilde{G}_{t^{\prime}}$ with low $r$-way expansion. We construct this
$r$-way partition, denoted by $\mathcal{R}$, as follows:

$\mathcal{R}\triangleq\left\\{\widetilde{S}_{1},\ldots,\widetilde{S}_{\ell_{1}},p_{1},\ldots,p_{k-1},p^{*}_{k}\right\\}$

where $\ell_{1}\triangleq|\mathcal{S}_{\mathrm{small}}|$, and we define

$p^{*}_{k}\triangleq
p_{k}\cup\left(\widetilde{V}_{t^{\prime}}^{\mathrm{nc}}\setminus\bigcup_{S_{j}\in\mathcal{S}_{\mathrm{small}}}\widetilde{S}_{j}\right)$

to be the union of the super node $p_{k}$ with the leftover non-contracted
vertices which do not belong to any $\widetilde{S}_{j}$. We start by showing
that $\mathcal{R}$ has low $r$-way expansion:

  * •

By Lemma B.5, we know that for every $S_{j}\in\mathcal{S}_{\mathrm{small}}$,
it holds that
$\Phi_{\widetilde{G}_{t^{\prime}}}(\widetilde{S}_{j})=O\left(\log^{-0.9\alpha}(n_{t^{\prime}})\right)$.

  * •

By Property (C3) of Lemma B.3, we know that for every super node
$p_{i}\in\\{p_{k_{1}},\ldots p_{k-1}\\}$ it holds that
$\Phi_{\widetilde{G}_{t^{\prime}}}(p_{i})=O\left(k^{-6}\cdot\log^{-\gamma}(n_{t^{\prime}})\right)$.

  * •

Finally, for $p_{k}^{*}$ we know that

$\displaystyle\Phi_{\widetilde{G}_{t^{\prime}}}(p^{*}_{k})=\frac{w_{\widetilde{G}_{t^{\prime}}}(p^{*}_{k},\widetilde{V}_{t^{\prime}}\setminus
p^{*}_{k})}{\min\left\\{\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(p^{*}_{k}),\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(\widetilde{V}_{t^{\prime}}\setminus
p^{*}_{k})\right\\}}.$ (37)

We split the computation of this conductance into two cases.

Case 1: Suppose
$\min\left\\{\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(p^{*}_{k}),\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(\widetilde{V}_{t^{\prime}}\setminus
p^{*}_{k})\right\\}=\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(p^{*}_{k})$.
Then, we have that

$\displaystyle\Phi_{\widetilde{G}_{t^{\prime}}}(p^{*}_{k})$
$\displaystyle=\frac{w_{\widetilde{G}_{t^{\prime}}}(p^{*}_{k},\widetilde{V}_{t^{\prime}}\setminus
p^{*}_{k})}{\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(p^{*}_{k})}$
$\displaystyle\leqslant\frac{w_{\widetilde{G}_{t}}(p_{k},\widetilde{V}_{t}\setminus
p_{k})+\log^{\gamma}(n_{t^{\prime}})+\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(\widetilde{V}_{t^{\prime}}^{\mathrm{nc}})}{\mathrm{vol}_{\widetilde{G}_{t}}(p_{k})-\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(\widetilde{V}_{t^{\prime}}^{\mathrm{nc}})}$
(38)
$\displaystyle\leqslant\frac{\Phi_{\widetilde{G}_{t}}(p_{k})\cdot\mathrm{vol}_{\widetilde{G}_{t}}(p_{k})+3\cdot\log^{\gamma}(n_{t^{\prime}})}{\Omega\left(\mathrm{vol}_{\widetilde{G}_{t}}(p_{k})\right)}$
(39)
$\displaystyle=\frac{O\left(k^{-6}\cdot\log^{-2\gamma}(n_{t})\right)\cdot\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(p_{k})+3\cdot\log^{\gamma}(n_{t^{\prime}})}{\Omega\left(\mathrm{vol}_{\widetilde{G}_{t}}(p_{k})\right)}$
(40)
$\displaystyle=\frac{O\left(k^{-6}\cdot\log^{-2\gamma}(n_{t})\cdot\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(p_{k})\right)}{\Omega\left(\mathrm{vol}_{\widetilde{G}_{t}}(p_{k})\right)}$
(41) $\displaystyle=O\left(k^{-6}\cdot\log^{-2\gamma}(n_{t})\right),$

where (38) holds because $|E_{\mathrm{new}}|\leqslant\log^{\gamma}(n_{t})$ is
the maximum amount of weight that can be added between $p_{k}$ and its
complement, (39) holds because
$\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(\widetilde{V}_{t^{\prime}}^{\mathrm{nc}})\leqslant
2\cdot|E_{\mathrm{new}}|$ is the maximum volume of non-contracted vertices
that can be added to $\widetilde{G}_{t^{\prime}}$ and (40) holds because of
statement (C3) of Lemma B.3, and (41) holds since
$\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(p_{k})\geqslant\mathrm{vol}(G_{t})/k\geqslant
n_{t}/k$.

Case 2: Suppose
$\min\left\\{\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(p^{*}_{k}),\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(\widetilde{V}_{t^{\prime}}\setminus
p^{*}_{k})\right\\}=\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(\widetilde{V}_{t^{\prime}}\setminus
p^{*}_{k})$. Then it holds that the conductance of $p^{*}_{k}$ is upper
bounded by the maximum conductance of every other cluster in $\mathcal{R}$,
i.e.,

$\displaystyle\Phi_{\widetilde{G}_{t^{\prime}}}(p^{*}_{k})$
$\displaystyle=\frac{w_{\widetilde{G}_{t^{\prime}}}(p^{*}_{k},\widetilde{V}_{t^{\prime}}\setminus
p^{*}_{k})}{\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(\widetilde{V}_{t^{\prime}}\setminus
p^{*}_{k})}$
$\displaystyle\leqslant\frac{\sum_{S_{j}\in\mathcal{S}_{\mathrm{small}}}w_{\widetilde{G}_{t^{\prime}}}(\widetilde{S}_{j},\widetilde{V}_{t^{\prime}}\setminus\widetilde{S}_{j})+\sum_{j=1}^{k-1}w_{\widetilde{G}_{t^{\prime}}}(p_{j},\widetilde{V}_{t^{\prime}}\setminus
p_{j})}{\sum_{S_{j}\in\mathcal{S}_{\mathrm{small}}}\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(\widetilde{S}_{j})+\sum_{j=1}^{k-1}\mathrm{vol}_{\widetilde{G}_{t^{\prime}}}(p_{j})}$
$\displaystyle\leqslant\max\left\\{\max_{S_{j}\in\mathcal{S}_{\mathrm{small}}}\left\\{\Phi_{\widetilde{G}_{t^{\prime}}}(\widetilde{S}_{j})\right\\},\max_{p_{j}\in\\{p_{1},\ldots,p_{k-1}\\}}\left\\{\Phi_{\widetilde{G}_{t^{\prime}}}(p_{j})\right\\}\right\\}$
$\displaystyle=\max\left\\{O\left(\log^{-0.9\alpha}(n_{t^{\prime}})\right),O\left(k^{-6}\cdot\log^{-\gamma}(n_{t^{\prime}})\right)\right\\},$

where the last inequality follows by the mediant inequality.

Combining the two cases, we have that

$\Phi_{\widetilde{G}_{t^{\prime}}}(p^{*}_{k})=\max\left\\{O\left(\log^{-0.9\alpha}(n_{t^{\prime}})\right),O\left(k^{-6}\cdot\log^{-\gamma}(n_{t^{\prime}})\right)\right\\}.$

We have so far analysed the conductance of each of the clusters in the
partition $\mathcal{R}$, and have shown that

$\rho_{\widetilde{G}_{t^{\prime}}}(r)=\max\left\\{O\left(\log^{-0.9\alpha}(n_{t^{\prime}})\right),O\left(k^{-6}\cdot\log^{-\gamma}(n_{t^{\prime}})\right)\right\\}.$
(42)

Before reaching the final contradiction, we prove the following claim.

######  Claim B.5.1.

It holds that $r\geqslant\ell$.

###### Proof.

Assume by contradiction that $r<\ell$. In this case, we know that
$r=|\mathcal{S}_{\mathrm{small}}|+|\mathcal{P}|$, and $\ell=|\mathcal{S}|$.
Therefore, the condition of $r<\ell$ gives us that
$|\mathcal{S}_{\mathrm{small}}|+|\mathcal{P}|<|\mathcal{S}|$, which implies
that
$|P|<|\mathcal{S}|-|\mathcal{S}_{\mathrm{small}}|=|\mathcal{S}_{\mathrm{large}}|$.
This means that the number of large clusters in $\mathcal{S}$ is greater than
the number of clusters in $\mathcal{P}$.

It therefore holds that $|\mathcal{S}_{\mathrm{large}}|>|\mathcal{P}|=k$.
Furthermore, since it holds that for every
$S_{j}\in\mathcal{S}_{\mathrm{large}}$ that
$\mathrm{vol}_{G_{t^{\prime}}}(S_{j})>k^{6}\cdot\log^{2\gamma}(n_{t})$, and
the number of new edges is $|E_{\mathrm{new}}|\leqslant\log^{\gamma}(n_{t})$,
it also holds that

$\Phi_{G_{t}}(S_{j})=O\left(\Phi_{G_{t^{\prime}}}(S_{j})\right)=\max\left\\{O\left(\log^{-\alpha}(n_{t^{\prime}})\right),k^{6}\cdot\log^{\gamma}(n_{t})\right\\}.$

This means that $\mathcal{S}_{\mathrm{large}}$ is a set of
$|\mathcal{S}_{\mathrm{large}}|\geqslant k+1$ disjoint subsets in $G_{t}$ with
low conductance, which contradicts the higher-order Cheeger inequality and
proves the claim. ∎

Combining (42) with Claim B.5.1 gives us that

$\rho_{\widetilde{G}_{t^{\prime}}}(\ell)=\max\left\\{O\left(\log^{-0.9\alpha}(n_{t^{\prime}})\right),O\left(k^{-6}\cdot\log^{-\gamma}(n_{t^{\prime}})\right)\right\\},$

and this proves the first statement.

Next we prove the second statement. Let $A_{1},\ldots A_{\ell}$ be the
partition such that
$\Phi_{\widetilde{G}_{t^{\prime}}}(A_{i})=O\left(\log^{-\delta}(n_{t^{\prime}})\right)$
for every $1\leqslant i\leqslant\ell$. Recall that $\hat{A_{i}}$ is the
representation of the set $A_{i}$ in the full graph $G_{t^{\prime}}$, i.e.,

$\hat{A_{i}}\triangleq A_{i}^{\mathrm{nc}}\bigcup\left(\bigcup_{p_{j}\in
A_{i}^{\mathrm{c}}}P^{(t^{\prime})}_{j}\right),$

where
$P^{(t^{\prime})}_{j}=P_{j}\setminus(P_{j}\cap\widetilde{V}^{\mathrm{nc}}_{t^{\prime}})$,
$A_{i}^{\mathrm{nc}}\triangleq A_{i}\cap V^{\mathrm{nc}}_{t^{\prime}}$, and
$A_{i}^{\mathrm{c}}\triangleq A_{i}\cap V^{\mathrm{c}}_{t^{\prime}}$. One can
see $P^{(t^{\prime})}_{j}$ as the vertices in $P_{j}$ that have not been
pulled out into the contracted graph yet.

Notice that, when $A_{i}^{\mathrm{c}}=\emptyset$, it holds by construction
that
$\Phi_{G_{t^{\prime}}}(A_{i})=\Phi_{\widetilde{G}_{t^{\prime}}}(A_{i})\leqslant\log^{-\delta}(n_{t^{\prime}})$.
So we only look at the case where $A^{\mathrm{c}}_{i}\neq\emptyset$. Without
loss of generality, we assume that $A^{c}_{i}$ does not contain all the
contracted nodes $p_{1},\ldots,p_{k}$. If it did, then

$\Phi_{G_{t^{\prime}}}(\hat{A}_{i})=\Phi_{G_{t^{\prime}}}\left(\bigcup_{A_{j}^{c}=\emptyset}A_{j}\right)\leqslant\log^{-\delta}(n_{t^{\prime}}).$

Therefore, given that for any $1\leqslant i\leqslant\ell$ it holds that
$\mathrm{vol}_{G_{t^{\prime}}}(A_{i}^{\mathrm{nc}})\leqslant
2\cdot|E_{\mathrm{new}}|\leqslant 2\cdot\log^{\gamma}(n_{t})$, and for any
$1\leqslant j\leqslant k$ it holds that
$\mathrm{vol}_{G_{t^{\prime}}}(P_{i}^{(t^{\prime})})=\Omega(k^{6}\cdot\log^{2\gamma}(n_{t}))$,
we get that

$\Phi_{G_{t^{\prime}}}(\hat{A}_{i})=O\left(\Phi_{G_{t^{\prime}}}\left(\bigcup_{p_{j}\in
A_{i}^{\mathrm{c}}}P^{(t^{\prime})}_{j}\right)\right)=O\left(k^{-6}\cdot\log^{-\gamma}(n_{t^{\prime}})\right),$

where the last line holds because of property (C3) of Lemma B.3. This proves
the second statement. ∎

###### Proof of Lemma 4.5.

We first prove the first statement, and we will prove this by contradiction.
Assume by contradiction that
$\lambda_{\ell+1}(\mathcal{L}_{G_{t^{\prime}}})<C\cdot\frac{\log^{-\alpha}(n_{t^{\prime}})}{(\ell+1)^{6}}$
for some constant $C$. Then, by the higher-order Cheeger inequality, there
exists an optimal $(\ell+1)$-way partition $\mathcal{S}=\\{S_{1},\ldots
S_{\ell+1}$} such that for all $1\leqslant i\leqslant\ell+1$

$\Phi_{G_{t^{\prime}}}(S_{i})\leqslant\rho_{G_{t^{\prime}}}(\ell+1)\leqslant
C_{\ref{lem:Higher
Cheeger}}\cdot(\ell+1)^{3}\cdot\sqrt{\lambda_{\ell+1}(G_{t^{\prime}})}=O\left(\log^{-0.5\alpha}(n_{t^{\prime}})\right).$

By Lemma 4.4, it then holds that
$\rho_{\widetilde{G}_{t^{\prime}}}(\ell+1)=\max\left\\{O\left(\log^{-0.45\alpha}(n_{t^{\prime}})\right),O\left(k^{-6}\cdot\log^{-\gamma}(n_{t^{\prime}})\right)\right\\}$,
which contradicts the fact that

$\rho_{\widetilde{G}_{t^{\prime}}}(\ell+1)\geqslant\frac{\lambda_{\ell+1}(\mathcal{L}_{\widetilde{G}_{t^{\prime}}})}{2}=\Omega(1),$

from which the first statement of the lemma follows.

Next we prove the second statement. We prove this by analysing the spectrum of
$\mathcal{L}_{\widetilde{G}_{t^{\prime}}}$ with respect to
$\mathcal{L}_{G_{t^{\prime}}}$ through
$\mathcal{L}_{H^{\prime}_{t^{\prime}}}$. As proven in Lemma B.2,
$H^{\prime}_{t^{\prime}}$ is a cluster preserving sparsifier of
$G_{t^{\prime}}$, and therefore we know that

$\lambda_{\ell+1}(\mathcal{L}_{H^{\prime}_{t^{\prime}}})=\Omega(\lambda_{\ell+1}(\mathcal{L}_{G_{t^{\prime}}})).$
(43)

Our next analysis is inspired by the work on meta graphs of Macgregor and Sun
(Macgregor & Sun, 2022). We will analyse the spectrum of
$\mathcal{L}_{H^{\prime}_{t^{\prime}}}$ with respect to the spectrum of
$\mathcal{L}_{\widetilde{G}_{t^{\prime}}}$, and for simplicity we denote
$H^{\prime}_{t^{\prime}}\triangleq H$,
$\widetilde{G}_{t^{\prime}}\triangleq\widetilde{G}$, and
$n_{t^{\prime}}\triangleq n$. For every vertex $u_{j}\in V(\widetilde{G})$ in
the contracted graph, we associate it with a non-empty group of vertices
$A_{j}\subset V(H)$ as follows: for all
$u_{j}\in\widetilde{V}_{t^{\prime}}^{\mathrm{nc}}$, we associate $u_{j}$ with
its unique corresponding single vertex $v\in V(H)$, and for every
$u_{j}=p_{r}\in\widetilde{V}_{t^{\prime}}^{\mathrm{c}}$ for some $r$, we
associate it with its corresponding vertices in the cluster
$P^{(t^{\prime})}_{r}\subset V(H)$. Then, let $\chi_{j}\in\mathbb{R}^{n}$ be
the indicator vector for the vertices $A_{j}\subset V(H)$ corresponding to the
vertex $u_{j}\in V(\widetilde{G})$.

We define $\widetilde{n}=|V(\widetilde{G})|$, and let the eigenvalues of
$\mathcal{L}_{\widetilde{G}}$ be
$\gamma_{1}\leqslant\gamma_{2}\leqslant\ldots\leqslant\gamma_{\widetilde{n}}$
with corresponding eigenvectors
$g_{1},g_{2},\ldots,g_{\widetilde{n}}\in\mathbb{R}^{\widetilde{n}}$. We
further define vectors $\bar{g}_{1},\ldots\bar{g}_{\widetilde{n}}$ which will
represent the eigenvectors $g_{1},\ldots g_{\widetilde{n}}$ of the normalised
Laplacian $\mathcal{L}_{\widetilde{G}}$, but blown up to size
$\mathbb{R}^{n}$. Formally, we define

$\bar{g}_{i}\triangleq\sum_{j=1}^{\widetilde{n}}\frac{D_{H}^{\frac{1}{2}}\chi_{j}}{\|D_{H}^{\frac{1}{2}}\chi_{j}\|}g_{i}(j).$

We can readily check that these vectors form an orthonormal basis. First,

$\displaystyle\bar{g}_{i}\bar{g}_{i}^{\intercal}$
$\displaystyle=\sum_{j=1}^{\widetilde{n}}\sum_{u\in
A_{j}}\left(\frac{\sqrt{d_{H}(u)}}{\sqrt{\mathrm{vol}_{H}(A_{j})}}g_{i}(j)\right)^{2}$
$\displaystyle=\sum_{j=1}^{\widetilde{n}}g_{i}(j)^{2}\sum_{u\in
A_{j}}\frac{d_{H}(u)}{\mathrm{vol}_{H}(A_{j})}$
$\displaystyle=\sum_{j=1}^{\widetilde{n}}g(j)^{2}=1.$

And similarly for any $i_{1}\neq i_{2}$,

$\displaystyle\bar{g}_{i_{1}}\bar{g}_{i_{2}}^{\intercal}$
$\displaystyle=\sum_{j=1}^{\widetilde{n}}\sum_{u\in
A_{j}}\frac{d_{H}(u)}{\mathrm{vol}_{H}(A_{j})}g_{i_{1}}(j)g_{i_{2}}(j)$
$\displaystyle=\sum_{j=1}^{\widetilde{n}}g_{i_{1}}(j)g_{i_{2}}(j)=0.$

We also get the useful property that for the eigenvalues
$\lambda_{1},\ldots,\lambda_{n}$ of $\mathcal{L}_{H}$ and
$\gamma_{1},\ldots,\gamma_{\widetilde{n}}$ of the contracted Laplacian
$\mathcal{L}_{\widetilde{G}}$, it holds that $\lambda_{i}\leqslant
2\cdot\nu_{i}$. In particular,

$\displaystyle\bar{g}_{i}\mathcal{L}_{H}\bar{g}_{i}^{\intercal}$
$\displaystyle=\sum_{x=1}^{\widetilde{n}}\sum_{y=x}^{\widetilde{n}}\sum_{u\in
A_{x}}\sum_{v\in
A_{y}}w_{H}(u,v)\left(\frac{\bar{g}_{i}(u)}{\sqrt{d_{H}(u)}}-\frac{\bar{g}_{i}(v)}{\sqrt{d_{H}(v)}}\right)^{2}$
$\displaystyle=\sum_{x=1}^{\widetilde{n}}\sum_{y=x}^{\widetilde{n}}w_{H}(A_{x},A_{y})\left(\frac{g_{i}(x)}{\sqrt{\mathrm{vol}_{H}(A_{x}})}-\frac{g_{i}(y)}{\sqrt{\mathrm{vol}_{H}(A_{y}})}\right)^{2}$
$\displaystyle=2\cdot g_{i}\mathcal{L}_{\widetilde{G}}g_{i}^{\intercal}.$

Therefore we have an $i$-dimensional subspace $X_{i}$ such that

$\max_{x\in
X_{i}}\frac{x^{\intercal}\mathcal{L}_{H}x}{x^{\intercal}x}=2\cdot\gamma_{i},$

from which it follows by the Courant-Fischer theorem that
$\lambda_{i}\leqslant 2\cdot\gamma_{i}$. Combining this with (43), we get that

$\lambda_{\ell+1}(\mathcal{L}_{\widetilde{G}_{t^{\prime}}})\geqslant\frac{1}{2}\cdot\lambda_{\ell+1}(\mathcal{L}_{H^{\prime}_{t^{\prime}}})=\Omega\left(\lambda_{\ell+1}(\mathcal{L}_{G_{t^{\prime}}})\right)=\Omega(1),$

which proves the lemma. ∎