原文鏈接：https://blog.csdn.net/Mrong1013967/article/details/115330139

HeteSim：異構(gòu)網(wǎng)絡(luò)中相關(guān)性度量的通用框架

摘要

相似性搜索是許多應(yīng)用中的一個(gè)重要功能，它通常側(cè)重于度量同一類(lèi)型對(duì)象之間的相似性。然而，在許多場(chǎng)景中，我們需要測(cè)量具有不同類(lèi)型的對(duì)象之間的相關(guān)性。隨著異構(gòu)網(wǎng)絡(luò)研究的興起，對(duì)不同類(lèi)型對(duì)象的相關(guān)性度量變得越來(lái)越重要。本文研究了異構(gòu)網(wǎng)絡(luò)中的相關(guān)搜索問(wèn)題，其任務(wù)是度量異構(gòu)對(duì)象（包括具有相同類(lèi)型或不同類(lèi)型的對(duì)象）的相關(guān)性。提出了一種新的度量方法HeteSim，該方法具有以下特點(diǎn)：（1）一致性度量：可以在一個(gè)統(tǒng)一的框架內(nèi)度量同一類(lèi)型或不同類(lèi)型對(duì)象之間的關(guān)聯(lián)性；（2）路徑約束性度量：基于兩個(gè)對(duì)象之間的搜索路徑，通過(guò)遵循一個(gè)序列來(lái)定義對(duì)象對(duì)之間的關(guān)聯(lián)性半度量測(cè)度：HeteSim具有一些良好的性質(zhì)（如自極大性和對(duì)稱(chēng)性），這些性質(zhì)對(duì)許多數(shù)據(jù)挖掘任務(wù)至關(guān)重要。分析了HeteSim的計(jì)算特點(diǎn)，提出了相應(yīng)的快速計(jì)算策略。實(shí)證研究表明，HeteSim能夠有效地評(píng)價(jià)異構(gòu)對(duì)象之間的相關(guān)性。

一、簡(jiǎn)介

相似性搜索是廣泛應(yīng)用中的一項(xiàng)重要任務(wù)，如web搜索[1]和產(chǎn)品推薦[2]。相似性搜索的關(guān)鍵是相似性度量，它評(píng)估對(duì)象對(duì)之間的相似性。對(duì)于傳統(tǒng)的分類(lèi)和數(shù)值數(shù)據(jù)類(lèi)型，如Jaccard系數(shù)和余弦相似性，相似性度量已經(jīng)得到了廣泛的研究。也有一些關(guān)于利用網(wǎng)絡(luò)中的鏈路信息來(lái)度量節(jié)點(diǎn)相似性的研究，如Personalized PageRank[3]、SimRank[4]和PathSim[5]。傳統(tǒng)的相似性度量研究主要集中在同一類(lèi)型的對(duì)象上。也就是說(shuō)，被測(cè)量的對(duì)象具有相同的類(lèi)型，例如“文檔到文檔”、“網(wǎng)頁(yè)到網(wǎng)頁(yè)”和“用戶(hù)到用戶(hù)”。對(duì)于不同類(lèi)型物體的相似性度量研究很少。也就是說(shuō)，被測(cè)量的對(duì)象是不同類(lèi)型的，例如“作者到會(huì)議”和“用戶(hù)到電影”。這是合理的。不同類(lèi)型物體的相似性有點(diǎn)違背我們的常識(shí)。此外，與同類(lèi)對(duì)象的相似性可以在同質(zhì)情況下（如同一特征空間或同質(zhì)鏈接結(jié)構(gòu)）進(jìn)行度量不同，不同類(lèi)型對(duì)象的相似性更是難以定義。

然而，不同類(lèi)型對(duì)象的相似性不僅有意義，而且在某些場(chǎng)景中也很有用。例如，作者J.F.naugton與SIGMOD的關(guān)系比KDD更密切。青少年可能更喜歡電影《哈利波特》，而不是《肖申克的救贖》。此外，在許多應(yīng)用中需要對(duì)不同類(lèi)型的對(duì)象進(jìn)行相似性度量。例如，在推薦系統(tǒng)中，我們需要知道用戶(hù)和電影之間的關(guān)系，才能做出準(zhǔn)確的推薦。在自動(dòng)輪廓提取應(yīng)用中，我們需要測(cè)量不同類(lèi)型對(duì)象的相關(guān)性，如作者和會(huì)議、會(huì)議和組織等。特別是隨著異構(gòu)信息網(wǎng)絡(luò)研究的出現(xiàn)[5]，[6]，研究不同類(lèi)型對(duì)象之間的關(guān)聯(lián)性不僅越來(lái)越重要，而且是可行的。異構(gòu)信息網(wǎng)絡(luò)是指包含多類(lèi)型對(duì)象和表示不同關(guān)系的多類(lèi)型鏈接的邏輯網(wǎng)絡(luò)[7]。例如，書(shū)目網(wǎng)絡(luò)包括作者、論文、會(huì)議、術(shù)語(yǔ)及其表示它們之間關(guān)系的鏈接。很明顯，異構(gòu)信息網(wǎng)絡(luò)無(wú)處不在，是現(xiàn)代信息基礎(chǔ)設(shè)施的重要組成部分[7]。因此，在這樣的網(wǎng)絡(luò)中提供對(duì)不同類(lèi)型對(duì)象的相關(guān)搜索功能是非常必要的，這是許多應(yīng)用的基礎(chǔ)。由于不同類(lèi)型的對(duì)象共存于同一網(wǎng)絡(luò)中，因此可以通過(guò)鏈接結(jié)構(gòu)來(lái)度量它們的相關(guān)性。

本文研究了異構(gòu)信息網(wǎng)絡(luò)中的相關(guān)搜索問(wèn)題。關(guān)聯(lián)搜索的目的是有效地度量異構(gòu)對(duì)象（包括具有相同類(lèi)型或不同類(lèi)型的對(duì)象）之間的關(guān)聯(lián)性。與相似性搜索只度量同類(lèi)型對(duì)象之間的相似性不同，關(guān)聯(lián)性搜索度量的是異構(gòu)對(duì)象之間的相關(guān)性，而不局限于同類(lèi)型對(duì)象。與信息檢索領(lǐng)域中的關(guān)系檢索[8]、[9]不同，這里的關(guān)聯(lián)搜索是在異構(gòu)網(wǎng)絡(luò)上進(jìn)行的，而異構(gòu)網(wǎng)絡(luò)是由對(duì)象的元數(shù)據(jù)構(gòu)成的。此外，基于以下原因，我們認(rèn)為一個(gè)理想的相關(guān)性度量應(yīng)該滿(mǎn)足對(duì)稱(chēng)性。（1） 對(duì)稱(chēng)度量在許多學(xué)習(xí)任務(wù)中更為通用和有用。雖然對(duì)稱(chēng)性在查詢(xún)?nèi)蝿?wù)中是不必要的，但是對(duì)于許多重要的任務(wù)，如聚類(lèi)和協(xié)同過(guò)濾，對(duì)稱(chēng)性是必不可少的。此外，它也是度量的必要條件。（2） 對(duì)稱(chēng)度量在許多應(yīng)用中更有意義，特別是對(duì)于異構(gòu)對(duì)象對(duì)的相關(guān)性。例如，在一些應(yīng)用程序中，我們需要回答這樣的問(wèn)題，比如誰(shuí)對(duì)會(huì)議SIGIR的重要性與J.F.naugton對(duì)SIGMOD的重要性相似。通過(guò)比較對(duì)象對(duì)之間的相關(guān)性，我們可以推斷出它們的相對(duì)重要性。然而，它只能通過(guò)對(duì)稱(chēng)測(cè)度來(lái)實(shí)現(xiàn)，而不能通過(guò)非對(duì)稱(chēng)測(cè)度來(lái)實(shí)現(xiàn)。可以通過(guò)圖1所示的示例來(lái)解釋。對(duì)于對(duì)稱(chēng)測(cè)度，我們可以推斷W.B.Croft1對(duì)SIGIR的重要性與J.F.Naughton2對(duì)SIGMOD的重要性相同，因?yàn)樗鼈兊年P(guān)聯(lián)度很接近。假設(shè)我們知道J.F.諾頓是SIGMOD中一位有影響力的研究者，我們可以得出結(jié)論，W.B.克羅夫特也是SIGIR中一位有影響力的研究者。然而，我們不能從如圖1（b）所示的不對(duì)稱(chēng)度量中推斷出相對(duì)重要性信息。從作者與會(huì)議、會(huì)議與作者的關(guān)系中，我們會(huì)得出相互矛盾的結(jié)論。

盡管異構(gòu)網(wǎng)絡(luò)中的關(guān)聯(lián)搜索有著重要的價(jià)值和意義，但到目前為止還很少有人對(duì)其進(jìn)行研究。它面臨著以下研究挑戰(zhàn)。（1） 異構(gòu)網(wǎng)絡(luò)比傳統(tǒng)的同構(gòu)網(wǎng)絡(luò)復(fù)雜得多。在異構(gòu)網(wǎng)絡(luò)中，不同類(lèi)型的對(duì)象和鏈接共存于一個(gè)網(wǎng)絡(luò)中，具有不同的語(yǔ)義。作為圖2（b）所示的書(shū)目示例（更多細(xì)節(jié)見(jiàn)第V.A節(jié)），它包括作者、論文、術(shù)語(yǔ)和會(huì)議類(lèi)型。“作者論文”是指作者撰寫(xiě)的論文，而“論文會(huì)議”是指在會(huì)議上發(fā)表的論文。如果不考慮類(lèi)型和語(yǔ)義的差異，混合不同類(lèi)型的對(duì)象來(lái)度量相似度是沒(méi)有意義的。我們可以發(fā)現(xiàn)，通過(guò)一系列對(duì)象類(lèi)型之間的關(guān)系連接兩個(gè)對(duì)象的搜索路徑，體現(xiàn)了豐富的語(yǔ)義信息[5]。基于不同的搜索路徑，兩個(gè)對(duì)象的相關(guān)性可能完全不同。例如，作者與會(huì)議的關(guān)系應(yīng)根據(jù)“作者-論文-作者-論文-作者-論文-會(huì)議”路徑和“作者-論文-作者-論文-會(huì)議”路徑的不同而有所不同，即作者在會(huì)議上發(fā)表論文與合作作者在會(huì)議上發(fā)表論文的關(guān)系。因此，一個(gè)理想的相關(guān)性度量應(yīng)該是路徑依賴(lài)的，因?yàn)檫@樣的度量可以捕獲路徑下的語(yǔ)義并基于不同的路徑返回有意義的值。（2） 對(duì)于異構(gòu)對(duì)象，很難設(shè)計(jì)一個(gè)統(tǒng)一的、對(duì)稱(chēng)的關(guān)聯(lián)度量。在異構(gòu)網(wǎng)絡(luò)中，連接同一類(lèi)型對(duì)象的路徑通常是對(duì)稱(chēng)的，路徑長(zhǎng)度是偶數(shù)，因此根據(jù)對(duì)稱(chēng)路徑設(shè)計(jì)對(duì)稱(chēng)度量并不困難，正如PathSim[5]所做的那樣。然而，連接不同類(lèi)型對(duì)象的路徑是不對(duì)稱(chēng)的，路徑長(zhǎng)度可能是奇數(shù)。在這種情況下，設(shè)計(jì)一個(gè)對(duì)稱(chēng)的相關(guān)性度量是不容易的。對(duì)于這兩種情況，設(shè)計(jì)一個(gè)統(tǒng)一的相關(guān)性度量更具挑戰(zhàn)性。

