Approximating the Exponential, the Lanczos Method and an \tilde{O}(m)-Time Spectral Algorithm for Balanced Separator

Spectral Algorithms, Balanced Graph Partitioning, Matrix Exponential, Lanczos Method, Uniform Approximation.

Introduction and Our Results

The Balanced Separator problem (BS) asks the following decision question: given an unweighted graph $G=(V,E),$ $V=[n],\left|E\right|=m,$ a constant balance parameter $b\in(0,\nicefrac{{1}}{{2}}],$ and a target conductance value $\gamma\in(0,1),$ does $G$ have a $b$-balanced cut $S$ such that $\phi(S)\leq\gamma$? Here, the conductance of a cut $(S,\bar{S})$ is defined to be $\phi(S)\stackrel{{\scriptstyle\text{\tiny def}}}{{=}}\nicefrac{{|E(S,\bar{S})|}}{{\min\{{\mathsf{vol}}(S),{\mathsf{vol}}(\overline{S})\}}},$ where ${\mathsf{vol}}(S)$ is the sum of the degrees of the vertices in the set $S$. Moreover, a cut $(S,\bar{S})$ is $b$-balanced if $\min\{{\mathsf{vol}}(S),{\mathsf{vol}}(\bar{S})\}\geq b\cdot\text{vol}(V).$ This is a classic NP-hard problem and a central object of study for the development of approximation algorithms, both in theory and in practice. On the theoretical side, BS has far reaching connections to spectral graph theory, the study of random walks and metric embeddings. In practice, algorithms for BS play a crucial role in the design of recursive algorithms , clustering and scientific computation .

At the core of our algorithm for BS, and more generally of most MMWU based algorithms, lies an algorithm to quickly compute $\exp(-A)v$ for a PSD matrix $A$ and a unit vector $v.$ It is sufficient to compute an approximation $u,$ to $\exp(-A)v,$ in time which is as close as possible to $t_{A}.$ It can be shown that using about $\|A\|$ terms in the Taylor series expansion of $\exp(-A),$ one can find a vector $u$ that approximates $\exp(-A)v.$ Hence, this method runs in time roughly $O(t_{A}\cdot\|A\|).$ In our application, and certain others , this dependence on the norm is prohibitively large. The following remarkable result was cited in Kale .

Let $A\succeq 0$ and $\varepsilon>0.$ There is an algorithm that requires $O\left(\log^{2}\nicefrac{{1}}{{\varepsilon}}\right)$ iterations to find a vector $u$ such that $\left\lVert\exp(-A)v-u\right\rVert\leq\left\lVert\exp(-A)\right\rVert\varepsilon,$ for any unit vector $v$. The time for every iteration is ${O}(t_{A}).$

This hypothesis would suffice to prove Theorem 1.1. But, to the best of our knowledge, there is no known proof of this result. In fact, the source of this unproved hypothesis can be traced to a paper of Eshof and Hochbruck (EH) . EH suggest that one may use the Lanczos method (described later), and combine it with a rational approximation for $e^{-x}$ due to Saff, Schonhage and Varga , to reduce the computation of $\exp(-A)v$ to a number of $(I+\alpha A)^{-1}v$ computations for some $\alpha>0.$ Note that this is insufficient to prove the hypothesis above as there is no known way to compute $(I+\alpha A)^{-1}v$ in time $O(t_{A}).$ They note this and propose the use of iterative methods to do this computation. They also point out that this will only result in an approximate solution to $(I+\alpha A)^{-1}v$ and make no attempt to analyze the running time or the error of their method when the inverse computation is approximate. We believe that we are quite distant from proving the hypothesis for all PSD matrices and, moreover, that proving such a result may provide valuable insights into a fast (approximate) inversion method for symmetric PSD matrices, an extremely important open problem.

A significant part of this paper is devoted to a proof of the above hypothesis for a class of PSD matrices that turns out to be sufficient for the BS application. For the norm-independent, fast-approximate inverse computation, we appeal to the result of Spielman and Teng (also see improvements by Koutis, Miller and Peng ). The theorem we prove is the following.

In the symmetric PSD setting we also prove the following theorem which, for our application, gives a result comparable to Theorem 1.3.

Upper Bound. For every $0\leq a<b,$ and $0<\delta\leq 1$, there exists a polynomial ${p}$ that satisfies, $\sup_{x\in[a,b]}|e^{-x}-{p}(x)|\leq\delta\cdot e^{-a},$ and has degree $O\left(\sqrt{\max\{\log^{2}\nicefrac{{1}}{{\delta}},(b-a)\cdot\log\nicefrac{{1}}{{\delta}}\}}\cdot\left(\log\nicefrac{{1}}{{\delta}}\right)^{2}\right)$.

Lower Bound. For every $0\leq a<b$ such that $a+\log_{e}4\leq b,$ and $\delta\in(0,\nicefrac{{1}}{{8}}],$ any polynomial $p(x)$ that approximates $e^{-x}$ uniformly over the interval $[a,b]$ up to an error of $\delta\cdot e^{-a},$ must have degree at least $\frac{1}{2}\cdot\sqrt{b-a}\ .$

Organization of the Main Body of the Paper

In Section 3 we present a technical overview of our results and in Section 4 we discuss the open problems arising from our work. The main body of the paper follows after it and is divided into three sections, each of which have been written so that they can be read independently. Section 5 contains a complete description and all the proofs related to Theorem 1.1 and Theorem 3.1. Section 6 contains our results on computing the matrix exponential; in particular the proofs of Theorems 1.2, 1.4 and 3.2. Section 7 contains the proof of our structural results on approximating $e^{-x}$ and the proof of Theorem 1.5.

Technical Overview of Our Results

In this section, we provide an overview of Theorem 1.1. As pointed out in the introduction, our algorithm, BalSep, when combined with the matrix-exponential-vector algorithm in Theorem 1.4 results in a very simple and practical algorithm for BS. We record the theorem here for completeness and then move on to the overview of BalSep and its proof. The proof of this theorem appears in Section 5.4.

