2024金融風(fēng)控反欺詐圖行算法

金融風(fēng)控反欺詐圖算法

先介紹下金融借貸業(yè)務(wù)流程：用戶前來(lái)申請(qǐng)借貸，會(huì)先經(jīng)過(guò)欺詐識(shí)別，把欺詐團(tuán)伙

和主觀欺詐的個(gè)人拒絕掉，然后對(duì)通過(guò)的人做信用評(píng)估，最后根據(jù)額度模型，算

出利潤(rùn)最大化時(shí)放款金額。

剛才提到了團(tuán)隊(duì)欺詐，舉個(gè)真實(shí)的例子。宜人貸在他們的財(cái)報(bào)中公布的，他們被

一個(gè)團(tuán)伙成功抬走了2000多單，當(dāng)時(shí)宜人貸的件均4w,一下?lián)p失了8OOOW!!

那么如何防范這種風(fēng)險(xiǎn)呢。這就是今天要分享的圖算法。圖可以將這些一個(gè)個(gè)有

良好記錄的個(gè)體關(guān)聯(lián)起來(lái)，一網(wǎng)打盡。

再舉一些團(tuán)伙欺詐的行為。比如一個(gè)團(tuán)伙，注冊(cè)真實(shí)的淘寶商家，然后刷出良好的

淘寶購(gòu)物記錄?；蛘邅?lái)回轉(zhuǎn)賬，刷出良好的銀行流水。

剛才前兩位老師都沒(méi)有提到額度模型，簡(jiǎn)單介紹下，如果只給川戶放款5000,

可能壞賬風(fēng)險(xiǎn)很小，但是利息也少，如果放款1OOOO,利息雖然收到利息多了，

但是壞賬風(fēng)險(xiǎn)高嶺，所以需要做個(gè)權(quán)衡

Graph簡(jiǎn)介

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

?V:vertexset

?E:edgeset(有向，無(wú)向，有權(quán)重和沒(méi)有權(quán)重)

舉例，兩個(gè)人之間的聯(lián)系，A給B買(mǎi)了東西，A和B之間的通話次數(shù)時(shí)長(zhǎng)多于A

和C之間。

?度中心性(DegreeCentrality)-表示連接到某節(jié)點(diǎn)的邊數(shù)。在有向圖中，

我們可以有2個(gè)度中心性度量：流入和流出。一個(gè)節(jié)點(diǎn)的節(jié)點(diǎn)度越大就意味

著該節(jié)點(diǎn)在網(wǎng)絡(luò)中就越重要。

?接近中心性(ClosenessCentrality)-從某節(jié)點(diǎn)到所有其他節(jié)點(diǎn)的最短路徑

的平均長(zhǎng)度。反映在網(wǎng)絡(luò)中某一節(jié)點(diǎn)與其他節(jié)點(diǎn)之間的接近程度。

?介中心性(BetweennessCentrality)-某節(jié)點(diǎn)在多少對(duì)節(jié)點(diǎn)的最短路徑上。

介數(shù)中心性是比較能體現(xiàn)節(jié)點(diǎn)在圖中橋梁作用的中心性度量方法。介數(shù)反映

了相應(yīng)的節(jié)點(diǎn)或者邊在整個(gè)網(wǎng)絡(luò)中的作用和影響力，具有很強(qiáng)的現(xiàn)實(shí)意義。

例如，在交通網(wǎng)絡(luò)中，介數(shù)較高的道路擁擠的概率很大；在電力網(wǎng)絡(luò)中，介

數(shù)較高的輸電線路和節(jié)點(diǎn)容易發(fā)生危險(xiǎn)。

社團(tuán)發(fā)現(xiàn)算法一般有：

?最小割，正則化割:通過(guò)計(jì)算圖的最小割，即將網(wǎng)絡(luò)劃分為預(yù)定的分組數(shù)，

并使連接各分組的邊的條數(shù)最少。

