趙 瑜,譚海寧,劉志方，武 超

(1. 91977部隊(duì)，北京 100142; 2. 中國科學(xué)院大學(xué)，北京 100049;3. 中國科學(xué)院 計(jì)算技術(shù)研究所， 北京 100190; 4. 西南電子電信技術(shù)研究所， 四川 成都 610041;5. 中國電子科技集團(tuán)公司 電子科學(xué)研究院，北京 100041)

0 引言

現(xiàn)實(shí)世界中,隨著互聯(lián)網(wǎng)的發(fā)展,各類可以通過圖來進(jìn)行描述刻畫的網(wǎng)絡(luò)數(shù)據(jù)呈現(xiàn)爆發(fā)式的增長,比如社交網(wǎng)絡(luò)、論文引用網(wǎng)絡(luò)、基因圖譜等。這些圖數(shù)據(jù)或者對象、個體、群組或者組件之間存在聯(lián)系或者相互影響,形成了結(jié)構(gòu)復(fù)雜、數(shù)據(jù)規(guī)模大、相互連接的復(fù)雜信息網(wǎng)絡(luò)。如今,對信息網(wǎng)絡(luò)(如萬維網(wǎng)、生物信息網(wǎng)絡(luò))的分析,已經(jīng)得到了社會科學(xué)、計(jì)算機(jī)科學(xué)、物理學(xué)、生物學(xué)等領(lǐng)域研究者的廣泛關(guān)注,并且研究成果已經(jīng)應(yīng)用在各個領(lǐng)域中。而在網(wǎng)絡(luò)分析過程中,一個重要的問題就是如何合適地表示網(wǎng)絡(luò)信息。傳統(tǒng)的信息網(wǎng)絡(luò)表示方法一般使用高維度的稀疏向量,然而高維度的稀疏向量的表示方式成為人們使用相關(guān)的統(tǒng)計(jì)學(xué)習(xí)方法進(jìn)行網(wǎng)絡(luò)分析的局限所在,由于高維度的向量表示將會帶來很大的空間浪費(fèi)和計(jì)算時(shí)間開銷[1-2]。隨著表示學(xué)習(xí)技術(shù)在自然語言處理、計(jì)算機(jī)視覺等領(lǐng)域的發(fā)展和廣泛應(yīng)用,研究者開始探索將網(wǎng)絡(luò)中的節(jié)點(diǎn)表示為低維稠密的向量表示方法,網(wǎng)絡(luò)表示學(xué)習(xí)概念應(yīng)運(yùn)而生，各類網(wǎng)絡(luò)表示學(xué)習(xí)方法及模型也如雨后春筍般層出不窮[2-5]。

當(dāng)前大多數(shù)的網(wǎng)絡(luò)表示學(xué)習(xí)研究通常假設(shè)網(wǎng)絡(luò)是同構(gòu)的,即網(wǎng)絡(luò)中的節(jié)點(diǎn)和節(jié)點(diǎn)之間具有相同的鏈接關(guān)系,例如，Eigenmaps[6]、Deepwalk[3]、Node2vec[7]、LINE[8]、Grarep[9]、SDNE[10]等。然而,實(shí)際生活中大多數(shù)網(wǎng)絡(luò)是異構(gòu)的,即網(wǎng)絡(luò)中的節(jié)點(diǎn)類型和鏈接關(guān)系不是相同類型的,例如，微信網(wǎng)絡(luò)由用戶、照片、文本信息等多種類型節(jié)點(diǎn)組成,除了人與人之間的朋友關(guān)系,還存在著其他類型的關(guān)系,如個人和照片之間的標(biāo)記關(guān)系、個人與文本消息之間的發(fā)布關(guān)系、文本消息與文本消息之間的回復(fù)關(guān)系等[11]?？梢钥闯?異構(gòu)信息網(wǎng)絡(luò)包含了更加全面的信息,蘊(yùn)含了更加豐富的語義,正是由于異構(gòu)信息網(wǎng)絡(luò)的特殊性,同構(gòu)網(wǎng)絡(luò)的表示學(xué)習(xí)方法不能直接遷移應(yīng)用于異構(gòu)信息網(wǎng)絡(luò),為網(wǎng)絡(luò)表示學(xué)習(xí)帶了諸多挑戰(zhàn)。近些年,面向異構(gòu)信息網(wǎng)絡(luò)的表征學(xué)習(xí)發(fā)展異常迅猛,并且取得了很多有價(jià)值的研究成果。

主流的異構(gòu)信息網(wǎng)絡(luò)表征學(xué)習(xí)方法可以根據(jù)學(xué)習(xí)模型方法的不同分為兩類： 一類是生成式模型,在生成式模型中我們假設(shè)異構(gòu)信息網(wǎng)絡(luò)中存在一個潛在的、真實(shí)的連續(xù)性分布ptrue(v|vc),ptrue(v|vc)就是指除了vc之外其他節(jié)點(diǎn)與該節(jié)點(diǎn)的關(guān)系分布；另一類是判別式模型,判別式模型主要是直接學(xué)習(xí)兩個節(jié)點(diǎn)之間邊的概率分布,并且將兩個節(jié)點(diǎn)v和vc聯(lián)合作為特征,然后輸出兩個節(jié)點(diǎn)之間存在邊的概率ptrue(edge|v,vc)。

從以上兩類工作可以看出,在異構(gòu)信息網(wǎng)絡(luò)表征學(xué)習(xí)領(lǐng)域,生成式模型和判別式模型都體現(xiàn)出了各自的優(yōu)勢,但是卻沒有工作很好地將生成式模型和判別式模型進(jìn)行融合。GraphGAN[12]、ANE[13]借助對抗生成網(wǎng)絡(luò)巧妙地將生成式模型和判別式模型進(jìn)行融合,但是GraphGAN主要是面向同構(gòu)信息網(wǎng)絡(luò),受GraphGAN的啟發(fā),本文主要是基于對抗生成網(wǎng)絡(luò),提出面向異構(gòu)信息網(wǎng)絡(luò)的表征學(xué)習(xí)框架。

