基于重整化群的复杂网络长时动力学预测
论文标题：Predicting Long-term Dynamics of Complex Networks via Identifying Skeleton in Hyperbolic Space
作者：Ruikun Li, Huandong Wang, Jinghua Piao, Qingmin Liao, Yong Li
会议：KDD 2024
论文链接：
https://dl.acm.org/doi/10.1145/3637528.3671968
代码链接：
https://github.com/tsinghua-fib-lab/DiskNet
现实世界中许多复杂系统的演化行为可以建模为复杂网络上的动力学过程，例如大脑、社交网络和生态系统。这些现实网络中通常存在大量节点和边。一方面，大规模网络显着增加了复杂网络上推理和估计任务的计算复杂度。另一方面，大量不重要的节点作为干扰变量会阻止我们揭示网络的有效动力学。因此，本文的核心内容是：给定一个任意复杂的网络，我们要找到它的低维骨架，并在该骨架上以高预测性能和低计算成本对粗尺度长期动力学进行建模和预测。
背景
为现实世界的大规模复杂网络识别低维骨架作为其主干是一个长期存在的问题，因为其有利于缓解存储压力、降低分析难度、提升计算效率和预测表现。统计物理和机器学习领域分别通过理论分析和数据驱动的方式给出不同的解决方案，例如复杂网络的重整化群和基于下游任务的图粗化。然而，这些方法忽略了节点的动力学，无法建模网络上节点的演化行为。
建模复杂网络上节点动力学的网络骨架面临两个基本挑战：
（1）如何确定哪些节点到同一个超节点，从而同时保留网络的拓扑和动力学特性。这涉及分配矩阵的计算。（2）如何设计原始网络和网络骨架的可逆映射，从而既能聚合原始节点特征到超节点，并且能够从超节点恢复回原始节点。聚合意味着粗化和不可避免的信息损失，而恢复时需要克服信息损失重建原始节点级别的信息。
面向长时预测的基本目标，为解决上述挑战，我们融合了现有物理知识和深度学习模型的优势，提出了一种新颖的深度学习模型来识别蕴含网络节点长时动力学的低维骨架，并在其上预测长时演化过程（见下图）。
图1 基于网络骨架预测节点长时动力学示意图
模型
我们提出动力学不变骨架神经网络（DiskNet），通过识别双曲空间中的骨架来预测复杂网络的长时动力学，整体框架如图2所示。根据上述挑战，我们：
首先提出了双曲重整化群模块，该模块利用双曲几何强大的表示能力来捕获节点的拓扑和动力学相似性，从而计算自适应分配矩阵，指导节点分配和动态聚合。
最后设计了基于度的聚类超分辨率模块来把动力学表征提升回原始节点级别。
图2 所提模型的流程框架
针对如何确定节点分配矩阵问题的挑战，我们在双曲重整化群模块中为每个原始节点和超节点维护可学习的特征向量，并以庞加莱球空间作为度量，从而在端到端的学习过程中捕获动力学特性。这些特征作为自适应分配矩阵计算模块的输入用于计算一个分配矩阵，表示哪个原始节点被分配到哪个超节点。此外，我们采用统计物理学的理论方法识别的节点特征和网络骨架作为节点特征向量和分配矩阵计算模块的初始化和预训练标签，从而为所识别的骨架引入原始拓扑特征。
针对聚合——恢复过程中信息损失的挑战，我们设计了基于度的聚类超分辨率模块来从骨架上粗粒度的预测结果恢复出每个原始节点的预测结果。这一设计受到其他物理学相关工作的启发，即现实世界网络的节点动力学相似性与度的相似性成正相关。我们把具有相似的度的节点重新归为一簇，并为每个簇分别维护一个超分辨率网络。原始节点的历史轨迹和其超节点的粗粒度预测轨迹合并作为超分辨率的输入，从而同时考虑其个性化特征和长时粗粒度演化趋势。
实验
我们的实验对象是来自不同学科的3种动力学方程在5个真实网络和2个合成网络上的演化过程。动力学方程涵盖细胞尖峰活动和异步谐振子的同步过程，网络拓扑包括北美电网、果蝇脑网络、全球机场网络、社交媒体网络和万维网跳转网络。
我们首先在第一部分实验中评估了DiskNet和其他最先进网络动力学预测方法的表现，结果如表1所示。所有模型观测过去12步演化轨迹并预测未来120步的轨迹。DiskNet的长时预测表现在所有场景都取得了最优或次优，这一方面表明识别低维骨架对于长时预测的提升，另一方面也反向验证了DiskNet识别动力学骨架的有效性。
表1 网络节点动力学的长时预测结果
在第二部分实验中，我们可视化了DiskNet在同一个网络上面对不同动力学时，计算的分配矩阵的差异，并以统计物理学的理论方法进行对比，如图3所示。物理学理论方法忽略节点动力学信息而只保留原始网络拓扑特征，因此识别的骨架始终是一样的。而DiskNet面对不同动力学时，原始节点和超节点的分配关系是不同的，并且呈现出按庞加莱空间的径坐标和角坐标分层的特点。
图3 从不同网络节点动力学识别的骨架
第三部分实验中，我们使用不同的网络降维/聚合/剪枝模块代替DiskNet的双曲重整化群模块，验证不同的骨架识别方法在节点动力学长时预测任务的表现。结果如表2所示。启发式方法、图池化方法和物理学重整化群方法所识别的网络骨架无法实现最佳的长时预测表现。
表2 在不同方法识别的网络骨架上预测节点动力学的表现
接下来，我们对DiskNet的计算开销进行分析。我们对比了所有基于神经常微分方程的模型随着网络规模的扩大，其计算时间开销的变化，如图4所示。当降维率设置小于10%时，DiskNet在网络规模翻倍时，计算开销的增长不到50%，相比之下其他Baseline的计算成本成倍提升。这验证了在低维骨架上进行动力学建模的效率增益。
图4 推理时间随网络规模的变化曲线
最后，我们通过一系列消融实验和鲁棒性分析验证了DiskNet每个模块的贡献和对超参数取值的鲁棒性，详细结果可见原文。
参考文献
[1] García-Pérez, Guillermo, Marián Boguñá, and M. Ángeles Serrano. "Multiscale unfolding of real networks by geometric renormalization." Nature Physics 14.6 (2018): 583-589.
[2] Zang, Chengxi, and Fei Wang. "Neural dynamics on complex networks." Proceedings of the 26th ACM SIGKDD international conference on knowledge discovery & data mining. 2020.
[3] Thibeault, Vincent, Antoine Allard, and Patrick Desrosiers. "The low-rank hypothesis of complex systems." Nature Physics 20.2 (2024): 294-302.
[4] Prasse, Bastian, and Piet Van Mieghem. "Predicting network dynamics without requiring the knowledge of the interaction graph." Proceedings of the National Academy of Sciences 119.44 (2022): e2205517119.
