Abstract

子圖查詢處理（也稱為子圖搜索）和子圖匹配是許多應(yīng)用領(lǐng)域中的基本圖問題。為解決這些問題制定實(shí)際的解決辦法，人們已經(jīng)作出了許多努力。盡管付出了這些努力，但現(xiàn)有的算法在處理大型圖和/或許多圖時顯示出了有限的運(yùn)行時間和可伸縮性。在本文中，我們提出了一個新的子圖搜索算法使用等價的頂點(diǎn)為了減少搜索空間：
(1)靜態(tài)等價的頂點(diǎn)的查詢圖，導(dǎo)致一個有效的匹配順序的頂點(diǎn)；(2)動態(tài)等價的候選頂點(diǎn)的數(shù)據(jù)圖，使我們能夠捕獲和刪除冗余的搜索空間。
這些子圖搜索技術(shù)也導(dǎo)致了一種改進(jìn)的子圖匹配算法。實(shí)驗(yàn)表明，我們的方法在查詢處理時間上優(yōu)于最先進(jìn)的子圖搜索和子圖匹配算法多達(dá)幾個數(shù)量級。

1 Introduction

在過去的幾十年里，由于公開的各種圖數(shù)據(jù)，人們?yōu)殚_發(fā)NP-hard圖問題的實(shí)際解決方案做出了大量的努力[36]。一方面，研究人員已經(jīng)被激勵去開發(fā)可伸縮和高效的算法來分析大型圖，如社交網(wǎng)絡(luò)和資源描述框架（RDF）數(shù)據(jù)。大圖最著名的問題之一是子圖匹配。給定一個數(shù)據(jù)圖G和查詢圖q，子圖匹配問題是在G中找到所有匹配的q.另一方面，較小的圖數(shù)據(jù)包括蛋白質(zhì)相互作用（PPI）網(wǎng)絡(luò)和化合物鼓勵研究人員獲得快速和可擴(kuò)展的算法來處理大量的圖。子圖查詢處理（也稱為子圖搜索）是這些圖的集合中的一個眾所周知的問題。給定一組數(shù)據(jù)圖和一個查詢圖，子圖搜索是檢索D中包含q作為子圖的所有數(shù)據(jù)圖。
子圖匹配和子圖搜索都有多種現(xiàn)實(shí)世界的應(yīng)用：社會網(wǎng)絡(luò)分析[10,38]、RDF查詢處理[20,21]、PPI網(wǎng)絡(luò)分析[6,31]和化學(xué)化合物搜索[46]。然而，這些問題是np困難的，因?yàn)樗鼈儼▽ふ易訄D同構(gòu)，這是一個np困難的問題。也就是說，解決這些問題是應(yīng)用程序的瓶頸。
盡管這兩個問題彼此密切相關(guān)，但對每個問題的研究直到最近都是單獨(dú)進(jìn)行的?，F(xiàn)有的子圖搜索的工作[4,9,12,22,46,50,51]主要采用索引過濾驗(yàn)證策略： (1)給定一組數(shù)據(jù)圖，數(shù)據(jù)結(jié)構(gòu)由子結(jié)構(gòu)（即特征）的數(shù)據(jù)圖索引階段，(2)給定一個查詢圖q，數(shù)據(jù)圖的特征被過濾在過濾階段，和(3)子圖在驗(yàn)證階段對每個剩余的候選圖進(jìn)行同構(gòu)測試。同時，最近對子圖匹配[3,13,14,40]的研究提出了基于預(yù)處理枚舉框架的[3,13,14,40]算法：在查詢圖和數(shù)據(jù)圖上構(gòu)建輔助數(shù)據(jù)結(jié)構(gòu)，并利用數(shù)據(jù)結(jié)構(gòu)找到查詢圖的所有匹配情況。這些算法極大地提高了查詢處理的性能。研究人員最近利用現(xiàn)有的子圖匹配算法有效地解決了子圖搜索問題[39]。然而，它在處理大型查詢圖或許多數(shù)據(jù)圖時顯示出了有限的響應(yīng)時間和可伸縮性。
本文提出了一種新的基于靜態(tài)等價和動態(tài)等價的子圖搜索算法來解決其中的局限性。首先，我們將查詢頂點(diǎn)的鄰域等價性應(yīng)用于回溯的匹配順序，從而導(dǎo)致驗(yàn)證階段的搜索空間更小。其次，我們基于候選數(shù)據(jù)頂點(diǎn)的鄰域等價性，捕獲搜索空間的子樹的運(yùn)行時等價性，并剔除搜索空間的冗余性（即等效子樹）。此外，我們提出了一種稱為鄰居安全的高效過濾方法，使我們能夠在查詢圖和數(shù)據(jù)圖上構(gòu)建一個緊湊的輔助數(shù)據(jù)結(jié)構(gòu)，以獲得盡可能少的候選數(shù)據(jù)。我們在幾個著名的真實(shí)數(shù)據(jù)集和合成數(shù)據(jù)集上進(jìn)行了廣泛的實(shí)驗(yàn)，以比較我們的方法與現(xiàn)有的算法。此外，我們的子圖搜索技術(shù)反過來導(dǎo)致了一種改進(jìn)的子圖匹配算法VEQM。實(shí)驗(yàn)結(jié)果表明，該方法在查詢處理時間方面比現(xiàn)有的子圖搜索和子圖匹配算法的性能要好幾個數(shù)量級。我們的算法、數(shù)據(jù)集和查詢集的可執(zhí)行文件都是公開可用的。

本文的其余部分組織如下。第2節(jié)提供了定義、問題陳述和相關(guān)的工作。第3節(jié)概述了我們的方法。第4節(jié)介紹了我們的過濾技術(shù)。第5節(jié)描述了我們基于靜態(tài)等價的查詢頂點(diǎn)匹配順序。6提出了一種利用動態(tài)等價性的方法來檢測和去除部分搜索空間的新技術(shù)。第7節(jié)與以前的工作進(jìn)行了廣泛的實(shí)驗(yàn)比較。8總結(jié)了論文。

2 Preliminaries

在本文中，我們主要關(guān)注帶有標(biāo)記頂點(diǎn)的無向連通圖。我們的技術(shù)可以很容易地擴(kuò)展到帶有標(biāo)記邊的有向圖或不連通圖。圖g =（V (g)，E (g)，Lg）由集合V (g)頂點(diǎn)、集合E (g)邊和標(biāo)記函數(shù)Lg： V (g)→∑組成，它為每個頂點(diǎn)分配一個標(biāo)簽，其中∑是一組標(biāo)簽。對于V (g)的一個子集S，誘導(dǎo)子圖g[S]表示g的子圖，g的頂點(diǎn)集為S，其邊集包含E (g)中的所有邊，它們在S中都有兩個端點(diǎn)。
給定一個圖q =（V (q)、E (q)、Lq）和圖G =（V (G)、E (G)、LG），q在G中的嵌入是一個映射M：V(q)→V(G)，這樣
(1)M(即M (u)≠M(fèi)（u’），(2)對于每個V（q）中的u，Lq(u)=LG(M(u))，以及(3)（M(u),M(u’)）∈E(G））對于每個（u,u’）∈E (G)。
我們稱q是與G同構(gòu)的子圖，用q?G表示，如果q在G中存在一個嵌入。一個滿足(2)和(3)的映射被稱為同態(tài)，即，它可能不是內(nèi)射的。q的誘導(dǎo)子圖在G中的嵌入稱為部分嵌入。為了便于可追溯性，我們按照在回溯過程中添加到M的順序枚舉部分嵌入M中的映射對。
我們將使用有向無環(huán)圖（DAG）作為工具來構(gòu)建q和g的輔助數(shù)據(jù)結(jié)構(gòu)。給定DAG g，如果頂點(diǎn)沒有入邊，則是根，如果頂點(diǎn)沒有出邊，頂點(diǎn)是葉子。如果只有一個根，那么一個DAG g就是一個有根的DAG。設(shè)Child (u)表示V (g)中的一組頂點(diǎn)，它們有來自u的輸入邊。根于u的g的子dag，用gu表示，是g的誘導(dǎo)子圖，其頂點(diǎn)是u和u的所有后代。

2.1 Problem statement

子圖搜索。給定一個查詢圖q和一組數(shù)據(jù)圖D，子圖搜索問題是找到D中包含q作為子圖的所有數(shù)據(jù)圖。即，子圖搜索是計算答案集Aq = {G∈D | q?G}。
子圖的匹配。給定一個查詢圖q和一個數(shù)據(jù)圖G，子圖匹配問題是找到q在G中的所有嵌入。
上述問題與[39]之間密切相關(guān)。給定一個查詢圖q和一組D的數(shù)據(jù)圖，我們可以解決子圖搜索問題通過一個修改子圖匹配算法，也就是說，對于每個數(shù)據(jù)圖G∈D報告G和終止一旦發(fā)現(xiàn)第一個嵌入qG.自子圖同構(gòu)（即，“G包含一個子圖同構(gòu)q？”）是np完備的[11]，這兩個問題都是np困難的。

2.2 Related work

子圖搜索。許多早期的子圖搜索算法都采用了索引-過濾-驗(yàn)證策略。根據(jù)算法提取特征[18,39]的方法，這些算法可以分為以下兩組。
首先，在特征挖掘方法中，提取了數(shù)據(jù)圖中經(jīng)常出現(xiàn)的常見特征。gIndex [46]從數(shù)據(jù)圖中提取頻繁的子圖，并從這些特征中構(gòu)建一個前綴樹。Tree+[50]將頻繁的樹挖掘到預(yù)定的大小，并將它們存儲為哈希表。這些方法在索引構(gòu)建[15,18]中是昂貴的。
其次，達(dá)到用戶定義大小的所有特性都在特性枚舉方法中進(jìn)行枚舉和索引。GCode [51]枚舉所有路徑，并通過使用這些路徑在數(shù)據(jù)圖中生成頂點(diǎn)簽名。CT索引[22]枚舉樹和循環(huán)特征，而SING [9]、GraphGrepSX [4]和Grapes [12]列出了所有有界長度的路徑。由于數(shù)據(jù)圖的所有特征都是枚舉的，因此這些方法中的索引構(gòu)造需要大量的內(nèi)存，從而導(dǎo)致索引很大。
上述兩種方法的目的是通過使用它們的索引來過濾掉盡可能多的錯誤答案，以避免探索在驗(yàn)證中沒有發(fā)現(xiàn)嵌入的錯誤圖的整個搜索空間；然而，這些方法的索引構(gòu)建通常需要大量的時間和空間。
研究人員最近使用了一種不構(gòu)建索引的過濾-驗(yàn)證策略。CFQL [39]利用現(xiàn)有的子圖匹配算法來加快子圖的搜索速度。具體來說，分別采用CFL-Match的預(yù)處理技術(shù)和GraphQL的搜索方法進(jìn)行過濾和驗(yàn)證。在沒有構(gòu)建索引的情況下，CFQL優(yōu)于索引濾波驗(yàn)證算法，得益于現(xiàn)有子圖匹配算法的濾波能力和高效的驗(yàn)證技術(shù)。
子圖匹配?；跒鯛柭幕厮輀43]，提出了許多子圖匹配算法[3,8,13,14,16,23,37,40,48,49]。這種方法通常工作如下： (1)對于每個查詢頂點(diǎn)u，一個候選集C (u)通過過濾過程，其中C (u)是一組候選數(shù)據(jù)頂點(diǎn)，你可以映射到，和(2)匹配的查詢頂點(diǎn)確定，和每個查詢頂點(diǎn)迭代映射到一個候選頂點(diǎn)通過匹配的順序。雖然這些算法是基于這個通用框架設(shè)計的，但它們在性能上差異很大，這依賴于過濾方法、匹配順序和在回溯過程中刪除搜索空間的技術(shù)。
早期的子圖匹配算法如Ullmann [43]、VF2[8]、QuickSI[37]和SPath [49]通過使用考慮頂點(diǎn)鄰域的局部過濾器獲得候選集；然而，最近的算法如GraphQL [16]、Turboiso [14]、CFL-Match [3]，CECI [2]和DAF [13]在查詢圖和數(shù)據(jù)圖上構(gòu)建輔助數(shù)據(jù)結(jié)構(gòu)，以獲得小的候選集。此外，Turboiso、CFL-Match和DAF通過利用輔助數(shù)據(jù)結(jié)構(gòu)，盡可能精確地估計搜索成本，從而產(chǎn)生有效的匹配順序。一些算法消除了源于回溯性質(zhì)的冗余計算（例如，[13]中的失敗集）。
[26,27,40]全面地覆蓋和研究了最近從幾個不同的社區(qū)發(fā)展起來的各種子圖匹配算法。在人工智能中，格拉斯哥子圖求解器（格拉斯哥）[28]是專門針對子圖同構(gòu)進(jìn)行優(yōu)化的，但它也提供了子圖匹配。與其他現(xiàn)有的方法不同，格拉斯哥將子圖同構(gòu)作為一個約束規(guī)劃問題。
在生物信息學(xué)社區(qū)，RI [5]提出了一種基于全局匹配順序的回溯方法。
特別是，Sun和Luo的深入研究[40]是一項(xiàng)開創(chuàng)性的工作，它不僅為有效的子圖匹配算法提出了設(shè)計指導(dǎo)方針，而且還開發(fā)了最快的子圖匹配算法（結(jié)合了現(xiàn)有算法的不同技術(shù)）。因此，我們認(rèn)為該算法（GQLfs和RIfs）是最先進(jìn)的方法，在第七節(jié)我們的方法與之進(jìn)行了比較。
有些方法側(cè)重于采用批處理查詢處理的子圖匹配的綜合技術(shù)。MQOsubiso [34]計算查詢執(zhí)行順序，以便可以利用緩存的中間結(jié)果。給定一個查詢工作負(fù)載，WaSQ [25]預(yù)先緩存該工作負(fù)載的每個查詢的嵌入。接下來，給定一個新的查詢q，它重用查詢工作負(fù)載和緩存的嵌入來有效地找到q的嵌入（工作負(fù)載感知的子圖匹配）。
誘導(dǎo)子圖匹配。子圖同構(gòu)在其他領(lǐng)域中有兩種不同的定義，如人工智能和生物信息學(xué)：非誘導(dǎo)子圖同構(gòu)和誘導(dǎo)子圖同構(gòu)。非誘導(dǎo)子圖同構(gòu)是指在第二節(jié)中定義的嵌入。2，這是在數(shù)據(jù)管理界中常用的子圖同構(gòu)的概念。誘導(dǎo)子圖同構(gòu)還需要非鄰接條件（這意味著應(yīng)該存在一條q的邊，它對應(yīng)于G的匹配頂點(diǎn)之間的每條邊）。在這兩種定義之間，VF3 [7]、Glasgow和RI主要處理誘導(dǎo)子圖同構(gòu)（或誘導(dǎo)子圖匹配）。相比之下，我們的研究主要集中在非誘導(dǎo)子圖匹配上。
多路連接。由于一個多路連接可以用一個圖來表示，所以許多基于連接的算法都枚舉了所有的同態(tài)（在Sect中定義）。2)在一個數(shù)據(jù)圖中的一個查詢圖。雖然嵌入必須是內(nèi)射的，但同態(tài)不需要是內(nèi)射的，也就是說，同態(tài)允許結(jié)果中包含重復(fù)的數(shù)據(jù)頂點(diǎn)，而嵌入不包含。
基于最壞情況最優(yōu)連接（WCOJ）設(shè)計了幾種最近的圖同態(tài)算法，即一個運(yùn)行時間受查詢圖輸出數(shù)量限制的連接算法的集合。[1]和圖形[17]采用最壞情況最優(yōu)連接來生成專門為小查詢的連接計劃。RapidMatch [42]最近提出了一種基于連接的圖同態(tài)引擎，它可以評估小型和大型查詢。研究人員還開發(fā)了通過選擇查詢頂點(diǎn)順序來優(yōu)化最壞情況最優(yōu)計劃的方法。具體地說，[29]提出了一個動態(tài)規(guī)劃優(yōu)化器，它生成計劃（通過執(zhí)行兩個較小的子查詢的二進(jìn)制連接或擴(kuò)展一個查詢頂點(diǎn)擴(kuò)展一個交點(diǎn)的子查詢）和一種選擇最壞情況下最優(yōu)子計劃的查詢頂點(diǎn)順序的自適應(yīng)技術(shù)。
總結(jié)和壓縮。圖摘要是將圖轉(zhuǎn)換為更緊湊的表示，同時保留它們的結(jié)構(gòu)屬性或查詢的輸出。對于子圖匹配，SGMatch [35]將查詢圖和數(shù)據(jù)圖分解為一組圖集，并按照其圖集的匹配順序?qū)⒉樵儓D的圖與數(shù)據(jù)圖的相應(yīng)圖進(jìn)行匹配。
一些壓縮范例，如輸入壓縮和輸出壓縮，旨在減輕子圖匹配中的繁重計算。作為一種輸入壓縮技術(shù)，BoostIso [33,45]通過在預(yù)處理中合并對稱頂點(diǎn)（在將查詢圖作為輸入之前）來壓縮數(shù)據(jù)圖。對于輸出壓縮，基于頂點(diǎn)覆蓋的壓縮（VCBC）[32]將輸出嵌入到大小大于嵌入的壓縮編碼中，基于晶體的計算框架（CBF）[32]實(shí)現(xiàn)的不是嵌入，而是它們的代碼，以降低子圖匹配的總體成本。
與上述方法不同，我們的方法采用查詢頂點(diǎn)的等價鄰域來決定匹配順序，并在輔助數(shù)據(jù)結(jié)構(gòu)中基于等價鄰域找到等價子樹。