本文的主要貢獻(xiàn)包括：

(1) 我們提出了基于對抗生成網(wǎng)絡(luò)的異構(gòu)信息網(wǎng)絡(luò)表征學(xué)習(xí)模型HINGAN,能夠同時(shí)融合生成式模型和判別式模型進(jìn)行網(wǎng)絡(luò)表征學(xué)習(xí)。

(2) 我們的方法HINGAN提出了一種新的面向異構(gòu)信息網(wǎng)絡(luò)的表征學(xué)習(xí)方法,該方法利用元路徑進(jìn)行節(jié)點(diǎn)上下文的探索,并且結(jié)合生成對抗模型進(jìn)行表征學(xué)習(xí)。

(3) 我們在幾個真實(shí)的數(shù)據(jù)集上進(jìn)行多標(biāo)簽分類、鏈路預(yù)測以及可視化等網(wǎng)絡(luò)分析任務(wù),實(shí)驗(yàn)結(jié)果表明HINGAN在三個應(yīng)用場景中都取得了不錯的結(jié)果。

本文的結(jié)構(gòu)組織安排如下： 第1節(jié)介紹了面向異構(gòu)信息網(wǎng)絡(luò)表征學(xué)習(xí)的相關(guān)工作，包括基于生成式模型和基于判別式模型的相關(guān)方法。第2節(jié)詳細(xì)地定義和描述了本文提出的表征框架HINGAN。第3節(jié)通過充分的實(shí)驗(yàn)對本文提出的方法進(jìn)行有效的驗(yàn)證，并報(bào)告相關(guān)的實(shí)驗(yàn)結(jié)果。最后,第4節(jié)對本文工作進(jìn)行了總結(jié)，并展望該技術(shù)的未來發(fā)展方向和前景。

1 相關(guān)工作

本節(jié)我們將詳細(xì)介紹面向異構(gòu)信息網(wǎng)絡(luò)的表征方法，包括基于生成式模型的表征學(xué)習(xí)方法、基于判別式模型的表征學(xué)習(xí)方法以及融合生成式和判別式模型的表征學(xué)習(xí)方法。

首先，基于生成式模型的異構(gòu)信息網(wǎng)絡(luò)表示方法主要有HERec[14]、Metapath2vec[15]、SERL[16]等。

HERec[14]提出了一種基于異構(gòu)信息網(wǎng)絡(luò)表示的推薦模型,文中首先利用元路徑進(jìn)行路徑探索，獲得路徑序列,然后按照類型進(jìn)行歸類過濾,獲得同一類型節(jié)點(diǎn)基于某一元路徑的鄰居上下文,通過這種方法巧妙地將異構(gòu)信息網(wǎng)絡(luò)表征學(xué)習(xí)問題轉(zhuǎn)化為同構(gòu)網(wǎng)絡(luò)表征學(xué)習(xí)問題。這樣,基于不同的元路徑可以獲得不同的網(wǎng)絡(luò)表征向量R。最后文章中提出了一種非線性融合框架,將不同元路徑學(xué)習(xí)到的網(wǎng)絡(luò)表征向量進(jìn)行融合轉(zhuǎn)換,用于進(jìn)一步的推薦任務(wù)。

Metapath2vec[15]提出了基于Skip-gram[17]算法的異構(gòu)信息網(wǎng)絡(luò)表征框架，Metapath2vec和Metapath2vec++。Metapath2vec將不同類型的節(jié)點(diǎn)按照同構(gòu)節(jié)點(diǎn)對待,直接作為skip-gram模型的輸入,進(jìn)行網(wǎng)絡(luò)表征學(xué)習(xí)。而Metapath2vec++在Metapath2vec的基礎(chǔ)上改進(jìn)了損失函數(shù)的評估方式,分類型進(jìn)行損失函數(shù)構(gòu)建,對類型進(jìn)行了區(qū)分。經(jīng)過實(shí)驗(yàn)對比發(fā)現(xiàn)兩種方法各有利弊,適用于不同的網(wǎng)絡(luò)分析任務(wù)中。

SERL[16]提出了一種融合不同語義元路徑信息的異構(gòu)信息網(wǎng)絡(luò)表征框架,文章主要是基于Skip-gram模型,提出了一種可以學(xué)習(xí)不同元路徑在表示學(xué)習(xí)中語義信息重要性的框架。SERL在進(jìn)行隨機(jī)游走探索節(jié)點(diǎn)上下文的過程中同時(shí)借助不同的元路徑,在一定程度上拉近了節(jié)點(diǎn)的語義鄰近性,達(dá)到了融合不同語義關(guān)系的目的。

基于判別式模型的異構(gòu)網(wǎng)絡(luò)表征學(xué)習(xí)方法主要有HIN2VEC[18]、HNE[19]等。

HIN2VEC[18]構(gòu)造了一個二分類器,針對指定的節(jié)點(diǎn)對X和Y,判斷節(jié)點(diǎn)對之間存在某種關(guān)系R的概率P(R|X,Y)。通過構(gòu)造邊的判別式模型，實(shí)現(xiàn)節(jié)點(diǎn)之間鄰近性的保留。

HNE[19]通過CNN和全連接層分別提取圖片和文本的特征信息,根據(jù)圖片—圖片、圖片—文本以及文本—文本等關(guān)系構(gòu)建損失函數(shù),并且在學(xué)習(xí)過程中,實(shí)現(xiàn)了參數(shù)共享。

