Multi-way spectral partitioning and higher-order Cheeger inequalities

Introduction

Cheeger’s inequality for graphs [AM85, Alo86, SJ89] yields a robust version of this fact for $k=2$. To state it, we introduce some notation. For any subset $S\subseteq V$, define the expansion of $S$ to be the quantity

where the minimum is over all collections of $k$ non-empty, disjoint subsets $S_{1},S_{2},\ldots,S_{k}\subseteq V$. It is an easily verifiable fact that $\rho_{G}(k)=0$ if and only if $\lambda_{k}=0$. Cheeger’s inequality offers the following quantitative connection betwen $\rho_{G}(2)$ and $\lambda_{2}$,

We remark that the left-hand side follows easily, and the non-trivial content of the connection is contained in the right-hand side inequality.

The discrete version of Cheeger’s inequality is proved via a simple spectral partitioning algorithm. Besides being an important theoretical tool, since their inception spectral methods have been used for solving a wide range of optimization problems, from graph coloring [AG83, AK97] to image segmentation [SM00, TM06] to web search [Kle99, BP98].

Higher-order Cheeger inequalities. In general, we study higher-order analogs of (1), and develop new multi-way spectral partitioning algorithms. A special case of one of our main theorems (see Section 3.4 and Theorem 4.9) follows. It offers a strong quantitative version of the fact that $\rho_{G}(k)=0\iff\lambda_{k}=0$.

This resolves a conjecture of Miclo [Mic08]; see also [DJM12], where some special cases are considered. Moreover, Miclo [Mic13] has used Theorem 1.1 as the key step in establishing a 40-year-old conjecture of Simon and H$\o$egh-Krohn [SHK72]. We discuss this connection briefly at the end of the present section.

We remark that from Theorem 1.1, it is easy to find a partition of the vertex set into $k$ non-empty pieces such that every piece in the partition has expansion $O(k^{3})\sqrt{\lambda_{k}}$ (see Theorem 3.8). It is known that a dependence on $k$ in the right-hand side of (2) is necessary; see Section 4.4.

Finding many sets and small-set expansion. If one is interested in finding slightly fewer sets, our approach performs significantly better.

If $G$ is planar then, the bound improves to,

More generally, if $G$ excludes $K_{h}$ as a minor, then

We remark that the bound (3) holds with $2k$ replaced by $(1+\delta)k$ for any $\delta>0$, but where the leading constant now becomes $\delta^{-3}$; see Corollary 4.2. Louis, Raghavendra, Tetali and Vempala [LRTV12] have independently proved a somewhat weaker version of the bound (3), using rather different techniques. Specifically, they show that there exists an absolute constant $C>1$ such that $\rho_{G}(k)\leq O(\sqrt{\lambda_{Ck}\log k})$.

In particular, Theorem 1.2 has applications to the small-set expansion problem in graphs, which is fundamentally connected to the Unique Games Conjecture and many other problems in approximation algorithms (see [RS10, RST10]). To capture the expansion of small sets in graphs, we define the value,

Arora, Barak and Steurer [ABS10] prove the bound,

where $n=|V|$. Note that for $k=n^{\varepsilon}$ and $\epsilon\in(0,1)$, one achieves an upper bound of $O(\sqrt{\lambda_{k}})$, and this small loss in the expansion constant is crucial for applications to approximating small-set expansion. This was improved further in Steurer’s thesis [Ste10] by showing that for every $\alpha>0$,

Such a bound is also obtained in the works [OT12, OW12]. These bounds work fairly well for large values of $k$, but give less satisfactory results when $k$ is smaller.

Louis, Raghavendra, Tetali and Vempala [LRTV11] proved that

and conjectured that $\sqrt{k}$ could be replaced by $k$. Theorem 1.2 immediately yields,

resolving their conjecture up to a factor of 2 (and actually, as discussed earlier, up to a factor of $1+\delta$ for every $\delta>0$).

Moreover, (5) is quantitatively optimal for the noisy hypercube graphs (see Section 4.4), yielding an optimal connection between the $k$th Laplacian eigenvalue and expansion of sets of size $\approx n/k$.

It is interesting to note that in [KLPT11], it is shown that for $n$-vertex, bounded-degree planar graphs, one has $\lambda_{k}=O(k/n)$. Thus the spectral algorithm guaranteeing (4) partitions such a planar graph into $k$ disjoint pieces, each of expansion $O(\sqrt{k/n})$. This is tight, up to a constant factor, as one can easily see for an $\sqrt{n}\times\sqrt{n}$ planar grid, in which case the set of size $\approx n/k$ with minimal expansion is a $\sqrt{n/k}\times\sqrt{n/k}$ subgrid.