受兩個(gè)對(duì)象被相關(guān)對(duì)象引用時(shí)是相關(guān)的這一直覺(jué)的啟發(fā)，我們提出了一個(gè)通用的框架HeteSim來(lái)評(píng)估異構(gòu)網(wǎng)絡(luò)中異構(gòu)對(duì)象的相關(guān)性。HeteSim是一種基于路徑的相關(guān)性度量方法，能夠有效地捕捉搜索路徑的微妙語(yǔ)義。基于成對(duì)隨機(jī)游走模型，HeteSim統(tǒng)一處理任意搜索路徑，保證了HeteSim的對(duì)稱(chēng)性。另一個(gè)好處是HeteSim可以用相同的方法評(píng)估具有相同或不同類(lèi)型對(duì)象的相關(guān)性。此外，HeteSim是一個(gè)半度量度量。換句話(huà)說(shuō)，HeteSim滿(mǎn)足非負(fù)性、不可分辨的同一性和對(duì)稱(chēng)性。這意味著HeteSim可以用于許多學(xué)習(xí)任務(wù)（如聚類(lèi)和協(xié)作過(guò)濾）。我們還考慮了HeteSim的計(jì)算問(wèn)題，提出了四種快速計(jì)算策略。大量的實(shí)驗(yàn)驗(yàn)證了HeteSim的有效性。作為一種通用的關(guān)聯(lián)度量，HeteSim通過(guò)四個(gè)實(shí)例說(shuō)明了其在異構(gòu)網(wǎng)絡(luò)知識(shí)發(fā)現(xiàn)中的優(yōu)勢(shì)和通用性：自動(dòng)提取對(duì)象輪廓、通過(guò)對(duì)象對(duì)的相對(duì)重要性進(jìn)行專(zhuān)家查找、基于路徑語(yǔ)義的關(guān)聯(lián)搜索和基于語(yǔ)義的電影推薦。HeteSim在機(jī)器學(xué)習(xí)任務(wù)（即查詢(xún)和聚類(lèi)）中也顯示了它的潛力，在這些任務(wù)中，HeteSim優(yōu)于其他成熟的相似性度量。此外，大量實(shí)驗(yàn)驗(yàn)證了HeteSim快速計(jì)算策略的重要性。

二 相關(guān)工作

與相關(guān)性搜索最相關(guān)的工作是相似性搜索。這里我們簡(jiǎn)要地總結(jié)一下這些工作。相似性搜索已經(jīng)被很好地研究了很長(zhǎng)一段時(shí)間。這些研究大致可以分為兩類(lèi)：基于特征的方法和基于鏈接的方法。基于特征的方法根據(jù)對(duì)象的特征值（如余弦相似度、Jaccard系數(shù)和歐氏距離）來(lái)度量對(duì)象的相似度。k近鄰也廣泛應(yīng)用于相似度量[10]，[11]，其目的是根據(jù)數(shù)值特征上定義的相似性來(lái)尋找top-k近鄰。基于特征相似性，top-k相似對(duì)搜索算法（即top-k-join）考慮元組之間的相似性[12]。這種方法不考慮對(duì)象之間的鏈接關(guān)系，因此不能應(yīng)用于網(wǎng)絡(luò)數(shù)據(jù)。

基于鏈接的方法基于對(duì)象在圖中的鏈接結(jié)構(gòu)來(lái)度量對(duì)象的相似性。非對(duì)稱(chēng)相似性度量個(gè)性化PageRank3]通過(guò)重新啟動(dòng)隨機(jī)行走來(lái)評(píng)估從源對(duì)象到目標(biāo)對(duì)象的概率。它擴(kuò)展到在線查詢(xún)[13]、[14]和top-k答案[15]的可伸縮計(jì)算。SimRank[4]是一個(gè)對(duì)稱(chēng)的相似性度量，它通過(guò)兩個(gè)對(duì)象的鄰居的相似性來(lái)評(píng)估它們的相似性。由于其計(jì)算復(fù)雜性，許多后續(xù)研究都是為了加速這種計(jì)算[16]，[17]。SCAN[18]通過(guò)比較兩個(gè)對(duì)象的近鄰集來(lái)度量它們的相似性。最近，Jin等人提出了RoleSim，通過(guò)自守等價(jià)來(lái)度量節(jié)點(diǎn)對(duì)的角色相似性[19]。這些方法只考慮同一類(lèi)型的對(duì)象，不適用于異構(gòu)網(wǎng)絡(luò)。ObjectRank[20]將基于權(quán)限的排序應(yīng)用于標(biāo)簽圖中的關(guān)鍵字搜索，PopRank[21]提出了一種與領(lǐng)域無(wú)關(guān)的對(duì)象級(jí)鏈接分析模型。盡管這兩種方法注意到異構(gòu)關(guān)系會(huì)影響相似性，但它們沒(méi)有考慮包含不同類(lèi)型對(duì)象的路徑的不同語(yǔ)義，因此也無(wú)法度量異構(gòu)網(wǎng)絡(luò)中對(duì)象的相似性。

近年來(lái)，異構(gòu)數(shù)據(jù)的相關(guān)性研究應(yīng)運(yùn)而生。Wang等人[22]提出了一個(gè)從異構(gòu)數(shù)據(jù)中學(xué)習(xí)相關(guān)性的模型，而他們的模型更側(cè)重于分析異構(gòu)網(wǎng)絡(luò)的上下文，而不是網(wǎng)絡(luò)結(jié)構(gòu)。Fouss等人[23]基于隨機(jī)游走的Markovchain模型，設(shè)計(jì)了一個(gè)具有良好性質(zhì)和解釋力的相似度量ECTD。不幸的是，由于缺乏路徑約束，ECTD無(wú)法捕捉到異構(gòu)網(wǎng)絡(luò)中的微妙語(yǔ)義。Sun等人[5]考慮到由不同類(lèi)型對(duì)象構(gòu)成的元路徑的語(yǔ)義，提出了基于對(duì)稱(chēng)路徑的PathSim來(lái)度量相同對(duì)象的相似性。然而，許多有價(jià)值的路徑是不對(duì)稱(chēng)的，不同類(lèi)型對(duì)象之間的相關(guān)性也是有意義的。PathSim不適合這些條件。在信息檢索領(lǐng)域，Lao和Cohen[9]，[24]提出了一種路徑約束隨機(jī)游走（PCRW）模型來(lái)度量由豐富的科學(xué)文獻(xiàn)元數(shù)據(jù)構(gòu)造的有向圖中的實(shí)體鄰近性。雖然PCRW模型可以用來(lái)度量不同類(lèi)型對(duì)象之間的相關(guān)性，但是PCRW模型的非對(duì)稱(chēng)性限制了它的應(yīng)用。在我們的HeteSim定義中，用戶(hù)可以基于任意的搜索路徑來(lái)度量異構(gòu)對(duì)象的相關(guān)性。HeteSim的優(yōu)點(diǎn)（如對(duì)稱(chēng)性和自最大性）使它適合于更多的應(yīng)用。

三、 初步

異構(gòu)信息網(wǎng)絡(luò)是一種特殊類(lèi)型的信息網(wǎng)絡(luò)，它包含多種類(lèi)型的對(duì)象或多種類(lèi)型的鏈接。

定義1：信息網(wǎng)絡(luò)。給定一個(gè)由一組實(shí)體類(lèi)型和一組關(guān)系組成的模式，信息網(wǎng)絡(luò)被定義為一個(gè)有向圖G=（V，E），它具有一個(gè)對(duì)象類(lèi)型映射函數(shù)和一個(gè)連接類(lèi)型映射函數(shù)。每個(gè)對(duì)象屬于一個(gè)特定的對(duì)象類(lèi)型每個(gè)連接屬于一個(gè)特定的關(guān)系，當(dāng)對(duì)象類(lèi)型或關(guān)系類(lèi)型時(shí)，該網(wǎng)絡(luò)稱(chēng)為異構(gòu)信息網(wǎng)絡(luò)，否則稱(chēng)為同質(zhì)信息網(wǎng)絡(luò)。

在信息網(wǎng)絡(luò)中，我們區(qū)分對(duì)象類(lèi)型和關(guān)系類(lèi)型。作為網(wǎng)絡(luò)的模板，網(wǎng)絡(luò)模式描述對(duì)象類(lèi)型和對(duì)象類(lèi)型之間存在的關(guān)系。對(duì)于A型到B型之間存在的關(guān)系R，表示為A和B是關(guān)系R的源類(lèi)型和目標(biāo)類(lèi)型，分別表示為R.S和R.T。對(duì)于，逆關(guān)系自然保持不變。通常，R不等于，除非R是對(duì)稱(chēng)的，這兩種類(lèi)型相同。

實(shí)例1：書(shū)目信息網(wǎng)絡(luò)是典型的異構(gòu)信息網(wǎng)絡(luò)。ACM數(shù)據(jù)集的網(wǎng)絡(luò)模式（見(jiàn)第V.A節(jié)）如圖2(a)所示。它包含來(lái)自七種實(shí)體的對(duì)象：論文（P）、作者（A）、從屬關(guān)系（F）、術(shù)語(yǔ)（T）、主題（S）、地點(diǎn)（V）和會(huì)議（C）（會(huì)議包括多個(gè)地點(diǎn)，例如KDD包括KDD2010、KDD2009等等）。存在連接不同類(lèi)型對(duì)象的鏈接。鏈接類(lèi)型由兩個(gè)對(duì)象類(lèi)型之間的關(guān)系定義。例如，作者和論文之間存在著表示寫(xiě)作或按關(guān)系寫(xiě)作的聯(lián)系，地點(diǎn)和論文之間存在著表示出版或按關(guān)系出版的聯(lián)系。圖2(b)和(c)分別顯示了DBLP數(shù)據(jù)集和IMDB電影數(shù)據(jù)的網(wǎng)絡(luò)模式（見(jiàn)第V.A節(jié)）。

