圖數據挖掘-演算法、安全與應用 宣琦 阮中遠 閔勇 9787302637141 【台灣高等教育出版社】

編輯推薦
《圖數據挖掘：演算法、安全與應用》提供了對圖數據挖掘方法的最新評述，在此基礎上引申出一個前沿課題，即圖數據挖掘的安全性問題，並介紹了一系列檢測方法來識別圖數據中的對抗樣本。此外，它向讀者介紹了圖數據增強和子圖網路以進一步增強模型，即提高其準確性和魯棒性。最後，本書描述了這些前沿演算法在各種場景中的應用，例如交通網路、社交和技術網路以及區塊鏈交易網路等。

內容簡介
網路圖的表徵能力異常強大，它能夠對事物之間任意類型的相互作用關係進行建模，因此網路圖數據在生物信息、交通網路、科研合作、萬維網和社交網路等領域的一系列實際場景中隨處可見。圖數據挖掘用於從圖數據中發現有用的信息和知識。然而，網路中節點和鏈路及其半結構形式的複雜性在各種計算任務，如節點分類、鏈路預測和圖分類等方面提出了挑戰。在這一背景下，研究人員最近提出了各種前沿的圖機器學習演算法，包括圖嵌入和圖神經網路，顯著地提升了圖數據挖掘的性能。
《圖數據挖掘：演算法、安全與應用》提供了對圖數據挖掘方法的最新評述，在此基礎上引申出一個前沿課題，即圖數據挖掘的安全性問題，並介紹了一系列檢測方法來識別圖數據中的對抗樣本。此外，它向讀者介紹了圖數據增強和子圖網路以進一步增強模型，即提高其準確性和魯棒性。最後，本書描述了這些前沿演算法在各種場景中的應用，例如交通網路、社交和技術網路以及區塊鏈交易網路等。

目錄
第1章 基於多通道圖神經網路的信息源估計 1
1 1 介紹 1
1 2 相關工作 5
1 2 1 信息擴散模型 5
1 2 2 信息源檢測 6
1 2 3 圖神經網路 7
1 3 準備工作 8
1 4 多通道圖神經網路 10
1 4 1 輸入的特徵指數 11
1 4 2 圖卷積網路 14
1 4 3 MCGNN的體繫結構 15
1 4 4 損失函數 17
1 5 實驗 17
1 5 1 數據集和實驗裝置 17
1 5 2 基線和評估指標 18
1 5 3 合成網路的結果 20
1 5 4 現實世界網路的結果 23
1 6 本章小結 26
第2章 基於超子結構網路的鏈路預測器 27
2 1 引言 27
2 2 現有的鏈路預測方法 29
2 2 1 啟髮式方法 29
2 2 2 基於嵌入的方法 31
2 2 3 基於深度學習的模型 32
2 3 模型介紹 33
2 3 1 問題表述 33
2 3 2 鄰域歸一化 34
2 3 3 構建HSN 35
2 3 4 HELP 37
2 4 實驗分析 39
2 4 1 數據集 39
2 4 2 鏈路預測方法的比較 40
2 4 3 評價指標 40
2 4 4 實驗設置 41
2 4 5 鏈路預測結果 41
2 4 6 參數的敏感性 45
2 5 本章小結 46
第3章 基於子圖網路的寬度學習圖分類方法 47
3 1 介紹 48
3 2 相關工作 49
3 2 1 子圖網路 49
3 2 2 網路表示 50
3 2 3 寬度學習 50
3 3 子圖網路 51
3 3 1 一階子圖網路 52
3 3 2 二階子圖網路 53
3 4 採樣子圖網路 55
3 4 1 採樣策略 55
3 4 2 構建S2GN 58
3 5 基於S2GN的BLS分類器 59
3 5 1 圖分類 59
3 5 2 BLS分類器 59
3 5 3 分類框架 62
3 6 實驗 62
3 6 1 數據集 62
3 6 2 網路表示 63
3 6 3 基於SGN的圖分類 64
3 6 4 基於S2GN的圖分類 65
3 6 5 計算複雜度 67
3 7 總結與展望 68
第4章 子圖增強及其在圖數據挖掘中的應用 69
4 1 引言 69
4 2 相關工作 71
4 2 1 圖分類 71
4 2 2 圖學習中的數據增強 72
4 3 圖分類模型演化框架 72
4 3 1 問題表述 72
4 3 2 子圖增強 73
4 3 3 數據篩選 77
4 3 4 模型演化框架 77
4 4 子圖增強的應用 79
4 4 1 圖分類 80
4 4 2 鏈路預測 80
4 4 3 節點分類 82
4 4 4 實驗結果 83
4 5 本章小結 86
第5章 基於圖的對抗攻擊：如何隱藏你的結構信息 87
5 1 背景 88
5 2 對抗攻擊 90
5 2 1 問題描述 90
5 2 2 攻擊分類 91
5 3 攻擊策略 93
5 3 1 節點分類 93
5 3 2 鏈路預測 100
5 3 3 圖分類 104
5 3 4 社團檢測 108
5 4 本章小結 113
第6章 基於圖的對抗防禦：提高演算法魯棒性 115
6 1 引言 115
6 2 對抗訓練 117
6 2 1 圖對抗訓練 117
6 2 2 平滑對抗訓練 121
6 3 圖凈化 124
6 3 1 GCN-Jaccard 124
6 3 2 GCN-SVD 126
6 4 魯棒性驗證 127
6 4 1 圖結構擾動下的魯棒性驗證 128
6 4 2 節點屬性擾動下的魯棒性驗證 129
6 4 3 社團檢測的魯棒性驗證 131
6 5 基於結構的防禦 133
6 5 1 懲罰聚合GNN 133
6 5 2 魯棒圖卷積網路 135
6 6 對抗檢測 137
6 6 1 基於節點分類的對抗檢測 137
6 6 2 基於圖分類的對抗檢測 138
6 7 防禦總結 140
6 8 實驗和分析 142
6 8 1 對抗訓練 142
6 8 2 對抗檢測 146
6 9 本章小結 147
第7章 通過網路方法理解以太坊交易 149
7 1 介紹 149
7 2 以太坊交易數據集 151
7 3 圖嵌入技術 153
7 3 1 基於因式分解的方法 153
7 3 2 基於隨機遊走的方法 154
7 3 3 基於深度學習的方法 155
7 3 4 其他方法 156
7 4 方法 156
7 4 1 基本定義 156
7 4 2 動態有偏遊走 158
7 4 3 學習動態圖嵌入 161
7 5 實驗 163
7 5 1 節點分類 163
7 5 2 鏈路預測 165
7 6 本章小結 168
7 7 附錄 169
第8章 尋找你的餐友：Yelp網路案例研究 171
8 1 介紹 171
8 2 數據描述和預處理 173
8 3 鏈路預測方法 176
8 3 1 相似性指數 176
8 3 2 變異圖自動編碼器 177
8 4 實驗分析 178
8 4 1 實驗設置 178
8 4 2 朋友推薦 178
8 4 3 共同覓食的預測 180
8 5 本章小結 183

