周曉旭 劉迎風 付英男 朱仁煜 高明

摘要：網(wǎng)絡是一種常用的數(shù)據(jù)結(jié)構(gòu)，在社交、通信和生物等領(lǐng)域廣泛存在，如何對網(wǎng)絡頂點進行表示是學術(shù)界和工業(yè)界廣泛關(guān)注的難點問題之一，網(wǎng)絡頂點表示學習旨在將頂點映射到一個低維的向量空間，并且能夠保留網(wǎng)絡中頂點問的拓撲結(jié)構(gòu)，本文在分析網(wǎng)絡頂點表示學習的動機與挑戰(zhàn)的基礎(chǔ)上，對目前網(wǎng)絡頂點表示學習的主流方法進行了詳細分析與比較，主要包括基于矩陣分解、基于隨機游走和基于深度學習的方法，最后介紹了衡量網(wǎng)絡頂點表示性能的方法。

關(guān)鍵詞：網(wǎng)絡嵌入：隨機游走：矩陣分解：深度神經(jīng)網(wǎng)絡

中圖分類號：TP391 文獻標志碼：A DOI：10.3969/j，issn，1000-5641.202091007

0引言

現(xiàn)實世界中普遍存在類型豐富多樣的網(wǎng)絡數(shù)據(jù)結(jié)構(gòu)，如社交網(wǎng)絡、通信網(wǎng)絡、生物網(wǎng)絡等，這些網(wǎng)絡表示實體之間的關(guān)系，規(guī)模從數(shù)百個頂點到數(shù)百萬個甚至數(shù)十億個頂點，分析網(wǎng)絡在許多應用中都發(fā)揮著至關(guān)重要的作用，因此也得到學術(shù)界和工業(yè)界越來越多的關(guān)注，對網(wǎng)絡進行有效分析首先要對網(wǎng)絡頂點進行表示，鄰接矩陣、拉普拉斯矩陣等傳統(tǒng)表示方法展示了頂點間的顯式關(guān)系，更復雜的、高階的拓撲結(jié)構(gòu)很難被有效地表示出來，而且這類傳統(tǒng)方法通常復雜度較高，難以應用在大規(guī)模網(wǎng)絡上，為了突破傳統(tǒng)方法的“瓶頸”，頂點嵌入技術(shù)旨在盡可能保留網(wǎng)絡拓撲結(jié)構(gòu)、頂點語義信息和頂點屬性的前提下，將頂點映射到低維向量空間中，該空間也被稱之為頂點嵌入空間，嵌入空間不僅能夠重構(gòu)原始網(wǎng)絡，而且保留了網(wǎng)絡的拓撲特征，如果兩個頂點在網(wǎng)絡拓撲結(jié)構(gòu)上是相似的，那么這兩個頂點在嵌入空間中也要盡量靠近。

在頂點嵌入后，可以利用機器學習或者深度學習方法在嵌入空間中高效地進行網(wǎng)絡分析，如鏈接預測、頂點分類和網(wǎng)絡可視化，鏈接預測指預測缺失的鏈接或?qū)砜赡墚a(chǎn)生的鏈接，頂點分類指基于有標記的頂點和網(wǎng)絡拓撲關(guān)系進一步確定其他頂點的標簽，網(wǎng)絡可視化將原始網(wǎng)絡降維到二維空間中展示，有助于直觀理解網(wǎng)絡中頂點間的相互關(guān)系。

1問題與挑戰(zhàn)

由于網(wǎng)絡數(shù)據(jù)結(jié)構(gòu)存在一些獨特的特征，致使網(wǎng)絡頂點表示學習面臨眾多問題和挑戰(zhàn)，其中三個最關(guān)鍵挑戰(zhàn)分別是：

