淺談圖嵌入演算法

Part 01

●  什麼是圖片嵌入 ##● 

##圖嵌入是將圖結構資料映射為低維稠密向量的過程，同時使得原圖中拓撲結構相似或屬性接近的節點在向量空間上的位置也接近，能夠很好地解決圖結構資料難以有效率地輸入機器學習演算法的問題。

對於圖的表示和存儲，最容易想到的是使用鄰接矩陣的方式。將圖中的每個節點編號，建構出一個

#########的矩陣，其中##############表示圖中節點的數量。圖中任兩個節點是否有邊相連決定了鄰接矩陣中對應位置的值，這種表示法非常容易理解且直觀，但非常低效。因為現實場景中的圖可能包含成千上萬甚至更多的節點，而大多數節點之間是沒有邊連接的，這會導致所得的鄰接矩陣十分稀疏。使用鄰接矩陣表示和儲存圖需要較高的計算成本和空間成本，而圖嵌入演算法能夠有效率地解決圖分析問題。 #####################Part 02#####################●##### #  ###############基本概念############# ###############● ###### ##############概念1 圖：##########

圖表示為，其中##表示節點，表示邊。 與節點類型映射函數#與邊類型對應函數相關聯。 表示節點類型的集合，表示邊類型的集合。

概念2 同構圖：

圖，其中。也就是說，所有節點都屬於一種類型，所有邊都屬於一種類型，例如社交網路中的使用者關注關係圖，只有使用者這一種節點類型和關注關係這一邊類型。

概念3 異質圖：

圖#，其中或。也就是說，節點類型或邊類型多於一種，例如學術網路中的圖結構，存在論文、作者、會議等多種節點類型，邊的關係包括作者與論文之間的創作關係、論文與會議之間的發表關係、論文與論文之間的引用關係等。

概念4 一階相似度：

如果連接兩個節點的邊的權重較大，則它們之間的一階相似度越大。節點與節點#之間的一階相似度表示為 #，有，其中#是節點 ##與節點

之間連邊

的權重。

概念5 二階相似度：如果兩個節點鄰近的網絡結構越相似，則它們之間的二階相似度越大。節點與節點#之間的二階相似度是的鄰域

#的鄰域

######之間的相似性。如圖1所示，因為有邊連接節點f和節點g，所以節點f和節點g一階相似。雖然沒有邊連接節點e和節點g，但是它們相同的鄰居節點有四個，所以節點e和節點g二階相似。 ##################

图1 二阶相似度示意图

概念6 图嵌入：

给定输入图，以及预定义的嵌入维数，图嵌入是要在尽可能保留图属性的前提下，将图转换到维空间。依赖一阶相似度或高阶相似度量化图属性的保留程度，使用一个维向量或一组维向量来表示一个图，每个向量表示图的一部分的嵌入，例如节点或边。

Part 03

●  图嵌入算法分类 ● 

​在过去几十年，研究人员们提出了许多优秀的算法，在社交网络、通信网络等场景中被证明具有显著的效果。业界通常根据输出粒度的差异将这些图嵌入算法分为以下三类：

（1）节点嵌入

节点嵌入是最常见的类型，在低维空间中用向量对图中的每一个节点进行表示，“相似”节点的嵌入向量表示也是相似的。当需要对图中的节点进行分析，进而执行节点分类或节点聚类等任务时，通常会选择节点嵌入。

（2）边嵌入

在低维空间中用向量对图中的每一条边进行表示。边由一对节点组成，通常表示节点对关系。当需要对图中的边进行分析，执行知识图谱关系预测或链路预测等任务时，适合选择边嵌入。

（3）图嵌入

在低维空间中用向量对整个图进行表示，通常是分子或蛋白质这样的小图。将图表示为一个向量便于计算不同图之间的相似性，从而解决图分类问题。

不同的任务需求决定了选用的图嵌入算法，由于篇幅原因，这里节选出节点嵌入中的DeepWalk算法和Node2Vec算法来进行相对详细的学习。

Part 04

●  经典图嵌入算法 ● 

1.DeepWalk算法​

