# Spectral Clustering Oracles in Sublinear Time

Grzegorz Gluch
EPFL  Michael Kapralov
EPFL  Silvio Lattanzi
Google Research  Aida Mousavifar
EPFL  Christian Sohler
University of Cologne 111Work was partially done while author was visiting
researcher at Google Research, Switzerland

###### Abstract

Given a graph $G$ that can be partitioned into $k$ disjoint expanders with
outer conductance upper bounded by $\epsilon\ll 1$, can we efficiently
construct a small space data structure that allows quickly classifying
vertices of $G$ according to the expander (cluster) they belong to? Formally,
we would like an efficient local computation algorithm that misclassifies at
most an $O(\epsilon)$ fraction of vertices in every expander. We refer to such
a data structure as a _spectral clustering oracle_.

Our main result is a spectral clustering oracle with query time
$O^{*}(n^{1/2+O(\epsilon)})$ and preprocessing time
$2^{O(\frac{1}{\epsilon}k^{4}\log^{2}(k))}n^{1/2+O(\epsilon)}$ that provides
misclassification error $O(\epsilon\log k)$ per cluster for any $\epsilon\ll
1/\log k$. More generally, query time can be reduced at the expense of
increasing the preprocessing time appropriately (as long as the product is
about $n^{1+O(\epsilon)}$) – this in particular gives a nearly linear time
spectral clustering primitive.

The main technical contribution is a sublinear time oracle that provides dot
product access to the spectral embedding of $G$ by estimating distributions of
short random walks from vertices in $G$. The distributions themselves provide
a poor approximation to the spectral embedding, but we show that an
appropriate linear transformation can be used to achieve high precision dot
product access. We give an estimator for this linear transformation and
analyze it using spectral perturbation bounds and a novel upper bound on the
leverage scores of the spectral embedding matrix of a $k$-clusterable graph.
We then show that dot product access to the spectral embedding is sufficient
to design a clustering oracle. At a high level our approach amounts to
hyperplane partitioning in the spectral embedding of $G$, but crucially
operates on a nested sequence of carefully defined subspaces in the spectral
embedding to achieve per cluster recovery guarantees.

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
  3. 3 Technical overview
    1. 3.1 Sublinear time dot product access to the spectral embedding
    2. 3.2 Geometry of the spectral embedding
      1. 3.2.1 Hard instance for natural hyperplane partitioning
      2. 3.2.2 Our hyperplane partitioning scheme
  4. 4 Properties of the spectral embedding of $(k,\varphi,\epsilon)$-clusterable graphs
    1. 4.1 Standard bounds on cluster means and directional variance
    2. 4.2 Strong Tail Bounds on the Spectral Embedding
    3. 4.3 Centers are strongly orthogonal
    4. 4.4 Robustness property of $(k,\varphi,\epsilon)$-clusterable graphs
  5. 5 A spectral dot product oracle
    1. 5.1 The spectral dot product oracle - overview
    2. 5.2 Stability bounds for the low rank approximation
    3. 5.3 Stability bounds under sampling of vertices
    4. 5.4 Stability bounds under approximations of columns by random walks
    5. 5.5 Proof of Theorem 2
    6. 5.6 Computing approximate norms and spectral dot products (Proof of Theorem 6)
  6. 6 The main algorithm and its analysis
    1. 6.1 The Algorithm (Partitioning Scheme, Algorithm 7)
    2. 6.2 Bounding intersections of $C_{\mu_{i},\theta}$ with true clusters $C_{i}$
    3. 6.3 Partitioning scheme works with exact cluster means & dot products
    4. 6.4 Finding the cluster means
      1. 6.4.1 Quality of cluster means approximation
      2. 6.4.2 Approximate Centers are strongly orthogonal
    5. 6.5 Partitioning scheme works with approximate cluster means & dot products
    6. 6.6 LCA

##  1 Introduction

As a central problem in unsupervised learning, graph clustering has been
extensively studied in the past decades. Several formalizations of the problem
have been considered in the literature. In this paper, we focus on the
following (informal) variant of graph clustering: Given a graph $G$ and an
integer $k$, we are interested in finding $k$ nonoverlapping sets
$C_{1},C_{2},\dots,C_{k}$ that are internally well-connected and that have a
sparse cut to the outside. A popular approach to this problem is spectral
clustering [KVV04, NJW02, SM00, VL07]: One embeds vertices of the graph into
$k$ dimensional Euclidean space using the bottom $k$ eigenvectors of the
Laplacian, and clusters the points in Euclidean space using the $k$-means
algorithm (in practice), or using a more careful space partitioning approach
(in theory). Spectral clustering has been applied in the context of a wide
variety of problems, for example, image segmentation [SM00], speech separation
[BJ06], clustering of protein sequences [PCS06], and predicting landslides in
geophysics [BMD+15]. Spectral clustering usually requires to process the graph
in two steps. First one computes the spectral embedding and then one clusters
the resulting point set. This two stage approach seems to be highly non-local
and it seems to be hard to obtain faster methods, if one only has to determine
the cluster membership for a small subset of the vertices. However, such a
sublinear time access is desirable in some applications. As a basic step
towards such a sublinear time clustering algorithm, we need a way to quickly
access the spectral embedding in some way. Therefore, we ask the following
question, where we use $f_{x}\in\mathbb{R}^{k}$ to denote the spectral
embedding of vertex $x$:

Is it possible to obtain dot product access to the spectral embedding of a
graph in sublinear time? In other words, given a pair of vertices $x,y\in V$,
can we quickly approximate the dot product $\langle f_{x},f_{y}\rangle$ in
$o(n)$ time?

If such access is possible, it appears plausible that one can design a
sublinear spectral clustering oracle, a small space data structure that
provides fast query access to a good clustering of the graph. Our main result
in this paper is (a) a small space data structure that provides query access
to dot products in the spectral embedding, as above, and (b) a sublinear time
spectral clustering oracle that uses this data structure.

We study a popular version of the spectral clustering problem where one
assumes the existence of a planted solution, namely that the input graph can
be partitioned into clusters $C_{1},\ldots,C_{k}$ whose internal connectivity
is nontrivially higher than the external connectivity. The goal is to recover
the clusters approximately. An average case version of this problem, where the
clusters induce Erdős-Rényi graphs (or random regular graphs), and the edges
across clusters are similarly random, has been studied extensively in the
literature on the stochastic block model (SBM) [Abb18] for its close
relationship to the community detection problem. In this work we study a
worst-case version of this problem:

Given a graph $G=(V,E)$ that admits a partitioning into a disjoint union of
$k$ induced expanders $C_{1},\ldots,C_{k}$ with outer conductance bounded by
$\epsilon\ll 1$, output an approximation to $C_{1},\ldots,C_{k}$ that is
correct up to a $O(\epsilon)$ error on every cluster.

We define a spectral clustering oracle with per cluster error $\delta\in(0,1)$
as a small space data structure that implicitly defines disjoint subsets
$\widehat{C}_{1},\ldots,\widehat{C}_{k}$ of $V$ such that for some permutation
$\pi$ on $k$ elements one has
$|C_{i}\Delta\widehat{C}_{\pi(i)}|\leq\delta|C_{i}|$ for every $i=1,\ldots,k$.
The oracle must provide fast query access to such a clustering. The focus of
this paper is:

Design a sublinear time spectral clustering oracle with per cluster error
$\approx O(\epsilon)$.

Our main result is a spectral clustering oracle as above, with a slight loss
in error parameter. Specifically, our spectral clustering oracle is correct up
to $O(\epsilon\log k)$ error on every cluster:

######  Theorem 1 (Informal).

There exists a spectral clustering oracle that for every graph $G=(V,E)$ that
admits a partitioning into a disjoint union of $k$ induced expanders
$C_{1},\ldots,C_{k}$ with outer conductance bounded by
$\epsilon\ll\frac{1}{\log k}$ achieves error $O(\epsilon\log k)$ per cluster,
query time $\approx n^{1/2+O(\epsilon)}$, preprocessing time $\approx
2^{O(\frac{1}{\epsilon}k^{4}\log^{2}(k))}n^{1/2+O(\epsilon)}$ and space
$\approx n^{1/2+O(\epsilon)}$.

Query times can be made faster at the expense of increased space and
prepropcessing time, as long as the product of query time and preprocessing
time is $\approx n^{1+O(\epsilon)}$, leading in particular to a nearly linear
time algorithm for spectral clustering.

As byproduct of our main result we also obtain new efficient clustering
algorithms in the Local Computation Algorithms (LCA) model (see [RTVX11] for
introduction of the model and [ARVX12] for LCA with limited randomness).

A very important feature of the problem above is the fact that our algorithms
recovers a $1-O(\epsilon\log k)$ fraction of every cluster as opposed to just
classifying a $1-O(\epsilon\log k)$ fraction of vertices of the graph
correctly (this latter question allows one to output fewer than $k$ clusters,
and is much easier to solve). To put this in perspective, it is instructive to
apply multiway Cheeger inequalities (e.g., [LGT14], [CKCLL+13]) to our
setting, noting that the $k$-th eigenvalue $\lambda_{k}$ of the normalized
Laplacian of a graph that can be partitioned into $k$ clusters as above is
bounded by $O(\epsilon)$. This means that multiway Cheeger inequalities can be
used to recover $k$ clusters with outer conductance $k^{2}\sqrt{\epsilon}$
(see [LGT14]), which becomes trivial unless $\epsilon<1/k^{4}$ (we note that
our problem admits a much simpler solution when $\epsilon\ll 1/k$). One may
note that multiway Cheeger inequalities can also recover $0.9k$ clusters with
outer conductance $\log^{O(1)}k\sqrt{\epsilon}$ in our setting (e.q.
[LRTV12]), but, as mentioned above, recovering most clusters is much easier
that recovering each cluster to $1\pm O(\epsilon)$ multiplicative error, and
does not solve our problem. The most relevant prior result is due to Sinop
[Sin16], where the author achieves error $O(\sqrt{\epsilon})$ per cluster
using spectral techniques. Sinop’s result improves up on previous work of
[AS12], which achieved per cluster error of $O(\epsilon k)$ (or, rather, is
somewhat incomparable to [AS12] due to the worst dependence on $\epsilon$, but
a lack of dependence on $k$). As we argue below, Sinop’s techniques are hard
to extend to the sublinear time regime. At the same time, one should note that
our result improves on [AS12] under the assumption that cluster sizes are
comparable while using only sublinear time in the size of the input graph.

##### Main challenges and comparison to results on testing cluster structure.

This problem is related the well-studied expansion testing problem [KS08,
NS10, GR11, CS10, KPS13], which corresponds to the setting of one or two
clusters, as well as to the problem of testing cluster structure of graphs,
where one essentially wants to determine $k$, the number of clusters in $G$.
The problem of testing cluster structure has recently been considered in the
literature [CPS15, CKK+18]: given access to a graph $G$ as above, compute the
value of $k$ (in fact, both results [CPS15] and [CKK+18] apply to the harder
property testing problem of distinguishing between graphs that are
$k$-clusterable according to the definition above and graphs that are
$\epsilon$-far from $k$-clusterable, but a procedure for computing $k$ is the
centerpiece of both results). It is interesting to note that the work of
[CPS15] also yields an algorithm for our problem, but only under very strong
assumptions on the outer conductance of the clusters (one needs
$\epsilon\ll\frac{1}{\text{poly}(k)\log n}$). The recent work of Peng [Pen20]
considers a robust version of testing cluster structure, but requires
$\epsilon\ll\frac{1}{\text{poly}(k)\log n}$, just like the work of [CPS15].

The recent work of [CKK+18] on testing cluster structure yields an optimal
tester, which works for any $\epsilon$ smaller than a constant and achieves
essentially optimal runtime, but unfortunately their techniques do no extend
to the ‘learning’ version of the problem. The reason is very simple: the
algorithm of [CKK+18] needs to distinguish between the graph $G$ being a union
of $k$ clusters and $k+1$ clusters, and their approach amounts to verifying
whether a graph can be partitioned into $k$ clusters. To do so it suffices to
check whether the spectral embedding is effectively $k$-dimensional, i.e.
whether it spans a nontrivial $(k+1)$-dimensional volume. In order to certify
this, however, it suffices to exhibit $k+1$ vertices that span a nontrivial
$(k+1)$-dimensional volume. For that, one essentially only needs to locate at
least one ‘typical’ point in every cluster, which is much easier than our task
of correctly recovering almost all, i.e. a $1-O(\epsilon)$ fraction of
vertices in every cluster. In other words, testing graph cluster structure
requires only a rather basic access to and control of the spectral embedding.
The main technical contribution of our paper is a set of tools for getting
precise dot product access to this embedding, together with several new
structural claims about it that enable our clustering algorithm.

##### Comparison to the work of Sinop [Sin16].

The work of Sinop [Sin16] gives a nearly linear time algorithm for recovering
every cluster up to error of $1\pm O(\sqrt{\epsilon})$ using spectral
techniques222One must note that the work of [Sin16] does not require the
bounded degree assumption, and can handle clusters of significantly different
size., for sufficiently small $\epsilon$. The algorithm would be very hard to
implement in sublinear time, since one of its central tools (the Round
procedure, which controls propagation of error i.e., Lemma 5.4 of [Sin16])
heavily relies on the ability to have explicit access to the
eigendecomposition of the Laplacian. Specifically, Sinop’s algorithm first
finds a crude approximation $S$ to a cluster to be recovered, and then
improves the approximation by explicitly constructing the corresponding
submatrix of the spectral embedding and performing an SVD. One could plausibly
envision implementing this using random walks, but that would be challenging,
since one would need to consider a random walk induced on a rather
unstructured subset of vertices of the graph.

##### Our contributions: sublinear time access to the spectral embedding.

Let $G=(V,E)$ be a $d$-regular graph with $n=|V|$. Without loss of generality
we assume that $V=\\{1,\ldots,n\\}$. We assume that $n$ and $d$ are given to
the algorithm and that we have oracle access to $G$: We can specify a vertex
$x\in V$ and a number $i,1\leq i\leq d$, and we will be given in constant time
the $i$-th neighbor of $x$. This is also called the bounded degree graph
model.

In this paper we will consider $d$-regular graphs that have a certain cluster
structure. We parameterize this cluster structure using the internal and
external conductance parameters.

######  Definition 1 (Internal and external conductance).

Let $G=(V,E)$ be a graph. For a set $S\subseteq C\subseteq V$, let
$E(S,C\setminus S)$ be the set of edges with one endpoint in $S$ and the other
in $C\setminus S$. The conductance of a set $S$ within $C$ is
$\phi^{G}_{C}(S)=\frac{|E(S,C\setminus S)|}{d|S|}$. The external-conductance
of set $C$ is defined to be $\phi^{G}_{V}(C)=\frac{|E(C,V\setminus
C)|}{d|C|}$. The internal-conductance of set $C\subseteq V$, denoted by
$\phi^{G}(C)$, is

$\min_{S\subseteq C\text{,}0<|S|\leq\frac{|C|}{2}}\phi^{G}_{C}(S)$

if $|C|>1$ and one otherwise.

######  Remark 1.

For simplicity we present all the proofs for $d$-regular graphs, even though
all the proofs also work for $d$-bounded graphs, with the same definition of
conductance as in Definition 1 (i.e., with normalization by $d|S|$ as opposed
to the volume of $S$; the two notions of conductance can in the worst case
differ by a factor of $d$). Note that this is equivalent to converting a
$d$-bounded degree graph $G$ to a $d$-regular graph $G^{\text{reg}}$ by adding
$d-\text{deg}(v)$ self-loops to each vertex $v$ with degree $\text{deg}(v)$.
Let $L^{\text{reg}}$ be the normalized Laplacian of $G^{\text{reg}}$. Then the
random walk on graph $G$ is exactly same as a lazy random walk on graph
$G^{\text{reg}}$ and the definition of conductance is consistent.

Based on the conductance, clusterability of graphs is defined as follows.

######  Definition 2 ($(k,\varphi,\epsilon)$-clustering).

Let $G=(V,E)$ be a $d$-regular graph. A $(k,\varphi,\epsilon)$-clustering of
$G$ is a partition of vertices $V$ into disjoint subsets $C_{1}\cup\ldots\cup
C_{k}$ such that for all $i\in[k]$, $\phi^{G}(C_{i})\geq\varphi$,
$\phi^{G}_{V}(C_{i})\leq\epsilon$ and for all $i,j\in[k]$ one has
$\frac{|C_{i}|}{|C_{j}|}\in O(1)$. $G$ is called
$(k,\varphi,\epsilon)$-clusterable if there exists a
$(k,\varphi,\epsilon)$-clustering for $G$.

We also need for formally define spectral embedding.

######  Definition 3 (Spectral embedding).

For a $d$-regular graph $G=(V,E)$ and integer $2\leq k\leq n$ we define the
spectral embedding of $G$ as follows. Let $U\in\mathbb{R}^{k\times n}$ denote
the matrix of the bottom $k$ eigenvectors of the normalized Laplacian of $G$
(this choice is not unique; fix any such matrix $U$). Then for every $x\in V$
the spectral embedding $f_{x}\in\mathbb{R}^{k}$ of $x$ is the $x$-th column of
the matrix $U$, which we write as $U=(f_{y})_{y\in V}$.

######  Remark 2.

We note that the spectral embedding $f_{x},x\in V$ is not uniquely defined.
However, in this paper we are only interested in obtaining dot product access
to this embedding, i.e. in fast algorithms for computing $\langle
f_{x},f_{y}\rangle$ for $x,y\in V$. Such dot products are in fact uniquely
defined for any $G$ that is $(k,\varphi,\epsilon)$-clusterable with
$\epsilon/\varphi^{2}$ smaller than an absolute constant – see Remark 4 below.

Our first algorithmic result is a sublinear time spectral dot product oracle:

######  Theorem 2.

[Spectral Dot Product Oracle] Let $\epsilon,\varphi\in(0,1)$ with
$\epsilon\leq\frac{\varphi^{2}}{10^{5}}$. Let $G=(V,E)$ be a $d$-regular graph
that admits a $(k,\varphi,\epsilon)$-clustering $C_{1},\dots,C_{k}$. Let
$\frac{1}{n^{5}}<\xi<1$. Then InitializeOracle($G,1/2,\xi$) (Algorithm 4)
computes in time $(\frac{k}{\xi})^{O(1)}\cdot
n^{1/2+O(\epsilon/\varphi^{2})}\cdot(\log n)^{3}\cdot\frac{1}{\varphi^{2}}$ a
sublinear space data structure $\mathcal{D}$ of size
$(\frac{k}{\xi})^{O(1)}\cdot n^{1/2+O(\epsilon/\varphi^{2})}\cdot(\log n)^{3}$
such that with probability at least $1-n^{-100}$ the following property is
satisfied:

For every pair of vertices $x,y\in V$,
SpectralDotProduct($G,x,y,1/2,\xi,\mathcal{D}$) (Algorithm 5) computes an
output value $\left\langle f_{x},f_{y}\right\rangle_{\scriptscriptstyle apx}$
such that with probability at least $1-n^{-100}$

$\left|\ \left\langle f_{x},f_{y}\right\rangle_{\scriptscriptstyle
apx}-\langle f_{x},f_{y}\rangle\right|\leq\frac{\xi}{n}.$

The running time of SpectralDotProduct($G,x,y,1/2,\xi,\mathcal{D}$) is
$(\frac{k}{\xi})^{O(1)}\cdot n^{1/2+O(\epsilon/\varphi^{2})}\cdot(\log
n)^{2}\cdot\frac{1}{\varphi^{2}}$.

Furthermore, for any $0\leq\delta\leq 1/2$, one can obtain the following
trade-offs between preprocessing time and query time: Algorithm
SpectralDotProduct($G,x,y,\delta,\xi,\mathcal{D}$) requires
$(\frac{k}{\xi})^{O(1)}\cdot n^{\delta+O(\epsilon/\varphi^{2})}\cdot(\log
n)^{2}\cdot\frac{1}{\varphi^{2}}$ per query when the prepressing time of
Algorithm InitializeOracle($G,\delta,\xi$) is increased to
$(\frac{k}{\xi})^{O(1)}\cdot n^{1-\delta+O(\epsilon/\varphi^{2})}\cdot(\log
n)^{3}\cdot\frac{1}{\varphi^{2}}$.

##### Our results: a spectral clustering oracle.

Our goal is to compute a data structure that provides sublinear time access to
a $(k,\varphi,\epsilon)$-clustering of $G$. Such a data structure is called a
$(k,\varphi,\epsilon)$-clustering oracle. We now formally define a spectral
clustering oracle in the Local Computation (LCA) model:

######  Definition 4 (Spectral clustering oracle).

A randomized algorithm $\mathcal{O}$ is a $(k,\varphi,\epsilon)$-clustering
oracle if, when given query access to a $d$-regular graph $G=(V,E)$ that
admits a $(k,\varphi,\epsilon)$-clustering $C_{1},\ldots,C_{k}$, the algorithm
$\mathcal{O}$ provides consistent query access to a partition
$\widehat{P}=(\widehat{C}_{1},\ldots,\widehat{C}_{k})$ of $V$. The partition
$\widehat{P}$ is determined solely by $G$ and the algorithm’s random seed.
Moreover, with probability at least $9/10$ over the random bits of
$\mathcal{O}$ the partition $\widehat{P}$ has the following property: for some
permutation $\pi$ on $k$ elements one has for every $i\in[k]$:

