趙雪莉，盧光躍，呂少卿+，張 潘

1.西安郵電大學(xué) 通信與信息工程學(xué)院，西安710121

2.西安郵電大學(xué) 陜西省信息通信網(wǎng)絡(luò)及安全重點(diǎn)實驗室，西安710121

現(xiàn)實世界普遍存在各種各樣復(fù)雜但蘊(yùn)含著豐富信息的網(wǎng)絡(luò)，如社交網(wǎng)絡(luò)、生物網(wǎng)絡(luò)和物流網(wǎng)絡(luò)等。其中二分網(wǎng)絡(luò)是復(fù)雜網(wǎng)絡(luò)中一種重要的網(wǎng)絡(luò)表現(xiàn)形式，該類網(wǎng)絡(luò)由兩種類型的節(jié)點(diǎn)構(gòu)成，其邊只存在于不同類型的節(jié)點(diǎn)之間，如引文網(wǎng)絡(luò)[1]中作者和其論文發(fā)表的會議、購物網(wǎng)絡(luò)中用戶和商品、社交網(wǎng)絡(luò)中用戶和其所屬社區(qū)等均能抽象為二分網(wǎng)絡(luò)。因此對二分網(wǎng)絡(luò)進(jìn)行研究和分析具有非常高的應(yīng)用價值。

在針對網(wǎng)絡(luò)結(jié)構(gòu)的研究中，一個重要的問題是如何合適地表示網(wǎng)絡(luò)結(jié)構(gòu)信息。傳統(tǒng)的網(wǎng)絡(luò)表示一般采用高維稀疏矩陣，但高維稀疏矩陣往往需要更高的時間和空間成本。同時，隨著人工智能技術(shù)的突飛猛進(jìn)，越來越多的研究領(lǐng)域都融入了機(jī)器學(xué)習(xí)、深度學(xué)習(xí)等技術(shù)，但是傳統(tǒng)的網(wǎng)絡(luò)表示方法無法直接應(yīng)用這些算法，因此研究人員轉(zhuǎn)而探索將網(wǎng)絡(luò)中的節(jié)點(diǎn)表示為低維向量的方法，即網(wǎng)絡(luò)表示學(xué)習(xí)（或網(wǎng)絡(luò)嵌入）。網(wǎng)絡(luò)表示學(xué)習(xí)將網(wǎng)絡(luò)中的節(jié)點(diǎn)表示為低維稠密向量，并且最大程度地保留原網(wǎng)絡(luò)中的結(jié)構(gòu)信息和特性，隨后這些表示向量作為對應(yīng)節(jié)點(diǎn)的特征能夠被應(yīng)用到后續(xù)的節(jié)點(diǎn)分類[2]、鏈路預(yù)測[3]、社區(qū)發(fā)現(xiàn)[4]、推薦[5-6]和可視化[7]等任務(wù)中。

目前已有的網(wǎng)絡(luò)表示學(xué)習(xí)算法主要針對同質(zhì)網(wǎng)絡(luò)，即只包含一種類型節(jié)點(diǎn)的網(wǎng)絡(luò)，如Deep Walk[8]、

Node2vec[9]、LINE（large-scale information network embedding）[10]和SDNE（structural deep network embedding）[11]等。盡管這些算法已經(jīng)被應(yīng)用在相關(guān)網(wǎng)絡(luò)分析任務(wù)中，卻很難有效地應(yīng)用于二分網(wǎng)絡(luò)。與同質(zhì)網(wǎng)絡(luò)不同，二分網(wǎng)絡(luò)中有兩類節(jié)點(diǎn)，而且邊只存在于不同類型的節(jié)點(diǎn)之間，即顯式關(guān)系，但同類型的節(jié)點(diǎn)之間仍存在某種隱式關(guān)系，這種隱式關(guān)系與顯式關(guān)系的語義完全不同。文獻(xiàn)[12]表明對這種隱式關(guān)系建?？梢蕴岣吣Ｐ偷耐扑]性能。另一方面，由于周期性問題，在二分網(wǎng)絡(luò)上執(zhí)行隨機(jī)游走可能會失敗[13]。

與此同時，一些學(xué)者提出了針對異質(zhì)網(wǎng)絡(luò)的表示學(xué)習(xí)算法，如基于元路徑的metapath2vec 和metapath2vec++[14]等。雖然針對異質(zhì)網(wǎng)絡(luò)的表示學(xué)習(xí)算法也可以應(yīng)用于二分網(wǎng)絡(luò)，但該類方法同樣沒有區(qū)分具有不同語義的顯式關(guān)系和隱式關(guān)系。

因此一些專門針對二分網(wǎng)絡(luò)的表示學(xué)習(xí)算法如BiNE（bipartite network embedding）[15-16]、FOBE 和HOBE（first-and high-order bipartite embeddings）[17]被提出。此類方法基于二分網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)，從不同角度進(jìn)行建模得到網(wǎng)絡(luò)的低維表示向量。

