同时补全缺失信号并推断动态图结构,效果优于现有方法。
Learning Time-Varying Graphs from Incomplete Graph Signals
- 联合优化图拉普拉斯与信号缺失值,双向信息流动提升鲁棒性。
- 引入时序平滑正则,抑制噪声引起的虚假变化,支持渐进演化。
- 适合高缺失率数据场景,尤其适用于大规模动态网络分析。
本文针对从部分观测的图信号中联合推断时变网络拓扑和补全缺失数据这一挑战性问题,提出统一的非凸优化框架,同时恢复一系列图拉普拉斯矩阵并重建未观测信号。与传统解耦方法不同,该集成方法在图域与信号域间实现双向信息传递,在高缺失率情形下表现出更优鲁棒性。为捕捉真实网络动态,对拉普拉斯序列引入融合Lasso正则,通过惩罚连续变化量来促进时序平滑,既防止噪声引发的虚假波动,又允许渐进式拓扑演化。针对联合优化问题,设计高效近端交替方向乘子法(PADMM),利用问题结构实现图与信号子问题的闭式求解,保障大规模网络与长时序的可扩展性。理论上,尽管存在非凸性,仍证明该算法收敛至驻点;并给出非渐近统计保证,提供以样本量、信号平滑度和图固有时序变异性为函数的图估计误差高概率上界。大量数值实验验证方法有效性,表明其在收敛速度与图学习与信号恢复联合精度方面显著优于现有最优基线。
原文摘要 · Abstract (English)
This paper tackles the challenging problem of jointly inferring time-varying network topologies and imputing missing data from partially observed graph signals. We propose a unified non-convex optimization framework to simultaneously recover a sequence of graph Laplacian matrices while reconstructing the unobserved signal entries. Unlike conventional decoupled methods, our integrated approach facilitates a bidirectional flow of information between the graph and signal domains, yielding superior robustness, particularly in high missing-data regimes. To capture realistic network dynamics, we introduce a fused-lasso type regularizer on the sequence of Laplacians. This penalty promotes temporal smoothness by penalizing large successive changes, thereby preventing spurious variations induced by noise while still permitting gradual topological evolution. For solving the joint optimization problem, we develop an efficient Proximal Alternating Direction Method of Multipliers (PADMM) algorithm, which leverages the problem's structure to yield closed-form solutions for both the graph and signal subproblems. This design ensures scalability to large-scale networks and long time horizons. On the theoretical front, despite the inherent non-convexity, we establish a convergence guarantee, proving that the proposed PADMM scheme converges to a stationary point. Furthermore, we derive non-asymptotic statistical guarantees, providing high-probability error bounds for the graph estimator as a function of sample size, signal smoothness, and the intrinsic temporal variability of the graph. Extensive numerical experiments validate the approach, demonstrating that it significantly outperforms state-of-the-art baselines in both convergence speed and the joint accuracy of graph learning and signal recovery.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。