導(dǎo)讀：數(shù)科安全集群是一個spark集群，承載日常大多數(shù)的數(shù)據(jù)計算，具有強(qiáng)大的安全性。集群具有豐富的資源，因此在spark集群上進(jìn)行圖計算是一個既安全又便利的選擇。圖計算通常分為歸納式學(xué)習(xí)和直推式學(xué)習(xí)兩類，這兩類算法具有不同的計算方式和部署邏輯。

歸納式學(xué)習(xí)（Inductive Learning），從訓(xùn)練集中歸納經(jīng)驗，之后應(yīng)用于測試集。

直推式學(xué)習(xí)（Transductive Learning），從觀測集中的訓(xùn)練點推廣經(jīng)驗，應(yīng)用到觀測集中的測試點；意味著測試點本身是可觀測到的，如果有新的測試點，就需要重新訓(xùn)練。

今天要介紹的主要內(nèi)容是圖算法在數(shù)科安全集群上的應(yīng)用。全文主要分為四個部分：

Inductive類算法的部署

Inductive類常用算法

Transductive類常用算法

總結(jié)和展望

01Inductive類算法的部署

安全集群出于安全的考慮對開發(fā)環(huán)境有較多限制，因此，在已有hadoop和spark的基礎(chǔ)上，接下來重點討論不需要部署而能夠使用的框架或計算方式。

1. 在Spark上運行pytorch框架

部署算法是將算法部署于集群中。Pytorch有專門的分布式模型的封裝接口DistributedDataParallel，內(nèi)部有一套參數(shù)同步方式，也可以通過調(diào)用dist.all_reduce等接口實現(xiàn)。Spark有專門的運行同步訓(xùn)練的RDD結(jié)構(gòu)RDDBarrier。將二者結(jié)合，在RDDBarrier中運行分布式pytorch模型便可以實現(xiàn)在spark上運行pytorch框架。

具體代碼如圖，首先創(chuàng)建RDDBarrier，然后在mapPartition上可直接構(gòu)建pytorch的同步框架。提交時帶上pytorch包的python環(huán)境即可。

2. 在Spark上運行pyg圖學(xué)習(xí)框架

① 采樣服務(wù)器

Pyg是一個圖學(xué)習(xí)框架，可以借助pytorch的分布式接口實現(xiàn)分布式訓(xùn)練，通過Pytorch的DistributedDataParallel實現(xiàn)訓(xùn)練參數(shù)的同步。

參考官方示例可以發(fā)現(xiàn)，在構(gòu)建數(shù)據(jù)集時，需要把所有數(shù)據(jù)加載到單機(jī)上，因此，數(shù)據(jù)集的規(guī)模是需要單機(jī)能負(fù)載的。下面列舉幾種數(shù)據(jù)規(guī)模和的對應(yīng)部署方式。

當(dāng)每個節(jié)點能夠完整讀入頂點和邊的信息時，直接使用DataLoader加載，相當(dāng)于單機(jī)訓(xùn)練，后使用DistributedDataParallel同步參數(shù)。

當(dāng)集群中節(jié)點難以完全存儲，只有Driver端能讀入完整的邊關(guān)系和頂點屬性時，則在Driver端調(diào)用NeighborLoader后分發(fā)給各個worker實現(xiàn)邊采樣邊訓(xùn)練。

當(dāng)Driver端也無法讀入所有信息時，可以只讀入完整的邊關(guān)系，調(diào)用pyg的NeighborSampler對邊進(jìn)行采樣。

當(dāng)只有Driver能讀入完整邊信息時，采用NeighborSampler對邊進(jìn)行采樣。

BlockManager：Spark的底層結(jié)構(gòu)，負(fù)責(zé)RDD存儲，數(shù)據(jù)存儲在本地，需要時拉取其他節(jié)點上的數(shù)據(jù)。由于blockmanager在spark上是私有的，需要封裝一個代理類再暴露給python。

簡單的分布式數(shù)據(jù)庫：借助blockmanager的思想實現(xiàn)一個簡單的分布式數(shù)據(jù)庫，如構(gòu)建sqlite3，本地數(shù)據(jù)直接在sqlite中獲取，非本地數(shù)據(jù)通過all_to_all或者scatter等pytorch操作抽取其他節(jié)點的數(shù)據(jù)。

② 圖分割方式

如上的方法要求所有數(shù)據(jù)至少能存入一臺機(jī)器尤其是邊關(guān)系，但是當(dāng)圖結(jié)構(gòu)巨大單機(jī)無法完全載入時，則必須采用分布式的解決方案，最直接的想法便是將圖分割，分發(fā)到各executor中執(zhí)行圖采樣和計算。

