In graph signal processing, we typically assume the underlying network—whether it is a social graph, a brain connectivity map, or a sensor grid—is a fixed, known entity. We then use this "ground truth" to filter, denoise, or interpolate signals. However, as Marques et al. point out, real-world graphs are rarely perfect; they are often inferred from noisy data, subject to link failures, or entirely unknown.
This creates a circular dependency: to understand the signal, you need the graph; to learn the graph, you need the signal. The emerging research direction of joint topology and signal estimation breaks this cycle by treating both the network structure and the data as interdependent variables in a single optimization framework.
The Failure of Sequential Pipelines
The traditional approach to "dirty" data is sequential: first, denoise the signal or impute missing values, then construct the graph. Mayiami et al. argue that this leads to "noise-induced topology error accumulation." Because the graph construction step is highly sensitive to signal noise, even minor errors in the initial denoising phase can lead to significant inaccuracies in the reconstructed network.
By contrast, joint estimation allows the signal processing task to inform the denoising of the graph structure itself. As Giannakis et al. demonstrate, when we estimate topology and signals simultaneously, the inferred graph acts as a sophisticated regularizer for the signal, while the signal provides the evidence needed to refine the graph.
The Mechanics of Mutual Refinement
How do these systems actually learn both at once? The most common mechanism is an alternating optimization scheme. In this loop, the model performs two steps iteratively:
- Signal Denoising/Imputation: Given the current graph, the model smooths the signal. For example, Shi and Mishne use low-pass graph filtering to estimate missing observations based on the current topology.
- Topology Refinement: Given the denoised signal, the model updates the graph edges to better reflect the signal's smoothness or structural constraints.
This biconvex approach, as described by Chau et al., ensures that the learned graph is consistent with a completed version of the data. In high-dimensional settings like brain imaging, Liu et al. show that this synergy improves the estimation of both intrinsic patterns and data connectivity, outperforming methods that treat the tasks in isolation.
Robustness to Real-World Corruption
Joint estimation is particularly powerful when data is not just noisy, but fundamentally "broken."
- Outliers and Sparse Errors: Kang et al. propose decomposing a noisy input matrix into a low-rank "clean" component and a sparse error component while simultaneously optimizing the graph. This prevents outliers from warping the inferred topology.
- Missing Links: In biological networks, many associations are unknown. Zou et al. use iterative refinement to predict missing microRNA-disease associations, while Chen et al. show that jointly detecting noisy links and predicting missing ones creates a "mutual supervision" that improves overall network reconstruction.
- Non-Gaussian Noise: While many models assume simple noise, Shi and Mishne introduced the GLEN framework, which uses exponential family distributions to handle counts, binary values, and other diverse data types.
Beyond Static Graphs
The frontier of this field involves dynamic and complex structures. Javaheri et al. have extended joint estimation to time-varying graphs, allowing for the tracking of evolving networks even when faced with sensor failures or heavy-tailed financial data. Similarly, Marques et al. have applied these principles to "blind deconvolution," recovering both source signals and the diffusion process (the graph filter) from noisy observations.
By treating the graph not as a rigid input but as a flexible, optimizable variable, these methods transform the "curse" of noisy data into a joint inference problem where the signal and the structure work together to reveal the underlying truth.
Key Foundational Work
Robust Graph Learning from Noisy Data (2018) — contributed 1 concept elements to this direction.
Simultaneous low-rank component and graph estimation for high-dimensional graph signals: Application to brain imaging (2017) — contributed 1 concept elements to this direction.
Prediction of potential disease-associated microRNAs using structural perturbation method (2018) — contributed 1 concept elements to this direction.