融合啟發式和Boosting 的子圖匹配基數估計方法

侯文哲，趙 翔

國防科技大學 信息系統工程重點實驗室，長沙410000

隨著網絡大數據的迅速發展，社交關系、知識表示等領域大放異彩。圖數據庫作為一種描述關系數據的天然模型，已成為當前海量網絡數據管理的解決范式。因此，圖數據管理技術也成為當前的研究熱點。近年，以子圖匹配為代表的圖數據上基礎操作的性能得到了巨大提升。但是，一個完善的高吞吐的圖數據庫系統還應具備自適應的任務調度能力；為了實現這個目標，圖數據庫系統需要對系統中的任務進行代價估計——特別是對中間結果基數的盡可能準確估計，從而優化多任務執行的序列與配置。本研究以子圖匹配任務為例，研究針對該任務的基數估計的有效方法。

子圖匹配是圖數據庫管理、查詢等各項工作中的基礎操作。為提高子圖匹配操作的執行效率，現有研究對其執行過程進行了有效的剪枝、索引構建等優化，但精確的子圖匹配問題仍然是一個NP 完全問題，隨著待匹配結點的增多，匹配將難以在有效的時間內完成。若能在匹配執行之前就能夠盡可能準確地估算匹配結果的基數，便可幫助實現對匹配執行過程和多個匹配任務的整體優化，對于提升圖數據庫管理系統的效率和吞吐量意義重大。

當前，在關系型數據庫管理系統領域，學者已經提出一些機器學習的方法和傳統的非機器學習方法來對查詢結果的數據庫查詢任務的基數進行預測，而這些方法往往基于數據庫的連接過程，無法直接應用到以圖為結構的圖數據庫匹配的基數估計工作中。另一方面，現有的用于子圖匹配基數估計的部分研究依賴于離線統計的方法，無法充分利用圖數據中的結構信息，且沒有一個適用于多結點查詢圖匹配基數估計的框架。

鑒于此，本研究旨在設計一個通用方法來實現多結點查詢圖的預測框架，并通過對圖數據的結構信息建模、編碼，應用Boosting 學習的思想，實現魯棒的多結點子圖在大規模數據圖中匹配基數的預測工作。具體地，提出BoostCard 方法，它首先針對數據圖中結點的鄰居信息建模，將結點分類并構建相應索引，然后對不同類型結點之間能否連成一邊的概率進行預測，并基于上述信息，對多結點子圖的匹配基數進行預測，最后運用機器學習的方法對匹配結果的基數進行補償。

簡言之，文章的主要貢獻是將圖數據的結構信息建模到子圖匹配結果的基數估計工作中，并根據Boosting 學習思想，提出適用于多結點子圖的匹配結果預測方法（Boosting cardinality estimator，BoostCard）。

1 相關工作

在社交、電商、零售、物聯網等行業快速發展的Web 2.0 環境中，圖數據庫因為它的對聯系建模等天然優勢，彌補了傳統關系型數據庫在復雜關系運算方面的短板。對于圖數據庫，找到一種準確、有效的代價預測方法，將能夠實現數據管理系統的優化，提高執行效率。以代價估計為依據尋找最佳執行策略的方法已經在各大傳統關系型數據庫系統中得到應用。在圖數據庫的數據管理操作中，子圖同構查詢是重要的基礎查詢形式，也是數據管理的基礎操作，在實際執行查詢前，若能夠預先估計出這些基礎操作的查詢結果基數，也將極大地提升圖數據庫的查詢性能。然而，目前提出的方法普遍對圖數據庫的結構要求較為特化，還沒有一個泛用、完善的圖數據庫數據管理操作代價估計的解決方案。

1.1 子圖同構算法

子圖同構問題，簡單來說就是在給定的數據圖中查找與模式圖相同的子結構，一般分為精確匹配和近似匹配。本研究針對精確匹配展開討論，匹配過程中要求數據圖的匹配結果與模式圖完全一致。

圖）定義三元組(,,)表示一個圖，其中表示圖中結點的集合；表示邊的集合，∈×；是該圖的屬性映射函數，將邊或結點映射到一個或一組屬性。

（子圖匹配）已知數據圖=(,,)和模式圖=(V,E,L)，精確子圖匹配要求在模式圖和數據子圖=(,,)之間建立一個雙射函數：