3 Overview of our approach

我們首先概述了我們的子圖匹配算法，然后對子圖搜索進(jìn)行了修改。
子圖匹配。給定一個查詢圖q和一個數(shù)據(jù)圖G，我們的子圖匹配算法包括以下三個步驟。
(i)構(gòu)建查詢DAG。
我們構(gòu)建了一個查詢DAG qD，這是一個由q通過為q中的邊分配方向而構(gòu)建的DAG（例如，圖2中它的反向qD?1是查詢DAG）。選擇標(biāo)簽不頻繁且程度大的頂點(diǎn)作為量子D的根，從r進(jìn)行BFS遍歷，構(gòu)建量子D[13]。我們還在q中的所有1次頂點(diǎn)中找到了鄰域等價類（NEC），并將同一NEC中的頂點(diǎn)合并為qD中的單個頂點(diǎn)，其中NEC是一組具有相同標(biāo)簽和的查詢頂點(diǎn)同樣的鄰居[14]。在圖2的查詢DAG qD中，qD中頂點(diǎn)u5的鄰域等價類（即NEC（u5））對應(yīng)于q中的一個單例集{u5}。

(ii)建設(shè)候選空間。
我們在q和G上建立了一個輔助數(shù)據(jù)結(jié)構(gòu)候選空間（CS）。q和G上的A CS由每個頂點(diǎn)u∈V (q)的候選集C (u)和候選頂點(diǎn)之間的邊組成：
(a)對于每個u∈V (q)，都有一個候選集C (u)，它是G中u可以映射到的頂點(diǎn)集。(映射的確切條件在第四章節(jié)中描述。)
(b)當(dāng)且僅當(dāng)（u，u’）∈E（q）和（v，v’）∈E (G)時，v∈C (u)和v’∈C（u’）之間有一條邊。

圖3a為圖2中q上的CS和圖1中的G1。三個候選的v1、v2、v9在C（u1）中，在v2∈C（u1）和v5∈C（u2）之間有一條邊。CS是[13]中使用的一種輔助數(shù)據(jù)結(jié)構(gòu)，但我們的CS構(gòu)造與[13]不同。我們通過使用擴(kuò)展的dag圖DP（動態(tài)規(guī)劃）和一個附加的過濾函數(shù)，利用一個稱為鄰居安全的概念。 4).如果有任何u∈V (q)使得C (u) =?，我們不返回任何結(jié)果（因?yàn)槿绻腥魏慰盏暮蜻x集，就不能在G中嵌入q）；否則繼續(xù)下一步。
(iii)匹配。
我們通過新的匹配順序匹配查詢頂點(diǎn)u∈V (q)與CS的C (u)中的候選頂點(diǎn)，該匹配順序是基于u的未映射可擴(kuò)展候選頂點(diǎn)的數(shù)量和NEC (u)的大小(第五節(jié)).此外，我們提出了一種新的技術(shù)，利用動態(tài)等價的子樹來去除搜索空間的重復(fù)子樹。 6).我們還在我們的算法中應(yīng)用了失敗的[13]集。
子圖搜索。
在子圖搜索的一般框架中，根據(jù)給定的數(shù)據(jù)圖集建立索引I。給定一個查詢圖q、一組數(shù)據(jù)圖的D和索引I，我們可以執(zhí)行以下步驟，并輸出一組答案圖的Aq。
（i）使用索引進(jìn)行過濾。對于I中不包含q的每個特征，帶有該特征的數(shù)據(jù)圖將被過濾掉。D中剩余的數(shù)據(jù)圖集用Bq表示。接下來，我們繼續(xù)對q和每個數(shù)據(jù)圖G∈Bq進(jìn)行以下步驟。
（ii）構(gòu)建一個查詢DAG。以與子圖匹配相同的方式從q構(gòu)建一個查詢DAG qD。
（iii）建設(shè)候選空間。對于查詢的DAG qD和數(shù)據(jù)圖G，我們采用與子圖匹配相同的方法構(gòu)建CS。
（iv）搜索。與上面的匹配不同，我們在G中找到最多一個q的嵌入。如果在G中找到一個q的嵌入，這一步返回G作為答案；或者沒有。
我們在上面將我們的子圖搜索算法描述為一個更一般的子圖搜索框架，因?yàn)槲覀兊募夹g(shù)可以用作索引-過濾-驗(yàn)證框架的過濾和搜索階段，其中任何索引都可以應(yīng)用于索引和過濾階段?；谖覀兊膶?shí)證研究，使用索引建立一個現(xiàn)有的索引和過濾會產(chǎn)生相當(dāng)大的開銷，但對大多數(shù)查詢沒有獲得更高的過濾能力，這已經(jīng)被[39]證實(shí)；事實(shí)上，最先進(jìn)的子圖搜索算法CFQL [39]已經(jīng)表明，現(xiàn)有的索引方法以及最近的預(yù)處理和枚舉技術(shù)在廣泛使用的數(shù)據(jù)集如PDBS、PCM和PPI的查詢處理中效率低下（因此CFQL逐個在多個數(shù)據(jù)圖上運(yùn)行子圖搜索）。因此，我們不使用索引，而將Bq視為數(shù)據(jù)圖的D。然而，可以在出現(xiàn)時利用索引（例如，I/O密集型應(yīng)用）。

4 Filtering by neighbor-safetdy

