基于相似網(wǎng)絡(luò)和聯(lián)合注意力的圖嵌入模型

摘" 要：圖注意力網(wǎng)絡(luò)（graph attention network，GAT）將注意力機(jī)制與圖神經(jīng)網(wǎng)絡(luò)融合，但模型只關(guān)注節(jié)點的一階鄰域節(jié)點，缺乏對高階相似節(jié)點的考慮，同時在計算注意力分?jǐn)?shù)時缺乏對節(jié)點結(jié)構(gòu)特征的關(guān)注.為此提出一種基于相似網(wǎng)絡(luò)和聯(lián)合注意力的圖嵌入模型.首先計算網(wǎng)絡(luò)中的節(jié)點相似性，并將高相似度且未連接的節(jié)點對構(gòu)建新邊以形成相似網(wǎng)絡(luò).其次，引入結(jié)構(gòu)相關(guān)性和內(nèi)容相關(guān)性的概念，分別用于表征節(jié)點之間的結(jié)構(gòu)關(guān)系和內(nèi)容特征.通過融合兩種相關(guān)性得分計算得到聯(lián)合注意力分?jǐn)?shù).最后使用聯(lián)合注意力分?jǐn)?shù)對節(jié)點特征加權(quán)聚合，得到最終的節(jié)點嵌入表示.將本文所提算法在Cora、Citeseer和Pubmed 3個數(shù)據(jù)集上進(jìn)行節(jié)點分類任務(wù)，準(zhǔn)確率分別達(dá)到85.70%、74.30%、84.10%，與原始圖注意力網(wǎng)絡(luò)模型相比分別提高了2.70%、3.94%和2.60%.可見，所提出的算法可以得到更好的節(jié)點嵌入表示.

關(guān)鍵詞：圖嵌入;圖注意力網(wǎng)絡(luò);節(jié)點相似性;相似網(wǎng)絡(luò);節(jié)點分類

