本文要介绍的论文是ICML2016的CNN在图上的应用文章。ICML是机器学习领域的顶级会议，而这篇文章的内容——<>——也具有很好的理论和实践价值。如果你对图的数据结构不是很熟悉，建议你参考文末相关基础知识的介绍。CNN在计算机视觉（CV）和自然语言处理领域达到了state-of-art的水平。其中的数据可以称为一种欧几里德数据。CNN可以高效地处理这种数据结构并探索其所代表的特征。所谓欧几里德（Euclidean）数据，是指类似于网格、序列……的数据。例如，图像可以看作是二维网格数据，语音信号可以看作是一维网格数据。然而在实际处理问题中仍然存在大量的非欧数据，如社交多媒体网络（SocialNetwork）数据、化学成分（ChemicalCompound）结构数据、生物基因蛋白质（Protein）数据和知识图谱（Knowledge图）数据等。此类数据属于图结构数据。CNN等神经网络结构无法有效处理此类数据。因此，本文要解决的问题是如何利用CNN高效处理图结构数据。本文提出的算法思路很简单。它将图结构的数据转换成CNN可以高效处理的结构。处理过程主要分为两步：1.从图结构中选择一个具有代表性的节点序列；2.为每个选中的节点找到一个卷积邻域（neighborhoodfield）。接下来我们详细介绍算法相关的细节。本文将一幅图像看成一个特殊的图，即网格图，每个像素是图中的一个节点。那么我猜测文章的动机主要是想把CNN在图像上的应用推广到一般的图上。那么我们先来看看CNN在Image中的应用。如图3所示，左图展示了图像在神经网络层的滚动操作过程。最底层是输入的featuremap（或原图），通过一个卷积（这里表示的是一个3*3的卷积核，也就是文章中的receptivefield=9），卷积后输出一个Featuremap。如图3中的卷积运算所示，底层的9个像素被加权映射到上层的一个像素；看图3右图，它以图形的方式展示了左图下方的输入数据。任意一个卷积区域都可以看作是一个中心点的一个节点及其域内的节点集合，最终得到的加权图就是一个值。因此，底部的输入featuremap可以看成是：确定一个正方形网格图中的一些节点列来表示图像，并构造一个正则化的邻域图（而这个邻域图就是卷积核的面积，aka知觉场）。这样解释，如论文中的图1所示，一张4*4大小的图像实际上可以表示为一个有4个节点（图中的1,2,3,4）的图（graph），其中每个节点还包括一个与卷积核（neighborhoodfield）大小相同的邻域。那么，这个图像（image）的卷积其实就是这4个节点组成的图（graph）的域的卷积。那么，对于一个一般的图数据，只需要选择其中的节点，求解得到它相关的固定大小（与卷积核大小相同）的域，就可以使用CNN卷积得到的特征表示图。需要注意的是，图4(b)所示的是(a)中某个节点的邻域，这个感知场按照与卷积核从左到右、从上到下相同的顺序映射到一个卷积核上bottom根据空间位置向量的大小，然后进行卷积。但是在一般的图集中，图像中没有空间位置信息。这也是图数据处理过程中需要解决的问题。基于以上描述，论文主要做了三件事：1.选择合适的节点；2.为每个节点建立邻域；3.建立从图表示到向量表示的单一映射，保证结构特征相似的节点可以映射到向量中相似的位置。该算法具体分为4个步骤：1.图中顶点选择中的NodeSequenceSelection。首先，对于输入图，需要确定宽度w（在算法1中定义），它表示要选择的节点数。其实就是感知域的个数（其实就是说每次对一个节点的感知域进行卷积，卷积stride=kernelsize）。那么具体如何选择节点呢？其实论文里说的是根据图中节点的排序标签来选择，但是这篇文章并没有更多介绍如何排序。主要采用的方法是：centrality，即集中的方法。个人理解是越中心的点越重要。这里的中心位置不是空间概念，而是衡量点与点之间关系重要性的概念。让我用一个简单的例子来说明。图5中的两张图其实代表的是同一张图，我们比较的是标红的两个不同节点的中心位置关系。在比较过程中，我们计算节点与所有其他节点之间的距离关系。我们假设相邻两个节点之间的距离为1。那么对于图5中左图中的红色节点，有4个节点与其直接相连，所以距离为+4；再远一点的是与其邻接点相邻的3，距离+6；依次相邻有3个+9；最后还有一个最远的+4；所以我们知道节点的总距离为23。同理，我们得到右边节点的距离为3+8+6+8=25。那么很明显在选择节点的时候会先选择左边的节点。当然，这只是一种排序和选择节点的方法，它的问题也很明显。论文在这项工作中没有给出详细的解释。2.找到节点域的邻域集合接下来，为每个选定的节点确定一个接受域，进行卷积运算。然而，在此之前，首先找到每个节点的邻域域，然后从中确定感知域中的节点。假设感知域的大小为k，对于每个Node显然有两种情况：邻域内k个节点不够，或者邻域点过多。这将在以下章节中解释。如图所示，选择了6个节点。对于每一个节点，首先找到它的直接相邻节点（称为1-neighborhood），如果不够，再添加间接相邻节点。然后对于1-neighborhood就够的情况，先把它们都放到候选区，下一步通过归一化做最后的选择。3.图归一化过程GraphNormalization假设在上一步的NeighborhoodAssemble过程中，一个节点得到一个域，共有N个节点。那么N的个数可能不等于k。因此，normalize的过程就是选择带有排序标签的，按照这个顺序映射到vector中。如果该节点的邻居节点个数不足，则直接全选，不足以填充dummy节点，但仍需排序；如果超过N，则需要按照排序截断后面的节点。如图7所示，展示了从节点选择到求解感受野的整个过程。Normalize排序后，可以映射到一个vector。因此，这一步最重要的就是对节点进行排序。如图8所示，它代表了对任意节点求解其感受野的过程。这里卷积核的大小是4，所以最后必须选4个节点，包括节点本身。因此，需要对这些节点进行标记（labeling）。当然，方法有很多种，那么什么样的标注方法最好呢？如图7所示，实际上，从这7个节点中选取4个节点，就会形成一组包含4个节点的图。作者认为，在某个标签下，从集合中随机选取两个图，计算它们的图在向量空间中的距离与图在图空间中的距离之差的期望值。如果期望值越小，说明标签越好。好的！具体表达如下：得到最佳标签后，可以将节点依次映射到一个有序向量，得到节点的感受野，如图6最右所示。4.卷积网络structureConvolutionalArchitecture文章使用了一个2层的卷积神经网络，将输入转化为向量vector后可以进行卷积运算。具体操作如图9所示。首先，最下面的灰色方块是网络的输入，每个方块代表一个节点的感受野区域，也就是前面解得到的4个节点。其中，an表示每个节点数据中的一个维度（如果节点是彩色图片，就是3维；如果是文本，可能是词向量……这里表示数据的维度是n).粉红色的代表卷积核。核的大小为4，但宽度必须与数据维度相同。因此，在每个节点体积季度后获取一个值。卷积步长（stride）为4，表示每次卷积为1个节点，stride=4只是下次跨到下一个节点。（注：论文中图1中，（a）中stride=1，但转换为（b）中的结构后stride=9）。卷积核的个数为M，表示卷积后得到的featuremap的通道数为M，所以最终的结果为V1...VM，即为map的特征表示。有了它，就可以执行分类或回归任务。基本题：图的基本概念：主要由顶点和边组成，有一个邻接矩阵A，如果其中的节点特征化（Feat），如右图所示。