Before we explain our algorithm, it is useful to review the RLE algorithm. Recall that given $G,\gamma$ and $b,$ the goal of the BS problem is to either certify that every $b$-balanced cut in $G$ has conductance at least $\gamma,$ or produce a $\Omega(b)$ balance cut in $G$ of conductance $O(\sqrt{\gamma}).$ RLE does this by applying LE iteratively to remove unbalanced cuts of conductance $O(\sqrt{\gamma})$ from $G.$ The iterations stop and the algorithm outputs a cut, when it either finds a $(b/2)$-balanced cut of conductance $O(\sqrt{\gamma})$ or the union of all unbalanced cuts found so far is $(b/2)$-balanced. Otherwise, the algorithm terminates when the residual graph has spectral gap at least $2\gamma.$ In the latter case, any $b$-balanced cut must have at least half of its volume lie within the final residual graph, and hence, has conductance at least $\gamma$ in the original graph. Unfortunately, this algorithm may require $\Omega(n)$ iterations in the worst case. For instance, this is true if the graph $G$ consists of $\Omega(n)$ components loosely connected to an expander-like core through cuts of low conductance. This example highlights the weakness of the RLE approach: the second eigenvector of the Laplacian may only be correlated with one low-conductance cut and fail to capture at all even cuts of slightly larger conductance. This limitation makes it impossible for RLE to make significant progress at any iteration. We now proceed to show how to fix RLE and present our algorithm at a high level.

1.2 High-Level Idea of Our Algorithm

Rather than working with the vertex embedding given by the eigenvector, at iteration $t,$ we will consider the multi-dimensional vector embedding represented by the transition probability matrix $P^{(t)}$ of a certain random walk over the graph. We refer to this kind of walk as an Accelerated Heat Kernel Walk (AHK) and we describe it formally in Section 3.1.4. At each iteration $t=1,2,\ldots,$ the current AHK walk is simulated for $\tau=\nicefrac{{\log n}}{{\gamma}}$ time to obtain $P^{(t)}.$ For any $t,$ this choice of $\tau$ ensures that the walk must mix across all cuts of conductance much larger than $\gamma,$ hence emphasizing cuts of the desired conductance in the embedding $P^{(t)}.$ The embedding obtained in this way, can be seen as a weighted combination of multiple eigenvectors, with eigenvectors of low eigenvalue contributing more weight. Hence, the resulting embedding captures not only the cut corresponding to the second eigenvector, but also cuts associated with other eigenvectors of eigenvalue close to $\gamma.$ This enables our algorithm to potentially find many different low-conductance unbalanced cuts at once. Moreover, the random walk matrix is more stable than the eigenvector under small perturbations of the graph, making it possible to precisely quantify our progress from one iteration to the next as a function of the mixing of the current random walk. For technical reasons, we are unable to show that we make sufficient progress if we just remove the unbalanced cuts found, as in RLE. Instead, if we find a low-conductance unbalanced cut $S^{(t)}$ at iteration $t,$ we perform a soft removal, by modifying the current walk $P^{(t)}$ to accelerate the convergence to stationarity on the set $S^{(t)}.$ This ensures that a different cut is found using $P^{(t+1)}$ in the next iteration. In particular, the AHK walks we consider throughout the execution of the algorithm will behave like the standard heat kernel on most of the graph, except on a small unbalanced subset of vertices, where their convergence will be accelerated. We now present our algorithm in more detail. We first recall some definitions.

1.3 Definitions

1.4 The AHK Random Walk and its Mixing

1.5 Our Algorithm and its Analysis

The algorithm proceeds as follows: At iteration $t,$ it checks if the total deviation of $P^{(t)},$ i.e., $\Psi(P^{(t)},V),$ is sufficiently small (i.e., $P^{(t)}$ is mixing). In this case, we can guarantee that no balanced cut of conductance less than $\gamma$ exists in $G.$ In more formal language, it appears below.

This result has a simple explanation in terms of the AHK random walk $P^{(t)}.$ Notice that $P^{(t)}$ is accelerated only on a small unbalanced set $S.$ Hence, if a balanced cut of conductance less than $\gamma$ existed, its convergence could not be greatly helped by the acceleration over $S.$ Thus, if $P^{(t)}$ is still mixing very well, no such balanced cut can exist. On the other hand, if $P^{(t)}$ has high total deviation (i.e., the walk has not yet mixed), then, intuitively, some cut of low conductance exists in $G.$ Formally, we show that, the embedding $\{v^{(t)}_{i}\}_{i\in V}$ has low quadratic form with respect to the Laplacian of $G.$

From an SDP-rounding perspective, this means that the embedding $P^{(t)}$ can be used to recover a cut $S^{(t)}$ of conductance $O(\sqrt{\gamma}),$ using the SDP-rounding techniques from OV. If $S^{(t)}$ or $\cup_{i=1}^{t}S^{(i)}$ is $\Omega(b)$-balanced, then we output that cut and terminate. Otherwise, $S^{(t)}$ is unbalanced. In this case, we accelerate the convergence from $S^{(t)}$ in the current AHK walk by increasing $(\beta^{(t)})_{i}$ for every $i\in S^{(t)}$ to give $\beta^{(t+1)},$ and using $\beta^{(t+1)}$ to produce $P^{(t+1)}$ and move on to the next iteration.

The analysis of our algorithm bounds the number of iterations by using the total deviation of $P^{(t)}$ from stationarity as a potential function. Using the techniques of OV, it is possible to show that, whenever an unbalanced cut $S^{(t)}$ is found, most of the deviation of $P^{(t)}$ can be attributed to $S^{(t)}.$ In words, we can think of $S^{(t)}$ as the main reason why $P^{(t)}$ is not mixing. Formally,

Moreover, we can show that accelerating the convergence of the walk from $S^{(t)}$ has the effect of removing from $P^{(t+1)}$ a large fraction of the deviation due to $S^{(t)}.$ The proof is a simple application of the Golden-Thompson inequality and mirrors the main step in the MMWU analysis. Hence, we can show the total deviation of $P^{(t+1)}$ is just a constant fraction of that of $P^{(t)}.$

1.6 Exponential Embeddings of Graph and Proof Ideas

2 Our Algorithms to Compute an Approximation to exp⁡(−A)​v𝐴𝑣\exp(-A)v

In this section, we give an overview of the algorithms in Theorem 1.2 and Theorem 1.4 and their proofs. The algorithm for Theorem 1.3 is very similar to the one for Theorem 1.2 and we give the details in Section 6.3.2. A few quick definitions: A matrix $M$ is called Upper Hessenberg if, $(M)_{ij}=0$ for $i>j+1.$ $M$ is called tridiagonal if $M_{ij}=0$ for $i>j+1$ and for $j>i+1.$ Let $\lambda_{1}(M)$ and $\lambda_{n}(M)$ denote the largest and smallest eigenvalues of $M$ respectively.

As we mention in the introduction, the matrices that we need to exponentiate for the BS algorithm are no longer sparse or SDD. Thus, Theorem 1.2 is insufficient for our application. Fortunately, the following theorem suffices and its proof is not very different from that of Theorem 1.2, which is explained below. Its proof appears in Section 6.4.

