作者：Tobias Skovgaard Jepsen

編譯：ronghuaiyang

導讀

這是第二篇，用頻譜圖卷積來做半監督學習。

圖的機器學習是一項非常困難的任務，因為圖的結構非常複雜，但同時也提供了豐富的信息。本文是關於如何利用圖卷積網絡(GCNs)對圖進行深度學習系列文章的第二篇。GCNs是一種功能強大的神經網絡，旨在直接處理圖並利用圖的結構信息。

在前一篇文章中，我對GCNs進行了高層次的介紹，並展示了如何根據節點的鄰居表示更新節點表示。在這篇文章中，我們首先深入了解了在前一篇文章中討論的相當簡單的圖卷積期間執行的聚合。然後我們繼續最近發布的圖卷積傳播規則，我展示了如何實現和用它來(semi-supervised學習)對Zachary空手道俱樂部社區進行預測。如下所示，GCN能夠學習每個節點的潛在特徵表示，這些節點將兩個社區分隔為兩個具有合理內聚性和分離的集群，儘管每個社區只使用了一個訓練樣本。

簡單回顧

在上一篇文章中，我們用了一個簡單的數學框架來表示GCNs的傳播。簡單來說，給定一個N × F⁰的特徵矩陣X，還有一個表示圖結構的矩陣，N × N的鄰接矩陣A，GCN中的每個隱層可以表示為Hⁱ = f(Hⁱ⁻¹, A))，其中 H⁰ =X ，f 是傳播法則。每一層的Hⁱ對應一個N × Fⁱ 的特徵矩陣，其中每一行表示一個節點。

傳播規則的形式為：

1. f(Hⁱ,A) = σ(AHⁱWⁱ)
2. f(Hⁱ,A) = σ(D⁻¹ÂHⁱWⁱ)，其中  = A + I, I是單位矩陣, D⁻¹是 Â的度矩陣的逆矩陣。

使用這些規則來計算一個節點的特徵表達，先聚合其鄰居節點，再通過一個權值矩陣Wⁱ進行變換，然後通過一個激活函數σ。我們可以通過細化規則1和2來把聚合和轉換的步驟更加明確，比如f(Hⁱ, A) = transform(aggregate(A,Hⁱ),Wⁱ)，其中對於規則1，transform(M, Wⁱ) = σ(MWⁱ)，aggregate(A,Hⁱ) = AHⁱ ，對於規則2， aggregate(A,Hⁱ) =D⁻¹Â Hⁱ 。

正如我們在前一篇文章中所討論的，規則1中的聚合將節點表示為其鄰居特徵表示的和，這有兩個明顯的缺點:

• 節點的聚合表示不包含其本身的特徵
• 度大的節點在特徵表示上會有較大的值，度小的節點會有較小的值，這可能會導致梯度爆炸的問題，使得使用對特徵尺度敏感的隨機梯度下降等算法進行訓練更加困難。

為了解決這兩個問題，規則2首先通過向A添加單位矩陣來強制自循環，然後使用轉換後的鄰接矩陣A = A+I進行聚合。接下來，是歸一化特徵表示，與度矩陣的逆D⁻¹相乘，把聚合轉換為均值，使得聚合節點具有特徵不變性。

在下文中，我將把規則1稱為求和規則，把規則2稱為平均規則。

頻譜圖卷積

Kipf和Welling最近的一篇文章提出了使用頻譜傳播規則快速近似譜圖卷積：

與前一篇文章中討論的求和規則和均值規則相比，譜規則只在聚合函數的選擇上有所不同。雖然它在某種程度上類似於均值規則，因為它使用度矩陣D取負冪對聚合進行標準化，但標準化是不對稱的。我們來試一下。

把加權和作為聚合

到目前為止，我們可以將我所介紹的聚合函數理解為加權和，其中每個聚合規則只在權重的選擇上有所不同。我們將首先看到如何用加權和來表示相對簡單的和和規則，然後再看譜規則。

要查看如何使用Sum規則計算第i個節點的聚合特徵表示，我們將看到聚合中的第i行是如何計算得到的。

如式1a所示，我們可以將第i個節點的聚合特徵表示為向量矩陣乘積。我們可以將這個向量矩陣乘積表示為一個簡單的加權和，如公式1b所示，其中我們對X中的N行求和。

式1b中第j個節點在聚合中的貢獻由A 的第i行的第j列的值決定。由於A是一個鄰接矩陣，如果第j個節點是第i個節點的鄰居，則該值為1，否則為0。因此，方程1b對應於對第i個節點的鄰居的特徵表示進行求和。

綜上所述，每個鄰居的貢獻完全依賴於由鄰接矩陣A定義的鄰域。

要查看平均規則如何聚合節點表示，我們再次看到如何使用平均規則計算聚合中的第i行。為了簡單起見，我們只考慮「原始」鄰接矩陣上的均值規則，而不考慮A與單位矩陣I之間的加法，它只對應於向圖中添加自循環。

