Efficient Graph Learning From Noisy and Incomplete Data
Efficient Graph Learning From Noisy and Incomplete Data
复制标题
DOI：
10.1109/tsipn.2020.2964249
复制
发表时间：
2020
影响因子：
3.2
通讯作者：
Peter Berger;Gabor Hannak;G. Matz
中科院分区：
文献类型：
--
作者：
Peter Berger;Gabor Hannak;G. Matz
我们考虑从一组给定的光滑图信号中学习图的问题。我们的图学习方法被表述为边缘权重的约束二次规划。我们提供了最优解的隐式表征，并提出了一个定制的ADMM算法来有效地解决这个问题。几种基于最近邻和平滑的图学习方法被证明是我们方法的特殊情况。具体来说，我们的算法生成了一个高效但极其精确的$b$匹配图的近似值。然后，我们提出了一种推广方案，该方案可以通过联合图学习和信号绘制来处理噪声和不完整数据。我们将我们的方法与最先进的合成数据方法和来自奥地利国家委员会的真实世界数据进行比较。
We consider the problem of learning a graph from a given set of smooth graph signals. Our graph learning approach is formulated as a constrained quadratic program in the edge weights. We provide an implicit characterization of the optimal solution and propose a tailored ADMM algorithm to solve this problem efficiently. Several nearest neighbor and smoothness based graph learning methods are shown to be special cases of our approach. Specifically, our algorithm yields an efficient but extremely accurate approximation to $b$-matched graphs. We then propose a generalization of our scheme that can deal with noisy and incomplete data via joint graph learning and signal inpainting. We compare the performance of our approach with state-of-the art methods on synthetic data and on real-world data from the Austrian National Council.