然而，真實的網(wǎng)絡(luò)往往伴隨著數(shù)據(jù)缺失導(dǎo)致的網(wǎng)絡(luò)結(jié)構(gòu)稀疏的情況，僅僅依賴拓?fù)浣Y(jié)構(gòu)很難得到理想的網(wǎng)絡(luò)表示。此外，現(xiàn)實中二分網(wǎng)絡(luò)的節(jié)點(diǎn)往往攜帶著豐富的屬性信息，如在購物網(wǎng)絡(luò)中，用戶擁有年齡段、職業(yè)、收入等屬性，商品有價格、產(chǎn)地、品牌等屬性；引文網(wǎng)絡(luò)中作者有研究領(lǐng)域、所屬機(jī)構(gòu)等屬性，論文有文本信息、出版信息等屬性。屬性作為輔助信息對稀疏網(wǎng)絡(luò)結(jié)構(gòu)的表示學(xué)習(xí)有巨大的影響。例如，在社交網(wǎng)絡(luò)中若兩個用戶不是好友關(guān)系，但若他們有相同的興趣、學(xué)歷和職業(yè)等，則在表示空間中這兩名用戶節(jié)點(diǎn)的表示向量應(yīng)該更加接近。越來越多網(wǎng)絡(luò)表示學(xué)習(xí)算法選擇融合節(jié)點(diǎn)所具有的文本、標(biāo)簽和統(tǒng)計特征等屬性信息，現(xiàn)有的工作表明[18-20]，利用屬性這一輔助信息一方面能夠提高推薦的準(zhǔn)確性，另一方面可以在一定程度上緩解數(shù)據(jù)稀疏性的問題[21]和冷啟動問題[22]。例如，文獻(xiàn)[23]研究了在社交網(wǎng)絡(luò)中結(jié)合網(wǎng)絡(luò)結(jié)構(gòu)和屬性相似性對于學(xué)習(xí)攜帶更多信息的節(jié)點(diǎn)表示的重要性，作者通過分析Facebook數(shù)據(jù)集上用戶的畢業(yè)年份、專業(yè)和宿舍等屬性信息對友誼關(guān)系的影響，發(fā)現(xiàn)屬性相似的用戶之間有更強(qiáng)的社交關(guān)系。文獻(xiàn)[24]研究表明，考慮用戶的年齡、性別和其他屬性特征對評價推薦系統(tǒng)是至關(guān)重要的。因此屬性信息對于網(wǎng)絡(luò)表示學(xué)習(xí)以及下一步的任務(wù)具有重要意義，而現(xiàn)有的針對二分網(wǎng)絡(luò)的表示學(xué)習(xí)算法都忽略了對節(jié)點(diǎn)屬性信息的利用。

為了解決上述問題，本文提出一種結(jié)合屬性信息的二分網(wǎng)絡(luò)表示學(xué)習(xí)算法ABNE（attributed bipartite network embedding），能夠?qū)⒐?jié)點(diǎn)的屬性信息融入二分網(wǎng)絡(luò)表示學(xué)習(xí)過程中從而學(xué)習(xí)到更加全面的網(wǎng)絡(luò)表示。具體來說，整個模型分為對顯式關(guān)系建模以及對結(jié)合屬性信息的隱式關(guān)系建模兩部分。首先，通過加強(qiáng)有連邊的節(jié)點(diǎn)對與對方鄰居節(jié)點(diǎn)的相似性嵌入顯式關(guān)系；此外，定義屬性相似度矩陣并將其作為權(quán)重矩陣的補(bǔ)充指導(dǎo)有偏隨機(jī)游走捕獲隱式關(guān)系，隨后通過聯(lián)合優(yōu)化顯式關(guān)系模型和結(jié)合屬性信息的隱式關(guān)系模型，最終得到同時攜帶網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息和節(jié)點(diǎn)屬性信息的二分網(wǎng)絡(luò)表示。在四個真實公開的數(shù)據(jù)集上進(jìn)行的推薦實驗結(jié)果表明了ABNE 方法的有效性。

1 相關(guān)工作

本文是結(jié)合屬性信息的二分網(wǎng)絡(luò)表示學(xué)習(xí)算法，相關(guān)的工作包括針對二分網(wǎng)絡(luò)的表示學(xué)習(xí)以及結(jié)合屬性信息的網(wǎng)絡(luò)表示學(xué)習(xí)。

BiNE 算法[15-16]是專門針對二分網(wǎng)絡(luò)的表示學(xué)習(xí)算法，該方法分別對二分網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的顯式關(guān)系和隱式關(guān)系建模，通過加強(qiáng)不同類型節(jié)點(diǎn)的相似性嵌入顯式關(guān)系，并提出了一種有偏隨機(jī)游走方式嵌入隱式關(guān)系，最后設(shè)計了一個聯(lián)合優(yōu)化框架從而得到二分網(wǎng)絡(luò)的低維向量表示；另外一個專門為二分網(wǎng)絡(luò)設(shè)計的表示學(xué)習(xí)算法是FOBE和HOBE算法[17]，其中FOBE 算法將有連接的不同類型的節(jié)點(diǎn)對分解為存在鄰居關(guān)系的同類型節(jié)點(diǎn)對捕捉局部關(guān)系，HOBE 算法通過強(qiáng)化網(wǎng)絡(luò)節(jié)點(diǎn)之間的代數(shù)距離捕捉高階關(guān)系，并聯(lián)合兩種算法同時捕捉網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的局部和高階關(guān)系從而得到網(wǎng)絡(luò)的表示學(xué)習(xí)向量。然而，以上方法均只考慮到了二分網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)，沒有涉及到二分網(wǎng)絡(luò)豐富的屬性信息。

