Graph Representation 圖神經網絡
圖表示學習(representation learning)——圖神經網絡框架，主要涉及PyG、DGL、Euler、NeuGraph和AliGraph五個框架。除了NeuGraph沒有開源外，其它框架都已開源。

Pytorch Geometric (PyG)
PyG在PyTorch上實現，最核心的類是torch_geometric.nn.MessagePassing，用戶只需定義消息傳遞$?$（message()）、更新函數$\gamma$（update()）和聚合函數$Agg$即可。
GCN的傳播規則用向量可表成
[\mathbf{x}i^{(k)} = \sum{j \in \mathcal{N}(i) \cup { i }} \frac{1}{\sqrt{\deg(i)} \cdot \sqrt{\deg(j)}} \cdot \left( \mathbf{\Theta} \cdot \mathbf{x}_j^{(k-1)} \right)]
進而可表示成gather和scatter的兩個過程。

PyTorch Geometric 使實現圖神經網絡變得簡單。例如，edge convolutional layer實現邊緣卷積層：
import torch
from torch.nn import Sequential as Seq, Linear as Lin, ReLU
from torch_geometric.nn import MessagePassing

class EdgeConv(MessagePassing):
def init(self, F_in, F_out):
super(EdgeConv, self).init(aggr=‘max’) # “Max” aggregation.
self.mlp = Seq(Lin(2 * F_in, F_out), ReLU(), Lin(F_out, F_out))

def forward(self, x, edge_index):# x has shape [N, F_in]# edge_index has shape [2, E]return self.propagate(edge_index, x=x)  # shape [N, F_out]def message(self, x_i, x_j):# x_i has shape [E, F_in]# x_j has shape [E, F_in]edge_features = torch.cat([x_i, x_j - x_i], dim=1)  # shape [E, 2 * F_in]return self.mlp(edge_features)  # shape [E, F_out]

Deep Graph Library (DGL)
DGL和PyG都是目前運用得最廣泛的圖神經網絡庫，原理都差不多，但各有優劣。比如DGL是無關平臺(platform-agnostic)的，只要底層是深度學習庫，都可以靈活支持；支持隨機游走和隨機采樣。

DGL將消息傳遞的式子拆分成對邊應用(edge-wise)和對結點應用(node-wise)
[\begin{cases}
\mathbf{m}_i^{(k+1)} = \phi^{e\left(\mathbf{v}_i}{(k)},\mathbf{v}_j^{{(k)},\mathbf{e}_{j,i}}{(k)}\right)\\
\mathbf{v}i^{(k+1)} = \phi^{v\left(\mathbf{v}_i}{(k)},\mathop{Agg}{j\in\mathcal{N}_i}\mathbf{m}_i^{(k+1)}\right)
\end{cases}]
其中${?}^e$是消息函數，${?}^v$是更新函數。
先前的庫都需要用戶用稀疏矩陣(CSR/COO)存儲圖，稠密張量存儲特征，大量的底層設施會暴露給用戶；而DGL底層設施都交由runtime系統進行管理。
深度學習系統最大問題在于沒有辦法高效表示圖數據，而圖系統最大的問題在于沒法自動微分！
現有用得最廣泛的框架是前面兩個框架DGL和PyG，但（早期版本的）DGL和PyG只是提供了一個編程框架（面向圖的消息傳遞模型），并沒有深度解決計算的問題（這很大程度也是GCN很難火起來的原因，因為無法做到很高的可擴展性）。在GCN的原作實現和GraphSAGE的原作實現中，都使用了TensorFlow進行編程，所采用的方法都是簡單暴力的矩陣乘，這樣其實很大程度忽略了圖計算框架這些年取得的成果。因此NeuGraph的出現也正是為了彌合這兩者，將圖計算與深度學習有機地融合起來。（這也是matrix-based和matrix-free兩種方法的對碰。）
NeuGraph把常見的GNN分為三類：圖卷積、圖循環、圖注意力網絡。
進而提出了SAGA-NN (Scatter-ApplyEdge-Gather-ApplyVertex with Neural Networks)編程模型，其中SAGA部分屬于圖計算的消息傳遞，而兩個A則是深度學習神經網絡的應用。

由于GCN相比起傳統的圖算法（在圖計算層面上）要簡單很多，就是對全圖不斷進行遍歷，因此Scatter和Gather是確定的，而兩個Apply階段則是用戶自定義的函數。（所以似乎NeuGraph沒法實現GraphSAGE，因為GraphSAGE的鄰域是由一定策略采樣出來的，而不是取全部鄰域）。
GPU Execution
目前的深度學習框架都很難處理大圖，因為GPU的內存無法存儲這么大規模的圖，因此NeuGraph在數據流抽象的基礎上進行了圖劃分。
（關于計算硬件，這里是值得考慮的。GPU在稠密矩陣計算上具有先天優勢，但如果換成稀疏陣優勢是否還存在呢。圖處理框架的發展證明了CPU集群有辦法承擔大規模的圖計算任務，從這種角度來看的話是否CPU在GNN的處理上也更存在優勢呢？或者更加激進地，利用FPGA實現這樣既能高效遍歷又能高效算矩陣的架構是否有辦法呢？）
按邊劃分為chunk（準確來說是把鄰接矩陣按列劃分），然后送到不同的GPU上進行計算，優化方法(streaming out of GPU core)：
? 使用selective scheduling，先用CPU篩一遍有用的邊，再把這些邊送去GPU算
? 為了確保足夠的局部性，采用了Kernighan-Lin算法進行圖劃分（METIS包），確保同一個chunk中的大部分邊都連向同一個節點
? 用pipeline scheduling最大程度重疊IO和計算時間
AliGraph
AliGraph是Alibaba內部的圖計算系統，已經商用在淘寶各種預測任務上，并且取得了很好的效果。
提出目前GNN面臨著四個問題：大規模、異構、屬性、動態圖。
關于GNN的抽象，AliGraph就比NeuGraph要做得更好一些，考慮到了采樣過程。

系統架構從上到下包括應用層、算法層、算子層、采樣層和存儲層，如下圖。

Storage Level
? 圖劃分：采用了四種方法（METIS、頂點/邊割、2D劃分、流式劃分），由用戶自行選擇
? 圖屬性存儲：AliGraph考慮到了圖結構(structure)和圖屬性(attribute)的存儲方式，以索引方式并分開兩個表存，這就很數據庫了（確保第二范式）。也許會犧牲一定的計算時間，但是考慮到數據量過大，同時屬性信息千奇百怪，因此這樣存儲可能是比較合適的。考慮到訪問時間的問題，加了兩個cache在這，用LRU策略。

? 緩存鄰域結點：通過計算一個指標來衡量，選最大指標的那些進行緩存。

參考鏈接：
https://www.h5w3.com/128316.html
https://github.com/rusty1s/pytorch_geometric

總結

以上是生活随笔為你收集整理的Graph Representation 图神经网络的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。