張 霞，陳維政，謝正茂，閆宏飛

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

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

張 霞+，陳維政，謝正茂，閆宏飛

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

網(wǎng)絡(luò)表示學(xué)習(xí)是一個經(jīng)典的學(xué)習(xí)問題，其目的是將高維的網(wǎng)絡(luò)在低維度的向量空間進(jìn)行表示。目前大多數(shù)的網(wǎng)絡(luò)表示學(xué)習(xí)方法都是無監(jiān)督的，忽視了標(biāo)簽信息。受LINE（large-scale information network embed-ding）算法啟發(fā)而提出了一種半監(jiān)督的學(xué)習(xí)算法TLINE。TLINE是一種直推式表示學(xué)習(xí)算法，其通過優(yōu)化LINE部分的目標(biāo)函數(shù)來保留網(wǎng)絡(luò)的局部特性。而標(biāo)簽信息部分，則使用線性支持向量機(jī)（support vector machine）來提高帶標(biāo)簽結(jié)點的區(qū)分度。通過邊采樣、負(fù)采樣和異步隨機(jī)梯度下降來降低算法的復(fù)雜度，從而使TLINE算法可以處理大型的網(wǎng)絡(luò)。最后，在論文引用數(shù)據(jù)集CiteSeer和共同作者數(shù)據(jù)集DBLP上進(jìn)行了實驗，實驗結(jié)果表明，TLINE算法明顯優(yōu)于經(jīng)典的無監(jiān)督網(wǎng)絡(luò)表示學(xué)習(xí)算法DeepWalk和LINE。

直推式；網(wǎng)絡(luò)表示學(xué)習(xí)；結(jié)點分類

1 引言

隨著信息技術(shù)的迅速發(fā)展和互聯(lián)網(wǎng)的普及，現(xiàn)代社會進(jìn)入了一個信息爆炸的時代，生活中處處充滿著信息。信息之間的關(guān)聯(lián)形成了各種各樣的信息網(wǎng)絡(luò)，例如社交媒體的各種交互形成的社交網(wǎng)絡(luò)，學(xué)術(shù)界中論文的引用形成的論文引用網(wǎng)絡(luò)，還有大眾熟悉的萬維網(wǎng)（World Wide Web）。網(wǎng)絡(luò)的基本組成單位是結(jié)點，一個結(jié)點可以是一個用戶、一篇文章，或者是一個網(wǎng)頁，網(wǎng)絡(luò)的邊表示不同結(jié)點的關(guān)系，比如用戶間的社交關(guān)系、論文間的引用關(guān)系以及網(wǎng)頁間的鏈接關(guān)系。網(wǎng)絡(luò)包含的大量有價值的信息有待挖掘。

網(wǎng)絡(luò)表示學(xué)習(xí)（network embedding learning）是網(wǎng)絡(luò)分析和學(xué)習(xí)的非常重要的一步，它依據(jù)相關(guān)優(yōu)化目標(biāo)，將規(guī)模大、維度高的網(wǎng)絡(luò)映射到一個低維度的空間，用低維度的向量來表示網(wǎng)絡(luò)中的結(jié)點，同時還盡可能地保存原始數(shù)據(jù)的網(wǎng)絡(luò)局部特性和全局特性。將網(wǎng)絡(luò)用低維向量表示之后，就可以進(jìn)行各種機(jī)器學(xué)習(xí)任務(wù)，諸如可視化[1]、結(jié)點分類[2]、鏈接預(yù)測[3]等。

本文主要關(guān)注的是網(wǎng)絡(luò)結(jié)點分類任務(wù)。傳統(tǒng)的做法首先將網(wǎng)絡(luò)進(jìn)行表示學(xué)習(xí)，再用分類算法諸如支持向量機(jī)（support vector machine，SVM）[4]對表示學(xué)習(xí)出的向量進(jìn)行分類，這是一種無監(jiān)督學(xué)習(xí)的做法。直觀上來看，標(biāo)簽信息是一種網(wǎng)絡(luò)特性，不應(yīng)該獨立于網(wǎng)絡(luò)存在。結(jié)點所帶的標(biāo)簽，反映了結(jié)點的不同特質(zhì)，在某種程度上也反映了結(jié)點間的關(guān)系。如果在網(wǎng)絡(luò)進(jìn)行表示學(xué)習(xí)的同時，也運用到結(jié)點信息，那么對表示結(jié)點的真實性質(zhì)將會大有裨益。

