Categories
程式開發

基於 GNN 的圖表示學習


導讀:圖數據有著複雜的結構,多樣化的屬性類型,以及多層面的學習任務,要充分利用圖數據的優勢,就需要一種高效的圖數據表示方法。與表示學習在數據學習中的重要位置一樣,圖表示學習也成了圖學習領域中的十分熱門的研究課題。

作為近幾年深度學習的新興領域,GNN 在多個圖數據的相關任務上都取得了不俗的成績,這也顯示出了其強大的表示學習能力。毫無疑問 GNN 的出現,給圖表示學習帶來了新的建模方法。表示學習本身俱有十分豐富的內涵和外延,從建模方法、學習方式、學習目標、學習任務等等方面都有所涵蓋。這些內容在前面章節均有闡述,所以本章我們主要就基於 GNN 的無監督圖表示學習進行講解。這也有另外一方面的考慮,在實際的應用場景裡面,大量的數據標籤往往具有很高的獲取門檻,研究如何對圖數據進行高效地無監督表示學習將具有十分重要的價值。

本文內容分2節,第1節主要從三種建模方法上對圖表示學習進行對比闡述。第2節分別從兩類無監督學習目標——重構損失與對比損失,對基於 GNN 的無監督表示學習進行闡述。

圖表示學習

在前面我們通常用鄰居矩陣 A∈RNxN 表示圖的結構信息,一般來說,A 是一個高維且稀疏的矩陣,如果我們直接用 A 去表示圖數據,那麼構築於之上的機器學習模型將難以適應,相關的任務學習難以高效。因此,我們需要實現一種對圖數據的更加高效的表示方式。而圖表示學習的主要目標,正是將圖數據轉化成低維稠密的向量化表示方式,同時確保圖數據的某些性質在向量空間中也能夠得到對應。這裡圖數據的表示,可以是節點層面的,也可以是全圖層面的,但是作為圖數據的基本構成元素,節點的表示學習一直是圖表示學習的主要對象。一種圖數據的表示如果能夠包含豐富的語義信息,那麼下游的相關任務如點分類、邊預測、圖分類等,就都能得到相當優秀的輸入特徵,通常在這樣的情況下,我們直接選用線性分類器對任務進行學習。圖 1 展示了圖表示學習的過程:

基於 GNN 的圖表示學習 1

圖 1 圖表示學習過程

同表示學習一樣,圖表示學習的核心也是研究數據的表示。特殊的是,圖表示學習的研究對像是圖數據。我們知道圖數據中蘊涵著豐富的結構信息,這本質上對應著圖數據因內在關聯而產生的一種非線性結構。這種非線性結構在補充刻畫數據的同時,也給數據的學習帶來了極大的挑戰。因此在這樣的背景下,圖表示學習就顯得格外重要,它具有以下兩個重要作用:

  1. 將圖數據表示成線性空間中的向量。從工程上而言,這種向量化的表示為擅長處理線性結構數據的計算機體系提供了極大的便利。
  2. 為之後的學習任務奠定基礎。圖數據的學習任務種類繁多,有節點層面的,邊層面的,還有全圖層面的,一個好的圖表示學習方法可以統一高效地輔助這些任務的相關設計與學習。

圖表示學習從方法上來說,可以分為基於分解的方法,基於隨機遊走的方法,以及基於深度學習的方法,而基於深度學習的方法的典型代表就是 GNN 相關的方法。下面我們回顧一下前兩類方法:

在早期,圖節點的嵌入學習一般是基於分解的方法,這些方法通過對描述圖數據結構信息的矩陣進行矩陣分解,將節點轉化到低維向量空間中去,同時保留結構上的相似性。這種描述結構信息的矩陣比如有鄰接矩陣(1),拉普拉斯矩陣(2),節點相似度矩陣(3)。一般來說,這類方法均有解析解,但是由於結果依賴於相關矩陣的分解計算,因此,這類方法具有很高的時間複雜度和空間複雜度。

近些年,詞向量方法在語言表示上取得了很大的成功,受該方法的啟發,一些方法開始將在圖中隨機遊走產生的序列看作句子,節點看作詞,以此類比詞向量從而學習出節點的表示。典型的方法比如 DeepWalk(4)、Node2Vec(5)等。圖 2 給出了 DeepWalk 算法的示意圖:

基於 GNN 的圖表示學習 2

圖 2 DeepWalk 算法示意圖

DeepWalk 通過隨機遊走將圖轉化成節點序列,設置中心節點左右距離為 w 的節點為 上下文 ( context ),如圖 2b 所示。同詞向量方法一樣,DeepWalk 本質上建模了中心節點與上下文節點之間的共現關係,這種關係的學習也採用了負採樣的優化手段,如圖 2d 所示。

