網(wǎng)絡(luò)嵌入在計算社會科學(xué)中的發(fā)展與應(yīng)用

陳寶祥

（安徽工程大學(xué)計算機與信息學(xué)院，蕪湖 241000）

網(wǎng)絡(luò)嵌入即網(wǎng)絡(luò)表示學(xué)習(xí)也被稱為圖嵌入.它旨在將高維稀疏向量轉(zhuǎn)化為低維稠密向量，從而使得算法的性能和效率得到提升.本文針對前人的工作做出了系統(tǒng)性的總結(jié)以及展望，對未來可應(yīng)用的領(lǐng)域做出了預(yù)測以及分析.對比之前已有的綜述[1-3]本文有兩個主要優(yōu)勢：1）將網(wǎng)絡(luò)嵌入與計算社會科學(xué)緊密結(jié)合，討論了在社會科學(xué)中的多個領(lǐng)域內(nèi)網(wǎng)絡(luò)嵌入的重要應(yīng)用.2）將網(wǎng)絡(luò)嵌入的經(jīng)典算法做出了全面的對比，而不只是局限于各類算法間的小范圍比較.

1 符號及基本定義

1.1 無向圖、有向圖與加權(quán)圖

在無向圖中定義G=，其中V是非空集合它包含著n個向量，E是V中的構(gòu)成的無序二元組.也就是說，如果圖中的每一條邊都是沒有方向的，那么這個圖就是無向圖.G的鄰接矩陣A是一個n×n的矩陣，如果Vi和Vj之間有一條邊，則Aij=1否則Aij=0.

有向圖與無向圖的區(qū)別在于圖中的邊是否具有方向，即在無向圖中，兩個頂點Vi和Vj之間連通，則這兩個頂點必是可以互相可以到達(dá)的，而若是有向圖則不是這種情況了，即使存在Vi到Vj的路徑也不一定存在Vj和Vi的路徑.

加權(quán)圖是圖中的每一條邊e∈E都與權(quán)重相關(guān)聯(lián).如果在一條邊中如果權(quán)重是1，則表示兩個節(jié)點間有正向連接，反之如果邊的權(quán)重是-1則表示兩個節(jié)點之間有反向連接.

1.2 異構(gòu)網(wǎng)絡(luò)

異構(gòu)網(wǎng)絡(luò)是具有多種類型的節(jié)點以及多種類型的邊的網(wǎng)絡(luò)G.形式上，G與節(jié)點類型fv：e→O，?v∈V和邊的類型fe：e→Q，?e∈E相關(guān)聯(lián).其中O是所有節(jié)點類型的集合，Q是所有邊類型的集合.

1.3 網(wǎng)絡(luò)嵌入

網(wǎng)絡(luò)嵌入旨在產(chǎn)生對于網(wǎng)絡(luò)G的映射函數(shù)，Φ：V→R|V|×d，d?|V|，這個映射Φ對于每個節(jié)點v∈V都定義了潛在表示.同時，也用Φ（v）來表示各個節(jié)點v的嵌入向量.

2 網(wǎng)絡(luò)嵌入的方法

近年來關(guān)于網(wǎng)絡(luò)嵌入算法研究方向主要有：基于隨機游走的算法、結(jié)合外部信息的算法、基于深度學(xué)習(xí)的算法以及基于異構(gòu)信息網(wǎng)絡(luò)的算法.

2.1 基于隨機游走的算法

DeepWalk[4]出現(xiàn)于2014年，當(dāng)時正值Word2vec算法在文本上成功應(yīng)用，掀起了一波向量化的浪潮.Word2vec算法可以將一個詞映射為一個低維向量，并且保持語料中豐富信息.而DeepWalk算法則是利用隨機游走中獲得的局部信息，來獲得類似文本的序列數(shù)據(jù)[5-6]，它將節(jié)點ID作為一個個“詞”，使用skip-gram方法訓(xùn)練得到“詞向量”[7].這篇論文為后續(xù)的一系列工作起到了啟發(fā)作用.其中DeepWalk與Word2vec的對比如表1.