已有的屬性網(wǎng)絡(luò)表示學(xué)習(xí)的方法主要集中在同質(zhì)網(wǎng)絡(luò)上。如基于矩陣分解的TADW（text associated deep walk）[25]，該算法首先證明了Deep Walk等價于矩陣分解，隨后將節(jié)點(diǎn)的文本特征納入網(wǎng)絡(luò)表示學(xué)習(xí)過程中，得到了同時保留結(jié)構(gòu)信息和屬性信息的網(wǎng)絡(luò)表示；基于神經(jīng)網(wǎng)絡(luò)的方法如CANE（context-aware network embedding）[26]，該算法引入卷積神經(jīng)網(wǎng)絡(luò)將屬性信息和拓?fù)浣Y(jié)構(gòu)信息整合在一起，并通過相互關(guān)注機(jī)制學(xué)習(xí)到了上下文相關(guān)的網(wǎng)絡(luò)表示從而應(yīng)用于基于文本的信息網(wǎng)絡(luò)中。然而，由于二分網(wǎng)絡(luò)特殊的節(jié)點(diǎn)類型和連邊特性與同質(zhì)網(wǎng)絡(luò)有本質(zhì)上的區(qū)別，因此上述為屬性同質(zhì)網(wǎng)絡(luò)設(shè)計的算法不能直接應(yīng)用于屬性二分網(wǎng)絡(luò)。

N2VSCDNNR（local recommender system based on node2vec and rich information network）算法[5]應(yīng)用于用戶-商品二分網(wǎng)絡(luò)，該方法首先借助商品的類別信息得到了用戶-類別網(wǎng)絡(luò)，再通過一種模式投影得到了用戶-用戶和商品-商品網(wǎng)絡(luò)，然后在這兩個網(wǎng)絡(luò)上應(yīng)用Node2vec 捕獲節(jié)點(diǎn)之間復(fù)雜的潛在關(guān)系，學(xué)習(xí)到了用戶和商品兩類節(jié)點(diǎn)的向量表示。最后，提出了一種新的聚類方法，對用戶和商品聚類用于推薦任務(wù)。然而，該算法是專門為推薦任務(wù)設(shè)計的。此外，該方法僅涉及到了二分網(wǎng)絡(luò)中一種類型節(jié)點(diǎn)的一種屬性信息，無法應(yīng)用于兩種類型節(jié)點(diǎn)都攜帶屬性信息的屬性二分網(wǎng)絡(luò)中。

本文在BiNE和FOBE模型的基礎(chǔ)上進(jìn)一步考慮了節(jié)點(diǎn)的屬性信息對二分網(wǎng)絡(luò)表示的影響，提出了ABNE 模型，通過該模型訓(xùn)練得到了更加全面、高效的網(wǎng)絡(luò)表示向量。

2 問題定義

2.1 相關(guān)定義

本節(jié)給出了本文工作相關(guān)的一些定義：

定義1（屬性二分網(wǎng)絡(luò)）給定屬性二分網(wǎng)絡(luò)G=(U,V,E,A)，其中U和V分別表示這兩類的集合，E是網(wǎng)絡(luò)中邊的集合，且E僅存在于節(jié)點(diǎn)集U和V之間，即E?U×V，A=AU?AV是這兩類節(jié)點(diǎn)的屬性集合。

定義2（屬性二分網(wǎng)絡(luò)表示學(xué)習(xí)）給定屬性二分網(wǎng)絡(luò)G=(U,V,E,A)，網(wǎng)絡(luò)表示的目標(biāo)是學(xué)習(xí)一個映射函數(shù)f:U?V→Rd，將圖G中的每一個節(jié)點(diǎn)映射為一個d維向量，且滿足d＜＜min(|U|,|V|)。

Fig.1 Attributed bipartite network representation learning圖1 屬性二分網(wǎng)絡(luò)表示學(xué)習(xí)

圖1 展示了一個屬性二分網(wǎng)絡(luò)表示學(xué)習(xí)的示例。該圖中左側(cè)為一個屬性二分網(wǎng)絡(luò)，其中包括網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)以及兩類節(jié)點(diǎn)的屬性信息。右側(cè)為該二分網(wǎng)絡(luò)節(jié)點(diǎn)在低維空間的表示。在拓?fù)浣Y(jié)構(gòu)上有直接連接，即存在顯式關(guān)系的節(jié)點(diǎn)對如(u2,v2)在嵌入空間中有相似的表示。節(jié)點(diǎn)對(v1,v3)雖然不存在顯式關(guān)系，但它們均與節(jié)點(diǎn)u3和u4相連，即它們存在隱式關(guān)系，因此它們在嵌入空間彼此接近。在屬性二分網(wǎng)絡(luò)中，即使節(jié)點(diǎn)u1和u4沒有直接連邊，但由于它們屬性相似因此在嵌入空間中彼此接近。

2.2 符號和解釋

為更好地描述本文方法，表1列出了主要的符號及其定義。

Table 1 Overview of main symbols表1 文中主要符號概述

3 結(jié)合屬性的二分網(wǎng)絡(luò)表示學(xué)習(xí)算法

