精华 图算法系列《第三章 图平台与处理》
发布于 1 个月前 作者 feng_neo4j 212 次浏览 来自 分享

在本章中,我们将快速介绍图处理的不同方法和最常见的平台。我们将更仔细地研究本书中使用的两个平台,Apache Spark和Neo4j,以及它们何时适合不同的需求。包括平台安装指南,这样为接下来的几章做好准备。

图平台和处理注意事项

图分析处理具有结构驱动、全局聚焦、难以解析等独特的计算特性。在本节中,我们将讨论图平台和处理的一般注意事项。

平台注意事项

垂直扩展(scale up)和水平扩展(scale out)之间,一直是有争论的。应该使用功能强大的多核、大内存机器,并专注于高效的数据结构和多线程算法吗?或者,投资在分布式处理框架和相关算法上?

一种有用的评估方法是COST(Configuration that Outperforms a Single Thread),由F. McSherry、M. Isard和D. Murray在一篇文献《Scalability! But at What COST?》中提出。COST给我们提供了一种将系统的可伸缩性与系统引入的开销进行比较的方法。它核心概念是,经过算法优化和数据结构优化的良好配置系统,会优于一般性目标的水平扩展解决方案。这是一种测量性能得分的办法,不需要为低配机器增加并行。将可扩展性和有效利用资源的这两点区分开,将有助于我们建立一个明确为我们需求而配置的平台。 在这样的配置方法下,图平台的的一些高度集成的解决方案,如优化算法、处理和内存,可以更紧密地协调工作。

处理过程的考虑

有多种表示方法来表达数据处理过程,比如,流处理或批处理,或者是以记录存储的数据上Map-Reduce范式。不过,对于图数据,也有一些方法将图结构中内在的数据依赖性整合到它们的处理中: image.png

image.png Pregel Pregel是一个以节点为中心、容错的并行处理框架,由Google创建,用于对大型图进行性能分析。pregel基于批量同步并行(bulk synchronous parallel, BSP)模型。BSP包含不同的计算和通信阶段,这一点简化了并行编程。 Pregel在BSP上添加了一个以节点为中心的抽象层,算法通过该抽象层计算来自每个节点的附近节点的传入消息的值。这些计算在每次迭代中执行一次,可以更新节点值并向其他节点发送消息。这些节点还可以在通信阶段将消息打包进行传输,这有助于减少网络通信的数量。当再没有新消息或达到设置的限制时,算法完成。

这些应用于图的方法中,大多数都需要整个图才能进行有效的交叉拓扑运算。这是因为分离的或者分布的图数据会导致工作实例之间大量的数据传输和重组(reshuffling)。这对于许多算法来说,因为需要迭代处理全局的图结构,这会带来一些麻烦。

有代表性的平台

有几种平台满足图处理的要求。传统上,图计算引擎和图数据库之间是分离的,这要求用户根据其流程需要操纵数据:

图计算引擎 图计算引擎是只读的、非事务性的引擎,专注于高效执行迭代图分析和整个图的查询。图计算引擎支持图算法的不同定义和处理范例,例如以节点为中心(例如,Pregel、Gather-Apply-Scatter)或基于MapReduce的方法(例如,PACT)。这些引擎的例子有Giraph、GraphLab、Graph-Engine和Apache Spark。

图数据库 从事务性的背景来看,图数据库关注点集中在使用较小的查询进行快速的写入和读取,这些查询通常接触到图的一小部分。它们的优势在于操作健壮性和对许多用户的高并发和可扩展性。

选择我们所需的平台

