圖拉普拉斯矩陣譜特性分析

李社蕾 陸嬌嬌

摘 要：卷積神經(jīng)網(wǎng)絡(luò)泛化到圖結(jié)構(gòu)上之后受到很多研究者的關(guān)注，由于譜圖理論的強(qiáng)大支撐，基于譜域的圖卷積神經(jīng)網(wǎng)絡(luò)的研究備受關(guān)注，文中研究圖拉普拉斯矩陣的譜域特性，以及圖拉普拉斯矩陣的特征向量與特征值之間的關(guān)系。通過實(shí)驗(yàn)，驗(yàn)證了圖拉普拉斯矩陣的特征向量矩陣具有的頻譜特性，重建圖結(jié)構(gòu)、圖分割等優(yōu)美的內(nèi)在特性，為圖卷積神經(jīng)網(wǎng)絡(luò)進(jìn)一步研究提供參考。

關(guān)鍵詞：拉普拉斯矩陣;頻譜特性;特征向量;卷積神經(jīng)網(wǎng)絡(luò);圖結(jié)構(gòu)特性;MATLAB

中圖分類號(hào)：TP391文獻(xiàn)標(biāo)識(shí)碼：A文章編號(hào)：2095-1302（2020）06-00-02

0 引 言

圖拉普拉斯矩陣（Laplacian Matrix）也稱為導(dǎo)納矩陣，作為圖的矩陣表示，在工程中應(yīng)用非常廣泛[1]。拉普拉斯矩陣又叫作離散拉普拉斯算子，在譜聚類方面，拉普拉斯矩陣被應(yīng)用到聚類分析中，聚類問題從圖的角度看就是對(duì)圖的分割問題[2-3]。因此，出現(xiàn)了一種譜聚類算法（Spectral Clustering），該算法的核心思想是把樣本空間的聚類問題轉(zhuǎn)化為無向圖G最優(yōu)劃分問題[4-6]。隨著卷積神經(jīng)網(wǎng)絡(luò)在圖結(jié)構(gòu)上泛化，深入理解圖拉普拉斯矩陣物理含義及譜域特性有助于加深對(duì)GCN模型的理解，并為GCN模型進(jìn)一步深入研究及改進(jìn)提供理論參考。

1 拉普拉斯矩陣

拉普拉斯矩陣在圖論中，表示圖的一種矩陣，給定一個(gè)有N個(gè)節(jié)點(diǎn)的簡(jiǎn)單圖無向圖G （V， E， A）。其中，V={v1， v2， ...， vN}

表示所有頂點(diǎn)的集合;E為邊集合，eij=（vi， vj）∈E表示兩個(gè)節(jié)點(diǎn)i和j之間的邊;A為鄰接矩陣，是一個(gè)N×N的矩陣：

令dv表示頂點(diǎn)v的度，普拉普拉斯矩陣L定義如下：

L也可以看作定義在空間函數(shù)上的算子g：V（G）→R滿足

由定義可知：

式中，D=diag （dv1，dv2， ...， dvN ）為圖的度矩陣。簡(jiǎn)單無向圖如圖1所示。

圖中，圖結(jié)構(gòu)是由6個(gè)頂點(diǎn)組成的簡(jiǎn)單無向圖，其度矩陣D、圖1的鄰接矩陣A為：

確定了D和A之后，根據(jù)式（4）就可以得到圖1的拉普拉斯矩陣L：

圖的拉普拉斯矩陣具有如下性質(zhì)：

（1）拉普拉斯矩陣為實(shí)對(duì)稱矩陣，其特征向量構(gòu)成的矩陣為正交陣;

（2）拉普拉斯矩陣是半正定的，有N個(gè)非負(fù)的特征值0=λ0≤λ2≤...≤λN-1，其中最小特征值λ0=0，所對(duì)應(yīng)的特征向量為1;

（3）對(duì)于任意向量f∈Rn，式（7）成立：

2 頻域特性

