網(wǎng)絡(luò)表示學(xué)習(xí)算法的分析與驗證

王 巖，唐 杰

(清華大學(xué) 計算機科學(xué)與技術(shù)系，北京 100084)

0 緒論

在互聯(lián)網(wǎng)和多媒體技術(shù)興起之前，社交網(wǎng)絡(luò)分析領(lǐng)域所使用的數(shù)據(jù)量一直都比較小，但是隨著一大批新興社交媒體的普及，例如，F(xiàn)acebook、Twitter、Sina Weibo、Wechat和百度貼吧等，這些社交網(wǎng)絡(luò)上的數(shù)據(jù)規(guī)模開始爆炸性增長，它們動輒具有上億的用戶，由這些用戶產(chǎn)生的數(shù)據(jù)，如好友關(guān)系、發(fā)布的文本、圖片乃至視頻信息也到達了驚人的量級。除此之外，還有在學(xué)術(shù)研究中論文合作者或論文引用組成的網(wǎng)絡(luò)，在專利申請中構(gòu)成的網(wǎng)絡(luò)，在網(wǎng)頁相互鏈接構(gòu)成的網(wǎng)絡(luò)等等，這些超大規(guī)模數(shù)據(jù)的產(chǎn)生，也進一步推動著社交網(wǎng)絡(luò)分析這一領(lǐng)域的發(fā)展。

網(wǎng)絡(luò)表示學(xué)習(xí)算法是近年來網(wǎng)絡(luò)分析中一個熱點研究方向。對網(wǎng)絡(luò)型數(shù)據(jù)或者對網(wǎng)絡(luò)中的點或邊的分析，一直以來都在構(gòu)建各種評價指標(biāo)的層面，而網(wǎng)絡(luò)表示學(xué)習(xí)則給出了另一種看待網(wǎng)絡(luò)的觀點。在得到整個網(wǎng)絡(luò)的特征表示，網(wǎng)絡(luò)中各節(jié)點的表示乃至各邊的向量表示之后，就可以使用各種傳統(tǒng)機器學(xué)習(xí)方法(例如，支持向量機分類算法)來對各種表示進行更深層次的研究。從這個層面上來說，網(wǎng)絡(luò)的表示學(xué)習(xí)意義重大，因為它在社會網(wǎng)絡(luò)分析領(lǐng)域和傳統(tǒng)機器學(xué)習(xí)領(lǐng)域搭建了一個連接的橋梁。網(wǎng)絡(luò)表示學(xué)習(xí)的要求大致有以下兩點： (1)通過學(xué)習(xí)網(wǎng)絡(luò)的表示來保留網(wǎng)絡(luò)的拓撲結(jié)構(gòu)信息。(2)根據(jù)網(wǎng)絡(luò)的表示學(xué)習(xí)進一步進行網(wǎng)絡(luò)推斷任務(wù)。例如，節(jié)點標(biāo)簽分類任務(wù)，邊的存在與否的預(yù)測問題等。

此外，研究各類網(wǎng)絡(luò)表示學(xué)習(xí)算法是否學(xué)習(xí)到了高階或低階的結(jié)構(gòu)信息，在稀疏網(wǎng)絡(luò)還是稠密網(wǎng)絡(luò)上表現(xiàn)如何，算法是否具有較強的魯棒性(是否對參數(shù)敏感)等問題，可以全面評價各類算法的性能、效率和應(yīng)用范圍等，也可以幫助以后的研究者或者在工業(yè)界的工程開發(fā)算法的選擇上提供借鑒參考。

1 相關(guān)研究

