童 寧，徐 珊，湯 穎，秦緒佳

(浙江工業(yè)大學(xué) 計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院，杭州 310023)

1 引 言

圖數(shù)據(jù)包含豐富的信息，人們可以使用圖查詢相關(guān)技術(shù)來(lái)從圖結(jié)構(gòu)數(shù)據(jù)中挖掘到想要的信息.信息網(wǎng)絡(luò)是一種具有圖結(jié)構(gòu)的數(shù)據(jù)，在實(shí)際應(yīng)用中，大多數(shù)的信息網(wǎng)絡(luò)是異構(gòu)的，稱為異構(gòu)信息網(wǎng)絡(luò)，例如影視信息網(wǎng)絡(luò)、蛋白質(zhì)結(jié)構(gòu)網(wǎng)絡(luò)、文獻(xiàn)信息網(wǎng)絡(luò)等.這類網(wǎng)絡(luò)中的節(jié)點(diǎn)和邊并不是單一類型的，如在影視信息網(wǎng)絡(luò)中，節(jié)點(diǎn)有“電影”和“影人”2種類型，邊有“參演”和“執(zhí)導(dǎo)”2種類型.節(jié)點(diǎn)和邊的多樣性使得對(duì)異構(gòu)網(wǎng)絡(luò)的挖掘相較于同構(gòu)網(wǎng)絡(luò)更具有挑戰(zhàn)性.圖查詢作為一種常用的異構(gòu)網(wǎng)絡(luò)挖掘方法，也面臨著節(jié)點(diǎn)和邊多樣性的問(wèn)題.倘若在進(jìn)行圖查詢時(shí)不區(qū)分網(wǎng)絡(luò)中節(jié)點(diǎn)和邊的類型則會(huì)損失這些不同的類型所蘊(yùn)含的語(yǔ)義信息.

在異構(gòu)信息網(wǎng)絡(luò)中，節(jié)點(diǎn)間的語(yǔ)義關(guān)系不但與節(jié)點(diǎn)和邊類型相關(guān)，還與節(jié)點(diǎn)屬性相關(guān).以影視信息網(wǎng)絡(luò)為例，電影的簡(jiǎn)介是電影節(jié)點(diǎn)的屬性之一，以文本的方式來(lái)描述電影的內(nèi)容，該文本屬性能夠影響到節(jié)點(diǎn)間的關(guān)系模式.舉例來(lái)說(shuō)，兩位影人通過(guò)一部電影產(chǎn)生了合作的關(guān)系，連接的電影可以是電影A，其文本屬性將其描述為關(guān)于家庭的喜劇電影，也可以是電影B，其文本屬性將其描述為關(guān)于校園的愛情電影.當(dāng)選擇電影A作為兩位影人之間的連接節(jié)點(diǎn)時(shí)，他們之間的關(guān)系可以被描述成“兩位影人合作了一部家庭喜劇類的電影”.當(dāng)選擇電影B時(shí)，兩位影人之間的關(guān)系可以被描述成“兩位影人合作了一部校園愛情類的電影”.因此，使用圖查詢技術(shù)挖掘異構(gòu)信息網(wǎng)絡(luò)中的關(guān)系語(yǔ)義時(shí)需要考慮節(jié)點(diǎn)文本屬性的影響.而以往的異構(gòu)網(wǎng)絡(luò)圖查詢工作往往未結(jié)合節(jié)點(diǎn)文本屬性[1，2]，這在一定程度上會(huì)影響對(duì)異構(gòu)網(wǎng)絡(luò)中蘊(yùn)含的豐富語(yǔ)義信息的分析和挖掘.

由于異構(gòu)信息網(wǎng)絡(luò)包含著復(fù)雜的類型信息和屬性信息，對(duì)異構(gòu)信息網(wǎng)絡(luò)進(jìn)行圖查詢需要解決以下問(wèn)題：

1)查詢輸入的問(wèn)題.常見的查詢語(yǔ)言輸入和構(gòu)建查詢模板輸入都需要用戶額外學(xué)習(xí)查詢語(yǔ)言和網(wǎng)絡(luò)模式.由于異構(gòu)信息網(wǎng)絡(luò)的復(fù)雜性，對(duì)異構(gòu)信息網(wǎng)絡(luò)進(jìn)行查詢時(shí)，需要構(gòu)建更復(fù)雜的查詢模板.這給普通用戶帶來(lái)了一定的負(fù)擔(dān).

2)不同語(yǔ)義關(guān)系組合的問(wèn)題.在異構(gòu)信息網(wǎng)絡(luò)中，兩個(gè)對(duì)象間存在多條、跨越多個(gè)節(jié)點(diǎn)類型的語(yǔ)義關(guān)系.傳統(tǒng)的異構(gòu)網(wǎng)絡(luò)圖查詢通?；谠窂絹?lái)表達(dá)這些語(yǔ)義關(guān)系，但是節(jié)點(diǎn)的文本屬性也能對(duì)查詢對(duì)象的語(yǔ)義關(guān)系造成影響.因此，在圖查詢的過(guò)程中需要在計(jì)算元路徑重要度的同時(shí)結(jié)合文本屬性從而提高查詢準(zhǔn)確率.

3)對(duì)查詢結(jié)果的結(jié)構(gòu)信息和語(yǔ)義信息進(jìn)行分析.查詢得到的結(jié)果子圖具有拓?fù)浣Y(jié)構(gòu)特征，而且節(jié)點(diǎn)文本屬性包含了重要的語(yǔ)義信息.因此，結(jié)合結(jié)果子圖的拓?fù)浣Y(jié)構(gòu)信息和語(yǔ)義信息對(duì)查詢結(jié)果進(jìn)行分析對(duì)于用戶快速理解網(wǎng)絡(luò)的異構(gòu)關(guān)系模式非常重要.

