# Learning Graphs with Monotone Topology Properties and Multiple Connected Components

arXiv: https://arxiv.org/abs/1705.10934 · HTML: https://mlsanity.com/paper/1705.10934/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 May 2017.

## Built on by (most cited first, 13 of 13)

- [Graph Learning: A Survey](https://mlsanity.com/paper/2105.00696/) (2021)
- [Accelerated Graph Learning from Smooth Signals](https://mlsanity.com/paper/2110.09677/) (2021)
- [Fast Projected Newton-like Method for Precision Matrix Estimation under Total Positivity](https://mlsanity.com/paper/2112.01939/) (2021)
- [Sparse Graph Learning Under Laplacian-Related Constraints](https://mlsanity.com/paper/2111.08161/) (2021)
- [Learning Large-Scale MTP2 Gaussian Graphical Models via Bridge-Block Decomposition](https://mlsanity.com/paper/2309.13405/) (2023)
- [Laplacian Constrained Precision Matrix Estimation: Existence and High Dimensional Consistency](https://mlsanity.com/paper/2111.00590/) (2021)
- [Adaptive Estimation of Graphical Models under Total Positivity](https://mlsanity.com/paper/2210.15471/) (2022)
- [Joint Network Topology Inference via Structured Fusion Regularization](https://mlsanity.com/paper/2103.03471/) (2021)
- [Distributed Estimation of Sparse Inverse Covariances](https://mlsanity.com/paper/2109.12020/) (2021)
- [Joint Graph and Vertex Importance Learning](https://mlsanity.com/paper/2303.08552/) (2023)
- [Learning to Identify Graphs from Node Trajectories in Multi-Robot Networks](https://mlsanity.com/paper/2307.04374/) (2023)
- [A Copula Graphical Model for Multi-Attribute Data using Optimal Transport](https://mlsanity.com/paper/2404.06735/) (2024)
- [Online Proximal ADMM for Graph Learning from Streaming Smooth Signals](https://mlsanity.com/paper/2409.12916/) (2024)

## Abstract (arXiv)

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.