網(wǎng)絡(luò)表示學(xué)習(xí)

陳維政，張 巖，李曉明

北京大學(xué)信息科學(xué)技術(shù)學(xué)院 北京 100871

網(wǎng)絡(luò)表示學(xué)習(xí)

陳維政，張 巖，李曉明

北京大學(xué)信息科學(xué)技術(shù)學(xué)院 北京 100871

以Facebook、Twitter、微信和微博為代表的大型在線社會網(wǎng)絡(luò)不斷發(fā)展，產(chǎn)生了海量體現(xiàn)網(wǎng)絡(luò)結(jié)構(gòu)的數(shù)據(jù)。采用機(jī)器學(xué)習(xí)技術(shù)對網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行分析的一個(gè)重要問題是如何對數(shù)據(jù)進(jìn)行表示。首先介紹了網(wǎng)絡(luò)表示學(xué)習(xí)的研究背景和相關(guān)定義。然后按照算法類別，介紹了當(dāng)前5類主要的網(wǎng)絡(luò)表示學(xué)習(xí)算法，特別地，對基于深度學(xué)習(xí)的網(wǎng)絡(luò)表示學(xué)習(xí)技術(shù)進(jìn)行了詳細(xì)的介紹。之后討論了網(wǎng)絡(luò)表示學(xué)習(xí)的評測方法和應(yīng)用場景。最后，探討了網(wǎng)絡(luò)表示學(xué)習(xí)的研究前景。

網(wǎng)絡(luò)；表示學(xué)習(xí)；深度學(xué)習(xí)

1 引言

在互聯(lián)網(wǎng)興起之前，社會網(wǎng)絡(luò)分析一直是社會科學(xué)、心理學(xué)和人類學(xué)等專業(yè)的研究領(lǐng)域，數(shù)據(jù)規(guī)模一直都相對較小。伴隨著互聯(lián)網(wǎng)的快速普及，以Facebook、Twitter、微信、微博為代表的大型在線社會網(wǎng)絡(luò)不斷發(fā)展，這些網(wǎng)絡(luò)動輒擁有數(shù)千萬乃至數(shù)億用戶，產(chǎn)生的數(shù)據(jù)極其豐富，結(jié)構(gòu)極其復(fù)雜，成為人類社會生活的一種真實(shí)寫照。同時(shí)，學(xué)術(shù)論文引用網(wǎng)絡(luò)、移動通信網(wǎng)絡(luò)、維基百科乃至整個(gè)互聯(lián)網(wǎng)等具有網(wǎng)絡(luò)結(jié)構(gòu)的數(shù)據(jù)也得到了學(xué)術(shù)界廣泛的研究。網(wǎng)絡(luò)數(shù)據(jù)挖掘已經(jīng)成為當(dāng)前計(jì)算機(jī)科學(xué)的重要研究領(lǐng)域，每年在KDD、WSDM和ICDM等國際會議上都會發(fā)表大量相關(guān)的研究論文。

機(jī)器學(xué)習(xí)算法為相關(guān)研究提供了重要的模型和工具。如何對網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行合理表示以作為機(jī)器學(xué)習(xí)算法的輸入，是機(jī)器學(xué)習(xí)算法應(yīng)用在網(wǎng)絡(luò)數(shù)據(jù)分析中首先要面對的問題，從2013年開始舉辦的ICLR（International Conference on Learning Representations）表明，表示學(xué)習(xí)已經(jīng)成為學(xué)術(shù)界關(guān)心的重要問題。

網(wǎng)絡(luò)數(shù)據(jù)最大的特點(diǎn)在于樣本點(diǎn)之間存在著鏈接關(guān)系，這表明網(wǎng)絡(luò)中樣本點(diǎn)之間并非完全獨(dú)立。除了節(jié)點(diǎn)間的鏈接關(guān)系，網(wǎng)絡(luò)中節(jié)點(diǎn)自身也可能含有信息，比如互聯(lián)網(wǎng)中網(wǎng)頁節(jié)點(diǎn)對應(yīng)的文本信息，這些特性使得網(wǎng)絡(luò)表示學(xué)習(xí)需要考慮更多的因素。傳統(tǒng)的基于譜嵌入、最優(yōu)化、概率生成模型等框架的網(wǎng)絡(luò)表示算法已經(jīng)不能適應(yīng)大數(shù)據(jù)時(shí)代對網(wǎng)絡(luò)表示學(xué)習(xí)問題在算法效率和精度方面的更高要求。近年來，基于深度神經(jīng)網(wǎng)絡(luò)的算法在特征學(xué)習(xí)上獲得了極大的進(jìn)展，給語音識別、圖像識別、自然語言處理等領(lǐng)域帶來了一種新氣象。就自然語言處理而言，近兩年以word2vec模型為代表的基于深度學(xué)習(xí)的詞向量表示模型，掀起了一股表示學(xué)習(xí)的研究熱潮。這些深度學(xué)習(xí)模型也啟發(fā)了網(wǎng)絡(luò)表示學(xué)習(xí)的研究，近兩年的相關(guān)工作已經(jīng)展現(xiàn)出這一方向的廣闊前景。

2 相關(guān)定義

俗話說“巧婦難為無米之炊”，再強(qiáng)大的機(jī)器學(xué)習(xí)算法也需要數(shù)據(jù)進(jìn)行支持。在同樣的數(shù)據(jù)集上，針對同一個(gè)任務(wù)，由于特征的不同，同一個(gè)算法的結(jié)果也可能會有天壤之別。圖1展示了應(yīng)用機(jī)器學(xué)習(xí)算法的過程，首先從數(shù)據(jù)中提取有價(jià)值的信息，然后把數(shù)據(jù)表示成特征向量，進(jìn)而采用機(jī)器學(xué)習(xí)算法完成相關(guān)任務(wù)。由于特征的選擇和設(shè)計(jì)對算法結(jié)果的決定性作用，很多數(shù)據(jù)挖掘方面的研究工作淪為了特征工程，即把工作重心放到了針對特定的數(shù)據(jù)由人工設(shè)計(jì)出有價(jià)值的特征。因?yàn)閿?shù)據(jù)的規(guī)模越來越大，復(fù)雜性越來越高，特征工程需要耗費(fèi)大量的人力，而且需要特征設(shè)計(jì)者具備專業(yè)的領(lǐng)域知識，這與應(yīng)用機(jī)器學(xué)習(xí)算法的初衷是相違背的。這種狀況表明傳統(tǒng)的機(jī)器學(xué)習(xí)算法嚴(yán)重依賴于特征的設(shè)計(jì)，而不能從原始數(shù)據(jù)中分辨出有價(jià)值的信息。

圖1 應(yīng)用機(jī)器學(xué)習(xí)算法的流程

表示學(xué)習(xí)又稱作特征學(xué)習(xí)，是機(jī)器學(xué)習(xí)領(lǐng)域中的一個(gè)重要研究問題，它的目標(biāo)是自動學(xué)習(xí)一個(gè)從原始輸入數(shù)據(jù)到新的特征表示的變換，使得新的特征表示可以有效應(yīng)用在各種機(jī)器學(xué)習(xí)任務(wù)中，從而把人從繁瑣的特征工程中解放出來。根據(jù)訓(xùn)練數(shù)據(jù)的區(qū)別，可以把表示學(xué)習(xí)算法分為如下兩類。