?非負(fù)矩陣分解:基本原理是將原始矩陣分解得到社區(qū)指示矩陣和基矩陣

?基于模塊度的社區(qū)劃分

?基于節(jié)點(diǎn)相似性的社區(qū)劃分

最小割算法廣泛應(yīng)用在分布式計(jì)算的負(fù)載均衡中，對(duì)集群節(jié)點(diǎn)的分組有利于減少不

相關(guān)節(jié)點(diǎn)之間的通信。然而由于該算法限定了網(wǎng)絡(luò)最終分組的個(gè)數(shù)，而不能通過(guò)算

法"發(fā)現(xiàn)”節(jié)點(diǎn)間的內(nèi)在聯(lián)系并自然地構(gòu)成若干個(gè)社區(qū)，因此最小割算法應(yīng)用較為局

限。

本文主要分享這兩類(lèi)的主要算法，基于模塊度的louvain和基于信息燧infomap,

基于相似度的node2vec

模塊度(Modularity)公式及簡(jiǎn)化

優(yōu)化目標(biāo)：一般認(rèn)為社團(tuán)內(nèi)部的點(diǎn)之間的連接相對(duì)稠密，而不同社團(tuán)的點(diǎn)之間的連

接相對(duì)稀疏。

所以模塊度也可以理解是社區(qū)內(nèi)部邊的權(quán)重減去所有與社區(qū)節(jié)點(diǎn)相連的邊的權(quán)重和,

對(duì)無(wú)向圖更好理解，即社區(qū)內(nèi)部邊的度數(shù)(內(nèi)部的連線數(shù))減去社區(qū)內(nèi)節(jié)點(diǎn)的總度

數(shù)。

詬T

1網(wǎng)￡/kjkj

A3(G,0)

2m2m

L2,J

