下圖是圖同構(gòu)問(wèn)題的一個(gè)簡(jiǎn)單判別流程，從上至下的 3 個(gè)圖中，2 和 3 為同構(gòu)圖，1 則是與二者為異構(gòu)圖。相同的顏色表示相同的節(jié)點(diǎn)特征，鄰居聚合散列后會(huì)生成一個(gè)新的特征。若經(jīng)過(guò)若干次迭代后，若對(duì)應(yīng)節(jié)點(diǎn)的顏色不同，則能夠斷言二者互為異構(gòu)圖。

WL-test 只能夠判別兩個(gè)圖不是同構(gòu)圖，但并不能判定兩個(gè)圖一定是同構(gòu)圖。

而 Shervashidze et al. 又基于 WL-test 提出了 WL subtree kernel 算法，該算法能夠評(píng)估兩個(gè)圖的相似性。

作者并沒(méi)有詳細(xì)解釋 WL subtree kernel 的具體計(jì)算過(guò)程，這里我們也不必過(guò)于糾結(jié)具體的算法，只需要知道 WL WL subtree kernel 能夠高效地判定兩個(gè)圖結(jié)構(gòu)的相似性。

如果我們能夠在圖分類(lèi)任務(wù)中，精確而高效地判定出兩個(gè)圖的相似性，那么在預(yù)測(cè)任務(wù)中，就更容易確定兩個(gè)圖是否屬于一個(gè)類(lèi)別。而 GNN 的聚合操作與 WL-test 高度相似，因此我們可以合理懷疑：GNN 能夠在圖相似性評(píng)估的過(guò)程（圖表征學(xué)習(xí)）中達(dá)到 WL-test 的性能水平。只要聚合函數(shù)能起到跟 hash 函數(shù)一樣的單射性，那么理論上二者是能夠達(dá)到同級(jí)別的性能水平的。

Figure 1. 簡(jiǎn)單表述了經(jīng)過(guò) 2 次 WL-test 迭代后，每個(gè)節(jié)點(diǎn)聚合的鄰居信息。這個(gè)過(guò)程是跟 GNN agreegation 高度相似的。

3 THEORETICAL FRAMEWORK: OVERVIEW

整個(gè)論文中，作者假設(shè)節(jié)點(diǎn)的特征向量是離散的（畢竟特征向量值連續(xù)的情況下，99.9999% 都不會(huì)聚合出一個(gè)相同的嵌入，作者也就沒(méi)牛逼可吹了）。作者將這樣的圖稱(chēng)為有限圖。對(duì)于有限圖，更深卷積層的特征向量也同樣是離散的。

作者這里給出了 Multiset 的定義，但我們不用太關(guān)注這個(gè)概念，直接將其理解為節(jié)點(diǎn)的鄰居即可。

為了研究 GNN 的表征能力，作者分析了 GNN 什么情況下會(huì)將兩個(gè)節(jié)點(diǎn)映射到嵌入空間中的相同位置。直觀地說(shuō)，一個(gè)最強(qiáng)大的 GNN 只有在兩個(gè)節(jié)點(diǎn)具備相同的鄰居子樹(shù)結(jié)構(gòu)時(shí)才會(huì)將它們映射到同一個(gè)嵌入空間的位置。我們也可以將問(wèn)題簡(jiǎn)化為：GNN是否映射兩個(gè)相同的鄰域特征（multiset）映射到相同的嵌入表示。畢竟最強(qiáng)大的 GNN 永遠(yuǎn)不會(huì)將兩個(gè)不同的鄰域特征映射到同一個(gè)嵌入，即聚合函數(shù)必須是單射 injective 的。因此，我們將 GNN 的聚合函數(shù)抽象為一種可以由 neural network 表示的 multiset function，并分析該函數(shù)是否能夠表示為 injective multiset function。

只要 multiset function 能表示為單射函數(shù)，這就意味著在 GNN 的聚合鄰居操作中，對(duì)于不同鄰域的特征，聚合后能夠獲取到一個(gè)唯一的輸出表征，這樣就能夠捕捉到更多的圖結(jié)構(gòu)信息以及鄰居節(jié)點(diǎn)的特征信息。GNN 就能夠獲得非常強(qiáng)大的表征能力。

injective function，即單射函數(shù)，表示輸入跟輸出是一對(duì)一的關(guān)系，即對(duì)于不同的輸入x，f(x) 永遠(yuǎn)不可能存在相同的輸出。

接下來(lái)，我們將利用這個(gè)推論（injective multiset function）來(lái)開(kāi)發(fā)一個(gè)最強(qiáng)大的 GNN。在 Section.5 我們研究了當(dāng)下流行的 GNN variants 并且發(fā)現(xiàn)它們的聚合方式都本質(zhì)上不滿足 injective 的特性，因此其模型的表征能力都不太強(qiáng)，但這些模型也可以捕獲到 Graph 的其他的有趣的屬性。

4 BUILDING POWERFUL GRAPH NEURAL NETWORKS