結(jié)合生成式模型和判別式模型的異構(gòu)信息網(wǎng)絡(luò)表征方法主要有GraphGAN[12]、GAN-HBNR[20]等。

GraphGAN[12]: 借助對抗生成網(wǎng)絡(luò)巧妙地將生成式模型和判別式模型進(jìn)行融合，實(shí)現(xiàn)了同構(gòu)信息網(wǎng)絡(luò)表征任務(wù)。本模型本身不是專門為異構(gòu)信息網(wǎng)絡(luò)設(shè)計(jì)，但是可以通過將異構(gòu)節(jié)點(diǎn)視為同類型節(jié)點(diǎn)進(jìn)行表征學(xué)習(xí)。

GAN-HBNR[20]: 提出了一種面向異構(gòu)信息網(wǎng)絡(luò)的異構(gòu)信息表征方法，不僅考慮了網(wǎng)絡(luò)結(jié)構(gòu)，同時(shí)整合了節(jié)點(diǎn)的內(nèi)容信息，在個性化引用推薦任務(wù)中取得了不錯的效果。

2 基于對抗模型的異構(gòu)信息網(wǎng)絡(luò)表征

本文提出了一種無監(jiān)督的異構(gòu)信息網(wǎng)絡(luò)表征學(xué)習(xí)方法HINGAN，以對抗生成網(wǎng)絡(luò)為基礎(chǔ)，沿用了對抗生成網(wǎng)絡(luò)中的博弈思想，設(shè)計(jì)構(gòu)造了生成網(wǎng)絡(luò)和對抗網(wǎng)絡(luò)兩部分，并且利用元路徑進(jìn)行節(jié)點(diǎn)語義上下文的探索，達(dá)到提升網(wǎng)絡(luò)表示學(xué)習(xí)的效果。在這一節(jié)，我們首先給出在本文中用到的相關(guān)符號及其含義，然后闡述異構(gòu)信息網(wǎng)絡(luò)、元路徑以及網(wǎng)絡(luò)表征學(xué)習(xí)概念及定義，接下來介紹對抗生成網(wǎng)絡(luò)以及本文提出的表征模型HINGAN，最后將詳細(xì)分析該模型的時(shí)間及空間復(fù)雜度。

2.1 符號及其含義

為了下文闡述方便，我們首先將本文中用到的符號及其含義進(jìn)行簡單介紹，如表1所示。

表1 符號定義

2.2 問題定義

本文研究的問題是如何構(gòu)建一個合適的異構(gòu)信息網(wǎng)絡(luò)表征學(xué)習(xí)模型，并且借助對抗生成網(wǎng)絡(luò)將網(wǎng)絡(luò)中數(shù)據(jù)映射到低維向量空間。這里，我們將異構(gòu)信息網(wǎng)絡(luò)形式化定義如下：

定義1(異構(gòu)信息網(wǎng)絡(luò))信息網(wǎng)絡(luò)可以用一個有向圖G=(V,E,Φ,Y) 表示。這里V表示節(jié)點(diǎn)的集合，E∈V×V表示由來自節(jié)點(diǎn)集合V的節(jié)點(diǎn)組成的邊的集合，Φ表示節(jié)點(diǎn)的類型映射函數(shù)，即集合V中的每個節(jié)點(diǎn)都可以映射到節(jié)點(diǎn)類型集合T中的某一特定節(jié)點(diǎn)類型，可以形式化表示為Φ:V→T。Y表示邊的類型映射函數(shù)，即集合E中每條邊都可以映射到邊類型集合R中的某一特定邊類型，可以形式化表示為Y:E→R。當(dāng)|T|>1or|R|>1，該信息網(wǎng)絡(luò)G=(V,E,Φ,Y) 被稱為異構(gòu)信息網(wǎng)絡(luò)。

在面向信息網(wǎng)絡(luò)的基于鏈接的相似性度量方法中，兩個網(wǎng)絡(luò)節(jié)點(diǎn)間的相似性主要是根據(jù)指定網(wǎng)絡(luò)節(jié)點(diǎn)之間的鏈接方式(鏈接路徑)進(jìn)行衡量。由于異構(gòu)信息網(wǎng)絡(luò)中網(wǎng)絡(luò)節(jié)點(diǎn)和邊的異構(gòu)性，網(wǎng)絡(luò)節(jié)點(diǎn)之間的連接關(guān)系更具有多樣性，并且不同的連接關(guān)系代表著不同的語義關(guān)系。形式化地，我們將異構(gòu)信息網(wǎng)絡(luò)中連接兩個網(wǎng)絡(luò)節(jié)點(diǎn)的類型路徑都稱作元路徑，定義如下：

本文中，我們的目標(biāo)是獲得高質(zhì)量的異構(gòu)信息網(wǎng)絡(luò)的向量表示，更好地學(xué)習(xí)網(wǎng)絡(luò)的結(jié)構(gòu)信息。在這里我們給出網(wǎng)絡(luò)表示學(xué)習(xí)的基本定義：

定義3(網(wǎng)絡(luò)表示學(xué)習(xí))給定某異構(gòu)信息網(wǎng)絡(luò)G=(V,E,Φ,Y)，異構(gòu)信息網(wǎng)絡(luò)表示學(xué)習(xí)的目的對每一個頂點(diǎn)v∈V學(xué)習(xí)一個實(shí)數(shù)向量Rv∈Rd,其中d表示向量的維度，滿足d?|V|。

2.3 HINGAN模型

