论文笔记之Learning Convolutional Neural Networks for Graphs

这篇论文发表于2016年的ICML会议，并涉及领域方面的相关研究。针对如何将卷积神经网络应用于图结构数据这一问题，提出了一种创新的方法论。

架构：

具体而言，在本方法中，我们采用w个大小固定的子图（每个子图的大小为k+1）来表征输入图的信息；随后对这些子图进行规范化处理，并将它们拼接成一个w×(k+1)维向量作为传统CNN模型的输入进行学习训练。这一过程实现了图结构信息到向量表示的有效转换。

---

算法流程
输入：任意一张图
输出：每个channel输出w个receptive field

Step1： graph node labeling（对图中的各个节点进行标记化处理, 其中一个典型的方法是基于节点度值来进行标记, 这种做法也可称为color refinement technique或vertex classification method）
文中采用了Weisfeiler-Lehman algorithm来进行图划分. 通过这一算法, 可以获得每个节点对应的 rank 值（确保不同 graph 结构具有统一的标准组织方式）

Step2： 对经过标记后的节点进行排序，并选取排序后的前w个节点作为后续处理的对象（从而将大小不一的图转换为相同尺寸）。如果输入中的节点数量少于w，则在输出结果中添加全零填充层（即padding）。

Step3： 通过设置stride=s进行遍历这些节点。其中当s=1时（或文中s=1），为了确保输出具有w个receptive field，在step2中进行补充处理。

Step4： 对遍历过程中的每个节点v（称作root），利用广度优先搜索算法获取该节点的所有直接邻居；若不足k个，则继续对这些直接邻居的所有直接邻居进行探索；直至收集到足够的k个邻居或所有可能的邻居都被探索完毕；之后将此root与其所收集到的k个邻居一起构建了相应的邻域图

Step 5: 在 step 4 完成后会生成 w 个（s=1）的邻域图谱（neighborhood graphs）。接下来需要对这 w 个图谱进行标记（labeling），并根据 root 节点 v 的远近关系评估每个节点的排名（rank）。根据算法 4 的规定是距离 v 越近则 rank 值 r 越小。如果某个邻域图谱包含的节点数量少于 k 个，则需要用虚拟节点（0-node）来进行补充

Step6：

通过这w个receptive field就能得到一个w(k+1)维的向量