表1 DeepWalk與Word2vec對比Tab.1 ThecomparisonbetweenDeepWalk and word2vec

1）Node2vec算法.Node2vec算法[8]是在DeepWalk算法的基礎(chǔ)上演變而來，它定義了一個偏隨機游走的策略生成序列，以探索不同的鄰域，以學(xué)習(xí)網(wǎng)絡(luò)節(jié)點連續(xù)特征表示.如算法字面意思，它是一種將節(jié)點映射到低維特征空間的方法，這種方法可以最大限度地保留節(jié)點的網(wǎng)絡(luò)鄰域.與DeepWalk一樣該算法采用skip-gram訓(xùn)練，對比分析了廣度優(yōu)先（BFS）以及深度優(yōu)先（DFS）兩種游走方式，圖1所示是從節(jié)點u在k=3的情況下分別使用BFS和DFS搜索.

DeepWalk中根據(jù)邊的權(quán)重而進(jìn)行隨機游走，而Node2vec則加入了權(quán)重調(diào)整參數(shù)α.圖2中t是上一個節(jié)點，v是最新節(jié)點，x是候選的下一個節(jié)點.通過不同的p和q設(shè)置參數(shù)，可以達(dá)到保留不同信息的目的.特別的是，當(dāng)p和q都為1的時候，Node2vec也就相當(dāng)于DeepWalk.

圖1 Deep Walk的搜索策略框架Fig.1 Search strategy framework of DeepWalk

圖2 node2vec中的隨機游走Fig.2 Random walk in node2vec

2）LINE算法.LINE[9]算法分析了一階相似性和二階相似性.其中一階相似性就是兩個點直接相連，且邊權(quán)重越大說明兩個點越相似，如下圖3中的6和7.二階相似性則是兩個點之間共享了很多鄰居，如圖3的5和6.文章中以簡單的方式構(gòu)造了一個目標(biāo)函數(shù)，能同時保留二者的信息.以一階相似性為例，節(jié)點i和j相連的經(jīng)驗概率就是和歸一化后的權(quán)重，即1（i，j）=wij/W，而通過向量計算這個概率值是目標(biāo)函數(shù)是讓這兩個分布距離最小，選擇散度作為距離衡量函數(shù)就得到了最后損失函數(shù)O1.

圖3 LINE中相似性Fig.3 Proximityin LINE

2.2 結(jié)合外部信息的算法

網(wǎng)絡(luò)結(jié)構(gòu)只是分析網(wǎng)絡(luò)嵌入問題的一種方法，真實世界中節(jié)點和邊都具有實際意義.比如在一個社交網(wǎng)絡(luò)中，用戶自身會有標(biāo)簽和文本，這些信息對于網(wǎng)絡(luò)的構(gòu)建有著不可或缺的作用，本節(jié)提出的是關(guān)于結(jié)合外部信息的算法.

1）CANE算法.CANE算法考慮了節(jié)點上的文本信息[10]，學(xué)習(xí)對每個節(jié)點產(chǎn)出文本向量和結(jié)構(gòu)向量.同時分為兩個模式，一種是上下文忽略模式另一種是上下文感知模式.對于上下文忽略模式，文本向量是固定的.對于一個文本，每個詞向量組成矩陣，以l為窗口在d個核上進(jìn)行卷積操作，得到的結(jié)果按照行取最大來獲得最后的文本向量.對于上下文感知模式則引入注意力機制，如圖4所示，通過產(chǎn)出的注意力權(quán)重，再進(jìn)行聯(lián)合操作，這樣節(jié)點在不同點連接的時候作用是不一樣的.

2）CENE算法.CENE算法[11]將文本轉(zhuǎn)化為特殊的節(jié)點，由此產(chǎn)生出兩種不同的邊，分別是節(jié)點與節(jié)點，節(jié)點與文檔.如果兩種邊同時建模，則會有兩種損失函數(shù)產(chǎn)生，而若將文本拆分為句子，則句子有三種方式嵌入，如圖5所示.