首先我們給出了 GNN 模型的最大表征能力，即具備單射性的聚合策略。理想情況下，最強(qiáng)大的 GNN 可以通過(guò)將不同的圖結(jié)構(gòu)映射到不同的嵌入空間來(lái)區(qū)分它們。然而，這種將任意兩個(gè)不同的 Graph 映射到不同的嵌入空間的能力意味著要解決一個(gè)困難的圖同構(gòu)問(wèn)題。即：我們希望同構(gòu)圖映射到相同的嵌入空間，非同構(gòu)圖映射到不同的嵌入空間。但在我們的分析中，我們利用一個(gè)稍微弱一些的標(biāo)準(zhǔn)來(lái)定義 GNN 的表征能力 —— WL-test，它通常能夠很好地區(qū)分非同構(gòu)圖，并且性能也較高，除了少數(shù)例外情況（比如正則圖）。

引理2：只要圖神經(jīng)網(wǎng)絡(luò)能夠?qū)⑷我鈨蓚€(gè)異構(gòu)圖劃分到兩個(gè)不同的嵌入，那么 WL-test 也一定可以將這兩個(gè)圖判定為異構(gòu)圖。簡(jiǎn)單來(lái)說(shuō)，圖神經(jīng)網(wǎng)絡(luò)能做的，WL-test 一定能做；但圖神經(jīng)網(wǎng)絡(luò)不能做的，WL-test 也能做。

因此，任何基于聚合的 GNN 在區(qū)分不同的圖方面最多也就跟 WL-test 一樣強(qiáng)大。那么是否存在與 WL-test 一樣強(qiáng)大的 GNN 呢？

Theorem 3. 給出了肯定的答案：若鄰居聚合函數(shù)與 Readout function 都是 injective function，那么這樣的 GNN 與 WL-test 一樣強(qiáng)大。

定理3：若對(duì)于任意兩個(gè)非同構(gòu)圖 \(G_1\) and \(G_2\)（由 WL-test 判定），那么只要 GNN 具備足夠多層且滿足下面兩個(gè)條件，就能夠?qū)蓤D映射到不同的嵌入：

1. GNN 通過(guò)式子 \(h_v(k)=φ(h_v(k-1), f(\{h_u(k-1):u∈N(v)\}))\) 聚合并且遞歸更新節(jié)點(diǎn)特征

   其中，函數(shù) \(f(x)\) 的入?yún)?multisets，\(φ(x)\) 表示一個(gè) combination 操作，且滿足 injective。

2. GNN 的 graph-level readout 入?yún)⒁彩?multisets（即節(jié)點(diǎn)特征 \(\{h_v(k)\}\)），并且 readout 滿足 injective。

作者已經(jīng)在附錄中給出了定理3的證明。對(duì)于有限圖，單射性能夠很好地描述一個(gè)函數(shù)是否能夠維持輸入信息的獨(dú)特性。但對(duì)于無(wú)限圖，由于其中的節(jié)點(diǎn)特征是連續(xù)的，則需要進(jìn)一步考慮。

此外，描述學(xué)習(xí)到的特征在函數(shù)圖像中的親密度也是一件非常有趣的事情。我們將把這些問(wèn)題留到未來(lái)的工作，并且將重心放到輸入節(jié)點(diǎn)特征來(lái)自可數(shù)集合的情況。

引理4：主要是告訴我們，只要特征空間是離散的，那么在聚合后依然能夠得到一個(gè)離散的特征空間。本篇論文也是在特征離散的前提下討論的。

除了區(qū)分不同的圖以外，GNN 還有一個(gè)重要的優(yōu)點(diǎn)，即能夠捕獲圖結(jié)構(gòu)的相似性。而 WL-test 是無(wú)法捕獲圖之間的相似性的，這也是為什么我們不直接采用 WL-test 到圖數(shù)據(jù)任務(wù)處理中。

原因在于：WL-test 中節(jié)點(diǎn)的特征向量本質(zhì)上是 one-hot encodings，即描述節(jié)點(diǎn)屬于哪個(gè)類(lèi)別的 one-hot 編碼，且經(jīng)過(guò)鄰居聚合 hash 后得到的也只是 “代表新的節(jié)點(diǎn)類(lèi)別的 one-hot”，無(wú)法得到一個(gè)具備節(jié)點(diǎn)特征與圖結(jié)構(gòu)信息的空間嵌入，因此不能捕獲子樹(shù)之間的相似性。

相比之下，滿足 Theorem 3 的 GNN 通過(guò)學(xué)習(xí)將鄰居節(jié)點(diǎn)特征聚合映射到一個(gè)向量空間，相隔較遠(yuǎn)距離的嵌入大概率不屬于一個(gè)類(lèi)別，而相隔較近的嵌入則同屬一個(gè)類(lèi)別。這使得 GNN 不僅可以區(qū)分不同的圖結(jié)構(gòu)，還可以將近似的圖結(jié)構(gòu)映射到相似的嵌入，并捕獲圖結(jié)構(gòu)之間的依賴(lài)關(guān)系。捕獲節(jié)點(diǎn)的結(jié)構(gòu)相似性被證明是有助于泛化的，特別是當(dāng)鄰居的特征向量的是稀疏的，或者存在噪聲邊緣特征時(shí)。