以path圖為例介紹，圖拉普拉斯矩陣的頻域特性，path圖如圖2所示。圖中有頂點(diǎn)集合{1， 2， ...， 10}，邊（i， i+1），1≤i≤N，共10個(gè)頂點(diǎn)，9條邊。圖3為path圖的部分特征譜。由圖可知，特征值0對(duì)應(yīng)的特征向量U [：， 0]為常向量，對(duì)應(yīng)傅里葉變換的直流分量，特征值λ1，λ2對(duì)應(yīng)特征向量，U [：， 1]，U [：， 2]為低頻特征向量。它們描繪出的曲線類似于弦的低頻振動(dòng)模式，路徑圖可以看作是弦的離散化，拉普拉斯矩陣對(duì)應(yīng)于拉普拉斯算子的離散化;相反，最高頻率的特征值對(duì)應(yīng)的特征向量U [：， N-1]與每個(gè)頂點(diǎn)按正負(fù)交替出現(xiàn)。這些高頻特征向量可能與圖著色和尋找獨(dú)立集的問題有關(guān)。

3 重建圖結(jié)構(gòu)特性

通?？梢允褂玫皖l特征值來得到圖結(jié)構(gòu)，3×4網(wǎng)格圖的圖鄰接關(guān)系和圖結(jié)構(gòu)如圖4所示。它的前兩個(gè)為非平凡特征向量，觀察發(fā)現(xiàn)它們可能為頂點(diǎn)提供坐標(biāo)而重構(gòu)圖結(jié)構(gòu)。

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]這兩個(gè)特征向量作為坐標(biāo)畫出圖形。頂點(diǎn)a被繪制在坐標(biāo)ψ1（a），ψ2（a），使用ψ1為每個(gè)頂點(diǎn)提供水平坐標(biāo)，ψ2為每個(gè)頂點(diǎn)提供垂直坐標(biāo)。然后把這些邊畫成直線就得到了圖5中的圖結(jié)構(gòu)。

4 譜聚類特性

將圖像根據(jù)Ncut算法的構(gòu)圖規(guī)則構(gòu)成圖結(jié)構(gòu)之后，圖的拉普拉斯矩陣的特征向量在圖像中展示除了如圖6所示的特性，其最小非平凡特征向量實(shí)現(xiàn)了圖像的分割，結(jié)果如

圖6（c）所示，其次小非平凡特征向量對(duì)剩余區(qū)域進(jìn)行再次分割，結(jié)果如圖6（d）所示。

5 結(jié) 語

本文分別從頻域特性、重建結(jié)構(gòu)特性及譜聚類特性三方面分析了圖拉普拉斯矩陣譜特性，并基于MATLAB對(duì)其結(jié)果進(jìn)行了仿真。實(shí)驗(yàn)結(jié)果展示了圖拉普拉斯矩陣內(nèi)在優(yōu)美的譜特性，為基于譜域的圖結(jié)構(gòu)處理提供了依據(jù)，并為圖卷積神經(jīng)網(wǎng)絡(luò)對(duì)圖拉普拉斯矩陣的譜特性應(yīng)用提供了參考。

參考文獻(xiàn)

[1]謝德喜.拉普拉斯變換在工程方程中的應(yīng)用[J]. 天津輕工業(yè)學(xué)院學(xué)報(bào)，1990（1）：103-110.

[2]劉穎，張艷邦.拉普拉斯矩陣在聚類中的應(yīng)用[J]. 天津科技大學(xué)學(xué)報(bào)，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].計(jì)算機(jī)科學(xué)，2008，35（7）：14-18.

[5]胡乾坤，丁世飛.局部相似性優(yōu)化的 p-譜聚類算法[J].計(jì)算機(jī)科學(xué)與探索，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].浙江工業(yè)大學(xué)學(xué)報(bào)，2018（4）：363-368.

[8]盧鵬麗，才彥姣.一種自動(dòng)確定特征向量與類別數(shù)目的譜聚類算法[J].蘭州理工大學(xué)學(xué)報(bào)，2018（2）：90-94.

[9]王貝貝.改進(jìn)的譜聚類算法及其應(yīng)用研究[D].太原：中北大學(xué)，2018.

[10]劉健辰，時(shí)光.基于推廣的概率分布區(qū)間分解法的時(shí)滯系統(tǒng)穩(wěn)定性分析[J].控制與決策，2017（10）：1824-1830.