极验原创

2019/05/09 12:05

张行军作者

金融风控反欺诈之图算法

先介绍下金融借贷业务流程：用户前来申请借贷，会先经过欺诈识别，把欺诈团伙和主观欺诈的个人拒绝掉，然后对通过的人做信用评估，最后根据额度模型，算出利润最大化时放款金额。

刚才提到了团队欺诈，举个真实的例子。xx贷在他们的财报中公布的，他们被一个团伙成功撸走了2000多单，当时xx贷的件均4w，一下损失了8000w！！

那么如何防范这种风险呢。这就是今天要分享的图算法。图可以将这些一个个有良好记录的个体关联起来,一网打尽。

再举一些团伙欺诈的行为。比如一个团伙，注册真实的淘宝商家，然后刷出良好的淘宝购物记录。或者来回转账，刷出良好的银行流水。

刚才前两位老师都没有提到额度模型，简单介绍下，如果只给用户放款5000，可能坏账风险很小，但是利息也少，如果放款10000，利息虽然收到利息多了，但是坏账风险高岭，所以需要做个权衡

Graph简介

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

V:vertex set
E:edge set (有向，无向，有权重和没有权重)

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

度中心性（Degree Centrality） - 表示连接到某节点的边数。在有向图中，我们可以有2个度中心性度量：流入和流出。一个节点的节点度越大就意味着该节点在网络中就越重要。
接近中心性（Closeness Centrality） - 从某节点到所有其他节点的最短路径的平均长度。反映在网络中某一节点与其他节点之间的接近程度。
介中心性（Betweenness Centrality） - 某节点在多少对节点的最短路径上。介数中心性是比较能体现节点在图中桥梁作用的中心性度量方法。介数反映了相应的节点或者边在整个网络中的作用和影响力，具有很强的现实意义。例如，在交通网络中，介数较高的道路拥挤的概率很大；在电力网络中，介数较高的输电线路和节点容易发生危险。

社团发现算法一般有：

最小割，正则化割:通过计算图的最小割，即将网络划分为预定的分组数，并使连接各分组的边的条数最少。
非负矩阵分解:基本原理是将原始矩阵分解得到社区指示矩阵和基矩阵
基于模块度的社区划分
基于节点相似性的社区划分

最小割算法广泛应用在分布式计算的负载均衡中，对集群节点的分组有利于减少不相关节点之间的通信。然而由于该算法限定了网络最终分组的个数，而不能通过算法“发现”节点间的内在联系并自然地构成若干个社区，因此最小割算法应用较为局限。

本文主要分享这两类的主要算法，基于模块度的 louvain和基于信息熵infomap，基于相似度的node2vec

模块度(Modularity)公式及简化

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

所以模块度也可以理解是社区内部边的权重减去所有与社区节点相连的边的权重和，对无向图更好理解，即社区内部边的度数（内部的连线数）减去社区内节点的总度数。

模块度公式的解释

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

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

表示节点i所属的社区；

表示所有边的权重之和（边的数目）。

其中表示社区c内的边的权重之和，表示与社区c内的节点相连的边的权重之和，即社区c节点的度之和（包含与其他社区相连边的度）。

从概率的角度去看：

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

表示在一种理想情况下，给定任意节点i的的度ki，对节点i和节点j进行随机连边，边属于社区c的概率期望。

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

一般使用后面简化的公式，简化后的公式删除了判断两个节点是否划为同一个社区的函数，所以在一定程度上大大减少了Q值计算量。

Louvain

Louvain算法的思想很简单：

将图中的每个节点看成一个独立的社区，此时社区的数目与节点个数相同；
对每个节点i，依次尝试把节点i分配到其每个邻居节点所在的社区，计算分配前与分配后的模块度变化，并记录最大的那个邻居节点，如果，则把节点i分配最大的那个邻居节点所在的社区，否则保持不变；
重复2，直到所有节点的所属社区不再变化；
对图进行压缩，将所有在同一个社区的节点压缩成一个新节点，社区内节点之间的边的权重转化为新节点的环的权重，社区间的边权重转化为新节点间的边权重，然后重复2，3；
重复2~4，直到整个图的模块度不再发生变化。

第一阶段称为Modularity Optimization，主要是将每个节点划分到与其邻接的节点所在的社区中，以使得模块度的值不断变大；

第二阶段称为Community Aggregation，主要是将第一步划分出来的社区聚合成为一个点，即根据上一步生成的社区结构重新构造网络。重复以上的过程，直到网络中的结构不再改变为止。

移动

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

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

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

http://www.cnblogs.com/fengfenggirl/p/louvain.html

2. Spark GraphX分布式图计算实战

