研究图拉普拉斯矩阵的谱域特性.docx

研究图拉普拉斯矩阵的谱域特性图拉普拉斯矩阵也称为导纳矩阵,作为图的矩阵表示,在工程中应用非常广泛[1]拉普拉斯矩阵又叫作离散拉普拉斯算子,在谱聚类方面,拉普拉斯矩阵被应用到聚类分析中,聚类问题从图的角度看就是对图的分割问题[2,3]因此,出现了一种谱聚类算法,该算法的核心思想是把样本空间的聚类问题转化为无向图G最优划分问题[4,5,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所示图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]与每个顶点按正负交替出现这些高频特征向量可能与图着色和寻找独立集的问题有关图2path图邻接关系和图结构图3path图的部分特征谱3、重建图结构特性通常可以使用低频特征值来得到图结构,3×4网格图的图邻接关系和图结构如图4所示它的前两个为非平凡特征向量,观察发现它们可能为顶点提供坐标而重构图结构图4grid图邻接关系和图结构在图5中,用G.U[:,1],G.U[:,2]这两个特征向量作为坐标画出图形顶点a被绘制在坐标ψ1(a),ψ2(a),使用ψ1为每个顶点提供水平坐标,ψ2为每个顶点提供垂直坐标然后把这些边画成直线就得到了图5中的图结构图5grid图的部分特征谱4、谱聚类特性将图像根据Ncut算法的构图规则构成图结构之后,图的拉普拉斯矩阵的特征向量在图像中展示除了如图6所示的特性,其最小非平凡特征向量实现了图像的分割,结果如图6(c)所示,其次小非平凡特征向量对剩余区域进行再次分割,结果如图6(d)所示。

图6谱聚类用于图像的分割5、结语本文分别从频域特性、重建结构特性及谱聚类特性三方面分析了图拉普拉斯矩阵谱特性,并基于MATLAB对其结果进行了仿真实验结果展示了图拉普拉斯矩阵内在优美的谱特性,为基于谱域的图结构处理提供了依据,并为图卷积神经网络对图拉普拉斯矩阵的谱特性应用提供了参考参考文献：[1]谢德喜.拉普拉斯变换在工程方程中的应用[J].天津轻工业学院学报,1990(1):103-110.[2]刘颖,张艳邦.拉普拉斯矩阵在聚类中的应用[J].天津科技大学学报,2019(3):76-80.[4]蔡晓妍,戴冠中,杨黎斌.谱聚类算法综述[J].计算机科学,2008,35(7):14-18.[5]胡乾坤,丁世飞.局部相似性优化的p-谱聚类算法[J].计算机科学与探索,2018,12(3):462-471.[7]王万良,朱文博,郑建炜.基于ADMM的拉普拉斯约束表示型聚类算法[J].浙江工业大学学报,2018(4):363-368.[8]卢鹏丽,才彦姣.一种自动确定特征向量与类别数目的谱聚类算法[J].兰州理工大学学报,2018(2):90-94.[9]王贝贝.改进的谱聚类算法及其应用研究[D].太原:中北大学,2018.[10]刘健辰,时光.基于推广的概率分布区间分解法的时滞系统稳定性分析[J].控制与决策,2017(10):1824-1830.李社蕾,陆娇娇.图拉普拉斯矩阵谱特性分析[J].物联网技术,2020,10(06):92-93+97.基金:海南省自然科学基金资助项目(619MS076).。