摘要：復(fù)雜網(wǎng)絡(luò)中的節(jié)點(diǎn)往往形成一些頻繁出現(xiàn)且具有特定局部連接模式的高階子結(jié)構(gòu)，利用這些高階子結(jié)構(gòu)可以更好地刻畫網(wǎng)絡(luò)的拓?fù)涮卣骷跋嚓P(guān)功能模塊。通過度量節(jié)點(diǎn)間的結(jié)構(gòu)相似性，有助于研究拓?fù)浣Y(jié)構(gòu)中節(jié)點(diǎn)之間的交互模式，理解復(fù)雜網(wǎng)絡(luò)的局部結(jié)構(gòu)和功能。為更充分利用節(jié)點(diǎn)鄰域的高階結(jié)構(gòu)信息，提出了一種利用節(jié)點(diǎn)鄰域內(nèi)的k 元節(jié)點(diǎn)組標(biāo)簽信息的結(jié)構(gòu)相似性判定方法GANNLI（Group-based Aggregated Neighborhood Label Information）。該方法首先將k 元節(jié)點(diǎn)組形成的非同構(gòu)子圖作為其組標(biāo)簽，再利用WL方法對k 元節(jié)點(diǎn)組的鄰域組標(biāo)簽信息進(jìn)行聚合和更新，統(tǒng)計節(jié)點(diǎn)所構(gòu)成的不同k 元組的標(biāo)簽信息以得到節(jié)點(diǎn)表示，并利用余弦相似度計算節(jié)點(diǎn)間的結(jié)構(gòu)相似性。與僅考慮節(jié)點(diǎn)度、接近中心性等低階信息的方法相比，本方法利用高階k 元組結(jié)構(gòu)信息更有效地度量了節(jié)點(diǎn)間的結(jié)構(gòu)相似性。在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，所提出的GANNLI算法能更有效地計算節(jié)點(diǎn)間的結(jié)構(gòu)相似性，在節(jié)點(diǎn)分類任務(wù)中的性能相比Struc2vec提高了2%至6%，相比Node2vec提高了8%至14%。

關(guān)鍵詞：復(fù)雜網(wǎng)絡(luò)；結(jié)構(gòu)相似性；k元組；高階結(jié)構(gòu)；Weisfeiler-Lehman方法

中圖分類號：O436 文獻(xiàn)標(biāo)志碼：A 文章編號：0253-2395（2024）05-0993-11

0 引言

通常用G = （V，E ） 來表示節(jié)點(diǎn)集V，邊集E的圖G。節(jié)點(diǎn)作為圖數(shù)據(jù)的基本元素，網(wǎng)絡(luò)中功能相似的節(jié)點(diǎn)在結(jié)構(gòu)和屬性等方面有較高的相似性。節(jié)點(diǎn)相似性的研究在識別社交網(wǎng)絡(luò)中心節(jié)點(diǎn)和分類交通網(wǎng)絡(luò)中的樞紐節(jié)點(diǎn)重要性等方面應(yīng)用廣泛?；诠?jié)點(diǎn)自身的屬性信息來度量節(jié)點(diǎn)間的相似性通常不考慮節(jié)點(diǎn)間的拓?fù)溥B接，兩個節(jié)點(diǎn)屬性越相似，其相似性越高。在社交網(wǎng)絡(luò)中，可以根據(jù)兩個人的年齡和興趣等信息判斷兩個人是否可能成為朋友；在交通網(wǎng)絡(luò)中，可以通過客運(yùn)量和行程車速等節(jié)點(diǎn)屬性的相似性識別關(guān)鍵樞紐節(jié)點(diǎn)。

實(shí)際上，節(jié)點(diǎn)鄰域的拓?fù)浣Y(jié)構(gòu)在很大程度上決定了該節(jié)點(diǎn)在網(wǎng)絡(luò)中所行使的功能，如社交網(wǎng)絡(luò)中不同社區(qū)的中心節(jié)點(diǎn)具有相似的鄰域拓?fù)浣Y(jié)構(gòu)；無標(biāo)度網(wǎng)絡(luò)中的Hub 節(jié)點(diǎn)與網(wǎng)絡(luò)中其他節(jié)點(diǎn)緊密連接；生物網(wǎng)絡(luò)中代謝通路關(guān)鍵蛋白質(zhì)節(jié)點(diǎn)傾向于大度節(jié)點(diǎn)。可以從結(jié)構(gòu)相似性和同質(zhì)相似性［1-3］兩個角度對節(jié)點(diǎn)間的鄰域拓?fù)浣Y(jié)構(gòu)相似性進(jìn)行描述。同質(zhì)相似性從共同鄰居角度計算節(jié)點(diǎn)間相似性，如果兩個節(jié)點(diǎn)共享較多的鄰居節(jié)點(diǎn)，則它們的同質(zhì)相似性較高。同質(zhì)相似性高的節(jié)點(diǎn)位于網(wǎng)絡(luò)中同一社區(qū)的可能性更大。

