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