圖嵌入模型綜述圖分析用于深入挖掘圖數據的內在特征，然而圖作為非歐幾里德數據，傳統的數據分析方法普遍存在較高的計算量和空間開銷。圖嵌入是一種解決圖分析問題的有效方法，其將原始圖數據轉換到低維空間并保留關鍵信息，從而提升節點分類、鏈接預測、節點聚類等下游任務的性能。圖是復雜系統中常用的信息載體，可以表示現實中許多復雜關系，如社交網絡、犯罪網絡、交通網絡等。圖結構作為一種非歐幾里德數據，很難直接應用卷積神經網絡和循環 神經網絡。為了構造用于圖數據挖掘的特征表示，圖嵌入將節點映射到低維空間，生成保留原始圖中某些重要信息的低維向量。目前，圖嵌入不僅在節點分類、鏈接預測、節點聚類、可視化等復雜網絡上的機器學習任務中獲得成功，還廣泛用于社交影響力建模、內容推薦等現實任務。

圖嵌入定義

圖：表示為 ，其中 表示節點集， 表示邊集。

靜態圖：給定圖，如果節點和邊的不隨時間變化，圖 為靜態圖。

動態圖：按時間分成一系列演化圖， 表示演化圖的數量，每個演化圖表示時刻的狀態。

一階相似度：節點之間的成對鄰近度。

二階相似度：節點鄰域結構的相似度。

圖嵌入 ：將每個節點映射成低維向量表示，保留了原始圖中某些關鍵信息。

圖嵌入分類

基于矩陣分解的圖嵌入

基于矩陣分解的圖嵌入通過分解節點關系矩陣獲得低維嵌入。不同的關系矩陣采用的分解方法不同 ，例如鄰接矩陣通常使用奇異值分解（SVD）的方法生成節點嵌入，而屬性矩陣通常使用特征值分解的方法。

基于矩陣分解的靜態圖嵌入

基于矩陣分解的靜態圖嵌入模型對節點關聯信息矩陣和屬性信息矩陣進行特征分解，然后將分解得到的屬性嵌入和結構嵌入進行融合，生成節點的低維嵌入表示。

局部線性映射LLE將每個節點表示為相鄰節點的線性組合，構造鄰域保持映射。具體實現分為三步：

以某種度量方式（如歐氏距離）選擇 k個鄰近節點；

由 k個近鄰線性加權重構節點，并最小化節點重建誤差獲得最優權重；

最小化最優權重構建的目標函數生成 Y

基于矩陣分解的動態圖嵌入

基于矩陣分解的動態圖方法利用特征分解構造圖的高階相似度矩陣，然后利用矩陣攝動理論更新圖的動態信息。DANE采用分布式框架：離線部分，采用最大化相關性的方法捕捉圖結構和節點屬性的依賴關系；在線部分，使用矩陣攝動理論更新嵌入的特征值和特征向量。

基于隨機游走的圖嵌入

受word2vec的啟發，基于隨機游走的圖嵌入方法將節點轉化為詞，將隨機游走序列作為句子，利用Skip-Gram 生成節點的嵌入向量。隨機游走法可以保留圖的結構特性，并且在無法完整觀察的大型圖上仍有不錯的表現。

基于隨機游走的靜態圖嵌入

基于隨機游走的靜態圖嵌入模型通過隨機游走獲得訓練語料庫，然后將語料庫集成到 Skip-Gram 獲得節點的低維嵌入表示。Deepwalk使用隨機游走對節點進行采樣，生成節點序列，再通過 Skip-Gram 最大化節點序列中窗口范圍內節點之間的共現概率。

Deepwalk 不僅在數據量較少時有較好的表現，還可以擴展到大型圖的表示學習。由于優化過程中未使用明確的目標函數，使得模型保持網絡結構的能力受到限制。

node2vec在 Deepwalk的基礎上，引入有偏的隨機游走，增加鄰域搜索的靈活性，生成質量更高、信息更多的嵌入表示。通過設置 p 和 q 兩個參數，平衡廣度優先搜索和深度優先搜索策略，使生成的嵌入能夠保持社區結構等價性或鄰域結構等價性。

基于隨機游走的動態圖嵌入

CTDNE利用時間隨機游走從連續型動態圖中學習包含時間信息的嵌入表示。，CTDNE 采用的時間隨機游走與靜態圖方法相似，但約束每個隨機游走符合邊出現的時間順序，即邊的遍歷必須按照時間遞增的順序，由于每條邊包含多個時間戳，使得同一節點可能在游走中出現多次。

基于自編碼器的圖嵌入

自編碼器使隱藏層學習到的表示維度小于輸入數據，即對原始數據進行降維。基于自編碼器的圖嵌入方法使用自編碼器對圖的非線性結構建模，生成圖的低維嵌入表示。 基于自編碼器的靜態圖嵌入

基于自編碼器的圖嵌入方法起源于使用稀疏自編碼器的 GraphEncoder。其基本思想是將歸一化的圖相似度矩陣作為節點原始特征輸入到稀疏自編碼器中進行分層預訓練，使生成的低維非線性嵌入可以近似地重建輸入矩陣并保留稀疏特性。

基于自編碼器的動態圖嵌入

基于自編碼器的動態圖方法將每個時刻訓練的參數作為下一時刻自編碼器的初始值，從而在一定程度上保持生成嵌入的穩定性，提高模型的計算效率。

基于圖神經網絡的圖嵌入

圖神經網絡（GNN）是專門處理圖數據的深度模型，其利用節點間的消息傳遞來捕捉某種依賴關系，使生成的嵌入可以保留任意深度的鄰域信息。