網(wǎng)絡(luò)的表示學(xué)習(xí)是一項很有挑戰(zhàn)性的研究。一方面，因為真實網(wǎng)絡(luò)的數(shù)據(jù)量非常龐大，一個好的表示學(xué)習(xí)算法，必須能夠高效處理大規(guī)模的網(wǎng)絡(luò)?，F(xiàn)存的很多網(wǎng)絡(luò)表示學(xué)習(xí)算法[1,5-6]，在小型網(wǎng)絡(luò)中效果很好，但由于高計算復(fù)雜度，它們難以處理大規(guī)模的網(wǎng)絡(luò)。另一方面，如何將結(jié)點的標(biāo)簽信息加入到表示學(xué)習(xí)的過程中，也是研究的難點。

本文一方面受LINE（large-scale information network embedding）算法的啟發(fā)，建立目標(biāo)函數(shù)，通過優(yōu)化目標(biāo)函數(shù)，保留網(wǎng)絡(luò)結(jié)構(gòu)的局部特性。優(yōu)化過程中，通過使用異步隨機(jī)梯度下降（asynchronous stochastic gradient descent,ASGD）、邊采樣（edge sampling）和負(fù)采樣（negative sampling）使得算法復(fù)雜度大大降低，能夠以很小的時間代價對大型網(wǎng)絡(luò)進(jìn)行表示學(xué)習(xí)。另一方面，使用SVM作為分類訓(xùn)練的分類器，在采樣邊的同時，對邊上帶標(biāo)簽的結(jié)點進(jìn)行訓(xùn)練，使得該結(jié)點的表示學(xué)習(xí)向量帶上分類信息。

最后在CiteSeer和DBLP數(shù)據(jù)集上進(jìn)行實驗，并將TLINE算法同目前備受關(guān)注的無監(jiān)督算法以及原LINE算法進(jìn)行比較。實驗結(jié)果表明，TLINE算法在對網(wǎng)絡(luò)結(jié)點進(jìn)行表示學(xué)習(xí)和分類的任務(wù)上，效果顯著優(yōu)于其他比較方法，體現(xiàn)了直推式學(xué)習(xí)的優(yōu)越性。同時，對TLINE算法做了參數(shù)（SVM正則化項系數(shù)、LINE和SVM平衡參數(shù)）敏感度實驗，并找到一組通用參數(shù)。

2 相關(guān)工作

網(wǎng)絡(luò)表示學(xué)習(xí)是在低維度的向量表示空間內(nèi)，通過對網(wǎng)絡(luò)結(jié)構(gòu)特性分析，對網(wǎng)絡(luò)結(jié)點進(jìn)行表示。表示學(xué)習(xí)的意義是緩解數(shù)據(jù)稀疏，建立統(tǒng)一的表示空間，實現(xiàn)知識的遷移。

傳統(tǒng)的方法，諸如PCA（principal component anal-ysis）和SVD（singular value decomposition），目標(biāo)都是為了能在低維度空間中盡可能地保留數(shù)據(jù)集的累計方差。一些著名的表示學(xué)習(xí)方法，諸如MDS（multidimensional scaling）[5]、LLE（locally linear embedding）[7]、Laplacian Eigenmap[8]和DGE（directed graph embedding）[9]都是基于譜因子分解的算法。傳統(tǒng)的方法還有一類是基于概率圖模型的表示方法，代表性的算法有Link-PLSA-LDA[10]、RTM（relational topic models）[11]和PLANE（probabilistic latent document network embedding）[12]。然而由于高計算復(fù)雜度，使得這一系列算法不能應(yīng)用于大規(guī)模網(wǎng)絡(luò)。

