手把手解釋實現(xiàn)頻譜圖卷積

雷鋒網(wǎng)AI科技評論編者按：先來回顧一下什么是圖。圖G是由有向或無向邊連接的一組節(jié)點(頂點)組成的。在這篇文章中，我將假設(shè)一個帶有N個節(jié)點的無向圖G。圖中的每個節(jié)點都有一個C維特征向量，所有節(jié)點的特征表示為N×C維矩陣X???。圖的一側(cè)表示為N×N矩陣A，當(dāng)在其中輸入A??，表示節(jié)點I是否與節(jié)點j相連時，該矩陣稱為相鄰矩陣。

圖1

左邊的傅里葉基(DFT矩陣)，其中每列或每行是基向量，重新整合成28×28(如右邊所示)，即右邊顯示20個基向量。傅里葉基利用計算頻譜卷積進行信號處理。如圖所示，本文采用的正是拉普拉斯基方法。

圖2：在N=5和N=6節(jié)點的無向圖中節(jié)點的順序是任意的。

對于圖的頻譜分析對于圖聚類、社區(qū)發(fā)現(xiàn)和無監(jiān)督學(xué)習(xí)任務(wù)等方面都是有用的。在這篇文章中，我主要描述了Bruna等人在2014年，ICLR 2014的工作中，他們將頻譜分析和卷積神經(jīng)網(wǎng)絡(luò)(ConvNets)相結(jié)合，產(chǎn)生了頻譜圖卷積網(wǎng)絡(luò)，可以有監(jiān)督的方式進行訓(xùn)練，用于圖的分類任務(wù)中。

盡管與空間圖卷積方法相比，頻譜圖卷積目前還不太常用，但了解頻譜圖卷積的工作原理仍有助于避免產(chǎn)生和其他方法同樣的問題。 另外，在結(jié)論中我提到了我最近在做的一些工作，能使頻譜圖卷積更具優(yōu)勢。

1.  拉普拉斯基以及一些物理學(xué)原理

雖然“頻譜”聽起來可能很復(fù)雜，但我們只需要知道它是將信號/音頻/圖像/圖分解成簡單元素(微波、圖)的組合就夠了。為了在分解過后得到一些好的性質(zhì)，這些簡單元素通常是正交的，就是與相互線性無關(guān)，因此就形成了一個基。

當(dāng)我們討論信號或者圖像處理中的“頻譜”時，指的是傅里葉變換，它為我們提供了不同頻率的正弦波和余弦波的特定基 (DFT矩陣，例如Python中的scip.linalg.dft)，這樣我們就可以將信號或是圖像表示為這些波的總和。但是當(dāng)我們討論圖和神經(jīng)網(wǎng)絡(luò)圖(GNN)時，“頻譜”意味著拉普拉斯圖L的特征分解，你可以認(rèn)為拉普拉斯圖L是一種特殊的相鄰矩陣A，而特征分解就是為了找到構(gòu)成我們的圖基本正交分量的一種方法。

拉普拉斯圖直觀地顯示了當(dāng)我們在節(jié)點I中放置一些“潛在元素”時，“能量”在圖上的傳播方向和擴散程度。在數(shù)學(xué)和物理學(xué)中，拉普拉斯基的一個典型應(yīng)用是解決信號(波)如何在動態(tài)系統(tǒng)中傳播。如果相鄰的值沒有突然的變化，那擴散就是很平滑的，如下面的動圖所示。

圖3

基于拉普拉斯圖的規(guī)則，網(wǎng)格圖中某些信號的擴散。基本上，計算這些動力需要節(jié)點(像素)中的拉普拉斯算子和初始值，即與高強度(熱)對應(yīng)的紅色和黃色像素相對應(yīng)。

在后面的文章中，我將假設(shè)“對稱歸一化拉普拉斯算子”，它經(jīng)常用于圖神經(jīng)網(wǎng)絡(luò)中，因為它是規(guī)范化的，所以當(dāng)你疊加許多層圖時，節(jié)點特征會以一種更平滑的方式傳播，不會造成數(shù)據(jù)爆炸，特征值或梯度也不會消失。原因是它是基于圖的相鄰矩陣A進行計算的，可以在幾行Python代碼中完成，如下所示：

圖4

我們假設(shè)A是對稱的，即A=A?，并且我們的圖應(yīng)該是無向的，否則節(jié)點度不能明確的定義，在計算拉普拉斯算子時必須做一些假設(shè)。相鄰矩陣A的一個性質(zhì)是?(矩陣乘積取n次)暴露了節(jié)點之間的n-hop連接。

