雷鋒網(wǎng)AI科技評(píng)論按：近年來(lái)，圖神經(jīng)網(wǎng)絡(luò)（GNN）領(lǐng)域內(nèi)可謂百家爭(zhēng)鳴。然而，真正要想在圖神經(jīng)網(wǎng)絡(luò)的設(shè)計(jì)上有革命性的創(chuàng)新，不可避免地要對(duì)圖論的本質(zhì)問(wèn)題進(jìn)行深入探究。

本文是一篇來(lái)自京都大學(xué)的圖神經(jīng)網(wǎng)絡(luò)表達(dá)能力綜述，從GNN、WL 算法、組合優(yōu)化問(wèn)題之間的聯(lián)系入手，進(jìn)行了深入的歸納和分析。內(nèi)容涉及計(jì)算機(jī)網(wǎng)絡(luò)通信、網(wǎng)絡(luò)算法，組合數(shù)學(xué)、可計(jì)算性分析等方面，內(nèi)容非常豐富，其融會(huì)貫通的能力令人嘆為觀止！ 

原文鏈接：https://arxiv.org/pdf/2003.04078v1.pdf

一、引言

對(duì)于各種各樣的圖學(xué)習(xí)問(wèn)題來(lái)說(shuō)，圖神經(jīng)網(wǎng)絡(luò)（GNN）是非常有效的機(jī)器學(xué)習(xí)模型。這些問(wèn)題包括化學(xué)信息學(xué)、推薦系統(tǒng)、問(wèn)答系統(tǒng)、以及組合優(yōu)化問(wèn)題。Hamilton、Zhou、Wu 等人分別于 2017、2018、2019 年對(duì) GNN 做了全面的綜述。

盡管在許多領(lǐng)域中，GNN 在實(shí)驗(yàn)中都取得了成功，但是 Xu 等人和 Morris 等人卻指出，GNN 不能夠區(qū)分一些圖對(duì)。這說(shuō)明 GNN 不能使用任何參數(shù)正確地對(duì)這些圖進(jìn)行分類(lèi)，除非這些圖的標(biāo)簽是相同的。這樣的結(jié)果與多層感知機(jī)的通用近似能力形成了鮮明的對(duì)比。

此外，Sato 等人指出了 GNN 最多能像分布式局部算法（Distributed Local Algorithm）一樣強(qiáng)大。因此，除了圖同構(gòu)問(wèn)題，還有許多 GNN 無(wú)法解決的組合優(yōu)化問(wèn)題。所以，研究人員提出了各種各樣可證明的強(qiáng)大的 GNN 模型，從而克服 GNN 的局限性。

針對(duì) GNN 的表達(dá)能力和各種各樣為了克服這些局限性而設(shè)計(jì)的 GNN 模型，本文給出了一個(gè)全面的概述。與其它關(guān)于 GNN 的綜述（介紹 GNN 的架構(gòu)和應(yīng)用）不同，本文重點(diǎn)關(guān)注 GNN 的理論特性。

本文的組織結(jié)構(gòu)如下：在本章的其余部分中，我們將介紹本文使用的數(shù)學(xué)符號(hào)并簡(jiǎn)要回顧標(biāo)準(zhǔn)的 GNN 模型。在第 2 章中，我們看到 GNN 不能使用基本的參數(shù)和具體的示例來(lái)區(qū)分某些圖。在第 3 章中，我們介紹了 GNN 和 WL 算法之間的聯(lián)系。在第 4 章中，我們根據(jù) GNN 與分布式局部算法的聯(lián)系，介紹了 GNN 可以/不可以求解的組合優(yōu)化問(wèn)題。在第 5 章中，我們將 GNN、WL 算法，以及分布式局部算法之間的關(guān)系總結(jié)為「XS 一致性」（XS correspondence）。

1、數(shù)學(xué)符號(hào)

表一為本文中使用到的數(shù)學(xué)符號(hào)：

表 1：數(shù)學(xué)符號(hào)

{...} 表示一個(gè)集合，{{...}} 表示一個(gè)多重集。 在多重集之中，同一個(gè)元素可以出現(xiàn)多次。例如，{3,3,4} = {3,4}，但是{{3,3,4}} ≠ {3,4}。有時(shí)，我們將一個(gè)集合看做一個(gè)多重集，反之亦然。

對(duì)于每個(gè)正數(shù)              ，[n] 代表集合 {1,2,...,n}。諸如 a,b 和 c 這樣的小寫(xiě)字母代表一個(gè)標(biāo)量，一個(gè)加粗的小寫(xiě)字母（如 a,b 和 c）代表一個(gè)向量。諸如 A,B 和 C 這樣的加粗大寫(xiě)字母，代表一個(gè)矩陣或一個(gè)張量。A^T 代表 A 的轉(zhuǎn)置。對(duì)于向量               以及              ，               代表 a 和 b 的串聯(lián)。         表示點(diǎn)集 V 和邊集 E 組成的對(duì)。n 代表節(jié)點(diǎn)的數(shù)量，m 代表圖與上下文無(wú)關(guān)時(shí)邊的數(shù)量。

對(duì)于每個(gè)節(jié)點(diǎn) v 來(lái)說(shuō)，N(v) 代表 v 的鄰居節(jié)點(diǎn)的集合，deg(v) 代表 v 的鄰居節(jié)點(diǎn)的個(gè)數(shù)。如果一張圖包含節(jié)點(diǎn)特征向量              ，圖可以被表征為一個(gè)元組 G=(V,E,X)。        代表節(jié)點(diǎn) v 在第 l 層中的嵌入（詳見(jiàn)公式 2）；              代表第 l 層的聚合函數(shù)（詳見(jiàn)公式 1）；              代表第 l 層的更新函數(shù)（詳見(jiàn)公式 2）；              為讀出函數(shù)（詳見(jiàn)公式 3）；              為輸入圖中度的最大值；b(k) 代表第 k 個(gè)貝爾數(shù)；H(k) 為第 k 個(gè)調(diào)和數(shù)              。

2、 問(wèn)題設(shè)定

本文重點(diǎn)關(guān)注以下的節(jié)點(diǎn)分類(lèi)問(wèn)題和圖分類(lèi)問(wèn)題。