基於隨機遊走的方法相比上一類方法,最大的優點是通過將圖轉化為序列的方式從而實現了大規模圖的表示學習。但是這也導致了兩個缺點:一是將圖轉化成序列集合,圖本身的結構信息沒有被充分利用;二是該學習框架很難自然地融合進圖中的屬性信息進行表示學習。

關於 GNN 方法的建模細節,作為本書之前相關章節的重要內容進行了闡述,這裡就不再贅述。通過之前的學習,我們可以知道基於 GNN 的圖表示學習具有以下幾點優勢:

  1. 非常自然地融合進了圖的屬性信息進行學習,而之前的方法大多把圖裡面的結構信息與屬性信息進行單獨處理。
  2. GNN 本身作為一個可導的模塊,能夠嵌入到任意一個支持端對端學習的系統中去,這種特性使得其能夠與各個層面的有監督學習任務進行有機結合( 或者以微調學習的形式進行結合),學習出更加適應該任務的數據表示。
  3. GNN 的很多模型如 GraphSAGE、MPNN 等都是支持歸納學習的,多數情況下對於新數據的表示學習可以直接進行預測,而不用像之前的多數方法需要重新訓練一次。
  4. 相較於分解類的方法只能適應小圖的學習,GNN 保證了算法在工程上的可行性,對大規模圖的學習任務也能適應。

綜上,基於 GNN 的相關方法具有強大的學習能力與廣泛的適應性,是圖表示學習重要的代表性方法。

基於 GNN 的圖表示學習

憑藉強大的端對端學習能力,GNN 這類模型可以非常友好地支持有監督的學習方式。但是 GNN 本身作為一種重要的對圖數據進行表示學習的框架,只要與相應的無監督損失函數結合起來就能實現無監督圖表示學習。無監督學習的主體在於損失函數的設計,這裡我們分兩類損失函數進行介紹:基於重構損失的 GNN 和基於對比損失的 GNN。

1. 基於重構損失的 GNN

類比於自編碼器的思路,我們可以將節點之間的鄰接關係進行重構學習,為此可以定義一個如下的圖自編碼器 ( Graph AutoEncoder ):

基於 GNN 的圖表示學習 3

基於 GNN 的圖表示學習 4

其中,Z 是所有節點的表示,這裡借助 GNN 模型同時對圖的屬性信息與結構信息進行編碼學習。 ${hat A}$ 是重構之後的鄰接矩陣,這裡使用了向量的內積來表示節點之間的鄰接關係。圖自編碼器的重構損失可以定義如下:

基於 GNN 的圖表示學習 5

由於過平滑的問題,GNN 可以輕易地將相鄰節點學習出相似的表達,這就導致解碼出來的鄰接矩陣 ${hat A}$ 能夠很快趨近於原始鄰接矩陣 A,模型參數難以得到有效優化。因此,為了使 GNN 習得更加有效的數據分佈式表示,同自編碼器一樣,我們必須對損失函數加上一些約束目標。比如,我們可以學習降噪自編碼器的做法,對輸入數據進行一定地擾動,迫使模型從加噪的數據中提取有用的信息用於恢復原數據。這種加噪的手段包括但不限於下面所列的一種或多種:

  1. 對原圖數據的特徵矩陣 X 適當增加隨機噪聲或置零處理;
  2. 對原圖數據的鄰接矩陣 A 刪除適當比例的邊,或者修改邊上的權重值。

另外,其他的許多自編碼器中的設計思路都可以被借鑒。接下來,我們看看比較重要的變分圖自編碼器 ( Variational Graph Autoencoder ,VGAE ) (6)。 VGAE 和變分自編碼器的基本框架一樣,不同的是使用了 GNN 來對圖數據進行編碼學習。下面分三個方向來介紹其基本框架包括推斷模型 ( 編碼器 )、生成模型 ( 解碼器 )、損失函數。

① 推斷模型

基於 GNN 的圖表示學習 6

基於 GNN 的圖表示學習 7

與 VAE 不同的是,這裡我們使用兩個 GNN 對 μ、σ 進行擬合:

基於 GNN 的圖表示學習 8

② 生成模型

基於 GNN 的圖表示學習 9

這裡也簡單使用了兩個節點表示向量的內積來擬合鄰接關係。

③ 損失函數

基於 GNN 的圖表示學習 10

同樣地,隱變量 z 的先驗分佈選用標準正態分佈:

基於 GNN 的圖表示學習 11