● 監(jiān)督表示學(xué)習(xí)（supervised representation learning）：是指從已標(biāo)注數(shù)據(jù)中學(xué)習(xí)數(shù)據(jù)的新的特征表示。比如處理分類或者回歸任務(wù)的多層神經(jīng)網(wǎng)絡(luò)，其中的隱藏層可以作為輸入數(shù)據(jù)的新的特征。參考文獻(xiàn)[1]提出的有監(jiān)督字典學(xué)習(xí)也是一類典型的有監(jiān)督表示學(xué)習(xí)算法。

● 無監(jiān)督表示學(xué)習(xí)（unsupervised representation learning）：是指從未標(biāo)注數(shù)據(jù)中學(xué)習(xí)數(shù)據(jù)的新的特征表示。無監(jiān)督表示學(xué)習(xí)算法通常也是一種降維算法，用來從高維輸入數(shù)據(jù)中發(fā)現(xiàn)有意義的低維特征表示。經(jīng)典的代表性算法包括主成分分析、局部線性嵌入[2]、獨(dú)立成分分析[3]和無監(jiān)督字典學(xué)習(xí)[4]等。

[5]對表示學(xué)習(xí)的評價(jià)準(zhǔn)則和主要方法進(jìn)行了詳細(xì)的綜述，但對網(wǎng)絡(luò)表示學(xué)習(xí)基本沒有涉及, 而且上述的表示學(xué)習(xí)算法通常都無法直接應(yīng)用到網(wǎng)絡(luò)數(shù)據(jù)上。在一個(gè)網(wǎng)絡(luò)中，相連的節(jié)點(diǎn)之間通常存在著依賴關(guān)系。以網(wǎng)頁分類任務(wù)為例，每個(gè)網(wǎng)頁都可以認(rèn)為是一個(gè)文檔，只考慮文檔的文本內(nèi)容信息雖然也可以對網(wǎng)頁進(jìn)行分類，但卻忽視了網(wǎng)頁之間的鏈接關(guān)系。因?yàn)樵诂F(xiàn)實(shí)世界中，網(wǎng)絡(luò)中通常具有同質(zhì)性，相似的節(jié)點(diǎn)更有可能存在著聯(lián)系，直觀上說就是“人以類聚，物以群分”以及“近朱者赤，近墨者黑”，這表明有可能通過網(wǎng)絡(luò)中的鏈接信息獲得更好的節(jié)點(diǎn)（這里指一個(gè)網(wǎng)頁）特征表示。參考文獻(xiàn)[6]提出了通過網(wǎng)絡(luò)表示學(xué)習(xí)把節(jié)點(diǎn)表示為向量的3種好處：

● 可以直接利用得到的節(jié)點(diǎn)向量表示作為機(jī)器學(xué)習(xí)算法的輸入，避免針對網(wǎng)絡(luò)數(shù)據(jù)重新設(shè)計(jì)新的機(jī)器學(xué)習(xí)算法；

● 網(wǎng)絡(luò)中節(jié)點(diǎn)的距離、乘積等需要定量計(jì)算的概念不容易給出明確的定義，通過把節(jié)點(diǎn)表示成向量，可以在向量空間中直接進(jìn)行各種運(yùn)算；

● 在大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)中，節(jié)點(diǎn)之間的鏈接關(guān)系可能會非常復(fù)雜而不易觀察，但是通過在低維向量空間中進(jìn)行可視化分析展示，可以很直觀地觀察節(jié)點(diǎn)之間的關(guān)系。

為了給出網(wǎng)絡(luò)表示學(xué)習(xí)的定義，下面首先介紹一些基本的概念。

● 節(jié)點(diǎn)（vertex, node）：節(jié)點(diǎn)是網(wǎng)絡(luò)中的一個(gè)功能個(gè)體，引文網(wǎng)絡(luò)中的一篇文章、社交網(wǎng)絡(luò)中的一個(gè)用戶，都可以看作一個(gè)節(jié)點(diǎn)。

● 邊（edge）：邊是用來刻畫兩個(gè)節(jié)點(diǎn)之間關(guān)系的，可能具有方向性，稱為有向邊，比如引文網(wǎng)絡(luò)中的引用關(guān)系和郵件網(wǎng)絡(luò)中的發(fā)送接收關(guān)系；也可能不具備方向性，稱為無向邊，比如Facebook中的好友關(guān)系。

● 網(wǎng)絡(luò)（network）：網(wǎng)絡(luò)是對關(guān)系數(shù)據(jù)的刻畫，定義網(wǎng)絡(luò)G=(V,E)，V是G的節(jié)點(diǎn)集合，E是G的邊集合。

● 鄰接矩陣（adjacency matrix）：網(wǎng)絡(luò)G=(V,E)對應(yīng)的鄰接矩陣A是|V|×|V|的，鄰接矩陣直接給出了網(wǎng)絡(luò)的矩陣表示，如果(vi,vj)∈E,那么Aij=1，否則Aij=0。

● 相似度矩陣（similarity matrix）：網(wǎng)絡(luò)G=(V,E)對應(yīng)的相似度矩陣W是|V|×|V|的，如果沒有額外的信息，可以通過把鄰接矩陣A中每一行進(jìn)行歸一化得到W矩陣，W矩陣可以作為計(jì)算PageRank值時(shí)用到的轉(zhuǎn)移概率矩陣。如果有額外的信息，比如在引文網(wǎng)絡(luò)中，可以用兩篇論文的文檔相似度作為節(jié)點(diǎn)之間的相似度。相似度矩陣有時(shí)也被稱為親和度矩陣（affinity matrix）。

● 度數(shù)矩陣（degree matrix）：網(wǎng)絡(luò)G=(V,E)對應(yīng)的度數(shù)矩陣D是|V|×|V|的對角矩陣，如果i=j，那么Dij=i的度數(shù)，否則Dij=0。

● 拉普拉斯矩陣（Laplacian matrix）：網(wǎng)絡(luò)G=(V,E)對應(yīng)的拉普拉斯矩陣L滿足L=D-A。

● 特征矩陣：網(wǎng)絡(luò)G=(V,E)只給出網(wǎng)絡(luò)的鏈接關(guān)系，而網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)v可能擁有其他屬性，比如社會網(wǎng)絡(luò)中的用戶除了好友鏈接關(guān)系外，自身還擁有標(biāo)簽數(shù)據(jù)，在論文引用網(wǎng)絡(luò)中，每個(gè)文章節(jié)點(diǎn)還對應(yīng)著自身的文本內(nèi)容。定義G的特征矩陣為X，X是|V|×m維的，m是節(jié)點(diǎn)屬性的特征空間大小。X通常是一個(gè)高度稀疏的矩陣，傳統(tǒng)的表示學(xué)習(xí)算法圍繞在如何對X有效降維以獲得數(shù)據(jù)點(diǎn)的低維表示方面，而沒有考慮網(wǎng)絡(luò)的顯式鏈接關(guān)系。

● 信息網(wǎng)絡(luò)：如果網(wǎng)絡(luò)G=(V,E)對應(yīng)的特征矩陣X是非空的，那么G是一個(gè)信息網(wǎng)絡(luò)。

