大規(guī)模演化知識(shí)網(wǎng)絡(luò)中的關(guān)聯(lián)推理

趙澤亞 賈巖濤 王元卓 靳小龍 程學(xué)旗

1（中國(guó)科學(xué)院網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重點(diǎn)實(shí)驗(yàn)室（中國(guó)科學(xué)院計(jì)算技術(shù)研究所） 北京 100190）2（解放軍信息工程大學(xué) 鄭州 450000）3（中國(guó)天繪衛(wèi)星中心 北京 102012）（53414264＠qq．com）

大規(guī)模演化知識(shí)網(wǎng)絡(luò)中的關(guān)聯(lián)推理

趙澤亞1，2，3賈巖濤1王元卓1靳小龍1程學(xué)旗1

1（中國(guó)科學(xué)院網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重點(diǎn)實(shí)驗(yàn)室（中國(guó)科學(xué)院計(jì)算技術(shù)研究所） 北京 100190）2（解放軍信息工程大學(xué) 鄭州 450000）3（中國(guó)天繪衛(wèi)星中心 北京 102012）（53414264＠qq．com）

關(guān)聯(lián)推理；演化知識(shí)網(wǎng)絡(luò)；背包問(wèn)題；鏈接延展模式；知識(shí)庫(kù)

網(wǎng)絡(luò)大數(shù)據(jù)時(shí)代，數(shù)據(jù)不再僅僅是簡(jiǎn)單的采集對(duì)象，其背后其實(shí)蘊(yùn)含著大量豐富、復(fù)雜、關(guān)聯(lián)的知識(shí)［1］．當(dāng)前網(wǎng)絡(luò)數(shù)據(jù)是廣泛可用的，所缺乏的只是從中提取知識(shí)的能力．有效利用網(wǎng)絡(luò)大數(shù)據(jù)價(jià)值的主要任務(wù)不僅僅是是獲取越來(lái)越多的數(shù)據(jù)，也需要從已有的數(shù)據(jù)中挖掘更多有用的知識(shí)［2］，構(gòu)建成知識(shí)庫(kù)，便于對(duì)知識(shí)更充分地利用，因此基于網(wǎng)絡(luò)的大規(guī)模知識(shí)庫(kù)的構(gòu)建是最近流行的一個(gè)研究方向，現(xiàn)有的大規(guī)模知識(shí)庫(kù)有YAGO［3－4］，DBpedia［5］，Probase［6］等．

基于大規(guī)模知識(shí)庫(kù)的關(guān)聯(lián)推理是從海量信息中挖掘知識(shí)實(shí)現(xiàn)知識(shí)庫(kù)增長(zhǎng)的有效手段之一［7］，其主要目的是利用已有的大規(guī)模知識(shí)網(wǎng)絡(luò)推理或者預(yù)測(cè)知識(shí)網(wǎng)絡(luò)中隱含的關(guān)系．目前，關(guān)聯(lián)推理已經(jīng)在個(gè)性化推薦、社區(qū)發(fā)現(xiàn)、知識(shí)問(wèn)答等方面得到廣泛應(yīng)用［8］．

現(xiàn)有的關(guān)于知識(shí)網(wǎng)絡(luò)中關(guān)聯(lián)推理的研究，采用的方法主要有有監(jiān)督學(xué)習(xí)、半監(jiān)督學(xué)習(xí)以及無(wú)監(jiān)督學(xué)習(xí)等．目前的研究更多的是基于異構(gòu)信息網(wǎng)絡(luò)的關(guān)聯(lián)推理，這里的異構(gòu)信息網(wǎng)絡(luò)包含多種不同類型的實(shí)體與關(guān)系，例如人物、地點(diǎn)、組織機(jī)構(gòu)、電影、論文等，以及它們之間可能產(chǎn)生的各種類型的關(guān)系．現(xiàn)實(shí)中典型的異構(gòu)信息網(wǎng)絡(luò)有計(jì)算機(jī)科學(xué)文獻(xiàn)網(wǎng)絡(luò)DBLP和互聯(lián)網(wǎng)電影資料庫(kù)IMDB．

研究證明，在含有時(shí)間信息的異構(gòu)網(wǎng)絡(luò)中進(jìn)行關(guān)聯(lián)推理時(shí)，考慮時(shí)間信息得到的推理結(jié)果比未考慮時(shí)間信息得到的結(jié)果更好，例如文獻(xiàn)［9－10］．同樣地，由相關(guān)研究工作［11－12］證實(shí)，加入空間信息會(huì)對(duì)異構(gòu)信息網(wǎng)絡(luò)上的關(guān)聯(lián)推理帶來(lái)更大的提升．例如，文獻(xiàn)［13］已證明，融合了空間信息的關(guān)聯(lián)推理可以獲得更好的推理結(jié)果，但是在文獻(xiàn)［13］中的研究，僅僅考慮了一種類型實(shí)體間的關(guān)聯(lián)推理，并非異構(gòu)信息網(wǎng)絡(luò)．目前，基于異構(gòu)信息網(wǎng)絡(luò)且對(duì)網(wǎng)絡(luò)中的時(shí)空信息加以利用進(jìn)行關(guān)聯(lián)推理的相關(guān)研究還很少．

針對(duì)知識(shí)網(wǎng)絡(luò)中時(shí)空信息的不斷豐富，而現(xiàn)有的一些知識(shí)網(wǎng)絡(luò)模型無(wú)法很好地刻畫這些信息的問(wèn)題，我們首先提出一個(gè)融合時(shí)間與空間信息的演化知識(shí)網(wǎng)絡(luò)表示模型．與傳統(tǒng)的異構(gòu)信息網(wǎng)絡(luò)不同，演化知識(shí)網(wǎng)絡(luò)中的點(diǎn)和邊都有相應(yīng)的時(shí)間演化函數(shù)和空間演化函數(shù)，用于表示點(diǎn)和邊上的時(shí)間信息和空間信息．利用這些時(shí)空函數(shù)可以詳細(xì)刻畫出現(xiàn)實(shí)中的實(shí)體自身的時(shí)空演化特點(diǎn)以及實(shí)體間關(guān)系的時(shí)空演變．例如在學(xué)術(shù)網(wǎng)絡(luò)中，傳統(tǒng)的異構(gòu)信息網(wǎng)絡(luò)只能推理多種類型的實(shí)體之間存在的不同類型的關(guān)系，卻沒有時(shí)序的概念，無(wú)法表達(dá)不同關(guān)系產(chǎn)生的先后順序、關(guān)系存在的時(shí)間范圍以及關(guān)系產(chǎn)生的地點(diǎn)等．這些信息對(duì)于關(guān)系預(yù)測(cè)和推薦是不可或缺的重要因素，且對(duì)于關(guān)聯(lián)推理也具有重要意義．基于演化知識(shí)網(wǎng)絡(luò)提出了一種新的關(guān)聯(lián)推理方法．由于知識(shí)網(wǎng)絡(luò)中的關(guān)聯(lián)推理是知識(shí)挖掘的重要手段，而在知識(shí)挖掘中我們最關(guān)注的無(wú)疑是推理結(jié)果的正確性，因此我們提出新的關(guān)聯(lián)推理方法旨在提高關(guān)聯(lián)推理的準(zhǔn)確率及對(duì)大規(guī)模數(shù)據(jù)的適應(yīng)性．總結(jié)起來(lái)，本文貢獻(xiàn)可歸納為以下2點(diǎn)：