$|C_{i}\triangle\widehat{C}_{\pi(i)}|\leq
O\left(\frac{\epsilon\cdot\log(k)}{\varphi^{3}}\right)|C_{i}|\text{.}$

######  Remark 3.

Note that it is crucial that $\mathcal{O}$ provides consistent answers, i.e.
classifies a given $x\in V$ in the same way every time it is queried (for a
fixing of its random seed).

We are interested in clustering oracles that perform few probes per query. Our
main contribution is:

######  Theorem 3.

For every integer $k\geq 2$, every $\varphi\in(0,1)$, every
$\epsilon\ll\frac{\varphi^{3}}{\log k}$, every $\delta\in(0,1/2]$ there exists
a $(k,\varphi,\epsilon)$-clustering oracle that:

  * •

has
$\widetilde{O}_{\varphi}\left(2^{O\left(\frac{\varphi^{2}}{\epsilon}k^{4}\log^{2}(k)\right)}\cdot
n^{1-\delta+O(\epsilon/\varphi^{2})}\right)$ preprocessing time,

  * •

has $\widetilde{O}_{\varphi}\left(\left(\frac{k}{\epsilon}\right)^{O(1)}\cdot
n^{\delta+O(\epsilon/\varphi^{2})}\right)$ query time,

  * •

uses $\widetilde{O}_{\varphi}\left(\left(\frac{k}{\epsilon}\right)^{O(1)}\cdot
n^{1-\delta+O(\epsilon/\varphi^{2})}\right)$ space,

  * •

uses $\widetilde{O}_{\varphi}\left(\left(\frac{k}{\epsilon}\right)^{O(1)}\cdot
n^{O(\epsilon/\varphi^{2})}\right)$ random bits,

where $O_{\varphi}$ suppresses dependence on $\varphi$ and $\widetilde{O}$
hides all $\operatorname{polylog}(n)$ factors.

To the best of our knowledge, our algorithm is the first sublinear spectral
clustering algorithm in literature. We hope that our main technique for
providing sublinear time access to the spectral embedding will have further
applications in sublinear time spectral graph theory. Our simple algorithm for
recovering clusters using hyperplane partitioning in a carefully defined
sequence of subspaces may also be of independent interest in spectral
partitioning problems. We provide a detailed overview of the analysis and the
main ideas are involved in Section 3.

##### Other related work.

Besides the work on property testing and the work on clustering with labelled,
data another closely related area is local clustering. In local clustering one
is interested of finding the entire cluster around a node $v$ in time
proportional to the size of the cluster. Several algorithms are known for this
problem [ACL08, AGPT16, OA14, ST14, ALM13] but unfortunately they cannot be
applied to solve our problem because when the clusters have linear size they
take linear time (in addition, the output clusters may overlap). In this paper
instead we focus on solving the problem using strictly sublinear time.

##  2 Preliminaries

In this paper we mostly use the matrix notation to represent graphs. For a
vertex $x\in V$, we say that $\mathds{1}_{x}\in\mathbb{R}^{n}$ is the
indicator of $x$, that is, the vector which is $1$ at index $x$ and $0$
elsewhere. For a (multi) set $I_{S}=\\{x_{1},\ldots,x_{s}\\}$ of vertices from
$V$ we abuse notation and also denote by $S$ the $n\times s$ matrix whose
$i^{\text{\tiny{th}}}$ column is $\mathds{1}_{x_{i}}$. For $i\in\mathbb{N}$ we
use $[i]$ to denote the set $\\{1,2,\dots,i\\}$.

For a symmetric matrix $A$, we write $\nu_{i}(A)$ (resp.
$\nu_{\max}(A),\nu_{\min}(A))$ to denote the $i^{\text{th}}$ largest (resp.
maximum, minimum) eigenvalue of $A$.

Let $m\leq n$ be integers. For any matrix $A\in\mathbb{R}^{n\times m}$ with
singular value decomposition (SVD) $A=Y\Gamma Z^{T}$ we assume
$Y\in\mathbb{R}^{n\times n}$, $\Gamma\in\mathbb{R}^{n\times n}$ is a diagonal
matrix of singular values and $Z\in\mathbb{R}^{m\times n}$ (this is a slightly
non-standard definition of the SVD, but having $\Gamma$ be a square matrix
will be convenient). $Y$ has orthonormal columns, the first $m$ columns of $Z$
are orthonormal, and the rest of the columns of $Z$ are zero. For any integer
$q\in[m]$ we denote $Y_{[q]}\in\mathbb{R}^{n\times q}$ as the first $q$
columns of $Y$ and $Y_{-[q]}$ to denote the matrix of the remaining columns of
$Y$. We also denote by $Z_{[q]}\in\mathbb{R}^{m\times q}$ as the first $q$
columns of $Z$ and $Z_{-[q]}$ to denote the matrix of the remaining $n-q$
columns of $Z$. Finally we denote by $\Gamma_{[q]}\in\mathbb{R}^{q\times q}$
the submatrix of $\Gamma$ corresponding to the first $q$ rows and columns of
$\Gamma$ and we use $\Gamma_{-[q]}$ to denote the submatrix corresponding to
the last $n-q$ rows and $n-q$ columns of $\Gamma$. So for any $q\in[m]$ the
span of $Y_{-[q]}$ is the orthogonal complement of the span of $Y_{[q]}$ in
$\mathbb{R}^{n}$, also the span of the columns of $Z_{-[q]}$ is the orthogonal
complement of the span of $Z_{[q]}$ in $\mathbb{R}^{m}$. Thus we can write
$A=Y_{[q]}\Gamma_{[q]}Z^{T}_{[q]}+Y_{-[q]}\Gamma_{-[q]}Z^{T}_{-[q]}$.

We also denote with $A_{G}$ the adjacency matrix of $G$ and with $L$ the
normalized Laplacian of $G$ where $L=I-\frac{A_{G}}{d}$. For $L$ we denote its
eigenvalues with $0\leq\lambda_{1}\leq\ldots\leq\lambda_{n}\leq 2$ and we
write $\Lambda$ to refer to the diagonal matrix of these eigenvalues in
ascending order. We also denote with $(u_{1},\ldots,u_{n})$ an orthonormal
basis of eigenvectors of $L$ and with $U\in\mathbb{R}^{n\times n}$ the matrix
whose columns are the orthonormal eigenvectors of $L$ arranged in increasing
order of eigenvalues. Therefore the eigendecomposition of $L$ is $L=U\Lambda
U^{T}$. We write $U_{[k]}\in\mathbb{R}^{n\times k}$ for the matrix whose
columns are the first $k$ columns of $U$ and also define $F=U_{[k]}^{T}$. For
every vertex $x$ we denote the spectral embedding of vertex $x$ on the bottom
$k$ eigenvectors of $L$ with $f_{x}\in\mathbb{R}^{k}$, i.e.
$f_{x}=F\mathds{1}_{x}$. For pairs of vertices $x,y\in V$ we use the notation

$\langle f_{x},f_{y}\rangle:=f_{x}^{T}f_{y}$

to denote the dot product in the embedded domain.

######  Remark 4.

We note that if $G$ is a $(k,\varphi,\epsilon)$-clusterable graph with
$\epsilon/\varphi^{2}$ smaller than a constant, the space spanned by the
bottom $k$ eigenvectors of the normalized Laplacian of $G$ is uniquely
defined, i.e. the choice of $U_{[k]}$ is unique up to multiplication by an
orthonormal matrix $R\in\mathbb{R}^{k\times k}$ on the right. Indeed, by Lemma
3 below one has $\lambda_{k}\leq 2\epsilon$ and by Lemma 1 below one has
$\lambda_{k+1}\geq\varphi^{2}/2$. Thus, since we assume that
$\epsilon/\varphi^{2}$ is smaller than an absolute constant, we have
$2\epsilon<\varphi^{2}/2$, and therefore the subspace spanned by the bottom
$k$ eigenvectors of the Laplacian, i.e. the space of $U_{[k]}$, is uniquely
defined, as required. We note that while the choice of $f_{x}$ for $x\in V$ is
not unique, but the dot product between the spectral embedding of $x\in V$ and
$y\in V$ is well defined, since for every orthonormal $R\in\mathbb{R}^{k\times
k}$ one has $\langle
Rf_{x},Rf_{y}\rangle=(Rf_{x})^{T}(Rf_{y})=f_{x}^{T}(R^{T}R)f_{y}=f_{x}^{T}f_{y}.$

In this paper we also consider the transition matrix of the random walk
associated with $G$ $M=\frac{1}{2}\cdot\left(I+\frac{A}{d}\right)$. From any
vertex $v$, this random walk takes every edge incident to $v$ with probability
$\frac{1}{2d}$, and stays on $v$ with the remaining probability which is at
least $\frac{1}{2}$. Note that this random walk is exactly same as a lazy
random walk on $G$ and that $M=I-\frac{L}{2}$. Observe that $\forall i$
$u_{i}$ is also an eigenvector of $M$, with eigenvalue
$1-\frac{\lambda_{i}}{2}$. We denote with $\Sigma$ the diagonal matrix of the
eigenvalues of $M$ in descending order. Therefore the eigendecomposition of
$M$ is $M=U\Sigma U^{T}$. We write $\Sigma_{[k]}\in\mathbb{R}^{k\times k}$ for
the matrix whose columns are the first $k$ rows and columns of $\Sigma$.
Furthermore, for any $t$, $M^{t}$ is a transition matrix of random walks of
length $t$. For any vertex $x$, we denote the probability distribution of a
$t$-step random walk starting from $x$ by $m_{x}=M^{t}\mathds{1}_{x}$. For a
(multi) set $I_{S}=\\{x_{1},\ldots,x_{s}\\}$ of vertices from $V$, let matrix
$M^{t}S\in\mathbb{R}^{n\times s}$ is a matrix whose columns are probability
distributions of $t$-step random walks starting from vertices in $I_{S}$. More
formally the $i$th column of $M^{t}S$ is $m_{x_{i}}$. For any vertex $x\in V$
let $\mathcal{N}(x):\\{y\in V:\\{x,y\\}\in E\\}$ denote the set of vertices
that are adjacent to the vertex $x$.

######  Definition 5 (Cluster Centers).

Let $G=(V,E)$ be a $d$-regular graph. Let $C_{1},\ldots,C_{k}$ be a
$(k,\varphi,\epsilon)$-clustering of $G$. We define the _spectral center_ of
cluster $C_{i}$ as

$\mu_{i}:=\frac{1}{|C_{i}|}\sum_{x\in C_{i}}f_{x}\text{.}$

For vertex $x\in V$, we define $\mu_{x}$ as the cluster center of the cluster
which $x$ belongs to.

In our analysis we use the following standard results on eigenvalues and
matrix norms. Recall that for any $m\times n$ matrix $A$, the multi-sets of
nonzero eigenvalues of $AA^{\top}$ and $A^{\top}A$ are equal.

######  Lemma 1 ([CKK+18]).

Let $G$ be any graph which is composed of $k$ components $C_{1},\ldots C_{k}$
such that $\phi^{G}(C_{i})\geq\varphi$ for any $i\in[k]$. Let $L$ be the
normalized Laplacian matrix of $G$, and $\lambda_{k+1}$ be the $(k+1)$st
smallest eigenvalue of $L$. Then $\lambda_{k+1}\geq\frac{\varphi^{2}}{2}$.

For a $d$-regular graph $G$, let $\rho_{G}(k)$ denote the minimum value of the
maximum conductance over any possible $k$ disjoint nonempty subsets. That is

$\rho_{G}(k)\leq\min_{\text{disjoint
}S_{1},\ldots,S_{k}}\max_{i}\phi_{G}(S_{i})$

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

For any $d$-regular graph $G$ and any $k\geq 2$, it holds that

$\lambda_{k}\leq 2\rho_{G}(k)\text{.}$

######  Lemma 3.

Let $G=(V,E)$ be a $d$ regular graph that admits a
$(k,\varphi,\epsilon)$-clustering $C_{1},\ldots,C_{k}$. Let $L$ be the
normalized Laplacian matrix of $G$. Let $\lambda_{1}\leq\ldots\leq\lambda_{n}$
be eigenvalues of $L$, then we have $\lambda_{k+1}\geq\frac{\varphi^{2}}{2}$
and $\lambda_{k}\leq 2\epsilon$.

###### Proof.

Note that $G$ is composed of $k$ components $C_{1},\ldots C_{k}$ such that for
all $1\leq i\leq k$ we have $\phi^{G}(C_{i})\geq\varphi$. Hence, by Lemma 1 we
get $\lambda_{k+1}\geq\frac{\varphi^{2}}{2}\text{.}$ Moreover for all $1\leq
i\leq k$, we have $\phi^{G}_{V}(C_{i})\leq\epsilon$. Thus by Lemma 2 we have
$\lambda_{k}\leq 2\epsilon\text{.}$ ∎

Since we assume that the maximum ratio of cluster sizes is bounded by a
constant, we have

######  Proposition 1.

Let $G=(V,E)$ be a $d$ regular graph that admits a
$(k,\varphi,\epsilon)$-clustering $C_{1},\ldots,C_{k}$. Then we have
$\min_{i\in\\{1,\ldots,k\\}}|C_{i}|=\Omega\left(\frac{n}{k}\right)$ and
$\max_{i\in\\{1,\ldots,k\\}}|C_{i}|=O\left(\frac{n}{k}\right)$.

A symmetric $n\times n$ matrix is positive semi-definite, if and only if all
its eigenvalues are non-negative. The spectral norm of matrix
$A\in\mathbb{R}^{n\times n}$ is defined as
$\max_{x\in\mathbb{R}^{n},x\not=0}\frac{\|Ax\|_{2}}{\|x\|_{2}}$ that equals
the square root of the largest eigenvalue of the matrix $A^{T}A$. The
Frobenius norm of a matrix $A$ is defined as $\sqrt{\sum_{i,j}(A_{i,j})^{2}}$.
For matrices $A,\widetilde{A}\in\mathbb{R}^{n\times n}$, we write
$A\preccurlyeq\widetilde{A}$, if $\forall x\in\mathbb{R}^{n}$ we have
$x^{T}Ax\leq x^{T}\widetilde{A}x$.

##  3 Technical overview

In this section we give an overview of the analysis and the main technical
contributions of the paper. Recall that we denote the matrix of bottom $k$
eigenvectors of the normalized Laplacian of $G$ by $U_{[k]}$. The spectral
embedding of a vertex $x\in V$, denoted by $f_{x}\in\mathbb{R}^{k}$, is simply
the $x$-th column of $U_{[k]}^{T}$. The main intuition behind spectral
clustering is that the points $f_{x}\in\mathbb{R}^{k}$ are well-concentrated
around cluster means $\mu_{i}\in\mathbb{R}^{k}$, defined for every
$i=1,\ldots,k$ by

$\mu_{i}=\frac{1}{|C_{i}|}\sum_{x\in C_{i}}f_{x}.$ (1)

See Fig. 1 for an illustration.

$\mu_{1}$$\mu_{2}$$\mu_{3}$$C_{1}$$C_{2}$$C_{3}$ Figure 1:  Example of a
spectral embedding where points are concentrated around means.

The contributions of our paper are twofold. Our first contribution is a
primitive that provides dot product access to the spectral embedding of a
graph in sublinear time: we show in Theorem 2 how, given any pair of vertices
$x,y\in V$ one can compute

$\langle f_{x},f_{y}\rangle_{apx}\approx\langle f_{x},f_{y}\rangle,$ (2)

in time $\approx n^{1/2+O(\epsilon)}$ per evaluation (see Algorithm 5 in
Section 5 for the formal definition of $\langle\cdot,\cdot\rangle_{apx}$ and
its analysis).

Our second contribution is to show how dot product access as in (2) above
allows one to solve the cluster recovery problem. Both of these contributions
are based on a new property of the spectral embedding that we establish. This
property allows us to quantify the intuitive statement that vertices in the
embedding concentrate around cluster means defined in (2) above in a very
strong formal sense.

In the rest of this section we first present our sublinear time dot product
oracle (in Section 3.1) and then outline how access to such an oracle can be
used to design a simple spectral clustering algorithm (in Section 3.2). We
assume that the inner conductance of the clusters $\varphi$ is constant for
the purposes of this overview to simplify notation.

###  3.1 Sublinear time dot product access to the spectral embedding

We start with a description of the main underlying ideas underlying the proof
of Theorem 2. Our starting point from earlier work is the observation that
collision statistics of random walks can be used to exhibit the structure of a
$(k,\varphi,\epsilon)$-clusterable graph. In particular, in
$(k,\varphi,\epsilon)$-clusterable graphs, there is a gap between
$\lambda_{k}$ and $\lambda_{k+1}$, and the behavior of random walks is
essentially determined by the bottom $k$ eigenvectors of the Laplacian and the
corresponding eigenvalues. This suggests that we can potentially use random
walks to determine the spectral embedding. The spectral embedding is of course
not necessarily unique (for example, if not all of the bottom $k$ eigenvalues
are unique). However, the dot product of the embedded vertices is still well-
defined as a function of the subspace spanned by the bottom $k$ eigenvectors
of the Laplacian, as the subspace itself is uniquely defined because of the
aforementioned gap between $\lambda_{k}$ and $\lambda_{k+1}$. See Remark 4 for
more details. We now give an overview of our approach.

Fix two vertices $x,y\in V$. We would like to compute

$\langle
f_{x},f_{y}\rangle=(F\mathds{1}_{x})^{T}(F\mathds{1}_{y})=\mathds{1}_{x}^{T}U_{[k]}U_{[k]}^{T}\mathds{1}_{y}.$

The direct approach to this would amount to computing an eigendecomposition of
$M$ to obtain $U_{[k]}$, but that would take at least $\Omega(n)$ time and is
too expensive for our purposes. On the other hand, it is well-known that we
are able to estimate, in about $n^{1/2}$ time, the dot product

$(M^{t}\mathds{1}_{x})^{T}(M^{t}\mathds{1}_{y})=\mathds{1}_{x}^{T}M^{2t}\mathds{1}_{y}.$

Note that
$\mathds{1}_{x}^{T}M^{2t}\mathds{1}_{y}=\mathds{1}_{x}^{T}U\Sigma^{2t}U^{T}\mathds{1}_{y}$.
Thus to get $U_{[k]}U_{[k]}^{T}$ from $\mathds{1}_{x}^{T}M^{2t}\mathds{1}_{y}$
we need to remove the matrix $\Sigma^{2t}$ from the middle. Specifically, we
can estimate the quantity above as follows. For some precision parameter
$\xi\in(0,1)$ we first run $\approx n^{1/2+O(\epsilon/\varphi^{2})}/\xi^{2}$
random walks from $x$, letting $\widehat{m}_{x}\in\mathbb{R}^{n}$ denote a
vector whose $a$’th component is the fraction of random walks from $x$ that
end up at $a$. Similarly, we run $\approx
n^{1/2+O(\epsilon/\varphi^{2})}/\xi^{2}$ random walks from $y$, letting
$\widehat{m}_{y}\in\mathbb{R}^{n}$ denote a vector whose $a$’th component is
the fraction of random walks from $y$ that end up at $a$. One can show333This
calculation is mostly amounts to a rather standard collision counting
calculation that relies on the birthday paradox if one wants to establish the
claim for most vertices $x,y\in V$ (this was done in [CPS15] and [CKK+18] for
example). Our new moment bounds for the spectral embedding (see Lemmas 4 and 5
in Section 4) allow us to establish such a claim for all vertices $x,y\in V$ –
see Lemma 22. that with high (constant) probability we have

$\left|\widehat{m}_{x}^{T}\widehat{m}_{y}-\mathds{1}_{x}^{T}M^{2t}\mathds{1}_{y}\right|\leq\xi\cdot\frac{1}{n}.$
(3)

While (3) is not directly useful, a primitive for constructing empirical
distributions $\widehat{m}_{x}$ and $\widehat{m}_{y}$ as above is a central
part of our approach. We formalize it as Algorithm 1 (RunRandomWalks) below:

Algorithm 1 RunRandomWalks($G,R,t,x$)

1:Run $R$ random walks of length $t$ starting from $x$

2:Let $\widehat{m}_{x}(y)$ be the fraction of random walks that ends at $y$
$\triangleright$ vector $\widehat{m}_{x}$ has support at most $R$

3:return $\widehat{m}_{x}$

