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

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

引言

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

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

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

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

1.基于因子分解的方法

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

(1)Locally Linear Embedding (LLE)

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

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

y1=w12y2+w13y3+w14y4

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

(2)Laplacian Eigenmaps

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

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

=tr(YTLY)

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

2.基于隨機游走的方法

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

(1)DeepWalk

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

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

(2)Node2Vec

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

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

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

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

4.其他方法

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

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

二、結(jié)論

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