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

AIGC动态1周前发布 ai-front
95 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。

豆包-智能助手

原文和模型


【原文链接】 阅读原文 [ 5500字 | 22分钟 ]
【原文作者】 AI前线
【摘要模型】 moonshot-v1-32k
【摘要评分】 ★★★★★

© 版权声明
讯飞星火大模型

相关文章

星火内容运营大师

暂无评论

暂无评论...