圖分割有多種方式，但是大多都是做多次的s-t割，如Karger’s algorithm每次隨機(jī)選取兩個節(jié)點進(jìn)行s-t分割。這些方式并沒有原生的spark支持，metis和parMetis需要單獨編譯部署，因此并沒有太多的使用。一種折中的方式是使用社區(qū)切分方法，借助LPA、Louvain、業(yè)務(wù)規(guī)則等一些無監(jiān)督社區(qū)發(fā)現(xiàn)算法進(jìn)行圖分割。

③ 分布式圖采樣

使用社區(qū)切分可以將圖的規(guī)?？s小但是分割不一定是均勻的。在Spark中GraphX的隨機(jī)分割是均勻的，當(dāng)單一節(jié)點放不下邊關(guān)系時，可以借助spark的blockmanager，對分發(fā)到各executor的節(jié)點進(jìn)行鄰居采樣，可直接借助GraphX的aggregateMessages在消息聚合時進(jìn)行動態(tài)采樣。可以將以上過程封裝為采樣層，每層運算前均需要調(diào)用一次采樣層。其中，動態(tài)采樣指的是每次采樣固定長度的數(shù)據(jù)。

④ 預(yù)采樣分發(fā)

之前的采樣方式是逐層的方式，因此可以將采樣和訓(xùn)練分離開。Pyg的采樣服務(wù)器本質(zhì)也是采取分離的方式的。因此可以避開復(fù)雜的底層邏輯，直接使用兩輪join采樣，將一個節(jié)點和他的鄰居放在一起直接抽樣好然后分發(fā)。

如下總結(jié)了常見的情況和對應(yīng)的部署方式，前四個都是pyg支持的，最后一個是通用性最強(qiáng)的也是普遍采用的方式，只是速度上相較其他幾種稍微慢些。

⑤ 回溯問題與預(yù)采樣

在標(biāo)簽預(yù)測時，訓(xùn)練集的節(jié)點屬性，節(jié)點間的關(guān)聯(lián)關(guān)系以及節(jié)點的鄰居屬性都必須在標(biāo)簽狀態(tài)時間之前獲取，因此，需要為每個訓(xùn)練節(jié)點構(gòu)建回溯子圖，結(jié)合預(yù)采樣分發(fā)的思路直接分發(fā)后調(diào)用pyg進(jìn)行分布式訓(xùn)練。

02Inductive類常用算法

無監(jiān)督學(xué)習(xí)只利用未標(biāo)記的樣本集，監(jiān)督學(xué)習(xí)只利用標(biāo)記的樣本集進(jìn)行學(xué)習(xí)，同時利用標(biāo)記樣本和未標(biāo)記樣本的是半監(jiān)督學(xué)習(xí)。圖算法在學(xué)習(xí)過程中由于鄰居節(jié)點不一定包含標(biāo)簽信息因此屬于半監(jiān)督學(xué)習(xí)。傳統(tǒng)機(jī)器學(xué)習(xí)的樣本之間通常是獨立的，而圖學(xué)習(xí)的樣本之間卻是有聯(lián)系的，所以圖學(xué)習(xí)較傳統(tǒng)機(jī)器學(xué)習(xí)更為復(fù)雜。

1. 矩陣分解類

該類型的方法特點是快速，但是對圖中屬性信息和結(jié)構(gòu)信息融合比較困難。目前主要應(yīng)用在屬性較少的圖上或者進(jìn)行圖結(jié)構(gòu)的壓縮的任務(wù)上。

① Deepwalk

Deepwalk和Node2vec都是基于矩陣分解類的，其中一個重要的模塊是skip-gram。Skip-gram是對逐點互信息矩陣進(jìn)行分解，其中W代表中心詞，C為對應(yīng)的上下文。

Deepwalk本質(zhì)是在做共現(xiàn)矩陣的分解，走幾步就是幾個鄰接矩陣的加和，所以分解過程和skip-gram的過程相同。當(dāng)圖上節(jié)點缺乏結(jié)構(gòu)關(guān)系時，依舊可以通過屬性分解的方式構(gòu)建。對于沒有結(jié)構(gòu)關(guān)系的節(jié)點使用節(jié)點屬性構(gòu)建余弦相似度矩陣S，分解為H與H轉(zhuǎn)置的乘積，而具有相鄰關(guān)系的節(jié)點對應(yīng)隱變量h也應(yīng)該相近。

2. 編碼器類

矩陣分解類很難融合圖中節(jié)點的結(jié)構(gòu)信息和屬性信息，可以通過編碼器對信息進(jìn)行壓縮后重構(gòu)的方式融合信息，壓縮后的編碼即為embedding。編碼器可以使用各種實現(xiàn)方式，非常自由，但是編碼器很難獲得k-hop的信息。

