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

李社蕾，楊博雄，陸嬌嬌

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

0 引 言

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

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

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

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

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

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

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

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

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)

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

(2)

其中，ω與特征值密切相關。

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

2.2 譜圖傅里葉變換

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

2.2.1 圖上的拉普拉斯算子

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

(3)

從公式上看，含義很明確，為所有非混合二階偏導數(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é)點i的值。類比圖像中f(x,y)即為f在f(x,y)處的值，對于任意節(jié)點i，對i節(jié)點進行微擾，它可能變?yōu)槿我庖粋€與它相鄰的節(jié)點j∈Ni，其中Ni表示節(jié)點i的一階鄰域節(jié)點的集合。

所以對于Graph來說，其拉普拉斯算子如下：

(5)

上式中j∈Ni可以去掉，因為節(jié)點i和j如果不直接相鄰，則Wij=0。

繼續(xù)簡化一下：

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

(6)

即：

Δf=(A-Df)i

對于任意i都成立，則：

-Δf=(D-Af)i

(7)

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

對于無向圖，其拉普拉斯算子為實對稱矩陣，它的特征向量兩兩正交，并且很容易證明其特征值全部大于等于0，即0=λ1≤λ2≤…≤λn，這樣就找到了圖上的一組基。

2.2.2 譜圖傅里葉變換

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

(8)

其中，i為第i個頂點；λ為第l個特征值；u為第個特征向量；f為待變換信號(向量)，f尖為其對應的傅里葉變換，f和f尖與頂點i一一對應。

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

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

(9)

逆變換形式為：

(10)

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

圖2 path(10個節(jié)點)圖鄰接關系及圖結(jié)構(gòu)

圖3 path圖的譜圖傅里葉譜

3 譜圖小波基分析研究

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

(11)

采用反傅里葉變換得到：

(12)

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

(13)

在圖域中顯式地展開此項為：

(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ù)也可以直接從小波算子中實現(xiàn)，如：

(16)

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

(17)

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

ψs=UGsUT

(18)

譜圖小波逆變換基為：

ψ-s=UG-sUT

(19)

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

4 實驗結(jié)果與分析

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

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

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

5 結(jié)束語

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