關(guān)鍵詞：隨機(jī)游走;圖模型;注意力機(jī)制;圖擴(kuò)散

中圖分類號：TP391 文獻(xiàn)標(biāo)志碼：A

0 引言（Introduction）

基于圖的深度學(xué)習(xí)方法在解決許多重要的圖問題上取得了成功[1-4]，其中一些工作旨在使用注意力機(jī)制提取圖上的特征信息[5]，但存在以下問題。

（1）典型的圖方法對于每個(gè)節(jié)點(diǎn)僅使用非常有限的鄰居節(jié)點(diǎn)信息，而更大的鄰域可以向模型提供更多的信息。一般的方法是通過疊加多個(gè)層達(dá)到傳遞全局信息的目的，但是過多的層會(huì)導(dǎo)致過度平滑問題[6-7]，并且隨著層數(shù)增加，訓(xùn)練難度會(huì)不斷增大。

（2）使用圖數(shù)據(jù)的挑戰(zhàn)性在于要找到正確的表達(dá)圖結(jié)構(gòu)的方式，傳統(tǒng)方法無法區(qū)分鄰居的位置關(guān)系[8]，從而失去了節(jié)點(diǎn)相關(guān)的拓?fù)湫畔??；谧⒁饬C(jī)制[5]的方法將鄰居特征的加權(quán)和作為中心節(jié)點(diǎn)的輸出特征，但只考慮了特征信息，并沒有反映節(jié)點(diǎn)不同的結(jié)構(gòu)。ZHOU等[9]提出在注意力機(jī)制中引入代表結(jié)構(gòu)信息的可學(xué)習(xí)向量，但向量的學(xué)習(xí)增大了參數(shù)量和模型復(fù)雜度，存在過擬合的現(xiàn)象。

綜上所述，本文提出一種隨機(jī)游走的圖擴(kuò)散模型（GraphDiffusion Model with Random Walks，GDR），該算法通過隨機(jī)游走的擴(kuò)散方式[10]訪問鄰居節(jié)點(diǎn)，確保了對每個(gè)中心節(jié)點(diǎn)的局部鄰域進(jìn)行編碼。通過設(shè)置游走的相關(guān)參數(shù)，可以滿足控制一定范圍內(nèi)鄰域信息的需求。本研究認(rèn)為，該游走策略產(chǎn)生的鄰居節(jié)點(diǎn)包含了圖的結(jié)構(gòu)，使得在注意力機(jī)制計(jì)算特征相關(guān)性的同時(shí)包含了節(jié)點(diǎn)的拓?fù)湫畔?，并且這種擴(kuò)散方法沒有增加模型的參數(shù)，使訓(xùn)練更加簡單。

1 問題描述（Problem statement）

對于圖中節(jié)點(diǎn)的分類任務(wù)，建立圖G=（V，ε，A），其中V是圖中的節(jié)點(diǎn)集，ε是邊集，反映了節(jié)點(diǎn)之間的連通性。A∈RN×N 表示G 的鄰接矩陣。同時(shí)，建立矩陣H ∈RN×d 作為節(jié)點(diǎn)的輸入特征矩陣，其中N 表示節(jié)點(diǎn)數(shù)，d 表示輸入特征維度。給定圖G 的輸入特征矩陣H，通過學(xué)習(xí)一個(gè)特征轉(zhuǎn)換函數(shù)f 得到輸出特征矩陣H'∈RN×d'，再通過分類器對輸出特征的節(jié)點(diǎn)進(jìn)行分類。

2 模型架構(gòu)（Model architecture）

2.1 整體架構(gòu)

