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

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

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

對于圖的頻譜分析對于圖聚類、社區(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)督的方式進(jìn)行訓(xùn)練，用于圖的分類任務(wù)中。

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

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

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

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

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

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

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

圖4

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

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

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

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

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

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

  2.  卷積 

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

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

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

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

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

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

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

圖9

 公式：

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

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

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

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

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

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

  3.  頻譜域中的“平滑”擴(kuò)散

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

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

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

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

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

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

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

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

圖14：樣條基用于在頻域中滑動濾波器，從而使濾波器更加局部化。樣條函數(shù)和其他多項(xiàng)式函數(shù)都是有用的，因?yàn)槲覀兛梢詫V波器表示為它們的和。

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

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

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

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

總之，在頻譜域中進(jìn)行平滑處理使Bruna等人了解了更多的局部濾波器信息。這種濾波器的模型可以獲得與模型相似的結(jié)果，無需平滑化，但可訓(xùn)練參數(shù)卻少得多，因?yàn)闉V波器的大小與輸入圖的大小無關(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é)點(diǎn)分類方面取得了很好的效果。Levie等人2018年在“CayleyNets”上的另一項(xiàng)研究發(fā)現(xiàn)，它在節(jié)點(diǎn)分類、矩陣完成(推薦系統(tǒng))和社區(qū)檢測方面表現(xiàn)出了很強(qiáng)的性能。因此，根據(jù)你的應(yīng)用程序和基礎(chǔ)設(shè)施，頻譜圖卷積可能是一個(gè)不錯(cuò)的選擇。

在我的關(guān)于計(jì)算機(jī)視覺及其他圖神經(jīng)網(wǎng)絡(luò)教程的另一部分（文章鏈接：https:///tutorial-on-graph-neural-networks-for-computer-vision-and-beyond-part-2-be6d71d70f49）中，我解釋了由Defferrard等人在2016年提出的Chebyshev頻譜圖卷積，它直到現(xiàn)在還是一個(gè)非常強(qiáng)大的基線，它有一些很好的特性，而且很容易實(shí)現(xiàn)，正如我用PyTorch演示的那樣。

原文鏈接：https:///spectral-graph-convolution-explained-and-implemented-step-by-step-2e495b57f801

更多內(nèi)容

「LSTM之父」 Jürgen Schmidhuber訪談：暢想人類和 AI 共處的世界 | WAIC 2019
歷年 AAAI 最佳論文（since 1996）
一份完全解讀：是什么使神經(jīng)網(wǎng)絡(luò)變成圖神經(jīng)網(wǎng)絡(luò)？