引言

現(xiàn)實(shí)世界中的許多問題都可以通過圖結(jié)構(gòu)表述，例如基因序列關(guān)系、蛋白質(zhì)結(jié)構(gòu)、知識(shí)圖譜和社交網(wǎng)絡(luò)，鑒于這種廣泛存在的結(jié)構(gòu)特征，研究者們自然會(huì)嘗試將特定結(jié)構(gòu)融入學(xué)習(xí)模型中，概率圖模型（PGM: probabilistic graphical model）和圖神經(jīng)網(wǎng)絡(luò)（GNN: Graph Neural Networks）應(yīng)該算是兩個(gè)代表性的方向；其中結(jié)合深度學(xué)習(xí)的圖神經(jīng)網(wǎng)絡(luò)近幾年發(fā)展迅速，在CV、NLP和推薦系統(tǒng)的應(yīng)用場景中的表現(xiàn)出巨大潛力。丁香園團(tuán)隊(duì)希望能在GNN領(lǐng)域中找到合適的文本知識(shí)表示學(xué)習(xí)方法，因此本文將從表示學(xué)習(xí)的角度出發(fā)，通過列舉GNN領(lǐng)域一些有代表性的工作介紹圖表示學(xué)習(xí)的實(shí)驗(yàn)思路。

Graph Embedding

傳統(tǒng)Graph Embedding算法在表示學(xué)習(xí)任務(wù)中其實(shí)表現(xiàn)不俗，而且當(dāng)圖的規(guī)模不斷增長時(shí)，訓(xùn)練GNN也不是一件容易的事，此外今天GNN做表示學(xué)習(xí)的基本框架與傳統(tǒng)算法的區(qū)別并不大，因此本文首先介紹傳統(tǒng)Graph Embedding算法，首先是圖表示先驅(qū)的Deepwalk。

• DeepWalk: Online Learning of Social Representations [1]

Deepwalk的思路非常直白，在持有結(jié)構(gòu)化數(shù)據(jù)（建好的圖）的條件下，基本可以看作采樣+Word2vec的兩段式，可以大致認(rèn)為Deepwalk就是「如何將帶結(jié)構(gòu)信息的數(shù)據(jù)喂給word2vec」。我們知道word2vec的訓(xùn)練方式（原文采用SkipGram）是通過中心詞（target）預(yù)測窗口內(nèi)的詞（context），所以Deepwalk的采樣過程可以看作「如何定義和獲取圖上節(jié)點(diǎn)的context」。這里Deepwalk給出最基本的方法，就是定義任意中心節(jié)點(diǎn)到鄰接節(jié)點(diǎn)的跳轉(zhuǎn)概率，然后跳轉(zhuǎn)一定次數(shù)作為該中心節(jié)點(diǎn)的context，這樣就組成了word2vec接受的輸入樣本：(target，context)

可以認(rèn)為Deepwalk確立了一種通用的Graph Embedding求解框架，即：(1) 定義中心節(jié)點(diǎn)的鄰域及采樣方法；(2) 設(shè)計(jì)(target, neighbors)的embedding模型。后續(xù)的Graph Embedding模型及很多復(fù)雜的GNN模型其實(shí)也都是改進(jìn)這兩個(gè)框架的具體操作，例如下面的LINE和Node2vec。

• LINE: Large-scale Information Network Embedding [2]

在Deepwalk之后較短的時(shí)段內(nèi)（2014年之后），多數(shù)工作直接延用了word2vec訓(xùn)練embedding向量的方式，并將重點(diǎn)放在如何改進(jìn)中心節(jié)點(diǎn)鄰域的采樣方法上。LINE的關(guān)鍵改進(jìn)就在于對(duì)context的設(shè)定，作者提出了一階和二階兩種鄰域關(guān)系，如下圖所示