為了解決上述問(wèn)題，本文在圖查詢各階段任務(wù)的驅(qū)動(dòng)下，設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)針對(duì)異構(gòu)信息網(wǎng)絡(luò)的圖查詢可視分析系統(tǒng)HINQVis(heterogeneous information network query visualization system).首先，針對(duì)圖查詢輸入階段的問(wèn)題，本文從簡(jiǎn)單的用戶輸入中提取可能的關(guān)系模式，使用元路徑表示這些關(guān)系模式，并結(jié)合用戶輸入的短文本計(jì)算元路徑的重要度來(lái)衡量不同關(guān)系模式的重要程度，在系統(tǒng)中使用模式視圖展示元路徑和重要度.其次，在查詢過(guò)程中，根據(jù)元路徑的重要度結(jié)合多條元路徑，得到更復(fù)雜的查詢模板用于查詢.最后，在查詢結(jié)果分析階段，提取結(jié)果子圖中的拓?fù)浣Y(jié)構(gòu)特征并使用總覽視圖和子圖視圖進(jìn)行展示，使用細(xì)節(jié)視圖對(duì)結(jié)果子圖中節(jié)點(diǎn)的相關(guān)屬性進(jìn)行可視化，通過(guò)總覽視圖、子圖視圖和細(xì)節(jié)視圖間的聯(lián)動(dòng)交互探索查詢結(jié)果中潛藏的信息.

本文提出了一種結(jié)合短文本的元路徑重要度計(jì)算方法，在計(jì)算元路徑重要度時(shí)能夠?qū)⒂脩糨斎氲亩涛谋九c節(jié)點(diǎn)的文本屬性相結(jié)合；實(shí)現(xiàn)了一種結(jié)合多條元路徑的實(shí)例生成和向量化方法，能夠根據(jù)元路徑的重要度生成查詢實(shí)例并將其向量化；設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)針對(duì)異構(gòu)信息網(wǎng)絡(luò)的基于圖查詢的可視化分析系統(tǒng)，對(duì)查詢結(jié)果進(jìn)行展示，供用戶交互探索.

2 相關(guān)工作

2.1 圖查詢輸入

常見的圖查詢輸入方式有查詢語(yǔ)言輸入，如SPARQL[3]，XPATH[4]，XQUERY[5].但是這些查詢語(yǔ)言的使用需要研究人員有著相關(guān)的專業(yè)知識(shí)，因此為了簡(jiǎn)化查詢輸入，一些圖形工具被開發(fā)了出來(lái).Ng等[6]開發(fā)了FGreat框架，能夠交互式地自動(dòng)完成圖查詢.Lissandrini等[7]通過(guò)直觀的建議來(lái)對(duì)用戶的查詢進(jìn)行擴(kuò)展，以幫助用戶探索知識(shí)圖譜.Qiu等[8]將具有復(fù)雜語(yǔ)義的問(wèn)題轉(zhuǎn)化成查詢圖，以對(duì)知識(shí)圖譜進(jìn)行圖查詢.Huang等[9]提出一種跨語(yǔ)言的檢索方法，能解決用戶輸入與查詢內(nèi)容語(yǔ)言不不同的問(wèn)題.Orko[10]能夠從語(yǔ)音輸入中提取出目標(biāo)節(jié)點(diǎn)進(jìn)行查詢.VIGOR[11]從用戶輸入的查詢語(yǔ)言中提取查詢示例，然后將查詢結(jié)果可視化并進(jìn)行分析.Wang等[12]簡(jiǎn)化了SPARQL查詢來(lái)幫助用戶對(duì)知識(shí)圖進(jìn)行查詢.Jung等[13]提出了一種將韓語(yǔ)查詢直接轉(zhuǎn)化為SPARQL查詢的方法.Hu等[14]將關(guān)鍵詞搜索和SPARQL語(yǔ)句結(jié)合，提出了一種準(zhǔn)確率更高的問(wèn)答系統(tǒng).Shuai等[15]設(shè)計(jì)了一個(gè)針對(duì)電影數(shù)據(jù)的問(wèn)答系統(tǒng)，能夠?qū)⒂脩糨斎氲闹形膯?wèn)題轉(zhuǎn)換成知識(shí)圖查詢語(yǔ)句，在Neo4j圖數(shù)據(jù)庫(kù)中查詢答案.Eviza[16]通過(guò)用戶與系統(tǒng)之間的交互式對(duì)話，不斷更新系統(tǒng)的查詢能力.

由于自然語(yǔ)言的便利性，本文的工作在圖查詢階段使用自然語(yǔ)言作為目標(biāo)節(jié)點(diǎn)對(duì)和其約束的輸入.同時(shí)為了使系統(tǒng)更加簡(jiǎn)便，與上述部分工作不同的是，本文的工作不需要用戶構(gòu)建查詢模板.

2.2 子圖查詢

子圖查詢一般可以根據(jù)其查詢方式的不同，分成關(guān)鍵詞子圖、凝聚子圖以及圖模式匹配3大類.凝聚子圖查詢(cohesive subgraph search)[17]關(guān)注于圖數(shù)據(jù)中聯(lián)系緊密的部分子圖.關(guān)鍵詞圖查詢(keyword search on graph)[18]能夠根據(jù)輸入的關(guān)鍵詞，在圖數(shù)據(jù)中搜索匹配關(guān)鍵詞的子圖，這些子圖的頂點(diǎn)滿足了關(guān)鍵詞帶來(lái)的約束.圖模式匹配(graph pattern matching)能夠根據(jù)輸入的模式圖，從圖數(shù)據(jù)中搜索出擁有相同模式的所有子圖.然而該方法面臨的困難一是大部分圖數(shù)據(jù)中的頂點(diǎn)和邊過(guò)多，二是根據(jù)不同的匹配語(yǔ)義會(huì)形成圖模擬[19]、子圖同構(gòu)[20]和強(qiáng)模擬等問(wèn)題[21].Gao等[22]提出了“時(shí)間尊重流程圖”的概念，在帶有時(shí)間屬性的圖數(shù)據(jù)上進(jìn)行圖模式匹配.Liu等[23]提出了一種多約束的圖模式匹配方法，通過(guò)“強(qiáng)社交圖”的概念來(lái)探索大型的社交網(wǎng)絡(luò)數(shù)據(jù).DiffWalk[24]以圖數(shù)據(jù)中影響最大的節(jié)點(diǎn)作為起始，通過(guò)擴(kuò)散游走來(lái)遍歷大型圖數(shù)據(jù)，從而達(dá)到圖模式匹配的目的.

圖模式匹配查詢被廣泛應(yīng)用于大規(guī)模圖數(shù)據(jù)的挖掘.本文使用圖模式匹配進(jìn)行子圖查詢，并且通過(guò)借助節(jié)點(diǎn)對(duì)的相似性，使其避免了子圖同構(gòu)等問(wèn)題來(lái)完成子圖查詢.

