面向圖相似性搜索的高效圖編輯距離算法

摘 要：在圖相似性搜索問題中，圖編輯距離是較為普遍的度量方法，其計算性能很大程度上決定了圖相似性搜索算法的性能。針對傳統圖編輯距離算法中存在的因大量冗余映射和較大搜索空間導致的性能低下問題，提出了一種改進的圖編輯距離算法。該算法首先對圖中頂點進行等價劃分，以此計算映射編碼來判斷等價映射；然后定義映射完整性更新等價映射優先級，選出主映射參與擴展；其次，設計高效的啟發式函數，提出基于映射編碼的下界計算方法，快速得到最優映射。最后，將改進的圖編輯距離算法擴展應用于圖相似性搜索。在不同數據集上的實驗結果表明，該算法具有更好的搜索性能，在搜索空間上最大可降低49%，速度提升了約29%。

關鍵詞：圖編輯距離；等價映射；映射編碼；下界計算；圖相似性搜索

中圖分類號：TP391 文獻標志碼：A 文章編號：1001-3695（2023）02-009-0371-07

doi： 10.19734/j.issn.1001-3695.2022.06.0303

Efficient graph edit distance algorithm for graph similarity search

Qiu Zhena，b， Zheng Zhaohuia，b

（a. School of Computer Science amp; Technology， b. Jiangsu Cyberspace Security Engineering Laboratory， Soochow University， Suzhou Jiangsu 215008， China）

Abstract：In graph similarity search， the graph edit distance algorithm is a common measurement method and its performance largely determines the graph similarity search performance. Aiming at the low performance of the traditional graph edit distance algorithm， such as many redundant mappings and large search space， this paper proposed an improved graph edit distance algorithm. Firstly， it divided all the vertices in the graph into several equivalent classes， by computing mapping encoding to judge equivalent mapping. Then it defined the mapping integrity to update the priority of equivalent mapping and selected main mapping to extend. Secondly， in order to quickly obtain the optimal mapping， it proposed a lower bound computation method based on the mapping encoding and designed an effective heuristic function. Finally， it applied the improved graph edit distance algorithm to graph similarity search. Experimental results show that the proposed algorithm has better search performance on multiple datasets， which can decrease the search space up to 49% and the speed increases about 29%.

Key words：graph edit distance; equivalent mapping; mapping encoding; lower bound computation; graph similarity search

0 引言

在大數據時代，隨著信息技術的迅速發展，數據量呈指數級增長，其中大部分數據包含復雜的屬性信息和語義結構［1］。為實現復雜數據的高效存儲［2，3］與查詢，通常將這些數據實體以及實體之間的關系建模為圖結構，對復雜數據的處理便轉換為如圖匹配［4～6］、圖相似性搜索［7，8］和圖聚類［9］等圖的基本操作。例如在藥物發現領域，將分子表征為圖結構，為查詢與新化合物相似的分子，推斷新化合物的分子性質，通常采用圖相似性搜索算法完成這一過程。此外，圖結構現已被廣泛應用于計算機視覺、模式識別、生物化學等領域［10～14］。

面對不斷增長的圖數據規模，設計準確高效的圖相似性度量方法［15～17］至關重要。圖編輯距離（graph edit distance，GED）［18］作為精確衡量圖之間結構差異的常用度量指標，幾乎可以評估所有類型的圖，其計算效率在很大程度上決定了圖相似性搜索算法的性能。

圖編輯距離是指將源圖轉換為目標圖所需的最小編輯操作代價之和。通過為兩個圖建立頂點之間的一一映射，將搜索空間組織為搜索樹，樹中的內部節點表示部分映射，葉子節點代表完整映射。樹中的每個映射都有一個編輯代價值，由已映射部分的精確編輯代價值和未映射部分的估計代價值組成。計算圖編輯距離的過程就是在搜索樹中求解具有最小編輯代價的完整映射過程。根據算法求解精度，圖編輯距離算法分為精確圖編輯距離算法［19～21］和近似圖編輯距離算法［22～24］。精確圖編輯距離算法因其求解空間大、時空復雜度高，一般用于求解小規模圖搜索問題；近似圖編輯距離算法可以在多項式時間內求解，主要用于精度要求不高但圖規模較大的圖相似性搜索問題。

本文針對精確圖編輯距離算法在大規模數據集上的應用展開研究，試圖通過降低其求解空間和時間復雜度擴展其適用的圖搜索問題規模。在已有研究中，最經典的算法是AGED［25］。該算法源自于1968年Nilsson提出的A算法，之后Riesen等人［26］首次將A算法應用于圖編輯距離，從而形成AGED。該算法基于頂點映射進行啟發式最佳優先搜索，保證找到一個最小的完整映射，但是其需要存儲大量中間映射狀態，對于含有n個頂點的數據圖，會產生n！個映射，導致占用巨大的搜索空間，使得該算法僅適用于規模較小的圖。為緩解這一問題，Abu-Aisheh等人［27］基于深度優先搜索提出DF-GED算法，通過構建頂點和邊的代價矩陣避免重復計算節點的代價，并將當前最優完整映射代價作為上界以便剪枝。其空間效率優于AGED，但該算法容易陷入局部最優。不同于以上兩種算法，Gouda等人［17］提出基于邊映射的CSI_GED算法，枚舉兩圖之間同構的公共子結構，該算法在稀疏圖上取得了良好的性能。AStar-BMa算法［20，28］提出基于分支結構的BMa下界，可以在更大程度上減少映射空間，但是該算法沒有考慮區分等價映射，導致花費較多的時間計算具有相同代價的冗余映射，且時間復雜度高達O（n4）。Chang等人［28］針對這一問題提出基于波束堆棧搜索的BSS_GED算法，通過識別冗余映射和無效映射減少搜索空間，但是該算法中等價映射定義不嚴格，無法識別由圖中的對稱結構誘導得到的冗余映射，導致去冗余映射的精度不夠，因此仍然存在可優化的空間。

