直推式網絡表示學習*

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

北京大學 信息科學技術學院，北京 100871

直推式網絡表示學習*

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

北京大學 信息科學技術學院，北京 100871

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

直推式；網絡表示學習；結點分類

1 引言

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

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

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

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

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

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

2 相關工作

網絡表示學習是在低維度的向量表示空間內，通過對網絡結構特性分析，對網絡結點進行表示。表示學習的意義是緩解數據稀疏，建立統一的表示空間，實現知識的遷移。

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

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

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

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

通過對LINE和SVM的權衡，本文提出的TLINE算法既對結點的標簽信息進行了充分利用，又同時適用于大規(guī)模的網絡表示學習的任務。

3 模型與實現

3.1 大規(guī)模網絡表示學習

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

ui∈Rd是結點vi在d維空間的表示向量。此時再定義經驗分布函數如下：

為了保存網絡的局部特性，需要優(yōu)化以下函數：

省略一些常數項，可以得到：

這里，σ指代的是sigmoid函數。Oline通過最小化目標函數，可以得到|v|個結點的對于網絡局部特性學習得出的表示學習向量{ui}i=1…|v|。

3.2 基于SVM的分類

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

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

3.3 直推式網絡表示學習

給定一個網絡圖結構，圖上的部分結點帶有分類信息，任務是要能夠對還沒有進行分類的結點進行分類。傳統的表示學習和分類算法，分為兩步進行，如圖1所示。首先將每個結點映射到低維空間，即表示學習，然后再在這低維空間中，將帶分類信息的結點作為訓練集，剩下的作為測試集。用訓練集的表示學習向量來訓練分類器，最后對測試集進行分類判定輸出。

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

Fig.1 Traditional unsupervised embedding learning and classification圖1 傳統無監(jiān)督表示學習和分類

Fig.2 Transductive embedding learning and classification圖2 直推式表示學習和分類

為了更好地表示網絡結構的局部特性，同時提高分類的效果，本文把在網絡表示學習中效果顯著的LINE算法和著名的支持向量機分類算法結合起來，用直推式表示學習的方式對網絡進行表示學習，即是說：

β是平衡LINE和SVM的比例參數。

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

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

4 實驗結果與分析

4.1 數據集

本文研究的是網絡上的表示學習和分類，因此數據既要有網絡信息，也需要部分結點帶有分類標簽信息。本次實驗的數據集有兩個，一個是取自論文max-margin DeepWalk[17]中的CiteSeer網絡，另一個是論文LINE[15]中的DBLP網絡。

（1）CiteSeer網絡的邊沒有權重，包含3 324個結點，4 732條邊，以及6個分類。CiteSeer（又名Research-Index）是NEC研究院在自動引文索引（autonomous citation indexing，ACI）機制的基礎上建設的一個學術論文數字圖書館。CiteSeer引文索引系統提供了一種通過引文鏈接檢索文獻的方式，目標是從多方面促進學術文獻的傳播和反饋。該數據集以論文為結點，論文的引文鏈接為邊，形成一個引文網絡。

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

4.2 比較方法

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

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

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

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

4.3 分類任務實驗結果

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

Table 1 Micro-F1 of node classification on CiteSeer dataset表1 CiteSeer數據集上結點分類的微平均Micro-F1 %

Table 2 Micro-F1 of node classification on DBLP dataset表2 DBLP數據集上結點分類的微平均Micro-F1 %

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

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

4.4 參數敏感度實驗

對于LINE和SVM平衡參數β和SVM正則化項系數λ，本文在CiteSeer數據集和DBLP數據集上對參數進行了聯合分析，結果如圖3和圖4所示。

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

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

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

本文經過參數組合訓練，為了能夠在兩個數據集上都達到較好效果，分類任務實驗中取 β=0.5，λ=0.02。

5 總結和展望

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

在今后的工作中，將放眼網絡的全局特性而非單獨的局部特性，來對網絡進行表示學習。同時，把同構網絡的學習算法擴展到更為普遍的異構網絡，以及使用深度學習技術進一步優(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—），女，四川遂寧人，北京大學碩士研究生，主要研究領域為機器學習，網絡表示學習。

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—），男，山東濟寧人，北京大學博士研究生，主要研究領域為機器學習，社會網絡分析。

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年于北京大學獲得碩士學位，現為北京大學信息學院助理研究員，主要研究領域為分布式系統，Web信息爬取，大數據。

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年于北京大學獲得博士學位，現為北京大學副教授，主要研究領域為信息檢索，分布式計算。發(fā)表學術論文50多篇，作為負責人承擔國家自然科學基金、核高基項目、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(國家自然科學基金);the National Basic Research Program of China under Grant No.2014CB340400(國家重點基礎研究發(fā)展計劃(973計劃)).

Received 2016-11,Accepted 2017-01.

CNKI網絡優(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.