1）提出了一個(gè)演化知識(shí)網(wǎng)絡(luò)表示模型，將知識(shí)的時(shí)空信息融入到整個(gè)知識(shí)網(wǎng)絡(luò)中，為知識(shí)的演化和計(jì)算提供更多的信息．

2）研究了基于演化知識(shí)網(wǎng)絡(luò)的關(guān)聯(lián)推理方法．具體講，提出一種基于混合背包問(wèn)題的關(guān)聯(lián)推理方法KP－LIM，提高關(guān)聯(lián)推理的準(zhǔn)確率和推理效率．

實(shí)驗(yàn)證明，與當(dāng)前流行的關(guān)聯(lián)推理方法相比，我們提出的關(guān)聯(lián)推理方法得到了更好的推理效果，在準(zhǔn)確率上有8%～37%的提高，且在千萬(wàn)規(guī)模的數(shù)據(jù)集上的實(shí)驗(yàn)證明我們的方法依然有效．

下面詳細(xì)介紹關(guān)聯(lián)推理的相關(guān)研究工作．目前主流的關(guān)聯(lián)推理方法是運(yùn)用機(jī)器學(xué)習(xí)的算法進(jìn)行關(guān)聯(lián)推理，基本上可被分為2類：有監(jiān)督學(xué)習(xí)方法［13－18］和無(wú)監(jiān)督學(xué)習(xí)方法［10，19－21］．其中文獻(xiàn)［13］是有監(jiān)督學(xué)習(xí)方法的經(jīng)典代表，它將關(guān)聯(lián)推理問(wèn)題當(dāng)成一個(gè)分類問(wèn)題，利用經(jīng)典的邏輯回歸方法訓(xùn)練模型實(shí)現(xiàn)關(guān)聯(lián)推理．盡管有監(jiān)督學(xué)習(xí)的方法比較流行，但是它們也存在許多弊端，例如訓(xùn)練復(fù)雜度高、平衡性較差、難以選擇合適的特征等．相反，無(wú)監(jiān)督的方法不需要關(guān)于數(shù)據(jù)分布的先驗(yàn)知識(shí)，避免了有監(jiān)督學(xué)習(xí)的訓(xùn)練復(fù)雜度高等問(wèn)題，對(duì)于大規(guī)模數(shù)據(jù)具有更強(qiáng)的適應(yīng)性．無(wú)監(jiān)督的方法主要是通過(guò)定義一些指標(biāo)來(lái)刻畫網(wǎng)絡(luò)中實(shí)體間的相似度來(lái)實(shí)現(xiàn)關(guān)聯(lián)推理，例如文獻(xiàn)［19］是近期無(wú)監(jiān)督關(guān)聯(lián)推理的典型代表，它以經(jīng)典的共同鄰居（common neighbour，CN）方法為基礎(chǔ)，加入節(jié)點(diǎn)連通性、邊連通性以及部分時(shí)間信息等信息進(jìn)行關(guān)聯(lián)推理，但該方法只利用了網(wǎng)絡(luò)中的局部信息．我們的提出的推理方法KP－LIM也是一種無(wú)監(jiān)督學(xué)習(xí)方法，該方法定義了一個(gè)拓?fù)涮卣鳌溄友诱鼓Ｊ剑↙E模式），將全圖的結(jié)構(gòu)特征以及網(wǎng)絡(luò)中的時(shí)空間信息融入到背包問(wèn)題的參數(shù)中，利用背包問(wèn)題的求解對(duì)LE模式進(jìn)行選擇，再利用選出的模式實(shí)現(xiàn)關(guān)聯(lián)推理．

另一方面，目前流行的關(guān)聯(lián)推理方法大部分是應(yīng)用于異構(gòu)信息網(wǎng)絡(luò)上的，即網(wǎng)絡(luò)中的實(shí)體與邊的類型是多種多樣的，例如文獻(xiàn)［9，15，22］等．近期又有許多工作將時(shí)間信息融入了異構(gòu)信息網(wǎng)絡(luò)中，并利用這些信息來(lái)提高關(guān)聯(lián)推理的準(zhǔn)確性．我們提出的演化知識(shí)網(wǎng)絡(luò)模型既包含知識(shí)的時(shí)間信息也包含知識(shí)的空間信息，并利用這些信息進(jìn)一步提高了關(guān)聯(lián)推理的準(zhǔn)確率．需要特別指出的是，YAGO2［4］中已經(jīng)提出了一個(gè)基于時(shí)空信息知識(shí)網(wǎng)絡(luò)的模型SPOTL，但是這個(gè)模型主要解決了YAGO2知識(shí)庫(kù)上的知識(shí)檢索與查詢問(wèn)題，并未將時(shí)空信息應(yīng)用到關(guān)聯(lián)推理問(wèn)題上．

綜上所述，由于現(xiàn)有的知識(shí)網(wǎng)絡(luò)對(duì)于知識(shí)的時(shí)空信息的描述能力有限，導(dǎo)致在進(jìn)行關(guān)聯(lián)推理時(shí)無(wú)法對(duì)時(shí)空信息進(jìn)行充分地利用，限制關(guān)聯(lián)推理準(zhǔn)確率的提高，因此我們提出一種融合了時(shí)空信息的知識(shí)演化網(wǎng)絡(luò)模型，并提出一種基于該網(wǎng)絡(luò)的推理方法，提高關(guān)聯(lián)推理的準(zhǔn)確率．

1 演化知識(shí)網(wǎng)絡(luò)模型

本節(jié)我們主要提出一個(gè)演化知識(shí)網(wǎng)絡(luò)模型和定義在該網(wǎng)絡(luò)上的一種特殊的子網(wǎng)絡(luò)——鏈接延展模式．

1．1 演化知識(shí)網(wǎng)絡(luò)

演化知識(shí)網(wǎng)絡(luò)是一個(gè)異構(gòu)的演化的多重圖，且圖中的節(jié)點(diǎn)和邊都包含時(shí)間與空間信息．具體定義如下：

定義1．演化知識(shí)網(wǎng)絡(luò)．給定一個(gè)時(shí)間集合T，空間集合S，則演化知識(shí)網(wǎng)絡(luò)GT，S可定義為一個(gè)8元組：

其中，V是演化知識(shí)網(wǎng)絡(luò)中節(jié)點(diǎn)的集合；E有向邊的集合，它的具體表示形式是一個(gè)3元組（u，v，r），這里u，v∈V，r∈R，其中R是邊的所有類型構(gòu)成的集合； ：V→A是節(jié)點(diǎn)類型的計(jì)算函數(shù)，使得每個(gè)節(jié)點(diǎn)通過(guò)該計(jì)算函數(shù)，可得到唯一的類型 （v）∈A，這里A為頂點(diǎn)的所有類型構(gòu)成的集合；φ：E→R表示在邊集合中某一條邊的計(jì)算函數(shù)，且每一個(gè)實(shí)體對(duì)間最多有｜R｜條邊；θ表示圖中邊的時(shí)間屬性信息，用來(lái)描述一條邊的發(fā)生以及存在的時(shí)間信息；τ是邊的空間屬性信息；λ是節(jié)點(diǎn)的時(shí)間屬性信息，η是節(jié)點(diǎn)的空間屬性信息．

