无需显式建模隐藏节点,也能从部分观测信号中准确恢复图结构。
Learning Graph from Smooth Signals under Partial Observation: A Robustness Analysis
- 基于信号平滑性构建图学习方法,隐含抵抗隐藏节点干扰
- 在部分观测下,可准确恢复原始图拓扑结构
- 适用于信号平滑的网络系统,如社交或传感器网络
从节点信号中学习网络结构对图信号处理和机器学习的下游任务至关重要。隐藏节点的信号不可观测可能破坏图估计结果。尽管已有研究通过显式建模隐藏节点来增强图学习的鲁棒性,但对“朴素”、忽略隐藏节点的方法的鲁棒性分析仍不充分。本文证明,传统的图拓扑学习方法在低通滤波信号的部分观测下具有隐式鲁棒性。通过将受限等距性质(RIP)扩展至图学习目标中的Dirichlet能量函数,我们表明基于平滑性的图学习方法(如GL-SigRep)在部分观测条件下仍能恢复观测节点对应的真值图结构。合成与真实数据实验验证了该结论。
原文摘要 · Abstract (English)
Learning the graph underlying a networked system from nodal signals is crucial to downstream tasks in graph signal processing and machine learning. The presence of hidden nodes whose signals are not observable might corrupt the estimated graph. While existing works proposed various robustifications of vanilla graph learning objectives by explicitly accounting for the presence of these hidden nodes, a robustness analysis of "naive", hidden-node agnostic approaches is still underexplored. This work demonstrates that vanilla graph topology learning methods are implicitly robust to partial observations of low-pass filtered graph signals. We achieve this theoretical result through extending the restricted isometry property (RIP) to the Dirichlet energy function used in graph learning objectives. We show that smoothness-based graph learning formulation (e.g., the GL-SigRep method) on partial observations can recover the ground truth graph topology corresponding to the observed nodes. Synthetic and real data experiments corroborate our findings.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。