1）節(jié)點(diǎn)分類(lèi)問(wèn)題

輸入：一張圖 G=(V，E，X)，其中每個(gè)節(jié)點(diǎn) v∈V

輸出：v 的標(biāo)簽 y_v

2）圖分類(lèi)問(wèn)題

輸入：一張圖 G=(V，E，X)

輸出：圖 G 的標(biāo)簽 y_G

具體來(lái)說(shuō)，我們考慮的是 GNN 可以計(jì)算的函數(shù)              以及              的類(lèi)別。因?yàn)?GNN 不能對(duì)圖上所有的函數(shù)建模（詳見(jiàn)本文后續(xù)部分）。

3、圖神經(jīng)網(wǎng)絡(luò)

再簡(jiǎn)要介紹標(biāo)準(zhǔn)的 GNN 模型。

1）GNN 發(fā)展史

Sperduti 和 Starita 以及 Baskin 于 1997 年首次提出類(lèi)似于 GNN 的模型。他們使用神經(jīng)網(wǎng)絡(luò)從圖數(shù)據(jù)中抽取出特征，而不是使用手動(dòng)設(shè)計(jì)的圖特征。Sperduti 和 Starita 于 1997 年遞歸地應(yīng)用了一種線性聚合操作以及非線性激活函數(shù)，而 Baskin 等人則于 1997 年使用了參數(shù)共享機(jī)制對(duì)節(jié)點(diǎn)和邊特征的不變性變換進(jìn)行了建模。

這些特性在現(xiàn)代 GNN 中非常普遍。Gori 等人于 2005 年、Scarselli 等人于 2009 年分別提出了新型的圖學(xué)習(xí)模型，它們使用了遞歸的聚合技術(shù)并且將這些模型稱為圖神經(jīng)網(wǎng)絡(luò)。

值得注意的是，在本文中，GNN 不僅僅代表這類(lèi)模型，GNN 是代表這類(lèi)模型的后續(xù)變體的通用術(shù)語(yǔ)。

Li 等人于 2016 年將 Gori 等人（2015）和 Scarselli 等人（2009）的思想擴(kuò)展到了門(mén)控圖神經(jīng)網(wǎng)絡(luò)上。分子圖網(wǎng)絡(luò)（Merkwirth 和 Lengauer，2005）是一種具有相似架構(gòu)的圖神經(jīng)網(wǎng)絡(luò)的并行模型，其層數(shù)為一個(gè)常數(shù)。

Duvenaud 等人于 2015 年構(gòu)建了一種受圓形指紋啟發(fā)的 GNN 模型。受核消息傳遞算法（Song 等人于 2010、2011 年提出）的啟發(fā)，Dai 等人于 2016 年提出了一種新的 GNN 模型。Gilmer 等人于 2017 年使用消息傳遞機(jī)制提供了一種對(duì) GNN 的統(tǒng)一視角，從而表征 GNN。

在本文中，我們并不考慮  GNN 模型的頻域變體（例如 Bruna 等人于 2014年發(fā)表的論文「 Spectral networks and locally connected networks on graphs」，以及 Defferrard 等人于 2016 年發(fā)表的論文「 Convolutional neural networks on graphs with fast localized spectral fifiltering」），僅僅考慮基于消息傳遞機(jī)制的空域方法。

             

圖 1：?jiǎn)螌酉鬟f圖神經(jīng)網(wǎng)絡(luò)。

             

圖 2：雙層消息傳遞圖神經(jīng)網(wǎng)絡(luò)。

2）消息傳遞機(jī)制

根據(jù)消息傳遞機(jī)制，L 層的 GNN 可以被形式化定義如下：

             

 

其中，              和              都是參數(shù)化函數(shù)。在這里，              可以被看做節(jié)點(diǎn) u 在第 k 個(gè)消息傳遞階段中的「消息」。每個(gè)節(jié)點(diǎn)將聚合它們鄰居節(jié)點(diǎn)的消息，從而計(jì)算出下一個(gè)消息或嵌入。GNN 基于最終的嵌入              對(duì)節(jié)點(diǎn) v 進(jìn)行分類(lèi)。

當(dāng)沒(méi)有可用的節(jié)點(diǎn)特征              時(shí)，根據(jù) Xu 等人于 2019 年發(fā)表的論文「How powerful are graph neural networks?」以及 Knyazev 等人于 2019 年發(fā)表的論文「Understanding attention and generalization in graph neural networks」，我們使用獨(dú)熱的度向量作為初始的嵌入。

圖 1 和圖 2 對(duì)這種方案進(jìn)行了說(shuō)明，其中顏色代表特征和嵌入。相同的顏色代表相同的向量。

在本例中，圖 1 中的單層 GNN 無(wú)法區(qū)分出左下角用嵌入 3 表示的節(jié)點(diǎn)。這說(shuō)明這些節(jié)點(diǎn)擁有不同的類(lèi)標(biāo)簽，單層 GNN 往往不能正確對(duì)這些節(jié)點(diǎn)進(jìn)行分類(lèi)，這是因?yàn)?GNN 僅僅基于最終的嵌入對(duì)接點(diǎn)進(jìn)行分類(lèi)。相反，如圖 2 所示，雙層 GNN 就可以將所有節(jié)點(diǎn)區(qū)分開(kāi)來(lái)。

除了結(jié)構(gòu)上的限制，一般而言，              和并不一定要是單射函數(shù)。例如，              可能是成立的。這就對(duì) GNN 施加了更多的限制。本文旨在確定 GNN 可以/無(wú)法識(shí)別的圖的特性。

在圖分類(lèi)問(wèn)題中，GNN 使用讀出函數(shù)計(jì)算圖嵌入              ：

             

其中，              是一個(gè)參數(shù)化的函數(shù)。GNN 基于圖嵌入              對(duì)圖 G 進(jìn)行分類(lèi)。典型的 GNN 模型可以通過(guò)如下所示的消息傳遞框架形式化定義。

GraphSAGE-mean（詳見(jiàn) Hamilton 等人于 2017 年發(fā)表的論文「Inductive representation learning on large graphs」）

             

其中              是一個(gè)參數(shù)矩陣，而σ是一個(gè)激活函數(shù)（如 sigmoid 和 ReLU）。

