網(wǎng)絡(luò)頂點(diǎn)表示學(xué)習(xí)方法

周曉旭 劉迎風(fēng) 付英男 朱仁煜 高明

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

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

中圖分類號(hào)：TP391 文獻(xiàn)標(biāo)志碼：A DOI：10.3969/j，issn，1000-5641.202091007

0引言

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

在頂點(diǎn)嵌入后，可以利用機(jī)器學(xué)習(xí)或者深度學(xué)習(xí)方法在嵌入空間中高效地進(jìn)行網(wǎng)絡(luò)分析，如鏈接預(yù)測(cè)、頂點(diǎn)分類和網(wǎng)絡(luò)可視化，鏈接預(yù)測(cè)指預(yù)測(cè)缺失的鏈接或?qū)?lái)可能產(chǎn)生的鏈接，頂點(diǎn)分類指基于有標(biāo)記的頂點(diǎn)和網(wǎng)絡(luò)拓?fù)潢P(guān)系進(jìn)一步確定其他頂點(diǎn)的標(biāo)簽，網(wǎng)絡(luò)可視化將原始網(wǎng)絡(luò)降維到二維空間中展示，有助于直觀理解網(wǎng)絡(luò)中頂點(diǎn)間的相互關(guān)系。

1問(wèn)題與挑戰(zhàn)

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

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

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

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

2問(wèn)題定義

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

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

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

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

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

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

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

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

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

3網(wǎng)絡(luò)頂點(diǎn)表示學(xué)習(xí)方法的分類

長(zhǎng)久以來(lái)，針對(duì)網(wǎng)絡(luò)頂點(diǎn)表示學(xué)習(xí)已經(jīng)提出了許多方法，本文根據(jù)它們?cè)趫D的頂點(diǎn)表示方法上的差異，將這些模型分成三大類別：基于矩陣分解的方法、基于隨機(jī)游走的方法和基于深度神經(jīng)網(wǎng)絡(luò)的方法，接下來(lái)介紹每一類里的代表性方法。

3.1基于矩陣分解的方法

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

3.1.1Locall，y Linear Embedding

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

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

3.3基于深度學(xué)習(xí)的方法

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

3.3.1SDNE

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

3.3.2SiNE

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

4應(yīng)用

學(xué)習(xí)到的網(wǎng)絡(luò)頂點(diǎn)嵌入可以應(yīng)用到后續(xù)任務(wù)中，如鏈接預(yù)測(cè)、頂點(diǎn)分類和可視化，通?？梢愿鶕?jù)這些任務(wù)上的評(píng)價(jià)指標(biāo)來(lái)衡量學(xué)習(xí)到的網(wǎng)絡(luò)頂點(diǎn)嵌入的優(yōu)劣。

4.1鏈接預(yù)測(cè)

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

4.2頂點(diǎn)分類

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

4.3網(wǎng)絡(luò)可視化

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

5總結(jié)

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