作者：小伍哥

來源：小伍哥聊風控

關于圖的風控應用，之前的很多文章都是基于算法的，今天分享一篇基于圖進行人工特征提取的欺詐檢測文章，這樣大部分人都能應用上了，其中的特征提取方法和思想，值得我們探索和借鑒，可以作為無監督的的指標進行監控，也可以作為算法特征的輸入。本文內容來自論文《SocialWatch: Detection of Online Service Abuse via Large-Scale Social Graphs》，地址：https://users.soe.ucsc.edu/~abadi/Papers/socialwatch.pdf

一、背景介紹

本文主要進行的是兩類風險賬戶的檢測：黑產自己注冊的賬號+黑產盜號的賬號。在一些網絡在線服務中，黑產會使用這些控制的惡意賬號進行一些惡意行為，這些賬號可能是黑產批量注冊的，也可能是盜號，因此需要有明顯的特征去區分惡意賬號和正常賬號。論文為了識別郵箱服務中的惡意賬號，提出來兩類特征：一類是基于圖的屬性統計指標，另一類是基于社交關系的特征(social affinity feature)。

我們可以從這篇文章中學到幾個點：第一個是如何構圖（文章中用的郵件，我們可以用電話、地址、點擊、設備、IP等），第二個是圖統計特征提，第三個是圖社交關系特征提取。

二、設計構建Graph

論文中根據郵件關系構建了兩種不同類型的圖，頂點都是用戶，但是邊的構造有所不同，示意圖如下。

1）發送郵件的有向圖Gd：如果用戶v1給v2發郵件，那么生成v1指向v2的邊，權重是發送的數量

2）用戶關系的無向圖Gu：如果用戶v1給v2發郵件>=2，同時v2給v1發郵件>=2，那么v1和v2之間會形成一條邊。

下圖為示意圖，第一個圖覆蓋比較廣，第二個條件的條件比較嚴格，通過要求邊緣的權重至少同時為2，可以消除因偶爾或意外電子郵件交換（例如，意外回復惡意帳戶）而導致的弱連接，圖會小很多，但是整個圖的靠靠性要強很多，可能很多人不知道結構化的數據怎么構建有向圖和無向圖，后面我會出個文章教大家怎么構圖。

條件1圖：節點數為6.82億個，邊數57.45

條件2圖：節點個數2.55億個，邊數4.369

三、檢測黑產自己注冊的賬號

對于黑產自己的賬號，有兩個最顯著且易于計算的圖屬性，節點度 和 PageRank。度是一種能捕捉賬戶攻擊性的圖屬性，PageRank 是一種從全局層面計算整個圖上每個節點的權重的方法。接下來，我們將討論如何在社交環境中修改這兩個屬性以進行檢測。

1、賬號回復率

賬號回復率 = 回復該賬號郵件的賬號數/接收該賬號郵件的賬號數

惡意賬號出度大（發郵件給其他的賬號數量多），但回復率會比較低，通過簡單的統計，可以找到一些明顯的惡意賬號。

2、PageRank

PageRank算法是一種基于圖的傳播算法，一種簡單的想法是在有向圖Gd上使用PageRank，傳播善意分數（goodness score），然而盡管惡意賬號的回復率比較低，但是由于發送的郵件數巨大，偶然性的回復會使得其善意分數偏高，而一些不活躍的正常賬號善意分數會比較低。

為了解決上述問題，論文提出來了兩處改進，一是修改邊的權重（考慮發送和回復比例），二是把原來網絡圖連接關系進行反轉（入鏈變成出鏈，出鏈變成入鏈），傳播惡意分數（badness score）。

下面舉一個簡單的例子：

假設一個正常賬號A發送給spammer的郵件數是1，而給其friend的郵件數是10。那么在傳播goodness score時，根據A發送郵件數作為傳播權重，傳給spammer的善意得分比較小。

將出入關系進行反轉，若spammer給A發送的郵件數是100，而friend給A發送的郵件數是10，根據公式：

w(A->spammer) = (101/2) /( 101/2+11/11+11/11) ) = 96.4%

w(A->friend) = (11/11) /( 101/2+11/11+11/11) ) = 1.8%

根據上述權重由A傳播惡意分數，傳給spammer的善意得分比較大。定義指標badness_score/goodness_score，若指標大于某閾值則認為賬號是惡意的。

