作者 | 蔣寶尚
編輯 | 叢末
6月23日，中科院計算所的研究員、智源研究院的智源青年科學家沈華偉老師在第二屆北京智源大會上做了《圖神經網絡的表達能力》的報告。
在報告中，沈華偉老師提到：這幾年，雖然圖神經網絡在其他領域大量應用，但「內核」仍然停滯不前，目前設計新圖神經網絡（GNN）的兩種常用方式都在面臨理論上的瓶頸。
沈華偉老師還對近幾年圖神經網絡表達能力的相關研究進行了梳理，他說：「GNN出現的早期，大家對它表達能力的認識是基於其在半監督學習，尤其是節點分類任務上的優秀表現，一些應用向的研究也只是對圖神經網絡表達能力經驗上的證明」。
基於這個認知，在介紹完圖神經網絡的基本知識之後，沈華偉老師對圖神經網絡的表達能力給予了理論上的介紹。
以下是演講全文，AI科技評論做了不改變原意的整理。 此文經過沈老師修改。
圖神經網絡過去幾年炙手可熱，也取得了一系列的突破，但是這兩年發展進入了相對停滯的狀態。
當前更多的研究員是把圖神經網絡當做一個工具，也即把圖神經網絡泛化到其他領域進行應用方向的研究。例如早期圖神經網絡在節點分類、鏈路預測以及圖分類上取得了一些進展之後，很快就用在了其他領域，包括推薦領域、自然語言處理領域等等。
其實，圖神經網絡「內核」仍然停滯不前。為什麼呢？因為在設計新GNN的時候通常有兩種方式：一是經驗性的直覺，二是試錯。而這兩種方式都會面臨理論上的瓶頸。
另外，如果只靠試錯，那麼GNN和深度學習就會同樣存在是否「鍊金術」的質疑。那麼GNN帶來的提升究竟來自哪？2019年時，ICLR發表了題為《How powerful are graph neural networks》的文章，掀起了對GNN表達能力的討論。
1
GNN表達能力的經驗性證明
我們今天報告的主題也是討論GNN的表達能力，看看它到底有什麼特色以及限制。
在GNN出現的早期，大家的認識是基於其在半監督學習，尤其是節點分類任務上優秀的性能表現，其中以GCN（圖卷積網絡 ）為代表。
隨後，就有研究員將GNN強大的表達能力用在了推理、認知等領域，更有研究員用在了量子化學領域。
例如一個水分子式H2O，它能告訴我們水分子裡面有兩個氫，一個氧，此表達方式和自然語言處理裡面的TF-IDF是一樣的，能夠看出「詞」出現的頻次，但沒有包含結構信息。
而化學分子式另一種表達，畫出結構圖的模式相當於把分子結構給理清了，於是，研究員開始思考，這「結構圖」是否比原來「頻次」方式有更好的表達能力，如果有了表達能力，那能否用包含結構、包含節點的方式對分子式的化學特性進行預測。如果能，表達能力自然得到了證明。
GNN方法對比傳統密度泛函的分析方法，在算力方面有大幅度的節省。畢竟，密度泛函的分析用模擬的方式進行計算，通常需要高性能計算機進行操作。在現實情況中，GNN確實做到了化學精度以內的預測，用的就是message passing GNN的方式。
所以，如果能用GNN直接擬合一個模型，從而對任意一個新的分子進行性能預測，自然就體現出來了GNN的表達能力，但這只是經驗性表達能力的認識。
另外，在《自然》子刊上，也有一些用GNN建模預測的文章發表，例如預測玻璃的動力學特點、預測地震等等。這些案例也都是對GNN表達能力提供了經驗性的認知，我們接下來想從理論的角度討論GNN的表達能力。
2
GNN基本知識
介紹一下基本的知識，GNN的輸入是一張圖，圖中有節點集合，參數包括V、E、W、X等。GNN早期典型的兩類任務是節點分類和圖分類，在節點分類任務中，GNN的目的是訓練得出網絡當中節點的表達，然後根據節點的表達進行下遊的任務；在圖分類任務中，GNN的目的是要訓練得到圖的表達，有了圖表達之後再對圖做分類。在這兩個典型的任務中，目前80%、90%的工作都傾向於節點分類，只有少數是圖分類。
關於GNN的標準框架，目前用得比較多的是Aggregate+Combine，此框架比較靈活，圖分類任務和節點分類任務都適用，其策略方式是通過迭代，用鄰居的表示迭代更新自己的表示。策略一共分兩步，第一步是聚合鄰居信息；第二步是把鄰居信息和自己上一輪的信息進行耦合。
下面舉幾個這種框架的例子，第一個是2017年提出的GraphSAGE，其操作是把鄰居的表達進行變換之後，取裡面最大的一個賦給自己，然後再把學到的表達和自己上一輪的表達做整合，隨後得到新的表達。值得一提的是，GraphSAGE用了Max-pooling的方式，此方式限制了他的表達能力，是導致表達能力喪失關鍵的一步。
GCN的表達方式直接，將鄰居進行特徵變換，然後按照矩陣規划進行傳遞，它的特點是把AGGREGATE和COMBINE兩個操作進行了整合。值得注意的是，GCN採用了Mean-pooling的方式，此方式也限制了它的表達能力。另外，GCN的改進版是GAT，其採用的方式是weighted mean pooling。
3
圖神經網絡的表達能力如何
前面是關於圖神經網絡基本介紹，現在回到今天的主題：圖神經網絡的表達能力。我們先討論2019年發表在ICLR上的《How powerful are graph neural networks》。
首先明確什麼是表達能力，所謂表達能力一般有兩個方面，第一個方面是表示的空間大小，例如，一個N位的二進位能表達N的二次方個數。這種表達能力旨在表示多少不同的東西，不同的結果。
第二個方面是關於近似能力。例如設計一個神經網絡能夠近似什麼樣的函數。值得一提的是，在1989年的時候就有了證明：神經網絡的層次只要足夠深，就可以逼近任意連續函數。這個「萬能近似定理」也解釋了為什麼深度學習從來不擔心表達能力的原因。
但是GNN提出之後，深度學習表達能力的話題又被提起，2017年有研究員發現深度學習的表達能力和深度神經網絡的層次是指數關係，假如網絡有D層，那麼表達能力與「某個數」的D次方成正比，大家感興趣可以看相關的論文。
GNN引進之後，對於表達能力有什麼樣的啟示呢？如上述左圖所示，如果不看結構，節點的標號標1還是標2是區分不開。如果想區分這個不同的「標號1」，需要觀察標號的鄰居，可以通過鄰居信息進行區分。GCN可以把鄰居信息進行聚合，提升區分節點的能力。如上圖左下所示，在一層GCN操作完成之後，已經可以區分一些標號，但左下圖四個「標3」的點還是區分不出來。
所以，一層GCN區分能力並不夠，那能否通過加深層次解決表達能力呢？兩層GNN之後，如上圖所示，變成了八個點，並可以完全區分開。
所以，如果用兩層GCN對上述節點進行分類，無論Label標記成何種方式，GCN的表達能力都能滿足分類要求。
上面是兩層GCN完全可以區分的例子。回到剛才的問題，把GNN加深就一定能把表達能力做上去嗎？也就是說，我們能不能通過深度實現無窮大的表達能力？2019年那篇ICLR文章回答：不可以！
上面是節點的角度，下面從圖的角度進行討論，也即如果把不同的圖做成一個表示，GNN表示圖的方面表達能力如何。這裡有兩個關鍵因素，一個是節點的特徵，一個是圖的結構，節點的特徵剛才已經講過了，如果把節點做深度神經網絡，已經可以幫我們解決掉表達能力問題。
所以，另外一個表達能力的限制就來自於圖的結構。
下面看兩個簡單的例子，左上角的圖都是24個碳原子，有兩個有機化學的分子式：左邊的結構是兩層，一層12個碳，24個碳分成平行的兩層，都和自己的鄰居相連。右邊圖是24個碳結構變成一個正球體，每個面都由五個碳構成。這兩個結構，人一眼就能看出它倆的不同，但是GCN無法區分，即使把層次加深到無窮多層也區分不了它倆。
即使簡化成左下角兩個更加簡單的圖，GCN也區分不出來。所以，這給出的啟示是：通過提升GCN的深度來提升圖的表達能力，是無法做到的。
那麼它的表達能力受限在哪兒？既然是圖的結構相關，那我們就想到可以採用WL-test，對兩個圖是否同構進行測試。
WL test 的主要是通過聚合節點鄰居的 label，然後通過 hash 函數得到節點新的 label，不斷重複知道每個節點的 label 穩定不變。穩定後，統計兩張圖的label的分布，如果分布相同，則一般認為兩張圖時同構的。
所以，WL test遞歸聚合鄰居的方式和GNN類似，都是一個遞歸地來更新自己的特徵，只不過更新的方式，WL test做了一個單射函數，但是GNN用的聚合函數，無論是Max、Mean還是Sum，大部分情況下都不是單射的。也就是說GNN非單射的聚合方式，把原本不一樣的東西聚合後變得一樣了，這讓GNN喪失了表達能力。
更直白一些，WL Test是一個單射函數，GNN不是單射函數，於是WL Test為GNN的表達能力提供了一個理論上的上界。（註：這裡GNN說的是通過鄰居聚合，如果別的聚合方式，性能可能超過WL test的）
為什麼當前流行的GNN，例如GCN、GraphSAGE為什麼不是單射呢？原因有兩個，一個是每層做特徵變換做得不夠；另一個是，這些圖神經網絡用的聚合函數天然具有單射屬性。
所以，在論文《How Powerful are Graph Neural Networks》中，作者提出來了新的圖模型GIN(Graph Isomorphism Network)，其中I表示圖同構，關鍵思想是構建了一個單射函數。有了單射函數，GIN也達到了和W L test類似的表達能力，達到了圖神經網絡表達能力的上界。
後來作者對GIN模型的表達能力進行了驗證，具體是用數據的擬合能力進行測評，驗證思想是：如果表達能力足夠強，那麼數據集上的每個數據都能精確擬合。驗證結果確實符合作者的預期，通過構造一個單設的聚合函數，能夠實現和WL Test一樣的表達能力。
那麼，泛化能力如何呢？也即在Test Loss 表現如何呢？這裡有一個直觀上的事實是，如果Training Loss做得不好，那麼Test Loss表現也不會好，畢竟Train是Test的基準，另外，如果訓練集上表現非常好，而在測試集上表現非常差，那麼就出現過擬合現象，沒有泛化能力了。
提出GIN的作者也在論文中證實了，GIN在表達能力上很強，但是在其他任務上，泛化能力還不如表達能力差的模型，如上圖GIN在幾個數據集上的表現。
所以，這給圖神經網絡帶來的啟示是：高的表達能力，並不總意味著對下遊任務友好，但是低表達能力總是不好的。綜上，我們還是希望構造出一個強表達能力的圖神經網絡，這是當前學界研究員的共識。
總結一下ICLR 2019那篇論文的工作：首先GNN在理論上有一個表達能力的上界，這個上界是WL Test；為什麼是WL Test？因為它的聚合函數是單射；同時這篇論文又提出了GIN這一有著單射聚合函數的圖神經網絡，並對其表達能力進行了驗證。
4
待討論問題：圖神經網絡的前沿
那篇文章在2019發表之後，引起了很大的關注，其實後來有很多人進行了討論，我把這些問題拋在這裡，大家討論一下。
第一個問題，高的表達能力，到底是不是必要的，我們有沒有必要構造出這麼高表達能力的圖神經網絡？我們能否做出一個通用的極強表達能力GNN，然後再也不用考慮表達能力這個問題了？
我們現在並沒有得到這個問題的答案。對於節點分類，基本上可以提供universal approximitor，對於圖分類無法做到，不僅做不到，而且有些場景下表現還特別差。
那麼，對於特殊的任務，我們有沒有必要構造出高表達能力的東西呢？前面提到，如果表達能力很差，泛化能力肯定不好，表達能力好的，泛化能力也未必好。這在一定程度上也解釋了為什麼GNN和GraphSAGE聚合函數不是單射，表達能力有限的情況下，為什麼還能在一些任務上表現非常棒。
在一些場景下，GNN的大部分表達能力其實用不上。我們真正需要什麼呢？我們需要的是它可以把相似的對象，例如相似的節點和圖映射成相近的表達。
那麼問題又來了，用什麼衡量是否相似？所以就有很多度量兩個圖是否相似的工作。另外，判斷一個複雜對象，能不能分解成簡單對象進行表達這也是個值得探討的問題。
第二個問題，關於結構。其實我們都希望GNN學到結構，大家研究GNN這幾年，也都明白了GNN在結構上無能為力，只是用結構進行了約束，做了平滑。
舉例而言，什麼是一個好的圖表達？假設一個分子結構圖裡面有一個苯環，能不能把這個分子式分成苯，還是說分子式中有很多苯環的情況下，才能分成苯。
這個問題的本質，其實在回答我們做的是信息抽取還是相似性度量。如果想做信息抽取，也就是想識別出分子式裡面有沒有苯結構，現在的GNN做不到這一點，或者必須再設計一些別的方式才能達到。
所以，這兩年大家一直在思考，GNN研究的是模式識別，還是說只是圖相似性的度量方式。
第三個問題，能不能構造一個更強大的GNN呢？也即表達能力更強大的GNN？關於表達能力，一階WL Test已經在理論限制突破能力。這兩年大家更多的研究方式是把常用的1階WL Test拓展成K階，所以就有了KGN的方式。在這樣K階的WL Test方式下，表達方式已經突破1階的能力，但是成本也比較大，因為需要處理的對象增加了很多。
這種方式給大家起了拋轉引玉的作用，給提升GNN表達能力提供了一種思路。但是這種把所有可能都列出來的方式並不是我們所需要的，我們想要的是一個layer-by-layer的網絡，也即如果網絡每一層非常簡單，層次的堆疊是逐漸提升的，然後獲得一個更強大的表達能力。
所以，layer-by-layer網絡也是未來幾年大家應該去探索的一個問題。所以現在我把這個問題拋出來了，你能設計一個這樣layer-by-layer的網絡，從而獲得一個比GNN更強大的表達能力嗎？