GraphX 在图数据库 NebulaGraph 的图计算实践

图计算实践

一、背景

随着网络信息技术的飞速发展，数据逐渐向多源异构化方向发展，且不同来源的异构数据之间也存在的千丝万缕的关联，这种数据之间隐藏的关联关系和网络结构特性对于数据分析至关重要。但传统关系型数据库在分析大规模数据关联特性时存在性能缺陷、表达有限等问题，因此有着更强大表达能力的图数据受到业界极大重视，图计算就是以图作为数据模型来表达问题并予以解决的过程。图可以融合多源多类型的数据，除了可以展示数据静态基础特性之外，还可通过图计算展示隐藏在数据之间的图结构特性和点对关联关系，成为社交网络、推荐系统、知识图谱、金融风控、网络安全、文本检索等领域重要的分析手段。

二、算法应用

为了支撑大规模图计算的业务需求，NebulaGraph 基于 GraphX 提供了 PageRank 和 Louvain 社区发现的图计算算法，允许用户通过提交 Spark 任务的形式执行算法应用。此外，用户也可以通过 Spark Connector 编写 Spark 程序调用 GraphX 自带的其他图算法，如 LabelPropagation、ConnectedComponent 等。

PageRank

PageRank 是谷歌提出的用于解决链接分析中网页排名问题的算法，目的是为了对互联网中数以亿计的网页进行排名。

PageRank 简介

美国斯坦福大学的 Larry Page 和 Sergey Brin 在研究网页排序问题时采用学术界评判论文重要性的方法，即看论文的引用量以及引用该论文的论文质量，对应于网页的重要性有两个假设：

数量假设：如果一个网页 A 被很多其他网页链接到，则该网页比较重要；
质量假设：如果一个很重要的网页链接到网页 A，则该网页的重要性会被提高。

并基于这两个假设提出 PageRank 算法。

PageRank 应用场景

社交应用的相似度内容推荐

在对微博、微信等社交平台进行社交网络分析时，可以基于 PageRank 算法根据用户通常浏览的信息以及停留时间实现基于用户的相似度的内容推荐；

分析用户社交影响力

在社交网络分析时根据用户的 PageRank 值进行用户影响力分析；

文献重要性研究

根据文献的 PageRank 值评判该文献的质量，PageRank 算法就是基于评判文献质量的想法来实现设计。

此外 PageRank 在数据分析和挖掘中也有很多的应用。

算法思路

GraphX 的 PageRank 算法是基于 Pregel 计算模型的，该算法流程包括 3 步骤：

为图中每个节点（网页）设置一个同样的初始 PageRank 值；
第一次迭代：沿边发送消息，每个节点收到所有关联边上对点的信息，得到一个新的 PageRank 值；
第二次迭代：用这组新的 PageRank 按不同算法模式对应的公式形成节点自己新的 PageRank。

Louvain 社区发现

Louvain 是用来进行社会网络挖掘的社区发现算法，属于图的聚类算法。

Louvain 算法介绍

Louvain 是基于模块度（Modularity）的社区发现算法，通过模块度来衡量一个社区的紧密程度。如果一个节点加入到某一社区中会使得该社区的模块度相比其他社区有最大程度的增加，则该节点就应当属于该社区。如果加入其它社区后没有使其模块度增加，则留在自己当前社区中。

模块度

模块度公式

模块度 Q 的物理意义：社区内节点的连边数与随机情况下的边数之差，定义函数如下：

$$ Q = \frac{1}{2m} \times \sum_{i,j}[A_{ij} - \frac{k_ik_j}{2m}]\delta(c_i,c_j) \ 条件：\delta(u,v) = \begin{cases} 1 &\text{when u == v} \ 0 &\text {}else \end{cases} $$

其中

$A_{ij}$：节点 i 和节点 j 之间边的权重 $K_i$ ：所有与节点 i 相连的边的权重之和 $C_i$ ：节点 i 所属的社区 $m$ ：图中所有边的权重之和

模块度公式变形

在此公式中，只有节点 i 和节点 j 属于同一社区，公式才有意义，所以该公式是衡量的某一社区内的紧密度。对于该公式的简化变形如下：