一階相鄰就是直接相連，二階相鄰則是取兩個(gè)鄰接節(jié)點(diǎn)鄰居的重合部分；這樣，一階關(guān)系可以采樣出(target, neighbor)，二階關(guān)系則會(huì)采樣出(target, neighbors)；對(duì)此，可以分別用sigmoid和softmax計(jì)算二元組的概率分布；在計(jì)算loss時(shí)，如果將兩種采樣方式合并計(jì)算，會(huì)得到一組embedding，也可以考慮分開計(jì)算loss，得到兩組embedding weights，再用concat([first_order_embed, second_order_embed])合并。

• node2vec: Scalable Feature Learning for Networks [3]

Node2vec也沿用了word2vec的訓(xùn)練方式，而在采樣上比LINE更接近Deepwalk的思路。不過作者進(jìn)一步思考了節(jié)點(diǎn)間的距離和節(jié)點(diǎn)本身的位置這些結(jié)構(gòu)信息的意義。

我們知道圖的遍歷有深度優(yōu)先(DFS)和廣度優(yōu)先(BFS)兩種，采用DFS會(huì)更容易采樣到較遠(yuǎn)的點(diǎn)，而BFS傾向于發(fā)掘周圍的點(diǎn)。對(duì)此，作者提出了兩個(gè)概念來描述這種位置結(jié)構(gòu)：(1): 同質(zhì)性(homophily)，指緊密圍繞從而形成一個(gè)社群(community)的節(jié)點(diǎn)，比如圖上的 u 和 s_2 ; (2): 結(jié)構(gòu)性(structural equivalence)，只雖然距離較遠(yuǎn)因而不能構(gòu)成同一個(gè)社群，但彼此社群中都處于類似的位置，比如圖上的 u 和 s_6 （注意，作者表示DFS更側(cè)重同質(zhì)性，BFS傾向于結(jié)構(gòu)性，和大家的理解一致么）

基于這兩種結(jié)構(gòu)性質(zhì)，作者擴(kuò)展了Deepwalk的采樣方法，設(shè)定了兩個(gè)概率參數(shù) p 和 q ，分別是回退參數(shù)（p: return parameter）和進(jìn)出參數(shù)（q: in-out parameter），如上圖所示，當(dāng)前節(jié)點(diǎn)從 t 到 v ，如果 p 降低，則退回到 t 的概率就越大，q 降低則驅(qū)使算法走向新節(jié)點(diǎn)；控制這兩個(gè)參數(shù)就可以改變context的采樣結(jié)果，影響最終emebdding結(jié)果。

還有諸如SDNE，EGES這類工作都屬于Graph Embeding方法，操作簡單實(shí)用性高，在圖的節(jié)點(diǎn)數(shù)量很大時(shí)，下面的GNN方法不太容易訓(xùn)練應(yīng)用，傳統(tǒng)Graph Embeding方法依然有大量戲份。

Graph Neural Networks

GNN的正式定義大約來源于2009年的這篇文章[4]，隨后經(jīng)歷了大約6年的沉寂直到2014年，受word2vec的啟發(fā)，包括前文提到的一系列Graph Embedding算法相繼出現(xiàn)；再之后，大概2017年起，各類結(jié)合了Gated機(jī)制，CNN，Attention的GNN模型結(jié)構(gòu)不斷被提出；時(shí)至今日，基于GNN的研究已經(jīng)深入諸多領(lǐng)域，新穎概念層出不窮；筆者初窺門徑，以下僅選個(gè)別有代表性的工作簡單介紹。

• GCN: SEMI-SUPERVISED CLASSIFICATION WITH GRAPH CONVOLUTIONAL NETWORKS [5]

融入CNN形成的GCN框架可能是最流行的GNN之一，然而CV領(lǐng)域大放異彩的CNN并不能直接用在屬于非歐空間的圖結(jié)構(gòu)上，直觀的說法是"圖結(jié)構(gòu)中鄰居節(jié)點(diǎn)的個(gè)數(shù)不固定，卷積核無法計(jì)算"，因此需要某種轉(zhuǎn)換操作，要么固定鄰居節(jié)點(diǎn)個(gè)數(shù)，要么將非歐空間的圖轉(zhuǎn)換到歐式空間，本節(jié)文章中的GCN就屬于后者，這就引出了GCN的核心之一的Laplacian算子；下面我們先解釋圖的空間變換。

