本文介绍来自北京航空航天大学彭浩老师团队发表在Artificial Intelligence Journal（AIJ） 2024上的一篇文章“Incremental Measurement of Structural Entropy for Dynamic Graphs”。为了解决目前的方法不支持动态编码树更新和增量结构熵计算的问题，
作者提出一种新的增量度量框架 - Incre-2dSE
，它可以动态调整社区划分，支持更新的二维结构熵的实时测量。作者在人工和现实世界的数据集上进行了广泛的实验，实验结果证明，该增量算法有效地捕捉了社区的动态演变，减少了时间消耗，并提供了良好的可解释性。
论文名称：
Incremental Measurement of Structural Entropy for Dynamic Graphs
论文链接：
https://doi.org/10.48550/arXiv.2207.12653
代码链接：
https://github.com/SELGroup/IncreSE
一、引言
近年来，有学者提出一种基于编码树的图结构信息度量，即结构熵，用于发现图中嵌入的自然层次结构。结构熵在生物数据挖掘、信息安全、图神经网络等领域得到了广泛的应用。
在动态场景中，一个图在时间序列中从初始状态演变为许多更新的图。为了有效地度量不断变化的社区划分的质量，我们需要在任何给定时间增量地计算更新的结构熵。不幸的是，由于两个挑战，目前的结构熵方法不支持有效的增量计算。
挑战 1：为每个更新的图重建编码树将导致大量的时间消耗
为了解决这个问题，作者提出了两种二维编码树的动态调整策略，即
朴素调整策略
和
节点移位调整策略
。前者保持原有的社区划分，支持理论结构熵分析；后者基于结构熵最小化原则，通过在社区之间移动节点，动态调整社区划分。
挑战 2：传统定义的结构熵计算具有较高的时间复杂度
为了解决这个问题，作者设计了一个增量框架，即
Incre-2dSE
，用于有效地测量更新的二维结构熵。具体而言，Incre-2dSE首先利用两种动态调整策略生成调整量，即重要统计量从原始图到更新图的变化，然后利用调整量通过新设计的增量公式计算更新后的结构熵。此外，作者还将增量方法推广到无向加权图，并对有向加权图的一维结构熵的计算进行了详细的讨论。
二、方法
图 1 Incre-2dSE与传统离线算法的示意图
2.1 二维编码树的动态调整策略
2.1.1 朴素调整策略
朴素调整策略包括两部分：边缘策略和节点策略。边缘策略规定增量边不会改变编码树的结构；节点策略规定，当一个新节点
与已有节点
连接时，且
对应二维编码树中的叶节点
，即
时，将设置一个标签为
的新叶节点
作为
父节点的直接后继节点，而不是另一个1高度的节点。我们可以从群体的角度来描述编码树的修改。
具体来说，增量边不改变现有节点的社区，而新节点被分配到其邻居的社区，而不是另一个任意社区。显然，给定大小为
的增量序列，我们可以在时间复杂度为
的情况下得到更新后的编码树，即更新后的社区划分。
在这一部分中，作者引入了全局不变量和局部差分两个量，通过朴素平差策略实现了更新结构熵的逼近和快速增量计算。对图
施加大小为
的增量序列
，采用朴素调整策略得到新的图
及其对应的二维编码树
，更新后的二维结构熵可表示为：
然而，增量大小
会影响上式中求和方程中的所有项。因此，更新和计算过程的成本至少为
，当图变得非常大时，这个成本是巨大的。一种直观的尝试是在更新的结构熵和原始的结构熵之间做出区别，试图在
中计算增量熵。然而，由于在上式的所有项中
都变为
，因此很难从差分方程中推导出简洁的
公式。
为了解决这个问题，作者在这里引入了全局不变量和局部差分。作者将全局不变量定义为近似更新的结构熵，局部差分定义为更新后的结构熵与全局不变量之差，也可视为近似误差。总的来说，通过计算和求和全局不变量和局部差分，可以在
内计算出更新后的二维结构熵。
2.1.2 节点移位调整策略
虽然朴素调整策略可以快速获得更新后的二维编码树及其相应的结构熵，但我们仍然需要一种更有效的策略来获得较低结构熵的更好的社区划分。因此，作者提出了另一种新的动态调整策略，即节点移位，通过迭代地将节点移动到其最优偏好社区。与单纯调整策略不同，边缘变化可以改变现有节点的社区，使结构熵最小化。此外，该策略支持同时增加多个边和删除现有边。因此，节点移位调整策略完全克服了朴素调整策略的局限性。
首先将最优偏好社区（OPC）定义为目标节点的最佳社区，即如果目标节点进入其OPC，则总体二维结构熵与OPC以外的其他社区相比必须最低。则节点移位调整策略可描述为：
-
-
-
将涉及的节点更新为与移位节点连接但在不同社区的所有节点，然后重复步骤（2）。
2.2 Incre-2dSE：增量测量框架
图1展示了增量测量框架（包括初始化和测量两个阶段）和传统离线算法（TOA）。Incre-2dSE的目的是在给定原始图、原始编码树和增量序列的情况下，在动态调整社区划分的同时，有效地度量更新后的二维结构熵。
2.2.1 阶段1：初始化
给定图
为稀疏矩阵，其二维编码树由如下字典表示：{社区ID 1：节点列表1，社区ID 2：节点列表2，…}时，可以很容易地获取并保存结构数据，其时间复杂度为
。然后使用保存在
中的结构数据计算结构表达式。总的来说，初始化阶段需要总时间复杂度为
。
2.2.2 阶段2：测量
在这个阶段，我们首先需要生成从
到
的调整。通过提出的两种动态调整策略，作者提供了两种算法来生成调整量，即朴素调整量生成算法（NAGA）和节点移位调整量生成算法（NSGA）（图1中的①）。两种算法的输入都是原始图的结构数据和一个增量序列，输出是一个调整。NAGA的时间复杂度为
，因为它需要在增量序列中遍历
条边，而每条边只需要花费
。
在NSGA中，我们首先需要
来初始化调整。其次，在节点移动部分，我们需要确定所有涉及节点的OPC，这需要花费
。此步骤重复
次，时间开销为
，其中
表示第
次迭代中涉及的节点数。由于大多数情况下
和
，所以NSGA的总时间复杂度为
。
得到调整值后，可以增量计算更新后的二维结构熵:
为了实现上述增量计算过程，作者还提供了基于调整的增量更新算法（AIUA）（图1中的②）。给定输入，即原始图的结构数据和结构表达式以及更新后的图的调整，我们可以增量计算更新后的二维结构熵，并在新的调整到来时有效地更新结构数据和结构表达式，为下一个AIUA过程做好准备。更新结构数据的时间复杂度为
。更新结构表达式的时间复杂度为
。计算更新后的二维结构熵的时间复杂度为
。综上，AIUA的总时间复杂度为
。
2.3 基线：传统的离线算法（TOA）
传统的离线算法（TOA）对每一个更新的图重构编码树，并通过定义计算更新后的二维结构熵。TOA由以下四个步骤组成。首先，将原始图与增量序列结合生成更新后的图（图1中的a）。其次，使用几种不同的静态社团检测算法，如Infomap、Louvain、Leiden，将图节点集划分为社团，构建二维编码树（图1中的b）。第三，对更新后的图的节点级、社团级、图级结构数据进行计数并保存（图1中的c）。更新后的结构熵通过式1计算（图1中的d）。TOA的总时间成本为
加上所选社团检测算法的成本。
作者给出了传统离线算法的伪代码，如下图所示：
图 2 传统离线算法的伪代码
2.4 复杂图的扩展
作者在文章中讨论了将此方法扩展到无向加权图或有向图的可行性。首先，作者论证了无向加权图的方法可以由无向无权图的方法自然推广。其次，分析了有向图结构熵增量计算范式与无向图结构熵增量计算范式的根本区别，提出了有向加权图一维结构熵增量计算的新方法。
无向加
权图
：
无向加权图结构熵的增量测量方法可以直观、方便地从之前提出的无向无权图结构熵增量测量方法中扩展出来。作者首先介绍了无向加权图的二维结构熵的定义。在此基础上，更新了结构熵调整的定义，提出了新情况下结构熵计算的增量公式。
有向图
：
由于有向图的结构熵测量与无向图的结构熵测量有本质的不同，本文提出的主要方法难以转移到有向图场景中。关键的区别在于有向图需要转换成一个转移矩阵，而平稳分布需要计算。由于二维结构熵的增量计算非常复杂，在这一部分中，作者简要地提出了一种测量有向权图一维结构熵的增量方案。具体来说，首先定义了有向加权图及其非负矩阵表示。然后，引入了有向加权图的结构熵公式。最后，回顾了有向加权图一维结构熵精确或近似计算的传统方法，即特征向量计算和全局聚合，并提出了一种增量迭代逼近算法，即局部传播算法，如图3所示。
在全局聚合中，每次迭代都需要遍历所有的节点和边，这导致了很高的计算冗余。在这一部分中，作者提出了一种快速逼近更新后的一维结构熵的新方法，即局部传播。顾名思义，其关键思想是在下式（3）中使用仅涉及改变的局部节点的信息传播方案，进一步降低聚合过程的冗余度。
图 3 局部传播算法的示意图
三、实验与评估
作者基于动态图形实时监控和社区优化的应用进行了广泛的实验。
3.1 数据集介绍
首先，作者利用“Networkx”（一个Python库）中的随机分区图(random)、高斯随机分区图(gaussian)和随机块模型(SBM)方法生成动态图的3种不同初始状态。之后，通过Hawkes Process对每个初始状态生成增量序列和更新图。霍克斯过程通过假设历史事件可以影响当前事件的发生，对离散序列事件进行建模。
图 4 人工Hawkes数据集生成过程
真实数据集：
对于现实世界的数据集，作者选择了Cit-HepPh、DBLP和Facebook进行实验。对于每个数据集，作者截取了21个连续的快照（一个初始状态和20个更新的图）。由于结构熵仅在连通图上定义，因此只保留每个快照的最大连通分量。总的来说，图5简要显示了人工数据集和真实数据集的统计数据。
图 5 人工数据集和真实数据集的统计描述
3.2 实验结果与分析
3.2.1 应用：动态图形实时监控和社区优化
