Pseudo-distributions for expansion

Let \(G\) be a \(d\)-regular graph with vertex set \([n]\).The treatment of expansion here also works for non-regular graph. We assume regularity in order to be consistent with earlier definitions in the context of Cheeger’s inequality and degree-2 sum-of-squares. Let \(f_G\from \bits\to\R\) be the function that outputs for every vector \(x\in\bits^n\) the number of edges \(f_G(x)\) cut by \(x\) (viewed as a bipartition of the vertex set), \[ f_G(x)= \sum_{\set{i,j}\in E(G)} (x_i-x_j)^2\,. \] We identify the vector \(x\in \bits^n\) with the subset \(S=\{i\in[n]\mid x_i=1\}\) indicated by \(x\). For every \(i,j\in [n]\), the function \((x_i-x_j)^2\) indicates whether \(i\) and \(j\) are on different sides of the bipartition corresponding to \(x\). Recall the expansion of \(G\), \[ {\varphi}(G) = \min_{x\in \bits^n} \frac{f_G(x)}{\tfrac d n \card{x}\cdot (n-\card{x})}\,. \label{eq:expansion} \] Here, \(\card{x}=\sum_{i=1}^n x_i\) is the size of the set indicated by \(x\).

Note that actual probability distributions \(\mu\from \bits^n\to \R_{\ge 0}\) satisfy \(\E_\mu f_G \ge {\varphi}(G)\cdot \E_{\mu(x)} \frac d n \cdot \card x (n-\card x)\) and equality is achieved by distributions supported on sets with minimum expansion. If we consider degree-4 pseudo-distributions, we can find in polynomial time one such that the ratio of \(\pE_\mu f_G\) and \(\pE_{\mu(x)}\tfrac d n\card{x}(n-\card x)\) is as small as possible—certainly no more than \({\varphi}(G)\). The following theorem shows that this ratio can never be much smaller than \({\varphi}(G)\) and that we can extract from the pseudo-distribution a set with small expansion at most \({\varphi}(G)\cdot O(\sqrt {\log n})\).

A birds-eye view of the proof

The proof of Reference:arora-rao-vazirani-approximation-min-expansion consists of several part. We describe each of them at a high level and explain how they fit together.

The first component is an algorithm called region growing. Given two subsets \(A,B\subseteq[n]\) this algorithm tries to find the best cut of the graph between \(A\) and \(B\) guided by the pseudo-distribution \(\mu\). As we will see, this algorithm achieves a \(O(1/\Delta)\)-approximation (compared to the pseudo-distribution) if the sets \(A,B\) are \(\Delta\)-separated in the sense that \(\card{A},\card{B}\ge \Omega(n)\) and \(\E_{\mu(x)} (x_i-x_j)^2\ge \Delta\) for every \(i\in A\) and \(j\in B\).

The second component is a structure theorem for pseudo-distributions that shows that for some \(\Delta\ge \Omega(1)/\sqrt{\log n}\) such \(\Delta\)-separated sets always exist.The actual proof requires a small case distinction here which we are going to ignore for this high-level discussion.

To prove this structure theorem we apply the quadratic sampling lemma (from lecture 1) in order to obtain Gaussian variables \(X_1,\ldots,X_n\) with the same first two moments as the pseudo-distribution. A natural first attempt to construct separated sets from those variables is to choose \(A\) to be all vertices \(i\in [n]\) such that \(X_i\) is significantly below its mean, say \(X_i \le \E X_i -1\) and to choose \(B\) to be all vertices \(j\in[n]\) such that \(X_j\) is significant above its mean, say \(X_j\ge \E X_j +1\). Indeed, this construction ensures that \(A\) and \(B\) are \(\Delta\)-separated for some \(\Delta\ge \Omega(1)/\log n\) (which in turn gives an \(O(\log n)\) approximation).

To improve over this first attempt, we post-process the sets \(A\) and \(B\) by iteratively removing pairs \(i\in A\) and \(j\in B\) that violate the separation condition, i.e., \(\E (X_i-X_j)^2\le \Delta\). The heart of the proof is to upper bound the number of disjoint pairs of this form. We will show that its expectation is at most \(O(n)\cdot (\Delta \cdot \sqrt{\log n})^{\Omega(1)}\). It follows that if we choose \(\Delta=c\sqrt{\log n}\) for a sufficiently small constant \(c>0\), then only a small fraction of vertices are removed in the post-processing phase in expectation.

To upper bound their expected number, we relate the above disjoint pairs to maxima of Gaussian processes defined in terms of the variables \(X_1,\ldots,X_n\). A crucial ingredient is an upper bound on the variance (and concentration) of the maximum of a Gaussian process and the fact that the Gaussian variables \(X_1,\ldots,X_n\) satisfy squared triangle inequalities \(\E (X_i-X_j)^2\le \E (X_i-X_k)^2 + \E (X_k-X_j)^2\) (because the pseudo-distribution \(\mu\) satisfies this inequality and \(X_1,\ldots,X_n\) have the same first two moments as \(\mu\)).

Region growing