4.1 GRAPH ISOMORPHISM NETWORK (GIN)

在確立了最強(qiáng)大的 GNN 的開(kāi)發(fā)條件后（滿足單射的聚合函數(shù)），我們接下來(lái)開(kāi)發(fā)一個(gè)簡(jiǎn)單的架構(gòu)，圖同構(gòu)網(wǎng)絡(luò) GIN，它能夠被證明滿足 Theorem 3. 中的條件。這個(gè)模型推廣了 WL-test 從而實(shí)現(xiàn)了 GNNs 系模型的最強(qiáng)判別能力。

為了建模一個(gè)單射鄰居聚合函數(shù)，作者提出了一種 “deep multisets” 理論，即：用神經(jīng)網(wǎng)絡(luò)參數(shù)化 “通用的單射鄰居聚合函數(shù)”。下一個(gè) Lemma 說(shuō)明了 sum-aggregators 能夠在鄰居聚合函數(shù)上具備單射的性質(zhì)。

引理5：假設(shè)向量空間 \(\mathcal{X}\) 是離散的，那么一定存在函數(shù) \(f\) 將節(jié)點(diǎn)特征進(jìn)行投影到一個(gè) n 維嵌入的函數(shù)，使得 \(h(X) = \sum_{x ∈ X} f(x)\) 的值對(duì)于每一個(gè)位于向量空間 \(\mathcal{X}\) 的 multiset \(X\) 都能取到一個(gè)唯一的值。此外，任何一個(gè) multiset function \(g\) 都能被拆解為 \(g(X) = φ(\sum_{x ∈ X} f(x))\)，其中 \(φ\(chéng)) 是某個(gè)函數(shù)。

引理5，主要就是證明了 sum-aggregation 的單射性，我們明白這一點(diǎn)即可。

作者在論文附錄中證明了 Lemma 5. 這里我們先不去管證明了。

Deep MultiSets 和 sets 最重要的一個(gè)區(qū)別是：是否滿足單射的性質(zhì)。比如 mean-aggregator 就不滿足單射性質(zhì)。（后面會(huì)解釋 mean-aggregation 為什么不滿足單射性）

“Deep MultiSets 和 sets 最重要的一個(gè)區(qū)別是：是否滿足單射的性質(zhì)?！?這句話我并不是看的很懂，個(gè)人的理解是：聚合函數(shù)的參數(shù)的豐富程度能夠決定能否滿足單射的性質(zhì)，比如平均聚合的多集特征中，真正處理的只是整個(gè)特征集合中的一部分特征。

以 Lemma 5. 中的 “通用的單射鄰居聚合函數(shù)” 建模機(jī)制作為構(gòu)建模塊，我們可以構(gòu)想出一個(gè)聚合方案，該方案能夠表示一個(gè) “入?yún)楣?jié)點(diǎn)以及其鄰居 multiset” 的泛函數(shù)，因此滿足 Theorem 3. 中的 injective condition。下一個(gè)推論給出了一個(gè)簡(jiǎn)單而具體的公式。

推論6：對(duì)于參數(shù) \(\epsilon\)，由無(wú)限種可能使得 \(h(c, X) = (1 + \epsilon) * f(c) + \sum_{x ∈ X} f(x)\) 對(duì)于每一個(gè)元組 (c, X) 都能夠拿得唯一的值。

其實(shí)跟引理5 差不太多，只需要把 c 理解為節(jié)點(diǎn)自身，X 理解為節(jié)點(diǎn)鄰居多集即可。

鑒于普遍近似理論 universal approximation theorem (Hornik et al., 1989; Hornik, 1991)，我們可以利用 MLPs 建模并學(xué)習(xí) Corollary 6. 中的 \(f\) and \(?\) 函數(shù)。實(shí)際操作上，我們用單層感知機(jī)對(duì) \(f^{(k+1)}??^{(k)}\) 進(jìn)行建模，因?yàn)?MLPs 能夠表示函數(shù)的組合。

在第一次迭代聚合時(shí)，若輸入的特征是 one-hot encodings，那么我們?cè)谶M(jìn)行 sum 聚合之前并不需要 MLPs，因?yàn)檫@些特征的求和操作已經(jīng)滿足單射性質(zhì)。我們可以讓 \(\epsilon\) 作為一個(gè)可學(xué)習(xí)參數(shù)或是固定參數(shù)。那么此時(shí) GIN 的聚合操作可以由如下公式表示：

一般來(lái)說(shuō)，可能存在許多其他強(qiáng)大的 GNNs。但 GIN 是最強(qiáng)大的 GNNs 之一，同時(shí)也很簡(jiǎn)單。

4.2 GRAPH-LEVEL READOUT OF GIN

