A Tutorial on Network Embeddings
摘要：
A Tutorial on Network Embeddings
paper： https://arxiv.org/abs/1808.02590
NE 的中心思想就是找到一種對映函式，該函式將網路中的每個節點轉換為低維度的潛在表示
典型例子 DeepWalk：
其學習 Za...
A Tutorial on Network Embeddings
paper： ofollow,noindex" target="_blank">https://arxiv.org/abs/1808.02590
NE 的中心思想就是找到一種對映函式，該函式將網路中的每個節點轉換為低維度的潛在表示
典型例子 DeepWalk：
其學習 Zachary’s Karate network 網路中的拓撲結構資訊並轉換成一個二維的潛在表示（latent representation）
目標
- 適應性
- 隨著網路發展，新的表示不需要重複學習
- 可擴充套件
- 短時間處理較大規模網路
- 社群感知
- 潛在節點間的距離可用於評估網路節點間的相似性度量
- 低維
- 標記資料稀疏時，低維模型能夠更好的推廣，並加速收斂和推理
- 持續
- 需要潛在的表示在連續的空間內模擬社群成員關係，連續的表示使社群有更平滑的邊界，促進分類
此文包含
- 無監督網路嵌入方法在無特徵的同質網路的應用
- 調研特徵網路和部分標記網路中的網路嵌入
- 討論異構網路嵌入方法
網路嵌入發展
傳統意義的Graph Embedding
- 降維
- PCA
- 多維縮放（MDS）
- 將特徵矩陣 M 的每一行投影到k 維向量，保留k 維空間中原始矩陣中不同物件距離
- Isomap 演算法
- （MDS 的擴充套件）通過將每個節點與特定距離內的節點連線構造鄰域圖，以保持非線性流形的整體結構
- 區域性線性嵌入（ LLE ）
這些方法都在小型網路上提供良好效能，但其時間複雜度至少為二次，故無法在大規模網路上執行
深度學習
- DeepWalk
- 通過將節點視為單詞並生成短隨機遊走作為句子來彌補網路嵌入和單詞嵌入的差距。然後，可以將諸如 Skip-gram 之類的神經語言模型應用於這些隨機遊走以獲得網路嵌入。
- 按需生成隨機遊走。skim-gram 針對每個樣本進行了優化
- DeepWalk 是可擴充套件的，生成隨機遊走和優化 Skip-gram 模型的過程都是高效且平凡的並行化
- 引入了深度學習圖形的範例
無向網路的網路嵌入
- LINE
- 為了更好的儲存網路的結構資訊，提出了一階相似度和二階相似度的概念，並在目標函式中結合了兩者
- 使用廣度優先演算法，只有距離給定節點最多兩跳的節點才被視為相鄰節點
- 使用負抽樣 skip-gram
- Node2vec
- 反映網路的結構
- deepwalk 的擴充套件（deepwalk 完全時隨機的），引入偏向的隨機遊走，增加 p，q 兩個引數，p（控制訪問走過的node，即往回走，q 控制沒走過的node ，向外走）
- DeepWalk和node2vec演算法是先在網路中隨機遊走，得到node的序列。兩個node同時出現在一個序列中的頻率越高，兩個node的相似度越高。然後構建一個神經網路，神經網路的輸入是node，輸出是其他node與輸入的node同時出現的概率。同時出現的概率越高，兩個node的相似度越高。為了保持相似度一致，得到目標函式
- Walklets
- 不要遊走，跳過！線上學習多尺度網路嵌入
- 進一步學習節點不同權重的網路嵌入，以不同的粒度捕獲網路的結構資訊。
- GraRep
- 通過將圖形鄰接矩陣提升到不同的冪來利用不同尺度的節點共現資訊，將奇異值分解（SVD）應用於鄰接矩陣的冪以獲得節點的低維表示
- GraphAttention
- 不是預先確定超引數來控制上下文節點分佈，而是自動學習對圖轉換矩陣的冪集數的關注
- 通過設定隱藏層，這些層裡的節點能夠注意其鄰近節點的特徵，我們能夠（隱含地）為鄰近的不同節點指定不同的權重，不需要進行成本高昂的矩陣運算（例如反演），也無需事先知道圖的結構
- SDNE
- https://blog.csdn.net/wangyang163wy/article/details/79698563
- 通過深度自動編碼器保持 2 跳鄰居之間的接近度。它通過最小化它們的表示之間的歐幾里德距離來進一步保持相鄰節點之間的接近度
- 具有多層非線性函式，從而能夠捕獲到高度非線性的網路結構。然後使用一階和二階鄰近關係來保持網路結構。二階鄰近關係被無監督學習用來捕獲全域性的網路結構，一階鄰近關係使用監督學習來保留網路的區域性結構
- DNGR
- 基於深度神經網路的學習網路嵌入的方法
改進
HARP
- network embedding的時候保持網路高階的結構特徵，具體的做法是通過將原網路圖進行合併，合併為多個層次的網路圖
- 通過遞迴地粗粒化方式，將原網路圖的節點和邊通過合併劃分成一系列分層的結構更小的網路圖，然後再利用現有的演算法進行不斷的特徵提取，從而實現最終的network embedding特徵提取
特徵網路嵌入（ Attributed Network Embeddings ）
無監督網路嵌入方法僅利用網路結構資訊來獲得低維度的網路特徵。但是現實世界網路中的節點和邊緣通常與附加特徵相關聯，這些特徵稱為屬性（attribute）。
例如在諸如 Twitter 的社交網路站點中，使用者（節點）釋出的文字內容是可用的。因此期望網路嵌入方法還從節點屬性和邊緣屬性中的豐富內容中學習
挑戰：特徵的稀疏性，如何將它們合併到現有的網路嵌入框架中
方法：
- TADW
- Network repre- sentation learning with rich text information
- 研究節點與文字特徵相關聯情況，首先證明了deepwalk 實質上是將轉移概率矩陣 分解為兩個低維矩陣，它將文字矩陣合併到矩陣分解過程中
聯合建模網路結構和節點特徵
- CENE
- 結合網路結構和節點特徵
- 將文字內容視為特殊型別的節點，並利用節點-節點連結和節點內容連結進行節點嵌入。 優化目標是共同最小化兩種型別鏈路的損失。
節點標籤，引文網路中的出版地和日期等
典型方法是：優化用於生成節點嵌入和用於預測節點標籤的損失
- GENE
- 將組的資訊考慮到Network Embedding學習中，同一組的節點即使直接沒有邊，一般也會存在一些內在關係
- 每個相同的組也會學到一個向量表示，組向量有兩個用處：1）在利用周圍節點預測中心節點時，組向量也會加入預測; 2）組向量也會預測組中的其他節點。最後目標函式是將上述兩項相加而成
- Max margin DeepWalk（MMDW）
- 第一部分是基於矩陣分解的節點嵌入模型
- 第二部分是將學習的表示作為特徵來訓練標記節點上的最大邊緣 SVM 分類器。通過引入偏置梯度，可以聯合更新兩個部分中的引數。
異構網路嵌入
- Chang [13] 提出了異構網路的深度嵌入框架
- 為每種模態（如影象，文字）構建一個特徵表示，然後將不同模態的嵌入對映到同一個嵌入空間
- 優化目標：最大化連結節點嵌入間的相似性、最小化未連結節點的嵌入