Recall from Section 3.1.4 that our algorithm for BS requires us to compute $\exp(-A)v$ for a matrix $A$ of the form $D^{-\nicefrac{{1}}{{2}}}(L+\sum_{i}\beta_{i}L(S_{i}))D^{-\nicefrac{{1}}{{2}}},$ where $\beta_{i}\geq 0.$ We first note that if we let $\Pi\stackrel{{\scriptstyle\text{\tiny def}}}{{=}}I-\nicefrac{{1}}{{2m}}\cdot(D^{\nicefrac{{1}}{{2}}}{1})(D^{\nicefrac{{1}}{{2}}}{1})^{\top},$ the projection onto the space orthogonal to $\nicefrac{{1}}{{\sqrt{2m}}}\cdot D^{\nicefrac{{1}}{{2}}}{1},$ then, for each $i,$ $D^{-\nicefrac{{1}}{{2}}}L(S_{i})D^{-\nicefrac{{1}}{{2}}}=\Pi(\nicefrac{{d_{i}}}{{2m}}\cdot I+e_{i}e_{i}^{\top})\Pi.$ Since $D^{\nicefrac{{1}}{{2}}}{1}$ is an eigenvector of $D^{-\nicefrac{{1}}{{2}}}LD^{-\nicefrac{{1}}{{2}}},$ we have, $\Pi D^{-\nicefrac{{1}}{{2}}}LD^{-\nicefrac{{1}}{{2}}}\Pi=D^{-\nicefrac{{1}}{{2}}}LD^{-\nicefrac{{1}}{{2}}}.$ Thus,

This is of the form $\Pi HMH\Pi,$ where $H\stackrel{{\scriptstyle\text{\tiny def}}}{{=}}D^{-\nicefrac{{1}}{{2}}}$ is diagonal and $M$ is SDD. It is worth noting that since $A$ itself may be neither sparse nor SDD, we cannot apply the Spielman-Teng SDD solver to approximate $(I+\alpha A)^{-1}.$ The proof of the above theorem uses the Sherman-Morrison formula to extend the SDD solver to fit our requirement. Moreover, to obtain a version of Theorem 1.4 for such matrices, we do not have to do anything additional since multiplication by $H$ and $\Pi$ take $O(n)$ steps and hence, $t_{A}$ is still $O(m_{M}+n).$ The details appear in Section 6.4. Finally, note that in our application, $\|HMH\|$ is ${\rm poly}(n).$

We now give an overview of the proofs of Theorem 1.2 and Theorem 1.4. First, we explain a general method known as the Lanczos method, which is pervasive in numerical linear algebra. We then show how suitable adaptations of this can be combined with (old and new) structural results in approximation theory to obtain our results.

Since exact computation of $f(B)$ usually requires diagonalization of $B,$ which could take as much as $O(n^{3})$ time (see ), we seek an approximation to $f(B)v$. The Lanczos method allows us to do exactly that: It looks for an approximation to $f(B)v$ of the form $p(B)v$, where $p$ is a polynomial of small degree, say $k$. Before we describe how, we note that it computes this approximation in roughly $O((t_{B}+n)k)$ time plus the time it takes to compute $f(\cdot)$ on a $(k+1)\times(k+1)$ tridiagonal matrix, which can often be upper bounded by $O(k^{2})$ (see ). Hence, the time is reduced to $O((t_{B}+n)k+k^{2}).$ What one has lost in this process is accuracy: The candidate vector $u$ output by the Lanczos method, is now only an approximation to $f(B)v.$ The quality of approximation, or $\|f(B)v-u\|,$ can be upper bounded by the uniform error of the best degree $k$ polynomial approximating $f$ in the interval $[\lambda_{n}(B),\lambda_{1}(B)].$ Roughly, $\|f(B)v-u\|\approx(\min_{p_{k}\in\Sigma_{k}}\sup_{x\in[\lambda_{1}(B),\lambda_{n}(B)]}|f(x)-p_{k}(x)|).$ Here $\Sigma_{k}$ is the collection of all real polynomials of degree at most $k.$ Surprisingly, one does not need to know the best polynomial and proving existence of good polynomials is sufficient. By increasing $k,$ one can reduce this error and, indeed, if one lets $k=n,$ there is no error. Thus, the task is reduced to proving existence of low degree polynomials that approximate $f$ within the error tolerable for the applications.

Computing the Best Polynomial Approximation.

Now, we describe in detail, the Lanczos method and how it achieves the error guarantee claimed above. Notice that for any polynomial $p$ of degree at most $k,$ the vector $p(B)v$ lies in $\mathcal{K}\stackrel{{\scriptstyle\text{\tiny def}}}{{=}}{\mathsf{Span}}\{v,Bv,\ldots,B^{k}v\}$ – called the Krylov subspace. The Lanczos method iteratively creates an orthonormal basis $\{v_{i}\}_{i=0}^{k}$ for $\mathcal{K}$, such that $\forall\ i\leq k,\ {\mathsf{Span}}\{v_{0},\ldots,v_{i}\}={\mathsf{Span}}\{v,\ldots,B^{i}v\}.$ Let $V_{k}$ be the $n\times(k+1)$ matrix with $\{v_{i}\}_{i=0}^{k}$ as its columns. Thus, $V_{k}V_{k}^{\top}$ denotes the projection onto the Krylov subspace. We let $T_{k}$ be the $(k+1)\times(k+1)$ matrix expressing $B$ as an operator restricted to $\mathcal{K}$ in the basis $\{v_{i}\}_{i=0}^{k}$, i.e., $T_{k}\stackrel{{\scriptstyle\text{\tiny def}}}{{=}}V_{k}^{\top}BV_{k}.$ Note that this is not just a change of basis, since vectors in $\mathcal{K}$ can be mapped by $B$ to vectors outside $\mathcal{K}$. Now, since $v,Bv\in\mathcal{K}$, we must have $Bv=(V_{k}V^{\top}_{k})B(V_{k}V^{\top}_{k})v=V_{k}(V^{\top}_{k}BV_{k})V_{k}^{\top}v=V_{k}T_{k}V_{k}^{\top}v.$ Iterating this argument, we get that for all $i\leq k$, $B^{i}v=V_{k}T_{k}^{i}V_{k}^{\top}v,$ and hence, by linearity, $p(B)v=V_{k}p(T_{k})V_{k}^{\top}v,$ for any polynomial $p$ of degree at most $k.$

