多元圖融合的異構(gòu)信息網(wǎng)嵌入

吳 瑤 申德榮 寇 月 聶鐵錚 于 戈

(東北大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院 沈陽(yáng) 110169)18642113630@163.com)

網(wǎng)絡(luò)表示學(xué)習(xí)是將網(wǎng)絡(luò)嵌入到低維空間中，可以將網(wǎng)絡(luò)中的節(jié)點(diǎn)、邊或圖表示成向量形式.這種表示形式能夠更多保留節(jié)點(diǎn)的網(wǎng)絡(luò)結(jié)構(gòu)或者語(yǔ)義信息，因此可以將該向量表示作為特征應(yīng)用到各種數(shù)據(jù)挖掘任務(wù)當(dāng)中.

當(dāng)前已有許多針對(duì)同構(gòu)網(wǎng)絡(luò)嵌入的研究成果[1-3]和部分面向異構(gòu)網(wǎng)絡(luò)嵌入的研究.利用元路徑進(jìn)行網(wǎng)絡(luò)嵌入是提取異構(gòu)網(wǎng)絡(luò)特征的常用方法，但是元路徑結(jié)構(gòu)簡(jiǎn)單，可能會(huì)丟失一些重要的信息.元圖可以獲取到較元路徑更復(fù)雜的信息，同時(shí)考慮節(jié)點(diǎn)間的元圖和元路徑會(huì)得到更好的嵌入結(jié)果[4].然而，已有方法大多由專家指定元路徑和元圖，類型較單一，不適用于大型復(fù)雜的網(wǎng)絡(luò)，而且在指定元圖和元路徑時(shí)未考慮同類型網(wǎng)絡(luò)各自的獨(dú)特性，影響節(jié)點(diǎn)嵌入準(zhǔn)確性.雖然已提出了一些針對(duì)異構(gòu)網(wǎng)絡(luò)元路徑的發(fā)現(xiàn)算法，但是還沒有見到關(guān)于元圖的發(fā)現(xiàn)方法.部分研究利用頻繁子圖挖掘算法找到當(dāng)前異構(gòu)網(wǎng)絡(luò)的頻繁子圖，將其作為元圖，但是因?yàn)轭l繁子圖算法生成的元圖數(shù)量較大，并且在結(jié)構(gòu)上可能存在很大程度的相似性，導(dǎo)致后續(xù)基于元圖的相似度計(jì)算復(fù)雜度過高.

鑒于元路徑是一種特殊形式的元圖，本文提出了一種元圖發(fā)現(xiàn)算法.在各種復(fù)雜網(wǎng)絡(luò)的數(shù)據(jù)挖掘應(yīng)用場(chǎng)景下，該算法可以發(fā)現(xiàn)網(wǎng)絡(luò)中的適量關(guān)鍵元圖，這些元圖可以提取原網(wǎng)絡(luò)的各類重要信息，減少網(wǎng)絡(luò)嵌入的信息損失.基于元圖發(fā)現(xiàn)算法，本文提出一種多元圖融合的異構(gòu)網(wǎng)絡(luò)嵌入方法，該方法利用自動(dòng)編碼器模型，進(jìn)一步自適應(yīng)地選擇關(guān)鍵元結(jié)構(gòu)并學(xué)習(xí)權(quán)重值，不僅能夠更好地獲取網(wǎng)絡(luò)的結(jié)構(gòu)和語(yǔ)義特征，還可能有效降低人為因素對(duì)嵌入結(jié)果的影響.

本文的主要貢獻(xiàn)有4個(gè)方面：

1) 提出了一種元圖發(fā)現(xiàn)算法，該算法可以挖掘代表當(dāng)前網(wǎng)絡(luò)結(jié)構(gòu)和語(yǔ)義特征的重要元圖，有助于提升后續(xù)嵌入的準(zhǔn)確性；

2) 提出了一種基于元圖的節(jié)點(diǎn)相似度度量方法，相比于已有的計(jì)算方法，更具有通用性；

3) 利用神經(jīng)網(wǎng)絡(luò)嵌入節(jié)點(diǎn)的元圖特征,通過原始特征的降維和融合，可以根據(jù)當(dāng)前網(wǎng)絡(luò)的特性計(jì)算不同元圖的重要性，提高嵌入的準(zhǔn)確性；

4) 通過對(duì)比實(shí)驗(yàn)，證明本文提出的方法在各類下游應(yīng)用中的執(zhí)行效果要優(yōu)于其他網(wǎng)絡(luò)嵌入算法.

1 相關(guān)工作

