structures of clusters in directed graphs can be uncovered with complex-valued
Hermitian matrices [CLSZ20, LS20], our result shows that one can apply real-
valued Laplacians of undirected graphs, and find more general patterns of
clusters.

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

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

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

and, taking ${\mathbf{A}}_{M}$ to be the adjacency matrix, this defines a
graph ${M}=({V}_{M},{E}_{M},{w}_{M})$ which we refer to as the meta-graph of
the clusters. Informally, the meta-graph is constructed by viewing every
cluster ${S}_{i}$ as a ‘giant vertex’, and captures the structure of the
optimal clusters. Then, define the normalised adjacency matrix of ${M}$ by
${\mathbf{B}}_{M}\triangleq{\mathbf{D}}^{-\frac{1}{2}}_{M}{\mathbf{A}}_{M}{\mathbf{D}}^{-\frac{1}{2}}_{M}$,
and the normalised Laplacian matrix of ${M}$ by
${\mathbf{N}}_{M}\triangleq{\mathbf{I}}-{\mathbf{B}}_{M}$. Let the eigenvalues
of ${\mathbf{N}}_{M}$ be $\gamma_{1}\leq\ldots\leq\gamma_{k}$, and
${\bm{g}}_{i}\in\mathbb{R}^{k}$ be the eigenvector corresponding to
$\gamma_{i}$ for any $i\in[k]$.

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

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

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

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

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

  * •

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

  * •

it holds for any different $i,j\in[k]$ that
$\left\|\frac{\bar{{\bm{x}}}^{(i)}}{\left\|\bar{{\bm{x}}}^{(i)}\right\|}-\frac{\bar{{\bm{x}}}^{(j)}}{\left\|\bar{{\bm{x}}}^{(j)}\right\|}\right\|^{2}\geq\theta$.

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

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

######  Example 5.1.

Suppose the meta-graph is $C_{6}$, the cycle on $6$ vertices. Figure
5.4(5.4(a)) shows that the vertices of $C_{6}$ are well separated by the
second and third eigenvectors of ${\mathbf{N}}_{C_{6}}$.111Notice that the
first eigenvector is always the constant vector and gives no useful
information. This is why we visualise the second and third eigenvectors only.
Since the minimum distance between any pair of vertices in this embedding is
$2/3$, we say that $C_{6}$ is $\left(2/3,3\right)$-distinguishable. Figure
5.4(5.4(b)) shows that, when using ${\bm{f}}_{2},{\bm{f}}_{3}$ of
${\mathbf{N}}_{G}$ to embed the vertices of a $600$-vertex graph with a
cyclical cluster pattern, the embedded points closely match the ones from the
meta-graph. 222In Examples 5.1 and 5.2, the graphs $G$ are generated according
to a generalised stochastic block model based on the defined meta-graph. The
model is formally described in Section 5.3.

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

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

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

######  Example 5.2.

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

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

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

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

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

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

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

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

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

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

######  Lemma 5.1.

The following statements hold:

  1. 1.

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

  2. 2.

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

###### Proof.

By definition, we have that

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

which proves the first statement.

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

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

which completes the proof. ∎

The following lemma presents an important relationship between the eigenvalues
of ${\mathbf{N}}_{M}$ and those of ${\mathbf{N}}_{G}$.

######  Lemma 5.2.

It holds for any $i\in[k]$ that $\lambda_{i}\leq\gamma_{i}$.

###### Proof.

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

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

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

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

from which the lemma follows by the Courant-Fischer theorem (Theorem 2.1). ∎

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

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

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

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

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

and can prove the following structure theorem with meta-graphs.

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

The following statements hold:

  1. 1.

it holds for any $i\in[\ell]$ that
$\left\|\bar{{\bm{g}}}_{i}-\widehat{{\bm{f}}}_{i}\right\|^{2}\leq\gamma_{i}/\lambda_{\ell+1}$;

  2. 2.

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

$\sum_{i=1}^{\ell}\left\|{\bm{f}}_{i}-\widehat{{\bm{g}}}_{i}\right\|^{2}\leq\Psi(\ell).$

###### Proof.

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

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

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

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

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

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

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

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

###  5.2 Spectral Clustering with Fewer Eigenvectors

In this section, we analyse spectral clustering with fewer eigenvectors. The
algorithm is essentially the same as the standard spectral clustering
described in Section 4.2, with the only difference that every $u\in{V}_{G}$ is
embedded into a point in $\mathbb{R}^{\ell}$ by the mapping defined in (5.2).
The analysis follows from the one in Section 4.2 at a very high level.
However, since we require that $\\{F(u)\\}_{u\in{V}_{G}}$ are well separated
in $\mathbb{R}^{\ell}$ for some $\ell<k$, the proof is more involved. For any
$i\in[k]$, we define the approximate centre
${\bm{p}}^{(i)}\in\mathbb{R}^{\ell}$ of every cluster ${S}_{i}$ by

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

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

######  Lemma 5.3.

It holds that

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

###### Proof.

By definition, it holds that

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

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

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

######  Lemma 5.4.

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

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

###### Proof.

It holds by definition that

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

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

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

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

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

On the other hand, we have that

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

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

######  Lemma 5.5.

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

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

###### Proof.

By definition, it holds that

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

We upper bound the second term by

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

from which we conclude that

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

######  Lemma 5.6.

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

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

###### Proof.

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

$\xrightarrow{}$$\begin{bmatrix}{\mathbf{B}}_{1}&{\mathbf{0}}&{\mathbf{0}}\\\
{\mathbf{0}}&{\mathbf{B}}_{2}&{\mathbf{0}}\\\
{\mathbf{0}}&{\mathbf{0}}&{\mathbf{B}}_{3}\end{bmatrix}$$\xrightarrow{}$Graph
${G}$Normalised Laplacian ${\mathbf{N}}$Spectral
Embedding$\xrightarrow{}$$\begin{bmatrix}{\mathbf{B}}_{1}&{\mathbf{C}}_{12}&{\mathbf{C}}_{13}\\\
{\mathbf{C}}_{12}^{\intercal}&{\mathbf{B}}_{2}&{\mathbf{C}}_{23}\\\
{\mathbf{C}}_{13}^{\intercal}&{\mathbf{C}}_{23}^{\intercal}&{\mathbf{B}}_{3}\end{bmatrix}$$\xrightarrow{}$Graph
${G}$Normalised Laplacian ${\mathbf{N}}$Spectral
Embedding$\rightarrow$$v_{1}$$v_{3}$$v_{5}$$v_{4}$$v_{2}$$\rightarrow$$x_{1}=v_{1}$$x_{2}=v_{4}$$x_{3}=v_{5}$${\bm{p}}^{(i)}$${\bm{p}}^{(j)}$$\frac{{\bm{p}}^{(i)}}{\left\|{\bm{p}}^{(i)}\right\|}$$\frac{{\bm{p}}^{(j)}}{\left\|{\bm{p}}^{(j)}\right\|}$${\bm{a}}_{i}$${\bm{a}}_{j}$$\frac{\left\|{\bm{a}}_{i}\right\|}{\left\|{\bm{a}}_{j}\right\|}{\bm{a}}_{j}$
Figure 5.6:  Illustration of the proof of Lemma 5.6. Our goal is to give a
lower bound on the length of
$\left(\frac{{\bm{p}}^{(i)}}{\left\|{\bm{p}}^{(i)}\right\|}-\frac{{\bm{p}}^{(j)}}{\left\|{\bm{p}}^{(j)}\right\|}\right)$,
which is the blue dashed line in the figure. We instead calculate a lower
bound on the length of
$\left({\bm{a}}_{i}-\frac{\left\|{\bm{a}}_{i}\right\|}{\left\|{\bm{a}}_{j}\right\|}{\bm{a}}_{j}\right)$,
which is the red dashed line, and use the fact that by construction
$\left\|{\bm{a}}_{i}\right\|\leq 1$ and $\left\|{\bm{a}}_{j}\right\|\leq 1$.

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

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

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

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

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

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

Now, we have that

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

and have by Lemma 5.5 that

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

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

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

Finally, we have that

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

which completes the proof. ∎

######  Lemma 5.7.

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

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

###### Proof.

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

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

and

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

which implies that

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

Now, we proceed by case distinction.

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

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

and

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

since $\theta<1$.

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

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

Then, it holds that

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

which completes the proof. ∎

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

######  Lemma 5.8.

Let $A_{1},\ldots A_{k}$ be the output of spectral clustering with $\ell$
eigenvectors, and $\sigma$ and ${M}_{\sigma,i}$ be defined as in (4.5) and
(4.6). If $\Psi(\ell)\leq\theta^{3}/40^{2}$, then

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

###### Proof.

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

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

and that

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

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

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

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

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

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

######  Theorem 5.2.

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

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

###### Proof.

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

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

###  5.3 Experimental Results

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

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

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

####  5.3.1 Results on Synthetic Data

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

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

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

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

Figure 5.7:  A comparison on the output of spectral clustering with meta-
graphs $C_{10}$ and $P_{4,4}$, when different number of eigenvectors are used.
Note that classical spectral clustering uses $10$ and $16$ eigenvectors
respectively.

####  5.3.2 Results on the BSDS Dataset

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

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

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

####  5.3.3 Results on the MNIST and USPS Datasets

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

(a)

(b)

(c)

(d)

Figure 5.8:  Experimental results on the MNIST and USPS datasets. (a) and (b):
Adjusted Rand Index and accuracy of spectral clustering on the MNIST dataset;
(c) and (d): Adjusted Rand Index and accuracy of spectral clustering on the
USPS dataset. These experiments show that spectral clustering with 7
eigenvectors gives the best partition of the input into 10 clusters.

###  5.4 Future Work

This work is merely the starting point in the study of spectral clustering
with fewer than $k$ eigenvectors, and leaves many open questions. For example,
although one can enumerate the number of used eigenvectors from $1$ to $k$ and
take the best clustering result with respect to some objective function (such
as graph conductance or the normalised cut value), it would be interesting to
know whether the ‘optimal’ number of eigenvectors can be computed directly.

######  Open Question 3.

Can the ‘optimal’ number of eigenvectors for spectral clustering be computed
directly from the Laplacian spectrum?

Additionally, more empirical studies could give further insight into the
structure of the meta-graphs of real-world datasets.

######  Open Question 4.

What are the typical meta-graph structures appearing in real-world datasets?
Do they share any common properties that can be exploited to improve spectral
clustering in practice?

(a) Original Image

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

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

(d) Original Image

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

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

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

(a) Original Image

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

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

(d) Original Image

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

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

(g) Original Image

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

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

(j) Original Image

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

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

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

## Chapter 6Finding Densely Connected Clusters Locally

In this chapter we turn our attention from learning the arbitrary structure of
clusters to the problem of finding clusters with a specific known structure.
Moreover, we would like to solve the problem _locally_ so that we can learn
the structure of a graph close to some particular vertex of interest.

To begin, let us recall the definition of a _local clustering algorithm_.
Given an arbitrary vertex $u$ of graph ${G}=({V},{E})$ as input, a local graph
clustering algorithm finds some low-conductance set ${S}\subset{V}$ containing
$u$, while the algorithm runs in time proportional to the size of the target
cluster and independent of the size of the graph ${G}$. Because of the
increasing size of available datasets, which makes centralised computation too
expensive, local graph clustering has become an important learning technique
for analysing a number of large-scale graphs and has been applied to solve
many other learning and combinatorial optimisation problems [ALM13, And10,
AOGPT16, FWY20, LG20, TMIY20, WFH+17, YBLG17]. In this chapter, we study local
graph clustering for learning the structure of clusters that are defined by
their inter-connections, and develop local algorithms to achieve this
objective in both undirected and directed graphs. The design and analysis of
the algorithms in this chapter build on the _personalised Pagerank_ and
_evolving set process_ techniques for local clustering which are described in
Section 3.3.

The first result of this chapter is a local algorithm for finding densely
connected clusters in an undirected graph ${G}=({V},{E})$.

######  Main Result 4 (See Theorem 6.1 for the formal statement).

Given an undirected graph ${G}=({V},{E})$ and a seed vertex $u$, our local
algorithm finds _two_ clusters ${L},{R}$ around $u$, which are densely
connected to each other and are loosely connected to
${V}\setminus({L}\cup{R})$.

The design of the algorithm is based on a new reduction that allows us to
relate the connections between ${L},{R}$ and ${V}\setminus({L}\cup{R})$ to a
_single_ cluster in the resulting graph ${H}$, and a generalised analysis of
Pagerank-based algorithms for local graph clustering. The significance of the
designed algorithm is demonstrated by experimental results on the Interstate
Dispute Network from 1816 to 2010. By connecting two vertices (countries) with
an undirected edge weighted according to the severity of their military
disputes and using the USA as the seed vertex, the algorithm recovers two
groups of countries that tend to have conflicts with each other, and shows how
the two groups evolve over time. In particular, as shown in Figure 6.1, the
algorithm not only identifies the changing roles of Russia, Japan, and eastern
Europe in line with 20th century geopolitics, but also the reunification of
east and west Germany around 1990.

(a) 1816-1900

(b) 1900-1950

(c) 1950-1990

(d) 1990-2010

Figure 6.1:  Clusters found by LocBipartDC on the interstate dispute network,
using the USA as the seed vertex. In each case, countries in the yellow
cluster tend to enter conflicts with countries in the blue cluster and vice
versa.

The second result of this chapter is a local algorithm for finding densely
connected clusters in a _directed graph_.

######  Main Result 5 (See Theorem 6.2 for the formal statement).

Given a directed graph ${G}=({V},{E})$ and a seed vertex $u$, our local
algorithm finds two clusters ${L}$ and ${R}$, such that (i) there are many
edges _from ${L}$ to ${R}$_, and (ii) ${L}\cup{R}$ is loosely connected to
${V}\setminus({L}\cup{R})$.

The design of this algorithm is based on the following two techniques: (1) a
new reduction that allows us to relate the edge weight from ${L}$ to ${R}$, as
well as the edge connections between ${L}\cup{R}$ and
${V}\setminus({L}\cup{R})$, to a _single_ vertex set in the resulting
_undirected_ graph ${H}$; (2) a refined analysis of the ESP-based algorithm
for local graph clustering. We demonstrate that the algorithm is able to
recover local densely connected clusters in the US migration dataset, in which
two vertex sets ${L}$ and ${R}$ defined as above could represent a higher-
order migration trend. In particular, as shown in Figure 6.2, by using
different counties as starting vertices, the algorithm uncovers refined and
more localised migration patterns than the previous work on the same dataset
[CLSZ20]. This algorithm is the first local clustering algorithm that achieves
a similar goal on directed graphs.

(a) Ohio Seed

(b) New York Seed

(c) California Seed

(d) Florida Seed

Figure 6.2:  Clusters found by EvoCutDirected in the US migration network, in
which four different counties are used as starting vertices of the local
algorithm. In each case, people tend to migrate from the red counties to the
green counties.