在本節(jié)中，我們描述了一種動態(tài)規(guī)劃方法與濾波技術(shù)相結(jié)合，以獲得一個緊湊的CS。
假設(shè)DAG q的路徑樹T (q)為樹，使得每個根葉路徑對應(yīng)q中不同的根葉路徑，并且T (q)共享q的根葉路徑的共同前綴（見圖2）。將具有v∈V (G)的根DAG q的弱嵌入M定義為T (q)的同態(tài)，使M (u) = v。這些概念最初是由[13]提出的。
給定一個CS，我們?yōu)閡∈V (q)和v∈V (G)定義了一個動態(tài)規(guī)劃（DP）表： D[u，v] = 1，如果v∈C (u)，以及以下必要條件，將嵌入映射到v保持；否則D[u，v] = 0。
(1)在v處存在一個子dagqu的弱嵌入M（即T（qu）的同態(tài)，使得M (u) = v）。
(2)對于將u映射到v的嵌入的任何必要條件h（u、v）（條件(1）除外），在CS中都是正確的。（下面我們提出了一個新的必要條件h (u、v）。）
D[u，v]可以使用以下從葉頂點(diǎn)到根頂點(diǎn)的自下而上的遞歸順序來計算，即，u在q中的所有子節(jié)點(diǎn)被處理后被處理：

其中，一個主函數(shù)f（D[uc，·]，v）為1，如果在CS中有vc與v相鄰，否則D[uc，vc] = 1；0。在動態(tài)規(guī)劃中比單獨(dú)應(yīng)用f更有效。
經(jīng)過動態(tài)規(guī)劃后，新的候選集計算如下：v在新的C (u)中，當(dāng)且僅當(dāng)D[u，v] = 1。（注意，候選集C (u)作為d的緊湊表示）這種優(yōu)化技術(shù)將被稱為擴(kuò)展的DAG-graph DP。讓從遞歸(2)中省略h（u，v）的優(yōu)化是簡單的DAGgraph DP。請注意，DAF [13]使用了簡單的DAG-圖DP，它只利用了上面的條件(1)。

我們提出一個必要的條件，確認(rèn)有標(biāo)簽l的v∈C (u)在CS中是足夠被映射到u的有標(biāo)簽l的鄰居，當(dāng)一個查詢節(jié)點(diǎn)v被映射到他的候選v∈C (u)。給定圖2的查詢圖和圖3的CS，用標(biāo)簽A將u2映射到v3不足以支撐u2的鄰居（例如v1和v2）和標(biāo)簽A。
現(xiàn)在我們定義了一個嵌入的必要條件h。

定義1對于每個頂點(diǎn)u∈V (q)和一個標(biāo)簽l∈∑，一個鄰集Nbrq（u，l）是u標(biāo)簽為l的鄰集的集合。對于每個頂點(diǎn)v∈C (u)和一個標(biāo)簽l∈∑，一個鄰域集NbrCS（u，v，l）被定義為∪un∈Nbrq（u，l）{vn∈C（un）| vn是v，v∈C (u)在CS中的毗鄰。

定義2給定一個查詢圖q和一個q和G上的CS，我們說v∈C（u）是鄰居安全的，關(guān)于u如果每個標(biāo)簽l∈∑，|Nbrq(u，l)|≤|NbrCS（u，v，l）|。

示例1在圖2的查詢圖q，Nbrq（u2，A）={u1，u4}，Nbrq（u2，B）={u3，u5}，圖三a中的CS，NbrCS（u2，v3，A）={v1}，NbrCS（u2，v5，B）={v3,v4,v6}。根據(jù)定義2，v3對于u2不是鄰居安全的，因?yàn)閨Nbrq（u2，A）|＞|NbrCS（u2，v3，A）|，而v5對于u2是鄰居安全的。

引理1假設(shè)我們在q和g上有一個CS。對于每個頂點(diǎn)u∈V (q)，將u映射到一個候選頂點(diǎn)v∈C(u)不能導(dǎo)致q的嵌入。
證明我們用矛盾證明了引理。假設(shè)存在v∈C (u)，當(dāng)映射u到v的嵌入M時，對u是不安全的。因?yàn)椤什皇青従影踩P(guān)于u（例如，存在這樣|Nbr頂點(diǎn)∈q（u，l）| > |NbrCS（u，v，l）|），至少有兩個不同的ui和ujNbrq（u，l）映射到相同的∈∈NbrCS（u，v，l）M（即M（ui）= M（u j）= vn）。這與在嵌入的定義中，M是內(nèi)射的條件（即，M（ui）= M（u j）為ui= u j）相矛盾。通過引理1，我們定義了h（u，v），這樣h（u，v）= 1，如果v是鄰居安全的，否則，h（u，v）= 0。
引理2給定q和G上的一個CS，擴(kuò)展的|圖DP在CS上的時間復(fù)雜度為O（|E(q)|×|E(G)|）。
在擴(kuò)展的dag圖DP之前，為每個u∈V (q)和l∈計算一個鄰居集Nbrq（u，l）。現(xiàn)在，對于每個u∈V (q)，必須為每個v∈C (u)和l∈計算鄰居集NbrCS（u，v，l）。為了做到這一點(diǎn)，對于一個固定的u∈V (q)，我們需要檢查v和vn之間的所有v∈C (u)和所有vn∈C（un）的邊，其中un∈Nbrq（u，l）的定義為4.1。對于固定的u∈V (q)，所有的鄰集Nbrq（u，l）都是不相交的，并且覆蓋了u的所有鄰集，因此我們在這個計算中只看u的每個鄰集un一次。根據(jù)∈C (u)的條件(b)，候選∈C（un）和所有的vn∈C（un）之間的邊數(shù)最多為O（|E (G)|）。 3.因此，對所有u∈V (q)的鄰域安全計算需要u∈V(q){deg(u)×O（|E (G)|）} = O（|E (q)||E (G)|）時間。
上述時間復(fù)雜度包括鄰居安全的計算，但它與[13]中DP的復(fù)雜度相同。
一個緊湊型CS的構(gòu)造。
通過使用上述優(yōu)化技術(shù)，多次使用不同的查詢DAG，我們可以過濾盡可能多的候選頂點(diǎn)，從而計算一個緊湊的CS。
在開始時，構(gòu)造了一個初始的CS。對于每個u∈V（q），C（u）被初始化為頂點(diǎn)集v∈v(G)，如LG (v) = Lq (u)。此外，鄰域標(biāo)簽頻率（NLF）濾波器[14]可以去除v∈C(u)，這樣就有一個滿足|Nbrq（u，l）| > |NbrG（v，l）|的標(biāo)簽l∈∑。我們將NLF實(shí)現(xiàn)為一個位數(shù)組，包含4個|||V(g)|位，以表示每個v∈V (g)和l∈的|||（v，l）|最多4個。因此，它可以用|NbrG（v，l）| < 4過濾v∈C (u)，從而使|Nbrq（u，l）| > |NbrG（v，l）|。圖3a說明了圖2中的查詢圖q上的初始CS和圖1中的數(shù)據(jù)圖G1。
由于DP是基于一個查詢的DAG來執(zhí)行的，所以我們使用DAG qD及其反向的qD?1（在圖2中）來細(xì)化候選集。在細(xì)化的第一步中，我們使用qD?1對初始CS運(yùn)行簡單的DAGgraph DP。在第二步中，我們通過DAG-圖DP進(jìn)行子圖搜索或擴(kuò)展的DAG-圖DP進(jìn)行子圖匹配。在第三步中，我們使用qD?1執(zhí)行擴(kuò)展的dag圖DP。
示例2給出圖2中的qD?1和圖3a中的CS，我們首先細(xì)化C（u1），然后細(xì)化C（u2），以此類推。在對圖3b中的C（u1）和C（u2）進(jìn)行細(xì)化后，v3和v4從C（u2）中去除，因?yàn)樗鼈儗2是不安全的。因此，在對圖3c中的C（u5）進(jìn)行細(xì)化后，v5從C（u5）中移除，因?yàn)関5附近沒有vc∈C（u2）。在同一圖中，v3、v4∈C（u3）對于u3是不安全的，而v5∈C（u3）在inC（u2）中沒有鄰居，因此它們從C（u3）中移除。
最后，如果存在一個空的候選集，即C (u) =?，我們就終止。否則，經(jīng)過多次優(yōu)化執(zhí)行，我們得到最終的CS。我們可以通過交替qD和qD?1重復(fù)擴(kuò)展的DAG圖DP，直到候選集合沒有發(fā)生變化，但從我們的實(shí)證研究來看，DP的三個步驟就足夠了。事實(shí)上，[13]實(shí)驗(yàn)證實(shí)了不需要改進(jìn)超過三次的事實(shí)。
綜上所述，VEQ中的擴(kuò)展DAG-圖DP和DAF [13]中的簡單DAG-圖DP都通過三種改進(jìn)構(gòu)造CS，每一種都將DP和查詢DAG的反向拓?fù)漤樞蛱幚鞤P。然而，與簡單的DAG-graph DP不同，擴(kuò)展的DAG-圖DP是一個更通用的框架，它可以添加嵌入的任何必要條件。我們采用鄰居安全（即定義2）作為這個必要條件。
在VEQ中通過鄰居安全過濾和在VF3 [7]中探索可行的部分映射有兩個主要區(qū)別。首先，當(dāng)VF3在查詢圖和數(shù)據(jù)圖上計算可行性集時，我們將鄰居安全應(yīng)用于只保留候選集中存活頂點(diǎn)之間的邊的CS。鄰居的安全只取決于這些邊緣，因此導(dǎo)致高過濾能力，以去除不希望的候選者。其次，VF3在搜索（或枚舉）階段試圖擴(kuò)展部分映射（因?yàn)榭尚行约菑漠?dāng)前部分映射計算出來的）時，會在可行性規(guī)則中考慮每個部分映射，但鄰居安全是搜索階段之前使用的一種過濾技術(shù)。
鄰域集與鄰域標(biāo)簽等價類（NLEC）[41]相同。偽星同構(gòu)約束（PSIC）[41]是一個嵌入的必要條件，它推廣了定義2。給定一個Nbrq（u，l）序列，對于1≤i≤|Nbrq（u，l）|，PSIC增量地將該序列中u的第一個i鄰域的數(shù)（即i）與與v相鄰的候選鄰域的并集大小進(jìn)行比較。同時，定義2只比較了|Nbrq（u，l）|和CS中與v相鄰的所有候選鄰居的并集大小。根據(jù)我們的實(shí)證研究，PSIC的濾波能力對定義2的提高可以忽略不計。在我們的工作中，我們首先將引理1和dag圖DP的濾波方法結(jié)合在一個單一的框架中。
鄰居安全利用緊湊輔助數(shù)據(jù)結(jié)構(gòu)CS中鄰居的標(biāo)簽頻率。這不會給沉重的搜索階段產(chǎn)生額外的計算開銷。（請注意，預(yù)處理步驟需要多項(xiàng)式時間，而搜索步驟在最壞的情況下需要指數(shù)級時間。）

5 Matching order based on static equivalence

在本節(jié)中，我們提出了一種改進(jìn)的自適應(yīng)查詢頂點(diǎn)的匹配順序，利用頂點(diǎn)的靜態(tài)等價性。假設(shè)我們試圖在搜索過程中擴(kuò)展部分嵌入M。
查詢圖q中一個未映射的頂點(diǎn)u在M中被稱為可擴(kuò)展，關(guān)于M如果至少有一個鄰居的u匹配M，和設(shè)置CM (u)的可擴(kuò)展的候選人u關(guān)于M被定義為一組頂點(diǎn)v∈C (u)相鄰M（un）CS每個映射的鄰居u。我們選擇一個可擴(kuò)展的頂點(diǎn)u作為下一個頂點(diǎn)，并將u與u的每個可擴(kuò)展的候選頂點(diǎn)進(jìn)行匹配。
然而，我們的自適應(yīng)匹配順序與現(xiàn)有的算法有所不同。最先進(jìn)的子圖匹配算法[3,13]采用葉分解策略，將查詢圖中的頂點(diǎn)分解為1度頂點(diǎn)集和其余的頂點(diǎn)集，并在將非1度頂點(diǎn)匹配后匹配1度頂點(diǎn)。這種方法通常有助于延遲冗余笛卡爾積[3]；然而，它有時花費(fèi)不必要的搜索空間，特別是在有小的1度頂點(diǎn)候選點(diǎn)的數(shù)量。我們在自適應(yīng)匹配順序中考慮了所有的查詢頂點(diǎn)，以減少搜索空間。
示例3考慮圖2中q的查詢DAG qD和圖1中的數(shù)據(jù)圖G2。請注意，在g2中沒有嵌入q。圖4中的搜索樹說明了搜索過程。一個節(jié)點(diǎn)（u，v）表示一個部分嵌入M的最后一對映射對，讓M表示一個節(jié)點(diǎn)和一個部分嵌入。一個節(jié)點(diǎn)（u、v）！表示映射沖突，即v已經(jīng)匹配，因此u不能映射到v。設(shè)（u，{v1，…，vn}）表示G中的n個頂點(diǎn)與qD中的一個頂點(diǎn)u匹配，其中n個= |NEC (u)|。根據(jù)圖4a所示的葉分解，在匹配非1次頂點(diǎn)后，匹配葉頂點(diǎn)u5。具體來說，給定一個部分嵌入M = {（u1，v1），（u2，v2）}，我們選擇u3作為下一個可擴(kuò)展頂點(diǎn)，然后匹配u4和u5；然而，沒有部分嵌入導(dǎo)致嵌入。因此，將u4和u5與所有可擴(kuò)展候選對象匹配，會推遲v3處u3和u5的映射沖突，從而導(dǎo)致巨大的冗余搜索空間。

