基于節(jié)點(diǎn)相似度的無監(jiān)督屬性圖嵌入模型

李 揚(yáng)，吳安彪，袁 野，趙琳琳，王國(guó)仁

（1.東北大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，沈陽(yáng) 110169；2.北京理工大學(xué)計(jì)算機(jī)學(xué)院，北京 100081）

0 引言

圖，也叫網(wǎng)絡(luò)，作為一種常見的數(shù)據(jù)結(jié)構(gòu)，廣泛地出現(xiàn)在人們的日常生活中，例如社交網(wǎng)絡(luò)、萬維網(wǎng)等。在大數(shù)據(jù)時(shí)代，圖已經(jīng)成為有效存儲(chǔ)和建模實(shí)體關(guān)系的重要媒介。在各種圖中，屬性圖引發(fā)了很多關(guān)注，屬性圖不僅保留了節(jié)點(diǎn)間的拓?fù)浣Y(jié)構(gòu)，而且還具有豐富的屬性信息。在實(shí)際應(yīng)用中，屬性信息在許多任務(wù)中起著重要作用。例如，在社交網(wǎng)絡(luò)中，用戶是否要購(gòu)買某產(chǎn)品不僅與他的社交狀況有關(guān)，而且與用戶最近的購(gòu)買記錄密切相關(guān)。此外，有關(guān)社會(huì)科學(xué)的一些相關(guān)研究還表明，節(jié)點(diǎn)的屬性可以反映和影響其社區(qū)結(jié)構(gòu)［1］。因此，關(guān)于屬性圖的研究是必要且有意義的。

許多屬性圖嵌入工作（例如圖卷積網(wǎng)絡(luò)（Graph Convolutional Network，GCN）［2］）都取得了巨大的成功，可以利用它們?nèi)ソ鉀Q多數(shù)圖上的深度學(xué)習(xí)問題。半監(jiān)督算法在保證實(shí)驗(yàn)效果的基礎(chǔ)上極大減少了需要標(biāo)記數(shù)據(jù)的數(shù)量，這是一個(gè)巨大的進(jìn)步。但是在大數(shù)據(jù)時(shí)代，圖的規(guī)模非常大，具有十億個(gè)節(jié)點(diǎn)的大圖并不少見。以一個(gè)有十億個(gè)節(jié)點(diǎn)的圖為例，按照文獻(xiàn)［2］中最低的標(biāo)記率0.001 計(jì)算，需要標(biāo)記一百萬個(gè)節(jié)點(diǎn)。而且，由于數(shù)據(jù)標(biāo)記率如此低，無法保證在圖上進(jìn)行的各種下游任務(wù)都能取得良好的效果。因此，需要在大圖上標(biāo)記的數(shù)據(jù)量很大。與此同時(shí)，數(shù)據(jù)標(biāo)注的難度很高。以上情況導(dǎo)致標(biāo)注過程會(huì)消耗大量的人力物力，一定程度上阻礙了有監(jiān)督或半監(jiān)督圖嵌入算法的實(shí)際應(yīng)用。

而且，許多現(xiàn)有的屬性圖嵌入方法是端到端的。輸入是圖中節(jié)點(diǎn)的特征，輸出是下游任務(wù)的最終結(jié)果。換句話說，端到端算法所得到的嵌入向量是與標(biāo)簽相關(guān)的。標(biāo)簽是依賴于專家或經(jīng)驗(yàn)標(biāo)注的，如果基于經(jīng)驗(yàn)的數(shù)據(jù)標(biāo)注出現(xiàn)問題，將會(huì)對(duì)最終結(jié)果產(chǎn)生影響。同時(shí)，端到端算法違背了圖嵌入的初衷。圖嵌入的目的是將圖中的每個(gè)節(jié)點(diǎn)都表示為低維向量，并使用該向量執(zhí)行一系列下游任務(wù)。端到端使嵌入變得不可見。當(dāng)下游任務(wù)發(fā)生變化時(shí)，需要調(diào)整整個(gè)模型。在實(shí)際應(yīng)用中，圖上的任務(wù)往往不是單一的，在滿足各種任務(wù)的同時(shí)需要調(diào)整整個(gè)模型所需的代價(jià)使得端到端算法會(huì)消耗更多的成本。

諸如GCN 一類的屬性圖嵌入方法更加關(guān)注節(jié)點(diǎn)的屬性信息?，F(xiàn)有的圖嵌入理論認(rèn)為，圖上的信息主要包括拓?fù)湫畔ⅲɡ缒男┕?jié)點(diǎn)是該節(jié)點(diǎn)的鄰居）和屬性信息（例如節(jié)點(diǎn)的特征）。GCN 一類方法的思想是沿圖上的路徑傳播屬性。與屬性信息相比，拓?fù)湫畔⒃贕CN 的輸出中反映較少，靈活地調(diào)整屬性信息和拓?fù)湫畔?duì)嵌入的影響是必要的。