圖卷積網(wǎng)絡(luò)（GCN，詳見(jiàn) Kipf 和 Welling 等人于 2017 年發(fā)表的論文「Deep models of interactions across sets」）

              

圖注意力網(wǎng)絡(luò)（GAT，詳見(jiàn) Velickovic 等人于 2018 年發(fā)表的論文「Weak models of distributed computing, with connections to modal logic」）

              

嚴(yán)格來(lái)說(shuō)，在這些模型中，              并不僅僅是關(guān)于              的函數(shù)，它還用到了鄰居節(jié)點(diǎn)的度以及注意力權(quán)重這些邊信息。然而，這些信息可以被認(rèn)為被包含在了消息              中。因此，這里使用的數(shù)學(xué)符號(hào)并不會(huì)影響這些模型可以計(jì)算的函數(shù)的類(lèi)別。

Gilmer 等人于 2017 年發(fā)表的論文「Neural message passing for quantum chemistry」介紹了許多其它的消息傳遞 GNN 的示例。

二、 GNN 無(wú)法區(qū)分的圖

             

圖 3：GNN 不能區(qū)分上面兩種分子，因?yàn)樗鼈兌际前?20 個(gè)節(jié)點(diǎn)的 3-正則圖。

本章討論樸素的 GNN 無(wú)法通過(guò)基本參數(shù)和具體示例區(qū)分的圖。

K-正則圖是一種每個(gè)節(jié)點(diǎn)都恰好有 k 個(gè)鄰居節(jié)點(diǎn)的圖。如圖 3 所示，「Decaprismane C_20H_20」和「Dodecahedrane C_20H_20」都是 3-正則圖。顯然，消息傳遞 GNN 無(wú)法區(qū)分具有相同尺寸和節(jié)點(diǎn)特征的 k-正則圖。

我們?cè)趫D 4 中說(shuō)明了這種現(xiàn)象。由于右邊的圖包含三角形，而左邊的圖并不包含三角，所以這兩個(gè)圖并不是同構(gòu)的。然而，左圖和右圖中所有節(jié)點(diǎn)中的所有的消息是相同的。因此，最終通過(guò) GNN 計(jì)算得到的所有嵌入都是相同的。這種結(jié)果并不盡如人意，因?yàn)槿绻麅蓚€(gè)正則圖（例如，「Decaprismane C_20H_20」和「Dodecahedrane C_20H_20」）有不同的類(lèi)標(biāo)簽，無(wú)論模型參數(shù)如何，消息傳遞 GNN 往往無(wú)法區(qū)分它們。

除了正則圖意外，還有許多非正則、非同構(gòu)的圖是 GNN 無(wú)法區(qū)分的。圖 5 列舉出了一些 GNN 無(wú)法區(qū)分的非正則、非同構(gòu)的圖的示例。圖 5(a) 和 (b) 是通過(guò)為圖 4 中正則圖中的節(jié)點(diǎn)附上一個(gè)「葉子」結(jié)點(diǎn)生成的（就像附上一個(gè)氫原子一樣）。圖 5(e) 和 (f) 包含除度特征之外的節(jié)點(diǎn)特征，但是 GNN 不能區(qū)分它們。

圖 6 中的十氫化萘 C_10H_18 和雙環(huán)戊烷 C_10H_18 是 GNN 無(wú)法區(qū)分的現(xiàn)實(shí)世界中的圖，同理圖 5(c) 和 (d) 也是 GNN 無(wú)法區(qū)分的。同樣的，這也說(shuō)明如果兩個(gè)分子有不同的類(lèi)標(biāo)簽，無(wú)論模型參數(shù)如何，GNN 往往無(wú)法區(qū)分他們。似乎 GNN 無(wú)法區(qū)分的圖是無(wú)窮無(wú)盡的。

那么，我們能歸納出這類(lèi) GNN 無(wú)法區(qū)分的圖的特點(diǎn)嗎？下一章將介紹 Xu 等人和 Morris 的研究成果，它們通過(guò)「Weisfeiler-Lehman」算法描述了這類(lèi)圖。

             

圖 4：消息傳遞 GNN 并不能將任何一對(duì)具有相同的度和尺寸的正則圖區(qū)分開(kāi)來(lái)（即使他們并不是同構(gòu)的）。

             

圖 5：盡管這些圖并不是同構(gòu)的，但是 GNN 也無(wú)法將 a 和 b、c 和 d、e 和 f 區(qū)分開(kāi)來(lái)。

             

圖 6：GNN 無(wú)法將這兩種分子區(qū)分開(kāi)來(lái)，即使這些圖不是同構(gòu)或正則的。 

三、GNN 與「Weisfeiler-Lehman」算法的聯(lián)系

在本章中，我們將介紹 GNN 與 Weisfeiler-Lehman 算法之間的聯(lián)系

1、Weisfeiler-Lehman 算法

圖同構(gòu)問(wèn)題，是一種確定一對(duì)圖是否同構(gòu)的決策問(wèn)題。

輸入：一對(duì)圖 G=（V，E，X）和 H=（U，F(xiàn)，Y）

輸出：確定是否存在一種雙射              使得                            且              當(dāng)且僅當(dāng)               

若兩圖同構(gòu)，則我們認(rèn)為這兩個(gè)圖相等，GNN 應(yīng)該輸出相同的嵌入。

Weisfeiler-Lehman（WL）算法是一種被用來(lái)解決圖同構(gòu)問(wèn)題的算法。WL 算法有許多種變體：

1）1-維 WL（1-WL）算法（也稱「color refinement」）：是最常用的變體，我們有時(shí)直接將其稱為 WL 算法。該算法為每個(gè)節(jié)點(diǎn)賦予一種標(biāo)簽（顏色），并不斷聚合鄰居節(jié)點(diǎn)信息、修改節(jié)點(diǎn)的標(biāo)簽（顏色），直到標(biāo)簽不再變化（收斂）。

輸入：一對(duì)圖 G=（V，E，X）和 H=（U，G，Y）

       