近來，詞向量表示學(xué)習(xí)方法在自然語言處理領(lǐng)域受到廣泛關(guān)注，代表算法有Skip-Gram[13]等。受此啟發(fā)，研究人員提出了一種新的網(wǎng)絡(luò)表示學(xué)習(xí)算法，通過對詞向量的學(xué)習(xí)來表示學(xué)習(xí)網(wǎng)絡(luò)。在詞向量學(xué)習(xí)任務(wù)中輸入的是文本語料，而在網(wǎng)絡(luò)表示學(xué)習(xí)任務(wù)中輸入的則是一個網(wǎng)絡(luò)，看上去這是兩個毫不相關(guān)的任務(wù)。DeepWalk[14]的出現(xiàn)將這兩者聯(lián)系起來。觀察到在文本語料中，詞語出現(xiàn)的頻率服從冪律分布，而如果在網(wǎng)絡(luò)上進(jìn)行隨機(jī)游走，結(jié)點被訪問到的次數(shù)也服從冪律分布。因此DeepWalk把結(jié)點作為一種人造語言的單詞，通過在網(wǎng)絡(luò)中進(jìn)行隨機(jī)游走獲得隨機(jī)游走路徑。把結(jié)點作為單詞，把隨機(jī)游走路徑作為句子，這樣獲得的數(shù)據(jù)就可以直接作為word2vec算法的輸入以訓(xùn)練結(jié)點的向量表示。

受到文本表示學(xué)習(xí)的啟發(fā)而產(chǎn)生的DeepWalk，開拓了網(wǎng)絡(luò)表示學(xué)習(xí)的新思路。由于對網(wǎng)絡(luò)缺少整體的把握，DeepWalk依據(jù)隨機(jī)游走而獲得的訓(xùn)練數(shù)據(jù)，會損失掉部分的網(wǎng)絡(luò)結(jié)構(gòu)信息，因此訓(xùn)練出來的效果還是不夠理想。唐建等人提出的LINE[15]，則直接建模了網(wǎng)絡(luò)的一階和二階的結(jié)構(gòu)信息。

然而，DeepWalk和LINE都是無監(jiān)督模型，未能對結(jié)點標(biāo)簽信息進(jìn)行有效利用。事實上，標(biāo)簽信息在網(wǎng)絡(luò)數(shù)據(jù)中十分常見，不含標(biāo)簽信息的模型對于表示學(xué)習(xí)結(jié)果的區(qū)分度十分有限。為了對標(biāo)簽信息進(jìn)行有效利用，半監(jiān)督學(xué)習(xí)方法應(yīng)運而生。LSHM（latent space heterogeneous model）[16]和MMDW（maxmargin DeepWalk）[17]即是其中兩種代表算法。LSHM通過學(xué)習(xí)結(jié)點的向量表示和訓(xùn)練標(biāo)簽的分類函數(shù)來學(xué)習(xí)模型。該算法一方面考慮到網(wǎng)絡(luò)結(jié)構(gòu)邊的特性，認(rèn)為相鄰結(jié)點的標(biāo)簽盡可能地相似，另一方面考慮了分類函數(shù)對已知標(biāo)簽的預(yù)測能力。MMDW采用一種基于矩陣分解的算法對網(wǎng)絡(luò)結(jié)構(gòu)進(jìn)行建模，這導(dǎo)致了極大的空間復(fù)雜度，因此MMDW依然不適用于規(guī)模較大的網(wǎng)絡(luò)。

通過對LINE和SVM的權(quán)衡，本文提出的TLINE算法既對結(jié)點的標(biāo)簽信息進(jìn)行了充分利用，又同時適用于大規(guī)模的網(wǎng)絡(luò)表示學(xué)習(xí)的任務(wù)。

3 模型與實現(xiàn)

3.1 大規(guī)模網(wǎng)絡(luò)表示學(xué)習(xí)

兩個結(jié)點之間的邊所表示的是網(wǎng)絡(luò)的局部特性，邊的權(quán)重常常預(yù)示著兩個結(jié)點在真實世界的相似度。比如說，在社交網(wǎng)絡(luò)中，兩個人如果是朋友，他們極有可能有著相似的興趣愛好。再比如說，在萬維網(wǎng)中指向彼此的鏈接往往有著相似的話題。唐建等人在LINE[15]論文中對局部特性進(jìn)行如下表示，對于每一個無向邊(i,j)，定義關(guān)于點vi和vj的聯(lián)合分布：

ui∈Rd是結(jié)點vi在d維空間的表示向量。此時再定義經(jīng)驗分布函數(shù)如下：

為了保存網(wǎng)絡(luò)的局部特性，需要優(yōu)化以下函數(shù)：

