图表征学习：迈向动态开放环境

图数据是对万物间联系的一般抽象，广泛存在于各行各业中。图表征学习为图数据的建模与分析提供了新范式，是近年来机器学习与数据挖掘领域的热门研究方向，并被有效地应用于推荐系统、交通预测等众多领域。本书将全面介绍图表征学习，特别是针对处于真实世界动态、开放环境之中图数据的图表征学习方法。本书分为3 篇：第1 篇介绍图嵌入和图神经网络等经典图表征学习方法；第2 篇围绕鲁棒性、动态性、可解释性、分布外泛化性等多个角度，系统地介绍针对动态开放环境中的图表征学习方法；第3 篇以四个不同领域为例，从推荐系统、交通预测、自然语言处理、组合优化等场景，介绍图表征学习的应用方法。除了对代表性方法进行详细介绍，本书还提供了丰富的参考文献，读者可以更深入地学习图表征学习的前沿内容。

本书适合具有一定机器学习基础的高年级本科生、研究生、教师和研究者，以及对图数据感兴趣的计算机工程师和从业人员阅读，也适合对人工智能、深度学习和图数据分析感兴趣的其他人士参考。

朱文武

清华大学计算机科学与技术系教授，清华大学人工智能研究院大数据智能中心主任，信息科学与技术国家研究中心副主任，国家973项目首席科学家。欧洲科学院院士、ACM Fellow、IEEE Fellow、AAAS Fellow、SPIE Fellow。曾任微软亚洲研究院主任研究员、英特尔中国研究院首席科学家与总监及美国贝尔实验室研究员等职。主要从事多媒体智能计算、大数据分析等研究工作。曾担任IEEE Transactions on Multimedia主编、指导委员会主席。10次获国际最佳论文奖。获2018年度国家自然科学二等奖（排名第1）和2012年度国家自然科学二等奖（排名第2）。

王鑫

清华大学计算机科学与技术系助理研究员，中国计算机学会多媒体专业技术委员会副秘书长，清华大学博士后校友会秘书处副秘书长。主要研究方向为多媒体智能、媒体大数据、机器学习等，在IEEE TPAMI、ICML、NeurIPS、ACM Multimedia等相关领域国际顶级期刊或会议上发表论文100余篇。承担国家优秀青年科学基金等项目，获2017年度中国博士后创新人才支持计划、2020年度ACM中国新星奖、2022年度IEEE TCMC新星奖、2022年度教育部自然科学一等奖。

张子威

清华大学计算机科学与技术系博士后，清华大学数理基科班学士、计算机系博士。主要研究方向为图机器学习，在国际顶级期刊和会议上发表论文30余篇，谷歌学术引用超过3000次。曾获清华大学优秀博士毕业生与优秀博士毕业论文、吴文俊人工智能优秀博士学位论文提名，入选百度AI华人新星百强榜单、AI 2000学者榜单、2022年博士后创新人才支持计划。

清华大学朱文武教授团队全新力作！

张钹、徐宗本、陈纯院士倾情作序推荐！

详解图表征学习的基础知识、前沿进展

系统论述图表征学习的动态性、可解释性、鲁棒性和泛化性等热点问题

全面剖析图表征学习在推荐系统、交通预测、自然语言处理、组合优化领域的应用方法

推荐序一

我们周围的世界小到原子、分子的结构，大到人类社会的交通、物流和社交网络，都蕴含着事物之间的相互关系。图数据（Graph Data）正是对这种关系的一种抽象。由此可见，图数据无处不在。为了让机器能够分析和有效地利用图数据，需要使用机器学习算法对图数据进行建模，这就是“图表征学习”（GraphRepresentation Learning）。

本书正是一本专门介绍这一重要内容的专著。本书共17 章，除了第1 章介绍图和神经网络的基础知识，以及第17 章展望图表征学习的未来发展，主体部分共15 章，分为3 篇。

第1 篇介绍经典图表征学习，包括图表征学习的两种基本算法及其理论分析。第1 个算法——图嵌入（第2 章），介绍结构保持的三种图嵌入方法，即基于随机游走、基于矩阵分解和基于深度自编码器的图嵌入。图嵌入将图中的元素向量化，即将节点、边、子图和整图等以向量的形式表征，然后对该表征进行机器学习。第2 个算法——图神经网络（第3 章），按照时间脉络从早期的发展直到2022 年的进展，分别介绍了谱域图神经网络、空域图神经网络和消息传递图神经网络的基础内容。为了将仅适用于图像或文本等规则结构数据的传统深度学习方法推广到一般图数据，需要在图数据上定义适合的神经网络架构——图神经网络，并进行端到端的学习。理论分析部分（第4 章）通过以下四方面，即图信号处理、图同构测试、图神经网络表达能力以及过平滑与深层图神经网络，对图表征学习进行理论分析，以加深读者对图表征学习内在机制的理解。

