chapter5_图神经网络.md

第 5 章 图神经网络

作者: 张伟 (Charmve)

日期: 2021/06/11

• 第 5 章 图神经网络
  • 5.1 历史脉络
  • 5.2 图神经网络(Graph Neural Network)
    • 5.2.1 状态更新与输出
    • 5.2.2 不动点理论
    • 5.2.3 具体实现
    • 5.2.4 模型学习
    • 5.2.5 GNN与RNN
    • 5.2.6 GNN的局限
  • 5.3 门控图神经网络(Gated Graph Neural Network)
    • 5.3.1 状态更新
    • 5.3.2 实例1:到达判断
    • 5.3.3 实例2:语义解析
    • 5.3.4 GNN与GGNN
  • 5.4 图卷积神经网络(GCNN)
    • 5.4.1 图卷积缘起
    • 5.4.2 图卷积框架(Framework)
    • 5.4.3 再谈卷积
    • 5.4.4 空域卷积(Spatial Convolution)
    • 5.4.5 消息传递网络(Message Passing Neural Network)
    • 5.4.6 图采样与聚合(Graph Sample and Aggregate)
    • 5.4.7 图结构序列化(PATCHY-SAN)
    • 5.4.8 频域卷积(Spectral Convolution)
  • 5.5 生成图表示
    • 5.5.1 图读出操作(ReadOut)
    • 5.5.2 基于统计的方法(Statistics Category)
    • 5.5.3 基于学习的方法(Learning Category)
    • 5.5.4 其他方法
  • 5.6 图神经网络在计算机视觉上的应用
    • 5.6.1 点云分割
    • 5.6.2 点云生成
    • 5.6.3 RGBD图像分割
    • 5.6.4 视觉问答VQA
    • 5.6.5 零次学习ZSL
  • 小结
  • 参考文献

5.1 历史脉络

在开始正文之前，笔者先带大家回顾一下图神经网络的发展历史。不过，因为图神经网络的发展分支非常之多，笔者某些叙述可能并不全面，一家之言仅供各位读者参考：

1. 图神经网络的概念最早在2005年提出。2009年Franco博士在其论文 [2]中定义了图神经网络的理论基础，笔者呆会要讲的第一种图神经网络也是基于这篇论文。
2. 最早的GNN主要解决的还是如分子结构分类等严格意义上的图论问题。但实际上欧式空间(比如像图像 Image)或者是序列(比如像文本 Text)，许多常见场景也都可以转换成图(Graph)，然后就能使用图神经网络技术来建模。
3. 2009年后图神经网络也陆续有一些相关研究，但没有太大波澜。直到2013年，在图信号处理(Graph Signal Processing)的基础上，Bruna(这位是LeCun的学生)在文献 [3]中首次提出图上的基于频域(Spectral-domain)和基于空域(Spatial-domain)的卷积神经网络。
4. 其后至今，学界提出了很多基于空域的图卷积方式，也有不少学者试图通过统一的框架将前人的工作统一起来。而基于频域的工作相对较少，只受到部分学者的青睐。
5. 值得一提的是，图神经网络与图表示学习(Represent Learning for Graph)的发展历程也惊人地相似。2014年，在word2vec [4]的启发下，Perozzi等人提出了DeepWalk [5]，开启了深度学习时代图表示学习的大门。更有趣的是，就在几乎一样的时间，Bordes等人提出了大名鼎鼎的TransE [6]，为知识图谱的分布式表示(Represent Learning for Knowledge Graph)奠定了基础。

5.2 图神经网络(Graph Neural Network)

首先要澄清一点，除非特别指明，本文中所提到的图均指图论中的图(Graph)。它是一种由若干个结点(Node)及连接两个结点的边(Edge)所构成的图形，用于刻画不同结点之间的关系。下面是一个生动的例子，图片来自论文[14]:

参考文献

[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–Pineda_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

[14]. Graph Neural Networks: A Review of Methods and Applications, https://arxiv.org/pdf/1812.08434