关联图谱在转转风控的实践
1 背景 1-1 引言 2 关联图谱介绍 2-1 关联图谱的定义 2-2 关联图谱和图论的关系 3 关联图谱架构 3-1 关联方案 3-2 关系存储 3-3 关联架构 3-4 关联降噪 3-5 关联扩召 4 关联图谱应用 4-1 关联特征挖掘 4-2 关联染色 4-3 运营后台展示 4-4 关联数据分析 4-5 关联监控 5 总结
1.背景
1-1.引言
转转上大多数“坏事”是少部分人做的，这一小部分人(黑产)为了控制成本，重复利用已有资源进行欺诈、薅羊毛、洗钱等违规行为。黑产的资源和行为会成聚集性，因此，关联在团伙识别上发挥着重要的作用，能使单一维度的用户识别升级成对团伙的对抗，对于风险控制是非常有效的手段。
2.关联图谱介绍
2-1.关联图谱的定义
在常规的风险识别场景中，往往关注的是单一节点的属性。其实，在这背后还有另一类非常有效的信息——关联信息。比如，用户A的注册手机号是M；用户B的注册手机号也是M；那么，用户A和用户B则通过注册手机号M相互关联，M就是用户A和用户B的关联因子。如果将用户A、用户B、关联因子M这些结构型的信息用图表示出来，就构成了我们所说的关联图谱。
2-2.关联图谱和图论的关系
关联图谱的理论基础是图论。图论是数学的一个分支，它以图为研究对象，图论中的图是由若干给定的点及连接两点的线所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系，用点代表事物，用连接两点的线表示相应两个事物间具有这种关系。图论本身有很多分支，如几何图论、组合图论、算法图论、随机图论、代数图论等。通常我们说的图论是组合图论，而在人工智能的领域里代数图论也有很重要的应用。
2-3.图论
2-3-1.顶点和边
顶点表示某个事物或对象，如下图中的用户A、用户B、用户C。
边表示事物和事物的关系，如下图中的关联因子a、关联因子b、关联因子c。
2-3-2.有向图和无向图
无向图：节点之间的边不存在方向。如下图：
有向图：节点之间的边存在方向。如下图：
2-3-3.同构图和异构图
异构图：可以存在多种节点和边。如下图，可以存在多种节点(用户、手机号、设备)。
同构图：只存在一种节点和边。如下图，只存在一种节点(用户节点)。
2-3-4.邻接矩阵和邻接表
邻接矩阵和邻接表是图的两种表现形式。
邻接矩阵用一个一维数组存储顶点的信息 和 二维数组来边的信息 上图的邻接矩阵表示：
| A | B | C | D | E | F | |
|---|---|---|---|---|---|---|
| A | 0 | 0 | 1 | 0 | 0 | 1 |
| B | 0 | 0 | 1 | 1 | 0 | 1 |
| C | 1 | 1 | 0 | 0 | 1 | 0 |
| D | 0 | 1 | 0 | 0 | 1 | 0 |
| E | 0 | 0 | 1 | 1 | 0 | 0 |
| F | 1 | 1 | 0 | 0 | 0 | 0 |
邻接表数组（顶点集）+链表（边集）的形式 无向图的邻接表：
2-3-5.路径和最短路径
路径：从图中一个顶点到另一个顶点所经过的长度叫做路径。其中，长度最小的路径叫做最短路径。最短路径问题主要包括两个方面：单源最短路径：给定顶点到其它所有顶点的最短路径问题。多源最短路径：每对顶点之间的最短路径问题。一般求图中路径的方法最通用的就是广度优先遍历算法和深度优先遍历算法。求最短路径常用算法有很多，比如Dijkstra算法、Floyd算法。在此就不展开讲啦～
2-3-6.连通图和连通分量
在无向图G中，如果从顶点 v 到顶点 w 有路径存在，则称 v 和 w 是连通的。如果图G中任意两个顶点 v 和 m 都是连通的（即任意两个顶点连通），则称G是连通图（Connected Graph）。无向图中的极大连通子图称为连通分量。注意连通分量的概念，它强调：
要是子图； 子图要是连通的； 连通子图含有极大顶点数； 具有极大顶点数的连通子图包含依附于这些顶点的所有边。
上图的图a是一个无向非连通图。但是它有两个连通分量，即图b和图c；而图d尽管是图a的子图，但它却不满足连通子图的极大顶点数；因此它不是图a无向图的连通分量。
3.关联图谱架构
3-1.关联方案
3-1-1.同构图 vs 异构图
上面图论基础中介绍过，同构图只存在一种行为/关系，而异构图存在多种行为和关系。只存储用户和关联因子的情况下：
| 同构图 | 异构图 | |
|---|---|---|
| 存储成本 | 低 | 高 |
| 图的大小 | 小 | 大 |
| 计算复杂度 | 低 | 高 |
所以，同构图既符合应用场景，又能最小代价的解决问题。
3-1-2.图——>树
将图五中错综复杂的关系以用户A为树的根节点，F、C为第二层树节点，以此类推，将图五表示成树的形式，这种树型的形式对于线上单一用户的关联比较容易理解。如下图
3-2. 关系存储
如下图所示，有一组这样的关联数据，该怎么存储呢？
3-2-1. MySQL
设备表：
| 用户uid | 设备信息 | 时间 |
|---|---|---|
| 用户A | 设备a | t1 |
| 用户B | 设备d | t2 |
| 用户C | 设备a | t3 |
| 用户C | 设备b | t4 |
| 用户C | 设备f | t5 |
| 用户D | 设备f | t6 |
| 用户D | 设备c | t7 |
| 用户F | 设备b | t8 |
| 用户G | 设备c | t9 |
手机号表:
| 用户uid | 手机号信息 | 时间 |
|---|---|---|
| 用户A | 手机号a | t1 |
| 用户A | 手机号b | t2 |
| 用户B | 手机号a | t3 |
| 用户B | 手机号c | t4 |
| 用户D | 手机号b | t5 |
为啥关联因子要分开存储？这是具体的业务形态决定的，各个关联因子分散在不同的业务中。
3-2-2. Redis
redis存储的是key-set结构，这样就可以快速定位到对应的用户(或者关联因子)关联的数据(类似于前面介绍的邻接表)。
3-2-3. 图数据库
图数据库虽然对图计算和图查询有很好的支持，但是会有一些弊端（如neo4j缺少集群和横向扩展的能力)。并且集群运维也需要专门的人力去覆盖，暂时来说还不做考虑。
3-3. 关联架构
3-3-1. 关联结构
3-3-2. 关联架构图
3-4. 关联降噪
随着关联因子纬度的增多，并非每个关联因子都能绝对准确的刻画两个用户之间的关系。有些弱关联会造成关联误伤，为了提高准确性，需要将弱关联因子降噪。
3-4-1. 关联增加限定条件
关联因子存在过期时间，因子长时间未活跃的，设置无效关联。 排除无效关联因子，比如说：手机号11111111111。 弱关联因子组合使用，组合次数越多，准确越高。
3-4-2. 排除异常关联部分
某一个关联因子关联用户太多，这种就需要考虑因子的准确性问题。
3-4-3. 设置关联上限
设置关联上限，一是保证接口的时效性；二是防止关联过多带来的误伤太大。
3-4-4. 设置关联层级
层级越深，召回越大，关联误伤越多；在实际业务场景中，需要根据业务权衡召回和准确。
3-5. 关联扩召
3-5-1. 弱关联因子
比如说，同一个ip、同一个地址等等。弱关联也可通过降噪使用增加召回。
3-5-2. 行为相似关联
团伙在进行操作的时候基本上都会统一操作，脚本程序自动化操作，所以行为存在很大的相似性，增加行为相似的关联也能扩大关联的召回。
4. 关联图谱应用
4-1. 关联特征挖掘
我们可以根据关系挖掘出许多特征。比如，团伙用户的中心性相关的特征。中心性(centrality)体现了节点在关联中的重要程度，衡量指标主要包括度中心性(Degree centrality)、紧密中心性(Closeness centrality)、中介中心性(Betweenness centrality)、特征向量中心性(eigenvectorcentrality)等。简单介绍下度中心性(Degree centrality): 度中心性定义为节点上度的数目，是关联图谱中中心度量方式。一个节点如果与很多其他节点发生直接联系，那么这个节点就处于中心地位。通过这个我们就可以挖掘一些最直接的特征，比如：用户下关联因子的数量、关联因子关联的用户数量等等。
还有许多其他的相关的特征，在此不一一列出。
4-2.关联染色
4-2-1. 关联染色定制化
关联因子层级可配，关联因子可配置 关联因子和关联层级针对具体的业务配置，根据业务场景的准确性进行后续的处置(直接处罚，降级处罚，人工审核等)。
4-2-2. 主动染色
4-2-2-1. 策略(运营人员)识别染色
4-2-2-2. 场景行为关联染色
如上图流程，用户A在平台内进行登录行为的时候；当前请求中含有用户的唯一编码、设备信息等。此时，以用户A为树中的一个点经过设备(关联因子1)去发散，发散的层级根据具体的业务场景去决策。如果在发散的过程中，发现与之关联的账户是黑产账户，用户A就会染成黑色账户或者灰色账户，为后续用户风险识别提供决策依据。注意:如果确定要将用户A染色，务必记录染色的源头账户以及关联染色的关系链，为后续分析提供证据。比如：用户A->B->F->G，发现F和G都是黑产账户，可以将A账户染色，B账户染色。记录A、B账户的源头账户是F的源头账户(F账户可能也是关联染色的账户，因此此处记录的是最终的源头)。
4-2-3. 染色解除
如果发现黑产账户误染，解除当前账户的时候要查看当前账户是源头染色还是非源头染色；如果是源头染色，确认无误后，解除此源头下所有的染色用户；如果是非源头染色，首先要确认此账户源头染色账户是否有问题，如果属于误染，解除团伙所有的染色。如果不属于误染，再确认下当前账户是否有问题，如果属于关联因子准确性导致的误染，需要解除当前账户染色以及因为当前账户关联的染色，再将当前账户的关联因子清除(防止关联因子再次误伤)；还可以把当前账户孤立，就不会再次误伤了；账户孤立的弊端就是此账户不会再在团伙中出现。
4-3. 运营后台展示
4-3-1. 关联账户信息
4-3-2. 用户之间的关联路径
由于关联数据存储和关联层级配置，选择的是广度优先遍历算法。如图十七：用户S和用户E的关联路径
4-4. 关联数据分析
4-4-1. 用户关联
表1
| 用户uid | 关联因子a |
|---|---|
| uid1 | 关联因子1 |
| uid2 | 关联因子2 |
| ...... | ...... |
| uidn | 关联因子n |
hive表关联，一个join表操作就能将关联数据输出:
select
distinct zzt2.用户uid as 用户A,
zzt3.用户uid as touid As 用户B,
zzt1.关联因子a as 关联因子
from
(select 关联因子a from 表1 group by 关联因子a having count(1)>=2 ) zzt1
JOIN
(select 用户uid,关联因子a from 表1 ) zzt2
ON
zzt1.关联因子a=zzt2.关联因子a
JOIN
(select 用户uid,关联因子a from 表1) zzt3
ON
zzt1.关联因子a=zzt3.关联因子a
当然，实际工程中要比这个复杂，关联因子的数据要经过多次的预处理。
4-4-2. 关联分组
通过Graphx的connectedComponents求图中的连通图，选取连通图中的一个id作为组id，这个是为了方便数据分析用。上面连通图已经介绍过了，此处不再次介绍。
4-5. 关联监控
4-5-1. 大团伙监控
团伙数量大于n的团伙定时check。关联账户数量太多，属于很不正常的特征。需要定时review大账户的用户行为，进行染色或者重点监控。
4-5-2. 关联占比
监控团伙用户(关联账户>2)的占比，数据波动应该稳定在一定的范围之内；否则，要引起重视。
4-5-3. 团伙请求qps占比
这个指标需要实时监控，如果指标突然占比增多，大概率有团伙在作案，需要根据行为重点跟踪。
5. 总结
关联图谱是一种非常有效的风控基础能力，关联强度的定义要和业务逻辑融合；关联因子的强弱选择和具体的业务场景是相辅相成的，关联图谱的准确和召回也跟具体的业务场景有莫大的联系；因此，要从实际的业务场景出发，选择适合自己业务的关联能力。
作者介绍:
刘冬冬，转转资深研发，多年风控研发经验，主要负责风控架构，涉及策略引擎、关联图谱等风控核心能力。
想了解更多转转公司的业务实践，欢迎点击关注下方公众号：