網(wǎng)絡(luò)表示學(xué)習(xí)吸引了大量數(shù)據(jù)挖掘和社會學(xué)的研究者，本文主要研究網(wǎng)絡(luò)表示學(xué)習(xí)中的節(jié)點表示學(xué)習(xí)算法。初期的網(wǎng)絡(luò)表示學(xué)習(xí)與維度縮減(Dimension Reduction)的經(jīng)典方法相關(guān)，例如，多維縮放(Multi-dimension Scaling, MDS[1])、IsoMap[2]、LLE[3]和拉普拉斯特征映射(Laplacian Eigenmap[4])。 這些方法通常先使用數(shù)據(jù)點的特征向量構(gòu)建親和度圖(例如，數(shù)據(jù)的K最緊鄰圖)，再將這個圖映射到低維空間中。然而，這些算法通常依賴于求解親和度矩陣的主導(dǎo)特征向量，其時間復(fù)雜度很高，至少為節(jié)點數(shù)量N的二次方，使得它們很難處理大規(guī)模網(wǎng)絡(luò)[2]。

此外，A Ahmed等在2013年WWW中提出了一種圖分解(Graph Factorization[5])的技術(shù)。它通過矩陣分解找到圖的低維表示，而后使用隨機梯度下降算法(Stochastic Gradient Descent, SGD)來優(yōu)化其節(jié)點的低維空間表示，該技術(shù)也具有同樣受限于時空間復(fù)雜度的問題。

Shaosheng Cao等在2015年提出了一個能夠很好地保留網(wǎng)絡(luò)拓撲結(jié)構(gòu)的算法GraRep[6]。該算法通過操作圖中的不同階的節(jié)點轉(zhuǎn)移概率矩陣來捕捉不同階的結(jié)構(gòu)信息，而不需要任何緩慢和復(fù)雜的抽樣過程。它將不同的轉(zhuǎn)移概率矩陣進行分解以獲得不同階的特征表示，在各自歸一化后并將它們合并起來作為最終的節(jié)點表示，通過適當(dāng)選擇最高階數(shù)，GraRep就能最大程度保留網(wǎng)絡(luò)的高、低階的結(jié)構(gòu)信息。

而后，在2016年P(guān)eng Cui等提出了模型HOPE[7]，用于捕捉網(wǎng)絡(luò)的高階結(jié)構(gòu)信息和保留有向圖中節(jié)點之間的反對稱關(guān)系，他們使用幾個不同的網(wǎng)絡(luò)結(jié)構(gòu)描述矩陣，例如，Katz矩陣、Personalized PageRank矩陣或Adamic-Adar矩陣，并將它們應(yīng)用到矩陣分解技術(shù)中，從而獲得節(jié)點的特征表示。由于他們保持了圖的非對稱關(guān)系，所以在有向圖中獲得了很好的實驗效果。

Bryan Perozzi在2014年根據(jù)圖中隨機游走的路徑中節(jié)點出現(xiàn)的頻率服從長尾分布，與自然語言處理中詞頻的分布十分相似，因而提出了使用語言模型中的深度學(xué)習(xí)技術(shù)Word2Vec來學(xué)習(xí)圖的鄰接矩陣的隱含表示的算法DeepWalk[8]。通過簡單的隨機游走策略生成一些路徑后，將其作為語言模型Word2Vec的輸入文本語料而學(xué)得每個節(jié)點的向量表示，取得了十分突出的效果。

此后，北京大學(xué)的Jian Tang等在定義了一階接近度(First-order Proximity)與二階接近度(Second-order Proximity)后，通過定義一個設(shè)計精妙的目標(biāo)函數(shù)從而同時保留節(jié)點的一階或二階接近度，分別得到了節(jié)點的特征表示，并將每個節(jié)點的兩類特征表示連接起來，成為最后表示的算法LINE(Large-scale Information Network Embedding)。又因其考慮到網(wǎng)絡(luò)結(jié)構(gòu)中較為高階的信息，從而獲得了良好的效果[9]。

