本文介紹來自北京航空航天大學彭浩老師團隊發表在 The journal of Artificial Intelligence 2024 上的一篇文章“Incremental Measurement of Structural Entropy for Dynamic Graphs”。為了解決當前方法不支援動態編碼樹更新和增量結構熵計算的問題，作者提出一種新的增量度量框架 – Incre-2dSE，它可以動態調整社區劃分，支援更新後二維結構熵的即時度量。作者在人工和現實世界的資料集上進行了廣泛的實驗，實驗結果證明，該增量演算法有效地捕捉了社群的動態演化，減少了時間消耗，並具有良好的可解釋性。

近年來，有學者提出一種基於編碼樹的圖結構資訊度量，即結構熵，用於發現圖中嵌入的自然層次結構。結構熵在生物資料探勘、資訊安全、圖神經網路等領域得到了廣泛的應用。

在動態場景中，一個圖在時間序列中從初始狀態演變為許多更新後的圖。為了有效地度量不斷變化的社區劃分的質量，我們需要在任何給定時間增量地計算更新的結構熵。不幸的是，由於以下兩個挑戰，目前的結構熵方法不支援有效的增量計算。

為了解決這個問題，作者提出了兩種二維編碼樹的動態調整策略，即樸素調整策略和節點偏移策略。前者保持原有的社區劃分，支援理論結構熵分析；後者基於結構熵最小化原則，透過在社群之間移動節點，動態調整社區劃分。

為了解決這個問題，作者設計了一個增量框架，即 Incre-2dSE，用於有效地度量更新的二維結構熵。具體而言，Incre-2dSE 首先利用兩種動態調整策略生成調整量，即重要統計量從原始圖到更新圖的變化，然後利用調整量透過新設計的增量公式計算更新後的結構熵。此外，作者還將增量方法推廣到無向加權圖，並對有向加權圖的一維結構熵的計算進行了詳細的討論。

樸素調整策略包括兩部分：邊策略和點策略。邊策略規定增量邊不會改變編碼樹的結構；點策略規定，當一個新節點 v 與已有節點 u 連線時，且 u 對應二維編碼樹中的葉節點 η，即 Tη=u 時，將設定一個標籤為 Tγ=v 的新葉節點 γ 作為 η 父節點的直接後繼節點，而不是另一個 1 高度的節點。我們可以從社群的角度來描述編碼樹的修改。具體來說，增量邊不改變現有節點的社群，而新節點被分配到其鄰居的社群，而不是另一個任意社群。顯然，給定大小為 n 的增量序列，我們可以在時間複雜度為 O(n) 的情況下得到更新後的編碼樹，即更新後的社區劃分。

在這一部分中，作者引入了全域性不變數和區域性變化量兩個量，透過樸素調整策略實現了更新結構熵的逼近和快速增量計算。對圖 G 施加大小為 n 的增量序列 \xi ，採用樸素調整策略得到新的圖 G' 及其對應的二維編碼樹 T' ，更新後的二維結構熵可表示為：

