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

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

面向結構化圖數據的異常檢測：背景與挑戰

異常檢測是數據挖掘的經典任務之一。分析異常數據有助于企業或用戶理解其背后的形成機制，從而做出相應決策，避免損失。隨著網絡發展，面向結構化數據的異常檢測，即圖異常檢測，受到越來越多關注。

圖異常檢測具體可定義為：尋找圖上的少部分對象（節點、邊、子圖等），它們與其余大多數對象有著不同分布規律。 本文專注于圖上異常節點的檢測任務 。相較于傳統的異常檢測方法，圖異常檢測能夠利用不同實體之間的關聯信息，更好服務于網絡安全、欺詐檢測、水軍檢測、金融風控、故障監測等實際場景。

下圖直觀對比了傳統異常檢測與面向圖的異常檢測任務之間的區別。

圖 1：傳統異常檢測與面向圖的異常檢測任務對比。

近年來，圖神經網絡成為分析處理結構化數據的一大利器。圖神經網絡通過學習包含節點自身特征和鄰居信息的嵌入表示，來更好完成分類、重建、回歸等下游任務。

然而，通用的圖神經網絡（如圖卷積網絡等）主要針對正常數據設計，在異常檢測任務上容易遇到 “過平滑”(over-smoothing) 問題，即異常節點和正常節點的表達難以區分，影響異常檢測的準確率。例如，在金融欺詐檢測的實際應用中，異常賬戶通常會先與多個正常賬戶進行正常交易來偽裝自己，降低自身可疑程度，之后再展開違規交易。這種 “關系欺詐” 進一步增加了圖異常檢測的難度。

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

事實證明，選擇不同的頻譜濾波器（spectral filter）會影響圖神經網絡的表達能力，從而造成性能上的差異。

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

為了填補現有研究的空白，本文希望回答這樣一個問題： 如何為圖神經網絡量身定做一個頻譜濾波器用于異常檢測？

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

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

圖片的上半部分展示了包含不同程度異常的數據在 BA 圖上的分布，而下半部分展示了對應的頻譜能量分布。其中，柱狀圖代表對應頻譜區間的能量占比，折線圖代表從零到該點頻域能量的累積占比。

圖 2：頻譜能量 “右移” 現象的可視化。

從上圖可以看出，當異常數據占比為 0% 時，大部分能量集中在低頻部分（λ<0.5）。通過增大異常節點相對于正常節點的方差 σ 或比例 α，數據的異常程度逐漸增大，頻譜上低頻部分的能量逐漸變少，高頻部分則相應增加。基于高斯分布假設，本文 從理論上嚴格證明了數據異常程度的增大和頻譜能量的 “右移” 之間存在單調關系 。

在實際場景中，異常數據通常遵循更加復雜的分布。在四個大規模圖異常檢測數據集上，研究者同樣證實了 “右移” 現象的存在。以下圖亞馬遜異常用戶檢測數據集為例，當刪除數據中一部分異常節點后，頻譜上低頻能量顯著增多，同時高頻則相應減少。如果刪除同樣數量的隨機節點，頻譜的能量分布幾乎沒有變化。這進一步驗證了異常數據是頻譜能量 “右移” 的關鍵。

圖 3 : 亞馬遜異常用戶檢測數據集上刪除不同節點對頻譜能量分布的影響：原圖 (The Original)，刪除隨機節點 (Drop-Random)，刪除異常節點 (Drop-Anomaly)

圖異常檢測的新利器：Beta 小波圖神經網絡

上節的分析表明，在圖異常檢測時需要關注 “右移” 效應。例如上圖亞馬遜數據集中，特征值 λ=1 附近的頻譜信息與異常數據有較大關聯。為了更好地捕獲異常信息，圖神經網絡需要具備帶通濾波器的性質，只保留 λ=1 附近的信號同時過濾其余信號。

遺憾的是，現有的圖神經網絡大多屬于低通濾波器或者自適應濾波器，它們無法保證帶通性質。其中自適應濾波器雖然具有擬合任意函數的能力，但在異常檢測中同樣可能退化為低通濾波器。這是因為在整個數據集中，異常數據對應的高頻信息占比較小，而大部分頻譜能量仍然集中在低頻。

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

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

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

本文 在四個大規模圖異常檢測數據集上驗證了 BWGNN 的性能 。其中，Yelp 數據集面向點評網站異常評論檢測，Amazon 數據集面向電商平臺異常用戶檢測，T-Finance 數據集面向交易網絡異常用戶檢測，T-Social 數據集面向社交網絡異常用戶檢測，包含多達五百萬個節點和七千萬條邊。

從下表可以看出，與傳統分類模型、通用圖神經網絡和專門的圖異常檢測模型相比，BWGNN 在 40% 訓練數據和 1% 訓練數據（半監督）兩個場景下均取得更好的效果。在運行效率上，BWGNN 與大部分通用圖神經網絡耗時接近，比其余圖異常檢測模型更高效。

總結

本文中，研究者發現圖上異常節點的出現會導致頻譜能量 “右移”，為面向結構化數據的異常檢測提供了一種新視角。基于該發現，本文提出了圖異常檢測的新工具 ——Beta 小波圖神經網絡 (BWGNN)。它通過專門設計的帶通濾波器來捕獲 “右移” 產生的高頻異常信息，在多個數據集上取得了最優效果。

在實際落地中，圖異常檢測通常是一個復雜的系統工程，但選擇合適的圖神經網絡是影響系統性能的一個關鍵因素。研究者提出的 BWGNN 設計精簡、復雜度低、易于替換，是圖神經網絡的一項新選擇。