Now, a natural approximation for $f(B)v$ is $V_{k}f(T_{k})V_{k}^{\top}v$. Writing $r_{k}(x)\stackrel{{\scriptstyle\text{\tiny def}}}{{=}}f(x)-p_{k}(x),$ where $p_{k}$ is any degree $k$ approximation to $f(x)$, the error in the approximation is $f(B)v-V_{k}f(T_{k})V_{k}^{\top}v=r_{k}(B)v-V_{k}r_{k}(T_{k})V_{k}^{\top}v,$ for any choice of $p_{k}.$ Hence, the norm of the error vector is at most $(\left\lVert r_{k}(B)\right\rVert+\left\lVert r_{k}(T_{k})\right\rVert)\left\lVert v\right\rVert,$ which is bounded by the value of $r_{k}$ on the eigenvalues of $B$ (eigenvalues of $T_{k}$ are a subset of eigenvalues of $B$). More precisely, the norm of the error is bounded by $2\left\lVert v\right\rVert\cdot\max_{\lambda\in\text{Spectrum}(B)}|f(\lambda)-p_{k}(\lambda)|.$ Minimizing over $p_{k}$ gives the error bound claimed above. Note that we do not explicitly need the approximating polynomial. It suffices to prove that there exists a degree $k$ polynomial that uniformly approximates $f$ well on an interval containing the spectrum of $B$ and $T_{k}.$

If we construct the basis iteratively as above, $Bv_{j}\in{\mathsf{Span}}\{v_{0},\ldots,v_{j+1}\}$ by construction, and if $i>j+1,$ $v_{i}$ is orthogonal to this subspace and hence $v_{i}^{\top}(Bv_{j})=0$. Thus, $T_{k}$ is Upper Hessenberg. Moreover, if $B$ is symmetric, $v_{j}^{\top}(Bv_{i})=v_{i}^{\top}(Bv_{j}),$ and hence $T_{k}$ is symmetric and tridiagonal. This means that while constructing the basis, at step $i+1$, it needs to orthonormalize $Bv_{i}$ only w.r.t. $v_{i-1}$ and $v_{i}$. Thus the total time required is $O((t_{B}+n)k)$, plus the time required for the computation of $f(T_{k})$, which can typically be bounded by $O(k^{2})$ for a tridiagonal matrix (using ). This completes an overview of the Lanczos method. The Lanczos procedure described in Figure 4 in the main body, implements the Lanczos method. We now move on to describing how we apply it to obtain our two algorithms.

Our Algorithm.

The starting point of the algorithm that underlies Theorem 1.2 is a rather surprising result by Saff, Schönhage and Varga (SSV) , which says that for any integer $k,$ there exists a degree $k$ polynomial $p_{k}^{\star}$ such that, $p_{k}^{\star}((1+\nicefrac{{x}}{{k}})^{-1})$ approximates $e^{-x}$ up to an error of $O(k\cdot 2^{-k})$ over the interval $[0,\infty)$ (Theorem 6.8, Corollary 6.9). Then, to compute $\exp(-A)v,$ one could apply the Lanczos method with $B\stackrel{{\scriptstyle\text{\tiny def}}}{{=}}(I+\nicefrac{{A}}{{k}})^{-1}$ and $f(x)\stackrel{{\scriptstyle\text{\tiny def}}}{{=}}e^{k(1-\nicefrac{{1}}{{x}})}.$ Essentially, this was the method suggested by Eshof and Hochbruck . The strong approximation guarantee of the SSV result along with the guarantee of the Lanczos method from the previous section, would imply that the order of the Krylov subspace for $B$ required would be roughly $\log\nicefrac{{1}}{{\delta}},$ and hence, independent of $\|A\|.$ The running time is then dominated by the computation $Bv=(I+\nicefrac{{A}}{{k}})^{-1}v.$

EH note that the computation of exact matrix inverse is a costly operation ($O(n^{3})$ time in general) and all known faster methods for inverse computation incur some error. They suggest using the Lanczos method with faster iterative methods, e.g. Conjugate Gradient, for computing the inverse (or rather the product of the inverse with a given vector) as a heuristic. They make no attempt to give a theoretical justification of why approximate computation suffices. Also note that, even if the computation was error-free, a method such as Conjugate Gradient will have running time which varies with $\sqrt{\nicefrac{{\lambda_{1}(A)}}{{\lambda_{n}(A)}}}$ in general. Thus, the EH method falls substantially short of resolving the hypothesis mentioned in the introduction.

To be able to prove Theorem 1.2 using the SSV guarantee, we have to adapt the Lanczos method in several ways, and hence, deviate from the method suggested by EH: 1) EH construct $T_{k}$ as a tridiagonal matrix as Lanczos method suggests, but since the computation is no longer exact, the basis $\{v_{i}\}_{i=0}^{k}$ is no longer guaranteed to be orthonormal. As a result, the proofs of the Lanczos method break down. Our algorithm, instead, builds an orthonormal basis, which means that $T_{k}$ becomes an Upper Hessenberg matrix instead of tridiagonal and we need to compute $k^{2}$ dot products in order to compute $T_{k}.$ 2) With $T_{k}$ being asymmetric, several nice spectral properties are lost, e.g. real eigenvalues and an orthogonal set of eigenvectors. We overcome this fact by symmetrizing $T_{k}$ to construct $\widehat{T}_{k}=\frac{T_{k}+T_{k}^{\top}}{2}$ and computing our approximation with $\widehat{T}_{k}.$ This permits us to bound the quality of a polynomial approximation applied to $\widehat{T}_{k}$ by the behavior of the polynomial on the eigenvalues of $\widehat{T}_{k}$. 3) Our analysis is based on the SSV approximation result, which is better than the variant proved and used by EH. Moreover, for their shifting technique, which is the source of the $\left\lVert\exp(-A)\right\rVert$ factor in the hypothesis, the given proof in EH is incorrect and it is not clear if the given bound could be achieved even under exact computationEH show the existence of degree $k$ polynomials in $(1+\nu x)^{-1}$ for any constant $\nu\in(0,1),$ that approximate $e^{-x}$ up to an error of $\exp(\nicefrac{{1}}{{2\nu}}-\Theta(\sqrt{k(\nu^{-1}-1)})).$ In order to deduce the claimed hypothesis, it needs to be used for $\nu\approx\nicefrac{{1}}{{\lambda_{n}(A)}},$ in which case, there is a factor of $e^{\lambda_{n}(A)}$ in the error, which could be huge.. 4) Most importantly, since $A$ is SDD, we are able to employ the Spielman-Teng solver (Theorem 6.10) to approximate $(I+\nicefrac{{A}}{{k}})^{-1}v$. This procedure, called ExpRational, has been described in Figure 5 in the main body.

