Spectral and Algebraic Graph Theory Ch16 - The Lovàsz-Simonovits Approach to Random Walks

本期专栏为 “谱图理论” 系列的第16期，将介绍耶鲁大学教授、两届哥德尔奖得主 Daniel A. Spielman 所著图书 《Spectral and Algebraic Graph Theory》 电子版链接 第十六章 The Lovàsz - Simonovits Approach to Random Walks 中的内容。

本期作者 | 丁海鹏，中国人民大学高瓴人工智能学院

16.1 引入

在介绍本章内容之前，首先引入一个新定义。对于向量 \(\mathbf{f}\) 和整数 \(k\)，定义 \(\mathbf{f}\{k\}\) 为 \(\mathbf{f}\) 中最大的 \(k\) 个分量的和。特别地，\(\mathbf{f}\{0\}=0\). 若写成更严格的符号化定义，对于 \(n\) 维向量 \(\mathbf{f}\)，构造排列 \(\pi\) 使得

\[\mathbf{f}(\pi(1))\ge\mathbf{f}(\pi(2))\ge...\ge\mathbf{f}(\pi(n)),\]

那么我们有

\[\mathbf{f}\{k\}=\sum_{i=1}^k\mathbf{f}(\pi(i)).\]

对于 \(x\in[0,n],x\in \mathbb{R}\backslash \mathbb{Z}\)，我们进一步定义若 \(x\in[k,k+1],k\in\mathbb{Z}\)，那么

\[\mathbf{f}\{x\}=(x-k)\mathbf{f}\{k\}+(k+1-x)\mathbf{f}\{k+1\}.\]

直观地看，\(\mathbf{f}\{x\}\) 图像是一条折线，转折点在横轴为整数的位置上，第\(k\)条折线的斜率恰好为向量 \(\mathbf{f}\) 第 \(k\) 大的值。折线段的斜率是单调不增的，这意味着 \(\mathbf{f}\{x\}\)是上凸的。

接下来，我们将要证明 Lovàsz - Simonovits Theorem.

Theorem 16.1.1 令 \(W\) 为一个 \(d\)-正则图 \(G=(V,E)\) 的懒惰随机游走矩阵，衰减因子为 0.5，传导率至少为 \(\phi\). 令 \(\mathbf{g}=W\mathbf{f}\)，那么对于所有 \(0\le k\le n\) 的整数 \(k\)，我们有结论

\[\mathbf{g}\{k\}\le\frac{1}{2}(\mathbf{f}\{k-\phi h\}+\mathbf{f}\{k+\phi h\}),\]

其中 \(h=\min(k,n-k)\).

remark

1. 向量 \(\mathbf{f}\) 的每一维分量，描述了图中所对应节点的信号（也许是下文将要提到的随机游走概率）。
2. 该定理可以推广到非正则权重图。为了方便简洁地体现思想，这里仅证明无权正则图的情况。

3. 我们可以使用该定理来界定图上随机游走的收敛速度。令 \(\mathbf{p}_t\) 为图进行了 \(t\) 步随机游走后的概率分布，并绘制曲线 \(\mathbf{p}_t\{x\}\). 该定理告诉我们，随着随机游走步数的提升，曲线将逐渐下移，并一定会落在上条曲线一些 弦 的下方，以描述收敛的速度。不等式的右侧就描述了这样一条弦。

   直观地看，传导率越大，随机游走收敛至稳态应当越快，那么每一步随机游走产生的曲线应该更靠下，在上一条曲线一条更宽的弦下方。

4. 我们将使用该定理证明 Cheeger’s inequality 奇格不等式。

16.2 定义与基本结论

Claim 16.2.1 令 \(h(x)\) 为一上凸函数，且 \(z > y > 0\). 那么，

\[\frac{1}{2}(h(x-z)+h(x+z))\le \frac{1}{2}(h(x-y)+h(x+y))\]

这描述了上凸函数图像中两条弦的位置关系，可以通过上凸函数的性质轻松推导得到。

Claim 16.2.2 令 \(\mathbf{f}\) 是一个向量，\(k\in[0,n]\)，\(\alpha_1,...,\alpha_n\in[0,1]\) 且满足

\[\sum_i \alpha_i=k.\]

那么，

\[\sum_i\alpha_i\mathrm{f}\{i\}\le\mathrm{f}\{k\}.\]

若 \(k=0\)，上述不等式等号成立。否则，将不等式两边同时除以 \(k\)，则不等式左式描述了一个向量各分量的加权平均，且权重均不超过\(1/k\)。该加权平均值一定不高于权重为 \(1/k\) 的最大 \(k\) 个值求和，这很显然。

在本章中，我们只考虑正则图上的懒惰随机游走，每一步游走停留的概率为 0.5. 对于一个节点集合 \(S\) 和节点 \(\alpha\)，定义\(\gamma(\alpha,S)\) 为 \(\alpha\) 经过一步随机游走后停留在 \(S\) 中的概率。