通過(guò) GIN 學(xué)習(xí)的節(jié)點(diǎn)嵌入可以直接用于節(jié)點(diǎn)分類(lèi)問(wèn)題以及鏈路預(yù)測(cè)問(wèn)題，但對(duì)于圖分類(lèi)問(wèn)題，我們提出了以下方法：通過(guò)節(jié)點(diǎn)的嵌入構(gòu)造整個(gè)圖的嵌入。一般我們會(huì)把這個(gè)過(guò)程稱(chēng)為 Graph Readout。

Graph Readout 的一個(gè)重要因素是：隨著迭代（聚合）次數(shù)增加，對(duì)應(yīng)于子樹(shù)結(jié)構(gòu)的節(jié)點(diǎn)表征會(huì)變得更加精細(xì)以及覆蓋范圍更廣。因此足夠的迭代次數(shù)是獲得良好判別能力的關(guān)鍵。然而，有時(shí)較少迭代的特征也可能會(huì)帶來(lái)更好的泛化能力，所以并不是一味的增加聚合次數(shù)就能夠讓性能變得更好。

因此，作者利用到了每一次迭代聚合的節(jié)點(diǎn)表征信息，通過(guò)類(lèi)似 Jumping Knowledge Networks (Xu et al., 2018) 的架構(gòu)來(lái)實(shí)現(xiàn)，并用下列 Readout concat 方案替換 Eq 2.4：

即，把每一次迭代聚合得到的表征進(jìn)行一個(gè) concat。

基于 Theorem 3. 和 Corollary 6. GNN 能夠很好地推廣 WL-test 和 WL subtree kernel（在求和之前，我們不需要額外的 MLP，原因跟 Eq 4.1 的相同，此時(shí)的 sum 已經(jīng)滿足了單射性質(zhì)）

5 LESS POWERFUL BUT STILL INTERESTING GNNS

接下來(lái)，我們研究一下不滿足 Theorem 3 （單射）條件的 GNNs，包括 GCN，GraphSAGE。再?gòu)膬蓚€(gè)方面開(kāi)展關(guān)于聚合函數(shù) Eq4.1 的消融實(shí)驗(yàn)

1. 用 1-layer 的感知機(jī)而不采用 MLPs（單純鄰域節(jié)點(diǎn)線性求和作為聚合策略是否可行）
2. 均值池化或最大池化，而不采用 sum（不采用求和而是采用 mean or max 的聚合策略是否可行）

我們將會(huì)驚訝地發(fā)現(xiàn)，這些 GNN 變體會(huì)無(wú)法識(shí)別一些簡(jiǎn)單的圖，并且性能也不如 wL-test 強(qiáng)大。但盡管如此，采用 mean aggregators 的模型（如 GCN）在節(jié)點(diǎn)分類(lèi)任務(wù)中還是會(huì)得到不錯(cuò)的結(jié)果。為了更便于理解，我們將精確地描述不同 GNN 變體能或不能捕捉到的圖，并且討論有關(guān) “圖學(xué)習(xí)” 的含義。

5.1 1-LAYER PERCEPTRONS ARE NOT SUFFICIENT

Lemma 5 中的函數(shù) \(f\) 能夠?qū)⒔厝徊煌?multisets 映射到一個(gè)唯一的 Embeddings 上。基于普遍近似理論，函數(shù) \(f\) 能夠被 MLP 參數(shù)化。盡管如此，許多現(xiàn)有的 GNNs 都采用的是單層的感知機(jī)，然后通過(guò) Relu 進(jìn)行非線性激活。這樣的單層映射屬于廣義線性模型的例子。因此我們感興趣的是：?jiǎn)螌痈兄獧C(jī)是否能夠用于圖學(xué)習(xí)。但 Lemma 7 表明，確實(shí)存在單層感知機(jī)永遠(yuǎn)無(wú)法區(qū)分的 multisets。

引理7：確實(shí)存在不同的多集 \(X_1 ≠ X_2\)，但對(duì)于任何映射 \(W\) 二者映射后的嵌入都是相等的。單層感知機(jī)可以是某種線性映射，此時(shí) GNN 層會(huì)退化為簡(jiǎn)單的鄰域特征求和。但引理7是建立在線性映射中缺乏偏置項(xiàng) bias 的基礎(chǔ)上的。

雖然有了偏置項(xiàng)和足夠大的輸出維度，單層感知機(jī)大概率能夠區(qū)分不同的 multisets，但盡管如此，與采用多層感知機(jī)的模型不同，單層感知機(jī)即便是帶有偏置項(xiàng)，也不屬于 multisets function 的通用逼近函數(shù)。因此，即便 1-layer GNN 能夠?qū)⒉煌膱D嵌入到不同的表征，但這種嵌入可能無(wú)法充分捕獲兩個(gè)圖的相似性，并且對(duì)于簡(jiǎn)單分類(lèi)器（比如線性分類(lèi)器）來(lái)說(shuō)很難擬合。在 Section 7 中我們將會(huì)看到，1-layer GNN 在應(yīng)用圖分類(lèi)任務(wù)時(shí)，會(huì)導(dǎo)致嚴(yán)重的欠擬合，并且在 test Accuracy 方面也通常比 MLPs GNN 表現(xiàn)差。

