Cheeger-Alon-Milman Inequality

1 定理 #

图的Conductance\(\phi_G\)满足如下不等式： \[\frac{\lambda_{2}}{2}\leq \phi_{G}\leq \sqrt{2\lambda_{2}}\]

其中\(0=\lambda_1\leq \lambda_2\leq \dots \leq \lambda_n\)是图 G的Normalized Laplacian的特征值

2 证明 #

先证明左边的不等号：

Normalized Laplacian \(\mathcal{L}\)的最小特征值 0 对应的特征向量\(v_1=D^{\frac{1}{2}}\vec{1}\)，根据Rayleigh Quotient的性质，有： \[\lambda_2 = \min_{x\perp v_1}\frac{{x^T \mathcal{L} x}}{x^Tx} = \min_{x\perp v_1}\frac{x^T D^{-\frac{1}{2}}LD^{-\frac{1}{2}}x}{x^Tx} = \min_{D^{\frac{1}{2}}y\perp v_1}\frac{y^TLy}{y^TDy} \] 其中\(y=D^{-\frac{1}{2}}x\)

下面证明上述Rayleigh Quotient可以表达为顶点子集\(S\)的Conductance的表达式：

引理： 对任意非空集\(S \subseteq V\)，都可以构造出一个对应的\(y\)，满足\(D^{\frac{1}{2}}y\perp v_1\)，且有：

\[ \frac{y^T L y}{y^T D y} = \frac{d(V)w(\partial(S))}{d(V-S)d(S)}\]

证明：

令\(\vec{y}=\vec{1}_S - \sigma \vec{1}\)，其中\(\sigma=d(S)/d(V)\)，可以验证其满足\(D^{\frac{1}{2}}y\perp v_1\)：

\[(D^{\frac{1}{2}}y)^T D^{\frac{1}{2}}\vec{1} = \vec{1}_S^T D \vec{1} - \sigma \vec{1}^T D \vec{1} = d(S) - \frac{d(S)}{d(V)}d(V) = 0\]

剩下的证明只要计算上述等式成立即可：

根据Laplacian and Quadratic Form的定义，分子：

\[y^T L y = \sum_{(a,b) \in E} \left[(\vec{1}_S(a)-\sigma)-(\vec{1}_S(b)-\sigma)\right]^2 = \sum_{(a,b) \in E} (\vec{1}_S(a)-\vec{1}_S(b))^2 = | \partial(S) |\]

分母：

\[\begin{align} y^T D y &= \vec{1}_S^T D \vec{1}_S - \sigma \vec{1}_S^T D \vec{1} - \sigma \vec{1}^T D \vec{1}_S + \sigma^2 \vec{1}^T D \vec{1} \\ &= d(S) - 2\sigma d(S) - \sigma^2 d(V) \\ &= d(S)(1-\sigma) \\ &= d(S)\frac{d(V)-d(S)}{d(V)} \\ &= \frac{d(S)d(V-S)}{d(V)} \end{align}\]

所以等式成立。

由引理可得，\(\lambda_2 \leq \frac{d(V)w(\partial(S))}{d(V-S)d(S)}\)

因为\(d(V) = d(V-S) + d(S)\)，所以\(d(V) \leq 2\max (d(V-S), d(S))\) 分情况讨论可得：

\[\lambda_2 \leq 2 \frac{w(\partial(S))}{\min (d(S),d(V-S))} =2\phi(S)\]

上式对任意\(S\)都成立，所以最小化右边后仍成立： \[\frac{\lambda_{2}}{2}\leq \phi_{G}\]

下面证明右边的不等号，只需证明存在一个\(S \subseteq V\)，使得\(\phi(S) \leq \sqrt{2\lambda_2} = \sqrt{2\min_{D^{\frac{1}{2}}y\perp v_1}\frac{y^TLy}{y^TDy}}\)

思路是，证明对任意一个\(y\)，都能构造出一个\(S\),使得\(\phi(S)\)较小，即如下引理：

引理：对任意\(y \in \RR^V\)，可以找到一个\(S \subseteq \text{supp}(y)\)使得\(\frac{w(\partial(S_t))}{d(S_t)}\leq \sqrt{2R(y)}\)

其中\(\text{supp}(y)=\{i \in V | y_i \neq 0\}\)是\(y\)的 support，\(R(y)\)是 generalized Rayleigh Quotient\(\frac{y^T L y}{y^T D y} = \frac{\sum_{(i,j)\in E} w_{i,j}(y_i-y_j)^2}{\sum_{i \in V}d(i)y_i^2}\)。

证明：