Large gaps in the spectrum. We recall that in the practice of spectral clustering, it is often observed that the correct number of clusters is indicated by a large gap between adjacent eigenvalues, i.e., if $\lambda_{k+1}\gg\lambda_{k}$, then one expects the input graph can be more easily partitioned into $k$ pieces than $k+1$. In Section 4.3, we prove a result supporting this phenomenon.

The key point is that the implicit constant in the upper bound is independent of $k$, unlike the bound (3).

The relation to hyperboundedness and spectral gaps of Markov operators. Consider a probability space $(\Omega,\mathcal{F},\mu)$. A self-adjoint operator $M:L^{2}(\mu)\to L^{2}(\mu)$ is said to be Markovian if, whenever $f\in L^{2}(\mu)$, we have $f\geq 0\implies Mf\geq 0$ and $M\mathbf{1}=\mathbf{1}$. One says that $M$ is ergodic if $Mf=f$ implies that $f$ is a multiple of $\mathbf{1}$.

Such an operator $M$ may not have any eigenvectors other than $\mathbf{1}$, but one defines its spectrum $\sigma(M)$ to be the set of $\lambda\in$ such that $\lambda I-M$ fails to be invertible. An ergodic Markov operator $M$ is said to have a spectral gap if there is a $\delta>0$ such that $\sigma(M)\subseteq\{1\}\cup[-1,1-\delta]$. Finally, say that $M$ is hyperbounded if there exists a $p>2$ such that

In [Mic13], the following theorem is proved.

If a self-adjoint, ergodic Markov operator is hyperbounded, then it has a spectral gap.

This was conjectured by Simon and H$\o$egh-Krohn [SHK72] for the special case of Markov semi-groups. They actually indicated that the conjecture was probably false even in this specialized setting. Miclo uses Theorem 1.1 as a fundamental step in the proof of Theorem 1.4. The basic idea is to relate the operator $2\rightarrow p$ norm to expansion of small sets in a graph (or, more generally, in the underlying probability space $(\Omega,\mu)$). Then one uses Theorem 1.1 to relate expansion of small sets to the spectrum of the operator. One can consult [BBH+12] for a detailed discussion of operator norms and small-set expansion from a computational perspective.

In fact, in the same paper that Miclo conjectured the validity of Theorem 1.1, he conjectured that finding such a family $\{\psi_{i}\}$ should be possible [Mic08, DJM12]. We resolve this conjecture and prove the following theorem in Section 3.4.

To prove this, we start with an orthonormal system of eigenfunctions of the Laplacian,

Observe that $\mathcal{R}_{G}(F)\leq\lambda_{k}$.

On the other hand, it straightforward to check that,

A natural approach would be to find (at least) $k$ such directions, and then define,

Unfortunately, this sharp cutoff could make the value

much larger than the corresponding quantity for $F$. Thus we must pursue a smoother approach for localizing $F$.

The radial projection distance. Our method of smooth localization depends crucially on defining a proper notion of distance between vertices, based on the map $F$. We would like to think of two vertices $u,v\in V$ as close if their Euclidean distance $\|F(u)-F(v)\|$ is small compared to their norms $\|F(u)\|,\|F(v)\|$. To capture this, we define the radial projection distance via,

The isotropy condition (7) gives us the following spreading property of $d_{F}$: If $S\subseteq V$, then

The notion of “close to the boundary” depends on the dimension $k$, and thus the smoothness of our maps $\{\psi_{i}\}$ will degrade as the dimension grows. For many families of graphs, however, we can appeal to special properties of their intrinsic geometry.

Exploiting the intrinsic geometry. It is well-known that the shortest-path metric on a planar graph has many nice properties, but $d_{F}$ is, in general, not a shortest-path geometry. Thus it is initially unclear how one might prove a bound like (4) using our approach. The answer is to combine information from the spectral embedding with the intrinsic geometry of the graph.

We define $\hat{d}_{F}$ as the shortest-path pseudometric on $G$, where the length of an edge $\{u,v\}\in E$ is precisely $d_{F}(u,v)$. In Sections 3.2 and 3.3, we show that it is possible to do the partitioning in the metric $\hat{d}_{F}$, and thus for planar graphs (and other generalizations), we are able to achieve dimension-independent bounds in Theorem 1.2.

