Learning Graphs with Monotone Topology Properties and Multiple Connected Components

Abstract

Recent papers have formulated the problem of learning graphs from data as an inverse covariance estimation with graph Laplacian constraints. While such problems are convex, existing methods cannot guarantee that solutions will have specific graph topology properties (e.g., being $k$-partite), which are desirable for some applications. In fact, the problem of learning a graph with given topology properties, e.g., finding the $k$-partite graph that best matches the data, is in general non-convex. In this paper, we develop novel theoretical results that provide performance guarantees for an approach to solve these problems. Our solution decomposes this problem into two sub-problems, for which efficient solutions are known. Specifically, a graph topology inference (GTI) step is employed to select a feasible graph topology, i.e., one having the desired property. Then, a graph weight estimation (GWE) step is performed by solving a generalized graph Laplacian estimation problem, where edges are constrained by the topology found in the GTI step. Our main result is a bound on the error of the GWE step as a function of the error in the GTI step. This error bound indicates that the GTI step should be solved using an algorithm that approximates the similarity matrix by another matrix whose entries have been thresholded to zero to have the desired type of graph topology. The GTI stage can leverage existing methods (e.g., state of the art approaches for graph coloring) which are typically based on minimizing the total weight of removed edges. Since the GWE stage is formulated as an inverse covariance estimation problem with linear constraints, it can be solved using existing convex optimization methods. We demonstrate that our two step approach can achieve good results for both synthetic and texture image data.

References in corpus (11)

• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Discrete Signal Processing on Graphs
• Perfect Reconstruction Two-Channel Wavelet Filter-Banks for Graph Structured Data
• Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies
• Exact covariance thresholding into connected components for large-scale Graphical Lasso
• Structure estimation for discrete graphical models: Generalized covariance matrices and their inverses
• Subgraph-based filterbanks for graph signals
• High-Dimensional Gaussian Graphical Model Selection: Walk Summability and Local Separation Criterion
• Learning Gaussian Tree Models: Analysis of Error Exponents and Extremal Structures
• Transform-based Distributed Data Gathering
• Graphical Lasso and Thresholding: Equivalence and Closed-form Solutions

Cited by in corpus (12)

• Graph Learning: A Survey
• Learning graphs from data: A signal representation perspective
• Connecting the Dots: Identifying Network Structure via Graph Signal Processing
• A Unified Framework for Structured Graph Learning via Spectral Constraints
• Two Channel Filter Banks on Arbitrary Graphs with Positive Semi Definite Variation Operators
• Sparse Graph Learning Under Laplacian-Related Constraints
• Covariance estimation with nonnegative partial correlations
• Laplacian Constrained Precision Matrix Estimation: Existence and High Dimensional Consistency
• Joint Network Topology Inference via Structured Fusion Regularization
• Distributed Estimation of Sparse Inverse Covariances
• Time-Varying Graph Learning with Constraints on Graph Temporal Variation
• PrecoG: an efficient unitary split preconditioner for the transform-domain LMS filter via graph Laplacian regularization