Blind Identification of Graph Filters

Abstract

Network processes are often represented as signals defined on the vertices of a graph. To untangle the latent structure of such signals, one can view them as outputs of linear graph filters modeling underlying network dynamics. This paper deals with the problem of joint identification of a graph filter and its input signal, thus broadening the scope of classical blind deconvolution of temporal and spatial signals to the less-structured graph domain. Given a graph signal $\mathbf{y}$ modeled as the output of a graph filter, the goal is to recover the vector of filter coefficients $\mathbf{h}$, and the input signal $\mathbf{x}$ which is assumed to be sparse. While $\mathbf{y}$ is a bilinear function of $\mathbf{x}$ and $\mathbf{h}$, the filtered graph signal is also a linear combination of the entries of the lifted rank-one, row-sparse matrix $\mathbf{x}{\mathbf{h}}^T$. The blind graph-filter identification problem can thus be tackled via rank and sparsity minimization subject to linear constraints, an inverse problem amenable to convex relaxations offering provable recovery guarantees under simplifying assumptions. Numerical tests using both synthetic and real-world networks illustrate the merits of the proposed algorithms, as well as the benefits of leveraging multiple signals to aid the blind identification task.

References in corpus (3)

• Cooperative Game Theory Approaches for Network Partitioning
• Discrete Signal Processing on Graphs
• A Unified Framework for Identifiability Analysis in Bilinear Inverse Problems with Applications to Subspace and Sparsity Models

Cited by in corpus (27)

• Graph Learning: A Survey
• Learning graphs from data: A signal representation perspective
• Stationary Graph Processes and Spectral Estimation
• Fast Resampling of 3D Point Clouds via Graphs
• Graph Signal Processing: History, Development, Impact, and Outlook
• Signal Processing on Higher-Order Networks: Livin' on the Edge ... and Beyond
• Spectral Domain Sampling of Graph Signals
• Spectral Projector-Based Graph Fourier Transforms
• Two-Channel Critically-Sampled Graph Filter Banks With Spectral Domain Sampling
• A Directed Graph Fourier Transform with Spread Frequency Components
• Invariance-Preserving Localized Activation Functions for Graph Neural Networks
• Joint Inference of Multiple Graphs from Matrix Polynomials
• Graph-signal Reconstruction and Blind Deconvolution for Structured Inputs
• Exact Blind Community Detection from Signals on Multiple Graphs
• Robust Graph Filter Identification and Graph Denoising from Signal Observations
• Structural-constrained Methods for the Identification of Unobservable False Data Injection Attacks in Power Systems
• Joint Network Topology Inference in the Presence of Hidden Nodes
• An Underparametrized Deep Decoder Architecture for Graph Signals
• Signal Processing on the Permutahedron: Tight Spectral Frames for Ranked Data Analysis
• Signal Processing on Directed Graphs
• Blind Community Detection from Low-rank Excitations of a Graph Filter
• Graph Blind Deconvolution with Sparseness Constraint
• Blind Demixing of Diffused Graph Signals
• Identifying First-order Lowpass Graph Signals using Perron Frobenius Theorem
• Estimating Network Processes via Blind Identification of Multiple Graph Filters
• Graph-LDA: Graph Structure Priors to Improve the Accuracy in Few-Shot Classification
• Rank-One Measurements of Low-Rank PSD Matrices Have Small Feasible Sets