手把手解釋實(shí)現頻譜圖卷積

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

圖1

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

圖2：在N=5和N=6節點(diǎn)的無(wú)向圖中節點(diǎn)的順序是任意的。

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

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

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

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

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

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

圖3

基于拉普拉斯圖的規則，網(wǎng)格圖中某些信號的擴散?；旧?，計算這些動(dòng)力需要節點(diǎn)(像素)中的拉普拉斯算子和初始值，即與高強度(熱)對應的紅色和黃色像素相對應。

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

圖4

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

我們生成了三個(gè)圖，接下來(lái)可以觀(guān)察它們的相鄰矩陣，拉普拉斯算子以及它們的功率。

圖5

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

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

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

圖6

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

2.  卷積

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

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

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

圖7：MNIST數據集的特征值(降序)和對應的特征向量。

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

圖8

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

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

圖9

公式：

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

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

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

可訓練權重(濾波器)W頻譜的維數取決于圖中節點(diǎn)N的數量。

W頻譜也取決于以特征向量V編碼的圖形結構。

這些問(wèn)題讓我們很難把這個(gè)方法用在具有可變結構的大規模圖數據集中。下文總結的重點(diǎn)在于解決這些問(wèn)題和其他可能出現的問(wèn)題。

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

圖11：頻譜域中的平滑擴散會(huì )有點(diǎn)不同

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

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

圖12

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

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

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

圖13

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

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

圖14

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

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

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

圖15

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

圖16

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

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

總結

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

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

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

原文章地址為手把手解釋實(shí)現頻譜圖卷積