省略一些常數(shù)項，可以得到：

這里，σ指代的是sigmoid函數(shù)。Oline通過最小化目標(biāo)函數(shù)，可以得到|v|個結(jié)點的對于網(wǎng)絡(luò)局部特性學(xué)習(xí)得出的表示學(xué)習(xí)向量{ui}i=1…|v|。

3.2 基于SVM的分類

對于一個二元分類問題，線性分類器是對于輸入空間中將實例劃分為正負(fù)兩類的分離超平面：在超平面的一側(cè)的所有點都被分類為“是”，另一側(cè)的則為“否”。線性支持向量機(jī)在二分類問題上可以轉(zhuǎn)化為如下的最優(yōu)化問題：

二分類問題只是多分類問題中的一個特例，而多分類問題更為普遍。也可以把上式擴(kuò)展到多分類的問題上，得到新的目標(biāo)函數(shù):

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

給定一個網(wǎng)絡(luò)圖結(jié)構(gòu)，圖上的部分結(jié)點帶有分類信息，任務(wù)是要能夠?qū)€沒有進(jìn)行分類的結(jié)點進(jìn)行分類。傳統(tǒng)的表示學(xué)習(xí)和分類算法，分為兩步進(jìn)行，如圖1所示。首先將每個結(jié)點映射到低維空間，即表示學(xué)習(xí)，然后再在這低維空間中，將帶分類信息的結(jié)點作為訓(xùn)練集，剩下的作為測試集。用訓(xùn)練集的表示學(xué)習(xí)向量來訓(xùn)練分類器，最后對測試集進(jìn)行分類判定輸出。

直推式表示學(xué)習(xí)是一種半監(jiān)督學(xué)習(xí)算法。在學(xué)習(xí)過程中，使用較少的有標(biāo)簽樣本和較多的無標(biāo)簽樣本進(jìn)行學(xué)習(xí)。其與傳統(tǒng)的學(xué)習(xí)分類算法不同之處在于，在這種混合樣本的學(xué)習(xí)過程中，測試集的樣本分布信息從標(biāo)簽樣本轉(zhuǎn)移到最終的分類器和無標(biāo)簽樣本中。如圖2中，圖的表示學(xué)習(xí)和分類器的訓(xùn)練是同時進(jìn)行的，這樣的學(xué)習(xí)方式，使得在學(xué)習(xí)結(jié)點的表示向量的過程中，將結(jié)點的分類信息也涵蓋進(jìn)來。表示學(xué)習(xí)和分類的過程相互影響，使得結(jié)點的分類信息變成了圖表示學(xué)習(xí)結(jié)果的一部分，而結(jié)點的表示學(xué)習(xí)向量也同樣影響著分類器的參數(shù)。這樣一來，結(jié)點的表示學(xué)習(xí)結(jié)果含義更為豐富，情況也更有針對性，有助于最后對無標(biāo)簽結(jié)點的分類。

Fig.1 Traditional unsupervised embedding learning and classification圖1 傳統(tǒng)無監(jiān)督表示學(xué)習(xí)和分類

Fig.2 Transductive embedding learning and classification圖2 直推式表示學(xué)習(xí)和分類

為了更好地表示網(wǎng)絡(luò)結(jié)構(gòu)的局部特性，同時提高分類的效果，本文把在網(wǎng)絡(luò)表示學(xué)習(xí)中效果顯著的LINE算法和著名的支持向量機(jī)分類算法結(jié)合起來，用直推式表示學(xué)習(xí)的方式對網(wǎng)絡(luò)進(jìn)行表示學(xué)習(xí)，即是說：

β是平衡LINE和SVM的比例參數(shù)。

對Oline和Osvm，采用負(fù)采樣優(yōu)化，代入上式，最后得到的TLINE目標(biāo)函數(shù)如下：