本文提出的GDR模型的整體架構(gòu)如圖1所示，它由多個(gè)特征轉(zhuǎn)換模塊組成，每個(gè)模塊包含一個(gè)隨機(jī)游走層（RandomWalk Layer， RWL）和一個(gè)圖注意力層（Graph AttentionLayer， GAL）。RWL以隨機(jī)游走的擴(kuò)散方式獲取各中心節(jié)點(diǎn)的鄰居，這些鄰居節(jié)點(diǎn)包含結(jié)構(gòu)上的依賴關(guān)系，并可繼續(xù)擴(kuò)散到更大的鄰域。GAL通過圖上的注意力機(jī)制對RWL層輸出的節(jié)點(diǎn)及其鄰居進(jìn)行特征轉(zhuǎn)換，注意力機(jī)制本質(zhì)上只針對鄰居節(jié)點(diǎn)特征加權(quán)求和，引入RWL后，節(jié)點(diǎn)之間通過結(jié)構(gòu)進(jìn)行了區(qū)分，使模型包含更完備的信息。輸入的圖數(shù)據(jù)通過多個(gè)特征轉(zhuǎn)換模塊后，生成的最終特征進(jìn)入神經(jīng)網(wǎng)絡(luò)分類器中進(jìn)行節(jié)點(diǎn)類別的預(yù)測。

2.2 隨機(jī)游走層

典型的圖模型在采集鄰居節(jié)點(diǎn)時(shí)，只使用了每個(gè)節(jié)點(diǎn)非常有限的鄰域范圍，GraphSAGE（Graph SAmple and aggreGatE）模型[8]通過隨機(jī)采樣的方式從一階或二階鄰域中獲取節(jié)點(diǎn)，GAT模型[5]則直接使用一階節(jié)點(diǎn)，這種局部的鄰域通過疊加多層而不斷擴(kuò)大;對于其中一層（圖2），作為鄰居節(jié)點(diǎn)的B 和C，相對中心節(jié)點(diǎn)A 沒有做結(jié)構(gòu)上的區(qū)分，在連接方式上相對A 是沒有差別的，而不同的連接方式正是鄰居節(jié)點(diǎn)拓?fù)浣Y(jié)構(gòu)的差異?；谧⒁饬C(jī)制的特征學(xué)習(xí)方法最初是在自然語言的背景下開發(fā)的，旨在尋找線性文本中連續(xù)單詞的上下文位置關(guān)系，即線性的結(jié)構(gòu)。注意力機(jī)制無法對位置進(jìn)行區(qū)分，典型的Transformer模型[11]在原始特征中加入位置信息，是一種人為設(shè)計(jì)的特征，文獻(xiàn)作者沒有對其進(jìn)行詳細(xì)解釋。網(wǎng)絡(luò)是非線性結(jié)構(gòu)，需要更豐富的鄰域范圍內(nèi)的結(jié)構(gòu)信息。SAN（StructuralAttention Network）模型[9]則是在圖中引入了一個(gè)結(jié)構(gòu)化向量，讓模型在訓(xùn)練過程中自動(dòng)地進(jìn)行結(jié)構(gòu)化信息的學(xué)習(xí)，但增加了模型的參數(shù)。

整個(gè)特征轉(zhuǎn)換模塊分為隨機(jī)游走和圖注意力計(jì)算兩個(gè)階段。隨機(jī)游走階段首先利用輸入的鄰接矩陣A，根據(jù)公式（1）計(jì)算轉(zhuǎn)移矩陣T，其次根據(jù)公式（2）及參數(shù)α 和k 計(jì)算得到概率矩陣P，最后根據(jù)P 中的概率進(jìn)行隨機(jī)游走生成鄰居節(jié)點(diǎn)集合S。圖注意力階段則從上一階段輸出的節(jié)點(diǎn)集合S中選擇中心節(jié)點(diǎn)的鄰居，首先利用輸入的特征矩陣H，根據(jù)公式（4）計(jì)算注意力系數(shù)，其次根據(jù)公式（5）對輸入特征進(jìn)行轉(zhuǎn)換，最后通過神經(jīng)網(wǎng)絡(luò)分類器進(jìn)行類別預(yù)測。

3 實(shí)驗(yàn)（Experiment）

本文通過轉(zhuǎn)導(dǎo)學(xué)習(xí)和歸納學(xué)習(xí)，將GDR模型與其他基準(zhǔn)模型在節(jié)點(diǎn)分類任務(wù)中的性能進(jìn)行了比較。本節(jié)總結(jié)了實(shí)驗(yàn)設(shè)置、結(jié)果，并對GDR模型的相關(guān)參數(shù)進(jìn)行了簡要分析。

3.1 數(shù)據(jù)集描述