借鑒參考文獻(xiàn)[7]中對網(wǎng)絡(luò)表示學(xué)習(xí)的定義并進(jìn)行擴(kuò)展，給出如下定義。

定義1 （網(wǎng)絡(luò)表示學(xué)習(xí)）給定網(wǎng)絡(luò)G=(V,E)，G對應(yīng)的節(jié)點(diǎn)特征矩陣是X，對任意節(jié)點(diǎn)v∈V，學(xué)習(xí)低維向量表示rv∈Rk，rv是一個(gè)稠密的實(shí)數(shù)向量，并且滿足k遠(yuǎn)小于|V|。

定義1并不限定網(wǎng)絡(luò)G的方向性，即無論G中的邊是有向的還是無向的，都會予以考慮。定義1也不對網(wǎng)絡(luò)G中的節(jié)點(diǎn)類型做出限制，如果G中只含有一種類型的節(jié)點(diǎn)，那么G是一個(gè)同構(gòu)網(wǎng)絡(luò)；如果G中的節(jié)點(diǎn)屬于不同的類型，那么G是一個(gè)異構(gòu)網(wǎng)絡(luò)。由于針對異構(gòu)網(wǎng)絡(luò)表示學(xué)習(xí)的工作相對較少，在下文中，如果沒有特別指出，提到的網(wǎng)絡(luò)通常是指同構(gòu)網(wǎng)絡(luò)。特征矩陣X也可以是一個(gè)空矩陣，由于隱私性的要求，有時(shí)無法獲得網(wǎng)絡(luò)除了結(jié)構(gòu)之外的數(shù)據(jù)，此時(shí)只有網(wǎng)絡(luò)中顯式的鏈接信息，節(jié)點(diǎn)本身不能提供更多的信息，那么網(wǎng)絡(luò)G是一個(gè)純網(wǎng)絡(luò)。反之，如果G是非空矩陣，那么網(wǎng)絡(luò)G有結(jié)構(gòu)之外的信息，G是一個(gè)信息網(wǎng)絡(luò)?；ヂ?lián)網(wǎng)就是一個(gè)典型的信息網(wǎng)絡(luò)，考慮到在線社會網(wǎng)絡(luò)中存在大量的UGC（user generated content, 用戶原創(chuàng)內(nèi)容），在線社會網(wǎng)絡(luò)也可以構(gòu)建為信息網(wǎng)絡(luò)。

下文將針對上述各種情況下的網(wǎng)絡(luò)表示學(xué)習(xí)進(jìn)行介紹。直觀上，有兩種依據(jù)可以對不同的算法進(jìn)行分類：一種是參考表示學(xué)習(xí)的分類，即將所有的網(wǎng)絡(luò)表示學(xué)習(xí)算法分為有監(jiān)督的網(wǎng)絡(luò)表示學(xué)習(xí)和無監(jiān)督的網(wǎng)絡(luò)表示學(xué)習(xí)；另一種是根據(jù)輸入數(shù)據(jù)的不同進(jìn)行劃分，比如按照網(wǎng)絡(luò)的方向性、是否是異構(gòu)網(wǎng)絡(luò)等性質(zhì)。然而這兩種劃分依據(jù)并不合適，因?yàn)楫?dāng)前的網(wǎng)絡(luò)表示學(xué)習(xí)算法的主要區(qū)別在于算法類型，同一算法類型下的算法框架都是相似的，因此第3節(jié)將按照算法類型的區(qū)別對相關(guān)研究工作進(jìn)行分類整理。

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

3.1 基于譜方法的網(wǎng)絡(luò)表示學(xué)習(xí)

從廣義上看，譜方法是指利用輸入數(shù)據(jù)矩陣的譜（比如特征值和特征向量，奇異值和奇異向量）的一類算法的統(tǒng)稱[7]。針對網(wǎng)絡(luò)表示學(xué)習(xí)，這個(gè)矩陣由特定的算法設(shè)計(jì)決定，可能是相似度矩陣、拉普拉斯矩陣等類型。譜方法常用來獲得數(shù)據(jù)的低維表示[8]，比如經(jīng)典的PCA（principal components analysis，主成分分析）算法中就是對樣本的協(xié)方差矩陣選取特征向量進(jìn)行降維。雖然可以把網(wǎng)絡(luò)表示成鄰接矩陣，作為PCA或者SVD（singular value decomposition，奇異值分解）的輸入以獲得節(jié)點(diǎn)的低維表示，但是由于缺乏節(jié)點(diǎn)內(nèi)在的信息, 通常這種表示的質(zhì)量較差[9]。基于譜方法的網(wǎng)絡(luò)表示學(xué)習(xí)只考慮了結(jié)構(gòu)信息，難以直接對信息網(wǎng)絡(luò)進(jìn)行應(yīng)用，這里對幾個(gè)代表性算法進(jìn)行介紹。

圖2 DGE算法的降維效果展示[6]

參考文獻(xiàn)[2]提出LLE（locally linear embedding）是一種非線性降維算法。LLE算法認(rèn)為每一個(gè)數(shù)據(jù)點(diǎn)都可以由其近鄰點(diǎn)的線性加權(quán)組合構(gòu)造得到。LLE算法的輸入是一個(gè)鄰接矩陣[10]，然后計(jì)算出每個(gè)節(jié)點(diǎn)的局部重建權(quán)值矩陣，最后推導(dǎo)出一個(gè)特征值分解問題，進(jìn)而計(jì)算節(jié)點(diǎn)的低維表示。

參考文獻(xiàn)[11]提出的LaplacianEigenmaps算法的直觀思想是希望相鄰的節(jié)點(diǎn)在降維后的空間中盡可能地接近。LaplacianEigenmaps算法可以反映出數(shù)據(jù)內(nèi)在的流形結(jié)構(gòu)。LaplacianEigenmaps算法的輸入也是鄰接矩陣，與LLE算法不同的是LaplacianEigenmaps算法最終選取拉普拉斯矩陣的最小k個(gè)非零特征值對應(yīng)的特征向量作為學(xué)習(xí)到的網(wǎng)絡(luò)表示。

LLE算法和LaplacianEigenmaps算法都只能處理無向網(wǎng)絡(luò)，但現(xiàn)實(shí)中很多網(wǎng)絡(luò)（如網(wǎng)頁鏈接網(wǎng)絡(luò)）都是有方向的，Chen等基于隨機(jī)游走的思想提出了DGE（directed graph embedding）算法[6]，DGE算法可以處理有向或無向網(wǎng)絡(luò)，如果無向網(wǎng)絡(luò)是連通的，DGE算法此時(shí)等價(jià)于LaplacianEigenmaps算法。圖2給出了DGE算法把WebKB數(shù)據(jù)映射到二維空間的可視化效果，WebKB數(shù)據(jù)集包括康奈爾、德克薩斯和威斯康辛3所大學(xué)的2 883個(gè)網(wǎng)頁組成的鏈接網(wǎng)絡(luò)，圖2中3種不同顏色的節(jié)點(diǎn)對應(yīng)了不同大學(xué)的網(wǎng)絡(luò)。

參考文獻(xiàn)[12]從社團(tuán)檢測的角度設(shè)計(jì)網(wǎng)絡(luò)表示學(xué)習(xí)算法，目的在于希望學(xué)習(xí)到的網(wǎng)絡(luò)表示向量的每一維度都代表一個(gè)社團(tuán)所占的權(quán)重。其目標(biāo)函數(shù)是希望模塊度最大化[13]，最終將問題轉(zhuǎn)化為選取模塊度矩陣的前k個(gè)特征值對應(yīng)的特征向量作為網(wǎng)絡(luò)特征表示。