ABNE 算法旨在結(jié)合二分網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息和節(jié)點(diǎn)的屬性信息，從而得到更加全面的網(wǎng)絡(luò)表示結(jié)果。為了實現(xiàn)這一目的，本文考慮從屬性二分網(wǎng)絡(luò)的顯式關(guān)系和隱式關(guān)系兩方面進(jìn)行建模，并將屬性信息融合進(jìn)對隱式關(guān)系的建模當(dāng)中。具體來說，將有連邊的節(jié)點(diǎn)對分解為同類型鄰居節(jié)點(diǎn)間的間接關(guān)系集，通過最小化經(jīng)驗分布和概率分布之間的KL散度（Kullback-Leibler divergence）來嵌入顯式關(guān)系。由于隱式關(guān)系存在于由二分網(wǎng)絡(luò)分離出的兩個同質(zhì)網(wǎng)絡(luò)，因此需要先將原二分網(wǎng)絡(luò)轉(zhuǎn)化為兩個同質(zhì)網(wǎng)絡(luò)。對隱式關(guān)系建模分為三步：首先將攜帶屬性的二分網(wǎng)絡(luò)轉(zhuǎn)化為兩個屬性同質(zhì)網(wǎng)絡(luò)；其次分別在兩個屬性同質(zhì)網(wǎng)絡(luò)上運(yùn)用余弦相似度得到兩個屬性相似度矩陣，再結(jié)合屬性相似度矩陣和同質(zhì)網(wǎng)絡(luò)權(quán)重矩陣得到兩個新的同質(zhì)網(wǎng)絡(luò)權(quán)重矩陣；最后在這兩個新的同質(zhì)網(wǎng)絡(luò)上進(jìn)行有偏隨機(jī)游走捕獲隱式連接關(guān)系。在完成對顯式關(guān)系和結(jié)合屬性信息的隱式關(guān)系建模后，提出了一個聯(lián)合優(yōu)化框架學(xué)習(xí)得到最終的節(jié)點(diǎn)表示。本章將按照這個順序介紹ABNE算法。

3.1 顯式關(guān)系建模

二分網(wǎng)絡(luò)由兩種不同類型的節(jié)點(diǎn)構(gòu)成，不同類型的節(jié)點(diǎn)意味著不同的對象、概念和關(guān)系[27]。文獻(xiàn)[17]對于電影-觀眾二分網(wǎng)絡(luò)的研究表明，強(qiáng)制直接嵌入電影和觀眾兩類節(jié)點(diǎn)的相似性會侵蝕特定類型節(jié)點(diǎn)集的特征，從而降低下游任務(wù)性能。因此，本文方法并不是直接加強(qiáng)不同類型節(jié)點(diǎn)的相似性，而是加強(qiáng)相同類型節(jié)點(diǎn)之間的相似性對顯式關(guān)系進(jìn)行建模。具體地：

在二分網(wǎng)絡(luò)中，節(jié)點(diǎn)ui和節(jié)點(diǎn)vj的經(jīng)驗概率為：

其中，wij為邊eij的權(quán)重。顯然，如果兩個節(jié)點(diǎn)之間邊的權(quán)值越大，它們同時出現(xiàn)的概率就會越大。

對于直接相連的ui和vj，定義它們之間的相似性為兩個節(jié)點(diǎn)與彼此鄰居節(jié)點(diǎn)的內(nèi)積經(jīng)過Sigmoid函數(shù)激活后的均值的乘積，則ui和vj之間的聯(lián)合概率分布為：

其中，Dui、Γ(ui)分別表示節(jié)點(diǎn)ui的度和與ui連接的節(jié)點(diǎn)v的集合，Dvj、Γ(vj)分別表示節(jié)點(diǎn)vj的度和與vj相連的節(jié)點(diǎn)u的集合。

為了在低維空間保持節(jié)點(diǎn)的顯式關(guān)系，采用最小化這兩種分布的KL散度來學(xué)習(xí)節(jié)點(diǎn)的表示向量，即最小化以下目標(biāo)函數(shù)：

忽略掉一些無關(guān)約束得到：

3.2 結(jié)合屬性信息的隱式關(guān)系建模

隱式關(guān)系存在于由二分網(wǎng)絡(luò)分離出的兩個同質(zhì)網(wǎng)絡(luò)。此時，學(xué)習(xí)隱式關(guān)系這一目標(biāo)轉(zhuǎn)化為學(xué)習(xí)兩個屬性同質(zhì)網(wǎng)絡(luò)的表示。

首先，將原二分網(wǎng)絡(luò)轉(zhuǎn)化為兩個同質(zhì)網(wǎng)絡(luò)。根據(jù)Co-HITS（co-hyperlink-induced topic search）[28]，定義兩個同質(zhì)網(wǎng)絡(luò)的權(quán)重矩陣分別為：

本文定義節(jié)點(diǎn)集U和V的屬性相似度矩陣分別為MU和MV，并用屬性矩陣行向量的余弦相似作為其屬性相似度，即：

MAM（modified adjacency matrix）方法[29]將網(wǎng)絡(luò)的鄰接矩陣與節(jié)點(diǎn)的屬性相似性矩陣結(jié)合，創(chuàng)建了一個統(tǒng)一的相似度矩陣。參考該方法本文將屬性相似度矩陣與原同質(zhì)網(wǎng)絡(luò)的權(quán)重矩陣相加作為新的權(quán)重矩陣，即：

其中,ε為屬性相似性的權(quán)重系數(shù)，ε的大小體現(xiàn)屬性相似性對嵌入向量的重要性。該重構(gòu)網(wǎng)絡(luò)既反映結(jié)構(gòu)信息又反映屬性信息，相比原網(wǎng)絡(luò)，新權(quán)重矩陣攜帶更高的信息量，且重構(gòu)網(wǎng)絡(luò)的每個節(jié)點(diǎn)之間關(guān)系更加豐富。接著采用文獻(xiàn)[15-16]提到的方法分別在兩個同構(gòu)網(wǎng)絡(luò)上執(zhí)行有偏隨機(jī)游走，得到兩個語料庫DU和DV，并分別在兩個語料庫上執(zhí)行Skip-gram模型得到節(jié)點(diǎn)的表示向量。其目的是保留隱式關(guān)系鄰近性，該鄰近性假設(shè)中心節(jié)點(diǎn)和上下文節(jié)點(diǎn)具有更加近似的向量表示。具體來說，給出語料庫DU中一個節(jié)點(diǎn)序列S和節(jié)點(diǎn)ui，節(jié)點(diǎn)uc為節(jié)點(diǎn)ui的上下文，向量為節(jié)點(diǎn)ui作為上下文時的表示向量，對該語料庫的目標(biāo)函數(shù)為：

