英语原文共 15 页

FASTGCN：基于重要SAMPLI的图卷积网络快速学习

Jie Chenlowast;

, Tengfei Malowast;

, Cao XiaoIBM Researchchenjie@us.ibm.com, Tengfei.Ma1@ibm.com, cxiao@us.ibm.

摘要

Kipf和Wling最近提出的图卷积网络(GCN)是一种有效的半监督学习图模型。然而，这个模型最初是设计用来学习的。 培训和测试数据的存在。此外，跨层的递归邻域扩展为使用大而密集的图进行训练带来了时间和记忆方面的挑战。放宽要求 在测试数据同时可用的情况下，我们将图卷积解释为概率测度下嵌入函数的积分变换。这样的解释允许使用蒙特卡洛方法一致地估计积分，这反过来导致了一个批处理的培训方案，正如我们在这项工作中提出的-FastGCN。随着重要抽样的加强，FastGCN不仅训练效率高，对推理也有很好的推广作用。与GCN及相关模型相比，我们进行了一组综合实验，证明了该方法的有效性。特别地，是数量级更有效的，而预测仍然是相当准确的。

1. 介绍

图是两两关系的通用表示。许多真实世界的数据自然以图表的形式出现；例如，社会网络、基因表达网络和知识图。进位 以图表为基础的学习任务，如节点分类和链路预测的性能，最近做出了很大的努力来扩展完善的网络体系结构，包括经常性的网络结构。 NeuralNetworks(RNN)andConvolutionalNeuralNetworks(CNN)，ToGraphData;see,E.gine,Bruna等人(2013年)；Duvenaud等人(2015年)；Li等人(2015年)；Jain等人(2015年)；Henaff等人(2015年)；Nieper等人(2016年)；Kipfamp;Wling(2016年a；b)。虽然学习图的特征表示是这项工作中的一个重要课题，但在这里，我们重点讨论了图的特征表示。 在这方面，应用卷积结构的最接近的工作是图卷积网络(GCN)(Kipfamp;Wling，2016 a；b)。借鉴图像卷积滤波器的概念 GCN使用图的连通性结构作为滤波器来执行邻域混合。该体系结构可以通过以下Express来优雅地概括：

其中，At是图邻接矩阵的一些标准化，H(L)包含Lth层中的图形顶点的嵌入(RowWise)，W(L)是参数矩阵，并且其是非线性。如同 许多图论算法，邻接矩阵对训练和测试数据的成对关系进行编码。对两个数据同时进行模型的学习以及嵌入。 至少正如作者所建议的那样。然而，对于许多应用，测试数据可能不容易获得，因为图可以不断地与新的顶点(例如，新的A成员)扩展。 推荐系统的新产品和用于功能测试的新药)。这样的场景需要一个只从一组训练顶点学习模型的归纳方案，并且 很好地推广到图的任何扩充。

对于GCN的更严重的挑战是，跨层的邻域的递归扩展导致批量训练中的昂贵计算。特别是对于稠密图和幂律图, 单个顶点的邻域展开很快就填满了图的很大一部分。然后，通常的小批量培训将涉及到每批的大量数据，即使是小批量的数据。因此，要使GCN适用于大型、密集的图，可伸缩性是一个迫切需要解决的问题。

为了解决这两方面的挑战，我们提出从不同的角度来看待图的卷积，并将它们解释为概率测度下嵌入函数的积分变换这种观点为归纳学习提供了一种原则性的机制，从损失的形成到梯度的随机形式。特别地，特别地，我们解释了图的顶点是某些概率分布的iid样本，并将损失和每个卷积层写成关于顶点嵌入函数的积分。 然后，利用蒙特卡罗近似对积分进行求值，确定了样本损耗和样本梯度。以进一步改变抽样分布(如重要性抽样)以减小近似方差。 所提出的FastGCN方法不仅克服了对测试数据的依赖，而且为每批计算带来了可控的成本。在撰写本报告时，我们注意到一个新出版的w Ork GraphSAGE(Hamilton等人，2017年)，也建议使用抽样来减少GCN的计算足迹。 我们的抽样方案更经济，从而大大节省了梯度计算，将在3.3节中进行更详细的分析。第四部分的实验结果 ， FastGCN的每批计算比GraphSAGE快一个数量级以上，而分类精度具有很高的可比性。

2.相关工作