為了解決上述問題，本文提出了一種無監(jiān)督的兩階段模型：第一階段將已存在的無屬性圖嵌入方法（以DeepwalkDeepWalk 為例）作用在屬性圖上得到包含拓?fù)湫畔⒌那度胂蛄?，利用該向量可以得到屬性圖的拓?fù)湎嗨贫染仃?，并利用屬性圖的屬性得到屬性相似度矩陣，第二階段利用已存在的屬性圖嵌入方法（以GCN 為例）作用在屬性圖上得到低維向量，利用該向量得到的相似度矩陣以及第一階段已經(jīng)得到的拓?fù)湎嗨贫染仃嚭蛯傩韵嗨贫染仃囉?jì)算損失，從而反向更新GCN 的權(quán)重，最終得到屬性圖的嵌入向量。本質(zhì)上，本文方法是提取圖中節(jié)點(diǎn)之間的拓?fù)湎嗨贫群蛯傩韵嗨贫龋缓蠡谶@些相似度嵌入節(jié)點(diǎn)，并通過現(xiàn)有的無屬性圖嵌入方法和屬性圖嵌入方法來學(xué)習(xí)這種嵌入。更具體地說，本文的主要工作如下：

1）提出了一種無監(jiān)督的屬性圖嵌入方法。與現(xiàn)有的有監(jiān)督和半監(jiān)督方法不同，該方法可以在不依賴任何標(biāo)簽的情況下使圖中的每個(gè)節(jié)點(diǎn)獲得相應(yīng)的嵌入向量。

2）設(shè)計(jì)了一個(gè)損失函數(shù)，該函數(shù)是屬性信息與嵌入向量信息差值以及拓?fù)湫畔⑴c嵌入向量信息差值的和，通過調(diào)整這兩項(xiàng)的權(quán)重可以靈活地調(diào)整屬性和拓?fù)浣Y(jié)構(gòu)對(duì)嵌入向量的影響，并最終使得到的嵌入向量盡可能地保留拓?fù)浜蛯傩孕畔ⅰ?/p>

3）在真實(shí)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，評(píng)估本文所提出的方法。實(shí)驗(yàn)結(jié)果表明，在沒有任何標(biāo)簽的情況下，該方法就可以實(shí)現(xiàn)優(yōu)異的性能。

1 相關(guān)工作

圖嵌入是一個(gè)熱門的研究方向，在此方向上已經(jīng)有一系列的經(jīng)典工作。下面將從圖嵌入和屬性圖嵌入兩方面來介紹相關(guān)工作。

1.1 圖嵌入

大多數(shù)圖嵌入方法屬于以下三類：基于分解的方法、基于隨機(jī)游走的方法、基于深度學(xué)習(xí)的方法。

基于分解的方法受矩陣分解方法的啟發(fā)，該方法假定數(shù)據(jù)位于低維流形。拉普拉斯特征圖（Laplacian Eigenmaps，LE）［3］和局部保留投影（Locality Preserving Projections，LPP）算法［4］依靠特征分解來保留局部流形結(jié)構(gòu)。由于特征分解操作代價(jià)高昂，這些方法在處理大規(guī)模圖時(shí)面臨困難。為了緩解這個(gè)問題，已經(jīng)提出了幾種方法，有代表性的是圖分解（Graph Factorization，GF）［5］、GraRep（Graph Representation）［6］和HOPE（High-Order Proximity Preserved Embedding）［7］。這些方法的主要區(qū)別在于它們所采用的節(jié)點(diǎn)相似度計(jì)算方法。GF 直接從鄰接矩陣中提取一階鄰近度來計(jì)算節(jié)點(diǎn)相似度，而GraRep 和HOPE 分別利用鄰接矩陣和相似度度量（即余弦相似度）的不同冪獲得高階鄰近度以捕獲更準(zhǔn)確的節(jié)點(diǎn)相似度。

基于隨機(jī)游走的方法假定如果一對(duì)節(jié)點(diǎn)經(jīng)常同時(shí)出現(xiàn)在圖的模擬隨機(jī)游走的路徑中，那么這對(duì)節(jié)點(diǎn)很相似。因此與基于因式分解的方法所使用的確定性方法相比，節(jié)點(diǎn)相似性的計(jì)算更加隨機(jī)。DeepWalk［8］和node2vec［9］是該類方法中較為成功的方法，它們的區(qū)別在于隨機(jī)游走的方式不同。DeepWalk 模擬均勻的隨機(jī)游走，而node2vec 依賴于有偏的隨機(jī)游走。Perozzi 等［10］擴(kuò)展了DeepWalk 在圖中編碼了多尺度的節(jié)點(diǎn)關(guān)系。與DeepWalk 和node2vec 將節(jié)點(diǎn)嵌入到歐幾里得空間不同，Chamberlain 等［11］將節(jié)點(diǎn)嵌入到雙曲空間。

基于分解和隨機(jī)游走的方法往往采用淺層模型，這導(dǎo)致其捕獲復(fù)雜圖結(jié)構(gòu)的能力嚴(yán)重不足。為了解決這個(gè)問題，一些研究人員引入了深度學(xué)習(xí)技術(shù)。Tian 等［12］提出了一個(gè)堆疊的稀疏自編碼器通過重構(gòu)鄰接矩陣來嵌入節(jié)點(diǎn)。Wang等［13］提出了一個(gè)堆疊的自編碼器，其通過使用一階鄰近度作為正則項(xiàng)來重構(gòu)二階鄰近度。Cao 等［14］使用堆疊的去噪自編碼器來重構(gòu)互信息矩陣。