網(wǎng)絡(luò)嵌入方法學(xué)習(xí)網(wǎng)絡(luò)節(jié)點(diǎn)在低維空間的潛在表示，其結(jié)果可以作為各種數(shù)據(jù)挖掘任務(wù)的輸入特征，例如聚類、分類、檢索、鏈路預(yù)測(cè)等，因其較好的執(zhí)行效果和在各領(lǐng)域的通用性，該方法成為近年來的研究熱點(diǎn).DeepWalk[1]是第1個(gè)提出使用語(yǔ)言模型skip-gram和無監(jiān)督方式學(xué)習(xí)節(jié)點(diǎn)表示的方法，具體來說，將單詞序列擴(kuò)展到圖，即用節(jié)點(diǎn)代替單詞，用隨機(jī)游走抽取的圖路徑作為單詞的上下文，進(jìn)而學(xué)習(xí)潛在節(jié)點(diǎn)的表示.Node2vec[2]是DeepWalk方法的擴(kuò)展，它引入偏置隨機(jī)游走生成序列，并分析了深度優(yōu)先和廣度優(yōu)先2種游走方式所保留的不同結(jié)構(gòu)信息，同時(shí)相比于DeepWalk依據(jù)權(quán)重的隨機(jī)游走，該方法則增加了權(quán)重的調(diào)整參數(shù).LINE[3]保留網(wǎng)絡(luò)節(jié)點(diǎn)的一階相似度和二階相似度信息，采用廣度優(yōu)先搜索策略生成上下文節(jié)點(diǎn)，并使用負(fù)采樣優(yōu)化skip-gram模型.

近些年，隨著應(yīng)用系統(tǒng)復(fù)雜性的提升和用戶需求的多樣性發(fā)展，簡(jiǎn)單的同構(gòu)網(wǎng)絡(luò)難以表示現(xiàn)實(shí)世界，而異構(gòu)信息網(wǎng)的異質(zhì)性恰好可以解決復(fù)雜關(guān)系的建模問題，因此針對(duì)異構(gòu)信息網(wǎng)的網(wǎng)絡(luò)嵌入方法也相繼出現(xiàn).PME[5]是一種基于度量學(xué)習(xí)的異構(gòu)信息網(wǎng)絡(luò)嵌入模型，以統(tǒng)一方式捕獲一階和二階鄰近關(guān)系，并在單獨(dú)的對(duì)象空間和關(guān)系空間中構(gòu)建對(duì)象和關(guān)系嵌入，同時(shí)提出一種損失感知自適應(yīng)采樣方法用于模型優(yōu)化.異構(gòu)信息網(wǎng)中的異質(zhì)性在引入豐富信息的同時(shí)也引入了潛在的不兼容語(yǔ)義，為了保留網(wǎng)絡(luò)嵌入中豐富但可能不兼容的信息，Shi等人[6]提出了HEER算法，該算法通過將邊緣表示和異構(gòu)度量相結(jié)合，解決異構(gòu)信息網(wǎng)絡(luò)的綜合轉(zhuǎn)錄問題.為解決網(wǎng)絡(luò)中多類型節(jié)點(diǎn)、關(guān)系的結(jié)構(gòu)信息和非結(jié)構(gòu)化屬性、文本的信息融合問題，Zhang等人[7]提出了SHNE異構(gòu)網(wǎng)絡(luò)嵌入模型，該模型通過skip-gram和深度語(yǔ)義編碼的聯(lián)合優(yōu)化，捕獲節(jié)點(diǎn)之間的異構(gòu)結(jié)構(gòu)接近度和非結(jié)構(gòu)化語(yǔ)義關(guān)系.Huang等人[8]提出一個(gè)用于大規(guī)模網(wǎng)絡(luò)異構(gòu)信息學(xué)習(xí)的通用嵌入框架，加速拓?fù)浣Y(jié)構(gòu)與節(jié)點(diǎn)屬性、二階相似性、鏈路方向性等信息的聯(lián)合學(xué)習(xí)，同時(shí)將復(fù)雜的建模和優(yōu)化過程分解為許多簡(jiǎn)單的獨(dú)立子問題，以分布式方式完成節(jié)點(diǎn)相似度的評(píng)估.

元路徑和元圖作為異構(gòu)信息網(wǎng)的不同層次的網(wǎng)絡(luò)模式，可以代表網(wǎng)絡(luò)中特定的語(yǔ)義關(guān)系，因此在大量研究中都得到了充分的應(yīng)用.TransPath[9]利用知識(shí)圖中轉(zhuǎn)換機(jī)制的概念，將元路徑視為從第一個(gè)節(jié)點(diǎn)到最后一個(gè)節(jié)點(diǎn)的轉(zhuǎn)換操作.此外還提出了一種用戶引導(dǎo)的元路徑采樣策略，該策略以用戶的偏好為指導(dǎo)，可以更精確地探索路徑的語(yǔ)義，同時(shí)通過避免其他噪聲和無意義的元路徑提高了模型效率.Ji等人[10]提出了一個(gè)基于元路徑融合的關(guān)注機(jī)制模型，用于異構(gòu)信息網(wǎng)絡(luò)的嵌入.該模型首先利用元路徑從原始異構(gòu)網(wǎng)絡(luò)中抽取出多個(gè)同構(gòu)網(wǎng)絡(luò)，然后使用共同注意機(jī)制融合從多個(gè)同構(gòu)網(wǎng)絡(luò)中學(xué)習(xí)的節(jié)點(diǎn)嵌入.Sun等人[4]提出基于元圖的網(wǎng)絡(luò)嵌入模型，利用耦合張量-矩陣分解的方法獲得節(jié)點(diǎn)的聯(lián)合嵌入，即元圖和其嵌入元路徑的公共潛在特征.Zhang等人[11]引入多對(duì)齊屬性異構(gòu)網(wǎng)絡(luò)的概念建模網(wǎng)絡(luò)結(jié)構(gòu)，將社交網(wǎng)絡(luò)中的元路徑進(jìn)行分類，通過異構(gòu)鏈接和屬性信息定義了用戶間各種類型的交互關(guān)系，然后將基于元路徑的相似度作為深度自動(dòng)編碼器的輸入特征，學(xué)習(xí)用戶節(jié)點(diǎn)的低維表示.

