Robust Graph Filter Identification and Graph Denoising from Signal Observations

Abstract

When facing graph signal processing tasks, the workhorse assumption is that the graph describing the support of the signals is known. However, in many relevant applications the available graph suffers from observation errors and perturbations. As a result, any method relying on the graph topology may yield suboptimal results if those imperfections are ignored. Motivated by this, we propose a novel approach for handling perturbations on the links of the graph and apply it to the problem of robust graph filter (GF) identification from input-output observations. Different from existing works, we formulate a non-convex optimization problem that operates in the vertex domain and jointly performs GF identification and graph denoising. As a result, on top of learning the desired GF, an estimate of the graph is obtained as a byproduct. To handle the resulting bi-convex problem, we design an algorithm that blends techniques from alternating optimization and majorization minimization, showing its convergence to a stationary point. The second part of the paper i) generalizes the design to a robust setup where several GFs are jointly estimated, and ii) introduces an alternative algorithmic implementation that reduces the computational complexity. Finally, the detrimental influence of the perturbations and the benefits resulting from the robust approach are numerically analyzed over synthetic and real-world datasets, comparing them with other state-of-the-art alternatives.

arXiv commentCurrently under review for publication in the IEEE Transactions on Signal Processing journal

References in corpus (13)

• Community structure in social and biological networks
• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Discrete Signal Processing on Graphs
• Renormalization group analysis of the small-world network model
• Stationary Graph Processes and Spectral Estimation
• Signal Processing on Graphs: Causal Modeling of Unstructured Data
• Multivariate Bernoulli distribution
• Forecasting Time Series with VARMA Recursions on Graphs
• Blind Identification of Graph Filters
• Transferability of Spectral Graph Convolutional Neural Networks
• Detecting Central Nodes from Low-rank Excited Graph Signals via Structured Factor Analysis
• Convergence and Stability of Graph Convolutional Networks on Large Random Graphs
• Does the ${\ell }_1$-norm Learn a Sparse Graph under Laplacian Constrained Graphical Models?

Cited by in corpus (1)

• Joint Network Topology Inference in the Presence of Hidden Nodes