2020必火的图神经网络（GNN）是什么？有什么用？

导读：近年来，作为一项新兴的图数据学习技术，图神经网络（GNN）受到了非常广泛的关注。2018年年末，发生了一件十分有趣的事情，该领域同时发表了三篇综述类型论文，这种“不约而同”体现了学术界对该项技术的认可。

事实上，在2019年的各大顶级学术会议上，与图神经网络有关的论文也占据了相当可观的份额。相信在未来几年，这种流行的趋势会只增不减。

本文就从“图”说起，带你了解图神经网络的概念及应用。

作者：刘忠雨、李彦霖、周洋

来源：大数据DT（ID：hzdashuju）

01 图的基本定义

图（Graph）是一个具有广泛含义的对象。在数学中，图是图论的主要研究对象；在计算机工程领域，图是一种常见的数据结构；在数据科学中，图被用来广泛描述各类关系型数据。许多图学习的理论都专注于图数据相关的任务上。

通常，图被用来表示物体与物体之间的关系。这在生活中有着非常多的现实系统与之对应，比如化学分子、通信网络、社交网络等。事实上，任何一个包含二元关系的系统都可以用图来描述。因此，研究并应用图相关的理论，具有重大的现实意义。

本文，我们主要对图相关的概念做一些基础介绍，包括图的基本定义、图在计算机中的存储表示方法与遍历方法、图数据及其常见的应用场景、图数据深度学习的浅述。

在数学中，图由顶点（Vertex）以及连接顶点的边（Edge）构成。顶点表示研究的对象，边表示两个对象之间特定的关系。

图可以表示为顶点和边的集合，记为G = (V, E)，其中V是顶点集合，E是边集合。同时，我们设图G的顶点数为N，边数为M（如无特殊说明，本文中的图均如此表示）。一条连接顶点vi, vj∈V的边记为（vi, vj）或者eij。如图1-1所示，V = {v1, v2, v3, v4, v5}，E = {(v1, v2), (v1, v3), (v2, v4), (v2, v3), (v3, v4), (v4, v5)}。

▲图1-1 图G的定义

02 图的基本类型

1. 有向图和无向图

如果图中的边存在方向性，则称这样的边为有向边eij = <vi, vj>，其中vi是这条有向边的起点，vj是这条有向边的终点，包含有向边的图称为有向图，如图1-2所示。与有向图相对应的是无向图，无向图中的边都是无向边，我们可以认为无向边是对称的，同时包含两个方向：eij = <vi, vj> = <vj, vi> = eji。

▲图1-2 有向图

2. 非加权图与加权图

如果图里的每条边都有一个实数与之对应，我们称这样的图为加权图，如图1-3所示，该实数称为对应边上的权重。在实际场景中，权重可以代表两地之间的路程或运输成本。一般情况下，我们习惯把权重抽象成两个顶点之间的连接强度。与之相反的是非加权图，我们可以认为非加权图各边上的权重是一样的。

▲图1-3 加权图

3. 连通图与非连通图

如果图中存在孤立的顶点，没有任何边与之相连，这样的图被称为非连通图，如图1-4所示。相反，不存在孤立顶点的图称为连通图。

<