在這個(gè)演化知識(shí)網(wǎng)絡(luò)模型中，我們記錄了圖中節(jié)點(diǎn)與邊的時(shí)間和空間信息．這里的時(shí)間信息是一系列離散的時(shí)間戳，空間信息則是一系列離散的地理位置信息．演化知識(shí)網(wǎng)絡(luò)的可演化性主要體現(xiàn)在可通過(guò)感知網(wǎng)絡(luò)中產(chǎn)生的新變化與自身進(jìn)行比較，發(fā)現(xiàn)新知識(shí)，并實(shí)現(xiàn)自我更新．網(wǎng)絡(luò)中的節(jié)點(diǎn)和邊都有時(shí)間戳信息，它們都會(huì)隨著時(shí)間的變化而演變，例如對(duì)于當(dāng)前國(guó)家元首這個(gè)節(jié)點(diǎn)，會(huì)隨著節(jié)點(diǎn)任職期滿而自動(dòng)更新為前任領(lǐng)導(dǎo)人，這便體現(xiàn)了網(wǎng)絡(luò)的時(shí)空可演化性．

1．2 鏈接延展模式

基于我們提出的演化知識(shí)網(wǎng)絡(luò)，本文著重研究在該網(wǎng)絡(luò)上的關(guān)聯(lián)推理問(wèn)題．關(guān)聯(lián)推理的主要目的是，利用知識(shí)庫(kù)中已有的知識(shí)作為基礎(chǔ)推理出兩實(shí)體間可能存在的新關(guān)系．這里我們做的關(guān)聯(lián)推理不僅僅要推理出新的邊，還要給出邊的類型．推理的主要思路是：首先構(gòu)造出所有可能存在的鏈接延展模式；然后建立一個(gè)混合背包問(wèn)題模型，將每一個(gè)模式看作背包問(wèn)題中待選擇的物品；通過(guò)背包問(wèn)題的求解，選擇出對(duì)于關(guān)聯(lián)推理有意義的模式；利用這些模式在圖中進(jìn)行匹配，推理出新的關(guān)系．

首先引入演化知識(shí)網(wǎng)絡(luò)中的鏈接延展（link extendable，LE）模式的定義，簡(jiǎn)稱為L(zhǎng)E模式．

定義2．鏈接延展模式．已知一個(gè)關(guān)系集R，知識(shí)網(wǎng)絡(luò)GT，S，我們定義GT，S上的一個(gè)子網(wǎng)絡(luò)H＝（V′，E′），V′ A，E′ R，在這個(gè)子網(wǎng)絡(luò)中任意兩節(jié)點(diǎn)都可通過(guò)一條邊進(jìn)行關(guān)聯(lián)，如果這個(gè)子網(wǎng)絡(luò)中有n個(gè)節(jié)點(diǎn)，則稱其為n元模式，我們將這個(gè)子網(wǎng)絡(luò)叫做鏈接延展模式．

由于子網(wǎng)絡(luò)中節(jié)點(diǎn)的個(gè)數(shù)越多，計(jì)算復(fù)雜度越大且對(duì)關(guān)聯(lián)推理的結(jié)果提升較小，因此本文重點(diǎn)研究3元模式．為了便于理解，下面我們簡(jiǎn)單列舉一些典型LE模式．假設(shè)A′＝｛author（Au），paper（P）｝，R′＝｛write（w），cite（c）｝，若子網(wǎng)絡(luò)中的點(diǎn)集為V′＝｛V1（Au），V2（P），V3（Au）｝，邊集E′＝｛c（V1，V2），w（V3，V2），c（V1，V3）｝，則該LE模式由圖1（a）表示；同理，若子網(wǎng)絡(luò)為V′＝｛V1（P），V2（Au），V3（P）｝，E′＝｛w（V2，V1），c（V2，V3），c（V1，V3）｝，則該LE模式可刻畫為圖1（b）．

Fig．1Examples for LE－Patterns．圖1 LE模式樣例示意圖

在真實(shí)的演化知識(shí)網(wǎng)絡(luò)中，凡是滿足LE模式要求的子網(wǎng)絡(luò)均稱為L(zhǎng)E模式的實(shí)例h，例如圖2（a）表示圖1（a）的一個(gè)實(shí)例，圖2（b）代表圖1（b）的一個(gè)實(shí)例．

Fig．2 LE－Patterns instances．圖2 不同LE模式的實(shí)例示意圖

由圖2可知，對(duì)于不同的LE模式的定義我們可以找到它相應(yīng)的實(shí)例，且對(duì)于同一個(gè)LE模式可以有多個(gè)不同的實(shí)例．在進(jìn)行關(guān)聯(lián)推理時(shí)，我們需要將LE模式進(jìn)行分解，使其成為可用來(lái)實(shí)現(xiàn)關(guān)聯(lián)推理的新的LE模式．例如圖2（a）表示的一個(gè)LE模式，我們可將其拆解為3個(gè)可用于關(guān)聯(lián)推理的新的模式，如圖3所示：

Fig．3 LE－Patterns for link prediction．圖3 用于關(guān)聯(lián)推理的LE模式示意圖

在圖3（a）中，我們將相連的兩條邊作為關(guān)聯(lián)推理的條件，單獨(dú)的一條邊作為推理的結(jié)論．在進(jìn)行關(guān)聯(lián)推理時(shí)，若已知在3個(gè)節(jié)點(diǎn)他們的類型滿足圖3（a）中Au—P—Au的要求，且節(jié)點(diǎn)類型為Au—P和P—Au的節(jié)點(diǎn)對(duì)之間的關(guān)系分別為cite和write，則我們可推出兩節(jié)點(diǎn)間存在cite關(guān)系．例如在圖2（a）中，我們已知Tom和Lily類型為作者，paper1的類型為論文，且已知Tom引用了paper1，Lily寫了paper1，則根據(jù)圖3（a）中的LE模式，我們可推理Tom和Lily之間存在引用關(guān)系．需要指出的是，在網(wǎng)絡(luò)中利用這些模式進(jìn)行推理的結(jié)果并非全部正確，例如圖1（b）所代表的模式的含義是，某一位作者寫了2篇文章，可得出這2篇文章之間存在引用關(guān)系，而事實(shí)上這個(gè)引用關(guān)系可能不存在，因此，對(duì)于網(wǎng)絡(luò)中包含的所有的模式構(gòu)成的集合，我們需要利用背包問(wèn)題的思想，從中選出置信度較高且涵蓋關(guān)系類型更廣泛的模式子集，并用子集中的所有模式進(jìn)行關(guān)聯(lián)推理．

2 關(guān)聯(lián)推理方法

2．1 基于混合背包問(wèn)題的關(guān)聯(lián)推理方法（KP－LIM）

為了實(shí)現(xiàn)基于某一演化知識(shí)網(wǎng)絡(luò)GT，S上的關(guān)聯(lián)推理，首先需要找出網(wǎng)絡(luò)中所有可能存在的可用于關(guān)聯(lián)推理的模式，通過(guò)混合背包問(wèn)題求最優(yōu)解的思想對(duì)不同模式進(jìn)行選擇．

下面我們先簡(jiǎn)要介紹一下背包問(wèn)題．背包問(wèn)題（knapsack problem）是一種組合優(yōu)化的NP完全問(wèn)題，可以描述為：給定一組物品，每種物品都有自己的重量和價(jià)值，在限定的總重量M內(nèi)，我們?nèi)绾芜x擇才能使物品的總價(jià)值最高．

這里我們將不同的模式看作背包問(wèn)題中要裝進(jìn)背包中的物品，因此每個(gè)模式需要有相應(yīng)的重量Weight和價(jià)值Value兩個(gè)參數(shù)．我們從不同LE模式在網(wǎng)絡(luò)中匹配的實(shí)例個(gè)數(shù)以及正確的實(shí)例個(gè)數(shù)的角度，給LE模式的2個(gè)參數(shù)重量Weight和價(jià)值Value做了以下定義．