（1）稀疏性真實世界中的網(wǎng)絡頂點的度通常服從長尾分布，能夠觀察到的邊僅占很小的比例，許多頂點間的邊存在缺失，實際上大多數(shù)頂點僅有很少的連接，少數(shù)頂點擁有更多的連接，由于稀疏的網(wǎng)絡鏈接給頂點表示造成了困難，因此網(wǎng)絡中普遍存在的稀疏特征給頂點表示學習帶來了很大的挑戰(zhàn)，

（2）保留結(jié)構(gòu)和屬性頂點表示學習需要保留原始網(wǎng)絡中的局部結(jié)構(gòu)和全局結(jié)構(gòu)，網(wǎng)絡中彼此相近的頂點在嵌入空間中也應該盡量靠近，頂點間的相對位置也要保持不變，此外，網(wǎng)絡頂點的屬性信息也是網(wǎng)絡的重要組成部分，但如何將這些信息與網(wǎng)絡拓撲結(jié)構(gòu)綜合在一起？因此，同時保留頂點的結(jié)構(gòu)和屬性信息是網(wǎng)絡頂點嵌入學習的重要挑戰(zhàn)。

（3）可擴展性現(xiàn)實世界中的信息網(wǎng)絡其規(guī)模越來越龐大，從數(shù)百個頂點到數(shù)百萬個頂點甚至數(shù)十億個頂點，分析大規(guī)模信息網(wǎng)絡的需求越來越迫切，但也要避免耗費昂貴的計算代價，因此，網(wǎng)絡表示學習方法要具備可擴展性，能夠針對大規(guī)模網(wǎng)絡進行頂點表示學習，并進一步支持針對大規(guī)模網(wǎng)絡的其他分析與應用。

2問題定義

定義1（網(wǎng)絡）