3.2 基于最優(yōu)化的網(wǎng)絡(luò)表示學(xué)習(xí)

基于最優(yōu)化的網(wǎng)絡(luò)表示學(xué)習(xí)算法是指根據(jù)一個(gè)明確的優(yōu)化目標(biāo)函數(shù)，并且以節(jié)點(diǎn)在低維空間的向量表示作為參數(shù)，通過求解目標(biāo)函數(shù)的最大化或最小化，求出節(jié)點(diǎn)的低維表示的一類算法。下面介紹兩個(gè)代表性的工作。

網(wǎng)絡(luò)表示學(xué)習(xí)的一個(gè)重要應(yīng)用是節(jié)點(diǎn)標(biāo)簽預(yù)測[14]。通常的情景是，在一個(gè)網(wǎng)絡(luò)上每個(gè)節(jié)點(diǎn)都有對應(yīng)的標(biāo)簽，但是只有部分節(jié)點(diǎn)的標(biāo)簽是已知的，其余節(jié)點(diǎn)的標(biāo)簽是未知的，針對這個(gè)任務(wù)，參考文獻(xiàn)[15]中提出了LSHM（latent space heterogeneous model）算法。LSHM算法同時(shí)學(xué)習(xí)節(jié)點(diǎn)的向量表示和標(biāo)簽的線性分類函數(shù)，它的優(yōu)化目標(biāo)函數(shù)包括兩部分：一部分考慮了網(wǎng)絡(luò)上的平滑性，即相鄰節(jié)點(diǎn)的標(biāo)簽盡可能相似；另一部分考慮了分類函數(shù)對已知標(biāo)簽的預(yù)測能力，因此LSHM算法是一種半監(jiān)督的網(wǎng)絡(luò)表示學(xué)習(xí)算法。如果只考慮目標(biāo)函數(shù)的第一部分，那么LSHM算法就可以以相似度矩陣作為輸入。

LSHM算法可以處理異構(gòu)網(wǎng)絡(luò)，圖3給出了一個(gè)異構(gòu)網(wǎng)絡(luò)的示例，這個(gè)異構(gòu)網(wǎng)絡(luò)包括作者、論文和詞語3種類型的節(jié)點(diǎn)，作者都有一個(gè)表示其所屬研究領(lǐng)域的標(biāo)簽，論文都有一個(gè)會議標(biāo)簽。LSHM算法處理異構(gòu)網(wǎng)絡(luò)的思想是無論節(jié)點(diǎn)屬于何種類型，都對節(jié)點(diǎn)在同一向量空間學(xué)習(xí)低維表示。LSHM算法提出了一種針對節(jié)點(diǎn)屬性的擴(kuò)展方式，這里對節(jié)點(diǎn)屬性和節(jié)點(diǎn)標(biāo)簽進(jìn)行區(qū)分，比如引文網(wǎng)絡(luò)中，文章的文本內(nèi)容是節(jié)點(diǎn)屬性，文章所屬的會議是節(jié)點(diǎn)標(biāo)簽。LSHM算法針對節(jié)點(diǎn)屬性的擴(kuò)展方式是把屬性也作為一種沒有標(biāo)簽的節(jié)點(diǎn)，比如文本屬性中的每一個(gè)詞語都對應(yīng)一個(gè)新的節(jié)點(diǎn)，圖3中的關(guān)鍵詞節(jié)點(diǎn)即論文節(jié)點(diǎn)的屬性，文章節(jié)點(diǎn)與詞語節(jié)點(diǎn)的權(quán)重可以定義為詞頻等指標(biāo)，這樣新的網(wǎng)絡(luò)依然可以用LSHM算法處理。

網(wǎng)絡(luò)信息傳播預(yù)測中，一類傳統(tǒng)的方法是首先從用戶的行為中發(fā)現(xiàn)傳播的隱式結(jié)構(gòu)[16]，直觀上說就是建立一個(gè)網(wǎng)絡(luò)，然后在網(wǎng)絡(luò)上模擬信息擴(kuò)散的過程。參考文獻(xiàn)[17]學(xué)習(xí)用戶節(jié)點(diǎn)在連續(xù)隱空間上的低維表示，把在網(wǎng)絡(luò)上的擴(kuò)散問題轉(zhuǎn)化為在隱空間上的擴(kuò)散問題。如圖4所示，每個(gè)用戶都對應(yīng)隱空間中的一個(gè)向量（也可以稱作位置、點(diǎn)）。

以上兩個(gè)基于最優(yōu)化的網(wǎng)絡(luò)表示學(xué)習(xí)算法，各自和特定的網(wǎng)絡(luò)分析任務(wù)有關(guān)，在設(shè)計(jì)優(yōu)化目標(biāo)函數(shù)時(shí)都使用hinge損失函數(shù)，求解方法通常是隨機(jī)梯度下降。

3.3 基于概率生成式模型的網(wǎng)絡(luò)表示學(xué)習(xí)

概率生成式算法是指用一個(gè)基于概率的生成過程去建模觀測數(shù)據(jù)的產(chǎn)生過程，經(jīng)典的PLSA、LDA都屬于概率生成式算法，本質(zhì)上都是概率圖模型?；诟怕噬墒剿惴ǖ木W(wǎng)絡(luò)表示學(xué)習(xí)，是指用一個(gè)采樣過程去建模網(wǎng)絡(luò)數(shù)據(jù)的生成過程。這些模型的求解方法通常是Gibbs 采樣、變分推斷和期望最大化算法等。

圖3 異構(gòu)網(wǎng)絡(luò)示例[15]

圖4 隱空間上的信息擴(kuò)散[17]

考慮到概率生成模型通常被用來建模文本數(shù)據(jù)，基于概率生成式算法的網(wǎng)絡(luò)表示學(xué)習(xí)通常也是以文本網(wǎng)絡(luò)作為輸入數(shù)據(jù)，文本網(wǎng)絡(luò)是指網(wǎng)絡(luò)中的每個(gè)節(jié)點(diǎn)都有對應(yīng)的文本屬性，典型的例子如：網(wǎng)頁超鏈接網(wǎng)絡(luò)中的每個(gè)網(wǎng)頁都有自己的文本內(nèi)容，在線社會網(wǎng)絡(luò)中每個(gè)用戶都有自己的文本屬性。當(dāng)前針對文本網(wǎng)絡(luò)的表示學(xué)習(xí)，通常學(xué)習(xí)到的都是文本節(jié)點(diǎn)在主題空間上的向量表示，下面介紹3個(gè)代表性的工作：Link-PLSA-LDA模型[18]、RTM模型[19]和PLANE模型[9]。

Link-PLSA-LDA模型是為學(xué)術(shù)論文引用網(wǎng)絡(luò)設(shè)計(jì)的，其圖模型如圖5所示，這個(gè)模型首先建模被引用論文集合的生成過程，然后建模引用論文集合的過程。

圖5 Link-PLSA-LDA的圖模型[18]