This technique also addresses a common shortcoming of spectral methods: The spectral embedding can lose auxiliary information about the input data that could help with clustering. Our “hybrid” technique for planar graphs suggests that such information (in this case, planarity) can be fruitfully combined with the spectral computations.

Dimension reduction. In order to obtain the tight bound (3) for general graphs, we have to improve the quantitative parameters of our construction. The main loss in our preceding construction comes from the ambient dimension $k$.

A new multi-way Cheeger inequality. Dimension reduction only yields a loss of $O(\log k)$ in (3). In order to get the bound down to $\sqrt{\log k}$, we abandon our goal of localizing eigenfunctions. In Section 4.2, we give a new multi-way Cheeger rounding algorithm that combines random partitions of the radial projection distance $d_{F}$, and random thresholding based on $\|F(\cdot)\|$ (as in Cheeger’s inequality). By analyzing these two processes simultaneously, we are able to achieve (3). In addition, we use this method to achieve the stated bound in (2).

2 A general algorithm

Find disjoint subsets $S_{1},S_{2},\ldots,S_{r}\subseteq V$ using the values $\{F(v)/\|F(v)\|:v\in V\}$.

Sort the vertices $S_{i}=\{v_{1},v_{2},\ldots,v_{n_{i}}\}$ so that

Output the least-expanding set among the $n_{i}-1$ sets of the form,

We remark that partitioning the normalized vectors as in step (i) is used in the approach of [NJW02], but not in some other methods of spectral partitioning (see [VM03] for alternatives). Unlike [NJW02], our spectral partitioning algorithm does not use directly the eigenvectors of the normalized Laplacian; the vectors we use are multiplied by $D^{1/2}$ where $D$ is the diagonal degree matrix (see Section 2.1). In other words, we use the right eigenvectors of the associated random walk matrix. This is similar to [SM00], except that they do not normalize the spectral embedding as in our step (i).

Preliminaries

Let $G=(V,E,w)$ be a finite, undirected graph, with positive weights $w:E\to(0,\infty)$ on the edges. For a pair of vertices $u,v\in V$, we sometimes write $w(u,v)$ for $w(\{u,v\})$. For a subset of vertices $S\subseteq V$, we write $E(S,\overline{S}):=\{\{u,v\}\in E:|\{u,v\}\cap S|=1\}$. For a subset of edges $F\subseteq E$, we write $w(F)=\sum_{e\in F}w(e)$. We use $x\sim y$ to denote $\{x,y\}\in E$. We extend the weight to vertices by defining, for a single vertex $v\in V$, $w(v):=\sum_{u\sim v}w(u,v)$. We can think of $w(v)$ as the weighted degree of vertex $v$. We will assume throughout that $w(v)>0$ for every $v\in V$. For $S\subseteq V$, we write $w(S)=\sum_{v\in S}w(v)$.

For two expressions $A$ and $B$, we write $A\lesssim B$ for $A\leq O(B)$ and $A\asymp B$ for the conjunction of $A\lesssim B$ and $A\gtrsim B$.

Observe that for an unweighted, $d$-regular graph, we have $\mathcal{L}_{G}=\frac{1}{d}L$.

where the latter value is referred to as the Rayleigh quotient of $f$ (with respect to $G$).

In particular, one sees that $\mathcal{L}_{G}$ is a positive-definite operator with eigenvalues

For a connected graph, the first eigenvalue corresponds to the eigenfunctions $g=D^{1/2}f$, where $f$ is any non-zero constant function. Furthermore, by standard variational principles,

In particular, one can use (9) to easily prove the left-hand side of (2) using the following standard observation.

Consider any $f=\sum_{i=1}^{k}\alpha_{i}\psi_{i}$. Then, for any $u,v\in V$, we have

using the fact the $\psi_{i}$’s are disjointly supported. Therefore,

Applying the preceding lemma with $\psi_{i}=\mathbf{1}_{S_{i}}$ as the indicator functions of disjoint sets $S_{1},S_{2},\ldots,S_{k}$ yields the left-hand side of (2), observing that $\phi_{G}(S_{i})=\mathcal{R}_{G}(\mathbf{1}_{S_{i}})$.

2 Cheeger’s inequality with Dirichlet boundary conditions

Given a subset $S\subseteq V$ by, we denote the Dirichlet conductance of $S$ by,

For convenience, we take $\phi_{G}(\emptyset)=\infty$. If $\mathcal{H}$ is a Hilbert space, we extend the notion of Rayleigh quotients to arbitrary maps $\psi:V\to\mathcal{H}$ via,