其中 HASH 是一種單射哈希函數(shù)。如果 1-WL 算法輸出「非同構(gòu)」，那么 G 和 H 就不是同構(gòu)的圖，但即使 1-WL 算法輸出「可能同構(gòu)」，G 和 H 仍有可能非同構(gòu)。例如，對(duì)于圖 4 中的圖，1-WL 算法將輸出「可能同構(gòu)」，然而它們并非同構(gòu)。1-WL 算法可以保證在時(shí)間復(fù)雜度為              的迭代過(guò)程之內(nèi)完成。

2）K-維 WL 算法： 1-維 WL 的推廣。k-維 WL 為每 k 個(gè)節(jié)點(diǎn)組成的元組賦予一種顏色。

輸入：一對(duì)圖 G=（V，E，X）和 H=（U，F(xiàn)，Y）

          

              

其中，              是第 i 個(gè)鄰居節(jié)點(diǎn)，它使用 G 中的每個(gè)節(jié)點(diǎn)替換 k 元組中的第 i 個(gè)元素?！窰ASH」是一種單射的哈希函數(shù)，它為相同的同構(gòu)型賦予相同的顏色。換而言之，              當(dāng)且僅當(dāng)              ；              當(dāng)且僅當(dāng)              ∈              。這種限制對(duì)于              和              ，以及              和              同樣成立。

3）K-維 folklore WL（k-FWL）算法：是 1 維 WL 算法的另一種推廣。

             

其中              。K-WL 和 K-FWL 仍然存在不足。如果 K-WL 和 K-FWL 輸出「非同構(gòu)」，那么 G 和 H 則不是同構(gòu)圖，但即使 K-WL 和 K-FWL 輸出「可能同構(gòu)」，G 和 H 仍然可能不是同構(gòu)圖。

WL 算法的變體的能力具有如下關(guān)系：

• 1-WL 與 2-WL 能力相當(dāng)。換句話說(shuō)，對(duì)于任意一對(duì)圖，這兩種算法的輸出相同。

• 對(duì)于任意的 k≥2，k-FWL 的能力與 (k+1)-WL 相當(dāng)。

• 對(duì)于任意的 k≥2，(k+1)-WL 一定比 k-WL 能力更強(qiáng)。換句話說(shuō)，存在一對(duì)非同構(gòu)圖（G，H），使得 k-WL 輸出「可能同構(gòu)」，但 (k+1)-WL 輸出「非同構(gòu)」。

 

             

圖 7：WL 算法相關(guān)變體的層次

研究者們已經(jīng)大量研究了 WL 算法可以/無(wú)法區(qū)分的圖所具備的性質(zhì)。值得注意的是：

• 如果兩圖都是隨機(jī)抽取的，那么隨著圖的尺寸趨向與無(wú)限大，1-WL 算法失效的概率趨近于 1。

• 當(dāng) k≥2 時(shí)，存在一對(duì)尺寸為 O(k) 的非同構(gòu)圖（G，H），使得 k-WL 的輸出為「可能同構(gòu)」。

• 對(duì)任意一對(duì)非同構(gòu)樹(shù) S 和 T，1-WL 算法輸出 S 和 T 都是「非同構(gòu)的」。

• 對(duì)于任意的正整數(shù)    以及一對(duì)有 n 個(gè)頂點(diǎn)的 k 正則圖 G 和 H，1-WL 算法輸出的 G 和 H 是「可能同構(gòu)」 。

• 在準(zhǔn)線性時(shí)間內(nèi)，1-WL 算法可以將圖與和它非同構(gòu)圖的區(qū)分開(kāi)來(lái)。

2、GNN 和 WL 算法之間的聯(lián)系

本節(jié)介紹 GNN 與 WL 算法之間的聯(lián)系。

定理 1：對(duì)于任意的消息傳遞 GNN 和任意的圖 G 和 H，如果 1-WL 算法輸出 G 和 H 是「可能同構(gòu)」的，那么由 GNN 計(jì)算出的嵌入 h_G 和 h_H 是相同的。

換而言之，消息傳遞 GNN 并沒(méi)有 1-WL 那樣強(qiáng)大。這是因?yàn)榫酆虾瘮?shù)和更新函數(shù)可以被看做 1-WL 算法的哈希函數(shù)，而聚合函數(shù)和更新函數(shù)并不一定是單射的。在這種 GNN 和 1-WL 的對(duì)應(yīng)關(guān)系的啟發(fā)下，Xu 等人于 2019 年發(fā)表的論文「How powerful are graph neural networks? 」通過(guò)使聚合函數(shù)和更新函數(shù)限制為單射函數(shù)，提出了一種與 1-WL 一樣強(qiáng)大的 GNN——圖同構(gòu)網(wǎng)絡(luò)（GIN）：

             

其中，   是一個(gè)標(biāo)量參數(shù)，MLP 是一個(gè)多層感知機(jī)。根據(jù)深度多重集理論（GIN 的聚合函數(shù)在某些假設(shè)下是單射函數(shù)），GIN 與 1-WL 一樣強(qiáng)大。

定理 2：對(duì)于所有的   ，存在 L 層 GIN 的參數(shù)使得：若節(jié)點(diǎn)的度以一個(gè)常數(shù)為上界，且節(jié)點(diǎn)特征的支撐集的大小有限，那么對(duì)于任意的 G 和 H，如果 1-WL 算法在 L 次迭代內(nèi)輸出 G 和 H 是「非同構(gòu)」的，則由 GIN 計(jì)算出的嵌入 h_G 和 h_H 是不同的。

推論 3：對(duì)于任意的圖 G 和 H，如果 1-WL 算法輸出 G 和 H 是「非同構(gòu)」的，那么存在 GIN 的參數(shù)使得由 GIN 計(jì)算出的嵌入 h_G 和 h_H 是不同的。

由于 1-WL 算法定義了消息傳遞 GNN 表達(dá)能力的上界，GIN 也有時(shí)被稱為最強(qiáng)大的消息傳遞 GNN。那么，我們?nèi)绾尾拍軜?gòu)建比 1-WL 算法更加強(qiáng)大的 GNN 呢？

Morris 等人于 2019 年基于 k-WL 算法的一種變體提出了一種更為強(qiáng)大的模型。他們用「集合 k-WL」算法替代了「k-WL」算法，從而減小內(nèi)存開(kāi)銷(xiāo)。

1）「集合 k-WL」算法