較為常見的方法是LINE，其通過余弦相似度還原邊權(quán)重建模一階相似度。二階相似性采用word2vec的思路訓(xùn)練，上下文相似的節(jié)點也相似。di為當(dāng)前節(jié)點i的所有邊權(quán)重之和。最終通過拼接一階相似度向量和二階相似度向量得到最終的embedding。但是由于二者尺度和方向的差異，可能會對最終結(jié)果有影響，所以使用較少。

一階建模節(jié)點之間的相似度，二階相似度衡量的是節(jié)點的鄰居節(jié)點集合的相關(guān)程度即鄰接矩陣A每行之間的相關(guān)程度。SDNE通過深度自編碼方式重構(gòu)鄰接矩陣A保留二階相似度。一階相似度采用隱藏層表示的距離來計算，所以最終的損失函數(shù)為一階loss與二階loss以及正則項的和。

將一階和二階信息放到一個解碼器中很容易造成相互影響。因此回到LINE的思路，采用一個編碼器和兩個解碼器的方式減少二者的影響同時也增加了訓(xùn)練參數(shù)。一階信息的重構(gòu)使用一階鄰域的屬性信息做加權(quán)平均或者做元素級平均來重構(gòu)，高階信息可以通過重構(gòu)鄰接矩陣或者使用上下文向量的方式重構(gòu)。

當(dāng)需要考慮屬性信息時，可以對屬性信息重構(gòu)將屬性信息加入。高階相似度和一階相似度與SDNE相似。

同時還需要考慮拼接一致性的問題。通常假設(shè)相同節(jié)點在兩個視圖中的隱層表示比較接近，不同且不相鄰節(jié)點應(yīng)該遠(yuǎn)離。在拼接時可能會有不一致的問題比如尺度不一會導(dǎo)致一個視圖的影響蓋過另一個，或者方向不一導(dǎo)致結(jié)果減弱或者抵消。

3. GCN等深度網(wǎng)絡(luò)類

首先介紹卷積的推廣。卷積是在拉普拉斯算子的特征向量構(gòu)成的空間上的操作。把函數(shù)映射到該空間就是對函數(shù)做傅里葉變換。卷積就是在該空間上的操作，可以保證頻譜不變性。

圖上的拉普拉斯矩陣通常是通過熱傳導(dǎo)方程推導(dǎo)的。對于一維和多維的情況推導(dǎo)如下，其中D表示節(jié)點的度矩陣。

迪利克雷能量用于衡量圖上屬性函數(shù)的震蕩情況，一般由圖上節(jié)點的梯度和來表示。

GCN的過程是首先構(gòu)造圖的拉普拉斯矩陣，計算拉普拉斯特征向量。將特征向量空間當(dāng)作傅里葉空間，直接將屬性映射到該空間即可。但是由于卷積核參數(shù)巨大，通常使用切比雪夫多項式進(jìn)行近似。將cheby核限制在2階就可以得到常用的GCN表達(dá)式。

由于GCN需要用到整個鄰接矩陣，因此學(xué)習(xí)方式是transductive類的。但是因為GCN在每次聚合時只選擇鄰居節(jié)點，所以有工作如graphsage在GCN上做了改進(jìn)可以實現(xiàn)inductive方式的學(xué)習(xí)。具體過程如下，主要的差別在于聚合操作，不再限制為加和而可以使用如means等方式。

GAT相較于graphsage增加了注意力，按照一定的權(quán)重聚合鄰居的表示。GIN分析了GCN和GraphSage在聚合后無法保持單射的問題，使用MLP作為更新函數(shù)并加入了自身信息減少擾動。

4. 模型訓(xùn)練方式與評價

① 折疊式訓(xùn)練

將近鄰的節(jié)點分層聚合，縮小網(wǎng)絡(luò)規(guī)模，訓(xùn)練好后逐步打開，使用社區(qū)值初始化繼續(xù)后續(xù)的訓(xùn)練直至收斂。這種方式速度快、易訓(xùn)練，有時單機(jī)就可以完成小規(guī)模的圖訓(xùn)練。

② AUC與假設(shè)檢驗

驗證模型是否有效需要進(jìn)行假設(shè)檢驗。AUC是一種U的統(tǒng)計量，是非參數(shù)順序統(tǒng)計量，具有漸進(jìn)正態(tài)性。樣本量越大，其正態(tài)性越好。不同的樣本AUC是不具備可比性的。

③ IV值

