譜圖傅里葉變換與譜圖小波變換基分析研究

李社蕾，楊博雄，陸嬌嬌

(1.三亞學(xué)院 信息與智能工程學(xué)院，海南 三亞 572022；2.三亞學(xué)院 陳國(guó)良院士工作站，海南 三亞 572022)

0 引 言

在現(xiàn)實(shí)世界中，大量數(shù)據(jù)是以圖或者網(wǎng)絡(luò)的形式存在的，比如社交網(wǎng)絡(luò)、知識(shí)圖譜、蛋白質(zhì)相互作用網(wǎng)、世界貿(mào)易網(wǎng)等等。2012年，Imagenet圖像識(shí)別大賽中，Hinton組的Alexnet[1]引入了全新的深層結(jié)構(gòu)和dropout方法，將錯(cuò)誤率從25%以上提升至15%，顛覆了圖像識(shí)別領(lǐng)域。圖數(shù)據(jù)結(jié)構(gòu)的研究者們開始嘗試將卷積神經(jīng)網(wǎng)絡(luò)泛化后應(yīng)用在這樣的數(shù)據(jù)集上，就產(chǎn)生了圖卷積神經(jīng)網(wǎng)絡(luò)，比如GNN、GCN、GAE、GRNN等。

傅里葉變換和小波變換在數(shù)字圖像及信號(hào)處理領(lǐng)域應(yīng)用非常成功[2]，諸多研究者也已將傅里葉變換、二進(jìn)小波和正交小波泛化到了圖結(jié)構(gòu)上，Kipf & Welling[3]提出的GCN利用圖上的傅里葉變換，由卷積定理，實(shí)現(xiàn)了譜圖傅里葉變換的卷積快速算法，Hammond等[4]將二進(jìn)小波泛化到了圖結(jié)構(gòu)上，Xu B[5]等利用譜圖小波變換，并結(jié)合熱擴(kuò)散理論[6-7]實(shí)現(xiàn)了譜圖小波變換的卷積快速算法[8]。迄今為止，譜圖理論在圖卷積神經(jīng)網(wǎng)絡(luò)應(yīng)用中[9-12]僅僅是為了解決在圖結(jié)構(gòu)上做卷積的問題，沒有真正發(fā)揮譜圖理論——這一強(qiáng)大理論體系的作用，同時(shí)也大大限制了圖卷積神經(jīng)網(wǎng)絡(luò)性能的發(fā)揮。因此，該文結(jié)合數(shù)據(jù)集(Coar)在分析其圖結(jié)構(gòu)的基礎(chǔ)上，對(duì)譜圖傅里葉變換與譜圖小波變換基進(jìn)行研究，為譜圖小波變換和譜圖傅里葉變換更深入的與圖卷積神經(jīng)網(wǎng)絡(luò)結(jié)合提供參考。

1 引文數(shù)據(jù)集Cora圖結(jié)構(gòu)分析

1.1 Cora數(shù)據(jù)集分析

引文數(shù)據(jù)集Cora的圖結(jié)構(gòu)是由論文和論文之間的關(guān)系構(gòu)成的網(wǎng)絡(luò)，其中關(guān)系包括引用關(guān)系、共同作者等，每篇論文作為一個(gè)節(jié)點(diǎn)，關(guān)系作為邊，就形成了天然的圖結(jié)構(gòu)。在Cora數(shù)據(jù)集中，有2 708個(gè)節(jié)點(diǎn)，有5 268條邊，構(gòu)成無(wú)向圖，節(jié)點(diǎn)特征維數(shù)1 433，共7類標(biāo)簽，其圖結(jié)構(gòu)如圖1所示。

圖1 Cora數(shù)據(jù)集圖結(jié)構(gòu)

1.2 Cora數(shù)據(jù)集加載

在Pytorch和Pytorch Geometric(PyG)框架下，加載Cora數(shù)據(jù)集的代碼是很簡(jiǎn)單的，具體代碼如下：

import os

import os.path as osp

from torch_geometric.datasets import Planetoid

import torch_geometric.transforms as T

dataset='Cora'

path=osp.join(osp.dirname(osp.realpath('__file__')), 'data', dataset)

##加載數(shù)據(jù)集

dataset=Planetoid(path, dataset, T.NormalizeFeatures())

data=dataset[0]

2 譜圖傅里葉基分析研究

2.1 傳統(tǒng)傅里葉變換

根據(jù)傳統(tǒng)傅里葉變換[13]：

(1)

即，信號(hào)f(t)與e-iωt為基函數(shù)的積分，這組基函數(shù)從數(shù)學(xué)上看e-iωt是拉普拉斯算子的本征函數(shù)，因?yàn)閑-iωt滿足：

