2018/12/31 11:40

北大、微软提出NGra：高效大规模图神经网络计算

目前，深度学习技术通常以深度神经网络（DNN）的形式展现。由于其在语音、视觉和自然语言处理等领域所取得的成功，深度学习技术越来越受欢迎。在这些领域中，底层数据表征的坐标通常具有规则的网格结构，这有利于包含大量类似于单指令多数据流（SIMD）数据并行运算的硬件加速机制（例如 GPU）。目前，将深度学习模型应用在具有不规则图结构的数据上成为了一种新兴的趋势 [9, 22, 25, 13, 15, 4, 5, 29]，这种趋势是由诸如社交网络、知识图谱、以及生物信息学和神经科学（例如，蛋白质之间的交互或大脑中的神经元连接）中的图形的重要性所驱动的。这种趋势也促使人们在其目标应用（例如，分类、嵌入、问答系统）上取得了当前最佳的结果。这些基于图的神经网络（GNN）通常将神经网络模型应用在图中与顶点和边相关的特征上，传播运算结果并进行聚合，从而生成下一级的特征。

现有的解决方案都不能很好地支持 GNN。现有的图处理引擎 [28，26，11，6，41] 往往会提供一个类似于信息收集（Gather）——应用（Apply））——结果分发（Scatter）的 GAS 顶点程序模型，但这种方式无法在图结构中表达和支持神经网络架构。TensorFlow[3]、PyTorch[2]、MxNet[8]、CNTK[42] 等深度学习框架旨在将神经网络表示为数据流图，但并不直接支持图传播模型。此外，它们都不能提供处理大型图所需的可扩展性，也不支持基于 GPU 的图传播 operator（将图传播转换为稀疏操作）的高效实现。当前缺乏对这些需求的支持严重限制了充分挖掘大规模 GNN 潜力的能力，同时也为 DNN 与大型图结构的结合在系统层面上提出了巨大的挑战。

在本文中，作者介绍了首次实现支持大规模 GNN 的 NGra 系统，它从一个易于表达的编程模型发展到一个可扩展的、高效 GPU 并行处理引擎。NGra 将数据流与顶点程序的抽象自然地结合在了一个名为 SAGA-NN（Scatter-Apply Edge Gather-Apply Vertex with Neural Networks）的新模型中。SAGA 可以被认为是一个 GAS 模型的变体，SAGA-NN 模型中由用户定义的函数使用户能够通过使用数据流抽象（而不是使用那些为处理传统图问题如 PageRank、连通分量、最短路径而设计的算法）在顶点或边数据（以张量形式被处理）上表达神经网络计算。

与在深度神经网络上的情况一样，高效使用 GPU 对 GNN 的性能至关重要，而且由于处理大型图结构的额外挑战，对 GPU 的使用就显得更为关键了。为了实现超越 GPU 物理限制的可扩展性，NGra 显式地将图结构划分（顶点和边数据）成块，将一个在 SAGA-NN 模型中表达的 GNN 算法转成了具有块粒度 operator 的数据流图，通过该数据流图，作者可以在单个或多个 GPU 上进行基于块的并行流处理。

然后，NGra 引擎的效率在很大程度上取决于 NGra 如何管理和调度并行流的处理过程，以及如何在 GPU 上实现关键的图传播 operator（结果分发和信息收集）。NGra 十分关注数据的位置，从而尽量减少 GPU 内存内外的数据交换，最大限度地提高 GPU 内存中数据块的重用性，同时以流形式同时进行数据迁移和计算。对于多 GPU 的情况，它使用了一种基于环的流机制，通过在 GPU 之间直接交换数据块来避免主机内存中的冗余数据迁移。SAGA-NN 模型中的结果分发和信息收集阶段执行沿着边的顶点数据传播，在稀疏结构上表现为矩阵乘法。众所周知，在像 GPU 这样数据并行的硬件上执行稀疏的矩阵操作是非常困难的。因此，NGra 将图传播引擎支持的特殊 operator 引入到数据流图中，并优化其在 GPU 上的执行。请注意，与其基于 GPU 的图引擎所关注的传统图处理场景不同，在 GNN 的场景下，由于每个顶点的数据可能就是一个特征向量，而不是简单的标量，可变顶点数据本身可能无法被容纳到 GPU 设备内存中。因此，本文的方案更倾向于利用每个顶点数据访问中的并行性来提高内存访问效率。

