% -*- mode: latex; mode: auto-fill; fill-column: 80 -*- \documentclass{article} \usepackage{bm} \input preamble \renewcommand{\norm}[1]{\mathify{\left\Vert #1 \right\Vert}} \begin{document} \lecture{13}{March 22, 2006}{Ronitt Rubinfeld}{Punyashloka Biswal} \section{Conductance} For a graph to have a small mixing time, we would like a random walk that starts within some small subset of nodes to quickly have a non-zero probability of being anywhere on the graph. To capture this idea, we define the notion of \emph{conductance} as follows: \begin{definition}[Conductance, first attempt] \label{def:cond1} Let $G = (V,E)$ be an undirected graph and $S \subset V$ be a set of nodes. Then the conductance $\Phi(S,\bar S)$ is defined as \[ \Phi(S,\bar S) = \frac{\abs E_{S,\bar S}}{\abs E_S}, \] where \begin{eqnarray*} \bar S &=& V - S, \\ E_S &=& \{ (u,v) \in E \mid u, v \in S \} \textrm{ and}\\ E_{S,\bar S} &=& \{ (u,v) \in E \mid u \in S, v \in \bar S \}. \end{eqnarray*} The conductance of the graph $\Phi_G$ is defined as \[ \Phi_G = \min_{\abs S \le \abs V/2} \Phi(S,\bar S). \] \end{definition} To see why a graph with large conductance should have a small mixing time, let $S$ be the set of `overweight' nodes $v$ such that $\pi^t_v > \tilde \pi_v$. Since $G$ has a large conductance, there are many ways for a random walker on $S$ to cross over to $\bar S$ and reduce the probability gap. In the extreme case where $\pi^t_v = 1/\abs S$ for $v \in S$ and zero otherwise, then the probability of crossing the cut is precisely the conductance $\Phi(S, \bar S)$. The definition of $\Phi_G$ restricts the mimimum to subsets $S$ of at most $\abs V/2$ vertices to make sure that our results are not skewed by overly large sets. For example, consider $S = V - \{ v \}$ when $G$ is $d$-regular: clearly, $\Phi(S,\{ v \}) = d / [(n-1)d] = 1/(n-1)$, which is very small regardless of the large-scale properties of the graph. To get around this problem, we only compute conductances between subsets that form a constant fraction of the entire graph (the choice of the value $1/2$ is arbitrary). In order to avoid this unnatural restriction, as well as to make the conductance symmetric with respect to cuts (so that $\Phi(S,\bar S) = \Phi(\bar S,S)$), we shall henceforth use a somewhat different definition: \addtocounter{theorem}{-1} % Use the old counter value in order to get a % primed number \renewcommand{\thetheorem}{\arabic{theorem}$'$} \begin{definition}[Conductance] Let $G = (V,E)$ and $S$ be defined as in definition~\ref{def:cond1}. Then the conductance of the cut $(S, \bar S)$ is defined as \[ \Phi_S = \Phi_{\bar S} = \frac{\abs{E_{S,\bar S}}\abs E}{\abs{E_S} \abs{E_{\bar S}}} \] and the graph conductance $\Phi_G$ is defined as the minimum conductance over all cuts. \end{definition} \renewcommand{\thetheorem}{\arabic{theorem}} Without loss of generality, suppose $\abs{E_S} \le \abs{E_{\bar S}}$. But $E = E_S \cup E_{\bar S}$, so that $\abs E / \abs{E_{\bar S}} \le 2$. This implies that the new definition differs from the old one by a factor of at most $2$. \begin{definition}[$\bm{\mathcal{L}_2}$-Distance] The $\mathcal{L}_2$-distance between two distributions $D_1$ and $D_2$ over a discrete set $X$ is denoted by $\norm{D_1 - D_2}_2$ and is defined as \[ \norm{D_1 - D_2}_2 = \sqrt{\sum_{x \in X} \bigl(D_1(x) - D_2(x)\bigr)^2} \] \end{definition} We are usually interested in the $\mathcal{L}_1$-distance between probability distributions, and the following lemma relates the two notions of distance: \begin{lemma} \label{lem:norms} Let $D_1$ and $D_2$ be two distributions. Then \[ \norm{D_1 - D_2}_2 \le \norm{D_1 - D_2}_1 \le \sqrt n \norm{D_1 - D_2}_2 \] \end{lemma} \begin{proof} Write $D = D_1 - D_2$ and $D(x) = D_1(x) - D_2(x)$. Then, on one hand, \[ \norm{D}_1^2 = \left( \sum \abs{D(x)} \right)^2 = \sum D(x)^2 + \sum_{x \ne y} \abs{D(x)}\abs{D(y)} \ge \sum D(x)^2 = \norm{D}_2^2. \] On the other hand, if we apply Chebychev's sum inequality to the numbers $\abs{D(x_1)}, \abs{D(x_2)}, \ldots, \abs{D(x_n)}$ and $1, 1, \ldots, 1$, then we get \[ \left( \sum_{x \in X} \abs{D(x)} \right)^2 \le n \sum_{x \in X} \abs{D(x)} ^2, \] or $\norm{D}_1^2 \le n \norm{D}_2^2$. Taking the square roots of these two inequalities, we have the result. \end{proof} The following theorem (which we shall prove in a subsequent lecture) gives a precise relationship between the conductance of a graph and the mixing time: \begin{theorem} \label{thm:mixing} Let $P$ be the transition matrix corresponding to a random walk on a graph $G$, and define $d(t) = \Vert P^t\pi_0 - \tilde\pi \Vert_2^2$ to be the square of the $L_2$-distance between the distribution after $t$ steps and the stationary distribution. Then \[ d(t) \le \left[ 1 - \frac{\Phi_G^2}{4} \right]^t d(0) \] \end{theorem} Notice that $d(0) \le 2$ for all starting distributions $\pi_0$, because \[ \Vert \pi_0 - \tilde \pi\Vert_2 \le \norm{\pi_0}_2 + \Vert\tilde\pi\Vert_2 \le \norm{\pi_0}_1 + \Vert \tilde\pi \Vert_1 = 2. \] Therefore, if we set $t = (4/\Phi_G^2) \ln (2n/\varepsilon^2)$, then \[ d(t) \le \left[ 1 - \frac{\Phi_G^2}{4} \right]^ {\frac{4}{\Phi_G^2} \ln \frac{2n}{\varepsilon^2}} \cdot 2 \le \frac{\varepsilon^2}{n} \] by theorem~\ref{thm:mixing}. We can now apply lemma~\ref{lem:norms} to translate this into an $L_1$ bound: \[ \norm{P^t\pi_0 - \tilde\pi}_1 \le \sqrt n \norm{P^t\pi_0 - \tilde\pi_1}_2 = \sqrt{nd(t)} \le \varepsilon. \] This formalizes our earlier intuition that a graph with a large conductance mixes fast. More specifically, it suffices to show that $\Phi_G = \Omega(1/\log n)$ to prove rapid mixing. In some cases, we can even show a \emph{constant} lower bound on the conductance! We shall be particularly interested in graphs that are $d$-regular for some $d$. In this case, the conductance is given by \[ \Phi_G = \min_S \frac{\abs{E_{S,\bar S}}\abs{E}}{\abs{E_S}\abs{E_{\bar S}}} = \min_S \frac{\abs{E_{S,\bar S}}d\abs V}{d \abs S d \abs{\bar S}} = \frac{1}{d} \left( \min_S \frac{\abs{E_{S,\bar S}}\abs V}{\abs S \abs{\bar S}} \right). \] The parenthetized term above has a special name: it is the \emph{edge magnification} $\mu$: \[ \mu = \min_S \frac{\abs{E_{S,\bar S}}\abs V}{\abs S \abs{\bar S}}, \] and for $d$-regular graphs, $\Phi_G = \mu/d$. One important technique for lower-bounding the conductance of a graph is the method of canonical paths, which we have already used for the hypercube. The idea is to carefully choose a set of paths between every pair of nodes, such that no edge in the graph has too many paths going through it: \begin{definition}[Congestion] Let $P = \{ p_{uv} \}$ be a set of canonical paths for a graph $G = (V,E)$, where $p_{uv}$ connects vertex $u$ to vertex $v$. Then the congestion of an edge $e \in E$ is defined as the number of paths $p \in P$ that use $e$. Also, the congestion of $G$ is defined as the maximum congestion over all edges $e$. \end{definition} The congestion of a graph can be as large as $O(n^2)$---consider, for example, the line on $n$ nodes---but for many graphs, it is possible to find a set of canonical paths that makes the congestion small. For a graph of low conductance, however, there are bottleneck edges which must be congested by \emph{any} chosen set of paths. \begin{claim} \label{clm:congestion-bound} If $G$ has congestion $\alpha n$ with respect to some set of canonical paths, then $\mu \ge 1/\alpha$. \end{claim} \begin{proof} Fix a cut $(S, \bar S)$ of $G$. Then the number of canonical paths $p_{uv}$ connecting $u \in S$ to $v \in \bar S$ is $\abs S \abs{\bar S}$. Each of these paths has to use at least one edge $e$ in the cut, i.e., $e \in E_{S,\bar S}$. By the definition of congestion, we have \begin{eqnarray*} \textrm{\# of paths crossing cut} &\leq& \sum_{e \in E_{S,\bar S}} (\textrm{\# of paths crossing $e$}) \\ &\le& \abs{E_{S,\bar S}} \max_{E_{S,\bar S}} (\textrm{\# of paths crossing $e$}) \\ \abs S \abs{\bar S} &\le& \abs{E_{S,\bar S}} \alpha n \\ \frac{\abs{E_{S,\bar S}} n}{\abs S \abs{\bar S}} &\ge& \frac{1}{\alpha} \end{eqnarray*} for all cuts $(S, \bar S)$. The edge expansion $\mu$ is the minimum value of the left hand side of the above inequality, so $\mu \ge 1/\alpha$. \end{proof} Recall that in lecture~7 (weakly learning monotone functions), we studied the conductance of the hypercube on $n = 2^N$ nodes using canonical paths. We chose paths which had the property that an edge on a path, along with $N$ additional bits (or a \emph{complementary point}), completely determined the start and end node (and therefore the path). This property, allowed us to argue that no more than $n$ distinct paths could pass through a given edge, bounding the congestion and hence the conductance. We will do something similar for the problem of uniformly generating graph matchings, which we shall address next. \section{Uniformly Generating Matchings} Given a bipartite graph $G = (V,E)$ where $m = \abs E$, we wish to generate a matching of the vertices of the graph uniformly at random.\footnote{It is possible to generate maximal and/or perfect matchings, but here we address the simpler problem of generating arbitrary matchings.} We do this by constructing a Markov chain with states corresponding to matchings and in which transitions correspond to small local changes in the matching. Given an initial matching (state) $M$, the possible transitions are defined as follows: \begin{tabbing} \hspace{5em} \= \+ \kill Pick an edge $e \in_R E$ \\ \IF{} \= $e \in M$,\\ \> \THEN{} set $M \leftarrow M - \{ e \}$ \\ \ELSE{} \IF{} $M \cup \{ e \}$ is a matching \\ \> \THEN{} set $M \leftarrow M \cup \{ e \}$ \\ \ELSE \\ \> stay put \end{tabbing} The resulting Markov chain $\mathcal M = (\mathcal S, \mathcal T)$ has the following properties: \begin{itemize} \item It is \emph{undirected}, because every transition is reversible. \item It is \emph{connected}: to get from matching $M_1$ to $M_2$: Drop all the edges in $M_1$ to get to the empty matching, and then build up $M_2$ one edge at a time. In fact, this shows that the diameter of the chain is at most $2 \abs M \le 2 \abs V / 2 = \abs V$, where $M$ is a maximal matching. \item It is \emph{non-bipartite}, because it has at least one self-loop (for example, consider starting from any maximal matching and picking an edge not in the matching). \item It is \emph{regular} with degree $m$, because for any initial matching, we can consider any of the $m$ edges of $G$ to add or remove. \end{itemize} In order to define the canonical paths on this Markov chain, we note that the symmetric difference $M_1 \oplus M_2$ of two matchings consists of a set of alternating paths and cycles. We fix an arbitrary ordering on the edges of $G$, a start edge for every possible path or cycle, and a traversal direction for every cycle. To convert $M_1$ into $M_2$, we consider the edges in $M_1 \oplus M_2$ in the order defined above. When we encounter an edge $e$, we process the entire alternating path or cycle that contains it (as shown below). We keep doing this until there are no more paths or cycles to process. \begin{itemize} \item To process a path $e_1 e_2 \ldots e_k$, we have to delete an edge before we can add a new one. Assume $e_1$ and $e_k$ both must be added. If not, we can just delete them before running the algorithm. So $k$ is odd. The algorithm is: \begin{tabbing} \hspace{5em} \= \+ \kill \IF{} \= \kill $i \leftarrow 1$\\ \WHILE{} $i \ne k$ \DO \\ \> Delete $e_{i+1}$ \\ \> Insert $e_i$ \\ \> $i \leftarrow i + 2$ \\ Insert $e_k$ \end{tabbing} \item To process a cycle $e_1 e_2 \ldots e_k e_1$, we need to be careful, because we must delete \emph{two} edges in the cycle before any insertions are possible. Assume $e_1$ must be deleted. Note that $k$ must be even. The algorithm runs as follows: \begin{tabbing} \hspace{5em} \= \+ \kill \IF{} \= \kill Delete $e_1$\\ $i \leftarrow 2$\\ \WHILE{} $i \ne k$ \DO \\ \> Delete $e_{i+1}$ \\ \> Insert $e_i$ \\ \> $i \leftarrow i + 2$ \\ Insert $e_1$ \end{tabbing} \end{itemize} Given a transition $e \in \mathcal T$, we need to find a way to bound its congestion. We shall do so by answering the question: ``what additional information do we need to reconstruct the endpoints of the path?'' For the hypercube, we found this bound in terms of a number of bits, but in this case, we don't even know how large $\mathcal S$ is. Luckily, however, claim~\ref{clm:congestion-bound}, which bounds the conductance, requires the value of the congestion to be specified as a multiple of the chain size. Therefore, we shall specify the aditional information in the form of \emph{another} matching (the complementary point) and a small number of additional bits. \begin{claim} Fix a transition $M_a \rightarrow M_b$. We can reconstruct the starting and ending states $M_1$ and $M_2$ of the canonical path if we specify the additional information $\bar M = (M_1 \oplus M_2) - M_a$. \end{claim} \begin{proof} Using the ordering on edges, we can decide which edges in $M_a$ have not yet been corrected. These edges must match $M_1$. The remaining edges of $M_1$ are given by the corrections contained in $M_a \oplus \bar M$. Similarly, we can reconstruct $M_2$ as well. \end{proof} Unfortunately, we are not quite done, because $\bar M$ might not be a matching, so that it is unsuitable as a complementary point. However, it can be shown that we can always remove at most two edges from $\bar M$ to make it into a matching. Therefore, it suffices to specify the resulting matching, along with one of $m^2$ possibilities for the two edges. This means that the edge congestion is at most $m^2\abs S$. By claim~\ref{clm:congestion-bound}, $\mu \ge 1/m^2$. We have already noted that $\mathcal M$ is $m$-regular, so that \[ \Phi_G = \frac{\mu}{m} = \frac{1/m^2}{m} = \frac{1}{m^3}. \] The number of matchings is bounded by the number of subsets of the edge set, $2^m$. Using this, we can set \[ t = \frac{4}{\Phi_G^2} \ln \frac{2\abs S}{\varepsilon^2} \le 4m^6 \ln\frac{2^{m+1}}{\varepsilon^2} = O(m^7 \ln(1/\varepsilon)) \] to get within $\varepsilon$ of the uniform distribution. Therefore, the Markov chain mixes rapidly, or in polynomial time. \end{document}