盡管大部分圖嵌入方法都屬于上述三種類型，但仍有例外 。例 如，LINE（Large-scale Information Network Embedding）［15-16］是一個(gè)成功的淺層嵌入方法，其通過保存圖的局部和全局結(jié)構(gòu)來獲得嵌入。

1.2 屬性圖嵌入

1.1 節(jié)中描述的圖嵌入方法僅利用圖的結(jié)構(gòu)來學(xué)習(xí)節(jié)點(diǎn)表示，但是現(xiàn)實(shí)世界圖中的節(jié)點(diǎn)通常帶有一組豐富的屬性，為了利用節(jié)點(diǎn)特征，已經(jīng)提出了許多屬性圖嵌入方法，這些方法分為兩大類：有監(jiān)督方法和無監(jiān)督方法。

有監(jiān)督的屬性圖嵌入通過利用標(biāo)簽信息來嵌入節(jié)點(diǎn)。例如，Huang 等［17］提出了一種利用頻譜技術(shù)將鄰接矩陣、節(jié)點(diǎn)特征矩陣和節(jié)點(diǎn)標(biāo)簽矩陣映射到同一個(gè)向量空間中的監(jiān)督方法。Hamilton 等［18］提出了GraphSAGE（Graph Sample and AGgrEgate）的四個(gè)變體，這是一種以歸納方式計(jì)算節(jié)點(diǎn)嵌入的框架。許多方法使用部分標(biāo)簽信息來處理圖。例如，GCN［2］將頻譜卷積合并到神經(jīng)網(wǎng)絡(luò)中。圖注意力網(wǎng)絡(luò)（Graph ATtention network，GAT）［19］利用注意力機(jī)制來確定相鄰節(jié)點(diǎn)在最終節(jié)點(diǎn)表示中的影響。

無監(jiān)督的屬性圖嵌入方法可解決缺少標(biāo)簽信息的問題，這種情況在許多實(shí)際應(yīng)用中都存在。Yang 等［20］和Huang等［21］提出了矩陣分解的方法來結(jié)合圖的結(jié)構(gòu)信息和節(jié)點(diǎn)的屬性信息。此外Kipf 等［22］提出了兩種利用圖卷積網(wǎng)絡(luò)的圖自動(dòng)編碼器（Graph Auto-Encoder，GAE）。Pan 等［23］還介紹了一種基于對(duì)抗方法的圖形編碼器。對(duì)于圖聚類，Wang 等［24］提出了一種圖形自動(dòng)編碼器，它能夠重構(gòu)節(jié)點(diǎn)特征；然而，這種自編碼器只能重構(gòu)圖的結(jié)構(gòu)或圖的屬性而不能同時(shí)重構(gòu)兩者。Gao 等［25］提出了一個(gè)框架，該框架由兩個(gè)常規(guī)的自動(dòng)編碼器組成，它們分別重構(gòu)了圖的結(jié)構(gòu)和節(jié)點(diǎn)的屬性。

2 問題定義

本章介紹論文中所使用的主要變量，以及屬性圖嵌入問題的相關(guān)定義。表1 總結(jié)了文中所使用的主要變量。

表1 主要變量Tab.1 Main parameters

定義1屬性圖。屬性圖是一種數(shù)據(jù)結(jié)構(gòu)，可以表示為G={V，E，A}，其中V={v1，v2，…，vn}表示圖中的|V|個(gè)節(jié)點(diǎn)組成的集合，E表示節(jié)點(diǎn)之間的邊的集合。A∈R|V|×m表示節(jié)點(diǎn)的屬性信息，其中m是屬性向量的維數(shù)，Ai是與節(jié)點(diǎn)vi對(duì)應(yīng)的屬性向量（例如，社交網(wǎng)絡(luò)中用戶的年齡和性別或蛋白質(zhì)-蛋白質(zhì)相互作用網(wǎng)絡(luò)上的蛋白質(zhì)類別）。

值得注意的是，這些屬性是來自應(yīng)用程序域的屬性。它們不是由專家手工制作或通過嵌入技術(shù)產(chǎn)生的合成特征。因此，它們不包括任何拓?fù)湫畔ⅰ?/p>

在各種應(yīng)用程序中，將屬性圖嵌入到低維向量空間中很有用。為了獲得嵌入，必須保留圖的拓?fù)浣Y(jié)構(gòu)。局部圖結(jié)構(gòu)，即兩個(gè)節(jié)點(diǎn)是否相鄰，必須在嵌入向量中得到反映。以下定義度量了兩個(gè)節(jié)點(diǎn)之間的局部結(jié)構(gòu)。

定義2一階鄰近度。圖中兩個(gè)節(jié)點(diǎn)之間的一階鄰近度是局部的成對(duì)鄰近度。對(duì)于由邊(u，v)鏈接的每對(duì)節(jié)點(diǎn)，定義u和v之間的一階鄰近度為1。如果無法觀察到u和v之間的邊，則它們的一階鄰近度為0。