###  6.1 Algorithm for Undirected Graphs

We first develop and analyse a local algorithm for finding two clusters in an
undirected graph with a dense cut between them. To formalise this notion, for
any undirected graph ${G}=({V},{E})$ and disjoint ${L},{R}\subset{V}$, we
recall the definition of bipartiteness given in Section 3.2:

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

Notice that a low ${\beta}({L},{R})$ value means that there is a dense cut
between ${L}$ and ${R}$, and there is a sparse cut between ${L}\cup{R}$ and
${V}\setminus({L}\cup{R})$. In particular, ${\beta}({L},{R})=0$ implies that
$({L},{R})$ forms a bipartite and connected component of ${G}$. We describe a
local algorithm for finding almost-bipartite sets ${L}$ and ${R}$ with a low
value of ${\beta}({L},{R})$.

####  6.1.1 Reduction by Double Cover

The design of most local algorithms for finding a target set ${S}\subset{V}$
of low conductance is based on analysing the behaviour of random walks
starting from vertices in ${S}$. In particular, when the conductance
${\Phi}_{G}({S})$ is low, a random walk starting from most vertices in ${S}$
leaves ${S}$ with low probability. However, for our setting, the target is a
pair of sets ${L},{R}$ with many connections between them. As such, a random
walk starting in either ${L}$ or ${R}$ is very likely to leave the starting
set. To address this, we use a novel technique based on the double cover of
${G}$ to reduce the problem of finding two sets of high conductance to the
problem of finding one of _low_ conductance. Formally, for any undirected
graph ${G}=({V}_{G},{E}_{G})$, its double cover is the bipartite graph
${H}=({V}_{H},{E}_{H})$ defined as follows: (1) every vertex $v\in{V}_{G}$ has
two corresponding vertices $v_{1},v_{2}\in{V}_{H}$; (2) for every edge
$\\{u,v\\}\in{E}_{G}$, there are edges $\\{u_{1},v_{2}\\}$ and
$\\{u_{2},v_{1}\\}$ in ${E}_{H}$. See Figure 6.3 for an illustration.

$\xrightarrow{}$$\begin{bmatrix}{\mathbf{B}}_{1}&{\mathbf{0}}&{\mathbf{0}}\\\
{\mathbf{0}}&{\mathbf{B}}_{2}&{\mathbf{0}}\\\
{\mathbf{0}}&{\mathbf{0}}&{\mathbf{B}}_{3}\end{bmatrix}$$\xrightarrow{}$Graph
${G}$Normalised Laplacian ${\mathbf{N}}$Spectral
Embedding$\xrightarrow{}$$\begin{bmatrix}{\mathbf{B}}_{1}&{\mathbf{C}}_{12}&{\mathbf{C}}_{13}\\\
{\mathbf{C}}_{12}^{\intercal}&{\mathbf{B}}_{2}&{\mathbf{C}}_{23}\\\
{\mathbf{C}}_{13}^{\intercal}&{\mathbf{C}}_{23}^{\intercal}&{\mathbf{B}}_{3}\end{bmatrix}$$\xrightarrow{}$Graph
${G}$Normalised Laplacian ${\mathbf{N}}$Spectral
Embedding$\rightarrow$$v_{1}$$v_{3}$$v_{5}$$v_{4}$$v_{2}$$\rightarrow$$x_{1}=v_{1}$$x_{2}=v_{4}$$x_{3}=v_{5}$${\bm{p}}^{(i)}$${\bm{p}}^{(j)}$$\frac{{\bm{p}}^{(i)}}{\left\|{\bm{p}}^{(i)}\right\|}$$\frac{{\bm{p}}^{(j)}}{\left\|{\bm{p}}^{(j)}\right\|}$${\bm{a}}_{i}$${\bm{a}}_{j}$$\frac{\left\|{\bm{a}}_{i}\right\|}{\left\|{\bm{a}}_{j}\right\|}{\bm{a}}_{j}$$a_{1}$$a_{2}$$a$$b$$c$$d$$\Longrightarrow$$b_{1}$$b_{2}$$c_{1}$$c_{2}$$d_{1}$$d_{2}$

Figure 6.3: An example of the construction of the double cover

Now we show a tight connection between the value of ${\beta}({L},{R})$ for any
disjoint sets ${L},{R}\subset{V}_{G}$ and the conductance of a _single_ set in
the double cover of ${G}$. To this end, for any ${S}\subset{V}_{G}$, we define
${S}_{1}\subset{V}_{H}$ and ${S}_{2}\subset{V}_{H}$ by
${S}_{1}\triangleq\\{v_{1}~{}|~{}v\in{S}\\}$ and
${S}_{2}\triangleq\\{v_{2}~{}|~{}v\in{S}\\}$. We formalise the connection in
the following lemma.

######  Lemma 6.1.

Let ${G}$ be an undirected graph, ${S}\subset{V}$ with partitioning
$({L},{R})$, and ${H}$ be the double cover of ${G}$. Then, it holds that
${\Phi}_{H}({L}_{1}\cup{R}_{2})={\beta}_{G}({L},{R})$.

###### Proof.

Let ${S}^{\prime}={L}_{1}\cup{R}_{2}$, and by definition we have that
$\mathrm{vol}_{G}({S})=\mathrm{vol}_{H}({S}^{\prime})$. On the other hand, it
holds that

$\mathrm{vol}_{H}({S}^{\prime})={w}_{H}({S}^{\prime},{V}\setminus{S}^{\prime})+2{w}_{H}({S}^{\prime},{S}^{\prime})={w}_{H}({S}^{\prime},{V}\setminus{S}^{\prime})+2{w}_{H}({L}_{1},{R}_{2}).$

This implies that

${\Phi}_{H}({S}^{\prime})=\frac{{w}_{H}({S}^{\prime},{V}\setminus{S}^{\prime})}{\mathrm{vol}_{H}({S}^{\prime})}=\frac{\mathrm{vol}_{G}({S})-2{w}_{H}({L}_{1},{R}_{2})}{\mathrm{vol}_{G}({S})}=1-\frac{2{w}_{G}({L},{R})}{\mathrm{vol}_{G}({S})}={\beta}_{G}({L},{R}),$

which proves the statement. ∎

Next we look at the other direction of this correspondence. Specifically,
given any ${S}\subset{V}_{H}$ in the double cover of a graph ${G}$, we would
like to find two disjoint sets ${L}\subset{V}_{G}$ and ${R}\subset{V}_{G}$
such that ${\beta}_{G}({L},{R})={\Phi}_{H}({S})$. However, such a connection
does not hold in general. To overcome this, we restrict our attention to those
subsets of ${V}_{H}$ which can be unambiguously interpreted as two disjoint
sets in ${V}_{G}$.

######  Definition 6.1.

(Simple set) We call ${S}\subset{V}_{H}$ simple if
$\left\lvert\\{v_{1},v_{2}\\}\cap{S}\right\rvert\leq 1$ holds for all
$v\in{V}_{G}$.

Given this definition, the following corollary follows directly from Lemma
6.1.

######  Corollary 6.1.

For any simple set ${S}\subset{V}_{H}$, let ${L}=\\{u:u_{1}\in{S}\\}$ and
${R}=\\{u:u_{2}\in{S}\\}$. Then, ${\beta}_{G}({L},{R})={\Phi}_{H}({S}).$

####  6.1.2 Design of the Algorithm

So far we have shown that the problem of finding densely connected sets
${L},{R}\subset{V}_{G}$ can be reduced to finding ${S}\subset{V}_{H}$ of low
conductance in the double cover ${H}$, and this reduction raises the natural
question of whether existing local algorithms can be directly employed to find
${L}$ and ${R}$ in ${G}$. However, this is not the case: even though a set
${S}\subset{V}_{H}$ returned by most local algorithms is guaranteed to have
low conductance, vertices of ${G}$ could be included in ${S}$ twice, and as
such ${S}$ doesn’t necessarily give us disjoint sets ${L},{R}\subset{V}_{G}$
with low value of ${\beta}({L},{R})$. See Figure 6.4 for an illustration.

$\xrightarrow{}$$\begin{bmatrix}{\mathbf{B}}_{1}&{\mathbf{0}}&{\mathbf{0}}\\\
{\mathbf{0}}&{\mathbf{B}}_{2}&{\mathbf{0}}\\\
{\mathbf{0}}&{\mathbf{0}}&{\mathbf{B}}_{3}\end{bmatrix}$$\xrightarrow{}$Graph
${G}$Normalised Laplacian ${\mathbf{N}}$Spectral
Embedding$\xrightarrow{}$$\begin{bmatrix}{\mathbf{B}}_{1}&{\mathbf{C}}_{12}&{\mathbf{C}}_{13}\\\
{\mathbf{C}}_{12}^{\intercal}&{\mathbf{B}}_{2}&{\mathbf{C}}_{23}\\\
{\mathbf{C}}_{13}^{\intercal}&{\mathbf{C}}_{23}^{\intercal}&{\mathbf{B}}_{3}\end{bmatrix}$$\xrightarrow{}$Graph
${G}$Normalised Laplacian ${\mathbf{N}}$Spectral
Embedding$\rightarrow$$v_{1}$$v_{3}$$v_{5}$$v_{4}$$v_{2}$$\rightarrow$$x_{1}=v_{1}$$x_{2}=v_{4}$$x_{3}=v_{5}$${\bm{p}}^{(i)}$${\bm{p}}^{(j)}$$\frac{{\bm{p}}^{(i)}}{\left\|{\bm{p}}^{(i)}\right\|}$$\frac{{\bm{p}}^{(j)}}{\left\|{\bm{p}}^{(j)}\right\|}$${\bm{a}}_{i}$${\bm{a}}_{j}$$\frac{\left\|{\bm{a}}_{i}\right\|}{\left\|{\bm{a}}_{j}\right\|}{\bm{a}}_{j}$$a_{1}$$a_{2}$$a$$b$$c$$d$$\Longrightarrow$$b_{1}$$b_{2}$$c_{1}$$c_{2}$$d_{1}$$d_{2}$$\cdots$$a_{1}$$S$$b_{1}$$c_{1}$$d_{1}$$e_{1}$$f_{1}$$\cdots$$\cdots$$a_{2}$$b_{2}$$c_{2}$$d_{2}$$e_{2}$$f_{2}$$\cdots$
Figure 6.4: The indicated vertex set ${S}\subset{V}_{H}$ has low conductance.
However, since ${S}$ contains many pairs of vertices which correspond to the
same vertex in ${G}$, ${S}$ gives us little information for finding disjoint
${L},{R}\subset{V}_{G}$ with a low ${\beta}({L},{R})$ value.

##### The Simplify Operator

Taking the example shown in Figure 6.4 into account, our objective is to
design a local algorithm for finding some set ${S}\subset{V}_{H}$ of low
conductance which is also simple. To ensure this, we introduce the simplify
operator, and analyse its properties.

######  Definition 6.2 (Simplify operator).

Let ${H}$ be the double cover of ${G}$, where the two corresponding vertices
of any $u\in{V}_{G}$ are defined as $u_{1},u_{2}\in{V}_{H}$. Then, for any
${\bm{p}}\in\mathbb{R}^{2n}_{\geq 0}$, the simplify operator is a function
$\sigma:\mathbb{R}^{2n}_{\geq 0}\rightarrow\mathbb{R}^{2n}_{\geq 0}$ defined
by

$\displaystyle(\sigma\circ{\bm{p}})(u_{1})$
$\displaystyle\triangleq\max(0,{\bm{p}}(u_{1})-{\bm{p}}(u_{2})),$
$\displaystyle(\sigma\circ{\bm{p}})(u_{2})$
$\displaystyle\triangleq\max(0,{\bm{p}}(u_{2})-{\bm{p}}(u_{1}))$

for every $u\in{V}_{G}$.

Notice that, for any vector ${\bm{p}}$ and any $u\in{V}_{G}$, at most one of
$u_{1}$ and $u_{2}$ is in the support of $\sigma\circ{\bm{p}}$; hence, the
support of $\sigma\circ{\bm{p}}$ is always simple. To explain the meaning of
$\sigma$, for a vector ${\bm{p}}$ one could view ${\bm{p}}(u_{1})$ as our
‘confidence’ that $u\in{L}$, and ${\bm{p}}(u_{2})$ as our ‘confidence’ that
$u\in{R}$. Hence, when ${\bm{p}}(u_{1})\approx{\bm{p}}(u_{2})$, both
$(\sigma\circ{\bm{p}})(u_{1})$ and $(\sigma\circ{\bm{p}})(u_{2})$ are low
which captures the fact that we would not prefer to include $u$ in either
${L}$ or ${R}$. On the other hand, when ${\bm{p}}(u_{1})\gg{\bm{p}}(u_{2})$,
we have $(\sigma\circ{\bm{p}})(u_{1})\approx{\bm{p}}(u_{1})$, which captures
our confidence that $u$ should belong to ${L}$. The following lemma summaries
some key properties of $\sigma$.

######  Lemma 6.2.

The following holds for the $\sigma$-operator:

  * •

$\sigma\circ(c\cdot{\bm{p}})=c\cdot(\sigma\circ{\bm{p}})$ for
${\bm{p}}\in\mathbb{R}_{\geq 0}^{2n}$ and any $c\in\mathbb{R}_{\geq 0}$;

  * •

$\sigma\circ({\bm{a}}+{\bm{b}})\preceq\sigma\circ{\bm{a}}+\sigma\circ{\bm{b}}$
for ${\bm{a}},{\bm{b}}\in\mathbb{R}_{\geq 0}^{2n}$;

  * •

$\sigma\circ({\mathbf{W}}{\bm{p}})\preceq{\mathbf{W}}(\sigma\circ{\bm{p}})$
for ${\bm{p}}\in\mathbb{R}_{\geq 0}^{2n}$.

###### Proof.

For any $u_{1}\in{V}_{H}$, we have by definition that

$\displaystyle\sigma\circ(c\cdot{\bm{p}})(u_{1})$
$\displaystyle=\max(0,c\cdot{\bm{p}}(u_{1})-c\cdot{\bm{p}}(u_{2}))$
$\displaystyle=c\cdot\max(0,{\bm{p}}(u_{1})-{\bm{p}}(u_{2}))$
$\displaystyle=c\cdot\sigma\circ{\bm{p}}(u_{1}),$

and similarly we have
$\sigma\circ(c\cdot{\bm{p}})(u_{2})=c\cdot\sigma\circ{\bm{p}}(u_{2})$.
Therefore, the first statement holds.

Now we prove the second statement. Let $u_{1},u_{2}\in{V}_{H}$ be the vertices
that correspond to $u\in{V}_{G}$. We have by definition that

