雷鋒網AI科技評論按：近年來，圖神經網絡（GNN）領域內可謂百家爭鳴。然而，真正要想在圖神經網絡的設計上有革命性的創新，不可避免地要對圖論的本質問題進行深入探究。
本文是一篇來自京都大學的圖神經網絡表達能力綜述，從GNN、WL 算法、組合優化問題之間的聯繫入手，進行了深入的歸納和分析。內容涉及計算機網絡通信、網絡算法，組合數學、可計算性分析等方面，內容非常豐富，其融會貫通的能力令人歎為觀止！
原文鏈接：https://arxiv.org/pdf/2003.04078v1.pdf
一、引言
對於各種各樣的圖學習問題來說，圖神經網絡（GNN）是非常有效的機器學習模型。這些問題包括化學信息學、推薦系統、問答系統、以及組合優化問題。Hamilton、Zhou、Wu 等人分別於 2017、2018、2019 年對 GNN 做了全面的綜述。
儘管在許多領域中，GNN 在實驗中都取得了成功，但是 Xu 等人和 Morris 等人卻指出，GNN 不能夠區分一些圖對。這說明 GNN 不能使用任何參數正確地對這些圖進行分類，除非這些圖的標籤是相同的。這樣的結果與多層感知機的通用近似能力形成了鮮明的對比。
此外，Sato 等人指出了 GNN 最多能像分佈式局部算法（Distributed Local Algorithm）一樣強大。因此，除了圖同構問題，還有許多 GNN 無法解決的組合優化問題。所以，研究人員提出了各種各樣可證明的強大的 GNN 模型，從而克服 GNN 的侷限性。
針對 GNN 的表達能力和各種各樣為了克服這些侷限性而設計的 GNN 模型，本文給出了一個全面的概述。與其它關於 GNN 的綜述（介紹 GNN 的架構和應用）不同，本文重點關注 GNN 的理論特性。
本文的組織結構如下：在本章的其餘部分中，我們將介紹本文使用的數學符號並簡要回顧標準的 GNN 模型。在第 2 章中，我們看到 GNN 不能使用基本的參數和具體的示例來區分某些圖。在第 3 章中，我們介紹了 GNN 和 WL 算法之間的聯繫。在第 4 章中，我們根據 GNN 與分佈式局部算法的聯繫，介紹了 GNN 可以/不可以求解的組合優化問題。在第 5 章中，我們將 GNN、WL 算法，以及分佈式局部算法之間的關係總結為「XS 一致性」（XS correspondence）。
1、數學符號
表一為本文中使用到的數學符號：
表 1：數學符號
{...} 表示一個集合，{{...}} 表示一個多重集。 在多重集之中，同一個元素可以出現多次。例如，{3,3,4} = {3,4}，但是{{3,3,4}} ≠ {3,4}。有時，我們將一個集合看做一個多重集，反之亦然。
對於每個正數
，[n] 代表集合 {1,2,...,n}。諸如 a,b 和 c 這樣的小寫字母代表一個標量，一個加粗的小寫字母（如 a,b 和 c）代表一個向量。諸如 A,B 和 C 這樣的加粗大寫字母，代表一個矩陣或一個張量。A^T 代表 A 的轉置。對於向量
以及
，
代表 a 和 b 的串聯。
表示點集 V 和邊集 E 組成的對。n 代表節點的數量，m 代表圖與上下文無關時邊的數量。
對於每個節點 v 來說，N(v) 代表 v 的鄰居節點的集合，deg(v) 代表 v 的鄰居節點的個數。如果一張圖包含節點特徵向量
，圖可以被表徵為一個元組 G=(V,E,X)。
代表節點 v 在第 l 層中的嵌入（詳見公式 2）；
代表第 l 層的聚合函數（詳見公式 1）；
代表第 l 層的更新函數（詳見公式 2）；
為讀出函數（詳見公式 3）；
為輸入圖中度的最大值；b(k) 代表第 k 個貝爾數；H(k) 為第 k 個調和數
。
2、 問題設定
本文重點關注以下的節點分類問題和圖分類問題。
1）節點分類問題
輸入：一張圖 G=(V，E，X)，其中每個節點 v∈V
輸出：v 的標籤 y_v
2）圖分類問題
輸入：一張圖 G=(V，E，X)
輸出：圖 G 的標籤 y_G
具體來說，我們考慮的是 GNN 可以計算的函數
以及
的類別。因為 GNN 不能對圖上所有的函數建模（詳見本文後續部分）。
3、圖神經網絡
再簡要介紹標準的 GNN 模型。
1）GNN 發展史
Sperduti 和 Starita 以及 Baskin 於 1997 年首次提出類似於 GNN 的模型。他們使用神經網絡從圖數據中抽取出特徵，而不是使用手動設計的圖特徵。Sperduti 和 Starita 於 1997 年遞歸地應用了一種線性聚合操作以及非線性激活函數，而 Baskin 等人則於 1997 年使用了參數共享機制對節點和邊特徵的不變性變換進行了建模。
這些特性在現代 GNN 中非常普遍。Gori 等人於 2005 年、Scarselli 等人於 2009 年分別提出了新型的圖學習模型，它們使用了遞歸的聚合技術並且將這些模型稱為圖神經網絡。
值得注意的是，在本文中，GNN 不僅僅代表這類模型，GNN 是代表這類模型的後續變體的通用術語。
Li 等人於 2016 年將 Gori 等人（2015）和 Scarselli 等人（2009）的思想擴展到了門控圖神經網絡上。分子圖網絡（Merkwirth 和 Lengauer，2005）是一種具有相似架構的圖神經網絡的並行模型，其層數為一個常數。
Duvenaud 等人於 2015 年構建了一種受圓形指紋啟發的 GNN 模型。受核消息傳遞算法（Song 等人於 2010、2011 年提出）的啟發，Dai 等人於 2016 年提出了一種新的 GNN 模型。Gilmer 等人於 2017 年使用消息傳遞機制提供了一種對 GNN 的統一視角，從而表徵 GNN。
在本文中，我們並不考慮 GNN 模型的頻域變體（例如 Bruna 等人於 2014年發表的論文「 Spectral networks and locally connected networks on graphs」，以及 Defferrard 等人於 2016 年發表的論文「 Convolutional neural networks on graphs with fast localized spectral fifiltering」），僅僅考慮基於消息傳遞機制的空域方法。
圖 1：單層消息傳遞圖神經網絡。
圖 2：雙層消息傳遞圖神經網絡。
2）消息傳遞機制
根據消息傳遞機制，L 層的 GNN 可以被形式化定義如下：
其中，
和
都是參數化函數。在這裡，
可以被看做節點 u 在第 k 個消息傳遞階段中的「消息」。每個節點將聚合它們鄰居節點的消息，從而計算出下一個消息或嵌入。GNN 基於最終的嵌入
對節點 v 進行分類。
當沒有可用的節點特徵
時，根據 Xu 等人於 2019 年發表的論文「How powerful are graph neural networks?」以及 Knyazev 等人於 2019 年發表的論文「Understanding attention and generalization in graph neural networks」，我們使用獨熱的度向量作為初始的嵌入。
圖 1 和圖 2 對這種方案進行了說明，其中顏色代表特徵和嵌入。相同的顏色代表相同的向量。
在本例中，圖 1 中的單層 GNN 無法區分出左下角用嵌入 3 表示的節點。這說明這些節點擁有不同的類標籤，單層 GNN 往往不能正確對這些節點進行分類，這是因為 GNN 僅僅基於最終的嵌入對接點進行分類。相反，如圖 2 所示，雙層 GNN 就可以將所有節點區分開來。
除了結構上的限制，一般而言，
和並不一定要是單射函數。例如，
可能是成立的。這就對 GNN 施加了更多的限制。本文旨在確定 GNN 可以/無法識別的圖的特性。
在圖分類問題中，GNN 使用讀出函數計算圖嵌入
：
其中，
是一個參數化的函數。GNN 基於圖嵌入
對圖 G 進行分類。典型的 GNN 模型可以通過如下所示的消息傳遞框架形式化定義。
GraphSAGE-mean（詳見 Hamilton 等人於 2017 年發表的論文「Inductive representation learning on large graphs」）
其中
是一個參數矩陣，而σ是一個激活函數（如 sigmoid 和 ReLU）。
圖卷積網絡（GCN，詳見 Kipf 和 Welling 等人於 2017 年發表的論文「Deep models of interactions across sets」）
圖注意力網絡（GAT，詳見 Velickovic 等人於 2018 年發表的論文「Weak models of distributed computing, with connections to modal logic」）
嚴格來說，在這些模型中，
並不僅僅是關於
的函數，它還用到了鄰居節點的度以及注意力權重這些邊信息。然而，這些信息可以被認為被包含在了消息
中。因此，這裡使用的數學符號並不會影響這些模型可以計算的函數的類別。
Gilmer 等人於 2017 年發表的論文「Neural message passing for quantum chemistry」介紹了許多其它的消息傳遞 GNN 的示例。
二、 GNN 無法區分的圖
圖 3：GNN 不能區分上面兩種分子，因為它們都是包含 20 個節點的 3-正則圖。
本章討論樸素的 GNN 無法通過基本參數和具體示例區分的圖。
K-正則圖是一種每個節點都恰好有 k 個鄰居節點的圖。如圖 3 所示，「Decaprismane C_20H_20」和「Dodecahedrane C_20H_20」都是 3-正則圖。顯然，消息傳遞 GNN 無法區分具有相同尺寸和節點特徵的 k-正則圖。
我們在圖 4 中說明了這種現象。由於右邊的圖包含三角形，而左邊的圖並不包含三角，所以這兩個圖並不是同構的。然而，左圖和右圖中所有節點中的所有的消息是相同的。因此，最終通過 GNN 計算得到的所有嵌入都是相同的。這種結果並不盡如人意，因為如果兩個正則圖（例如，「Decaprismane C_20H_20」和「Dodecahedrane C_20H_20」）有不同的類標籤，無論模型參數如何，消息傳遞 GNN 往往無法區分它們。
除了正則圖意外，還有許多非正則、非同構的圖是 GNN 無法區分的。圖 5 列舉出了一些 GNN 無法區分的非正則、非同構的圖的示例。圖 5(a) 和 (b) 是通過為圖 4 中正則圖中的節點附上一個「葉子」結點生成的（就像附上一個氫原子一樣）。圖 5(e) 和 (f) 包含除度特徵之外的節點特徵，但是 GNN 不能區分它們。
圖 6 中的十氫化萘 C_10H_18 和雙環戊烷 C_10H_18 是 GNN 無法區分的現實世界中的圖，同理圖 5(c) 和 (d) 也是 GNN 無法區分的。同樣的，這也說明如果兩個分子有不同的類標籤，無論模型參數如何，GNN 往往無法區分他們。似乎 GNN 無法區分的圖是無窮無盡的。
那麼，我們能歸納出這類 GNN 無法區分的圖的特點嗎？下一章將介紹 Xu 等人和 Morris 的研究成果，它們通過「Weisfeiler-Lehman」算法描述了這類圖。
圖 4：消息傳遞 GNN 並不能將任何一對具有相同的度和尺寸的正則圖區分開來（即使他們並不是同構的）。
圖 5：儘管這些圖並不是同構的，但是 GNN 也無法將 a 和 b、c 和 d、e 和 f 區分開來。
圖 6：GNN 無法將這兩種分子區分開來，即使這些圖不是同構或正則的。
三、GNN 與「Weisfeiler-Lehman」算法的聯繫
在本章中，我們將介紹 GNN 與 Weisfeiler-Lehman 算法之間的聯繫
1、Weisfeiler-Lehman 算法
圖同構問題，是一種確定一對圖是否同構的決策問題。
輸入：一對圖 G=（V，E，X）和 H=（U，F，Y）
輸出：確定是否存在一種雙射
使得
且
當且僅當
若兩圖同構，則我們認為這兩個圖相等，GNN 應該輸出相同的嵌入。
Weisfeiler-Lehman（WL）算法是一種被用來解決圖同構問題的算法。WL 算法有許多種變體：
1）1-維 WL（1-WL）算法（也稱「color refinement」）：是最常用的變體，我們有時直接將其稱為 WL 算法。該算法為每個節點賦予一種標籤（顏色），並不斷聚合鄰居節點信息、修改節點的標籤（顏色），直到標籤不再變化（收斂）。
輸入：一對圖 G=（V，E，X）和 H=（U，G，Y）
其中 HASH 是一種單射哈希函數。如果 1-WL 算法輸出「非同構」，那麼 G 和 H 就不是同構的圖，但即使 1-WL 算法輸出「可能同構」，G 和 H 仍有可能非同構。例如，對於圖 4 中的圖，1-WL 算法將輸出「可能同構」，然而它們並非同構。1-WL 算法可以保證在時間複雜度為
的迭代過程之內完成。
2）K-維 WL 算法： 1-維 WL 的推廣。k-維 WL 為每 k 個節點組成的元組賦予一種顏色。
輸入：一對圖 G=（V，E，X）和 H=（U，F，Y）
其中，
是第 i 個鄰居節點，它使用 G 中的每個節點替換 k 元組中的第 i 個元素。「HASH」是一種單射的哈希函數，它為相同的同構型賦予相同的顏色。換而言之，
當且僅當
；
當且僅當
∈
。這種限制對於
和
，以及
和
同樣成立。
3）K-維 folklore WL（k-FWL）算法：是 1 維 WL 算法的另一種推廣。
其中
。K-WL 和 K-FWL 仍然存在不足。如果 K-WL 和 K-FWL 輸出「非同構」，那麼 G 和 H 則不是同構圖，但即使 K-WL 和 K-FWL 輸出「可能同構」，G 和 H 仍然可能不是同構圖。
WL 算法的變體的能力具有如下關係：
1-WL 與 2-WL 能力相當。換句話說，對於任意一對圖，這兩種算法的輸出相同。
對於任意的 k≥2，k-FWL 的能力與 (k+1)-WL 相當。
對於任意的 k≥2，(k+1)-WL 一定比 k-WL 能力更強。換句話說，存在一對非同構圖（G，H），使得 k-WL 輸出「可能同構」，但 (k+1)-WL 輸出「非同構」。
圖 7：WL 算法相關變體的層次
研究者們已經大量研究了 WL 算法可以/無法區分的圖所具備的性質。值得注意的是：
如果兩圖都是隨機抽取的，那麼隨著圖的尺寸趨向與無限大，1-WL 算法失效的概率趨近於 1。
當 k≥2 時，存在一對尺寸為 O(k) 的非同構圖（G，H），使得 k-WL 的輸出為「可能同構」。
對任意一對非同構樹 S 和 T，1-WL 算法輸出 S 和 T 都是「非同構的」。
對於任意的正整數
以及一對有 n 個頂點的 k 正則圖 G 和 H，1-WL 算法輸出的 G 和 H 是「可能同構」 。
在準線性時間內，1-WL 算法可以將圖與和它非同構圖的區分開來。
2、GNN 和 WL 算法之間的聯繫
本節介紹 GNN 與 WL 算法之間的聯繫。
定理 1：對於任意的消息傳遞 GNN 和任意的圖 G 和 H，如果 1-WL 算法輸出 G 和 H 是「可能同構」的，那麼由 GNN 計算出的嵌入 h_G 和 h_H 是相同的。
換而言之，消息傳遞 GNN 並沒有 1-WL 那樣強大。這是因為聚合函數和更新函數可以被看做 1-WL 算法的哈希函數，而聚合函數和更新函數並不一定是單射的。在這種 GNN 和 1-WL 的對應關係的啟發下，Xu 等人於 2019 年發表的論文「How powerful are graph neural networks? 」通過使聚合函數和更新函數限制為單射函數，提出了一種與 1-WL 一樣強大的 GNN——圖同構網絡（GIN）：
其中，
是一個標量參數，MLP 是一個多層感知機。根據深度多重集理論（GIN 的聚合函數在某些假設下是單射函數），GIN 與 1-WL 一樣強大。
定理 2：對於所有的
，存在 L 層 GIN 的參數使得：若節點的度以一個常數為上界，且節點特徵的支撐集的大小有限，那麼對於任意的 G 和 H，如果 1-WL 算法在 L 次迭代內輸出 G 和 H 是「非同構」的，則由 GIN 計算出的嵌入 h_G 和 h_H 是不同的。
推論 3：對於任意的圖 G 和 H，如果 1-WL 算法輸出 G 和 H 是「非同構」的，那麼存在 GIN 的參數使得由 GIN 計算出的嵌入 h_G 和 h_H 是不同的。
由於 1-WL 算法定義了消息傳遞 GNN 表達能力的上界，GIN 也有時被稱為最強大的消息傳遞 GNN。那麼，我們如何才能構建比 1-WL 算法更加強大的 GNN 呢？
Morris 等人於 2019 年基於 k-WL 算法的一種變體提出了一種更為強大的模型。他們用「集合 k-WL」算法替代了「k-WL」算法，從而減小內存開銷。
1）「集合 k-WL」算法
令
為 V 的包含 k 個節點的子集。
。「集合 k-WL」算法為每個由 k 個節點組成的集合賦予一種顏色。
其中，
是一種單射哈希函數，它為由 S 劃分的子圖賦予一種顏色。集合 3-WL 算法可以區分三角形（1-WL 無法做到這一點）。因此，集合 3-WL 算法可以區分圖 5 中的 a 和 b、c 和 d、e 和 f，而 1-WL 算法則無法區分。由於三角形的個數（即聚類係數）在各種網絡中有著很重要的作用，所以集合 3-WL 的這種特性是迫切需要的。
然而，集合 3-WL 算法無法區分圖 8 中的 a 和 b，因為 3-WL 算法無法將其區分。需要注意的是，集合 k-WL 算法一定弱於 k-WL 算法。例如，3-WL 可以區分圖 9 中的 a 和 b（因為 3-WL 可以檢測出 4 聯通分量的數目），而集合 3-WL 算法無法做到這一點。
Morris 等人於 2019 年基於集合 k-WL 算法提出了 k-維 GNN（k-GNN）。k-GNN 為每 k 個節點組成的集合賦予一種嵌入。
2）k-維 GNN（k-GNN）
其中，
根據 S 劃分的子圖賦予一個特徵向量。k-GNN 可以被看做在拓展圖
上進行操作的消息傳遞 GNN，此時節點的集合為
，存在
和
之間的一條邊，當且僅當
。k-GNN 與集合 k-WL 算法能力相當。
圖 8：儘管這些圖是非同構的，3-維 WL 算法和 3-GNN 也不能區分 a 和 b。
圖 9: 3-維 WL 算法可以區分這些圖，但是集合 3-維 WL 算法無法做到這一點。
定理 4：Morris 等人於 2019 年提出，對於任意的圖 G 和 H，當 k≥2 時，如果集合 k-WL 算法輸出 G 和 H 是「非同構」的，那麼存在 k-GNN 的參數使得由 k-GNN 計算得到的嵌入 h_G 和 h_H 不同。
k-GNN 需要維護
個嵌入，因此其內存開銷相當大。在 Maron 等人 2019 年發表的論文「Provably powerful graph networks」中，他們基於 2-FWL 算法提出了一種與 3-WL 能力相當，但只用維護
個嵌入的 GNN 模型，從而緩解了內存開銷的問題。為了介紹該模型，讀者需要了解高階不變和等變 GNN。
3、高階圖神經網絡
本章介紹高階不變和等變 GNN。首先形式化定義不變性和等變性。令
為集合 [n] 上的對稱群。
對於一個張量
以及一種排列
，我們定義
為
。
對於一個張量
以及一種排列
，我們定義
為
。
定義 5（不變性）：若對於任意
和
，
成立，則會函數
是不變的。若對於任意
和
，
成立，則函數
是不變的。
定義 6（等變性）：若對於任意
和
，
成立，則函數
是等變的。若對於任意
和
，
成立，則
是等變的。
不變性是 l=0 時的等變性的特例。我們可以很自然地想到，圖學習模型應該具備不變性和等變性，因為圖不會由於任何節點擾動而改變。
Maron 等人推廣了 Zaheer、Kondor、Hartford 等人的思想，列舉出了所有不變和等變的線性變換。他們發現，不變和等變線性變換的基的大小與維度 n 無關。具體而言，線性不變變換
的基的大小為 b(k)，
的基的大小為 b(k+l)，其中 b(k) 是第 k 個貝爾數（即集合 [k] 的劃分的數量）。
定理 7：
構成了線性不變性變換
的一組正交基。
定理 8：
構成了線性等變性變換
的一組正交基。
因此，任意的線性不變和等變變換可以分別通過大小為 b(k) 和 b(k+l) 的基向量的線性組合進行建模。Maron 等人於 2019 年提出使用這種變換作為非消息傳遞 GNN 的構建模塊。Maron 等人通過揭示高階 GNN 和 高階 WL 算法之間的關係，並提出了一種新的基於高階 FWL 算法的高階 GNN 模型，緩解了參數過多、內存開銷過大的問題。首先，Maron 等人說明使用 k 階張量的高階 GNN 與 k-WL 的能力相當。
定理 9：對於任意的圖 G 和 H，如果 k-WL 算法輸出「非同構」，則存在最多帶有 k 階（
）張量的高階 GNN ，使得由高階 GNN 計算得到的嵌入 h_G 和 h_H 是不同的。
這說明在一般情況下， n 階張量是充分且必要的。必要性： 存在一對大小為 O(k) 的非同構圖，使得 k-WL 算法無法區分。充分性：n-WL 可以區分所大小為 n 的圖。
接著，Maron 等人提出了一個與 2-FWL 算法能力相當的 GNN 模型。
定理 10：對於任意的圖 G、H，如果 2-FWL 算法輸出「非同構」，存在二階 folklore GNN 的參數，使得由二階 folklore GNN 計算得到的嵌入 h_G 和 h_H 是不同的。
4、關係池化
本節將介紹另一種 Murphy 等人於 2019 年在論文「Relational pooling for graph representations」中提出的構建強大的 GNN 的方法。這種思路非常直接，關係池化層取所有可能的排列的平均（如 Jannosy 池化）。
也就是說，令 f 為一種消息傳遞 GNN，A 為 G=（V，E，X）的鄰接矩陣，
為單位矩陣，
為 V 上的對稱群。由此，關係池化 GNN（RP-GNN）可以被定義為：
換句話說，RP-GNN 串聯了節點索引的獨熱編碼和節點特徵，然後對所有可能的排列取平均。RP-GNN 的強大之處在於，它在構造上具有明顯的排列不變性，比 GIN 和 1-WL 算法更加強大。
定理 11：RP-GNN 比原始的消息傳遞 GNN f 更加強大。尤其是當 f 是通過 GIN 建模時，以及圖帶有離散屬性時，RP-GNN 比 1-WL 算法要更加強大。
四、GNN 與組合優化問題的聯繫
至此，我們已經探討了圖同構問題。本章將討論其它的組合優化問題，例如：最小頂點覆蓋問題、最小支配集問題、最大匹配問題，並通過計算 GNN 的算法效率評估 GNN 的表達能力。具體而言將介紹 GNN 和分佈式局部算法（Distributed Local Algorithms）之間的關係。
值得注意的是，在本章中，對於建模組合優化算法而言，GNN 並不一定需要具備不變性或等變性。
1、分佈式局部算法
分佈式局部算法是在恆定時間內運行的分佈式算法。具體而言，一個分佈式局部算法解決了計算機網絡領域中本身存在的一個問題：每臺計算機運行相同的程序，每臺計算機與相鄰計算機進行一定數量的同步通信後，再決定輸出。
例如，假設移動設備與附近的設備組成了一個通信網絡。通信網絡必須包含中心節點來控制通信，這個中心節點必須形成網絡的一個頂點覆蓋（即每條邊至少被一箇中心節點覆蓋）。中心節點的數目需要儘可能的小，但是每個移動設備必須要在 5 輪通信之內被聲明為中心節點。
那如何才能設計滿足要求的算法呢？該問題的示意圖如圖 10 所示。
圖 10：分佈式局部算法示意圖。左：與鄰居計算機的通信。右：在一定次數的通信後，每個節點的應答。
目前，已經有多種分佈式算法的計算模型。在分佈式局部算法的計算模型中，標準計算模型使用端口編號策略。在該模型中，每個節點 v 都有 deg(v) 個端口，每條與 v 關聯的邊都與其中一個端口相連。只有一條邊可以連接到一個端口。在每一輪通信中，每個節點同時向每個端口發送一條消息。
通常，不同的消息被髮送到不同的端口。然後，每個節點同時接收消息。每個節點都知道相鄰節點提交消息的端口號和消息傳來的端口號。每個節點都會基於這些消息計算接下來的消息和狀態。在一定輪數的通信之後，每個節點都會基於狀態和接收到的信息輸出一個應答（例如，聲明成為一箇中心節點）。這種模型被稱為局部模型或矢量一致模型（VV_C（1）模型）。
在這裡，（1）代表該模型在一定輪數的通信後會停止運行。Hella 等人研究了一些比 VV_C（1）模型能力弱的模型。多重集廣播模型（MB（1））沒有使用端口編號策略，但是會將消息發送給所有的鄰居節點（即廣播）。集合廣播（SB（1））模型也沒有使用端口編號策略，SB（1）模型以集合形式接受消息，而且不能對重複的消息進行計數。Hella 等人說明，VV_C（1）一定能比 MB（1）處理更廣泛的問題，MB（1）一定能比 SB（1）處理更廣泛的問題。
2、GNN 與局部算法的聯繫
本節介紹 Sata 等人在論文「Approximation ratios of graph neural networks for combinatorial problems」中指出的 GNN 和分佈式局部算法之間的關係。首先，Sata 等人根據分佈式局部算法的計算模型對 GNN 模型進行了分類。
1）MB-GNN
MB-GNN 是標準的消息傳遞 GNN。它對應於 MB（1） 模型。
GraphSAGE-mean、GCN、GAT 都是 MB-GNN 的實例。儘管 GAT 的消息是通過注意力加權的，每個節點都會將當前的嵌入廣播給所有的鄰居節點，每個節點可以計算注意力權值和加權求和結果。因此，GAT 也是 MB-GNN。
2）SB-GNN
SB-GNN 是一類受限的 GNN，它們將嵌入聚合為一個集合。它對應於 SB（1） 模型。
GraphSAGE-pool 是 SB-GNN 的一種實例。
3）VV_C-GNN
VV_C-GNN 使用了一種端口編碼策略。VV_C-GNN 首先計算一個任意的端口編號 p，然後通過如下所示的方法計算節點的嵌入。
其中 p(v,u) 是 v 的端口編號，邊 {v,u} 與這些端口相連。VV_C-GNN 可以向不同的鄰居節點傳遞不同的消息，而 MB-GNN 總是向所有鄰居節點傳遞相同的消息。VV_C-GNN 和 MB-GNN 如圖 11 所示。Sato 等人指出，這些 GNN 模型與其相對應的局部算法的計算模型能力相當。
圖 11：（a）端口編碼的示意圖（b）MBGNN 向所有鄰居節點傳遞相同的消息。（c）VV_C-GNN 向鄰居節點傳遞不同的消息。
4）CPN-GNN
CPN-GNN 將鄰居節點的嵌入按照端口編碼順序串聯起來。
其中，△是輸入圖的最大度，
是與 v 的第 i 個端口相連的鄰居節點，
是科學系的參數。當度數小於 △ 時，CPNGNN 適當地進行補零填充，它是最強大的 VV_C-GNN。
在組合優化問題中，若搜索出的解更接近最優解（即近似比更小），則算法性能越好。為了探究 CPNGNN 在組合優化問題中的性能，可以計算通過 CPNGNN 算法搜索到的解的近似比。在論文「Approximation ratios of graph neural networks for combinatorial problems」中，Sato 等人考慮了以下三種問題：
1）最小頂點覆蓋問題
輸入：圖 G=（V，E）
輸出：節點集合
，其尺寸為滿足下列性質的最小值：對於任意邊
，u或 v 在 U 中。
2）最小支撐集問題
輸入：圖 G=（V，E）
輸出：節點集合
，其尺寸為滿足下列性質的最小值：對於任意的節點
，節點 v 或者至少一個 v 的鄰居節點在 V 中。
3）最大匹配問題
最小支撐集問題
輸入：圖 G=（V，E）
輸出：邊的集合
，其尺寸為滿足下列性質的最小值：對於任意的節點
，節點 v 或者至少一個 v 的鄰居節點在 V 中。
Sato 等人注意到，添加度特徵以外的特徵可以減小上述三個問題的近似比。
圖 12：一種簡單的 2-著色問題。每個綠色（0）節點與最少一個紅色節點相連，每個紅色（1）節點與至少一個綠色節點相連。
具體而言，他們考慮了一個簡單的 2-著色問題。一個 2-著色問題是為圖中的節點賦予 2 種顏色，使得圖中每一個幾點至少有一個顏色不同的鄰居。圖 12 是這種簡單的 2-著色問題的示意圖。2-著色問題可以在線性時間內通過廣度優先搜索（BFS）算法完成計算。Sato 等人指出，將這種簡單的 2 著色問題增加到節點特徵中可以使 GNN 獲取更多關於輸入圖的信息，並且得到更好的近似比。
3、隨機特徵增強 GNN
本章介紹的是，將隨機特徵添加到每個節點中，可以使 GNN 區分更多類別的圖，並且建模出更高效的算法。
Sata 等人提出了帶有隨機特徵的 GIN（rGIN）。rGIN 在每次程序被調用時賦予一個隨機特徵。具體而言，rGIN 獲取一個圖 G=（V，E，X）作為輸入，從一個離散分佈 μ 中為每個節點以獨立同分布的方式取樣得到隨機特徵
，並且使用帶有隨機特徵的圖
計算節點或圖的嵌入，其中
且
。
需要注意的是，儘管 rGIN 在訓練和測試時賦予不同的隨機特徵，但是 rGIN 也可以在測試時泛化到模型沒有見過的圖上。
圖 13：（a）當節點特徵向同時，消息傳遞 GNN 無法區分兩個三角形和六邊形。（b）當具有隨機節點特徵時，消息傳遞 GNN 可以區分兩個三角形和六邊形。
表 2：最小支撐集問題（MDS）和最大匹配問題（MM）的近似比的總結。*代表這些近似比達到了下界。△代表最大度，H(k) 代表第 k 個調和數，
是一個任意的常量，C是一個固定的常量。除常數項外，rGIN 的近似比與多項式算法的最佳近似比相匹配，除無關項外，rGIN 的近似比與多項式算法的最佳近似比相匹配。
五、XS 一致性
正如第三章和第四章所提到的，GNN 與 WL 算法和分佈式局部算法息息相關。本章將根據 GNN、WL算法、分佈式局部算法之間的關係總結 GNN 的表達能力。我們將它們的關係稱作「XS 一致性」（根據 Xu 等人和 Sato 等人的名字命名）。
Xu 等人和 Sato 等人的研究結果給出了 GNN、WL 算法以及分佈式局部算法的要素之間的一致性。表 3 總結了這種一致性。
表 3：XS 一致性給出了 GNN、WL 算法，以及分佈式局部算法的要素之間的具體聯繫。
例如，分佈式算法領域也研究了求解組合優化問題所需的通信輪數。Astrand 等人指出，
輪通信足以解決 2-近似問題，其中 △ 是最大度。Babai 等人指出，1-WL 算法在 2 輪迭代之內有很大概率可以確定出一個足夠大的隨機圖。根據 XS 一致性，這樣的結論可以被用來設計 GNN 的層數。
此外，WL 算法和分佈式局部算法在很多領域內都有聯繫。例如，k-WL 算法與帶有計數量詞的一階邏輯、組合數學中的跳卵石遊戲、線性規劃、Sherali-Adams 鬆弛都有聯繫（這些問題也可以通過組合優化方式求解）。分佈式局部算法與模態邏輯、常數時間算法都有關。具體而言：
對於任意的 k≥2，存在一個帶有計數量詞的 k 個變量的一階邏輯語句
，使得
且
當且僅當 k-WL 算法輸出 G 和 H 是「非同構」的。
在遊戲
中，玩家 2 在 G 和 H 上有一個獲勝策略，當且僅當 k-WL 算法輸出 G 和 H是「可能同構」的。
令 A 和 B 是 G 和 H 的鄰接矩陣。存在雙隨機實值矩陣 X 使得 AX=XB，當且僅當 1-WL 算法輸出 G 和 H 是「可能同構」的。
令 A 和 B 是 G 和 H 的鄰接矩陣。如果 （k+2）-WL 算法輸出 G 和 H 是「可能同構」的，則對於任意的 k≥2，存在 AX=XB 的秩-k Sherali-Adams 鬆弛的解，使得 X 是雙隨機的。
令 A 和 B 是 G 和 H 的鄰接矩陣。只有 （k+1）-WL 算法輸出 G 和 H 是「可能同構」的，則對於任意的 k≥2，才存在 AX=XB 的秩-k Sherali-Adams 鬆弛的解，使得 X 是雙隨機的。
在相應的Kripke模型上，VV_C（1） 模型可以識別梯度多模態邏輯的邏輯公式，而在VV_C（1）模型上，梯度多模態邏輯可以模擬任意算法。
一個分佈式局部算法可以被轉化為一個常量時間算法。
得益於 XS 一致性，我們可以使用該領域的結論推導出許多 GNN 的理論特性。例如，Barcelo 等人利用 WL 算法和一階邏輯之間的關係構建了更加強大的 GNN。
六、結語
本文中，我們介紹了圖神經網絡的表達能力。換而言之，我們介紹了消息傳遞 GNN 的能力最多與一維 WL 算法相當，以及如何將 GNN 推廣到 k 維 WL 算法上。
接著，我們介紹了 GNN 和分佈式算法之間的聯繫，指出了 GNN 在 GNN 可以計算的組合優化算法近似比方面的侷限性。 雷鋒網雷鋒網雷鋒網
不僅如此，我們還指出了將隨機特徵添加到每個節點中會顯著提升近似比。
最後，我們將 GNN、WL 算法，以及分佈式局部算法之間的關係總結為「XS 一致性」。
閱讀更多 雷鋒網 的文章
