GraphLab 入门实例指南

因为课程的机会接触了一下 GraphLab,许多概念以及对应的思维方式需要改变。这里主要介绍一下基本概念,以及如何启动 GraphLab 集群并进行简单的计算。


更新记录

  • 2016.04.13: 初稿

GraphLab 是 CMU 开发的分布式 graph parallel 框架,用来在大数据上执行机器学习和数据挖掘算法。GraphLab 把具体的计算抽象成为节点(vertex),而计算之间的数据关系抽象成为边(edge)。

简单来说就是具体的计算会在每个节点上进行,有三个步骤:

  1. Gather: 对于每个节点来说,其 master 和 mirror 节点会从相邻的边和节点收集所需信息
  2. Apply: 所有收集到的信息会在 master 节点完成计算并更新节点,完成之后这个改动会同步到其他的 mirror 节点中
  3. Scatter: master 和 mirror 节点选择更新对应相邻的边和节点,收到消息的节点会被激活,继续执行对应的计算

步骤过程

另外有一个需要注意的地方是在最新的版本中,采用 Vertex-Cut 来进行数据分隔。这样的好处是,一条边连接的两个节点肯定在一台机器上,对于每个节点来说,可能会有几个不同的复制,其中一个将成为 master,其他的则是 mirror。

安装部署

手动配置的步骤还是比较繁琐的,不过 GraphLab 提供了启动 Amazon EC2 的脚本,可以自动进行机器的申请和部署。这里也主要以这种方式来进行之后的步骤。

官方 Github 下载好源代码之后,解压之后进入 scripts 文件夹。然后需要在环境变量中进行如下配置(这个只对当前的终端有效):

  • export AWS_ACCESS_KEY_ID=[your AWS access key]
  • export AWS_SECRET_ACCESS_KEY=[your AWS secret key]

完成之后可以通过如下的命令来启动集群

./gl-ec2 -k [密钥名] -i [密钥文件路径] -t [实例类型] -s [slave 数量] -r us-east-1 launch [集群名称]

这里的实例类型默认是 m1.large,这里我们可以简单测试一下(对于大的图可能 m4.large 内存会不够),我使用的命令是

./gl-ec2 -k demo -i demo.pem -t m4.large -s 10 -r us-east-1 -a ami-89adafe3 launch p423

没啥意外的话(如果有意外的话一般是当前区域没有足够的主机,换一个机器类型即可),就可以看到机器正在启动,如下图所示

启动脚本执行完毕之后。我们就可以进行登录了,命令为:

./gl-ec2 -k [keypair] -i [key-file] -r us-east-1 login [cluster-name]

对于当前的例子来说就是

./gl-ec2 -k demo -i demo.pem -r us-east-1 login p422

执行的话也可以用脚本进行,编译之后(具体参考官方的例子)使用 ~/graphlab/scripts/mpirsync 把程序分发到集群的每一台机器上,然后使用 mpiexec 命令来具体执行。

如果要关闭集群的话,命令为:

./gl-ec2 -k [keypair] -i [key-file] -r us-east-1 destroy [cluster-name]

对于当前的例子就是

./gl-ec2 -k demo -i demo.pem -r us-east-1 destroy p422

PageRank

接下来我们试着用 GraphLab 把 PageRank 实现一次。首先当然是要搞到文档,用如下命令 brew install doxygen; doxygen。等待一段时间之后,就可以在 doc/doxygen/index.html 中查看文档了。

PageRank 的具体介绍可以查看维基,这里做一个简要介绍。我们先来看看具体的公式

这个公式是什么意思呢?这里我们取 N = 1, d = 0.85,也就是说,一个页面的 PageRank 值,等于一个常数加上其他指向它的页面所贡献的 PageRank 值。每个指向该页面的页面具体贡献的数值,是指向该页面的页面自己的 PageRank 值除以外链的个数,即简单的平均数,一个页面把自己的 PageRank 分散出去。一个简单的例子

page1, rank: 1.0, point to: page2, page3
page2, rank: 1.0, point to: page3, page1

经过第一次迭代之后,会得到如下的分布,这里稍微解释一下,为什么 page1 得到的是 0.5 呢?因为我们可以看到只有 page2 指向 page1,而 page2 一共有 2 个外链,所以其权重被平均分成两份,于是就是 0.5;page2 得到 0.5 也是同理。而 page1 和 page2 都指向 page3,page3 从他们身上拿到了 0.5,所以是 1.

key: page1 contributions received: 0.5 point to: page2 page3
key: page2 contributions received: 0.5 point to: page3 page1
key: page3 contributions received: 1.0 point to:

这里 page3 没有外链,就成了『异类』,所以必须把这类节点的权重平均分给所有的节点,这里 user3 的初始权重是 1,因为一共有 3 个用户,可得:

page1 = 0.15 + 0.85 * (0.5 + 1.0/3) = 0.8583
page2 = 0.15 + 0.85 * (0.5 + 1.0/3) = 0.8583
page3 = 0.15 + 0.85 * (1.0 + 1.0/3) = 1.2834

之后就继续按照这样的模式计算下去,直到指定次数或者收敛(排名不再变动)。

具体实现

我们从官方给出的例子)中可以大概了解具体要如何编写。还是用之前提到的几个步骤:gather, apply, scatter (以下代码来自官方例子)

float gather(icontext_type& context, const vertex_type& vertex,
edge_type& edge) const {
return ((1.0 - RESET_PROB) / edge.source().num_out_edges()) * edge.source().data();
}
/* Use the total rank of adjacent pages to update this page */
void apply(icontext_type& context, vertex_type& vertex,
const gather_type& total) {
const double newval = total + RESET_PROB;
last_change = std::fabs(newval - vertex.data());
vertex.data() = newval;
}
/* The scatter edges depend on whether the pagerank has converged */
edge_dir_type scatter_edges(icontext_type& context,
const vertex_type& vertex) const {
if (last_change > TOLERANCE) return graphlab::OUT_EDGES;
else return graphlab::NO_EDGES;
}
/* The scatter function just signal adjacent pages */
void scatter(icontext_type& context, const vertex_type& vertex,
edge_type& edge) const {
context.signal(edge.target());
}

因为我们现在是针对于某个节点在运算,所以不需要考虑全局的状况,甚至也不需要在意怎么获取邻接节点,都可以认为框架会帮我们处理好,我们直接专注于需要在节点上进行的计算即可!所以可以看到整个 PageRank 在 GraphLab 上的实现非常简单明了!

不过需要注意的是,这个例子中并没有处理没有外链的页面,也就是 dangling page 的情况,如果想要得到更准确的 pagerank,需要进行处理。

参考链接

捧个钱场?