3 系統(tǒng)任務(wù)分析和概述

3.1 任務(wù)分析

在圖查詢輸入、子圖查詢和查詢結(jié)果分析3階段任務(wù)驅(qū)動(dòng)下，本文為HINQVis系統(tǒng)定義了如下任務(wù)，以指導(dǎo)系統(tǒng)的設(shè)計(jì)：

任務(wù)1.自動(dòng)地從查詢輸入中提取用戶所希望的關(guān)系模式.在本文的圖查詢過(guò)程中，用戶首先輸入一對(duì)或者一個(gè)實(shí)例節(jié)點(diǎn)，然后通過(guò)一句短文本對(duì)其所希望的查詢結(jié)果進(jìn)行描述，該輸入方式通俗易懂且便于操作.系統(tǒng)需要根據(jù)用戶的輸入，從中提取出所有可能的關(guān)系模式.

任務(wù)2.支持用戶以交互的方式構(gòu)造查詢模板.根據(jù)用戶的輸入可能會(huì)提取到較多的關(guān)系模式，若結(jié)合所有提取到的模式進(jìn)行查詢，則很可能會(huì)得到很多用戶不希望的結(jié)果.所以系統(tǒng)需要向用戶提供一種交互方式，讓用戶選擇感興趣的關(guān)系模式，再根據(jù)用戶所選的結(jié)果進(jìn)行后續(xù)的圖查詢.

任務(wù)3.對(duì)子圖特征進(jìn)行概述，提供一個(gè)自上而下的探索方式.用戶難以從相似的拓?fù)浣Y(jié)構(gòu)中看出各個(gè)結(jié)果子圖的特征，所以系統(tǒng)在得到查詢結(jié)果之后，需要向用戶展示不同子圖的特征，讓用戶可以根據(jù)此特征來(lái)對(duì)不同的查詢結(jié)果進(jìn)行有效區(qū)分.

任務(wù)4.對(duì)查詢得到的所有子圖的細(xì)節(jié)信息進(jìn)行有效展示.在通過(guò)查詢得到結(jié)果子圖后，用戶需要通過(guò)觀察節(jié)點(diǎn)的 詳細(xì)信息來(lái)理解查詢的結(jié)果.所以系統(tǒng)需要在展示結(jié)果子圖時(shí)，以直觀的方式向用戶呈現(xiàn)每個(gè)結(jié)果子圖中各個(gè)節(jié)點(diǎn)與邊的細(xì)節(jié)信息.

任務(wù)5.對(duì)查詢得到的各個(gè)節(jié)點(diǎn)的屬性信息進(jìn)行有效展示.本文通過(guò)用戶輸入的短文本來(lái)約束查詢結(jié)果，通過(guò)觀察節(jié)點(diǎn)屬性中包含的文本屬性可以分析出短文本約束的效果.所以系統(tǒng)需要有效地向用戶展示查詢結(jié)果中節(jié)點(diǎn)的文本屬性，同時(shí)也需要將節(jié)點(diǎn)的其他屬性同步地呈現(xiàn)出來(lái).

3.2 系統(tǒng)概述

HINQVis系統(tǒng)概覽如圖1所示，針對(duì)每個(gè)任務(wù)，本文都設(shè)計(jì)了相應(yīng)的視圖來(lái)滿足需求，這些視圖分別為輸入視圖、模式視圖、總覽視圖、子圖視圖以及屬性視圖.在輸入視圖中，用戶可以輸入希望查詢的節(jié)點(diǎn)以及用來(lái)約束的短文本；在模式視圖中，用戶可以選擇其感興趣的關(guān)系來(lái)構(gòu)建查詢模式；在總覽視圖中，用戶可以觀察到查詢結(jié)果子圖的分布特征；在子圖視圖中，用戶可以觀察到節(jié)點(diǎn)的連接關(guān)系及其細(xì)節(jié)信息；在屬性視圖中，用戶可以觀察到節(jié)點(diǎn)的屬性信息.

圖1 可視分析系統(tǒng)組成Fig.1 Composition of the visual analysis system

4 結(jié)合短文本的圖查詢實(shí)現(xiàn)

本節(jié)介紹如何結(jié)合短文本生成元路徑以及其重要度.進(jìn)一步，本文結(jié)合多條元路徑進(jìn)行查詢并對(duì)查詢結(jié)果進(jìn)行挖掘.

4.1 元路徑及重要度生成

兩個(gè)節(jié)點(diǎn)間存在多條元路徑，這些元路徑的語(yǔ)義以及重要度受到多種因素的影響.下面介紹如何結(jié)合多方面因素生成元路徑并計(jì)算重要度.

4.1.1 元路徑及其重要度的定義

根據(jù)Zhu等[2]的研究，元路徑的重要度受到長(zhǎng)度、路徑實(shí)例數(shù)量和路徑的稀有度的約束.因此，本文根據(jù)這3項(xiàng)約束，將連接給定節(jié)點(diǎn)對(duì)〈s，t〉的元路徑P的重要度Is，t(P)計(jì)算函數(shù)定為：

Is，t(P)=Ss，t(P)×Rs，t(P)×fPenalty(|P|) (P∈Ps→t)

(1)

其中，Ps→t是連接節(jié)點(diǎn)s和t的元路徑集合，元路徑P是該集合中的一個(gè)元素.fPenalty(|P|)表示元路徑P的長(zhǎng)度衰減函數(shù)，Rs，t(P)表示的是元路徑P的稀有程度，Ss，t(P)則是一個(gè)元路徑重要度支持函數(shù).

本文在構(gòu)建元路徑重要度支持函數(shù)Ss，t(P)時(shí)結(jié)合了電影節(jié)點(diǎn)的文本屬性.元路徑P中的電影節(jié)點(diǎn)包含了電影的實(shí)例，本文通過(guò)計(jì)算用戶輸入的短文本與電影實(shí)例的文本簡(jiǎn)介的相似度來(lái)對(duì)該重要度支持函數(shù)進(jìn)行約束.