基于圖神經網絡的靜態圖嵌入

基于 GNN的靜態圖模型聚合節點鄰域的嵌入并不斷迭代更新，利用當前的嵌入及上一次迭代的嵌入生成新的嵌入表示。

GraphSAGE 不是為每個節點訓練單獨的嵌入，而是通過采樣和聚合節點的局部鄰域特征訓練聚合器函數，同時學習每個節點鄰域的拓撲結構及特征分布，生成嵌入表示。

圖注意力網絡（graph attention network，GAT）在 GCN 的基礎上引入注意力機制，對鄰近節點特征加權求和，分配不同的權值。

基于圖神經網絡的動態圖嵌入

基于 GNN的動態圖模型通常在靜態圖模型的基礎上，引入一種循環機制更新網絡參數，實現動態過程的建模，使生成低維嵌入可以有效保留圖的動態演化信息。

DyRep將動態圖嵌入假設為圖的動態（拓撲演化）和圖上的動態交織演化（節點間的活動）的中介過程。

DySAT通過鄰域結構和時間兩個維度的聯合自注意力來計算節點嵌入，結構注意力塊通過自注意聚集和堆疊從每個節點局部鄰域中提取特征。

基于其他方法的圖嵌入

LINE同樣定義了一階相似度和二階相似度函數，并對其進行優化。一階相似度用于保持鄰接矩陣和嵌入表示的點積接近，二階相似度用于保持上下文節點的相似性。LINE 分別優化一階和二階相似度的目標函數，然后將生成的嵌入向量進行拼接。

數據集與應用

靜態圖嵌入數據集

20-Newsgroup：由大約 20 000 個新聞組文檔構成的數據集。這些文檔根據主題劃分成 20 個組，每個文檔表示為每個詞的 TF-IDF 分數向量，構建余弦相似圖。為了證明聚類算法的穩健性，分別從 3、6和 9 個不同的新聞組構建了 3 個圖。

Flickr：由照片分享網站 Flickr 上的用戶組成的網絡。網絡中的邊指示用戶之間的聯系關系。標簽指示用戶的興趣組（例如黑白色攝影）。

DBLP：引文網絡數據集，每個頂點表示一個作者，從一個作者到另一個作者的參考文獻數量由這兩個作者之間的邊權重來記錄。標簽上標明了研究人員發表研究成果的 4個領域。

YouTube：YouTube 視頻分享網站用戶之間的社交網絡。標簽代表了喜歡視頻類型（例如動漫視頻）的觀眾群體。

Wikipedia：網頁共現網絡，節點表示網頁，邊表示網頁之間的超鏈接。Wikipedia數據集的 TF-IDF矩陣是描述節點特征的文本信息，節點標簽是網頁的類別。

Cora、CiteSeer、Pubmed：標準的引文網絡基準數據集，節點表示論文，邊表示一篇論文對另一篇論文的引用。節點特征是論文的詞袋表示，節點標簽是論文的學術主題。

Yelp：本地商業評論和社交網站，用戶可以提交對商家的評論，并與其他人交流。由于缺乏標簽信息，該數據集常用于鏈接預測。

動態圖嵌入數據集

Epinions：產品評論網站數據集，基于評論的詞袋模型生成節點屬性，以用戶評論的主要類別作為類別標簽。該數據集有 16個時間戳。

Hep-th：高能物理理論會議研究人員的合作網絡，原始數據集包含 1993 年 1 月至 2003 年 4 月期間高能物理理論會議的論文摘要。

AS（autonomous systems）：由邊界網關協議日志構建的用戶通信網絡。該數據集包含從 1997年 11月 8 日到 2000 年 1 月 2 日的 733 條通信記錄，通常按照年份將這些記錄劃分為不同快照。

Enron：Enron 公司員工之間的電子郵件通信網絡。該數據集包含 1999 年 1 月至 2002 年 7 月期間公司員工之間的電子郵件。

UCI：加州大學在線學生社區用戶之間的通信網絡。節點表示用戶，用戶之間的消息通信表示邊緣。每條邊攜帶的時間指示用戶何時通信。

圖嵌入任務

網絡重構

網絡重構任務是利用學習到節點低維向量表示重新構建原始圖的拓撲結構，評估生成的嵌入保持圖結構信息的能力。好的網絡嵌入方法能夠捕捉到具有網絡結構信息的嵌入表示，從而能夠很好地重構網絡。

節點分類

節點分類任務是利用圖的拓撲結構和節點特征確定每個節點所屬類別。節點分類任務可以利用已有標簽節點和連接關系來推斷丟失的標簽。 鏈接預測

鏈接預測任務用于預測兩個節點之間是否存在邊或者預測圖中未觀察到的鏈接，評估生成嵌入在保持拓撲結構方面的性能。

聚類

聚類任務采用無監督的方式將圖劃分為若干個社區，使屬于同一社區的節點具有更多相似特性。將生成的嵌入表示進行聚類，使具有相似特性的節點盡可能在同一社區。在。

異常檢測

異常檢測任務用于識別圖中的“非正常”結構，通常包括異常節點檢測、異常邊緣檢測和異常變化檢測。圖數據的異常檢測主要是找出與正常數據集差異較大的離群點（異常點）。

可視化

可視化任務是對嵌入進行降維和可視化，從而直觀地觀察原始圖中某些特征。對于可視化任務，好的嵌入表示在二維圖像中相同或相近的節點彼此接近，不同的節點彼此分離。

原文標題：圖嵌入模型綜述：方法、數據集和應用

文章出處：【微信公眾號：Imagination Tech】歡迎添加關注！文章轉載請注明出處。