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

摘要：本文從零開始引導與大家一起學習圖知識。希望大家可以通過本教程學習如何使用圖資料庫與圖計算引擎。本篇將以華為雲圖引擎服務來輔助大家學習如何使用圖資料庫與圖計算引擎。本文分享自華為雲社區《從零開始學Graph Database（1）》，作者：弓乙。基礎概念什麼是圖？首先，我們需要明確圖 ...

摘要：本文從零開始引導與大家一起學習圖知識。希望大家可以通過本教程學習如何使用圖資料庫與圖計算引擎。本篇將以華為雲圖引擎服務來輔助大家學習如何使用圖資料庫與圖計算引擎。

本文分享自華為雲社區《從零開始學Graph Database（1）》，作者：弓乙。

基礎概念

什麼是圖？

首先，我們需要明確圖 Graph的概念。

這裡的圖，是graph, 是graphical，而不是graphic。即圖處理的是關係問題，而不是圖片。我們解決是關係問題，而非視覺cv問題。

在離散數據中，有專門研究圖的圖論。包含子圖相關，染色，路徑，網路流量等問題。

在電腦科學中，我們將圖抽象為一種數據結構，即由點,邊構成的集合。我們可以將現實世界的任意一種包含關係的實體用圖來抽象概括。

我們通常把圖的問題定義為G=(V,E,φ)：

V:是節點的集合
E:是邊的集合
φ: E->{(x,y) | (x,y)∈ V^2 ∪ x≠y }是一個關聯函數，它每條邊映射到一個有頂點組成的有序對上。

下圖是一個使用圖來描述的社交網路。點代表了人，邊代表了人和人之間為朋友關係。在構建了這樣一個社交網路以後，我們可以通過使用圖查詢和演算法使得圖數據產生價值。如利用k跳查詢,共同鄰居,node2vec等來為社交網路中的用戶進行好友推薦。

// 好友推薦邏輯
試想我們為李雷推薦好友，思路是：向他推薦其好友的好友。但是需要過濾掉本身李雷的好友。
如上圖，小明即是李雷的好友，也是李雷好友的好友。所以在這種情況中，我們不需要再向李雷推薦小明瞭。
而是推薦 小霞和小剛。

這種稍微有點複雜的推薦思路，可以使用查詢語言進行。
以gremlin為例：
g.V("李雷").repeat(out("friend").simplePath().where(without('1hop')).store('1hop')).
times(2).path().by("name").limit(100)

可以使用圖做什麼？

傳統上我們使用圖來解決一些數學問題。比如圖論起源於著名的柯尼斯堡七橋問題, 該問題被歐拉推廣為：怎樣判斷是否存在著一個恰好包含了所有邊，且沒有重覆的路徑。即一筆畫問題。

歐拉證明瞭以下定理，並解決了一筆畫問題：

連通的無向圖G有歐拉路徑（一筆畫）的充要條件是：G中的奇點的數目等於0或2。

（奇點：連接邊數為奇數的頂點。）

我們可以用一筆畫問題來解決七橋問題，從模型可以看出來，七橋問題中的奇點數目為4個，顯然不滿足一筆畫的充要條件。故七橋無法在所有橋都只能走一遍的前提下，把這個地方所有的橋都走遍。

當然了，圖並非只能解決這類圖論經典問題(如四色問題，馬的遍歷問題，郵遞員問題, 網路流問題 )，只要能夠將研究對象表示為圖結構，就能利用圖的特點來解決問題，甚至大部分情況下，並不需要使用到多麼高深的演算法。

查詢與演算法

圖查詢

這裡的查詢一般指代使用原生圖查詢語言進行的圖上對象的查詢操作。如neo4j的Cypher，tinkerpop的Gremlin等。Cypher與Gremlin也是業界使用較多的查詢語言，Cypher是側重於pattern matching的聲明式語言，而Gremlin則是基於groovy的函數式編程語言，強調graph traversal的重要性。

如：

1、gremlin

g.V("李雷").outE('friend').has('age',gt(30)).otherV().where(out('friend').(hasId('李雷'))).limit(100)

2、cypher

match (a)-[r1:friend]->(b)-[r2:friend]->(c) where a.mid='李雷' and r1.age>30 and a=c return id(b) limit 100

以上兩種寫法等價，只是使用的圖查詢語言有區別。

圖演算法

除了明確規則的查詢外，我們也可以利用圖演算法對圖進行分析。畢竟圖中蘊含的信息量遠比錶面看上去多，這個時候我們希望通過圖演算法揭示圖中更多的信息，如發現節點之間隱含關係，分析節點重要性，對業務場景進行行為預測等。

下表列出了目前不同類型具有代表性的圖演算法：

實際的場景中，我們需要同時兼顧演算法的效果和執行成本。這也是很多使用場景所面臨的trade-off問題。正如我們前面所說，大部分情況下不需要用到非常高深的圖演算法，特別是在線上任務中，我們更看重時延和效率。

亦或者說，線上場景中，重查詢輕演算法；而在離線場景中，重演算法而輕查詢。

事實上，圖查詢與圖演算法的邊界並沒有那麼涇渭分明。或者說，圖演算法算是某種程度上的特殊圖查詢。我們普遍認為演算法較查詢需要更多的計算資源，會占用更多的CPU與記憶體。

比如上圖的多跳查詢和BFS algorithm，本質上是同一個查詢。灰色模塊顯示的是gremlin與cypher的查詢方法，藍色模塊顯示的是不同圖資料庫中BFS演算法的執行方式。但他們的結果都是一致的，均為點Tom的三度鄰居。也就是在業界，N跳查詢即可以作為廣度/深度優先演算法/khop演算法單列出來，也可以作為圖遍歷/圖查詢中一種常用模式存在。

除此以外，subgraph matching也是一個圖查詢與圖演算法同時存在的研究課題。如上圖，我們輸入目標子圖q，在圖G中尋找其同構圖，這其實是一個NP-Hard問題。

當然了，即使子圖查詢是一個非常困難的問題，大部分圖查詢語言還是提供了相應的match語法用於基於模式匹配的搜索功能，如neo4j使用的Cypher，或者支持指令式和聲明式查詢的Gremlin。而在圖演算法領域，subgraph matching則是一個極重要，極複雜的研究課題。下表中列出來一部分具有代表性的子圖匹配演算法的分類。(來源於paper[In-Memory Subgraph Matching: An In-depth Study])。

圖的應用

下麵讓我們從一個具體的例子中體會一下圖在場景中的使用。

假設我們需要在社交關係中為用戶推薦好友，在不同的場景中，可以使用不同類別的查詢和演算法。如果用於線上推薦，我們可以將二度鄰居作為其推薦結果，即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 l


louvain:
[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"
    }
}