图神经网络：基础、前沿与应用

本书致力于介绍图神经网络的基本概念和算法、研究前沿以及广泛和新兴的应用，涵盖图神经网络的广泛主题，从基础到前沿，从方法到应用，涉及从方法论到应用场景方方面面的内容。全书分为四部分：部分介绍图神经网络的基本概念；第二部分讨论图神经网络成熟的方法；第三部分介绍图神经网络典型的前沿领域；第四部分描述可能对图神经网络未来研究比较重要和有前途的方法与应用的进展情况。

本书适合高年级本科生和研究生、博士后研究人员、讲师以及行业从业者阅读与参考。

本书致力于介绍图神经网络的基本概念和算法、研究前沿以及广泛和新兴的应用，涵盖图神经网络的广泛主题，从基础到前沿，从方法到应用，涉及从方法论到应用场景方方面面的内容。全书分为四部分：第一部分介绍图神经网络的基本概念；第二部分讨论图神经网络成熟的方法；第三部分介绍图神经网络典型的前沿领域；第四部分描述可能对图神经网络未来研究比较重要和有前途的方法与应用的进展情况。

本书适合高年级本科生和研究生、博士后研究人员、讲师以及行业从业者阅读与参考。

吴凌飞博士 毕业于美国公立常春藤盟校之一的威廉与玛丽学院计算机系。目前他是Pinterest公司主管知识图谱和内容理解的研发工程经理。曾任硅谷研究中心的首席科学家和IBM Thomas J. Vatson Research Centerl的高级研究员。主要研究方向是机器学习、表征学习和自然语言处理的有机结合，在图神经网络及其应用方面有深入研究。他在机器学习、深度学习等领域的著名会议或期刊上发表100多篇论文。 崔鹏博士 清华大学计算机系终身副教授。于2010年在清华大学获得博士学位。研究兴趣包括数据挖掘、机器学习和多媒体分析，擅长网络表示学习、因果推理和稳定学习、社会动力学建模和用户行为建模等。他在机器学习和数据挖掘领域的著名会议或期刊上发表100多篇论文。 裴健博士 杜克大学电子与计算机工程系教授。他是数据科学、大数据、数据挖掘和数据库系统等领域的研究人员。他擅长为新型数据密集型应用开发有效的数据分析技术，并将其研究成果转化为产品和商业实践。自2000年以来，他已经出版一本教科书、两本专著，并在众多具有影响力的会议或期刊上发表300多篇论文。 赵亮博士 埃默里大学计算科学系助理教授。曾在乔治梅森大学信息科学与技术系和计算机科学系担任助理教授。于2016年在弗吉尼亚理工大学计算机科学系获得博士学位。研究兴趣包括数据挖掘、人工智能和机器学习，在时空和网络数据挖掘、图深度学习、非凸优化、事件预测和可解释机器学习等方面有深入研究。

第 一部分 引言

第 1章 表征学习 2

1.1 导读 2

1.2 不同领域的表征学习 3

1.2.1 用于图像处理的表征学习 3

1.2.2 用于语音识别的表征学习 5

1.2.3 用于自然语言处理的表征学习 7

1.2.4 用于网络分析的表征学习 8

1.3 小结 9

第 2章 图表征学习 11

2.1 导读 11

2.2 传统图嵌入方法 12

2.3 现代图嵌入方法 13

2.3.1 保留图结构和属性的图表征学习 13

2.3.2 带有侧面信息的图表征学习 15

2.3.3 保留高级信息的图表征学习 15

2.4 图神经网络 16

2.5 小结 17

第3章 图神经网络 18

3.1 导读 18

3.2 图神经网络概述 19

3.2.1 图神经网络基础 19

3.2.2 图神经网络前沿 20

3.2.3 图神经网络应用 22

3.2.4 本书组织结构 23

3.3 小结 24

第二部分 基础

第4章 用于节点分类的图神经网络 28

4.1 背景和问题定义 28

4.2 有监督的图神经网络 29

4.2.1 图神经网络的一般框架 29

4.2.2 图卷积网络 30

4.2.3 图注意力网络 32

4.2.4 消息传递神经网络 33

4.2.5 连续图神经网络 33

4.2.6 多尺度谱图卷积网络 35

4.3 无监督的图神经网络 37

4.3.1 变分图自编码器 37

4.3.2 深度图信息化 39

4.4 过平滑问题 41

4.5 小结 42

第5章 图神经网络的表达能力 44

5.1 导读 44

5.2 图表征学习和问题的提出 47

5.3 强大的消息传递图神经网络 49

5.3.1 用于集合的神经网络 49

5.3.2 消息传递图神经网络 50

5.3.3 MP-GNN的表达能力 51

5.3.4 具有1-WL测试能力的MP-GNN 53

5.4 比1-WL测试更强大的图神经网络架构 54

5.4.1 MP-GNN的局限性 54

5.4.2 注入随机属性 56

5.4.3 注入确定性距离属性 61

5.4.4 建立高阶图神经网络 65

5.5 小结 69

第6章 图神经网络的可扩展性 71