本文使用異步隨機(jī)梯度下降算法來最優(yōu)化目標(biāo)函數(shù)。隨機(jī)梯度下降是最小化損失函數(shù)的一種常用方法，其每次優(yōu)化對應(yīng)的是訓(xùn)練集中每個樣本，與之相對的批量梯度下降，對應(yīng)的則是所有樣本。雖然隨機(jī)梯度下降算法中，并不是每次迭代損失函數(shù)都是向著全局最優(yōu)的方向，但是大的整體方向卻是向著全局最優(yōu)解進(jìn)行，其結(jié)果也往往臨近全局最優(yōu)解。使用隨機(jī)梯度下降，不僅算法復(fù)雜度相對較低，同時還可以一定程度上避免過擬合問題。在圖的梯度下降中，還需要關(guān)注的問題是要找到一個合適的學(xué)習(xí)速率。

4 實驗結(jié)果與分析

4.1 數(shù)據(jù)集

本文研究的是網(wǎng)絡(luò)上的表示學(xué)習(xí)和分類，因此數(shù)據(jù)既要有網(wǎng)絡(luò)信息，也需要部分結(jié)點帶有分類標(biāo)簽信息。本次實驗的數(shù)據(jù)集有兩個，一個是取自論文max-margin DeepWalk[17]中的CiteSeer網(wǎng)絡(luò)，另一個是論文LINE[15]中的DBLP網(wǎng)絡(luò)。

（1）CiteSeer網(wǎng)絡(luò)的邊沒有權(quán)重，包含3 324個結(jié)點，4 732條邊，以及6個分類。CiteSeer（又名Research-Index）是NEC研究院在自動引文索引（autonomous citation indexing，ACI）機(jī)制的基礎(chǔ)上建設(shè)的一個學(xué)術(shù)論文數(shù)字圖書館。CiteSeer引文索引系統(tǒng)提供了一種通過引文鏈接檢索文獻(xiàn)的方式，目標(biāo)是從多方面促進(jìn)學(xué)術(shù)文獻(xiàn)的傳播和反饋。該數(shù)據(jù)集以論文為結(jié)點，論文的引文鏈接為邊，形成一個引文網(wǎng)絡(luò)。

（2）DBLP是一個帶權(quán)重的網(wǎng)絡(luò)，其邊的權(quán)重代表兩個作者合作的論文數(shù)量。DBLP網(wǎng)絡(luò)有18 058個結(jié)點，103 011條邊，以及3個分類。論文LINE[15]中作者提到，數(shù)據(jù)來自3個不同的研究領(lǐng)域：數(shù)據(jù)挖掘領(lǐng)域的WWW、KDD會議，機(jī)器學(xué)習(xí)領(lǐng)域的NIPS、ICML會議，計算機(jī)視覺領(lǐng)域的CVPR、ICCV會議。網(wǎng)絡(luò)是根據(jù)在這些會議上發(fā)布的論文進(jìn)行構(gòu)建的，因為這3個領(lǐng)域彼此之間非常詳盡，所以將這3個類別進(jìn)行區(qū)分十分有挑戰(zhàn)性。

4.2 比較方法

為了驗證TLINE算法的性能，本文用以下3個算法在DBLP和CiteSeer兩個數(shù)據(jù)集上進(jìn)行效果比較。

（1）DeepWalk[14]：DeepWalk算法是無監(jiān)督的網(wǎng)絡(luò)表示學(xué)習(xí)算法，由Perozzi于2014年提出，首次將深度學(xué)習(xí)引入到網(wǎng)絡(luò)表示學(xué)習(xí)中。DeepWalk算法在網(wǎng)絡(luò)圖上進(jìn)行隨機(jī)游走，將隨機(jī)游走的路徑當(dāng)成特殊的句子并應(yīng)用于語言模型上，學(xué)習(xí)出網(wǎng)絡(luò)結(jié)點的向量表示形式。實驗中將DeepWalk的參數(shù)取如下值：滑動窗口大小w=10，結(jié)點序列長度t=40，每個結(jié)點對應(yīng)的結(jié)點序列數(shù)量γ=80。

（2）LINE[15]：唐建提出的LINE算法。LINE和TLINE算法，均在CiteSeer實驗中取樣5萬條邊，在DBLP實驗中取樣50萬條邊。

（3）TLINE：本文提出的算法。參數(shù)設(shè)置為β=0.5，λ=0.02，表示向量的空間維度為10。

4.3 分類任務(wù)實驗結(jié)果

