圖1：左邊的傅立葉基(DFT矩陣)，其中每列或每行是基向量，重新整合成28×28(如右邊所示)，即右邊顯示20個基向量。傅立葉基利用計算頻譜卷積進行信號處理。如圖所示，本文採用的正是拉普拉斯基方法。
雷鋒網(公眾號：雷鋒網)AI科技評論編者按：先來回顧一下什麼是圖。圖G是由有向或無向邊連接的一組節點(頂點)組成的。在這篇文章中，我將假設一個帶有N個節點的無向圖G。圖中的每個節點都有一個C維特徵向量，所有節點的特徵表示為N×C維矩陣X⁽ˡ⁾。圖的一側表示為N×N矩陣A，當在其中輸入Aᵢⱼ，表示節點I是否與節點j相連時，該矩陣稱為相鄰矩陣。
圖2：在N=5和N=6節點的無向圖中節點的順序是任意的。
對於圖的頻譜分析對於圖聚類、社區發現和無監督學習任務等方面都是有用的。在這篇文章中，我主要描述了Bruna等人在2014年，ICLR 2014的工作中，他們將頻譜分析和卷積神經網絡(ConvNets)相結合，產生了頻譜圖卷積網絡，可以有監督的方式進行訓練，用於圖的分類任務中。
儘管與空間圖卷積方法相比，頻譜圖卷積目前還不太常用，但了解頻譜圖卷積的工作原理仍有助於避免產生和其他方法同樣的問題。 另外，在結論中我提到了我最近在做的一些工作，能使頻譜圖卷積更具優勢。
1. 拉普拉斯基以及一些物理學原理雖然「頻譜」聽起來可能很複雜，但我們只需要知道它是將信號/音頻/圖像/圖分解成簡單元素(微波、圖)的組合就夠了。為了在分解過後得到一些好的性質，這些簡單元素通常是正交的，就是與相互線性無關，因此就形成了一個基。
當我們討論信號或者圖像處理中的「頻譜」時，指的是傅立葉變換，它為我們提供了不同頻率的正弦波和餘弦波的特定基 (DFT矩陣，例如Python中的scip.linalg.dft)，這樣我們就可以將信號或是圖像表示為這些波的總和。但是當我們討論圖和神經網絡圖(GNN)時，「頻譜」意味著拉普拉斯圖L的特徵分解，你可以認為拉普拉斯圖L是一種特殊的相鄰矩陣A，而特徵分解就是為了找到構成我們的圖基本正交分量的一種方法。
拉普拉斯圖直觀地顯示了當我們在節點I中放置一些「潛在元素」時，「能量」在圖上的傳播方向和擴散程度。在數學和物理學中，拉普拉斯基的一個典型應用是解決信號(波)如何在動態系統中傳播。如果相鄰的值沒有突然的變化，那擴散就是很平滑的，如下面的動圖所示。
圖3：基於拉普拉斯圖的規則，網格圖中某些信號的擴散。基本上，計算這些動力需要節點(像素)中的拉普拉斯算子和初始值，即與高強度(熱)對應的紅色和黃色像素相對應。
在後面的文章中，我將假設「對稱歸一化拉普拉斯算子」，它經常用於圖神經網絡中，因為它是規範化的，所以當你疊加許多層圖時，節點特徵會以一種更平滑的方式傳播，不會造成數據爆炸，特徵值或梯度也不會消失。原因是它是基於圖的相鄰矩陣A進行計算的，可以在幾行Python代碼中完成，如下所示：
圖4
我們假設A是對稱的，即A=Aᵀ，並且我們的圖應該是無向的，否則節點度不能明確的定義，在計算拉普拉斯算子時必須做一些假設。相鄰矩陣A的一個性質是ⁿ(矩陣乘積取n次)暴露了節點之間的n-hop連接。
我們生成了三個圖，接下來可以觀察它們的相鄰矩陣，拉普拉斯算子以及它們的功率。
圖5：相鄰矩陣，拉普拉斯算子及隨機功率圖(左)，「星狀圖」(中間)和「路徑圖」(右)。我將A 2規範化，使得每行之和等於1，從而得到了一個關於2-hop連接的概率解釋。注意，拉普拉斯算子及其功率是對稱矩陣，這使得特徵分解更容易，並且便於在深度圖網絡中進行特徵傳播。
例如，假設中間的星狀圖是由金屬製成的，這樣它就能很好地傳遞熱量。然後，如果我們開始加熱節點0(深藍色)，熱量將以拉普拉斯算子定義的方式傳播到其他節點。在所有的邊都相等這種星狀圖的特殊情況下，熱量會均勻地擴散到所有其他節點，但由於結構不同，並不適用於其他圖。
在計算機視覺和機器學習的背景下，拉普拉斯圖定義了如果我們疊加多個圖神經層，該如何更新節點特徵。類似於我的教程的第一部分，為了從計算機視覺的角度理解頻譜圖卷積，我將使用MNIST數據集，它在28×28的規則網格圖上定義圖像。
圖6：MNIST圖像定義了28×28的規則網格特徵X(左)、相鄰矩陣A(中間)和拉普拉斯算子(右)。拉普拉斯圖看起來像一個單位矩陣的原因是該圖有相當多的節點(784)，因此在歸一化之後，對角線外的值比1小得多。
2. 卷積在信號處理中，可以看出空間域中的卷積是頻域的乘積。(也稱為卷積定理)同樣的定理也適用於圖。在信號處理中，為了將信號轉換到頻域，我們使用離散傅立葉變換，它基本上是信號與特殊矩陣(基，DFT矩陣)的矩陣乘法。由於是在這樣的基礎上假設了一個規則的網格，
所以我們不能用它來處理不規則圖，這是一個典型的例子。相反，我們使用了一個更通用的基，即拉普拉斯圖L的特徵向量V，它可以通過特徵分解得到：l=VΛVᵀ，其中Λ是L的特徵值。
PCA與拉普拉斯圖的特徵分解。在實際計算頻譜圖卷積時，只需使用與最小特徵值相對應的幾個特徵向量。乍一看，它似乎與計算機視覺主成分分析(PCA)中常用的策略相反，在PCA中，我們更擅長處理最大特徵值對應的特徵向量。然而，這種差異僅僅是因為計算上述拉普拉斯算子採用了反證法，因此用PCA計算的特徵值與拉普拉斯圖的特徵值成反比(正式分析見本文)。還請注意，PCA應用於數據集的協方差矩陣，目的是提取最大的異常因子，也就是數據變化最大的維度，比如特徵面。這種變化是由特徵值來測量的，因此最小的特徵值實際上對應於噪聲或「假」特徵，這些特徵在應用中被認為是無用的，甚至是有害的。
圖7：MNIST數據集的特徵值(降序)和對應的特徵向量。
將拉普拉斯圖的特徵分解應用於單圖，提取節點的子圖或集群(群落)，特徵值告訴我們許多關於圖連通性的信息。在下面的例子中，我將使用對應20個最小特徵值的特徵向量，假設20比節點N的數量小得多(在MNIST情況下，N=784)。為了求左下的特徵值和特徵向量，我使用了一個28×28的正則圖，而在右邊我按照Bruna等人的實驗，在28×28的規則網格上的400個隨機位置上採樣構造不規則圖(詳見他們的論文)。
圖8：拉普拉斯圖 L的特徵值Λ(底部)和特徵向量V(頂部)。根據Bruna等人2014年在ICLR 2014(右)的實驗，對一個規則的28×28網格(左)和400個點進行隨機採樣。給出了對應於20個最小特徵值的特徵向量。特徵向量在左側為784維，右側為400維，V分別為784×20和400×20。在左側的20個特徵向量中，每個特徵向量被重新更改為28×28，而在右側，將400維特徵向量更改為28×28，為缺失的節點添加白色像素。因此，每個特徵向量中的每個像素對應於一個節點或一個缺失節點(右側為白色)。這些特徵向量可以看作是我們分解圖形的基礎。
因此，給定拉普拉斯圖L，節點特徵X和濾波器W頻譜，在Python頻譜卷積圖上看起來非常簡單：
圖9
公式：
圖10：頻譜圖卷積，其中⊙表示按元素方向乘積
假設我們的節點特徵X⁽ˡ⁾是1維的，例如MNIST像素，但是它可以擴展到C維：我們只需要對每個維度重複這個卷積，然後在信號或圖像卷積中對C求和。
公式(3)實質上與使用傅立葉變換在規則網格上對信號進行頻譜卷積基本相同，因此給機器學習帶來了一些問題：
這些問題讓我們很難把這個方法用在具有可變結構的大規模圖數據集中。下文總結的重點在於解決這些問題和其他可能出現的問題。
3. 頻譜域中的「平滑」擴散
圖11：頻譜域中的平滑擴散會有點不同
Bruna等人是最早通過應用頻譜圖分析學習卷積濾波器從而解決圖分類問題的研究者之一。使用上述公式(3)學習的濾波器作用於整個圖，也就是說它們具有了整體的技術支持。在計算機視覺環境中，這與在MNIST上訓練的28×28像素的卷積濾波器是一樣的，即濾波器的大小與輸入數值相同(請注意，我們濾波器仍然會滑動，只是表現在零填充的圖像上)。對於MNIST來說，我們實際上可以訓練這樣的濾波器，但人們普遍認為應該避免這一點，這樣會加大訓練的難度，主要是因為參數的潛在數據爆炸以及訓練大型濾波器帶來的困難。雖然這些濾波器確實具有可以捕獲不同圖像之間相同有用特徵的能力。
實際上，我使用PyTorch和我的GitHub的代碼成功地訓練了這樣一個模型。你應該使用mnist_fc.py-模型conv運行它。經過100次的訓練後，濾波器看起來更像是數字的混合體：
圖12：具有技術支持的濾波器通常是用於頻譜卷積。在這種情況下，這些是使用帶有單個卷積層的ConvNet學習的28×28濾波器，其後是ReLU，7×7 MaxPooling和完全連接的分類層。 為清楚起見，由於零填充，卷積層的輸出仍為28×28。 令人驚訝的是，該網絡在MNIST上達到了96.7％。 這可以通過數據集的簡單性來解釋。
重申一下，我們通常希望濾波器更小、更局部化(這與我下面要指出的情況不完全相同)。
為了實現這一點，他們提出在頻譜域中滑動濾波器，從而使它們在空間域上更符合頻譜理論。我們的想法是，你可以將公式(3)中的濾波器W頻譜表示為?預定義函數(如樣條)的總和，而不是學習W的N值，我們要學習這個和的K係數α： 圖13：我們可以將N維濾波器的W頻譜近似為K函數f的有限和，如下所示。因此，不需要學習W頻譜的N值，我們可以學習這些函數的K係數(α)；當K<N<sub>N</sub>時，它會變得有效。
雖然fk的維數取決於節點N的個數，但這些函數是固定的，因此我們不必學習它們。我們需要學到的唯一東西是係數α，所以W頻譜不再依賴於N，對嗎？
圖14：樣條基用於在頻域中滑動濾波器，從而使濾波器更加局部化。樣條函數和其他多項式函數都是有用的，因為我們可以將濾波器表示為它們的和。
為了使公式(4)更加合理，我們希望K<N能將可訓練參數的數目從N減少到K，更重要的是它能從N中分離出來，以便我們的GNN能夠消化任意大小的圖。我們可以使用不同的基來執行這種「擴展」，這取決於我們需要的屬性。例如，上面所示的三次樣條函數被稱為平滑函數(也就是說，你不能看到節點，就是分段樣條多項式各個部分相交的位置)。我在另一篇文章中討論的Chebyshev多項式，在近似函數之間具有有最小的?∞距離。傅立葉基是變換後保留大部分信號能量的基。大多數基是正交的，因為具有可以彼此表達的項是多餘的。
雷鋒網提示，濾波器W頻譜仍然和輸入的數值一樣大，但是它們的有效寬度很小。對於MNIST圖像，我們將使用28×28濾波器，其中只有一小部分值的絕對值大於0，這些數值是無限接近的，即濾波器是在局部有效的，實際上很小，如下所示(左第二)：
圖15：從左到右：(1)輸入圖像。(2)有效寬度小的局部濾波器，多數數值值無限接近於0。(3)數字7的MNIST圖像與濾波器的頻譜圖卷積結果。(4)利用傅立葉變換進行頻譜卷積的結果。這些結果表明，頻譜圖卷積對圖像的應用是非常有限的，這可能是由於拉普拉斯基相對於傅立葉基的空間結構較弱所致。
圖16：僅用V：X『=V VᵀX的M分量對MNIST圖像進行傅立葉和拉普拉斯圖的重建。我們可以看到，基壓縮了圖像中不同的模式(傅立葉情況下的定向邊緣和拉普拉斯情況下的全局模式)。這使得上述卷積的結果不同。
總之，在頻譜域中進行平滑處理使Bruna等人了解了更多的局部濾波器信息。這種濾波器的模型可以獲得與模型相似的結果，無需平滑化，但可訓練參數卻少得多，因為濾波器的大小與輸入圖的大小無關，這對於將模型縮放到大型圖的數據集是很重要的。然而，學習的濾波器W頻譜仍然依賴於特徵向量V，這使得將該模型應用於可變圖結構的數據集具有很大的挑戰性。
總結：
儘管原始頻譜圖卷積方法存在諸多不足，但由於頻譜濾波器能夠更好地捕捉圖中全局的複雜模式，因此在某些應用中依然非常具有競爭力，而GCN(Kipf&Wling，ICLR，2017)等局部方法不能在深層網絡中疊加。例如，Liao等人發表的兩篇ICLR 2019論文。 「LanczosNet」和Xu等人在「微波神經網絡圖」的基礎上，解決了頻譜圖卷積存在的一些不足，在預測分子性質和節點分類方面取得了很好的效果。Levie等人2018年在「CayleyNets」上的另一項研究發現，它在節點分類、矩陣完成(推薦系統)和社區檢測方面表現出了很強的性能。因此，根據你的應用程式和基礎設施，頻譜圖卷積可能是一個不錯的選擇。
在我的關於計算機視覺及其他圖神經網絡教程的另一部分（文章連結：https://towardsdatascience.com/tutorial-on-graph-neural-networks-for-computer-vision-and-beyond-part-2-be6d71d70f49）中，我解釋了由Defferrard等人在2016年提出的Chebyshev頻譜圖卷積，它直到現在還是一個非常強大的基線，它有一些很好的特性，而且很容易實現，正如我用PyTorch演示的那樣。
原文連結：https://towardsdatascience.com/spectral-graph-convolution-explained-and-implemented-step-by-step-2e495b57f801（雷鋒網注）
雷鋒網原創文章，未經授權禁止轉載。詳情見轉載須知。