6.1 导读 71

6.2 引言 72

6.3 抽样范式 72

6.3.1 节点级抽样 74

6.3.2 层级抽样 76

6.3.3 图级抽样 79

6.4 大规模图神经网络在推荐系统中的应用 82

6.4.1 物品-物品推荐 82

6.4.2 用户-物品推荐 83

6.5 未来的方向 84

第7章 图神经网络的可解释性 86

7.1 背景：深度模型的可解释性 86

7.1.1 可解释性和解释的定义 86

7.1.2 解释的价值 87

7.1.3 传统的解释方法 88

7.1.4 机遇与挑战 90

7.2 图神经网络的解释方法 90

7.2.1 背景 91

7.2.2 基于近似的解释 92

7.2.3 基于相关性传播的解释 95

7.2.4 基于扰动的解释 96

7.2.5 生成式解释 97

7.3 图神经网络的可解释模型 97

7.3.1 基于GNN的注意力模型 98

7.3.2 图上的解耦化表征学习 100

7.4 图神经网络解释的评估 101

7.4.1 基准数据集 101

7.4.2 评价指标 103

7.5 未来的方向 103

第8章 图神经网络的对抗鲁棒性 105

8.1 动机 105

8.2 图神经网络的局限性：对抗性样本 107

8.2.1 对抗性攻击的分类 107

8.2.2 扰动的影响和一些启示 110

8.2.3 讨论和未来的方向 112

8.3 可证明的鲁棒性：图神经网络的认证 113

8.3.1 特定模型的认证 113

8.3.2 模型无关的认证 115

8.3.3 高级认证和讨论 116

8.4 提高图神经网络的鲁棒性 117

8.4.1 改进图 117

8.4.2 改进训练过程 118

8.4.3 改进图神经网络的架构 120

8.4.4 讨论和未来的方向 121

8.5 从鲁棒性的角度进行适当评估 122

8.6 小结 124

第三部分 前沿

第9章 图分类 128

9.1 导读 128

9.2 用于图分类的图神经网络：典型工作和现代架构 129

9.2.1 空间方法 129

9.2.2 频谱方法 132

9.3 池化层：从节点级输出学习图级输出 133

9.3.1 基于注意力的池化层 134

9.3.2 基于聚类的池化层 134

9.3.3 其他池化层 134

9.4 图神经网络和高阶层在图分类中的局限性 135

9.5 图神经网络在图分类中的应用 137

9.6 基准数据集 137

9.7 小结 138

第 10章 链接预测 139

10.1 导读 139

10.2 传统的链接预测方法 140

10.2.1 启发式方法 140

10.2.2 潜在特征方法 143

10.2.3 基于内容的方法 145

10.3 基于GNN的链接预测方法 145

10.3.1 基于节点的方法 145

10.3.2 基于子图的方法 147

10.3.3 比较基于节点的方法和基于子图的方法 150

10.4 链接预测的理论 151

10.4.1 γ?C衰减启发式理论 151

10.4.2 贴标签技巧 155

10.5 未来的方向 158

10.5.1 加速基于子图的方法 158

10.5.2 设计更强大的贴标签技巧 159

10.5.3 了解何时使用独热特征 159

第 11章 图生成 160

11.1 导读 160

11.2 经典的图生成模型 160

11.2.1 Erd s-Rényi模型 161

11.2.2 随机块模型 162

11.3 深度图生成模型 163

11.3.1 表征图 163

11.3.2 变分自编码器方法 164

11.3.3 深度自回归方法 168

11.3.4 生成对抗网络方法 174

11.4 小结 178

第 12章 图转换 179

12.1 图转换问题的形式化 179

12.2 节点级转换 180

12.2.1 节点级转换的定义 180

12.2.2 交互网络 180

12.2.3 时空卷积循环神经网络 181

12.3 边级转换 182

12.3.1 边级转换的定义 182

12.3.2 图转换生成对抗网络 183

12.3.3 多尺度图转换网络 184

12.3.4 图转换策略网络 185

12.4 节点-边共转换 186

12.4.1 节点-边共转换的定义 186

12.4.2 基于编辑的节点-边共转换 190

12.5 其他基于图的转换 193

12.5.1 序列到图的转换 193

12.5.2 图到序列的转换 194

12.5.3 上下文到图的转换 195

12.6 小结 196

第 13章 图匹配 197

13.1 导读 197

13.2 图匹配学习 198

13.2.1 问题的定义 199

13.2.2 基于深度学习的图匹配模型 200

13.2.3 基于GNN的图匹配模型 201

13.3 图相似性学习 205

13.3.1 问题的定义 205

13.3.2 图-图回归任务 206

13.3.3 图-图分类任务 209

13.4 小结 210

第 14章 图结构学习 211

14.1 导读 211

14.2 传统的图结构学习 212

14.2.1 无监督图结构学习 212

14.2.2 有监督图结构学习 214

14.3 图神经网络的图结构学习 215

14.3.1 图结构和表征的联合学习 216

14.3.2 与其他问题的联系 225

