陳波馮 李靖東 盧興見(jiàn) 沙朝鋒 王曉玲 張 吉

1(華東師范大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 上海 200062)

2(復(fù)旦大學(xué)計(jì)算機(jī)科學(xué)技術(shù)學(xué)院 上海 200433)

3(之江實(shí)驗(yàn)室 杭州 310000)

圖作為一種通用的數(shù)據(jù)結(jié)構(gòu)，被廣泛用于表示復(fù)雜的結(jié)構(gòu)化數(shù)據(jù).相對(duì)于其他數(shù)據(jù)結(jié)構(gòu)，它能更好地存儲(chǔ)和表達(dá)實(shí)體及其聯(lián)系.現(xiàn)實(shí)世界中，圖在社交網(wǎng)絡(luò)分析、Web網(wǎng)絡(luò)分析、交通路網(wǎng)優(yōu)化、知識(shí)圖譜構(gòu)建等領(lǐng)域均有廣泛的應(yīng)用.針對(duì)這些語(yǔ)義豐富、樣式多樣、規(guī)模龐大的圖數(shù)據(jù)，如何快速、準(zhǔn)確地檢測(cè)其中的異常引起了學(xué)術(shù)界和產(chǎn)業(yè)界的廣泛關(guān)注.圖異常檢測(cè)是指在一個(gè)大圖或海量圖數(shù)據(jù)庫(kù)中尋找包含“陌生”或者“不尋?！蹦Ｊ降慕Y(jié)構(gòu)(包括節(jié)點(diǎn)、邊或者子圖)，具有廣泛的應(yīng)用場(chǎng)景，例如英特網(wǎng)中的惡意攻擊、社交網(wǎng)絡(luò)中的突發(fā)事件檢測(cè)、電子商務(wù)中的水軍發(fā)現(xiàn)等.相較于傳統(tǒng)的異常檢測(cè)方法，基于圖的異常檢測(cè)由于圖具有強(qiáng)大的表達(dá)能力，不僅可以將復(fù)雜的數(shù)據(jù)加以直觀的呈現(xiàn)，同時(shí)也能將數(shù)據(jù)中隱含的相關(guān)性融入到異常檢測(cè)過(guò)程中.

面向圖的異常檢測(cè)工作最早發(fā)表于2003年[1]，現(xiàn)有工作大致可分為基于靜態(tài)圖和基于動(dòng)態(tài)圖2類.在基于靜態(tài)圖的異常檢測(cè)工作中，一類方法利用ego網(wǎng)絡(luò)[2]或者基于團(tuán)體[3]研究問(wèn)題；一類方法基于圖的結(jié)構(gòu)信息進(jìn)行異常檢測(cè)[4-6]，也有一些工作基于子空間選擇，試圖在節(jié)點(diǎn)特征的子空間中發(fā)現(xiàn)異常[7-9].還有一些工作通過(guò)概率、統(tǒng)計(jì)方法獲取圖的統(tǒng)計(jì)信息進(jìn)行異常檢測(cè)[10-13].盡管這些工作在異常檢測(cè)上取得了不錯(cuò)的進(jìn)展，但這些方法如利用ego網(wǎng)絡(luò)的方法，由于處理圖數(shù)據(jù)，必須考慮節(jié)點(diǎn)之間的交互，在圖較為稀疏時(shí)難以實(shí)現(xiàn)較好的效果；或者如子空間選擇和統(tǒng)計(jì)方法，由于淺層學(xué)習(xí)機(jī)制難以綜合利用節(jié)點(diǎn)的屬性和結(jié)構(gòu)信息.在基于動(dòng)態(tài)圖的異常檢測(cè)方面，同樣有一些工作基于團(tuán)體[14-15]、基于結(jié)構(gòu)[6,16]、或基于概率統(tǒng)計(jì)[17-19]進(jìn)行異常檢測(cè).另外一類典型的方法是首先獲取圖的概要，然后通過(guò)聚類和異常檢測(cè)來(lái)確定概要中的異常，例如文獻(xiàn)[20-21]，但是這些方法獲得的概要無(wú)法保留重要的結(jié)構(gòu)信息，比如鄰接節(jié)點(diǎn)的信息.現(xiàn)有的基于動(dòng)態(tài)圖的異常檢測(cè)方法大多依賴于啟發(fā)式規(guī)則，通常只是簡(jiǎn)單地考慮某一類特征；雖然有部分方法[22-23]考慮了內(nèi)容甚至?xí)r間因素，但并不靈活，導(dǎo)致其應(yīng)用局限于特定的場(chǎng)景.

近年來(lái)，深度學(xué)習(xí)成為人工智能和機(jī)器學(xué)習(xí)中極為重要的部分，在提取數(shù)據(jù)中潛在復(fù)雜模式方面表現(xiàn)出優(yōu)越的性能，并在音頻、圖像和自然語(yǔ)言處理等領(lǐng)域得到了廣泛應(yīng)用.深度學(xué)習(xí)方法能夠合理處理復(fù)雜的屬性信息，并且可以從數(shù)據(jù)中學(xué)習(xí)隱含的規(guī)律；此外，通過(guò)神經(jīng)網(wǎng)絡(luò)對(duì)圖進(jìn)行嵌入不僅可以很好地保留信息[24-26]，還可以很好地處理節(jié)點(diǎn)或邊的屬性，同時(shí)保留結(jié)構(gòu)信息，進(jìn)而方便檢查隱空間中節(jié)點(diǎn)或邊表示的相似性.近年來(lái)隨著對(duì)圖進(jìn)行嵌入表示取得顯著進(jìn)展，如何利用深度學(xué)習(xí)方法進(jìn)行圖異常檢測(cè)在過(guò)去幾年中吸引了廣泛關(guān)注.基于深度學(xué)習(xí)的圖異常檢測(cè)方法通常使用圖的嵌入表示方法先將圖表示為隱空間中的向量，然后使用該向量重構(gòu)圖從而剔除異常信息的影響，最后通過(guò)重構(gòu)誤差進(jìn)行異常檢測(cè).

關(guān)于異常和離群點(diǎn)檢測(cè)，已經(jīng)存在非常全面的綜述類文章，例如Zimek等人[27]重點(diǎn)介紹了關(guān)于高維離群值檢測(cè)，Schubert等人[28]討論了局部離群值檢測(cè)技術(shù).但是，這些文章通常關(guān)注多維數(shù)據(jù)實(shí)例的點(diǎn)，沒(méi)有或者不是直接地關(guān)注基于圖的檢測(cè)技術(shù).盡管文獻(xiàn)[29]從圖的角度對(duì)異常檢測(cè)技術(shù)進(jìn)行了調(diào)研，但是缺少對(duì)深度學(xué)習(xí)技術(shù)下的圖異常檢測(cè)技術(shù)的關(guān)注.與以往關(guān)于異常檢測(cè)的綜述不同，本文專注于大圖或海量圖數(shù)據(jù)庫(kù)中的異常檢測(cè)，并對(duì)基于深度學(xué)習(xí)的圖異常檢測(cè)技術(shù)進(jìn)行全面地梳理和總結(jié)，是最早聚焦基于深度學(xué)習(xí)的圖異常檢測(cè)技術(shù)方面的研究綜述.

本文首先對(duì)圖上的異常定義做了全面的分析，然后詳細(xì)介紹了基于深度神經(jīng)網(wǎng)絡(luò)的圖表示學(xué)習(xí)方法，接著從靜態(tài)圖和動(dòng)態(tài)圖的角度出發(fā)，對(duì)現(xiàn)有基于深度學(xué)習(xí)的圖異常檢測(cè)方法進(jìn)行系統(tǒng)地總結(jié)和歸類，并討論相關(guān)方法的局限性.接著簡(jiǎn)單介紹圖異常檢測(cè)技術(shù)的實(shí)際應(yīng)用場(chǎng)景和相關(guān)的數(shù)據(jù)集，最后討論基于深度學(xué)習(xí)的圖異常檢測(cè)研究面臨的挑戰(zhàn)及未來(lái)可行的研究方向.本文期望通過(guò)對(duì)目前基于深度學(xué)習(xí)的圖異常檢測(cè)研究現(xiàn)狀的梳理，為后續(xù)研究提供可借鑒的思路.

1 圖上的異常定義

關(guān)于圖上的異常目前還沒(méi)有統(tǒng)一的定義，并且異常通常跟應(yīng)用領(lǐng)域或場(chǎng)景相關(guān)，本文分別從靜態(tài)圖和動(dòng)態(tài)圖的角度出發(fā)，梳理并總結(jié)了常見(jiàn)的圖上的異常定義.

1.1 靜態(tài)圖上的異常定義

靜態(tài)圖上的異常通常是指圖中很少的或者與觀察到的模式有明顯偏差的節(jié)點(diǎn)、邊或子圖.下面將根據(jù)結(jié)構(gòu)、屬性及其組合對(duì)靜態(tài)圖上的異常進(jìn)行定義.

1) 靜態(tài)圖上的結(jié)構(gòu)異常

① 節(jié)點(diǎn)與節(jié)點(diǎn)之間：給定一個(gè)圖G，如果在屬性不相符的節(jié)點(diǎn)之間有邊連接，則定義該邊為異常邊.例如在DBLP數(shù)據(jù)集中，節(jié)點(diǎn)代表作者信息，來(lái)自2個(gè)不同領(lǐng)域的作者擁有完全不符的屬性信息，突然合作發(fā)了一篇文章[30]，因此產(chǎn)生連接的邊被定義為異常邊.

② 節(jié)點(diǎn)與子圖之間：給定一個(gè)圖G和其中的節(jié)點(diǎn)v，v在屬性上屬于一個(gè)社區(qū)(社區(qū)內(nèi)的節(jié)點(diǎn)擁有相似的屬性信息)，如果v和屬于其他社區(qū)的節(jié)點(diǎn)有邊相連，那么定義該節(jié)點(diǎn)為異常節(jié)點(diǎn)，如圖1(a)所示，其中較大的圓形和矩形分別表示異常節(jié)點(diǎn)及對(duì)應(yīng)的屬性，不同顏色表示不同社區(qū)，2個(gè)節(jié)點(diǎn)之間的箭頭表示邊的連接，2個(gè)屬性之間的箭頭表示某種度量下的相似性[31].圖1(a)中較大的紅色圓形節(jié)點(diǎn)在屬性上與大量紅色矩形相連，說(shuō)明該節(jié)點(diǎn)在屬性上屬于紅色社區(qū)，在結(jié)構(gòu)上卻與較多的其他社區(qū)節(jié)點(diǎn)相連，因此該節(jié)點(diǎn)被定義為異常節(jié)點(diǎn).

③ 子圖與子圖之間：給定一個(gè)圖G，可基于子圖與子圖之間的關(guān)系來(lái)發(fā)現(xiàn)異常，主要有2種情況：Ⅰ.Perozzi 等人[2]通過(guò)對(duì)子圖的質(zhì)量進(jìn)行定義，從而將質(zhì)量低的子圖定義為異常.質(zhì)量高的子圖其內(nèi)部節(jié)點(diǎn)緊密地相互連接，并且在屬性上較為相似；子圖之間區(qū)分明顯，即子圖與子圖只有很少的邊相連，或者即使相連，它們?cè)趯傩陨系牟町愐埠艽?Ⅱ.文獻(xiàn)[1]中定義包含較少常見(jiàn)模式(提前確定)的子圖為異常子圖.