如圖1，模式圖在數據圖中存在兩個匹配的子圖，即=[(,),(,),(,),(,)]和=[(,),(,),(,),(,)]。

圖1 精確匹配示例Fig.1 Sample of exact subisomorphism

從算法的角度，精確匹配分為無索引的匹配和基于索引的匹配，無索引的精確匹配利用圖中的語義和結構信息縮小匹配范圍。1976 年提出的Ullmann算法針對結點的度、映射規則、結點鄰接關系提出一系列剪枝規則，在小規模圖匹配問題中簡單有效。在Ullmann 算法的基礎上，Sansone 等人提出VF2 算法，通過標簽中的語義信息對匹配的預選集進行過濾，并通過預選結點在未匹配結點中的入度和出度進行一步預先判斷，進一步縮小了搜索空間。

近年來的改進算法將更復雜的路徑和子圖結構引入剪枝過程，進一步縮小了搜索空間，以實現更大規模的匹配問題求解。隨著圖數據規模的繼續擴大，基于索引的匹配技術應運而生，這些技術通過數據圖中的有效特征構建索引，能夠快速縮小子圖范圍，再基于備選子圖展開精確匹配。這些特征既能實現圖索引構建，又很大程度上表達了圖的結構信息，對包含圖數據的結構特征構建也能起到極大的幫助作用。

而在最終的匹配過程中，子圖匹配問題仍然是NP 完全問題（non-deterministic polynomial complete problem），在多項式的時間開銷內對匹配結果的基數進行粗略估計將為查詢操作的優化提供重要依據。

1.2 啟發式預測方法

圖數據庫系統進行查詢時使用連接運算擴大對圖中各邊的搜索和匹配。一些圖數據庫系統將預先加入索引的圖數據子模式作為基本單位進行連接。Maduko 等人針對上述過程，提出了一種圖數據摘要技術，并通過建立的圖數據摘要，使用有索引的頻繁子結構描述查詢子圖數據的特征，進行啟發式的查詢子圖基數估計。

對子圖匹配問題的代價預估技術，在資源描述框架中也已經提出了一系列可行的實現模型，但這些方法對圖數據的構成結構有較高的要求，解決問題較為特化，在所有結點均表示一個實體的非資源描述框架的圖數據中難以達到預期,不能實現普通圖數據庫的匹配代價預測。

針對上述問題，Paradies 等人為非資源描述框架下的圖數據提出一種專門的子圖匹配基數估計的方法，該方法基于統計學理論，運用數據圖中的基礎統計數據預測兩結點及其相連的邊在單張大規模數據圖中的匹配結果的基數，并通過關系依賴使算法在多屬性圖的環境中更加穩定有效。但是方法只對兩個結點及其相連的邊有效，無法直接應用于存在多結點的完整模式圖匹配中。

1.3 關系型數據的智能化估計

近幾年來，很多學者為提升數據庫查詢性能預測的普適性，尤其是為解決存在復雜謂詞和連接時傳統方法誤差較大的問題，提出了一些基于深度學習的解決方案。Kipf 等人提出Learned Cardinalities方法，對數據庫表、連接操作、謂詞邏輯分別進行編碼，以實現數據庫查詢輸入的向量化轉化表示。

最新的結構化查詢語言（structured query language，SQL）查詢性能預測研究通過SQL 查詢執行計劃實現了更為靈活的端到端預測來適應各種不同結構的查詢。SQL 查詢語句可以通過執行優化器表示為查詢執行計劃的形式，它們將SQL 查詢細化成對數據庫系統中的原子性操作，并構建成樹狀結構來表示具體執行過程。

結合執行計劃的樹狀結構特點，一些學者通過構建相應的表示模型來執行逐級預測。Sun、Li 為執行計劃樹的結點構建一個結點表示網絡來預測到每個結點為止的開銷及基數，并作為高一級運算的輸入向上傳遞；對于有謂詞限定數據，該方法采取簡單的數理計算獲取預測值。Marcus 等人針對執行計劃中不同的操作構建不同輸入結構的神經網絡作為神經單元，并將這些神經單元依據查詢計劃的結構連接成樹，僅通過查詢計劃中的參數和低一級的預測結果作為輸入實現預測。

2 問題定義