上面的計算不是很理解的同學，可以看看這個文章，網頁排序算法PageRank：http://sparkandshine.net/webpages-ranking-algorithm-pagerank/

三、被盜號賬戶檢測-社會親和力特征

被盜的賬號相比于黑產自己注冊的賬號來講行為的噪音更大（被盜號賬戶，過去的行為都很正常，并沒有大規模的異常郵件行為），通過degree或者pagerank很難識別到，為了解決這個問題，作者從社交關系的角度出發，定義了兩個 social affinity feature（社會親和力特征）：Recipient connectivity（收件人連通性 ）和 Social distance（社交距離），下面我們分別看看這兩個特征的具體含義。

1、 Recipient connectivity（收件人連通性 ）

一個正常賬號 和 與其進行郵件通訊的賬號往往處于同一個社區，對于一個賬號v，從Gu中抽取頂點為接收到v郵件的賬號子圖Gu(v)，通過連通圖聚類得到若干連通分量c1，c2，...，ck，這些連通圖分量的成員數至少為2，于是：對于節點v而言，刪除節點v得到以節點v為中心的一階的子圖，然后使用connected components 算法獲取k個聯通分量，顯然最小聯通分量包含兩個節點。

最后使用公式：Recipient connectivity（v） = 連通分量的賬號數之和/接收到v郵件的賬號數

我畫了個示意圖，如下所示，我們把定點V剔除后，剩下的圖，連通性各不相同，圖1就是比較異常的，只要定都發送，發送的各個點之間并沒有聯系，剔除后連同分量為0，而圖3，剔除后的三個賬戶，依然連通，所以連通分量為3。

這背后的直覺就是正常的賬戶和周圍人的聯系一般較為密切而極少與不認識的人存在聯系，因此其 recipient connectivity 往往較高，而對于一個被劫持的正常賬戶，由于被劫持賬戶也是用來發廣告之類的（比如微博號、qq號，微信號被盜，會給關注的人發各種亂七八糟的私信），因此被劫持的賬戶一旦發生了這類行為，其recipient connectivity往往會發生變化，從而變得較低。

Recipient connectivity的一個問題是兩個用戶在郵件網絡中沒有聯系，不代表其在真實世界中也沒有聯系。

注意：無向圖G的極大連通子圖稱為G的連通分量( Connected Component)，任何連通圖的連通分量只有一個，即是其自身，非連通的無向圖有多個連通分量。求圖的連通分量的目的，是為了確定從圖中的一個頂點是否能到達圖中的另一個頂點，也就是說，圖中任意兩個頂點之間是否有路徑可達。這個問題從圖上可以直觀地看出答案，然而，一旦把圖存入計算機中，答案就不大清楚了。

2、Social distance（收件人社交距離）

對于一個賬號v，從子圖Gu中剔除賬號v和相關的邊，于是：Social distance（v）= 接收到v郵件的賬號之間的平均最短距離

However, the social-distance fea-ture l(v) requires computing shortest-path distances on the largegraph Gu for all user pairs in R(v)

這個特征怎么理解？其背后的直覺是復雜網絡中的“小世界”，正常賬戶往往在一個社交圈子里，大部分人彼此認識，因此對于正常用戶的通過郵件構建起來的社交圈子而言，其social distance比較短，而對于被劫持的正常賬戶而言，群體中的其他人彼此并不認識，其social distance比較長。

有了這些相關特征后，如果有已知的被盜賬號，那么通過各種算法就可以構建一個分類任務了，從而識別其他的被盜賬號，或者直接用規則，識別被盜賬號。

收獲就這兩個社交親和力特征，用來幫助處理盜號問題，沒標簽就做規則，有標簽就作為特征train 模型。在上述缺失觀測的情況下，由最短路徑距離定義的社會距離是完整圖上真實社會距離的上限近似值。

通過上面的圖，我們可以發現一個理論，六度分隔理論，哈佛大學心理學教授斯坦利·米爾格拉姆于1967年根據這個概念做過一次連鎖信實驗，嘗試證明平均只需要6步就可以聯系任何兩個互不相識的人。后世的人們將這個理論稱作是“六度空間理論”或“六度分隔理論”。我們的計算中，正常用戶的距離，均值恰好是6左右。

文章就寫到這里了，文章雖然簡單，但是里面的細節還是非常多的，大家可以結合自己的業務，尋找不同的關系圖，然后來研究里面提到的指標。