作者使用顶点程序抽象和用于图传播过程的自定义 operater 对 TensorFlow 进行扩展，从而实现 NGra。结果证明 NGra 可以被扩展，然后通过利用单个服务器的主机内存和 GPU 的计算能力，实现在（包含数百万顶点和数百特征维度以及数亿边的）大型图上对 GNN 算法的支持，而这不能直接通过使用现有的深度学习框架实现。与可以通过 GPU 支持的小型图上的 TensorFlow 相比，NGra 可以取得大约 4 倍的运算加速。作者还对 NGra 中的多个优化所带来的性能提升进行了广泛的评估，以证明它们的有效性。

图 1：双层 GNN 的前馈运算过程

图 3：GNN 中每一层的 SAGA-NN 运算流程

NGra 系统

NGra 以用户接口的形式提供了数据流和定点程序抽象的组合。在这种抽象之下，NGra 主要由以下几部分组成：（1）一个将 SAGA-NN 模型中实现的算法转换为块粒度数据流图的前端，它使得大型图上的 GNN 计算可以在 GPU 中被实现；（2）一个制定最小化主机与 GPU 设备内存之间数据迁移调度策略的优化层，它能够找到进行融合操作和去除冗余计算的机会；（3）一组高效的传播操作内核，它支持针对 GPU 中重复的数据迁移和计算的基于流的处理；（4）在运行时执行数据流。由于 NGra 在很大程度上利用了现有的基于数据流的深度学习框架来实现在运行时执行数据流，因此作者将重点放在本节前三个框架的设计上，因为它们是 NGra 系统的主要贡献。

图 4：用于 G-GCN 层上目标区间 V0 的基于块的数据流图。为了得到更清晰的可视化结果，在连接到 D2H 时，SAG 阶段输出张量置换被隐藏在了 SAG 的子图中。

图 13：TensorFlow（TF），cuSPARSE，以及 NGra（NG）在不同密度的图上传播内核的时间。

图 16：在大型图上的不同应用中使用 NGra 的加速情况

论文：Towards Efficient Large-Scale Graph Neural Network Computing

论文地址：https://arxiv.org/abs/1810.08403

最近的深度学习模型已经从低维的常规网格（如图像、视频和语音）发展到了高维的图结构数据（如社交网络、大脑连接和知识图谱）上。这种演进催生了基于大型图的不规则和稀疏模型，这些模型超出了现有深度学习框架的设计范围。此外，这些模型不容易适应在并行硬件（如 GPU）上的有效大规模加速。

本文介绍了基于图的深度神经网络（GNN）的第一个并行处理框架 NGra。NGra 提出了一种新的 SAGA-NN 模型，用于将深度神经网络表示为顶点程序，其每一层都具有定义好的（结果分发、应用边、信息收集、应用顶点）图操作阶段。该模型不仅可以直观地表示 GNN，而且便于映射到高效的数据流表示。NGra 通过自动图形划分和基于块的流处理（使用 GPU 核心或多个 GPU），显式地解决了可扩展性的挑战，它仔细考虑了数据位置、并行处理和数据迁移的重叠等问题。NGra 虽然是稀疏的，但通过对 GPU 上的结果分发/信息收集 operator 进行高度优化，进一步提高了效率。本文的评估结果表明，NGra 可以扩展到任何现有框架都无法直接处理的大型真实图结构上，同时即使是在小规模的 TensorFlow 的多基线设计上，也可以实现高达 4 倍的加速。

理论图神经网络北大微软亚洲研究院NGra

相关数据

深度学习技术