綜上所述，目前的圖編輯距離算法仍然面臨映射空間較大、等價映射定義不嚴格、下界計算復雜度高等問題。研究發現，基于A的圖編輯距離算法的計算瓶頸在于映射擴展階段的大量計算，具體表現為：此過程中的大量冗余映射導致映射擴展次數過多，使得搜索空間樹很大，限制了搜索速度；針對大量等價映射，映射的選取方法會對搜索效率產生影響。針對以上兩個方面，本文對映射擴展過程作出優化，提出一種改進的圖編輯距離算法，并將其應用于圖相似性搜索，主要研究內容如下：

a）針對映射擴展過程中存在的大量冗余映射以及等價映射定義精度較低的問題，本文結合圖中頂點與邊的鄰域信息定義了更高精度的等價映射判定方法，并為映射建立編碼。通過映射編碼精確判定等價映射，大大降低了映射冗余度，減少映射擴展計算次數，減小了映射搜索空間。

b）針對映射擴展中等價映射簇中的映射選擇問題，定義映射完整性約束邊界，提出一種新的等價映射擴展方法，選擇完整性最大的等價映射作為主映射進行擴展比較，從而提高映射擴展的速度。

c）基于映射編碼與映射完整性約束，定義高效的啟發式函數，提出一種高性能的圖編輯距離算法。在大規模數據集上的實驗結果表明，相較于AGED和AStar-BMa算法，本文算法的運行時間最低，映射擴展數量與搜索空間均有較大幅度的降低，驗證了本文算法的有效性。

1 背景知識

本文將帶標簽圖g定義為一個三元組：g=（Vg，Eg，Lg）。其中：Vg={v1，v2，…，v|Vg|}表示圖g中的頂點集合；Eg表示邊集合；Lg表示頂點或邊的標簽標記函數；|Vg|和|Eg|分別表示圖g中頂點和邊的數量。表1給出了本文中使用的符號說明。

1.1 基本定義

定義1 圖同構。如果兩個圖g=（Vg，Eg，Lg）和q=（Vq，Eq，Lq），存在一個滿足以下條件的雙射函數h：Vg→Vq，則圖g和圖q同構。

定義2 圖編輯操作。圖編輯操作是指將圖q轉換為圖g，使得兩圖同構的基本操作，共包括六種基本操作：頂點u的插入與刪除、邊e的插入與刪除以及頂點或邊標簽的替換操作，其編輯代價分別記為cV（ε，u）、cV（u，ε）、cE（ε，e）、cE（e，ε）、cV（u，h（u））和cE（e，h（e））。

例1 如圖1所示，將圖q轉換為圖g的圖編輯操作過程和編輯代價具體表現為：a）刪除連接頂點B和C的邊b，編輯代價為cE（b，ε）；b）添加連接頂點A和B的邊b，編輯代價為cE（ε，b）；c）將頂點C替換為頂點A，編輯代價為cV（C，A）。

定義3 頂點映射。根據定義1可得兩圖中Vg到Vq的頂點映射，如果圖中所有頂點都已建立映射關系，則稱該映射為完整映射，否則判定為部分映射。

例2 現定義v→u為頂點v和u之間的映射關系，如圖2所示，f1={v1→u1，v2→u2，v3→u3}是Vg到Vq的一個部分映射，f2={v1→u1，v2→u2，v3→u3，v4→u4}是一個完整映射。

定義4 映射擴展。記u∈Vgf-和v∈Vqf-分別為圖g和q中的未映射頂點，對于部分映射f，其后繼映射為f′=f∪{u→v}，該過程稱為一次映射擴展。如圖2所示，映射f1到f2的過程為一次映射擴展。

定義5 映射的編輯代價。對于圖g到圖q的完整映射f，其編輯代價為該映射導出的編輯路徑長度，記為ηf（g，q）。對于部分映射f，定義其編輯代價下界為小于等于由f擴展得到的所有完整映射中的最小值，記為η（f）≤minf∈F（g，q）ηf（g，q）。其中，F（g，q）表示從頂點集合Vg到Vq的映射集合。

例3 如圖2所示，完整映射f2導出的編輯路徑為f2={v1→u1，v2→u2，v3→u3，v4→u4}，其長度為4，則ηf2（g，q）=4。

定義6 圖編輯距離。在所有完整映射中，編輯代價最小的映射為最優映射，其編輯代價即為圖編輯距離，記為GED（g，q），定義如下：

其中：F（g，q）表示從頂點集合Vg到Vq的映射集合。

1.2 AGED算法簡介

