陳寶祥

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

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

1 符號及基本定義

1.1 無向圖、有向圖與加權圖

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

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

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

1.2 異構網絡

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

1.3 網絡嵌入

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

2 網絡嵌入的方法

近年來關于網絡嵌入算法研究方向主要有：基于隨機游走的算法、結合外部信息的算法、基于深度學習的算法以及基于異構信息網絡的算法.

2.1 基于隨機游走的算法

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

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

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

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

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

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

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

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

2.2 結合外部信息的算法

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

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

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

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

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

2.3 基于深度學習的算法

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

圖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的卷積操作，最終的目標是單個節(jié)點的分類和表示學習.該方法定義了一種半監(jiān)督方式，可以將部分節(jié)點的標簽也作為損失的一部分.

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

2.4 基于異構信息網絡的算法

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

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

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

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

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

3 網絡嵌入在社會科學中的應用

3.1 網絡嵌入在社會學的應用

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

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

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

3.2 網絡嵌入在語言學的應用

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

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

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

3.3 網絡嵌入在心理學的應用

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

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

圖10 神經網絡框架Fig.10 Neural network framework

3.4 網絡嵌入在人類學的應用

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

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

4 結論

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

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