(EG?

E-2m

=E

c

Iwhenuv

8(%o)=

{0else

模塊度公式的解釋

“行節(jié)點(diǎn)?和節(jié)點(diǎn)j之間邊的權(quán)重，網(wǎng)絡(luò)不是帶權(quán)圖時(shí)，所有邊的權(quán)重可以看做

是1：

%二￡4,表示所有與節(jié)點(diǎn)i相連的邊的權(quán)重之和（度數(shù)）；

Q表示節(jié)點(diǎn)i所屬的社區(qū);

m=2&表示所有邊的權(quán)重之和（邊的數(shù)目）。

其中Sm表示社區(qū)c內(nèi)的邊的權(quán)重之和，土表示與社區(qū)c內(nèi)的節(jié)點(diǎn)相連

的邊的權(quán)重之和，即社區(qū)C節(jié)點(diǎn)的度之和（包含與其他社區(qū)相連邊的度）。

從概率的角度去看：

‘C表示實(shí)際情況下，c社區(qū)內(nèi)產(chǎn)生邊的概率。

+一

aC^*表_不在一種理想情況卜，給定任意節(jié)點(diǎn)i的的度ki,對(duì)節(jié)點(diǎn)i和節(jié)點(diǎn)j進(jìn)行

隨機(jī)連邊，邊屬于社區(qū)c的概率期望。

于是上式就表示了社區(qū)內(nèi)連邊數(shù)與隨機(jī)期望的一個(gè)差值。連邊數(shù)比隨機(jī)期望值越高,

表明社區(qū)劃分的越好。

一般使用后面簡(jiǎn)化的公式，簡(jiǎn)化后的公式刪除了判斷兩個(gè)節(jié)點(diǎn)是否劃為同一個(gè)社

區(qū)的函數(shù)，所以在一定程度上大大減少了Q值計(jì)算量。

Louvain

Louvain算法的思想很簡(jiǎn)單：

?一i，依次注試把節(jié)后i分h￡節(jié)心所在的社區(qū)，計(jì)算分

配前與分配后的模塊度變化△Q,并記錄△Q最大的那個(gè)

如果maxAQ〉0

鄰居節(jié)點(diǎn)則把節(jié)點(diǎn)i分配

△Q最大的那個(gè)鄰居節(jié)點(diǎn)所在的社區(qū)，否則保持不變:

?電復(fù)2,■到所有節(jié)點(diǎn)的所屬社區(qū)不再變化；

點(diǎn)之間的邊的權(quán)重轉(zhuǎn)化為新節(jié)點(diǎn)的環(huán)的權(quán)重，社區(qū)間的邊權(quán)重轉(zhuǎn)化為新節(jié)

點(diǎn)間的邊權(quán)重，然后重復(fù)2,3：

?丁.復(fù)2~4,，仃.咬不再發(fā)生變化。

第一階段稱為ModularityOptimization,主要是將每個(gè)節(jié)點(diǎn)劃分到與其鄰接的節(jié)點(diǎn)

所在的社區(qū)中，以使得模塊度的值不斷變大；

第二階段稱為CommunityAggregation,主要是將第一步劃分出來(lái)的社區(qū)聚合成為

一個(gè)點(diǎn)，即根據(jù)上一步生成的社區(qū)結(jié)構(gòu)重新構(gòu)造網(wǎng)絡(luò)。重復(fù)以上的過(guò)程，直到網(wǎng)絡(luò)

中的結(jié)構(gòu)不再改變?yōu)橹埂?/p>

2m2m2

'[2,271是社區(qū)c內(nèi)節(jié)點(diǎn)與節(jié)點(diǎn)i的邊權(quán)重之和，再乘以2

前面部分表示把節(jié)點(diǎn)i加入到社區(qū)c后的模塊度，后一部分是節(jié)點(diǎn)i作為一個(gè)獨(dú)立

社區(qū)和社區(qū)c的模塊度

1,模塊度與Louvain社區(qū)發(fā)現(xiàn)算法

blogs.eom/fengfenggirl/p/louvain.html

2.SparkGraphX分布式圖計(jì)算實(shí)戰(zhàn)

3

7

infomap

從信息論的角度出發(fā)，假設(shè)個(gè)randomworker在圖上進(jìn)行隨機(jī)游走，那么怎么

用最少的編碼長(zhǎng)度來(lái)表示其路徑呢？

如果節(jié)點(diǎn)存在社區(qū)結(jié)構(gòu)，那么社區(qū)內(nèi)的節(jié)點(diǎn)就可以共享社區(qū)的bit位碼，可以得到

更小的平均比特，所以社區(qū)劃分的越好，那么表示任意一條隨機(jī)游走的路徑所需的

平均比特就越小。

如果我們能夠計(jì)算出每個(gè)節(jié)點(diǎn)的到達(dá)概率，就可以依據(jù)信息燔的公式來(lái)量化平均比

特了：

工(尸)=H(P)=PalogPa

怎么計(jì)算每個(gè)點(diǎn)的到達(dá)概率呢？

一個(gè)暴力的辦法是在圖上進(jìn)行長(zhǎng)時(shí)間的隨機(jī)游走，最后統(tǒng)計(jì)每個(gè)節(jié)點(diǎn)的出現(xiàn)概率。

太暴力了。

利用pagerank思路，初始化了每個(gè)節(jié)點(diǎn)的到達(dá)概率之后，就可以不斷地迭代更新

每個(gè)節(jié)點(diǎn)的到達(dá)概率，這個(gè)結(jié)果會(huì)很快趨于收斂。

其實(shí)這過(guò)程就是一個(gè)馬爾科夫隨機(jī)過(guò)程，隨機(jī)初始化起始值，然后隨機(jī)游走就相當(dāng)

于不停地用概率轉(zhuǎn)移矩陣相乘，最后就可以達(dá)到馬爾科夫穩(wěn)態(tài)。

把隨機(jī)游走事件歸為二類(lèi)：進(jìn)入某個(gè)社團(tuán)，離開(kāi)某個(gè)社團(tuán)，再社團(tuán)內(nèi)部游走.

定義清楚各類(lèi)事件的發(fā)生概率，依據(jù)信息燧公式，就可以得到此時(shí)編碼所需的平

均比特了,其本質(zhì)就是從信息論的角度出發(fā)。

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

L(M)將圖劃分成m個(gè)社區(qū)，編碼隨機(jī)游走路徑時(shí)的平均比特；

qc=EZiqs產(chǎn)生進(jìn)入社區(qū)這種事件的總概率；

H(Q)=-ZZ】(qs/qc)iog?c/qc)進(jìn)入社區(qū)事件發(fā)生的信息嫡；