在过去的几年里，出现了一些基于图形的卷积网络模型，用于解决图结构数据的应用，例如分子的表示(Duvenaud等人，2015年)。 一个重要的工作流程建立在光谱图论的基础上(Bruna等人，2013年；Henaff等人，2015年；Defferrard等人，2016年)。它们在光谱域中定义了参数化滤波器，其灵感来源于 图傅里叶变换这些方法学习了整个图的特征表示，并可用于图形分类。

另一种工作是学习图顶点的嵌入。 ICHGOYALamp;Ferrara（2017）是最近一项调查，涵盖了几个类别的方法。另一条工作线学习图形顶点的嵌入，Goyalamp;Ferrara(2017)是最近的一项调查，涵盖了几个类别的方法。主要类别包括： 基于因式分解的算法，通过矩阵分解产生嵌入；例如，Rowweisamp;Saul(2000)；Belkinamp;Niyogi(2001)；Ahmed等(2013)；Cao等人(2015)；ouetal.(2016)。这些方法学习训练和测试的表示。另一类是基于随机步行的方法（Perizzi等人，2014；Groveramp;Leskovec，2016），通过探索社区来计算节点表示。LINE（Tangetal.，2015 )也是通过保存第一和二阶接近度而激发的这种技术。同时，还出现了一些较深的神经网络架构，它更好地捕捉了图中的非线性，如SDNE(Wang等人，2016)。如前所述，GCN(Kipfamp;Wling，2016a)是我们工作的基础。

与我们的方法最相关的工作是GraphSA。(Hamilton等人，2017)，它通过邻域信息的聚合来学习节点表示。提议的聚合器之一采用GCN体系结构。提交人也承认，针对GCN的存储瓶颈，提出了一种限制邻域大小的自组织抽样方案。我们的抽样方法是以另一种更有原则的提法为基础的。主要的区别是我们采样顶点而不是邻域。由此产生的计算节省在3.3节中进行了分析。

3.通过采样进行训练和推理

GCN与许多标准的神经网络结构的一个显著区别是样本丢失缺乏独立性。基于损失函数对独立数据样本的加性质，设计了SGD及其批量泛化等训练算法，。对于图形，另一方面，每个顶点与所有相邻顶点进行卷积，另一方面，对于图，每个顶点都与它的所有邻域进行卷积，因此定义一个有效计算的样本梯度是非常简单的。具体而言，考虑标准SGD场景，其中损失是与数据分布D有关的某些函数g的期望：

这里，W表示要优化的模型参数。当然，数据分布通常是未知的，相反，通过访问n个iid样本x1......xn，可以将经验损失降到最小

在SGD的每一步中，梯度用nabla;g(W；XI)近似，这是nabla;L的一个假设的无偏样本，可以解释为每一梯度步骤都向样品损耗g(W；XI)推进。样品损耗和样品梯度只涉及一个样品。

对于图，通过丢弃I的信息，不再利用独立性计算样本梯度nabla;g(W；xi)。 S相邻顶点及其邻域，递归。因此，我们寻求另一种提法。为了在相同的抽样框架下转换学习问题，让我们假设存在一个顶点集V0与概率空间(V0，F，P)相关联的(可能无限)图，这样，对于给定的图G，它是G的一个诱导子图，并且它的顶点是根据概率测度P的Vrsquo;的iid样本。对于概率空间，Vrsquo;作为样本。F可以是任何事件空间(例如，幂集F=2V0)。概率测度P定义抽样分布。

为了解决卷积引起的独立性问题，我们解释了网络的各层定义了顶点的嵌入函数（随机 变量)，其与相同的概率度量绑定，但不独立。见图1。具体而言，回想GCN的体系结构

对于函数泛化，我们编写：

在这里，u和v是独立的随机变量，它们具有相同的概率测度P。函数h(L)被解释为从第1层开始的嵌入函数。嵌入函数 两个连续层的circ;是通过卷积表示的，表示为积分变换，其中核对应于矩阵的(v，u)元。损失就是开除。 最后嵌入的。请注意，积分不是通常的Riemann-Stieltjes积分，因为变量u和v是图的顶点，而不是实数；这种区别只是形式主义的问题。用函数形式编写GCN允许以蒙特卡洛方式计算积分，这就导致了一种批处理的训练算法，也导致了训练和测试数据的自然分离。如在归纳学习中。对于每一层l，我们使用tl的 iid样本u(L)1，。。。，u(L)tlsim;P近似计算积分变换( 2)，即，

其中H(0)T0为H(0)。然后，(3)中的损失L允许估计器

下面的结果证明了估计量是一致的。证明是大数定律和连续映射定理的递推应用，在附录中给出了证明。

