作者丨紀(jì)厚業(yè)
學(xué)校丨北京郵電大學(xué)博士生
研究方向丨異質(zhì)圖神經(jīng)網(wǎng)絡(luò)及其應(yīng)用
引言
圖神經(jīng)網(wǎng)絡(luò)（Graph Neural Network）已經(jīng)成為深度學(xué)習(xí)領(lǐng)域最熱?的方向之一。作為經(jīng)典的 Message-passing 模型，圖神經(jīng)網(wǎng)絡(luò)通常包含兩步:從鄰居節(jié)點(diǎn)收集消息 message，然后利用神經(jīng)網(wǎng)絡(luò)來(lái)更新節(jié)點(diǎn)表示。但是 Message-passing 模型有兩個(gè)基礎(chǔ)性的問(wèn)題：
1. 丟失了節(jié)點(diǎn)與其鄰居間的結(jié)構(gòu)信息：
2. 無(wú)法捕獲節(jié)點(diǎn)之間的?距離依賴關(guān)系：
大多數(shù) MPNNs 僅僅聚合 k 跳內(nèi)的節(jié)點(diǎn)鄰居消息來(lái)更新節(jié)點(diǎn)表示。但是，圖上兩個(gè)節(jié)點(diǎn)可能具有相似的結(jié)構(gòu)（社區(qū)中心、橋節(jié)點(diǎn)），即使他們的距離很遠(yuǎn)；
可能的解法是將現(xiàn)有的 GNN 堆疊多層，但是這可能帶來(lái)過(guò)平滑問(wèn)題。
針對(duì)上述問(wèn)題，本文提出了一種 geometric aggregation scheme，其核心思想是：將節(jié)點(diǎn)映射為連續(xù)空間的一個(gè)向量（graph embedding），在隱空間查找鄰居并進(jìn)行聚合。
本文的主要貢獻(xiàn)：
提出了一種 geometric aggregation scheme，其可以同時(shí)在真實(shí)圖結(jié)構(gòu)/隱空間來(lái)聚合信息來(lái)克服 MPNNs 兩個(gè)基礎(chǔ)性缺陷；
提出了一種基于 geometric aggregation scheme 的圖神經(jīng)網(wǎng)絡(luò) Geom-GCN；
實(shí)驗(yàn)驗(yàn)證了模型的效果。
模型
Geometric Aggregation Scheme 如下圖所示，Geometric aggregation scheme 主要包含 3 個(gè)部分：node embedding (panel A1-A3)，structural neighborhood (panel B) 和 bi-level aggregation (panel C)。
A1->A2：利用 graph embedding 技術(shù)將圖上的節(jié)點(diǎn)（如節(jié)點(diǎn) v）映射為隱空間一個(gè)向量表示 
。 A2->B1：針對(duì)某一個(gè)節(jié)點(diǎn) v（參看 B2 中的紅色節(jié)點(diǎn)）周?chē)囊粋€(gè)子圖，我們可以找到該節(jié)點(diǎn)的一些鄰居 
。B2：圓形虛線（半徑為 ρ）內(nèi)的節(jié)點(diǎn)代表了紅色節(jié)點(diǎn)在隱空間的鄰居：
圓形虛線外的節(jié)點(diǎn)代表了節(jié)點(diǎn)在原始圖上的真實(shí)鄰居 
。既然節(jié)點(diǎn)已經(jīng)表示為向量，那么不同節(jié)點(diǎn)之間就有相對(duì)關(guān)系。在 B2 的 3x3 網(wǎng)格內(nèi)，不同節(jié)點(diǎn)相對(duì)于紅色節(jié)點(diǎn)有 9 種相對(duì)位置關(guān)系 
，關(guān)系映射函數(shù)為 
。B3：基于 Bi-level aggregation 來(lái)聚合鄰居 N(v) 的信息并更新節(jié)點(diǎn)的表示。Low-level aggregation p：聚合節(jié)點(diǎn) v 在某個(gè)關(guān)系 r 下的鄰居的信息。這里用一個(gè)虛擬節(jié)點(diǎn)的概念來(lái)表示。
High-level aggregation q：聚合節(jié)點(diǎn)在多種關(guān)系 R 下的鄰居的信息。
Non-linear transform：非線性變化一下。
其中， 是節(jié)點(diǎn) v 在第 l 層 GNN 的表示。這里本質(zhì)上：先針對(duì)一種關(guān)系 r 來(lái)學(xué)習(xí)節(jié)點(diǎn)表示，然后再對(duì)多個(gè)關(guān)系下的表示進(jìn)行融合。Geom-GCN: An implementation of the scheme這里將上一節(jié)中很抽象的 Low-level aggregation p 和 High-level aggregation q 以及關(guān)系映射函數(shù) τ。給出了具體的形式：關(guān)系映射函數(shù) τ 考慮了 4 種不同的位置關(guān)系。
Low-level aggregation p 其實(shí)就是 GCN 中的平均操作。
High-level aggregation q 本質(zhì)就是拼接操作。
How to distinguish the non-isomorphic graphs once structural neighborhood本文 argue 之前的工作沒(méi)能較好的對(duì)結(jié)構(gòu)信息進(jìn)行描述，這里給了一個(gè) case study 來(lái)說(shuō)明 Geom-GCN 的優(yōu)越性。
假設(shè)所有節(jié)點(diǎn)的特征都是 a。針對(duì)節(jié)點(diǎn) 來(lái)說(shuō)，其鄰居分別為 和 。假設(shè)采用 mean 或者 maximum 的 aggregator。
則兩種結(jié)構(gòu)無(wú)法區(qū)分。本文的映射函數(shù) ：
更多關(guān)于 GNN 表示能力的論文參?：19 ICLR GIN How Powerful are Graph Neural Networks。實(shí)驗(yàn)
本文主要對(duì)比了 GCN 和 GAT，數(shù)據(jù)集?下表：
不同數(shù)據(jù)集的 homophily 可以用下式衡量。
本文為 Geom-GCN 選取了 3 種 graph embedding 方法：
實(shí)驗(yàn)結(jié)果?下表：
作者又進(jìn)一步測(cè)試了兩個(gè)變種：
結(jié)果?下圖：
可以看出：隱空間鄰居對(duì) β 較小的圖貢獻(xiàn)更大。
然后，作者測(cè)試了不同 embedding 方法在選取鄰居上對(duì)實(shí)驗(yàn)結(jié)果的影響。
可以看出：這里并沒(méi)有一個(gè)通用的較好 embedding 方法。需要根據(jù)數(shù)據(jù)集來(lái)設(shè)置，如何自動(dòng)的找到最合適的 embedding 方法是一個(gè) feature work。最后是時(shí)間復(fù)雜度分析。本文考慮了多種不同的關(guān)系，因此，Geom-GCN 的時(shí)間復(fù)雜度是 GCN 的 2|R| 倍。另外，和 GAT 的實(shí)際運(yùn)行時(shí)間相差無(wú)幾，因?yàn)?attention 的計(jì)算通常很耗時(shí)。
總結(jié)
本文針對(duì) MPNNs 的兩個(gè)基礎(chǔ)性缺陷設(shè)計(jì)了Geom-GCN 來(lái)更好地捕獲結(jié)構(gòu)信息和?距離依賴。實(shí)驗(yàn)結(jié)果驗(yàn)證了 Geom-GCN 的有效性。但是本文并不是一個(gè) end-to-end 的框架，有很多地方需要手動(dòng)選擇設(shè)計(jì)。
