ON LEARNING LAPLACIANS OF TREE STRUCTURED GRAPHS
Keng-Shih Lu, Eduardo Pavéz, Antonio Ortega · 2018
How to obtain a graph from data samples is a crucial problem in graph signal processing and in other areas, such as machine learning. This graph learning problem can be formulated as a Gaussian maximum likelihood estimation with Laplacian constraints on the precision matrix, possibly under particular topology constraints. To obtain its solution, we typically require iterative convex optimization solvers. In this paper, we show that when the target graph topology is known and does not contain any cycle, i.e., it is a tree, then the optimal Laplacian has a closed form in terms of the empirical covariance matrix. In particular, the edge weights have the form of an inverse mean square difference when the regularization parameter is zero. Based on this result, we show how to obtain the optimal tree topology using the maximum weight spanning tree algorithm. Finally, we show some experimental results, where our method outperforms existing methods. In addition, our method for topology inference also provides higher accuracy in finding the ground truth topology using synthetic data.