本文是對《Asymmetric Transitivity Preserving Graph Embedding》一文的淺顯翻譯與理解，原文章已上傳至個人資源，如有侵權即刻刪除。

朋友們，我們在github創(chuàng)建了一個圖學習筆記庫，總結了相關文章的論文、代碼和我個人的中文筆記，能夠幫助大家更加便捷地找到對應論文，歡迎star~

Chinese-Reading-Notes-of-Graph-Learning

更多相關文章，請移步：文獻閱讀總結：網絡表示學習/圖學習

文章目錄

• 前言
• Title
• Main Body
• • 1 定義
  • 2 損失函數(shù)
  • 3 優(yōu)化高階接近度
  • 4 近似誤差

前言

該文章認為，與無向圖不同，有向圖中的傳遞性是非對稱的，提出 HOPE(High-Order Proximity Preserved Embedding)算法來學習無向圖中的非對稱傳遞性，該算法對非對稱傳遞性的測量是可觀測的。

HOPE 將嵌入分為兩部分，即源嵌入和目標嵌入。通過近似高階接近度，模擬多個接近度測量標準的通用公式，通過廣義 SVD 保證了算法的可擴展性。并且對四種接近度的測量標準進行公式推導，最終都歸為通用形式。避免了對接近度矩陣 S 的高復雜度 SVD 計算，將其視為中間變量不直接求解，而是使用最大奇異值 K 跳過 S 得到最終嵌入。

---

Title

《Asymmetric Transitivity Preserving Graph Embedding》（保持非對稱傳遞性的圖嵌入）
——KDD 2016: The 22th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining
Author: Mingdong Ou

---

Main Body

針對有向圖中的非對稱傳遞性，將向量分為 source vector 和 target vector 兩部分。節(jié)點 vi 與 vj 之間的路徑越多且越短，vi 的源向量和 vj 的目標向量就越相似。從理論上講，無向圖和有向圖都可以被表示為有向圖。

1 定義

G=(V,E)，V 是頂點集，E 是邊集，A 是鄰接矩陣，S 是高階接近度矩陣， U=[U^s,Ut] 是嵌入矩陣，分為源嵌入和目標嵌入。

2 損失函數(shù)

目標是通過近似高階接近度來保持非對稱傳遞性，損失函數(shù)為：

對 S，有多種高階接近度的度量衡，其通用形式如下：

對四種度量衡分別推導：
（1）Katz Index：是兩節(jié)點間所有路徑的加權和，權重與路徑長度呈指數(shù)關系，則有：

其中 β 是衰變參數(shù)，要比鄰接矩陣的譜半徑小。A^l 即加和的每項，每次多乘一個鄰接矩陣 A。

（2）RPR(Rooted PageRank)：表示 vi 穩(wěn)定狀態(tài)下隨機游走連接 vj 的概率，設在一步隨機游走中向其他相鄰節(jié)點延伸的概率為 α，返回上一出發(fā)點的概率為(1-α),則有：

其中，P 是滿足 ∑(i=1,…,N)P_i*j=1 的概率轉移矩陣，即矩陣各元素非負，且各行元素之和為1，各元素用概率表示，在一定條件下是互相轉移的。

（3）CN(Common Neighbors)：S_ij 即同時連接 vi 和 vj 兩節(jié)點的的節(jié)點數(shù)量，對有向圖而言，S_ij 即同時作為 vi 邊目標和 vj 邊源的節(jié)點數(shù)量，則有：

（4）AA(Adamic-Adar)：是 CN 的變體，其為每個鄰居分配一個權重，這意味著一個節(jié)點連接的節(jié)點越多，該節(jié)點對某一節(jié)點的接近度就越小，則有：

上述四個度量衡可以被分為兩種類型：全局接近度的有 Katz index 和 rooted PageRank，都推導為遞歸形式；局部接近度的有 Common Neighbors 和 Adamic-Adar。Mg 與全局非對稱傳遞性關系密切，其有形式為 I-α·B，其中 B 為轉移矩陣，α 為參數(shù)，α 越大，越容易在圖中觀察到傳遞性；α 為0時，觀察到的關系就只能在子圖中傳遞，子圖的范圍受到 Ml 的限制。

3 優(yōu)化高階接近度

損失函數(shù)目的在于找到接近度矩陣 S 中最優(yōu)的 K 階接近度，對高階接近度矩陣 S 執(zhí)行 SVD 奇異值分解，使用其中最大的 K 值及其對應的向量來構建最優(yōu)嵌入向量，則有：

{σ1,σ2,…,σN} 是降序排列的奇異值，可以得到最優(yōu)嵌入向量如下：

然而，對 S 進行奇異值分解計算耗費過大，S 是計算的瓶頸，且其只是中間產物，因此提出新的算法避免對 S 的計算，直接得到嵌入向量。將原始 SVD 問題轉化為廣義 SVD 問題，以便使用通用公式進行接近度測量，則有：

有算法描述如下：

用到了最大奇異值 K，代替對 S 的 SVD 分解，通過 A 計算出 M，對 M 進行 JDGSVD，同樣可以得到用來計算最終向量的奇異值。

4 近似誤差

給出了算法的誤差范圍如下：

可以得到，S 階數(shù)越低，誤差就越小。

總結

以上是生活随笔為你收集整理的文献阅读（6）KDD2016-Asymmetric Transitivity Preserving Graph Embedding的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。