輕松進行動態圖異常檢測，南洋理工提出GeneralDyG
此項研究成果已被 AAAI 2025 錄用。該論文的第一作者是南洋理工大學計算與數據科學學院 (CCDS) 的碩士生楊瀟，師從苗春燕教授，主要研究方向是圖神經網絡。該論文的通訊作者為南洋理工大學百合研究中心的瓦倫堡 - 南洋理工大學校長博士后研究員趙雪嬌；申志奇，南洋理工大學計算與數據科學學院高級講師，高級研究員。
- 論文標題：A Generalizable Anomaly Detection Method in Dynamic Graphs
- 論文鏈接：https://arxiv.org/abs/2412.16447
- 代碼：https://github.com/YXNTU/GeneralDyG
研究背景與問題描述
隨著動態圖數據的廣泛應用，它在社交網絡、電商和網絡安全等領域展現了強大的建模能力。然而，與靜態圖相比，動態圖因節點和邊的動態演變特性，給數據分析帶來了更大的挑戰，尤其是在異常檢測方面。異常檢測是保障系統安全和數據完整性的關鍵任務，旨在識別顯著偏離正常模式的異常事件，例如欺詐交易、社交媒體垃圾信息和網絡入侵等。及時發現這些異常對系統的可靠性和安全性至關重要。
基于深度學習的動態圖異常檢測方法已取得一定進展，例如利用圖神經網絡提取結構信息或通過時序模型捕獲時間依賴性。然而，這些方法在通用性方面仍存在顯著不足。具體而言，它們通常難以適應不同的數據集和任務場景，難以高效捕獲動態圖中局部與全局的復雜特征。此外，一些方法在處理大規模動態圖時計算成本較高，異常事件的編碼也不夠準確，導致在新場景中的檢測性能顯著下降。
方法設計
本文針對動態圖異常檢測中的數據分布多樣、動態特征捕捉困難以及計算成本高三大挑戰，提出了一種通用方法（GeneralDyg）。首先，為應對數據分布多樣問題，我們提取節點、邊及其拓撲結構的關鍵信息，從而適應不同數據集的復雜特征分布。其次，為解決動態特征捕捉的難題，我們結合全局時間動態和局部結構變化，深入建模動態圖中的多尺度動態模式。最后，為降低計算成本，我們構建了一種輕量化框架，能夠高效捕獲關鍵動態特征，同時顯著提升計算效率。
如圖 1 所示，本文方法由三部分組成，每部分針對上述挑戰提供了解決方案：
（a）時間 ego-graph 采樣模塊，通過構建緊湊的子圖結構有效應對計算資源限制；（b）圖神經網絡提取模塊，全面捕獲動態圖的節點與邊的多樣性和復雜結構；（c）時間感知 Transformer 模塊，有效融合全局和局部動態特征。
圖 1 ：動態圖異常檢測框架 GeneralDyG 的整體架構
（a）時間 ego-graph 采樣模塊旨在通過構建緊湊的子圖結構有效緩解動態圖大規模數據帶來的計算壓力。具體來說，該模塊基于中心事件，通過 k-hop 算法提取其周圍交互歷史，構成時間 ego-graph。k-hop 算法的設計考慮了事件間的時間順序與拓撲關系，確保采樣過程兼顧時間動態與結構特性。此外，為了捕捉事件之間的層級關系，該模塊引入了特殊標記（如層級標記符號）來分隔不同層次的交互信息。這些標記能夠幫助 Transformer 模塊更好地識別與學習時間序列中的層級動態。此外，該模塊還通過限制 k 的范圍來控制采樣的規模，從而在信息完整性與計算效率之間取得平衡。這樣的設計在保留動態結構信息的同時，顯著降低了計算復雜度。
（b）在時間 ego-graph 的基礎上，本文設計了一種新的圖神經網絡（TensGNN）來提取豐富的結構信息。TensGNN 通過交替應用節點層和邊層來實現特征信息的傳播與更新，從而在節點特征和邊特征之間構建強關聯。具體而言，節點層利用節點的鄰接矩陣和特定拉普拉斯矩陣進行卷積運算，同時結合邊的特征更新節點表示。相應地，邊層則基于邊的鄰接關系和節點的狀態更新邊的特征表示。這種交替堆疊的方式能夠更好地捕捉動態圖中的局部與全局特性。此外，該模塊引入了輕量化的算子，避免了冗余計算，在大規模數據集上也能保持較高的計算效率。
（c）時間感知 Transformer 模塊：最后，GeneralDyG 通過時間感知 Transformer 模塊整合時間序列和結構特征。在自注意力機制中，模型分別利用 Query 和 Key 編碼圖的拓撲結構信息，而將 Value 保留為原始事件特征，以確保異常檢測的準確性。通過這一模塊，模型能夠有效捕獲動態圖中全局的時間依賴性和局部的動態變化，從而實現對復雜異常模式的準確建模。
實驗驗證
本文在節點級別（node level）和邊級別（edge level）兩個層面上進行了實驗評估，使用了四個真實數據集：SWaT 和 WADI 用于節點級別異常檢測，Bitcoin-Alpha 和 Bitcoin-OTC 用于邊級別異常檢測。
我們將 GeneralDyG 與 20 種主流基線方法進行對比，這些基線方法涵蓋了圖嵌入（如 node2vec、DeepWalk）和異常檢測（如 TADDY、SAD、GDN）兩大類別。實驗通過 AUC、AP 和 F1 等指標全面評估模型性能，并在不同異常比例（1%、5%、10%）下進行了系統性測試。結果表明，GeneralDyG 在所有數據集上均顯著優于現有方法，展現了卓越的通用性與檢測能力，如圖 2 所示。
圖 2 Bitcoin-Alpha 和 Bitcoin-OTC 數據集上的邊異常檢測性能對比。
總結
總的來說，我們提出了一種通用的動態圖上異常檢測方法 GeneralDyg，解決數據分布多樣、動態特征捕獲難和計算成本高三大核心問題，GeneralDyG 展現了卓越的通用性和魯棒性，為動態圖異常檢測提供了一種高效且通用的解決方案。詳細方法流程以及實驗結果請參考原文。