描述Laplacian算子不得不提Fourier變換，我們知道Fourier變換可以將時(shí)域函數(shù)轉(zhuǎn)換到頻域的"線性變換"，公式大概長這樣：

需要關(guān)注的是 e^{-2 piixv} 這個(gè)"基向量"，就是它將時(shí)域函數(shù)f(x)映射到以它為基的頻域空間；那么對(duì)于GCN，關(guān)鍵就在于找到這個(gè)"基向量"，通過"圖Fourier變換"完成非歐空間到歐式空間的映射，這才引出Laplacian算子；參照wiki上的中文定義[6]：拉普拉斯算子或是拉普拉斯算符(Laplace operator, Laplacian)是由歐幾里得空間中的一個(gè)函數(shù)的梯度的散度給出的微分算子；先做梯度運(yùn)算，再做散度運(yùn)算，簡單說就是二階導(dǎo)數(shù)，它描述了二維空間中某種量的傳播狀態(tài)；最終，研究者們找到了拉普拉斯矩陣L作為Laplacian算子，并用L的特征向量作為基向量執(zhí)行"圖Fourier變換"，L就是圖的度矩陣減去鄰接矩陣，取L的特征向量組U為"圖Fourier變換"的基向量（這里僅簡單描述Laplacian算子的作用意義，有關(guān)Laplacian算子和Fourier變換的公式推導(dǎo)有很多精彩的文章珠玉在前，這里便不做贅述）。

Laplacian算子和圖Fourier變換是GCN的基石，不過GCN的內(nèi)容遠(yuǎn)不止如此，圖卷積網(wǎng)絡(luò)的框架是多篇文章不斷改進(jìn)的結(jié)果，這里引用的工作算是博采眾長，早在2014年[7]就有研究提出了用拉普拉斯矩陣的特征分解實(shí)現(xiàn)卷積，但計(jì)算中包含的特征分解計(jì)算復(fù)雜度高，因此另一個(gè)讓GCN應(yīng)用廣泛的貢獻(xiàn)是通過切比雪夫多項(xiàng)式(Chebyshev)近似圖卷積計(jì)算，引文第二段集中介紹了該近似過程，綜合改進(jìn)后的GCN如引文中的公式2所示，其中HW就如同CNN運(yùn)算一般，前面矩陣A和D的運(yùn)算就是圖卷積的近似。

最后，這類對(duì)整張圖做特征提取的方法被稱為Transductive approaches，下面要介紹另一類Inductive approaches中有代表性的GraphSAGE。

• GraphSAGE: Inductive Representation Learning on Large Graphs [8]

Transductive approaches都有一個(gè)問題，就是必須要對(duì)全圖操作，這樣一方面內(nèi)存會(huì)限制圖的規(guī)模，另一方面想更新圖結(jié)構(gòu)就不得不重新處理整張圖；GraphSAGE的一個(gè)好處就是"以偏概全"，不再對(duì)整張圖做變換和卷積，而是采樣固定個(gè)數(shù)鄰居并基于這種target-neighbors的子圖結(jié)構(gòu)訓(xùn)練聚合函數(shù)(AGGREGATE)，這樣一方面可以根據(jù)需求，通過控制鄰居個(gè)數(shù)來增減圖的規(guī)模，另一方面對(duì)于新加入的節(jié)點(diǎn)，完全可以用訓(xùn)練好的聚合函數(shù)獲得embedding表示或其他下有任務(wù)結(jié)果。

