A Unified Framework for Structured Graph Learning via Spectral Constraints

Abstract

Graph learning from data represents a canonical problem that has received substantial attention in the literature. However, insufficient work has been done in incorporating prior structural knowledge onto the learning of underlying graphical models from data. Learning a graph with a specific structure is essential for interpretability and identification of the relationships among data. Useful structured graphs include the multi-component graph, bipartite graph, connected graph, sparse graph, and regular graph. In general, structured graph learning is an NP-hard combinatorial problem, therefore, designing a general tractable optimization method is extremely challenging. In this paper, we introduce a unified graph learning framework lying at the integration of Gaussian graphical models and spectral graph theory. To impose a particular structure on a graph, we first show how to formulate the combinatorial constraints as an analytical property of the graph matrix. Then we develop an optimization framework that leverages graph learning with specific structures via spectral constraints on graph matrices. The proposed algorithms are provably convergent, computationally efficient, and practically amenable for numerous graph-based tasks. Extensive numerical experiments with both synthetic and real data sets illustrate the effectiveness of the proposed algorithms. The code for all the simulations is made available as an open source repository.

References in corpus (10)

• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• The huge Package for High-dimensional Undirected Graph Estimation in R
• Projected Subgradient Methods for Learning Sparse Gaussians
• Graph topology inference based on sparsifying transform learning
• Vandermonde Factorization of Hankel Matrix for Complex Exponential Signal Recovery -- Application in Fast NMR Spectroscopy
• Sparse Generalized Eigenvalue Problem via Smooth Optimization
• Learning Graphs with Monotone Topology Properties and Multiple Connected Components
• Orthogonal Sparse PCA and Covariance Estimation via Procrustes Reformulation
• Scalable and Flexible Multiview MAX-VAR Canonical Correlation Analysis
• Upper bound for the Laplacian eigenvalues of a graph

Cited by in corpus (8)

• Two Channel Filter Banks on Arbitrary Graphs with Positive Semi Definite Variation Operators
• Multiway $p$-spectral graph cuts on Grassmann manifolds
• Distributionally Robust Graph Learning from Smooth Signals under Moment Uncertainty
• Learning block structured graphs in Gaussian graphical models
• Comparing Graph Spectra of Adjacency and Laplacian Matrices
• Sparse Graphical Linear Dynamical Systems
• Learning Graph Laplacian with MCP
• Online Inference for Mixture Model of Streaming Graph Signals with Non-White Excitation