其中，Φ(ui)為節(jié)點(diǎn)序列S中ui的上下文節(jié)點(diǎn)。同樣，可以得到語料庫DV的目標(biāo)函數(shù)為：

根據(jù)相關(guān)的網(wǎng)絡(luò)嵌入方法[8-10]，輸入中心節(jié)點(diǎn)ui（或vj）可以得到它的上下文節(jié)點(diǎn)uc（或vc）的概率分別為：

然而，式（13）和式（14）在實際計算時有一個重要的問題，即每遍歷一個節(jié)點(diǎn)對(ui,uc)（或(vj,vc)）就需要在整個語料庫DU（或DV）上計算一次當(dāng)前中心節(jié)點(diǎn)ui（或vj）和全部詞向量的點(diǎn)積，這個計算量是非常大的。因此，本文采用負(fù)采樣[30]的思想來處理這個問題。通過負(fù)樣本的引入，目標(biāo)轉(zhuǎn)化為使正樣本Z∈Φ(ui)（或Z∈Φ(vj)）預(yù)測概率盡可能大，負(fù)樣本Z∈Ν(ui)（或Z∈Ν(vj)）的預(yù)測概率盡可能小，從而將建立在整個語料庫的多分類問題轉(zhuǎn)換成一個建模在正負(fù)樣本上的二分類問題，有效地減少了計算復(fù)雜度。局部敏感哈希[31]是高維空間中最流行的神經(jīng)網(wǎng)絡(luò)搜索算法之一。該算法背后的原理是，通過使用特定的哈希函數(shù)使得彼此接近的數(shù)據(jù)點(diǎn)集發(fā)生碰撞的概率遠(yuǎn)遠(yuǎn)大于距離較遠(yuǎn)的點(diǎn)集[31]。因此，通過局部敏感哈希算法可以得到高質(zhì)量且多樣化的負(fù)樣本。具體地，該算法先將同一類型節(jié)點(diǎn)分到不同的桶內(nèi)，并給定中心節(jié)點(diǎn)ui，再從與包含中心節(jié)點(diǎn)的桶不相同的桶內(nèi)隨機(jī)選擇ns個負(fù)樣本，該負(fù)樣本表示為N(ui)。這樣可以近似優(yōu)化目標(biāo)為：

同樣，節(jié)點(diǎn)集V的目標(biāo)函數(shù)為：

其中，條件概率P(z|ui;f)和P(z|vj;f)被定義為：

3.3 聯(lián)合表示學(xué)習(xí)模型及其優(yōu)化

為了同時保留二分網(wǎng)絡(luò)的結(jié)構(gòu)相似性和節(jié)點(diǎn)的屬性相似性，本文將嵌入二分網(wǎng)絡(luò)的顯式關(guān)系和結(jié)合屬性信息的隱式關(guān)系的目標(biāo)函數(shù)結(jié)合起來，形成一個聯(lián)合優(yōu)化框架：

其中，參數(shù)α和β為超參數(shù)，調(diào)節(jié)α和β的大小以適應(yīng)不同的網(wǎng)絡(luò)。具體來說，α越大，也就意味著二分網(wǎng)絡(luò)的隱式關(guān)系對節(jié)點(diǎn)表示學(xué)習(xí)的影響越大，β越大，則表示二分網(wǎng)絡(luò)的顯式關(guān)系對節(jié)點(diǎn)表示學(xué)習(xí)的影響越大。

ABNE算法的目標(biāo)是最大化式（19），由于該目標(biāo)函數(shù)是非凸的，求梯度為0得到的點(diǎn)并不能判別其是否是全局最優(yōu)，同時為了避免由訓(xùn)練集規(guī)模加大使訓(xùn)練過程變得異常緩慢這一問題，本文采用隨機(jī)梯度上升算法（stochastic gradient ascent algorithm，SGA）[15-16]優(yōu)化攜帶網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)和節(jié)點(diǎn)屬性信息的目標(biāo)函數(shù)。隨機(jī)梯度上升算法每次采用一個樣本更新目標(biāo)，相比于梯度上升算法每更新一次就需要用到所有的樣本的方式，大大加快了訓(xùn)練速度。具體步驟如下：

步驟1對于隨機(jī)的顯式連接關(guān)系，利用SGA 來最大化F1=-βO1，ui、vj和uk、vk的更新公式如下：

步驟2給定中心節(jié)點(diǎn)ui（或vj），采用SGA最大化F2=α(lnO2+lnO3),從而可以嵌入節(jié)點(diǎn)的隱式關(guān)系。具體來說，給定ui（或v j）作為中心節(jié)點(diǎn)及它的上下文節(jié)點(diǎn)uc（或vc），ui、vj和、的更新公式如下：

其中，I(z,ui)是一個指標(biāo)函數(shù)，它判斷節(jié)點(diǎn)z是否是節(jié)點(diǎn)ui的上下文，指標(biāo)函數(shù)I(z,ui)的形式如式（28），指標(biāo)函數(shù)I(z,vj)具有相似的意義。