與同構(gòu)網(wǎng)絡(luò)不同，異構(gòu)網(wǎng)絡(luò)中的兩個(gè)對(duì)象可以通過(guò)不同的路徑連接，這些路徑具有不同的含義。例如，在圖2(a)中，作者和會(huì)議可以通過(guò)“作者論文會(huì)場(chǎng)會(huì)議”（APVC）路徑、“作者論文主題論文會(huì)場(chǎng)會(huì)議”（APSPVC）路徑等連接。這兩條路徑下的語(yǔ)義是不同的。APVC路徑意味著由作者撰寫(xiě)的論文在會(huì)議上發(fā)表，而APSPVC路徑意味著與作者論文主題相同的論文在會(huì)議上發(fā)表。顯然，不同路徑下不同的語(yǔ)義會(huì)導(dǎo)致不同的結(jié)果。APVC路徑下的關(guān)聯(lián)性強(qiáng)調(diào)作者參與的會(huì)議，APSPVC路徑下的關(guān)聯(lián)性強(qiáng)調(diào)發(fā)表與作者論文主題相同的論文的會(huì)議。例如，Christos Faloutsos的大部分論文都發(fā)表在KDD、VLDB和SIGMOD上。然而，與他的論文主題相同的論文可能會(huì)在廣泛的會(huì)議上發(fā)表，如ICDM、SDM和CIKM。因此，在異構(gòu)網(wǎng)絡(luò)中，對(duì)象的關(guān)聯(lián)性依賴(lài)于搜索路徑。形式上，我們將元搜索路徑定義為關(guān)聯(lián)路徑。

定義2：關(guān)聯(lián)路徑。關(guān)聯(lián)路徑P是在模式上定義的路徑，并且以的形式表示，其定義了類(lèi)型和之間的復(fù)合關(guān)系。路徑P的長(zhǎng)度是P中關(guān)系的個(gè)數(shù)，即l。

為了簡(jiǎn)單起見(jiàn)，如果同一對(duì)類(lèi)型之間沒(méi)有多重關(guān)系，我們也可以使用表示關(guān)聯(lián)路徑的類(lèi)型名稱(chēng)：。我們說(shuō)，網(wǎng)絡(luò)G中和之間的具體路徑是相關(guān)路徑p的路徑實(shí)例，如果每個(gè)、和每個(gè)鏈路屬于p中的關(guān)系，則可表示為。關(guān)聯(lián)路徑是P的反向路徑，定義了P定義的逆關(guān)系。同樣，我們將的反向路徑實(shí)例定義為P的反向路徑，在G中，如果由P定義的關(guān)系R是對(duì)稱(chēng)的（即P等于），如APA和APCPA。兩個(gè)相關(guān)路徑和在等于時(shí)才可確定，且連接路徑寫(xiě)為，等于。一個(gè)簡(jiǎn)單的可解釋的例子是AP和P V可以連接到路徑AP V。

四、 HETESIM：一個(gè)統(tǒng)一對(duì)稱(chēng)的關(guān)聯(lián)度量

A.基本思路

在許多領(lǐng)域中，相似對(duì)象更可能與其他相似對(duì)象相關(guān)。例如，相似的研究人員通常發(fā)表許多相似的論文；相似的顧客購(gòu)買(mǎi)相似的商品。因此，如果兩個(gè)對(duì)象被相似的對(duì)象引用，則它們是相似的。這種直覺(jué)也適用于異構(gòu)對(duì)象。例如，研究人員與研究人員發(fā)表論文的會(huì)議更相關(guān)；客戶(hù)對(duì)客戶(hù)通常購(gòu)買(mǎi)的品牌更忠誠(chéng)。盡管SimRank[4]中也應(yīng)用了類(lèi)似的思想，但它僅限于同構(gòu)網(wǎng)絡(luò)。當(dāng)我們將這一思想應(yīng)用于異構(gòu)網(wǎng)絡(luò)時(shí)，它面臨著以下挑戰(zhàn)。（1） 異構(gòu)對(duì)象的關(guān)聯(lián)性是路徑約束的。關(guān)聯(lián)路徑不僅捕獲語(yǔ)義信息，而且對(duì)行走路徑進(jìn)行約束。因此需要設(shè)計(jì)一種基于路徑的相似度度量方法。（2） 應(yīng)為任意路徑設(shè)計(jì)均勻?qū)ΨQ(chēng)的度量。對(duì)于給定的路徑（對(duì)稱(chēng)或非對(duì)稱(chēng)），該度量可以用一個(gè)分?jǐn)?shù)來(lái)評(píng)估異構(gòu)對(duì)象對(duì)（相同或不同類(lèi)型）的相關(guān)性。在下一節(jié)中，我們將詳細(xì)說(shuō)明這些挑戰(zhàn)及其解決方案。

B.基于路徑的相關(guān)性度量

與同構(gòu)網(wǎng)絡(luò)不同，異構(gòu)網(wǎng)絡(luò)中的路徑具有語(yǔ)義，使得對(duì)象對(duì)的關(guān)聯(lián)性依賴(lài)于給定的關(guān)聯(lián)路徑。根據(jù)相似對(duì)象與相似對(duì)象相關(guān)的基本思想，提出了一種基于路徑的相關(guān)性度量方法：HeteSim。

定義3：HeteSim：給定一條關(guān)聯(lián)路徑，兩個(gè)對(duì)象s和t（s∈R1.s和t∈Rl.t）之間的HeteSim得分為：

其中是基于關(guān)系的s，是基于關(guān)系的t的近鄰.

當(dāng)s沒(méi)有任何外鄰居（即）或t沒(méi)有任何內(nèi)鄰居（即，）時(shí)，我們無(wú)法推斷出s和t之間的任何關(guān)聯(lián)，因此我們將它們的關(guān)聯(lián)值定義為0。特別是我們認(rèn)為同一類(lèi)型的對(duì)象具有自關(guān)系（表示為I關(guān)系），每個(gè)對(duì)象都只與自身有自關(guān)聯(lián)。顯然，一個(gè)對(duì)象與我的關(guān)系本身是相似的。因此，其相關(guān)性測(cè)度可定義如下：

定義4：基于自我關(guān)系的HeteSim：基于自我關(guān)系I的兩個(gè)相同類(lèi)型對(duì)象s和t之間的HeteSim是：

其中δ（s，t）=1，如果s和t相同，或者δ（s，t）=0。

等式（1）表明，的計(jì)算需要迭代(s,t)沿路徑（s沿路徑和t對(duì)路徑）的所有對(duì)，并總結(jié)這些對(duì)的相關(guān)性。然后，我們用s的外鄰居和t的內(nèi)鄰居的總數(shù)對(duì)其進(jìn)行歸一化，即s和t之間的關(guān)系是s的外鄰居和t的內(nèi)鄰居之間的平均關(guān)系，這個(gè)過(guò)程一直持續(xù)到s和t沿著路徑相遇。與SimRank[4]類(lèi)似，HeteSim也是基于成對(duì)隨機(jī)游走，同時(shí)考慮了路徑約束。正如我們所知，SimRank測(cè)量了兩個(gè)隨機(jī)沖浪者在同一個(gè)節(jié)點(diǎn)相遇的時(shí)間[4]。相比之下，度量了當(dāng)s沿著路徑走，而t逆著路徑走時(shí)，s和t在同一節(jié)點(diǎn)相遇的可能性。

C.關(guān)聯(lián)路徑分解

然而，源對(duì)象s和目標(biāo)對(duì)象t可能不會(huì)沿著給定的路徑P相遇。對(duì)于同一類(lèi)型對(duì)象的相似性度量，相關(guān)路徑通常是等長(zhǎng)的，甚至是對(duì)稱(chēng)的，因此源對(duì)象和目標(biāo)對(duì)象將在中間對(duì)象處相遇。然而，對(duì)于不同類(lèi)型對(duì)象的關(guān)聯(lián)度量，關(guān)聯(lián)路徑通常是奇數(shù)長(zhǎng)度。在這種情況下，源對(duì)象和目標(biāo)對(duì)象將永遠(yuǎn)不會(huì)在同一個(gè)對(duì)象上相遇。以APVC路徑為例，沿著路徑的作者和反對(duì)路徑的會(huì)議永遠(yuǎn)不會(huì)在同一個(gè)對(duì)象中相遇。因此，原HeteSim算法不適用于奇長(zhǎng)相關(guān)路徑。為了解決這一難題，一個(gè)基本思想是將奇數(shù)長(zhǎng)度的路徑變換為偶數(shù)長(zhǎng)度的路徑，從而使源對(duì)象和目標(biāo)對(duì)象總是能夠在同一個(gè)對(duì)象上相遇。因此，可以將任意路徑分解為兩條等長(zhǎng)路徑。

當(dāng)相關(guān)路徑的長(zhǎng)度l為偶數(shù)時(shí)，源對(duì)象（沿路徑）和目標(biāo)對(duì)象（對(duì)路徑）將在中間位置的中間類(lèi)型對(duì)象處相遇，因此相關(guān)路徑P可分為兩條等長(zhǎng)路徑和，即，其中，。

當(dāng)路徑長(zhǎng)度l為奇數(shù)時(shí)，源對(duì)象和目標(biāo)對(duì)象將在關(guān)系處相遇。例如，基于APSPVC路徑，源對(duì)象和目標(biāo)對(duì)象經(jīng)過(guò)兩步之后將在SP關(guān)系處相遇。為了使源對(duì)象和目標(biāo)對(duì)象在同一類(lèi)型對(duì)象上相遇，我們可以在原子關(guān)系之間添加一個(gè)中間類(lèi)型的對(duì)象E，同時(shí)保持和之間的關(guān)系。然后新路徑變成，長(zhǎng)度為l+1，一個(gè)偶數(shù)。在前面的例子中，路徑變成APSEPVC，其長(zhǎng)度現(xiàn)在是偶數(shù)。源對(duì)象和目標(biāo)對(duì)象將在中間位置上的中間類(lèi)型對(duì)象M=E處相遇。因此，新的關(guān)聯(lián)路徑P′也可以分解為兩條等長(zhǎng)路徑和。

