前一陣子看到了這篇很有意思的文章: How Powerful are Graph Neural Networks? , 最近在想transformer結構的時候又想起了這篇文章, 並且特意看了以下ICLR這篇文章的會議視頻. 有意思的是, 在作者分享完了之後, 有一位研究者也問了作者怎麼看待Self Attention, 作者並沒有回答的很詳細, 只是說了Self Attention不是Max power GNN(這個概念下面會解釋), 但是在node feature比較豐富的時候自有它的應用.

閑話說完, 說回這篇文章.

這篇文章說了以下事情:

  1. 介紹了目前GNN的一般框架和WL test(Weisfeiler-Lehman test)
  2. 定義了什麼是強大的GNN, 證明了什麼樣的GNN符合強大的標準, 並給出一個具體實現(GIN)
  3. 講了一下一些不powerful的操作

這篇文章個人感覺寫的蠻好的, 淺顯易懂, 證明都在附錄中, 看完對圖網路也有了大概的認識. 這篇文章會介紹一下這個工作的結果, 並不會深入理論證明(其實是懶得看了). 水平有限, 如有謬誤, 歡迎指正.

GNN的一般框架

符號解釋:

  • V, E : 圖的節點和邊的集合
  • h_v^k : 節點v在第k次循環(第k層)的特徵向量
  • N(v) : 節點v的所有相鄰節點

我們知道, 一般圖包含有節點(V)和邊(E), 我們用 X_v 來表示圖的初始節點特徵向量(比如one hot), 在GNN中, 我們希望將整個圖的信息都學習到一個個節點特徵向量h_v 中, 然後對這個圖進行節點分類和整個圖的分類.

因此, 一般的NLP任務也可以看作是圖, 節點為詞, 邊就是相鄰的詞, 對每個詞做分類, 即序列標註(NER等任務), 就是對節點做分類. 而一般的分類任務, 比如話題分類, 就是對圖做分類.

一般的GNN都是一個循環聚合相鄰節點的過程, 也就是說, 一個節點在第k次循環的特徵h_{k} 取決於: 前一次循環的特徵 h_{k-1} 和前一次循環的所有鄰居的特徵 {h_{u}^{k-1}, u in N(v) }, 而最終整個圖的表示, 則是綜合所有節點的特徵向量, 具體說來就是以下三個公式:

egin{aligned} &a_v^{k} = AGGREGATE^k({h_u^{k-1}: u in N(v) }) \ &h_v^k = COMBINE^k(h_v^{k-1}, a_v^k) \ &h_G = READOUT({ h_v^k|v in G }) end{aligned}

上面第一條公式得到相鄰節點的特徵, 第二條公式結合了相鄰節點特徵和自身特徵得到新的特徵, 第三條公式結合了所有節點的最終表示得到圖表示. GNN實現的不同點一般在與AGGREGATE, COMBINE和READOUT的選擇. 比如在GraphSAGE中, AGGREGATE就是dense + ReLu + Max Pooling, COMBINE就是concat+dense.

WL Test

WL Test是將節點不斷循環聚合的過程, 每個循環裡面會做以下兩個事情:

  1. 整合節點及其相鄰節點的標籤
  2. 將整合後的標籤hash成一個新的標籤

對於兩個圖, 如果在WL test的循環中出現任何一個節點的標籤不一致, 那麼這兩個圖是不類似的(non-isomorphic).

和GNN不同的是, GNN將節點映射成一個低維的, dense的向量, 而WL test則映射成一個one-hot.

比如, 對"機器學習真有趣", "機器學習真無趣"這個兩圖的"習"節點進行WL test循環, 得到的aggregated label為:

iter 0: 習
iter 1: 學習真
iter 2: 器學習真有

iter 0: 習
iter 1: 學習真
iter 2: 器學習真無

在iter 2發現習節點標籤不一樣, 那麼這兩個圖是non-isomorphic的.

什麼是強大的GNN?

感覺有股中二的氣息...

強大的GNN指的是, 對於任意不同的圖, 都能夠通過將它們映射到同一個空間中的不同向量來區分它們.

接著作者證明了以下兩個theorem:

  1. WL test是強大的
  2. 如果AGGREGATION, COMBINE和READOUT函數都是一對一的映射的話, 那麼GNN和WL test一樣強大

因此, 只要滿足上面的2的GNN, 就是強大的, 作者提出了一個強大並且簡單的GNN: Graph Isomorphism Network(GIN).

GIN

接著, 作者證明了下面的引理(原文並不限於圖的語境下, 這裡為了方便理解稍做修改, 不嚴謹!!!):

假設圖 G 的節點是可數的, 且節點的相鄰節點 N(v) 數量有上界, 那麼存在一個函數f: V ightarrow R^n , 使得有無限個epsilon , 函數

h(v, N(v)) = (1+epsilon)cdot f(v) + Sigma_{u in N(v)}f(u)

和 (v, N(v)) 是一一對應的(為啥加和是一一對應的? 證明請見Lemma 5). 並且任意函數g都可以拆解成

g(v, N(v)) = phi(h(v, N(v))) .

存在這樣一個函數就好辦了, 由於universal approximation theorem, MLP可以擬合任意函數, 直接一個MLP懟上去就好了, 順帶還擬合了複合函數 fcirc phi :

h_v^k=MLP((1 + epsilon ) cdot h_v^{k-1} + Sigma_{u in N(v)}h_u^{k-1})

這裡 epsilon 可以預先設定一個固定值, 也可以通過學習得到.

好了, 到這裡我們有AGGREGATION, COMBINE都是一對一映射了

對於READOUT, 直接加和就好了, 為了讓結果漂亮一點, 作者還concat了每一層的特徵

h_G = CONCAT(SUM({ h_v^k | v in G }) | k = 0, 1, dots, K)

不夠強大的GNN

如果用下面的結構就不夠強:

  • 單層Perceptron
  • 用mean pooling或者max pooling代替sum
  • 對於mean, 如果圖的統計信息和分布信息比圖結構重要的話 那麼mean pooling的結果也會不錯. 另外, 如果節點特徵差異比較大並且很少重複的話, 那麼mean和sum一樣強大
  • 如果對於任務來說, 最重要的是確定邊緣節點, 或者說數據「骨架」而不是圖結構的話, max pooling可能效果也不錯

實驗結果

這裡就不詳細敘述了, 個人感覺比較有意思的實驗結果是Figure 4, 作者分別比較了sum, mean, max, mlp, single layer perceptron在訓練集的效果, 看能不能擬合到WL subtree kernel的效果, 實驗結果證明了作者是對的. 至於泛化能力, 理論裡面並沒有對泛化能力做保證, 但是還是效果還是很不錯的.

原文鏈接: github.com/JayYip/deep-


推薦閱讀：
相关文章