因为\(R(cy)=R(y), c \in \RR, c\neq 0\)，所以可以任意缩放\(y\)，不失一般性，考虑\(\forall i, |y_i|\leq 1\)

另外可以假设\(y_i\)是有序的，因为可以重新给顶点标号。

要从\(y\)的 support 中选出一个子集，所用的方法是设置一个阈值\(t \in \RR \)，选出的子集是\(S_t = \left\{ i \in V \mid y_i^2>t \right\}\)，其中的平方是用来凑出\(R(y)\)的。

均匀随机地选\(t \in [0,1]\)，考虑期望\(\E_t[w(\partial(S_t))]\)和\(\E_t[d(S_t)]\)

\[ \begin{align} \E_t[w(\partial(S_t))] &= \E_t \left[ \sum_{(i,j) \in \partial(S_t)}w_{i,j} \right] =\E_t \left[ \sum_{(i,j) \in E} \1[(i,j) \in \partial(S_t)] w_{i,j} \right] = \sum_{(i,j) \in E} w_{i,j} \E_t \left[ \1{(i,j) \in \partial(S_t)} \right] \\ &= \sum_{(i,j)\in E} w_{i,j} (y_j^2-y_i^2) \text{ assuming } y_i^2\leq y_j^2 \\ &= \sum_{(i,j)\in E} w_{i,j} (y_j-y_i)(y_j+y_i) \leq \sqrt{\sum_{(i,j)\in E} w_{i,j}(y_j-y_i)^2}\sqrt{\sum_{(i,j)\in E} w_{i,j}(y_j+y_i)^2} \end{align}\]

最后的不等式是Cauchy–Schwarz Inequality。第一个平方根下的项就是\(R(y)\)的分子，第二个平方跟下的项是：

\[\sum_{(i,j)\in E} w_{i,j}(y_j+y_i)^2 \leq \sum_{(i,j)\in E} w_{i,j}2(y_j^2+y_i^2)= 2\sum_{i \in V} \sum_{j: (i,j)\in E} w_{i,j} y_i^2 =2\sum_{i \in V} d(i)y_i^2\]

最终得到：

\[\E_t[w(\partial(S_t))] \leq \sqrt{\sum_{(i,j)\in E} w_{i,j}(y_j-y_i)^2}\sqrt{2\sum_{i \in V} d(i)y_i^2}\]

再计算另一个期望：

\[\E_t[d(S_t)] = \E_t \left[ \sum_{i \in S_t} d(i) \right] = \E_t \left[ \sum_{i \in V} \1[i \in S_t]d(i) \right] = \sum_{i \in V} d(i) \E_t [\1{i \in S_t}] = \sum_{i \in V} d(i) y_i^2\]

得到两个期望的比值：

\[\frac{\E_t[w(\partial(S_t))]}{\E_t[d(S_t)]} \leq \sqrt{2R(y)}\]

下面证明，一定存在某个\(t=t_{*}\)，使得\(\frac{w(\partial(S_{t_{*}}))}{d(S_{t_{*}})}\leq \sqrt{2R(y)}\)

引理： 令\(f,g\)为任意实值可积函数，一定存在\(t_{*}\)使得：

\[\frac{f(t_{*})}{g(t_{*})}\leq \frac{\E_t[f(t)]}{\E_t[g(t)]}\]

证明：

令\(C=\frac{\E_t[f(t)]}{\E_t[g(t)]}\)，所以：

\[0=\E_t[f(t)]-C\E_t[g(t)] = \E_t[f(t)-Cg(t)]\]

所以一定存在\(t=t_{*}\)使得\(f(t_{*})-Cg(t_{*})\leq 0\)，否则上式不可能为 0，所以：

\[\frac{f(t_{*})}{g(t_{*})}\leq C= \frac{\E_t[f(t)]}{\E_t[g(t)]}\]

（这里的不等号似乎需要\(g(t_{*})>0\)的条件才行，这个引理可能不太严谨。但我们要算的\(d(S)\)确实是正的。）

证毕。

这个引理实际上描述了一个找\(S_{t_{*}}\)的算法：尝试所有能导致不同\(S_t\)的\(t\)，选出\(\frac{w(\partial(S_t)))}{d(S_t)}\)最小的那个。

注意，上述引理并没有证明我们想要的，即存在一个\(S\)使得\(\phi(S) \leq \sqrt{2\lambda_2}\)，只证明了\(\frac{w(\partial(S))}{d(S)}\leq \sqrt{2R(y)}\)，在Conductance的定义中，需要保证\(d(S)\leq d(V-S)\)，否则可以选择\(S=V\)