Vincent W Zheng于2017年提出將節(jié)點的社區(qū)結(jié)構(gòu)特征這種更高階的信息增加到目標(biāo)函數(shù)中。將基于LINE和高斯混合模型(Gaussian Mixure Model，GMM)加入到學(xué)習(xí)中而提出了ComEmbed[10]。它考慮將每個社區(qū)結(jié)構(gòu)用一個高斯分量來代表，每個社區(qū)具有一個社區(qū)中心向量(社區(qū)特征表示)和該社區(qū)中所有節(jié)點特征表示的協(xié)方差矩陣，通過坐標(biāo)下降(Coordinate Descent)迭代地優(yōu)化節(jié)點特征表示和社區(qū)特征表示，ComEmbed獲得了較好的效果。

Aditya Grover與Jure Leskovec在DeepWalk的基礎(chǔ)上對其隨機游走的策略提出了改進算法node2vec[11]，使得隨機游走的過程兼顧了廣度優(yōu)先搜索(Breadth-First Search, BFS)與深度優(yōu)先搜索(Depth-First Search, DFS)，從而提高了隨機游走生成的路徑的質(zhì)量。但由于其在抽樣的過程中要構(gòu)建圖中每一條邊(節(jié)點v到u)到下一個點(u的一個鄰居節(jié)點)的轉(zhuǎn)移概率表，因而具有比DeepWalk更高的時間和空間復(fù)雜度。

Shaosheng Cao等在2016年考慮到使用Skip-gram 語言模型+ Negative Sampling優(yōu)化算法,DeepWalk的目標(biāo)函數(shù)的一個可行解是節(jié)點互信息矩陣(Pointwise Mutual Information，PMI)[12]，因而將PMI矩陣的一個變形矩陣： 非負節(jié)點互信息矩陣(Positive Pointwise Mutual Information，PPMI)作為深度學(xué)習(xí)模型堆棧式自編碼器(Stacked Denoising AutoEncoder，SDAE[13])的輸入，將SDAE的最中間層的特征作為節(jié)點的最終表示，該深度學(xué)習(xí)模型為DNGR[14]。

Peng Cui等在2016年也提出了一個深度學(xué)習(xí)模型(Structral Deep Network Embedding, SDNE[15])。該模型能夠通過一個半監(jiān)督學(xué)習(xí)的框架，同時捕捉到節(jié)點的一階接近度和二階接近度[9]。具體來說，一階接近度被用來保留節(jié)點的局部結(jié)構(gòu)信息而作為模型的有監(jiān)督部分，而二階接近度被用來保留節(jié)點的全局結(jié)構(gòu)信息而作為模型的無監(jiān)督部分，是深度學(xué)習(xí)模型深度自編碼器(Deep AutoEncoder，DAE)的輸入。通過在半監(jiān)督學(xué)習(xí)模型中聯(lián)合優(yōu)化節(jié)點的一階接近度和二階接近度，該模型能夠同時保留網(wǎng)絡(luò)的局部結(jié)構(gòu)和全局結(jié)構(gòu)，從而獲得很好的效果[15]。

2 網(wǎng)絡(luò)表示學(xué)習(xí)算法分析

網(wǎng)絡(luò)表示學(xué)習(xí)意在學(xué)習(xí)一個網(wǎng)絡(luò)的結(jié)構(gòu)信息在一個較低維空間的特征表示，形式化來說，給定一個網(wǎng)絡(luò)G(V,E)，網(wǎng)絡(luò)中節(jié)點個數(shù)|V|=n，wv,u代表節(jié)點v與u之邊的權(quán)重，邊的總條數(shù)|E|=m。網(wǎng)絡(luò)表示學(xué)習(xí)意在將每個圖中的節(jié)點v∈V映射到一個低維空間Rd，也就是說學(xué)習(xí)一個函數(shù)fG:v→Rd,其中d

從這些不同的算法所使用的主要技術(shù)手段來分類，現(xiàn)有的網(wǎng)絡(luò)表示學(xué)習(xí)方案大概有三類。