網(wǎng)絡G（V，E）由頂點集合V={V1…，Vn）和邊集合E={eij）構(gòu)成的二元組，其中ei表示Vi與Vi之間的連接，無權(quán)網(wǎng)絡G的鄰接矩陣記為A，其中當Vi與Vj存在連接時，aij=1.否則aj=0.對于無向網(wǎng)絡G，A具有對稱性，即aij=aji，帶權(quán)網(wǎng)絡G的權(quán)重矩陣記為S其中sij表示Vi與vj連接上的權(quán)重，權(quán)重能夠表示頂點間聯(lián)系的強弱。

網(wǎng)絡頂點在嵌入低維向量空間的過程中，需要利用頂點間的局部相似性，在LINE中提出了頂點間的局部結(jié)構(gòu)相似性。

定義2（一階相似性）一階相似性表示網(wǎng)絡中兩個頂點間的局部相似性，如果頂點%和%間有邊連接，則邊上的權(quán)重sij即為頂點vi和vj的一階相似度;若沒有邊連接，sij=0.則一階相似性也為0.

在現(xiàn)實網(wǎng)絡中，能夠觀察到的邊僅占很小的比例，而許多頂點間的邊都缺失了，這種頂點對的一階相似性為0.一階相似性忽略了頂點間的隱式關(guān)系，因此為了保留更豐富的網(wǎng)絡結(jié)構(gòu)，進一步定義頂點之間的高階相似性。

定義3（二階相似性）二階相似性表示網(wǎng)絡中兩個頂點之間的鄰居相似性，用pi=（wi，1.…，wi V ）表示頂點vi與其他頂點的一階接近度，wij表示頂點vi和頂點vj的一階相似性，二階相似性可以，通過pi和pj的相似性確定，若頂點vi與vj間不存在一樣的鄰居頂點，則二階相似性為

二階相似性考慮兩個頂點鄰域間的相似性，如果它們具有相似的鄰居，則認為它們是相似的，在社交網(wǎng)絡中，有相同朋友的人往往具有相似的興趣，很可能也會成為朋友，在單詞共現(xiàn)網(wǎng)絡中，經(jīng)常與同一組單詞同時出現(xiàn)的單詞往往具有相似的含義。

如圖1所示，頂點6和頂點7之間存在邊，且權(quán)重較大，則認為兩者一階相似性較高，而頂點5和頂點6之間不存在邊，則兩者間的一階相似性為0.但是由于它們的鄰居重合度較高，則認為兩者的二階相似性較高。

學習到的頂點表示空間需要保留網(wǎng)絡結(jié)構(gòu)并可以重構(gòu)原始的網(wǎng)絡，如果兩個頂點之間存在鏈接，為了保留網(wǎng)絡關(guān)系，這兩個頂點在嵌入空間中的距離也應相對較小。

3網(wǎng)絡頂點表示學習方法的分類

長久以來，針對網(wǎng)絡頂點表示學習已經(jīng)提出了許多方法，本文根據(jù)它們在圖的頂點表示方法上的差異，將這些模型分成三大類別：基于矩陣分解的方法、基于隨機游走的方法和基于深度神經(jīng)網(wǎng)絡的方法，接下來介紹每一類里的代表性方法。

3.1基于矩陣分解的方法

對于有禮個頂點的網(wǎng)絡G，用n×n的鄰接矩陣A來表示網(wǎng)絡的拓撲結(jié)構(gòu)，每一行每一列的值代表頂點和其余頂點的連接關(guān)系，值為0表示頂點之間不存在邊，鄰接矩陣的行向量或列向量構(gòu)成了頂點的一種n維表示，這種表示的維度通常都很高，而網(wǎng)絡嵌入想要得到的是低維頂點向量表示，通過矩陣分解、維度約減，可以將高維的原始矩陣分解獲得低維表示，例如，對鄰接矩陣、拉普拉斯矩陣、轉(zhuǎn)移概率矩陣等進行特征值分解、奇異值分解、非負矩陣分解，從而獲得頂點的低維表示。

3.1.1Locall，y Linear Embedding

局部線性嵌入（Locally Linear Embedding，LLE）假設(shè)頂點可以由它的鄰居向量線性表示，降維之后仍能保持同樣的線性關(guān)系，即權(quán)重系數(shù)基本保持不變。

LLE首先利用K一最近鄰算法或其他方法確定降維前頂點vi的k個鄰居頂點，然后使用最小化均方誤差找到線性表示的歸一化權(quán)重系數(shù)wij，wij表示頂點vj對于重構(gòu)頂點vi的重要性，即對于所有頂點：

3.3基于深度學習的方法

網(wǎng)絡節(jié)點嵌入的學習目標是找到能將原始網(wǎng)絡空間轉(zhuǎn)換為低維向量空間的映射函數(shù)，網(wǎng)絡的結(jié)構(gòu)復雜，而且是非線性結(jié)構(gòu)，因此之前通過線性模型尋找節(jié)點嵌入的方法不足以保留信息網(wǎng)絡的非線性特征，而深度神經(jīng)網(wǎng)絡能夠?qū)?shù)據(jù)中的非線性結(jié)構(gòu)進行建模，在許多領(lǐng)域都得到了應用且獲得了成功，因此許多工作用端到端的深度網(wǎng)絡學習網(wǎng)絡頂點表示。

3.3.1SDNE

與使用淺層模型的嵌入方法相比，真實網(wǎng)絡結(jié)構(gòu)較為復雜，淺層模型找到的頂點表示向量不能保存網(wǎng)絡高階的非線性特征，而深度學習擅長捕捉非線性特征，Structural Deep Network Embedding，簡稱SDNE，率先將深度學習應用在網(wǎng)絡表示學習中，與之前使用神經(jīng)網(wǎng)絡對圖進行表示的已有工作不同，SDNE學習的是可以在任務之間利用的低維表示，而且考慮了頂點之間的一階和二階相似性，如圖6所示，模型使用半監(jiān)督學習能夠同時保留一階和二階網(wǎng)絡相似性，SDNE首先利用無監(jiān)督學習，根據(jù)頂點的鄰居結(jié)構(gòu)，通過多個非線性函數(shù)構(gòu)成自動編碼器獲取頂點的潛在表示，yi（k）=σ（w（k）yi（k-1）+6（k）），以此保留網(wǎng)絡的二階相似性，然后為了保留一階相似性，借助拉普拉斯特征映射方法，有監(jiān)督地根據(jù)鄰接矩陣代表的先驗知識調(diào)整節(jié)點的嵌入表示，SDNE遵循的思路是當相似的頂點在嵌入空間中被映射得較遠時，就讓模型的損失變大，模型的損失函數(shù)為：

