面向圖的異常檢測研究綜述*

李 忠,靳小龍,莊傳志,孫 智

1(網(wǎng)絡(luò)數(shù)據(jù)科學(xué)與技術(shù)重點(diǎn)實(shí)驗(yàn)室(中國科學(xué)院 計(jì)算技術(shù)研究所),北京 100190)

2(中國科學(xué)院大學(xué) 計(jì)算機(jī)與控制學(xué)院,北京 100049)

1 研究背景

在互聯(lián)網(wǎng)、物聯(lián)網(wǎng)以及通信技術(shù)不斷發(fā)展的大背景下,信息的交互、分析、協(xié)同變得越來越普遍.生活中的網(wǎng)絡(luò)更隨處可見,如電話通聯(lián)網(wǎng)絡(luò)、交通運(yùn)輸網(wǎng)絡(luò)、電力網(wǎng)絡(luò)等等.尤其隨著社交網(wǎng)絡(luò)的產(chǎn)生,人們有了更好的交流與協(xié)作平臺(tái),如微博、微信、QQ 等等.當(dāng)人們享受網(wǎng)絡(luò)帶來的便捷性的同時(shí),網(wǎng)絡(luò)中的異常與欺詐行為也影響了社交網(wǎng)絡(luò)的正常發(fā)展,如欺詐信息的傳播、電信與信用卡欺詐、網(wǎng)絡(luò)僵尸粉絲、購物網(wǎng)站惡意評(píng)價(jià)、網(wǎng)絡(luò)掃描與網(wǎng)絡(luò)入侵等.如何能夠盡早并準(zhǔn)確地檢測到這些異常與欺詐行為,避免造成更多的危害變得尤為重要.區(qū)別于傳統(tǒng)數(shù)據(jù)挖掘技術(shù)的面向圖的異常檢測技術(shù),因其普適性和高效性,也受到學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注.

1.1 面向圖的異常檢測的定義

Hawkins 定義異常檢測[1]就是發(fā)現(xiàn)那些和大部分對(duì)象不同的目標(biāo)對(duì)象,以至于這些對(duì)象的分布或形成機(jī)制看起來與其他數(shù)據(jù)是不同的.面向圖的異常檢測是將原始問題使用圖數(shù)據(jù)結(jié)構(gòu)進(jìn)行建模,并使用圖數(shù)據(jù)挖掘技術(shù)和圖論的相關(guān)理論知識(shí),從圖中找出分布、形成規(guī)律和大多數(shù)其他的實(shí)體不同的節(jié)點(diǎn)或者邊.

1.1.1 傳統(tǒng)的異常檢測方法

傳統(tǒng)的異常檢測是數(shù)據(jù)挖掘中的一個(gè)重要應(yīng)用,用來發(fā)現(xiàn)數(shù)據(jù)集中不同于其他數(shù)據(jù)的對(duì)象.離群點(diǎn)檢測是異常檢測的一種常用方法,傳統(tǒng)的離群點(diǎn)檢測的一般過程為:首先,根據(jù)已有的正常數(shù)據(jù)建立一個(gè)參考模型,對(duì)于新的觀測數(shù)據(jù),測試數(shù)據(jù)相似度是否在某個(gè)閾值之內(nèi),以此來判斷數(shù)據(jù)是否是異常數(shù)據(jù).傳統(tǒng)的異常檢測的方法也非常多,可以大致分為4 類——基于統(tǒng)計(jì)的方法、基于距離的方法、基于偏差的方法、基于密度的方法.

(1)基于統(tǒng)計(jì)的方法:假設(shè)數(shù)據(jù)分布符合一定的概率分布,如果數(shù)據(jù)和分布有差距,則認(rèn)為是異常數(shù)據(jù).但是現(xiàn)實(shí)數(shù)據(jù)有可能不符合任何一種理想的概率分布,或者符合的分布模式是未知的;

(2)基于距離的方法:原理是正常的數(shù)據(jù)應(yīng)該有足夠多的鄰居,異常數(shù)據(jù)則有很少的鄰居;

(3)基于偏差的方法:使用模型對(duì)數(shù)據(jù)進(jìn)行預(yù)測,若預(yù)測值與實(shí)際值偏差超過一定的閾值則為異常數(shù)據(jù);

(4)基于密度的方法:基于距離的異常方法的改進(jìn),利用網(wǎng)格作KNN 查詢,可以查找局部異常因子.

1.1.2 面向圖的異常檢測方法

使用圖數(shù)據(jù)表示網(wǎng)絡(luò)具有得天獨(dú)厚的優(yōu)勢.網(wǎng)絡(luò)存在于我們生活的方方面面,圖數(shù)據(jù)表示能力強(qiáng),可以表示實(shí)體與實(shí)體之間的復(fù)雜關(guān)系.使用圖模型表示網(wǎng)絡(luò)數(shù)據(jù),可使用圖論的相關(guān)技術(shù)挖掘數(shù)據(jù)中有價(jià)值的信息.常用的圖數(shù)據(jù)挖掘技術(shù)主要包括圖聚類、圖分類、圖切割等.圖異常檢測技術(shù)是圖數(shù)據(jù)挖掘技術(shù)的一種,如在社交網(wǎng)絡(luò)中,將每個(gè)人作為一個(gè)點(diǎn),人與人之間的互動(dòng)關(guān)系是邊,則在龐大的社交圈子中,不同人之間的互動(dòng)聯(lián)系就構(gòu)成了龐大的社交關(guān)系圖.在社交網(wǎng)絡(luò)中,使用圖異常檢測技術(shù)可以識(shí)別網(wǎng)絡(luò)中的異常賬號(hào)、僵尸粉絲、廣告推手等等.在計(jì)算機(jī)網(wǎng)絡(luò)訪問圖中,使用圖數(shù)據(jù)挖掘技術(shù)可以找出潛在的攻擊者或入侵者.面向圖異常檢測可定義為:給定一個(gè)無權(quán)或有權(quán)的、靜態(tài)的或動(dòng)態(tài)的圖數(shù)據(jù)模型,查找其中與大多數(shù)觀測對(duì)象不一樣的少量的邊、節(jié)點(diǎn)或子圖.

面向圖異常檢測不僅僅需要考慮對(duì)象與對(duì)象之間的相似度,還需要考慮對(duì)象與對(duì)象之間的關(guān)系信息.比如:通過交易網(wǎng)絡(luò)圖分析哪些交易是欺詐交易、通過通信網(wǎng)絡(luò)數(shù)據(jù)圖分析恐怖分子之間的聯(lián)系網(wǎng)絡(luò)、通過用戶-商品網(wǎng)絡(luò)數(shù)據(jù)分析水軍或惡意評(píng)價(jià)之間的關(guān)系、通過關(guān)注者-被關(guān)注者網(wǎng)絡(luò)分析網(wǎng)絡(luò)僵尸粉絲的攻擊方向等.

傳統(tǒng)的圖異常檢測技術(shù)是異常檢測技術(shù)和離群點(diǎn)檢測技術(shù)在圖數(shù)據(jù)挖掘中的應(yīng)用,主要包括基于信息論的方法、基于偏差的方法、基于距離的方法以及基于社區(qū)的方法.近年來,神經(jīng)網(wǎng)絡(luò)是人工智能領(lǐng)域興起的研究熱點(diǎn),隨著研究工作的不斷深入,神經(jīng)網(wǎng)絡(luò)在許多領(lǐng)域都取得了很大的進(jìn)展,尤其是在模式識(shí)別、智能機(jī)器人、預(yù)測估計(jì)、自然語言處理等領(lǐng)域已成功地解決了許多現(xiàn)代計(jì)算機(jī)難以解決的實(shí)際問題,并表現(xiàn)出了良好的智能特性.隨著神經(jīng)網(wǎng)絡(luò)的發(fā)展,近年來也有一些使用深度神經(jīng)網(wǎng)絡(luò)進(jìn)行圖異常檢測的方法[2],主要分成兩類.

(1)基于有監(jiān)督學(xué)習(xí)的方法,通過使用標(biāo)簽數(shù)據(jù)訓(xùn)練就可以得到非線性分類器,將異常檢測問題作為分類問題來處理;

(2)基于偏差的方法,通過使用編碼器-解碼器模型對(duì)數(shù)據(jù)進(jìn)行重建,重建的誤差超過閾值則認(rèn)為是異常數(shù)據(jù).該方法通常適用于時(shí)間序列圖.

本文在總結(jié)傳統(tǒng)圖異常檢測技術(shù)的基礎(chǔ)上,介紹了近年來采用神經(jīng)網(wǎng)絡(luò)以及張量分解等技術(shù)的圖異常檢測算法,最后對(duì)各類方法進(jìn)行分析對(duì)比,說明其優(yōu)缺點(diǎn).

1.2 面向圖的異常檢測的分類

本文按照輸入圖的類型分為靜態(tài)圖異常檢測與動(dòng)態(tài)圖異常檢測兩大類.給定一個(gè)問題,從是否將問題建模為動(dòng)態(tài)圖的角度出發(fā),便于形成對(duì)問題的清晰的解決思路.此外,面向靜態(tài)圖的異常檢測方法改進(jìn)之后也可以應(yīng)用于動(dòng)態(tài)圖的異常檢測.因此,本文從靜態(tài)圖的異常檢測到動(dòng)態(tài)圖的異常檢測,形成遞進(jìn)邏輯,也便于讀者理解相關(guān)模型與方法的優(yōu)缺點(diǎn).

? 面向靜態(tài)圖的異常檢測

根據(jù)靜態(tài)圖是否包含屬性,靜態(tài)圖異常檢測可以分為兩類——無權(quán)靜態(tài)圖異常檢測以及有權(quán)靜態(tài)圖異常檢測.

(1)無權(quán)靜態(tài)圖異常檢測:給定一個(gè)靜態(tài)同質(zhì)圖,充分利用圖的結(jié)構(gòu)信息查找模式并識(shí)別異常節(jié)點(diǎn).該類方法可以根據(jù)使用的模式進(jìn)一步分為基于結(jié)構(gòu)的模式和基于群體的模式這兩類;

(2)加權(quán)靜態(tài)圖異常檢測:靜態(tài)圖的節(jié)點(diǎn)或者邊具有屬性,利用結(jié)構(gòu)信息以及節(jié)點(diǎn)和邊的屬性信息進(jìn)行異常檢測.如社交網(wǎng)絡(luò)中用戶的興趣、金融交易網(wǎng)絡(luò)中的交易數(shù)量以及交易類型等等.

? 面向動(dòng)態(tài)圖的異常檢測

給定一個(gè)無權(quán)圖的序列或者加權(quán)圖的序列,從中查找:(1)對(duì)應(yīng)一個(gè)事件或者改變對(duì)應(yīng)的圖;(2)導(dǎo)致該改變或者事件的前k個(gè)節(jié)點(diǎn)/邊/子圖.

1.3 相關(guān)綜述工作

近年來,由于社會(huì)各界對(duì)異常檢測的關(guān)注,面向圖的異常檢測取得了很大的進(jìn)展,有不少面向圖異常檢測的綜述性文章陸續(xù)發(fā)表.Akoglu 等人[3]對(duì)面向圖異常檢測進(jìn)行了綜述,給出了異常檢測分類的基礎(chǔ)框架,將所有的算法分成了基于分類、統(tǒng)計(jì)、聚類以及信息論這4 種類型,并對(duì)每種方法進(jìn)行對(duì)比,給出面向圖的異常檢測在各個(gè)領(lǐng)域的應(yīng)用.Gogoi 等人[4]按照使用技術(shù),從基于距離的異常檢測、基于密度的異常檢測以及其他技術(shù)異常檢測這3 個(gè)方面進(jìn)行綜述,并將各種方法進(jìn)行對(duì)比.Gupta 等人[5]針對(duì)時(shí)序數(shù)據(jù)的異常檢測工作進(jìn)行了總結(jié)和歸納,其中,時(shí)序數(shù)據(jù)包括空間時(shí)序數(shù)據(jù)、分布數(shù)據(jù)流、時(shí)序網(wǎng)絡(luò)等.Ranshous 等人[6]將面向動(dòng)態(tài)圖異常檢測分成了基于群體檢測方法、基于MDL 的方法、基于距離的方法、基于降維的方法、基于概率分布的方法等幾類,并將每種類型方法中的主要算法進(jìn)行對(duì)比.Yu 等人[7]關(guān)注于社交網(wǎng)絡(luò)的異常檢測,并從點(diǎn)異常和群體異常兩個(gè)方面對(duì)社交網(wǎng)絡(luò)異常檢測研究進(jìn)展進(jìn)行概括和展望.

盡管已有上述眾多的面向網(wǎng)絡(luò)的異常檢測綜述,但大多都基于某一具體應(yīng)用領(lǐng)域,目前仍然缺少對(duì)圖異常檢測研究進(jìn)展進(jìn)行系統(tǒng)、全面、深入地梳理和總結(jié)的工作.以往的工作或基于圖的異常檢測的具體某一應(yīng)用進(jìn)行歸納分析(如Yu 等人[7]和Zhang 等人[8]聚焦于社交網(wǎng)絡(luò)中異常的賬號(hào)檢測以及異常群體檢測,Mao 等人[9]關(guān)注于空間軌跡異常檢測,Mo 等人[10]關(guān)注于網(wǎng)絡(luò)水軍檢測),或只總結(jié)了傳統(tǒng)的異常檢測方法而沒有涉及利用機(jī)器學(xué)習(xí)或者神經(jīng)網(wǎng)絡(luò)技術(shù)(如Gogoi 等人[4]和Gupta 等人[5]的工作).為此,本文對(duì)面向圖的異常檢測領(lǐng)域的傳統(tǒng)方法以及最新的研究進(jìn)展進(jìn)行系統(tǒng)的歸納和分類總結(jié),并展望未來的發(fā)展趨勢.

本文首先按照輸入圖的類型將現(xiàn)有工作分為面向靜態(tài)圖的異常檢測與面向動(dòng)態(tài)圖的異常檢測兩大類.在兩類異常檢測中,首先總結(jié)傳統(tǒng)的、經(jīng)典的方法,然后總結(jié)近年來利用機(jī)器學(xué)習(xí)技術(shù)與神經(jīng)網(wǎng)絡(luò)技術(shù)的一些方法.在第4 節(jié)中,總結(jié)面向圖異常檢測的關(guān)鍵技術(shù)、常用框架、領(lǐng)域應(yīng)用、實(shí)驗(yàn)數(shù)據(jù)以及評(píng)估方法.最后探討該領(lǐng)域的所有方法的優(yōu)缺點(diǎn)、當(dāng)前圖異常檢測的挑戰(zhàn)以及未來發(fā)展趨勢.

2 面向靜態(tài)圖的異常檢測

靜態(tài)圖的異常檢測面對(duì)的圖是靜態(tài)的,也可以是變化網(wǎng)絡(luò)在某一個(gè)時(shí)刻的快照,并根據(jù)整個(gè)圖的結(jié)構(gòu)信息和節(jié)點(diǎn)信息,從中查找異常的實(shí)體,如節(jié)點(diǎn)、邊、子圖.