Let \(G\) be a \(d\)-regular graph with vertex set \([n]\). Let \(\mu\from \bits^n\to \R\) be a degree-\(4\) pseudo-distribution. Let \(d(i,j)=\pE_{\mu(x)}(x_i-x_j)^2\) be the probability under \(\mu\) that \(i\) and \(j\) are on different sides of the bipartition. For a subset \(S\subseteq [n]\), we let \(d(i,S)=\min_{s \in S}d(i,s)\). Since the inequality \((x_i-x_j)^2 + (x_j-x_k)^2 \ge (x_i-x_k)^2\) holds over the hypercube for all \(i,j,k\in[n]\) and this inequality as a deg-4 sos proof, we have the following triangle inequality for all \(i,j,k\in [n]\) \[ \label{eq:squared-triangle-inequality} d(i,j) + d(j,k) \ge d(i,k)\,. \]

The following lemma is the main tool for extracting a set with small expansion out of a degree-4 pseudo-distribution.

It remains to show that we can always find a subset \(A\) as above for \(\Delta\ge \Omega(1/\sqrt{\log n})\). For simplicity, we first focus on the following special case,If the graph has a sparsest cut such that the smaller side has size at least \(0.2n\), we can require this inequality for the pseudo-distribution without loss of generality. Furthermore, it turns out that even the general case can be reduced to this special case. We present this reduction at the end of these notes. \[ \sum_{i,j\in [n]} d(i,j) \ge 0.1 \cdot n^2\,. \label{eq:well-spread} \] In this special case, we show that for some \(\Delta \ge \Omega(1/\sqrt{\log n})\) there exist sets \(A,B\subseteq [n]\) with \(\card{A},\card{B}\ge \Omega(n)\) such that \(d(i,j)\ge \Delta\) for all \(i\in A\) and \(j\in B\). Indeed for this choice of \(A\), the condition of the region growing lemma is satisfied, \[ \card{A} \cdot \sum_{i=1}^n d(i,A) \ge \card{A} \cdot \card{B}\cdot \Delta \ge \Omega(\Delta \cdot n^2) \ge \Omega(\Delta) \cdot \sum_{i,j\in[n]} d(i,j)\,. \] By Reference:region-growing, we obtain a \(O(1/\Delta)\le O(\sqrt{\log n})\)-approximation for the expansion of \(G\).

Structure theorem

The quadratic sampling lemma allows us to translate the task of finding sets \(A\) and \(B\) as above to a question about \(n\) jointly-distributed Gaussian variables. Without loss of generality we may assume that \(\E_{\mu(x)} x = \tfrac 12 \cdot \Ind\).The definition of expansion \eqref{eq:expansion} is symmetric in the sense that both \(x\) and its complement \(\Ind-x\) have the same value. Therefore, we can symmetrize the pseudo-distribution in the same way as for Max Cut.

Let \(X=(X_1,\ldots,X_n)\) be a Gaussian vector that matches the first two moments of \(x-\tfrac 12 \cdot \Ind\) under the pseudo-distribution \(\mu\). Then, \(X\) satisfies \(\E X_i=0\), \(\E X_i^2\le 1\), and \(\E (X_i-X_j)^2=d(i,j)\) for all \(i,j\in [n]\).

The following theorem about such Gaussian vectors shows that sets \(A\) and \(B\) as above exist and that we can find them efficiently. Together with Reference:region-growing this theorem implies Reference:arora-rao-vazirani-approximation-min-expansion in the special case that the pseudo-distribution satisfies \eqref{eq:well-spread}

It will useful to rephrase the above theorem in terms of vertex separators in certain graphs associated with the Gaussian vector \(X\). For \(\Delta>0\), let \(H\) be the directed graph with vertex set \([n]\) such that \[ E(H) = \{ (i,j)\in [n]^2 \mid d(i,j) \le \Delta\}\,. \label{eq:geometric-graph} \] We say that subsets \(A,B\subseteq [n]\) form a vertex separator if no edge of \(H\) goes directly between \(A\) and \(B\), i.e., \(E(H)\cap A\times B=\emptyset\). We say such a vertex separator is good if \(\card A \cdot \card B \ge \Omega(n^2)\). With this terminology in place, we see that in order to prove Reference:structure it is enough to show that there exists \(\Delta\ge \Omega\Paren{1/\sqrt {\log n}}\) such that \(H\) has a good vertex separator.

⊕ In this graph, the set of vertices in the middle is a vertex separator. Removing this set breaks the graph into two parts \(A\) and \(B\) that are not connected by an edge. If we added, the red edge to the graph, the set of vertices in the middle would no longer be a vertex separator.

Proof of structure theorem

Let \(X=(X_1,\ldots,X_n)\) be a centered Gaussian vector with \(\E X_i^2\le 1\) for all \(i\in[n]\). Let \(d(i,j)=\E(X_i-X_j)^2\) for all \(i,j\in [n]\). Suppose that \(d\) satisfies \eqref{eq:squared-triangle-inequality} and \eqref{eq:well-spread}. For \(\Delta>0\), let \(H\) be the graph with vertex set \([n]\) and edge set \eqref{eq:geometric-graph}.