令                  為 V 的包含 k 個(gè)節(jié)點(diǎn)的子集。                 ?！讣?k-WL」算法為每個(gè)由 k 個(gè)節(jié)點(diǎn)組成的集合賦予一種顏色。

              

其中，  是一種單射哈希函數(shù)，它為由 S 劃分的子圖賦予一種顏色。集合 3-WL 算法可以區(qū)分三角形（1-WL 無(wú)法做到這一點(diǎn)）。因此，集合 3-WL 算法可以區(qū)分圖 5 中的 a 和 b、c 和 d、e 和 f，而 1-WL 算法則無(wú)法區(qū)分。由于三角形的個(gè)數(shù)（即聚類(lèi)系數(shù)）在各種網(wǎng)絡(luò)中有著很重要的作用，所以集合 3-WL 的這種特性是迫切需要的。

然而，集合 3-WL 算法無(wú)法區(qū)分圖 8 中的 a 和 b，因?yàn)?3-WL 算法無(wú)法將其區(qū)分。需要注意的是，集合 k-WL 算法一定弱于 k-WL 算法。例如，3-WL 可以區(qū)分圖 9 中的 a 和 b（因?yàn)?3-WL 可以檢測(cè)出 4 聯(lián)通分量的數(shù)目），而集合 3-WL 算法無(wú)法做到這一點(diǎn)。

Morris 等人于 2019 年基于集合 k-WL 算法提出了 k-維 GNN（k-GNN）。k-GNN 為每 k 個(gè)節(jié)點(diǎn)組成的集合賦予一種嵌入。

 

2）k-維 GNN（k-GNN）

             

其中，  根據(jù) S 劃分的子圖賦予一個(gè)特征向量。k-GNN 可以被看做在拓展圖              上進(jìn)行操作的消息傳遞 GNN，此時(shí)節(jié)點(diǎn)的集合為  ，存在  和   之間的一條邊，當(dāng)且僅當(dāng) 。k-GNN 與集合 k-WL 算法能力相當(dāng)。

             

圖 8：盡管這些圖是非同構(gòu)的，3-維 WL 算法和 3-GNN 也不能區(qū)分 a 和 b。

             

圖 9: 3-維 WL 算法可以區(qū)分這些圖，但是集合 3-維 WL 算法無(wú)法做到這一點(diǎn)。

定理 4：Morris 等人于 2019 年提出，對(duì)于任意的圖 G 和 H，當(dāng) k≥2 時(shí)，如果集合 k-WL 算法輸出 G 和 H 是「非同構(gòu)」的，那么存在 k-GNN 的參數(shù)使得由 k-GNN 計(jì)算得到的嵌入 h_G 和 h_H 不同。

k-GNN 需要維護(hù) 個(gè)嵌入，因此其內(nèi)存開(kāi)銷(xiāo)相當(dāng)大。在 Maron 等人 2019 年發(fā)表的論文「Provably powerful graph networks」中，他們基于 2-FWL 算法提出了一種與 3-WL 能力相當(dāng)，但只用維護(hù)          個(gè)嵌入的 GNN 模型，從而緩解了內(nèi)存開(kāi)銷(xiāo)的問(wèn)題。為了介紹該模型，讀者需要了解高階不變和等變 GNN。

3、高階圖神經(jīng)網(wǎng)絡(luò)

本章介紹高階不變和等變 GNN。首先形式化定義不變性和等變性。令    為集合 [n] 上的對(duì)稱群。

對(duì)于一個(gè)張量  以及一種排列 ，我們定義  為               。

對(duì)于一個(gè)張量以及一種排列 ，我們定義  為        。

定義 5（不變性）：若對(duì)于任意    和   ，   成立，則會(huì)函數(shù)         是不變的。若對(duì)于任意  和    ，    成立，則函數(shù)   是不變的。

定義 6（等變性）：若對(duì)于任意  和   ，    成立，則函數(shù)      是等變的。若對(duì)于任意              和          ，          成立，則       是等變的。

不變性是 l=0 時(shí)的等變性的特例。我們可以很自然地想到，圖學(xué)習(xí)模型應(yīng)該具備不變性和等變性，因?yàn)閳D不會(huì)由于任何節(jié)點(diǎn)擾動(dòng)而改變。

Maron 等人推廣了 Zaheer、Kondor、Hartford 等人的思想，列舉出了所有不變和等變的線性變換。他們發(fā)現(xiàn)，不變和等變線性變換的基的大小與維度 n 無(wú)關(guān)。具體而言，線性不變變換              的基的大小為 b(k)，              的基的大小為 b(k+l)，其中 b(k) 是第 k 個(gè)貝爾數(shù)（即集合 [k] 的劃分的數(shù)量）。

定理 7：   構(gòu)成了線性不變性變換   的一組正交基。

定理 8：    構(gòu)成了線性等變性變換 的一組正交基。

因此，任意的線性不變和等變變換可以分別通過(guò)大小為 b(k) 和 b(k+l) 的基向量的線性組合進(jìn)行建模。Maron 等人于 2019 年提出使用這種變換作為非消息傳遞 GNN 的構(gòu)建模塊。Maron 等人通過(guò)揭示高階 GNN 和 高階 WL 算法之間的關(guān)系，并提出了一種新的基于高階 FWL 算法的高階 GNN 模型，緩解了參數(shù)過(guò)多、內(nèi)存開(kāi)銷(xiāo)過(guò)大的問(wèn)題。首先，Maron 等人說(shuō)明使用 k 階張量的高階 GNN 與 k-WL 的能力相當(dāng)。

定理 9：對(duì)于任意的圖 G 和 H，如果 k-WL 算法輸出「非同構(gòu)」，則存在最多帶有 k 階（）張量的高階 GNN ，使得由高階 GNN 計(jì)算得到的嵌入 h_G 和 h_H 是不同的。

這說(shuō)明在一般情況下， n 階張量是充分且必要的。必要性： 存在一對(duì)大小為 O(k) 的非同構(gòu)圖，使得 k-WL 算法無(wú)法區(qū)分。充分性：n-WL 可以區(qū)分所大小為 n 的圖。

接著，Maron 等人提出了一個(gè)與 2-FWL 算法能力相當(dāng)?shù)?GNN 模型。

