获奖团队简介
团队名称：冀科数字
团队成员：冀科数字是一支由河北省科学院应用数学研究所和天津大学的算法爱好者组成的联合队伍，希望通过比赛提升自己在图数据挖掘算法设计与优化方面的技术水平。我们的口号是“做数字时代的勇者”。
队长：王志强，博士，毕业于浙江大学控制系。目前工作于河北省科学院应用数学研究所，主要研究方向为大数据分析等。在比赛中负责整体方案设计。
队员：唐松，硕士，目前天津大学博士在读。主要研究方向为区块链、大数据系统架构等。在比赛中负责并行算法实现。
队员：崔能西，大三，就读于天津大学工科实验班。在比赛中负责数据处理与算法测试。
队员：檀改芳，本科，毕业于燕山大学测控技术与仪器专业。目前工作于河北省科学院应用数学研究所，主要研究方向为知识图谱。在比赛中负责线程调度与优化算法。
队员：张天亮，博士，毕业于中国农业大学。目前工作于河北省科学院应用数学研究所，主要研究方向为机器学习与数据分析等。在比赛中负责整体方案优化。
所获奖项：二等奖
摘 要
本赛题我们根据交易参数对图数据中边的属性进行编码标记，并按不同的属性进行分类，最后通过不同分类集合的归并实现对不同子图模式的挖掘。本方案的亮点主要有：一是将图数据中边的多个属性进行合并编码，利用排序方法实现了不同模式交易边的快速分类，并为节点的快速匹配打下基础；二是利用统计原理估算满足子图模式频繁度阈值时各模式数据量应该达到的规模，跳过规模小的边集合，极大减少了参与节点比对的数据量。
关 键 词
金融图数据，大数据分析，模式挖掘，并行算法
1 赛题任务简介
目前图计算广泛应用到金融风控的场景中，特别是基于图数据进行异常的风险行为模式挖掘，比如反套现，反洗钱等。业界常用的频繁子图挖掘算法可以帮助发现高频出现的子图结构，如何使用频繁子图挖掘算法高效地进行异常风险行为模式挖掘显得尤为重要。本赛题内容如下：
（1）使用简化的金融仿真数据，数据分为点类型数据和边类型数据。点类型数据即为账户数据，又分为普通账户（account）和卡账户（card）两种，有效字段为name和id。边类型数据为两种为带有时间戳和金额的账户间交易、转账等数据，即account_to_account（记为A2A）和account_to_card（记为A2C），有效字段为source_id、target_id、amt、strategy_name和buscode。
（2）在这些交易数据形成的大型图中进频繁子图的挖掘，其中子图复杂度为3阶，即具有3条边的子图，频繁度不小于10000。
（3）根据官方对赛题的解析，子图模式按照欧拉回路的构造标准，如果考虑3阶子图，则本题只考虑链式和三角形环路两种模式。
2 赛题分析
本赛题要实现频繁子图的挖掘，需要处理以下几方面的内容：
（1）数据读取与处理。按照要求对数据进行读取和格式转化，去除无效的字段，并把所有数值字段进行整型处理以提高后续计算效率。
（2）图模式定义。根据交易数据类型，从A2A的数据中可以产生链式子图和环路子图两种，而A2C数据所形成的边只能存在于链式子图的最末端，即这种子图只有A2A→ A2A→A2C这一类链式子图。
（3）频繁度计算。最直接的方式就是对子图模式进行穷举，然后对图数据进行遍历，判断每个3阶子图的模式，如果符合某个模式，就将其频繁度加上1。
（4）算法设计。遍历的计算量是巨大的，需要进行大幅度的优化，算法优化的角度是多方面的，比如遍历路径的剪枝、搜索算法的优化、编程语言的选择和多线程并行计算的实现。
3 算法实现
3.1 实现思路
（1）对于边属性进行处理，原始的交易数据中没有起点名称（source_name）和终点名称的字段(target_name)，则在数据处理中增加这两个字段，通过对相应的账户数据进行查询获得相应的值。这样在后续算法实现过程中只用考虑边数据。
（2）整合需要匹配的模式属性对各边进行编码，即将各边的source_name、target_name、amt、strategy_name和buscode合成到一个字段进行表示，那么按这个字段对边数据进行排序就可以实现边模式的快速分类。
（3）改变遍历图数据找出频繁子图的实现方式。利用先给出子图模式，再计量该模式的频繁度的思路。这样可以对各种模式逐一计算，满足要求的可以直接输出结果，不用占用大量的中间内存。
（4）设计子图模式的遍历算法。先对边模式进行分类，然后任意抽取两个模式出来进行排列，分别做为3阶子图的首边和末边，那么中间边的起点名称和终点名称已经确认，进一步缩小了中间边的选择范围。
3.2 算法流程设计
本方案根据图数据模式挖掘的特点，结合C++的语言特点设计本方案的主体流程：
Step1 读入账户数据和交易数据，进行数据整理：
Step1.1 将有效字段进行数据格式转化；
Step1.2 在建立边数据时，通过起点和终点的ID查询补充相应的名称字段；
Step1.3 对有效字段进行组合，按source_name、target_name、amt、strategy_name和buscode的顺序合并生成类别标签字段（type_tag）。
Step2 对边数据进行排序和分类：
Step2.1 对边数据按type_tag和source_id进行两层排序；
Step2.2 对排序后的数据按type_tag进行类别区间的标识并建立字典数据；
Step2.3 对标签字典按source_name和target_name的组合进行二次区间标识，并建立区间索引字典数据。
Step3 计算3阶子图模式的频繁度：
Step3.1 按边属性类别建立双层循环实现首边和末边的排序；
Step3.2 根据首边的终点名称和末边的起点名称组成的标签索引从Step2.3中建立的区间字典中找到可以匹配的边类别做为中间边的可选集合；
Step3.3 对前两步确定的三条边进行组合遍历，匹配衔接点ID，如果两个节点都匹配上了，则对应子图模式频繁度加1；
Step3.4 上一步遍历完成后，检查频繁度是否达到筛选阈值，如果符合要求，则将该子图模式及频繁度写入结果文件中。
4 方案优化与扩展
4.1 方案优化
本方案是为了解决一个实际的应用问题，为了更高的执行效率，我们结合语言环境、算法思路、数据特点等因素进行了全面的优化：
（1）编程语言方面，运用C++进行了算法的实现，其中利用mmap进行数据读取，提高数据载入效率，调用OpenMP并行编程框架，实现了大数据循环的并行化。
（2）数据处理方面，对于边模式进行标签化时，将标签字段进行整形表达，利用位操作实现了各属性字段的快速拼接，因为整形数据可以实现更高效的比较和排序计算。
（3）遍历剪枝方面，对于子图模式的遍历实质上是一个决策树过程，即由首边选择末边，再选择中间边的过程。根据概率原则，考虑各ID的出现概率为完全随机的，则子图频繁度
的估计公式为 。
式中，
为第i条边模式所对应的数据量，
为连接第i条与第j条的节点所对应名称的账号数量。经测算当
时找到满足频繁度要求的概率极低。因此，我们可以通过估算公式得到的结果，做出是否跳过精确比对计算的决策。
（4）进行衔接点匹配时，要根据当前边的终点ID来匹配下一边的起点ID，这是一个搜索过程，由于我们已经对同属性边的起点ID进行了排序，则可以利用二分法进行快速查找。
4.2 方案扩展
（1）利用对模式进行标签命名的方式，可以扩展为任何模式，通过排序进行模式的自动分组和快速查找。
（2）由于对模式数据建立的索引，可以对任意子图模式进行频繁度统计，并且可以保证结果的唯一性。
（3）可以对多种频繁度计算规则进行统计，比如完全的欧拉路径，即统计过程中每个模式的频繁度计算是每条边只参与一次计算。
5 结语
通过本次比赛，对金融图数据分析方法有了一定的认识和理解，在相关算法设计方面有如下心得：
（1）本方案所用的数据载入方法、数据快速转化方法、二分法快速搜索算法适用于很多算法开法方案。
（2）利用先确定子图模式再计算频繁度的实现方式，可以大幅减少内存的占用。
（3）在频繁度的计算中引入概率思维，可以大大减少模式搭配组合，大幅提高挖掘效率。
（4）对于频繁子图挖掘这样的大数据场景，数据特点、索引优化和查询算法都将对整体效率产生重大影响。
由于团队成员均是在本次比赛中刚刚接触金融图数据挖掘的算法研究，对很多内容还处于学习摸索阶段，因此方案还有很大的提升空间。保守估计，我们方案的运行效率还有30%-50%的优化提升空间。
致 谢
感谢平台和主办方给了我们这次锻炼机会。感谢河北省科学院应用数学研究所提供优质的算力资源。感谢队友们的精诚合作，让我们的队伍能够一步步坚实地迈进决赛。
—End—
戳“阅读原文”，速来竞技练习~
原文始发于微信公众号（DataFountain）：【二等奖方案】大规模金融图数据中异常风险行为模式挖掘赛题「冀科数字」解题思路