Even if we cannot apply (3) directly, it lets us compute a seemingly related
to quantity $\mathds{1}_{x}^{T}M^{2t}\mathds{1}_{y}$ quickly by invoking
Algorithm 1 and computing one dot product. In order to get from
$\mathds{1}_{x}^{T}M^{2t}\mathds{1}_{y}$ to
$\mathds{1}_{x}^{T}U_{[k]}U_{[k]}^{T}\mathds{1}_{y}$, we need to somehow apply
a linear transformation on the random walk distributions before computing the
dot product between them, i.e. we need a different dot product operation. It
is easy to see that the correct linear transformation is given by the matrix
$U_{[k]}{\Sigma}_{[k]}^{-2t}U_{[k]}^{T}$, where $M^{t}=U\Sigma^{t}U^{T}$ is
the eigendecomposition of $M$ and $U_{[k]}$ stands for the matrix of bottom
$k$ eigenvectors of the Laplacian444Note that this matrix is not well defined
in the presence of repeated eigenvectors, but any fixed choice of this matrix
suffices for our purposes. It is also interesting to note that while we use a
canonical choice of the eigendecomposition of $M$ throughout the paper, all
our bounds are oblivious to the choice of this basis, and hold for the
subspace of bottom $k$ eigenvectors, which is well defined since there is a
gap between the $k$-th and $(k+1)$-th eigenvalues in $k$-clusterable graphs..
Specifically, we have

$(M^{t}\mathds{1}_{x})^{T}(U_{[k]}{\Sigma}_{[k]}^{-2t}U_{[k]}^{T})(M^{t}\mathds{1}_{y})=\mathds{1}_{x}^{T}U_{[k]}U_{[k]}^{T}\mathds{1}_{y}=\langle
f_{x},f_{y}\rangle,$

which is exactly the quantity we are interested in. Of course, there is a
major problem with this approach, since
$U_{[k]}{\Sigma}_{[k]}^{-2t}U_{[k]}^{T}$ is an $n\times n$ matrix! To get
around this issue, we approximate $U_{[k]}{\Sigma}_{[k]}^{-2t}U_{[k]}^{T}$ by
a sparse low rank matrix, as we describe below. Specifically, we let $I_{S}$
be a multiset of $s\ll n$ vertices selected uniformly at random. Let $S$ be
the $n\times s$ matrix whose $j$-th column equals $\mathds{1}_{i_{j}}$ and let
$\widetilde{W}\widetilde{\Sigma}^{2t}\widetilde{W}^{T}$ denote the
eigendecomposition of $\frac{n}{s}\cdot(M^{t}S)^{T}(M^{t}S)$555We abuse
notation somewhat by writing $S$ to denote the $n\times s$ matrix whose
$(a,j)$-th entry equals $1$ if the $j$-th sampled vertex equals $a$ and $0$
otherwise.. We show that with an appropriate choice of the sampling parameter
$s\ll n$ one has

$U_{[k]}{\Sigma}_{[k]}^{-2t}U_{[k]}^{T}\approx
M^{t}S\cdot\widetilde{\Psi}\cdot S^{T}M^{t},$ (4)

where

$\widetilde{\Psi}=\frac{n}{s}\cdot\widetilde{W}_{[k]}\widetilde{\Sigma}_{[k]}^{-4t}\widetilde{W}_{[k]}^{T}$
(5)

is an $s\times s$ matrix that can be computed explicitly. The corresponding
primitive to compute $(M^{t}S)^{T}(M^{t}S)$ is presented as Algorithm 2
(EstimateCollisionProbabilities) below. It basically estimates the Gram matrix
of random walk distributions out of $I_{S}$ (denoted by $\mathcal{G}$) by
counting collisions, and taking medians of estimates to reduce failure
probability appropriately. After computing the approximate Gram matrix, we
derive from it the matrix
$\Psi=\frac{n}{s}\cdot\widehat{W}_{[k]}\widehat{\Sigma}_{[k]}^{-2}\widehat{W}_{[k]}^{T}$,
where $\mathcal{G}=\widehat{W}\widehat{\Sigma}\widehat{W}^{T}$ is the
eigendecomposition of $\mathcal{G}$ (see line (8) and line (10) of Algorithm
4; note that $G$ is a symmetric matrix, and hence an eigendecomposition
exists).

Algorithm 2 EstimateCollisionProbabilities($G,I_{S},R,t$)

1:for $i=1$ to $O(\log n)$ do

2: ${\widehat{Q}_{i}}:=\textsc{EstimateTransitionMatrix}(G,I_{S},R,t)$

3: ${\widehat{P}_{i}}:=\textsc{EstimateTransitionMatrix}(G,I_{S},R,t)$

4:
$\mathcal{G}_{i}:=\frac{1}{2}\left(\widehat{P}_{i}^{T}\widehat{Q}_{i}+\widehat{Q}_{i}^{T}\widehat{P}_{i}\right)$
$\triangleright$ $\mathcal{G}_{i}$ is symmetric

5:Let $\mathcal{G}$ be a matrix obtained by taking the entrywise median of
$\mathcal{G}_{i}$’s $\triangleright$ $\mathcal{G}$ is symmetric

6:return $\mathcal{G}$ $\triangleright$ $\mathcal{G}\in\mathbb{R}^{s\times s}$

Algorithm 2 uses an auxiliary primitive presented as

Algorithm 3 EstimateTransitionMatrix$(G,I_{S},R,t)$

1:for each sample $x\in I_{S}$ do

2: $\widehat{m}_{x}:=\textsc{RunRandomWalks}(G,R,t,x)$

3:Let ${\widehat{Q}}$ be the matrix whose columns are $\widehat{m}_{x}$ for
$x\in I_{S}$

4:return $\widehat{Q}$ $\triangleright$ $\widehat{Q}$ has at most $Rs$ non-
zeros

The proof of (4) relies on matrix perturbation bounds (the Davis-Kahan
$\sin\theta$ theorem) as well as spectral concentration inequalities,
crucially coupled with our tail bounds on the spectral embedding (see Lemma 4
and Lemma 5). In particular Lemma 4 and it’s consequence - Lemma 5 can be used
to bound the leverage scores of $U_{[k]}$ (i.e. $||f_{x}||^{2}_{2}$ for $x\in
V$). This part of the analysis is presented in Section 5.2.

######  Lemma 4.

[Tail-bound] Let $\varphi\in(0,1)$ and $\epsilon\leq\frac{\varphi^{2}}{100}$,
and let $G=(V,E)$ be a $d$-regular graph that admits
$(k,\varphi,\epsilon)$-clustering $C_{1},\ldots,C_{k}$. Let $L$ be the
normalized Laplacian of $G$. Let $u$ be a normalized eigenvector of $L$ with
$||u||_{2}=1$ and with eigenvalue at most $2\epsilon$. Then for any $\beta>1$
we have

$\frac{1}{n}\cdot\biggl{|}\left\\{x\in
V:|u(x)|\geq\beta\cdot\sqrt{\frac{10}{\min_{i\in[k]}|C_{i}|}}\right\\}\biggl{|}\leq\left(\frac{\beta}{2}\right)^{-{\varphi^{2}/20\cdot\epsilon}}\text{.}$

######  Lemma 5.

Let $\varphi\in(0,1)$ and $\epsilon\leq\frac{\varphi^{2}}{100}$, and let
$G=(V,E)$ be a $d$-regular graph that admits $(k,\varphi,\epsilon)$-clustering
$C_{1},\ldots,C_{k}$. Let $u$ be a normalized eigenvector of $L$ with
$||u||_{2}=1$ and with eigenvalue at most $2\epsilon$. Then we have

$||u||_{\infty}\leq
n^{20\cdot\epsilon/\varphi^{2}}\cdot\sqrt{\frac{160}{\min_{i\in
k}|C_{i}|}}\text{.}$

We note that the number of samples $s$ is chosen as $s\approx
k^{O(1)}n^{O(\epsilon/\varphi^{2})}$ (see Algorithm 4) , where the second
factor is due to our upper bound on the $\ell_{\infty}$ norm of the bottom $k$
eigenvectors of the Laplacian of a $(k,\varphi,\epsilon)$-clusterable graph
proved in Section 4.

Once we establish (4) in Section 5.3 (see Lemma 19), we get for every $x,y\in
V$

$\begin{split}(M^{t}\mathds{1}_{x})^{T}M^{t}S\cdot\widetilde{\Psi}\cdot
S^{T}M^{t}(M^{t}\mathds{1}_{y})\approx\mathds{1}_{x}^{T}U_{[k]}U_{[k]}^{T}\mathds{1}_{y},\end{split}$
(6)

which is what we would like to compute. One issue remains at this point, which
is that we cannot compute $M^{t}\mathds{1}_{x}$ or $M^{t}\mathds{1}_{y}$
explicitly, and neither can we store and compute our approximation
$M^{t}S\cdot\Psi\cdot S^{T}M^{t}$, since it is a dense, albeit low rank,
matrix. We resolve this problem by running an appropriate number of random
walks out of the sampled nodes $I_{S}$, as well as the queried nodes $x,y\in
V$. Specifically, we run $\approx n^{1/2+O(\epsilon)}$ random walks from every
sampled node in $I_{S}$, defining an $n\times s$ matrix $Q$ whose $(a,b)$-th
entry is the fraction of walks from $a$ that ended at $b$ and using the matrix
$Q$ as a proxy for $M^{t}S$ (note that the expectation of $Q$ is exactly
$M^{t}S$). Such a matrix $Q$ is computed as per line (2) and line (3) of
Algorithm 2 (EstimateCollisionProbabilities). We note that Algorithm 4
(InitializeOracle) performs $O(\log n)$ independent estimates that we
ultimately use to boost confidence (by the median trick). The entire
preprocessing is summarized in Algorithm 4 (InitializeOracle) below:

Algorithm 4 InitializeOracle($G,\delta,\xi$) $\triangleright$ Need:
$\epsilon/\varphi^{2}\leq\frac{1}{10^{5}}$

1:$t:=\frac{20\cdot\log n}{\varphi^{2}}$

2:$R_{\text{init}}:=O{(n^{1-\delta+980\cdot\epsilon/\varphi^{2}}\cdot
k^{17}/{\xi}^{2})}$

3:$s:=O(n^{480\cdot\epsilon/\varphi^{2}}\cdot\log n\cdot k^{8}/{\xi}^{2})$

4:Let $I_{S}$ be the multiset of $s$ indices chosen independently and
uniformly at random from $\\{1,\ldots,n\\}$

5:for $i=1$ to $O(\log n)$ do

6:
${\widehat{Q}_{i}}:=\textsc{EstimateTransitionMatrix}(G,I_{S},R_{\text{init}},t)$
$\triangleright$ $\widehat{Q}_{i}$ has at most $R_{\text{init}}\cdot s$ non-
zeros

7:$\mathcal{G}:=$EstimateCollisionProbabilities$(G,I_{S},R_{\text{init}},t)$

8:Let
$\frac{n}{s}\cdot\mathcal{G}:=\widehat{W}\widehat{\Sigma}\widehat{W}^{T}$ be
the eigendecomposition of $\frac{n}{s}\cdot\mathcal{G}$ $\triangleright$
$\mathcal{G}\in\mathbb{R}^{s\times s}$

9:if $\widehat{\Sigma}^{-1}$ exists then

10:
$\Psi:=\frac{n}{s}\cdot\widehat{W}_{[k]}\widehat{\Sigma}_{[k]}^{-2}\widehat{W}_{[k]}^{T}$
$\triangleright$ $\Psi\in\mathbb{R}^{s\times s}$

11: return $\mathcal{D}:=\\{\Psi,\widehat{Q}_{1},\ldots,\widehat{Q}_{O(\log
n)}\\}$

Equipped with the primitives presented above, we can now state our final dot
product estimate:

$\widehat{m}_{x}^{T}Q\Psi
Q^{T}\widehat{m}_{y}\approx\mathds{1}_{x}^{T}U_{[k]}U_{[k]}^{T}\mathds{1}_{y}=\langle
f_{x},f_{y}\rangle,$ (7)

where $\widehat{m}_{x}$ and $\widehat{m}_{y}$ are empirical distributions of
$\approx n^{1/2+O(\epsilon/\phi^{2})}$ out of $x$ and $y$ respectively, $Q$ is
an $n\times s$ matrix with $\approx n^{1/2+O(\epsilon/\phi^{2})}$ nonzeros per
column, and $\Psi$ is a possibly dense $s\times s$ matrix, where the number of
sampled vertices $s$ is ultimately chosen to be
$k^{O(1)}n^{O(\epsilon/\phi^{2})}$. The analysis of the error incurred in
replacing (4) with (7) is presented in Section 5.4. It relies on a birthday
paradox style variance computation similar to previous sublinear time
algorithms for testing graph cluster structure. The actual query procedure
that implements (7) is given by Algorithm 5 below.

Algorithm 5 SpectralDotProductOracle($G,x,y,\delta,\xi,\mathcal{D}$)
$\triangleright$ Need: $\epsilon/\varphi^{2}\leq\frac{1}{10^{5}}$
$\triangleright$
$\mathcal{D}:=\\{\Psi,\widehat{Q}_{1},\ldots,\widehat{Q}_{O(\log n)}\\}$

1:$R_{\text{query}}:=O{(n^{\delta+500\cdot\epsilon/\varphi^{2}}\cdot
k^{9}/{\xi}^{2})}$

2:for $i=1$ to $O(\log n)$ do

3: ${\widehat{m}^{i}_{x}:=\textsc{RunRandomWalks}(G,R_{\text{query}},t,x)}$

4: ${\widehat{m}^{i}_{y}:=\textsc{RunRandomWalks}(G,R_{\text{query}},t,y)}$

5:Let ${\alpha}_{x}$ be a vector obtained by taking the entrywise median of
$(\widehat{Q}_{i})^{T}(\widehat{m}^{i}_{x})$ over all runs

6:Let ${\alpha}_{y}$ be a vector obtained by taking the entrywise median of
$(\widehat{Q}_{i})^{T}(\widehat{m}^{i}_{y})$ over all runs

7:return $\left\langle f_{x},f_{y}\right\rangle_{\scriptscriptstyle
apx}:={\alpha}_{x}^{T}\Psi{\alpha}_{y}$

##### Trading off preprocessing time for query time.

Finally, we note that one can reduce query time (i.e., runtime of
SpectralDotProductOracle) at the expense of increased preprocessing time and
size of data structure. Specifically, one can run $\approx
n^{\delta+O(\epsilon/\phi^{2})}$ random walks from nodes $x,y$ whose dot
product is being estimated by SpectralDotProductOracle at the expense of
increasing the number of random walks run to generate the matrix $Q$ in
InitializeOracle to $\approx n^{1-\delta+O(\epsilon/\phi^{2})}$, for any
$\delta\leq 1/2$. This in particular leads to a nearly linear time spectral
clustering algorithm.

###  3.2 Geometry of the spectral embedding

We now describe our spectral clustering algorithm. Since we only have dot
product access to the spectral embedding, the algorithm must be very simple.
Indeed, our algorithm amounts to performing hyperplane partitioning in a
sequence of carefully crafted subspaces of the embedding space, using (a good
approximation to) cluster means $\mu_{i}$.

We first present a simple hyperplane partitioning, then we give an example
embedding to show why it might be hard to prove that this scheme works. After
that we design a modification of the hyperplane partitioning scheme that,
through the course of carving, carefully projects out some directions of the
embedding. This modification is an idealized version of our final algorithm
for which we can prove per cluster recovery guarantees.

First we assume that the cluster means (1) are known. In that case we define,
for every $i=1,\ldots,k$, the sets

$\widetilde{C}_{i}:=\\{x\in V:\langle f_{x},\mu_{i}\rangle\geq
0.9||\mu_{i}||^{2}\\}$

of points that are nontrivially correlated with the $i$-th cluster mean
$\mu_{i}$. Note that $\widetilde{C}_{i}=C_{\mu_{i},0.9}$ in terms of
Definition 8, but since $\mu_{i}$’s are fixed in this overview, we use the
simpler notation. We next define, for every $i=1,\ldots,k$,

$\widehat{C}_{i}:=\widetilde{C}_{i}\setminus\bigcup_{j=1}^{i-1}\widetilde{C}_{j}.$
(8)

In other words, this is a natural ‘hyperplane-carving’ approach: points that
belong to the first hyperplane $\widetilde{C}_{1}$ are taken as the first
cluster, points in the second hyperplane $\widetilde{C}_{2}$ that were not
captured by the first hyperplane are taken as the second cluster, etc. This is
a natural high dimensional analog of the Cheeger cut that has been used in
many results on spectral partitioning. The hope here would be to show that
there exists a permutation $\pi$ on $[k]$ such that

$|\widehat{C}_{i}\Delta C_{\pi(i)}|\leq O(\epsilon)\cdot|C_{\pi(i)}|,$ (9)

for every $i=1,\ldots,k$, where we assume that the inner conductance $\phi$ of
the clusters is constant. Here $\Delta$ stands for the symmetric difference
operation.

One natural approach to establishing (9) would be to prove that for every
$i=1,\ldots,k$ vertices $x\in C_{i}$ concentrate well around cluster means
$\mu_{i}$ (see Fig. 1). This would seem to suggest that $\widetilde{C}_{i}$’s
are close to the $C_{i}$’s, and so are the $\widehat{C}_{i}$’s. This property
of the spectral embedding is quite natural to expect, and versions of this
property have been used in the literature. For example, one can show that for
every $\alpha\in\mathbb{R}^{k},||\alpha||_{2}=1$,

$\sum_{i=1}^{k}\sum_{x\in C_{i}}\langle f_{x}-\mu_{i},\alpha\rangle^{2}\leq
O(\epsilon).$ (10)

The bound in (10) follows using rather standard techniques – see Section 4.1
for this and related claims. One can check that (10) suffices to show that
$\widetilde{C}_{i}$’s are very close to $C_{i}$’s, namely that for every
$i=1,\ldots,k$ there exists $j\in[k]$ such that

$|\widetilde{C}_{i}\Delta C_{j}|=O(\epsilon)\cdot|C_{j}|.$ (11)

The formal proof is given in Section 6.2. The result in (11) is encouraging
and suggests that the clusters $\widehat{C}_{i}$ defined by the simple
hyperplane partitioning process approximate the $C_{i}$’s, but this is not the
case! The problem lies in the fact that while $\widetilde{C}_{i}$’s
approximate the $C_{i}$’s well as per (11), the bound in (11) does not
preclude nontrivial overlaps in the $\widetilde{C}_{i}$’s – we give an example
in below.

####  3.2.1 Hard instance for natural hyperplane partitioning

We now give an example configuration of vertices in Euclidean space such that
(a) the configuration does not contradict (10) and (b) the natural hyperplane
partitioning algorithm (8) fails for this configuration. This shows why we
develop a different algorithm that can deal with configurations like the one
presented in this subsection.

Consider the following configuration of $C_{i}$’s and $\mu_{i}$’s. Suppose
that all cluster sizes are equal $\frac{n}{k}$, and let
$k=\frac{1}{\epsilon}$. Let $\mu_{i}$’s form an orthogonal system and for each
$i\in[k]$ let $||\mu_{i}||_{2}=\sqrt{\frac{k}{n}}$. For all $i<k=1/\epsilon$
for all $x\in C_{i}$ we set $f_{x}=\mu_{i}$, that is points from all clusters
except for $1/\epsilon$’th one are tightly concentrated around cluster means –
see Fig. 2 for an illustration with $k=3$. Then for cluster $C_{1/\epsilon}$
we distribute points as follows. For every $i=1,\dots,1/\epsilon-1$ we move
$\epsilon/2$ fraction of its points to $\mu_{1/\epsilon}+\mu_{i}$, and another
$\epsilon/2$ fraction of the points to $\mu_{1/\epsilon}-\mu_{i}$. The
remaining $\epsilon$ fraction of $C_{1/\epsilon}$ stays at $\mu_{1/\epsilon}$.
Now observe that all cluster means are where they should be, since we applied
symmetric perturbations. Secondly notice that (10) is satisfied for every
direction $\alpha$. Intuitively it is the case because we moved $1/\epsilon-1$
disjoint subsets of $C_{1/\epsilon}$ of size $\epsilon\frac{n}{k}$ in
$1/\epsilon-1$ orthogonal directions. Lastly observe what happens to
$\widetilde{C}_{i}$’s. For all $i=1,\dots,1/\epsilon-1$ set
$\widetilde{C}_{i}$ contains $C_{i}$ and $\epsilon/2$ fraction of
$C_{1/\epsilon}$ that was moved in direction $\mu_{i}$. One can verify that
this is perfectly consistent with (10), and in particular with (11). The
problem is that many clusters have large overlap with one particular cluster,
namely $C_{1/\epsilon}$. Indeed notice that the ball carving process returns
$\widehat{C}_{1/\epsilon}$ such that $|\widehat{C}_{1/\epsilon}\cap
C_{1/\epsilon}|=(\frac{1+\epsilon}{2})\frac{n}{k}$. That means that constant
(almost $1/2$) fraction of cluster $C_{1/\epsilon}$ is not recovered!

$\mu_{1}$$\mu_{2}$$\mu_{3}$$C_{1}$$C_{2}$$C_{3}$ Figure 2:  Example of a
spectral embedding that is consistent with (10) and (11) but for which the
natural hyperplane partitioning would not work.

####  3.2.2 Our hyperplane partitioning scheme