新的匹配順序。在我們的自適應(yīng)匹配順序來選擇下一個可擴(kuò)展的頂點(diǎn)時，我們可以通過允許對1度頂點(diǎn)的匹配順序的靈活性來節(jié)省大量的搜索空間。假設(shè)我們正試圖擴(kuò)展一個部分嵌入的M。
-如果有一個一度可擴(kuò)展頂點(diǎn)u，使|NEC (u)|≥|UM (u)|，其中UM (u)表示CM (u)中u的未映射的可擴(kuò)展候選集，-如果|NEC (u)| > |UM (u)|，回溯。。
–否則（例如，如果|NEC (u)|=|UM (u)|），則選擇u作為下一個頂點(diǎn)。
-否則，如果只有一個可擴(kuò)展頂點(diǎn)，選擇其中一個作為下一個頂點(diǎn)。
-否則，選擇一個可擴(kuò)展的頂點(diǎn)u，使|CM (u)|是非單次頂點(diǎn)中的最小值。
示例4考慮了圖4b中新的匹配順序的搜索樹?；叵胍幌拢琿D中頂點(diǎn)u5的鄰域等價類NEC（u5）對應(yīng)于q中的一個單例集合{u5 (}。給定一個部分嵌入的M = {（u1，v1），u2，v2)}和UM（u5）= {v3}，我們選擇u5作為下一個頂點(diǎn)來匹配，因?yàn)閨NEC（u5）|=|UM（u5）|。在我們將M擴(kuò)展到M∪{（u5，{v3}）}之后，沒有一次可擴(kuò)展的頂點(diǎn)，所以我們選擇u3作為下一個要匹配的頂點(diǎn)。因此，我們可以在不匹配u4的情況下，盡早在v3處檢測到u3和u5的映射沖突。

6 Run-time pruning by dynamic equivalence

在本節(jié)中，我們開發(fā)了一種基于CS中候選頂點(diǎn)的鄰域等價性來動態(tài)去除搜索樹的等價子樹的新技術(shù)。一旦我們訪問一個新節(jié)點(diǎn)（即一個新的部分嵌入）M，我們探索子樹根于M和回到節(jié)點(diǎn)M.利用鄰居等價的候選人和知識的探索子樹根于M，我們可以刪除一些部分嵌入節(jié)點(diǎn)的兄弟姐妹M。
定義3 假設(shè)我們給定一個q和G上的CS。對于V（q）的節(jié)點(diǎn)u和C（u）中的兩個候選節(jié)點(diǎn)vi和vj，我們說vi和vj共享鄰居，如果對于每個q中的u的鄰居un，vi和vj在C（un）中有共同的鄰居。然后一個cell 派（u，v）被定義為，在CS中和v共享鄰居的節(jié)點(diǎn)集，v‘屬于C（u）。
作為一個新的運(yùn)行示例，我們使用了圖5中的查詢圖q和數(shù)據(jù)圖G3。注意，v3、v4和v5在G3中有不同的鄰居集。兩個圖之間，CS圖6構(gòu)造，v3v4和v5C（u5）共享鄰居在CS（即π（u5v3）=π（u5v4）=π（u5v5）={v3，v4，v5）)，而只有v3和v4C（u2）共享鄰居在CS（即π（u2、v3）= π（u2、v4）= {v3、v4}）。

假設(shè)在本節(jié)的其余部分中，我們在探索了植根于M∪{（u，vi）}的子樹后，給出了一個部分嵌入的M，一個可擴(kuò)展的頂點(diǎn)u∈V (q)和vi∈CM (u)。設(shè)TM（u，vi）表示在基于M∪{（u，vi）}的子樹中找到的嵌入集合。對于一些未映射的可擴(kuò)展候選對象vj∈CM (u)，我們的目標(biāo)是避免探索基于M∪（u，v j）的子樹（例如，如果基于M∪（u，vi）的子樹和基于M∪（u，v j）的子樹是等價的，定義如下）。
定義4給定一個（部分）嵌入M?，根于M∪{（u，vi）}，（部分）嵌入Ms?∈TM（u，v j）對稱到M?是M??（u，vi）∪（u，vj）如果vj沒有映射到M?；??（u，vi），（u’，vj）∪（u，vj），（u’，vi）如果vj在M?中映射到u’。
定義5在M∪（vi）上的子樹和在M∪（vj）上的子樹在以下情況下是等價的：
當(dāng)子樹根M∪{（vi）}沒有嵌入（即TM（vi）=?），子樹根M∪{(v)}也沒有嵌入，當(dāng)TM（uvi）=?，對于每個嵌入M?∈TM（uvi）存在一個嵌入女士?∈TM（u，v j）對稱到M?，反之亦然。
假設(shè)我們給出一個根于M∪{（u，vi）}的子樹Ti，以及它對應(yīng)的子樹Tj根于M∪{（u，v j）}，如圖7、8和9所示。

圖7顯示了在Ti中沒有發(fā)現(xiàn)嵌入的情況。在Ti中，u不能與vi匹配，因?yàn)関i已經(jīng)與u匹配，然后u與vj匹配，但最終在Ti中沒有發(fā)現(xiàn)嵌入。在Tj中，除了vi和vj的角色交換外。然后將vi和vj包含在負(fù)細(xì)胞πM?（u，vi）中，其定義見定義6。

圖8顯示了與圖7相似的情況，但在Ti中發(fā)現(xiàn)了一個嵌入。即u與vj匹配，在Ti中發(fā)現(xiàn)嵌入M?。Tj的情況與Ti的情況相同，只是vi和vj的角色是交換的。因此，對稱嵌入的Ms?中包含（u，v j）和（u，vi），而不是（u，vi）和（u，v j）。在這種情況下，vi和vj包含在陽性細(xì)胞πM +（u，vi）中。

圖9顯示了在Ti中發(fā)現(xiàn)了嵌入的M?，但在Tj中沒有發(fā)現(xiàn)對稱嵌入的Ms?的情況。在這種情況下，vi不包括在單元格π（u，v j）中，而vi則包括在Figs的π（u，v j）中。7和8。在Ti中，vi從未被訪問過作為u的候選者，因?yàn)関i不包括在π（u，v j）中。u與vj匹配，得到嵌入M?。在Tj中，vi將不作為u的候選者被訪問，因?yàn)関i不包括在π（u，v j）中。而u將不會與vj匹配，因?yàn)関j已經(jīng)與u匹配，所以將不會找到對稱嵌入的Ms?。如果在Ti中訪問的單元格π（u，v j）不包含vi，那么vj就包含在增量集δM（u，vi）中。
現(xiàn)在我們將正式定義保證等價性的條件。
定義6讓我（uvi）的所有映射（u，，）沖突(u)6∈厘米(u)子樹根于M∪（，），和我（uvi）的所有映射（u，v）訪問的子樹π（u，v）vi。關(guān)于M的負(fù)單元格π?M（u，vi）是π（u，vi）∩{∩（u，vi）∈IM（u，vi）π（u，vi）}，如果在子樹的vi處至少有一個映射沖突；否則π（u，vi）。A positive cell πM +(u, vi) regarding M is πM ?(u, vi) ? δM (u, vi) where delta set δM (u, vi) = ∪(u ,v )∈OM (u,vi)π(u , v ).關(guān)于M的等價集πM（u，vi）的定義如下：

到節(jié)點(diǎn)M∪（u3，v9），在探索了基于M∪（u3，v9）的子樹之后，M=（u1，v1），（u2，v3），（u4，v8）。關(guān)于M的等價集πM（u3，v9）是π?M（u3，v9）= π（u3，v9）= {v8，v9，v10}，因?yàn)樵趘9處不存在映射沖突。M∪{（u2，v3）}M={（u1v1）}，有一個映射沖突v3后的探索子樹根于M∪{（u2v3）}沒有嵌入發(fā)現(xiàn)，因此πM（u2v3）πM?（u2v3）=π（u2v3）∩π（u5v3）={v3，v4}。

例6（正單元格）作為圖10搜索樹中的一個具體例子，假設(shè)我們在探索了M∪（u4，v10）之后，在M∪（u4，v10）之后，回到M = {（u1，v2），（u2，v6）}。在勘探過程中沒有出現(xiàn)映射沖突，πM?（u4，v10）為π（u4，v10）= {v10，v11，v12}。在這次探索中，我們還訪問了一個映射（u3，v11），這樣π（u3，v11）v10，因此πM+（u4，v10）=π?M（u4，v10）?δM（u4，v10）= {v10，v12}，其中δM（u4，v10）= π（u3，v11）= {v11}。由于我們在勘探過程中發(fā)現(xiàn)了嵌入物，所以πM（u4，v10）就是πM +（u4，v10）。
現(xiàn)在我們聲稱等價集πM（u，vi）導(dǎo)致了每個vj∈πM（u，vi）的M∪{（u，v j）}的子樹之間的等價性。
引理3對于每一個vj∈πM（u，vi），根于M∪{（u，vi）}的子樹和根于M∪{（u，v j）}的子樹是等價的（即，πM是保證等價性的條件）。
對vi成分的證明?！蔆 (u)和vj∈C (u)，我們需要遵循
(i)C(u）中的兩個候選者vi和vj共享鄰居。
（ii）對于在M∪（u，vi）的子樹中與u發(fā)生沖突的頂點(diǎn)u，存在vj∈C（u）與vi∈C（u）共享鄰居。
（iii）對于基于M∪（u，vi）的子樹中映射到vj的每個頂點(diǎn)u，存在vi∈C（u）與vj∈C（u）共享鄰居。
vi和vj在πM（u，vi）中的事實(shí)可以重寫如下。
-如果TM（u，vi）=?，(i)和（ii）保持。–否則，(i)、（ii）和（iii）持有。
設(shè)TM（u，vi）TM（u，v j）表示對于每個嵌入M?∈TM（u，vi）都存在一個對稱于M?的嵌入Ms?∈TM（u，v j）。那么子樹的等價性的定義可以描述如下。
-如果為TM（u，vi）=?，則為TM（u，v j）=?，即TM（u，vi）TM（u，v j）。–否則，TM（u，vi）TM（u，v j）和TM（u，vi）TM（u，v j）。
我們用矛盾法證明了該引理，即如果TM（u，vi）TM（u，v j），則vj/∈πM（u，vi）。設(shè)u是第一個與u具有相同標(biāo)簽的查詢頂點(diǎn)，如果存在這樣的頂點(diǎn)，則以匹配的順序出現(xiàn)在u后面；否則。
假設(shè)TM（u，vi）TM（u，v j），即存在一個嵌入M?∈TM（u，v j），在TM（u，vi）中不對稱。也就是說，在根于M∪{（u，vj）}的子樹中存在一個部分嵌入M2，導(dǎo)致M?，但對稱于M2的部分嵌入M1必須不存在于根于M∪{（u，vi）}的子樹中，或者永遠(yuǎn)不會導(dǎo)致嵌入在TM（u、vi）中。假設(shè)M1 = M∪{（u，vi），…，（u，v j）}和M2 = M∪{（u，v j），…，（u，vi）}如果u=u；M1 = M∪{（u，vi）}和M2 = M∪{（u，v j）}否則。在u及其候選的vn∈C（un）中存在一個鄰居un，使得M2擴(kuò)展到一個不能被M1擴(kuò)展的映射（un，vn）。這意味著vj∈C（u）與vn∈C（un）相鄰，而vi∈C（u）不相鄰，這與vi，v j∈C（u）共享鄰居相矛盾，即，該聲明與條件（ii）如果u=u；條件(i)如果u=u。
假設(shè)TM（u，vi）為TM（u，v j）。與上述相同，這個假設(shè)導(dǎo)致與條件（iii）如果u=u；條件(i)如果u=u。
示例7（通過負(fù)單元格進(jìn)行修剪）再次考慮圖10中的搜索樹。當(dāng)我們回到節(jié)點(diǎn)M∪{（u3v9）}M={（u1v1），（u2v3），（u4v8）}后的探索子樹基于M∪{（u3v9）}，我們找不到任何嵌入的q，沒有映射沖突v9在探索。因此，無論πM（u3，v9）中的哪個頂點(diǎn)與u3匹配，它都不會導(dǎo)致q的嵌入，因?yàn)樗锌赡艿臄U(kuò)展都將以同樣的方式以失敗告終。因此，我們不需要為每個vj∈πM（u3，v9）擴(kuò)展節(jié)點(diǎn)M∪{（u3，v9）}的兄弟節(jié)點(diǎn)M∪{（u3，v j）}。類似地，假設(shè)我們在探索了節(jié)點(diǎn)M∪{（u2，v3）}之后，回到了其中M = {（u1，v1）}。我們找不到q的任何嵌入，在勘探過程中在v3處有一個映射沖突，所以πM（u2，v3）= {v3，v4}。這意味著根于M∪{（u2，v4）}的子樹將與根于M∪{（u2，v3）}的子樹相同，除了映射沖突發(fā)生在（u5，v4）而不是（u5，v3）。因此，M∪{（u2，v4）}不會導(dǎo)致嵌入，因此我們不需要擴(kuò)展節(jié)點(diǎn)M∪{（u2，v3）}的兄弟M∪{（u2，v4）}。
示例8（通過陽性單元格進(jìn)行修剪）請再次考慮圖10中的搜索樹。假設(shè)我們探索了根于M∪{（u4、v10）}的子樹，其中M = {（u1、v2）、（u2、v6）}，并回到節(jié)點(diǎn)M∪{（u4、v10）}。我們在TM（u4，v10）中發(fā)現(xiàn)了兩個嵌入，得到了πM（u4，v10）= {v10，v12}，這意味著M∪{（u4，v12）}將導(dǎo)致對每個M?∈TM（u4，v10）的嵌入對稱，即相同的嵌入如M?∈TM（u4，v10），除了u4被映射到v12。注意，v11∈CM（u4）不在πM（u4，v10）中，因?yàn)槲覀兛赡苡捎趗4和u3在v11處的映射沖突，沒有發(fā)現(xiàn)任何從M∪{（u4，v11）}擴(kuò)展出來的嵌入。

