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

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