中亦科技：如何优化大规模图谱中可疑链路搜索效果

　　链路搜索作为基础的图分析任务，在电商、金融、医疗等多个领域中都有着广泛的应用，比如传染病的传播分析，电商中的用户行为分析，以及金融行业中的交易链路分析等。在金融行业中，海量交易行为下隐藏着丰富的信息，而其中可疑交易链路在实际风控业务中尤其重要。比如贷前调查时，发现某家企业突然短时间内与另一家企业存在短期频繁交易以提高流水;或者在贷后检查时，查明某家企业的贷款金额快速转给了一家黑名单企业;则会触发风险，需提高警惕。

　　国内信创领域头部企业中亦科技指出，在相关可疑交易链路中，较为复杂的是环形链路。环形资金链路通常指公司或个人通过一系列交易，形成资金循环利用的行为，目的是达到资金占用或者盈利目的，比如洗钱、套现、虚假增资等等，这类环形链路交易背后通常都伴随着金融风险。那么当如何从海量流水中对可疑环形链路进行深度挖掘呢?中亦科技提供了一套经过实践检验的算法思路。

　　基础算法

　　Rocha-Thatte算法是一种实用且高效的有向图环形链路侦测算法，主要通过消息传递机制进行环路识别。如图1所示，该算法主要步骤如下：

　　1. 初始化图中所有节点 v 均为活动节点;

　　2. 对于活动节点，记录并发送消息路径列表至邻居节点;

　　3. 对每个节点v收到的消息路径列表进行以下检查：

　　a) 如果收到的消息为空，则设为不活动节点，停止消息传递;

　　b) 如果路径列表中的第一个元素ID与ID(v)相同，则说明发现一个环。判断ID(v)是否为路径列表中的最小ID(避免重复)，如果是，则记录该路径列表为一个环;

　　c) 如果ID(v)在路径列表中的其他位置，则删除该路径(该路径已被计算);

　　d) 如果ID(v)不在该路径列表中，则将ID(v)追加到其列表中剩余路径的末尾作为新的消息进行下一步消息传递。

　　4. 重复步骤2和3，直到所有节点均为不活动节点，并输出所有记录的成环的路径列表。

　　图1  Rocha-Thatte算法消息传递示例

　　优化算法

　　虽然Rocha-Thatte算法是可并行的高效算法，但是在实际金融场景落地时，仍然面临以下两个挑战：

　　首先，实际场景下的环形交易链路侦测需要考虑一些限制条件，比如下一笔交易的交易时间需在上一笔交易后的一段时间内、下一笔交易的交易金额需在上一笔交易的一定金额比例范围内等。那么对于每条路径我们都需要判断下一笔交易是否符合限制条件，这会显著提升计算复杂度。

　　其次，由于实际交易数据量大，而环形链路侦测算法本身的空间复杂度也很高，因为它在中间计算过程中需要存储所有候选的环形路径，进而导致极高的内存消耗。

　　因此，针对以上问题，我们把账户和交易都作为节点，分别建立账户-账户和交易-交易之间的连边，从而通过强连通分量算法对候选交易和路径做预处理过滤，降低计算复杂度和内存消耗。具体步骤和思路如下：

　　1. 强连通分量[2]中的任意节点都是可达的，因此成环的账户必然在同一个强连通分量中。如图2a所示，我们可以将所有交易根据方向合并成账户与账户的Account_Account边，形成账户之间的有向网络，并使用强连通分量算法[3]，得到每个账户的SCC_ID。

　　2. 针对交易链路限制条件，可以采用类似预处理的方式，预先过滤筛选避免重复计算。如图2b所示，对于每个账户的转入与转出交易，如果其转入账户与转出账户的SCC_ID相同，并且满足预设限制条件(交易时间、交易金额等)，建立交易-交易的Trans_Trans边，从而得到一个交易之间的有向无环网络(因为假设满足时间先后顺序)。

　　3. 为了侦测环形链路，这里需要将成环的最后一条边也连上。如图2c所示，我们可以采用类似于Rocha-Thatte算法的消息传递的思路，但只是传递交易ID以及对应转出账户ID。对于每个交易节点，如果收到的消息中的转出账户ID与自身的转入账户ID相同，则与收到消息中的交易ID对应的交易节点建立一条Trans_Trans边。

　　4. 与第一步类似，在建立的交易网络上使用强连通分量算法，获得每笔交易的SCC_ID。

　　5. 在交易网络上使用Rocha-Thatte算法，并且在传递消息路径时过滤不同SCC_ID的交易节点，对候选路径进行剪枝从而降低内存消耗，最终得到所有成环链路，如图2d所示。

　　图2 优化算法主要步骤示例

　　应用案例

　　在交易网络中，一般来说交易点的数量级会大于客户点，即使是小部分客户的多度交易网络也可能拓展到全图。此时使用基础的环形链路侦测算法，不仅在业务上有一定的局限性，同时对机器性能也存在较高的要求。而通过优化的环形链路侦测算法，分步处理问题，在时间和性能上均有较大的提升。

　　以下是是某金融机构的个人账户反洗钱案例中的运行结果(包含约2.3亿节点和3.7亿边)：

　　表1 两类算法运行结果比较

　　结语

　　本文主要介绍了链路搜索在金融场景中常用的环形链路侦测算法，包括基础算法和优化算法，并重点介绍了在实际落地中所遇到的挑战和相应的优化思路，最后通过实际案例说明了优化环形链路侦测算法在大规模图谱中的高效性。