Pi。=ZaQpa+qcrandomworker在社區(qū)i內(nèi)部的概率，這里包括了在社區(qū)內(nèi)跳轉(zhuǎn)和離

開(kāi)該社區(qū)兩類(lèi)事件；

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

-Za€/(Pa/P<U)log(Pa/PfO)randomworker下一步事件發(fā)生在社區(qū)i內(nèi)部的信息嫡；

Infomap算法的迭代過(guò)程

1,初始化，對(duì)每個(gè)節(jié)點(diǎn)都視作獨(dú)立的社區(qū)；

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

3,對(duì)圖里的節(jié)點(diǎn)隨機(jī)采樣出一個(gè)序列，按順序依次嘗試將每個(gè)節(jié)點(diǎn)賦給鄰居節(jié)

點(diǎn)所在的社區(qū)，取平均比特下降最大時(shí)的社區(qū)賦給該節(jié)點(diǎn)，如果沒(méi)有下降，

該節(jié)點(diǎn)的社區(qū)不變。

參考鏈接

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.使用隨機(jī)游走(Randomwalk)的方式在圖中進(jìn)行節(jié)點(diǎn)采樣獲得節(jié)點(diǎn)共關(guān)系，

2,使用skip-gram,根據(jù)步驟1中生成的節(jié)點(diǎn)序列學(xué)習(xí)每個(gè)節(jié)點(diǎn)的向量表示。

skip-gram就是根據(jù)給定輸入的節(jié)點(diǎn)，預(yù)測(cè)上下文節(jié)點(diǎn)。

Deepwalk有多不足，比如泛化能力，有新節(jié)點(diǎn)加入時(shí)，它必須重新訓(xùn)練模型以表示

該節(jié)點(diǎn)。

其中一個(gè)就是采樣，從其鄰居中隨機(jī)采樣節(jié)點(diǎn)作為下一個(gè)訪問(wèn)節(jié)點(diǎn)，是一種可重復(fù)

訪問(wèn)已訪問(wèn)節(jié)點(diǎn)的深度優(yōu)先遍歷算法。

node2vec是一種綜合考慮DFS鄰域和BFS鄰域的graphembedding方法

node2vec

優(yōu)化FI標(biāo)：

loPr

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

條件獨(dú)立假設(shè)：

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

特征空間的對(duì)稱性：

尸丁(電|加))=/沖皿少叫、、

優(yōu)化目標(biāo)：

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

Z

u=Euevexp(/(u)?/?))計(jì)算

量非常大，所以論文采用負(fù)采樣(negativesample)進(jìn)行近似計(jì)算。

這個(gè)node2vec優(yōu)化目標(biāo)函數(shù)，因?yàn)樗竺ΧΦ膚ord2vec是一樣。

我們最初是用一個(gè)Python寫(xiě)的包，跑一遍算法需要一盾。后來(lái)想，既然優(yōu)化目標(biāo)

是一樣的，那能不能用word2vec包，因?yàn)閣ord2vec用c寫(xiě)的，而旦還采用了

HierarchicalSoftmax,negativesampling加速。

然后在網(wǎng)上找到了一個(gè)套用word2vec實(shí)現(xiàn)的nodeZvec包，速度快很多。

