論文地址：https://arxiv.org/abs/2205.15508

代碼地址：https://github.com/squareRoot3/Rethinking-Anomaly-Detection

面向結(jié)構(gòu)化圖數(shù)據(jù)的異常檢測(cè)：背景與挑戰(zhàn)

異常檢測(cè)是數(shù)據(jù)挖掘的經(jīng)典任務(wù)之一。分析異常數(shù)據(jù)有助于企業(yè)或用戶理解其背后的形成機(jī)制，從而做出相應(yīng)決策，避免損失。隨著網(wǎng)絡(luò)發(fā)展，面向結(jié)構(gòu)化數(shù)據(jù)的異常檢測(cè)，即圖異常檢測(cè)，受到越來(lái)越多關(guān)注。

圖異常檢測(cè)具體可定義為：尋找圖上的少部分對(duì)象（節(jié)點(diǎn)、邊、子圖等），它們與其余大多數(shù)對(duì)象有著不同分布規(guī)律。 本文專注于圖上異常節(jié)點(diǎn)的檢測(cè)任務(wù) 。相較于傳統(tǒng)的異常檢測(cè)方法，圖異常檢測(cè)能夠利用不同實(shí)體之間的關(guān)聯(lián)信息，更好服務(wù)于網(wǎng)絡(luò)安全、欺詐檢測(cè)、水軍檢測(cè)、金融風(fēng)控、故障監(jiān)測(cè)等實(shí)際場(chǎng)景。

下圖直觀對(duì)比了傳統(tǒng)異常檢測(cè)與面向圖的異常檢測(cè)任務(wù)之間的區(qū)別。

圖 1：傳統(tǒng)異常檢測(cè)與面向圖的異常檢測(cè)任務(wù)對(duì)比。

近年來(lái)，圖神經(jīng)網(wǎng)絡(luò)成為分析處理結(jié)構(gòu)化數(shù)據(jù)的一大利器。圖神經(jīng)網(wǎng)絡(luò)通過(guò)學(xué)習(xí)包含節(jié)點(diǎn)自身特征和鄰居信息的嵌入表示，來(lái)更好完成分類(lèi)、重建、回歸等下游任務(wù)。

然而，通用的圖神經(jīng)網(wǎng)絡(luò)（如圖卷積網(wǎng)絡(luò)等）主要針對(duì)正常數(shù)據(jù)設(shè)計(jì)，在異常檢測(cè)任務(wù)上容易遇到 “過(guò)平滑”(over-smoothing) 問(wèn)題，即異常節(jié)點(diǎn)和正常節(jié)點(diǎn)的表達(dá)難以區(qū)分，影響異常檢測(cè)的準(zhǔn)確率。例如，在金融欺詐檢測(cè)的實(shí)際應(yīng)用中，異常賬戶通常會(huì)先與多個(gè)正常賬戶進(jìn)行正常交易來(lái)偽裝自己，降低自身可疑程度，之后再展開(kāi)違規(guī)交易。這種 “關(guān)系欺詐” 進(jìn)一步增加了圖異常檢測(cè)的難度。

為了解決上述困難，研究者專門(mén)提出 針對(duì)異常檢測(cè)任務(wù)的圖神經(jīng)網(wǎng)絡(luò)模型 ，包括（1）利用注意力機(jī)制從多個(gè)視圖聚合鄰域信息；（2）利用重采樣方法聚合不同類(lèi)別的鄰域信息；（3）設(shè)計(jì)額外的損失函數(shù)來(lái)輔助圖神經(jīng)網(wǎng)絡(luò)的訓(xùn)練等。這些方法主要從空域的角度設(shè)計(jì)圖神經(jīng)網(wǎng)絡(luò)來(lái)處理異常，但并沒(méi)有人從譜域的角度考慮過(guò)該問(wèn)題。

事實(shí)證明，選擇不同的頻譜濾波器（spectral filter）會(huì)影響圖神經(jīng)網(wǎng)絡(luò)的表達(dá)能力，從而造成性能上的差異。

