喬 田，張明西，王金華，周 飛，劉 洲，羅 睿，吳 玉

（1.上海理工大學(xué) 出版印刷與藝術(shù)設(shè)計學(xué)院，上海 200093；2.中國電子科技集團公司第三十二研究所，上海 201808；3.江蘇國信靖江發(fā)電有限公司，江蘇 泰州 214513；4.中國人民解放軍軍事科學(xué)院，北京 200023）

0 引言

近年來，基于學(xué)術(shù)網(wǎng)絡(luò)的相似性搜索已經(jīng)在學(xué)術(shù)搜索、合作關(guān)系預(yù)測等領(lǐng)域引起廣泛關(guān)注。學(xué)術(shù)網(wǎng)絡(luò)中的相似性搜索旨在從海量的學(xué)術(shù)數(shù)據(jù)中發(fā)現(xiàn)相似的對象。相似性搜索的關(guān)鍵是有效的相似性度量，在學(xué)術(shù)網(wǎng)絡(luò)中，相似性度量側(cè)重于評估同一類型對象間的相似性，例如學(xué)術(shù)網(wǎng)絡(luò)中與給定作者相似的作者或與給定論文相似的論文。在數(shù)據(jù)化時代，學(xué)術(shù)網(wǎng)絡(luò)逐漸呈現(xiàn)大規(guī)?；蛷?fù)雜化，增加了相似性度量的難度。如何快速、有效地實現(xiàn)多數(shù)據(jù)源對象匹配，幫助用戶從大規(guī)模數(shù)據(jù)中識別出其感興趣的內(nèi)容具有重要的研究意義。

目前，相似性度量方法主要分為兩類：基于內(nèi)容的相似性度量和基于鏈接的相似性度量。與基于內(nèi)容的相似性度量相比，基于鏈接的相似性度量更加符合人類的直觀判斷。當(dāng)前已有大量工作利用網(wǎng)絡(luò)的全局結(jié)構(gòu)信息計算節(jié)點間的相似性，例如RWR［1］、P-Rank［2］、SimRank［3］等。這些方法通常采用隨機游走算法進行迭代計算，盡管能夠得到理想的結(jié)果，但是時間和空間復(fù)雜度較高。大量工作提出優(yōu)化技術(shù)［4-8］以減少計算開銷，但其主要針對同構(gòu)網(wǎng)絡(luò)。本文研究了學(xué)術(shù)網(wǎng)絡(luò)中的top-k相似性計算，旨在進行相似性計算時考慮節(jié)點間的異構(gòu)關(guān)系，并有效降低相似性計算的時間和空間成本。

1 相關(guān)工作

相似性度量評估了網(wǎng)絡(luò)中對象間的相似度，是許多數(shù)據(jù)挖掘任務(wù)的基礎(chǔ)。同質(zhì)網(wǎng)絡(luò)中的對象間相似度已被廣泛研究。SimRank［3］是一種典型的相似度計算算法，基于“相似的節(jié)點被相似節(jié)點引用”的思想，利用網(wǎng)絡(luò)上下文結(jié)構(gòu)迭代計算相似度。SimRank 在近期引起了廣泛關(guān)注，并出現(xiàn)了一系列變種，包括P-Rank［2］、C-Rank［9］、RG-Sim-Rank［10］等。其中，P-Rank 和C-Rank 考慮了不同方向鏈接關(guān)系對相似度的貢獻，RG-SimRank 通過構(gòu)建隨機游走圖整合任意方向和任意步長的相遇概率。針對SimRank 的效率問題，研究者提出一些優(yōu)化方法用于快速計算。Top-Sim 從top-k搜索角度優(yōu)化SimRank，其枚舉了所有隨機路徑，以避免在SimRank 計算時訪問整張圖，適用于大規(guī)模圖［4］；ProbeSim 算法根據(jù)反向游走計算SimRank［11］；CrashSim 在ProbeSim 算法基礎(chǔ)上計算圖中所有頂點與查詢頂點的top-k結(jié)果集［12］。然而，這些方法針對的是同構(gòu)信息網(wǎng)絡(luò)，沒有考慮多類型鏈接關(guān)系。

