基于跨圖特征融合和結(jié)構(gòu)感知注意力的圖相似度計(jì)算

中圖分類號：TP391 文獻(xiàn)標(biāo)志碼：A 文章編號：1001-3695（2025）08-010-2320-09

doi：10.19734/j.issn.1001-3695.2025.01.0020

Graph similarity computation based on cross-graph feature fusion and structure-aware attention

Pang Jun ^1，2 ，Yan Bingxin’，LinXiaoli1，2，Wang Mengxiang3+ （1.ColegeofomputerScienceamp;Tchnolog，WuhanUniersityofSieceamp;Techolog，Wuhan43O5，hina;2.HubeiProceKeyL boratoryfelos; jing 100088，China）

Abstract：GED isacommonlyused graph similarity metric function whose exact computation isanNP-hard problem.Therefore，recentlyresearchershave proposed numerousgraph neural network-based graph similaritycomputation methods.The existing methods ignrethecrossgraph interactioninformationbetweentwograph nodesduringfeature extractionandlack the learning of higher-orderrelationships betwee nodes inthe graph.Toaddresstheabove problems，this paperproposedamodel for graph similaritycomputationbasedoncross-graphfeature fusionand structure-aware atention.Firstly，themodel proposed across-graphnodefeature leaing method，which introducedacrossgraphattentiomechanismtoextractthecro-raphinteractioninformationof nodes，andeffectivelyfusedthelocal featuresofnodesandthecross-graphinteraction features.Secondly，he modelproposedastructure-awaremulti-atentionmechanism，whichcombinedthefeatureinformationofnodes withthegraph structural informationtoeficientlycapturethehigher-orderrelationshipsamong nodes.Experimentalesultson three public datasets show that the prediction accuracy of the CFSA model is improved by 4.8% ，5. 1% ，and 15.8% ， respectively，compared tothe existing models，and hasadvantages inalarge numberof performance metrics，which proves the effectiveness and efficiency of CFSA for the GED prediction task.

Key words： graph edit distance（GED）； graph similarity；graph neural network（GNN） ； graph embedding learning

0 引言