定義3．模式價(jià)值Value．已知演化知識(shí)網(wǎng)絡(luò)GT，S，某一LE模式le的所有實(shí)例的集合H＝｛h1，h2，…，hn｝，其中包含n個(gè)不同實(shí)例，且每個(gè)實(shí)例中的每條邊包含有該邊產(chǎn)生的時(shí)間信息t，則le的價(jià)值V（le）為其中，ωi（t）代表某一條邊產(chǎn)生的相對(duì)時(shí)間，即ωi（t）＝t－t0，t0為整個(gè)網(wǎng)絡(luò)中邊產(chǎn)生的最早時(shí)間．因此，LE模式的價(jià)值代表了LE模式對(duì)應(yīng)所有實(shí)例間關(guān)系時(shí)間的和，即當(dāng)LE模式對(duì)應(yīng)的實(shí)例越多，且相應(yīng)的實(shí)例發(fā)生的時(shí)間越靠后，該模式的價(jià)值越大．

定義4．模式重量Weight．已知一個(gè)LE模式中包含的3個(gè)關(guān)系為E1，E2，E3，若我們要用該LE模式對(duì)關(guān)系E3進(jìn)行推理，首先通過(guò)遍歷全圖得到所有滿足LE模式中節(jié)點(diǎn)類型和關(guān)系E1，E2要求的所有實(shí)例的個(gè)數(shù)為N，且這些實(shí)例中又滿足LE模式中關(guān)系E3要求的實(shí)例的個(gè)數(shù)為n，則le的重量W（le）為

例如，由圖1（a）表示的LE模式，若用它來(lái)推理作者間的引用關(guān)系，它在全圖中所有匹配上另外2條關(guān)系規(guī)則的實(shí)例數(shù)量有100，其中2作者間存在引用關(guān)系的有99個(gè)實(shí)例，則該LE模式的重量為0．01．下面我們介紹如何將LE模式的選擇問(wèn)題建模成一個(gè)混合背包問(wèn)題．

首先，根據(jù)要推理關(guān)系的類型的不同，將所有的LE模式分成k類，因此這里的k等于關(guān)系類型的總數(shù)．假設(shè)每一類中包含Ni（i＝1，2，…，k）個(gè)不同LE模式．為了滿足所有關(guān)系類型都可以被推理出來(lái)，我們應(yīng)在每個(gè)分類中至少選出一個(gè)LE模式．最終該問(wèn)題可歸納為一個(gè)多重混合背包問(wèn)題：

其中，xij表示對(duì)于第i個(gè)分類中的第j個(gè)LE模式，xij＝1表示選擇該模式，xij＝0表示不選擇該模式，vij表示該模式的價(jià)值，wij表示重量．

為了求解上面的混合背包問(wèn)題，我們將問(wèn)題拆解成2個(gè)0－1背包問(wèn)題：1）多重選擇背包問(wèn)題，即在約束為耗費(fèi)小于M＊（M＊＜M）條件下，從每個(gè)分類中選出一個(gè)結(jié)果，這個(gè)步驟主要是保證每個(gè)分類中都有一個(gè)LE模式被選擇出來(lái)，即在后期做推理時(shí)，每種關(guān)系都可能被推理出來(lái)；2）常規(guī)的背包問(wèn)題，在耗費(fèi)小于M－M＊約束下我們可以從剩下的所有模式中選擇更多意義的模式，提高推理的召回率．

2．2 算法及分析

實(shí)現(xiàn)關(guān)聯(lián)推理的過(guò)程可主要分為以下3個(gè)步驟：1）構(gòu)造可能存在的LE模式．已知演化知識(shí)網(wǎng)絡(luò)GT，S上的邊的所有類型，則任意3種類型的邊的組合可構(gòu)成一個(gè)候選LE模式．2）背包問(wèn)題實(shí)現(xiàn)模式選擇．遍歷全圖，找出不同模式相應(yīng)的所有實(shí)例，計(jì)算得到不同模式的Weight和Value，通過(guò)混合背包問(wèn)題的求解選出有意義的LE模式．3）利用選出的模式在網(wǎng)絡(luò)中進(jìn)行匹配得到推理結(jié)果．下面算法1中給出我們提出的關(guān)聯(lián)推理算法的實(shí)現(xiàn)．

算法1．基于鏈接延展模式的關(guān)聯(lián)推理．

輸入：演化知識(shí)網(wǎng)絡(luò)GT，S，待推理的實(shí)體對(duì)集合｛（n，n′）1，（n，n′）2，…，（n，n′）k｝；

輸出：推理出的關(guān)系集合result．

由于在網(wǎng)絡(luò)中實(shí)體間關(guān)系的類型的數(shù)量較少，因此LE模式的構(gòu)造部分不是主要耗時(shí)的部分．分析可知整個(gè)關(guān)聯(lián)推理過(guò)程的計(jì)算量集中在遍歷全圖找與模式相匹配的實(shí)例的過(guò)程，即算法1中調(diào)用的算法2．在算法2中我們采用一些優(yōu)化技巧以提高效率，適應(yīng)大數(shù)據(jù)環(huán)境的要求．下面我們給出算法2具體過(guò)程．

算法2．實(shí)例匹配與查找算法．

輸入：演化知識(shí)網(wǎng)絡(luò)GT，S，LE模式集SLE＝｛le1，le2，…，lem｝；

一般的遍歷全圖找不同模式的實(shí)例的方法是，對(duì)于每一個(gè)模式，遍歷圖中的所有節(jié)點(diǎn)；對(duì)于某一個(gè)節(jié)點(diǎn)，遍歷它所有的邊，如果滿足模式要求，則以該邊的另一個(gè)端點(diǎn)為起點(diǎn)遍歷其他所有的邊，看是否滿足模式要求，依此類推．假設(shè)共有m個(gè)不同實(shí)例，全圖有n個(gè)節(jié)點(diǎn)，且圖中節(jié)點(diǎn)的平均出度入度和為r，則該運(yùn)算的復(fù)雜度為O（mnr3）．以上方法雖然容易實(shí)現(xiàn)，運(yùn)算復(fù)雜度卻很高，效率低下，因此算法2利用了一些技巧降低了時(shí)間復(fù)雜度．

首先，我們不針對(duì)每個(gè)模式遍歷一遍全圖來(lái)找實(shí)例，而是做一個(gè)映射表，在這個(gè)映射表中不同模式對(duì)應(yīng)的值為到當(dāng)前為止該模式匹配上的實(shí)例個(gè)數(shù)，因此只需遍歷一遍全圖即可得到所有模式的實(shí)例個(gè)數(shù)．由于這里我們采用的模式均為3元模式，基于三角形的特殊構(gòu)造，對(duì)于每個(gè)節(jié)點(diǎn)的具體匹配過(guò)程，我們不需要從一個(gè)節(jié)點(diǎn)出發(fā)，以廣度優(yōu)先的思想遍歷3層關(guān)系，只需要從一個(gè)節(jié)點(diǎn)出發(fā)，找出它自身的所有關(guān)系，任意2個(gè)關(guān)系為一組，若這2個(gè)關(guān)系對(duì)的終點(diǎn)之間也存在關(guān)系則可構(gòu)成一個(gè)LE模式，將映射表中的相應(yīng)模式的value值加1即可．該算法經(jīng)過(guò)優(yōu)化后的時(shí)間復(fù)雜度為O（nr2）．

3 實(shí) 驗(yàn)