定理 10：對(duì)于任意的圖 G、H，如果 2-FWL 算法輸出「非同構(gòu)」，存在二階 folklore GNN 的參數(shù)，使得由二階 folklore GNN 計(jì)算得到的嵌入 h_G 和 h_H 是不同的。

4、關(guān)系池化

本節(jié)將介紹另一種 Murphy 等人于 2019 年在論文「Relational pooling for graph representations」中提出的構(gòu)建強(qiáng)大的 GNN 的方法。這種思路非常直接，關(guān)系池化層取所有可能的排列的平均（如 Jannosy 池化）。

也就是說(shuō)，令 f 為一種消息傳遞 GNN，A 為 G=（V，E，X）的鄰接矩陣，     為單位矩陣，      為 V 上的對(duì)稱群。由此，關(guān)系池化 GNN（RP-GNN）可以被定義為：

             

換句話說(shuō)，RP-GNN 串聯(lián)了節(jié)點(diǎn)索引的獨(dú)熱編碼和節(jié)點(diǎn)特征，然后對(duì)所有可能的排列取平均。RP-GNN 的強(qiáng)大之處在于，它在構(gòu)造上具有明顯的排列不變性，比 GIN 和 1-WL 算法更加強(qiáng)大。

定理 11：RP-GNN 比原始的消息傳遞 GNN  f 更加強(qiáng)大。尤其是當(dāng) f 是通過(guò) GIN 建模時(shí)，以及圖帶有離散屬性時(shí)，RP-GNN 比 1-WL 算法要更加強(qiáng)大。

四、GNN 與組合優(yōu)化問(wèn)題的聯(lián)系

至此，我們已經(jīng)探討了圖同構(gòu)問(wèn)題。本章將討論其它的組合優(yōu)化問(wèn)題，例如：最小頂點(diǎn)覆蓋問(wèn)題、最小支配集問(wèn)題、最大匹配問(wèn)題，并通過(guò)計(jì)算 GNN 的算法效率評(píng)估 GNN 的表達(dá)能力。具體而言將介紹 GNN 和分布式局部算法（Distributed Local Algorithms）之間的關(guān)系。

值得注意的是，在本章中，對(duì)于建模組合優(yōu)化算法而言，GNN 并不一定需要具備不變性或等變性。

1、分布式局部算法

分布式局部算法是在恒定時(shí)間內(nèi)運(yùn)行的分布式算法。具體而言，一個(gè)分布式局部算法解決了計(jì)算機(jī)網(wǎng)絡(luò)領(lǐng)域中本身存在的一個(gè)問(wèn)題：每臺(tái)計(jì)算機(jī)運(yùn)行相同的程序，每臺(tái)計(jì)算機(jī)與相鄰計(jì)算機(jī)進(jìn)行一定數(shù)量的同步通信后，再?zèng)Q定輸出。

例如，假設(shè)移動(dòng)設(shè)備與附近的設(shè)備組成了一個(gè)通信網(wǎng)絡(luò)。通信網(wǎng)絡(luò)必須包含中心節(jié)點(diǎn)來(lái)控制通信，這個(gè)中心節(jié)點(diǎn)必須形成網(wǎng)絡(luò)的一個(gè)頂點(diǎn)覆蓋（即每條邊至少被一個(gè)中心節(jié)點(diǎn)覆蓋）。中心節(jié)點(diǎn)的數(shù)目需要盡可能的小，但是每個(gè)移動(dòng)設(shè)備必須要在 5 輪通信之內(nèi)被聲明為中心節(jié)點(diǎn)。

那如何才能設(shè)計(jì)滿足要求的算法呢？該問(wèn)題的示意圖如圖 10 所示。

             

圖 10：分布式局部算法示意圖。左：與鄰居計(jì)算機(jī)的通信。右：在一定次數(shù)的通信后，每個(gè)節(jié)點(diǎn)的應(yīng)答。

目前，已經(jīng)有多種分布式算法的計(jì)算模型。在分布式局部算法的計(jì)算模型中，標(biāo)準(zhǔn)計(jì)算模型使用端口編號(hào)策略。在該模型中，每個(gè)節(jié)點(diǎn) v 都有 deg(v) 個(gè)端口，每條與 v 關(guān)聯(lián)的邊都與其中一個(gè)端口相連。只有一條邊可以連接到一個(gè)端口。在每一輪通信中，每個(gè)節(jié)點(diǎn)同時(shí)向每個(gè)端口發(fā)送一條消息。

通常，不同的消息被發(fā)送到不同的端口。然后，每個(gè)節(jié)點(diǎn)同時(shí)接收消息。每個(gè)節(jié)點(diǎn)都知道相鄰節(jié)點(diǎn)提交消息的端口號(hào)和消息傳來(lái)的端口號(hào)。每個(gè)節(jié)點(diǎn)都會(huì)基于這些消息計(jì)算接下來(lái)的消息和狀態(tài)。在一定輪數(shù)的通信之后，每個(gè)節(jié)點(diǎn)都會(huì)基于狀態(tài)和接收到的信息輸出一個(gè)應(yīng)答（例如，聲明成為一個(gè)中心節(jié)點(diǎn)）。這種模型被稱為局部模型或矢量一致模型（VV_C（1）模型）。

在這里，（1）代表該模型在一定輪數(shù)的通信后會(huì)停止運(yùn)行。Hella 等人研究了一些比 VV_C（1）模型能力弱的模型。多重集廣播模型（MB（1））沒(méi)有使用端口編號(hào)策略，但是會(huì)將消息發(fā)送給所有的鄰居節(jié)點(diǎn)（即廣播）。集合廣播（SB（1））模型也沒(méi)有使用端口編號(hào)策略，SB（1）模型以集合形式接受消息，而且不能對(duì)重復(fù)的消息進(jìn)行計(jì)數(shù)。Hella 等人說(shuō)明，VV_C（1）一定能比 MB（1）處理更廣泛的問(wèn)題，MB（1）一定能比 SB（1）處理更廣泛的問(wèn)題。

2、GNN 與局部算法的聯(lián)系