圖數(shù)據(jù)因其獨(dú)特的表達(dá)能力，能夠有效地表示實(shí)體及實(shí)體之間的復(fù)雜關(guān)系，因此在推薦系統(tǒng)[1、社交網(wǎng)絡(luò)分析和生物信息學(xué)[3]等領(lǐng)域得到廣泛應(yīng)用。圖相似度計(jì)算作為圖數(shù)據(jù)分析的基本操作，在各種實(shí)際應(yīng)用中得到了廣泛的關(guān)注。例如，在社交網(wǎng)絡(luò)分析中，通過計(jì)算不同用戶之間的相似度，來預(yù)測兩者之間是否存在關(guān)聯(lián)[2；在藥物研發(fā)中，通過計(jì)算藥物和蛋白質(zhì)分子的相似度，尋找關(guān)鍵子結(jié)構(gòu)，從而準(zhǔn)確預(yù)測藥物靶標(biāo)結(jié)合親和力[3]；在計(jì)算機(jī)安全中，通過評估未知軟件與惡意軟件之間的相似度，從而識別潛在的安全威脅[4]。因此，圖相似度計(jì)算在理論研究和實(shí)踐應(yīng)用中均具有重要意義。

圖編輯距離是一種衡量兩個(gè)圖相似度的函數(shù)[5]，通過計(jì)算一個(gè)圖轉(zhuǎn)換為另一個(gè)圖所需的最小編輯操作數(shù)，評估這兩個(gè)圖的相似度。然而，精確計(jì)算兩個(gè)圖之間的圖編輯距離是NP-hard問題（NP-hardproblem）[6]。即使采用先進(jìn)的方法，對于節(jié)點(diǎn)數(shù)較多的圖，計(jì)算它們之間的精確圖編輯距離仍然面臨時(shí)間效率的挑戰(zhàn)，這使得其在可拓展性方面存在較大限制[7]。近年來，作為一種新興的深度學(xué)習(xí)方法，圖神經(jīng)網(wǎng)絡(luò)能有效利用圖結(jié)構(gòu)信息學(xué)習(xí)圖的表示，并以端到端的方式實(shí)現(xiàn)對圖中復(fù)雜任務(wù)的處理，從而為圖相似度計(jì)算問題提供了全新的解決方案[8.9]

根據(jù)能否生成圖編輯路徑，現(xiàn)有基于圖神經(jīng)網(wǎng)絡(luò)的圖相似度計(jì)算方法可分為不可恢復(fù)編輯路徑的圖相似度計(jì)算模型[10～18]和可恢復(fù)編輯路徑的圖相似度計(jì)算模型[19～21]兩類。第一類模型將圖相似度計(jì)算作為一種回歸任務(wù)，通過深度學(xué)習(xí)框架來學(xué)習(xí)圖的特征表示，并計(jì)算特征向量之間相似度作為圖對的相似度。例如，文獻(xiàn)[10]提出的SimGNN模型，首次將圖神經(jīng)網(wǎng)絡(luò)引入圖相似度計(jì)算問題中，通過多層圖卷積網(wǎng)絡(luò)學(xué)習(xí)節(jié)點(diǎn)特征和全局圖表示，將其輸人全連接網(wǎng)絡(luò)從而獲得圖相似度。這類方法雖然有效提升了圖相似度計(jì)算的效率和準(zhǔn)確度，但由于其無法恢復(fù)相應(yīng)的圖編輯路徑，從而影響了模型的可解釋性。第二類模型是將圖神經(jīng)網(wǎng)絡(luò)與其他技術(shù)相結(jié)合，不僅計(jì)算圖編輯距離，還可生成相應(yīng)的圖編輯路徑，具有更好的可解釋性。例如，文獻(xiàn)[21提出的GEDGNN模型，通過圖神經(jīng)網(wǎng)絡(luò)生成的節(jié)點(diǎn)嵌入，學(xué)習(xí)圖對之間的節(jié)點(diǎn)匹配關(guān)系和匹配成本，并提出一種后處理算法，利用節(jié)點(diǎn)匹配關(guān)系計(jì)算圖編輯距離和相應(yīng)的圖編輯路徑。但這兩類方法存在以下兩點(diǎn)不足：a）在節(jié)點(diǎn)特征學(xué)習(xí)階段，僅考慮圖中節(jié)點(diǎn)的局部特征信息，忽略了跨圖節(jié)點(diǎn)之間的潛在相關(guān)性；b）忽略了節(jié)點(diǎn)間高階關(guān)系的重要性，在處理復(fù)雜結(jié)構(gòu)的圖時(shí)，無法有效捕獲節(jié)點(diǎn)之間的深層次關(guān)系。

因此，本文提出了一種基于跨圖特征融合和結(jié)構(gòu)感知注意力的圖相似度計(jì)算模型CFSA。在CFSA模型中，針對第一點(diǎn)不足，提出了一種跨圖節(jié)點(diǎn)特征學(xué)習(xí)方法，引入跨圖注意力機(jī)制，學(xué)習(xí)兩個(gè)圖節(jié)點(diǎn)之間的跨圖交互信息，并將這些交互特征與局部特征相融合，從而增強(qiáng)節(jié)點(diǎn)的嵌入表示。針對第二點(diǎn)不足，提出了一種結(jié)構(gòu)感知型多頭自注意力機(jī)制，通過結(jié)合圖的結(jié)構(gòu)信息和節(jié)點(diǎn)特征信息，挖掘節(jié)點(diǎn)之間的高階關(guān)系。

本文的主要貢獻(xiàn)總結(jié)如下：a）提出了一種基于跨圖特征融合和結(jié)構(gòu)感知注意力的圖相似度計(jì)算模型CFSA，通過有效整合不同層次的節(jié)點(diǎn)信息和捕捉節(jié)點(diǎn)間的高階關(guān)系，彌補(bǔ)現(xiàn)有模型表達(dá)能力不足的問題；b）提出了一種跨圖節(jié)點(diǎn)特征學(xué)習(xí)方法，引入跨圖注意力機(jī)制，學(xué)習(xí)源圖和目標(biāo)圖節(jié)點(diǎn)之間的跨圖交互信息，并將節(jié)點(diǎn)的跨圖交互特征與局部特征相融合，從而豐富節(jié)點(diǎn)嵌入特征；c）提出了一種結(jié)構(gòu)感知型多頭自注意力機(jī)制。該機(jī)制在傳統(tǒng)的多頭自注意力機(jī)制的基礎(chǔ)上，融合了圖的拓?fù)浣Y(jié)構(gòu)信息，有效捕捉節(jié)點(diǎn)間的高階關(guān)系，并增強(qiáng)了模型對復(fù)雜圖結(jié)構(gòu)的學(xué)習(xí)能力；d）在三個(gè)公共圖數(shù)據(jù)集上執(zhí)行GED預(yù)測任務(wù)，驗(yàn)證了本文模型的有效性和效率，在預(yù)測準(zhǔn)確率上比現(xiàn)有模型分別提升了 4.8% .5.1% .15.8% 0

1相關(guān)工作

1.1不可恢復(fù)編輯路徑的圖相似度計(jì)算模型

該類模型將圖相似度計(jì)算問題視為回歸任務(wù)，采用端到端的方式執(zhí)行圖相似度計(jì)算。 SimGNN^[10] 通過結(jié)合直方圖特征和神經(jīng)張量網(wǎng)絡(luò)分別提取節(jié)點(diǎn)級與圖級交互信息，將其輸入全連接網(wǎng)絡(luò)計(jì)算圖相似度。然而，該模型在節(jié)點(diǎn)特征提取時(shí)僅考慮節(jié)點(diǎn)的局部特征。GraphSim[1]通過學(xué)習(xí)不同卷積層的節(jié)點(diǎn)級交互信息，以捕捉不同尺度的節(jié)點(diǎn)交互特征。然而，由于需要多次計(jì)算節(jié)點(diǎn)交互信息，導(dǎo)致模型時(shí)間復(fù)雜度較高。TaGSim^[12] 通過考慮不同圖編輯操作對圖結(jié)構(gòu)的影響，分別構(gòu)建類型感知的圖級嵌入，并基于類型感知相似度計(jì)算圖編輯距離，但是其忽略了遠(yuǎn)距離節(jié)點(diǎn)之間的相關(guān)性。MGMN[14]提出節(jié)點(diǎn)-圖跨級交互層，以捕捉每個(gè)節(jié)點(diǎn)與另一個(gè)圖的圖級嵌入之間的跨級交互信息。 CLSim^[18] 通過將圖級交互信息與節(jié)點(diǎn)級交互信息相結(jié)合，以捕獲節(jié)點(diǎn)圖交互細(xì)節(jié)。然而，該模型采用簡單拼接的方式結(jié)合節(jié)點(diǎn)級和圖級信息，從而導(dǎo)致冗余特征的引入。上述模型雖然提高了圖相似度計(jì)算的準(zhǔn)確度和效率，但無法提供圖編輯路徑信息。

1.2可恢復(fù)編輯路徑的圖相似度計(jì)算模型

該類模型將圖神經(jīng)網(wǎng)絡(luò)與其他技術(shù)相結(jié)合，不僅可以計(jì)算圖相似度和圖編輯距離，還能生成相應(yīng)的圖編輯路徑。GENN- 和 Noah^[20] 將傳統(tǒng) A^* 算法與圖神經(jīng)網(wǎng)絡(luò)相結(jié)合，改善A*搜索算法中未匹配部分估計(jì)成本較差的問題。其中，GENN-A*提出動(dòng)態(tài)圖嵌人算法，高效生成嵌人向量。Noah提出圖路徑網(wǎng)絡(luò)來優(yōu)化 A^* 算法。然而， A^* 算法在計(jì)算每個(gè)狀態(tài)的估計(jì)成本時(shí)使用估計(jì)成本函數(shù)，導(dǎo)致不準(zhǔn)確值的累積，從而使最終預(yù)測的圖編輯距離往往與真實(shí)值之間存在較大的差距。另外，受圖對齊思想的啟發(fā)，GEDGNN[21]通過建模兩個(gè)圖節(jié)點(diǎn)間的匹配關(guān)系和匹配成本，進(jìn)而計(jì)算圖編輯距離和相應(yīng)的圖編輯路徑。但該類模型在提取節(jié)點(diǎn)特征時(shí)，僅考慮節(jié)點(diǎn)間的局部特征，忽略了跨圖節(jié)點(diǎn)之間的潛在相關(guān)性。此外，在處理具有復(fù)雜結(jié)構(gòu)的大圖時(shí)，基于局部特征的建模無法全面反映整體圖特征，忽略了節(jié)點(diǎn)間高階關(guān)系的重要性。

綜上所述，可恢復(fù)編輯路徑的圖相似度計(jì)算模型能夠計(jì)算圖編輯距離，并生成相應(yīng)的圖編輯路徑。因此，本文對該類模型展開研究。與現(xiàn)有模型相比，本文通過跨圖節(jié)點(diǎn)特征學(xué)習(xí)方法和結(jié)構(gòu)感知多頭注意力機(jī)制，學(xué)習(xí)了節(jié)點(diǎn)的跨圖交互信息和節(jié)點(diǎn)間高階關(guān)系。下文將概述本文所涉及的基本概念，并對相關(guān)問題進(jìn)行形式化定義。

2基本概念與問題形式化定義

定義1圖編輯距離。給定一對圖 （G₁，G₂） ，將 G₁ 轉(zhuǎn)換為G₂ 的最小編輯操作數(shù)稱為圖編輯距離，用 GED（G₁，G₂） 表示。其中編輯操作分為添加或刪除邊、添加或刪除孤立節(jié)點(diǎn)、改變節(jié)點(diǎn)或邊的標(biāo)簽[2I]三類。

定義2圖編輯路徑。給定一對圖 （G₁，G₂） ，將 G₁ 轉(zhuǎn)換為G₂ 的一系列編輯操作 （o₁，o₂，…，o_k） 稱為編輯路徑。最短編輯路徑對應(yīng)圖編輯距離[21]

圖1展示了圖 G₁ 和 G₂ 之間的圖編輯路徑和圖編輯距離。其中不同的顏色代表節(jié)點(diǎn)的不同標(biāo)簽，將源圖 G₁ 轉(zhuǎn)換為目標(biāo)圖 G₂ 至少需要三次編輯操作。 G₁ 中節(jié)點(diǎn) {v₁，v₂，v₃} 分別匹配G₂ 中的 {u₂，u₃，u₄} 。假設(shè)編輯成本統(tǒng)一，則 GED（G₁，G₂）=3 ，具體編輯路徑為：刪除邊 （v₁，v₂） 、插入節(jié)點(diǎn) v₄ 、插入邊（ v₁ ，v₄ ）。 G₁ 到 G₂ 的編輯路徑，實(shí)際上依賴于圖中節(jié)點(diǎn)之間的匹配關(guān)系。通過明確節(jié)點(diǎn)間的匹配關(guān)系，并基于這些匹配關(guān)系制定有效的編輯策略，不僅可以計(jì)算圖編輯距離，還能生成相應(yīng)的圖編輯路徑。

定義3圖相似度計(jì)算。給定一個(gè)源圖集合 D 和查詢圖集合 Q ，通過構(gòu)造一個(gè)可學(xué)習(xí)的相似度函數(shù) ，輸入圖對 G_i∈D 和 G_j∈Q ，輸出 G_i 和 G_j 之間的相似度分?jǐn)?shù) Score_ij← 三R ，其中 R∈（0，1]^[16] 。

基于以上定義，本文研究基于圖編輯距離的圖相似度計(jì)算。

圖1圖編輯距離示例Fig.1Example of graph edit distance

3 CFSA模型

3.1框架概述

CFSA模型的基本思想是：首先，將輸入圖對的初始節(jié)點(diǎn)嵌入分別輸入多層圖同構(gòu)網(wǎng)絡(luò)，生成包含局部特征的節(jié)點(diǎn)嵌入；

