# Reconstruction of Graph Signals through Percolation from Seeding Nodes

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 30 Jul 2015.

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

- [Graph Learning: A Survey](https://mlsanity.com/paper/2105.00696/) (2021)
- [Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond](https://mlsanity.com/paper/2101.05510/) (2021)
- [Signal processing on simplicial complexes](https://mlsanity.com/paper/2106.07471/) (2021)
- [Filter Learning for Subgraphs: Algebras and Performance Risk Bounds](https://mlsanity.com/paper/2607.21263/) (2026)

## Abstract (arXiv)

New schemes to recover signals defined in the nodes of a graph are proposed. Our focus is on reconstructing bandlimited graph signals, which are signals that admit a sparse representation in a frequency domain related to the structure of the graph. Most existing formulations focus on estimating an unknown graph signal by observing its value on a subset of nodes. By contrast, in this paper, we study the problem of reconstructing a known graph signal using as input a graph signal that is non-zero only for a small subset of nodes (seeding nodes). The sparse signal is then percolated (interpolated) across the graph using a graph filter. Graph filters are a generalization of classical time-invariant systems and represent linear transformations that can be implemented distributedly across the nodes of the graph. Three setups are investigated. In the first one, a single simultaneous injection takes place on several nodes in the graph. In the second one, successive value injections take place on a single node. The third one is a generalization where multiple nodes inject multiple signal values. For noiseless settings, conditions under which perfect reconstruction is feasible are given, and the corresponding schemes to recover the desired signal are specified. Scenarios leading to imperfect reconstruction, either due to insufficient or noisy signal value injections, are also analyzed. Moreover, connections with classical interpolation in the time domain are discussed. The last part of the paper presents numerical experiments that illustrate the results developed through synthetic graph signals and two real-world signal reconstruction problems: influencing opinions in a social network and inducing a desired brain state in humans.