為了將網(wǎng)絡(luò)的元路徑或者元圖特征更好地應(yīng)用到網(wǎng)絡(luò)嵌入模型當(dāng)中，少數(shù)研究集中于關(guān)鍵元路徑或元圖的發(fā)現(xiàn)和基于二者的特征度量.Huang等人[12]提出3種基于元結(jié)構(gòu)的相關(guān)性度量方法，由于這些度量的計(jì)算復(fù)雜性較高，進(jìn)一步設(shè)計(jì)一種支持以上數(shù)據(jù)結(jié)構(gòu)的度量算法.Meng等人[13]研究自動(dòng)發(fā)現(xiàn)元路徑的方法，根據(jù)用戶提供的具有較高相似度的節(jié)點(diǎn)對(duì)，生成能夠解釋節(jié)點(diǎn)對(duì)語(yǔ)義關(guān)系的元路徑集合.同時(shí)提出貪婪樹算法選擇最相關(guān)的元路徑以降低計(jì)算的時(shí)間復(fù)雜度.Fang等人[14]提出基于元圖集合的相似度，利用監(jiān)督方法自動(dòng)學(xué)習(xí)元圖集合中相似度的正確形式以適應(yīng)期望的關(guān)系類型，同時(shí)設(shè)計(jì)雙階段訓(xùn)練和基于對(duì)稱的匹配算法加速元圖匹配的過程.

2 問題定義

針對(duì)異構(gòu)信息網(wǎng)嵌入問題，我們首先給出相關(guān)定義，然后進(jìn)行問題描述.

定義1.異構(gòu)信息網(wǎng).異構(gòu)信息網(wǎng)是帶有對(duì)象類型映射函數(shù)φ:V→L和鏈接類型映射函數(shù)ψ:E→R的有向圖G=(V,E)，圖中的每個(gè)對(duì)象V屬于一種對(duì)象類型φ(V),每條邊E屬于一種鏈接類型ψ(E).

定義2.元圖[12].元圖S是定義在網(wǎng)絡(luò)模式TG=(L,R)上具有單一源節(jié)點(diǎn)nsou(入度為0)和單一目標(biāo)節(jié)點(diǎn)ntar(出度為0)的有向無環(huán)圖，可以表示為S=(N,M,nsou,ntar)，其中N是節(jié)點(diǎn)的集合，M是邊的集合.

我們研究異構(gòu)信息網(wǎng)基于元圖的節(jié)點(diǎn)嵌入方法，即給出一個(gè)異構(gòu)信息網(wǎng)絡(luò)G=(V,E)，根據(jù)生成的元圖M_G=(Vsou,Vtar,E)計(jì)算節(jié)點(diǎn)相似度s(Vsou,Vtar)作為原始特征Mij，利用神經(jīng)網(wǎng)絡(luò)模型得到所有節(jié)點(diǎn)的低維表示x1,x2,…,xn.

本文提出的多元圖融合的異構(gòu)網(wǎng)絡(luò)嵌入模型(heterogeneous network embedding model based on multiple meta-graph fusion， HE-MGF)包括元圖發(fā)現(xiàn)和基于多元圖融合的節(jié)點(diǎn)嵌入2部分.模型的基本思想如圖1所示，首先利用頻繁元圖發(fā)現(xiàn)算法得到當(dāng)前異構(gòu)信息網(wǎng)的一系列頻繁元圖；然后通過聚類算法，選擇具有代表性的元圖集合；接下來計(jì)算節(jié)點(diǎn)間基于元圖集合的相似性分?jǐn)?shù)；最后利用神經(jīng)網(wǎng)絡(luò)模型對(duì)元圖集合進(jìn)行融合嵌入.

Fig. 1 Framework of HE-MGF圖1 基于元圖的異構(gòu)信息網(wǎng)嵌入模型的框架

3 元圖發(fā)現(xiàn)

元圖代表特定的結(jié)構(gòu)和語(yǔ)義信息，不同網(wǎng)絡(luò)中不同類型元圖的重要性程度也存在一定差異.因此，需要根據(jù)特定網(wǎng)絡(luò)的特性選擇頻繁元圖集合，以涵蓋網(wǎng)絡(luò)的重要語(yǔ)義特征.所以本文提出頻繁元圖發(fā)現(xiàn)方法挖掘不同網(wǎng)絡(luò)的關(guān)鍵信息.

3.1 頻繁元圖挖掘

