1.1.2 由一道面試題引發的思考

在現實生活中，絕大多數人具備圖的思維方式嗎？我們來看看下面這個問題：構造一張圖（由頂點、邊構成），使圖里包含5個三角形，且只再增加1條邊就能讓三角形的個數增加為10。

補充信息：這張圖中，頂點代表賬戶，邊代表賬戶間的轉賬交易，賬戶間可以有多筆交易。所謂的三角形就是由3個賬戶間的交易形成的原子級三角形，原子級是指三角形不可嵌套，三角形的每條邊都是不可分割的，也就是說，1條邊僅對應1筆轉賬交易。

我們來分析一下這個題目的關鍵：只增加1條邊，三角形卻要增加5個。也就是說，先前有5個三角形，它們若能共用1條邊，那么再增加1條這樣的邊，就會形成5個新的三角形，而共用1條邊也意味著這5個三角形也會共用2個頂點。分析至此，答案是不是呼之欲出了？

這是筆者從真實的業務場景中領悟并提煉出來的一道面試題，這道題讓很多擅長百度或谷歌搜索以及刷題的應試者手足無措，90%的人在網上面試階段看到這道題后都歸于沉默，而9%的人會給出如圖1-4所示的解答。

很顯然，圖1-4這個答案中間的豎線導致原子邊被切割了，同時也引入了多個無用的頂點，它完全不符合只增加1條邊的限制條件。給出這種答案的人大抵沒有仔細讀題。

這個問題好的地方在于，它可以有很多個答案，不一而足。例如圖1-5所示的答案，這樣構圖可謂用心良苦，雖然略顯復雜，但本質上完全符合上面的分析：固定2個頂點，連接1條邊，出現了5個新的三角形。然而，如此辛苦的構圖實際上也是平面化（低維化）的，它牽涉的點、邊數量比較多。

有沒有更簡潔的方案呢？答案是有。圖1-6所示的7個頂點（A～G）已經形成了5個三角形，如果在A、B間再新增1條邊，就形成了10個三角形，包含5個新增的三角形。為了在二維平面內表達這個高維空間，我們用虛線表示被遮蓋部分的邊。

很顯然，這個方案用了較少的點和邊。它最巧妙的地方在于在頂點A、B之間新增的邊，很多人覺得不可思議，但是如果仔細讀問題，A、B是兩個賬戶，賬戶之間完全可以存在多筆交易，這其實已經在暗示解題的思路了。

那么，按照這個思路繼續探尋下去，如何構造一個使用更少的點和邊的圖來解這個題目呢？

圖1-7所示的解決方案僅使用了4個頂點與7條邊就構造出了5個三角形。增加8號邊之后，能形成5個新的三角形。這個解法的聰明之處在于頂點A、C、B之間由1～5號邊所形成的4個三角形復用了1、2、3、4這幾條邊。因此，圖的上半部分有4個三角形，下半部分有1個三角形，它們共用了邊A、B（5號邊），只要在A、B之間新增1條邊，全圖的三角形數量就會翻倍。這是相當巧妙的構圖邏輯。

類似地（觸類旁通），如果我們可以構造一張圖，上面包含3個三角形，下面包含2個三角形，兩部分共享一條邊，同樣可以達到類似的效果。聰明的讀者可以嘗試畫出這張圖的樣子。目前已知最精簡的構圖如圖1-8所示，它只用了3個頂點和8條邊。聰明的讀者如果可以想到更極致的方案，歡迎聯系筆者。

現在我們探究一下這個題目背后所蘊含的圖的意義。在銀行業中，以零售轉賬為例，大型商業銀行中有數以億計的借記卡賬戶，這些賬戶每個月有數以億計的交易（通常交易的數量會數倍于賬戶數量）。如果以卡賬戶為頂點，以賬戶間的交易為邊，就構造成了一張有數以億計點和邊的大圖。如何衡量這些賬戶之間連接的緊密程度呢？或者說，如何判斷這張圖的拓撲空間結構呢？類似地，在一張SNS社交網絡圖中，頂點為用戶，邊為用戶間的關聯關系，如何衡量這個社交圖譜的拓撲結構或緊密程度呢？

三角形是表達緊密關聯關系的最基礎的結構。如圖1-9的社交網絡圖譜（局部）所示，兩個框內的4個頂點間都構成了16個（2×2×2+2×2×2）三角形。從空間結構上看，它們之間的緊密程度也更突出。

上面提到的銀行轉賬賬戶間所形成的三角形的個數，很大程度上可以表示銀行賬戶間某種關聯關系的緊密程度。2020年某季度，某股份制銀行的轉賬數據形成了2萬億個三角形，而頂點與邊的數量都在10億以內，也就是說平均每個頂點都參與到了上千個轉賬三角關系中。這個數字是非常驚人的，但我們仔細分析就會發現，如果少量的頂點之間存在多個轉賬關系，例如A、B、C三個頂點，如果它們兩兩之間都存在著100條邊，那么總共就構成了100萬個三角形。類似地，A與B兩個頂點之間存在一個關系，它們各自分別與另外1000個賬戶存在一個轉賬關系，A、B之間每增加一條邊就會增加1000個三角形。

