導讀：現實中的人和人、人和物、物和物構成了各種複雜多樣的關係，這些關係可以透過圖進行建模和表達：比如轉賬網路、社交網路等。對圖（圖模型）的理解和應用尤為重要。今天分享的主題整體比較發散，除了圖資料庫的相關內容，還會分享一些我們在其他方向的思考，包括圖的技術棧、圖的智慧平臺，以及圖資料庫與圖智慧平臺的關係，最後分享下圖資料庫在騰訊內部業務場景中的應用。主要內容：
- 像圖一樣思考
- 圖Young！圖Simple？
- 圖資料庫與圖智慧平臺
- 圖資料庫應用
01
像圖一樣思考
除了圖資料庫，我們還自研了圖計算框架、圖視覺化引擎和圖分析元件等，也和公司內的Flink（Oceanus）產品進行打通，目的是完善圖流融合的一些功能。
1. 圖論
圖論在1738年由尤拉開創，解決柯尼斯堡七橋問題，用圖將不同區域建模成點，把橋建模成邊，透過圖解決了實際問題並發展出了圖論。
目前對圖的分類一般為屬性圖模型和RDF圖模型。我們自研的EasyGraph圖資料庫、Angel-Graph圖計算框架以及Graph-Idex圖視覺化平臺是基於有向屬性圖模型實現的。其中頂點用來表示實體或例項，如人、裝置、抽象的IP等，邊用來表示頂點之間的關聯關係，最終透過圖平臺元件完成圖資料的建模、儲存、計算、視覺化分析和應用。
2. 轉賬場景
在使用圖資料庫、圖計算、圖視覺化等圖技術前，需要先從業務角度定義和思考構圖問題。比如在轉賬支付網路場景，首先識別圖中哪些是實體（頂點），如使用者的ID、銀行卡、裝置、手機號、證件號、WIFI、地理資訊等都可以看作頂點，頂點之間的關係則可以透過使用者行為序列或頂點間的依賴關係生成，這些關係包括使用者轉賬資訊、使用者在裝置上面的登入行為以及繫結手機號/銀行卡等操作。透過對業務場景的理解建模構造整體圖模型網路，進一步識別出圖中的同構或異構關係。如UID與UID之間的轉賬同構網路，UID和裝置之間的異構二部圖。
準確詳盡的構圖建模有利於用圖計算、圖查詢、圖視覺化、圖分析等技術挖掘圖資料的價值。
3. 萬物互聯
如今是萬物互聯的時代，早期大資料時代不只是資料量的增長，資料之間的聯絡也更加複雜多樣化，如社交APP中關注、點贊、評論等行為構成的社交網路，行動通訊的簡訊、電話構成的通訊網路，移動支付場景如微信支付、紅包、面對面的支付、掃碼等構成了支付網路，電商場景的瀏覽、購買、收藏、評論行為構成了使用者和物品之間的購物網路。
萬物互聯的時代使得圖無所不在，因此對圖資料的挖掘尤為重要，以往傳統的單點分析技術逐漸難以準確或完整的刻劃個體，針對圖資料的關聯性計算和查詢分析成為常態需求。
4. 以圖治圖
值得思考的是如何透過圖技術解決圖的應用問題？作為一種特殊的資料結構，《演算法導論》的第六部分的第21-25章介紹了圖的基礎知識，如圖的儲存用到了鄰接表（連結串列）、鄰接矩陣，以及圖的遍歷，最大流等演算法問題。
不同格式的資料需要的儲存元件不同，HDFS儲存非結構化資料，Hive儲存有欄位清晰的結構化資料。圖既然也是一種特殊的資料結構，也需要高效的儲存系統— —Graph Database。圖資料庫在儲存圖資料時充分考慮到資料查詢遍歷時的區域性性問題，解決了一跳擴充套件甚至子圖級的資料鄰近儲存。
傳統的MapReduce任務假設資料之間的聯絡較弱，使得資料的劃分和平行計算較為容易。但是對圖而言，資料之間的耦合性較強，往往需要先對圖進行劃分，不同的劃分方式對計算效率影響較大。MapReduce的粗粒度劃分會導致負載計算不均衡等問題，最終導致圖的計算效率較低，所以2010年Google提出Pregel分散式圖計算框架，並提出了以頂點為中心的程式設計思想：Think like a vertex 像頂點一樣思考，每個點都可以接收鄰居傳送的資訊，並結合自身的屬性和更新函式進行更新操作，並把更新後的資訊沿著鄰邊傳送給鄰居，透過不斷迭代完成整個計算過程。在做計算時站在頂點的角度思考整個圖計算過程，可以靈活表達多種圖演算法，提升開發效率。
圖視覺化則是天然地把點邊構成的網路呈現出來，用頂點大小、邊的粗細表達權重資訊，透過顏色或形狀表達不同點邊型別，這種視覺捕獲的資訊不僅直觀，而且更容易被理解。
02
圖Young！圖Simple？
回顧圖技術的發展應用歷程，圖是不是一門比較年輕的技術呢？圖技術是不是很簡單？
1. 發展歷程
① 圖理論
回答是不是年輕的問題，可以從圖理論的發展歷程來看。
自1738年尤拉提出圖論至今已有200多年的歷史，中間也有一些圖演算法如旅行者揹包等問題，但並沒有對工業界造成很大的影響，偏理論研究性質的演算法一般短期難以看到效果。
但在1998年，PageRank演算法的提出以及對Google搜尋引擎的影響使得人們意識到圖演算法的重要性。特別是最近幾年，如2014年、2015年、2016年出現圖的表示學習演算法，DeepWalk借鑑Random Walk的思想學習圖的Embedding，再到GCN、Graphsage的出現，將卷積思想擴充套件到圖領域，促進了圖神經網路方向的研究，GNN也是目前圖最火熱的研究方向。
② 圖計算框架
從圖計算框架而言，自2010年Pregel發表後，分散式圖計算系統成為工業界主流研究方向，一些知名的圖計算框架如2012年PowerGraph，2014年Spark的GraphX以及2016年的Gemini等。騰訊在2019年也實現了Angel-Graph和Plato。2019年Facebook也開源了Pytorch-BigGraph，它是基於Pytorch實現的圖神經網路框架。從圖計算框架的發展歷程來看只有十幾年的歷史。
③ 圖資料庫
2007年Neo4j的出現發展處了圖資料庫方向，到2012年的Titian、TigerGraph以及後面的JanusGraph等圖資料庫。
縱觀圖算法理論、圖計算框架和圖資料庫系統的發展歷程，圖技術既年輕又充滿活力。
2. 發展趨勢
在2019和2021年Gartner資料和分析技術趨勢預測中，都將圖作為十大技術趨勢之一（參考下圖），工業界對圖的應用以及學術界對圖的研究也成為趨勢，並在實際應用場景落地較多。而圖資料庫管理系統在DBEngine Ranking也扶搖直上，成為發展趨勢最快的方向。
3. 需求與挑戰
從騰訊內部業務的需求和痛點進一步說明，騰訊在QQ、微信、廣告、支付、遊戲、影片、音樂等場景有著豐富多樣的圖資料，某些業務場景單個網路可達十億級頂點、千億級邊，如此龐大的圖資料蘊藏著價值，也給圖的儲存、計算、分析提出了更高的的要求，特別是超級頂點的存在成為儲存和計算的的共同難題，也是亟需解決的問題。為了提升元件的易用性，需要和內部大資料生態打通，如TDW、HDFS、Spark、Flink、排程系統等，最終圍繞圖資料庫、圖計算框架、圖視覺化平臺元件等構建圖智慧平臺。
03
圖資料庫與圖智慧平臺
目前圖智慧平臺引擎包括三部分：圖計算框架、圖資料庫系統和圖視覺化引擎。外部對接了流計算引擎，騰訊內部使用Oceanus把流計算與圖計算、圖查詢進行融合。
圖智慧平臺的定位是在解決百億頂點、萬億邊的圖儲存，包括相簿管理、許可權管理、圖查詢分析等功能，以便大幅提升業務的查詢使用效率。以及為了微信支付、遊戲、廣告的計算需求提供高效能的圖計算能力。解決圖資料之上的TP和AP問題。
1. 圖的三駕馬車
① 圖計算
圖的三駕馬車中我們在2019年自研了圖計算框架Angel-Graph，解決了傳統圖挖掘、圖表示學習和圖神經網路的高效能計算問題，包括經典的PageRank ，Closeness等演算法，以及圖表示學習Deepwalk、Node2Vec的Embeeding演算法，以及GNN演算法，將三大類圖計算問題融合成一個框架 —— “三位一體”。目前已開源在Github上的Angel-ML專案中，也是業界第一個比較全面覆蓋圖計算問題的開源圖計算框架，我們的研究成果也發表在ICDE 2020頂會上，感興趣的同學可以看下這篇論文。
在實現圖計算框架時首先考慮圖的分散式切分問題。因為百億級甚至千億級的圖，單機是難以存下的。目前Angel-Graph基於引數伺服器的架構，將頂點資訊儲存在全記憶體的ps上，在圖計算或圖演算法如PageRank的迭代計算過程中，邊結構是不變的，資料的頻繁更新發生在頂點上。Graphx低效的原因之一是RDD的immutable特性，RDD的每次更新需要生成新的RDD，因此佔用了大量的記憶體開銷。為了保障在受限共享資源環境下圖計算任務的穩定執行，Angel-Graph引入了batch計算的邏輯，業務側可以根據資源配置調整計算速度，保障資源不足的情況下仍能穩定執行。
在百億級的圖資料上對比Graphx 和Angel-Graph的效能，Angel僅用1/3的資源，效能可以達到Graphx的10倍以上。因為同樣融合了spark生態，Angel-Graph也可以像Graphx一樣保障圖計算的ETL能力，即圖資料讀取、預處理和結果儲存可以在一個圖計算任務中，從而避免了中間資料的中斷、落盤和二次載入。
② 圖儲存
圖資料庫一般解決對圖資料的查詢需求，以及對重新結果的子圖分析。圖是一種非歐空間的資料，在社交網路場景中往往符合小世界模型，如六度空間理論。所以比較遠的查詢如3跳以上查詢到的資料較多，難以高併發執行。一般對圖資料庫的的應用主要為1/2階查詢，以及更多跳的帶條件遍歷，透過條件約束查詢到的資料量。圖資料庫也可以和圖計算、圖視覺化引擎融合打通，解決全量的AP分析，以及查詢結果的的視覺化。
2. EasyGraph
目前EasyGraph採用了儲存計算分離架構，查詢層既支援無狀態的TP查詢需求，也支援有狀態的AP分析，比如剛才提到的3跳以上的查詢計算問題，單點的server的計算效能較差，難以滿足業務需求，因此可以採用分散式的server來解決。
3. 圖的視覺化
圖視覺化透過展示實體、關係幫助使用者獲取對查詢結果資料的洞悉能力，目的是為了使得圖資料可看、可理解和可分析。圖視覺化系統已廣泛應用在知識圖譜、金融風控、網路安全、排程依賴等領域。如金融支付場景的團伙欺詐判定，圖視覺化可以對事中或是事後進行分析，從而判斷模型檢測結果的正確性，或者觀察欺詐團伙形成的過程，從而對業務策略或規則進行修正。
視覺化一般支援搜尋、過濾、渲染、佈局、計算等功能，也提供點級、邊級、子圖級不同視角的轉化。在實際場景中百萬級以上的圖在瀏覽器端已經難以渲染，座標計算等比較重的計算為成為瓶頸，可以把前端計算的邏輯下推到後端執行，這也是我們在做的一些最佳化。
4. 圖的應用概覽
總結而言，圖的普遍應用需求便是圖智慧平臺需要解決的問題，技術層面可以歸納為儲存、計算(離線、線上)、視覺化以及易用的開發工具等。場景的應用如視覺化分析、統計畫像、模式識別、圖學習、知識圖譜、查詢分析等。
04
圖資料庫應用——以圖治圖
最後迴歸正題，分享下圖資料庫的應用，這也是今天的主題。首先介紹圖資料庫在整個騰訊業務中的應用。
1. 統一排程系統
作為平臺團隊，最能體會到圖資料的價值，特別是對排程系統而言。排程系統相當於平臺的管家，負責資料的入庫、出庫、計算、挖掘、分析等，每天有大概有1050w的任務被排程，300W+的SQL查詢，以及300P+的資料搬遷。在這樣高效的排程系統中任務並非獨立執行，而是存在各種依賴關係，而且有很多的任務不一定是臨時建立和臨時去呼叫的，很多工被例行化執行。
以右邊的圖（參下圖）為例，假如C這種天級任務依賴於A、B這兩個小時級任務，當A，B兩個任務1-24小時的任務執行成功之後才會觸發C任務的執行，它本身有一個靜態依賴圖和動態執行圖。我們將任務依賴關係儲存到圖資料庫，並對多階依賴關係進行實時查詢，從而解決高併發的依賴判斷問題，將圖查詢的依賴判斷和事件觸發機制進行有效結合，對統一排程系統的實時性進行最佳化。
相比採用MySQL儲存依賴關係的解決方案，圖資料庫使得之前兩分鐘輪訓排程耗時下降到了30毫秒，整個排程實時性提升了4000倍，在沒有用圖資料庫之前，我們看到在整點的時候這個波峰效應非常明顯，採用圖資料庫後波峰效應大幅度降低，任務排程的實時性也得到了保障。
2. 金融支付
圖視覺化引擎可以應用在資金鍊路分析中。左圖大概一千多個點，兩千多條邊，這是一個完整的圖。為了更方便對區域性資訊視覺化分析，我們做了很多最佳化，一方面能對點、邊的屬性進行顏色、大小的調整，另外也提供了一些聚合的演算法，比如透過一些社群發現演算法或者業務給定聚合規則對點或區域性的子圖進行聚合，聚合後圖中頂點自然包含了很多統計資訊。也可以點選展開分析某個聚合點，這樣幫助使用者清晰的判斷區域性交易情況。
3. 欺詐團伙判斷
欺詐團伙的判定用到了圖智慧平臺多個元件的功能。在做欺詐團伙檢測時，首先需要圖計算框架執行Louvain演算法，為了滿足業務需求，我們自研了帶有先驗知識的PKLouvain演算法（Prior Knowledge Louvain）。因為在安全風控場景中圖演算法有很強的業務邏輯，這些業務規則也可以用在社團挖掘演算法中。比如透過使用者登入的ID，wifi等資訊去構圖，業務側事先知道哪些點肯定屬於一個社團，哪些點肯定不在同個社團結構中。透過將這些資訊構造正負邊關係輸入到Louvain演算法中，然後控制社團的合併邏輯，相比傳統的Louvain演算法，PKLouvain演算法在準確率上有11%~22%的提升。
PKLouvain演算法的計算結果也可以儲存在圖資料庫中，然後根據使用者id或社群id查詢完整的社團結果，透過圖視覺化引擎還原和展示整個的社團結構。業務同學根據視覺化結果進行業務判定，判斷查詢到的社團是否為欺詐團伙，這裡面會涉及到許多的業務規則和對業務的理解。如果發現一個新型的欺詐團伙結構，也可以從裡面提取出來一些新的規則或者策略，並將這些規則或策略加入圖演算法中，進一步的最佳化圖計算的結果。
這種從圖計算=>圖資料庫=>圖視覺化=>業務模型/策略/規則=>圖計算=>…，整個過程形成了閉環，也用到了圖智慧平臺的圖計算框架、圖資料庫、圖可視引擎。例如以賭博莊家為例，像傳統關係型資料庫做這種關聯分析，需要寫複雜的sql查詢語句，並引入大量的表join操作，嚴重影響計算效能，對一個賭博莊家的兩階的判定需要17分鐘才能做完，但是結合圖資料庫、圖視覺化可以輕鬆實現秒級的業務研判，比如右圖的賭博莊家的二階的關係，紅色的點標識賭博使用者，可以看到很多使用者都是這種紅色，那麼這個頂點周圍很大程度上存在賭博團伙。
4. 圖智慧平臺服務開放
目前圖智慧平臺的功能已經對外開放，在騰訊雲的智慧鈦機器學習平臺上提供了Angel-Graph圖計算功能，圖計算框架也在Github Angel-ML專案進行開源。圖資料庫的一些能力基本功能也作為騰訊雲圖資料庫產品KonisGraph，歡迎大家體驗和關注。
05
精彩問答
Q：有狀態的GraphService如何實現分散式容錯？
A：我們在做有狀態Server的分散式容錯時也參考了Angel-Graph圖計算的一些工作，較重的離線計算可以採用checkpoint，輕量的計算只需要對查詢結果的資料儲存即可，失敗時重新計算。
Q：圖視覺化有沒有優秀的前端框架和產品案例推薦一下？
A：Gephi、Antv都是不錯的視覺化工具，NetworkX也足夠易用，可以根據業務需求靈活選擇。
Q：EasyGraph和Plato 都是騰訊的，都有圖儲存，它們和Angel-Graph是什麼關係，是支援的場景不一樣麼？
A：EasyGraph和Plato解決的問題不一樣，柏拉圖是圖計算框架，EasyGraph則是圖資料庫系統。在我們圖智慧平臺中Angel-Graph也是圖計算框架，所以Plato和Angel-Graph的功能和應用場景更相似，都是為了解決騰訊內部圖資料的挖掘計算問題。
今天的分享就到這裡，謝謝大家。
在文末分享、點贊、在看，給個3連擊唄~
分享嘉賓：
分享嘉賓：李曉森 騰訊大資料 專家工程師
編輯整理：王彥磊
出品平臺：DataFunTalk