其次，采用跨圖節(jié)點(diǎn)特征學(xué)習(xí)方法，學(xué)習(xí)節(jié)點(diǎn)的跨圖特征信息，并將節(jié)點(diǎn)的局部特征和跨圖特征相融合，豐富節(jié)點(diǎn)嵌入的特征信息；接著，對節(jié)點(diǎn)嵌入進(jìn)行比較，生成節(jié)點(diǎn)級交互信息；隨后，采用結(jié)構(gòu)感知多頭注意力機(jī)制，綜合考慮圖的結(jié)構(gòu)信息和節(jié)點(diǎn)的特征信息，挖掘節(jié)點(diǎn)之間的高階關(guān)系，并引入平均池化操作，對經(jīng)過注意力機(jī)制處理的節(jié)點(diǎn)嵌入進(jìn)行整合生成圖級嵌入；對圖級嵌入進(jìn)行比較，生成圖級交互信息；最后，融合上述交互信息計(jì)算最終的圖編輯距離，其中，圖級比較使用神經(jīng)張量網(wǎng)絡(luò)計(jì)算，節(jié)點(diǎn)級比較使用多視角匹配方法計(jì)算。

模型的整體框架結(jié)構(gòu)如圖2所示，主要包括節(jié)點(diǎn)級交互模塊、圖級交互模塊和圖編輯距離計(jì)算模塊三個(gè)部分。此外，為了生成圖編輯路徑，本文利用在節(jié)點(diǎn)比較中生成的節(jié)點(diǎn)匹配矩陣，并基于此矩陣應(yīng)用 k -最佳匹配算法，尋找權(quán)重排名前 k 的節(jié)點(diǎn)匹配關(guān)系。通過節(jié)點(diǎn)匹配關(guān)系，生成相應(yīng)的圖編輯路徑。

圖2CFSA模型框架Fig.2FrameworkofCFSAmodel

3.2 節(jié)點(diǎn)級交互

本節(jié)首先通過圖同構(gòu)網(wǎng)絡(luò)學(xué)習(xí)節(jié)點(diǎn)的局部特征；其次，引入跨圖節(jié)點(diǎn)特征學(xué)習(xí)方法提取節(jié)點(diǎn)的跨圖交互信息，并將節(jié)點(diǎn)的局部特征和跨圖交互特征相融合，生成節(jié)點(diǎn)嵌入向量；最后，基于節(jié)點(diǎn)嵌入向量計(jì)算圖對節(jié)點(diǎn)級交互信息。

3.2.1節(jié)點(diǎn)嵌入生成

本節(jié)采用圖同構(gòu)網(wǎng)絡(luò)學(xué)習(xí)節(jié)點(diǎn)的局部特征，并提出一種跨圖節(jié)點(diǎn)特征學(xué)習(xí)方法，捕獲兩個(gè)圖節(jié)點(diǎn)之間的跨圖交互特征，并將節(jié)點(diǎn)的跨圖特征與局部特征相融合，豐富節(jié)點(diǎn)嵌入特征。

首先，對于輸入圖中的每個(gè)節(jié)點(diǎn) ，如果圖 是一個(gè)有標(biāo)簽的圖，則初始節(jié)點(diǎn)嵌入定義為該節(jié)點(diǎn)標(biāo)簽的one-hot向量；而對于沒有節(jié)點(diǎn)標(biāo)簽的圖，則將初始節(jié)點(diǎn)嵌入設(shè)置為一個(gè)常數(shù)值，即一維向量。在現(xiàn)有的圖表示學(xué)習(xí)方法中，圖同構(gòu)網(wǎng)絡(luò)（graphisomorphismnetwork，GIN）是一種基于圖同構(gòu)理論設(shè)計(jì)的模型，具有強(qiáng)大的圖結(jié)構(gòu)判別能力，能夠有效捕捉圖之間的拓?fù)洳町悺＞唧w而言，其通過多層消息傳遞機(jī)制，迭代聚合目標(biāo)節(jié)點(diǎn)特征及其多跳鄰域信息，并更新節(jié)點(diǎn)特征表示[22]。因此，本文采用三層圖同構(gòu)網(wǎng)絡(luò)來提取圖中節(jié)點(diǎn)的局部特征。

受多級圖匹配網(wǎng)絡(luò)[14]的啟發(fā)，本文提出了一種新穎的跨圖節(jié)點(diǎn)特征學(xué)習(xí)方法，學(xué)習(xí)兩個(gè)圖節(jié)點(diǎn)之間的跨圖交互特征，并將節(jié)點(diǎn)的跨圖特征和局部特征相融合，如圖3所示。該方法通過學(xué)習(xí)跨圖節(jié)點(diǎn)嵌人之間的語義相似度，構(gòu)造跨圖注意力權(quán)重矩陣，并基于該矩陣與局部特征節(jié)點(diǎn)嵌入進(jìn)行加權(quán)求和，從而挖掘輸入圖對節(jié)點(diǎn)間的跨圖交互特征。然后，將局部特征節(jié)點(diǎn)嵌入與跨圖特征節(jié)點(diǎn)嵌人相融合，得到融合節(jié)點(diǎn)嵌入。

跨圖節(jié)點(diǎn)特征學(xué)習(xí)的具體流程如下：首先，通過余弦相似度函數(shù)計(jì)算跨圖節(jié)點(diǎn)之間的特征相似度，從而構(gòu)建跨圖注意力權(quán)重矩陣。計(jì)算過程如式（1）所示。

α_i，j=cosine（h_i¹，h_j²）v_i∈V₁，v_j∈V₂

其中： h_i¹ 和 h_j² 分別為圖 G₁ 中節(jié)點(diǎn) v_i 和圖 G₂ 中節(jié)點(diǎn) v_j 的局部特征節(jié)點(diǎn)嵌入； α_i，j 表示圖 G₁ 中節(jié)點(diǎn) v_i 和圖 G₂ 中節(jié)點(diǎn) v_j 之間的注意力系數(shù)。

其次，將局部特征節(jié)點(diǎn)嵌入與跨圖注意力權(quán)重矩陣進(jìn)行注意力加權(quán)，以捕獲一個(gè)圖中節(jié)點(diǎn)與另一個(gè)圖中各個(gè)節(jié)點(diǎn)之間的交互信息，計(jì)算過程如式（2）所示。

其中： T_i¹ 和 T_j² 分別為圖 G₁ 中節(jié)點(diǎn) v_i 和圖 G₂ 中節(jié)點(diǎn) v_j 的特征張量。

接著，通過對生成的加權(quán)特征張量進(jìn)行降維處理，以有效整合并提取其主要的跨圖特征信息。具體而言，使用平均池化操作對特征張量進(jìn)行下采樣，然后使用softmax函數(shù)對其進(jìn)行歸一化處理，這樣不僅降低了特征維度，還能有效保留重要的特征信息，計(jì)算過程如式（3）所示。

z_i¹=softmax（mean（T_i¹）），z_j²=softmax（mean（T_j²））

其中： z_i¹ 和 z_j² 分別為圖 G₁ 中節(jié)點(diǎn) v_i 和圖 G₂ 中節(jié)點(diǎn) v_j 的跨圖特征節(jié)點(diǎn)嵌入； mean 是平均池化操作。

同時(shí)，引入殘差連接，將局部特征節(jié)點(diǎn)嵌入與跨圖特征節(jié)點(diǎn)嵌入相融合。不僅保留節(jié)點(diǎn)的局部特征信息，還能整合節(jié)點(diǎn)的跨圖交互信息，從而生成更豐富的節(jié)點(diǎn)嵌人。計(jì)算過程如式（4）所示。

x_i¹=h_i¹+z_i¹，x_j²=h_j²+z_j²

其中： x_i¹ 是圖 G₁ 中節(jié)點(diǎn) v_i 的特征融合節(jié)點(diǎn)嵌入； x_j² 是圖 G₂ 中節(jié)點(diǎn) v_j 的特征融合節(jié)點(diǎn)嵌入。

3.2.2 節(jié)點(diǎn)級比較

為了捕獲輸入圖對節(jié)點(diǎn)之間的交互信息，通常采用節(jié)點(diǎn)嵌入成對比較計(jì)算節(jié)點(diǎn)級相似度，但該方法在處理復(fù)雜交互關(guān)系時(shí)，無法充分挖掘不同視角下的潛在信息。為此，本文引入一種多視角匹配方法[21]。該方法將兩個(gè)圖的節(jié)點(diǎn)嵌入 x¹∈Σ （204號 和 作為輸人，采用雙線性張量層計(jì)算多個(gè)視角下的節(jié)點(diǎn)交互關(guān)系。接著，利用多層感知機(jī)整合這些交互信息，從而生成一個(gè)形狀為 ∣V₁∣×∣V₂∣ 的特征矩陣。計(jì)算過程如式（5）所示。

