北航、滴滴联合提出一种新的增量度量框架，实现动态图结构熵的高效增量计算

1,242 0 0

文章摘要

北京航空航天大学彭浩老师团队在《The journal of Artificial Intelligence》2024年发表的论文“Incremental Measurement of Structural Entropy for Dynamic Graphs”中提出了一种新的增量度量框架——Incre-2dSE，旨在解决现有方法在动态编码树更新和增量结构熵计算方面的不足。该框架能够动态调整社区划分，并实时度量更新后的二维结构熵。通过在人工和现实世界数据集上的广泛实验，研究结果表明，Incre-2dSE算法能有效捕捉社区的动态演化，减少时间消耗，并具有良好可解释性。

结构熵作为一种图结构信息度量方法，已被广泛应用于生物数据挖掘、信息安全、图神经网络等领域。然而，在动态场景中，现有结构熵方法面临两大挑战：一是为每个更新的图重建编码树导致大量时间消耗；二是传统结构熵计算具有高时间复杂度。为了解决这些问题，作者提出了两种二维编码树的动态调整策略——朴素调整策略和节点偏移策略。朴素调整策略通过保持原有社区划分，支持理论结构熵分析；而节点偏移策略则基于结构熵最小化原则，通过移动节点动态调整社区划分。

Incre-2dSE框架包括初始化和度量两个阶段。在初始化阶段，通过结构数据计算结构表达式；在度量阶段，利用两种动态调整策略生成调整量，并通过新设计的增量公式计算更新后的结构熵。此外，作者还将增量方法推广到无向加权图，并针对有向加权图的一维结构熵计算进行了详细讨论。

在实验评估中，作者基于动态图形实时监控和社区优化的应用，在人工和真实世界数据集上进行了广泛的实验。实验结果表明，Incre-2dSE算法在不同静态社区检测方法下，都能有效地优化社区划分并监控相应的二维结构熵。同时，超参数研究表明，节点偏移策略的迭代次数增加，可以进一步降低结构熵，提高社区划分质量。

总体而言，该研究提出的Incre-2dSE框架为动态图的社区划分和结构熵度量提供了一种有效的增量方法，具有重要的理论和应用价值。论文链接为https://doi.org/10.48550/arXiv.2207.12653，代码链接为https://github.com/SELGroup/IncreSE。