除了對模型的有效性進(jìn)行檢驗還要對模型的輸出進(jìn)行評估。模型輸出的embedding或者得分對于下游任務(wù)是否有用？有多少用？也需要評估。IV值本質(zhì)上是對稱的KL散度，衡量分布差異的程度。

03Transductive類常用算法

Transductive是直推式算法，需要利用整個圖的信息，只能預(yù)測圖上已有的節(jié)點，不能預(yù)測未知節(jié)點信息。原始GCN就采用這種方式，需要對全圖的鄰接矩陣做歸一化后進(jìn)行卷積。transductive必須進(jìn)行全圖操作，由于僅同構(gòu)圖的邊數(shù)量能達(dá)到幾百億的規(guī)模，節(jié)點的度更是服從指數(shù)型分布，于是經(jīng)常會遇到內(nèi)存不足的問題。

1. GraphX框架及優(yōu)化經(jīng)驗

① 傳播框架

目前的傳播框架有兩種：

Pregel：頂點接收上個超步傳遞來的信息，整合并修改頂點，設(shè)置頂點活躍狀態(tài)，活躍節(jié)點傳遞消息給鄰居，結(jié)束該階段超步。

GAS：GAS是GraphLab提出的，將圖消息傳播抽象為Gather, Apply, Scatter三個階段，Gather/Scatter只針對單條邊，Gather的返回值由graphlab求和計算。

GraphX主要使用Pregel，也借鑒了GAS的部分思想。GraphX需要手動判斷節(jié)點活躍與否，并不會自動設(shè)置節(jié)點的活躍狀態(tài)。動態(tài)傳播需要在傳播消息時判斷節(jié)點活躍狀態(tài)，手動實現(xiàn)不活躍節(jié)點不傳播。

② 相關(guān)優(yōu)化

精度要求不高，可以將double換為float；若屬性向量特別多，densevector換為SparseVector；每一輪迭代后需要及時unpersist。

2. 為GraphX增加參數(shù)學(xué)習(xí)能力

GraphX是沒有參數(shù)學(xué)習(xí)能力的，我們需要構(gòu)建一些參數(shù)并在節(jié)點之間同步。此時便可以利用blockmanager或者pytorch存儲參數(shù)。根據(jù)具體業(yè)務(wù)設(shè)計loss求解參數(shù)。

3. 各類算法與相關(guān)應(yīng)用

① 模式匹配

主要查找特定用戶、反作弊、查找異常點等。通常使用的是graphframe，其中有一個motiffinding操作可以匹配一些模式。

② 標(biāo)簽傳播

標(biāo)簽傳播是比較常用的操作。Louvain是使用社區(qū)模塊進(jìn)行社區(qū)化衡量的標(biāo)準(zhǔn)，也適用于標(biāo)簽傳播。標(biāo)簽衡量標(biāo)準(zhǔn)通常是依據(jù)業(yè)務(wù)自主設(shè)計的，傳播方案也需要根據(jù)業(yè)務(wù)、數(shù)據(jù)類型做設(shè)計。一般采用衰減形式的傳播或者歸一化的傳播并配合閾值。

③ 屬性傳播

屬性傳播主要用于補(bǔ)充缺失屬性為后續(xù)模型或業(yè)務(wù)提供支持。常常采用的假設(shè)是同配假設(shè)即高緯度與高緯度節(jié)點相連接，相似節(jié)點相連接。這里的傳播沒有學(xué)習(xí)過程，不需要調(diào)節(jié)參數(shù)，因此數(shù)據(jù)集選擇也不需要回溯。

④ 中心度計算

中心度計算是比較重要且常用的任務(wù)如pr, ppr, kcore, triangle, degree等，可以為后續(xù)任務(wù)提供信息。這里有一個基礎(chǔ)理論即Perron-Frobenius定理，表示非負(fù)不可約矩陣一般等于強(qiáng)連通圖，即譜半徑為最大特征值，對應(yīng)唯一的嚴(yán)格為正的特征向量。

在計算節(jié)點中心度之前會假設(shè)節(jié)點已經(jīng)有一個中心度，可以通過鄰居節(jié)點中心度的和來更新當(dāng)前節(jié)點的中心度。鑒于以上定理，特征向量中心度就是直接求鄰接矩陣最大特征值對應(yīng)的特征向量，每一維對應(yīng)各個節(jié)點的中心度。同時，也可以對特征向量中心度做歸一化。

Pagerank系列的算法都是從特征向量中心度的基礎(chǔ)上發(fā)展而來的，比如PageRank就是在歸一化的特征向量中心度的基礎(chǔ)上加了一個跳出機(jī)制，避免出度為0的節(jié)點的影響。

04總結(jié)展望