1. 首頁 > 生活百科 > >

從零開始學Graph Database：什么是圖( 二 )

生活百科


從零開始學Graph Database：什么是圖

文章插圖
亦或者說 ， 在線場景中，重查詢輕算法；而在離線場景中，重算法而輕查詢 。
事實上，圖查詢與圖算法的邊界并沒有那么涇渭分明 ?；蛘哒f，圖算法算是某種程度上的特殊圖查詢 。我們普遍認為算法較查詢需要更多的計算資源，會占用更多的CPU與內存 。
從零開始學Graph Database：什么是圖

文章插圖
比如上圖的多跳查詢和BFS algorithm ， 本質上是同一個查詢 ?；疑K顯示的是gremlin與cypher的查詢方法，藍色模塊顯示的是不同圖數據庫中BFS算法的執行方式 。但他們的結果都是一致的，均為點Tom的三度鄰居 。也就是在業界，N跳查詢即可以作為廣度/深度優先算法/khop算法單列出來 ， 也可以作為圖遍歷/圖查詢中一種常用模式存在 。
從零開始學Graph Database：什么是圖

文章插圖
除此以外，subgraph matching也是一個圖查詢與圖算法同時存在的研究課題 。如上圖，我們輸入目標子圖q，在圖G中尋找其同構圖，這其實是一個NP-Hard問題 。
當然了，即使子圖查詢是一個非常困難的問題，大部分圖查詢語言還是提供了相應的match語法用于基于模式匹配的搜索功能，如neo4j使用的Cypher，或者支持指令式和聲明式查詢的Gremlin 。而在圖算法領域，subgraph matching則是一個極重要 ， 極復雜的研究課題 。下表中列出來一部分具有代表性的子圖匹配算法的分類 。(來源于paper[In-Memory Subgraph Matching: An In-depth Study]) 。
從零開始學Graph Database：什么是圖

文章插圖
圖的應用下面讓我們從一個具體的例子中體會一下圖在場景中的使用 。
假設我們需要在社交關系中為用戶推薦好友，在不同的場景中，可以使用不同類別的查詢和算法 。如果用于在線推薦，我們可以將二度鄰居作為其推薦結果，即2跳查詢，這在大部分的圖數據庫中是一個代價非常小的查詢，大多可在100ms以內完成 ， 甚至可以在10ms內返回；如果用于離線推薦 ， 則會傾向于使用推薦效果更優秀的圖算法 。例如，利用社團算法louvain, labelPropagation, Strongly Connected, k-Core獲得每個點的社團分類，并將分類結果作為點上embedding的vector參與后續downstream task計算；或者直接使用圖上Node embedding算法(Node2vec, FastRP, Weisfeiler-Lehman等)得到一個完整的點上Embedding的結果用于后續訓練；當然，也可以直接使用圖相似性算法(Cosine, Jaccard等)直接得到針對某個點的推薦結果 。
gremlin: g.V('李雷').out().out()cypher: match (n)--(m)--(l) where id(n)='李雷' return llouvain:[GES API]POST /ges/v1.0/{project_id}/graphs/{graph_name}/action?action_id=execute-algorithm{"algorithmName": "louvain","parameters": {"max_iterations": "100","convergence": "0.01","weight":"score"}}大部分的工業使用場景中，圖更多地扮演著數據庫的角色 ， 用來管理某個領域內的關系數據 。用戶大多看中圖對于多跳關聯分析能力，以及數據間脈絡的整理歸集，分析和可視化 。
特別的，在某些垂直領域，由于其天生的關系結構，圖數據庫/圖計算已經成為其不可或缺的工具了 。如 ， 在金融機構使用圖來進行風控管理，通過對用戶聯系人交易等數據分析，識別欺詐借貸行為 ， 規避惡意借貸風險，識別黑產群體等；或作為知識圖譜的底層，提供快速關聯查詢 ， 路徑識別推薦，融合各種異構異質數據等 。
從零開始學Graph Database：什么是圖

文章插圖
為了更真實地體驗圖在各個行業的應用 ， 也可以使用以下開箱即用的demo進行動手實踐：
  • 新冠患者軌跡追溯
  • 電商風控案例
  • 利用圖數據庫研究COVID-19論文數據集
  • 教育知識圖譜使用案例
以上案例提供了包括數據源 ， 數據建模(schema)，云上創圖，查詢或分析演示等功能 。
點擊關注 ， 第一時間了解華為云新鮮技術~

推薦閱讀