融合雙重自監(jiān)督信號(hào)的圖異常檢測(cè)

馮健, 趙宇鵬, 劉天

(西安科技大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院, 西安 710054)

當(dāng)前,在網(wǎng)絡(luò)異常攻擊、突發(fā)事件檢測(cè)等場(chǎng)景中,圖異常檢測(cè)技術(shù)得到了廣泛研究和應(yīng)用。圖異常檢測(cè)是將原始問(wèn)題抽象成圖數(shù)據(jù)結(jié)構(gòu),并基于圖的結(jié)構(gòu)和屬性信息利用圖機(jī)器學(xué)習(xí)技術(shù)識(shí)別圖中顯著不同節(jié)點(diǎn)。

典型的圖異常檢測(cè)方法包括基于數(shù)據(jù)挖掘的傳統(tǒng)方法和基于深度學(xué)習(xí)的方法[1]。隨著網(wǎng)絡(luò)規(guī)模的擴(kuò)大及深度學(xué)習(xí)在各研究領(lǐng)域的成功,后者成為主流[2],并演化為兩類:基于有監(jiān)督的和基于自監(jiān)督的圖異常檢測(cè)方法。由于圖異常具有多樣性、未知性和稀疏性[3],使得標(biāo)簽的獲取尤為困難,因此,基于自監(jiān)督的方法更具研究前景和實(shí)踐價(jià)值。

自監(jiān)督圖異常檢測(cè)方法利用數(shù)據(jù)本身生成自監(jiān)督信號(hào)從而指導(dǎo)異常檢測(cè)。根據(jù)自監(jiān)督信號(hào)的來(lái)源,圖中的異常通常分為兩種:結(jié)構(gòu)異常和屬性異常。其中結(jié)構(gòu)異常是指圖中某集團(tuán)中,節(jié)點(diǎn)之間的聯(lián)系遠(yuǎn)大于平均值的一部分?jǐn)?shù)據(jù)[4];而屬性異常是指屬性與相鄰節(jié)點(diǎn)的屬性存在顯著不同的數(shù)據(jù)。根據(jù)監(jiān)督信號(hào)的產(chǎn)生機(jī)理,一般采用兩種自監(jiān)督學(xué)習(xí)方法進(jìn)行圖異常檢測(cè):自編碼器(autoencoder, AE)和對(duì)比學(xué)習(xí)。其中,前者通過(guò)自編碼器對(duì)圖中節(jié)點(diǎn)進(jìn)行信息重構(gòu),若重構(gòu)誤差過(guò)大則判定為異常[5]。此類方法并非以異常檢測(cè)為目標(biāo),而是通過(guò)重構(gòu)學(xué)習(xí)原始數(shù)據(jù)的潛在表示;同時(shí),此類方法常以屬性信息作為自監(jiān)督信號(hào)指導(dǎo)異常檢測(cè),往往忽略結(jié)構(gòu)信息,使得其檢測(cè)效果受限。后者通過(guò)巧妙構(gòu)建正負(fù)例并通過(guò)對(duì)比學(xué)習(xí)節(jié)點(diǎn)的異常程度[6],目前主要聚焦于結(jié)構(gòu)正負(fù)例信息的對(duì)比,對(duì)屬性信息考慮不足,且結(jié)構(gòu)信息的選取仍較為直接,未能考慮高階、復(fù)雜的結(jié)構(gòu)對(duì)比,因此仍有較大的改進(jìn)空間。

為此,提出融合結(jié)構(gòu)和屬性的自監(jiān)督圖異常檢測(cè)模型(integrating structure and attribute self-supervised graph anomaly detection model,SA-SGADM),主要工作包括:

(1)設(shè)計(jì)一種融合結(jié)構(gòu)和屬性的自監(jiān)督圖異常檢測(cè)模型,結(jié)合對(duì)比學(xué)習(xí)和自編碼器,有效檢測(cè)結(jié)構(gòu)和屬性異常。