1. 若 \(\alpha\in S\)，那么该概率等于自身不动的概率0.5，加上其邻居在 \(S\) 之中的比例的一半（因为只有一半的概率会移动）。
2. 若 \(\alpha\in S\)，相似地，该概率等于其邻居在 \(S\) 之中的比例的一半。

16.3 热身

我们将首先证明，对于进行 \(t\) 步后的随机游走，\(\mathbf{p}_t\{x\}\) 的曲线一定在 \(t-1\) 步所对应的曲线之下。

首先我们定义，对于向量 \(\mathbf{f}\) 与点集 \(S\)，有

\[\mathbf{f}(S)=\sum_{a\in S}\mathbf{f}(a).\]

很明显，对于所有定义内的整数 \(k\) ，均存在至少一个对应大小为 \(k\) 的点集 \(S\) 使得

\[\mathbf{f}(S)=\mathbf{f}\{k\}.\]

若 \(f\) 的各分量值唯一，那么对应整数 \(k\) 的点集 \(S\) 唯一。

Lemma 16.3.1 令 \(\mathbf{f}\) 为一向量且 \(\mathbf{g}=W\mathbf{f}\)，那么对于任意的 \(x\in[0,n]\)，

\[\mathbf{g}\{x\}\le\mathbf{f}\{x\}，\]

其中 \(W\) 为提到的懒惰随机游走转移矩阵。

Proof Lemma 16.3.1 由于 \(\mathbf{g}\{x\}\)为一分段一次函数，我们只需要证明分段节点处函数值满足条件即可。令 \(k\) 为一整数且 \(S\) 为满足 \(\mathbf{f}(S)=\mathbf{f}\{k\}\) 的点集。那么由 \(\mathbf{g}=W\mathbf{f}\)，

\[\mathbf{g}(S)=\sum_{a\in V}\gamma(a,S)\mathbf{f}(a).\]

又图为正则图，那么

\[\sum_{a\in V}\gamma(a,S)=k.\]

那么，根据 Claim 16.2.2，\(\mathbf{g}(S)\) 可以被描述为上式形式，则一定有

\[\sum_{a\in V}\gamma(a,S)\mathbf{f}(a)\le\mathbf{f}\{k\}.\]

16.4 定理证明

回顾在一 \(d\)-正则图上关于点集 \(S\) 的传导率 \(\phi(S)\) 的定义有：

\[\phi(S) \overset{\text{def}}{=} \frac{\vert\partial(S)\vert}{d\min(\vert S\vert,n-\vert S\vert)},\]

其中 \(\partial(S)\) 表示了点集 \(S\) 向外连边的数量。

传导率描述了一个点集 \(S\) 与图剩余部分的连接情况。若传导率越大，则连接越紧密。相应地，两个点集通过随机游走的交流也就越密切。对本章主定理的证明需要我们更深入地分析传导率。

Lemma 16.4.1 令 \(S\) 为一大小为 \(k\) 的点集，那么：

\[\sum_{a\notin S}\gamma(a,S)=\frac{\phi(S)}{2}\min(k,n-k).\]

Proof of Lemma 16.4.1 对于 \(a\notin S\)，\(\gamma(a,S)\) 即从 \(a\) 连接到点集 \(S\) 的边数比例的一半。这样，从点集 \(S\) 向外连边的数量即为

\[\sum_{a\notin S}2\gamma(a,s)d=\vert\partial(S)\vert=d\phi(S)\min(k,n-k)。\]

故引理得证。

Lemma 16.4.2 令 \(W\) 为一 \(d\)-正则图上的懒惰随机游走转移矩阵，\(\mathbf{g}=W\mathbf{f}\). 对于任意大小为 \(k\)，传导率至少为 \(\phi\) 的点集 \(S\)，有

\[\mathbf{g}(S)\le \frac{1}{2}(\mathbf{f}\{k-\phi h\}+\mathbf{f}\{k+\phi h\}),\]

其中 \(h=\min(k,n-k)\)

Remark

方便起见，下证明中，我们用 \(\gamma(a)\) 代替 \(\gamma(a,S)\).

Proof of Lemam 16.4.2 为了证明该引理，我们将分析并变形如下公式：

\[\mathbf{g}(S)=\sum_{a\in V}\gamma(a)\mathbf{f}(a).\]

我们进行如下定义：

\[\alpha(a)= \begin{cases} \gamma(a)-1/2 & \mathrm{if}\ a\in S\\ 0 & \mathrm{if}\ a\notin S \end{cases} \quad \mathrm{and} \quad \beta(a)= \begin{cases} 1/2 & \mathrm{if}\ a\in S\\ \gamma(a) & \mathrm{if}\ a\notin S \end{cases}.\]

也就是说，\(\alpha(a)+\beta(a)=\gamma(a)\)，故

\[\mathrm{g}(S)=\sum_{a\in V}\alpha(a)\mathbf{f}(a)+\sum_{a\in V}\beta(a)\mathbf{f}(a).\]