M=MLP（x¹W^[1：k]（x²）^?）

其中： W^[1：k]∈R^k×d×d 是 k 維的可學(xué)習(xí)權(quán)重張量。

通過多視角匹配方法生成特征矩陣后，分別構(gòu)建節(jié)點(diǎn)匹配矩陣 M_match 和匹配成本矩陣 M_cost 。其中，節(jié)點(diǎn)匹配矩陣 M_match 表示兩個(gè)圖中節(jié)點(diǎn)間的匹配程度，它通過將生成的特征矩陣與真實(shí)匹配矩陣進(jìn)行監(jiān)督學(xué)習(xí)來實(shí)現(xiàn)。匹配成本矩陣 M_cost 表示節(jié)點(diǎn)對進(jìn)行匹配所需的代價(jià)。由于多視角匹配方法捕獲的是節(jié)點(diǎn)間的相似度，所以需要對輸出的特征矩陣進(jìn)行調(diào)整，從而轉(zhuǎn)換為匹配成本矩陣。本文采用線性變換進(jìn)行處理，從而獲得匹配成本矩陣 M_cost ，計(jì)算過程如式（6）所示。

M_cost=1-MLP（x¹W^[1：k]（x²）^T）

3.3 圖級交互

本節(jié)引入結(jié)構(gòu)感知型的多頭注意力機(jī)制來挖掘節(jié)點(diǎn)間的高階關(guān)系，并采用平均池化生成圖級嵌入。最后，基于圖級嵌人計(jì)算圖級交互信息。

3.3.1結(jié)構(gòu)感知型多頭注意力機(jī)制與圖級嵌入生成

在圖神經(jīng)網(wǎng)絡(luò)GNN中，由于感受野的限制，淺層的GNN難以有限建模節(jié)點(diǎn)間的高階關(guān)系，而深層的GNN會導(dǎo)致節(jié)點(diǎn)的特征表示趨向于相似，出現(xiàn)過度平滑現(xiàn)象。為了有效學(xué)習(xí)節(jié)點(diǎn)之間的高階關(guān)系，本文引入了多頭注意力機(jī)制。然而，傳統(tǒng)的注意力機(jī)制僅關(guān)注節(jié)點(diǎn)間的特征相似性，忽視了圖結(jié)構(gòu)中存在的拓?fù)湫畔ⅰＲ虼耍疚奶岢隽艘环N結(jié)構(gòu)感知型多頭注意力機(jī)制，如圖4所示。該機(jī)制結(jié)合了多頭注意力技術(shù)和拓?fù)浣Y(jié)構(gòu)信息，以挖掘圖中節(jié)點(diǎn)間隱含的高階關(guān)系，并增強(qiáng)模型對復(fù)雜圖數(shù)據(jù)的學(xué)習(xí)能力。

圖4結(jié)構(gòu)感知型多頭注意力與圖嵌入生成 Fig.4Structure aware multi-head attention and graph embedding generation

首先，將上文生成的節(jié)點(diǎn)嵌入與節(jié)點(diǎn)的緊密中心性向量相結(jié)合，形成一個(gè)新的特征表示，作為結(jié)構(gòu)感知多頭注意力機(jī)制的輸入。其中，緊密中心性是用于評估一個(gè)節(jié)點(diǎn)到其他所有節(jié)點(diǎn)的緊密程度，以反映節(jié)點(diǎn)的重要性，其值越高意味著該節(jié)點(diǎn)具有更強(qiáng)的連接性和信息傳播能力。緊密中心性的計(jì)算過程如式（7）所示。

其中： N 是圖中的節(jié)點(diǎn)數(shù); d_[i][j] 是節(jié)點(diǎn) v_i 和 v_j 之間的最短距離； 表示節(jié)點(diǎn) v_i 結(jié)合緊密中心性的嵌人向量; C_vi 表示節(jié)點(diǎn) v_i 的緊密中心性值。

接著，利用線性變換對結(jié)合緊密中心性的節(jié)點(diǎn)嵌入進(jìn)行處理，計(jì)算其在第 Φ_t 個(gè)注意力頭中的查詢向量 、鍵向量 K_t 和值向量 V_t 。其中， ， W_t^Q，W_t^K，W_t^V 分別是查詢、鍵和值相關(guān)的可學(xué)習(xí)參數(shù)矩陣 ，t={1，2，…，n} （ n 等于注意力頭數(shù)）。

然后，采用點(diǎn)積操作計(jì)算查詢向量 與鍵向量 K_t 之間的相似度，得到注意力得分 A 。此外，為了更全面地捕捉節(jié)點(diǎn)間的位置關(guān)系，引入了節(jié)點(diǎn)間距離信息來構(gòu)造距離矩陣，并基于距離矩陣來動(dòng)態(tài)調(diào)整 A 。然后，對 A 進(jìn)行歸一化處理，從而得到注意力權(quán)重 W_A 。最后，將值向量 V_t 與注意力權(quán)重 W_A 進(jìn)行加權(quán)求和，從而得到單個(gè)注意力頭的注意力輸出。距離矩陣和注意力輸出的計(jì)算過程分別如式（10）（11）所示。

其中 ?M_dis 表示距離矩陣，其元素為節(jié)點(diǎn)間最短距離的倒數(shù); d_k表示鍵向量的維度，除以 是防止得分因維度增大而增大。

多頭自注意力將輸出映射到不同的子空間。在每個(gè)注意力頭中，分別計(jì)算其注意力輸出，最終通過連接操作（concat）拼接所有單頭的特征表達(dá)。計(jì)算過程如式（12）（13）所示。

Head_t=attention（Q_t，K_t，V_t）

MultiHead=concat（Head₁，…，Head_n）W^o

其中： Head_t 是第 χ_t 個(gè)頭的注意力輸出； W^o 是輸出變換矩陣。

為了生成圖級嵌入，本文采用平均池化處理，通過對節(jié)點(diǎn)嵌人進(jìn)行均值計(jì)算，避免信息的丟失，并有效整合節(jié)點(diǎn)信息。計(jì)算過程如式（14）所示。

其中： H 是圖級嵌入向量。

3.3.2 圖級比較

對于給定兩個(gè)圖的圖級嵌入，本文采用神經(jīng)張量網(wǎng)絡(luò)（neuraltensornetwork，NTN）來比較兩個(gè)圖嵌人之間的相似性。與傳統(tǒng)的線性方法相比，NTN能夠有效捕捉圖級嵌入之間的非線性關(guān)系和復(fù)雜交互，計(jì)算過程如式（15）所示。

其中： W^[1：k]∈R^d×d×k 是權(quán)重張量; V∈R^k×2d 表示標(biāo)準(zhǔn)神經(jīng)網(wǎng)絡(luò)的權(quán)重向量； b∈R^k 是偏置向量；ReLU Ξ（Λ?Λ） 是非線性激活函數(shù)。

3.4圖編輯距離計(jì)算和圖編輯路徑生成

本節(jié)結(jié)合上文獲得的節(jié)點(diǎn)級交互信息和圖級交互信息，計(jì)算輸入圖對的相似度和圖編輯距離，并通過節(jié)點(diǎn)匹配矩陣提取節(jié)點(diǎn)匹配關(guān)系，基于這些匹配關(guān)系生成相應(yīng)的圖編輯路徑。

首先，對節(jié)點(diǎn)匹配矩陣使用softmax函數(shù)進(jìn)行歸一化處理，以提取每一行節(jié)點(diǎn)對的相對重要性。然后，將處理后的節(jié)點(diǎn)匹配矩陣與匹配成本矩陣進(jìn)行點(diǎn)乘操作，計(jì)算整體節(jié)點(diǎn)匹配成本。其次，采用多層感知機(jī)處理圖級比較中生成的相似度向量，以生成一個(gè)標(biāo)量。計(jì)算過程如式（16）所示。

其中 ∴f（θ?θ） 是一個(gè)無參數(shù)函數(shù)，用于調(diào)整結(jié)果的尺度； H¹ 和H² 是圖級嵌入； GED（G₁，G₂） 是圖 G₁ 和圖 G₂ 的預(yù)測圖編輯距離值。