(2)設(shè)計(jì)正負(fù)例采樣策略提取節(jié)點(diǎn)的局部子結(jié)構(gòu),提高對(duì)比學(xué)習(xí)效率。

(3)在四個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)證明了SA-SGADM的有效性。

1 相關(guān)工作

1.1 圖異常檢測(cè)

異常檢測(cè)的本質(zhì)是發(fā)現(xiàn)分布或形成機(jī)制與其他大部分?jǐn)?shù)據(jù)不同的數(shù)據(jù)對(duì)象,而圖網(wǎng)絡(luò)的異常檢測(cè)更是成為研究重點(diǎn)。

傳統(tǒng)的圖異常檢測(cè)一般是基于矩陣分解、密度聚類等方法發(fā)現(xiàn)異常節(jié)點(diǎn),如Radar[7]、ANOMALOUS[8]、AMEN[9]等。盡管這些方法在低維屬性圖上取得了成功,但由于非線性學(xué)習(xí)能力有限[8],在高維圖上異常檢測(cè)的結(jié)果往往不盡如人意。

隨著深度學(xué)習(xí)的飛速發(fā)展,基于深度學(xué)習(xí)的圖異常檢測(cè)方法得到了大量研究[10],而有著強(qiáng)大圖學(xué)習(xí)能力的圖神經(jīng)網(wǎng)絡(luò)技術(shù)也被廣泛應(yīng)用于圖異常檢測(cè)領(lǐng)域。最新的圖異常檢測(cè)方法逐漸歸為兩大類:基于有監(jiān)督的和基于自監(jiān)督的方法。其中前者充分利用數(shù)據(jù)標(biāo)簽得到非線性分類器,如ConvNets[11]等。然而,由于圖異常數(shù)據(jù)中的標(biāo)簽成本高昂,使自監(jiān)督學(xué)習(xí)逐漸成為解決圖異常檢測(cè)任務(wù)的主流方向。

1.2 自監(jiān)督圖異常檢測(cè)

自監(jiān)督圖異常檢測(cè)通常分為基于自編碼器和基于對(duì)比學(xué)習(xí)的方法。其中前者通過(guò)自編碼器對(duì)網(wǎng)絡(luò)中的數(shù)據(jù)進(jìn)行重構(gòu),并根據(jù)重構(gòu)差值進(jìn)行異常檢測(cè),如DOMINANT[12]、SpecAE[13]等。此類方法在重構(gòu)時(shí)往往用到屬性信息,忽略對(duì)結(jié)構(gòu)異常的檢測(cè)。而后者通過(guò)構(gòu)造正負(fù)例,并對(duì)正負(fù)例進(jìn)行對(duì)比實(shí)現(xiàn)異常檢測(cè),如DGI[14]、CoLA[3]等。此類方法在構(gòu)建正負(fù)例時(shí)常對(duì)目標(biāo)節(jié)點(diǎn)進(jìn)行匿名化處理,容易忽略對(duì)屬性異常的檢測(cè)。

為了能夠有效檢測(cè)結(jié)構(gòu)和屬性兩種不同類型的圖異常,擬結(jié)合自編碼器和對(duì)比學(xué)習(xí),同時(shí)生成結(jié)構(gòu)和屬性自監(jiān)督信號(hào),提高檢測(cè)的效果。另外,在構(gòu)造用于對(duì)比學(xué)習(xí)的正負(fù)例時(shí),不同于以往隨機(jī)采樣的方法,設(shè)計(jì)了基于節(jié)點(diǎn)局部子結(jié)構(gòu)的采樣策略,以提升對(duì)比學(xué)習(xí)的效率。

2 問(wèn)題定義

概念定義:圖表示為G=(V,E,X)。其中V={v1,v2,…,vN}是N個(gè)節(jié)點(diǎn)的集合;E是邊的集合,其中eij={vi,vj}∈E,表示節(jié)點(diǎn)vi和vj之間的連邊。若有邊則eij=1,否則eij=0;A∈RN×N為G的鄰接矩陣,aij=eij。X={x1,x1,…,xN}∈RN×D為屬性矩陣,D表示屬性的維度。

