此項研究成果已被 AAAI 2025 錄用。該論文的第一作者是南洋理工大學(xué)計算與數(shù)據(jù)科學(xué)學(xué)院 (CCDS) 的碩士生楊瀟，師從苗春燕教授，主要研究方向是圖神經(jīng)網(wǎng)絡(luò)。該論文的通訊作者為南洋理工大學(xué)百合研究中心的瓦倫堡 - 南洋理工大學(xué)校長博士后研究員趙雪嬌；申志奇，南洋理工大學(xué)計算與數(shù)據(jù)科學(xué)學(xué)院高級講師，高級研究員。

• 論文標題：A Generalizable Anomaly Detection Method in Dynamic Graphs
• 論文鏈接：https://arxiv.org/abs/2412.16447
• 代碼：https://github.com/YXNTU/GeneralDyG

研究背景與問題描述

隨著動態(tài)圖數(shù)據(jù)的廣泛應(yīng)用，它在社交網(wǎng)絡(luò)、電商和網(wǎng)絡(luò)安全等領(lǐng)域展現(xiàn)了強大的建模能力。然而，與靜態(tài)圖相比，動態(tài)圖因節(jié)點和邊的動態(tài)演變特性，給數(shù)據(jù)分析帶來了更大的挑戰(zhàn)，尤其是在異常檢測方面。異常檢測是保障系統(tǒng)安全和數(shù)據(jù)完整性的關(guān)鍵任務(wù)，旨在識別顯著偏離正常模式的異常事件，例如欺詐交易、社交媒體垃圾信息和網(wǎng)絡(luò)入侵等。及時發(fā)現(xiàn)這些異常對系統(tǒng)的可靠性和安全性至關(guān)重要。

基于深度學(xué)習(xí)的動態(tài)圖異常檢測方法已取得一定進展，例如利用圖神經(jīng)網(wǎng)絡(luò)提取結(jié)構(gòu)信息或通過時序模型捕獲時間依賴性。然而，這些方法在通用性方面仍存在顯著不足。具體而言，它們通常難以適應(yīng)不同的數(shù)據(jù)集和任務(wù)場景，難以高效捕獲動態(tài)圖中局部與全局的復(fù)雜特征。此外，一些方法在處理大規(guī)模動態(tài)圖時計算成本較高，異常事件的編碼也不夠準確，導(dǎo)致在新場景中的檢測性能顯著下降。

方法設(shè)計

本文針對動態(tài)圖異常檢測中的數(shù)據(jù)分布多樣、動態(tài)特征捕捉困難以及計算成本高三大挑戰(zhàn)，提出了一種通用方法（GeneralDyg）。首先，為應(yīng)對數(shù)據(jù)分布多樣問題，我們提取節(jié)點、邊及其拓撲結(jié)構(gòu)的關(guān)鍵信息，從而適應(yīng)不同數(shù)據(jù)集的復(fù)雜特征分布。其次，為解決動態(tài)特征捕捉的難題，我們結(jié)合全局時間動態(tài)和局部結(jié)構(gòu)變化，深入建模動態(tài)圖中的多尺度動態(tài)模式。最后，為降低計算成本，我們構(gòu)建了一種輕量化框架，能夠高效捕獲關(guān)鍵動態(tài)特征，同時顯著提升計算效率。

如圖 1 所示，本文方法由三部分組成，每部分針對上述挑戰(zhàn)提供了解決方案：

（a）時間 ego-graph 采樣模塊，通過構(gòu)建緊湊的子圖結(jié)構(gòu)有效應(yīng)對計算資源限制；（b）圖神經(jīng)網(wǎng)絡(luò)提取模塊，全面捕獲動態(tài)圖的節(jié)點與邊的多樣性和復(fù)雜結(jié)構(gòu)；（c）時間感知 Transformer 模塊，有效融合全局和局部動態(tài)特征。

圖 1 ：動態(tài)圖異常檢測框架 GeneralDyG 的整體架構(gòu)