本節(jié)我們將詳細(xì)介紹相關(guān)的實(shí)驗(yàn)結(jié)果，驗(yàn)證我們提出的基于混合背包問(wèn)題的關(guān)聯(lián)推理方法KPLIM的合理性與有效性，以及KP－LIM方法對(duì)于大數(shù)據(jù)環(huán)境的適應(yīng)性．

3．1 實(shí)驗(yàn)數(shù)據(jù)集及參數(shù)選擇

我們采用來(lái)自不同領(lǐng)域的數(shù)據(jù)構(gòu)建成2個(gè)演化知識(shí)網(wǎng)絡(luò)進(jìn)行關(guān)聯(lián)推理實(shí)驗(yàn)．這2個(gè)演化知識(shí)網(wǎng)絡(luò)的數(shù)據(jù)分別來(lái)自于學(xué)術(shù)領(lǐng)域和電影領(lǐng)域，均包含了多種不同類型的節(jié)點(diǎn)和關(guān)系．其中學(xué)術(shù)網(wǎng)中的數(shù)據(jù)是從知名的學(xué)術(shù)文章網(wǎng)站Soscholar①上用網(wǎng)絡(luò)爬蟲爬取得到的，在這個(gè)網(wǎng)絡(luò)中包含：1 000萬(wàn)個(gè)作者（A）、700萬(wàn)篇論文（P）、50萬(wàn)個(gè)雜志（M）、1．4萬(wàn)個(gè)會(huì)議（C）和5萬(wàn)個(gè)關(guān)鍵詞（K）．我們選用論文的發(fā)表時(shí)間以及會(huì)議的召開時(shí)間作為網(wǎng)絡(luò)中時(shí)間信息，選機(jī)構(gòu)所在地構(gòu)成網(wǎng)絡(luò)中的空間信息．

對(duì)于電影網(wǎng)，它的數(shù)據(jù)主要來(lái)自于對(duì)知名電影網(wǎng)站IMDB上的電影信息的爬?。摼W(wǎng)主要包括：演員（Ac）和導(dǎo)演（D）共4 530 159個(gè)，電影（M）2 132 383部，我們選取電影上映時(shí)間、拍攝地等信息作為電影知識(shí)網(wǎng)絡(luò)的時(shí)間與空間信息．在表1和表2中分別列舉了學(xué)術(shù)網(wǎng)和電影網(wǎng)中所有的實(shí)體間的直接關(guān)系．需要指出的是，表中羅列的是從元數(shù)據(jù)中抽取的直接關(guān)系．

Table 1 Direct Relations in the Scholar Network表1 學(xué)術(shù)網(wǎng)絡(luò)直接關(guān)系表

Table 2 Direct Relations in the Film Network表2 電影網(wǎng)絡(luò)直接關(guān)系表

①http：??www．soscholar．com?

表3中列舉了一些學(xué)術(shù)網(wǎng)絡(luò)中的常見的LE模式，其中第1列是待推理關(guān)系中2端節(jié)點(diǎn)實(shí)體的類型，第2列是待推理關(guān)系的類型，第3列是LE模式需要從網(wǎng)絡(luò)中匹配實(shí)例的規(guī)則．在電影網(wǎng)中生成規(guī)則的方法與學(xué)術(shù)網(wǎng)相同，這里不再一一列舉相應(yīng)的LE規(guī)則．

Table 3 General LE－Rules in the Scholar Network表3 學(xué)術(shù)網(wǎng)絡(luò)中常見的LE規(guī)則

對(duì)于學(xué)術(shù)網(wǎng)，已知邊的類型數(shù)，則根據(jù)LE模式的特點(diǎn)可以找出所有可能存在的LE模型，去掉一些不可能存在的模式，最終，對(duì)于學(xué)術(shù)網(wǎng)我們可得到了124個(gè)不同的模式．同理對(duì)于電影網(wǎng)，我們共得到18個(gè)模式．

實(shí)驗(yàn)過(guò)程中，我們?cè)趫D中隨機(jī)隱藏掉占整個(gè)網(wǎng)絡(luò)中所有關(guān)系數(shù)量的指定比例的關(guān)系以及它們所有的附加信息，實(shí)驗(yàn)過(guò)程中通過(guò)改變這個(gè)比例來(lái)比較不同方法的推理能力，這里由于我們做的是關(guān)聯(lián)推理，而不是關(guān)系預(yù)測(cè)或時(shí)序關(guān)聯(lián)推理，因此在隱藏關(guān)系時(shí)不考慮關(guān)系的時(shí)間順序．為了驗(yàn)證我們提出的方法的有效性，在實(shí)驗(yàn)中我們將KP－LIM方法與2種最近比較流行的關(guān)聯(lián)推理方法進(jìn)行比較，一個(gè)是經(jīng)典的有監(jiān)督算法的代表邏輯回歸方法［14］（簡(jiǎn)稱Logistic），另一個(gè)是文獻(xiàn)［8］中提出的方法M－CN＋ANC＋OAWpress（簡(jiǎn)稱CN），它是一種典型的無(wú)監(jiān)督學(xué)習(xí)方法．對(duì)于邏輯回歸方法，我們是將每一個(gè)LE模式作為一維特征，構(gòu)造訓(xùn)練數(shù)據(jù)，通過(guò)邏輯回歸算法進(jìn)行學(xué)習(xí)，學(xué)出每個(gè)特征的系數(shù)，在進(jìn)行關(guān)聯(lián)推理時(shí)給出一個(gè)實(shí)體對(duì)，匹配不同的模式．如果沒有模式可以匹配上，則推理兩節(jié)點(diǎn)間沒有關(guān)系；如果有模式匹配上則不同的關(guān)系可以得到一個(gè)分?jǐn)?shù)，當(dāng)分?jǐn)?shù)大于某一閾值時(shí)，我們推理這兩節(jié)點(diǎn)間存在這種關(guān)系．實(shí)驗(yàn)可得，當(dāng)閾值選擇為0．6時(shí)，邏輯回歸的推理效果最好，因此在后面的比較實(shí)驗(yàn)中，我們選擇閾值為0．6．而對(duì)于CN方法，在給出實(shí)體對(duì)后，針對(duì)每種關(guān)系可計(jì)算出一個(gè)得分．同理我們選擇一個(gè)閾值，當(dāng)?shù)梅执笥谠撻撝禃r(shí)，推理兩實(shí)體間存在某一關(guān)系，實(shí)驗(yàn)可知當(dāng)閾值選擇0．8時(shí)效果最好．

對(duì)于KP－LIM模型，在背包問(wèn)題中有2個(gè)參數(shù)需要確定，背包問(wèn)題的總體約束值M＞0和多重選擇背包問(wèn)題的約束條件M＊，對(duì)于M＊有一個(gè)寬泛的約束是0＜M＊＜M，而事實(shí)上我們對(duì)M＊給出一個(gè)更為嚴(yán)格的約束，即對(duì)于每一個(gè)模式分類，找出一個(gè)耗費(fèi)最小的模式，則M＊應(yīng)大于所有分類中最小耗費(fèi)值之和，用公式可表示為

對(duì)于M的值，也有一個(gè)更為嚴(yán)格的約束，即所有模式的耗費(fèi)之和，對(duì)于學(xué)術(shù)網(wǎng)M值的上限Mmax是10．2，對(duì)于電影網(wǎng)的Mmax是4．15．