RTM模型建模文本的生成過程與傳統(tǒng)的主題模型LDA保持一致，不同之處在于RTM建模了鏈接關(guān)系的產(chǎn)生，這個(gè)模型的假設(shè)是如果兩個(gè)文本節(jié)點(diǎn)之間存在邊，那么它們在主題上的分布應(yīng)該更相似。PLANE和RTM的圖模型表示的對比如圖6所示。

PLANE模型對RTM模型進(jìn)行了擴(kuò)展，希望從可視化的角度學(xué)習(xí)主題和文本節(jié)點(diǎn)的低維表示。PLANE模型的生成過程希望同時(shí)建模兩個(gè)方面：一是表示學(xué)習(xí)，即對每個(gè)主題和每個(gè)文本節(jié)點(diǎn)都學(xué)習(xí)其在二維空間上的坐標(biāo)，二是傳統(tǒng)的主題建模。RTM模型不能直接得到文本節(jié)點(diǎn)在二維空間上的表示，故PLANE的作者用PE算法[20]對RTM模型學(xué)習(xí)到的文章話題表示進(jìn)行降維。

圖6 RTM和PLANE的圖模型對比[9]

如果只有網(wǎng)絡(luò)的結(jié)構(gòu)信息，而沒有節(jié)點(diǎn)各自的文本內(nèi)容，那么上面提到的3種算法都無法直接使用，因?yàn)檫@些算法需要學(xué)習(xí)節(jié)點(diǎn)在主題空間上的分布。解決這個(gè)問題的一種思路是學(xué)習(xí)節(jié)點(diǎn)在社團(tuán)層面上的分布[21,22]，這類算法假設(shè)每個(gè)節(jié)點(diǎn)在社團(tuán)空間上有一個(gè)分布，然后建模網(wǎng)絡(luò)中邊的產(chǎn)生。參考文獻(xiàn)[23]進(jìn)一步考慮了文本內(nèi)容，在學(xué)習(xí)節(jié)點(diǎn)在社團(tuán)空間上的分布的同時(shí)，可以學(xué)習(xí)社團(tuán)在主題空間上的分布。

3.4 基于力導(dǎo)向繪圖的網(wǎng)絡(luò)表示學(xué)習(xí)

力導(dǎo)向繪圖（force-directed graph drawing）是指一類在美學(xué)上讓人感到舒適的節(jié)點(diǎn)繪圖方法，通常是基于網(wǎng)絡(luò)中節(jié)點(diǎn)的相對位置，在節(jié)點(diǎn)之間和邊之間分配作用力，從而將網(wǎng)絡(luò)中的節(jié)點(diǎn)以某種方式放置在二維或者三維空間中，使得邊的長度盡量相等，同時(shí)盡可能減少交叉邊的數(shù)量[24]。

代表性的方法有FR-layout[25]和 KK-layout[26]，圖7給出了這兩種算法對同一網(wǎng)絡(luò)的可視化效果。這些方法將網(wǎng)絡(luò)視為一個(gè)彈簧系統(tǒng)，對節(jié)點(diǎn)位置進(jìn)行調(diào)整的最終目標(biāo)是希望這個(gè)系統(tǒng)的能量最小化。此類方法通常會被應(yīng)用到網(wǎng)絡(luò)可視化軟件中[27,28]，而與機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘等任務(wù)沒有直接的應(yīng)用關(guān)系。

3.5 基于深度學(xué)習(xí)的網(wǎng)絡(luò)表示學(xué)習(xí)

近年來，深度學(xué)習(xí)技術(shù)在語音處理、圖像識別、自然語音處理等領(lǐng)域掀起了巨大的熱潮。深度學(xué)習(xí)本質(zhì)上是一種特征學(xué)習(xí)方法[29]，其思想在于將原始數(shù)據(jù)通過非線性模型轉(zhuǎn)變?yōu)楦邔哟蔚奶卣鞅硎?，從而獲得更抽象的表達(dá)。與特征工程中需要人工設(shè)計(jì)特征不同，深度學(xué)習(xí)會自動從數(shù)據(jù)中學(xué)習(xí)出特征表示。

在自然語言處理領(lǐng)域，一個(gè)重要的研究方向是學(xué)習(xí)詞語、句子、文章等的分布式向量表示。針對網(wǎng)絡(luò)表示學(xué)習(xí)，2014年以來也出現(xiàn)了兩個(gè)具有代表性的基于深度學(xué)習(xí)的模型：Deepwalk[30]、LINE[31]。這兩個(gè)模型都是基于當(dāng)前最流行的神經(jīng)網(wǎng)絡(luò)語言模型word2vec[32～34]，下面首先簡要回顧神經(jīng)網(wǎng)絡(luò)語言模型的發(fā)展過程，然后介紹神經(jīng)網(wǎng)絡(luò)語言模型在網(wǎng)絡(luò)表示學(xué)習(xí)中的應(yīng)用。

學(xué)習(xí)分布式表示的思想最早來源于Hinton在1986年的工作[35]，利用神經(jīng)網(wǎng)絡(luò)語言模型學(xué)習(xí)詞語的詞向量則是Bengio在2001年提出的[36]。圖8是Bengio等人設(shè)計(jì)的一個(gè)4層神經(jīng)網(wǎng)絡(luò)語言模型（NNLM）。這個(gè)模型用一個(gè)長度為n（這里n=4）的窗口在語料中滑動，然后用前n-1個(gè)詞預(yù)測觀測到窗口內(nèi)的最后一個(gè)詞的概率。輸入層是窗口內(nèi)前n-1個(gè)詞的向量表示，投影層將輸入層的向量進(jìn)行拼接，隱藏層對投影層的輸出進(jìn)行了非線性轉(zhuǎn)換，輸出層是每個(gè)詞出現(xiàn)在下一個(gè)位置的概率。這個(gè)模型的求解方法用的是隨機(jī)梯度下降和反向傳播，其中詞向量僅是這個(gè)神經(jīng)網(wǎng)絡(luò)語言模型的副產(chǎn)品。

圖7 FR-layout 與KK-layout示意

圖8 Bengio提出的4層神經(jīng)網(wǎng)絡(luò)語言模型

Bengio提出的這種前向神經(jīng)網(wǎng)絡(luò)語言模型的復(fù)雜度很高，特別是輸出層Softmax計(jì)算的復(fù)雜度是和詞匯表大小同階。在多個(gè)后續(xù)工作中，都對Softmax計(jì)算進(jìn)行了替換或優(yōu)化。如參考文獻(xiàn)[37]提出的Hierarchical Softmax，這個(gè)算法將輸出層建模為一棵霍夫曼樹。參考文獻(xiàn)[38]中使用了hinge loss函數(shù)。Noise contrastive estimation[39]也是一種常用的降低NNLM時(shí)間復(fù)雜度的算法。

近年來最受關(guān)注的神經(jīng)網(wǎng)絡(luò)語言模型是Mikolov提出的word2vec，word2vec去掉了前向神經(jīng)語言網(wǎng)絡(luò)中的隱藏層，使得訓(xùn)練詞向量的速度大幅提高。如圖9所示，word2vec包括兩個(gè)不同的模型，一個(gè)是CBOW模型（continuous bag-ofwords mode），另一個(gè)是Skip-gram模型（continuous skip-gram model）。CBOW模型利用窗口中間詞的上下文預(yù)測中間的詞，Skip-gram反其道行之，用窗口中間的詞去預(yù)測這個(gè)詞的上下文。