同时，我们还没有利用\(D^{\frac{1}{2}}y\perp v_1\)的条件，这个条件等价于\(0=(D^{\frac{1}{2}}y)^T D^{\frac{1}{2}} \vec{1} = y^T D \vec{1} = \sum_{i \in V} d(i)y_i\)

下面想办法构造顶点子集，满足\(d(S)\leq d(V-S)\)的条件。

对于\(R(y)=\frac{\sum_{(i,j)\in E} w_{i,j}(y_i-y_j)^2}{\sum_{i \in V}d(i)y_i^2}\)，如果\(y\)的每一个元素都加一个常数\(c\)，显然分子不变。下面证明分母一定会变大：

令\(z=y+c \vec{1}\)，分母变成了：

\[\sum_{i \in V} d(i)z_i^2 = \sum_{i \in V} d(i)(y_i+c)^2\]

跟原来的分母求差值：

\[\sum_{i \in V} d(i)(y_i+c)^2-\sum_{i \in V}d(i)y_i^2 = 2c\sum_{i\in V}d(i)y_i+\sum_{i\in V}d(i)c^2 = \sum_{i\in V}d(i)c^2 \geq 0\]

最后一个等号利用了刚刚没用到的正交条件。

不失一般性，假设\(y_1\leq \dots \leq y_n\)，选取一个最小的\(j\)，使得\(\sum_{1\leq i\leq j}d(i)\geq \frac{d(V)}{2}\)。然后令\(c=-y_j\)，得到\(z=y-y_j \vec{1}\)，所以有\(R(z)\leq R(y)\)（把 y 换成 z 后，分子不变，分母变大）。

由于\(z_j=0\)，所以不算点\(j\)，点集\(V\)被分成两组：\(S_- = \left\{ i\in V \mid y_i<y_j \right\}=\left\{ i\in V \mid z_i<0 \right\}\)和：\(S_+ = \left\{ i\in V \mid y_i>y_j \right\}=\left\{ i\in V \mid z_i>0 \right\}\)。它们都只包含至多一半的\(d(V)\)，这便构造出了满足我们需要的点集。

下面定义两个向量\(z_-, z_+\)，且令他们的 support 比\(z\)“少”：

\[\begin{align*} &z_-=\begin{cases} z_i& \text{ if } z_i<0\\ 0& \text{ otherwise.} \end{cases} &\text{ and} \;\;\;\;\; z_+=\begin{cases} z_i& \text{ if } z_i>0\\ 0& \text{ otherwise.} \end{cases} \end{align*} \]

若使用上面证明的引理分别施加在这两个向量上，由于找出来的子集\(S_{t_{*}}\)是向量的 support 的子集，所以分别一定是\(S_{-}\)和\(S_+\)的子集，满足我们的需求。

最后一步，就是证明\(\min \left\{R(z_-),R(z_+)\right\}\leq R(y)\)，只要证明如下引理：

引理：\(\min \left\{ R(z_-),R(z_+) \right\}\leq R(z)\)

证明：

\(z^T D z = z_+^T D z_+ + z_-^T D z_-\)，因为左边为\(\sum_{i \in V} d(i)z_i^2\)，右边\(z_-, z_+\)只是将\(z_i\)为零的项去掉了，值不变。

\(z^T L z \geq z_+^T L z_+ + z_-^T L z_-\)，因为左边为\(\sum_{(i,j)\in E} w_{i,j}(z_i-z_j)^2\)，右边：\(\sum_{(i,j)\in E} w_{i,j} \left[ (z_{+i}-z_{+j})^2 + (z_{-i}-z_{-j})^2 \right]\)，对于每条边\((i,j)\in E\)，如果\(z_i, z_j\)异号，则\((z_i-z_j)^2 = (z_{+i}-z_{+j})^2 + (z_{-i}-z_{-j})^2\)，如果同号，则\((z_{+i}-z_{+j})^2 + (z_{-i}-z_{-j})^2 = 0\)

所以有\[\frac{z_+^T L z_+ + z_-^T L z_-}{z_+^T D z_+ + z_-^T D z_-}\leq \frac{z^T L z}{z^T D z} = R(z)\]

又因为\[\min\left\{\frac{A}{B}, \frac{B}{D} \right\} \leq \frac{A+B}{C+D}\]，得到：\[\min \left\{ R(z_-),R(z_+) \right\}\leq R(z) \]

最终，整个证明思路是，对任意满足正交条件的\(y\)，首先将其成变换成\(z = y-y_j \vec{1}\)，然后根据构造出的\(z_-, z_+\)利用引理找到合适的顶点子集。综合以上的结论得到，这个顶点子集的Conductance小于等于\(R(y)\)

证毕。

---