淺談圖嵌入算法如何高效解決輸入機(jī)器學(xué)習(xí)算法的問(wèn)題

Labs 導(dǎo)讀

圖作為一種重要的數(shù)據(jù)表示形式，普遍存在于多樣化的實(shí)際場(chǎng)景中，如社交網(wǎng)絡(luò)中的社交圖、電子商務(wù)網(wǎng)站中的用戶興趣圖、科研領(lǐng)域中的論文引文圖等。有效的圖分析能夠幫助人們深入了解數(shù)據(jù)背后的內(nèi)容，從而解決節(jié)點(diǎn)分類、節(jié)點(diǎn)聚類、鏈路預(yù)測(cè)等問(wèn)題。然而圖上的數(shù)學(xué)和統(tǒng)計(jì)操作是有限的，將機(jī)器學(xué)習(xí)方法直接應(yīng)用到圖上是很有挑戰(zhàn)性的。在這種情況下，圖嵌入似乎是一個(gè)合理的解決方案。

作者：何穎

單位：中國(guó)移動(dòng)智慧家庭運(yùn)營(yíng)中心安全產(chǎn)品部

什么是圖嵌入●

圖嵌入是將圖結(jié)構(gòu)數(shù)據(jù)映射為低維稠密向量的過(guò)程，同時(shí)使得原圖中拓?fù)浣Y(jié)構(gòu)相似或?qū)傩越咏墓?jié)點(diǎn)在向量空間上的位置也接近，能夠很好地解決圖結(jié)構(gòu)數(shù)據(jù)難以高效輸入機(jī)器學(xué)習(xí)算法的問(wèn)題。

對(duì)于圖的表示和存儲(chǔ)，最容易想到的是使用鄰接矩陣的方式。對(duì)圖中的每個(gè)節(jié)點(diǎn)進(jìn)行編號(hào)，構(gòu)造出一個(gè)的矩陣，其中表示圖中節(jié)點(diǎn)的數(shù)量。圖中任意兩個(gè)節(jié)點(diǎn)是否有邊相連決定了鄰接矩陣中對(duì)應(yīng)位置的值，這種表示方法非常容易理解且直觀，但是非常低效。因?yàn)楝F(xiàn)實(shí)場(chǎng)景中的圖可能會(huì)包含成千上萬(wàn)甚至更多的節(jié)點(diǎn)，而大多數(shù)節(jié)點(diǎn)之間是沒(méi)有邊連接的，這會(huì)導(dǎo)致得到的鄰接矩陣十分稀疏。使用鄰接矩陣表示和存儲(chǔ)圖需要較高的計(jì)算成本和空間成本，而圖嵌入算法能夠高效解決圖分析問(wèn)題。

Part 02 ●基本概念● 概念1 圖： 圖表示為，其中表示節(jié)點(diǎn)，表示邊。與節(jié)點(diǎn)類型映射函數(shù)和邊類型映射函數(shù)相關(guān)聯(lián)。表示節(jié)點(diǎn)類型的集合，表示邊類型的集合。 ? 概念2 同構(gòu)圖： 圖，其中。也就是說(shuō)，所有節(jié)點(diǎn)都屬于一種類型，所有邊都屬于一種類型，比如社交網(wǎng)絡(luò)中的用戶關(guān)注關(guān)系圖，只有用戶這一種節(jié)點(diǎn)類型和關(guān)注關(guān)系這一種邊類型。 ? 概念3 異構(gòu)圖： 圖，其中或。也就是說(shuō)，節(jié)點(diǎn)類型或邊類型多于一種，比如學(xué)術(shù)網(wǎng)絡(luò)中的圖結(jié)構(gòu)，存在論文、作者、會(huì)議等多種節(jié)點(diǎn)類型，邊的關(guān)系包括作者與論文之間的創(chuàng)作關(guān)系、論文與會(huì)議之間的發(fā)表關(guān)系、論文與論文之間的引用關(guān)系等。 ? 概念4 一階相似度： 如果連接兩個(gè)節(jié)點(diǎn)的邊的權(quán)重較大，則它們之間的一階相似度越大。節(jié)點(diǎn)和節(jié)點(diǎn)之間的一階相似度表示為，有，其中是節(jié)點(diǎn)和節(jié)點(diǎn)之間連邊的權(quán)重。 ? 概念5 二階相似度： 如果兩個(gè)節(jié)點(diǎn)鄰近的網(wǎng)絡(luò)結(jié)構(gòu)越相似，則它們之間的二階相似度越大。節(jié)點(diǎn)和節(jié)點(diǎn)之間的二階相似度是的鄰域和的鄰域之間的相似性。如圖1所示，因?yàn)橛羞呥B接節(jié)點(diǎn)f和節(jié)點(diǎn)g，所以節(jié)點(diǎn)f和節(jié)點(diǎn)g一階相似。雖然沒(méi)有邊連接節(jié)點(diǎn)e和節(jié)點(diǎn)g，但是它們相同的鄰居節(jié)點(diǎn)有四個(gè)，所以節(jié)點(diǎn)e和節(jié)點(diǎn)g二階相似。 ? ?