另辟蹊徑：譜域視角下的圖異常檢測(cè)

為了填補(bǔ)現(xiàn)有研究的空白，本文希望回答這樣一個(gè)問(wèn)題： 如何為圖神經(jīng)網(wǎng)絡(luò)量身定做一個(gè)頻譜濾波器用于異常檢測(cè)？

本文首次嘗試了從 譜域視角 分析圖上的異常數(shù)據(jù)，并觀察到：異常數(shù)據(jù)會(huì)導(dǎo)致頻譜能量的 “右移”，即能量更少集中在低頻，同時(shí)更多集中在高頻。

為了可視化這種右移現(xiàn)象，研究者首先隨機(jī)生成了一個(gè)有 500 個(gè)節(jié)點(diǎn)的 Barabási–Albert 圖（BA 圖），并假設(shè)圖上正常節(jié)點(diǎn)和異常節(jié)點(diǎn)的屬性分別遵循兩個(gè)不同的高斯分布，其中異常節(jié)點(diǎn)的方差更大。

圖片的上半部分展示了包含不同程度異常的數(shù)據(jù)在 BA 圖上的分布，而下半部分展示了對(duì)應(yīng)的頻譜能量分布。其中，柱狀圖代表對(duì)應(yīng)頻譜區(qū)間的能量占比，折線圖代表從零到該點(diǎn)頻域能量的累積占比。

圖 2：頻譜能量 “右移” 現(xiàn)象的可視化。

從上圖可以看出，當(dāng)異常數(shù)據(jù)占比為 0% 時(shí)，大部分能量集中在低頻部分（λ<0.5）。通過(guò)增大異常節(jié)點(diǎn)相對(duì)于正常節(jié)點(diǎn)的方差 σ 或比例 α，數(shù)據(jù)的異常程度逐漸增大，頻譜上低頻部分的能量逐漸變少，高頻部分則相應(yīng)增加。基于高斯分布假設(shè)，本文 從理論上嚴(yán)格證明了數(shù)據(jù)異常程度的增大和頻譜能量的 “右移” 之間存在單調(diào)關(guān)系 。

在實(shí)際場(chǎng)景中，異常數(shù)據(jù)通常遵循更加復(fù)雜的分布。在四個(gè)大規(guī)模圖異常檢測(cè)數(shù)據(jù)集上，研究者同樣證實(shí)了 “右移” 現(xiàn)象的存在。以下圖亞馬遜異常用戶檢測(cè)數(shù)據(jù)集為例，當(dāng)刪除數(shù)據(jù)中一部分異常節(jié)點(diǎn)后，頻譜上低頻能量顯著增多，同時(shí)高頻則相應(yīng)減少。如果刪除同樣數(shù)量的隨機(jī)節(jié)點(diǎn)，頻譜的能量分布幾乎沒(méi)有變化。這進(jìn)一步驗(yàn)證了異常數(shù)據(jù)是頻譜能量 “右移” 的關(guān)鍵。

圖 3 : 亞馬遜異常用戶檢測(cè)數(shù)據(jù)集上刪除不同節(jié)點(diǎn)對(duì)頻譜能量分布的影響：原圖 (The Original)，刪除隨機(jī)節(jié)點(diǎn) (Drop-Random)，刪除異常節(jié)點(diǎn) (Drop-Anomaly)

圖異常檢測(cè)的新利器：Beta 小波圖神經(jīng)網(wǎng)絡(luò)

上節(jié)的分析表明，在圖異常檢測(cè)時(shí)需要關(guān)注 “右移” 效應(yīng)。例如上圖亞馬遜數(shù)據(jù)集中，特征值 λ=1 附近的頻譜信息與異常數(shù)據(jù)有較大關(guān)聯(lián)。為了更好地捕獲異常信息，圖神經(jīng)網(wǎng)絡(luò)需要具備帶通濾波器的性質(zhì)，只保留 λ=1 附近的信號(hào)同時(shí)過(guò)濾其余信號(hào)。