选择一个生产平台需要考虑很多因素,例如要运行的分析类型、性能需求、现有环境和团队偏好。我们在本书中使用Apache Spark和Neo4j来展示图算法,因为它们都提供了独特的优势。 Spark是一个扩展和以节点为中心的图计算引擎的例子。它的计算框架和库支持各种数据科学工作流,因而很受欢迎。当如下情形满足的时候,Spark可能是一个正确的选择:

  • 算法基本上是可并行或可分的。
  • 算法工作流需要使用多种工具和语言进行“多语言”操作。
  • 分析可以在批处理模式下脱机运行。
  • 图表分析是针对未转换为图表格式的数据。
  • 团队需要并具备编码和实现自己算法的专业知识。
  • 团队很少使用图算法。
  • 团队倾向于将所有数据和分析保存在Hadoop生态系统中。

Neo4j图平台紧密集成了图数据库和以算法为中心的处理,并针对图进行了优化。它在构建基于图的应用程序方面很受欢迎,并且包含一个针对其本地图数据库进行优化的图算法库。当如下情形满足的时候,Neo4j可能是一个正确的选择:

  • 算法更具迭代性,需要良好的内存配置。
  • 算法和结果对性能敏感。
  • 图分析针对复杂的图数据和/或需要深路径遍历。
  • 分析/结果与事务性工作负载集成。
  • 用于为已有的图增加更多的属性。
  • 团队需要与基于图的可视化工具集成。
  • 团队喜欢预先打包和支持的算法。 最后,一些组织同时使用Neo4j和Spark进行图处理:Spark用于大规模数据集和数据集成的高级过滤和预处理,Neo4j用于更具体的处理和与基于图的应用程序的集成。

Apache Spark

Apache Spark(或简写成为Spark)是一个用于大规模数据处理的分析引擎。它使用一种叫做DataFrame的抽象表来表示和处理行和列数据,其中行有标识,列有类型。该平台集成了各种数据源,并支持Scala、Python和R等语言。Spark支持各种分析库,如图3-1所示。它基于内存的系统能使用高效的分布式图计算。

GraphFrames是Spark的一个图处理库,它在2016年继承了GraphX,但它与核心Apache Spark是分离的。GraphFrames基于GraphX,但使用DataFrame作为其基础数据结构。GraphFrames支持Java、Scala和Python作为编程语言。2019年春天,“Spark Graph: Property Graphs, Cypher Queries, and Algorithms”提案被通过(见“Spark图的演变”)。我们希望这能将使用DataFrame框架和Cypher查询语言的大量特征引入到核心Spark项目中。不过,在本书中,我们的示例将基于Python API(PySpark),因为它目前在Spark数据科学家中很受欢迎。

image.png 图3-1.Spark是一个开源的分布式通用集群计算框架。它包括几个用于不同工作负载的模块。

Spark图的演变 Spark Graph Project是由Databricks和Neo4j的Apache项目贡献者发起的一项联合倡议,旨在将对DataFrames、Cypher和对DataFrames算法的支持作为3.0版本的一部分引入核心Apache Spark项目。 Cypher最初是在Neo4j中实现的一种声明性图查询语言,但通过OpenCypher项目,它现在被多个数据库供应商和一个开源项目(Cypher for ApacheSark,CAPS)使用。 在不久的将来,我们期望使用CAPS加载和投影图数据作为Spark平台的一个集成部分。我们将在Spark图项目实现之后发布Cypher示例。 这一发展不会影响本书所涵盖的算法,但可能会为如何调用过程添加新的功能。图算法的基础数据模型、概念和计算将保持不变。

节点和关系表示为DataFrame,每个DataFrame包含节点唯一ID和每个关系的源节点和目标节点。我们可以看到表3-1中的节点DataFrame和表3-2中的关系DataFrame的示例。基于这些DataFrame的GraphFrame将有两个节点,即JFK和SEA,以及一个从JFK到SEA的关系。

表3-1 节点DataFrame image.png 表3-2 关系DataFrame image.png

节点DataFrame必须具有ID列。此列中的值用于唯一标识每个节点。关系DataFrame必须有SRC和DST列。这些列中的值描述连接的节点,并应引用出现在节点数据框的ID列中的条目。

