持续创造，加速生长！这是我参与「日新计划 10 月更文挑战」的第1天，点击查看活动详情

本文共享自华为云社区《从零开始学Graph Database（1）》，作者：弓乙 。

本文从零开始引导与大家一同学习图常识。期望大家能够经过本教程学习怎么运用图数据库与图核算引擎。本篇将以华为云图引擎服务来辅助大家学习怎么运用图数据库与图核算引擎。

基础概念

什么是图？

首要，咱们需求清晰图 Graph的概念。

这里的图，是graph, 是graphical，而不是graphic。即图处理的是联系问题，而不是图片。咱们处理是联系问题，而非视觉cv问题。

从零开始学Graph Database：什么是图

在离散数据中，有专门研究图的图论。包括子图相关，染色，路径，网络流量等问题。

在核算机科学中，咱们将图笼统为一种数据结构，即由点,边构成的调集。咱们能够将实际世界的任意一种包括联系的实体用图来笼统概括。

咱们通常把图的问题界说为G=(V,E,)：

V:是节点的调集
E:是边的调集
: E->{(x,y) | (x,y)∈ V^2 ∪ x≠y }是一个相关函数，它每条边映射到一个有极点组成的有序对上。

下图是一个运用图来描绘的交际网络。点代表了人，边代表了人和人之间为朋友联系。在构建了这样一个交际网络以后，咱们能够经过运用图查询和算法使得图数据产生价值。如运用k跳查询,共同街坊,node2vec等来为交际网络中的用户进行老友引荐。

从零开始学Graph Database：什么是图

// 老友引荐逻辑
试想咱们为李雷引荐老友，思路是：向他引荐其老友的老友。可是需求过滤掉自身李雷的老友。
如上图，小明即是李雷的老友，也是李雷老友的老友。所以在这种状况中，咱们不需求再向李雷引荐小明了。
而是引荐 小霞和小刚。
这种略微有点复杂的引荐思路，能够运用查询言语进行。
以gremlin为例：
g.V("李雷").repeat(out("friend").simplePath().where(without('1hop')).store('1hop')).
times(2).path().by("name").limit(100)

能够运用图做什么？

传统上咱们运用图来处理一些数学问题。比方图论起源于著名的柯尼斯堡七桥问题, 该问题被欧拉推广为：怎样判别是否存在着一个恰好包括了一切边，且没有重复的路径。即一笔画问题。

从零开始学Graph Database：什么是图

欧拉证明了以下定理，并处理了一笔画问题：

连通的无向图G有欧拉路径（一笔画）的充要条件是：G中的奇点的数目等于0或2。
（奇点：衔接边数为奇数的极点。）

咱们能够用一笔画问题来处理七桥问题，从模型能够看出来，七桥问题中的奇点数目为4个，明显不满足一笔画的充要条件。故七桥无法在一切桥都只能走一遍的前提下，把这个地方一切的桥都走遍。

当然了，图并非只能处理这类图论经典问题(如 四色问题，马的遍历问题，邮递员问题, 网络流问题 )，只要能够将研究方针表明为图结构，就能运用图的特点来处理问题，甚至大部分状况下，并不需求运用到多么深邃的算法。

查询与算法

图查询

这里的查询一般指代运用原生图查询言语进行的图上方针的查询操作。如neo4j的Cypher，tinkerpop的Gremlin等。Cypher与Gremlin也是业界运用较多的查询言语，Cypher是侧重于pattern matching的声明式言语，而Gremlin则是根据groovy的函数式编程言语，着重graph traversal的重要性。

从零开始学Graph Database：什么是图如：

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

以上两种写法等价，只是运用的图查询言语有区别。

图算法

除了清晰规则的查询外，咱们也能够运用图算法对图进行剖析。究竟图中包含的信息量远比表面看上去多，这个时分咱们期望经过图算法揭示图中更多的信息，如发现节点之间隐含联系，剖析节点重要性，对事务场景进行行为预测等。

下表列出了现在不同类型具有代表性的图算法：

从零开始学Graph Database：什么是图实际的场景中，咱们需求同时统筹算法的作用和履行成本。这也是许多运用场景所面对的trade-off问题。正如咱们前面所说，大部分状况下不需求用到十分深邃的图算法，特别是在在线使命中，咱们更垂青时延和功率。

从零开始学Graph Database：什么是图

亦或许说，在线场景中，重查询轻算法；而在离线场景中，重算法而轻查询。

事实上，图查询与图算法的边界并没有那么泾渭分明。或许说，图算法算是某种程度上的特殊图查询。咱们普遍认为算法较查询需求更多的核算资源，会占用更多的CPU与内存。

从零开始学Graph Database：什么是图

比方上图的多跳查询和BFS algorithm，本质上是同一个查询。灰色模块显示的是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 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"
    }
}

大部分的工业运用场景中，图更多地扮演着数据库的人物，用来办理某个范畴内的联系数据。用户大多看中图对于多跳相关剖析能力，以及数据间头绪的整理归集，剖析和可视化。

特别的，在某些笔直范畴，由于其天然生成的联系结构，图数据库/图核算已经成为其不可或缺的工具了。如，在金融机构运用图来进行风控办理，经过对用户联系人交易等数据剖析，识别诈骗假贷行为，躲避歹意假贷风险，识别黑产群体等；或作为常识图谱的底层，提供快速相关查询，路径识别引荐，融合各种异构异质数据等。

从零开始学Graph Database：什么是图

为了更真实地体验图在各个职业的应用，也能够运用以下开箱即用的demo进行着手实践：

  • 新冠患者轨迹追溯

  • 电商风控事例

  • 运用图数据库研究COVID-19论文数据集

  • 教育常识图谱运用事例

以上事例提供了包括数据源，数据建模(schema)，云上创图，查询或剖析演示等功能。

点击重视，第一时间了解华为云新鲜技能~