Spark生态系统中的图数据分析知识

图结构可有效表示稀疏矩阵，因而图数据分析可用于实现大数据分析。对于Spark生态系统中的图处理系统GraphX，《Spark GraphX in Action》一书给出了详细的教程和典型用例，将教会读者如何使用GraphX和GraphFrames进行图分析。本文是Info对该书作者的访谈，内容包括图数据及分析技术、GraphX高效程序开发、图数据分析的趋势等。

如何定义图数据?

Michael Malak：就事论事，图结构看上去并非像股价图那样，而是边和点的集合。但这只是一种模糊的数学抽象。更具体地说，在书的第一章中我们将真实世界中的图划分为五类：网络、树、类RDBMS结构、稀疏矩阵以及其它杂七杂八的结构。

Robin East：传统的数据分析方法侧重于事物本身，即实体，例如银行交易、资产注册等等。而图数据不仅关注事务，还关注事物之间的联系。例如，如果有一个呼叫记录告诉我张三曾打电话给李四，这样就可以将张三和李四关联起来。这种关联关系提供了与两者相关的有价值信息，而这样的信息是不可能仅从两者单纯的个体数据中获取的。

图数据分析与传统数据的处理的不同之处

Malak：正如我们在书的第一章中所描述的，RDBMS不足以有效地处理图路径遍历运算，因为该运算需要进行大量的自连接运算。用于稀疏矩阵处理是另一个图分析展示出良好性能的领域，在书中机器学习相关的第七章中对此有所描述。

East：图分析事实上是一系列的实践，这些实践侧重于对数据条目间关联信息内容的描绘。在不同实体间连接模式可见的情况下，对不同数据间关联建模提供了十分强大的能力。再次使用电话呼叫记录作为例子，当我们对由不同人所做的不同呼叫而组成的“网络”进行分析时，就可以去构建具有不同交互类型的图形。在一些情况下，我们可以使用数据的结构信息对不同的行为进行分隔(例如区分犯罪与否)。

图数据分析是如何促进大数据和预测分析?

Malak：对于已有的大数据，首先你需要从数据中抽取出结构化数据，通常是关系模型或者图模型。一些问题可自然地表示为图问题，例如地图中的路由查找、社会网络分析(尤其是在一个社会网络图中发现意见领袖)。所有的机器学习都是关于做预测的，而在书中关于机器学习的一章也是内容最长的。这一章中展示了一些使用图数据上机器学习的方法。

East：基于大数据的预测分析的效能，事实上取决于抽取许多不同类型的特征作为预测算法输入的能力。书中我最喜欢的例子就是对原有垃圾邮件检测的全新实现。原问题是使用逻辑回归检测垃圾页面，但是我们采用了一种有趣的新思想，即Truncated Page Rank算法，该算法使用基于图的输入特性扩展了传统的输入特性。书中展示了如何在GraphX中实现这个模型。

GraphFrames的工作机制

Malak：作为Apache Spark生态系统的一部分，GraphX是Spark的官方图处理系统。即使在Spark 2.0中也是如此。GraphX基于RDD技术，每条边和每个节点均由一个RDD表示。GraphFrames作为spark-packages.org所提供的附加软件，依然是基于DataFrames的。

将GraphX与GrapeFrames进行对比，这很大程度上就是RDD与DataFrames的对比。使用DataFrames(对于GraphFrames也一样)，Catalyst查询计划器、Tungsten sun.misc.unsafe原始内存布局、即时字节码生成会得到潜在的巨大性能提升。就即时字节码生成而言，Spark 2.0对整个处理流水线而非keyhole代码生成进行了改进，这取得了相比于Spark 1.6 Dataframes十倍的性能提升。GraphX具有内部路由表，这便利了三元组(triplet)的构建;GraphFrames虽然缺少内部路由表的设计，但从DataFrames所免费获取的性能改进弥补这一不足，并给出了更大的性能优势。

GraphFrames还具有使用Neo4j Cypher语言的子集和DataFrames对SQL语言的支持进行组合查询的功能。最后一点，GraphFrames提供了对Python和Java语言的绑定，这对于喜欢Python语言和更适应Java开发的程序员是一个喜讯。但是GraphX的痛点在于仅官方支持Scala语言(虽然在书中我们也展示了如何跨域数以百计的关卡实现在开发中对Java的支持)。我们在第十章中涵盖了GraphFrames相关内容，并给出了一个有趣的例子，就是去查找本应存在于Wikipedia中的缺失链接。

