融合雙重自監督信號的圖異常檢測

馮健, 趙宇鵬, 劉天

(西安科技大學計算機科學與技術學院, 西安 710054)

當前,在網絡異常攻擊、突發事件檢測等場景中,圖異常檢測技術得到了廣泛研究和應用。圖異常檢測是將原始問題抽象成圖數據結構,并基于圖的結構和屬性信息利用圖機器學習技術識別圖中顯著不同節點。

典型的圖異常檢測方法包括基于數據挖掘的傳統方法和基于深度學習的方法[1]。隨著網絡規模的擴大及深度學習在各研究領域的成功,后者成為主流[2],并演化為兩類:基于有監督的和基于自監督的圖異常檢測方法。由于圖異常具有多樣性、未知性和稀疏性[3],使得標簽的獲取尤為困難,因此,基于自監督的方法更具研究前景和實踐價值。

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

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

(1)設計一種融合結構和屬性的自監督圖異常檢測模型,結合對比學習和自編碼器,有效檢測結構和屬性異常。

(2)設計正負例采樣策略提取節點的局部子結構,提高對比學習效率。

(3)在四個數據集上進行實驗證明了SA-SGADM的有效性。

1 相關工作

1.1 圖異常檢測

異常檢測的本質是發現分布或形成機制與其他大部分數據不同的數據對象,而圖網絡的異常檢測更是成為研究重點。

傳統的圖異常檢測一般是基于矩陣分解、密度聚類等方法發現異常節點,如Radar[7]、ANOMALOUS[8]、AMEN[9]等。盡管這些方法在低維屬性圖上取得了成功,但由于非線性學習能力有限[8],在高維圖上異常檢測的結果往往不盡如人意。

隨著深度學習的飛速發展,基于深度學習的圖異常檢測方法得到了大量研究[10],而有著強大圖學習能力的圖神經網絡技術也被廣泛應用于圖異常檢測領域。最新的圖異常檢測方法逐漸歸為兩大類:基于有監督的和基于自監督的方法。其中前者充分利用數據標簽得到非線性分類器,如ConvNets[11]等。然而,由于圖異常數據中的標簽成本高昂,使自監督學習逐漸成為解決圖異常檢測任務的主流方向。

1.2 自監督圖異常檢測

自監督圖異常檢測通常分為基于自編碼器和基于對比學習的方法。其中前者通過自編碼器對網絡中的數據進行重構,并根據重構差值進行異常檢測,如DOMINANT[12]、SpecAE[13]等。此類方法在重構時往往用到屬性信息,忽略對結構異常的檢測。而后者通過構造正負例,并對正負例進行對比實現異常檢測,如DGI[14]、CoLA[3]等。此類方法在構建正負例時常對目標節點進行匿名化處理,容易忽略對屬性異常的檢測。

為了能夠有效檢測結構和屬性兩種不同類型的圖異常,擬結合自編碼器和對比學習,同時生成結構和屬性自監督信號,提高檢測的效果。另外,在構造用于對比學習的正負例時,不同于以往隨機采樣的方法,設計了基于節點局部子結構的采樣策略,以提升對比學習的效率。

2 問題定義

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

問題定義:對于圖G,基于自監督的圖異常檢測是在不借助節點標簽的情況下通過學習得到節點的異常值μ,依據該值對節點進行異常檢測。

3 SA-SGADM

為進行基于自監督的圖異常檢測,SA-SGADM生成結構和屬性自監督信號,以應對不同類型的圖異常。模型框架由四部分組成:①輸入采樣模塊。利用圖元信息進行正負例節點采樣;②自監督信號生成模塊。通過圖神經網絡生成結構和屬性自監督信號;③異常檢測模塊。基于對比學習進行異常檢測;④輸出模塊。如圖1所示。

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

3.1 輸入采樣模塊

目的是通過新的采樣策略選取正負例節點,以提高后續對比學習的效率。如圖2所示。

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

3.1.1 正例節點采樣

隨機選取一個目標節點vt作為正例節點。

3.1.2 負例節點采樣

計算vt所涉及的封閉三角形的圖元個數來構造節點的節點圖元度(node graphlet degree,Ngd)值,并以此構建G的圖元鄰接矩陣ANgd=[atn],其中atn的計算公式為

(1)

在atn=1的節點中隨機選取某個節點vn作為負例節點。

3.1.3 子結構采樣

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

3.2 自監督信號生成模塊

面向多類型圖異常生成結構和屬性自監督信號。

3.2.1 結構自監督信號

針對圖中的結構異常,生成結構自監督信號。

利用圖卷積神經網絡(graph convolutional networks, GCN)[16]對Φt和Φn進行表示學習。公式為

(2)

需要注意的是,為了避免后續對比學習時識別出與目標節點相匹配的子結構從而引起信息泄露的問題,對源節點進行匿名化處理,即在進行子結構學習時將源節點的屬性向量置為零向量。且為了得到子結構的圖級表示,使用平均池化技術,具體公式為

(3)

3.2.2 屬性自監督信號

針對圖中的屬性異常,生成屬性自監督信號。

(1)目標節點屬性表示。為了將屬性與子結構投影到相同的空間中,使用與gt學習過程中相同的Wt和σ,然后利用深度神經網絡(deep neural networks, DNN)對目標節點進行屬性表示,公式為

ht=σ(xtWt)

(4)

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