一階鄰近度可以在一定程度上反映圖中兩個(gè)節(jié)點(diǎn)的相似性。例如，在網(wǎng)絡(luò)購(gòu)物平臺(tái)上彼此成為朋友的人們傾向于購(gòu)買類似的產(chǎn)品；在萬維網(wǎng)上彼此連接的用戶往往會(huì)瀏覽相似的主題。許多現(xiàn)有的嵌入方法（例如等距特征映射（Isometric feature Mapping，IsoMap）、局部線性嵌入（Locally Linear Embedding，LLE）、LE 和GF）都旨在保留一階鄰近度。

僅僅衡量?jī)蓚€(gè)節(jié)點(diǎn)是否是鄰居還遠(yuǎn)遠(yuǎn)不夠。因?yàn)樵S多節(jié)點(diǎn)不是彼此相鄰的，所以無法根據(jù)兩個(gè)節(jié)點(diǎn)是否是鄰居來確定兩個(gè)節(jié)點(diǎn)的嵌入是否相似。一種直覺是共享鄰居的節(jié)點(diǎn)也可能是相似的。例如，與某人同時(shí)成為朋友的兩個(gè)人可能具有相同的愛好，并且在社交網(wǎng)絡(luò)中更可能成為朋友；在推薦系統(tǒng)中，與某人同時(shí)是好友的兩個(gè)用戶也可能會(huì)購(gòu)買類似的產(chǎn)品。因此，一些方法還定義了二階鄰近度以保留此類信息。

定義3二階鄰近度。圖中一對(duì)節(jié)點(diǎn)(u，v)之間的二階接近度是它們的鄰居之間的相似度。即fpu=(fpu，1，fpu，2，…，fpu，u-1，fpu，u+1，…fpu，v-1，fpu，v+1，…，fpu，n-1，fpu，n)表示u與所有其他節(jié)點(diǎn)（不包括節(jié)點(diǎn)u和v）的一階鄰近度，則fpu和fpv之間的相似性決定了u和v之間的二階鄰近度。如果沒有節(jié)點(diǎn)是u和v的公共鄰居，則u和v之間的二階接近度為0。

通過保存圖中成對(duì)節(jié)點(diǎn)的拓?fù)湎嗨贫?，可以極大地保留圖中的拓?fù)湫畔ⅰ＠眠@些拓?fù)湫畔?，可以針?duì)圖中的每個(gè)節(jié)點(diǎn)生成一個(gè)低維嵌入向量。值得注意的是，這個(gè)低維嵌入向量只包含拓?fù)湫畔⒍话渌畔?。下面給出圖的拓?fù)湎嗨贫染仃嚨亩x。

定義4圖的拓?fù)湎嗨贫染仃?。圖的拓?fù)湎嗨贫染仃囀且粋€(gè)方陣，其行數(shù)和列數(shù)為圖的節(jié)點(diǎn)個(gè)數(shù)。其中的每一個(gè)位置對(duì)應(yīng)于圖中兩個(gè)節(jié)點(diǎn)之間的拓?fù)湎嗨贫?，即?/p>

其中：ST(i，j)表示第i個(gè)節(jié)點(diǎn)與第j個(gè)節(jié)點(diǎn)間的拓?fù)湎嗨贫?；表示?jié)點(diǎn)i和節(jié)點(diǎn)j的拓?fù)淝度耄弧啊ぁ北硎鞠蛄康狞c(diǎn)積；| |表示向量的范數(shù)。

定義5圖的屬性相似度矩陣。圖的屬性相似度矩陣是一個(gè)方陣，其行數(shù)和列數(shù)為圖的節(jié)點(diǎn)個(gè)數(shù)。其中的每一個(gè)位置對(duì)應(yīng)于圖中兩個(gè)節(jié)點(diǎn)之間的屬性相似度，即：

其中：SA(i，j)表示第i個(gè)節(jié)點(diǎn)與第j個(gè)節(jié)點(diǎn)間的屬性相似度；Ai和Aj表示節(jié)點(diǎn)i和節(jié)點(diǎn)j的屬性向量。

定義6圖的相似度矩陣。圖的相似度矩陣是一個(gè)方陣，其行數(shù)和列數(shù)為圖的節(jié)點(diǎn)個(gè)數(shù)。其中的每一個(gè)位置對(duì)應(yīng)于圖中兩個(gè)節(jié)點(diǎn)之間的相似度，即：

其中：S(i，j)表示第i個(gè)節(jié)點(diǎn)與第j個(gè)節(jié)點(diǎn)間的相似度；Hi和Hj表示節(jié)點(diǎn)i和節(jié)點(diǎn)j的嵌入向量。

式（1）～（3）分別定義了圖的拓?fù)湎嗨贫染仃?、屬性相似度矩陣和相似度矩陣。根?jù)上述公式計(jì)算所需的時(shí)間復(fù)雜度為O(n2)，n為節(jié)點(diǎn)的個(gè)數(shù)。在本文中不單獨(dú)針對(duì)成對(duì)節(jié)點(diǎn)計(jì)算相似度而是針對(duì)整個(gè)圖計(jì)算圖上各節(jié)點(diǎn)之間的相似度，即首先對(duì)拓?fù)淝度刖仃?、屬性矩陣、嵌入矩陣作?guī)范化，然后使用該矩陣與該矩陣的轉(zhuǎn)置作矩陣乘法，得到的結(jié)果與使用式（1）～（3）運(yùn)算結(jié)果相同。計(jì)算過程如式（4）～（6）所示：

