A Local Clustering Algorithm for Massive Graphs and its Application to Nearly-Linear Time Graph Partitioning

Introduction

Given a vertex of interest in a massive graph, we would like to find a small cluster around that vertex, in time proportional to the size of the cluster. The algorithm we introduce will solve this problem while only examining vertices near the initial vertex, under some reasonable notion of nearness. We call such an algorithm a local algorithm.

Our local clustering algorithm provides a very powerful primitive for the design of fast graph algorithms. In Section 3 of this paper, we use it to design the first nearly-linear time algorithm for graph partitioning that produces a partition of nearly-optimal balance among those approximating a target conductance. In the papers [ST08b] and [ST08a], we proceed to use this graph partitioning algorithm to design nearly-linear time algorithms for sparsifying graphs and for solving symmetric, diagonally-dominant linear systems.

We say that a graph algorithm is a local algorithm if it is given a particular vertex as input, and at each step after the first only examines vertices connected to those it has seen before. The use of a local algorithm naturally leads to the question of in which order one should explore the vertices of a graph. While it may be natural to explore vertices in order of shortest-path distance from the input vertex, such an ordering is a poor choice in graphs of low-diameter, such as social network graphs [LH08]. We suggest first processing the vertices that are most likely to occur in short random walks from at the input vertex. That is, we consider a vertex to be near the input vertex if it is likely to appear in a short random walk from the input vertex.

In Section 3, we use a local graph exploration process to find a cluster that is near the input vertex. Following Kannan, Vempala and Vetta [KVV04], we say that a set of vertices is a good cluster if it has low conductance; that is, if it has many more external than internal edges. We give an efficient local clustering algorithm, Nibble, that runs in time proportional to the size of the cluster it outputs. Although our algorithm may not find a local cluster for some input vertices, we will show that it is usually successful. In particular, we prove the following theorem: There exists a constant $\alpha>0$ such that for any target conductance $\phi$ and any cluster $C_{0}$ of conductance at most $\alpha\cdot\phi^{2}/\log^{3}n$, when given a random vertex $v$ sampled according to degree inside $C_{0}$, Nibble will return a cluster $C$ mostly inside $C_{0}$ and with conductance at most $\phi$, with probability at least $1/2$.

The local clustering algorithm Nibble makes a novel use of random walks. For a positive integer $t$, suppose $p_{t,v}$ is the probability distribution of the $t$-step random walk starting at $v$. As the support of $p_{t,v}$—the set of nodes with positive probability—could grow rapidly, Nibble maintains a truncated version of the distribution. At each step of the truncated random walks, Nibble looks a for cluster among only nodes with high probability. The truncation is critical to ensure that the clustering algorithm is output sensitive. It guarantees that the size of the support of the distribution that Nibble maintains is not too much larger than the size of the cluster it produces. The cluster that Nibble produces is local to the starting vertex $v$ in the sense that it consists of nodes that are among the most favored destinations of random walks starting from $v$.

By using the personal PageRank vector [PBMW98] to define nearness, Andersen, Chung and Lang [ACL06], have produced an improved version of our algorithm Nibble, which they call PageRank-Nibble. Following this work, other local algorithms have been designed by Andersen et. al. [ABC+07] for approximately computing Personal PageRank vectors, by Andersen [And08] for finding dense subgraphs and by Andersen, Chung and Lang [ACL07] for partitioning directed graphs.

2 Nearly Linear-Time Algorithms

Our local clustering algorithm provides a powerful tool for designing fast graph algorithms. In this paper and its two companion papers, we show how to use it to design randomized, nearly linear-time algorithms for several important graph-theoretic and numerical problems.

The need for algorithms whose running time is linear or nearly linear in their input size has increased as algorithms handle larger inputs. For example, in circuit design and simulation, an Intel Dual Core Itanium processor has more than one billion transistors, which is more than 100 times the number of transistors that the Pentium had in 2000 [Cor05]; in scientific computing, one often needs to solve linear systems that involve hundreds of millions of variables [SLM+02]; in modern information infrastructure, the web has grown into a graph of hundreds billions of nodes [GS05]. As a result of this rapid growth in problem size, what used to be considered an efficient algorithm, such as a $O(n^{1.5})$-time algorithm, may no longer be adequate for solving problems of these scales. Space complexity poses an even greater problem.