從上面的方程式可以看出，推導過程稍微長了一些。在方程2a中，我們首先對鄰接矩陣A進行變換，將其與度矩陣D的倒數相乘。這個計算在式2b中更加明確。逆度矩陣是一個對角矩陣，其中沿對角線的值是節點度的相反數。因此，我們可以去掉產生方程2c的一個求和符號。方程2c可進一步簡化為方程2d和2e。

如公式2e所示，我們現在再次對鄰接矩陣A中的N行求和。正如在討論和規則時提到的，這對應於對每個第i個節點的鄰居求和。然而，方程2e中加權和的權重保證了第i個節點的和為1。因此，方程2e對應於第i個節點鄰居特徵表示的均值。

求和規則只依賴於鄰接矩陣A定義的鄰域，而均值規則也依賴於節點度數。

我們現在有一個有用的框架來分析譜規則。看看會指引我們走向哪裡。

與均值規則一樣，我們使用度矩陣D對鄰接矩陣A進行變換。然而，如式3a所示，我們將度矩陣取-0.5的冪，並在A的兩邊乘以它。這個操作可以分解如下式3b所示。再次回顧，度矩陣(及其冪)是對角的。因此，我們可以進一步簡化方程3b，直到得到方程3d中的表達式。

方程3e顯示了一些很有趣的東西。在計算第i個節點的聚合特徵表示時，不僅要考慮第i個節點的程度，還要考慮第j個節點的度。

與均值規則相似，譜規則對聚合進行標準化。聚合特徵表示與輸入特徵大致保持相同的尺度。然而，在加權和中，譜規則對相鄰的權重在低度時較高，在高度時較低。當低度鄰居比高度鄰居提供更多有用的信息時，這可能是有用的。

使用GCNs來進行半監督分類

除了譜規則，Kipf和Welling還演示了GCNs如何用於半監督分類。在半監督學習中，我們希望同時使用帶標籤和未帶標籤的示例。到目前為止，我們已經隱式地假設整個圖是可用的。換句話說，我們知道所有的節點，但不知道所有的節點標籤。

在我們所見過的所有規則中，我們對節點鄰居進行聚合，因此共享鄰居的節點往往具有類似的特徵表示。如果圖形顯示同質性，則此屬性非常有用，即，有連接的節點趨於相似(例如具有相同的標籤)。同質性存在於許多真實的網絡中，特別是社交網絡表現出很強的同質性。

我們看到在前面的文章，在同構的節點上使用圖結構，即使GCN隨機初始化就可以實現很好的分離的特徵表示。我們可以更進一步，在標記節點上訓練GCN，通過更新所有節點共享的權重矩陣，有效地將節點標記信息傳播給未標記節點。這可以做到如下:

1. 通過GCN執行正向傳播。
2. 在GCN的最後一層按行應用sigmoid函數。
3. 計算已知節點標籤上的交叉熵損失。
4. 反向傳播損耗並更新每一層的權值矩陣W。

在Zachary空手道俱樂部上進行社群預測

讓我們看看譜規則如何使用半監督學習將節點標記信息傳播到未標記節點。和前一篇文章一樣，我們將以Zachary的空手道俱樂部為例。

Zachary空手道俱樂部

簡單地說，Zachary 's karate_club是一個小型的社交網絡，其中管理員和空手道俱樂部的教練之間會發生衝突。任務是預測空手道俱樂部的每個成員選擇衝突的哪一方。網絡的圖形表示如下所示。每個節點表示空手道俱樂部的一個成員，成員之間的連結表示他們在俱樂部之外進行交互。管理員和教練分別用A和I標記。

在MXNet上做譜圖卷積

我在MXNet上實現了譜規則，實現如下：

__init__使用鄰接矩陣A，輸入和輸出維度 in_units， out_units作為輸入，輸出每個節點的特徵表示。A中加上了單位矩陣，構成了自循環，計算度矩陣D，然後將鄰接矩陣A轉換為A_hat，這是譜規則中指定的。變換的過程並不是必須的。

最後，我們存了兩個模型參數— A_hat是一個常量，權值矩陣 W是可訓練的參數。

hybrid_forward就是最神奇的地方。在前向中，我們調用這個方法，這個方法的輸入為： X, 這是前一層的輸出，參數 A_hat和 W，這兩個是在 __init__中定義的。

構建圖卷積網絡

現在我們已經實現了譜規則，我們可以將這些層疊加在一起。我們使用了一個類似於前一篇文章的兩層架構，其中第一個隱藏層有4個單元，第二個隱藏層有2個單元。這種體系結構使生成的二維嵌入很容易可視化。它與前一篇文章的架構有三個不同之處:

我們使用譜規則而不是平均規則。

我們使用不同的激活函數：第一層使用tanh激活函數，否則死神經元的機率會很高，第二層使用恆等函數，因為我們使用最後一層對節點進行分類。

最後，我們在GCN之上添加了一個邏輯回歸層來進行節點分類。

上述體系結構的Python實現如下：

我將網絡中包含圖卷積層的特徵學習部分分解為「特徵」組件，將分類部分分解為「分類器」組件。單獨的「功能」組件使以後更容易可視化這些層的激活。 LogisticRegressor是使用邏輯回歸的一個分類層，把每個節點的特徵加起來，然後經過一個sigmoid函數。

