圖神經網路火了？談下它的普適性與局限性

知識 07-29

選自arXiv

作者：Andreas Loukas

機器之心編譯

參與：韓放、張倩

圖神經網路（GNN）是一類基於深度學習的圖域信息處理方法。由於具有較好的性能和可解釋性，GNN 已成為一種廣泛應用的圖分析方法。然而，再好的方法都存在一定的局限。來自洛桑聯邦理工學院的研究者在 arXiv 上發表了一篇論文，指出了圖神經網路在消息傳遞分散式系統中的圖靈普適性和局限性。

本文得出了兩個重要結論：

1. 在足夠的深度、寬度、節點獨立性和層表達條件下，GNN 是圖靈普適（Turing universal）的；

2. 當 GNN 的深度和寬度受到限制時，它們的能力會大大降低。

為什麼要研究 GNN 的局限性

機器學習中的一個基本問題是確定模型可以學習和不能學習的內容。在深度學習中，大量的研究工作都取得了正面的結果。例如，眾所周知，具有足夠深度和寬度的前饋神經網路可以逼近任何通用函數。

最近，我們看到了研究圖神經網路普適性的第一批結果，這些神經網路以圖作為輸入。針對層是線性的且輸入排列是等變的深層網路，Maron 等人得出了一個不變數函數的通用近似定理。Keriven 和 Peyr"E也證明了等變函數的普適性，儘管這一次是在一個特定的淺層體系結構下。擴展到深集，Xu 等人還證明了由和聚集器組成的單圖神經網路層的普適性，該結果後來由 Seo 等人擴展。這些研究從函數層面探究了 GNN 模型能學到什麼，即 GNN 的普適性。

研究 GNN 的普適性使我們能夠在有限的範圍內把握模型的能力。理論上，只要有足夠的數據和正確的學習演算法，一個普適的網路就可以解決它所面臨的任何任務。然而，這些結果帶來的洞察也可能是有限的。知道一個足夠大的網路可以用來解決任何問題，並不能在實踐中指導神經網路設計。當然也不能保證該網路能夠在給定的學習演算法（如隨機梯度下降）下解決給定的任務。

然而，通過研究模型的局限性通常更容易獲得對模型的洞察。畢竟，網路所不能學到的關於特定特徵的知識在應用時獨立於訓練過程。此外，通過幫助我們理解與模型相關的任務的難度，不可能性結果（impossibility result）有助於得出關於如何選擇模型超參數的實用建議。

以圖分類問題為例。訓練一個圖分類器需要識別是什麼構成了一個類，即在同一個類而非其他類中找到圖共享的屬性，然後決定新的圖是否遵守所學習到的屬性。然而，如果可以通過一定深度的圖神經網路（且測試集足夠多樣化）證明上述決策問題是不可能的，那麼我們可以確定，同一個網路將不會學習如何正確地對測試集進行分類，這與使用了什麼學習演算法無關。因此，在進行實驗時，我們應該把重點放在比下限更深的網路上。

本文兩大結論

本文研究了圖神經網路的計算能力局限。作者沒有聚焦於特定的架構，這裡所考慮的網路屬於消息傳遞框架的範疇。選擇該模型是因為它足夠通用，能夠涵蓋幾個最先進的網路，包括 GCN、Chebynet、門控圖神經網路、分子指紋、相互作用網路、分子圖卷積等。本文提出的不可能性陳述（impossibility statement）源於一種新的技術，它能使理論計算機科學的成果重新定位。這將引出涉及圖的一系列決策、優化和估計問題的下界。值得注意的是，這些問題中的一些被認為是不可能的，除非 GNN 的深度和寬度的乘積超過了圖的大小；即使對於看起來很簡單的任務或在考慮近似值時，這種依賴性仍然很強。

具體來講，本文主要得出了兩大結論。

GAN 在什麼情況下具有圖靈普適性

如果滿足一定的條件，GNN 就可以在其輸入上計算任何可由圖靈機計算的函數。這個結果不同於最近的普適性結果，後者考慮了在特定的函數類（不變和等變）和特定的體系結構上的近似（而不是可計算性）。這一主張遵循一種直接的方式，即建立 GNN 與 LOCAL的圖靈等價，這是分散式計算中的一個經典模型，本身就是圖靈通用模型。簡而言之，如果滿足以下四個強條件，GNN 就被證明是圖靈普適的：（i）有足夠的層；（ii）所述層有足夠的寬度；（iii）節點之間互相獨立；（iv）每層計算的函數具有足夠的表現力。

哪些情況下 GNN 學習能力會下降

為了了解更多，作者研究了對不使用讀出函數的 GNN 的深度 d 和寬度 w 進行限制的含義。具體來說，當乘積 dw 受到限制時，GNN 的能力會大打折扣。該分析依賴於一個新的引理，該引理能夠將不可能性結果從 LOCAL 轉換到 GNN。這種方法的主要好處是，它允許我們重新使用從理論計算機科學到圖神經網路設置的幾個重要下界。

設 G 為神經網路的輸入。本文給出了以下問題的下界：

檢測 G 是否包含特定長度的循環；

驗證給定的 G 子圖是否連接，是否包含循環，是否為生成樹，是否為二分體，是否為一條簡單的路徑，是否對應於 G 的割或哈密頓循環；

近似兩個頂點之間的最短路徑，最小割和最小生成樹；

找到最大獨立集、最小頂點覆蓋或 G 的著色；

計算或近似 G 的直徑和周長；

表 1：主要結果總結。

圖 1：給出下界的圖例。

論文鏈接：https://arxiv.org/abs/1907.03199

本文為機器之心編譯，轉載請聯繫本公眾號獲得授權。

------------------------------------------------

喜歡這篇文章嗎？立刻分享出去讓更多人知道吧！