圖數據庫 | 24、如何進行正確性驗證？

圖數據庫計算和查詢結果的正確性，這個重要性當然是不言而喻的！

老夫之前也寫文章講過，今天再手書一篇，旨在向大家系統地介紹一下圖數據庫查詢與計算到底如何進行正確性驗證！！！

圖數據庫中的操作分為以下2類：

·?面向元數據的操作：即面向頂點、邊或它們之上的屬性字段的操作，具體可以分為增、刪、改、查4類。

·??面向高維數據的操作：這也是本書關注的重點，例如面向全圖或子圖數據的查詢結果返回多個頂點、邊組合而成的高維數據結構，可能是多頂點的集合、點邊構成的路徑、子圖（子網）甚至是全圖遍歷結果。

面向高維數據的查詢有以下3類:

·?K鄰查詢：即返回某頂點的全部K度（跳）鄰居頂點集合。K鄰查詢可以有很多變種，包括按照某個特定方向、點邊屬性字段進行過濾。還有全圖K鄰查詢，也被視作一種高計算復雜度的圖算法。

·?路徑查詢：常見的有最短路徑、模板路徑、環路路徑、組網查詢、自動展開查詢等。

·?圖算法：圖算法在本質上是面向元數據、K鄰、路徑等查詢方式的組合。

無論以何種方式進行高維查詢，圖數據庫中的操作無外乎遵循如下3種遍歷模式:

·?廣度優先：如K鄰查詢、最短路徑等。·深度優先：如環路查詢、組網查詢、模板路徑查詢、圖嵌入隨機游走等。

·?深度優先與廣度優先兼而有之：以最短路徑方式遍歷的模板路徑或組網查詢、帶方向或條件過濾的模板K鄰查詢、定制化的圖算法等。

注意：
面向元數據的圖數據庫操作和關系型數據庫有相似的地方，正確性驗證方法在此就不再贅述了。本文老夫著重介紹圖數據庫特有的高維數據查詢正確性驗證。

我們以圖數據庫基準性能評測中常用的Twitter-2010數據集為例來說明如何進行圖查詢的正確性驗證。

Twitter數據集（其中頂點數量為4200萬，邊數量為14.7億，原始數據占24.6GB）的下載鏈接為：http://an.kaist.ac.kr/traces/WWW2010.html。

在開始驗證前，以Twitter數據集為例，了解一下圖數據模型的特征。

（1）有向圖

由頂點（人）和邊（關注關系）組成，其中關注關系為有向邊。

Twitter源數據中有兩列，對應每一行是由Tab鍵分隔的兩個數字，例如12與13，代表兩個用戶的ID，表示兩者間的有向的關注關系：12關注13。在圖數據建模中應該構建為兩條邊，一條表示從12到13的正向邊，另一條則是從13到12的反向邊，缺一不可。后面的驗證細節中很多正確性的問題都與此相關——沒有構建反向邊，查詢結果不可避免會出錯。

（2）簡單圖與多邊圖

如果一對頂點間存在超過（含）2條邊，則其為多邊圖，否則為簡單圖。

在簡單圖中任意頂點間最多只有1條邊，因此簡單圖也稱作“單邊圖”?。

Twitter數據實際上是一種特殊的多邊圖，當兩個用戶互相關注對方時，他們之間可以形成兩條邊。在金融場景中，如果用戶賬戶為頂點，轉賬交易為邊，那么兩個賬戶之間可以存在多筆轉賬關系，即多條邊。

很多系統只能支持簡單的單邊圖，這樣就會帶來很多圖上查詢與計算的結果錯誤的問題。

（3）點、邊屬性

Twitter數據本身除了隱含的邊的方向可以作為一種特殊的邊屬性外，并不存在其他點邊屬性。這個特征區別于金融行業中的交易流水圖——無論是頂點還是邊都可能存在多個屬性，可以被用來對實體或關系進行精準的查詢過濾、篩選、排序、聚合運算、下鉆、歸因分析等。不支持點邊屬性過濾的圖數據庫可以認為功能沒有實現閉環，也不具備商業化價值。

我們以K鄰查詢為例來驗證圖數據庫查詢結果的正確性！！

首先，我們要明確K鄰查詢的定義，事實上K-Hop查詢有兩種含義，分別是：第K度（跳）鄰居、從第1跳到第K跳的全部鄰居。

其中第K跳鄰居指的是全部距離原點最短路徑距離為K的鄰居數量。這兩種含義的區別僅僅在于到底K-Hop的鄰居是只包含當前步幅（跳、層）的鄰居，還是包含前面所有層的鄰居。無論是哪種定義，有兩個要點直接影響“正確性”?：

·?K鄰查詢的正確實現方式默認應基于廣度優先搜索。

·?結果集去重：即第K層的鄰居集合中不會有重復的頂點，也不會有在其他層出現的鄰居（已知的多款圖數據庫系統都存在數據結果沒有去重的錯誤）?。

有的圖數據庫（或圖計算引擎）會用深度優先搜索（DFS）方式，通過窮舉全部可能的深度為K跳的路徑來試圖找到全部路徑和最終能抵達的終點。但是，DFS方式實現K鄰查詢有2個致命的缺點:

·效率低下：在體量稍大的圖中，不可能遍歷完全，例如Twitter數據集中常見的有超過百萬鄰居的頂點，如果以深度遍歷，復雜度是天文數字級的（百萬的11次方以上）?；