搜索過程。算法1中的匹配是我們在CS中找到所有q嵌入的搜索過程。如果|M|=|V（qD）|（第1行），我們報告M作為q的嵌入；否則，我們在第3行選擇一個可擴(kuò)展的頂點(diǎn)（||=0首先選擇qD的根頂點(diǎn)），對于每個未訪問的v∈CM (u)，將當(dāng)前的部分嵌入M擴(kuò)展到M‘=M∪{（u，v）}，并遞歸地執(zhí)行與M的匹配（第5-24行）。然而，我們的回溯過程不同于現(xiàn)有的算法如下。
一方面，我們根據(jù)新的自適應(yīng)匹配順序，在多個可擴(kuò)展頂點(diǎn)中選擇下一個可擴(kuò)展頂點(diǎn)u。5（第3行）。更多的另一方面，引理3的剪枝技術(shù)是v∈CM (u)，v被初始化為“不等價”（第4行）。讓eqM(u, v)為πM(u, v)中的頂點(diǎn)。中的頂點(diǎn)，該頂點(diǎn)已經(jīng)在M的擴(kuò)展中與u匹配。M. 對于每個未訪問的候選者v∈CM（u），我們報告一個嵌入Ms?∈TM（u，v）對稱于M?的每個嵌入M?從M∪{(u, eqM (u, v))}擴(kuò)展而來，并且如果v∈CM（u）是等價的，則轉(zhuǎn)到第5行（第7-9行）；否則，初始化πM-(u, v)和δM (u, v)，并更新δM (u , v )為搜索樹中(u, v)的每一個祖先(u , v )更新δM，以便的每一個祖先(u , v )更新δM (u , v )，使va /∈π(u, v)和π(ua, va) ∩π(u, v)=?。遞歸調(diào)用匹配（第12-14行）。在遞歸調(diào)用匹配之后，πM表示πM?（u，v），如果子樹中沒有嵌入πM∪（u，v）}；πM +（u，v）= πM?（u，v）?δM（u，v），否則（第17-18行）。接下來，我們讓eqM（u，v）為v，并將“等價”設(shè)置為πM（u，v）中的每個v（第19-21行）。如果v已經(jīng)被訪問（第22行），則會發(fā)生M?1(v)和u在v處的映射沖突，因此我們更新一個負(fù)細(xì)胞πM?p（M?1(v)，v）（第23-24行）。
子圖搜索，我們修改算法1，這樣它發(fā)現(xiàn)一個嵌入q在每個G∈∈首先，我們終止并返回真一旦找到第一個嵌入m，一個可擴(kuò)展的頂點(diǎn)u和一個未訪問的可擴(kuò)展候選人v∈厘米(u)，v是等價的，我們?nèi)サ?行（第8行刪除）。最后，不再需要δM（u，v）的計算（第13-14行被移除）。
引理4給定一個頂點(diǎn)u∈V (q)和可擴(kuò)展候選項(xiàng)的集合CM (u)，計算所有v∈CM (u)的單元格π（u，v）的時間復(fù)雜度為O（deg(u)|V (G)||CM (u)|）。證明我們可以通過CM (u)數(shù)組上的分治范式獲得細(xì)胞π（u，v）：(1)選擇一個新的軸候選vn∈u鄰居un（un），(2)分區(qū)元素數(shù)組的兩個子數(shù)組根據(jù)每個元素v∈CM (u)是否鄰居的c，和(3)重復(fù)每個子數(shù)組的步驟，直到子數(shù)組是一個單例或所有可能的樞軸vn∈C（un）為所有鄰居u檢查。在q中有u的deg (u)個鄰居。對于u的每個鄰居un，在所有v∈CM (u)的C（un）中都有O（|V (G)|）鄰域。因此，所有可能的樞軸的數(shù)量為O（deg(u)|V (G)|）。因此，計算所有v∈CM (u)的單元格π（u，v）的時間復(fù)雜度為O（deg(u)|V (G)||CM (u)|）。
在實(shí)現(xiàn)中，不需要為每個u∈V (q)和v∈C (u)計算π（u，v），因?yàn)橐粋€人只能訪問發(fā)現(xiàn)一些v∈C (u)，并在子圖搜索中嵌入（或一些子圖匹配中嵌入）后終止。因此，細(xì)胞不是在CS構(gòu)建后計算CS中的所有候選細(xì)胞的，而是在第一次計算v∈CM (u)時計算CM (u)；事實(shí)上，為所有v∈CM (u)計算細(xì)胞π（u，v）需要合理的時間，因?yàn)閨CM (u)||C (u)|。我們使用單元格id來實(shí)現(xiàn)實(shí)現(xiàn)效率和更好的表示。在實(shí)現(xiàn)中，我們將每個不同的單元格與一個唯一的ID關(guān)聯(lián)起來。一旦獲得了π（u，v），每個v∈C（∈）的ID，這樣v∈π（u，v），因此當(dāng)以后訪問v∈C (u)時，π（u，v）可以通過ID重用和訪問。對于一些候選的v∈π（u，v），一旦我們計算πM（u，v），我們將v∈πM（u，v）標(biāo)記為“等價的”，這樣只要當(dāng)前的部分嵌入M保持不變，我們就可以重用πM（u，v）。

7 Performance evaluation

在本節(jié)中，我們評估了子圖搜索和子圖匹配的競爭算法的性能。所有的源代碼均來自之前論文的作者，并在C++中實(shí)現(xiàn)。實(shí)驗(yàn)在一臺運(yùn)行CentOS的機(jī)器上進(jìn)行，該機(jī)器有兩個IntelXeonE5-2680v3 2.5 GHz cpu和256GB內(nèi)存。
由于這些問題是np困難的，算法不能在合理的時間內(nèi)處理一些查詢；因此，我們?yōu)槊總€查詢設(shè)置了10分鐘的時間限制。如果算法在時間限制內(nèi)不處理查詢，我們將查詢的處理時間視為10分鐘。我們說在時間內(nèi)完成的查詢被解決。每個查詢集由100個查詢圖組成。對于每個查詢集，我們測量在之前的工作[13,18,39]中常用的度量的平均值：

• 假陽性率FPq=|Cq|?|Aq||Cq|查詢圖q：我們評估子圖搜索算法的過濾能力，其中Cq是q過濾后剩余數(shù)據(jù)圖的集合，Aq是q的答案圖的集合。
• 輔助數(shù)據(jù)結(jié)構(gòu)的大小：我們測量候選集的大小之和，即u∈V(q)|C(u)|，以評估子圖匹配算法的有效性。
• 查詢處理時間：我們測量子圖搜索的過濾時間和驗(yàn)證時間之和，或者子圖匹配的預(yù)處理時間（即構(gòu)建輔助數(shù)據(jù)結(jié)構(gòu)的時間）和搜索時間（即枚舉前105個嵌入的時間）之和。為了進(jìn)行合理的比較，我們計算了處理由至少一種競爭算法求解的查詢圖的平均時間。
  
  
• 過濾時間與驗(yàn)證時間的比：這顯示了查詢處理時間占多少過濾或驗(yàn)證時間。

盡管諸如Grapes等子圖搜索的索引過濾驗(yàn)證方法顯然在索引數(shù)據(jù)集上花費(fèi)了大量的時間和空間，但索引時間和索引大小將不會被視為評估的度量，因?yàn)樗衅渌訄D搜索算法都沒有索引地處理查詢。

7.1 Induced versus non-induced

“誘導(dǎo)”子圖匹配和“非誘導(dǎo)”子圖匹配是不同的問題。這兩個問題中的哪一個更難解決？由于不同的算法使用不同的技術(shù)，因此通過比較不同的算法并不容易回答上述問題。幸運(yùn)的是，RI [5]和Glasgow [28]同時解決了誘導(dǎo)和非誘導(dǎo)子圖匹配問題，因此我們試圖通過測量這些算法在誘導(dǎo)和非誘導(dǎo)問題中的搜索空間和查詢處理時間來回答上述問題。我們在實(shí)驗(yàn)中加入了VF3 [7]和VEQM作為參考。
圖11顯示了這些算法的搜索空間的大?。此阉鳂渲械墓?jié)點(diǎn)數(shù)）和查詢時間，其中(I)和(N)分別表示“誘導(dǎo)的”和“非誘導(dǎo)的”。在這個實(shí)驗(yàn)中，我們只運(yùn)行每個算法在10分鐘的時限內(nèi)找到所有匹配的查詢，以便我們可以測量搜索空間的大小。RI (N)和Glasgow (N)的搜索空間分別比RI (I)和Glasgow (I)大得多，說明非誘導(dǎo)子圖匹配是比誘導(dǎo)子圖匹配的搜索空間更大的問題。因此，誘導(dǎo)算法與非誘導(dǎo)算法之間的搜索空間的差距導(dǎo)致了它們之間的查詢處理時間的差距。VEQM的性能始終優(yōu)于其他非誘導(dǎo)算法。因此，即使對于同一算法，這兩個問題也顯示出顯著的困難差距。因此，在接下來的實(shí)驗(yàn)中，我們主要將我們的算法與非誘導(dǎo)子圖搜索或子圖匹配算法進(jìn)行比較。

7.2 Subgraph search