根據(jù)能夠檢測異常的實(shí)體之間的關(guān)系是否是相互獨(dú)立的,靜態(tài)圖異常檢測可以分為孤立個(gè)體異常檢測和群體異常檢測.

2.1 孤立個(gè)體異常檢測

定義.給定一個(gè)網(wǎng)絡(luò)數(shù)據(jù),從中查找異常的實(shí)體,若異常的實(shí)體和實(shí)體之間是相互獨(dú)立的,則為孤立個(gè)體異常檢測.

面向孤立個(gè)體的網(wǎng)絡(luò)異常檢測可以分為基于結(jié)構(gòu)的方法、基于社團(tuán)的方法、基于信息論的方法、基于降維的方法、基于子圖的異常檢測和基于神經(jīng)網(wǎng)絡(luò)的方法等.

2.1.1 基于結(jié)構(gòu)的方法

基于結(jié)構(gòu)的方法分為兩類:基于結(jié)構(gòu)特征的方法和基于結(jié)構(gòu)相似度的方法:第1 種方法是總結(jié)已有正常網(wǎng)絡(luò)的特征,如節(jié)點(diǎn)出入度的分布規(guī)律或者子圖中心度的規(guī)律等;第2 種方法是通過圖的結(jié)構(gòu)計(jì)算節(jié)點(diǎn)臨近度,并以此判斷節(jié)點(diǎn)的異常性.

網(wǎng)絡(luò)的特征可以按照特征粒度分為節(jié)點(diǎn)的特征和圖的特征兩部分.

? 節(jié)點(diǎn)的特征主要包括節(jié)點(diǎn)的出度、入度、中介中心度(betweenness centrality)、特征向量中心性(eigenvector centrality)、集中系數(shù)(clustering coefficient)等.Akoglu[11]提出了egonet 特征,如節(jié)點(diǎn)所在的三角型數(shù)目、egonet 權(quán)重等等;

? 網(wǎng)絡(luò)的圖特征主要包括聯(lián)通分量的個(gè)數(shù)、聯(lián)通分量的分布、圖的主特征值、最小生成樹權(quán)重、平均節(jié)點(diǎn)深度、全局集中系數(shù)等.

基于節(jié)點(diǎn)的網(wǎng)絡(luò)特征的異常檢測方法的代表方法是OddBall.OddBall[11]是一種基于特征的異常檢測方法,通過觀測基于egonet 的特征分布規(guī)律,查找不符合該規(guī)律的egonet,即可以找出圖中的異常節(jié)點(diǎn).自我網(wǎng)絡(luò)(egonet)關(guān)注的不是網(wǎng)絡(luò)整體,而是以個(gè)體節(jié)點(diǎn)為中心,通過收集以該個(gè)體所關(guān)聯(lián)節(jié)點(diǎn)的信息,可以為個(gè)體構(gòu)建一個(gè)局部網(wǎng)絡(luò).一個(gè)egonet 是指以個(gè)體節(jié)點(diǎn)為中心的一跳范圍內(nèi)的所有鄰居節(jié)點(diǎn),以及這些節(jié)點(diǎn)之間的鏈接構(gòu)成一個(gè)egonet.如圖1 所示.

Fig.1 Egonet networks[11]圖1 Egonet 示意圖[11]

圖1 中紅色節(jié)點(diǎn)為核心節(jié)點(diǎn),藍(lán)色節(jié)點(diǎn)為一跳鄰居節(jié)點(diǎn),方框中包含的節(jié)點(diǎn)和邊組成了紅色節(jié)點(diǎn)的egonet.通過觀測正常真實(shí)網(wǎng)絡(luò),Akoglu[11]提出如下基于egonet 的特征的分布規(guī)律:給定一個(gè)圖G,節(jié)點(diǎn)i∈V(G),節(jié)點(diǎn)i的egonet 為gi,滿足:(1)gi中的節(jié)點(diǎn)數(shù)目Ni和邊的數(shù)目Ei符合冪律分布,1≤α≤2;(2)gi中的權(quán)重Wi和邊的數(shù)據(jù)Ei符合冪律分布,β≥1.真實(shí)的社交網(wǎng)絡(luò)符合該冪律分布,根據(jù)基于geonet 的分布規(guī)律,OddBall 使用節(jié)點(diǎn)值到擬合曲線的距離作為異常值,距離擬合曲線越遠(yuǎn)的點(diǎn),異常值越高.算法使用的特征易于計(jì)算,可以用于大規(guī)模網(wǎng)絡(luò)異常檢測.但是,如果網(wǎng)絡(luò)不符合冪律分布,則該算法將不起作用,且該算法只能適用于靜態(tài)圖.

2.1.2 基于社團(tuán)的方法

基于社團(tuán)方法的主要思路是:通過使用群體檢測的方法,將距離比較近的節(jié)點(diǎn)歸為一個(gè)群體,并查找那些連接各個(gè)群體卻不屬于各個(gè)群體的節(jié)點(diǎn)或者邊,即,在網(wǎng)絡(luò)中查找橋接節(jié)點(diǎn)或者橋接邊.

該類方法一般分成兩個(gè)步驟:(1)通過給定的網(wǎng)絡(luò)結(jié)構(gòu),利用節(jié)點(diǎn)的相似性或空間鄰近性確定節(jié)點(diǎn)屬于哪些群體;(2)查找群體的橋接節(jié)點(diǎn)或者橋接邊.

針對(duì)后文圖7 所示的GLAD 模型圖[12],步驟(1)可以基于節(jié)點(diǎn)的相似度,使用k-means 聚類方法將節(jié)點(diǎn)聚為k個(gè)類.該方法需要借助上一節(jié)中提到的相似度的計(jì)算方法.步驟(1)也可以使用譜劃分的方法,譜劃分以譜圖劃分為理論基礎(chǔ),矩陣的譜就是矩陣的特征值和矩陣的特征向量,圖劃分問題轉(zhuǎn)換成求解Laplacian 矩陣的譜分解.算法的核心思想是:通過引入Laplacican 矩陣,使用特征矩陣進(jìn)行降維,再對(duì)低維的數(shù)據(jù)進(jìn)行劃分,極大地降低了運(yùn)算量.

針對(duì)很多圖劃分方法以最大化群組內(nèi)部邊數(shù)為目標(biāo)的方法,往往忽視了兩種節(jié)點(diǎn)——一種是hub 節(jié)點(diǎn),另一種是異常節(jié)點(diǎn),Xu 等人[13]提出了網(wǎng)絡(luò)結(jié)構(gòu)聚類的算法SCAN.SCAN 算法將網(wǎng)絡(luò)中的節(jié)點(diǎn)分成3 種角色:一種是組內(nèi)節(jié)點(diǎn),這些節(jié)點(diǎn)屬于某一些社團(tuán);另外一種是橋接節(jié)點(diǎn),該類節(jié)點(diǎn)并不屬于某一個(gè)社團(tuán),它們把不同的社團(tuán)加以連接;最后一種是異常節(jié)點(diǎn),該類節(jié)點(diǎn)只與很少幾個(gè)特定團(tuán)體之間有連接.如圖2 所示.

Fig.2 SCAN algorithm[13]圖2 SCAN 算法示意圖[13]

那些沒有在高密度的連接塊之內(nèi)的節(jié)點(diǎn)則為異常節(jié)點(diǎn).算法借助于DBSCAN 算法確定超參數(shù)ε與μ.算法的時(shí)間復(fù)雜度為O(E),當(dāng)圖內(nèi)邊數(shù)較稠密時(shí),時(shí)間復(fù)雜度很高.

網(wǎng)絡(luò)群體檢測還可以使用矩陣分解的方法,Tong 和Lin[14]提出了使用矩陣分解進(jìn)行群體檢測和異常檢測的方法NrMF,對(duì)于一個(gè)圖G的鄰接矩陣A,若一個(gè)秩為r的A的相似矩陣為,那么對(duì)應(yīng)的殘差矩陣為,對(duì)于一個(gè)低維的矩陣的分解可以為,其中,F和G是一個(gè)維度為r的分解矩陣,R是殘差矩陣.F和G能夠自然地反映網(wǎng)絡(luò)的群體結(jié)構(gòu)信息,而對(duì)于殘差矩陣,則對(duì)應(yīng)著一個(gè)異常節(jié)點(diǎn).實(shí)驗(yàn)證實(shí)了算法能夠有效地識(shí)別出網(wǎng)絡(luò)中的異常連接,可用于端口掃描檢測以及DDoS 攻擊分析.

2.1.3 基于信任傳播的方法

互聯(lián)網(wǎng)上有不計(jì)其數(shù)的網(wǎng)頁,用戶信息獲取的一個(gè)重要方式是通過搜索引擎.垃圾網(wǎng)頁欺詐(Web spamming)是一種常用的攻擊搜索引擎排序算法的行為.PageRank 和HITS 算法認(rèn)為:有很多重要的網(wǎng)頁指向的網(wǎng)頁是重要的網(wǎng)頁,實(shí)際上是通過頁面之間的超鏈接傳播網(wǎng)頁的重要性.Gy?ngyi 等人[15]提出了針對(duì)垃圾網(wǎng)頁的檢測算法TrustRank,該算法假設(shè)兩個(gè)網(wǎng)頁之間的連接表示兩個(gè)網(wǎng)頁的信任,比如網(wǎng)頁A指向網(wǎng)頁B表示網(wǎng)頁A傳遞信任給網(wǎng)頁B.

TrustRank 由于種子網(wǎng)頁列表的設(shè)置會(huì)有一定的偏差,使得與種子網(wǎng)站相關(guān)領(lǐng)域的網(wǎng)頁信任值高,不同領(lǐng)域的信任值低.針對(duì)該問題,Wu 和Goel[16]提出了改進(jìn)算法Topical TrustRank,使用話題劃分種子網(wǎng)站列表,并提出不同的話題信息值合并的方法.

2.1.4 基于信息論的方法

利用信息論的方法進(jìn)行異常檢測一般使用信息論中的最小描述長度準(zhǔn)則MDL.對(duì)于給定的數(shù)據(jù)集合,使用模型和數(shù)據(jù)表示原有數(shù)據(jù),正常數(shù)據(jù)使用的模型和描述數(shù)據(jù)占用空間最小,異常數(shù)據(jù)使得占用空間增大.MDL模型具體介紹見第4.2 節(jié).針對(duì)以往的算法只能計(jì)算無權(quán)圖,而真實(shí)世界的網(wǎng)絡(luò)邊往往是具有屬性值的,如用戶產(chǎn)品打分網(wǎng)絡(luò),邊上會(huì)有用戶打分信息;社交網(wǎng)絡(luò)中的邊上會(huì)包含關(guān)系建立的時(shí)間;電話通聯(lián)網(wǎng)絡(luò)中會(huì)包含電話的持續(xù)時(shí)間等等.Shah 等人[17]提出了在加權(quán)圖上利用網(wǎng)絡(luò)結(jié)構(gòu)和邊的信息進(jìn)行異常檢測的方法EdgeCentric,算法使用MDL 檢測具有異常行為的節(jié)點(diǎn).算法支持同質(zhì)網(wǎng)絡(luò)與異質(zhì)網(wǎng)絡(luò),并給出了網(wǎng)絡(luò)中邊的數(shù)據(jù)為多屬性或單屬性時(shí)節(jié)點(diǎn)的異常度量.

Chakrabarti[18]提出了基于圖劃分的異常邊檢測算法,算法可以檢測出偏離網(wǎng)絡(luò)大簇的異常的邊.方法的核心思想是:如果移除一條邊可以使網(wǎng)絡(luò)更容易劃分,那么移除邊的兩個(gè)連接節(jié)點(diǎn)則是異常節(jié)點(diǎn).劃分算法嘗試尋找最好的劃分?jǐn)?shù),使得MDL 可以編碼整個(gè)網(wǎng)絡(luò)的空間使用最小.

2.1.5 基于神經(jīng)網(wǎng)絡(luò)的方法

近年來,深度神經(jīng)網(wǎng)絡(luò)因?yàn)榫哂休^高的靈活性以及能夠按照層級(jí)提取數(shù)據(jù)特征,從而在多個(gè)領(lǐng)域都取得了很好的性能.使用深度學(xué)習(xí)的方法解決圖異常檢測的方法也越來越多,并且通過實(shí)驗(yàn)表明,與一些傳統(tǒng)方法相比都取得了不錯(cuò)的進(jìn)步[19].

Chouiekh 等人[20]提出了使用有監(jiān)督學(xué)習(xí)的方法,使用正常用戶的數(shù)據(jù)訓(xùn)練神經(jīng)網(wǎng)絡(luò),使用神經(jīng)網(wǎng)絡(luò)學(xué)習(xí)特征,并用于正常用戶與異常用戶的分類.方法使用電話通聯(lián)網(wǎng)絡(luò)用戶通話詳細(xì)信息(CDR),提取其中的通話事件信息,包括通聯(lián)出度、入度、最大通話時(shí)間、每天通話數(shù)、每天SMS 數(shù)量等信息,將兩個(gè)月內(nèi)用戶每天的特征數(shù)據(jù)表示成一張圖,然后使用交叉驗(yàn)證的方法,利用7 層卷積神經(jīng)網(wǎng)絡(luò)進(jìn)行訓(xùn)練,神經(jīng)網(wǎng)絡(luò)由3 個(gè)卷積層、2 個(gè)池化層和1 個(gè)全連接層組成.通過實(shí)驗(yàn)對(duì)比,這一算法比SVM、隨機(jī)森林和梯度提升算法取得的效果要好.

Alsheikh 等人[21]提出在Spark 計(jì)算節(jié)點(diǎn)上使用深度學(xué)習(xí)提取特征的方法,解決了深度學(xué)習(xí)模型含有較多隱層以及海量參數(shù)、難以在集群上進(jìn)行模型訓(xùn)練的問題.該工作用于電話通聯(lián)網(wǎng)絡(luò)產(chǎn)生的海量數(shù)據(jù),使用Spark 分布式計(jì)算框架提高海量數(shù)據(jù)的處理能力,是當(dāng)前很多工業(yè)產(chǎn)品的主流做法.

圖3 為分層提取特征的深度學(xué)習(xí)模型圖,第1 層輸入的數(shù)據(jù)為無標(biāo)簽數(shù)據(jù),為了學(xué)習(xí)到輸入數(shù)據(jù)的結(jié)構(gòu),每一層包含一個(gè)編碼函數(shù)和解碼函數(shù),編碼函數(shù)使用輸入數(shù)據(jù)與當(dāng)前層的參數(shù)生成一個(gè)新的特征集合,解碼函數(shù)使用特征和參數(shù)重構(gòu)數(shù)據(jù),前一層的輸入作為后面層的輸出.最后,通過淺層特征的不斷組合學(xué)習(xí)到復(fù)雜的特征.通過使用標(biāo)簽數(shù)據(jù)對(duì)每一層的參數(shù)進(jìn)行微調(diào),通過該方法可以實(shí)現(xiàn)網(wǎng)絡(luò)的復(fù)雜特征提取,并采用Chouiekh 等人[20]的思路進(jìn)行模型訓(xùn)練與異常檢測.