Error Analysis.

To complete the proof of Theorem 1.2, we need to analyze the role of the error that creeps in due to approximate matrix inversion. The problem is that this error, generated in each iteration of the Krylov basis computation, propagates to the later steps. Thus, small errors in the inverse computation may lead to the basis $V_{k}$ computed by our algorithm to be quite far from the $k$-th order Krylov basis for $B,v.$ We first show that, assuming the error in computing the inverse is small, $\widehat{T}_{k}$ can be used to approximate degree $k$ polynomials of $B=(I+\nicefrac{{A}}{{k}})^{-1}$ when restricted to the Krylov subspace, i.e. $\|p(B)v-V_{k}p(\widehat{T}_{k})V_{k}^{\top}v\|\lessapprox\left\lVert p\right\rVert_{1}.$ Here, if $p\stackrel{{\scriptstyle\text{\tiny def}}}{{=}}\sum_{i=0}^{k}a_{i}\cdot x^{i},$ $\left\lVert p\right\rVert_{1}=\sum_{i\geq 0}^{k}|a_{i}|.$ This is the most technical part of the error analysis and unfortunately, the only way we know of proving the error bound above is by tour de force. A part of this proof is to show that the spectrum of $\widehat{T}_{k}$ cannot shift far from the spectrum of $B.$

To bound the error in the candidate vector output by the algorithm, i.e. $\|f(B)v-V_{k}f(\widehat{T}_{k})V_{k}^{\top}v\|,$ we start by expressing $e^{-x}$ as the sum of a degree $k$-polynomial $p_{k}$ in $(1+\nicefrac{{x}}{{k}})^{-1}$ and a remainder function $r_{k}.$ We use the analysis from the previous paragraph to upper bound the error in the polynomial part by $\approx\left\lVert p\right\rVert_{1}.$ We bound the contribution of the remainder term to the error by bounding $\left\lVert r_{k}(B)\right\rVert$ and $\|{r_{k}(\widehat{T}_{k})}\|.$ This step uses the fact that eigenvalues of $r_{k}(\widehat{T}_{k})$ are $\{r_{k}(\lambda_{i})\}_{i},$ where $\{\lambda_{i}\}_{i}$ are eigenvalues of $\widehat{T_{k}}.$ This is the reason our algorithm symmetrizes $T_{k}$ to $\widehat{T}_{k}.$ To complete the error analysis, we use the polynomials $p_{k}^{\star}$ from SSV and bound $\left\lVert p_{k}^{\star}\right\rVert_{1}.$ Even though we do not know $p_{k}^{\star}$ explicitly, we can bound its coefficients indirectly by writing it as an interpolation polynomial. All these issues make the error analysis highly technical. However, since the error analysis is crucial for our algorithms, a more illuminating proof is highly desirable.

In this section, we give a brief overview of the proof of Theorem 1.5. The details appear in Section 7 and can be read independently of the rest of the paper.

A straightforward approach to approximate $e^{-x}$ over $[a,b]$ is by truncating its series expansion around $\frac{a+b}{2}.$ With a degree of the order of $(b-a)+\log\nicefrac{{1}}{{\delta}},$ these polynomials achieve an error of $\delta\cdot e^{-\nicefrac{{(b+a)}}{{2}}}$, for any constant $\delta>0.$ This approach is equivalent to approximating $e^{\lambda}$ over $,$ for $\lambda\stackrel{{\scriptstyle\text{\tiny def}}}{{=}}\nicefrac{{(b-a)}}{{2}},$ by polynomials of degree $O(\lambda+\log\nicefrac{{1}}{{\delta}}).$ On the flip side, it is known that if $\lambda$ is constant, the above result is optimal (see e.g. ). Instead of polynomials, one could consider approximations by rational functions, as in . However, the author in shows that, if both $\lambda$ and the degree of the denominator of the rational function are constant, the required degree of the numerator is only an additive constant better than that for the polynomials. It might seem that the question of approximating the exponential has been settled and one cannot do much better. However, the result by SSV mentioned before, seems surprising in this light. The lower bound does not apply to their result, since the denominator of their rational function is unbounded. In a similar vein, we ask the following question: If we are looking for weaker error bounds, e.g. $\delta\cdot e^{-a}$ instead of $\delta\cdot e^{-\nicefrac{{(b+a)}}{{2}}}$ (recall $b>a$), can we improve on the degree bound of $O((b-a)+\log\nicefrac{{1}}{{\delta}})$? Theorem 1.5 answers this question in the affirmative and gives a new upper bound and an almost matching lower bound. We give an overview of the proofs of both these results next.

Lower Bound.

Discussion and Open Problems

The main remaining open question regarding the design of spectral algorithms for BS is whether it is possible to obtain stronger certificates that no sparse balanced cuts exist, in nearly-linear time. This question is of practical importance in the construction of decompositions of the graph into induced graphs that are near-expanders, in nearly-linear time . OV show that their certificate, which is of the same form as that of BalSep, is stronger than the certificate of Spielman and Teng . In particular, our certificate can be used to produce decompositions into components that are guaranteed to be subsets of induced expanders in $G.$ However, this form of certificate is still much weaker than that given by RLE, which actually outputs an induced expander of large volume.

With regards to approximating the Matrix exponential, a computation which plays an important role in SDP-based algorithms, random walks, numerical linear algebra and quantum computing, settling the hypothesis remains the main open question. Further, as noted earlier, the error analysis plays a crucial role in making Theorem 1.2 and, hence, Theorem 1.1 work, but its proof is rather long and difficult. A more illuminating proof of this would be highly desirable.

Another question is to close the gap between the upper and lower bounds on polynomial approximations to $e^{-x}$ over an interval $[a,b]$ in Theorem 1.5.

The Algorithm for Balanced Separator

In this section we provide our spectral algorithm BalSep and prove Theorem 1.1. We also mention how Theorem 3.1 follows easily from the proof of Theorem 1.1 and Theorem 1.4. We first present the preliminaries for this section.

Special Graphs

We denote by $K_{V}$ the complete graph with weight $\nicefrac{{d_{i}d_{j}}}{{2m}}$ between every pair $i,j\in V.$ For $i\in V,$ $S_{i}$ is the star graph rooted at $i$, with edge weight of $\nicefrac{{d_{i}d_{j}}}{{2m}}$ between $i$ and $j,$ for all $j\in V.$

Graph matrices.

Vector and Matrix Notation.

