基于異構關系分布的學術網絡相似性搜索

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

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

0 引言

近年來，基于學術網絡的相似性搜索已經在學術搜索、合作關系預測等領域引起廣泛關注。學術網絡中的相似性搜索旨在從海量的學術數據中發現相似的對象。相似性搜索的關鍵是有效的相似性度量，在學術網絡中，相似性度量側重于評估同一類型對象間的相似性，例如學術網絡中與給定作者相似的作者或與給定論文相似的論文。在數據化時代，學術網絡逐漸呈現大規模化和復雜化，增加了相似性度量的難度。如何快速、有效地實現多數據源對象匹配，幫助用戶從大規模數據中識別出其感興趣的內容具有重要的研究意義。

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

1 相關工作

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

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

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

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

2.1 符號與問題定義

學術網絡中對象與關系構成了不同類型的鏈接，可被視為異構網絡。如圖1 所示的學術網絡包括作者、論文、會議等類型對象，以及引用、發表、被發表等多個類型的鏈接關系。

Fig.1 academic network and network model圖1 學術網絡與網絡模式

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

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

2.2 關系特征矩陣構建

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

關系特征矩陣是根據不同類型對象的分布特征，統計分析獲得的。依據GRM 中的定義，關系特征矩陣表示為：

2.3 相似性度量算法

2.3.1 基于鏈接的相似性度量

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

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

2.3.2 TopSim算法擴展

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

2.3.3 top-k相似搜索

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

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

3 實驗結果與分析

3.1 實驗數據

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

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

3.2 評估方法

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

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

3.3 實驗結果

3.3.1 MAP值

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

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

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

Fig.2 MAP corresponding to different parametersk圖2 不同參數k對應的MAP

Fig.3 MAP corresponding to different parameters l圖3 不同參數l對應的MAP

Fig.4 MAP corresponding to different parameters μ圖4 不同參數μ對應的MAP

3.3.2 案例研究

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

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

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

案例研究表明，本文提出的方法不僅在MAP 指標上提升了相似搜索效果，而且能夠從真實學術異構網絡中查找到符合人們常規認知的相似對象。

3.3.3 效率

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

Fig.5 Query time corresponding to different parameters μ圖5 不同參數μ對應的查詢時間

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

Fig.6 Query time corresponding to different parameters l圖6 不同參數l對應的查詢時間

4 結語

本文從學術網絡復雜化和大規模化的現狀出發，提出一種基于異構關系分布特征的相似性搜索方法。與現有方法相比，該方法考慮了網絡的異構關系數據分布特征。通過對不同類型的對象數據規模進行統計分析，得到關系特征矩陣。基于關系特征矩陣擴展TopSim 算法實現大規模學術網絡上的相似性搜索。同時，為了節省計算開銷，設置閾值篩選來減少不必要的計算操作，以實現快速的查詢處理。在真實數據上開展大量實驗，結果表明，當考慮數據構成及其分布特點時，在保證查詢效率的基礎上，查詢結果的準確率平均提升了7.25%。