$\displaystyle\sigma\circ({\bm{a}}+{\bm{b}})(u_{1})$
$\displaystyle=\max(0,{\bm{a}}(u_{1})+{\bm{b}}(u_{1})-{\bm{a}}(u_{2})-{\bm{b}}(u_{2}))$
$\displaystyle=\max(0,{\bm{a}}(u_{1})-{\bm{a}}(u_{2})+{\bm{b}}(u_{1})-{\bm{b}}(u_{2}))$
$\displaystyle\leq\max(0,{\bm{a}}(u_{1})-{\bm{a}}(u_{2}))+\max(0,{\bm{b}}(u_{1})-{\bm{b}}(u_{2}))$
$\displaystyle=\sigma\circ{\bm{a}}(u_{1})+\sigma\circ{\bm{b}}(u_{1}),$

where the last inequality holds by the fact that
$\max(0,x+y)\leq\max(0,x)+\max(0,y)$ for any $x,y\in\mathbb{R}$. For the same
reason, we have that

$\sigma\circ({\bm{a}}+{\bm{b}})(u_{2})\leq\sigma\circ{\bm{a}}(u_{2})+\sigma\circ{\bm{b}}(u_{2}).$

Combining these proves the second statement.

Finally, we prove the third statement. Recall that the lazy random walk matrix
for a graph is defined to be
${\mathbf{W}}=\frac{1}{2}({\mathbf{I}}+{\mathbf{A}}{\mathbf{D}}^{-1})$. By
this definition, we have that

$({\mathbf{W}}{\bm{p}})(u_{1})=\frac{1}{2}{\bm{p}}(u_{1})+\frac{1}{2}\sum_{v\in
N_{G}(u)}\frac{{\bm{p}}(v_{2})}{{d}_{H}(v_{2})},$

and

$({\mathbf{W}}{\bm{p}})(u_{2})=\frac{1}{2}{\bm{p}}(u_{2})+\frac{1}{2}\sum_{v\in
N_{G}(u)}\frac{{\bm{p}}(v_{1})}{{d}_{H}(v_{1})}.$

Without loss of generality, we assume that
$({\mathbf{W}}{\bm{p}})(u_{1})\geq({\mathbf{W}}{\bm{p}})(u_{2})$. This implies
that
$(\sigma\circ({\mathbf{W}}{\bm{p}}))(u_{2})=0\leq({\mathbf{W}}(\sigma\circ{\bm{p}}))(u_{2})$,
hence it suffices to prove that
$(\sigma\circ({\mathbf{W}}{\bm{p}}))(u_{1})\leq({\mathbf{W}}(\sigma\circ{\bm{p}}))(u_{1})$.
By definition, we have that

$\displaystyle(\sigma\circ({\mathbf{W}}{\bm{p}}))(u_{1})$
$\displaystyle=\max(0,({\mathbf{W}}{\bm{p}})(u_{1})-({\mathbf{W}}{\bm{p}})(u_{2}))$
$\displaystyle=({\mathbf{W}}{\bm{p}})(u_{1})-({\mathbf{W}}{\bm{p}})(u_{2})$
$\displaystyle=\frac{1}{2}\left({\bm{p}}(u_{1})-{\bm{p}}(u_{2})\right)+\frac{1}{2}\sum_{v\in
N_{G}(u)}\left(\frac{{\bm{p}}(v_{2})}{{d}_{H}(v_{2})}-\frac{{\bm{p}}(v_{1})}{{d}_{H}(v_{1})}\right)$
$\displaystyle=\frac{1}{2}\left({\bm{p}}(u_{1})-{\bm{p}}(u_{2})\right)+\frac{1}{2}\sum_{v\in
N_{G}(u)}\frac{{\bm{p}}(v_{2})-{\bm{p}}(v_{1})}{{d}_{G}(v)},$ (6.1)

where the last equality follows by the fact that
${d}_{H}(v_{1})={d}_{H}(v_{2})={d}_{G}(v)$ for any $v\in{V}_{G}$. To analyse
(6.1), notice that
${\bm{p}}(v_{1})-{\bm{p}}(v_{2})=(\sigma\circ{\bm{p}})(v_{1})-(\sigma\circ{\bm{p}})(v_{2})$
for any $v\in{V}_{G}$ for the following reasons:

  * •

When ${\bm{p}}(v_{1})\geq{\bm{p}}(v_{2})$, we have that
$(\sigma\circ{\bm{p}})(v_{1})-(\sigma\circ{\bm{p}})(v_{2})=\left({\bm{p}}(v_{1})-{\bm{p}}(v_{2})\right)-0={\bm{p}}(v_{1})-{\bm{p}}(v_{2})$;

  * •

Otherwise, we have ${\bm{p}}(v_{1})<{\bm{p}}(v_{2})$ and
$(\sigma\circ{\bm{p}})(v_{1})-(\sigma\circ{\bm{p}})(v_{2})=0-({\bm{p}}(v_{2})-{\bm{p}}(v_{1}))={\bm{p}}(v_{1})-{\bm{p}}(v_{2})$.

Therefore, we can rewrite (6.1) as

$\displaystyle(\sigma\circ({\mathbf{W}}{\bm{p}}))(u_{1})$
$\displaystyle=\frac{1}{2}((\sigma\circ{\bm{p}})(u_{1})-(\sigma\circ{\bm{p}})(u_{2}))+\frac{1}{2}\sum_{v\in
N(u)}\frac{(\sigma\circ{\bm{p}})(v_{2})-(\sigma\circ{\bm{p}})(v_{1})}{{d}_{G}(v)}$
$\displaystyle\leq\frac{1}{2}\cdot(\sigma\circ{\bm{p}})(u_{1})+\frac{1}{2}\sum_{v\in
N(u)}\frac{(\sigma\circ{\bm{p}})(v_{2})}{{d}_{G}(v)}$
$\displaystyle=({\mathbf{W}}(\sigma\circ{\bm{p}}))(u_{1}),$

where the inequality holds by the fact that $(\sigma\circ{\bm{p}})(u_{1})\geq
0$ and $(\sigma\circ{\bm{p}})(u_{2})\geq 0$ for any $u\in{V}_{G}$. Since the
analysis above holds for any $v\in{V}_{G}$, we have that
$\sigma\circ({\mathbf{W}}{\bm{p}})\preceq{\mathbf{W}}(\sigma\circ{\bm{p}})$,
which finishes the proof of the lemma. ∎

While our analysis is based on all the three properties in Lemma 6.2, the
third is of particular importance: it implies that, if ${\bm{p}}$ is the
probability distribution of a random walk in ${H}$, applying $\sigma$ before
taking a one-step random walk would never result in lower probability mass
than applying $\sigma$ after taking a one-step random walk. This means that no
probability mass would be lost when the $\sigma$-operator is applied between
every step of a random walk, in comparison with applying $\sigma$ at the end
of an entire random walk process.

##### Description of the Algorithm

Our proposed algorithm is conceptually simple: every vertex $u$ of the input
graph ${G}$ maintains two copies $u_{1},u_{2}$ of itself, and these two
‘virtual’ vertices are used to simulate $u$’s corresponding vertices in the
double cover ${H}$ of ${G}$. Then, as the neighbours of $u_{1}$ and $u_{2}$ in
${H}$ are entirely determined by $u$’s neighbours in ${G}$ and can be
constructed locally, a random walk process in ${H}$ is simulated in ${G}$.
This allows us to apply a local algorithm similar to the one by Anderson et
al. [ACL06] on this ‘virtual’ graph ${H}$. Finally, since all the required
information about $u_{1},u_{2}\in{V}_{H}$ is maintained by $u\in{V}_{G}$, the
$\sigma$-operator can be applied locally.

The formal description of the algorithm is given in Algorithm 1, which invokes
Algorithm 2 as the key component to compute the approximate Pagerank
$\mathrm{apr}_{H}(\alpha,{\bm{\chi}}_{u_{1}},{\bm{r}})$. Specifically,
Algorithm 2 maintains, for every vertex $u\in{V}_{G}$, tuples
$({\bm{p}}(u_{1}),{\bm{p}}(u_{2}))$ and $({\bm{r}}(u_{1}),{\bm{r}}(u_{2}))$ to
keep track of the values of ${\bm{p}}$ and ${\bm{r}}$ in ${G}$’s double cover.
For a given vertex $u$, the entries in these tuples are expressed by
${\bm{p}}_{1}(u),{\bm{p}}_{2}(u),{\bm{r}}_{1}(u),$ and ${\bm{r}}_{2}(u)$
respectively. Every DCPush operation (Algorithm 3) preserves the invariant
${\bm{p}}+\mathrm{ppr}_{H}(\alpha,{\bm{r}})=\mathrm{ppr}_{H}(\alpha,{\bm{\chi}}_{v_{1}}),$
which ensures that the final output of Algorithm 2 is an approximate Pagerank
vector. It is worth noting that, although the presentation of the
ApproximatePagerankDC procedure is similar to the one in Andersen et al.
[ACL06], in the DCPush procedure the update of the residual vector ${\bm{r}}$
is slightly more involved: specifically, for every vertex $u\in{V}_{G}$, both
${\bm{r}}_{1}(u)$ and ${\bm{r}}_{2}(u)$ are needed in order to update
${\bm{r}}_{1}(u)$ (or ${\bm{r}}_{2}(u)$). That is one of the reasons that the
performance of the algorithm in Andersen et al. [ACL06] cannot be directly
applied for this algorithm, and a more technical analysis, some of which is
parallel to theirs, is needed in order to analyse the correctness and
performance of the algorithm.

Input : A graph ${G}$, starting vertex $u$, target volume $\gamma$, and target
bipartiteness $\beta$

Output : Two disjoint sets ${L}$ and ${R}$

1 Set $\alpha=\frac{\beta^{2}}{378}$, and $\epsilon=\frac{1}{20\gamma}$

2 Compute
${\bm{p}}^{\prime}=\textsc{ApproximatePagerankDC}(u,\alpha,\epsilon)$

3 Compute ${\bm{p}}=\sigma\circ{\bm{p}}^{\prime}$

4 for  _$j\in[1,\left\lvert\mathrm{supp}(p)\right\rvert]$_ do

5 if  _${\Phi}({S}_{j}^{{\bm{p}}})\leq\beta$_ then

6 Set ${L}=\\{u:u_{1}\in{S}_{j}^{{\bm{p}}}\\}$, and
${R}=\\{u:u_{2}\in{S}_{j}^{{\bm{p}}}\\}$

7 return $({L},{R})$

8 end if

9

10 end for

Algorithm 1 LocBipartDC$({G},u,\gamma,\beta)$

Input : Starting vertex $v$, parameters $\alpha$ and $\epsilon$

Output : Approximate Pagerank vector
$\mathrm{apr}_{H}(\alpha,{\bm{\chi}}_{v_{1}},{\bm{r}})$

1 Set ${\bm{p}}_{1}={\bm{p}}_{2}={\bm{r}}_{2}={\bm{0}}$; set
${\bm{r}}_{1}={\bm{\chi}}_{v}$

2 while
_$\max_{(u,i)\in{V}\times\\{1,2\\}}\frac{{\bm{r}}_{i}(u)}{{d}(u)}\geq\epsilon$_
do

3 Choose any $u$ and $i\in\\{1,2\\}$ such that
$\frac{{\bm{r}}_{i}(u)}{{d}(u)}\geq\epsilon$

4
$({\bm{p}}_{1},{\bm{p}}_{2},{\bm{r}}_{1},{\bm{r}}_{2})=\textsc{DCPush}(\alpha,(u,i),{\bm{p}}_{1},{\bm{p}}_{2},{\bm{r}}_{1},{\bm{r}}_{2})$

5 end while

return ${\bm{p}}=\left[{\bm{p}}_{1},{\bm{p}}_{2}\right]$

Algorithm 2 ApproximatePagerankDC$(v,\alpha,\epsilon)$

Input : $\alpha,(u,i),{\bm{p}}_{1},{\bm{p}}_{2},{\bm{r}}_{1},{\bm{r}}_{2}$

Output :
$({\bm{p}}^{\prime}_{1},{\bm{p}}^{\prime}_{2},{\bm{r}}^{\prime}_{1},{\bm{r}}^{\prime}_{2})$

1 Set
$({\bm{p}}_{1}^{\prime},{\bm{p}}_{2}^{\prime},{\bm{r}}_{1}^{\prime},{\bm{r}}_{2}^{\prime})=({\bm{p}}_{1},{\bm{p}}_{2},{\bm{r}}_{1},{\bm{r}}_{2})$

2 Set ${\bm{p}}^{\prime}_{i}(u)={\bm{p}}_{i}(u)+\alpha{\bm{r}}_{i}(u)$

3 Set ${\bm{r}}^{\prime}_{i}(u)=(1-\alpha)\frac{{\bm{r}}_{i}(u)}{2}$

4 for  _$v\in N_{G}(u)$_ do

5 Set
${\bm{r}}^{\prime}_{3-i}(v)={\bm{r}}_{3-i}(v)+(1-\alpha)\frac{{\bm{r}}_{i}(u)}{2{d}(u)}$

6 end for

return
$({\bm{p}}^{\prime}_{1},{\bm{p}}^{\prime}_{2},{\bm{r}}^{\prime}_{1},{\bm{r}}^{\prime}_{2})$

Algorithm 3
DCPush$(\alpha,(u,i),{\bm{p}}_{1},{\bm{p}}_{2},{\bm{r}}_{1},{\bm{r}}_{2})$

####  6.1.3 Analysis of ApproximatePagerankDC

We begin by considering the ApproximatePagerankDC algorithm, and show that it
computes an approximate Pagerank vector on the double cover of the input
graph. The following lemma shows that DCPush maintains that throughout the
algorithm
$\left[{\bm{p}}_{1}^{\intercal},{\bm{p}}_{2}^{\intercal}\right]^{\intercal}$
is an approximate Pagerank vector on the double cover with residual
$\left[{\bm{r}}_{1}^{\intercal},{\bm{r}}_{2}^{\intercal}\right]^{\intercal}$,
where $\left[{\bm{a}}^{\intercal},{\bm{b}}^{\intercal}\right]^{\intercal}$ for
${\bm{a}}\in\mathbb{R}^{n_{1}}$ and ${\bm{b}}\in\mathbb{R}^{n_{2}}$ is the
vector in $\mathbb{R}^{n_{1}+n_{2}}$ obtained by concatenating ${\bm{a}}$ and
${\bm{b}}$.

######  Lemma 6.3.

Let ${\bm{p}}^{\prime}_{1},{\bm{p}}^{\prime}_{2},{\bm{r}}^{\prime}_{1}$ and
${\bm{r}}^{\prime}_{2}$ be the result of
$\textsc{DCPush}((u,i),{\bm{p}}_{1},{\bm{p}}_{2},{\bm{r}}_{1},{\bm{r}}_{2})$.
Let
${\bm{p}}=\left[{\bm{p}}_{1}^{\intercal},{\bm{p}}_{2}^{\intercal}\right]^{\intercal}$,
${\bm{r}}=\left[{\bm{r}}_{1}^{\intercal},{\bm{r}}_{2}^{\intercal}\right]^{\intercal}$,
${\bm{p}}^{\prime}=\left[({\bm{p}}^{\prime}_{1})^{\intercal},({\bm{p}}^{\prime}_{2})^{\intercal}\right]^{\intercal}$
and
${\bm{r}}^{\prime}=\left[({\bm{r}}^{\prime}_{1})^{\intercal},({\bm{r}}^{\prime}_{2})^{\intercal}\right]^{\intercal}$.
Then, we have that

