环路检测算法在风控领域中的几种优化方向

环路检测在风控领域的应用实践 韩纪飞-Fabarta-高级技术专家 DataFunSummit#2023 目录CONTENT 背景与挑战 算法优化 应用案例 总结与展望 01 背景与挑战 DataFunSummit#2023 环路检测含义与应用 •环路检测算法是一种用于识别和防止欺诈行为的强大工具。它通过分析交易和资金流动的网络，检测潜在的环路结构，以识别异常模式和潜在的欺诈行为。 挑战 01 数以亿计点边的大型图网络下算法效率的挑战 02 多重图的支持与优化 03 有限硬件资源下的算法调整 02 算法优化 DataFunSummit#2023 大型图网络下算法效率优化 •分布式图计算 •利用分布式计算框架libgrape-lite，将大规模图数据切割为子图，并通过并行计算和消息传递方式实现高效的环路检测。 •除环路检测外，ArcNeural多模态智能引擎基于该框架已支持50+算法，覆盖路径分析、中心性分析、社区发现、关联性分析、子图挖掘等场景。 测试项 ArcNeural多模态智能引擎 Plato 资源使用情况 BFS 1.16s 10.37s 压力持续时间：8hCPU使用率：<=75%内存使用率：<=80% WCC 1.32s 25.49s CDLP 19.48s 34.85s PageRank 3.63s 36.11s •图计算服务器配置：4台32核CPU、256G内存、500GSSD、万兆网络 •图计算测试数据集：LDBCGraphalytics-datagen-9_2-zf,点:4.3亿,边:10.4亿 大型图网络下算法效率优化 •剪枝策略 •�初始化点�、入度 •②标记�或者入度为0的点（不在环路中） •③去除标记点，更新�、入度 •④迭代②-③，直到无新增标记点。 •复杂度 •O(V+E) 多重图的支持与优化 •风控场景如金融交易图中，两点间同种类型边往往会存在多条（多重图）。 •环路数量指数级增加，遍历效率也深受影响。 •解决思路 •�算法运行时去除平行边，只保留一条边，缺点在于无法根据边属性做环过滤，如需获取真实环路径还需二次处理。 •②多条边只遍历一次，输�结果时展开。 有限硬件资源下的算法调整 •PIE（Pregel升级） •PEval：单机图算法 •IncEval：单机版本的增量算法 •环路检测算法 •�运行PEval，每个节点上遍历图，判断是否构成环，当遍历到外部节点时，将遍历信息发送到外部节点。 •②IncEval根据收到的遍历信息，继续遍历，迭代运行至无消息。 •内存资源消耗 •算法中间状态消耗：当前遍历信息，结果等 •消息缓存 有限硬件资源下的算法调整 •单机BFS •队列结构存储遍历路径，每次从队列中取�一条路径，遍历路径当前点邻接点，判断是否成环。 •遇到外部点时发送消息，继续遍历。 •缺点：中间状态内存消耗大。 •单机DFS •递归遍历邻接点。 •遇到外部点时发送消息，继续遍历。 •缺点：当图切分较为分散时，消息缓存所需内存将大大增加。 •分布式DFS •递归遍历邻接点，遇到外部点时发送消息，停止遍历，存储遍历状态，以便后续恢复。 •并行度较单机DFS低，但内存消耗小。 •缺点：速度慢 最优方案：优化图切分（难度较大）+单机DFS 复杂度分析与实验结果 •算法复杂度 •无剪枝策略：O(V*(V+E+R)) •剪枝策略：O(V+E+V*R) 单机BFS 单机DFS+单节点 单机DFS+两节点 分布式DFS+两节点 分布式DFS+剪枝+两节点 时间/s OOM 16000 OOM 46000 200 内存/MB 30G+ 138 30G+ 93 195 点：table 边impact：table->impact->table 数据量：10w个table，1w个impact边 03 应用案例 DataFunSummit#2023 应用案例 •环路场景 •交易闭环：指定一批起点，沿着环路方向，交易时间（边属性）递增。 •50w点，2000w边上发现30w+交易环路涉及6000左右点。 •转账回路：不指定起点，给定时间区间，环路上起始边转账时间满足区间。 •20w点，400w边上发现3跳以上环路10w+涉及5000点。 •发现潜在风险主体后，结合环路交易次数、交易金额、环路长度等输�风险评分，为审核人员和机器模型提供重要特征参考。 04 总结与展望 DataFunSummit#2023 总结与展望 •总结 •介绍了环路检测算法在风控场景的探索，提供了算法效率优化、硬件资源限制下的算法探索，为环路检测算法在风控场景的落地提供了工程化方案。 •展望 •环路虽然简单直观，但离最终的业务指标尚有距离，环路检测与上下游链路的融合仍需努力。 •分布式算法开发较为复杂，优化开发链路，新型AI工具的使用等。 •图切分策略的优化升级。 公司介绍 Fabarta是一家AI基础设施公司，基于自研的多模态智能引擎，提供结构化数据和非结构化数据的融合存储 （记忆）和分析(推理)能力，并通过低代码平台帮助企业将AI能力快速落地到业务场景中。 ArcNeural多模态智能引擎 •以Data-CentricAI为核心构建AI时代的数据基础设施产品，将传统的数据库“存储&计算”架构演进为“记忆&推理”架构，是AGI时代的核心基础设施。 Fabarta®企业智能分析平台 •结合ArcNeural多模智能引擎的企业级智能平台，帮助开发者、咨询师以及应用开发人员更快速地将图引擎与大模型的融合能力应用于行业中，加速图智能在企业场景的落地。 Fabarta®多模态数据编织平台 •为企业打造基于数据编织技术的下一代数据价值生态的基础设施，利用智能的技术帮助企业盘点数据资产，构建数据资产地图，让企业充分发挥数据流动带来的价值。 感谢观看