Many basic graph-theoretic problems such as connectivity and topological sorting can be solved in linear or nearly-linear time. The efficient algorithms for these problems are built on linear-time primitives such as Breadth-First-Search (BFS) and Depth-First-Search (DFS). Minimum Spanning Trees (MST) and Shortest-Path Trees are examples of other commonly used nearly linear-time primitives. We hope to build up the library of nearly-linear time graph algorithms that may be used as primitives. While the analyzable variants of the algorithms we present here, and even their improved versions by Andersen, Chung and Lang [ACL06], may not be immediately useful in practice, we believe practical algorithms may be derived from them by making less conservative choices of parameters.

Our local clustering algorithm provides an exciting new primitive for developing nearly linear-time graph algorithms. Because its running time is proportional to the size of the cluster it produces, we can repeatedly apply it remove many clusters from a graph, all within nearly-linear time.

In the second part of this paper, we use Nibble as a subroutine to construct a randomized graph partitioning algorithm that runs in nearly-linear time. To the best of our knowledge, this is the first nearly linear-time partitioning algorithm that finds an approximate sparsest cut with approximately optimal balance. In our first companion paper [ST08b], we apply this new partitioning algorithm to develop a nearly-linear-time algorithm for producing spectral sparsifiers of graphs. We begin that paper by extending the partitioning algorithm of this paper to obtain a stronger guarantee on its output: if it outputs a small set, then the complement must be contained in a subgraph whose conductance is higher than the target.

Clusters and Conductance

Let $G=(V,E)$ be an undirected graph with $V=\left\{1,\dotsc,n\right\}$. A cluster of $G$ is a subset of $V$ that is richly intra-connected but sparsely connected with the rest of the graph. The quality of a cluster can be measured by its conductance, the ratio of the number of its external connections to the number of its total connections.

We let $d(i)$ denote the degree of vertex $i$. For $S\subseteq V$, we define $\mu\left(S\right)=\sum_{i\in S}d(i)$ (often called the volume of $S$). So, $\mu\left(V\right)=2|E|$. Let $E(S,V-S)$ be the set of edges connecting a vertex in $S$ with a vertex in $V-S$. We define the conductance of a set of vertices $S$, written $\Phi\left(S\right)$ by

We sometime refer to a subset $S$ of $V$ as a cut of $G$ and refer to $(S,V-S)$ as a partition of $G$. The balance of a cut $S$ or a partition $(S,V-S)$ is then equal to

We call $S$ a sparsest cut of $G$ if $\Phi\left(S\right)=\Phi_{G}{}$ and $\mu\left(S\right)/\mu\left(V\right)\leq 1/2$.

In the construction of a partition of $G$, we will be concerned with vertex-induced subgraphs of $G$. However, when measuring the conductance and volumes of vertices in these vertex-induced subgraphs, we will continue to measure the volume according to the degrees of vertices in the original graph. For clarity, we define the conductance of a set $S$ in the subgraph induced by $A\subseteq V$ by

For convenience, we define $\Phi^{G}_{A}\left(\emptyset\right)=1$ and, for $\left|A\right|=1$, $\Phi^{G}_{A}{}=1$.

For $A\subseteq V$, we let $G(A)$ denote the subgraph of $G$ induced by the vertices in $A$. We introduce the notation $G[A]$ to denote graph $G(A)$ to which self-loops have been added so that every vertex in $G[A]$ has the same degree as in $G$. Each self-loop adds 1 to the degree. We remark that if $G(A)$ is the subgraph of $G$ induced on the vertices in $A$, then

So, when we prove lower bounds on $\Phi^{G}_{A}{}$, we obtain lower bounds on $\Phi_{G(A)}{}$.

Clustering is an optimization problem: Given an undirected graph $G$ and a conductance parameter, find a cluster $C$ such that $\Phi\left(C\right)\leq\phi$, or determine no such cluster exists. The problem is NP-complete (see, for example [LR99] or [SS06]). But, approximation algorithms exist. Leighton and Rao [LR99] used linear programming to obtain $O(\log n)$-approximations of the sparsest cut. Arora, Rao and Vazirani [ARV04] improved this to $O(\sqrt{\log n})$ through semi-definite programming. Faster algorithms obtaining similar guarantees have been constructed by Arora, Hazan and Kale [AHK04], Khandekar, Rao and Vazirani [KRV06], Arora and Kale [AK07], and Orecchia, Schulman, Vazirani, and Vishnoi [OSVV08].

