基于deepwalk方法的適應有限文本信息的DWLTI算法

江東燦, 陳維政, 閆宏飛

(北京大學 計算機科學與技術系 北京 100871)

基于deepwalk方法的適應有限文本信息的DWLTI算法

江東燦, 陳維政, 閆宏飛

(北京大學 計算機科學與技術系 北京 100871)

提出一種新的網(wǎng)絡表示學習算法DWLTI，它是可以同時考慮網(wǎng)絡的結構信息和節(jié)點的文本屬性信息的低維向量表示.DWLTI模型是一種基于deepwalk方法的能夠適應有限文本信息的新模型.它通過采用合適的數(shù)據(jù)融合形式，同時最大化隨機游走獲得的節(jié)點序列和文本內(nèi)容的詞語序列的共現(xiàn)概率.通過應用兩棵哈夫曼子樹，使得即使只有少量部分節(jié)點擁有自身的文本信息，這些稀疏信息也能被充分利用.最后在真實網(wǎng)絡數(shù)據(jù)集上進行節(jié)點分類實驗，評估學習到的節(jié)點表示的質(zhì)量.實驗結果表明，利用有限文本信息的DWLTI優(yōu)于多種經(jīng)典基線模型.

deepwalk； 層次Softmax； 有限文本信息； 網(wǎng)絡表示學習； 深度學習

0 引言

準確地表達大規(guī)模網(wǎng)絡節(jié)點之間的關系是數(shù)據(jù)挖掘機器學習領域中一個充滿挑戰(zhàn)的重要研究目標，也是其他諸多任務不可或缺的前提.近年來，將離散節(jié)點映射(embedding)到一個新的低維連續(xù)空間中以向量形式表示是網(wǎng)絡表示學習(network representation)一個熱點方向.

然而在現(xiàn)有的網(wǎng)絡表示學習算法中，多數(shù)僅僅純粹考慮網(wǎng)絡結構關系，而忽略了節(jié)點本身擁有的文本信息內(nèi)容.比如譜向量(spectral embedding)[1]、MDS[2]、IsoMap[3]等時間復雜度很高的經(jīng)典學習算法,以及近年來運用神經(jīng)網(wǎng)絡模型通過隨機游走序列學習向量表示的deepwalk算法[4], 具有運用節(jié)點之間直接鄰居關系的一階模型和運用節(jié)點鄰居結構相似度的二階模型的line算法[5]等.同時也存在一些不是為網(wǎng)絡設計的算法，它們主要解決如何將文本信息映射成向量的問題，比如傳統(tǒng)的詞袋模型[6], 基于矩陣分解的潛在語義分析LSA(latent semantic analysis)[7], 主題模型[8-9]，基于神經(jīng)網(wǎng)絡的學習方法Word2Vec[10-11], PV-DBOW[12]，多向量話題表示方法[13]等，但它們同樣僅考慮了節(jié)點文本單方面的的信息，而不考慮節(jié)點之間的網(wǎng)絡結構關系.因此，目前大部分的算法都是僅基于網(wǎng)絡結構或是節(jié)點文本信息某一方面的內(nèi)容，鮮有算法將兩者結合在一起，通過綜合利用網(wǎng)絡中共存的各類有效信息，將節(jié)點映射表示成能夠充分反映網(wǎng)絡特征的向量.同時我們也注意到，在很多網(wǎng)絡中，除了網(wǎng)絡結構關系之外只有部分節(jié)點擁有文本信息，如何在文本信息稀疏有限的情況下,還能在向量表示中學習到相關內(nèi)容，也是一個值得關注的問題.

本文提出一種新的網(wǎng)絡表示學習算法，在優(yōu)化目標中同時考慮網(wǎng)絡結構信息和節(jié)點自身的文本內(nèi)容，基于deepwalk對網(wǎng)絡中節(jié)點與節(jié)點之間的結構關系進行建模，基于PV-DBOW對節(jié)點自身包含的文本信息建模，并采用正確的融合形式，同時最大化隨機游走獲得的節(jié)點序列的出現(xiàn)概率和文本內(nèi)容的共現(xiàn)概率，并通過在模型中應用兩棵哈夫曼樹，使得即使只有少量部分節(jié)點擁有自身的文本信息，這些稀疏信息也能在學習中充分發(fā)揮作用而不會被稀釋忽略，并進一步利用層次Softmax建立二叉樹神經(jīng)網(wǎng)絡結構優(yōu)化模型，采用深度學習的方法訓練學習模型參數(shù).最后我們通過線性SVM分類器在數(shù)據(jù)集上進行分類任務測試向量表示的效果.實驗結果表明，我們的算法能夠充分利用網(wǎng)絡中并存的多類信息，即使在節(jié)點信息與文本信息規(guī)模不一致的情況下，在訓練數(shù)據(jù)從10%～90%的各種占比的情況下，分類準確率都能優(yōu)于一些經(jīng)典的算法.