Many variants of the following lemma are known; see, e.g. [Chu96].

implying there exists a $t\in[0,\infty]$ for which $S_{t}$ satisfies the statement of the lemma. ∎

3 Random partitions of metric spaces

We now discuss some of the theory of random partitions of metric spaces. Let $(X,d)$ be a finite metric space. We use $B(x,R)=\{y\in X:d(x,y)\leq R\}$ to denote the closed ball of radius $R$ about $x$. We will write a partition $P$ of $X$ as a function $P:X\to 2^{X}$ mapping a point $x\in X$ to the unique set in $P$ that contains $x$.

A random partition $\mathcal{P}$ is $(\Delta,\alpha,\delta)$-padded if $\mathcal{P}$ is $\Delta$-bounded, and for every $x\in X$, we have

A random partition is $(\Delta,L)$-Lipschitz if $\mathcal{P}$ is $\Delta$-bounded, and, for every pair $x,y\in X$, we have

The next result is proved in [CCG+98]. See also [LN05, Lem 3.16].

A partitioning theorem for excluded-minor graphs is presented in [KPR93], with an improved quantitative dependence coming from [FT03].

If $X$ is the shortest-path metric on a graph excluding $K_{h}$ as a minor, then for every $\Delta>0$ and $\delta>0$, $X$ admits a $(\Delta,O(h^{2}/\delta),1-\delta)$-padded random partition and a $(\Delta,O(h^{2}))$-Lipschitz random partition.

Finally, for the special case of bounded-genus graphs, a better bound is known [LS10].

If $X$ is the shortest-path metric on a graph of genus $g$, for every $\Delta>0$ and $\delta>0$, $X$ admits a $(\Delta,O((\log g)/\delta),1-\delta)$-padded random partition, and a $(\Delta,O(\log g))$-Lipschitz random partition.

Localizing eigenfunctions

Otherwise, if $F(u)=F(v)=0$, we put $d_{F}(u,v)\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=0$, else $d_{F}(u,v)\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\infty$.

First, we record the following simple fact.

2 Smooth localization

For future applications, it will be useful to consider the largest metric on $G$ which agrees with $d_{F}$ on edges. This is the induced shortest-path (extended pesudo-) metric on $G$, where the length of an edge $\{u,v\}\in E$ is given by $d_{F}(u,v)$. We will use the notation $\hat{d}_{F}$ for this metric. Observe that $\hat{d}_{F}\geq d_{F}$ since $d_{F}$ is a pseudo-metric. We will write

for the open $\varepsilon$-neighborhood of $S$ in the metric $\hat{d}_{F}$.

if $\{u,v\}\in E$, then $|\psi(u)-\psi(v)|\leq(1+\frac{2}{\varepsilon})\|F(u)-F(v)\|$.

In particular, observe that $\theta$ is $(1/\varepsilon)$-Lipschitz with respect to $\hat{d}_{F}$, so since $\hat{d}_{F}$ and $d_{F}$ agree on edges, we have for every $\{u,v\}\in E$,

Finally, set $\psi(v)\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\theta(v)F(v)$.

Properties (i) and (ii) are immediate from the definition, thus we turn to property (iii). Fix $\{u,v\}\in E$. We have,

Since $\theta\leq 1$, the first term is at most $\|F(u)-F(v)\|$. Now, using (12), and Lemma 3.1, we have

Additionally property (i) implies that for each $i\in[r]$,

and by property (iii) of Lemma 3.3, and since the supports are disjoint,

In particular, if we reorder the maps so that $\mathcal{R}_{G}(\psi_{1})\leq\mathcal{R}_{G}(\psi_{2})\leq\cdots\leq\mathcal{R}_{G}(\psi_{r})$, then the preceding two inequalities imply (14).

3 Random partitioning

Then there exist r disjoint subsets $T_{1},T_{2},\ldots,T_{r}\subseteq V$ such that for each $i\neq j$, we have $\hat{d}_{F}(T_{i},T_{j})\geq 2\Delta/\alpha$, and for every $i=1,2,\ldots,k$,

Furthermore, by the spreading property of $F$, we have, for each $S\in P$,

because the first $r-1$ pieces will have total mass at most

for all $r\in[k/2,k]$, leaving at least $\frac{\cal M}{2k}$ mass left over from (15). ∎

We mention a representative corollary that follows from the conjunction of Lemmas 3.4 and 3.5.

