本文由北邮@爱可可-爱生活 老师推荐，阿里云云栖社区组织翻译。文中所有标蓝部分均可阅读原文查看详情。

编者按：基于图的机器算法学习是一个强大的工具。结合运用模块特性，能够在集合检测中发挥更大作用。本文是基于图的机器算法系列文的第二篇（前情回顾：基于图的机器算法 （一））。

在上一篇文章中，我们进行了使用模块化优化方式来进行集合检测的探索。然而它有个不足，你的图需要适应内存。当你的节点数超过数十亿，边数将变成万亿，这很快就会出现问题。

幸运的是，我们可以利用分布式计算系统来解除这个限制。为此，我们首先需要定义节点的状态，使其包含计算期间所需的所有信息;这将构成在分布式集群的器之间传递数据的基本结构。

让我们简要回顾一下模块化优化的过程。通过迭代方式对局部模块化优化的节点进行合并，以产生新的和更小的图来工作。重复，直到满意。这种方法产生了两个重要的属性：

• 局部性：每个节点只需要来自其第一度邻点的知识。这意味着群集之间传递的数据是最少的。这样，您就不必从节点到节点进行跳转来获取跨集群的信息。

• 独立性：每个局部计算独立于图的布局。在迭代中，每个节点可以异步地将其信息发送到其邻点，而无需等待阻塞序列集合的操作。

让我们继续深入地探究在不同节点进行集合传送的初始步骤。记住每个节点需要读取来自其邻点的信息，以便计算局部模块化的梯度。

进行大规模数据传送的最好方法是使用分布式事务。它是组成程序的对象的工作方式，用于在不同计算机（互联网）上运行对象和进行系统交互。在集合检测过程中，每个节点向其邻点发类似如下内容的消息：

“嗨，我是你友好的邻居，集合12的节点3。”

通过独立地向它们的第一度邻点发送消息，每个节点可以检索它们并获取为进行局部模块化优化所需的所有信息。 每个消息的内容可以任意调整，从而增加了相当大的灵活性。

如果你曾经使用过图，一定不会对顶点和边的概念陌生。如果不得不遍历所有的顶点及其边来进行数据传送，这将是件很痛苦的事。在GraphX的世界中，或许我们可以尝试第三种原语：三元组。

GraphX中支持的三种不同的视图，更详细介绍请访问AMLab

三元组以一种简化的和有用的方式来进行顶点和边属性的逻辑连接。表面上看，EdgeTriplet类透过增添srcAttr和dstAttr成员来对Edge 类进行了扩展，其分别为源和目标属性。通过减少三元组视图。sendMsg和mergeMsg都是内部函数执行必要的聚合为局部模块更新。每个节点独立和并行,等待它的将减少其所有消息转变成一个连贯的地方和加权边缘,和做决定基于局部模块化deltaQ邻近集合。

几轮迭代后,图已经聚集到局部平衡(如少量的节点达到改变集合的状态)。算法可以进展到下一步压缩那些集合形成一个紧凑的状态。这是通过创建一个含有新节点集和边的新图来完成的，这些边是有前次计算而推断得到的(例如：外部边的平均值或和)。

函数的选用取决于使用案例(例如：求平均值，求和等)。

每次迭代时集合压缩在单节点中的影响

假设我们有足够大的磁碟，可以使用全功能函数程序来对超大图进行模块化优化工作。

计算时间

在每次传递时meta-集合数量会自然减少,因此大部分的计算时间仅用于第一次。这表明先序数据在时间节约上有相当的优势。

在集群级别的局部节点优化意味着发生更少的机器间传送

聚集

这种方法不一定收敛于最优方案。为了改善这种情况,多次迭代可以优化数据的结构。这为两个同属于某个集合的节点提供了一个便利的概率代理方式。

布局

布局策略的有效性要考虑图的连接性。例如,对于一个完全连接和未加权的图,输出将会退化。事先考虑阈值图像中提取数据的稀疏表示。

模块化的充分优化依赖图的连接模式。例如，一个点阵布局算法的执行效果将相当差。模块化优化并不能保证足够的集群；因此获得的最后一个集合不能说就绝对属于某个节点组(甚至任何组)。

层次结构

这一过程的迭代特性提供了一种层次化的在后续迭代集合之间的视图。中间步骤应该被保存，以进行更深层次的有效消息发掘。

查执行集合检测的可行性是通过GraphX分布式方法实现的。嵌入到Hadoop生态系统中的模块化优化方法实现了网络空前规模的研究；适用于营销，市场细分，基因聚类，主题建模等领域。

文章原标题《Graph-based machine learning: Part 2》，作者：Sebastien Dery。文章为简译，更为详细的内容，请查看原文。

-END-

云栖社区

ID：yunqiinsight

云计算丨互联网架构丨大数据丨机器学习丨运维