元圖是一種有向無環(huán)圖，具有單一起點(diǎn)和終點(diǎn)，是網(wǎng)絡(luò)中子圖的子集；而包含節(jié)點(diǎn)數(shù)量過多的元圖對(duì)計(jì)算節(jié)點(diǎn)對(duì)的相似度并無重要的作用；大多應(yīng)用場(chǎng)景要求元圖的起點(diǎn)和終點(diǎn)的類型要一致等.為此，本文利用GRAMI[16]算法，并進(jìn)行部分修正，稱為FMGM算法，該算法能更好地適用于自動(dòng)生成元圖的應(yīng)用場(chǎng)景.FMGM包括3部分：FrequentMeta-graphMining(見算法1)是算法的整體流程(其中行⑦～是FMGM增加的元圖抽取過程)，Subgraph-Extension(見算法2)為子圖擴(kuò)展過程(其中行⑤～是FMGM增加的剪枝部分)，IsFrequentCsp[16](見算法3)用于解決子圖同構(gòu)問題.

算法1.FrequentMeta-graphMining.

輸入：G=(V,E)、頻繁度閾值t；

輸出：所有頻繁度超過t的元圖集合M.

①M(fèi)，S置為空集；

② 構(gòu)建G的頻繁邊集合fedgs；

③ foreoffedgs*選擇僅包含目標(biāo)類型節(jié)點(diǎn)的頻繁邊*

④S←S∪SubgraphExtension；

⑤ removeefromGandfedgs；*從原圖和頻繁邊集合中刪除當(dāng)前邊*

⑥ end for

⑦ for eachmofS

⑧Mg←mpath(tp)；*根據(jù)設(shè)定的起點(diǎn)和重點(diǎn)類型tp，選擇當(dāng)前子圖中滿足要求的路徑*

⑨ end for

⑩ for eachmpath1,mpath2 ofMg

mpath1.tg==mpath2.tg

算法1的行①②初始化結(jié)果集，并構(gòu)建頻繁邊集合；行③～⑥選擇起始邊并執(zhí)行子圖擴(kuò)展，在此次擴(kuò)展結(jié)束后刪除當(dāng)前邊；行⑦～抽取頻繁元圖.

算法2.SubgraphExtension.

輸入：G的子圖S、元圖圖節(jié)點(diǎn)數(shù)量的最大值m、t、fedgs；

輸出：所有擴(kuò)展S的頻繁元圖M.

①M(fèi)←s，candidateset置為空；*當(dāng)前子圖放入結(jié)果集中，候選集置為空*

② foruinsandeinfedgs*針對(duì)子圖中的每個(gè)節(jié)點(diǎn)和每條頻繁邊*

③ ife可以被用于擴(kuò)展u

④ext=s+e；

⑤ if當(dāng)前子圖ext未生成過并且其節(jié)點(diǎn)量小于閾值m

⑥candidateset←ext；

⑦ end if

⑧ else ifext中的節(jié)點(diǎn)數(shù)量為m

⑨ ifextis meta-graph

⑩candidateset←ext；

算法3.IsFrequentCsp.

輸入：s，G，t；

輸出：ifs是頻繁元圖，返回true，否則返回false.

① consider theCSPofsinG；

② 應(yīng)用節(jié)點(diǎn)和邊的一致性規(guī)則，去掉矛盾組合；

③ if 任意領(lǐng)域的節(jié)點(diǎn)數(shù)量小于t

⑤ end if

⑥ for eachsol*CSP的一個(gè)解決方案*

⑦ 在對(duì)應(yīng)領(lǐng)域domains中標(biāo)記sol所有節(jié)點(diǎn)；

⑧ if所有domains至少有t個(gè)節(jié)點(diǎn)

⑨ return true；

⑩ end if

算法3的行①～⑤計(jì)算子圖的CSP，刪除不滿足頻繁度條件的子圖；行⑥～遍歷domains刪除不滿足條件的子圖.算法3中的CSP表示為三元組形式(X,D,C)，X是子圖節(jié)點(diǎn)(變量)的有序集合，D是域集合(domains)，每個(gè)X都對(duì)應(yīng)一個(gè)包含G中所有節(jié)點(diǎn)的域，C是X之間的約束條件集合CSP的一個(gè)可行的解決方案(sol)，就是一個(gè)滿足約束條件C的節(jié)點(diǎn)分配方案，即向X中的每個(gè)變量分配domains中滿足約束條件的節(jié)點(diǎn).

3.2 候選元圖選擇

由于生成的元圖數(shù)量較多，且大部分結(jié)構(gòu)相似，而元圖匹配的計(jì)算代價(jià)又非常高，所以我們提出基于k-means聚類的思想，選擇具有代表性的關(guān)鍵元圖.具體思路是將生成的頻繁元圖根據(jù)其結(jié)構(gòu)相似度聚成k個(gè)類別，每個(gè)類別再根據(jù)其組內(nèi)的結(jié)構(gòu)相關(guān)性和組間的結(jié)構(gòu)差異性，投票選擇出最能代表本類別元圖的某一個(gè)或者某幾個(gè)元圖.

首先介紹元圖相似度的計(jì)算方法，如果2個(gè)元圖共享一些公共的表示，則兩者的結(jié)構(gòu)可能是相似的，代表的語(yǔ)義關(guān)系可能也是相似的.基于最大公共子圖(MCS)計(jì)算元圖的結(jié)構(gòu)相似度是一種理想的方法，二者的MCS越大，它們的結(jié)構(gòu)相似度就越高.元圖結(jié)構(gòu)相似度的計(jì)算公式為：

(1)