2) 靜態(tài)圖上的屬性異常

給定一個(gè)圖G和其中的節(jié)點(diǎn)v，v在結(jié)構(gòu)上屬于一個(gè)社區(qū)，如果v和大量屬于其他社區(qū)的節(jié)點(diǎn)的屬性相似，那么這種異?？梢远x為屬性上的異常，如圖1(b)所示，較大的紅色圓形節(jié)點(diǎn)與大量紅色節(jié)點(diǎn)相連，說(shuō)明該節(jié)點(diǎn)在結(jié)構(gòu)上屬于紅色社區(qū)，在屬性上較大的紅色矩形卻與較多的其他社區(qū)屬性相連，因此被定義為屬性異常節(jié)點(diǎn).

Fig. 1 Example of anomaly definition on static graph圖1 靜態(tài)圖上異常定義的示例[31]

3) 靜態(tài)圖上結(jié)構(gòu)和屬性的聯(lián)合異常

給定一個(gè)圖G和其中的節(jié)點(diǎn)v，v在結(jié)構(gòu)上屬于一個(gè)社區(qū)A，在屬性上屬于不同于A的社區(qū)B，那么這種異常可以定義為結(jié)構(gòu)和屬性的聯(lián)合異常，也稱為社區(qū)異常，如圖1(c)所示，較大的紅色圓形節(jié)點(diǎn)與大量綠色節(jié)點(diǎn)相連，屬于綠色社區(qū)A，在屬性上與大量藍(lán)色屬性相連，屬于藍(lán)色社區(qū)B，該節(jié)點(diǎn)在屬性和結(jié)構(gòu)上分別屬于不同的社區(qū)，因此被定義為結(jié)構(gòu)和屬性的聯(lián)合異常.

基于1)2)3)中異常定義，我們給出了靜態(tài)圖下異常檢測(cè)任務(wù)形式化定義.

靜態(tài)圖異常檢測(cè)：給定靜態(tài)圖G，靜態(tài)圖異常檢測(cè)任務(wù)的目標(biāo)是找到圖G中不尋常的模式(結(jié)構(gòu)異常模式，屬性異常模式，聯(lián)合異常模式).

1.2 動(dòng)態(tài)圖上的異常定義

對(duì)于一個(gè)隨時(shí)間變化的動(dòng)態(tài)圖，圖中可能會(huì)有新的節(jié)點(diǎn)或邊的增加和刪除，從而引起圖結(jié)構(gòu)和屬性的動(dòng)態(tài)變化，可能會(huì)出現(xiàn)異常.動(dòng)態(tài)圖上的異常通常是導(dǎo)致變化或事件發(fā)生的topk個(gè)節(jié)點(diǎn)、邊或子圖.

1) 基于結(jié)構(gòu)變化的異常

基于社區(qū)的方法特別適合用于動(dòng)態(tài)圖結(jié)構(gòu)的變化分析，因?yàn)樯鐓^(qū)具有總結(jié)圖網(wǎng)絡(luò)結(jié)構(gòu)的能力.Chen等人[32]定義了圖2中6種社區(qū)變化的異常，一般情況下穩(wěn)定的社區(qū)不會(huì)隨時(shí)間而改變，在連續(xù)的圖快照之間發(fā)生以下改變可認(rèn)為圖結(jié)構(gòu)發(fā)生了異常.

Fig. 2 Six possible community-based structural abnormalities in the evolutionary network[32]圖2 進(jìn)化網(wǎng)絡(luò)中6種可能的基于社區(qū)的結(jié)構(gòu)異常類型[32]

① 生長(zhǎng)的社區(qū)：隨時(shí)間的推移，快照t處的社區(qū)中新增了一些成員，從較小的社區(qū)發(fā)展成快照t+1中的一個(gè)大型社區(qū)，例如社區(qū)2.

② 收縮的社區(qū)：先前的更大社區(qū)失去一些成員收縮成更小的社區(qū)，例如社區(qū)4.

③ 合并的社區(qū)：快照t處的2個(gè)或多個(gè)小社區(qū)合并組成的社區(qū)，例如快照t+1處的社區(qū)7.

④ 劃分社區(qū)：快照t處的社區(qū)可能會(huì)在快照t+1處分成多個(gè)社區(qū)，例如社區(qū)8.

⑤ 新生的社區(qū)：在某些快照中可能會(huì)出現(xiàn)新的社區(qū)，例如社區(qū)11.

⑥ 消失的社區(qū)：在某些快照中一些舊社區(qū)可能會(huì)消失，例如社區(qū)12.

2) 基于屬性變化的異常

基于節(jié)點(diǎn)的屬性特征為每個(gè)快照創(chuàng)建一個(gè)“good summary”，計(jì)算不同時(shí)刻圖快照之間的距離，設(shè)定超過(guò)某個(gè)閾值時(shí)，將相應(yīng)時(shí)序圖快照標(biāo)記為異常.在不同場(chǎng)景和算法中，構(gòu)建“good summary”的方法以及使用的距離可以進(jìn)行不同的定義.其中Akoglu等人[33]提出，如果某個(gè)節(jié)點(diǎn)的“行為”偏離其過(guò)去的“正常行為”，則該節(jié)點(diǎn)在某個(gè)時(shí)間范圍內(nèi)是異常的.

3) 基于結(jié)構(gòu)和屬性變化的異常

在隨時(shí)間演變的大圖中，Wang等人[34]對(duì)節(jié)點(diǎn)屬性和圖結(jié)構(gòu)信息進(jìn)行建模，如果一個(gè)節(jié)點(diǎn)的屬性在時(shí)刻t不遵循其自身的歷史行為模式且它所在的社區(qū)路徑顯示異常活動(dòng)或不遵循其所屬社區(qū)的模式，則認(rèn)為該節(jié)點(diǎn)在時(shí)間t是異常的.

基于1)2)3)中異常定義，我們給出了動(dòng)態(tài)圖下異常檢測(cè)任務(wù)形式化定義.

動(dòng)態(tài)圖異常檢測(cè)：給定動(dòng)態(tài)圖Gd={G1,G2,G3,…,Gt}，Gt代表時(shí)刻t下的圖信息，動(dòng)態(tài)圖異常檢測(cè)任務(wù)的目標(biāo)是找到動(dòng)態(tài)圖Gd中導(dǎo)致異常(基于結(jié)構(gòu)變化的異常，基于屬性變化的異常，基于結(jié)構(gòu)和屬性變化的異常)發(fā)生的節(jié)點(diǎn)，邊或者子圖.

1.3 異常檢測(cè)評(píng)價(jià)指標(biāo)

屬性圖中異常節(jié)點(diǎn)的數(shù)量遠(yuǎn)小于所有節(jié)點(diǎn)的數(shù)量，因此無(wú)法使用傳統(tǒng)分類任務(wù)中的評(píng)估指標(biāo)(例如精度和準(zhǔn)確度)很好地評(píng)估異常檢測(cè)任務(wù)的性能.例如學(xué)習(xí)一個(gè)把所有實(shí)例預(yù)測(cè)為正常的模型會(huì)得到一個(gè)很好的性能指標(biāo)表現(xiàn)，但是，該模型無(wú)法檢測(cè)到任何異常.曲線下面積(AUC)可以測(cè)量實(shí)例之間的相對(duì)關(guān)系，并且可以測(cè)量模型把異常實(shí)例排在正常實(shí)例前面的概率，這滿足了我們?cè)诋惓z測(cè)任務(wù)中尋找最佳可能異常實(shí)例的需求，因此各種實(shí)驗(yàn)中通常將AUC作為評(píng)估指標(biāo).此外，由于現(xiàn)實(shí)生活中錯(cuò)誤識(shí)別異常具有很高代價(jià)，往往想要找到異?？赡苄宰罡叩膶?shí)例，因此異常檢測(cè)任務(wù)中也通常將召回率(Recall)作為評(píng)價(jià)指標(biāo)，即選取異?？赡苄宰罡叩牟糠止?jié)點(diǎn)，將檢測(cè)到的異常占所有異常的比例作為評(píng)價(jià)指標(biāo).

2 基于深度神經(jīng)網(wǎng)絡(luò)的圖表示學(xué)習(xí)

進(jìn)行異常檢測(cè)等圖分析研究的一個(gè)關(guān)鍵問(wèn)題是如何合理地表示圖中的特征信息，如何將圖映射到低維向量空間，在保持原始圖結(jié)構(gòu)的同時(shí)支持推理的圖表示學(xué)習(xí)研究引起了學(xué)術(shù)界和產(chǎn)業(yè)界的廣泛關(guān)注.此外，由于節(jié)點(diǎn)的嵌入表示可以用于異常檢測(cè)算法的輸入，支持異常檢測(cè)任務(wù)，因此，圖表示學(xué)習(xí)方法在圖異常檢測(cè)領(lǐng)域具有重要作用.

在傳統(tǒng)的圖表示學(xué)習(xí)方法中，基于因子分解的方法以矩陣的形式表示節(jié)點(diǎn)之間的連接，并將該矩陣因子分解以獲得節(jié)點(diǎn)的嵌入表示向量.例如LLE算法[35]假設(shè)每個(gè)節(jié)點(diǎn)的嵌入表示都是其在嵌入空間中鄰居節(jié)點(diǎn)的嵌入向量表示的線性組合，Laplacian Eigenmaps算法[36]相比于LLE算法來(lái)說(shuō)考慮了節(jié)點(diǎn)之間的權(quán)重.DeepWalk算法[37]第一次將深度學(xué)習(xí)技術(shù)引入到圖表示學(xué)習(xí)領(lǐng)域，node2vec[38]采用了帶有偏向的隨機(jī)游走來(lái)學(xué)習(xí)圖中節(jié)點(diǎn)的嵌入表示.上述方法雖然可以學(xué)到圖中的節(jié)點(diǎn)表示，但大部分都是基于線性或淺層神經(jīng)網(wǎng)絡(luò)的表示，而現(xiàn)實(shí)世界中節(jié)點(diǎn)之間往往存在著非線性關(guān)系.由于深度神經(jīng)網(wǎng)絡(luò)模型在提取數(shù)據(jù)中潛在的復(fù)雜模式方面表現(xiàn)出極為優(yōu)越的性能，因此越來(lái)越多的基于深度神經(jīng)網(wǎng)絡(luò)的方法應(yīng)用于圖的表示學(xué)習(xí)任務(wù).

2.1 圖神經(jīng)網(wǎng)絡(luò)模型及應(yīng)用