The example in Section 3.2.1 suggests that we need to develop a diffferent
algorithm. Our main contribution here is an algorithm that more carefully
deals with the overlaps of $\widetilde{C}_{i}$’s. The high level idea for the
algorithm is to recover clusters in stages and after every stage project out
the directions corresponding to recovered clusters.

First we observe the following property of $(k,\varphi,\epsilon)$-clusterable
graphs (see Lemma 16). Any collection of pairwise disjoint sets with small
outer-conductance matches the original clusters well. More precisely for every
collection $\\{\widehat{C}_{1},\dots,\widehat{C}_{k}\\}$ of pairwise disjoint
sets satisfying for every $i\in[k]$ $\phi(\widehat{C}_{i})\leq
O(\epsilon\log(k))$ there exists a permutation $\pi$ on $[k]$ such that

$|\widehat{C}_{i}\Delta C_{\pi(i)}|\leq O(\epsilon\log(k))\cdot|C_{\pi(i)}|,$
(12)

In the algorithm we will test many candidate clusters and the property above
allows us to test if a particular candidate $\widehat{C}$ is good by only
computing its outer-conductance.

Now we describe our algorithm more formally. The algorithm proceeds in
$O(\log(k))$ stages. In the first stage it considers $k$ candidate clusters
$\widehat{C}_{i}$, where $x\in\widehat{C}_{i}$ if it has big correlation with
$\mu_{i}$ but small correlation with all other $\mu_{j}$’s. More formally

$\widehat{C}_{i}:=\widetilde{C}_{i}\setminus\bigcup_{j\neq
i}\widetilde{C}_{j}\text{,}$ (13)

which is equivalent to:

$\left\langle f_{x},\mu_{i}\right\rangle\geq 0.9||\mu_{i}||^{2}\text{ and for
all }j\neq i\left\langle
f_{x},\mu_{j}\right\rangle<0.9||\mu_{j}||^{2}\text{.}$

Note that by definition all these clusters are disjoint. At this point we
return all candidate clusters $\widehat{C}_{i}$ for which
$\phi(\widehat{C}_{i})\leq O(\epsilon)$, remove the corresponding vertices
from the graph, remove the corresponding $\mu$’s from the set
$\\{\mu_{1},\dots,\mu_{k}\\}$ of centers and proceed to the next stage.

In the next stage we restrict our attention to a lower dimensional subspace
$\Pi$ of $\mathbb{R}^{k}$. Intuitively we want to project out all the
directions corresponding to the removed cluster centers. Formally we define
$\Pi$ to be the subspace orthogonal to all $\mu$’s removed up to this point
(we overload notation by also using $\Pi$ for the orthogonal projection onto
this subspace). We will see that $\mu$’s are close to being orthogonal (see
Lemma 7). This fact means that
$\Pi\approx\text{span}(\\{\mu_{1},\dots,\mu_{b}\\})$, where
$\\{\mu_{1},\dots,\mu_{b}\\}$ is the set of $\mu$’s that were not removed in
the first step. Now the algorithm considers $b$ candidate clusters where the
condition for $x$ being in a cluster $i$ changes to:

$\left\langle f_{x},\Pi\mu_{i}\right\rangle\geq 0.9||\Pi\mu_{i}||^{2}\text{
and for all }j\in[b],j\neq i\left\langle
f_{x},\Pi\mu_{j}\right\rangle<0.9||\Pi\mu_{j}||^{2}\text{.}$

Now we return all candidate clusters that satisfy $\phi(\widehat{C}_{i})\leq
O(\epsilon)$ but this time the constant hidden in the $O$ notation is bigger
than in the first stage. In general at any stage $t$ we change the test to
$O(\epsilon\cdot t)$. At the end of the stage we proceed in a similar fashion
by returning the clusters, removing the corresponding vertices and $\mu$’s and
considering a lower dimensional subspace of $\Pi$ in the next stage.

The algorithm continues in such a fashion for $O(\log(k))$ stages. Thus for
all returned clusters $\widehat{C}_{i}$ it is true that there exists $j$ such
that666Note that this algorithm may not return a partition of the graph but
only a collection of disjoint clusters. Later, in Section 6.6 in Proposition
3, we present a simple reduction that shows that an algorithm that guarantees
(12) is enough to construct a clustering oracle that, as required by
Definition 4, returns a partition. The high level idea is to assign the
remaining vertices to clusters randomly.:

$|\widehat{C}_{i}\triangle C_{j}|\leq
O\left(\epsilon\log(k)\right)\cdot|C_{j}|\text{.}$

Let’s analyze how this algorithm works for the configuration presented in
Section 3.2.1. In the first stage we have that, for all
$i\neq\frac{1}{\epsilon}$, $\widehat{C}_{i}=C_{i}$ and moreover
$|\widehat{C}_{1/\epsilon}\cap
C_{1/\epsilon}|=(\frac{1+\epsilon}{2})\frac{n}{k}$. So all candidate cluster
$\widehat{C}_{i}$ for $i\neq 1/\epsilon$ are returned but crucially this time
(in contrast with the natural hyperplane partitioning) cluster
$C_{1/\epsilon}$ is left untouched. Then directions
$\\{\mu_{1},\dots,\mu_{1/\epsilon-1}\\}$ are projected out. In the second
stage the algorithm considers only vertices from $C_{1/\epsilon}$ projected
onto one dimensional subspace $\text{span}(\mu_{1/\epsilon})$ and recovers
this cluster up to $O(\epsilon)$ error.

Because of the robustness property (12), to show that this algorithm works we
only need to argue that at the end of $O(\log(k))$ stages $k$ sets are
returned. We do that by showing that in every stage at least half of the
remaining clusters is recovered. It is done in Lemma 37 and crucially relies
on the following fact. When the algorithm considers a subspace $\Pi$ then the
number of points in the union of sets:

$\\{x\in V:\left\langle f_{x},\Pi\mu_{i}\right\rangle\geq
0.9||\Pi\mu_{i}||^{2}\\}\cap\\{x\in V:\left\langle
f_{x},\Pi\mu_{j}\right\rangle\geq 0.9||\Pi\mu_{j}||^{2}\\}\text{,}$

for all $i,j\in[b],i\neq j$ is bounded by $O(\epsilon\cdot b\cdot\frac{n}{k})$
(see Lemma 36 and Remark 7). To prove that we observe that every point $x$ in
this intersections has big projection onto some two $\mu_{i},\mu_{j}$ from
$\\{\mu_{1},\dots,\mu_{b}\\}$. Then using the fact that $\mu$’s are close to
being orthogonal we deduce that
$\Pi\approx\text{span}(\\{\mu_{1},\dots,\mu_{b}\\})$ this in particular means
that $\Pi\mu_{i}\approx\mu_{i}$, $\Pi\mu_{j}\approx\mu_{j}$. Because of that
$f_{x}$ is abnormally far (further by a factor of $1/\epsilon$ with respect to
the average) from it’s center $\mu_{x}$. Now applying (10) for an orthonormal
basis of $\Pi$ and summing the inequalities we get that that the number of
points in the intersections is bounded by $O(\epsilon\cdot
b\cdot\frac{n}{k})$. Having this bound we can argue that at least half of the
remaining clusters is recovered as on average only
$O(\epsilon\cdot\frac{n}{k})$ points from each cluster belong to the
intersections. The formal argument is given in Section 6.3.

The use of subspaces is crucial for our approach. If we relied solely on the
bounds on norms (i.e. bounds on $||f_{x}||$) we could only claim a recovery
guarantee of $O(\epsilon k)$ per cluster. One of the reasons is that there can
be $\Theta(\epsilon n)$ vertices of abnormally big norm and all of them can
belong to one cluster (as it happens in the example from Section 3.2.1). The
use of carefully crafted sequence of subspaces solves this issue as it allows
to derive better bounds for the number of abnormal vertices in each stage. It
is possible as we can show that the ”variance of the distribution” of
$f_{x}$’s cannot concentrate on subspaces. This leads to an
$O(\epsilon\log(k))$ error guarantee per cluster.

What remains is to remove the assumption that the cluster means $\mu_{i}$ are
known to the algorithm. We show, using our tail bounds from Lemma 4, that a
random sample of $O(1/\epsilon\cdot k^{3}\log k)$ points in every cluster is
likely to concentrate around the mean. This allows us to take a
$O(1/\epsilon\cdot k^{4}\log k)$ size sample of points, guess in exponential
(in $1/\epsilon\cdot k^{4}\log^{2}k$) time which points belong to which
cluster, and ultimately find surrogates $\widehat{\mu}_{i}$ that are
sufficiently close to the actual $\mu_{i}$’s for the analysis to go through.
This part of the analysis is presented in Section 6.4.1. We also need a
mechanism for testing if a set of approximate $\widehat{\mu}$’s induces (via
our partitioning algorithm) a good clustering. We accomplish this goal by
designing a simple sampling based tester that determines whether or not the
clusters induced by a particular collection of candidate cluster means have
the right size and outer conductance properties. See Section 6.5 for this part
of the analysis.

To design our spectral clustering algorithm we need to perform tests like
$\left\langle
f_{x},\Pi\mu\right\rangle\stackrel{{\scriptstyle?}}{{\geq}}0.9||\Pi\mu||_{2}^{2}$
for a given vertex $x$, a candidate cluster mean $\mu$, and the projection
matrix $\Pi$. Hence, we need tools to approximate $\left\langle
f_{x},\Pi\mu\right\rangle$ and $||\Pi\mu||_{2}^{2}$. As explained above,
instead of exact cluster means i.e. $\mu$ we will perform the test for
approximate cluster means i.e, $\widehat{\mu}=\frac{1}{|S|}\sum_{y\in
S}f_{y}$, where $S$ is a small subset $S$ of sampled nodes. First observe that
for any vertex $x$ one can estimate $\left\langle
f_{x},\widehat{\mu}\right\rangle_{\scriptscriptstyle apx}$ as follows:

$\left\langle f_{x},\widehat{\mu}\right\rangle_{\scriptscriptstyle
apx}=\frac{1}{|S|}\sum_{y\in S}\left\langle
f_{x},f_{y}\right\rangle_{\scriptscriptstyle apx}$

where $\left\langle f_{x},f_{y}\right\rangle_{\scriptscriptstyle apx}$ can be
computed using (SpectralDotProductOracle) Algorithm 5. Next we will explain
how to compute $\left\langle
f_{x},\widehat{\Pi}f_{y}\right\rangle_{\scriptscriptstyle apx}$ for $x,y\in
V$. Recall that $\widehat{\Pi}$ is the subspace orthogonal to all
$\widehat{\mu}$’s removed so far. Let
$\\{\widehat{\mu}_{1},\ldots,\widehat{\mu}_{r}\\}$ denote the set of removed
cluster means, and let $X\in\mathbb{R}^{k\times r}$ denote a matrix whose
columns are $\widehat{\mu}_{i}$’s. Therefore the projection matrix onto the
span of $\\{\widehat{\mu}_{1},\ldots,\widehat{\mu}_{r}\\}$ is given by
$X(X^{T}X)^{-1}X$. Hence, we have $\widehat{\Pi}=I-X(X^{T}X)^{-1}X$ and we can
compute $\left\langle
f_{x},\widehat{\Pi}f_{y}\right\rangle_{\scriptscriptstyle apx}$ as follows:

$\left\langle f_{x},\widehat{\Pi}f_{y}\right\rangle_{\scriptscriptstyle
apx}=\left\langle f_{x},f_{y}\right\rangle_{\scriptscriptstyle
apx}-(f_{x}^{T}X)(X^{T}X)^{-1}(Xf_{y})\text{.}$

Note that the $i$-th column of matrix $X$ is $\widehat{\mu}_{i}$, thus
$f_{x}^{T}X\in\mathbb{R}^{r}$ is a vector whose $i$-th entry can be computed
by $\left\langle f_{x},\widehat{\mu}_{i}\right\rangle_{\scriptscriptstyle
apx}$. Moreover notice that $X^{T}X\in\mathbb{R}^{r\times r}$ is matrix such
that its $(i,j)$-th entry can be computed by
$\left\langle\widehat{\mu}_{i},\widehat{\mu}_{j}\right\rangle_{\scriptscriptstyle
apx}$. Therefore $(f_{x}^{T}X)$, $(Xf_{y})$ and $(X^{T}X)^{-1}$ all can be
computed explicitly which let us compute $\left\langle
f_{x},\widehat{\Pi}f_{y}\right\rangle_{\scriptscriptstyle apx}$. Given the
primitive to compute $\left\langle
f_{x},\widehat{\Pi}f_{y}\right\rangle_{\scriptscriptstyle apx}$ we are able to
estimate $\left\langle f_{x},\Pi(\mu)\right\rangle$ and $||\Pi(\mu)||_{2}^{2}$
as follows:

$\left\langle
f_{x},\widehat{\Pi}\widehat{\mu}\right\rangle_{\scriptscriptstyle
apx}:=\frac{1}{|B|}\cdot\sum_{y\in B}\left\langle
f_{x},\widehat{\Pi}f_{y}\right\rangle_{\scriptscriptstyle apx}\text{,}$
$\left\lVert\widehat{\Pi}\widehat{\mu}\right\rVert_{\scriptscriptstyle
apx}^{2}:=\frac{1}{|B|}\cdot\sum_{x\in B}\left\langle
f_{x},\widehat{\Pi}\widehat{\mu}\right\rangle_{\scriptscriptstyle
apx}\text{.}$

This part of the analysis is presented in Section 5.6.

##  4 Properties of the spectral embedding of
$(k,\varphi,\epsilon)$-clusterable graphs

In this section we study the spectral embedding of
$(k,\varphi,\epsilon)$-clusterable graphs. Recall that the spectral embedding
maps every vertex $x\in V$ to a $k$-dimensional vector $f_{x}$. We are
interested in understanding the geometric properties of this embedding. We
start by recalling some standard properties of the embedding: We show that the
cluster means

$\mu_{i}=\frac{1}{|C_{i}|}\sum_{x\in C_{i}}f_{x}$

are almost orthogonal and of length roughly $1/\sqrt{|C_{i}|}$ (Lemma 7
below). Then we give a bound on the directional variance, by which we mean the
sum of squared distances of points $f_{x}$ to their corresponding cluster
centers when projected on direction $\alpha$. We show in Lemma 6 below that
the directional variance is bounded by $O(\epsilon/\varphi^{2})$ for every
direction $\alpha\in\mathbb{R}^{k},\|\alpha\|=1$. This in particular implies
(see Lemma 9 below) that ‘rounding’ the spectral embedding by mapping each
vertex to its corresponding cluster center results in a matrix $U$ that
spectrally approximates the matrix of bottom $k$ eigenvectors of the
Laplacian. These bounds are rather standard, and their proofs are provided for
completeness. The main shortcoming of the standard bounds is that they can
only allow us to apply averaging arguments, and are thus unable to rule out
that some of the embedded points are quite far away from their corresponding
cluster center. For example, they do not rule out the possibility of an
$\Omega(1/k)$ fraction of the points being $\approx\sqrt{k}$ further away from
their corresponding centers. Since we would like to recover every cluster to
up an $O(\epsilon)$ error, such bounds are not sufficient on their own.

For this reason we consider the distribution of the projection of the embedded
points on the direction of any of the first $k$ eigenvectors and we give
stronger tail bounds for these distributions (in Lemma 4) than what follows
from variance calculations only. Basically, we give a strong bound on the
$O(\varphi^{2}/\epsilon)$-th moment of the spectral embedding as opposed to
just on the second moment, as above. These higher moment bounds are then
crucially used to achieve sublinear time access to dot products in the
embedded space in Section 5 (we need them to establish spectral concentration
of a small number of random samples in Section 5.2) as well as to argue that a
small sample of vertices contains a good approximation to the true cluster
means $\mu_{i},i=1,\ldots,k$ in its span in Section 6.4.1.

###  4.1 Standard bounds on cluster means and directional variance

The lemma below bounds the variance of the spectral embedding in any
direction.

######  Lemma 6.

(Variance bounds) Let $k\geq 2$ be an integer, $\varphi\in(0,1)$, and
$\epsilon\in(0,1)$. Let $G=(V,E)$ be a $d$-regular graph that admits
$(k,\varphi,\epsilon)$-clustering $C_{1},\ldots,C_{k}$. Then for all
$\alpha\in\mathbb{R}^{k}$, with $\|\alpha\|=1$ we have

$\sum_{i=1}^{k}\sum_{x\in C_{i}}\left\langle
f_{x}-\mu_{i},\alpha\right\rangle^{2}\leq\frac{4\epsilon}{\varphi^{2}}.$

###### Proof.

For each $i\in[k]$, and any vertex $x\in C_{i}$, let $d_{i}(x)$ denote the
degree of vertex $x$ in the subgraph $C_{i}$. Let $H_{i}$ be a graph obtained
by adding $d-d_{i}(x)$ self-loops to each vertex $x\in C_{i}$. Let $L$ denote
the normalized Laplacian of graph $G$. For each $i\in[k]$ and let $L_{i}$
denote the normalized Laplacian of $H_{i}$, and let $\lambda_{2}({H_{i}})$ be
the second smallest eigenvalue of $L_{i}$.

Let $z=U_{[k]}\alpha$. Note that $||z||_{2}=1$. By Lemma 3 we have
$\lambda_{1}\leq\ldots\leq\lambda_{k}\leq 2\epsilon$, where $\lambda_{i}$ is
the $i^{\text{th}}$ smallest eigenvalue of of $L$. Therefore we have

$\langle z,Lz\rangle\leq\lambda_{k}\leq 2\epsilon$ (14)

Fix some $i\in[k]$, let $z^{\prime}\in\mathbb{R}^{n}$ be a vector such that
$z^{\prime}(x):=z(x)-\langle\mu_{i},\alpha\rangle$. For any $S\subseteq V$, we
define $z^{\prime}_{S}\in\mathbb{R}^{n}$ to be a vector such that for all
$x\in V$ $z^{\prime}_{S}(x)=z^{\prime}(x)$ if $x\in S$ and
$z^{\prime}_{S}(x)=0$ otherwise. Note that $z(x)=\left\langle
f_{x},\alpha\right\rangle$, thus we have

$\sum_{x\in V}z^{\prime}_{C_{i}}(x)=\sum_{x\in C_{i}}z^{\prime}(x)=\sum_{x\in
C_{i}}z(x)-\left\langle\mu_{i},\alpha\right\rangle=\sum_{x\in
C_{i}}\left\langle f_{x}-\mu_{i},\alpha\right\rangle=0$

Thus we have $z^{\prime}_{C_{i}}\perp\mathds{1}$, so by properties of Rayleigh
quotient we get

$\frac{\langle z^{\prime}_{C_{i}},L_{i}z^{\prime}_{C_{i}}\rangle}{\langle
z^{\prime}_{C_{i}},z^{\prime}_{C_{i}}\rangle}=\frac{1}{d}\frac{\sum_{x,y\in
C_{i},(x,y)\in E}(z^{\prime}(x)-z^{\prime}(y))^{2}}{\sum_{x\in
C_{i}}(z^{\prime}(x))^{2}}=\frac{1}{d}\frac{\sum_{x,y\in C_{i},(x,y)\in
E}(z(x)-z(y))^{2}}{\sum_{x\in
C_{i}}(z(x)-\langle\mu_{i},\alpha\rangle)^{2}}\geq\lambda_{2}({H_{i}})$ (15)

Furthermore, by Cheeger’s inequality for any $i\in[k]$ we have
$\lambda_{2}(H_{i})\geq\frac{\varphi^{2}}{2}$. Hence, for any $i\in[k]$ we
have

$\frac{\sum_{x,y\in C_{i},(x,y)\in E}(z(x)-z(y))^{2}}{d\sum_{x\in
C_{i}}(z(x)-\langle\mu_{i},\alpha\rangle)^{2}}\geq\lambda_{2}({H_{i}})\geq\frac{\varphi^{2}}{2}$

Now observe the following:

$\displaystyle 2\epsilon$ $\displaystyle\geq\langle z,Lz\rangle$ By (14)
$\displaystyle=\frac{1}{d}\cdot\sum_{(x,y)\in E}(z(x)-z(y))^{2}$
$\displaystyle\geq\frac{1}{d}\cdot\sum_{i=1}^{k}\sum_{x,y\in C_{i},(x,y)\in
E}(z(x)-z(y))^{2}$
$\displaystyle\geq\frac{\varphi^{2}}{2}\cdot\sum_{i=1}^{k}\sum_{x\in
C_{i}}(z(x)-\langle\mu_{i},\alpha\rangle)^{2}$ By (15)

Recall that for all $x\in V$, $z(x)=\left\langle f_{x},\alpha\right\rangle$.
Therefore for for any $\alpha\in\mathbb{R}^{k}$ with $\|\alpha\|=1$ we have

$\sum_{i=1}^{k}\sum_{x\in C_{i}}\langle
f_{x}-\mu_{i},\alpha\rangle^{2}\leq\frac{4\epsilon}{\varphi^{2}}$

∎

The following lemma shows that the length of the cluster mean of cluster
$C_{i}$ is roughly $1/\sqrt{|C_{i}|}$ and that cluster means are almost
orthogonal.

######  Lemma 7.