圖1 二階相似度示意圖 概念6 圖嵌入： 給定輸入圖，以及預(yù)定義的嵌入維數(shù)，圖嵌入是要在盡可能保留圖屬性的前提下，將圖轉(zhuǎn)換到維空間。依賴一階相似度或高階相似度量化圖屬性的保留程度，使用一個(gè)維向量或一組維向量來(lái)表示一個(gè)圖，每個(gè)向量表示圖的一部分的嵌入，例如節(jié)點(diǎn)或邊。

圖嵌入算法分類●

在過(guò)去幾十年，研究人員們提出了許多優(yōu)秀的算法，在社交網(wǎng)絡(luò)、通信網(wǎng)絡(luò)等場(chǎng)景中被證明具有顯著的效果。業(yè)界通常根據(jù)輸出粒度的差異將這些圖嵌入算法分為以下三類：

（1）節(jié)點(diǎn)嵌入

節(jié)點(diǎn)嵌入是最常見(jiàn)的類型，在低維空間中用向量對(duì)圖中的每一個(gè)節(jié)點(diǎn)進(jìn)行表示，“相似”節(jié)點(diǎn)的嵌入向量表示也是相似的。當(dāng)需要對(duì)圖中的節(jié)點(diǎn)進(jìn)行分析，進(jìn)而執(zhí)行節(jié)點(diǎn)分類或節(jié)點(diǎn)聚類等任務(wù)時(shí)，通常會(huì)選擇節(jié)點(diǎn)嵌入。

（2）邊嵌入

在低維空間中用向量對(duì)圖中的每一條邊進(jìn)行表示。邊由一對(duì)節(jié)點(diǎn)組成，通常表示節(jié)點(diǎn)對(duì)關(guān)系。當(dāng)需要對(duì)圖中的邊進(jìn)行分析，執(zhí)行知識(shí)圖譜關(guān)系預(yù)測(cè)或鏈路預(yù)測(cè)等任務(wù)時(shí)，適合選擇邊嵌入。

（3）圖嵌入

在低維空間中用向量對(duì)整個(gè)圖進(jìn)行表示，通常是分子或蛋白質(zhì)這樣的小圖。將圖表示為一個(gè)向量便于計(jì)算不同圖之間的相似性，從而解決圖分類問(wèn)題。

不同的任務(wù)需求決定了選用的圖嵌入算法，由于篇幅原因，這里節(jié)選出節(jié)點(diǎn)嵌入中的DeepWalk算法和Node2Vec算法來(lái)進(jìn)行相對(duì)詳細(xì)的學(xué)習(xí)。

經(jīng)典圖嵌入算法

