基于MDL引导的张量分解方法在时序网络中的结构变化点检测

《Pattern Recognition》：Structural Change Point Detection in Temporal Networks via MDL-Guided Tensor Decomposition

　　黄贤斌|胡耀|陈立明|陈永勇|黄月驰中国贵州省贵阳市贵州大学数学与统计学院，邮编550025

摘要
我们提出了一种新的框架，通过整合CANDECOMP/PARAFAC（CP）张量分解和最小描述长度（MDL）原理，用于检测时间网络中的结构变化点。该方法利用时间索引的邻接矩阵构建三阶张量，然后应用CP分解来提取每个时间段内的潜在节点因素和时间因素。在MDL准则下，通过最小化总编码成本来共同估计变化点的数量和位置。与现有的基于相似性或模型的方法相比，我们的方法具有更高的检测精度，并且具备理论一致性保证。大量仿真结果表明，该框架在不同网络拓扑结构中都能保持超过95%的F1分数，即使在信噪比较低的环境中也能保持良好的性能（准确率超过90%）。将该方法应用于曼哈顿的实际交通数据后，成功识别出了日常出行模式中的三个可解释的变化时刻（分别为05:45、10:45和18:15）。我们的方法为动态网络系统中的结构变化分析提供了一种有原则且可扩展的解决方案。

引言
复杂时间网络演化分析已成为现代研究的基石，对于从社交网络[1]到生物系统[2][3]等领域的动态系统建模至关重要。在此背景下，变化点检测——即识别潜在生成机制中的突然转变——对于理解系统动态具有重要意义。研究人员已经探讨了由外部事件引发的结构变化[4]，这些方法在分析电子邮件通信[5]和旅游流量[6]方面有着具体应用。除了社交计算之外，这些方法还被用于描述动态蛋白质相互作用[7]以及全球贸易中的关键转变[8]。它们在识别实体间金融网络中的风险[9]以及监控软件故障检测过程[10]方面同样重要。准确识别这些转变是系统管理的基本方法。

虽然单变量时间序列的变化点检测已经相当成熟，但将这些概念应用于网络数据则面临诸多挑战。例如，经典的累积和（CUSUM）算法[11]主要是为在线序列数据设计的。后续研究通过统计方法和机器学习方法进一步拓展了这一基础[12][13]。最近在模式识别领域的研究则通过探索动态图表示和异常检测进一步推动了这一领域的发展[14]。然而，传统技术[15]通常将数据快照视为独立向量，因此往往无法捕捉动态图中固有的复杂拓扑依赖性和高阶相关性。随着现代数据规模的不断扩大，迫切需要开发专门针对时间网络数据的高效算法，因为时间网络具有与单变量时间序列不同的独特拓扑特性。

为了解决这些挑战，我们提出了一种基于MDL引导的张量分解框架，用于结构变化点检测。(1)该框架利用CP分解来捕捉潜在的拓扑变化（如社区切换）。(2)非参数MDL准则无需先验知识即可自适应地确定变化点。(3)我们为估计出的变化点数量和位置的一致性提供了理论证明。(4)大量实验验证了该方法对噪声和稀疏性的鲁棒性，以及在真实交通数据上的有效性。

本文的其余部分安排如下：第2节回顾现有文献。第3节详细阐述张量CP分解和MDL编码的理论框架。第4节建立理论一致性保证。第5节报告大量的仿真研究和比较分析结果。第6节利用曼哈顿出租车数据集展示该方法的实际应用价值。最后，第7节对整个研究进行总结。

相关工作
时间网络变化点检测的研究主要分为两类：非参数的基于相似性的方法和参数化的基于模型的方法。非参数方法避免了明确的分布假设，通常将变化检测重新表述为比较或分类一系列图快照的问题。常见的方法包括使用连体图神经网络[16]的基于相似性的检测方法、基于图距离的度量方法[8]，以及线性化方法。

结构变化的定义
对于网络数据，会在每个时间点捕获网络快照。基于这些快照，我们可以定义Gt=(N,Et)，其中t=1,…,T，N表示网络数据中的节点集合，通常保持不变。Et则表示时间t时节点之间的边集合，在大多数情况下，边的权重会随时间变化。

对于时间网络，这也可以表示为一个三阶邻接张量Y=(aijk)∈RN×N×T，其中aijk表示节点间的连接强度。在本研究中，

理论保证
设真正的变化点数量为m*，真正的变化点位置为Γ*={τ0,τ1,?,τm*}。进一步假设变化点位置位于单位区间[0, 1]内，该区间由分位数λ*={λ1*,λ2*,?,λm**}表示，其中τj=?λj*T?，j=0,1,?,m*，这里的??·??表示向下取整函数，即小于或等于给定值的最大整数。在后续的理论分析中，λ将用来代替Γ。

根据[30]中的要求，对于每一个

仿真研究与性能评估
本节通过全面的数值评估来验证所提框架的有效性和可靠性。实验设计围绕两个主要维度展开。第一个维度侧重于内在鲁棒性，即评估该方法在不同条件下的变化点数量和位置估计精度，这些条件包括不同的噪声水平、信号强度、网络规模和稀疏程度。第二个维度涉及比较分析。

真实数据分析
为了在真实系统中验证该框架，我们分析了曼哈顿黄色出租车需求数据集[1]。我们利用曼哈顿市中心的60个相邻区域构建了一个时间网络，其中加权边表示各区域之间的乘客流动情况。按照标准做法[36]，我们使用了2014年4月16日的数据，将24小时的时间段划分为96个15分钟的间隔（T=0到T=96）。由此得到的邻接矩阵

结论与未来工作
本研究通过将CP张量分解与最小描述长度（MDL）原理相结合，提出了一种用于时间网络结构变化点检测的有原则的框架。该方法通过提取潜在的节点因素和时间因素，能够捕捉从全局密度变化到局部社区重组等各种复杂的结构演变，并通过动态规划共同估计出最佳的变化点数量和位置。同时，还提供了全面的理论分析。

CRediT作者贡献声明
黄贤斌：撰写——初稿、可视化、研究。胡耀：撰写——审阅与编辑、正式分析。陈立明：方法论、概念设计。陈永勇：监督、数据整理。黄月驰：项目管理、方法论。

利益冲突声明
作者声明没有已知的财务利益或个人关系可能影响本文所述的工作。

致谢
本研究得到了贵州省人工智能与类脑计算重点实验室的支持，我们对此表示感谢。此外，本研究还得到了国家自然科学基金（项目编号12161016）、贵州省基础研究计划（自然科学）（项目编号QianKeHeJiChu-ZK[2024] YiBan082）以及贵州省教育厅青年科技人才成长计划（项目编号Qianjiaoji）的支持。