We consider the following randomized algorithm to find vertex separators for \(H\):

1. Choose subsets \(A^0,B^0\subseteq [n]\) such that \[ A^0 = \{ i \mid X_i \le -1\} \text{ and } B^0 = \{ j \mid X_j \ge 1\}\,. \]
2. Find a maximal matching \(M\) in the edges \(E(H) \cap A^0 \times B^0\).
3. Output the sets \(A=A^0 \setminus V(M)\) and \(B=B^0 \setminus V(M)\).

Note that the objects constructed by the algorithm, in particular the sets \(A\) and \(B\) and the matching \(M\), are jointly distributed with the Gaussian vector \(X\). We emphasize that the edges of the matching \(M\) are directed. In particular, the event \((i,j)\in E\) implies that \(X_j-X_i\ge 2\).

We observe that the output \((A,B)\) of the algorithm forms a vertex separator in \(H\). Indeed, by the maximality of \(M\), every edge \((i,j)\in E(H)\cap A^0 \times B^0\) has at least one endpoint in \(V(M)\), which means that \((i,j)\) is not contained in \(A\times B\).

We also observe that if we find the maximal matching in step 2 by greedily passing over the edges in a canonical order independent of the randomness of \(X\), then for every \(x\in \R^n\), the matching produced in the event \(X=x\) is the reverse of the matching produced in the event \(X=-x\). It follows that for every vertex \(i\in [n]\), \[ \Pr\{ \text{$i$ has outgoing edge in $M$}\} = \Pr\{ \text{$i$ has incoming edge in $M$}\} \,. \]

The following lemma characterizes the success of the above algorithm in terms of the expected size of \(M\).

We will analyze the expected size of the random matching \(M\) by relating it to the maximum of a Gaussian process.We remark that the lemma only uses the triangle inequalities \eqref{eq:squared-triangle-inequality} but not inequality \eqref{eq:well-spread}.

Together Reference:vertex-separator-or-large-matching and Reference:maximum-of-gaussian-process allow us to prove Reference:structure.

It remains to prove Reference:maximum-of-gaussian-process. The proof considers the following family of Gaussian processes and relates their expected maxima in terms of the expected size of the matching \(M\). For \(i\in [n]\) and \(k\in \N\), let \(\super Y k_i\) be the maximum of the Gaussian process \(\{ X_j-X_i \mid j\in H^k(i)\}\), \[ \super Y k_i = \max_{j\in H^k(i)} X_j-X_i\,. \] Here, \(H^k(i)\) denotes the set of vertices that can be reached from \(i\) by at most \(k\) steps in the graph \(H\). Define the following potential function, \[ \Phi(k) = \sum_{i=1}^n \E \super Y k_i\,. \] Note that \(\Phi(k)\) allows us to lower bound \(\E \max_{i,j\in[n]}X_j-X_i\) because \(\Phi(k)/n \le \E \max_{i,j\in[n]}X_j-X_i\).

The following lemma is the key ingredient for the proof of Reference:maximum-of-gaussian-process.We remark that the proof of this lemma neither uses the triangle inequalities \eqref{eq:squared-triangle-inequality} nor the inequality \eqref{eq:well-spread}.

This chaining lemma directly implies Reference:maximum-of-gaussian-process.

The proof of Reference:chaining uses the following remarkable fact about the variance of maxima of Gaussian processes: The variance of the maximum of a collection of Gaussian variables is bounded by the maximum variance of a variable in the collection.In contrast, the expectation of the maximum typically depends also on the number of variables in the collection.

The proof of this inequality also shows Gaussian-like concentration around the mean. In that form it is sometimes called Borell’s inequality and follows from Gaussian concentration inequalities for Lipschitz functions (Sudakov and Cirel\('\)son 1974; Borell 1975).See this book chapter by Pollard for different proofs of this concentration inequality.

Reduction to the well-spread case

We describe now how to prove Reference:arora-rao-vazirani-approximation-min-expansion in case inequality \eqref{eq:well-spread} is not satisfied.

Recall the distance \(d(i,j)=\E_{\mu(x)}(x_i-x_j)^2\). Let \(\delta>0\) be the average distance \[ \delta=\tfrac 1 {n^2} \sum_{i,j\in[n]} d(i,j)\,. \label{eq:average-distance} \]

The following lemma shows that if there exists a cluster of radius significantly smaller than \(\delta\) that contains a constant fraction of vertices, then the condition of Reference:region-growing is satisfied for \(\Delta\ge \Omega(1)\) (which means that we get a \(O(1)\)-approximation).

The following lemma shows that if the condition of the previous lemma is not satisfied, then after restricting to a constant fraction of the vertices there are Gaussian random variables that we can apply the structure theorem to in order to obtain sets \(A,B\subseteq[n]\) with \(\card{A},\card{B}\ge \Omega(n)\) such that \(d(i,j)\ge \Omega(1/\sqrt{\log n})\cdot \delta\) for all \(i\in A\) and \(j\in B\).