0
论文作者：Mathias Niepert、Mohamed Ahmed、Konstantin Kutzkov NEC Labs Europe，海德尔堡，德国
论文摘要
许多重要问题可以划归到图像数据学习框架里。我们针对学习卷积神经网络提出了一个框架，可以适用于任何图形。这些图形可以是无向的，定向的，也可以是具有离散和连续节点和边缘属性。类似于基于图形的卷积网络，可以再本地化的可连接输入区域上允许，我们提出了一种普遍方法，可以从图形中提取本地化的可连接区域。使用既定的基准数据集，我们展示了带有最先进图形内核的学习功能表现，是具有竞争力的，同时，它们的计算效率也是非常高的。
一、概述
在这篇论文中，我们的目标是卷积神经网络解决一大类基于图形的学习问题。我们想到了以下两个问题：
1. 给定一个图形集合，学习一项功能，可以用于在未见图形上进行分类和回归。任意两个图的节点不一定是对应的。举个例子，集合中的每一个图形都可以“模型化”一种化合物，输出也可以是一个功能，将未见组件定位到癌细胞的活性水平。
2. 给定一个大图，学习图形表现，可以用来推断看不见的图形属性，比如节点类型或是缺少的边。我们提出了一个框架，用于学习定向和无向图形类别的表现。这些图形可以有多个离散和连续属性的节点和边，可能有多个类型的边。和识别图像的卷积神经网络类似，我们利用输入的图像构建了局部连接的邻域。这些邻域构建效率高，可以充当卷积网络的感知域，让卷积网络有成效地学习图像特征。
图1：一个3*3感受域的卷积神经网络。该域可以覆盖图形被移动，从左到右，从上到下，通过使用一个特定跨越（这里：1）和零填充（这里：0）(a).被感受域所读取的值被转化成一个现行层，并反馈送至一个卷积架构(b). 被创建的感受域和感受域的形状的节点序列完全由超参数决定。
图2. 建议架构的一个图例通过一个图形标记程序，从图中选择一个节点序列。对于序列中的一些节点，局部领域图将会被拼装且正则化。正则化的邻域也将被用作感受域，并且和现有的卷积神经网络组件进行整合。
此处建议的方式根据卷积神经网络（CNN）识别图像的理论（福岛邦彦，1980年； Atlaset等人，1988年；LeCun等人，1998年、2015年)而设计，并将这些理论拓展应用在任意图上。
图1展示了卷积神经网络识别图像的局部连接感知域。
一个图像可以表现为正方形格网的图形，其节点就代表像素。现在，一个卷积神经网络可以被视为穿越一个节点序列（图1（a）中的节点1到4，每个节点之间形成大小固定的邻域图（图1（b）的3乘3格网））。邻域图可以充当感知域，通过像素节点解读特征值。由于像素的空间顺序并不清晰，邻域的图从左到右、从上到下生成节点序列，这种序列的确定过程是独特的。自然语言处理（NLP）的问题也同样是独一无二的，因为每个句子（及其句法树）都决定了一些词语的序列。然而，对多个图形集合来说，某个特定问题的顺序（空间、时间或是其他顺序）是缺失的，图形的节点并不对应。在这种情况下，必须解决两个问题：(i)确定邻域产生的节点序列；(ii) 计算邻域图形的正则化，即一种从图形特征转换到矢量特征的独特映射。每个输入图形首先确定邻域生成的节点（及其顺序）。在生成这些节点的邻域里都能提取一个k节点，并进行正则化。也就是说，以固定的线性顺序，进行空间的独特映射。经过正则化的邻域可以成为某个考量节点的感受域。最终，卷积层和稠密层等特征学习组成部分与正则化的邻域相结合，形成卷积神经网络的感受域。
图2展示了PATCHY-SAN结构。该结构在运用现有方式时有诸多优势：
首先，它效率很高，很容易并行，可以应用于大图形；第二，对于计算生物学和社交网络分析等多个领域的应用来说，可视化网络主题非常重要（Milo等人, 2002），PATCHY-SAN支持特征可视化，那样可以深入了解图形结构特征；第三，PATCHY-SAN并未创造另一个图核，而是学习依靠应用的特征，无需做特征工程的工作。我们的理论贡献在于，界定图形及其复杂性的正则化问题；提供一种比较方法，比较各种图形集合的图形标记方式；显示PATCHY-SAN归纳图像卷积神经网络的结果。我们通过运用标准的数据集展现出，和高级水平的图核相比，经过学习图像的卷积神经网络不但有效，而且效率很高。
二、相关文献
对图核可以采用基于核的学习方法，如支持向量机（SVM）就可以直接处理图形（Vishwanathan等人，2010年）。图形之核最初的定义是，单个图形所有节点的相似函数（Kondor 与Lafferty，2002年）。核按特征分两大类，一类是偏差频谱核，另一类是基于基元的核（Milo等人，2002年；Alon，2007年）。但由于子图枚举组合很复杂，基元图核受到节点很少的子图限制。图核还有一类是简称WL的Weisfeiler-Lehman算法核（Shervashidze等人，2011年）。可是WL核只支持离散特征，对测试的训练样本用有记忆的线性系统。PATCHY-SAN用WL核作为计算感受域时一个可能标识的过程。深度图核（Yanardag与Vishwanathan，2015年）和图形不变特征核（Orsini等人，2015）比较图的依据是子结构的存在方式或者数量，如根据基元、子树和其他图形的不变特征（Haussler，1999年；Orsini等人，2015年）。PATCHY-SAN则是从图形数据中学习子结构，不受预先界定的主题限制。但所有图核训练都很复杂，图形数量至少有二次方变化（Shervashidze等人，2011年）。如果是大型图形的问题，用这种方法需要付出很高代价。PATCHY-SAN用线性方式测量图形数量。
图形神经网络（GNN）（Scarselli等人，2009年）是通过图形明确的一个递归神经网络结构。图形神经网络运用递归神经网络在图形结构上游走，这期间传播节点表示，直至抵达一个固定点为止。然后，由此形成的节点表示会成为可以用于分类和回归问题的特征。图形神经网络仅支持离散的标识，只要每次学习迭代的图形都有边和节点，就能在很多反向传播操作中发挥作用。门控图序列神经网络会改变图形神经网络，以便利用门控递归单元（GRU）和输出序列（Li等人，2015年）。
最近的论著拓展了卷积神经网络的应用范围，将它用在有别于低维度格网结构的拓扑学（Bruna等人，2014年；Henaff等人，2015年）。然而，所有这些方法都假定的是一个全球图形结构，这即是说，不同输入样本的顶点是同一个匹配（Duvenaud等人，2015年），基于此在图形上进行卷积类操作，开发某个图形特征彼此不同的变量。
三、论文背景
我们在此简要介绍了在卷积网络和图形理论方面所需的背景。
3.1. 卷积神经网络
根据早期论著显示，动物大脑的视觉皮层生长着结构复杂的细胞，它们负责监测视域内小局部域的光。卷积神经网络正是受到这些论著启发而来（Hubel 与Wiesel，1968年）。卷积神经网络于上世纪80年代开创，现已用于解决图像、演讲、文本和药物研发问题（阿特拉斯等人，1988；LeCun等人，1989年、1998年、2015年；Wallach等人，2015年）。卷积神经网络的前身是神经认知机（福岛邦彦，1980年）。卷积神经网络通常由卷积层和稠密层组成。第一层卷积层的目的是，在输入图像的局部域内发现共同模式后将其提取。卷积神经网络通过卷积过程学习输入图像的滤波，对图像内每个图像定位进行内积运算，输出作为张量的结果。张量的深度就是滤波数量。
3.2. 图形
假如图形G是一个偶对，用公式可以表达为G= (V, E)，其中代表图中顶点的V = {v1, ..., vn}，则代表图中边的E可以表达为E ⊆ V × V。假设n是顶点的数目，m是边的数目。每个图形可以用一个大小为n ×n的邻接矩阵A表示。如果有一条边以顶点vi和顶点vj为端点，则A i,j = 1，否则Ai,j = 0。在这种情况下，我们可以称顶点vi在A有一个定位i。而如果又是A i,j = 1，我们可以说vi和vj是邻接的顶点。节点和边的属性都是有特性的，因为在一个图形内每个节点和边都能获取一个值。为了避免与图论中的标号概念混淆，我们用了属性值这个术语，并没有用标识一说。链是图形中节点的序列，其中连续的节点刚好由一条边连接起来。路是内部节点互不相同的链。我们用公式d(u, v)代表u和v之间的距离，它也就代表着u和v之间最短路径的长度。N1(v)代表一个节点的1-邻域，也就是所有邻接的节点。
标识与节点划分 PATCHY-SAN运用图形标识让节点形成顺序。图形标识`表现为这样一个函数： ` : V → S，其中V是顶点集合，S是一个有序的组合，比如一些实际数目和整数。图形标识过程会计算输入图的图形标识。在语境明确的时候，我们所说的标识既是指图形标识，又是指计算图形标识的过程。一个排序（或着色）可以表达为这样一个函数r : V → {1, ..., |V |}。仅限于`(u) > `(v)这种条件时，每个标识都能导出一个排序，它可以用公式表达为r(u) < r(v)。如果图形G的标识是单射函数，它就能决定该图形所有顶点的顺序，以及G特有的邻接矩阵A`(G)。在那个邻接矩阵中，顶点v在A`(G)的定位是r(v) 。而且，每个图形标识都能导出一个顶点V上的节点划分{V1, ..., Vn}，其中仅限于`(u) = `(v)这种条件时，它们的关系可以表达为公式u, v ∈ Vi。图形标识过程的实例是节点度，以及其他中心度的衡量指标，都是网络分析的常用指标。例如，顶点v的中介中心度计算出穿越v的少数最短路径。Weisfeiler-Lehman（WL）算法（Weisfeiler & Lehman，1968年；Douglas，2011年）是划分某个图形内部顶点的一种过程。它也就是业内所说的着色求精和朴素顶点分类。着色求精已经引起WL研究人员极大的兴趣，因为它能用来提高图模型推理的速度（Kersting等人，2009年；2014年），还能用作计算图核的方法（Shervashidze等人，2011年）。PATCHY-SAN应用这些标识过程和其他度量指标（度、网页排名、特征向量中心度等），让图形的节点形成一个顺序，在依赖应用的顺序（时间、空间顺序等）缺失时弥补空缺。
同构与正则化 很多应用程序域都存在判定两个图形是否同构的计算问题。图形同构（GI）问题属于NP（非确定性多项式问题），但尚未明确是P问题（能在多项式时间内解决），还是NP难题。 在许多限制较缓和的情况下，GI属于P问题。比如处理有界度的图，GI就是P问题（Luks，1982年）。图形G的正则化是有固定顶点顺序的图形G0，此图与G同构，体现了G的全部同构类型。实际操作中，图形正则化工具NAUTY展示了卓越的性能（McKay与Piperno，2014年）。
四、任意图形的学习卷积神经网络
当卷积神经网络用在图像上时，一个感受域（一个方形格网）会以特定的幅度移动到每个图像上方。感受域会读取像素的特征值，每个频道读取一次，每个频道会生成一批值。由于图像的像素有隐性排列——空间顺序，感受域总是从左到右、从上到下移动。而且，空间顺序独到地决定了每个感受域的节点，以及这些节点对向量空间表示的映射方式（见图1（b））。因此，只有在像素的结构角色（感受域内的空间定位）相同时，用两种不同感受域定位读取的两个像素的值才会分配给同一相对定位。
为展示卷积神经网络和PATCHY-SAN的联系，我们将卷积神经网络框定在图像上，以此辨认在表现为方形格网图的该图像上有何节点序列，并以相同序列的各个节点构建经过正则化的邻域图——一个感受域。有的图形集合缺失依赖应用的节点顺序，任意两个图形的节点位置也未能对准。对这类图形集合，我们需要判断每个图形(i)为创建邻域的节点序列，以及(ii)一种从图形表示到向量表示的独特映射。在该向量表示中，那些在邻域图上结构角色相同的节点定位也相同。
我们解决这些问题的对策是，运用图形标识过程，将两个不同图形的节点分配给各自邻接矩阵的同一相对定位，前提是这些节点在图形内的结构角色相同。对给定的图形集合，PATCHY-SAN（选择组装-正则化）对每个图形都采用了以下步骤：(1)从图形中挑选一个长度固定的节点序列；(2)对选中的序列，将其所有节点组装为固定大小的邻域；(3)将提取后的邻域图正则化；(4)对于由此得来的区域序列，通过卷积神经网络学习邻域表示。
接下来，我们会一一介绍解决上述问题的方法。
4.1. 节点序列选择
算法1 SELNODESEQ: 选择节点序列
选择节点序列是面向各个输入图的辨识过程，其辨识的是构建感受域的节点序列。算法1列举了一个这样的选择过程。首先，根据给定的图形标识将输入图的顶点分类。接着，利用给定的卷积步长s遍历，得到节点序列。对每个访问过的节点，用算法3构建感受域，直至感受域w全部构建完毕。相对于选中的节点序列，卷积步长s决定了创建一个感受域时两个连续节点的距离。如果节点的数目小于w，为了间隔考虑，该算法会构建全零的感受域。挑选顶点序列可能有多种可选的方法。比如根据图形标识的值深度优先遍历输入图。我们将在今后的论文中探讨这些方法。
4.2. 邻域组装
算法2：NEIGHASSEMB: 领域组装
以上步骤辨识的每个节点都必须构建一个感受域。算法3首先需要算法2组装输入节点的局部邻域。邻域的节点是感受域的候选集。算法2列举邻域组装步骤。已知输入一个节点v以及感受域的大小k，选择过程会执行广度优先搜索，以一个和节点v相距越来越远的距离探索顶点，并将这些顶点添加到一个N集上。如果集合的节点数目小于k，就会收集大部分新近添加到N的顶点1-邻域，直到至少数目为k的顶点都已经进入N为止，或者直到再也没有邻域添加到N。请注意，在这种情况下，N的大小可能不等于k。
4.3. 图像正则化
图3：每个图形都会执行正则化，感应到一个根节点v的邻域上(红色节点；节点颜色表示了到根节点的距离)。一个图形标签用于对节点进行评级，并创建正则化感受域，节点属性之一的大小k (这里: k = 9) 和边缘属性之一的大小k × k 。正则化还包括过量节点和虚拟节点的填充。每个顶点（边缘）属性对应一个带有各自感受域的输入通道。
算法3：RECEPTIVEFIELD: 创建感受域
算法4：NORMALIZEGRAPH: 图形正则化
对上一步组装的邻域进行正则化，就可以构建一个节点的感受域。如图3所示，正则化赋予邻域图的节点一种顺序，以便进行从无序图形空间到线性顺序向量空间的映射。基本设想是利用图形标识过程，即使是两个不同图形的节点，只要节点在图形内的结构角色相同，就将它们分配给对应邻接矩阵相同的相对定位。为了实现这种设想，我们给优化图形正则化的问题下了定义，旨在寻找相对给定图形集合而言最适合的标识。
问题1（优化图形正则化）。在以下公式中，G是k个节点未标识图形的集合，l是一个单射图形标识过程，dG是有k个节点的图形的距离度量，是k × k矩阵的距离度量，可以根据公式得出 。
.
这里的问题可以归结为，对于任意两个从中随机统一绘出的图形，可以预计到图形在向量空间的距离（有关基于l的邻接矩阵），而图形在图形空间的距离又是最小的，找出一个图形标识过程l。优化图形正则化的问题是对典型的图形规范化问题做一个总结。不过，典型标识算法只针对同构图才有优化效果，对那些可能相似但并非同构的图形，可能效果不佳。优化正则化问题的预期值越低，标识就能让节点与相似的结构角色匹配得越好。请注意，相似性是由dG决定的。
对于优化正则问题的复杂性，我们得到以下结论：
推论1 优化图形正则化是NP难题。
证明方法：减少子图同构，PATCHY-SAN并未解决以上优化问题，而是可能对比不同的图形标识方法，然后选择对给定图形集合而言最适合的方法。
推论2 在以下公式中，G是图形集合，(G1, G0 1), ...,(GN , G0 N)是图形对的序列，那些图形来自G，是随机且独立的统一抽样结果。
已知θˆ` := PN i=1 dA A`(Gi), A`(G0 i) /N，并且θ` :=E G dA A`(G), A`(G0) − dG(G, G0) 。如果dA ≥ dG，只要θ`1 < θ`2，则EG[θˆ`1] < EG[θˆ`2]。
有了推论2，我们能以未经监督的方式，通过对相关估算的对比，比较不同的标识过程。在dA ≥ dG的前提下， 
的估算值越小，绝对差越小。因此，我们可以简单选择 
最小的标识。仍然以dA ≥ dG为前提举例。编辑图形距离和邻接矩阵的汉明距离。最后要注意，所有上述演算结果都可以延用在有向图上。
就本文主张的方法而言，其核心内容就是图形正则化问题，以及应用局部图形结构正则化适合的图形标识过程。在PATCHY-SAN框架内，我们进行一个顶点v的邻域图正则化。顶点的标识因此受限于v的图形距离：对任意两个顶点u和w，假如u比w更接近v，那么v的排名就始终高于w。这样的界定能保证v始终排在第一位。在G中，一个顶点越靠近v，其在向量空间表示中的排名就越高。
大部分标识方法都不是单射的，因此有必要打破同一标识节点的联系。为此，我们采用了NAUTY（McKay 与Piperno，2014年）。NAUTY将此前的节点划分视为输入，通过选择按字典序最大的邻接矩阵打破了现有的联系。对有界度的图来说，图形同构是在PTIME时刻（Luks，1982年）由于邻域图的大小恒定为k，此算法在多项式时间内以原始图大小运行，平均线性时间为k（Babai等人，1980年）。我们的实验证实，计算图形邻域的典型标识增加的功耗微乎其微。
算法4列举了正则化过程。如果输入集U的大小超过k，该过程首先应用在基于l的排名，以便选择排名最高的那些k节点，并重新计算较小节点集的排名。如果U的大小不及k，该过程就增加不连通的伪节点。最后，它会导出顶点N的子图，将以排名r作为此前着色的图形规范化。
我们能按照下面的方法将PATCHY-SAN 结构关联到卷积神经网络上。
定理3. 给定一个图形的像素序列。将 P大小为(2m – 1)2，幅度为s，没有零填充，以及1-WL标准化感受域的ATCHY-SAN架构应用到上序列上，和大小为(2m – 1)，幅度为s，没有零填充感受域的卷积神经网络第一层是一样的。（相当于固定序列感受域）
证据：有可能显示出，如果一个输入图形是一个正方形网格，那么之后为顶点构建的1-WL正则化感受域将始终是一个按照独特顶点顺序，且有着独特正方形网格图形。
4.4. 卷积架构
PATCHY-SAN能够处理顶点和边缘属性（离散的和连续的）。设av是顶点属性的数量，设ae是边缘属性的数量。对于每一个输入图形G，它都适用于顶点和边缘，结果就是一个 (w, k, av) 和一个 (w, k, k, ae) 张量。这些可以被重塑到一个 (wk, av) 和一个(wk2, ae) 张量上。请注意，av 和ae 都是输入渠道的数量。我们现在可以将大小设为k的跨越和感受域的1维卷积层应用到第一个张量，把k2应用到第二张量。其余的架构可以被任意选择。
我们可以使用合并层去整合分别代表节点和边缘的卷积层。
五、复杂性和实现
图4：在不同图形上感受域的每秒处理速率
PATCHY-SAN创造感受域的算法效率非常高，而且也是原生并行化的，因为感受域是独立生成的。我们可以展示以下渐近的最坏结果。
定理四. 把N设为图形数量，把K设为感受域大小体积，把W设为宽度，还有O(f(n, m))函数化了为一个n个顶点和m个边缘的图形计算指定标签复杂度。对于计算N图形的感受域来说，PATCHY-SAN有一个最差复杂度函数O(Nw(f(n, m) + nlog(n) + exp(k)))。
证明: 节点序列选择需要每个输入图形的标签和k最高排名的节点检索。对于正则化图形补丁的创建，绝大多数计算工作都花费在了将标签过程应用在一个大小可能比k大的邻域上。将d设为输入图形G的最大度，将U设为由算法2返回的邻域。我可以得到 |U| ≤ (k − 2)d ≤ n. 函数exp(k)来自于在一个K节点图形上最图形正则化算法NAUTY最坏情况下的复杂度(Miyazaki, 1997)。
举个例子，对于Weisfeiler-Lehman算法来说，它有一个O((n + m)log(n)) 复杂度 (Berkholz 等人, 2013)，还有常量w <n 和 k <n，PATCHY-SAN复杂度就是在N内的线性化，以及在m和n中的非线性化。
六、实验
我们进行了三种类型的实验：一个运行分析，一个学习功能的定量（定性）分析，还有在基准数据集上的图形内核比较。
6.1. 运行分析
通过将PATCHY-SAN结构应用在真实世界的图形中，我们评估了它的效率。目标是对比感受域被生成的等级和最先进的卷积神经网络表现的学习等级。所有输入图形都是Python模块GRAPHTOOL1集合的一部分。对于一个指定图形，通过利用标准化一维Weisfeiler-Lehman (1-WL)算法，我们使用PATCHY-SAN结构来计算所有节点的感受域(Douglas, 2011)。环面（torus）是一个带有1万个节点的周期性晶格；随机（random）是一个带有1万个节点和一度分布P(k) ∝ 1/k and kmax = 3的随机无向图；电网（power）是一个美国地区电网拓扑结构的网络；polbooks是polbooks是关于2004年美国总统大选书籍的一个联合购买网络； 优先（preferential）是一个优先连接网络模型，新加入的顶点有3度；astro-ph 是一个合著网络，上面有很多来自提交天体物理论文预印本的平台arvix的作者(Newman,2001);email-enron 是一个交流网络是由近50万封已发送的电子邮件生成的(Leskovec et al., 2009)。所有实验都是在一个有64G RAM和2.8GHz独立处理器的商用硬件上。
图4描绘了感受域在每秒时间里是如何对每个输入图形进行评级的。对于大小k = 5和k = 10的感受域，PATCHY-SAN 创建的域的评级速率超过1000/s，除了email-enron 的速率分别是600/s和320/s。 一个有2卷积和2致密层的卷积神经网络可以在同样的机器上，以每秒200-400个训练样子速率进行学习。因此，感受域所产生的这个速率对于一个下游卷积神经网络而言完全足够了。
图5：受限玻尔兹曼机可视化功能可以和1维WL（大小为9的正则感受域），一个有线连接图形（Barabasi & Albert ´ 1999, 左下），一个联合采购政治书籍网络(右上)，一个随机图形（右下）一起学习，这些带有100个节点的图形实例被描绘在左边。一个功能可视化表现的权重（像素越暗，相应的权重就会越高）和3个样例图形都取自受限玻尔兹曼机（通过设置除了隐藏节点相应的全部功能为0）。在相邻矩阵中，黄色节点已经被有了位置1（建议看彩色图形）
6.2. 功能可视化
可视化实验的目标，就是要定性调查无监督特质学习热门模型，比如受限玻尔兹曼机(RBM) (Freund & Haussler, 1992) 是否能够被整合到PATCHY-SAN 结构里。对于每一个输入图形，我们已经为所有阶段生成了感受域，并把这些用于是受限玻尔兹曼机的输入香。受限玻尔兹曼机有100个隐藏节点，结合对比分歧差异，它以0.01的学习速率被分成30个时期进行训练。针对大小为9标准化感受域的1维Weisfeiler-Lehman算法(1-WL)，通过一个单层受限玻尔兹曼机，我们实现了功能可视化。值得注意的是，通过受限玻尔兹曼机学习的功能，相当于感受域类型在发生。图5描绘了部分功能和样例，它们都是从四个不同图形中抽取的。
6.3. 图形分类
图形分类是指将图形分配到多个类型中的一个的问题。
表1: PATCHY-SAN架构数据集合属性和准确度及时间结果（按秒），以及图形内核的四种状态。
表2：在社交图形上的准确度比较结果
数据集。依靠先进的图形内核，我们使用了六个标准基准数据集来对于运行时间和分类准确度，它们分别是：MUTAG, PCT, NCI1, NCI109, PROTEIN, 以及D&D。 MUTAG (Debnath 等人, 1991) 是一个188硝基化合物数据集合，类别可以指出化合物对细菌的诱变效应。PTC由344个化学化合物组成，类别可以指出雄性小白鼠和雌性小白虎的致癌性(Toivonen等人, 2003). NCI1和NCI109 是化学混合物，可以按照非小细胞肺癌和卵巢肿瘤细胞进行筛选(Wale & Karypis, 2006). PROTEINS是一个图形集合，节点是二级结构元素，边缘指示氨基酸序列里或是3D空间里的邻域。Graphs可以按照酶或非酶被归类。D&D是1178蛋白质结构的数据集(Dobson & Doig, 2003) ，可以按照酶和非酶被分类。
实验设置. 我们比较了带有最短路径内核（SP）的PATCHY-SAN结构(Borgwardt & Kriegel, 2005)，随机游走内核 (RW) (Gaertner 等人., 2003)，图形计数内核 (GK) (Shervashidze 等人, 2009)，以及Weisfeiler-Lehman子树内核(WL) (Shervashidze 等人, 2011)。和之前的工作类似 (Yanardag & Vishwanathan, 2015), 我们把WL的高度参数设为2，GK的图形体积大小设为7，然后从{10−6, 10−5, ..., 10−1}中为随机游走内核（RW）选择选择衰弱因子。我们利用LIB-SVM进行了十倍交叉验证(Chang &Lin, 2011)，使用九倍交叉验证进行培训，一倍用于测试，并且重复试验了十次。我们汇报了平均预测准确度和标准偏差。
对于PATCHY-SAN 结构(也被称为PSCN)来说，我们使用了1维WL正则化，一个宽度w等于节点平均值（见表1），感受域大小是k = 5和k = 10。对于试验，我们只是有了节点属性。此外，我们还在k=10的条件下进行了试验，我们使用了合并层(k = 10E),为节点和边缘整合了感受域。为了做出一个较为公平的比较，我们使用了一个单一网络架构，它有两个卷积层，一个致密隐藏层，以及针对所有试验的softmax层。第一个卷积层有十六个输出信道（特征映射）。第二个卷积层有八个输出信道，一个大跨越到s = 1，域大小定为10。卷积层具有可调整的线性单元。致密层有128个可调整的线性单元，丢码率为0.5。丢码和神经元的数量相对较少，需要避免过度拟合较小的数据集合。我们唯一优化的超参数是针对迷你梯度下降算法RMSPROP的时期数量和批量大小，上面提到的所有这一切都是结合THEANO (Bergstra等人., 2010)和KERAS (Chollet, 2015)执行的。同时在k = 10的批量处理中，我们还应用了一个逻辑回归（PSLR）分类器。
不仅如此，我们用同样的设置2 在更大的社交图形集合上进行了实验（每个集合最多有1.2万个图形，平均400个节点），根据之前图形计数（GK）和深度图形计数内核（DGK）汇报的结果，我们和PATCHY-SAN进行了比较(Yanardag & Vishwanathan, 2015)。我们使用了正则化节点度作为属性，突出了其优势之一：它可以轻松地整合进行连续功能。
结果. 表1列出了实验结果。我们忽略了NCI109的结果，因为他们和NCI1的结果几乎一模一样。尽管使用了一个通用的卷积神经网络架构，但是，现有图形内核的卷积神经网络的准确度还是有很强竞争力的。在绝大多数情况下，一个感受域体积里的10个结果都被分到了最适合的类别里，分类准确度也是最好的。相对较高的方差可以用小规模的基准数据集合来解释，事实上，卷积神经网络的超参数（时期和批量处理大小除外）无法调准到个体数据集合。与图形和文本数据的实验相似，在处理大数据集合时，我们期望PATCHY-SAN能够表现的比绝大多数大数据集合要更好。不仅如此，相比于绝大多数图形内核（WL），PATCHY-SAN的效率能够提升2-8倍。对于海量图形的数据集合，我们期待能够获得更加显著的性能优势。中介度中心性正则化的结果，其实和运行时间异常非常相似，大概只有10%的差异。逻辑回归应用在PATCHY-SAN的感受域上表现的不好，甚至更差，这说明PATCHY-SAN在和卷积神经网络一起使用的时候效果会很好，卷积神经网络可以学习非线性功能整合以及在各个感受域上分享权重。
在社交图形数据上，PATCHY-SAN 同样具有很强的竞争力。相比于其他六个数据集合中的四个双内核，它明显更好，并且实现了其他数据集合的联系。表2罗列了试验的结果。
七、结论和未来工作
我们提出了一个学习图形表现框架方法，当和卷积神经网络连同协作时能发挥更大作用。它结合了两个互补程序: (a) 选择一个可以覆盖图形大部分区域的节点序列，以及(b) 对序列中的每个节点，生成本地标准化邻域表现。实验表明，这种方法在最先进的图形内核状态下是具有竞争力的。对于未来工作的方向，包括替代神经网络结构的使用，比如循环神经网络（RNN）；整合不同的感受域大小；结合受限玻尔兹曼机(RBM)和自编码器进行训练；以及基于该方法理念的统计关系模型。
Via PDF
雷峰网原创文章，未经授权禁止转载。详情见转载须知。