定義5：關(guān)聯(lián)路徑分解。任意相關(guān)路徑可分解為兩條相等的路徑和（即），其中和。M和mid的定義如上所述。

顯然，對(duì)于對(duì)稱(chēng)路徑，等于。例如，關(guān)聯(lián)路徑P=AP CP A可以分解為和。對(duì)于相關(guān)路徑APSPVC，我們可以在SP中添加中間類(lèi)型對(duì)象E，從而使路徑成為APSEPVC，因此和。

下一個(gè)問(wèn)題是，我們?nèi)绾螌⒅虚g類(lèi)型的對(duì)象E添加到奇數(shù)長(zhǎng)度路徑中和之間的原子關(guān)系R中。為了包含原來(lái)的原子關(guān)系，我們需要使R關(guān)系成為兩個(gè)新關(guān)系的組合。為此，對(duì)于關(guān)系R的每個(gè)實(shí)例，我們可以添加一個(gè)E實(shí)例來(lái)連接關(guān)系實(shí)例的源對(duì)象和目標(biāo)對(duì)象。圖3（a）中示出了一個(gè)示例，其中中間類(lèi)型對(duì)象E沿著每個(gè)路徑實(shí)例添加在原子關(guān)系A(chǔ)B之間。

定義6：原子關(guān)系的分解。對(duì)于原子關(guān)系R，我們可以在R.S和R.T之間添加一個(gè)對(duì)象類(lèi)型E（稱(chēng)為邊對(duì)象）。因此，原子關(guān)系R被分解為和，其中表示R.S和E之間的關(guān)系，表示E和R.T之間的關(guān)系。對(duì)于每個(gè)關(guān)系實(shí)例r∈R，一個(gè)實(shí)例e∈E連接r.S和r.T。路徑r.S→e和e→r.T分別是和的實(shí)例。

很明顯，分解具有以下性質(zhì)，其證明見(jiàn)附錄A。
性質(zhì)1。原子關(guān)系R可以分解為和，，這種分解是唯一的。

基于此分解，具有原子關(guān)系R的兩個(gè)對(duì)象的關(guān)聯(lián)度可計(jì)算如下：

定義7：基于原子關(guān)系的HeteSim：基于原子關(guān)系R（s∈R.s和t∈R.t）的兩個(gè)不同類(lèi)型對(duì)象s和t之間的HeteSim是：

很容易發(fā)現(xiàn)HeteSim(s，t | I)是HeteSim(s，t | R)的一個(gè)特例，因?yàn)閷?duì)于自關(guān)系I，和。定義7意味著HeteSim可以通過(guò)計(jì)算兩個(gè)不同類(lèi)型對(duì)象相互影響的平均值，直接測(cè)量?jī)蓚€(gè)具有原子關(guān)系R的對(duì)象之間的關(guān)聯(lián)性。

實(shí)例2：圖3（a）示出了原子關(guān)系分解的示例。將AB關(guān)系分解為AE和EB關(guān)系。此外，關(guān)系A(chǔ)B是AE和EB的組成，如圖3（b）所示。圖3（c）中示出了兩個(gè)HeteSim示例。我們可以發(fā)現(xiàn)，異質(zhì)性恰恰反映了事物的關(guān)聯(lián)性。以為例，雖然與、、等連接，但由于只與連接，因此與更接近。這一信息正確地反映在基于AB路徑的的HeteSim得分中：(0,0.17,0.33,0.17)。

我們還發(fā)現(xiàn)，在HeteSim中，物體和物體本身的相似性不是1。以圖3（c）右圖為例，a2與自身的關(guān)聯(lián)度為0.33。這顯然是不合理的。在下一節(jié)中，我們將對(duì)異質(zhì)性進(jìn)行規(guī)范，使關(guān)聯(lián)性測(cè)度更加合理。

D.異象的正常化

首先，我們介紹了給定任意關(guān)聯(lián)路徑的任意兩個(gè)對(duì)象之間的HeteSim的計(jì)算。

定義8：轉(zhuǎn)移概率矩陣。對(duì)于關(guān)系，是A型和B型之間的相鄰矩陣。是沿行向量的歸一化矩陣，它是基于關(guān)系R的A→B的轉(zhuǎn)移概率矩陣。是沿列向量的歸一化矩陣，它是基于關(guān)系的B→A的轉(zhuǎn)移概率矩陣。

很容易證明轉(zhuǎn)移概率矩陣具有以下性質(zhì)。證據(jù)見(jiàn)附錄A。

性質(zhì)2。和，其中是的轉(zhuǎn)置。
定義9：可達(dá)概率矩陣。給定網(wǎng)絡(luò)G=（V，E）遵循網(wǎng)絡(luò)模式，路徑的可達(dá)概率矩陣PM被定義為（為簡(jiǎn)單起見(jiàn)，PM）。PM(i，j)表示目標(biāo)在路徑P下到達(dá)目標(biāo)的概率。

根據(jù)HeteSim的定義和性質(zhì)2，基于關(guān)聯(lián)路徑，和中的對(duì)象之間的關(guān)聯(lián)是

上述公式表明，基于路徑P的和的相關(guān)性是兩個(gè)概率分布的內(nèi)積，即沿路徑到達(dá)中間型對(duì)象M，沿路徑到達(dá)M。對(duì)于和中的兩個(gè)實(shí)例a和b，它們基于路徑P的相關(guān)性為

式中，表示中的第a行。

我們已經(jīng)說(shuō)過(guò)，HeteSim需要正常化。相同對(duì)象的相關(guān)性為1是合理的，因此HeteSim可以標(biāo)準(zhǔn)化如下：

定義10：HeteSim的正常化。基于相關(guān)路徑P的兩個(gè)對(duì)象a和b之間的歸一化HeteSim是：

事實(shí)上，歸一化HeteSim是源對(duì)象a和目標(biāo)對(duì)象b到達(dá)中間類(lèi)型對(duì)象M的概率分布的余弦，其范圍為0到1。圖3（d）顯示了標(biāo)準(zhǔn)化的HeteSim分?jǐn)?shù)。顯然，規(guī)范化的HeteSim更為合理。規(guī)范化是HeteSim的一個(gè)重要步驟，具有以下優(yōu)點(diǎn)。（1） 歸一化HeteSim具有良好的性質(zhì)。下面的屬性4表明HeteSim滿(mǎn)足不可分辨的恒等式。（2） 它有很好的解釋。歸一化HeteSim是表示可達(dá)概率的兩個(gè)向量的余弦。正如Fouss等人指出的[23]，節(jié)點(diǎn)向量之間的角度比節(jié)點(diǎn)之間的距離更具預(yù)測(cè)性。在下一節(jié)中，HeteSim是指標(biāo)準(zhǔn)化的HeteSim。

E.HeteSim的特性

HeteSim具有良好的性能，這使得它在許多應(yīng)用中非常有用。這些特性的證明見(jiàn)附錄A。

特性3：對(duì)稱(chēng)：

性質(zhì)3顯示了HeteSim的對(duì)稱(chēng)性質(zhì)。盡管PathSim[5]也具有類(lèi)似的對(duì)稱(chēng)屬性，但只有當(dāng)路徑是對(duì)稱(chēng)的并且a和b具有相同類(lèi)型時(shí)，它才成立。HeteSim不僅對(duì)于對(duì)稱(chēng)路徑（注意對(duì)于對(duì)稱(chēng)路徑P等于）而且對(duì)于非對(duì)稱(chēng)路徑具有更一般的對(duì)稱(chēng)特性.

特性4。自極大值：HeteSim(a,b | P)∈[0，1]。HeteSim(a,b | P)等于1當(dāng)且僅當(dāng)?shù)扔凇?/p>

屬性4表明HeteSim受到很好的約束。對(duì)于對(duì)稱(chēng)路徑P（即），等于，因此HeteSim(a,a | P)等于1。如果我們將兩個(gè)對(duì)象（即dis(s,t)）之間的距離定義為dis(s,t)=1?HeteSim(s,t)，則同一對(duì)象的距離為零（即dis(s,s)=0）。因此，和合論滿(mǎn)足了不可分辨的同一性。請(qǐng)注意，這是一個(gè)不可分辨的一般身份。對(duì)于不同類(lèi)型的兩個(gè)對(duì)象，如果它們?cè)谥虚g類(lèi)型對(duì)象上具有相同的概率分布，則它們的HeteSim得分也為1。這是合理的，因?yàn)樗鼈兓诮o定的路徑具有相似的結(jié)構(gòu)。

由于HeteSim服從非負(fù)性、不可分辨恒等式和對(duì)稱(chēng)性，我們可以說(shuō)HeteSim是一個(gè)半度量測(cè)度[25]。由于基于路徑的度量，HeteSim不服從三角形不等式。半度量測(cè)度有許多優(yōu)點(diǎn)，可以廣泛應(yīng)用于許多領(lǐng)域[25]。

特性5。連接到SimRank。對(duì)于基于模式S=（{a，B}，{R}）的二部圖G=（V，E），假設(shè)SimRank中的常數(shù)C為1，

其中和。這里HeteSim是非標(biāo)準(zhǔn)化版本。

這個(gè)性質(zhì)揭示了SimRank和HeteSim的聯(lián)系。SimRank總結(jié)了兩個(gè)對(duì)象在經(jīng)過(guò)所有可能的步驟后的相遇概率。HeteSim只計(jì)算沿著給定關(guān)聯(lián)路徑的相遇概率。如果相關(guān)路徑探索了兩個(gè)對(duì)象之間所有可能的元路徑，那么基于這些路徑的HeteSim之和就是SimRank。所以我們可以說(shuō)HeteSim是SimRank的路徑約束版本。通過(guò)關(guān)聯(lián)路徑，HeteSim可以精細(xì)地評(píng)估異構(gòu)對(duì)象的相似性。這一性質(zhì)也意味著HeteSim比SimRank更有效，因?yàn)镠eteSim只需要計(jì)算給定關(guān)聯(lián)路徑上的相遇概率，而不是所有可能的元路徑。

F.討論