（a）時間 ego-graph 采樣模塊旨在通過構(gòu)建緊湊的子圖結(jié)構(gòu)有效緩解動態(tài)圖大規(guī)模數(shù)據(jù)帶來的計算壓力。具體來說，該模塊基于中心事件，通過 k-hop 算法提取其周圍交互歷史，構(gòu)成時間 ego-graph。k-hop 算法的設(shè)計考慮了事件間的時間順序與拓撲關(guān)系，確保采樣過程兼顧時間動態(tài)與結(jié)構(gòu)特性。此外，為了捕捉事件之間的層級關(guān)系，該模塊引入了特殊標記（如層級標記符號）來分隔不同層次的交互信息。這些標記能夠幫助 Transformer 模塊更好地識別與學(xué)習(xí)時間序列中的層級動態(tài)。此外，該模塊還通過限制 k 的范圍來控制采樣的規(guī)模，從而在信息完整性與計算效率之間取得平衡。這樣的設(shè)計在保留動態(tài)結(jié)構(gòu)信息的同時，顯著降低了計算復(fù)雜度。

（b）在時間 ego-graph 的基礎(chǔ)上，本文設(shè)計了一種新的圖神經(jīng)網(wǎng)絡(luò)（TensGNN）來提取豐富的結(jié)構(gòu)信息。TensGNN 通過交替應(yīng)用節(jié)點層和邊層來實現(xiàn)特征信息的傳播與更新，從而在節(jié)點特征和邊特征之間構(gòu)建強關(guān)聯(lián)。具體而言，節(jié)點層利用節(jié)點的鄰接矩陣和特定拉普拉斯矩陣進行卷積運算，同時結(jié)合邊的特征更新節(jié)點表示。相應(yīng)地，邊層則基于邊的鄰接關(guān)系和節(jié)點的狀態(tài)更新邊的特征表示。這種交替堆疊的方式能夠更好地捕捉動態(tài)圖中的局部與全局特性。此外，該模塊引入了輕量化的算子，避免了冗余計算，在大規(guī)模數(shù)據(jù)集上也能保持較高的計算效率。

（c）時間感知 Transformer 模塊：最后，GeneralDyG 通過時間感知 Transformer 模塊整合時間序列和結(jié)構(gòu)特征。在自注意力機制中，模型分別利用 Query 和 Key 編碼圖的拓撲結(jié)構(gòu)信息，而將 Value 保留為原始事件特征，以確保異常檢測的準確性。通過這一模塊，模型能夠有效捕獲動態(tài)圖中全局的時間依賴性和局部的動態(tài)變化，從而實現(xiàn)對復(fù)雜異常模式的準確建模。

實驗驗證

本文在節(jié)點級別（node level）和邊級別（edge level）兩個層面上進行了實驗評估，使用了四個真實數(shù)據(jù)集：SWaT 和 WADI 用于節(jié)點級別異常檢測，Bitcoin-Alpha 和 Bitcoin-OTC 用于邊級別異常檢測。

我們將 GeneralDyG 與 20 種主流基線方法進行對比，這些基線方法涵蓋了圖嵌入（如 node2vec、DeepWalk）和異常檢測（如 TADDY、SAD、GDN）兩大類別。實驗通過 AUC、AP 和 F1 等指標全面評估模型性能，并在不同異常比例（1%、5%、10%）下進行了系統(tǒng)性測試。結(jié)果表明，GeneralDyG 在所有數(shù)據(jù)集上均顯著優(yōu)于現(xiàn)有方法，展現(xiàn)了卓越的通用性與檢測能力，如圖 2 所示。

圖 2 Bitcoin-Alpha 和 Bitcoin-OTC 數(shù)據(jù)集上的邊異常檢測性能對比。

總結(jié)

總的來說，我們提出了一種通用的動態(tài)圖上異常檢測方法 GeneralDyg，解決數(shù)據(jù)分布多樣、動態(tài)特征捕獲難和計算成本高三大核心問題，GeneralDyG 展現(xiàn)了卓越的通用性和魯棒性，為動態(tài)圖異常檢測提供了一種高效且通用的解決方案。詳細方法流程以及實驗結(jié)果請參考原文。