[發明專利]動態圖異常檢測方法

在審

• 申請號: 202310057301.7
• 申請日: 2023-01-17
• 公開（公告）號: CN116150694A
• 公開（公告）日: 2023-05-23
• 發明（設計）人: 劉強;程沐陽;魏佳星;季一木
• 申請（專利權）人: 南京郵電大學
• 主分類號: G06F18/2433
• 分類號: G06F18/2433;G06F16/906
• 代理公司: 南京蘇科專利代理有限責任公司 32102
• 代理人: 姚姣陽

1.一種動態圖異常檢測方法，其特征在于，主要包括以下步驟：

步驟1、非易失性存儲器存儲階段，將隨時間變化的動態圖記為G，初始化非易失性存儲器并配置為主要內存存儲器，其中存儲動態圖的時序快照集合為G＝{G₁，G₂，......，G_T}；

步驟2、動態隨機存儲器存儲階段，對非易失性存儲器中的時序快照集合進行粗粒度檢測，找出可能的異常時刻并將其快照存入動態隨機存儲器；

步驟3、特征表示階段，對所有可能的異常時刻T獲得游走序列，從游走序列中學習各頂點的嵌入表示F_T；

步驟4、異常判斷階段，對F_T，對嵌入向量進行異常檢測，輸出異常節點。

2.根據權利要求1所述的動態圖異常檢測方法，其特征在于：在步驟1中，所述非易失性存儲器中T時刻的網絡快照為G_T，定義G_T＝(V，E_T，T)，V為點集，E_T為邊集，其中的邊e＝(u，v，t)，t為邊對應的時間。

3.根據權利要求1所述的動態圖異常檢測方法，其特征在于：在步驟2中，所述非易失性存儲器中的時序快照集合通過基于隨機草圖繪制的方法進行粗粒度檢測。

4.根據權利要求3所述的動態圖異常檢測方法，其特征在于：所述隨機草圖繪制的方法包括隨機采樣頂點并統計其中的邊數以形成特征草圖。

5.根據權利要求4所述的動態圖異常檢測方法，其特征在于：在步驟2中，所述動態圖的特征提取通過隨機抽樣生成K維的特征向量。

6.根據權利要求5所述的動態圖異常檢測方法，其特征在于：在步驟2具體還包括以下步驟：

A1、對動態圖G進行K次采樣，每個頂點被采樣的概率設為p，第i次采樣得到的子圖中的邊數為s_i，K次采樣過后，得到動態圖G對應的特征草圖為(S₁，S₂，......，S_K)；

A2、對每個網絡快照G_T的特征草圖作為針對流數據的輸入，檢測異常時刻T是否可能為異常時刻，對檢測到的可能異常時刻T，將其對應的網絡快照G_T送入所述動態隨機存儲器中。

7.根據權利要求1所述的動態圖異常檢測方法，其特征在于：在步驟3中，通過帶時序的隨機游走方式，設置權重以關注與異常時刻T更接近的時間點。

8.根據權利要求1所述的動態圖異常檢測方法，其特征在于，在步驟3具體還包括以下步驟：

B1、對起始頂點s，初始邊選擇最接近異常時刻T的邊；

B2、對每個頂點s，得到其對應的時間游走序列S_T；

B3、令f：s-＞R^D作為給下游預測任務提供特征表示的映射函數。

9.根據權利要求1所述的動態圖異常檢測方法，其特征在于：在步驟3中，通過基于Softmax函數的時序加權分布對初始邊進行取樣，其中偏置函數為：

其中，τ(e)是邊e代表的時間，在t時刻，下一個游走邊e滿足τ(e)≤t；

對下一連邊的抽樣采用有偏抽樣的方法，并將偏置函數設置如下：

其中，Γt(u)是當前所處頂點u的鄰居頂點的集合；

得到游走序列S_T后，網絡的特征學習優化函數如下：

其中，f將節點映射到對應的embedding的映射函數，W_T∈S_T是一個時間上的采樣鄰域。

10.根據權利要求1所述的動態圖異常檢測方法，其特征在于：在步驟4中，選用利用基于密度的聚類算法優化聚類效果，離群頂點則為異常點。