英语原文共 10 页

语境图马尔可夫模型：图形处理的深层次生成方法

摘要

我们介绍了语境图马尔可夫模型，这是一种将生成模型和神经网络的思想结合起来处理图形数据的方法。它以一种建设性的方法为基础，构建一个由概率模型层组成的深层架构，该架构学习以增量的方式编码结构化信息。上下文以一种高效且可伸缩的方式在图形顶点和边缘之间进行扩散。所得到的图编码与判别模型结合使用来处理结构分类基准。

1引言

结构化域学习(SDs)处理不同大小和拓扑结构的数据，相当于识别、综合和嵌入模型中的结构关系。一种在过去广泛使用的简单方法是对结构进行预处理，以获得手工设计的特征的固定矢量表示，并将其提供给标准的学习模型。在这样做的过程中，许多携带有用信息的关系肯定会丢失。通过对有向无环结构(序列、树和标记)施加拓扑顺序(称为因果关系假设)，递归和递归模型被广泛用于学习这类编码，但因果关系假设限制了可以处理的数据的类别。特别是，如果没有昂贵的扩散机制和对模型状态转移函数的约束，状态空间的递归定义就不能应用于循环输入。

本文介绍了一种新颖的无监督学习编码生成模型的循环结构，它借鉴了以前的SD处理工作，即生成的自下而上的隐马尔可夫树模型（Bacciu等.2012a）和神经网络的建设性方法图（Micheli.2009）。

我们相信这是第一个可伸缩的实现生成模型的处理可变大小的图表。它的概率特性允许对标记不确定性建模，以及对图形顶点和弧线进行推理。无监督生成编码器可以在不依赖于当前问题的数据中捕获丰富的模式，允许跨不同任务广泛地重用编码，并最终利用无标记的示例在半监督设置中提高准确性。

此外，模型以增量方式进行训练，这允许在受监督的任务中自动构建体系结构。信息传播是通过深度学习方式分层实现的。每个层中的计算都是完全本地的，高度可伸缩的，不需要迭代过程或收敛条件。深度对上下文的形成有深远的影响，因为它允许每个顶点收集其周围环境的更广泛的图像，其中有许多层对生成上下文编码是有作用的。我们将集中讨论需要将从图的域转换到离散或连续空间的分类任务。与固定的核函数相比，这种映射具有自适应的优点，它由编码函数和输出函数组成。前者以图g为输入，生成隐藏表示z(g)，后者以编码为输入，输出预测。我们将考虑一个通过支持向量机(SVM)实现的输出函数，输入生成模型的潜在变量学习的隐藏表示z(g)。我们的模型被称为语境图马尔可夫模型(CGMM)，其表示能力在树分类(直接与递归和内核方法进行比较)和生化数据集(其中化合物自然地以无向图表示)的流行基准上进行了测试。

2背景

本节提供了我们在本文其余部分中处理的图形类的定义以及相关的符号。然后，我们总结了结构化数据机器学习模型的背景，特别强调了那些能够处理与本文方法相同的结构的模型。

2.1符号

我们考虑从一组图数据中学习结构化数据其中，每个样本是一个标记图，其拓扑结构、节点数和边缘相对于其他样本不同。图结构没有任何限制，特别是在非循环方面。图由一组顶点和一组边（也称为弧）定义，例如在两个顶点之间。 有向弧（u，v）可以与标签相关联，为了本文的目的，我们假设它取自有限字母。 类似地，顶点u与来自有限词汇。的标签相关联。 从上下文中清除时，我们省略了下标g以避免混乱。

图1展示了一个示例图来澄清符号：我们使用无向边来简化绘图，以表示具有相同标签的两个有向弧的存在。在本文的其余部分,我们将使用附近的一个顶点u的概念,定义为。下面我们将考虑u的一个开放邻域，即不包含u本身的邻域。无向连接由两个有向弧建模。图1显示了目标节点u = 4的邻域示例，用虚线表示。

图1突出显示整篇论文中使用的符号的示例图：表示顶点u的标签，是连接u到v的边的标签，而Ne（u）是顶点u的邻居集。图中突出显示顶点4的邻域为虚线区域。无向边表示在顶点之间的不同方向上定向的两个弧的存在，并且共享相同的标记。通常，图表可以包括有向和无向边缘。

2.2.图形的机器学习

处理结构化数据的数据集是一项复杂的任务，因为它需要能够满足改变大小和连接性的样本，从这种结构变化模式中提取对实现预测和/或探索性分析有用的样本。这需要学习能够适应样本结构的模型。文献中的几种方法已经成功地处理了序列、树和其他非循环拓扑。然而，当转移到更一般的、可能是循环的拓扑时，就像我们在本文中所关注的那样，事情就变得相当麻烦了。这方面的文献报道了许多通过简化和放宽原始问题来处理循环问题的作品。