Fig.3 Layered feature extraction with deep learning model[21]圖3 分層提取特征深度學(xué)習(xí)模型[21]

以上工作都是采用有監(jiān)督的方法,有監(jiān)督的方法需要有一定的標(biāo)記數(shù)據(jù),對(duì)于沒有標(biāo)記的數(shù)據(jù),可以使用無監(jiān)督的方法.傳統(tǒng)的異常檢測方法對(duì)數(shù)據(jù)降維的處理往往采用PCA 的方法,但PCA 方法假設(shè)系統(tǒng)是線性的,而在真實(shí)的環(huán)境中系統(tǒng)可能是非線性的[22].針對(duì)該問題,自學(xué)習(xí)編碼器是一種無監(jiān)督的模型訓(xùn)練方法,不需要用戶提供標(biāo)記數(shù)據(jù).數(shù)據(jù)處理流程如圖4 所示.

Zhang 等人[23]提出了使用自編碼器降維的方法,并將該自編碼器用于社交網(wǎng)絡(luò)謠言檢測,通過使用自編碼器,模型能夠從原始數(shù)據(jù)中學(xué)習(xí)到更多的特征,并通過訓(xùn)練的模型識(shí)別正常的用戶和謠言制造者.Zhang 等人[23]的思路是:首先采集每個(gè)用戶的原始數(shù)據(jù),使用原始數(shù)據(jù)進(jìn)行標(biāo)準(zhǔn)化處理;然后使用自編碼器進(jìn)行訓(xùn)練,輸入和輸出設(shè)置為相等,使用反向傳播算法調(diào)整超參數(shù);然后使用訓(xùn)練的模型,輸入和輸出差距較大的則為謠言信息.網(wǎng)絡(luò)中的要素除了節(jié)點(diǎn)的信息之外,還包括節(jié)點(diǎn)的文本信息、用戶行為信息等等.Zhang 等人[23]的工作還利用了節(jié)點(diǎn)的文本信息,以此來提取特征.

Fig.4 Flow chart for rumor detection using auto-encoder model[23]圖4 使用自編碼器進(jìn)行謠言檢測的流程圖[23]

針對(duì)自動(dòng)編碼器魯棒性弱的特點(diǎn),出現(xiàn)了自動(dòng)編碼器的變種,降噪自動(dòng)編碼器DA 是在自動(dòng)編碼器的基礎(chǔ)上,訓(xùn)練數(shù)據(jù)加入噪聲,所以自動(dòng)編碼器必須學(xué)習(xí)去除這種噪聲而獲得真正的沒有被噪聲污染過的輸入[24].因此,這就迫使編碼器去學(xué)習(xí)輸入信號(hào)的更加魯棒的表達(dá),這也是它的泛化能力比一般編碼器要更強(qiáng)的原因.Castellini 等人[25]提出了使用降噪自動(dòng)編碼器檢測僵尸粉絲的方法,該算法針對(duì)監(jiān)督學(xué)習(xí)的方法需用標(biāo)簽數(shù)據(jù)、而且標(biāo)簽數(shù)據(jù)需要覆蓋各類異常特征的問題,提出了使用半監(jiān)督的方法進(jìn)行異常檢測.該方法的總體思路和Zhang 等人[23]提出的方法相同,使用真實(shí)的數(shù)據(jù)進(jìn)行訓(xùn)練,得到原始數(shù)據(jù)的一個(gè)低維表示,并訓(xùn)練超參數(shù)使得重構(gòu)數(shù)據(jù)盡量一致,重構(gòu)差異較大的數(shù)據(jù)為異常數(shù)據(jù).實(shí)驗(yàn)表明,算法的魯棒性比自動(dòng)編碼器要好.

生成式對(duì)抗網(wǎng)絡(luò)(generative adversarial network,簡稱GAN)可以對(duì)現(xiàn)實(shí)世界復(fù)雜的高維數(shù)據(jù)進(jìn)行建模,一些算法將GAN 應(yīng)用于網(wǎng)絡(luò)異常檢測領(lǐng)域.Zenati 等人[26]提出了使用GAN 進(jìn)行異常檢測的方法,訓(xùn)練使用BiGAN模型,使模型同時(shí)學(xué)習(xí)一個(gè)編碼器E,將輸入樣本x映射到一個(gè)潛在的表示z,同時(shí)學(xué)習(xí)一個(gè)生成器G和判別器D.有別于普通GAN 的判別器只考慮輸入,這里的判別器同時(shí)需要考慮潛層表示.Zenati 等人[26]探索了不同的訓(xùn)練策略,使得E=G-1.通過在KDD CUP 99 上的異常入侵檢測數(shù)據(jù)集測試,算法取得了當(dāng)前最高的準(zhǔn)確度.

2.2 群體異常檢測

給定一個(gè)網(wǎng)絡(luò)數(shù)據(jù),從其中查找異常的實(shí)體,異常的實(shí)體和實(shí)體之間存在一定的相互關(guān)系,通過異常檢測算法檢測出的為異常群體.

群體的網(wǎng)絡(luò)異常檢測可以分為基于譜分析的方法、基于稠密子圖檢測的方法、基于張量檢測的方法和基于多層貝葉斯模型的方法等.

2.2.1 基于譜分析的方法

圖譜理論是應(yīng)用圖的相關(guān)矩陣的特征值和特征向量解決圖的相關(guān)問題的方法[27],該類方法進(jìn)行異常檢測通常抽取具有相關(guān)性的用戶群組或?qū)ο笕航M.譜分析中一個(gè)很重要的概念就是拉普拉斯矩陣,Von[28]給出了更多拉普拉斯矩陣的變種,如Lrw和Lsym,Lrw可以用于k=2 到k=100 的網(wǎng)絡(luò)劃分.研究發(fā)現(xiàn):該方法的網(wǎng)絡(luò)劃分可以檢測出很多非常小的簇和一個(gè)非常大的核,并且簇內(nèi)部缺乏相關(guān)性.針對(duì)該問題,Prakash[29]介紹了直接使用鄰接矩陣進(jìn)行劃分的方法,同時(shí)發(fā)現(xiàn)了一些在大的稀疏網(wǎng)絡(luò)中存在的規(guī)律.通過研究18.6 萬個(gè)節(jié)點(diǎn)和數(shù)百萬條邊的電話通聯(lián)網(wǎng)絡(luò),發(fā)現(xiàn)圖的單一向量在一條特定的軸上分布得很清晰,這種規(guī)律稱為EigenSpokes,由此算法可以進(jìn)行檢測可疑連接行為.EigenSpokes 基于SVD 分解.該方法使用奇異值分解(singular value decomposition,簡稱SVD)方法,通過對(duì)圖的鄰接矩陣進(jìn)行分解查找相似的用戶群.一般的工作都是通過分析左奇異矩陣Ui和Uj來發(fā)現(xiàn)存在的不同尋常的模式,如沿軸向分布、分布成類似珍珠的團(tuán)等等.在圖5 所示的電話通聯(lián)網(wǎng)絡(luò)中,顯示出不同時(shí)空域?qū)?yīng)的EigenSpokes 規(guī)律分布圖.

Fig.5 Time and space distribution of telephone communication network[29]圖5 電話通聯(lián)網(wǎng)絡(luò)中不同時(shí)空域?qū)?yīng)的分布圖[29]

2.2.2 基于稠密子圖的方法

稠密子圖挖掘一直是圖數(shù)據(jù)挖掘的熱點(diǎn),一般地,基于稠密子圖異常檢測的步驟是:首先查找網(wǎng)絡(luò)中最稠密的k個(gè)子圖,然后進(jìn)行異常檢測.該類異常檢測的定義根據(jù)場景的不同其使用方法也不盡相同.例如:社交網(wǎng)絡(luò)中的所有節(jié)點(diǎn)應(yīng)該都在一定的密度子圖中,沒有在稠密子圖中的少量節(jié)點(diǎn)為異常節(jié)點(diǎn);而在用戶-商品構(gòu)成的二部圖中,欺詐賬戶往往因?yàn)橛休^高的一致性評(píng)價(jià)從而形成了稠密子圖,而此時(shí),在最稠密子圖中心的節(jié)點(diǎn)往往是欺詐節(jié)點(diǎn).

傳統(tǒng)的用于稠密子圖檢測的方法一般是使用子圖平均度度量,Charikar[30]提出使用子圖的平均度定義子圖的密度,對(duì)于一個(gè)圖G=(V,E)為一個(gè)無向圖,其中,S?V,定義E(S)={i,j∈E:i∈S,j∈S},定義子圖的密度為f(S)=|E(S)|÷|S|,即子圖中邊的個(gè)數(shù)與點(diǎn)的個(gè)數(shù)的比值.2f(S)是集合S的平均度,而稠密子圖的問題則轉(zhuǎn)化為計(jì)算函數(shù)f(S)最大值的問題.求解該f(S)的問題是一個(gè)線性規(guī)劃問題,Charikar[30]給出了求解問題的精確算法.為了降低算法的復(fù)雜度,Charikar[30]提出了一種近似比為2 的近似算法.

已有的利用檢測子圖最大平均度密度的方法存在一定的偏差,往往使檢測出的結(jié)果包含大量的正常用戶,準(zhǔn)確率較低,增加了后期人為判斷的難度.針對(duì)這一問題,Liu 等人[31]提出了HoloScope 方法,基于“對(duì)比可疑度”的度量標(biāo)準(zhǔn)在5 000 萬條邊的大圖上,利用單機(jī)計(jì)算節(jié)點(diǎn)進(jìn)行檢測異常:(1)“對(duì)比可疑度”動(dòng)態(tài)度量了異常用戶和正常用戶行為的對(duì)比性差異,包括連接拓?fù)?、時(shí)間序列起伏、評(píng)分多樣性等信息,有效地防止了對(duì)正常用戶行為的誤判;(2)該檢測方法魯棒,并從理論上給出了對(duì)欺詐者攻擊時(shí)間的屏障下界,增加了欺詐的時(shí)間成本;(3)在僅利用拓?fù)浣Y(jié)構(gòu)和全部信息這兩種實(shí)驗(yàn)條件下,該檢測方法都比相應(yīng)的基準(zhǔn)方法在準(zhǔn)確率上有較大的提升;(4)算法的時(shí)間復(fù)雜度與大圖的邊數(shù)近似地呈線性關(guān)系,具有應(yīng)用于大規(guī)模數(shù)據(jù)分析的能力.

2.2.3 基于張量分解的方法

譜分析方法一般使用鄰接矩陣特征分解和SVD 分解進(jìn)行稠密子圖的檢測,EigenSpokes 算法用來在模式圖中查找異常的模式,Jiang 等人[32]用于在社交網(wǎng)絡(luò)中查找相同規(guī)律的關(guān)注者賬號(hào),Shah 等人[33]提出fBox 用來在社交網(wǎng)絡(luò)中查找小規(guī)模的異常攻擊.

圖或社交網(wǎng)絡(luò)一般被建模為二維網(wǎng)絡(luò)數(shù)據(jù)進(jìn)行研究,但這樣往往帶來數(shù)據(jù)的缺失.近年來,人們使用多模數(shù)據(jù)(張量)對(duì)網(wǎng)絡(luò)進(jìn)行建模與分析,當(dāng)模度為2 時(shí),可以建模社交網(wǎng)絡(luò)的關(guān)注與被關(guān)注者的關(guān)系,如建模Fasebook上的誰和誰是朋友的關(guān)系;當(dāng)模度為3 時(shí),可以建模以上網(wǎng)絡(luò)是如何演進(jìn)的或者商品評(píng)價(jià)時(shí)使用的是什么詞組;當(dāng)模度為4 時(shí),可以通過分析目標(biāo)IP、原始IP、目標(biāo)端口、時(shí)間戳等信息來追蹤網(wǎng)絡(luò)軌跡或者進(jìn)行入侵檢測.

以維基百科修改歷史數(shù)據(jù)集為例說明張量表示:存在關(guān)系R(user,page,date,count),每個(gè)元組(u,p,d,c)表示用戶u在日期d修改了頁面p,次數(shù)為c.關(guān)系中,前3 個(gè)是屬性,分別為user、page和date,最后一個(gè)是度量屬性count.

圖6 所示為關(guān)系的張量表示,底色為黃色的數(shù)據(jù)構(gòu)成子塊B,在圖6(b)中,子塊B對(duì)應(yīng)著子張量R.

針對(duì)基于SVD 分解的方法以及張量分解的方法沒有對(duì)多模稠密子圖按照可疑度進(jìn)行排序這一問題,Jiang等人[34]提出了CROSSSPOT 算法.該算法給出了在多模數(shù)據(jù)中進(jìn)行稠密子圖測量的度量公式,并提出了針對(duì)子向量或子張量進(jìn)行可疑度計(jì)算的度量公式,并使用該度量在張量中查找稠密子圖.

針對(duì)以往張量計(jì)算的算法計(jì)算速度較低、精確度也較低的問題,Shin 等人提出了一種靈活的、可調(diào)整的在張量中查找稠密子圖的框架M-Zoom[35].以往的算法在考慮子圖密度時(shí),使用的密度度量方式分為3 種:基于算術(shù)的度量方式、基于空間的度量方式、基于可疑度的度量方式.M-Zoom 算法可以使用以上但不限于這3 種度量方式.M-Zoom 給出可以使用的子張量密度的定義為:如果兩個(gè)塊在某一個(gè)屬性上有相同的基數(shù),兩個(gè)塊的度量相等或者更高,則兩個(gè)塊的稠密度是相同的.算法可以用于在維基百科中查找沖突觀點(diǎn)的用戶之間的編輯戰(zhàn),也可以檢測出維基百科中的攻擊活動(dòng),如頻繁的頁碼修改攻擊.該算法也可以用來進(jìn)行網(wǎng)絡(luò)入侵檢測,在網(wǎng)絡(luò)AirForce 數(shù)據(jù)集上,該算法測試AUC 為0.98.

Fig.6 Tensor representation of relations圖6 關(guān)系的張量表示

2.2.4 基于多層貝葉斯模型的方法

層次貝葉斯模型是一個(gè)統(tǒng)計(jì)模型,用來為具有不同水平的問題進(jìn)行建模,通過貝葉斯方法估計(jì)后驗(yàn)分布的參數(shù).使用多層貝葉斯模型進(jìn)行異常檢測的方法多是使用概率分布創(chuàng)建一個(gè)數(shù)據(jù)的生成模型,并將那些相對(duì)不是模型生成的數(shù)據(jù)認(rèn)為是異常數(shù)據(jù).Xiong 等人[36]提出了兩種層次貝葉斯模型,第1 種就是隱含狄利克雷分布(latent Dirichlet allocation,簡稱LDA)模型,文獻(xiàn)[36]假設(shè)每一個(gè)單獨(dú)的數(shù)據(jù)點(diǎn)屬于幾個(gè)話題,每一個(gè)群組是話題的聯(lián)合分布,使用多元高斯分布來確定觀測數(shù)據(jù)屬于哪一個(gè)話題.Yu 等人提出了GLAD 算法[12],GLAD 模型利用節(jié)點(diǎn)的特征信息和網(wǎng)絡(luò)結(jié)構(gòu)信息,自動(dòng)推斷群組的成員組成以及同時(shí)判斷成員的角色.假設(shè)每一個(gè)成員為p,一個(gè)群組為Gp,一個(gè)角色為Rp,Gp表示考慮了網(wǎng)絡(luò)信息相似性的聚類,Rp表示節(jié)點(diǎn)特征值的歸類.為簡化起見,定義群組的個(gè)數(shù)為M,角色的個(gè)數(shù)為K,圖7 所示為GLAD 的模型圖.