$L(K_{V})=D-\nicefrac{{1}}{{2m}}\cdot D{\bf 1}{\bf 1}^{\top}D=D^{\nicefrac{{1}}{{2}}}(I-\nicefrac{{1}}{{2m}}\cdot D^{\nicefrac{{1}}{{2}}}{\bf 1}{\bf 1}D^{\nicefrac{{1}}{{2}}})D^{\nicefrac{{1}}{{2}}}.$

Embedding Notation.

$\sum_{i\in V}d_{i}R_{i}\bullet X=\sum_{i\in V}d_{i}\left\lVert v_{i}-v_{\mathsf{avg}}\right\rVert^{2}=\nicefrac{{1}}{{2m}}\cdot\sum_{i<j}d_{j}d_{i}\left\lVert v_{i}-v_{j}\right\rVert^{2}=L(K_{V})\bullet X.$

2 AHK Random Walks

A useful matrix to study $\mathcal{H}(\beta)$ will be $D^{-1}P_{2\tau}(\beta).$ This matrix describes the probability distribution over the edges of $G$ and has the advantage of being symmetric and positive semidefinite:

$D^{-\nicefrac{{1}}{{2}}}P_{\tau}(\beta)$ is a square root of $D^{-1}P_{2\tau}(\beta).$

Hence, $D^{-1}P_{2\tau}(\beta)$ is the Gram matrix of the embedding given by the columns of its square root $D^{-\nicefrac{{1}}{{2}}}P_{\tau}(\beta).$ This property will enable us to use geometric SDP techniques to analyze $\mathcal{H}(\beta).$

Mixing.

A fundamental quantity for our algorithm will be the total deviation from stationarity over a subset $S\subseteq V.$ We will denote $\Psi(P_{t}(\beta),S)\stackrel{{\scriptstyle\text{\tiny def}}}{{=}}\sum_{i\in S}\Psi(P_{t}(\beta),i).$ In particular, $\Psi(P_{\tau}(\beta),V)$ will play the role of potential function in our algorithm. The following facts express these mixing quantities in the geometric language of the embedding corresponding to $D^{-1}P_{2\tau}(\beta).$

$\Psi(P_{\tau}(\beta),i)=d_{i}R_{i}\bullet D^{-1}P_{2\tau}(\beta).$

Proof: By Fact 5.3 and the definition of $R_{i}:$

The following is a consequence of Fact 5.2:

$\Psi(P_{\tau}(\beta),V)=\sum_{i\in V}d_{i}R_{i}\bullet D^{-1}P_{2\tau}(\beta)=L(K_{V})\bullet D^{-1}P_{2\tau}(\beta).$

3 Algorithm Description

Our algorithm BalSep will call two subroutines FindCut and ExpV. FindCut is an SDP-rounding algorithm that uses random projections and radial sweeps to find a low-conductance cut, that is either $c$-balanced, for some constant $c=\Omega(b)\leq\nicefrac{{b}}{{100}}$ defined in OV, or obeys a strong guarantee stated in Theorem 5.8. Such algorithm is implicit in and is described precisely in Section 5.7. ExpV is a generic algorithm that approximately computes products of the form $P_{\tau}(\beta)u$ for unit vectors $u.$ Expv can be chosen to be either the algorithm implied by Thereom 3.2, which makes use of the Spielman-Teng solver, or that in Theorem 1.4, which just applies the Lanczos method.

We are now ready to describe BalSep, which will output a $c$-balanced cut of conductance $O(\sqrt{\gamma})$ or the string NO, if it finds a certificate that no $b$-balanced cut of conductance less than $\gamma$ exists. BalSep can also fail and output the string Fail. We will show that this only happens with small probability. The algorithm BalSep is defined in Figure 1. The constants in this presentation are not optimized and are likely to be higher than what is necessary in practice. They can also be modified to obtain different trade-offs between the approximation guarantee and the output balance.

At iteration $t=1,$ we have $\beta^{(1)}={\bf 0},$ so that $P^{(1)}$ is just the probability transition matrix of the heat kernel on $G$ for time $\tau.$ In general at iteration $t,$ BalSep runs ExpV to compute $O(\log n)$ random projections of $P^{(t)}$ and constructs an approximation $\{v^{(t)}_{i}\}_{i\in V}$ to the embedding given by the columns of $D^{-\nicefrac{{1}}{{2}}}P^{(t)}.$ This approximate embedding has Gram matrix $X^{(t)}.$

In Step $2,$ BalSep computes $L(K_{V})\bullet X^{(t)},$ which is an estimate of the total deviation $\Psi(P^{(t)},V)$ by Fact 5.5. If this deviation is small, the AHK walk $P^{(t)}$ has mixed sufficiently over $G$ to yield a certificate that $G$ cannot have any $b$-balanced cut of conductance less than $\gamma.$ This is shown in Lemma 5.6. If the AHK walk $P^{(t)}$ has not mixed sufficiently, we can use FindCut to find a cut $S^{(t)}$ of low conductance $O(\sqrt{\gamma}),$ which is an obstacle for mixing. If $S^{(t)}$ is $c$-balanced , we output it and terminate. Similarly, if $S\cup S^{(t)}$ is $c$-balanced, as $\phi(S\cup S^{(t)})\leq O(\sqrt{\gamma}),$ we can also output $S\cup S^{(t)}$ and exit. Otherwise, $S^{(t)}$ is unbalanced and is potentially preventing BalSep from detecting balanced cuts in $G.$ We then proceed to modify the AHK walk, by increasing the values of $\beta^{(t+1)}$ for the vertices in $S^{(t)}.$ This change ensures that $P^{(t+1)}$ mixes faster from the vertices in $S^{(t)}$ and in particular mixes across $S^{(t)}.$ In particular, this means that, at any given iteration $t,$ the support of $\beta^{(t)}$ is $\cup_{r=1}^{t-1}S^{(r)},$ which is an unbalanced set.

The BalSep algorithm exactly parallels the RLE algorithm, introducing only two fundamental changes. First, we use the embedding given by the AHK random walk $P^{(t)}$ in place of the eigenvector to find cuts in $G$ or in a residual graph. Secondly, rather than fully removing unbalanced low-conductance cuts from the graph, we modify $\beta^{(t)}$ at every iteration $t,$ so $P^{(t+1)}$ at the next iteration mixes across the unbalanced cuts found so far.

4 Analysis

The analysis of BalSep is at heart a modification of the MMWU argument in OV, stated in a random-walk language. This modification allows us to deal with the different embedding used by BalSep at every iteration with respect to OV.