AGED算法采用基于頂點映射的啟發式搜索方法，將搜索過程組織成一棵搜索樹，深度優先搜索求得的最短路徑，即圖編輯距離。該算法的思路是：采用初始為空的優先隊列que維護映射狀態，每次迭代時，從que中選擇編輯代價下界最小的映射擴展，計算其子映射的編輯代價下界并入隊，最終首次從que中出隊的完整映射代價為圖編輯距離。對于圖1中的圖g和q，其搜索樹結構如圖3所示。圖中，level表示圖q的頂點映射序列。為簡潔表示，圖中僅給出部分映射路徑。

AGED算法主要分為以下三個子問題：

a）頂點映射序列。在對兩個圖執行頂點映射時，需要以源圖的頂點序列為基準執行映射，不同的頂點映射序列會產生不同空間大小的搜索樹。一般選取圖中最具代表性的頂點為起始點，深度優先搜索遍歷得到源圖的頂點映射序列。

b）頂點映射與代價函數設計。如圖3所示，得到圖的頂點映射序列level={v1，v2，v3，v4}后，從level中第一個頂點v開始依次與圖g中的所有頂點比較，找到頂點之間的一一映射。對于含有四個頂點的圖q而言，會產生4！次映射，需要較大的時間與空間開銷。因此，AGED算法通過定義啟發式函數優化映射擴展過程。

c）最優映射選擇。AGED算法根據映射代價函數過濾沒有必要擴展的部分映射，選擇最優部分映射擴展，直到找到一個編輯代價最小的完整映射，即為最優映射。

AGED算法可以精確計算圖之間的結構差異，但是該算法在計算映射擴展的過程中需要很大的時空代價，當圖中頂點數超過12個時，AGED將無法計算圖編輯距離。針對這一問題，本文對映射擴展過程進行改進，降低映射空間、提高計算效率。

2 優化的圖編輯距離算法

不同于現有研究中僅基于頂點單一鄰域信息進行等價劃分，本文算法考慮頂點的全部鄰域信息并對圖中頂點進行劃分，從而生成高精度映射編碼，以提升判斷等價映射的準確度；然后定義映射完整性約束邊界更新等價映射優先級，選擇優先級最高的映射作為等價映射簇的主映射，參與映射編輯代價的比較；最后，提出新的下界計算方法優化映射擴展過程，根據映射編碼定義高效的代價啟發式函數，選擇最優部分映射擴展實現映射的高效過濾，進而快速計算圖編輯距離。

2.1 等價映射與映射完整性

2.1.1 等價映射

以圖1為例，q中的頂點v1和v2組成圖中的對稱結構，可判定為等價頂點，由等價頂點組成的映射視為等價映射，具有相同的編輯代價。為了避免上述等價映射帶來的額外時間與空間代價，本文算法結合頂點鄰域中頂點與邊的信息來代替頂點單一鄰域信息，將圖中所有頂點更精確地劃分到所屬等價類中并計算映射編碼。若映射編碼相同，則判定為等價映射并去重，從而進一步降低搜索空間。

定義7 鄰域信息。對于圖g的頂點集合Vg中的任一頂點u∈Vg和邊集合Eg中的任一條邊e∈Eg，根據式（5）（6）定義其鄰域信息。

定義8 頂點等價。對于頂點u，v∈Vg，當且僅當滿足式（7）（8）時，頂點u與v等價，記做u≡v。

其中：adj（·）表示頂點的鄰接邊集合，Lg（·）表示圖g中頂點或者邊的標簽。

定義9 等價類。根據定義8，將等價頂點劃分為一類，則頂點集合Vg將被劃分為σ|g|個等價類：Vσ1g，Vσ2g，…，Vσ|g|g。對于每個頂點u∈Vσig，定義頂點u的所屬等價類μ（u）=i。

定義10 頂點集編碼。給定頂點集合ver={v1，v2，…，vn}，則ver的頂點集編碼定義為Θ（ver）={μ（v1），μ（v2），…，μ（vn）}。

定義11 映射編碼。給定映射f=∪|f|k=1{vik→ujk}，1≤k≤|f|，則f的映射編碼Θ（f）定義如下：

其中：μ（ujk）表示頂點ujk的等價類編號；|f|表示映射f中的頂點數量。

定義12 等價映射。給定兩個映射f1和f2，如果其映射編碼相同，則f1和f2導出的編輯路徑長度相等，具有相等的編輯代價下界，定義為等價映射。具體表示為：如果Θ（f1）=Θ（f2），則η（f1）=η（f2）。

以圖2中的兩個圖g和q為例，等價映射判定計算過程如下：

a）計算頂點與邊的鄰域信息。

c）計算映射編碼。

根據以上計算步驟可以將頂點集合Vg劃分為Vσ1g，Vσ2g，Vσ3g三個等價類，則μ（u1）=μ（u2）=1，μ（u3）=2，μ（u4）=3。

d）判斷是否為等價映射。

對于映射f1={v1→u1，v2→u2，v3→u3}，映射f2={v1→u2，v2→u1，v3→u3}，其映射編碼Θ（f1）={1，2，3}=Θ（f2），因此f1和f2是等價映射，由f1和f2誘導出的完整映射具有相等的編輯代價。根據這一性質，在映射擴展時只需保留眾多等價映射中的一個即可，由此可節省巨大的時空代價。

2.1.2 映射完整性

