# Learning Graph from Smooth Signals under Partial Observation: A Robustness Analysis

arXiv: https://arxiv.org/abs/2509.14887 · HTML: https://mlsanity.com/paper/2509.14887/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 25 references that are in the map.
- First posted on arXiv 18 Sep 2025.

## Builds on (most cited first, 13 of 13)

- [Sketching as a Tool for Numerical Linear Algebra](https://mlsanity.com/paper/1411.4357/) (2014)
- [How to learn a graph from smooth signals](https://mlsanity.com/paper/1601.02513/) (2016)
- [Learning graphs from data: A signal representation perspective](https://mlsanity.com/paper/1806.00848/) (2018)
- [Learning heat diffusion graphs](https://mlsanity.com/paper/1611.01456/) (2016)
- [A User Guide to Low-Pass Graph Signal Processing and its Applications](https://mlsanity.com/paper/2008.01305/) (2020)
- [Learning Graphs from Smooth and Graph-Stationary Signals with Hidden Variables](https://mlsanity.com/paper/2111.05588/) (2021)
- [Random sampling of bandlimited signals on graphs](https://mlsanity.com/paper/1511.05118/) (2015)
- [Joint Network Topology Inference in the Presence of Hidden Nodes](https://mlsanity.com/paper/2306.17364/) (2023)
- [Blind Community Detection from Low-rank Excitations of a Graph Filter](https://mlsanity.com/paper/1809.01485/) (2018)
- [Detecting Central Nodes from Low-rank Excited Graph Signals via Structured Factor Analysis](https://mlsanity.com/paper/2109.13573/) (2021)
- [A centrality measure for quantifying spread on weighted, directed networks](https://mlsanity.com/paper/2303.09684/) (2023)
- [Learning the Causal Structure of Networked Dynamical Systems under Latent Nodes and Structured Noise](https://mlsanity.com/paper/2312.05974/) (2023)
- [Network Topology Inference from Smooth Signals Under Partial Observability](https://mlsanity.com/paper/2410.05707/) (2024)

## Built on by (most cited first, 1 of 1)

- [From topology learning to graph generation: A unifying perspective](https://mlsanity.com/paper/2609.02286/) (2026)

## Abstract (arXiv)

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.