3）Trans-Net算法.算法Trans-Net[12]顧名思義在思想中融入了機器翻譯，通過自動編碼邊的標(biāo)簽，再將邊映射到同一個空間加減，最后利用解碼器還原為二元標(biāo)簽集，即可得到預(yù)測結(jié)果，具體算法框架如圖6.

圖4 上下文感知文本嵌入的說明Fig.4 An illustration of context-awaretext embedding

2.3 基于深度學(xué)習(xí)的算法

深度學(xué)習(xí)算法是最近的熱潮，它的發(fā)展突飛猛進(jìn)，Word2vec其實是人工神經(jīng)網(wǎng)絡(luò)中的淺層模型.但是深度模型在獲得嵌入結(jié)果方面，有著自己的獨特優(yōu)勢，它的思路就是將網(wǎng)絡(luò)序列化再借用自然語言處理的方式訓(xùn)練模型[13].對比圖像處理方面利用卷積神經(jīng)網(wǎng)絡(luò)的操作，將卷積神經(jīng)網(wǎng)絡(luò)用在圖上就是后文提到的圖卷積網(wǎng)絡(luò).本文主要列舉了對節(jié)點進(jìn)行嵌入的方法.

圖5 CENE框架表示Fig.5 Illustration of CENE framework

圖6 TransNet框架Fig.6 Theframework of TransNet

圖7 SDNE半監(jiān)督深度模型的框架Fig.7 The framework of the semi-supervised deep model of SDNE

1）SSC-GCN算法.SSC-GCN算法[14]引入了一種被稱為spectral的卷積操作，最終的目標(biāo)是單個節(jié)點的分類和表示學(xué)習(xí).該方法定義了一種半監(jiān)督方式，可以將部分節(jié)點的標(biāo)簽也作為損失的一部分.

2）SDNE算法.SDNE算法[15]在某些邏輯方面與前文提到的TransNet有相似點，如圖7中表示了SDNE算法的基本框架，它對節(jié)點的描述特征向量使用自動編碼器編碼，加重非零項懲罰.取編碼器中間層作為向量表示，由此獲得二階相似性，相鄰節(jié)點相似度越高，則兩個節(jié)點的鄰接相鄰越相似，說明它們共享了許多鄰居，最后得到的映射向量也會更加接近.而對于一階相似性，通過評估有連邊的點的向量距離考慮，最后引入損失函數(shù)判斷.

2.4 基于異構(gòu)信息網(wǎng)絡(luò)的算法

在現(xiàn)實生活中的網(wǎng)絡(luò)不同于理想化的，異構(gòu)網(wǎng)絡(luò)才是網(wǎng)絡(luò)的真實樣貌.比如在一個交易中，涉及到的節(jié)點有商品、人、店鋪等；知識圖譜中則具有不同類型的節(jié)點和邊，但是前述的大部分工作都是工作與同構(gòu)網(wǎng)絡(luò)之下，因此研究異構(gòu)網(wǎng)絡(luò)的嵌入框架及算法對解決生活中的問題具有指導(dǎo)作用.

1）PTE算法.PTE算法[16]旨在將預(yù)測信息在最后的嵌入中體現(xiàn)出來，但是并不像CNN/RNN模型一樣直接嵌套一個復(fù)雜的預(yù)測模型.它通過定義三種網(wǎng)絡(luò)形式：單詞-單詞、單詞-文本、單詞-標(biāo)簽，將框架設(shè)置為二部圖的模型，隨后將各自的損失函數(shù)匯總到一起得到最終結(jié)果.單詞-單詞共現(xiàn)網(wǎng)絡(luò)和單詞-文本網(wǎng)絡(luò)對非監(jiān)督信息進(jìn)行編碼，分別捕獲本地上下文級單詞共現(xiàn)和文本級單詞共現(xiàn)；單詞-標(biāo)簽網(wǎng)絡(luò)對受監(jiān)督的信息進(jìn)行編碼，捕獲類級單詞的共現(xiàn).