The algorithm Nibble works by approximately computing the distribution of a few steps of the random walk starting at a seed vertex $v$. It is implicit in the analysis of the volume estimation algorithm of Lovász and Simonovits [LS93] that one can find a cut with small conductance from the distributions of the steps of the random walk starting at any vertex from which the walk does not mix rapidly. We will observe that a random vertex in a set of low conductance is probably such a vertex. We then extend the analysis of Lovász and Simonovits to show one can find a cut with small conductance from approximations of these distributions, and that these approximations can be computed quickly. In particular, we will truncate all small probabilities that appear in the distributions to 0. In this way, we reduce the work required to compute our approximations.

For the rest of this section, we will work with a graph $G=(V,E)$ with $n$ vertices and $m$ edges, so that $\mu\left(V\right)=2m$. We will allow some of these edges to be self-loops. Except for the self-loops, which we allow to occur with multiplicities, the graph is assumed to be unweighted. We will let $A$ be the adjacency matrix of this graph. That is,

We define the following two vectors supported on a set of vertices $S$:

We will consider the random walk that at each time step stays at the current vertex with probability $1/2$, and otherwise moves to the endpoint of a random edge attached to the current vertex. Thus, self-loops increase the chance the walk stays at the current vertex. For example, if a vertex has $4$ edges, one of which is a self-loop, then when the walk is at this vertex it has a $5/8$ chance of staying at that vertex, and a $1/8$ chance of moving to each of its $3$ neighbors.

The matrix realizing this walk can be expressed by $M=(AD^{-1}+I)/2$, where $d(i)$ is the degree of node $i$, and $D$ is the diagonal matrix with diagonal entries $(d(1),\dotsc,d(n))$. Typically, a random walk starts at a node $v$. In this case, the distribution of the random walk at time $t$ evolves according to $p_{t}=M^{t}\chi_{v}$.

We note that $\psi_{V}$ is the steady-state distribution of the random walk, and that $\psi_{S}$ is the restriction of that walk to the set $S$.

We will use the truncation operation defined by

Our algorithm, Nibble, will generate the sequence of vectors starting at $\chi_{v}$ by the rules

That is, at each time step, we will evolve the random walk one step from the current density, and then round every $q_{t}(u)$ that is less than $d(u)\epsilon$ to 0. Note that $q_{t}$ and $r_{t}$ are not necessarily probability vectors, as their components may sum to less than $1$.

In the statement of the algorithm and its analysis, we will use the following notation. For a vector $p$, we let $S_{j}(p)$ be the set of $j$ vertices $u$ maximizing $p(u)/d(u)$, breaking ties lexicographically. That is, $S_{j}(p)=\left\{\pi(1),\dotsc,\pi(j)\right\}$ where $\pi$ is the permutation such that

for all $i$, and $\pi(i)<\pi(i+1)$ when these two ratios are equal. We then set

Note that $\lambda_{n}(p)$ always equals $2m$.

Following Lovász and Simonovits [LS90], we set

This function $I(p,\cdot)$ is essentially the same as the function $h$ defined by Lovász and Simonovits—it only differs by a linear transformation.

We remark that for $x=\lambda_{j}(p)$, $I(p,x)=p(S_{j}(p))$, and that $I(p,x)$ is linear in $x$ between these points. Finally, we let $I_{x}(p,x)$ denote the partial derivative of $I(p,x)$ with respect to $x$, with the convention that for $x=\lambda_{j}(p)$,

where $\pi$ is the permutation specified above so that $\pi(j)=S_{j}(p)-S_{j-1}(p)$.

As $p(\pi(i))/d(\pi(i))$ is non-increasing, $I_{x}(p,x)$ is a non-increasing function in $x$ and $I(p,x)$ is a concave function in $x$.

During the course of our exposition, we will need to set many constants, which we collect here for convenience. For each, we provide a suitable value and indicate where it is first used in the paper.

The following is an exhaustive list of the inequalities we require these constants to satisfy.

Given a $\phi$, we set constants that will play a prominent role in our analysis:

Condition (C.1) guarantees that the set $C$ has low conductance. Condition (C.2) ensures that it does not contain too much volume, while condition (C.3) ensures that it does not contain too little. Condition (C.4) guarantees that many elements of $C$ have large probability mass. While it would be more natural to define condition (C.4) as a constraint on $I_{x}(q_{t},\lambda_{j}(q_{t}))$ instead of $I_{x}(q_{t},2^{b})$, our proof of correctness requires the latter.