問(wèn)題定義:對(duì)于圖G,基于自監(jiān)督的圖異常檢測(cè)是在不借助節(jié)點(diǎn)標(biāo)簽的情況下通過(guò)學(xué)習(xí)得到節(jié)點(diǎn)的異常值μ,依據(jù)該值對(duì)節(jié)點(diǎn)進(jìn)行異常檢測(cè)。

3 SA-SGADM

為進(jìn)行基于自監(jiān)督的圖異常檢測(cè),SA-SGADM生成結(jié)構(gòu)和屬性自監(jiān)督信號(hào),以應(yīng)對(duì)不同類型的圖異常。模型框架由四部分組成:①輸入采樣模塊。利用圖元信息進(jìn)行正負(fù)例節(jié)點(diǎn)采樣;②自監(jiān)督信號(hào)生成模塊。通過(guò)圖神經(jīng)網(wǎng)絡(luò)生成結(jié)構(gòu)和屬性自監(jiān)督信號(hào);③異常檢測(cè)模塊。基于對(duì)比學(xué)習(xí)進(jìn)行異常檢測(cè);④輸出模塊。如圖1所示。

圖1 SA-SGADM框架圖Fig.1 Framework of SA-SGADM

3.1 輸入采樣模塊

目的是通過(guò)新的采樣策略選取正負(fù)例節(jié)點(diǎn),以提高后續(xù)對(duì)比學(xué)習(xí)的效率。如圖2所示。

圖2 輸入采樣流程圖Fig.2 Flow chart of input sampling

3.1.1 正例節(jié)點(diǎn)采樣

隨機(jī)選取一個(gè)目標(biāo)節(jié)點(diǎn)vt作為正例節(jié)點(diǎn)。

3.1.2 負(fù)例節(jié)點(diǎn)采樣

計(jì)算vt所涉及的封閉三角形的圖元個(gè)數(shù)來(lái)構(gòu)造節(jié)點(diǎn)的節(jié)點(diǎn)圖元度(node graphlet degree,Ngd)值,并以此構(gòu)建G的圖元鄰接矩陣ANgd=[atn],其中atn的計(jì)算公式為

(1)

在atn=1的節(jié)點(diǎn)中隨機(jī)選取某個(gè)節(jié)點(diǎn)vn作為負(fù)例節(jié)點(diǎn)。

3.1.3 子結(jié)構(gòu)采樣

分別以vt和vn為源節(jié)點(diǎn),用重啟隨機(jī)游走(random walk with restart,RWR)遍歷[15]進(jìn)行m個(gè)節(jié)點(diǎn)的子結(jié)構(gòu)采樣,得到子結(jié)構(gòu)Φt和Φn。

3.2 自監(jiān)督信號(hào)生成模塊

面向多類型圖異常生成結(jié)構(gòu)和屬性自監(jiān)督信號(hào)。

3.2.1 結(jié)構(gòu)自監(jiān)督信號(hào)

針對(duì)圖中的結(jié)構(gòu)異常,生成結(jié)構(gòu)自監(jiān)督信號(hào)。

利用圖卷積神經(jīng)網(wǎng)絡(luò)(graph convolutional networks, GCN)[16]對(duì)Φt和Φn進(jìn)行表示學(xué)習(xí)。公式為

(2)

需要注意的是,為了避免后續(xù)對(duì)比學(xué)習(xí)時(shí)識(shí)別出與目標(biāo)節(jié)點(diǎn)相匹配的子結(jié)構(gòu)從而引起信息泄露的問(wèn)題,對(duì)源節(jié)點(diǎn)進(jìn)行匿名化處理,即在進(jìn)行子結(jié)構(gòu)學(xué)習(xí)時(shí)將源節(jié)點(diǎn)的屬性向量置為零向量。且為了得到子結(jié)構(gòu)的圖級(jí)表示,使用平均池化技術(shù),具體公式為