首先分別將用戶輸入的短文本約束以及電影的文本簡(jiǎn)介計(jì)算成向量，然后以向量相乘的形式得到兩者的相似度，最后根據(jù)相似度排名篩選出受到短文本約束的電影節(jié)點(diǎn).針對(duì)輸入的短文本查詢，使用結(jié)巴分詞算法對(duì)短文本進(jìn)行分詞，并使用定向Skip-Gram模型(directional skip-gram，DSG)[25]計(jì)算出每個(gè)詞的向量表示.之后將所有詞向量的平均值作為短文本的句向量，其計(jì)算公式為：

(2)

其中，Vi為短文本分詞后的其中一個(gè)詞向量，VQ為短文本的句向量，n為短文本分詞后的詞數(shù)量.

電影節(jié)點(diǎn)的文本簡(jiǎn)介記作T，經(jīng)過(guò)結(jié)巴分詞后可以得到簡(jiǎn)介的詞序列，接著為每個(gè)詞計(jì)算其TF-IDF值，作為該詞的權(quán)重值.然后使用DSG模型計(jì)算出沒(méi)個(gè)詞的到詞向量.最后將每個(gè)詞向量與其相應(yīng)的TF-IDF值加權(quán)求和取平均得到文本簡(jiǎn)介的句向量，其計(jì)算公式為：

(3)

其中VTj是文本簡(jiǎn)介分詞后的其中一個(gè)詞向量，wj是當(dāng)前詞對(duì)應(yīng)的TF-IDF值，VT是文本簡(jiǎn)介的句向量，m是文本簡(jiǎn)介分詞后的詞數(shù)量.

在經(jīng)過(guò)以上計(jì)算得到查詢的短文本和電影簡(jiǎn)介的句向量后，計(jì)算兩段文本的相似性，公式為：

(4)

元路徑的重要度支持函數(shù)定義為：

Ss，t(P)=fstrength(P)×fMNIs(P)

(5)

(6)

其中pA為節(jié)點(diǎn)A的實(shí)例集合，是Vu是A中每個(gè)電影節(jié)點(diǎn)實(shí)例的文本向量，VQ是查詢輸入的短文本向量.當(dāng)A為電影節(jié)點(diǎn)時(shí)，本文基于A中所有實(shí)例與用戶輸入的短文本的相似性來(lái)計(jì)算強(qiáng)度權(quán)值，若兩個(gè)文本向量越相似，fsim的值就會(huì)越小，隨之fstrength的值就會(huì)越大，最終會(huì)作用到元路徑重要度支持函數(shù)上，Ss，t(P)的值也就越大.當(dāng)A為影人節(jié)點(diǎn)時(shí)，本文通過(guò)A的出/入度的最小值的倒數(shù)來(lái)計(jì)算fstrength.在Zhu等[2]的研究中，fstrength僅由節(jié)點(diǎn)A出/入度的最小值來(lái)計(jì)算，該方法只能基于元路徑挖掘異構(gòu)網(wǎng)絡(luò)的結(jié)構(gòu)信息，無(wú)法引入節(jié)點(diǎn)的文本屬性，而本文的方法能夠同時(shí)保留網(wǎng)絡(luò)的結(jié)構(gòu)信息和節(jié)點(diǎn)的語(yǔ)義信息.

4.1.2 元路徑的生成過(guò)程

本文通過(guò)一種基于貪婪樹的數(shù)據(jù)結(jié)構(gòu)來(lái)生成連接輸入節(jié)點(diǎn)對(duì)的元路徑，總共分為3個(gè)階段.第1個(gè)階段，針對(duì)用戶輸入的節(jié)點(diǎn)對(duì)和短文本約束，系統(tǒng)會(huì)生成一棵貪婪樹.以輸入節(jié)點(diǎn)對(duì)“張藝謀”和“鞏俐”為例，圖2給出了貪婪樹的生成過(guò)程，其中貪婪樹中對(duì)象節(jié)點(diǎn)的結(jié)構(gòu)如圖2左上角所示.一個(gè)貪婪樹節(jié)點(diǎn)包含了兩個(gè)信息，一是在路徑擴(kuò)展過(guò)程中所生成的以鍵值對(duì)(Key-Value)的形式儲(chǔ)存的節(jié)點(diǎn)，二是用來(lái)表示當(dāng)前的貪婪樹節(jié)點(diǎn)能否繼續(xù)向下擴(kuò)展的“True/False”標(biāo)記——“True”還能繼續(xù)擴(kuò)展；“False”則表示不能，此時(shí)的節(jié)點(diǎn)可能已經(jīng)達(dá)到了元路徑的最大長(zhǎng)度也可能是元路徑的終點(diǎn)(目標(biāo)節(jié)點(diǎn)出現(xiàn)在Value中).本文將異構(gòu)信息網(wǎng)絡(luò)中的邊類型作為連接貪婪樹節(jié)點(diǎn)的邊.圖中Value列表中存儲(chǔ)的是當(dāng)前節(jié)點(diǎn)key根據(jù)相應(yīng)的邊可達(dá)的節(jié)點(diǎn).

第2個(gè)階段對(duì)第1階段中生成的貪婪樹進(jìn)行遍歷從而得到一系列由節(jié)點(diǎn)ID組成的路徑；然后從遍歷得到的路徑中根據(jù)邊來(lái)推導(dǎo)出組成路徑的節(jié)點(diǎn)類型，舉例來(lái)說(shuō)，如圖2中的根節(jié)點(diǎn)通過(guò)邊“Direct_in”連接到其子節(jié)點(diǎn)，則可推斷出根節(jié)點(diǎn)的類型為影人，子節(jié)點(diǎn)的類型為導(dǎo)演；最后將節(jié)點(diǎn)的類型連接成元路徑，在此階段中，會(huì)有多條不同的元路徑被生成.第3個(gè)階段統(tǒng)計(jì)貪婪樹中每個(gè)節(jié)點(diǎn)所含的實(shí)例節(jié)點(diǎn)數(shù)量，從而得到用來(lái)計(jì)算元路徑重要度的各種參數(shù).

圖2 貪婪樹結(jié)構(gòu)Fig.2 Greedy tree structure

4.2 多條元路徑結(jié)合的查詢結(jié)果生成

