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

關鍵詞：復雜網(wǎng)絡；結構相似性；k元組；高階結構；Weisfeiler-Lehman方法

中圖分類號：O436 文獻標志碼：A 文章編號：0253-2395（2024）05-0993-11

0 引言

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

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

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

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

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

1 相關工作

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

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

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

2 背景知識

2.1 基本概念

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

2.2 Weisfeiler-Lehman圖核

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

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

盡管WL 算法是對兩個圖是否同構進行判定的，實際上，其迭代的賦予節(jié)點或節(jié)點組標簽的過程，也是對節(jié)點或節(jié)點組進行編碼的過程。局部鄰域范圍內拓撲結構相似的節(jié)點通常會被賦予相似的標簽，本文利用WL 算法的編碼過程對節(jié)點的局部鄰域結構相似性進行判定。

3 節(jié)點間結構相似性度量方法GANNLI

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

為了提取k 元節(jié)點組的鄰域結構，對k 元節(jié)點組P 的鄰域進行了定義，如下式所示：

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

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

3.2 GANNLI方法

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

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

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

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

4 實驗分析

4.1 k 元節(jié)點組表達能力分析

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

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

4.2 真實網(wǎng)絡上的節(jié)點相似性比較

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

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

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

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

4.3 在分類任務上的比較結果

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

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

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

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

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

5 總結

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

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

基金項目：國家自然科學基金（62072292）； 山西省1331工程項目