原题：An Introduction to Graph Neural Network(GNN) For Analysing Structured Data——Understand What GNN Is and What GNN Can Do
原文：HTML
作者：Shanon Hong

---

图形神经网络（Graph Neural Network，GNN）由于其分析图形结构数据的能力，最近受到了很多关注。本文对图形神经网络做了一个简单的介绍。它涵盖了一些图形理论，以便于理解图形和分析图形的问题。然后介绍了不同形式的图形神经网络及其原理。此外，还包括GNN的一些应用。

Graph Theory

首先，我们需要知道什么是图（Graph）。

图是由两个部分组成的数据结构：顶点（vertices）和边（edges）。它被用作一种数学结构来分析对象和实体之间的成对关系。通常，一个图被定义为 G = ( V , E ) G=(V, E) G=(V,E)，其中， V V V 是节点集合， E E E 是它们之间的边。

A simple graph. Figure by author

一个图通常用邻接矩阵 A A A（Adjacency matrix）来表示，如果一个图有 N N N 个节点，那么 A A A 的维数为 ( N × N ) (N \times N) (N×N)。人们有时会提供另一个特征矩阵来描述图中的节点。如果每个节点有 F F F 个特征，那么特征矩阵 X X X 的维数为 ( N × F ) (N \times F) (N×F)。

---

Why Is a Graph Difficult To Analyze?

首先，欧氏空间中不存在图，这意味着它不能用我们熟悉的任何坐标系来表示。与波（waves）、图像（images）或时间序列信号（time-series signals）等其他类型的数据相比（“文本”也可以被视为时间序列），这使得图形数据的解释更加困难，这些数据可以很容易地映射到二维或三维欧氏空间。

其次，图没有固定的形式。为什么？请看下面的例子。图(A)和图(B)结构完全不同，视觉上也不同。但当我们将其转化为邻接矩阵表示时，两个图的邻接矩阵是相同的(如果不考虑边的权重)。那么我们应该考虑这两张图是相同还是不同呢？

Graph (A). Figure by author

Graph (B). Figure by author

最后，对于人类的解释来说，图通常是难以想象的。例如具有成百上千个节点的图，维度非常高，节点非常密集，使得人类更难理解图。因此，为这项任务训练机器学习模型是具有挑战性的。下面是模拟集成电路中逻辑门的图。

Example of a giant graph: circuit netlist. Figure from J. Baehr et. al. “Machine Learning and Structural Characteristics of Reverse Engineering”

---

Why Use Graphs?

人们选择图来解决问题的原因可以归纳为以下几点：

• 图提供了处理抽象概念(如关系和交互)的更好方法。它们还提供了一种直观的视觉方式来思考这些概念。图也是分析社会关系的自然基础。
• 图可以通过将问题简化为更简单的表示或将问题转换为不同角度的表示来解决更复杂的问题。
• 图论用于研究和建模社交网络、欺诈模式、功耗模式、社交媒体中的病毒和影响。社会网络分析(SNA)可能是图论在数据科学中最著名的应用。

---

Traditional Graph Analysis Methods

传统方法主要基于算法，​​例如：

• searching algorithms, e.g. BFS, DFS
• shortest path algorithms, e.g. Dijkstra’s algorithm, Nearest Neighbour
• spanning-tree algorithms, e.g. Prim’s algorithm
• clustering methods, e.g. Highly Connected Components, k-mean

这种算法的局限性在于，我们需要在应用该算法之前以一定的置信度获得图的先验知识。换句话说，它没有为我们提供研究图本身的手段。最重要的是，没有办法进行图级分类。

---

Graph Neural Network

图形神经网络（Graph Neural Network），顾名思义，是一种可以直接应用于图的神经网络。它为节点级、边级和图级预测任务提供了一种方便的方法。

文献中主要有三种类型的图神经网络：

• Recurrent Graph Neural Network
• Spatial Convolutional Network
• Spectral Convolutional Network

GNN的直觉是，节点是由它们的邻居和连接自然定义的。为了理解这一点，我们可以简单地想象，如果我们移除一个节点周围的邻居和连接，那么该节点将丢失所有信息。因此，节点的邻居和到邻居的连接定义了节点的概念。

考虑到这一点，我们给每个节点一个状态( x x x)来表示它的概念。我们可以使用节点状态( x x x)来产生输出( o o o)，即关于概念的决策。节点的最终状态( x n x_n xn​)通常称为 节点嵌入(node embedding)。所有GNN的任务是通过查看相邻节点的信息来确定每个节点的节点嵌入。

我们将从最早的图形神经网络开始，递归图形神经网络（Recurrent Graph Neural Network，RecGNN）。

---

Recurrent Graph Neural Network