結(jié)構(gòu)相似性利用更豐富的鄰域拓?fù)湫再|(zhì)定義節(jié)點(diǎn)間的相似性，如節(jié)點(diǎn)度、鄰居節(jié)點(diǎn)度分布、接近中心性、聚集系數(shù)等信息。結(jié)構(gòu)相似性較高的節(jié)點(diǎn)可能位于網(wǎng)絡(luò)的不同社區(qū)，甚至位于不同的連通分量。如在社交網(wǎng)絡(luò)不同社區(qū)中角色相似的節(jié)點(diǎn)往往有較高的結(jié)構(gòu)相似性［4］；在交通網(wǎng)絡(luò)中不同區(qū)域的樞紐節(jié)點(diǎn)間結(jié)構(gòu)相似性較高。早期的節(jié)點(diǎn)結(jié)構(gòu)相似性計算方法如REGE 和面向分類型數(shù)據(jù)的REGE 算法（CATegorical REGE，CATREGE）迭代搜索節(jié)點(diǎn)鄰居的最優(yōu)匹配［5］，時間復(fù)雜度較高，無法應(yīng)用于大規(guī)模網(wǎng)絡(luò)?；诒硎緦W(xué)習(xí)的結(jié)構(gòu)相似性計算方法Struc2vec［6］基于節(jié)點(diǎn)鄰域內(nèi)度分布構(gòu)造相似圖，在其上隨機(jī)游走獲取節(jié)點(diǎn)鄰域上下文，以學(xué)習(xí)得到節(jié)點(diǎn)表示。然而，隨機(jī)游走過程帶來的隨機(jī)性，可能導(dǎo)致結(jié)構(gòu)相似的節(jié)點(diǎn)得到不同的鄰域上下文，無法準(zhǔn)確度量節(jié)點(diǎn)間的結(jié)構(gòu)相似性。

實(shí)際上，網(wǎng)絡(luò)中的節(jié)點(diǎn)間往往成組作用，形成一些頻繁出現(xiàn)且具有特定局部連接模式的高階子結(jié)構(gòu)。利用這些高階子結(jié)構(gòu)可以更好地刻畫網(wǎng)絡(luò)的拓?fù)涮卣骷捌湎嚓P(guān)的功能模塊［7］。例如在社會學(xué)中，通過網(wǎng)絡(luò)中三角形的相對數(shù)量來描述網(wǎng)絡(luò)的聚類特性；在分子化學(xué)中，官能團(tuán)和環(huán)與物質(zhì)的化學(xué)性質(zhì)密切相關(guān)；在蛋白質(zhì)研究中，類簇結(jié)構(gòu)在構(gòu)建蛋白質(zhì)相關(guān)作用網(wǎng)絡(luò)中起到關(guān)鍵作用［8］。利用節(jié)點(diǎn)成組結(jié)構(gòu)特征度量節(jié)點(diǎn)間的結(jié)構(gòu)相似性，在社交網(wǎng)絡(luò)節(jié)點(diǎn)角色識別、交通網(wǎng)絡(luò)樞紐節(jié)點(diǎn)重要性分類等方面具有廣泛的應(yīng)用和重要的實(shí)用價值。

為更充分利用網(wǎng)絡(luò)高階結(jié)構(gòu)信息，本文提出了一種利用節(jié)點(diǎn)鄰域內(nèi)的k 元節(jié)點(diǎn)組標(biāo)簽信息的結(jié)構(gòu)相似性判定方法GANNLI （Aggrega?tion Label Information of k-tuple Group in NodeNeighborhood）。該方法首先按k 元節(jié)點(diǎn)組形成的非同構(gòu)子圖作為其組標(biāo)簽，再利用WL 方法對k 元節(jié)點(diǎn)組的鄰域組標(biāo)簽信息進(jìn)行聚合，并更新組標(biāo)簽；統(tǒng)計節(jié)點(diǎn)所構(gòu)成的不同k 元組的標(biāo)簽信息得到節(jié)點(diǎn)表示；并利用余弦相似度計算節(jié)點(diǎn)間的結(jié)構(gòu)相似性。與僅考慮節(jié)點(diǎn)度、接近中心性等低階信息的方法相比，本方法利用高階k 元組結(jié)構(gòu)信息更有效地度量了節(jié)點(diǎn)間的結(jié)構(gòu)相似性。在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上實(shí)驗(yàn)結(jié)果表明，利用節(jié)點(diǎn)組信息的結(jié)構(gòu)相似性提高了節(jié)點(diǎn)分類任務(wù)的精確度。

1 相關(guān)工作

節(jié)點(diǎn)間相似性度量是進(jìn)行圖數(shù)據(jù)分析以及進(jìn)行節(jié)點(diǎn)分類、節(jié)點(diǎn)聚類、鏈路預(yù)測、角色分析等下游任務(wù)的基礎(chǔ)。對節(jié)點(diǎn)間結(jié)構(gòu)相似性的度量，利用更豐富的鄰域拓?fù)湫再|(zhì)，在社交網(wǎng)絡(luò)節(jié)點(diǎn)角色識別、交通網(wǎng)絡(luò)樞紐節(jié)點(diǎn)重要性分類等方面應(yīng)用廣泛，具有重要的實(shí)用價值。如在Facebook、微博等社交網(wǎng)絡(luò)中，可以發(fā)現(xiàn)不同社區(qū)中相同角色的人，從而提高對用戶的針對性推薦和廣告投放等工作的準(zhǔn)確度；在交通網(wǎng)絡(luò)中，識別重要樞紐節(jié)點(diǎn)，對重要樞紐節(jié)點(diǎn)予以保護(hù)。