(3)

3.2.2 屬性自監(jiān)督信號(hào)

針對(duì)圖中的屬性異常,生成屬性自監(jiān)督信號(hào)。

(1)目標(biāo)節(jié)點(diǎn)屬性表示。為了將屬性與子結(jié)構(gòu)投影到相同的空間中,使用與gt學(xué)習(xí)過(guò)程中相同的Wt和σ,然后利用深度神經(jīng)網(wǎng)絡(luò)(deep neural networks, DNN)對(duì)目標(biāo)節(jié)點(diǎn)進(jìn)行屬性表示,公式為

ht=σ(xtWt)

(4)

式(4)中:xt為vt的原始屬性;ht則為vt的屬性表示。

(2)屬性重構(gòu)。由于在正負(fù)子結(jié)構(gòu)表示的過(guò)程中對(duì)目標(biāo)節(jié)點(diǎn)進(jìn)行了匿名化處理,導(dǎo)致目標(biāo)節(jié)點(diǎn)的屬性信息丟失。同時(shí),采用GCN學(xué)習(xí)也會(huì)帶來(lái)一定程度上的屬性平滑,削弱了原始屬性的唯一性。因此,使用自編碼器對(duì)節(jié)點(diǎn)的屬性進(jìn)行重構(gòu),以提取出屬性自監(jiān)督信號(hào)。

具體來(lái)說(shuō),就是通過(guò)自編碼器對(duì)ht進(jìn)行重構(gòu),公式為

z=fe(ht)=σ(Weht+b)

(5)

(6)

(7)

式(7)中:La表示屬性自監(jiān)督信號(hào)部分的目標(biāo)函數(shù)。

3.3 異常檢測(cè)模塊

基于上述工作得到的結(jié)構(gòu)和屬性自監(jiān)督信號(hào),通過(guò)對(duì)比學(xué)習(xí)進(jìn)行異常檢測(cè)。

(2)異常檢測(cè)。使用雙線性評(píng)分函數(shù)Dis[3]計(jì)算實(shí)例對(duì)之間的匹配程度。表示為

(8)

(9)

利用讀出函數(shù)ψ計(jì)算重構(gòu)前后正負(fù)實(shí)例對(duì)的差值,公式為

(10)

式(10)中:ct,t和ct,n分別為正負(fù)實(shí)例對(duì)重構(gòu)前后的對(duì)比結(jié)果;ψ為max、min、mean三種處理方法。

異常檢測(cè)的目標(biāo)是最大化ct,t和最小化ct,n,因此采用二元交叉熵(binary cross entropy, BCE)損失作為目標(biāo)函數(shù),公式為

(11)

式(11)中:Ls為結(jié)構(gòu)自監(jiān)督信號(hào)部分的目標(biāo)函數(shù)。

通過(guò)利用圖元鄰接矩陣進(jìn)行正負(fù)子圖采樣,以及結(jié)合對(duì)比學(xué)習(xí)機(jī)制和自編碼器機(jī)制的學(xué)習(xí)方式,SA-SGADM在異常檢測(cè)過(guò)程中能夠同時(shí)有效識(shí)別結(jié)構(gòu)異常節(jié)點(diǎn)和屬性異常節(jié)點(diǎn)。

3.4 輸出模塊

節(jié)點(diǎn)異常評(píng)分的計(jì)算公式為

(12)

式(12)中:R為計(jì)算輪次。

由于正常節(jié)點(diǎn)的ct,t值應(yīng)趨向于1,而ct,n趨向于0,因此μ應(yīng)接近1;異常節(jié)點(diǎn)沒(méi)有特定的匹配模式,其ct,t和ct,n都趨于0.5,因此μ應(yīng)趨于0。對(duì)所有節(jié)點(diǎn)按μ從小到大排列,前K個(gè)節(jié)點(diǎn)被認(rèn)定為異常節(jié)點(diǎn),其中K為注入異常的個(gè)數(shù)。