3.4 聯(lián)合表示學(xué)習(xí)算法流程及復(fù)雜度分析

本文提出的ABNE算法流程如下：

算法1ABNE算法

輸入：屬性二分網(wǎng)絡(luò)G=(U,V,E,A)，網(wǎng)絡(luò)的權(quán)重矩陣W，窗口大小ws，負(fù)樣本個數(shù)ns，表示向量維度d，每個節(jié)點(diǎn)行走的最大次數(shù)maxγ，每個節(jié)點(diǎn)最小的行走次數(shù)minγ，隨機(jī)游走停止概率p。

輸出：網(wǎng)絡(luò)節(jié)點(diǎn)表示矩陣U和V。

1.根據(jù)式（7）、式（8）計算屬性相似度矩陣MU、MV；

2.根據(jù)式（9）、式（10）計算同質(zhì)網(wǎng)絡(luò)新的權(quán)重矩陣LU、LV；

3.初始化節(jié)點(diǎn)的表示向量矩陣U和V；

4.初始化上下文向量和；

5.DU=隨機(jī)游走(LU,U,maxγ,minγ,p)；

6.DV=隨機(jī)游走(LV,V,maxγ,minγ,p)；

7.對于直接連接的邊(ui,vj)∈E執(zhí)行

8.找出節(jié)點(diǎn)ui的鄰域Γ(ui)；

9.找出節(jié)點(diǎn)vj的鄰域Γ(vj)；

10.根據(jù)式（20）和式（21）更新ui和vj；

11.根據(jù)式（22）和式（23）更新uk和vk；

12.對于序列S∈DU中的每一個節(jié)點(diǎn)對(ui,uc)執(zhí)行

13.對節(jié)點(diǎn)ui進(jìn)行負(fù)采樣生成ns個負(fù)樣本Φ(ui)；

14.根據(jù)式（24）和式（26）更新ui和；

15.對于序列S∈DV中的每一個節(jié)點(diǎn)對(vj,vc)執(zhí)行

16.對節(jié)點(diǎn)vj進(jìn)行負(fù)采樣生成ns個負(fù)樣本Φ(vj)；

17.根據(jù)式（25）和式（27）更新uk和；

18.返回網(wǎng)絡(luò)節(jié)點(diǎn)的表示矩陣U和V

由上面的分析可以看出，ABNE算法的時間復(fù)雜度主要取決生成語料庫和聯(lián)合模型優(yōu)化和的計算。bs是從每個節(jié)點(diǎn)開始的行走次數(shù)，其中minγ≤bs≤maxγ，則生成語料庫的復(fù)雜度為2|E|×bs×2ws，本文中ns代表為每個節(jié)點(diǎn)生成的負(fù)樣本的數(shù)量，則本文算法整體的時間復(fù)雜度為O(2|E|×bs×2ws(1+ns))。

4 實驗結(jié)果及分析

4.1 實驗數(shù)據(jù)集

本文選取了4 個公開的真實網(wǎng)絡(luò)作為實驗數(shù)據(jù)集進(jìn)行實驗仿真，其統(tǒng)計數(shù)據(jù)如表2所示。

Table 2 Datasets for real networks表2 真實網(wǎng)絡(luò)數(shù)據(jù)集

數(shù)據(jù)集的具體介紹如下：

Yelp數(shù)據(jù)集（http://www.yelp.com/dataset-challenge）的連邊表示用戶對商家的評分，該數(shù)據(jù)集由8 136位用戶、7 903 個商家、31 746 條評分構(gòu)成，評分從1～5不等。此外，該數(shù)據(jù)集還包括用戶和商家的屬性信息，本文對屬性信息采用獨(dú)熱編碼（One-Hot 編碼），則每位用戶的點(diǎn)贊信息屬性被表示為一個11維二進(jìn)制的向量，每個商家的類別和所在城市屬性被表示為一個558維的向量表示。Douban Book數(shù)據(jù)集（http://book.douban.com/）的連邊表示用戶對書籍的評分情況，該數(shù)據(jù)集由7 230位用戶、9 707部電影、23 750條評分構(gòu)成，評分從1～5 不等，用戶所屬團(tuán)體作為用戶的屬性信息，由一個2 936 維的向量表示，書籍的出版商和年份作為書籍的兩種屬性信息，由一個1 879維的向量表示。Douban Movie 數(shù)據(jù)集（http://movie.douban.com/）的連邊表示用戶對電影的評分情況，該數(shù)據(jù)集由7 189 位用戶、6 057 部電影、53 409 條評分構(gòu)成，評分從1～5 不等，用戶所屬團(tuán)體作為用戶的屬性信息，由一個2 753維的向量表示，電影類型作為電影的屬性信息，由一個38 維的向量表示。Movielens數(shù)據(jù)集（https://grouplens.org/datasets/movielens/）的連邊表示用戶對電影的評分，該數(shù)據(jù)集由943 位用戶、1 682部電影和10 000條評分構(gòu)成，評分從1～5不等，用戶的年齡段和職業(yè)作為用戶的兩種屬性信息，由一個29 維的向量表示，電影類型作為電影的屬性信息，由一個19維的向量表示。

此外，本文還分別計算了以上4個數(shù)據(jù)集的密度和不同類型節(jié)點(diǎn)集的平均度，計算結(jié)果顯示這4個數(shù)據(jù)集的密度有很大的差異，其中Douban Book和Yelp數(shù)據(jù)集最為稀疏，其次是Douban Movie 數(shù)據(jù)集，而Movielens數(shù)據(jù)集更密集。