我們生成了三個圖，接下來可以觀察它們的相鄰矩陣，拉普拉斯算子以及它們的功率。

圖5

相鄰矩陣，拉普拉斯算子及隨機功率圖(左)，“星狀圖”(中間)和“路徑圖”(右)。我將A 2規(guī)范化，使得每行之和等于1，從而得到了一個關(guān)于2-hop連接的概率解釋。注意，拉普拉斯算子及其功率是對稱矩陣，這使得特征分解更容易，并且便于在深度圖網(wǎng)絡(luò)中進行特征傳播。

例如，假設(shè)中間的星狀圖是由金屬制成的，這樣它就能很好地傳遞熱量。然后，如果我們開始加熱節(jié)點0(深藍(lán)色)，熱量將以拉普拉斯算子定義的方式傳播到其他節(jié)點。在所有的邊都相等這種星狀圖的特殊情況下，熱量會均勻地擴散到所有其他節(jié)點，但由于結(jié)構(gòu)不同，并不適用于其他圖。

在計算機視覺和機器學(xué)習(xí)的背景下，拉普拉斯圖定義了如果我們疊加多個圖神經(jīng)層，該如何更新節(jié)點特征。類似于我的教程的第一部分，為了從計算機視覺的角度理解頻譜圖卷積，我將使用MNIST數(shù)據(jù)集，它在28×28的規(guī)則網(wǎng)格圖上定義圖像。

圖6

MNIST圖像定義了28×28的規(guī)則網(wǎng)格特征X(左)、相鄰矩陣A(中間)和拉普拉斯算子(右)。拉普拉斯圖看起來像一個單位矩陣的原因是該圖有相當(dāng)多的節(jié)點(784)，因此在歸一化之后，對角線外的值比1小得多。

2.  卷積

在信號處理中，可以看出空間域中的卷積是頻域的乘積。(也稱為卷積定理)同樣的定理也適用于圖。在信號處理中，為了將信號轉(zhuǎn)換到頻域，我們使用離散傅里葉變換，它基本上是信號與特殊矩陣(基，DFT矩陣)的矩陣乘法。由于是在這樣的基礎(chǔ)上假設(shè)了一個規(guī)則的網(wǎng)格，

所以我們不能用它來處理不規(guī)則圖，這是一個典型的例子。相反，我們使用了一個更通用的基，即拉普拉斯圖L的特征向量V，它可以通過特征分解得到：l=VΛV?，其中Λ是L的特征值。

PCA與拉普拉斯圖的特征分解。在實際計算頻譜圖卷積時，只需使用與最小特征值相對應(yīng)的幾個特征向量。乍一看，它似乎與計算機視覺主成分分析(PCA)中常用的策略相反，在PCA中，我們更擅長處理最大特征值對應(yīng)的特征向量。然而，這種差異僅僅是因為計算上述拉普拉斯算子采用了反證法，因此用PCA計算的特征值與拉普拉斯圖的特征值成反比(正式分析見本文)。還請注意，PCA應(yīng)用于數(shù)據(jù)集的協(xié)方差矩陣，目的是提取最大的異常因子，也就是數(shù)據(jù)變化最大的維度，比如特征面。這種變化是由特征值來測量的，因此最小的特征值實際上對應(yīng)于噪聲或“假”特征，這些特征在應(yīng)用中被認(rèn)為是無用的，甚至是有害的。

圖7：MNIST數(shù)據(jù)集的特征值(降序)和對應(yīng)的特征向量。

將拉普拉斯圖的特征分解應(yīng)用于單圖，提取節(jié)點的子圖或集群(群落)，特征值告訴我們許多關(guān)于圖連通性的信息。在下面的例子中，我將使用對應(yīng)20個最小特征值的特征向量，假設(shè)20比節(jié)點N的數(shù)量小得多(在MNIST情況下，N=784)。為了求左下的特征值和特征向量，我使用了一個28×28的正則圖，而在右邊我按照Bruna等人的實驗，在28×28的規(guī)則網(wǎng)格上的400個隨機位置上采樣構(gòu)造不規(guī)則圖(詳見他們的論文)。

圖8

