用测地线建模动态图的连续演化,精准检测状态转变。
Geodesics of Dynamic Graphs for Regime Change Detection

- 将图的动态变化视为图空间中的测地线轨迹
- 在真实疫情数据中检测到更贴近外部事件的转折点
- 适合分析社会网络、物理系统等持续演化的复杂时序图
传统动态网络变化点检测假设状态间为突变,忽略了现实中普遍存在的连续演化过程,如社交网络或物理系统。本文首次将‘状态’定义为时间图中一致动力学的时期,并将其表征为图空间中的测地线轨迹。通过定义显著的动力学漂移(包括新轨迹或速度变化)作为状态转变,我们利用图回归方法测量观测图序列相对于端点间估计测地线的累积距离,结合变化点检测算法实现检测。实验在具有可变轨迹与速度的动态网络上验证,优于现有先进模型。进一步在新冠疫情期间的移动数据中分析,结果表明本方法所识别的变化点更契合外部事件。本工作首次实现了图空间中演化状态间的检测,为复杂时序图分析提供了现实且强大的工具。
原文摘要 · Abstract (English)
Traditional change point detection in dynamic networks assumes abrupt transitions between stationary states, overlooking scenarios of continuous evolution which arise in most real-world applications, such as social networks or physical systems. We address this gap by formally defining regimes as periods of coherent dynamics in temporal graphs, which we characterize as trajectories along geodesics in a suitably defined graph space. This original perspective allows us to define regime changes as significant drifts in dynamics, either toward new trajectories or with pace changes. We leverage graph regression methods to measure the cumulative distance of sequences of observed graphs from the estimated geodesics between their endpoints, in the relevant graph space, which we can combine with change point detection algorithms. We present experiments on dynamic networks, with changing trajectories and varying speeds, in which we outperform state of the art change point detection models. Then, we analyse mobility data during the Covid-19 pandemic, and show that our assumptions on regular network evolution lead to change points that are more aligned to external events compared to the outcomes of baseline methods. Our work is the first to model and detect changes between evolving regimes in graph space, providing a realistic and powerful tool for analyzing complex temporal graph data.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。