我們首先簡要介紹一下對抗生成模型，對抗生成模型最早由Goodfellow等在2014年提出，其特點(diǎn)是在模型中有兩個對立的網(wǎng)絡(luò)，一個是生成網(wǎng)絡(luò)G，一個是判別網(wǎng)絡(luò)D。生成網(wǎng)絡(luò)，在模型中將輸入數(shù)據(jù)映射到和訓(xùn)練樣本相同的空間，訓(xùn)練的目的就是學(xué)習(xí)訓(xùn)練樣本數(shù)據(jù)的關(guān)系規(guī)則，或者說是分布，使自己造樣本的能力盡可能強(qiáng)，讓判別網(wǎng)絡(luò)沒法判別真樣本和自己生成的假樣本。判別網(wǎng)絡(luò)，其輸入既可以是訓(xùn)練樣本，也可以是生成網(wǎng)絡(luò)的輸出，目的是區(qū)分輸入數(shù)據(jù)是來自樣本集還是來自生成網(wǎng)絡(luò)，其輸出是表示輸入是來自樣本集的概率。本質(zhì)上說，生成對抗網(wǎng)絡(luò)需要我們構(gòu)造形如式(1)所示的minimax博弈問題。

=Ex～pdata(x)[logD(x)]

+Ez～pdata(z)[log(1-D(G(z)))]

(1)

式(1)中，D(x)表示判別模型，G(z)表示生成模型，x～pdata(x)表示x屬于真實(shí)的數(shù)據(jù)集，z～pdata(z)表示數(shù)據(jù)z屬于生成模型G生成的假數(shù)據(jù)樣本集。

這里受生成對抗網(wǎng)絡(luò)模型的啟發(fā)，我們提出了面向異構(gòu)信息網(wǎng)絡(luò)的基于生成對抗網(wǎng)絡(luò)模型的表示學(xué)習(xí)模型HINGAN，HINGAN整體框架如圖1所示。

圖1 HINGAN模型結(jié)構(gòu)圖

由圖1可以看出，HINGAN整體框架分為三部分： 帶權(quán)同構(gòu)圖生成、生成模型構(gòu)建、判別模型構(gòu)建。下面分別詳細(xì)介紹三個模塊的實(shí)現(xiàn)方法。

(1) 帶權(quán)同構(gòu)圖生成。由于異構(gòu)信息網(wǎng)絡(luò)中含有不同類型的節(jié)點(diǎn)和邊關(guān)系，為了克服異構(gòu)信息網(wǎng)絡(luò)中節(jié)點(diǎn)類型不一致給分析和建模帶來的挑戰(zhàn)，這里我們提出了一種基于元路徑的異構(gòu)信息網(wǎng)絡(luò)協(xié)同過濾方法，主要是通過元路徑引導(dǎo)，實(shí)現(xiàn)異構(gòu)信息網(wǎng)絡(luò)異質(zhì)節(jié)點(diǎn)到同質(zhì)節(jié)點(diǎn)的帶權(quán)邊轉(zhuǎn)換，并且我們在轉(zhuǎn)換的過程中同時(shí)考慮了多元路徑信息。

由圖2可以看出,連接兩個節(jié)點(diǎn)a1→…→a2有多條元路徑，并且在異構(gòu)信息網(wǎng)絡(luò)中不同的元路徑信息表達(dá)不同的語義關(guān)系，比如路徑a1→Org→a2可以表示為元路徑Author→Organization→Author (簡寫為“AOA”)的實(shí)例，表示兩個作者來自同一個組織，而路徑a1→p1→ACL→p2→a2可以表示為元路徑Author→Paper→Venue→Paper→Author(簡寫為“APVPA”)的實(shí)例，表示兩個作者在同一個會議上發(fā)表了相關(guān)文章?？梢钥闯霾煌脑窂叫畔⒖梢詡鬟f不同的語義關(guān)系，并且兩個節(jié)點(diǎn)之間可以有多條路徑信息，即兩個節(jié)點(diǎn)之間可以包含多種語義關(guān)系。并且在實(shí)際應(yīng)用場景中，如果我們只考慮單元路徑信息，在學(xué)習(xí)過程中可能會損失大量的語義信息，比如如果我們只考慮“APVPA”，造成a1和a2之間沒有路徑，進(jìn)而模型會認(rèn)為a1和a2不鄰近，造成表示結(jié)果偏差。而如果我們同時(shí)考慮多條元路徑信息，比如增加“AOA”，由圖2可以看出，兩個節(jié)點(diǎn)之間可以重新建立鄰近性，增強(qiáng)表示學(xué)習(xí)效果，所以我們在過濾異質(zhì)節(jié)點(diǎn)的過程中需要同時(shí)考慮多條元路徑，并且給不同路徑賦予不同的權(quán)重,主要步驟如下。

圖2 多路徑實(shí)例關(guān)系互補(bǔ)示意圖

第一步根據(jù)需求選定使用元路徑集合Smp={P1,P2,…,Pn}，并且指定元路徑的權(quán)重集合μmp={μ1,μ2,…,μn}，滿足?P∈Smp都存在一個權(quán)重μ*∈μmp與之對應(yīng)。

p(vi+1|vi,P)

(2)

第三步根據(jù)第二步中探測的鄰居節(jié)點(diǎn)進(jìn)行邊的權(quán)重分配，假設(shè)節(jié)點(diǎn)對(vs,vt)之間關(guān)系邊的權(quán)重可以形式化如式(3)所示。

(3)

在這里Svs,vt指連接節(jié)點(diǎn)對(vs,vt)所有的元路徑實(shí)例組成的集合，μPinst是指元路徑實(shí)例Pinst對應(yīng)的權(quán)重，在實(shí)際轉(zhuǎn)換過程中我們按照式(4)對頂點(diǎn)的權(quán)重進(jìn)行了歸一化處理。

(4)