In the rest of this section, we will prove the following theorem on the performance of Nibble.

Nibble can be implemented so that on all inputs, it runs in time $O(2^{b}(\log^{6}m)/\phi^{4})$. Moreover, Nibble satisfies the following properties.

When $C=\mbox{\rm{Nibble}}(G,v,\phi,b)$ is non-empty,

$\mu\left(S^{g}\right)\geq\mu\left(S\right)/2$, and

$v\in S^{g}$ and $C=\mbox{\rm{Nibble}}(G,v,\phi,b)\not=\emptyset$ imply $\mu\left(C\cap S\right)\geq 2^{b-1}$.

2 Basic Inequalities about Random Walks

We first establish some basic inequalities that will be useful in our analysis. Readers who are eager to see the analysis of Nibble can first skip this subsection. Suppose $G=(V,E)$ is an undirected graph. Recall $M=(AD^{-1}+I)/2$, where $A$ is the adjacency matrix of $G$.

Applying the transformation $z=D^{-1}p$, we see that it is equivalent to show that for all $z$

To prove this, we note that $D^{-1}MD=D^{-1}(AD^{-1}+I)D/2=M^{T}$, and the sum of the entries in each row of this matrix is 1. ∎

For a set $S\subseteq V$, we define the matrix $D_{S}$ to be the diagonal matrix such that $D_{S}(u,u)=1$ if $u\in S$ and $0$ otherwise.

For every $S\subseteq V$, all non-negative vectors $p$ and $q$, and every $t\geq 1$,

as $p$, $q$, $D_{\bar{S}}$, and $M$ are all non-negative. The proposition now follows by induction. ∎

For all $t\geq 0$ and for all $S\subset V$,

Note that $M\psi_{S}$ is the distribution after a single-step walk from a random vertex in $S$ and {\mbox{\boldmath1}}^{T}D_{S}(M\psi_{S}) is the probability that the walk stays inside $S$. Thus, {\mbox{\boldmath1}}^{T}(D_{S}M)^{t}\psi_{S} is the probability that a $t$-step walk starting from a random vertex in $S$ stays entirely in $S$.

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

The base case, $t=0$, follows from the fact that $\left\|D^{-1}\psi_{S}\right\|_{\infty}=1/\mu\left(S\right)$. To complete the induction, observe that if $x$ is a non-negative vector such that $\left\|D^{-1}x\right\|_{\infty}\leq 1/\mu\left(S\right)$, then

where the second-to-last inequality follows from Proposition 2.2.

from which the proposition follows, as {\mbox{\boldmath1}}^{T}\psi_{S}=1.

Observing that {\mbox{\boldmath1}}^{T}M={\mbox{\boldmath1}}^{T}, we compute

3 The Analysis of Nibble

Our analysis of Nibble consists of three main steps. First, we define the sets $S^{g}$ mentioned in Theorem 2.1 and establish property (N.2). We then refine the structure of $S^{g}$ to define sets $S_{b}^{g}$ and prove property (N.3). The sets $S^{g}$ and $S^{g}_{b}$ are defined in terms of the distributions of random walks from a vertex in $S$, without reference to the truncation we perform in the algorithm. We then analyze the impact of truncation used in Nibble and extend the theory of Lovász and Simonovits [LS93] to truncated random walks.

Step 1: SgS^{g} and its properties

For each set $S\subseteq V$, we define $S^{g}$ to be the set of nodes $v$ in $S$ such that for all $t\leq t_{last}$,

Note that $\chi_{\bar{S}}^{T}M^{t}\chi_{v}$ denotes the probability that a $t$-step random walk starting from $v$ terminates outside $S$. Roughly speaking, $S^{g}$ is the set of vertices $v\in S$ such that a random walk from $v$ it is reasonably likely to still be in $S$ after $t_{last}$ time steps. We will prove the following bound on the volume of $S^{g}$.

Let $S\subseteq V$, and let $D_{S}$ be the diagonal matrix such that $D_{S}(u,u)=1$ if $u\in S$ and $0$ otherwise. For $t\geq 0$,

as {\mbox{\boldmath1}}^{T}(D_{S}M)^{t}\chi_{v} is a non-increasing function of $t$. Define

So, $S^{\prime}\subseteq S^{g}$, and it suffices to prove that $\mu\left(S^{\prime}\right)\geq\mu\left(S\right)/2$.