圖神經(jīng)網(wǎng)絡(luò)的概念在文獻(xiàn)[39]中首次提出，它拓展了現(xiàn)有的深度神經(jīng)網(wǎng)絡(luò)模型，用于處理以圖的形式表示的數(shù)據(jù).圖神經(jīng)網(wǎng)絡(luò)的目標(biāo)是學(xué)習(xí)一個(gè)包含每個(gè)節(jié)點(diǎn)鄰居信息的嵌入表示向量，以方便執(zhí)行節(jié)點(diǎn)標(biāo)簽分類、鏈接預(yù)測(cè)、異常檢測(cè)等任務(wù).圖神經(jīng)網(wǎng)絡(luò)被廣泛應(yīng)用于圖分析和挖掘領(lǐng)域，例如Battaglia等人[40]在物理系統(tǒng)領(lǐng)域?qū)?duì)象和關(guān)系的相關(guān)作用建模成圖結(jié)構(gòu)，通過(guò)輸入到圖神經(jīng)網(wǎng)來(lái)對(duì)圖網(wǎng)絡(luò)結(jié)構(gòu)中各種物理系統(tǒng)進(jìn)行預(yù)測(cè)和推斷；Schlichtkrull等人[41]將知識(shí)圖譜中的關(guān)系建模成圖結(jié)構(gòu)，然后利用圖神經(jīng)網(wǎng)絡(luò)對(duì)邊進(jìn)行預(yù)測(cè)，從而完成知識(shí)圖譜中的鏈接補(bǔ)全等任務(wù).

圖卷積神經(jīng)網(wǎng)絡(luò)旨在將卷積推廣到圖領(lǐng)域，現(xiàn)有的圖卷積神經(jīng)網(wǎng)絡(luò)分為譜方法和空間方法兩大類.基于譜方法的圖卷積神經(jīng)網(wǎng)絡(luò)[42-43]利用卷積定理在每一層定義圖卷積算子，在損失函數(shù)指導(dǎo)下通過(guò)梯度反向回傳學(xué)習(xí)卷積核，并堆疊多層組成神經(jīng)網(wǎng)絡(luò).基于空間方法的圖卷積神經(jīng)網(wǎng)絡(luò)[44]基本思想是利用圖上的信息傳播機(jī)制，通過(guò)信息構(gòu)造、鄰居聚集、表示更新3個(gè)步驟使用上一時(shí)刻相鄰節(jié)點(diǎn)的狀態(tài)信息.在圖異常檢測(cè)領(lǐng)域，Ding等人[45]將圖卷積神經(jīng)網(wǎng)絡(luò)當(dāng)作編碼器用于捕捉網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點(diǎn)屬性之間的復(fù)雜交互，獲得節(jié)點(diǎn)的高質(zhì)量的嵌入表示后進(jìn)一步用于異常檢測(cè)任務(wù).

近年來(lái)，隨著注意力機(jī)制在越來(lái)越多的領(lǐng)域取得成功，圖注意力網(wǎng)絡(luò)[46-48]也得到了廣泛的研究和關(guān)注.與以往關(guān)心邊上信息的模型不同，GAT通過(guò)注意力機(jī)制定義聚合函數(shù)，鄰接矩陣僅被用來(lái)定義相關(guān)節(jié)點(diǎn).具體來(lái)說(shuō)，為了獲得節(jié)點(diǎn)更好的特征表示，首先針對(duì)節(jié)點(diǎn)特征做一個(gè)線性變換，再針對(duì)中心節(jié)點(diǎn)i，計(jì)算鄰居節(jié)點(diǎn)j對(duì)節(jié)點(diǎn)i的重要性程度eij，然后通過(guò)softmax函數(shù)歸一化獲得節(jié)點(diǎn)的重要性程度,最后通過(guò)加權(quán)求和的聚集函數(shù)來(lái)獲得節(jié)點(diǎn)的表示.Nathani等人[49]將GAT用作編碼器以捕獲圖結(jié)構(gòu)中具有各種關(guān)系的實(shí)體的多樣性，從關(guān)系里學(xué)習(xí)到實(shí)體新的向量表示后用于鏈接預(yù)測(cè)等下游任務(wù).Wu等人[50]將社會(huì)關(guān)系抽象成圖結(jié)構(gòu)，利用多個(gè)圖注意力網(wǎng)絡(luò)建模不同的社會(huì)關(guān)系從而用于社交推薦任務(wù).在圖異常檢測(cè)方面，F(xiàn)an等人[51]使用GAT捕獲中心節(jié)點(diǎn)不同鄰居之間的重要性程度和網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點(diǎn)屬性之間的復(fù)雜交互，在獲得高質(zhì)量的嵌入表示后將重構(gòu)損失當(dāng)作異常的可能性大小.Ding等人[52]在編碼器和解碼器部分使用了圖注意力網(wǎng)絡(luò)獲得節(jié)點(diǎn)表示后利用二分類的方法對(duì)節(jié)點(diǎn)進(jìn)行異常檢測(cè)，此外，圖注意力網(wǎng)絡(luò)的引入使得模型適用于遞推式異常點(diǎn)檢測(cè).

2.2 基于深度神經(jīng)網(wǎng)絡(luò)的圖表示學(xué)習(xí)方法

由于深度自動(dòng)編碼器具有建模數(shù)據(jù)中非線性結(jié)構(gòu)的能力，因此常被用于各種基于深度神經(jīng)網(wǎng)絡(luò)的表示學(xué)習(xí)任務(wù).最近，SDNE(structural deep network embedding)[53],DNGR(deep neural networks for learning graph representations)[54]、圖自編碼器[55-56]，利用深度自動(dòng)編碼器可以捕捉數(shù)據(jù)非線性關(guān)系的能力來(lái)獲得節(jié)點(diǎn)更好的表示.

SDNE使用深度自動(dòng)編碼器來(lái)保留一階和二階網(wǎng)絡(luò)鄰近度，并通過(guò)共同優(yōu)化一階和二階鄰近度來(lái)學(xué)習(xí)節(jié)點(diǎn)的嵌入表示.DNGR將隨機(jī)測(cè)量與深度自動(dòng)編碼器結(jié)合，采用一種無(wú)監(jiān)督的表示學(xué)習(xí)算法來(lái)學(xué)習(xí)節(jié)點(diǎn)表示，然后對(duì)學(xué)習(xí)的表示利用聚類算法對(duì)節(jié)點(diǎn)進(jìn)行聚類，使用聚類性能來(lái)評(píng)估不同圖上表示學(xué)習(xí)的質(zhì)量.DNGR和SDNE僅考慮與節(jié)點(diǎn)對(duì)之間的連通性有關(guān)的節(jié)點(diǎn)結(jié)構(gòu)信息，忽略了節(jié)點(diǎn)可能包含描述節(jié)點(diǎn)自身屬性的特征信息.而圖自編碼器利用圖神經(jīng)網(wǎng)絡(luò)可以同時(shí)編碼節(jié)點(diǎn)結(jié)構(gòu)信息和屬性信息來(lái)捕捉節(jié)點(diǎn)的更好嵌入表示，它采用傳統(tǒng)的深度自編碼器的架構(gòu)，即由encoder編碼部分和decoder解碼部分構(gòu)成，將通過(guò)encoder后得到的嵌入表示作為節(jié)點(diǎn)的表示.

在圖自編碼器的研究中，Kipf等人[55]使用圖神經(jīng)網(wǎng)絡(luò)作為encoder來(lái)得到節(jié)點(diǎn)的嵌入表示，將圖神經(jīng)網(wǎng)絡(luò)視為一個(gè)以節(jié)點(diǎn)特征和鄰接矩陣為輸入，以節(jié)點(diǎn)的嵌入表示為輸出的函數(shù).在decoder部分，則采用了內(nèi)積來(lái)重構(gòu)原始的圖結(jié)構(gòu).圖注意力自編碼器(GATE)[56]同樣采用了深度自編碼器的架構(gòu).GATE使用GAT作為encoder部分來(lái)得到節(jié)點(diǎn)的嵌入表示.GATE在decoder部分同樣采用了注意力機(jī)制，通過(guò)重構(gòu)原始圖的結(jié)構(gòu)和屬性，從而獲得節(jié)點(diǎn)的嵌入表示向量.

將圖自編碼器用于異常檢測(cè)已有一些探索性的研究，Ding等人[45]將GCN當(dāng)作編碼器用于捕捉網(wǎng)絡(luò)結(jié)構(gòu)和節(jié)點(diǎn)屬性之間的復(fù)雜交互，實(shí)現(xiàn)高質(zhì)量的嵌入表示后將通過(guò)解碼器重構(gòu)的損失大小當(dāng)作異常的可能性大??；Ding等人[52]在編碼器和解碼器部分使用圖注意力網(wǎng)絡(luò)獲得節(jié)點(diǎn)表示，然后利用二分類的方法對(duì)節(jié)點(diǎn)進(jìn)行異常檢測(cè).Fan等人[51]提出的對(duì)偶自動(dòng)編碼器(AnomalyDAE)使用了圖自編碼器的思想，在編碼器部分使用GAT捕獲中心節(jié)點(diǎn)不同鄰居之間的重要性程度和網(wǎng)絡(luò)結(jié)構(gòu)與節(jié)點(diǎn)屬性之間的復(fù)雜交互，獲得高質(zhì)量的嵌入表示后將重構(gòu)損失當(dāng)作異常的可能性大小.

3 基于深度學(xué)習(xí)的圖異常檢測(cè)方法

介紹了靜態(tài)圖和動(dòng)態(tài)圖上的異常檢測(cè)定義，以及基于深度學(xué)習(xí)的圖表示學(xué)習(xí)方法之后，本節(jié)詳細(xì)介紹基于深度學(xué)習(xí)的圖異常檢測(cè)方法及其進(jìn)展.目前具有代表性的基于深度學(xué)習(xí)的圖異常方法如表1所示:

Table 1 Deep Learning Based Graph Anomaly Detection Methods表1 基于深度學(xué)習(xí)的圖異常檢測(cè)方法梳理

3.1 基于深度學(xué)習(xí)的靜態(tài)圖異常檢測(cè)方法

在基于深度學(xué)習(xí)的靜態(tài)圖異常檢測(cè)場(chǎng)景下，由于標(biāo)簽數(shù)據(jù)難以獲得[65]，通常采用無(wú)監(jiān)督或者半監(jiān)督學(xué)習(xí)的方法來(lái)檢測(cè)異常.無(wú)監(jiān)督的深度異常檢測(cè)技術(shù)僅根據(jù)數(shù)據(jù)實(shí)例的內(nèi)在屬性來(lái)檢測(cè)離群值，通常用于未標(biāo)記數(shù)據(jù)樣本的自動(dòng)標(biāo)記.此外，在實(shí)際應(yīng)用中，除了大量未標(biāo)記的樣本之外，還可以訪問(wèn)一小部分已標(biāo)記的樣本，例如某個(gè)領(lǐng)域?qū)＜因?yàn)證為正?；虍惓５膶?shí)例子集，因此半監(jiān)督的學(xué)習(xí)也常用于異常檢測(cè).接下來(lái)本節(jié)將從無(wú)監(jiān)督和半監(jiān)督的角度對(duì)靜態(tài)圖上基于深度學(xué)習(xí)的異常檢測(cè)方法進(jìn)行介紹.

3.1.1 無(wú)監(jiān)督的深度圖異常檢測(cè)方法