·結果大概率錯誤：即便是可以通過DFS完成遍歷，也沒有對結果進行分層，即無法判斷某個鄰居到底是位于第1跳還是第N跳。

我們先從驗證1度（1跳）鄰居開始，以Twitter數據集的頂點27960125為例。在源數據集中，如圖1所示，返回了8行（對應圖數據庫中的8條邊）?，但是它的1度鄰居到底是幾個呢？

正確答案是7個，注意圖1中頂點27960125的一個鄰居27498091出現了2次，它們之間存在兩條相互的關系（對應源數據集中的2行）?。但是作為去重后的1度鄰居集合，只有7個。

在圖2中，我們以無向圖（即雙向邊遍歷）的方式對頂點27960125進行1度鄰居查詢，得到全部鄰居頂點為7個。

為了更精準地驗證結果正確性，對K鄰查詢還可以按照邊的方向來進行過濾，例如只查詢頂點2796015的出邊、入邊或雙向邊（默認是查詢雙向邊關聯的全部鄰居）?。圖3展示了如何通過圖查詢語言來完成相應的工作。注意，該頂點有6條出邊對應的1跳鄰居、2條入邊對應的1跳鄰居，其中有1個鄰居27498091是重疊的。

如果參考美國圖數據庫廠家Tigergraph在Github網站上公開的性能測試結果數據文件，其K鄰查詢的結果存在明顯的錯誤，例如圖7-14中頂點27960125的1-Hop結果僅返回6個鄰居。

Tigergraph的查詢結果錯誤有3個可能，并且具有典型性。

·構圖錯誤：只存儲了單向邊，沒有存儲反向邊，無法進行反向邊遍歷；

·查詢方式錯誤：只進行了單向查詢，沒有進行雙向遍歷查詢；

·圖查詢代碼實現錯誤：即沒有對結果進行有效的去重，這個在多跳K-Hop查詢中再繼續分析。

其中，構圖錯誤代表數據建模錯誤，這意味著業務邏輯不能在數據建模層面被準確反映。例如在反欺詐、反洗錢場景中，賬戶A收到了一筆來自賬戶B的轉賬，但是卻因為沒有存儲一條從A至B的反向邊而無法追蹤該筆交易，這顯然是不能容忍的。

查詢方式和查詢代碼邏輯錯誤同樣也會對結果造成嚴重影響——每一跳查詢雙向邊，在多跳情況下查詢復雜度指數級高于單向邊查詢，這也意味著Tigergraph如果正確地實現圖數據建模、存儲與查詢，其性能會指數級降低，并且存儲空間的占用也會成倍增加（存儲正向和反向邊的數據結構要比僅存儲單向邊復雜2倍以上）?，數據加載時間也會成倍增加。

如果我們繼續追溯頂點27960125的2-Hop結果集，就會發現結果的錯誤更加隱蔽，例如Tigergraph的2-Hop實際上僅僅返回了沿出邊遍歷的第2度鄰居結果（圖5）?，并且沒有對結果去重。其第2度鄰居數1128中含有重復的頂點，按照只進行出邊查詢得到的去重結果應該是1127——但是2-Hop的正確結果應該是533108（圖6）?，這兩者間有473倍的差異，即47300%的誤差！在2-Hop的結果中，就可以看到Tigergraph的查詢結果同時存在以上所述的3種錯誤——構圖錯誤、查詢方式錯誤、結果未去重錯誤。

圖5 :Tigergraph僅進行單向遍歷的錯誤的2-Hop結果（Github）

遺憾的是，類似的查詢結果錯誤問題在今天的圖數據庫市場并不是個例，我們在Neo4j、ArangoDB等系統中也發現因底層算法實現或接口調用等問題而出現的錯誤。

更為遺憾的是，有多個廠家的“自研圖數據庫”實際上是對Neo4j社區版或ArangoDB的封裝，姑且不論這么操作是否涉嫌違規商用，暴力封裝幾乎注定了它們的查詢結果也是錯誤的。例如Neo4j默認并不對K鄰查詢結果集進行去重，而一旦開啟去重，它的運行效率會指數級下降；而ArangoDB有一種最短路徑查詢模式，只返回一條路徑，這種模式本身就是對最短路徑的錯誤理解與實現。

圖數據庫配套的可視化工具可以幫助我們更直觀、便捷地查詢結果的正確性。

上面介紹了圖上的基礎查詢K鄰查詢的正確性驗證方法，以及可能出現的錯誤情形。還有很多其他圖操作同樣也涉及結果錯誤的問題，但是都能通過一些基礎的方法來驗證。下面再舉2個有代表性的例子：最短路徑和圖算法。

最短路徑可以看作K鄰查詢的一個自然延展，區別在于它需要返回的結果有2個特征：

·高維結果：最短路徑需要返回多條由頂點、邊按遍歷順序組合而成的路徑；

·全部路徑：任意兩個頂點間可能存在多條最短路徑，如果是轉賬網絡、反洗錢網絡、歸因分析等查詢，只計算一條路徑顯然是無法反映全貌的。

以Twitter數據集中的頂點12、13之間的最短路徑為例，它們之間存在兩條最短路徑（圖7）?，其中一條由12指向13，另一條由13指向12（圖8）?，這個在源數據中也可以通過grep操作得到快速驗證。在更復雜（更深度）的查詢中，可以用類似的邏輯，通過層層的抽絲剝繭來驗證結果的正確性。