We now prove the following lemma, which says that if Nibble is started from any $v\in S^{g}$ with parameter $b$ and returns a non-empty set $C$, then $\mu\left(C\cap S\right)\geq 2^{b-1}$.

Let $S\subseteq V$ be a set of vertices such that $\Phi(S)\leq f_{1}(\phi)$. If Nibble is run with parameter $b$, is started at a $v\in S^{g}$, and outputs a non-empty set $C$, then $\mu\left(C\cap S\right)\geq 2^{b-1}$.

For $v\in S^{g}$, let $q_{t}$ be given by (1) and (2). Then, for $t\leq t_{last}$,

where the second inequality follows from the definition of $S^{g}$.

Let $t$ be the index of the step at which the set $C$ is generated. Let $j^{\prime}$ be the least integer such that $\lambda_{j^{\prime}}(q_{t})\geq 2^{b}$. Condition (C.3) implies $j^{\prime}\leq j$. As $I_{x}$ is non-increasing in its second argument and constant between $2^{b}$ and $\lambda_{j^{\prime}}(q_{t})$, Condition $(C.4)$ guarantees that for all $u\in S_{j^{\prime}}(q_{t})$,

by (4). So, $\mu\left(S_{j^{\prime}}(q_{t})\cap S\right)\geq 2^{b-1}$, and, as $j^{\prime}\leq j$,

Step 2: Refining SgS^{g}

Before defining the sets $S^{g}_{b}$, we first recall some of the facts we can infer about the function $I$ from the work of Lovász and Simonovits. These facts will motivate our definitions and analysis.

In the first part of the proof of Lemma 1.4 of [LS90], Lovász and Simonovits prove

For every non-negative vector $p$ and every $x$,

For each $p_{t}$, $I(p_{t},x)$ is a concave function that starts at $(0,0)$ and goes to $(\mu\left(V\right),1)$. Lemma 2.9 says that for each $t$, the curve defined by $I(p_{t+1},\cdot)$ lies below the curve defined by $I(p_{t},\cdot)$. In particular,

If none of the sets $S_{j}(p_{t+1})$ has conductance less than $\phi$, then Lovász and Simonovits prove a bound on how far below $I(p_{t},\cdot)$ the curve of $I(p_{t+1},\cdot)$ must lie. The following Lemma is a special case of Lemma 1.4 of [LS93], restricted to points $x$ of the form $\lambda_{j}(Mp)$. Lovász and Simonovits [LS90] claim that the following is true for all $x$, but point out in the journal version of their paper [LS93] that this claim was false. Fortunately, we do not need the stronger claim.

For any non-negative vector $p$, if $\Phi(S_{j}(Mp))\geq\phi$, then for $x=\lambda_{j}(Mp)$,

where $\widehat{x}$ denotes $\min(x,2m-x)$.

The mistake in [LS90] is the assertion in the beginning of the proof that the inequality holds for all $x$ if it holds for all $x$ of form $\lambda_{j}(Mp)$.

When this lemma applies, one may draw a chord across the curve of $I(p_{t},\cdot)$ around $x$ of width proportional to $\phi$, and know that $I(p_{t+1},x)$ lies below. Thus, we know that if none of the sets $S_{j}(p_{t})$ has conductance less than $\phi$, then the curve $I(p_{t},\cdot)$ will approach a straight line. On the other hand, Proposition 2.5 will tell us that some point of $I(p_{t_{last}},\cdot)$ lies well above this line (see Lemma 2.14).

We write $x_{h}$ instead of $x_{h}(v)$ when $v$ is clear from context. Define

The quantities $h_{v}$ are well-defined and the sets $S^{g}_{b}$ partition $S^{g}$. Moreover, $x_{h-1}<x_{h}$ for all $h$.

Finally, to show that $x_{h-1}<x_{h}$, we apply Lemma 2.9 to show

As $I(p_{t_{h}},\cdot)$ is non-decreasing and

Step 3: Clustering and truncated random walks

We now establish that vectors produced by the truncated random walk do not differ too much from those produced by the standard random walk.

The left-hand inequalities of (20) are trivial. To prove the right-hand inequality of (20), we consider $p_{t}-\left[p_{t}\right]_{\epsilon}$, observe that by definition

and then apply Proposition 2.2. Inequality (21) then follows from (3). ∎

