图是一种数据结构，它对一组对象（节点）及其关系（边）进行建模。近年来，由于图结构的强大表现力，用机器学习方法分析图的研究越来越受到重视。图神经网络（GNN）是一类基于深度学习的处理图域信息的方法。由于其较好的性能和可解释性，GNN 最近已成为一种广泛应用的图分析方法。
GNN 的第一个动机源于卷积神经网络（CNN）。CNN 的广泛应用带来了机器学习领域的突破并开启了深度学习的新时代。然而 CNN 只能在规则的 Euclidean 数据上运行，如图像（2 维网格）和文本（1 维序列）。如何将 CNN 应用于图结构这一非欧几里德空间，成为 GNN 模型重点解决的问题。
GNN 的另一个动机来自图嵌入（Graph Embedding），它学习图中节点、边或子图的低维向量空间表示。DeepWalk、LINE、SDNE 等方法在网络表示学习领域取得了很大的成功。然而，这些方法在计算上较为复杂并且在大规模上的图上并不是最优的，GNN 旨在解决这些问题。
描述来源：机器之心 https://www.jiqizhixin.com/articles/2018-12-28-21
发展历史
描述
图神经网络的概念首先由 Gori 等人于2005年提出，并由 Scarselli 等人进一步阐明。这些早期的研究以迭代的方式通过循环神经架构传播邻近信息来学习目标节点的表示，直到达到稳定的固定点。该过程所需计算量庞大，而近来也有许多研究致力于解决这个难题。一般情况下，图神经网络代表的是所有用于图数据的深度学习方法。
受到卷积网络在计算机视觉领域所获巨大成功的激励，近来出现了很多为图数据重新定义卷积概念的方法。这些方法属于图卷积网络（GCN）的范畴。Bruna 等人于2013年提出了关于图卷积网络的第一项重要研究，他们基于谱图论（spectral graph theory）开发了一种图卷积的变体。自此，基于谱的图卷积网络不断改进、拓展、进阶。由于谱方法通常同时处理整个图，并且难以并行或扩展到大图上，基于空间的图卷积网络开始快速发展。这些方法通过聚集近邻节点的信息，直接在图结构上执行卷积。结合采样策略，计算可以在一个批量的节点而不是整个图中执行，这种做法有望提高效率。除了图卷积网络，近几年还开发出了很多替代的图神经网络。这些方法包括图注意力网络（GAT）、图自编码器、图生成网络以及图时空网络。
Battaglia 等人将图网络定位为从关系数据中学习的构建块，并在统一的框架下回顾了部分图神经网络。然而，他们整体的框架是高度抽象的，失去了每种方法在原论文中的见解。Lee 等人对图注意力模型（一种图神经网络）进行了部分调查。最近，Zhang 等人提出了一项关于图深度学习的最新调查，却忽略了对图生成网络和图时空网络的研究。总之，现有的研究没有一个对图神经网络进行全面的回顾，只覆盖了部分图卷积神经网络且检查的研究有限，因此遗漏了图神经网络替代方法的最新进展，如图生成网络和图时空网络。
主要事件
| 年份 | 事件 | 相关论文/Reference |
| 2005 | Gori 等人提出GNN | Scarselli, F., Gori, M., Tsoi, A. C., Hagenbuchner, M., & Monfardini, G. (2009). The graph neural network model. IEEE Transactions on Neural Networks, 20(1), 61-80. |
| 2013 | Bruna 等人提出了关于图卷积网络的第一项重要研究，他们基于谱图论（spectral graph theory）开发了一种图卷积的变体 | Bruna, J., Zaremba, W., Szlam, A., & LeCun, Y. (2013). Spectral networks and locally connected networks on graphs. arXiv preprint arXiv:1312.6203. |
| 2015 | Li, L. J. et al.提出了一种基于图像的社交网络 CelebrityNet，该网络基于名人照片中编码的隐性关系构建而成 | Li, L. J., Shamma, D. A., Kong, X., Jafarpour, S., Van Zwol, R., & Wang, X. (2015). CelebrityNet: A Social Network Constructed from Large-Scale Online Celebrity Images. ACM Transactions on Multimedia Computing, Communications, and Applications (TOMM), 12(1), 3. |
| 2016 | Eslami, S. A. et al.提出了一个用于结构化图像模型（可以对目标进行明确的推理）中的有效推理的框架。这种方法是通过使用一个循环神经网络来执行概率推理——该循环神经网络可以处理场景元素且一次处理一个。关键的是，该模型自身可以学习选择合适数量的推理步骤。相比于监督式的方法，该网络可以产出更精确的推理，而且它们的结构也可以使归纳得到进一步的提升 | Eslami, S. A., Heess, N., Weber, T., Tassa, Y., Szepesvari, D., & Hinton, G. E. (2016). Attend, infer, repeat: Fast scene understanding with generative models. In Advances in Neural Information Processing Systems (pp. 3225-3233). |
| 2018 | Veličković, P. et al.提出了基于近邻节点注意机制的网络架构 GAT，可用于处理复杂、不规则结构的计算图，并在三种困难的基准测试中得到了业内最佳水平 | Veličković, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., & Bengio, Y. (2017). Graph attention networks. arXiv preprint arXiv:1710.10903. |
| 2018 | Liao, R. et al.提出了一种图神经网络的新变体——图分割神经网络（Graph Partition Neural Network，GPNN），该网络适用于处理大型图 | Liao, R., Brockschmidt, M., Tarlow, D., Gaunt, A. L., Urtasun, R., & Zemel, R. (2018). Graph partition neural networks for semi-supervised classification. arXiv preprint arXiv:1803.06272. |
| 2018 | Chen, J. et al.提出基于控制变量的图卷积网络（GCN），有效减少感受野大小 | Chen, J., Zhu, J., & Song, L. (2017). Stochastic training of graph convolutional networks with variance reduction. arXiv preprint arXiv:1710.10568. |
| 2018 | Li, R. et al.提出自适应图卷积神经网络 AGCN，可接受任意图结构和规模的图作为输入 | Li, R., Wang, S., Zhu, F., & Huang, J. (2018, April). Adaptive graph convolutional neural networks. In Thirty-Second AAAI Conference on Artificial Intelligence. |
| 2018 | Zügner, D. et al.提出了针对图深度学习模型的对抗攻击方法，是首个在属性图上的对抗攻击研究；研究者还提出了一种利用增量计算的高效算法 Nettack | Zügner, D., Akbarnejad, A., & Günnemann, S. (2018, July). Adversarial attacks on neural networks for graph data. In Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining (pp. 2847-2856). ACM. |
| 2018 | Yan, S. et al.提出了一种时空图卷积网络，并利用它们进行人类行为识别 | Yan, S., Xiong, Y., & Lin, D. (2018, April). Spatial temporal graph convolutional networks for skeleton-based action recognition. In Thirty-Second AAAI Conference on Artificial Intelligence. |
发展分析
瓶颈
未来仍有一些开放性问题待解决，如：
- 浅层结构。经验上使用更多参数的神经网络能够得到更好的实验效果，然而堆叠多层的 GNN 却会产生 over-smoothing 的问题。具体来说，堆叠层数越多，节点考虑的邻居个数也会越多，导致最终所有节点的表示会趋向于一致。
- 动态图。目前大部分方法关注于在静态图上的处理，对于如何处理节点信息和边信息随着时间步动态变化的图仍是一个开放问题。
- 非结构化场景。虽然很多工作应用于非结构化的场景（比如文本），然而并没有通用的方法用于处理非结构化的数据。
- 扩展性。虽然已经有一些方法尝试解决这个问题，将图神经网络的方法应用于大规模数据上仍然是一个开放性问题。
未来发展方向
- 加深网络。深度学习的成功在于深度神经架构。例如在图像分类中，模型 ResNet 具有 152 层。但在图网络中，实证研究表明，随着网络层数增加，模型性能急剧下降。这是由于图卷积的影响，因为它本质上推动相邻节点的表示更加接近彼此，所以理论上，通过无限次卷积，所有节点的表示将收敛到一个点。这导致了一个问题：加深网络是否仍然是学习图结构数据的好策略？
- 感受野。节点的感受野是指一组节点，包括中心节点和其近邻节点。节点的近邻（节点）数量遵循幂律分布。有些节点可能只有一个近邻，而有些节点却有数千个近邻。尽管采用了采样策略，但如何选择节点的代表性感受野仍然有待探索。
- 可扩展性。大部分图神经网络并不能很好地扩展到大型图上。主要原因是当堆叠一个图卷积的多层时，节点的最终状态涉及其大量近邻节点的隐藏状态，导致反向传播变得非常复杂。虽然有些方法试图通过快速采样和子图训练来提升模型效率，但它们仍无法扩展到大型图的深度架构上。
- 动态性和异质性。大多数当前的图神经网络都处理静态同质图。一方面，假设图架构是固定的。另一方面，假设图的节点和边来自同一个来源。然而，这两个假设在很多情况下是不现实的。在社交网络中，一个新人可能会随时加入，而之前就存在的人也可能退出该社交网络。在推荐系统中，产品可能具有不同的类型，而其输出形式也可能不同，也许是文本，也许是图像。因此，应当开发新方法来处理动态和异质图结构。
Contributor: Xue Geng