圖數(shù)據(jù)中節(jié)點(diǎn)相似性的度量，可以從同質(zhì)相似性和結(jié)構(gòu)相似性兩方面進(jìn)行描述。同質(zhì)相似性通常根據(jù)節(jié)點(diǎn)之間的路徑連通信息計算節(jié)點(diǎn)間的相似性。公共鄰居相似性（CN）［9］、杰卡德相似性（Jaccard）［10］、Adamic-Adar 相似性（AA）［11］等利用節(jié)點(diǎn)間的公共鄰居信息計算相似性。其中公共鄰居相似性指標(biāo)［9］利用節(jié)點(diǎn)間公共鄰居絕對數(shù)量計算相似性，杰卡德相似性指標(biāo)［10］利用節(jié)點(diǎn)間公共鄰居數(shù)量在兩者所有鄰居中的占比計算相似性。Zhou 等基于網(wǎng)絡(luò)資源分配的思想提出了資源分配相似性指標(biāo)（RA）［12］，以節(jié)點(diǎn)間的公共鄰居作為傳播媒介，將自身所擁有的資源平均分配給它的鄰居，利用鄰居節(jié)點(diǎn)可以接收到的資源數(shù)作為二者間的相似性值。Adamic 等考慮到圖數(shù)據(jù)度分布的偏態(tài)性影響提出Adamic-Adar 相似性指標(biāo)（AA）［11］?；诠侧従拥南嗨菩远攘勘举|(zhì)上利用了節(jié)點(diǎn)間的2-路徑信息，若兩節(jié)點(diǎn)間擁有較多的2- 路徑，則它們擁有較多的公共鄰居。為了更充分地利用節(jié)點(diǎn)間的路徑連通信息以計算相似性，研究者根據(jù)節(jié)點(diǎn)間不同長度的路徑數(shù)、節(jié)點(diǎn)間隨機(jī)游走概率等定義了節(jié)點(diǎn)間的相似性。Katz 指標(biāo)利用網(wǎng)絡(luò)中節(jié)點(diǎn)之間的所有路徑進(jìn)行相似性計算，越短的路徑賦予越高的權(quán)重。Zhou 等根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)間長度為2 和3 的路徑數(shù)定義節(jié)點(diǎn)間的局部路徑相似性度量（Lo?cal Path Similarity Index，LP）指標(biāo)［12-13］。2015 年Chen 等根據(jù)網(wǎng)絡(luò)中節(jié)點(diǎn)間的長度不超過3 的路徑數(shù)定義節(jié)點(diǎn)間的局部相似性指標(biāo)（Local Sim?ilarity Index，LS）［14］。隨著表示學(xué)習(xí)技術(shù)的發(fā)展，有很多的學(xué)者提出了一系列的對圖結(jié)構(gòu)進(jìn)行表示學(xué)習(xí)的算法。2014 年，Perozzi 等提出DeepWalk［15］算法，在節(jié)點(diǎn)局部鄰域上采用隨機(jī)游走的思想進(jìn)行節(jié)點(diǎn)采樣得到節(jié)點(diǎn)路徑序列，將路徑作為語言模型的輸入得到節(jié)點(diǎn)的學(xué)習(xí)表示。2016 年，Grover 等［16］針對DeepWalk 算法中節(jié)點(diǎn)之間游走概率相等的缺點(diǎn)提出了Node2vec算法，通過引入?yún)?shù)p 和q，控制隨機(jī)游走的廣度和深度，可以更加靈活地捕捉節(jié)點(diǎn)的上下文信息?；诼窂降南嗨菩远攘繑U(kuò)大了鄰域節(jié)點(diǎn)的探索范圍，可以在更廣泛鄰域內(nèi)對節(jié)點(diǎn)間相似性進(jìn)行度量。然而因?yàn)榇蠖裙?jié)點(diǎn)與其他節(jié)點(diǎn)的關(guān)系緊密，度越大的節(jié)點(diǎn)在生成路徑時被訪問的概率越大，使得許多節(jié)點(diǎn)最相似的是大度節(jié)點(diǎn)［17］。

節(jié)點(diǎn)間的結(jié)構(gòu)相似性度量了節(jié)點(diǎn)及周圍鄰域的拓?fù)浣Y(jié)構(gòu)信息，如節(jié)點(diǎn)度［18］、鄰居節(jié)點(diǎn)度分布、接近中心性、節(jié)點(diǎn)間距離分布、聚集系數(shù)等信息。Zhang 等基于一階鄰域度特征信息提出了局部相對方法（Local Relative Entropy，LRE）［19］，利用節(jié)點(diǎn)一階鄰域度分布描述其鄰域拓?fù)浣Y(jié)構(gòu)，利用相對熵計算節(jié)點(diǎn)一階鄰域度分布差異以得到節(jié)點(diǎn)間的相似性。Mu 等提出了基于節(jié)點(diǎn)間距離分布的結(jié)構(gòu)相似性度量方法DDRE（Distance Distribution and Relative EntropybasedSimilarity）［20］，通過節(jié)點(diǎn)之間的最短路徑定義節(jié)點(diǎn)的距離分布，DDRE 需要遍歷網(wǎng)絡(luò)中所有節(jié)點(diǎn)，計算代價較高。Zou 等將節(jié)點(diǎn)相似性矩陣與平均聚合機(jī)制相結(jié)合對圖神經(jīng)網(wǎng)絡(luò)的鄰域聚合機(jī)制進(jìn)行改進(jìn)［21］。Ribeiro 等基于語言模型提出了算法Struc2vec ［6］，利用節(jié)點(diǎn)鄰域內(nèi)度序列得到節(jié)點(diǎn)間的相似性，并作為節(jié)點(diǎn)間路徑權(quán)重利用隨機(jī)游走得到節(jié)點(diǎn)在拓?fù)浣Y(jié)構(gòu)相似圖上的鄰域上下文，最終學(xué)習(xí)得到反映節(jié)點(diǎn)結(jié)構(gòu)相似性的潛在表示。然而隨機(jī)游走過程帶來的隨機(jī)性，導(dǎo)致結(jié)構(gòu)完全相同的兩個節(jié)點(diǎn)得到的鄰域上下文會存在不同，從而使得結(jié)構(gòu)完全相同的兩個節(jié)點(diǎn)得到的嵌入表示存在一定的距離。

2 背景知識

2.1 基本概念

