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.