${\bm{p}}^{\prime}+\mathrm{ppr}_{H}(\alpha,{\bm{r}}^{\prime})={\bm{p}}+\mathrm{ppr}_{H}(\alpha,{\bm{r}}).$

###### Proof.

After the push operation, we have

$\displaystyle{\bm{p}}^{\prime}$
$\displaystyle={\bm{p}}+\alpha{\bm{r}}(u_{i}){\bm{\chi}}_{u_{i}}$
$\displaystyle{\bm{r}}^{\prime}$
$\displaystyle={\bm{r}}-{\bm{r}}(u_{i}){\bm{\chi}}_{u_{i}}+(1-\alpha){\bm{r}}(u_{i}){\mathbf{W}}_{H}{\bm{\chi}}_{u_{i}}$

where ${\mathbf{W}}_{H}$ is the lazy random walk matrix on the double cover of
the input graph. Then, we have

$\displaystyle{\bm{p}}+\mathrm{ppr}_{H}(\alpha,{\bm{r}})$
$\displaystyle={\bm{p}}+\mathrm{ppr}_{H}(\alpha,{\bm{r}}-{\bm{r}}(u_{i}){\bm{\chi}}_{u_{i}})+\mathrm{ppr}_{H}(\alpha,{\bm{r}}(u_{i}){\bm{\chi}}_{u_{i}})$
$\displaystyle={\bm{p}}+\mathrm{ppr}_{H}(\alpha,{\bm{r}}-{\bm{r}}(u_{i}){\bm{\chi}}_{u_{i}})+\left[\alpha{\bm{r}}(u){\bm{\chi}}_{u_{i}}+(1-\alpha)\mathrm{ppr}_{H}(\alpha,{\bm{r}}(u){\mathbf{W}}_{H}{\bm{\chi}}_{u_{i}})\right]$
$\displaystyle=\left[{\bm{p}}+\alpha{\bm{r}}(u_{i}){\bm{\chi}}_{u_{i}}\right]+\mathrm{ppr}_{H}(\alpha,\left[{\bm{r}}-{\bm{r}}(u_{i}){\bm{\chi}}_{u_{i}}+(1-\alpha){\bm{r}}(u_{i}){\mathbf{W}}_{H}{\bm{\chi}}_{u_{i}}\right])$
$\displaystyle={\bm{p}}^{\prime}+\mathrm{ppr}_{H}(\alpha,{\bm{r}}^{\prime}).$

Here, we use the fact that $\mathrm{ppr}(\alpha,\cdot)$ is linear and

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

which follows from the fact that
$\mathrm{ppr}(\alpha,{\bm{s}})=\alpha\sum_{t=0}^{\infty}(1-\alpha)^{t}{\mathbf{W}}_{H}^{t}{\bm{s}}$.
∎

Now we can show the correctness and performance guarantee of the
ApproximatePagerankDC algorithm.

######  Lemma 6.4.

For a graph ${G}$ and any $v\in{V}_{G}$,
$\textsc{ApproximatePagerankDC}(v,\alpha,\epsilon)$ has running time
$O\\!\left(\frac{1}{\epsilon\alpha}\right)$ and computes
${\bm{p}}=\mathrm{apr}_{H}(\alpha,{\bm{\chi}}_{v_{1}},{\bm{r}})$ such that
$\max_{u\in{V}_{H}}\frac{{\bm{r}}(u)}{{d}(u)}<\epsilon$ and
$\mathrm{vol}(\mathrm{supp}({\bm{p}})))\leq\frac{1}{\epsilon\alpha}$, where
${H}$ is the double cover of ${G}$.

###### Proof.

By Lemma 6.3, we have that
${\bm{p}}=\mathrm{apr}_{H}(\alpha,{\bm{\chi}}_{v_{1}},{\bm{r}})$ throughout
the algorithm and so this clearly holds for the output vector. By the stopping
condition of the algorithm, it holds that
$\max_{u\in{V}_{H}}\frac{{\bm{r}}(u)}{{d}(u)}<\epsilon$.

Let $T$ be the total number of push operations performed by
ApproximatePagerankDC, and $d_{j}$ be the degree of the vertex $u_{i}$ used in
the $j$-th push. The amount of probability mass on $u_{i}$ at time $j$ is at
least $\epsilon d_{j}$ and so the amount of probability mass that moves from
${\bm{r}}_{i}$ to ${\bm{p}}_{i}$ at step $j$ is at least $\alpha\epsilon
d_{i}$. Since
$\left\|{\bm{r}}_{1}\right\|_{1}+\left\|{\bm{r}}_{2}\right\|_{1}=1$ at the
beginning of the algorithm, we have that
$\alpha\epsilon\sum_{j=1}^{T}d_{j}\leq 1,$ which implies that

$\displaystyle\sum_{j=1}^{T}d_{j}$
$\displaystyle\leq\frac{1}{\alpha\epsilon}.$ (6.2)

Now, note that for every vertex in $\mathrm{supp}({\bm{p}})$, there must be at
least one push operation on that vertex. So,

$\mathrm{vol}(\mathrm{supp}({\bm{p}}))=\sum_{v\in\mathrm{supp}({\bm{p}})}{d}(v)\leq\sum_{j=1}^{T}d_{j}\leq\frac{1}{\epsilon\alpha}.$

Finally, to bound the running time, we can implement the algorithm by
maintaining a queue of vertices satisfying
$\frac{{\bm{r}}(u)}{{d}(u)}\geq\epsilon$, and repeat the push operation on the
first item in the queue at every iteration, updating the queue as appropriate.
The push operation and queue updates can be performed in time proportional to
${d}(u)$ and so the running time follows from (6.2). ∎

####  6.1.4 Analysis of LocBipartDC

We now come to the analysis of the main algorithm and the core technical
result of this chapter. To prove the correctness of the LocBipartDC algorithm,
we show two complementary facts which we state informally here:

  1. 1.

If there is a simple set ${S}\subset{V}_{H}$ with low conductance, then for
most $u_{1}\in{S}$ the simplified approximate Pagerank vector
${\bm{p}}=\sigma\circ\mathrm{apr}(\alpha,{\bm{\chi}}_{u_{1}},{\bm{r}})$ would
have a lot of probability mass on a small set of vertices.

  2. 2.

If ${\bm{p}}=\sigma\circ\mathrm{apr}(\alpha,{\bm{\chi}}_{u_{1}},{\bm{r}})$
contains a lot of probability mass on some small set of vertices, then there
is a sweep set of ${\bm{p}}$ with low conductance.

As we see in Section 6.1.1, there is a direct correspondence between almost-
bipartite sets in ${G}$, and low-conductance and simple sets in ${H}$. This
means that the two facts above are exactly what we need to prove that
Algorithm 1 can find densely connected sets in ${G}$.

We first show in Lemma 6.5 how the $\sigma$-operator affects some standard
mixing properties of Pagerank vectors in order to establish the first fact
promised above. This lemma relies on the fact that ${S}\subset{V}_{G}$
corresponds to a _simple_ set in ${V}_{H}$. This allows us to apply the
$\sigma$-operator to the approximate Pagerank vector
$\mathrm{apr}_{H}(\alpha,{\bm{\chi}}_{u_{1}},{\bm{r}})$ while preserving a
large probability mass on the target set. We make use of the following fact
proved by Andersen et al. [ACL06] which shows that the approximate Pagerank
vector has a large probability mass on a set of vertices if they have low
conductance.

######  Proposition 6.1 ([ACL06], Theorem 4).

For any vertex set ${S}$ and any constant $\alpha\in[0,1]$, there is a subset
${S}_{\alpha}\subseteq{S}$ with
$\mathrm{vol}({S}_{\alpha})\geq\mathrm{vol}({S})/2$ such that for any vertex
$v\in{S}_{\alpha}$, the approximate Pagerank vector
$\mathrm{apr}(\alpha,{\bm{\chi}}_{v},r)$ satisfies

$\mathrm{apr}(\alpha,{\bm{\chi}}_{v},{\bm{r}})({S})\geq
1-\frac{{\Phi}({S})}{\alpha}-\mathrm{vol}({S})\max_{u\in{V}}\frac{{\bm{r}}(u)}{{d}(u)}.$

The following lemma generalises this result to show that applying the
$\sigma$-operator to the approximate Pagerank vector maintains this large
probability mass up to a constant factor.

######  Lemma 6.5.

For any set ${S}\subset{V}_{{G}}$ with partitioning $({L},{R})$ and any
constant $\alpha\in[0,1]$, there is a subset ${S}_{\alpha}\subseteq{S}$ with
$\mathrm{vol}({S}_{\alpha})\geq\mathrm{vol}({S})/2$ such that, for any vertex
$v\in{S}_{\alpha}$, the simplified approximate Pagerank on the double cover
${\bm{p}}=\sigma\circ\left(\mathrm{apr}_{H}(\alpha,{\bm{\chi}}_{v_{1}},{\bm{r}})\right)$
satisfies

${\bm{p}}({L}_{1}\cup{R}_{2})\geq
1-\frac{2{\beta}({L},{R})}{\alpha}-2\mathrm{vol}({S})\max_{u\in{V}}\frac{{\bm{r}}(u)}{{d}(u)}.$

###### Proof.

By Lemma 6.1 and Proposition 6.1, there is a set ${S}_{\alpha}\subseteq{E}$
with $\mathrm{vol}({S}_{\alpha})\geq\mathrm{vol}({S})/2$ such that it holds
for $v\in{S}_{\alpha}$ that

$\mathrm{apr}_{H}(\alpha,{\bm{\chi}}_{v},{\bm{r}})({L}_{1}\cup{R}_{2})\geq
1-\frac{{\beta}({L},{R})}{\alpha}-\mathrm{vol}({S})\max_{u\in{V}}\frac{{\bm{r}}(u)}{{d}(u)}.$

Therefore, by the definition of ${\bm{p}}$ we have that

$\displaystyle{\bm{p}}({L}_{1}\cup{R}_{2})$
$\displaystyle\geq\mathrm{apr}(\alpha,{\bm{\chi}}_{v},{\bm{r}})({L}_{1}\cup{R}_{2})-\mathrm{apr}(\alpha,{\bm{\chi}}_{v},{\bm{r}})({L}_{2}\cup{R}_{1})$
$\displaystyle\geq\mathrm{apr}(\alpha,{\bm{\chi}}_{v},{\bm{r}})({L}_{1}\cup{R}_{2})-\mathrm{apr}(\alpha,{\bm{\chi}}_{v},{\bm{r}})(\overline{{L}_{1}\cup{R}_{2}})$
$\displaystyle\geq\mathrm{apr}(\alpha,{\bm{\chi}}_{v},{\bm{r}})({L}_{1}\cup{R}_{2})-(1-\mathrm{apr}(\alpha,{\bm{\chi}}_{v},{\bm{r}})({L}_{1}\cup{R}_{2}))$
$\displaystyle=2\cdot\mathrm{apr}(\alpha,{\bm{\chi}}_{v},{\bm{r}})({L}_{1}\cup{R}_{2})-1$
$\displaystyle\geq
1-\frac{2{\beta}({L},{R})}{\alpha}-2\mathrm{vol}({S})\max_{u\in{V}}\frac{{\bm{r}}(u)}{{d}(u)},$

which proves the statement of the lemma. ∎

To prove the second fact promised at the beginning of this subsection, we show
as an intermediate lemma that the value of ${\bm{p}}(u_{1})$ can be bounded
with respect to its value after taking a step of the random walk:
$({\mathbf{W}}{\bm{p}})(u_{1})$. In order to prove this, we need to carefully
analyse the effect of the $\sigma$-operator on the approximate Pagerank
vector, and in particular examine the effect of the residual vector
${\bm{r}}$.

######  Lemma 6.6.

Let ${G}$ be a graph with double cover ${H}$, and
$\mathrm{apr}(\alpha,{\bm{s}},{\bm{r}})$ be the approximate Pagerank vector
defined with respect to ${H}$. Then,
${\bm{p}}=\sigma\circ\left(\mathrm{apr}(\alpha,{\bm{s}},{\bm{r}})\right)$
satisfies that
${\bm{p}}(u_{1})\leq\alpha\left({\bm{s}}(u_{1})+{\bm{r}}(u_{2})\right)+(1-\alpha)({\mathbf{W}}{\bm{p}})(u_{1})$,
and
${\bm{p}}(u_{2})\leq\alpha\left({\bm{s}}(u_{2})+{\bm{r}}(u_{1})\right)+(1-\alpha)({\mathbf{W}}{\bm{p}})(u_{2})$
for any $u\in{V}_{G}$.

###### Proof.

Let $u\in{V}_{G}$ be an arbitrary vertex. We have that

$\displaystyle{\bm{p}}(u_{1})$
$\displaystyle=\sigma\circ\big{(}\mathrm{ppr}(\alpha,{\bm{s}})-\mathrm{ppr}(\alpha,{\bm{r}})\big{)}(u_{1})$
$\displaystyle=\sigma\circ\big{(}\alpha{\bm{s}}+(1-\alpha){\mathbf{W}}\mathrm{ppr}(\alpha,{\bm{s}})-\alpha{\bm{r}}-(1-\alpha){\mathbf{W}}\mathrm{ppr}(\alpha,{\bm{r}})\big{)}(u_{1})$
$\displaystyle=\sigma\circ\big{(}\alpha{\bm{s}}+(1-\alpha){\mathbf{W}}\mathrm{apr}(\alpha,{\bm{s}},{\bm{r}})-\alpha{\bm{r}}\big{)}(u_{1})$
$\displaystyle=\max(0,(\alpha{\bm{s}}+(1-\alpha){\mathbf{W}}\mathrm{apr}(\alpha,{\bm{s}},{\bm{r}}))(u_{1})$
$\displaystyle\quad\quad{}-(\alpha{\bm{s}}+(1-\alpha){\mathbf{W}}\mathrm{apr}(\alpha,{\bm{s}},{\bm{r}}))(u_{2})+\alpha{\bm{r}}(u_{2})-\alpha{\bm{r}}(u_{1}))$
$\displaystyle\leq\sigma\circ\big{(}\alpha{\bm{s}}+(1-\alpha){\mathbf{W}}\mathrm{apr}(\alpha,{\bm{s}},{\bm{r}})\big{)}(u_{1})+\max(0,\alpha{\bm{r}}(u_{2})-\alpha{\bm{r}}(u_{1}))$
$\displaystyle\leq\sigma\circ\big{(}\alpha{\bm{s}}+(1-\alpha){\mathbf{W}}\mathrm{apr}(\alpha,{\bm{s}},{\bm{r}})\big{)}(u_{1})+\alpha{\bm{r}}(u_{2})$
$\displaystyle\leq\sigma\circ\big{(}\alpha{\bm{s}}\big{)}(u_{1})+(1-\alpha)\sigma\circ\big{(}{\mathbf{W}}\mathrm{apr}(\alpha,{\bm{s}},{\bm{r}})\big{)}(u_{1})+\alpha{\bm{r}}(u_{2})$
$\displaystyle\leq\alpha{\bm{s}}(u_{1})+\alpha{\bm{r}}(u_{2})+(1-\alpha)({\mathbf{W}}{\bm{p}})(u_{1}),$

