An efficient alternating direction method for graph learning from smooth signals

We consider the problem of identifying the graph topology from a set of smooth graph signals. A well-known approach to this problem is minimizing the Dirichlet energy accompanied with some Frobenius norm regularization. Recent works have incorporated the logarithmic barrier on the node degrees to improve the overall graph connectivity without compromising graph sparsity, which is shown to be quite effective in enhancing the quality of the learned graphs. Although a primal-dual algorithm has been proposed in the literature to solve this type of graph learning formulations, it lacks a rigorous convergence analysis and appears to have a slow empirical performance. In this paper, we cast the graph learning formulation as a nonsmooth, strictly convex optimization problem and develop an efficient alternating direction method of multipliers to solve it. We show that our algorithm converges to the global minimum with arbitrary initialization. We conduct extensive experiments on various synthetic and real-world graphs, the results of which show that our method exhibits sharp linear convergence and is substantially faster than the commonly adopted primal-dual method.