為了確定M＊和M的具體值，我們首先固定M的值、變更M＊的值，來(lái)研究M＊的值變化對(duì)于關(guān)聯(lián)推理效果的影響，找出推理結(jié)果最優(yōu)時(shí)M＊的值；然后固定M＊的值，在（M＊，Mmax）的范圍內(nèi)調(diào)節(jié)M的值，找出推理結(jié)果最優(yōu)的M值，最終可通過(guò)實(shí)驗(yàn)確定出2個(gè)參數(shù)的值．圖4給出了對(duì)學(xué)術(shù)網(wǎng)進(jìn)行參數(shù)調(diào)節(jié)的過(guò)程，其中圖4（a）～（d）分別代表M＝6，7，8，10時(shí)對(duì)M＊的值進(jìn)行調(diào)節(jié)得到的測(cè)試結(jié)果．從圖4可知，當(dāng)M＝7，M＊＝5時(shí)，對(duì)于學(xué)術(shù)網(wǎng)上的關(guān)聯(lián)推理結(jié)果最好．同理我們對(duì)電影網(wǎng)上的數(shù)據(jù)進(jìn)行測(cè)試，得到當(dāng)M＝3，M＊＝2時(shí)結(jié)果最優(yōu)．

3．2 實(shí)驗(yàn)結(jié)果及分析

本節(jié)我們會(huì)通過(guò)實(shí)驗(yàn)進(jìn)行3方面的比較：1）比較KP－LIM與Logistic和CN方法間的關(guān)聯(lián)推理準(zhǔn)確率；2）演化知識(shí)絡(luò)網(wǎng)與傳統(tǒng)的異構(gòu)信息網(wǎng)絡(luò)的比較；3）KP－LIM算法對(duì)于大數(shù)據(jù)的適應(yīng)性的性能測(cè)試．

3．2．1 不同關(guān)聯(lián)推理方法的推理效果比較

在進(jìn)行不同關(guān)聯(lián)推理方法的比較實(shí)驗(yàn)時(shí)，我們選擇準(zhǔn)確率作為評(píng)價(jià)指標(biāo)，主要是因?yàn)榛诖笠?guī)模知識(shí)網(wǎng)絡(luò)的關(guān)聯(lián)推理，推理結(jié)果的正確與否具有決定性作用，推理結(jié)果作為知識(shí)必須要保證其準(zhǔn)確性，因此這里我們選準(zhǔn)確率作為指標(biāo)．

實(shí)驗(yàn)結(jié)果如表4所示，主要比較了3種不同方法的準(zhǔn)確率，在這里α表示隱去的關(guān)系數(shù)量占全圖關(guān)系總數(shù)量的比例．隨著α的增加，KP－LIM方法的表現(xiàn)均優(yōu)于其他2種方法，與有監(jiān)督算法Logistic相比，我們的方法在學(xué)術(shù)網(wǎng)上準(zhǔn)確率獲得了2%～62%的提高；對(duì)于CN方法，我們的方法獲得了28%～70%的提高，平均提高量分別為29%和37%．同理在電影網(wǎng)上，我們的方法分別獲得了和1%～22%和20%～30%的提高，平均提高值分別為8%和24%．綜合以上結(jié)果可得出結(jié)論，KP－LIM方法在不同的數(shù)據(jù)集上，比當(dāng)前比較流行的2種方法均取得更好的推理結(jié)果．其主要原因是，我們的方法將不同模式的特點(diǎn)以及全圖的背景知識(shí)信息融入到背包問(wèn)題中，通過(guò)背包問(wèn)題的求解，從模式集合中選出高質(zhì)量的模式進(jìn)行關(guān)聯(lián)推理；而Logistic采用了所有的模式，僅僅通過(guò)訓(xùn)練數(shù)據(jù)給不同的模式學(xué)習(xí)出不同的系數(shù)，既未將全部的背景知識(shí)信息加以利用，模型的好壞完全受訓(xùn)練數(shù)據(jù)好壞的影響，又未對(duì)模式進(jìn)行篩選；而CN方法只考慮了待推理的2個(gè)實(shí)體的相關(guān)關(guān)系，對(duì)圖的結(jié)構(gòu)信息利用不充分，因而它的準(zhǔn)確率最低．

Fig．4 Parameter tuning on the scholar network．圖4 學(xué)術(shù)網(wǎng)調(diào)參結(jié)果

Table 4 Precision Obtained by Using Different Inference Methods表4 不同關(guān)聯(lián)推理方法準(zhǔn)確率值的比較%

3．2．2 演化知識(shí)網(wǎng)絡(luò)與傳統(tǒng)網(wǎng)絡(luò)的比較

在3．2．1節(jié)中我們通過(guò)實(shí)驗(yàn)證明了KP－LIM與其他幾個(gè)關(guān)聯(lián)推理中的經(jīng)典方法在準(zhǔn)確率上有較大的提高，其功于我們提出的基于混合背包問(wèn)題的模式選擇策略色優(yōu)越性，同時(shí)我們猜想演化知識(shí)網(wǎng)絡(luò)模型自身也對(duì)與推理結(jié)果的準(zhǔn)確率的提高有一定的幫助．因此，我們分別在演化知識(shí)網(wǎng)絡(luò)（EKN）和異構(gòu)信息網(wǎng)絡(luò)（HIN）中采用KP－LIM方法進(jìn)行關(guān)聯(lián)推理，比較2個(gè)網(wǎng)絡(luò)中的推理效果．在2個(gè)網(wǎng)絡(luò)中，我們分別隱掉相同的關(guān)系，再對(duì)這些關(guān)系類型進(jìn)行推理，由于傳統(tǒng)的異構(gòu)信息網(wǎng)絡(luò)中沒有時(shí)間信息，因此只能采用弱化的KP＿LIM方法進(jìn)行模式選擇，即模式價(jià)值的定義有所改變，改為與該模式所有匹配的實(shí)例的個(gè)數(shù)．推理結(jié)果如圖5所示：

Fig．5 Link inference on different networks．圖5 不同網(wǎng)絡(luò)中的關(guān)聯(lián)推理比較

由圖5可知，隨著隱掉邊的比例的變化，EKN上的推理準(zhǔn)確率始終比HIN高，提高比例為1．9%～87%．由此可見，演化知識(shí)網(wǎng)絡(luò)與異構(gòu)信息網(wǎng)絡(luò)相比對(duì)關(guān)聯(lián)推理有一定的幫助，這主要是因?yàn)檠莼R(shí)網(wǎng)絡(luò)中包含點(diǎn)與邊的時(shí)空信息，這些信息對(duì)于關(guān)聯(lián)推理的準(zhǔn)確率的提高具有重要意義．值得注意的是，隨著隱掉邊的比例的增加，兩者的推理準(zhǔn)確率均呈下降趨勢(shì)，這是由于隱掉邊的比例越大，已有的可用于推理的知識(shí)越少，因此推理的準(zhǔn)確率有一定的下降．

3．2．3 KP－LIM的性能測(cè)試

由于在大數(shù)據(jù)環(huán)境下，數(shù)據(jù)量急劇增長(zhǎng)，能否適應(yīng)大數(shù)據(jù)的挑戰(zhàn)，也是衡量一個(gè)算法好壞的重要方面，因此，下面我們對(duì)KP－LIM方法的計(jì)算性能進(jìn)行測(cè)試．首先分別構(gòu)造不同大小的知識(shí)網(wǎng)絡(luò)，測(cè)試在不同規(guī)模的網(wǎng)絡(luò)上KP－LIM進(jìn)行關(guān)聯(lián)推理的時(shí)間消耗，這里我們將網(wǎng)絡(luò)中的點(diǎn)的數(shù)量從100萬(wàn)逐漸增加到1 000萬(wàn)，并記錄下推理時(shí)間的變化，如圖6所示．