在進行映射擴展的過程中，會不可避免地存在編輯代價相等的映射，組成等價映射簇，簇中不同等價映射到達完整映射的距離可能不同。定義映射到達完整映射的程度為映射完整性，距離完整映射越近，映射完整性越高，獲得該映射的編輯代價越快，越有利于在短時間內得到最優映射。通過建立映射完整性邊界，更新映射優先級，選出等價映射簇中的主映射，即優先級最高的映射，參與后續映射擴展，進而優化映射擴展速度。

定義13 映射完整性。對于映射f，將其已映射部分的長度記為|f|，其誘導的完整映射長度記為|f.vertex|，則映射f的完整性f.full定義如下：

本文將每一個映射表示為（f，x，η（f）），其中x表示映射f的完整性，η（f）表示映射f的編輯代價下界值。對于η（f）相等的映射，比較它們的完整性值x，x越大，賦予其對應的映射以較高的優先級，等價映射簇中x最大的映射為主映射。例如在圖3中，假設映射fa和fb組成等價映射簇，則計算得fa.full=0.5lt;fb.full=0.75，因此fb比fa更早到達完整映射，主映射為fb。

2.2 下界計算

以圖g和q為例，本文算法采用初始狀態為空的優先隊列que保存q到g的頂點映射，每次迭代優先選擇編輯代價最小的映射出隊擴展。不同于AGED每次迭代時計算所有映射的編輯代價并擴展，本文算法在擴展過程中剪枝以降低搜索空間開銷。對于映射f，根據式（11）定義有效的啟發式函數計算編輯代價下界，將映射編輯代價η（f）分為已映射部分的實際代價和未映射部分的估計代價兩部分。

其中：gf和gf-分別表示圖g的已映射部分和未映射部分；qf和qf-分別表示圖q的已映射部分和未映射部分。

2.2.1 計算已映射部分f的實際代價ηf（gf，qf）

本文算法依據頂點與邊的鄰域信息劃分等價類，通過計算映射編碼來代替代價計算中的頂點與邊的編輯操作。對于映射fa和fb，首先計算它們已映射部分的映射編碼，記為Θ（fa）和Θ（fb）。由定義12可知，如果Θ（fa）=Θ（fb），則η（fa）=η（fb），根據式（10）計算映射完整性，選出主映射進行后續編輯代價的比較；如果Θ（fa）≠Θ（fb），表明fa和fb會產生不同的編輯代價，則仍然通過比較頂點與邊標簽差異計算編輯ηf（gf，qf），其流程如算法1所示。

算法1 PartialCost（g，q，f）

輸入：圖g和q，映射f。

輸出：已映射部分的編輯代價ηf（gf，qf）。

ηf（gf，qf）=0;

// 計算映射編碼

for vertex u in gf do

compute μ（u）→Θ（gf）;

// 比較頂點

// 修改頂點標簽

for vertex u in gf do

if Lq（v）≠Lg（h（v）） then

ηf（gf，qf）+=1;

// 比較邊

// 刪除邊、修改邊標簽

for edge （u，v） in Vq do

if （h（v），h（u））g or Lq（u，v）≠Lg（h（u），h（v）） then

ηf（gf，qf）+=1;

// 插入邊

for edge （u，v） in Vq do

if （h-（x），h-（y））q then

ηf（gf，qf）+=1;

return ηf（gf，qf），Θ（gf）.

2.2.2 計算未映射部分的估計代價ηf-（gf-，qf-）

本文結合映射編碼和LS下界算法計算未映射部分的編輯代價。首先利用映射編碼計算下界，如果該下界有效，則可在多項式時間內得到編輯代價下界，否則仍然采用LS算法計算下界lbLS。詳細過程如下：

給定映射fa和fb，首先計算未映射部分的映射編碼Θ（f-a）和Θ（f-b）。如果Θ（f-a）=Θ（f-b），則未映射部分的代價相等，選擇ηf（gf，qf）最小的映射優先擴展；如果Θ（f-a）≠Θ（f-b），則進一步量化映射編碼的距離以計算編輯代價下界估值，計算方式如式（12）所示。

其中：κ表示未映射集合中元素標簽相同的數量，Γ（·，·）表示兩集合之間的等價類距離，對于集合X和Y，計算方式如式（13）所示。

如果該算法得到的編輯代價下界相等，則無法高效選擇其中的最優映射，故后續采用LS［29］方法加以計算，并取其中的最大值作為下界，計算方式如式（14）所示。

其中：（·，·）表示兩集合之間的頂點與邊標簽差異，對于集合X和Y，計算方式如式（15）所示。

綜上所述，該部分流程如算法2所示。

算法2 LBCost（g，q，f-）

輸入：圖g和q，映射f-。

輸出：已映射部分的編輯代價ηf-（gf-，qf-）。

ηf-（gf-，qf-）=0;

κ=0，union=0;

// 計算未映射部分的映射編碼Θ（·，·）

for vertex u in gf- do

compute μ（u）→Θ（gf-）;

for vertex v in qf- do

compute μ（v）→Θ（qf-）;

// 計算映射編碼的距離

if Θ（gf-）≠Θ（qf-） then

for i in range（len（qf-）） do

// 元素標簽相同

if Lg（gf-［i］）==Lq（qf-［i］） then

κ=κ+1;

// 頂點編碼相同

if Lg（Θ（gf-）［i］）==Lq（Θ（qf-）［i］） then

