基于 Nebula Graph 構建圖學習能力
經常看技術文章的小伙伴可能會留意到除了正在閱讀的那篇文章，在文章頁面的正文下方或者右側區域會有若干同主題、同作者的文章等你閱讀；經常逛淘寶、京東的小伙伴可能發現了，一旦你購買或者查看過某個商品之后，猜你喜歡的推薦商品會貼近你剛拔草的商品…這些日常生活中常遇到的事情，可能是由一個名叫圖學習的“家伙”提供技術支持。
圖學習，顧名思義是基于圖的機器學習，按照本期項目介紹的參賽隊伍——圖學習興趣小隊隊長楊鑫的話就是，圖學習是一個通過深度學習方法，基于圖的結構與屬性生成一個向量作為點、邊或者整個圖的表征。
在之前 Nebula Hackathon 2021 年的參賽項目中，圖學習興趣小隊“豪氣”地說要讓 Nebula Graph 具備支持圖學習的能力，在本文接下來的內容中，你將了解到他們是怎么實現這一目標的。
在講述項目實現之前，項目負責人楊鑫先給大家上了一課“圖解圖學習”。
以獲取頂點的向量表征為例來講解下圖學習過程，第一步需要對圖中頂點鄰居進行采樣拿到鄰居的拓撲結構以及屬性；第二步便是通過自定義的聚合函數聚合鄰居頂點蘊含的信息進行計算；最后一步基于聚合信息得到圖中各頂點的向量表示。
楊鑫表示，衡量一個圖學習算法的好壞是通過生成向量中包含圖中頂點屬性及拓撲結構的豐富程度來判斷的。
在選擇圖學習框架時，圖學習興趣小隊有自己的一套選型標準：首先它是開源組件，方便二次開發，其次它支持分布式，最后框架本身和圖數據庫的耦合程度要低方便定制化開發。經過深入調研，由于 DGL 同底層的圖數據庫耦合過高，PYG 不支持分布式，最終他們采用了 Euler，而在 Nebula Hackathon 2021 中，圖學習興趣小隊的重點工作便是用 Nebula Graph 替換 Euler 原生圖數據庫，讓社區用戶可以基于 Nebula Graph 低成本嘗試圖學習能力。
在方案設計上，架構分為三層：底層是 Nebula Graph 圖數據庫，中間層是圖采樣算子層，為上層 Euler 圖算法提供多種采樣圖數據的能力。圖采樣算子則是他們本次工作的重點——重寫 22 個 TF 采樣算子、6 種 nGQL 采樣語法。
以全局帶權采樣語法設計為例，
這里采用了預計算（離線）+ 計算下推（實時）的方式來實現全局采樣，主要過程為（上圖 1-4）
- graphd 提交異步構建任務給 metad；
- metad 下發任務給各個 storaged 節點進行計算；
- storaged 將計算結果上報給 metad 匯總；
- metad 通過心跳將結果同步給 graphd。
詳細展開來講，在圖學習訓練過程中，數據采樣是一個非常高頻的操作，采樣性能好壞對圖學習訓練耗時影響很大。
在這里，楊鑫他們采用別名采樣算法作為全局帶權采樣語法的核心算法，它的基本原理是首先對進行采樣的全部數據根據各自的權重計算出一份采樣表，采樣表由行號（sid）、vid1、采樣概率（prob）、vid2 四部分組成，其中行號是從 0 開始的編號，vid1、vid2 表示可以被采樣的某個頂點的 vid；采樣流程是首先在表中隨機選擇一行，然后再隨機生成一個 0~1 之間的值 p，如果 p < prob，則本次采樣的數據是 vid1，否則采樣 vid2。
目前圖學習是基于靜態圖數據訓練，因此我們可以通過預計算的方式離線生成一份別名采樣表，而實時采樣過程簡化為基于預計算的采樣表做兩次隨機采樣，時間復雜度由 O(n) 降到 O(1)，可以極大地提高采樣效率。
下面是基于 Nebula Graph 實現的全局帶權采樣具體實現，跟 Nebula Graph 的索引重建邏輯很相似。
- Graph 服務調用 Meta 服務啟動一個異步構建采樣表任務，并支持異步任務的狀態查詢。
- Meta 服務的作用是控制異步任務的執行，包括分配每個 Storage 節點需要處理的數據（根據 partition 的 leader 分布決定）、異步觸發各個 Storage 節點進行采樣表的計算、記錄任務的執行狀態、記錄全局信息（點、邊權重和）、通過心跳邏輯將全局信息緩存在 Graph 服務中。
- Storage 服務的任務是生成所負責數據的采樣表。采樣表的計算是整個流程中的核心邏輯，計算過程需要對所有點、邊編號，并根據權重大小對點、邊進行分類，很顯然這些數據是無法全部存儲在內存中的，所以我們在 Storage 中增加了一個采樣統計信息 RocksDB 實例來存儲采樣表、點邊總數、點邊權重、計算中間變量等數據。以計算某一類點的采樣表的過程為例：
第一步遍歷全圖來統計這一類點的權重和數量，同時為了給生成采樣表做準備，將點的序號（點的讀取順序）、vid、權重等數據存儲在了圖中（B1）結構中。其中 key 的數據結構是 type + tagid + sid，type 標識了數據是 B1 類型，tagid 就是點的 tag，sid 是點的序號，跟采樣表的 key 結構相同。
第二步將數據分類，根據權重值以點的總數的倒數為界將所有的點分成兩部分，分別以（B2）、（B3）的結構存儲，key 的組成與 (B1) 結構相比就是type 值不同。
第三步分別遍歷（B2）、（B3），根據別名采樣算法的理論來計算每個點的采樣概率 prob。這里每個點是用 sid 來標識的，也就是說實際上是在計算第 sid 個點的采樣概率，概率值作為采樣表的一部分會更新到（B1）結構中。
第四步將中間變量（B2）、（B3）結構刪除掉，釋放磁盤空間。
利用采樣表進行實時采樣的過程就比較簡單了。完成采樣表的預計算后會將點、邊權重的統計信息上報到 Meta 服務存儲，然后通過心跳通知 Graph 服務將這些數據緩存在本地。根據這些數據可以計算出點、邊在各 Storage 服務上所占的權重比例，將用戶指定的采樣數量按比例分配到各 Storage 服務，然后在 Storage 服務上通過兩次的隨機數操作采樣到足夠數量的數據后返回，最后在 Graph 服務上進行數據聚合，這樣就完成了一次帶權采樣。
另外為了提高異步任務的健壯性，還實現了失敗重試、任務重復限制、重建采樣表后臟數據清理、導出采樣表等功能。
提到項目設計以及重寫其他算子過程中遇到的問題，圖學習興趣小隊隊長楊鑫表示因為 Nebula Graph 的數據都存儲在磁盤中，要用 Nebula Graph 替換 Euler 原生內存圖數據庫，改造后的 Euler 在采樣效率上肯定要低于原生 Euler，因此怎么保證改造后 Euler 的圖學習訓練耗時盡可能接近原生 Euler 是要解決的首要問題，至少得保證兩者采樣性能不能有數據級上的差距。
原生 Euler 中的圖學習算法由 Python 實現，通過 TensorFlow 的 OP 機制來調用 C++ 實現的采樣算子，然后在采樣算子內直接調用內存圖數據庫獲取數據，這樣就完成了一次數據采樣。
圖興趣小隊最初的方案是將采樣算子用 Python 實現，這樣一次數據采樣過程就變成了圖學習算法直接調用采樣算子，然后在采樣算子內則通過 Nebula Graph 的 Python 客戶端執行采樣語法獲取數據。這樣改造后的系統會有更清晰的處理流程，但是經過測試他們發現其訓練耗時要遠大于原生 Euler，具體到訓練過程中的每次數據采樣上，其耗時是原生 Euler 的幾十倍，這樣的結果顯然是不能滿足要求的。通過分析各階段執行耗時他們發現，數據采樣的耗時要遠大于采樣語法的執行耗時，所以他們認為是 Python 客戶端在反序列化上消耗了大量時間。因此圖興趣小隊進行了第一次優化，使用 fbthrift fastproto 替換 Nebula Graph 原生客戶端的序列化組件，優化后的性能提高了一倍，整體訓練耗時確實有所降低，但是這樣的結果卻仍然無法滿足他們的使用要求。
這時候用上了第二個方案，重寫 C++ 版本的采樣算子，在采樣算子中通過 Nebula Graph 的 C++ 客戶端執行采樣語法獲取數據，相比第一個方案多了一些適配工作，算子的重寫主要是適配 C++ 客戶端的輸入輸出，另外改造了 C++ 客戶端以便采樣算子的調用。
這也是他們最終的方案，這樣改造后的 Euler 雖然在訓練耗時上仍然高于原生 Euler，但是差距控制在了二倍以內，符合預期。
當談到本次有什么值得圖學習興趣小隊留意的項目時，隊長楊鑫表示比較關注的是大油條東北虎隊伍的項目——如何吊打 Nebula 的深度查詢，這個項目的優化思路對他們很有借鑒意義。
因為在實際使用中，圖興趣小隊所在團隊的業務方有很多的多跳查詢需求，包括 GO 查詢、FINDPATH 查詢等。這本應該是 Nebula Graph 所擅長的部分，在大部分場景下也確實如此，但是在遇到出度很大的頂點的時候，查詢性能會急劇惡化。其主要原因還是基于目前 Nebula Graph 的架構，多跳查詢只能先將一跳的結果集匯總到 Graph 服務后才能進行下一跳計算，完全不能將多跳計算下推。而這個項目正好給他們提供了一個解決這個難題的思路。