遺憾的是，現(xiàn)有的圖神經(jīng)網(wǎng)絡(luò)大多屬于低通濾波器或者自適應(yīng)濾波器，它們無(wú)法保證帶通性質(zhì)。其中自適應(yīng)濾波器雖然具有擬合任意函數(shù)的能力，但在異常檢測(cè)中同樣可能退化為低通濾波器。這是因?yàn)樵谡麄€(gè)數(shù)據(jù)集中，異常數(shù)據(jù)對(duì)應(yīng)的高頻信息占比較小，而大部分頻譜能量仍然集中在低頻。

為了更好處理異常數(shù)據(jù)造成的 “右移”，研究者提出了一種圖異常檢測(cè)的新方法 —— Beta 小波圖神經(jīng)網(wǎng)絡(luò) (BWGNN) 。通過(guò)借鑒 Hammond 圖小波理論，他們基于 Beta 函數(shù)設(shè)計(jì)了新的小波核作為圖神經(jīng)網(wǎng)絡(luò)的頻譜濾波器。

相比于常用的熱核 (Heat Kernel) 函數(shù)，Beta 函數(shù)作為小波核不僅符合帶通濾波器的要求，還具有更好的頻域局部性與空域局部性。下圖對(duì)比了熱核小波與 Beta 核小波的區(qū)別。

圖 4：熱核小波與 Beta 核小波在譜域（左）和空域（右）上的對(duì)比，Beta 函數(shù)具有更好的帶通與局部性質(zhì)。

本文 在四個(gè)大規(guī)模圖異常檢測(cè)數(shù)據(jù)集上驗(yàn)證了 BWGNN 的性能 。其中，Yelp 數(shù)據(jù)集面向點(diǎn)評(píng)網(wǎng)站異常評(píng)論檢測(cè)，Amazon 數(shù)據(jù)集面向電商平臺(tái)異常用戶檢測(cè)，T-Finance 數(shù)據(jù)集面向交易網(wǎng)絡(luò)異常用戶檢測(cè)，T-Social 數(shù)據(jù)集面向社交網(wǎng)絡(luò)異常用戶檢測(cè)，包含多達(dá)五百萬(wàn)個(gè)節(jié)點(diǎn)和七千萬(wàn)條邊。

從下表可以看出，與傳統(tǒng)分類(lèi)模型、通用圖神經(jīng)網(wǎng)絡(luò)和專門(mén)的圖異常檢測(cè)模型相比，BWGNN 在 40% 訓(xùn)練數(shù)據(jù)和 1% 訓(xùn)練數(shù)據(jù)（半監(jiān)督）兩個(gè)場(chǎng)景下均取得更好的效果。在運(yùn)行效率上，BWGNN 與大部分通用圖神經(jīng)網(wǎng)絡(luò)耗時(shí)接近，比其余圖異常檢測(cè)模型更高效。

總結(jié)

本文中，研究者發(fā)現(xiàn)圖上異常節(jié)點(diǎn)的出現(xiàn)會(huì)導(dǎo)致頻譜能量 “右移”，為面向結(jié)構(gòu)化數(shù)據(jù)的異常檢測(cè)提供了一種新視角?；谠摪l(fā)現(xiàn)，本文提出了圖異常檢測(cè)的新工具 ——Beta 小波圖神經(jīng)網(wǎng)絡(luò) (BWGNN)。它通過(guò)專門(mén)設(shè)計(jì)的帶通濾波器來(lái)捕獲 “右移” 產(chǎn)生的高頻異常信息，在多個(gè)數(shù)據(jù)集上取得了最優(yōu)效果。

在實(shí)際落地中，圖異常檢測(cè)通常是一個(gè)復(fù)雜的系統(tǒng)工程，但選擇合適的圖神經(jīng)網(wǎng)絡(luò)是影響系統(tǒng)性能的一個(gè)關(guān)鍵因素。研究者提出的 BWGNN 設(shè)計(jì)精簡(jiǎn)、復(fù)雜度低、易于替換，是圖神經(jīng)網(wǎng)絡(luò)的一項(xiàng)新選擇。