当前位置 博文首页 > 韦全敏的博客:从图(Graph)到图卷积(Graph Convolution):漫谈图
本文属于图神经网络的系列文章,文章目录如下:
笔者最近看了一些图与图卷积神经网络的论文,深感其强大,但一些 Survey 或教程默认了读者对图神经网络背景知识的了解,对未学过信号处理的读者不太友好。同时,很多教程只讲是什么,不讲为什么,也没有梳理清楚不同网络结构的区别与设计初衷 (Motivation)。
因此,本文试图沿着图神经网络的历史脉络,从最早基于不动点理论的图神经网络 (Graph Neural Network, GNN) 一步步讲到当前用得最火的图卷积神经网络 (Graph Convolutional Neural Network, GCN), 期望通过本文带给读者一些灵感与启示。
在开始正文之前,笔者先带大家回顾一下图神经网络的发展历史。不过,因为图神经网络的发展分支非常之多,笔者某些叙述可能并不全面,一家之言仅供各位读者参考:
首先要澄清一点,除非特别指明,本文中所提到的图均指图论中的图 (Graph)。它是一种由若干个结点 (Node) 及连接两个结点的边 (Edge) 所构成的图形,用于刻画不同结点之间的关系。下面是一个生动的例子,图片来自论文 [14]:
最早的图神经网络起源于 Franco 博士的论文 [2], 它的理论基础是不动点理论。给定一张图 G G G,每个结点都有其自己的特征 (feature), 本文中用 x v x_v xv?表示结点 v 的特征;连接两个结点的边也有自己的特征,本文中用 x ( v , u ) x_{(v,u)} x(v,u)?表示结点 v 与结点 u 之间边的特征;GNN 的学习目标是获得每个结点的图感知的隐藏状态 h v h_v hv?(state embedding),这就意味着:对于每个节点,它的隐藏状态包含了来自邻居节点的信息。那么,如何让每个结点都感知到图上其他的结点呢?GNN 通过迭代式更新所有结点的隐藏状态来实现,在 t + 1 t+1 t+1时刻,结点 v v v的隐藏状态按照如下方式更新:
𝐡 𝑣 t + 1 = 𝑓 ( 𝐱 𝑣 , 𝐱 𝑐 𝑜 [ 𝑣 ] , 𝐡 𝑛 𝑒 [ 𝑣 ] t , 𝐱 𝑛 𝑒 [ 𝑣 ] ) , 𝐡_𝑣^{t+1}=𝑓(𝐱_𝑣,𝐱_{𝑐𝑜[𝑣]},𝐡^t_{𝑛𝑒[𝑣]},𝐱_{𝑛𝑒[𝑣]}), hvt+1?=f(xv?,xco[v]?,hne[v]t?,xne[v]?),
上面这个公式中的 f f f 就是隐藏状态的状态更新函数,在论文中也被称为局部转移函数 (local transaction function)。公式中的 𝐱 𝑐 𝑜 [ 𝑣 ] 𝐱_{𝑐𝑜[𝑣]} xco[v]?指的是与结点 v v v相邻的边的特征, 𝐱 𝑛 𝑒 [ 𝑣 ] 𝐱_{𝑛𝑒[𝑣]} xne[v]?指的是结点 v v v的邻居结点的特征, 𝐡 𝑛 𝑒 [ 𝑣 ] t 𝐡^t_{𝑛𝑒[𝑣]} hne[v]t?则指邻居结点在 t t t时刻的隐藏状态。注意 f f f 是对所有结点都成立的,是一个全局共享的函数。那么怎么把它跟深度学习结合在一起呢?聪明的读者应该想到了,那就是利用神经网络 (Neural Network) 来拟合这个复杂函数 f f f。值得一提的是,虽然看起来 f f f 的输入是不定长参数,但在 f f f 内部我们可以先将不定长的参数通过一定操作变成一个固定的参数,比如说用所有隐藏状态的加和来代表所有隐藏状态。我们举个例子来说明一下:
假设结点 5 5 5为中心结点,其隐藏状态的更新函数如图所示。这个更新公式表达的思想自然又贴切:不断地利用当前时刻邻居结点的隐藏状态作为部分输入来生成下一时刻中心结点的隐藏状态,直到每个结点的隐藏状态变化幅度很小,整个图的信息流动趋于平稳。至此,每个结点都 “知晓” 了其邻居的信息。状态更新公式仅描述了如何获取每个结点的隐藏状态,除它以外,我们还需要另外一个函数 g g g 来描述如何适应下游任务。举个例子,给定一个社交网络,一个可能的下游任务是判断各个结点是否为水军账号。
𝐨 𝑣 = 𝑔 ( 𝐡 𝑣 , 𝐱 𝑣 ) 𝐨_𝑣=𝑔(𝐡_𝑣,𝐱_𝑣) ov?=g(hv?,xv?)
在原论文中, g g g 又被称为局部输出函数 (local output function),与 f f f 类似, g g g 也可以由一个神经网络来表达,它也是一个全局共享的函数。那么,整个流程可以用下面这张图表达:
仔细观察两个时刻之间的连线,它与图的连线密切相关。比如说在 T 1 T_1 T1?