定義2 引用了關于子圖匹配問題的定義，擬解決的問題是盡可能準確預測子圖匹配的基數。

（子圖匹配基數）對于給定的數據圖=(,,)以及模式圖=(V,E,L)，模式圖可能與的任意子圖=(,,)建立雙射函數滿足子圖匹配的要求，將所有滿足要求的函數集合記作F，該集合中元素的個數|F|即為數據圖與模式圖的子圖匹配基數。

在大規模的數據圖中，執行子圖匹配任務往往會面臨時空開銷大，無法在足夠短的時間內給出結果。本文研究子圖匹配基數的預測方法，輸入擬執行子圖匹配的模式圖與數據圖。在不進行實際的子圖匹配操作的前提下，輸出一個該組圖數據的子圖匹配基數的預測值。

3 BoostCard 方法

BoostCard 是一種在整張模式圖上游走，依經過的每一邊估計匹配結果基數的方法，這個過程中會利用對各個結點的局部結構信息生成對應的結點表示，并以此提高每一跳預測的準確度。在這一預測框架下，為了能夠實現對模式圖全局信息的掌握，預測補償機制以提升學習的形式加入到方法中，對結點的表示向量進行學習，獲得針對不同模式圖的補償強度來優化預測結果。

3.1 基本思路

模式圖對于數據圖的匹配過程被視為一個連接操作的執行過程。模式圖中的結點的匹配順序由深度優先遍歷產生：(,,,)，首先將中的結點分為兩個集合，即已匹配集V和待匹配集V。初始條件下，所有結點均于待匹配集V中，隨著未匹配的結點加入匹配，模式圖中的結點依匹配順序由待匹配集轉移到已匹配集中。如圖2 所示的子圖匹配過程中，在前三個結點已經完成匹配的情況下，V={,,}，V={}。匹配的過程可以看作模式圖的子圖在數據圖的約束下添加一個滿足條件的結點及其與中一點之間相連的邊，匹配完成后V={,,,}，V=?。

圖2 結構信息獲取Fig.2 Structural information acquirement

BoostCard的基本預測過程在算法1中給出描述。

預測框架

BoostCard 預測主要由四部分組成：結構索引、結點連接預測、多結點預測框架、預測補償器。

預測執行過程如下：（1）通過結構索引將數據圖中所有結點分類分組，并構建簡單索引實現快速訪問。（2）在構建的結構索引的基礎上，通過結點連接預測過程，對數據圖中任意兩類結點之間連成一邊的概率進行預測。（3）多結點預測器依照匹配過程，預測模式圖在數據圖中出現的次數，即匹配結果的基數。預測器對模式圖的子圖的匹配基數進行預測，并依照匹配順序添加新的待匹配結點以更新，直到所有中結點全部添加到中，此時所得到的預測結果即為模式圖的匹配基數估計值。（4）根據建立的結構索引，可以通過預測補償器獲取模式圖的統計向量表示作為依據，結合提升學習的思想對預測結果進行補償。

接下來，分別對模型的每個部分進行討論。

3.2 結構索引

結構索引的目的在于對數據圖中出現的結點的結構信息建模。這些結構信息主要基于每個結點及其相鄰的結點的屬性信息構建而成。

屬性映射函數將各結點的屬性映射到自然數集中：

:→

其中，為數據圖中屬性集，??，為自然數集的子集；∈，可作為結點屬性的唯一表示。

結構索引的構成由圖2（d）所示，對于數據圖中的結點v，其中，l∈，為結點v的整數映射，為表示v的鄰居結點信息的二值向量：

對于數據圖的結點v，若其存在屬性映射到整數集后取值為的鄰居，則取值為1，不存在上述鄰居結點則取值為0，在圖2（a）所示的數據圖中，結點的結構索引向量如圖2（e）所示。圖中結點和邊的屬性映射到整數域中，圖2（b）展示了經屬性映射的數據圖。結點自身的屬性映射為2，其鄰居結點含有被映射為0、1 的屬性；在圖示的數據圖中，結點屬性只有4 種取值，的長度為4。綜上，的結構索引向量中取值為2，為(1,1,0,0)。結構索引將數據圖中的各個結點的結構信息表示成一個標量與一個向量組成的元組作為結點v的結構標識d∈×{0,1}。擁有同樣結構標識的結點即被視為同種類型的結點。 D={∈|d=}表示有同一類結構標識的結點。