用G = （V，E ） 來表示圖數(shù)據(jù)，其中V （G ） ={ v1，…，vn } 表示圖數(shù)據(jù)中實(shí)體的集合，|V （G ）| =n 表示圖數(shù)據(jù)中的實(shí)體數(shù)量，E （G ） 表示圖數(shù)據(jù)中實(shí)體間關(guān)系的集合，|E （G ）| = m 代表實(shí)體間關(guān)系的數(shù)量。在圖G 中，節(jié)點(diǎn)vi 的一階鄰域表示為N （ vi ） = { vj：（ vi，vj ） ∈ E （G ） }， 節(jié)點(diǎn)vj ∈ N （ vi ） 稱為節(jié)點(diǎn)vi 的一階鄰居。節(jié)點(diǎn)vi 的度為d （ vi ） = |N （ vi ）| 表示圖G 中與節(jié)點(diǎn)vi 有連邊的節(jié)點(diǎn)數(shù)，簡記di。假設(shè)圖S 為圖G 的一個節(jié)點(diǎn)數(shù)為k 的非空子圖，其節(jié)點(diǎn)集V （ S ） ={w1，…，wk }? V （G ） 且邊集E （ S ） = {（ wi，wj ）：wi，wj ∈ V （ S ） } ? E （G ），用[V （G ）]k表示所有節(jié)點(diǎn)數(shù)為k 的非空子圖的集合，將節(jié)點(diǎn)數(shù)為k 的非空子圖稱為圖G 的一個k 元節(jié)點(diǎn)組。

2.2 Weisfeiler-Lehman圖核

常見的圖核方法以圖的分解方式進(jìn)行分類，主要有基于路徑的圖核方法［22］、基于子圖的圖核方法［23］以及基于子樹的圖核方法［24］。這三類方法分別將圖分解為路徑、子圖、子樹等不同的組件，使用R- 卷積核［25］對比每對組件對圖的相似度進(jìn)行計算［26］，被廣泛應(yīng)用于藥物研發(fā)［27］、生物網(wǎng)絡(luò)鏈路預(yù)測［28］中。Weis?feiler-Lehman（WL）圖核方法［29-30］是使用頻率最高的基于子樹的圖核方法，它將WL 算法與核函數(shù)相結(jié)合以有效進(jìn)行圖結(jié)構(gòu)相似性分析。設(shè)待比較的兩個圖分別為G 和G' （|V （G ）|=|V （G' ）|），WL 算法迭代的為圖中的每個頂點(diǎn)賦予標(biāo)簽，若在某次迭代中兩圖對應(yīng)的標(biāo)簽序列不同，則可判定G 和G' 不同構(gòu)；若算法迭代|V （G ）| 次，對應(yīng)的標(biāo)簽序列仍相同，則兩圖同構(gòu)。每一次迭代主要分為四個步驟：標(biāo)簽初始化、鄰域標(biāo)簽表示、標(biāo)簽壓縮、重標(biāo)簽，分別對應(yīng)于圖1 中①、②、③、④。對網(wǎng)絡(luò)中的節(jié)點(diǎn)v，將其所有鄰居節(jié)點(diǎn)的標(biāo)簽排序得到鄰域標(biāo)簽字符串，合并v 標(biāo)簽與排序后的鄰域標(biāo)簽集，并利用hash 函數(shù)壓縮合并后的標(biāo)簽集合為一個新標(biāo)簽號以更新v 的標(biāo)簽。WL 算法為圖G 賦予標(biāo)簽的T 步迭代過程如算法1 所示。

當(dāng)網(wǎng)絡(luò)中節(jié)點(diǎn)信息較少時，WL 算法通常采用節(jié)點(diǎn)度作為初始標(biāo)簽，這導(dǎo)致算法不能很好地區(qū)分一些非同構(gòu)圖［31］，如圖2 所示的兩個圖由于具有相同的度序列，且每個節(jié)點(diǎn)的鄰居度也完全相同，導(dǎo)致WL 算法無法區(qū)分。這是由于算法1 中僅利用單個節(jié)點(diǎn)及其鄰域的度信息進(jìn)行圖同構(gòu)檢測，無法反映圖中節(jié)點(diǎn)在高階結(jié)構(gòu)方面的差異。針對此，Babai［30］提出了利用網(wǎng)絡(luò)中由k 個節(jié)點(diǎn)組成的高階結(jié)構(gòu)進(jìn)行圖同構(gòu)判定的方法，稱為k-Weisfeiler-Lehman 方法，簡稱k-WL 方法［31］，迭代地為網(wǎng)絡(luò)中的k 元節(jié)點(diǎn)組賦予標(biāo)簽，對比兩個網(wǎng)絡(luò)的k 元組標(biāo)簽在迭代過程的差異進(jìn)行同構(gòu)判定，用戶可根據(jù)網(wǎng)絡(luò)特征，選擇合適的k 來增強(qiáng)算法區(qū)分非同構(gòu)圖的能力。通常，k 越大則算法的圖同構(gòu)判定能力越強(qiáng)。顯然，WL 算法是k-WL 方法在k=1 時的特例。

盡管WL 算法是對兩個圖是否同構(gòu)進(jìn)行判定的，實(shí)際上，其迭代的賦予節(jié)點(diǎn)或節(jié)點(diǎn)組標(biāo)簽的過程，也是對節(jié)點(diǎn)或節(jié)點(diǎn)組進(jìn)行編碼的過程。局部鄰域范圍內(nèi)拓?fù)浣Y(jié)構(gòu)相似的節(jié)點(diǎn)通常會被賦予相似的標(biāo)簽，本文利用WL 算法的編碼過程對節(jié)點(diǎn)的局部鄰域結(jié)構(gòu)相似性進(jìn)行判定。

3 節(jié)點(diǎn)間結(jié)構(gòu)相似性度量方法GANNLI

3.1 k 元節(jié)點(diǎn)組的鄰域

為了提取k 元節(jié)點(diǎn)組的鄰域結(jié)構(gòu)，對k 元節(jié)點(diǎn)組P 的鄰域進(jìn)行了定義，如下式所示：