14.4 未来的方向 226

14.4.1 鲁棒的图结构学习 226

14.4.2 可扩展的图结构学习 226

14.4.3 异质图的图结构学习 227

14.5 小结 227

第 15章 动态图神经网络 228

15.1 导读 228

15.2 背景和表示法 229

15.2.1 图神经网络 229

15.2.2 序列模型 230

15.2.3 编码器-解码器框架和模型训练 233

15.3 动态图的类型 233

15.3.1 离散型与连续型 234

15.3.2 演变类型 235

15.3.3 预测问题、内插法和外推法 235

15.4 用图神经网络对动态图进行建模 236

15.4.1 将动态图转换为静态图 236

15.4.2 用于DTDG的图神经网络 238

15.4.3 用于CTDG的图神经网络 240

15.5 应用 242

15.5.1 基于骨架的人类活动识别 243

15.5.2 交通预测 244

15.5.3 时序知识图谱补全 245

15.6 小结 247

第 16章 异质图神经网络 248

16.1 HGNN简介 248

16.1.1 HG的基本概念 249

16.1.2 异质性给HG嵌入带来的独特挑战 250

16.1.3 对HG嵌入发展的简要概述 251

16.2 浅层模型 251

16.2.1 基于分解的方法 252

16.2.2 基于随机游走的方法 253

16.3 深度模型 254

16.3.1 基于消息传递的方法 254

16.3.2 基于编码器-解码器的方法 257

16.3.3 基于对抗的方法 257

16.4 回顾 259

16.5 未来的方向 259

16.5.1 结构和属性保存 259

16.5.2 更深入的探索 260

16.5.3 可靠性 260

16.5.4 应用 261

第 17章 自动机器学习 262

17.1 背景 262

17.1.1 AutoGNN的表示法 264

17.1.2 AutoGNN的问题定义 264

17.1.3 AutoGNN的挑战 265

17.2 搜索空间 265

17.2.1 架构搜索空间 266

17.2.2 训练超参数搜索空间 268

17.2.3 高效的搜索空间 269

17.3 搜索算法 269

17.3.1 随机搜索 269

17.3.2 进化搜索 270

17.3.3 基于强化学习的搜索 270

17.3.4 可微搜索 271

17.3.5 高效的表现评估 272

17.4 未来的方向 273

第 18章 自监督学习 275

18.1 导读 275

18.2 自监督学习概述 276

18.3 将SSL应用于图神经网络：对训练策略、损失函数和代理任务进行分类 277

18.3.1 训练策略 278

18.3.2 损失函数 281

18.3.3 代理任务 283

18.4 节点级代理任务 283

18.4.1 基于结构的节点级代理任务 284

18.4.2 基于特征的节点级代理任务 285

18.4.3 混合代理任务 285

18.5 图级代理任务 287

18.5.1 基于结构的图级代理任务 287

18.5.2 基于特征的图级代理任务 291

18.5.3 混合代理任务 291

18.6 节点-图级代理任务 293

18.7 讨论 294

18.8 小结 295

第四部分 广泛和新兴的应用

第 19章 现代推荐系统中的图神经网络 298

19.1 图神经网络在推荐系统中的实践 298

19.1.1 简介 298

19.1.2 预测用户-物品偏好的经典方法 302

19.1.3 用户-物品推荐系统中的物品推荐：二分图的视角 302

19.2 案例研究1：动态的GNN学习 304

19.2.1 动态序贯图 304

19.2.2 DSGL 304

19.2.3 模型预测 307

19.2.4 实验和讨论 308

19.3 案例研究2：设备-云协作的GNN学习 309

19.3.1 提议的框架 309

19.3.2 实验和讨论 312

19.4 未来的方向 313

第 20章 计算机视觉中的图神经网络 315

20.1 导读 315

20.2 将视觉表征为图 316

20.2.1 视觉节点表征 316

20.2.2 视觉边表征 317

20.3 案例研究1：图像 318

20.3.1 物体检测 318

20.3.2 图像分类 319

20.4 案例研究2：视频 320

20.4.1 视频动作识别 320

20.4.2 时序动作定位 322

20.5 其他相关工作：跨媒体 322

20.5.1 视觉描述 322

20.5.2 视觉问答 323

20.5.3 跨媒体检索 324

20.6 图神经网络在计算机视觉中的前沿问题 324

20.6.1 用于计算机视觉的高级图神经网络 325

20.6.2 图神经网络在计算机视觉中的更广泛应用 325

20.7 小结 326

第 21章 自然语言处理中的图神经网络 327

21.1 导读 327

21.2 将文本建模为图 329

21.2.1 自然语言处理中的图表征 329

21.2.2 从图的角度完成自然语言处理任务 330

21.3 案例研究1：基于图的文本聚类和匹配 332

21.3.1 基于图聚类的热点事件发现和组织 332

21.3.2 使用图分解和卷积进行长文档匹配 333

21.4 案例研究2：基于图的多跳阅读理解 335

21.5 未来的方向 338

21.6 小结 339

第 22章 程序分析中的图神经网络 341