讓我們分析一下計(jì)算的時(shí)空復(fù)雜性。假設(shè)一類(lèi)對(duì)象的平均大小為n，有T類(lèi)對(duì)象，則HeteSim的空間要求為來(lái)存儲(chǔ)相關(guān)矩陣。設(shè)d是基于關(guān)系和的所有對(duì)象對(duì)（s，t）上的平均值。對(duì)于給定的l長(zhǎng)度相關(guān)路徑，所需時(shí)間是，因?yàn)楣?jié)點(diǎn)對(duì)（即n2）沿相關(guān)路徑計(jì)算它們的相關(guān)度。對(duì)于SimRank，同時(shí)迭代計(jì)算所有類(lèi)型（即（Tn）2）中節(jié)點(diǎn)對(duì)的相似性，因此其空間復(fù)雜度為O(T2n2)，時(shí)間復(fù)雜度為O(k(T2d)(T n)2)，即），其中k是迭代次數(shù)。所以計(jì)算HeteSim的復(fù)雜度要比SimRank小得多。

在這里，我們討論如何選擇關(guān)聯(lián)路徑。有幾種方法可以做到這一點(diǎn)。（1） 用戶(hù)可以根據(jù)自己的領(lǐng)域知識(shí)和經(jīng)驗(yàn)選擇合適的路徑。（2） 監(jiān)督學(xué)習(xí)可用于自動(dòng)確定相關(guān)路徑的重要性。在信息檢索領(lǐng)域，Lao和Cohen[24]提出了一種可學(xué)習(xí)的接近度度量，其中接近度由簡(jiǎn)單的“路徑專(zhuān)家”的加權(quán)組合來(lái)定義。通過(guò)標(biāo)記訓(xùn)練數(shù)據(jù)，學(xué)習(xí)算法可以推斷出路徑的權(quán)值。類(lèi)似的策略也可用于路徑選擇。（3） 最近，Sun等人[26]將元路徑選擇和用戶(hù)引導(dǎo)信息結(jié)合起來(lái)用于異構(gòu)網(wǎng)絡(luò)中的聚類(lèi)。類(lèi)似的用戶(hù)引導(dǎo)信息也可以應(yīng)用于HeteSim中相關(guān)路徑的選擇。

相似性度量有很多種，其中大部分基于三種基本策略[5]：（1）路徑計(jì)數(shù)策略度量連接源對(duì)象和目標(biāo)對(duì)象的路徑實(shí)例數(shù)；（2）隨機(jī)游走（RW）策略度量從源對(duì)象到目標(biāo)對(duì)象的隨機(jī)游走概率；（3）成對(duì)隨機(jī)游動(dòng)（Pairwise random walk，PRW）策略度量從源對(duì)象和目標(biāo)對(duì)象出發(fā)到達(dá)相同中間對(duì)象的成對(duì)隨機(jī)游動(dòng)概率。由于對(duì)稱(chēng)性和任意路徑約束，本文采用了PRW模型。雖然RW模型也可以通過(guò)基于路徑和的可達(dá)概率的組合來(lái)滿(mǎn)足對(duì)稱(chēng)性，但它對(duì)于對(duì)稱(chēng)路徑是冗余的，并且缺乏良好的可解釋性。對(duì)于PRW模型，當(dāng)關(guān)聯(lián)路徑長(zhǎng)度為奇數(shù)時(shí)，不可避免地會(huì)遇到源對(duì)象和目標(biāo)對(duì)象不相交的問(wèn)題。為了解決這個(gè)問(wèn)題，可以采用一些可選的策略，例如分配會(huì)議對(duì)象類(lèi)型。基于以下優(yōu)點(diǎn)，本文采用路徑沉積策略。（1） 它有一個(gè)統(tǒng)一的框架來(lái)評(píng)估相同或不同類(lèi)型對(duì)象對(duì)任意路徑的相關(guān)性。（2） 它提供了一種簡(jiǎn)單而有效的方法來(lái)評(píng)估基于原子關(guān)系的兩個(gè)不同類(lèi)型對(duì)象的相關(guān)性（參見(jiàn)定義7).

進(jìn)一步比較了表一中六個(gè)已建立的相似度量，分別對(duì)異構(gòu)網(wǎng)絡(luò)（Heteim、PathSim和PCWR）和三種同質(zhì)網(wǎng)絡(luò)的相似度量（P-PageRank、SimRank和RoleSim）進(jìn)行了比較。雖然這些相似性度量都是通過(guò)網(wǎng)絡(luò)結(jié)構(gòu)來(lái)評(píng)價(jià)節(jié)點(diǎn)的相似性，但它們具有不同的屬性和特征。異構(gòu)網(wǎng)絡(luò)的三種度量都是基于路徑的，因?yàn)楫悩?gòu)網(wǎng)絡(luò)中的元路徑體現(xiàn)了語(yǔ)義，簡(jiǎn)化了網(wǎng)絡(luò)結(jié)構(gòu)。基于RW模型的兩種度量（即P-PageRank和PCRW）不滿(mǎn)足對(duì)稱(chēng)性。由于滿(mǎn)足三角不等式，Rolesi是度量，而HeteSim、PathSim和SimRank是半度量。

五、實(shí)驗(yàn)

在實(shí)驗(yàn)中，我們用四個(gè)案例研究和兩個(gè)學(xué)習(xí)任務(wù)驗(yàn)證了HeteSim在三個(gè)數(shù)據(jù)集上的有效性。

A.數(shù)據(jù)集

實(shí)驗(yàn)中采用了三種異構(gòu)信息網(wǎng)絡(luò)。

ACM數(shù)據(jù)集：ACM數(shù)據(jù)集于2010年6月從ACM數(shù)字圖書(shū)館3下載。ACM數(shù)據(jù)集來(lái)自14個(gè)具有代表性的計(jì)算機(jī)科學(xué)會(huì)議：KDD、SIGMOD、WWW、SIGIR、CIKM、SODA、STOC、SOSP、SPAA、SIGCOMM、MobiCOMM、ICML、COLT和VLDB。這些會(huì)議包括196個(gè)相應(yīng)的會(huì)場(chǎng)會(huì)議記錄（例如，KDD會(huì)議包括12個(gè)會(huì)議記錄，如KDD'10、KDD'09等）。這個(gè)數(shù)據(jù)集有1.2萬(wàn)篇論文，1.7萬(wàn)名作者，1.8萬(wàn)名作者。在去掉論文標(biāo)題和摘要中的停止詞之后，我們得到了1.5萬(wàn)個(gè)出現(xiàn)在超過(guò)1%的論文中的術(shù)語(yǔ)。該網(wǎng)絡(luò)還包括73個(gè)主題，這些論文在ACM類(lèi)。ACM數(shù)據(jù)集的網(wǎng)絡(luò)架構(gòu)如圖2（a）所示。

DBLP數(shù)據(jù)集[27]：DBLP數(shù)據(jù)集是從DBLP網(wǎng)站收集的一個(gè)子網(wǎng)絡(luò)，涉及數(shù)據(jù)庫(kù)、數(shù)據(jù)挖掘、信息檢索和人工智能四個(gè)研究領(lǐng)域的主要會(huì)議，自然形成四個(gè)類(lèi)。該數(shù)據(jù)集包含14K篇論文、20個(gè)會(huì)議、14K位作者和89k個(gè)術(shù)語(yǔ)，總鏈接數(shù)為17K。在數(shù)據(jù)集中，4057位作者，所有20個(gè)會(huì)議和100篇論文都被標(biāo)注為四個(gè)研究領(lǐng)域之一。網(wǎng)絡(luò)架構(gòu)如圖2（b）所示。

電影數(shù)據(jù)集[28]：IMDB電影數(shù)據(jù)來(lái)自互聯(lián)網(wǎng)電影數(shù)據(jù)庫(kù)5，包括電影、演員、導(dǎo)演和類(lèi)型。從電影數(shù)據(jù)構(gòu)造電影異構(gòu)網(wǎng)絡(luò)，其模式如圖2（c）所示。電影數(shù)據(jù)包括1.5K部電影、5K演員、551名導(dǎo)演和112種類(lèi)型。

B.案例研究

在本節(jié)中，我們通過(guò)四個(gè)任務(wù)的案例研究來(lái)展示HeteSim的特點(diǎn)：自動(dòng)對(duì)象分析、專(zhuān)家發(fā)現(xiàn)、關(guān)聯(lián)搜索和語(yǔ)義推薦。

1） 任務(wù)1：自動(dòng)對(duì)象分析：我們首先在自動(dòng)對(duì)象分析任務(wù)中研究了我們的方法對(duì)不同類(lèi)型相關(guān)性度量的有效性。如果我們想知道一個(gè)對(duì)象的輪廓，我們可以測(cè)量該對(duì)象與我們感興趣的對(duì)象的相關(guān)性。例如，我們想知道克里斯托斯法魯索斯的學(xué)術(shù)概況。可以通過(guò)測(cè)量Christos Faloutsos與相關(guān)對(duì)象（如會(huì)議、附屬機(jī)構(gòu)、其他作者等）的相關(guān)性來(lái)解決該問(wèn)題。表II顯示了ACM數(shù)據(jù)集上各種類(lèi)型的頂級(jí)相關(guān)對(duì)象列表。AP V C路徑顯示了他積極參加的會(huì)議。請(qǐng)注意，KDD和SIGMOD是Christos Faloutsos參加的兩個(gè)主要會(huì)議，這在他的主頁(yè)中有提到。從路徑APT中，我們可以得到他的研究興趣：數(shù)據(jù)挖掘、模式發(fā)現(xiàn)、可伸縮圖挖掘和社會(huì)網(wǎng)絡(luò)。利用aps路徑，我們可以發(fā)現(xiàn)他的研究領(lǐng)域，表現(xiàn)為ACM主題：數(shù)據(jù)庫(kù)管理（H.2）和數(shù)據(jù)存儲(chǔ)（E.2）。根據(jù)AP A路徑，HeteSim找到了最重要的合著者，其中大部分是他的博士生。另一個(gè)有趣的例子見(jiàn)附錄B。

