圖機器學習

武強，蘭州大學副研究員。長期從事人工智能與復雜系統領域的交叉研究，參與並主

持多個重點科研項目，致力於推動前沿人工智能技術在交通、氣象等領域的行業落地應用。多項成果已成功轉化並應用於我國城市交通系統。在ICML、KDD、AAAI等國

際AI會議及Future Generation Computer Systems（FGCS）、Knowledge-Based

Systems（KBS）等期刊發表論文20余篇。曾榮獲谷歌“全球機器學習開發者專家”

（Google Developer Expert，GDE）稱號。著有《人工智能技術基礎》《元宇宙中的硬科技》等圖書。

呂琳媛，中國科學技術大學教授，“中國青年女科學家獎”“科學探索獎”獲得者。

長期從事復雜系統與復雜網絡領域的研究，發表學術論文100余篇，谷歌學術引用近2

萬次。2019年入選《麻省理工科技評論》“中國35歲以下科技創新35人”，2020年獲“系統科學與系統工程科學技術獎——青年科技獎”，2022年獲Erd?s–Rényi Prize獎。出版《鏈路預測》《重塑：信息經濟的結構》《網絡滲流》《反常識》等圖書。

第 1章 引言 1

1.1 圖機器學習概述 2

1.1.1　為什麼需要圖機器學習 2

1.1.2　圖機器學習的分類 3

1.2 圖機器學習應用 5

1.3 圖機器學習任務 8

1.3.1 節點預測 8

1.3.2 鏈接預測 8

1.3.3 整圖預測 9

1.4 圖機器學習展望 9

1.5 本章小結 10

1.6 參考文獻 10

 

第 2章 圖機器學習基礎 12

2.1 圖論基礎 13

2.1.1 基本概念 13

2.1.2 表示方法 15

2.1.3 節點重要性指標 16

2.1.4 異質圖 20

2.1.5 圖生成模型 22

2.1.6 網絡子圖 28

2.1.7 網絡社區 30

2.2 機器學習基礎 34

2.2.1 感知機 34

2.2.2 深度學習 35

2.2.3 激活函數 36

2.2.4 損失函數和梯度下降 37

2.2.5 反向傳播 39

2.3 本章小結 39

2.4 參考文獻 39

 

第3章 基於圖基礎結構特征的圖機器學習 41

3.1 圖基礎結構特征與圖機器學習 42

3.2 基於節點特征的圖機器學習 43

3.2.1 用聚類系數表示節點特征 43

3.2.2 用圖元向量表示節點特征 44

3.3 基於鏈接特征的圖機器學習 46

3.3.1 基於距離的特征 46

3.3.2 局部鄰域重疊 47

3.3.3 全局鄰域重疊 48

3.4 基於整圖特征的圖機器學習 49

3.4.1 基於圖內核的表示方法 49

3.4.2 基於圖元特征的表示方法 49

3.4.3 基於WL內核的表示方法 50

3.5 本章小結 53

3.6 參考文獻 53

 

第4章 圖嵌入表示 54

4.1 為什麼需要圖嵌入 55

4.2 圖嵌入的編/解碼架構 56

4.3 節點嵌入 57

4.3.1 淺層嵌入 57

4.3.2 隨機遊走嵌入 58

4.3.3 有偏隨機遊走嵌入 60

4.4 整圖嵌入 62

4.4.1 求和法 62

4.4.2 虛擬節點法 63

4.4.3 匿名遊走嵌入 63

4.4.4 可學習遊走嵌入 64

4.4.5 整圖嵌入的應用 65

4.5 本章小結 65

4.6 參考文獻 66

 

第5章 圖矩陣分解 67

5.1 矩陣分解與節點嵌入 68

5.1.1 矩陣分解 68

5.1.2 矩陣分解與隨機遊走的局限性 69

5.2 PageRank算法 70

5.2.1 PageRank算法背景 70

5.2.2 PageRank矩陣表示 71

5.2.3 PageRank與隨機遊走 72

5.3 PageRank計算和優化 73

5.3.1 冪疊代法 73

5.3.2 PageRank存在的問題 73

5.3.3 PageRank算法的局限性 74

5.3.4 個性化PageRank和帶重啟的隨機遊走 75

5.4 本章小結 76

5.5 參考文獻 77

 

第6章 消息傳遞與節點分類 78

6.1 網絡關聯與集體分類 79

6.1.1 網絡關聯 79

6.1.2 集體分類 80

6.2 關系分類 81

6.3 疊代分類 83

6.3.1 疊代分類定義 83

6.3.2 疊代分類方法 83

6.3.3 疊代分類過程舉例 84

6.4 信念傳播 85

6.4.1 信念傳播定義 86

6.4.2 信念傳播過程 86

6.4.3 信念傳播的優點和不足 87

6.5 矯正與平滑 87

6.5.1 C&S方法介紹 88

6.5.2 用C&S方法處理節點預測問題 88

6.6 本章小結 92

6.7 參考文獻 92

 

第7章 圖神經網絡研究思路與經典模型 93

7.1 圖神經網絡的研究思路 94

7.1.1 圖神經網絡基礎 94

7.1.2 圖神經網絡方法 97

7.1.3 圖神經網絡訓練 98

7.2 圖神經網絡的結構 99

7.2.1 網絡結構 100

7.2.2 批量標準化 100

7.2.3 Dropout方法 101

7.3 經典圖神經網絡：圖卷積神經網絡 102

7.3.1 GCN的空域理解 102

7.3.2 圖傅裏葉變換 104

7.3.3 圖卷積神經網絡的譜域解釋 105

7.4 經典圖神經網絡：GraphSAGE和GAT 107

7.4.1 GraphSAGE 107

7.4.2 GAT 108

7.5 代碼實踐 109

7.6 本章小結 111