Fig.7 GLAD model[12]圖7 GLAD 模型圖[12]

GLAD 利用角色混合比例來定義群組的異常值,群組的異常值為 -∑p∈G〈logp(Rp|θ)〉p,分值越高,群組越異常.GLAD 的局限在于只能對(duì)靜態(tài)圖進(jìn)行建模,無法建模動(dòng)態(tài)圖.除了群組的角色比例與其他正常群組不同之外,研究混合比例隨網(wǎng)絡(luò)演進(jìn)的變化過程也是很有意義的.

2.3 小結(jié)

本節(jié)主要對(duì)面向靜態(tài)圖異常檢測的方法進(jìn)行歸類總結(jié),并從個(gè)體異常檢測以及群體的異常檢測兩個(gè)方面進(jìn)行歸納,將個(gè)體的異常檢測分成基于網(wǎng)絡(luò)結(jié)構(gòu)的異常檢測、基于群體的異常檢測、基于信任傳播的異常檢測和基于信息論的異常檢測等幾種類型.早期對(duì)于靜態(tài)圖異常檢測的研究主要從圖的特征提取、圖結(jié)構(gòu)劃分以及信息壓縮等方面進(jìn)行,但對(duì)于大規(guī)模圖數(shù)據(jù)異常檢測而言,早期方法往往不能勝任.近年來,由于網(wǎng)絡(luò)規(guī)模的提升以及計(jì)算能力的提升,圖異常檢測方法主要使用張量分解技術(shù)以及神經(jīng)網(wǎng)絡(luò)的相關(guān)技術(shù).這兩種技術(shù)都可以利用多模數(shù)據(jù),異常檢測也不是僅局限于網(wǎng)絡(luò)結(jié)構(gòu)特征,還可以融合考慮節(jié)點(diǎn)的內(nèi)容信息、標(biāo)簽信息以及行為信息,并且應(yīng)用越來越廣泛.

靜態(tài)圖在對(duì)數(shù)據(jù)進(jìn)行建模時(shí)沒有考慮到時(shí)間維度,即:隨著時(shí)間的變化,網(wǎng)絡(luò)結(jié)構(gòu)變化對(duì)應(yīng)的圖數(shù)據(jù)也發(fā)生了變化.因此,靜態(tài)圖異常檢測也具有局限性.動(dòng)態(tài)圖異常檢測技術(shù)在靜態(tài)圖異常檢測的基礎(chǔ)上發(fā)展而來.

3 面向動(dòng)態(tài)圖的異常檢測

現(xiàn)實(shí)世界中的網(wǎng)絡(luò)并不是一成不變的,而是隨著時(shí)間的改變,網(wǎng)絡(luò)的結(jié)構(gòu)和網(wǎng)絡(luò)節(jié)點(diǎn)的屬性也在不斷發(fā)生著變化,比如新的節(jié)點(diǎn)加入、個(gè)體之間新關(guān)系的增加或者消失、節(jié)點(diǎn)屬性的改變等等.動(dòng)態(tài)圖的異常檢測主要研究異常的節(jié)點(diǎn)、關(guān)系或者節(jié)點(diǎn)所處的某一個(gè)特殊的時(shí)刻.動(dòng)態(tài)圖異常檢測主要是檢測那些和大多數(shù)網(wǎng)絡(luò)演進(jìn)行為不同的異常情況,動(dòng)態(tài)圖異常檢測在現(xiàn)實(shí)生活中有很多重要的應(yīng)用,如生態(tài)失衡的研究、網(wǎng)絡(luò)系統(tǒng)的入侵研究、社交網(wǎng)絡(luò)中異常用戶和事件的研究、社交網(wǎng)絡(luò)用戶輿情檢測.雖然近幾年來有很多用于靜態(tài)圖異常檢測的方法,但是該類方法無法直接用于動(dòng)態(tài)圖,這是由于動(dòng)態(tài)圖異常檢測和靜態(tài)圖異常檢測模型不同所致.針對(duì)挑戰(zhàn)和異常類型的不同,主要表現(xiàn)在如下幾個(gè)方面.

(1)圖異常的種類不同:靜態(tài)圖中有異常點(diǎn)、異常關(guān)系、異常的子結(jié)構(gòu);動(dòng)態(tài)圖中同樣包含以上幾種異常,但是還包含圖斷層、圖子結(jié)構(gòu)消失或者偶爾出現(xiàn)的社交群體等等;

(2)網(wǎng)絡(luò)原型的變化有了時(shí)間的維度,需要同時(shí)存儲(chǔ)時(shí)間維度并進(jìn)行分析,每一個(gè)時(shí)間維度需要對(duì)原有圖和增量圖進(jìn)行存儲(chǔ)分析,原有靜態(tài)圖的分析方法還可以將所有數(shù)據(jù)加載在內(nèi)存中進(jìn)行計(jì)算,動(dòng)態(tài)圖中由于數(shù)據(jù)量太大將無法實(shí)現(xiàn);

(3)網(wǎng)絡(luò)原型與時(shí)間的關(guān)聯(lián)性具有多樣性,如社交網(wǎng)絡(luò)變化較快而基因網(wǎng)絡(luò)變化較慢;

(4)有些圖異常會(huì)跨多個(gè)時(shí)間域,分析起來更加困難.

動(dòng)態(tài)圖的異常類型可以分為異常實(shí)體、關(guān)系、子結(jié)構(gòu)和事件這4 種.本文將異常分成個(gè)體異常檢測、群體異常檢測和事件異常檢測這3 部分.個(gè)體異常檢測包括異常實(shí)體、關(guān)系以及事件的檢測.最后根據(jù)異常檢測采用的技術(shù)進(jìn)行二次分類,主要包括基于社團(tuán)檢測的方法、基于壓縮的方法、基于距離的方法、基于概率模型的方法等.

3.1 個(gè)體異常檢測

動(dòng)態(tài)圖往往可以表示成為一個(gè)圖和時(shí)間相關(guān)的序列.動(dòng)態(tài)圖中檢測異常的個(gè)體之間是相互獨(dú)立的,沒有依存關(guān)系的為面向動(dòng)態(tài)圖異常個(gè)體檢測,其中,異常的類型可以是異常的節(jié)點(diǎn)、異常的邊、異常的時(shí)刻等等.主要使用的方法可以分為基于偏差的方法、基于譜的方法和基于降維的方法等幾類.

3.1.1 基于偏差的方法

動(dòng)態(tài)圖異常檢測最基本的方法就是構(gòu)建每一個(gè)時(shí)刻網(wǎng)絡(luò)對(duì)應(yīng)的特征,然后進(jìn)行異常分析.Pincombe[37]定義了圖結(jié)構(gòu)特征的距離來衡量兩個(gè)連續(xù)時(shí)刻的圖結(jié)構(gòu)的差異,比如權(quán)重、邊數(shù)、節(jié)點(diǎn)數(shù)、網(wǎng)絡(luò)直徑等.該工作用于網(wǎng)絡(luò)異常演進(jìn)時(shí)間節(jié)點(diǎn)檢測.給定一個(gè)時(shí)間段以及度量方式,構(gòu)建一個(gè)網(wǎng)絡(luò)特征的序列.給定圖G={V,E,WV,WE},算法對(duì)每一種圖的特征構(gòu)建一個(gè)時(shí)間相關(guān)序列,每一個(gè)時(shí)間序列使用自回歸滑動(dòng)平均模型進(jìn)行建模.自回歸滑動(dòng)平均模型(autoregressive moving average model,簡稱ARMA 模型)是研究時(shí)間序列的重要方法,由自回歸模型(簡稱AR 模型)與移動(dòng)平均模型(簡稱MA 模型)為基礎(chǔ)“混合”構(gòu)成[38].

針對(duì)ARMA 模型無法考慮一段時(shí)間內(nèi)網(wǎng)絡(luò)特征變化的特點(diǎn),Malhotra 等人[39]提出了使用LSTM(long short-term memory)進(jìn)行異常檢測的方法,LSTM 是長短期記憶網(wǎng)絡(luò),是一種時(shí)間遞歸神經(jīng)網(wǎng)絡(luò),適合于處理和預(yù)測時(shí)間序列中間隔和延遲相對(duì)較長的重要事件.通過在LSTM 中包含一定的循環(huán)隱層,可以令網(wǎng)絡(luò)使用更稀疏的表示學(xué)習(xí)到更高層級(jí)的時(shí)序特征.算法通過使用不包含異常的數(shù)據(jù)進(jìn)行訓(xùn)練,得到一個(gè)與時(shí)間相關(guān)的預(yù)測函數(shù),預(yù)測結(jié)果的誤差應(yīng)該符合多元高斯分布,并以此進(jìn)行異常檢測.

算法的模型為:針對(duì)一個(gè)時(shí)間序列模型X={x(1),x(2),x(3),…,x(n)},其中,對(duì)于每一個(gè)時(shí)刻t對(duì)應(yīng)的x(t)∈Rm,是一個(gè)m維的向量{x(1),x(2),x(3),…,x(n)},每一個(gè)值對(duì)應(yīng)一個(gè)輸入變量.訓(xùn)練一個(gè)預(yù)測模型用來預(yù)測輸入變量的值,訓(xùn)練使用交叉驗(yàn)證的方法,將正常的數(shù)據(jù)集分成4 個(gè)部分:正常數(shù)據(jù)、正常驗(yàn)證數(shù)據(jù)1、正常驗(yàn)證數(shù)據(jù)2、正常測試數(shù)據(jù).首先使用LSTM 訓(xùn)練模型,然后計(jì)算預(yù)計(jì)錯(cuò)誤的分布函數(shù).圖8 所示為該算法LSTM 的模塊單位和層級(jí)結(jié)構(gòu).

LSTM 的網(wǎng)絡(luò)架構(gòu)為:使用m個(gè)維度中的一個(gè)作為輸入,d×l個(gè)單元作為輸出,隱層的LSTM 單元是循環(huán)網(wǎng)絡(luò)的一個(gè)全連接網(wǎng)絡(luò),使用時(shí)間序列SN進(jìn)行訓(xùn)練,集合VN1用來停止訓(xùn)練.使用SN訓(xùn)練的模型計(jì)算驗(yàn)證數(shù)據(jù)集合實(shí)驗(yàn)數(shù)據(jù)集中的每一個(gè)點(diǎn)對(duì)應(yīng)的錯(cuò)誤值的向量,錯(cuò)誤向量的分布符合多元高斯分布N=N(μ,Σ),使用最大似然估計(jì)的方法估計(jì)參數(shù)μ和Σ的值,在t時(shí)刻的相似度pt通過t時(shí)間的錯(cuò)誤向量進(jìn)行計(jì)算,當(dāng)pt小于閾值τ時(shí),任務(wù)在t時(shí)刻是異常數(shù)據(jù);否則為正常數(shù)據(jù).閾值τ可以通過最大化Fβ-score(異常數(shù)據(jù)為正樣本,正常數(shù)據(jù)為負(fù)樣本)計(jì)算得出.

Fig.8 Units and hierarchies of LSTM[39]圖8 LSTM 模塊單位和層級(jí)結(jié)構(gòu)[39]

基于偏差的方法也需要首先定義一個(gè)度量衡量兩點(diǎn)之間的區(qū)別,偏差也可以認(rèn)為是距離.異常節(jié)點(diǎn)和異常邊的異常檢測有些是基于距離度量的方法.衡量兩個(gè)圖的相似度一般使用網(wǎng)絡(luò)的結(jié)構(gòu)特征,如網(wǎng)絡(luò)中節(jié)點(diǎn)的數(shù)目,不同的方法選擇不同的度量方式,并用來計(jì)算異常值.

3.1.2 基于社區(qū)的方法

基于社區(qū)的方法追蹤網(wǎng)絡(luò)社區(qū)隨著時(shí)間推進(jìn)的社區(qū)變化情況以及社區(qū)組成節(jié)點(diǎn)的關(guān)系變化過程,同時(shí)進(jìn)行異常檢測.該類方法主要應(yīng)用社區(qū)的網(wǎng)絡(luò)結(jié)構(gòu),方法的不同體現(xiàn)在兩個(gè)方面:(1)對(duì)社區(qū)結(jié)構(gòu)進(jìn)行分析的方法不同,比如采用不同的社區(qū)檢測方法;(2)社區(qū)定義的方法不同,有的方法按照可能性認(rèn)為節(jié)點(diǎn)可以隸屬于多個(gè)社區(qū),即有重疊的社區(qū)發(fā)現(xiàn),而有些方法認(rèn)為節(jié)點(diǎn)只能屬于一個(gè)社區(qū).

面向動(dòng)態(tài)圖的基于社區(qū)的孤立異常檢測可以分為異常節(jié)點(diǎn)的檢測和異常關(guān)系的檢測.一個(gè)社區(qū)中的節(jié)點(diǎn)應(yīng)該具有一定的相似性,如果一個(gè)節(jié)點(diǎn)在某一個(gè)時(shí)間段內(nèi)新增大量的邊,那么其他節(jié)點(diǎn)也應(yīng)該新增大量的邊.如果其他節(jié)點(diǎn)沒有新增大量的邊,那么該節(jié)點(diǎn)為異常節(jié)點(diǎn).

針對(duì)動(dòng)態(tài)圖中社團(tuán)演進(jìn)模式難以發(fā)現(xiàn)以及存在很多干擾因素的問題,Gupta 等人[40]提出了一種有效的檢測網(wǎng)絡(luò)演進(jìn)趨勢異常的方法:首先對(duì)正常的網(wǎng)絡(luò)社團(tuán)演進(jìn)行為使用潛在的模式挖掘進(jìn)行建模,然后使用他們提出的通過計(jì)算節(jié)點(diǎn)演進(jìn)與正常演進(jìn)模式之間的距離來計(jì)算偏差.

Fu 等人提出了dMMSB[41]模型以識(shí)別網(wǎng)絡(luò)中角色以及角色隨著時(shí)間變化的過程,但該模型需要用戶指定一個(gè)超參數(shù).Rossi 等人針對(duì)dMMSB 模型需要超參數(shù)以及算法可擴(kuò)展性差的問題,提出了一個(gè)可擴(kuò)展的時(shí)序行為模型DBMM[42],用來分析節(jié)點(diǎn)行為隨時(shí)間變化的過程,學(xué)習(xí)一個(gè)預(yù)測模型估計(jì)節(jié)點(diǎn)行為,并可以檢測異常的時(shí)序行為轉(zhuǎn)移情況.

3.1.3 基于矩陣分解或張量分解的方法