East：弹性分布式数据集(Resilient Distributed Datasets，RDD)是Spark提供的核心底层数据结构。在GraphX中，RDD用于表示图中的边和节点。另一方面，DataFrames是高层数据接口，提供了一些面向开发人员的有用特性，例如SQL接口。DataFrames还提供了若干性能优化。GraphFrames使用DataFrames表示图，而非RDD。

GraphFrames中添加了若干GraphX所不具有的关键特性，例如查询结构、Python属性函数(Property)和Java API。无论如何，从一种表示方式转化为另一种都是可能的，事实上这也是PageRank、连通分量等标准算法的实现方法。

四种不同的图数据相关的概念

记者：你们能介绍一下NoSQL图数据库、图数据查询、图数据分析和图数据可视化这四种图数据相关的概念吗?

Malak：我在2016年6月的Spark峰会上做过一个报告，报告中对图技术给出了一个很好的“频谱”展示。频谱图的一端是真正OLTP风格的NoSQL图数据库，包括Neo4j、Titan、OrientDB等。另一端是OLAP风格的图处理和数据分析系统，包括GraphX、GraphLab等。图查询涉及的范围处于该频谱图的中央。NoSQL图数据库和GraphFrames也都可以进行查询，但是GraphX在查询方面非常有局限性。

无论OLTP风格图数据库或是OLAP风格的图处理和分析系统，都可以应用图数据库可视化技术，所以图数据可视化的领域范围与该频谱图是相互正交的。在本书中我们论及两种特定的技术：Gephi和组合使用Zpeppelin与d3.js。需要指出的是，图可视化的用例与关系数据可视化的用例之间有很大的差异。关系数据可视化的目标是对数据取得直观的了解，而图数据可视化的目标在于对数据或算法进行调试。

East：正如Michael已提到的，现在已有一些不同的图数据库，它们满足了一系列不同用例的需求。值得强调的是GraphX提供了内存中的图处理功能，而非数据库功能。可以使用GraphX从一系列数据源中构建基于内存的图，这样的数据源中可能包括对NoSQL图数据库的查询。实际上后一种组合的潜在应用前景巨大。

图可视化是一个需要整整一本书去阐述的话题，很高兴看到Manning出版社已经于前期初版了这样的一本书，那就是Corey Lanum所著的《Visualizing Graph Data》。

最佳解决方案用例

记者：在哪些受欢迎的用例数据处理中，图数据处理是更好解决的方案?

Malak：应用GraphX的典型代表性算法是PageRank。一些用例使用或者拓展了RageRank算法，这样的用例超越了Google将PageRank用于搜索排序的应用，可用于在论文引用网络(书中给出了一个实例)和社会网络这样类型的图中查找意见领袖。在书中我们还展示了如何将PageRank转化为另一种称为Truncated Page Rank的算法，这种算法可用于发现垃圾网页链接农场。

除了PageRank之外，我们在书中还给出了一些经典图算法的实现，这些经典图算法提出于半个世纪之前，其中包括了最短路径(例如地理空间映射)、旅行推销员问题和最小生成树等算法。最小生成树问题听上去很学术，但是在书中我们展示了它的一个有意思的应用，就是辅以MLlib提供的word2vec算法，从语料库中自动建立层次化概念分类结构。一些Spark中的机器学习算法实际上是GraphX实现的，其中包括：一种类似于ALS可用于推荐系统的算法SVD++、幂迭代聚类(Power Iteration Clustering，PIC)等。在书中给出了使用PIC算法实现计算机视觉中图像分割的例子。

East：在数据间关联与数据项本身同等重要的情况下，就应该考虑使用图方法进行数据处理。虽然有时使用传统方法也能实现这种图处理，但是这样的实现方法很快会变成一种繁重工作，因为即使对于十分简单的结构，这样的方法也需要付出很大的努力才能实现。与之相对比的是，对于互连的数据，GraphX等图处理系统提供了非常自然的数据表示和交互方式。

Spark机器学习程序库的用例

