Graph topology inference based on transform learning

The association of a graph representation to large datasets is one of key steps in graph-based learning methods. The aim of this paper is to propose an efficient strategy for learning the graph topology from signals defined over the vertices of a graph, under a signal band-limited (either exactly or only approximately so) assumption, which corresponds to signals having clustering properties. The proposed method is composed of two optimization steps. The first step consists in learning, jointly, the sparsifying orthonormal transform and the graph signal from the observed data. The solution of this joint problem is achieved through an iterative algorithm whose alternating intermediate solutions are expressed in closed form. The second step recovers the Laplacian matrix, and then the topology, from the knowledge of the sparsifying transform, through a convex optimization strategy which admits an efficient solution.