1 模型設計及求解

帶有文本信息的網(wǎng)絡可以表示成G=(V,E,D)，其中:vi∈V是網(wǎng)絡中的節(jié)點;ei,j=(vi,vj)∈E是網(wǎng)絡中節(jié)點直接的連接關系;di∈D是節(jié)點i中文本信息中的單位信息.網(wǎng)絡表示學習方法的目標是為每個點vi學習它在低維空間中的向量表示，使得在網(wǎng)絡結構連接中相近的點，或者在文本內(nèi)容上具有相似性的點，在映射后的低維空間中向量之間的距離也會更接近.

我們將網(wǎng)絡中的節(jié)點分為兩類：一類是自己具有文本信息的節(jié)點；另一類是自己沒有文本信息的節(jié)點.對網(wǎng)絡中的所有節(jié)點，我們的模型中采用deepwalk方法對它們之間的網(wǎng)絡結構關系進行建模學習; 對于自己具有文本信息的節(jié)點，我們的模型中另外對其采用PV-DBOW方法對節(jié)點自帶的文本信息進行建模學習，最后將兩者結合在一起，兩類信息共同對節(jié)點的向量表示產(chǎn)生影響.由于我們的融合過程里文本信息學習過程和節(jié)點關系的學習過程沒有混雜在一起，而是分別對節(jié)點向量產(chǎn)生影響，所以即使只有有限的節(jié)點具有文本信息，也能充分發(fā)揮這些文本信息的作用，不會由于這類節(jié)點在網(wǎng)絡整體中占比太小而導致這些稀疏信息在學習過程中被忽略.

1.1 采用deepwalk方法學習網(wǎng)絡結構信息

deepwalk中發(fā)現(xiàn)一個無標度網(wǎng)絡圖中節(jié)點出現(xiàn)的頻率也是符合冪律分布的，這和自然語言中詞頻是符合冪律分布具有相同的特征，所以deepwalk提出了引入自然語言領域中發(fā)展成熟的神經(jīng)網(wǎng)絡模型來處理網(wǎng)絡中的結構信息，他選擇使用Word2Vec模型[10-11].

在網(wǎng)絡結構信息的模型中，我們通過在網(wǎng)絡中構造隨機游走的序列來學習網(wǎng)絡中節(jié)點的向量表示.任意選取一個起始節(jié)點vi，從這個節(jié)點開始，隨機選擇一個它的鄰居節(jié)點作為序列中的下一個節(jié)點，再從這個被選中的節(jié)點開始繼續(xù)這個隨機過程，直到產(chǎn)生預設數(shù)量的序列節(jié)點個數(shù).通過這種隨機游走產(chǎn)生的序列，我們獲得了網(wǎng)絡結構信息.這種將序列控制在一定長度內(nèi)的隨機游走有兩個優(yōu)點：一是方便并行，多個局部可以同時探索；另一方面是一旦局部信息發(fā)生了變化，我們不用在全局中重新計算.

將網(wǎng)絡中的所有節(jié)點看作詞匯表，隨機游走生成的序列即為一種特殊語言中的句子.采用Word2Vec 中的SkipGram算法作為語言模型，其思想是給定句子中的某個詞(某個節(jié)點)，最大化一個句子(序列)中在其左右一定窗口范圍(i-w,i+w)中出現(xiàn)的詞(序列中周圍的節(jié)點)的出現(xiàn)概率，所以優(yōu)化目標為

(1)

(2)

其中:N是節(jié)點的總數(shù)量；S是隨機游走獲得的序列集合.逐次迭代更新向量表示，實現(xiàn)對這個優(yōu)化目標的求解，最后，在圖結構中相互連接或者連接關系臨近的點在低維向量空間中的向量也會更加靠近.

具體算法如下：

輸入：圖G和相關參數(shù)(窗口大小，序列抽樣個數(shù)，序列長度等)

輸出：映射表示矩陣Φ

隨機初始化表示矩陣

進行γ次隨機游走

對所有節(jié)點亂序排列

所有節(jié)點依次作為初始節(jié)點，作以下循環(huán)處理：

從這個節(jié)點開始隨機游走，產(chǎn)生預設長度的序列

對每個序列用SkipGram模型進行處理，對隨機游走得到的序列中的每個點vi

用窗口大小w獲得向左和向右的2w個節(jié)點

用這個窗口中的每個節(jié)點uk，更新

1.2 采用PV_DBOW學習部分節(jié)點的文本信息