union=union+1;

Γ（gf-，qf-）=len（Θ（qf-））+len（Θ（qf-））-2×union;

lb1=2×Γ（gf-，qf-）-κ;

// 計算LS

n1=len（LV（gf-），n2=len（LV（qf-））;

（LV（gf-），LV（qf-））=max（n1，n2）-LV（gf-）∩LV（qf-）;

// 同理計算（LE（gf-），LE（qf-））

lb2=（LE（gf-），LE（qf-））+（LV（gf-），LV（qf-））;

ηf-（gf-，qf-）=max（lb1，lb2）;

return ηf-（gf-，qf-）.

2.2.3 算法有效性分析

下界比較：對于任一映射f，均有η（f）≥lbLS，即本文算法可以得到更緊致的編輯代價下界。

證明 η（f）≥lbLS

lbLS=（LV（gf-），LV（qf-））+（LE（gf-），LE（qf-））=

max{|LV（gf-）|，|LV（qf-）|}-|LV（gf-）∩LV（qf-）+

max{|LE（gf-）|，|LE（qf-）|}-|LE（gf-）∩LE（qf-）|

因為κ=|LV（gf-）∩LV（qf-）|+|LE（gf-）∩LE（qf-）|，則

2×Γ（gf-，qf-）-κ-（LV（gf-），LV（qf-））+（LE（gf-），LE（qf-））=

2×（|Θ（gf-）∪Θ（qf-）|-|Θ（gf-）∩Θ（qf-）|）

2×Γ（gf-，qf-）-κ-（LV（gf-），LV（qf-））+（LE（gf-），LE（qf-））=

2×（|Θ（gf-）∪Θ（qf-）|-|Θ（gf-）∩Θ（qf-）|）+

max{|LV（gf-）|，|LV（qf-）|}+max{|LE（gf-）|，|LE（qf-）|}

因為|Θ（gf-）∪Θ（qf-）|≥|Θ（gf-）∩Θ（qf-）|，

所以|Θ（gf-）∪Θ（qf-）|-|Θ（gf-）∩Θ（qf-）|≥0。

2×Γ（gf-，qf-）-κ≥（LV（gf-），LV（qf-））+（LE（gf-），LE（qf-））

得證η（f）≥lbLS。

2.3 算法流程與算法復雜度分析

2.3.1 算法流程

本文改進的圖編輯距離算法步驟如下：a）統計圖g中頂點與邊的鄰域信息，將頂點集合劃分為若干等價類子集；b）計算圖q中頂點的度序列，從度最小的頂點開始深度優先遍歷得到頂點序列Vq；c）以Vq為基準開始執行Vq到Vg的映射；d）根據算法1計算已映射部分的編輯代價；e）計算已映射部分的映射編碼，判斷是否為等價映射，如果是等價映射，則計算映射完整性，并更新映射優先級，選出主映射進行后續比較；f）根據算法2計算未映射部分的編輯代價下界；g）根據步驟f）得到的映射編輯代價下界比較映射的編輯代價，優先選擇編輯代價最小的映射擴展出隊擴展；h）重復步驟d）～g），選擇最終的最優完整映射代價，即為圖編輯距離。

綜上所述，可得本文算法流程如圖4所示。

2.3.2 算法復雜度分析

1）時間復雜度分析

設圖q和g的頂點規模均為N，已映射部分規模為N1，則未映射部分規模為N-N1。在算法預處理階段，通過比較Vg中的頂點所屬等價類來劃分頂點集合Vg，最壞情況下的時間復雜度為O（N3），該過程僅需在映射擴展前計算一次，所以其復雜度不會對整個算法產生決定性的影響。

首先根據算法1計算已映射部分的編輯代價，時間復雜度為O（N）；然后計算映射擴展，這部分是圖編輯距離計算的核心。其中，映射完整性的優先級計算所需時間復雜度為O（1）。計算映射編碼時，遍歷映射中的頂點集合，取出預處理時期計算好的頂點所屬類的編碼，其并集即為映射編碼的值，該過程時間復雜度為O（N1）。而后通過映射距離和LS計算編輯代價下界，由文獻［30］可知，計算LS的時間復雜度為O（2N），計算映射編碼的距離所需的時間復雜度為O（N-N1）。因此，本文編輯代價下界的時間復雜度為O（N）。

2）空間復雜度分析

根據文獻［24］可知，計算不同頂點數量的兩個圖之間的圖編輯距離可轉換為具有相同頂點數量的圖編輯距離的計算，以下討論中均假設|Vg|=|Vq|=N。本文以搜索樹中的總映射數量，即搜索樹中的總節點數來衡量搜索空間，記為TN。經計算，本文算法空間復雜度為O（NN！/∏σgi=1|Vig|！）。

證明 假設搜索樹中第k層節點數為TNk，則搜索空間TN=∑Nk=0TNk。在第k（1≤k≤N）層中，記圖g中已映射頂點數為k，頂點集合為TNkg={ui1，ui2，…，uik}，頂點集合的等價類劃分情況可用向量x=［x1，…，xσg］表示，其中xi（1≤i≤σg）表示所對應的映射TNkg中屬于Vig的頂點數量，滿足