為了便于模型在訓(xùn)練過程中進(jìn)行損失計(jì)算和優(yōu)化參數(shù)，引入sigmoid函數(shù)，將圖編輯距離映射到（0，1），作為圖相似度得分。計(jì)算過程如式（17）所示。

其中： σ（?） 是sigmoid函數(shù); score（G₁，G₂） 是圖 G₁ 和圖 G₂ 的預(yù)測圖相似度得分。

此外，對于圖編輯路徑的生成，本文采用文獻(xiàn)[21]提出的k -最佳匹配方法。該方法通過將節(jié)點(diǎn)匹配矩陣構(gòu)造成二分圖，在二分圖上計(jì)算前 k 個(gè)最大權(quán)重匹配，針對每種匹配關(guān)系，采用基于標(biāo)簽集的GED下界方法[23]生成相應(yīng)的圖編輯路徑。

3.5 模型訓(xùn)練

由于本文旨在預(yù)測圖編輯距離值并尋找最優(yōu)節(jié)點(diǎn)匹配（用于生成圖編輯路徑），所以模型訓(xùn)練過程中的損失函數(shù)包含 L_value 和 L_match 兩部分，分別表示GED值損失和節(jié)點(diǎn)匹配損失。其中， λ 是一個(gè)超參數(shù)。

3.5.1節(jié)點(diǎn)匹配損失函數(shù)

在模型訓(xùn)練過程中，節(jié)點(diǎn)匹配矩陣 M_match 通過與真實(shí)匹配矩陣 M^* 進(jìn)行監(jiān)督學(xué)習(xí)，來減少兩者之間的差異。其中，真實(shí)匹配矩陣是指在將源圖轉(zhuǎn)換為目標(biāo)圖所需最少編輯操作數(shù)的

情況下，圖對中節(jié)點(diǎn)之間的真實(shí)匹配關(guān)系，該矩陣中每個(gè)元素只能取值1或0。本文采用二元交叉熵?fù)p失作為節(jié)點(diǎn)匹配損失函數(shù)，來不斷優(yōu)化節(jié)點(diǎn)匹配矩陣，計(jì)算公式如式（19）所示。

logM_match[i][j]+（1-M_[i][j]^*）?log（1-M_match[i][j]）） （19其中：BCELoss（·）是二元交叉熵?fù)p失函數(shù)。

3.5.2 GED值損失函數(shù)

由于機(jī)器學(xué)習(xí)模型傾向于預(yù)測小范圍內(nèi)的值，所以在訓(xùn)練前將真實(shí)的GED值進(jìn)行歸一化處理，將其轉(zhuǎn)換為（0，1）的圖相似度得分。本文采用指數(shù)函數(shù)進(jìn)行轉(zhuǎn)換，計(jì)算過程如式（20）所示。

其中： λ（x）=e^-x GED^*（G₁，G₂） 是圖 G₁ 和圖 G₂ 的真實(shí)圖編輯距離值。

采用均方誤差來計(jì)算預(yù)測圖相似度得分與真實(shí)圖相似度得分之間的差異，從而作為值損失。值損失函數(shù)如式（21）所示。

L_value=（score（G₁，G₂）-score^*（G₁，G₂））²

其中： score^*（G₁，G₂） 是圖 G₁ 和圖 G₂ 的真實(shí)圖相似度得分。

3.6 復(fù)雜度分析

本節(jié)分析CFSA的時(shí)間和空間復(fù)雜度。CFSA的時(shí)間和空間復(fù)雜度由節(jié)點(diǎn)級交互、圖級交互和圖編輯距離計(jì)算三部分組成。

節(jié)點(diǎn)級交互模塊的時(shí)間開銷主要包括節(jié)點(diǎn)嵌入生成和節(jié)點(diǎn)級比較，使用 n=max{∣V₁∣，∣V₂∣} 和 m=max{∣E₁∣，∣E₂∣} 表示輸入圖對的尺度信息。其中，節(jié)點(diǎn)嵌入生成包括圖同構(gòu)網(wǎng)絡(luò)和跨圖特征學(xué)習(xí)方法。經(jīng)分析，圖同構(gòu)網(wǎng)絡(luò)和跨圖特征學(xué)習(xí)方法的時(shí)間復(fù)雜度分別為 O（Lmd+Lnd² ）和 O（n²d） ，節(jié)點(diǎn)級比較的時(shí)間復(fù)雜度為 O（knd²+kn²d+k²n²） 。其中， L 表示圖同構(gòu)網(wǎng)絡(luò)層數(shù)（ L=3 》 d 和 k 分別表示嵌入維度和權(quán)重張量的維度。圖級交互模塊的時(shí)間開銷主要包括圖級嵌入生成和圖級比較。其中，圖級嵌入生成包括結(jié)構(gòu)感知多頭注意力機(jī)制和平均池化操作。經(jīng)分析，圖級嵌入部分的時(shí)間復(fù)雜度為 O（n²d+ nd² ），圖級比較的時(shí)間復(fù)雜度為 O（kd²） 。圖編輯距離計(jì)算模塊的時(shí)間開銷為 O（n²） 。由于超參數(shù) L，d 和 k 為常數(shù)標(biāo)量（與圖規(guī)模無關(guān)），所以，CFSA的時(shí)間復(fù)雜度為 O（n²） 。

節(jié)點(diǎn)級交互模塊的空間復(fù)雜度包括節(jié)點(diǎn)嵌入存儲部分和中間計(jì)算結(jié)果存儲部分。經(jīng)分析，圖同構(gòu)網(wǎng)絡(luò)和跨圖特征學(xué)習(xí)方法的空間復(fù)雜度分別為 O（nd+d²） 和 O（n²d） ，節(jié)點(diǎn)級比較的空間復(fù)雜度為 O（kd²+kn²） 。圖級交互模塊的空間復(fù)雜度主要包括結(jié)構(gòu)感知多頭注意力機(jī)制的中間計(jì)算結(jié)果。經(jīng)分析，結(jié)構(gòu)感知多頭注意力機(jī)制的空間復(fù)雜度為 O（n²+d²） ，圖級比較的空間復(fù)雜度為 O（kd²） 。圖編輯距離計(jì)算模塊的空間復(fù)雜度為 O（n²） 。因此，CFSA的空間復(fù)雜度為 O（n²） 。

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

本文在三個(gè)常用的公開數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)，對比了本文提出的CFSA與基線模型在圖編輯距離預(yù)測任務(wù)中的性能，還進(jìn)行了相關(guān)消融實(shí)驗(yàn)，并分析了不同超參數(shù)設(shè)置對模型性能的影響。

4.1數(shù)據(jù)集

本文采用了AIDS[21] Linux^[21] 和IMDB[21]三個(gè)真實(shí)圖數(shù)

據(jù)集。表1列出了這些圖數(shù)據(jù)集的統(tǒng)計(jì)信息，其中g(shù)raphs、 和 ∣E∣_max 分別表示數(shù)據(jù)集中圖的數(shù)量、平均節(jié)點(diǎn)數(shù)、平均邊數(shù)、最大節(jié)點(diǎn)數(shù)和最大邊數(shù)。

4.2 實(shí)驗(yàn)設(shè)置和評價(jià)指標(biāo)

實(shí)驗(yàn)環(huán)境中使用的操作系統(tǒng)為CentOS8.4.2105，CPU為IntelCorei5-1O400F，64GBRAM，GPU為NVIDIAGeForceRTX3070。編程環(huán)境為Python3.8，PyTorch1.10.1。

對于所有數(shù)據(jù)集，以6：2：2的比例隨機(jī)劃分為訓(xùn)練集、驗(yàn)證集和測試集。在驗(yàn)證集或測試集中的每個(gè)圖 G ，本文將從訓(xùn)練集中隨機(jī)選擇100個(gè)圖，以形成100個(gè)圖對用于驗(yàn)證或測試。對于圖對之間的真實(shí)圖編輯距離，在AIDS和Linux數(shù)據(jù)集中采用窮舉搜索進(jìn)行精確計(jì)算。在IMDB數(shù)據(jù)集中，對于節(jié)點(diǎn)數(shù)不超過10的圖，同樣采用窮舉搜索精確計(jì)算圖編輯距離。對于節(jié)點(diǎn)數(shù)超過10的圖，采用 TaGSim^[12] 中提出的圖對生成器為每個(gè)圖生成測試圖對。具體而言，對于每個(gè)圖隨機(jī)進(jìn)行一系列編輯操作，以生成合成圖，并將編輯操作數(shù)視為圖編輯距離值。