實(shí)驗(yàn)使用的數(shù)據(jù)集如表1所示，在3個(gè)引文數(shù)據(jù)集上預(yù)測文檔類別以評估本文模型的轉(zhuǎn)導(dǎo)學(xué)習(xí)能力，包括Citeseer、Cora和Pubmed[14]。數(shù)據(jù)集包含文檔的特征向量集合及文檔之間的引用鏈接列表，以此構(gòu)造出鄰接矩陣和特征矩陣，訓(xùn)練過程中使用了圖中所有節(jié)點(diǎn)的特征向量。歸納任務(wù)部分采用了生物醫(yī)學(xué)領(lǐng)域的蛋白質(zhì)相互作用（Protein-Protein Interaction，PPI）數(shù)據(jù)集[8]，由對應(yīng)于不同蛋白質(zhì)組織的圖組成，共有24張圖，每個(gè)圖的平均節(jié)點(diǎn)數(shù)為2 372個(gè)，節(jié)點(diǎn)特征維度為50維，由位置基因集、基序基因集和免疫學(xué)特征組成，該數(shù)據(jù)集中一個(gè)節(jié)點(diǎn)同時(shí)擁有多個(gè)標(biāo)簽，并且用于測試任務(wù)的圖在訓(xùn)練期間沒有被使用。

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

對于引文數(shù)據(jù)集，采用一個(gè)特征轉(zhuǎn)換模塊的GDR模型。其中，RWL的重啟概率α 為0.1，擴(kuò)散系數(shù)k 為10。GAL則主要參考了GAT模型進(jìn)行設(shè)置，采用8個(gè)注意力層組成的多頭注意力結(jié)構(gòu)，每個(gè)頭輸出8個(gè)維度的特征（總共64個(gè)特征），使用ELU激活函數(shù)進(jìn)行非線性變換，最后一層是softmax分類。由于引文數(shù)據(jù)集較小，模型采用了λ=0.005的L2正則化方法。

PPI數(shù)據(jù)集用于評價(jià)模型在跨圖上的歸納學(xué)習(xí)能力，采用了3個(gè)特征轉(zhuǎn)換模塊，RWL的重啟概率α 為0.1，擴(kuò)散系統(tǒng)k 為20，GAL的設(shè)置同樣參照了GAT 模型的做法，以方便對比模型改進(jìn)的效果。前兩個(gè)GAL是4個(gè)注意力層組成的多頭注意力結(jié)構(gòu)，每個(gè)頭輸出256維的特征（總共1 024維），采用ELU激活函數(shù)。最后一層是單頭的注意力層，輸出維度為類別數(shù)，由于每個(gè)節(jié)點(diǎn)屬于多個(gè)類別，因此分類采用了logistic函數(shù)。

3.3 基準(zhǔn)模型

對于引文數(shù)據(jù)集，選用的對比模型為GAT和GCN[7]，以及GCN在使用多階Chebyshev截?cái)鄷r(shí)的效果。對于PPI數(shù)據(jù)集，除了與注意力模型GAT進(jìn)行對比，還比較了GraphSAGE模型中提出的4種不同的聚合方法。這些方法在小范圍鄰域內(nèi)采樣節(jié)點(diǎn)并通過某種聚合函數(shù)計(jì)算輸出特征，如GrapshSAGE-GCN采用了GCN的圖卷積操作作為聚合函數(shù)，GraphSAGE-mean 直接取所有采樣特征的平均值，GraphSAGE-LSTM將采樣的鄰居特征隨機(jī)排序后輸入LSTM進(jìn)行聚合，GraphSAGE-pooling將節(jié)點(diǎn)特征經(jīng)過全連接的神經(jīng)網(wǎng)絡(luò)后進(jìn)行最大池化聚合。

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

表2給出了在3個(gè)引文數(shù)據(jù)集上針對測試節(jié)點(diǎn)的分類準(zhǔn)確率。從表2中可以看出，在對比方法中，GDR模型在3個(gè)引文數(shù)據(jù)集上都取得了最高準(zhǔn)確率，并且注意力機(jī)制中的參數(shù)設(shè)置完全參考GAT模型，可以認(rèn)為性能的提升來自RWL的隨機(jī)游走策略，表明通過擴(kuò)散得到的鄰居節(jié)點(diǎn)提供了更多的信息。相比于SAN模型通過引入訓(xùn)練時(shí)可學(xué)習(xí)的結(jié)構(gòu)化向量的方法，游走策略沒有給模型增加訓(xùn)練時(shí)的參數(shù)，因此不容易過擬合。