在神经范式中，几乎同时提出了两种基本方法来设计图形的神经网络。它们能够学习用于分类或回归任务的隐藏表示(状态编码)和输出函数。通过利用权重共享技术，他们还实现了一个平稳性假设，以便有效地处理可变大小的结构。图神经网络(Scarselli等.2009) (GNN)是一种使用递归模型直接扩展的监督模型。在迭代的方式中，在每一步中，与相邻顶点相关的神经元之间交换信息。神经元实现了由权值约束得到的收缩态转移函数，以保证扩散过程在每个历元都能达到平衡。因此，GNN可以处理有向图、无向图和循环图，代价是对权重值引入约束，并为效率方面有缺陷的循环引入递归动力学。另一方面，图的神经网络(Micheli.2009) (NN4G)利用了一种前馈神经网络结构，该结构的分层结构是在训练时确定的 (Fahlman amp; Lebiere.1990)。循环结构在没有递归状态定义的情况下很容易处理，因为通过利用冻结状态，计算对每个顶点都是局部的，而增量结构允许以对称的方式捕获越来越大的上下文(正式证明在(Micheli.2009))。因此，NN4G可以应用于任何类型的图(例如GNN)，尽管对权重值的限制有所放宽。NN4G还实现了一种更有效的方法，既避免了对循环的动态过程的需要，又通过渐进层开发了任务的增量方法。(Duvenaud等.2015)提出了一种类似NN4G的分层方法，其灵感来源于化学结构中的圆形指纹。与NN4G(和CGMM)不同的是，图的编码是通过所有层的端到端反向传播来学习的，而不是渐进的。最近，人们提出了将卷积神经网络(CNN)扩展到图形的替代方法：PATCHY-SAN (Niepert等.2016)是第一个将卷积以顶点为中心扩展到图形中相邻节点的方法。在处理拓扑结构变化的图数据集时，这种方法需要为每个图确定一个在整个数据集上一致的顶点顺序，并对邻域大小施加上限，限制灵活性和上下文传播。两种相关的方法(Defferrard 等.2016;Kipfamp;Welling.2017)通过对图的拉普拉斯算子进行光谱分析，将CNN扩展到图中，但这种方法限制了对具有无向边的固定大小的单一图的适用性。最近(Hamilton等.2017)，出现了将图卷积扩展到不同大小结构的初步工作，使用了一种非常类似于(Micheli.2009)的信息传播机制。

在过去的十年中，内核已经成为处理图形数据最流行的方法。它们通常基于原始问题的松弛，计算原始图中更简单(计算上可承受)的子结构/特征之间的匹配，例如从每个顶点随机漫步生成的子结构/特征(Borgwardt amp; Kriegel.2005;Kashima等.2003)。(Da San Martino等.2012) 提出的解决方案是将图转换为多组有向无环图(DAGs)，将相似度定义为DAGs上的多组相似度评分。Fast-Subtree（Shervashidze＆Borgwardt.2009）内核（FS）通过Weisfeiler-Lehman（WL）测试对图的同构性进行比较。 这是基于迭代算法，其输出重新标记的图，其中每个顶点是多组压缩的结果。 FS内核使用来自不同WL迭代的重新标记作为结构特征，从根本上根据这种重新标记中的公共字符串的数量来计算图形相似性。 在大型数据集上使用这些内核受到计算成本的限制。 此外，它们缺乏适应性，因为相似性函数是由手工设计的特征定义的，而不是从数据中学习，这可能会限制它们的适用范围。

概率模型在图形数据中的应用在很大程度上受到循环对用于编码结构信息的随机变量之间的概率关系的影响。循环使得推理和训练过程对于实际应用来说过于复杂。在这方面，许多贡献都是处理非循环结构，如树，通常通过递归扩展隐藏的马尔可夫模型(Frasconi等.1998;勤奋等人，2003;Bacciu等.2012a)。这些概率模型学习树x上的分布P(x)，假设节点是由隐藏状态生成的，其转换概率取决于节点的子节点、兄弟节点或父节点。这些(通常是无监督的)生成模型可用于解决监督任务，例如在学习概率过程的基础上定义生成内核(Bacciu等.2018)。

本文提出的模型在NN4G环境传播方案的基础上，引入了第一个可伸缩的变尺度图生成模型。它使用隐藏变量来编码结构信息，使用邻近节点的扩散。为了避免出现循环问题，上下文传播是通过在前生成层冻结邻居隐藏状态的表示来实现的。

3语境图马尔可夫模型

接下来，我们将介绍语境图马尔可夫模型的形式化，简要总结运行该模型所需的主要步骤，即参数学习、顶点编码推理和增量分层策略。

3.1.模型