Γ（ P ）={ p1，…，pi - 1，q，pi + 1，…，pk：q ∈ N1 （ pi ）∧ q ? P }，

k 元節(jié)點(diǎn)組的鄰域Γ（ P ） 是通過用被替換節(jié)點(diǎn)pi的鄰域節(jié)點(diǎn)q ∈ N （ pi ） 來替換的，即被替換節(jié)點(diǎn)與替換節(jié)點(diǎn)之間有連邊。如圖3 所示，k 元節(jié)點(diǎn)組｛1， 2， 5｝的鄰域k 元節(jié)點(diǎn)組有｛1， 2， 4｝和｛1， 5， 6｝，其中｛1， 2， 4｝是節(jié)點(diǎn)5 的鄰域節(jié)點(diǎn)4 替換節(jié)點(diǎn)5 得到的，｛1， 5， 6｝是節(jié)點(diǎn)2 的鄰域節(jié)點(diǎn)6 替換節(jié)點(diǎn)2 得到的。

3.2 GANNLI方法

GANNLI 方法包括生成k 元節(jié)點(diǎn)組、k 元節(jié)點(diǎn)組組標(biāo)簽初始化、k 元節(jié)點(diǎn)組鄰域聚合、特征統(tǒng)計、節(jié)點(diǎn)間結(jié)構(gòu)相似性計算等5 個主要過程。首先，對于圖中所有的節(jié)點(diǎn)V （G ），生成k 元節(jié)點(diǎn)組的集合［V（G）］k。 判斷k 元節(jié)點(diǎn)組P 組成的子結(jié)構(gòu)類型作為k 元節(jié)點(diǎn)組的組標(biāo)簽。在k 元節(jié)點(diǎn)組鄰域聚合部分利用WL 方法對k 元節(jié)點(diǎn)組的鄰域組標(biāo)簽信息進(jìn)行聚合，并更新組標(biāo)簽。在特征統(tǒng)計過程中，對包含節(jié)點(diǎn)v 的k 元節(jié)點(diǎn)組的不同標(biāo)簽類型及對應(yīng)數(shù)量進(jìn)行統(tǒng)計，生成關(guān)于節(jié)點(diǎn)v 的特征向量F（v）。在節(jié)點(diǎn)間結(jié)構(gòu)相似性計算部分，使用余弦相似度，如式（1）所示。

cos （ F （ u ），F(xiàn) （ v ） ）= F （ u ）T F （ v ）／｜｜F（ u ）｜｜·｜｜F（ v ） ｜｜。（1）

對節(jié)點(diǎn)v 和節(jié)點(diǎn)u 的特征向量F（u）和F（v）進(jìn)行余弦相似度計算，從而得到節(jié)點(diǎn)v 和節(jié)點(diǎn)u之間的相似性。

算法2 給出了GANNLI 算法框架。

4 實(shí)驗(yàn)分析

4.1 k 元節(jié)點(diǎn)組表達(dá)能力分析

為了驗(yàn)證不同大小的k 元節(jié)點(diǎn)組對網(wǎng)絡(luò)結(jié)構(gòu)的表達(dá)能力，設(shè)計了一個驗(yàn)證實(shí)驗(yàn)。如圖4所示圖中有4 個連通分量，其節(jié)點(diǎn)可分為7 類（用不同顏色代表）。

圖5 展示了不同k 元節(jié)點(diǎn)組對圖4 的分類結(jié)果。當(dāng)k=1，圖中所有節(jié)點(diǎn)被識別為同一類。當(dāng)k=2 時，節(jié)點(diǎn)將按度分類，因此圖中節(jié)點(diǎn)被分為2 度點(diǎn)和3 度點(diǎn)；當(dāng)k=3 時，由于圖中黃色和粉色節(jié)點(diǎn)的所有3 元組構(gòu)成情況相同，因此被錯誤識別為同一類；而當(dāng)k=4 時，所有類別不同的節(jié)點(diǎn)的4 元組構(gòu)成情況各異，因此將所有節(jié)點(diǎn)都劃分到正確類別?？梢钥闯?，不同規(guī)模的k 元節(jié)點(diǎn)組對網(wǎng)絡(luò)中節(jié)點(diǎn)具有不同的表達(dá)能力，通常k越大，不同類別節(jié)點(diǎn)的k 元組構(gòu)成情況差別越明顯，因此算法的分類能力也增強(qiáng)。

4.2 真實(shí)網(wǎng)絡(luò)上的節(jié)點(diǎn)相似性比較

本節(jié)實(shí)驗(yàn)采用網(wǎng)絡(luò)是由兩個完全相同的跆拳道網(wǎng)絡(luò)（Karate）構(gòu)成的鏡像Karate 網(wǎng)絡(luò)，如圖6 所示，其中邊框顏色相同的節(jié)點(diǎn)互為鏡像節(jié)點(diǎn)。分別利用本節(jié)所提算法GANNLI 和傳統(tǒng)方法Struc2vec 得到鏡像Karate 網(wǎng)絡(luò)中節(jié)點(diǎn)的表示，其中將GANNLI 算法得到的最終標(biāo)簽向量作為節(jié)點(diǎn)表示。圖7 給出了用t-SNE 對兩種算法所得表示進(jìn)行降維可視化的效果圖，其中紅色結(jié)果展示本文算法的可視化結(jié)果，藍(lán)色結(jié)果展示Struc2vec 算法的可視化結(jié)果，坐標(biāo)系上方與右方的箱體分布圖分別表示橫縱方向上節(jié)點(diǎn)的分布結(jié)果。

