Learning Convolutional Neural Networks for Graphs

图卷积网络(Graph Convolutional Network),顾名思义,就是把图像处理中的卷积层运用到图上,图卷积网络能够处理如下两类问题[1]——

  • 给定一系列图作为训练集,可以训练出一个函数,该函数能够对未知的图进行分类或回归。
  • 给一张很大的图,学习图的表示函数(representation),并对于未知的图,推导出一些性质,诸如判断一个节点的类型,或是消失的边权等等。

回顾卷积神经网络,一个像素的特征值,来自于该层输入中,这个像素空间上临近点的像素特征。卷积神经网络的成功,从某种意义上来说,正式借助了这种隐含的空间特征。对于NLP也是同理

但是,对于大部分图而言,并没有这么好的特征可以利用,要将CNN迁移到图上面,需要解决这两个问题——

  • 找到一部分中间点,这些中间点将各自总结其邻域节点的特征。
  • 计算每个中间点临近图的正则化表示,即向量空间中的一个可以编码这个图的表示

定义术语

首先,需要定义图的节点的标号(labeling)和排名(ranking)。标号是一个给图上每个节点赋予一个权值的映射l(u)。而排序是将图上每一个节点权值从小到大排名后的排名映射r(u)。即满足对于任意u, v \in Vr(u)<r(v)当且仅当l(u)>l(v)

倘若r(u)函数和l(u)函数都是单射的,那么使用r(u)对于图中的节点编号进行置换,可以得到A^l(G)

上述定义其实是有道理的,假设l(u)是一个能够描述节点位置的函数,那么使用r(u)映射后的图G'可以用来当做一个图的标准化(Canonicalization)结构,这个结构能够用来比较两个图是否同构(Isomorphism)。

l(u)的最优化是NP的,但是可以构造出相对有效的l(u)——用距离“中心节点”的距离函数作为l(u),这里的“中心节点”是Node Sequence Selection函数的结果。

算法流程

Node Sequence Selection

为了对图进行卷积操作,我们需要定义卷积的stride和width。实际的算法非常简单,既然我们假设了r(u)函数能够有效刻画节点空间位置,那么在按照r(u)排序后的节点序列中,使用一个width大小stride步长的滑动窗口就可以完成节点的选择了。

Neighborhood Assembly

这一个步骤,试图对于上一步得到的若干个节点,分别找到一个大小为k的领域,这里用了简单的广度优先搜索算法。

Graph Normalization

图的规范化操作使用上一步得到的中心节点及其领域,重新对于领域中的节点进行标号,进而通过标号的排名进行置换,此时的图就相对规范了。由于距离不是单射函数,所以文中引用了NAUTY的方法,对于同样距离的节点进行区分。

Convolutional Architecture

文中的模型能够同时处理点权和边权,仅需要改变CNN的stride参数即可,具体实现略

评价

  • 没有公开代码,可复现性存疑
  • 适合作为GCN的入门论文,但和现在主流的GCN不一样。

引用

  1. Niepert M, Ahmed M, Kutzkov K. Learning convolutional neural networks for graphs[C]//International conference on machine learning. 2016: 2014-2023.

发表评论

电子邮件地址不会被公开。 必填项已用*标注

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据