● 1.DeepWalk算法 受自然語(yǔ)言處理領(lǐng)域中word2vec思想的啟發(fā)，Perozzi等為了建立學(xué)習(xí)圖中節(jié)點(diǎn)表示向量的模型，將節(jié)點(diǎn)與節(jié)點(diǎn)的共現(xiàn)關(guān)系類比于語(yǔ)料庫(kù)中詞與詞的共現(xiàn)關(guān)系，提出了DeepWalk算法。通過(guò)隨機(jī)游走的方式采集圖中節(jié)點(diǎn)的鄰居節(jié)點(diǎn)序列，相當(dāng)于節(jié)點(diǎn)上下文的語(yǔ)料庫(kù)，進(jìn)而可以解決圖中節(jié)點(diǎn)之間共現(xiàn)關(guān)系的提取問(wèn)題。預(yù)先設(shè)置好節(jié)點(diǎn)序列的長(zhǎng)度和起點(diǎn)，隨機(jī)游走策略將會(huì)指導(dǎo)如何在鄰居節(jié)點(diǎn)中確定下一個(gè)游走節(jié)點(diǎn)，重復(fù)執(zhí)行該步驟，即可獲得滿足條件的序列，隨機(jī)游走示意圖如圖2所示。

圖2 隨機(jī)游走示意圖 將word2vec算法中的單詞對(duì)應(yīng)成圖中的節(jié)點(diǎn)，單詞序列對(duì)應(yīng)成隨機(jī)游走得到的節(jié)點(diǎn)序列，那么對(duì)于一個(gè)隨機(jī)游走，定義其優(yōu)化目標(biāo)函數(shù)如公式所示。 ? ? 為了更進(jìn)一步學(xué)習(xí)節(jié)點(diǎn)的潛在特征表示，DeepWalk算法引入了映射函數(shù)，實(shí)現(xiàn)圖中節(jié)點(diǎn)到維向量的映射，那么問(wèn)題就轉(zhuǎn)換成要估算下列公式的可能性。 ? ? 概率的計(jì)算同樣需要參考word2vec算法中的skip-gram模型。 ? 如圖3所示，skip-gram模型包含兩個(gè)關(guān)鍵的矩陣，一個(gè)是中心詞向量矩陣，另一個(gè)是背景詞向量矩陣，這兩個(gè)權(quán)重矩陣分別代表著作為不同角色時(shí)單詞所關(guān)聯(lián)的詞向量。skip-gram是一個(gè)預(yù)測(cè)詞上下文的模型，先從語(yǔ)料庫(kù)中學(xué)習(xí)了詞與詞之間的關(guān)系，再用這些關(guān)系來(lái)表達(dá)一個(gè)特定詞的上下文，即詞的向量表示。也就是說(shuō)，在同一個(gè)序列中，兩個(gè)單詞同時(shí)出現(xiàn)的頻率越高，兩個(gè)單詞的向量表示越相似。將這個(gè)思想應(yīng)用到圖中，定義其優(yōu)化目標(biāo)函數(shù)如公式所示。 ? ? 在隨機(jī)游走過(guò)程中，不考慮采樣序列中節(jié)點(diǎn)與節(jié)點(diǎn)的順序關(guān)系，這能夠更好地反映節(jié)點(diǎn)的鄰近關(guān)系，同時(shí)減少了計(jì)算成本。 ?

圖3skip-gram模型示意圖 2.Node2Vec算法 在DeepWalk算法的基礎(chǔ)上，研究者Grover A和Leskovec J提出了Node2Vec算法。Node2Vec算法對(duì)DeepWalk算法中通過(guò)隨機(jī)游走生成節(jié)點(diǎn)序列的過(guò)程進(jìn)行優(yōu)化，定義參數(shù)和參數(shù)對(duì)每次隨機(jī)游走是傾向于廣度優(yōu)先采樣還是深度優(yōu)先采樣進(jìn)行引導(dǎo)，因此適應(yīng)性很高。假定當(dāng)前訪問(wèn)節(jié)點(diǎn)，則下一個(gè)訪問(wèn)節(jié)點(diǎn)的概率如公式所示。 ? ? 式中表示從節(jié)點(diǎn)到節(jié)點(diǎn)的轉(zhuǎn)移概率，表示歸一化常數(shù)。 ? ?