因?yàn)橛?jì)算最大公共子圖是NP-Hard問題，所以本文提出一種近似的簡(jiǎn)化替代算法，每個(gè)元圖都可以表示為(x,y)T的矩陣形式，其中x=(nt1,nt2,…,ntk)，y=(et1,et2,…,etk)，ntk表示圖的節(jié)點(diǎn)類型，etk表示圖的邊類型，兩者的取值分別表示特定類型節(jié)點(diǎn)和邊的數(shù)量.因?yàn)橛嘞蚁嗨贫仍谟?jì)算文本相似性時(shí)有較好的效果，所以本部分利用余弦相似度(式(2))計(jì)算2圖的結(jié)構(gòu)相似度，利用式(3)計(jì)算類心(m_x,m_y)T：

(2)

(3)

下面簡(jiǎn)單描述元圖聚類的方法.

算法4.Meta-graphSelection.

輸入：簇?cái)?shù)目k、頻繁元圖集合D；

輸出：候選元圖集合R.

① 在D中隨機(jī)選擇k個(gè)對(duì)象構(gòu)建初始類心集合w1；

② fordofDandcofw

③Sdc=SS(d,c)；*計(jì)算d與類心的結(jié)構(gòu)相似度*

④ end for

⑤ fordofD

⑥mi←max(Sdc)；*將d歸類到相似度分?jǐn)?shù)最高的類心所在的聚類mi中*

⑦ end for

⑧ 計(jì)算新類心wt；

⑨ ifwt≠wt-1

SS(d,*)求和，作為類內(nèi)元圖相似度*

4 基于多元圖融合的網(wǎng)絡(luò)嵌入

本節(jié)利用一種適用于非對(duì)稱元圖的相似度度量方法HeteMGSim計(jì)算節(jié)點(diǎn)的相似度矩陣，并將該矩陣作為后續(xù)嵌入模型的原始特征.

4.1 基于元圖的節(jié)點(diǎn)相似度計(jì)算方法——HeteMGSim

現(xiàn)有的基于元圖的相似度計(jì)算方法，包括StructCount，SCSE[12]，GraphSim[10]這3種.這些方法都在不同方面存在缺陷，GraghSim使用的前提是元圖必須為對(duì)稱形式，StructCount沒有考慮起始節(jié)點(diǎn)的活躍度對(duì)相似度的影響程度，SCSE需要使用元結(jié)構(gòu)層的概念，但是對(duì)于非標(biāo)準(zhǔn)形式的元圖而言，很難界定節(jié)點(diǎn)所處的結(jié)構(gòu)層次.受HeteSim[17]啟發(fā)，我們提出一種適用非對(duì)稱元圖的節(jié)點(diǎn)相似度計(jì)算方法HeteMGSim，該方法的通用性要優(yōu)于以上計(jì)算方法.

HeteSim的基本思想是將查找元路徑實(shí)例問題轉(zhuǎn)化為節(jié)點(diǎn)對(duì)的隨機(jī)游走問題，并將源節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)的相似度定義為二者在特定元路徑的中點(diǎn)相遇的概率.

因?yàn)樵獔D是具有相同起始點(diǎn)的元路徑的組合，從給定的元圖中可以抽取到若干條元路徑，所以計(jì)算2點(diǎn)在不同元路徑相遇概率的乘積可以作為節(jié)點(diǎn)在元圖中的相遇概率.給定一個(gè)HIN，2點(diǎn)沿元路徑P的可達(dá)矩陣Cp為：

Cp=UA1A2×UA2A3×…×UAlAl+1,

(4)

其中，UAiAi+1是鄰接矩陣的行歸一化結(jié)果，表示Ai→Ai+1的轉(zhuǎn)移概率矩陣，同時(shí)，鄰接矩陣的按列歸一化VAiAi+1表示Ai+1→Ai的轉(zhuǎn)移概率.式(5)表示2點(diǎn)沿元路徑在中點(diǎn)類型M下相遇的概率：

HeteSim(A1,Al+1|P)=UA1A2×UA2A3×…×
Umid-1M×VM×Vmid+1×VAlAl+1,

(5)

其中，P1P2,…,Pn是構(gòu)成元圖的元路徑集合，所以兩者在中點(diǎn)類型M下相遇的概率表示為

HeteMGSim(A1,Al+1|S)=
HeteSim(A1,Al+1|P1)×
HeteSim(A1,Al+1|P2)×…×
HeteSim(A1,Al+1|Pk)=
HeteSim(A1,Al+1|P1LP1R)×…×
HeteSim(A1,Al+1|PkLPkR).

(6)

4.2 利用神經(jīng)網(wǎng)絡(luò)嵌入節(jié)點(diǎn)

在異構(gòu)信息網(wǎng)中，每個(gè)元圖都可以獲取特定的語(yǔ)義關(guān)系信息，利用關(guān)鍵元圖的信息將其融合，可以很大程度上保留原網(wǎng)絡(luò)的全部結(jié)構(gòu)和語(yǔ)義信息，所以利用基于元圖的節(jié)點(diǎn)相似度進(jìn)行網(wǎng)絡(luò)嵌入將會(huì)是非常有效的方法.

