Graph topology inference based on sparsifying transform learning

Abstract

Graph-based representations play a key role in machine learning. The fundamental step in these representations is the association of a graph structure to a dataset. In this paper, we propose a method that aims at finding a block sparse representation of the graph signal leading to a modular graph whose Laplacian matrix admits the found dictionary as its eigenvectors. The role of sparsity here is to induce a band-limited representation or, equivalently, a modular structure of the graph. The proposed strategy is composed of two optimization steps: i) learning an orthonormal sparsifying transform from the data; ii) recovering the Laplacian, and then topology, from the transform. The first step is achieved through an iterative algorithm whose alternating intermediate solutions are expressed in closed form. The second step recovers the Laplacian matrix from the sparsifying transform through a convex optimization method. Numerical results corroborate the effectiveness of the proposed methods over both synthetic data and real brain data, used for inferring the brain functionality network through experiments conducted over patients affected by epilepsy.

arXiv commentSubmitted to IEEE Transactions on Signal Processing, March 2018

References in corpus (8)

• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Model-Based Compressive Sensing
• Signals on Graphs: Uncertainty Principle and Sampling
• Signal Processing on Graphs: Causal Modeling of Unstructured Data
• ${\ell }_0$ Sparsifying Transform Learning with Efficient Optimal Updates and Convergence Guarantees
• A Unique "Nonnegative" Solution to an Underdetermined System: from Vectors to Matrices
• Semi-Blind Inference of Topologies and Dynamical Processes over Graphs
• Nonlinear Structural Vector Autoregressive Models for Inferring Effective Brain Network Connectivity

Cited by in corpus (10)

• A Unified Framework for Structured Graph Learning via Spectral Constraints
• Wide-Sense Stationarity in Generalized Graph Signal Processing
• Learning Product Graphs Underlying Smooth Graph Signals
• On Inference of Network Topology and Confirmation Bias in Cyber-Social Networks
• Graph learning under spectral sparsity constraints
• Skeleton-based Hand-Gesture Recognition with Lightweight Graph Convolutional Networks
• Topology Inference for Network Systems with Unknown Inputs
• Network Reconstruction Problem for an Epidemic Reaction-Diffusion
• Learning Chebyshev Basis in Graph Convolutional Networks for Skeleton-based Action Recognition
• Learning Multi-Frequency Partial Correlation Graphs