該類方法一般是將網(wǎng)絡(luò)表示成為張量,然后使用張量分解的方法或者其他降維的方法.動(dòng)態(tài)圖的異常檢測首先需要對(duì)動(dòng)態(tài)圖進(jìn)行建模,最簡單且直接的方法是將時(shí)間作為一個(gè)維度,另外幾個(gè)維度為其他感興趣的因素.使用張量進(jìn)行建模的優(yōu)點(diǎn)是擴(kuò)展性強(qiáng),算法可以通過增加維度來考慮更多的信息,如屬性信息.然后在整個(gè)圖的張量的角度上,查找通用的模式并檢測出異常的模式.靜態(tài)圖和動(dòng)態(tài)圖使用張量進(jìn)行異常檢測的方法是類似的,對(duì)于一個(gè)模度為2 的張量,一般使用SVD 分解的方法進(jìn)行異常檢測;在高維的張量上進(jìn)行異常檢測,則使用SVD的擴(kuò)展方法PARAFAC.

通過矩陣分解可以得到每一個(gè)節(jié)點(diǎn)的活動(dòng)向量,如果一個(gè)節(jié)點(diǎn)的活動(dòng)在一個(gè)連續(xù)的時(shí)間內(nèi)變化較大,則認(rèn)為該節(jié)點(diǎn)為異常節(jié)點(diǎn).在靜態(tài)圖中,常使用主成分分析的方法進(jìn)行降維,但在整個(gè)動(dòng)態(tài)圖中使用PCA 降維,計(jì)算量會(huì)特別巨大.Yu 等人[43]認(rèn)為,動(dòng)態(tài)圖的異常改變或者發(fā)生事件具有時(shí)間和空間上的局部性.因此,Yu 等人提出在網(wǎng)絡(luò)邊結(jié)構(gòu)上使用局部的PCA 方法進(jìn)行分析,局部的特征向量表示了邊關(guān)聯(lián)模型的相關(guān)信息,而局部的特征值則表示了網(wǎng)絡(luò)邊關(guān)聯(lián)變化強(qiáng)弱的相對(duì)水平.

Yu 等人[43]算法的主要思路是:對(duì)每一個(gè)節(jié)點(diǎn)維持一個(gè)邊連接矩陣M,M為n×n的矩陣,其中,n為連接鄰居的數(shù)目.對(duì)于每一個(gè)節(jié)點(diǎn)i,值M(j,k)表示邊(i,j)和(i,k)的頻率權(quán)重,頻率權(quán)重采用衰減函數(shù),隨著時(shí)間的推遲而減弱.針對(duì)矩陣M使用PCA 降維方法,最大的特征值和特征向量表示了關(guān)聯(lián)邊的變化活動(dòng)情況,每個(gè)時(shí)間快照的特征值構(gòu)成了一個(gè)時(shí)間序列.在閾值之外的特征值對(duì)應(yīng)的時(shí)間節(jié)點(diǎn)為異常時(shí)間點(diǎn),對(duì)應(yīng)的節(jié)點(diǎn)i為異常節(jié)點(diǎn).

3.1.4 異常邊識(shí)別方法

以上方法都是從動(dòng)態(tài)圖中查找異常節(jié)點(diǎn),還有一些方法是從網(wǎng)絡(luò)中查找異常邊.如Heard 等人[44]認(rèn)為:如果一個(gè)社交網(wǎng)絡(luò)在某些方面進(jìn)行了重要的改變,那么意味著在大多數(shù)情況下存在一些個(gè)體通聯(lián)比以往更少或者更多,或者進(jìn)行通聯(lián)不同個(gè)體的數(shù)量比平時(shí)更多或更少.因此,他們提出一種在動(dòng)態(tài)圖中進(jìn)行異常檢測的兩步驟方法:第1 階段清理數(shù)據(jù)庫找到潛在的網(wǎng)絡(luò)異常節(jié)點(diǎn)子數(shù)據(jù)集,第2 步使用該子數(shù)據(jù)集構(gòu)建一個(gè)子圖.該算法可以完全并行執(zhí)行.收斂到有問題的快照和節(jié)點(diǎn)對(duì)數(shù)據(jù)后,使用譜聚類的方法查找網(wǎng)絡(luò)中的節(jié)點(diǎn)簇,收斂計(jì)算結(jié)果,提高準(zhǔn)確性.

Li 等人[45]將交通網(wǎng)絡(luò)視為一個(gè)邊的權(quán)重隨時(shí)間而變化的動(dòng)態(tài)圖,他們使用衰減函數(shù)計(jì)算隨著時(shí)間的變化邊權(quán)重的變化情況.算法將動(dòng)態(tài)交通網(wǎng)絡(luò)視為一個(gè)網(wǎng)絡(luò)邊的流,整個(gè)網(wǎng)絡(luò)沒有固定的拓?fù)浣Y(jié)構(gòu),如果一條邊在流中頻繁出現(xiàn),則該網(wǎng)絡(luò)中該邊會(huì)持續(xù)存在,關(guān)于邊的持續(xù)函數(shù)計(jì)算是通過該邊自從添加后持續(xù)的時(shí)間長度來表示的.異常度函數(shù)使用相似函數(shù)的變化總和表示,算法需要給定一個(gè)啟發(fā)式參數(shù)k,查找最異常的前k個(gè)邊.Abello 等人[46]提出了基于集合偏差的異常模式檢測方法DND,該方法將圖中的所有邊標(biāo)記上兩個(gè)個(gè)體之間通信的時(shí)間,將整個(gè)動(dòng)態(tài)圖視為一個(gè)集合系統(tǒng),這樣可以使用組合差查看不同時(shí)間范圍的變化情況,DND 的網(wǎng)絡(luò)表示圖如圖9 所示.

Fig.9 DND algorithm[46]圖9 DND 算法[46]

DND 算法使用邊集合偏差表示邊的頻率,當(dāng)網(wǎng)絡(luò)中存在一個(gè)新的邊時(shí),邊的差通過與所有活躍的邊的偏差的平均值進(jìn)行計(jì)算而獲得,如果該邊的集合差超過一定的閾值,那么就認(rèn)定邊是異常的邊.

3.2 異常群體檢測

區(qū)別于動(dòng)態(tài)圖的孤立目標(biāo)異常檢測,動(dòng)態(tài)圖群體檢測考慮到時(shí)間維度,難度更大.因?yàn)槭紫纫鶕?jù)給出的時(shí)間序列數(shù)據(jù),提取出所有的社團(tuán)信息,這需要使用社團(tuán)發(fā)現(xiàn)的相關(guān)算法.而隨著時(shí)間的改變,社團(tuán)的組成結(jié)構(gòu)是變化的,每個(gè)時(shí)間快照數(shù)據(jù)中的社團(tuán)信息需要對(duì)應(yīng)起來,這需要使用社團(tuán)匹配的技術(shù).Greene 等人[47]給出了追蹤網(wǎng)絡(luò)社團(tuán)演進(jìn)的一些方法,可用于社團(tuán)匹配以及社團(tuán)演進(jìn)研究.當(dāng)確定好匹配的社團(tuán)之后,才可以使用異常檢測的方法對(duì)社團(tuán)的變化情況進(jìn)行比較,如比較子圖的邊的權(quán)重、比較子圖在相鄰時(shí)間上的三角形數(shù)目的變化情況.在動(dòng)態(tài)圖中,異常子圖主要是社團(tuán)分解、社團(tuán)合并、社團(tuán)消失或者頻繁再現(xiàn)等等不同于其他多數(shù)社團(tuán)變化的子圖和時(shí)間戳.動(dòng)態(tài)圖異常群體檢測不同的領(lǐng)域,關(guān)注的異常群體的類型也不一樣,如可以分析交通情況或者用于分析社交網(wǎng)絡(luò)異常群體.

動(dòng)態(tài)圖異常群體的檢測方法一般可以分為基于社團(tuán)檢測的方法、基于降維的方法和基于距離的方法等.

3.2.1 基于社團(tuán)檢測的方法

基于社團(tuán)的方法首先將每一個(gè)時(shí)間的網(wǎng)絡(luò)快照數(shù)據(jù)進(jìn)行社團(tuán)檢測,然后分析社團(tuán)的演進(jìn)過程.

Chen 等人[48]提出一種基于社團(tuán)的無參數(shù)的異常檢測方法.Chen 等人認(rèn)為,社團(tuán)異常主要分為6 種類型:社團(tuán)的收縮、社團(tuán)的增長、社團(tuán)的合并、社團(tuán)的切分、新社團(tuán)的誕生和社團(tuán)的消亡.算法使用社團(tuán)代表集合,將臨近時(shí)刻的社團(tuán)代表集合進(jìn)行比較,并將社團(tuán)的變化情況歸為6 種異常中的一種.圖10 所示為社團(tuán)增長和社團(tuán)合并的示意圖.

Fig.10 Community growth and community consolidation[48]圖10 社團(tuán)增長和社團(tuán)合并示意圖[48]

算法使用的是有重疊的社團(tuán)檢測技術(shù),使用社團(tuán)代表集合代表一個(gè)社團(tuán).一個(gè)社團(tuán)的代表定義為在該社團(tuán)中存在的且在其他社團(tuán)中存在的次數(shù)最少的節(jié)點(diǎn).通過使用代表集合,可有效降低算法的時(shí)間復(fù)雜度.

Araujo 等人[49]提出了一種基于增量張量分解的異常群體檢測方法,可以發(fā)現(xiàn)臨時(shí)的社團(tuán)或者周期性不斷出現(xiàn)的社團(tuán).算法使用MDL 的方法進(jìn)行社團(tuán)分析,并使用張量分解的方法收斂計(jì)算結(jié)果集合.他們提出了一種近似算法,算法首先對(duì)每一個(gè)起點(diǎn)終點(diǎn)時(shí)間對(duì)給出一個(gè)打分,挑選出候選社團(tuán)集合,使用得分值進(jìn)行排序,查找重要的社團(tuán),使用MDL 確定社團(tuán)的大小,最后根據(jù)檢測到的社團(tuán)結(jié)合,再次使用張量分解多次迭代找到最優(yōu)結(jié)果集合.

3.2.2 基于分解的方法

基于分解的方法是指使用矩陣分解或者張量分解的方法進(jìn)行異常檢測,張量分析是高維數(shù)據(jù)分析的一種有效工具.Koutra 等人[50]提出了一種基于PARAFAC 的分解方法,可以檢測出動(dòng)態(tài)圖中微小的團(tuán)或者微小的改變,并進(jìn)一步用于異常檢測.

TENSORSPLAT 可以檢測動(dòng)態(tài)圖中的改變,如在DBLP 數(shù)據(jù)集中,可以檢測經(jīng)常轉(zhuǎn)換研究領(lǐng)域的作者.另外,還可以檢測隨時(shí)間改變的異常情況,如可以在計(jì)算機(jī)連接網(wǎng)絡(luò)或者社交網(wǎng)絡(luò)交互中檢測異常情況.算法還可以檢測節(jié)點(diǎn)聚類信息,如研究領(lǐng)域相同的作者或者是相同的會(huì)議上發(fā)表論文的作者.

雖然已經(jīng)有了成熟的張量分解的方法,但是很多現(xiàn)實(shí)的情況是數(shù)據(jù)量太大而無法加載到內(nèi)存中.針對(duì)內(nèi)存中無法加載超大張量的情況,Papalexakis 等人[51]提出了一種可并行執(zhí)行并加速的張量分解的方法,算法可以提供運(yùn)行速度14 倍,并給出了分解結(jié)果正確的理論下限.

總而言之,使用分解的方法多是在靜態(tài)圖的基礎(chǔ)上考慮時(shí)間維度信息,并使用張量分解的方法分析網(wǎng)絡(luò)變化情況,以進(jìn)行異常檢測.

3.3 事件異常檢測

不同于靜態(tài)圖,動(dòng)態(tài)圖除了有異常點(diǎn)、異常邊、異常子圖之外,還有一種類型是事件異常檢測.通常情況下,事件異常檢測是在時(shí)序數(shù)據(jù)中查找與其他大多數(shù)不同的時(shí)間點(diǎn),再通過對(duì)時(shí)間點(diǎn)的網(wǎng)絡(luò)結(jié)構(gòu)數(shù)據(jù)使用靜態(tài)圖的異常檢測方法深入研究異常發(fā)生的深層原因.

從時(shí)序數(shù)據(jù)中查找異常數(shù)據(jù),需要將每一個(gè)時(shí)間快照的網(wǎng)絡(luò)數(shù)據(jù)提取網(wǎng)絡(luò)特征,臨近的數(shù)據(jù)使用相似度的評(píng)估方法檢測異常數(shù)據(jù),如可以使用每個(gè)時(shí)間快照的節(jié)點(diǎn)的數(shù)目和連接邊的數(shù)目變化情況,也可以提取每個(gè)時(shí)間快照的平均集聚系數(shù),分析變化較大的時(shí)間點(diǎn).

3.3.1 基于分解的方法

分解的方法主要是指矩陣分解或者張量分解的方法.基于分解的方法的主要思路有兩種.

? 一種是使用數(shù)據(jù)降維,然后使用降維后得到的向量對(duì)原始數(shù)據(jù)進(jìn)行重構(gòu)還原.如果重建的誤差高于一定的閾值,則認(rèn)為對(duì)應(yīng)的原始數(shù)據(jù)是異常數(shù)據(jù),如Sun 等人[52]提出的異常檢測方法;

? 另一種思路是對(duì)每個(gè)時(shí)刻的圖數(shù)據(jù)的特征值和特征向量進(jìn)行計(jì)算,分析其變化趨勢,變動(dòng)較大的數(shù)據(jù)則為異常時(shí)間點(diǎn).

低維度的數(shù)據(jù)往往可以直接采用SVD 分解的方法或者CUR 分解的方法,但是實(shí)際使用的數(shù)據(jù)是高維度稀疏的圖數(shù)據(jù),而稀疏的高維張量往往無法直接加載到內(nèi)存中.Sun 等人[52]提出了一種壓縮的矩陣分解方法,用于計(jì)算高維系數(shù)矩陣,并可以從動(dòng)態(tài)圖中檢測事件異常.

Sun 等人[52]提出的異常檢測思路是對(duì)于每一個(gè)時(shí)刻t,使用提出的高維系數(shù)矩陣的壓縮方法,計(jì)算出一個(gè)低維稠密的矩陣,并存儲(chǔ)對(duì)應(yīng)的列和行,存儲(chǔ)近似差值SSE,近似差值可以認(rèn)為是使用壓縮后的矩陣能夠掌握的全局變化的信息量.在整個(gè)時(shí)間序列過程中,固定壓縮比例和壓縮后矩陣的大小,觀測近似差值的變化情況.如果一個(gè)時(shí)刻的近似差較大或者一個(gè)時(shí)間段內(nèi)近似差值變化較大,則在對(duì)應(yīng)的時(shí)刻網(wǎng)絡(luò)中有較大的變化或者事件,可以進(jìn)一步采用靜態(tài)圖異常檢測的方法進(jìn)行研究.