where the first equality follows by the definition of the approximate
Pagerank, the second equality follows by the definition of the Pagerank, and
the last two inequalities follow by Lemma 6.2. This proves the first
statement, and the second statement follows by symmetry. ∎

Notice that applying the $\sigma$-operator for any vertex $u_{1}$ introduces a
new dependency on the value of the residual vector ${\bm{r}}$ at $u_{2}$. This
subtle observation demonstrates the additional complexity introduced by the
$\sigma$-operator when compared with previous analysis of Pagerank-based local
algorithms [ACL06]. Taking account of the $\sigma$-operator, let us further
analyse the Lovász-Simonovits curve defined by ${\bm{p}}$, which is a common
technique in the analysis of random walks on graphs [LS90]. Our goal is to
show that if there is a set ${S}$ with a large value of ${\bm{p}}({S})$, then
there must be a sweep set ${S}_{j}^{{\bm{p}}}$ with low conductance. We first
bound the curve at some point by the conductance of the corresponding sweep
set.

######  Lemma 6.7.

Let ${\bm{p}}=\sigma\circ\left(\mathrm{apr}(\alpha,{\bm{s}},{\bm{r}})\right)$.
It holds for any $j\in[n-1]$ that

$\displaystyle{\bm{p}}\\!\left[\mathrm{vol}({S}_{j}^{{\bm{p}}})\right]\leq$
$\displaystyle\alpha\Big{(}{\bm{s}}\\!\left[\mathrm{vol}({S}_{j}^{{\bm{p}}})\right]+{\bm{r}}\\!\left[\mathrm{vol}({S}_{j}^{{\bm{p}}})\right]\Big{)}$
$\displaystyle{}+(1-\alpha)\frac{1}{2}\Big{(}{\bm{p}}\\!\left[\mathrm{vol}({S}_{j}^{{\bm{p}}})-\left\lvert\partial({S}_{j}^{{\bm{p}}})\right\rvert\right]\Big{)}$
$\displaystyle{}+(1-\alpha)\frac{1}{2}\Big{(}{\bm{p}}\\!\left[\mathrm{vol}({S}_{j}^{{\bm{p}}})+\left\lvert\partial({S}_{j}^{{\bm{p}}})\right\rvert\right]\Big{)}.$

Since
$\mathrm{vol}({S}_{j}^{{\bm{p}}})\pm\left\lvert\partial({S}_{j}^{{\bm{p}}})\right\rvert=\mathrm{vol}({S}_{j}^{{\bm{p}}})(1\pm{\Phi}({S}_{j}^{{\bm{p}}}))$,
this tells us that when the conductance of the sweep set ${S}_{j}^{{\bm{p}}}$
is high, the Lovász-Simonovits curve around the point
$\mathrm{vol}({S}_{j}^{{\bm{p}}})$ is close to a straight line. For the proof
of Lemma 6.7, we view the undirected graph ${H}$ instead as a directed graph,
and each edge $\\{u,v\\}\in{E}_{H}$ as a pair of directed edges $(u,v)$ and
$(v,u)$. For any edge $(u,v)$ and vector ${\bm{p}}\in\mathbb{R}_{\geq
0}^{2n}$, let

$p(u,v)=\frac{{\bm{p}}(u)}{{d}(u)}$

and for a set of directed edges ${A}$, let

$p({A})=\sum_{(u,v)\in{A}}p(u,v).$

Now for any set of vertices ${S}\subset{V}_{H}$, let
$\mathrm{in}({S})=\\{(u,v)\in{E}_{H}:v\in{S}\\}$ and
$\mathrm{out}({S})=\\{(u,v)\in{V}_{H}:u\in{S}\\}$. Additionally, for any
simple set ${S}\subset{V}_{H}$, we define the simple complement of the set
${S}$ by

$\widehat{{S}}=\\{u_{2}:u_{1}\in{S}\\}\cup\\{u_{1}:u_{2}\in{S}\\}.$

We need the following property of the Lovász-Simonovitz curve with regard to
sets of edges.

######  Lemma 6.8.

For any set of edges ${A}$, it holds that

$p({A})\leq{\bm{p}}\\!\left[\left\lvert{A}\right\rvert\right].$

###### Proof.

For each $u\in{V}$, let $x_{u}=\left\lvert\\{(u,v)\in{A}\\}\right\rvert$ be
the number of edges in ${A}$ with the tail at $u$. Then, we have by definition
that

$\displaystyle p({A})$
$\displaystyle=\sum_{(u,v)\in{A}}\frac{{\bm{p}}(u)}{{d}(u)}=\sum_{u\in{V}}\frac{x_{u}}{{d}(u)}{\bm{p}}(u).$

Since $x_{u}/{d}(u)\in[0,1]$ and

$\sum_{u\in{V}}\frac{x_{u}}{{d}(u)}{d}(u)=\sum_{u\in{V}}x_{u}=\left\lvert{A}\right\rvert,$

the statement follows from (3.1). ∎

We also make use of the following lemma from [ACL06].

######  Lemma 6.9 ([ACL06], Lemma 4).

For any distribution ${\bm{p}}$ and any set of vertices ${A}$,

$({\mathbf{W}}{\bm{p}})({A})\leq\frac{1}{2}\cdot\left(p(\mathrm{in}({A})\cup\mathrm{out}({A}))+p(\mathrm{in}({A})\cap\mathrm{out}({A}))\right).$

These two facts give us everything we need to prove the behaviour of the
Lovász-Simonovits curve described in Lemma 6.7.

###### Proof of Lemma 6.7.

By definition, we have that

$\displaystyle{\bm{p}}({S})$
$\displaystyle=\sum_{u_{1}\in{S}}{\bm{p}}(u_{1})+\sum_{u_{2}\in{S}}{\bm{p}}(u_{2})$
$\displaystyle\leq\sum_{u_{1}\in{S}}\Big{(}\alpha\left({\bm{s}}(u_{1})+{\bm{r}}(u_{2})\right)+(1-\alpha)({\mathbf{W}}{\bm{p}})(u_{1})\Big{)}$
$\displaystyle\quad\quad{}+\sum_{u_{2}\in{S}}\Big{(}\alpha\left({\bm{s}}(u_{2})+{\bm{r}}(u_{1})\right)+(1-\alpha)({\mathbf{W}}{\bm{p}})(u_{2})\Big{)}$
$\displaystyle=\alpha\cdot\Bigg{(}\sum_{u_{1}\in{S}}{\bm{s}}(u_{1})+\sum_{u_{2}\in{S}}{\bm{s}}(u_{2})+\sum_{u_{1}\in{S}}{\bm{r}}(u_{2})+\sum_{u_{2}\in{S}}{\bm{r}}(u_{1})\Bigg{)}$
$\displaystyle\quad\quad{}+(1-\alpha)\cdot\Bigg{(}\sum_{u_{1}\in{S}}({\mathbf{W}}{\bm{p}})(u_{1})+\sum_{u_{2}\in{S}}({\mathbf{W}}{\bm{p}})(u_{2})\Bigg{)}$
$\displaystyle=\alpha\cdot\Big{(}{\bm{s}}({S})+{\bm{r}}\left(\widehat{{S}}\right)\\!\Big{)}+(1-\alpha)\cdot({\mathbf{W}}{\bm{p}})({S})$
$\displaystyle\leq\alpha\cdot\Big{(}{\bm{s}}({S})+{\bm{r}}\left(\widehat{{S}}\right)\\!\Big{)}+(1-\alpha)\cdot\frac{1}{2}\cdot\Big{(}p(\mathrm{in}(S)\cup\mathrm{out}(S))+p(\mathrm{in}(S)\cap\mathrm{out}(S))\Big{)},$

where the first inequality follows by Lemma 6.6 and the last one follows by
Lemma 6.9.

Now, recall that
${\bm{p}}\\!\left[\mathrm{vol}({S}_{j}^{{\bm{p}}})\right]={\bm{p}}({S}_{j}^{{\bm{p}}})$
and notice that
$\mathrm{vol}\left(\widehat{{S}_{j}^{{\bm{p}}}}\right)=\mathrm{vol}\left({S}_{j}^{{\bm{p}}}\right)$
holds by the definition of $\widehat{{S}}$. Hence, using Lemma 6.8, we have
that

$\displaystyle{\bm{p}}\\!\left[\mathrm{vol}({S}_{j}^{{\bm{p}}})\right]$
$\displaystyle={\bm{p}}({S}_{j}^{{\bm{p}}})$
$\displaystyle\leq\alpha\left({\bm{s}}({S}_{j}^{{\bm{p}}})+{\bm{r}}\left(\widehat{{S}_{j}^{{\bm{p}}}}\right)\right)+(1-\alpha)\cdot\frac{1}{2}\Big{(}p\left(\mathrm{in}({S}_{j}^{{\bm{p}}})\cup\mathrm{out}({S}_{j}^{{\bm{p}}})\right)+p(\mathrm{in}({S}_{j}^{{\bm{p}}})\cap\mathrm{out}({S}_{j}^{{\bm{p}}}))\Big{)}$
$\displaystyle\leq\alpha\Big{(}{\bm{s}}\\!\left[\mathrm{vol}({S}_{j}^{{\bm{p}}})\right]+{\bm{r}}\\!\left[\mathrm{vol}({S}_{j}^{{\bm{p}}})\right]\Big{)}$
$\displaystyle\qquad{}+(1-\alpha)\cdot\frac{1}{2}\left({\bm{p}}\\!\left[\left\lvert\mathrm{in}({S}_{j}^{{\bm{p}}})\cup\mathrm{out}({S}_{j}^{{\bm{p}}})\right\rvert\right]+{\bm{p}}\\!\left[\left\lvert\mathrm{in}({S}_{j}^{{\bm{p}}})\cap\mathrm{out}({S}_{j}^{{\bm{p}}})\right\rvert\right]\right).$

It remains to show that

$\left\lvert\mathrm{in}({S}_{j}^{{\bm{p}}})\cap\mathrm{out}({S}_{j}^{{\bm{p}}})\right\rvert=\mathrm{vol}({S}_{j}^{{\bm{p}}})-\left\lvert\partial({S}_{j}^{{\bm{p}}})\right\rvert,$

and

$\left\lvert\mathrm{in}({S}_{j}^{{\bm{p}}})\cup\mathrm{out}({S}_{j}^{{\bm{p}}})\right\rvert=\mathrm{vol}({S}_{j}^{{\bm{p}}})+\left\lvert\partial({S}_{j}^{{\bm{p}}})\right\rvert.$

The first follows by noticing that
$\left\lvert\mathrm{in}({S}_{j}^{{\bm{p}}})\cap\mathrm{out}({S}_{j}^{{\bm{p}}})\right\rvert$
counts precisely twice the number of edges with both endpoints inside
${S}_{j}^{{\bm{p}}}$. The second follows since

$\left\lvert\mathrm{in}({S}_{j}^{{\bm{p}}})\cup\mathrm{out}({S}_{j}^{{\bm{p}}})\right\rvert=\left\lvert\mathrm{in}({S}_{j}^{{\bm{p}}})\cap\mathrm{out}({S}_{j}^{{\bm{p}}})\right\rvert+\left\lvert\mathrm{in}({S}_{j}^{{\bm{p}}})\setminus\mathrm{out}({S}_{j}^{{\bm{p}}})\right\rvert+\left\lvert\mathrm{out}({S}_{j}^{{\bm{p}}})\setminus\mathrm{in}({S}_{j}^{{\bm{p}}})\right\rvert$

and both the second and third terms on the right hand side are equal to
$\left\lvert\partial({S}_{j}^{{\bm{p}}})\right\rvert$. ∎

We now show another technical lemma which bounds the Lovász-Simonovits curve
with respect to the conductance of the sweep sets ${S}_{j}^{{\bm{p}}}$. To
understand this lemma, recall from the discussion in Section 3.3 that the
Lovász-Simonovits curve of the stationary distribution is linear:
${\bm{\pi}}[k]=k/\mathrm{vol}({V}_{H})$. This lemma bounds how far the Lovász-
Simonovits curve deviates from that of the stationary distribution. In
particular, if there is no sweep set with low conductance, then the deviation
must be small.

######  Lemma 6.10.

Let
${\bm{p}}=\sigma\circ\left(\mathrm{apr}_{H}(\alpha,{\bm{s}},{\bm{r}})\right)$
such that $\max_{u\in{V}_{H}}\frac{{\bm{r}}(u)}{{d}(u)}\leq\epsilon$, and
$\phi$ be any constant in $[0,1]$. If ${\Phi}({S}_{j}^{{\bm{p}}})\geq\phi$ for
all $j\in[\left\lvert\mathrm{supp}({\bm{p}})\right\rvert]$, then

${\bm{p}}[k]-\frac{k}{\mathrm{vol}({V}_{H})}\leq\alpha t+\alpha\epsilon
kt+\sqrt{\min(k,\mathrm{vol}({V}_{H})-k)}\left(1-\frac{\phi^{2}}{8}\right)^{t}$

for all $k\in[0,\mathrm{vol}({V}_{H})]$ and integer $t\geq 0$.

###### Proof.

For ease of discussion we write $k_{j}=\mathrm{vol}({S}_{j}^{{\bm{p}}})$ and
let $\overline{k_{j}}=\min(k_{j},\mathrm{vol}({V}_{H})-k_{j})$. For
convenience we write

$f_{t}(k)=\alpha t+\alpha\epsilon
kt+\sqrt{\min(k,\mathrm{vol}({V}_{H})-k)}\left(1-\frac{\phi^{2}}{8}\right)^{t}.$

We prove by induction that for all $t\geq 0$,

${\bm{p}}[k]-\frac{k}{\mathrm{vol}({V}_{H})}\leq f_{t}(k).$

For the base case, this holds for $t=0$ for any $\phi$. Our proof is by case
distinction: (1) for any integer $k\in[\mathrm{vol}({V}_{H})-1]$,

${\bm{p}}[k]-\frac{k}{\mathrm{vol}({V}_{H})}\leq
1\leq\sqrt{\min(k,\mathrm{vol}({V}_{H})-k)}\leq f_{0}(k);$