$ Q = \frac{1}{2m} \times \sum{i,j}[A{i,j} - \frac{k_ik_j}{2m}]\delta(c_i,c_j) \ = \frac{1}{2m}[\sum{i,j}A{i,j} - \frac{\sum_ik_i \sum_jk_j}{2m}]\delta(c_i,c_j) \ = \frac{1}{2m} \sum_c[\sum{in} - \frac{{\sum{tot}}^{2}}{2m}] $

$\Sigma_{in}$ 表示：社区 c 内的边的权重之和 $\Sigma_{k_n}$ 表示：所有与社区 c 内节点相连的边的权重之和（因为 i 属于社区 c）包括社区内节点与节点 i 的边和社区外节点与节点 i 的边。 $\Sigma_{k_j}$ 表示：所有与社区 c 内节点相连的边的权重之和（因为 j 属于社区 c）包括社区内节点与节点 j 的边和社区外节点与节点 j 的边。 _$\Sigma{tot}$ _代替_ $\Sigma{k_i}$_ 和 $\Sigma_{k_j}$。（即社区 c 内边权重和 + 社区 c 与其他社区连边的权重和）

求解模块度变化

在 Louvain 算法中不需要求每个社区具体的模块度，只需要比较社区中加入某个节点之后的模块度变化，所以需要求解 △Q。

将节点 i 分配到某一社区中，社区的模块度变化为：

$\Delta{Q} = [\frac{\sum{in} + k{i,in}}{2m} -({\frac{\sum{tot} + k_i}{2m}})^{2}] - [\frac{\sum{in}}{2m} - (\frac{\sum_{tot}}{2m})^{2} - (\frac{k_i}{2m})^{2}] \ = [\frac{k{i,in}}{2m} - \frac{\sum{tot}k_i}{2m^2}]$

其中

$k_{i,in}$：社区内所有节点与节点 i 连边权重之和（对应新社区的实际内部权重和乘以 2，因为 $k_{i,in}$ 对于社区内所有的顶点 i，i 关联的每条边其实被计算了两次） $K_i$：所有与节点 i 相连的边的权重之和故实现算法时只需求 $[k{i,in} - \sum{tot} \times \frac{k_i}{m}]$ 即可。

Louvain 应用场景

金融风控

在金融风控场景中，可以根据用户行为特征进行团伙识别；

社交网络

可以基于网络关系中点对之间关联的广度和强度进行社交网络划分；对复杂网络分析、电话网络分析人群之间的联系密切度；

推荐系统

基于用户兴趣爱好的社区发现，可以根据社区并结合协同过滤等推荐算法进行更精确有效的个性化推荐。

Louvain 算法思路

Louvain 算法包括两个阶段，其流程就是这两个阶段的迭代过程。

阶段一：不断地遍历网络图中的节点，通过比较节点给每个邻居社区带来的模块度的变化，将单个节点加入到能够使 Modularity 模块度有最大增量的社区中。（比如节点 v 分别加入到社区 A、B、C 中，使得三个社区的模块度增量为-1， 1， 2，则节点 v 最终应该加入到社区 C 中）

阶段二：对第一阶段进行处理，将属于同一社区的顶点合并为一个大的超点重新构造网络图，即一个社区作为图的一个新的节点。此时两个超点之间边的权重是两个超点内所有原始顶点之间相连的边权重之和，即两个社区之间的边权重之和。

下面是对第一二阶段的实例介绍。

Louvain 社区算法

第一阶段遍历图中节点加入到其所属社区中，得到中间的图，形成四个社区；

第二阶段对社区内的节点进行合并成一个超级节点，社区节点有自连边，其权重为社区内部所有节点间相连的边的权重之和的 2 倍，社区之间的边权重为两个社区间顶点跨社区相连的边的权重之和，如红色社区和浅绿色社区之间通过（8,11）、（10，11）、（10,13）相连，所以两个社区之间边的权重为 3。