$$H^{T'}(G')=\sum_{\alpha_i \in A}(-\frac{g'_{\alpha_i}}{2m+2n}log\frac{V'_{\alpha_i}}{2m+2n}+\sum_{v_j \in T_{\alpha_i}}-\frac{d'_j}{2m+2n}log\frac{d'_j}{V'_{\alpha_i}}) (1)$$

然而，增量大小 n 會影響上式中求和方程中的所有項。因此，更新和計算過程的成本至少為 O(|V|) ，當圖變得非常大時，這個成本是巨大的。一種直觀的嘗試是在更新的結構熵和原始的結構熵之間作差，並嘗試以 O(n) 計算增量熵。然而，由於在上式的所有項中 m 都變為 m+n ，因此很難透過作差推匯出簡潔的 O(n) 增量計算公式。為了解決這個問題，作者在這裡引入了全域性不變數和區域性變化量。作者將全域性不變數定義為更新後結構熵的近似，區域性變化量定義為更新後的結構熵與全域性不變數之差，也可視為近似誤差。總的來說，透過計算和求和全域性不變數和區域性變化量，可以在 O(n) 內計算出更新後的二維結構熵。

雖然樸素調整策略可以快速獲得更新後的二維編碼樹及其相應的結構熵，但我們仍然需要一種更有效的策略來獲得具有較低結構熵的更好的社區劃分。因此，作者提出了另一種新的動態調整策略，即節點偏移策略，其主要思想是迭代地將節點移動到其最優偏好社群。與樸素調整策略不同，邊變化可以改變現有節點的社群，使結構熵最小化。此外，該策略支援同時增加多個邊和刪除現有邊。因此，節點偏移策略基本克服了樸素調整策略的侷限性。

首先將最優偏好社群（OPC）定義為目標節點的最佳社群，即如果目標節點進入其 OPC，則總體二維結構熵與進入 OPC 以外的其他社群相比一定是最小的。節點偏移策略可描述為：（1）設涉及節點為增量序列中出現的所有節點；（2）對於每個涉及節點，將其移動到其 OPC；（3）將涉及節點更新為與發生移動的節點連線但在不同社群的所有節點，然後重複步驟（2）。

圖 1 展示了增量度量框架（包括初始化和度量兩個階段）和傳統離線演算法（TOA）。Incre-2dSE 的目的是在給定原始圖、原始編碼樹和增量序列的情況下，在動態調整社區劃分的同時，有效地度量更新後的二維結構熵。

給定圖 G=(V,E) 為稀疏矩陣，其二維編碼樹由如下字典表示：{社群 ID 1：節點列表 1，社群 ID 2：節點列表 2，…}時，可以很容易地獲取並儲存結構資料，其時間複雜度為 O(|E|) 。然後使用儲存在 O(|V|) 中的結構資料計算結構表示式。總的來說，初始化階段需要總時間複雜度為 O(|E|)。

在這個階段，我們首先需要生成從 G 到 G' 的調整。透過提出的兩種動態調整策略，作者提供了兩種演算法來生成調整量，即樸素調整量生成演算法（NAGA）和節點偏移調整量生成演算法（NSGA）（圖 1 中的①）。兩種演算法的輸入都是原始圖的結構資料和一個增量序列，輸出是一個調整。NAGA 的時間複雜度為 O(n) ，因為它需要在增量序列中遍歷 n 條邊，而每條邊只需要花費 O(1) 。在 NSGA 中，我們首先需要 O(n) 來初始化調整。其次，在節點移動部分，我們需要確定所有涉及節點的 OPC，這需要花費 O(|A||I|)。此步驟重複 N 次，時間開銷為 O(|A|(|I_1|+|I_2|+…+|I_N|)) ，其中 I_i 表示第 $i$ 次迭代中涉及的節點數。由於大多數情況下滿足 I_1\le n 和I_i+1\le I_i，所以 NSGA 的總時間複雜度為 O(nN|A|)。

得到調整值後，可以增量計算更新後的二維結構熵:

傳統離線演算法（TOA）對每一個更新的圖重構編碼樹，並透過定義計算更新後的二維結構熵。TOA 由以下四個步驟組成。首先，將原始圖與增量序列結合生成更新後的圖（圖 1 中的 a）。其次，使用幾種不同的靜態社群檢測演算法，如 Infomap、Louvain、Leiden，將圖節點集劃分為社群，構建二維編碼樹（圖 1 中的 b）。第三，對更新後的圖的節點級、社群級、圖級結構資料進行計數並儲存（圖 1 中的 c）。更新後的結構熵透過式 1 計算（圖 1 中的 d）。TOA 的總時間成本為O(|E|+n) 加上所選社群檢測演算法的成本。

作者給出了傳統離線演算法的虛擬碼，如下圖所示：

作者在文章中討論了將此方法擴充套件到無向加權圖或有向圖的可行性。首先，作者論證了無向加權圖的方法可以由無向無權圖的方法自然推廣。其次，分析了有向圖結構熵增量計算正規化與無向圖結構熵增量計算正規化的根本區別，提出了有向加權圖一維結構熵增量計算的新方法。

無向加權圖： 無向加權圖結構熵的增量度量方法可以直觀、方便地從之前提出的無向無權圖結構熵增量度量方法中擴展出來。作者首先介紹了無向加權圖的二維結構熵的定義。在此基礎上，更新了結構熵調整的定義，提出了新情況下結構熵計算的增量公式。

有向圖： 由於有向圖的結構熵度量與無向圖的結構熵度量有本質的不同，因此本文提出的主要方法難以轉移到有向圖場景中。其中關鍵的區別在於有向圖需要轉換成一個轉移矩陣，並計算平穩分佈。由於二維結構熵的增量計算非常複雜，在這一部分中，作者簡要地提出了一種度量有向權圖一維結構熵的增量方案。具體來說，首先定義了有向加權圖及其非負矩陣表示。然後，引入了有向加權圖的結構熵公式。最後，回顧了有向加權圖一維結構熵精確或近似計算的傳統方法，即特徵向量計算和全域性聚合，並提出了一種增量迭代逼近演算法，即區域性傳播演算法，如圖 3 所示。

在全域性聚合中，每次迭代都需要遍歷所有的節點和邊，這導致了很高的計算冗餘。在這一部分中，作者提出了一種快速逼近更新後的一維結構熵的新方法，即區域性傳播。顧名思義，其關鍵思想是利用式（3）將區域性受到增量影響的節點的資訊進行傳播，動態地更新平穩分佈，從而獲得低於全域性聚合的時間複雜度。

$$\pi^{(\theta +1)}i=\sum{v_j \in N(v_i)} \pi^{(\theta)}j b{ji} (3)$$

圖 3 區域性傳播演算法的示意圖

實驗與評估：作者基於動態圖形即時監控和社群最佳化的應用進行了廣泛的實驗。

人工資料集： 首先，作者利用“Networkx”（一個 Python 庫）中的隨機分割槽圖 (random)、高斯隨機分割槽圖 (gaussian) 和隨機塊模型 (SBM) 方法生成動態圖的 3 種不同初始狀態。之後，透過 Hawkes Process 對每個初始狀態生成增量序列和更新圖。霍克斯過程透過假設歷史事件可以影響當前事件的發生，對離散序列事件進行建模。

真實資料集： 對於現實世界的資料集，作者選擇了 Cit-HepPh、DBLP 和 Facebook 進行實驗。對於每個資料集，作者截取了 21 個連續的快照（一個初始狀態和 20 個更新的圖）。由於結構熵僅在連通圖上定義，因此只保留每個快照的最大連通分量。總的來說，圖 5 簡要顯示了人工資料集和真實資料集的統計資料。

在本應用中，我們旨在透過 NAGA+AIUA 和 NSGA+AIUA 的增量演算法最佳化社區劃分並監控相應的二維結構熵，以及基線 TOA 來即時量化動態圖的每個快照的社群質量。具體來說，對於每個資料集，我們首先從 Infomap、Louvain 和 Leiden 中選擇一種靜態社群檢測方法（簡稱靜態方法）生成初始狀態的社區劃分。實驗結果如圖 6（真實資料集）和圖 7（人工資料集）所示。

在這一部分中，作者評估了節點偏移策略的不同迭代次數對更新結構熵的影響。作者使用迭代次數 $N=3,5,7,9$ 的 NSGA+AIUA 分別度量前一小節中每種情況下 20 個更新圖的平均更新結構熵。實驗結果如圖 8 所示，更新的結構熵隨著迭代次數的增加而減少。這是因為，隨著迭代次數的增加，更多的節點將轉移到它們的 OPC，這導致結構熵進一步降低。實驗還表明，節點偏移策略具有良好的可解釋性。

圖 9 給出了 NAGA+AIUA 和 NSGA+AIUA（N=3,5,7,9）這兩種增量演算法在所有 6 個數據集上的耗時比較。圖中的縱軸表示所選增量演算法在所有 20 個快照中的平均耗時。橫軸表示 3 個選定的靜態方法。

圖 10 給出了線上演算法 NSGA+AIUA（N = 5）與離線演算法 TOA 的時間對比。從結果可以看出，作者提出的所有增量演算法都比現有的靜態方法快得多。

在這一部分中，作者研究 Incre-2dSE 與當前靜態演算法之間的差距。目前主流的結構熵度量靜態演算法稱為結構熵最小化（SEM），是一種以結構熵為目標函式的靜態圖 k 維編碼樹的貪心構造演算法。作者在六個資料集上的所有時間戳上度量了 Incre-2dSE（NAGA/NSGA+AIUA）和 2d-SEM 的結構熵，如圖 11 所示。

作者還評估了兩種近似一維結構熵度量方法，即全域性聚集和區域性傳播，在兩個人工資料集上的時間消耗（ER 資料集和 Cycle 資料集）。耗時實驗結果如圖 12 所示。

除以上列出的實驗結果之外，作者還進行了更新閾值分析、魯棒性分析、收斂性分析。這些分析的結果表明，①設定更新的閾值可以提高效率，並更好地適應頻繁更改的圖形；②本文的增量演算法使結構熵保持在一個穩定和較低的水平上，對不斷增加的噪聲具有很高的魯棒性；③區域性差值總是小於它的上界，有力地支援了局部變化量及其一階絕對矩的收斂性。

本文提出了兩種新的動態調整策略，即樸素調整策略和節點偏移策略，以分析更新的結構熵，並逐步調整原有的社區劃分，使其朝著更低的結構熵方向發展。作者還實現了一個增量框架，即支援更新的二維結構熵的即時度量。進一步，作者討論了提出的方法在無向加權圖上的推廣，以及在有向加權圖上的一維結構熵計算。在未來，作者的目標是開發更多的動態調整策略，用於層次化社區劃分和高維結構熵的增量度量演算法。

篇幅原因，我們在本文中省略了諸多細節，更多細節可以在論文中找到。感謝閱讀！