以下部分是我学习CMU 15-751: TCS Toolkit的课堂笔记。由于只是个人笔记，因此许多地方在推导上可能不那么严谨，还望理论大佬多多包涵。
1 问题定义
1.1 无向图G
在本文中，我们将研究对象限定在无向图（undirected graph）G=(V,E)，且满足：
- 有限（finite）；
- 允许重边和自环；
- 不允许度为0的顶点（即孤立，isolated顶点），但允许有多个连通分量；
此外，我们在某些情况下可能会假设G是正则的。
正则图：指各顶点的度均相同的无向简单图。
1.2 顶点标签f
定义 设函数
将图的每个顶点用一个实数值来进行标记，我们称其为顶点标签（vertex labelling）。在实际应用场景中，f可能是温度、电压、嵌入的坐标（推广到Rd时）或者S⊆V的0-1示性函数。
在本文中，我们会将函数f想成是一个如下所示的（列）向量：
回顾 函数集合F={f:V→R}上带有加法和标量乘法：
- 加法：f+g（逐点）；
- 标量乘法：c⋅f（c∈R）；
可以证明，F是一个向量空间，且维度n=|V|。后面我们还会在F上定义内积和范数。
2 Laplacian二次型
2.1 定义
接下来我们将要介绍的是谱图论（spectral graph theory）的关键，也就是Laplacian二次型（Laplacian quadratic form），其定义如下：
（符号约定：u∼v表示服从均匀分布的随机无向边(u,v)∈E，有时把它想成两条“有向边”（u到v和v到u）是很有用的，前面的12系数有其妙处，我们后面会介绍）
直观地理解，Laplacian二次型刻画了图的“能量”（energy），这也是我们为什么用E(f)来表示它的原因。它在其它语境下，又被称为Dirichlet形式（Dirichlet form），局部方差（local variance），解析边界大小（analytic boundary size）。
2.2 性质
关于Laplacian二次型，我们有以下事实：
-
E[f]⩾0；
-
E[c⋅f]=c2⋅E[f]；
-
E[f+c]=E[f]（c∈R）；
直觉上，E[f]的值越小，也就意味着f更加“光滑”（smooth），即其值不会沿着边变化得太剧烈。
例 设图顶点的子集S⊆V, 0-1示性函数f=IS用于指示顶点是否在集合S中，即：
则我们有：
这里可以看到乘以系数12的妙处了，如果我们把无向边u∼v想成“伸出”与“伸入”S的两条有向边，那么乘以12可以使我们只计算“伸出”S的边。
2.3 标准随机游走
为了选择一个随机顶点，我们可以：
- 均匀随机地选择一条边 (u,v)；
- 输出 u（或v）；
我们依据此采样方式得到的顶点分布记为π，πi表示顶点i被抽中的概率。我们有以下事实：
事实 π(u)正比于deg(u)，即
（注意这里用到了握手定理，即∑vdeg(v)=2|E|）
直观地看，π为每个顶点给出了权重/重要性。
注：如果G是正则的，那么π是在V上的均匀分布。
在此基础上，我们可以得到一些有用的结论。
事实 下列步骤：
- 随机采 u∼π；
- 再均匀随机地采u的一个邻居v（记为v∼u）
实质上就等价于均匀随机地采样边(u,v)。如果我们接着输出v，则v也服从分布π。
推论 设t∈N，随机采u∼π，进行t步的 “标准随机游走”（standard random walk，S.R.W.）：
则v的分布也是π。
定义 π是不变（invariant）/ 平稳（stationary）分布。
Q： 现在假设u0∈V是非随机的，并从u0t⇝v。随着t→∞，v的分布是否还会→π？
A： 当G非连通图时不是；当G为二分图时也不是；而其它情况都是如此（我们后面会介绍原因）。
Q： 那么需要多少步才能到达平稳分布呢（也即马尔可夫链的混合时间，mixing time）？
A： 这需要考虑图G的谱（特征值），具体我们会在下一讲中介绍。直观的例子比如图拥有较小的割集，那么在随机游走时就需要较长的时间来跨越S和ˉS；更极端的例子比如非连通图直接永远不会达到平稳分布。在2.2中我们证明了若图的割集较小则其E[IS]就较小，而我们后面会看到快速收敛等价于E[f]永远不会小。
2.4 f的均值和方差
设f:V→R，若u∼π，则f(u)是一个实随机变量（我们这里简记为f）。对于该随机变量，我们接下来讨论它的均值与方差。
均值（mean） f的均值定义为：
例 若S⊆V，f=IS，则
直观上，这个概率表示S的“权重”或“体积”。
方差（variance） f的方差定义为：
注意，上述式(3)成立是由于：
辨析 这里要注意f的方差Var(f)和其能量E(f)的差异，它们俩的对比如下：
可见方差Var[f]是对图的顶点取期望（我们称其为关于f的全局方差，global variance），而E[f]则是对图的边取期望（我们称其为关于f的局部方差，local variance）。
3 Laplacian二次型的极值
3.1 F上的的内积与范数
接下来我们讨论Laplacian二次型的极值，而这就需要我们先定义F={f:V→R}空间上的内积和范数。
定义 设f,g:V→R，则向量空间F上的 加权内积（weighted inner product） 可以定义为：
直观地，我们可以将其写做：
注： 当G是正则图时（此时π为均匀分布），上式是经由1|V|缩放的“标准点积”（normal dot product）。
回顾 实向量空间上的内积满足以下性质
- ⟨f,g⟩π=⟨g,f⟩π；
- ⟨c⋅f+g,h⟩π=c⟨f,h⟩π+⟨g,h⟩π（c∈R）；
- ⟨f,f⟩π=Eu∼π[f(u)2]⩾0with equality iff f≡0；
定义 对于f∈F，我们可以由内积诱导出f的2-范数：
处理2-范数的平方通常比直接处理它更容易，故我们常常使用 \lVert f \rVert^2_2:=\langle f, f\rangle_{\pi}=\mathbb{E}_{u\sim\pi}\left[f(u)^2\right] 。
此外，我们还可以定义f的1-范数：
例 设S\subseteq V，f=\mathbb{I}_S，则
且我们有
3.2 最小化/最大化\mathcal{E}\left[f\right]
我们在 2.3 中提到随机游走快速收敛等价于\mathcal{E}\left[f\right]永远不会小，那么\mathcal{E}\left[f\right]能够有多小呢？
最小化 现在我们来考虑最小化\mathcal{E}\left[f\right]，即求解：
我们已知\mathcal{E}[f]\geqslant0，故我们接下来讨论什么样的f可以使\mathcal{E}[f]=0。
首先对于f\equiv 0（即将图的每个顶点都映射到0）这一trival的情况，\mathcal{E}\left[f\right]=0；
接下来考虑non-trival的情况。我们注意到f\equiv 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[f\right]=0约束）。所谓线性无关，直观上即如下所示的关系：
更一般地说，集合\{f: \mathcal{E}[f]=0\}事实上就是\mathbb{I}_{S_1}, \mathbb{I}_{S_2}\cdots, \mathbb{I}_{S_l}的张成空间\{\sum^l_{i=1}c_i\mathbb{I}_{S_i}: c_1,\cdots, c_l\in \mathbb{R}\}。
最大化 接下来我们来考虑最大化\mathcal{E}\left[f\right]，即求解
（这里需要注意由于\mathcal{E}[c\cdot f]=c^2\mathcal{E}[f]，故我们要添加关于\text{Var}\left[f\right]的约束项以控制常数缩放因子的影响）
事实上，上述优化问题即等价于：
这是因为：
直觉上，该优化问题是在寻找一个好的嵌入V\rightarrow \mathbb{R}，使得边的两个端点在嵌入空间中能够尽可能“远”。那么，什么样的G才能最成功呢？答案是二分图。
如果G是二分图，V=(V_1, V_2)。设
也即
于是我们有\lVert f \rVert^2_2=\mathbb{E}[f^2]=\mathbb{E}\left[1\right]=1，且\mathcal{E}[f]=2（由于\frac{1}{2}\mathbb{E}_{u\sim v}[(f(u) - f(v))^2]中f(u)和f(v)都为\pm1）
命题 \mathcal{E}[f] \leqslant 2 \lVert f \rVert^2_2（即2\mathbb{E}[f^2]）
证明如下：
例 等式\mathcal{E}[f] = 2 \lVert f\rVert^2_2当且仅当G为二分图的时候成立。
4 Markov转移算子
4.1 定义
根据我们前面在 3.2 中的的叙述，我们已经知道
\mathcal{E}[f]=\text{arithm}= \lVert f\rVert^2_2 - \mathbb{E}_{u\sim v}[f(u)\cdot f(v)]
这里
注意上图中的带*表达式\mathbb{E}_{v\sim u}\left[f(v)\right]刻画的是顶点u邻居集合\{v\}的f标签平均值。而这个表达式实际上描述了一个将顶点u映射到其邻居标签平均值的函数，接下来我们就来进一步研究这个函数。
定义 我们定义函数Kf: V\rightarrow\mathbb{R}满足
由于我们是离散状态空间，故上式可以写为(Kf)(u)=\sum_v f(v)\text{Pr}\left[v\rightarrow u\mid v\right]，这里\text{Pr}[v\rightarrow u\mid v]表示邻居顶点v到当前顶点u的状态转移概率。直观地理解，函数Kf使得顶点u被赋予其邻居集合的f标签平均值。
这里K为定义在函数空间\mathcal{F}=\{f: V\rightarrow \mathbb{R}\}上的线性算子，它将函数f\in\mathcal{F}映射到Kf\in\mathcal{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: V\rightarrow \mathbb{R}，
证明
基于此，我们有下列推论：
推论
也即K是自伴的（self-adjoint）。而这在图G是正则图的情况下就等价于K是对称的。
接下来再来看我们熟悉的那个示性函数例子。
例 设S, T\subseteq V（S\cap T=\emptyset），f=\mathbb{I}_S，g=\mathbb{I}_T，则：
4.3 Markov链
概率分布转移 设p为在顶点V上的概率分布，即
我们进行如下步骤：
- 随机采一个顶点u\sim p。
- 进行一步从u\rightarrow 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{t\text{-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.
__EOF__