對于初始節(jié)點(diǎn)嵌入，為具有節(jié)點(diǎn)標(biāo)簽的AIDS數(shù)據(jù)集采用one-hot編碼方案，而Linux和IMDB數(shù)據(jù)集中的節(jié)點(diǎn)無標(biāo)簽，采用常量編碼方案。在3層圖同構(gòu)網(wǎng)絡(luò)中，每層的輸出特征大小依次為128、64和32；多頭注意力機(jī)制中，注意力頭數(shù)設(shè)置為8；多視角匹配方法中，使用16個(gè)參數(shù)矩陣，每個(gè)矩陣大小為 32×32;k -最佳匹配框架中， k 值設(shè)置為100，損失函數(shù)中的參數(shù) λ 在AIDS和Linux數(shù)據(jù)集中設(shè)為10，在IMDB數(shù)據(jù)集中設(shè)為 1^[21] 。訓(xùn)練過程中，批處理大小設(shè)定為128；使用dropout防止過擬合，dropout率設(shè)置為0.5;使用Adam進(jìn)行模型參數(shù)的優(yōu)化，優(yōu)化器中學(xué)習(xí)率設(shè)置為0.001，權(quán)重衰減設(shè)置為 0.000 5 。

為全面評估本文模型在相似性計(jì)算任務(wù)上的性能，采用以下七個(gè)指標(biāo)進(jìn)行評估：準(zhǔn)確率（ACC）[21]、均方誤差（MSE）[18]平均絕對誤差（MAE）[21]、Spearman 等級相關(guān)系數(shù) （ρ）^[18] Kendall 等級相關(guān)系數(shù)（τ）[18]、 準(zhǔn)確率 （p@k）^[18] 、時(shí)間（time）[21]。其中，ACC評估的是圖編輯距離值預(yù)測的準(zhǔn)確率，其值越大表示模型性能越好；MSE和MAE評估的是模型預(yù)測結(jié)果與真實(shí)結(jié)果的誤差情況，其值越小表示模型性能越好； _;ρ 、τ_?p@k 評估的是排名指標(biāo)，其值越大表示模型性能越好。時(shí)間指標(biāo)測量的是計(jì)算100個(gè)圖對GED所需的運(yùn)行時(shí)間。

4.3基線模型

本文選擇了一些具有代表性的模型作為基線模型，根據(jù)能否生成編輯路徑分為以下兩組：

a）不可恢復(fù)編輯路徑的圖相似度計(jì)算模型： SimGNN^[10] TaGSim^[12] 、 GPN^[20] 、MGMN[14]、GEDGNN[21]、CLSim[18]

b）可恢復(fù)編輯路徑的圖相似度計(jì)算模型：Greedy算法[21，24] ΔNoah^[20] 、GEDGNN-matching[21]。

本文分別使用同類的CFSA和CFSA-matching與上述兩類模型進(jìn)行比較。其中，CFSA采用端到端學(xué)習(xí)的方式來預(yù)測GED值;CFSA-matching將CFSA中生成的節(jié)點(diǎn)匹配矩陣與

GEDGNN中的后處理算法相結(jié)合，來預(yù)測GED值并生成圖編輯路徑。

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

本節(jié)分別在AIDS、Linux和IMDB三個(gè)公開數(shù)據(jù)集上對比了本文CFSA和對比方法，并進(jìn)行了消融實(shí)驗(yàn)和參數(shù)敏感性實(shí)驗(yàn)。

4.4.1整體性能分析

本節(jié)給出并分析了本文CFSA與基線模型在ACC、MSE、 時(shí)間指標(biāo)的對比實(shí)驗(yàn)結(jié)果，如表2～4所示。其中，基線模型的實(shí)驗(yàn)數(shù)據(jù)按照文獻(xiàn)[18，21]中的結(jié)果，此外因?yàn)镸GMN嵌入維度和dropout率設(shè)置與本文不同，公平起見，按照本文參數(shù)重現(xiàn)了其過程。另外，表中加粗的數(shù)據(jù)為本評估指標(biāo)的最優(yōu)結(jié)果，“一”表示相關(guān)實(shí)驗(yàn)數(shù)據(jù)在原文中未報(bào)道。

從表2～4的實(shí)驗(yàn)結(jié)果中可看到，CFSA在AIDS、Linux和IMDB數(shù)據(jù)集中絕大多數(shù)指標(biāo)上均取得了最優(yōu)結(jié)果。在第一類不可恢復(fù)編輯路徑的圖相似度計(jì)算模型中，對比基線模型中最優(yōu)的GEDGNN，本文CFSA在運(yùn)行時(shí)間上略有增加，這是由于引入的跨圖節(jié)點(diǎn)特征方法和結(jié)構(gòu)感知多頭注意力機(jī)制增加了時(shí)間開銷。但是，GEDGNN的時(shí)間復(fù)雜度為 O（n²）^[21] ，與本文一致。此外，CFSA在性能方面有顯著提升。CFSA在AIDS、Linux和IMDB數(shù)據(jù)集上的ACC指標(biāo)分別提升了4.8、5.1、15.8百分點(diǎn)。在四項(xiàng)排名指標(biāo)上，CFSA相較于絕大多數(shù)基線模型也均有提升。這是因?yàn)镃FSA一方面通過跨圖節(jié)點(diǎn)特征學(xué)習(xí)方法，有效學(xué)習(xí)跨圖節(jié)點(diǎn)之間的特征信息；另一方面通過結(jié)構(gòu)感知多頭注意力機(jī)制，有效學(xué)習(xí)了圖中節(jié)點(diǎn)間的高階關(guān)系以及大圖中豐富的結(jié)構(gòu)信息，使得模型的嵌入信息更全面，從而得到更好的預(yù)測結(jié)果。而早期的SimGNN只對節(jié)點(diǎn)的局部特征進(jìn)行學(xué)習(xí)；TaGSim和GPN均忽略了遠(yuǎn)距離節(jié)點(diǎn)間的潛在關(guān)系;MGMN缺乏對跨圖節(jié)點(diǎn)間細(xì)粒度對應(yīng)關(guān)系的學(xué)習(xí)；CLSim 通過采用跨層次特征提取來整合不同層次信息，但是它只是對跨層次特征進(jìn)行簡單拼接；GEDGNN在特征嵌入時(shí)，忽略了跨圖節(jié)點(diǎn)間的潛在相關(guān)性，且未考慮節(jié)點(diǎn)間高階關(guān)系的重要性。在AIDS和Linux數(shù)據(jù)集，CFSA在 ρ 或 τ 指標(biāo)上取得了次優(yōu)效果。這是由于CFSA強(qiáng)調(diào)細(xì)粒度節(jié)點(diǎn)間的匹配關(guān)系，可能在全局排序上存在不足，但是其在 p@10 和 指標(biāo)上實(shí)現(xiàn)了更高的準(zhǔn)確率。

在第二類可恢復(fù)編輯路徑的圖相似度計(jì)算模型中，本文CFSA-matching在AIDS、Linux和IMDB數(shù)據(jù)集上的運(yùn)行時(shí)間均低于其他基線模型，且性能上也均有提升。同時(shí)，CFSAmatching在三個(gè)數(shù)據(jù)集上的ACC指標(biāo)相比于GEDGNN-mathing分別提升了 2.5，3.4，1.0 百分點(diǎn)，其他各項(xiàng)指標(biāo)也均取得最優(yōu)效果。這是因?yàn)橥ㄟ^學(xué)習(xí)跨圖節(jié)點(diǎn)特征信息后生成的節(jié)點(diǎn)匹配矩陣更有效地捕捉了兩個(gè)圖之間節(jié)點(diǎn)的相似性。而Greedy采用貪婪算法直接生成節(jié)點(diǎn)匹配矩陣，導(dǎo)致節(jié)點(diǎn)匹配矩陣值較差；Noah方法通過GPN優(yōu)化 A^* 算法，但由于計(jì)算 A^* 搜索樹中每個(gè)狀態(tài)的估計(jì)成本時(shí)采用GPN生成的估計(jì)成本函數(shù)，導(dǎo)致不準(zhǔn)確值的累積，從而預(yù)測結(jié)果較差；GEDGNN采用交叉矩陣模型生成節(jié)點(diǎn)匹配矩陣，但是該模塊中輸入的節(jié)點(diǎn)嵌入僅學(xué)習(xí)了節(jié)點(diǎn)的局部特征。在IMDB數(shù)據(jù)集上，Noah的運(yùn)行時(shí)間超過 24h ，因此實(shí)驗(yàn)中用“一”表示。此外，第二類模型未計(jì)算輸人圖對間的相似度，因此該類模型的MSE指標(biāo)均用“—”表示。