受自然语言处理领域中word2vec思想的启发，Perozzi等为了建立学习图中节点表示向量的模型，将节点与节点的共现关系类比于语料库中词与词的共现关系，提出了DeepWalk算法。通过随机游走的方式采集图中节点的邻居节点序列，相当于节点上下文的语料库，进而可以解决图中节点之间共现关系的提取问题。预先设置好节点序列的长度和起点，随机游走策略将会指导如何在邻居节点中确定下一个游走节点，重复执行该步骤，即可获得满足条件的序列，随机游走示意图如图2所示。

圖2 隨機遊走示意圖

#將word2vec演算法中的單字對應成圖中的節點，單字序列對應成隨機遊走得到的節點序列，那麼對於一個隨機遊走 ，定義其最佳化目標函數如公式所示。

為了更進一步學習節點的潛在特徵表示，DeepWalk演算法引入了映射函數，實作圖中節點到維向量的映射，那麼問題就轉換成要估算下列公式的可能性。

機率的計算同樣需要參考word2vec演算法中的skip-gram模型。

如圖3所示，skip-gram模型包含兩個關鍵的矩陣，一個是中心詞向量矩陣 ，另一個是背景詞向量矩陣，這兩個權重矩陣分別代表著作為不同角色時單字所關聯的詞向量。 skip-gram是一個預測詞上下文的模型，先從語料庫中學習了詞與詞之間的關係，再用這些關係來表達一個特定詞的上下文，即詞的向量表示。也就是說，在同一個序列中，兩個單字同時出現的頻率越高，兩個單字的向量表示越相似。將這個想法應用到圖中，定義其最佳化目標函數如公式所示。

在隨機遊走過程中，不考慮在取樣序列中節點與節點的順序關係，這能夠更好地反映節點的鄰近關係，同時減少了計算成本。

圖3 skip-gram模型示意圖

2.Node2Vec演算法

在DeepWalk演算法的基礎上，研究者Grover A和Leskovec J提出了Node2Vec演算法。 Node2Vec演算法將DeepWalk演算法中透過隨機遊走產生節點序列的過程進行最佳化，定義參數#與參數

#對每次隨機遊走是傾向於廣度優先採樣還是深度優先採樣進行引導，因此適應性很高。假定目前存取節點，則下一個存取節點的機率如公式所示。

表示從節點

到節點

############的轉移機率，###############表示歸一化常數。 #############################################################################圖4 Node2Vec隨機遊走策略示意圖###### ###

Node2Vec的隨機遊走策略是根據兩個參數進行控制的，如圖4所示。假設經過邊到達節點v，下一步準備訪問節點x，設##，是節點和之間的邊權。也就是說，當圖是無權圖時，直接決定了節點的轉移機率。當圖是有權圖時，與邊權重的乘積決定了節點最終的轉移機率。 可以根據下列公式來計算，式中是節點##和節點

之間的最短路徑距離。 當遊走取樣從節點走到節點

#並且需要選擇下一跳節點時，會有以下三種情況。 (1) 當#時，傳回節點

######。 ##########

(2) 當時，選擇節點##與節點的共同鄰接節點，例如節點。

(3) 當#時，選擇與節點 #無關的節點的鄰接節點，例如節點##或 。

也就是說，參數#控制著返回上一跳節點的機率，參數更多控制的是探索網路的局部結構資訊還是全域結構訊息，DeepWalk模型其實是##和的值設定為1時的Node2Vec模型。

Part 05

●  總結 ● 

隨著資訊科技的快速發展，網路環境變得日益複雜，網路攻擊頻傳，其中APT攻擊呈現高發態勢，是企業需要關注的安全問題。事實上，APT攻擊發生的基本環境──網絡，本身就是一個由電腦等元素構成的網絡結構，這也不難聯想到使用圖數據結構來表達這些元素間的關係，再將攻擊檢測問題轉化為圖中的節點、邊或子圖分類任務。圖嵌入是一個豐富且極具研究空間的問題，如何提高模型訓練效率、創新模型構造方法、將圖嵌入的想法應用於更多的生產實踐，企業需要透過更進一步的研究，才能找到更好的答案。

參考文獻

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

[2]Cai H, Zheng V W, Chang K C C . A comprehensive survey of graph embedding: Problems, techniques, and applications[J]。 ##[3]Goyal P, Ferrara E. Graph embedding techniques, applications, and performance: A survey[J]. Knowledge-Based Systems, 2018, 151: 78-94.

以上是淺談圖嵌入演算法的詳細內容。更多資訊請關注PHP中文網其他相關文章！