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