In this case, we set $r=\lceil(1-\delta/2)k\rceil$ in our application of Lemma 3.5. After extracting at least $\lceil(1-\delta/2)k\rceil$ sets, we apply Lemma 3.4, but only take the first $r^{\prime}=\lceil(1-\delta)k\rceil$ functions $\psi_{1},\psi_{2},\ldots,\psi_{r^{\prime}}$. ∎

Note, in particular, that we can apply the preceding corollary with $\delta=\frac{1}{2k}$ to obtain $r=k$.

4 Higher-order Cheeger inequalities

We now present some theorems applying our machinery to embeddings which come from the eigenfunctions of $\mathcal{L}_{G}$.

where $\lambda_{k}$ is the $k$th smallest eigenvalue of $\mathcal{L}_{G}$. If $G$ excludes $K_{h}$ as a minor, then the bound improves to

and if $G$ has genus at most $g\geq 1$, then one gets

Choose $\Delta\asymp\sqrt{\delta}$ so that $(1-\Delta^{2})^{-1}\leq 1+\frac{\delta}{48}$. In this case, Lemma 3.2 implies that $F$ is $(\Delta,\frac{1}{k}+\frac{\delta}{48k})$-spreading. Now, for general graphs, since $d_{F}$ is Euclidean, we can use Theorem 2.3 applied to $d_{F}$ to achieve $\alpha\asymp k/\delta$ in the assumptions of Corollary 3.6. Observe that $\hat{d}_{F}\geq d_{F}$, so that $B_{\hat{d}_{F}}(v,\Delta/\alpha)\subseteq B_{d_{F}}(v,\Delta/\alpha)$, meaning that we can satisfy both conditions (i) and (ii), verifying (16).

We remark that in Section 4.1, we will give an alternate bound of $O(\delta^{-7}\log^{2}k)\cdot\lambda_{k}$ for (16), which is better for moderate values of $\delta$.

Finally, we can use the preceding theorems in conjunction with Lemma 2.2 to produce many non-expanding sets.

(Non-expanding $k$-partition) For any weighted graph $G=(V,E,w)$, there exists a partition $V=S_{1}\cup S_{2}\cup\cdots\cup S_{k}$ such that

where $\lambda_{k}$ is the $k$th smallest eigenvalue of $\mathcal{L}_{G}$. If $G$ excludes $K_{h}$ as a minor, then the bound improves to

and if $G$ has genus at most $g\geq 1$, then one gets

Now reorder the sets so that $w(S_{1})\leq w(S_{2})\leq\cdots\leq w(S_{k})$, and replace $S_{k}$ with the larger set $S_{k}^{\prime}=V\setminus(S_{1}\cup S_{2}\cup\cdots\cup S_{k-1})$ so that $V=S_{1}\cup S_{2}\cup\cdots\cup S_{k-1}\cup S^{\prime}_{k}$ forms a partition. One can now easily check that

A similar argument yields the other two bounds. ∎

Using Theorem 3.7 in conjunction with Lemma 2.2 again yields the following.

For every $\delta\in(0,1)$ and any weighted graph $G=(V,E,w)$, there exist $r\geq\lceil(1-\delta)k\rceil$ disjoint sets $S_{1},S_{2},\ldots,S_{r}\subseteq V$ such that,

where $\lambda_{k}$ is the $k$th smallest eigenvalue of $\mathcal{L}_{G}$. If $G$ excludes $K_{h}$ as a minor, then the bound improves to

and if $G$ has genus at most $g\geq 1$, then one gets

We remark that the bound (19) will be improved, in various ways, in Section 4.

Improved quantitative bounds

A main result of this section is the following theorem.

For any weighted graph $G=(V,E,w)$, $k\in\{1,2,\ldots,n\}$, and $\delta\in(0,1)$, there exist $r\geq\lceil(1-\delta)k\rceil$ disjoint sets $S_{1},S_{2},\ldots,S_{r}\subseteq V$ with

where $\lambda_{k}$ is the $k$th smallest eigenvalue of $\mathcal{L}_{G}$.

One should observe that in Theorems 3.7 and 3.9, the loss of $k^{2}$ in (16) and $k$ in (19) comes from the dimension of the eigenfunction embedding. To achieve somewhat better bounds for general graphs, we now show how to drastically reduce the dimension while preserving the Rayleigh quotient and spreading properties.

and, for every $\delta\in(0,\frac{1}{2}]$,

with probability at least $1/2$, the map $\Gamma_{k,h}$ satisfies both of the following conditions:

${\cal R}_{G}(\Gamma_{k,h}\circ F)\leq 8\cdot\mathcal{R}_{G}(F)$, and