其中，HT、A、H分別為屬性圖的拓?fù)淝度?、屬性向量和屬性圖的嵌入。、AT、HT分別為屬性圖拓?fù)淝度?、屬性向量和屬性圖嵌入的轉(zhuǎn)置。normalize()是矩陣規(guī)范化函數(shù)。

問題定義無監(jiān)督屬性圖嵌入。給定屬性圖G={V，E，A}，屬性圖嵌入旨在通過無監(jiān)督學(xué)習(xí)將節(jié)點(diǎn)vi映射成一個(gè)低維向量Hi∈Rd，且該向量可以同時(shí)保留節(jié)點(diǎn)的拓?fù)浜蛯傩孕畔?，其中d是嵌入向量的維數(shù)，d?|V|。

接下來，本文將介紹兩階段的無監(jiān)督屬性圖嵌入模型，利用該模型所得到的嵌入向量可以同時(shí)保留圖的拓?fù)浜蛯傩孕畔ⅰ?/p>

3 算法框架

一個(gè)理想的屬性圖嵌入模型需要滿足幾個(gè)要求：第一，其生成的嵌入向量必須能夠保留圖的拓?fù)湫畔ⅲ绻?jié)點(diǎn)之間的一階鄰近度或二階鄰近度；第二，其生成的嵌入向量必須保留圖的屬性信息；第三，它可以在不依賴標(biāo)簽的情況下生成嵌入，并且該嵌入向量可以保存大部分信息。在本章中，提出一個(gè)屬性圖嵌入模型，該模型可以滿足所有這三個(gè)要求。

如圖1 所示，所提模型主要分為兩階段。第一階段，利用已有的無屬性圖嵌入方法（以DeepWalk 為例）提取節(jié)點(diǎn)的拓?fù)湫畔⒑凸?jié)點(diǎn)的屬性來計(jì)算各節(jié)點(diǎn)之間的拓?fù)湎嗨贫群蛯傩韵嗨贫?。第二階段，利用現(xiàn)有的屬性圖嵌入方法（以GCN 為例）獲得屬性圖的嵌入并計(jì)算相似度矩陣，根據(jù)損失函數(shù)來更新屬性圖嵌入模型的參數(shù)，最后利用更新的參數(shù)來獲得屬性圖嵌入向量。下面，分別詳細(xì)地描述算法的兩個(gè)階段。

圖1 無監(jiān)督屬性圖嵌入模型Fig.1 Unsupervised attributed graph embedding model

3.1 拓?fù)湫畔⒑蛯傩孕畔?/h3>

由第2 章可知，圖上的拓?fù)湫畔⒑蛯傩孕畔⒖梢员华?dú)立表達(dá)，因此可以使用現(xiàn)有的無屬性圖嵌入方法來提取圖上的拓?fù)湫畔?，然后?jì)算圖的拓?fù)湎嗨贫染仃嚒?/p>

對(duì)于無屬性圖嵌入，已經(jīng)有一系列成熟的方法可用于提取圖中的局部和全局信息。這些方法主要由三類組成：基于矩陣分解的方法、基于隨機(jī)游走技術(shù)、基于深度學(xué)習(xí)的方法。其中包含一系列有影響力的方法，例如局部線性嵌入（LLE）、LE、GF、GraRep、HOPE、DeepWalk、node2vec、結(jié)構(gòu)深度網(wǎng)絡(luò)嵌入（Structural Deep Network Embedding，SDNE）、深度遞歸網(wǎng)絡(luò)嵌入（Deep Recursive Network Embedding，DRNE）、LINE 等。這些方法均可以應(yīng)用在本文框架中。在本文中，以DeepWalk 為例來獲得屬性圖的拓?fù)湎嗨贫染仃?，如算? 所示。其中，ω、d、γ、t均為DeepWalk 算法中的參數(shù)，分別為窗口大小、嵌入向量大小、每個(gè)節(jié)點(diǎn)為起點(diǎn)所走的路徑個(gè)數(shù)、路徑長(zhǎng)度。第1）～9）行為DeepWalk 算法的實(shí)現(xiàn)，第10）行是DeepWalk 算法得到的拓?fù)淝度胂蛄?，?1）行利用第10）行所得到的結(jié)果根據(jù)式（4）計(jì)算出圖的拓?fù)湎嗨贫染仃嚒Ｗ罱K，根據(jù)算法1，可得圖的拓?fù)湎嗨贫染仃嚒?/p>

算法1 Topology Similarity。

對(duì)于屬性圖的屬性信息，可以通過節(jié)點(diǎn)之間的屬性相似度來度量。算法2 展示了如何根據(jù)屬性計(jì)算屬性圖的屬性信息。經(jīng)過上述步驟可以獲得屬性圖的拓?fù)湫畔⒑蛯傩孕畔?。下面介紹如何獲得屬性圖的嵌入。

