# Mixing properties of random walks on graphs

I have a question about this paper (not behind a pay wall) on the Cheeger inequality for graphs.

One of the main ideas of the paper is that random walks on graphs can be used to find sets with small isoperimetric ratio. The principle seems to be as follows: if a vertex $v$ is well connected to a neighborhood of a vertex $u$, then a random walk starting at $u$ will visit $v$ more often than you would expect from looking at the degree of $v$ alone.

This principle is made precise and quantitative via various mixing estimates in the paper. I want to ask about one specific mixing result (Lemma 4 of secton 6), though my question may apply to the others as well. First, the notation:

• $S$ is a set of vertices in an undirected graph $G$
• $W$ is the lazy random walk matrix of $G$: $W = \frac{1}{2}(I + D^{-1}A)$ where $D$ is the degree matrix and $A$ is the adjacency matrix
• $pr_u$ is a personalized PageRank vector associated to a vertex $u$ with parameter $c$; it is the unique solution to the equation $$pr_u = c \chi_u + (1-c)pr_u W$$ where $\chi_u$ is the characteristic function of $u$
• $\pi$ is the function defined on the vertex set of $G$ which assigns to each vertex $v$ the degree of $v$ divided by $vol(G)$.
• $\gamma_u$ is the smallest isoperimetric ratio obtained by a sweep over $pr_u$ (see section 4 of the paper)

The mixing result is: $$\left| \frac{pr_u(S) - \pi(S)}{1 - \pi(S)} \right| \leq 1 - (1-c)^k + \sqrt{\frac{vol(S)}{d_u}}\left(1 - \frac{\gamma_u^2}{8}\right)(1-c)^k$$

One of the key steps in the proof of this mixing result is the estimate: $$f(x) \leq c + (1-c)fW(x)$$ where $f = \frac{pr_u - \pi}{1 - \pi}$ and $0 \leq x \leq vol(G)/2$ (see section 4 for the definition). However, this estimate is not proved in the paper, and I have serious doubts that it is true (which I can share if desired).

First question: Can anyone prove this estimate, or confirm that it is incorrect?

However, I believe I can prove the estimate for $f = pr_u$. Moreover, I think that this is enough to prove the mixing lemma with $pr_u(S)$ instead of $\frac{pr_u(S) - \pi(S)}{1 - \pi(S)}$ on the left-hand side, and this in turn is enough to prove Theorem 4 in section 6 (with a different constant, though I think the constant in the paper is wrong either way). But I am suspicious of this because it seems inconsistent in spirit with a variety of other results (including two other mixing results in the paper).

Second question: Can anyone explain why $\frac{pr_u - \pi}{1 - \pi}$ instead of just $pr_u$ in the statement of Lemma 4 is necessary (either to prove Lemma 4 or Theorem 3)?

This question is already very long, so I will keep this edit brief. In an effort to understand what is going on, I looked at the corresponding results for random walks rather than PageRank vectors (Lemma 3 and Theorem 2 in the paper above). Again, everything seems to work out without the need for the distribution $\pi$. Lemma 3 is the estimate: $$|f_k(S)| \leq \sqrt{\frac{vol(S)}{d_u}} \left(1-\frac{\beta_k^2}{8}\right)^k$$ where $f_k = \chi_u W^k - \pi$.

Again, let us replace $f_k$ with simply $\chi_u W^k$. If $u \in S$ then $f_0(S) = 1$ and the right-hand side is $\sqrt{\frac{vol(S)}{d_u}} \geq 1$. If $u \notin S$ then $f_0(S) = 0$ and the right-hand side is nonnegative. The inductive step only uses the fact that $f_{k+1} = f_k W$, which is still true. As far as I can tell the proof of Theorem 2 still works exactly the same way without $\pi$ (as long as Lemma 3 is true), so I again don't see why it is there.

• At the request of the OP, the bounty has been refunded and the question will be migrated. – Todd Trimble Jul 2 '14 at 19:11
• this is a totally decent question & personally like/encourage the use of se to delve into paper details (even though it is a generally rare/tricky use) ... however suggest just emailing the author 1st, she might be able to quickly comment/resolve the question, and it virtually qualifies as helpful/very detailed peer review anyway. also if you give lots of page refs to the formulas/sections, that would be helpful. (& if you find anything out plz update this page as a public service with either comments or maybe even an answer.) – vzn Jul 4 '14 at 1:02
• Indeed, my first attempt to get an answer was to email the author, but so far iI have not received a response. I will post an update if this changes. – Paul Siegel Jul 4 '14 at 2:08
• find her "defn" of $f(n)$ p8 too abstract/hard to follow (there does not actually seem to be a defn) & other aspects of the paper not self-contained esp for "outsiders". anyway she seems to be choosing a $f(n)$ such that the choice is sufficient to lead to a proof of Lemma 4 p13...? suggest further Theoretical Computer Science Chat – vzn Jul 4 '14 at 3:04
• I have to admit that the details of the paper are not very user-friendly. I wrote up some notes available at www.math.columbia.edu/~siegel/Spectral Clustering.pdf which go into a bit more detail on the background; if anybody feels motivated to really dive into this question, this may help. The relevant material starts in section 5. – Paul Siegel Jul 4 '14 at 12:21