本文將圖查詢的結(jié)果稱為實(shí)例節(jié)點(diǎn)對(duì)，該節(jié)點(diǎn)對(duì)之間的語(yǔ)義與輸入的節(jié)點(diǎn)對(duì)之間的語(yǔ)義相同，其語(yǔ)義由多條元路徑組合而成，且受到輸入的短文本的約束.同時(shí)本文將節(jié)點(diǎn)對(duì)之間的連接關(guān)系符合某條元路徑的程度定義為節(jié)點(diǎn)對(duì)在該條元路徑上的相似度，通過(guò)搜索在每條元路徑上都有較高相似度的節(jié)點(diǎn)對(duì)，來(lái)得到符合要求的查詢結(jié)果.節(jié)點(diǎn)對(duì)根據(jù)不同元路徑的相似度計(jì)算公式為：

(7)

其中，ρei(vi，Ci+1)表示類型為Ci+1，通過(guò)邊ei連接到節(jié)點(diǎn)vi

1http：//39.105.145.46：8000/video/

的節(jié)點(diǎn)x的集合.Pi，n表示元路徑中從節(jié)點(diǎn)Ci到Cn的子序列.α為固定參數(shù)，設(shè)置為0.5.當(dāng)節(jié)點(diǎn)x的類型Ci+1為電影時(shí)，使用電影文本簡(jiǎn)介和查詢短文本的相似度和∑fsim(Vu，VQ)來(lái)替代公式(7)中的|ρei(vi，Ci+1)|.

然后，本文使用一個(gè)線性聚合函數(shù)計(jì)算節(jié)點(diǎn)對(duì)s和t之間的相似度σ(s，t|P)，將每條元路徑相應(yīng)的重要度作為相似度的權(quán)重，聚合函數(shù)為：

(8)

其中，Ij是通過(guò)公式(1)計(jì)算出的元路徑Pj的重要度.

最后本文為每條所用到的元路徑，針對(duì)每個(gè)影人節(jié)點(diǎn)計(jì)算一個(gè)相似度矩陣，用來(lái)表示兩位影人之間的關(guān)系符合該元路徑程度.元路徑P的相似性矩陣Sp中每個(gè)元素的計(jì)算公式為：

(9)

每條元路徑在第1次被生成時(shí)，就構(gòu)建好與其對(duì)應(yīng)的相似度矩陣.通過(guò)在每條元路徑的相似度矩陣搜索非0的位置及其相應(yīng)的值，就能很方便地找到在該元路徑上相似的節(jié)點(diǎn)對(duì)及其相似度.

4.3 查詢結(jié)果的特征提取和表示

本文基于查詢結(jié)果的拓?fù)涮卣魈崛∶總€(gè)結(jié)果子圖的特征向量，將其降維到2維后進(jìn)行聚類操作來(lái)得到每個(gè)子圖的特征分布.該過(guò)程可以被分為以下4個(gè)步驟：

步驟1.提取子圖的拓?fù)涮卣?假設(shè)通過(guò)結(jié)合語(yǔ)義與多條元路徑查詢后得到了一系列節(jié)點(diǎn)對(duì)，每個(gè)節(jié)點(diǎn)對(duì)與連接它們的每條元路徑形成一個(gè)結(jié)果子圖，本文針對(duì)結(jié)果子圖提取以下3個(gè)特征(所需的各個(gè)參數(shù)在生成貪婪樹的時(shí)候統(tǒng)計(jì)得到)：

1)節(jié)點(diǎn)出入度比值：該比值表示的是在當(dāng)前集合中，能沿著元路徑到達(dá)目標(biāo)節(jié)點(diǎn)的成員所占的比例.節(jié)點(diǎn)ni的入度記為In(ni)，出度記為Out(ni)，出入度比值計(jì)算公式則為:

(10)

2)平均實(shí)例數(shù)：一條長(zhǎng)度為s的元路徑除去頭尾后的序列記為{n2，…，ni，…，ns-1}，序列上第i個(gè)節(jié)點(diǎn)的實(shí)例集合為ni，平均實(shí)例數(shù)的計(jì)算公式為:

(11)

3)與源/目標(biāo)節(jié)點(diǎn)有著相同類型的節(jié)點(diǎn)數(shù)量：本文通過(guò)這兩個(gè)特征來(lái)分別表示結(jié)果子圖所包含的節(jié)點(diǎn)中與源/目標(biāo)節(jié)點(diǎn)相似的個(gè)數(shù).

步驟2.特征的向量化.針對(duì)每個(gè)查詢得到的節(jié)點(diǎn)對(duì)，將其每條元路徑上的子圖特征以向量的形式記錄下來(lái)，然后根據(jù)各條元路徑的重要度對(duì)這些向量加權(quán)求和，最終得到了每個(gè)節(jié)點(diǎn)對(duì)所形成的結(jié)果子圖的特征向量.

步驟3.降維.將每個(gè)查詢結(jié)果子圖的特征向量降維到2維以便于可視化.介于降維的時(shí)效性，本文選擇主成分分析(principal component analysis，PCA)進(jìn)行降維.

步驟4.聚類.本文使用速度較快的k-means方法對(duì)降維結(jié)果實(shí)行聚類操作.通過(guò)反復(fù)的實(shí)驗(yàn)本文發(fā)現(xiàn)，降維后的結(jié)果子圖形成的聚簇個(gè)數(shù)通常元路徑數(shù)量多1個(gè)，所以本文將k值定為元路徑的數(shù)量+1.

5 可視化設(shè)計(jì)與實(shí)現(xiàn)

本節(jié)介紹可視化系統(tǒng)HINQVis的設(shè)計(jì)與實(shí)現(xiàn)，為了更好的展示，本文在網(wǎng)址1上發(fā)布了一個(gè)介紹視頻來(lái)對(duì)系統(tǒng)的使用進(jìn)行說(shuō)明.

5.1 可視化系統(tǒng)的設(shè)計(jì)目標(biāo)

設(shè)計(jì)目標(biāo)1.便于操作的輸入界面.為了便于用戶操作，系統(tǒng)的輸入不能使用過(guò)于復(fù)雜圖查詢語(yǔ)言，而是要用簡(jiǎn)單的自然語(yǔ)言作為輸入.系統(tǒng)的輸入應(yīng)該僅包含必要的查詢信息，即源/目標(biāo)節(jié)點(diǎn)以及短文本約束.所以系統(tǒng)需要一個(gè)簡(jiǎn)潔且完整輸入界面以接收必要的信息.