其實(shí)看算法流程很容易想象整個(gè)流程，基本也符合deepwalk的兩段式，值得注意的就是其中的AGGREGATE，文中對(duì)比了四種聚合函數(shù)：lstm，gcn，mean，pool(max)；大家可以參照文中的對(duì)比實(shí)驗(yàn)選擇合適自己任務(wù)的方法。此外，作者在文中也給出了針對(duì)無監(jiān)督和有監(jiān)督的不同loss設(shè)定，無監(jiān)督繼續(xù)采用類似word2vec的方式，有監(jiān)督任務(wù)則替換成適合特定目標(biāo)的損失即可，另外本文發(fā)表于2017年，Transformer也是同年發(fā)表，而今結(jié)合self-attention做聚合函數(shù)的工作已經(jīng)非常多了，框架上基本也和GraphSAGE一致，很容易替換擴(kuò)展。

總體來說，本文無論是思路，結(jié)構(gòu)還是源碼都比較簡單，對(duì)應(yīng)到工程落地，可以參考同一團(tuán)隊(duì)在KDD2018發(fā)表的，基于Pinterest公司推薦系統(tǒng)的實(shí)踐工作[9]；不過，我們嘗試用GraphSAGE直接學(xué)習(xí)文本知識(shí)的embedding時(shí)，感覺并不十分理想，首先是當(dāng)圖的規(guī)模非常大時(shí)訓(xùn)練比較慢，收斂情況與子圖采樣密切相關(guān)，找采樣參數(shù)需要大量實(shí)驗(yàn)；另外需要注意，源碼中構(gòu)造圖結(jié)構(gòu)用的是Python的networkx庫，這個(gè)庫是基于dict存儲(chǔ)的，比較費(fèi)內(nèi)存；最后，我們的文本知識(shí)包含大約150w節(jié)點(diǎn)，1億條邊，無監(jiān)督訓(xùn)練的結(jié)果不夠理想，當(dāng)然很可能是數(shù)據(jù)量不足以及還沒找到合適的采樣參數(shù)，不過，這種規(guī)模的圖對(duì)我們來說已經(jīng)很大了，用稀疏矩陣存儲(chǔ)會(huì)更省資源，不過得用sparse的API重寫整個(gè)結(jié)構(gòu)，所以如果有辦法可以直接對(duì)稀疏矩陣做計(jì)算得到embedding豈不省事許多，下一節(jié)的ProNE。

• ProNE: Fast and Scalable Network Representation Learning [10]

本文大概應(yīng)該歸為Graph Embedding一類，因?yàn)椴]有GCN和GraphSAGE這些框架中的多層網(wǎng)絡(luò)結(jié)構(gòu)，不過本文第二部分的embedding過程應(yīng)用了GCN中spectual方法的思路，在GCN之后介紹也更合適。本文將圖表示學(xué)習(xí)的模型分為三類，GNN歸為一類，前文的Deepwalk、LINE、node2vec屬于skip-gram類，ProNE則屬于矩陣分解類模型。

ProNE整體可分為兩部分，第一部分對(duì)無向圖結(jié)構(gòu)的鄰接矩陣做稀疏矩陣分解。作者定義了如下?lián)p失函數(shù)最大化節(jié)點(diǎn) r 和鄰居 c 的共現(xiàn)頻率p，同時(shí)最小化負(fù)采樣鄰居概率：

最小化loss的充分條件是loss對(duì) r{i}^{T} c{j} 的偏導(dǎo)數(shù)為0，可得節(jié)點(diǎn) r 和鄰居 c 的的距離公式并構(gòu)造距離矩陣

對(duì)距離矩陣 M 做tSVD(truncated Singular Value Decomposition)并取最后top-d的奇異值和對(duì)應(yīng)向量作為這一部分的節(jié)點(diǎn)embedding表示，為了效率，作者用randomized tSVD加速運(yùn)算。

