GeniePath，螞蟻金服發表於 KDD 2018，一種可擴展的能夠學習自適應感受路徑的圖神經網路框架。定義在具有排列不變性的圖數據上（permutation invariant graph data）。其自適應路徑層（adaptive path layer）包括兩個互補的功能單元，分別用來進行廣度與深度的探索，前者用來學習一階鄰域節點的權重，後者用來提取和過濾高階鄰域內匯聚的信息。在直推（transductive）和歸納（inductive）兩種學習任務的實驗中，均達到了 state-of-the-art 的效果。

圖表示學習與圖神經網路

圖（Graph），或稱為（網路，Network），是一種由對象（節點，node）和關係（連邊，edge）構成的數據結構。 Graph Neural Networks: A Review of Methods and Applications 生活中很多數據或系統可以被建模成圖，例如社交網路，蛋白質-蛋白質交互網路，疾病傳播網路，知識圖譜等。圖強大到建模和表達能力也吸引了越來越多的學者的關注。與我們熟知的基於格點（2D gird）的圖像數據不同，圖是非歐數據（non-Euclidean data），為了能夠用神經網路進行運算，我們需要先得到節點和連邊的一種向量表示，這項技術被稱為圖表示學習（graph representation learning），或者叫網路嵌入（network embedding），下文不做區分。

受到到自然語言處理中 word2vec Efficient Estimation of Word Representations in Vector Space 的啟發，誕生了 DeepWalk Deepwalk: Online learning ofsocialrepresentations、node2vec node2vec: Scalable feature learning for networks、LINE LINE: Large-scale Information Network Embedding 等網路嵌入演算法，它們的思路是將節點類比為自然語言中的單詞，在圖上生成一些經過隨機遊走（Random Walk）產生的節點序列，把這些序列看成句子。類似於 word2vec 的思想，每個節點都可以用處於其上下文（context）的節點來表示，得到一個長度遠小於圖上節點數的低維稠密的實值向量。該向量編碼了（encode） 圖的結構信息，我們可以利用該向量做節點分類、鏈路預測等下游任務。

需要注意的是，很多人（尤其是做計算機視覺的人）可能對嵌入這項技術並不熟悉。因為圖像天然就是用低維稠密的實值向量來表示的。圖像上，每個像素點都對應一個 RGB 值，每個 RGB 通道都是 [0, 255] 的數。此外，顏色空間有多種，比如 RGB、HSV 等，我們會在不同的任務中選取更適合的顏色表示方式。（用 Photoshop 調過照片的朋友可能會更有體會。）

同樣的道理，嵌入得到的向量化的節點和連邊的表示也是為了圖上的下游任務來服務的。而基於隨機遊走的方法得到的表示信息往往無法針對具體任務進行優化，此外，隨機遊走演算法只能得到圖上的結構信息，而無法融合節點的特徵信息。因此，研究人員又提出了基於神經網路架構的圖表示學習，稱為圖神經網路 Graph Neural Network （GNN）。感興趣的朋友可以閱讀相關的綜述文章。A Gentle Introduction to Graph Neural Network，Graph Neural Networks: A Review of Methods and Applications，A Comprehensive Survey on Graph Neural Networks。這些演算法的基本思路是，針對特定下游任務用端到端 (end-to-end) 的方式進行學習訓練，並且可以融合節點的特徵信息，比如 cora 引文數據集中，節點的結構信息包含了文章的摘要，這對於做節點分類和鏈路預測會起到重要作用。我們知道，在 CNN 中，卷積核所定義的是對圖像上每個像素點與其周圍像素點進行信息交互的方式。同樣，GNN中，每個節點也有領域的概念（由圖的結構信息所定義），圖上的卷積核也是要進行節點和其鄰居的信息交互。這裡，卷積核的大小往往是固定的，受限於運算複雜度，我們一般使用一階或者二階領域。

有代表性的 GNN 演算法包括，GCN Semi-supervised classification with graph convolutional networks, GAT Graph Attention Networks，GraphSAGE Inductive Representation Learning on Large Graphs。此外，開源社區也出現了一些 GNN 的開發框架，其中，PyTorch Geometric (PyG) 基於 PyTorch 實現，熟悉 PyTorch 的人可以很舒服地使用 PyG 進行 GNN 演算法的開發。PyG 提供了一個基礎組件，MessagePassing。它認為像 GCN、GAT、GraphSAGE 等演算法可以抽象為如圖所示的組件。每一層圖卷積層要做的就是和相應領域

內的節點進行信息的交互。不同的演算法的區別在於其所定義的消息的映射方式和領域的選取不用。

可變形卷積核

Deformable Convolutional Networks ，這是一篇有趣的文章，我們以往熟知的卷積核是下圖左上角所示的那種規則形狀的，而這篇文章提出了一種可變形卷積核，它會根據具體的任務和輸入數據而改變卷積核的形狀，也就是感受野。並且在目標檢測任務中取得了比較好的效果。

GeniePath 的作者可能是（論文中沒有提到）受到了這篇文章的啟發，將這個 idea 引入到了 Graph 中。提出了自適應感受野的 GNN 演算法。但是該演算法的並不是通過調整節點的領域來實現的，而將距離多跳（k-hop）的節點的信息存儲在 LSTM 的 memory 中，由神經網路進行學習自動判斷哪些信息對於自己完成下游任務是有利的，而進行提取和過濾。

Permutation Invariant