$\Gamma_{k,h}\circ F$ is $(\Delta/4,(1+\Delta)\eta)$-spreading with respect to $G$.

Let $\delta=\Delta/16$. We may assume that $k\geq 2$. Choose $h\asymp(1+\log{k}+\log(\frac{1}{\Delta}))/\Delta^{2}$ large enough such that $2e^{-\delta^{2}h/12}\leq\delta^{2}k^{-3}/128$. Let $\Gamma=\Gamma_{k,h}$.

First, observe that (20) combined with Markov’s inequality implies that the following holds with probability at least $3/4$,

Therefore, by Markov’s inequality, with probability at least $31/32$, we have

In particular, with probability at least $31/32$, we have

Combining our estimates for (23) and (26), we conclude that (i) holds with probability at least $23/32$. Thus we can finish by showing that (ii) holds with probability at least $25/32$. We first consider property (ii) for subsets of $U$.

and let $I_{u,v}$ be the random variable indicating that ${\cal A}_{u,v}$ does not occur.

We claim that for $u,v\in V$, ${\cal A}_{u,v}$ occurs if $u,v\in U$, and

where we have used the fact that $\Gamma$ is a linear operator. The other direction can be proved similarly.

By linearity of expectation, and Markov’s inequality, we conclude that

Fix a vertex $u\in S$. Since for every $v\in S\setminus B_{d_{F}}(u,\Delta/2)$, we have $d_{F}(u,v)\geq\Delta/2$, $d_{\Gamma(F)}(u,v)\leq\Delta/4$, and recalling that $\delta=\Delta/16$, it must be that $I_{u,v}=1$. On the other hand, we have

Thus under our assumption on the existence of $S$ and again using $S\subseteq U$, we have

where the last inequality follows from $\eta\geq 1/k$ and $\delta\leq 1/16$. Combining this with (27) yields the claim. ∎

The preceding claim guarantees a spreading property for subsets $S\subseteq U$. Finally, we need to handle points outside $U$.

With probability at least $15/16$, we have

Let ${\cal D}_{u}$ be the event that $u\notin U$, and let $H_{u}:=\|\Gamma(F(u))\|^{2}\mathbf{1}_{{\cal D}_{u}}$. Then,

Using the inequality, valid for all non-negative $X$,

where we have used (22) and the initial choice of $h$ sufficiently large.

It follows from this, (29), and (24), that

To conclude the proof of the lemma, we need to verify that (ii) holds with probability at least $25/32$. But observe that if (26) holds, then the conclusion of the preceding claim is,

Combining this with Claim 4.4 shows that with probability at least $25/32$, $\Gamma\circ F$ is $(\Delta/4,(1+7\delta)\eta)$-spreading, completing the proof. ∎

where $\lambda_{k}$ is the $k$th smallest eigenvalue of $\mathcal{L}_{G}$.

We may clearly assume that $\delta\geq\frac{1}{2k}$. Choose $\Delta\asymp\delta$ so that $(1-16\Delta^{2})^{-1}(1+4\Delta)\leq 1+\frac{\delta}{48}$. In this case, for some choice of

2 A multi-way Cheeger inequality

Note that Theorem 4.6 combined with Lemma 2.2 is still not strong enough to prove Theorem 4.1. To do that, we need to combine Lemma 4.3 with a strong Cheeger inequality for Lipschitz partitions.

Since the statement of the lemma is homogeneous in $F$, we may assume that $M=1$. By Theorem 2.4, there exists an $\Delta$-bounded random partition $\mathcal{P}$ satisfying, for every $u,v\in V$,

Let $\mathcal{P}=S_{1}\cup S_{2}\cup\cdots\cup S_{m}$, where we recall that $m$ is a random number.

Next, if $\{u,v\}\in E$ with $\|F(u)\|^{2}\leq\|F(v)\|^{2}$, then we have

where in the final line we have used Lemma 3.1.

Thus, we can use Cauchy-Schwarz to write,

Since $\lceil(1-\delta)k\rceil\leq k$, we may assume that

To see this, suppose we start with the family $\{S_{i}\}$ and iteratively merge the two sets for which $\sum_{v\in S_{i}}w(v)\|F(v)\|^{2}$ is smallest subject to the constraint that no set has a sum which exceeds $\frac{\mathcal{M}}{k}\left(1+\frac{\delta}{4}\right)$. At the end of this process, let $T_{1},T_{2},\ldots,T_{r^{\prime}}$ represent the sets constructed that satisfy (35). We will have

