Learning Graphs With Monotone Topology Properties and Multiple Connected Components
Learning Graphs With Monotone Topology Properties and Multiple Connected Components
复制标题
学习具有单调拓扑属性和多个连通分量的图
DOI：
--
复制
发表时间：
2017
影响因子：
5.4
通讯作者：
Antonio Ortega
中科院分区：
文献类型：
--
作者：
Eduardo Pavez;Hilmi E. Egilmez;Antonio Ortega
最近的论文已经制定了从数据学习图的问题作为一个逆协方差估计问题与图拉普拉斯约束。虽然这样的问题是凸的，但是现有方法不能保证解将具有特定的图拓扑性质（例如，是树），这对于某些应用是期望的。具有拓扑性质的图的学习问题一般是非凸的。在本文中，我们提出了一种方法来解决这些问题，将它们分解成两个子问题，其中有效的解决方案是已知的。具体地，采用图拓扑推理（GTI）步骤来选择可行的图拓扑。然后，通过求解广义图拉普拉斯估计问题来执行图权重估计（GWE）步骤，其中边缘受到在GTI步骤中发现的拓扑的约束。我们的主要结果是作为GTI步骤中的误差的函数的GWE步骤的误差上的界。该误差界限指示GTI步骤应当使用通过另一矩阵来近似数据相似性矩阵的算法来求解，该另一矩阵的条目已经被阈值化为零以具有期望类型的图拓扑。GTI阶段可以利用现有的方法，这些方法通常基于最小化移除的边缘的总权重。由于GWE阶段是具有线性约束的逆协方差估计问题，因此可以使用现有的凸优化方法来求解。我们证明，我们的方法可以取得良好的效果，合成和纹理图像数据。
Recent papers have formulated the problem of learning graphs from data as an inverse covariance estimation problem with graph Laplacian constraints. While such problems are convex, existing methods cannot guarantee that solutions will have specific graph topology properties (e.g., being a tree), which are desirable for some applications. The problem of learning a graph with topology properties is in general non-convex. In this paper, we propose an approach to solve these problems by decomposing them 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. 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 data 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, which are typically based on minimizing the total weight of removed edges. Since the GWE stage is an inverse covariance estimation problem with linear constraints, it can be solved using existing convex optimization methods. We demonstrate that our approach can achieve good results for both synthetic and texture image data.
DOI：
10.1214/17-aos1668
发表时间：
2019
期刊：
The Annals of Statistics
影响因子：
--
作者：
Lauritzen, Steffen;Uhler, Caroline;Zwiernik, Piotr
通讯作者：
Zwiernik, Piotr