2024金融风控反欺诈图行算法

金融风控反欺诈图算法

先介绍下金融借贷业务流程：用户前来申请借贷，会先经过欺诈识别，把欺诈团伙

和主观欺诈的个人拒绝掉，然后对通过的人做信用评估，最后根据额度模型，算

出利润最大化时放款金额。

刚才提到了团队欺诈，举个真实的例子。宜人贷在他们的财报中公布的，他们被

一个团伙成功抬走了2000多单，当时宜人贷的件均4w,一下损失了8OOOW!!

那么如何防范这种风险呢。这就是今天要分享的图算法。图可以将这些一个个有

良好记录的个体关联起来，一网打尽。

再举一些团伙欺诈的行为。比如一个团伙，注册真实的淘宝商家，然后刷出良好的

淘宝购物记录。或者来回转账，刷出良好的银行流水。

刚才前两位老师都没有提到额度模型，简单介绍下，如果只给川户放款5000,

可能坏账风险很小，但是利息也少，如果放款1OOOO,利息虽然收到利息多了，

但是坏账风险高岭，所以需要做个权衡

Graph简介

G=(V,E)G=(V,E)

•V:vertexset

•E:edgeset(有向，无向，有权重和没有权重)

举例，两个人之间的联系，A给B买了东西，A和B之间的通话次数时长多于A

和C之间。

•度中心性(DegreeCentrality)-表示连接到某节点的边数。在有向图中，

我们可以有2个度中心性度量：流入和流出。一个节点的节点度越大就意味

着该节点在网络中就越重要。

•接近中心性(ClosenessCentrality)-从某节点到所有其他节点的最短路径

的平均长度。反映在网络中某一节点与其他节点之间的接近程度。

•介中心性(BetweennessCentrality)-某节点在多少对节点的最短路径上。

介数中心性是比较能体现节点在图中桥梁作用的中心性度量方法。介数反映

了相应的节点或者边在整个网络中的作用和影响力，具有很强的现实意义。

例如，在交通网络中，介数较高的道路拥挤的概率很大；在电力网络中，介

数较高的输电线路和节点容易发生危险。

社团发现算法一般有：

•最小割，正则化割:通过计算图的最小割，即将网络划分为预定的分组数，

并使连接各分组的边的条数最少。

•非负矩阵分解:基本原理是将原始矩阵分解得到社区指示矩阵和基矩阵

•基于模块度的社区划分

•基于节点相似性的社区划分

最小割算法广泛应用在分布式计算的负载均衡中，对集群节点的分组有利于减少不

相关节点之间的通信。然而由于该算法限定了网络最终分组的个数，而不能通过算

法"发现”节点间的内在联系并自然地构成若干个社区，因此最小割算法应用较为局

限。

本文主要分享这两类的主要算法，基于模块度的louvain和基于信息燧infomap,

基于相似度的node2vec

模块度(Modularity)公式及简化

优化目标：一般认为社团内部的点之间的连接相对稠密，而不同社团的点之间的连

接相对稀疏。

所以模块度也可以理解是社区内部边的权重减去所有与社区节点相连的边的权重和,

对无向图更好理解，即社区内部边的度数(内部的连线数)减去社区内节点的总度

数。

诟T

1网£/kjkj

A3(G,0)

2m2m

L2,J