第二部分利用高階Cheeger不等式(higher-order Cheeger's inequality)，上一步僅利用了每個(gè)節(jié)點(diǎn)的局部鄰居，這里借鑒GCN中spectrum方法的思路設(shè)計(jì)了傳播策略(propagation strategy)，目的是獲取圖結(jié)構(gòu)中的局部平滑(localized smoothing)信息和全局聚類(global clustering)信息，而Cheeger不等式為我們解釋了圖結(jié)構(gòu)譜方法的特征值與局部平滑(localized smoothing)信息和全局聚類(global clustering)信息之間的關(guān)系。

首先，GCN部分的引文中其實(shí)介紹了，圖Fourier變換實(shí)際上是一次圖Fourier變換加一次逆變換，這個(gè)過程可以理解為：先由拉普拉斯矩陣的特征向量組 U 將 X 映射到對(duì)應(yīng)向量空間，用特征值lambda_k 縮放 X ，再被逆變換處理；然后，在圖分割理論(graph partition)中有一個(gè) k-way Cheeger 常量 \rho_{G}(k) ，這個(gè)常量越小表示圖的劃分越好，直觀的表述大概是"子圖聚合程度越高，該常量對(duì)應(yīng)越小，相對(duì)的劃分就越好"；最后我們通過高階Cheeger不等式將拉普拉斯矩陣的特征值和這個(gè)常量聯(lián)系起來

上式表明Cheeger 常量對(duì)應(yīng)著特征值的上下界，更小的常量對(duì)應(yīng)更小的特征值，也對(duì)應(yīng)著更內(nèi)聚(clustering)的子圖，反之對(duì)應(yīng)更大的特征值，此時(shí)圖結(jié)構(gòu)中的子圖更為平滑(smoothing)；因此，在這部分里，作者設(shè)計(jì)了一個(gè)函數(shù) g 用于控制特征值的取值范圍，此時(shí)的圖Fourier變換為

最后，再參照GCN中利用切比雪夫多項(xiàng)式近似計(jì)算 \widetilde{L} 即可，整個(gè)過程可以看作限制特征值范圍的GCN，注意最后為保證正交性，還需要對(duì)Embedding結(jié)果做一次SVD。

我們知道通常對(duì)于大規(guī)模圖結(jié)構(gòu)，Graph Embedding在效率上的價(jià)值更為明顯，ProNE在效率方面比Deepwalk、LINE、node2vec都要出色，文中的時(shí)間對(duì)比表明，在5個(gè)常見的GNN數(shù)據(jù)集上(PPI、Wiki、BlogCatalog、DBLP、Youtube)，ProNE比效率最好的LINE快大概9-50倍；我們用150w節(jié)點(diǎn)，1億條邊的稀疏矩陣做文本知識(shí)學(xué)習(xí)，默認(rèn)參數(shù)（128維向量，迭代10次）耗時(shí)大概1小時(shí)以內(nèi)；具體來說，我們?cè)噲D識(shí)別出每個(gè)文本知識(shí)詞匯中包含的特定類別詞，例如下面的"口腔咽喉黏膜充血"中的"口腔、咽喉、黏膜"均為身體部位；"卵巢雄激素腫瘤"中包含的"卵巢"屬于身體部位類詞匯，"腫瘤"屬于常見病癥詞的詞根，按照包含詞以及類別構(gòu)建鄰接圖，應(yīng)用ProNE方法，并按cosine計(jì)算相關(guān)詞匯，結(jié)果看起來還不錯(cuò)：

出色的efficient兼顧不錯(cuò)的effective，源碼的Python版是用networkx加載圖結(jié)構(gòu)，這部分完全可以用scipy.sparse的API替換，只有一點(diǎn)美中不足，和GCN一樣不能直接應(yīng)用于有向圖，所以下面為大家介紹一篇有關(guān)文本有向圖Embedding的工作SynGCN。

• Incorporating Syntactic and Semantic Information in Word Embeddings using Graph Convolutional Networks [11]