5.2 STRUCTURES THAT CONFUSE MEAN AND MAX-POOLING

如果我們?cè)诰酆喜僮髦校瑢?\(h(X) = \sum_{x∈X}f(x)\) 替換為 GCN 中的 mean pooling 或者 GraphSAGE 中的 max pooling 可能會(huì)發(fā)生什么？

平均池化聚合以及最大池化聚合都仍然屬于 well-defined 的多集函數(shù)，因?yàn)樗鼈兌际桥帕胁蛔兊?。但它們都不滿足單射性。圖2根據(jù)聚合器的表征能力對(duì)三種聚合器進(jìn)行了排名，并且圖3闡述了 max-pooling 和 mean-pooling 無(wú)法區(qū)分的結(jié)構(gòu)。節(jié)點(diǎn)顏色表明了不同的節(jié)點(diǎn)特征，并且我們假設(shè) GNNs 會(huì)在 combine 操作之前先執(zhí)行 Aggregation。

對(duì)于 sum 聚合來(lái)說(shuō)，能夠捕捉 multiset 中所有特征的信息，而 mean 聚合能捕捉部分比例特征的信息，而 max 聚合則忽略了特征信息的多樣性。

在 Figure 3a 中，所有的節(jié)點(diǎn)都具備相同的特征，因此對(duì)于 mean 和 max 聚合都會(huì)得到相同的結(jié)果，不具備單射性。即便兩個(gè)圖從結(jié)構(gòu)上來(lái)看并不相同，但 mean and max 聚合卻能夠取到相同的值，也就意味著在這種情況下，mean and max 聚合無(wú)法捕獲到任何圖結(jié)構(gòu)的信息。但對(duì)于 sum pooling aggregators 能夠給出不同的值，也就意味著 sum aggregator 能夠區(qū)分這兩種圖結(jié)構(gòu)（但單純的線性求和可能無(wú)法獲取到圖結(jié)構(gòu)信息）。同樣的參數(shù)也可以應(yīng)用于任何無(wú)標(biāo)記的圖。如果使用節(jié)點(diǎn)度而不是常量值作為節(jié)點(diǎn)輸入特征，原則上，mean 聚合可以起到類(lèi)似 sum 聚合的作用，但最大池化不能。

Fig.3a 表明，平均和最大池化對(duì)于區(qū)分具備重復(fù)特征的節(jié)點(diǎn)是困難的。我們定義 \(h_{color}\) 為節(jié)點(diǎn)特征的映射結(jié)果（相同特征會(huì)映射到相同的顏色）。Fig.3b 表明，對(duì)于兩個(gè)不同結(jié)構(gòu)的圖，最大池化聚合 \(max(h_{g}, h_{r})\) and \(max (h_{g}, h_{r}, h_{r})\) 能夠取到相同的表征。因此最大池化聚合并不能區(qū)分這兩張圖。但 sum aggregator 仍然能夠區(qū)分。同樣地，對(duì)于 Fig.3c，mean and max pooling 同樣會(huì)無(wú)法區(qū)分，因?yàn)?\(\frac{1}{2}(hg + hr) = \frac{1}{4}(hg + hg + hr + hr)\)

5.3 MEAN LEARNS DISTRIBUTIONS

為了描述 mean aggregator 能夠區(qū)分的 multisets 類(lèi)別，我們考慮一個(gè)例子：\(X_1=(S, m)\) and \(X_2=(S, k·m)\)，其中 \(X_1\) and \(X_2\) 擁有相同元素但個(gè)數(shù)不同（但成比例）的集合，任何平均聚合器都將 \(X_1\) 和 \(X_2\) 映射到相同的嵌入，因?yàn)樗皇菍?duì) \(X_i\) 的特征取平均值。

若在 graph 任務(wù)中，若 提取統(tǒng)計(jì)信息以及信息分布 比 提取特定結(jié)構(gòu)信息 更加重要，那么 mean aggregator 的效果還不錯(cuò)。此外，若節(jié)點(diǎn)特征多樣且重復(fù)性較少時(shí)，mean aggregator 跟 sum aggregator 的效果一樣好?；蛟S這能夠被解釋為什么平均存在一定的局限性，但平均聚合 GNNs 對(duì)節(jié)點(diǎn)分類(lèi)的任務(wù)依然很有效，比如文章主題分類(lèi)，社群檢測(cè)這類(lèi)任務(wù)，它們都屬于節(jié)點(diǎn)特征豐富，且鄰域特征分布為分類(lèi)任務(wù)提供了更明顯的信息。

5.4 MAX-POOLING LEARNS SETS WITH DISTINCT ELEMENTS