將文本信息表示成向量的最原始的模型是詞袋模型BOW(bag-of-words)[6], 但是詞袋模型具有一些不可忽略的缺點，比如它忽略了詞匯之間的語義關系，近義詞在詞袋模型中的表示往往依然是不同的，以及向量表示的空間維度可能太高并存在高維引起的稀疏問題等.PV-DBOW(paragraph vector without word ordering: distributed bag of words)[12]方法是另一種運用神經(jīng)網(wǎng)絡將文本信息映射成低維空間向量的方法，它是一個非監(jiān)督的學習框架，能夠從長度不定的文本信息中學習定長的向量表示.相同語義的詞語在新的低維空間中的位置也是相近的，并且它們之間的距離也是具有意義的，比如“國王”的向量，減去“男性”的向量，加上“女性”的向量，將會在“王后”的向量附近.

根據(jù)PV-DBOW算法，對于給定的文本序列，我們設定一定的窗口長度，隨機設定窗口位置，并從這個窗口范圍內(nèi)隨機抽取單詞來進行預測，這個方法和Word2Vec中的SkipGram算法的思想實際上是相似的，但是PV-DBOW能夠?qū)θ我忾L度的文本信息比如句子、段落、文章等都進行學習.

1.3 DWLTI模型

針對網(wǎng)絡中同時具有網(wǎng)絡結構信息和僅有部分節(jié)點自身的文本信息的特點，我們設計了新的能夠適應有限文本信息的deepwalk方法，我們稱其為DWLTI模型(deepwalk with limited text information)，它綜合運用deepwalk學習網(wǎng)絡結構信息和PV-DBOW學習文本信息的思想，使得映射到低維空間中的向量表示同時充分具有這兩類信息中的特征.

在上述算法的迭代更新中，當規(guī)模變大時，直接對P計算的計算量將變得非常大，所以需要進一步采用層次Softmax[14-15]來估計這個概率.將每個點都作為一個二叉樹的葉子節(jié)點，從而將上述概率轉化成對從樹的根節(jié)點到達某個葉子節(jié)點的路徑的概率，假設從根節(jié)點到葉節(jié)點uk的路徑中經(jīng)過的樹節(jié)點為b0,b1, …,b, 上述概率即為Prvj),其中Pvj)可以用一個二分類器Pr)來計算選擇左子樹或是右子樹的概率,σ是一個sigmoid函數(shù).

圖1 DWLTI哈夫曼樹Fig.1 DWLTI Huffman tree

由于我們的優(yōu)化函數(shù)中同時存在網(wǎng)絡結構和文本信息兩部分的內(nèi)容，并且這兩部分信息的規(guī)模大小可能并不一致，所以在DWLTI模型中通過兩棵哈夫曼樹來進行迭代更新，和將兩種信息混雜在一棵哈夫曼樹中相比，即使擁有文本信息的節(jié)點數(shù)量較少，這些信息也能全部通過單獨的哈夫曼樹發(fā)揮作用，而不會被大量的網(wǎng)絡結構信息節(jié)點稀釋忽略，示意圖如圖1所示.

2 實驗

2.1 實驗數(shù)據(jù)集及參數(shù)設置

為了檢驗向量表示的結果，我們選擇了兩個數(shù)據(jù)集Cora和Citeseer，先通過我們的DWLTI模型學習出節(jié)點對應的低維空間向量，再用線性SVM利用獲得的低維空間向量進行分類任務.

Cora數(shù)據(jù)集中有2 708篇機器學習相關的論文，其中包含7個具體的子類和5 429條連接.連接定義為論文之間的引用關系，同時文檔自身的內(nèi)容信息用一個1 433維的0-1向量表示.

Citeseer數(shù)據(jù)集中有3 312篇著作，其中包含了6個具體的子類和4 732條連接.和Cora數(shù)據(jù)集相似，連接是論文之間的引用關系，同時文檔自身的內(nèi)容信息可以用一個3 703維的0-1向量表示.

在實驗中，我們設置DWLTI模型的向量長度d=200，窗口大小等于10.每個節(jié)點選擇80個隨機游走序列，每個隨機游走序列的長度等于40，并將文檔的內(nèi)容信息轉換成序列進行學習.最終用線性SVM在模型學習出的向量表示上進行分類任務，采用準確率作為度量標準.

2.2 實驗結果

我們選用經(jīng)典的deepwalk和line算法作為實驗結果對比.對deepwalk對應參數(shù)設置與DWLTI相同的值，對line算法采樣個數(shù)為1 000萬.在實驗結果表1和表2中，line(1st)表示line的一階模型，line(2nd)表示line的二階模型， DWLTI(0.2)表示網(wǎng)絡中只有20%的節(jié)點自身具有文本信息，DWLT(0.5)表示網(wǎng)絡中只有50%的節(jié)點自身具有文本信息.