近年來異構(gòu)網(wǎng)絡(luò)中的相似性搜索得到了廣泛關(guān)注。PathSim［13］首次提出元路徑的概念，通過特定元路徑的對稱路徑實例度量相同類型對象的相似度。許多學(xué)者提出基于元路徑的方法，包括HeteSim［14］、AvgSim［15］、RelSim［16］等。HeteSim 通過元路徑實例度量相同或不相同類型對象之間的相似度；AvgSim 改進了HeteSim 算法，該算法通過沿著給定元路徑和反向元路徑的兩個隨機游走過程評估相似度值；RelSim 基于元路徑，根據(jù)用戶提供的簡單關(guān)系實例測量異構(gòu)網(wǎng)絡(luò)中關(guān)系實例之間的相似度?；谟脩舳x元路徑的方法依賴于網(wǎng)絡(luò)模式，缺乏通用性。Net-Sim［17］和SimCC［18］僅處理x-star 模式的網(wǎng)絡(luò)，但當(dāng)網(wǎng)絡(luò)變得多樣化時并不適用。SimFusion 通過統(tǒng)一關(guān)系矩陣（URM）表示不同類型的關(guān)系，并通過URM 迭代計算對象間的相似度［19］。SimFusion+解決了SimFusion 的發(fā)散問題［20］。SimFusion 和SimFusion+只考慮當(dāng)前路徑長度的相遇，不能完全整合多類型關(guān)系。HeteRank 提出的通用關(guān)系矩陣（General Relationship Matrix，GRM）利用節(jié)點間的相遇整合所有關(guān)系類型［21］。

針對上述大多數(shù)相似度計算方法存在的各種問題，本文提出一種基于鏈接的相似性度量方法。首先，由于學(xué)術(shù)異構(gòu)網(wǎng)絡(luò)中不同類型對象的數(shù)據(jù)規(guī)模存在差異，節(jié)點間的關(guān)聯(lián)路徑由多種類型鏈接關(guān)系組成，利用全局異構(gòu)關(guān)系的分布規(guī)模統(tǒng)計分析得到關(guān)系特征矩陣。然后，基于關(guān)系特征矩陣擴展傳統(tǒng)的top-k相似性計算方法TopSim，使其適用于大規(guī)模異構(gòu)網(wǎng)絡(luò)［4］。同時，通過閾值篩選策略［22］加速查詢過程，返回最相似的k個節(jié)點。

2 基于鏈接的相似性度量算法

2.1 符號與問題定義

學(xué)術(shù)網(wǎng)絡(luò)中對象與關(guān)系構(gòu)成了不同類型的鏈接，可被視為異構(gòu)網(wǎng)絡(luò)。如圖1 所示的學(xué)術(shù)網(wǎng)絡(luò)包括作者、論文、會議等類型對象，以及引用、發(fā)表、被發(fā)表等多個類型的鏈接關(guān)系。

Fig.1 academic network and network model圖1 學(xué)術(shù)網(wǎng)絡(luò)與網(wǎng)絡(luò)模式

定義1異構(gòu)網(wǎng)絡(luò)：異構(gòu)網(wǎng)絡(luò)［13］表示為有向圖G=(V，E)，網(wǎng)絡(luò)中每個節(jié)點v∈V，Xi類型的節(jié)點集合由Vi表示。Eij表示Vi與Vj間關(guān)系Rij的鏈接集合。G具有對象類型映射函數(shù)Φ：V→Λ 和關(guān)系映射函數(shù)Ψ：E→R，其中|Λ|＞1 或|R|＞1。每個對象Φ(v)∈Λ 屬于一個特定對象類型Φ(v) ∈Λ。每個邊e∈E屬于特定關(guān)系Ψ(e)∈R。其中，用來描述異構(gòu)網(wǎng)絡(luò)的元結(jié)構(gòu)被稱作網(wǎng)絡(luò)模式，定義為TG=(Λ，R)，節(jié)點為對象類型Λ，邊為R中的關(guān)系。

top-k相似性搜索問題定義如下：給定查詢對象u和參數(shù)k，top-k相似性搜索的任務(wù)是找到k個與u最相似的對象，并將對象按照相似性分值由高到低排序后返回給用戶。對于返回序列中的v和不在序列中的v′，滿足s(u，v)≥s(u，v′)，其中s(u，v)是相似性度量函數(shù)。

2.2 關(guān)系特征矩陣構(gòu)建

關(guān)系的重要性與網(wǎng)絡(luò)中不同類型對象的規(guī)模有關(guān)［17］。GRM［21］是統(tǒng)一關(guān)系矩陣URM［19］的一種改進形式，優(yōu)勢在于能夠利用網(wǎng)絡(luò)不同類型對象的數(shù)據(jù)規(guī)模，依據(jù)異構(gòu)關(guān)系的分布進行統(tǒng)計分析，捕獲關(guān)系的重要性，避免了在進行URM 中涉及的關(guān)系重要性計算時繁瑣的人工定義過程。GRM 適用于復(fù)雜的異構(gòu)網(wǎng)絡(luò)，因此借鑒GRM 的思想構(gòu)建關(guān)系特征矩陣。

