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

李社蕾，楊博雄，陸嬌嬌

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

0 引 言

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

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

1 引文數(shù)據(jù)集Cora圖結構分析

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

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

圖1 Cora數(shù)據(jù)集圖結構

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圖，圖鄰接關系及圖結構如圖2所示，圖的譜圖傅里葉譜如圖3所示，特征值0對應的特征向量為U[:,0]，等價于傳統(tǒng)傅里葉變換直流成分，特征值小的為低頻成分，特征值大的為高頻成分。

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

圖3 path圖的譜圖傅里葉譜

3 譜圖小波基分析研究

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

(11)

采用反傅里葉變換得到：

(12)

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

(13)

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

(14)

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

形式上，小波系數(shù)是由給定函數(shù)f與這些小波的內積產(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的過濾器內核，這里用的熱核，則譜圖小波變換基定義為：

ψs=UGsUT

(18)

譜圖小波逆變換基為：

ψ-s=UG-sUT

(19)

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

4 實驗結果與分析

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

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

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

5 結束語

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