隨機(jī)游走的方式

復(fù)雜網(wǎng)絡(luò)處理的任務(wù)其實(shí)離不開(kāi)兩種特性，前面也提到過(guò)：一種是同質(zhì)性，就是之

前所說(shuō)的社區(qū)。一種就是結(jié)構(gòu)相似性，值得注意的是，結(jié)構(gòu)相似的兩個(gè)點(diǎn)未必相連,

可以是相距很遠(yuǎn)的兩個(gè)節(jié)點(diǎn)。

能不能改進(jìn)DeepWalk中隨機(jī)游走的方式，使它綜合DFS和BFS的特性呢？所以

本文引入了兩個(gè)參數(shù)用來(lái)控制隨機(jī)游走產(chǎn)生的方式。

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

[0otherwise

(jifdtx=O

(%，/)=(1ifdtx=1

if4,=2

z是分子的歸一化常數(shù)

如果已經(jīng)采樣了(t,v),也就是說(shuō)現(xiàn)在停留在節(jié)點(diǎn)v上，那么下一個(gè)要采樣的節(jié)點(diǎn)

x是哪個(gè)？作者定義了一個(gè)概率分布，也就是一個(gè)節(jié)點(diǎn)到它的不同鄰居的轉(zhuǎn)移概率:

直觀的解釋一下這個(gè)分布：

1

?如果t與X相等，那么采樣X(jué)的概率為P；

?如果t與X相連，那么采樣X(jué)的概率1：

1

?如果t與x不相連，那么采樣x概率為q

參數(shù)p、q的意義分別如下：

返回概率P：

DataFunTalk成就百萬(wàn)數(shù)據(jù)科學(xué)家！

?如果p>max(q/l),那么采樣會(huì)盡量不往回走，對(duì)應(yīng)上圖的情況，就是卜一

個(gè)節(jié)點(diǎn)不太可能是上一個(gè)訪問(wèn)的節(jié)點(diǎn)to

?如果p<min(q,l),那么采樣會(huì)更傾向于返回上一個(gè)節(jié)點(diǎn)，這樣就會(huì)一直在

起始點(diǎn)周?chē)承┕?jié)點(diǎn)來(lái)回轉(zhuǎn)來(lái)轉(zhuǎn)去。

出入?yún)?shù)q：

?如果q>l,那么游走會(huì)傾向于在起始點(diǎn)周?chē)墓?jié)點(diǎn)之間跑，可以反映出一

個(gè)節(jié)點(diǎn)的BFS特性。

?如果q<l,那么游走會(huì)傾向于往遠(yuǎn)處跑，反映出DF$特性。

?當(dāng)p=l,q=l時(shí)，游走方式就等同于DeepWalk中的隨機(jī)游走。

簡(jiǎn)而言之：

參數(shù)p控制重復(fù)訪問(wèn)剛剛訪問(wèn)過(guò)的頂點(diǎn)的概率，

參數(shù)q控制著游走是向外還是向內(nèi)，若q>l,隨機(jī)游走傾向于訪問(wèn)和t接近的頂

點(diǎn)(偏向BFS)o若q<l?傾向于訪問(wèn)遠(yuǎn)離t的頂點(diǎn)(偏向DFS)o

缺點(diǎn)

1慢

2,先embedding再聚類(lèi)，感覺(jué)這兩個(gè)過(guò)程很割裂??！融合一下

comE

Graphembedding得到向最后，可以做很多事情，在我們這個(gè)主題可以簡(jiǎn)單的通過(guò)

聚類(lèi)來(lái)講節(jié)點(diǎn)分組。

但是這個(gè)過(guò)程比較割裂，先優(yōu)化node2vec,然后再優(yōu)化聚類(lèi)。能不能整體上一次

性優(yōu)化完呢。