由于CFQL [39]明顯優(yōu)于現(xiàn)有的子圖搜索算法，而Grapes [12]在現(xiàn)有的索引-過濾-驗(yàn)證算法[18,39]中查詢處理速度最快的，因此我們選擇這兩種算法與我們的子圖搜索算法VEQS進(jìn)行比較。此外，我們修改了最先進(jìn)的子圖匹配算法DAF [13]來解決子圖搜索，并將其（在本節(jié)中稱為DAFS）包括在我們的比較中。真實(shí)數(shù)據(jù)集。實(shí)驗(yàn)在真實(shí)數(shù)據(jù)集上進(jìn)行，其中[12,18,39]中使用的PDBS，PCM，PPI，和IMDB，REDDIT，由[47]提供。PDBS是一組代表DNA、RNA和蛋白質(zhì)的圖表。PCM是一套氨基酸的蛋白質(zhì)接觸圖。PPI是一個蛋白質(zhì)-蛋白質(zhì)相互作用網(wǎng)絡(luò)的數(shù)據(jù)庫。IMDB是一個電影協(xié)作數(shù)據(jù)集。REDDIT是一個在線討論社區(qū)的數(shù)據(jù)集，而協(xié)作”是一個科學(xué)協(xié)作數(shù)據(jù)集。由于沒有關(guān)于IMDB、REDDIT和合作的標(biāo)簽信息，我們隨機(jī)分配了一個標(biāo)簽每個頂點(diǎn)都有10個不同的標(biāo)簽。表2總結(jié)了這些數(shù)據(jù)集的特征。

查詢集。為了檢驗(yàn)這些算法，我們采用了兩種與以往研究相似的查詢生成方法，即隨機(jī)游走[18,39]和寬度優(yōu)先搜索（BFS）[39,44]。對于每個數(shù)據(jù)集D，我們生成8個查詢集QiR（即隨機(jī)游走）和QiB（即BFS），其中i∈{8,16,32,64}是一個查詢圖的邊數(shù)。通過隨機(jī)游走方法生成查詢圖如下： (1)從隨機(jī)選擇的圖G∈D中均勻隨機(jī)選擇一個頂點(diǎn)；(2)從選定的頂點(diǎn)進(jìn)行隨機(jī)游走，直到我們訪問i條不同的邊，從中提取一個帶有這些邊的子圖。在BFS方法中，我們從選定的頂點(diǎn)執(zhí)行一個BFS，直到我們訪問i條不同的邊。
假陽性比率。圖12顯示了真實(shí)數(shù)據(jù)集上的子圖搜索算法的假陽性率（collab的Q64R中的假陽性率缺失，因?yàn)槌薞EQS之外，沒有任何算法在時限內(nèi)完成COLLAB的Q64R中的任何查詢）。DAFS在過濾假答案方面最差，但在大多數(shù)查詢集中，平均假陽性率小于0.1。假陽性比的很大提高源于利用鄰居安全的擴(kuò)展dag圖DP。查詢處理時間。圖13顯示了這些算法的查詢處理時間的算術(shù)平均值。VEQS通常是最快的（除了一些小尺寸的查詢集），這不僅是因?yàn)閿U(kuò)展的DAG-graph DP獲得的假陽性答案更少，而且由于動態(tài)等價縮小的基于靜態(tài)等價的匹配順序的搜索樹也更小。VEQS比DAFS快兩個數(shù)量級，比CFQL快3個數(shù)量級。在IMDB的Q32B中，VEQS比葡萄高出5個數(shù)量級。然而，VEQS的查詢處理時間略大于CFQL Q8R和Q8B PDBS，PCM，PPI因?yàn)榍度胍粋€小的查詢圖可以很容易地找到所有的算法，因此利用擴(kuò)展DAG-graph DP或修剪技術(shù)VEQS可能招致開銷。
每個算法的查詢處理時間根據(jù)查詢圖的大小和數(shù)據(jù)集的特征而有很大的變化。一般來說，VEQS和其他圖之間的性能差距會隨著查詢圖大小的增大而增大。雖然grap顯示了在PDBS上的性能穩(wěn)定，但其查詢處理時間隨著查詢圖大小的增長而呈指數(shù)增長。在除PDBS之外的所有數(shù)據(jù)集的CFQL結(jié)果中，也可以觀察到大型查詢的查詢處理時間的峰值。然而，DAFS在稀疏數(shù)據(jù)圖REDDIT和PDBS中需要幾乎恒定的查詢處理時間，并且比在其他的CFQL和PDBS中顯示出更穩(wěn)定的性能。除了PPI（最大的數(shù)據(jù)圖）和協(xié)作（大量最密集的數(shù)據(jù)圖）外，隨著所有數(shù)據(jù)集的查詢圖大小的增加，VEQS的查詢處理時間保持穩(wěn)定。
些結(jié)果來源于過濾時間與驗(yàn)證時間的比值，如表3所示。對于所有的競爭算法，驗(yàn)證在最壞的情況下需要指數(shù)級時間而濾波需要多項(xiàng)式時間。實(shí)際上，在表3中，Grapes花費(fèi)了大部分的查詢處理時間來驗(yàn)證候選圖，這降低了整體性能。CFQL的驗(yàn)證時間占了除PDBS外的大部分查詢處理時間。雖然DAFS的驗(yàn)證時間在PPI、IMDB和COLLAB上占其查詢處理時間的60%以上，但驗(yàn)證時間的比例始終小于CFQL。不像其他的算法，VEQS花費(fèi)的驗(yàn)證時間少于或與過濾時間相當(dāng)，這證實(shí)了它比其他過濾時間的性能更穩(wěn)定。為了進(jìn)一步量化和分析查詢之間的性能差距，我們在圖14中測量了查詢處理時間的幾何平均值。我們還在圖15中給出了查詢處理時間的分布情況。對于每個算法，每個數(shù)據(jù)集上的查詢都按圖15中該算法的查詢處理時間的升序進(jìn)行排序。查詢處理時間的分布和算法的行為因數(shù)據(jù)集而異。在PDBS中，每個算法的查詢處理時間都在逐漸增加。在IMDB和PCM中，由于VEQS的開銷，對于大約80%的查詢，CFQL和DAFS的查詢處理時間都小于VEQS。(圖中CFQL和DAFS的幾何平均值小于VEQS的幾何平均值，證實(shí)了這一結(jié)果。 14.)相比之下，VEQS對大多數(shù)查詢顯示了相對恒定的查詢處理時間，不像其他的查詢處理時間急劇增加硬查詢。在REDDIT中，Grapes和CFQL提前達(dá)到了硬查詢的時間限制，而VEQS則顯示出穩(wěn)定的性能。對于PPI和COLLAB，所有的算法都有非常困難的查詢，其查詢處理時間超過了時間限制（即10分鐘）。葡萄首先達(dá)到時間限制，然后DAFS達(dá)到極限，然后是CFQL。同時，VEQS只有少數(shù)查詢的運(yùn)行時間超過了時間限制。敏感性分析。我們通過改變一組D的數(shù)據(jù)圖的幾個特征來評估算法。我們使用演化圖[30]升級PPI的最小數(shù)據(jù)圖（有2008條邊），生成每個數(shù)據(jù)圖G∈D，并根據(jù)冪律分布為頂點(diǎn)分配標(biāo)簽。我們改變了以下參數(shù)：
-在： 10、20、40、80中不同標(biāo)簽的數(shù)量
-在D： 2、4、8、16中數(shù)據(jù)圖的比例因子s
-在D： 102、103、104、105中數(shù)據(jù)圖的數(shù)量
s表示|E (G)|倍大于輸入數(shù)據(jù)圖的|倍，而演化圖通過相應(yīng)地增加|V (G)|來保持G相同的統(tǒng)計特性。與現(xiàn)有的工作[18,39]類似，我們將| | = 20、s = 2和|D| = 103設(shè)置為默認(rèn)值；事實(shí)上，我們選擇s = 2，以便默認(rèn)的|V(現(xiàn)有工作的壓力測試。如果未指定，則參數(shù)被設(shè)置為其默認(rèn)值。我們在每個數(shù)據(jù)集d上使用查詢集Q16R和Q16B。假陽性比率。這些算法在合成數(shù)據(jù)集上的假陽性率顯示在圖16的左列。由于內(nèi)存使用過多，Grapes無法完成使用s = 16或使用|D| = 105的數(shù)據(jù)圖的索引。VEQS在假陽性比率方面始終優(yōu)于其他公司?？偟膩碚f，假陽性率隨著不同標(biāo)簽數(shù)量的增加而減少，因?yàn)轫旤c(diǎn)上有更多的不同標(biāo)簽，使算法能夠提取不同的特征或獲得更少的候選特征，從而導(dǎo)致過濾更多的錯誤答案。隨著數(shù)據(jù)圖的大?。幢壤蜃觭）的增大，假陽性比率通常也會降低，特別是對于隨機(jī)游走查詢集。
查詢處理時間。算法對合成數(shù)據(jù)集的查詢處理時間如圖17右列所示。查詢處理時間隨著不同標(biāo)簽數(shù)量的增加而減少，因?yàn)槲覀兛梢酝ㄟ^利用更多的標(biāo)簽來過濾更多的數(shù)據(jù)圖，并驗(yàn)證更少的候選圖。查詢處理時間隨著數(shù)據(jù)圖的增加而增加，因?yàn)轵?yàn)證假陽性數(shù)據(jù)圖的時間可能會顯著增加。時間也會隨著數(shù)據(jù)圖數(shù)量的增加而增加，因?yàn)楦嗟募訇栃源鸢缚赡軙灾笖?shù)級增加驗(yàn)證時間。
綜上所述，VEQS在過濾錯誤答案方面優(yōu)于其他算法，并且在驗(yàn)證中占用的查詢處理時間較少。我們觀察的實(shí)驗(yàn)驗(yàn)證通常需要更多的時間在一個假陽性的答案比一個答案，因?yàn)橐粋€算法必須探索整個搜索空間來驗(yàn)證沒有嵌入假陽性圖而終止一旦發(fā)現(xiàn)一個嵌入答案圖。因此，假陽性答案的數(shù)量越少，探索整個搜索空間的嘗試就越少。然而，在驗(yàn)證階段，在答案圖中找到一個嵌入物有時會花費(fèi)很多錢。因此，一種更先進(jìn)的驗(yàn)證技術(shù)可以通過避免頻繁的回溯，快速地找到在答案圖中嵌入查詢圖。因此，降低假陽性答案（通過具有鄰居安全的擴(kuò)展dag-grapDP）和減少搜索空間（通過基于靜態(tài)等價匹配和動態(tài)等價運(yùn)行時修剪）可以縮短驗(yàn)證時間，從而顯著提高整體性能。

7.3 Subgraph matching