本文將GNN應(yīng)用于Word Embedding任務(wù)，框架上基本采用GraphSAGE的鄰居采樣+編碼函數(shù)聚合信息的模式，訓(xùn)練上也與word2vec類似，值得關(guān)注的是其融合有向圖的SemGCN結(jié)構(gòu)

具體而言，word2vec的context在這里由target詞的知識(shí)組成，在編碼過程中我們希望對(duì)有向邊做特別處理，其實(shí)這里有向圖就起到了一個(gè)線性組合的作用，對(duì)有向圖的融合非常簡單，就是構(gòu)造一個(gè)有向圖的鄰接矩陣，對(duì)原有的特征embedding矩陣 M 做線性變換，與 M 疊加后再過下一個(gè)編碼層。這種線性組合的方式很容易上手，而且至少對(duì)個(gè)別節(jié)點(diǎn)做微調(diào)效果立竿見影，不過大規(guī)模應(yīng)用是否普遍有效還需要進(jìn)一步檢驗(yàn)，我們還沒做進(jìn)一步試驗(yàn)，這里僅作為一種思路介紹。

總結(jié)

本文僅簡要列舉了幾項(xiàng)圖結(jié)構(gòu)表示學(xué)習(xí)發(fā)展中有代表性的工作供大家參考；GCN和GraphSAGE代表了圖結(jié)構(gòu)轉(zhuǎn)換兩種處理角度，就表示學(xué)習(xí)而言，或許是受圖規(guī)模和計(jì)算資源的限制，后續(xù)工作中傾向于后者的采樣方法的占比較高，但"圖Fourier變換"的思路非常精彩不容忽視，而且在流形學(xué)習(xí)等領(lǐng)域也有諸多應(yīng)用；基于子圖訓(xùn)練聚合函數(shù)的方向上，除了嘗試更有效的編碼結(jié)構(gòu)外，如何擴(kuò)展和結(jié)合更豐富的圖結(jié)構(gòu)信息應(yīng)該是更關(guān)鍵的方向，除了上文提到的有向圖外，在推薦系統(tǒng)中已經(jīng)出現(xiàn)了很多基于異構(gòu)信息網(wǎng)絡(luò)(heterogeneous information network[12])的工作，用于結(jié)合節(jié)點(diǎn)和邊對(duì)應(yīng)的不同類別或語義；當(dāng)然回歸工程實(shí)踐，我們不該忽略Graph Embedding類的方法，也不該將其與GNN割裂開，上文提到的ProNE中的傳播策略完全可以用于其他方法的Embedding向量上，基于此類方法再訓(xùn)練GraphSAGE有可能更容易收斂，簡單的有向圖線性組合也具有指導(dǎo)意義。下一步我們也希望在ProNE的基礎(chǔ)上嘗試更多深層結(jié)構(gòu)，并基于有向圖線性組合的思路，調(diào)整圖結(jié)構(gòu)來貼合不同應(yīng)用任務(wù)。

---

參考文獻(xiàn)

[1]?https://arxiv.org/abs/1403.6652

[2]?https://arxiv.org/abs/1503.03578

[3]?https://arxiv.org/abs/1607.00653

[4]?https://persagen.com/files/misc/scarselli2009graph.pdf

[5]?https://arxiv.org/abs/1609.02907

[6]?https://zh.wikipedia.org/wiki/拉普拉斯算子

[7]?https://arxiv.org/abs/1312.6203

[8]?https://papers.nips.cc/paper/6703-inductive-representation-learning-on-large-graphs.pdf

[9]?https://arxiv.org/pdf/1806.01973.pdf

[10]?https://www.ijcai.org/Proceedings/2019/594

[11]?https://www.aclweb.org/anthology/P19-1320/?

[12]?https://arxiv.org/pdf/1511.0485

?轉(zhuǎn)載自：https://zhuanlan.zhihu.com/p/122285764

總結(jié)

以上是生活随笔為你收集整理的初探GNN-文本表示学习的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。