記Ak為式（16）中所有解的集合，對于其中的一個解x，對應唯一的TNkq，可產生k！/∏σgi=1xi！種映射編碼，每個映射編碼對應一個TNkg到TNkq的唯一映射，則TNk=∑x∈Axk！/∏σgi=1xi！。

當k=N時，∑σgi=1|Vig|=|Vg|=N，式（16）具有唯一解x=［|V1g|，|V2g|，…，|Vσgg|］，則

根據搜索樹的性質，搜索樹中第0層只有一個根節點，且節點數逐層遞增，即TN0=1TNi≤TNN，i∈［1，N］，則通過不等式縮放可得TN=1+∑Nk=1TNk≤NN！∏σgi=1|Vig|！+1，因此3 實驗分析

3.1 實驗環境與數據集

本文實驗運行環境為：CPU是Intel Xeon @2.40 GHz，8核，內存為8 GB，操作系統為Ubuntu，所用軟件為Visual Studio Code，具體信息如表2所示。所用數據集包括AIDS-1、AIDS-2、GREC三個真實數據集和一個人工數據集SYN，各數據集詳細參數信息如表3所示。其中，AIDS-1是來自NCI/HIN發展治療項目的病毒篩選數據集，用于發現艾滋病病毒，該數據集由42 687個化合物組成；AIDS-2去除了AIDS-1數據集中頂點數量大于35的數據圖，選擇其中10 000個圖組成AIDS-2。GREC包含了來自建筑等其他領域的1 000張圖片。GraphGen是一個合成圖生成器，本文使用該合成圖生成器生成含有10 000個數據圖的人工數據集SYN。

3.2 對比算法與評估指標

3.2.1 圖編輯距離算法

為驗證本文改進的圖編輯距離算法的有效性，選用三種算法進行對比實驗：本文改進的圖編輯距離算法（EC-GED）、AGED［25］以及AStar-BMa［20］算法。本文采用文獻［17］中的方法將每個數據集中頂點數量在［i-1，i+1］內的圖分為一組，其中i={6，9，12，15，18，21}，則共分為六組進行實驗：［5，7］，［8，10］，［11，13］，［14，16］，［17，19］，［20，22］。實驗時，每組查詢選取30對數據圖進行圖編輯距離計算，為避免偶然因素帶來的實驗誤差，對每組查詢計算6×30次，并分別從搜索空間和算法平均運行時間兩方面對圖編輯距離算法進行性能分析：a）平均運行時間t，圖編輯距離算法中從開始映射到得到最優映射的時間；b）搜索空間n，圖編輯距離計算中映射擴展的總次數。映射擴展計算次數越少，表明計算所得下界越接近真實值，剪枝效果越好，搜索空間越小。

3.2.2 圖相似性搜索算法

為測試不同的圖編輯距離算法下圖相似性搜索的性能，本文將以上圖編輯距離算法應用于基于過濾—驗證框架的圖相似性搜索中：給定圖數據集G={g1，g2，…，g|G|}，查詢圖q和閾值τ，則結果集R={gi|GED（gi，q）≤τ，gi∈G}。由于AGED無法處理超過12個頂點的數據圖，本部分實驗只考慮EC-GED和AStar-BMa算法，過濾階段統一采用標簽差異［30］過濾，驗證階段分別采用EC-GED和AStar-BMa算法精確計算圖編輯距離，隨機選取100個圖組成查詢圖集合Q，并分析算法性能。

3.3 實驗結果與分析

3.3.1 圖編輯距離算法結果分析

a）平均運行時間t。

本實驗在AIDS-2、GREC和SYN三個數據集上測試圖編輯距離算法的運行時間，表4給出了AGED、AStar-BMa、EC-GED三種算法在不同頂點規模|V|上的平均運行時間，頂點數量|V|的取值為［5，22］。由表4可以看出，當圖中頂點數量超過12時，AGED算法提示內存溢出，無法繼續計算；AStar-BMa和EC-GED可以處理表4中列出的所有頂點規模的數據圖，其中，AStar-BMa由于高達O（n4）的時間復雜度，導致其運行時間較長。相較于AStar-BMa，EC-GED雖然需要在前期計算頂點鄰域信息來劃分頂點集合，但是其復雜度不會對整個算法產生決定性的影響，并且可以避免后期大量冗余映射的計算，減少算法運行時間，因此具有更優的效果。而且EC-GED算法不論在稀疏圖數據集AIDS-2、GREC還是在稠密圖數據集SYN上，均能取得最優的運行時間，驗證了EC-GED算法在不同密度數據圖上均具有較好的計算效果，進而可以提升圖相似性搜索的效率。

為探索本文提出的去除冗余映射以及下界計算方法對圖編輯距離算法中搜索空間的影響，圖5給出了AStar-BMa和EC-GED算法在不同數據集上的搜索空間占用情況，其中橫坐標表示頂點規模中的參數i，縱坐標表示不同頂點規模下產生的映射數量n，用來衡量搜索空間。由圖5可知，在AIDS-2、GREC、SYN數據集上，EC-GED算法產生的映射總數始終低于AStar-BMa，即EC-GED具有更小的搜索空間。其原因在于：（a）EC-GED給出了更嚴格的等價映射定義，能夠更加有效地減少等價映射的空間占用；（b）結合下界計算中提出的高效啟發式函數，實現了搜索樹的高效剪枝。對比AStar-BMa算法，EC-GED算法的搜索空間平均減少了14% ～49%。