我們由此提出一種多元圖融合的無監(jiān)督網(wǎng)絡(luò)嵌入方法，利用自動(dòng)編碼器模型[11]首先對(duì)基于元圖的相似度特征進(jìn)行降維，然后學(xué)習(xí)不同元圖的權(quán)重，最后融合不同元圖下節(jié)點(diǎn)的向量表示.

深度自動(dòng)編碼器模型可以通過一系列非線性映射操作將網(wǎng)絡(luò)的原始特征映射到一個(gè)低維的特征空間中.自動(dòng)編碼器包括編碼和解碼2部分，編碼部分映射原始特征向量到目標(biāo)特征空間，同時(shí)解碼部分恢復(fù)潛在特征表示到重構(gòu)空間.模型的目的是保證原始特征與重構(gòu)特征盡可能相似，以減少降維過程造成的信息損失.

本文擴(kuò)展傳統(tǒng)的自動(dòng)編碼器模型用于解決基于元圖的網(wǎng)絡(luò)節(jié)點(diǎn)嵌入問題，該模型以多個(gè)元相似矩陣作為輸入，比如在社交網(wǎng)絡(luò)中，如果想保留所有用戶之間的相似度，那么矩陣的行就可以表示特定元圖下的某一用戶與其他用戶的相似度分?jǐn)?shù).每個(gè)元圖對(duì)應(yīng)的相似度矩陣，都需要執(zhí)行一系列獨(dú)立的編碼和解碼操作，同時(shí)為了融合不同元圖的信息，增加了編碼階段潛在特征整合的隱藏層和解碼階段潛在特征分解的隱藏層.自動(dòng)編碼器的結(jié)構(gòu)如圖2所示：

Fig. 2 Auto-encoder for node embedding圖2 自動(dòng)編碼器嵌入節(jié)點(diǎn)

在編碼部分，xi代表節(jié)點(diǎn)的原始特征，yi是隱藏層的潛在特征，在目標(biāo)空間中的編碼結(jié)果表示為zi，式(7)～(9)表示這些變量間的關(guān)系：

(7)

(8)

(9)

(10)

(11)

(12)

該模型的目標(biāo)函數(shù)是最小化網(wǎng)絡(luò)中所有實(shí)例的原始特征向量與重構(gòu)特征向量之間的編碼損失.由于輸入向量是極其稀疏的，即相似度矩陣中零元素的數(shù)量要遠(yuǎn)遠(yuǎn)超過非零元素的數(shù)量，直接將其放入模型中會(huì)增加零元素的編碼解碼操作，為克服這個(gè)問題，在定義損失函數(shù)時(shí)，為非零特征的損失分配較高的權(quán)重值，進(jìn)一步對(duì)每個(gè)元圖的損失求和，最終的損失函數(shù)表示為

(13)

5 實(shí)驗(yàn)與分析

在數(shù)據(jù)集上測(cè)試本文提出的網(wǎng)絡(luò)嵌入算法.

5.1 數(shù)據(jù)集

如表1所示，本文使用3個(gè)數(shù)據(jù)集，DBLP1包含339篇文章以及文章的作者、來源、參考文獻(xiàn)3種屬性信息.為降低稀疏性，我們?cè)跀?shù)據(jù)集中選擇發(fā)表論文25篇以上的作者集合，以及論文數(shù)量在50篇以上的會(huì)議和期刊，利用論文及其屬性信息構(gòu)建異構(gòu)網(wǎng)絡(luò).網(wǎng)絡(luò)鏈接包括author-paper，paper-venue，paper-paper這3種類型.我們用DBLP1完成節(jié)點(diǎn)的鏈路預(yù)測(cè)任務(wù).DBLP2[17]是帶有標(biāo)簽的數(shù)據(jù)集，與DBLP1相比，DBLP2增加了論文的主題信息和各類節(jié)點(diǎn)的標(biāo)簽信息，其中的標(biāo)簽類型代表4類研究領(lǐng)域.因?yàn)镈BLP2丟失了論文間的引用關(guān)系，而該信息對(duì)paper，author類型節(jié)點(diǎn)的鏈路預(yù)測(cè)有很重要的作用(如預(yù)測(cè)論文未來的引用關(guān)系、預(yù)測(cè)合作者關(guān)系)，所以我們僅利用DBLP2完成節(jié)點(diǎn)分類任務(wù).DEG是包含學(xué)位信息的數(shù)據(jù)集，其構(gòu)建的異構(gòu)網(wǎng)絡(luò)包括degree，person，school，term這4種類型的節(jié)點(diǎn)以及person-degree，degree-term，degree-school這3種類型的連接關(guān)系.我們用DEG完成節(jié)點(diǎn)的鏈路預(yù)測(cè)任務(wù).

Table 1 Statistics of Datasets表1 數(shù)據(jù)集統(tǒng)計(jì)

5.2 實(shí)驗(yàn)設(shè)置及對(duì)比實(shí)驗(yàn)

本文將HE-MGF算法與4種算法進(jìn)行比較.

1) AD.我們用人工指定關(guān)鍵元圖代替HE-NGF模型的元圖生成部分.圖3所示的元圖是DBLP1，DEG的常用元圖.

2) Dual-stage[14].一種利用樣本進(jìn)行監(jiān)督學(xué)習(xí)的方法，具體思路是利用種子元圖，通過結(jié)構(gòu)相似度啟發(fā)式獲取候選元圖，再根據(jù)特定語(yǔ)義下選擇的訓(xùn)練樣本進(jìn)行雙向訓(xùn)練得到有效的元圖和相應(yīng)的權(quán)重值.