(EG?

E-2m

=E

c

Iwhenuv

8(%o)=

{0else

模块度公式的解释

“行节点।和节点j之间边的权重，网络不是带权图时，所有边的权重可以看做

是1：

%二£4,表示所有与节点i相连的边的权重之和（度数）；

Q表示节点i所属的社区;

m=2&表示所有边的权重之和（边的数目）。

其中Sm表示社区c内的边的权重之和，土表示与社区c内的节点相连

的边的权重之和，即社区C节点的度之和（包含与其他社区相连边的度）。

从概率的角度去看：

‘C表示实际情况下，c社区内产生边的概率。

+一

aC^*表_不在一种理想情况卜，给定任意节点i的的度ki,对节点i和节点j进行

随机连边，边属于社区c的概率期望。

于是上式就表示了社区内连边数与随机期望的一个差值。连边数比随机期望值越高,

表明社区划分的越好。

一般使用后面简化的公式，简化后的公式删除了判断两个节点是否划为同一个社

区的函数，所以在一定程度上大大减少了Q值计算量。

Louvain

Louvain算法的思想很简单：

•一i，依次注试把节后i分h£节心所在的社区，计算分

配前与分配后的模块度变化△Q,并记录△Q最大的那个

如果maxAQ〉0

邻居节点则把节点i分配

△Q最大的那个邻居节点所在的社区，否则保持不变:

•电复2,■到所有节点的所属社区不再变化；

点之间的边的权重转化为新节点的环的权重，社区间的边权重转化为新节

点间的边权重，然后重复2,3：

•丁.复2~4,，仃.咬不再发生变化。

第一阶段称为ModularityOptimization,主要是将每个节点划分到与其邻接的节点

所在的社区中，以使得模块度的值不断变大；

第二阶段称为CommunityAggregation,主要是将第一步划分出来的社区聚合成为

一个点，即根据上一步生成的社区结构重新构造网络。重复以上的过程，直到网络

中的结构不再改变为止。

2m2m2

'[2,271是社区c内节点与节点i的边权重之和，再乘以2

前面部分表示把节点i加入到社区c后的模块度，后一部分是节点i作为一个独立

社区和社区c的模块度

1,模块度与Louvain社区发现算法

blogs.eom/fengfenggirl/p/louvain.html

2.SparkGraphX分布式图计算实战

3

7

infomap

从信息论的角度出发，假设个randomworker在图上进行随机游走，那么怎么

用最少的编码长度来表示其路径呢？

如果节点存在社区结构，那么社区内的节点就可以共享社区的bit位码，可以得到

更小的平均比特，所以社区划分的越好，那么表示任意一条随机游走的路径所需的

平均比特就越小。

如果我们能够计算出每个节点的到达概率，就可以依据信息燔的公式来量化平均比

特了：

工(尸)=H(P)=PalogPa

怎么计算每个点的到达概率呢？

一个暴力的办法是在图上进行长时间的随机游走，最后统计每个节点的出现概率。

太暴力了。

利用pagerank思路，初始化了每个节点的到达概率之后，就可以不断地迭代更新

每个节点的到达概率，这个结果会很快趋于收敛。

其实这过程就是一个马尔科夫随机过程，随机初始化起始值，然后随机游走就相当

于不停地用概率转移矩阵相乘，最后就可以达到马尔科夫稳态。

把随机游走事件归为二类：进入某个社团，离开某个社团，再社团内部游走.

定义清楚各类事件的发生概率，依据信息燧公式，就可以得到此时编码所需的平

均比特了,其本质就是从信息论的角度出发。

£(M)=qcH(Q)+E^p"H(#)

L(M)将图划分成m个社区，编码随机游走路径时的平均比特；

qc=EZiqs产生进入社区这种事件的总概率；

H(Q)=-ZZ】(qs/qc)iog®c/qc)进入社区事件发生的信息嫡；

Pi。=ZaQpa+qcrandomworker在社区i内部的概率，这里包括了在社区内跳转和离

开该社区两类事件；

H(尸)=-(qc/p©)log(q八"2)

-Za€/(Pa/P<U)log(Pa/PfO)randomworker下一步事件发生在社区i内部的信息嫡；

Infomap算法的迭代过程

1,初始化，对每个节点都视作独立的社区；

2.while平均比特的值不再下降；

3,对图里的节点随机采样出一个序列，按顺序依次尝试将每个节点赋给邻居节

点所在的社区，取平均比特下降最大时的社区赋给该节点，如果没有下降，

该节点的社区不变。

参考链接

1.Themapequation

/apps/MapDemo.html

2.https://mp.weixin.qq.eom/s/qUxMesQA-edSyHeudQRRGA

3.DEEPGRAPHINFOMAX阅读笔i己

https://zhuanlan.zhihu.eom/p/58682802

Graphembeddings

Deepwalk

1.使用随机游走(Randomwalk)的方式在图中进行节点采样获得节点共关系，

2,使用skip-gram,根据步骤1中生成的节点序列学习每个节点的向量表示。

skip-gram就是根据给定输入的节点，预测上下文节点。

Deepwalk有多不足，比如泛化能力，有新节点加入时，它必须重新训练模型以表示

该节点。

其中一个就是采样，从其邻居中随机采样节点作为下一个访问节点，是一种可重复

访问已访问节点的深度优先遍历算法。

node2vec是一种综合考虑DFS邻域和BFS邻域的graphembedding方法

node2vec

优化FI标：

loPr

maxEuevg^s(iz)|/(u))

条件独立假设：

Pr(Ns(u)\f(u})=EUw)尸/(出〃3))

特征空间的对称性：

尸丁(电|加))=/冲皿少叫、、

优化目标：

m；x工叱匕jog+£除心(〃)/(%)・/(〃)]

Z

u=Euevexp(/(u)•/®))计算

量非常大，所以论文采用负采样(negativesample)进行近似计算。

这个node2vec优化目标函数，因为它跟大名鼎鼎的word2vec是一样。

我们最初是用一个Python写的包，跑一遍算法需要一盾。后来想，既然优化目标

是一样的，那能不能用word2vec包，因为word2vec用c写的，而旦还采用了

HierarchicalSoftmax,negativesampling加速。

然后在网上找到了一个套用word2vec实现的nodeZvec包，速度快很多。

随机游走的方式

复杂网络处理的任务其实离不开两种特性，前面也提到过：一种是同质性，就是之

前所说的社区。一种就是结构相似性，值得注意的是，结构相似的两个点未必相连,

可以是相距很远的两个节点。