7.7 參考文獻 111

 

第8章 圖神經網絡設計 112

8.1 多層圖神經網絡設計 113

8.1.1 過度平滑問題的產生 113

8.1.2 過度平滑的解決思路 113

8.2 圖增強設計 115

8.2.1 圖特征增強 115

8.2.2 圖結構增強 116

8.3 圖神經網絡表達能力設計 118

8.3.1 圖神經網絡表達能力概述 119

8.3.2 GCN和GraphSAGE的表達能力分析 120

8.4 圖同構網絡模型 122

8.4.1 重集上的單射函數 122

8.4.2 GIN模型設計 122

8.4.3 GIN模型與WL圖內核的聯系 123

8.5 本章小結 124

8.6 參考文獻 125

 

第9章 圖神經網絡訓練 126

9.1 圖神經網絡預測頭設置 127

9.1.1 節點級別任務 127

9.1.2 鏈接級別任務 128

9.1.3 圖級別任務 128

9.2 圖神經網絡訓練基礎條件 130

9.2.1 損失函數 130

9.2.2 評估函數 131

9.3 圖神經網絡訓練流程 134

9.3.1 數據集劃分 134

9.3.2 GNN訓練流程 137

9.3.3　GNN設置和調試 137

9.4 代碼實踐 138

9.4.1 數據介紹 138

9.4.2 多層 GNN 模型實現 139

9.4.3 訓練和測試過程 141

9.5 本章小結 143

9.6 參考文獻 143

 

第 10章 圖神經網絡優化 144

10.1 圖神經網絡的局限性 145

10.1.1 結構識別缺陷 145

10.1.2 位置識別缺陷 146

10.1.3 圖同構測試限制GNN的表達能力上限 147

10.2 圖神經網絡的優化思路 147

10.2.1 基於位置感知的GNN優化 148

10.2.2 基於身份感知的GNN優化 149

10.3 圖神經網絡的魯棒性分析 153

10.3.1 深度學習的魯棒性 153

10.3.2 GNN的魯棒性 153

10.4 本章小結 156

10.5 參考文獻 157

 

第 11章 大規模圖神經網絡 158

11.1 GNN在大規模網絡中的應用 159

11.1.1 大規模圖應用場景 159

11.1.2 大規模圖應用問題 159

11.2 鄰域抽樣模型 160

11.2.1 模型思路 161

11.2.2 重啟隨機遊走算法 162

11.2.3 避免冗余計算的模型 162

11.3 Cluster-GCN模型 163

11.3.1 模型思路 164

11.3.2 模型訓練 165

11.3.3 模型優化 166

11.4 Simplifying-GCN模型 166

11.4.1 模型思路 167

11.4.2 模型訓練 167

11.5 本章小結 168

11.6 參考文獻 168

 

第 12章 圖神經網絡在知識圖譜中的應用 169

12.1 關系圖卷積神經網絡 170

12.1.1 R-GCN模型介紹 170

12.1.2 R-GCN的擴展性 172

12.1.3 R-GCN的應用 172

12.2 知識圖譜初步 174

12.2.1 知識圖譜概念 174

12.2.2 知識圖譜補全 175

12.3 知識圖譜查詢 179

12.3.1 基礎查詢 180

12.3.2 高級查詢 181

12.4 知識圖譜構建和存儲 187

12.4.1 知識圖譜構建 187

12.4.2 知識圖譜存儲 189

12.5 本章小結 190

12.6 參考文獻 190

 

第 13章 圖神經網絡在網絡科學領域的應用 191

13.1 深度圖生成模型 192

13.1.1 深度圖生成模型初步 192

13.1.2 GraphRNN圖生成模型 194

13.1.3 圖生成模型的評估和優化 197

13.2 基於圖神經網絡的子圖挖掘 201

13.2.1 子圖嵌入表示 201

13.2.2 識別高頻子圖結構 204

13.3 基於圖神經網絡的社區發現 206

13.3.1 Louvain算法 206

13.3.2 重疊社區檢測算法BigCLAM和NOCD 210

13.4 本章小結 215

13.5 參考文獻 215

 

第 14章 圖神經網絡在推薦系統和自然語言處理中的應用 216

14.1 圖神經網絡與推薦系統 217

14.1.1 推薦系統概述 217

14.1.2 基於圖節點嵌入的推薦模型 218

14.1.3 基於協同過濾的GNN推薦模型 220

14.1.4 大規模圖神經網絡推薦模型PinSAGE 225

14.2 圖神經網絡與自然語言處理 227

14.2.1 自然語言處理概要 227

14.2.2 NLP中圖的構建與處理 230

14.2.3 基於圖的編碼器-解碼器模型 233

14.2.4 圖在自然語言處理中的具體應用 235

14.3 本章小結 238

14.4 參考文獻 239

 

第 15章 圖神經網絡在自然科學研究中的應用 242

15.1 圖神經網絡在物理學中的應用 243

15.1.1 圖神經網絡重新發現萬有引力定律 243

15.1.2 用圖神經網絡實現復雜物理世界的仿真模擬 244

15.2 圖神經網絡在生物化學和醫療領域的應用 245

15.2.1 GNN輔助藥物發現 246

15.2.2 GNN預測蛋白質折疊結構 248

15.2.3 GNN輔助醫療診斷 250

15.2.4　GNN與天氣預報 251

15.3 本章小結 252

15.4 參考文獻 252

 

第 16章 總結和展望 253

16.1 圖機器學習模型及應用 254

16.1.1 圖機器學習模型總結 254

16.1.2 圖機器學習應用總結 254

16.2 圖機器學習未來展望 255

16.2.1 預訓練圖神經網絡 255

16.2.2 雙曲圖神經網絡 255

16.2.3 圖機器學習與其他技術的結合 256