节点和关系DataFrame可以使用形式数据源(包括Parquet、JSON和CSV)来加载。查询的话,可以一同使用PySpark API和Spark SQL。

GraphFrame还为用户提供了一个扩展点来那些非实现开箱即用(not out of the box)的算法。

安装Spark

你可以从Apache Spark网站下载Spark。下载后,需要安装以下库才能从Python执行Spark任务:

pip3 install pyspark graphframes 注意,译者在python2上安装graphframes提示版本不足,建议使用python3.6或更高的版本。

运行pyspark,来启动pyspark REPL(交互解释器,Read-Eval-Print Loop):

pyspark --driver-memory 2g --executor-memory 6g --packages graphframes:graphframes:0.7.0-spark2.4-s_2.11 其中 --package是必须要带上的,否则会出现错误。这个参数代表了当前的应用程序还用到graphframes:0.7.0-spark2.4-s_2.11所对应的jar包。该jar包会自动被加载。对于这个参数不熟悉的读者,请用pyspark —help来了解更详细的信息。

image.png

虽然Spark作业应该在一个机器集群上执行,但是为了演示目的,我们只在一台机器上执行这些作业。在由Bill Chambers和Matei Zaharia(O’Reilly)撰写的《Spark: The Definitive Guide》中,你可以了解更多关于在生产环境中运行Spark的信息。

现在你已经准备好学习如何在Spark上运行图算法了。

Neo4j图平台

Neo4j图平台支持图数据的事务处理和分析处理。它包括图存储和使用数据管理和分析工具进行计算。集成工具集位于通用协议、API和查询语言Cypher之上,为不同的用途提供有效的访问,如图3-2所示。 image.png 图3-2.Neo4j图平台是围绕支持事务应用程序和图分析的本机图数据库构建的。

在这本书中,我们将使用Neo4j图算法库。库作为插件安装在数据库中,并提供一组用户定义的过程(User-defined procedures),这些Procedure可以通过Cypher查询语言执行。

图算法库包括支持图分析和机器学习工作流的并行算法版本。算法在基于任务的并行计算框架之上执行,并针对Neo4j平台进行了优化。对于不同的图大小,内部实现可以扩展到数百亿个节点和关系。

结果可以作为元组流传输到客户机,表格结果可以用作进一步处理的驱动表。结果还可以作为节点属性或关系类型有效地写回数据库。

在这本书中,我们还将使用Neo4J Awesome Procedures on Cypher(APOC)库。APOC由450多个过程和函数组成,用于帮助完成数据集成、数据转换和模型重构等常见任务。

安装NEO4j

开发人员可以便利地使用Neo4j Desktop,它包含一个本地的NEO4j数据库。Neo4j Desktop可以从Neo4j网站上下载。一旦安装并启动了Neo4j Desktop,图算法和APOC库就可以作为插件(plugins)安装。在左侧菜单中,创建一个项目并选择它。然后在要安装插件的数据库上单击“管理”。在插件选项卡上,你将看到几个插件的选项。单击图算法和APOC的安装按钮。 见图3-3和3-4。 image.png 图3-3.安装图算法库

image.png 图3-4.安装APOC库 Jennifer Reif在她的博客文章“Explore New Worlds—Adding Plugins to Neo4”中更详细地解释了安装过程。现在你已经准备好学习如何在Neo4j中运行图算法了。

总结

在前面的章节中,我们已经描述了为什么图分析对于研究现实网络很重要,并研究了基本的图概念、分析和处理。这为我们了解如何应用图算法打下了坚实的基础。在下一章中,我们将开始了解如何使用Spark和Neo4j中的示例运行图算法。

《图算法》的连载。分享给对图计算感兴趣的朋友们。 公众号:《 Medical与AI的故事》 原文链接:https://mp.weixin.qq.com/s/noI1BHnyeFzEe6-cChlAkg

回到顶部