正如在最初的GNN论文中所介绍的，递归神经网络是建立在Banach不动点定理（Banach Fixed-Point Theorem）的假设之上的。Banach不动点定理指出：设 ( X , d ) (X,d) (X,d) 是完全度量空间（complete metric space），设 ( T : X → X ) (T:X→X) (T:X→X) 是压缩映射（contraction mapping）。那么 T T T 有一个唯一的不动点 X ∗ X* X∗，对于任意 x ∈ X x∈X x∈X， n → ∞ n→∞ n→∞ 的序列 T n ( x ) T_n(x) Tn​(x) 收敛到 X ∗ X* X∗。这意味着如果我将映射 T T T 应用到 x x x 上 k k k 次， x k x^k xk 应该几乎等于 x k − 1 x^{k-1} xk−1，即：

RecGNN定义了一个参数化函数 f w f_w fw​：

其中 l n ， l c o ， x n e ， l n e l_n，l_{co}，x_{ne}，l_{ne} ln​，lco​，xne​，lne​ 分别表示当前节点 [ n ] [n] [n] 的特征，节点 [ n ] [n] [n] 的边，相邻节点的状态以及相邻节点的特征。在原始论文中，作者将节点特征（node features）称为节点标签（node labels）。这可能会让人困惑。

An illustration of node state update based on the information in its neighbors. Figure from “The Graph Neural Network Model”

最终，在经过 k k k 次迭代之后，最终的节点状态将用于产生输出，以决定每个节点。输出函数定义为：

---

Spatial Convolutional Network

空间卷积网络（Spatial Convolution Network）的直观性类似于著名的CNN，后者主导着图像分类和分割任务的文献。要了解图像上的CNN，您可以查看这篇文章，其中详细说明了CNN。

简而言之，对图像进行卷积的想法是对中心像素周围的相邻像素求和，该像素由参数化大小和可学习权重的滤波器指定。空间卷积网络采用了相同的思想，其通过将相邻节点的特征聚合到中心节点中。

Left: Convolution on a regular graph such as an image. Right: Convolution on the arbitrary graph structure. Figure from “A Comprehensive Survey on Graph Neural Networks”

---

Spectral Convolutional Network

与其他类型的GNN相比，这种类型的图卷积网络具有非常强大的数学基础。谱卷积网络建立在图信号处理理论的基础上。并通过简化和逼近图卷积。

通过Chebyshev多项式逼近（Hammond et al，2011），图卷积可以简化为以下形式：

经过进一步简化后，GCN论文提出了一种2层神经网络结构，可以用以下等式描述：

其中 A ^ \hat{A} A^ 是原始图邻接矩阵 A A A 的经过预处理的拉普拉斯算子（Laplacian）。（有关数学的详细信息，请参见GCN论文。将需要大量的精力来进行充分说明。）

如果你有一些机器学习的经验，这个公式看起来很熟悉。这不过是两个常用的全连接层结构。但在这种情况下，它确实起到了图形卷积的作用。我将在下面展示它为什么可以执行图形卷积。

Example of a graph with a feature assigned to each node. Figured by author

让我们考虑一下，我们有一个包含4个节点的简单图形。如上图所示，为这些节点中的每个节点分配了一个特征矩阵。图形邻接矩阵（adjacency matrix）和特征矩阵（feature matrix）很容易得出，如下所示：

Example of the adjacency matrix and feature matrix. Figure by author

请注意，邻接矩阵的对角线特意更改为“1”，以便为每个节点添加一个自循环（self-loop）。这是为了在我们执行特征聚合（ feature aggregation）时包含每个节点本身的特征。

然后，执行 A × X A \times X A×X（为简单起见，先忽略A的拉普拉斯算子和权重矩阵W）

Example of graph convolution by matrix multiplication. Figure by author

矩阵相乘的结果显示在最右边的矩阵中。让我们以第一个节点的结果特性为例。不难注意到，结果是[node 1]的所有特征的总和，包括[node 1]本身的特征，而[node 4]中的特征不包括在内，因为它不是[node 1]的邻居。从数学上讲，图的邻接矩阵只有在有边时才有值“1”，否则为“0”。这使得矩阵乘法成为连接到参考节点的节点的特征的总和。

因此，谱卷积网络和空间卷积网络虽然起点不同，但传播规则相同。

目前可用的所有卷积图神经网络共享相同的格式。他们都试图通过这个消息传递过程学习一个传递节点信息和更新节点状态的函数。

任何图形神经网络都可以表示为具有消息传递函数（message-passing function）、节点更新函数（node update function）和读出函数（readout function）的消息传递神经网络（J. Gilmer等人，2017）。

What Can GNN do?

GNN解决的问题可大致分为三类：

• Node Classification
• Link Prediction
• Graph Classification

在节点分类（Node Classification）中，任务是预测图中每个节点的节点嵌入（node embedding）。这种类型的问题通常以半监督（semi-supervised）的方式训练，其中只有部分图被标记。节点分类的典型应用包括引用网络（citation networks）、Reddit贴文、Youtube视频和Facebook好友关系。

在链接预测（Link Prediction）中，任务是理解图中实体之间的关系，并预测两个实体之间是否有联系。例如，一个推荐系统可以被视为链接预测问题，在该模型中，给定一组用户对不同产品的评论，任务是预测用户的偏好，并根据用户的兴趣调整推荐系统以推送更多相关的产品。