其中，N(vs)指節(jié)點(diǎn)vs的鄰居節(jié)點(diǎn)集合。

(2) 生成模型G和判別模型D的構(gòu)建。給定同構(gòu)圖數(shù)據(jù)網(wǎng)絡(luò)G=(V,E)，V表示網(wǎng)絡(luò)的節(jié)點(diǎn)集合，E表示邊的集合。給定節(jié)點(diǎn)vc∈V，ptrue(v|vc)指節(jié)點(diǎn)vc在節(jié)點(diǎn)集合V中的真實(shí)鄰居分布。這里我們的目標(biāo)便是學(xué)習(xí)訓(xùn)練兩個模塊： 一是生成模型G(v|vc;θG)，我們需要調(diào)整模型讓G(v|vc;θG)≈ptrue(v|vc)；二是判別模型D(v,vc;θD)，對于給定的節(jié)點(diǎn)對(v,vc),D(v,vc;θD) 表示節(jié)點(diǎn)對之間存在邊關(guān)系的概率。生成器和判別器扮演著兩個不同的角色，生成器盡力去逼近ptrue(v|vc)，爭取產(chǎn)生和vc足夠相似的點(diǎn)集，而判別器需要去區(qū)分生成器產(chǎn)生的數(shù)據(jù)和vc的真實(shí)鄰居分布。根據(jù)式(1),這里我們可以一般化對抗生成模型，如(5)所示。

+Ev～G(v|vc;θG)[log(1-D(v,vc;θG))])

(5)

在構(gòu)造判別函數(shù)的過程中，為了便于梯度計(jì)算，我們采用類似于Deepwalk中的激活方法，通過計(jì)算兩個向量內(nèi)積的sigmoid函數(shù)進(jìn)行定義，如(6)所示。

(6)

(7)

(3) 進(jìn)行生成式模型的構(gòu)建，這里我們沿用了GraphGAN[12]中的構(gòu)建方式,θG的梯度更新可以整理為如式(8)所示。

(8)

其中，G(v|vc)的計(jì)算方式按照形式化式(9)進(jìn)行計(jì)算:

(9)

(10)

式(10)中，pc(*|*) 表示兩個節(jié)點(diǎn)的相關(guān)性概率，可以引入式(6)進(jìn)行計(jì)算，具體計(jì)算方式見式(11)所示。

(11)

最后，我們將HINGAN模型整體算法總結(jié)如下：

算法1 HINGAN

2.4 復(fù)雜度分析

考慮異構(gòu)信息網(wǎng)絡(luò)表示學(xué)習(xí)是否能夠進(jìn)行實(shí)際應(yīng)用的關(guān)鍵問題在于時(shí)空復(fù)雜度，在HINGAN迭代過程中我們只需要存儲節(jié)點(diǎn)以及節(jié)點(diǎn)的鄰居信息，空間復(fù)雜度為O(|V|)。時(shí)間復(fù)雜度主要分為三部分，第一部分進(jìn)行帶權(quán)同構(gòu)圖的構(gòu)建，在這一模塊中我們只需要對某個節(jié)點(diǎn)按照元路徑進(jìn)行鄰居探測，并且在實(shí)際計(jì)算過程中，我們限制了元路徑P的長度|P|(|P|≤l),所以這部分的時(shí)間復(fù)雜度為O(|V|·lD),D代表異構(gòu)信息網(wǎng)絡(luò)里的節(jié)點(diǎn)平均度數(shù); 第二部分G(v|vc;θG)生成器部分，對應(yīng)算法1中9～12行，這部分算法復(fù)雜度為O(nGD·|V|·log|V|·k),nG為生成器對每個節(jié)點(diǎn)的采樣節(jié)點(diǎn)數(shù)，d表示節(jié)點(diǎn)表示的維度; 第三部分D(v,vc;θD)判別器部分，對應(yīng)算法1中14～17行，這部分算法的時(shí)間復(fù)雜度為O(nD·D·|V|·log|V|·d)+O(nD·|V|·d)。從整體上來說，因?yàn)閰?shù)nD,nG,D,d為常量，所以HINGAN算法的時(shí)間復(fù)雜度為O(|V|·log|V| )，可以應(yīng)用于大規(guī)模異構(gòu)信息網(wǎng)絡(luò)分析任務(wù)中。

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

在本節(jié)中我們對HINGAN進(jìn)行了大量的量化分析實(shí)驗(yàn)，為了說明HINGAN算法的有效性，我們對其在異構(gòu)信息網(wǎng)絡(luò)多標(biāo)簽分類、鏈路預(yù)測、可視化三個任務(wù)上進(jìn)行了網(wǎng)絡(luò)分析實(shí)驗(yàn)，并且與當(dāng)前的主流算法進(jìn)行了詳細(xì)的實(shí)驗(yàn)對比。其次，為了驗(yàn)證算法的魯棒性和高效性，我們分別進(jìn)行了HINGAN模型的參數(shù)敏感性和迭代效率實(shí)驗(yàn)。

3.1 實(shí)驗(yàn)數(shù)據(jù)集

我們分別選擇了AMiner、DBLP兩個異構(gòu)信息網(wǎng)絡(luò)數(shù)據(jù)集進(jìn)行多標(biāo)簽分類、鏈路預(yù)測、可視化分析任務(wù)，兩個數(shù)據(jù)集的統(tǒng)計(jì)特征如表2所示。

表2 數(shù)據(jù)集的統(tǒng)計(jì)特征

