introduction

• 本$paper$paper将图像（$image$image）看作是一种特殊的图（$graph$graph），即一种$grid\ graph$grid graph，每一个像素就是$graph$graph当中的一个$node$node。对于图像来说，卷积神经网络对输入图像的局部关联的区域进行操作，和此类似，本文提出了一种通用的方法，也抽取图中局部关联的区域进行相应的操作。
• 文章的$motivation$motivation主要来自于想将$CNN$CNN在图像上的应用$generalize$generalize到一般的$graph$graph上面（将局部连接区域作为输入）。
  主要要解决$2$2个问题：
• 1.如何确定$w$w个中心节点序列并为之创建邻域？
• 2.如何一个将图表示唯一映射到一个向量表示上，使得领域图之间相似结构的节点处于向量表示中相似的位置？

同构图
Graph kernel

有哪些指标可以描述两个图（graph）的相似度？

nauty
McKay提出的首先将图表示为某种规范形式,然后再判断是否同构的著名的Nauty(no automorphisms)算法，目前最快的图同构问题解决方案Nauty通过选择词典上最大的邻接矩阵来打破相等关系

The Weisfeiler-Lehman algorithm

method

Node Sequence Selection

首先对于输入的一个$Graph$Graph，需要确定一个宽度$w$w，它表示也就是要选择的$nodes$nodes的个数。其实也就是感知野的个数（其实这里也就是表明，每次卷积一个$node$node的感知野，卷积的$stride= kernel\ size$stride=kernel size的）

1：$labeling$labeling算法确定一个$graph$graph中$node$node次序（主要采取的是中心化 的测量方式，这里的中心应该是度量一个点的关系中的重要性的概念；比如可以用$node\ degree$node degree来确定，或$betweeness\ centrality$betweeness centrality等）。

• $graph\ labeling$graph labeling（对图的节点做标记，比如可以用节点的度做标记，做图的划分，也 可以叫做$color\ refinement\ or\ vertex\ classification$color refinement or vertex classification）文中采用$The\ Weisfeiler-Lehman\ algorithm$The Weisfeiler−Lehman algorithm做图的划分。由此可以得到每个节点的$rank$rank 值（为了不同的图能够有一个规范化的组织方式）

2：排序后，取前$w$w个节点，作为要做卷积操作的的中心$node$node；若不足$w$w个节点，则在输出中加全零的$receptive field$receptivefield，相当于$0$0填充。如下图所示，$w=6$w=6，意味着我们需要从图结果中选择$6$6个$node$node做卷积操作。)
-

3：采用$stride=s$stride=s（步长）来遍历这$w$w个节点；若满足步长的不足$w$w个，则在输出中加全零的$receptive\ field$receptive field，相当于$0$0填充（同$2$2）

• 

Neighborhood Assembly

• 接下来对选出来的每一个$node$node确定一个感知野$receptive\ filed$receptive filed以便进行卷积操作。
• 遍历$w$w中每个节点（称为$root$root），采用$BFS$BFS广度优先搜索，获取对应$node$node的$1-neighborhood$1−neighborhood（即直接相邻的$nodes$nodes）；若不足$K$K个，再遍历$1-neighborhood$1−neighborhood的$1-neighborhood$1−neighborhood，直到满足$k$k个，(注意：此时可能多于$K$K个)或者所有的邻居节点都遍历完。如下图所示，为每个目标$node$node选择至少$4$4个$node$node（包括自己，$k$k即为感受野$node$node的个数），最后的结果如下：

Graph Normalization

子图规范化：对邻域集合中的节点按照标号函数k进行排序，得到接受域。那么，对于节点的属性，$k$k个节点属性值构成了一个输入通道，对于边的属性，$k*k$k∗k个属性值也构成了一个输入通道。我们可以分别用一维的卷积层来处理这两种输入通道（对于节点属性卷积层长度为$k$k，对于边属性卷积层长度为$k*k$k∗k）正则化还包括过量节点和虚拟节点的填充。每个顶点（边缘）属性对应一个带有各自感受域的输入通道。