設(shè)計(jì)目標(biāo)2.關(guān)系模式可視化.系統(tǒng)將元路徑作為關(guān)系模式，需要將所有匹配查詢條件的元路徑及其相應(yīng)的重要度展示出來(lái).同時(shí)為了讓用戶自行構(gòu)建想要的關(guān)系模式，系統(tǒng)還需要向用戶提供一定的交互功能.

設(shè)計(jì)目標(biāo)3.查詢結(jié)果總覽.根據(jù)“Overview first，zoom and filter，then details-on-demand”的設(shè)計(jì)準(zhǔn)則，系統(tǒng)應(yīng)該向用戶提供一種自上而下的方式方式來(lái)探索查詢得到的結(jié)果.所以系統(tǒng)需要先向用戶呈現(xiàn)一個(gè)總覽視圖，再讓用戶根據(jù)這個(gè)視圖來(lái)進(jìn)行交互式探索.

設(shè)計(jì)目標(biāo)4.查詢結(jié)果細(xì)節(jié)特征可視化.查詢得到的結(jié)果子圖包含豐富的細(xì)節(jié)信息，包括拓?fù)浣Y(jié)構(gòu)特征與語(yǔ)義特征，因此系統(tǒng)需要針對(duì)兩種細(xì)節(jié)分別向用戶提供不同的視圖來(lái)展示與分析.

5.2 可視化系統(tǒng)的設(shè)計(jì)

圖3展示了HINQVis系統(tǒng)的界面，本文將在此對(duì)系統(tǒng)的各個(gè)視圖進(jìn)行詳細(xì)的介紹.

在圖3(a)是系統(tǒng)的輸入視圖，該視圖能夠讓用戶以自然語(yǔ)言的方式輸入查詢節(jié)點(diǎn)對(duì)和短文本.系統(tǒng)要求必須輸入短文本對(duì)查詢結(jié)果進(jìn)行約束，但是對(duì)于輸入的節(jié)點(diǎn)，系統(tǒng)能夠支持“完整輸入源/目標(biāo)節(jié)點(diǎn)”、“僅輸入源節(jié)點(diǎn)”與“僅輸入目標(biāo)節(jié)點(diǎn)”3種查詢模式.

圖3(b)是系統(tǒng)的模式視圖.元路徑能夠表達(dá)節(jié)點(diǎn)間的連接模式，同時(shí)它也是一種圖結(jié)構(gòu)的數(shù)據(jù)，因此本文使用節(jié)點(diǎn)鏈接圖進(jìn)行可視化以更好地表達(dá)圖數(shù)據(jù).進(jìn)一步，本文將每條元路徑的重要度通過(guò)其右側(cè)矩形的長(zhǎng)度來(lái)表示，以便用戶對(duì)不同元路徑間的重要度進(jìn)行對(duì)比.用戶還可以勾選多條元路徑對(duì)其進(jìn)行組合，以得到自己想要的節(jié)點(diǎn)連接模式.

在圖3(c)是系統(tǒng)的總覽視圖.查詢得到的結(jié)果子圖在被提取特征后，在總覽視圖中以散點(diǎn)圖的形式被展示出來(lái).系統(tǒng)通過(guò)聚類算法將散點(diǎn)圖分割成不同的集群，并且使用不同的顏色對(duì)不同的集群進(jìn)行編碼，使用戶能夠直觀地看出不同集群的分布.

圖3(d)是在總覽視圖中選擇某一集群后，該集群在指定元路徑上的子圖視圖.本文使用?；鶊D來(lái)可視化結(jié)果子圖的拓?fù)涮卣鳎粤鞯男问綄⒉樵兊玫降慕Y(jié)果子圖清晰地呈現(xiàn)給用戶.

圖3 本文系統(tǒng)界面Fig.3 System interface

本文在圖4中給出了3種不同查詢模式下對(duì)應(yīng)的子圖視圖.在圖4(a)是將源/目標(biāo)節(jié)點(diǎn)完整輸入時(shí)的子圖視圖，此時(shí)查詢得到的所有結(jié)果子圖中每個(gè)子圖的首/尾節(jié)點(diǎn)與用戶輸入的源/目標(biāo)節(jié)點(diǎn)的連接關(guān)系是相同的.在圖4(b)是只輸入源節(jié)點(diǎn)時(shí)的子圖視圖，此時(shí)查詢得到的結(jié)果子圖的首節(jié)點(diǎn)固定為輸入的源節(jié)點(diǎn)，尾結(jié)點(diǎn)與首節(jié)點(diǎn)的連接關(guān)系符合用戶在模式視圖中構(gòu)建的元路徑模式.在圖4(c)是只輸入目+標(biāo)節(jié)點(diǎn)時(shí)的子圖視圖，此時(shí)查詢得到的結(jié)果子圖的尾結(jié)點(diǎn)固定為輸入的目標(biāo)節(jié)點(diǎn)，首節(jié)點(diǎn)與尾結(jié)點(diǎn)的連接關(guān)系符合用戶構(gòu)建的元路徑模式.視圖上方的按鈕可以將子圖視圖轉(zhuǎn)換成與按鈕相對(duì)應(yīng)的元路徑的形式顯示.

圖4 不同輸入形式的子圖可視化Fig.4 Subgraph visualization of different input forms

如圖3(e)和圖3(f)所示，屬性視圖展示了查詢得到的電影節(jié)點(diǎn)一些關(guān)鍵屬性信息，這些信息能夠體現(xiàn)出查詢結(jié)果符合用戶輸入的短文本約束.首先本文通過(guò)詞云來(lái)對(duì)查詢結(jié)果中電影節(jié)點(diǎn)的類別信息進(jìn)行展示，同時(shí)用描述類別的詞的大小來(lái)編碼屬于此類別的電影數(shù)量，用戶可以直觀地看出不同集群中的電影在類別上的區(qū)別.然后，本文提取電影簡(jiǎn)介的關(guān)鍵詞，再次使用詞云對(duì)其進(jìn)行可視化展示，并且將詞的大小設(shè)計(jì)為關(guān)鍵詞與用戶輸入的短文本的相似性，通過(guò)這種方法來(lái)呈現(xiàn)查詢得到的節(jié)點(diǎn)對(duì)受短文本語(yǔ)義約束程度.最后本文統(tǒng)計(jì)當(dāng)查詢結(jié)果子圖中所有電影的上映年份，以及在每個(gè)年份中每位影人參與的電影數(shù)量，通過(guò)像素視圖的形式對(duì)這些統(tǒng)計(jì)信息進(jìn)行展示，其中每一行對(duì)應(yīng)了一個(gè)影人，每一列對(duì)應(yīng)了一個(gè)年份，每個(gè)像素塊的顏色深淺就表示了某位的影人在某年中參與的電影數(shù)量.圖3(f)展示了查詢結(jié)果中的電影列表，包含了電影的名稱及簡(jiǎn)介.列表中電影的排列順序是由電影與查詢輸入的短文本的相似度來(lái)決定，相似度越高，電影就越靠上.