中圖分類號：TP181""""" 文獻(xiàn)標(biāo)志碼：A文章編號：1000-2367（2024）06-0036-09

圖可以表示許多現(xiàn)實世界的數(shù)據(jù)集，例如蛋白質(zhì)結(jié)構(gòu)網(wǎng)絡(luò)，引文網(wǎng)絡(luò)以及社交網(wǎng)絡(luò)等.圖的節(jié)點和邊蘊含著豐富的信息，并可適應(yīng)多個領(lǐng)域的學(xué)習(xí)任務(wù).在圖的各種分析任務(wù)上依賴于可用的圖表示，獲得用于圖數(shù)據(jù)挖掘的特征表示的關(guān)鍵環(huán)節(jié)就是圖表示學(xué)習(xí)，又稱圖嵌入.圖表示學(xué)習(xí)目標(biāo)是將節(jié)點映射到低維空間，生成低維、稠密的向量并盡可能保留原始圖中的信息.最后生成的向量表示應(yīng)用于各種下游任務(wù)，比如節(jié)點聚類［1］和鏈路預(yù)測［2］等等.

傳統(tǒng)的圖嵌入算法，例如矩陣分解（matrix factorization，MF）、Deepwalk［3］等算法，這類算法在生成節(jié)點的低維向量表示時容易丟失初始節(jié)點的屬性特征，在保留圖的特征信息方面存在不足.近年來，神經(jīng)網(wǎng)絡(luò)逐漸推廣到圖數(shù)據(jù)鄰域并取得顯著成果，研究人員提出許多圖神經(jīng)網(wǎng)絡(luò)模型（graph neural network，GNN），其中圖注意力網(wǎng)絡(luò)（GAT）［4］引起了眾多的關(guān)注，并被應(yīng)用于解決大量現(xiàn)實世界的問題，例如節(jié)點分類、圖像分割和社交推薦等.

圖注意力網(wǎng)絡(luò)將神經(jīng)網(wǎng)絡(luò)與注意力機(jī)制相結(jié)合，旨在通過計算每個節(jié)點與其鄰居節(jié)點之間的注意力權(quán)重來動態(tài)聚合鄰居節(jié)點的特征，并將其與當(dāng)前節(jié)點的特征結(jié)合起來遞到下一層.這種方法能夠在多層神經(jīng)架構(gòu)中傳遞和整合來自相鄰節(jié)點的高度相關(guān)特征，從而提高網(wǎng)絡(luò)性能.

但目前GAT在聚合節(jié)點特征時仍有缺點.一方面GAT在聚合節(jié)點特征時只有一階鄰居節(jié)點被關(guān)注，

收稿日期：2023-06-16;修回日期：2023-07-04.

基金項目：河北省自然科學(xué)基金（F2021205014）；河北省高等學(xué)?？茖W(xué)技術(shù)研究項目（ZD2022139）；中央引導(dǎo)地方科技發(fā)展資金項目（226Z1808G）；河北省歸國人才資助項目（C20200340）.

作者簡介（通信作者）：王靜紅（1967-），女，河北石家莊人，河北師范大學(xué)教授，博士，主要研究方向為人工智能與大數(shù)據(jù)、數(shù)據(jù)挖掘，E-mail： wangjinghong@126.com.

引用本文：王靜紅，李昌鑫，楊家騰，等.基于相似網(wǎng)絡(luò)和聯(lián)合注意力的圖嵌入模型［J］.河南師范大學(xué)學(xué)報（自然科學(xué)版），2024，52（6）：36-44.（Wang Jinghong，Li Changxin，Yang Jiateng，et al.A graph embedding model based on similar networks and joint attention［J］.Journal of Henan Normal University（Natural Science Edition），2024，52（6）：36-44.DOI：10.16366/j.cnki.1000-2367.2023.06.16.0001.）

而與節(jié)點密切相關(guān)的高階鄰居節(jié)點會被忽略.但在真實網(wǎng)絡(luò)數(shù)據(jù)集中，如圖嵌入中常用的數(shù)據(jù)集Cora［5］、Citeseer［5］等，節(jié)點的度通常較小，僅利用一階鄰居節(jié)點會導(dǎo)致在特征聚合時可利用的信息過少.同時，在圖嵌入中，相似節(jié)點在嵌入空間中也更接近，因此利用高階相似節(jié)點可以豐富節(jié)點特征信息以完成更好的節(jié)點表征.但若在注意力網(wǎng)絡(luò)中直接利用高階鄰居節(jié)點則會出現(xiàn)過度平滑［6］問題.另一方面GAT在計算注意力分?jǐn)?shù)時主要基于節(jié)點內(nèi)容特征，而很少考慮節(jié)點的結(jié)構(gòu)特征.以上反映出GAT在利用節(jié)點結(jié)構(gòu)信息和高階相似節(jié)點信息方面存在弱點.

針對上述問題，本文提出融合高階相似節(jié)點和節(jié)點結(jié)構(gòu)信息的圖聯(lián)合注意力嵌入模型，其關(guān)鍵思想是第一步利用節(jié)點相似性度量指標(biāo)計算節(jié)點相似性，然后構(gòu)建相似網(wǎng)絡(luò)，使節(jié)點能夠與其高階相似節(jié)點建立起聯(lián)系.第二步結(jié)合節(jié)點內(nèi)容相關(guān)性和結(jié)構(gòu)相關(guān)性計算聯(lián)合注意力分?jǐn)?shù).最后使用聯(lián)合注意力分?jǐn)?shù)進(jìn)行加權(quán)聚合.更具體地說，本文的貢獻(xiàn)總結(jié)如下：1）提出了相似網(wǎng)絡(luò)構(gòu)建方法.通過相似性度量指標(biāo)構(gòu)建相似網(wǎng)絡(luò)，使節(jié)點與其關(guān)系密切的高階鄰居節(jié)點建立起聯(lián)系，成為其新的一階鄰居節(jié)點，保證模型可以考慮到其相似度較高的高階鄰居節(jié)點.

2）提出了聯(lián)合注意力分?jǐn)?shù)計算方法.結(jié)合內(nèi)容相關(guān)性和結(jié)構(gòu)相關(guān)性計算聯(lián)合注意力分?jǐn)?shù).內(nèi)容相關(guān)性由現(xiàn)有的圖注意力機(jī)制計算，用來表征節(jié)點的內(nèi)容關(guān)系.設(shè)計一個自適應(yīng)距離計算函數(shù)計算節(jié)點的結(jié)構(gòu)相關(guān)性，用來表征節(jié)點的結(jié)構(gòu)關(guān)系，從而使模型在計算注意力分?jǐn)?shù)時不但關(guān)注節(jié)點內(nèi)容信息還考慮到節(jié)點結(jié)構(gòu)信息.3）提出基于相似網(wǎng)絡(luò)和聯(lián)合注意力的圖嵌入模型.利用聯(lián)合注意力分?jǐn)?shù)進(jìn)行節(jié)點特征加權(quán)聚合，得到節(jié)點的嵌入表示.將模型在真實世界的3個數(shù)據(jù)集上進(jìn)行實驗，并與多個基準(zhǔn)算法進(jìn)行了比較，取得較好的節(jié)點分類結(jié)果，表明了本文所提算法的優(yōu)越性及合理性.

1" 相關(guān)工作

圖嵌入旨在將圖中的節(jié)點映射到低維空間，生成低維稠密的向量，并保留圖原始信息.對于圖嵌入算法，大致可以分為3類：基于分解的方法、基于隨機(jī)游走的方法和基于深度學(xué)習(xí)的方法.

基于分解的圖嵌入方法有拉普拉斯特征圖（laplacian eigenmaps，LE）算法［7］、局部保留投影算法（locality preserving projections，LPP）［8］，基于隨機(jī)游走的方法有Deepwalk［3］，Node2vec［9］.Deepwalk算法將SkipGram模型［10］應(yīng)用到生成的隨機(jī)游走上，被認(rèn)為是第一個基于圖表示學(xué)習(xí)的圖嵌入算法.上述基于分解和基于游走的兩種方法僅考慮網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)信息.而現(xiàn)實世界中圖中的節(jié)點都帶有豐富的屬性信息，因此使用這兩種方法學(xué)習(xí)圖嵌入時會忽略節(jié)點的屬性信息從而影響最終的表示.

然后，神經(jīng)網(wǎng)絡(luò)開始應(yīng)用到圖嵌入領(lǐng)域.為了更好地學(xué)習(xí)圖結(jié)構(gòu)數(shù)據(jù)中的低維表征，迄今為止已經(jīng)提出了許多圖神經(jīng)網(wǎng)絡(luò)模型（GNNs），例如圖卷積網(wǎng)絡(luò)（graph convolution network，GCN）［11］、圖注意力網(wǎng)絡(luò)（GAT）等.譜域CNNs中用于特征聚合的函數(shù)是根據(jù)圖的譜表示定義的，如Spectral CNN［12］將圖域中的卷積運算轉(zhuǎn)換為更為簡單的拉普拉斯運算.之后使用譜圖理論中卷積運算的方法被提出，如GCN、SGCN［13］.而空域GNNs直接利用中心節(jié)點的局部結(jié)構(gòu)屬性來定義用于特征聚合的卷積運算，因此必須通過各種處理步驟來適應(yīng)不同的節(jié)點結(jié)構(gòu).如Graph SAGE［14］通過固定領(lǐng)域采樣大小聚合特征信息，或根據(jù)節(jié)點度學(xué)習(xí)一個權(quán)重矩陣［15］.最近，圖注意力網(wǎng)絡(luò)（GAT）通過將圖神經(jīng)網(wǎng)絡(luò)與注意力機(jī)制相結(jié)合取得了很大的成功［4］.注意力機(jī)制允許處理可變大小的輸入并關(guān)注最相關(guān)的部分，目前已經(jīng)廣泛應(yīng)用于機(jī)器翻譯［16］和視覺處理［17］.GAT首先會基于中心節(jié)點和一跳鄰居節(jié)點的特征計算節(jié)點之間的注意力分?jǐn)?shù)，然后使用注意力分?jǐn)?shù)來獲得節(jié)點特征的加權(quán)聚合，隨后傳播到下一層.

然而，圖注意力網(wǎng)絡(luò)在計算注意力分?jǐn)?shù)時嚴(yán)重依賴于一階鄰居節(jié)點的節(jié)點特征，而高階鄰居節(jié)點特征和節(jié)點拓?fù)浣Y(jié)構(gòu)特征往往被忽略.由于GNN的過渡平滑原因［6］，直接利用高階鄰居節(jié)點之間的注意力時，GAT的性能會下降.因此如何利用GAT中的結(jié)構(gòu)信息和相關(guān)度極高的高階節(jié)點仍是一個挑戰(zhàn).

研究者開始關(guān)注結(jié)構(gòu)因素對注意力分?jǐn)?shù)的影響.CATs算法［18］提出聯(lián)合注意力機(jī)制，結(jié)合神經(jīng)網(wǎng)絡(luò)內(nèi)部和外部的異構(gòu)可學(xué)習(xí)因素來計算注意力系數(shù)，但是所提模型預(yù)測能力取決于結(jié)構(gòu)干預(yù)的質(zhì)量，易受外部噪聲影響.ADSF算法［19］關(guān)鍵思想是將每一個節(jié)點置于由其高階鄰居節(jié)點組成的局部感受域內(nèi)，感受域內(nèi)將自適應(yīng)學(xué)習(xí)圖局部結(jié)構(gòu).SuperGAT［20］通過自監(jiān)督學(xué)習(xí)改進(jìn)圖注意力機(jī)制，利用邊的自監(jiān)督任務(wù)來提高對節(jié)點關(guān)系重要性的理解，并提出了平衡標(biāo)簽一致性和邊存在性的注意力形式.GOAT模型［21］通過引入部分信息分解和排列敏感的聚合器，利用自注意力機(jī)制學(xué)習(xí)節(jié)點的排序并捕捉鄰域節(jié)點之間的協(xié)同和冗余信息.上述方法并沒有考慮到節(jié)點相似性問題.SiGraC［22］模型提出使用基于節(jié)點相似性的卷積矩陣計算節(jié)點嵌入，但其是基于圖卷積思想，并沒有考慮到不同節(jié)點之間相對重要性的問題.

因此針對以上算法存在的不足，本文提出新的圖嵌入模型，在算法中增加對高階相似節(jié)點和拓?fù)浣Y(jié)構(gòu)特征信息的關(guān)注，從而得到更好的節(jié)點嵌入表示.

2" 基礎(chǔ)知識

本節(jié)介紹論文中所涉及的所有變量以及相關(guān)定義.

G為圖，V是圖的節(jié)點集，E是圖的邊集，N表示圖的節(jié)點數(shù)量，X表示特征矩陣，A為圖的鄰接矩陣，C是圖的相似度矩陣，α是相似度閾值，fij表示內(nèi)容相關(guān)性，sij表示結(jié)構(gòu)相關(guān)性，H表示圖嵌入.

定義1" 圖.圖可以表示為G=（V，E），其中V為圖的節(jié)點集合，E為邊集.圖共有N個節(jié)點，C個節(jié)點類別，|E|條邊.使用A∈｛0，1｝N×N表示圖的鄰接矩陣，X∈RN×D為輸入節(jié)點特征矩陣，Ni表示節(jié)點i及其一跳鄰居節(jié)點.

定義2" 相似網(wǎng)絡(luò).本文使用節(jié)點相似性度量指標(biāo)計算節(jié)點與其鄰居節(jié)點的相似性，計算方式如下：ci，j=γ（i，j），（1）其中，ci，j表示節(jié)點i與節(jié)點j之間的相似度，ci，j值越大表明節(jié)點i與節(jié)點j之間越相似，γ（i，j）為相似度計算函數(shù).在矩陣形式中最終得到相似度矩陣C，其中C（i，j）為節(jié)點i與節(jié)點j之間的相似度，即ci，j.然后計算相似網(wǎng)絡(luò)的鄰接矩陣，此處超參數(shù)α為相似度閾值，用來限制相似節(jié)點的連接，計算方式如下：

A′=1，ci，jα，0，其他.（2）

當(dāng)A′i，j=1時在節(jié)點i和節(jié)點j之間構(gòu)建邊ei，j，否則不構(gòu)建邊，最終會形成新的相似網(wǎng)絡(luò)G′.

定義3" 圖嵌入.給定圖G=（V，E），通過無監(jiān)督或有監(jiān)督學(xué)習(xí)將圖中每個節(jié)點vi映射到低維空間，并保留原始信息.其任務(wù)旨在學(xué)習(xí)一個映射函數(shù)f：vi→hi∈Rd，其中vi表示第i個節(jié)點，hi∈Rd表示節(jié)點i的低維向量表示.

3" 算法框架

本算法首先構(gòu)建相似網(wǎng)絡(luò)，其次分別計算相似網(wǎng)絡(luò)中節(jié)點之間的內(nèi)容相關(guān)性和結(jié)構(gòu)相關(guān)性，兩者結(jié)合得到聯(lián)合注意力分?jǐn)?shù).最后使用聯(lián)合注意力分?jǐn)?shù)進(jìn)行特征加權(quán)聚合，得到節(jié)點的嵌入表示.算法框架圖如圖1所示.

本算法主要由3部分構(gòu)成：

1）相似網(wǎng)絡(luò)構(gòu)建模塊：首先使用節(jié)點相似性度量指標(biāo)計算網(wǎng)絡(luò)中節(jié)點之間的相似度.根據(jù)相似度閾值α進(jìn)行篩選，對相似度較高且未連接的節(jié)點對構(gòu)建新的邊，從而使節(jié)點與其高階相似節(jié)點建立起聯(lián)系，最終形成相似網(wǎng)絡(luò).此模塊解決了原始圖注意力網(wǎng)絡(luò)只關(guān)注一階鄰居節(jié)點的問題，豐富了聚合時的節(jié)點特征信息.

2）聯(lián)合注意力分?jǐn)?shù)計算模塊：若計算節(jié)點i和節(jié)點j之間的聯(lián)合注意力分?jǐn)?shù)，需分別計算節(jié)點對的內(nèi)容相關(guān)性和結(jié)構(gòu)相關(guān)性.從內(nèi)容上講，節(jié)點內(nèi)容特征將用來計算節(jié)點對的內(nèi)容相關(guān)性；從結(jié)構(gòu)上講，節(jié)點結(jié)構(gòu)特征被用來計算結(jié)構(gòu)相關(guān)性.節(jié)點內(nèi)容相關(guān)性使用GAT中的注意力分?jǐn)?shù)計算方法獲得.通過設(shè)計一個自適應(yīng)距離計算函數(shù)來計算節(jié)點的結(jié)構(gòu)相關(guān)性，最后聯(lián)合節(jié)點內(nèi)容相關(guān)性和結(jié)構(gòu)相關(guān)性計算得到聯(lián)合注意力分?jǐn)?shù).

3）圖注意力機(jī)制模塊：使用圖注意力機(jī)制進(jìn)行特征提取，在特征聚合過程中根據(jù)聯(lián)合注意力分?jǐn)?shù)對節(jié)點特征進(jìn)行加權(quán)聚合，最終得到嵌入表示.

3.1" 相似網(wǎng)絡(luò)構(gòu)建模塊

本模塊旨在使高階相似節(jié)點參與到學(xué)習(xí)過程中.本文使用4種節(jié)點相似性度量來計算得到網(wǎng)絡(luò)的相似度矩陣CN×N，其中N為節(jié)點的個數(shù)，CN×N中每一個位置對應(yīng)于原始網(wǎng)絡(luò)中兩個節(jié)點之間的相似度，后根據(jù)相似度閾值α進(jìn)行篩選相似節(jié)點對，若節(jié)點對相似度高于相似度閾值則構(gòu)建邊，最終形成相似網(wǎng)絡(luò)G′.

4種有代表性的節(jié)點相似性度量指標(biāo)，分別是common neighbors（CN）［23］，jaccard index（Jaccard）［24］，adamic-adar（AA）［25］，hub depressed index（HDI）［26］.下面將分別介紹這4種相似性計算方法.

（1）Common Neighbors（CN）：給定節(jié)點u∈V，Γ（u）V為節(jié)點u的鄰居節(jié)點集合.節(jié)點uV和節(jié)點vV的共同鄰域定義如下：

cu，v=|Γ（u）∩Γ（u）|=|｛w∈V|（v，w）∧（u，w）∈ε｝|.（3）

在矩陣形式中，相似度矩陣可以被表述為：C=2.（4）

（2）Jaccard Index：該指標(biāo)通過將交集的大小與并集的大小歸一化來評估兩個節(jié)點的鄰居之間的重疊情況：cu，v=|Γ（u）∩Γ（v）||Γ（u）∪Γ（v）|.（5）

在矩陣形式中，相似度矩陣可以通過以下方式求得C=2·（N+M-2），（6）

其中，N表示與A相同大小的全一矩陣，·表示矩陣點除操作.

（3）Adamic-Adar（AA）：該方法通過給連接較少的共同鄰居分配更多的權(quán)重來完善共同鄰居的概念：cu，v=∑w∈|Γ（u）∩Γ（v）|1log2（|Γ（w）|）.（7）

在矩陣形式中，相似度矩陣可由以下方式求得：C=log2（-1）.（8）

（4）Hub Depressed Index（HDI）：與Jaccard指標(biāo)類似，HDI的目的是根據(jù)節(jié)點的度歸一化兩個節(jié)點的鄰域的重疊部分，為了關(guān)注度數(shù)較高的節(jié)點：cu，v=|Γ（u）∩Γ（v）|max｛|Γ（u）∪Γ（v）|｝.（9）

基于HDI構(gòu)建的相似度矩陣，可以表述為：C=2·max｛N，N｝.（10）

3.2" 基于聯(lián)合注意力分?jǐn)?shù)的特征加權(quán)聚合模塊

本節(jié)主要介紹在構(gòu)建相似網(wǎng)絡(luò)后，算法中的聯(lián)合注意力分?jǐn)?shù)計算和圖注意力機(jī)制模塊的應(yīng)用.

首先，利用GAT中的注意力分?jǐn)?shù)計算方法得到相似網(wǎng)絡(luò)G′中所有節(jié)點對的內(nèi)容相關(guān)性.計算如下所示：fij=exp（LeakyRelu（T（Wi‖Wj）））∑k∈Niexp（LeakyRelu（T（Wi‖Wk））），（11）

其中，W∈RF′×F是網(wǎng)絡(luò)中所有節(jié)點共享的可訓(xùn)練的權(quán)重矩陣，為單層前饋神經(jīng)網(wǎng)絡(luò)的參數(shù)向量，‖表示串聯(lián)函數(shù)，F(xiàn)為節(jié)點的初始特征維度，i和j分別表示節(jié)點i和節(jié)點j的初始特征向量，Ni表示節(jié)點i的一階鄰居節(jié)點集合.通過此過程則能得到節(jié)點與其一階鄰居節(jié)點之間的特征相關(guān)性.

然后，尋求獲得節(jié)點i和節(jié)點j之間的結(jié)構(gòu)相關(guān)性.在矩陣形式中圖的結(jié)構(gòu)相關(guān)性可用下述方法獲得：Sij=arg min Φ（Mij，Aij），（12）

其中，S為圖的結(jié)構(gòu)相關(guān)性矩陣，Sij表示節(jié)點i和節(jié)點j之間的結(jié)構(gòu)相關(guān)性.Φ（·）為距離函數(shù)，A為輸入圖的鄰接矩陣，M為與A相同緯度的、所有節(jié)點可共享的自適應(yīng)可訓(xùn)練矩陣，本文中距離函數(shù)選擇歐氏距離，則式（12）可以寫為：Sij=arg min（Aij-Mij）2，（13）

之后，歸一化結(jié)構(gòu)相關(guān)性sij=exp（sij）∑k∈Niexp（sik）.（14）

然后將兩者結(jié)合計算最終的聯(lián)合注意力分?jǐn)?shù)aij=γ（ij）ij+β（ij）ijγ（ij）+β（ij），（15）

其中，γ（·）和β（·）是轉(zhuǎn)換函數(shù)，用于調(diào)整特征相關(guān)性和結(jié)構(gòu)相關(guān)性.在本文中使用Sigmoid作為轉(zhuǎn)換函數(shù)，有：γ（ij）=11+e-ij，（16）

β（ij）=11+e-ij.（17）

在獲得聯(lián)合注意力分?jǐn)?shù)后，執(zhí)行特征加權(quán)聚合用來更新每個節(jié)點的特征，并傳播到下一層或被用于后續(xù)學(xué)習(xí)任務(wù)的最終表征：

h（l+1）i=σ（∑j∈NiαijWh（l）j），（18）

其中，σ（·）為激活函數(shù)，αij為節(jié)點i和節(jié)點j之間的聯(lián)合注意力分?jǐn)?shù)，h（l）j為節(jié)點j在第l層的向量表示.

具體的算法如算法1所示.

算法1" 基于相似網(wǎng)絡(luò)和聯(lián)合注意力的圖嵌入模型（SiCAT）.

輸入" 圖G=（V，E），特征矩陣X，鄰接矩陣A.

輸出" 嵌入矩陣H

①" 根據(jù)指定的節(jié)點相似性度量指標(biāo)計算節(jié)點相似性，得到圖的相似度矩陣S，

②" 根據(jù)式（2）計算相似網(wǎng)絡(luò)鄰接矩陣，構(gòu)建相似網(wǎng)絡(luò)G′，

③" 根據(jù)式（11）和（13）分別計算節(jié)點內(nèi)容相關(guān)性和結(jié)構(gòu)相關(guān)性sij，

④" 根據(jù)式（16）和（17）使用轉(zhuǎn)換函數(shù)調(diào)整內(nèi)容相關(guān)性和結(jié)構(gòu)相關(guān)性，根據(jù)式（15）計算最終注意力分?jǐn)?shù)αij，

⑤" 根據(jù)式（18）進(jìn)行節(jié)點特征加權(quán)聚合，得到節(jié)點i的向量嵌入表示hi，

⑥" 利用隨機(jī)梯度迭代更新權(quán)重，直到收斂到局部最優(yōu)或達(dá)到訓(xùn)練次數(shù)上限，

⑦" end for.

4" 實驗分析

本節(jié)首先介紹了實驗所使用的數(shù)據(jù)集以及相關(guān)實驗設(shè)置，后使用多個基準(zhǔn)數(shù)據(jù)集對提出的模型進(jìn)行實證分析，并多個圖嵌入學(xué)習(xí)算法進(jìn)行對比，對實驗結(jié)果進(jìn)行分析，驗證本算法的優(yōu)越性.

4.1" 數(shù)據(jù)集及實驗配置

本文使用3個經(jīng)典基準(zhǔn)數(shù)據(jù)集（Cora、Citeseer和Pubmed）［27］進(jìn)行實驗，數(shù)據(jù)集統(tǒng)計信息如表1所示.以上3個數(shù)據(jù)集被廣泛應(yīng)用于各種圖嵌入算法評估實驗，它們均屬于引文網(wǎng)絡(luò)，其中節(jié)點表示論文，連邊表示論文之間的引用關(guān)系，特征表示論文的屬性信息，如作者、年份、研究主題等.本實驗的下游學(xué)習(xí)任務(wù)為節(jié)點分類，最終通過使用節(jié)點分類的準(zhǔn)確率評估所有算法的有效性.

實驗中，首先分別使用CA、Jaccard、AA、HDI 4個相似性度量指標(biāo)計算節(jié)點相似性，初始相似度閾值α為0.本文方法的網(wǎng)絡(luò)結(jié)構(gòu)遵循GAT算法結(jié)構(gòu)設(shè)置，采用兩層消息傳遞層和多頭注意力機(jī)制.第一層，8個注意力頭中的每一個注意力頭都學(xué)習(xí)一個轉(zhuǎn)換矩陣W∈Rd×8；第二層，在來自第一層8個注意力頭產(chǎn)生的級聯(lián)特征上使用轉(zhuǎn)換矩陣W∈R64×C（C為節(jié)點的標(biāo)簽數(shù)），采用一個注意頭后跟一個softmax算子.

使用Adam優(yōu)化器來學(xué)習(xí)參數(shù)模型，初始學(xué)習(xí)率r為0.005，衰減系數(shù)為0.000 5.為了防止模型過度擬合，在實驗中引入提前停止策略.模型的輸入維度為節(jié)點的初始特征維度，隱藏層嵌入向量維數(shù)為8.迭代輪數(shù)e設(shè)置為1 000，對于每個數(shù)據(jù)集，所有方法運行10次以獲得穩(wěn)定的統(tǒng)計數(shù)據(jù)，實驗結(jié)果取平均值記錄.

為了驗證算法的有效性，本文將模型與具有代表性的圖嵌入算法在節(jié)點分類問題上進(jìn)行對比，包括Deepwalk［3］、GCN［11］、GraphSAGE［14］、GAT［4］、ADSF［19］、superGAT［20］和GOAT［21］等.

4.2" 實驗結(jié)果

本文算法及上述基線在節(jié)點分類任務(wù)上的實驗結(jié)果如表2所示，粗體表示SiCAT獲得了比其他基線更好的表現(xiàn).本文提出的基于相似網(wǎng)絡(luò)的聯(lián)合注意力圖嵌入模型根據(jù)所選用的相似性計算方法不同有4個變體，分別是SiCAT-CN、SiCAT-Jac、SiCAT-HDI和SiCAT-AA.本文所提算法對節(jié)點分類的提升效果較為顯著，通過分析數(shù)據(jù)集節(jié)點平均度的變化可以得到解釋，原始網(wǎng)絡(luò)與相似網(wǎng)絡(luò)節(jié)點平均度對比如圖2所示.

根據(jù)表2可見，SiCAT-Jac、SiCAT-AA、SiCAT-CN 3種算法在3個數(shù)據(jù)集中的表現(xiàn)全部優(yōu)于所有基線方法，其中SiCAT-AA算法綜合結(jié)果最優(yōu)，與原始GAT相比分別提高了2.70%、3.94%和2.60%，因此在后續(xù)的分析研究中均以SiCAT-AA為例進(jìn)行研究分析.

Cora、Citeseer和Pubmed 3個數(shù)據(jù)集原始網(wǎng)絡(luò)中節(jié)點的平均度分別為3.9、2.8和4.5.數(shù)據(jù)集中的節(jié)點的平均度較低，即每個節(jié)點連接的鄰居節(jié)點數(shù)量較少，從而導(dǎo)致在特征聚合過程中每個節(jié)點可利用的鄰居節(jié)點特征信息較少.引入相似網(wǎng)絡(luò)后3個數(shù)據(jù)集中節(jié)點平均度分別增加4.4、3.4和5.9，有效提高了節(jié)點的平均度.每個節(jié)點的一階鄰居節(jié)點數(shù)量增多，使模型可以充分地利用更多的節(jié)點特征信息.

4.3" 可視化

本小節(jié)進(jìn)行可視化任務(wù).以SiCAT-AA算法為例，Cora、Citeseer和Pubmed 3個數(shù)據(jù)集上的節(jié)點利用本算法得到節(jié)點嵌入向量，將嵌入向量作為TSNE（T-distributed stochastic neighbor embedding）的輸入，進(jìn)行降維轉(zhuǎn)化為二維向量表示.同一類節(jié)點用相同的顏色進(jìn)行表示，可視化結(jié)果如圖3表示.可見在3個數(shù)據(jù)集中屬于同一類的節(jié)點大多能分配到一個簇中，體現(xiàn)了本文所提算法的有效性.

4.4" 對比實驗

為了進(jìn)一步驗證所提模型的有效性，設(shè)置本文所提算法與GAT對照實驗.對比實驗結(jié)果選用分類準(zhǔn)確率acc、損失函數(shù)與準(zhǔn)確率收斂趨勢演變進(jìn)行對比.在圖4中繪制了GAT和SiCAT的節(jié)點分類準(zhǔn)確率和損失函數(shù)的演變，可以看出隨著epoch的增加，SiCAT的準(zhǔn)確率accuracy和損失函數(shù)loss都逐漸收斂到穩(wěn)定的區(qū)域并達(dá)到更優(yōu)值，且與GAT相比收斂速度更快且收斂效果更好.

4.5" 超參數(shù)分析

本節(jié)研究超參數(shù)相似度閾值α對實驗結(jié)果的影響，引入相似度閾值α旨在過濾掉相似度值較低的節(jié)點對.在圖注意力網(wǎng)絡(luò)中，增加鄰居節(jié)點的數(shù)量不一定能夠有效提取節(jié)點的結(jié)構(gòu)特征，反而可能會產(chǎn)生噪聲節(jié)點，因此對于相似節(jié)點邊的構(gòu)建需要進(jìn)行一定的限制.本文使用相似度閾值解決這一問題，設(shè)置初值為0，不斷增加其值，觀察分析實驗結(jié)果.在Cora、Citeseer和Pubmed 3個數(shù)據(jù)集上節(jié)點分類準(zhǔn)確率跟隨相似度閾值的變化趨勢分別如圖5所示.

對于Cora和Citeseer數(shù)據(jù)集，當(dāng)相似度閾值為4時，節(jié)點分類準(zhǔn)確率達(dá)到最高；對于Pubmed數(shù)據(jù)集，當(dāng)相似度閾值為5時，節(jié)點分類準(zhǔn)確率達(dá)到最高.可以看出，對于不同的數(shù)據(jù)集，相似度閾值的選取一般也不同.對于出現(xiàn)此結(jié)果的原因，本文分析認(rèn)為Pubmed數(shù)據(jù)集節(jié)點數(shù)遠(yuǎn)遠(yuǎn)大于Cora和Citeseer數(shù)據(jù)集，且原始網(wǎng)絡(luò)節(jié)點的平均度也是最大，因此原始網(wǎng)絡(luò)上的節(jié)點擁有更多的一階鄰居節(jié)點可以參與到特征聚合的過程中，對構(gòu)建新的一階鄰居節(jié)點的需求較小.

5" 總" 結(jié)

本文提出一種新的圖嵌入算法，考慮了在利用圖注意力網(wǎng)絡(luò)時如何利用節(jié)點的高階相似節(jié)點和節(jié)點結(jié)構(gòu)特征以獲得更好的嵌入表示.本文算法一方面利用高階相似節(jié)點補(bǔ)充特征聚合中可利用的節(jié)點信息，解決了實際網(wǎng)絡(luò)數(shù)據(jù)集中節(jié)點度較小、只使用節(jié)點一階鄰居信息而造成特征聚合不足的問題.另一方面解決了注意力分?jǐn)?shù)計算過程中對節(jié)點結(jié)構(gòu)特征考慮不足的問題.通過以上方法獲得更加全面準(zhǔn)確的注意力分?jǐn)?shù)，最終得到高質(zhì)量的嵌入表示.此外，本文所提算法在3個基準(zhǔn)數(shù)據(jù)集上的節(jié)點分類任務(wù)的實驗結(jié)果均好于基準(zhǔn)，驗證了模型的有效性，能夠?qū)W習(xí)到更好的嵌入向量.未來，計劃研究表示學(xué)習(xí)中的圖數(shù)據(jù)增強(qiáng)問題，解決圖神經(jīng)網(wǎng)絡(luò)模型中普遍存在的過渡平滑、非魯棒性等問題.

參" 考" 文" 獻(xiàn)

［1］ ""TONG N，TANG Y，CHEN B，et al.Representation learning using Attention Network and CNN for Heterogeneous networks［J］.Expert Systems with Applications，2021，185：115628.

［2］CHAMI I，YING R，R C，et al.Hyperbolic graph convolutional neural networks［J］.Advances in Neural Information Processing Systems，2019，32：4869-4880.

［3］PEROZZI B，AL-RFOU R，SKIENA S.DeepWalk：online learning of social representations［C］//Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining.［s.l.］：ACM，2014.

［4］VELICˇKOVIC′ P，CUCURULL G，CASANOVA A，et al.Graph attention networks［EB/OL］.［2023-05-13］.http：//arxiv.org/abs/1710.10903

［5］GAO H C，HUANG H.Deep attributed network embedding［C］//Twenty-Seventh International Joint Conference on Artificial Intelligence.Palo Alto：AAAI Press，2018.

［6］LI Q M，HAN Z C，WU X M.Deeper insights into graph convolutional networks for semi-supervised learning［C］//Proceedings of the AAAI conference on artificial intelligence.Palo Alto：AAAI Press，2018.

［7］BELKIN M，NIYOGI P.Laplacian eigenmaps and spectral techniques for embedding and clustering［M］.Cambridge：The MIT Press，2002.

［8］HE X F，NIYOGI P.Locality preserving projections［C］//Proceedings of the 16th International Conference on Neural Information Processing Systems.［s.l.］：ACM，2003.

［9］GROVER A，LESKOVEC J.node2vec：scalable feature learning for networks［J］.KDD：Proceedings International Conference on Knowledge Discovery amp; Data Mining，2016，2016：855-864.

［10］MIKOLOV T，CHEN K，CORRADO G，et al.Efficient estimation of word representations in vector space［J］.ArXiv e-Prints，2013.arXiv：1301.3781.

［11］KIPF T N，WELLING M.Semi-supervised classification with graph convolutional networks［J］.ArXiv e-Prints，2016.arXiv：1609.02907.

［12］BRUNA J，ZAREMBA W，SZLAM A，et al.Spectral networks and locally connected networks on graphs［J］.ArXiv e-Prints，2013.arXiv：1312.6203.

［13］WU F，SOUZA A，ZHANG T，et al.Simplifying graph convolutional networks［C］//International conference on machine learning.Lille：PMLR，2019.

［14］HAMILTON W L，YING R，LESKOVEC J.Inductive representation learning on large graphs［C］//Proceedings of the 31st International Conference on Neural Information Processing Systems.［s.l.］：ACM，2017.

［15］DUVENAUD D，MACLAURIN D，AGUILERA-IPARRAGUIRRE J，et al.Convolutional networks on graphs for learning molecular fingerprints［C］//Proceedings of the 28th International Conference on Neural Information Processing Systems-Volume 2.［s.l.］：ACM，2015.

［16］LUONG T，PHAM H，MANNING C D.Effective approaches to attention-based neural machine translation［J］.arXiv preprint，2015.arXiv：150804025.

［17］XU K，BA J L，KIROS R，et al.Show，attend and tell：neural image caption generation with visual attention［C］//Proceedings of the 32nd International Conference on International Conference on Machine Learning-Volume 37.［s.l.］：ACM，2015.

［18］HE T，ONG Y S，BAI L.Learning conjoint attentions for graph neural nets［J］.Advances in Neural Information Processing Systems，2021，34：2641-53.

［19］ZHANG K，ZHU Y，WANG J，et al.Adaptive structural fingerprints for graph attention networks.［EB/OL］.［2023-05-09］.https：//openreview.net/forum？id=BJxWx0NYPr.

［20］KIM D，OH A.How to find your friendly neighborhood：graph attention design with self-supervision［EB/OL］.［2023-05-12］.http：//arxiv.org/abs/2204.04879

［21］CHATZIANASTASIS M，LUTZEYER J，DASOULAS G，et al.Graph ordering attention networks［J］.Proceedings of the AAAI Conference on Artificial Intelligence，2023，37（6）：7006-7014.

［22］JIN W，DERR T，WANG Y Q，et al.Node similarity preserving graph convolutional networks［C］//Proceedings of the 14th ACM International Conference on Web Search and Data Mining.［s.l.］：ACM，2021.

［23］NEWMAN M E.Clustering and preferential attachment in growing networks［J］.Physical Review E，Statistical，Nonlinear，and Soft Matter Physics，2001，64（2 Pt 2）：025102.

［24］JACCARD P.The distribution of the flora in the alpine zone.1［J］.New Phytologist，1912，11（2）：37-50.

［25］LIBEN-NOWELL D，KLEINBERG J.The link prediction problem for social networks［C］//Proceedings of the twelfth international conference on Information and knowledge management.［s.l.］：ACM，2003.

［26］ZHOU T，LYU L Y，ZHANG Y C.Predicting missing links via local information［J］.The European Physical Journal B，2009，71（4）：623-630.

［27］SEN P，NAMATA G，BILGIC M，et al.Collective classification in network data［J］.AI Magazine，2008，29（3）：93-106.

A graph embedding model based on similar networks and joint attention

Wang Jinghong1a，b，c， Li Changxin1a， Yang Jiateng2， Yu Fuqiang1a

（1. a. College of Computer and Cyber Security;" b. Hebei Key Laboratory of Network and Information Security; c. Hebei Provincial

Engineering Research Center for Supply Chain Big Data Analytics amp; Security， Hebei Normal University， Shijiazhuang 050024，

China; 2. Artificial Intelligence and Big Data， Hebei Polytechnic Institute， Shijiazhuang 050020， China）

Abstract： The Graph Attention Network（GAT） incorporates the attention mechanism into graph neural networks. However， the model only considers the first-order neighborhood nodes of nodes， neglecting the consideration of higher-order similar nodes， and fails to account for the structural features of nodes when calculating the attention score. To address this issue， this paper propose a graph embedding model based on higher-order similar nodes and joint attention. Specifically， our approach first computes node similarities in the network and subsequently constructs new edges between pairs of nodes that are highly similar but not directly connected， thus forming a similar network. Secondly， we introduce the notions of structural relevance and content relevance to respectively characterize structural relationships and content features among nodes. Finally， we perform weighted aggregation of the node features using joint attention scores to obtain the final node embedding representations. The accuracy improvement over traditional models was found to be 2.70%， 3.94%， and 2.60%， respectively. These results demonstrate that the proposed method yields a better representation of node embedding.

Keywords： graph embedding; graph attention network; node similarity; similar network; node classification

［責(zé)任編校" 陳留院" 趙曉華］