2） 任務(wù)2：專(zhuān)家發(fā)現(xiàn)：在這種情況下，我們希望通過(guò)專(zhuān)家發(fā)現(xiàn)任務(wù)來(lái)驗(yàn)證HeteSim的有效性，以反映對(duì)象對(duì)的相對(duì)重要性。我們知道，通過(guò)比較對(duì)象對(duì)的關(guān)聯(lián)性，可以揭示對(duì)象對(duì)的相對(duì)重要性。假設(shè)我們知道某個(gè)領(lǐng)域的專(zhuān)家，這里的專(zhuān)家查找任務(wù)是通過(guò)其他領(lǐng)域的專(zhuān)家的相對(duì)重要性來(lái)查找他們。表三顯示了ACM數(shù)據(jù)集上六對(duì)“會(huì)議作者”的不同方法返回的相關(guān)性得分。基于APVC和CVPA路徑定義了會(huì)議與作者的關(guān)聯(lián)性，這兩種路徑具有相同的語(yǔ)義：作者在會(huì)議中發(fā)表論文。由于對(duì)稱(chēng)特性，HeteSim為兩條路徑返回相同的值，而PCRW為這兩條路徑返回不同的值。假設(shè)我們熟悉數(shù)據(jù)挖掘領(lǐng)域，并且已經(jīng)知道C.Faloutsos是KDD領(lǐng)域一位有影響力的研究者。比較這些HeteSim分?jǐn)?shù)，我們可以發(fā)現(xiàn)在其他研究領(lǐng)域有影響力的研究人員，即使我們不太熟悉這些領(lǐng)域。J.F.諾頓、W.B.克羅夫特和A.古普塔應(yīng)該分別是西格莫德、西格爾和蘇打的有影響力的研究者，因?yàn)樗麄兊腍eteSim得分與C.法洛索斯非常相似。此外，我們還可以推斷，羅思和陳彥可能分別是SIGIR和SIGCOMM的積極研究者，因?yàn)樗麄兊腍eteSim分?jǐn)?shù)適中。事實(shí)上，C.Faloutsos、J.F.Naughton、W.B.Croft和A.Gupta是他們研究社區(qū)排名第一的作者。羅思和陳彥是年輕的教授，他們?cè)诟髯缘难芯款I(lǐng)域都做了很好的工作。然而，如果相關(guān)性度量不是對(duì)稱(chēng)的（例如，PCRW），那么在比較這些相關(guān)性得分時(shí)很難判斷哪些作者更具影響力。例如，嚴(yán)晨和SIGCOMM的PCRW得分是APVC路徑中最大的。然而，當(dāng)考慮相反的路徑（即CVPA路徑）時(shí)，該值是最小的。附錄C中的定量實(shí)驗(yàn)表明，與PCRW相比，HeteSim能更準(zhǔn)確地揭示作者會(huì)議對(duì)的相對(duì)重要性。

?

3） 任務(wù)3：基于路徑語(yǔ)義的相關(guān)性搜索：如前所述，基于路徑的相關(guān)性度量可以捕獲路徑的語(yǔ)義。在這個(gè)相關(guān)搜索任務(wù)中，我們將通過(guò)比較三種基于路徑的度量（HeteSim、PCRW和PathSim）和SimRank來(lái)觀察路徑的重要性和語(yǔ)義捕獲的有效性。這項(xiàng)任務(wù)是根據(jù)AP V CV P A路徑，即在同一會(huì)議上發(fā)表論文的作者，找出與Christos Faloutsos相關(guān)的前10位作者。通過(guò)忽略對(duì)象的異構(gòu)性，我們直接在整個(gè)網(wǎng)絡(luò)上運(yùn)行SimRank，從不同類(lèi)型對(duì)象混合在一起的排名結(jié)果中選出前十名作者。比較結(jié)果如表四所示。乍一看，我們可以發(fā)現(xiàn)，三個(gè)基于路徑的措施都返回研究人員具有類(lèi)似的聲譽(yù)與克里斯托斯略有不同的順序。然而，SimRank的結(jié)果完全違背了我們的常識(shí)。我們認(rèn)為SimRank性能不好的原因是它只考慮了鏈接結(jié)構(gòu)而忽略了鏈接語(yǔ)義。在異構(gòu)網(wǎng)絡(luò)中，不同類(lèi)型的對(duì)象連接在一起。如果忽略鏈接語(yǔ)義，對(duì)不同類(lèi)型的鏈接一視同仁，就會(huì)充滿(mǎn)噪音。通過(guò)選擇有用的關(guān)系序列，元路徑避免了復(fù)雜結(jié)構(gòu)帶來(lái)的噪聲。此外，元路徑體現(xiàn)了關(guān)系序列的語(yǔ)義。因此，元路徑是異構(gòu)網(wǎng)絡(luò)的基本分析工具。

另外，讓我們分析三種基于路徑的度量返回的結(jié)果的細(xì)微差異。PathSim發(fā)現(xiàn)了類(lèi)似的同行作者，比如Philip Yu和Jiawei Han。它們?cè)跀?shù)據(jù)挖掘領(lǐng)域有著相同的聲譽(yù)。對(duì)PCRW來(lái)說(shuō)，奇怪的是，與克里斯托斯·法魯索斯最相似的作家不是他自己，而是查魯·C·阿加瓦爾和賈維漢。這顯然是不合理的。我們推測(cè)，在Christos Faloutsos參加的會(huì)議上，Charu C.Aggarwal和Jiawei Han發(fā)表了大量的論文，因此Christos Faloutsos對(duì)Charu C.Aggarwal和Jiawei Han的可達(dá)概率比他本人更高。赫特西姆的結(jié)果有點(diǎn)不同。最相似的作家是斯里尼瓦桑·帕塔薩拉西和閻錫峰，而不是菲利普·俞正聲和韓嘉偉。讓我們重溫路徑AP VCVP A的語(yǔ)義：作者在同一會(huì)議上發(fā)表論文。圖4顯示了沿著路徑APVC從作者到會(huì)議的可達(dá)概率分布。很明顯，Srinivasan Parthasarathy和Xifeng Yan關(guān)于會(huì)議的論文的概率分布更接近Christos Faloutsos，因此基于相同的會(huì)議出版物，它們應(yīng)該更類(lèi)似于Christos。雖然俞敏洪和韓嘉偉與C.Faloutsos享有相同的聲譽(yù)，但他們的論文在不同的會(huì)議上發(fā)表的范圍更廣。因此，根據(jù)APVCVP A路徑，他們不是與C.Faloutsos最相似的作者。因此，我們的HeteSim更準(zhǔn)確地捕捉了路徑的語(yǔ)義。附錄D中的另一個(gè)例子進(jìn)一步說(shuō)明了HeteSim捕獲相關(guān)路徑語(yǔ)義的能力。

4） 任務(wù)4：語(yǔ)義推薦：在這個(gè)案例研究中，我們展示了在推薦系統(tǒng)中應(yīng)用HeteSim的潛力。推薦系統(tǒng)的一個(gè)重要目標(biāo)是根據(jù)用戶(hù)的意圖推薦產(chǎn)品。理想的推薦系統(tǒng)應(yīng)該能夠捕捉不同用戶(hù)意圖的微妙之處。以電影數(shù)據(jù)集為例。假設(shè)“M”代表電影，“T”代表電影類(lèi)型。“A”和“D”分別代表演員和導(dǎo)演。如果用戶(hù)希望找到與《鋼鐵俠》演員相同的電影，可以在推薦系統(tǒng)中使用MAM路徑。對(duì)于喜歡與《鋼鐵俠》類(lèi)型相同的電影的用戶(hù)，可以使用路徑MTM。推薦結(jié)果如表五所示。結(jié)果表明，HeteSim可以根據(jù)不同的路徑推薦不同的電影。MAM路徑推薦與電影《鋼鐵俠》共用演員的電影，如《追風(fēng)箏的人》和《晚安》。雖然前四部推薦電影（除了《鋼鐵俠》本身）都只有一個(gè)與《鋼鐵俠》相同的演員，但《追風(fēng)箏的人》的演員較少，所以得分較高。MTM路徑推薦與《鋼鐵俠》類(lèi)型相同的電影，如《不可思議的綠巨人》、《少年變種海龜》和《繁殖》。“不可思議的綠巨人”與“鋼鐵俠”有著更為常見(jiàn)的類(lèi)型，因此它排名第一。更有趣的是，基于相關(guān)路徑，HeteSim可以推薦不同類(lèi)型的對(duì)象。例如，用戶(hù)可能喜歡與演員“西爾維斯特·史泰龍”的電影類(lèi)型相同的電影。可采用AMTM路徑。結(jié)果顯示在表五的最后一列。由于“西爾維斯特·史泰龍”在許多有關(guān)拳擊和體育的電影中扮演主角，HeteSim推薦這類(lèi)電影，如《洛奇》和《百萬(wàn)美元寶貝》。遵循這一思想，我們?cè)O(shè)計(jì)了一個(gè)基于語(yǔ)義的推薦系統(tǒng)HeteRecom[28]。

C.查詢(xún)?nèi)蝿?wù)性能

查詢(xún)?nèi)蝿?wù)將驗(yàn)證HeteSim在異構(gòu)對(duì)象查詢(xún)搜索中的有效性。由于PathSim不能度量不同類(lèi)型對(duì)象之間的關(guān)聯(lián)性，因此本實(shí)驗(yàn)只比較了HeteSim和PCRW。在DBLP數(shù)據(jù)集上，我們基于CPA路徑來(lái)度量會(huì)議和作者之間的接近度。對(duì)于每一次會(huì)議，我們根據(jù)相關(guān)作者的測(cè)量分?jǐn)?shù)對(duì)他們進(jìn)行排名。然后根據(jù)作者標(biāo)簽繪制前100名作者的ROC曲線（當(dāng)作者標(biāo)簽和會(huì)議標(biāo)簽相同時(shí)，為真，否則為假）。之后，我們計(jì)算AUC（Area Under ROC Curve）得分來(lái)評(píng)估排名結(jié)果的表現(xiàn)。請(qǐng)注意，DBLP數(shù)據(jù)集上的所有會(huì)議和一些作者都標(biāo)有四個(gè)研究領(lǐng)域之一（見(jiàn)第V.A節(jié)）。分?jǐn)?shù)越大意味著表現(xiàn)越好。我們?cè)u(píng)估了9個(gè)代表性會(huì)議的表現(xiàn)，其AUC分?jǐn)?shù)如表六所示。我們可以發(fā)現(xiàn)，HeteSim在所有9個(gè)會(huì)議中都始終優(yōu)于PCRW。結(jié)果表明，所提出的HeteSim方法比非對(duì)稱(chēng)相似性度量PCRW更適合于鄰近查詢(xún)?nèi)蝿?wù)。

D.群集任務(wù)的性能