(Cluster means) Let $k\geq 2$ be an integer, $\varphi\in(0,1)$, and
$\epsilon\in(0,1)$. Let $G=(V,E)$ be a $d$-regular graph that admits
$(k,\varphi,\epsilon)$-clustering $C_{1},\ldots,C_{k}$. Then we have

  1. 1.

$\text{ for all }i\in[k]$,
$\left|||\mu_{i}||_{2}^{2}-\frac{1}{|C_{i}|}\right|\leq\frac{4\sqrt{\epsilon}}{\varphi}\frac{1}{|C_{i}|}$

  2. 2.

$\text{ for all }i\neq j\in[k]$,
$\left|\langle\mu_{i},\mu_{j}\rangle\right|\leq\frac{8\sqrt{\epsilon}}{\varphi}\frac{1}{\sqrt{|C_{i}\|C_{j}|}}$

To prove Lemma 7 we need Lemma 9 in which we will use the following result
from [HJ90] (Theorem 1.3.20 on page 53).

######  Lemma 8 ([HJ90]).

Let $h,m,n$ be integers such that $1\leq h\leq m\leq n$. For any matrix
$A\in\mathbb{R}^{m\times n}$ and matrix $B\in\mathbb{R}^{n\times m}$, the
multisets of nonzero eigenvalues of $AB$ and $BA$ are equal. In particular, if
one of $AB$ and $BA$ is positive semidefinite, then $\nu_{h}(AB)=\nu_{h}(BA)$.

######  Lemma 9.

Let $k\geq 2$ be an integer, $\varphi\in(0,1)$, and $\epsilon\in(0,1)$. Let
$G=(V,E)$ be a $d$-regular graph that admits $(k,\varphi,\epsilon)$-clustering
$C_{1},\ldots,C_{k}$. Let $H\in\mathbb{R}^{k\times k}$ be a matrix whose
$i$-th column is $\mu_{i}$. Let $W\in\mathbb{R}^{k\times k}$ be a diagonal
matrix such that $W(i,i)=\sqrt{|C_{i}|}$. Then for any
$\alpha\in\mathbb{R}^{k}$, $\|\alpha\|=1$, we have

  1. 1.

$|\alpha^{T}\left((HW)(HW)^{T}-I\right)\alpha|\leq\frac{4\sqrt{\epsilon}}{\varphi}$

  2. 2.

$|\alpha^{T}\left((HW)^{T}(HW)-I\right)\alpha|\leq\frac{4\sqrt{\epsilon}}{\varphi}$

###### Proof.

Proof of item (1): Let $Y\in\mathbb{R}^{k\times n}$ denote a matrix whose
$x$-th column is $\mu_{x}$ for any $x\in V$. Note that

$YY^{T}=\sum_{i=1}^{k}|C_{i}|\mu_{i}\mu_{i}^{T}=(HW)(HW)^{T}\text{.}$

We define $\widetilde{z}:=Y^{T}\alpha$, and $z:=U_{[k]}\alpha$. Note that
$U_{[k]}^{T}U_{[k]}=I$. Therefore we have

$\displaystyle|\alpha^{T}\left((HW)(HW)^{T}-I\right)\alpha|$
$\displaystyle=|\alpha^{T}(YY^{T}-U_{[k]}^{T}U_{[k]})\alpha|$
$\displaystyle=\left|\sum_{x\in V}\widetilde{z}(x)^{2}-z(x)^{2}\right|$ From
definition of $z(x)$ and $\widetilde{z}(x)$ $\displaystyle=\left|\sum_{x\in
V}\left(z(x)-\widetilde{z}(x)\right)\left(z(x)+\widetilde{z}(x)\right)\right|$
$\displaystyle\leq\sqrt{\sum_{x\in V}(z(x)-\widetilde{z}(x))^{2}\sum_{x\in
V}(\widetilde{z}(x)+z(x))^{2}}$ By Cauchy-Schwarz inequality (16)

Note that for any $x\in V$, we have $z(x)=\left\langle
f_{x},\alpha\right\rangle$ and
$\widetilde{z}(x)=\left\langle\mu_{x},\alpha\right\rangle$. Therefore by Lemma
6 we have

$\sqrt{\sum_{x\in V}(z(x)-\widetilde{z}(x))^{2}}=\sqrt{\sum_{x\in
V}\left\langle
f_{x}-\mu_{x},\alpha\right\rangle^{2}}\leq\frac{2\sqrt{\epsilon}}{\varphi}$
(17)

To complete the proof it suffices to show that $\sum_{x\in
V}(\tilde{z}(x)+z(x))^{2}\leq 4$. Note that

$\displaystyle\sum_{x\in V}\tilde{z}(x)^{2}$ $\displaystyle=\sum_{x\in
V}\left\langle\alpha,\mu_{x}\right\rangle^{2}$
$\displaystyle=\sum_{i}|C_{i}|\left\langle\alpha,\frac{\sum_{x\in
C_{i}}f_{x}}{|C_{i}|}\right\rangle^{2}$
$\displaystyle=\sum_{i}|C_{i}|\left(\frac{\sum_{x\in
C_{i}}\left\langle\alpha,f_{x}\right\rangle}{|C_{i}|}\right)^{2}$
$\displaystyle\leq\sum_{i}\sum_{x\in
C_{i}}\left\langle\alpha,f_{x}\right\rangle^{2}$ By Jensen’s inequality
$\displaystyle=\sum_{x\in V}z(x)^{2}$

Thus we have

$\sum_{x\in V}(\tilde{z}(x)+z(x))^{2}\leq\sum_{x\in
V}2(\tilde{z}(x)^{2}+z(x)^{2})\leq 2+2\sum_{x\in V}\tilde{z}(x)^{2}\leq 4$
(18)

In the first inequality we used the fact that $(\tilde{z}(x)-z(x))^{2}\geq 0$
and for the second inequality we used the fact that
$||z||_{2}^{2}=||U_{[k]}\alpha||_{2}^{2}=1$. Putting (18), (17), and (16)
together we get

$|\alpha^{T}\left((HW)(HW)^{T}-I\right)\alpha|\leq\frac{4\sqrt{\epsilon}}{\varphi}\text{.}$

Proof of item (2): Note that by item (2) for any vector $\alpha$ with
$||\alpha||_{2}=1$ we have

$1-\frac{4\sqrt{\epsilon}}{\varphi}\leq\alpha^{T}\left((HW)(HW)^{T}\right)\alpha\leq
1+\frac{4\sqrt{\epsilon}}{\varphi}$

Thus by Lemma 8 we have that the set of eigenvalues of $(HW)(HW)^{T}$ and
$(HW)^{T}(HW)$ are the same, and all of the eigenvalues lie in the interval
$[1-\frac{4\sqrt{\epsilon}}{\varphi},1+\frac{4\sqrt{\epsilon}}{\varphi}]$.
Thus for any vector $\alpha$ with $||\alpha||_{2}=1$ we have

$1-\frac{4\sqrt{\epsilon}}{\varphi}\leq\alpha^{T}\left((HW)^{T}(HW)\right)\alpha\leq
1+\frac{4\sqrt{\epsilon}}{\varphi}\text{.}$

∎

Now we are able to prove Lemma 7. See 7

###### Proof.

Proof of item (1): Let $H\in\mathbb{R}^{k\times k}$ be a matrix whose $i$-th
column is $\mu_{i}$. Let $W\in\mathbb{R}^{k\times k}$ be a diagonal matrix
whose such that $W(i,i)=\sqrt{|C_{i}|}$. Thus by Lemma 9 item (2) for any
$\alpha\in\mathbb{R}^{k}$ with $\|\alpha\|=1$, we have

$|\alpha^{T}\left((HW)^{T}(HW)-I\right)\alpha|\leq\frac{4\sqrt{\epsilon}}{\varphi}$

Let $\alpha=\mathds{1}_{i}$. Thus we have

$|((HW)^{T}(HW))(i,i)-1|\leq\frac{4\sqrt{\epsilon}}{\varphi}$ (19)

Note that
$((HW)^{T}(HW))(i,i)=(WH^{T}HW)(i,i)=||\mu_{i}||^{2}_{2}|C_{i}|$.Therefore we
get

$\left|||\mu_{i}||^{2}_{2}-\frac{1}{|C_{i}|}\right|\leq\frac{4\sqrt{\epsilon}}{\varphi}\cdot\frac{1}{|C_{i}|}$

Proof of item (2): Let
$\alpha=\frac{1}{\sqrt{2}}(\mathds{1}_{i}+\mathds{1}_{j})$. Note that
$||\alpha||_{2}=1$. Thus by Lemma 9 item (2) we have

$|\alpha^{T}\left((HW)^{T}(HW)-I\right)\alpha|\leq\frac{4\sqrt{\epsilon}}{\varphi}$

Note that

$\left|\alpha^{T}\left((HW)^{T}(HW)-I\right)\alpha\right|=\left|\frac{1}{2}\left(||\mu_{i}||^{2}_{2}|C_{i}|+||\mu_{j}||^{2}_{2}|C_{j}|+2\left\langle\mu_{i},\mu_{j}\right\rangle\sqrt{|C_{i}||C_{j}|}-2\right)\right|$

Therefore we get

$\left|||\mu_{i}||^{2}_{2}|C_{i}|+||\mu_{j}||^{2}_{2}|C_{j}|+2\left\langle\mu_{i},\mu_{j}\right\rangle\sqrt{|C_{i}||C_{j}|}-2\right|\leq\frac{8\sqrt{\epsilon}}{\varphi}$

Thus

$\displaystyle\left|\left\langle\mu_{i},\mu_{j}\right\rangle\sqrt{|C_{i}||C_{j}|}\right|$
$\displaystyle\leq\left|\frac{1}{2}\left(1-||\mu_{i}||^{2}_{2}|C_{i}|\right)+\frac{1}{2}\left(1-||\mu_{j}||^{2}_{2}|C_{j}|\right)\right|+\frac{4\sqrt{\epsilon}}{\varphi}$
$\displaystyle\leq\frac{1}{2}\cdot\frac{4\sqrt{\epsilon}}{\varphi}+\frac{1}{2}\cdot\frac{4\sqrt{\epsilon}}{\varphi}+\frac{4\sqrt{\epsilon}}{\varphi}$
By item (1) $\displaystyle\leq\frac{8\sqrt{\epsilon}}{\varphi}$

Therefore we get

$\left|\left\langle\mu_{i},\mu_{j}\right\rangle\right|\leq\frac{8\sqrt{\epsilon}}{\varphi}\cdot\frac{1}{\sqrt{|C_{i}||C_{j}|}}\text{.}$

∎

###  4.2 Strong Tail Bounds on the Spectral Embedding

The main results of this section are the following two lemmas. The first lemma
gives an upper bound on the length of the projection of any point $f_{x}$ on
an arbitrary direction $\alpha\in\mathbb{R}^{k}$. The second lemma considers
the distribution of the lengths of projected $f_{x}$ and we get tail bounds
that show that the fraction of points whose projected length exceeds the
‘expectation’ (which is about $1/\sqrt{|C_{i}|}$ for the smallest cluster
$C_{i}$) by a factor of $\beta$ is bounded by
$\beta^{-\varphi^{2}/{10\epsilon}}$. In other words, we bound the
$O(\varphi^{2}/\epsilon)$-th moment as opposed to the second moment, which
gives us tight control over the embedding when $\epsilon/\varphi^{2}\ll 1/\log
k$.

See 5

See 4

We are interested in deriving moment bounds for the distribution of the
entries of the first $k$ eigenvectors $u$ of $L$ (i.e., eigenvectors with
eigenvalue smaller than $2\epsilon$), and specifically in the distribution of
the absolute values of the entries of $u$. In order to be able to analyze this
distribution, we define the sets of all entries in $u$ that are bigger than a
threshold $\theta$:

######  Definition 6 (Threshold sets).

Let $G=(V,E)$ be a graph with normalized Laplacian $L$. Let $u$ be a
normalized eigenvector of $L$ with $||u||_{2}=1$. Then for the vector $u$ and
a threshold $\theta\in\mathbb{R}^{+}$ we define the threshold set $S(\theta)$
with respect to the eigenvector $u$ and threshold $\theta$ as

$S(\theta):=\\{x\in V:u(x)\geq\theta\\}\text{.}$

Our arguments will use that for every vertex $x$, we have
$u(x)\approx\frac{1}{d}\sum_{\\{x,y\\}\in E}u(y)$. So nodes neighboring other
nodes with large $u(\cdot)$ values are likely to have large $u(\cdot)$ values
as well. This motivates the following definition of the potential of a
threshold set.

######  Definition 7 (Potential of a threshold set).

Let $G=(V,E)$ be a graph with normalized Laplacian $L$. Let $u$ be a
normalized eigenvector of $L$ with $||u||_{2}=1$. Then for vector $u$ and a
threshold $\theta\in\mathbb{R}^{+}$ we define the potential of a threshold set
$S(\theta)$ as

$p(\theta)=\sum_{x\in S(\theta)}u(x)\text{.}$

We start by proving a core bound on the threshold sets (Lemma 10 below) that
forms the basis of our approach: the main technical results of this section
(Lemma 5 and Lemma 4) essentially follow by repeated application of Lemma 10.
Specifically, we now argue that if a threshold set $S(\theta)$ expands in the
graph $G$ and the relative potential of the set (i.e.,
$p(\theta)/|S(\theta)|$) is at most $2\theta$, then we can slightly decrease
$\theta$ to obtain a new $\theta^{\prime}$ such that the corresponding
threshold set is a constant factor larger that $S(\theta)$ and the relative
potential is bounded by $2\theta^{\prime}$.

######  Lemma 10 (Threshold shift for expanding threshold sets).

Let $G=(V,E)$ be a $d$-regular graph with normalized Laplacian $L$. Let $u$ be
a normalized eigenvector of $L$ with $||u||_{2}=1$ and with eigenvalue
$\lambda\leq 2\epsilon$. Let $\theta\in\mathbb{R}^{+}$ be a threshold. Suppose
that $S(\theta)$ is the threshold set with respect to $u$ and $\theta$ such
that $S(\theta)$ is non-empty, $\phi^{G}(S(\theta))\geq\varphi$ and
$\frac{p(\theta)}{|S(\theta)|}\leq 2\theta$. Then the following holds for
$\theta^{\prime}=\theta\left(1-\frac{8\epsilon}{\varphi}\right)$:

  1. 1.

$|S(\theta^{\prime})|\geq(1+\varphi/2)|S(\theta)|\text{, and}$

  2. 2.

$\frac{p(\theta^{\prime})}{|S(\theta^{\prime})|}\leq 2{\theta^{\prime}}$.

###### Proof.

Proof of item (1): Note that $\lambda u=Lu=(I-\frac{A}{d})u$. Thus for any
$x\in V$ we have $\left(Lu\right)(x)=u(x)-\frac{1}{d}\sum_{\\{x,y\\}\in
E}u(y)$. Thus we have,

$u(x)-\frac{1}{d}\sum_{\\{x,y\\}\in E}u(y)=\lambda\cdot u(x)\text{.}$

We write the above as

$\sum_{y\in\mathcal{N}(x)}(u(x)-u(y))=d\cdot\lambda\cdot u(x)\text{,}$ (20)

where $\mathcal{N}(x)=\\{y\in V:\exists\\{x,y\\}\in E\\}$. Summing (20) over
all $x\in S(\theta)$ we get

$\sum_{x\in S(\theta)}\sum_{y\in\mathcal{N}(x)}(u(x)-u(y))=\sum_{x\in
S(\theta)}\lambda\cdot d\cdot u(x)=\lambda\cdot d\cdot p(\theta)\text{,}$ (21)

and note that

$\sum_{x\in
S(\theta)}\sum_{y\in\mathcal{N}(x)}(u(x)-u(y))=\sum_{\begin{subarray}{c}\\{x,y\\}\in
E\\\ x\in S(\theta),y\not\in S(\theta)\end{subarray}}(u(x)-u(y))\text{.}$ (22)

For any edge $e=\\{x,y\\}\in E$, we define $\Delta(e)=|u(x)-u(y)|$. Note that
for any $e=\\{x,y\\}$ such that $x\in S(\theta)$ and $y\not\in S(\theta)$ we
have $u(x)\geq\theta>u(y)$, hence $\Delta(e)=u(x)-u(y)$. Therefore, putting
(22) and (21) together we get

$\sum_{e\in E(S(\theta),V\setminus S(\theta))}\Delta(e)=\lambda\cdot d\cdot
p(\theta)\text{.}$

By an averaging argument there exists a set $E_{L}\subseteq
E(S_{\theta},V\setminus S_{\theta})$ such that
$|E_{L}|\geq\frac{|E(S(\theta),V\setminus S(\theta))|}{2}$ and all edges $e\in
E_{L}$ satisfy $\Delta(e)\leq\frac{2\cdot\lambda\cdot d\cdot
p(\theta)}{|E(S(\theta),V\setminus S(\theta))|}$. We define $V_{L}$ as a
subset of vertices of $V\setminus S(\theta)$ that are connected to vertices of
$S(\theta)$ by edges in $E_{L}$, i.e.

$V_{L}=\\{y\in V\setminus S(\theta):\exists\ \\{x,y\\}\in E_{L},x\in
S(\theta)\\}\text{.}$

Note that

$|V_{L}|\geq\frac{|E_{L}|}{d}\geq\frac{|E(S(\theta),V\setminus
S(\theta))|}{2d}\text{.}$ (23)

Using the assumption of the lemma that $\phi^{G}(S(\theta))\geq\varphi$ we
obtain

$|E(S(\theta),V\setminus S(\theta))|\geq\varphi\cdot
d\cdot|S(\theta)|\text{.}$ (24)

Putting (24) and (23) together we get

$|V_{L}|\geq\frac{\varphi|S(\theta)|}{2}\text{.}$ (25)

Recall that for all $e\in E_{L}$ we have
$\Delta(e)\leq\frac{2\cdot\lambda\cdot d\cdot
p(\theta)}{|E(S(\theta),V\setminus S(\theta))|}$. We have $\lambda\leq
2\epsilon$, therefore for all $e\in E_{L}$ we have
$\Delta(e)\leq\frac{4\cdot\epsilon\cdot d\cdot
p(\theta)}{|E(S(\theta),V\setminus S(\theta))|}$. Thus for all $y\in V_{L}$ we
get

$u(y)\geq\theta-\frac{4\cdot\epsilon\cdot d\cdot
p(\theta)}{|E(S(\theta),V\setminus S(\theta))|}\text{.}$ (26)

By the assumption of the lemma we have $\frac{p(\theta)}{|S(\theta)|}\leq
2\theta$, hence, by inequality (24) we get

$\theta-\frac{4\cdot\epsilon\cdot d\cdot p(\theta)}{|E(S(\theta),V\setminus
S(\theta))|}\geq\theta-\frac{4\cdot\epsilon\cdot d\cdot
p(\theta)}{\varphi\cdot
d\cdot|S(\theta)|}=\theta-\frac{4\epsilon}{\varphi}\cdot\frac{p(\theta)}{|S(\theta)|}\geq\theta\left(1-\frac{8\epsilon}{\varphi}\right)\text{.}$
(27)

Putting (27) and (26) together we get for all $y\in V_{L}$,
$u(y)\geq\theta\left(1-\frac{8\epsilon}{\varphi}\right)$. Let
$\theta^{\prime}:=\theta(1-\frac{8\epsilon}{\varphi})$. Thus

$S(\theta)\cup V_{L}\subseteq S(\theta^{\prime}){.}$

By definition of $V_{L}$ we have $V_{L}\cap S(\theta)=\emptyset$. Therefore,
$|S(\theta^{\prime})|\geq|S(\theta)|+|V_{L}|$. Thus by inequality (25) we get

$|S(\theta^{\prime})|\geq|S(\theta)|\left(1+\frac{\varphi}{2}\right)\text{.}$
(28)

This concludes the proof of the first part of the lemma.

Proof of item (2): Now using that for all $x\not\in S(\theta)$ we have
$u(x)<\theta$ and that $p(\theta)\leq 2\theta|S(\theta)|$ by assumption of the
lemma we obtain

$\displaystyle p(\theta^{\prime})$ $\displaystyle=\sum_{u\in
S(\theta^{\prime})}u(x)$ $\displaystyle=\sum_{x\in S(\theta)}u(x)+\sum_{x\in
S(\theta^{\prime})\setminus S(\theta)}u(x)$ $\displaystyle\leq
p(\theta)+\theta|S(\theta^{\prime})\setminus S(\theta)|$ $\displaystyle\leq
2\theta|S(\theta)|+\theta|S(\theta^{\prime})\setminus S(\theta)|\text{.}$
$\displaystyle\text{Since }p(\theta)\leq 2\theta|S(\theta)|$

By (28) we have $|S(\theta^{\prime})\setminus
S(\theta)|\geq\frac{\varphi}{2}|S(\theta)|$. Therefore, using
$\epsilon\leq\frac{\varphi^{2}}{100}$ we get