目前已有的基于深度學(xué)習(xí)的無(wú)監(jiān)督異常檢測(cè)方法大都采用基于殘差分析的思想，在基于殘差分析的異常檢測(cè)方法中，原始數(shù)據(jù)與估計(jì)數(shù)據(jù)的差距(即重構(gòu)誤差)是顯示數(shù)據(jù)集中實(shí)例異常的有力指標(biāo).具體來(lái)說(shuō)，具有較大重構(gòu)誤差的數(shù)據(jù)實(shí)例更有可能被認(rèn)為是異常，因?yàn)樗鼈兊哪Ｊ矫黠@偏離大多數(shù)情況.在各種基于殘差分析的異常檢測(cè)方法中，深度自編碼實(shí)現(xiàn)了最先進(jìn)的性能[58-59].深度自編碼器是所有無(wú)監(jiān)督的深度學(xué)習(xí)異常檢測(cè)模型的核心，其思想是假定正常的實(shí)例數(shù)目比異常實(shí)例數(shù)目多，深度自編碼器可以記住正常的模式，但不能有效地從低維投影重建這些異常點(diǎn)，因此這些具有較少出現(xiàn)次數(shù)的異常點(diǎn)在通過(guò)自編碼器后往往具有較大的殘差，從而被判別為異常點(diǎn).該類模型的框架如圖3所示，針對(duì)輸入數(shù)據(jù)通過(guò)一個(gè)編碼器(encoder)得到數(shù)據(jù)的隱層表示，然后該表示通過(guò)一個(gè)解碼器(decoder)重構(gòu)輸入數(shù)據(jù)，最后用輸入和重構(gòu)的輸出之間的殘差損失(residual loss)大小作為衡量數(shù)據(jù)異常的指標(biāo).

Fig. 3 Residual analysis based anomaly detection mode圖3 基于殘差分析的異常檢測(cè)模型

在基于殘差分析思想的基礎(chǔ)上，學(xué)者們提出了一系列圖上無(wú)監(jiān)督的異常檢測(cè)方法.

首先，Li等人在文獻(xiàn)[57]中針對(duì)在沒(méi)有先驗(yàn)知識(shí)的情況下，如何表征屬性信息的殘差以發(fā)現(xiàn)異常，以及如何利用屬性殘差和網(wǎng)絡(luò)信息之間的一致性，從而以一般方式識(shí)別異常，提出了異常檢測(cè)框架Radar，進(jìn)而進(jìn)行異常檢測(cè)任務(wù)，通過(guò)學(xué)習(xí)和分析殘差，發(fā)現(xiàn)與大多數(shù)樣本不同的異常行為.最后在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)表明了該殘差分析框架Radar的效性和普遍性.

Bandyopadhyay等人[58]在文獻(xiàn)[31]的基礎(chǔ)上對(duì)異常檢測(cè)的模型進(jìn)行改進(jìn)，提出了DONE和AdONE算法，模型結(jié)構(gòu)如圖4所示，該模型在編碼器和解碼器部分替換了文獻(xiàn)[31]中使用的矩陣分解方法，采用了深度自編碼器來(lái)獲得結(jié)構(gòu)和屬性上的重構(gòu)損失，用于捕捉非線性關(guān)系，同樣利用損失函數(shù)引入了結(jié)構(gòu)上的異常分?jǐn)?shù)O1和屬性上的異常分?jǐn)?shù)O2.在獲得節(jié)點(diǎn)屬性和結(jié)構(gòu)上的低維表示后，使用對(duì)抗學(xué)習(xí)的思想，學(xué)習(xí)社區(qū)異常中的映射矩陣W，讓節(jié)點(diǎn)在屬性和結(jié)構(gòu)上具有一致性，從而獲得社區(qū)角度的混合異常分?jǐn)?shù)O3.

Fig. 4 Model structure of DONE and AdONE[58]圖4 DONE和AdONE模型結(jié)構(gòu)[58]

Liang等人[60]提出在做表示學(xué)習(xí)任務(wù)的過(guò)程中去檢測(cè)異常點(diǎn).文獻(xiàn)[60]采用2個(gè)對(duì)偶深度神經(jīng)網(wǎng)絡(luò)去編碼節(jié)點(diǎn)特征xi和節(jié)點(diǎn)的鄰居特征xNi，獲得編碼后的節(jié)點(diǎn)特征h1(xi)和鄰居節(jié)點(diǎn)特征h1(xNi).然后通過(guò)一個(gè)共享層融合節(jié)點(diǎn)的表示，即ei=λihl1(xi)+ (1-λi)hl1(xNi)，最后通過(guò)有標(biāo)簽的類型數(shù)據(jù)和無(wú)標(biāo)簽的表示學(xué)習(xí)任務(wù)去訓(xùn)練模型，由于異常點(diǎn)往往會(huì)影響表示學(xué)習(xí)的效果，因此通過(guò)將鄰居信息融入到表示學(xué)習(xí)中，可以在表示學(xué)習(xí)任務(wù)中消除異常點(diǎn)的影響，在學(xué)習(xí)節(jié)點(diǎn)良好的嵌入表示的過(guò)程中同時(shí)檢測(cè)出節(jié)點(diǎn)的異常分?jǐn)?shù).

上述介紹的基于深度學(xué)習(xí)的異常檢測(cè)方法往往將節(jié)點(diǎn)的結(jié)構(gòu)和屬性信息分開(kāi)考慮，忽略了兩者之間的某些交互信息，而圖神經(jīng)網(wǎng)絡(luò)可以同時(shí)編碼節(jié)點(diǎn)結(jié)構(gòu)和屬性信息，將結(jié)構(gòu)和屬性信息結(jié)合起來(lái)考慮，可以捕捉到節(jié)點(diǎn)的更好表示.因此，圖神經(jīng)網(wǎng)絡(luò)越來(lái)越多地被用于圖上的異常檢測(cè)領(lǐng)域.接下來(lái)將對(duì)已有的利用圖神經(jīng)網(wǎng)絡(luò)的異常檢測(cè)方法進(jìn)行介紹.

Dominant[45]使用GCN對(duì)屬性網(wǎng)絡(luò)進(jìn)行建模，解決了上述提到的分開(kāi)考慮結(jié)構(gòu)和屬性信息的局限性，當(dāng)處理與經(jīng)過(guò)多層非線性轉(zhuǎn)換的高階節(jié)點(diǎn)交互時(shí)，GCN緩解了網(wǎng)絡(luò)稀疏性的問(wèn)題，可以捕獲數(shù)據(jù)的非線性以及屬性網(wǎng)絡(luò)上2個(gè)信息源之間的復(fù)雜交互.該模型的結(jié)構(gòu)如圖5所示，具體來(lái)說(shuō)，Dominant在自動(dòng)編碼器框架中利用從GCN獲得的節(jié)點(diǎn)嵌入來(lái)重構(gòu)原始的屬性和結(jié)構(gòu)信息.然后，通過(guò)結(jié)構(gòu)上的重構(gòu)誤差和屬性上的重建誤差來(lái)獲得異常分?jǐn)?shù)，并通過(guò)異常分?jǐn)?shù)的排序來(lái)標(biāo)記異常.實(shí)驗(yàn)結(jié)果證明：利用GCN的深度模型Dominant的優(yōu)越性.該方法雖然通過(guò)使用GCN可以很好地捕捉節(jié)點(diǎn)模態(tài)和屬性模態(tài)的良好交互信息，但是該模型的設(shè)計(jì)比較簡(jiǎn)單，只是直接使用了GCN作為編碼器，沒(méi)有考慮到GCN的一些缺點(diǎn)，如平滑問(wèn)題.

Fig. 5 Model structure of Dominant[45]圖5 Dominant模型結(jié)構(gòu)[45]

雖然將深度學(xué)習(xí)當(dāng)作特征抽取工具提取出特征后用作異常檢測(cè)任務(wù)已經(jīng)取得良好效果，但是先進(jìn)行特征抽取然后進(jìn)行異常檢測(cè)的方法很容易導(dǎo)致性能欠佳，因?yàn)榈谝徊降奶卣鞒槿〔恢离S后的異常檢測(cè)任務(wù)，很容易導(dǎo)致異常檢測(cè)任務(wù)的關(guān)鍵信息在第一步已經(jīng)被移除，從而陷入局部最優(yōu)解.因此，Zong等人[66]采用了一種聯(lián)合訓(xùn)練的方法，即將殘差分析的損失與聚類分析的損失聯(lián)合起來(lái)，構(gòu)造一個(gè)統(tǒng)一的損失函數(shù)，利用深度神經(jīng)網(wǎng)絡(luò)技術(shù)去同時(shí)優(yōu)化特征抽取與聚類分析的過(guò)程，從而取得更準(zhǔn)確的異常檢測(cè)結(jié)果.Li等人[59]首次將這種聯(lián)合訓(xùn)練方法用于圖上的異常檢測(cè)，所提模型如圖6所示，在模型左半部分，首先從結(jié)構(gòu)和屬性的角度提取特征，在獲得節(jié)點(diǎn)在結(jié)構(gòu)和屬性上的隱層表示后，拼接其隱層特征后用于高斯密度估計(jì)，最后將特征重構(gòu)的損失和密度估計(jì)的損失采用聯(lián)合訓(xùn)練的方法，位于高斯分布邊緣的節(jié)點(diǎn)具有較高異常分?jǐn)?shù).

Fig. 6 Model structure of SpecAE[59]圖6 SpecAE模型結(jié)構(gòu)[59]

圖上的異常檢測(cè)旨在發(fā)現(xiàn)模式與大多數(shù)參考節(jié)點(diǎn)明顯不同的節(jié)點(diǎn)，但是，現(xiàn)有方法都忽略了圖結(jié)構(gòu)和節(jié)點(diǎn)屬性之間復(fù)雜的跨模態(tài)交互.在文獻(xiàn)[51]中，作者提出了一個(gè)通過(guò)雙自動(dòng)編碼器(AnomalyDAE)進(jìn)行異常檢測(cè)的深度聯(lián)合表示學(xué)習(xí)框架，該框架捕獲了圖結(jié)構(gòu)和節(jié)點(diǎn)屬性之間的跨模態(tài)交互，以實(shí)現(xiàn)高質(zhì)量的嵌入.如圖7所示，AnomalyDAE由結(jié)構(gòu)自編碼器和屬性自編碼器組成，以共同學(xué)習(xí)潛在空間中的節(jié)點(diǎn)嵌入和屬性嵌入.該框架在結(jié)構(gòu)編碼器中通過(guò)采用注意力機(jī)制來(lái)學(xué)習(xí)不同鄰居的重要性，以有效捕獲結(jié)構(gòu)模式，這在異常檢測(cè)中扮演著重要作用.此外，通過(guò)將節(jié)點(diǎn)嵌入和屬性嵌入兩者作為屬性解碼器的輸入，在重建節(jié)點(diǎn)屬性的過(guò)程中學(xué)習(xí)結(jié)構(gòu)和節(jié)點(diǎn)屬性之間的跨模態(tài)交互作用.最后，可以通過(guò)從結(jié)構(gòu)和屬性2個(gè)角度測(cè)量節(jié)點(diǎn)的重構(gòu)誤差來(lái)檢測(cè)異常.

Fig. 7 Model structure of AnomalyDAE[51]圖7 AnomalyDAE 的網(wǎng)絡(luò)結(jié)構(gòu)[51]

Fig. 8 Model structure of AEGIS[52]圖8 AEGIS模型結(jié)構(gòu)[52]