infomap

从信息论的角度出发，假设一个random worker 在图上进行随机游走，那么怎么用最少的编码长度来表示其路径呢？

如果节点存在社区结构，那么社区内的节点就可以共享社区的bit位码，可以得到更小的平均比特, 所以社区划分的越好，那么表示任意一条随机游走的路径所需的平均比特就越小。

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

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

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

利用pagerank思路，初始化了每个节点的到达概率之后，就可以不断地迭代更新每个节点的到达概率，这个结果会很快趋于收敛。

其实这过程就是一个马尔科夫随机过程，随机初始化起始值，然后随机游走就相当于不停地用概率转移矩阵相乘，最后就可以达到马尔科夫稳态。

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

定义清楚各类事件的发生概率，依据信息熵公式，就可以得到此时编码所需的平均比特了,其本质就是从信息论的角度出发。

Infomap算法的迭代过程

初始化，对每个节点都视作独立的社区；
while 平均比特的值不再下降；
对图里的节点随机采样出一个序列，按顺序依次尝试将每个节点赋给邻居节点所在的社区，取平均比特下降最大时的社区赋给该节点，如果没有下降，该节点的社区不变。

参考链接

1. The map equation

http://www.mapequation.org/apps/MapDemo.html

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

3. DEEP GRAPH INFOMAX 阅读笔记

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

Graph embeddings

Deepwalk

使用随机游走(RandomWalk)的方式在图中进行节点采样获得节点共关系，
使用skip-gram，根据步骤1中生成的节点序列学习每个节点的向量表示。skip-gram就是根据给定输入的节点，预测上下文节点。

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

其中一个就是采样，从其邻居中随机采样节点作为下一个访问节点，是一种可重复访问已访问节点的深度优先遍历算法。

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

node2vec

优化目标：

条件独立假设：

特征空间的对称性：

优化目标：

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

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

我们最初是用一个Python写的包，跑一遍算法需要一周。后来想，既然优化目标是一样的，那能不能用word2vec包，因为word2vec用c写的，而且还采用了 Hierarchical Softmax，negative sampling加速。

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

随机游走的方式

复杂网络处理的任务其实离不开两种特性，前面也提到过：一种是同质性，就是之前所说的社区。一种就是结构相似性，值得注意的是，结构相似的两个点未必相连，可以是相距很远的两个节点。

能不能改进DeepWalk中随机游走的方式，使它综合DFS和BFS的特性呢？所以本文引入了两个参数用来控制随机游走产生的方式。

Z是分子的归一化常数

如果已经采样了 (t,v) ，也就是说现在停留在节点v上，那么下一个要采样的节点x是哪个？作者定义了一个概率分布，也就是一个节点到它的不同邻居的转移概率：

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

如果t与x相等，那么采样x的概率为；
如果t与x相连，那么采样x的概率1；
如果t与x不相连，那么采样x概率为

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

返回概率p：

如果 p>max(q,1) ，那么采样会尽量不往回走，对应上图的情况，就是下一个节点不太可能是上一个访问的节点t。
如果 p<min(q,1) ，那么采样会更倾向于返回上一个节点，这样就会一直在起始点周围某些节点来回转来转去。

出入参数q：

如果 q>1 ，那么游走会倾向于在起始点周围的节点之间跑，可以反映出一个节点的BFS特性。
如果 q<1 ，那么游走会倾向于往远处跑，反映出DFS特性。
当p=1，q=1时，游走方式就等同于DeepWalk中的随机游走。

简而言之：

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

参数q控制着游走是向外还是向内，若q>1，随机游走倾向于访问和t接近的顶点(偏向BFS)。若q<1，倾向于访问远离t的顶点(偏向DFS)。

缺点

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

comE

Graphembedding得到向量后，可以做很多事情，在我们这个主题可以简单的通过聚类来讲节点分组。

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

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

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

1. https://blog.csdn.net/u012151283/article/details/87013915

2. Learning Community Embedding with Community Detection and Node Embedding on Graphs

https://zhuanlan.zhihu.com/p/36924789

3. Learning Community Embedding with Community Detection and Node Embedding on Graphs

https://github.com/vwz/ComE

4. http://sentic.net/community-embedding.pdf

评价指标

Modularity

标准化互信息 NMI ( Normalized Mutual Information )

假设对于N个样本点的两种标签划分为U 和 V. 熵为划分集的不准确性

极验

极验是全球顶尖的交互安全技术服务商，于2012年在武汉成立。全球首创 “行为式验证技术” ，利用生物特征与人工智能技术解决交互安全问题，为企业抵御恶意攻击防止资产损失提供一站式解决方案。

