谱图论中，Laplacian二次型和Markov转移算子如何关联？
摘要：以下部分是我学习CMU 15-751: TCS Toolkit的课堂笔记。接下来将要介绍的是谱图论（spectral graph theory）的关键，也就是Laplacian二次型（Laplacian quadratic form）。直观
以下部分是我学习CMU 15-751: TCS Toolkit的课堂笔记。由于只是个人笔记，因此许多地方在推导上可能不那么严谨，还望理论大佬多多包涵。
1 问题定义
1.1 无向图\(G\)
在本文中，我们将研究对象限定在无向图（undirected graph）\(G=(V, E)\)，且满足：
有限（finite）；
允许重边和自环；
不允许度为0的顶点（即孤立，isolated顶点），但允许有多个连通分量；
此外，我们在某些情况下可能会假设\(G\)是正则的。
正则图：指各顶点的度均相同的无向简单图。
1.2 顶点标签\(f\)
定义 设函数
\[f: V\rightarrow \mathbb{R}
\]
将图的每个顶点用一个实数值来进行标记，我们称其为顶点标签（vertex labelling）。在实际应用场景中，\(f\)可能是温度、电压、嵌入的坐标（推广到\(\mathbb{R}^d\)时）或者\(S\subseteq V\)的0-1示性函数。
在本文中，我们会将函数\(f\)想成是一个如下所示的（列）向量：
\[\left(\begin{aligned}
\bigg|\\
f\\
\bigg|
\end{aligned}\right)\begin{aligned}
\leftarrow &v_1\\
\leftarrow &v_2\\
&\vdots \\
\leftarrow &v_n
\end{aligned}
\]
回顾 函数集合\(\mathcal{F}=\{f: V\rightarrow \mathbb{R}\}\)上带有加法和标量乘法：
加法：\(f+g\)（逐点）；
标量乘法：\(c\cdot f\)（\(c\in\mathbb{R}\)）；
可以证明，\(\mathcal{F}\)是一个向量空间，且维度\(n=|V|\)。后面我们还会在\(\mathcal{F}\)上定义内积和范数。
2 Laplacian二次型
2.1 定义
接下来我们将要介绍的是谱图论（spectral graph theory）的关键，也就是Laplacian二次型（Laplacian quadratic form），其定义如下：
\[\mathcal{E}\left[f\right] = \frac{1}{2}\cdot\mathbb{E}_{u\sim v}\left[ \left(f\left(u\right) - f\left(v\right)\right)^2\right]
\]
（符号约定：\(u\sim v\)表示服从均匀分布的随机无向边\((u, v)\in E\)，有时把它想成两条“有向边”（\(u\)到\(v\)和\(v\)到\(u\)）是很有用的，前面的\(\frac{1}{2}\)系数有其妙处，我们后面会介绍）
直观地理解，Laplacian二次型刻画了图的“能量”（energy），这也是我们为什么用\(\mathcal{E}(f)\)来表示它的原因。它在其它语境下，又被称为Dirichlet形式（Dirichlet form），局部方差（local variance），解析边界大小（analytic boundary size）。
2.2 性质
关于Laplacian二次型，我们有以下事实：
\(\mathcal{E}\left[f\right]\geqslant 0\)；
\(\mathcal{E}\left[c \cdot f\right] = c^2 \cdot \mathcal{E}\left[f\right]\)；
\(\mathcal{E}\left[f + c \right] = \mathcal{E}\left[f\right]\)（\(c\in\mathbb{R}\)）；
直觉上，\(\mathcal{E}\left[f\right]\)的值越小，也就意味着\(f\)更加“光滑”（smooth），即其值不会沿着边变化得太剧烈。