论文标题：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）。

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

二、方法

给定图数据的集合，PATCHY-SAN按照以下步骤进行处理每个图：

①从图中选择一个固定长度的节点序列；

②在选定的序列中为每个节点分配（assemble）一个固定大小的邻域；

③将提取的邻域图标准化；

④使用卷积神经网络学习邻域表示。

1. 节点序列选择

                                                Algorithm 1

创建感受野的Algorithm 3如下：

                                                 Algorithm 3

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提供一种度量的标准来对比不同的图标记程序，然后挑选最优的：

4. 卷积架构

三、实验

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

1. 效率

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

                                                 效率

2. 性能

                                                     性能

                                                        性能