3.1.2 半監(jiān)督的深度圖異常檢測(cè)方法

通常情況下，異常檢測(cè)被當(dāng)作一個(gè)無(wú)監(jiān)督學(xué)習(xí)問(wèn)題來(lái)處理，大多數(shù)現(xiàn)有的方法僅限于包括有標(biāo)簽的正常樣本，只有少數(shù)方法可以利用標(biāo)記的異常，已有的半監(jiān)督的深度異常檢測(cè)方法通常假設(shè)在輸入空間和學(xué)習(xí)到的特征空間中，彼此接近的點(diǎn)更有可能共享相同的標(biāo)簽，在深度神經(jīng)網(wǎng)絡(luò)層的隱藏層中能夠?qū)W習(xí)魯棒特征，保留區(qū)分屬性，用于分離正常點(diǎn)和離群數(shù)據(jù)點(diǎn).

目前只有少數(shù)學(xué)者在圖上利用半監(jiān)督學(xué)習(xí)的方法進(jìn)行檢測(cè)異常任務(wù)，Kumagai等人[61]提出了一種新的半監(jiān)督下同時(shí)考慮圖結(jié)構(gòu)的標(biāo)簽和所有節(jié)點(diǎn)的屬性信息進(jìn)行異常檢測(cè)的深度學(xué)習(xí)方法.在文獻(xiàn)[61]中，為了學(xué)習(xí)有用的節(jié)點(diǎn)嵌入以進(jìn)行異常檢測(cè)，作者提出學(xué)習(xí)一個(gè)超球面，使包圍正常節(jié)點(diǎn)嵌入的超球面的體積最小化，同時(shí)將異常節(jié)點(diǎn)嵌入在超球面之外，當(dāng)要檢測(cè)的節(jié)點(diǎn)屬于學(xué)習(xí)到的最小球半徑之外，則將該數(shù)據(jù)當(dāng)作異常節(jié)點(diǎn).具體來(lái)說(shuō)，該方法首先通過(guò)利用圖卷積神經(jīng)網(wǎng)絡(luò)抽取節(jié)點(diǎn)的嵌入表示H，然后針對(duì)有標(biāo)簽的正常實(shí)例，最小化正常實(shí)例節(jié)點(diǎn)到球中心的距離：

Lnor(θ)

(1)

從而學(xué)習(xí)到一個(gè)包含盡可能多正常樣本的超球.其次，為了更有效地使用異常樣本，考慮正負(fù)樣本不平衡的特性，采用近似AUC的思想[67]：

RAUC(θ)

(2)

其中f是sigmoid函數(shù)，當(dāng)a(vn)?a(vm)時(shí)，f(·)取得較大值；當(dāng)a(vn)?a(vm),f(·)取得較小值，因此最大化式(2)鼓勵(lì)異常節(jié)點(diǎn)的分?jǐn)?shù)值要比正常節(jié)點(diǎn)的分?jǐn)?shù)值高，讓異常節(jié)點(diǎn)距離超球中心c的距離較遠(yuǎn).最后該模型結(jié)合式(1)(2)這2個(gè)損失函數(shù)去優(yōu)化模型參數(shù)，對(duì)剩下的未標(biāo)記樣本執(zhí)行異常檢測(cè)任務(wù):

L(θ)Lnor(θ)-λRAUC(θ).

(3)

通過(guò)在不同比例的有標(biāo)簽數(shù)據(jù)下進(jìn)行實(shí)驗(yàn)證明該方法優(yōu)于已有的異常檢測(cè)方法.

雖然文獻(xiàn)[61]提出的算法在半監(jiān)督的背景下對(duì)圖上節(jié)點(diǎn)進(jìn)行了異常檢測(cè)，但是文獻(xiàn)[61]僅僅使用圖卷積神經(jīng)網(wǎng)絡(luò)去提取特征，沒(méi)有考慮不同的節(jié)點(diǎn)貢獻(xiàn)度以及平滑問(wèn)題; 其次，GCN很難應(yīng)用在超大圖上，每次卷積操作計(jì)算都需要將整個(gè)圖放入到內(nèi)存和顯存，計(jì)算量和內(nèi)存與顯存占用量會(huì)隨著節(jié)點(diǎn)數(shù)的增加而遞增，因此如何針對(duì)大圖進(jìn)行異常檢測(cè)也是半監(jiān)督深度異常檢測(cè)方法未來(lái)的一個(gè)重要研究方向.

3.1.3 靜態(tài)圖上的異常檢測(cè)對(duì)比實(shí)驗(yàn)

為了驗(yàn)證上述基于深度學(xué)習(xí)的靜態(tài)圖異常檢測(cè)方法的有效性，本節(jié)將使用目前已公布源碼的2篇文獻(xiàn)[45,58]的代碼，在公開(kāi)數(shù)據(jù)集上進(jìn)行對(duì)比實(shí)驗(yàn)，以評(píng)估他們?cè)趫D深度異常檢測(cè)方面的效果.使用的數(shù)據(jù)集基本情況如表2所示.由于現(xiàn)有的公開(kāi)數(shù)據(jù)集通常沒(méi)有異常標(biāo)注，我們手動(dòng)將5%的異常(包括結(jié)構(gòu)異常、屬性異常和兩者組合而成的異常)注入到部分公開(kāi)的屬性化網(wǎng)絡(luò)數(shù)據(jù)集中.遵循文獻(xiàn)[31]中使用的策略，以確保注入的異常與實(shí)際異常相接近.異常注入過(guò)程包括：

Table 2 Summary of the Datasets表2 實(shí)驗(yàn)數(shù)據(jù)集信息

1) 計(jì)算每個(gè)類的節(jié)點(diǎn)數(shù)目的概率分布；

2) 用這些概率選擇一個(gè)分類；

3) 對(duì)于結(jié)構(gòu)異常：在所選分類中注入一個(gè)異常節(jié)點(diǎn)，使該節(jié)點(diǎn)具有(m+/-10%)的邊連接其余(未選定)分類的節(jié)點(diǎn)，其中，m是所選分類中節(jié)點(diǎn)的平均度數(shù)；

4) 結(jié)構(gòu)異常的節(jié)點(diǎn)的屬性在語(yǔ)義上與從所選類中采樣得到的關(guān)鍵字一致.

對(duì)于屬性異常(從不同的分類中隨機(jī)抽取屬性)和組合異常(分別從2個(gè)不同的類中采樣邊和屬性)采用了類似的方法.

實(shí)驗(yàn)結(jié)果如圖9所示.Ding等人[45]提出的方法名為Dominant，Bandyopadhyay等人[58]提出了DONE和AdONE兩種方法.屬性網(wǎng)絡(luò)中的離群點(diǎn)檢測(cè)非常重要.DONE和AdONE都會(huì)在節(jié)點(diǎn)embedding過(guò)程中生成異常分值.取3次異常檢測(cè)的加權(quán)平均值作為節(jié)點(diǎn)的異常分值并根據(jù)該分值對(duì)節(jié)點(diǎn)進(jìn)行排序生成排名表L.由于每個(gè)數(shù)據(jù)集中有5%的異常節(jié)點(diǎn)，我們繪制了從排名表(L)中排名前5%到25%的節(jié)點(diǎn)的召回率.圖9的實(shí)驗(yàn)結(jié)果表明DONE的表現(xiàn)在3個(gè)數(shù)據(jù)集上相對(duì)于其他2種方法都要稍差一些，這是由于DONE將屬性和結(jié)構(gòu)分別建模后僅僅使用特征變換矩陣W建模屬性和結(jié)構(gòu)的交互信息，而AdONE和Dominant分別利用了更加復(fù)雜的對(duì)抗訓(xùn)練和圖神經(jīng)網(wǎng)絡(luò)建模交互信息，因此總是相比DONE取得更好的效果.Dominant和AdONE在不同數(shù)據(jù)集上各有優(yōu)勢(shì)，特別地，我們發(fā)現(xiàn)在Citeseer數(shù)據(jù)集上Dominant具有顯著優(yōu)勢(shì)，通過(guò)對(duì)數(shù)據(jù)集的分析發(fā)現(xiàn)，Citeseer數(shù)據(jù)集相比其他數(shù)據(jù)集的特征維度較高并且更加稀疏，這說(shuō)明Dominant利用圖神經(jīng)網(wǎng)絡(luò)同時(shí)建模屬性和結(jié)構(gòu)信息可以處理更加復(fù)雜的數(shù)據(jù)集.實(shí)驗(yàn)表明：目前基于深度學(xué)習(xí)的圖異常檢測(cè)算法已經(jīng)可以取得較好的精確度.

Fig. 9 Experimental results of deep learning based anomaly detection in static graph圖9 基于深度學(xué)習(xí)的靜態(tài)圖異常檢測(cè)實(shí)驗(yàn)結(jié)果

3.2 基于深度學(xué)習(xí)的動(dòng)態(tài)圖異常檢測(cè)方法

本節(jié)重點(diǎn)介紹動(dòng)態(tài)圖上基于深度學(xué)習(xí)的異常檢測(cè)方法，因?yàn)榛谏疃葘W(xué)習(xí)的技術(shù)主要引入了圖上的結(jié)構(gòu)和屬性信息，而這些信息都會(huì)隨時(shí)間發(fā)生變化，所以我們重點(diǎn)介紹因?yàn)闀r(shí)序引發(fā)的圖結(jié)構(gòu)和屬性變化的相關(guān)異常檢測(cè)方法.

3.2.1 基于結(jié)構(gòu)變化的動(dòng)態(tài)圖異常檢測(cè)方法

這類方法的主要思路是：針對(duì)由一系列靜態(tài)圖組成的動(dòng)態(tài)圖，尋找那些時(shí)間點(diǎn)，在這些時(shí)間點(diǎn)上圖發(fā)生了顯著變化或者發(fā)生了異常事件；進(jìn)而，發(fā)現(xiàn)影響最大的節(jié)點(diǎn)、邊或者子圖結(jié)構(gòu).

DPADS[68]算法檢測(cè)圖的異常是和文獻(xiàn)[32]類似的思想：異常的子結(jié)構(gòu)(或子圖)是正常模式的結(jié)構(gòu)變種(正常模式邊和節(jié)點(diǎn)的增加或者缺失).假設(shè)d(G1,G2)表示2個(gè)圖G1和G2之間的結(jié)構(gòu)差異度量，計(jì)算把圖G1轉(zhuǎn)化為G2的同構(gòu)圖的計(jì)算量(添加、刪除點(diǎn)與改變標(biāo)簽的變化數(shù)量)，衡量G1和G2之間的差異.

DPADS算法把靜態(tài)圖上的異常檢測(cè)算法GBAD和并行異常檢測(cè)算法PLAD擴(kuò)展到大規(guī)模動(dòng)態(tài)圖的異常檢測(cè)中，如圖10所示，Ti-1，Ti，Ti+1為時(shí)間滑動(dòng)窗口.本文定義了3種基本類型圖的異常：添加、修改和移除.添加異常是正常模式增加了節(jié)點(diǎn)或邊，修改異常包含了一個(gè)節(jié)點(diǎn)或邊的意外標(biāo)簽，移除異常的子結(jié)構(gòu)比正常子結(jié)構(gòu)缺少了邊或節(jié)點(diǎn).算法的輸入為n個(gè)子圖，這些子圖既可以是靜態(tài)圖的劃分，也可以是時(shí)序圖的一部分.DPADS主要可以分為2個(gè)階段：初始化和迭代處理.其中初始化階段，其主要的目標(biāo)是在n個(gè)子圖中找出正常模式S和與其存在差異的異常模式.這個(gè)階段可以歸納為：

