網(wǎng)絡(luò)表示學(xué)習(xí)發(fā)展綜述

(西華大學(xué)計(jì)算機(jī)與軟件工程學(xué)院 四川 成都 610039)

引言

伴隨著互聯(lián)網(wǎng)的快速普及、在線社交網(wǎng)絡(luò)迅猛發(fā)展，每天網(wǎng)絡(luò)上都會(huì)產(chǎn)生量級(jí)極大的數(shù)據(jù)，在已經(jīng)成為當(dāng)前計(jì)算機(jī)科學(xué)重要研究領(lǐng)域的網(wǎng)絡(luò)數(shù)據(jù)挖掘中，這些帶挖掘的數(shù)據(jù)無(wú)疑具有極大的研究?jī)r(jià)值。

網(wǎng)絡(luò)數(shù)據(jù)最鮮明的特點(diǎn)就體現(xiàn)在數(shù)據(jù)節(jié)點(diǎn)之間存在著鏈接關(guān)系，這也反映了網(wǎng)絡(luò)中樣本點(diǎn)并非完全獨(dú)立。表示學(xué)習(xí)的目的是為網(wǎng)絡(luò)中的每一個(gè)節(jié)點(diǎn)分配某個(gè)線性空間中的向量，使得這些向量能夠保持原來(lái)網(wǎng)絡(luò)的結(jié)構(gòu)信息，這對(duì)于社會(huì)網(wǎng)絡(luò)分析以及機(jī)器學(xué)習(xí)領(lǐng)域具有重大的意義[1]。

一、網(wǎng)絡(luò)表示學(xué)習(xí)方法介紹

網(wǎng)絡(luò)表示學(xué)習(xí)，又名網(wǎng)絡(luò)嵌入、圖嵌入，目的在于用低維緊湊的向量表示網(wǎng)絡(luò)中的節(jié)點(diǎn)，為下一步的任務(wù)提供有效的特征表示。讓映射出來(lái)的向量能夠擁有表示和推理的功能，方便下游計(jì)算，從而能夠使得到的向量表示使用于社交網(wǎng)絡(luò)中廣泛使用的應(yīng)用場(chǎng)景里去。因此，網(wǎng)絡(luò)表示學(xué)習(xí)具有相當(dāng)重大的意義。

1.基于因子分解的方法

基于結(jié)構(gòu)的因子分解方法，大都是用傳統(tǒng)的方法進(jìn)行因子分解[2]。

(1)Locally Linear Embedding (LLE)

局部線性嵌入(Locally Linear Embedding, LLE)是無(wú)監(jiān)督的非線性降維算法，是流形學(xué)習(xí)經(jīng)典算法。LLE假設(shè)高維空間的數(shù)據(jù)樣本在局部依舊包含歐式空間的性質(zhì)，即“鄰域保持”思想：該節(jié)點(diǎn)可以通過(guò)其鄰居節(jié)點(diǎn)點(diǎn)的線性組合重構(gòu)出來(lái)。

假使有樣本節(jié)點(diǎn)y1，用K-NN算法找到與它最接近的三個(gè)樣本節(jié)點(diǎn)y2，y3，y4。使用這三個(gè)鄰域節(jié)點(diǎn)表示該樣本節(jié)點(diǎn)，即：

y1=w12y2+w13y3+w14y4

能夠發(fā)現(xiàn)，在降維前后權(quán)重系數(shù)基本不發(fā)生改變的。利用這種局部相關(guān)性，LLE在局部建立降為映射關(guān)系，之后再將這種局部映射推廣至整個(gè)網(wǎng)絡(luò)。

(2)Laplacian Eigenmaps

拉普拉斯特征映射的思想比較簡(jiǎn)單。觀察問(wèn)題的角度與LLE類似，用子圖的思想去構(gòu)建數(shù)據(jù)之間的關(guān)系。

通過(guò)拉普拉斯特征映射可以體現(xiàn)出數(shù)據(jù)內(nèi)在的流形結(jié)構(gòu)。如果節(jié)點(diǎn)之間的邊權(quán)重越大，就說(shuō)明這兩個(gè)節(jié)點(diǎn)的距離越近，那么在嵌入后節(jié)點(diǎn)對(duì)應(yīng)的值就應(yīng)越接近。 最優(yōu)化目標(biāo)如下：

=tr(YTLY)

其中L是對(duì)應(yīng)網(wǎng)絡(luò)的拉普拉斯矩陣。即 L=D-A。D 是度矩陣，A 是鄰接矩陣。約束條件為1=YTDY, 移除了嵌入時(shí)的隨意縮放因素。問(wèn)題的標(biāo)準(zhǔn)解就是求標(biāo)準(zhǔn)化拉普拉斯矩陣最小的幾個(gè)特征值所對(duì)應(yīng)的特征向量。

2.基于隨機(jī)游走的方法

基于隨機(jī)游走的方法，主要有DeepWalk和Node2Vec[3]。

(1)DeepWalk