關(guān)系特征矩陣是根據(jù)不同類型對象的分布特征，統(tǒng)計分析獲得的。依據(jù)GRM 中的定義，關(guān)系特征矩陣表示為：

2.3 相似性度量算法

2.3.1 基于鏈接的相似性度量

SimRank［3］是一種經(jīng)典的鏈接相似性量算法，適用于任何具有鏈接的網(wǎng)絡(luò)。SimRank 算法將節(jié)點u與v之間的相似性值定義為s(u，v)，若u=v，則s(u，v)=1；否則：

其中，Rl(uv)表示在目標節(jié)點處結(jié)束的長度為l的相似路徑集合，Sn(u，v)是兩個隨機游走分別從節(jié)點u 和v 開始行走n步后第一次相遇的概率總和。

2.3.2 TopSim算法擴展

針對學(xué)術(shù)網(wǎng)絡(luò)對象間關(guān)聯(lián)路徑中不同類型的鏈接關(guān)系，引入關(guān)系特征矩陣擴展TopSim 算法，擴展后的算法可用于異構(gòu)網(wǎng)絡(luò)的相似性計算。在構(gòu)建關(guān)系特征矩陣時使用GRM 預(yù)先計算得到異構(gòu)鏈接關(guān)系權(quán)值，每條鏈接的權(quán)值表示從一個節(jié)點轉(zhuǎn)移到另一個節(jié)點的概率。[Pn]u，t、[]t，v表示分別從u和v出發(fā)沿 著路徑隨機游走n步長到節(jié)點t的轉(zhuǎn)移概率，根據(jù)公式（1），[P]u，t=ωij[pij]u，t，u∈Vi且t∈Vj。相似矩陣用S 表示，Sl(u，v)表示節(jié)點u和v之間的相似性。對于l≠0，可得到：

2.3.3 top-k相似搜索

擴展的TopSim 算法（EntSim）利用查詢節(jié)點n步內(nèi)結(jié)構(gòu)的上下文計算節(jié)點間的相似度，給定查詢節(jié)點u，從查詢點出發(fā)的兩個隨機游走分別表示為rw1和rw2。Set表示rw2經(jīng)過的相似路徑集合，假設(shè)rw1在第i步訪問節(jié)點u，Seti是rw2在第i步訪問的節(jié)點集合。對于每個節(jié)點v∈Seti，根據(jù)公式（8）計算Si(u，v)，并將(u，Si(u，v))存儲Smapi(u)中，通過Smapi(u)迭代計算相似性值。具體算法步驟如下：

在top-k搜索過程中，給定查詢節(jié)點u，假設(shè)n為最大隨機游走步數(shù)，D為節(jié)點的平均出度，l表示從u到v的步數(shù)。該算法僅需存儲查詢節(jié)點在n步內(nèi)的結(jié)構(gòu)上下文，空間復(fù)雜度為。Smapi(u)存儲查詢節(jié)點u的局部鄰域，在最壞的情況下，生成Dl個走了相同步數(shù)的Smapi(u)，其中Smapi(u)的大小為D2(n-l)。在真實數(shù)據(jù)集中，許多相似路徑是可以合并的，其中Smapi(u)的大小為D(n-l)，該算法的時間復(fù)雜度為O(nDn)。

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

3.1 實驗數(shù)據(jù)

實驗所用數(shù)據(jù)為開放學(xué)術(shù)圖譜（OAG）中的微軟學(xué)術(shù)圖譜MAG［23］。MAG 是索引1.11 億篇論文的有向引文圖的一個子集。MAG 是包含了論文（736 389 個節(jié)點）、作者（1 134 649 個節(jié)點）、機構(gòu)（8 740 個節(jié)點）和研究領(lǐng)域（59 965 個節(jié)點）以及節(jié)點之間有向關(guān)系的學(xué)術(shù)異構(gòu)網(wǎng)絡(luò)。實驗通過對MAG 原始數(shù)據(jù)集進行預(yù)處理來抽取數(shù)據(jù)，抽取后的學(xué)術(shù)異構(gòu)網(wǎng)絡(luò)包括31 548 個作者及其機構(gòu)數(shù)據(jù)，3 260 個論文及其研究領(lǐng)域數(shù)據(jù)以及158 183 條關(guān)系數(shù)據(jù)，從中選取1 000 個論文節(jié)點與作者節(jié)點來驗證查詢的準確率和效率。