In this analysis, the quantity $\Psi(P^{(t)},V)$ plays the role of potential function. Recall that, from a random-walk point of view, $\Psi(P^{(t)},V)$ is the total deviation from stationarity of $P_{\tau}(\beta^{(t)})$ over all vertices as starting points. We start by showing that if the potential function is small enough, we obtain a certificate that no $b$-balanced cut of conductance at most $\gamma$ exists. In the second step, we show that, if an unbalanced cut $S^{(t)}$ of low conductance is found, the potential decreases by a constant fraction. Unless explicitly stated otherwise, all proofs are found in Section 5.5.

We argue that, if $\Psi(P^{(t)},V)$ is sufficiently small, it must be the case that $G$ has no $b$-balanced cut of conductance less than $\gamma.$ A similar result is implicit in OV. This theorem has a simple explanation in terms of the AHK random walk $P^{(t)}.$ Notice that $P^{(t)}$ is accelerated only on a small unbalanced set $S.$ Hence, if a balanced cut of conductance less than $\gamma$ existed, its convergence could not be greatly helped by the acceleration over $S.$ Then, if $P^{(t)}$ is still mixing very well, no such balanced cut can exist.

Let $S=\cup_{i=1}^{t}S^{(i)}.$ If $\Psi(P^{(t)},V)\leq\frac{4}{3n},$ and ${\mathsf{vol}}(S)\leq c\cdot 2m\leq\nicefrac{{b}}{{100}}\cdot 2m$, then

Moreover, this implies that no $b$-balanced cut of conductance less than $\gamma$ exists in $G.$

The Deviation of an Unbalanced Cut.

In the next step, we show that, if the walk has not mixed sufficiently, w.h.p. the embedding $\{v^{(t)}_{i}\}_{i\in V},$ computed by BalSep, has low quadratic form with respect to the Laplacian of $G.$ From a SDP-rounding perspective, this means that the embedding can be used to recover cuts of value close to $\gamma.$ This part of the analysis departs from that of OV, as we use our modified definition of the embedding.

If $\Psi(P^{(t)},V)\geq\frac{1}{n},$ then w.h.p. $L\bullet X^{(t)}\leq O(\gamma)\cdot L(K_{V})\bullet X^{(t)}.$

This guarantee on the embedding allows us to apply SDP-rounding techniques in the subroutine FindCut. The following result is implicit in . Its proof appears in Section 5.7 for completeness.

The following corollary is a simple consequence of Lemma 5.7 and Theorem 5.8:

At iteration $t$ of BalSep, if $\Psi(P^{(t)},V)\geq\frac{1}{n}$ and $S^{(t)}$ is not $c$-balanced, then w.h.p. $\Psi(P^{(t)},S)\geq\nicefrac{{1}}{{2}}\cdot\Psi(P^{(t)},V).$

In words, at the iteration $t$ of BalSep, the cut $S^{(t)}$ must either be $c$-balanced or be an unbalanced cut that contributes a large constant fraction of the total deviation of $P^{(t)}$ from the stationary distribution. In this sense, $S^{(t)}$ is the main reason for the failure of $P^{(t)}$ to achieve better mixing. To eliminate this obstacle and drive the potential further down, $P^{(t)}$ is updated to $P^{(t+1)}$ by accelerating the convergence to stationary from all vertices in $S^{(t)}.$ Formally, this is achieved by adding weighted stars rooted at all vertices over $S^{(t)}$ to the transition-rate matrix of the AHK random walk $P^{(t)}$.

Potential Reduction.

The next theorem crucially exploits the stability of the process $\mathcal{H}(\beta^{(t)})$ and Corollary 5.9 to show that the potential decreases by a constant fraction at every iteration in which an unbalanced cut is found. More precisely, the theorem shows that accelerating the convergence from $S^{(t)}$ at iteration $t$ of BalSep has the effect of eliminating at least a constant fraction of the total deviation due to $S^{(t)}.$ The proof is a simple application of the Golden-Thompson inequality and mirrors the main step in the MMWU analysis.

At iteration $t$ of BalSep, if $\Psi(P^{(t)},V)\geq\frac{1}{n}$ and $S^{(t)}$ is not $c$-balanced, then w.h.p.

We are now ready to prove Theorem 1.1 and Theorem 3.1 by applying Lemma 5.10 to show that after $O(\log n)$ iterations, the potential must be sufficiently low to yield the required certificate according to Lemma 5.6.

Proof: [Proof of Theorem 1.1] If BalSep outputs a cut $S$ in Step $4$, by construction, we have that $\phi(S)\leq O(\sqrt{\gamma})$ and $S$ is $\Omega(b)$-balanced. Alternatively, at iteration $t,$ if $L(K_{V})\bullet X^{(t)}\leq\nicefrac{{1+\varepsilon}}{{n}},$ we have by Lemma 5.18 that

Therefore, by Lemma 5.6, we have a certificate that no $b$-balanced cut of conductance less than $\gamma$ exists in $G.$ Otherwise, we must have $L(K_{V})\bullet X^{(t)}\geq\nicefrac{{1+\varepsilon}}{{n}},$ which, by Lemma 5.18, implies that

Then, by Lemma 5.7 and Theorem 5.8, we have w.h.p. that FindCut does not fail and outputs a cut $S^{(t)}$ with $\phi(S^{(t)})\leq O(\sqrt{\gamma}).$ As BalSep has not terminated in Step $4,$ it must be the case that $S^{(t)}$ is not $c$-balanced and, by Theorem 5.10, we obtain that w.h.p. $\Psi(P^{(t+1)},V)\leq\nicefrac{{5}}{{6}}\cdot\Psi(P^{(t)},V).$ Now,

Hence, after $\nicefrac{{2\log n}}{{\log(\nicefrac{{6}}{{5}})}}\leq 12\log n=T$ iterations, w.h.p. we have that $\Psi(P^{(T)},V)\leq\nicefrac{{1}}{{n}}$ and, by Lemma 5.6, no $b$-balanced cut of conductance less than $\gamma$ exists.

We now consider the running time required by the algorithm at every iteration. In Step $1,$ we compute $k=O(\log n),$ products of the form $D^{-\nicefrac{{1}}{{2}}}P^{(t)}u,$ where $u$ is an unit vector, using the ExpV algorithm based on the Spielman-Teng solver, given in Theorem 3.2. This application of Theorem 3.2 is explained in Section 3.2. By the definition of $\beta^{(t)},$ at iteration $t$ we have:

5 Proofs

In this section we provide the proofs from the Section 5. We start with some preliminaries.

Vector and Matrix Notation.

$L\preceq 2\cdot D$ and $L(S_{i})\preceq 2\cdot D.$

