图系列|从图(Graph)到图卷积(Graph Convolution): 漫谈图神经网络模型
笔者最近看了一些图与图卷积神经网络的论文，深感其强大，但一些Survey或教程默认了读者对图神经网络背景知识的了解，对未学过信号处理的读者不太友好。同时，很多教程只讲是什么，不讲为什么，也没有梳理清楚不同网络结构的区别与设计初衷(Motivation)。
因此，本文试图沿着图神经网络的历史脉络，从最早基于不动点理论的图神经网络(Graph Neural Network， GNN)一步步讲到当前用得最火的图卷积神经网络(Graph Convolutional Neural Network， GCN)， 期望通过本文带给读者一些灵感与启示。
- 本文的提纲与叙述要点主要参考了2篇图神经网络的Survey，分别是来自IEEE Fellow的A Comprehensive Survey on Graph Neural Networks[1] 以及来自清华大学朱文武老师组的Deep Learning on Graphs: A Survey[7]， 在这里向两篇Survey的作者表示敬意。
- 同时，本文关于部分图卷积神经网络的理解很多都是受到知乎问题[8]高赞答案的启发，非常感谢他们的无私分享！
- 最后，本文还引用了一些来自互联网的生动形象的图片，在这里也向这些图片的作者表示感谢。本文中未注明出处的图片均为笔者制作，如需转载或引用请联系本人。
历史脉络
在开始正文之前，笔者先带大家回顾一下图神经网络的发展历史。不过，因为图神经网络的发展分支非常之多，笔者某些叙述可能并不全面，一家之言仅供各位读者参考：
- 图神经网络的概念最早在2005年提出。2009年Franco博士在其论文 [2]中定义了图神经网络的理论基础，笔者呆会要讲的第一种图神经网络也是基于这篇论文。
- 最早的GNN主要解决的还是如分子结构分类等严格意义上的图论问题。但实际上欧式空间(比如像图像 Image)或者是序列(比如像文本 Text)，许多常见场景也都可以转换成图(Graph)，然后就能使用图神经网络技术来建模。
- 2009年后图神经网络也陆续有一些相关研究，但没有太大波澜。直到2013年，在图信号处理(Graph Signal Processing)的基础上，Bruna(这位是LeCun的学生)在文献 [3]中首次提出图上的基于频域(Spectral-domain)和基于空域(Spatial-domain)的卷积神经网络。
- 其后至今，学界提出了很多基于空域的图卷积方式，也有不少学者试图通过统一的框架将前人的工作统一起来。而基于频域的工作相对较少，只受到部分学者的青睐。
- 值得一提的是，图神经网络与图表示学习(Represent Learning for Graph)的发展历程也惊人地相似。2014年，在word2vec [4]的启发下，Perozzi等人提出了DeepWalk [5]，开启了深度学习时代图表示学习的大门。更有趣的是，就在几乎一样的时间，Bordes等人提出了大名鼎鼎的TransE [6]，为知识图谱的分布式表示(Represent Learning for Knowledge Graph)奠定了基础。
图神经网络(Graph Neural Network)
首先要澄清一点，除非特别指明，本文中所提到的图均指图论中的图(Graph)。它是一种由若干个结点(Node)及连接两个结点的边(Edge)所构成的图形，用于刻画不同结点之间的关系。下面是一个生动的例子，图片来自论文[7]:
状态更新与输出
最早的图神经网络起源于Franco博士的论文[2], 它的理论基础是不动点理论。给定一张图 G，每个结点都有其自己的特征(feature), 本文中用xv表示结点v的特征；连接两个结点的边也有自己的特征，本文中用x(v,u)表示结点v与结点u之间边的特征；GNN的学习目标是获得每个结点的图感知的隐藏状态 hv(state embedding)，这就意味着：对于每个节点，它的隐藏状态包含了来自邻居节点的信息。那么，如何让每个结点都感知到图上其他的结点呢？GNN通过迭代式更新所有结点的隐藏状态来实现，在t+1时刻，结点v的隐藏状态按照如下方式更新：
1 | 𝐡^{t+1}_𝑣=𝑓(𝐱_𝑣,𝐱_𝑐𝑜[𝑣],𝐡^{t}_𝑛𝑒[𝑣] ,𝐱_𝑛𝑒[𝑣]), |
上面这个公式中的 f 就是隐藏状态的状态更新函数，在论文中也被称为局部转移函数(local transaction function)。公式中的xco[v]指的是与结点v相邻的边的特征，xne[v]指的是结点v的邻居结点的特征，htne[v]则指邻居结点在t时刻的隐藏状态。注意 f 是对所有结点都成立的，是一个全局共享的函数。那么怎么把它跟深度学习结合在一起呢？聪明的读者应该想到了，那就是利用神经网络(Neural Network)来拟合这个复杂函数 f。值得一提的是，虽然看起来 f 的输入是不定长参数，但在 f 内部我们可以先将不定长的参数通过一定操作变成一个固定的参数，比如说用所有隐藏状态的加和来代表所有隐藏状态。我们举个例子来说明一下：
假设结点5为中心结点，其隐藏状态的更新函数如图所示。这个更新公式表达的思想自然又贴切：不断地利用当前时刻邻居结点的隐藏状态作为部分输入来生成下一时刻中心结点的隐藏状态，直到每个结点的隐藏状态变化幅度很小，整个图的信息流动趋于平稳。至此，每个结点都“知晓”了其邻居的信息。状态更新公式仅描述了如何获取每个结点的隐藏状态，除它以外，我们还需要另外一个函数 g 来描述如何适应下游任务。举个例子，给定一个社交网络，一个可能的下游任务是判断各个结点是否为水军账号。
1 | 𝐨_𝑣=𝑔(𝐡_𝑣,𝐱_𝑣) |
在原论文中，g 又被称为局部输出函数(local output function)，与 f 类似，g 也可以由一个神经网络来表达，它也是一个全局共享的函数。那么，整个流程可以用下面这张图表达：
仔细观察两个时刻之间的连线，它与图的连线密切相关。比如说在 T1 时刻，结点 1 的状态接受来自结点 3 的上一时刻的隐藏状态，因为结点 1 与结点 3相邻。直到 Tn 时刻，各个结点隐藏状态收敛，每个结点后面接一个 g 即可得到该结点的输出 o。
对于不同的图来说，收敛的时刻可能不同，因为收敛是通过两个时刻p-范数的差值是否小于某个阈值 ϵ来判定的，比如：
…
参考文献
[1]. A Comprehensive Survey on Graph Neural Networks, https://arxiv.org/abs/1901.00596
[2]. The graph neural network model, https://persagen.com/files/misc/scarselli2009graph.pdf
[3]. Spectral networks and locally connected networks on graphs, https://arxiv.org/abs/1312.6203
[4]. Distributed Representations of Words and Phrases and their Compositionality, http://papers.nips.cc/paper/5021-distributed-representations-of-words-andphrases
[5]. DeepWalk: Online Learning of Social Representations, https://arxiv.org/abs/1403.6652
[6]. Translating Embeddings for Modeling Multi-relational Data, https://papers.nips.cc/paper/5071-translating-embeddings-for-modeling-multi-relational-data
[7]. Deep Learning on Graphs: A Survey, https://arxiv.org/abs/1812.04202
[8]. 如何理解Graph Convolutional Network（GCN）? https://www.zhihu.com/question/54504471
[9]. Almeida–Pineda recurrent backpropagation, https://www.wikiwand.com/en/Almeida%E2%80%93Pineda_recurrent_backpropagation
[10]. Gated graph sequence neural networks, https://arxiv.org/abs/1511.05493
[11]. Representing Schema Structure with Graph Neural Networks for Text-to-SQL Parsing, https://arxiv.org/abs/1905.06241
[12]. Spider1.0 Yale Semantic Parsing and Text-to-SQL Challenge, https://yale-lily.github.io/spider
[13]. https://www.wikiwand.com/en/Laplacian_matrix
作者： SivilTaram
出处：https://www.cnblogs.com/SivilTaram/p/graph_neural_network_1.html
本站使用「CC BY 4.0」创作共享协议，转载请在文章明显位置注明作者及出处。