由圖6可知，隨著網(wǎng)絡(luò)規(guī)模的迅速增加，我們提出的KP－LIM推理方法時(shí)間消耗的增長(zhǎng)緩慢．當(dāng)網(wǎng)絡(luò)規(guī)模擴(kuò)大了10倍，推理耗時(shí)僅從8．372s增加到15．726s．在算法2我們也對(duì)KP－LIM方法的時(shí)間復(fù)雜度進(jìn)行了分析，該算法的主要時(shí)間消耗集中在遍歷全圖找不同模式實(shí)例的過(guò)程，復(fù)雜度為O（nr2），這里n代表網(wǎng)絡(luò)中節(jié)點(diǎn)的個(gè)數(shù)，r為節(jié)點(diǎn)的出入度，因此隨著網(wǎng)絡(luò)規(guī)模的增加，r的變化較小，因此整個(gè)算法的時(shí)間消耗主要受到網(wǎng)絡(luò)中節(jié)點(diǎn)的個(gè)數(shù)n的影響，因而隨著網(wǎng)絡(luò)規(guī)模的增加算法的時(shí)間消耗呈線性增長(zhǎng)．綜上所述，我們提出的關(guān)系KP－LIM不僅在推理準(zhǔn)確率上取得了較好的結(jié)果，其計(jì)算成本也并沒有對(duì)著網(wǎng)絡(luò)規(guī)模的擴(kuò)大而呈指數(shù)增長(zhǎng)，因此KP－LIM的計(jì)算性能也能夠滿足大規(guī)模知識(shí)網(wǎng)絡(luò)對(duì)關(guān)聯(lián)推理性能與效率的要求．

Fig．6 The change of time consumption with the increase scale of relation network．圖6 隨著網(wǎng)絡(luò)規(guī)模的增加關(guān)聯(lián)推理的時(shí)間消耗

4 總結(jié)與展望

本文首先提出了一個(gè)融合了時(shí)間與空間信息的演化知識(shí)網(wǎng)絡(luò)，基于該網(wǎng)絡(luò)提出了一種關(guān)聯(lián)推理方法．實(shí)驗(yàn)證明我們的方法比當(dāng)前流行的一些關(guān)聯(lián)推理方法取得了更高的準(zhǔn)確率，且在大數(shù)據(jù)的環(huán)境下依然擁有較好適應(yīng)性．但該KP－LIM方法也存在一定的局限性，例如對(duì)于網(wǎng)絡(luò)中已有的關(guān)系數(shù)量有一定的依賴性、無(wú)法很好地應(yīng)對(duì)冷啟動(dòng)問(wèn)題，且對(duì)于網(wǎng)絡(luò)中的空間信息利用不夠．

因此，關(guān)于這個(gè)工作，仍有以下4個(gè)需要研究的方向：1）KP－LIM方法對(duì)知識(shí)網(wǎng)絡(luò)中已有的關(guān)系數(shù)量的依賴性較強(qiáng)，當(dāng)面對(duì)冷啟動(dòng)問(wèn)題時(shí)，如何保證推理的準(zhǔn)確率有待進(jìn)一步研究；2）對(duì)于演化知識(shí)網(wǎng)絡(luò)中的空間信息的利用有限，下一步可研究如何更充分地利用網(wǎng)絡(luò)中的時(shí)空信息，進(jìn)一步提高推理效果；3）從知識(shí)表示的角度，研究知識(shí)網(wǎng)絡(luò)的演化性和關(guān)聯(lián)推理，是近年來(lái)知識(shí)網(wǎng)絡(luò)的關(guān)聯(lián)推理研究的新方向，相關(guān)工作包括文獻(xiàn)［23］；4）研究時(shí)序關(guān)系的推理，即推理知識(shí)網(wǎng)絡(luò)中關(guān)系產(chǎn)生的時(shí)間，是進(jìn)一步研究知識(shí)網(wǎng)絡(luò)演化性的又一重要方向，相關(guān)工作包括文獻(xiàn)［24］．

［1］Wang Yuanzhuo，Jia Yantao，Liu Dawei，et al．Open Web knowledge aided information search and data mining［J］．Journal of Computer Research and Development，2015，52（2）：456 474（in Chinese）（王元卓，賈巖濤，劉大偉，等．基于開放網(wǎng)絡(luò)知識(shí)的信息檢索與數(shù)據(jù)挖掘［J］．計(jì)算機(jī)研究與發(fā)展，2015，52（2）：456 474）

［2］Wang Yuanzhuo，Jin Xiaolong，Cheng Xueqi．Network big data：Present and future［J］．Chinese Journal of Computers，2013，36（6）：1125 1138（in Chinese）（王元卓，靳小龍，程學(xué)旗．網(wǎng)絡(luò)大數(shù)據(jù)：現(xiàn)狀與挑戰(zhàn)［J］．計(jì)算機(jī)學(xué)報(bào)，2013，36（6）：1125 1138）

［3］Lujun F，Anish D S，Cong Y，et al．Rex：Explaining relationships between entity pairs［J］．VLDB Endowment，2011，5（3）：241 252

［4］Suchanek F M，Kasneci G，Weikum G．Yago：A large ontology from Wikipedia and wordnet［J］．Web Semantics：Science，Services and Agents on the World Wide Web，2008，6（3）：203 217

［5］Hoffart J，Suchanek F M，Berberich K，et al．YAGO2：A spatially and temporally enhanced knowledge base from Wikipedia［C］??Proc of the 23rd Int Joint Conf on Artificial Intelligence．Menlo Park，CA：AAAI，2013：3161 3165

［6］Jia Yantao，Wang Yuanzhuo，Cheng Xueqi，et al．OpenKN：An open knowledge computational engine for network big data［C］??Proc of the 2014Int Conf on Advances in Social Networks Analysis and Mining（ASONAM 14）．Los Alamitos，CA：IEEE Computer Society，2014：657 664

［7］Lin Hailun，Jia Yantao，Wang Yuanzhuo，et al．Populating knowledge base with collective entity mentions：A graphbased approach［C］??Proc of the 2014Int Conf on Advances in Social Networks Analysis and Mining（ASONAM 14）．Los Alamitos，CA：IEEE Computer Society，2014：504 611

［8］Cheng Xueqi，Jin Xiaolong，Wang Yuanzhuo．Survey on big data system and analytic technology［J］．Journal of Software，2014，25（9）：1889 1908（in Chinese）（程學(xué)旗，靳小龍，王元卓．大數(shù)據(jù)系統(tǒng)和分析技術(shù)綜述［J］．軟件學(xué)報(bào)，2014，25（9）：1889 1908）

［9］Lee J B，Adorna H．Link prediction in a modified heterogeneous bibliographic network［C］??Proc of the 2012 Int Conf on Advances in Social Networks Analysis and Mining（ASONAM 12）．Los Alamitos，CA：IEEE Computer Society，2012：442 449

［10］Rossetti G，Berlingerio M，Giannotti F．Scalable link prediction on multidimensional networks［C］??Proc of the 11th Int Conf on Data Mining Workshops（ICDMW 11）．Los Alamitos，CA：IEEE Computer Society，2011：979 986

［11］Cho E，Myers S A，Leskovec J．Friendship and mobility：User movement in location－based social networks［C］??Proc of the 17th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining．New York：ACM，2011：1082 1090

［12］Wang Dashun，Pedreschi D，Song C，et al．Human mobility，social ties，and link prediction［C］??Proc of the 17th ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining．New York：ACM，2011：1100 1108

［13］Crandall D J，Backstrom L，Cosley D，et al．Inferring social ties from geographic coincidences［J］．National Academy of Sciences，2010，107（52）：22436 22441

