本文簡要闡述三篇與此相關的文章，它們分別研究了基於信息傳遞的圖神經網絡 GNNmp 的計算能力，GNNs 的推理能力和阻礙 GCN 變深的問題---over-fitting 與 over-smoothing。
本文涉及的 3 篇 ICLR 原文：
- What graph neural networks cannot learn: depth vs width
- What Can Neural Networks Reason About?
- DropEdge: Towards Deep Graph Convolutional Networks on Node Classification
圖數據在現實世界中廣泛存在，圖神經網絡（GNNs）也在相關的機器學習任務中取得了不錯的效果，但簡單地“將數據給模型、希望其擬合出來可以得到預期結果”的一整套函數在某種程度上是不負責任的。更好地理解 GNNs 適合與不適合哪些問題可以幫助我們更好地設計相關模型。本文簡要闡述三篇與此相關的文章，它們分別研究了基於信息傳遞的圖神經網絡 GNNmp 的計算能力、GNNs 的推理能力和阻礙 GCN 變深的問題---over-fitting 與 over-smoothing。
What graph neural networks cannot learn: depth vs width
機器學習中一個很基礎的問題是判斷什麼是一個模型可以學習和不能學習的。在深度學習中，已經有很多工作在研究如 RNNs、Transformers 以及 Neural GPUs 的表現力。我們也可以看到有工作在研究普遍意義上的 GNNs 相關的理論，如以圖作為輸入的神經網絡。普遍性的表述使得我們可以更好地研究模型的表現力。
理論上，給定足夠的數據和正確的訓練方式，一個這種架構下的網絡可以解決任何它所面對的任務。但這並不應該是一切，只是知道”一個足夠大的網絡可以被用來解決任何問題”無法使我們合理地設計這個網絡，而另一方面，我們需要通過研究他們的侷限來獲取更多關於這個模型的認知。
本文研究了基於信息傳遞的圖神經網絡 GNNmp 的表達能力，包括 GCN、gated graph neural networks 等，並回答瞭如下問題：
（1）什麼是 GNNmp 可以計算的？
本文證明了在一定條件下，GNNmp 可以計算任何可以被圖靈機計算的函數。這個證明通過建立 GNNmp 和 LOCAL 之間的關係來實現。而 LOCAL 是一個經典的分佈式計算中的模型，本身是具有圖靈普遍性的。簡言之，GNNmp 如果滿足如下的幾個較強的條件，即具有足夠多的層數和寬度、節點之間可以相互區分，即被證明是普遍的。
（2）什麼是 GNNmp 不可以計算的？
本文證明了如果乘積 dw 被限制，GNNmp 的能力會損失很大一部分。具體的，本文對於以下的幾個問題展示了 dw 的下限，即檢測一個圖中是否含有一個指定長度的環，確認一個子圖是否是聯通的、是否包含環、是否是一個二分圖或是否具有哈密頓迴路等。
本文展現了 GNNmp 在和合成數據上的實驗結果，選取 4-cycle 分類問題，即將圖根據它們是否包含有 4 個節點的迴路來將其分類的問題來檢驗 GNNmp 的能力，目的在於驗證 GNNmp 的 dw 乘積，節點數 n 和 GNNmp 解決問題的能力之間的關係。
What Can Neural Networks Reason About?
近來，有很多關於構建可以學會推理的神經網絡的嘗試。推理任務多種多樣，如視覺或文本問答、預測物體隨時間的演化、數學推理等。神奇的是那些在推理任務中表現較好的神經網絡通常具有特定的結構，而很多成功的模型均採用 GNN 的架構，這種網絡可以顯示的建模物體兩兩之間的關係，並可以逐步的通過結合某個物體和其它物體的關係來更新該物體的表示。同時，其他的模型，如 neural symbolic programs、Deep Sets 等，也都可以在特定問題上取得較好的效果。但是關於模型泛化能力和網絡結構之間關係的研究仍然較少，我們自然會問出這樣的問題：怎樣的推理任務可以被一個神經網絡學習到？這個問題的回答對我們如何理解現有模型的表現力和其侷限性至關重要。本文通過建立一個理論框架來回答這個問題，我們發現如果可以在推理問題和網絡之間建立良好的對應關係，那麼這個問題可以被很好地解決。
例如，在 Bellman-Ford 算法求解任意兩點間最短路徑的問題上，雖然可以證明 MLP 可以表示任何 GNN 可以表示的函數，但 GNN 的泛化能力更強，而後者決定了 GNN 的效果更好，或者說，GNN 學到了如何去推理。究其原因，GNN 可以通過學習一個很簡單的步驟，即該算法中的鬆弛過程，來很好地模擬 Bellman-Ford 算法，而與此相對應地，MLP 卻必須去模擬整個 for 循環才可以模擬 Bellman-Ford 算法。
DropEdge: Towards Deep Graph Convolutional Networks on Node Classification
GCNs 在圖的很多任務上取得了 SOTA 的表現，如節點分類，社交推薦，關聯預測等，而 over-fitting 和 over-smoothing 是兩個阻礙 GCNs 在節點分類等任務上進一步發展的問題。
我們在四個數據集上驗證 DropEdge 的效果，說明其可以提高 GCNs 的表現裡並確實具有防止 over-smoothing 的作用。
更多 ICLR 論文話題，可通過微信“Moonnn01”加入 ICLR 2020 交流群討論。
閱讀更多 AMiner學術 的文章