CGMM是一种学习对结构信息进行编码的图形的概率模型，它采用模块化的方法，利用基础模块的堆栈和分层的池策略来提高识别效率(Fahlman amp; Lebiere.1990)。如预期，CGMM架构借鉴NN4G，而每一层的实现都受到树的递归概率模型的强烈影响，如自底向上的隐马尔可夫模型(BHTMM) (Bacciu等.2012a)。

基本的CGMM组件使用离散隐藏状态变量对顶点及其上下文的信息进行编码，从而对图形进行建模。因此，每个顶点u都与一个多项式随机变量相关联，该变量的值在有限字母表{1，hellip;，C}，其中C为隐藏状态大小。与隐马尔可夫模型一样，节点u的隐状态分配通过发射分布来确定观测到的标签 (再次假设是离散的)的发射。不同于标准的隐马尔可夫模型,然而,当前隐藏状态的任务,即l层的架构,并不取决于从另一组在同一层隐状态l。相反,顶点状态在l层是由相邻的顶点的冷冻的作业Ne(u)在前一层。这是一个关键的区别，因为这样的赋值可以在级别l上被认为是完全可观察到的，从而避免了层之间的相互因果依赖，并防止由于循环而陷入不确定的推理循环。

图2以图形模型的形式展示了该方法，主要集中在目标层l上。当前级别上的隐藏状态由大写项表示，这些项是图形模型的空节点，因为它们没有被观察到。顶点标签是观察到的节点，概率模型在图的结构上展开，就像一个隐藏的马尔可夫模型在序列的结构上展开一样。图2还描述了如何隐藏状态通过分布确定节点基于其邻国的状态(也可能是自己)之前的水平。这些状态是由另一个概率模型确定的，之前训练过，然后冻结。结果的状态分配用小写的项标记，相应的节点是黑色的，表示必须考虑观察到它们。

图2.表示为在左侧图形结构上展开CGMM的第l层的图形模型。通常，空节点对应于未观察到的变量，而完整节点表示观察到的顶点标签(阴影部分)和前一层的状态分配(黑节点)。粗的无向边表示弧，虚线箭头表示概率因果关系。

图2中描述的方案在许多层之间迭代，每个层都相对于前面的层进行了独立的训练，但是使用它们以隐藏状态标签的形式提取的知识。图3显示了CGMM在四层结构上的展开。这个过程从第一级开始，除了顶点标签，隐藏状态的分配不考虑任何上下文。在下一次迭代中，顶点可以访问关于其直接邻居的信息。在第三级，他们开始从邻居的邻居那里接收信息。此过程的迭代允许从图的每个节点进行有效的上下文传播(前提是使用足够数量的层)。该体系结构中的上下文传播是对称的，不需要隐藏状态之间的因果依赖关系。因此，CGMM可以有效地处理任意维度的图，而不需要对拓扑属性进行假设，这与需要限制顶点邻域大小或添加填充来使用固定大小表示的模型形成了对比。

图3.为循环结构(左侧)展开隐藏的状态变量。在这个图中，实线表示边缘，虚线表示上下文信息流。在第一层顶点不知道任何关于周围结构的信息。如果我们关注红色的顶点，我们就会看到深度的增加是如何导致状态(圆形的正方形)的，这些状态在图形中占了更大的一部分。也许更重要的是，由于因果关系假设的放宽，信息的传播是对称的。如果不引入循环状态定义，循环或递归模型就无法实现这一点。

CGMM的每一层都是使用相同概率模型的不同实例实现的，下面我们将为该模型提供似然函数。让我们首先定义的套层先于当前层L。我们让表示相邻的隐状态的顶点集u,由前一层。然后我们可以定义l级模型的可能性为

请回忆一下，当上下文清楚时，我们将从索引项g中抽象出来以简化符号。式(1)假设顶点是相互独立的，使得模型的训练有效且具有可扩展性。结构信息通过前一层的状态分配条件间接传递。由于条件部分中状态的组合数(潜在的)，最右边项的复杂性可能变得不可行的。这可以通过采用诸如（Bacciu等.2012a）中的切换父（SP）近似来处理，以便控制子到父转换的复杂性。 这里，我们引入一个SP变量，其概率表示确定状态转移时的等级的权重，另一个变量的分布控制带有标签a的弧的权重，当考虑的层是时给出。由此产生的可能性是

我们介绍了表示美国的作业水平有标签的所有邻国的弧。这样的参数允许根据顶点的隐藏状态、连接边上的标签以及生成上下文信息的深度来区分顶点。隐藏状态分布可以进一步分解为

假设中的所有顶点，共享arc标签a的a(u)贡献相等(对于每个级别)。显然，可以设计这种分布的其他分解方法，但是为了本文的目的，我们坚持使用最简单和直观的方法。

综上所述，a能级l的模型

资料编号：[3602]