乐趣区

关于图数据库:图计算-101图计算的类型语言与系统

jiezi

背景
现实生活中的很多数据都能够建模成图（Graph）这一形象的构造。这种高效紧凑的数据模式能够示意出拓扑、属性、时序等丰盛的信息，而图计算的指标就是从图构造中挖掘出有价值的常识或法则，例如频繁模式、因果关系等。随着信息时代的到来，数据规模呈爆炸式增长，产生了对大规模的图数据进行高效解决的需要，图计算曾经成为了工业界和学术界的热点话题，并因而诞生了一系列的图计算零碎及优化钻研工作。
简单的业务场景，以致图数据的计算类型也是多种多样的。目前，存在着三种最次要的图计算类型，别离是图查问、图剖析和图学习，上面咱们就逐个地进行介绍。
图查问
通常来说，图数据十分宏大，而图数据的交互式查问只关怀其中满足条件的比拟大量的点和边。如下图所示，这些点和边会造成特定的门路，或者子图模式。例如，从一个中央到另一个中央的最优路线，或者物流的门路信息，都是典型的门路查问场景。子图模式是另一种类型的图查问，它用子图示意某种模式，而后用这个子图在全图中进行匹配查问。

                            门路查问（右）和子图查问（左）

门路查问的实质是图的遍历，通常依照如下的步骤进行：首先将图上特定的顶点设为待查点；而后每个待查点通过本人所连贯的满足条件的边找到指标端点汇合，查看指标端点是否满足查问指标；如果满足则将该指标端点放入后果集，否则将该指标端点设置为新的待查点。始终反复这样的步骤，直到没有待查点。简略来说，就是在图查问的整个过程中，依照用户指定的条件，一步一步在图上游走遍历，并最终取得想要的后果。
另一种类型的图查问，即子图查问，其实践根底是子图同构。用户须要给定待查问的子图（点、边以及它们所要满足的条件），而后从数据图上查找所有满足条件的后果，使得：每个后果是数据图上的子图；该子图和查问图是同构的；且该子图所映射的点和边满足查问图上对应点和边的查问条件。简略来说，就是在大图中去寻找用户关怀的某种特定构造。
图查问最典型的两大支流语言，别离是 Gremlin[1] 和 Cypher[2]。Gremlin 基于 Groovy，但有许多语言变体，容许开发者以 Java、Python 等编程语言原生编写查问。它既蕴含命令式也蕴含申明式的语义，能不便表白图遍历的逻辑，所以被泛滥图数据库系统采纳，例如 JanusGraph、InfiniteGraph、Cosmos DB、DataStax Enterprise(5.0+)、Amazon Neptune 等。另一种图查询语言 Cypher 则采纳了基于形容式的模式匹配。因为与 SQL 相似，具备语法简略和灵活性高的特点，因而被 neo4j、RedisGraph、AgensGraph 等零碎采纳。
例如，在蕴含 person 和 location 类型点的图中，查问与 mike 一起寓居的人，用 Gremlin 和 Cypher 编写的查问语句别离如下所示。

# Gremlin
g.V().has('name', 'mike').as('a')
.out('lives').in('lives').where(neq('a'))
.values('name')
 
# Cypher 
MATCH
(src:person{name:"mike"})-[:lives]->()<-[:lives]-(dst:person)
RETURN dst.name