Fig. 10 Diagram of DPADS[68]圖10 DPADS[68]示意圖

1) 并行處理n個(gè)子圖，然后分別檢測(cè)top-M個(gè)正常模式，一共可以得到n×M個(gè)正常模式;

2) 判斷得到正常模式S;

3) 根據(jù)正常模式S得到異常模式結(jié)構(gòu).

迭代處理階段的主要目標(biāo)是迭代分析時(shí)序數(shù)據(jù)的結(jié)構(gòu)異常.

1) 算法把時(shí)間窗口向后移動(dòng)一個(gè)窗口，讓新獲取的子圖包含在滑動(dòng)窗口內(nèi);

2) 在新來(lái)到的子圖中檢測(cè)top-M個(gè)正常模式，從滑動(dòng)窗口中的所有子圖中判斷得到正常模式S′.如果S′=S，那么就只需檢測(cè)新子圖里的異常；否則需要對(duì)窗口里的每個(gè)子圖都基于正常模式S′檢測(cè)異常結(jié)構(gòu);

3) 對(duì)每個(gè)異常子結(jié)構(gòu)計(jì)算R值，值最小的子結(jié)構(gòu)判定為異常結(jié)構(gòu),重復(fù)迭代過(guò)程.

為了減少惡意活動(dòng)的影響并及時(shí)啟動(dòng)恢復(fù)過(guò)程，AnomRank[64]在準(zhǔn)確性和實(shí)時(shí)性做出了改進(jìn)，提出了一種快速準(zhǔn)確的在線算法用于檢測(cè)動(dòng)態(tài)圖中的異常.首先對(duì)異常進(jìn)行分類，如圖11(a)所示，除了像DPADS將節(jié)點(diǎn)的增加或者缺失作為異常外，如圖11(b)所示，AnomRank將連接的節(jié)點(diǎn)之間的邊數(shù)的變數(shù)作為異常，例如惡意的端口攻擊中的頻繁連接.論文基于已有的衡量節(jié)點(diǎn)重要性的PageRank算法，認(rèn)為異常導(dǎo)致節(jié)點(diǎn)分?jǐn)?shù)突然變化.作者首先定義了僅考慮節(jié)點(diǎn)的節(jié)點(diǎn)重要性(ScoreS)和考慮了節(jié)點(diǎn)和邊權(quán)重的節(jié)點(diǎn)重要性(ScoreW)，在此基礎(chǔ)上，作者設(shè)計(jì)了動(dòng)態(tài)的重要性計(jì)算函數(shù)實(shí)現(xiàn)快速計(jì)算，將重要性分?jǐn)?shù)變化大的節(jié)點(diǎn)識(shí)別為異常節(jié)點(diǎn)，從而實(shí)現(xiàn)實(shí)時(shí)的異常檢測(cè).

Fig. 11 Two changes in dynamic graphs: Structure change and edge weight change[64]圖11 動(dòng)態(tài)圖的2種改變: 結(jié)構(gòu)改變和邊權(quán)重改變[64]

Yu等人[62]則是提出了一種基于圖嵌入的動(dòng)態(tài)圖異常檢測(cè)框架NetWalk，提出一種新的基于深度自編碼神經(jīng)網(wǎng)絡(luò)的Clique Embedding方法來(lái)學(xué)習(xí)節(jié)點(diǎn)的向量表示(最小化每個(gè)walk中頂點(diǎn)對(duì)的距離)，這種節(jié)點(diǎn)向量表示方法，可以很好的基于聚類進(jìn)行Clique Embedding異常檢測(cè).同時(shí)為了應(yīng)對(duì)邊異常，還構(gòu)建了一個(gè)查詢表，根據(jù)學(xué)習(xí)的圖表示和阿達(dá)馬變換(Hadamard Transform)對(duì)新的邊進(jìn)行實(shí)時(shí)編碼，這種節(jié)點(diǎn)和邊的編碼方式可以得到“良好的摘要”.網(wǎng)絡(luò)還為每個(gè)頂點(diǎn)維護(hù)了一個(gè)固定大小的蓄水池，用來(lái)解決動(dòng)態(tài)圖的數(shù)據(jù)更新問(wèn)題，文獻(xiàn)[62]中給出了新的邊到來(lái)時(shí)候的3種更新策略，總結(jié)來(lái)說(shuō)就是新的邊到來(lái)時(shí)，會(huì)以P的概率替換水池里存在的頂點(diǎn)，刪除邊的時(shí)候只針對(duì)已經(jīng)刪除了的頂點(diǎn)進(jìn)行替換，然后通過(guò)蓄水池中新的walk來(lái)更新網(wǎng)絡(luò).文中的邊異常判斷是通過(guò)計(jì)算新來(lái)的邊和中心節(jié)點(diǎn)的距離來(lái)確定.

3.2.2 基于屬性變化的動(dòng)態(tài)圖異常檢測(cè)方法

基于特征的異常檢測(cè)方法.這類方法的主要思想是“相似的圖可能共享某些特征”，反過(guò)來(lái)說(shuō)就是指異常結(jié)點(diǎn)(子圖)和其他正常結(jié)點(diǎn)(子圖)的特征存在很大不同，所以這類方法的主要步驟都是：

1) 從輸入圖的每個(gè)快照中，提取關(guān)鍵的特征值來(lái)為每個(gè)快照構(gòu)造“摘要”;

2) 使用距離函數(shù)比較連續(xù)摘要;

3) 當(dāng)距離大于閾值時(shí)，將相應(yīng)摘要定性為異常.

其中不同算法的區(qū)別體現(xiàn)在：

1) 構(gòu)造“圖摘要”的方法不同；

2) 使用的距離或相似度函數(shù)不同；

3) 定義和選擇閾值以將實(shí)例標(biāo)記為異常的方式不同.

其中Akoglu等人[33]提出為每個(gè)快照創(chuàng)建摘要(例如將相關(guān)特征進(jìn)行向量表示)，并使用距離函數(shù)對(duì)摘要進(jìn)行連續(xù)快照比較，2個(gè)快照之間的某個(gè)閾值以上的距離表示它們之間的變化點(diǎn)或異常.算法會(huì)先為圖中所有節(jié)點(diǎn)提取幾個(gè)網(wǎng)絡(luò)特征的時(shí)間序列，再建立一個(gè)相關(guān)矩陣，表示在特定時(shí)間窗口內(nèi)圖中所有節(jié)點(diǎn)對(duì)之間的“行為”相關(guān)性.然后導(dǎo)出所有節(jié)點(diǎn)的“行為”向量，并將其與在多個(gè)先前時(shí)間窗口內(nèi)檢測(cè)到的最近的過(guò)去“行為”的向量進(jìn)行比較.如果發(fā)現(xiàn)當(dāng)前的“行為”與最近的歷史有很大不同，則將當(dāng)前的時(shí)間窗口標(biāo)記為異常.

基于社區(qū)的異常檢測(cè)方法.這類方法的主要思想是時(shí)間序列中其社區(qū)結(jié)構(gòu)與最近過(guò)去的快照有很大不同的快照是存在異常的.Miz等人[63]針對(duì)時(shí)空數(shù)據(jù)集(例如Web和社交網(wǎng)絡(luò)的用戶活動(dòng)日志)提出了一種可擴(kuò)展的異常檢測(cè)方法，對(duì)此類網(wǎng)絡(luò)中用戶的集體行為進(jìn)行異常檢測(cè).對(duì)一個(gè)屬性圖而言，節(jié)點(diǎn)的屬性是動(dòng)態(tài)時(shí)序信號(hào)，該方法先進(jìn)行特征提取與過(guò)濾，僅保留時(shí)間序列中潛在的異常節(jié)點(diǎn)(時(shí)序?qū)傩灾斜仨氝_(dá)到足夠數(shù)量的異常)，丟棄明顯非異常節(jié)點(diǎn).然后借鑒Hebbian學(xué)習(xí)規(guī)則：2個(gè)神經(jīng)元的共同激活會(huì)導(dǎo)致2個(gè)神經(jīng)元之間的連接(突觸)增強(qiáng).該方法使用Hopfield網(wǎng)絡(luò)方法學(xué)習(xí)一個(gè)記憶網(wǎng)絡(luò)，即給定網(wǎng)絡(luò)的初始結(jié)構(gòu)，對(duì)2個(gè)初始連接的節(jié)點(diǎn)i和j，在時(shí)間t，根據(jù)某種相似性度量Sim{i,j,t}更新它們之間邊的權(quán)重，因此相鄰節(jié)點(diǎn)之間的邊會(huì)隨著相似性的變化得到增強(qiáng)或消除，最終具有相似行為的節(jié)點(diǎn)會(huì)強(qiáng)連接并在記憶網(wǎng)絡(luò)中聚集在一起.通過(guò)對(duì)網(wǎng)絡(luò)學(xué)習(xí)后的每個(gè)社區(qū)進(jìn)行分析，可以了解發(fā)生的事件和異常活動(dòng).

3.2.3 基于結(jié)構(gòu)和屬性變化的動(dòng)態(tài)圖異常檢測(cè)方法

在隨時(shí)間演變的大圖中，Wang等人[34]通過(guò)對(duì)節(jié)點(diǎn)屬性和圖結(jié)構(gòu)信息進(jìn)行建模，設(shè)計(jì)出一個(gè)異常定位框架來(lái)確定導(dǎo)致圖結(jié)構(gòu)發(fā)生變化的特定圖實(shí)體并降低誤報(bào)率.該方法先使用VAR模型(Vector Autoregression model)建模不同時(shí)刻圖快照的特征矩陣,描述動(dòng)態(tài)圖中單個(gè)節(jié)點(diǎn)的行為歷史的方法：

(4)

然后使用快速貪心算法對(duì)每個(gè)時(shí)間戳處的圖快照進(jìn)行分區(qū)，若相鄰時(shí)間戳Ct,a和C(t-1),x檢測(cè)到的社區(qū)的相似性超過(guò)閾值，相似性計(jì)算：

(5)

則將其中的2個(gè)社區(qū)連接匹配到一起，再使用VAR模型來(lái)了解社區(qū)路徑的活動(dòng)如何隨時(shí)間變化，建模進(jìn)化的社區(qū)路徑，得到社區(qū)路徑異常分?jǐn)?shù).再定義一個(gè)以社區(qū)為中心的節(jié)點(diǎn)模型，在固定的時(shí)間戳下將節(jié)點(diǎn)的特征向量與其所在社區(qū)的其他節(jié)點(diǎn)的平均特征向量進(jìn)行比較，差異即為基于社區(qū)的節(jié)點(diǎn)模型中該節(jié)點(diǎn)的異常分?jǐn)?shù).如圖12所示，給定一個(gè)節(jié)點(diǎn)，異常定位框架會(huì)判斷當(dāng)前節(jié)點(diǎn)在時(shí)刻t的屬性是否滿足：1)不遵循其自身的歷史行為模式且其所在的社區(qū)路徑顯示異常活動(dòng);或2)不遵循其自身的歷史行為模式,其所在的社區(qū)路徑活動(dòng)正常，但不遵循其所屬社區(qū)的模式.若滿足2個(gè)條件之一則認(rèn)為節(jié)點(diǎn)在時(shí)間t是異常的.