(2) for $k=0$ or $k=\mathrm{vol}({V}_{H})$,
${\bm{p}}[k]-\frac{k}{\mathrm{vol}({V}_{H})}=0\leq f_{0}(k)$. The base case
follows, since $f_{0}$ is concave and ${\bm{p}}[k]$ is linear between integer
values.

Now for the inductive case, we assume that the claim holds for $t$ and show
that it holds for $t+1$. It suffices to show that the following holds for
every $j\in[\left\lvert\mathrm{supp}({\bm{p}})\right\rvert]$:

${\bm{p}}[k_{j}]-\frac{k_{j}}{\mathrm{vol}({V}_{H})}\leq f_{t+1}(k_{j}).$

The lemma follows because this inequality holds trivially for $j=0$ and $j=n$
and ${\bm{p}}[k]$ is linear between $k_{j}$ for
$j\in\\{0,n\\}\cup[1,\left\lvert\mathrm{supp}({\bm{p}})\right\rvert]$.

For any $j\in[1,\left\lvert\mathrm{supp}({\bm{p}})\right\rvert]$, it holds by
Lemma 6.7 that

$\displaystyle{\bm{p}}\\!\left[k_{j}\right]$
$\displaystyle\leq\alpha\left({\bm{s}}\\!\left[k_{j}\right]+{\bm{r}}\\!\left[k_{j}\right]\right)+(1-\alpha)\frac{1}{2}\left({\bm{p}}\\!\left[k_{j}-\left\lvert\partial({S}_{j}^{{\bm{p}}})\right\rvert\right]+{\bm{p}}\\!\left[k_{j}+\left\lvert\partial({S}_{j}^{{\bm{p}}})\right\rvert\right]\right)$
$\displaystyle\leq\alpha+\alpha\epsilon
k_{j}+\frac{1}{2}\left({\bm{p}}\\!\left[k_{j}-{\Phi}({S}_{j}^{{\bm{p}}})\cdot\overline{k_{j}}\right]+{\bm{p}}\\!\left[k_{j}+{\Phi}({S}_{j}^{{\bm{p}}})\cdot\overline{k_{j}}\right]\right)$
$\displaystyle\leq\alpha+\alpha\epsilon
k_{j}+\frac{1}{2}\left({\bm{p}}\\!\left[k_{j}-\phi\overline{k_{j}}\right]+{\bm{p}}\\!\left[k_{j}+\phi\overline{k_{j}}\right]\right),$

where the second inequality uses the fact that
${\bm{r}}\\!\left[k_{j}\right]\leq\epsilon k_{j}$ and the last inequality uses
the concavity of ${\bm{p}}\\!\left[k\right]$ and the fact that
${\Phi}({S}_{j}^{{\bm{p}}})\geq\phi$. By the induction hypothesis, we have
that

$\displaystyle{\bm{p}}\\!\left[k_{j}\right]$
$\displaystyle\leq\alpha+\alpha\epsilon
k_{j}+\frac{1}{2}\left(f_{t}(k_{j}-\phi\overline{k_{j}})+\frac{k_{j}-\phi\overline{k_{j}}}{\mathrm{vol}({V}_{H})}+f_{t}(k_{j}+\phi\overline{k_{j}})+\frac{k_{j}+\phi\overline{k_{j}}}{\mathrm{vol}({V}_{H})}\right)$
$\displaystyle=\alpha+\alpha\epsilon
k_{j}+\frac{k_{j}}{\mathrm{vol}({V}_{H})}+\frac{1}{2}\left(f_{t}(k_{j}+\phi\overline{k_{j}})+f_{t}(k_{j}-\phi\overline{k_{j}})\right)$
$\displaystyle=\alpha+\alpha\epsilon k_{j}+\alpha t+\alpha\epsilon
k_{j}t+\frac{k_{j}}{\mathrm{vol}({V}_{H})}+\frac{1}{2}\Bigg{(}\sqrt{\min(k_{j}-\phi\overline{k_{j}},\mathrm{vol}({V}_{H})-k_{j}+\phi\overline{k_{j}})}$
$\displaystyle\qquad{}+\sqrt{\min(k_{j}+\phi\overline{k_{j}},\mathrm{vol}({V}_{H})-k_{j}-\phi\overline{k_{j}})}\Bigg{)}\left(1-\frac{\phi^{2}}{8}\right)^{t}$
$\displaystyle\leq\alpha(t+1)+\alpha\epsilon
k_{j}(t+1)+\frac{k_{j}}{\mathrm{vol}({V}_{H})}+\frac{1}{2}\left(\sqrt{\overline{k_{j}}-\phi\overline{k_{j}}}+\sqrt{\overline{k_{j}}+\phi\overline{k_{j}}}\right)\left(1-\frac{\phi^{2}}{8}\right)^{t}$

Now, using the Taylor series of $\sqrt{1+\phi}$ at $\phi=0$, we see that for
any $x\geq 0$ and $\phi\in[0,1]$,

$\displaystyle\frac{1}{2}\left(\sqrt{x-\phi x}+\sqrt{x+\phi x}\right)$
$\displaystyle\leq\frac{\sqrt{x}}{2}\left(\left(1-\frac{\phi}{2}-\frac{\phi^{2}}{8}-\frac{\phi^{3}}{16}\right)+\left(1+\frac{\phi}{2}-\frac{\phi^{2}}{8}+\frac{\phi^{3}}{16}\right)\right)$
$\displaystyle\leq\sqrt{x}\left(1-\frac{\phi^{2}}{8}\right).$

Applying this with $x=\overline{k_{j}}$, we have

$\displaystyle{\bm{p}}\\!\left[k_{j}\right]-\frac{k_{j}}{\mathrm{vol}({V}_{H})}$
$\displaystyle\leq\alpha(t+1)+\alpha\epsilon
k_{j}(t+1)+\sqrt{\overline{k_{j}}}\left(1-\frac{\phi^{2}}{8}\right)\left(1-\frac{\phi^{2}}{8}\right)^{t}$
$\displaystyle=f_{t+1}(k_{j}),$

which completes the proof. ∎

We can now use this bound to show the other direction: if the Lovász-
Simonovits curve is particularly large at some point, then there must be a
sweep set with low conductance.

######  Lemma 6.11.

Let ${G}$ be a graph with double cover ${H}$, and let
${\bm{p}}=\sigma\circ\left(\mathrm{apr}_{H}(\alpha,{\bm{s}},{\bm{r}})\right)$
such that $\max_{u\in{V}_{H}}\frac{{\bm{r}}(u)}{{d}(u)}\leq\epsilon$. If there
is a set of vertices ${S}\subset{V}_{H}$ and a constant $\delta$ such that
${\bm{p}}({S})-\frac{\mathrm{vol}({S})}{\mathrm{vol}({V}_{H})}\geq\delta$,
then there is some $j\in[1,\left\lvert\mathrm{supp}({\bm{p}})\right\rvert]$
such that

${\Phi}_{H}({S}_{j}^{{\bm{p}}})<6\sqrt{(1+\epsilon\mathrm{vol}({S}))\alpha\ln\left(\frac{4}{\delta}\right)\big{/}\delta}.$

###### Proof.

Let ${H}_{c}$ be a weighted version of the double cover with the weight of
every edge equal to some constant $c$. Let $k=\mathrm{vol}_{{H}_{c}}({S})$ and
$\overline{k}=\min(k,\mathrm{vol}({V}_{{H}_{c}})-k)$. Notice that the
behaviour of random walks and the conductance of vertex sets are unchanged by
re-weighting the graph by a constant factor. As such,
${\bm{p}}=\sigma\circ\mathrm{apr}_{{H}_{c}}(\alpha,{\bm{s}},{\bm{r}})$ and we
let $\phi=\min_{j}{\Phi}_{{H}_{c}}({S}_{j}^{{\bm{p}}})$. Hence, by Lemma 6.10
it holds for any $t>0$ that

$\displaystyle\delta$
$\displaystyle<{\bm{p}}\\!\left[k\right]-\frac{k}{\mathrm{vol}({V}_{{H}_{c}})}<\alpha
t(1+\epsilon k)+\sqrt{\overline{k}}\left(1-\frac{\phi^{2}}{8}\right)^{t}.$

Letting $v=\mathrm{vol}({V}_{{H}_{c}})$ we set
$t=\left\lceil\frac{8}{\phi^{2}}\ln\frac{2\sqrt{v/2}}{\delta}\right\rceil$.
Now, assuming that

$\delta\geq\frac{2}{\sqrt{v/2}}$ (6.3)

we have

$\delta<(1+\epsilon
k)\alpha\left\lceil\frac{8}{\phi^{2}}\ln\frac{2\sqrt{v/2}}{\delta}\right\rceil+\frac{\delta}{2\sqrt{v/2}}\sqrt{\overline{k}}<\frac{9(1+\epsilon
k)\alpha\ln(v/2)}{\phi^{2}}+\frac{\delta}{2}.$

We set $c$ such that

$v=c\
\mathrm{vol}({V}_{H})=\mathrm{vol}({V}_{{H}_{c}})=\left(\frac{4}{\delta}\right)^{2},$

which satisfies (6.3) and implies that

$\phi<\sqrt{\frac{36(1+\epsilon k)\alpha\ln(4/\delta)}{\delta}}.$

By the definition of $\phi$, there must be some ${S}_{j}^{{\bm{p}}}$ with the
desired property. ∎

We have now shown the two facts promised at the beginning of this subsection.
Putting these together, if there is a simple set ${S}\subset{V}_{H}$ with low
conductance, then we can find a sweep set of
$\sigma\circ\mathrm{apr}(\alpha,{\bm{s}},{\bm{r}})$ with low conductance. By
the reduction from almost-bipartite sets in ${G}$ to low-conductance simple
sets in ${H}$, our target set corresponds to a simple set ${S}\subset{V}_{H}$
which leads to Algorithm 1 for finding almost-bipartite sets. Our result is
summarised as follows.

######  Theorem 6.1.

Let ${G}$ be an $n$-vertex undirected graph, and ${L},{R}\subset{V}_{G}$ be
disjoint sets such that ${\beta}({L},{R})\leq\beta$ and
$\mathrm{vol}({L}\cup{R})\leq\gamma$. Then, there is a set
${C}\subseteq{L}\cup{R}$ with $\mathrm{vol}(C)\geq\mathrm{vol}({L}\cup{R})/2$
such that, for any $v\in{C}$,
$\textsc{LocBipartDC}\left({G},v,\gamma,\sqrt{7560\beta}\right)$ returns
$({L}^{\prime},{R}^{\prime})$ with
${\beta}({L}^{\prime},{R}^{\prime})=O\\!\left(\sqrt{\beta}\right)$ and
${\mathrm{vol}({L}^{\prime}\cup{R}^{\prime})}=O\\!\left(\beta^{-1}\gamma\right)$.
Moreover, the algorithm has running time $O\\!\left(\beta^{-1}\gamma\log
n\right)$.

###### Proof.

We set the parameters of Algorithm 1 to be

  * •

$\alpha=\widehat{\beta}^{2}/378=20\beta$, and

  * •

$\epsilon=1/(20\gamma)$.

Let
${\bm{p}}=\sigma\circ\left(\mathrm{apr}_{H}(\alpha,{\bm{\chi}}_{v},{\bm{r}})\right)$
be the simplified approximate Pagerank vector computed in the algorithm, which
satisfies that $\max_{v\in{V}_{H}}\frac{{\bm{r}}(v)}{{d}(v)}\leq\epsilon$, and
${C}^{\prime}={L}_{1}\cup{R}_{2}$ be the target set in the double cover.
Hence, by Lemma 6.5 we have that

${\bm{p}}({C}^{\prime})\geq
1-\frac{2\beta}{\alpha}-2\epsilon\cdot\mathrm{vol}({C})\geq
1-\frac{1}{10}-\frac{1}{10}=\frac{4}{5}.$

Notice that, since ${C}^{\prime}$ is simple, we have that
$\frac{\mathrm{vol}({C}^{\prime})}{\mathrm{vol}({V}_{H})}\leq\frac{1}{2}$ and

${\bm{p}}({C}^{\prime})-\frac{\mathrm{vol}({C}^{\prime})}{\mathrm{vol}({V}_{H})}\geq\frac{4}{5}-\frac{1}{2}=\frac{3}{10}.$

Therefore, by Lemma 6.11 and choosing $\delta=3/10$, there is some
$j\in[1,\left\lvert\mathrm{supp}({\bm{p}})\right\rvert]$ such that

$\displaystyle{\Phi}({S}_{j}^{{\bm{p}}})$
$\displaystyle<\sqrt{\frac{360}{3}(1+\epsilon\mathrm{vol}({C}))\alpha\ln\left(\frac{40}{3}\right)}\leq\sqrt{\left(1+\frac{1}{20}\right)7200\beta}=\widehat{\beta}.$

Since such a ${S}_{j}^{{\bm{p}}}$ is a simple set, by Lemma 6.1, we know that
the sets ${L}^{\prime}=\\{u\in{V}_{G}:u_{1}\in{S}_{j}^{{\bm{p}}}\\}$ and
${R}^{\prime}=\\{u\in{V}_{G}:u_{2}\in{S}_{j}^{{\bm{p}}}\\}$ satisfy
${\beta}({L}^{\prime},{R}^{\prime})\leq\widehat{\beta}$. For the volume
guarantee, Lemma 6.4 gives that

$\mathrm{vol}(\mathrm{supp}({\bm{p}}))\leq\frac{1}{\epsilon\alpha}=\frac{\gamma}{\beta}.$

Since the sweep set procedure in the algorithm is over the support of
${\bm{p}}$, we have that

$\mathrm{vol}({L}^{\prime}\cup{R}^{\prime})\leq\mathrm{vol}(\mathrm{supp}({\bm{p}}))\leq\beta^{-1}\gamma.$

Now, we analyse the running time of the algorithm. By Lemma 6.4, computing the
approximate Pagerank vector ${\bm{p}}^{\prime}$ takes time

$O\\!\left(\frac{1}{\epsilon\alpha}\right)=O\\!\left(\beta^{-1}\gamma\right).$

Since
$\mathrm{vol}(\mathrm{supp}({\bm{p}}^{\prime}))=O\\!\left(\frac{1}{\epsilon\alpha}\right)$,
computing $\sigma\circ\left({\bm{p}}^{\prime}\right)$ can also be done in time
$O\\!\left(\beta^{-1}\gamma\right)$. The cost of checking each conductance in
the sweep set loop is
$O\\!\left(\mathrm{vol}(\mathrm{supp}({\bm{p}}))\log(n)\right)=O\\!\left(\beta^{-1}\gamma\log(n)\right)$.
This dominates the running time of the algorithm, which completes the proof of
the theorem. ∎

