網絡嵌入：理論、方法和應用

杨成，北京邮电大学计算机学院副教授。他分别于 2014 年和 2019 年获得清华大学计算机科学专业学士学位和博士学位。其研究方向包括网络表示学习、社会计算和自然语言处理，在 IJCAI、ACL、ACM TOIS、IEEE TKDE 等top级会议和期刊上发表论文四十余篇，谷歌学术引用近四千次。

刘知远，清华大学计算机科学与技术系副教授。他分别于在 2006 年和 2011 年获得清华大学计算机科学与技术专业学士和博士学位。研究方向是自然语言处理和社会计算，在国际期刊和 IJCAI、AAAI、ACL、EMNLP 等会议上发表了六十余篇论文，谷歌学术应用量超过一万次。

涂存超，清华大学计算机科学与技术系博士后。他分别于 2013 年和 2018 年获得清华大学计算机科学与技术专业学士和博士学位。其研究方向包括网络表示学习、社会计算和法律智能，在 IEEE TKDE、AAAI、ACL、EMNLP 等国际期刊和会议上发表论文二十余篇。

石川，北京邮电大学计算机学院教授。其主要研究方向包括数据挖掘、机器学习和大数据分析。在数据挖掘方面的top级期刊和会议，如 IEEE TKDE、ACM TIST、KDD、WWW、AAAI 和 IJCAI 等，发表了相关论文一百余篇。

孙茂松，清华大学计算机科学与技术系教授，清华大学人工智能研究院常务副院长。其研究方向包括自然语言处理、互联网智能、机器学习、社会计算和计算教育学，在各种top级会议和期刊上发表论文二百余篇，谷歌学术引用量超 1.5 万次，并于 2020 年当选欧洲科学院外籍院士。

第 一部分 網絡嵌入介紹

第 1 章 網絡嵌入基礎 3

1.1 背景 3

1.2 網絡嵌入的興起 4

1.3 網絡嵌入的評估 5

1.3.1 節點分類 6

1.3.2 鏈接預測 6

1.3.3 節點聚類 6

第 2 章 一般圖的網絡嵌入 9

2.1 代表性方法 9

2.1.1 早期工作 (約 2001～2013) 9

2.1.2 近期工作（2014 至今） 10

2.2 理論：一種統一的網絡嵌入框架 13

2.2.1 k 階鄰近度 13

2.2.2 網絡表示學習框架 14

2.2.3 對比觀察 16

2.3 方法：網絡嵌入更新 17

2.3.1 問題形式化 17

2.3.2 近似算法 18

2.4 實驗 19

2.4.1 數據集 19

2.4.2 基線方法和實驗設置 20

2.4.3 多標簽分類 21

2.4.4 鏈接預測 22

2.4.5 實驗分析 22

2.5 擴展閱讀 23

第二部分 結合附加信息的網絡嵌入

第 3 章 結合節點屬性的網絡嵌入 27

3.1 概述 27

3.2 方法: 文本輔助 DeepWalk 28

3.2.1 低秩矩陣分解 29

3.2.2 TADW 算法 29

3.2.3 復雜度分析 30

3.3 實驗分析 30

3.3.1 數據集 31

3.3.2 TADW 設置 31

3.3.3 基線方法 31

3.3.4 分類器和實驗設置 32

3.3.5 實驗結果分析 32

3.3.6 案例分析 34

3.4 擴展閱讀 34

第 4 章 回顧結合節點屬性的網絡嵌入：一種基於圖捲積網絡的視角 37

4.1 基於圖捲積網絡的網絡嵌入 37

4.1.1 圖捲積網絡 37

4.1.2 基於圖捲積網絡的屬性圖嵌入 35

4.1.3 討論 39

4.2 方法：自適應圖編碼器 40

4.2.1 問題形式化 40

4.2.2 總體框架 40

4.2.3 拉普拉斯平滑濾波器 41

4.2.4 自適應編碼器 43

4.3 實驗分析 46

4.3.1 數據集 46

4.3.2 基線方法 46

4.3.3 評估指標和參數設置 47

4.3.4 節點聚類結果 48

4.3.5 鏈接預測結果 48

4.3.6 GAE 與 LS+RA 49

4.3.7 消融實驗 49

4.3.8 k 值的選取 50

4.3.9 可視化 52

4.4 擴展閱讀 53

第 5 章 結合節點內容的網絡嵌入 55

5.1 概述 55

5.2 方法：上下文感知網絡嵌入 56

5.2.1 問題形式化 56

5.2.2 總體框架 57

5.2.3 基於結構的目標 57

5.2.4 基於文本的目標 58

5.2.5 上下文無關的文本表示 58

5.2.6 上下文感知的文本表示 59

5.2.7 CANE 的優化 61

5.3 實驗分析 61

5.3.1 數據集 61

5.3.2 基線方法 62

5.3.3 評估指標和實驗設置 62

5.3.4 鏈接預測 63

