英语原文共 12 页
半监督分类的图分区神经网络
摘 要
我们提出了图分区神经网络（GPNN）,它是能够处理极大图的图神经网络（GNNs）的扩展。GPNNs在小子图中节点之间的局部传播信息和子图之间的全局传播信息之间交替。为了有效地划分图形，我们尝试了几种分区算法，并提出了一种新的快速处理大规模图形的变体。我们在各种半监督节点分类任务上广泛测试我们的模型。 实验结果表明，GPNN在基于图形的半监督分类的各种数据集上优于或与最先进的方法相当。 我们还表明，GPNNs可以实现与标准GNNs相似的性能，传播步骤更少。
1 介绍
图形是一种灵活的数据编码方式，许多任务可以用来学习图形结构输入。例子包括预测化学分子的性质[9]，回答有关知识图的问题[25]，使用解析结构的输入进行自然语言处理（树木或更丰富的结构，如抽象意义表示）[4]，预测适当的 - 数据结构或源代码在编程语言中的联系[2,22]，并从场景图中进行预测[39]。序列数据可以看作是简单链结构图的特例。因此，我们有兴趣在这些类型的图形结构输入上训练高容量神经网络模型。图神经网络（GNNs）[11,14,21,22,28,29,42]是最好的竞争者之一，尽管最近有兴趣将其他类似神经网络的模型应用于图形数据，包括概括卷积结构[9,18,30]。 Gilmer等人，[12]最近审查并统一了许多这些模型。
GNN模型中没有引起太多关注的一个重要问题是信息如何在图表中传播。通常情况下，信息必须在图表上长距离传播，例如，当我们在序列的元素之间增加了额外的关系时，如文本，编程语言源代码或时间流。最简单的方法，以及几乎所有基于图形的神经网络采用的方法都是遵循分布式计算理论中的同步消息传递系统[3]。具体地，推断作为一系列轮次执行：在每一轮中，每个节点向其所有邻居发送消息，传递消息并且每个节点基于所接收的消息进行一些计算。虽然这种方法具有简单且易于实现的优点，但当任务需要在图中长距离传播信息时，效率特别低。例如，在处理序列数据时，如果我们对长度为N的序列采用上述调度，则需要个消息从序列的开头到结束传播信息，并且在训练期间所有消息必须存储在内存中。相比之下，序列数据的常见做法是使用正向传递，然后以为代价进行反向传递，以便从端到端传播信息，例如，在隐马尔可夫模型（HMMs）或双向递归神经网络（RNNs）中。
解决此问题的一种可能方法是按照一些预先指定的顺序顺序在图表上传播信息，如双向LSTMs中那样。但是，这种顺序解决方案有几个问题。首先，如果用于训练的图形具有大直径，则展开的GNN计算图将是大的（参见长序列上的双向LSTMs）。这导致学习（例如，消失/爆炸梯度）和实现困难（即，资源约束）的基本问题。其次，顺序调度通常不太适合并行硬件上的有效加速。最近，Gilmer等人，[12]试图通过引入一个“虚节点”来解决第一个问题，该虚节点具有与输入图中所有节点的连接，这意味着所有节点彼此相距最多两步。但是，我们注意到图形结构本身通常包含重要信息，通过添加其他节点和边缘来修改这些信息。
在这项工作中，我们提出了图分区神经网络（GPNN），它利用了传播时间表，结合了同步和顺序传播时间表的特征。具体地说，我们首先将图形划分为分离子图和切割集，然后在子图中使用同步传播在切割集内进行同步传播的交替步骤。 在第3节中，我们在一个例子中讨论不同的传播时间表，表明GPNNs可以比标准GNNs更有效，然后正式呈现我们的模型。 最后，我们在第4节中评估了我们在各种半监督分类基准上的模型。实证结果表明，我们的模型要么优于或与图表上最先进的学习系统相当。
2相关工作
有许多用于处理图形结构输入的神经网络模型。它们大致可归类为递归神经网络（RNNs）的概括[13,14,21,22,25,28,29,34,37]和卷积神经网络（CNNs）的概括[7,9,18,30]]。Gilmer等人[12]提供了许多这些模型的良好评论和统一，并且它们提供了一些额外的模型变化，这些变化导致从分子结构输入进行预测的强有力的实证结果。
在类似RNN的模型中，标准方法是使用同步调度来传播信息。在类似卷积的模型中，节点更新模拟标准卷积，其中层中的所有节点都被更新为前一层中相邻节点状态的函数。这导致信息以与同步计划相同的模式在图表中传播。虽然我们的重点主要是Li等人[22]的RNN模型。将我们的时间表应用于其他模型也会很有趣。
一些基于RNN的神经网络模型在受限制的图类上操作，并采用顺序或顺序类型的调度。例如，递归神经网络[13,33]和树-LSTMs [37]具有使用完全顺序调度的双向变体。Sukhbaatar等人[35]代理的建模可以被视为具有顺序调度的GNN模型，其中消息向内传递到主节点，主节点聚合来自不同代理的消息，然后从主节点向外传递到所有代理。 我们工作的不同之处在于关注具有任意结构的图形（不一定是序列或树）。最近，Marino等人[25]开发了类似注意力的机制，动态选择图节点的子集来传播信息，但传播在所选节点之间是同步的。
最近，Hamilton等人[16]提出了图样本和聚合（GraphSAGE）方法。它首先为每个节点采样邻域图，其可以被视为原始图的重叠分区。然后将改进的图卷积网络（GCN）[18]独立地应用于每个邻域图。他们表明，这种基于分区的策略有助于在大规模图形上进行无监督的表示学习。
广泛研究调度的领域是概率推理文献。通常将图分解为一组生成树并依次更新树结构[41]。基于图分区的时间表已经在信念传播（BP）[26]，广义信念传播（GBP）[43,48]，广义平均场推理[45,46]和基于双重分解的推理[19,49]中进行了探索。在广义平均场推断[45]中，应用图分区算法，例如图切割，以获得节点簇。采用集群间的顺序更新调度来执行变分推理。Zhang等人[49]采用基于分区的策略，以更好地分配基于双分解的消息传递算法，用于高阶MRF。联结树算法[20]也可以被视为基于分区的推理，其中通过在加权集团图上找到最大生成树来获得分区。结点树的每个节点对应于原始图中的节点簇，即最大集团。然后可以在连接树上执行顺序更新。有关信念传播背景下的顺序更新的更多讨论，另见[10,36,38]。最后，顺序与同步更新的问题出现在数值线性代数中。Jacobi迭代使用同步更新，而Gauss-Seidel应用相同的算法但根据顺序调度。
3模型
在本节中，我们简要概括了图神经网络（GNN），然后描述了我们的图分区神经网络（GPNN）。 图具有节点和边缘。我们专注于有向图，因为我们的方法通过将任何无向边分成两个有向边来容易地应用于无向图。我们将外出邻域表示为Nout（v）= {uisin;V| （v，u）isin;E}，类似地，输入邻域为Nin（v）= {uisin;V| （u，v）isin;E}。 我们将边类型c（v，u）isin;{1，...，C}与每个边（v，u）相关联，其中C是一些预先指定的边类型总数。这种边缘类型用于编码节点之间的不同关系。注意，还可以将多个边缘类型与相同边缘相关联，从而产生多图形。我们假设每个有向边有一个边缘类型来简化这里的符号，但是模型可以很容易地推广到多边情况。
3.1图形神经网络
图神经网络[22,29]可以看作是递归神经网络（RNN）到任意图的扩展。图中的每个节点在时间步骤0与初始状态向量相关联。初始状态向量可以是[22]中观察到的特征或注释。在时间步t，通过根据边缘类型变换源状态，为每个边计算输出消息，即
其中Mc（u，v）是一个消息函数，它可以是身份或完全连接的神经网络。请注意下标c（v，u），表示相同类型的不同边共享消息函数的相同实例。然后，我们在接收节点聚合所有消息，即
其中A是聚合函数，可以是求和，平均或最大池函数。最后，每个节点将根据其当前状态向量和聚合消息更新其状态向量，即
其中U是更新功能，可以是门控循环单元（GRU），长短期存储器（LSTM）单元或完全连接的网络。请注意，所有节点共享相同的更新功能实例。 所描述的传播步骤被重复应用于固定数量的时间步长T，以获得最终状态向量{h（T）v | visin;V}。 然后可以通过将这些状态向量馈送到由所有节点共享的完全连接的神经网络来实现节点分类任务。通常采用反向传播（BPTT）来学习模型。
3.2图分区神经网络
从单个节点的角度描述了上述推理过程。如果我们从图表视图中查看相同的过程，我们会观察到一个同步调度，其中所有节点同时接收和发送消息，参见 图1（d）中的插图。一个自然的问题是考虑不同的传播时间表，其中并非图中的所有节点同时发送消息，例如顺序调度，其中节点以某种线性序列排序，并且消息一次仅从一个节点发送。两种想法的混合导致我们的图形分区神经网络（GPNN），我们将在详细说明如何适当地划分图形之前讨论。最后，我们讨论如何处理初始节点标签和节点分类任务。
传播模型 我们首先考虑示例中的图1（a）。在图1（d）中示出了使用标准（同步）传播调度表示信息如何从时间步长t传播到时间步骤t 1的相应计算图。 示例图的直径为5，因此需要至少5个步骤才能在图上传播信息。图1（c）显示了两个可能的序列，显示了信息如何在节点2到6和5到1之间传播。这些可视化表明（i）完整的同步传播时间表需要在每个步骤进行重要的计算，并且（ii）顺序传播调度，其中我们仅沿节点序列传播，导致非常稀疏和深的计算图。 此外，通过实验，我们发现顺序调度要求在整个图形中进行多个传播轮次，从而产生更深的计算图形。
为了实现有效的传播和易于学习，我们提出了一种遵循分而治之的策略的新传播计划。 特别是，我们首先将图分割成分离子图。 我们将在下面解释如何计算图分区的细节。 现在，我们假设我们已经有了K个子图，这样每个子图包含一个节点的子集和由该子集引起的边。 我们还将有一个切割集，即连接不同子图的边集。 我们的例子的一个可能的分区在图1（b）中可视化。
在GPNN中，我们在每个子图的本地并行传播信息（利用高度并行的计算单元，如GPU）和在子图之间传播消息之间交替。 我们的传播时间表显示在Alg1中。 为了理解这个时间表的好处，考虑图1中的示例图的广播问题。当来自任何一个节点的信息第一次到达图中的所有其他节点时，该问题被认为已经解决。 我们将比较针对不同传播时间表解决此问题所需的消息数。
同步传播：图1（d）显示同步步骤需要10条消息。 广播需要足够的传播步骤来覆盖图形直径（在这种情况下为5），总共提供5times;10 = 50条消息。
分区传播：为简单起见，我们分析了TS = DS，TC = 1的情况，其中DS是子图的最大直径。 使用1（e）中的分区，我们得到DS = 2，并且子图内传播的每个步骤需要8个消息。 在TS步骤（8DS消息）之后，在每个子图内解决广播问题。 在子示例中，子图间传播需要2个消息，在Alg1中每个外部循环迭代给出8DS 2个消息。 该示例需要在所有子图之间广播2次外部迭代，总共提供2（8DS 2）= 36条消息。
通常，我们的传播计划不需要比同步计划更多的消息来解决广播（如果子图K的数量设置为1或N，则我们的计划减少到同步计划）。 我们在A.1部分中详细分析了解链图上广播问题所需的消息数量。 总的来说，我们的方法避免了同步调度所需的大量消息，同时避免了顺序调度所需的非常深的计算图。 我们在第四部分中的实验中表明，即使在极大的图形上，这也使得学习易于处理。
图分区 我们现在研究如何构建图分区。首先，由于图论中的分区问题通常是NP难的，我们只是在实践中寻找近似值。一种简单的方法是重复使用经典的频谱划分方法。 具体来说，我们遵循[32]中的归一化切割方法，并使用随机游走归一化图拉普拉斯矩阵L = I-D-1W，其中I是单位矩阵，D是度矩阵，W是图的权重矩阵（ 即，如果没有权重，则为邻接矩阵）。
然而，频谱划分方法很慢，难以用大图进行扩展[40]。出于性能原因，我们开发了以下基于Alg2中列出的多种子流填充分区算法的启发式方法。 我们首先随机地对初始种子节点进行采样，这些节点偏向于被标记并且具有大的出度的节点。我们维护一个全局字典，将节点分配给子图，并最初将每个选定的种子节点分配给它自己的子图。然后，我们使用泛洪填充来增长字典，将未分配的节点附加到该图的子图的直接邻居。 为了避免偏向第一个子图，我们在每轮开始时随机置换子图的顺序。 重复应用此过程，直到子图不再增长。图中可能仍然存在断开连接的组件，我们将这些组件分配给到目前为止找到的最小子图以平衡子图大小。
节点特征和分类 在实践中，使用图形结构数据的问题有时（1）没有观察到与每个节点相关的特征[15];（2）每个节点具有非常高的维度稀疏特征[6]。我们为初始节点标签开发了两种类型的模型：嵌入输入和特征输入。对于嵌入输入，我们将可学习的节点嵌入引入到模型中以解决挑战（1），其灵感来自其他图形嵌入方法。 对于具有观察到的特征的节点，我们将嵌入初始化为这些观察，并且所有其他节点随机初始化。所有嵌入都被馈送到传播模型，并被视为可学习的参数。 对于特征输入，我们应用稀疏的全连接网络来输入要素以应对挑战（2）。 然后将尺寸减小的特征馈送到传播模型，并且与模型的其余部分共同学习稀疏网络。
我们还凭经验发现，将输入特征与传播模型产生的最终嵌入连接起来有助于提高性能。
4实验
我们在各种半监督任务上测试我们的模型：引文网络上的文档分类; 从知识图中提取的二分图中的实体分类; 和远程监督的实体提取。然后，我们比较我们的模型利用的不同分区方法。 我们还比较了不同传播时间表的有效性。 我们遵循[47]中的数据集和实验设置。图表1总结了统计数据，揭示了数据集在规模，标签率和特征维度方面的差异很大。我们在附录中报告了所有实验
资料编号：[3499]
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
