基于用戶導向的異構網絡語義預測算法研究

王少峰，郭俊霞，盧 罡

北京化工大學 信息學院，北京 100029

1 引言

隨著信息網絡的快速發展，對信息網絡的分析已成為一個重要的研究方向，包括信息檢索、數據挖掘、社交網絡、關系預測等等。信息網絡是一種將有向圖作為基本數據結構的網絡，它對結點類型和關系類型進行了明確的區分。如果它只包含一種類型的結點和一種類型的關系，則稱為同構網絡；如果包含多種類型的結點和多種類型的關系，則被稱為異構網絡。現實的信息網絡往往很復雜，包含很多種類型的結點和關系，所以對異構網絡的研究十分重要。

隨著異構網絡的信息量與日俱增，用戶在搜索感興趣的信息時耗費大量時間與精力。相似性搜索作為異構網絡數據挖掘的一種基本方法，能夠幫助用戶快速準確地搜索所需要的信息。為此，有許多相似性度量方法被提出，大致可以分為以下三類：（1）基于結點特征的相似性度量[1-2]：網絡中的結點包含一系列特征，結點間的相似性可以通過特征相似性來進行計算。這些方法適用于特征豐富的相同類型結點，不能用于計算不同類型結點間的相似性。（2）基于圖特性的相似性度量[3-4]：通過特征子圖、分類圖等圖拓撲概念計算相似性，將結點間的相似性轉化為與結點有關的圖結構相似性計算得到。（3）基于元路徑的相似性度量[5-7]：通過遞歸地計算結點鄰居間相似性，最終得到全局相似性。如文獻[5]基于“如果兩個結點和被其相似的結點所引用，那么這兩個結點也相似”的思想，提出SimRank算法。這類算法是基于結點結構的上下文，從全局路徑出發計算相似性，需要計算的路徑數非常多，帶來計算量大的問題，無法擴展到大規模數據集中。

在相似性搜索中，基于用戶導向去預測與用戶搜索相關的路徑，是減少路徑選擇數的重要參考依據。文獻[8]中對于需要聚類的目標，用戶只需要提供小部分與目標相關的特征集，便可根據該特征集找到相似的結點。文獻[9]通過考慮用戶對不同搜索結果的滿意程度，建立修改度量系數的目標函數，從而實現微博中體現用戶興趣的主題時序相似性計算，為用戶提供更好的搜索結果。針對基于元路徑的相似性搜索算法普遍存在計算量大的問題，基于利用用戶導向預測與用戶搜索相關的路徑，以減少路徑數的考慮，本文擬進行基于用戶導向的語義預測算法研究。本文的主要貢獻為：

（1）從圖拓撲結構的角度出發，提出一種基于用戶導向進行語義預測的算法。該算法可用于同類型和不同類型結點間的語義預測，并通過語義預測減少了元路徑選擇數，緩解了計算量大的問題。并且不需要用戶具備相關專業知識，對用戶是友好的。

（2）為在多語義路徑上計算相似性提供一種實現方法。本文根據預測過程所得到的概率作為多語義路徑的權重，對多語義路徑上的相似性分數進行加權組合。

（3）本文實驗表明，通過與實際情況進行比較，本文算法在對稱與非對稱路徑上均能夠對結點間的語義進行準確預測，并且在多語義環境下的排名結果質量明顯好于對應算法。

2 相關研究

針對基于元路徑的相似性度量方法存在路徑選擇數多的問題，已有一些研究成果，包括針對SimRank的算法改進[10-11]，路徑依賴隨機行走[12]法等。文獻[10]通過理論上界分析，將每次迭代計算后不可能進入Top-k候選集的節點對鎖定，從而在精確度損失不大的情況下大幅提升計算時間。文獻[11]提出SimRank的線性遞歸表達式，結合蒙特卡洛模擬方法、距離的衰減特性、適應性選樣技術使得搜索的時間復雜度獨立于圖的規模，方便進行并行計算，使得計算大規模的圖成為可能。但這些算法只能應用于同構圖中，無法應用于異構網絡計算不同類型結點間的相似性。文獻[12]提出一個路徑依賴隨機游走（PCRW）算法，用于度量一個由文獻庫中元數據組成的有向圖中的結點相似性。其相似度被定義為一個已知的約束隨機行走的組合，每個約束只遵循遠離搜索結點的邊標簽的一個特定序列。該算法具有非對稱屬性，可用于計算不同類型結點間的相似性。也因為其非對稱屬性，不能用于計算同類型結點相似性。

