论文标题：Learning Convolutional Neural Networks for Graphs
论文链接：https://arxiv.org/abs/1605.05273
论文来源：ICML 2016

一、概述

在这篇论文中，我们的目的是将卷积神经网络应用于大量的基于图的学习问题。考虑以下两个问题：
①使用图的集合作为训练数据，来实现未见图上的分类和回归问题，例如，集合内的每个图可以模拟一个化合物，输出可以是一个函数，将未见化合物映射到它们对抗癌细胞的活性水平；
②对于一个大的图，可以学习图的表示来用来推断未见图的属性，比如节点的类型和缺失的边。

本文提出的PATCHY-SAN适用于处理这些问题，所面对的图数据可以是有向图或者无向图，图的节点和边可以有离散或者连续的属性并且可以有多种类型的边。

一张图片可以认为是一种特殊的图，即grid图，它的节点代表像素。在处理图像数据时，CNN处理的过程可以理解为：
①在一个节点序列上进行移动（下图(a)中的1-4节点）；
②生成这些节点的固定大小的邻域图（下图(b)中的grid）的过程。

CNN处理grid数据

这里的邻域图相当于感受野。上图(b)表示的是将这个邻域图从图的表示转化为向量表示的过程，这个过程也就是按照从左到右、从上到下的顺序将邻域图展平即可，然后将这个向量加权累加得到卷积后的结果。

由于图像数据存在天然的空间顺序，因而节点序列创建邻域图的顺序（也就是卷积核移动的顺序）总是从左到右、从上到下，然而在图数据中，图没有固定的空间顺序，而且不同的图可能有不同的拓扑结构。

类比上述CNN处理图像的过程，使用CNN来处理图数据可以分为以下两个类似的步骤：
①决定用于生成邻域图的节点序列；
②计算一个标准化的邻域图，也就是从图的表示到向量空间表示。

本文提出的PATCHY-SAN架构就用来实现上述的过程，其大体的流程如下图所示：

PATCHY-SAN

PATCHY-SAN有以下几个优点：
①它是高效的，天然能够并行化，并且适用于大型图；
②对于从计算生物学到社会网络分析的许多应用来说，将网络的可视化是很重要的，PATCHY-SAN支持特性可视化，能够观察图的结构属性；
③PATCHY-SAN学习 application dependent的特征，而不需要进行特征工程（feature engineering）。

PATCHY-SAN利用图标注（graph labeling）程序来为图的节点施加一个顺序。一个图标注程序是一个函数，一个从映射到的函数，是一个有序集合（ordered set），元素可以是实数或者整数。另外，一个ranking（或者叫coloring）是一个函数。我们利用图标注程序对图的节点进行标注，然后根据标注结果进行排序得到节点的ranking，规则是当且仅当。如果是单射的，那么图的ranking就是唯一的，按照这样的ranking组织的邻接矩阵也是唯一的。另外，图标注程序也表明了图的一个划分（partition），也就是当且仅当。

图标记程序的例子有在网络分析中常用的节点度和其他中心性（centrality）度量。比如节点的betweeness centrality度量是计算通过的最短路径的分数。总之图标记的方法有很多种，本文中并未详述采用的图标记方法。

二、方法

给定图数据的集合，PATCHY-SAN按照以下步骤进行处理每个图：
①从图中选择一个固定长度的节点序列；
②在选定的序列中为每个节点分配（assemble）一个固定大小的邻域；
③将提取的邻域图标准化；
④使用卷积神经网络学习邻域表示。

1. 节点序列选择

Algorithm 1表示如何选择节点序列，其中表示要选择的节点个数，这里的stride 代表步长，如果创建的感受野数量少于（原因是因为），那么要为选择到但未被创建感受野的节点创建全0感受野：

Algorithm 1

创建感受野的Algorithm 3如下：

Algorithm 3

2. 邻域图的分配

Algorithm 1中需要为节点创建感受野，需要Algorithm 2应用广度优先搜索来获取节点的邻域节点，搜索距离越来越远的节点，并将这些节点添加到集合中作为候选（节点数量可能大于感受野大小）：

Algorithm 2

3. 图的标准化

对于每个节点分配的邻域图需要进行进一步的标准化，标准化的过程为邻域图的节点施加了一个顺序，以便于能够将邻域图从图的表示转换到向量空间表示，下图展示了这个过程：

图的标准化

算法Algorithm 4如下：

Algorithm 4

从整个算法中可以看出来图标记程序起到了非常关键的作用，可以认为一个图标记程序的效果好坏直接关系算法的性能。图标记程序的原则是当且仅当两个不同图的节点在图中的结构角色（structural role）相似时，将它们分配到各自邻接矩阵中相似的相对位置。那么怎么定义一个比较好的图标记程序呢？本文定义了最优图标准化问题（optimal graph normalization problem）来求解一个最优的图标记程序：

代表有个节点的无标注图集合，表示一个单射的图标注程序，代表有个节点的图的距离度量，代表矩阵的距离度量，最优的图标记程序就是：

求解的过程也就是寻找一个图标记程序，满足任意两个从中采样的图，向量空间中图的距离(关于基于的邻接矩阵)与图空间中图的距离之间的期望差异是最小的。

这样的求解方法符合前面提到的图标记程序的原则，代表图的距离度量，可以采用图的编辑距离，来衡量邻接矩阵的相似度，可以采用邻接矩阵的汉明距离。

最优图标准化问题是经典图规范化问题（graph canonicalization problem）的一种推广。然而，规范标注算法只适用于同构图，对于相似但非同构的图可能表现不佳。

虽然上面给出了如何求解一个最优的图标记程序，但是事实上这是一个NP-hard的问题。PATCHY-SAN并不能解决这个NP-hard的问题，也就是说最优的是求不出来的，不过PATCHY-SAN提供一种度量的标准来对比不同的图标记程序，然后挑选最优的：

代表有个节点的无标注图集合，是一个序列，这里面的图的pair都是从中随机采样出来的。另外有

以及

如果，那么当且仅当。

上述定理可以使我们比较不同的图标记程序时使用无监督的方式进行，在假设下，估计量越小，就会越小，因此我们会选择最小的图标记程序。假设是可以成立，在采用图的编辑距离，采用邻接矩阵的汉明距离时即可成立。说明一点，上述方法可以拓展到有向图。

图的归一化问题以及在邻域图结构的标准化中应用适当的图标记程序是本文方法的核心。在Algorithm 4中对节点进行标准化时还要受限于节点与的距离，对于任意两个顶点，如果比更接近，那么的ranking总是比高，在Algorithm 4用来表示这样的排序方式。这样的限制确保总在ranking为的位置，并且离越近的节点，在向量空间中的ranking就会越高。

4. 卷积架构

PATCHY-SAN能够既能够处理节点特征也可以处理边的特征，使用代表节点属性的数量（也就是特征的维度），代表边属性的数量，那么对于每个输入图，按照前述算法应用标准化感受野以后会得到两个tensor，形状分别为和，这两个tensor可以reshape成和形状的tensor，这里和就相当于input channel的数量，然后对两个tensor分别应用卷积核感受野大小、步长分别为和（感受野大小与步长一致）的1D卷积操作。

三、实验

简单展示一下一部分实验的效果，具体实验设置参看原文。

1. 效率

下图表示了利用前述算法在不同数据上生成感受野的效率：

效率

2. 性能

性能

性能