腾讯AI Lab联合清华、港中文，万字解读图深度学习历史、最新进展与应用（1）

前言

人工智能领域近几年历经了突飞猛进的发展。图像、视频、游戏博弈、自然语言处理、金融等大数据分析领域都实现了跨越式的进步并催生了很多改变了我们日常生活的应用。近段时间，图神经网络成为了人工智能领域的一大研究热点，尤其是在社交网络、知识图谱、化学研究、文本分析、组合优化等领域，图神经网络在发掘数据中隐含关系方面的强大能力能帮助我们获得更好的数据表达，进而能让我们做出更好的决策。比如通过图神经网络梳理人类社会关系网络的演变，可有望帮助我们理解人类社会的底层运作模式，进而让我们离理想社会更近一步。

在今年的计算机协会国际数据挖掘与知识发现大会（ACM SIGKDD，简称 KDD）上，图神经网络备受研究关注的现状得到了充分体现：粗略统计，今年 KDD 接收的 216 篇论文（research track）中有近 40 篇与图神经网络相关。也因此，一场为期一天的图神经网络相关课程得到了参会人员的重点关注。该联合课程的主题为「图深度学习：基础、进展和应用（Deep Graph Learning: Foundations, Advances and Applications）」，由腾讯AI Lab、清华大学、香港中文大学等机构联合组织，从基础的图概念一直谈到了当今最前沿的图神经网络研究进展。

本次课程分为两个主题。本文将分图神经网络历史、图神经网络的最新研究进展和图神经网络的应用进展三大部分归纳总结该课程Theme II: Advances and Applications部分的核心内容，Theme I以及更多详细的内容可参看课程幻灯片及相关论文：https://ai.tencent.com/ailab/ml/KDD-Deep-Graph-Learning.html

为了解决图学习中的一系列具有挑战性的问题， 探索图学习应用的边界并在于助力公司各类与图数据相关的业务。腾讯AI Lab于2017年下半年开始布局图深度学习的研究，积极探索图深度学习的应用边界。并且在各大机器学习数据挖掘顶级会议上发表多篇文章，涉及大图计算，超深图神经网络，无监督图学习，图的对抗攻击，图的样本学习等。在未来我们将探索图深度学习在广泛场景的应用，如社交推荐，****物研发等。使其能够真正造福人类。

一、图与图神经网络

1.什么是图？

汉语中的「图」可以对应成英语中多个不同的词：image、picture、map 以及本文关注的 graph。图（graph）也可称为「关系图」或「图谱」，是一种可用于描述事物之间的关系的结构。图的基本构成元素为顶点和连接顶点的边。根据边是否存在方向的性质，还可分为有向图和无向图。一般而言，我们通常可将图表示成点和连接点的线的形式，这有助于我们更直观地理解，如下图所示：

但为便于计算机处理，我们也可用矩阵来表示图。比如如果定义当 v_i 与 v_j 相连时，A[i,j]=1，否则 A[i,j]=0，则可将以上矩阵表示为邻接矩阵 A：

图具有很强的表征能力。物理学系统建模、蛋白质预测、疾病分类以及许多文本和图像处理任务都可以表示成图结构的数据，比如图可用于表示文本中句子的依赖关系和图像中事物的相对位置，也可以用于分析社交网络中的信息传播和用户关系，还能通过分析分子之间的关联来发现新****。

2.图神经网络

近些年在大数据和硬件发展双重助力下迎来跨越式发展的深度神经网络技术让我们具备了分析和理解大规模图数据的能力。总体而言，图分析任务可分为节点分类、连接预测、聚类三类。

图神经网络（GNN）就是处理图数据的神经网络，其中有两种值得一提的运算操作：图过滤(Graph Filter, 分为基于空间的过滤和基于谱的过滤）和图池化。其中图过滤可细化节点特征，而图池化可以从节点表示生成图本身的表示。

一般来说，GNN 的框架在节点层面上由过滤层和激活构成，而对于图层面的任务，则由过滤层、激活和池化层组成不同的模块后再连接而成。

在 GNN 的实现方面，目前最常用的方法是消息传递框架（Message Passing Framework）。简单总结起来，该框架分为两个步骤。

第一步是消息生成步骤。首先，从近邻节点收集状态数据，然后使用对应函数生成当前节点的消息。在第二步中，我们更新目标节点的状态。

目前大多数空间式 GNN 都可以构建为某种消息传递过程，而且事实上目前大多数用于图的深度学习工具包大都采用了这一框架，比如 Deep Graph Library 和 PyTorch Geometric。

3.图神经网络的发展历史

图神经网络（GNN）并不是一个新事物，最早的GNN 的历史可以追溯到 1997 年，粗略总结起来，GNN 的发展过程大致可分为三个阶段。

在第一个阶段，GNN 所使用的主要方法是基于循环神经网络（RNN）的扩展。众所周知，RNN 擅长处理序列数据，而反过来，序列数据则可被视为一种特殊模式的图。因此，早期的一些工作（TNN97 / TNN08）将处理序列数据的 RNN 泛化用于树和有向无环图（DAG）等特殊的图结构。但那之后这一领域的发展几乎陷入了停滞状态。然而，在当前这轮深度学习热潮的带动下，对非结构化数据的建模和处理的研究开始广泛涌现，GNN 也迎来了自己的发展契机，顶级会议上的相关论文数量也迅猛增长。

在第二个阶段，卷积被引入到了 GNN 的工作流程中。当用矩阵进行表示时，图与卷积擅长处理的图像具有很多相似性，也因此开启了在 GNN 中使用卷积的时代。一系列的工作将在谱空间上的图卷积转换为了拓扑空间上的近似，并在此基础上于 2017 年诞生了图卷积网络（GCN），其首次使用了逐层卷积来扩展感受野，图神经网络也由此开始了实际应用。

我们现在正处于 GNN 发展的第三个阶段。图卷积已经出现了多种变体，注意力机制已被引入 GNN 中，此外还出现了图池化（Graph Pooling）技术和高阶 GNN。这一阶段出现的重要技术包括：

●  变体卷积：Lanczos 网络（使用 Lanczos 算法来获取图拉普拉斯的低秩近似）、图小波神经网络（使用小波变换替代傅里叶变换）、双曲 GCN（将 GCN 构建到双曲空间中）。

●  注意力机制：图注意力网络（使用可学习的自注意力替换固定的聚合权重）、门控注意力网络（加入了可学习的门来建模每个头的重要度）、谱式图注意力网络（将注意力应用于谱域中的高/低频组件）。

●  图池化：SAGE（自注意图嵌入，在池化时使用自注意力来建模节点重要度）、通过图剪切实现图池化（通过图剪切算法得到的预训练子图实现图池化）、可微分图池化（DIFFPOOL，通过学习聚类分配矩阵以分层方式来聚合节点表征）、特征池化（EigenPooling，通过整合节点特征和局部结构来获得更好的分配矩阵）。

●  高阶 GNN：高阶 GNN 是指通过扩展感受野来将高阶相近度（high-order proximities）编码到图中。高阶相近度描述的是距离更多样的节点之间的关系，而不仅是近邻节点之间的关系。这方面的研究工作包括 DCNN（通过把转移矩阵的幂级数堆叠起来而将邻接矩阵扩展为张量，然后相互独立地输出节点嵌入和图嵌入）、MixHop（使用了归一化的多阶邻接矩阵，然后汇集各阶的输出，从而同时得到高阶和低阶的相近度）、APPNP（使用了个性化 PageRank 来为目标节点构建更好的近邻关系）。

下图简单总结了各种 GNN 变体之间的关系：