［14］Popescul A，Ungar L H．Statistical relational learning for link prediction［C?OL］??Proc of the 18th Int Joint Conf on Artificial Intelligence．Acapulco，Mexico：IJCAI，2003［2016－01－05］．http：??www．cis．upenn．edu?～ungar?papers? popescul?statistical03link．pdf

［15］Sun Yizhou，Barber R，Gupta M，et al．Co－author relationship prediction in heterogeneous bibliographic networks［C］??Proc of the 2011Int Conf on Advances in Social Networks Analysis and Mining（ASONAM 11）．Los Alamitos，CA：IEEE Computer Society，2011：121 128

［16］Sun Yizhou，Han Jiawei，Aggarwal C C，et al．When will it happen？：Relationship prediction in heterogeneous information networks［C］??Proc of the 5th ACM Int Conf on Web Search and Data Mining（WSDM 12）．New York：ACM，2012：663 672

［17］Tang Jie，Lou Tiancheng，Kleinberg J．Inferring social ties across heterogenous networks［C］??Proc of the 5th ACM Int Conf on Web Search and Data Mining（WSDM 12）．New York：ACM，2012：743 752

［18］Jia Yantao，Wang Yuanzhuo，Li Jingyuan，et al．Structuralinteraction link prediction in microblogs［C］??Proc of the 22nd Int Conf on World Wide Web Companion（WWW 13）．New York：ACM，2013：193 194

［19］Davis D，Lichtenwalter R，Chawla N V．Multi－relational link prediction in heterogeneous information networks［C］??Proc of the 2011Int Conf on Advances in Social Networks Analysis and Mining（ASONAM 11）．Los Alamitos，CA：IEEE Computer Society，2011：281 288

［20］Liu Dawei，Wang Yuanzhuo，Jia Yantao．LSDH：A hashing approach for large－scale link prediction in microblogs［C］?? Proc of the 28th AAAI 14．Palo Alto，CA：AAAI，2014：3120 3121

［21］Zhao Zeya，Jia Yantao，Wang Yuanzhuo．Content－structural relation inference in knowledge base［C］??Proc of the 28th AAAI 14．Palo Alto，CA：AAAI，2014：3154 3155

［22］Yang Yang，Chawla N V，Sun Yizhou，et al．Predicting links in multi－relational and heterogeneous networks［C］?? Proc of the 13th Int Conf on Data Mining Workshops（ICDM 12）．Los Alamitos，CA：IEEE Computer Society，2012：755 764

［23］Jia Yantao，Wang Yuanzhuo，Lin Hailun，et al．Locally adaptive translation for knowledge graph embedding［C］?? Proc of the 30th AAAI 16．a(chǎn)rXiv preprint arXiv：1512．01370［24］Zhao Zeya，Jia Yantao，Wang Yuanzhuo，et al．Temporal

link prediction based on dynamic heterogeneous information

network［J］．Journal of Computer Research and

Development，2015：52（8）：1735 1741（in Chinese）

（趙澤亞，賈巖濤，王元卓，等．基于動(dòng)態(tài)異構(gòu)信息網(wǎng)絡(luò)的時(shí)

序關(guān)系預(yù)測(cè)［J］．計(jì)算機(jī)研究與發(fā)展，2015，52（8）：1735

1741）

Wang Yuanzhuo，born in 1978．PhD，associate professor．IEEE member and senior member of China Computer Federation．His current research interests include social computing，open knowledge network，network security analysis，stochastic game model，etc．

Zhao Zeya，born in 1990．Master．Her main research interests include open knowledge engineering，data mining，social computing．

Jia Yantao，born in 1983．PhD，assistant professor．His main research interests include open knowledge network，social computing，combinatorial algorithms．

Jin Xiaolong，born in 1976．Associate professor，PhD supervisor．His research interests include social computing，multiagent systems，performance modelling and evaluation，etc．

Cheng Xueqi，born in 1971．Professor，PhD supervisor．His research interests include network science，Web search ＆data mining．

Link Inference in Large Scale Evolutionable Knowledge Network

Zhao Zeya1，2，3，Jia Yantao1，Wang Yuanzhuo1，Jin Xiaolong1，and Cheng Xueqi11（Key Laboratory of Network Data Science ＆Technology（Institute of Computing Technology，Chinese Academy of Sciences），Beijing100190）2（The PLA Information Engineering University，Zhengzhou450000）3（TH－Satelite Center of China，Beijing102012）

In the era of network big data，the spatiotemporal information of knowledge is richly stored in knowledge networks，such as the building time of links，the lifetime of vertices，etc．Traditional knowledge network representation models are mostly blind to either the spatial or the temporal information of vertices and links in the network．It has been verified in the literature that considering the spatial or the temporal information of vertices and links can promote the performance of link inference in knowledge networks．In this paper，we propose an evolutionable knowledge network model，i．e．，a heterogeneous knowledge network，in which vertices and edges are anchored in both time and space dimensions．Then based on the model，we further study the link inference problem on evolutionable knowledge networks．Specifically，we firstly define the link extendable patterns to characterize the link formation process，and then propose a knapsack constrained link inference method to turn the link inference problem into a combinatorial optimization problem with the knapsack－like constrains．The dynamic programming technique is used to solve the optimization problem in pseudo－polynomial time complexity．Experiments on real data sets suggest the better effectiveness and scalability of our proposed method over large－scale networks than the state－of－the－art methods．

link inference；evolutionable knowledge network；knapsack problem；link extendable（LE）pattern；knowledge base

TP182

2014－11－24；

2015－03－13

國(guó)家“九七三”重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃基金項(xiàng)目（2014CB340405，2013CB329602）；國(guó)家自然科學(xué)基金項(xiàng)目（61173008，61232010，61303244，61402442）；北京市科技新星計(jì)劃項(xiàng)目（Z121101002512063）；國(guó)家科技支撐計(jì)劃項(xiàng)目（2012BAH39B04）；北京市自然科學(xué)基金青年基金項(xiàng)目（4154086）

This work was supported by the National Basic Research Program of China（973Program）（2014CB340405，2013CB329602），the National Natural Science Foundation of China（61173008，61232010，61303244，61402442），Beijing Nova Program（Z121101002512063），the National Key Technology Research and Development Program of China（2012BAH39B04），and the Natural Science Foundation of Beijing（4154086）．

摘 要 網(wǎng)絡(luò)大數(shù)據(jù)時(shí)代的到來(lái)使得知識(shí)網(wǎng)絡(luò)中時(shí)空信息越來(lái)越豐富．現(xiàn)有的知識(shí)網(wǎng)絡(luò)描述模型對(duì)知識(shí)的時(shí)空信息刻畫不足．研究證明，利用網(wǎng)絡(luò)中知識(shí)的時(shí)空信息以及相關(guān)性，能夠提高網(wǎng)絡(luò)中知識(shí)間的關(guān)聯(lián)推理的準(zhǔn)確率．針對(duì)以上問(wèn)題，首先提出了一種包含時(shí)空信息的演化知識(shí)網(wǎng)絡(luò)表示模型，然后研究在該網(wǎng)絡(luò)模型上的關(guān)聯(lián)推理問(wèn)題，提出了一種基于背包問(wèn)題的知識(shí)間關(guān)聯(lián)推理方法．在多個(gè)數(shù)據(jù)集上的實(shí)驗(yàn)證明了所提出的關(guān)聯(lián)推理方法的有效性以及對(duì)大規(guī)模知識(shí)網(wǎng)絡(luò)的適應(yīng)性．