_注：社区内的权重为所有内部结点之间边权重的两倍，因为 Kin 的概念是社区内所有节点与节点 i 的连边和，在计算某一社区的 Kin 时，实际上每条边都被其两端的顶点计算了一次，一共被计算了两次。_

整个 Louvain 算法就是不断迭代第一阶段和第二阶段，直到算法稳定（图的模块度不再变化）或者到达最大迭代次数。

三、算法实践

演示环境

三台虚拟机，环境如下：
- Cpu name：Intel(R) Xeon(R) Platinum 8260M CPU @ 2.30GHz
- Processors：32
- CPU Cores：16
- Memory Size：128G
软件环境
- Spark：spark-2.4.6-bin-hadoop2.7 三个节点集群
- yarn V2.10.0：三个节点集群
- NebulaGraph V1.1.0：分布式部署，默认配置

测试数据

创建图空间

CREATE SPACE algoTest(partition_num=100, replica_factor=1);

创建点边 Schema

CREATE TAG PERSON()
CREATE EDGE FRIEND(likeness double);

导入数据

利用 Exchange 工具将数据离线导入 NebulaGraph。

测试结果

Spark 任务的资源分配为 --driver-memory=20G --executor-memory=100G --executor-cores=3

PageRank 在一亿数据集上的执行时间为 21min（PageRank 算法执行时间）
Louvain 在一亿数据集上的执行时间为 1.3h（Reader + Louvain 算法执行时间）

如何使用 NebulaGraph 的算法

下载 nebula-algorithm 项目并打成 jar 包

$ git clone git@github.com:vesoft-inc/nebula-java.git
$ cd nebula-java/tools/nebula-algorithm
$ mvn package -DskipTests

配置项目中的 src/main/resources/application.conf

{
  # Spark relation config
  spark: {
    app: {
        # not required, default name is the algorithm that you are going to execute.
        name: PageRank

        # not required
        partitionNum: 12
    }

    master: local

    # not required
    conf: {
        driver-memory: 8g
        executor-memory: 8g
        executor-cores: 1g
        cores-max:6
    }
  }

  # NebulaGraph relation config
  nebula: {
    # metadata server address
    addresses: "127.0.0.1:45500"
    user: root
    pswd: nebula
    space: algoTest
    # partition specified while creating nebula space, if you didn't specified the partition, then it's 100.
    partitionNumber: 100
    # nebula edge type
    labels: ["FRIEND"]

    hasWeight: true
    # if hasWeight is true，then weightCols is required， and weghtCols' order must be corresponding with labels.
    # Noted: the graph algorithm only supports isomorphic graphs,
    #        so the data type of each col in weightCols must be consistent and all numeric types.
    weightCols: [“likeness”]
  }

  algorithm: {
    # the algorithm that you are going to execute，pick one from [pagerank, louvain]
    executeAlgo: louvain
    # algorithm result path
    path: /tmp

    # pagerank parameter
    pagerank: {
        maxIter: 20
        resetProb: 0.15  # default 0.15

    }

    # louvain parameter
    louvain: {
        maxIter: 20
        internalIter: 10
        tol: 0.5
   }
  }
}

确保用户环境已安装 Spark 并启动 Spark 服务
提交 nebula-algorithm 应用程序：

spark-submit --master xxx --class com.vesoft.nebula.tools.algorithm.Main /your-jar-path/nebula-algorithm-1.0.1.jar -p /your-application.conf-path/application.conf

如果你对上述内容感兴趣，欢迎用 nebula-algorithm 试试^^

References

NebulaGraph：https://github.com/vesoft-inc/nebula
GraphX：https://github.com/apache/spark/tree/master/graphx
Spark-connector：https://github.com/vesoft-inc/nebula-java/tree/master/tools/nebula-spark
Exchange：https://github.com/vesoft-inc/nebula-java/blob/master/doc/tools/exchange/ex-ug-toc.md
nebula-algorithm：https://github.com/vesoft-inc/nebula-java/tree/v1.0/tools/nebula-algorithm

作者有话说：Hi，我是安祺，NebulaGraph 研发工程师，如果你对本文有任何疑问，欢迎来论坛和我交流：https://discuss.nebula-graph.com.cn/