算法2 Attributed Similarity。

3.2 屬性圖嵌入模型

通過算法1 和算法2，可以得到屬性圖的拓?fù)湎嗨贫群蛯傩韵嗨贫染仃?。接下來，使用現(xiàn)有的屬性圖嵌入技術(shù)來進(jìn)行嵌入?？梢栽诖丝蚣苤惺褂玫乃惴òǖ幌抻贕CN 及其一系列變體、圖注意力網(wǎng)絡(luò)、圖自動(dòng)編碼器等。

本節(jié)以GCN 為例，下面給出GCN 模型。

GCN 模型是一個(gè)k層深度模型，可以表示為，其中W={W(1)，W(2)，…，W(k)}，通常用于節(jié)點(diǎn)的端到端學(xué)習(xí)。給定一個(gè)具有節(jié)點(diǎn)屬性和拓?fù)浣Y(jié)構(gòu)的屬性圖G，GCN 同時(shí)將這兩種類型的信息編碼為每層的隱藏特征，用作網(wǎng)絡(luò)節(jié)點(diǎn)的單獨(dú)信息 。形式上，GCN的前向傳播過程為f(k)(f(k-1)(…f(1)(G)…))。GCN 的每一層都使用了鄰居聚合函數(shù)f(·)，進(jìn)而通過前一層的特征來生成下一層的特征，如式（7）所示：

從呈現(xiàn)節(jié)點(diǎn)屬性的最低嵌入H(0)開始，模型迭代地聚合一層中每個(gè)節(jié)點(diǎn)的隱藏特征與其相鄰節(jié)點(diǎn)的特征，以在下一層H(1)中為該節(jié)點(diǎn)生成隱藏特征。依此類推（見式（7））。

通過使用上述模型可以獲得屬性圖的嵌入S，一個(gè)自然的直覺是使屬性圖的嵌入盡可能與屬性圖的拓?fù)湫畔⒑蛯傩孕畔⒁恢隆Ｒ虼?，本文提出了一種損失函數(shù)，如式（8）所示：

其中，本文設(shè)置α為超參數(shù)用以控制節(jié)點(diǎn)拓?fù)湫畔⒑蛯傩孕畔⒃趽p失函數(shù)中的比例，因?yàn)楣?jié)點(diǎn)的拓?fù)湫畔⒑蛯傩孕畔?duì)不同的數(shù)據(jù)集以及在不同的任務(wù)中影響是不同的，通過該參數(shù)可以直接控制拓?fù)湫畔⒑蛯傩孕畔?duì)于最終嵌入的生成。對(duì)于不同的任務(wù)，不同的屬性會(huì)導(dǎo)致超參數(shù)的設(shè)置有差異。這里，“‖a‖F(xiàn)”為向量a的Frob enius 范數(shù)。算法3 詳細(xì)描述了如何通過GCN 模型得到最終的嵌入向量。第1）～2）行是GCN 模型的構(gòu)建及初始化過程，以屬性圖的屬性矩陣為輸入。第3）～4）行為GCN 模型的前向傳播過程。第5）行是利用GCN 最后一層的輸出計(jì)算相似度矩陣（見式（6））。第6）行是根據(jù)相似度矩陣、拓?fù)湎嗨贫染仃?、屬性相似度矩陣和超參?shù)α來計(jì)算損失函數(shù)。第7）行是根據(jù)損失函數(shù)更新GCN 中每一層的權(quán)重W(l)。第9）～10）行，通過迭代epoch次后，確定GCN 模型中各層的權(quán)重W(l)，最后將屬性圖G輸入到已訓(xùn)練好的GCN 模型中輸出各個(gè)節(jié)點(diǎn)所對(duì)應(yīng)的嵌入向量，如式（7）所示。

算法3 Attributed graph embedding。

4 實(shí)驗(yàn)與結(jié)果分析

本章使用多個(gè)基準(zhǔn)數(shù)據(jù)集定性和定量地評(píng)估所提出的方法。

4.1 數(shù)據(jù)集及實(shí)驗(yàn)配置

本文使用3 個(gè)基準(zhǔn)數(shù)據(jù)集（Cora、Citeseer 和Pubmed［26］），它們被廣泛用于評(píng)估屬性圖嵌入方法。表2 給出了數(shù)據(jù)集的統(tǒng)計(jì)數(shù)據(jù)。

表2 數(shù)據(jù)集統(tǒng)計(jì)信息Tab.2 Dataset statistical information

在此實(shí)驗(yàn)中，使用Adam 優(yōu)化器［27］來學(xué)習(xí)模型參數(shù)，初始學(xué)習(xí)率為0.1。對(duì)于Cora 和Citeseer，超參數(shù)α設(shè)置為0.4；對(duì)于Pubmed，超參數(shù)α設(shè)置為0.5。對(duì)于Cora 和Citeseer，epoch被設(shè)置為2 500；對(duì)于Pubmed，將epoch設(shè)置為2 000。對(duì)于模型中使用的GCN，其層數(shù)設(shè)置為2，隱藏層大小為1 000，嵌入向量維數(shù)d為64。

4.2 基線方法