由于HeteSim的對(duì)稱(chēng)性，它可以直接應(yīng)用于聚類(lèi)任務(wù)。為了評(píng)估它的性能，我們將HeteSim與五個(gè)成熟的相似性度量進(jìn)行了比較，包括兩個(gè)基于路徑的度量（即PathSim和PCRW）和三個(gè)同質(zhì)度量（即SimRank、RoleSim和P-PageRank）。這些度量使用相同的信息來(lái)確定對(duì)象之間的成對(duì)相似性。我們?cè)u(píng)估了DBLP數(shù)據(jù)集的聚類(lèi)性能。主要包括三個(gè)任務(wù)：基于CPAPC路徑的會(huì)議聚類(lèi)、基于APCPA路徑的作者聚類(lèi)和基于P-AP-CP路徑的論文聚類(lèi)。對(duì)于非對(duì)稱(chēng)度量（即PCRW和P-PageRank），可通過(guò)基于路徑P和P-1的相似矩陣的平均來(lái)獲得對(duì)稱(chēng)相似矩陣。對(duì)于RoleSim，它應(yīng)用于路徑P構(gòu)造的網(wǎng)絡(luò)中。對(duì)于SimRank和P-PageRank，它們應(yīng)用于路徑PL構(gòu)造的子網(wǎng)絡(luò)中（注意，實(shí)驗(yàn)中的三條路徑是對(duì)稱(chēng)的）。例如，對(duì)于CPAPC路徑，從路徑CPA導(dǎo)出的二部圖MCA可以用于SimRank和P-PageRank度量。然后，基于不同度量返回的相似矩陣，我們應(yīng)用歸一化割[29]進(jìn)行聚類(lèi)。群集數(shù)設(shè)置為4。NMI準(zhǔn)則（歸一化互信息）[30]用于評(píng)估會(huì)議、作者和論文的聚類(lèi)性能。NMI介于0和1之間，越高越好。在實(shí)驗(yàn)中，P-PageRank、SimRank和RoleSim的阻尼因子分別設(shè)置為0.9、0.8和0.1。

表七總結(jié)了100次運(yùn)行的平均聚類(lèi)精度結(jié)果。我們可以發(fā)現(xiàn)HeteSim在兩個(gè)任務(wù)（作者和論文聚類(lèi)）上取得了最好的性能，在會(huì)議聚類(lèi)任務(wù)上取得了第三名的成績(jī)。總之，它在三種類(lèi)型的聚類(lèi)精度的加權(quán)平均方面表現(xiàn)最好。PCWR和P-PageRank的一般結(jié)果表明，盡管兩個(gè)隨機(jī)游走過(guò)程的組合可以構(gòu)造對(duì)稱(chēng)的相似性度量，但簡(jiǎn)單的組合不能生成良好的相似性度量。RoleSim的目標(biāo)是檢測(cè)角色相似度，與結(jié)構(gòu)相似度略有不同，因此在這些聚類(lèi)任務(wù)中性能較差。此外，我們還記錄了所有度量的相似度計(jì)算的運(yùn)行時(shí)間。由于篇幅限制，我們只在表VII的最后一列顯示了作者集群任務(wù)的代表性運(yùn)行時(shí)間。我們可以發(fā)現(xiàn)HeteSim和PCWR的運(yùn)行時(shí)間最小，因?yàn)樗鼈冎恍枰芈窂接?jì)算一次矩陣乘法。SimRank和P-PageRank中的迭代計(jì)算使它們的運(yùn)行時(shí)間更長(zhǎng)。RoleSim中的鄰域匹配過(guò)程具有很高的時(shí)間復(fù)雜度，這使得它非常耗時(shí)。實(shí)驗(yàn)表明，HeteSim不僅在同類(lèi)對(duì)象的相似性度量上有很好的表現(xiàn)，而且作為一種高效聚類(lèi)的相似性度量方法也有潛力。

?

六、 快速計(jì)算策略與實(shí)驗(yàn)

HeteSim對(duì)時(shí)間和空間的計(jì)算要求很高。在大規(guī)模的信息網(wǎng)絡(luò)中，在線查詢(xún)是負(fù)擔(dān)不起的。因此，一個(gè)主要的策略是離線計(jì)算相關(guān)矩陣，并用這些矩陣進(jìn)行在線查詢(xún)。對(duì)于常用的關(guān)聯(lián)路徑，關(guān)聯(lián)矩陣可以提前具體化。在線查詢(xún)將非常快，因?yàn)樗恍枰ㄎ痪仃囍械男泻土小Ｈ欢?#xff0c;實(shí)現(xiàn)所有常用路徑也需要花費(fèi)大量的時(shí)間和空間。因此，本文提出了四種快速計(jì)算關(guān)聯(lián)矩陣的策略。此外，實(shí)驗(yàn)驗(yàn)證了這些策略的有效性。

A.HeteSim的計(jì)算特點(diǎn)

HeteSim的計(jì)算包括兩個(gè)階段：矩陣乘法（表示為MUL，即和的計(jì)算）、相關(guān)性計(jì)算（表示為REL，即的計(jì)算和歸一化）。為了分析HeteSim的計(jì)算特性，我們通過(guò)實(shí)驗(yàn)觀察了這兩個(gè)相位在不同路徑上的運(yùn)行時(shí)間。

基于ACM數(shù)據(jù)集（見(jiàn)第V.A節(jié)），我們選擇了四條不同長(zhǎng)度的路徑（l）：、、和。l表示路徑重復(fù)次數(shù)，范圍從1到5。我們根據(jù)這些路徑記錄了HeteSim不同階段的運(yùn)行時(shí)間，如圖5所示。我們首先觀察圖5（a）中MUL的運(yùn)行時(shí)間。不同的路徑有不同的運(yùn)行時(shí)間。隨著路徑長(zhǎng)度的增加，由于需要乘法的矩陣越來(lái)越多，矩陣乘法的運(yùn)行時(shí)間不斷增加。然后我們考慮圖5（b）中REL階段的運(yùn)行時(shí)間。除與圖5（a）相同的觀察外，REL的運(yùn)行時(shí)間受長(zhǎng)度l的影響很大，即當(dāng)l為2和4時(shí)，和的REL運(yùn)行時(shí)間顯著增加。讓我們以為例來(lái)分析原因。當(dāng)l為1、3和5時(shí)，源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)將沿著路徑在中間節(jié)點(diǎn)C處相遇，因此相關(guān)性計(jì)算為。然而，當(dāng)l為2和4時(shí)，相關(guān)性計(jì)算是。由于A的尺寸比C大得多，的運(yùn)行時(shí)間比長(zhǎng)得多。相似的原因使有相反的波動(dòng)。此外，當(dāng)矩陣變得稠密時(shí)，REL所花費(fèi)的時(shí)間不再增長(zhǎng)。因此其增長(zhǎng)率逐漸降低。對(duì)于路徑，A和P的維數(shù)很接近（#A 17K和#P 12K），因此對(duì)于不同的路徑長(zhǎng)度，其運(yùn)行時(shí)間沒(méi)有明顯的差異。另外，可達(dá)概率矩陣始終保持稀疏，使得的運(yùn)行時(shí)間小于其它路徑的運(yùn)行時(shí)間。

圖5（c）和（d）顯示了這兩個(gè)階段的運(yùn)行時(shí)間與總運(yùn)行時(shí)間的比率。一方面，它說(shuō)明了REL階段主導(dǎo)了HeteSim的運(yùn)行時(shí)間。另一方面，MUL的比率隨著路徑長(zhǎng)度的增加而增加。從這些實(shí)驗(yàn)中，我們可以總結(jié)出HeteSim計(jì)算的兩個(gè)特點(diǎn)。（1） 相關(guān)性計(jì)算是主要的耗時(shí)階段。這意味著矩陣乘法的加速可能不會(huì)顯著減少HeteSim的運(yùn)行時(shí)間，盡管這種策略被廣泛用于加速SimRank[4]和PCWR[24]。（2） 矩陣的維數(shù)和稀疏性對(duì)HeteSim算法的效率有很大的影響。

B.快速計(jì)算策略

雖然不能直接減少相關(guān)計(jì)算階段的運(yùn)行時(shí)間，但可以通過(guò)調(diào)整矩陣維數(shù)和保持矩陣稀疏來(lái)加快HeteSim的計(jì)算速度。基于上述思想，我們?cè)O(shè)計(jì)了以下四種策略。

1） 動(dòng)態(tài)規(guī)劃策略：矩陣乘法服從聯(lián)想性。而且，不同的計(jì)算序列具有不同的時(shí)間復(fù)雜度。動(dòng)態(tài)規(guī)劃策略（DP）利用聯(lián)想特性改變矩陣乘法的順序。DP的基本思想是分配具有高計(jì)算優(yōu)先級(jí)的低維矩陣。對(duì)于路徑HeteSim的期望最小計(jì)算復(fù)雜度可由下式計(jì)算，計(jì)算順序由i記錄。

利用O（l2）復(fù)雜度的動(dòng)態(tài)規(guī)劃方法，可以很容易地求解上述方程。運(yùn)行時(shí)間可以省略，因?yàn)閘比矩陣維數(shù)小得多。

相關(guān)路徑中可能有許多重復(fù)的子路徑。顯然，這些重疊子路徑只需計(jì)算一次。例如，通過(guò)計(jì)算矩陣APT一次，可以得到APTPA的結(jié)果。在矩陣乘法過(guò)程中，DP策略保留了矩陣的計(jì)算序列和相應(yīng)的結(jié)果。對(duì)于一個(gè)新的計(jì)算序列，如果以前計(jì)算過(guò)，則可以直接使用相應(yīng)的結(jié)果。因此，復(fù)用策略進(jìn)一步加快了矩陣乘法。注意，DP策略只加速多階段（即矩陣乘法），并且不會(huì)改變相關(guān)結(jié)果，因此DP是一種信息無(wú)損策略。