為了評估我們的子圖匹配算法VEQM的性能，我們將VEQM與來自數(shù)據(jù)管理社區(qū)的最近的子圖匹配算法CFL-Match [3]、DAF [13]、RIfs [40]和GQLfs[40]以及來自AI社區(qū)的格拉斯哥[28]進(jìn)行了比較。
數(shù)據(jù)集。我們用表4中的真實(shí)數(shù)據(jù)集來測試算法，這些數(shù)據(jù)集在以前的工作中被廣泛使用[3,13,14,23].酵母、HPRD和人類是蛋白質(zhì)-蛋白質(zhì)相互作用的網(wǎng)絡(luò)。電子郵件通信網(wǎng)絡(luò)和DBLP協(xié)作網(wǎng)絡(luò)來自斯坦福大型網(wǎng)絡(luò)數(shù)據(jù)集收集[24]。YAGO是一個RDF數(shù)據(jù)集。
查詢集。我們使用與[3]和[13]相同的實(shí)驗(yàn)設(shè)置。我們生成稀疏查詢集Qi S和非稀疏查詢集Qi N，其中i是查詢圖中的頂點(diǎn)數(shù)，這樣對于酵母和HPRD的i∈{50、100、150、200}，其余數(shù)據(jù)集的i∈{10、20、30、40}。Qi S和Qi N中的每個查詢圖的平均度分別為≤3和>3。查詢圖的生成如下： (1)均勻隨機(jī)選擇一個頂點(diǎn)，(2)對數(shù)據(jù)圖進(jìn)行隨機(jī)游走，直到我們訪問i個不同的頂點(diǎn)，(3)提取一個子圖，包含訪問的頂點(diǎn)和這些頂點(diǎn)之間的一些邊。輔助數(shù)據(jù)結(jié)構(gòu)的尺寸。為了評估我們的CS與最優(yōu)的距離，我們比較了我們的CS和Steady的大小。穩(wěn)態(tài)重復(fù)精煉C (u)達(dá)到一個穩(wěn)定狀態(tài)，其中對于每個v∈C (u)和u∈(q)，v滿足以下約束：對于一個鄰域u，C（u）和一組v的鄰居至少有一個共同的頂點(diǎn)。采用穩(wěn)態(tài)作為[40]中的最優(yōu)CS。
圖18顯示了每個算法和Steady的輔助數(shù)據(jù)結(jié)構(gòu)的平均大小。其規(guī)模越小，算法的搜索空間就越小。輔助數(shù)據(jù)結(jié)構(gòu)的大小會隨著查詢圖的增大而增大。由于擴(kuò)展的DAG-圖DP具有鄰居安全性，VEQM始終比DAF和CFL-Match的候選數(shù)據(jù)數(shù)量更少。
在大多數(shù)查詢集中，在我們擴(kuò)展的dag圖DP后剩余的候選數(shù)量略大于Steady，但有時小于穩(wěn)態(tài)，因?yàn)槿跚度牒袜従影踩次覀兊倪^濾條件）的結(jié)合略強(qiáng)于Steady的過濾條件。與DAF中的CS大小相比，擴(kuò)展的DAG圖DP在酵母和電子郵件中減少了10%以上，在DBLP中減少了20%；事實(shí)上，DAF只使用簡單的DAG圖DP，所以對于每個u∈V (q)，VEQM的CS中的C (u)是DAF的一個子集。
圖19顯示了擴(kuò)展的DAg圖DP、CFL-Match、DAF和Steady的過濾時間。一方面，延伸由于鄰居安全計算，DAG-graph DP通常比CFLMatch或DAF花費(fèi)更多的時間，但這反過來會在合理的時間內(nèi)產(chǎn)生更緊湊的CS（除YAGO外，大多數(shù)情況下，<為10 ms，YAGO中約為100 ms）。另一方面，擴(kuò)展的dag圖DP比Steady快三個數(shù)量級以上（因?yàn)槲覀兊倪^濾使用了三次細(xì)化，而Steady無限期地使用它們）。結(jié)果表明，VEQis的濾波方法足夠快，可以在實(shí)際應(yīng)用中使用，同時得到了接近Steady的大小。
查詢處理時間。圖20顯示了這些算法的平均查詢處理時間。格拉斯哥的DBLP和YAGO上的內(nèi)存不足。由于前面幾節(jié)中描述的三種主要技術(shù)，VEQM的性能通常優(yōu)于GQLfs和RIfs，其次是DAF、CFL-Match和格拉斯哥。特別是，VEQM在人類Q40S中比RIfs強(qiáng)三個數(shù)量級，在酵母Q50S、人類Q40S、Q40N和DBLP中比GQLfs強(qiáng)兩個數(shù)量級。在酵母、電子郵件、DBLP和Human的許多查詢集中，VEQM比CFL-Match和DAF快超過3個數(shù)量級。與VEQS不同的是，VEQM在一個數(shù)據(jù)圖中搜索多個嵌入，因此它可以通過使用等價集同時輸出大量的對稱嵌入。但是，由于在HPRD和Email的一些查詢集中，由于擴(kuò)展的HPRD圖DP的開銷和等價集的計算，VEQM的查詢處理時間略高于其他查詢處理時間。例如，HPRD體積小，有許多不同的標(biāo)簽，因此，HPRD的大多數(shù)查詢在100 ms內(nèi)完成，這意味著它們對于所有算法都是簡單的實(shí)例。
圖21展示了所有算法的查詢處理時間的分布（該分布比幾何平均值更能反映查詢之間的性能差距，因此這里只給出了該分布）。對于每個算法，它的查詢處理時間按升序排序，以便更快（或更容易）的查詢更早出現(xiàn)。對于酵母、電子郵件、DBLP和Human，VEQM在處理簡單查詢方面比CFL-Match和DAF花費(fèi)更多的時間，因?yàn)閂EQM在過濾和修剪方面有計算開銷；然而，VEQM在硬查詢方面比其他的性能更好。特別是在酵母和人類中，每個算法都以不同的百分比達(dá)到時間限制。CFL-Match首先達(dá)到時間限制，其次是格拉斯哥和DAF，而VEQM在最右邊的幾個查詢中幾乎沒有接近頂部，其次是運(yùn)行正常的GQLfs。此外，VEQM甚至沒有達(dá)到Email和DBLP的時間限制，即VEQM的查詢處理時間通常是穩(wěn)定的。對于簡單的數(shù)據(jù)集HPRD，DAF和CFL-Match對于大多數(shù)查詢比VEQM花費(fèi)更少的時間。相比之下，VEQM在查詢處理時間上通常是穩(wěn)定的，而對于硬查詢，其他算法的運(yùn)行時間會逐漸增加。在YAGO中，VEQM對于大多數(shù)查詢都是最快的。對于硬查詢，VEQM的運(yùn)行時間逐漸增加，而其他查詢的運(yùn)行時間則急劇增加。
由于我們在數(shù)據(jù)圖中找到了針對子圖匹配問題的大量嵌入，所以除HPRD外，所有數(shù)據(jù)集中的搜索時間所花費(fèi)的時間都遠(yuǎn)遠(yuǎn)超過預(yù)處理時間。在預(yù)處理搜索方法中，VEQM和GQLfs在搜索階段平均花費(fèi)68%的查詢處理時間，而RIfs、DAF和CFL-Match的查詢處理時間分別為72%、93%和96%。因此，我們獲得緊的候選集和減少搜索空間的策略得到了一種有效的子圖匹配算法。

7.4 Comparison with a workload-aware algorithm

我們在實(shí)驗(yàn)中比較了VEQM和WaSQ [25]。請注意，我們的工作和WaSQ解決了不同的問題。WaSQ解決了工作負(fù)載感知的子圖匹配，即給定一個查詢工作負(fù)載（一組查詢），WaSQ預(yù)先緩存工作負(fù)載的每個查詢的嵌入，然后給定一個新的查詢q，它重用查詢工作負(fù)載和緩存的嵌入來有效地找到q的嵌入。
圖22為WaSQ和VEQM的查詢處理時間。與我們工作中的其他實(shí)驗(yàn)一樣，我們?yōu)槊總€查詢設(shè)置了10分鐘的時間限制。由于WaSQ將一個查詢工作負(fù)載作為輸入，因此我們?yōu)榘?00個查詢的每個查詢工作負(fù)載，將WaSQ的時間限制設(shè)置為1000分鐘。圖中的空條表示W(wǎng)aSQ沒有在時間限制內(nèi)完成。盡管WaSQ重用了以前的查詢結(jié)果，而VEQ沒有重用，但在大多數(shù)情況下，VEQM的性能都優(yōu)于WaSQ或可以與WaSQ相當(dāng)。
現(xiàn)代圖查詢處理系統(tǒng)建立給定數(shù)據(jù)圖的數(shù)據(jù)庫，以有效地找到圖24EmptyHeaded和VEQM的查詢處理時間。x軸上的T、L、B分別表示三角形、棒棒糖、杠鈴查詢，例如，THPRD表示HPRD固定模式中的三角形查詢。有些系統(tǒng)是專門為SPARQL查詢或批處理查詢而設(shè)計的。因此，我們的方法可以應(yīng)用于圖形處理系統(tǒng)以兩種方式： (1)信息（例如，鄰居標(biāo)簽頻率或特定子結(jié)構(gòu)如三角形）發(fā)現(xiàn)數(shù)據(jù)圖可以計算和存儲之前查詢圖，和(2)我們的方法可以擴(kuò)展到多個查詢處理或RDF查詢處理。

7.5 Comparison with join-based algorithms

在本小節(jié)中，我們將VEQM與現(xiàn)有的基于連接的子圖查詢引擎進(jìn)行比較，如經(jīng)驗(yàn)[1]、圖形流[29]和快速匹配[42]。這些算法來自于DBMS中的連接操作，因?yàn)橐粋€多路自然連接可以用一個圖來表示，其中一個屬性和一個關(guān)系分別對應(yīng)于一個頂點(diǎn)和一條邊。經(jīng)驗(yàn)頭、圖形流和快速匹配的源代碼可以在GitHub上公開獲得。
圖23顯示了圖形流、快速匹配(H)（用于查找同態(tài)的快速匹配）、快速匹配(E)（用于查找嵌入的快速匹配）和VEQM的查詢處理時間。圖流不包含在HPRD和YAGO的結(jié)果中，因此圖流不能生成子圖目錄。總的來說，VEQM的性能優(yōu)于其他的，而且它在大型圖形中擴(kuò)展得很好。在酵母中，VEQM的表現(xiàn)一直優(yōu)于其他的。在人類實(shí)驗(yàn)中，VEQM始終領(lǐng)先于執(zhí)行圖形流和快速匹配(E)。在電子郵件、DBLP和YAGO中，VEQM在大型查詢方面的性能優(yōu)于其他VEQM。對于除酵母之外的數(shù)據(jù)集上的一些小查詢，RapidMatch (H)通常比VEQM表現(xiàn)得更好，因?yàn)镽apidMatch (H)搜索的同態(tài)與嵌入不同，不一定是內(nèi)射的(見第二節(jié)。2)，因此，RapidMatch (H)可能比搜索嵌入的VEQM需要更小的搜索空間來發(fā)現(xiàn)一個小的（或簡單的）查詢圖的前105個匹配項(xiàng)。
圖24顯示了“經(jīng)驗(yàn)”和“VEQM的查詢處理時間。由于經(jīng)驗(yàn)在碼頭容器中運(yùn)行，VEQ也在同一容器中進(jìn)行了實(shí)驗(yàn)。empty頭沒有針對大型復(fù)雜圖查詢[1]進(jìn)行優(yōu)化，因此我們使用了[1]中使用的三個代表性查詢（即三角形、棒棒糖和杠鈴查詢），這些查詢可以通過經(jīng)驗(yàn)頭的最壞情況最優(yōu)連接有效地處理。x軸上的T、L和B分別表示三角形、棒棒糖和杠鈴查詢，例如，THPRD表示對HPRD的三角形查詢。在這里，我們運(yùn)行VEQM來查找查詢圖的所有嵌入。在大多數(shù)情況下，VEQM比經(jīng)驗(yàn)占用的查詢處理時間更少。

7.6 Effectiveness of individual techniques