where in the second inequality we have used (34).

We can already use this to improve (19) in Theorem 3.9.

For every $\delta\in(0,1)$ and any weighted graph $G=(V,E,w)$, there exist $r\geq\lceil(1-\delta)k\rceil$ disjoint, non-empty sets $S_{1},S_{2},\ldots,S_{r}\subseteq V$ such that,

where $\lambda_{k}$ is the $k$th smallest eigenvalue of $\mathcal{L}_{G}$.

Observe that setting $\delta=\frac{1}{2k}$ in the preceding theorem yields Theorem 1.1.

And now we can complete the proof of Theorem 4.1.

Let $F(v)=(f_{1}(v),f_{2}(v),\ldots,f_{k}(v))$. Choose $\Delta\asymp\delta$ so that $(1-16\Delta^{2})^{-1}(1+4\Delta)\leq 1+\frac{\delta}{4}$. In this case, for some choice of

3 Gaps in the spectrum

We now show that if there are significant gaps in the spectrum of $G$, one can obtain a higher-order Cheeger inequality with no dependence on $k$.

where $\lambda_{k}$ is the $k$th smallest eigenvalue of $\mathcal{L}_{G}$.

$\Lambda$ is $(\Delta,\eta)$-spreading for some $\Delta\asymp\delta$ and $\eta=\frac{1}{k}+\frac{\delta}{16k}$,

$\mathcal{R}_{G}(\Lambda)\leq 8\mathcal{R}_{G}(F)\leq 8\lambda_{k}$ .

Since the radial projection distance $d_{\Lambda}$ is Euclidean, we can use Theorem 2.3 to achieve a $(\Delta/4,\alpha,1-\delta/16)$-padded random partition $\mathcal{P}$ of $(V,d_{\Lambda})$ with $\alpha\asymp\frac{h}{\delta}\asymp\frac{\log k}{\delta^{3}}$. For a subset $S\subseteq V$, let

where we define $\mathcal{M}_{\Lambda}(S)\mathrel{\vbox{\hbox{\scriptsize.}\hbox{\scriptsize.}}}=\sum_{v\in S}w(v)\|\Lambda(v)\|^{2}$ for any $S\subseteq V$.

In this case it must be that for $1\leq i,j\leq(1-2\delta)k$ and $i\neq j$, we have

Since $\Lambda$ is $(\Delta,\eta)$-spreading, for any $i\leq(1-2\delta)k$, we have

This is because the first $r-1$ pieces will have total mass at most

leaving at least $\frac{\delta}{8}\mathcal{M}_{\Lambda}(V)\geq\frac{1}{8k}\mathcal{M}_{\Lambda}(V)$ left over from (38).

for some constant $c^{\prime}>0$, contradicting our initial assumption (for $c=c^{\prime}$). ∎

Lemma 2.2 immediately yields the following corollary.

Under the assumptions of Theorem 4.10, there are at least $r\geq(1-3\delta)k$ non-empty, disjoint sets $S_{1},S_{2},\ldots,S_{r}\subseteq V$ such that $\phi_{G}(S_{i})\lesssim\sqrt{\lambda_{k}/\delta^{3}}$.

Let us conclude this section by describing the consequences of the above results for spectral clustering algorithms. The proof of Theorem 4.10 aligns with the folklore belief that, in spectral clustering, the number of clusters is best chosen based on a large gap in the spectrum of the underlying graph. Additionally, the proof provides a justification for the use of the $k$-means heuristic. Observe that in Case I (the only possible case under the assumptions of the theorem), the support of each of the functions $\psi_{i}$ is a ball of radius at most $\Delta$ with respect to the metric $d_{\Lambda}$. In other words, the vertices are concentrated in $\asymp k$ balls of small radius after the dimension reduction step. It seems plausible that the $k$-means heuristic could successfully locate a good partition of the vertices in such a scenario.

4 Noisy hypercubes

where $\varepsilon=\frac{\log(2)}{\log(k/C)}$.

Let $H=H_{k,\varepsilon}$. First, the weighted degree of every vertex is

Thus $\lambda_{k}(H)\leq 2\varepsilon$. We will now show that for $|S|\leq Cn/k$, one has $\phi_{H}(S)\geq\frac{1}{2}$, completing the proof of the theorem.

For $\eta\in$, the Bonami-Beckner operator $T_{\eta}$ is defined as

The Bonami-Beckner inequality [Bon70, Bec75] states that