本文實驗了測試集占總數(shù)據(jù)集10%到90%的情況，對于DeepWalk和LINE算法，在得到結(jié)點的表示向量之后，使用SVM算法對結(jié)點進(jìn)行分類。本次實驗使用微平均Micro-F1作為衡量標(biāo)準(zhǔn)，取10次實驗平均后的結(jié)果。在CiteSeer數(shù)據(jù)集和DBLP數(shù)據(jù)集上進(jìn)行測試，表1和表2是實驗結(jié)果，標(biāo)黑的數(shù)據(jù)是實驗中得到的最好結(jié)果?？梢杂^察到以下現(xiàn)象：

Table 1 Micro-F1 of node classification on CiteSeer dataset表1 CiteSeer數(shù)據(jù)集上結(jié)點分類的微平均Micro-F1 %

Table 2 Micro-F1 of node classification on DBLP dataset表2 DBLP數(shù)據(jù)集上結(jié)點分類的微平均Micro-F1 %

（1）在大多數(shù)實驗中，直推式網(wǎng)絡(luò)表示學(xué)習(xí)算法實驗結(jié)果都比無監(jiān)督網(wǎng)絡(luò)表示學(xué)習(xí)算法的效果更好。就LINE和TLINE算法進(jìn)行比較，TLINE算法在CiteSeer和DBLP上平均有7%和6%的提高。這說明標(biāo)簽信息對于表示學(xué)習(xí)有很重要的意義。

（2）TLINE算法對于另外兩個算法有明顯的優(yōu)勢，并且優(yōu)勢隨著訓(xùn)練集比例的增大而增大。

4.4 參數(shù)敏感度實驗

對于LINE和SVM平衡參數(shù)β和SVM正則化項系數(shù)λ，本文在CiteSeer數(shù)據(jù)集和DBLP數(shù)據(jù)集上對參數(shù)進(jìn)行了聯(lián)合分析，結(jié)果如圖3和圖4所示。

在CiteSeer數(shù)據(jù)集上，λ取值從0.001到10，β取值從0.001到10。隨λ的增加微平均Micro-F1先略微增加，然后再減少。此數(shù)據(jù)集在λ為0.1，β為0.1到1附近取得最好結(jié)果。在DBLP數(shù)據(jù)集上，在β取值為0.001到1的情況下，λ在很大的一個范圍內(nèi)參數(shù)不敏感。因為擴(kuò)大了參數(shù)訓(xùn)練的力度，可以發(fā)現(xiàn)在 β和λ取值較大的情況下，微平均顯示訓(xùn)練結(jié)果很不好，且趨于一個常數(shù)。通過對 β和λ的敏感度組合訓(xùn)練，可以發(fā)現(xiàn)，兩者具有一定的相關(guān)性，但在β獲得較好取值的情況下，λ參數(shù)更不敏感。

Fig.3 Parameterβandλsensitivity research of TLINE on CiteSeer dataset圖3 TLINE在CiteSeer數(shù)據(jù)集上β和λ的組合敏感度實驗

Fig.4 Parameterβandλsensitivity research of TLINE on DBLP dataset圖4 TLINE在DBLP數(shù)據(jù)集上β和λ的組合敏感度實驗

本文經(jīng)過參數(shù)組合訓(xùn)練，為了能夠在兩個數(shù)據(jù)集上都達(dá)到較好效果，分類任務(wù)實驗中取 β=0.5，λ=0.02。

5 總結(jié)和展望

本文學(xué)習(xí)LINE算法的思想對網(wǎng)絡(luò)結(jié)構(gòu)局部特性加以利用，同時利用標(biāo)簽信息對網(wǎng)絡(luò)進(jìn)行直推式表示學(xué)習(xí)。已有的表示學(xué)習(xí)算法大部分只能處理小數(shù)據(jù)集，并且沒能將網(wǎng)絡(luò)的標(biāo)簽屬性很好地結(jié)合到網(wǎng)絡(luò)的表示學(xué)習(xí)中。受LINE算法的啟發(fā)，為了保持網(wǎng)絡(luò)結(jié)構(gòu)的局部特性，在TLINE算法中同樣利用了兩結(jié)點之間的邊權(quán)重，來表示兩個結(jié)點在低維空間表示學(xué)習(xí)出的向量相似度。然后在標(biāo)簽信息方面，使用線性支持向量機(jī)提高帶標(biāo)簽結(jié)點的可區(qū)分度，間接影響了無標(biāo)簽結(jié)點的向量表示結(jié)果。最后，通過在CiteSeer論文引用數(shù)據(jù)集和DBLP共同作者數(shù)據(jù)集上的實驗，可以看出，對于結(jié)點分類任務(wù)，TLINE算法的結(jié)果明顯優(yōu)于經(jīng)典的無監(jiān)督網(wǎng)絡(luò)表示學(xué)習(xí)算法（DeepWalk和LINE）。

