1 Laplacian 算子
给定无向图\(G=(V, E)\),我们在上一篇博客《谱图论:Laplacian二次型和Markov转移算子》中介绍了其对应的Laplacian二次型:
\[\mathcal{E}[f]=\frac{1}{2} \cdot \mathbb{E}_{u \sim v}\left[(f(u)-f(v))^2\right]
\]
这里\(f: V\rightarrow \mathbb{R}\)为图的顶点标签,\(u\sim v\)表示服从均匀分布的随机无向边\((u, v)\in E\)。直观地理解,Laplacian二次型刻画了图的“能量”(energy)。\(\mathcal{E}[f]\)的值越小,也就意味着\(f\)更加“光滑”(smooth),即其值不会沿着边变化得太剧烈。
事实上,我们可以做进一步地等价变换:
\[\begin{aligned}
\mathcal{E}[f] &=\frac{1}{2} \cdot \mathbb{E}_{u \sim v}\left[(f(u)-f(v))^2\right]\\
&= \langle f, f \rangle - \mathbb{E}_{u\sim v}\left[f(u)f(v)\right]\\
&= \langle f, f \rangle - \langle f, Kf \rangle\\
&= \langle f, If - Kf \rangle \\
&= \langle f, (I - K) f \rangle
\end{aligned}
\]
这\(K\)为我们在上一篇博客中提到的MarKov转移算子,它满足:\((K f)(u)=\mathbb{E}_{v \sim u}[f(v)]\)。
对于最后一个等式而言,我们称算子
\[L = I - K
\]
为图\(G\)的 (归一化)Laplacian算子。
注 对于\(d\)-正则图\(G\)而言,我们有
\[L = I - \frac{1}{d} A = \frac{1}{d}(dI - A)
\]
这里\(A\)为\(G\)的邻接矩阵,\(dI - A\)被称为非归一化Laplacian算子,或直接被简称为Laplacian算子。
和\(K\)一样,\(L\)也是定义在函数空间\(\mathcal{F}=\{f: V \rightarrow \mathbb{R}\}\)上的线性算子,按照以下规则将\(f\in \mathcal{F}\)映射到\(Lf\in \mathcal{F}\),满足
\[Lf(u) = f(u) - \mathbb{E}_{v\sim u}[f(v)],
\]
通过研究\(L\),我们就能把握Laplacian二次型\(\mathcal{E}[f] = \langle f, Lf \rangle\)的特性,从而把握图\(G\)的特性,这是谱图理论中至关重要的一点。
接下来再来看我们熟悉的那个示性函数例子。
例 设图顶点的子集\(S\subseteq V\), 0-1示性函数\(f=\mathbb{I}_S\)用于指示顶点是否在集合\(S\)中,即:
\[f(u)=\left\{\begin{array}{lll}
1 & \text { if } & u \in S \\
0 & \text { if } & u \notin S
\end{array}\right.
\]
则我们有:
\[\begin{aligned}
& \langle f, Lf \rangle = \mathbb{E}[f] = \text{Pr}_{u\sim v}[u\in S, v\notin S]\\
& \langle f, f\rangle = \mathbb{E}_{u\sim \pi}[f(u)^2] = \text{Pr}_{u\sim \pi}[u\in S] = \text{vol}(S)
\end{aligned}
\]
直观地理解,这里\(\text{Pr}_{u\sim v}[u\in S, v\notin S]\)表示“伸出”\(S\)的边占总边数的比例;\(\text{vol}(S)\)表示\(S\)的“体积”。则上述两式的比值
\[\begin{aligned}
\frac{\langle f, Lf\rangle}{\langle f, f \rangle} &= \text{Pr}_{u\sim v}\left[v\notin S\mid u \in S \right]\\
&= \text{Pr}\left[ \underbrace{\text{pick a random } u\in S}_{\text{proportional to the degree}}\text{, do }\ 1 \text{ step, that you get out of } S \right] \\
& \in \left[0, 1\right]
\end{aligned}
\]
表示从集合\(S\)中的“逃出”概率。我们将这个比值称为\(S\)的电导(conductance)(我们在博客《图数据挖掘:重叠和非重叠社区检测算法》中介绍过,当时是用来衡量社区划分的质量,这个值越小说明划分得越好),用\(\Phi[S]\)表示。
2 再论Laplacian二次型的极值
有了\(L\),那么最小化/最大化\(\mathcal{E}[f]\)的问题就可以进行进一步的研究了。考虑下列优化问题:
\[\begin{aligned}
& \max \quad \mathcal{E}[f] = \langle f, Lf\rangle = \underbrace{\frac{1}{2}\mathbb{E}_{u\sim v}\left[\left(f(u) - f(v)\right)^2\right]}_{\text{continous func. } f: \space\mathbb{R}^n\rightarrow \mathbb{R}}\\
& \text{s.t.} \underbrace{\quad \lVert f \rVert^2_2 = \langle f, f\rangle = \mathbb{E}_{u\sim\pi}[f(u)^2] = 1}_{\text{compat set}, \text{ ellipsoid in } \mathbb{R}^n} \quad (\Leftrightarrow\text{Var}[f] = 1)
\end{aligned}
\]
存在一个极大值点\(\varphi: V\rightarrow \mathbb{R}\),它满足:
\[L \varphi=\lambda \varphi \quad \text { for some } \lambda \in \mathbb{R},
\]
也即\(L\varphi \parallel \varphi\)。此外,该极大点也可以被有效地找到。
推论
\[\mathcal{E}[\varphi] = \langle \varphi, L\varphi\rangle = \langle \varphi, \lambda \varphi \rangle = \lambda \langle \varphi, \varphi \rangle = \lambda \in \left[0, 2\right]
\]
事实
\[\begin{aligned}
& \mathbb{E}[\varphi] = \mathbb{E}_{u\sim \pi}\left[\varphi(u)\right] = \mathbb{E}_{u\sim \pi}\left[\varphi(u) \cdot 1\right] = 0 \Leftrightarrow \langle \varphi, \mathbb{1} \rangle = 0 \Leftrightarrow \varphi \perp \mathbf{1}\\
& \text{Var}[\varphi] = 1
\end{aligned}
\]
下面我们来证明为什么\(\mathcal{E}[f]\)的极大值点\(\varphi\)满足\(L\varphi \parallel \varphi\)。
证明 我们采用反证法,即假设极大值点\(\varphi\)满足\(L\varphi \nparallel \varphi\),如下图所示:
由于\(L\varphi \nparallel \varphi\),那么我们可以现在\(L\varphi\)与\(\varphi\)之间的垂线方向上取\(f = \varphi + \varepsilon \psi\)(\(\varepsilon\neq 0\)是一个很小的数,\(\psi\)为单位向量),根据勾股定理有\(\lVert f \rVert^2_2 = 1 + \epsilon^2\)。则:
\[\begin{aligned}
\mathcal{E}[f] = \langle f, Lf \rangle &\overset{(1)}{=} \langle \varphi + \varepsilon \psi, L\varphi + L\varepsilon \psi \rangle \\
& \overset{(2)}{=} \langle \varphi, L \varphi \rangle + \underbrace{\varepsilon \langle \phi, L \psi \rangle + \varepsilon \langle \psi, L \varphi \rangle}_{L \text{ is self-adjoint}} + \varepsilon^2 \langle \psi, L \psi \rangle\\
& \overset{(3)}{=} \langle \varphi, L \varphi \rangle + \underbrace{2\varepsilon \langle \psi, L \varphi \rangle}_{>0} + \mathcal{O}(\epsilon^2) \\
& > \langle \varphi, L \varphi \rangle
\end{aligned}
\]
(其中等式\((3)\)用到了自伴算子的定义)而这与\(\varphi\)为极大值点相矛盾。因此,\(\mathcal{E}[f]\)的极大值点\(\varphi\)满足\(L\varphi \parallel \varphi\)。
3 Laplacian算子的谱性质
在上一小节,我们已经证明了\(\varphi\)是一个极大值点。现在我们不采用\(\varphi\)及所有与\(\varphi\)平行的解,而将解限制在与\(\varphi\)相正交的子空间中。这样,优化问题就变为了:
\[\text{Max } \underbrace{\langle f, Lf \rangle}_{\text{continous func. }} \quad \text{s.t.} \underbrace{\lVert f \rVert^2_2 = \langle f, f \rangle = 1}_{\text{compat set}},\quad f\perp \varphi
\]
求解该优化问题可以采用与之前相同的思路,也即存在极大值点\(\varphi^{\prime}\)满足:
\[L \varphi^{\prime}=\lambda^{\prime} \varphi^{\prime} \quad \text { for some } \lambda^{\prime} \leqslant \lambda,\text{and } \mathbb{E}[\varphi^{\prime}] = 0 (\Leftrightarrow \langle \varphi^{\prime}, \mathbf{1} \rangle = 0)
\]
这里\(\lambda^{\prime} < \lambda\)的原因是\(\lambda\)已经对应了极大值点,而我们添加了新的约束使\(f\nparallel \varphi\),故这里\(\lambda^{\prime}\)对应的是第二大的极值点。
重复这个步骤,不断寻找第3大,第\(4\)大……的极大值点,并使其与之前找到的所有极大值点正交,直到找到最后一个(第\(n\)大的)极大值点。在这个过程中得到的极大值点都会\(\perp\)于\(\mathbf{1}\)(\(\mathbf{1}\)为全1向量),而最后一个极大值点即为所剩的\(\mathbf{1}\)向量本身,此时有
\[L\mathbf{1}=0
\]
由此可见最后一个特征值(最小的特征值)为0。
通过上面所述的步骤,我们可以找到Laplacian算子的\(n\)个相互正交的规范化特征向量(范数为1)及其对应的特征值。而这事实上和我们在线性代数课程中所学过的谱定理密切相关。
谱定理 若\(T\)为一个实向量空间\(V\)上的自伴算子,则\(V\)有一个由\(T\)的特征向量组成的规范正交基(orthonormal basis)\(\varphi_1, \varphi_2, \cdots, \varphi_{n}\),每个特征向量分别对应于实特征值\(\lambda_1, \lambda_2, \cdots, \lambda_{n}\)。
我们前面证明过Markov转移算子\(K\)是自伴的,则\(L = I - K\)也是自伴的(事实上,又由于\(\langle f, Lf \rangle \geqslant 0\),\(L\)还是半正定的)。于是,关于图\(G\)的Laplacian算子就有以下定理:
定理 给定\(G\)及其Laplacian算子\(L\),则存在规范正交基(函数)\(\mathbf{1} \equiv \varphi_1, \varphi_2, \cdots, \varphi_{n}\)及实数$0=\lambda_1 \leqslant \lambda_2\leqslant \cdots \leqslant \lambda_{n} \leqslant 2 $满足:
\[L\varphi_i = \lambda_i \varphi_i
\]
我们将\(\lambda_2\)和更广泛的\(\lambda_k\)(\(k\)为一个较小的值)称为低频(low-frequency) 特征值,而将\(\lambda_n\)称为高频(high-frequency) 特征值。
事实上,除了讨论Laplacian算子\(L\)之外,我们也可以讨论Markov转移算子\(K\)的特征向量及特征值。由\(L = I - K\),我们有
\[K \varphi_i = (I - L) \varphi_i = I \varphi_i - L\varphi_i = \varphi_i - \lambda_i \varphi_i = (1 - \lambda_i) \varphi_i,
\]
则\(K\)拥有特征向量\(\varphi_i\)及其相伴的特征值 \(\kappa_i = 1 - \lambda_i\),且\(-1\leqslant \kappa_{n}\leqslant\cdots\leqslant \kappa_2 \leqslant \kappa_1 = 1\)。
定义 给定\(f: V\rightarrow \mathbb{R}\)和正交基\(\varphi_1, \varphi_2, \cdots \varphi_{n}\),那么\(f\)能够唯一地表示为\(\varphi_i\)的一个线性组合:
\[f = \hat{f}(1) \varphi_1 + \hat{f}(2) \varphi_2 + \cdots \hat{f}(n) \varphi_{n},\quad \hat{f}(i)\in \mathbb{R}
\]
这个性质会为我们带来许多新的结论。
命题 将\(L\)应用于\(f\),就得到了:
\[Lf = \underbrace{\lambda_1 \hat{f}(1) \varphi_1}_{0} + \lambda_2 \hat{f}(2) \varphi_2 + \cdots + \lambda_{n} \hat{f}(n) \varphi_{n},
\]
可以看到,\(L\)应用于\(f\)可以转换为分别去应用于正交基。为了方便,我们常常会使用如下所示的记号:
\[\widehat{Lf}(i) = \lambda_i \hat{f}(i)
\]
此外,我们也可以使用规范正交基来简化我们内积和范数的表示。
命题 给定另一个函数
\[g = \hat{g}(1)\varphi_1 + \cdots + \hat{g}(n)\varphi_{n},
\]
则\(f\)和\(g\)的内积
\[\langle f, g\rangle = \sum_{i, j}\hat{f}(i)\hat{g}(j)\langle \varphi_i, \varphi_j \rangle = \sum_{1\leqslant i \leqslant n}\hat{f}(i)\cdot \hat{g}(i)
\]
推论
根据内积我们可以诱导出范数
\[\lVert f \rVert^2_2 = \langle f, f\rangle = \sum_{1\leqslant i \leqslant n}\hat{f}(i)^2,
\]
\(f\)的均值可表示为:
\[\mathbb{E[f]}=\mathbb{E}_{u\sim \pi}[f(u)] = \langle f, \mathbf{1}\rangle=\langle f, \varphi_1 \rangle = \widehat{f}(1)
\]
可以看到,\(f\)沿规范正交基的展开式中的第一项就是均值乘单位向量:
\[f = \underbrace{\hat{f}(1)}_{\mathbb{E}[f]} \underbrace{\varphi_1}_{\mathbf{1}} + \hat{f}(2) \varphi_2 + \cdots \hat{f}(n) \varphi_{n}, \quad \hat{f}(i) \in \mathbb{R},
\]
\(f\)的方差可表示为:
\[\begin{aligned}
\text{Var}[f] & = \mathbb{E}[f^2] - \mathbb{E}[f]^2 \\
& = \sum_{1\leqslant i \leqslant n} \left[\hat{f}(i)^2\right] - \hat{f}(1)^2 \\
&= \sum_{1< i \leqslant n} \hat{f}(i)^2
\end{aligned}
\]
(注意第\(1\)项\(\hat{f}(1)^2 - \hat{f}(1)^2\)抵消掉了)
Laplacian二次型\(\mathcal{E}[f]\)可表示为:
\[\begin{aligned}
\mathcal{E}[f] &= \langle f, Lf \rangle \\
&= \sum_{i, j}\lambda_i \hat{f}(i)\hat{f}(j)\langle \varphi_i, \varphi_j \rangle\\
&= \sum_{1 < i\leqslant n}\lambda_i \hat{f}(i)^2
\end{aligned}
\]
(注意第\(1\)项由于\(\lambda_1=0\)就消失了)文章来源:https://www.toymoban.com/news/detail-711055.html
参考
[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.文章来源地址https://www.toymoban.com/news/detail-711055.html
到了这里,关于谱图论:Laplacian算子及其谱性质的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!