5.3.5 節點分類 64

5.3.6 案例分析 65

5.4 擴展閱讀 66

第 6 章 結合節點標簽的網絡嵌入 69

6.1 概述 69

6.2 方法：最大間隔 DeepWalk 69

6.2.1 問題形式化 70

6.2.2 基於矩陣分解的 DeepWalk 70

6.2.3 最大間隔 DeepWalk 71

6.2.4 MMDW 的優化 71

6.3 實驗分析 73

6.3.1 數據集和實驗設置 73

6.3.2 基線方法 73

6.3.3 實驗結果和分析 74

6.3.4 可視化 75

6.4 擴展閱讀 76

第三部分 面向不同特性圖結構的網絡嵌入

第 7 章 面向具有社區結構的圖的網絡嵌入 79

7.1 概述 79

7.2 方法：社區增強的網絡表示學習 80

7.2.1 問題形式化 81

7.2.2 DeepWalk 81

7.2.3 社區增強的 DeepWalk 81

7.3 實驗分析 84

7.3.1 數據集 84

7.3.2 基線方法 84

7.3.3 評測指標和參數設置 85

7.3.4 節點分類 86

7.3.5 鏈接預測 86

7.3.6 社區發現 87

7.3.7 發現社區的可視化 87

7.4 擴展閱讀 88

第 8 章 面向大規模圖的網絡嵌入 91

8.1 概述 92

8.2 方法：壓縮式網絡嵌入 93

8.2.1 問題形式化 94

8.2.2 圖劃分 94

8.2.3 組映射 95

8.2.4 組聚合 96

8.2.5 目標函數和優化 96

8.3 實驗分析 97

8.3.1 數據集 97

8.3.2 基線方法和實驗設置 98

8.3.3 鏈接預測 99

8.3.4 多標簽分類 99

8.3.5 可擴展性 102

8.3.6 時間效率 103

8.3.7 不同的圖劃分算法 104

8.4 擴展閱讀 105

第 9 章 面向異質圖的網絡嵌入 107

9.1 概述 107

9.2 方法：關系結構感知的異質圖嵌入 109

9.2.1 問題形式化 109

9.2.2 數據觀察 109

9.2.3 基本思想 111

9.2.4 附屬關系和交互關系的建模 112

9.2.5 異質圖嵌入的統一模型 113

9.3 實驗分析 113

9.3.1 數據集 113

9.3.2 基線方法 113

9.3.3 參數設置 114

9.3.4 節點聚類 114

9.3.5 鏈接預測 115

9.3.6 節點分類 115

9.3.7 變體模型的比較 116

9.3.8 可視化 117

9.4 擴展閱讀 118

第四部分 網絡嵌入應用

第 10 章 面向社會關系抽取的網絡嵌入 123

10.1 概述 123

10.2 方法: 平移網絡 124

10.2.1 問題形式化 124

10.2.2 平移機制 124

10.2.3 邊表示構建 126

10.2.4 整體模型 127

10.2.5 預測 127

10.3 實驗分析 128

10.3.1 數據集 128

10.3.2 基線模型 128

10.3.3 評測指標和實驗設置 129

10.3.4 實驗結果和分析 129

10.3.5 標簽對比 130

10.3.6 案例分析 131

10.4 擴展閱讀 131

第 11 章 面向基於位置的社交網絡推薦系統的網絡嵌入 133

11.1 概述 133

11.2 方法: 網絡與軌跡聯合模型 135

11.2.1 問題形式化 135

11.2.2 社交網絡構建建模 136

11.2.3 移動軌跡生成建模 137

11.2.4 整體模型 141

11.2.5 參數學習 142

11.3 實驗分析 143

11.3.1 數據集 143

11.3.2 評估任務與基線方法 144

11.3.3 下一個位置推薦任務實驗結果 145

11.3.4 好友推薦任務實驗結果 148

11.4 擴展閱讀 149

第 12 章 面向信息傳播預測的網絡嵌入 153

12.1 概述 153

12.2 方法：神經傳播模型 155

12.2.1 問題形式化 155

12.2.2 模型假設 156

12.2.3 使用註意力機制提取活躍用戶 157

12.2.4 使用捲積神經網絡聚合活躍用戶表示進行預測 158

12.2.5 整體架構、模型細節和學習算法 159

12.3 實驗分析 159

12.3.1 數據集 160

12.3.2 基線模型 160

12.3.3 超參數設置 161

12.3.4 微觀級別的傳播預測 161

12.3.5 網絡嵌入的好處 163

12.3.6 可解釋性 164

12.4 擴展閱讀 165

第五部分 網絡嵌入展望

第 13 章 網絡嵌入的未來方向 169

13.1 基於先進技術的網絡嵌入 169

13.2 更細粒度場景中的網絡嵌入 169

13.3 具有更好的可解釋性的網絡嵌入 170

13.4 面向應用的網絡嵌入 170

參考文獻 171