在詞向量學(xué)習(xí)任務(wù)中，輸入是文本語料，在網(wǎng)絡(luò)表示學(xué)習(xí)任務(wù)中，輸入是一個(gè)網(wǎng)絡(luò)，看上去這兩個(gè)任務(wù)毫不相關(guān)，但Deepwalk算法的出現(xiàn)，解決了這兩個(gè)任務(wù)之間的鴻溝。Deepwalk算法的作者觀察到在文本語料中詞語出現(xiàn)的頻率服從冪律分布，而在無標(biāo)度網(wǎng)絡(luò)上進(jìn)行隨機(jī)游走的話，節(jié)點(diǎn)被訪問到的次數(shù)也服從冪律分布。因此Deepwalk把節(jié)點(diǎn)作為一種人造語言的單詞，通過在網(wǎng)絡(luò)中進(jìn)行隨機(jī)游走，獲得隨機(jī)游走路徑，把節(jié)點(diǎn)作為單詞，把隨機(jī)游走路徑作為句子，這樣獲得的數(shù)據(jù)就可以直接作為word2vec算法的輸入以訓(xùn)練節(jié)點(diǎn)的向量表示。這是一個(gè)非常具有創(chuàng)造性的想法。圖10給出了Deepwalk模型的框架示意。

圖9 word2vec的兩種模型[37]

圖10 Deepwalk模型框架

Deepwalk算法被證明等價(jià)于分解矩陣M，其中，M的第i行第j列的元素是節(jié)點(diǎn)i在固定步數(shù)內(nèi)隨機(jī)游走到節(jié)點(diǎn)j的次數(shù)[40]。同樣，word2vec也被證明等價(jià)于分解PMI矩陣[41]或者詞共現(xiàn)矩陣[42]。在矩陣分解模型框架下，Yang等人提出了在Deepwalk中考慮節(jié)點(diǎn)的文本信息的算法TADW模型[43]。Deepwalk和TADW的矩陣分解示意如圖11所示，其中矩陣M都可以由網(wǎng)絡(luò)的鄰接矩陣導(dǎo)出。

Deepwalk中矩陣M被分解為兩個(gè)矩陣的乘積，這兩個(gè)矩陣進(jìn)行拼接后作為節(jié)點(diǎn)最終的向量表示，所用的求解方法是正則化的低秩矩陣分解[44]。TADW將矩陣M分解為3個(gè)矩陣的乘積，其中，矩陣T是節(jié)點(diǎn)的文本特征矩陣，通過對TF-IDF矩陣進(jìn)行奇異值分解降維得到的，計(jì)算H和T的乘積，把得到的矩陣和W拼接后得到的矩陣被作為節(jié)點(diǎn)的特征矩陣。

圖11 Deepwalk和TADW的矩陣分解示意[43]

Deepwalk在網(wǎng)絡(luò)中基于隨機(jī)游走獲得訓(xùn)練數(shù)據(jù)，因此針對網(wǎng)絡(luò)本身的結(jié)構(gòu)沒有一個(gè)明確的優(yōu)化目標(biāo)函數(shù)。參考文獻(xiàn)[32]提出的LINE算法，認(rèn)為網(wǎng)絡(luò)中存在兩種接近度，一種是first-order接近度，是指如果網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)之間存在邊，那么它們之間的first-order接近度是這條邊的權(quán)重，沒有邊相連則接近度等于0，這可以看作“物以類聚，人以群分”的一種體現(xiàn)。然后是second-order接近度，是指如果網(wǎng)絡(luò)中兩個(gè)節(jié)點(diǎn)有共同好友，那么它們之間的second-order接近度是它們好友集合的相似度，沒有共同好友則接近度等于0。以圖12為例，節(jié)點(diǎn)6和節(jié)點(diǎn)7擁有較高的firstorder接近度，節(jié)點(diǎn)5和節(jié)點(diǎn)6擁有較高的second-order接近度。LINE算法對兩種接近度分別設(shè)計(jì)了一個(gè)優(yōu)化目標(biāo)函數(shù)，然后分別訓(xùn)練出一個(gè)向量表示，最后以兩種向量的拼接作為節(jié)點(diǎn)最終的向量表示。Deepwalk算法只考慮了second-order接近度，參考文獻(xiàn)[31]中的實(shí)驗(yàn)表明LINE算法在節(jié)點(diǎn)標(biāo)簽預(yù)測任務(wù)上要優(yōu)于Deepwalk算法。參考文獻(xiàn)[45]基于LINE算法針對文檔標(biāo)簽預(yù)測任務(wù)提出了PTE算法，將部分標(biāo)簽已知的文檔集合數(shù)據(jù)轉(zhuǎn)換為了一個(gè)包括詞語、文檔、標(biāo)簽3種節(jié)點(diǎn)的異構(gòu)網(wǎng)絡(luò)，然后學(xué)習(xí)各種節(jié)點(diǎn)的向量表示，提高了文檔標(biāo)簽預(yù)測任務(wù)的效果。

圖12 LINE中接近度的說明[31]

表1 網(wǎng)絡(luò)數(shù)據(jù)示例

4 評測方法和應(yīng)用場景

可以從定量和定性兩個(gè)角度評測網(wǎng)絡(luò)表示學(xué)習(xí)算法的性能，為此需要結(jié)合具體的應(yīng)用場景。在當(dāng)前的網(wǎng)絡(luò)表示學(xué)習(xí)的相關(guān)工作中，最常見的定量評測方法是節(jié)點(diǎn)標(biāo)簽預(yù)測任務(wù)，表1列舉了一些常見的網(wǎng)絡(luò)數(shù)據(jù)及其對應(yīng)的節(jié)點(diǎn)和標(biāo)簽。

在標(biāo)簽預(yù)測任務(wù)中，網(wǎng)絡(luò)里部分節(jié)點(diǎn)的標(biāo)簽是已知的，目的是推斷出其他節(jié)點(diǎn)的標(biāo)簽。通常的過程是首先學(xué)習(xí)出每個(gè)節(jié)點(diǎn)的向量表示，然后利用已知標(biāo)簽的節(jié)點(diǎn)訓(xùn)練分類器（常用的分類器有l(wèi)ogistics regression和SVM等），然后以其余節(jié)點(diǎn)的向量表示作為輸入，預(yù)測它們的標(biāo)簽。如果在網(wǎng)絡(luò)表示學(xué)習(xí)的過程中利用到了標(biāo)簽信息，通?？梢蕴岣邩?biāo)簽預(yù)測任務(wù)的性能[15,45]，即半監(jiān)督的網(wǎng)絡(luò)表示學(xué)習(xí)可能會優(yōu)于無監(jiān)督的網(wǎng)絡(luò)表示學(xué)習(xí)，這是因?yàn)榍罢邔W(xué)習(xí)到的網(wǎng)絡(luò)向量表示是和預(yù)測任務(wù)相關(guān)的。