3.5 模型優(yōu)化

通過(guò)結(jié)合式(7)和式(11),得到融合結(jié)構(gòu)和屬性的自監(jiān)督圖異常檢測(cè)模型的優(yōu)化目標(biāo),公式為

L=La+Ls

(13)

優(yōu)化目標(biāo)為最小化L。

4 實(shí)驗(yàn)與結(jié)果分析

為了驗(yàn)證SA-SGADM的有效性,設(shè)計(jì)了3組實(shí)驗(yàn),試回答以下問(wèn)題。

問(wèn)題1:SA-SGADM與以往異常檢測(cè)模型相比性能是否有提升?

問(wèn)題2:模型中參數(shù)的不同取值是否對(duì)檢測(cè)效率產(chǎn)生影響?

問(wèn)題3:基于圖元鄰接矩陣采樣是否會(huì)提高檢測(cè)效率?如何選擇讀出函數(shù)ψ使效果最優(yōu)?

4.1 實(shí)驗(yàn)數(shù)據(jù)集

使用四個(gè)數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)驗(yàn)證,分別是社交網(wǎng)絡(luò)Blogcatalog[17]、Flickr[18]和引文網(wǎng)絡(luò)Cora[19]、Citeseer[19],如表1所示。

表1 實(shí)驗(yàn)數(shù)據(jù)集Table 1 Experimental Datasets

上述數(shù)據(jù)集僅包含正常數(shù)據(jù),因此需要人工加入異常數(shù)據(jù)。

(1)結(jié)構(gòu)異常。基于文獻(xiàn)[20]的方法通過(guò)擾動(dòng)網(wǎng)絡(luò)的拓?fù)浣Y(jié)構(gòu)獲得。將原本不相關(guān)的節(jié)點(diǎn)組成的小社團(tuán)視為異常。指定社團(tuán)的大小為p,個(gè)數(shù)為q。從節(jié)點(diǎn)集合V中選取p個(gè)節(jié)點(diǎn)進(jìn)行全連接,并將其標(biāo)記為結(jié)構(gòu)異常節(jié)點(diǎn)。其中p=15,針對(duì)BlogCatalog、Flickr、Cora、Citeseer數(shù)據(jù)集,q分別設(shè)置為10、15、5、5。

(2)屬性異常。按照文獻(xiàn)[21]中的策略構(gòu)造,先確定目標(biāo)節(jié)點(diǎn)vt,再隨機(jī)選取50個(gè)節(jié)點(diǎn),并分別計(jì)算vt與其的歐幾里得距離,最后將vt與距離最遠(yuǎn)節(jié)點(diǎn)的屬性互換。

4.2 評(píng)價(jià)指標(biāo)

使用ROC-AUC[3]作為評(píng)價(jià)指標(biāo)以衡量模型的性能。AUC越接近1表示模型具有更好的性能。

4.3 實(shí)驗(yàn)一:基線比較

為了回答問(wèn)題1,將SA-SGADM與傳統(tǒng)異常檢測(cè)模型Radar[7]、ANOMALOUS[8]、AMEN[9]以及基于深度學(xué)習(xí)的異常檢測(cè)模型DOMINANT[12]、DGI[14]、CoLA[3]進(jìn)行比較。結(jié)果如表2所示。

從表2 可以看出與SA-SGADM相比,傳統(tǒng)異常檢測(cè)模型因不能很好地處理高緯度數(shù)據(jù),因此性能較差;而SA-SGADM同時(shí)包含了兩種類型的自監(jiān)督信號(hào),在解決多類型異常檢測(cè)問(wèn)題時(shí)的效率優(yōu)于基于深度學(xué)習(xí)的方法。

表2 基線對(duì)比Table 2 Comparison with baselines