We remark that the quadratic approximation guarantee in Theorem 6.1 matches
the state-of-the-art local algorithm for finding a single set with low
conductance [AOGPT16]. Furthermore, this result presents a significant
improvement over the previous state-of-the-art by Li and Peng [LP13], whose
design is based on an entirely different technique. For any
$\epsilon\in[0,1/2]$, their algorithm has running time
$O\\!\left(\epsilon^{2}\beta^{-2}\gamma^{1+\epsilon}\log^{3}\gamma\right)$ and
returns a set with volume $O\\!\left(\gamma^{1+\epsilon}\right)$ and
bipartiteness $O\\!\left(\sqrt{\beta/\epsilon}\right)$. In particular, their
algorithm requires much higher time complexity in order to guarantee the same
bipartiteness $O\left(\sqrt{\beta}\right)$.

###  6.2 Algorithm for Directed Graphs

We now turn our attention to local algorithms for finding densely-connected
clusters in directed graphs. In comparison with undirected graphs, we are
interested in finding disjoint ${L},{R}\subset{V}$ of an input directed graph
${G}=({V},{E})$ such that most of the edges adjacent to ${L}\cup{R}$ are _from
${L}$ to ${R}$_. To formalise this, we define the _flow ratio_ from ${L}$ to
${R}$ as

$F({L},{R})\triangleq
1-\frac{2{w}({L},{R})}{\mathrm{vol}_{\mathrm{out}}({L})+\mathrm{vol}_{\mathrm{in}}({R})},$

where ${w}({L},{R})$ is the number of directed edges from ${L}$ to ${R}$.
Notice that we take not only edge densities but also edge directions into
account: a low $F({L},{R})$-value tells us that almost all edges with their
tail in ${L}$ have their head in ${R}$, and conversely almost all edges with
their head in ${R}$ have their tail in ${L}$. One could also see $F({L},{R})$
as a generalisation of ${\beta}({L},{R})$. In particular, if we view an
undirected graph as a directed graph by replacing each edge with two directed
edges, then ${\beta}({L},{R})=F({L},{R})$. In this section, we develop a local
algorithm for finding such vertex sets in a directed graph, and analyse the
algorithm’s performance.

####  6.2.1 Reduction by Semi-Double Cover

Given a directed graph ${G}=({V}_{G},{E}_{G})$, we construct its semi-double
cover ${H}=({V}_{H},{E}_{H})$ as follows: (1) every vertex $v\in{V}_{G}$ has
two corresponding vertices $v_{1},v_{2}\in{V}_{H}$; (2) for every edge
$(u,v)\in{E}_{G}$, we add the edge $\\{u_{1},v_{2}\\}$ in ${E}_{H}$, see
Figure 6.5 for illustration.

$\xrightarrow{}$$\begin{bmatrix}{\mathbf{B}}_{1}&{\mathbf{0}}&{\mathbf{0}}\\\
{\mathbf{0}}&{\mathbf{B}}_{2}&{\mathbf{0}}\\\
{\mathbf{0}}&{\mathbf{0}}&{\mathbf{B}}_{3}\end{bmatrix}$$\xrightarrow{}$Graph
${G}$Normalised Laplacian ${\mathbf{N}}$Spectral
Embedding$\xrightarrow{}$$\begin{bmatrix}{\mathbf{B}}_{1}&{\mathbf{C}}_{12}&{\mathbf{C}}_{13}\\\
{\mathbf{C}}_{12}^{\intercal}&{\mathbf{B}}_{2}&{\mathbf{C}}_{23}\\\
{\mathbf{C}}_{13}^{\intercal}&{\mathbf{C}}_{23}^{\intercal}&{\mathbf{B}}_{3}\end{bmatrix}$$\xrightarrow{}$Graph
${G}$Normalised Laplacian ${\mathbf{N}}$Spectral
Embedding$\rightarrow$$v_{1}$$v_{3}$$v_{5}$$v_{4}$$v_{2}$$\rightarrow$$x_{1}=v_{1}$$x_{2}=v_{4}$$x_{3}=v_{5}$${\bm{p}}^{(i)}$${\bm{p}}^{(j)}$$\frac{{\bm{p}}^{(i)}}{\left\|{\bm{p}}^{(i)}\right\|}$$\frac{{\bm{p}}^{(j)}}{\left\|{\bm{p}}^{(j)}\right\|}$${\bm{a}}_{i}$${\bm{a}}_{j}$$\frac{\left\|{\bm{a}}_{i}\right\|}{\left\|{\bm{a}}_{j}\right\|}{\bm{a}}_{j}$$a_{1}$$a_{2}$$a$$b$$c$$d$$\Longrightarrow$$b_{1}$$b_{2}$$c_{1}$$c_{2}$$d_{1}$$d_{2}$$\cdots$$a_{1}$$S$$b_{1}$$c_{1}$$d_{1}$$e_{1}$$f_{1}$$\cdots$$\cdots$$a_{2}$$b_{2}$$c_{2}$$d_{2}$$e_{2}$$f_{2}$$\cdots$$a_{1}$$a_{2}$$a$$b$$c$$d$$\Longrightarrow$$b_{1}$$b_{2}$$c_{1}$$c_{2}$$d_{1}$$d_{2}$

Figure 6.5: An example of a directed graph and its semi-double cover

It is worth comparing this reduction with the one for undirected graphs:

  * •

For undirected graphs, we apply the standard double cover and every undirected
edge in ${G}$ corresponds to two edges in the double cover ${H}$;

  * •

For directed graphs, every directed edge in ${G}$ corresponds to _one_
undirected edge in ${H}$. This _asymmetry_ would allow us to ‘recover’ the
direction of any edge in ${G}$.

We follow the use of ${S}_{1},{S}_{2}$ from Section 6.1: for any
${S}\subset{V}_{G}$, we define ${S}_{1}\subset{V}_{H}$ and
${S}_{2}\subset{V}_{H}$ by ${S}_{1}\triangleq\\{v_{1}~{}|~{}v\in{S}\\}$ and
${S}_{2}\triangleq\\{v_{2}~{}|~{}v\in{S}\\}$. The lemma below shows the
connection between the value of $F_{G}({L},{R})$ for any ${L},{R}$ and
${\Phi}_{H}({L}_{1}\cup{R}_{2})$.

######  Lemma 6.12.

Let ${G}$ be a directed graph with semi-double cover ${H}$. Then, it holds for
any ${L},{R}\subset{V}_{G}$ that
$F_{G}({L},{R})={\Phi}_{H}({L}_{1}\cup{R}_{2})$. Similarly, for any simple set
${S}\subset{V}_{H}$, let ${L}=\\{u:u_{1}\in{S}\\}$ and
${R}=\\{u:u_{2}\in{S}\\}$. Then, it holds that
$F_{G}({L},{R})={\Phi}_{H}({S})$.

###### Proof.

We define ${S}_{H}={L}_{1}\cup{R}_{2}$, and have that

$\displaystyle{\Phi}_{H}({S}_{H})$
$\displaystyle=\frac{{w}({S}_{H},{V}_{H}\setminus{S}_{H})}{\mathrm{vol}_{H}({S}_{H})}$
$\displaystyle=\frac{\mathrm{vol}_{H}({S}_{H})-2{w}_{H}({S}_{H},{S}_{H})}{\mathrm{vol}_{H}({S}_{H})}$
$\displaystyle=1-\frac{2{w}_{H}({S}_{H},{S}_{H})}{\mathrm{vol}_{H}({S}_{H})}$
$\displaystyle=1-\frac{2{w}_{G}({L},{R})}{\mathrm{vol}_{\mathrm{out}}({L})+\mathrm{vol}_{\mathrm{in}}({R})}$
$\displaystyle=F_{G}({L},{R}).$

This proves the first statement of the lemma. The second statement of the
lemma follows by the same argument. ∎

####  6.2.2 Design and Analysis of the Algorithm

The new algorithm is a modification of the algorithm by Andersen and Peres
[AP09] described in Section 3.3.2. Given a directed graph ${G}$ as input, the
algorithm simulates the volume-biased ESP on ${G}$’s semi-double cover ${H}$.
Notice that the graph ${H}$ can be constructed locally in the same way as the
local construction of the double cover. However, as the output set ${S}$ of an
ESP-based algorithm is not necessarily simple, the algorithm only returns
vertices $u\in{V}_{G}$ in which _exactly_ one of $u_{1}$ and $u_{2}$ are
included in ${S}$. The key procedure for the algorithm is given in Algorithm
4, in which the GenerateSample procedure is the one described at the end of
Section 3.3.2.

Input : Starting vertex $u$, $i\in\\{1,2\\}$, target flow ratio $\phi$

Output : A pair of sets ${L},{R}\subset{V}_{G}$

1 Set $T=\lfloor(100\phi^{\frac{2}{3}})^{-1}\rfloor$

2 Compute ${S}=\textsc{GenerateSample}_{H}(u_{i},T)$

3 Let ${L}=\\{u\in{V}_{G}:u_{1}\in{S}$ and $u_{2}\not\in{S}\\}$

4 Let ${R}=\\{u\in{V}_{G}:u_{2}\in{S}$ and $u_{1}\not\in{S}\\}$

return ${L}$ and ${R}$

Algorithm 4 EvoCutDirected$(u,i,\phi)$

Notice that in the constructed graph ${H}$,
${\Phi}({L}_{1}\cup{R}_{2})\leq\phi$ does not imply that
${\Phi}({L}_{2}\cup{R}_{1})\leq\phi$. Due to this asymmetry, Algorithm 4 takes
a parameter $i\in\\{1,2\\}$ to indicate whether the starting vertex is in
${L}$ or ${R}$. If it is not known whether $u$ is in ${L}$ or ${R}$, two
copies can be run in parallel, one with $i=1$ and the other with $i=2$. Once
one of them terminates with the performance guaranteed in Theorem 6.2, the
other can be terminated. Hence, we can always assume that it is known whether
the starting vertex $u$ is in ${L}$ or ${R}$.

We now analyse the algorithm. Notice that, since the evolving set process
gives us an arbitrary set on the semi-double cover, Algorithm 4 converts this
into a simple set by removing any vertices $u$ where $u_{1}\in{S}$ and
$u_{2}\in{S}$. The following definition allows us to discuss sets which are
close to being simple.

######  Definition 6.3 ($\epsilon$-simple set).

For any set ${S}\subset{V}_{H}$, let
${P}=\\{u_{1},u_{2}:u\in{V}_{G},u_{1}\in{S}~{}\mbox{and}~{}u_{2}\in{S}\\}$. We
call set ${S}$ $\epsilon$-simple if it holds that
$\frac{\mathrm{vol}({P})}{\mathrm{vol}({S})}\leq\epsilon.$

The notion of $\epsilon$-simple sets measures the ratio of vertices in which
both $u_{1}$ and $u_{2}$ are in ${S}$. In particular, any simple set defined
in Definition 6.1 is $0$-simple. We show that, if ${S}\subset{V}_{H}$ is an
$\epsilon$-simple set for small $\epsilon$, we can construct a simple set
${S}^{\prime}$ with low conductance.

######  Lemma 6.13.

For any $\epsilon$-simple set ${S}\subset{V}_{H}$, let
${P}=\\{u_{1},u_{2}:u\in{V}_{G},u_{1}\in{S}\mbox{ and }u_{2}\in{S}\\}$ and set
${S}^{\prime}={S}\setminus{P}$. Then,
${\Phi}({S}^{\prime})\leq\frac{1}{1-\epsilon}({\Phi}({S})+\epsilon).$

###### Proof.

By the definition of conductance, we have

$\displaystyle{\Phi}({S}^{\prime})$
$\displaystyle=\frac{{w}({S}^{\prime},{V}\setminus{S}^{\prime})}{\mathrm{vol}({S}^{\prime})}$
$\displaystyle\leq\frac{{w}({S},{V}\setminus{S})+\mathrm{vol}({P})}{\mathrm{vol}({S})-\mathrm{vol}({P})}$
$\displaystyle\leq\frac{1}{1-\epsilon}\frac{{w}({S},{V}\setminus{S})+\mathrm{vol}({P})}{\mathrm{vol}({S})}$
$\displaystyle\leq\frac{1}{1-\epsilon}\left(\frac{{w}({S},{V}\setminus{S})}{\mathrm{vol}({S})}+\epsilon\right)$
$\displaystyle=\frac{1}{1-\epsilon}\left({\Phi}({S})+\epsilon\right),$

which proves the lemma. ∎

Given this, in order to guarantee that ${\Phi}({S}^{\prime})$ is low, we need
to construct ${S}$ such that ${\Phi}({S})$ is low and ${S}$ is
$\epsilon$-simple for small $\epsilon$. The following lemma shows that, by
choosing the number of steps of the evolving set process carefully, we can
very tightly control the overlap of the output of the evolving set process
with the target set ${S}$, which we know to be simple.

######  Lemma 6.14.

Let ${C}\subset{V}_{H}$ be a set with conductance ${\Phi}({C})=\phi$, and let
$T=(100\phi^{\frac{2}{3}})^{-1}$. There exists a set ${C}_{g}\subseteq{C}$
with volume at least $\mathrm{vol}({C})/2$ such that for any $x\in{C}_{g}$,
with probability at least $7/9$, a sample path
$({S}_{0},{S}_{1},\ldots,{S}_{T})$ from the volume-biased ESP started from
${S}_{0}=\\{x\\}$ satisfies the following:

  * •

${\Phi}({S}_{t})<60\phi^{\frac{1}{3}}\sqrt{\ln(\mathrm{vol}({V}))}$ for some
$t\in[0,T]$;

  * •

$\mathrm{vol}({S}_{t}\cap{C})\geq\left(1-\frac{1}{10}\phi^{\frac{1}{3}}\right)\mathrm{vol}({S}_{t})$
for all $t\in[0,T]$.

###### Proof.

By Proposition 3.3, with probability at least $(1-1/9)$ there is some $t<T$
such that

$\displaystyle{\Phi}({S}_{t})$ $\displaystyle\leq
3\sqrt{4T^{-1}\ln\mathrm{vol}({V}_{H})}=3\sqrt{400\phi^{\frac{2}{3}}\ln\mathrm{vol}({V}_{H})}=60\phi^{\frac{1}{3}}\sqrt{\ln(\mathrm{vol}({V}_{H}))}.$

Then, by Proposition 3.1 we have that $\mathrm{esc}(x,T,{C})\leq
T\phi=\frac{1}{100}\phi^{1/3}$. Hence, by Proposition 3.4, with probability at
least $9/10$,

$\max_{t\leq
T}\frac{\mathrm{vol}({S}_{t}\setminus{C})}{\mathrm{vol}({S}_{t})}\leq
10\cdot\mathrm{esc}(x,T,{C})\leq\frac{1}{10}\cdot\phi^{1/3}$

Applying the union bound on these two events proves the statement of the
lemma. ∎

This allows us to analyse the performance of Algorithm 4, which is summarised
in Theorem 6.2.