還有一些文獻提出根據用戶的專業知識來選擇與搜索相關的某一條具體的路徑，即單路徑。文獻[6，13]提出PathSim算法用于計算相同類型結點間的相似性。該算法基于單個對稱元路徑，雙向隨機游走，通過可交換矩陣，計算相同類型結點間的相似性。用戶需要根據自己掌握的相關領域知識來選擇單個路徑。該算法只能用于計算同類型結點，不能用于不同類型結點。文獻[7]提出HeteSim算法用于計算不同類型結點間的相似性。該算法基于單個對稱元路徑，雙向隨機行走，計算異構網絡中不同類型實體間的相似性。同樣的，用戶需要根據自己掌握的相關領域知識來選擇單個路徑。文獻[14]提出在HeteSim基礎上的矩陣分解方法，可以得到結點的軟聚類或硬聚類結果，以此進一步縮小路徑的選擇范圍。在這些方法中，用戶可以根據自己的專業知識來選擇相應的單路徑，減少了路徑選擇的數量，減小了計算量，但要求用戶對相關領域專業知識的理解較高，具有一定局限性。

通過引入用戶導向，預測與用戶搜索相關元路徑的方法[15-20]也可以用來改善路徑選擇數大的問題，而且在用戶滿意度方面表現更好。其中包括幾類算法：利用種子的半監督算法[15-16]、關系預測算法[17-18]，和監督與半監督組合算法[19-20]。利用種子的半監督算法是在半監督的基礎上，將用戶提供的標簽樣例和未提供標簽的樣例結合起來，進一步提高檢索效率。關系預測算法是在用戶輸入搜索和導向的情況下，根據輸入之間的關系，利用建好的預測算法去預測搜索與路徑之間的相似概率。監督與半監督組合算法分別克服了監督學習需要大量標注語料以及半監督學習標注語料受限于一定應用環境的缺點，可以在少量標注語料的情況下方便快捷地移植到其他標注語料受限的應用環境中。但這些算法主要適用于同構網絡或異構網絡中的同類型結點。在異構網絡不同類型結點上的語義預測仍有待進一步研究。

文獻[4]利用最大公共子圖和最小公共超圖等圖結構信息的方法與PathSim的結果集合有相當數量是重合的，表明了該文所提方法確實能有效度量各節點的相似程度。在文獻[3]中進一步表明，利用類圖信息所得到的結點相似性的準確性相較基于元路徑所得實體相似性的準確性要好很多。由于利用圖的結構信息不需要用戶的專業知識，并且圖中可以包含有不同類型的結點，再基于以上文獻的實驗結果，可以得出以下結論：利用圖的結構信息來對不同類型和相同類型結點間的語義進行預測是可行的。

本文從用戶導向的角度出發，提出一個面向異構網絡、基于用戶導向的語義預測算法。該算法不僅考慮同類型結點，同時也考慮不同類型結點。該算法不需要用戶具備一定的專業知識，而是利用圖的結構信息，計算用戶搜索匹配各相關路徑的概率，通過選擇概率最大的路徑，可以減少候選路徑數，從而減小計算量。同時，可預測得到各相關路徑的概率，為多語義環境下計算相似性提供一種具體實現方法。

3 用戶導向-語義預測算法