4.4 實(shí)驗(yàn)二:參數(shù)確定

為了回答問(wèn)題2,分別對(duì)子結(jié)構(gòu)大小k、采樣輪次r和嵌入維度d三個(gè)參數(shù)取不同值以觀察其對(duì)模型效率的影響。

(1)子結(jié)構(gòu)大小。考慮到離目標(biāo)節(jié)點(diǎn)較遠(yuǎn)的節(jié)點(diǎn)不會(huì)提供有用的信息,也會(huì)帶來(lái)較大的運(yùn)算壓力,故將k設(shè)置在2～5,實(shí)驗(yàn)結(jié)果證明k=5時(shí)達(dá)到最優(yōu)。如圖3所示。

(2)采樣輪次。將r設(shè)置在100～500,實(shí)驗(yàn)證明r=300時(shí)性能最優(yōu),如圖4所示。

(3)嵌入維度。考慮到編碼器和解碼器的運(yùn)行效率,將d的取值范圍設(shè)置在16～256進(jìn)行實(shí)驗(yàn),實(shí)驗(yàn)結(jié)果表明d=64時(shí)達(dá)到最優(yōu),如圖5所示。

圖3 子結(jié)構(gòu)大小Fig.3 Size of substructure

圖5 嵌入維度Fig.5 Dimension of embedding

4.5 實(shí)驗(yàn)三:消融實(shí)驗(yàn)

為了回答問(wèn)題3,研究了基于圖元鄰接矩陣采樣以及不同ψ對(duì)模型的影響,分別形成對(duì)比模型未采用基于圖元鄰接矩陣采樣(SA-SGADM-A)以及采用基于圖元的子結(jié)構(gòu)采樣、但ψ不同的模型SA-SGADM-max、SA-SGADM-min和SA-SGADM-mean。結(jié)果如表3所示。

表3 消融實(shí)驗(yàn)結(jié)果Table 3 Results of ablation experiment

從表3可以看出:

(1)使用原始鄰接矩陣的模型SA-SGADM-A無(wú)法帶來(lái)與SA-SGADM相同的優(yōu)秀檢測(cè)結(jié)果。

(2)在引文網(wǎng)絡(luò)數(shù)據(jù)集中使用最小值讀出函數(shù)SA-SGADM-min時(shí)效果達(dá)到最優(yōu),而社交網(wǎng)絡(luò)數(shù)據(jù)集中使用最大值讀出函數(shù)SA-SGADM-max時(shí)效果達(dá)到最優(yōu)。原因可能在于引文網(wǎng)絡(luò)的顯著度(平均為2.5)低于社交網(wǎng)絡(luò)(平均為32.4),從而導(dǎo)致引文網(wǎng)絡(luò)進(jìn)行子結(jié)構(gòu)采樣時(shí)信息丟失,因此真實(shí)對(duì)比的結(jié)果普遍偏小,社交網(wǎng)絡(luò)則與之相反。

5 結(jié)論與展望

針對(duì)圖網(wǎng)絡(luò)中的自監(jiān)督異常節(jié)點(diǎn)檢測(cè)研究,對(duì)異常多樣性等問(wèn)題探索以及本文進(jìn)行系統(tǒng)總結(jié),得出如下結(jié)論。

(1)模型通過(guò)生成雙重自監(jiān)督信號(hào),能夠有效檢測(cè)圖中多類型的異常節(jié)點(diǎn)。

(2)利用復(fù)雜的圖元信息進(jìn)行節(jié)點(diǎn)采樣并結(jié)合對(duì)比學(xué)習(xí),能夠提高異常檢測(cè)的效率。

對(duì)于未來(lái)的工作,可以從如下方面進(jìn)行展開:

(1)將研究擴(kuò)展至不同的圖元素異常檢測(cè)中,如邊、子圖等。

(2)動(dòng)態(tài)圖的異常檢測(cè)也是研究發(fā)展之一。