GCN圖卷積網絡入門詳解

作者：雷鋒字幕組 2020-09-23 14:52:01

人工智能深度學習

在這篇文章中，我們將仔細研究一個名為GCN的著名圖神經網絡。首先，我們先直觀的了解一下它的工作原理，然后再深入了解它背后的數學原理。

為什么要用Graph?

許多問題的本質上都是圖。在我們的世界里，我們看到很多數據都是圖，比如分子、社交網絡、論文引用網絡。

圖的例子。(圖片來自[1])

Graph上的任務

節點分類：預測特定節點的類型。
鏈接預測：預測兩個節點是否有聯系
社區檢測：識別密集聯系的節點群落。
網絡相似性：兩個(子)網絡的相似性有多大?

機器學習的生命周期

在圖中，我們有節點特征(代表節點的數據)和圖的結構(表示節點如何連接)。

對于節點來說，我們可以很容易地得到每個節點的數據。但是當涉及到圖的結構時，要從中提取有用的信息就不是一件容易的事情了。例如，如果2個節點彼此距離很近，我們是否應該將它們與其他對節點區別對待呢?高低度節點又該如何處理呢?其實，對于每一項具體的工作，僅僅是特征工程，即把圖結構轉換為我們的特征，就會消耗大量的時間和精力。

圖上的特征工程。(圖片來自[1])

如果能以某種方式同時得到圖的節點特征和結構信息作為輸入，讓機器自己去判斷哪些信息是有用的，那就更好了。

這也是為什么我們需要圖表示學習的原因。

我們希望圖能夠自己學習 "特征工程"。(圖片來自[1])

圖卷積神經網絡(GCNs)

論文：基于圖神經網絡的半監督分類(2017)[3]

GCN是一種卷積神經網絡，它可以直接在圖上工作，并利用圖的結構信息。

它解決的是對圖(如引文網絡)中的節點(如文檔)進行分類的問題，其中僅有一小部分節點有標簽(半監督學習)。

在Graphs上進行半監督學習的例子。有些節點沒有標簽(未知節點)。

主要思想

就像"卷積"這個名字所指代的那樣，這個想法來自于圖像，之后引進到圖(Graphs)中。然而，當圖像有固定的結構時，圖(Graphs)就復雜得多。

從圖像到圖形的卷積思想。 (圖片來自[1])

GCN的基本思路：對于每個節點，我們從它的所有鄰居節點處獲取其特征信息，當然也包括它自身的特征。假設我們使用average()函數。我們將對所有的節點進行同樣的操作。最后，我們將這些計算得到的平均值輸入到神經網絡中。

在下圖中，我們有一個引文網絡的簡單實例。其中每個節點代表一篇研究論文，同時邊代表的是引文。我們在這里有一個預處理步驟。在這里我們不使用原始論文作為特征，而是將論文轉換成向量(通過使用NLP嵌入，例如tf-idf)。NLP嵌入，例如TF-IDF)。

讓我們考慮下綠色節點。首先，我們得到它的所有鄰居的特征值，包括自身節點，接著取平均值。最后通過神經網絡返回一個結果向量并將此作為最終結果。

GCN的主要思想。我們以綠色節點為例。首先，我們取其所有鄰居節點的平均值，包括自身節點。然后，將平均值通過神經網絡。請注意，在GCN中，我們僅僅使用一個全連接層。在這個例子中，我們得到2維向量作為輸出(全連接層的2個節點)。

在實際操作中，我們可以使用比average函數更復雜的聚合函數。我們還可以將更多的層疊加在一起，以獲得更深的GCN。其中每一層的輸出會被視為下一層的輸入。

2層GCN的例子：第一層的輸出是第二層的輸入。同樣，注意GCN中的神經網絡僅僅是一個全連接層(圖片來自[2])。

讓我們認真從數學角度看看它到底是如何起作用的。

直觀感受和背后的數學原理

首先，我們需要一些注解

我們考慮圖G，如下圖所示。

從圖G中，我們有一個鄰接矩陣A和一個度矩陣D。同時我們也有特征矩陣X。

那么我們怎樣才能從鄰居節點處得到每一個節點的特征值呢?解決方法就在于A和X的相乘。

看看鄰接矩陣的第一行，我們看到節點A與節點E之間有連接，得到的矩陣第一行就是與A相連接的E節點的特征向量(如下圖)。同理，得到的矩陣的第二行是D和E的特征向量之和，通過這個方法，我們可以得到所有鄰居節點的向量之和。