DeepWalk是最早提出的基于Word2Vec的節(jié)點(diǎn)向量化模型，是把語(yǔ)言模型的方法用在了社會(huì)網(wǎng)絡(luò)之中，從而可以用深度學(xué)習(xí)的方法，除了表示節(jié)點(diǎn)以外，還可以反映節(jié)點(diǎn)間的拓?fù)潢P(guān)系，即表現(xiàn)出社會(huì)網(wǎng)絡(luò)中的社會(huì)關(guān)系。

其大致思路，就是使用構(gòu)造節(jié)點(diǎn)在網(wǎng)絡(luò)上的隨機(jī)游走路徑，模擬文本生成的過(guò)程，給出節(jié)點(diǎn)序列，再將該序列向量化，然后用Skip-gram和Hierarchical Softmax模型對(duì)隨機(jī)游走序列中每個(gè)局部序列內(nèi)的節(jié)點(diǎn)對(duì)進(jìn)行概率建模，將隨機(jī)游走序列的似然概率最大化，利用隨機(jī)梯度下降方法調(diào)整參數(shù)。

(2)Node2Vec

Node2Vec通過(guò)改進(jìn)隨機(jī)游走序列生成的方法對(duì)DeepWalk算法進(jìn)行了拓展。在DeepWalk中，是完全隨機(jī)地去選取隨機(jī)游走序列中下一個(gè)節(jié)點(diǎn)的，而node2vec通過(guò)加入兩個(gè)超參數(shù)p和q，將寬度優(yōu)先搜索(BFS)和深度優(yōu)先搜索(DFS)的思路加入到隨機(jī)游走序列的生成進(jìn)程中。BFS重視鄰居節(jié)點(diǎn)，并描繪了相對(duì)鄰域的表示，BFS中的節(jié)點(diǎn)通常會(huì)多次出現(xiàn)，使得核心節(jié)點(diǎn)鄰域中節(jié)點(diǎn)的方差減少；DFS則注重高層次節(jié)點(diǎn)間同質(zhì)性的刻畫。即BFS能夠體現(xiàn)圖的結(jié)構(gòu)性質(zhì)，而DFS則能夠反映鄰居節(jié)點(diǎn)的相似性大小。

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

在網(wǎng)絡(luò)表示學(xué)習(xí)中，還有基于深度學(xué)習(xí)的方法，比較具有代表性的方法就是Structural Deep Network Embedding (SDNE)[4]。

SDNE是第一個(gè)將深度學(xué)習(xí)應(yīng)用于網(wǎng)絡(luò)表示學(xué)習(xí)中的方法。它是一種半監(jiān)督的學(xué)習(xí)模型。它屬于在LINE模型的基礎(chǔ)上做出了拓展，在使用深度學(xué)習(xí)的方法進(jìn)行網(wǎng)絡(luò)表示學(xué)習(xí)中結(jié)合了一階估計(jì)和二階估計(jì)的優(yōu)點(diǎn)，以此來(lái)表示出網(wǎng)絡(luò)中的局部以及全局結(jié)構(gòu)屬性，具有很強(qiáng)的適應(yīng)性。SDNE利用了深度自動(dòng)編碼器分別優(yōu)化1階和2階相似度，通過(guò)最小化節(jié)點(diǎn)表示之間的歐式距離來(lái)保留鄰居節(jié)點(diǎn)之間的相似度。學(xué)習(xí)得到的向量表示能夠包含網(wǎng)絡(luò)高度非線性的局部和全局結(jié)構(gòu)，而且對(duì)稀疏網(wǎng)絡(luò)也有很高的適用性。

4.其他方法

LINE 的大概思路就是把一個(gè)大規(guī)模網(wǎng)絡(luò)中的所有節(jié)點(diǎn)根據(jù)其關(guān)系的緊密程度映射到向量空間中，表征成為低維向量，聯(lián)系緊密的節(jié)點(diǎn)會(huì)被映射到接近的位置，而在網(wǎng)絡(luò)中衡量?jī)蓚€(gè)節(jié)點(diǎn)聯(lián)系緊密程度的重要標(biāo)準(zhǔn)就是這兩個(gè)節(jié)點(diǎn)之間邊的權(quán)值。該模型既想到節(jié)點(diǎn)間的一階相似性：兩個(gè)節(jié)點(diǎn)之間邊的權(quán)值較大就認(rèn)為這兩個(gè)節(jié)點(diǎn)比較相似，也兼顧到了二階相似性：即兩個(gè)節(jié)點(diǎn)也許沒(méi)有直接相連的邊，但假如它們的一階公共節(jié)點(diǎn)相當(dāng)多，那么也認(rèn)為這兩個(gè)節(jié)點(diǎn)是比較相似的。

LINE不僅保留了網(wǎng)絡(luò)局部和全局的網(wǎng)絡(luò)結(jié)構(gòu)信息，還可以用于含有無(wú)權(quán)或有權(quán)邊的大型網(wǎng)絡(luò)，并且相當(dāng)有效。

二、結(jié)論

本文總結(jié)了網(wǎng)絡(luò)表示學(xué)習(xí)的節(jié)點(diǎn)表示學(xué)習(xí)的主要方法。上述網(wǎng)絡(luò)表示學(xué)習(xí)方法，基本涵蓋了網(wǎng)絡(luò)表示學(xué)習(xí)的研究。