整理 | 耿玉霞，浙江大学直博生。研究方向：知识图谱，零样本学习，自然语言处理等。
来源 | 开放知识图谱（公众号id：OpenKG-CN）
责编 | Jane
近日，清华刘知远老师组在 arXiv 上发表了一篇关于图神经网络的综述，本次论文浅尝在分享这篇论文的基础上，对图神经网络的相关方法及应用作一次梳理。
一、前言
图神经网络(GraphNeural Networks, GNNs)，主要针对非欧几里得空间结构（图结构）的数据进行处理。具有以下特点：
-
忽略节点的输入顺序；
-
在计算过程中，节点的表示受其周围邻居节点的影响，而图本身连接不变；
-
图结构的表示，使得可以进行基于图的推理。
二、图神经网络模型
通常，
图神经网络由两个模块组成：传播模块(PropagationModule)和输出模块(Output Module)，
具体地：
（1）Propagation Module：图中节点之间传递信息并更新状态；
-
aggregator: 对于一个节点v, 通过聚合其周围节点的信息，学习其潜在表示h_v (state embedding)。
其中，x_v为节点v的features，x_co[v]为其周围边的features，h_ne[v]表示节点v周围邻居节点的state embedding，x_ne[v]表示周围节点的features。
-
updater: 更新节点的stateembedding。
（2）Output Module：基于节点和边的向量表示根据不同的任务定义目标函数
在监督学习场景中，对于一个特定的节点，其监督信号表示为：t_v，lossfunction定义为：
常见的图神经网络有：图卷积神经网络(GraphConvolutional Networks, GCNs)，门控图神经网络(Gated Graph Neural Networks,GGNNs)以及基于Attention机制的GraphAttention Networks(GAT)，下面详细介绍这三种网络：
1、图卷积神经网络（GCN）
（1）基于谱方法(Spectral Methods):
相关论文：<ICLR-17> Kipf T N, Welling M.Semi-supervised classification with graph convolutional networks.
通过计算图拉普拉斯算子(Graph Laplacian)的特征分解，在Fourier域定义卷积计算。对于输入信号x和卷积核?_?=????(?):
其中，表示图结构的Graph Laplacian矩阵可分解为：
上式的计算将卷积核近似为切比雪夫多项式，并进行化简：
最终得到GCN网络中的表示：
-
aggregator:
-
updater:
但是以上方法有几点不足，卷积核的学习依赖图拉普拉斯矩阵的特征分解，对于图结构有一定的要求，在固定结构上学习的模型，无法迁移到其他结构的模型上。
（2）基于非谱方法(Non-spectral Methods):
在图上直接定义卷积计算，将不同size的邻居节点考虑在内，同时保持像CNN一样的局部卷积不变性。
-
DCNNs：基于扩散卷积的思想的网络；
-
GraphSAGE：采样固定size的邻居节点，同时通过mean,LSTM, pooling等方式聚合周围节点的信息。
2、门控图神经网络（GGNN）
相关论文：<ICLR-16> Li Y, Tarlow D, Brockschmidt M,et al. Gated graph sequence neural networks.
-
提高图结构信息的long-term传播能力
-
将图中的edge信息考虑在内
将图矩阵作如下表示，不同类型的边采用不同类型的传播矩阵，同时，用 A^(out)和 A^(in) 分别表示节点的入度信息和出度信息。
计算图传播信息：
（1）Propagation module
-
initialization step
-
pass information：矩阵A中包含了当前节点与其他节点的交互信息
节点的state embedding h_{v^(t-1)}，与其他节点的交互信息a_{v^(t)}通过GRU单元进行融合：
-
update gate
-
reset gate
-
activate
（2）Output module
-
node-level
-
graph-level
其中，i,j表示两个全连接神经网络。
3、注意力图神经网络（GAT）
相关论文：<ICLR-18> Velickovic, Petar, et al. Graphattention networks.
-
为节点的不同的邻居节点指定不同权重
-
节点-邻居节点对的计算可并行化，相比于GCN等网络，速度较快
节点权重的计算：
节点信息的更新：
由“Attentionis all you need”一文中提出的 head attention，GAT 网络中也使用了 headattention：
三、图神经网络应用
1、Structural Scenarios
主要应用于其数据结构为图结构的场景
，如蛋白质分子结构图、KnowledgeGraph 等。以 KnowledgeGraph 中应用 GNN 为例：
相关论文：<IJCAI-17> Hamaguchi T, et al. Knowledgetransfer for out-of-knowledge-base entities: a graph neural network approach.
论文主要针对 KG 中的 out-of-knowledge-base(OOKB) 实体，进行知识库补全等任务。
a、OOKB实体定义：
在训练过程中未被训练到的实体，无法得到其 embedding 表示，从而无法预测其与知识库中其他实体之间的关系。如下图中在测试期间新出现的实体“Blade-Runner”，或者说新出现的三元组“(Blade-Runner,based-on, Do-Androids-Dream-of-Electric-Sheep?)”（图中红线所示部分）。
我们的任务则定义为：基于知识库中已存在的三元组（2）和当前新出现的三元组（1），预测当前新实体与知识库中其他实体之间的关系（即三元组3）。
同时，OOKB 实体即哪些与知识库中已存在的实体直接相连的实体，基于此，可以通过知识库中现有的实体表示得到 OOKB 实体表示。
b、这篇文章利用 GNN 中节点表示的方式，对 OOKB 实体进行表示：
其中，T_head 表示以 OOKB 实体为尾实体的三元组集合，T_tail 表示以 OOKB 实体为头实体的三元组集合，通过其周围邻居的头尾实体对当前实体进行表示。
T_head, T_tail 分别表示聚合三元组信息的函数，论文中为 batchnormalization function。
经 GNN 传播的节点状态表示为：
c、模型的输出模块利用 TransE 等经典模型，进行知识库补全任务。
2、Non-structural Scenarios
主要应用于其数据结构为非图结构的场景，如图片、文本等。在此类场景中，应用GNN通常有两种方式：
-
利用具有图结构信息的外部资源，如 KnowledgeGraph 等；
-
探索此类数据中隐含的图结构，如文本的句法数结构。
（1）图片相关任务：
-
Image Classification, i.e., zero-shot, few-shot
-
Visual Reasoning, i.e., VQA
-
Semantic Segmentation
其中，图片分类任务零样本学习和少样本学习的相关论文有：
-
Zero-shot recognition via semantic embeddings and knowledge graphs
-
Rethinking knowledge graph propagation for zero-shot learning
-
Multi-label zero-shot learning with structured knowledge graphs
-
The more you know: Using knowledge graphs forimage classification
-
Few-shot learning with graph neural networks
（2）NLP相关任务：
-
Text Classification
-
Sequence Labeling
-
Neural machine translation
-
Relation Extraction
-
Event Extraction
以机器翻译的一篇论文为例，通过将 sourcelanguage 的句法结构图输 GNN 进行 encode，继而附加 Attention layer 和 decoder 层，输出 target language 序列。
相关论文：<ACL-18> Beck D, Haffari G, Cohn T.Graph-to-sequence learning using gated graph neural networks.
这篇文章以“Graph tosequence”为要点，实验部分包括两个任务，其中一个是 AMR 图输出序列，另一个做 syntax-aware 的机器翻译任务。
其中，AMR Graph 为从句子的句法表示中抽象出来的语义表示语言，具体相似语义的句子有相同的 AMR Graph。如下图左所示。
模型在 Seq2seq 模型的基础上，以 AMR graph 为输入，通过 GGNN 网络进行 encode，经过 Attention 层和 RNNdecoder 输出序列。GGNN encoder 部分表示为：
其中，
表示当前节点与周围节点相连边的参数，l_e 表示不同边的类型。
但随着 Graph 中边类型的增多，很容易引起参数爆炸的问题，因此，本文提出了一种融合 Graph 中 edge 信息的方式，即将 edge 转化为附加的节点(no labelled edges)。具体地，通过将 Graph 转化为对应的二分图。上图中的句法结构图对应的二分图如下所示：
由此，graph 中的边的类型只有一种。
四、Open problems
图神经网络目前虽被广泛利用，但存在不少问题亟待解决：
（1）Shallowstructure：多层的图神经网络，可能会导致 over-smoothing的问题，如 GCN 等网络，一些论文中也尝试用 Skip connection 的方式加以解决；
（2）Dynamicgraphs：GNN 目前仅能处理一些静态图，对于实时增加/减少的节点和边则无法很好地处理；
（3）Non-structuralscenarios：在处理非图结构的数据时，希望利用其中内在的结构，而目前从 raw data 中生成 graph 的方法仍需改善；
（4）Scalability
五、总结
本文中总结了近年来常用的几种图神经网络模型，并就其应用场景进行了进一步的探讨。总的来说，图神经网络强大的计算能力，对图结构数据的友好处理，深受研究者们的喜爱，但其仍存在很多需要解决的问题，也是我们可以进一步研究的方向。
最后，送上这份值得大家收藏的论文地址
论文链接：
https://arxiv.org/pdf/1812.08434.pdf
GNN相关论文列表链接：
https://github.com/thunlp/GNNPapers
原文链接：
https://mp.weixin.qq.com/s/043sK8IDmdTYDpbCfPLIxw
（本文为AI科技大本营转载文章，转载请联系作者，禁止二次转载）
推荐荐阅读：
❤点击“阅读原文”，查看历史精彩文章。