(2)

其中，ω與特征值密切相關(guān)。

由傳統(tǒng)傅里葉變換可知，如果能夠在圖上找到一組和e-iωt等價(jià)的基向量，就可以實(shí)現(xiàn)圖上的傅里葉變換。

2.2 譜圖傅里葉變換

為了在圖上尋找一組實(shí)現(xiàn)傅里葉變換的基向量，需要去圖上尋找圖的拉普拉斯算子。

2.2.1 圖上的拉普拉斯算子

傳統(tǒng)拉普拉斯算子定義如下：

(3)

從公式上看，含義很明確，為所有非混合二階偏導(dǎo)數(shù)的和。下面分析拉普拉斯算子在數(shù)字圖像處理中的近似情況：

[f(x+1,y)+f(x-1,y)-2f(x,y)]+

[f(x,y+1)+f(x,y-1)-2f(x,y)]=

f(x+1,y)+f(x-1,y)+f(x,y+1)+

f(x,y-1)-4f(x,y)

(4)

f=(f1,f2,…,fn)

其中，fi即表示函數(shù)f在節(jié)點(diǎn)i的值。類比圖像中f(x,y)即為f在f(x,y)處的值，對(duì)于任意節(jié)點(diǎn)i，對(duì)i節(jié)點(diǎn)進(jìn)行微擾，它可能變?yōu)槿我庖粋€(gè)與它相鄰的節(jié)點(diǎn)j∈Ni，其中Ni表示節(jié)點(diǎn)i的一階鄰域節(jié)點(diǎn)的集合。

所以對(duì)于Graph來(lái)說(shuō)，其拉普拉斯算子如下：

(5)

上式中j∈Ni可以去掉，因?yàn)楣?jié)點(diǎn)i和j如果不直接相鄰，則Wij=0。

繼續(xù)簡(jiǎn)化一下：

(Af)i-(Df)i=(A-Df)i

(6)

即：

Δf=(A-Df)i

對(duì)于任意i都成立，則：

-Δf=(D-Af)i

(7)

所以圖上的拉普拉斯算子就是：D-A，也稱為拉普拉斯矩陣：L=D-A。

對(duì)于無(wú)向圖，其拉普拉斯算子為實(shí)對(duì)稱矩陣，它的特征向量?jī)蓛烧唬⑶液苋菀鬃C明其特征值全部大于等于0，即0=λ1≤λ2≤…≤λn，這樣就找到了圖上的一組基。

2.2.2 譜圖傅里葉變換

仿照傳統(tǒng)傅里葉定義，得到Graph上的傅里葉變換：

(8)

其中，i為第i個(gè)頂點(diǎn)；λ為第l個(gè)特征值；u為第個(gè)特征向量；f為待變換信號(hào)(向量)，f尖為其對(duì)應(yīng)的傅里葉變換，f和f尖與頂點(diǎn)i一一對(duì)應(yīng)。

利用矩陣乘法將圖上的傅里葉變換推廣到矩陣形式：

即f在圖上的傅里葉變換的矩陣形式為：

(9)

逆變換形式為：

(10)

圖2為包含10個(gè)節(jié)點(diǎn)的path圖，圖鄰接關(guān)系及圖結(jié)構(gòu)如圖2所示，圖的譜圖傅里葉譜如圖3所示，特征值0對(duì)應(yīng)的特征向量為U[:,0]，等價(jià)于傳統(tǒng)傅里葉變換直流成分，特征值小的為低頻成分，特征值大的為高頻成分。

圖2 path(10個(gè)節(jié)點(diǎn))圖鄰接關(guān)系及圖結(jié)構(gòu)

圖3 path圖的譜圖傅里葉譜

3 譜圖小波基分析研究

Hammond[3,14-15]將二進(jìn)小波泛化到了圖結(jié)構(gòu)上，譜圖小波變換由小波算子生成，小波算子是拉普拉斯算子的值函數(shù)。利用連續(xù)泛函微積分可以在Hilbert空間上定義有界自伴線性算子的可積函數(shù)。使用算子的譜表示來(lái)實(shí)現(xiàn)的，在設(shè)置中，它等價(jià)于圖的傅里葉變換。特別地，對(duì)于譜圖小波核g，小波算子Tg=g(L)通過每個(gè)傅里葉模式調(diào)制作用于特定函數(shù)f：

(11)

采用反傅里葉變換得到：

(12)

