<p>I have a question about <a href="http://www.math.pku.edu.cn/teachers/yaoy/Fall2011/cheeger_chung.pdf">this paper</a> (not behind a pay wall) on the Cheeger inequality for graphs. </p>

<p>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.</p>

<p>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:</p>

<ul>
<li>$S$ is a set of vertices in an undirected graph $G$</li>
<li>$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</li>
<li>$pr_u$ is a <em>personalized PageRank vector</em> 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$</li>
<li>$\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)$.</li>
<li>$\gamma_u$ is the smallest isoperimetric ratio obtained by a sweep over $pr_u$ (see section 4 of the paper)</li>
</ul>

<p>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$$</p>

<p>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).</p>

<blockquote>
  <p>First question: Can anyone prove this estimate, or confirm that it is incorrect?</p>
</blockquote>

<p>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).</p>

<blockquote>
  <p>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)?</p>
</blockquote>

<hr>

<p>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$.  </p>

<p>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.</p>

CC BY-SA 3.0
2014-07-04T01:02:56.233Z
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
CC BY-SA 3.0
2014-07-04T02:08:28.323Z
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
CC BY-SA 3.0
2014-07-04T03:04:27.470Z
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 [chat]
vzn
CC BY-SA 3.0
2014-07-04T12:21:26.483Z
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
CC BY-SA 3.0
2014-07-04T18:39:01.173Z
ok. further delving into this. the basic issue seems to be that Chung has a tighter bound than you feel you can prove. but Chung _fully proves_ the bound given, not once but _twice,_ getting the same bound via two different methods, one cited in an earlier paper, and the 2nd in the paper you cite via different means. her tighter bound is not _necessary,_ it is _sufficient_ as is your "looser" bound. her proof shows the _selection_ of the tighter lower bound is _sufficient_. seems concept of "necessary" here would refer to _tightest possible_ lower bounds. do you see any actual _contradiction?_
vzn
CC BY-SA 3.0
2014-07-04T20:18:06.530Z
My first question asks if she has really proven her tighter bound: her argument, at least in this paper, requires the estimate $f(x) \leq c + (1-c)fW(x)$ for $f = \frac{pr_u - \pi}{1 - \pi}$.  But ultimately I believe the final result (Theorem 3) can be proved using the looser bound (maybe with a slightly different constant), and in that sense I am not claiming that there is anything seriously wrong.
Paul Siegel
CC BY-SA 3.0
2014-07-04T20:18:45.303Z
However, I am suspicious of my own claim that the looser bound is sufficient, because these sorts of results seem to always be proved using a tighter bound.  This is what my second question is about.
Paul Siegel
<graph-theory>
Mixing properties of random walks on graphs
Paul Siegel
# Mixing properties of random walks on graphs

(Asked by: username_0 on 2014-06-28)

I have a question about [this paper](http://www.math.pku.edu.cn/teachers/yaoy/Fall2011/cheeger_chung.pdf) (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.

**Tags:** graph-theory

> **Comments:**
> **username_1**: 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.)  
> **username_0**: 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.  
> **username_1**: 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 [chat]  
> **username_0**: 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.  
> **username_1**: ok. further delving into this. the basic issue seems to be that Chung has a tighter bound than you feel you can prove. but Chung _fully proves_ the bound given, not once but _twice,_ getting the same bound via two different methods, one cited in an earlier paper, and the 2nd in the paper you cite via different means. her tighter bound is not _necessary,_ it is _sufficient_ as is your "looser" bound. her proof shows the _selection_ of the tighter lower bound is _sufficient_. seems concept of "necessary" here would refer to _tightest possible_ lower bounds. do you see any actual _contradiction?_  
> **username_0**: My first question asks if she has really proven her tighter bound: her argument, at least in this paper, requires the estimate $f(x) \leq c + (1-c)fW(x)$ for $f = \frac{pr_u - \pi}{1 - \pi}$.  But ultimately I believe the final result (Theorem 3) can be proved using the looser bound (maybe with a slightly different constant), and in that sense I am not claiming that there is anything seriously wrong.  
> **username_0**: However, I am suspicious of my own claim that the looser bound is sufficient, because these sorts of results seem to always be proved using a tighter bound.  This is what my second question is about.  

---

## 0 answers