在图分类（Graph Classification）中，任务是将整个图分成不同的类别。它类似于图像分类，但目标变为图形域。有许多工业问题可以应用图形分类，例如，在化学、生物医学、物理中，模型被赋予分子结构，并被要求将目标分类为有意义的类别。它加速了原子、分子或任何其他结构化数据类型的分析。

---

Some Real Applications

这一部分将更深入地了解GNN在现实世界中的应用。

GNN in Natural Language Processing

GNN被广泛应用于自然语言处理。实际上，这也是GNN最初开始的地方。如果有自然语言处理的经验，你一定认为文本应该是一种顺序或时间数据，最好用RNN或LTSM来描述。GNN从一个完全不同的角度来看待这个问题。GNN利用词或文献的内在联系来预测范畴。比如引用网络（citation network）就是试图通过论文引用关系和其他论文引用的词来预测网络中每篇论文的标签。它也可以通过观察一个句子的不同部分来建立一个句法模型，而不是像RNN或LTSM那样纯粹的顺序。

GNN in Computer Vision

许多基于CNN的方法在图像中的目标检测方面取得了最先进的性能，但是我们不知道目标之间的关系。GNN在CV中的一个成功应用是使用图形来模拟由基于CNN的检测器检测到的对象之间的关系。在从图像中检测到对象之后，它们然后被馈送到用于关系预测的GNN推断中。GNN推论的结果是一个生成的图形，它模拟了不同对象之间的关系。

Scene Graph Generation. Figure from D. Xu, Y. Zhu, C. B. Choy, and L. Fei-Fei, “Scene graph generation by iterative message passing,” in Proc. of CVPR, 2017

CV中另一个有趣的应用是从图描述（graph descriptions）生成图像（image generation）。这可以解释为几乎与上述应用相反。传统的图像生成方法是使用GAN或自动编码器的文本到图像生成。图（graph）到图像（image）的生成提供了更多关于图像语义结构的信息，而不是使用文本来描述图像。

Image generated from scene graphs. Figure from J. Johnson, A. Gupta, and L. Fei-Fei, “Image generation from scene graphs,” in Proc. of CVPR, 2018

我想分享的最有趣的应用是零射学习（zero-shot learning，ZSL）。简而言之，ZSL正在尝试学习对一个没有训练样本的类（目标类）进行分类。这很有挑战性，因为如果没有训练样本，我们需要让模型逻辑地“think”以识别目标。举个例子，如果给我们三张图片(如下图所示)，让我们在其中找到“okapi”。我们以前可能没见过“okapi”。但如果我们也被告知“okapi”是一种长着四条腿、长着斑马条纹皮肤的鹿脸动物，那么我们就不难分辨出哪一种是“okapi”。典型的方法是通过将检测到的特征转换成文本来模拟这种“thinking process”。然而，文本编码（text encodings）是相互独立的。很难对文本描述之间的关系进行建模。换句话说，图形表示（graph representations）很好地模拟了这些关系，使机器以更“human-like”的方式思考。

Figure from X. Wang, Y. Ye, and A. Gupta, “Zero-shot recognition via semantic embeddings and knowledge graphs,” in CVPR 2018

---

GNN in Other Domains

GNN的更多实际应用包括人类行为检测、交通控制、分子结构研究、推荐系统、程序验证、逻辑推理、社会影响预测和对抗攻击预防。下图显示了一个社交网络中的人际关系模型。GNN可以用来把人们聚集成不同的社区团体。

Graph of Social Network. Image from GDJ, via Pixabay

---

Conclusion

在这篇文章中，我们回顾了一些图论知识，并强调了分析图的重要性。人们总是把机器学习算法看成一个“黑箱”。大多数机器学习算法只从训练数据的特征中学习，但没有实际的逻辑来执行。有了图，我们也许可以把一些“逻辑”传递给机器，让它更自然地“思考”。

GNN仍然是一个相对较新的地区，值得更多的研究关注。它是分析图数据的强大工具。然而，它不仅限于图中的问题。它可以很容易地推广到任何可以用图建模的研究。图建模是分析问题的自然方式。

---

References:

• F.Scarselli, M.Gori, “The graph neural network model,” IEEE Transactions on Neural Networks, 2009.
• T. N. Kipf and M. Welling, “Semi-supervised classification with graph convolutional networks,” in Proc. of ICLR, 2017.
• Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, Philip S. Yu, “A Comprehensive Survey on Graph Neural Networks”, arXiv:1901.00596.
• D. Xu, Y. Zhu, C. B. Choy, and L. Fei-Fei, “Scene graph generation by iterative message passing,” in Proc. of CVPR, vol. 2, 2017.
• J. Johnson, A. Gupta, and L. Fei-Fei, “Image generation from scene graphs,” in Proc. of CVPR, 2018.
• X. Wang, Y. Ye, and A. Gupta, “Zero-shot recognition via semantic embeddings and knowledge graphs,” in CVPR 2018.