下面將本文提出的屬性圖嵌入方法與以下最新的有監(jiān)督和無監(jiān)督的方法進(jìn)行比較。

DeepWalk［8］：DeepWalk 是一種圖嵌入方法，可在圖上模擬隨機(jī)游走，進(jìn)而利用隨機(jī)游走得到的路徑訓(xùn)練SkipGram模型［28］。

增強(qiáng)的DeepWalk（DeepWalk+features）：此基準(zhǔn)將原始節(jié)點(diǎn)的屬性和DeepWalk 的嵌入向量連接在一起，以利用節(jié)點(diǎn)屬性。

標(biāo)簽傳播（Label Propagation，LP）［29］：LP 將圖中的可用標(biāo)簽傳播給未標(biāo)記的節(jié)點(diǎn)。

圖自動(dòng)編碼器（GAE）［22］：GAE 使用圖卷積網(wǎng)絡(luò)作為編碼器，并在編碼器中重建圖結(jié)構(gòu)。

變圖自動(dòng)編碼器（Variational Graph Auto-Encoder，VGAE）［22］：VGAE 是GAE 的變體版本。

GraphSAGE［18］：GraphSAGE 具有四個(gè)無監(jiān)督的變體，其特征聚合器分為應(yīng)用卷積樣式聚合器（GraphSAGE-GCN）、屬性向量中的元素逐項(xiàng)均值（GraphSAGE-mean）、通過將相鄰節(jié)點(diǎn)的屬性集成到LSTM 中進(jìn)行匯總（Graph Sample and AGgrEgate-Long Short-Term Memory recurrent neural network，GraphSAGE-LSTM）和在應(yīng)用全連接的神經(jīng)網(wǎng)絡(luò)后執(zhí)行逐元素最大池操作（GraphSAGE-pool）。

4.3 節(jié)點(diǎn)分類

將本文所提出的方法與上述基線在節(jié)點(diǎn)分類任務(wù)上進(jìn)行比較。DeepWalk和LP的精度可從Kipf &Welling［2］中獲取。本文還重用了Veli?kovi? 等［30］報(bào)告中的增強(qiáng)型DeepWalk 的指標(biāo)。此外，也將本文提出的方法與GAE 和VGAE 進(jìn)行了比較。

本文所提出的方法在3 個(gè)數(shù)據(jù)集上都展現(xiàn)出了良好的性能，如表3 所示。其中在Cora 和Citeseer 數(shù)據(jù)集上，此方法超過了所有基線方法，可以觀察到最佳無監(jiān)督基線方法分別提高了1.2 個(gè)百分點(diǎn)和2.4 個(gè)百分點(diǎn)；在Pubmed 數(shù)據(jù)集上，本文方法沒有超過最好的基線方法，與最好的基線方法相比，本文方法所取得的準(zhǔn)確率低0.9 個(gè)百分點(diǎn)。可以注意到，Pubmed 數(shù)據(jù)集節(jié)點(diǎn)數(shù)是Cora 數(shù)據(jù)集和Citeseer 數(shù)據(jù)集節(jié)點(diǎn)數(shù)的6～7 倍，然而，Pubmed 數(shù)據(jù)集的屬性向量長(zhǎng)度只有Cora 數(shù)據(jù)集的1/3，只有Citeseer 數(shù)據(jù)集的1/7，這意味著與前兩個(gè)數(shù)據(jù)集相比，Pubmed 數(shù)據(jù)集中的節(jié)點(diǎn)擁有更加豐富的拓?fù)湫畔⒑透迂毞Φ膶傩孕畔ⅲ瑢?dǎo)致節(jié)點(diǎn)嵌入無法均衡地表達(dá)這兩種信息，這或許是Pubmed 數(shù)據(jù)集上節(jié)點(diǎn)分類任務(wù)表現(xiàn)不佳的原因之一。

表3 不同數(shù)據(jù)集上的節(jié)點(diǎn)分類任務(wù)準(zhǔn)確率比較Tab.3 Accuracy comparison of node classification task on different datasets

此外，Cora 數(shù)據(jù)集和Citeseer 數(shù)據(jù)集與Pubmed 數(shù)據(jù)集上的超參數(shù)設(shè)置是不同的。超參數(shù)α表明拓?fù)湫畔?duì)于嵌入向量的貢獻(xiàn)程度，同樣，1-α表示屬性信息對(duì)于嵌入向量的貢獻(xiàn)程度。由4.1 節(jié)可知，Cora 和Citeseer 數(shù)據(jù)集上的超參數(shù)α設(shè)置為0.4，Pubmed 數(shù)據(jù)集上的超參數(shù)α設(shè)置為0.5。對(duì)于Pubmed 數(shù)據(jù)集上的節(jié)點(diǎn)來說，它們擁有更加豐富的拓?fù)湫畔?，因此拓?fù)湫畔?duì)于嵌入向量的貢獻(xiàn)程度被設(shè)置得更大，最終導(dǎo)致嵌入向量對(duì)于屬性信息沒有完整地表達(dá)，使得準(zhǔn)確率不高。

4.4 可視化