第2 篇是全书的重点，介绍动态开放环境中的图表征学习。本书将图数据中的结构、特征、性质和任务等在时间上发生变化的情况定义为动态环境；将在机器学习过程或应用场景中，数据分布、学习目标、特征或标签等因素发生变化的情况定义为开放环境。针对这种动态和开放环境对图表征学习提出的挑战，研究人员在经典图表征学习的基础上，进行了专门的设计与改进。第2 篇详细介绍了这方面的内容，具体包括：为降低噪声和对抗攻击的影响的鲁棒图表征学习（第5 章）；为有效捕捉图数据背后的复杂潜在因子的解耦图表征学习（第6 章）；为学习随时间动态变化的图数据表征的动态图表征学习（第7 章）；为减少对标签信息的依赖的无监督图神经网络与自监督图神经网络（第8 章）；增加对图神经网络决策过程的理解和信任程度的图神经网络的可解释性（第9 章）；增加图表征学习对不同环境的自适应能力的自动图表征学习（第10 章）；为有效地解决图样本量不足的问题的元学习与图表征学习（11 章）；针对开放环境中训练数据和测试数据非同分布的情况下的分布外泛化图表征学习（第12 章）。

第3 篇介绍图表征学习的应用，包括推荐系统（第13 章）、交通预测（第14章）、自然语言处理（第15 章）和组合优化（第16 章）。

从2013 年人们尝试将深度学习运用于图数据算起，尽管图表征学习的历史只有短短的10 年，但该领域的发展非常迅速。图表征学习的理论、方法和应用已经积累了丰富的材料和知识。为了让更多读者了解这一领域的进展，已经有相关的图书出版，如2020 年出版的麦吉尔大学（McGill Universit）的William L.Hamilton 撰写的《图表示学习》（Graph Representation Learning）。与已有的图书相比，本书的内容更加丰富、系统且具有前瞻性，特别注重介绍动态开放环境中的图表征学习。由于许多图数据都处于动态开放环境之中，如何处理这个问题对于图表征学习的长远发展有重要意义。本书正好提供了在这方面取得的主要成果。

本书适合具有一定机器学习基础的高年级本科生、研究生、教师和研究者，以及对图数据感兴趣的计算机工程师和从业人员阅读，也适合对人工智能、深度学习和图数据分析感兴趣的其他人士参考。

张钹

清华大学

推荐序二

古希腊哲学家德谟克利特曾主张“世界上一切事物都是相互联系的”，而图正是一种描述万物间联系的通用语言。例如，人和人的联系可以表示为社交图，分子中不同原子间的关联可以表示为分子图，工厂中互相关联的传感器也可以建模成一个图。可以说，图数据在我们的生活中无处不在。

由于图数据的广泛存在，图表征学习成了机器学习领域的一个热门研究方向，受到了研究者和从业者的广泛关注。概括地说，图表征学习旨在学习图的向量化表征并且建模图结构，从而实现图数据的分析。与其他机器学习模型相比，结构是图表征学习里面的一个核心的因素，也使得图表征学习在方法上与其他机器学习有很大的区别。例如，在图表征学习的一类早期方法——图嵌入中，如何在向量空间中保持图结构便是一个关键的难题；图表征学习的另一类代表性算法——图神经网络，是基于图结构定义了一种新的神经网络架构，并成了图领域的一种新范式。此外，图表征学习也在诸多场景中有着重要的应用，例如电商网站的推荐系统、金融平台的欺诈监测、交通网络的车流预测、分子图的性质分析，等等。

本书的主要特点在于深入浅出地介绍了图表征学习的理论、方法和应用，既适合初学者学习，也适合专业人士深入研究。首先，本书介绍了图表征学习的基本概念和方法，包括图嵌入、图神经网络等。然后，本书详细讲解了动态开放环境中的图表征学习，这是该领域的研究前沿。相比于静态封闭环境假设，动态开放环境对图表征学习方法的鲁棒性、泛化性、可解释性等均提出了严峻挑战，也激发了一系列新方法的设计。这些方法可以帮助我们更好地处理现实世界中的复杂图数据。最后，本书还介绍了图表征学习的应用，包括推荐系统、交通预测等。