AMiner[21]網(wǎng)絡(luò)是由開放學(xué)術(shù)組織發(fā)布的億級學(xué)術(shù)圖譜，其中包括不同類型實(shí)體(如作者、論文、會議等)，并且還包含可以擴(kuò)充不同類型實(shí)體的語義數(shù)據(jù)，在本文中，我們篩選了來自8個領(lǐng)域59個學(xué)術(shù)會議的相關(guān)數(shù)據(jù)組成異構(gòu)信息網(wǎng)絡(luò)，并做進(jìn)一步的網(wǎng)絡(luò)分析。

DBLP[11]網(wǎng)絡(luò)也是在異構(gòu)信息網(wǎng)絡(luò)研究中被經(jīng)常用到的數(shù)據(jù)集。在本文中我們使用的是DBLP[11]中使用的經(jīng)過篩選的DBIS數(shù)據(jù)集，該數(shù)據(jù)集包括來自4個領(lǐng)域的20個學(xué)術(shù)會議，其中包括14 475名作者以及14 376篇論文信息。

3.2 實(shí)驗(yàn)設(shè)置

在本文實(shí)驗(yàn)中，我們選取了目前比較流行的效果較好的網(wǎng)絡(luò)表示模型，我們主要通過多標(biāo)簽分類、鏈路預(yù)測和可視化三個分析任務(wù)來進(jìn)行實(shí)驗(yàn)結(jié)果對比，下面簡單概述我們對比的主流算法。

Deepwalk[3]: 該算法借鑒了Word2Vec[17]的表示生成方式，也是基于Skip-gram模型進(jìn)行向量學(xué)習(xí)，巧妙地將深度文本表示方法用來學(xué)習(xí)網(wǎng)絡(luò)節(jié)點(diǎn)表示。并且在Deepwalk中作者通過隨機(jī)游走的形式進(jìn)行節(jié)點(diǎn)上下文的探索，以此來獲得網(wǎng)絡(luò)結(jié)構(gòu)特征向量。

Node2vec[7]: 該算法擴(kuò)展了Deepwalk，主要改進(jìn)了Deepwalk算法中隨機(jī)游走的策略，定義了兩個參數(shù)p和q,在BFS和DFS中達(dá)到一個平衡，同時(shí)考慮了局部和宏觀的語義信息。

LINE[8]: 該算法在Deepwalk基礎(chǔ)上，引入了二階關(guān)系的概念，并且LINE對一階和二階關(guān)系分別設(shè)計(jì)不同的目標(biāo)函數(shù)，然后得到兩種類型的向量，最后進(jìn)行拼接組合操作，以此來獲得節(jié)點(diǎn)的向量表達(dá)，在本實(shí)驗(yàn)中我們使用強(qiáng)化版本LINE(1st+2nd)來進(jìn)行對比實(shí)驗(yàn)。

SDNE[10]: 該算法基于自動編碼機(jī)提出了一種半監(jiān)督學(xué)習(xí)模型，用于表示網(wǎng)絡(luò)的全局結(jié)構(gòu)屬性和局部結(jié)構(gòu)屬性。

Metapath2vec[15]: 該算法是2017年微軟研究院提出的面向異構(gòu)信息網(wǎng)絡(luò)的表示學(xué)習(xí)工作，該算法使用基于元路徑的隨機(jī)游走進(jìn)行節(jié)點(diǎn)鄰居發(fā)現(xiàn)，并且用異構(gòu)節(jié)點(diǎn)版本的Skip-gram算法求解網(wǎng)絡(luò)中節(jié)點(diǎn)的向量表示，并且有兩個版本Metapath2vec和Metapath2vec++。在實(shí)際實(shí)驗(yàn)過程中發(fā)現(xiàn)，Metapath2vec性能表現(xiàn)更好一點(diǎn)，在本文中我們使用Metapath2vec版本進(jìn)行對比試驗(yàn)。

GraphGAN[12]: 借助對抗生成網(wǎng)絡(luò)巧妙地將生成式模型和判別式模型進(jìn)行融合，實(shí)現(xiàn)了同構(gòu)信息網(wǎng)絡(luò)表征任務(wù)。

在實(shí)驗(yàn)過程中，由于Deepwalk和LINE本身不是為異構(gòu)信息網(wǎng)絡(luò)設(shè)計(jì)的，所以在對比實(shí)驗(yàn)過程中，我們將模型學(xué)到的帶權(quán)網(wǎng)絡(luò)作為Deepwalk和LINE模型的輸入。而對于Metapath2vec，因?yàn)槠浔旧砭瓦m用于異構(gòu)信息網(wǎng)絡(luò)，所以直接讓Metapath2vec用于異構(gòu)信息網(wǎng)絡(luò)數(shù)據(jù)集。在參數(shù)設(shè)置方面，Deepwalk的窗口大小設(shè)置為10，隨機(jī)游走的步數(shù)設(shè)定為80，每個節(jié)點(diǎn)的游走次數(shù)設(shè)定為10。所有方法的向量表示維度都設(shè)定為128。并且對于Metapath2vec我們選定的元路徑為“APVPA”，和原文保持一致。而對于HINGAN，元路徑的長度閾值l設(shè)定為4，并且我們用Grid-search方法獲得最優(yōu)權(quán)重值μ。對于網(wǎng)絡(luò)AMiner，滿足條件的元路徑集合為{“APA”，“AOA”,“APPA”,“APVPA”}。對于DBLP，滿足條件的元路徑集合為{“APA”,“APVPA”}。

3.3 多標(biāo)簽分類任務(wù)