拉普拉斯圖 L的特征值Λ(底部)和特征向量V(頂部)。根據(jù)Bruna等人2014年在ICLR 2014(右)的實驗，對一個規(guī)則的28×28網(wǎng)格(左)和400個點進行隨機采樣。給出了對應(yīng)于20個最小特征值的特征向量。特征向量在左側(cè)為784維，右側(cè)為400維，V分別為784×20和400×20。在左側(cè)的20個特征向量中，每個特征向量被重新更改為28×28，而在右側(cè)，將400維特征向量更改為28×28，為缺失的節(jié)點添加白色像素。因此，每個特征向量中的每個像素對應(yīng)于一個節(jié)點或一個缺失節(jié)點(右側(cè)為白色)。這些特征向量可以看作是我們分解圖形的基礎(chǔ)。

因此，給定拉普拉斯圖L，節(jié)點特征X和濾波器W頻譜，在Python頻譜卷積圖上看起來非常簡單：

圖9

公式：

圖10：頻譜圖卷積，其中⊙表示按元素方向乘積

假設(shè)我們的節(jié)點特征X???是1維的，例如MNIST像素，但是它可以擴展到C維：我們只需要對每個維度重復(fù)這個卷積，然后在信號或圖像卷積中對C求和。

公式(3)實質(zhì)上與使用傅里葉變換在規(guī)則網(wǎng)格上對信號進行頻譜卷積基本相同，因此給機器學(xué)習(xí)帶來了一些問題：

可訓(xùn)練權(quán)重(濾波器)W頻譜的維數(shù)取決于圖中節(jié)點N的數(shù)量。

W頻譜也取決于以特征向量V編碼的圖形結(jié)構(gòu)。

這些問題讓我們很難把這個方法用在具有可變結(jié)構(gòu)的大規(guī)模圖數(shù)據(jù)集中。下文總結(jié)的重點在于解決這些問題和其他可能出現(xiàn)的問題。

3.  頻譜域中的“平滑”擴散

圖11：頻譜域中的平滑擴散會有點不同

Bruna等人是最早通過應(yīng)用頻譜圖分析學(xué)習(xí)卷積濾波器從而解決圖分類問題的研究者之一。使用上述公式(3)學(xué)習(xí)的濾波器作用于整個圖，也就是說它們具有了整體的技術(shù)支持。在計算機視覺環(huán)境中，這與在MNIST上訓(xùn)練的28×28像素的卷積濾波器是一樣的，即濾波器的大小與輸入數(shù)值相同(請注意，我們?yōu)V波器仍然會滑動，只是表現(xiàn)在零填充的圖像上)。對于MNIST來說，我們實際上可以訓(xùn)練這樣的濾波器，但人們普遍認(rèn)為應(yīng)該避免這一點，這樣會加大訓(xùn)練的難度，主要是因為參數(shù)的潛在數(shù)據(jù)爆炸以及訓(xùn)練大型濾波器帶來的困難。雖然這些濾波器確實具有可以捕獲不同圖像之間相同有用特征的能力。

實際上，我使用PyTorch和我的GitHub的代碼成功地訓(xùn)練了這樣一個模型。你應(yīng)該使用mnist_fc.py-模型conv運行它。經(jīng)過100次的訓(xùn)練后，濾波器看起來更像是數(shù)字的混合體：

圖12

具有技術(shù)支持的濾波器通常是用于頻譜卷積。在這種情況下，這些是使用帶有單個卷積層的ConvNet學(xué)習(xí)的28×28濾波器，其后是ReLU，7×7 MaxPooling和完全連接的分類層。 為清楚起見，由于零填充，卷積層的輸出仍為28×28。 令人驚訝的是，該網(wǎng)絡(luò)在MNIST上達到了96.7％。 這可以通過數(shù)據(jù)集的簡單性來解釋。

重申一下，我們通常希望濾波器更小、更局部化(這與我下面要指出的情況不完全相同)。

為了實現(xiàn)這一點，他們提出在頻譜域中滑動濾波器，從而使它們在空間域上更符合頻譜理論。我們的想法是，你可以將公式(3)中的濾波器W頻譜表示為?預(yù)定義函數(shù)(如樣條)的總和，而不是學(xué)習(xí)W的N值，我們要學(xué)習(xí)這個和的K系數(shù)α：

圖13

我們可以將N維濾波器的W頻譜近似為K函數(shù)f的有限和，如下所示。因此，不需要學(xué)習(xí)W頻譜的N值，我們可以學(xué)習(xí)這些函數(shù)的K系數(shù)(α)；當(dāng)K<N_N時，它會變得有效。