4.2 對比算法及參數(shù)設(shè)置

DeepWalk/Node2vec：該方法在網(wǎng)絡(luò)上執(zhí)行有偏隨機(jī)游走來產(chǎn)生節(jié)點(diǎn)的路徑，然后使用Skip-gram 模型訓(xùn)練得到網(wǎng)絡(luò)的低維嵌入向量空間。實驗中參數(shù)設(shè)置為：從每個節(jié)點(diǎn)開始的行走次數(shù)w=10，節(jié)點(diǎn)序列長度l=80，窗口大小ws=10，參數(shù)p=q=0.25（僅用于Node2vec算法）。

LINE：本文與同時考慮一階相似度和二階相似度的LINE（1st+2nd）算法作對比。實驗中設(shè)置負(fù)樣本個數(shù)ns=5。

BiNE：該算法通過聯(lián)合優(yōu)化顯式關(guān)系模型和隱式關(guān)系模型得到了網(wǎng)絡(luò)的低維向量表示。實驗參數(shù)如下值：隱式關(guān)系權(quán)重系數(shù)α=β=0.01，顯示關(guān)系權(quán)重系數(shù)γ=0.1，隨機(jī)游走窗口大小ws=5，隨機(jī)游走停止概率p=0.15，負(fù)樣本個數(shù)ns=4。

為了保證實驗的公平性，節(jié)點(diǎn)的表示向量維度均選取為d=128。另外，本文算法ABNE 的主要參數(shù)設(shè)置為：隱式關(guān)系權(quán)重系數(shù)α=0.01，顯式關(guān)系權(quán)重系數(shù)β=1，屬性相似性權(quán)重系數(shù)ε=10，其他超參數(shù)參照文獻(xiàn)[15-16]的設(shè)置。

4.3 推薦任務(wù)實驗結(jié)果

本文將得到的節(jié)點(diǎn)表示向量用于推薦任務(wù)，以評價算法性能，實驗中對4 個數(shù)據(jù)集運(yùn)用相同的設(shè)置。本文隨機(jī)抽取60%的邊作為訓(xùn)練數(shù)據(jù)，余下40%的邊進(jìn)行測試。對于每個用戶，對其測試集中的所有對象進(jìn)行排序，并對排序列表前十位進(jìn)行評估。評價指標(biāo)為：F1 分?jǐn)?shù)（F1-score）、MRR（mean reciprocal rank）、歸一化折損累計增益（normalized discounted cumulative gain，NDCG）和平均準(zhǔn)確率（mean average precision，MAP）。

表3、表4、表5 和表6 分別記錄了ABNE 和其他對比方法在4個數(shù)據(jù)集上的實驗性能。結(jié)果顯示，本文算法ABNE明顯優(yōu)于為同質(zhì)網(wǎng)絡(luò)設(shè)計的3種模型，證明了同質(zhì)網(wǎng)絡(luò)上的表示學(xué)習(xí)算法并不適用于二分網(wǎng)絡(luò)。此外，本文方法ABNE在Yelp數(shù)據(jù)集、Douban Book 數(shù)據(jù)集和Douban Movie 數(shù)據(jù)集上的性能均優(yōu)于僅利用網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)的BiNE 算法，且在Yelp 和Douban Book數(shù)據(jù)集上的改進(jìn)更為明顯，在邊密集的Movielens數(shù)據(jù)集上，ABNE的MRR值較BiNE提高了5.09個百分點(diǎn)，其他3個指標(biāo)略低于BiNE。顯然，本文的模型顯著地改進(jìn)了拓?fù)浣Y(jié)構(gòu)稀疏的二分網(wǎng)絡(luò)上的推薦結(jié)果。

Table 3 Top-10 recommendation performance on Yelp表3 Yelp數(shù)據(jù)集上的Top-10推薦結(jié)果 %

Table 4 Top-10 recommendation performance on Douban Book表4 Douban Book數(shù)據(jù)集上的Top-10推薦結(jié)果%

Table 5 Top-10 recommendation performance on Douban Movie表5 Douban Movie數(shù)據(jù)集上的Top-10推薦結(jié)果%

Table 6 Top-10 recommendation performance on Movielens表6 Movielens數(shù)據(jù)集上的Top-10推薦結(jié)果 %

為了更加明確地說明加強(qiáng)不同類型節(jié)點(diǎn)之間關(guān)系的作用和屬性信息對于網(wǎng)絡(luò)結(jié)構(gòu)的有效性，基于推薦任務(wù)的實驗結(jié)果，分別在4.4 節(jié)和4.5 節(jié)對這兩部分進(jìn)行了詳細(xì)的說明。

4.4 加強(qiáng)相同類型節(jié)點(diǎn)相似性嵌入顯示關(guān)系的作用