計算 "和向量矩陣 "AX的第一行。

這里還有一些需要改進的地方。

我們忽略了節點本身的特征。例如，計算得到的矩陣的第一行也應該包含節點A的特征。
我們不需要使用sum()函數，而是需要取平均值，甚至更好的鄰居節點特征向量的加權平均值。那我們為什么不使用sum()函數呢?原因是在使用sum()函數時，度大的節點很可能會生成的大的v向量，而度低的節點往往會得到小的聚集向量，這可能會在以后造成梯度爆炸或梯度消失(例如，使用sigmoid時)。此外，神經網絡似乎對輸入數據的規模很敏感。因此，我們需要對這些向量進行歸一化，以擺脫可能出現的問題。

在問題(1)中，我們可以通過在A中增加一個單位矩陣I來解決，得到一個新的鄰接矩陣Ã。

取lambda=1(使得節點本身的特征和鄰居一樣重要)，我們就有Ã=A+I，注意，我們可以把lambda當做一個可訓練的參數，但現在只要把lambda賦值為1就可以了，即使在論文中，lambda也只是簡單的賦值為1。

通過給每個節點增加一個自循環，我們得到新的鄰接矩陣

對于問題(2): 對于矩陣縮放，我們通常將矩陣乘以對角線矩陣。在當前的情況下，我們要取聚合特征的平均值，或者從數學角度上說，要根據節點度數對聚合向量矩陣ÃX進行縮放。直覺告訴我們這里用來縮放的對角矩陣是和度矩陣D̃有關的東西(為什么是D̃，而不是D?因為我們考慮的是新鄰接矩陣Ã 的度矩陣D̃，而不再是A了)。

現在的問題變成了我們要如何對和向量進行縮放/歸一化?換句話說：

我們如何將鄰居的信息傳遞給特定節點?我們從我們的老朋友average開始。在這種情況下，D̃的逆矩陣(即，D̃^{-1})就會用起作用。基本上，D̃的逆矩陣中的每個元素都是對角矩陣D中相應項的倒數。

例如，節點A的度數為2，所以我們將節點A的聚合向量乘以1/2，而節點E的度數為5，我們應該將E的聚合向量乘以1/5，以此類推。

因此，通過D̃取反和X的乘法，我們可以取所有鄰居節點的特征向量(包括自身節點)的平均值。

到目前為止一切都很好。但是你可能會問加權平均()怎么樣?直覺上，如果我們對高低度的節點區別對待，應該會更好。

但我們只是按行縮放，但忽略了對應的列(虛線框)。

為列增加一個新的縮放器。

新的縮放方法給我們提供了 "加權 "的平均值。我們在這里做的是給低度的節點加更多的權重，以減少高度節點的影響。這個加權平均的想法是，我們假設低度節點會對鄰居節點產生更大的影響，而高度節點則會產生較低的影響，因為它們的影響力分散在太多的鄰居節點上。

在節點B處聚合鄰接節點特征時，我們為節點B本身分配最大的權重(度數為3)，為節點E分配最小的權重(度數為5)。

因為我們歸一化了兩次，所以將"-1 "改為"-1/2"

例如，我們有一個多分類問題，有10個類，F 被設置為10。在第2層有了10個維度的向量后，我們將這些向量通過一個softmax函數進行預測。

Loss函數的計算方法很簡單，就是通過對所有有標簽的例子的交叉熵誤差來計算，其中Y_{l}是有標簽的節點的集合。

層的數量

#layers的含義

層數是指節點特征能夠傳輸的最遠距離。例如，在1層的GCN中，每個節點只能從其鄰居那里獲得信息。每個節點收集信息的過程是獨立進行的，對所有節點來說都是在同一時間進行的。

當在第一層的基礎上再疊加一層時，我們重復收集信息的過程，但這一次，鄰居節點已經有了自己的鄰居的信息(來自上一步)。這使得層數成為每個節點可以走的最大跳步。所以，這取決于我們認為一個節點應該從網絡中獲取多遠的信息，我們可以為#layers設置一個合適的數字。但同樣，在圖中，通常我們不希望走得太遠。設置為6-7跳，我們就幾乎可以得到整個圖，但是這就使得聚合的意義不大。