表1 Cora數(shù)據(jù)集上的節(jié)點分類準確率

表2 Citeseer數(shù)據(jù)集上的節(jié)點分類準確率

實驗結果表明，我們的DWLTI算法幾乎在所有情況下的分類準確率都優(yōu)于幾種經(jīng)典算法.即使是文本信息節(jié)點稀疏的情況下都能充分利用有限的信息，在我們的實驗中，即使只有20%或50%的節(jié)點具有文本信息，也能達到比deepwalk和line算法更優(yōu)的結果.因此，在DWLTI模型中學習得到的向量表示具有更高的分類準確率.DWLTI算法是一種適應有限文本信息的網(wǎng)絡表示新模型，在網(wǎng)絡表示學習研究中具有一定的意義.

[1] TANG L, LIU H. Leveraging social media networks for classification[J]. Data mining and knowledge discovery, 2011, 23(3):447-478.

[2] COX T F, COX M A A. Multidimensional scaling[M].2nd Edition.Florida: CRC Press, 2000.

[3] TENENBAUM J B, DE S V, LANGFORD J C. A global geometric framework for nonlinear dimensionality reduction[J]. Science, 2000, 290(5500):2319-23.

[4] 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, 2014:701-710.

[5] TANG J, QU M, WANG M Z, et al. Line: large-scale information network embedding[C]//Proceedings of the 24th International Conference on World Wide Web. Florence, 2015: 1067-1077.

[6] MANNING C D, RAGHAVAN P, SCHüTZE H. Introduction to information retrieval[M].Cambridge: Cambridge University Press, 2008:824-825.

[7] LANDAUER T K, FOLTZ P W, LAHAM D. An introduction to latent semantic analysis[J]. Discourse processes, 1998, 25(2):259-284.

[8] HOFMANN T. Probabilistic latent semantic indexing[C]//Proceedings of the 27th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. Sheffied, 2004:56-73.

[9] BLEI D M, NG A Y, JORDAN M I. Latent dirichlet allocation[J]. Journal of machine learning research, 2003,3(1):993-1022.

[10]MIKOLOV T, CORRADO G, CHEN K, et al. Efficient estimation of word representations in vector space[C]//Proceedings of Workshop at ICLR.Florida,2013:1-12.

[11]MIKOLOV T, SUTSKEVER I, CHEN K, et al. Distributed representations of words and phrases and their compositionality[C]//Advances in Neural Information Processing Systems 26.Lake Tahoe,2013:3111-3119.

[12]LE Q V, MIKOLOV T. Distributed representations of sentences and documents[J]. Computer science, 2014, 4:1188-1196.

[13]李欣雨,袁方,劉宇,等.面向中文新聞話題檢測的多向量文本聚類方法[J].鄭州大學學報(理學版),2016,48(2):47-52.

[14]MORIN F, BENGIO Y. Hierarchical probabilistic neural network language model[C]//Proceedings of the International Workshop on Artificial Intelligence and Statistics. Cambridge, 2005: 246-252.

[15]MNIH A, HINTON G E. A scalable hierarchical distributed language model[C]//Conference on Neural Information Processing Systems. Vancouver, 2008:1081-1088.

(責任編輯：王?？?

DWLTI Method Based on Deepwalk with Limited Text Information

JIANG Dongcan, CHEN Weizheng, YAN Hongfei

(DepartmentofComputerScienceandTechnology,PekingUniversity,Beijing100871,China)

A new network representation method was proposed.It could simultaneously consider both the network link structure information and the text information on some nodes in the optimization goal. It had created a correct format to merge those parts to maximize the co-occurrence probability of the nodes sequence gotten by random walk and the word sequence in text. The new model used two Huffman sub-trees to make all text information useful even with small amount of nodes. It used Hierarchical Softmax to optimize the model by building binary tree and learned model parameters using deep learning.Linear SVM was chosed to test the quality of vector representation in the new low-dimension embedding space. The experimental result showed that the new method DWLTI was useful in the network with limited text information on part nodes. The results of DWLTI were better than some other classical models in this field.

deepwalk； hierarchical Softmax； limited text information； network representation； deep learning

2016-11-15

973項目(2014CB340400)；國家自然科學基金項目(U1536201，61272340).

江東燦(1992—)，女，福建南平人，碩士研究生，主要從事搜索引擎與數(shù)據(jù)挖掘研究，E-mail：dongcan.jiang@gmail.com; 通訊作者：閆宏飛(1973—)，男，吉林扶余人，副教授，主要從事搜索引擎與數(shù)據(jù)挖掘研究，E-mail:yhf1029@gmail.com.

TP301.6

A

1671-6841(2017)01-0029-05

10.13705/j.issn.1671-6841.2016312