For all $i\in V,$ $L(S_{i})=\nicefrac{{d_{i}}}{{2m}}\cdot L(K_{V})+d_{i}R_{i}.$ In particular, $L(S_{i})\succeq d_{i}R_{i}.$

Notation for BalSep.

The following are useful facts to record about $C^{(t)}:$

The vector $D^{\nicefrac{{1}}{{2}}}$ is the eigenvector of $C^{(t)}$ with smallest eigenvalue $0.$

5.2 Useful Lemmata

$\Psi(P^{(t)},V)=L(K_{V})\bullet D^{-1}P_{2\tau}(\beta^{(t)})={\rm Tr}(e^{-2\tau C^{(t)}})-1.$

Using Fact 5.1 and the cyclic property of the trace function, we obtain

Finally, by Fact 5.13, we must have that the right-hand side equals ${\rm Tr}(e^{-2\tau C^{(t)}})-1,$ as required.

The following lemma is a simple consequence of the convexity of $e^{-x}.$ It is proved in .

5.3 Proof of Lemma 5.6

Let $S=\cup_{i=1}^{t}S^{(i)}$ and set $\beta\stackrel{{\scriptstyle\text{\tiny def}}}{{=}}\beta^{(t)}.$ By Lemma 5.15, we have ${\rm Tr}(e^{-2\tau C^{(t)}})-1\leq\nicefrac{{4}}{{3n}}.$ Hence, $\lambda_{n-1}(e^{-2\tau C^{(t)}})\leq\nicefrac{{4}}{{3n}},$ which implies that, by taking logs,

which proves the first part of the Lemma.

For the second part, we start by noticing that, for $i\in S,$ $\beta^{(t)}_{i}\leq 72\gamma\cdot\nicefrac{{t}}{{T}}\leq 72\gamma.$ Now for any $b$-balanced cut $U,$ with ${\mathsf{vol}}(U)\leq{\mathsf{vol}}(\bar{U}),$ consider the vector $x_{U}$ defined as

Applying the guarantee of Equation 1, we obtain

As ${\mathsf{vol}}(S)\leq\nicefrac{{b}}{{100}}\cdot 2m\leq\nicefrac{{{\mathsf{vol}}(U)}}{{100}},$ we have $\phi(U)\geq\gamma.$

5.4 Proof of Lemma 5.7

Proof: Consider $L\bullet D^{-1}P_{2\tau}(\beta{{}^{(t)}})=L\bullet D^{-\nicefrac{{1}}{{2}}}e^{-2\tau C^{(t)}}D^{-\nicefrac{{1}}{{2}}}.$ Using the cyclic property of trace and the definition of $C^{(t)},$ we have that

We now consider the spectrum of $C^{(t)}.$ By Fact 5.13, the smallest eigenvalue is $0.$ Let the remaining eigenvalues be $\lambda_{2}\leq\lambda_{3}\leq\cdots\leq\lambda_{n}.$ Then, $C^{(t)}\bullet e^{-2\tau C^{(t)}}=\sum_{i=2}^{n}\lambda_{i}e^{-2\tau\lambda_{i}}.$ We will analyze these eigenvalues in two groups. For the first group, we consider eigenvalues smaller than $24\gamma$ and use Lemma 5.15, together with the fact that $\gamma\geq\nicefrac{{1}}{{n^{2}}}:$

For the remaining eigenvalues, we have, by Lemma 5.14::

Now, we apply the Johnson-Lindenstrauss Lemma (Lemma 5.18) to both sides of this inequality to obtain:

5.5 Proof of Corollary 5.9

Proof: By Lemma 5.7 and Theorem 5.8, we have that $S^{(t)}$ w.h.p. is either $c$-balanced or $\sum_{i\in S^{(t)}}d_{i}R_{i}\bullet X^{(t)}\geq\nicefrac{{2}}{{3}}\cdot L(K_{V})\bullet X^{(t)}.$ By Lemma 5.18 and as $\nicefrac{{1+\varepsilon}}{{1-\varepsilon}}\leq\nicefrac{{4}}{{3}},$ we have w.h.p.:

5.6 Proof of Theorem 5.10

Proof: By Lemma 5.15 and the Golden-Thompson inequality in Lemma 5.17:

We now apply Lemma 5.16 to the second term under trace. To do this we notice that $\sum_{i\in S^{(t)}}L(S_{i})\preceq 2L(K_{V})\preceq 2D,$ so that

Applying the cyclic property of trace, we get

Next, we use Fact 5.12 to replace $L(S_{i})$ by $R_{i}$ and notice that $288\cdot\nicefrac{{\tau\gamma}}{{T}}=2:$

Then, we apply the definition of $\Psi(P^{(t)},S):$

Finally, by Corollary 5.9, we know that w.h.p. $\Psi(P^{(t)},S^{(t)})\geq\nicefrac{{1}}{{2}}\cdot\Psi(P^{(t)},V)$ and the required result follows.

6 SDP Interpretation

In this case, the MMWU uses Equation 2 to produce a candidate solution $Y^{(t+1)}$ with lower objective value. Otherwise, FindCut is run on the embedding corresponding to $Y^{(t)}.$ By Theorem 5.8, this yields either a cut of the required balance or a dual certificate that $Y^{(t)}$ is infeasible. This certificate has the form

and is used by the update to construct the next candidate $Y^{(t+1)}.$ The number of iterations necessary is determined by the width of the two possible updates described above. A simple calculation shows that the width of the update for Equation 2 is $\Theta(1),$ while for Equation 3, it is only $O(\gamma).$ Hence, the overall width is $\Theta(1),$ implying that $O(\nicefrac{{\log n}}{{\gamma}})$ iteration are necessary for the algorithm of OV to produce a dual certificate that the SDP is infeasible and therefore no $b$-balanced cut of conductance $\gamma$ exists.

Our modification of the update is based on changing the starting candidate solutions from $Y^{(1)}\propto D^{-1}$ to $X^{(1)}\propto D^{-\nicefrac{{1}}{{2}}}e^{-2\tau D^{-\nicefrac{{1}}{{2}}}LD^{-\nicefrac{{1}}{{2}}}}D^{-\nicefrac{{1}}{{2}}}.$ In Lemma 5.6 and Lemma 5.7, we show that this modification implies that all $X^{(t)}$ must now have $L\bullet X^{(t)}\leq O(\gamma)\cdot L(K_{V})\bullet X^{(t)}$ or else we find a dual certificate that the SDP is infeasible. This additional guarantee effectively allows us to bypass the update of Equation 2 and only work with updates of the form given in Equation 3. As a result, our width is now $O(\gamma)$ and we only require $O(\log n)$ iterations.