這裡提到了一個概念，排列不變性（permutation invariant）。這裡[DeepSets: Modeling Permutation Invariance] (inference.vc/deepsets-m) 給出了一個通俗的解釋。

同樣的參數輸入到函數中，它們的排列順序並不影響結果。數據結構——集合（set）會用到這樣的不變性，相應地，那些在建模中用到集合概念的問題都要遵循排列不變性，例如點雲，多主體強化學習，圖片場景中多個目標的集合等。在 DeepMind 文章 Graph Matching Networks for Learning the Similarity of Graph Structured Objects 中也有提到排序不變性。"In the past few years graph neural networks (GNNs) have emerged as an effective class of models for learning representations of structured data and for solving various supervised prediction problems on graphs. Such models are invariant to permutations of graph elements by design and compute graph node representations through a propagation process which iteratively aggregates local structural information. These node representations are then used directly for node classification, or pooled into a graph vector for graph classification. " 本文在演算法部分（Proposed Approaches）詳細介紹了排列不變性。函數空間要滿足圖數據所需要的排列不變性。我們要學的是一個函數 f，將圖 G 映射到嵌入 H。我們要假設的是該 f 具有排列不變性，學習任務與鄰居節點的順序是無關的。文中用下面公式來定義聚合（aggregator）函數 f 的這個性質，其中 sigma 表示的是任意的排列。

。然後提到了一個定理，當且僅當函數 f 可以被分解為

其中 phi 和 rho 是兩個映射。那麼 f 是具有排列不變形的。並且兩個具有排列不變形的函數的複合函數

可以等價於 g(f(x))。也是滿足排列不變性的，因此，我們可以將函數進行堆疊來設計神經網路。GraphSAGE 提供 LSTM 的聚合器，這種聚合器是不具有 Permutation Invariant 的，因為 LSTM 接收的是遍歷節點的隱變數序列，排序是敏感的。此外，這裡的 Permutation Invariant 也指圖是靜態的，不隨時間演化。 因為文章中提到 「This is in opposition to temporal graphs.」

GeniePath Algorithm

Adaptive Path Layer 是文章的核心內容，相比其他演算法中使用事先定義好的路徑（pre-defined paths），例如一階鄰居等，Adaptive Path Layer 目標是自學習感受路徑，信號在學到的路徑上傳播。這個問題可以等效於學習每個節點的一個合理的子圖，該子圖包括兩部分，廣度方向上給出一階鄰居中節點的權重，深度方向上 t 跳範圍內重要的鄰居。自適應廣度函數定義為

其中 theta 代表參數。H 代表的是節點的嵌入（或者叫隱狀態表示）。自適應深度函數定義為，

其中，Phi 代表參數。

我們可以將本文和 GAT 或者 GraphSAGE 等常用的非頻域的 GNN 框架的區別認為是在它們的基礎上加了 memory（通過 LSTM 實現）。存儲通過一階鄰域進行的信息傳遞得到的高階領域節點的信息。所謂的自適應，自學習，其實就是通過 LSTM 的門對 LSTM 的 memory 所存儲的高階領域信息的提取和過濾 （分別對應遺忘門和輸出門）所體現的。而一階鄰域和高階領域的信息交互體現在 LSTM 的輸入門。

注意，廣度函數的輸出的 H 上標是 tmp，只有將 H_tmp 再輸入到深度函數中，才達到一個 epoch 的訓練。

本質來講，這裡是一個去掉了 multi-head 機制的 GAT。

自適應深度函數，本質上就是一個 LSTM，並且這裡並沒有依賴傳統 LSTM 的循環輸入，而是只有一次輸入。主要利用的是它的存儲。其中最重要的公式是最後一個，輸出的節點的表示等於存儲於 LSTM memory C 的信息和提取和過濾。而提取和過濾的控制是由廣度函數的輸入決定的。

論文僅給出了 Adaptive Path Layer，而沒有模型的結構圖。這裡根據對文章的理解畫出神經網路框架。文章提出兩個框架，一個是直接將 Adaptive Path Layer 循環 T 次，那麼將 t-hop 的節點信息的交互可以融合起來。另一個是 GeniePath-lazy，區別在在於先只過廣度函數，得到

，再整體輸入到深度函數中。

下面列出文中使用的數據信息。

下面是文章給出的實驗結果，對比的演算法包括 MLP，node2vec，以及幾個經典的 GCN 演算法。其中 MLP 輸入的僅是節點的特徵信息，無法利用圖結構信息。而 node2vec 輸入的僅是圖結構信息，無法利用節點的特徵信息。

我們能看到 GeniePath 在蛋白質交互網路數據 PPI 上的表現顯著強於其他演算法，我猜想其中的原因與 PPI 的數據特點有關。在文章 Link Prediction Based on Graph Neural Networks 有這樣一段話。「the common neighbor heuristic assumes that two nodes are more likely to connect if they have many common neighbors. This assumption may be correct in social networks, but is shown to fail in protein-protein interaction (PPI) networks --two proteins sharing many common neighbors are actually less likely to interact」 ，一般情況下，我們會假設兩個節點有更多的共同鄰居，它們會傾向於更加相似，但是在蛋白質中，如果兩個蛋白質有越多的共同節點，它們更傾向於不發生反應。GeniePath 通過 LSTM 組件融合了圖中的高階鄰居信息，使得得到更高的準確率。

GeniePath 的 PyTorch 復現，已發到 https://shawnwang.tech github.com/shawnwang-te 感興趣的朋友可以關注。


推薦閱讀：
相关文章