圖4 Node2Vec隨機(jī)游走策略示意圖 Node2Vec的隨機(jī)游走策略是根據(jù)兩個(gè)參數(shù)進(jìn)行控制的，如圖4所示。假設(shè)經(jīng)過(guò)邊到達(dá)節(jié)點(diǎn)v，下一步準(zhǔn)備訪問(wèn)節(jié)點(diǎn)x，設(shè)，是節(jié)點(diǎn)和之間的邊權(quán)。也就是說(shuō)，當(dāng)圖是無(wú)權(quán)圖時(shí)，直接決定了節(jié)點(diǎn)的轉(zhuǎn)移概率。當(dāng)圖是有權(quán)圖時(shí)，與邊權(quán)重的乘積決定了節(jié)點(diǎn)最終的轉(zhuǎn)移概率。可以根據(jù)以下公式來(lái)計(jì)算，式中是節(jié)點(diǎn)和節(jié)點(diǎn)之間的最短路徑距離。 ?

當(dāng)游走采樣從節(jié)點(diǎn)走到節(jié)點(diǎn)并需要選擇下一跳節(jié)點(diǎn)時(shí)，會(huì)有以下三種情況。 ? (1) 當(dāng)時(shí)，返回節(jié)點(diǎn)。 ? (2) 當(dāng)時(shí)，選擇節(jié)點(diǎn)和節(jié)點(diǎn)的共同鄰接節(jié)點(diǎn)，例如節(jié)點(diǎn)。 ? (3) 當(dāng)時(shí)，選擇與節(jié)點(diǎn)無(wú)關(guān)的節(jié)點(diǎn)的鄰接節(jié)點(diǎn)，例如節(jié)點(diǎn)或。 ? 也就是說(shuō)，參數(shù)控制著返回上一跳節(jié)點(diǎn)的概率，參數(shù)更多地控制的是探索網(wǎng)絡(luò)的局部結(jié)構(gòu)信息還是全局結(jié)構(gòu)信息，DeepWalk模型其實(shí)是和的值設(shè)置為1時(shí)的Node2Vec模型。

總結(jié)

隨著信息技術(shù)的快速發(fā)展，網(wǎng)絡(luò)環(huán)境變得日益復(fù)雜，網(wǎng)絡(luò)攻擊頻發(fā)，其中APT攻擊呈高發(fā)態(tài)勢(shì)，是企業(yè)需要關(guān)注的安全問(wèn)題。事實(shí)上，APT攻擊發(fā)生的基本環(huán)境——網(wǎng)絡(luò)，本身就是一個(gè)由計(jì)算機(jī)等元素構(gòu)成的網(wǎng)絡(luò)結(jié)構(gòu)，這也不難聯(lián)想到使用圖數(shù)據(jù)結(jié)構(gòu)來(lái)表達(dá)這些元素間的關(guān)系，再將攻擊檢測(cè)問(wèn)題轉(zhuǎn)化為圖中的節(jié)點(diǎn)、邊或子圖分類任務(wù)。圖嵌入是一個(gè)豐富且極具研究空間的問(wèn)題，如何提高模型訓(xùn)練效率、創(chuàng)新模型構(gòu)造方法、將圖嵌入的思想應(yīng)用于更多的生產(chǎn)實(shí)踐，企業(yè)需要通過(guò)更進(jìn)一步的研究，才能找到更好的答案。

參考文獻(xiàn)

[1]Xu M. Understanding graph embedding methods and their applications[J]. SIAM Review, 2021, 63(4): 825-853.

[2]Cai H, Zheng VW, Chang K C C. A comprehensive survey of graph embedding: Problems, techniques, and applications[J]. IEEE Transactions on Knowledge and Data Engineering, 2018, 30(9): 1616-1637.

[3]Goyal P, Ferrara E. Graph embedding techniques, applications, and performance: A survey[J]. Knowledge-Based Systems, 2018, 151: 78-94.

編輯：黃飛