Reconstruction of Graph Signals through Percolation from Seeding Nodes

Santiago Segarra, Antonio G. Marques, Geert Leus, Alejandro Ribeiro

Abstract

This paper presents a novel framework for the reconstruction and induction of bandlimited graph signals via a process termed "percolation." Unlike traditional graph signal processing (GSP) which focuses on sampling unknown signals, this work addresses the inverse problem: how to drive a complex network into a desired, known state using sparse, localized interventions. By injecting "seeding" values into a subset of nodes and applying a graph filter, the authors demonstrate that smooth signals can be perfectly reconstructed across various topologies, including social and biological networks. The study explores the trade-offs between seeding density, filter complexity, and noise robustness, providing a mathematical foundation for network control.

Introduction

In classical Digital Signal Processing (DSP), the Nyquist-Shannon sampling theorem provides the theoretical basis for reconstructing continuous signals from discrete samples. As data increasingly resides on irregular structures like social networks, sensor grids, and brain connectomes, Graph Signal Processing (GSP) has emerged to extend these concepts to the graph domain.

While most GSP literature focuses on the sampling problem—estimating an unknown signal from a few observations—this research addresses the induction problem. The goal is to determine how to generate a specific, known target signal across an entire graph by interacting with only a small subset of "seeding" nodes. This has profound implications for network control, such as influencing opinion dynamics in social groups or stimulating specific cognitive states in the brain through localized neurostimulation.

Methodology

The authors propose a two-phase framework for signal induction:

  1. Seeding Phase: Sparse signal values are injected into the graph at specific nodes.
  2. Filtering Phase: A localized graph filter, based on the graph's adjacency or Laplacian matrix (the "graph-shift operator"), is applied. This filter allows the injected values to "percolate" through the network, eliminating unwanted high frequencies and smoothing the signal into the desired target state.

Seeding Architectures

The paper evaluates three distinct architectures for signal injection:

  • Multiple Node - Single Time (MN-ST): $P$ different nodes inject a single value simultaneously.
  • Single Node - Multiple Time (SN-MT): A single node injects $P$ values sequentially over successive time steps.
  • Multiple Node - Multiple Time (MN-MT): A hybrid approach where multiple nodes inject values over multiple time steps.

By leveraging the eigendecomposition of the graph-shift operator, the authors translate the reconstruction problem into the graph frequency domain. This allows for the derivation of exact seeding values and filter coefficients required for perfect reconstruction of bandlimited signals.

Key Theoretical Insights

Seeding vs. Target Values

A critical finding is that seeding values are generally not equal to the target signal values at those nodes. In traditional time-domain interpolation, samples are taken directly from the signal. In graph percolation, however, the seeding values must be mathematically derived to account for the subsequent diffusion process; they act as "drivers" rather than mere samples.

The Oversampling Trade-off

The research identifies a significant relationship between seeding density and communication overhead. By "oversampling"—injecting more seeding values than the theoretical minimum—the degree of the required graph filter can be reduced. Since the filter degree corresponds to the number of communication hops between neighbors, increasing the number of seeding nodes directly lowers the network's internal communication burden.

Robustness in Noisy Environments

When the injection process is subject to noise, the authors discover a counterintuitive selection strategy: the most robust seeding nodes are often those that weakly express the target frequencies. Because these nodes require higher-power injections to influence the network, they naturally achieve a higher Signal-to-Noise Ratio (SNR), leading to more stable reconstruction.

Experimental Results

The framework was validated across synthetic and real-world datasets:

  • Synthetic Erdős-Rényi (ER) Graphs: In constant SNR regimes, the MN-ST scheme demonstrated superior robustness, with a median reconstruction error of 0.048, compared to 0.349 for the SN-MT scheme.
  • Social Networks (Zachary’s Karate Club): To model opinion dynamics, the authors found that the MN-MT scheme was most effective. Influencing three different individuals once proved significantly more efficient than influencing a single individual three times.
  • Brain Networks: Using a 66-region human brain connectome, the authors simulated Transcranial Magnetic Stimulation (TMS) to drive the brain from a resting to an active state. The study identified 1,611 highly robust 6-node seeding configurations. Notably, the Pars Orbitalis (left and right) appeared frequently in optimal setups, suggesting its pivotal role in robust brain state induction.

Discussion and Future Work

While the framework provides a rigorous basis for signal induction, it relies on the assumption that the target signal is strictly bandlimited and the graph topology is known. Furthermore, optimizing node selection in noisy environments remains a computationally intensive, non-convex problem.

Future research directions include the use of convex relaxations (such as $\ell_1$-norm minimization) to handle node selection in larger networks. Additionally, the authors suggest extending the framework to stochastic programming for scenarios where the target signal is drawn from a statistical distribution rather than being a fixed, known value.

Summary updated

Abstract

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.
BibTeX
@article{segarra2015reconstruction,
  author = {Santiago Segarra and Antonio G. Marques and Geert Leus and Alejandro Ribeiro},
  title = {{Reconstruction of Graph Signals through Percolation from Seeding Nodes}},
  journal = {IEEE Trans. Signal Process.},
  year = {2015},
  doi = {10.1109/tsp.2016.2552510},
}
Figure