记者：通过提供面向批处理、流数据和图数据处理的程序库，Spark给出了一种统一的大数据处理架构。Spark还提供了机器学习程序库。你们能介绍一些同时使用所有这些程序库的用例吗?

Malak：在书里关于机器学习的一章中，我们描述了在MLlib中使用GraphX的方法，但是其中所提及的方法都是批处理应用。类似于Spark中的任何其它对象，在GraphX和GraphFrames中图也是不可变的对象，不可以在图中增量地添加边或节点。虽然Spark Streaming也是基于不可变数据，但是它通过实现对关系数据的小型批处理方法使得流数据处理成为可能，小型批处理实现了类似于微型关系表的功能，这种微型表比微型图更加有用。在《Spark GraphX in Action》一书出版后，GraphX的创立者Ankur Dave在Spark峰会上展示了一个称为Tegra的研究项目，该项目为实现对增量流数据的更新，重写了GraphX的代码(该项目与Spark Streaming无关)。但是我并不相信当前Tegra的代码已经公开可用。

East：在线欺诈检测就是这样的一个领域。考虑到欺诈攻击的快速演变特性，预测分析需要使用最近五分钟或者更短时间内所生成的特性。此外将图模型加入到特征混合中的方法，具有实现更加有效的预测算法的潜力。

比GraphX更加高效的技术

Malak：一个原则就是审慎地掌控缓存和RDD血统(lineage)。鉴于GraphX程序多为实现迭代运算，该原则对于性能问题是尤其重要的。其它一些典型的Spark技术对性能优化也有效，例如选取适当的序列化程序。

East：当然首要的是了解Spark的工作机制，以及如何对进程进行监控以了解系统运行状态。Spark提供的基于Web的GUI可以实时展示系统运行状态，为此必须了解如何最大化地去使用这些工具。程序有很多不同的优化方向，例如缓存、序列化、监测点等，但是理想情况下只有在你理解你的应用是如何执行的，才可以应用这些优化方向。

Spark GraphX程序库实现中还有哪些缺失特性?

Malak：书中第八章专用于阐述“缺失的算法”，其中包括：PDF文件的读取、图的合并、孤立节点的滤除、全局聚类参数的计算等。此外，为加速GraphX程序运行，GraphX的创建者Ankur Dave建立了一个称为IndexedRDD的程序包。该程序包尚未集成到Apache Spark的发布版本中，因而在某种程度上也可以说是GraphX所“缺失”的。在第八章中我们展示了如何将IndexedRDD集成到GraphX程序中，以实现程序性能的提高。

East：可能协同使用Spark Streaming时需要对图的增量更新的支持，所以大家时常会提出需要此特性。鉴于当前GraphX的数据结构是不可变的，因而增量更新意味着重新创建整个图，这是一个十分耗时的过程。

图数据处理领域中未来趋势

Malak：一个发展趋势将会是同时可处理OLAP和OLTP类型应用的图系统。在上面提到过我在2016年6月Spark峰会上给出的频谱图，其中很明显可以看出NoSQL图数据库在对整个频谱的覆盖上遥遥领先。但是对于哪一种特定的NoSQL图数据库将会成为最终胜出者的问题，Neo4j、Turi(或Dato、GraphLab)、OrientDB、Titan、Oracle PGX等都是潜在的胜出者。其中GraphX的一个显著优势是，对于已经部署了Spark集群的系统，无需再付出额外的安装和管理代价。而当前Spark集群已在很多公司中得以部署。因而与Spark的集成将会成为影响任何未来可能处于统治地位的图技术的关键因素。

East：我认为有两个领域值得密切关注。第一个领域是在图数据库与图处理架构间的紧密集成。这可通过Neo4j这样的图数据库与Spark这样的图处理系统间的无缝互操作实现，或许这些功能也可出现在同一产品中。

另一个领域是图算法与主流机器学习算法两者间更加紧密地集成。当前一些程序库只是侧重于其中的一方(GraphX也仅是与Spark机器学习程序库松散地集成)。事实上，可经常看到用图来替代表示稀疏数据矩阵。

Robin还谈及了图数据处理的方法。

East： 如果你习惯于使用关系数据库进行传统数据处理，那么可能需要一段时间去理解使用基于图的方法进行数据建模。如果你固步自封，那么很快就会看到图结构的应用将无所不在。

本文作者：Srini Penchikala

来源：51CTO