$\displaystyle\frac{p(\theta^{\prime})}{|S(\theta^{\prime})|}$
$\displaystyle\leq$
$\displaystyle\frac{2\theta|S(\theta)|+\theta|S(\theta^{\prime})\setminus
S(\theta)|}{|S(\theta)|+|S(\theta^{\prime})\setminus
S(\theta)|}=\theta\cdot\frac{2+\frac{|S(\theta^{\prime})\setminus
S(\theta)|}{|S(\theta)|}}{1+\frac{|S(\theta^{\prime})\setminus
S(\theta)|}{|S(\theta)|}}\leq\theta\cdot\frac{2+\frac{\varphi}{2}}{1+\frac{\varphi}{2}}\leq\theta\cdot
2\left(1-\frac{8\epsilon}{\varphi}\right)\leq 2\theta^{\prime}$

∎

We would like to apply Lemma 10 iteratively, but there is one hurdle: while
the first condition on the threshold set $S(\theta)$ naturally follows as long
as $S(\theta)$ is not too large (by Proposition 2), the second condition needs
to be established at the beginning of the iterative process. Lemma 11
accomplishes exactly that: we prove that for any value $\theta_{1}$ with
threshold set $S(\theta_{1})$ not empty or not too large, there exists a close
value $\theta$ that meets the conditions of previous lemma.

######  Proposition 2.

Let $G=(V,E)$ be a $d$-regular graph that admits a
$(k,\varphi,\epsilon)$-clustering $C_{1},\ldots,C_{k}$. For any set
$S\subseteq V$ with size $|S|\leq\frac{1}{2}\cdot\min_{i\in k}|C_{i}|$ we have
$\phi^{G}(S)\geq\varphi$.

###### Proof.

For any $1\leq i\leq k$ we define $S_{i}=S\cap C_{i}$. Note that

$|S_{i}|\leq|S|\leq\frac{1}{2}\cdot\min_{i\in
k}|C_{i}|\leq\frac{|C_{i}|}{2}\text{.}$

Therefore since $\phi^{G}(C_{i})\geq\varphi$ we have $E(S_{i},C_{i}\setminus
S_{i})\geq\varphi d|S_{i}|$. Thus we get

$E(S,V\setminus S)\geq\sum_{i=1}^{k}E(S_{i},C_{i}\setminus S_{i})\geq\varphi
d\sum_{i=1}^{k}|S_{i}|=\varphi d|S|\text{.}$

Hence, $\phi^{G}(S)\geq\varphi$. ∎

######  Lemma 11.

Let $\varphi\in(0,1)$ and $\epsilon\leq\frac{\varphi^{2}}{100}$, and let
$G=(V,E)$ be a $d$-regular graph that admits $(k,\varphi,\epsilon)$-clustering
$C_{1},\ldots,C_{k}$. Let $L$ denote the normalized Laplacian of $G$. Let $u$
be a normalized eigenvector of $L$ with $||u||_{2}=1$ and with eigenvalue
$\lambda\leq 2\epsilon$. Let $\theta_{1}\in\mathbb{R}^{+}$ be a threshold. Let
$S(\theta_{1})$ be the threshold set with respect to $u$ and $\theta_{1}$.
Suppose that
$1\leq|S(\theta_{1})|\leq\frac{1}{2}\cdot\min_{i\in\\{1,\dots,k\\}}|C_{i}|$.
Then there exists a threshold $\theta_{2}$ such that the following holds:

  1. 1.

$\theta_{1}\left(1-\frac{8\epsilon}{\varphi}\right)\leq\theta_{2}\leq\theta_{1}\text{,
and}$

  2. 2.

$\frac{p(\theta_{2})}{|S(\theta_{2})|}\leq 2\theta_{2}$

###### Proof.

Let

$\theta^{*}:=\min\left\\{\theta\geq\theta_{1}\;\biggl{|}\;S(\theta)\not=\emptyset\text{
and }\frac{p(\theta)}{|S(\theta)|}\leq 2\theta\right\\}\text{.}$

We can conclude that $\theta^{*}$ exists, as by the assumption of the lemma we
have $|S(\theta_{1})|\geq 1$ and for $\theta_{\max}=\max_{x\in V}u(x)$ we have
$\frac{p(\theta_{\max})}{|S(\theta_{\max})|}=\theta_{\max}$. We also have
$|S(\theta^{*})|\leq\min_{i\in\\{1,\dots,k\\}}|C_{i}|/2$ as
$\theta^{*}\geq\theta_{1}$ and by the assumption of the lemma. So Proposition
2 implies

$\phi^{G}(S(\theta^{*}))\geq\varphi\text{.}$ (29)

Now Lemma 10 implies

$\frac{p(\theta^{*}(1-\frac{8\epsilon}{\varphi}))}{|S(\theta^{*}(1-\frac{8\epsilon}{\varphi}))|}\leq
2\theta^{*}\left(1-\frac{8\epsilon}{\varphi}\right)$

and by minimality of $\theta^{*}$ we have that:

$\theta_{1}\left(1-\frac{8\epsilon}{\varphi}\right)\leq\theta^{*}\left(1-\frac{8\epsilon}{\varphi}\right)\leq\theta_{1}\text{.}$

So we can set
$\theta_{2}:=\theta^{*}\left(1-\frac{8\epsilon}{\varphi}\right)$. ∎

We are now ready to prove our tail bound. The main idea behind the proof is to
use Lemma 10 and Lemma 11 to show that if a vertex has a large entry along one
of the bottom $k$ eigenvectors this implies that many other vertices also have
a relatively large value along the same eigenvector. Thus, not too many
$f_{x}$ can have such a large value.

See 4

###### Proof.

Let $s_{\min}=\min_{i\in\\{1,\dots,k\\}}|C_{i}|$. We define

$S^{+}=\left\\{x\in
V:u(x)\geq\beta\cdot\sqrt{\frac{10}{s_{\min}}}\right\\}\text{,}$

and

$S^{-}=\left\\{x\in V:-u(x)\geq\beta\cdot\sqrt{\frac{10}{s_{\min}}}\right\\}$

Note that $-u$ is also an eigenvector of $L$ with the same eigenvalue as $u$,
hence, without loss of generality suppose that $|S^{+}|\geq|S^{-}|$. Let
$T=\left\\{x\in V:u(x)^{2}\geq\frac{10}{s_{\min}}\right\\}\text{.}$ Since,
$1=\|u\|^{2}_{2}=\sum_{x\in V}u(x)^{2}$, an averaging argument implies
$|T|\leq\frac{s_{\min}}{10}$. Let

$T^{+}=\left\\{x\in V:u(x)\geq\sqrt{\frac{10}{s_{\min}}}\right\\}\text{.}$

Note that $\beta>1$, hence, ${S^{+}}\subseteq{T^{+}}\subseteq T$, and so we
have $|{S^{+}}|\leq|T^{+}|\leq|T|\leq\frac{s_{\min}}{10}$. We may assume that
$S^{+}$ is non-empty as otherwise the lemma follows immediately. Let
$\theta_{0}=\beta\cdot\sqrt{\frac{10}{s_{\min}}}$. Note that
$S^{+}=S(\theta_{0})$. Hence, $1\leq|S(\theta_{0})|\leq\frac{s_{\min}}{10}$.
Therefore by Lemma 11 there exists a threshold $\theta_{1}$ such that

$\left(1-\frac{8\epsilon}{\varphi}\right)\beta\cdot\sqrt{\frac{10}{s_{\min}}}\leq\theta_{1}\leq\beta\cdot\sqrt{\frac{10}{s_{\min}}}\text{,
and}$ (30) $\frac{p(\theta_{1})}{|S(\theta_{1})|}\leq 2\theta_{1}\text{.}$

For any $t\geq 1$ we define
$\theta_{t+1}=\theta_{t}(1-\frac{8\epsilon}{\varphi})$. For some
$t^{\prime}\geq 0$ we must have
$\theta_{t^{\prime}+1}\leq\sqrt{\frac{10}{s_{\min}}}\leq\theta_{t^{\prime}}$.
Thus by (30) we have

$\theta_{t^{\prime}}=\left(1-\frac{8\epsilon}{\varphi}\right)^{t^{\prime}-1}\theta_{1}\geq\left(1-\frac{8\epsilon}{\varphi}\right)^{t^{\prime}}\cdot\beta\cdot\sqrt{\frac{10}{s_{\min}}}\text{,}$
(31)

and

$\theta_{t^{\prime}}\leq\frac{\theta_{t^{\prime}+1}}{\left(1-\frac{8\epsilon}{\varphi}\right)}\leq\frac{\sqrt{\frac{10}{s_{\min}}}}{\left(1-\frac{8\epsilon}{\varphi}\right)}$
(32)

Putting (31) and (32) together we get

$\beta\leq\left(1-\frac{8\epsilon}{\varphi}\right)^{-t^{\prime}-1}$ (33)

Recall that for all $t\geq 1$ we have
$\theta_{t+1}=\theta_{t}(1-\frac{8\epsilon}{\varphi})$, thus

$S^{+}={S(\theta_{0})}\subseteq{S(\theta_{1})}\subseteq{S(\theta_{2})}\subseteq\ldots\subseteq
S(\theta_{t^{\prime}})\subseteq T^{+}\text{.}$

Therefore for all $0\leq t\leq t^{\prime}$ we have

$|S^{+}|\leq|S(\theta_{t})|\leq|T^{+}|\leq\frac{s_{\min}}{10}\text{.}$ (34)

Since
$|S(\theta_{t})|\leq\frac{\min_{i\in\\{1,\dots,k\\}}|C_{i}|}{10}=\frac{s_{\min}}{10}$,
by Lemma 10 for all $1\leq t\leq t^{\prime}$ we have

$|S(\theta_{t+1})|\geq|S(\theta_{t})|\left(1+\frac{\varphi}{2}\right)\text{.}$
(35)

Therefore

$\displaystyle t^{\prime}$
$\displaystyle\leq\log_{1+\frac{\varphi}{2}}\left(\frac{|T^{+}|}{|S^{+}|}\right)$
By (35)
$\displaystyle\leq\log_{1+\frac{\varphi}{2}}\left(\frac{s_{\min}}{10\cdot|S^{+}|}\right)$
By (34)
$\displaystyle\leq\log_{1+\frac{\varphi}{2}}\left(\frac{s_{\min}}{5\cdot|S^{+}\cup
S^{-}|}\right)$ $\displaystyle\text{By the assumption }|S^{+}|\geq|S^{-}|$
(36)

Putting (33) and (36) together we get

$\displaystyle\beta$
$\displaystyle\leq\left(1-\frac{8\epsilon}{\varphi}\right)^{-t^{\prime}-1}$ By
(33)
$\displaystyle\leq\left(1-\frac{8\epsilon}{\varphi}\right)^{-1-\log_{1+\frac{\varphi}{2}}\left(\frac{s_{\min}}{5\cdot|S^{+}\cup
S^{-}|}\right)}$ By (36) $\displaystyle\leq
2\cdot\left(\frac{s_{\min}}{5\cdot|S^{+}\cup
S^{-}|}\right)^{-\log_{1+\frac{\varphi}{2}}\left(1-\frac{8\epsilon}{\varphi}\right)}$
$\displaystyle\text{Since }\frac{\epsilon}{\varphi^{2}}\leq\frac{1}{100}$ (37)

Note that for any $x\in\mathbb{R}$ we have $1+x\leq e^{x}$, and for any
$x<0.01$ we have $1-x\geq e^{-1.2x}$, thus given
$\frac{\epsilon}{\varphi}<0.01$ we have

${\log_{1+\frac{\varphi}{2}}\left(1-\frac{8\epsilon}{\varphi}\right)}=\frac{\ln\left(1-\frac{8\epsilon}{\varphi}\right)}{\ln\left(1+\frac{\varphi}{2}\right)}\geq\frac{-\frac{10\epsilon}{\varphi}}{\frac{\varphi}{2}}\geq-\frac{20\cdot\epsilon}{\varphi^{2}}$
(38)

Putting (37) and (38) together we get

$\frac{\beta}{2}\leq\left(\frac{s_{\min}}{5\cdot|S^{+}\cup
S^{-}|}\right)^{(20\cdot\epsilon/\varphi^{2})}$

Therefore we have

$|S^{+}\cup S^{-}|\leq
s_{\min}\cdot\left(\frac{\beta}{2}\right)^{-\left(\varphi^{2}/20\cdot\epsilon\right)}\leq
n\cdot\left(\frac{\beta}{2}\right)^{-\left(\varphi^{2}/20\cdot\epsilon\right)}\text{.}$

∎

As a consequence of our tail bound we can prove a bound on
$\ell_{\infty}$-norm on any unit vector in the eigenspace spanned by the
bottom $k$ eigenvectors of $L$, i.e. $U_{[k]}$.

See 5

###### Proof.

We define

$S=\left\\{x\in V:|u(x)|\geq
n^{20\epsilon/\varphi^{2}}\cdot\sqrt{\frac{160}{\min_{i\in
k}|C_{i}|}}\right\\}$

Let $\beta=4\cdot n^{20\epsilon/\varphi^{2}}$. By Lemma 4 we have

$\displaystyle|S|$ $\displaystyle\leq
n\cdot\left(\frac{\beta}{2}\right)^{-{\varphi^{2}/20\cdot\epsilon}}\leq
n\cdot\left(2\cdot
n^{20\epsilon/\varphi^{2}}\right)^{-{\varphi^{2}/20\cdot\epsilon}}<1$

Therefore $S=\emptyset$, hence

$\|u\|_{\infty}\leq n^{20\epsilon/\varphi^{2}}\cdot\sqrt{\frac{160}{\min_{i\in
k}|C_{i}|}}\text{.}$

∎

###  4.3 Centers are strongly orthogonal

The main result of this section is Lemma 12 which generalizes Lemma 7 to the
orthogonal projection of cluster centers into the subspace spanned by some of
the centers. To prove Lemma 12 we first need to prove Lemma 13, Lemma 14 and
Lemma 15.

######  Lemma 12.

Let $k\geq 2$, $\varphi\in(0,1)$ and $\frac{\epsilon}{\varphi^{2}}$ be smaller
than an absolute positive constant. Let $G=(V,E)$ be a $d$-regular graph that
admits $(k,\varphi,\epsilon)$-clustering $C_{1},\ldots,C_{k}$. Let
$S\subset\\{\mu_{1},\dots,\mu_{k}\\}$ denote a subset of cluster means. Let
$\Pi\in\mathbb{R}^{k\times k}$ denote the orthogonal projection matrix onto
$span(S)^{\perp}$. Then the following holds:

  1. 1.

For all ${\mu}_{i}\in\\{{\mu}_{1},\ldots,{\mu}_{k}\\}\setminus S$ we have
$\left|\|\Pi{\mu}_{i}\|_{2}^{2}-||\mu_{i}||_{2}^{2}\right|\leq\frac{16\sqrt{\epsilon}}{\varphi}\cdot||\mu_{i}||_{2}^{2}\text{.}$

  2. 2.

For all ${\mu}_{i}\neq\mu_{j}\in\\{{\mu}_{1},\ldots,{\mu}_{k}\\}\setminus S$
we have
$|\langle\Pi{\mu}_{i},\Pi{\mu}_{j}\rangle|\leq\frac{40\sqrt{\epsilon}}{\varphi}\cdot\frac{1}{\sqrt{|C_{i}|\cdot|C_{j}|}}\text{.}$

Matrix $A\in\mathbb{R}^{n}$ is poitive definite if $x^{T}Ax>0$ for all $x\neq
0$, and it is positive semidefinite if $x^{T}Ax\geq 0$ for all
$x\in\mathbb{R}^{n}$. We write $A\succ 0$ to indicate that $A$ is positive
definite, and $A\succcurlyeq 0$ to indicate that it is positive semidefinite.
We use the semidefinite ordering on matrices, writing $A\succcurlyeq B$ if and
only if $A-B\succcurlyeq 0$.

######  Theorem 4 ([Tod11]).

Let $A,B\in\mathbb{R}^{n\times n}$ be invertible, positive definite matrices.
Then $A\succcurlyeq B\implies B^{-1}\succcurlyeq A^{-1}$.

###### Proof.

By symmetry, we only need to show $A\succcurlyeq B\implies B^{-1}\succcurlyeq
A^{-1}$. Since $B\succ 0$ for any $x,y\in\mathbb{R}^{n}$ we obtain

$\displaystyle 0$ $\displaystyle\leq\left\langle
y-B^{-1}x,B(y-B^{-1}x)\right\rangle$ $\displaystyle=\left\langle
y,By\right\rangle-\left\langle y,x\right\rangle-\left\langle
B^{-1}x,By\right\rangle+\left\langle x,B^{-1}x\right\rangle$
$\displaystyle=\left\langle y,By\right\rangle-2\left\langle
x,y\right\rangle+\left\langle x,B^{-1}x\right\rangle$

so

$2\left\langle x,y\right\rangle-\left\langle y,By\right\rangle\leq\left\langle
x,B^{-1}x\right\rangle$ (39)

Since $A\succcurlyeq B$ it follows from (39) that

$2\left\langle x,y\right\rangle-\left\langle y,Ay\right\rangle\leq
2\left\langle x,y\right\rangle-\left\langle y,Ay\right\rangle\leq\left\langle
x,B^{-1}x\right\rangle$ (40)

Letting $y=A^{-1}x$ in the leftmost expression of (40) we obtain

$\left\langle x,A^{-1}x\right\rangle\leq\left\langle x,B^{-1}x\right\rangle$

Since $x\in\mathbb{R}^{n}$ is is arbitrary, we get $B^{-1}\succcurlyeq
A^{-1}$. ∎

######  Lemma 13.

Let $H,\widetilde{H}\in\mathbb{R}^{n\times n}$ be invertible, positive
definite matrices. Let $\delta<1$. Suppose that for any vector
$x\in\mathbb{R}^{n}$ with $\|x\|_{2}=1$ we have $(1-\delta)x^{T}Hx\leq
x^{T}\widetilde{H}x\leq(1+\delta)x^{T}Hx\text{.}$ Then for any vector
$y\in\mathbb{R}^{n}$ with $\|y\|_{2}=1$ we have
$\frac{1}{1+\delta}y^{T}H^{-1}y\leq
y^{T}\widetilde{H}^{-1}y\leq\frac{1}{1-\delta}y^{T}H^{-1}y\text{.}$

###### Proof.

Note that we have $(1-\delta)H\preceq\widetilde{H}\preceq(1+\delta)H$
therefore, by Theorem 4 we have

$\frac{1}{(1-\delta)}\cdot
H^{-1}\succcurlyeq\widetilde{H}^{-1}\succcurlyeq\frac{1}{(1+\delta)}\cdot
H^{-1}$

∎

######  Lemma 14.

Let $k\geq 2$, $\varphi\in(0,1)$ and $\frac{\epsilon}{\varphi^{2}}$ be smaller
than an absolute positive constant. Let $G=(V,E)$ be a $d$-regular graph that
admits $(k,\varphi,\epsilon)$-clustering $C_{1},\ldots,C_{k}$. Let
$S=\\{\mu_{1},\ldots,\mu_{k}\\}\setminus\\{\mu_{i}\\}$. Let
$H=[\mu_{1},\mu_{2},\ldots,\mu_{i-1},\mu_{i+1},\ldots,\mu_{k}]$ denote a
matrix such that its columns are the vectors in $S$. Let
$W\in\mathbb{R}^{(k-1)\times(k-1)}$ denote a diagonal matrix such that for all
$j<i$ we have $W(j,j)=\sqrt{|C_{j}|}$ and for all $j\geq i$ we have
$W(j,j)=\sqrt{|C_{j+1}|}$. Let $Z=HW$. Then $Z^{T}Z$ is invertible, and for
any vector $x\in\mathbb{R}^{k-1}$ with $||x||_{2}=1$ we have

$|x^{T}((Z^{T}Z)^{-1}-I)x|\leq\frac{5\sqrt{\epsilon}}{\varphi}\text{.}$

###### Proof.

Let $Y\in\mathbb{R}^{k\times k}$ be a matrix, whose $i$-th column is equal to
$\sqrt{C_{i}}\cdot\mu_{i}$. By Lemma 9 item (2) for any vector
$z\in\mathbb{R}^{k}$ with $||\alpha||_{2}=1$ we have

$|\alpha^{T}(Y^{T}Y-I)\alpha|\leq\frac{4\sqrt{\epsilon}}{\varphi}$

Let $x\in\mathbb{R}^{k-1}$ be a vector with $||x||_{2}=1$, and let
$\alpha\in\mathbb{R}^{k}$ be a vector defined as follows:

$\alpha_{j}=\begin{cases}x_{j}&j<i\\\ 0&j=i\\\ x_{j+1}&j>i\end{cases}$

Thus we have $||\alpha||_{2}=||x||_{2}=1$ and $Y\alpha=Zx$. Hence, we get

$|x^{T}(Z^{T}Z-I)x|=|\alpha^{T}(Y^{T}Y-I)\alpha|\leq\frac{4\sqrt{\epsilon}}{\varphi}$

Thus for any vector $x\in\mathbb{R}^{k-1}$ with $||x||_{2}=1$ we have

$1-\frac{4\sqrt{\epsilon}}{\varphi}\leq x^{T}(Z^{T}Z)x\leq
1+\frac{4\sqrt{\epsilon}}{\varphi}$

