谱图论:Laplacian算子及其谱性质

这篇具有很好参考价值的文章主要介绍了谱图论:Laplacian算子及其谱性质。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

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\),如下图所示:

谱图论:Laplacian算子及其谱性质

由于\(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\)就消失了)

参考

[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模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【Opencv入门到项目实战】(四):图像梯度计算|Sobel算子|Scharr算子|Laplacian算子

    在图像处理中,梯度是指图像中像素灰度变化的速率或幅度,我们先来看下面这张图 假设我们想要计算出A点的梯度,我们可以发现A点位于边缘点,A点左边为黑色,右边为白色,而计算图像的梯度可以提取出图像中的边缘信息,我们常用的方法是使用 Sobel算子 或 Scharr算子

    2024年02月13日
    浏览(49)
  • python --opencv图像处理Canny算子边缘检测(Roberts算子、Prewitt算子、Sobel算子、Laplacian算子、Scharr 算子、 LOG 算子)

    边缘检测是基于灰度突变来分割图像的常用方法,其实质是提取图像中不连续部分的特征。目前常见边缘检测算子有差分算子、 Roberts 算子、 Sobel 算子、 Prewitt 算子、 Log 算子以及 Canny 算子等。 其中, Canny 算子是由计算机科学家 John F. Canny 于 1986 年提出的一种边缘检测算子

    2024年04月12日
    浏览(51)
  • OpenCV 入门教程:Laplacian算子和Canny边缘检测

    边缘检测在图像处理和计算机视觉领域中起着重要的作用。 Laplacian 算子和 Canny 边缘检测是两种常用的边缘检测方法,它们能够帮助我们准确地检测图像中的边缘信息。 OpenCV 提供了这

    2024年02月13日
    浏览(53)
  • OpenCV—拉普拉斯算子(Laplacian)边缘检测:原理与实现

    目录 介绍 拉普拉斯算子的作用 拉普拉斯算子的原理 使用OpenCV实现拉普拉斯算子 完整代码展示 结论 拉普拉斯算子是一种常用于图像处理的边缘检测技术,它有助于识别图像中的边缘和纹理特征。本文将深入探讨拉普拉斯算子的原理,以及如何使用OpenCV实现它。        

    2024年02月04日
    浏览(54)
  • 我在Vscode学OpenCV 图像处理三(图像梯度--边缘检测【图像梯度、Sobel 算子、 Scharr 算子、 Laplacian 算子、Canny 边缘检测】)

    这里需要区分开边缘检测和轮廓检测 边缘检测并非万能,边缘检测虽然能够检测出边缘,但边缘是不连续的,检测到的边缘并不是一个整体。图像轮廓是指将边缘连接起来形成的一个整体,用于后续的计算。 OpenCV 提供了查找图像轮廓的函数 cv2.findContours(),该函数能够查找图

    2024年02月04日
    浏览(56)
  • Python从0到1丨详解图像锐化的Sobel、Laplacian算子

    本文分享自华为云社区《[Python从零到壹] 五十八.图像增强及运算篇之图像锐化Sobel、Laplacian算子实现边缘检测》,作者: eastmount 。 Sobel算子是一种用于边缘检测的离散微分算子,它结合了高斯平滑和微分求导。该算子用于计算图像明暗程度近似值,根据图像边缘旁边明暗程

    2024年02月09日
    浏览(38)
  • 关系的基本概念及其性质

    二元关系: 定义: 设A和B是两个集合,A×B的任一子集R称为从A到B的一个二元关系。 如果(a,b)∈R,则a与b符合关系R,记为aRb;  如果(a,b) R,则a与b不符合关系R,记为aRb。 如果A=B,则称R为A上的二元关系。 性质:  若|A|=m,|B|=n,则|A×B|=m×n,A×B共有2m×n个子集,所以从A到B的二

    2024年02月04日
    浏览(71)
  • Kronecker积及其等式性质

    m × n mathit{m} times mathit{n} m × n 矩阵 A = [ a 1 , ⋯   , a n ] boldsymbol{A}=left[boldsymbol{a}_{1}, cdots, boldsymbol{a}_{mathit{n} }right] A = [ a 1 ​ , ⋯ , a n ​ ] 和 p × q mathit{p} times mathit{q} p × q 矩阵 B boldsymbol{B} B 的 K r o n e c k e r mathit{Kronecker} K r o n e c k e r 积记作 A ⊗ B boldsymbol{A}

    2024年02月07日
    浏览(25)
  • 矩阵的其他性质及其运算技巧

    1.单位矩阵(E):类似实数运算中的“1”,任何矩阵乘单位矩阵都等于该矩阵本身,但不同矩阵对应的单位矩阵不同。 2.矩阵乘法满足结合律和分配律,但不满足交换律,原因见三。 3.当两个不同阶矩阵相乘时,如果可以运算,则运算后会得到一个矩阵,而交换两个矩阵的位

    2024年02月06日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包