從圖7 可以看出，互為鏡像的節(jié)點(diǎn)通過Struc2vec 算法所得到節(jié)點(diǎn)表示并不完全相同，而通過本文所提的GANNLI 方法可以得到完全相同的標(biāo)簽向量。這是由于Struc2vec 利用隨機(jī)游走得到節(jié)點(diǎn)特征序列以產(chǎn)生節(jié)點(diǎn)表示，而游走過程的隨機(jī)性可能使兩個結(jié)構(gòu)完全相同的節(jié)點(diǎn)得到不同的節(jié)點(diǎn)特征序列，從而導(dǎo)致它們最終的節(jié)點(diǎn)表示產(chǎn)生差異。除鏡像節(jié)點(diǎn)外，結(jié)構(gòu)相似性高的節(jié)點(diǎn)利用GANNLI 算法可以得到更相似的節(jié)點(diǎn)表示，如節(jié)點(diǎn)組｛15， 16， 19， 21，23｝在網(wǎng)絡(luò)中都僅與節(jié)點(diǎn)33 和34 相連，因此GANNLI 對這5 個節(jié)點(diǎn)給出了完全相同的標(biāo)簽向量，而節(jié)點(diǎn)1 和34 分別為真實(shí)社區(qū)中的中心節(jié)點(diǎn)，它們的標(biāo)簽向量也距離更近。

圖8 展示了GANNLI 和Struc2vec 算法對鏡像Karate 俱樂部網(wǎng)絡(luò)的節(jié)點(diǎn)表示與節(jié)點(diǎn)度之間的分布關(guān)系。由圖可知，兩種方法節(jié)點(diǎn)表示與節(jié)點(diǎn)度之間的分布相似，驗(yàn)證了本文所提方法GANNLI 利用k 元節(jié)點(diǎn)組對節(jié)點(diǎn)間結(jié)構(gòu)相似性計算的正確性。

圖9 展示了在鏡像Karate 網(wǎng)絡(luò)上，GANNLI與Struc2vec 方法得到節(jié)點(diǎn)表示間的距離分布對比情況，包括鏡像節(jié)點(diǎn)對間的距離分布以及所有節(jié)點(diǎn)對間的距離分布，其中標(biāo)記“+”的曲線為鏡像對之間的距離，標(biāo)記“×”的曲線為所有對之間的距離。由于本文所提算法GANNLI 賦予了鏡像節(jié)點(diǎn)對相同的標(biāo)簽向量，因此鏡像節(jié)點(diǎn)間的平均距離為0，而Struc2vec 鏡像節(jié)點(diǎn)間的平均距離為0.87。此外，GANNLI 方法所得表示的所有節(jié)點(diǎn)對的平均距離為9.34，而Struc2vec 方法所有節(jié)點(diǎn)對的平均距離為8.06，這表明所提方法得到的節(jié)點(diǎn)表示對網(wǎng)絡(luò)節(jié)點(diǎn)的區(qū)分性優(yōu)于Struc2vec。

4.3 在分類任務(wù)上的比較結(jié)果

節(jié)點(diǎn)分類任務(wù)是一個常見節(jié)點(diǎn)表示的下游任務(wù)。當(dāng)節(jié)點(diǎn)的標(biāo)簽與節(jié)點(diǎn)的結(jié)構(gòu)有關(guān)而不是與鄰居節(jié)點(diǎn)的標(biāo)簽有關(guān)時，分類時更應(yīng)該關(guān)注節(jié)點(diǎn)間的結(jié)構(gòu)相似性。本節(jié)使用空中交通網(wǎng)絡(luò)數(shù)據(jù)集來驗(yàn)證所提算法GANNLI 對節(jié)點(diǎn)間結(jié)構(gòu)相似性的判別能力。數(shù)據(jù)集包含巴西空中交通網(wǎng)絡(luò)（Brazil_airports）、美國空中交通網(wǎng)絡(luò)（USA_airports）和歐洲空中交通網(wǎng)絡(luò)（Eu?rope_airports）等3 個無權(quán)無向網(wǎng)絡(luò)，其中節(jié)點(diǎn)代表機(jī)場，邊表示機(jī)場間存在直達(dá)航班。根據(jù)機(jī)場的航班或人員的活動水平為機(jī)場分配標(biāo)簽。對每個數(shù)據(jù)集，按照機(jī)場活動水平將機(jī)場分為四組，按機(jī)場活動水平排名前25%、25%～50%、50%～75%、后25% 賦予4 類不同標(biāo)簽。

巴西空中交通網(wǎng)絡(luò)（Brazil_airports）：從巴西國家民航局（ANAC）收集2016 年1 月至12月的數(shù)據(jù)，有131 個節(jié)點(diǎn)，1 038 個邊（直徑為5）。機(jī)場活動水平通過對應(yīng)時期的航班起降總數(shù)來衡量。

美國空中交通網(wǎng)絡(luò)（USA_airports）：數(shù)據(jù)收集自美國交通統(tǒng)計局2016 年1 月至10 月，有1 190 個節(jié)點(diǎn)，13 599 個邊（直徑為8）。機(jī)場活動水平通過對應(yīng)時期通過機(jī)場客流量來衡量。

歐洲空中交通網(wǎng)絡(luò)（Europe_airports）：從歐盟統(tǒng)計局（Eurostat）收集的2016 年1 月至11月的數(shù)據(jù)，有399 個節(jié)點(diǎn)，5 995 個邊（直徑為5）。機(jī)場活動水平通過對應(yīng)時期的航班起降總數(shù)來衡量。

