提出首个高效可证明收敛的网络拓扑推断方法，适用于节点部分可观测场景。
Network Topology Inference from Smooth Signals Under Partial Observability
- 基于列稀疏或低秩约束设计一阶算法框架
- 理论证明线性收敛，实验速度优于现有方法
- 适合大规模网络拓扑推断，兼具理论与实用价值
从平滑信号中推断网络拓扑是数据科学与工程中的重要问题。现实场景中常面临仅能观测部分节点的挑战。尽管已有研究考虑隐藏节点并提出多种优化框架，但现有方法往往缺乏大规模网络下的实际效率，或无法提供理论收敛保证。本文针对部分可观测条件下的平滑信号拓扑推断问题，提出首个一阶算法框架，包含基于列稀疏正则化与低秩约束的两种变体。我们建立了理论收敛性证明，证明了算法具有线性收敛率。在合成数据与真实数据上的大量实验表明，结果与理论预测一致，不仅实现线性收敛，且相比现有方法显著提升速度。据我们所知，这是首个在部分可观测条件下，针对平滑信号的网络结构推断提出一阶算法框架的工作，兼具线性收敛保证与大规模应用的实用性。
原文摘要 · Abstract (English)
Inferring network topology from smooth signals is a significant problem in data science and engineering. A common challenge in real-world scenarios is the availability of only partially observed nodes. While some studies have considered hidden nodes and proposed various optimization frameworks, existing methods often lack the practical efficiency needed for large-scale networks or fail to provide theoretical convergence guarantees. In this paper, we address the problem of inferring network topologies from smooth signals with partially observed nodes. We propose a first-order algorithmic framework that includes two variants: one based on column sparsity regularization and the other on a low-rank constraint. We establish theoretical convergence guarantees and demonstrate the linear convergence rate of our algorithms. Extensive experiments on both synthetic and real-world data show that our results align with theoretical predictions, exhibiting not only linear convergence but also superior speed compared to existing methods. To the best of our knowledge, this is the first work to propose a first-order algorithmic framework for inferring network structures from smooth signals under partial observability, offering both guaranteed linear convergence and practical effectiveness for large-scale networks.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。