通過調(diào)整重啟概率α 和擴(kuò)散系數(shù)k，觀察游走策略的作用。圖4顯示了α 取值的變化對測試集準(zhǔn)確率的影響。雖然針對不同數(shù)據(jù)集的最佳取值略有不同，但是起伏變化基本一致，重啟概率在0.1～0.2時(shí)表現(xiàn)最佳，表明一定的重啟概率使游走兼顧了局部與全局結(jié)構(gòu)，并帶來了性能的提升。由于不同的圖數(shù)據(jù)具有不同的結(jié)構(gòu)，因此在訓(xùn)練時(shí)需要針對具體的數(shù)據(jù)集調(diào)整該參數(shù)取值。

圖5顯示了擴(kuò)散系數(shù)k 取不同值時(shí)，對模型分類結(jié)果的影響。隨著k 值的增加，準(zhǔn)確率呈現(xiàn)上升趨勢，證明隨機(jī)游走的擴(kuò)散策略對模型性能的提升是有益的。如圖5所示，使用適當(dāng)?shù)膋 值（例如取值為10）有效地近似精確結(jié)果已經(jīng)足夠，更大的取值帶來的效果提升不明顯，而且可能會(huì)因?yàn)楦噜従庸?jié)點(diǎn)的加入而導(dǎo)致GAL的過擬合。

表3總結(jié)了不同方法在PPI數(shù)據(jù)集0e1GpSYVhisAwu5eLy9rC1LhCZSC57I8NQ0rxnLOzvQ=上的歸納學(xué)習(xí)結(jié)果比較，采用GraphSAGE模型中的評價(jià)方法測試了模型在未見節(jié)點(diǎn)上的micro F1值。由于GDR模型采用的是有監(jiān)督的學(xué)習(xí)，所以本研究比較的是GraphSAGE模型的有監(jiān)督版本。本文方法在對比中取得了明顯優(yōu)勢。GraphSAGE模型在選取鄰居節(jié)點(diǎn)時(shí)，使用的采樣策略沒有區(qū)分節(jié)點(diǎn)之間的相對關(guān)系，證明了本文方法在獲取結(jié)構(gòu)信息上具有優(yōu)勢。GAT模型在獲取鄰域時(shí)，只使用一階鄰居節(jié)點(diǎn)，而GDR模型在游走時(shí)可通過設(shè)置擴(kuò)散系數(shù)傳播到更大的鄰域，體現(xiàn)了擴(kuò)散的效果。SAN模型與本文方法取得了同樣的得分，但需要訓(xùn)練一個(gè)有參數(shù)的向量矩陣，增加了模型的復(fù)雜度，而本文方法在訓(xùn)練上更加簡單。

4 結(jié)論（Conclusion）

本文提出了一種基于隨機(jī)游走策略的圖擴(kuò)散模型，可用于圖節(jié)點(diǎn)的分類。該模型在經(jīng)典的圖注意力模型基礎(chǔ)上增加了一個(gè)隨機(jī)游走層，能有效地提取圖數(shù)據(jù)中更大鄰域范圍內(nèi)的節(jié)點(diǎn)信息，使注意力機(jī)制同時(shí)考慮了節(jié)點(diǎn)的結(jié)構(gòu)和特征。在多個(gè)引文數(shù)據(jù)集及一個(gè)蛋白質(zhì)網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)表明，該模型對節(jié)點(diǎn)的分類結(jié)果優(yōu)于現(xiàn)有的經(jīng)典模型，證明了隨機(jī)游走策略的有效性。

作者簡介：

周安眾（1986-），男，碩士，講師。研究領(lǐng)域：大數(shù)據(jù)技術(shù)，人工智能。

謝丁峰（1978-），男，碩士，副教授。研究領(lǐng)域：大數(shù)據(jù)技術(shù)，人工智能。