Fig.3 的例子表明：最大池化會(huì)將多個(gè)具備相同特征的節(jié)點(diǎn)視為單個(gè)節(jié)點(diǎn)（即，將 multiset 看作為單個(gè) set）。最大池化捕捉特征的并非確切的圖結(jié)構(gòu)信息，也不是圖節(jié)點(diǎn)的分布信息。最大池化適用于識(shí)別 “代表性骨架”，Qi et al. 的工作從經(jīng)驗(yàn)上表明，最大池化聚合學(xué)習(xí)適合識(shí)別 3D 點(diǎn)云的 “骨架”，并且對(duì)噪聲和異常值具有更強(qiáng)的魯棒性。為了完整性起見(jiàn)，下一個(gè)推論表明，最大池化聚合器捕獲了 multiset 的底層集合。

可以將 3D 點(diǎn)云理解為三維圖像，一般會(huì)應(yīng)用于建筑安全隱患識(shí)別，城市管理等。

推論9：可以簡(jiǎn)單理解為，max 聚合能夠捕捉到結(jié)構(gòu)相似的底層結(jié)構(gòu)信息。其實(shí)跟最大池化的特性比較相似，具備更好的魯棒性以及抗噪性，但缺點(diǎn)是會(huì)丟失一些信息。但即便如此，依然能夠捕獲到底層結(jié)構(gòu)相同的類(lèi)別。

5.5 REMARKS ON OTHER AGGREGATORS

還有一些其他的非標(biāo)準(zhǔn)鄰居聚合方式，但本篇論文并未提及，比如：weighted average via attention (Velickovic et al., 2018)，LSTM pooling (Hamilton et al., 2017a; Murphy et al., 2018). 本文強(qiáng)調(diào)的是：該理論框架足夠普適去描述基于聚合方式的 GNNs 的表征性能。未來(lái)會(huì)考慮應(yīng)用框架去分析和理解其他的聚合方式。

6 OTHER RELATED WORK

盡管 GNNs 取得了成功（從經(jīng)驗(yàn)主義的角度來(lái)看），但用數(shù)學(xué)方法研究其性質(zhì)的工作相對(duì)較少。一個(gè)例外是Scarselli et.al（2009a）的工作，他認(rèn)為：最早的 GNN 模型（Scarselli et.al，2009b）可以在概率上近似于 measurable functions。Lei et.al（2017）表明，他們提出的架構(gòu)位于圖核的 RKHS（abbr. reproducing kernel Hilbert space 再生式原子核希爾伯特空間） 中，但沒(méi)有明確研究它可以區(qū)分哪些圖。這些作品都側(cè)重于一個(gè)特定的體系結(jié)構(gòu)，并不容易推廣到多個(gè)體系結(jié)構(gòu)。

相比之下，上述結(jié)論為分析和描述一個(gè)廣泛類(lèi)別的 GNN 的表達(dá)能力提供了一個(gè)更一般的理論框架。最近，許多基于 GNN 的架構(gòu)被提出，包括和聚合和 MLP（巴塔格利亞等人，2016；斯卡塞利等人，2009b；Duvenaud等人，2015），而大多數(shù)沒(méi)有理論推導(dǎo)。與許多先前的 GNN 架構(gòu)相比，我們的圖同構(gòu)網(wǎng)絡(luò)（GIN）在理論上更加充分，并且簡(jiǎn)單而強(qiáng)大。

measurable functions: 不太理解這個(gè)概念具體是什么函數(shù)，我個(gè)人暫且理解為可以通過(guò)公式表達(dá)的函數(shù)（或者能夠通過(guò)最大近似理論去利用 MLPs 逼近的函數(shù)）

7 EXPERIMENTS

在實(shí)驗(yàn)部分比較了 GIN 于其他較弱的 GNN 變體在測(cè)試集，訓(xùn)練集上的表現(xiàn)。訓(xùn)練集能夠去評(píng)估模型的表征能力，且測(cè)試集能評(píng)估模型的泛化能力。

Datasets. 我們采用 9 個(gè)圖分類(lèi) benchmarks：4個(gè)生物信息學(xué)數(shù)據(jù)集（MUTAG，PTC，NCI1，PROTEINS）以及5個(gè)社交網(wǎng)絡(luò)數(shù)據(jù)集（COLLAB，IMDB-BINARY，IMDB-MULTI，REDDIT-BINARY，REDDIT-MULTI5K）。重要的是，我們實(shí)驗(yàn)?zāi)康牟⒉皇亲屇Ｐ鸵蕾?lài)于輸入節(jié)點(diǎn)的特征，而是主要讓模型從網(wǎng)絡(luò)結(jié)構(gòu)中學(xué)習(xí)。因此，在生物信息學(xué) Graph 中，節(jié)點(diǎn)具有分類(lèi)輸入特征；但在社交網(wǎng)絡(luò)中，節(jié)點(diǎn)沒(méi)有特征。

對(duì)于社交網(wǎng)絡(luò)數(shù)據(jù)集，我們創(chuàng)建節(jié)點(diǎn)特征如下：對(duì)于 REDDIT 數(shù)據(jù)集，我們將所有的節(jié)點(diǎn)特征向量設(shè)置為統(tǒng)一（因此，這里的特征是不具備信息的）；對(duì)于其他的社交網(wǎng)絡(luò) Graphs，我們基于節(jié)點(diǎn) degrees 去生成 one-hot encodings 以表示節(jié)點(diǎn)特征。數(shù)據(jù)集統(tǒng)計(jì)匯總于 table.1 更多的數(shù)據(jù)細(xì)節(jié)可以在 Appendix.I 中找到。