表2AIDS數(shù)據(jù)集整體性能評估Tab.2Overall performance evaluation of the AIDS dataset

表3Linux數(shù)據(jù)集整體性能評估Tab.3Overall performance evaluation of the Linuxdataset

表4IMDB數(shù)據(jù)集整體性能評估

Tab.4Overall performanceevaluation of theIMDB dataset

此外，圖5直觀展示了本文模型與基線模型在GED預(yù)測任務(wù)中的均方誤差。圖6可視化了本文模型在三個(gè)數(shù)據(jù)集上執(zhí)行GED預(yù)測時(shí)，MAE指標(biāo)的變化曲線。

圖5可見，在AIDS和Linux數(shù)據(jù)集上，CFSA的MSE指標(biāo)優(yōu)于其他基線模型。然而，在IMDB數(shù)據(jù)集上，CFSA在MSE指標(biāo)取得次優(yōu)效果，這是由于模型對真實(shí)相似度得分的轉(zhuǎn)換機(jī)制不同。其中，CFSA采用指數(shù)函數(shù)進(jìn)行真實(shí)相似度得分轉(zhuǎn)換，而GEDGNN采用線性函數(shù)轉(zhuǎn)換。由于IMDB為大圖數(shù)據(jù)集，指數(shù)函數(shù)轉(zhuǎn)換得到的相似度較高，從而導(dǎo)致MSE指標(biāo)偏高。圖6可見，隨著訓(xùn)練輪數(shù)的增加，MAE指標(biāo)逐漸收斂。這一趨勢表明，CFSA在訓(xùn)練過程中不斷優(yōu)化其預(yù)測性能，且在第80個(gè)epoch后MAE指標(biāo)趨于穩(wěn)定。

圖6平均絕對誤差變化曲線Fig.6Mean absolute error variation curve

4.4.2消融實(shí)驗(yàn)

本節(jié)通過消融實(shí)驗(yàn)來驗(yàn)證CFSA中的跨圖節(jié)點(diǎn)特征學(xué)習(xí)方法和結(jié)構(gòu)感知多頭注意力機(jī)制的有效性，實(shí)驗(yàn)結(jié)果如表5所示。其中： w/o cross表示不考慮跨圖節(jié)點(diǎn)信息，只使用卷積網(wǎng)絡(luò)學(xué)習(xí)局部特征； w/0 MHSA表示不考慮結(jié)構(gòu)信息的多頭注意力，只使用簡單全局注意力學(xué)習(xí)全局特征。

表5可見，CFSA在三個(gè)真實(shí)數(shù)據(jù)集上的各項(xiàng)指標(biāo)均優(yōu)于w/ocross和w/oMHSA。綜合來看，結(jié)構(gòu)感知多頭注意力機(jī)制對實(shí)驗(yàn)結(jié)果影響較大，相比于不采用該機(jī)制的模型，預(yù)測準(zhǔn)確率在AIDS、Linux和IMDB三個(gè)數(shù)據(jù)集上分別提升了2.2、2.7、16.1百分點(diǎn)，在大圖數(shù)據(jù)集中更為明顯。實(shí)驗(yàn)結(jié)果也驗(yàn)證了使用跨圖節(jié)點(diǎn)特征學(xué)習(xí)方法可以發(fā)現(xiàn)跨圖節(jié)點(diǎn)間隱含的特征信息，且結(jié)構(gòu)感知多頭注意力機(jī)制可以深入挖掘圖中節(jié)點(diǎn)的高階關(guān)系，從而有效處理復(fù)雜圖結(jié)構(gòu)數(shù)據(jù)。

4.4.3參數(shù)敏感性分析

本節(jié)對CFSA在AIDS、Linux和IMDB數(shù)據(jù)集上研究了不同卷積網(wǎng)絡(luò)對模型性能的影響，另外，在AIDS數(shù)據(jù)集上，采用不同層數(shù)的圖同構(gòu)網(wǎng)絡(luò)研究模型層數(shù)對CFSA性能的影響。在Linux數(shù)據(jù)集上，研究節(jié)點(diǎn)嵌入維度、結(jié)構(gòu)感知多頭注意力機(jī)制中注意力頭數(shù)量、dropout率對CFSA性能的影響，以及 k 最佳匹配框架中不同 k 值對CFSA-matching性能的影響。

圖7（a）可見，圖卷積網(wǎng)絡(luò)GCN在GED預(yù)測任務(wù)中表現(xiàn)不佳，由于GCN依賴于聚合鄰居節(jié)點(diǎn)的特征進(jìn)行學(xué)習(xí)，在聚合過程中容易受到鄰居節(jié)點(diǎn)噪聲的影響，并且無法有效處理復(fù)雜的拓?fù)潢P(guān)系。相比之下，圖同構(gòu)網(wǎng)絡(luò)GIN在GED預(yù)測任務(wù)中表現(xiàn)更好，因?yàn)镚IN中采用單射聚合，確保節(jié)點(diǎn)特征在聚合過程保持唯一性，且能夠?qū)⒉煌膱D結(jié)構(gòu)映射到不同的嵌入空間中，從而有效地區(qū)別不同的圖結(jié)構(gòu)。

圖7（b）可見，隨著圖同構(gòu)網(wǎng)絡(luò)卷積層數(shù)的增加，本文模型在圖編輯距離預(yù)測準(zhǔn)確率方面先增加后降低。因?yàn)榫矸e網(wǎng)絡(luò)層數(shù)較低時(shí)，增加模型層數(shù)有利于提取節(jié)點(diǎn)間的高階特征，從而獲取更全面的嵌入信息，顯著提高節(jié)點(diǎn)嵌入的質(zhì)量。然而，持續(xù)增加網(wǎng)絡(luò)層數(shù)，會導(dǎo)致梯度消失或過擬合現(xiàn)象，使得模型無法有效優(yōu)化參數(shù)，從而降低了模型的預(yù)測準(zhǔn)確率。

圖7（c）可見，隨著節(jié)點(diǎn)嵌入維度的增加，CFSA在圖編輯距離預(yù)測準(zhǔn)確率方面不斷增加。這是由于低維嵌入空間存在表征瓶頸，無法充分編碼表示節(jié)點(diǎn)的特征信息，當(dāng)嵌人維度超過32維時(shí)，CFSA評估指標(biāo)趨于穩(wěn)定。圖7（d）可見，適當(dāng)增加結(jié)構(gòu)感知多頭注意力機(jī)制中的注意力頭數(shù)量，可以提升模型的預(yù)測準(zhǔn)確率。當(dāng)注意力頭數(shù)設(shè)置較低時(shí)，雖然可以降低模型的計(jì)算量，但是會限制模型的特征捕捉能力，難以充分捕捉復(fù)雜數(shù)據(jù)中的多樣化特征，從而導(dǎo)致模型的表達(dá)能力不足。但是，過度增加注意力頭數(shù)，會導(dǎo)致模型生成冗余特征并降低計(jì)算效率。圖7（e）可見，隨著神經(jīng)網(wǎng)絡(luò)中dropout率的增加，CFSA在圖編輯距離預(yù)測準(zhǔn)確率方面先增加后降低。這是由于當(dāng)dropout率較低時(shí)，模型可能存在過擬合問題。當(dāng)增加至0.5時(shí)，正則化效果最佳，預(yù)測準(zhǔn)確率最高。但繼續(xù)增加dropout率，可能會過度丟棄神經(jīng)元，導(dǎo)致模型欠擬合。圖7（f）可見，隨著k-最佳匹配中 k 值的不斷增大，CFSA-matching的預(yù)測準(zhǔn)確率不斷提升。這是由于當(dāng) k 值較大時(shí)，模型可以學(xué)習(xí)更多組節(jié)點(diǎn)匹配關(guān)系，從而得到更準(zhǔn)確的預(yù)測結(jié)果。但是，較大的 k 值會增加模型的時(shí)間開銷。綜上，將模型層數(shù)設(shè)定為3、節(jié)點(diǎn)嵌入維度設(shè)定為32、注意力頭數(shù)設(shè)定為8、dropout率設(shè)定為 0.5，k 值設(shè)定為100時(shí)，模型能夠獲得更佳的效果。