由于異構網絡中語義的多樣性，用戶搜索往往含有歧義性，所以需要更好地理解用戶搜索意向，以減少路徑選擇數。例如，在圖1所示的網絡中，作者和會議之間可以通過“Author-Paper-Venue-Conf”（APVC），“Author-Paper-Venue-Subj-Paper-Venue-Conf”（APSPVC）等路徑來連接。其中，APVC路徑表示作者寫的文獻發表在會議上，著重于作者參加的會議；而APSPVC路徑表示在會議中發表的文獻，這些文獻與作者發表的文獻有相同主題，著重于與作者文獻有相同主題的其他會議文獻。所以，在度量結點相似性之前，先進行語義預測，降低語義歧義性，可減少候選路徑數。

圖1 ACM數據集網絡模式

3.1 異構網絡的相關定義

Han和Yu等人在文獻[21]和文獻[22]中正式提出和倡導信息網絡這一概念，并探索信息網絡的元結構，即網絡模式，同時提出元路徑的概念。利用元路徑所包含的語義來查找用戶搜索的信息，是相似性搜索領域一個主要的研究方向。本文在前人提出的信息網絡、網絡模式、元路徑和基于用戶導向的相似性搜索定義基礎上，提出以下兩個定義。

定義1路徑回溯

在一個數據集中，對于一個搜索q，在某個語義下，可以得到一系列相關或不相關結果集，則訓練集可以形式化為：D=(qii=1,2,…,N ，其中是正相關結果集，q-i是不相關結果集。直觀上，可以知道：有相似結果的搜索應該有相似的語義，而有不相似結果的搜索應該有不同的語義。對于D中的一個候選結果r（用戶導向），正相關搜索可以收集并定義為不相關搜索為。則該候選結果r和正相關搜索所對應的語義，就是用戶搜索隱含的候選路徑。

定義2正則路徑數

本文定義正則路徑數來表示網絡中兩個結點的整體連通性，表示如下：

其中P(qi,ui)表示在候選路徑下搜索qi到用戶導向ui的路徑實例數，P(qi,)表示在候選路徑下從結點qi開始的路徑實例數，P(, ui)表示在候選路徑下到達結點ui的路徑實例數，l表示路徑長度。

3.2 語義預測過程

在進行語義預測前，首先準備一個數據集，數據集是以搜索的格式準備的。然后對這個數據集使用路徑回溯方法，得到與用戶搜索相關的所有候選路徑。在此基礎上，統計搜索和導向在各候選路徑上的路徑實例數。然后將各路徑上的路徑實例數代入公式（1），得到對應路徑上的正則路徑數。

由于語義之間的含義不同，可以把語義預測看作一個多分類問題。Softmax模型是logistic回歸模型在多分類問題上的推廣，可以用來對語義預測問題進行概率建模。在多分類問題中，類標簽可以取兩個以上的值。本文中，自變量是語義路徑的正則路徑數，因變量是搜索匹配該語義路徑的概率。具體形式如公式（2）所示：

p(S=j|qi,ui,θ)表示基于用戶導向ui和搜索qi屬于語義 j的概率，k是對應語義數，其中xji是路徑 j的正則路徑數對概率分布進行歸一化，使得所有概率之和為 1。

為了得到搜索匹配各候選路徑的最優概率θj，本文訓練模型參數θ，使其能夠最小化代價函數 ：

1{值為真的表達式}=1，1{值為假的表達式}=0。

對于J(θ)的最小化問題，由于J(θ)不是嚴格非凸的，回歸中對參數的最優化求解不只一個。為了求出唯一解，使得J(θ)成為一個嚴格凸函數，通過添加一個權重衰減項來修改代價函數。有了這個權重衰減項以后(λ＞0)，代價函數就變成了嚴格的凸函數，這樣就可以保證得到唯一的解。并且因為J()θ是凸函數，利用梯度下降法等優化算法可以保證收斂到全局最優解。現在代價函數變為：

為了使用優化算法，需要求得這個新函數J()θ的導數，如下：

有了上面的偏導數公式以后，就可以將它代入到優化算法中。本文使用梯度下降法來實現最優概率θj。在梯度下降法的標準實現中，每一次迭代需要進行如下更新：

當迭代一定次數后，得到最優的θj，進而得到最優θ。其中α表示沿梯度下降方向的步長。在得到最優的θ后，選擇最大的分量θj，利用相似性算法公式對相應的路徑進行計算，給出最終結果。

3.3 算法描述

首先基于用戶搜索q和導向u，得到各候選路徑的正則路徑數，然后利用softmax函數得到搜索q匹配各候選路徑的初始概率。再利用優化算法求出搜索q匹配各候選路徑的最優概率，最后代入softmax函數得到最終概率。具體過程如算法1所示。

算法1語義預測算法

輸入：用戶搜索q，用戶導向u，圖S=( )A,R

輸出：搜索q匹配相關語義的概率列表result

1. for eachq，u do

2. 路徑回溯（q，u）->Pl(q , u)；

3. Pl(q ,u)->xl(q , u)；

4. end for

5.for allxl(q ,u ) do

6. p(S=j|q,u,θ)；

7.end for

8.for each xl(q ,u ) do

9. J(θ)；

10. repeat

11. ?θjJ(θ)；

12. θj=θj-α?θjJ(θ)；

13. until迭代次數>107

14. end

15. end for

16.for allθjdo

17. p(S=j|q,u,θ)；

18.return result{θopt}其中，Pl( )

q,u是在路徑 j上的路徑實例數。p(S=j|q,u,θ)表示基于用戶導向u，搜索q屬于語義 j的概率。?θjJ()θ是利用梯度下降法來求最優概率θopt。

4 實驗

4.1 實驗數據集

本文使用DBLP數據集作為實驗對象，其中包含1 928 000個文獻，109 000個作者，1 000個會議和193 000個關鍵字，以及總共4 244 000個關系。它的網絡模式如圖2所示。

圖2 DBLP網絡模式

4.2 實驗設計

考慮到實驗環境對路徑步長的影響，為了能得到有效的正則路徑數，本實驗的路徑步長控制在4步之內，路徑語義如表1所示。

為了驗證本文提出算法的有效性，設計如下三個實驗問題：

（1）基于用戶導向的語義預測算法能否準確預測用戶搜索意向

表1 DBLP數據集4步長路徑語義表

預測算法通過所給的搜索和導向，得到搜索屬于各候選路徑的最終概率。當選擇概率最大的路徑時，與實際選擇情況進行比較，驗證是否能準確預測。

（2）多語義路徑下的排名是否比單語義路徑的排名更準確

為了得到更為準確的結果，文獻[7]和文獻[13]都曾提出在多語義環境下計算相似性，但沒有給出解決方法。本文利用用戶搜索與導向在各語義路徑下的概率作為該路徑下的權重，然后將相似性算法在各相關路徑上的相似性分數進行加權組合，得到多語義路徑上的相似性分數，再與原相似性算法的相似性分數進行比較。

（3）本文算法與對應相似性算法的效率對比

本文實驗中將對本文算法與對應算法的效率進行實驗比較與分析。

4.3 實驗結果分析

4.3.1 算法時間復雜度分析

本文算法主要分為路徑回溯、語義預測兩部分。在路徑回溯部分，由于是對搜索和用戶導向結點雙向回溯，算法的時間復雜度為O()n2。在語義預測部分，用到的是調整的softmax函數，時間復雜度為O()n。在對該算法的參數θ進行優化時使用了梯度下降法，梯度下降法的時間復雜度為O(tn)，t表示迭代次數。所以本算法的時間復雜度為O(n2+(t +1) n)，而HeteSim算法的時間復雜度為O(k dn2T4)，其中k表示迭代次數，d表示結點出度和入度乘積的平均值，T表示結點類型數；PathSim算法的時間復雜度為O(n2)。

4.3.2 實驗參數的選擇

迭代步長只影響速度，不影響收斂性。在梯度下降法中，往往需要設置一個合適的步長。步長設置太大，使得要估計的系數在迭代過程中不斷增大，最后趨于無窮大，程序陷入死循環或溢出；太小可能永遠到不了最優點。由相關證明文件（http://research.cs.buct.edu.cn/WDBLab/Appendix.pdf）可知，當假定正則項系數λ=1時，步長α在（0，2）范圍內對所有預定義路徑來說是比較合適的。并且迭代達到1 000萬次時，迭代停止。本實驗中，設定迭代步長的初始值為0.1（因為各路徑的初始概率值就比較低，步數設置太大時最優解會出現負數，也就意味著步數太大導致越過了最優解），每次迭代步長的值由下面公式確定：

α=α*0.8

4.3.3 與其他算法的比較

PathSim[13]和HeteSim[7]是異構網絡中兩個經典的相似性搜索算法。它們都是基于單個元路徑，計算異構網絡中實體間的相似性。對于一個對稱元路徑P=(Pl)，算法PathSim和HeteSim都可以應用在該元路徑上，而對于非對稱元路徑，HeteSim可以應用。本實驗中，分別在對稱與非對稱元路徑上與上述算法進行比較。

在對稱路徑上，給出一個用戶搜索Christos Faloutsos和導向Spiros Papadimitriou，結果如表2和表3所示。

表2 路徑APA上，用PathSim得到的Top-10與Christos Faloutsos最相似的作者

表3 路徑APA上，用HeteSim得到的Top-10與Christos Faloutsos最相似的作者

現實中，Spiros Papadimitriou是Christos Faloutsos的共作者，所以用戶搜索隱含的語義是找到Christos Faloutsos的其他共作者。所以PathSim和HeteSim算法所走路徑都是APA。而在用預測算法進行預測時，在定義路徑APA、APVPA和APTPA上的歸一化概率如表4所示。其中概率最大的路徑為APA，概率為0.433 8。選擇概率最大路徑為APA，與PathSim和HeteSim相符；而當選擇組合路徑時，各路徑權重即為上述概率。

表4 基于不同導向，作者Christos Faloutsos在對稱元路徑上的匹配概率

而對于同一個搜索Christos Faloutsos，此時給出的導向是Philip S.Yu，結果如表5和表6所示。

現實中，Philip S.Yu是在數據挖掘領域與Christos Faloutsos名聲相當的作者，所以用戶搜索隱含的語義是找到與Christos Faloutsos在數據挖掘領域名聲相當的其他作者。所以HeteSim算法所走路徑是APVPA。而在用預測算法進行預測時，在定義路徑APA、APVPA和APTPA上的歸一化概率如表4所示。其中概率最大的路徑為APVPA，其概率為0.581 5。選擇概率最大路徑為APVPA，與PathSim和HeteSim相符；而當選擇組合路徑時，各路徑權重即為上述概率。

表5 路徑APCPA上，用PathSim得到的Top-10與Christos Faloutsos最相似的作者

表6 路徑APVPA上，用HeteSim得到的Top-10與Christos Faloutsos最相似的作者

在非對稱路徑上，給出一個用戶搜索Christos Faloutsos和導向KDD，結果如表7所示。

表7 路徑APC上，Top-10與作者相關的會議

現實中，KDD是Christos Faloutsos主要參加的會議，所以HeteSim可以根據用戶的專業知識去選擇特定的元路徑APC。而在用預測算法進行預測時，在定義路徑APC，和APTPC上的歸一化概率如表8所示。其中概率最大的路徑為APC，其概率為0.600 3。概率最大路徑為APC，與HeteSim相符；而當選擇組合路徑時，各路徑權重即為上述概率。

表8 基于用戶搜索Christos Faloutsos和導向KDD的各路徑概率

根據以上實驗，可以得出下面兩個結論：

（1）基于用戶導向，由語義預測算法得到概率最高的路徑與實際選擇的路徑是相同的，說明預測算法能夠準確地對用戶搜索意向進行預測。

（2）本實驗利用用戶搜索與導向在各語義路徑下的概率作為該路徑下的權重，然后將PathSim和HeteSim在各相關路徑的相似性分數進行加權組合，分別與PathSim和HeteSim進行比較。由表2和表3可以看到，當給出用戶搜索Christos Faloutsos和導向Spiros Papadimitriou時，多語義路徑下的得分比PathSim和HeteSim高。但在給出用戶搜索Christos Faloutsos和導向Philip S.Yu時，得分比PathSim和HeteSim低。這是由于多語義路徑下對語義的區分度不高，勢必會將相關語義的得分拉低，同時將不太相關語義的得分拉高，造成了多語義路徑得分并不一定總是比單語義路得分高。同時也說明了相似性得分只是評價相似性度量的一個方面，還需要對實際的排名質量進行比較。

4.3.4 排名的質量比較

為了比較排名結果的質量，本文使用DCG指標[23]來評價本文方法和其他算法分別在對稱路徑APA、APTPA、APCPA和非對稱路徑APC，APTPC上搜索Christos Faloutsos的表現。

在本文實驗中，將實驗結果按1～10進行打分。10分表示排名最好的結果，1分表示排名最差的結果。

在APA路徑上，PathSim和HeteSim與本文方法的DCG分數如圖3所示。

圖3 APA路徑上，本文方法與PathSim、HeteSim的DCG分數

在APCPA路徑上，PathSim和HeteSim與本文方法的DCG分數如圖4所示。

圖4 APCPA路徑上，本文方法與PathSim、HeteSim的DCG

在APC路徑上，HeteSim和本文方法的DCG分數如圖5所示。

圖5 APC路徑上，HeteSim和本文方法的DCG分數

可以看到，在對稱路徑和非對稱路徑上，本文方法在原有相似性算法的基礎上，利用多語義環境下的相似性分別與PathSim和HeteSim進行了比較，都表現出了較好的性能。說明雖然多語義路徑下的得分不一定比單語義路徑得分高，但排名質量是好于單語義路徑的。

4.3.5 算法效率對比

為了比較本文算法和對應算法的效率，本文將在對稱路徑和非對稱路徑上搜索Christos Faloutsos的運行時間進行比較。

在APA路徑上，基于用戶導向Spiros Papadimitriou，PathSim和HeteSim與本文方法的運行時間如圖6所示。

圖6 APA路徑上，本文方法與PathSim、HeteSim的運行時間

在APCPA路徑上，基于用戶導向Philip S.Yu，PathSim和HeteSim與本文方法的運行時間如圖7所示。

在APC路徑上，基于用戶導向KDD，HeteSim和本文方法的運行時間如圖8所示。

圖7 APCPA路徑上，本文方法與PathSim、HeteSim的運行時間

圖8 APC路徑上，本文方法與PathSim、HeteSim的運行時間

由以上實驗可以看到，本文算法的運行時間高于對應算法。這是由于本文首先基于用戶導向對搜索在各語義路徑下的匹配概率進行預測，并將概率作為對應路徑上的權重，然后利用相似性算法在各對應路徑上計算得到的相似性分數進行加權組合，即本文方法的運行時間包括語義預測和相似性計算兩部分。而且本文算法在預測部分為了得到準確的預測結果，需要進行迭代更新，當迭代次數逐漸增加時，本文算法與對應算法之間的運行時間差距會逐步增大。因此需要在運行時間和結果準確性之間進行權衡。

5 結束語

本文提出的用戶搜索導向-語義預測算法，可用于同類型和不同類型結點間的語義預測，能夠較好地預測用戶搜索的語義，且不需要用戶具備相關專業知識。并且本算法減少了元路徑選擇數，以一種新的方法緩解了計算量大的問題。本文根據預測過程所得到的概率作為多語義路徑的權重，為多語義環境下的相似性計算提供了具體的實現方法。實驗表明，本文提出的算法能夠準確對同類型和不同類型結點間語義的預測，在排名質量上好于對應的相似性算法。