2）HINES算法.HINES算法[17]對多元異構(gòu)網(wǎng)絡(luò)進(jìn)行嵌入，圖8中有不同類型的點，不同類型的邊.它引入了元路徑的概念，將不同點之間的連邊按照一定的元信息連起來，比如作者1-文章-作者2這樣的一個路徑表示的信息就可能是作者1與2之間合作了一篇文章，它可以推廣到很多場景.

通常對于相似的計算都是通過計算一階相似性的思路，但如果引入元路徑，那么A與B在一條路徑的兩端，相似度則應(yīng)該更大，這也取決于這條元路徑本身的信息量.圖8舉例說明了關(guān)于HINES的應(yīng)用.

圖8 舉例說明HINFig.8 An example of HIN

3 網(wǎng)絡(luò)嵌入在社會科學(xué)中的應(yīng)用

3.1 網(wǎng)絡(luò)嵌入在社會學(xué)的應(yīng)用

網(wǎng)絡(luò)嵌入廣泛應(yīng)用與各個領(lǐng)域，其中在數(shù)據(jù)挖掘和社會網(wǎng)絡(luò)分析與挖掘技術(shù)方面尤甚.關(guān)于網(wǎng)絡(luò)嵌入在社會學(xué)中的應(yīng)用，由清華大學(xué)的團(tuán)隊帶領(lǐng)設(shè)計架構(gòu)的網(wǎng)站Aminer，它實現(xiàn)了研究者的語義信息抽取、面向話題的專家搜索、權(quán)威機構(gòu)搜索、話題發(fā)現(xiàn)與趨勢分析、基于話題的社會影響力分析、研究者社會網(wǎng)絡(luò)識別眾多功能[18-20].

AMiner系統(tǒng)利用網(wǎng)絡(luò)嵌入為圖處理提供了重要的作用，它解決了用戶多賬號關(guān)聯(lián)、重名排岐、專家發(fā)現(xiàn)以及跨語言知識鏈接等關(guān)鍵問題[21-23].比如利用網(wǎng)絡(luò)嵌入技術(shù)識別來自多個異構(gòu)網(wǎng)絡(luò)的用戶，并將來自不同網(wǎng)絡(luò)的語義集成在一起，由此構(gòu)成了Aminer的核心.

利用這些功能，AMiner收集到越來越多的相關(guān)信息，并吸引到更多的使用者進(jìn)行訪問，據(jù)統(tǒng)計Aminer系統(tǒng)收集了7 900多萬篇論文信息、3 900多萬研究者信息，1.3億論文引用關(guān)系、780萬知識實體以及3萬多學(xué)術(shù)會議/期刊.吸引了全球220多個國家的600多萬用戶訪問.

3.2 網(wǎng)絡(luò)嵌入在語言學(xué)的應(yīng)用

隨著社會的發(fā)展，同一個詞語的意思以及詞的使用頻率在隨著時間不停地變化.因此在語言學(xué)中，通常會將詞匯意思的變遷以及詞語的使用頻率變化作為研究對象進(jìn)而分析比較.但是一旦引入嵌入的方法研究這個問題時，研究方式就可以更進(jìn)一步，將詞語轉(zhuǎn)化為低維向量，從而定量地分析社會變遷以及詞匯的語義變遷.如圖9是單詞“gay”的語義變遷情況.

圖9 “gay”的詞義變遷Fig.9 Semantic changeof“gay”

傳統(tǒng)的詞向量中一個詞的向量中只有一個值非零，雖然存在簡單的方法將詞轉(zhuǎn)化為向量，卻忽視了詞語詞間內(nèi)部的聯(lián)系，因此數(shù)據(jù)稀疏問題成為了當(dāng)時處理篇幅巨大的文本的時的障礙.隨后最為人所熟悉的改進(jìn)方案Word2vec利用skip-gram模型通過詞向量預(yù)測上下文的詞向量從而提高了性能與效率.近些年又有考慮一詞多義的算法出現(xiàn)[24-25]，它對不同的詞義建立不同的詞向量來預(yù)測上下文的詞向量.