以往的面向網(wǎng)絡(luò)數(shù)據(jù)流的異常檢測方法往往是基于數(shù)據(jù)源的方法,該類方法大多是在數(shù)據(jù)源嵌入一種檢測算法,但該類方法無法找到異常的完整分布情況.針對(duì)該問題,Jiang 等人[53]提出了在完整網(wǎng)絡(luò)數(shù)據(jù)流中使用稀疏PCA 進(jìn)行異常定位的方法,算法使用學(xué)習(xí)到的正常子空間進(jìn)行異常檢測.

3.3.2 基于距離的方法

基于距離的方法進(jìn)行事件檢測需要定義一個(gè)距離度量函數(shù)[54],計(jì)算一個(gè)時(shí)間序列數(shù)據(jù)中任意兩個(gè)連續(xù)的時(shí)刻之間的圖的距離;然后使用滑動(dòng)窗口計(jì)算平均值或者查找前k個(gè)偏差比較大的值對(duì)應(yīng)的時(shí)刻[55].

Berlingerio 等人[56]提出了一種基于距離的評(píng)價(jià)網(wǎng)絡(luò)相似度的方法NetSimile,給定兩組節(jié)點(diǎn)集合,使用NetSimile 算法可以計(jì)算兩組網(wǎng)絡(luò)之間的相似度,且網(wǎng)絡(luò)之間可以沒有共有節(jié)點(diǎn).算法可以使用在遷移學(xué)習(xí)中或者是網(wǎng)絡(luò)節(jié)點(diǎn)更換身份之后的重新識(shí)別.算法的主要思路是:針對(duì)每一個(gè)圖G,從眾多的特征之中提取出能夠表示網(wǎng)絡(luò)結(jié)構(gòu)和網(wǎng)絡(luò)結(jié)構(gòu)特征分布規(guī)律的特征.兩個(gè)圖之間的相似度就是兩個(gè)圖的指紋特征向量的相似度.

計(jì)算兩個(gè)圖之間相似度的方法多種多樣,Soundarajan 等人[57]對(duì)常見的計(jì)算兩個(gè)圖距離的方法進(jìn)行對(duì)比,通過實(shí)驗(yàn)對(duì)比近20 種網(wǎng)絡(luò)相似度的方法后發(fā)現(xiàn):不同的網(wǎng)絡(luò)相似度的計(jì)算方法具有驚人的相關(guān)性,一些復(fù)雜的計(jì)算網(wǎng)絡(luò)相似度的方法可以使用簡單的方法近似計(jì)算,并且?guī)е貑⒌碾S機(jī)游走方法和NetSimile 方法取得的結(jié)果排序是一致的.

3.3.3 基于神經(jīng)網(wǎng)絡(luò)的異常事件檢測方法

時(shí)序數(shù)據(jù)分析的傳統(tǒng)方法采用基于統(tǒng)計(jì)的方法居多,近年來,隨著深度神經(jīng)網(wǎng)絡(luò)的發(fā)展,尤其是長短期記憶網(wǎng)絡(luò)的發(fā)展,由于其具有存儲(chǔ)長期記憶的能力,對(duì)處理未知長度的序列數(shù)據(jù)非常有用.LSTM 內(nèi)部的循環(huán)隱層使得神經(jīng)網(wǎng)絡(luò)能夠?qū)W習(xí)到更高層的時(shí)序特征.

Malhotra 等人[39]提出了使用LSTM 進(jìn)行異常檢測的方法,通過使用LSTM 網(wǎng)絡(luò)建模正常數(shù)據(jù),可以準(zhǔn)確地檢測出沒有預(yù)處理過的異常.實(shí)驗(yàn)結(jié)果表明:LSTM 的sigmoid 的神經(jīng)層可以捕獲時(shí)間序列的結(jié)構(gòu)信息,并可以從不同的時(shí)間范圍處理時(shí)間序列信息.該方法已在第3.1.1 節(jié)中進(jìn)行了詳細(xì)介紹.

真實(shí)的數(shù)據(jù)中往往已經(jīng)包含了異常的數(shù)據(jù)和變化的數(shù)據(jù),這些數(shù)據(jù)使得訓(xùn)練的模型偏離了潛在的模式,尤其是實(shí)時(shí)在線系統(tǒng).Guo 等人[58]提出了一種魯棒性更高的自適應(yīng)梯度方法的LSTM 神經(jīng)網(wǎng)絡(luò),以預(yù)測時(shí)序數(shù)據(jù)中的異常和變化的點(diǎn)數(shù)據(jù).算法通過時(shí)序網(wǎng)絡(luò)局部的特征來設(shè)置損失的梯度,以適應(yīng)于新的實(shí)時(shí)的觀測數(shù)據(jù).算法使用LSTM 對(duì)時(shí)間數(shù)據(jù)建模,并采用隨機(jī)梯度下降的方法從時(shí)間序列數(shù)據(jù)中學(xué)習(xí)模型,一個(gè)新的觀測數(shù)據(jù)到達(dá)后,模型的參數(shù)根據(jù)新的可用數(shù)據(jù)損失的梯度進(jìn)行更新,如果新的觀測數(shù)據(jù)是可能的異常數(shù)據(jù),則與常規(guī)模式的數(shù)據(jù)不同,其對(duì)應(yīng)的梯度將會(huì)下調(diào),從而避免在線模型突然偏離正常的模式.該方法定義了一個(gè)變化點(diǎn)和前后的時(shí)間差距較大的點(diǎn).如果一個(gè)新的觀測數(shù)據(jù)為一個(gè)變化點(diǎn),則對(duì)應(yīng)的梯度將會(huì)被限制在一個(gè)較高的值并引導(dǎo)模型適應(yīng)新的數(shù)據(jù).算法根據(jù)局部數(shù)據(jù)的分布特征構(gòu)建一個(gè)權(quán)重函數(shù),權(quán)重由可疑度和局部數(shù)據(jù)偏差構(gòu)成,使得模型學(xué)習(xí)過程更具有魯棒性.

Malhotra 等人[39]提出的方法認(rèn)為:異常是一個(gè)孤立的時(shí)間點(diǎn),并且每個(gè)點(diǎn)之間是相互獨(dú)立的,異常檢測的模型并沒有利用以往的數(shù)據(jù)或者事件來評(píng)估當(dāng)前點(diǎn)的能力.在一些應(yīng)用場景中,如DOS 攻擊,事件通常會(huì)持續(xù)一段時(shí)間,并且異常是由一個(gè)連續(xù)的時(shí)間點(diǎn)集合來表示的,單獨(dú)一個(gè)點(diǎn)的訪問失敗是正常的,但當(dāng)很多點(diǎn)同時(shí)訪問失敗就不正常了.為了檢測這種攻擊,異常檢測的模型需要能夠捕獲并記住以往的一些事件,Bontemps 等人[59]針對(duì)以往的方法僅針對(duì)孤立點(diǎn)進(jìn)行異常檢測,提出了使用LSTM 網(wǎng)絡(luò)查找群體異常的方法,并將該方法應(yīng)用于網(wǎng)絡(luò)入侵檢測.在文獻(xiàn)[59]中,當(dāng)前的事件依賴于以往的事件和當(dāng)前的事件,模型通過一個(gè)循環(huán)數(shù)據(jù)監(jiān)測群體異常,循環(huán)數(shù)據(jù)中使用模型預(yù)測指定的時(shí)間之后的結(jié)果,如果預(yù)測誤差超過了一定的閾值并且持續(xù)了一段時(shí)間,則認(rèn)為是一段群體異常.

Malhotra 等人[60]認(rèn)為:時(shí)間序列數(shù)據(jù)往往會(huì)受到外部因素的干擾,如人為操作因素或者外界環(huán)境因素,而且可能不會(huì)被時(shí)間序列數(shù)值感應(yīng)器接收到,數(shù)據(jù)噪聲和異常數(shù)據(jù)同時(shí)存在,因此對(duì)時(shí)間序列的預(yù)測是困難的.Malhotra 等人[60]提出了使用編碼-解碼器的LSTM 神經(jīng)網(wǎng)絡(luò),使用模型重建正常的時(shí)間序列,使用重建誤差檢測異常.編碼器學(xué)習(xí)一個(gè)向量表示一個(gè)時(shí)間序列,而一個(gè)解碼器則表示重建一個(gè)時(shí)間序列,該模型的訓(xùn)練只能使用正常的時(shí)間序列數(shù)據(jù).該方法可以適用于多傳感器的時(shí)間序列數(shù)據(jù),當(dāng)給出一個(gè)異常序列之后,原有的模型不能很好地重建數(shù)據(jù),這樣會(huì)導(dǎo)致較高的重建誤差,以此來判定異常數(shù)據(jù).圖11 所示為序列數(shù)據(jù)的推斷模型.

Fig.11 Model to predict {x′(1),x′(2),x′(3)} with {x(1),x(2),x(3)}[60]圖11 使用序列數(shù)據(jù){x(1),x(2),x(3)}預(yù)測{x′(1),x′(2),x′(3)}的模型[60]

生成式對(duì)抗網(wǎng)絡(luò)(generative adversarial network,簡稱GAN)可以對(duì)現(xiàn)實(shí)世界復(fù)雜的高維數(shù)據(jù)進(jìn)行建模,一些算法將GAN 應(yīng)用于網(wǎng)絡(luò)異常檢測領(lǐng)域.當(dāng)前的時(shí)間序列數(shù)據(jù)都是多元數(shù)據(jù),即,在同一個(gè)時(shí)間點(diǎn)同時(shí)有多個(gè)感應(yīng)器檢測到的數(shù)據(jù).Li 等人[61]提出了使用GAN 和LSTM 相結(jié)合的方法進(jìn)行異常檢測,算法將多元數(shù)據(jù)同時(shí)進(jìn)行考慮,針對(duì)很多有監(jiān)督的異常檢測算法采用的是線性映射和轉(zhuǎn)換的無監(jiān)督的異常檢測算法,算法使用非線性轉(zhuǎn)換的方法綜合考慮多個(gè)時(shí)間序列.圖12 所示為模型架構(gòu)圖.

Fig.12 An anomaly detection model based on GAN[61]圖12 基于GAN 的異常檢測模型[61]

圖12 左面部分是一個(gè)典型的GAN,生成器從一個(gè)指定的潛在空間生成一個(gè)假的樣本,并傳遞給判別器.判別器區(qū)分生成樣本的真實(shí)與否,根據(jù)生成的結(jié)果更新判別器和生成器的參數(shù),使得判別器更好地區(qū)分?jǐn)?shù)據(jù)的真實(shí)性.生成器則被訓(xùn)練得盡量能夠騙過判別器,即讓判別器認(rèn)為假的樣本為真.通過足夠多輪的迭代,生成器能夠找到訓(xùn)練序列的潛在分布,判別器則能夠區(qū)分真和假的數(shù)據(jù).圖12 右側(cè)的框架是利用GAN 的生成器與判別器進(jìn)行異常檢測,生成器用來計(jì)算重建的樣本和真實(shí)數(shù)據(jù)之間的殘差,判別器用來計(jì)算判別差.通過實(shí)驗(yàn)驗(yàn)證,算法可有效檢測出網(wǎng)絡(luò)攻擊.

3.4 小結(jié)

動(dòng)態(tài)圖異常檢測是異常檢測的一個(gè)重要領(lǐng)域,本節(jié)將面向動(dòng)態(tài)圖異常檢測的異常類型分成了3 種類型:孤立點(diǎn)或孤立邊的異常檢測、異常群體的檢測、事件的異常檢測.動(dòng)態(tài)圖異常檢測問題常常為任務(wù)驅(qū)動(dòng),不同的應(yīng)用目標(biāo)可以使用不同的方法.如在社交網(wǎng)絡(luò)中,查詢異常的賬號(hào)或用戶行為需要使用個(gè)體異常檢測;金融欺詐中查找異常的時(shí)間節(jié)點(diǎn),需要使用事件異常檢測的方法.

4 面向圖的異常檢測技術(shù)框架與應(yīng)用

4.1 面向圖的異常檢測的關(guān)鍵技術(shù)

圖是一種常用的數(shù)據(jù)結(jié)構(gòu),用來描述實(shí)體和實(shí)體之間的相互關(guān)系.近年來,隨著社交網(wǎng)絡(luò)以及知識(shí)圖譜的推動(dòng),圖數(shù)據(jù)挖掘與圖異常檢測受到廣泛關(guān)注,面向圖的異常檢測也出現(xiàn)了很多新的方法,總體來說會(huì)涉及以下幾個(gè)關(guān)鍵技術(shù)之一.

(1)降維.降維技術(shù)是圖異常檢測的常用技術(shù)之一,這是因?yàn)榻稻S技術(shù)解決了圖異常檢測中的兩大問題:正常數(shù)據(jù)模式提取問題以及高維數(shù)據(jù)計(jì)算復(fù)雜度高的問題.在面向圖的異常檢測中,使用降維技術(shù)提取數(shù)據(jù)的主成分,正常數(shù)據(jù)可以使用主成分加以表示而異常數(shù)據(jù)無法做到,這是使用降維技術(shù)解決該類問題的一種常用思路,如利用自編碼器模型進(jìn)行數(shù)據(jù)重建、使用重建誤差進(jìn)行異常檢測的方法和NMF 方法等等.隨著網(wǎng)絡(luò)規(guī)模的快速膨脹,降維技術(shù)還能提高算法執(zhí)行效率,有利于降低原始數(shù)據(jù)計(jì)算復(fù)雜度.降維技術(shù)主要應(yīng)用于無監(jiān)督異常檢測中.基于矩陣分解的方法和基于張量分解的方法的本質(zhì)都是降維,傳統(tǒng)的降維方法包括MDL 方法與PCA 方法.網(wǎng)絡(luò)嵌入技術(shù)以及當(dāng)前火熱的圖神經(jīng)網(wǎng)絡(luò)技術(shù),也是將高維抽象空間的數(shù)據(jù)映射到低維具象的空間.如利用節(jié)點(diǎn)內(nèi)容相似度進(jìn)行異常檢測,可使用node2vec、LINE、GraRep;利用節(jié)點(diǎn)的結(jié)構(gòu)進(jìn)行異常檢測,可使用struct2ve;利用節(jié)點(diǎn)的附加信息,可使用CANE、CENE 方法;

(2)深度神經(jīng)網(wǎng)絡(luò)模型.該類方法受神經(jīng)網(wǎng)絡(luò)在其他領(lǐng)域取得的成功的啟發(fā),利用了神經(jīng)網(wǎng)絡(luò)和數(shù)據(jù)集訓(xùn)練識(shí)別器.該類方法不需要提取特征,模型會(huì)學(xué)習(xí)數(shù)據(jù)的低維特征和高維特征,并進(jìn)行識(shí)別.圖卷積神經(jīng)網(wǎng)絡(luò)可以直接端到端地分類或回歸.該技術(shù)主要分為兩類:一種是譜圖卷積,在傅里葉域進(jìn)行卷積變換;另一種是空間域卷積,直接在網(wǎng)絡(luò)上進(jìn)行卷積.該類方法主要應(yīng)用于有監(jiān)督的異常檢測中;