3.3.2SiNE

符號網(wǎng)絡是指具有正邊和負邊的信息網(wǎng)絡，正邊可以表示朋友、信任、喜歡、支持等積極關(guān)系，負

4應用

學習到的網(wǎng)絡頂點嵌入可以應用到后續(xù)任務中，如鏈接預測、頂點分類和可視化，通?？梢愿鶕?jù)這些任務上的評價指標來衡量學習到的網(wǎng)絡頂點嵌入的優(yōu)劣。

4.1鏈接預測

鏈接預測是指預測頂點對之間是否存在邊，這些邊可能是缺失的，也可能會在將來網(wǎng)絡的不斷演化中形成，在社交網(wǎng)絡中，鏈接預測技術(shù)可以預測兩個人是否為朋友關(guān)系，以此推薦可能的好友，在生物網(wǎng)絡中，鏈接預測用來判斷蛋白質(zhì)之間是否存在未知的相互作用，這可以提高在真實世界中實驗的目標性，減少昂貴的實驗測試。

4.2頂點分類

頂點分類是利用已知標簽頂點來推測其他頂點的標簽，在網(wǎng)絡中，頂點會帶有標簽，表示實體的屬性，例如，社交網(wǎng)絡中的標簽可以表示人的興趣、喜惡等，在引用網(wǎng)絡中，標簽可以表示文章的關(guān)鍵詞或研究領(lǐng)域，生物網(wǎng)絡中頂點的標簽可以表示實體的功能，由于標記成本高或者其他原因，只有少數(shù)頂點被打上了標簽，網(wǎng)絡中大部分頂點的標簽是未知的。

4.3網(wǎng)絡可視化

網(wǎng)絡可視化是將原始網(wǎng)絡降維到二維空間中以方便展示，應用主成分分析或者t-sNE，可以將學習的頂點嵌入進行可視化，以觀察網(wǎng)絡的空間結(jié)構(gòu)，如圖9所示，a-2）為使用Deepwalk學習到的空手道俱樂部網(wǎng)絡a-1）的可視化結(jié)果，b）為使用LINE學習到的DBLP網(wǎng)絡的可視化結(jié)果，通過將網(wǎng)絡表示進行可視化可以證明模型的有效性。

5總結(jié)

本文回顧了近年來網(wǎng)絡頂點表示學習的模型和算法，將現(xiàn)有的模型按照基于矩陣分解、基于隨機游走和基于深度學習分為3類，并且介紹了每一類中具有代表性的算法，算法的目標是能夠保留網(wǎng)絡的結(jié)構(gòu)和屬性特征，基于矩陣分解的模型適合于小型網(wǎng)絡，模型復雜度較高;基于隨機游走的模型借鑒了自然語言處理領(lǐng)域的思想，將隨機序列視為語句，頂點視為單詞，再進行后續(xù)的分析處理;新興的深度學習將自編碼器、圖卷積技術(shù)應用到頂點表示學習中，適合處理大型的網(wǎng)絡，網(wǎng)絡頂點表示學習的未來研究方向是利用非線性模型，如基于深度學習的算法，研究不同屬性的圖，如符號圖、異構(gòu)圖和二分圖，網(wǎng)絡嵌入方法還可以應用到知識圖譜、生物學網(wǎng)絡和社交網(wǎng)絡等領(lǐng)域以方便研究。