在这一步，我们将懒惰随机游走的“懒惰性”分离了出来。显然，\(0\le \alpha(a)\le 1/2,0\le\beta(a)\le 1/2\). 因此，我们可以简单地将 \(\mathbf{f}(a)\) 系数限制在 \((0,1)\) 之间，如

\[\sum_{a\in V}\alpha(a)\mathbf{f}(a)=\frac{1}{2}\sum_{a\in V}2\alpha(a)\mathbf{f}(a), \quad \mathrm{and}\quad \sum_{a\in V}\beta(a)\mathbf{f}(a)=\frac{1}{2}\sum_{a\in V}2\beta(a)\mathbf{f}(a).\]

又计算所有 \(\beta(a)\) 的和，可以分别计算 \(S\) 内的点与图中其他的点，我们有

\[\sum_{a\in V}\beta(a)=\frac{k}{2}+\sum_{a\notin S}\gamma(a).\]

方便起见，记

\[z = \sum_{a\notin S}\gamma(a),\]

于是我们有

\[\sum_{a\in V}(2\alpha(a))=k-2z,\quad \mathrm{and} \quad \sum_{a\in V}(2\alpha(a))=k+2z.\]

由 Lemma 16.4.1，\(z\ge\phi h/2\).

由 Claim 16.2.2,

\[\mathbf g(S)\le \frac{1}{2}(\mathbf f\{k-z\}+\mathbf f\{k+z\}).\]

由 Claim 16.2.1,

\[\mathbf g(S)\le \frac{1}{2}(\mathbf f\{k-\phi h\}+\mathbf f\{k+\phi h\}).\]

Proof of Theorem 16.1.1 对于 \([0,n]\) 中的所有整数 \(k\), 我们找到所有点集 \(\mathbf f(S)=\mathbf f\{k\}\)，并分别应用Lemma 16.4.2，则定理得证。

16.5 安德森对于奇格不等式的证明

该证明将利用 Lovàsz - Simonovits Approach. 同样地，为了更简洁地描述思想，该证明建立在 \(d\)-无权正则图上。如读者有兴趣，可以自行将证明推广至非正则权重图上，这是可以做到的。

Theorem 16.5.1 令 \(G\) 为一 \(d\)-正则图，其懒惰随机游走转移矩阵为 \(W\), 并令 \(\omega_2=1-\lambda\) 为矩阵 \(W\) 的次大特征值。那么，存在一个点集 \(S\) 使得 \(\phi(S)\le\sqrt{8\lambda}\).

Proof of Theorem 16.5.1 令 \(\omega_2\) 对应的特征向量为 \(\psi\). 由前面的知识我们知道，\(\psi\) 每个分量都为相同常数的向量正交，即 \(\psi\{n\}=0\). 定义

\[k=\arg \max_{0\le k\le n}\frac{\psi\{k\}}{\sqrt {\min(k,n-k)}}.\]

与此同时，记上式可取得的最大值为

\[\gamma=\max_{0\le k\le n}\frac{\psi\{k\}}{\sqrt{\min(k,n-k)}}.\]

不失一般性地，我们令 \(k\le n/2\). 对于 \(k>n/2\) 的情况，我们可以对特征向量 \(\psi\) 取反，使得 \(\gamma\) 不变，但转化 \(k<n/2\). 此时，\(\psi\{k\}=\gamma\sqrt{k}\). 对于其他任意的 \(k'\)，均有 \(\psi\{k'\}\le\gamma\sqrt k'\).

又 \(\psi\) 具有正特征值，那么

\[(W\psi)(S)=W\psi\{k\},\] \[(W\psi)(S)=(1-\lambda)\psi(S)=(1-\lambda)\gamma\sqrt{k}.\]

令 \(\phi\) 为 点集 \(S\) 的传导率。根据 Lemma 16.4.2，我们有

\[(W\psi)(S)\le\frac{1}{2}(\psi\{k-\phi k\}+\psi\{k+\phi k\}).\]

根据上侧的构造，上式右侧可以被限制为

\[\begin{aligned} (1-\lambda)\gamma\sqrt{k} = &(W\psi)(S)\\ \le & \frac{1}{2}(\psi\{k-\phi k\}+\psi\{k+\phi k\})\\ \le & \frac{1}{2}\left(\gamma\sqrt{k-\phi k}+\gamma\sqrt{k+\phi k}\right)\\ = & \frac{1}{2}\gamma\sqrt k\left(\sqrt{1-\phi}+\sqrt{1+\phi}\right). \end{aligned}\]

故上式可化简为

\[(1-\lambda)\le\frac{1}{2}\left(\sqrt{1-\phi}+\sqrt{1+\phi}\right).\]

对右式应用泰勒展开，容易得到

\[\frac{1}{2}\left(\sqrt{1-\phi}+\sqrt{1+\phi}\right)\le 1-\frac{\phi^2}{8},\]

即 \(\lambda \ge \phi^2/8, \phi(S)\le\sqrt{8\lambda}\).