Note that $Z^{T}Z$ is symmetric and positive semidefinit. Also note that
$Z^{T}Z$ is spectrally close to $I$, hence, $Z^{T}Z$ is invertible. Thus by
Lemma 13 for any vector $x\in\mathbb{R}^{k-1}$ we have

$1-\frac{5\sqrt{\epsilon}}{\varphi}\leq x^{T}(Z^{T}Z)^{-1}x\leq
1+\frac{5\sqrt{\epsilon}}{\varphi}$

Therefore we get

$|x^{T}((Z^{T}Z)^{-1}-I)x|\leq\frac{5\sqrt{\epsilon}}{\varphi}\text{.}$

∎

######  Lemma 15.

Let $k\geq 2$ be an integer, $\varphi\in(0,1)$, and $\epsilon\in(0,1)$. Let
$G=(V,E)$ be a $d$-regular graph that admits $(k,\varphi,\epsilon)$-clustering
$C_{1},\ldots,C_{k}$. Let
$S=\\{\mu_{1},\ldots,\mu_{k}\\}\setminus\\{\mu_{i}\\}$. Let
$H=[\mu_{1},\mu_{2},\ldots,\mu_{i-1},\mu_{i+1},\ldots,\mu_{k}]$ denote a
matrix such that its columns are the vectors in $S$. Let
$W\in\mathbb{R}^{(k-1)\times(k-1)}$ denote a diagonal matrix such that for all
$j<i$ we have $W(j,j)=\sqrt{|C_{j}|}$ and for all $j\geq i$ we have
$W(j,j)=\sqrt{|C_{j+1}|}$. Let $Z=HW$. Then we have

$\mu_{i}^{T}ZZ^{T}\mu_{i}\leq\frac{8\sqrt{\epsilon}}{\varphi}\cdot||\mu_{i}||_{2}^{2}\text{.}$

###### Proof.

Note that
$ZZ^{T}=(\sum_{j=1}^{k}|C_{j}|\mu_{j}\mu_{j}^{T})-|C_{i}|\mu_{i}\mu_{i}^{T}$.
Thus we have

$\mu_{i}^{T}ZZ^{T}\mu_{i}=\mu_{i}^{T}\left(\sum_{j=1}^{k}|C_{j}|\mu_{j}\mu_{j}^{T}\right)\mu_{i}-|C_{i}|\cdot||\mu_{i}||_{2}^{4}\text{.}$
(41)

By Lemma 9 item (1) for any vector $x$ with $||x||_{2}=1$ we have

$x^{T}\left(\sum_{j=1}^{k}|C_{j}|\mu_{j}\mu_{j}^{T}-I\right)x\leq\frac{4\sqrt{\epsilon}}{\varphi}$

Hence we can write

$\displaystyle\mu_{i}^{T}\left(\sum_{j=1}^{k}|C_{j}|\mu_{j}\mu_{j}^{T}\right)\mu_{i}$
$\displaystyle=\mu_{i}^{T}\left(\sum_{j=1}^{k}|C_{j}|\mu_{j}\mu_{j}^{T}-I\right)\mu_{i}+\mu_{i}^{T}\mu_{i}\leq\left(1+\frac{4\sqrt{\epsilon}}{\varphi}\right)||\mu_{i}||_{2}^{2}$

Therefore by (41) we get

$\displaystyle\mu_{i}^{T}ZZ^{T}\mu_{i}$
$\displaystyle=\mu_{i}^{T}\left(\sum_{j=1}^{k}|C_{j}|\mu_{j}\mu_{j}^{T}\right)\mu_{i}-|C_{i}|\cdot||\mu_{i}||_{2}^{4}$
$\displaystyle\leq\left(1+\frac{4\sqrt{\epsilon}}{\varphi}-|C_{i}|\cdot||\mu_{i}||_{2}^{2}\right)||\mu_{i}||_{2}^{2}$

By Lemma 7 we have
$|C_{i}|\cdot||\mu_{i}||_{2}^{2}\geq\left(1-\frac{4\sqrt{\epsilon}}{\varphi}\right)$.
Thus we get

$\displaystyle\mu_{i}^{T}ZZ^{T}\mu_{i}$
$\displaystyle\leq\left(1+\frac{4\sqrt{\epsilon}}{\varphi}-|C_{i}|\cdot||\mu_{i}||_{2}^{2}\right)||\mu_{i}||_{2}^{2}$
$\displaystyle\leq\left(1+\frac{4\sqrt{\epsilon}}{\varphi}-1+\frac{4\sqrt{\epsilon}}{\varphi}\right)||\mu_{i}||_{2}^{2}$
$\displaystyle\leq\frac{8\sqrt{\epsilon}}{\varphi}\cdot||\mu_{i}||_{2}^{2}$

∎

Now we prove the main result of the subsection (Lemma 12). See 12

###### Proof.

Proof of item (1): Since $\Pi$ is a orthogonal projection matrix we have
$||\Pi||_{2}=1$. Hence, we have
$||\Pi\mu_{i}||_{2}^{2}\leq||\mu_{i}||_{2}^{2}\leq\left(1+\frac{16\sqrt{\epsilon}}{\varphi}\right)||\mu_{i}||_{2}^{2}$.
Thus it’s left to prove
$||\Pi\mu_{i}||_{2}^{2}\geq\left(1-\frac{16\sqrt{\epsilon}}{\varphi}\right)||\mu_{i}||_{2}^{2}$.
Note that by Pythagoras’ theorem
$||\Pi\mu_{i}||^{2}_{2}=||\mu_{i}||^{2}_{2}-||(I-\Pi)\mu_{i}||^{2}_{2}$. We
will prove
$||(I-\Pi)\mu_{i}||^{2}_{2}\leq\frac{16\sqrt{\epsilon}}{\varphi}||\mu_{i}||^{2}_{2}$
which implies

$||\Pi\mu_{i}||^{2}_{2}\geq\left(1-16\frac{\sqrt{\epsilon}}{\varphi}\right)||\mu_{i}||_{2}^{2}\text{.}$

Let $S^{\prime}=\\{\mu_{1},\ldots,\mu_{k}\\}\setminus\\{\mu_{i}\\}$. Let
$\Pi^{\prime}$ denote the orthogonal projection matrix onto
$span(S^{\prime})^{\perp}$. Note that $S\subseteq S^{\prime}$, hence
${span}(S)$ is a subspace of ${span}(S^{\prime})$, therefore we have
$||(I-\Pi)\mu_{i}||^{2}_{2}\leq||(I-\Pi^{\prime})\mu_{i}||^{2}_{2}$. Thus it
suffices to prove
$||(I-\Pi^{\prime})\mu_{i}||^{2}_{2}\leq\frac{16\sqrt{\epsilon}}{\varphi}||\mu_{i}||^{2}_{2}$.
Let $H=[\mu_{1},\mu_{2},\ldots,\mu_{i-1},\mu_{i+1},\ldots,\mu_{k}]$ denote a
matrix such that its columns are the vectors in $S^{\prime}$. Let
$W\in\mathbb{R}^{(k-1)\times(k-1)}$ denote a diagonal matrix such that for all
$j<i$ we have $W(j,j)=\sqrt{|C_{j}|}$ and for all $j\geq i$ we have
$W(j,j)=\sqrt{|C_{j+1}|}$. Let $Z=HW$. The orthogonal projection matrix onto
the span of $S^{\prime}$ is defined as $(I-\Pi^{\prime})=Z(Z^{T}Z)^{-1}Z^{T}$,
and using Lemma 14 we get

$\displaystyle||(I-\Pi^{\prime})\mu_{i}||^{2}_{2}$
$\displaystyle=\mu_{i}^{T}Z(Z^{T}Z)^{-1}Z^{T}\mu_{i}$
$\displaystyle=\mu_{i}^{T}Z((Z^{T}Z)^{-1}-I)Z^{T}\mu_{i}+\mu_{i}^{T}ZZ^{T}\mu_{i}$

By Lemma 14 $(Z^{T}Z)^{-1}$ is spectrally close to $I$, therefore we have

$\left|\mu_{i}^{T}Z\left((Z^{T}Z)^{-1}-I\right)Z^{T}\mu_{i}\right|\leq\frac{5\sqrt{\epsilon}}{\varphi}||Z^{T}\mu_{i}||_{2}^{2}$

Thus we get

$||(I-\Pi^{\prime})\mu_{i}||^{2}_{2}\leq\left(\frac{5\sqrt{\epsilon}}{\varphi}+1\right)||Z^{T}\mu_{i}||_{2}^{2}\leq
2||Z^{T}\mu_{i}||_{2}^{2}$

By Lemma 15 we have

$||Z^{T}\mu_{i}||_{2}^{2}=\mu_{i}^{T}ZZ^{T}\mu_{i}\leq\frac{8\sqrt{\epsilon}}{\varphi}\cdot||\mu_{i}||_{2}^{2}$

Therefore we get

$||(I-\Pi)\mu_{i}||^{2}_{2}\leq||(I-\Pi^{\prime})\mu_{i}||^{2}_{2}\leq
2||Z^{T}\mu_{i}||_{2}^{2}\leq\frac{16\sqrt{\epsilon}}{\varphi}||\mu_{i}||_{2}^{2}$
(42)

Hence,

$||\Pi\mu_{i}||^{2}_{2}\geq\left(1-16\frac{\sqrt{\epsilon}}{\varphi}\right)||\mu_{i}||_{2}^{2}\text{.}$

Proof of item (2): Note that

$\displaystyle\langle\mu_{i},\mu_{j}\rangle$
$\displaystyle=\langle(I-\Pi)\mu_{i}+\Pi\mu_{i},(I-\Pi)\mu_{j}+\Pi\mu_{j}\rangle=\langle(I-\Pi)\mu_{i},(I-\Pi)\mu_{j}\rangle+\langle\Pi\mu_{i},\Pi\mu_{j}\rangle$

Thus by triangle inequality we have

$|\langle\Pi\mu_{i},\Pi\mu_{j}\rangle|\leq|\langle\mu_{i},\mu_{j}\rangle|+|\langle(I-\Pi)\mu_{i},(I-\Pi)\mu_{j}\rangle|$
(43)

By Cauchy Schwarz we have

$\displaystyle|\langle(I-\Pi)\mu_{i},(I-\Pi)\mu_{j}\rangle|$
$\displaystyle\leq||(I-\Pi)\mu_{i}||_{2}||(I-\Pi)\mu_{i}||_{2}$
$\displaystyle\leq\frac{16\sqrt{\epsilon}}{\varphi}\cdot||\mu_{i}||_{2}||\mu_{j}||_{2}$
By (42)
$\displaystyle\leq\frac{32\sqrt{\epsilon}}{\varphi}\cdot\frac{1}{\sqrt{|C_{i}||C_{j}|}}$
$\displaystyle\text{By Lemma \ref{lem:dotmu} for small enough
}\frac{\epsilon}{\varphi^{2}}$ (44)

Also by Lemma 7 we have

$|\langle\mu_{i},\mu_{j}\rangle|\leq\frac{8\sqrt{\epsilon}}{\varphi}\cdot\frac{1}{\sqrt{|C_{i}||C_{j}|}}$
(45)

Therefore by (43), (44) and (45) we get

$|\langle\Pi\mu_{i},\Pi\mu_{j}\rangle|\leq|\langle\mu_{i},\mu_{j}\rangle|+|\langle(I-\Pi)\mu_{i},(I-\Pi)\mu_{j}\rangle|\leq\frac{40\sqrt{\epsilon}}{\varphi}\cdot\frac{1}{\sqrt{|C_{i}||C_{j}|}}\text{.}$

∎

###  4.4 Robustness property of $(k,\varphi,\epsilon)$-clusterable graphs

In this subsection we show a Lemma that establishes a robustness property of
$(k,\varphi,\epsilon)$-clusterable graphs. That is we show that any collection
$\\{S_{1},S_{2},\dots,S_{k}\\}$ of pairwise disjoint subsets of vertices must
match clusters $\\{C_{1},\dots,C_{k}\\}$ well.

######  Lemma 16.

Let $G=(V,E)$ be a $d$-regular graph that admits a
$(k,\varphi,\epsilon)$-clustering $C_{1},\dots,C_{k}$. Let $k\geq 2$,
$\varphi\in(0,1)$ and $\frac{\epsilon}{\varphi^{3}}$ be smaller than an
absolute positive constant. If $S_{1},S_{2},\dots,S_{k}\subseteq V$ are $k$
disjoint sets such that for all $i\in[k]$

$\phi(S_{i})\leq O\left(\frac{\epsilon}{\varphi^{2}}\cdot\log(k)\right)$

then there exists a permutation $\pi$ on $k$ elements so that for all
$i\in[k]$:

$|C_{\pi(i)}\triangle S_{i}|\leq
O\left(\frac{\epsilon}{\varphi^{3}}\cdot\log(k)\right)|C_{\pi(i)}|$

###### Proof.

Fix $i\in[k]$ and let $J_{i}=\\{j:|S_{i}\cap C_{j}|\leq|C_{j}|/2\\}$. Then
observe that because the inner conductance of every $C_{i}$ is at least
$\varphi$ we get:

$\varphi\sum_{j\in J_{i}}|S_{i}\cap C_{j}|\leq
O\left(\frac{\epsilon}{\varphi^{2}}\cdot\log(k)\right)|S_{i}|$ (46)

Using (46) and the assumption $\frac{\epsilon}{\varphi^{3}}$ is sufficiently
small we get that

$\sum_{j\in J_{i}}|S_{i}\cap C_{j}|\leq
O\left(\frac{\epsilon}{\varphi^{3}}\cdot\log(k)\right)|S_{i}|<|S_{i}|$ (47)

(47) and $\sum_{j\in[k]}|S_{i}\cap C_{j}|=|S_{i}|$ gives us that

$\text{For all }i\in[k],J_{i}\neq[k]$ (48)

We will show that for each $i$: $|[k]\setminus J_{i}|=1$ and that a function
$i\mapsto\pi(i)\in[k]\setminus J_{i}$ (that is $\pi(i)$ is the only element of
$[k]\setminus J_{i}$) is a permutation and that it satisfies the claim of the
Lemma.

Assume that there exist $i_{1}\neq i_{2}\in[k]$ and $j\in([k]\setminus
J_{i_{1}})\cap([k]\setminus J_{i_{2}})$. By definition of $J_{i}$’s we get
that $|S_{i_{1}}\cap C_{j}|,|S_{i_{2}}\cap C_{j}|>|C_{j}|/2$ but $S_{i}$’s are
disjoint so it’s impossible that two of them intersect more than half of the
same $C_{j}$. That means that sets $([k]\setminus J_{i})$ are pairwise
disjoint for all $i$’s. But we also know from (48) that for all $i$
$([k]\setminus J_{i})\neq\emptyset$. So we have $k$ nonempty, pairwise
disjoint subsets of $[k]$, which means that every set contains one element and
all elements are different. That in turn means that we can define $\pi$ as a
function $i\mapsto\pi(i)\in[k]\setminus J_{i}$ and $\pi$ is a permutation.

Now we show that $\pi$ satisfies the claim of the Lemma. Observe that because
for all $i\in[k]$ the set $[k]\setminus J_{i}$ contains only one element we
get for all $i\in[k]$.

$\sum_{j\in J_{i}}|S_{i}\cap C_{j}|=|S_{i}\setminus C_{\pi(i)}|$ (49)

Note that because of (46) and (49) for all $i\in[k]$:

$|S_{i}\setminus C_{\pi(i)}|\leq O\left(\frac{\epsilon}{\varphi^{3}}\cdot\log
k\right)|S_{i}|.$ (50)

Moreover because inner conductance of every $C_{i}$ is at least $\varphi$ and
$|C_{\pi(i)}\setminus S_{i}|<|C_{\pi(i)}|/2$ we get that for all $i\in[k]$

$\varphi\cdot|C_{\pi(i)}\setminus S_{i}|\leq
O\left(\frac{\epsilon}{\varphi^{2}}\cdot\log(k)\right)|S_{i}|$ (51)

Finally combining (50) and (51) we get that:

$|C_{\pi(i)}\triangle S_{i}|\leq
O\left(\frac{\epsilon}{\varphi^{3}}\cdot\log(k)\right)|C_{\pi(i)}|$

∎

##  5 A spectral dot product oracle

Our goal in this section is to develop what we call a _spectral dot product
oracle_. The oracle is a sublinear time and space data structure that has
oracle access to a $(k,\varphi,\epsilon)$-clusterable graph $G$ and after a
preprocessing step can answer dot products queries for the spectral embedding.
Specifically, if $L=U\Lambda U^{T}$ is the normalized Laplacian of $G$ and the
$x$-th column of $F=U_{[k]}^{T}$ is called $f_{x}$ for $x\in V$ then our
oracle gets as input two vertices $x,y$ and returns an approximation of
$\langle f_{x},f_{y}\rangle$. Both the preprocessing time and the time to
evaluate an oracle query are $k^{O(1)}\cdot
n^{1/2+O(\epsilon/\varphi^{2})}\cdot(\log n)^{O(1)}$, that is, sublinear in
$n$ for $\epsilon\ll\varphi^{2}$. We now state the main theorem that we prove
in this section. The algorithms mentioned in Theorem 2 can be found later in
this section.

See 2

###  5.1 The spectral dot product oracle - overview

In the following sections we provide the proof of the spectral dot product
oracle. Recall from the technical overview that we are using the following
algorithms (we restate them for convenience of the reader). Our main tool for
accessing the spectral embedding of the graph is a primitive that runs a few
short (logarithmic length) random walks from a given vertex.

Algorithm 1 RunRandomWalks($G,R,t,x$)

1:Run $R$ random walks of length $t$ starting from $x$

2:Let $\widehat{m}_{x}(y)$ be the fraction of random walks that ends at $y$
$\triangleright$ vector $\widehat{m}_{x}$ has support at most $R$

3:return $\widehat{m}_{x}$

Another key primitive uses collision statistics to estimate the Gram matrix of
random walk distributions started at vertices in a set $S$.

Algorithm 2 EstimateCollisionProbabilities($G,I_{S},R,t$)

1:for $i=1$ to $O(\log n)$ do

2: ${\widehat{Q}_{i}}:=\textsc{EstimateTransitionMatrix}(G,I_{S},R,t)$

3: ${\widehat{P}_{i}}:=\textsc{EstimateTransitionMatrix}(G,I_{S},R,t)$

4:
$\mathcal{G}_{i}:=\frac{1}{2}\left(\widehat{P}_{i}^{T}\widehat{Q}_{i}+\widehat{Q}_{i}^{T}\widehat{P}_{i}\right)$
$\triangleright$ $\mathcal{G}_{i}$ is symmetric

5:Let $\mathcal{G}$ be a matrix obtained by taking the entrywise median of
$\mathcal{G}_{i}$’s $\triangleright$ $\mathcal{G}$ is symmetric

6:return $\mathcal{G}$

We also need the following procedure.

Algorithm 3 EstimateTransitionMatrix$(G,I_{S},R,t)$

1:for each sample $x\in I_{S}$ do

2: $\widehat{m}_{x}:=\textsc{RunRandomWalks}(G,R,t,x)$

3:Let ${\widehat{Q}}$ be the matrix whose columns are $\widehat{m}_{x}$ for
$x\in I_{S}$

4:return $\widehat{Q}$ $\triangleright$ $\widehat{Q}$ has at most $Rs$ non-
zeros

Then we can initialize the dot product oracle.

Algorithm 4 InitializeOracle($G,\delta,\xi$) $\triangleright$ Need:
$\epsilon/\varphi^{2}\leq\frac{1}{10^{5}}$

1:$t:=\frac{20\cdot\log n}{\varphi^{2}}$

2:$R_{\text{init}}:=O{(n^{1-\delta+980\cdot\epsilon/\varphi^{2}}\cdot
k^{17}/{\xi}^{2})}$

3:$s:=O(n^{480\cdot\epsilon/\varphi^{2}}\cdot\log n\cdot k^{8}/{\xi}^{2})$

4:Let $I_{S}$ be the multiset of $s$ indices chosen independently and
uniformly at random from $\\{1,\ldots,n\\}$

5:for $i=1$ to $O(\log n)$ do

6:
${\widehat{Q}_{i}}:=\textsc{EstimateTransitionMatrix}(G,I_{S},R_{\text{init}},t)$
$\triangleright$ $\widehat{Q}_{i}$ has at most $R_{\text{init}}\cdot s$ non-
zeros

7:$\mathcal{G}:=$EstimateCollisionProbabilities$(G,I_{S},R_{\text{init}},t)$

8:Let
$\frac{n}{s}\cdot\mathcal{G}:=\widehat{W}\widehat{\Sigma}\widehat{W}^{T}$ be
the eigendecomposition of $\frac{n}{s}\cdot\mathcal{G}$ $\triangleright$
$\mathcal{G}\in\mathbb{R}^{s\times s}$

9:if $\widehat{\Sigma}^{-1}$ exists then