本節(jié)介紹 Sata 等人在論文「Approximation ratios of graph neural networks for combinatorial problems」中指出的 GNN 和分布式局部算法之間的關(guān)系。首先，Sata 等人根據(jù)分布式局部算法的計(jì)算模型對(duì) GNN 模型進(jìn)行了分類(lèi)。

1）MB-GNN

MB-GNN 是標(biāo)準(zhǔn)的消息傳遞 GNN。它對(duì)應(yīng)于 MB（1） 模型。

 

             

GraphSAGE-mean、GCN、GAT 都是 MB-GNN 的實(shí)例。盡管 GAT 的消息是通過(guò)注意力加權(quán)的，每個(gè)節(jié)點(diǎn)都會(huì)將當(dāng)前的嵌入廣播給所有的鄰居節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)可以計(jì)算注意力權(quán)值和加權(quán)求和結(jié)果。因此，GAT 也是 MB-GNN。

2）SB-GNN

SB-GNN 是一類(lèi)受限的 GNN，它們將嵌入聚合為一個(gè)集合。它對(duì)應(yīng)于 SB（1） 模型。

             

GraphSAGE-pool 是 SB-GNN 的一種實(shí)例。

3）VV_C-GNN

VV_C-GNN 使用了一種端口編碼策略。VV_C-GNN 首先計(jì)算一個(gè)任意的端口編號(hào) p，然后通過(guò)如下所示的方法計(jì)算節(jié)點(diǎn)的嵌入。              

其中 p(v,u) 是 v 的端口編號(hào)，邊 {v,u} 與這些端口相連。VV_C-GNN 可以向不同的鄰居節(jié)點(diǎn)傳遞不同的消息，而 MB-GNN 總是向所有鄰居節(jié)點(diǎn)傳遞相同的消息。VV_C-GNN 和 MB-GNN 如圖 11 所示。Sato 等人指出，這些 GNN 模型與其相對(duì)應(yīng)的局部算法的計(jì)算模型能力相當(dāng)。

             

圖 11：（a）端口編碼的示意圖（b）MBGNN 向所有鄰居節(jié)點(diǎn)傳遞相同的消息。（c）VV_C-GNN 向鄰居節(jié)點(diǎn)傳遞不同的消息。

4）CPN-GNN

CPN-GNN 將鄰居節(jié)點(diǎn)的嵌入按照端口編碼順序串聯(lián)起來(lái)。

其中，△是輸入圖的最大度，              是與 v 的第 i 個(gè)端口相連的鄰居節(jié)點(diǎn)，              是科學(xué)系的參數(shù)。當(dāng)度數(shù)小于 △ 時(shí)，CPNGNN 適當(dāng)?shù)剡M(jìn)行補(bǔ)零填充，它是最強(qiáng)大的 VV_C-GNN。

在組合優(yōu)化問(wèn)題中，若搜索出的解更接近最優(yōu)解（即近似比更?。瑒t算法性能越好。為了探究 CPNGNN 在組合優(yōu)化問(wèn)題中的性能，可以計(jì)算通過(guò) CPNGNN 算法搜索到的解的近似比。在論文「Approximation ratios of graph neural networks for combinatorial problems」中，Sato 等人考慮了以下三種問(wèn)題：

1）最小頂點(diǎn)覆蓋問(wèn)題

輸入：圖 G=（V，E）

輸出：節(jié)點(diǎn)集合 ，其尺寸為滿足下列性質(zhì)的最小值：對(duì)于任意邊 ，u或 v 在 U 中。

2）最小支撐集問(wèn)題

輸入：圖 G=（V，E）

輸出：節(jié)點(diǎn)集合  ，其尺寸為滿足下列性質(zhì)的最小值：對(duì)于任意的節(jié)點(diǎn)  ，節(jié)點(diǎn) v 或者至少一個(gè) v  的鄰居節(jié)點(diǎn)在 V 中。

3）最大匹配問(wèn)題

最小支撐集問(wèn)題

輸入：圖 G=（V，E）

輸出：邊的集合   ，其尺寸為滿足下列性質(zhì)的最小值：對(duì)于任意的節(jié)點(diǎn)   ，節(jié)點(diǎn) v 或者至少一個(gè) v  的鄰居節(jié)點(diǎn)在 V 中。

Sato 等人注意到，添加度特征以外的特征可以減小上述三個(gè)問(wèn)題的近似比。

             

圖 12：一種簡(jiǎn)單的 2-著色問(wèn)題。每個(gè)綠色（0）節(jié)點(diǎn)與最少一個(gè)紅色節(jié)點(diǎn)相連，每個(gè)紅色（1）節(jié)點(diǎn)與至少一個(gè)綠色節(jié)點(diǎn)相連。

具體而言，他們考慮了一個(gè)簡(jiǎn)單的 2-著色問(wèn)題。一個(gè) 2-著色問(wèn)題是為圖中的節(jié)點(diǎn)賦予 2 種顏色，使得圖中每一個(gè)幾點(diǎn)至少有一個(gè)顏色不同的鄰居。圖 12 是這種簡(jiǎn)單的 2-著色問(wèn)題的示意圖。2-著色問(wèn)題可以在線性時(shí)間內(nèi)通過(guò)廣度優(yōu)先搜索（BFS）算法完成計(jì)算。Sato 等人指出，將這種簡(jiǎn)單的 2 著色問(wèn)題增加到節(jié)點(diǎn)特征中可以使 GNN 獲取更多關(guān)于輸入圖的信息，并且得到更好的近似比。

3、隨機(jī)特征增強(qiáng) GNN

本章介紹的是，將隨機(jī)特征添加到每個(gè)節(jié)點(diǎn)中，可以使 GNN 區(qū)分更多類(lèi)別的圖，并且建模出更高效的算法。

Sata 等人提出了帶有隨機(jī)特征的 GIN（rGIN）。rGIN 在每次程序被調(diào)用時(shí)賦予一個(gè)隨機(jī)特征。具體而言，rGIN 獲取一個(gè)圖 G=（V，E，X）作為輸入，從一個(gè)離散分布 μ 中為每個(gè)節(jié)點(diǎn)以獨(dú)立同分布的方式取樣得到隨機(jī)特征 ，并且使用帶有隨機(jī)特征的圖   計(jì)算節(jié)點(diǎn)或圖的嵌入，其中   且    。

