深度學習領域關於圖神經網絡(Graph Neural Networks，GNN)的研究熱情日益高漲，圖網絡已經成為2019年各大深度學習頂會的研究熱點。GNN 處理非結構化數據時的出色能力使其在網絡數據分析、推薦系統、物理建模、自然語言處理和圖上的組合優化問題方面都取得了新的突破。但是，大部分的圖網絡框架的建立都是基於研究者的先驗或啟發性知識，缺少清晰的理論支撐。
本文介紹ICLR2019的一篇論文，提出基於WL圖同構測試的理論框架，為眾多的GNN框架給出了精彩的理論分析，並提出了一個簡單但是強大的圖網絡框架 GIN(Graph Isomorphism Networks)，並驗證了GIN在圖分類任務上的卓越性能。
在剛剛過去的ICLR 2019會議中，一篇 Oral 的會議文章回答了很多圖網絡研究者都在思考的一個問題：圖神經網絡到底有多厲害 ( How Powerful are Graph Neural Networks) ？
本文是史丹福大學複雜網絡數據分析大佬 Jure Leskovec 教授團隊的最新力作(Node2Vec、GraphSAGE等經典工作也是出自該團隊)。自該工作公開以來，已經有了近70的citations，表明圖網絡社區對該工作的關注度很高。
論文題目：
How Powerful are Graph Neural Networks?
論文地址：
https://arxiv.org/pdf/1810.00826.pdf
眾所周知，圖網絡(GNNs)的新變體層出不窮，但是卻鮮有對圖網絡框架的理論分析。Kipf在2017年提出的GCN中，曾從圖上的譜分析的角度給出了GCN的理論基礎；近期也有日本研究者從圖信號處理的角度，表明GNNs只是一個低頻濾波器(arxiv.org/abs/1905.09550)。而本文嘗試從圖同構的角度出發，以Weisfeiler-Lehman Isomorphism Test (WL test)為基礎，給出了GNNs表徵能力的精彩理論分析，具體的貢獻總結如下：
作者表明，在區別不同圖結構時，GNNs最多只能取得和 WL test 一樣效果，即，GNNs表徵能力的上限是WL test；
作者也給出了構建GNNs的條件，滿足這些條件後，GNNs的表徵能力和 WL test一樣強；
給出了GCN和GraphSAGE等傳統圖網絡框架不能區分的網絡結構；
建立了一個簡單的框架GIN，並在理論上證明了其表徵能力和 WL test一樣強。
總結起來，全文需要回答兩個關鍵性的問題：
GNNs表徵能力的上限是什麼？
怎樣的GNNs 框架設計才能達到最好的表徵能力？
這裡的表徵能力是指對圖拓撲結構的表徵是否能有效區分不同的圖結構。所以，是否能夠判斷圖同構便成了GNNs表徵能力的判斷標準。如果GNNs對圖的表徵能區分同構或不同構的圖，則表明其有較強的表徵能力。
但圖同構是一個非常難的問題，至今還沒有有效的方法判斷兩個圖是否同構，所幸WL test是一個非常有效的圖同構檢驗近似方法，對圖結構具有很強的表徵能力。那麼，GNNs能否具有WL test一樣的表徵能力？有的話，怎麼設計框架怎樣達到和WL一樣的水平？
GNNs
大多數的GNNs可以歸結為 aggregation based 或者 message-passing based 的框架，主要包含聚合鄰居信息和更新節點信息兩步，AGGREGATE 和 COMBINE：
不同的GNNs區別就在與採用不同的 AGGREGATE 和 COMBINE 函數。比如GCN的 AGGREGATE 函數就是採用的mean-pooling，而GraphSAGE則是採用max-pooling。
The Weisfeiler-Lehman Isomorphism Test
WL test是一種有效的檢驗兩個圖是否同構的近似方法。當我們要判斷 Graph1 和 Graph2 是否同構時，WL test 的主要步驟如下圖所示，通過聚合節點鄰居的 label，然後通過 hash 函數得到節點新的 label，不斷重複知道每個節點的 label 穩定不變。
穩定後，統計兩張圖的label的分布，如果分布相同，則一般認為兩張圖時同構的。
我們可以發現，WL test 方法的步驟和GNNs具有異曲同工之妙，都是通過不斷聚合鄰居信息，得到節點的新表示，這也是為什麼Kipf在2017年GCN的論文中單獨討論和GCN和WL test關係的原因。而正是這種統一性，才使得本文能以 WL test 為基礎來分析GNNs框架。
本文作者基於WL test和GNNs框架的相似性，層層推進，給出了一系列重要的結果。
首先，作者說明GNNs框架的表徵能力不會超過WL test：
對於兩個不同構的圖，如果GNNs能將其map到不同embs，那麼WL test也會得出不同構的結論。既然GNNs不能超過WL test， 那麼如何才能和WL test一樣有效呢？
上圖展現了WL test與GNNs在表徵網絡結構時的共同點：一個節點的表徵都是由以該節點為父節點的子樹信息聚合得到(中間圖)。而在聚合的過程中，WL test最大的特點是其聚合函數採用的是單射(injective)的 hash 函數。那麼，是否將 GNNs 的的聚合函數也改成單射(injective)函數 就能達到和WL test一樣的效果呢？作者給出了肯定的答案：
該結論說明：如果GNNs的聚合函數是定義在multiset上的單射函數，那麼GNNs和WL的表徵能力一樣。也給出了設計 powerful 的 GNNs 框架的首要條件：injective。
但是，上述結論雖然給出了設計有效GNNs框架的充分條件，但是並沒有給出具體的設計指南，我們仍然不知道如何才能找到具有單射性質的聚合函數。而如下的結論很好的給出了答案：
上述結論表明，如果我們把節點上一層的表徵表示為c，其鄰居的表徵的集合表示為X，那麼任意關於 c 與 X 的函數 g (當然包括單射函數) 都可以表示為\phi 與 f 的複合形式。而該複合函數可以用萬能擬合函數MLPs來擬合，至此，作者們就得到了一個非常簡單的GNNs框架：
稱之為GIN (Graph Isomorphism Networks)， 該框架最大的特點就是簡單，並且其有效性具有理論保證。在圖分類的實驗中，該框架也表現出了SOTA的性能。
很過經典的GNNs框架採用 mean-pooling 或者 max-pooling的方法，而作者提出，這些聚合方法並不是單射函數，其不能區分一些不同的局部結構，從而導致框架的表徵能力下降：
比如上圖所示：相同的顏色代表相同的節點屬性。在圖a, b, c中，節點 v 與 v『 的局部結構均不相同，但是Mean 和 Max 卻不能有效區分，會導致兩種局部結構得到相同的節點表徵，從而丟失了網絡的結構信息。
但是採用Mean和Max-poling的框架(GCN，GraphSAGE)表現都很好，那麼他們學到了什麼呢？
作者認為：
Mean-pooling 致力於學習節點 feature 的分布： 所以，在下述情況中，Mean也能表現的很好：
當我們的任務之和節點feature的分布有關，而與具體的局部結構無關時
當節點的具有豐富的feature，很少重複時
這就解釋了為什麼GCN在做節點分類時，為什麼會有那麼好的效果：因為每個節點的特徵很難會重複。
Max 學的是 underlying set：Max處理Multiset時，只關心其對應的underlying set。所以，Max既沒有學到局部結構，也沒有學到分布。當我們關心Representative element或者「skeleton」時，Max會有好效果。
本文為了體現GIN在表徵網絡結構信息的的出色能力，選擇用網絡分類實驗來驗證其有效性。
Training Set Accuracy
我們需要強調的一點時，文中對GNNs表徵能力的分析只關係其擬合能力，即是否能對訓練數據進行充分的擬合，這一點可以由訓練過程的 training set accuracy 來驗證：
上圖表明，在5個數據集上，GIN的訓練精度都是最高，說明其擬合能力最好，即其對網絡結構的表徵能力最強。值得注意的是，GIN的訓練精度最高也沒有超過WL subtree kernel的精度，這樣驗證了文中的理論結果：GIN和 WL 一樣強，但是不會超過WL。
Test Set Accuracy
在網絡分類實驗的測試集上，GIN在多個數據集上均取得了SOTA的成績，表明GIN框架不僅有最強的擬合能力，還具有優秀的泛化能力。
該論文對基於聚合的GNN做了非常精彩的理論分析，給出了GNNs的表徵能力的上界，同時給出了如何設計GNNs才能使其表徵能力最強的條件。在此基礎上，設計了一個異常簡單的圖網絡框架GIN，但是卻非常的有效，在圖分類任務上取得了SOTA的成績。這篇工作表明了基於理論分析的框架構建是多麼的有效，使我們必須承認，對更加廣義的GNNs的理論分析是圖網絡社區的基礎性任務。
CLR 2019 OpenReview (推薦閱讀):
https://openreview.net/forum?id=ryGs6iA5Km
論文的Github頁面:
https://github.com/weihua916/powerful-gnns
相關博客：
https://asail.gitbook.io/hogwarts/graph/how_powerful
https://www.davidbieber.com/post/2019-05-10-weisfeiler-lehman-isomorphism-test/
錄播地址：
http://campus.swarma.org/play/coursedetail?id=10936
集智俱樂部QQ群｜877391004
商務合作及投稿轉載｜swarma@swarma.org
搜索公眾號：集智俱樂部
加入「沒有圍牆的研究所」
讓蘋果砸得更猛烈些吧！