本節(jié)將所提方法GANNLI 所得的節(jié)點(diǎn)表示用于分類任務(wù)，在空中交通網(wǎng)絡(luò)數(shù)據(jù)集上，與Struc2vec、Node2vec 算法所得的節(jié)點(diǎn)表示進(jìn)行對比實(shí)驗(yàn)。對Node2vec，采用節(jié)點(diǎn)度作為節(jié)點(diǎn)的特征信息，由采樣節(jié)點(diǎn)的度信息構(gòu)成采樣路徑信息。GANNLI 算法采用節(jié)點(diǎn)的3 元組標(biāo)簽信息，即k=3。采用支持向量機(jī)（SVM）、決策樹（DTree）、邏輯回歸（LR）等3 種分類器評價節(jié)點(diǎn)表示的分類性能，實(shí)驗(yàn)比較結(jié)果如圖10 所示?？梢钥吹?，GANNLI 算法在巴西空中交通網(wǎng)絡(luò)（Brazil_airports）、美國空中交通網(wǎng)絡(luò)（USA_airports）和歐洲空中交通網(wǎng)絡(luò)（Eu?rope_airports）等數(shù)據(jù)集上的分類性能相比Struc2vec 提高了2% 至6%，相比Node2vec 提高了8% 至14%。

5 總結(jié)

本文提出一種利用節(jié)點(diǎn)鄰域內(nèi)的k 元節(jié)點(diǎn)組標(biāo)簽信息的結(jié)構(gòu)相似性判定方法GANN?LI ，首先按k 元節(jié)點(diǎn)組形成的非同構(gòu)子圖作為其組標(biāo)簽，再利用WL 方法對k 元節(jié)點(diǎn)組的鄰域組標(biāo)簽信息進(jìn)行聚合，并更新組標(biāo)簽；統(tǒng)計節(jié)點(diǎn)所構(gòu)成的不同k 元組的標(biāo)簽信息得到節(jié)點(diǎn)表示；利用余弦相似度計算節(jié)點(diǎn)間的結(jié)構(gòu)相似性。在真實(shí)網(wǎng)絡(luò)數(shù)據(jù)集上實(shí)驗(yàn)結(jié)果表明，本文算法GANNLI 能更有效地計算節(jié)點(diǎn)間的結(jié)構(gòu)相似性，從而提高節(jié)點(diǎn)分類任務(wù)的性能。

下一步，GANNLI 算法可以進(jìn)一步優(yōu)化，以適應(yīng)更大規(guī)模的網(wǎng)絡(luò)數(shù)據(jù)和更加復(fù)雜的網(wǎng)絡(luò)結(jié)構(gòu)。此外，將該方法應(yīng)用于其他類型的圖分析任務(wù)，如社區(qū)發(fā)現(xiàn)、鏈路預(yù)測和圖嵌入等，可能會帶來更多有價值的發(fā)現(xiàn)。結(jié)合其他先進(jìn)的圖神經(jīng)網(wǎng)絡(luò)技術(shù)，GANNLI 有望在更廣泛的應(yīng)用領(lǐng)域中發(fā)揮更大的作用，提高復(fù)雜網(wǎng)絡(luò)分析的精度和效率。進(jìn)一步的研究還可以探索如何在動態(tài)網(wǎng)絡(luò)環(huán)境 中有效地應(yīng)用和擴(kuò)展GANNLI，以應(yīng)對實(shí)時數(shù)據(jù)變化帶來的挑戰(zhàn)。

參考文獻(xiàn)：

[1] FORTUNATO S. Community Detection in Graphs[J].Phys Rep， 2010， 486（3/4/5）： 75-174. DOI： 10.1016/j.physrep.2009.11.002.

[2] HENDERSON K， GALLAGHER B， ELIASSI-RAD T，et al. RolX： Structural Role Extraction amp; Mining in Large Graphs[C]//Proceedings of the 18th ACMSIGKDD International Conference on Knowledge Discoveryand Data Mining. New York： ACM， 2012： 1231-1239. DOI： 10.1145/2339530.2339723.

[3] YANG J， LESKOVEC J. Overlapping Communities ExplainCore-Periphery Organization of Networks[J]. ProcIEEE， 2014， 102（12）： 1892-1902. DOI： 10.1109/JPROC.2014.2364018.

[4] ROSSI R A， AHMED N K. Role Discovery in Networks[J]. IEEE Trans Knowl Data Eng， 2015， 27（4）： 1112-1131. DOI： 10.1109/TKDE.2014.2349913.

[5] TU K， CUI P， WANG X， et al. Deep Recursive NetworkEmbedding with Regular Equivalence[C]//Proceedingsof the 24th ACM SIGKDD International Conference onKnowledge Discovery amp; Data Mining. New York： ACM，2018： 2357-2366. DOI： 10.1145/3219819.3220068.

[6] RIBEIRO L F R， SAVARESE P H P， FIGUEIREDO DR. Struc2vec： Learning Node Representations fromStructural Identity[EB/OL]. arXiv Preprint： 1704， 03165，2017. https：//arxiv.org/abs/1704.03165.

[7] ARVIND V， FUHLBRüCK F， K?BLER J， et al. OnWeisfeiler-leman Invariance： Subgraph Counts and RelatedGraph Properties[J]. J Comput Syst Sci， 2020， 113：42-59. DOI： 10.1016/j.jcss.2020.04.003.

[8] BAEK M， DIMAIO F， ANISHCHENKO I， et al. AccuratePrediction of Protein Structures and Interactions Usinga Three-track Neural Network[J]. Science， 2021， 373（6557）： 871-876. DOI： 10.1126/science.abj8754.

[9] Lü L Y， ZHOU T. Link Prediction in Complex Networks：A Survey[J]. Phys A Stat Mech Appl， 2011， 390（6）： 1150-1170. DOI： 10.1016/j.physa.2010.11.027.

[10] ERTL O. ProbMinHash-A Class of Locality-sensitiveHash Algorithms for the （Probability） Jaccard Similarity[J]. IEEE Trans Knowl Data Eng， 2022， 34（7）： 3491-3506. DOI： 10.1109/TKDE.2020.3021176.

