圖神經網絡：基礎、前沿與應用

吴凌飞博士

毕业于美国公立常春藤盟校之一的威廉与玛丽学院计算机系。目前他是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 γ–衰減啟發式理論 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

22.1 導讀 341

22.2 程序分析中的機器學習 342

22.3 程序的圖表徵 343

22.4 用於程序圖的圖神經網絡 345

22.5 案例研究1：檢測變量誤用缺陷 346

22.6 案例研究2：預測動態類型化語言中的類型 348

22.7 未來的方向 350

第 23章 軟件挖掘中的圖神經網絡 352

23.1 導讀 352

23.2 將軟件建模為圖 353

23.2.1 宏觀與微觀層面的表徵 353

23.2.2 將宏觀和微觀層面的表徵結合起來 354

23.3 相關的軟件挖掘任務 355

23.4 軟件挖掘任務實例：源代碼總結 357

23.4.1 基於GNN的源代碼總結快速入門 357

23.4.2 改進的方向 363

23.5 小結 364

第 24章 藥物開發中基於圖神經網絡的生物醫學知識圖譜挖掘 366

24.1 導讀 366

24.2 現有的生物醫學知識圖譜 367

24.3 知識圖譜的推理 369

24.3.1 傳統的KG推理技術 370

24.3.2 基於GNN的KG推理技術 371

24.4 藥物開發中基於KG的假設生成 374

24.4.1 基於KG的藥物再利用的機器學習框架 374

24.4.2 基於KG的藥物再利用在COVID-19中的應用 375

24.5 未來的方向 376

24.5.1 KG質量控制 376

24.5.2 可擴展的推理 377

24.5.3 KG與其他生物醫學數據的結合 378

第 25章 預測蛋白質功能和相互作用的圖神經網絡 383

25.1 從蛋白質的相互作用到功能簡介 383

25.1.1 登上舞臺：蛋白質-蛋白質相互作用網絡 384

25.1.2 問題形式化、假設和噪聲：從歷史的視角 384

25.1.3 淺層機器學習模型 385

25.1.4 好戲上演：圖神經網絡 386

25.2 三個典型的案例研究 387

25.2.1 案例研究1：蛋白質-蛋白質和蛋白質-藥物相互作用的預測 387

25.2.2 案例研究2：蛋白質功能和功能重要的殘差的預測 389

25.2.3 案例研究3：使用圖自編碼器從生物網絡的表徵中學習多關系鏈接預測 391

25.3 未來的方向 393

第 26章 異常檢測中的圖神經網絡 395

26.1 導讀 395

26.2 基於GNN的異常檢測的問題 397

26.2.1 特定於數據的問題 397

26.2.2 特定於任務的問題 399

26.2.3 特定於模型的問題 399

26.3 流水線 400

26.3.1 圖的構建和轉換 400

26.3.2 圖表徵學習 401

26.3.3 預測 402

26.4 分類法 403

26.5 案例研究 404

26.5.1 案例研究1：用於惡意賬戶檢測的圖嵌入 404

26.5.2 案例研究2：基於層次註意力機制的套現用戶檢測 404

26.5.3 案例研究3：用於惡意程序檢測的註意力異質圖神經網絡 405

26.5.4 案例研究4：通過圖神經網絡學習程序表徵和相似性度量的圖匹配框架，用於檢測未知的惡意程序 406

26.5.5 案例研究5：使用基於註意力的時間GCN進行動態圖的異常檢測 408

26.5.6 案例研究6：使用GAS進行垃圾評論檢測 408

26.6 未來的方向 409

第 27章 智慧城市中的圖神經網絡 410

27.1 用於智慧城市的圖神經網絡 410

27.1.1 導讀 410

27.1.2 圖神經網絡在智慧城市中的應用場景 411

27.1.3 將城市系統表徵為圖 413

27.1.4 案例研究1：圖神經網絡在交通和城市規劃中的應用 415

27.1.5 案例研究2：圖神經網絡在城市事件和異常情況預測中的應用 417

27.1.6 案例研究3：圖神經網絡在城市人類行為分析中的應用 417

27.2 未來的方向 419

參考文獻 420