总之，无论是高等院校相关专业的本科生或研究生，还是领域内的专家，抑或是仅对图表征学习感兴趣的读者，本书都是一本很好的入门书和参考书，非常值得推荐。

徐宗本

西安交通大学

推荐序三

21 世纪以来，以深度学习为代表的机器学习技术不断发展，并显著推动了人工智能的进步。最早期的深度学习更多关注网格状的数据，例如音频、图片或文本等。除这些数据外，图（graph）则是一种更加通用的数据类型，能够更广泛地描述事物之间的关联关系，例如社交网络、金融网络、交通网络和蛋白质网络等。因此，如何在图数据上进行机器学习，是一个非常重要且有意义的研究方向，也是近年来的研究热点。

“图表征学习”（Graph Representation Learning）正是在这种背景下提出和发展起来的。它主要通过学习图中元素的向量化表征，从而利用机器学习进行图数据的分析和建模。相比于针对图片或文本数据设计的机器学习方法，图表征学习需要处理复杂的图结构信息，因此涉及许多独特的研究问题，吸引了众多研究者的关注。

本书是关于图表征学习的介绍，共17 章，内容丰富。从广度上看，书中讨论了图表征学习的不同方面，从早期的图嵌入到近期的图神经网络模型，以及图表征学习的各类应用，均有涉及。从深度上看，书中重点介绍了在动态开放环境中的图表征学习，包括图的动态性、鲁棒性、可解释性和泛化性等方面的内容，均是机器学习和人工智能领域的关键问题和前沿方向。本书作者朱文武教授等均来自清华大学，他们长期从事图表征学习的研究，对这个方向有深刻的理解。

本书既适合计算机科学、机器学习、数据分析专业的学生，以及大数据和人工智能应用程序开发人员参考；也适合本科高年级学生或者研究生，以及大学的老师和研究机构的研究人员阅读。

陈纯

浙江大学

前言

图数据是对事物间联系的一般抽象，广泛存在于我们的日常生活中，例如社交网络、交通网络、推荐系统和互联网等。作为图数据分析与挖掘的一种新范式，图表征学习是近年来机器学习与数据挖掘领域的热门研究方向。例如，在工业界，国内外多家互联网巨头，包括亚马逊、谷歌、阿里、百度、腾讯等，均开发研制了图表征学习的相关系统；国家自然科学基金委员会也将图表征学习相关内容列入“下一代人工智能重大研究计划”。可以说，图表征学习无论在研究还是应用方面，都有着极大的潜在价值和光明的发展前景。

为什么写作本书

考虑到图表征学习的快速发展和广泛应用，本书希望尽量全面地介绍图表征学习。本书作者所在的研究团队——清华大学多媒体与网络实验室，从2014 年左右开始关注图表征学习，并见证了这个领域从新兴，甚至可以说一开始相对小众，发展到目前受到各行各业的广泛关注，并成为一个机器学习和深度学习重要分支的全过程。本书作者基于在该方向的研究积累，并查阅了大量相关资料，费时约两年，写成了这本书。

在撰写本书的两年中，一方面，我们注意到有一些同期出版的图表征学习著作，它们对许多经典的图表征学习方法进行了介绍；另一方面，我们同时注意到，近期图表征学习的一个重要发展趋势是更加关注真实世界中图数据所处的动态开放环境。动态开放环境给图表征学习带来了很大挑战，也是图表征学习在解决真实世界问题时不可避免会遇到的瓶颈。因此，图表征学习针对动态开放环境发展出了许多新兴的、前沿的方法。考虑到这些因素，我们调整了本书原定的结构，并将更多篇幅用于介绍针对动态开放环境所设计的图表征学习方法，希望吸引更多读者了解、关注并继续深入研究这个方向。

本书主要内容

本书共包括17 章，除概述（第1 章）和展望（第17 章）外，主体的15 章分为3 篇，内容如下：

第1 篇介绍经典图表征学习，包括图嵌入（第2 章）、图神经网络（第3 章）和图表征学习理论分析（第4 章）。该篇内容将为动态开放环境中的图表征学习和应用奠定基础。