3.3 結點連接預測

結點連接預測的作用是針對數據圖，統計不同類型的結點之間能夠連成擁有某屬性的一邊的概率。

結點連接預測同樣將數據圖中的邊的屬性映射到整數集：

:→S

其中，分母表示數據圖中d類型的結點到d類型的結點可能的組合的個數；分子表示這些組合中兩點之間存在一條屬性映射到的邊的組合數。

至此，對于一個匹配查詢的模式圖，首先以兩結點及其間一邊構成的圖為例，將兩結點分別分類到對應的結點類型中，即可通過數據圖中這兩種結點的數目以及其間可連成一邊的概率預測匹配結果的基數。

如圖2（c）所示的模式圖中，結點對應數據圖的結構標識為(2,(0,1,0,0))，這與中結點的結構標識(2,(1,1,0,0))是不同的，然而模式圖顯然可以在數據圖中成功匹配。

預測乘子multiplier

匹配概率match_prob

輸入：數據圖中目標結點，模式圖中待匹配結點。

輸出：匹配到的概率。

3.4 多結點預測器

BoostCard 預測器根據匹配順序添加結點實現預測：

新加入的結點對于其所在模式圖的結構信息未必與數據圖中的對應結點完全相同，但是其結構信息卻可以以不同的概率對應到中不同種類的結點中。

其中，⊕為按位異或操作，兩個序列中對應位置的元素相同則取值為1，否則取值為0。

至此已實現了多結點模式圖的匹配基數估計。

3.5 預測補償

由于上述預測過程是一個使用預測值生成新的預測值的過程，未免會有誤差累積的問題。為了補償這種累計誤差，引入預測補償器實現模式圖的嵌入表示和累計誤差的補償，得到最終預測結果。

將定義為模式圖中所有結構標識的集合。對預測結果補償時，首先將模式圖嵌入表示為長度為||的向量：

由公式向量的每一個元素分別對應一個結構標識。

式中，∈[0,1]，為補償閾值，用以控制發生錯誤補償的情況，該值為超參數，取值越大，對錯誤補償的抑制越強。和為模型參數，下面通過訓練獲取對于特定數據圖的上述參數。

根據上述預測過程，能夠得到任意一組模式圖在給定數據圖中的匹配基數估計值。同時，也可以通過實際執行精確匹配來確定其真實的匹配基數。對于實際值大于預測值的模式圖，將其標簽標記為1，即M=1，對于實際值小于預測值的模式圖，將其標簽標記為-1，即M=-1。

其圖像如圖3 所示。

圖3 損失函數Fig.3 Loss function

4 實驗

BoostCard 方法主要應用于模式圖在單張大規模數據圖中的匹配結果基數的預測。本章展開實驗來評估BoostCard 方法對匹配基數的預測能力。

4.1 實驗內容

實驗采用經典的大規模圖數據Yeast 數據集、Human 數據集和Facebook 數據集以及使用graphGen工具人工生成的數據圖作為測試數據。在上述數據集中隨機生成結點數分別為2、3、4、5 以及10 的子圖作為匹配的查詢集。在本實驗中，所有生成的模式圖均為無環的樹狀圖。

對于獲取的數據集，采用VF2 算法執行匹配過程，記錄每組查詢圖在相應的數據圖中的匹配結果數作為匹配數據的真實值。在實際匹配的過程中，認為模式圖中結點的屬性應與數據圖中被匹配結點的屬性完全相同。

通過獲得的上述數據訓練BoostCard 預測模型。分別使用傳統的統計方法以及BoostCard 預測方法對數據的匹配結果進行預測，比較執行結果。

傳統統計方法通過式（10）計算結點的選擇度：

并通過式（9）計算一條邊在數據圖中的預測基數。

在多結點的預測過程中，預測按照結點游走的順序進行，每加入一個結點，將已經預測的部分看作一個新的結點，與下一個待匹配結點形成一個新的短路徑，直到所有結點完成匹配。該方法將作為本文的基準方法。

