以下部分是我学习CMU 15-751: TCS Toolkit的课堂笔记。由于只是个人笔记，因此许多地方在推导上可能不那么严谨，还望理论大佬多多包涵。
1 问题定义
1.1 无向图(G)
在本文中，我们将研究对象限定在无向图（undirected graph）(G=(V, E))，且满足：
- 有限（finite）；
- 允许重边和自环；
- 不允许度为0的顶点（即孤立，isolated顶点），但允许有多个连通分量；
此外，我们在某些情况下可能会假设(G)是正则的。
正则图：指各顶点的度均相同的无向简单图。
1.2 顶点标签(f)
定义 设函数
将图的每个顶点用一个实数值来进行标记，我们称其为顶点标签（vertex labelling）。在实际应用场景中，(f)可能是温度、电压、嵌入的坐标（推广到(mathbb{R}^d)时）或者(Ssubseteq V)的0-1示性函数。
在本文中，我们会将函数(f)想成是一个如下所示的（列）向量：
回顾 函数集合(mathcal{F}={f: Vrightarrow mathbb{R}})上带有加法和标量乘法：
- 加法：(f+g)（逐点）；
- 标量乘法：(ccdot f)（(cinmathbb{R})）；
可以证明，(mathcal{F})是一个向量空间，且维度(n=|V|)。后面我们还会在(mathcal{F})上定义内积和范数。
2 Laplacian二次型
2.1 定义
接下来我们将要介绍的是谱图论（spectral graph theory）的关键，也就是Laplacian二次型（Laplacian quadratic form），其定义如下：
（符号约定：(usim v)表示服从均匀分布的随机无向边((u, v)in E)）
直观地理解，Laplacian二次型刻画了图的“能量”（energy），这也是我们为什么用(mathcal{E}(f))来表示它的原因。它在其它语境下，又被称为Dirichlet形式（Dirichlet form），局部方差（local variance），解析边界大小（analytic boundary size）。
2.2 性质
关于Laplacian二次型，我们有以下事实：
-
(mathcal{E}left[fright]geqslant 0)；
-
(mathcal{E}left[c cdot fright] = c^2 cdot mathcal{E}left[fright])；
-
(mathcal{E}left[f + c right] = mathcal{E}left[fright])（(cinmathbb{R})）；
直觉上，(mathcal{E}left[fright])的值越小，也就意味着(f)更加“光滑”（smooth），即其值不会沿着边变化得太剧烈。
例 设图顶点的子集(Ssubseteq V), 0-1示性函数(f=mathbb{I}_{S})用于指示顶点是否在集合(S)中，即：
则我们有：
注意上述式子中要乘以(1/2)是因为我们考虑的是无向图，要避免有向边的重复计数（即“伸出”与“伸入”(S)），最后只需计算“伸出”(S)的边。
2.3 标准随机游走
为了选择一个随机顶点，我们可以：
- 均匀随机地选择一条边 ((u, v))；
- 输出 (u)（或(v)）；
我们依据此采样方式得到的顶点分布记为(pi)，(pi_i)表示顶点(i)被抽中的概率。我们有以下事实：
事实 (pi(u))正比于(text{deg}(u))，即
（注意这里用到了握手定理，即(sum_v text{deg}(v)=2|E|)）
直观地看，(pi)为每个顶点给出了权重/重要性。
注：如果(G)是正则的，那么(pi)是在(V)上的均匀分布。
在此基础上，我们可以得到一些有用的结论。
事实 下列步骤：
- 随机采 (usim pi)；
- 再均匀随机地采(u)的一个邻居(v)（记为(vsim u)）
实质上就等价于均匀随机地采样边((u, v))。如果我们接着输出(v)，则(v)也服从分布(pi)。
推论 设(tin mathbb{N})，随机采(usim pi)，进行(t)步的 “标准随机游走”（standard random walk，S.R.W.）：
则(v)的分布也是(pi)。
定义 (pi)是不变（invariant）/ 平稳（stationary）分布。
Q： 现在假设(u_0in V)是非随机的，并从(u_0 overset{t}{rightsquigarrow}v)。随着(trightarrow infin)，(v)的分布是否还会(rightarrow pi)？
A： 当(G)非连通图时不是；当(G)为二分图时也不是；而其它情况都是如此（我们后面会介绍原因）。
Q： 那么需要多少步才能到达平稳分布呢（也即马尔可夫链的混合时间，mixing time）？
A： 这需要考虑图(G)的谱（特征值），具体我们会在下一讲中介绍。直观的例子比如图拥有较小的割集，那么在随机游走时就需要较长的时间来跨越(S)和(bar{S})；更极端的例子比如非连通图直接永远不会达到平稳分布。在(2.2)中我们证明了若图的割集较小则其(mathcal{E}left[mathbb{I}_Sright])就较小，而我们后面会看到快速收敛等价于(mathcal{E}left[fright])永远不会小。
2.4 (f)的均值和方差
设(f:Vrightarrow mathbb{R})，若(usim pi)，则(f(u))是一个实随机变量（我们这里简记为(f)）。对于该随机变量，我们接下来讨论它的均值与方差。
均值（mean） (f)的均值定义为：
例 若(Ssubseteq V)，(f=mathbb{I}_S)，则
直观上，这个概率表示(S)的“权重”或“体积”。
方差（variance） (f)的方差定义为：
注意，上述式((3))成立是由于：
辨析 这里要注意(f)的方差(text{Var}(f))和其能量(mathcal{E}(f))的差异，它们俩的对比如下：
可见方差(text{Var}[f])是对图的顶点取期望（我们称其为关于(f)的全局方差，global variance），而(mathcal{E}[f])则是对图的边取期望（我们称其为关于(f)的局部方差，local variance）。
3 Laplacian二次型的极值
3.1 (mathcal{F})上的的内积与范数
接下来我们讨论Laplacian二次型的极值，而这就需要我们先定义(mathcal{F}={f: Vrightarrow mathbb{R}})空间上的内积和范数。
定义 设(f, g: Vrightarrowmathbb{R})，则向量空间(mathcal{F})上的 加权内积（weighted inner product） 可以定义为：
直观地，我们可以将其写做：
注： 当(G)是正则图时（此时(pi)为均匀分布），上式是经由(frac{1}{|V|})缩放的“标准点积”（normal dot product）。
回顾 实向量空间上的内积满足以下性质
- (langle f, grangle_{pi}=langle g, frangle_{pi})；
- (langle ccdot f + g, hrangle_{pi} = clangle f, hrangle_{pi} + langle g, h rangle_{pi})（(cinmathbb{R})）；
- (langle f, frangle_{pi}=mathbb{E}_{usimpi}left[f(u)^2right]geqslant 0quad text{with equality iff } fequiv 0)；
定义 对于(finmathcal{F})，我们可以由内积诱导出(f)的(2)-范数：
处理2-范数的平方通常比直接处理它更容易，故我们常常使用( lVert f rVert^2_2:=langle f, frangle_{pi}=mathbb{E}_{usimpi}left[f(u)^2right] )。
此外，我们还可以定义(f)的(1)-范数：
例 设(Ssubseteq V)，(f=mathbb{I}_S)，则
且我们有
3.2 最小化/最大化(mathcal{E}left[fright])
我们在 2.3 中提到随机游走快速收敛等价于(mathcal{E}left[fright])永远不会小，那么(mathcal{E}left[fright])能够有多小呢？
最小化 现在我们来考虑最小化(mathcal{E}left[fright])，即求解：
我们已知(mathcal{E}[f]geqslant0)，故我们接下来讨论什么样的(f)可以使(mathcal{E}[f]=0)。
首先对于(fequiv 0)（即将图的每个顶点都映射到(0)）这一trival的情况，(mathcal{E}left[fright]=0)；
接下来考虑non-trival的情况。我们注意到(fequiv 1)（或任何其它常数）时，
事实上，由于图的不同连通分量之间是不存在边的，因此只要保证(f)在图(G)的每个连通分量上是常数就行。
命题 (mathcal{E}[f]=0)当且仅当(f)在(G)的每个连通分量上是常数。此时：
即当图的连通分量为(S_1,cdots, S_l)时, (mathbb{I}_{S_1}, mathbb{I}_{S_2}, cdots, mathbb{I}_{S_l})是线性无关的（linearly independent）（并满足(mathcal{E}left[fright]=0)约束）。所谓线性无关，直观上即如下所示的关系：
更一般地说，集合({f: mathcal{E}[f]=0})事实上就是(mathbb{I}_{S_1}, mathbb{I}_{S_2}cdots, mathbb{I}_{S_l})的张成空间({sum^l_{i=1}c_imathbb{I}_{S_i}: c_1,cdots, c_lin mathbb{R}})。
最大化 接下来我们来考虑最大化(mathcal{E}left[fright])，即求解
（这里需要注意由于(mathcal{E}[ccdot f]=c^2mathcal{E}[f])，故我们要添加关于(text{Var}left[fright])的约束项以控制常数缩放因子的影响）
事实上，上述优化问题即等价于：
这是因为：
直觉上，该优化问题是在寻找一个好的嵌入(Vrightarrow mathbb{R})，使得边的两个端点在嵌入空间中能够尽可能“远”。那么，什么样的(G)才能最成功呢？答案是二分图。
如果(G)是二分图，(V=(V_1, V_2))。设
也即
于是我们有(lVert f rVert^2_2=mathbb{E}[f^2]=mathbb{E}left[1right]=1)，且(mathcal{E}[f]=2)（由于(frac{1}{2}mathbb{E}_{usim v}[(f(u) - f(v))^2])中(f(u))和(f(v))都为(pm1)）
命题 (mathcal{E}[f] leqslant 2 lVert f rVert^2_2)（即(2mathbb{E}[f^2])）
证明如下：
例 等式(mathcal{E}[f] = 2 lVert frVert^2_2)当且仅当(G)为二分图的时候成立。
4 Markov转移算子
4.1 定义
根据我们前面在 3.2 中的的叙述，我们已经知道
$mathcal{E}[f]=text{arithm}= lVert frVert^2_2 - mathbb{E}_{usim v}[f(u)cdot f(v)] $
这里
注意上图中的带(*)表达式(mathbb{E}_{vsim u}left[f(v)right])刻画的是顶点(u)邻居集合({v})的(f)标签平均值。而这个表达式实际上描述了一个将顶点(u)映射到其邻居标签平均值的函数，接下来我们就来进一步研究这个函数。
定义 我们定义函数(Kf: Vrightarrowmathbb{R})满足
由于我们是离散状态空间，故上式可以写为((Kf)(u)=sum_v f(v)text{Pr}left[vrightarrow umid vright])，这里(text{Pr}[vrightarrow umid v])表示邻居顶点(v)到当前顶点(u)的状态转移概率。直观地理解，函数(Kf)使得顶点(u)被赋予其邻居集合的(f)标签平均值。
这里(K)为定义在函数空间(mathcal{F}={f: Vrightarrow mathbb{R}})上的线性算子，它将函数(finmathcal{F})映射到(Kfinmathcal{F})，并满足：
定义 我们将上述的算子(K)称为图(G)的Markov转移算子（Markov transition operator）/归一化邻接矩阵（normalized adjacency matrix）。
我们可以将算子(K)表示成一个矩阵，该矩阵以如下方式作用：
且满足
所以(K)是归一化后的邻接矩阵(A)的转置（当然这里由于我们关注无向图，(A^T=A)），其每一列的和为(1)（代表一个概率分布）。这样的矩阵被称为随机矩阵（stochastic marix）。
4.2 自伴性质
如果图(G)是(d)-正则的（即所有顶点的度都为(d)），那么我们有：
那么对于非正则图呢？此时(K)的矩阵表示（在非规范正交基下）尽管可能不再是对称阵，但是算子(K)仍然满足自伴的性质。我们有以下事实：
事实 对于(f, g: Vrightarrow mathbb{R})，
证明
基于此，我们有下列推论：
推论
也即(K)是自伴的（self-adjoint）。而这在图(G)是正则图的情况下就等价于(K)是对称的。
接下来再来看我们熟悉的那个示性函数例子。
例 设(S, Tsubseteq V)（(Scap T=emptyset)），(f=mathbb{I}_S)，(g=mathbb{I}_T)，则：
4.3 Markov链
概率分布转移 设(p)为在顶点(V)上的概率分布，即
我们进行如下步骤：
- 随机采一个顶点(usim p)。
- 进行一步从(urightarrow v)的随机游走，并设(p^{prime})为(v)的概率分布。
则我们有如下的概率分布转移关系：
推论 对于平稳概率分布(pi)，满足
接下来我们再展示一个例子说明概率转移具体是如何运作的。
引理 对于算子$K^2 = K circ K $，我们有：
证明 给定(f)，设(g=Kf)，则
故
推论 (forall t in mathbb{N})，((K^tf)(u)=mathbb{E}_{u overset{ttext{-step S.R.W}}{ rightsquigarrow} w}left[ f(w)right])（甚至(t=0)时，我们也有(I f(u) = f(u))）。
参考
[1] CMU 15-751: TCS Toolkit
[2] Bilibili: CMU计算机科学理论(完结)—你值得拥有的数学和计算机课)
[3] Spielman D. Spectral graph theory[J]. Combinatorial scientific computing, 2012, 18: 18.
[4] Axler S. Linear algebra done right[M]. springer publication, 2015.
