以下部分是我学习 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\) 时）或者 \(S\subseteq V\) 的0-1示性函数.

在本文中，我们会将函数 \(f\) 想成是一个如下所示的（列）向量:

回顾 函数集合 \(\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） ，其定义如下:

（符号约定： \(u\sim v\) 表示服从均匀分布的随机无向边 \((u, v)\in E\) ） 。

直观地理解，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），即其值不会沿着边变化得太剧烈.

例 设图顶点的子集 \(S\subseteq 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\) 上的均匀分布.

在此基础上，我们可以得到一些有用的结论.

事实 下列步骤:

• 随机采 \(u\sim \pi\) ；
• 再均匀随机地采 \(u\) 的一个邻居 \(v\) （记为 \(v\sim u\) ）

实质上就等价于均匀随机地采样边 \((u, v)\) 。如果我们接着输出 \(v\) ，则 \(v\) 也服从分布 \(\pi\) .

推论 设 \(t\in \mathbb{N}\) ，随机采 \(u\sim \pi\) ，进行 \(t\) 步的 “标准随机游走”（standard random walk，S.R.W.） :

则 \(v\) 的分布也是 \(\pi\) .

定义 \(\pi\) 是 不变（invariant）/ 平稳（stationary）分布 .

Q： 现在假设 \(u_0\in V\) 是非随机的，并从 \(u_0 \overset{t}{\rightsquigarrow}v\) 。随着 \(t\rightarrow \infin\) ， \(v\) 的分布是否还会 \(\rightarrow \pi\) ?

A： 当 \(G\) 非连通图时不是；当 \(G\) 为二分图时也不是；而其它情况都是如此（我们后面会介绍原因）.

Q： 那么需要多少步才能到达平稳分布呢（也即马尔可夫链的混合时间，mixing time）?

A： 这需要考虑图 \(G\) 的谱（特征值），具体我们会在下一讲中介绍。直观的例子比如图拥有较小的割集，那么在随机游走时就需要较长的时间来跨越 \(S\) 和 \(\bar{S}\) ；更极端的例子比如非连通图直接永远不会达到平稳分布。在 \(2.2\) 中我们证明了若图的割集较小则其 \(\mathcal{E}\left[\mathbb{I}_S\right]\) 就较小，而我们后面会看到快速收敛等价于 \(\mathcal{E}\left[f\right]\) 永远不会小.

2.4 \(f\) 的均值和方差

设 \(f:V\rightarrow \mathbb{R}\) ，若 \(u\sim \pi\) ，则 \(f(u)\) 是一个实随机变量（我们这里简记为 \(f\) ）。对于该随机变量，我们接下来讨论它的均值与方差.

均值（mean） \(f\) 的均值定义为:

例 若 \(S\subseteq 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: V\rightarrow \mathbb{R}\}\) 空间上的内积和范数.

定义 设 \(f, g: V\rightarrow\mathbb{R}\) ，则向量空间 \(\mathcal{F}\) 上的 加权内积（weighted inner product） 可以定义为:

直观地，我们可以将其写做:

注 ： 当 \(G\) 是正则图时（此时 \(\pi\) 为均匀分布），上式是经由 \(\frac{1}{|V|}\) 缩放的“标准点积”（normal dot product）.

回顾 实向量空间上的内积满足以下性质 。

• \(\langle f, g\rangle_{\pi}=\langle g, f\rangle_{\pi}\) ；
• \(\langle c\cdot f + g, h\rangle_{\pi} = c\langle f, h\rangle_{\pi} + \langle g, h \rangle_{\pi}\) （ \(c\in\mathbb{R}\) ）；
• \(\langle f, f\rangle_{\pi}=\mathbb{E}_{u\sim\pi}\left[f(u)^2\right]\geqslant 0\quad \text{with equality iff } f\equiv 0\) ；

定义 对于 \(f\in\mathcal{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. 。

最后此篇关于谱图论：Laplacian二次型和Markov转移算子的文章就讲到这里了,如果你想了解更多关于谱图论：Laplacian二次型和Markov转移算子的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。