圖學習表示法

Graph Representation

圖(graph)是廣泛用於表達現實各種事物之間互動關係的一種資料結構,如模擬社群互動的社群網路(social network)、論文引用圖(citation graph)、知識圖譜等。由於其透過節點(node)和邊(edge)彈性組合的結構,將可以保有豐富的資訊量,進而有著各式各樣的分析及應用,如資訊擴散(information diffusion)、社群偵測(community detection)、節點分類(node classification)、鏈結預測(link prediction)等。一般來說,圖的內容相當龐大並且結構複雜,因此這些分析的計算是相當消耗資源的,隨著表示法學習的興盛,圖學習表示法(graph representation)提供了有效率的方式進行分析。圖學習表示法將圖的元素轉換至低維度的向量空間,同時保留了圖上的原有的資訊。透過表示法,一張圖的元素如子圖(subgraph)、節點、邊甚至整張圖可以由一組或多組低維度向量所表示,因此計算時只需要存放向量矩陣而不需要存放大量的節點、邊的屬性資訊省下了計算空間,另一方面,向量計算是方便進行平行話計算的因此可以加速分析的過程。除此以外,根據不同的種類的圖作為輸入,如異質圖(heterogeneous graph)、同質圖(homogeneous graph)、屬性圖(attribute graph)等,圖學習表示法皆有能力將其轉會為低維度向量進而分析,因此可以廣泛應用於各種情境,如生物醫學中的蛋白質分析、電商中的推薦系統。

在推薦系統的使用情境當中亦不乏圖學習表示法的應用,如 DeepWalk 透過隨機遊走(random walk)的抽樣方式取得一系列節點,並應用 word2vec 模型中的 skip-gram 演算法產生各個節點的向量,將節點間的區域鄰近關係(neighborhood similarity)帶入向量當中,LINE 模型定義了節點間的一階相似度(first-order proximity)用於模擬成對節點間的局部相似度,及二階相似度(second-order proximity)模擬兩節點其鄰居節點的相似度,並結合負抽樣演算法(negative sampling)訓練出能夠代表節點間鄰近關係的向量。在冷啟動問題的應用情境中,透過圖表示學習法將能夠更輕易的將社群網路、知識圖譜的資訊帶入推薦系統當中,如 KGCN 應用圖卷積網路(graph convolution neural network)於圖表示法並定義了不同種類的關係(relation)對於不同節點/實體(entity)有不同重要性,這些重要性將會在針對節點計算卷積(convolution)時有不同的權重影響,藉此帶入知識圖譜的資訊於推薦系統中對齊(align)的商品。