(2)屬性重構。由于在正負子結構表示的過程中對目標節點進行了匿名化處理,導致目標節點的屬性信息丟失。同時,采用GCN學習也會帶來一定程度上的屬性平滑,削弱了原始屬性的唯一性。因此,使用自編碼器對節點的屬性進行重構,以提取出屬性自監督信號。

具體來說,就是通過自編碼器對ht進行重構,公式為

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

(5)

(6)

(7)

式(7)中:La表示屬性自監督信號部分的目標函數。

3.3 異常檢測模塊

基于上述工作得到的結構和屬性自監督信號,通過對比學習進行異常檢測。

(2)異常檢測。使用雙線性評分函數Dis[3]計算實例對之間的匹配程度。表示為

(8)

(9)

利用讀出函數ψ計算重構前后正負實例對的差值,公式為

(10)

式(10)中:ct,t和ct,n分別為正負實例對重構前后的對比結果;ψ為max、min、mean三種處理方法。

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

(11)

式(11)中:Ls為結構自監督信號部分的目標函數。

通過利用圖元鄰接矩陣進行正負子圖采樣,以及結合對比學習機制和自編碼器機制的學習方式,SA-SGADM在異常檢測過程中能夠同時有效識別結構異常節點和屬性異常節點。

3.4 輸出模塊

節點異常評分的計算公式為

(12)

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

由于正常節點的ct,t值應趨向于1,而ct,n趨向于0,因此μ應接近1;異常節點沒有特定的匹配模式,其ct,t和ct,n都趨于0.5,因此μ應趨于0。對所有節點按μ從小到大排列,前K個節點被認定為異常節點,其中K為注入異常的個數。

3.5 模型優化

通過結合式(7)和式(11),得到融合結構和屬性的自監督圖異常檢測模型的優化目標,公式為

L=La+Ls

(13)

優化目標為最小化L。

4 實驗與結果分析

為了驗證SA-SGADM的有效性,設計了3組實驗,試回答以下問題。

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

問題2:模型中參數的不同取值是否對檢測效率產生影響?

問題3:基于圖元鄰接矩陣采樣是否會提高檢測效率?如何選擇讀出函數ψ使效果最優?

4.1 實驗數據集

使用四個數據集進行實驗驗證,分別是社交網絡Blogcatalog[17]、Flickr[18]和引文網絡Cora[19]、Citeseer[19],如表1所示。

表1 實驗數據集Table 1 Experimental Datasets

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

(1)結構異常。基于文獻[20]的方法通過擾動網絡的拓撲結構獲得。將原本不相關的節點組成的小社團視為異常。指定社團的大小為p,個數為q。從節點集合V中選取p個節點進行全連接,并將其標記為結構異常節點。其中p=15,針對BlogCatalog、Flickr、Cora、Citeseer數據集,q分別設置為10、15、5、5。

(2)屬性異常。按照文獻[21]中的策略構造,先確定目標節點vt,再隨機選取50個節點,并分別計算vt與其的歐幾里得距離,最后將vt與距離最遠節點的屬性互換。

4.2 評價指標

使用ROC-AUC[3]作為評價指標以衡量模型的性能。AUC越接近1表示模型具有更好的性能。

4.3 實驗一:基線比較

為了回答問題1,將SA-SGADM與傳統異常檢測模型Radar[7]、ANOMALOUS[8]、AMEN[9]以及基于深度學習的異常檢測模型DOMINANT[12]、DGI[14]、CoLA[3]進行比較。結果如表2所示。

從表2 可以看出與SA-SGADM相比,傳統異常檢測模型因不能很好地處理高緯度數據,因此性能較差;而SA-SGADM同時包含了兩種類型的自監督信號,在解決多類型異常檢測問題時的效率優于基于深度學習的方法。

表2 基線對比Table 2 Comparison with baselines

4.4 實驗二:參數確定

為了回答問題2,分別對子結構大小k、采樣輪次r和嵌入維度d三個參數取不同值以觀察其對模型效率的影響。

(1)子結構大小。考慮到離目標節點較遠的節點不會提供有用的信息,也會帶來較大的運算壓力,故將k設置在2～5,實驗結果證明k=5時達到最優。如圖3所示。

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

(3)嵌入維度。考慮到編碼器和解碼器的運行效率,將d的取值范圍設置在16～256進行實驗,實驗結果表明d=64時達到最優,如圖5所示。

圖3 子結構大小Fig.3 Size of substructure

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

4.5 實驗三:消融實驗

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

表3 消融實驗結果Table 3 Results of ablation experiment

從表3可以看出:

(1)使用原始鄰接矩陣的模型SA-SGADM-A無法帶來與SA-SGADM相同的優秀檢測結果。

(2)在引文網絡數據集中使用最小值讀出函數SA-SGADM-min時效果達到最優,而社交網絡數據集中使用最大值讀出函數SA-SGADM-max時效果達到最優。原因可能在于引文網絡的顯著度(平均為2.5)低于社交網絡(平均為32.4),從而導致引文網絡進行子結構采樣時信息丟失,因此真實對比的結果普遍偏小,社交網絡則與之相反。

5 結論與展望

針對圖網絡中的自監督異常節點檢測研究,對異常多樣性等問題探索以及本文進行系統總結,得出如下結論。

(1)模型通過生成雙重自監督信號,能夠有效檢測圖中多類型的異常節點。

(2)利用復雜的圖元信息進行節點采樣并結合對比學習,能夠提高異常檢測的效率。

對于未來的工作,可以從如下方面進行展開:

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

(2)動態圖的異常檢測也是研究發展之一。