c）映射完整性約束。

為驗證映射完整性約束對圖編輯距離計算的性能提升效果，圖6比較了加入映射完整性約束（EC-GED）和未加入映射完整性約束（FEC-GED）時兩種算法在不同數據集上的平均運行時間。在不同數據集上，對比FEC-GED算法，EC-GED算法的運行時間更短，速度提升區間為4%～29%，驗證了映射完整性約束的有效性。其原因在于EC-GED算法在每次迭代得到等價映射時，只需選出等價映射簇中的主映射參與擴展，可以避免計算所有等價映射的擴展過程，實現了高效剪枝，進一步提高了圖編輯距離的計算效率。

以上對比實驗結果表明，通過定義映射編碼和映射完整性約束，EC-GED算法對映射擴展過程作出優化，進一步提高了圖編輯距離的計算效率，并且該算法在稀疏圖和稠密圖上均適用，能夠應用于大規模圖數據庫相似性搜索。

3.3.2 圖相似性搜索結果分析

本部分實驗將EC-GED和AStar-BMa算法應用于圖相似性搜索，分別在真實數據集AIDS-1和人工數據集SYN上驗證實驗效果。實驗首先根據標簽差異過濾得到候選集C={c1，c2，…}，然后分別采用AStar-BMa和EC-GED算法計算查詢圖q與候選圖ci∈C的圖編輯距離GED（ci，q），如果GED（ci，q）≤τ，則ci為最終滿足條件的圖。由于使用的過濾策略相同，所以同一數據集得到的候選集大小相等，在這一前提下，圖相似性搜索的性能主要取決于GED的計算開銷。本部分實驗中，設置編輯距離閾值τ={1，3，5，7，9}，且在相同的實驗條件下每次查詢執行300次計算，取平均值作為算法的平均運行時間來驗證EC-GED算法在圖相似性搜索中的有效性。

在AIDS-1和SYN數據集上，采用不同的圖編輯距離算法EC-GED和AStar-BMa，對比相應的圖相似性搜索算法運行時間隨閾值的變化情況，如圖7所示。由3.3.1節中的實驗結果可知，EC-GED算法由于去除了大量冗余映射，在不同數據集上均能取得最優的運行時間，所以推測采用EC-GED的圖相似性搜索算法也可取得最優的性能。如圖7所示，隨著編輯距離閾值的增大，圖相似性搜索算法的運行時間均逐漸增大，而采用EC-GED算法的圖相似性搜索時間始終低于AStar-BMa。即使在大規模數據集上，EC-GED仍然具有較優的運行時間，且在閾值較小時，兩者運行時間差距較大，表明EC-GED算法在圖相似性搜索中的適用性和有效性，尤其對于閾值較小的圖相似性搜索問題，EC-GED表現出更好的性能。

4 結束語

本文針對傳統的圖編輯距離計算中存在的映射擴展次數較多、映射空間較大、等價映射定義不嚴格、下界計算復雜度高等問題，提出一種優化的圖編輯距離算法，通過頂點與邊的等價類劃分，給出更加準確的等價映射的定義；引入映射完整性約束，進一步優化映射擴展速度；結合映射編碼定義有效的啟發式函數計算下界，解決了下界計算復雜度較高的問題，進而有效提升了圖編輯距離算法的計算效率，減少了不必要的搜索空間開銷。在不同數據集上的實驗結果驗證了本文算法的有效性，并且可以提高大規模圖相似性搜索算法的性能。在未來研究中，應進一步考慮造成冗余映射的更多因素，以及如何將該方法應用于非統一編輯代價的計算情況。

參考文獻：

［1］Cao Longbing. Data science： a comprehensive overview ［J］. ACM Computing Surveys，2017，50（3）： article No. 43.

［2］Angles R，Gutierrez C. An introduction to graph data management ［M］// Graph Data Management. Data-Centric Systems and Applications. Cham： Springer，2018： 1-32.

［3］Patil N S，Kiran P，Kiran N P，et al. A survey on graph database mana-gement techniques for huge unstructured data ［J］. International Journal of Electrical and Computer Engineering，2018，8（2）： 1140-1149.

［4］Van Duong T T，Dolgorsuren B，Lee Y K，et al. Subgraph matching on multiple graph streams ［C］// Proc of IEEE International Conference on Big Data and Smart Computing. Piscataway，NJ： IEEE Press，2022： 104-107.

［5］Sun Shixuan，Luo Qiong. Subgraph matching with effective matching order and indexing ［J］. IEEE Trans on Knowledge and Data Engineering，2020，34（1）： 491-505.

［6］Sun Shixuan，Luo Qiong. In-memory subgraph matching： an in-depth study ［C］// Proc of ACM SIGMOD International Conference on Mana-gement of Data. New York： ACM Press，2020： 1083-1098.

［7］Shimomura L C，Oyamada R S，Vieira M R，et al. A survey on graph-based methods for similarity searches in metric spaces ［J］. Information Systems，2021，95（1）： 101507.

［8］Chen Xiaoyang，Huo Hongwei，Huan Jun，et al. MSQ-Index： a succinct index for fast graph similarity search ［J］. IEEE Trans on Knowledge and Data Engineering，2019，33（6）： 2654-2668.