• 从$neighborhood\ filed$neighborhood filed中选择感受野的$nodes$nodes，并确定感受野中$nodes$nodes的顺序

• 根据离$root$root节点$v$v的远近来计算每个节点的$rank$rank，对$w$w个$neighborhood\ graph$neighborhood graph进行$labeling$labeling；不足$K$K个则用哑节点（$dummy\ nodes$dummy nodes）补充

• 得到了已经$label$label好的$graph$graph，因为需要把它变成单射（$injective$injective），使每个节点的标签唯一，采用 $nauty$nauty的算法 排序；若$nodes$nodes数大于$k$k个则按排序截取前$k$k个

• 至此，通过这$w$w个$receptive\ field$receptive field就能得到一个$w*k$w∗k维的向量

$单射（injective）$单射（injective）– 指将不同的变量映射到不同的值的函数；在本文中含义即将不同节点映射到不同$label$label上

• 在某种标签下，随机从集合当中选择两个图，计算他们在$vector$vector空间的图的距离和在$graph$graph空间图的距离的差异的期望，如果这个期望越小那么就表明这个标签越好！具体的表示如下：
• 也就是说，对于$graph$graph中两个任意子图，保证其中具有相似的结构特征的$node$node可以被映射到$vector$vector当中相近的位置。
  
  得到最好的标签之后，就能够按着顺序将$node$node映射到一个有序的$vector$vector当中，也就得到了这个$node$node的$receptive\ field$receptive field。

但这被证明是一个$NP-Hard$NP−Hard问题

所以作者可以使用求近似解的方式–即$paper$paper比较了各种$labeling$labeling方法，并从其中找出最优解。具体如下：

Convolutional Architecture

$CNN$CNN的输入：经过上述步骤后，可以得到两个$tensor（w,k,a_v）$tensor（w,k,av​）和$（w,k,k,a_e）$（w,k,k,ae​）,分别对应于顶点特征和边特征；其中$a_v$av​和$a_e$ae​可以分别看成是$CNN$CNN中$channel$channel的个数

• 注释：每个子图对应两个$tensor$tensor（竖向），上面二维的即顶点特征表示，下面三维的即边特征表示；从左到右，$w$w个子图，所以分别对应$w$w个顶点特征$tensor$tensor和$w$w个边特征$tensor$tensor；其中$a_v$av​和$a_e$ae​可以分别看成是$CNN$CNN中$channel$channel的个数

文章使用的是一个$2$2层的卷积神经网络，将输入转化为一个向量$vector$vector之后便可以用来进行卷积操作了。

首先最底层的灰色块为网络的输入，每一个块表示的是一个$node$node的感知野$（receptive\ field）$（receptive field）区域，也是前面求解得到的$4$4个$nodes$nodes。其中$a_n$an​表示的是每一个$node$node的数据中的一个维度（$node$node如果是彩色图像那就是$3$3维；如果是文字，可能是一个词向量……这里表明数据的维度为n）。粉色的表示卷积核，核的大小为$4$4，但是宽度要和数据维度一样。因此，和每一个$node$node卷季后得到一个值。卷积的步长$（stride）$（stride）为4，表明每一次卷积$1$1个$node$node，$stride=4$stride=4下一次刚好跨到下一个$node$node。（备注：$paper$paper 中$Figure1$Figure1 当中，$（a）$（a）当中的$stride=1$stride=1，但是转化为$（b）$（b）当中的结构后$stride=9$stride=9）。卷积核的个数为$M$M，表明卷积后得到的特征图的通道数为$M$M，因此最终得到的结果为$V_1……V_M$V1​……VM​，也就是图的特征表示。有了它便可以进行分类或者是回归的任务了。

参考：
1、Learning Convolutional Neural Networks for Graphs
2、PPT
3、http://link.zhihu.com/?target=https%3A//github.com/tvayer/PSCN