雖然fk的維數(shù)取決于節(jié)點N的個數(shù)，但這些函數(shù)是固定的，因此我們不必學(xué)習(xí)它們。我們需要學(xué)到的唯一東西是系數(shù)α，所以W頻譜不再依賴于N，對嗎？

圖14

樣條基用于在頻域中滑動濾波器，從而使濾波器更加局部化。樣條函數(shù)和其他多項式函數(shù)都是有用的，因為我們可以將濾波器表示為它們的和。

為了使公式(4)更加合理，我們希望K<N能將可訓(xùn)練參數(shù)的數(shù)目從N減少到K，更重要的是它能從N中分離出來，以便我們的GNN能夠消化任意大小的圖。我們可以使用不同的基來執(zhí)行這種“擴展”，這取決于我們需要的屬性。例如，上面所示的三次樣條函數(shù)被稱為平滑函數(shù)(也就是說，你不能看到節(jié)點，就是分段樣條多項式各個部分相交的位置)。我在另一篇文章中討論的Chebyshev多項式，在近似函數(shù)之間具有有最小的?∞距離。傅里葉基是變換后保留大部分信號能量的基。大多數(shù)基是正交的，因為具有可以彼此表達的項是多余的。

雷鋒網(wǎng)提示，濾波器W頻譜仍然和輸入的數(shù)值一樣大，但是它們的有效寬度很小。對于MNIST圖像，我們將使用28×28濾波器，其中只有一小部分值的絕對值大于0，這些數(shù)值是無限接近的，即濾波器是在局部有效的，實際上很小，如下所示(左第二)：

圖15

從左到右：(1)輸入圖像。(2)有效寬度小的局部濾波器，多數(shù)數(shù)值值無限接近于0。(3)數(shù)字7的MNIST圖像與濾波器的頻譜圖卷積結(jié)果。(4)利用傅里葉變換進行頻譜卷積的結(jié)果。這些結(jié)果表明，頻譜圖卷積對圖像的應(yīng)用是非常有限的，這可能是由于拉普拉斯基相對于傅里葉基的空間結(jié)構(gòu)較弱所致。

圖16

僅用V：X‘=V V?X的M分量對MNIST圖像進行傅里葉和拉普拉斯圖的重建。我們可以看到，基壓縮了圖像中不同的模式(傅里葉情況下的定向邊緣和拉普拉斯情況下的全局模式)。這使得上述卷積的結(jié)果不同。

總之，在頻譜域中進行平滑處理使Bruna等人了解了更多的局部濾波器信息。這種濾波器的模型可以獲得與模型相似的結(jié)果，無需平滑化，但可訓(xùn)練參數(shù)卻少得多，因為濾波器的大小與輸入圖的大小無關(guān)，這對于將模型縮放到大型圖的數(shù)據(jù)集是很重要的。然而，學(xué)習(xí)的濾波器W頻譜仍然依賴于特征向量V，這使得將該模型應(yīng)用于可變圖結(jié)構(gòu)的數(shù)據(jù)集具有很大的挑戰(zhàn)性。

總結(jié)

盡管原始頻譜圖卷積方法存在諸多不足，但由于頻譜濾波器能夠更好地捕捉圖中全局的復(fù)雜模式，因此在某些應(yīng)用中依然非常具有競爭力，而GCN(Kipf&Wling，ICLR，2017)等局部方法不能在深層網(wǎng)絡(luò)中疊加。例如，Liao等人發(fā)表的兩篇ICLR 2019論文。 “LanczosNet”和Xu等人在“微波神經(jīng)網(wǎng)絡(luò)圖”的基礎(chǔ)上，解決了頻譜圖卷積存在的一些不足，在預(yù)測分子性質(zhì)和節(jié)點分類方面取得了很好的效果。Levie等人2018年在“CayleyNets”上的另一項研究發(fā)現(xiàn)，它在節(jié)點分類、矩陣完成(推薦系統(tǒng))和社區(qū)檢測方面表現(xiàn)出了很強的性能。因此，根據(jù)你的應(yīng)用程序和基礎(chǔ)設(shè)施，頻譜圖卷積可能是一個不錯的選擇。

原文鏈接：https://towardsdatascience.com/spectral-graph-convolution-explained-and-implemented-step-by-step-2e495b57f801（雷鋒網(wǎng)注）

本文轉(zhuǎn)自雷鋒網(wǎng)，如需轉(zhuǎn)載請至雷鋒網(wǎng)官網(wǎng)申請授權(quán)。

原文章地址為手把手解釋實現(xiàn)頻譜圖卷積