在今后的工作中，將放眼網(wǎng)絡(luò)的全局特性而非單獨的局部特性，來對網(wǎng)絡(luò)進(jìn)行表示學(xué)習(xí)。同時，把同構(gòu)網(wǎng)絡(luò)的學(xué)習(xí)算法擴(kuò)展到更為普遍的異構(gòu)網(wǎng)絡(luò)，以及使用深度學(xué)習(xí)技術(shù)進(jìn)一步優(yōu)化分類算法，都是很有挑戰(zhàn)性的研究方向。

[1]Tang Jian,Liu Jingzhou,Zhang Ming,et al.Visualizing largescale and high-dimensional data[C]//Proceedings of the 25th International Conference on World Wide Web,Montreal,Canada,Apr 11-15,2016.NewYork:ACM,2016:287-297.

[2]Yang Zhilin,Cohen W,Salakhutdinov R.Revisiting semisupervised learning with graph embeddings[C]//Proceedings of the 33rd International Conference on Machine Learning, New York,Jun 19-24,2016.Red Hook,USA:Curran Associates,2016:86-94.

[3]Tang Jie,Lou Tiancheng,Kleinberg J,et al.Transfer link prediction across heterogeneous social networks[J].ACM Transactions on Information Systems,2015,9(4):1-42.

[4]Suykens J A K,Vandewalle J.Least squares support vector machine classifiers[J].Neural Processing Letters,1999,9(3): 293-300.

[5]Cox T F,Cox M A A.Multidimensional scaling[M].Boca Raton,USA:CRC Press,2000:123-141.

[6]Tenenbaum J B,de Silva V,Langford J C.A global geometric framework for nonlinear dimensionality reduction[J].Science,2000,290(5500):2319-2323.

[7]Roweis S T,Saul L K.Nonlinear dimensionality reduction by locally linear embedding[J].Science,2000,290(5500): 2323-2326.

[8]Belkin M,Niyogi P.Laplacian eigenmaps and spectral techniques for embedding and clustering[C]//Proceedings of the 14th International Conference on Neural Information Processing Systems:Natural and Synthetic,Vancouver,Canada, Dec 3-8,2001.Cambridge,USA:MIT Press,2001:585-591.

[9]Chen Mo,Yang Qiong,Tang Xiaoou.Directed graph embedding[C]//Proceedings of the 20th International Joint Conference on Artificial Intelligence,Hyderabad,India,Jan 6-12, 2007.San Francisco,USA:Morgan Kaufmann Publishers Inc,2007:2707-2712.

[10]Nallapati R,Cohen W W.Link-PLSA-LDA:a new unsupervised model for topics and influence of blogs[C]//Proceedings of the 2nd International Conference on Weblogs and Social Media,Seattle,USA,Mar 30-Apr 2,2008.Menlo Park,USA:AAAI,2008:84-92.

[11]Chang J,Blei D M.Relational topic models for document networks[C]//Proceedings of the 12th International Conference on Artificial Intelligence and Statistics,Clearwater Beach,USA,Apr 16-18,2009.Cambridge,USA:JMLR, 2009:81-88.

[12]Le T M V,Lauw H W.Probabilistic latent document network embedding[C]//Proceedings of the 2014 International Conference on Data Mining,Shenzhen,China,Dec 14-17, 2014.Washington:IEEE Computer Society,2014:270-279.

[13]Le Q,Mikolov T.Distributed representations of sentences and documents[C]//Proceedings of the 31st International Conference on Machine Learning,Beijing,Jun 21-26,2014. Red Hook,USA:CurranAssociates,2014:2931-2939.