Fig. 12 Dynamic graph anomaly location framework[34]圖12 動(dòng)態(tài)圖異常定位框架[34]

4 圖異常檢測(cè)應(yīng)用場(chǎng)景和數(shù)據(jù)集

4.1 圖異常檢測(cè)應(yīng)用場(chǎng)景

在許多應(yīng)用中，檢測(cè)異常的能力變得越來(lái)越重要.目前，已經(jīng)有許多成功的異常檢測(cè)方法被開(kāi)發(fā)出來(lái)，并將其廣泛應(yīng)用于一些高影響力領(lǐng)域.例如欺詐檢測(cè)[69]、Web垃圾郵件和惡意軟件檢測(cè)[70-72]、垃圾評(píng)論檢測(cè)[10,73]、網(wǎng)絡(luò)入侵檢測(cè)[74]以及醫(yī)療保健監(jiān)視和警報(bào)[75]等.下面我們將介紹一些基于圖數(shù)據(jù)的異常發(fā)現(xiàn)算法在現(xiàn)實(shí)場(chǎng)景中的應(yīng)用.

4.1.1 電信欺詐

在眾多類型的電信欺詐中，最普遍存在的一種是訂閱欺詐.欺詐者經(jīng)常使用虛假身份獲取賬戶，目的是免費(fèi)使用該服務(wù)而不進(jìn)行任何付款.

最早基于圖數(shù)據(jù)的在電信欺詐檢測(cè)中有效的研究是由Cortes等人[76]完成的，他們主要將鏈接分析與時(shí)間和呼叫量信息一起使用.圍繞每個(gè)電話賬戶構(gòu)建和維護(hù)的子圖被稱為該賬戶的“communities of interest”(COI).COI主要包含在動(dòng)態(tài)加權(quán)度量方面與給定賬戶最相關(guān)的其他電話賬戶，這些度量考慮了這些通話方之間的通話數(shù)量和持續(xù)時(shí)間.作者使用每天更新的這些信息豐富的子圖，可以觀察到2個(gè)區(qū)分性質(zhì).首先，作者發(fā)現(xiàn)欺詐性電話賬戶之間有關(guān)聯(lián)，這些欺詐者要么直接相互呼叫，要么撥打相同的電話號(hào)碼，這使得他們?cè)贑OI中非常接近.第2個(gè)觀察結(jié)果表明，有可能通過(guò)其COI與以前標(biāo)記的欺詐性COI相似來(lái)發(fā)現(xiàn)新的欺詐性賬戶，這是由于被電話運(yùn)營(yíng)商檢測(cè)到的欺詐者創(chuàng)建新賬戶并表現(xiàn)出相似的通話習(xí)慣，而這些習(xí)慣被其COI有效地捕獲.

4.1.2 垃圾評(píng)論檢測(cè)

客戶每天都會(huì)在在線購(gòu)物網(wǎng)站(亞馬遜、淘寶網(wǎng))上發(fā)表很多評(píng)論.評(píng)論會(huì)影響客戶的購(gòu)買(mǎi)決定，同時(shí)也會(huì)吸引大量旨在誤導(dǎo)買(mǎi)家的垃圾評(píng)論發(fā)送者.例如2017-08—2018-07中國(guó)最大的二手商品應(yīng)用程序閑魚(yú)也遭受了垃圾評(píng)論的困擾，這些垃圾評(píng)論需要清除，因?yàn)樗鼈儾粌H破壞用戶體驗(yàn)，而且還為互聯(lián)網(wǎng)欺詐提供了溫床.

大多數(shù)現(xiàn)有的垃圾評(píng)論檢測(cè)方法都專注于從評(píng)論內(nèi)容或評(píng)論者行為中提取可靠的工程特征.Jindal等人[77]研究了重復(fù)評(píng)論內(nèi)容以檢測(cè)垃圾評(píng)論，他們收集了分別以評(píng)論、評(píng)論者、產(chǎn)品為中心的特征，并將其提供給邏輯回歸模型;Ott等人[78]僅關(guān)注評(píng)論的內(nèi)容，作者使用樸素貝葉斯和SVM分類器來(lái)解決問(wèn)題.但關(guān)系在垃圾評(píng)論檢測(cè)中也起著重要作用，例如，垃圾評(píng)論制造者經(jīng)常將垃圾評(píng)論廣告成組發(fā)布；基于關(guān)系的觀察，Wang等人[79]提出了第1種基于圖的垃圾評(píng)論檢測(cè)方法，他們使用3種類型的節(jié)點(diǎn)(評(píng)論者、商店和評(píng)論)構(gòu)建了“評(píng)論圖”，然后以類似HITS的方式增強(qiáng)了評(píng)論者的信任度，商店的可靠性和評(píng)論的誠(chéng)實(shí)性；Lucker等人[80]利用文獻(xiàn)[79]構(gòu)建的評(píng)論圖和評(píng)論者之間的關(guān)系圖進(jìn)行垃圾評(píng)論檢測(cè)；Akoglu等人[81]利用關(guān)系分類來(lái)檢測(cè)垃圾評(píng)論，并開(kāi)發(fā)了基于RMN的關(guān)系模型，以捕獲評(píng)論者和商店之間的相關(guān)性，然后使用LBP進(jìn)行推理；Li等人[72]提出了一種基于圖卷積網(wǎng)絡(luò)(GCN)的大規(guī)模反垃圾評(píng)論方法，用于在咸魚(yú)上檢測(cè)垃圾評(píng)論廣告.

4.1.3 網(wǎng)絡(luò)入侵檢測(cè)

大多數(shù)基于圖的網(wǎng)絡(luò)入侵檢測(cè)方法都專注于網(wǎng)絡(luò)圖的動(dòng)態(tài)增長(zhǎng)和變化.在此圖中，節(jié)點(diǎn)表示網(wǎng)絡(luò)中的代理，例如廣告、文件、目錄服務(wù)器和客戶端節(jié)點(diǎn)，邊表示它們?cè)诰W(wǎng)絡(luò)上的通信.跟蹤網(wǎng)絡(luò)圖的動(dòng)態(tài)性質(zhì)實(shí)際是基于計(jì)算節(jié)點(diǎn)的通信行為在受到攻擊時(shí)會(huì)發(fā)生變化的假設(shè).

Idé等人[82]監(jiān)視節(jié)點(diǎn)的“活動(dòng)”向量.節(jié)點(diǎn)的活動(dòng)分?jǐn)?shù)是集體計(jì)算的，如果一個(gè)節(jié)點(diǎn)鏈接到許多活動(dòng)節(jié)點(diǎn)，則其活動(dòng)得分很高.通過(guò)此定義，活動(dòng)向量實(shí)質(zhì)上成為描述通信圖的鄰接矩陣的主要特征向量.他們通過(guò)測(cè)量向量方向和大小的變化來(lái)跟蹤該向量隨時(shí)間的變化，并開(kāi)發(fā)在線閾值技術(shù)來(lái)決定何時(shí)將更改標(biāo)記為重要事件.這些事件可能對(duì)應(yīng)于網(wǎng)絡(luò)攻擊、故障和其他網(wǎng)絡(luò)配置更改.Sun等人[83]利用矩陣分解來(lái)捕獲網(wǎng)絡(luò)活動(dòng)的范數(shù).他們采用稱為緊湊矩陣分解的稀疏高效方法來(lái)分解網(wǎng)絡(luò)圖的鄰接矩陣，并使用重構(gòu)的相對(duì)和平方誤差作為隨時(shí)間變化的變化度量，以跟蹤網(wǎng)絡(luò)圖新來(lái)的快照.Ding等人[84]考慮了網(wǎng)絡(luò)社區(qū)的分析, 監(jiān)視跨社區(qū)的通信行為以發(fā)現(xiàn)網(wǎng)絡(luò)入侵.直覺(jué)上，跨越社區(qū)界限的交流被認(rèn)為是可疑的，可以視為攻擊的信號(hào). ROC曲線表明，他們提出的方法可實(shí)現(xiàn)90%以上的檢測(cè)準(zhǔn)確率，但在帶有惡意攻擊的ground truth數(shù)據(jù)中，誤報(bào)率較高，約為50%.

4.1.4 社交網(wǎng)絡(luò)

對(duì)于在社交網(wǎng)絡(luò)平臺(tái)上傳播惡意軟件的新方法，我們將其稱為Socware. Socware可由出現(xiàn)在諸如Facebook和Twitter之類的社交媒體平臺(tái)的新聞源中的任何帖子組成，這些帖子有4個(gè)特點(diǎn)：

1) 引導(dǎo)用戶進(jìn)入危害用戶設(shè)備的惡意網(wǎng)站；

2) 為了謀取利益，給用戶承諾提供虛假獎(jiǎng)勵(lì)并使用戶執(zhí)行某些任務(wù)(例如填寫(xiě)調(diào)查問(wèn)卷)；

3) 使用戶通過(guò)單擊或“點(diǎn)贊”來(lái)提高某些頁(yè)面的聲譽(yù)和知名度等；

4) 使用戶分享或重新發(fā)帖.

為了對(duì)抗Socware，Rahman等人[85]提出了一個(gè)分類框架，該框架利用了“social-context-aware”特征，例如共享特定帖子的不同用戶之間帖子的消息相似性.除了其他基于內(nèi)容的特征外，還包括該帖子在網(wǎng)絡(luò)中的傳播大小，其他網(wǎng)絡(luò)用戶對(duì)該帖子的“喜歡”和評(píng)論計(jì)數(shù)等.Gao等人[86]基于網(wǎng)絡(luò)級(jí)的特征，例如發(fā)件人的程度，用戶之間的交互歷史等，使用增量聚類對(duì)社交網(wǎng)絡(luò)進(jìn)行在線垃圾郵件過(guò)濾，這些方法依賴于基于集體特征集的學(xué)習(xí)分類器.

4.2 圖異常檢測(cè)數(shù)據(jù)集介紹與構(gòu)造

4.2.1 公開(kāi)數(shù)據(jù)集