Models and configurations. 我們?cè)u(píng)估了 GINs（Eqs.4.1 and 4.2）以及其他 less powerful GNN 變體。而針對(duì) GIN 框架，我們考慮它的兩個(gè)變體：

1. 基于 Eq.4.1 進(jìn)行梯度下降學(xué)習(xí)參數(shù) \(\epsilon\) 的 GIN-\(\epsilon\)
2. 一個(gè)更簡(jiǎn)單的 GIN-0，其中 Eq.4.1 的參數(shù) \(\epsilon\) 固定為0。

實(shí)驗(yàn)表明 GIN-0 有更強(qiáng)大的性能：GIN-0 不僅與 GIN-\(\epsilon\) 同樣擬合訓(xùn)練數(shù)據(jù)，而且具備良好的泛化性能，而在測(cè)試精度方面略微但始終優(yōu)于GIN-\(\epsilon\)。對(duì)于其他較弱的 GNN 變體 我們考慮替換 GIN-0 的 sum 聚合，采用 mean or max-pooling，或者替換多層感知機(jī)為單層感知機(jī)。

在 Fig.4 以及 Table.1 中，模型會(huì)根據(jù) 其采用的聚合方式/感知機(jī)的層數(shù) 來(lái)命名，例如 mean-1-layer 和 max-1-layer 分別對(duì)應(yīng)了 GCN 和 GraphSAGE，并且會(huì)在此基礎(chǔ)上進(jìn)行較小的修改。我們對(duì) GINs 以及 GNN 變體都采用相同的 Graph Readout（Eq.4.2），為了更好的測(cè)試性能，生物學(xué)信息數(shù)據(jù)集上采用 sum readout，社交網(wǎng)絡(luò)數(shù)據(jù)集采用 mean readout。

實(shí)驗(yàn)采用十折交叉驗(yàn)證，并且報(bào)告了交叉驗(yàn)證中，10次驗(yàn)證精度的平均值和標(biāo)準(zhǔn)差。對(duì)于所有的模型配置，采用5個(gè) GNN 層（包括輸入層），并且 MLPs 采用2層。Batch Normalization 應(yīng)用于每一個(gè) hidden layer。采用 Adam optimizer 并且初始化學(xué)習(xí)率為 0.01 并且以每 50 次 epochs 進(jìn)行一次衰減率為 0.5 的權(quán)重衰減。我們對(duì)于每個(gè)數(shù)據(jù)集都需要調(diào)整的超參為：

1. hidden units number：對(duì)于生物信息學(xué) Graph 采用 {16, 32}，社交網(wǎng)絡(luò) Graph 采用 64
2. batch size：
3. dropout ratio：{0, 0.5} after dense layer
4. epochs number：調(diào)整為 10 次平均交叉驗(yàn)證精度最好的 single epoch

注意，由于數(shù)據(jù)集size較小，使用驗(yàn)證集進(jìn)行超參調(diào)整時(shí)非常不穩(wěn)定的，比如 MUTAG 驗(yàn)證集只包含 18 條數(shù)據(jù)。

我們還報(bào)告了對(duì)于不同 GNNs 的訓(xùn)練精度，所有的模型超參都是固定的：

• 5 GNN layers（include input layer）
• hidden units of size 64
• minibatch of size 128
• dropout ratio 0.5

為了比較，WL subtree kernel 的訓(xùn)練精度也會(huì)被報(bào)告，其中我們將迭代次數(shù)設(shè)置為4，對(duì)比 5 GNN layers。

Baselines. 我們將上述 GNNs 與最先進(jìn)的圖分類(lèi)基準(zhǔn)進(jìn)行比較：

1. WL subtree kernel，采用 C-SVM 作為分類(lèi)器，我們調(diào)整的超參為 SVM 的 C；WL iterations number \(∈ \{1,2,...,6\}\)
2. 最先進(jìn)的深度學(xué)習(xí)架構(gòu) —— DCNN，PATCHY-SAN，DGCNN
3. Anonymous Walk Embeddings

對(duì)于深度學(xué)習(xí)方法和 AWL，我們報(bào)告了原始論文中報(bào)告的準(zhǔn)確度。

7.1 RESULTS

Training set performance. 我們通過(guò)比較 GNNs 的訓(xùn)練精度來(lái)驗(yàn)證之前對(duì) GNN 模型表征能力的理論分析。具備較高表征能力的模型應(yīng)該具備較高的訓(xùn)練準(zhǔn)確度。Fig.4 展示了具備相同超參的 GINs 和較弱的 GNN 變體的訓(xùn)練曲線。首先，理論上最強(qiáng)大的 GNN，即 GIN-\(\epsilon\) 和 GIN-0 都能夠完美地?cái)M合所有的訓(xùn)練集。