comE這個(gè)算法優(yōu)化目標(biāo)中加入了社區(qū)的檢測(cè)和嵌入°通過(guò)一個(gè)混合高斯模型將節(jié)

點(diǎn)劃分開(kāi)。

Aj/：

6=~aEr,eVLvjCCi

皿乩-

一階LOSS二階LOSS社區(qū)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>.社區(qū)檢測(cè)和社區(qū)嵌入。

這篇論文比較創(chuàng)新的一點(diǎn)，就是將社區(qū)嵌入定義為低維空間中的多元高斯分布。即對(duì)于社區(qū)k來(lái)說(shuō)（

）,它在d維空間下的社區(qū)嵌入是一個(gè)多元高斯分布M（物fc,EQ,其中

矽AW〃表示的是社區(qū)內(nèi)節(jié)點(diǎn)的平均向H（即中心點(diǎn)），&€N表示的是協(xié)方差矩陣。

整篇文章最大的難點(diǎn)在于，如何用統(tǒng)一的目標(biāo)函數(shù)來(lái)使得社區(qū)嵌入、社區(qū)檢測(cè)和節(jié)點(diǎn)嵌入三者問(wèn)題

得到最優(yōu)化的結(jié)果。由于社區(qū)嵌入是由多元高斯分布來(lái)表達(dá)的，因此就可以通過(guò)高斯混合模型來(lái)完

成。

假設(shè)每一個(gè)節(jié)點(diǎn)的嵌入向量仇可以由該節(jié)點(diǎn)所在社區(qū)的多元高斯分布產(chǎn)生，這樣一來(lái)，就可以得

到一個(gè)似然目標(biāo)函數(shù)：

\V\K

n￡p（蒼=向p（奶忸=A；M吸,⑴

?=1k=l

其中，p（Zi=k）表示的是節(jié)點(diǎn)明屬于社區(qū)k的概率。方便表示，可以將這個(gè)概率表達(dá)為7T,Jt：

K

7TikW砥A=I.在社區(qū)發(fā)現(xiàn)問(wèn)題中，這個(gè)概率是未知的。

*=1

而p（Vi\zi=A;八，@k,紈）=M（力地k,之）表示的是多元高斯分布。在社區(qū)嵌入問(wèn)題中，

如,￡k是未知的。

綜上，將公式1對(duì)上述三個(gè)未知變量求導(dǎo)，就可以同時(shí)實(shí)現(xiàn)社區(qū)檢測(cè)和嵌入。

優(yōu)化目標(biāo)中前面兩項(xiàng)跟LINE定義的相似度相似:

1st

對(duì)于每一條無(wú)向邊G,j）,定義頂點(diǎn)口和町之間的聯(lián)合旗率為：

Pi（%,與）=%占沽@電，色為頂，京叨的低維向■表示?何以看作一個(gè)內(nèi)積模型，計(jì)算兩個(gè)item之間的匹配程度）

同時(shí)定義經(jīng)蛉分布肉=帶,W=￡g）cE5j

優(yōu)化目標(biāo)為最小化：Oi=d（d

</《，?）是兩個(gè)分布的距離，常用的衡■再個(gè)概率分布差異的指標(biāo)為KL散度，使用KL8I度并忽略常數(shù)項(xiàng)后有

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

1?lorder怕似度只能用于無(wú)向國(guó)當(dāng)中.

2nd

這里對(duì)于每個(gè)頂點(diǎn)維護(hù)兩個(gè)embedding向量，一個(gè)是該頂點(diǎn)本身的表示向■,一個(gè)是該點(diǎn)作為其他頂點(diǎn)的上下文頂點(diǎn)時(shí)的

表示向

對(duì)于有向邊G，j）,定義給定點(diǎn)助條件下，產(chǎn)生上下文（鄰居）頂點(diǎn)盯的概率為

r（叼|5）=耳喘抬，其中VI為上下文頂點(diǎn)的個(gè)數(shù).

優(yōu)化目標(biāo)為

。2