在本小節(jié)中，我們將評估單個技術(shù)在減少總體查詢處理時間方面的有效性。我們運(yùn)行DAF和以下算法的變體來衡量每種技術(shù)所獲得的性能增益：
-DAF：用于比較的基線。
–VEQS-NS：采用簡單的dag圖DP進(jìn)行過濾，基于靜態(tài)等價進(jìn)行匹配順序，通過動態(tài)等價進(jìn)行運(yùn)行時剪枝。
–VEQM-SEQ-DEQ：在濾波中使用具有鄰域安全性的擴(kuò)展DAG-圖DP，在回溯中使用DAF的自適應(yīng)匹配順序。
–VEQM-DEQ：使用擴(kuò)展的dag圖DP和基于靜態(tài)等價的匹配順序。
-VEQS和VEQM：利用擴(kuò)展的dag圖DP，建立基于靜態(tài)等價的匹配順序，并通過動態(tài)等價進(jìn)行運(yùn)行時剪枝。
圖25顯示了這些算法對子圖匹配的查詢處理時間。
鄰居安全的有效性。對于子圖匹配問題，VEQM-SEQ-DEQ將酵母的Q50S、電子郵件的Q40S Q30N和酵母的Q100N的DAFM提高了兩個數(shù)量級。我們計算每個查詢圖q的最大mq=maxu∈V(q)，l∈|Nbrq（u，l）|。性能提高最大的前10個查詢圖的平均mq遠(yuǎn)遠(yuǎn)大于所有查詢。也就是說，當(dāng)查詢圖中存在具有更多具有相同標(biāo)簽的鄰居的頂點(diǎn)時，性能增益更大，因?yàn)猷従影踩珬l件可以利用該查詢頂點(diǎn)過濾出該頂點(diǎn)的不合格候選項(xiàng)。對于子圖搜索，VEQS在IMDB和REDDIT上將VEQS-NS提高了兩個數(shù)量級，PPI和合作顯示了顯著的性能提高，盡管鄰居安全過濾略微增加了PDBS和PCM上的查詢處理時間（見圖26）。注意，VEQS-NS表示的算法與VEQS完全相同，只是鄰居安全過濾被關(guān)閉。我們觀察到，是否打開鄰居安全濾波會導(dǎo)致濾波時間與驗(yàn)證時間之比的波動。表5給出了VEQS和VEQS-NS的過濾時間與驗(yàn)證時間的平均比值。顯然，VEQS始終比VEQS-NS在過濾上花費(fèi)更多的部分查詢處理時間。特別是，PPI，IMDB，和合作，其中的算法花費(fèi)最多的時間在驗(yàn)證上，受益于鄰居安全過濾，因?yàn)檫@種技術(shù)有助于大大減少驗(yàn)證的部分時間。
應(yīng)用鄰居安全條件可持續(xù)降低假陽性比，如圖所示。12和16，同時略微增加了過濾時間，如圖19所示。在這里，DAF的濾波方法與VEQSNS相同。
基于靜態(tài)等價性的匹配順序的有效性。VEQM-DEQ按照我們的匹配順序考慮所有查詢頂點(diǎn)，而VEQM-SEQ-DEQ只按照DAF的匹配順序考慮非一次查詢頂點(diǎn)。VEQM-DEQ在酵母的Q50N、Q150N、Q200N和電子郵件的Q30S方面的性能比VEQM-SEQ-DEQ高出兩個數(shù)量級。這兩種方法之間的性能差距可能會增加，特別是當(dāng)存在一級查詢頂點(diǎn)具有與非一級查詢頂點(diǎn)相同的標(biāo)簽時。
利用動態(tài)等效法實(shí)現(xiàn)運(yùn)行時剪枝的有效性。修剪搜索樹的等效子樹可以帶來很大的性能提高，特別是在圖25的YAGO中。在這些數(shù)據(jù)圖上，CS中通常有更多的鄰域等價的候選細(xì)胞，導(dǎo)致許多或大的細(xì)胞是剪枝能力的潛在來源。剪枝技術(shù)的有效性是以計算單元格和等價集的額外開銷為代價而獲得的，因此處理一些查詢圖的時間略有增加。搜索空間的大小。為了證明我們的技術(shù)的有效性，我們測量了搜索樹中的節(jié)點(diǎn)數(shù)，這表明了搜索空間的大小(圖。27日和28日)。我們比較了DAF匹配順序的搜索樹節(jié)點(diǎn)數(shù)量和新匹配順序的搜索樹節(jié)點(diǎn)數(shù)量（兩種方法都關(guān)閉運(yùn)行時剪枝，只評估匹配順序的性能）。在這個圖中，VEQ-SEQ-DEQ和VEQ-DEQ分別代表發(fā)送DAF和VEQ的匹配順序。表6給出了新的匹配順序（即（大?。╒EQ-SEQ-DEQ）-大?。╒EQ-Deq））/大小（VEQ-SEQDEQ））降低的比率，對于酵母的稀疏查詢和PPI的隨機(jī)游走查詢（比BFS查詢稀疏）的比例特別高。也就是說，新的匹配順序更利用了稀疏查詢圖，這些圖可能有更多的稀疏頂點(diǎn)。
我們還比較了圖28中沒有運(yùn)行時剪枝的算法和有運(yùn)行時剪枝的算法之間的搜索空間大小的差異。當(dāng)動態(tài)等價性開啟時，搜索空間的大小就會持續(xù)變小。表7顯示了動態(tài)等價（即（大?。╒EQ-DEQ）-大?。╒EQ））/大?。╒EQ-DEQ）)的修剪比率，這在大多數(shù)情況下非常高。一般來說，修剪后的比率會隨著查詢圖的大小的增長而增加。
基于靜態(tài)等價性的匹配階數(shù)的統(tǒng)計分析。我們的匹配順序通過利用兩種情況減少了搜索空間，即(1)|NEC (u)| > |UM (u)|和(2) |NEC (u)|=|UM (u)|。 5.NEC不需要是非單例才能進(jìn)行修剪；如果一個單例NEC沒有候選頂點(diǎn)（例如，當(dāng)|NEC (u)| = 1和|UM (u)| = 0）時，我們將回溯。
我們計算了這些情況的數(shù)量，并測量了基于靜態(tài)等價的匹配順序所減少的搜索空間的大小（在表6中，在許多情況下所減少的比例相當(dāng)高）。進(jìn)一步分析，表8總結(jié)了匹配的匹配和效果的可能性，在符號“>”和“=”表示比率（單位： %）的數(shù)量可擴(kuò)展的頂點(diǎn)u|NEC(u)|>|嗯(u)|和|NEC(u)|=|嗯(u)|，分別在所有可擴(kuò)展的頂點(diǎn)u∈V (q)搜索樹?！癊lse”表示剩余的可擴(kuò)展頂點(diǎn)的比率。請注意，在大多數(shù)情況下，||(u)|=|UM(u)|比|NEC (u)| > |UM (u)|發(fā)生的頻率更高。
當(dāng)|NEC(u)|≥|UM(u)|用“#減少/seq”表示時，每個可擴(kuò)展頂點(diǎn)u減少的搜索樹節(jié)點(diǎn)的平均數(shù)量。盡管|NEC (u)|≥|UM (u)|的比例很小，因?yàn)檫@只發(fā)生在1度頂點(diǎn)上，但#減少/seq在許多情況下是很大的，這導(dǎo)致了表2中相對較高的減少比率。請注意，稀疏查詢上的#簡化/seq高于非稀疏查詢，因?yàn)橄∈璨樵儓D通常有更多的1次頂點(diǎn)。
利用動態(tài)等效法對運(yùn)行時剪枝的統(tǒng)計分析。以前，表7給出了在大多數(shù)情況下具有高修剪比率的修剪搜索空間的大小。為了進(jìn)一步分析，我們計算在回溯中發(fā)生的運(yùn)行時等價的數(shù)量，以衡量等價的可能性。表9總結(jié)了可能性，其中“負(fù)”和“正”表示未映射可擴(kuò)展候選與∈CM (u)的比率第1節(jié)第5號定義的第一個條件和第二個條件。在搜索樹中訪問過的所有未映射的可擴(kuò)展候選對象中的6個?！癊lse”表示剩余未映射的可擴(kuò)展候選節(jié)點(diǎn)的比例，“#修剪/deq”是指每個負(fù)v或正v所修剪的搜索樹節(jié)點(diǎn)的數(shù)量。
一般來說，未映射的v∈CM (u)上的運(yùn)行時等價更有可能發(fā)生在更大或更密集的查詢圖上。表9中相對較高的比率，+陰性陽性病例加上較高的#修剪/deq，導(dǎo)致表7中非常高的修剪比率。與DBLP上的子圖匹配不同，合作上的子圖搜索的正比為零，我們最多找到一個嵌入。因此，我們可以在子圖匹配中充分利用動態(tài)等價性。
表10給出了表9的查詢圖的核心結(jié)構(gòu)[3,41]的動態(tài)等價的可能性和影響。這里，核心結(jié)構(gòu)作為表9實(shí)驗(yàn)的輸入。對于DBLP的小查詢（Q10S、Q20S、Q10N、Q20N），“正”所占的百分比高于表9，這表明核心結(jié)構(gòu)中的頂點(diǎn)更有可能成為正單元格。對于DBLP的大型查詢（Q30S、Q40S、Q30N、Q40N），“積極”所占的比例較低。對于與表9不同的每個協(xié)作查詢集，“Else”案例超過80%。同時，對于隨機(jī)游走查詢集，搜索樹節(jié)點(diǎn)的數(shù)量修剪陽性比表9的大兩到三個數(shù)量級，這表明隨機(jī)游走查詢中的核心頂點(diǎn)可以通過使用負(fù)單元格比非核心頂點(diǎn)修剪更多的搜索空間。
單元格的大小和等價性集。一個單元格中的候選頂點(diǎn)在CS中必須具有相同的鄰居，并且一個等價集必須是該單元格的一個子集。那么一個單元格或一個等價集在真實(shí)數(shù)據(jù)集中通常包含多少個頂點(diǎn)呢？為了回答這個問題，我們測量了在COLLAB和DBLP上的所有查詢的不同單元格和不同的等價集的大小。對于合作，一個單元格和一個等價集的平均大小分別為2.12和3.23。對于DBLP，其大小分別為1.62和3.74。一個等價集的平均大小大于一個單元格的平均大小，因?yàn)橐粋€大單元格的許多不同的子集變成了等價集大小范圍為2-10，這是等價集的大小中的大多數(shù)，而1是大多數(shù)大小的細(xì)胞。表11證實(shí)了這一現(xiàn)象，表11顯示了細(xì)胞和等價集的分布。在COLLAB和DBLP中，超過70%的細(xì)胞的大小為1，而超過80%的等效集的大小在2到10之間，我們可以在運(yùn)行時剪枝方法中利用這一點(diǎn)。一個尺寸出現(xiàn)的頻率通常會隨著尺寸的增加而減小。特別是，1.03×10?6%的細(xì)胞（即一個細(xì)胞）在51-60大小范圍內(nèi)，1.45×10?8%的等效細(xì)胞（即3個細(xì)胞）大小在51-60之間，這種情況很少發(fā)生。

7.7 Varying degree of query graphs

我們對頂點(diǎn)數(shù)相同但平均度不同的查詢圖進(jìn)行了性能研究。圖29顯示了不同程度的查詢圖的查詢處理時間。我們從每個數(shù)據(jù)圖中提取查詢圖。稀疏、中等和密集查詢圖的平均度≤分別為3，在3到6之間，≥為6。在酵母中，查詢處理時間隨著度的增加而減少，但在其他數(shù)據(jù)集中，查詢處理時間對度相當(dāng)不敏感，這在圖25中也可以看出。

8 Conclusion

為了加快子圖的搜索和子圖的匹配速度，我們引入了通用的等價性： (i)查詢頂點(diǎn)的等價性；以及（ii）候選數(shù)據(jù)頂點(diǎn)的等價性。在前者中，我們將查詢頂點(diǎn)的靜態(tài)等價性應(yīng)用于回溯的匹配順序。在后者中，我們使用候選頂點(diǎn)的鄰域等價性來獲得搜索樹的子樹之間的動態(tài)等價性，以便在回溯過程中剔除這些冗余的子樹。我們還提出了一種通過擴(kuò)展的dag圖DP的鄰居安全濾波技術(shù)。這三種技術(shù)改進(jìn)了子圖搜索和子圖匹配的算法。大量的實(shí)驗(yàn)表明，我們的算法在子圖搜索或子圖匹配方面比最先進(jìn)的算法要多出一個數(shù)量級。
我們的方法可以應(yīng)用于有向圖。假設(shè)我們給定一個有向查詢圖q和有向數(shù)據(jù)圖g然后我們認(rèn)為有向查詢圖作為無向圖，我們建立一個查詢，每條邊貼上1如果方向新分配的DAG匹配方向輸入查詢圖；否則0。在查詢DAG中，從一條邊（u，v）中，如果x為1，我們得到一條有向邊（u，v）；如果x為0，則為一條有向邊（v，u）。
本文中的算法已經(jīng)處理了一般的無向圖（包括無向循環(huán)）作為輸入。因此，它可以通過上述變換來處理循環(huán)有向圖。文章來源地址http://www.zghlxwxcb.cn/news/detail-774250.html

到了這里，關(guān)于【論文閱讀】Fast subgraph query processing and subgraph matching via static and dynamic equivalences的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！