常用的定性評測方法則是對網(wǎng)絡(luò)進(jìn)行可視化展示[6,9,31,45]，具體做法是對節(jié)點(diǎn)的向量表示進(jìn)行降維，從而將網(wǎng)絡(luò)中的節(jié)點(diǎn)都映射到二維空間上的一個(gè)點(diǎn)。通常需要節(jié)點(diǎn)標(biāo)簽信息，在可視化展示中，標(biāo)簽相同的節(jié)點(diǎn)之間距離應(yīng)該盡可能小。常用的高維向量降維工具有t-SNE[45]、PE[20]、PCA等。參考文獻(xiàn)[31]給出了利用t-SNE對一個(gè)論文合作網(wǎng)絡(luò)進(jìn)行可視化的樣例[31]，其中每一個(gè)節(jié)點(diǎn)代表一個(gè)用戶，每一種顏色代表一個(gè)研究領(lǐng)域，同一顏色的節(jié)點(diǎn)越集中則表明網(wǎng)絡(luò)表示學(xué)習(xí)算法的性能越好。

網(wǎng)絡(luò)表示學(xué)習(xí)中一個(gè)重要的參數(shù)是向量空間的維度k，在實(shí)驗(yàn)環(huán)節(jié)需要調(diào)整參數(shù)k的設(shè)置。k的值過小，則學(xué)習(xí)到的節(jié)點(diǎn)向量的表示能力不足；k的值過大，算法的計(jì)算量會大大增加。在概率生成式算法中，k就是主題或者社團(tuán)的個(gè)數(shù)。在基于深度學(xué)習(xí)的網(wǎng)絡(luò)表示學(xué)習(xí)算法中，k的取值一般是3位數(shù)。

5 結(jié)束語

本文總結(jié)了網(wǎng)絡(luò)表示學(xué)習(xí)的主要方法，并特別介紹了基于深度學(xué)習(xí)的網(wǎng)絡(luò)表示學(xué)習(xí)的最新進(jìn)展。深度學(xué)習(xí)在社會網(wǎng)絡(luò)分析領(lǐng)域的應(yīng)用還處于方興未艾的探索階段，但已有工作的結(jié)果是令人感到鼓舞的，基于深度學(xué)習(xí)的網(wǎng)絡(luò)表示學(xué)習(xí)算法（如Deepwalk、LINE）在網(wǎng)絡(luò)節(jié)點(diǎn)標(biāo)簽預(yù)測任務(wù)上的表現(xiàn)，已經(jīng)超越了傳統(tǒng)的基于譜的方法[13]、基于最優(yōu)化的方法[46]。然而，這兩個(gè)算法缺少在其他社會網(wǎng)絡(luò)分析任務(wù)中的應(yīng)用案例，普適性不足?；谝陨戏治?，本文設(shè)想了未來兩個(gè)值得探索的研究方向。

雖然標(biāo)簽預(yù)測任務(wù)十分常見，但是SNA領(lǐng)域還有很多其他重要的任務(wù)，比如影響力最大化、鏈接預(yù)測、社團(tuán)檢測等，這些任務(wù)和標(biāo)簽預(yù)測任務(wù)有著很大的不同：一方面，可以考慮針對特定的社會網(wǎng)絡(luò)分析任務(wù)，設(shè)計(jì)網(wǎng)絡(luò)表示學(xué)習(xí)模型；另一方面，無監(jiān)督的網(wǎng)絡(luò)表示學(xué)習(xí)算法是否對多種任務(wù)具有普適性也值得探究。

現(xiàn)實(shí)中存在著大量的異構(gòu)網(wǎng)絡(luò)，而且節(jié)點(diǎn)都對應(yīng)著豐富的標(biāo)簽、文本、圖像、語音等多媒體信息。如何使基于深度學(xué)習(xí)的網(wǎng)絡(luò)表示學(xué)習(xí)算法可以同時(shí)利用網(wǎng)絡(luò)的結(jié)構(gòu)和節(jié)點(diǎn)自身的特征信息，是一個(gè)重要的問題。這涉及如何設(shè)計(jì)網(wǎng)絡(luò)結(jié)構(gòu)，如何從網(wǎng)絡(luò)中采樣節(jié)點(diǎn)對等細(xì)節(jié)。TADW算法通過和Deepwalk等價(jià)的矩陣分解方法，在同構(gòu)網(wǎng)絡(luò)的表示學(xué)習(xí)中融入了節(jié)點(diǎn)自身的文本信息，這也為從矩陣分解的視角看待網(wǎng)絡(luò)表示學(xué)習(xí)的擴(kuò)展提供了有益的啟示。

參考文獻(xiàn)

[1] Mairal J, Ponce J, Sapiro G,et al. Supervised dictionary learning. Proceedings of the 2009 Conference on Neural Information Processing Systems, Vancouver, Canada, 2009:1033～1040

[2] Roweis S T, Saul L K. Nonlinear dimensionality reduction by locally linear embedding. Science, 2000, 290(5): 2323～2326

[3] Hyv?rinen A, Oja E. Independent component analysis: algorithms and applications. Neural Networks, 2000, 13(4～5): 411～430

[4] Lee H, Battle A, Rain R,et al. Efficient sparse coding algorithms. Proceedings of the 2006 Conference on Neural Information Processing Systems. Vancouver, Canada, 2006:801～808

[5] Bengio Y, Courville A, Vincent P. Representation learning: a review and new perspectives. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35(8): 1798～1828

[6] Chen M, Yang Q, Tang X O. Directed graph embedding. Proceedings of the 20th International Joint Conference on Artificial Intelligence (IJCAI), Hyderabad, India, 2007:2707～2712

[7] Kannan R,Vempala S. Spectral algorithms. Theoretical Computer Science, 2009, 4(3～4):157～288

[8] Brand M, Huang K. A unifying theorem for spectral embedding and clustering. Proceedings of the 9th International Conference on Workshop on Artificial Intelligence and Statistics, Florida, USA, 2003

[9] Le T, Lauw H W. Probabilistic latent document network embedding. Proceedings of 2014 IEEE InternationalConference on Data Mining (ICDM), Shenzhen, China, 2014:270～279

[10] Wojciech C, Brooks M J. A note on the locally linear embedding algorithm. International Journal of Pattern Recognition and Artificial Intelligence, 2009, 23(8): 1739～1752

[11] Belkin M, Niyogi P. Laplacian eigenmaps and spectral techniques for embedding and clustering. Proceedings of Annual Conference on Neural Information Processing Systems(NIPS), Cambridge, UK, 2001:585～591

[12] Tang L, Liu H. Relational learning via latent social dimensions. Proceedings of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,Paris, France, 2009:817～826

[13] Newman M. Modularity and community structure in networks. Proceedings of the National Academy of Sciences, 2006, 103(23): 8577～8582

[14] Zhou D Y, Huang J Y, Sch?lkopf B. Learning from labeled and unlabeled data on a directed graph. Proceedings of the 22nd International Conference on Machine Learning, Bonn, Germany, 2005: 1036～1043

[15] Jacob Y, Denoyer L, Gallinari P. Learning latent representations of nodes for classifying in heterogeneous social networks. Proceedings of the 7th ACM International Conference on Web Search and Data Mining, New York, USA, 2014: 373～382

[16] Yang J, Leskovec J. Modeling information diffusion in implicit networks. Proceedings of 2010 IEEE 10th International Conference on Data Mining (ICDM), Sydney, Australia, 2010: 599～608

[17] Bourigault S, Lagnier C, Lamprier S,et al. Learning social network embeddings for predicting information diffusion. Proceedings of the 7th ACM International Conference on Web Search and Data Mining, New York, USA, 2014: 393～402