在可視化任務(wù)中，本文將Cora 數(shù)據(jù)集上的前400 個(gè)節(jié)點(diǎn)分別利用DeepWalk 算法所得到的嵌入向量和本文所提出的方法所得到的嵌入向量作為t-SNE（t-distributed Stochastic Neighbor Embedding）算法的輸入，映射到二維空間上，結(jié)果如圖2、3 所示。圖上的每一種圖形代表Cora 數(shù)據(jù)集上不同的分類。其中，t-SNE 算法的參數(shù)均使用默認(rèn)設(shè)置。

圖2 為利用DeepWalk 算法所得到的嵌入向量作為t-SNE算法輸入的可視化結(jié)果。從圖2 中可以看到，DeepWalk 算法的可視化結(jié)果并不是有意義的，許多并不屬于同一類的節(jié)點(diǎn)聚集在一簇中，同時(shí)也存在大量的異常點(diǎn)獨(dú)立于簇間。原因主要?dú)w結(jié)于DeepWalk 算法所得到的嵌入向量只能保存屬性圖中節(jié)點(diǎn)的拓?fù)湫畔?，?duì)于屬性信息卻完全沒有表達(dá)。

圖3 為利用本文所提出的方法得到的嵌入向量作為t-SNE 算法輸入的可視化結(jié)果。與圖2 相比，屬于同一類的節(jié)點(diǎn)大多能夠被分配在一個(gè)或幾個(gè)簇中。同時(shí)，DeepWalk算法可視化結(jié)果中的異常點(diǎn)在圖3 中也被分配到了各自的簇中。與DeepWalk 相比，本文所提出的方法生成的可視化結(jié)果是更有意義的。

圖2 DeepWalk算法在Cora數(shù)據(jù)集上的可視化結(jié)果Fig.2 Visualization result of DeepWalk algorithm on Cora dataset

圖3 本文方法在Cora數(shù)據(jù)集上的可視化結(jié)果Fig.3 Visualization result of the proposed method on Cora dataset

4.5 超參數(shù)實(shí)驗(yàn)

圖4 展示了在Cora 數(shù)據(jù)集上超參數(shù)α的變化對(duì)節(jié)點(diǎn)分類任務(wù)準(zhǔn)確率的影響。當(dāng)α為0.4 時(shí)，節(jié)點(diǎn)分類的準(zhǔn)確率最高，達(dá)到了81.7%。針對(duì)不同的數(shù)據(jù)集以及不同的任務(wù)，α的選取一般也是不同的，選擇一個(gè)合適的α是任務(wù)質(zhì)量的前提保證。

圖4 不同超參數(shù)α下的節(jié)點(diǎn)分類準(zhǔn)確率Fig.4 Node classification accuracy with different hyperparameter α

圖5 展示了在Cora 數(shù)據(jù)集上嵌入向量維數(shù)d對(duì)節(jié)點(diǎn)分類準(zhǔn)確率的影響。此實(shí)驗(yàn)分別記錄了d為10、40、64、128、256時(shí)，節(jié)點(diǎn)分類準(zhǔn)確率的變化情況?？梢杂^察到，當(dāng)嵌入向量維數(shù)過大時(shí)，本文所提出的方法在Cora 數(shù)據(jù)集上的節(jié)點(diǎn)分類準(zhǔn)確率會(huì)下降。

圖5 不同嵌入向量維度d下的節(jié)點(diǎn)分類準(zhǔn)確率Fig.5 Node classification accuracy with different embedding vector dimension d

5 結(jié)語

圖數(shù)據(jù)廣泛存在于實(shí)際場(chǎng)景中，例如社交網(wǎng)絡(luò)平臺(tái)、交通數(shù)據(jù)、生物醫(yī)藥網(wǎng)絡(luò)等。本文提出了一種針對(duì)屬性圖的無監(jiān)督嵌入方法，通過傳統(tǒng)的無屬性圖嵌入方法和屬性圖有監(jiān)督嵌入方法，利用提出的損失函數(shù)，可以獲得能夠保存屬性圖屬性信息和拓?fù)湫畔⒌那度胂蛄俊Ｔ? 個(gè)基準(zhǔn)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明本文所提出的方法的有效性，它可以學(xué)習(xí)到高質(zhì)量的嵌入向量。在大部分?jǐn)?shù)據(jù)集上，本文所提出的方法所取得的效果已經(jīng)可以超過最好的無監(jiān)督基線方法。

本文所提出的方法的空間復(fù)雜度與圖中節(jié)點(diǎn)個(gè)數(shù)的平方成正比，因?yàn)樵趽p失函數(shù)中需要使用節(jié)點(diǎn)基于拓?fù)浜蛯傩孕畔⒌南嗨贫染仃?，且使用的GCN 模型也需要計(jì)算圖的拉普拉斯矩陣，這意味著本文的方法難以直接擴(kuò)展到大圖。此外，與一般的半監(jiān)督或有監(jiān)督屬性圖嵌入算法相比，本文方法的執(zhí)行時(shí)間也較長(zhǎng)，這是為了保證嵌入高質(zhì)量的代價(jià)。因此，未來的工作是改進(jìn)方法，使得該方法能夠在較短的時(shí)間內(nèi)，在占用更少的資源的同時(shí)，獲得更高質(zhì)量的嵌入向量。