[11] ADAMIC L A， ADAR E. Friends and Neighbors on theWeb[J]. Soc Netw， 2003， 25（3）： 211-230. DOI： 10.1016/s0378-8733（03）00009-1.

[12] ZHOU T， Lü L Y， ZHANG Y C. Predicting MissingLinks via Local Information[J]. Eur Phys J B， 2009， 71（4）： 623-630. DOI： 10.1140/epjb/e2009-00335-8.

[13] BASTAMI E， MAHABADI A， TAGHIZADEH E. AGravitation-based Link Prediction Approach in SocialNetworks[J]. Swarm Evol Comput， 2019， 44： 176-186.DOI： 10.1016/j.swevo.2018.03.001.

[14] CHEN Z Q， XIE Z， ZHANG Q. Community DetectionBased on Local Topological Information and Its Applicationin Power Grid[J]. Neurocomputing， 2015， 170：384-392. DOI： 10.1016/j.neucom.2015.04.093.

[15] PEROZZI B， AL-RFOU R， SKIENA S. DeepWalk： OnlineLearning of Social Representations[C]//Proceedings of the20th ACM SIGKDD International Conference onKnowledge Discovery and Data Mining. New York： ACM，2014： 701-710. DOI： 10.1145/2623330.2623732.

[16] GROVER A， LESKOVEC J. Node2vec： Scalable FeatureLearning for Networks[C]//Proceedings of the22nd ACM SIGKDD International Conference onKnowledge Discovery and Data Mining. New York：ACM， 2016： 855-864. DOI： 10.1145/2939672.2939754.

[17] ZHENG W P， CHEN C H， QIAN Y H， et al. A GraphClustering Algorithm Based Paths Between Nodes inComplex Networks[J]. Chin J Comput， 2020， 43（7）： 1312-327. DOI： 10.1016/j.phy sa.2016.11.015.

[18] BURT R. Structural Holes and Good Ideas[J]. Am J Sociol，2004， 110（2）： 349-399. DOI： 10.1086/421787.

[19] ZHANG Q， LI M Z， DENG Y. Measure the StructureSimilarity of Nodes in Complex Networks Based onRelative Entropy[J]. Phys A Stat Mech Appl， 2018， 491：749-763. DOI： 10.1016/j.physa.2017.09.042.

[20] MU J F， LIANG J Y， ZHENG W P， et al. Node SimilarityMeasure for Complex Networks[J]. J Front Comput SciTech， 2020， 14（5）： 749-759. DOI： 10.3778/j. issn.1673-9418.1905015.

[21] ZOU M H， GAN Z X， CAO R Z， et al. SimilaritynavigatedGraph Neural Networks for Node Classification[J]. Inf Sci， 2023， 633： 41-69. DOI： 10.1016/j.ins.2023.03.057.

[22] SHERVASHIDZE N， SCHWEITZER P， VAN LEEUWENE J， et al. Weisfeiler-Lehman Graph Kernels[J]. JMach Learn Res， 2011， 12： 2539-2561.

[23] MAHé P， VERT J P. Graph Kernels Based on Tree Patternsfor Molecules[J]. Mach Learn， 2009， 75（1）： 3-35.DOI： 10.1007/s10994-008-5086-2.

[24] G?RTNER T， FLACH P， WROBEL S. On Graph Kernels：Hardness Results and Efficient Alternatives[C]//LearningTheory and Kernel Machines. Berlin， Heidelberg： Springer，2003： 129-143. DOI：10.1007/978-3-540-45167-9_11.

[25] MAHé P， UEDA N， AKUTSU T， et al. Extensions of MarginalizedGraph Kernels[C]//Twenty-first internationalconference on Machine learning-ICML '04. New York：ACM， 2004： 70-77. DOI： 10.1145/1015330.1015446.

[26] ABURIDI M， MARCIA R. Wasserstein Distance-basedGraph Kernel for Enhancing Drug Safety and EfficacyPrediction[C]//2024 IEEE First International Conferenceon Artificial Intelligence for Medicine， Health andCare （AIMHC）. New York： IEEE， 2024： 113-119. DOI：10.1109/AIMHC59811.2024.00029.

[27] LI M， WANG Z， LIU L， et al. Subgraph-Aware GraphKernel Neural Network for Link Prediction in BiologicalNetworks[J]. IEEE J Biomed Health， 2024， 28（7）：4373-4381. DOI： 10.1109/JBHI.2024.3390092.

[28] CAI J Y， FURER M， IMMERMAN N. An OptimalLower Bound on the Number of Variables for GraphIdentification[C]//30th Annual Symposium on Foundationsof Computer Science. New York： IEEE， 1989：612-617. DOI： 10.1109/SFCS.1989.63543.

[29] KIEFER S， SCHWEITZER P. Upper Bounds on theQuantifier Depth for Graph Differentiation in FirstOrder Logic[C]//Proceedings of the 31st AnnualACM/IEEE Symposium on Logic in Computer Science.New York： ACM， 2016：287-296. DOI： 10.1145/2933575.2933595.

[30] BABAI L. Graph Isomorphism in QuasipolynomialTime[C]//Proceedings of the Forty-eighth Annual ACMSymposium on Theory of Computing. New York：ACM， 2016： 684-697. DOI： 10.1145/2897518.2897542.

[31] MORRIS C， RITZERT M， FEY M， et al. Weisfeiler andLeman Go Neural： Higher-order Graph Neural Networks[J]. Proc AAAI Conf Artif Intell， 2019， 33（1）：4602-4609. DOI： 10.1609/aaai.v33i01.33014602.

基金項(xiàng)目：國家自然科學(xué)基金（62072292）； 山西省1331工程項(xiàng)目