Algorithms and Spectral Graph Theory

\([n]=\{1,\dots,n\}\), where \(n\) is a positive integer.

matrix \(A \in \mathbb{R}^{n\times{n}}\), column vector \(x\in \mathbb{R}^n\), then row vector is \(x^T\)

\(a_{i,j}\) : \((i,j)\)-th entry of \(A, \quad A_j\) : \(j\)-th column of \(A\),

\(\quad \widetilde{A}_{i,j}\) : matrix obtained from \(A\) by deleting \(i\)-th row and \(j\)-th column

Linear (in)dependence: set of vectors \(\{ v_1,\dots,v_k \}\) is linearly independent if

\begin{equation} \nonumber c_1v_1+\dots+c_kv_k=0 \quad \Longrightarrow \quad c_i=0,\forall i \end{equation}

otherwise the set is called linearly dependent.

Span of a set of vectors \(S\), denoted \(\text{span}(S)\), is the set of all linear combinations of the vectors in \(S\). If \(\text{span}(S)=\mathbb{R}^n\), then \(S\) is said to span \(\mathbb{R}^n\).

Basis of \(\mathbb{R}^n\) (or, of a vector space \(V\)) is a linearly independent set of vectors that spans \(\mathbb{R}^n\) (or, \(V\)).

Dimension of a vector space \(V\), denoted \(\text{dim}(V)\), is the size of a basis of \(V\).

For subspaces \(V_1\) and \(V_2\) (of a vector space \(V\)), the sum is \(\{ v_1 + v_2 : v_1\in V_1, v_2\in V_2 \}\) and it is denoted \(V_1 + V_2\). The intersection \(V_1\cap V_2 = \{ v : v\in V_1, v\in V_2 \}\) is a subspace, and we have \(V_1\cap V_2 \subseteq V_i \subseteq V_1+V_2,~i=1,2\).

(Dimension identity): Let \(V\) be a vector space (finite dimensional), and let \(V_1,V_2\) be subspaces of \(V\). Then

\begin{equation} \nonumber \text{dim}(V_1) + \text{dim}(V_2) = \text{dim} (V_1\cap V_2) + \text{dim} (V_1 + V_2). \end{equation}

Nullspace (kernel) of \(A\): \(\text{nullsp}(A) = \{ x\in\mathbb{R}^n : Ax=0 \}\), and \(\text{null}(A)\) denotes the dimension of \(\text{nullsp}(A)\).

Range (image) of \(A\): \(\text{range}(A) = \{ Ax : x\in\mathbb{R}^n \}\), and its dimension is denoted \(\text{rank}(A)\); thus, \(\text{rank}(A) = \max\) no. of linearly independent columns of \(A\).

\begin{equation} \nonumber \text{rank}(A) + \text{null}(A) = n \end{equation}

\(\det(A) = \sum_{j=1}^n (-1)^{i+j} a_{i,j} \det( \widetilde{A}_{i,j} )\)

\(\det(A) = \sum_{\pi\in S^n} \text{sign}(\pi) \prod_{i=1}^n a_{i,\pi(i)}\), where \(\pi: [n] \rightarrow [n]\) is a permutation of \([n]\) (= index set of \(A\)), and \(\text{sign}(\pi) = (-1)^{\text{inv}(\pi)}\), where \(\text{inv}(\pi)\) denotes the number of inversions of \(\pi\), which is, \(\{(i,j):i\lt j\text{ and }\pi(i)>\pi(j)\}\)

\begin{align} \nonumber \det(A) \not=0 \quad &\text{ iff } \text{rank}(A)=n \notag \\ \det(A B) = \quad &\det(A) ~ \det(B) \notag \\ \text{rank}(A)=n \quad &\quad \Longrightarrow \quad A \text{ can be written as a product of elementary matrices} \end{align}

A nonzero-vector \(x\in\mathbb{R}^n\) is called an eigenvector of \(A\) if there exists a number \(\lambda\) s.t. \(Ax = \lambda x\) holds. We call \(\lambda\) an eigenvalue of \(A\).

\begin{equation} \nonumber Ax=\lambda x \text{ iff } (A-\lambda{I})x=0 \text{ iff } \text{null}(A-\lambda{I})\not= 0 \text{ iff } \text{rank}(A-\lambda{I})\lt n \text{ iff } \det(A-\lambda{I})=0 \end{equation}

\(\det(A-\lambda{I})\) is a polynomial of \(\lambda\) of degree \(n\), called the characteristic polynomial of \(A\); each root is an eigenvalue. Thus, \(\det(A-\lambda{I}) = \prod_{i=1}^n (\lambda - \lambda_i)\), where \(\lambda_1,\dots,\lambda_n\) are the roots of the characteristic polynomial; so \(\lambda_1,\dots,\lambda_n\) are the eigenvalues of \(A\). If one of these roots \(\lambda_i\) appears \(k\) times, then we say that \(\lambda_i\) is an eigenvalue of multiplicity \(k\).

For a fixed eigenvalue \(\lambda\), any non-zero vector in \(\text{nullsp}(A-\lambda{I})\) is an eigenvector.

All real symmetric matrices have real eigenvalues (follows from Spectral theorem).

Geometric view: an eigenvector is a direction that is fixed (up to scaling) by the linear transform defined by \(A\)

Eigenspace: for an eigenvalue \(\lambda\), we call \(\text{nullsp}(A-\lambda{I})\) the eigenspace of \(\lambda\). We have: \(\text{null}(A-\lambda{I})\) is the geometric multiplicity of \(\lambda\).

Inner product of vectors \(u, v \in \mathbb{R}^n\), namely, \(\sum_{j=1}^n u_j v_j\) is denoted by \(\langle u,v\rangle\) (or by \(u\cdot{v}\))

Norm (or, length) of a vector \(v\) is \(\Vert v\Vert = \sqrt{\langle v,v\rangle}\)

Orthogonal (or, perpendicular) vectors \(u,v\): \(\langle u,v\rangle=0\)

Set of vectors \(\{v_1,\dots,v_n\}\) is orthogonal if \(\langle v_i,v_j\rangle=0,~ \forall i\neq{j}\)

Set of vectors \(\{v_1,\dots,v_n\}\) is orthonormal if it is orthogonal, and \(\Vert v_i\Vert=1, \forall i\)