6 系統(tǒng)評(píng)估

6.1 元路徑有效性驗(yàn)證

實(shí)驗(yàn)通過(guò)將本文方法SMNIs(short-text strengthened-minimum instances，MNIs)與增強(qiáng)最小實(shí)例數(shù)(strengthened-minimum instances，MNIs)[2]、k最短元路徑(k-shortest meta paths，SMP)[26]、結(jié)合路徑長(zhǎng)度與重要度的方法(strength-and-length-based versioned，SLV)SLV1[27]和SLV2[28]方法進(jìn)行對(duì)比，來(lái)驗(yàn)證結(jié)合短文本生成的元路徑的有效性.

實(shí)驗(yàn)使用了從DBLP數(shù)據(jù)集中抽取的子集.該數(shù)據(jù)集從DBLP數(shù)據(jù)集中挑選了4個(gè)領(lǐng)域的20個(gè)最具代表性的會(huì)議，然后提取其中的相關(guān)論文與作者，其統(tǒng)計(jì)數(shù)據(jù)如表1所示，其中還包含了332338條邊.該數(shù)據(jù)集根據(jù)會(huì)議將作者的研究領(lǐng)域劃分為數(shù)據(jù)庫(kù)，數(shù)據(jù)挖掘，機(jī)器學(xué)習(xí)和信息檢索4個(gè)領(lǐng)域.在該數(shù)據(jù)集中，有4236位作者被標(biāo)記了其研究領(lǐng)域.本文的實(shí)驗(yàn)將每篇論文的標(biāo)題視為短文本數(shù)據(jù)，在提取標(biāo)題中的關(guān)鍵詞之后與查詢輸入的短文本進(jìn)行匹配.

表1 實(shí)驗(yàn)數(shù)據(jù)集Table 1 Experimental data set

首先選擇兩位作者，分別是Philip S.Yu和Jiawei Han，其中Philip S.Yu的研究領(lǐng)域?yàn)閿?shù)據(jù)庫(kù)和數(shù)據(jù)挖掘，Jiawei Han的研究領(lǐng)域?yàn)閿?shù)據(jù)挖掘.實(shí)驗(yàn)希望查詢得到的作者節(jié)點(diǎn)對(duì)能夠被輸入的短文本所約束，使兩者的研究領(lǐng)域都包含“數(shù)據(jù)挖掘”.

查詢輸入的節(jié)點(diǎn)對(duì)為，輸入的短文本為“pattern extraction model”.系統(tǒng)根據(jù)實(shí)驗(yàn)的輸入而生成了如表2所示的元路徑與其相應(yīng)的重要度.系統(tǒng)一共生成了長(zhǎng)度在5以內(nèi)的4條元路徑，其中元路徑“A—P—A”重要度在所有方法中都是最高的，其包含的語(yǔ)義是作者的合作關(guān)系；重要度排名第2的則是元路徑“A—P—C—P—A”，表示的是兩位作者曾在同一會(huì)議上發(fā)表過(guò)論文；剩下的2條元路徑分別表示兩位作者的論文有著相同的術(shù)語(yǔ)、兩位作者都與同一位作者有過(guò)合作.在實(shí)驗(yàn)使用的所有方法中，只有本文提出的方法在計(jì)算元路徑重要度時(shí)利用了輸入的短文本進(jìn)行約束.

表2 節(jié)點(diǎn)對(duì)的元路徑及重要度Table 2 Meta paths and importance of

然后本文根據(jù)各種方法計(jì)算得到的元路徑重要度進(jìn)行查詢得到5組實(shí)驗(yàn)結(jié)果，將每個(gè)方法生成的節(jié)點(diǎn)對(duì)集合記為{〈s1，t1〉，…，〈si，ti〉，…，〈sn，tn〉}，并對(duì)每個(gè)節(jié)點(diǎn)對(duì)使用公式(8)計(jì)算其相似度，其中〈si，ti〉表示查詢得到的某一個(gè)作者節(jié)點(diǎn)對(duì).當(dāng)si的研究領(lǐng)域與ti的研究領(lǐng)域相同，且都為“數(shù)據(jù)挖掘”時(shí)，可以看作查詢輸入的短文本對(duì)該節(jié)點(diǎn)對(duì)進(jìn)行了約束.本文將查詢準(zhǔn)確率定為節(jié)點(diǎn)對(duì)受短文本約束的比例，其公式為：

(12)

(13)

其中，d表示作者的領(lǐng)域，n表示查詢得到的相似度排名靠前的n對(duì)節(jié)點(diǎn)對(duì).

圖5展示了取不同對(duì)數(shù)的節(jié)點(diǎn)對(duì)后統(tǒng)計(jì)查詢準(zhǔn)確率的結(jié)果.橫坐標(biāo)表示的是實(shí)驗(yàn)提取的n對(duì)查詢得到的節(jié)點(diǎn)對(duì)，縱坐標(biāo)則表示相應(yīng)的查詢準(zhǔn)確率，即在所取的節(jié)點(diǎn)對(duì)中被短文本約束了的節(jié)點(diǎn)對(duì)的比例.從圖中可以看出，使用本文提出的方法設(shè)定元路徑重要度而查詢得到的節(jié)點(diǎn)對(duì)能夠更好地受到短文本語(yǔ)義的約束，特別是當(dāng)節(jié)點(diǎn)對(duì)的相似性排名較高時(shí)，該方法得到的查詢準(zhǔn)確率達(dá)到其他方法的近2倍.

圖5 實(shí)驗(yàn)結(jié)果統(tǒng)計(jì)Fig.5 Statistics of experimental results

6.2 案例分析

