文章插圖
圖3：圖表示學習的分類和代表性方法 。2.1 基本定義許多現實世界的系統可以抽象地表示為不同級別的信息圖，這些信息圖側重于組件以及這些組件之間的關聯 。圖表示學習方法旨在解決泛化圖嵌入的問題 。在這一部分中，我們首先定義了與圖表示學習相關的重要概念，包括不同類型的圖，以及不同的圖嵌入算法所依賴的圖鄰近度 。為了便于介紹和分析，首先介紹了符號的形式定義 。
假設\(G=(V,E)\)表示由一組頂點(也稱為節點)\(V=\{v_1,v_2,\cdots,v_{|V|}\}\)和一組鏈接(也稱為邊)\(E=\{e_{i,j}\} \in \mathbb{R}^{V \times V}\)組成的圖，其中\(|V|\)表示頂點數 。圖\(G\)的鄰接矩陣\(W\)保持與每條邊相關聯的非負權重 ， 如果\(v_i\)與\(v_j\)相連，那么\(w_{i,j}>0\)，反之\(w_{i,j}=0\) 。對于無向圖，鄰接矩陣是對稱的，即\(w_{i,j}=w_{j,i},?i,j∈[v]\) 。我們也設計了節點類型映射函數\(φ:V→T\)和鏈接類型映射函數\(ψ:E→R\) 。\(T\)和\(R\)分別是預定義的節點類型和鏈接類型的集合 。
2.1.1 定義1：同構圖和異構圖給定一個信息圖\(G\)，根據它的圖拓撲結構和屬性性質(有或沒有節點屬性) ， 可以將其分為不同類型的圖 。如果節點類型\(|T|>1\)或鏈路類型為\(|R|>1\)，即\(|T|+|R|>2\)，則該圖是異構圖 。否則，它是同構圖(\(|T|=1\)且\(|R|=1\)) 。同構圖只有一種類型的節點和唯一的鏈接類型，而異構圖包含多種類型的、相互連接的對象，例如"藥物-目標-疾病"圖 。同時，多重圖是異構圖的一種特殊類型 。多重圖也稱為多視圖或多維圖 ， 它只有一種類型的節點但有多種類型的邊 。它可以看作是一類特殊類型的異構圖，其中\(|T|=1\)但\(|R|>1\) 。
2.1.2 定義2：屬性圖信息圖中的抽象頂點通常有其固有的性質 。一個屬性圖可以形式化地定義為\(G=(V,E,A)\)，其中\(A\)是一個屬性表示矩陣 。對于每個節點\(v_i∈V\) ， 都有一個對應的特征向量\(a_i∈A\)隸屬于它，其中\(A=\{a_i|v_i∈V\}\)是所有節點的節點屬性特征集 。\(a_i\)是屬于節點\(v_i\)的屬性矩陣的第\(i\)行 。
2.1.3 定義3：元路徑對于異構圖，元路徑\(\mathrm{P}=\mathrm{T}_1 \stackrel{R_1}{\rightarrow} \mathrm{T}_2 \stackrel{R_2}{\rightarrow} \mathrm{T}_3 \rightarrow \ldots \stackrel{R_1}{\rightarrow} \mathrm{T}_{l+1}\)定義在網絡模式\(τ(G)=(T,R)\)上，它由節點類型\(T_1\)和節點類型\(T_{l+1}\)之間的復合關系\(R=R_1?R_2?R_3?···?R_l\)組成，其中\(l\)表示路徑的長度(\(l≥1\)) ， \(?\)表示關系上的復合算子 。元路徑可以有效地處理語義信息 ， 例如，一條路徑 \(\text{藥物}_a \stackrel{\text{靶標}}{\longrightarrow} \text{蛋白質}_b \stackrel{\text{相互作用}}{\longrightarrow} \text{疾病}_c\)在生物醫學圖中注明了一種疾病的治療機制 。
2.1.4 定義4：一階鄰近度一階鄰近度反映了兩個直接相鄰節點之間的局部成對相似度 。如果兩個頂點之間有連接，則這兩個節點相似，否則不相似 。形式上，兩個節點\(V_m\)和\(V_n\)的一階鄰近度用\(S_{m,n}\)來度量 。如果節點對\(v_m,v_n \notin E\) ， 則\(S_{m,n}>0\)；反之\(S_{m,n}=0\) 。
2.1.5 定義5：高階鄰近度高階鄰近度捕獲了節點之間的\(k\)跳(\(k≥2\))鄰域 。而二階鄰近度是高階鄰近度(\(k=2\))的特例，它由中間節點連接的鄰居節點的數目決定 。通過從\(v_m\)到\(v_n\)的\(k\)跳轉移概率來衡量兩個節點\(v_m\)和\(v_n\)的高階鄰近度，即\(S_{m,n}=\hat{E}+\hat{E}^2+\hat{E}^3+\cdots+\hat{E}^k\)，其中\(\hat{E}\)表示第一跳的轉移概率 。高階鄰近度捕捉到了全局鄰近度 。
2.1.6 定義6：語義鄰近通過兩個節點的屬性特征向量\(a_m\)和\(a_n\)的相似度來獲得兩個節點\(v_m\)和\(v_n\)的語義鄰近度 。常用的相似度度量包括余弦相似度、皮爾遜相關系數、杰卡德相似度系數和高斯交互輪廓(GIP)核相似度
2.2 同構圖嵌入圖嵌入的第一類是同構圖嵌入，也稱為網絡嵌入或非屬性圖嵌入 。它是最早發展起來的最簡單的圖表示學習方法 。在學習頂點的低維表示時，同構圖嵌入方法通常旨在保持圖的拓撲 。根據它們的技術細節，我們將這些同構圖嵌入方法分為三大類：基于矩陣分解的方法、基于隨機游動的方法和基于傳統深度學習的方法 。
2.2.1 基于矩陣分解的方法矩陣分解旨在將矩陣分解為低維矩陣，同時保持原矩陣的潛在流形結構和拓撲性質 。有一些開創性的工作(例如IsoMap、局部線性嵌入、拉普拉斯特征映射和圖因式分解)將節點之間的關系表示為圖鄰接矩陣、拉普拉斯矩陣或相似矩陣，然后采用矩陣因式分解來獲得嵌入 。這些方法的不同之處在于它們基于不同的一階矩陣來捕捉圖的結構，并且它們通常獲得節點的淺嵌入 。