第2 篇介绍针对动态开放环境的不同特点设计的图表征学习方法，包括鲁棒性（第5 章）、解耦表征（第6 章）、动态性（第7 章）、无监督学习（第8 章）、可解释性（第9 章）、自动机器学习（第10 章）、元学习（第11 章）和分布外泛化（第12 章），从不同方面全面地介绍动态开放环境中的图表征学习。

第3 篇以4 个代表性领域为例，介绍图表征学习的应用，包括推荐系统（第13 章）、交通预测（第14 章）、自然语言处理（第15 章）和组合优化（第16 章）。

致谢

感谢清华大学的张钹院士、西安交通大学的徐宗本院士、浙江大学的陈纯院士在百忙之中为本书作序。

感谢本书作者所在的清华大学多媒体与网络实验室研究生为本书写作提供的帮助（按姓名排序）：常恒、蔡婕、邓起谱、关超宇、李昊阳、李家栋、李霈雯、潘旺、秦一鉴、谢贝妮、张一彭、张泽阳。

感谢电子工业出版社博文视点及宋亚东编辑对本书出版所做的努力。

由于作者水平有限，书中不足之处在所难免，敬请专家和读者给予批评指正。

朱文武，王鑫，张子威

2023 年6 月

第1 章概述/1

1.1 引言/1

1.2 图基础知识/3

1.3 机器学习基础知识/7

第1 篇经典图表征学习

第2 章图嵌入/13

2.1 基于随机游走的图嵌入/13

2.2 基于矩阵分解的图嵌入/18

2.3 基于深度自编码器的图嵌入/21

2.4 本章小结/24

第3 章图神经网络/25

3.1 谱域图神经网络/26

3.2 空域图神经网络/34

3.3 消息传递图神经网络/41

3.4 图池化/47

3.5 本章小结/53

第4 章图表征学习理论分析/54

4.1 图信号处理/54

4.2 图同构测试/58

4.3 图神经网络表达能力/61

4.4 过平滑与深层图神经网络/64

4.5 本章小结/68

第2 篇动态开放环境图表征学习

第5 章鲁棒图表征学习/71

5.1 图数据上的对抗样本/71

5.2 图对抗攻击的分类/73

5.3 图神经网络模型上的攻击与防御方法/75

5.4 本章小结/78

第6 章解耦图表征学习· 79

6.1 基于变分自编码器的解耦图神经网络/79

6.2 基于邻域路由机制的解耦图神经网络/81

6.3 基于其他思想的解耦图神经网络/87

6.4 本章小结/90

第7 章动态图表征学习/91

7.1 动态图数据/91

7.2 离散时间动态图表征学习/92

7.3 连续时间动态图表征学习/94

7.4 本章小结/96

第8 章无监督图神经网络与自监督图神经网络/97

8.1 无监督学习的图神经网络/97

8.2 自监督学习的图神经网络/99

8.3 本章小结/106

第9 章图神经网络的可解释性/107

9.1 简介/107

9.2 可解释方法分类/109

9.3 实例级局部解释/110

9.4 模型级全局解释/114

9.5 对解释模型的评价/115

9.6 可解释性的交叉学科应用/117

9.7 本章小结/118

第10 章自动图表征学习/119

10.1 自动机器学习简介/119

10.2 图超参数优化/120

10.3 图神经网络架构搜索/122

10.4 本章小结/132

第11 章元学习与图表征学习/133

11.1 元学习简介/133

11.2 图上的元学习/136

11.3 本章小结/143

第12 章分布外泛化图表征学习/144

12.1 图分布外泛化问题和分类/145

12.2 数据层面方法/148

12.3 模型层面方法/151

12.4 学习策略/155

12.5 理论分析/162

12.6 本章小结/163

第3 篇图表征学习的应用

第13 章推荐系统/167

13.1 通用推荐/168

13.2 序列推荐/176

13.3 本章小结/179

第14 章交通预测/180

14.1 时空图/181

14.2 时空图神经网络模型/181

14.3 本章小结/188

第15 章自然语言处理/189

15.1 文本分类/189

15.2 关系抽取/192

15.3 文本生成/193

15.4 问答系统/196

15.5 其他任务/198

15.6 本章小结/198

第16 章组合优化/199

16.1 简介/199

16.2 预备知识/200

16.3 寻找可行解/201

16.4 本章小结/207

第17 章图表征学习展望/209

参考文献/211