能不能改进DeepWalk中随机游走的方式，使它综合DFS和BFS的特性呢？所以

本文引入了两个参数用来控制随机游走产生的方式。

尸匕=小一=。)=，吗也if(v，x"E

[0otherwise

(jifdtx=O

(%，/)=(1ifdtx=1

if4,=2

z是分子的归一化常数

如果已经采样了(t,v),也就是说现在停留在节点v上，那么下一个要采样的节点

x是哪个？作者定义了一个概率分布，也就是一个节点到它的不同邻居的转移概率:

直观的解释一下这个分布：

1

•如果t与X相等，那么采样X的概率为P；

•如果t与X相连，那么采样X的概率1：

1

•如果t与x不相连，那么采样x概率为q

参数p、q的意义分别如下：

返回概率P：

DataFunTalk成就百万数据科学家！

•如果p>max(q/l),那么采样会尽量不往回走，对应上图的情况，就是卜一

个节点不太可能是上一个访问的节点to

•如果p<min(q,l),那么采样会更倾向于返回上一个节点，这样就会一直在

起始点周围某些节点来回转来转去。

出入参数q：

•如果q>l,那么游走会倾向于在起始点周围的节点之间跑，可以反映出一

个节点的BFS特性。

•如果q<l,那么游走会倾向于往远处跑，反映出DF$特性。

•当p=l,q=l时，游走方式就等同于DeepWalk中的随机游走。

简而言之：

参数p控制重复访问刚刚访问过的顶点的概率，

参数q控制着游走是向外还是向内，若q>l,随机游走倾向于访问和t接近的顶

点(偏向BFS)o若q<l»倾向于访问远离t的顶点(偏向DFS)o

缺点

1慢

2,先embedding再聚类，感觉这两个过程很割裂！！融合一下

comE

Graphembedding得到向最后，可以做很多事情，在我们这个主题可以简单的通过

聚类来讲节点分组。

但是这个过程比较割裂，先优化node2vec,然后再优化聚类。能不能整体上一次

性优化完呢。

comE这个算法优化目标中加入了社区的检测和嵌入°通过一个混合高斯模型将节

点划分开。

Aj/：

6=~aEr,eVLvjCCi

皿乩­

一阶LOSS二阶LOSS社区LOSS

£(4>,6'.H.丸£)=01.)+。2仲仲')+3仲,Q£),oX°

°'6

Ourfinaloptimizationproblembecomes：P

一argmin£(4>.力'/1,北£)

0|=-EeEy

VA.d.；og(XQ>0仙切咏仪可

a=-£z*1%>3%N（我版.&）,

_____ES33

<1>.社区检测和社区嵌入。

这篇论文比较创新的一点，就是将社区嵌入定义为低维空间中的多元高斯分布。即对于社区k来说（

）,它在d维空间下的社区嵌入是一个多元高斯分布M（物fc,EQ,其中

矽AW〃表示的是社区内节点的平均向H（即中心点），&€N表示的是协方差矩阵。

整篇文章最大的难点在于，如何用统一的目标函数来使得社区嵌入、社区检测和节点嵌入三者问题

得到最优化的结果。由于社区嵌入是由多元高斯分布来表达的，因此就可以通过高斯混合模型来完

成。

假设每一个节点的嵌入向量仇可以由该节点所在社区的多元高斯分布产生，这样一来，就可以得

到一个似然目标函数：

\V\K

n£p（苍=向p（奶忸=A；M吸,⑴

»=1k=l

其中，p（Zi=k）表示的是节点明属于社区k的概率。方便表示，可以将这个概率表达为7T,Jt：

K

7TikW砥A=I.在社区发现问题中，这个概率是未知的。

*=1

而p（Vi\zi=A;八，@k,纨）=M（力地k,之）表示的是多元高斯分布。在社区嵌入问题中，

如,£k是未知的。

综上，将公式1对上述三个未知变量求导，就可以同时实现社区检测和嵌入。

优化目标中前面两项跟LINE定义的相似度相似:

1st

对于每一条无向边G,j）,定义顶点口和町之间的联合旗率为：

Pi（%,与）=%占沽@电，色为顶，京叨的低维向■表示♦何以看作一个内积模型，计算两个item之间的匹配程度）

同时定义经蛉分布肉=带,W=£g）cE5j

优化目标为最小化：Oi=d（d

</《，•）是两个分布的距离，常用的衡■再个概率分布差异的指标为KL散度，使用KL8I度并忽略常数项后有

°】=一E（M）€ElogPi（5,与）

1»lorder怕似度只能用于无向国当中.

2nd

这里对于每个顶点维护两个embedding向量，一个是该顶点本身的表示向■,一个是该点作为其他顶点的上下文顶点时的

表示向

对于有向边G，j）,定义给定点助条件下，产生上下文（邻居）顶点盯的概率为

r（叼|5）=耳喘抬，其中VI为上下文顶点的个数.

优化目标为

。2