从零开始学Graph Database：什么是图( 二 ) _生活百科

文章插图
亦或者说，在线场景中，重查询轻算法；而在离线场景中，重算法而轻查询。
事实上，图查询与图算法的边界并没有那么泾渭分明。或者说，图算法算是某种程度上的特殊图查询。我们普遍认为算法较查询需要更多的计算资源，会占用更多的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 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"}}大部分的工业使用场景中，图更多地扮演着数据库的角色，用来管理某个领域内的关系数据。用户大多看中图对于多跳关联分析能力，以及数据间脉络的整理归集，分析和可视化。
特别的，在某些垂直领域，由于其天生的关系结构，图数据库/图计算已经成为其不可或缺的工具了。如，在金融机构使用图来进行风控管理，通过对用户联系人交易等数据分析，识别欺诈借贷行为，规避恶意借贷风险，识别黑产群体等；或作为知识图谱的底层，提供快速关联查询，路径识别推荐，融合各种异构异质数据等。