(3)預(yù)測模型.該類方法是前面兩種關(guān)鍵技術(shù)的結(jié)合:首先,通過將原始的真實(shí)數(shù)據(jù)輸入到神經(jīng)網(wǎng)絡(luò)中,然后使用神經(jīng)網(wǎng)絡(luò)模型學(xué)習(xí)正常數(shù)據(jù)的潛在規(guī)律,使用學(xué)習(xí)到的模型預(yù)測未來的數(shù)據(jù),并利用預(yù)測誤差的分布規(guī)律或使用判別器判斷異常,如使用LSTM 或GAN 模型進(jìn)行預(yù)測.該類方法主要用于圖異常事件檢測.

4.2 面向圖的異常檢測的常用框架

從給定的原始數(shù)據(jù)中是否包含標(biāo)注數(shù)據(jù)的角度,面向圖的異常檢測可以分為有監(jiān)督的異常檢測方法和無監(jiān)督的異常檢測方法.有監(jiān)督的異常檢測算法的一般框架如圖13 所示.

在有監(jiān)督的圖異常檢測算法中,使用的特征包括數(shù)據(jù)本身的屬性信息(如社交網(wǎng)絡(luò)中節(jié)點(diǎn)的信用等級(jí)、是否認(rèn)證等等)以及圖的特征信息(如節(jié)點(diǎn)的出度、入度、中介中心度等等).

對(duì)于沒有可靠標(biāo)注的數(shù)據(jù)集,使用無監(jiān)督的圖異常檢測技術(shù),算法的一般框架如圖14 所示.

無監(jiān)督的圖異常檢測技術(shù)常使用降維技術(shù),對(duì)原始數(shù)據(jù)降維表示,并使用降維之后的模型表示原始數(shù)據(jù),利用重建誤差進(jìn)行圖異常檢測.常用的圖降維技術(shù)有:

(1)Network embedding 技術(shù).網(wǎng)絡(luò)嵌入技術(shù)的目標(biāo)是學(xué)習(xí)網(wǎng)絡(luò)中節(jié)點(diǎn)的低緯度潛在表示,學(xué)習(xí)到的特征表示可以結(jié)合聚類技術(shù),用于圖異常檢測;

(2)MDL 技術(shù).最小描述長度(MDL)準(zhǔn)則是Rissane 在研究通用編碼時(shí)提出來的,其基本原理是:對(duì)于一組給定的實(shí)例數(shù)據(jù)D,如果要對(duì)其進(jìn)行保存,為了節(jié)省存儲(chǔ)空間,一般采用某種模型對(duì)其進(jìn)行編碼壓縮,然后再保存壓縮后的數(shù)據(jù).所以需要保存的數(shù)據(jù)長度(比特?cái)?shù))等于這些實(shí)例數(shù)據(jù)進(jìn)行編碼壓縮后的長度加上保存模型所需數(shù)據(jù)長度,將該數(shù)據(jù)長度稱為總描述長度.最小描述長度(MDL)原理就是要求選擇總描述長度最小的模型.不失一般性,如果一個(gè)數(shù)據(jù)可以使用一個(gè)模型很好地進(jìn)行壓縮,則為正常數(shù)據(jù),異常數(shù)據(jù)則是那些使得最小描述長度變長的個(gè)體,如Shah 等人[17]的算法使用MDL 檢測具有異常行為的節(jié)點(diǎn),算法支持同質(zhì)網(wǎng)絡(luò)與異質(zhì)網(wǎng)絡(luò).Chakrabarti[18]提出了劃分算法嘗試尋找最好的劃分?jǐn)?shù),使得MDL 編碼整個(gè)網(wǎng)絡(luò)占用存儲(chǔ)空間最小.MDL 技術(shù)能夠用于異常檢測技術(shù),原因是該技術(shù)能夠壓縮表示原始數(shù)據(jù),而異常數(shù)據(jù)的表示需要較高的成本,以此進(jìn)行異常檢測;

(3)圖譜論相關(guān)技術(shù).使用拉普拉斯矩陣表示圖,利用使用特征值和特征向量表示對(duì)原有圖進(jìn)行表示,使用前k個(gè)特征值和特征向量對(duì)原始數(shù)據(jù)降維表示;

(4)張量分解.將一個(gè)張量表示成有限個(gè)秩-張量之和,達(dá)到數(shù)據(jù)降維的目標(biāo);

(5)編碼器-解碼器模型.該模型包含兩部分內(nèi)容:編碼器的作用是將高維的原始數(shù)據(jù)降到低維的結(jié)構(gòu)上表示,解碼器是編碼器的逆過程.編碼器與解碼器之間的隱層是該模型的核心,能夠反映高維原始數(shù)據(jù)的本質(zhì)規(guī)律,確定原始數(shù)據(jù)的維數(shù);

(6)PCA 降維.經(jīng)過特征工程之后的數(shù)據(jù),有很多特征存在線性相關(guān)性,PCA 方法的原理是查找原始數(shù)據(jù)在某一個(gè)維度或者方向上的投影,從而使數(shù)據(jù)在這些方向上投影的方差最大.這些方向包含了更多信息量,從而進(jìn)行數(shù)據(jù)壓縮以及異常數(shù)據(jù)挖掘.PCA 降維的缺點(diǎn)是只能線性降維.

Fig.13 Supervised graph anomaly detection algorithm framework圖13 有監(jiān)督的圖異常檢測算法框架圖

Fig.14 Unsupervised graph anomaly detection algorithm framework圖14 無監(jiān)督的圖異常檢測算法框架圖

4.3 面向圖異常檢測的應(yīng)用

隨著信息化技術(shù)的發(fā)展,人們?cè)絹碓街匾曅畔踩?異常檢測尤其是面向圖的異常檢測一直是學(xué)術(shù)界和工業(yè)界研究的熱點(diǎn).面向圖的異常檢測可以應(yīng)用于社會(huì)生活的各個(gè)領(lǐng)域,如金融、互聯(lián)網(wǎng)安全、社交關(guān)系挖掘、電信詐騙檢測等等.面向圖的異常檢測的應(yīng)用領(lǐng)域主要如下所列.

4.3.1 網(wǎng)絡(luò)入侵檢測

互聯(lián)網(wǎng)將世界上任意角落的兩個(gè)人通過網(wǎng)絡(luò)連接起來,在為人們提供交流工具、為企業(yè)提供合作平臺(tái)的同時(shí),也為網(wǎng)絡(luò)攻擊者提供了攻擊便利.利用圖異常檢測技術(shù),對(duì)正常的網(wǎng)絡(luò)行為和訪問方式建模,可以高效地識(shí)別并阻止網(wǎng)絡(luò)或者系統(tǒng)攻擊(如攻擊者通過0day 漏洞攻擊、DDoS 攻擊、系統(tǒng)提權(quán)攻擊、數(shù)據(jù)訪問惡意攻擊、未授權(quán)訪問系統(tǒng)或者惡意軟件等等).Animesh 等人[3]對(duì)使用異常檢測方法檢測網(wǎng)絡(luò)入侵的類型、檢測框架、方法分類等等進(jìn)行了總結(jié)歸納.Akoglu 等人[62]使用基于圖的異常檢測技術(shù)查找電子郵件通聯(lián)網(wǎng)絡(luò)中的重要節(jié)點(diǎn)與可疑節(jié)點(diǎn).Tong 和Lin[14]的工作可以應(yīng)用于端口掃描檢測以及DDoS 攻擊分析.Yu 等人[63]提出了基于隨機(jī)游走的SybilGuard 算法,可以用于女巫攻擊檢測.Liu[64]等人使用異常檢測技術(shù)檢測軟件漏洞.在點(diǎn)到點(diǎn)網(wǎng)絡(luò)中,女巫攻擊是一種常見的網(wǎng)絡(luò)問題,一個(gè)女巫惡意節(jié)點(diǎn)聲稱自己具有多重身份,可以使存儲(chǔ)在多個(gè)節(jié)點(diǎn)上的文件最后僅存儲(chǔ)在一個(gè)節(jié)點(diǎn)上,節(jié)點(diǎn)的退出導(dǎo)致文件存儲(chǔ)失效.在網(wǎng)絡(luò)中,惡意節(jié)點(diǎn)有很多女巫身份,網(wǎng)絡(luò)中會(huì)存在最小商割,即一部分邊(攻擊者和信任者之間的關(guān)系)的移除,使得網(wǎng)絡(luò)的大部分節(jié)點(diǎn)和剩余節(jié)點(diǎn)是不連通的,而正常的網(wǎng)絡(luò)中不存在這種割.SybilGuard 使用一種隨機(jī)游走的變種算法,在信任節(jié)點(diǎn)上多次重復(fù)執(zhí)行隨機(jī)游走算法,多個(gè)游走路徑的交點(diǎn)到起點(diǎn)之間的節(jié)點(diǎn)是可信任的.這是因?yàn)?通過信任節(jié)點(diǎn)構(gòu)成的路徑會(huì)以較大的概率還在信任區(qū)內(nèi),最后可以找到所有的信任區(qū)節(jié)點(diǎn),從而進(jìn)行女巫攻擊檢測.

4.3.2 電信網(wǎng)絡(luò)異常檢測

對(duì)電信服務(wù)提供者來說,使用基于圖的異常檢測技術(shù),可以對(duì)電信網(wǎng)絡(luò)節(jié)點(diǎn)異常流量進(jìn)行檢測和管理,同時(shí)提高電信網(wǎng)絡(luò)的魯棒性和抗攻擊性,避免骨干節(jié)點(diǎn)的癱瘓而導(dǎo)致整個(gè)網(wǎng)絡(luò)的通信中斷.對(duì)電信服務(wù)使用者來說,圖異常檢測技術(shù)可以識(shí)別通聯(lián)網(wǎng)絡(luò)中的廣告推手、電信網(wǎng)絡(luò)欺詐,查找異常的通聯(lián)時(shí)間節(jié)點(diǎn)以及異常的電話通聯(lián)群組.如:Akoglu 等人[39]使用動(dòng)態(tài)圖異常檢測技術(shù),基于短信收發(fā)網(wǎng)絡(luò),研究個(gè)體異常的時(shí)間周期(如短信接收規(guī)律的改變);Prakash 等人[29]使用譜分析技術(shù)識(shí)別電信網(wǎng)絡(luò)中的群組的變化;Chouiekh 等人[20]使用有監(jiān)督學(xué)習(xí)的方法,利用電話通聯(lián)網(wǎng)絡(luò)中用戶通話的詳細(xì)信息進(jìn)行正常用戶與異常用戶的分類;Prakash[29]使用鄰接矩陣劃分的方法檢測可疑電話行為.

4.3.3 社交網(wǎng)絡(luò)異常檢測

社交網(wǎng)絡(luò)中存在很多通過軟件批量生成的僵尸賬號(hào)以及垃圾信息傳播賬號(hào),該類賬號(hào)可以模擬正常的用戶行為,如發(fā)消息、關(guān)注可信賬號(hào)等.該類賬號(hào)可為某些賬號(hào)提供增粉、廣告推銷、活動(dòng)推廣、虛假商品評(píng)論等等服務(wù),為攻擊者賺取巨大利益,并給正常用戶的賬戶隱私、使用體驗(yàn)等造成威脅.使用圖異常檢測技術(shù)識(shí)別社交網(wǎng)絡(luò)中的異常賬號(hào),是當(dāng)前學(xué)術(shù)界和工業(yè)界一直關(guān)注的熱點(diǎn)問題.

對(duì)于社交網(wǎng)絡(luò)中的異常賬號(hào),Aggarwal[65]提出的 CatchSync 算法利用節(jié)點(diǎn)的結(jié)構(gòu)相似度來加以檢測.CatchSync 的主要思想是:社交網(wǎng)絡(luò)中的異常賬號(hào)有很多同步的行為,如這些可疑節(jié)點(diǎn)需要同時(shí)執(zhí)行某些任務(wù),必須關(guān)注某些指定的賬號(hào).同時(shí),這些節(jié)點(diǎn)的連接特點(diǎn)也不同于網(wǎng)絡(luò)的其他節(jié)點(diǎn).CatchSync 提出了同步度量和正常度度量方法,然后根據(jù)每一個(gè)節(jié)點(diǎn)計(jì)算節(jié)點(diǎn)的同步度與正常度,最后將整個(gè)網(wǎng)絡(luò)圖的同步度和正常度采用圖表方式加以展示.使用基于距離的方法,將偏離大部分節(jié)點(diǎn)的具有較高同步度和較低正常度的節(jié)點(diǎn)認(rèn)定為異常節(jié)點(diǎn).Henderson 提出的Rolx[66]根據(jù)節(jié)點(diǎn)的結(jié)構(gòu)信息給節(jié)點(diǎn)確定一個(gè)角色,如團(tuán)體成員節(jié)點(diǎn)、外圍節(jié)點(diǎn)等,為節(jié)點(diǎn)的分類和節(jié)點(diǎn)相似性計(jì)算提供了新的計(jì)量方法,該方法可用于社交網(wǎng)絡(luò)任務(wù)角色分類.

針對(duì)虛假評(píng)論檢測,圖異常檢測也有很多應(yīng)用.一般商品評(píng)論使用二部圖進(jìn)行網(wǎng)絡(luò)建模,Hooi 等人[67]提出了在二部圖上進(jìn)行異常檢測的算法Fraudar,該算法給出了一個(gè)新的可疑度度量,并給出了在圖中無法檢測異常的理論上限.Akoglu[68]針對(duì)以往的啟發(fā)式算法需要先驗(yàn)知識(shí)的缺點(diǎn)提出無監(jiān)督的方法FRAUDEAGLE,該算法可以用于用戶商品評(píng)價(jià)欺詐檢測,同時(shí)還可以使用網(wǎng)絡(luò)評(píng)論的評(píng)分信息和感情信息.算法包含兩個(gè)步驟:對(duì)用戶進(jìn)行打分和欺詐檢測.算法不使用評(píng)價(jià)的文本語義,只使用評(píng)價(jià)的情感信息,如評(píng)價(jià)是正面的還是負(fù)面的,以此將觀點(diǎn)欺詐問題轉(zhuǎn)換為網(wǎng)絡(luò)分類問題而加以解決.

圖異常檢測技術(shù)還可用于社交網(wǎng)絡(luò)謠言的檢測,如Zhang 等人[23]通過訓(xùn)練的模型來識(shí)別正常的用戶和謠言制造者.

4.3.4 金融異常檢測

金融異常主要是指金融欺詐,主要包括如下幾種類型:(1)偽造身份信息,獲取不當(dāng)利益,或者享受免費(fèi)服務(wù),如使用偽造的標(biāo)識(shí)信息、認(rèn)證信息、地址信息等辦理銀行卡或信息卡,違規(guī)獲取利益;(2)克隆他人信息,獲取他人財(cái)產(chǎn)或享受他人應(yīng)有的服務(wù);(3)捏造信息,通過相關(guān)途徑使非法利益合法,如洗錢行為.圖異常檢測技術(shù)在金融領(lǐng)域有著大量的應(yīng)用,如通過圖中回路識(shí)別洗錢行為、通過圖的對(duì)應(yīng)關(guān)系檢測冒用行為.如:NetProbe 算法[69]使用馬爾可夫隨機(jī)場(MRF)對(duì)用戶和交易進(jìn)行建模并查找欺詐用戶,同時(shí)使用信任傳播算法檢測欺詐者.