為了證明加強(qiáng)相同類型節(jié)點(diǎn)相似性嵌入隱式關(guān)系對二分網(wǎng)絡(luò)表示學(xué)習(xí)的重要性，本文將ABNE算法與加強(qiáng)不同類型節(jié)點(diǎn)之間關(guān)系的BiNE 算法的結(jié)果進(jìn)行比較，為了保證比較的公平性，設(shè)置ABNE 算法的屬性相似性權(quán)重系數(shù)ε=0。由于空間限制，此處只選用兩個算法的MRR@10和NDCG@10結(jié)果進(jìn)行比較。表7 的結(jié)果顯示，在最稀疏的Yelp 和Douban Book 數(shù)據(jù)集上，本文算法ABNE 的結(jié)果明顯優(yōu)于BiNE；在Movielens 數(shù)據(jù)集上，ABNE 的MRR 值較BiNE提高了4.11個百分點(diǎn)。以上結(jié)果說明了對于非常稀疏的二分網(wǎng)絡(luò)，加強(qiáng)相同類型節(jié)點(diǎn)的相似性是很有必要的，因此ABNE算法適用于或因大量缺失數(shù)據(jù)而導(dǎo)致拓?fù)浣Y(jié)構(gòu)稀疏的現(xiàn)實網(wǎng)絡(luò)中。

Table 7 Comparison of explicit relations modeling between ABNE and BiNE表7 ABNE算法與BiNE算法顯示關(guān)系建模比較%

4.5 屬性信息的有效性

為了證明屬性相似性對二分網(wǎng)絡(luò)節(jié)點(diǎn)表示學(xué)習(xí)的積極作用，本文將ABNE算法與屬性相似性權(quán)重系數(shù)ε設(shè)置為0時的MRR@10和NDCG@10結(jié)果進(jìn)行比較，表8結(jié)果顯示在4個數(shù)據(jù)集上結(jié)合屬性信息的結(jié)果均優(yōu)于忽略屬性信息的結(jié)果。因此，本文提出的結(jié)合屬性信息的二分網(wǎng)絡(luò)表示學(xué)習(xí)方法對拓?fù)浣Y(jié)構(gòu)起到了有效的補(bǔ)充。

Table 8 ABNE with and without attribute information表8 ABNE算法結(jié)合屬性和忽略屬性信息 %

4.6 參數(shù)敏感性分析

本節(jié)研究模型中主要參數(shù)的敏感性，包括隱式關(guān)系權(quán)重系數(shù)α，顯式關(guān)系權(quán)重系數(shù)β和屬性相似性權(quán)重系數(shù)ε。除了要測試的參數(shù)外，其他參數(shù)都采用默認(rèn)值。

本文通過在Douban Movie數(shù)據(jù)集上進(jìn)行的推薦任務(wù)對這3個參數(shù)進(jìn)行了分析。實驗設(shè)置隱式關(guān)系權(quán)重系數(shù)α分別為0.001、0.01、0.1、1、10 和100，顯式關(guān)系權(quán)重系數(shù)β分別為0.001、0.01、0.1、1和10，屬性相似性權(quán)重系數(shù)ε分別為0.01、0.1、1、10 和100 來研究這些參數(shù)對模型性能的影響。圖2、圖3 和圖4 分別記錄了不同參數(shù)下模型性能的變化。

Fig.2 Influence of α圖2 參數(shù)α 的影響

Fig.3 Influence of β圖3 參數(shù)β 的影響

Fig.4 Influence of ε圖4 參數(shù)ε 的影響

從圖2和圖3中可以觀察到，隨著顯式關(guān)系權(quán)重系數(shù)β的增加，模型性能逐漸增加，在β=1 時達(dá)到最優(yōu)，當(dāng)隱式關(guān)系權(quán)重系數(shù)α很大時模型性能降低，說明對于二分網(wǎng)絡(luò)，過分地強(qiáng)調(diào)隱式關(guān)系會導(dǎo)致表示向量的低效性。本文的屬性相似性權(quán)重系數(shù)ε會受到隱式關(guān)系權(quán)重系數(shù)α的影響，圖4顯示了在隱式關(guān)系權(quán)重系數(shù)α為默認(rèn)值的情況下，隨著屬性相似性權(quán)重系數(shù)ε的增加，性能指標(biāo)先增加，在ε=10 達(dá)到最優(yōu)，說明節(jié)點(diǎn)的屬性信息對二分網(wǎng)絡(luò)稀疏的拓?fù)浣Y(jié)構(gòu)起到了有效的補(bǔ)充。此外，可以觀察到使模型性能達(dá)到最優(yōu)的β值大于使性能達(dá)到最優(yōu)的α值，說明對于二分網(wǎng)絡(luò)表示學(xué)習(xí)，顯式關(guān)系比隱式關(guān)系更重要。

5 結(jié)束語

本文提出了一種結(jié)合屬性信息的二分網(wǎng)絡(luò)表示學(xué)習(xí)方法，該算法考慮從顯示關(guān)系和結(jié)合屬性信息的隱式關(guān)系兩方面學(xué)習(xí)網(wǎng)絡(luò)表示，首先借助同類型節(jié)點(diǎn)的相似性對顯式關(guān)系建立模型，其次將屬性信息作為隱式關(guān)系的補(bǔ)充并對其建立模型，最后提出一個聯(lián)合優(yōu)化框架，得到了融合了網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)信息和節(jié)點(diǎn)的屬性信息的網(wǎng)絡(luò)表示。在4 個真實網(wǎng)絡(luò)上的推薦實驗結(jié)果證明了ABNE算法的有效性。

由于大規(guī)?，F(xiàn)實網(wǎng)絡(luò)中節(jié)點(diǎn)的屬性相似性矩陣往往隨著節(jié)點(diǎn)的增加成為一個高維度稠密矩陣，這樣給計算帶來了很大空間復(fù)雜度，因此，在未來的工作中如何進(jìn)一步處理屬性信息指導(dǎo)網(wǎng)絡(luò)表示學(xué)習(xí)是一大挑戰(zhàn)。