深度学习（deep learning）是机器学习的分支，是一种试图使用包含复杂结构或由多重非线性变换构成的多个处理层对数据进行高层抽象的算法。深度学习是机器学习中一种基于对数据进行表征学习的算法，至今已有数种深度学习框架，如卷积神经网络和深度置信网络和递归神经网络等已被应用在计算机视觉、语音识别、自然语言处理、音频识别与生物信息学等领域并获取了极好的效果。

来源：LeCun, Y., Bengio, Y., & Hinton, G. (2015). Deep learning. nature, 521(7553), 436.

调度技术

调度在计算机中是分配工作所需资源的方法。资源可以指虚拟的计算资源，如线程、进程或数据流；也可以指硬件资源，如处理器、网络连接或扩展卡。进行调度工作的程序叫做调度器。调度器通常的实现使得所有计算资源都处于忙碌状态，允许多位用户有效地同时共享系统资源，或达到指定的服务质量。 see planning for more details

来源：维基百科

神经科学技术

神经科学，又称神经生物学，是专门研究神经系统的结构、功能、发育、演化、遗传学、生物化学、生理学、药理学及病理学的一门科学。对行为及学习的研究都是神经科学的分支。对人脑研究是个跨领域的范畴，当中涉及分子层面、细胞层面、神经小组、大型神经系统，如视觉神经系统、脑干、脑皮层。

来源：维基百科

TensorFlow技术

TensorFlow是一个开源软件库，用于各种感知和语言理解任务的机器学习。目前被50个团队用于研究和生产许多Google商业产品，如语音识别、Gmail、Google 相册和搜索，其中许多产品曾使用过其前任软件DistBelief。

来源：维基百科

张量技术

张量是一个可用来表示在一些矢量、标量和其他张量之间的线性关系的多线性函数，这些线性关系的基本例子有内积、外积、线性映射以及笛卡儿积。其坐标在维空间内，有个分量的一种量，其中每个分量都是坐标的函数，而在坐标变换时，这些分量也依照某些规则作线性变换。称为该张量的秩或阶（与矩阵的秩和阶均无关系）。在数学里，张量是一种几何实体，或者说广义上的“数量”。张量概念包括标量、矢量和线性算子。张量可以用坐标系统来表达，记作标量的数组，但它是定义为“不依赖于参照系的选择的”。张量在物理和工程学中很重要。例如在扩散张量成像中，表达器官对于水的在各个方向的微分透性的张量可以用来产生大脑的扫描图。工程上最重要的例子可能就是应力张量和应变张量了，它们都是二阶张量，对于一般线性材料他们之间的关系由一个四阶弹性张量来决定。

来源：维基百科

知识图谱技术

知识图谱本质上是语义网络，是一种基于图的数据结构，由节点(Point)和边(Edge)组成。在知识图谱里，每个节点表示现实世界中存在的“实体”，每条边为实体与实体之间的“关系”。知识图谱是关系的最有效的表示方式。通俗地讲，知识图谱就是把所有不同种类的信息（Heterogeneous Information）连接在一起而得到的一个关系网络。知识图谱提供了从“关系”的角度去分析问题的能力。知识图谱这个概念最早由Google提出，主要是用来优化现有的搜索引擎。不同于基于关键词搜索的传统搜索引擎，知识图谱可用来更好地查询复杂的关联信息，从语义层面理解用户意图，改进搜索质量。比如在Google的搜索框里输入Bill Gates的时候，搜索结果页面的右侧还会出现Bill Gates相关的信息比如出生年月，家庭情况等等。

来源：机器之心

神经网络技术

（人工）神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型，那时候研究者构想了「感知器（perceptron）」的想法。这一领域的研究者通常被称为「联结主义者（Connectionist）」，因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型，它们都是前馈神经网络：卷积神经网络（CNN）和循环神经网络（RNN），其中 RNN 又包含长短期记忆（LSTM）、门控循环单元（GRU）等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习，但也有一些为无监督学习设计的变体，比如自动编码器和生成对抗网络（GAN）。

来源：机器之心