Let $S\subseteq V$ be a set of vertices such that $\mu\left(S\right)\leq(2/3)\mu\left(V\right)$ and $\Phi(S)\leq f_{1}(\phi)$, and let $v$ lie in $S^{g}_{b}$. Define $q_{t}$ by running Nibble is with parameter $b$.

Let $S\subseteq V$ be a set of vertices such that $\mu\left(S\right)\leq(2/3)\mu\left(V\right)$ and $\Phi(S)\leq f_{1}(\phi)$, and let $v$ lie in $S^{g}_{b}$. If Nibble is run with parameter $b$, then for all $t\in(t_{h_{v}-1},t_{h_{v}}]$, condition (C.4) is satisfied.

where the first inequality follows from Lemma 2.13 and the second follows from Lemma 2.9.

As $I_{x}(q_{t},x)$ is non-increasing in $x$ and $x_{h_{v}-1}<x_{h_{v}}\leq 2x_{h_{v}-1}$, we have

where the second inequality follows from Lemma 2.9 and the definition of $q_{t}$, and the last follows from (23).

If $x_{h_{v}-1}\geq 2$, then $b\geq 1$ and we have $2^{b}\leq x_{h_{v}-1}<2^{b+1}$, and so

If $x_{h_{v}-1}<2$, then $b=0$, and so $I_{x}(q_{t},2^{b})=I_{x}(q_{t},x)$ for all $x<1$, which implies

It remains to show that conditions (C.1–3) are met for some $t\in(t_{h_{v}-1},t_{h_{v}}]$. We will do this by showing that if at least one of these conditions fail for every $j$ and every $t\in(t_{h_{v}-1},t_{h_{v}}]$, then the curve $I(q_{t_{h}},\cdot)$ will be too low, in violation of Lemma 2.14.

We will prove by induction that the conditions of the lemma imply that for all $t\in[t_{h-1},t_{h}]$ and all $x$,

The base case is when $t=t_{h-1}$, in which case (24) is satisfied because

For $1\leq x\leq 2m-1$, $I(q_{t},x)\leq I(q_{t},2m)\leq 1\leq\sqrt{\widehat{x}}$.

For $0\leq x\leq 1$, we have $I(q_{t},x)\leq\sqrt{\widehat{x}}$ as both are $0$ at $x=0$, the right-hand term dominates at $x=1$, the left-hand term is linear in this region, and the right-hand term is concave.

For $2m-1\leq x\leq 2m$, we note that at $x=2m$, $I(q_{t},x)=1<3x/5m$, and that we already know the right-hand term dominates at $x=2m-1$. The inequality then follows from the facts that left-hand term is linear in this region, and the right-hand term is concave.

Lovász and Simonovits [LS90] observe that

We now prove that (24) holds for $t$, assuming it holds for $t-1$, by considering three cases. As the right-hand side is concave and the left-hand side is piecewise-linear between points of the form $\lambda_{j}(q_{t})$, it suffices to prove the inequality at the points $\lambda_{j}(q_{t})$. If $x=\lambda_{j}(q_{t})$ and $I(q_{t},x)\leq\beta$, then (24) holds trivially. Similarly, if $x=\lambda_{j}(q_{t})>(5/6)2m$, then (24) holds trivially as well, as the left-hand side is at most 1, and the right hand side is at least 1. In the other cases, we have $\Phi(S_{j}(q_{t}))\geq\phi$, in which case we may apply Lemma 2.10 to show that for $x=\lambda_{j}(q_{t})$

We now observe that $t_{1}$ has been chosen to ensure

Let $S$ be a set of vertices such that $\mu\left(S\right)\leq(2/3)(2m)$ and $\Phi(S)\leq f_{1}(\phi)$, and let $v$ lie in $S^{g}_{b}$. If Nibble is run with parameter $b$, then there exists a $t\in(t_{h_{v}-1},t_{h_{v}}]$ and a $j$ for which conditions (C.1-3) are satisfied.

4 Proof of Theorem 2.1

Fact (N.1) follows from conditions (C.1) and (C.2) in the algorithm. Given a set $S$ satisfying $\mu\left(S\right)\leq(2/3)\mu\left(V\right)$, the lower bound on the volume of the set $S^{g}$ is established in Lemma 2.7. If $\Phi(S)\leq f_{1}(\phi)$ and $v\in S^{g}_{b}$, then Lemmas 2.17 and 2.15 show that the algorithm will output a non-empty set. Finally, lemma 2.8 tells us that if $\Phi(S)\leq f_{1}(\phi)$, $v\in S^{g}$ and the algorithm outputs a non-empty set $C$, then it satisfies $\mu\left(C\cap S\right)\geq 2^{b-1}$.