將每組模式圖隨機分為5 組，進行五折交叉驗證，并取平均值作為一次實驗結果，實驗重復5 次，得到5 組結果，最終輸出5 次實驗結果的平均值。為了在訓練及預測中，使輸出值更加均勻，對匹配基數做對數處理，這樣也更能表現匹配基數的數量級。接下來，將每個查詢結果對應的數據圖與模式圖作為預測模型的輸入，執行匹配基數估計。

為了評估預測的準確度，實驗采用兩個評價指標：平均平方誤差()、決定系數()。決定系數通常用來衡量回歸任務的擬合程度。其計算方式如式（12）所示，越大，表示模型的擬合程度越強。當值為負時，表示模型無法解釋擬合中的變異，即模型不適用于相應數據的擬合，實驗中以“—”表示。

4.2 實驗結果

通過預測結果與匹配實際值的對數均方誤差評估預測的準確率。預測值如表1 所示，由圖4給出。在結點較多的情況下，由于匹配基數的增大，匹配結果真值的方差隨之增大，通過進行評估反映得預測準確度的精度會有所下降，但由于同一組實驗中的不同方法采用的是相同的數據集，值的大小仍可用以比較兩種方法的準確度。在給定的數據集中，傳統預測方法在僅有兩個結點的模式圖中優于BoostCard 方法，其主要原因是BoostCard 方法中的結構索引等結構信息對單邊的預測會造成一定的影響，對統計信息直接應用的傳統方法在單邊預測的情況下反而更加準確。但是，在傳統的方法中，隨著結點數的增加，預測結果的分布很快變得不可控，在超過3 個結點的查詢集中甚至出現值為負的情況，預測結果與實際值難以成正線性關系，難以滿足實際需求，而在一定的范圍內，BoostCard 方法在多結點數據中仍能提供較穩定的估計值。

表1 預測r2 值Table 1 Estimated r2 values

圖4 估計均方誤差Fig.4 Estimation of mean-square error

4.3 預測補償準確率

本節通過調整閾值對預測補償器的執行效果進行評估。在BoostCard 預測方法中，在進行初步的基于概率的技術預測后，模型會通過機器學習方法對結果進行補償性預測，如3.5 節所述，這個過程可以看作一個分類問題。當實際值大于初步預測值時，預測補償因子＞0，反之，＜0。為了避免錯誤方向的補償，采用閾值來限制補償的執行。當且僅當預測補償因子的絕對值||＞時，執行預測補償。

實驗針對Human 及Facebook 數據集展開，研究的不同取值對正確執行補償的影響，通過設置不同的值研究補償結果。在實驗中，如下定義準確率（）并以此為評估依據：

評估結果如表2 所示。

表2 預測補償器準確率Table 2 Accuracy of estimation compensation

圖5 展示了Human 數據集中，對含有5 個結點的模式圖集進行預測時，準確率與執行率隨閾值取值變化的影響。圖像顯示，隨著增大補償預測的準確率有所升高，但是可執行的補償越來越少。閾值減小，將允許更多的預測結果執行預測補償，但有可能導致最終預測更加偏離真實值。

圖5 預測補償準確率與正確執行數Fig.5 Accuracy and recall of estimation compensation

5 結束語

子圖匹配的基數估計任務在圖數據相關領域的研究工作，尤其是圖數據庫執行效率優化方面發揮著重要作用。本文從統計學的角度結合集成學習的思想對圖數據中的結構鄰域信息進行建模并實現子圖匹配基數的預測。文章提出的BoostCard 方法能夠運用圖數據中結點鄰域的結構信息來提升預測過程的拓撲信息的利用率，在結點數目有限的模式圖中給出較高的預測準確度，實現了一種通用的匹配基數估計架構。為了提高預測模型對全局信息的應用，BoostCard 方法通過全局的結構索引信息對預測結果進行進一步補償，并提供一個可調節的閾值控制補償力度，以應對不同特征的數據集。相對于傳統的預測方法，BoostCard 方法能夠在結點較多的模式圖的匹配任務中實現更加穩定的表現。

BoostCard 方法同樣可以應用到各種索引編碼中，以表示模式圖中更加豐富、細化的結構特征。文章采取的結構索引實質上相當于一個星形特征的索引，現有的子圖匹配索引技術提供了鏈狀、樹狀、環狀等多種結構特征。這些結構特征將為提升學習提供更全面的學習依據，這也是未來工作中有待進一步考慮的問題。