訓練GCN

GCN模型的訓練代碼如下所示。簡而言之，我初始化了一個二進位交叉熵損失函數和一個SGD優化器，來學習網絡參數。然後，對模型進行指定數量的訓練，其中每個訓練示例計算「損失」，並使用「loss. backwards()」反向傳播損失。然後調用step更新模型參數。在每個epoch之後，由GCN層構造的特徵表示將存儲在「feature_representation」列表中，稍後我們將查看這個列表。

至關重要的是，只有教練和管理員的標籤被標記，並且網絡中剩餘的節點是已知的，但是沒有標記！GCN可以在圖形卷積過程中找到標記節點和未標記節點的表示形式，並且可以在訓練過程中利用這兩個信息源進行半監督學習。

具體來說，半監督學習發生在GCN中，它通過聚合節點的標記鄰居和未標記鄰居來生成節點的潛在特徵表示。在訓練過程中，我們將監督的二進位交叉熵損失反向傳播，以更新所有節點共享的權值。然而，這種損失依賴於標記節點的潛在特徵表示，而這些潛在特徵表示又依賴於標記節點和未標記節點。這樣，學習就變成了半監督的。

特徵可視化

如上所述，存儲每個epoch的特徵表示，這使我們能夠看到在訓練期間特徵表示是如何變化的。在下面，我考慮兩個輸入特徵表示。

表示 1

在第一個表示方法中，我們簡單地使用稀疏的34×34單位矩陣，I作為特徵矩陣「X」，即， 對圖中每個節點進行一次熱編碼。這種表示方法的優點是它可以用於任何圖，但是會導致網絡中每個節點的輸入參數，這需要大量內存和計算能力，以便在大型網絡上進行訓練，並可能導致過度擬合。幸運的是，空手道俱樂部的網絡非常小。使用這種表示，網絡被訓練了5000個epochs。

通過對網絡中所有節點進行分類，得到了誤差在網絡中的分布情況，如上圖所示。這裡，黑色表示分類錯誤。儘管將近一半(41%)的節點是錯誤分類的，但是與管理員或教練(但不是兩者都)緊密連接的節點往往是正確分類的。

使用表示方法1表示訓練過程中特徵的改變

在左邊，我已經說明了特徵表示在訓練期間是如何變化的。這些節點最初緊密地聚集在一起，但是隨著訓練的進行，教練和管理員被分開，拖著一些節點。

雖然管理員和教練得到了完全不同的表示，但是他們拖拽的節點不一定屬於他們的社區。這是因為圖卷積嵌入了在特徵空間中緊密共享鄰居的節點，但是共享鄰居的兩個節點可能不平等地連接到管理員和教練。特別是使用單位矩陣作為特徵矩陣，使得每個節點具有高度的局部表示，即，屬於圖中相同區域的節點很可能緊密地嵌入在一起。這使得網絡很難以歸納的方式在遙遠的地區之間共享共同的知識。

表示 2

我們將通過添加兩個特徵來改進表示法1，這兩個特徵不是特定於網絡的任何節點或區域，而是度量與管理員和教練之間的連接程度。為此，我們計算從網絡中的每個節點到管理員和教練的最短路徑距離，並將這兩個特徵連接到前面的表示形式。

有些人可能會認為這有點欺騙，因為我們注入了關於圖中每個節點位置的全局信息，(理想情況下)這應該由「特徵」組件中的圖形卷積層捕獲的信息。然而，圖卷積層總是有一個局部的視角，並且捕捉這些信息的能力有限。儘管如此，它仍然是理解GCNs的一個有用工具。

與之前一樣，我們對網絡中的所有節點進行了分類，並繪製了錯誤在網絡中的分布情況，如上圖所示。這一次，只有四個節點被錯誤分類，與表示法1相比，這是一個顯著的改進！在對特徵矩陣進行更仔細的檢查之後，這些節點要麼與教練和管理員之間的距離相等(在最短路徑的意義上)，要麼更接近管理員，但屬於教練社區。GCN使用表示2為250個epochs進行訓練。

如左圖所示，這些節點最初再次非常緊密地聚集在一起，但是在訓練開始之前就已經在一定程度上被劃分為多個社區！隨著訓練的進展，社區之間的距離也在增加。

總結

在這篇文章中，我深入地解釋了GCNs中的聚合是如何執行的，並以平均值、求和以及譜規則為例，展示了如何將其表示為加權和。我真誠地希望，你會發現這個框架有助於考慮在你自己的圖卷積網絡中進行聚合時可能需要哪些權重。

我還展示了如何在MXNet中實現和訓練一個GCN，以Zachary的空手道俱樂部為簡單示例網絡，使用頻譜圖卷積對圖進行半監督分類。我們看到僅僅使用兩個標記節點，GCN仍然有可能在表示空間中實現兩個網絡社區之間的高度分離。

英文原文：https://towardsdatascience.com/how-to-do-deep-learning-on-graphs-with-graph-convolutional-networks-62acf5b143d0