比照其余类型的数据处理，图查问具备显明的计算特色。海量数据和局部性差的特点，须要零碎在分布式工作划分、负载平衡、通信调度等方面进行优化；高计算复杂度和用户的低提早要求让零碎的并发能力变得尤为重要；超点导致的内存收缩、交互环境内存受限等特点，给零碎的内存治理带来了很大的挑战。
图剖析
图查问，个别只拜访满足特定条件的大量点或边，并实时返回后果，如从某个点登程按肯定条件走两跳，返回满足条件的门路。而图剖析则个别蕴含更简单的计算，侧重于剖析、开掘全图的整体特色或实体之间的关联信息，例如把全图所有点按肯定规定进行聚类。
事实上，图论是一个已有几百年钻研历史的传统数学分支，因而无关图剖析的算法也是举不胜举。从最短门路、连通重量等经典算法，到社区发现、协同过滤、模式开掘等人工智能畛域的理论问题，图剖析被利用在了越来越多的场景中，大规模图剖析也成为了一个钻研热点。参考 GraphX，常见的图剖析算法分类包含：

  • 简略的图剖析算法

    • PageRank
    • Shortest path
    • Graph coloring
    • Connected component

  • 社区发现类的算法

    • Triangle counting
    • K-core decomposition
    • K-Truss

  • 模式匹配类的算法

    • Graph simulation
    • (Sub)graph isomorphism
    • Keyword search

  • 协同举荐类的算法

    • Alternating least squares (ALS)
    • Stochastic gradient descent (SGD)
    • Tensor Factorization

  • 构造预测类的算法

    • Loopy belief propagation
    • Max-product linear programs
    • Gibbs sampling

    2010 年 Google 公开的 Pregel[3] 零碎是首个专门用于剖析大规模图数据的分布式系统，它首次提出了以点为核心的编程模型，并催生了后续一系列的学术研究和开源零碎。这种编程模型采纳部分的、面向点的计算思维，促使用户“像点一样思考”。因为这一模型具备人造的可扩展性和并行性，因此被宽泛应用。连续这一模型的零碎也从编程接口、工作划分、执行机制等各个角度对其进行优化，如 PowerGraph[4] 的经典编程模型 GAS。另一类零碎采取了更加高级的编程模型，如 Giraph++[5] 率先提出将子图作为计算的根本单元，因此执行效率更高。GRAPE[6] 提出的 PIE 模型能够将单机图算法主动并行化，在兼具高效性能的同时，大大降低了用户的编程难度。
    图数据的复杂性，使得图剖析零碎在设计上有很多须要思考的难点，比方：如何更无效地利用底层硬件资源，如何划分数据和保护分布式一致性，更高效的执行模式和任务调度策略，更先进的计算模式和编程模型，以及更好的零碎容错机制等等。
    图学习
    图学习，即基于图的机器学习，旨在将图的构造信息整合到机器学习模型中。随着以深度学习为代表的人工智能技术广泛应用，且图构造具备更强的表达能力，图学习成为了一个热点话题，也在因果关系、可解释性方面带来了冲破停顿。当初，图学习曾经被利用在了搜寻举荐、广告、金融风控、智能交通、医疗、城市等各个领域。另一方面，图学习也面临着一些新的技术挑战，例如数据规模宏大、点和边的异构性、多模态的属性特色、构造或属性随工夫动态变化等。
    图学习的传统办法，是表征学习。图表征学习（Graph Embedding），就是将图中的每一个顶点都示意成一个低维向量，并使该向量可能尽可能多的保留图的构造和内容信息。该示意向量能够作为特色用于后续的学习工作，如链接预测、顶点分类等。下图展现了一个经典的例子，其中右边是原始的图构造，左边是表征学习失去的一种映射计划，它把图 A 中的每个顶点转化成了二维坐标系中的一个点，也就是一个二维向量。原始图中严密相连的点（即雷同色彩的点）在映射失去的坐标空间中，仍然间隔较近。

    Graph Embedding 示例 (https://dl.acm.org/doi/abs/10…)
    对于图表征学习这一问题，曾经发展了十分多的钻研工作。这些工作针对同构图、异构图、属性图、动态图等不同类型的数据，提出了各式各样的计划，包含经典算法 DeepWalk[7]、LINE[8]、Node2Vec[9] 等。这些工作的根本做法是基于随机游走生成数据，而后通过训练优化参数，生成概率模型。
    另一种图学习的重要类型是图神经网络。传统的神经网络只能解决欧式空间的问题，要求数据是残缺、参差、规定的。例如一张照片，每个像素点固定与八个点相邻，因而每个点能够对应一个等长向量，蕴含了它自身的信息和街坊信息。而图神经网络（GNN），将经典神经网络模型如 Recurrent Neural Networks（RNN）、Convolutional Neural Networks（CNN）等扩大到了图上。它解决的是非欧式空间的问题，这是因为图构造是不规则的，每个点的街坊个数不一样，导致部分的维度不定长。与图表征学习试图学习出每个点的 embedding 不同，图神经网络的目标其实是学习出聚合函数，所有点通过同一个函数就能够利用部分信息计算出本身的 embedding。即便是图构造发生变化，甚至是齐全新的图，也能用原来的函数计算出有意义的后果。无关图神经网络，也曾经诞生了一系列经典算法，读者能够浏览无关文献 [10] 做进一步的理解。
    总结
    因为图数据具备依赖性强、局部性差、不规则散布、构造多样等特点，导致传统的数据并行零碎难以实用。另外，不同类型的计算特色和计算范式，也给图计算零碎的设计带来了多元化的要求。
    一个现实的图计算零碎，应该兼具通用性、高性能和易用性。在通用性上，咱们心愿它反对图查问、图剖析、图学习等多种类型的计算，同时，兼容语言规范与业界生态。在性能方面，能够实现低延时的交互式查问，具备高性能的图剖析能力，反对大规模图存储，提供高可扩展性等。在易用性上，应该提供对立的编程模型，高度形象、简略灵便的语言，并且实现零碎部署简略、集群方便管理，提供可视化的界面等等。
    应答图计算零碎面临的种种挑战、满足实在利用场景的需要、提供一站式高效的解决方案，正是 GraphScope 的设计初衷。GraphScope 零碎提出了多个重要的创新性技术，同时也在继续疾速迭代着，曾经证实在多个要害互联网畛域（如风控、电商举荐、广告、网络安全、常识图谱等）实现了重要的业务新价值，并致力于助力越来越多的重要利用场景。
    参考资料
    [1]Gremlin: https://tinkerpop.apache.org/…
    [2]Cypher: https://dl.acm.org/doi/abs/10…
    [3]Pregel: https://dl.acm.org/doi/abs/10…
    [4]PowerGraph: https://www.usenix.org/confer…
    [5]Giraph++: https://dl.acm.org/doi/abs/10…
    [6]GRAPE: https://dl.acm.org/doi/abs/10…
    [7]DeepWalk: https://dl.acm.org/doi/abs/10…
    [8]LINE: https://dl.acm.org/doi/abs/10…
    [9]Node2Vec: https://dl.acm.org/doi/abs/10…
    [10] 无关文献: https://www.sciencedirect.com…

退出移动版