目前主要的可用于圖異常檢測(cè)的公開(kāi)數(shù)據(jù)集如表3所示.此外，異常檢測(cè)數(shù)據(jù)集(outlier detection datasets, ODDS)提供了大量帶有g(shù)round truth的異常檢測(cè)數(shù)據(jù)集，包含來(lái)自不同領(lǐng)域的數(shù)據(jù)集，并將其集中地呈現(xiàn)給研究者.ODDS將數(shù)據(jù)集進(jìn)行了劃分，主要包括：1)多維點(diǎn)數(shù)據(jù)集：每個(gè)數(shù)據(jù)點(diǎn)有一個(gè)記錄，每個(gè)記錄包含多個(gè)屬性;2)用于事件檢測(cè)的時(shí)間序列圖數(shù)據(jù)集：時(shí)間圖數(shù)據(jù)，其中圖隨時(shí)間推移動(dòng)態(tài)變化，新的節(jié)點(diǎn)和邊會(huì)到達(dá)，或現(xiàn)有的節(jié)點(diǎn)和邊會(huì)消失;3)時(shí)間序列點(diǎn)數(shù)據(jù)集(多變量/單變量)：時(shí)間點(diǎn)數(shù)據(jù)，其中每個(gè)點(diǎn)都有一個(gè)或多個(gè)屬性，并且這些屬性會(huì)隨時(shí)間變化;4)對(duì)抗/攻擊場(chǎng)景和安全性數(shù)據(jù)集：來(lái)自在線評(píng)價(jià)系統(tǒng)的意見(jiàn)欺詐檢測(cè)數(shù)據(jù),網(wǎng)絡(luò)安全數(shù)據(jù)，例如DoS，DDoS等攻擊場(chǎng)景的入侵檢測(cè);5)擁擠場(chǎng)景視頻數(shù)據(jù)：用攝像機(jī)獲取的視頻片段.其中時(shí)序圖數(shù)據(jù)集可作為圖異常檢測(cè)的數(shù)據(jù)集.

Table 3 Public Datasets for Graph Anomaly Detection表3 圖異常檢測(cè)公開(kāi)數(shù)據(jù)集

4.2.2 異常注入方法

異常檢測(cè)的研究大多使用真實(shí)數(shù)據(jù)用以實(shí)驗(yàn).此外很多研究者還使用合成數(shù)據(jù)來(lái)模擬特定場(chǎng)景.出于隱私考慮，組織和利益相關(guān)者不愿意分享他們可用于異常檢測(cè)的信息.因此可以考慮使用綜合創(chuàng)建的數(shù)據(jù)，即在已有的公開(kāi)數(shù)據(jù)集中人為地注入異常數(shù)據(jù).目前異常注入方法主要有3種：1)擾動(dòng)原始數(shù)據(jù)，即將原本圖中正常的數(shù)據(jù)進(jìn)行人為的調(diào)整，使其呈現(xiàn)異常狀態(tài)；2)插入新的異常數(shù)據(jù)，即對(duì)原有圖進(jìn)行擴(kuò)展，插入異常的節(jié)點(diǎn)、邊等；3)在包含階段類別標(biāo)簽的圖中，將對(duì)應(yīng)標(biāo)簽數(shù)目出現(xiàn)次數(shù)最少的節(jié)點(diǎn)作為異常進(jìn)行處理.

5 圖異常檢測(cè)研究挑戰(zhàn)和未來(lái)

盡管目前在圖的異常檢測(cè)領(lǐng)域已有豐富的研究工作，但是仍面臨著很多挑戰(zhàn)：

1) 數(shù)據(jù)的相關(guān)性.首先，數(shù)據(jù)的相關(guān)性使得針對(duì)圖對(duì)象的異常定義變得困難.在傳統(tǒng)的異常檢測(cè)中，對(duì)象或數(shù)據(jù)點(diǎn)被視作是相互獨(dú)立的、同分布的，而圖數(shù)據(jù)中的對(duì)象由于節(jié)點(diǎn)間邊的存在往往具有復(fù)雜的相關(guān)性.因此，如何使用深度學(xué)習(xí)更好地挖掘這種相關(guān)性是異常檢測(cè)面臨的挑戰(zhàn)之一.

2) 定義的多樣性.鑒于圖的豐富表示形式，圖中異常的定義比傳統(tǒng)的異常點(diǎn)檢測(cè)要更加多樣化.例如，與圖子結(jié)構(gòu)相關(guān)的新型異常類型在許多應(yīng)用中都有所展現(xiàn)，如交易網(wǎng)絡(luò)中的洗錢(qián)環(huán)節(jié)等.深度學(xué)習(xí)算法如何兼容這些多樣化的異常定義也面臨挑戰(zhàn).

3) 檢測(cè)結(jié)果的可解釋性.盡管深度學(xué)習(xí)可以獲得較好的效果，但其結(jié)果的可解釋性較差，而異常檢測(cè)中的結(jié)果解釋和歸因尤為重要，基于深度學(xué)習(xí)的圖異常檢測(cè)算法如何為結(jié)果提供更好的解釋也是面臨的重要挑戰(zhàn)之一.

4) 算法的效率和自適應(yīng)性.深度學(xué)習(xí)的效率也是其缺陷之一，在圖的規(guī)模不斷擴(kuò)大的情況下，檢測(cè)算法需要高效且可擴(kuò)展；此外，當(dāng)動(dòng)態(tài)圖的變化幅度較大時(shí)，基于深度學(xué)習(xí)的檢測(cè)算法需要能夠處理這種變化；最后，由于深度學(xué)習(xí)在不同的數(shù)據(jù)上往往需要人工設(shè)置不同的參數(shù)，如何減少人工的參與也是挑戰(zhàn)之一.

綜上所述，基于深度學(xué)習(xí)的圖異常檢測(cè)的未來(lái)方向主要包括4個(gè)方面：

1) 考慮將深度學(xué)習(xí)異常檢測(cè)算法并行化和分布式化.面對(duì)越來(lái)越復(fù)雜的任務(wù)，數(shù)據(jù)和深度學(xué)習(xí)模型的規(guī)模都變得日益龐大.例如，Twitter用戶數(shù)量已經(jīng)超過(guò)3億，因此其形成的社交網(wǎng)絡(luò)的規(guī)模非常之大.因此，如果不做任何剪枝處理，深度學(xué)習(xí)模型可能會(huì)擁有上百億、甚至是幾千億個(gè)參數(shù)，必然會(huì)導(dǎo)致基于深度學(xué)習(xí)的異常檢測(cè)算法耗時(shí)過(guò)長(zhǎng)的情況，因此嘗試對(duì)其進(jìn)行并行和分布式處理是有效且直觀的解決方式.但是對(duì)深度學(xué)習(xí)算法的并行和分布式化，不應(yīng)只局限在對(duì)串行算法進(jìn)行多機(jī)實(shí)現(xiàn)以及底層實(shí)現(xiàn)方面的技術(shù)，更應(yīng)該基于對(duì)機(jī)器學(xué)習(xí)的完整理解，將分布式和深度學(xué)習(xí)緊密結(jié)合在一起，結(jié)合深度學(xué)習(xí)以及圖數(shù)據(jù)的特點(diǎn)，設(shè)計(jì)全新的真正合二為一的“分布式深度學(xué)習(xí)異常檢測(cè)”算法.

2) 圖類型的兼容性.面對(duì)日益復(fù)雜的圖，現(xiàn)有的深度學(xué)習(xí)圖異常檢測(cè)算法不能很好地適用所有場(chǎng)景，大多數(shù)模型針對(duì)同質(zhì)圖，對(duì)包含不同形態(tài)的異質(zhì)圖的研究很少.例如在異常檢測(cè)中通常會(huì)涉及到靜態(tài)圖、動(dòng)態(tài)圖、屬性圖等類型，而目前論文提出的方法都只針對(duì)其中某一種類型，無(wú)法兼顧所有的圖類型，更無(wú)法處理更為復(fù)雜的異質(zhì)圖.因此，應(yīng)當(dāng)考慮設(shè)計(jì)可以兼容多種圖數(shù)據(jù)類型的算法，以應(yīng)對(duì)日益復(fù)雜的數(shù)據(jù)類型.

3) 異常的解釋和歸因.深度學(xué)習(xí)的解釋性通常較差，將其運(yùn)用到圖異常檢測(cè)上往往會(huì)導(dǎo)致檢測(cè)結(jié)果難以直觀地理解；但是圖異常檢測(cè)不應(yīng)只停留在算法層面，而是應(yīng)當(dāng)更好地去考慮如何呈現(xiàn)給用戶更易理解的檢測(cè)結(jié)果.首先必須考慮將異常檢測(cè)結(jié)果進(jìn)行直觀的、可視化的呈現(xiàn)，其難點(diǎn)在于對(duì)于大規(guī)模的圖，其可視化需要耗費(fèi)大量CPU和內(nèi)存資源，應(yīng)當(dāng)如何去兼顧資源消耗和可視化效果.深度學(xué)習(xí)模型可解釋性指對(duì)模型內(nèi)部機(jī)制的理解以及對(duì)模型結(jié)果的理解.其重要性體現(xiàn)在：在建模階段，輔助開(kāi)發(fā)人員理解模型，進(jìn)行模型的對(duì)比選擇，必要時(shí)優(yōu)化調(diào)整模型；在投入運(yùn)行階段，向業(yè)務(wù)方解釋模型的內(nèi)部機(jī)制，對(duì)模型結(jié)果進(jìn)行解釋；但是目前此深度學(xué)習(xí)模型的可解釋性仍是學(xué)術(shù)界的難點(diǎn)及研究熱點(diǎn)之一.

6 總結(jié)與展望

本文首先介紹了圖異常檢測(cè)的相關(guān)背景和技術(shù)基礎(chǔ)，之后從靜態(tài)圖和動(dòng)態(tài)圖的角度出發(fā)，討論了基于深度學(xué)習(xí)的圖異常檢測(cè)的各種技術(shù)方法.然后介紹了圖異常檢測(cè)方法在各個(gè)領(lǐng)域的實(shí)際應(yīng)用，并介紹了現(xiàn)有工作中常用的數(shù)據(jù)集和異常注入方法，為之后研究人員開(kāi)展相關(guān)的研究打下了基礎(chǔ).最后，本文還討論了基于圖數(shù)據(jù)運(yùn)用深度學(xué)習(xí)進(jìn)行異常檢測(cè)面臨的挑戰(zhàn)和未來(lái)研究趨勢(shì)，這些對(duì)未來(lái)本領(lǐng)域的研究具有很強(qiáng)的指導(dǎo)意義.這篇綜述的目的是調(diào)查和分析用于圖異常檢測(cè)的各種深度學(xué)習(xí)模型，并評(píng)估相關(guān)技術(shù)方法的適用性，在為特定領(lǐng)域的異常檢測(cè)選擇深度學(xué)習(xí)模型時(shí)，這些評(píng)估和分析結(jié)果可以作為指南性的意見(jiàn).基于深度學(xué)習(xí)的異常檢測(cè)技術(shù)目前仍然是十分活躍的研究方向，但是在圖數(shù)據(jù)方面的應(yīng)用研究卻相對(duì)缺乏，未來(lái)會(huì)有更多的技術(shù)和研究成果出現(xiàn)，綜述的內(nèi)容也會(huì)進(jìn)行不斷地更新和擴(kuò)展.

作者貢獻(xiàn)聲明：陳波馮負(fù)責(zé)論文主要內(nèi)容的調(diào)研和撰寫(xiě)，以及論文的校驗(yàn)，李靖東輔助調(diào)研相關(guān)內(nèi)容并提供指導(dǎo)意見(jiàn)，盧興見(jiàn)，王曉玲，沙朝鋒，張吉對(duì)文章的結(jié)構(gòu)和內(nèi)容提供指導(dǎo)意見(jiàn)，其中盧興見(jiàn)和王曉玲貢獻(xiàn)相同，為共同通信作者.