VAE 與 GNN 的結合,不僅可以被用來學習圖數據的表示,其更獨特的作用是提供了一個圖生成模型的框架,能夠在相關圖生成的任務中得到應用,如(7)(8),用其對化學分子進行指導設計。

2. 基於對比損失的 GNN

對比損失是無監督表示學習裡面另外一種十分常見的損失函數。通常對比損失會設置一個評分函數 D(·),該得分函數會提高 “真實” ( 或正 ) 樣本 ( 對 ) 的得分,降低 “假” ( 或負 ) 樣本 ( 對 ) 的得分。

類比於詞向量,我們將對比損失的落腳點放到詞與上下文上。詞是表示學習的研究主體,在這裡,自然代表的是圖數據中的節點了,上下文代表的是與節點有對應關係的對象。通常,從小到大,圖裡的上下文依次可以是節點的鄰居、節點所處的子圖、全圖。作為節點與上下文之間存在的固有關係,我們希望評分函數提高節點與上下文對的得分,同時降低節點與非上下文對的得分。用式子表示如下:

基於 GNN 的圖表示學習 12

這裡 c 表示上下文的表示向量,${bar c}$ 表示非上下文的表示向量。下面我們依次來看看該損失函數在不同上下文的具體形式。

① 鄰居作為上下文

如果把鄰居作為上下文 ,那麼上述對比損失就在建模節點與鄰居節點的共現關係。在 GraphSAGE 的論文中就描述了這樣的一種無監督學習方式,與 DeepWalk 一樣,我們可以將在隨機遊走時與中心節點 vi 一起出現在固定長度窗口內的節點 vj 視為鄰居,同時通過負採樣的手段,將不符合該關係的節點作為負樣本。與 DeepWalk 不一樣的是,節點的表示學習模型還是使用 GNN,即:

基於 GNN 的圖表示學習 13

基於 GNN 的圖表示學習 14

這裡的 pn是一個關於節點出現概率的負採樣分佈,得分函數使用了向量內積加 sigmoid 函數,將分數限制在(0, 1)內。這個方法在優化目標上與圖自編碼器基本等同,但是這種負採樣形式的對比優化,並不需要與圖自編碼器一樣顯式地解碼出鄰接矩陣${hat A}$,由於$ {hat A}$ 破壞掉了原始鄰接矩陣的稀疏性,因此該方法不需要承擔O(N2) 的空間複雜度。

② 將子圖作為上下文

將鄰居作為上下文時,強調的是節點之間的共現關係,這種共現關係更多反應了圖中節點間的遠近距離,缺乏對節點結構相似性的捕捉。而通常節點局部結構上的相似性,是節點分類任務中一個比較關鍵的因素(9)。比如圖上兩個相距很遠的節點如果具有一樣的子圖結構,基於共現關係的建模方法就難以有效刻畫這種結構上的對等性。因此,論文(10)就提出了直接將子圖作為一種上下文進行對比學習。具體子圖的定義如圖 3 所示:

基於 GNN 的圖表示學習 15

圖 3 將子圖作為上下文進行預測(10)

對於一個中心節點,如圖 3,圖中的紅色節點所示,我們用一個 GNN 在其 K 階子圖上提取其表示向量,同時我們將處於中心節點 r1-hop 與 r2-hop 之間的節點定義為該中心節點的上下文錨點,如圖 3 所示。設 K=2、r1=1、r2=4,我們用另一個 GNN 來提取每個節點作為上下文錨點時的表示向量,同時為了得到一個總的,固定長度的上下文表示向量,將使用讀出機制來聚合上下文錨點的表示向量。式子表示如下:

基於 GNN 的圖表示學習 16

基於 GNN 的圖表示學習 17

基於 GNN 的圖表示學習 18

③ 全圖作為上下文

在引文(11)中,提出了 Deep Graph Infomax ( DGI )(11) 的方法對圖數據進行無監督表示學習。該方法實現了一種節點與全圖之間的對比損失的學習機制。其具體做法如下:

基於 GNN 的圖表示學習 19

基於 GNN 的圖表示學習 20

基於 GNN 的圖表示學習 21

首先為了得到負採樣的樣本,需要對圖數據進行相關擾動,得到 $X_{{rm currupt}},A_{{rm aurrupt}}$,具體的加噪方法,上文中已有概括。然後將這兩組圖數據送到同一個 GNN 模型中進行學習。為了得到圖的全局表示,我們使用讀出機制對局部節點的信息進行聚合。在最後的損失函數中,作者固定了全圖表示,對節點進行了負採樣的對比學習。這樣處理的原因是為了方便後續的節點分類任務。從互信息(12)(13)的角度看,通過一個統一的全局表示,最大化全圖與節點之間的互信息,這樣可以在所有節點的表示之間建立起一層更直接的聯繫。比如上面提到的,相距較遠節點之間的結構相似性的學習問題,這種設計可以保障該性質的高效學習。圖 4 給出了上述過程的示意圖:

基於 GNN 的圖表示學習 22

圖 4 節點與全圖對比損失學習機制(11)

同時在全圖層面的無監督學習上,上述損失函數的負樣本剛好相反,需要抽取其他圖的表示 $bar s$ 來代替,即:

基於 GNN 的圖表示學習 23

此時,由於是全圖層面的任務,所以我們希望通過上式讓全圖與其所有局部節點之間實現互信息最大化,也即獲得全圖最有效、最具代表性的特徵,這將對圖的分類任務十分有益。

03 參考文獻

(1) S. T. Roweis, L. K. Saul, Nonlinear dimensionality reduction by locally linea embedding, Science 290 (5500) (2000) 2323–2326.

(2) M. Belkin, P. Niyogi, Laplacian eigenmaps and spectral techniques for embedding and clustering, in: NIPS, Vol. 14, 2001, pp. 585–591.

(3) M. Ou, P. Cui, J. Pei, Z. Zhang, W. Zhu, Asymmetric transitivity preserving graph embedding, in: Proc. of ACM SIGKDD, 2016, pp. 1105–1114.

(4) Perozzi B, Al-Rfou R, Skiena S. Deepwalk: Online learning of social representations(C)//Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2014: 701-710.

(5) Grover A, Leskovec J. node2vec: Scalable feature learning for networks(C)//Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2016: 855-864.

(6) Kipf T N, Welling M. Variational graph auto-encoders(J). arXiv preprint arXiv:1611.07308, 2016.

(7) Simonovsky, Martin and Komodakis, Nikos. Graphvae:Towards generation of small graphs using variational autoencoders. arXiv preprint arXiv:1802.03480, 2018.

(8) Samanta, Bidisha, De, Abir, Ganguly, Niloy, and GomezRodriguez, Manuel. Designing random graph models using variational autoencoders with applications to chemical design. arXiv preprint arXiv:1802.05283, 2018.

(9) Claire Donnat, Marinka Zitnik, David Hallac, and Jure Leskovec. Learning structural node embeddings via diffusion wavelets. In International ACM Conference on Knowledge Discovery and Data Mining (KDD), volume 24, 2018.

(10) Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitnik, Percy Liang, Vijay S. Pande and Jure Leskovec. Pre-training Graph Neural Networks. arXiv preprint arXiv:1905.12265,2019.

(11) Veličković P, Fedus W, Hamilton W L, et al. Deep graph infomax(J). arXiv preprint arXiv:1809.10341, 2018.

(12) Hjelm R D, Fedorov A, Lavoie-Marchildon S, et al. Learning deep representations by mutual information estimation and maximization(J). arXiv preprint arXiv:1808.06670, 2018.

(13) Melamud O, Goldberger J. Information-theory interpretation of the skip-gram negative-sampling objective function(C)//Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers). 2017: 167-171.

(14) Berg R, Kipf T N, Welling M. Graph convolutional matrix completion(J). arXiv preprint arXiv:1706.02263, 2017.

作者介紹

劉忠雨:畢業於華中科技大學,資深圖神經網絡技術專家,極驗科技人工智能實驗室主任和首席技術官。在機器學習、深度學習以及圖學習領域有6年以上的算法架構和研發經驗,主導研發了極驗行為驗證、深知業務風控、疊圖等產品,極驗科技目前服務於全球26萬家企業。

李彥霖:畢業於武漢大學,極驗人工智能實驗室技術專家。一直從事機器學習、深度學習、圖學習領域的研究工作。在深度神經網絡算法研發、圖神經網絡在計算機視覺以及風控中的應用等領域實踐經驗豐富。

周洋:工學博士,畢業於武漢大學,目前在華中師範大學任教。曾受邀到北卡羅萊納大學訪學,長期在大數據挖掘前沿領域進行探索和研究,並應用於地理時空大數據、交通地理等諸多方向,已發表SCI&SSCI及核心期刊論文10餘篇。

本文來自 DataFunTalk

原文鏈接

https://mp.weixin.qq.com/s?__biz=MzU1NTMyOTI4Mw==&mid=2247496943&idx=1&sn=0707f92d0992abc28d81484f4dc4d548&chksm=fbd74683cca0cf9520fceac89e0a32370a59f3d49d8430b2044e5e502128bb962a6a8c0ac728&scene=27#wechat_redirect