图拉普拉斯矩阵谱特性分析

李社蕾 陆娇娇

摘 要：卷积神经网络泛化到图结构上之后受到很多研究者的关注，由于谱图理论的强大支撑，基于谱域的图卷积神经网络的研究备受关注，文中研究图拉普拉斯矩阵的谱域特性，以及图拉普拉斯矩阵的特征向量与特征值之间的关系。通过实验，验证了图拉普拉斯矩阵的特征向量矩阵具有的频谱特性，重建图结构、图分割等优美的内在特性，为图卷积神经网络进一步研究提供参考。

关键词：拉普拉斯矩阵;频谱特性;特征向量;卷积神经网络;图结构特性;MATLAB

中图分类号：TP391文献标识码：A文章编号：2095-1302（2020）06-00-02

0 引 言

图拉普拉斯矩阵（Laplacian Matrix）也称为导纳矩阵，作为图的矩阵表示，在工程中应用非常广泛[1]。拉普拉斯矩阵又叫作离散拉普拉斯算子，在谱聚类方面，拉普拉斯矩阵被应用到聚类分析中，聚类问题从图的角度看就是对图的分割问题[2-3]。因此，出现了一种谱聚类算法（Spectral Clustering），该算法的核心思想是把样本空间的聚类问题转化为无向图G最优划分问题[4-6]。随着卷积神经网络在图结构上泛化，深入理解图拉普拉斯矩阵物理含义及谱域特性有助于加深对GCN模型的理解，并为GCN模型进一步深入研究及改进提供理论参考。

1 拉普拉斯矩阵

拉普拉斯矩阵在图论中，表示图的一种矩阵，给定一个有N个节点的简单图无向图G （V， E， A）。其中，V={v1， v2， ...， vN}

表示所有顶点的集合;E为边集合，eij=（vi， vj）∈E表示两个节点i和j之间的边;A为邻接矩阵，是一个N×N的矩阵：

令dv表示顶点v的度，普拉普拉斯矩阵L定义如下：

L也可以看作定义在空间函数上的算子g：V（G）→R满足

由定义可知：

式中，D=diag （dv1，dv2， ...， dvN ）为图的度矩阵。简单无向图如图1所示。

图中，图结构是由6个顶点组成的简单无向图，其度矩阵D、图1的邻接矩阵A为：

确定了D和A之后，根据式（4）就可以得到图1的拉普拉斯矩阵L：

图的拉普拉斯矩阵具有如下性质：

（1）拉普拉斯矩陣为实对称矩阵，其特征向量构成的矩阵为正交阵;

（2）拉普拉斯矩阵是半正定的，有N个非负的特征值0=λ0≤λ2≤...≤λN-1，其中最小特征值λ0=0，所对应的特征向量为1;

（3）对于任意向量f∈Rn，式（7）成立：

2 频域特性

以path图为例介绍，图拉普拉斯矩阵的频域特性，path图如图2所示。图中有顶点集合{1， 2， ...， 10}，边（i， i+1），1≤i≤N，共10个顶点，9条边。图3为path图的部分特征谱。由图可知，特征值0对应的特征向量U [：， 0]为常向量，对应傅里叶变换的直流分量，特征值λ1，λ2对应特征向量，U [：， 1]，U [：， 2]为低频特征向量。它们描绘出的曲线类似于弦的低频振动模式，路径图可以看作是弦的离散化，拉普拉斯矩阵对应于拉普拉斯算子的离散化;相反，最高频率的特征值对应的特征向量U [：， N-1]与每个顶点按正负交替出现。这些高频特征向量可能与图着色和寻找独立集的问题有关。

3 重建图结构特性

通常可以使用低频特征值来得到图结构，3×4网格图的图邻接关系和图结构如图4所示。它的前两个为非平凡特征向量，观察发现它们可能为顶点提供坐标而重构图结构。

G.U [：， 1]= [-0.377 1  -0.156 2  0.156 2  0.377 1

-0.377 1  -0.156 2  0.156 2  0.377 1

-0.377 1  -0.156 2  0.156 2  0.377 1]

G.U [：， 2]= [-0.353 55，-0.353 55，-0.353 55，-0.353 55，

-1.1e-16，-1.7e-16，7.2e-18，2.7e-17，

0.353 55，0.353 55，0.353 55，0.353 55]

在图5中，用G.U [：， 1]，G.U [：， 2]这两个特征向量作为坐标画出图形。顶点a被绘制在坐标ψ1（a），ψ2（a），使用ψ1为每个顶点提供水平坐标，ψ2为每个顶点提供垂直坐标。然后把这些边画成直线就得到了图5中的图结构。

4 谱聚类特性

将图像根据Ncut算法的构图规则构成图结构之后，图的拉普拉斯矩阵的特征向量在图像中展示除了如图6所示的特性，其最小非平凡特征向量实现了图像的分割，结果如

图6（c）所示，其次小非平凡特征向量对剩余区域进行再次分割，结果如图6（d）所示。

5 结 语

本文分别从频域特性、重建结构特性及谱聚类特性三方面分析了图拉普拉斯矩阵谱特性，并基于MATLAB对其结果进行了仿真。实验结果展示了图拉普拉斯矩阵内在优美的谱特性，为基于谱域的图结构处理提供了依据，并为图卷积神经网络对图拉普拉斯矩阵的谱特性应用提供了参考。

参考文献

[1]谢德喜.拉普拉斯变换在工程方程中的应用[J]. 天津轻工业学院学报，1990（1）：103-110.

[2]刘颖，张艳邦.拉普拉斯矩阵在聚类中的应用[J]. 天津科技大学学报，2019（3）：76-80.

[3] SHI J，MALIK J. Normalized cuts and image segmentation [J]. IEEE transactions on pattern analysis and machine intelligence，2000，22（8）：888-905.

[4]蔡晓妍，戴冠中，杨黎斌.谱聚类算法综述[J].计算机科学，2008，35（7）：14-18.

[5]胡乾坤，丁世飞.局部相似性优化的 p-谱聚类算法[J].计算机科学与探索，2018，12（3）：462-471.

[6] KIPF T N，WELLING M. Semi-supervised classification with graph convolutional networks [J]. ICLR，2016，1：1-13.

[7]王万良，朱文博，郑建炜.基于ADMM的拉普拉斯约束表示型聚类算法[J].浙江工业大学学报，2018（4）：363-368.

[8]卢鹏丽，才彦姣.一种自动确定特征向量与类别数目的谱聚类算法[J].兰州理工大学学报，2018（2）：90-94.

[9]王贝贝.改进的谱聚类算法及其应用研究[D].太原：中北大学，2018.

[10]刘健辰，时光.基于推广的概率分布区间分解法的时滞系统稳定性分析[J].控制与决策，2017（10）：1824-1830.