It remains to bound the running time of Nibble. The algorithm will run for $t_{last}$ iterations. We will now show that with the correct implementation, each iteration takes time $O((\log n)/\epsilon)$. Instead of performing a dense vector multiplication in step (3.a), the algorithm should keep track of the set of vertices $u$ at which $r_{t}(u)>0$. Call this set $V_{t}$. The set $V_{t}$ can be computed in time $O(\left|V_{t}\right|)$ in step (3.b). Given knowledge of $V_{t-1}$, the multiplication in step (3.a) can be performed in time proportional to

Finally, the computation in step (3.c) might require sorting the vectors in $V_{t}$ according to $r_{t}$, which could take time at most $O(\left|V_{t}\right|\log n)$. Thus, the run-time of Nibble is bounded by

Nearly Linear-Time Graph Partitioning

In this section, we apply Nibble to design a partitioning algorithm Partition. This new algorithm runs in nearly linear-time. It computes an approximate sparsest cut with approximately optimal balance. In particular, we prove that there exists a constant $\alpha>0$ such that for any graph $G=(V,E)$ that has a cut $S$ of sparsity $\alpha\cdot\theta^{2}/\log^{3}n$ and balance $b\leq 1/2$, with high probability, Partition finds a cut $D$ with $\Phi_{V}(D)\leq\theta$ and $\textbf{bal}\left(D\right)\geq b/2$. Actually, Partition satisfies an even stronger guarantee: with high probability either the cut it outputs is well balanced,

or touches most of the edges touching $S$,

The expected running time of Partition is $O(m\log^{7}n/\phi^{4})$. Thus, it can be used to quickly find crude cuts.

Partition calls Nibble via a routine called Random Nibble that calls Nibble with carefully chosen random parameters. Random Nibble has a very small expected running time, and is expected to remove a similarly small fraction of any set with small conductance.

$C=\mathtt{RandomNibble}(G,\phi)$ (1) Choose a vertex $v$ according to $\psi_{V}$. (2) Choose a $b$ in $1,\ldots,\left\lceil\log m\right\rceil$ according to $\Pr\left[b=i\right]=2^{-i}/(1-2^{-\left\lceil\log m\right\rceil}).$ (3) $C=\mathtt{Nibble}(G,v,\phi,b)$.

Let $m$ be the number of edges in $G$. The expected running time of Random Nibble is $O\left(\log^{7}m/\phi^{4}\right)$. If the set $C$ output by Random Nibble is non-empty, it satisfies

$\mu\left(C\right)\leq(5/6)\mu\left(V\right).$

$\mbox{\bf E}\left[\mu\left(C\cap S\right)\right]\geq\mu\left(S\right)/4\mu\left(V\right)$.

The expected running time of Random Nibble may be upper bounded by

Parts (R.1) and (R.2) follow directly from part (N.1) of Theorem 2.1. To prove part (R.3), define $\alpha_{b}$ by

So, $\sum_{b}\alpha_{b}=1$. For each $i$, the chance that $v$ lands in $S^{g}_{i}$ is $\alpha_{i}\mu\left(S^{g}\right)/\mu\left(V\right)$. Moreover, the chance that $b=i$ is at least $2^{-i}$. If $v$ lands in $S^{g}_{i}$, then by part (N.3) of Theorem 2.1, $C$ satisfies

2 Partition

We now define Partition and analyze its performance. First, define

$D=\mathtt{Partition}(G,\theta,p)$, where $G$ is a graph, $\theta,p\in(0,1)$. (0) Set $W_{0}=V$, $j=0$ and $\phi=\theta/7$. (1) While $j<12m\left\lceil\lg(1/p)\right\rceil$ and $\mu\left(W_{j}\right)\geq(3/4)\mu\left(V\right)$, (a) Set $j=j+1$. (b) Set $D_{j}=\mathtt{RandomNibble}(G[W_{j-1}],\phi)$ (c) Set $W_{j}=W_{j-1}-D_{j}$. (2) Set $D=D_{1}\cup\dotsb\cup D_{j}$.