本文將圖異常檢測技術(shù)應(yīng)用進(jìn)行了分類匯總,見表1.

Table 1 Summary table of graph anomaly detection technologys’ application表1 圖異常檢測技術(shù)應(yīng)用分類匯總表

4.4 面向圖的異常檢測的數(shù)據(jù)集與評(píng)估方法

4.4.1 面向圖的異常檢測數(shù)據(jù)集類型

面向圖的異常檢測方法需要對(duì)應(yīng)的數(shù)據(jù)集來驗(yàn)證方法的有效性和方法的性能,而在當(dāng)前的研究中,絕大多數(shù)數(shù)據(jù)集都沒有可信的數(shù)據(jù)標(biāo)簽,而且在進(jìn)行異常標(biāo)注任務(wù)時(shí)也具有一定的挑戰(zhàn)性,有監(jiān)督的機(jī)器學(xué)習(xí)算法也難以使用標(biāo)注數(shù)據(jù)進(jìn)行訓(xùn)練.因此,當(dāng)前異常檢測方法數(shù)據(jù)集按照生成方式主要分為如下3 類:(1)按照分布規(guī)律生成的模擬數(shù)據(jù);(2)真實(shí)的數(shù)據(jù)以及模擬數(shù)據(jù)形成的合成數(shù)據(jù);(3)真實(shí)的帶標(biāo)注的數(shù)據(jù).

對(duì)于全部模擬數(shù)據(jù)集,一般使用模擬分布與隨機(jī)生成相結(jié)合的方法,模擬分布規(guī)律形成的數(shù)據(jù)為正常數(shù)據(jù)(如模擬社交網(wǎng)絡(luò)數(shù)據(jù)需要滿足冪律分布規(guī)律),隨機(jī)生成的數(shù)據(jù)為異常數(shù)據(jù).Kagan 等人在文獻(xiàn)[86]中的算法2提出了模擬真實(shí)數(shù)據(jù)分布的算法過程,SNAP 平臺(tái)中也有模擬生成數(shù)據(jù)的具體算法實(shí)現(xiàn).

半合成數(shù)據(jù)集使用真實(shí)數(shù)據(jù)作為正常數(shù)據(jù),使用隨機(jī)生成策略生成數(shù)據(jù)作為異常數(shù)據(jù).真實(shí)帶標(biāo)注的數(shù)據(jù)分為兩種類型:第1 種數(shù)據(jù)類型中包含是否是正常數(shù)據(jù)的標(biāo)識(shí),如信用卡欺詐檢測數(shù)據(jù)集;第2 種數(shù)據(jù)類型為數(shù)據(jù)可通過服務(wù)接口獲取數(shù)據(jù)是否正常的信息,如在社交網(wǎng)絡(luò)異常檢測中,可以通過網(wǎng)絡(luò)爬蟲獲取用戶當(dāng)前狀態(tài),如果用戶主頁無法訪問則用戶為異常用戶,Twitter 和新浪微博的數(shù)據(jù)集都可以采用該方法來進(jìn)行檢測.由于面向圖的異常檢測數(shù)據(jù)集比較多,且很多數(shù)據(jù)集節(jié)點(diǎn)附加數(shù)據(jù)很少,因此我們將常用的圖異常檢測數(shù)據(jù)集的名稱、類型、圖說明信息、節(jié)點(diǎn)數(shù)目、邊數(shù)據(jù)等信息進(jìn)行了總結(jié),并將Twitter 和新浪微博異常賬號(hào)驗(yàn)證代碼一起開源在了https://github.com/lizhong2613/GraphAnomalyDetectionDatasets 上.

圖異常檢測技術(shù)應(yīng)用于不同的領(lǐng)域,所面臨的圖數(shù)據(jù)的模型是不同的,原始數(shù)據(jù)按照模型組成可以分為兩種類型:同質(zhì)網(wǎng)絡(luò)數(shù)據(jù)集與異質(zhì)網(wǎng)絡(luò)數(shù)據(jù)集.異質(zhì)網(wǎng)絡(luò)將原始問題抽象成由不同類型的節(jié)點(diǎn)和不同類型的鏈接構(gòu)成的網(wǎng)絡(luò),同質(zhì)網(wǎng)絡(luò)中節(jié)點(diǎn)的類型和鏈接的類型是相同的.如在Twitter 社交網(wǎng)絡(luò)中,節(jié)點(diǎn)都對(duì)應(yīng)于一個(gè)用戶賬戶,節(jié)點(diǎn)之間的關(guān)系是關(guān)注關(guān)系;而在Yelp 數(shù)據(jù)集中,節(jié)點(diǎn)包含了商品和用戶賬號(hào)兩種類型,賬號(hào)和商品之間的關(guān)系是評(píng)論關(guān)系.

在以往工作中,常用的同質(zhì)網(wǎng)絡(luò)數(shù)據(jù)集主要包括Twitter、新浪微博、Academia.edu、Boys’ Friendship、ArXiv、DBLP 數(shù)據(jù)集.常用的異質(zhì)網(wǎng)絡(luò)數(shù)據(jù)集有Flixster、Yelp、douban 等.

4.4.2 面向圖的異常檢測算法性能評(píng)估方法

面向圖的異常檢測算法的目標(biāo)是,從給定的數(shù)據(jù)集中查找出異常數(shù)據(jù).傳統(tǒng)的圖異常檢測方法側(cè)重于算法的有效性以及算法的時(shí)間復(fù)雜度.由于近年來計(jì)算機(jī)算力的提升以及云計(jì)算等技術(shù)的出現(xiàn),圖異常檢測更加注重算法識(shí)別效果(尤其是神經(jīng)網(wǎng)絡(luò)類算法訓(xùn)練過程需要大量時(shí)間不斷迭代優(yōu)化模型).一般情況下,算法會(huì)給出一個(gè)異常度的定義,每個(gè)節(jié)點(diǎn)或邊按照分類器或可疑度計(jì)算公式獲得可疑度,在用戶給定閾值的情況下,按照降序給出數(shù)據(jù)集中的異常數(shù)據(jù).當(dāng)前,圖的異常檢測算法的評(píng)估利用二分類算法的評(píng)估方法說明算法的性能,主要采用如下指標(biāo).

(1)TPR:在所有實(shí)際為正的樣本中,被正確地判斷為正樣本的比率,該指標(biāo)越高越好;

(2)FPR:在所有實(shí)際為負(fù)的樣本中,被錯(cuò)誤地判斷為正樣本的比率,該指標(biāo)越低越好;

(3)Precision:原本為正例的樣本占預(yù)測為正樣本的比率,該指標(biāo)越高越好;

(4)AUC:AUC 指標(biāo)為ROC 曲線下面積,ROC 曲線由TPR 和FPR 計(jì)算得到,該指標(biāo)越高越好.

4.5 小 結(jié)

本節(jié)從圖異常檢測算法的關(guān)鍵技術(shù)、常用框架分類、詳細(xì)應(yīng)用領(lǐng)域、常用數(shù)據(jù)集以及評(píng)估方法等幾個(gè)角度出發(fā),對(duì)圖異常檢測進(jìn)行歸納整理,便于讀者對(duì)圖異常檢測問題有全面和詳細(xì)的了解.

5 總結(jié)與展望

面向圖的異常檢測是對(duì)圖數(shù)據(jù)進(jìn)行數(shù)據(jù)挖掘的一個(gè)主要應(yīng)用,也一直是學(xué)者們的研究熱點(diǎn).隨著互聯(lián)網(wǎng)的發(fā)展,圖規(guī)模越來越大,復(fù)雜性越來越高,新技術(shù)的發(fā)展也為面向圖的異常檢測提供了理論基礎(chǔ),如張量分解技術(shù)、網(wǎng)絡(luò)嵌入技術(shù)以及圖卷積技術(shù)等.然而,異常類型的不同,使用的方法也不同,達(dá)到的效果也不同,本節(jié)將對(duì)面向圖的異常檢測技術(shù)進(jìn)行總結(jié),并對(duì)未來的發(fā)展方向加以展望.

5.1 面向圖的異常檢測方法分類對(duì)比

異常檢測方法的分類匯總可見表2.

Table 2 Classification summary table of graph anomaly detection technology表2 異常檢測方法分類匯總表

Table 2 Classification summary table of graph anomaly detection technology (Continued)表2 異常檢測方法分類匯總表(續(xù))

5.2 面向圖的異常檢測的挑戰(zhàn)

近年來,面向圖的異常檢測受到了越來越多學(xué)者的關(guān)注,盡管新的研究方法和研究成果不斷涌現(xiàn),當(dāng)前的異常檢測研究還處于學(xué)術(shù)研究階段,面向圖的異常檢測仍然面臨很多挑戰(zhàn),主要如下:

(1)真實(shí)的異常數(shù)據(jù)不夠全面、規(guī)范.很多異常算法能夠查找出與其他大多數(shù)生成形式不同的數(shù)據(jù),但是在諸多應(yīng)用中,很少有確定的異常數(shù)據(jù),并且有標(biāo)注的數(shù)據(jù)少之又少.異常數(shù)據(jù)和噪聲數(shù)據(jù)同時(shí)存在于原始數(shù)據(jù)中,不能有效地使用有監(jiān)督的機(jī)器學(xué)習(xí)方法進(jìn)行模型訓(xùn)練,檢測模型訓(xùn)練難,結(jié)果驗(yàn)證難度大,識(shí)別結(jié)果存在偏差;

(2)算法有效性與算法可擴(kuò)展性的結(jié)合較為困難.隨著通信技術(shù)以及計(jì)算機(jī)技術(shù)的發(fā)展,當(dāng)前網(wǎng)絡(luò)的規(guī)模越來越大,網(wǎng)絡(luò)中的節(jié)點(diǎn)數(shù)以億計(jì),優(yōu)化結(jié)果搜索空間大;并且隨著網(wǎng)絡(luò)的變化,搜索空間呈指數(shù)級(jí)增長,網(wǎng)絡(luò)變化頻率快,異常業(yè)務(wù)場景也具有動(dòng)態(tài)性.如在金融欺詐和網(wǎng)絡(luò)欺詐中,算法并不是一成不變的,隨著模型的升級(jí),欺詐者也會(huì)針對(duì)模型進(jìn)行攻擊,導(dǎo)致模型需要不斷更新,一些傳統(tǒng)的方法無法應(yīng)用于大規(guī)模網(wǎng)絡(luò),甚至于節(jié)點(diǎn)關(guān)系的鄰接矩陣無法加載到內(nèi)存中.算法除了有效性,必須有較好的可擴(kuò)展性和經(jīng)濟(jì)性,可用于大規(guī)模圖計(jì)算;

(3)網(wǎng)絡(luò)內(nèi)容屬性與結(jié)構(gòu)屬性的結(jié)合應(yīng)用.除了網(wǎng)絡(luò)的規(guī)模較大以及變化頻率快的特點(diǎn),網(wǎng)絡(luò)中內(nèi)容的信息也越來越多元化,如社交網(wǎng)絡(luò)中用戶評(píng)論的內(nèi)容、用戶的興趣、用戶的個(gè)人信息、發(fā)表的觀點(diǎn)、所處的地理位置等等,充分利用網(wǎng)絡(luò)的多元信息進(jìn)行異常檢測充滿挑戰(zhàn);

(4)異常檢測的可解釋性.異常檢測模型難以給出異常實(shí)例的根本原因以及異常產(chǎn)生的原因,使用直觀性高、交互性強(qiáng)的工具進(jìn)行輔助,如使用圖表、動(dòng)畫的形式進(jìn)行研判,這方面的工作更少.

5.3 展望

綜上所述,圖異常檢測問題的建模與應(yīng)用得到了學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注,隨著云計(jì)算、神經(jīng)網(wǎng)絡(luò)的蓬勃發(fā)展,利用強(qiáng)大的計(jì)算能力,全面考慮網(wǎng)絡(luò)的結(jié)構(gòu)性信息和內(nèi)容性信息,構(gòu)建智能化的異常檢測模型的需求越來越強(qiáng)烈.尤其是異常檢測根據(jù)不同的應(yīng)用領(lǐng)域,采用的模型和方法差異性大、業(yè)務(wù)導(dǎo)向性強(qiáng)、模型不確定性強(qiáng)等諸多挑戰(zhàn)將推動(dòng)異常檢測的研究向縱深方向不斷發(fā)展.未來的研究方向主要包括以下幾個(gè)方面.

(1)結(jié)合自然語言處理技術(shù),全面融合網(wǎng)絡(luò)的結(jié)構(gòu)信息、標(biāo)簽信息和內(nèi)容信息,構(gòu)建充分利用多維度信息的異常檢測方法.當(dāng)前的異常檢測方法主要利用了節(jié)點(diǎn)或邊的結(jié)構(gòu)信息和屬性信息,只是利用了部分特征信息,但只有很少的工作會(huì)考慮內(nèi)容信息.如隨著社交網(wǎng)絡(luò)、電商平臺(tái)的發(fā)展,網(wǎng)絡(luò)承載的觀點(diǎn)也越來越多.如何充分利用內(nèi)容信息,結(jié)合越來越成熟的自然語言處理技術(shù),或者是圖神經(jīng)網(wǎng)絡(luò)技術(shù),將是未來的發(fā)展方向;

(2)自動(dòng)化特征提取技術(shù)與異常檢測的結(jié)合.現(xiàn)有的一些異常檢測方法利用專家知識(shí),通過大量的數(shù)據(jù)分析提取網(wǎng)絡(luò)特征,分析研判異常數(shù)據(jù)與正常數(shù)據(jù)的特征實(shí)現(xiàn)異常檢測.該方法規(guī)范性差,效率低.利用深度神經(jīng)網(wǎng)絡(luò),自動(dòng)提取網(wǎng)絡(luò)低維度特征與高維特征,構(gòu)建識(shí)別器或者異常檢測輔助工具,將是未來的發(fā)展方向;

(3)圖異常檢測的可解釋性研究.目前,對(duì)各種異常檢測方法的可解釋性工作是相當(dāng)少的,除了以往基于特征的異常檢測方法外,其他方法側(cè)重于算法的高效性和可擴(kuò)展性上的比較;而且實(shí)際生活中,真正的異常數(shù)據(jù)本來就很難獲取.未來的研究可以利用更加泛化的異常描述方法,解釋異常實(shí)例的特殊性成因,并結(jié)合可視化技術(shù),讓分析結(jié)果更加清晰;

(4)模型訓(xùn)練優(yōu)化以及預(yù)測結(jié)果優(yōu)化.未來的異常檢測模型能夠利用的特征與信息會(huì)很多,結(jié)果的準(zhǔn)確率也會(huì)越來越高,模型訓(xùn)練和模型調(diào)參的時(shí)間成本將會(huì)不斷增加.如何利用精簡模型獲取較高的模型性能,或者利用網(wǎng)絡(luò)壓縮的方法提高算法的效率,是下一步的研究方向.