前言/序言
事物之間的相互作用造就了我們的美麗世界。許多現實世界的系統，無論是自然的還是人工的，都可以自然地表達為圖或網路以捕捉其拓撲特性，而不是採用歐幾里得空間中的坐標形式。在生物學中，蛋白質相互調節，這種生理上的相互作用構成了所謂的生物體的交互組學；神經元相互連接，在大腦中處理信號，導致了智能的湧現；物種相互依賴，從而形成複雜的生態系統。此外，現代交通系統連接了不同國家的不同城市，極大地便利了我們的出行，使整個世界成為真正的地球村。如今，隨著我們進入網路空間，各種網路層出不窮。人們通過Facebook、微信、Twitter、微博等社交網路平台緊密聯繫，分享各自的觀點和個人興趣。人們可以使用谷歌、百度和雅虎等搜索引擎搜索感興趣的信息，而這些系統的核心便是一個巨大的網頁網路。人們還可以通過電子銀行或基於區塊鏈的平台(如以太坊)輕鬆轉移資金。此外，一些強大的數據挖掘或人工智慧技術本質上也是網路，如知識圖譜和深層神經網路。雖然這些網路促進了個人之間的信息交流，使我們的生活比以前更便捷，但也可能為病毒的傳播提供便利，並造成隱私泄露。例如，僅僅根據個人的自我社交網路就可以推斷出特定種類的關係[1]。因此，我們迫切需要發展一些方法來更好地了解這些網路的拓撲結構，以便在一定程度上預測並進一步影響其演變趨勢。
幸運的是，圖論作為數學的一個分支，自1736年歐拉對哥尼斯堡七橋問題的開創性研究以來[2]，已被完備地建立起來。在這個大數據時代，越來越多的系統被描述為圖(網路)，同時，相應的圖數據也被不斷地發布出來以供研究。網路已吸引了來自眾多不同領域的研究人員前赴後繼地投身其中。人們通過提出一系列的結構屬性，從微觀(節點和連邊)、中觀(模體和社團)到宏觀(整個網路)的角度來觀察並進一步測量這些網路[3]。在工業界，許多著名的搜索引擎和推薦系統基本上都是根據節點在相應網路中的結構重要性進行排名的，例如著名的PageRank演算法[4]和協同過濾演算法[5]。另外，在學術界，Strogatz等[6]根據較短的平均距離以及較大的平均聚類係數來表徵小世界網路，而Barabasi等[7]則通過冪律度分佈來定義無標度網路。這些研究引領了複雜網路的發展。隨後，研究人員提出了各種數學模型，模擬並分析了網路上的流行病傳播、同步等不同類型的動力學行為[8]。最近，人們提出了圖嵌入技術，如DeepWalk[9]和Node2Vec[10]，在網路空間和歐幾里得空間之間架起了一座橋樑。因此，我們可以採用機器學習演算法來自動分析圖數據。很快，深度學習框架，如圖卷積網路(GCN)[11， 12]等方法也被陸續提出，用以進一步分析網路圖數據。
在本書中，我們主要關注圖數據的監督學習。特別地，前3章介紹了關於節點分類、鏈路預測和圖分類的最先進的圖數據挖掘演算法，第4章介紹了用於進一步增強這些現有圖數據挖掘演算法的圖增強演算法。第5章和第6章分別分析了這些演算法在對抗攻擊下的脆弱性以及提高其魯棒性的方法。值得注意的是，我們還在第5章中分析了社團檢測作為無監督學習的脆弱性，並進行全面回顧。接下來，我們將對節點分類、鏈路預測和圖分類進行簡要回顧，並簡單介紹本書的各個章節。
第一節點分類可以通過屬性和結構信息來預測未知節點的標籤，這在社會網路分析中具有廣泛應用的場景。在某些情況下，同一類別的節點具有相似的拓撲屬性，因此我們可以使用基本的結構特徵[13]來區分它們，包括節點的度中心性、接近中心性、介數中心性、特徵向量中心性、聚類係數、H指數、核數、PageRank指數等。我們可以使用其中的一個或多個，再加上機器學習演算法來進行分類。這樣的模型相對簡單且可解釋，因為我們很容易知道哪個特徵在模型中更重要，而且幾乎所有這些手工設計的特徵都具有某個特定的物理或社會意義。儘管這種簡單的模型在某些情況下是可行的，但在其他一些情況下可能會失效，特別是當現實世界的網路可能包含數以萬計的節點，且網路拓撲結構不規則時。隨後，研究人員發展了圖嵌入技術，將圖數據轉換為可區分的矢量表示，同時保留固有的圖屬性。通常的嵌入技術主要基於隨機遊走、矩陣分解和神經網路。典型的圖嵌入演算法包括：DeepWalk[9]，它基於skip-gram模型[14]，利用網路中節點之間的共現關係信息得到節點的嵌入向量；GraRep[15]，它通過矩陣分解保留了嵌入空間中圖形的高階接近性；以及 LINE[16]，它保留了節點之間的一階和二階相似性，從而可以同時呈現網路的局部和全局結構信息。此外，隨著深度學習的發展，一系列圖神經網路(GNN)架構被提出，實現了節點的端到端分類。Bruna[17]提出了第一個基於譜域的圖卷積神經網路(GCN)，它通過傅里葉變換將圖和卷積運算擴展到譜域，ChebNet[11]和CayleyNet[18]分別採用切比雪夫多項式和凱利多項式對圖濾波器進行了簡化。Kipf和Welling[12]通過切比雪夫多項式的一階近似進一步簡化了操作，在基於譜域的方法和基於空域的方法之間架起了橋樑。這些研究在很大程度上促進了空域方法的發展，並顯著提高了節點的分類性能。然而，這種深度模型具有高度的非線性和複雜性，使其難以理解並增加了潛在的脆弱性。
在第1章中，殳欣成等設計了一個雙通道的圖神經網路框架來定位網路上的流行病傳播源，這可以被認為是一個典型的節點分類問題。其中，節點通道利用網路結構將每個節點表示為嵌入向量，而連邊通道將原始網路轉換為線圖，並提取線圖中節點的特徵向量作為原始連邊的表示。然後，兩個通道的特徵被整合，用來更好地估計傳播源。
鏈路預測的目的是根據當前觀察到的連邊來預測缺失的或未來的關係[19]，這在社交網路