|
由于高度復(fù)雜但信息豐富的圖形結(jié)構(gòu)，圖形上的機器學(xué)習(xí)一直以來都是一項艱巨的任務(wù)。本文是關(guān)于如何使用圖形卷積網(wǎng)絡(luò)（GCN）進(jìn)行圖形深度學(xué)習(xí)的系列文章中的第二篇。GCN是一種強大的神經(jīng)網(wǎng)絡(luò)，旨在利用圖形結(jié)構(gòu)信息并直接在圖形上工作。在本文開頭我將簡要回顧一下上一篇文章，你也可以直接點擊下方鏈接，進(jìn)行更加仔細(xì)，詳細(xì)的閱讀。 1.圖形卷積網(wǎng)絡(luò)的高級介紹（https:///how-to-do-deep-learning-on-graphs-with-graph-convolutional-networks-7d2250723780） 2.譜圖卷積的半監(jiān)督學(xué)習(xí)（本文） 簡要回顧 在我之前關(guān)于GCN的文章中（https:///how-to-do-deep-learning-on-graphs-with-graph-convolutional-networks-7d2250723780），我們看到了在GCN中的一個簡單的數(shù)學(xué)框架。簡而言之，給定一個N×F?特性矩陣X和一個圖的矩陣表示結(jié)構(gòu)，例如G的N×N鄰接矩陣A，GCN中的每個隱藏層可表示為H?= f（H?-1， A）其中H?= X且f是傳播規(guī)則。每個層H?對應(yīng)于N×F?特性矩陣，其中每一行是節(jié)點的特性表示。 我們看到了這種形式的傳播規(guī)則 1.f（H?，A）=σ（AH?W?） 2.f（H?，A）=σ（D-1H?W?）其中?= A + I，I是單位矩陣，D -1是?的度矩陣。 這些規(guī)則在通過應(yīng)用權(quán)重W?和激活函數(shù)σ進(jìn)行變換之前，將節(jié)點的特性表示計算為其鄰居的特性表示的集合。通過將上面的傳播規(guī)則1和2表示為f（H?，A）=transform(aggregate （A，H?），W?），我們可以使聚合和變換步驟更加明確，其中transform（M，W?）=σ（MW?）和規(guī)則1的aggregate（A，H?）=AH?，規(guī)則2的aggregate（A，H?）= D-1H?。 正如我們在上一篇文章中所討論的，規(guī)則1中的聚合將節(jié)點表示為其鄰居特性表示的總和，這有兩個明顯的缺點：
為了解決這兩個問題，規(guī)則2首先通過向A添加單位矩陣來強制執(zhí)行自循環(huán)，并使用變換后的鄰接矩陣?= A + I進(jìn)行聚合。接下來，通過乘以逆度矩陣D -1來對特性表示進(jìn)行標(biāo)準(zhǔn)化。將聚合轉(zhuǎn)換為聚合特性表示的規(guī)模對節(jié)點次數(shù)不變的均值。 在下文中，我將規(guī)則1稱為求和規(guī)則，將規(guī)則2稱為均值規(guī)則。 譜圖卷積 Kipf和Welling最近的一篇論文提出了使用光譜傳播規(guī)則的快速近似譜圖卷積[1]： 與前一篇文章中討論的總和均值規(guī)則相比，譜學(xué)規(guī)律僅在聚合函數(shù)的選擇上有所不同。雖然它有點類似于均值規(guī)則，因為它使用提升到負(fù)冪的度矩陣D對聚合進(jìn)行標(biāo)準(zhǔn)化，但標(biāo)準(zhǔn)化是不對稱的。讓我們試一試，看看它的作用。 作為加權(quán)和的聚合 到目前為止，我們可以理解我所介紹的作為加權(quán)和的聚合函數(shù)，其中每個聚合規(guī)則僅在它們的權(quán)重選擇上有所不同。我們先來看看如何用加權(quán)和來表示相對簡單的和與均值規(guī)則，然后再討論譜學(xué)規(guī)律。 求和規(guī)則 為了了解如何使用求和規(guī)則計算第i個節(jié)點的聚合特性表示，我們看到如何計算聚合中的第i行。 求和規(guī)則作為加權(quán)和 如等式1a所示，我們可以將第i個節(jié)點的聚合特性表示作為向量矩陣乘積來計算。我們可以將這個向量矩陣乘積表示為一個簡單的加權(quán)和，如公式1b所示，我們對X中的N行中的每一行求和。 公式1b中第j個節(jié)點在聚合中的貢獻(xiàn)由A的第i行的第j列的值確定。由于A是鄰接矩陣，如果第j個節(jié)點是第i個節(jié)點的鄰居，則該值為1，否則為0。等式1b對應(yīng)于對第i個節(jié)點的相鄰的特性表示求和。這證實了上一篇文章的看法。 總之，每個鄰居的貢獻(xiàn)僅取決于鄰接矩陣A定義的鄰域。 均值規(guī)則 要查看均值規(guī)則如何用聚合節(jié)點表示，我們再次查看如何計算聚合中的第i行。為簡單起見，我們只考慮'原始'鄰接矩陣的均值規(guī)則，而不考慮A和單位矩陣I之間的加法，這相當(dāng)于向圖形中添加自循環(huán)。 均值規(guī)則作為加權(quán)和 在等式2a中，我們現(xiàn)在首先通過將鄰接矩陣A乘以逆矩陣D來變換鄰接矩陣A。在等式2b中使該計算更明確。逆矩陣是一個區(qū)域矩陣，其中沿對角線的值是逆節(jié)點度s.t.的位置，（i，i）處的值是第i個節(jié)點的反度。因此，我們可以移除其中一個求和符號，得到等式2c。在等式2d和2e中可以進(jìn)一步減少等式2c。 如等式2e所示，我們現(xiàn)在再次對鄰接矩陣A中的N行中的每一行求和。如在求和規(guī)則的討論期間所提到的，這相當(dāng)于對每個第i個節(jié)點的鄰居進(jìn)行求和。然而，等式2e中的加權(quán)和的權(quán)重與第i個節(jié)點的次數(shù)之和1。因此，等式2e對應(yīng)于第i個節(jié)點的相鄰特性表示均值。 求和規(guī)則僅取決于鄰接矩陣A定義的鄰域，而均值規(guī)則也僅取決于節(jié)點度。 譜學(xué)規(guī)律 我們現(xiàn)在有一個有用的框架來分析譜學(xué)規(guī)律。讓我們看看它！ 作為加權(quán)和的譜學(xué)規(guī)律 與均值規(guī)則一樣，我們使用度矩陣D來變換鄰接矩陣A。但是，如等式3a所示，我們將度矩陣提高到-0.5的冪并將其乘以A的每一邊。此操作可以是分解如公式3b所示。再次回想一下，次數(shù)矩陣（及其冪）是對角線的。因此，我們可以進(jìn)一步簡化方程3b，直到達(dá)到方程3e中的表達(dá)式。 公式3e很有趣。在計算第i個節(jié)點的聚合特性表示時，我們不僅要考慮第i個節(jié)點的度，還要考慮第j個節(jié)點的度。 與均值規(guī)則類似，譜學(xué)規(guī)律對聚合s.t進(jìn)行標(biāo)準(zhǔn)化。聚合特性表示與輸入特性大致保持相同的比例。然而，如果譜學(xué)規(guī)律具有低度，則譜學(xué)規(guī)律將加權(quán)和中的鄰域加權(quán)，如果它們具有高度則加權(quán)較低。當(dāng)?shù)痛螖?shù)鄰居提供比高次數(shù)鄰居更有用的信息時，這可能是有用的。 GCN的半監(jiān)督分類 除譜學(xué)規(guī)律外，Kipf和Welling還演示了GCN如何用于半監(jiān)督分類[1]。到目前為止，我們假設(shè)整個圖表是可用的，即我們處于轉(zhuǎn)換的環(huán)境中。換句話說，我們知道所有節(jié)點，但不知道所有節(jié)點標(biāo)簽。 在我們看到的所有規(guī)則中，我們在節(jié)點鄰域上進(jìn)行聚合，因此共享鄰居的節(jié)點往往具有相似的特性表示。如果圖形表現(xiàn)出同質(zhì)性，即連接的節(jié)點傾向于相似（例如具有相同的標(biāo)簽），則該特性非常有用。同質(zhì)性發(fā)生在許多真實網(wǎng)絡(luò)中，尤其是社交網(wǎng)絡(luò)表現(xiàn)出非常強烈的同質(zhì)性。 正如我們在上一篇文章中看到的那樣，即使是隨機初始化的GCN也可以通過使用圖形結(jié)構(gòu)，在同構(gòu)圖中實現(xiàn)節(jié)點的特性表示之間的良好分離。通過在標(biāo)記節(jié)點上訓(xùn)練GCN，我們可以更進(jìn)一步，有效地將節(jié)點標(biāo)簽信息傳播到未標(biāo)記的節(jié)點。這可以通過以下方式完成： 1.通過GCN執(zhí)行正向傳播。 2.將sigmoid函數(shù)逐行應(yīng)用于GCN中的最后一層。 3.計算已知節(jié)點標(biāo)簽上的交叉熵?fù)p失。 4.反向傳播損失并更新每層中的權(quán)重矩陣W。 Zachary空手道俱樂部的預(yù)測 讓我們看看譜學(xué)規(guī)律如何使用半監(jiān)督學(xué)習(xí)將節(jié)點標(biāo)簽信息傳播到未標(biāo)記的節(jié)點。與前一篇文章一樣，我們將以Zachary的空手道俱樂部為例。 Zachary的空手道俱樂部 簡而言之，Zachary的空手道俱樂部是一個小型的社交網(wǎng)絡(luò)，在這里，管理員和空手道俱樂部的教練之間會發(fā)生沖突。任務(wù)是預(yù)測空手道俱樂部的每個成員會選擇的沖突的哪一方。網(wǎng)絡(luò)的圖形表示如下圖所示。每個節(jié)點代表空手道俱樂部的成員，并且成員之間的鏈接表示他們在俱樂部外進(jìn)行交互。管理員和教練分別標(biāo)有A和I。 Zachary的空手道俱樂部 MXNet中的譜圖卷積 我在MXNet中實現(xiàn)了譜學(xué)規(guī)律，這是一個易于使用且高效的深度學(xué)習(xí)框架。實施如下： init將鄰接矩陣Aalong作為輸入，其中每個節(jié)點的特性表示的輸入和輸出維數(shù)分別來自圖卷積層。in_units和out_units分別為輸入和輸出維數(shù)。通過與單位矩陣I相加，將自循環(huán)添加到鄰接矩陣A，計算度矩陣D，并將鄰接矩陣A變換為由譜學(xué)規(guī)律指定的A_hat。這種變換不是嚴(yán)格必要的，但是計算效率更高，因為在層的每次前向傳遞期間都會執(zhí)行變換。 最后，在init的with子句中，我們存儲了兩個模型參數(shù)A_hat存儲為常量，權(quán)重矩陣W存儲為可訓(xùn)練參數(shù)。 在正向傳遞中，我們使用以下輸入執(zhí)行此方法：X，前一層的輸出，以及我們在構(gòu)造函數(shù)init中定義的參數(shù)A_hat和W。 構(gòu)建圖形卷積網(wǎng)絡(luò) 現(xiàn)在我們已經(jīng)實現(xiàn)了譜學(xué)規(guī)律，我們可以將這些層疊加在一起。我們使用類似于前一篇文章中的兩層架構(gòu)，其中第一個隱藏層有4個單元，第二個隱藏層有2個單元。這種架構(gòu)可以輕松地顯示最終的二維嵌入。它與前一篇文章中的架構(gòu)有三點不同：
上述體系結(jié)構(gòu)的Python實現(xiàn)如下。 我已將包含圖形卷積層的網(wǎng)絡(luò)的特性學(xué)習(xí)部分分離為特性組件，將分類部分分離為分類器組件。單獨的特性組件使以后更容易可視化這些層的激活。用作分類器的邏輯回歸是一個分類層，它通過對最后一個圖形卷積層提供的每個節(jié)點的特性求和并對該和應(yīng)用sigmoid函數(shù)來執(zhí)行邏輯回歸。 為了完整起見，構(gòu)造特性組件的代碼是 而邏輯回歸的代碼是
訓(xùn)練GCN 訓(xùn)練GCN模型的代碼如下所示。簡而言之，我初始化了一個二進(jìn)制交叉熵?fù)p失函數(shù)cross_entropy和SGD優(yōu)化器、訓(xùn)練器來學(xué)習(xí)網(wǎng)絡(luò)參數(shù)。然后針對指定數(shù)量的紀(jì)元訓(xùn)練模型，其中針對每個訓(xùn)練示例計算損失，并且使用loss.backward（）反向傳播錯誤。然后調(diào)用trainer.step來更新模型參數(shù)。在每個紀(jì)元之后，由GCN層構(gòu)建的特性表示存儲在feature_representations列表中。
至關(guān)重要的是，只標(biāo)記了教練和管理員的標(biāo)簽，網(wǎng)絡(luò)中的其余節(jié)點是已知的，但它們未標(biāo)記！GCN可以在圖形卷積期間找到標(biāo)記和未標(biāo)記節(jié)點的表示，并且可以在訓(xùn)練期間利用這兩種信息源來執(zhí)行半監(jiān)督學(xué)習(xí)。 可視化特性 如上所述，存儲每個時期的特性表示，這允許我們在訓(xùn)練期間看到特性表示如何改變。在下面我考慮兩個輸入特性表示。 表示1 在第一種表示中，我們簡單地使用稀疏的34×34單位矩陣I作為特性矩陣X。該表示具有可以在任何圖中使用的優(yōu)點，但是會導(dǎo)致網(wǎng)絡(luò)中每個節(jié)點的輸入?yún)?shù)需要大量的記憶和計算能力，以便在大型網(wǎng)絡(luò)上進(jìn)行訓(xùn)練，并可能導(dǎo)致過度擬合。值得慶幸的是，空手道俱樂部網(wǎng)絡(luò)非常小。使用該表示對網(wǎng)絡(luò)進(jìn)行5000個歷元的訓(xùn)練。
通過對網(wǎng)絡(luò)中的所有節(jié)點進(jìn)行分類，我們可以獲得上面顯示的網(wǎng)絡(luò)中的錯誤分布。在這里，黑色表示錯誤分類。盡管近一半（41％）的節(jié)點被錯誤分類，但與管理員或教練（但不是兩者都有）緊密相連的節(jié)點往往被正確分類。
使用表示法1訓(xùn)練期間特性表示的變化 在左側(cè)，我已經(jīng)說明了在訓(xùn)練期間特性表示如何變化。節(jié)點最初是緊密地聚集在一起的，但隨著訓(xùn)練的進(jìn)行，教練和管理員被分開，用它們帶動一些節(jié)點。 雖然管理員和教練的表示方式完全不同，但他們拖動的節(jié)點不一定屬于他們的社區(qū)。這是因為圖形卷積在特性空間中嵌入了共享鄰居的節(jié)點，但是共享鄰居的兩個節(jié)點可能無法同等地連接到管理員和教練。特別地，使用單位矩陣作為特性矩陣會導(dǎo)致每個節(jié)點的高度局部表示。即，屬于圖的相同區(qū)域的節(jié)點可能緊密地嵌入在一起。這使得網(wǎng)絡(luò)難以以歸納的方式在遠(yuǎn)程區(qū)域之間共享公共知識。 表示2 我們將通過添加兩個不特定于網(wǎng)絡(luò)的任何節(jié)點或區(qū)域的特性來改進(jìn)表示1。為此，我們計算從網(wǎng)絡(luò)中的每個節(jié)點到管理員和教練的最短路徑距離，并將這兩個特性連接到先前的表示。 也許可能會認(rèn)為這種行為有點欺騙性，因為我們會在圖表中注入有關(guān)每個節(jié)點位置的全局信息，應(yīng)該（理想地）由特性組件中的圖卷積層捕獲的信息。但是，圖形卷積層始終具有局部視角，并且捕獲此類信息的能力有限。盡管如此，它仍然是理解GCN的有用工具。
我們共同對網(wǎng)絡(luò)中的所有節(jié)點進(jìn)行分類，并繪制出上圖的網(wǎng)絡(luò)中的錯誤分布。這次，只有四個節(jié)點被錯誤分類，相對于表示1有顯著改進(jìn)！仔細(xì)檢查特性矩陣后，這些節(jié)點要么與教練和管理員等距（在最短路徑意義上），要么離管理員更近，但屬于教練社區(qū)。使用表示1訓(xùn)練GCN 250個時期。
使用表示2訓(xùn)練期間特性表示的變化 如圖所示，節(jié)點最初再次非常緊密地聚集在一起，但在訓(xùn)練甚至開始之前，它們在某種程度上分成了社區(qū)！隨著訓(xùn)練的進(jìn)行，社區(qū)之間的距離也會增加。 下一步是什么？ 在這篇文章中，我已經(jīng)深入解釋了GCN中的聚合如何執(zhí)行，展示了如何將其表示為加權(quán)和。并使用均值、求和、譜學(xué)規(guī)律作為示例。我真誠地希望你會發(fā)現(xiàn)這個框架對于在你自己的圖形卷積網(wǎng)絡(luò)中聚合期間可能需要哪些權(quán)重非常有用。 我還展示了如何在MXNet中實施和訓(xùn)練GCN，使用Zachary的空手道俱樂部作為一個簡單的示例網(wǎng)絡(luò)，使用譜圖卷積對圖形進(jìn)行半監(jiān)督分類。我們看到如何使用兩個標(biāo)記的節(jié)點，GCN仍然可以在表示空間中實現(xiàn)兩個網(wǎng)絡(luò)社區(qū)之間的高度分離。 雖然有關(guān)圖形卷積網(wǎng)絡(luò)的更多信息，我希望將來有時間與你分享，但這是（目前）系列中的最后一篇文章。如果你有興趣進(jìn)一步閱讀，我想推薦一些我發(fā)現(xiàn)非常有趣的論文： 1. Inductive Representation Learning on Large Graphs（https:///abs/1706.02216） 在本文中，Hamilton等人提出了幾種新的聚合函數(shù)，例如，使用最大/平均聚合或多層感知器。此外，他們還提出了一種簡單的方法來進(jìn)行GCN的小批量訓(xùn)練，大大提高了訓(xùn)練速度。 2. FastGCN: Fast Learning with Graph Convolutional Networks via Importance Samping（https:///pdf/1801.10247.pdf） Hamilton等人提出的小批量方法的缺點在于，批量中的節(jié)點數(shù)量由于它們的遞歸而在執(zhí)行的聚合的數(shù)量中呈指數(shù)增長。Chen等人提出了他們的FastGCN方法，通過獨立地執(zhí)行圖卷積層的批量訓(xùn)練來解決這個缺點。 3.N-GCN: Multi-scale Graph Convolution for Semi-supervised Node Classification（https:///pdf/1802.08888.pdf） 在FastGCN解決訓(xùn)練遞歸圖卷積網(wǎng)絡(luò)問題的地方，N-GCN挑戰(zhàn)了GCN需要遞歸的前提！ Abu-El-Haija等人提出了一種具有多個（N）GCN的平面架構(gòu)，其輸出被連接在一起。每個GCN捕獲不同距離的鄰域，從而避免遞歸聚合。 參考 [1] Thomas Kipf和Max Welling撰寫的帶有圖形卷積網(wǎng)絡(luò)的半監(jiān)督分類論文。（https:///abs/1609.02907） |
|
|