图1：GCN的两个视图。在左边(图卷积视图)，每个圆表示图形顶点。在两个连续的行中，如果图形中的两个对应的顶点连接，则圆I与圆J连接(以灰色线表示)。 图中的对应顶点是连通的。卷积层使用图的连通性结构来混合顶点特征/嵌入。关于右边(积分变换视图)，下一层是前一层的一个整体变换(用橙色扇形表示)。.对于该方法，所有积分(包括损失函数)都采用蒙特卡罗抽样方法进行评估。相应地，在图视图中，以在每层中的引导方式对顶点进行次采样，以近似卷积。所采样的部分是用蓝色的圆和橙色的线条来表示。

定理1.如果g和sigma;是连续的，则

概率为1。

在实际应用中，我们给出了一个图形，其顶点已经假定为样本。因此，我们需要引导来获得一致的估计。特别地,对于网络架构, (1)输出H(M)像往常一样分批。我们仍然使用表示来自给定图的一批顶点。对于每一批，我们都要进行样品各层均匀，得到样品u(L)i，i=1。。。，tl，l=0，。。。、Mminus;1.这样的过程相当于对每个l的H(L)行进行均匀抽样。然后，我们得到批损失

在那里，递归地，

在这里，激活函数sigma;中的n是给定图中的顶点数，用于计算矩阵形式(1)与积分形式(2)之间的归一化差。 。通过在每个H(L)上应用链规则，可以直接得到相应的批处理梯度。见算法1。

3.1方差缩减

对于任何估计器来说，一个感兴趣的是改进其方差。尽管由于在所有层中的非线性,计算全方差是非常具有挑战性的,但是可以考虑每个层, 单层结构，旨在改善非线性前嵌入函数的方差。特别地，考虑到第1层，函数作为对流层的近似。 。当取样品时，的样本平均值承认了一个从 最终损失是由这一层造成的。因此，我们寻求改善这一差异。现在我们分别考虑每一层，我们将对表示法做如下更改，以保持表达式 较少累赘：

在v和u的联合分布下，上述样本平均值是

首先，我们有以下结果。

命题2.G的方差

其中

方差(6)由两部分组成。第一部分R几乎没有改进的余地，因为在v空间中的采样没有在这一层完成。第二部分(双积分) 另一方面，取决于这一层中的是如何被采样的。目前的结果(6)是利用概率测度P的抽样序列。 循环采样分布以减小方差。特别地，设q(U)是新的概率测度，其中是从。因此，我们定义了新的样本平均近似值。

以及利息的数量

定理 3.如果

的方差

其中R在命题2中定义。在Q的所有选择中，方差是最小的。

用这种方式定义抽样分布q的缺点是，它涉及到|x(u)|，这是一个不断变化的过程。 在训练期间。它对应于嵌入矩阵和参数矩阵的乘积。参数矩阵在每次迭代中都会被更新，并且矩阵积是昂贵的。 计算。因此，计算最优测度Q的成本是相当高的。作为一种折衷，我们考虑q的另一种选择，它只涉及b(U)。下面的命题给出了精确的定义，所产生的方差可能小于(6)，也可能不小于(6)。然而，在实践中，我们发现它几乎总是有帮助的。

命题4.如果

如果b(U)在(7)中定义，则Gq的方差允许

在命题2定义R的情况下，在概率测度Q的选择下，dQ(u)/dP(u)的比值与成正比，就是相对于v的积分。 实际应用中，对于网络体系结构(1)，我们定义了给定grap中所有顶点的概率质量函数。

和样本t点u1, . . . , ut，根据这个分布。从Q的表达式看，它不依赖l，即所有层的采样分布是相同的。到 总括而言，(4)中的批处理丢失批处理现在被递归地扩展为

(5)和(10)的主要区别在于前者得到样品的均匀性，后者是按Q表示的。因此，求和内的缩放发生了变化。相应的BATC 通过在每个H(L)上应用链规则，可以直接得到h梯度。见算法2。

3.2 推理

上一小节描述的抽样方法清楚地将测试数据与培训分开。这样的方法是归纳的，而不是许多图表中常见的换能器。 里特姆斯。其实质是将图顶点集转换为概率分布的iid样本，这样学习算法就可以使用对损失的一致估计量的梯度。 参数更新然后，为了进行推断，可以使用完整的GCN体系结构(1)计算新顶点的嵌入，也可以像在参数学习中所做的那样，通过抽样进行近似。 通常，使用完整的体系结构更简单，更容易实现。

<strong

资料编号：[3448]</strong