本文通過(guò)一個(gè)案例來(lái)展示HINQVis系統(tǒng)的使用方法，并對(duì)查詢結(jié)果進(jìn)行挖掘與分析.系統(tǒng)使用了豆瓣電影數(shù)據(jù)集，且能夠?qū)崟r(shí)地與用戶進(jìn)行交互.該數(shù)據(jù)集含有6794個(gè)影人節(jié)點(diǎn)和40661個(gè)電影節(jié)點(diǎn)，以及193194條電影與影人的關(guān)系.

用戶首先需要在輸入視圖輸入其想要查詢的節(jié)點(diǎn)以及短文本約束.以僅輸入源節(jié)點(diǎn)的查詢模式為例，用戶在輸入視圖的源節(jié)點(diǎn)方框處填入“鞏俐”，在短文本方框處填入“反抗封建社會(huì)的壓迫”.用戶在完成輸入之后點(diǎn)擊“查詢”鍵，系統(tǒng)便會(huì)在模式視圖中生成了如圖6所示的元路徑及其相應(yīng)的重要度.用戶通過(guò)觀察模式視圖可以得知，“鞏俐”在作為源節(jié)點(diǎn)時(shí)，她的身份只有“演員”，且在該視圖中的長(zhǎng)度為3的元路徑的重要度比長(zhǎng)度為5的元路徑都高.為了探索“鞏俐”與“導(dǎo)演”類型節(jié)點(diǎn)的合作關(guān)系，選擇了在相同長(zhǎng)度中重要度最高的2條元路徑“演員—電影—導(dǎo)演”和“演員—電影—導(dǎo)演—電影—導(dǎo)演”作為模式用于之后的查詢.

圖6 顯示元路徑和重要度的模式視圖Fig.6 Pattern view which shows meta-paths with importance

圖7 查詢結(jié)果特征總覽視圖Fig.7 Feature summary view of the query results

用戶點(diǎn)擊提交按鈕后，系統(tǒng)生成了如圖7所示的查詢結(jié)果總覽視圖.查詢得到的結(jié)果被分成了3類，視圖中的每個(gè)散點(diǎn)表示1個(gè)結(jié)果子圖.用戶需要在總覽視圖選擇一個(gè)集群，便可觀察該集群的結(jié)果子圖與屬性信息.圖8分別展示了3個(gè)集群的子圖視圖，用戶通過(guò)觀察子圖視圖的詳細(xì)內(nèi)容能夠了解3個(gè)集群之間的差異：集群a中的電影節(jié)點(diǎn)大部分都是較為經(jīng)典且評(píng)價(jià)較高的電影；在集群b和c中，與“鞏俐”節(jié)點(diǎn)有著合作關(guān)系的“導(dǎo)演”節(jié)點(diǎn)都是香港的導(dǎo)演，且其電影節(jié)點(diǎn)的內(nèi)容與集群a中的電影相差較大.這證明了本文在提取和表示查詢結(jié)果特征上的有效性.

圖8 不同類型集群的子圖視圖對(duì)比Fig.8 Comparison of subgraph views of different clusters

最后，觀察如圖9所示的屬性視圖.圖9分別展示了3個(gè)不同集群的屬性視圖.通過(guò)對(duì)比可以發(fā)現(xiàn)，在第1行的類別詞云視圖中，集群a的“劇情”詞云最大，表示其電影幾乎都含有“劇情”的類別；集群b的詞云大小分布較為平均，說(shuō)明其電影的類別分布較為分散；集群c中的詞云中“喜劇”與“奇幻”大于其他詞，其中“喜劇”更加顯著，表明其電影的類別以“喜劇”為主.用戶能夠從3個(gè)集群的詞云中看出明顯的不同，這進(jìn)一步說(shuō)明了本文在提取查詢結(jié)果特征上的有效性.屬性視圖的第2行展示的是關(guān)鍵詞詞云，用戶能夠從中看出詞云的內(nèi)容與其輸入的短文本約束存在著聯(lián)系，這能夠證明本文提出的方法在利用短文本語(yǔ)義計(jì)算元路徑重要度后對(duì)查詢結(jié)果有著較好的約束效果.屬性視圖的最后部分是一個(gè)像素圖，統(tǒng)計(jì)了電影的年份屬性，用戶對(duì)其進(jìn)行分析后可以發(fā)現(xiàn)3個(gè)集群在年份上的特征，集群a中包含了最多的“鞏俐”參演的電影，且其時(shí)間跨度在3個(gè)集群中是最大的，從1987年至2000年都有分布，而在另外兩個(gè)集群中，電影的上映時(shí)間都要早于1995年.

圖9 3個(gè)集群的屬性視圖對(duì)比Fig.9 Comparison of attribute views of 3 clusters

7 結(jié) 語(yǔ)

本文提出了一種結(jié)合短文本的圖查詢方法，并在此基礎(chǔ)上基于豆瓣電影數(shù)據(jù)設(shè)計(jì)并實(shí)現(xiàn)了一個(gè)圖查詢驅(qū)動(dòng)的可視分析系統(tǒng)HINQVis.系統(tǒng)利用元路徑表示節(jié)點(diǎn)間的關(guān)系模式，并結(jié)合節(jié)點(diǎn)的短文本屬性計(jì)算不同元路徑的重要度用于查詢.針對(duì)結(jié)果子圖的拓?fù)浣Y(jié)構(gòu)特征和語(yǔ)義特征進(jìn)行可視分析.最后使用DBLP數(shù)據(jù)集的子集進(jìn)行了驗(yàn)證實(shí)驗(yàn)，并使用一個(gè)案例介紹如何對(duì)查詢結(jié)果進(jìn)行可視分析.

未來(lái)的工作可以通過(guò)神經(jīng)網(wǎng)絡(luò)的方式學(xué)習(xí)元路徑特征，利用注意力機(jī)制來(lái)得到元路徑的重要度.同時(shí)在結(jié)合短文本語(yǔ)義進(jìn)行查詢時(shí)，還可以計(jì)算每個(gè)詞的重要度，結(jié)合每個(gè)詞不同的重要度來(lái)對(duì)結(jié)果進(jìn)行語(yǔ)義匹配.研究短文本中每個(gè)詞分別對(duì)短文本語(yǔ)義的重要度也是一個(gè)有價(jià)值的方向.