(1) 基于矩陣分解的算法，包括MDS[1]，譜聚類算法(Spectral Clustering)[16]，GraRep[6]，Hope[7]等。

(2) 基于生成模型的算法，包括LINE[9]，ComEmbed[10]等。

(3) 基于深度學(xué)習(xí)的算法，例如，DeepWalk[8]，node2vec[11]，DNGR[14]，SDNE[15]等。

基于生成模型的算法，其一般會根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)的特征建模一個概率分布，通過利用KL距離(Kullback-Leiler Divergence)等技術(shù)構(gòu)建一個目標(biāo)函數(shù)，再將其轉(zhuǎn)化為目標(biāo)函數(shù)的優(yōu)化問題。然后，通過各種優(yōu)化算法或近似技術(shù)，例如，隨機梯度下降算法、負采樣算法(Negative Sampling)來進行優(yōu)化，最終獲得網(wǎng)絡(luò)的節(jié)點特征表示，例如，LINE[9]。

基于深度學(xué)習(xí)的模型，一般都會先定義一個目標(biāo)函數(shù)，再利用現(xiàn)有的深度模型進行學(xué)習(xí)，例如，多層感知器，各種自編碼器的變形，或者分層softmax等。

本文想要探究各類網(wǎng)絡(luò)表示學(xué)習(xí)算法是否學(xué)習(xí)到了網(wǎng)絡(luò)的結(jié)構(gòu)信息，學(xué)到的是高階還是低階信息，算法的性能與網(wǎng)絡(luò)的稀疏情況，節(jié)點聚集情況是否有關(guān)，算法在實際應(yīng)用中是否具有穩(wěn)定性等等問題。本文收集了不同類型的8個現(xiàn)實世界數(shù)據(jù)集，并利用這些網(wǎng)絡(luò)來研究各類算法的表現(xiàn)。

3 實驗

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

在各種不同的網(wǎng)絡(luò)上對那些算法進行評測，包括WebKB、Citeseer、BlogCatalog、Wikipedia、PPI、Aminer等?，F(xiàn)在簡單介紹這些網(wǎng)絡(luò)的來源與構(gòu)成。

WebKB[18]網(wǎng)絡(luò)由4個子網(wǎng)組成，共有877個點和1 608條邊。子網(wǎng)分別來自于美國四所大學(xué)： Cornell、Texas、Washington、Wisconsin，這里將節(jié)點的社區(qū)編號作為其標(biāo)簽，實驗中獨立使用四個子網(wǎng)。

Citeseer[19]網(wǎng)絡(luò)是從Citeseer電子庫中抽取的引用關(guān)系網(wǎng)絡(luò)，節(jié)點是出版物，而有向邊代表一個引用關(guān)系，由于出版物可以引用他們自身，所以網(wǎng)絡(luò)中存在著自環(huán)。

Blogcatalog[20]是一個博客的社交網(wǎng)絡(luò)，每個點代表了一個博主，而每條邊代表了博主之間的社交關(guān)系。博主在提交博文時會附加一些興趣標(biāo)簽，本文考慮將這些興趣標(biāo)簽作為參考標(biāo)準(zhǔn)。

Wikipedia[21]是一個在維基百科前一百萬字節(jié)中的單詞共同出現(xiàn)的網(wǎng)絡(luò)，而其標(biāo)簽代表由斯坦福的POS-Tagger推斷出的Part-of-Speech(POS)。

Protein-Protein Interactions(PPI)[22]是Homo Sapiens網(wǎng)絡(luò)的子圖，該子圖對應(yīng)具有標(biāo)記基因并代表生物狀態(tài)的節(jié)點所構(gòu)成的圖。

表4.1 數(shù)據(jù)統(tǒng)計信息

3.2 實驗算法

實驗中主要實現(xiàn)并評估了以下算法：

Spectral Clustering[16]： 這個算法生成圖的歸一化的Laplace矩陣在低維空間的表示。

