on
Spectral Graph Theory
Lecture notes that I scribbled for CSCI5160: Approximation Algorithms (2021 Spring) taught by Prof. Siu On CHAN at CUHK.
The textbooks are Convex Optimization by Stephen Boyd and Lieven Vandenberghe, Approximation Algorithms and Semidefinite Programming by Bernd Gärtner and Jiri Matousek and Spectral and Algebraic Graph Theory by Daniel A. Spielman.
Course website: https://www.cse.cuhk.edu.hk/~siuon/csci5160-s21/
1 “Spectral”这个名字的由来 #
Spectral Graph Theory 中的 Spectral 到底指什么？
根据维基百科：https://en.wikipedia.org/wiki/Spectral_theory
希尔伯特在建立他的希尔伯特空间理论时最早使用了这个名字，但当时他完全是出于纯数学的角度。后来这个理论真的可以用来计算原子光谱（atomic spectra），希尔伯特也很吃惊，因为他起名字的时候完全没有考虑实际应用。但总之这个名字就沿用了下来，矩阵的特征分解也叫做谱分解（Spectral decomposition）的原因便是如此。
所以这个名字看似与光谱有关，实际上是个巧合。
Spectral Graph Theory 之所以叫 Spectral 大概就是因为大量用到了矩阵的谱分解吧。
2 Introduction and Background #
图的定义 #
\(G\)：无向图，无平行边，没有自己到自己的边
\(V\)：点集，大小为\(n\)
\(E\)：边集
整个 Spectral Graph Theory 主要考虑一个函数\(f\)将顶点映射到实数：\(\{f:V \rightarrow \RR\}\)
大部分时候这个函数被表示成一个向量\(\vec{x} \in \RR^V\)（养成习惯：将离散的函数和向量看作等价的对象）
(这一段内容很杂，需要重新整理到合适的位置） 定义内积（非标准的内积）： \(\langle f,g \rangle=\mathbb{E}_{u \sim \pi} [f(u)g(u)]\)
取 V 的子集 S，定义 \(f=1_S\) ，即若 u 属于 S， \(f(u)=1\) ，否则等于 0，那么
\[\|f\|_2^2=\langle f,f \rangle=\E_{u \sim \pi} [f(u)^2]=\Pr_{u \sim \pi}[u\in S]\]
Quadratic form 大致描述了函数 f 在边上变化的程度（local）: \(\mathcal{E}[f]=\frac{1}{2}\E_{u\sim v}[(f(u)-f(v))^2]\)
Variance 大致描述了函数 f 在全图上的变化程度（global）:\(\Var[f]=\frac{1}{2}\mathbb{E}_{u\sim v}[(f(u)-f(v))^2]\)
最小化 quadratic form：f 分别在 G 的 connected components 上取常数时，\(\mathcal{E}[f]=0\)
最大化 quadratic form：不加限制条件的话显然可以无穷大，故一般限制 \(\|f\|_2^2<=1\) 。可以证明： \(\mathcal{E}[f]\leq 2\|f\|_2^2\) ，取等号当且仅当 G 是二分图（bipartite）
给定 u，考虑函数 f 在与 u 相连的所有点上的平均值：\(\mathbb{E}_{v\sim u}[f(v)]\). 这个操作可以看作是一个将定点映射到实数的函数，取名为 Kf，即\(Kf(u)=\mathbb{E}_{v\sim u}[f(v)]\). K 作用于 \(f(u)\) 就是求 f 在与 u 相连的各个定点上的平均值。 可以证明 \(\langle f, Kg\rangle=\langle Kf, g \rangle = \mathbb{E}_{u\sim v}[f(u)g(v)]\) ，即 K 是自伴随的（self-adjoint）。 这里的 K 虽是自伴随但 K 并不一定是对称的，主要因为这里定义的内积不是标准的。
定义 normalized Laplacian \(L=I-K\) ，这样定义其实只是数学上的需要，没有什么物理意义。 人们定义 Laplacian 实际上是因为 \(\langle f,Lf \rangle = \mathcal{E}[f]\) ，人们最终目的还是为了研究 quadratic form
图的矩阵 #
图的邻接矩阵 \[ \mathbf{M}_{G}(a,b)=\begin{cases} 1& \text{ if } (a,b)\in E\\ 0& \text{ otherwise.} \end{cases} \] 因为我们假设是无向图，所以邻接矩阵是对称的。又因为图上的顶点没有自己到自己的边，所以矩阵的主对角线都是 0.
邻接矩阵虽然简单，但可能是最不重要的矩阵了，基本都是对它进行变换后再做研究。
比如 Diffusion matrix 或 Transition matrix，即归一化（行和为 1）的邻接矩阵。它描述了一个Random Walk的过程：想象图上有总量为 1 的某种气体分布在各个定点（这个初始的分布表示为一个向量），每一时刻，气体均匀地向相邻点扩散。这是一种对扩散的离散化描述。
先定义对角矩阵\(\mathbf{D}_G\)，其对角元素\(\mathbf{D}_{G}(a,a)\)为点 a 的度（degree）。Diffusion matrix（transition matrix）的定义在不同的教材上不同，例如 Spielman 将其定义为\(\mathbf{W}_G=\mathbf{M}_G \mathbf{D}_{G}^{-1}\)，此时对一个向量\(\mathbf{p}\in \RR ^{V}\)（理解为气体在各个点上的分布，向量各元素和为 1），下一个时间系统的状态表示为\(\mathbf{W}_G \mathbf{p}\)。O’Donnell 的定义为\(\mathbf{W}_{G}=\mathbf{D}_{G}^{-1}\mathbf{M}_{G}\)，此时对一个行向量\(\mathbf{p}^{T}\)，下一个时刻的状态为\(\mathbf{p}^{T}\mathbf{W}_{G}\)。这两个定义本质是一样的因为邻接矩阵是对称的，这个两个定义实际只相差一个转置。
定理: 若\(G\)是连通图, 其邻接矩阵为\(M\), 且特征值为\(\mu_1\geq \mu_2\geq \dots \geq \mu_n\), 如果\(\mu_n = -\mu_1\), 则\(G\)是二分图 (bipartite graph).
证明:
设\(\phi_n\)是\(\mu_n\)的一个长度为 1 的特征向量, 构造向量\(y\)使得其各项都是\(\phi_{n}\)各项的绝对值: \(\forall u, y(u) = | \phi_n(u) |\), 根据Rayleigh Quotient的性质, 有:
\[ \begin{aligned} | \mu_{n}| &= \left| \phi_n^T M \phi_n \right|\\ &= \left| \sum_{a,b} M(a,b)\phi_n(a)\phi_n(b)\right|\\ &\leq \sum_{a,b} M(a,b)y(a)y(b) = y^T M y \leq \mu_1 \end{aligned} \]
要令上式中不等号都取等号, 则\(y^T M y = \mu_1\)说明\(y\)是\(\mu_1\)的特征向量. 根据Perron-Frobenius Theorem, \(y\)各项都严格大于 0, 所以\(\phi_n\)各项都不是 0. 由\(\phi_n \perp y\), 可知\(\phi_n\)各项必然有正有负. 由图的连通性得, 一定存在一条边\((a,b)\)使得\(\phi_n(a) < 0 < \phi_n(b)\).
要使第一个不等号取等号, 需要\(\sum_{(a,b) \in E} M(a,b)\phi_n(a)\phi_n(b)\)中各项都同号, 由上面的结论, 它们一定都是负号.
所以对每条边\((a, b)\), \(\phi_n(a)\)和\(\phi_n(b)\)异号, 这个符号就将图划分成了二分图.
Laplacian and Quadratic Form #
Spectral Graph Theory 中最重要的研究对象可能是 Quadratic Form。为此要先定义 Laplacian matrix：
Laplacian matrix 定义为： \[\mathbf{L}_{G}=\mathbf{D}_G - \mathbf{M}_G\]
其中\(\vec{D}_G(i,i) = d(i)=\sum_{j:(i,j)\in E} w_{i,j}\)，\(w_{i,j}\)是边\((i,j)\)的权重。
只考虑权重为正数的情况，考虑无权图的时候，将每条边的权重设为 1 即可。
Quadratic form 定义为（等号证明略，简单展开即可）： \[\vec{x}^T \vec{L}_G \vec{x} = \sum_{(a,b)\in E} w_{a,b}(\vec{x}(a)-\vec{x}(b))^2\]
其中\(\vec{x}\in \RR^V\)，看作是一个将顶点映射到实数的函数。
可以将上述定义拓展到权重为负数的图，这里不讨论这些拓展。
大部分书都不提 Laplacian 的物理意义而直接引入。实际上也确实如此：根据 O’Donnell 所说，人们定义 Laplacian 实际上是因为用 Laplacian 可以方便地将 Quadratic form 表达为内积的形式（如上式），人们最终目的还是为了研究 Quadratic form。
Quadratic form 大致描述了函数\(\vec{x}\)在边上变化的程度（O’Donnell 将其称为 local variance，因为其形式很像是概率统计中的 variance）。Quadratic form 越大，说明函数\(\vec{x}\)在相邻两点间变化越剧烈。
Quadratic form 的一个应用：给定一个图，如何选择合适的坐标将它画出来？
考虑画在一维直线上，设函数\(\vec{x}\)将点映射到一个实数坐标，那么可以考虑最小化 quadratic form，从而相邻两点被放在靠近的位置，从而画图的时候减少边的重叠，画出来的图更清晰。
下面介绍一些关于 Laplacian 的定理：
定理：Laplacian 矩阵\(\vec{L}\)半正定
证明：
由定义，\(\vec{L}\)显然是对称的，且对任意向量\(\vec{x}\)有： \[\vec{x}^T \vec{L} \vec{x} = \sum_{(a,b) \in E} w_{a,b}(\vec{x}(a)-\vec{x}(b))^2\geq 0\]
定理：对任意 Laplacian，其最小的特征值为 0
证明：
设\(\vec{1}\)为各元素全为 1 的向量，简单计算可得\(\vec{L}\vec{1} = \vec{0}\)，即 Laplacian 矩阵有特征值 0,其特征向量是常数向量。又因半正定，故该特征值是最小的一个。
一般人们把 Laplacian 矩阵的特征值从小到大排列，因此\(\lambda_1=0\)。
定理：图 G 是连通的当且仅当\(\vec{L}_G\)的第二个特征值\(\lambda_2>0\)
证明：
若\(G\)不连通，则\(V\)一定可以被划分为两个子集\(U\)和\(\bar{U}\)，使得两者之间没有边。此时向量\(\vec{1}_U\)和\(\vec{1}_{\bar{U}}\)线性无关，且是\(\vec{L}_G\)的特征向量，对应的特征值都是 0.
若\(G\)连通，令\(\vec{x}\)为\(\vec{L}_G\)关于特征值 0 的特征向量。则\(\vec{L}_G \vec{x}=0\),所以\(\vec{x}^T\vec{L}_G \vec{x}=0\)。由定义展开，上式为：\(\sum_{(i,j) \in E}(x_i-x_j)^2 = 0\)
为满足上式，对任意一点\(i\)，其所有相邻的点\(j\)必须有\(x_i=x_j\)，可推知在同一连通分量里，任意两点\(i,j\)都应该有\(x_i=x_j\)。由\(G\)连通的假设，\(\vec{x}\)必定是一个常数向量，所以特征值 0 只出现一次，第二个特征值必定大于 0.
定理：对任意 Laplacian，其所有特征值都处于\([0, 2\Delta]\)，其中\(\Delta\)为最大的度（degree）：\(\Delta=\max_{i \in V} d(i)\)
证明：
令\(i\)为使\(|v_i|\)最大的那个顶点。 \[\begin{split}\lambda|v_i| &= |(\lambda v)_i| = |(Lv)_i| = \left| ((D-A)v)_i \right|\\ &= \left| d(i)v_i - \sum_{j \in V}A_{ij}v_j \right|\\ &\leq \left| d(i)v_i \right| + \left| \sum_{j \in V}A_{ij}v_j \right| \\ &= d(i)|v_i| + \sum_{i\sim j}|v_j| \leq 2\Delta|v_i|\end{split} \]
注意这个不等关系不是紧的（第一个不等号很松），实际上，Laplacian 的最大特征值的 upper bound 表达式很复杂，详见这篇survey
3 Graph Partitioning #
在研究 Random walk 时，需要对图的连通程度有所刻画。直觉上讲，当图连通得非常紧密时，从一点开始的 random walk 应该能很快到达其他的点。相反如果图很稀疏，random walk 可能会很慢才能到达别的点。
研究这个“连通程度”有很多应用，例如可以试图构造连通程度很差的图，这种结构可能用来设计不错的隔热材料。
下面会看到，“连通程度”与第二大的特征值\(\lambda_2\)紧密相关。
Isoperimetry and \(\lambda_{2}\) #
考虑寻找点的子集使得它与剩下的图相连的边最少。
首先定义顶点子集 \(S\) 的边界（boundary），即所有从 S 跨到 S 之外的边的集合：
\[\partial(S) = \{ (a,b)\in E:a \in S,b \not\in S \}.\]
定义 isoperimetric ratio：
\[ \theta(S) = \frac{|\partial(S)|}{|S|} \]
希望最小化这个 ratio，但一个技术细节是如果取 S 为整个图，则这个 ratio 为 0。故定义图 G 的最小 isoperimetric ratio 为：
\[ \theta_{G} = \min_{|S|\leq \frac{n}{2}} \theta(S) \]
该值上下界均被含 \(\lambda_{2}\) 的表达式 bound，详见 Cheeger’s Inequality.
Conductance #
Conductance 类似于 isoperimetric ratio，但不再只计算边的数量，而是考虑它们的权重。
对边集合\(F\)我们记 \(w(F)\) 为\(F\)中所有边的权重的和。对点 \(i\) 定义其度（degree）为\(d(i)=\sum_{j:(i,j)\in E} w_{ij}\)。对顶点子集\(S\)定义 \(d(S)=\sum_{i\in S}d(i)\)。注意 \(d(S)\) 中如果边的两个顶点都在\(S\)中，该边的权重被算了两次。
Conductance 的物理意义可想象为从\(S\)中开始的 random walk，从\(S\)跨到\(S\)之外的概率，可表达为\(\frac{w(\partial(S))}{d(S)}\)。
人们感兴趣的是如何选择一个顶点子集\(S\)，使得从 S 中 random walk 跨到外面的概率最小，即最小化 conductance。但一个细节是，如果选择\(S\)为\(V\)则显然跨到外面的概率为 0,故要加一个限制（不失一般性）：\(d(S)\leq d(V-S)\)。
定义点集\(S\)的 conductance 为：
\[ \phi(S)=\frac{w(\partial(S))}{\min (d(S),d(V-S))} \]
定义图 G 的 conductance（也叫 expansion）为： \[\phi_{G}=\min_{\substack{S \subset V, S\neq \emptyset \\ d(S)\leq d(V-S)}} \phi(S)\]
我们用图的 Conductance 反映图的连接情况，越大说明连接得越好。
例子：Barbell Graph
Barbell Graph 有\(2n\)个顶点，每\(n\)个顶点构成一个完全图，且这两个完全图之间有一条边相连。显然这个图连接得很不好。取其中一个完全图为\(S\)，计算其 conductance 可得\(\frac{1}{1+n(n-1)} = O(\frac{1}{n^2})\)。
对 Conductance 不同的书定义不同，有些人将\(S\)的 conductance 定义为： \[\phi(S) = \frac{d(V)w(\partial(S))}{d(S)d(V-S)}\]
这个奇怪的定义主要是因为有如下结论。这也是为什么要引入归一化的 Laplacian（Normalized Laplacian）。
令\(\vec{y}=\vec{1}_S - \sigma \vec{1}\)，其中\(\sigma=d(S)/d(V)\)，则： \[ \frac{\vec{y}^T \vec{L} \vec{y}}{\vec{y}^T \vec{D} \vec{y}} = \frac{d(V)w(\partial(S))}{d(S)d(V-S)}\]
这个结论在Cheeger-Alon-Milman Inequality的证明中被用作引理。
Normalized Laplacian #
定义归一化的 Laplacian（normalized Laplacian）： \(\mathcal{L}=D^{-\frac{1}{2}}LD^{-\frac{1}{2}}=I-\mathcal{A}\)，其中\(\mathcal{A}=D^{-\frac{1}{2}}AD^{-\frac{1}{2}}\)是归一化的邻接矩阵（normalized adjacency matrix）
定理：归一化邻接矩阵的特征值在\([-1,1]\)之间。归一化的 Laplacian 的特征值在\([0,2]\)之间。
证明：
由于 Laplacian 半正定，归一化 Laplacian 根据定义也半正定。即\(I-\mathcal{A} \succcurlyeq 0\)，根据Loewner order的性质，所有\(\mathcal{A}\)的特征值都小于等于 1.
同样可以证明\(D+A\succcurlyeq 0\)，所以\(I+\mathcal{A}=D^{-\frac{1}{2}}(D+A)D^{-\frac{1}{2}}\succcurlyeq 0\)，同样根据Loewner order的性质，所有\(\mathcal{A}\)的特征值都大于等于-1.
根据\(\mathcal{A}=I-\mathcal{L}\)，可以得到\(\mathcal{L}\)的特征值的范围为\([0,2]\)
定理：与 Laplacian 一样，对任意的归一化的 Laplacian，0 是它的特征值。
证明：
令\(v_1=D^{-\frac{1}{2}}\vec{1}\)，则有 \[\mathcal{L}v_1=D^{-\frac{1}{2}}LD^{-\frac{1}{2}}D^{\frac{1}{2}}\vec{1} = D^{-\frac{1}{2}}L \vec{1} = 0\]
Quantify well-connectedness of a graph via \(\lambda_{2}\) #
下面的结论(Cheeger-Alon-Milman Inequality)定量的描述了图的连通程度（conductance）和\(\lambda_2\)的关系：
\[\frac{\lambda_{2}}{2}\leq \phi_{G}\leq \sqrt{2\lambda_{2}}\]
也就是说\(\lambda_2\)越大, 连通程度越好, 在Random Walk时的Mixing Time就越小.
寻找使Conductance最小的顶点子集 #
这个问题叫做 Sparsest Cut，已被证明是 NP-hard.
但根据Cheeger-Alon-Milman Inequality，可以给出一个近似算法：
- 计算图的Normalized Laplacian第二小的特征值的特征向量\(y\)
- 重排\(y\)的各元素，使得\(y_{i_1}\leq \dots \leq y_{i_{n}}\)，即使得点\(i_1\)有最小值，点\(i_n\)有最大值
- 尝试所有的子集\(S=\left\{ i_1, \dots, i_j \right\}\)（或\(V-S\)，取决于谁的 total degree 更小）
上述算法可以保证找到一个子集\(S\)，使得\(\phi_S \leq 2\sqrt{\phi_G}\)
证明：
上述算法实际上就是Cheeger-Alon-Milman Inequality后一个不等号的证明的构造过程。可以保证找到一个子集\(S\)，使得\(\phi_S\leq \sqrt{2\lambda_2}\)
又由第一个不等号：\(\lambda_2\leq 2\phi_G\)，所以可得到\(\phi_S \leq 2\sqrt{\phi_G}\)
4 Random Walk #
Standard Random Walk #
Random walk 描述了一个在图上顶点间的随机过程：起始于一顶点\(i\)，随机选取与其相邻的顶点\(j\)并移动到\(j\)上，选择的概率与\(w_{i,j}\)成比例。这个过程重复无限地进行下去。注意这个定义中，每一步都一定会移动到下一个点，不会停在原本的点。
从\(i\)移动到\(j\)的概率为：
\[p_{ij} = \frac{w_{i,j}}{d(i)} = \frac{w_{i,j}}{\sum_{k:(i,k)\in E} w_{i,k}}\]
将矩阵\(P=(p_{ij})_{ij}\)称作转移矩阵（Transition Matrix），其每一行的和都是 1。
大部分时候我们不考虑单个点的 random walk，而是考虑一个“分布”，即“当前在各个点的概率”。这个分布可用一个向量来表示：\(\pi_{t}(i)\)表示当前 random walk 在点\(i\)上的概率。那么下一步在点\(j\)的概率为\(\sum_{i \in V} p_{ij} \pi_t(i)\)。用矩阵来表达为：把当前在各个点的分布表示成行向量\(\pi_t^T\)那么下一步的分布变为：\(\pi_{t+1}^T = \pi_t^T P\)。若令起始分布为\(\pi_0\)则时间\(t\)的分布为\(\pi_{t}^T = \pi_0^T P^t\)。
令\(A=(w_{i,j})_{ij}\)为邻接矩阵，\(D\)为对角矩阵，且\(D_{ii}=d(i)\)，则有\(P = D^{-1}A\)
Stationary Distribution #
其中分布\(\pi\)的定义为：先随机选择一条边\((u,v)\)，然后舍弃\(v\)，取\(u\)（也可以反过来，效果一样）。也就是说一个点的 degree 越大被选到的概率越高，公式表达为：
\[\pi(i) = \frac{d(i)}{\sum_{j \in V} d(j)}\]
当每条边的权值都为 1 的时候，可写为：\(\pi(u)=\frac{degree(u)}{2|E|}\)
如果\(G\)是 regular 的，即每个点的 degree 相等，则该分布就是均匀分布。
该分布也叫 Invariant Distribution，因为可以证明，若以该分布选起始点\(u_0\)，然后做Standard Random Walk，则\(u_1, u_2, \ldots\)均服从该分布。即：
定理：\(\pi^T = \pi^T P\)
证明：
\[(\pi^T P)(j) = \sum_{i \in V} p_{ij} \pi(i) = \sum_{i \in V} \frac{w_{i,j}}{d(i)} \frac{d(i)}{d(V)} = \sum_{i \in V} \frac{w_{i,j}}{d(V)} = \sum_{i \in V} \frac{d(j)}{d(V)} = \pi(j)\]
其中\(\sum_{i \in V} w_{i,j} = d(j)\)利用了无向图的性质\(w_{i,j} = w_{j,i}\)
Spectra of Walk Matrices #
一般来说转移矩阵\(P\)不是对称的, 但由于它相似于对称矩阵\(\mathcal{A} = D^{-\frac{1}{2}}AD^{-\frac{1}{2}}\) (即 Normalized Adjacency Matrix) , 所以它有跟\(\mathcal{A}\)同样的特征值 (特征向量不一定相同).
证明:
设\(v\)是\(\mathcal{A}\)的特征向量, 特征值为\(\lambda\), 则: \(v^T\mathcal{A} = v^T D^{-\frac{1}{2}}AD^{-\frac{1}{2}} = \lambda v^T\)
两边同右乘上\(D^{\frac{1}{2}}\)得到: \(v^TD^{-\frac{1}{2}}A = v^T D^{\frac{1}{2}} (D^{-1}A) = \lambda v^T D^{\frac{1}{2}}\)
即\(P= D^{-1}A\)有左特征值\(\lambda\), 左特征向量为\(v^T D^{\frac{1}{2}}\)
由于\(\mathcal{A}\)的特征值范围在\([-1,1]\) (证明见: Normalized Laplacian), 故\(P\)也是.
由于\(\pi^T = \pi^T P\), 即\(\pi\)是\(P\)的左特征向量, 特征值为 1, 所以这就是最大特征值.
由Perron-Frobenius Theorem, 令特征值 1 的重数为 1 (即图有唯一的Stationary Distribution.) 的一个充分条件是图是连通的. (实际上也是必要条件)
对于连通的图, 从任一初始分布\(\pi_0\)开始做Random Walk, 几乎总是会收敛到Stationary Distribution, 唯一的例外是 bipartite graph.
定理: 如果连通图不是 bipartite, 则 random walk 一定收敛到唯一的Stationary Distribution \(\pi\)
证明:
由于\(P\)的最大特征值是\(\mu_1 = 1 \) (特征向量是\(\pi\)), 根据图的矩阵中的证明, 若\(\mu_n=-1\), 则图是 bipartite.
由于图不是 bipartite, 得到\(\mu_2, \dots , \mu_n\)的绝对值都小于 1.
设\(P\)的特征向量是\(u_1, \dots , u_n\), 则有:
\[\pi_0 = c_1 u_1+\dots +c_n u_n\]
\[\pi_1 = c_1 \mu_1 u_1+\dots +c_n \mu_n u_n\]
\[\pi_t = c_1 \underbrace{\mu_1^t u_1}_{1^t \pi}+\dots +c_n \mu_n^t u_n\]
因为\(\mu_2, \dots , \mu_n\)的绝对值都小于 1, \(\mu_i^t \to 0\), 所以\(\pi_t \to \pi\) (常数\(c_1\)一定是 1, 因为两边都是分布, 和为 1).
Mixing Time #
Mixing time 描述了一个Random Walk收敛到Stationary Distribution的速度。即我们要找到\(\|\pi_t-\pi\|_1\)的 bound。
设\(\mathcal{A}\)的特征值为\(\mu_1\geq \mu_2\geq \dots \geq \mu_n\)，对应的特征向量为\(v_1,v_2, \dots , v_n\). 上面已经证明\(P\)有同样的特征值，设其特征向量为\(u_1, \dots , u_n\).
上面已经知道\(\mu_1=1\)，这里设一个常量\(\beta=1-\max \left\{ |\mu_2|, |\mu_n|\} \right\}\)，称为\(P\)或\(\mathcal{A}\)的 spectral gap，(表示“gap” to non-convergence to unique stationary distribution). 即\(\beta\)越大收敛得越快。
Regular undirected graphs #
由上面的计算可得：\(\pi_t = \pi+ c_2\mu_2^t u_2 +\dots +c_n \mu_n^t u_n\)，且由于是正规（regular）图，每个点的度都是\(d\)，此时\(D=dI\)，所以\(P\)和\(\mathcal{A}\)有同样的特征基（eigenbasis），因此我们取\(u_i=v_i\)，所以有：
\[\begin{aligned} \|\pi_t-\pi\|_2^2 &= \left\| \sum_{2\leq i\leq n} c_i\mu_i^t u_i \right\|_2^2 = \left\| \sum_{2\leq i\leq n} c_i\mu_i^t v_i \right\|_2^2\\ &= \sum_{2\leq i\leq n} c_i^2 \left| \mu_i \right|^{2t} \leq (1-\beta)^{2t} \sum_{2\leq i\leq n} c_i^2 \end{aligned} \]
其中最后一个等号利用了对称矩阵\(\mathcal{A}\)特征向量的正交性。又有：
\[\begin{aligned} \sum_{2\leq i\leq n} c_i^2 &\leq \sum_{1\leq i\leq n} c_i^2 = \left\| \sum_{1\leq i\leq n} c_i u_i \right\|_2^2 \\ &=\|\pi_0\|_2^2 = \sum_{i \in V} \pi_0(i)^2\\ &\leq \sum_{i \in V} \pi_0(i) = 1 \end{aligned} \]
又由基本不等式，得到：
\[\|\pi_t-\pi\|_1 \leq \sqrt{n} \|\pi_t-\pi\|_2 \leq (1-\beta)^t \sqrt{n}\]
General undirected graphs #
如果图不是正规的，则我们无法得到\(u_i=v_i\)，只能利用\(u_i = D^{\frac{1}{2}}v_i\)，此时：
\[\|\pi_t-\pi\|_2 = \left\| D^{\frac{1}{2}}D^{-\frac{1}{2}}(\pi_t-\pi) \right\|_{2} \leq \left\| D^{\frac{1}{2}} \right\|_{2} \left\| D^{-\frac{1}{2}}(\pi_t-\pi) \right\|_{2}\]
不等号是由于Operator Norm的性质，其中，
\[\left\| D^{\frac{1}{2}} \right\|_2 = \sup_{x \in \RR^V, \|x\|_2\leq 1} \|D^{\frac{1}{2}}\|_2 = \max _{i \in V} \sqrt{d(i)}\]
再由之前的计算得到：
\[\left\| D^{-\frac{1}{2}}(\pi_t-\pi) \right\|_2^2 = \left\| \sum_{2\leq i\leq n} c_i\mu_i^t v_i \right\|_2^2 \leq (1-\beta)^{2t} \sum_{2\leq i\leq n} c_i^2\]
\[\begin{aligned} \sum_{2\leq i\leq n} c_i^2 &\leq \sum_{1\leq i\leq n} c_i^2 = \left\| \sum_{1\leq i\leq n} c_i v_i \right\|_2^2 \\ &= \left\| D^{-\frac{1}{2}}\sum_{1\leq i\leq n} c_i u_i \right\|_2^2 \\ &=\|D^{-\frac{1}{2}}\pi_0\|_2^2 \leq \|D^{-\frac{1}{2}}\|_2^2 \|\pi_0\|_2^2\\ &\leq \|D^{-\frac{1}{2}}\|_2^2 = \sup_{x\in \RR^V, \|x\|_2\leq 1} \left\| D^{-\frac{1}{2}}x \right\|_2\\ &= \max_{i\in V} \sqrt{\frac{1}{d(i)}} = \frac{1}{\min_{i\in V} \sqrt{d(i)}} \end{aligned} \]
将上述结果放在一起得到：
\[\|\pi_t-\pi\|_2 \leq \left\|D^{\frac{1}{2}}\right\|_2 \left\|D^{-\frac{1}{2}}\right\|_2 (1-\beta)^{2t} = \sqrt{\frac{\max_{i\in V} d(i)}{\min_{i\in V} d(i)}}(1-\beta)^{2t}\]
Lazy Random Walk #
与Standard Random Walk不同, Lazy random walk 以 50%的概率停留不动, 另 50%的概率随机选择一个相邻点, 其转移矩阵表示为:
\[\tilde{P} = \frac{1}{2}I + \frac{1}{2} P = \frac{1}{2}I +\frac{1}{2}D^{-1}A\]
可以证明\(\tilde{P}\)的特征值在\([0,1]\)，不可能是-1,因此得出 Lazy random walk 一定收敛（即便是 bipartite graph）。