依據(jù)現(xiàn)有基準（Ground Truth）選取方法［3，10］，實驗選取不參與計算的對象類型作為基準。在相似論文查詢時，選取與查詢論文研究領(lǐng)域相同的論文作為基準，將數(shù)據(jù)集中屬于｛論文，研究領(lǐng)域｝類型的邊去除，以避免影響準確率評估。例如，論文SimRank 所屬領(lǐng)域包含SimRank Compution、Similarity Search、Information Retrieval 等，其中Sim-Rank Compution 領(lǐng)域的論文包括PRSim、Simrank*、Sim-Rank++、TopSim 等，實際上這些論文的研究內(nèi)容是相關(guān)的。同樣的，在相似作者查詢時，將數(shù)據(jù)集中屬于｛作者，研究機構(gòu)｝類型的邊去除，選取與查詢作者相同研究機構(gòu)下的作者作為基準。

3.2 評估方法

實驗對比了TopSim 和EntSim，以觀察引入關(guān)系特征矩陣擴展和閾值過濾對相似性搜索性能的影響。實驗以MAG 數(shù)據(jù)集中論文和作者對象為例進行搜索，采用平均精度均值（Mean Average Precision，MAP）評估 top-k相似性度量結(jié)果的準確性。MAP 的定義為：

其中，n為處于相似性度量結(jié)果位置j時的相似對象數(shù)量，rel(j)表示位置j上的對象是否相關(guān)，不相關(guān)時取值為0，相關(guān)時取值為1。

3.3 實驗結(jié)果

3.3.1 MAP值

圖2 表示不同排序k對應(yīng)的MAP 值，其中步長l=5，閾值μ=0，0.01，0.05。通過觀察可知，隨著k的不斷增加，MAP 值呈不斷下降趨勢。因為查詢搜索到的弱相關(guān)對象也隨著k增加，MAP 值不斷下降。由圖可知，返回結(jié)果中排名較高的對象更相似，應(yīng)該接近給定的查詢，而排名較低的對象應(yīng)該在相似對象列表的相對后序位置，表明所提出方法返回的查詢結(jié)果具有合理的排序。

圖3 表示不同參數(shù)l對應(yīng)的MAP，其中，閾值μ=0，0.01，0.05。分別以論文和作者進行查詢，觀察MAP 值隨著步長發(fā)生的變化。從圖中可以看出，當(dāng)步長大于3時，MAP 值出現(xiàn)下降趨勢，造成這種現(xiàn)象的一部分原因是步長的增加產(chǎn)生了噪聲鏈接，進而影響相似性度量效果。步長l在2～3 時的MAP 值是最佳的，當(dāng)l超過4 時，相似度結(jié)果趨于收斂，因而不再變化。實驗結(jié)果表明，本文所提出方法的MAP 值明顯高于TopSim 算法。

圖4 表示不同閾值μ對應(yīng)的MAP，其中參數(shù)k=5，10，15。以論文和作者進行查詢，觀察MAP 隨著μ變化而發(fā)生的變化。通過觀察可知，隨著μ的增加，MAP值呈逐漸下降趨勢，這是因為相似性度量時忽略了低于μ的相似性值，影響了低值相似性對最終相似性值的貢獻。實驗結(jié)果表明，本文提出的修剪策略在忽略較低相似性的同時，對測試參數(shù)范圍內(nèi)查詢結(jié)果的精確度影響較小。

Fig.2 MAP corresponding to different parametersk圖2 不同參數(shù)k對應(yīng)的MAP

Fig.3 MAP corresponding to different parameters l圖3 不同參數(shù)l對應(yīng)的MAP

Fig.4 MAP corresponding to different parameters μ圖4 不同參數(shù)μ對應(yīng)的MAP

3.3.2 案例研究

以論文和作者對象作為查詢內(nèi)容進行案例研究，觀察返回結(jié)果中的前5 個對象，以驗證EntSim 的查找是否符合人們有關(guān)相似性的常規(guī)認知。