HOPE[7]： 該算法通過分解Katz矩陣以保留有向圖的反對稱性質(zhì)，并集成了圖中拓撲結(jié)構(gòu)的高階的接近度的信息。

Modularity[17]： 該算法用SVD矩陣分解的算法來分解圖的模塊度矩陣，其中模塊度矩陣Q代表了圖中分割的信息。因此，最終的表示編碼了如何分割圖G的信息。

GraRep[6]： 此算法基于節(jié)點的k步轉(zhuǎn)移概率擴展了節(jié)點的高階的接近度，將從矩陣分解中獲得的不同階的表示歸一化后，連接在一起作為最終的表示。

LINE[9]： 這個算法精心設(shè)計了兩個目標(biāo)函數(shù)用來分別保留節(jié)點的一階接近度和二階接近度的信息，并將從兩個目標(biāo)函數(shù)中分別學(xué)習(xí)到的表示連接起來。

ComEmbed[10]： 該算法通過聯(lián)合優(yōu)化節(jié)點的表示與社區(qū)的表示，來保留一階接近度與更高階的社區(qū)結(jié)構(gòu)的接近度。

DeepWalk[8]： 該算法通過截斷的隨機游走路徑，將網(wǎng)絡(luò)結(jié)構(gòu)轉(zhuǎn)化為線性的節(jié)點序列，而后利用Skip-gram模型與分層softmax技術(shù)來學(xué)習(xí)節(jié)點的表示。

Node2vec[11]： 它利用廣度優(yōu)先搜索和深度優(yōu)先搜索來進行一個有偏置的隨機游走，以便在節(jié)點的同質(zhì)相似性和結(jié)構(gòu)等價相似性上達到一個均衡。

DNGR[14]： 它利用堆棧式自編碼器來學(xué)習(xí)非負節(jié)點互信息矩陣在低維空間的表示。

SDNE[15]： 此算法提出了一個基于深度自編碼器的半監(jiān)督學(xué)習(xí)模型，來聯(lián)合地學(xué)習(xí)節(jié)點的一階接近度與二階接近度來保留網(wǎng)絡(luò)的結(jié)構(gòu)信息。

3.3 參數(shù)設(shè)置

為了使算法的比較盡量公平，每個算法最終節(jié)點的表示維度d=128。 對GraRep而言，矩陣的最高階次K=5。 對于HOPE而言， Katz矩陣構(gòu)造過程中的參數(shù)β=0.01。 而對于DeepWalk，設(shè)置從每個節(jié)點開始的路徑數(shù)γ=10,路徑長度l=80,窗口大小w=5[8]。Node2vec與DeepWalk具有相同的參數(shù)，而其另外兩個超參數(shù)p,q則通過網(wǎng)格搜索來從{0.25, 0.50, 1, 2, 4}中擇優(yōu)選擇[11]。對LINE來說，設(shè)置初始的學(xué)習(xí)速率α=0.025，而負抽樣的數(shù)量為mne=5，總的邊抽樣的條數(shù)為T=γ×l×n[9]。對ComEmbed算法，其參數(shù)設(shè)置也與DeepWalk相似，而初始的學(xué)習(xí)速率α=0.01。對DNGR而言，其隨機平滑的總步長step=10，隨機平滑的比例α=0.98，其模型的堆棧式自編碼器的隱藏層數(shù)layer=2。最后對于SDNE，其深度自編碼器的層數(shù)layer=2。

3.4 實驗分析

與DeepWalk相同，我們在節(jié)點的多標(biāo)簽分類任務(wù)上對所有算法進行評測，隨機選擇不同比例的有標(biāo)簽的節(jié)點及其部分標(biāo)簽作為訓(xùn)練集，而其他部分則作為測試集。所有算法最終的節(jié)點特征表示都用一個使用L2正則技術(shù)的one-vs rest的邏輯回歸分類器訓(xùn)練，重復(fù)分類試驗10次，并報告10次結(jié)果的平均微觀F1值。由于宏觀F1值的趨勢與微觀F1值相似，因此在這里就不報告了[11]。