圖7參數(shù)敏感性分析

Fig.7Parametersensitivityanalysis

5結(jié)束語

本文提出了一種基于跨圖特征融合和結(jié)構(gòu)感知注意力的圖相似度計(jì)算模型CFSA，能有效整合不同層次的節(jié)點(diǎn)特征信息，并捕獲節(jié)點(diǎn)間高階關(guān)系。首先，提出一種跨圖節(jié)點(diǎn)特征學(xué)習(xí)方法，引入跨圖注意力機(jī)制學(xué)習(xí)兩個(gè)圖節(jié)點(diǎn)之間的跨圖交互信息，并將節(jié)點(diǎn)的跨圖交互特征和局部特征相融合。此外，提出一種結(jié)構(gòu)感知型多頭注意力機(jī)制，結(jié)合節(jié)點(diǎn)特征信息和圖結(jié)構(gòu)信息，挖掘節(jié)點(diǎn)之間的高階關(guān)系。在多個(gè)真實(shí)數(shù)據(jù)集上的大量實(shí)驗(yàn)結(jié)果表明，本文模型在圖編輯距離計(jì)算任務(wù)中獲得了更高的準(zhǔn)確率且優(yōu)于其他基線模型。后續(xù)工作將考慮融合子圖級特征信息，并對注意力機(jī)制進(jìn)行優(yōu)化，在降低模型時(shí)間復(fù)雜度的基礎(chǔ)上提升模型的整體性能。

參考文獻(xiàn)：

[1］王光，尹凱．融合用戶社交關(guān)系的自適應(yīng)圖卷積推薦算法［J]. 計(jì)算機(jī)應(yīng)用研究，2024，41（2）：482-487．（WangGuang，Yin Kai.Adaptive graph convolutional recommendation algorithm integrating user social relationships[J].Application Research of Computers，2024，41（2）：482-487.）

[2]Lee SW，TanveerJ，Rahmani A M，et al．SFGCN：synergetic fusion-based graph convolutional networks approach for link prediction in social networks[J]. Information Fusion，2025，114：102684.

[3]Yu Hui，Xu Wenxin，Tan Tian，etal.Predictionof drug-target bindingaffinitybased onmulti-scale feature fusion[J].Computersin BiologyandMedicine，2024，178：108699.

［4]吳月明，齊蒙，鄒德清，等，圖卷積網(wǎng)絡(luò)的抗混淆安卓惡意軟件 檢測[J]．軟件學(xué)報(bào)，2023，34（6）：2526-2542.（Wu Yueming， QiMeng，Zou Deqing，et al.Obfuscation-resilient Android malware detection based on graph convolutional networks[J].Journal of Software，2023，34（6）：2526-2542.）

[5]Bunke H. On a relation between graph edit distance and maximum common subgraph[J].Pattern Recognition Letters，1997，18 （8）：689-694.

[6]Blumenthal DB，Gamper J.On the exact computation of the graph edit distance[J].Pattern Recognition Letters，2020，134：46-57.

[7］邱珍，鄭朝暉．面向圖相似性搜索的高效圖編輯距離算法［J]. 計(jì)算機(jī)應(yīng)用研究，2023，40（2）：371-377．（Qiu Zhen，Zheng Zhaohui.Efcient graph edit distance algorithm forgraph similarity search[J]. Application Research of Computers，2023，40（2）： 371-377.）

[8]Yang Peilun，Wang Hanchen，Yang Jianye，et al. Deep learning approaches for similarity computation：a survey[J]. IEEE Trans on KnowledgeandData Engineering，2024，36（12）：7893-7912.

[9]Khoshraftar S，An Aijun：A survey on graph representation learning methods[J].ACMTranson IntelligentSystemsand Technology，2024，15（1）：1-55.

[10]Bai Yunsheng，Ding Hao，Bian Song，et al. SimGNN：a neural network approach to fast graph similarity computation[C]//Proc of the 12th ACM International Conference on Web Search and Data Mining. NewYork：ACMPress，2019：384-392.

[11]Bai Yunsheng，Ding Hao，Gu Ken，et al.Learning-based efficient graph similarity computation via multi-scale convolutional set matching [C]//Proc of AAAI Conference on Artificial Intelligence.Palo Alto， CA：AAAI Press，2020：3219-3226.

[12]Bai Jiyang，Zhao Peixiang.TaGSim[J]. Proc of the VLDB Endowment，2021，15（2）：335-347.

[13]LiYujia，Gu Chenjie，DullienT，etal.Graph matching networks for learning the similarity of graph structured objects[C]//Procof the 36th International Conference on Machine Learning.[S.1.]：PMLR， 2019：3835-3845.

[14]Ling Xiang，Wu Lingfei，Wang Saizhuo，etal.Multilevel graph matching networks for deep graph similarity learning[J].IEEE Trans on Neural Networks and Learning Systems，2023，34 （2）： 799-813.

[15]Zhang Zhen，Bu Jiajun，Ester M，et al.H2MN：graph similarity learning with hierarchical hypergraph matching networks[C]// Proc of the 27th ACM SIGKDD Conference on Knowledge Discovery amp; Data Mining.New York：ACM Press，2021：2274-2284.

[16］安麗霞，吳安彪，袁野，等．基于元結(jié)構(gòu)匹配與有偏采樣的圖相 似度計(jì)算方法[J]．計(jì)算機(jī)學(xué)報(bào)，2023，46（7）：1513-1531.（An Lixia，Wu Anbiao，YuanYe，etal.Graph similaritycomputation method based on meta-structures matching and biased sampling[J]. Chinese Journal of Computers，2023，46（7）：1513-1531.）

[17]侯雅靜，寧博，海潮，等.NAGSim：一種基于圖神經(jīng)網(wǎng)絡(luò)與注意 力機(jī)制的圖相似計(jì)算模型［J]．小型微型計(jì)算機(jī)系統(tǒng)，2023，44 （8）： 1665-1671.（Hou Yajing，Ning Bo，Hai Chao，et al. NAGSim：a graph similarity model based on graph neural networks and attention mechanism[J].Journal of Chinese Computer Systems， 2023，44（8）： 1665-1671.）

[18]Zou Cuifang，Lu Guangquan，Du Longqing，et al. Graph similarity learning for cross-level interactions [J]. Information Processing amp; Management，2025，62（1）：103932.

[19]Wang Runzhong，Zhang Tianqi，Yu Tianshu，et al.Combinatorial learning of graph edit distance via dynamic embedding[C]// Proc of IEEE/CVF Conference on Computer Vision and Pattern Recognition. Piscataway，NJ： IEEE Press，2021：5237-5246.

[20]Yang Lei， Zou Lei.Noah：neural-optimized A search algorithm for graph edit distance computation [C]// Proc of the 37th Intermational Conference on Data Engineering.Piscataway，NJ：IEEE Press， 2021：576-587.

[21]Piao Chengzhi，Xu Tingyang，Sun Xiangguo，et al. Computing graph edit distance Via neural graph matching[J].Proc of the VLDB Endowment，2023，16（8）：1817-1829.

[22] Xu K，Hu W，Leskovec J，et al. How powerful are graph neural networks？［EB/OL].（2018-10-01）. htps：//arxiv.org/ab/1810. 00826.

[23] Chang Lijun， Feng Xing， Lin Xuemin，et al. Speeding up GED verification for graphsimilaritysearch[C]//Proc of the 36th International Conference on Data Engineering. Piscataway，NJ： IEEE Press， 2020： 793-804.

[24]Kuhn H W. The Hungarian method for the assignment problem [J]. NavalResearch LogisticsQuarterly，1955，2（1-2）：83-97.