表1 是對隨機選取的論文和作者進行查詢后返回的前5 名相關(guān)結(jié)果。其中，第一篇目標論文“Distilling Word Embeddings：An Encoding Approach”涉及的主題有“word embedding”“neural networks”等。在返回的查詢結(jié)果中，排序第1 的論文主題包含“word embedding”“l(fā)inked data”等，排序為2 的論文包含的主題為“Domain-specific word embeddings”“word2vec”等。盡管排序為3 的論文并沒有涉及相關(guān)主題，但總體而言，論文3 的領(lǐng)域也是偏向于“embedding”的相關(guān)方向。第二篇目標論文包含的主題有“knowledge discovery”“classification”等。在查詢結(jié)果中，前兩篇都涉及主題“knowledge discovery”，與所查詢的論文主題相關(guān)。第1 位目標作者“Yehuda Koren”的研究方向主要是“數(shù)據(jù)挖掘”“推薦系統(tǒng)”等。在返回的結(jié)果中，排序為1 的作者“Chris Volinsky”的研究方向主要涉及“數(shù)據(jù)挖掘”“推薦系統(tǒng)”等；排序為2 的作者“Shawndra Hill”的研究方向主要涉及“知識發(fā)現(xiàn)”“數(shù)據(jù)挖掘”等；排序為3、4、5 的作者研究涉及不同方向。類似地，第2 位目標作者“Kevin Mc-Guinness”的研究方向主要是“圖像處理”“圖像分割”等，返回結(jié)果中前2 名作者的研究領(lǐng)域都涉及到了“圖像處理”方向，與所查詢的作者研究領(lǐng)域相關(guān)。

Table 1 Top-5 similar papers similar to given paper and author表1 與給定查詢論文及作者相關(guān)的前5名

案例研究表明，本文提出的方法不僅在MAP 指標上提升了相似搜索效果，而且能夠從真實學(xué)術(shù)異構(gòu)網(wǎng)絡(luò)中查找到符合人們常規(guī)認知的相似對象。

3.3.3 效率

圖5 表示不同閾值μ對應(yīng)的查詢時間，其中k=5，比較在進行相似論文和作者搜索實驗時μ在0～0.05 范圍內(nèi)的時間開銷。通過觀察可知，隨著μ的增加，計算時間明顯減少。因為在相似性度量時忽略了低于μ的低值相似性，減少了有關(guān)低值相似性所涉及的計算操作。實驗結(jié)果表明，通過對低值相似性進行閾值過濾，能夠有效降低相似搜索的在線查詢時間開銷。

Fig.5 Query time corresponding to different parameters μ圖5 不同參數(shù)μ對應(yīng)的查詢時間

圖6 表示不同步長l對應(yīng)的查詢時間，其中μ=0，0.01，0.05。比較在相似論文和作者搜索實驗中參數(shù)l在1～6 范圍內(nèi)的時間開銷。通過觀察可知，隨著步長l的增加，查詢時間呈快速上升趨勢，這是因為路徑數(shù)量隨著步長的增加呈指數(shù)級增長，進而影響相似搜索的時間開銷。本文所提出的方法通過設(shè)置閾值，顯著降低了時間開銷。事實上，由于相似性度量結(jié)果在l為4 時已經(jīng)收斂，在實際實施過程中可通過限制路徑長度的方式進一步降低時間開銷。實驗結(jié)果表明，本文所提出方法的在線查詢處理時間成本較低。

Fig.6 Query time corresponding to different parameters l圖6 不同參數(shù)l對應(yīng)的查詢時間

4 結(jié)語

本文從學(xué)術(shù)網(wǎng)絡(luò)復(fù)雜化和大規(guī)?；默F(xiàn)狀出發(fā)，提出一種基于異構(gòu)關(guān)系分布特征的相似性搜索方法。與現(xiàn)有方法相比，該方法考慮了網(wǎng)絡(luò)的異構(gòu)關(guān)系數(shù)據(jù)分布特征。通過對不同類型的對象數(shù)據(jù)規(guī)模進行統(tǒng)計分析，得到關(guān)系特征矩陣?；陉P(guān)系特征矩陣擴展TopSim 算法實現(xiàn)大規(guī)模學(xué)術(shù)網(wǎng)絡(luò)上的相似性搜索。同時，為了節(jié)省計算開銷，設(shè)置閾值篩選來減少不必要的計算操作，以實現(xiàn)快速的查詢處理。在真實數(shù)據(jù)上開展大量實驗，結(jié)果表明，當(dāng)考慮數(shù)據(jù)構(gòu)成及其分布特點時，在保證查詢效率的基礎(chǔ)上，查詢結(jié)果的準確率平均提升了7.25%。