A unified framework for structured graph learning via spectral constraints

MaRDI QIDQ4969059zbMATH OpenFDO

Authors

Publication date 5 October 2020

Full work available at URL https://arxiv.org/abs/1904.09792, https://jmlr.csail.mit.edu/papers/v21/19-276.html

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)

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.

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

Cites work

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

Cited in

(7)

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

Describes a project that uses

Uses Software

• R
• UCI
• 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)