• 論文地址：https:///pdf?id=Mspk_WYKoEH
• 歡迎關(guān)注小編知乎：戴鴿

消息傳遞是圖網(wǎng)絡(luò)中的一種常見方法了，一般來(lái)說(shuō)都是傳一個(gè)節(jié)點(diǎn)信息，但是在這篇文章中，作者認(rèn)為局部子圖信息也是能傳信息的，并且這種信息一樣能提高模型表現(xiàn)能力，使其能抓住更多的局部信息。另外，這個(gè)模型是可以通用到任意一個(gè)圖網(wǎng)絡(luò)上的，包括但不限于GCN，GIN。

Introduction

圖網(wǎng)絡(luò)通常采用信息傳遞的方式收集鄰居節(jié)點(diǎn)信息，然后采用聚合的方法更新當(dāng)前節(jié)點(diǎn)。然而這樣的方法經(jīng)常被認(rèn)為不能完整的刻畫一張圖。因此，作者將一個(gè)圖分解為多個(gè)子圖來(lái)增強(qiáng)圖網(wǎng)絡(luò)的表達(dá)能力，并且，這種方法在任何圖網(wǎng)絡(luò)上都是能適用的。如圖所示，子圖分割的方法采用以一個(gè)點(diǎn)為中心，采樣其鄰居構(gòu)成一個(gè)小圖，這種操作參考了CNN的設(shè)計(jì)，將每個(gè)點(diǎn)視作一個(gè)像素，這樣每個(gè)小子圖都是一個(gè)kernel，因此這個(gè)方法也叫做GNN-AK（GNN As Kernel）。由于參考了CNN的做法，所以Base GNN本質(zhì)上是統(tǒng)一的一套參數(shù)。圖中的Emb(i | Sub[j])項(xiàng)表示每個(gè)節(jié)點(diǎn)的信息都是由某種子圖中的信息帶來(lái)的，并且，作者定義了3中聚合器來(lái)整合這些信息。

Method

首先還是將一個(gè)圖表示成的形式，節(jié)點(diǎn)特征表示為。如果考慮為圖分類任務(wù)，那么這個(gè)圖對(duì)應(yīng)的標(biāo)簽應(yīng)當(dāng)記為。如果將一個(gè)點(diǎn)看成中心，則他的k階鄰居可以記成。根據(jù)鄰居節(jié)點(diǎn)的定義，當(dāng)k為1時(shí)，就能的得到作者對(duì)于星型子圖的定義： 。常規(guī)情況下，信息傳遞會(huì)寫成如下形式：

和分別表示l層的更新函數(shù)和聚合函數(shù)，表示圖級(jí)別的表征。從同質(zhì)圖的角度出發(fā)，如果按照1-WL的思路，每個(gè)節(jié)點(diǎn)可以可以被設(shè)置為一種與眾不同的標(biāo)簽，或者叫涂了一層新的顏色，即。如果再進(jìn)行一次信息傳遞，那么實(shí)際上就是對(duì)這些節(jié)點(diǎn)上的標(biāo)簽進(jìn)行一次壓縮，更新為。這個(gè)過(guò)程作者將其定義成或者說(shuō)是，這里指一種圖的函數(shù)，因此，如果是1-WL，這個(gè)方程最后變成了。

顯然，如果直接進(jìn)行這樣的壓縮肯定會(huì)喪失圖的表達(dá)能力，因此，可以假設(shè)這里的子圖本身也具有一定特征，用表示子圖在第l層上的隱藏屬性，即。這樣就可以說(shuō)第l層上的圖信息是受到這個(gè)子圖的影響了。與之前的信息傳遞不同，GNN-AK這個(gè)時(shí)候就可以說(shuō)是傳遞了更多的子圖特征。

簡(jiǎn)化一下表達(dá)方式，用替換。對(duì)于節(jié)點(diǎn)的嵌入特征表達(dá)就可以寫成，嵌入的方法可以認(rèn)為是一個(gè)GNN。如果同樣寫成信息傳遞的形式，則可以寫成：

如果再加入自己本身的信息，還能寫成：

更進(jìn)一步，還能考慮當(dāng)前節(jié)點(diǎn)是否對(duì)存在于不同子圖：

這里也可以添加一個(gè)門操作，保證只讓選中的子圖參與信息傳遞，即：

在GNN-AK的最終版本GNN-AK+中，作者將這些信息全部融合到了一起，寫作：

考慮到這些節(jié)點(diǎn)可能在不同子圖里被反復(fù)選擇，造成信息冗余，因此，對(duì)整個(gè)圖而言，是有一個(gè)對(duì)子圖的采樣的，如圖所示：采樣方法包括隨機(jī)采樣（Random Sampling），按照最遠(yuǎn)節(jié)點(diǎn)距離采樣（Farthest Sampling）和最小重疊子圖采樣（Min-set-cover sampling）。

Experiment

實(shí)驗(yàn)方面選用了大規(guī)模的數(shù)據(jù)包括ZINK-12K，CIFAR10，一些來(lái)自O(shè)GB的數(shù)據(jù)包括MolHIV，MolPCBA和一些小規(guī)模數(shù)據(jù)包括MUTAG，TUDataset等。實(shí)驗(yàn)機(jī)器為RTX-A6000。具體為：在大圖上的總體表現(xiàn)為：可以發(fā)現(xiàn)，加入GNN-AK+的方法只要不超計(jì)算資源，基本都能有效提高實(shí)驗(yàn)結(jié)果，如果GNN-AK+都超時(shí)的數(shù)據(jù)，那么其他圖網(wǎng)絡(luò)模型也大概率會(huì)超時(shí)。其運(yùn)算資源上的對(duì)比如下：R表示采樣子圖的個(gè)數(shù)，一般要用的話取3就好了，能在較為有限的時(shí)間和資源里取得較優(yōu)的表現(xiàn)。

另外加一個(gè)小圖上的實(shí)驗(yàn)效果：雖然也是不錯(cuò)，但效果提升沒有大圖數(shù)據(jù)上的明顯。