3) DeepWalk[1].忽略網(wǎng)絡(luò)異構(gòu)性，利用skip-gram模型的網(wǎng)絡(luò)表示學(xué)習(xí)方法.

4) Metapath2vec[18].基于元路徑的隨機(jī)游走重構(gòu)節(jié)點(diǎn)的異質(zhì)鄰居，并用skip-gram模型進(jìn)行節(jié)點(diǎn)嵌入的方法.

Fig. 3 Meta-graphs圖3 常用元圖

設(shè)置AD和Dual-stage對(duì)比實(shí)驗(yàn)的目的是評(píng)估元圖生成算法的有效性.根據(jù)本文的頻繁元圖挖掘和聚類算法得到當(dāng)前網(wǎng)絡(luò)中的部分關(guān)鍵元圖，將其嵌入結(jié)果與常用的DBLP元圖以及利用樣本進(jìn)行監(jiān)督學(xué)習(xí)的結(jié)果進(jìn)行分析比較，以評(píng)估元圖生成和聚類算法的優(yōu)越性.設(shè)置DeepWalk和Metapath2vec對(duì)比實(shí)驗(yàn)的目的是評(píng)估利用元圖信息相比于元路徑信息，或者不考慮異構(gòu)信息進(jìn)行嵌入的優(yōu)越性.

實(shí)驗(yàn)中，將4種算法的嵌入結(jié)果分別應(yīng)用于DBLP的鏈路預(yù)測(cè)和節(jié)點(diǎn)分類的挖掘任務(wù)中，因?yàn)樗x數(shù)據(jù)集包含時(shí)間屬性信息，所以可以實(shí)現(xiàn)2種鏈路預(yù)測(cè)任務(wù)，包括當(dāng)前網(wǎng)絡(luò)中未發(fā)現(xiàn)鏈路的推理和未來時(shí)點(diǎn)的鏈路預(yù)測(cè).在鏈路預(yù)測(cè)任務(wù)中，隨機(jī)選擇作者類型的節(jié)點(diǎn)對(duì)構(gòu)建測(cè)試集，包括當(dāng)前存在鏈接(合作者關(guān)系)的正樣本和不存在鏈接的負(fù)樣本，目標(biāo)是預(yù)測(cè)網(wǎng)絡(luò)中的合作者關(guān)系.在節(jié)點(diǎn)分類任務(wù)中，我們利用DBLP2的類標(biāo)簽訓(xùn)練SVM模型，測(cè)試節(jié)點(diǎn)關(guān)于研究領(lǐng)域分類的準(zhǔn)確性.在DEG鏈路預(yù)測(cè)任務(wù)中，隨機(jī)選擇degree類型的節(jié)點(diǎn)對(duì)，根據(jù)節(jié)點(diǎn)對(duì)是否處于同一語(yǔ)義類別劃分正樣本和負(fù)樣本.用準(zhǔn)確率、召回率、F1值度量不同算法的執(zhí)行效果.

5.3 實(shí)驗(yàn)結(jié)果

1) 預(yù)測(cè)、分類性能比較

如表2～4所示，在實(shí)驗(yàn)參數(shù)選擇最優(yōu)的情況下，與AD和Dual-stage算法相比，HE-MGF模型發(fā)現(xiàn)的元圖能更全面地獲取節(jié)點(diǎn)間的結(jié)構(gòu)和語(yǔ)義關(guān)系.而與DeepWalk和Metapath2vec算法相比，HE-MGF模型充分考慮了節(jié)點(diǎn)類型的異構(gòu)信息，以及網(wǎng)絡(luò)中代表不同語(yǔ)義關(guān)系的復(fù)雜圖結(jié)構(gòu)，使學(xué)習(xí)到的節(jié)點(diǎn)向量保留了除節(jié)點(diǎn)鄰接關(guān)系之外的其他重要信息，進(jìn)而達(dá)到較好的鏈路預(yù)測(cè)效果.

Table 2 Link Prediction Performance in Network Embedding(DBLP1)

Table 3 Node Classification Performance in Network Embedding (DBLP2)

Table 4 Link Prediction Performance in Network Embedding(DEG)

2) 頻繁度閾值的影響

元圖發(fā)現(xiàn)算法生成的關(guān)鍵元圖數(shù)量取決于子圖頻繁度的設(shè)置，較大的頻繁度可以獲得最關(guān)鍵的元圖集合，而較小的閾值設(shè)定可以得到更多類型的元圖，增加結(jié)構(gòu)和語(yǔ)義信息的多樣性.通過設(shè)置不同的閾值挖掘頻繁元圖，進(jìn)而完成節(jié)點(diǎn)嵌入和節(jié)點(diǎn)分類，可以發(fā)現(xiàn)適用于當(dāng)前數(shù)據(jù)集的閾值大小.我們比較了在不同嵌入維度d下，頻繁度閾值s對(duì)節(jié)點(diǎn)分類效果的影響，實(shí)驗(yàn)結(jié)果如圖4所示，最優(yōu)值為：d=150，s=60.