多標(biāo)簽分類任務(wù)是指每個節(jié)點(diǎn)會被標(biāo)記為一個或者多個標(biāo)簽，它是用來衡量網(wǎng)絡(luò)表示學(xué)習(xí)結(jié)果的一個常見的任務(wù)，本文也是用該任務(wù)來衡量模型HINGAN，使用準(zhǔn)確性(accuracy)來作為衡量指標(biāo)。在AMiner、DBLB數(shù)據(jù)集中，我們都是對作者(author)類型節(jié)點(diǎn)進(jìn)行表示，之后將10%的節(jié)點(diǎn)作為訓(xùn)練樣本，對剩下的90%節(jié)點(diǎn)進(jìn)行分類實(shí)驗(yàn)，我們用SVM來作為分類器，實(shí)驗(yàn)結(jié)果如表3、表4所示。

表3 AMiner多標(biāo)簽分類實(shí)驗(yàn)結(jié)果(準(zhǔn)確性/%)

表4 DBLP多標(biāo)簽分類實(shí)驗(yàn)結(jié)果(準(zhǔn)確性/%)

表3和表4分別表示各算法在AMiner和DBLP數(shù)據(jù)集上進(jìn)行多標(biāo)簽分類任務(wù)的準(zhǔn)確性，從表中可以看出Deepwalk和Node2vec兩個算法在多標(biāo)簽分類任務(wù)中表現(xiàn)很接近，我們的工作相較于其他方法表現(xiàn)更加優(yōu)異。在準(zhǔn)確率方面，在兩個數(shù)據(jù)集上分別取得了3.45%～10.32%和5.2%～16.2%的增益。實(shí)驗(yàn)表明雖然HINGAN建立在學(xué)習(xí)邊分布的基礎(chǔ)上，但是依然可以有效學(xué)習(xí)節(jié)點(diǎn)特征信息。除此之外，我們發(fā)現(xiàn)HINGAN的表現(xiàn)要優(yōu)于GraphGAN，反映出元路徑引導(dǎo)嵌入的優(yōu)勢。

3.4 鏈路預(yù)測任務(wù)

鏈路預(yù)測任務(wù)是指預(yù)測兩個節(jié)點(diǎn)之間是否存在邊，在本實(shí)驗(yàn)中，我們使用數(shù)據(jù)集DBLP，為了更好地進(jìn)行鏈路預(yù)測任務(wù)，在進(jìn)行實(shí)驗(yàn)之前為了防止邊太稠密，我們隨機(jī)選取50%的邊作為我們的基礎(chǔ)數(shù)據(jù)集。然后我們隨機(jī)隱藏10%的邊用來進(jìn)行鏈路預(yù)測任務(wù)，剩下的邊用來訓(xùn)練學(xué)習(xí)網(wǎng)絡(luò)表示模型，然后根據(jù)學(xué)到的節(jié)點(diǎn)表示來進(jìn)行鏈路預(yù)測。在對比實(shí)驗(yàn)中，我們添加一種對比方法CN(common neighbor)，因?yàn)樵摲椒ㄔ阪溌奉A(yù)測領(lǐng)域廣受好評。

在衡量實(shí)驗(yàn)結(jié)果過程中，我們通過指標(biāo)precision@k來進(jìn)行評估，這里precision@k表示在預(yù)測的k條邊中符合實(shí)際分布的邊所占比例。實(shí)驗(yàn)結(jié)果如表5、表6所示。

由表5、表6可以看出，在DBLP數(shù)據(jù)集上的鏈路預(yù)測任務(wù)中，HINGAN表現(xiàn)要優(yōu)于其他方法，并且隨著k值的變大，HINGAN的優(yōu)勢越來越明顯。在鏈路預(yù)測任務(wù)中，融合了判別模型的方法，如LINE、GraphGAN等，要明顯優(yōu)于生成式模型方法，如Deepwalk、Node2vec等，說明判別式模型在鏈路預(yù)測任務(wù)中表現(xiàn)更好。

表5 AMiner鏈路預(yù)測結(jié)果(precision@k)

表6 DBLP鏈路預(yù)測結(jié)果(precision@k)

在本實(shí)驗(yàn)中，我們還考慮了移除邊的比例給節(jié)點(diǎn)預(yù)測任務(wù)帶來的影響，以DBLP鏈路預(yù)測任務(wù)為例，我們通過改變移除邊的比例進(jìn)行實(shí)驗(yàn)來探索邊的稀疏性對鏈路預(yù)測任務(wù)帶來的影響，選取移除比例分別為15%，25%，40%，50%，80%來進(jìn)行實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果如圖3所示。

圖3 稀疏性對鏈路預(yù)測任務(wù)性能影響評估結(jié)果

由圖3可以看出，我們改變異構(gòu)信息網(wǎng)絡(luò)的稀疏性會降低各種方法在鏈路預(yù)測任務(wù)中的準(zhǔn)確性，但是我們的方法HINGAN在鏈路預(yù)測任務(wù)中的評估結(jié)果始終優(yōu)于其他模型，由于Deepwalk、Node2vec、Metapath2vec模型相似，所以變化趨勢也非常相似，而LINE、SDNE、GrapgGAN、 HINGAN方法結(jié)合了判別模型，所以它們表現(xiàn)更好。除此之外，我們發(fā)現(xiàn)各種方法都呈現(xiàn)出隨著邊刪除比例的增加，鏈路預(yù)測效果先急劇下降后變緩的趨勢，意味著測試邊集合減少，邊命中的概率也隨之減少，并且信息損失隨著邊的減少，對實(shí)驗(yàn)效果影響越來越弱。

3.5 可視化任務(wù)

網(wǎng)絡(luò)分析中另一個重要的應(yīng)用是可視化，在本節(jié)我們通過可視化的形式進(jìn)行向量表示的評估工作，這里我們將不同的方法學(xué)到的低維向量化表示輸入到可視化工具t-SNE[22]，在這里我們使用的是分類任務(wù)中學(xué)到的DBLP中作者(author)類型，我們隨機(jī)選取了6個類型作者中各200個作者作為輸入，可視化結(jié)果如圖4所示。

