Graph Representation 图神经网络

Graph Representation 图神经网络

图表示学习(representation learning)——图神经网络框架,主要涉及PyG、DGL、Euler、NeuGraph和AliGraph五个框架。除了NeuGraph没有开源外,其它框架都已开源。

 

PyG

DGL

Euler

NeuGraph

AliGraph

Dortmund

NYU

Alibaba

PKU

Alibaba

ICLR workshop’19

ICLR’19

N/A

ATC’19

VLDB’19

2018.5

2018.12

2019.1

2019

2019

Pytorch Geometric (PyG)

PyG在PyTorch上实现,最核心的类是torch_geometric.nn.MessagePassing,用户只需定义消息传递$\phi$(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)\]

进而可表示成gatherscatter的两个过程。

 Graph Representation 图神经网络

 

 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)的,只要底层是深度学习库,都可以灵活支持;支持随机游走和随机采样。

 Graph Representation 图神经网络

 

 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}\]

其中$\phi^e$是消息函数,$\phi^v$是更新函数。

先前的库都需要用户用稀疏矩阵(CSR/COO)存储图,稠密张量存储特征,大量的底层设施会暴露给用户;而DGL底层设施都交由runtime系统进行管理。

深度学习系统最大问题在于没有办法高效表示图数据,而图系统最大的问题在于没法自动微分!

现有用得最广泛的框架是前面两个框架DGLPyG,但(早期版本的)DGL和PyG只是提供了一个编程框架(面向图的消息传递模型),并没有深度解决计算的问题(这很大程度也是GCN很难火起来的原因,因为无法做到很高的可扩展性)。在GCN的原作实现和GraphSAGE的原作实现中,都使用了TensorFlow进行编程,所采用的方法都是简单暴力的矩阵乘,这样其实很大程度忽略了图计算框架这些年取得的成果。因此NeuGraph的出现也正是为了弥合这两者,将图计算与深度学习有机地融合起来。(这也是matrix-based和matrix-free两种方法的对碰。)

NeuGraph把常见的GNN分为三类:图卷积、图循环、图注意力网络。
进而提出了SAGA-NN (Scatter-ApplyEdge-Gather-ApplyVertex with Neural Networks)编程模型,其中SAGA部分属于图计算的消息传递,而两个A则是深度学习神经网络的应用。

 Graph Representation 图神经网络

 

 由于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要做得更好一些,考虑到了采样过程。

 Graph Representation 图神经网络

 

 系统架构从上到下包括应用层、算法层、算子层、采样层和存储层,如下图。

 Graph Representation 图神经网络

 

 Storage Level

  • 图划分:采用了四种方法(METIS、顶点/边割、2D划分、流式划分),由用户自行选择
  • 图属性存储:AliGraph考虑到了图结构(structure)和图属性(attribute)的存储方式,以索引方式并分开两个表存,这就很数据库了(确保第二范式)。也许会牺牲一定的计算时间,但是考虑到数据量过大,同时属性信息千奇百怪,因此这样存储可能是比较合适的。考虑到访问时间的问题,加了两个cache在这,用LRU策略。

 Graph Representation 图神经网络

  • 缓存邻域结点:通过计算一个指标来衡量,选最大指标的那些进行缓存。

 

 

参考链接:

https://www.h5w3.com/128316.html

https://github.com/rusty1s/pytorch_geometric

 

上一篇:Datawhale 图神经网络 Task01简单图论与环境配置与PyG库


下一篇:PHP-电商项目-1