开源｜LPA-Detector：基于GraphX 的LPA算法改进

开源项目专题系列

（五）

1.开源项目名称： LPA-Detector

2.github地址：

https://github.com/wuba/LPA-Detector

3.简介： 本文主要介绍基于GraphX框架对LPA算法的改造，并提出了一种新的标签传播算法，其实践结果表明：其改进的算法在运行效率和算法效果方面均有显著的提升。

LPA-Detector于2020年3月份开源，具备如下特点：

• 基于GraphX框架的LPA算法分布式改造，满足大规模图数据的并行计算需求；

• 产出实际生产应用中调优图计算的迭代参数，可大幅减少内存消耗和计算时间；

• 对图传播算法进行改进，引入基于节点置信权重和关系影响力的评价选优方法，提高传播的稳定性和准确性；

背景

关联网络是将现实中关联实体信息通过数据抽取、转换并以图的形式存储和计算的一种垂直类知识图谱。图的节点表示关联网络中的实体，边表示两个实体之间的关系。

风控场景下，通常高 风 险人群 具有 高 聚 集 性 特点，那么利用关联网络数据 并通过特定的 图算法就可以发现这些潜在的风险团伙。 LPA（Label Propagation Algorithm）正是 一种基于标签传播的高效的“社团发现”算法 ，它是由Usha等人在2007年提出，该算法具有线性复杂度，且不需要任何目标函数和网络中的先验信息，是一种适合在大规模数据集上进行风险传导的图算法。

在 生产应用中，我们发现LPA算法实际上仍存在着 两大 突出 问题： 一是在迭代更新节点过程中的随机性导致其结果不稳定且可信度低，不能满足 生产 应用的要求； 二是由于实际的 关联网络 数 据规模 非常庞大（上亿实体，百亿关 系），导致单机环境上运行时间非常长，耗时无法接受 。

针对以上两个问题，本文基于 GraphX对LPA算法进行了分布式改造，并 提 出 了一种新的 标签 置信权重的评价选优 方法， 以进一步 改 善其 算法的 执行 效率和效果，以下 为详细介绍：

算法改进

对于LPA算法的分布式改造： 选择 Spark/Hadoop 来实现图并行算法，GraphX 是基于 Spark 构建的图计算框架，提供了简单易用的图迭代接口，基于GraphX可以快速实现分布式的LPA算法。

对标签传播算法传播机制的改进：在标签传播过程中，将选取邻居节点中标签数量最多的标签作为当前节点的标签，当出现了最多标签数量有多个时，会随机选择标签，这种选择策略可能 导致弱关系或者影响较小标签成了决定性因素，最终导致风险传导结果表现出较高的误杀率。因此，这里引入了一种评价方法， 一种 基 于 标签 和 关 系 计 算 的 权 值分，该权值分是风险传导和节点标签更新的 选优 标准，详细参考权值计算。

1. 权值计算

在实际风险传导场景中，如风控场景“坏人”的标签具有重要价值，且人的关系越密切时对风险标签的传导更加有效，因此，我们结合标签传播的思想融合了节点置信权重和关系影响力。 

具体算法如下：

根据标签置信权重和关系影响力的联合重要程度对风险标签进行传导， 使得重要性较大的节点和关系更具代表意义，有效减少了LPA存在的随机逆流现象。

通过预计算的关系影响力等指标带入模型，可以满足不同场景下的应用需求，使节点之间的风险传导更加准确，从而提高算法的稳定性和准确性。

2. 算法实现

为了融合标签和关系在GraphX 中运行，这里设计了新的迭代过程，具体如下：

输入：G={V,E} ， V 表示节点，E 表示边（关系）；

输出：风险集Setc = {C1,C2...CK} , K为风险类别数，Ck 表示同一类别风险标签的顶点集合；

实现如下：

(1) 风险传导

风险传导为风险权值计算单元，实现了具体的计算过程。 在 利用GraphX进行图迭代时，我们优化了 消息的传播机制， 减少了不必要的消息传递，即针对图关系两端的节点中不需要传播的风险或已真实存在的风险标签，则进行过滤不作传递，其 实践结果表明： 对上亿节点和十亿级关系的图数据，优化后的迭代时间为原来的1/4。

(2) 消息合并

消息合并是对风险标签的融合和权重的再计算，这里的优化点是： 当节点存在成百上千个邻居节点时，会接受收到邻居 节点 个数的消息量，但实际消息中只有少量几种类型的标签，我们通过消息合并去重，将消息数量减少到了标签类型的数量，这样就大幅提升了后继消息的传递效率。

(3) 风 险 标签更新

风险标签更新是对节点风险的预估结果进行权值比较，将权重最高的标签作为当前节点待更新的标签。

使用方式

1. 数据准备

包括：节点数据和关系数据。

* 节点数据格式如下：

        {"attr":{"type":"v0"},"id":0}

        {"attr":{"type":"v2"},"id":2}

*关系数据格式如下：

{"dstId":2,"prop":{"type":"E0-2"},"srcId":0}

2. 权值设置

权重的调整通过配置文件设定，在配置文件中注明其标签和关系的权值即可。

3. 项目运行

准备好数据，设定权值和迭代次数，执行脚本run.sh即可。

未来规划

针对不同的业务场景自定义标签的置信权重和关系权重，如通过相似性或者影响力等，从而适配更多的业务场景。

另外，后续将陆续推出优化后的图特征、社团发现、图embedding等图计算工具，让更贴切于实际生产应用的图算法库加丰富。

如何贡献&问题反馈

LPA算法的改进是贡献社区的一小步，我们诚挚地希望开发者向我们提出宝贵的意见。

您可以通过以下方式向我们反馈建议和问题： 在https://github.com/wuba/LPA-Detector提交PR 或者 Issue.

作者介绍

黄佳，58金融高级开发工程师，主要负责58金融反欺诈识别开发工作。

参考文献

1. Spark官网 http://spark.apache.org/

2.Usha Nandini Raghavan, Reka Albert and Soundar Kumara.2002.Near linear time algorithm to detect community structures in large-scale networks.

想了解更多开源项目信息？

与项目成员零距离交流？

扫码加小秘书 微信

一切应有尽有

阅读推荐

1.“暗黑模式”之58 同城 iOS App深色模式适配实践

2.开源｜Zucker：Android APP模块化大小自动分析统计工具

3.开源｜WBBlades：基于Mach-O文件解析的APP分析工具

4.开源｜wwto：小程序跨端迁移解决方案——微信转其他小程序

5.开源｜qa_match：一款基于深度学习的层级问答匹配工具