而在實(shí)驗(yàn)中，對(duì)比 GIN-0 可以發(fā)現(xiàn)，GIN-\(\epsilon\) 針對(duì)參數(shù) \(\epsilon\) 的學(xué)習(xí)并沒(méi)有在擬合訓(xùn)練數(shù)據(jù)中獲得收益；采用 mean/max pooling 或單層感知機(jī)的 GNN 變體在許多數(shù)據(jù)集上都產(chǎn)生了嚴(yán)重的過(guò)擬合。可以發(fā)現(xiàn)，這些模型的訓(xùn)練精度水平與之前分析的 模型表征能力進(jìn)行的排名 一致，在訓(xùn)練精度方面

• MLPs 大于 1-layer perceptions
• sum aggregators 大于 mean / max aggregators

在我們的數(shù)據(jù)集上，GNN 的訓(xùn)練精度從未超過(guò) WL subtree kernel 的訓(xùn)練精度，這是意料之中的，因?yàn)?GNN 通常比 WL-test 的判別能力低。例如在 IMDBBINARY 上，沒(méi)有任何一個(gè)模型能夠完美地?cái)M合訓(xùn)練集，GNN 最多也只能夠達(dá)到與 wL kernel 相同的訓(xùn)練精度。這種實(shí)驗(yàn)結(jié)果與論文得出的結(jié)論一致，即 WL-test 是基于聚合的 GNN 的表征能力上限。然而 WL kernel 無(wú)法學(xué)習(xí)如何組合節(jié)點(diǎn)特征（即不能具備泛化能力），這對(duì)于預(yù)測(cè)任務(wù)來(lái)說(shuō)是非常關(guān)鍵的，接下來(lái)將說(shuō)明這個(gè)部分。

Test set performance.

接下來(lái)，我們比較 test accuracies。雖然我們的理論結(jié)果并沒(méi)有直接談到 GNNs 的泛化能力，但我們有理由去期待具備強(qiáng)大表征能力的 GNNs 能夠準(zhǔn)確捕捉感興趣的圖結(jié)構(gòu)，從而能夠很好地泛化。Table.1 比較了 GINs（Sum-MLP），其他 GNN 變體以及一些最先進(jìn)的 test accuracy baselines。

首先，對(duì)于 GINs，尤其是 GIN-0，在 9 個(gè)數(shù)據(jù)集上都比較弱的 GNN 變體表現(xiàn)都好。GINs 在社交網(wǎng)絡(luò)數(shù)據(jù)集上表現(xiàn)更好，這種類(lèi)型的數(shù)據(jù)包含了大量的訓(xùn)練圖數(shù)據(jù)。

而對(duì)于 Reddit 數(shù)據(jù)集，所有節(jié)點(diǎn)都共享相同的標(biāo)量作為節(jié)點(diǎn)特征。GINs 以及 sum-aggregation GNNs 都準(zhǔn)確地捕獲了圖結(jié)構(gòu)，并且顯著優(yōu)于其他模型。然而，mean-aggregation GNNs 無(wú)法捕獲未標(biāo)記圖的任何結(jié)構(gòu)（如 Section 5.2 所預(yù)測(cè)的一樣），并且表現(xiàn)甚至不如隨機(jī)預(yù)測(cè)。

即使提供節(jié)點(diǎn)的 degree 作為輸入特征，基于 mean-aggregation GNNs 也遠(yuǎn)遠(yuǎn)不如 sum-aggregation GNNs（在 REDDIT-BINARY 數(shù)據(jù)集上，mean-mlp aggregation 準(zhǔn)確率為 71.2±4.6%，在REDDIT-MULTI5K 準(zhǔn)確率為 41.3±2.1%）

比較 GINs（GIN-0 以及 GIN-\(\epsilon\)），我們觀察到 GIN-0 的性能略?xún)?yōu)于 GIN-\(\epsilon\)。由于兩種模型都能夠很好地?cái)M合訓(xùn)練數(shù)據(jù)，GIN-0 可能是因?yàn)楸?GIN-\(\epsilon\) 更簡(jiǎn)單因此獲得了更好的泛化能力。

8 CONCLUSION

在本文中，我們開(kāi)發(fā)了一個(gè)關(guān)于 GNNs 表征能力推到的理論基礎(chǔ)，并證明了當(dāng)下流行的 GNN variants 的表征能力上限。我們還基于鄰域聚合設(shè)計(jì)了一個(gè)可證明的性能最強(qiáng)大的 GNN。未來(lái)工作的一個(gè)有趣方向是超越鄰域聚合（或消息傳遞），以追求更強(qiáng)大的圖學(xué)習(xí)架構(gòu)。為了完成這個(gè)愿景，理解和改進(jìn) GNN 的泛化特性以及更好地理解它們的優(yōu)化前景也會(huì)很有趣。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-448989.html

到了這里，關(guān)于全網(wǎng)最詳細(xì)解讀《GIN-HOW POWERFUL ARE GRAPH NEURAL NETWORKS》?。。〉奈恼戮徒榻B完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！