當然，無論是轉賬交易數據、社交網絡數據、電商交易數據還是數字貨幣流轉數據，數據所形成的網絡（圖）用數學語言來定義都是一個拓撲空間（Topological Space）。在這個拓撲空間中，我們關心的是數據之間的關聯性、連通性、連續性、收斂性、相似度（哪些節點或節點集合的行為、特征等指標更為相似）、中心度、影響力以及傳播的力度（深度、廣度）等。用拓撲空間內數據關聯的方法來構造的圖可以完全還原并反映真實世界中我們是如何記錄并認知世界的。如果一個拓撲空間（一張圖）不能滿足對異構、多源、多維、多模態的數據的描述，那么就要構造另一張圖來表達—結果就是天然地形成了一個多圖的數據集合。每一張圖可以看作從一個（或多個）維度或領域（如知識領域、學科知識庫等）對某個數據集的聚類與關聯，區別于傳統關系型數據庫的二維關系表的方式，每一張圖可以是多張關系表的某種關聯組合。

在圖上，不再需要二維關系表操作中的表連接（Table Join）操作，而是用圖上的路徑或近鄰類操作來取代。我們知道，表連接的最大問題是在復雜、多表查詢模式下會出現的笛卡兒積（Cartesian Product，又稱直積）挑戰。尤其是在大表中，這種乘積的計算代價是極大的，參與表連接的表越多，它們的乘積就越大。例如，3張表X、Y、Z的直積計算量是{X}×{Y}×{Z}，如果X、Y、Z各有100萬、10萬、1萬行，計算量就是1000萬億，這是個天文數字。在很多情況下，關系型數據庫批處理緩慢的一個主要原因就是需要處理各種多表連接的問題。這種低效性實際上是因為關系型數據庫（以及它配套的查詢語言SQL）無法在數據結構層面做到完全反映真實世界。

人類大腦的存儲與計算從來不會在遍歷和窮舉時通過笛卡兒積在計算上浪費時間，但是當我們被迫使用關系型數據庫以及Excel表格的時候，經常需要極為低效地做反復遍歷和乘積的事情。在圖上則不會出現這種問題—在最壞的情況下，你可能需要以暴力的方式在圖上遍歷一層又一層的鄰居，但它的復雜度依然遠遠低于笛卡兒積（例如，1張圖有1000萬個點和邊，遍歷它的復雜度最大就是1000萬—任何顯著高于其最大點和邊數量的計算復雜度都是圖數據結構、圖算法或圖系統架構設計失敗的體現）。

看到這里，熟悉數倉的讀者可能會質疑通過極致的優化，數倉是可以盡可能避免笛卡兒積現象的，并且能做到各種計算優化與存儲進程的加速。然而，數倉是通過對數據不斷地進行分表，構建中間表、碼表，分層，預計算，緩存結果等一系列操作來實現所謂的優化和加速的。換言之，數倉更適用于數據流轉模式相對固定、靜態的查詢，如果查詢模式高度靈活且動態，數倉是無力承載的。究其根本，是因為整個關系型查詢SQL計算與分析的邏輯都是建立在二維表基礎之上的，如我們先前所述，用低維來表達高維，注定會遇到效率、靈活性甚至黑盒與不可解釋性等諸多問題。

值得一提的是，人的思維方式就是圖的思維方式。可以比擬、還原人的思維方式的圖數據庫或圖計算的方式，我們稱為原生圖（Native Graph）。通過原生圖的計算與分析，我們可以讓機器具備像人類一樣的高效關聯、發散、推導、迭代的能力，而讓機器擁有這樣的能力的基礎在廣義上就是圖查詢與分析算法，簡稱圖算法。

所謂原生圖，是相對于非原生圖而言的，在本質上指圖數據是如何以更高效的方式進行存儲和計算的。非原生圖使用的可能是關系型數據庫、列數據庫、文檔數據庫或鍵值數據庫來存儲圖數據；而原生圖使用的是更為高效的存儲（及計算）方式來為圖計算與查詢服務。

原生圖構建的當務之急是數據結構，這里要引入一個新的概念—無索引近鄰（Index-Free Adjacency）。這個概念既和存儲有關，也和計算有關。簡而言之，無索引近鄰數據結構相對于其他數據結構的最大優勢是，在圖中訪問任一數據所需的時間復雜度為O（1）。例如，從任一節點出發訪問它的1度近鄰的時間復雜度是O（1），反之亦然。而這種最低時間復雜度的數據訪問恰恰就是人類在大腦中搜尋任何知識點并關聯發散出去時所采用的方式。這種數據結構顯然和傳統數據庫中常見的基于樹狀索引的數據結構不同，從時間復雜度上看是O（1）與O（logN）[1]的區別。而在更復雜的查詢或算法實現中，這種區別會放大為O（K）與O（NlogN）或者更大（K≥1，通常小于10或20，但一定遠遠小于N，假設N是圖中頂點或實體的數量）。這就意味著在復雜迭代運算的時效性上會出現指數級的差距，在圖上如果是1s完成，傳統數據庫則可能需要1h、1天或更久（或者無法完成）—這意味著，傳統數據庫或數倉中的那些動輒T+1的批處理操作可以以T+0甚至純實時的方式瞬間完成！

當然，數據結構只是解決問題的一個方面，我們還需要從架構（如并發、高密度計算）、算法并發優化、代碼工程優化等多個維度去讓圖數據庫真的騰飛。有了原生圖存儲與高并發、高密度計算在底層算力上的支撐，圖上的遍歷、查詢、計算與分析可以得到進一步的飛躍。如果傳統的圖數據庫號稱比關系型數據庫快1000倍，那么飛躍之后的圖要快100萬倍！