A unified framework for structured graph learning via spectral constraints

zbMATH Open1498.68246arXiv1904.09792MaRDI QIDQ4969059FDOQ4969059

Authors:

Publication date: 5 October 2020

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.

Full work available at URL: https://arxiv.org/abs/1904.09792

Recommendations

• Spectral clustering via sparse graph structure learning with application to proteomic signaling networks in cancer
• scientific article; zbMATH DE number 1975565
• Learning graphical models with hubs
• Structured regularization for conditional Gaussian graphical models
• Learning a common substructure of multiple graphical Gaussian models

zbMATH Keywords

clusteringGaussian graphical modelspectral graph theoryLaplacian matrixadjacency matrixMarkov random fieldbipartite structurespectral similaritystructured graph learning

Mathematics Subject Classification ID

Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Estimation in multivariate analysis (62H12) Probabilistic graphical models (62H22) Graph theory (including graph drawing) in computer science (68R10)

Cites Work

• The graphical lasso: new insights and alternatives
• Lean algebraic multigrid (LAMG): fast graph Laplacian linear solver
• Gaussian Markov Random Fields
• Inferring sparse Gaussian graphical models with latent structure
• High-dimensional graphs and variable selection with the Lasso
• Kernels and regularization on graphs.
• Enhancing sparsity by reweighted \(\ell _{1}\) minimization
• Bayesian regularization for normal mixture estimation and model-based clustering
• Sparsistency and rates of convergence in large covariance matrix estimation
• Sparse inverse covariance estimation with the graphical lasso
• A unified convergence analysis of block successive minimization methods for nonsmooth optimization
• Model selection through sparse maximum likelihood estimation for multivariate Gaussian or binary data
• Model selection and estimation in the Gaussian graphical model
• Title not available (Why is that?)
• Graph clustering
• Title not available (Why is that?)
• Approximating discrete probability distributions with dependence trees
• Penalized likelihood methods for estimation of sparse high-dimensional directed acyclic graphs
• High-dimensional Ising model selection using \(\ell _{1}\)-regularized logistic regression
• Joint estimation of multiple graphical models
• The Joint Graphical Lasso for Inverse Covariance Estimation Across Multiple Classes
• Likelihood-based selection and sharp parameter estimation
• The Isotonic Regression Problem and Its Dual
• Joint estimation of multiple high-dimensional precision matrices
• Sparse Generalized Eigenvalue Problem Via Smooth Optimization
• Active set algorithms for isotonic regression; a unifying framework
• Node-based learning of multiple Gaussian graphical models
• The quadratic loss of isotonic regression under normality
• Analysis of Half-Quadratic Minimization Methods for Signal and Image Recovery
• Constructing cospectral graphs
• Spectral sparsification of graphs
• The Complexity of Distinguishing Markov Random Fields
• The linear complementarity problem, sufficient matrices, and the criss- cross method
• Title not available (Why is that?)
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Joint estimation of sparse multivariate regression and conditional graphical models
• Clustering with \(r\)-regular graphs
• Perfect Reconstruction Two-Channel Wavelet Filter Banks for Graph Structured Data
• High-dimensional Gaussian graphical model selection: walk summability and local separation criterion
• Matrix Nearness Problems with Bregman Divergences
• Graphical methods for efficient likelihood inference in Gaussian covariance models
• Title not available (Why is that?)
• Lower bounds on the (Laplacian) spectral radius of weighted graphs
• A sharp upper bound on the largest Laplacian eigenvalue of weighted graphs
• Majorization-Minimization Algorithms in Signal Processing, Communications, and Machine Learning
• Constructing trees in bipartite graphs
• Graph Spectra for Complex Networks
• Estimation of positive definite \(M\)-matrices and structure learning for attractive Gaussian Markov random fields
• Uncertainty Principles and Sparse Eigenvectors of Graphs
• Graph Topology Inference Based on Sparsifying Transform Learning
• Joint estimation of multiple precision matrices with common structures
• The cluster graphical Lasso for improved estimation of Gaussian graphical models
• Network Granger causality with inherent grouping structure
• Estimation of graphical models through structured norm minimization
• A lower bound for the second largest Laplacian eigenvalue of weighted graphs
• Simultaneous Clustering and Estimation of Heterogeneous Graphical Models
• Orthogonal Sparse PCA and Covariance Estimation via Procrustes Reformulation
• Vandermonde Factorization of Hankel Matrix for Complex Exponential Signal Recovery—Application in Fast NMR Spectroscopy
• Graphical Lasso and thresholding: equivalence and closed-form solutions
• Some results on the largest and least eigenvalues of graphs
• Learning Graphs With Monotone Topology Properties and Multiple Connected Components
• Transform-Based Distributed Data Gathering
• Scalable and Flexible Multiview MAX-VAR Canonical Correlation Analysis
• Optimization Algorithms for Graph Laplacian Estimation via ADMM and MM

Cited In (7)

• Learning Block Structured Graphs in Gaussian Graphical Models
• Multiway \(p\)-spectral graph cuts on Grassmann manifolds
• spectralGraphTopology
• Min-max framework for majorization-minimization algorithms in signal processing applications: an overview
• Learning graph Laplacian with MCP
• A Unifying Generative Model for Graph Learning Algorithms: Label Propagation, Graph Convolutions, and Combinations
• Block Structured Graph Priors in Gaussian Graphical Models

Uses Software

• R
• UCI-ml
• CVX
• Kernlab
• MNIST
• CVXR

This page was built for publication: A unified framework for structured graph learning via spectral constraints

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4969059)