2） 截短策略：截短策略是基于去掉那些不太重要的節(jié)點(diǎn)上的概率不會(huì)顯著降低性能的假設(shè)，這已經(jīng)被許多研究所證明[24]，[31]。這種策略的一個(gè)優(yōu)點(diǎn)是保持矩陣稀疏。稀疏矩陣大大減少了空間和時(shí)間的消耗。截?cái)嗖呗缘幕舅枷胧窃陔S機(jī)游動(dòng)的每一步中增加一個(gè)截?cái)嗖介L(zhǎng)。在截?cái)嗖襟E中，當(dāng)相關(guān)值小于閾值ε時(shí)，將這些節(jié)點(diǎn)的相關(guān)值設(shè)置為0。靜態(tài)閾值通常用于許多方法（例如，參考文獻(xiàn)[24]）。然而，該算法存在以下缺點(diǎn)：對(duì)于元素都具有高概率的矩陣，它可能不截?cái)嗳魏卧?#xff1b;對(duì)于元素都具有高概率的矩陣，它可能會(huì)截?cái)嗳我庖粋€(gè)，并且對(duì)于所有元素概率都很低的矩陣，它可能會(huì)截?cái)啻蠖鄶?shù)節(jié)點(diǎn)。由于查詢(xún)?nèi)蝿?wù)中的k對(duì)象通常都是最為關(guān)注的，因此閾值ε可以設(shè)置為每個(gè)搜索對(duì)象的k相關(guān)值。對(duì)于尺寸為M×L的相似矩陣，k可以動(dòng)態(tài)調(diào)整如下。

其中W是頂部對(duì)象的數(shù)量，由用戶(hù)決定。動(dòng)態(tài)調(diào)整的基本思想是，對(duì)于超對(duì)象類(lèi)型（即L較大），k緩慢增加。W和β決定截?cái)嗨健］^大的W或β將導(dǎo)致較大的k，這意味著更密集的矩陣。確定每個(gè)目標(biāo)的前k個(gè)相關(guān)值代價(jià)很大，因此我們可以通過(guò)整個(gè)矩陣的前kM值來(lái)估計(jì)該值。此外，最高kM值可以由原始矩陣中具有比率γ的樣本數(shù)據(jù)來(lái)近似。γ越大，運(yùn)行時(shí)間越長(zhǎng)，逼近精度越高。總之，截?cái)嗖呗允且环N信息丟失策略，它以較小的精度代價(jià)保持矩陣稀疏。另外，估計(jì)閾值ε需要額外的時(shí)間。

3） 混合策略：如上所述，DP策略可以加速M(fèi)UL階段，而截?cái)嗖呗钥梢酝ㄟ^(guò)保持稀疏矩陣間接加速REL階段。因此，可以設(shè)計(jì)一種混合策略來(lái)結(jié)合這兩種策略。對(duì)于多階段，采用DP策略。在獲得和之后，添加截?cái)嗖呗浴Ｅc上述截?cái)嗖呗圆煌?#xff0c;混合策略只截?cái)嗪汀；旌喜呗岳昧薉P和截?cái)嗖呗缘膬?yōu)點(diǎn)。這也是一種信息丟失策略，因?yàn)椴捎昧私財(cái)嗖呗浴?/p>

4） 蒙特卡羅策略：蒙特卡羅方法（montecarlo method，MC）是一類(lèi)通過(guò)重復(fù)隨機(jī)抽樣來(lái)估計(jì)結(jié)果的計(jì)算算法。它已用于計(jì)算矩陣乘法的近似值。Fogaras等人[13]應(yīng)用montecarlo算法來(lái)計(jì)算近似的個(gè)性化PageRank。最近，Ni等人[24]在路徑約束隨機(jī)游走模型的上下文中測(cè)試了montecarlo抽樣策略的有效性。

在這項(xiàng)研究中，我們應(yīng)用MC策略來(lái)估計(jì)和的價(jià)值。的值可以由步行者沿著路徑P從a訪問(wèn)節(jié)點(diǎn)b的次數(shù)的歸一化計(jì)數(shù)來(lái)近似。

?

C.快速計(jì)算實(shí)驗(yàn)

我們?cè)贏CM數(shù)據(jù)集上驗(yàn)證了快速計(jì)算策略的效率和有效性。使用四個(gè)路徑:、、和。?l表示路徑重復(fù)的次數(shù)，范圍從1到5。采用了四種快速計(jì)算策略和原始方法(即基線)。截?cái)噙^(guò)程中的參數(shù)設(shè)置如下:頂對(duì)象數(shù)W為200，β為0.5，γ為0.005。MC策略中的步行者(即K)數(shù)量為500。記錄所有策略的運(yùn)行時(shí)間和準(zhǔn)確性。在精度評(píng)估中，以原方法得到的關(guān)聯(lián)矩陣作為基線。準(zhǔn)確性是每個(gè)策略獲得的前100個(gè)對(duì)象的召回標(biāo)準(zhǔn)。所有實(shí)驗(yàn)都是在具有2.13 GHz英特爾至強(qiáng)8核處理器和64 GB內(nèi)存的機(jī)器上進(jìn)行的。

圖6顯示了四種策略在不同路徑上的運(yùn)行時(shí)間和準(zhǔn)確性。這些策略的運(yùn)行時(shí)間如圖6 (a)-(d)所示。我們可以觀察到，DP策略幾乎與基線具有相同的運(yùn)行時(shí)間。只有當(dāng)多相流階段主導(dǎo)整個(gè)運(yùn)行時(shí)間時(shí)(例如，和)，它才能加速異質(zhì)結(jié)構(gòu)計(jì)算。截?cái)嗪突旌喜呗缘那闆r并非如此，截?cái)嗪突旌喜呗燥@著地加速了HeteSim計(jì)算，并且在大多數(shù)情況下具有接近的加速比。除了AP A路徑，MC策略在大多數(shù)情況下都是四種策略中加速比最高的。然后，讓我們從圖6 (e)-(h)觀察它們的準(zhǔn)確性。DP策略的精度始終接近1。對(duì)于大多數(shù)路徑，混合策略實(shí)現(xiàn)了第二性能。MC策略的準(zhǔn)確性對(duì)于大多數(shù)路徑來(lái)說(shuō)也很高，而它在不同的路徑上波動(dòng)。顯然，截?cái)嗖呗栽诖蠖鄶?shù)情況下精度最低。

正如我們已經(jīng)注意到的，動(dòng)態(tài)規(guī)劃是一種信息無(wú)損的策略，它只會(huì)加速多階段規(guī)劃階段。此外，對(duì)于大多數(shù)路徑來(lái)說(shuō)，MUL階段不是主要的耗時(shí)部分。因此，動(dòng)態(tài)規(guī)劃策略以接近1的精度顯著地加速了故障樹(shù)。截?cái)嗖呗允且环N保持矩陣稀疏的信息丟失策略，因此可以有效地加速HeteSim。這就是為什么截?cái)嗖呗跃哂懈呒铀俦鹊鹊偷脑颉；旌喜呗越Y(jié)合了動(dòng)態(tài)規(guī)劃和截?cái)嗖呗浴Ｒ虼怂募铀俦冉咏財(cái)嗖呗浴；旌喜呗灾辉陔S機(jī)行走的最后一步進(jìn)行截?cái)?#xff0c;減少了信息損失。說(shuō)明其精度高于截?cái)嗖呗浴Ｎ覀冎?#xff0c;MC策略的本質(zhì)是反復(fù)隨機(jī)抽樣。為了達(dá)到高精度，高維或稀疏矩陣需要更多的walkers(即K較大)。在我們的實(shí)驗(yàn)中，固定步行者(即K為500)使得MC策略在某些條件下精度較差。例如，在圖6 (h)中，對(duì)于，相關(guān)性計(jì)算是。P的高維數(shù)和均勻分布導(dǎo)致了MC策略的低精度。

為了清楚地說(shuō)明這些策略對(duì)異構(gòu)計(jì)算兩個(gè)階段的影響，圖7給出了一個(gè)典型的運(yùn)行時(shí)示例。顯然，發(fā)展伙伴關(guān)系戰(zhàn)略確實(shí)大大加快了多國(guó)部隊(duì)階段，但對(duì)REL階段沒(méi)有影響。相反，由于稀疏矩陣和估計(jì)閾值所花費(fèi)的額外時(shí)間，截?cái)嗖呗员萂UL階段的基線慢。然而，由于保留了稀疏矩陣，截?cái)嗖呗源蟠蠹铀倭薘EL相位。與截?cái)嗖呗韵啾?#xff0c;多載波策略不僅加速了REL相位，而且有利于密集矩陣上的多載波相位。

根據(jù)以上分析，這些策略適用于不同的路徑和場(chǎng)景。對(duì)于非常稀疏的矩陣(如)和低維矩陣(如)，所有策略都不能顯著提高效率。然而，在這些條件下，可以在不應(yīng)用任何快速計(jì)算策略的情況下快速計(jì)算異質(zhì)結(jié)。對(duì)于計(jì)算開(kāi)銷(xiāo)較大的密集矩陣(如)和高維矩陣(如)，截?cái)唷⒒旌虾投嘀行牟呗钥梢杂行岣呋旌暇仃嚨男省Ｌ貏e地，混合策略和MC策略的加速比高達(dá)100，而精確度損失很小。如果多路徑階段是路徑的主要耗時(shí)部分，那么動(dòng)態(tài)規(guī)劃策略也可以在不損失準(zhǔn)確性的情況下大大加快速度。矩陣運(yùn)算策略具有很高的效率，但對(duì)于高維矩陣，其精度可能會(huì)下降。所以需要通過(guò)平衡效率和效果來(lái)設(shè)置合適的K。

七.結(jié)論

在本文中，我們研究了在異構(gòu)網(wǎng)絡(luò)中度量異構(gòu)對(duì)象(包括相同類(lèi)型或不同類(lèi)型的對(duì)象)相關(guān)性的相關(guān)性搜索問(wèn)題。我們提出了一個(gè)通用的相關(guān)性度量，稱(chēng)為HeteSim。作為一種路徑約束度量，HeteSim可以在一個(gè)統(tǒng)一的框架中度量同類(lèi)型和不同類(lèi)型對(duì)象的相關(guān)性。此外，HeteSim是一種半度量度量，可以在許多應(yīng)用中使用。大量的實(shí)驗(yàn)驗(yàn)證了異構(gòu)對(duì)象相關(guān)度評(píng)價(jià)的有效性和高效性。

未來(lái)的工作有一些有趣的方向。首先，可以探索更多的方法來(lái)度量異構(gòu)對(duì)象的相關(guān)性，如路徑計(jì)數(shù)和讀寫(xiě)策略。其次，由于本文提出的快速計(jì)算策略都是內(nèi)存中的方法，因此異構(gòu)系統(tǒng)的并行計(jì)算方法是一個(gè)值得探索的課題。最后，如何選擇和加權(quán)不同的元路徑也是異構(gòu)網(wǎng)絡(luò)的重要問(wèn)題。

總結(jié)

以上是生活随笔為你收集整理的【论文翻译】HeteSim：异构网络中相关性度量的通用框架的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。