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

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

研究背景與問(wèn)題描述

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

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

方法設(shè)計(jì)

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

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

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

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

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

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

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

實(shí)驗(yàn)驗(yàn)證

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

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

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

總結(jié)

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