[18] Nallapati R, Ahmed A, Xing E,et al. Joint latent topic models for text and citations. Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Las Vegas, USA, 2008: 542～550

[19] Chang J, Blei D. Relational topic models for document networks. Proceedings of International Conference on Artificial Intelligence and Statistics, Clearwater Beach, Florida, USA, 2009: 81～88

[20] Iwata T, Saito K, Ueda N,et al. Parametric embedding for class visualization. Neural Computation, 2007, 19(9): 2536～2556

[21] Gopalan P, Blei D. Efficient discovery of overlapping communities in massive networks. Proceedings of the National Academy of Sciences, 2013,110(36): 14534～14539

[22] Gopalan P, Mimno D, Gerrish S,et al. Scalable inference of overlapping communities. Proceedings of the 2012 Conference on Neural Information Processing Systems, Lake Tahoe, USA, 2012: 2249～2257

[23] Hu Z T, Yao J J, Cui B,et al. Community level diffusion extraction. Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data, Melbourne, Victoria, Australia, 2015: 1555～1569

[24] Kobourov S. Spring embedders and force directed graph drawing algorithms. arXiv Preprint 2012, arXiv:1201.3011,2012

[25] Fruchterman T, Reingold E. Graph drawing by force-directed placement. Software-Practice & Experience, 1991, 21(11): 1129～1164

[26] Kamada T, Kawai S. An algorithm for drawing general undirected graphs. Information Processing Letters, 1989, 31(1): 7～15

[27] Bastian M, Heymann S, Jacomy M. Gephi: an open source software for exploring and manipulating networks. Proceedings of the 3rd International Conference on Weblogs and Social Media, San Jose, California, USA, 2009: 361～362

[28] Ellson J, Gansner E, Koutsofios L,et al. Graphviz-open source graph drawing tools. Graph Drawing. Berlin Heidelberg: Springer, 2002

[29] Bengio Y, Goodfellow I, Courville A. Deep Learning, 2015

[30] Perozzi B, Al-Rfou R, Skiena S. Deepwalk: online learning of social representations. Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. New York, USA, 2014: 701～710

[31] Tang J, Qu M, Wang M Z,et al. LINE: large-scale information network embedding. Proceedings of the 24th International Conference on World Wide Web, Florence, Italy, 2015: 1067～1077

[32] Mikolov T, Sutskever I, Chen K,et al. Distributed representations of words and phrases and their compositionality. Proceedings of the 2013 Conference onNeural Information Processing Systems, Lake Tahoe, USA, 2013: 3111～3119

[33] Mikolov T, Chen K, Corrado G,et al. Efficient estimation of word representations in vector space. arXiv Preprint arXiv:1301.3781, 2013

[34] Mikolov T, Yih W T, Zweig G. Linguistic regularities in continuous space word representations. Proceedings of the 2013 Conference on NAACL and SEM, Atlanta, USA, 2013: 746～751

[35] Hinton G E. Learning distributed representations of concepts. Proceedings of the Eighth Annual Conference on the Cognitive Science Society, Amherst, Mass, USA, 1986: 1～12

[36] Bengio Y, Ducharme R, Vincent P,et al. A neural probabilistic language model. Journal of Machine Learning Research, 2003(3): 1137～1155

[37] Morin F, Bengio Y. Hierarchical probabilistic neural network language model. Proceedings of the 10th International Workshop Conference on Artificial Intelligence and Statistics,Barbados, 2005: 246～252

[38] Collober R, Weston J. A unified architecture for natural language processing: deep neural networks with multitask learning. Proceedings of the 25th International Conference on Machine Learning, Helsinki, Finland, 2008: 160～167

[39] Gutmann M, Hyv?rinen A. Noisecontrastive estimation: a new estimation principle for unnormalized statistical models. Proceedings on International Conference on Artificial Intelligence and Statistics, Sardinia, Italy, 2010: 297～304

[40] Yang C, Liu Z Y. Comprehend deepwalk as matrix factorization. arXiv Preprint arXiv:1501.00358, 2015

[41] Goldberg Y, Levy O. Word2vec explained: deriving Mikolov et al.'s negativesampling word-embedding method. arXiv Preprint arXiv:1402.3722, 2014

[42] Li Y T, Xu L L, Tian F,et al. Word embedding revisited: anew representation learning and explicit matrix factorization perspective. Proceedings of the 24th International Joint Conference on Artificial Intelligence,Buenos Aires, Argentina, 2015: 3650～3656

[43] Yang C, Liu Z Y, Zhao D L,et al. Network representation learning with rich text information. Proceedings of the 24th International Joint Conference on Artificial Intelligence,Buenos Aires, Argentina, 2015:2111～2117

[44] Yu H F, Jain P, Kar P,et al. Large-scale multi-label learning with missing labels. arXiv Preprint arXiv:1307.5101, 2013

[45] Tang J, Qu M, Mei Q Z. PTE: predictive text embedding through large-scale heterogeneous text networks. Proceedings of the 21st ACM SIGKDD Conference on knowledge Discovery and Data Mining, Sydney, Australia, 2015

[46] Ahmed A, Shervashidze N, Narayanamurthy S,et al. Distributed large-scale natural graph factorization. Proceedings of the 22nd International Conference on World Wide Web, Rio, Brazil, 2013: 37～48

陳維政，男，北京大學(xué)博士生，主要研究方向?yàn)闄C(jī)器學(xué)習(xí)和社會網(wǎng)絡(luò)分析。

張巖，男，北京大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)樾畔z索、文本分析和數(shù)據(jù)挖掘。

李曉明，男，北京大學(xué)教授、博士生導(dǎo)師，主要研究方向?yàn)樗阉饕?、網(wǎng)絡(luò)數(shù)據(jù)挖掘和并行與分布式系統(tǒng)。

Chen W Z, Zhang Y, Li X M. Network representation learning. Big Data Research, 2015025

Network Representation Learning

Chen Weizheng, Zhang Yan, Li Xiaoming
School of Electronic Engineering and Computer Science, Peking University, Beijing 100871, China

Along with the constant growth of massive online social networks such as Facebook, Twitter, Weixin and Weibo, a tremendous amount of network data sets are generated. How to represent the data is an important aspect when we apply machine learning techniques to analyze network data sets. Firstly, the research background was introduced and the definitions of NRL (network representation learning) were related. According to the categories of different algorithms, five kinds of primary NRL algorithms were introduced. Particularly, a detailed introduction to NRL algorithms based deep learning techniques was given emphatically. Then the evaluation methods and application scenarios of NRL were discussed. Finally, the research prospect of NRL in the future was discussed.

network, representation learning, deep learning

10.11959/j.issn.2096-0271.2015025

2015-08-20

國家重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃（“973”計(jì)劃）基金資助項(xiàng)目（No.2014CB340400），國家自然科學(xué)基金資助項(xiàng)目（No.61272340, No.61472013, No.61532001）

陳維政，張巖，李曉明. 網(wǎng)絡(luò)表示學(xué)習(xí). 大數(shù)據(jù), 2015025

Foundations Items:The National Basic Research Program of China (973 Program)(No.2014CB340400), The National Natural Science Foundation of China (No.61272340, No.61472013, No.61532001)