理论算法反欺诈

相关数据

近似计算技术

近似计算是一种计算技术，它返回可能不准确的结果而不是保证的准确结果，并且可以用于近似结果足以满足其目的的应用。

来源：维基百科

权重技术

线性模型中特征的系数，或深度网络中的边。训练线性模型的目标是确定每个特征的理想权重。如果权重为 0，则相应的特征对模型来说没有任何贡献。

来源：Google AI Glossary

参数技术

在数学和统计学裡，参数（英语：parameter）是使用通用变量来建立函数和变量之间关系（当这种关系很难用方程来阐述时）的一个数量。

来源：维基百科

Q值技术

Q值是原子核物理学及核化学中的名词，核反应的Q值是指核反应所产生的能量： Q=E(Reactants)-E(Products), Q值为正的核反应是放热反应，Q值为负的核反应是吸热反应 Q值也用在粒子物理学中，例如萨晋定律（Sargent's rule）中提到弱相互作用的反应速度和Q值的五次方成正比。Q值是静止的粒子衰变时产生的动能，例如中子的衰变： Q=（m_n - m_p - m_v - m_e）c^2 其中m_n是中子的质量，m_p是质子的质量，m_ν是电中微子的质量，m_e是电子的质量

来源：维基百科

收敛技术

在数学，计算机科学和逻辑学中，收敛指的是不同的变换序列在有限的时间内达到一个结论（变换终止），并且得出的结论是独立于达到它的路径（他们是融合的）。通俗来说，收敛通常是指在训练期间达到的一种状态，即经过一定次数的迭代之后，训练损失和验证损失在每次迭代中的变化都非常小或根本没有变化。也就是说，如果采用当前数据进行额外的训练将无法改进模型，模型即达到收敛状态。在深度学习中，损失值有时会在最终下降之前的多次迭代中保持不变或几乎保持不变，暂时形成收敛的假象。

来源：Wikipedia Google ML glossary

随机过程技术

在概率论概念中，随机过程是随机变量的集合。若一随机系统的样本点是随机函数，则称此函数为样本函数，这一随机系统全部样本函数的集合是一个随机过程。实际应用中，样本函数的一般定义在时间域或者空间域。随机过程的实例如股票和汇率的波动、语音信号、视频信号、体温的变化，反对法随机运动如布朗运动、随机徘徊等等。

来源：维基百科

非负矩阵分解技术

信息熵技术

在信息论中，熵是接收的每条消息中包含的信息的平均量，又被称为信息熵、信源熵、平均自信息量。这里，“消息”代表来自分布或数据流中的事件、样本或特征。熵的单位通常为比特，但也用Sh、nat、Hart计量，取决于定义用到对数的底。

来源：维基百科

目标函数技术

目标函数f(x)就是用设计变量来表示的所追求的目标形式，所以目标函数就是设计变量的函数，是一个标量。从工程意义讲，目标函数是系统的性能标准，比如，一个结构的最轻重量、最低造价、最合理形式；一件产品的最短生产时间、最小能量消耗；一个实验的最佳配方等等，建立目标函数的过程就是寻找设计变量与目标的关系的过程，目标函数和设计变量的关系可用曲线、曲面或超曲面表示。

来源：百度百科

正则化技术

当模型的复杂度增大时，训练误差会逐渐减小并趋向于0；而测试误差会先减小，达到最小值后又增大。当选择的模型复杂度过大时，过拟合现象就会发生。这样，在学习时就要防止过拟合。进行最优模型的选择，即选择复杂度适当的模型，以达到使测试误差最小的学习目的。

来源：李航著统计学习方法清华大学出版社

分布式计算技术技术

在计算机科学中，分布式计算，又译为分散式運算。这个研究领域，主要研究分布式系统如何进行计算。分布式系统是一组电脑，通过网络相互链接传递消息与通信后并协调它们的行为而形成的系统。组件之间彼此进行交互以实现一个共同的目标。

来源：维基百科

信息论技术

信息论是在信息可以量度的基础上，研究有效地和可靠地传递信息的科学，它涉及信息量度、信息特性、信息传输速率、信道容量、干扰对信息传输的影响等方面的知识。通常把上述范围的信息论称为狭义的信息论，又因为它的创始人是香农，故又称为香农信息论。

来源：曹雪虹等信息论与编码(第2版) 清华大学出版社

矩阵分解技术

矩阵分解是一种将矩阵简化为其组成部分的方法。这种方法可以简化更复杂的矩阵运算，这些运算可以在分解的矩阵上执行，而不是在原始矩阵本身上执行。它的衍生Non-negative matrix factorization也被用于降维等操作上。

来源：矩阵分解