映射技术

映射指的是具有某种特殊结构的函数，或泛指类函数思想的范畴论中的态射。逻辑和图论中也有一些不太常规的用法。其数学定义为：两个非空集合A与B间存在着对应关系f，而且对于A中的每一个元素x，B中总有有唯一的一个元素y与它对应，就这种对应为从A到B的映射，记作f：A→B。其中，y称为元素x在映射f下的象，记作：y=f(x)。x称为y关于映射f的原象*。*集合A中所有元素的象的集合称为映射f的值域，记作f(A)。同样的，在机器学习中，映射就是输入与输出之间的对应关系。

来源：Wikipedia

神经元技术

（人工）神经元是一个类比于生物神经元的数学计算模型，是神经网络的基本组成单元。对于生物神经网络，每个神经元与其他神经元相连，当它“兴奋”时会向相连的神经元发送化学物质，从而改变这些神经元的电位；神经元的“兴奋”由其电位决定，当它的电位超过一个“阈值”（threshold）便会被激活，亦即“兴奋”。目前最常见的神经元模型是基于1943年 Warren McCulloch 和 Walter Pitts提出的“M-P 神经元模型”。在这个模型中，神经元通过带权重的连接接处理来自n个其他神经元的输入信号，其总输入值将与神经元的阈值进行比较，最后通过“激活函数”（activation function）产生神经元的输出。

来源：Overview of Artificial Neural Networks and its Applications. (2018). medium.com.

数据迁移技术

数据迁移(又称分级存储管理，hierarchical storage management，hsm)是一种将离线存储与在线存储融合的技术。它将高速、高容量的非在线存储设备作为磁盘设备的下一级设备，然后将磁盘中常用的数据按指定的策略自动迁移到磁带库（简称带库）等二级大容量存储设备上。当需要使用这些数据时，分级存储系统会自动将这些数据从下一级存储设备调回到上一级磁盘上。对于用户来说，上述数据迁移操作完全是透明的，只是在访问磁盘的速度上略有怠慢，而在逻辑磁盘的容量上明显感觉大大提高了。

来源：百度百科

自然语言处理技术

自然语言处理（英语：natural language processing，缩写作 NLP）是人工智能和语言学领域的分支学科。此领域探讨如何处理及运用自然语言；自然语言认知则是指让电脑“懂”人类的语言。自然语言生成系统把计算机数据转化为自然语言。自然语言理解系统把自然语言转化为计算机程序更易于处理的形式。

来源：维基百科

深度神经网络技术

深度神经网络（DNN）是深度学习的一种框架，它是一种具备至少一个隐层的神经网络。与浅层神经网络类似，深度神经网络也能够为复杂非线性系统提供建模，但多出的层次为模型提供了更高的抽象层次，因而提高了模型的能力。

来源：机器之心 Techopedia

问答系统技术

问答系统是未来自然语言处理的明日之星。问答系统外部的行为上来看，其与目前主流资讯检索技术有两点不同：首先是查询方式为完整而口语化的问句，再来则是其回传的为高精准度网页结果或明确的答案字串。以Ask Jeeves为例，使用者不需要思考该使用什么样的问法才能够得到理想的答案，只需要用口语化的方式直接提问如“请问谁是美国总统？”即可。而系统在了解使用者问句后，会非常清楚地回答“奥巴马是美国总统”。面对这种系统，使用者不需要费心去一一检视搜索引擎回传的网页，对于资讯检索的效率与资讯的普及都有很大帮助。从系统内部来看，问答系统使用了大量有别于传统资讯检索系统自然语言处理技术，如自然语言剖析（Natural Language Parsing）、问题分类（Question Classification）、专名辨识（Named Entity Recognition）等等。少数系统甚至会使用复杂的逻辑推理机制，来区隔出需要推理机制才能够区隔出来的答案。在系统所使用的资料上，除了传统资讯检索会使用到的资料外（如字典），问答系统还会使用本体论等语义资料，或者利用网页来增加资料的丰富性。

来源：维基百科