Let $A$ be the normalized adjacency matrix of $H$, i.e. $A_{xy}=\frac{\varepsilon^{|x\oplus y|}}{(1+\varepsilon)^{k}}\,.$ It follows from an elementary calculation that $W_{S}$ is an eigenvector of $A$ with eigenvalue $(\frac{1-\varepsilon}{1+\varepsilon})^{|S|}$, i.e.

For $S\subseteq[n]$, let ${\bf 1}_{S}$ be the indicator function of $S$. Therefore,

where the one last inequality follows from (39).

Now, observe that for any $S\subseteq V$, we have

where we have written $E(S,S)$ for edges with both endpoints in $S$.

Hence, for any subset $S\subseteq V$ of size $|S|\leq Cn/k$, we have

where the last inequality follows by the choice of $\varepsilon=\log(2)/\log{(k/C)}$. ∎

The preceding theorem shows that even if we only want to find a set $S$ of size $n/\sqrt{k}$, then for values of $k\leq O(\log n)$, we can still only achieve a bound of the form $\phi_{H}(S)\lesssim\sqrt{\lambda_{k}\log k}$. The state of affairs for $k\gg\log n$ is a fascinating open question.

Conclusion

In Section 1.2, we gave a generic outline of our spectral partitioning algorithm. We remark that our instantiations of this algorithm are simple to describe. As an example, suppose we are given a weighted graph $G=(V,E,w)$ Let ${\cal L}_{G}=I-D^{-1/2}AD^{-1/2}$ be the normalized Laplacian matrix of $G$ where $I$ is the identity matrix, $A$ is the adjacency matrix and $D$ is the diagonal matrix of vertex degrees. We want to find $k$ disjoint sets, each of expansion $O(\sqrt{\lambda_{2k}\log k})$ where $\lambda_{2k}$ is the $2k^{\textrm{th}}$ smallest eigenvalue of ${\cal L}_{G}$ (recall Theorem 1.2). We specify a complete randomized algorithm.

Here, $B(x,R)$ represents the closed Euclidean ball of radius $R$ about $x$, and it is easy to see that this induces a partition of $V$ in a finite number of steps with probability one. In other words, we assign each vertex $v\in V$ to the first point $x_{i}$ such that

Let $V=S_{1}\cup S_{2}\cup\cdots\cup S_{m}$ be this partition.

(Intuitively, we form $k^{\prime}$ sets from our total of $m\geq k^{\prime}$ sets by balancing the $\mathcal{M}(\cdot)$-value among them.) At the end, we are left with a partition $V=S_{1}\cup S_{2}\cup\cdots\cup S_{k^{\prime}}$ of $V$ into $k^{\prime}\geq 3k/2$ sets.

(Cheeger Sweep) To complete the algorithm, for each $i=1,2,\ldots,k^{\prime}$, we choose a value $\tau$ such that

has the least expansion. We then output $k$ of the sets $\hat{S}_{1},\hat{S}_{2},\ldots,\hat{S}_{k^{\prime}}$ that have the smallest expansion.

We emphasize that one can run the above algorithm using any set of orthonormal vectors with small Rayleigh quotient. One can employ the recent developments on fast Laplacian solvers to find such vectors in near-linear time [ST04, KMP11, KOSZ13, Vis13]. Given orthonormal vectors $g_{1},\ldots,g_{2k}$, the above algorithms runs in time $O(n\cdot\textup{poly}(k))$. In particular every step except random partitioning runs in nearly linear time, and the random partitioning step runs in time $O(n\cdot 2^{h})$.

2 Future directions

The preceding algorithm suggests some natural questions. First, does dimension reduction help to improve the quality of clusterings in practice? For instance, if one runs the $k$-means algorithm (as in [NJW02]) on the randomly projected points, does it yield better results? Another interesting question is whether, at least in certain circumstances, the quality of the $k$-means clustering can be rigorously analyzed when used in place of our random geometric partitioning.

It would be interesting to find the right asymptotic dependence on $k$ in Theorem 1.1. Recall that in Theorems 1.2 and 4.12, we showed that if one is interested in finding, say, $k/2$ disjoint non-expanding sets, then the right dependence on $k$ is $\Theta(\sqrt{\log k})$.

One might hope that it is possible to achieve $\rho_{G}(k)\leq(\log(k))^{O(1)}\sqrt{\lambda_{k}}$. Such a bound is impossible if we instead try to find a $k$-partitioning of our graph. There are simple family of graphs where the sparsity of the best $k$-partitioning has a polynomial dependence on $k$ [LRTV12].

References