表2和表3中，報告了所有網(wǎng)絡(luò)表示學(xué)習(xí)算法(3.2節(jié)中的10種)在所有數(shù)據(jù)集(3.1中的8類)上的分類效果的實驗結(jié)果。每一行代表了某一個算法在某一個數(shù)據(jù)集上進行學(xué)習(xí)其網(wǎng)絡(luò)表示，而后使用分類器進行訓(xùn)練。訓(xùn)練數(shù)據(jù)和測試數(shù)據(jù)的比例從10%到90%不等，表格中的每一項代表使用分類器進行分類的準(zhǔn)確率。數(shù)值越大，代表分類效果越好，也代表了網(wǎng)絡(luò)表示學(xué)習(xí)算法的性能越好，能捕捉更多的結(jié)構(gòu)信息。根據(jù)表中的結(jié)果，可以得到如下的觀察與分析。

(1) 基于矩陣分解的算法，例如，Spectral Clustering、HOPE、GraRep以及Modularity在較為稠密的網(wǎng)絡(luò)上表現(xiàn)一般，但在一些特別的網(wǎng)絡(luò)上有些算法表現(xiàn)很好(GraRep 在Wisconsin，HOPE在Cornell)。而在較為稀疏的網(wǎng)絡(luò)上，它們表現(xiàn)得較好一些(Spectral Clustering在BlogCatalog、PPI，HOPE、Modularity在Wikipedia)。但是由于它們都有較高的時空復(fù)雜度，因此很難應(yīng)用到大規(guī)模的網(wǎng)絡(luò)上，從而限制了它們的實際應(yīng)用。

(2) 對于LINE來說，在稀疏和較為發(fā)散(低聚集系數(shù))的網(wǎng)絡(luò)上表現(xiàn)很好(LINE在Citeseer、PPI)，ComEmbed比LINE表現(xiàn)的更好，因為它將更高階的接近度信息(社區(qū)結(jié)構(gòu)信息)納入到考慮中。

(3) 深度學(xué)習(xí)模型表現(xiàn)出了最穩(wěn)定的效果以及在大多數(shù)網(wǎng)絡(luò)上有著最佳的表現(xiàn)(DeepWalk、node2vec在Washington、Texas、BlogCatalog上)。然而node2vec運行的速度要比DeepWalk慢得多。此外，DNGR表現(xiàn)的很一般，因其實質(zhì)上就是對一個非負節(jié)點互信息矩陣進行分解，只不過不是通過顯式的SVD等技術(shù)，而是通過深度學(xué)習(xí)中的堆棧式自編碼器來學(xué)習(xí)其潛在表示， 在細致地調(diào)節(jié)其參數(shù)時，可以獲得不錯的效果。至于SDNE，精心對深度學(xué)習(xí)模型的參數(shù)進行調(diào)整后，在某些數(shù)據(jù)集上，它擁有著最佳的表現(xiàn)(SDNE在BlogCatalog)，但是復(fù)雜深度學(xué)習(xí)模型所擁有的參數(shù)過多，難以調(diào)節(jié)，運行時間較長等因素也會影響其應(yīng)用[15]。

表2 各類算法效果1

續(xù)表

表3 各類算法效果2

4 總結(jié)

本文研究了現(xiàn)有各種網(wǎng)絡(luò)表示學(xué)習(xí)算法，并分析各類算法在不同類型網(wǎng)絡(luò)中的性能。將這些算法利用SAE平臺實現(xiàn)后，在各類不同網(wǎng)絡(luò)數(shù)據(jù)集上進行了網(wǎng)絡(luò)節(jié)點的多標(biāo)簽分類任務(wù)評測，以此評估這些算法的效果，且對算法的效率、使用范圍、性能等進行了分析。