10:
$\Psi:=\frac{n}{s}\cdot\widehat{W}_{[k]}\widehat{\Sigma}_{[k]}^{-2}\widehat{W}_{[k]}^{T}$
$\triangleright$ $\Psi\in\mathbb{R}^{s\times s}$

11: return $\mathcal{D}:=\\{\Psi,\widehat{Q}_{1},\ldots,\widehat{Q}_{O(\log
n)}\\}$

Finally, we have the query algorithm.

Algorithm 5 SpectralDotProductOracle($G,x,y,\delta,\xi,\mathcal{D}$)
$\triangleright$ Need: $\epsilon/\varphi^{2}\leq\frac{1}{10^{5}}$
$\triangleright$
$\mathcal{D}:=\\{\Psi,\widehat{Q}_{1},\ldots,\widehat{Q}_{O(\log n)}\\}$

1:$R_{\text{query}}:=O{(n^{\delta+500\cdot\epsilon/\varphi^{2}}\cdot
k^{9}/{\xi}^{2})}$

2:for $i=1$ to $O(\log n)$ do

3: ${\widehat{m}^{i}_{x}:=\textsc{RunRandomWalks}(G,R_{\text{query}},t,x)}$

4: ${\widehat{m}^{i}_{y}:=\textsc{RunRandomWalks}(G,R_{\text{query}},t,y)}$

5:Let ${\alpha}_{x}$ be a vector obtained by taking the entrywise median of
$(\widehat{Q}_{i})^{T}(\widehat{m}^{i}_{x})$ over all runs

6:Let ${\alpha}_{y}$ be a vector obtained by taking the entrywise median of
$(\widehat{Q}_{i})^{T}(\widehat{m}^{i}_{y})$ over all runs

7:return $\left\langle f_{x},f_{y}\right\rangle_{\scriptscriptstyle
apx}:={\alpha}_{x}^{T}\Psi{\alpha}_{y}$

Let $I_{S}=\\{i_{1},\ldots,i_{s}\\}$ be a multiset of $s$ indices chosen
independently and uniformly at random from $\\{1,\dots,n\\}$. Let $S$ be the
$n\times s$ matrix whose $j$-th column equals $\mathds{1}_{i_{j}}$. As already
explained in detail in the technical overview, we first prove stability bounds
for the pseudoinverse. Then we show that that $M^{t}$ is approximated by
$M^{t}S$ and finally we show that algorithm RunRandomWalks approximates the
$M^{t}\mathds{1}_{x}$ sufficiently well. We conclude with the proof of Theorem
2.

###  5.2 Stability bounds for the low rank approximation

The main result of this section is a bound on the stability of the
pseudoinverse of the rank-$k$ approximation of two symmetric, positive semi-
definite matrices $A,\widetilde{A}\in\mathbb{R}^{n\times n}$ that are
spectrally close and that have an eigenvalue gap between the $k$-th and
$(k+1)$-st eigenvalue. In order to prove this result, we use Weyl’s
inequality, which gives bounds on the eigenvalues of the sum of a matrix $A$
and a perturbation matrix $P$. Recall that for a symmetric matrix $A$, we
write $\nu_{i}(A)$ (resp. $\nu_{\max}(A),\nu_{\min}(A))$ to denote the
$i^{\text{th}}$ largest (resp. maximum, minimum) eigenvalue of $A$.

######  Lemma 17 (Weyl’s Inequality).

Let $A,P\in\mathbb{R}^{n\times n}$ be two symmetric matrices. Then we have for
all $i\in\\{1,\dots,n\\}$:

$\nu_{i}(A)+\nu_{\min}(P)\leq\nu_{i}(A+P)\leq\nu_{i}(A)+\nu_{\max}(P),$

where for a symmetric matrix $H\in\mathbb{R}^{n\times n}$ $\nu_{i}(H)$ denotes
its $i^{\text{th}}$ largest eigenvalue and $\nu_{\min}(H)$ and $\nu_{\max}(H)$
refer to the smallest and largest eigenvalues of $H$.

We will use the Davis-Kahan $\sin(\theta)$ Theorem [DK70] (the version given
in the note [DK]).

######  Theorem 5 (Davis-Kahan $sin(\theta)$-Theorem [DK70]).

. Let $H=E_{0}A_{0}E_{0}^{T}+E_{1}A_{1}E_{1}^{T}$ and
$\widetilde{H}=F_{0}\Lambda_{0}F_{0}^{T}+F_{1}\Lambda_{1}F_{1}^{T}$ be
symmetric real-valued matrices with $E_{0},E_{1}$ and $F_{0},F_{1}$
orthogonal. If the eigenvalues of $A_{0}$ are contained in an interval
$(a,b)$, and the eigenvalues of $\Lambda_{1}$are excluded from the interval
$(a-\eta,b+\eta)$for some $\eta>0$, then for any unitarily invariant norm
$\|.\|$

$\|F_{1}^{T}E_{0}\|\leq\frac{\|F_{1}^{T}(\widetilde{H}-H)E_{0}\|}{\eta}\text{.}$

Let $m\leq n$ be integers. For any matrix $A\in\mathbb{R}^{n\times m}$ with
singular value decomposition (SVD) $A=Y\Gamma Z^{T}$ we assume
$Y\in\mathbb{R}^{n\times n}$, $\Gamma\in\mathbb{R}^{n\times n}$ is a diagonal
matrix of singular values and $Z\in\mathbb{R}^{m\times n}$ (this is a slightly
non-standard definition of the SVD, but having $\Gamma$ be a square matrix
will be convenient). $Y$ has orthonormal columns, the first $m$ columns of $Z$
are orthonormal, and the rest of the columns of $Z$ are zero. For any integer
$q\in[m]$ we denote $Y_{[q]}\in\mathbb{R}^{n\times q}$ as the first $q$
columns of $Y$ and $Y_{-[q]}$ to denote the matrix of the remaining columns of
$Y$. We also denote by $Z_{[q]}\in\mathbb{R}^{m\times q}$ as the first $q$
columns of $Z$ and $Z_{-[q]}$ to denote the matrix of the remaining $n-q$
columns of $Z$. Finally we denote by $\Gamma_{[q]}\in\mathbb{R}^{q\times q}$
the submatrix of $\Gamma$ corresponding to the first $q$ rows and columns of
$\Gamma$ and we use $\Gamma_{-[q]}$ to denote the submatrix corresponding to
the last $n-q$ rows and $n-q$ columns of $\Gamma$. So for any $q\in[m]$ the
span of $Y_{-[q]}$ is the orthogonal complement of the span of $Y_{[q]}$ in
$\mathbb{R}^{n}$, also the span of the columns of $Z_{-[q]}$ is the orthogonal
complement of the span of $Z_{[q]}$ in $\mathbb{R}^{m}$. Thus we can write
$A=Y_{[q]}\Gamma_{[q]}Z^{T}_{[q]}+Y_{-[q]}\Gamma_{-[q]}Z^{T}_{-[q]}$.

######  Claim 1.

For every symmetric matrix $E$ and every pair of orthogonal projection
matrices $P,\widetilde{P}$ one has

$\begin{split}||P\cdot E\cdot P-\widetilde{P}\cdot
E\cdot\widetilde{P}||_{2}\leq
2\|E\|_{2}\cdot(\|P\cdot(I-\widetilde{P})\|_{2}+\|\widetilde{P}\cdot(I-P)\|_{2}).\end{split}$

###### Proof.

Since $\widetilde{P}+(I-\widetilde{P})=I$ we can write

$\displaystyle P\cdot E\cdot P$
$\displaystyle=(\widetilde{P}+(I-\widetilde{P}))P\cdot E\cdot
P\cdot(\widetilde{P}+(I-\widetilde{P}))$ $\displaystyle=P\cdot E\cdot
P\cdot(I-\widetilde{P})+\widetilde{P}\cdot P\cdot E\cdot
P\cdot\widetilde{P}+(I-\widetilde{P})\cdot P\cdot E\cdot P\cdot\widetilde{P}$
(52)

Since $P+(I-P)=I$ we have

$\displaystyle\widetilde{P}\cdot E\cdot\widetilde{P}$
$\displaystyle=\widetilde{P}(P+(I-P))\cdot
E\cdot\left(P+(I-P)\right)\widetilde{P}||_{2}$
$\displaystyle=\widetilde{P}\cdot E\cdot(I-P)\widetilde{P}+\widetilde{P}\cdot
P\cdot E\cdot P\cdot\widetilde{P}+\widetilde{P}\cdot(I-P)\cdot E\cdot
P\cdot\widetilde{P}$ (53)

Putting (5.2) and (5.2) together and by triangle inequality we get

$\displaystyle||P\cdot E\cdot P-\widetilde{P}\cdot E\cdot\widetilde{P}||_{2}$
$\displaystyle\leq\|P\cdot E\cdot
P\cdot(I-\widetilde{P})\|_{2}+\|(I-\widetilde{P})\cdot P\cdot E\cdot
P\cdot\widetilde{P}\|_{2}+\|\widetilde{P}\cdot
E\cdot(I-P)\widetilde{P}\|_{2}+\|\widetilde{P}\cdot(I-P)\cdot E\cdot
P\cdot\widetilde{P}\|_{2}$

Thus by submultiplicativity of the operator norm we get

$\displaystyle||P\cdot E\cdot P-\widetilde{P}\cdot E\cdot\widetilde{P}||_{2}$
$\displaystyle\leq\|P\|_{2}\|E\|_{2}\|P\cdot(I-\widetilde{P})\|_{2}+\|(I-\widetilde{P})\cdot
P\|_{2}\|E\|_{2}\|P\|_{2}\|\widetilde{P}\|_{2}+\|\widetilde{P}\|_{2}\|E\|_{2}\|(I-P)\widetilde{P}\|_{2}+\|\widetilde{P}\|_{2}\|E\|_{2}\|(I-P)\widetilde{P}\|_{2}$
$\displaystyle\leq\|E\|_{2}\left(\|P\cdot(I-\widetilde{P})\|_{2}+\|(I-\widetilde{P})\cdot
P\|_{2}+\|(I-P)\widetilde{P}\|_{2}+\|\widetilde{P}(I-P)\|_{2}\right)\text{~{}Since
$||P||=||\widetilde{P}||_{2}=1$}$
$\displaystyle=2\cdot\|E\|_{2}\cdot(\|P\cdot(I-\widetilde{P})\|_{2}+\|\widetilde{P}\cdot(I-P)\|_{2}),$

where the last equality holds since
$\|P\cdot(I-\widetilde{P})\|_{2}=\|(I-\widetilde{P})^{T}\cdot
P^{T}\|_{2}=\|(I-\widetilde{P})\cdot P\|_{2}$ and similarly since
$\|\widetilde{P}\cdot(I-P)\|_{2}=\|(I-P)^{T}\cdot\widetilde{P}^{T}\|_{2}=\|(I-P)\cdot\widetilde{P}\|_{2}$.
∎

Recall that for matrices $A,\widetilde{A}\in\mathbb{R}^{n\times n}$, we write
$A\preccurlyeq\widetilde{A}$, if $\forall x\in\mathbb{R}^{n}$ we have
$x^{T}Ax\leq x^{T}\widetilde{A}x$ and we write $A\prec\widetilde{A}$, if
$\forall x\in\mathbb{R}^{n}$ we have $x^{T}Ax<x^{T}\widetilde{A}x$. Now we can
state the main technical result of this section (Lemma 18), whose proof relies
on matrix perturbation bounds Davis-Kahan $\sin\theta$ theorem (Theorem 5).

We will need the following claim, whose proof is inspired by the proof of the
operator monotonicity of negative matrix inverse [Tod11]:

######  Claim 2.

Let $A,B\in\mathbb{R}^{n\times n}$ be symmetric positive semidefinite
matrices. Let $\Pi_{B}$ denote orthogonal projection operator onto the range
space of $B$. Then if $A\succeq B$, we have for every orthogonal projection
$\Pi_{A}$ satisfying $\Pi_{A}A^{+}=A^{+}\Pi_{A}$ that

$(\Pi_{A}A\Pi_{A})^{+}\preceq
B^{+}+2\|\Pi_{A}A^{+}\|_{2}\|\Pi_{A}(I-\Pi_{B})\|_{2}\cdot I.$

###### Proof.

For every $x\in\mathbb{R}^{n}$, and every $y\in\mathbb{R}^{n}$ (to be chosen
as $y=A^{+}x$ later) since $B$ is positive semidefinite we have

$(y-B^{+}x)^{T}B(y-B^{+}x)\geq 0,$

which in particular implies that

$y^{T}By-2x^{T}B^{+}By+x^{T}B^{+}x\geq 0,$

and since $A\succeq B$ by assumption,

$y^{T}Ay-2x^{T}B^{+}By+x^{T}B^{+}x\geq 0.$

We now chose $y=\Pi_{A}A^{+}x$ and rearrange, getting

$2x^{T}B^{+}B\Pi_{A}A^{+}x-x^{T}\Pi_{A}A^{+}\Pi_{A}x\leq x^{T}B^{+}x.$ (54)

Noting that $B^{+}B=\Pi_{B}$ and $\Pi_{A}\Pi_{A}A^{+}=\Pi_{A}A^{+}\Pi_{A}$, we
write the lhs of (54) as

$\begin{split}2x^{T}\Pi_{B}\Pi_{A}A^{+}x-x^{T}\Pi_{A}A^{+}\Pi_{A}x&=2x^{T}\Pi_{A}A^{+}\Pi_{A}x+2x^{T}(\Pi_{B}\Pi_{A}-\Pi_{A})\Pi_{A}A^{+}x-x^{T}\Pi_{A}A^{+}\Pi_{A}x\\\
&=x^{T}\Pi_{A}A^{+}\Pi_{A}x+2x^{T}((\Pi_{B}-I)\Pi_{A})\Pi_{A}A^{+}x.\end{split}$

Substituting the above into (54), and noting that

$|x^{T}(\Pi_{B}\Pi_{A}-\Pi_{A})\Pi_{A}A^{+}x|\leq\|\Pi_{A}A^{+}\|_{2}\cdot\|(\Pi_{B}-I)\Pi_{A}\|_{2}\cdot
x^{T}x,$

we get

$\begin{split}x^{T}\Pi_{A}A^{+}\Pi_{A}x\leq
x^{T}B^{+}x+2\|\Pi_{A}A^{+}\|_{2}\cdot\|(\Pi_{B}-I)\Pi_{A}\|_{2}\cdot
x^{T}x.\end{split}$

The above holds for all $x\in\mathbb{R}^{n}$. Also,
$\|(\Pi_{B}-I)\Pi_{A}\|_{2}=\|\Pi_{A}(I-\Pi_{B})\|_{2}$, since
$\Pi_{A},\Pi_{B}$ are projection matrices. Therefore, for all
$x\in\mathbb{R}^{n}$ we have

$\begin{split}\Pi_{A}A^{+}\Pi_{A}\preceq
B^{+}+2\|\Pi_{A}A^{+}\|_{2}\cdot\|\Pi_{A}(I-\Pi_{B})\|_{2}\cdot I,\end{split}$

as required. ∎

######  Lemma 18.

Let $A,\widetilde{A}\in\mathbb{R}^{n\times n}$ be symmetric matrices with
eigendecompositions $A=Y\Gamma Y^{T}$ and
$\widetilde{A}=\widetilde{Y}\widetilde{\Gamma}\widetilde{Y}^{T}$. Let the
eigenvalues of $A$ be $1\geq\gamma_{1}\geq\dots\geq\gamma_{n}\geq 0$. Suppose
that $\|A-\widetilde{A}\|_{2}\leq\frac{\gamma_{k}}{100}$ and
$\gamma_{k+1}<\gamma_{k}/4$. Then we have

$\|Y_{[k]}\Gamma^{-1}_{[k]}Y^{T}_{[k]}-\widetilde{Y}_{[k]}\widetilde{\Gamma}^{-1}_{[k]}\widetilde{Y}^{T}_{[k]}\|_{2}\leq\frac{16\|A-\widetilde{A}\|_{2}+4\gamma_{k+1}}{\gamma_{k}^{2}}\text{.}$

###### Proof.

We define $P=Y_{[k]}Y^{T}_{[k]}$ and
$\widetilde{P}=\widetilde{Y}_{[k]}\widetilde{Y}^{T}_{[k]}$, and let
$M=PAP=Y_{[k]}\Gamma_{[k]}Y^{T}_{[k]}$ and
$\widetilde{M}=\widetilde{P}\widetilde{A}\widetilde{P}=\widetilde{Y}_{[k]}\widetilde{\Gamma}_{[k]}\widetilde{Y}^{T}_{[k]}$.
First note that

$\displaystyle\widetilde{M}$
$\displaystyle=\widetilde{P}\widetilde{A}\widetilde{P}$
$\displaystyle\preceq\widetilde{P}(\widetilde{A}+\|A-\widetilde{A}\|_{2}\cdot
I)\widetilde{P}$
$\displaystyle\preceq\widetilde{P}(\widetilde{A}+\|A-\widetilde{A}\|_{2}\cdot
I)\widetilde{P}+(I-\widetilde{P})(\widetilde{A}+\|A-\widetilde{A}\|_{2}\cdot
I)(I-\widetilde{P})$ $\displaystyle=\widetilde{A}+\|A-\widetilde{A}\|_{2}\cdot
I$ $\displaystyle\preceq A+2\|A-\widetilde{A}\|_{2}\cdot I$
$\displaystyle=P(A+2\|A-\widetilde{A}\|_{2}\cdot
I)P+(I-P)(A+2\|A-\widetilde{A}\|_{2}\cdot I)(I-P)$ $\displaystyle\preceq
M+(2\|A-\widetilde{A}\|_{2}+\gamma_{k+1})I$ $\displaystyle=M+\eta\cdot I,$
(55)

where we let $\eta=2\|A-\widetilde{A}\|_{2}+\gamma_{k+1}$. The transition from
line 2 to line 3 is due to the fact that
$\widetilde{A}+\|A-\widetilde{A}\|_{2}\cdot I\succeq A\succeq 0$, and
therefore $(I-\widetilde{P})(\widetilde{A}+\|A-\widetilde{A}\|_{2}\cdot
I)(I-\widetilde{P})\succeq 0$. The transition from line 4 to line 5 is due to
$\widetilde{A}\preceq A+\|A-\widetilde{A}\|_{2}\cdot I$. The transition from
line 6 to line 7 is due to the fact that $(I-P)A(I-P)\preceq\gamma_{k+1}I$.

Similarly,

$\begin{split}M&=PAP\\\ &\preceq PAP+(I-P)A(I-P)\\\ &=A\\\
&\preceq\widetilde{A}+\|A-\widetilde{A}\|_{2}\cdot I\\\
&=\widetilde{P}(\widetilde{A}+\|A-\widetilde{A}\|_{2}\cdot
I)\widetilde{P}+(I-\widetilde{P})(\widetilde{A}+\|A-\widetilde{A}\|_{2}\cdot
I)(I-\widetilde{P})\\\
&\preceq\widetilde{M}+(2\|A-\widetilde{A}\|_{2}+\gamma_{k+1})I.\end{split}$
(56)

The transition from line 1 to line 2 is due to the fact that $A\succeq 0$, and
therefore $(I-P)A(I-P)^{T}\succeq 0$. The transition from line 3 to line 4 is
due to $A\preceq\widetilde{A}+\|A-\widetilde{A}\|_{2}\cdot I$. The transition
from line 5 to line 6 is due to the fact that

$(I-\widetilde{P})\widetilde{A}(I-\widetilde{P})\preceq\nu_{k+1}(\widetilde{A})\cdot
I\preceq(\|A-\widetilde{A}\|_{2}+\gamma_{k+1})I.$

We now apply Claim 2 with $A=M+(2\|A-\widetilde{A}\|_{2}+\gamma_{k+1})I$,
$\Pi_{A}=P$, $B=\widetilde{M}$ and $\Pi_{B}=\widetilde{P}$. Note that A is
symmetric and positive semidefinite. Also, $B$ is symmetric and positive
semidefinite because
$\nu_{\min}(B)=\nu_{k}(\widetilde{A})\geq\nu_{k}(A)-||A-\widetilde{A}||_{2}\geq\frac{99\cdot\gamma_{k}}{100}\geq
0$ by Weyl’s inequality and the fact that
$||A-\widetilde{A}||_{2}\leq\frac{\gamma_{k}}{100}$. Note that
$\Pi_{A}A^{+}=A^{+}\Pi_{A}$, as required, and $A\succeq B$ by (5.2). We get

$\displaystyle\widetilde{M}^{+}$ $\displaystyle\succeq(P(M+\eta
I)P)^{+}-2\|P(M+\eta I)^{+}P\|_{2}\cdot\|P(I-\widetilde{P})\|_{2}\cdot I$
$\displaystyle\succeq Y_{[k]}(\Gamma_{[k]}+\eta
I_{k})^{-1}Y^{T}_{[k]}+\frac{2}{\gamma_{k}}\cdot\|P(I-\widetilde{P})\|_{2}\cdot
I\text{~{}~{}~{}~{}~{}(since $\|P(M+\eta I)^{+}P\|_{2}\leq 1/\gamma_{k}$)}$