［9］Poulin V，Theberge F. Ensemble clustering for graphs： comparisons and applications［J］. Applied Network Science，2019，4（1）：1-13.

［10］Nguyen T，Nguyen G T T，Nguyen T，et al. Graph convolutional networks for drug response prediction ［J］. IEEE/ACM Trans on Computational Biology and Bioinformatics，2022，19（1）：146-154.

［11］Conte D，Foggia P，Sansone C，et al. Thirty years of graph matching in pattern recognition ［J］. International Journal of Pattern Recognition and Artificial Intelligence，2004，18（3）： 265-298.

［12］Yang Shengqi，Han Fangqiu，Wu Yinghui，et al. Fast top-k search in knowledge graphs ［C］// Proc of the 32nd International Conference on Data Engineering. Piscataway，NJ： IEEE Press，2016： 990-1001.

［13］Kyu K M，Oo A N. Graph-based indexing method for searching in RDF data ［C］// Proc of International Conference on Advanced Information Technologies. Piscataway，NJ： IEEE Press，2019： 96-101.

［14］Kanehisa M，Goto S. KEGG： Kyoto encyclopedia of genes and genomes ［J］. Nucleic Acids Research，2000，28（1）： 27-30.

［15］Zhu Yuanyuan，Qin Lu，Yu J X，et al. Answering top-k graph similarity queries in graph databases ［J］. IEEE Trans on Knowledge and Data Engineering，2019，32（8）： 1459-1474.

［16］Cheng J，Ke Yiping，Fu A W C，et al. Fast graph query processing with a low-cost index ［J］. The VLDB Journal，2011，20（4）： 521-539.

［17］Gouda K，Hassaan M. CSI_GED： an efficient approach for graph edit similarity computation ［C］// Proc of the 32nd International Confe-rence on Data Engineering. Piscataway，NJ： IEEE Press，2016： 265-276.

［18］Zeng Zhiping，Tung A K H，Wang Jianyong，et al. Comparing stars： on approximating graph edit distance ［J］. Proceedings of the VLDB Endowment，2009，2（1）： 25-36.

［19］Chang Lijun，Feng Xing，Lin Xuemin，et al. Speeding up GED verification for graph similarity search ［C］// Proc of the 36th International Conference on Data Engineering. Piscataway，NJ： IEEE Press，2020： 793-804.

［20］Chang Lijun，Feng Xing，Yao Kai，et al. Accelerating graph similarity search via efficient GED computation ［J］. IEEE Trans on Know-ledge and Data Engineering，2022，DOI： 10.1109/TKDE.2022.3153523.

［21］Blumenthal D B，Gamper J. On the exact computation of the graph edit distance ［J］. Pattern Recognition Letters，2020，134（1）： 46-57.

［22］Fankhauser S，Riesen K，Bunke H. Speeding up graph edit distance computation through fast bipartite matching ［C］// Proc of the 8th International Workshop on Graph-based Representations in Pattern Reco-gnition. Berlin： Springer，2011： 102-111.

［23］Dabah A，Chegrane I，Yahiaoui S. Efficient approximate approach for graph edit distance problem ［J］. Pattern Recognition Letters，2021，151（11）： 310-316.

［24］陳梓揚. 圖編輯距離的優化方法研究 ［D］. 上海： 東華大學，2021. （Chen Ziyang. Research on optimization for graph edit distance ［D］. Shanghai： Donghua University，2021.）

［25］Hart P E，Nilsson N J，Raphael B. A formal basis for the heuristic determination of minimum cost paths ［J］. IEEE Trans on Systems Science and Cybernetics，1968，4（2）： 100-107.

［26］Riesen K，Fankhauser S，Bunke H. Speeding up graph edit distance computation with a bipartite heuristic ［C］// Proc of the 5th International Workshop on Mining and Learning with Graphs. 2007： 21-24.

［27］Abu-Aisheh Z，Raveaux R，Ramel J Y，et al. An exact graph edit distance algorithm for solving pattern recognition problems ［C］// Proc of the 4th International Conference on Pattern Recognition Applications and Methods. Setubal，Portugal： SciTePress，2015： 271-278.

［28］Chang Lijun，Feng Xing，Lin Xuemin，et al. Efficient graph edit distance computation and verification via anchor-aware lower bound estimation ［EB/OL］. （2017-10-01）. https：//arxiv.org/pdf/1709.06810.pdf.

［29］陳曉陽. 大規模圖數據庫的相似性搜索算法研究 ［D］. 西安： 西安電子科技大學，2019. （Chen Xiaoyang. Research on similarity search in large-scale graph database ［D］. Xi’an： Xidian University，2019.）

［30］Zhao Xiang，Xiao Chuan，Lin Xuemin，et al. Efficient graph similarity joins with edit distance constraints ［C］// Proc of the 28th International Conference on Data Engineering. Piscataway，NJ： IEEE Press，2012： 834-845.

收稿日期：2022-06-27；修回日期：2022-08-16 基金項目：江蘇省高校自然科學研究項目（19KJA550002）；江蘇省高校優勢學科建設工程資助項目

作者簡介：邱珍（1997-），女，江蘇徐州人，碩士研究生，主要研究方向為數據檢索、網絡空間安全；鄭朝暉（1968-），男（通信作者），江西南昌人，博導，碩士，主要研究方向為網絡空間安全（zhengzh@suda.edu.cn）.