Fig. 4 Influence of support threshold圖4 頻繁度閾值的影響

3) 節(jié)點(diǎn)的向量表示維度的選擇

HE-MGF中自動(dòng)編碼器的嵌入維度會(huì)很大程度上影響節(jié)點(diǎn)表示學(xué)習(xí)的效果，所以需要對(duì)嵌入維度的敏感性進(jìn)行測(cè)試和分析.在4種對(duì)比算法中，因?yàn)镈eepWalk和Metapath2vec與HE-MGF采用的是完全不同的嵌入方式，而另外2種對(duì)比算法與HE-MGF除了在選擇元圖的部分存在差異外，它們使用的網(wǎng)絡(luò)嵌入模型都是編碼器，所以嵌入維度的敏感性是相似的.因此本文選擇對(duì)比算法中的DeepWalk和Metapath2vec，觀測(cè)維度參數(shù)的變化對(duì)嵌入結(jié)果的影響.實(shí)驗(yàn)結(jié)果如圖5所示，可以發(fā)現(xiàn)隨著嵌入維度的增大，節(jié)點(diǎn)分類的效果得到了顯著的提升，直到達(dá)到最優(yōu)值，之后嵌入維度的增加反而會(huì)降低節(jié)點(diǎn)分類效果.HE-MGF的嵌入維度最佳值為d=150.

Fig. 5 Influence of node embedding dimension圖5 節(jié)點(diǎn)嵌入維度的影響

4) 聚類數(shù)量k的影響

較多的元圖能抓取更加全面的信息，但是考慮到后續(xù)節(jié)點(diǎn)嵌入模型具有較高的復(fù)雜度，如果選擇過多的元圖，則需要大量計(jì)算節(jié)點(diǎn)在不同結(jié)構(gòu)下的相似度，進(jìn)而構(gòu)建目標(biāo)節(jié)點(diǎn)的相似度矩陣.根據(jù)實(shí)驗(yàn)結(jié)果發(fā)現(xiàn)，過多的元圖對(duì)于嵌入效果并沒有顯著的提升，所以考慮到效率問題，應(yīng)該在保證較高嵌入質(zhì)量的前提下選擇較少的元圖.我們比較了在不同頻繁度閾值s下，k值對(duì)鏈路預(yù)測(cè)效果的影響.我們?cè)谶@部分展示DBLP1與DEG的k值選擇結(jié)果，實(shí)驗(yàn)結(jié)果如圖6所示，DBLP1的最佳值為s=60，k=8.得到的有效元圖包括APA，APAPA，APPPA，APVPA，APPA，APA(APPPA)，APVPAPA，APA(APPPVPA).如圖7所示，DEG的最佳值為s=20，k=8.得到的有效元圖包括DTD，DPD，DSD，DTDTD，DPDPD，DTDPD，DTD(DSD)，DPD(DSD).與常用元圖相比，HE-MGF算法發(fā)現(xiàn)的元圖不但類型更全面，而且應(yīng)用于不同網(wǎng)絡(luò)的靈活性較高.

Fig. 6 Influence of k in DBLP1圖6 DBLP1中k值的影響

Fig. 7 Influence of k in DEG圖7 DEG中k值的影響

5) HE-MGF算法的執(zhí)行效率

因?yàn)轭l繁元圖發(fā)現(xiàn)算法中頻繁度參數(shù)的設(shè)定對(duì)HE-MGF執(zhí)行時(shí)間有重要影響，所以在這部分我們比較了在不同頻繁度閾值s下，數(shù)據(jù)集規(guī)模對(duì)算法性能的影響，實(shí)驗(yàn)結(jié)果如圖8所示：

Fig. 8 Running time of different data sizes圖8 不同數(shù)據(jù)集規(guī)模的運(yùn)行時(shí)間

6 總 結(jié)

本文提出一種多元圖融合的網(wǎng)絡(luò)節(jié)點(diǎn)表示模型.其中，利用頻繁元圖挖掘算法和進(jìn)一步元圖聚類實(shí)現(xiàn)了元圖的自動(dòng)發(fā)現(xiàn)任務(wù)，避免通過用戶指定和監(jiān)督學(xué)習(xí)生成元圖造成的信息缺失問題.同時(shí)，基于多元圖的網(wǎng)絡(luò)節(jié)點(diǎn)嵌入方法，利用無監(jiān)督的自動(dòng)編碼器結(jié)構(gòu)，可以自動(dòng)學(xué)習(xí)網(wǎng)絡(luò)中的關(guān)鍵元路徑以及相應(yīng)的權(quán)重值.另外，對(duì)基于元路徑計(jì)算節(jié)點(diǎn)相似度方法的改進(jìn)可以較好地適應(yīng)元圖的應(yīng)用場(chǎng)景，且具有更強(qiáng)的通用性.實(shí)驗(yàn)證明，本文提出的方法在準(zhǔn)確率和召回率上都有較好的效果.接下來，將本文的網(wǎng)絡(luò)嵌入方法擴(kuò)展到跨網(wǎng)絡(luò)或者動(dòng)態(tài)網(wǎng)絡(luò)的應(yīng)用場(chǎng)景中，以解決更廣泛的異構(gòu)信息網(wǎng)的數(shù)據(jù)挖掘問題.