3.3 網(wǎng)絡(luò)嵌入在心理學(xué)的應(yīng)用

抑郁是一項威脅到人生健康及安全的危險心理狀態(tài)，許多抑郁由于沒有受到及時的關(guān)心以及治療，導(dǎo)致了一些慘劇的發(fā)生.在當(dāng)今的互聯(lián)網(wǎng)社會，一些用戶會求助于在線資源的幫助去解決抑郁的情況.因此在論壇或其他一些社交網(wǎng)絡(luò)中識別抑郁用戶就成為了一項至關(guān)重要的任務(wù).這是網(wǎng)絡(luò)嵌入在心理學(xué)上的一項重大應(yīng)用，它通過采集用戶數(shù)據(jù)，并通過對照比較得到需要的結(jié)果[26].

如圖10所示，這是用戶和分類模型間共享的一般網(wǎng)絡(luò)神經(jīng)框架.每個輸入都有卷積網(wǎng)絡(luò)處理合并，用來創(chuàng)建用戶的向量表示.這個向量可以是一個或多個密集層，然后是執(zhí)行分類的輸出層.接收的輸入層、合并操作和輸出層的類型因特定模型而異.

圖10 神經(jīng)網(wǎng)絡(luò)框架Fig.10 Neural network framework

3.4 網(wǎng)絡(luò)嵌入在人類學(xué)的應(yīng)用

偏見在現(xiàn)實世界中隨處可見，比如對某些名字的歧視，對某種外貌的歧視，在尚未深入了事物時解時就已經(jīng)在心中下好了定論了.在論文[27]中，首先測試了職業(yè)向量詞是否在現(xiàn)實世界中嵌入了職業(yè)性別構(gòu)成.文章使用了美國勞工統(tǒng)計局的數(shù)據(jù)，對數(shù)據(jù)進(jìn)行分級，給出了每個職業(yè)的工人人數(shù)和女性比例，因此首先使用預(yù)先訓(xùn)練的向量詞標(biāo)示單個單詞，將一個多單詞術(shù)語轉(zhuǎn)換為一個表示類別超集的單詞，同時過濾掉不可能做到這一點的職業(yè).

實驗中還測試了中性的名字是否和男孩與女孩名字的頻率有關(guān)，這也是網(wǎng)絡(luò)嵌入在人類學(xué)中的應(yīng)用部分.為了處理這個問題所面臨的難點，即有些名字也是英語單詞，通過計算每個向量到所有名稱向量的質(zhì)心距離來計算每個向量的“類名稱”，最后消除20%的類名最少的向量.

4 結(jié)論

本文所述的網(wǎng)絡(luò)嵌入方法為傳統(tǒng)的特征工程提供了一個強有力的替代方案.近年來該方法一直推動著節(jié)點分類以及鏈路預(yù)測的發(fā)展.雖然前人在這條路上已經(jīng)做出了不少工作，但仍有許多問題需要完善，比如建立新的理論框架等.

完備的理論不僅使該領(lǐng)域的研究人員受益，同時在通過一致且有意義的基準(zhǔn)測試任務(wù)時，這些基礎(chǔ)任務(wù)也會允許應(yīng)用程序領(lǐng)域的專家更有效地區(qū)分與選擇各種方法.當(dāng)前的方法通常在不同的基準(zhǔn)上進(jìn)行評估，它們強調(diào)了不同的圖屬性，例如社區(qū)結(jié)構(gòu)、節(jié)點間強度關(guān)系.許多實際運用在生活中的應(yīng)用程序確實更關(guān)注于此，因此沒有必要為所有的任務(wù)建立共性的表達(dá)形式.在一個領(lǐng)域中，需要明確的是什么時候采用什么方法，這需要對編碼的確切內(nèi)容有著更精細(xì)的了解.