導(dǎo)讀
“億展宏圖”是eBay 支付風(fēng)控團(tuán)隊(duì)推出的系列文章，分享了eBay風(fēng)控團(tuán)隊(duì)工作在圖算法方面的一些理解和研究。在上期的里，我們介紹了訓(xùn)練圖神經(jīng)網(wǎng)絡(luò)的三種圖采樣范式和DeGNN算法，以此來更高性能地訓(xùn)練圖神經(jīng)網(wǎng)絡(luò)。本期億展宏圖，我們將介紹在圖算法中解決海量數(shù)據(jù)的方法。
引 言
在大數(shù)據(jù)場景中，海量的數(shù)據(jù)往往意味著超大的圖，這會(huì)影響到我們對(duì)問題的處理速度，各類算法的應(yīng)用也會(huì)受到限制。如下面這張?zhí)菪温┒穲D（為了數(shù)據(jù)安全性考慮，我們圖中展示的是假數(shù)據(jù)，不過大致和我們真實(shí)數(shù)據(jù)的數(shù)量級(jí)比較近似），可見每一次進(jìn)行縮小處理之后都會(huì)發(fā)生很大量級(jí)的變化。
那每一次的縮小處理是采用什么方法，適用的場景又是什么樣的呢？下面就帶大家從構(gòu)圖開始，一步一步來看如何處理圖太大的問題，每一步處理過程中又有哪些取舍問題需要考慮。
一
全量交易圖
要建立全量交易圖，主要有兩個(gè)步驟：1是構(gòu)圖；2是去掉超級(jí)節(jié)點(diǎn)。
1、構(gòu)圖
構(gòu)建圖就是在構(gòu)建關(guān)系網(wǎng)絡(luò)，所以這張網(wǎng)的構(gòu)建一定要從解決問題的實(shí)際場景出發(fā)。在風(fēng)控場景中，賬號(hào)之間的重疊信息和真實(shí)的交易行為是構(gòu)圖的重要信息來源。基于這樣的認(rèn)知，我們往往會(huì)選擇注冊(cè)賬號(hào)的郵件、電話、支付信息等作為賬號(hào)之間的邊。
然而，有時(shí)可選擇的關(guān)聯(lián)信息會(huì)有很多，那哪些信息對(duì)挖掘風(fēng)險(xiǎn)是更有效的呢？
這時(shí)，我們引入同質(zhì)偏好的概念。同質(zhì)偏好是指個(gè)體更傾向于與他們相似的個(gè)體建立連結(jié)，即“物以類聚”。我們標(biāo)注已知的風(fēng)險(xiǎn)點(diǎn)為“”，未知風(fēng)險(xiǎn)點(diǎn)為“0”，且n0為label的節(jié)點(diǎn)數(shù)量，n1為非label的節(jié)點(diǎn)數(shù)量。然后，我們定義三類二元組，分別為(1, 1)、(1, -0)和(0, -0)。它們分別表示(, -)、(, -)和(, -)形式的兩點(diǎn)一邊。再計(jì)算每一類二元組的節(jié)點(diǎn)數(shù)量總和，分別為m11、m10和m00，得到：
如果點(diǎn)和點(diǎn)之間的邊是隨機(jī)連接的，與他們本身的風(fēng)險(xiǎn)點(diǎn)(label)并無關(guān)系，那么m11和m10的期望值（如下公式計(jì)算得到）應(yīng)該是相等的。
其中p = 2M/(N(N – 1))，代表兩個(gè)節(jié)點(diǎn)相連的概率。如果p=1, 那么圖中所有的點(diǎn)都互相連接。現(xiàn)在我們定義(D) 和 (H)：
如果一個(gè)網(wǎng)絡(luò)中D>1, 表示這個(gè)網(wǎng)絡(luò)是的，這表示相比隨機(jī)連接，風(fēng)險(xiǎn)節(jié)點(diǎn)彼此連接得更緊密。如果H利用這兩個(gè)數(shù)值，可以幫助我們判斷，一個(gè)關(guān)系（邊）是否能夠很好地展現(xiàn)出網(wǎng)絡(luò)的同質(zhì)性，進(jìn)而有利于風(fēng)險(xiǎn)社團(tuán)的挖掘。在樣本數(shù)據(jù)中，我們使用了如上圖所示的邊關(guān)系，其中支付賬號(hào)或卡片( token)和注冊(cè)地址( )展示了非常高的值，其余類型的也均大于1，可見這些標(biāo)簽都是有意義的關(guān)聯(lián)關(guān)系。在交易數(shù)據(jù)中，確定好點(diǎn)和邊后，我們就可以搭建相關(guān)場景的圖（如下圖所示）。
(點(diǎn)擊可查看大圖)
2、去掉超級(jí)節(jié)點(diǎn)
因?yàn)橐恍┕残畔⑹枪蚕淼模热缈Х葟d/網(wǎng)吧IP、企業(yè)的對(duì)公賬戶、樞紐機(jī)場等，會(huì)使得這些節(jié)點(diǎn)擁有超過平均值幾倍甚至幾十倍的邊，如下圖中間部分的超大節(jié)點(diǎn)，我們稱之為超級(jí)節(jié)點(diǎn)。
網(wǎng)絡(luò)圖[1]
在風(fēng)控場景中，這些重度連接的節(jié)點(diǎn)趨向于快速累積更多鏈路，這使得具有少量邊的節(jié)點(diǎn)被忽視掉；而超級(jí)節(jié)點(diǎn)也會(huì)使得圖迅速變大且難以分割。所以，在構(gòu)圖之后，移除超級(jí)節(jié)點(diǎn)是第一步有效縮減圖的方式。比較直接的方法是：根據(jù)所有節(jié)點(diǎn)度()的分布，設(shè)定一個(gè)閾值，當(dāng)一個(gè)節(jié)點(diǎn)的度高于這個(gè)閾值的時(shí)候，就去掉這個(gè)節(jié)點(diǎn)。
二
風(fēng)險(xiǎn)交易圖
在全量交易圖中，包含著海量的數(shù)據(jù)，其中包含一些無關(guān)緊要的信息。這就需要對(duì)圖進(jìn)行“瘦身”，從而得到我們關(guān)注的信息——風(fēng)險(xiǎn)交易圖。我們一般采取K跳算法對(duì)圖進(jìn)行瘦身。
K跳算法(K-hop)在業(yè)務(wù)層面非常便于理解且操作，可以稱得上是最簡便的縮小圖網(wǎng)絡(luò)的方式，因此被廣泛使用。K跳算法指的是從某個(gè)頂點(diǎn)出發(fā)，尋找到所有與其最短路徑為K跳（或K步）的頂點(diǎn)的集合。它可以根據(jù)K值大小來調(diào)整得到縮小圖后的大小，通常進(jìn)行K跳算法之后，一張超級(jí)大圖會(huì)有一個(gè)量級(jí)的減小，但每個(gè)k值對(duì)應(yīng)的結(jié)果是固定的。在風(fēng)控場景中，將已知的風(fēng)險(xiǎn)節(jié)點(diǎn)標(biāo)注為標(biāo)簽，然后以這些風(fēng)險(xiǎn)節(jié)點(diǎn)出發(fā)，順著構(gòu)建好的邊往外延伸，保留k層與之關(guān)聯(lián)的所有節(jié)點(diǎn)，最后用保留的節(jié)點(diǎn)再構(gòu)建連通圖。子圖的擴(kuò)張順序正如下圖所示。
（點(diǎn)擊可查看大圖）
三
風(fēng)險(xiǎn)社群在進(jìn)一步縮小圖至風(fēng)險(xiǎn)社群過程中，我們常用連通圖、標(biāo)簽傳播算法、冪迭代聚類這三種方法。
1、連通圖
( )
連通圖[2]
如果從頂點(diǎn)A到頂點(diǎn)B有路徑相連，則稱A和B是連通的。如果一個(gè)圖中的任意兩點(diǎn)都是連通，那么圖被稱作連通圖。以連通圖的定義，K跳后的圖可以被切割成一個(gè)個(gè)子圖這些子圖就可作為天然的社區(qū)，從而進(jìn)行分割。圖的連通性是圖的基本性質(zhì)。以連通圖作為切割小圖的方式，是非常直觀和自然的。由連通圖得到的分割結(jié)果是唯一的，但往往還是會(huì)存在超大圖。
2、標(biāo)簽傳播算法
(label ,LPA)
LPA的社區(qū)劃分方式可以改善上述不夠靈活的問題。LPA是基于標(biāo)簽傳播的局部社區(qū)劃分算法。如下圖所示，首先給每個(gè)點(diǎn)一個(gè)標(biāo)簽，在一輪迭代中，再將每一個(gè)節(jié)點(diǎn)選擇與之相連的節(jié)點(diǎn)中占比最高的標(biāo)簽作為自己的標(biāo)簽，若占比相等就隨機(jī)選擇。如此迭代到最終穩(wěn)定或者規(guī)定的輪數(shù)之后，只保留有風(fēng)險(xiǎn)節(jié)點(diǎn)存在的社區(qū)，這樣就可進(jìn)一步縮小圖了。
在實(shí)際應(yīng)用中， LPA的迭代十分迅速有效率。但因?yàn)閭鞑サ碾S機(jī)性，劃分結(jié)果并不穩(wěn)定（甚至?xí)霈F(xiàn)標(biāo)簽震蕩、兩個(gè)點(diǎn)不能出現(xiàn)在同一個(gè)社區(qū)的情況）。如上圖所示，四個(gè)節(jié)點(diǎn)為一個(gè)小社區(qū)在兩次經(jīng)過標(biāo)簽傳播后，得到了完全不同的結(jié)果。LPA的另一個(gè)問題是在傳播結(jié)束后，會(huì)看到有很多孤立的點(diǎn)不在任何社區(qū)內(nèi)，在我們的例子中這樣的節(jié)點(diǎn)占比超過了20%。
3、冪迭代聚類
(power ,PIC)
如果我們想盡量不出現(xiàn)孤立點(diǎn)，讓每個(gè)節(jié)點(diǎn)都有自己歸屬的社群，那么可以使用PIC來做社區(qū)劃分。PIC適合對(duì)大型稀疏矩陣，即節(jié)點(diǎn)之間的關(guān)聯(lián)關(guān)系矩陣，進(jìn)行運(yùn)算。簡單來說，PIC 由兩部分組成：1）對(duì)稀疏的鄰接矩陣做維度變換。就如同下圖所示的從三維地球儀表面到二維地圖平面的映射， 這一步維度的變化可以讓數(shù)據(jù)對(duì)聚類算法的表征能力有所提高。
維度變換[3]
2）針對(duì)變換后的數(shù)據(jù)做聚類。維度變換后，需對(duì)數(shù)據(jù)進(jìn)行如下迭代步驟：
① 輸入按行歸一化的關(guān)聯(lián)關(guān)系矩陣W圖的連通性判斷算法，和期望聚類數(shù)k；
② 隨機(jī)選取一個(gè)非零初始向量；
③ 計(jì)算
并使得
④ 增加t，重復(fù)迭代步驟③，直到
為止；
⑤ 使用k-means對(duì)向量中的點(diǎn)進(jìn)行聚類；
⑥ 輸出社團(tuán)C?， C?，...， C。
PIC的具體原理有更復(fù)雜的論證，具體可以參考這篇論文：power [4]。
PIC的特點(diǎn)是可以用提前停止(early )來快速有效地找到特征向量(eigen )，得到一個(gè)低維空間的映射，這個(gè)映射后的數(shù)據(jù)恰好是適合聚類的特征輸入。這樣，PIC會(huì)更均勻地切分社區(qū)，且不會(huì)有孤立點(diǎn)存在，很好地解決了LPA丟失太多孤立點(diǎn)的問題。如下圖所示，我們以一個(gè)中心點(diǎn)加兩圈同心圓的圖為例，PIC在經(jīng)過多輪迭代后，能完美地切分出三個(gè)社區(qū)。
Power [5]
（點(diǎn)擊查看大圖）
連通圖、LPA、PIC這三種算法都可以縮小圖，得到風(fēng)險(xiǎn)社區(qū)。但它們都有各自的優(yōu)缺點(diǎn)，如下表所示：
那么在我們的實(shí)際例子中，基于這三種算法得到的社群到底是什么樣的呢？我們通過下面這些統(tǒng)計(jì)值來看一下：
總而言之，連通圖的社群關(guān)系比較便于理解，有連邊就屬于一個(gè)社群，不存在不確定性也不需要主觀優(yōu)化目標(biāo)設(shè)定。但它的缺點(diǎn)是：容易出現(xiàn)超大集群，通常容易被類似公共IP或者轉(zhuǎn)運(yùn)倉庫等信息噪聲較大的節(jié)點(diǎn)關(guān)聯(lián)到一起。LPA的標(biāo)簽傳播邏輯也并不復(fù)雜，且快速有效，但缺點(diǎn)是表現(xiàn)不穩(wěn)定，容易出現(xiàn)大量孤立節(jié)點(diǎn)。如果下游應(yīng)用關(guān)心的是顆粒度較細(xì)的關(guān)聯(lián)關(guān)系，且不關(guān)心原本聯(lián)結(jié)就松散的社群關(guān)系，那么LPA是個(gè)好的選擇。而聯(lián)通關(guān)系緊密的社群會(huì)較高可能地被暴露出來，大部分社群數(shù)量都不超過10個(gè)，當(dāng)然預(yù)期的規(guī)模大小可以通過迭代次數(shù)來控制。如果下游應(yīng)用還會(huì)有后續(xù)分解步驟或者聚類算法的話，PIC是個(gè)合適的選擇。它可以先高效地分離出大社群，這里社群個(gè)數(shù)的選取不涉及業(yè)務(wù)含義，一般會(huì)結(jié)合下游算法的處理能力和并行規(guī)模而決定。
四
高危社群
所謂“亂花漸欲迷人眼”，在包含有大量交易的交易圖網(wǎng)絡(luò)中，簡單的縮小和切割后得到的縮小圖中，還是無法讓人一眼聚集到圖的某一個(gè)可疑網(wǎng)絡(luò)，我們就需要對(duì)網(wǎng)絡(luò)進(jìn)行做可視化。那在可視化的時(shí)候，圖太大的問題要怎么解決呢？區(qū)域性社區(qū)檢測(local ,LCD)就能很好地幫我們解決這一問題做到這一點(diǎn)。對(duì)于LCD，首先我們來了解一下譜聚類( )，因?yàn)楹竺嬉榻B的兩個(gè)算法都是在此基礎(chǔ)上做了一些變動(dòng)。傳統(tǒng)的譜聚類是基于特征向量來進(jìn)行社區(qū)劃分的算法，具體步驟如下：1）構(gòu)造圖對(duì)應(yīng)的相似矩陣S∈n×n，并確定社區(qū)個(gè)數(shù)k；
2）根據(jù)S構(gòu)建鄰接矩陣W和度矩陣D，并算出拉普拉斯矩陣L；
3）計(jì)算L的前k個(gè)特征向量u1, …, uk，把u1, ..., uk組成矩陣U，U∈n×k；
4）U中的一行作為一個(gè)樣本，對(duì)n個(gè)樣本做K-means聚類，由此輸出k個(gè)群落。
由于傳統(tǒng)的譜聚類無法設(shè)定社區(qū)的最小規(guī)模，也無法避免最終輸出時(shí)社區(qū)之間可能存在的大小失衡，我們采用以下這些優(yōu)化過的算法：
1、ACL
( with ACL )[6]
網(wǎng)頁排名()算法中，我們知道最終轉(zhuǎn)移概率矩陣?PRV=PRV，所以PRV( )是特征向量，其特征值為1。
而ACL算法提出了一種近似算法得到特征向量，從而能大大地提高運(yùn)行速度。ACL可以在指定點(diǎn)附近找到一個(gè)相對(duì)小的社區(qū)，且計(jì)算時(shí)間與這個(gè)小社區(qū)的規(guī)模成正比（對(duì)比整個(gè)網(wǎng)絡(luò)圖，可以節(jié)省計(jì)算時(shí)間）。與傳統(tǒng)譜聚類不同的是，我們需要設(shè)定一個(gè)起始點(diǎn)和一些其他超參數(shù)來計(jì)算PR()向量，并以一些條件來搜索社區(qū)。在我們的樣本數(shù)據(jù)中，選取一個(gè)較大的子圖，如下圖所示，其中綠色表示訂單，黃色表示與其有連接關(guān)系的實(shí)體（地址、電話號(hào)碼、郵件等等）。在圖中隨機(jī)選擇一個(gè)起始點(diǎn)，得到以通過acl算法篩選出的點(diǎn)為中心的局部社區(qū)，即在一個(gè)相對(duì)較大的聯(lián)通圖上得到更貼近目標(biāo)節(jié)點(diǎn)的鄰居節(jié)點(diǎn)。這些更有關(guān)系的鄰居節(jié)點(diǎn)，用放大的節(jié)點(diǎn)表示。此外，在ACL的基礎(chǔ)上使用l1- (PR)這一優(yōu)化目標(biāo)，并用FISTA來得到最優(yōu)解[7]。用上述的改良算法，應(yīng)用在相同的樣本和起始點(diǎn)，得到的社區(qū)與ACL完全一致。
(點(diǎn)擊可查看大圖)
2、MQI
(Max Flow Cut )[8]
在ACL探測完一個(gè)社區(qū)后，有時(shí)候這個(gè)社區(qū)還是相對(duì)較大或者連著旁枝末節(jié)。這時(shí)，我們可以使用MQI在已經(jīng)尋找出的社區(qū)里尋找一個(gè)更優(yōu)社區(qū)。
MQI的做法是在給定的規(guī)模不大的參考節(jié)點(diǎn)里找到一個(gè)擁有最優(yōu)的連通率()的社區(qū)作為返回值。我們就在上圖ACL切分出來的社區(qū)基礎(chǔ)上，用MQI優(yōu)化，呈現(xiàn)出來的社區(qū)如下圖所示：
(點(diǎn)擊可查看大圖)
在得到這個(gè)社區(qū)之后我們就可以放大縮小坐標(biāo)系，來查看聚焦的小社區(qū)，也可以做進(jìn)一步的檢驗(yàn)或分析。
總結(jié)
現(xiàn)在是大數(shù)據(jù)的時(shí)代，這就導(dǎo)致構(gòu)建完的圖網(wǎng)絡(luò)往往是一張超級(jí)大圖。這既提供了更多信息，同時(shí)也帶來了很大的挑戰(zhàn)。本期億展宏圖，我們針對(duì)圖太大的問題圖的連通性判斷算法，提到了去除超級(jí)節(jié)點(diǎn)，并使用K跳算法縮小網(wǎng)絡(luò)，然后把仍然過大的圖通過LPA或者PIC進(jìn)行分割,最后可以用LCD聚焦到高風(fēng)險(xiǎn)社群。在這篇文章中使用的方法各有優(yōu)缺點(diǎn)，它們既可以被單獨(dú)使用，也可以結(jié)合在一起。在實(shí)際應(yīng)用中，我們可以結(jié)合場景和期望達(dá)到的效果，靈活地使用這些技巧來解決圖過大的問題。
下一期“億展宏圖”，我們將介紹異構(gòu)圖的深度學(xué)習(xí)模型和異構(gòu)圖算法模型，敬請(qǐng)期待！
參考資料:
[1] -2020/----and--
[2]
[3] /earth-/-data-r/intro-to- --/
[4]~/ /nips-2009-pic.pdf
[5]Power /~frank//-pic-final.pdf
[6]~fan/wp/.pdf
[7]
[8] 978-3-540-25960-2_25
往期推薦
億展宏圖 第一篇|兩張圖入門圖算法
億展宏圖 第二篇|圖算法在eBay支付風(fēng)控領(lǐng)域的應(yīng)用
億展宏圖 第三篇|如何高性能訓(xùn)練圖神經(jīng)網(wǎng)絡(luò)