Given any basis, we can construct an orthogonal basis by the Gram-Schmidt procedure: Given a basis \(B=\{w_1,\dots,w_k\}\), define the orthogonal basis \(B' = \{v_1,\dots,v_k\}\) by \(v_k = w_k - \sum_{j=1}^k \frac{ \langle w_k,v_j\rangle }{\Vert v_j\Vert} \; v_j,~\forall k: 2\le k\le n\) (and, \(v_1=w_1\)).

Then \(B''=\{ v_1/\Vert v_1\Vert, \dots, v_n/\Vert v_n\Vert \}\) is an orthonormal basis.

If \(B\) is a matrix whose columns form an orthonormal basis, then \(B^T B = I\) and hence the inverse of \(B\), denoted \(B^{-1}\), is equal to \(B^T\).

Application: Power of matrix Let \(L\) be a matrix whose columns form an orthonormal basis of eigenvectors of \(A\). Then \(AL = LD\), where \(D\) is the diagonal matrix of eigenvalues. Thus, \(A = LDL^{-1} = LDL^T\).

We may compute the power \(A^k\) by multiplying the above \(k\) times to get \((LDL^T) (LDL^T) \dots (LDL^T) = L D^k L^T\). Note that \(D^k\) is easily computed: replace each entry \(\alpha\) of \(D\) by its power \(\alpha^k\).

Application: Eigen decomposition
Let \(\{v_1,\dots,v_n\}\) be an orthonormal basis of eigenvectors.

It can be seen that \(I = v_1v_1^T + v_2v_2^T + \dots + v_nv_n^T\).

Hence, we have \(Ax = A (v_1v_1^T + v_2v_2^T + \dots + v_nv_n^T) x = ( \lambda_1 v_1v_1^T + \lambda_2 v_2v_2^T + \dots + \lambda_n v_nv_n^T ) x\). Thus, \(A = \lambda_1 v_1v_1^T + \lambda_2 v_2v_2^T + \dots + \lambda_n v_nv_n^T\).

Assume \(\lambda_i\neq 0, \forall i\). Then we have, \(A^{-1} = \frac{1}{\lambda_1} v_1v_1^T + \frac{1}{\lambda_2} v_2v_2^T + \dots + \frac{1}{\lambda_n} v_nv_n^T\) because

\begin{equation} \nonumber \begin{split} ( \lambda_1 v_1v_1^T + \lambda_2 v_2v_2^T + \dots + \lambda_n v_nv_n^T ) ( \frac{1}{\lambda_1} v_1v_1^T + \frac{1}{\lambda_2} v_2v_2^T + \dots + \frac{1}{\lambda_n} v_nv_n^T ) &= (v_1v_1^T + v_2v_2^T + \dots + v_nv_n^T)\\ &= I. \end{split} \end{equation}

The following inequalities are useful; most of them are simple.

• For two real numbers \(\alpha, \beta\), we have \((\alpha + \beta)^2 \le 2 (\alpha ^2 + \beta ^2)\).
• For two integers \(\alpha, \beta \in \{-1,0,+1\}\), we have \((\alpha + \beta)^2 \le 2 |\alpha + \beta|\).
• Let \(\alpha_1,\beta_1\), \(\alpha_2,\beta_2\), …, \(\alpha_k,\beta_k\), be \(k\) pairs of nonnegative real numbers. Then we have

\begin{equation} \nonumber \min_{i=1,k} \frac{\alpha_i}{\beta_i} \leq\frac{\alpha_1+\alpha_2+\dots+\alpha_k}{\beta_1+\beta_2+\dots+\beta_k} \leq\max_{i=1,k} \frac{\alpha_i}{\beta_i}. \end{equation}

• Let \(x\in\mathbb{R}^{n}\) satisfy \(x \perp \mathbf{1}\) (thus, \(\sum_i x_i=0\)). Then \(\sum_{i\lt j} (x_i-x_j)^2 = n \sum_i x_i^2\).

This parts of the notes closely follows the expositions by Lau (week 1 and [[][]).

Given a graph \(G\), there are several matrices we can associate to \(G\). Before stating them let us define \(D=\text{diag}(d_{1},\ldots,d_{n})\), where \(d_{i}\) denotes the degree of vertex \(i\). We can associate the following matrices to \(G\).

• The adjacency matrix \(A\). This is an \(n\times n\) \(01\)-matrix. The \(i,j\)-entry of \(A\), \(A_{i,j}\) is \(1\) if \(ij\in E\) and \(0\) otherwise.
• The normalized adjacency matrix \(\mathcal{A}\). This matrix is defined to be \(\mathcal{A}\deff D^{-1/2}AD^{-1/2}\).
• The Laplacian matrix \(L\). Here \(L\deff D-A\).
• The normalized Laplacian matrix \(\mathcal{L}\). This \(n\times n\) matrix is defined as \(\mathcal{L}\deff D^{-1/2}LD^{-1/2}=I-\mathcal{A}\).

Recall that the trace of a matrix \(M\) is defined to be the sum of its diagonal entries, that is, \(\trace(M)=\sum_{i=1}^{n}M_{i,i}\).

Let us begin by determining the spectrum of the adjacency matrix \(A\) for a couple of very specific kinds of graphs.

• Let \(G=K_{n}\), that is, let \(G\) be the complete graph on \(n\) vertices. In this case we have that \(A=J-I\), where \(J\) is the \(n\times n\) matrix with all entries equal to 1. Observe that \(I\) has \(1\) as an eigenvalue with multiplicity \(n\). Now, since \(J\) has rank \(1\), it follows that \(0\) is an eigenvalue of \(J\) with multiplicity \(n-1\). Finally, observe that \(\onesv\) is an eigenvector of \(J\) with eigenvalue \(n\). Thus \(J\) has as eigenvalues \(0\) with multiplicity \(n-1\) and \(n\) with multiplicity \(1\). This implies that \(A\) has eigenvalues \(-1\) with multiplicity \(n-1\) and \(n-1\) with multiplicity \(1\).
• Let \(G=K_{m,n}\), the complete bipartite graph with partite sets \(X\) and \(Y\). We may assume, without loss of generality, that \(X=\{1,\ldots,m\}\) and \(Y=\{m+1,\ldots,m+n\}\). Thus \begin{equation*} A= \left[\begin{array}{rr} 0& J_{m,n} \\ J_{m,n}^{\intercal} & 0 \\ \end{array}\right], \end{equation*}

  where \(J_{m,n}\) is the \(m\times n\) all ones matrix. Note that

\(\rank(A)=0\), so \(0\) is an eigenvalue of \(A\) with multiplicity \(n-2\). Now, since the trace of \(A\) is \(0\), we have that the sum of the eigenvalues of \(A\) is \(0\). Thus the two remaining eigenvalues, call them \(\alpha_{1}\) and \(\alpha_{2}\), must satisfy \(\alpha_{1}=-\alpha_{2}\). So far we know that

\begin{equation*} \begin{split} \det(A-\alpha I) &= \alpha^{m+n-2}(\alpha-\alpha_{1})(\alpha-\alpha_{2})\\ &= \alpha^{m+n-2}(\alpha^{2}-\alpha_{1}^{2})\\ &= \alpha^{m+n}-\alpha_{1}^{2}\alpha^{m+n-2}\\ &= \alpha^{m+n}-x\alpha^{m+n-2}, \end{split} \end{equation*}

where \(x=\alpha_{1}^{2}\). By computing the determinant of \(\alpha I-A\) we can observe that for each edge of \(G\) there is exactly one \(\alpha^{m+n-2}\). Since there are precisely \(mn\) such terms this implies that the coefficient of \(\alpha^{m+n-2}\) is \(mn\), that is \(x=mn\). Therefore \(\alpha_{1}=\sqrt{mn}\) and \(\alpha_{2}=-\sqrt{mn}\). Thus \(K_{m,n}\) has eigenvalues \(\sqrt{mn}\) and \(-\sqrt{mn}\) with multiplicity \(1\), and \(0\) with multiplicity \(m+n-2\).

Recall that the spectrum of the adjacency matrix of the complete bipartite graph \(K_{m,n}\) is symmetric about \(0\). In fact, as we will see in the following result, this property charecterizes bipartite graphs.

Let us now turn our attention to the spectrum of the Laplacian matrix \(L\) of a graph \(G\). Recall that \(L\deff D-A\), where \(D\) is the diagonal matrix with \(D_{i,i}\) being the degree of vertex \(i\) and \(A\) is the adjacency matrix of \(G\).

Note that if we add the entries of a row in \(L\) we obtain \(0\), since \(d_{i}\) will cancel out with the \(d_{i}\) \(-1\)'s that are off the diagonal in that row. This implies that \(L\onesv =\zerov\), or that \(\onesv\) is an eigenvector with eigenvalue \(0\). We will now see that \(0\) is the smallest eigenvalue of \(L\). Let \(e=ij\) and let \(b_{e}\) be the \(n\times 1\) column vector with entry \(i\) being \(1\), entry \(j\) being \(-1\) and \(0\) elsewhere. It is left as an exercise to the reader to show that if \(B=[b_{e_{1}}\dots b_{e_{m}}]\) is the \(n\times m\) matrix with columns given by the \(b_{e}\) vectors defined above, then \(L=B B^{\intercal}\).

We need to introduce one more concept and prove one more lemma before we are able to show that \(0\) is the smallest eigenvalue of \(L\).

A real symmetric matrix is said to be positive semidefinite if \(x^{\intercal}Mx\geq0\) for all \(x\in \R^{n}\).

We have established that \(0\) is the smallest eigenvalue of the Laplacian matrix of a graph. In the following result we explore the relation between the eigenvalue of the Laplacian \(0\) and the number of connected components of a graph.

For a real symmetric matrix \(A\) we define the Rayleigh quotient

\begin{equation} \nonumber R(x)\mathrel{\mathop:} = \frac{x^{\intercal}Ax}{x^{\intercal}x} = \frac{\sum_{i,j}a_{i,j}x_{i}x_{j}}{\sum_{i}x_{i}^{2}}. \end{equation}

Suppose \(A\) has eigenvalues \(\alpha_{1}\geq \alpha_{2}\geq \ldots \geq \alpha_{n}\) with corresponding orthonormal eigenvectors \(v_{1},\ldots,v_{n}\).

Note that the previous result allows us to obtain \(\alpha_{k}\) provided we know \(T_{k}\). The following result, the Courant-Fischer Theorem, gives a characterization of \(\alpha_{k}\) that does not depend on knowing \(T_{k}\) and it can be used for providing bounds for the eigenvalues of a matrix.

This part of the notes closely follows the expositions by Lau (week 1, week 2) and Spielman (2009).

In this section we study Cheeger's inequality, which provides a bound on how well connected a graph is in terms of the second smallest eigenvalue of its Laplacian matrix.

We have previously seen that a graph \(G\) is disconnected if and only if its second smallest eigenvalue \(\lambda_{2}\) is \(0\). Informally, Cheeger's inequality states that the second smallest eigenvalue is close to \(0\) if and only if there is a sparse cut in \(G\). Let us now formalize this by introducing the concept of conductance.

A measure of connectedness of a graph \(G=(V,E)\) is its conductance. The conductance of a nonempty set \(S\subseteq V\) is defined to be

\begin{equation} \nonumber \frac{e(S,V-S)}{\min\{|V|,|V-S|\}}. \end{equation}

The conductance of the graph \(G\), \(\Phi\), is defined to be the minimum of the conductances over all nonempty subsets of \(V\), in symbols

\begin{equation} \nonumber \Phi = \min_{\emptyset\neq S\subseteq V}\frac{e(S,V-S)}{\min\{|V|,|V-S|\}}. \end{equation}

In this section we prove a result which is analogous to that shown in the previous section. Here the result applies to the normalized laplacian \(\mathcal{L}\). Recall that for a graph \(G\) the normalized Laplacian is defined to be \(D^{-1/2}LD^{-1/2}\). By using the normalized Laplacian instead of the Laplacian matrix we remove the dependency on the maximum degree of \(G\) for the upper bound in Cheeger's inequality.

The conductance \(\hat{\Phi}(S)\) of a set \(\emptyset \neq S\subseteq V(G)\) is defined as

\begin{equation*} \hat{\Phi}(S)=\frac{e(S,V-S)}{\min\{\deg(S),\deg(V-S)\}}. \end{equation*}

The conductance \(\hat{\Phi}(G)\) of a graph \(G\) is defined to be

\begin{equation*} \hat{\Phi}(G)=\min_{\emptyset \neq S\subseteq V}\hat{\Phi}(S)= \min_{\emptyset \neq S\subseteq V} \frac{e(S,V-S)}{\min\{\deg(S),\deg(V-S)\}}. \end{equation*}

The main result of this section is the following.

This part of the notes closely follows the expositions by Lau (week 2,) and Spielman (2009-lecture 5, 2009-lecture 7).

Let us begin by considering a simpler type of random walk. Suppose we start at vertex \(u_{0}\in V\) at time \(t=0\). We move from the current vertex \(u_{i}\) to one of its neighbours with probability \(1/d_{u_{i}}\). We denote by \(p^{t}\in\R^{V}\) the probability distribution at time \(t\), that is, \(p^{t}=(p^{t}_{1},\ldots,p^{t}_{n})\) where \(p^{t}_{i}\) denotes the probability of being at vertex \(i\) at time \(t\). For our example we are are assuming that \(p^{0}=e_{u_{0}}\) for some \(u_{0}\in V\) but in general \(p^{0}\) could be any probability distribution on \(V\), that is, \(p^{0}\in\mathbb{R}^{V}\) with \(\sum_{i\in V}p^{0}_{i}=1\).

Note that at step \(t\) the probability of being at vertex \(u\) is given by

\begin{equation} \label{eq:rw_vertex_recurrence} p_{u}^{t}=\sum_{i\in N(u)}p_{i}^{t-1}\frac{1}{d_{i}}. \end{equation}

Using \eqref{eq:rw_vertex_recurrence} we can write \(p^{t}\) in terms of the adjacency \left (

\begin{array}{ccc} v1 & v2 \ \end{array}

\right ) of \(G\) as follows.

\begin{equation} \nonumber p^{t}=(AD^{-1})p^{t-1}=\ldots=(AD^{-1})^{t}p^{0} \end{equation}

We call a distribution \(\pi\) stationary if \(\pi=(AD^{-1})\pi\).

A natural stationary distribution is the one where the probability of being at each vertex is proportional to its degree. In symbols

\begin{equation} \nonumber \pi_{u}=\frac{d_{u}}{\sum_{v\in V}d_{v}}=\frac{d_{u}}{2m}, \end{equation}

or using vector notation \(\pi\mathrel{\mathop:}=\frac{1}{2m}d\). This is indeed a stationary distribution, since

\begin{equation} \nonumber (AD^{-1})\pi=(AD^{-1})(\frac{1}{2m}d)=\frac{1}{2m}A\mathbb{1}=\frac{1}{2m}d=\pi. \end{equation}

We can extend the analysis from the example above to any bipartite graph. If we start at a single vertex, then a bipartite graph is an obstruction to reach a stationary distribution, since the probabilities in the partite sets will eventually alternate between being \(0\) and positive.

Another obstruction to reach the stationary distribution \(\pi\) is to start at a single vertex in a disconnected graph, since no vertex at other components can be reached.

In fact, it turns out to be the case that if the graph is connected and non-bipartite then we eventually reach the stationary distribution \(\pi\).

We now go back to our original example, namely the lazy random walk. Note that in this case the probability of being at a vertex \(u\) at time \(t\), \(p_{u}^{t}\) is given by

\begin{equation} \nonumber p^{t}_{u}=\frac{1}{2}p_{u}^{t-1}+\frac{1}{2}\sum_{i\in N(u)} \frac{p_{i}^{t-1}}{d_{i}}. \end{equation}

We can rewrite this as

\begin{equation} \label{eq:rw_lazy} \begin{split} p^{t}&=\frac{1}{2}p^{t-1}+\frac{1}{2}AD^{-1}p^{t-1}\\ &=\frac{1}{2}(I+AD^{-1})p^{t-1}.\\ \end{split} \end{equation}

We call the matrix \(W\mathrel{\mathop:}\frac{1}{2}(I+AD^{-1})p^{t-1}\) the (lazy random) walk matrix. Equation \eqref{eq:rw_lazy} can now be rewritten as \(p^{t}=Wp^{t-1}=\ldots=W^{t}p^{0}\).

Observe that \(W\) is not symmetric, but it is similar to a symmetric matrix, since

\begin{equation} \nonumber \begin{split} D^{-1/2}WD^{1/2}&=D^{-1/2}(\frac{1}{2}I+\frac{1}{2}AD^{-1})D^{1/2}\\ &=\frac{1}{2}I+\frac{1}{2}D^{-1/2}AD^{-1/2}\\ &=\frac{1}{2}I+\frac{1}{2}\hat{A},\\ \end{split} \end{equation}

where \(\hat{A}\) is the normalized adjacency matrix. Thus \(W=D^{1/2}(\frac{1}{2}I+\frac{1}{2}\hat{A})D^{-1/2}\).

Denote the eigenvalues of \(\hat{A}\) by \(1=\alpha_{1}\geq\ldots\geq\alpha_{n}\geq -1\) with associated orthonormal eigenvectors \(v_{1},\ldots,v_{n}\).

Then \(W\) has eigenvalues \(\frac{1}{2}(1+\alpha_{i})\) with associated eigenvectors \(D^{1/2}v_{i}\), \(i=1,\ldots,n\). Indeed, we have

\begin{equation} \nonumber \begin{split} W(D^{1/2}v_{i})&=D^{1/2}(\frac{1}{2}I+\frac{1}{2}\hat{A})v_{i}\\ &= D^{1/2}(\frac{1}{2}(1+\alpha_{i}))v_{i}\\ &= \frac{1}{2}(1+\alpha_{i}) (D^{1/2}v_{i}). \end{split} \end{equation}

Since \(D^{1/2}\) has rank \(n\) it follows that \(D^{1/2}v_{1},\ldots,D^{1/2}v_{n}\) is a basis of eigenvectors corresponding to eigenvalues \(\frac{1}{2}(1+\alpha_{1}),\ldots,\frac{1}{2}(1+\alpha_{n})\).

Let \(\lambda_{i}=\frac{1}{2}(1+\alpha_{i})\), \(i=1,\ldots,n\). Then the eigenvalues of \(W\) are \(1=\lambda_{1}\geq\lambda_{2}\geq\ldots\geq\lambda_{n}\geq0\).

Observe that \(W\pi=D^{1/2}(\frac{1}{2}I+\frac{1}{2}\hat{A})D^{-1/2}\pi=\frac{1}{2}(\pi+AD^{-1}\pi)=\pi\), so \(\pi\) is an eigenvector of \(W\) associated to eigenvalue \(\lambda_{1}=1\).

At this point we make a mild assumption about \(G\) to prove our main result. We assume that \(G\) is connected and non-bipartite. This implies \(1=\lambda_{1}>\lambda_{2}\), and since \(W\pi=\pi\) we also conclude that any eigenvector associated to \(\lambda_{1}\) must be a scalar multiple of \(\pi\).

Note: Let \(M\) be a matrix with eigenvalues \(1=\lambda_{1}>\lambda_{2}\geq\ldots\geq\lambda_{n}\geq0\) with associated orthonormal eigenvectors \(v_{1},\ldots,v_{n}\). Let \(x\in\mathbb{R}^{n}\) and write \(x=\sum_{i=1}^{n}c_{i}v_{i}\). Then

\begin{equation} \nonumber M^{t}x=M^{t}(\sum_{i=1}^{n}c_{i}v_{i})=\sum_{i=1}^{n}\lambda^{t}_{i}c_{i}v_{i}=c_{1}v_{1}+\sum_{i=2}^{n}\lambda^{t}_{i}c_{i}v_{i}. \end{equation}

So \(M^{t}x\xrightarrow{t\to \infty} c_{1}v_{1}\), since \(\lambda_{i}<1\) for \(i=2,\ldots,n\). We will use this idea to show that \(W\) admits a stationary distribution and to provide a bound on the convergence rate. It is important to note that \(W\) may not admit an orthonormal basis of eigenvectors, so a more careful analysis will be required.

In this section we analyze the convergence of the lazy random walk using conductance via the Lovász-Simonovits Theorem.

Recall that the stationary distribution \(\pi\) assigns to each vertex \(u\) a probability that is proportional to the number of incidences at \(u\), namely \(\frac{d_{u}}{2m}\). Another way of thinking about this is the following. The probability of using edge \(uv\) from time \(i\) to time \(i+1\) is \(\frac{d_{u}}{2m}\frac{1}{d_{u}}+\frac{d_{v}}{2m}\frac{1}{d_{v}}=\frac{1}{m}\). So this probability is distributed uniformly on \(E\).

We perform the convergence analysis not on \(G\) but on a digraph \(D\) obtained from \(G\). The digraph \(D\) has the same vertex set as \(G\) and it has arcs \((u,v)\) and \((v,u)\) if and only if \(uv\in E\). We also add \(d_{u}\) loops at vertex \(u\), for each \(u\in V\). In total \(D\) has \(4m\) arcs.

Denote by \(p^{t}\in \mathbb{R}^{n}\) the probability distribution at time \(t\) during the lazy random walk. Let \(q^{t}\) be the probability distribution induced by \(p^{t}\) on the set of arcs, that is \(q^{t}(u,v)=\frac{p^{t}_{u}}{2d_{u}}\).

Define \(C^{t}\) to be the cumulative distribution function of \(q^{t}\), and let \(C^{t}(k)\) be the sum of the \(k\) largest values of \(q^{t}\).

For a fixed \(t\), suppose \(V\) is labeled so that \(\frac{p_{1}^{t}}{2d_{1}}\geq \frac{p_{2}^{t}}{2d_{2}}\geq \ldots\geq \frac{p^{t}_{n}}{2d_{n}}\). Given this labeling we have that \(C^{t}(2d_{1})=p_{1}^{t}\), \(C^{t}(2d_{1}+2d_{2})=p_{1}^{t}+p_{2}^{t}\), \(\ldots\), \(C^{t}(2\sum_{i\in [k]}d_{i})=\sum_{i\in[k]}p_{i}^{t}\). We say \(x_{k}\) is a breakpoint if \(x_{k}=\sum_{i\in[k]}2d_{i}\). Note that \(C^{t}\) behaves linearly between \(x_{i}\) and \(x_{i+1}\), so \(C^{t}\) is a piecewise linear function. Since \(C^{t}\) depends on \(t\) (via \(p^{t}\)), we relabel \(V\) for each time so that \(C^{t}\) preserves the properties from above.

We begin by showing a property of \(C^{t}\) which is closely related to concavity.

Note that taking \(r=0\) in the previous lemma implies that \(C^{t}\) is concave, that is,

\begin{equation} \nonumber C^{t}(x)\geq \frac{C^{t}(x-s)+C^{t}(x+s)}{2}, \end{equation}

for all \([x-s,x+s]\subseteq[0,4m]\).

Observe that the closer \(p^{t}\) is to the stationary distribution \(\pi\), the closer the graph of \(C^{t}(x)\) is to being a line, since the probabilities are closer to being distributed equally among arcs of \(D\). Next we show the Lovász-Simonovits theorem which we will use to show that the rate of convergence of the lazy random walk is \(O(\sqrt{m})\), provided that the conductance \(\Phi(G)\) is constant.

We now use the previous theorem to derive the convergence rate of the lazy random walk in terms of the conductance.

The Lovasz Simonovits theorem is a result that is interesting by itself. In this section we provide an alternate proof of it.

We use the following notation in this section.

• \(G=(V,E)\) denotes a connected graph.
• \(W\) is the walk matrix of the lazy random walk, explicitly, \begin{equation} \nonumber W=\frac{1}{2}(I+AD^{-1}). \end{equation}

  Note that \(W_{i,i}=1/2\) and that the column sum is \(1\).

  It should be noted that the Lovasz Simonovits theorem is more

• \(p^{0}\in \mathbb{R}^{V}\) is a probability distribution on \(V\). The vector \(p^{t}\) denotes the probability distribution after \(t\) steps of the lazy random walk, recall that \begin{equation} \nonumber p^{t}=Wp^{t-1} \end{equation}

  for \(t\geq 1\).

• We denote the stationary probability distribution by \(\pi=(\pi_{1},\ldots,\pi_{n})\). Recall that this probability distribution satisfies \(W\pi=\pi\).
  • Observe that since \(W\pi=\pi\), we have that \(\sum_{j\in V}w_{i,j}\pi_{j}=\pi_{i}\). Also, since the sum of the entries of a column of \(W\) is \(1\), then \(\sum_{j\in V} w_{j,i} \pi_{i} = \pi_{i}\). Therefore \(\sum_{j\in V}w_{i,j}\pi_{j} = \sum_{j\in V} w_{j,i} \pi_{i}\).
• \(\gamma\in \mathbb{R}^{n}\) denotes the sum of the first \(k\) rows of \(W\), namely, \(\gamma = (\underbrace{1,\ldots,1}_{k\text{ ones}},0,\ldots,0)W\). Note that \(\gamma_{i}\geq 1/2\) for \(i\leq k\), and \(\gamma_{i}\leq 1/2\) for \(i\geq k\) by the structure of \(W\).
• \(F=W\Pi\), where \(\Pi=\text{diag}(\pi_{1},\ldots,\pi_{n})\). Note that \(F\) is symmetric, since for \(ij\in E\) we have \begin{equation} \nonumber f_{i,j}=W_{i,j}\pi_{j}=\frac{1}{2d_{j}}\frac{d_{j}}{2m}=\frac{1}{4m} \end{equation}

  and

  \begin{equation} \nonumber f_{j,i}=W_{j,i}\pi_{i}=\frac{1}{2d_{i}}\frac{d_{i}}{2m}=\frac{1}{4m}. \end{equation}

  If \(ij\not\in E\) then we have \(f_{i,j}=0=f_{j,i}\).

  In fact \(F\) is symmetric since \(F=W\Pi=\frac{1}{2}(I+AD^{-1})\Pi=\frac{1}{2}(\Pi + A D^{-1}\Pi) = \frac{1}{2}(\Pi + \frac{1}{2m}A)\).

  By the symmetry of \(F\) it follows that for any \(S\subseteq V\) we have

  \begin{equation} \nonumber \sum_{j\in V-S}(\sum_{j\in S}f_{i,j})=\sum_{i\in S}(\sum_{h\in V-S}f_{h,i}). \end{equation}
• Here we define the function \(d^{t}:[0,1]\rightarrow \mathbb{R}\) which is part of the statement of the Lovasz Simonovits theorem. We proceed by defining two functions, \(d_{1}^{t}\) and \(d_{2}^{t}\), and showing that they are equal, we then call this function \(d^{t}\).

  Let us begin by defining \(d_{1}^{t}:[0,1]\rightarrow \mathbb{R}\). This function is defined in terms of the knapsack linear program as follows.

  \begin{equation} \nonumber \begin{array}{r@{}l@{}l} d_{1}^{t}(x)= &{} \text{max} \quad &{}\sum_{i\in V}(p_{i}^{t}-\pi_{i})w_{i} \\ &{}\text{s.t.}\quad &{}\sum_{i\in V}\pi_{i}w_{i} =x \\ &{} &{} 0\leq w_{i}\leq 1, \quad i\in V. \end{array} \end{equation}

  Now, let us make an assumption for the definition of \(d_{2}^{t}\). Let us assume that the elements of \(V\) are labelled so that

  \begin{equation} \nonumber \frac{p_{1}^{t}}{\pi_{1}} \geq \frac{p_{2}^{t}}{\pi_{2}} \geq \dots \geq \frac{p_{n}^{t}}{\pi_{n}}, \end{equation}

  and, assuming the ordering above, let \(\pi[k] = \sum_{i\in[k]}\pi_{i}\).

  We define \(d_{1}^{t}:[0,1]\rightarrow \mathbb{R}\) as follows.

  \begin{equation} \nonumber d_{2}^{t}(x)=(p_{1}-\pi_{1})+\dots+(p_{k}-\pi_{k})+\frac{x-\pi[k]}{\pi_{k+1}}(p_{k+1}-\pi_{k+1}), \end{equation}

  where \(k\) is such that \(\pi[k]\leq x \leq \pi[k+1]\).

  We claim that \(d_{1}^{t}=d_{2}^{t}\). This follows since the optimal solution to the knapsack linear program is given by ordering the items by decreasing \(\frac{\text{profit}}{\text{size}}\) ratios and then picking as many items as to fill the knapsack.

  Note that we can think of \(d^{t}\) as the function that describes how the optimal value of the knapsack linear program changes as we increase the size of the knapsack.

• Finally, let us recall the notion of conductance of a set. We define the conductance of \(S\) as \begin{equation} \nonumber \phi_{S} = \frac{ \sum_{j\in S}( \sum_{i\in V-S} w_{i,j} ) \pi_{j} }{ \min\{ \pi(S), \pi(V-S) \}} = \frac{ \sum_{j\in S}( \sum_{i\in V-S} f_{i,j} ) }{\min\{ \pi(S), \pi(V-S) \}}. \end{equation}

  The conductance of a graph \(G\) being defined as \(\Phi=\min_{S\subseteq V}\phi_{S}\).

We are now ready to state the Lovasz Simonovits theorem.

This part of the notes closely follows the expositions by Lau (week 6) and Spielman (2009-lecture 8).

The effective resistance between \(u\) and \(v\), \(\effResist_{u,v}\), is defined to be \(\phi_{u}-\phi_{v}\), where \(\phi\in\mathbb{R}^{V}\) is the resulting vector of potentials when one unit of current is supplied to \(u\) and one unit of current is removed from \(v\), that is, \(\extCur_{u}=1\) and \(\extCur_{v}=-1\). Intuitively we may thing of \(\effResist_{u,v}\) as the resistance between \(u\) and \(v\) given by the rest of electrical network. Algebraically we have \(L_{G}\phi=\extCur\). Now, since in this case \(\extCur=\chi_{u}-\chi_{v}\), then \(\extCur\perp\mathbb{1}\). Therefore \(\phi=L_{G}^{+ }\extCur\). As a consequence we obtain that \(\effResist_{u,v}=(\chi_{u}-\chi_{v})^{\intercal}L_{G}^{+}(\chi_{u}-\chi_{v})\).

Joule's first law asserts that the energy dissipated per unit of time at a resistor \(ab\) is given by \(f_{a,b}^{2}r_{ab}\). We define the energy dissipated in the network with currents \(f\in \mathbb{R}^E\) as the sum of all the energy dissipated at the resistors of the network, that is,

\begin{equation} \begin{split} \mathcal{E}(f)&=f^{\intercal}R f \\ &= \sum_{uv\in E}f_{u,v}^{2}r_{uv}\\ &= \sum_{uv\in E}f_{u,v}(\phi_{u}-\phi_{v})\\ &= \sum_{uv\in E}w_{ab}(\phi_{u}-\phi_{v})^{2}\\ &= \phi^{\intercal}L_{G}\phi. \end{split} \end{equation}

Note that when one unit of current is supplied to \(u\) and one unit is removed from \(v\) then we have \(\effResist_{u,v}=\mathcal{E}(f)\).

Let \(g\in\mathbb{R}^{E}\) be a current assignment on \(E\) that satisfies Kirchoff's flow conservation law The next theorem, known as Thompson's Principle, shows that among all such current assignments the one minimizing the energy dissipated in the network is precisely \(f=\chi_{u}-\chi_{v}\).

It is sometimes beneficial to think of effective resistance as a measure of distance between two nodes. We can think of distance as a function \(d\) on pairs of vertices that satisfies the following properties:

1. \(d(a,a) = 0\)
2. \(d(a,b) \geq 0\)
3. \(d(a,b) = d(b,a)\)
4. \(d(a,c) \leq d(a,b) + d(b,c)\)

Our goal is to show that \(R_{eff}\) satisfies these properties, the interesting one being item 4 (the triangle inequality).

We first start with Rayleigh's monotonicity principle, which states that the effective resistance cannot decrease if we increase the resistance of some edge.

We can gain some intuition about this principle by considering paths between vertices \(s\) and \(t\). If there is a short path between them, then the effetive resistance between them is ``small.'' If there are many paths between them, then the effective resistance is even smaller. More precisely, we can give the bound as stated in the following claim.

Now, we show that effictive resistance satisifies the triangle inequality.

This part of the notes closely follows the expositions by Lau (week 12) and Spielman (2010-lecture 12,2010-lecture 13).

The maximum cut problem can be formulated as an optimization problem with the objective function

\begin{equation} \nonumber \max_{S\subseteq{V}} \frac{e(S,\overline{S})}{|E|} \end{equation}

which lies in \([0,1]\). The following are the optimal values for some simple graphs.

Graphs	Maximum Cut
Bipartite Graphs	\(1\)
\(C_5\)	\(4/5\)
\(K_{2n}\)	\(n/(2n-1)\approx 1/2\)

It is an exercise to show that the greedy algorithm always finds a cut of objective value at least \(1/2\). It examines the nodes in order \(1,2,\cdots,n\), and places node \(i\) in the left set \(L\) or the right set \(R\) such that at least half of the edges from \(i\) to \(\{1,2,\cdots, i-1\}\) are in the cut.

We compare the two algorithms based on linear programming and semidefinite programming in the following table.

Based on	Approximation factor	Best possible
LP	0.5	For LP based hierarchies
SDP (GW '95)	0.878	Assuming Unique Games Conjecture

The main idea in Trevisan's work is to relate the cut to the last eigenvalue of the sum Laplacian. Let \(d_{1},\ldots,d_{n}\) denote the degrees of the nodes \(1,\ldots,n\) and let \(D^{1/2}\) denote the diagonal matrix with \(D^{1/2}_{i,i}=1/\sqrt{d_{i}}\). Recall that the normalized adjacency matrix of a graph \(G\) is defined as

\begin{equation} \nonumber \hat{A}=D^{-1/2}AD^{-1/2} \end{equation}

whose eigenvalues are

\begin{equation} \nonumber 1=\alpha_1\ge \alpha_2\ge \cdots \ge \alpha_n\ge -1. \end{equation}

Let \(L^s\) denote the sum Laplacian

\begin{equation} \nonumber L^s=I+\hat{A} \end{equation}

and

\begin{equation} \nonumber 2=\lambda_1\ge \lambda _2\ge \cdots \ge \lambda_n\ge 0 \end{equation}

its eigenvalues. Let us define \(L_{e}^{s}\) for \(e=ij\) as the \(n\times n\) matrix having its \(i,i\) entry equal to \(1/d_{i}\), its \(j,j\) entry equal to \(1/d_{j}\), its \(i,j\) and \(j,i\) entries equal to \(1/\sqrt{d_{i}d_{j}}\), and \(0\) elsewhere. Note that \(L^s\) is positive semidefinite, as it is the sum of \(L_e^s\) over all edges \(e=ij\in E\), where

\begin{equation} \nonumber x^TL_e^{s}x = \frac{x_{i}^{2}}{d_{i}} + \frac{x_{j}^{2}}{d_{j}} + 2 \frac{x_{i}x_{j}}{\sqrt{d_{i}d_{j}}} = \left(\frac{x_i}{\sqrt{d_i}}+\frac{x_j}{\sqrt{d_j}}\right)^2. \end{equation}

Consider a partition of the vertex set \(V\) into the left set \(L\), the right set \(R\) and the rest \(\overline{S}\). Define

\begin{equation} \nonumber \beta(L,R,\overline{S}):=\frac{\sum_{ij\in E} |y_i+y_j|}{\sum_{i} d_i |y_i|} \end{equation}

where

\begin{equation} \nonumber y_i=\begin{cases} -1, \quad i\in L\\ 1, \quad i\in R\\ 0, \quad i\in \overline{S}. \end{cases} \end{equation}

In Figure 5 we illustrate the motivation behind the definition of \(\beta\). We denote the number of edges having exactly one endpoint in \(\overline{S}\) to be \(\Cross\), the number of edges with exactly one endpoint in \(L\) and one endpoint in \(R\) is denoted by \(\Cut\), the number of edges having both endpoints in \(L\) or both endpoints in \(R\) is denoted by \(\Uncut\). Finally, we denote the number of edges with both endpoints in \(\overline{S}\) as \(\Deferred\). Observe how the value of \(|y_{i}+y_{j}|\) changes depending on where the edge \(ij\) has its endpoints. See Figure 5(b). We can now see that

\begin{equation} \nonumber \beta(L,R,\overline{S})=\frac{2\cdot\Uncut+\Cross}{2\cdot\Cut+2\cdot\Uncut+\Cross}. \end{equation}

Let \(\beta(G)\) denote the minimum of \(\beta(L,R,\overline{S})\) over all these partitions:

\begin{equation} \beta(G):= \nonumber \min_{y\in \{-1,0,1\}^n} \frac{\sum_{ij\in E} |y_i+y_j|}{\sum_{i} d_i |y_i|}. \end{equation}

Then the last eigenvalue \(\lambda_n\) provides a bound for \(\beta(G)\).

Informally speaking, \(\beta(G)\) serves as a `bridge' between \(\lambda_{n}\) and the value of \(\text{maxcut}(G)\), which is \(\max_{S\subseteq V}\frac{e(S,\overline{S})}{|E|}\). See the following proposition, which shows that if \(\text{maxcut(G)}\geq 1-\varepsilon\) then \(\beta(G)\leq \varepsilon\) and this implies \(\lambda_{n}\leq 2\varepsilon\). Before we give the proof, let us see how this set up give rise to the maximum cut algorithm.

The algorithm first constructs a partition \((L,R,\overline{S})\) of the vertex set \(V\) with

\begin{equation} \nonumber \beta(L,R,\overline{S})\le \sqrt{2\lambda_n} \end{equation}

and then recursively solves the maximum cut problem on \(G-S\), where \(S=L\cup R\). We refer to the edges between \(L\) and \(R\) as cut edges, the ones within \(L\) or within \(R\) as uncut edges, the ones between \(S\) and \(\overline{S}\) as cross edges, and the ones within \(\overline{S}\) as deferred edges.

The algorithm stops when there is no cross edge or deferred edge.

Throughout, the partition \((L,R,\overline{S})\) satisfies

\begin{align*} \nonumber 1-\beta(L,R,\overline{S})&=1-\frac{2\cdot \Uncut + \Cross}{2\cdot \Uncut + 2\cdot\Cut+ \Cross}\\ &=\frac{\Cut}{\Uncut +\Cut+0.5\cdot \Cross}\\ &\leq \frac{\Cut +0.5\cdot \Cross}{\Uncut +\Cut+0.5\cdot \Cross + 0.5\cdot \Cross}\\ &\le \frac{\Cut}{|E-E(\overline{S})|}+\frac{0.5\cdot \Cross}{|E-E(\overline{S})|} \end{align*}

By the first half of Theorem LINK MISSING, this immediately implies the following

In other words, if \(\beta(G)>\epsilon\), then the maximum cut is of value less that \(1-\epsilon\). As a remark, \(\lambda_n\) being small does not imply that the maximum cut is large, since for any graph with a bipartite component, \(\lambda_n=0\).

By the second half of Theorem LINK TO THM MISSING,

\begin{equation} \nonumber \frac{\Cut}{|E|}+\frac{0.5\cdot \Cross}{|E|}\ge 1-\sqrt{2\lambda_n}. \end{equation}

Let \(\theta\) be a parameter (later, we will fix its value to 0.1101). If \(1-\sqrt{2\lambda_n}\) is too small, say \(\lambda_n\ge \theta\), then \(\beta\ge \theta/2\), whence the optimum value is at most \(1-\theta/2\). In this case, we can choose the greedy algorithm to cut at least half edges, and this gives an approximation guarantee of

\begin{equation} \nonumber \frac{0.5}{1-0.5\cdot \theta}=\frac{1}{2-\theta} \end{equation}

If \(\lambda_n<\theta\), then the spectral algorithm outputs a cut with value

\begin{equation} \nonumber \mathrm{Alg}(G)=\Cut+0.5\cdot \Cross+\mathrm{Alg}(G-S) \end{equation}

Note that the optimum value satisfies

\begin{equation} \nonumber \mathrm{Opt}(G)\le \Uncut +\Cut+\Cross+\mathrm{Opt}(G-S). \end{equation}

Suppose by induction that

\begin{equation} \nonumber \mathrm{Alg}(G-S)\ge \alpha\, \mathrm{Opt}(G-S). \end{equation}

Then the approximation guarantee \(\gamma\) is

\begin{align*} \gamma & \ge \frac{\Cut+0.5\cdot \Cross+\alpha\,\mathrm{Opt}(G-S)}{\Uncut + \Cut+\Cross+\mathrm{Opt}(G-S)}\\ &\ge \min\left\{\frac{\Cut+0.5\cdot\Cross}{\Uncut + \Cut+\Cross},\alpha\right\}\\ &\ge \min \left\{1-\sqrt{2\theta},\alpha\right\}\\ &\ge \min\left\{1-\sqrt{2\theta},\frac{1}{2-\theta}\right\} \end{align*}

If we set \(\theta=0.1107\), then the approximation guarantee is at least 0.52.

We now prove the two inequalities in Theorem LINK TO THM. We start with the easy direction.

This part of the notes closely follows the exposition by Lau (week 3).

Spectral clustering is the problem of finding clusters using spectral algorithms. Clustering is a very useful technique widely used in scientific research areas involving empirical data. As it is a natural question to ask, given a big set of data, if we can put the data into groups such that data in the same group has similar behavior. Spectral clustering often outperforms traditional clustering algorithms, as it does not make strong assumptions on the form of the clusters. In addition, it is easy to implement, and can be efficiently solved by standard linear algebra software.

In this chapter, we will focus on studying spectral clustering algorithms, and this chapter is mainly based on the survey paper by Ulrike von Luxburg (2007). We will first get familiar with the background materials related to spectral clustering, and then see two basic spectral algorithms. Afterwards, we will try to get some intuition on these spectral algorithms: why the algorithms are designed as they are. We try to rigorously justify the algorithms from graph cut point of view, perturbation theory point of view. Another theoretical justification will be given for a slightly modified spectral algorithm. Lastly, some practical details and issues will be discussed.

Here are some notations that will be used later for similarity graph \(G=(V,E)\), \(V=\{v_1,\ldots , v_n\}\):

• non-negative weight of \(v_iv_j\) is defined as \(w_{ij}\).
• \(W:=(w_{ij})_{i,j=1,.,n}\) is the weighted adjacency matrix of the graph \(G\).
• \(d_i:=\sum^n_{j=1}w_{ij}\) denotes the degree of \(v_i\).
• \(D\) denotes the diagonal degree matrix of \(G\), with \(D_{ii}=d_i\) for \(i\in \{1,\ldots ,n\}\).
• \(\bar{A}\) denotes the complement of vertex set \(A\).
• \(W(A,B):= \sum_{i \in A,j \in B} w_{ij}\) is the sum of the weights of all edges going between set \(A\) and \(B\).
• \(vol(A):=\sum_{i \in A} d_i\) is a measure of the size of set \(A\).
• \(|A|\):= the cardinality of \(A\) is another measure of the size of set \(A\).
• \(\vec{1}_{A_i}\) denotes the indicator vector of set \(A_i\).

There are other ways to construct similarity graph of a data set in addition to the one described before:

• Fully connected graph: this similarity graph is the one described above, we create an edge between two points if their similarity \(s_{ij}\) is positive. Set \(w_{ij}=s_{ij}\) if \(v_iv_j \in E\).
• \(\epsilon\)-neighborhood graph: connect two points if their pairwise distance is smaller than \(\epsilon\). This graph is usually treated as an unweighted graph, since if \(v_iv_j \in E\), the distance between \(x_i\) and \(x_j\) is roughly of the same scale as \(\epsilon\).
• \(k\)-nearest neighbor graph: for each vertex \(v_i\), connect it to all of its \(k\)-nearest neighbors. Since this relation is not symmetric, we obtain a directed graph. The \(k\)-nearest neighbor graph is obtained by simply ignoring the directions on the edges, and set \(w_{ij}=s_{ij}\) if \(v_iv_j \in E\).
• Mutual \(k\)-nearest neighbor graph: is similar to \(k\)-nearest neighbor graph. The only difference is that after the directed graph is created, only keep edges that are bidirected, and ignore the directions. An undirected graph is obtained in this way. Set \(w_{ij}=s_{ij}\) if \(v_iv_j \in E\).

Before getting into the spectral clustering algorithms, let's briefly review graph Laplacians and their basic properties:

I. Unnormalized Laplacian

The unnormalized Laplacian \(L\) is defined as \(L=D-W\). Some basic properties are as follows:

• \(f^TLf=\frac{1}{2}\sum^n_{i,j=1}w_{ij}(f_i-f_j)^2\) holds for any \(f \in \mathbb{R}^n\).
• \(L\) has \(n\) non-negative real eigenvalues: \(0=\lambda_1 \leq \lambda_2 \leq\ldots \leq \lambda_n\).
• The smallest eigenvalue of \(L\) is \(0\), and the corresponding eigenvector is \(\vec{1}\).
• The number of connected components \(A_1,\ldots ,A_k\) in graph \(G\) equals to the number of eigenvalues of \(L\) equal to \(0\), and the eigenspace of eigenvalue \(0\) is spanned by vectors \(\vec{1}_{A_1},\ldots ,\vec{1}_{A_k}\).

II. Normalized Laplacian

For our purpose, we define normalized Laplacian slightly differently here: \(L_{rw}=D^{-1}L=I-D^{-1}W\). It is denoted as \(L_{rw}\), since it is related to the random walk matrix.

It is straightforward to verify the following properties also hold for \(L_{rw}\):

• \(L_{rw}u=\lambda u\) if and only if \(\lambda\) and \(u\) solve the generalized eigenproblem \(Lu=\lambda Du\).
• \(L_{rw}\) has \(n\) non-negative real eigenvalues: \(0=\lambda_1 \leq \lambda_2 \leq\ldots \leq \lambda_n\).
• The smallest eigenvalue of \(L_{rw}\) is \(0\), and the corresponding eigenvector is \(\vec{1}\).
• The number of connected components \(A_1,\ldots ,A_k\) in graph \(G\) equals to the number of eigenvalues of \(L_{rw}\) equal to \(0\), and the eigenspace of eigenvalue \(0\) is spanned by vectors \(\vec{1}_{A_1},\ldots ,\vec{1}_{A_k}\).

Now, we are ready to see two basic spectral clustering algorithms. The first algorithm uses unnormalized Laplacian, and the second one uses normalized Laplacian. The two algorithms are very similar to each other, and the only difference is they use different graph Laplacians. However, using different graph Laplacians may lend to different outcomes of clustering. We will discuss which algorithm is more preferable at the end of Section Six.

The previous section gives some intuitive justification for the spectral algorithms. Now, let's see some rigorous justification. The first rigorous justification is from graph cut point of view.

As discussed before, with the similarity graph constructed, we turned the clustering problem into a graph partition problem. Instead of finding a clustering so that data points in the same cluster are similar to each other and points in different clusters are dissimilar to each other, we want to find a partition of the graph so that edges within a group have big weights, and edges between different groups have small weights. We will see spectral clustering algorithms are approximation algorithms to graph partition problems.

Let's first define the graph partition problem mathematically. Since the goal is to find a partition \(A_1,\ldots ,A_k\) of the graph so that there are very few edges going between different groups, we can choose the objective function to be total weights of all cut edges: cut(\(A_1,\ldots ,A_k\)):= \(\frac{1}{2}\sum_{i=1}^kW(A_i,\bar{A_i})\). The scalar of \(\frac{1}{2}\) is due to the fact every cut edge is counted twice when summing over all group cuts.

Thus, the graph partition problem is defined as: \(\underset{A_1,\ldots ,A_k}{\arg\min}\): Cut\((A_1,\ldots ,A_k)\).

Notice when \(k\) equals to \(2\), this problem is exactly the minimum cut problem. There exist efficient algorithms for this problem. However, in practice running the minimum cut algorithm in many cases only ends up separating a single vertex from the rest of the graph. This is not what we want since we want the clusters to be reasonably large sets of points.

To fix this, we require the partition to be not only sparse but balanced as well. This can be achieved by explicitly incorporating these requirements into the objective function. Instead of using total weights of cut edges as the objective function, consider RatioCut and Ncut functions as follows:

RatioCut(\(A_1,\ldots ,A_k\)):= \(\sum_{i=1}^k\frac{W(A_i,\bar{A_i})}{|A_i|}\) = \(\sum_{i=1}^k\frac{cut(A_i,\bar{A_i})}{|A_i|}\).

Ncut(\(A_1,\ldots ,A_k\)):= \(\sum_{i=1}^k\frac{W(A_i,\bar{A_i})}{vol(A_i)}\) = \(\sum_{i=1}^k\frac{cut(A_i,\bar{A_i})}{vol(A_i)}\).

The difference between the Cut function and RatioCut, Ncut functions is that in RatioCut and Ncut, each term in the sum is divided by the size of the group. The size of the group is measured by the group cardinality in RatioCut, while in Ncut, the size of the group is measured by the group volume. In this way, the requirement of having a balanced partition is incorporated into the problem as well.

Thus, we consider these two graph partition problems instead:

RatioCut graph partition problem: \(\underset{A_1,\ldots ,A_k}{\arg\min}\): RatioCut\((A_1,\ldots ,A_k)\).

Ncut graph partition problem: \(\underset{A_1,\ldots ,A_k}{\arg\min}\): Ncut\((A_1,\ldots ,A_k)\).

However, with these two objective functions the graph partition problems become NP-hard. The best we can hope for is to solve these problems approximately. Indeed, we will prove later that the unnormalized spectral clustering algorithm solves the relaxed RatioCut problem and the normalized spectral clustering algorithm solves the relaxed Ncut problem. This provides a formal justification for the spectral algorithms.

In this section, we rigorously justify the spectral algorithms from perturbation theory point of view. Perturbation theory is the study of how eigenvalues and eigenvectors change when a small perturbation is introduced to the matrix.

Intuitively, the justification by this approach is the following:

In the ideal situation, the similarity graph constructed represents the clustering structure of the data exactly. In this case, each connected component of the similarity graph precisely corresponds to one cluster of the original data set. With the ideal similarity graph, suppose the graph has \(k\) components, the spectral algorithms will return \(k\) clusters corresponding to the \(k\) connected components (by similar arguments as in the toy example). Clearly, in this case the spectral algorithms produce the correct clustering.

However, in real life we may not always be able to construct the ideal similarity graph. The graph constructed in real life is in general some perturbed version of the ideal graph. As a result, the Laplacians of this similarity graph are perturbed versions of the ideal Laplacians. By perturbation theory, if the perturbation is not too big and the eigengap between \(\lambda_k\) and \(\lambda_{k+1}\) of the ideal Laplacian is relatively large, then the first \(k\) eigenvectors of the perturbed Laplacian is "close to" the first \(k\) eigenvectors of the ideal one. Thus, in real life the matrix \(U\) constructed in the algorithms is "close to" the \(U\) in the ideal case. Thus, although in this case we may not have all points in a cluster being represented by the same vector, their vector representations are still relatively close to each other. Hence, after running the \(k\)-means step, the correct clustering can still be identified.

Another justification for spectral clustering is provided in this section, and it is based on the paper by Dey, Rossi and Sidiropoulos (2014). We will consider a slightly modified spectral clustering algorithm as follows:

\(R = (1-2k\sqrt{\delta})/(8k\sqrt{n})\)

\(\delta =1/n+ (c' \triangle ^3 k^3log^3n)/ \tau\)

\(\triangle =\) maximum degree of graph \(G\)

\(c' > 0\) is a universal constant

\(\tau > c'\triangle ^2 k^5log^3n\), and \(\lambda_{k+1}^3(L_{rw}) > \tau \lambda_k(L_{rw})\)

The only difference between this spectral clustering algorithm and the ones we have seen in Section Two is that instead of using the \(k\)-means algorithm to obtain a clustering in the vector space, an approximation algorithm (by Charikar et al. 2001) for the robust \(k\)-center problem is used here.

Spectral clustering algorithms are very practical algorithms. In this section, we will discuss some practical details and issues related to the algorithms.

Spectral clustering algorithms have lots of applications in real life, including machine learning. However, we should apply the algorithms with care, as the algorithms are sensitive to the choice of similarity graphs, and can be unstable under different choices of parameters of the graph. Thus, the algorithms should not be taken as black boxes.

Spectral clustering is a very powerful tool, as it does not make strong assumptions on the form of the clusters. The \(k\)-means algorithm on the other hand, assumes the clusters to be of convex form, and thus may not preserve global structure of the data set. Another big advantage of spectral clustering is that it can be implemented efficiently for large data sets if the similarity graph constructed is sparse.

To further explore this subject, please refer to a list of papers in von Luxburg (2007).

A \(d\)-regular graph is called Ramanujan if its eigenvalues are either \(\pm d\) or bounded in absolute value by \(2\sqrt{d-1}\). Ramanujan graphs have been widely used in theoretical computer science; for example, they are spectral expanders on which lazy random walks mix quickly. In (cite?), Lubotzky asked whether there exists an infinite family of Ramanujan graphs of every degree greater than two. In his earlier work with Phillips and Sarnak (cite?), and in the work by Margulis (cite?), the cases for \(d=p+1\) where \(p\) is an odd prime were solved. Later, Chiu (cite?) filled the gap for \(p=2\). Following these, Morgenstern (cite?) generalized the statement to graphs of valency \(d=q+1\) where \(q\) is a prime power. All these constructions are sproadic.

The breakthrough was made in 2013 by Marcus, Spielman and Srivastava (cite?), who proved the existence of regular Ramanujan graphs of all degrees via a probabilistic approach. They showed that the characteristic polynomials of signed adjacency matrices of a graph form an interlacing family, whence this set contains a polynomial whose roots are bounded by the largest root of the expectation over the set. By the properties of the expected characterstic polynomial, which is the well-studied matching polynomial of the graph, they bounded its largest root and thus established the existence of infinite families of regular bipartite Ramanujan graphs of all degrees. With the same method, they constructed infinite families of biregular Ramanujan graphs of all degrees. This is the first existence result on infinite families of irregular Ramanujan graphs.

In this report, we provide a detailed summary of the proof given by Marcus et al (cite?). Since most of their ideas are not restricted to regular graphs, we will stick to the general setting and work on Ramanujan graphs as defined in their paper.

Given a graph \(G\) with adjacency matrix \(A\), the spectral radius of \(G\) is

\begin{equation} \nonumber \rho(G):=\sup_{||x||_2=1} ||Ax||_2 \end{equation}

where

\begin{equation} \nonumber \Vert x \Vert_2=\sum_{i=1}^{\infty}x_i^2 \end{equation}

whenever the series converges. If \(G\) is finite, the spectral radius is just the largest eigenvalue of \(A\). The graph \(G\) is bipartite if and only if its smallest eigenvalue is \(-\rho(G)\). By trivial eigenvalues, we mean the eigenvalue \(\rho(G)\), and \(-\rho(G)\) when \(G\) is bipartite.

A Ramanujan graph is a graph whose non-trivial eigenvalues have small absolute values. To give an exact definition such that an infinite family of Ramanujan graphs exists, we need to know how small the non-trivial eigenvalues will stay when the graph becomes infinitely large. The answer is related to its universal cover.

The universal cover of a graph \(G=(V,E)\) is an infinite tree \(T\) with all the non-backtracking walks starting at a fixed vertex \(u\) as its vertices. Here a walk is non-backtracking if it does not contain the subsequence \(vwv\) for any \(v,w\in V\). Two vertices in \(T\) are adjacent if one is a maximal subwalk of the other, that is, if one can be obtained by appending a vertex to the other. Different graphs may have the same universal cover. For example, the universal cover of every \(d\)-regular graph is the infinite \(d\)-regular tree. We inllustrate the universal cover of the complete graph \(K_4\) on vertices \(\{1,2,3,4\}\) in Figure 8. Every vertex of \(T\) is a non-backtracking walk starting at vertex 1, denoted by the last digit in the walk sequence, as one can read off each sequence from a path starting at the root.

In (cite?), Greenberg proved that for every \(\varepsilon>0\) and every infinite family of graphs that have the same universal cover \(T\), every sufficiently large graph in the family has a non-trivial eigenvalue that is at least \(\rho(T)-\varepsilon\). Thus, Marcus et al (cite?) defined an arbitrary graph to be Ramanujan if its non-trivial eigenvalues are bounded in absolute value by the spectral radius of its universal cover. This is consistent with the original definition of a \(d\)-regular Ramanujan graph, as the spectral radius of an infinite \(d\)-regular tree is \(2\sqrt{d-1}\) (cite?).

Marcus et al (cite?) realized the construction suggested by Bilu and Linial (cite?) through a sequence of 2-lifts of a base Ramanujan graph. A 2-lift of \(G=(V,E)\) is a graph with two vertices \(\{u_0,u_1\}\), called a fibre, for each vertex \(u\) in \(G\). There is a matching between two fibres \(\{u_0,u_1\}\) and \(\{v_0,v_1\}\) in the 2-lift if and only if there is an edge between \(u\) and \(v\) in \(G\). Thus, for each edge \(uv\) of \(G\), a 2-lift contains either one of the following matchings

Suppose there are \(m\) edges in \(G\). The signing with respect to a 2-lift is the map \(s:E\to\{1,-1\}^m\) defined by

\begin{equation} \nonumber s(uv)=\begin{cases} 1, \, \text{ if (a) appears,}\\ -1, \, \text{ if (b) appears.} \end{cases} \end{equation}

If we replace the non-zero \(uv\)-entry of the adjacency matrix \(A\) by \(s(uv)\), the resulting matrix is called the signed adjacency matrix, denoted \(A_s\). In the following example, (b) is a 2-lift of the complete bipartite graph \(K_{13}\), and the corresponding signed adjacency matrix is

\begin{equation*} A_S=\begin{pmatrix}0 & \textcolor{blue}{-1} & 1 & \textcolor{blue}{-1}\\ \textcolor{blue}{-1} & 0 & 0 & 0\\ 1 & 0 & 0 & 0\\ \textcolor{blue}{-1} & 0 & 0 & 0\end{pmatrix}. \end{equation*}

With the signed adjacency matrix, Bilu and Linial (cite?) characterized the eigenvalues of a 2-lift.

We will refer to the eigenvalues of \(A_s\) as the new eigenvalues of the 2-lift. For a Ramanujan graph \(G\) with universal cover \(T\), if there is a 2-lift of \(G\) whose universal cover has the same spectral radius as \(T\), and whose new eigenvalues are no larger in absolute value than \(\rho(T)\), then the 2-lift is also Ramanujan. Marcus et al (cite?) showed that a weaker version of the second condition is achievable:

This works as well when \(G\) is bipartite, since its eigenvalues are symemtric about zero. Further, if \(G\) is \((c,d)\)-biregular, that is, all the vertices in one colour class have degree \(c\) and all the other vertices have degree \(d\), then the first property is also satisfied, since the universal cover of every \((c,d)\)-biregular graph is the infinite \((c,d)\)-biregular tree with spectral radius \(\sqrt{c-1}+\sqrt{d-1}\) (cite?). Finally, note that a 2-lift of a bipartite graph is bipartite with the same degree distribution and thus the same universal cover. Therefore, applying 2-lifts inductively to the complete bipartite graph \(K_{cd}\), whose non-trivial eigenvlaues are zero, yields an infinite family of \((c,d)\)-biregular Ramanujan graphs.

The proof of Theorem \ref{main} is probabilistic. One attempt is to consider the expected largest eigenvalue over all signed adjacency matrices of \(G\). If the expectation were bounded by \(\rho(T)\), then so would the largest eigenvalue of some signed adjacency matrix. Unfortunately, this expectation can be much bigger than \(\rho(T)\). An alternative is to consider the expected characteristic polynomial of the signed adjacency matrices, since their roots are the new eigenvalues. In general, the relation between the roots of a sum of polynomials and the roots of a summand can be arbitrary. For reasons we will become clear with in Section \ref{interlacing}, the set of signed adjacency matrices is a spectial case, where the largest root of the expected characteristic polynomial actually provides an upper bound on the roots of some characteristic polynomial. This expectation is the matching polynomial of \(G\).

In this section, we follow the notations of Godsil (cite?). A matching with \(r\)-edges is called an \(r\)-matching. For a graph \(G\) on \(n\) vertices, we let \(m(G,r)\) denote the number of \(r\)-matchings in \(G\). Then \(m(G,0)=1\), and \(m(G,1)\) is the number of edges in \(G\). The matching polynomial of \(G\) is the generating function

\begin{equation} \nonumber \mu(G,x)=\sum_{r\ge 0}(-1)^rm(G,r)x^{n-2r}. \end{equation}

For example, the following graph has \(14\) matchings of size two and three perfect matchings, so its matching polynomial is \(x^6-8x^4+14x^2-3\).

We introduce two useful properties of the matching polynomials (see, e.g, (cite?)). When we write \(G\cup H\), we mean the disjoint union of the graphs \(G\) and \(H\). The notation \(G\backslash u\) denotes the graph obtained from \(G\) with \(u\) removed, and \(G\backslash uv\) the graph obtained from \(G\) with both \(u\) and \(v\) removed.

To bound the roots of the matching polynomial of \(G\), we need a connection between the matching polynomial and the universal cover. For a vertex \(u\) in \(G\), the path tree \(P(G,u)\) is the tree with all paths in \(G\) starting at \(u\) as its vertices, such that two paths are adjacent if one is a maximal subpath of the other. Godsil proved that the matching polynomial divides the characteristic polynomial of every path tree (see, e.g, (cite?)).

The above theorem follows from the following three lemmas and the fact that the matching polynomial and the characteristic polynomial of a forest are equal (cite?). For simplicity, we write \(\mu(G)\) for \(\mu(G,x)\) whenever the context is clear.

Theorem \ref{path} immediately implies the following:

Now consider the random signing \(s:E\to \{1,-1\}^m\). Let

\begin{equation} \nonumber f_s(x):=\det(xI-A_s). \end{equation}

The following theorem due to Godsil and Gutman (cite?) reveals the relation between these characteristic polynomials and the matching polynomial. We present a slightly modified proof based on the one given by Marcus et al (cite?).

Theorem \ref{bound} and Theorem \ref{expect} show that the roots of \(\E(f_s)\) are bounded by \(\rho(T)\). It suffices to prove that there is a signing \(s\) for which the largest root of \(f_s\) are bounded by the largest root of \(\E(f_s)\). This is guaranteed by the interlacing properties of \(\{f_s\}\).

Let \(g=\prod_{i=1}^{n-1}(x-\alpha_i)\) and \(f=\prod_{i=1}^n(x-\beta_i)\) be two real-rooted polynomials. We say \(g\) interlaces \(f\) if between every pair of roots of \(f\), there is a root of \(g\). In other words, \(g\) interlaces \(f\) if

\begin{equation} \nonumber \beta_1\le \alpha_1\le \beta_2\le \alpha_2\cdots\le \alpha_{n-1}\le \beta_n. \end{equation}

A set of polynomials \(f_1,f_2,\cdots,f_k\) have a common interlacing if there is a polynomial \(g\) that interlaces all of them.

The characteristic polynomials \(\{f_s\}\) do not necessarily have a common interlacing. However, they still have the desired property, as we can form them into an interlacing family.

Let \(S_1,\ldots, S_m\) be \(m\) sets. Suppose we have a set of polynomials \(\{f_{s_1,\cdots, s_m}\}\) indexed by the \(m\)-tuples in \(S_1\times \cdots \times S_m\). For \(k < m\) and a partial assignment \((s_1,\cdots, s_k)\in S_1\times \cdots \times S_k\), define

\begin{equation} \nonumber f_{s_1,\cdots,s_k}:=\sum_{(s_{k+1}, \cdots, s_m)\in S_{k+1}\times \cdots \times S_m} f_{s_1,\cdots,s_k,s_{k+1},\cdots,s_m}. \end{equation}

Intuitively, this is the scaled conditional expectation of the random polynomial chosen from \(\{f_{s_1,\cdots,s_m}\}\) with the first \(k\) coordinates fixed. In particular, for \(k=0\),

\begin{equation} \nonumber f_{\emptyset}:=\sum_{(s_1,\cdots, s_m)\in S_1\times \cdots \times S_m} f_{s_1,\cdots,s_m} \end{equation}

which gives the expectation over the whole set.

The polynomials \(\{f_{s_1,\cdots,s_m}\}\) form an interlacing family if for every \(k < m\) and every \((s_1,\cdots,s_k)\in S_1\times \cdots \times S_k\), the polynomials

\begin{equation} \nonumber \{f_{s_1,\cdots,s_k,t}:t\in S_{k+1}\} \end{equation}

have a common interlacing.

A basic problem in showing a set of polynomials form an interlacing family is to prove the existence of common interlacings. This is equivalent to the problem of real-rootedness of the convex combinations of the set, as dicovered independently in (cite?).

The proof of the above lemma is long. We sketch the ideas for the backward direction for two polynomials \(f\) and \(g\) with roots \(\alpha_1,\cdots,\alpha_n\) and \(\beta_1,\cdots, \beta_n\) respectively. Suppose the polynomial

\begin{equation} \nonumber h_{\lambda}=\lambda f+(1-\lambda)g. \end{equation}

is real-rooted for all \(\lambda\in[0,1]\). Note that \(f_1\) and \(f_2\) have a common interlacing if and only if for each \(\ell=1,2,\cdots,n-1\), we have

\begin{equation} \nonumber \max(\alpha_{\ell},\beta_{\ell})\le \min(\alpha_{\ell+1},\beta_{\ell+1}). \end{equation}

Another important observation is that that if \(f\) and \(g\) do not share any root, then the function

\begin{equation} \nonumber q_{\lambda}=\frac{\lambda}{1-\lambda}+\frac{g}{f} \end{equation}

has the same roots as \(h_{\lambda}\), which are all simple. This divides the proof into three steps. First, suppose \(f\) and \(g\) have distinct roots and do not share any root. By way of contradiction, if they do not have a common interlacing, then there is a smallest \(\ell\) such that

\begin{equation} \nonumber \max(\alpha_{\ell},\beta_{\ell})> \min(\alpha_{\ell+1},\beta_{\ell+1}). \end{equation}

One can show that the function \(q_0(x) < 0\) for all \(x\in(\alpha_{\ell},\alpha_{\ell+1})\). Adding a proper constant to \(q_0\) yields a funcion \(q_{\lambda}\) that has a multiple root in the interval \((\alpha_{\ell},\alpha_{\ell+1})\) for some \(\lambda\in(0,1)\). This contradicts the assumption. Next, for \(f\) and \(g\) that have multiple roots but do not share any root, the polynomials

\begin{gather*} f_{\varepsilon}=(1+\varepsilon)f+\varepsilon g\\ g_{\varepsilon}=\varepsilon f+(1-\varepsilon)g \end{gather*}

with sufficiently small \(\varepsilon>0\) have simple roots as \(f\) and \(g\) respectively, and do not share any root. For any \(\lambda\in[0,1]\), the roots of

\begin{equation} \nonumber h_{\lambda,\varepsilon}=\lambda f_{\varepsilon}+(1-\lambda)g_{\varepsilon} \end{equation}

are real. Thus, taking the limit for \(\varepsilon\to 0\) on both sides of

\begin{equation} \nonumber \max(\alpha_{\ell,\varepsilon},\beta_{\ell,\varepsilon})\le \min(\alpha_{\ell+1,\varepsilon},\beta_{\ell+1,\varepsilon}) \end{equation}

yields

\begin{equation} \nonumber \max(\alpha_{\ell},\beta_{\ell})\le \min(\alpha_{\ell+1},\beta_{\ell+1}). \end{equation}

Finally, the case where \(f\) and \(g\) with a common root \(\alpha\) can be treated by writing

\begin{gather*} f(x)=(x-\alpha)^{n_1}f_1(x)\\ g(x)=(x-\alpha)^{n_1}g_1(x) \end{gather*}

and applying the second case to \(f_1\) and \(g_1\). The general statement in which \(f\) and \(g\) have more than one common root follows in a similar way.

For our characteristic polynomials \(\{f_s\}\), the sets

\begin{equation} \nonumber S_1=\cdots=S_m=\{1,-1\}. \end{equation}

If for every \(k < m\) and every partial assignment \((s_1,\cdots,s_k)\in \{1,-1\}^m\), any convex combination of \(f_{s_1,\cdots,s_k,1}\) and \(f_{s_1,\cdots,s_k,-1}\) is real-rooted, then \(\{f_s\}\) form an interlacing family. This will follow from a more general result due to Marcus et al (cite?). In particular, real-rootedness of a univariate polynomial is implied by its real stability.

A multivariate polynomial \(f\in \mathbb{R}[z_1,\cdots,z_m]\) is called real stable if

\begin{equation} \nonumber f(z_1,\cdots,z_m)\ne 0 \end{equation}

whenever the imaginary parts of all \(z_i\) are positive. Borcea and Branden (cite?) showed that the following determinantal polynomials are real stable.

As a consequence of Hurwitz's theorem, if \(f(z_1,\cdots,z_m)\) is real stable, then so is \(f(z_1,\cdots,z_{m-1},c)\) for every real number \(c\) (see e.g, (cite?)). Thus, replacing any variable in the above determinantal polynomial by a real number preserves real stability.

Borcea and Branden (cite?) also characterized a class of differential operators on polynomials that preserve real stability. We will need a corollary to their characterization.

Operators of the above kind are of central role in the general statement that implies real-rootedness of the polynomials we are interested in. We will compose them with the operator \(Z_u\), which sets the variable \(u\) in a polynomial to zero. The following two lemmas are intermediate steps towards the general statement.

For instance, let \(A=\begin{pmatrix}1 & 2\\ 3 & 4\end{pmatrix}\), \(a=\begin{pmatrix} 5 \\6\end{pmatrix}\) and \(b=\begin{pmatrix} 7 \\ 8\end{pmatrix}\). We have

\begin{equation} \nonumber \det(A+uaa^T+vbb^T)=4uv - 14u - 20v - 2. \end{equation}

Thus

\begin{gather*} \det(A+uaa^T+vbb^T)\big|_{u=0,v=0}=-2\\ Z_uZ_v\partial_u\det(A+uaa^T+vbb^T)=4v-14\big|_{u=0,v=0}=-14\\ Z_uZ_v\partial_v\det(A+uaa^T+vbb^T)=4u-20\big|_{u=0,v=0}=-20. \end{gather*}

On the other hand,

\begin{gather*} \det(A+aa^T)=-16\\ \det(A+bb^T)=-22. \end{gather*}

Substituting these into both sides in Lemma \ref{operator} yields the same result \(6p-22\).

Lemma \ref{operator} leads to the main technical result on real-rootedness due to Marcus et al (cite?).

Now we show that if we pick the sign for each edge independently with any probability \(p_i\), then the expected characteristic polynomial is still real-rooted.

In this section, we prove the interlacing property of \(\{f_s\}\), which leads to the final existence result (cite?).

Marcus et al (cite?) proved the existence of infinite families of biregular Ramanujan graphs of all degrees. In particular, this answers Lubotzy's question on the existence of infinite families of \(d\)-regular Ramanujan graph for every \(d\ge 3\) (cite?). However, the application of Theorem \ref{main} is restricted to bipartite graphs, as it only provides an upper bound on the eigenvalues. It will be interesting to find a construction of non-bipartite Ramanujan graphs.

Another challenge is to give an efficient algorithm that finds the desired family of bipartite Ramanujan graphs. The existence proof in (cite?) is probabilistic, in which the polynomials \(\{f_{s_1,\cdots,s_k,t}\}\) are not easy to compute. For example, computing the matching polynomial of a graph is a \(\sharp P\)-hard problem in general. Thus, one might want to discover a polynomial-time algorithm based on this method.

In the course, we saw the proof of Cheeger's inequality:

The proof of the Cheeger's inequality is constructive and gives a spectral partitioning algorithm: take an eigenvector \(f\) of \(\lambda_2\), consider all the canonical cuts introduced by \(f\) and pick one with the smallest conductance. Let \(\phi(f)\) be the corresponding smallest conductance. The proof of the Cheeger's inequality actually shows that \(\frac{1}{2} \lambda _2 \leq \phi(f) \leq \sqrt{2 \lambda_2}\). Therefore, the spectral partitioning algorithm gives a linear time \(O(1/\sqrt{\lambda_2})\)-approximation algorithm for finding a sparse cut. However, the worst case performance is bad as \(\lambda_2\) can be as small as \(1/n^2\).

Spectral partitioning is a popular heuristic algorithm as it is easy to implement and works really good for some applications such as image segmentation and clustering. Its performance is much better than the worst case performance guaranteed by Cheeger's inequality and little explanation has been found for it. Improved Cheeger's inequality is a good step towards finding theoretical explanation for these kind of phenomena. It improves the upper bound of the Cheeger's inequality by using higher order spectral information. Improved Cheeger's inequality can also be used to find \(k\)-way graph partitioning that is partitioning the vertices of a graph into \(k\) disjoint sets such that the maximum conductance among them is small.

In Section 2, we see some preliminary results and definitions and also the statement of the improved Cheeger's inequality. In Section 3, we prove the main theorem. Section 4 is about spectral max cut algorithms. In class, we saw Trevisan's spectral algorithm for finding the maximum cut of a graph with approximation guarantee slightly more than \(0.5\). In the same fashion as improved Cheeger's inequality, in Section 4, we see an improved bound using higher order spectral information. Using that, we introduce another max cut algorithm that actually uses higher order spectral information. Section 5 is the conclusion.

Assume that we have a connected graph \(G=(V,E,w)\), with positive weights on the edges. For two sets of vertices \(S\) and \(T\), we define \(E(S,T)\) as the set of all edges that has one end in \(S\) and the other end in \(T\), we also define \(E(S)=E(S,S)\). We can extend the definition of weight to vertices as \(w(v)=\sum_{u \sim v} w(u,v)\), for all \(v \in V\). Note that if we use unit weights, then the weight of each vertex is just the degree of that. We define the volume of any \(S \subseteq V\) as \(vol(S):= \sum_{v \in S} w(v)\). Given a subset of vertices \(S\), we define the conductance of \(S\) as

\begin{equation} \nonumber \phi(S) := \frac{w(E(S, \overline{S}))}{\min \{vol(S),vol(\overline{S})\} }. \end{equation}

For a vector \(f \in \mathbb R^V\), and for a threshold \(t \in \mathbb R\), let \(V_f(t) := \{v: f(v) \geq t\}\) be a threshold set of \(f\). We let

\begin{equation} \phi(f) := \min_{t \in \mathbb R} \phi(V_f(t)). \label{phi-f} \end{equation}

We define the adjacency matrix as an operator that for any vector \(f \in \mathbb R^V\) and any vertex \(v\), we have \(Af(v) = \sum_{u \sim v} w(u,v) f(u)\). We also define the diagonal matrix \(D\) with the weights of vertices \(w(v)\)'s on the diagonal. Then the normalized Laplacian matrix is

\begin{equation} \nonumber \mathcal{L}:= I - D^{-1/2} A D^{-1/2}. \end{equation}

\(\mathcal{L}\) is a positive semidefinite matrix with eigenvalues:

\begin{equation} \nonumber 0 = \lambda_1 \leq \lambda_2 \leq \ldots \leq \lambda_n \leq 2. \end{equation}

Here is the statement of the main theorem, improved Cheeger's inequality, we prove.

The above theorem is interesting because it gives an improved theoretical bound for spectral partitioning algorithm that contains \(\lambda_k\), but the algorithm does not use any information from higher order eigenvalues. Informally, improved Cheeger's inequality shows that the graph has at most \(k-1\) outstanding sparse cuts when \(\lambda_{k-1}\) is small and \(\lambda_k\) is large. Let us see an example here. Let \(G\) be a graph on 50 vertices constructed as follows: attach a copy of a complete graph \(K_{10}\) to each vertex of a 5-cycle as in Figure \ref{Fig1}.

The first 6 eigenvalues of the normalized Laplacian are

\begin{equation} \nonumber \lambda_1=0, \ \ \lambda_2=\lambda_3=0.0134, \ \ \lambda_4=\lambda_5=0.0297, \ \ \lambda_6=0.9293. \end{equation}

As can be seen, there are 5 major components in graph \(G\). In other words, we can partition \(V(G)\) into 5 disjoint sets with small conductances. However, it is easy to check that we cannot partition it into 6 disjoint sets with the same property. Improved Cheeger's inequality implies that there is a large gap between \(\lambda_5\) and \(\lambda_6\) as can be seen above. Another interesting observation is an eigenvector of \(\lambda_2\). Figure \ref{Fig2} shows an eigenvector of \(\lambda_2\) as a functional of vertices. As can be seen, the eigenvector is like a step function. This is a key idea in the proof of the main theorem that if there is large gap between \(\lambda_{k-1}\) and \(\lambda_k\) for a small \(k\), then the second eigenvector is close to a step function, with \(O(k)\) number of steps. This also gives us an idea on \(k\)-way graph partitioning.

Informally, improved Cheeger's inequality says

• An undirected graph has \(k\) disjoint sparse cuts if and only if \(\lambda_k\) is small.
• When \(\lambda_{k-1}\) is small and \(\lambda_k\) is large, we can partition the graph into \(k-1\) sets of small conductance, but for every partitioning into \(k\) sets, there exists a set with large conductance.

Let us define the weighted norm of a vector \(f\) and its Rayleigh quotient with respect to \(G\) as

\begin{equation} \|f\|^2_w:=\sum_{v\in V} w(v) f^2(v), \ \ \ \ \mathcal{R}(f):=\frac{\sum_{uv \in E} w(u,v) |f(u)-f(v)|^2}{\|f\|_w^2}. \end{equation}

The support of a vector \(f\) is defined as \(\text{supp}(f) := \{v, f(v) \neq 0\}\).

In the rest of this section, we see three lemmas needed for the proof of the main theorem. The proof starts with the following lemma:

The following lemma is also very important in proving the main theorem.

The following well-known result is also needed for our proof. We gave a deterministic and randomized proof for that in class.

A key definition in the proof is \(k\)-step approximation of a vector \(f\). For any \(t_0,\ldots, t_{k-1} \in \mathbb R\), let us define the function \(\psi: \mathbb R \rightarrow \mathbb R\) as

\begin{equation} \nonumber \psi_{t_0,\ldots, t_{k-1}} (x)=\text{argmin}_{t_i}|x-t_i|. \end{equation}

Then we say that \(g\) is a \(k\)-step approximation of \(f\) if there exist \(t_0,\ldots, t_{k-1} \in \mathbb R\) such that

\begin{equation} \nonumber g(v) = \psi_{t_0,\ldots, t_{k-1}} (f(v)), \ \ \ \forall v \in V. \end{equation}

In other words, \(g(v)=t_i\) if \(t_i\) is the closest threshold to \(f(v)\). Figure \ref{Fig3} from \cite{main} shows the relation between \(f\) and \(g\) schematically.

The theme of our proof is that if there is a large gap between \(\lambda_2\) and \(\lambda_k\), then the vector \(f\) in Lemma \ref{R1} can be well approximated by a \(2k+1\) step function. Let us start by the following lemma:

Now we want to upper bound \(\phi(f)\) by using a \(2k+1\) step approximation of \(f\).

After proving Lemma \ref{L1} and Proposition \ref{P1}, the proof of the main theorem is immediate. Assume that \(f\) is a vector given by Lemma \ref{R1}, and let \(g\) be a vector given by Lemma \ref{L1}, then by using Proposition \ref{P1} we get

\begin{eqnarray} \phi(f) &\leq& 4k \mathcal{R}(f) + 4\sqrt{2}k\|f-g\|_w \sqrt{\mathcal{R}(f)} \ \ \ \text{(by Proposition \ref{P1})}\nonumber \\ &\leq& 4k \mathcal{R}(f) + 8\sqrt{2}k \mathcal{R}(f) / \sqrt{\lambda_k} \ \ \ \text{(by Lemma \ref{L1})} \nonumber \\ &\leq& 12\sqrt{2}k \mathcal{R}(f) / \sqrt{\lambda_k} \ \ \ \text{(using \(\lambda_k \leq 2\))}\nonumber \\ &\leq& 12\sqrt{2}k \frac{\lambda_2}{ \sqrt{\lambda_k}} \ \ \ \text{(by Lemma \ref{R1})}. \nonumber \end{eqnarray}

This is the improved Cheeger's inequality.

In class, we saw Trevisan's spectral algorithm for finding the maximum cut in a graph with approximation guarantee slightly more than \(0.5\). In the same fashion as improved Cheeger's inequality, in this section, we see an improved bound using higher order spectral information. Using that, we introduce another max cut algorithm that actually uses higher order spectral information. Let us define the normalized sum Laplacian of a graph \(G\) as \(I + D^{-1/2}AD^{-1/2}\), with eigenvalues \(0 \leq \alpha_1 \leq \ldots \leq \alpha_n \leq 2\). Let \((L,R)\) be subset of vertices such that \(L \cup R \neq \emptyset\), then we define bipartiteness ratio of \((L,R)\) as:

\begin{equation} \nonumber \beta(L,R) := \frac{2w(E(L,L))+2w(E(R,R))+w(E(L \cup R,\overline{L \cup R}))}{vol(L \cup R)}. \end{equation}

We define the bipartiteness ratio of a graph \(\beta(G)\) as the minimum of \(\beta(L,R)\) over all possible \((L,R)\). For a vector \(f\) and a threshold \(t\geq0\), let \(L_f(t):=\{v: f(v) \leq -t\}\) and \(R_f(t):=\{v: f(v) \geq t\}\) be a threshold cut of \(f\), then we define

\begin{equation} \nonumber \beta(f):= \min _{t \geq 0} \beta(L_f(t),R_f(t)), \end{equation}

and we let \((L_f(t_{opt}),R_f(t_{opt}))\) be the best threshold set of \(f\). In this section, we abuse the definition of Rayleigh quotient of \(f\) as

\begin{equation} \nonumber \mathcal{R}(f):= \frac{\sum_{u \sim v}w(u,v)|f(u)+f(v)|^2}{\sum_v w(v) f(v)^2}. \end{equation}

We proved the following lemma before

We also proved the following lemma that is very similar to the Cheeger's inequality and was the key point in designing the spectral max cut algorithm.

Using Lemma \ref{L2}, we saw a spectral algorithm for the max cut problem that guarantees an approximation ratio more that \(0.5\). Similar to the idea used for Cheeger's inequality, if we can improve the upper bound in Lemma \ref{L2} be using higher order spectral information, we can improve the approximation guarantee. The improvement of Lemma \ref{L2}, in the same fashion as improved Cheeger's inequality, is the following theorem:

As can be seen, this theorem is very similar to improved Cheeger's inequality and the proof is also very similar. We can define a \(k\)-step approximation \(g\) of a vector \(f\) as before, the only difference is that here \(f\) can accept negative values. The proof of Theorem \ref{T2} follows from the following two lemmas that are the adaptation of Proposition \ref{P1} and Lemma \ref{L1}. We state them without proof as the proofs are similar to their counterparts.

Note that we used Lemma \ref{L2} to prove the approximation guarantee for the Trevisan's max cut algorithm. Now that we have the improved bound of Theorem \ref{T2}, we can get a better bound for the same algorithm. However, we can do more and design an algorithm that uses higher order spectral information to get a better approximation bound.

The result proved in Trevisan's original paper \cite{tre} is stated slightly different from what we saw in class. The following theorem is the main result of \cite{tre}

\cite{tre} uses the above theorem to find a recursive algorithm with approximation guarantee of \(0.531\). The following theorem shows that by using higher order spectral information, a stronger result can be found.

In the rest of this paper, we state the algorithm and prove that if the algorithm works, we get the result of Theorem \ref{imp-cut}. To prove that the algorithm actually works and all the steps are consistent needs more work and an interested reader can find it in \cite{main}.

Let us define uncutness for a pair of cuts \((L,R)\) as follows

\begin{equation} \nonumber \gamma(L,R) := w(E(L,L))+w(E(R,R))+w(E(L \cup R, \overline{L \cup R})). \end{equation}

Note that the coefficient of edges inside \(L\) and \(R\) is one instead of 2 in the definition of \(\beta(L,R)\). The edges that contribute to the uncutness are shown in Figure \ref{Fig4}.

Here is the algorithm \\
A spectral algorithm for max cut:

\begin{eqnarray} &&U \leftarrow V, L \leftarrow \emptyset, R \leftarrow \emptyset. \nonumber\\ && \textbf{while \(E(U) \neq \emptyset\) do} \nonumber \\ && \ \ \ \text{Let \(H=(U,E(U))\) be the induced subgraph of \(G\) on \(U\).} \nonumber \\ && \ \ \ \text{Let \(f\) be the first eigenvalue of the sum Laplacian.} \nonumber \\ && \ \ \ \textbf{if \(\beta_H(f) \leq 192 \sqrt{2} k \mathcal{R}_H(f) / \alpha_k\) then} \nonumber \\ && \ \ \ \ \ (L,R) \leftarrow (L \cup L_f(t_{opt}),R \cup R_f(t_{opt})). \nonumber \\ && \ \ \ \ \ \text{Remove \(L_f(t_{opt})\) and \(R_f(t_{opt})\) from $U$}. \nonumber \\ && \ \ \ \textbf{else} \nonumber \\ && \ \ \ \ \ \text{In view of Lemma \ref{R4}, pick \(k\) disjointly supported vectors \(f_1,\ldots,f_k\) such that} \nonumber \\ && \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \beta_H(f) \leq 16 k \frac{\mathcal{R}_H(f)}{\sqrt{\max_{1 \leq i \leq k} \mathcal{R}_H(f_i) }}. \nonumber \\ && \ \ \ \ \ \text{Find a threshold cut \((L',R')=(L_{f_i}(t),R_{f_i}(t))\) for \(1 \leq i \leq k\) such that} \nonumber \\ && \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \min(\gamma(L \cup L',R \cup R'),\gamma(L \cup R',R \cup L') ) \leq \gamma(L,R). \nonumber \\ && \ \ \ \ \ \text{Remove \(L'\) and \(R'\) from \(U\), and let \((L,R)\) be one of \((L \cup L',R \cup R')\) or $(L \cup R',R \cup L')$} \nonumber \\ && \ \ \ \ \ \text{with minimum \(\gamma\).} \nonumber \\ && \ \ \ \textbf{end if} \nonumber \\ && \textbf{end while} \nonumber \\ && \textbf{return \((L,R)\).}\nonumber \end{eqnarray}

The algorithm maintains an induced cut \((L,R)\). To extend it, either we find an induced cut \((L',R')\) in the remaining graph \(H\) with \(\beta(H) = O(k \mathcal{R}_H(f) / \alpha_k)\), or we find an induced cut \((L',R')\) such that \\ \(\min(\gamma(L \cup L',R \cup R'),\gamma(L \cup R',R \cup L') ) \leq \gamma(L,R)\). In other words, we can extend our induced cut such that the uncutness does not increase. Let us see what it means not to increase the uncutness. Assume that \((L,R)\) is updated to \((L\cup L',R \cup R')\), then we have

\begin{equation} \nonumber \gamma(L \cup L',R \cup R') - \gamma(L,R) = - w(E(L,R'))-w(E(L',R))+ w(E(R'\cup L', \overline{ L\cup L' \cup R \cup R' })). \end{equation}

All the edges we have in the RHS of the above equation are shown in Figure \ref{Fig5}. Not increasing the uncutness means that the weight of the edges cut in the \(j\)-th iteration (\(w(E(L,R'))+w(E(L',R))\)) is at least as large as the total weight of the edges removed from \(H\) in the \(j\)-th iteration (\(w(E(R'\cup L', \overline{L\cup L' \cup R \cup R'}))\)). This is important and shows that if \(\beta\) is not small, then we increase our cut at least as large as the edges we remove from \(H\).

We skip the proof that in the second case of the algorithm, we can always find \((L',R')\) with the desired properties, an interested reader can see the proof in \cite{main}. Assuming that, we now prove Theorem \ref{imp-cut}.

Assume that after a number of iterations \(U\) be the remaining vertices, and let \(H=(U,E(U))\) be the corresponding induced subgarph. Let \(\alpha'_1 \geq 0\) be the smallest eigenvalue of the sum Laplacian of \(H\). Also assume that \(w(E(U))= \rho w(E(V))\). We know that the optimal solution cuts at least \(1-\epsilon\) (weighted) fraction of edges of \(G\). This means that it must cut at least \(1- \epsilon /\rho\) fraction of the edges of \(H\), otherwise the total fraction of edges cut is less that \((1-\rho)+(1-\epsilon /\rho) \rho=1-\epsilon\), which is a contradiction. This means that for an eigenvector \(f\) of \(H\) with eigenvalue \(\alpha_1'\), using Lemma \ref{L2}, we have

\begin{equation} \nonumber \alpha'/2 \leq \beta(H) \leq \epsilon / \rho \ \Rightarrow \ \mathcal{R}_H(f) \leq 2\epsilon / \rho \end{equation}

Using this, in the first case of the algorithm, we have

\begin{equation} \beta(L',R') \leq 192 \sqrt{2} k \mathcal{R}_H(f) / \alpha_k \leq 600k \frac{\epsilon}{\rho \alpha_k}. \label{eq3} \end{equation}

Our goal is to find the ratio of the edges cut by the final solution of the algorithm. Let \(\rho_j w(E)\) be the fraction of edges in \(H\) before the \(j\)-th iteration of the while loop for all \(j \geq 1\), so we have \(\rho_1=1\). If the first case of the algorithm happens in iteration \(j\), then by using \eqref{eq3} we cut at least \((1-600k \frac{\epsilon}{\rho_j \alpha_k})\) fraction of edges removed from \(H\) in the \(j\)-th iteration. The weight of the edges before \((j+1)\)-th iteration is \(\rho_{j+1} w(E)\), so we can find the following bound on the weight of edges added to the cut at iteration \(j\)

\begin{equation} \nonumber (\rho_j-\rho_{j+1}) w(E) \left (1-600k \frac{\epsilon}{\rho_j \alpha_k} \right ) \geq w(E) \int_{\rho_{j+1}}^{\rho_{j}} \left (1-600k \frac{\epsilon}{r \alpha_k} \right ) dr. \end{equation}

This inequality is by using the fact that \(\rho_j \geq \rho_{j+1}\) and the function in the integral is increasing.

In the second case of the algorithm, we choose a threshold cut of one of \(f_1,\ldots,f_k\). We choose \((L',R')\) such that the uncutness does not increase. As we explained above, this means that the weight of the edges cut in the \(j\)-th iteration is at least as large as the total weight of the edges removed from \(H\) in the \(j\)-th iteration. By our definition, this means the weight of the edges cut in the \(j\)-th iteration is at least \((\rho_j-\rho_{j+1}) w(E)\).

Assume that the \(j\)-th iteration is the last iteration that we use case 1 in the algorithm, then as we cut at least \((1-600k \frac{\epsilon}{\rho_j \alpha_k})\) of edges, we should have \(\rho_j \geq 600k \frac{\epsilon}{ \alpha_k}\). Using that and putting the above results for the two cases together, we conclude that the fraction of the edges cut by the algorithm is at least

\begin{equation} \nonumber \int_{600k \epsilon / \alpha_k} ^ 1\left (1-600k \frac{\epsilon}{r \alpha_k}\right ) dr = 1- \frac{600 k \epsilon}{ \alpha_k} \left ( 1+ \ln \left (\frac{\alpha_k}{600k \epsilon} \right )\right ). \end{equation}

This completes the proof of Theorem \ref{imp-cut}.

In this paper, we introduced and proved the improved Cheeger's inequality that uses higher order spectral information to improve the upper bound on the conductance of a graph. We also saw how to find a similar result for the bipartiteness of a graph, and introduced an improved spectral algorithm for the max cut that uses higher order spectral information.

In the main reference \cite{main}, you can find a second proof for the improved Cheeger's inequality. As these proofs are constructive, each of them gives ideas for designing algorithms. Section 4 of \cite{main} is about the connections and applications, and we saw the max cut algorithm from that section. The other applications studied are spectral multiway partitioning, balanced separation, manifold setting, planted and semi-random instances, and stable instances.

The paper is available at http://arxiv.org/abs/1304.2338, and a lecture by the first author is available at http://video.ias.edu/csdm/2014/0224-JonathanKelner.

In this section, we formally state the Maximum Flow problem and the main result of the paper.

Let \(G = (V, E, \mu)\) be a capacitated graph. Throughout this report, all graphs are undirected. Let \(n = |V|\) and \(m = |E|\) denote the number of vertices and edges in \(G\), respectively. The vector \(\mu \in \left(\mathbb{R}_*^+\right)^E\) gives the capacities of the edges. We are also given a vector of vertex demands \(\chi \in \mathbb{R}^V\) satisfying \(\sum_{v \in V} \chi_v = 0\). Whenever we say that a vector is a vector of vertex demands, we assume that it has that property. Our goal is to find the maximum value of \(\alpha\) such that there exists a flow satisfying the vertex demands \(\alpha\chi\) and such that the amount of flow along each edge \(e \in E\) is at most its capacity \(\mu_e\).

Next, we introduce some notation to allow a more precise and concise statement of the problem. We assume an arbitrary orientation of the edges of \(E\), and we let \(f \in \mathbb{R}^E\) denote a flow. We denote by \(f_e\) the flow on an edge \(e = (u, v) \in E\). When \(f_e > 0\) (respectively, when \(f_e < 0\)), flow is being sent from vertex \(u\) to vertex \(v\) (respectively, from vertex \(v\) to vertex \(u\)). For a vertex \(v \in V\), we denote by \(\vec{1}_v \in \mathbb{R}^V\) the vector whose entry indexed by \(v\) is equal to one, and whose all other entries are equal to zero. We define the edge-vertex incidence matrix \(B \in \{-1, 0, 1\}^{E \times V}\), whose row indexed by an edge \(e = (u, v) \in E\) is equal to \(\left(\vec{1}_u - \vec{1}_v\right)^\intercal\). We let \(U \in \left(\mathbb{R}_*^+\right)^{E \times E}\) denote the diagonal matrix associated with the edge capacities.

Using the notation introduced, we can succinctly restate the problem as follows.

The Maximum Flow Problem: $$\label{MF1} \tag{MF$_1$} \max\left\{\alpha \in \mathbb{R} : \exists f \in \mathbb{R}^E \textrm{ such that } B^\intercal f = \alpha \chi \textrm{ and } \left\|U^{-1}f\right\|_{\infty} \le 1 \right\}$$

The following examples may help in understanding the notation. Figure 18 shows a graph \(G\) with $$B = \left( \begin{array}{cccc} 1 & -1 & 0 & 0 \\ 0 & 1 & -1 & 0 \\ 0 & 0 & -1 & 1 \\ 1 & 0 & 0 & -1 \\ \end{array} \right) \textrm{ and } U = \left( \begin{array}{cccc} 2 & 0 & 0 & 0 \\ 0 & 4 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{array} \right) \ .\notag$$

Figure 19 shows the flow \(f = \left(-3, -1, 1,-3\right)^\intercal\) on graph \(G\). Note that \(f\) satisfies the vector of vertex demands $$\begin{aligned}B^\intercal f & = & \left(\begin{array}{cccc} 1 & -1 & 0 & 0 \\ 0 & 1 & -1 & 0 \\ 0 & 0 & -1 & 1 \\ 1 & 0 & 0 & -1 \\ \end{array} \right)^{\intercal} \left(\begin{array}{c} -3\\ -1\\ 1\\ -3 \end{array}\right) = \left(\begin{array}{c} -6\\ 2\\ 0\\ 4\\ \end{array}\right)\ ,\end{aligned} \notag$$ and that \(f\) violates the capacity constraints, because $$\begin{aligned} \left\|U^{-1}f\right\|_{\infty}& = & \left( \begin{array}{cccc} 2 & 0 & 0 & 0 \\ 0 & 4 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{array} \right) ^{-1} \left( \begin{array}{c} -3 \\ -1 \\ 1 \\ -3 \\ \end{array} \right) = \left\|\left( \begin{array}{c} -\frac{3}{2} \\ - \frac{1}{4} \\ 1 \\ -3 \end{array}\right)\right\|_{\infty} = 3 > 1 \ .\end{aligned}\notag$$

The main result of the paper is the following theorem. The capacity ratio of graph \(G\) is defined as the ratio between the maximum and the minimum capacity of an edge, and is denoted by \(S\).

Prior to this paper, the most efficient algorithm known was due to Christiano et al, with running time $$\tilde{O}\left(mn^{\frac{1}{3}}\textrm{poly}\left(\epsilon^{-1}\right)\right) \ .\notag$$

In Sections 11.5.1 – 11.5.3, we reformulate the Maximum Flow Problem \ref{MF1} as an unconstrained optimization problem. This reformulation requires the introduction of a projection matrix from the space of flows on \(G\) to the space of circulations on \(G\).

Section 11.5.5 describes how the Gradient Descent Method can be used to approximately solve the resulting unconstrained optimization problem. This requires replacing the objective function, which is non-differentiable, by a smooth approximation described in Section 11.5.4. Further, in order to avoid an inherent \(O(\sqrt{m})\) factor in the number of iterations, the authors introduce and analyze a non-Euclidean variant of the Gradient Descent Method, which is described in Section 11.4.

The running time of the algorithm presented in Section 11.5.5 depends heavily on the projection matrix used in the reformulation of the problem. Section 11.5.6 shows how to efficiently construct a projection matrix in order to obtain an almost-linear running time. Section 11.5.6.1 shows that this reduces to efficiently constructing an oblivious routing with low congestion, and Section 11.5.6.2 discusses how to construct such an oblivious routing. This is done by recursively constructing oblivious routings on smaller graphs. Obtaining a low-congestion oblivious routing for a graph from oblivious routings for smaller graphs is possible as long as there exist low-congestion embeddings from the original graph to the smaller ones and vice-versa. The recursive algorithm relies on two operations for obtaining smaller graphs: edge sparsification and vertex elimination. The former operation is based on Spielman and Teng and Spielman and Teng, while the latter is based on Madry, and presented on Section 11.5.6.3. The base case of the recursive algorithm uses electrical flows on graphs with \(O(1)\) vertices.

In this section, we describe a method for solving the problem $$\label{P} \tag{P} \min_{y \in \mathbb{R}^n} f(y) \ ,$$ where \(f : \mathbb{R}^n \rightarrow \mathbb{R}\) is a convex function with Lipschitz-continuous gradient.

Let \(\|\cdot\| : \mathbb{R}^n \rightarrow \mathbb{R}\) be an arbitrary norm on \(\mathbb{R}^n\), and recall that the gradient of \(f\) at a point \(x \in \mathbb{R}^n\) is defined as being the vector \(\nabla f(x) \in \mathbb{R}^n\) such that $$f(y) = f(x) + \langle\nabla f(x), y - x\rangle + o\left(\left\|y - x\right\|\right) \ .\notag$$

The analysis of the Gradient Descent Method when \(\|\cdot\|\) is the \(\ell_2\)-norm relies on the Cauchy-Schwarz inequality to compare the improvement \(\langle\nabla f(x), y - x\rangle\) when moving from a point \(x\) to a point \(y\) with the step size \(\left\|y - x\right\|\) and the value \(\nabla f(x)\) of the gradient at \(x\). Here, we rely on an analogue of the Cauchy-Schwarz inequality. We introduce the dual norm \(\left\|\cdot\right\|^{*} : \mathbb{R}^n \rightarrow \mathbb{R}\), defined as follows: $$\left\|x\right\|^{*} = \max_{y \in \mathbb{R}^n : \left\|y\right\| \le 1} \langle y, x \rangle \ .\notag$$

Bounding the convergence rate of the method requires assumptions on the smoothness of the gradient of \(f\). Specifically, we assume that \(\nabla f\) is Lipschitz-continuous with Lipschitz constant \(L \in \mathbb{R}^+\), that is, we assume that the following inequality holds for every two vectors \(x, y \in \mathbb{R}^n\): $$\left\|\nabla f(x) - \nabla f(y)\right\|^* \le L \left\|x - y\right\| \ .\notag$$

By integrating \(\frac{d}{dz}f(z)\) along a line going from \(z = x\) to \(z = y\), and using Lemma \ref{cs} and the Lipschitz-continuity of \(\nabla f\), one can prove the following result.

The Gradient Descent Method consists in choosing an initial point, and then at each iteration moving from the current point \(x\) to the point \(y\) that minimizes the upper bound on \(f(y)\) given by Lemma \ref{la}. If we let \(s = y - x\), then finding such a vector \(y\) amounts to solving

$$\min_{s \in \mathbb{R}^n} \left \langle \nabla f(x), s \right \rangle + \frac{L}{2} \left\|s\right\|^2 \ .\notag$$

By making the change of variable \(s = -\frac{s'}{L}\), one can show that the optimal step is \(s = -\frac{1}{L} \left(\nabla f(x)\right)^{\#}\), where $$\left(\nabla f(x)\right)^{\#} = \textrm{argmax}_{s \in \mathbb{R}^n} \langle \nabla f(x), s \rangle - \frac{1}{2}\|s\|^2 \ .\notag$$

We now state the Gradient Descent Method.

The Gradient Descent Method

1. Choose a starting point \(x_0 \in \mathbb{R}^n\).
2. For \(k \gets 0, 1, \dots\), until a stopping condition is met,
3.   let \(x_{k + 1} = x_k - \frac{1}{L} \left(\nabla f\left(x_k\right)\right)^{\#}\).

The following theorem bounds the convergence rate of the Gradient Descent Method. We let \(f^* \in \mathbb{R}\) be the optimal value of problem \ref{P} and \(X^* \subseteq \mathbb{R}^n\) be the set of optimal solutions, which we assume to be non-empty.

Note that the value of \(f\left(x_k\right)\) is non-increasing as \(k\) increases, as each iteration takes the optimal step with respect to the upper bound on \(f\) of Lemma \ref{la}, and the step \(s = 0\) is always a candidate. Thus, the parameter \(R\) is an upper bound on the distance between any point produced by the algorithm and its closest optimal solution.

In this section, we present an approximate algorithm for the Maximum Flow Problem using the Gradient Descent Method.

In Sections 11.5.1 – 11.5.3, we reformulate the problem as an unconstrained optimization problem, which requires introducing a circulation projection matrix. Figure 20 summarizes the steps of the reformulation. In Section 11.5.4, we introduce a smooth approximation of the objective function. In Section 11.5.5, we show how to apply the Gradient Descent Method to find an approximate solution, and we bound the running time of the algorithm. The running time will depend on properties of the projection matrix, and Section 11.5.6 discusses how to efficiently construct such a matrix with the desired properties.