需要注意的是，盡管 rGIN 在訓(xùn)練和測(cè)試時(shí)賦予不同的隨機(jī)特征，但是 rGIN 也可以在測(cè)試時(shí)泛化到模型沒(méi)有見(jiàn)過(guò)的圖上。

             

圖 13：（a）當(dāng)節(jié)點(diǎn)特征向同時(shí)，消息傳遞  GNN 無(wú)法區(qū)分兩個(gè)三角形和六邊形。（b）當(dāng)具有隨機(jī)節(jié)點(diǎn)特征時(shí)，消息傳遞 GNN 可以區(qū)分兩個(gè)三角形和六邊形。

表 2：最小支撐集問(wèn)題（MDS）和最大匹配問(wèn)題（MM）的近似比的總結(jié)。*代表這些近似比達(dá)到了下界。△代表最大度，H(k) 代表第 k 個(gè)調(diào)和數(shù)，     是一個(gè)任意的常量，C是一個(gè)固定的常量。除常數(shù)項(xiàng)外，rGIN 的近似比與多項(xiàng)式算法的最佳近似比相匹配，除無(wú)關(guān)項(xiàng)外，rGIN 的近似比與多項(xiàng)式算法的最佳近似比相匹配。

              

五、XS 一致性

正如第三章和第四章所提到的，GNN 與 WL 算法和分布式局部算法息息相關(guān)。本章將根據(jù) GNN、WL算法、分布式局部算法之間的關(guān)系總結(jié) GNN 的表達(dá)能力。我們將它們的關(guān)系稱作「XS 一致性」（根據(jù) Xu 等人和 Sato 等人的名字命名）。

Xu 等人和 Sato 等人的研究結(jié)果給出了 GNN、WL 算法以及分布式局部算法的要素之間的一致性。表 3 總結(jié)了這種一致性。

表 3：XS 一致性給出了 GNN、WL 算法，以及分布式局部算法的要素之間的具體聯(lián)系。

              

例如，分布式算法領(lǐng)域也研究了求解組合優(yōu)化問(wèn)題所需的通信輪數(shù)。Astrand 等人指出，              輪通信足以解決 2-近似問(wèn)題，其中 △ 是最大度。Babai 等人指出，1-WL 算法在 2 輪迭代之內(nèi)有很大概率可以確定出一個(gè)足夠大的隨機(jī)圖。根據(jù) XS 一致性，這樣的結(jié)論可以被用來(lái)設(shè)計(jì) GNN 的層數(shù)。

此外，WL 算法和分布式局部算法在很多領(lǐng)域內(nèi)都有聯(lián)系。例如，k-WL 算法與帶有計(jì)數(shù)量詞的一階邏輯、組合數(shù)學(xué)中的跳卵石游戲、線性規(guī)劃、Sherali-Adams 松弛都有聯(lián)系（這些問(wèn)題也可以通過(guò)組合優(yōu)化方式求解）。分布式局部算法與模態(tài)邏輯、常數(shù)時(shí)間算法都有關(guān)。具體而言：

• 對(duì)于任意的 k≥2，存在一個(gè)帶有計(jì)數(shù)量詞的  k 個(gè)變量的一階邏輯語(yǔ)句  ，使得     且 當(dāng)且僅當(dāng) k-WL 算法輸出 G 和 H 是「非同構(gòu)」的。

• 在游戲   中，玩家 2 在 G 和 H 上有一個(gè)獲勝策略，當(dāng)且僅當(dāng) k-WL 算法輸出 G 和 H是「可能同構(gòu)」的。

• 令 A 和 B 是 G 和 H 的鄰接矩陣。存在雙隨機(jī)實(shí)值矩陣 X 使得 AX=XB，當(dāng)且僅當(dāng) 1-WL 算法輸出 G 和 H 是「可能同構(gòu)」的。

• 令 A 和 B 是 G 和 H 的鄰接矩陣。如果 （k+2）-WL 算法輸出  G 和 H 是「可能同構(gòu)」的，則對(duì)于任意的 k≥2，存在 AX=XB 的秩-k Sherali-Adams 松弛的解，使得 X 是雙隨機(jī)的。

• 令 A 和 B 是 G 和 H 的鄰接矩陣。只有 （k+1）-WL 算法輸出  G 和 H 是「可能同構(gòu)」的，則對(duì)于任意的 k≥2，才存在 AX=XB 的秩-k Sherali-Adams 松弛的解，使得 X 是雙隨機(jī)的。

• 在相應(yīng)的Kripke模型上，VV_C（1） 模型可以識(shí)別梯度多模態(tài)邏輯的邏輯公式，而在VV_C（1）模型上，梯度多模態(tài)邏輯可以模擬任意算法。

• 一個(gè)分布式局部算法可以被轉(zhuǎn)化為一個(gè)常量時(shí)間算法。

得益于 XS 一致性，我們可以使用該領(lǐng)域的結(jié)論推導(dǎo)出許多 GNN 的理論特性。例如，Barcelo 等人利用 WL 算法和一階邏輯之間的關(guān)系構(gòu)建了更加強(qiáng)大的 GNN。

六、結(jié)語(yǔ)

本文中，我們介紹了圖神經(jīng)網(wǎng)絡(luò)的表達(dá)能力。換而言之，我們介紹了消息傳遞 GNN 的能力最多與一維 WL 算法相當(dāng)，以及如何將 GNN 推廣到 k 維 WL 算法上。

接著，我們介紹了 GNN 和分布式算法之間的聯(lián)系，指出了 GNN 在 GNN 可以計(jì)算的組合優(yōu)化算法近似比方面的局限性。 雷鋒網(wǎng)雷鋒網(wǎng)雷鋒網(wǎng)

不僅如此，我們還指出了將隨機(jī)特征添加到每個(gè)節(jié)點(diǎn)中會(huì)顯著提升近似比。

最后，我們將 GNN、WL 算法，以及分布式局部算法之間的關(guān)系總結(jié)為「XS 一致性」。

雷峰網(wǎng)原創(chuàng)文章，未經(jīng)授權(quán)禁止轉(zhuǎn)載。詳情見(jiàn)轉(zhuǎn)載須知。