圖4 可視化結(jié)果

由圖4可以看出，相對于其他3種模型，HINGAN方法獲得的節(jié)點(diǎn)向量表示經(jīng)過降維后，節(jié)點(diǎn)聚類效果更加明顯，輪廓更加清晰，主要是由于HINGAN模型整合了生成式模型和判別式模型，構(gòu)建過程中，在生成式模型中添加了判別式約束，使節(jié)點(diǎn)向量表示結(jié)果更優(yōu)。

3.6 參數(shù)評估

本節(jié)中，我們對HINGAN中元路徑選擇、參數(shù)d(向量維度)、迭代次數(shù)進(jìn)行了詳細(xì)的實(shí)驗(yàn)評估。

圖5中，我們通過使用不同的元路徑運(yùn)行HINGAN來衡量不同的元路徑對網(wǎng)絡(luò)表征的影響，我們分別單獨(dú)使用“APA”、單獨(dú)使用“APVPA”，同時(shí)使用“APA”和“APVPA”在DBLP上進(jìn)行多標(biāo)簽分類任務(wù)。除此之外，為了驗(yàn)證生成對抗模型的有效性，我們同時(shí)運(yùn)行使用“APVPA”的Metapath2vec方法來進(jìn)行結(jié)果對比。由圖5可以看出，在使用同一條元路徑“APVPA”情況下，HINGAN的效果要優(yōu)于Metapath2vec，進(jìn)一步說明結(jié)合生成式和判別式模型能夠更好地進(jìn)行網(wǎng)絡(luò)表征。根據(jù)圖5，我們還可以發(fā)現(xiàn)使用多條元路徑相較于分別單獨(dú)使用在多分類任務(wù)中能夠取得更好的效果，說明融合更多的語義信息能夠取得更好的表征效果。在數(shù)據(jù)集AMiner上進(jìn)行相同的元路徑對比實(shí)驗(yàn)，我們?nèi)〉昧讼嗨频膶?shí)驗(yàn)結(jié)果，在這里不再進(jìn)行贅述。

圖5 不同元路徑的影響評估結(jié)果

如圖6所示，我們評估維度對預(yù)測任務(wù)的影響，d(向量維度)分別取32、64、128、200、256，通過precision@k對HINGAN向量表示進(jìn)行評估，可以看出d取128時(shí)，HINGAN表示學(xué)習(xí)效果最好。

圖6 參數(shù)評估

圖6 (續(xù))

在更新過程中我們分別對生成器和判別器迭代更新了100次，每迭代一次將中間結(jié)果用于鏈路預(yù)測任務(wù)并評估precision@500,實(shí)驗(yàn)結(jié)果如圖所示，我們發(fā)現(xiàn)20～30之間準(zhǔn)確率較高并且可以減少計(jì)算開銷，所以在實(shí)驗(yàn)中我們設(shè)定迭代次數(shù)為30。

4 總結(jié)和展望

本文提出了一種融合生成式模型和判別式模型的面向異構(gòu)信息網(wǎng)絡(luò)的表示學(xué)習(xí)方法HINGAN。HINGAN一方面借助多元路徑進(jìn)行節(jié)點(diǎn)語義鄰居的探索，提高節(jié)點(diǎn)的語義鄰近性；另一方面，HINGAN借鑒生成對抗的博弈思想，通過構(gòu)建生成器和判別器，在生成判別的迭代更新過程中，更好的探索節(jié)點(diǎn)結(jié)構(gòu)和語義信息。本文在多個真實(shí)世界的網(wǎng)絡(luò)上進(jìn)行大量實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明該方法在多標(biāo)簽分類、邊關(guān)系預(yù)測和可視化三個應(yīng)用場景中都取得了不錯的表現(xiàn)。與此同時(shí)，HINGAN是可以實(shí)現(xiàn)規(guī)?；瘮U(kuò)展的，可以應(yīng)用到大規(guī)模網(wǎng)絡(luò)分析和挖掘任務(wù)。

在未來工作中，我們將進(jìn)一步考慮高效的面向異構(gòu)信息網(wǎng)絡(luò)的表示學(xué)習(xí)方法，并將從以下幾個方面進(jìn)行嘗試。

(1) 結(jié)合分布式機(jī)器學(xué)習(xí)技術(shù)，將HINGAN進(jìn)行分布式算法擴(kuò)展，結(jié)合近期盛行的GPU、TPU等高效計(jì)算方式，讓分析超大規(guī)模信息網(wǎng)絡(luò)成為可能。

(2) 如何解決網(wǎng)絡(luò)動態(tài)性問題，在實(shí)際應(yīng)用場景中，比如社交網(wǎng)絡(luò)，網(wǎng)絡(luò)中節(jié)點(diǎn)和邊的關(guān)系是動態(tài)變化的，而目前大多數(shù)的網(wǎng)絡(luò)表示學(xué)習(xí)方式都是建立在靜態(tài)網(wǎng)絡(luò)數(shù)據(jù)上，所以如何對網(wǎng)絡(luò)動態(tài)性進(jìn)行合理化建模，實(shí)現(xiàn)在線的實(shí)時(shí)的網(wǎng)絡(luò)表示任務(wù)，值得更多的關(guān)注。

(3) 如何解決表示學(xué)習(xí)過程中參數(shù)自動化學(xué)習(xí)問題，現(xiàn)在網(wǎng)絡(luò)表示學(xué)習(xí)方法普遍采用半監(jiān)督的方式，需要通過引入標(biāo)簽數(shù)據(jù)進(jìn)行超參數(shù)的學(xué)習(xí)，所以想要解決參數(shù)自動化學(xué)習(xí)問題，依然有很長的路要走。