然后定義尺度為t的小波算子：Tg=g(L)。應(yīng)該強(qiáng)調(diào)的是，即使圖的“空間域”是離散的，但核g的域還是連續(xù)的，因此尺度可以定義為任意正實(shí)數(shù)t。然后通過將這些算子應(yīng)用于單個(gè)頂點(diǎn)上的脈沖，即通過定位這些算子來(lái)實(shí)現(xiàn)譜圖小波。

(13)

在圖域中顯式地展開此項(xiàng)為：

(14)

(n=m?ψt,n(m)≠0,n≠m?ψt,n(m)=0)

形式上，小波系數(shù)是由給定函數(shù)f與這些小波的內(nèi)積產(chǎn)生的，如：

Wf(t,n)=〈ψt,n,f〉

(15)

利用{x}的正交性，可以看出小波系數(shù)也可以直接從小波算子中實(shí)現(xiàn)，如：

(16)

Tgf(n)=Ug(tλ)UTf(n)

(17)

從而得到了譜圖小波變換基ψs=UGsUT，gs=λs，其中Gs=diag{λ1s,λ2s,…,λns}。由于拉普拉斯算子矩陣有0特征值，導(dǎo)致矩陣不可逆，文獻(xiàn)[4]中設(shè)gs=e-λs，是一個(gè)具有尺度參數(shù)s的過濾器內(nèi)核，這里用的熱核，則譜圖小波變換基定義為：

ψs=UGsUT

(18)

譜圖小波逆變換基為：

ψ-s=UG-sUT

(19)

其中，Gs=diag{e-λ1s,e-λ2s,…,e-λns}，不同尺度下小波和擴(kuò)散情況如圖4所示。

4 實(shí)驗(yàn)結(jié)果與分析

本實(shí)驗(yàn)對(duì)Cora數(shù)據(jù)集圖結(jié)構(gòu)的譜圖傅里葉變換譜和譜圖小波變換譜進(jìn)行了仿真，為了方便展示，圖5和圖6分別展示了特征值(λ0,λ1,λ100,λ2707)對(duì)應(yīng)的特征向量的前500個(gè)元素的譜。對(duì)于特征值，λ0,λ1的值都為0，根據(jù)圖1的Coar數(shù)據(jù)集圖結(jié)構(gòu)，可知Coar數(shù)據(jù)集圖結(jié)構(gòu)為非連通圖，圖1的外部存在很多連通子圖，一部分連通子圖只有兩個(gè)節(jié)點(diǎn)組成，從而出現(xiàn)了大量值為0的特征向量，給半監(jiān)督節(jié)點(diǎn)分類帶來(lái)了很大挑戰(zhàn)。另外根據(jù)圖5和圖6可以發(fā)現(xiàn)，譜圖傅里葉變換譜展示了圖的譜域分布情況，特征值小的對(duì)應(yīng)低頻成分，特征值大的對(duì)應(yīng)高頻成分，而譜圖小波變換譜展示了圖結(jié)構(gòu)局部突變特性。實(shí)驗(yàn)表明通過譜圖傅里葉變換和譜圖小波變換可以獲取圖結(jié)構(gòu)的特征信息。

卷積神經(jīng)網(wǎng)絡(luò)泛化到圖結(jié)構(gòu)上，首先考慮的問題就是如何在圖上做卷積，而卷積神經(jīng)神經(jīng)網(wǎng)絡(luò)在對(duì)數(shù)字圖像進(jìn)行處理的時(shí)候，在圖像上做卷積是為了提取特征，不同卷積核提取不同的特征，通過多個(gè)卷積通道，提取圖像多方位的特征進(jìn)行訓(xùn)練，從而在圖像分割、語(yǔ)義分割等方面取得很大成功。卷積神經(jīng)網(wǎng)絡(luò)在圖結(jié)構(gòu)上進(jìn)行泛化時(shí)，可以轉(zhuǎn)換一下思路，可以考慮更有效的圖上提取特征的手段，對(duì)圖結(jié)構(gòu)進(jìn)行訓(xùn)練。

圖6 Cora數(shù)據(jù)集部分譜圖小波變換譜

5 結(jié)束語(yǔ)

通過對(duì)譜圖傅里葉變換與譜圖小波變換基的分析，發(fā)現(xiàn)譜圖傅里葉變換可以提取圖結(jié)構(gòu)高頻成分和低頻成分，譜圖小波變換可以提取圖結(jié)構(gòu)的局部快變成分，兩種變換從不同角度提取圖結(jié)構(gòu)的特征，為圖卷積神經(jīng)網(wǎng)絡(luò)的特征提取方法提供參考。后續(xù)將研究用不同的方式提取圖結(jié)構(gòu)的多方位特征，進(jìn)而提升圖卷積神經(jīng)網(wǎng)絡(luò)的性能。