[14]Perozzi B,Al-Rfou R,Skiena S.Deepwalk:online learning of social representations[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining,New York,Aug 24-27,2014.NewYork:ACM,2014:701-710.

[15]Tang Jian,Qu Meng,Wang Mingzhe,et al.LINE:largescale information network embedding[C]//Proceedings of the 24th International Conference on World Wide Web, Florence,Italy,May 18-22,2015.New York:ACM,2015: 1067-1077.

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

[17]Tu Cunchao,Zhang Weicheng,Liu Zhiyuan,et al.Max-margin DeepWalk:discriminative learning of network representation[C]//Proceedings of the 25th International Joint Conference on Artificial Intelligence,New York,Jul 9-15,2016. Menlo Park,USA:AAAI,2016:3889-3895.

ZHANG Xia was born in 1994.She is an M.S.candidate at Peking University.Her research interests include machine learning and network embedding.

張霞（1994—），女，四川遂寧人，北京大學(xué)碩士研究生，主要研究領(lǐng)域為機(jī)器學(xué)習(xí)，網(wǎng)絡(luò)表示學(xué)習(xí)。

CHEN Weizheng was born in 1990.He is a Ph.D.candidate at Peking University.His research interests include machine learning and social network analysis.

陳維政（1990—），男，山東濟(jì)寧人，北京大學(xué)博士研究生，主要研究領(lǐng)域為機(jī)器學(xué)習(xí)，社會網(wǎng)絡(luò)分析。

XIE Zhengmao was born in 1978.He received the M.S.degree in computer science from Peking University in 2003.Now he is a research assistant at Peking University.His research interests include distributed system,Web information crawling and large data.

謝正茂（1978—），男，湖南洞口人，2003年于北京大學(xué)獲得碩士學(xué)位，現(xiàn)為北京大學(xué)信息學(xué)院助理研究員，主要研究領(lǐng)域為分布式系統(tǒng)，Web信息爬取，大數(shù)據(jù)。

YAN Hongfei was born in 1973.He received the Ph.D.degree in computer science from Peking University in 2002.Now he is an associate professor at Peking University.His research interests include information retrieval and distributed computing.

閆宏飛（1973—），男，黑龍江哈爾濱人，2002年于北京大學(xué)獲得博士學(xué)位，現(xiàn)為北京大學(xué)副教授，主要研究領(lǐng)域為信息檢索，分布式計算。發(fā)表學(xué)術(shù)論文50多篇，作為負(fù)責(zé)人承擔(dān)國家自然科學(xué)基金、核高基項目、863計劃等。

Learning Transductive Network Embedding*

ZHANG Xia+,CHEN Weizheng,XIE Zhengmao,YAN Hongfei
School of Electronics Engineering and Computer Science,Peking University,Beijing 100871,China
+Corresponding author:E-mail:zhangxia9403@gmail.com

Network embedding is a classical task which aims to project a network into a low-dimensional space. Currently,most of existing embedding methods are unsupervised algorithms,which ignore useful label information. This paper proposes TLINE,a semi-supervised extension of LINE(large-scale information network embedding) algorithm.TLINE is a transductive network embedding method,which optimizes the loss function of LINE to preserve local network structure information,and applies SVM(support vector machine)to max the margin between the labeled nodes of different classes.By applying edge-sampling,negative sampling techniques and asynchronous stochastic gradient descent algorithm in the optimizing process,the computational complexity of TLINE is reduced, thus TLINE can handle the large-scale network.To evaluate the performance in node classification task,this paper tests the proposed methods on two real world network datasets,CiteSeer and DBLP.The experimental results indicate that TLINE outperforms the state-of-the-art baselines and is suitable for large-scale network.

transductive;network embedding learning;node classification

10.3778/j.issn.1673-9418.1611073

A

TP391

*The National Natural Science Foundation of China under Grant Nos.61272340,U1536201(國家自然科學(xué)基金);the National Basic Research Program of China under Grant No.2014CB340400(國家重點基礎(chǔ)研究發(fā)展計劃(973計劃)).

Received 2016-11,Accepted 2017-01.

CNKI網(wǎng)絡(luò)優(yōu)先出版:2017-01-16,http://www.cnki.net/kcms/detail/11.5602.TP.20170116.1702.010.html

ZHANG Xia,CHEN Weizheng,XIE Zhengmao,et al.Learning transductive network embedding.Journal of Frontiers of Computer Science and Technology,2017,11(4)：520-527.