介紹一下基本的知識，GNN的輸入是一張圖，圖中有節(jié)點集合，參數(shù)包括V、E、W、X等。GNN早期典型的兩類任務(wù)是節(jié)點分類和圖分類，在節(jié)點分類任務(wù)中，GNN的目的是訓(xùn)練得出網(wǎng)絡(luò)當(dāng)中節(jié)點的表達(dá)，然后根據(jù)節(jié)點的表達(dá)進(jìn)行下游的任務(wù)；在圖分類任務(wù)中，GNN的目的是要訓(xùn)練得到圖的表達(dá)，有了圖表達(dá)之后再對圖做分類。在這兩個典型的任務(wù)中，目前80%、90%的工作都傾向于節(jié)點分類，只有少數(shù)是圖分類。關(guān)于GNN的標(biāo)準(zhǔn)框架，目前用得比較多的是Aggregate+Combine，此框架比較靈活，圖分類任務(wù)和節(jié)點分類任務(wù)都適用，其策略方式是通過迭代，用鄰居的表示迭代更新自己的表示。策略一共分兩步，第一步是聚合鄰居信息；第二步是把鄰居信息和自己上一輪的信息進(jìn)行耦合。下面舉幾個這種框架的例子，第一個是2017年提出的GraphSAGE，其操作是把鄰居的表達(dá)進(jìn)行變換之后，取里面最大的一個賦給自己，然后再把學(xué)到的表達(dá)和自己上一輪的表達(dá)做整合，隨后得到新的表達(dá)。值得一提的是，GraphSAGE用了Max-pooling的方式，此方式限制了他的表達(dá)能力，是導(dǎo)致表達(dá)能力喪失關(guān)鍵的一步。GCN的表達(dá)方式直接，將鄰居進(jìn)行特征變換，然后按照矩陣規(guī)劃進(jìn)行傳遞，它的特點是把AGGREGATE和COMBINE兩個操作進(jìn)行了整合。值得注意的是，GCN采用了Mean-pooling的方式，此方式也限制了它的表達(dá)能力。另外，GCN的改進(jìn)版是GAT，其采用的方式是weighted mean pooling。3
圖神經(jīng)網(wǎng)絡(luò)的表達(dá)能力如何
前面是關(guān)于圖神經(jīng)網(wǎng)絡(luò)基本介紹，現(xiàn)在回到今天的主題：圖神經(jīng)網(wǎng)絡(luò)的表達(dá)能力。我們先討論2019年發(fā)表在ICLR上的《How powerful are graph neural networks》。首先明確什么是表達(dá)能力，所謂表達(dá)能力一般有兩個方面，第一個方面是表示的空間大小，例如，一個N位的二進(jìn)制能表達(dá)N的二次方個數(shù)。這種表達(dá)能力旨在表示多少不同的東西，不同的結(jié)果。第二個方面是關(guān)于近似能力。例如設(shè)計一個神經(jīng)網(wǎng)絡(luò)能夠近似什么樣的函數(shù)。值得一提的是，在1989年的時候就有了證明：神經(jīng)網(wǎng)絡(luò)的層次只要足夠深，就可以逼近任意連續(xù)函數(shù)。這個“萬能近似定理”也解釋了為什么深度學(xué)習(xí)從來不擔(dān)心表達(dá)能力的原因。但是GNN提出之后，深度學(xué)習(xí)表達(dá)能力的話題又被提起，2017年有研究員發(fā)現(xiàn)深度學(xué)習(xí)的表達(dá)能力和深度神經(jīng)網(wǎng)絡(luò)的層次是指數(shù)關(guān)系，假如網(wǎng)絡(luò)有D層，那么表達(dá)能力與“某個數(shù)”的D次方成正比，大家感興趣可以看相關(guān)的論文。GNN引進(jìn)之后，對于表達(dá)能力有什么樣的啟示呢？如上述左圖所示，如果不看結(jié)構(gòu)，節(jié)點的標(biāo)號標(biāo)1還是標(biāo)2是區(qū)分不開。如果想?yún)^(qū)分這個不同的“標(biāo)號1”，需要觀察標(biāo)號的鄰居，可以通過鄰居信息進(jìn)行區(qū)分。GCN可以把鄰居信息進(jìn)行聚合，提升區(qū)分節(jié)點的能力。如上圖左下所示，在一層GCN操作完成之后，已經(jīng)可以區(qū)分一些標(biāo)號，但左下圖四個“標(biāo)3”的點還是區(qū)分不出來。所以，一層GCN區(qū)分能力并不夠，那能否通過加深層次解決表達(dá)能力呢？兩層GNN之后，如上圖所示，變成了八個點，并可以完全區(qū)分開。所以，如果用兩層GCN對上述節(jié)點進(jìn)行分類，無論Label標(biāo)記成何種方式，GCN的表達(dá)能力都能滿足分類要求。上面是兩層GCN完全可以區(qū)分的例子。回到剛才的問題，把GNN加深就一定能把表達(dá)能力做上去嗎？也就是說，我們能不能通過深度實現(xiàn)無窮大的表達(dá)能力？2019年那篇ICLR文章回答：不可以！上面是節(jié)點的角度，下面從圖的角度進(jìn)行討論，也即如果把不同的圖做成一個表示，GNN表示圖的方面表達(dá)能力如何。這里有兩個關(guān)鍵因素，一個是節(jié)點的特征，一個是圖的結(jié)構(gòu)，節(jié)點的特征剛才已經(jīng)講過了，如果把節(jié)點做深度神經(jīng)網(wǎng)絡(luò)，已經(jīng)可以幫我們解決掉表達(dá)能力問題。所以，另外一個表達(dá)能力的限制就來自于圖的結(jié)構(gòu)。下面看兩個簡單的例子，左上角的圖都是24個碳原子，有兩個有機(jī)化學(xué)的分子式：左邊的結(jié)構(gòu)是兩層，一層12個碳，24個碳分成平行的兩層，都和自己的鄰居相連。右邊圖是24個碳結(jié)構(gòu)變成一個正球體，每個面都由五個碳構(gòu)成。這兩個結(jié)構(gòu)，人一眼就能看出它倆的不同，但是GCN無法區(qū)分，即使把層次加深到無窮多層也區(qū)分不了它倆。即使簡化成左下角兩個更加簡單的圖，GCN也區(qū)分不出來。所以，這給出的啟示是：通過提升GCN的深度來提升圖的表達(dá)能力，是無法做到的。那么它的表達(dá)能力受限在哪兒？既然是圖的結(jié)構(gòu)相關(guān)，那我們就想到可以采用WL-test，對兩個圖是否同構(gòu)進(jìn)行測試。WL test 的主要是通過聚合節(jié)點鄰居的 label，然后通過 hash 函數(shù)得到節(jié)點新的 label，不斷重復(fù)知道每個節(jié)點的 label 穩(wěn)定不變。穩(wěn)定后，統(tǒng)計兩張圖的label的分布，如果分布相同，則一般認(rèn)為兩張圖時同構(gòu)的。所以，WL test遞歸聚合鄰居的方式和GNN類似，都是一個遞歸地來更新自己的特征，只不過更新的方式，WL test做了一個單射函數(shù)，但是GNN用的聚合函數(shù)，無論是Max、Mean還是Sum，大部分情況下都不是單射的。也就是說GNN非單射的聚合方式，把原本不一樣的東西聚合后變得一樣了，這讓GNN喪失了表達(dá)能力。更直白一些，WL Test是一個單射函數(shù)，GNN不是單射函數(shù)，于是WL Test為GNN的表達(dá)能力提供了一個理論上的上界。（注：這里GNN說的是通過鄰居聚合，如果別的聚合方式，性能可能超過WL test的）為什么當(dāng)前流行的GNN，例如GCN、GraphSAGE為什么不是單射呢？原因有兩個，一個是每層做特征變換做得不夠；另一個是，這些圖神經(jīng)網(wǎng)絡(luò)用的聚合函數(shù)天然具有單射屬性。所以，在論文《How Powerful are Graph Neural Networks》中，作者提出來了新的圖模型GIN(Graph Isomorphism Network)，其中I表示圖同構(gòu)，關(guān)鍵思想是構(gòu)建了一個單射函數(shù)。有了單射函數(shù)，GIN也達(dá)到了和W L test類似的表達(dá)能力，達(dá)到了圖神經(jīng)網(wǎng)絡(luò)表達(dá)能力的上界。后來作者對GIN模型的表達(dá)能力進(jìn)行了驗證，具體是用數(shù)據(jù)的擬合能力進(jìn)行測評，驗證思想是：如果表達(dá)能力足夠強(qiáng)，那么數(shù)據(jù)集上的每個數(shù)據(jù)都能精確擬合。驗證結(jié)果確實符合作者的預(yù)期，通過構(gòu)造一個單設(shè)的聚合函數(shù)，能夠?qū)崿F(xiàn)和WL Test一樣的表達(dá)能力。那么，泛化能力如何呢？也即在Test Loss 表現(xiàn)如何呢？這里有一個直觀上的事實是，如果Training Loss做得不好，那么Test Loss表現(xiàn)也不會好，畢竟Train是Test的基準(zhǔn)，另外，如果訓(xùn)練集上表現(xiàn)非常好，而在測試集上表現(xiàn)非常差，那么就出現(xiàn)過擬合現(xiàn)象，沒有泛化能力了。提出GIN的作者也在論文中證實了，GIN在表達(dá)能力上很強(qiáng)，但是在其他任務(wù)上，泛化能力還不如表達(dá)能力差的模型，如上圖GIN在幾個數(shù)據(jù)集上的表現(xiàn)。所以，這給圖神經(jīng)網(wǎng)絡(luò)帶來的啟示是：高的表達(dá)能力，并不總意味著對下游任務(wù)友好，但是低表達(dá)能力總是不好的。綜上，我們還是希望構(gòu)造出一個強(qiáng)表達(dá)能力的圖神經(jīng)網(wǎng)絡(luò)，這是當(dāng)前學(xué)界研究員的共識。總結(jié)一下ICLR 2019那篇論文的工作：首先GNN在理論上有一個表達(dá)能力的上界，這個上界是WL Test；為什么是WL Test？因為它的聚合函數(shù)是單射；同時這篇論文又提出了GIN這一有著單射聚合函數(shù)的圖神經(jīng)網(wǎng)絡(luò)，并對其表達(dá)能力進(jìn)行了驗證。4
