【论文阅读】Learning Convolutional Neural Networks for Graphs

it2026-04-04 3

出版：ICML 2016 原文：http://211.81.63.130/cache/2/03/proceedings.mlr.press/cb5795e96aa42362f86e2ba3a13c32af/niepert16.pdf

卷积神经网络（CNN）可以提取图像像素点邻域的信息，从而抽取空间特征。而CNN处理的图像数据中像素点是排列成整齐的矩阵的，也就是Euclidean Structure结构。而对于graph这种拓扑结构，每个结点的度都不一样，原始的CNN就没办法处理了。这篇论文就提出了一种一般性的方法来根据邻居信息抽取特征。文章主要做了三个事情：1.从图结构当中选出具有代表性的nodes序列；2.对于选出的每一个node求出一个卷积的邻域（neighborhood field）。3. 建立graph表示到 vector表示的单一映射，保证具有相似的结构特征的node可以被映射到vector当中相近的位置。

1. Introduction

文章将CNN引入基于图（graph）的学习问题中。主要考虑了下面两个问题：

给定一组图，学习一个函数，这个函数可以被用于未知图的分类和回归问题。这一组图中任意两个图的结点不一定一一对应。给定一个大图（big graph），学习一个可以用来推断图属性的图表示。

提出了一个框架用于学习有向图和无向图的表示。与图的卷积神经网络类似，我们从输入图中构建了局部全连接邻域。这个邻域就作为CNN中的感受野。

提取拓扑图的空间特征，就是把每个顶点相邻的邻居找出来。这需要解决两个问题：

按照什么条件去找中心vertex的neighbors，也就是如何确定感受野。确定感受野之后，按照什么样的方式处理含有不同neihgbors的特征。

2. Related work

3. Background

3.2 Convolutional Neural Networks

3.3Graphs

标记和结点分区。PATCHY-SAN应用图标记（labeling）对结点进行强制排序。图标记 $l$ 是一个从一组结点 $V$ 映射到一个有序集合 $S$ 的函数 $l : V \to S$ ，S的元素可以是数字或是整数等。图标记（动词）过程就是计算图标记（名词）的过程。我们使用标记（labeling）来同时表示图标记和计算图标记的过程。排名（ranking）是函数 $r:V→{1,...,|V|}$ 。每次标记都会诱导一个排序 $r$ 并且当且仅当 $l (u) > l (v)$ 时有 $r (u) < r (v)$ 。如果图G的标记 $l$ 是单射的，就会决定G中所有节点的顺序（即没有顺序值一样的结点），并且产生G的唯一的邻接矩阵 $A^l(G)$ ，邻接矩阵中结点 $v$ 的位置是 $r (v)$ 。此外，每个图标记都会在 $V$ 上产生一个分区 ${V_1,...V_n}$ ，当且仅当 $l (u) = l (v)$ 时有 $u,v∈V_i$ 。同构和正则化。图 $G$ 的正则化图是结点顺序固定的图 $G^{'}$ ， $G^{'}$ 和 $G$ 是同构的。实践中，图正则化工具NAUTY表现出卓越的性能。

4. Learning CNNs for Arbitrary Graphs

给定一组图，文章提出的PATCHY-SAN（SELECT-ASSEMBLE-NORMALIZE）对每个图实施以下步骤：（1）从图中选择一个固定长度的节点序列；（2）在选定的序列中为每个节点聚合（assemble）一个固定大小的邻域；（3）标准化抽取的邻域图；和（4）使用卷积神经网络从得到的补丁（patches）序列中学习邻域表示。

4.1 节点序列选取Node Sequence Selection

节点序列选取是一个识别过程。对于每个输入图，为每个感受野创建一个节点序列。算法1给出了这个过程。首先，输入图的顶点根据给定的图标签进行排序。然后，使用给定的步长s遍历得到节点序列。对于每个访问到的结点，都执行算法3来构建感受野，直到精确地创建了w个感受野。如果结点的个数小于w的话，就会创建全零感受野来进行补充。

注：排序的方法：引用自：https://blog.csdn.net/zsfcg/article/details/82465973

4.2 邻域聚集Neighborhood Assemble

对于前面识别出来的每一个结点，都需要创建一个对应的感受野。算法3首先会调用算法2来生成输入结点的局部邻域。邻域中的结点是感受野的候选结点。算法2显示了邻域的生成步骤。给定一个节点v和感受野的大小k，该过程执行宽度优先搜索，搜索距离v越来越远的结点，并将这些结点添加到集合N中。如果收集的结点数小于k，则收集最新添加到N的结点的1邻域结点，依此类推，直到N中至少有k个结点，或者直到没有更多的邻居可添加。注意，此时N中结点数目可能与k不同。

4.3 图归一化Gragh Normalization

假设上一步Neighborhood Assemble过程当中一个node得到一个领域nodes总共有N个。那么N的个数可能和k不相等的。因此，normalize的过程就是要对他们打上排序标签进行选择，并且按照该顺序映射到向量当中。如果这个node的邻域nodes的个数不足的话，直接全部选上，不够补上哑节点（dummy nodes），但还是需要排序；如果数目N超过则需要按着排序截断后面的节点。如上图所示表示从选node到求解出receptive filed的整个过程。Normalize进行排序之后就能够映射到一个vector当中了。因此，这一步最重要的是对nodes进行排序。

如上图所示，表示对任意一个node求解它的receptive filed的过程。这里的卷积核的大小为4，因此最终要选出来4个node，包括这个node本身。因此，需要给这些nodes打上标签（labeling）。当然存在很多的方式，那么怎样的打标签方式才是最好的呢？如图7所示，其实从这7个nodes当中选出4个nodes会形成一个含有4个nodes的graph的集合。作者认为：在某种标签下，随机从集合当中选择两个图，计算他们在vector空间的图的距离和在graph空间图的距离的差异的期望，如果这个期望越小那么就表明这个标签越好！具体的表示如下：得到最好的标签之后，就能够按着顺序将node映射到一个有序的vector当中，也就得到了这个node的receptive field。

上图就是图的一次卷积的大致实现步骤：

第一层是在graph中选择w个中心点（红色）第二层是选择每个中心点的k个邻居第三层是将上述每一个中心点以及其邻居通过一个function进行排序，同卷积核对应位置进行加权求和实现一层卷积

4.4 卷积网络结构Convolutional Architecture

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

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