######  Theorem 6.2.

Let ${G}$ be an $n$-vertex directed graph, and ${L},{R}\subset{V}_{G}$ be
disjoint sets such that $F({L},{R})\leq\phi$ and
$\mathrm{vol}({L}\cup{R})\leq\gamma$. There is a set ${C}\subseteq{L}\cup{R}$
with $\mathrm{vol}({C})\geq\mathrm{vol}({L}\cup{R})/2$ such that, for any
$v\in{C}$ and some $i\in\\{1,2\\}$, $\textsc{EvoCutDirected}({G},v,i,\phi)$
returns $({L}^{\prime},{R}^{\prime})$ such that
$F({L}^{\prime},{R}^{\prime})=O\\!\left(\phi^{\frac{1}{3}}\log^{\frac{1}{2}}n\right)$
and
${\mathrm{vol}({L}^{\prime}\cup{R}^{\prime})}=O\\!\left(\left(1-\phi^{\frac{1}{3}}\right)^{-1}\gamma\right)$.
Moreover, the algorithm has running time
$O\\!\left(\phi^{-\frac{1}{2}}\gamma\log^{\frac{3}{2}}n\right)$.

###### Proof.

By Lemma 6.14, we know that, with probability at least $7/9$, the set ${S}$
computed by Algorithm 4 satisfies

$\mathrm{vol}({S}\cap{C})\geq\left(1-\frac{1}{10}\phi^{\frac{1}{3}}\right)\mathrm{vol}({S}).$

Let ${P}=\\{u_{1},u_{2}:u_{1}\in{S}$ and $u_{2}\in{S}\\}$. Then, since ${C}$
is simple, we have that

$\displaystyle\mathrm{vol}({P})$ $\displaystyle\leq
2\cdot(\mathrm{vol}({S})-\mathrm{vol}({S}\cap{C}))\leq
2\cdot\left(1-\left(1-\frac{1}{10}\phi^{\frac{1}{3}}\right)\right)\cdot\mathrm{vol}({S})=\frac{1}{5}\cdot\phi^{\frac{1}{3}}\mathrm{vol}({S}),$

which implies that ${S}$ is $(1/5)\cdot\phi^{\frac{1}{3}}$-simple. Therefore,
by letting ${S}^{\prime}={S}\setminus{P}$, we have by Lemma 6.13 that

$\displaystyle{\Phi}({S}^{\prime})$
$\displaystyle\leq\frac{1}{1-\epsilon}\cdot\left({\Phi}({S})+\epsilon\right)\leq\frac{1}{1-\frac{1}{5}}\left({\Phi}({S})+\frac{1}{5}\phi^{\frac{1}{3}}\right)\leq\frac{5}{4}\cdot{\Phi}({S})+\frac{1}{4}\cdot\phi^{\frac{1}{3}}.$

Since ${\Phi}({S})=O\\!\left(\phi^{\frac{1}{3}}\ln^{\frac{1}{2}}(n)\right)$ by
Lemma 6.14, we have that
${\Phi}({S}^{\prime})=O\\!\left(\phi^{\frac{1}{3}}\ln^{\frac{1}{2}}(n)\right)$.
For the volume guarantee, direct calculation shows that

$\displaystyle\mathrm{vol}({S}^{\prime})\leq\mathrm{vol}({S})\leq\frac{\mathrm{vol}({S}\cap{C})}{1-\frac{1}{10}\phi^{\frac{1}{3}}}\leq\frac{\mathrm{vol}({C})}{1-\phi^{\frac{1}{3}}}.$

Finally, the running time of the algorithm is dominated by the GenerateSample
method, which is shown in [AP09] to have running time
$O\\!\left(\mathrm{vol}({C})\phi^{-\frac{1}{2}}\ln^{\frac{3}{2}}(n)\right)$. ∎

Algorithm 4 is the first local algorithm for directed graphs that approximates
a pair of densely connected clusters, and demonstrates that finding such a
pair appears to be much easier than finding a low-conductance set in a
directed graph; in particular, existing local algorithms for finding a low-
conductance set require the stationary distribution of the random walk in the
directed graph [ACL07], the sublinear-time computation of which is unknown
[CKP+17]. However, the knowledge of the stationary distribution is not needed
for our algorithm.

###  6.3 Experimental Results

In this section we evaluate the performance of the newly proposed algorithms
on both synthetic and real-world datasets. For undirected graphs, we compare
the performance of LocBipartDC against the previous state-of-the-art [LP13]
through synthetic datasets with various parameters, and apply a real-world
dataset to demonstrate the significance of the new algorithm. For directed
graphs, we compare the performance of EvoCutDirected with the state-of-the-art
_non-local_ algorithm since our presented local algorithm for directed graphs
is the first such algorithm in the literature. All experiments are performed
on a Lenovo Yoga 2 Pro with an Intel(R) Core(TM) i7-4510U CPU @ 2.00GHz
processor and 8GB of RAM. The code can be downloaded from

https://github.com/pmacg/local-densely-connected-clusters.

####  6.3.1 Results for Undirected Graphs

We first compare the performance of LocBipartDC with the previous state-of-
the-art given by Li and Peng [LP13], which we can refer to as LP, on synthetic
graphs generated from the stochastic block model (SBM). Specifically, we
assume that the graph has $k=3$ clusters $\\{{C}_{j}\\}_{j=1}^{3}$, and the
number of vertices in each cluster, denoted by $n_{1},n_{2}$ and $n_{3}$
respectively, satisfy $n_{1}=n_{2}=0.1n_{3}$. Moreover, any pair of vertices
$u\in{C}_{i}$ and $v\in{C}_{j}$ is connected with probability $P_{i,j}$. We
assume that $P_{1,1}=P_{2,2}=p_{1}$, $P_{3,3}=p_{2}$, $P_{1,2}=q_{1}$, and
$P_{1,3}=P_{2,3}=q_{2}$. Throughout the experiments, we maintain the ratios
$p_{2}=2p_{1}$ and $q_{2}=0.1p_{1}$, leaving the parameters $n_{1}$, $p_{1}$
and $q_{1}$ free. Notice that the different values of $q_{1}$ and $q_{2}$
guarantee that ${C}_{1}$ and ${C}_{2}$ are the ones optimising the
$\beta$-value, which is why the proposed model is slightly more involved than
the standard SBM described in Section 2.3.2.

We evaluate the quality of the output $({L},{R})$ returned by each algorithm
with respect to its $\beta$-value, the Adjusted Rand Index (ARI) [GA17], as
well as the ratio of the misclassified vertices defined by
$\left(\left\lvert{L}\triangle{C}_{1}\right\rvert+\left\lvert{R}\triangle{C}_{2}\right\rvert\right)/\left(\left\lvert{L}\cup{C}_{1}\right\rvert+\left\lvert{R}\cup{C}_{2}\right\rvert\right)$.
All the reported results are the average performance of each algorithm over
$10$ runs, in which a random vertex from ${C}_{1}\cup{C}_{2}$ is chosen as the
starting vertex of the algorithm.

###### Setting the $\epsilon_{LP}$ parameter in the LP algorithm.

The LP algorithm has an additional parameter over LocBipartDC, which we refer
to as $\epsilon_{LP}$. This parameter influences the runtime and performance
of the algorithm and must be in the range $[0,1/2]$. In order to choose a fair
value of $\epsilon_{LP}$ for comparison with LocBipartDC, we consider several
values on graphs with a range of target volumes.

We generate graphs from the SBM such that $p_{1}=1/n_{1}$ and $q_{1}=100p_{1}$
and vary the size of the target set by varying $n_{1}$ between $100$ and
$10,000$. For values of $\epsilon_{LP}$ in $\\{0.01,0.02,0.1,0.5\\}$, Figure
6.6(a) shows how the runtime of the LP algorithm compares to the LocBipartDC
algorithm for a range of target volumes. In this experiment, the runtime of
the LocBipartDC algorithm lies between the runtimes of the LP algorithm for
$\epsilon_{LP}=0.01$ and $\epsilon_{LP}=0.02$. However, Figure 6.6(b) shows
that the performance of the LP algorithm with $\epsilon_{LP}=0.01$ is
significantly worse than the performance of the LocBipartDC algorithm, and so
for a fair comparison we set $\epsilon_{LP}=0.02$ for the remainder of the
experiments.

(a)

(b)

Figure 6.6: (a) A comparison of the runtimes of the LocBipartDC algorithm and
the LP algorithm with various values of $\epsilon_{LP}$. (b) Setting
$\epsilon_{LP}=0.01$ results in a significantly worse Adjusted Rand Index
(ARI) than the LocBipartDC algorithm.

###### Comparison on the synthetic data.

Table 6.1: Full comparison between Algorithm 1 (LBDC) and the previous state-of-the-art [LP13] (LP). For clarity we report the target bipartiteness $\beta={\beta}({C}_{1},{C}_{2})$ and target volume $\gamma=\mathrm{vol}({C}_{1}\cup{C}_{2})$ along with the SBM parameters. The final column shows the ratio between the number of misclassified vertices and the total number of vertices in the target clusters.  Input graph parameters | Algo. | Runtime |  $\beta$-value | ARI | Misclass.
---|---|---|---|---|---
$n_{1}=10^{3}$, $p_{1}=10^{-3}$, $q_{1}=0.018$ | LBDC | 0.09 | 0.154 | 0.968 | 0.073
$\beta\approx 0.1$, $\gamma\approx 4\cdot 10^{4}$ | LP | 0.146 | 0.202 | 0.909 | 0.138
$n_{1}=10^{4}$, $p_{1}=10^{-4}$, $q_{1}=0.0018$ | LBDC | 0.992 | 0.215 | 0.940 | 0.145
$\beta\approx 0.1$, $\gamma\approx 4\cdot 10^{5}$ | LP | 1.327 | 0.297 | 0.857 | 0.256
$n_{1}=10^{5}$, $p_{1}=10^{-5}$, $q_{1}=0.00018$ | LBDC | 19.585 | 0.250 | 0.950 | 0.166
$\beta\approx 0.1$, $\gamma\approx 4\cdot 10^{6}$ | LP | 30.285 | 0.300 | 0.865 | 0.225
$n_{1}=10^{3}$, $p_{1}=4\cdot 10^{-3}$, $q_{1}=0.012$ | LBDC | 1.249 | 0.506 | 0.503 | 0.763
$\beta\approx 0.4$, $\gamma\approx 4\cdot 10^{4}$ | LP | 1.329 | 0.597 | 0.445 | 0.785

We now compare the LocBipartDC and LP algorithms’ performance on graphs
generated from the SBM with different values of $n_{1},p_{1}$ and $q_{1}$. As
shown in Table 6.1, LocBipartDC not only runs faster, but also produces better
clusters with respect to all three metrics. Secondly, since the clustering
task becomes more challenging when the target clusters have higher
$\beta$-value, we compare the algorithms’ performance on a sequence of
instances with increasing value of $\beta$. Since
$q_{1}/p_{1}=2(1-\beta)/\beta$, we simply fix the values of $n_{1},p_{1}$ as
$n_{1}=1,000,p_{1}=0.001$, and generate graphs with increasing value of
$q_{1}/p_{1}$; this gives us graphs with monotone values of $\beta$. As shown
in Figure 6.7(a), the performance of our algorithm is always better than the
previous state-of-the-art.

Thirdly, notice that both algorithms use some parameters to control the
algorithm’s runtime and the output’s approximation ratio, which are naturally
influenced by each other. To study this dependency, we generate graphs
according to $n_{1}=100,000$, $p_{1}=0.000015$, and $q_{1}=0.00027$ which
results in target sets with $\beta\approx 0.1$ and volume $\gamma\approx
6,000,000$. Figure 6.7(b) shows that, in comparison with the previous state-
of-the-art, LocBipartDC takes much less time to produce output with the same
ARI value.

(a)

(b)

Figure 6.7:  (a) The ARI value of each algorithm when varying the target
$\beta$-value. A higher $q_{1}/p_{1}$ ratio corresponds to a lower
$\beta$-value. (b) The ARI value of each algorithm when bounding the runtime
of the algorithm.

###### Experiments on the real-world dataset.

We further demonstrate the significance of our algorithm on the Interstate
Disputes Dataset (v3.1) [MJK+19], which records every interstate dispute
during 1816–2010, including the level of hostility resulting from the dispute
and the number of casualties, and has been widely studied in the social and
political sciences [MMR02, MMT08] as well as the machine learning community
[HRC17, ME11, TB09]. For a given time period, we construct a graph from the
data by representing each country with a vertex and adding an edge between
each pair of countries weighted according to the severity of any military
disputes between those countries. Specifically, if there’s a war111A war is
defined by the maintainers of the dataset as a series of battles resulting in
at least 1,000 deaths.  between the two countries, the corresponding two
vertices are connected by an edge with weight $30$; for any other dispute that
is not part of an interstate war, the two corresponding vertices are connected
by an edge with weight $1$. We always use the USA as the starting vertex of
the algorithm, and the algorithm’s output, as visualised in Figure 6.1, can be
well explained by geopolitics. The $\beta$-values of the pairs of clusters in
Figures 6.1 are $0.361$, $0.356$, $0.170$ and $0.191$ respectively.

####  6.3.2 Results for Directed Graphs

Next we evaluate the performance of our algorithm for directed graphs on
synthetic and real-world datasets. Since there are no previous local directed
graph clustering algorithms that achieve similar objectives, we compare the
output of Algorithm 4 (ECD) with the state-of-the-art non-local algorithm
proposed by Cucuringu et al. [CLSZ20], and we refer this to as CLSZ in the
following.

###### Synthetic dataset.

Let us first look at the cyclic block model (CBM) described in Cucuringu et
al. [CLSZ20] with parameters $k$, $n$, $p$, $q$, and $\eta$. In this model, we
generate a directed graph with $k$ clusters ${C}_{1},\ldots,{C}_{k}$ of size
$n$, and for $u,v\in{C}_{i}$, there is an edge between $u$ and $v$ with
probability $p$ and the edge direction is chosen uniformly at random. For
$u\in{C}_{i}$ and $v\in{C}_{i+1\mod k}$, there is an edge between $u$ and $v$
with probability $q$, and the edge is directed from $u$ to $v$ with
probability $\eta$ and from $v$ to $u$ with probability $1-\eta$. Throughout
our experiments, we fix $p=0.001$, $q=0.01$, and $\eta=0.9$.

Secondly, since the goal of our algorithm is to find local structure in a
graph, we extend the cyclic block model with additional local clusters and
refer to this model as CBM+. In addition to the parameters of the CBM, we
introduce the parameters $n^{\prime},q^{\prime}_{1},q^{\prime}_{2}$, and
$\eta^{\prime}$. In this model, the clusters ${C}_{1}$ to ${C}_{k}$ are
generated as in the CBM, and there are two additional clusters ${C}_{k+1}$ and