On input a graph with $m$ edges, the expected running time of Partition is $O\left(m\lg(1/p)\log^{7}m/\theta^{4}\right)$. Let $D$ be the output of $\mathtt{Partition}(G,\theta,p)$, where $G$ is a graph and $\theta,p\in(0,1)$. Then

$\mu\left(D\right)\leq(7/8)\mu\left(V\right)$,

If $D\not=\emptyset$ then $\Phi_{V}\left(D\right)\leq\theta$, and

then with probability at least $1-p$, $\mu\left(D\right)\geq\mu\left(S\right)/2$.

In particular, with probability at least $1-p$ either

$\mu\left(D\right)\geq(1/4)\mu\left(V\right)$, or

$\mu\left(S\cap D\right)\geq\mu\left(S\right)/2$.

Property (P.3) is a little unusual and deserves some explanation. It says that for every set $S$ of low conductance, with high probability either $D$ is a large fraction of $S$, or it is a large fraction of the entire graph. While we would like to pick just one of these properties and guarantee that it holds with high probability, this would be unreasonable: on one hand, there might be no big set $D$ of small conductance; and, on the other hand, even if $S$ is small the algorithm might cut out a large set $D$ that completely avoids $S$.

The bound on the expected running time of Partition is immediate from the bound on the running time of RandomNibble.

Let $j_{out}$ be the iteration at which Partition stops, so that $D=D_{1}\cup\dotsb\cup D_{j_{out}}$. To prove (P.1), note that $\mu\left(W_{j_{out}-1}\right)\geq(3/4)\mu\left(V\right)$ and so $\mu\left(D_{1}\cup\dotsb\cup D_{j_{out}-1}\right)\leq(1/4)\mu\left(V\right)$. By part (R.2) of Lemma 3.1, $\mu\left(D_{j_{out}}\right)\leq(5/6)\mu\left(W_{j_{out}-1}\right)$. So,

So, if $\mu\left(D\right)\leq\mu\left(V\right)/2$, then $\Phi_{V}\left(D\right)\leq\phi$. On the other hand, we established above that $\mu\left(D\right)\leq(7/8)\mu\left(V\right)$, from which it follows that

Let $j_{max}=12m\left\lceil\lg(1/p)\right\rceil$. To prove part (P.3), let $S$ satisfy (28) and consider what happens if we ignore the second condition in the while loop and run Partition for all potential $j_{max}$ iterations, obtaining cuts $D_{1},\dotsc,D_{12m\left\lceil\lg(1/p)\right\rceil}$. Let

hold at iteration $k$, then with probability at least $1/2$, one of these conditions will be satisfied by iteration $k+12m$. Thus, after all $j_{max}$ iterations, one of conditions $(P.3.a)$ or $(P.3.b)$ will be satisfied with probability at least $1-p$. If the algorithm runs for fewer iterations, then condition $(P.3.a)$ is satisfied.

To simplify notation, let $C_{i}=D_{k+i}$ and $U_{i}=W_{k+i}$, for $0\leq i\leq 12m$. Assume that

For $1\leq i\leq 12m$, define the random variable

As each set $C_{i}$ is a subset of $U_{0}$, and the $C_{i}$ are mutually disjoint, we will always have

and note that this ensures $0<\beta\leq 1/2$. Moreover, if $\sum X_{i}\geq\beta$, then $\mu\left(S\cap D^{\leq k+12m}\right)\geq\mu\left(S\right)/2$ will hold.

We need to show that, with probability at least $1/2$, either an event $E_{j}$ holds, or $\sum X_{i}\geq\beta$. To this end, we now show that if neither $E_{j}$ nor $\sum_{i\leq j}X_{i}\geq\beta$ holds, then $\mbox{\bf E}\left[X_{j+1}\right]\geq 1/8m$. If $\sum_{i\leq j}X_{i}<\beta$, then

We also have $\mu\left(S\cap U_{j}\right)\leq\mu\left(S\right)\leq(2/3)\mu\left(U_{j}\right)$, so the conditions of part $(R.3)$ of Lemma 3.1 are satisfied and

So, for all $j$ we have $\mbox{\bf E}\left[Y_{j}\right]\geq 1/8m$, and so $\mbox{\bf E}\left[\sum_{j\leq 12m}Y_{j}\right]\geq 3/2$. On the other hand,

This implies that with probability at least $1/2$ either $\sum_{i}X_{i}\geq\beta$ or some event $E_{j}$ holds, which is what we needed to show. ∎

References