【導讀】GNN是目前機器學習領域的熱門網絡之一，肯多研究與技術分享相比不可知的深度學習網絡模型，GNN 有哪些吸引我們的優勢及硬核實力。然而，GNN 是完美的嗎？有什么缺點？在何種情況下，GNN 是無法發揮其能力的？近日，在 arXiv 上發布了一篇論文，專門研究探討了 GNN 在普適性與學習局限性等問題。

本文主要從計算能力有限的角度，來研究GNN在消息傳遞分布式系統中的圖靈普適性和局限性，并得到了兩個與圖論問題能否解決（impossibility statements）有關的結論：

（1）在一定的充足條件下，GNN是具有圖靈普適性的；

（2）而在深度和廣度被限制的條件下，GNN的性能會有一定的局限性。

應用第一個結論，可以對一些圖論優化問題設置更低的計算復雜度下界，第二個結論則說明在深度和廣度的乘積不超過圖的大小時，GNN是無法解決其他的一些問題的。

專業術語

為了方便大家后續閱讀理解文章，我們先把文中涉及的幾個專業問題做簡單闡述：

1、圖靈普適性（Turing universal）

一個具有圖靈普適性的圖靈機（Universal Turing machine）能夠模擬任何圖靈機在任何輸入下的情況。

2、一致性問題（Consensus）

即在分布式計算或者多代理（multi-agent）系統中，如何在發生進程故障的情況下保持系統的可靠性（reliability）。這通常需要進程就計算過程中的一些數值或數值操作達成一致，包括如何將提交到數據庫，如何識別leader進程，狀態機復制（一種故障容忍機制），原子廣播等操作。

3、不可能結果（Impossibility result）

這是分布式領域的專業術語，在一個完全異步的消息傳遞分布式系統中，如果一個進程有故障，那么一致性問題是無法得到解決的，在此基礎上，有兩個比較著名的 impossibility result：FLP和CAP，詳見[1][2]。本文中提出了關于GNN的兩個結論都是屬于GNN的 impossibility results。簡單來說，就是在一定的限制條件下問題能否被解決，那么任務的impossibility result就只有兩種情況：能和不能。

4、GNN的深度和廣度（depth and width）

深度就是網絡層數，廣度就是每層的感知域，也就是每個節點的能獲取到信息的鄰接節點的范圍。

模型普適性的研究

機器學習中的一個基本任務是研究哪些內容是一個模型（網絡）能學習到，而哪些是不能學習到的，也就是研究模型的普適性，研究其能否解決大部分任務。過去的一些研究通過不變函數或者等效函數來對網絡進行等效近似，從而在函數層面研究什么是一個模型能學習到的內容。

通常理論認為，在有充足的訓練數據和合適的學習優化算法的情況下，普適性網絡能夠解決大部分給定的任務，然而這種理解是不全面的，因為在實際應用時要滿足充足訓練數據和合適優化算法是比較困難的，這種無限制的普適性網絡是不能作為實際部署時的網絡設計參考的。

因此，可以從問題的對立面，即研究模型的局限性，來間接地研究其普適性，也就是在特定的任務中，特定的限制條件下網絡不能學習到的內容。這有助于了解模型和特定任務之間的關系，從而知曉任務能否被解決（impossibility results），進而幫助我們調整模型的參數。例如，在圖分類任務中，我們希望模型能學習到同一類圖的共同特征，不同類圖的區別特征，然而如果GNN模型本身的深度和廣度不足以學習到足夠的特征，那么這個問題就是impossible的，因此就需要進一步的調整深度和廣度。

文章主要貢獻

本文所研究的特定任務是圖論中的一些優化任務，特定限制條件是 GNN 的深度和廣度，將深度和廣度與理論計算機科學中的復雜度等度量聯系起來，再將計算復雜度作為這些優化任務的完成下界（從 impossible 變為 possible 的最低復雜度要求），從而得到GNN的深度和廣度對具體任務的影響，以及對GNN普適性的影響。具體地，關于普適性的研究有以下兩個結論。

1、GNN 的圖靈普適性

在足夠的條件下，GNN 能以圖靈機的形式對任意輸入函數進行運算，且不限于網絡結構。通過建立 GNN 和經典分布式計算模型 LOCAL 之間的圖靈等效，來間接的研究其普適性。這里的足夠條件是：

（1）有足夠的層數

（2）每一層都有足夠的廣度

（3）節點之間可以相互獨立（ids）

（4）每一層計算的函數有足夠的表現力

2、GNN 的學習能力局限性

正如前面提到的，在深度和廣度都被限制的情況下，GNN是無法表現出其圖靈普適性，即應用在具體任務上時，無法解決這個任務。那么如何確定能否完成任務的下界呢？還是通過 LOCAL。任務或問題的 impossiblility result 可以在GNN和LOCAL之間以一定的形式相互轉換，因此研究任務在 GNN下能否完成和在LOCAL下能否完成是等效的，進而可以在LOCAL模型下為完成任務的計算復雜度要求設置下界。具體的，文章中提到了四種類型的任務（問題定義詳見原論文）：

（1）檢測（detecting）圖G中是否含有特定長度的環（cycle of specific length）

（2）驗證（verifying）圖G的給定子圖是否連通（connected），是否具有環（cycle），是否為生成樹（spanning tree，具備樹結構，沒有環），是否為二分圖（bipartite，頂點集合可以分為兩個子集，所有邊的兩個頂點分屬于這兩個子集），是否為簡單路徑（simple path，與圖的哈密頓循環有關）

（3）計算（computing）兩個頂點間的最短路徑（shortest path between two vertices），圖的最小割（minimum cut），以及最小生成樹（the minimum spanning tree）

（4）求圖的最大獨立集（maximum independent），最小頂點覆蓋（minimum vertex cover），或圖的頂點著色問題（chromatic coloring）

以上問題都是屬于圖論中的傳統優化問題，雖然不是現在主流研究的頂點分類，圖分類問題，但二者之間有密不可分的聯系。這些問題的具體計算復雜度下界為：

總結

本文首次對GNN模型提出了 impossible 問題，并通過等效計算的方法，以計算復雜度的形式，給出了 GNN 在部分圖論任務中impossible results下界與網絡寬度和廣度的關系，在一定程度上說明了 GNN 的性能會受到網絡本身的寬度和廣度的限制。

由于原文中的數學推導過于復雜，因此這里我只介紹文章的基本思想。GNN作為目前機器學習領域的熱門研究之一，已經被應用于各種各樣的任務，通常在應用一個網絡的同時，也要同步地去研究這個網絡的內在本質，從而更好的理解，改進它，進而幫助我們在實際應用網絡時更好的設置網絡的參數，這篇文章就是一個很好的例子。