Leveraging Low-rank Factorizations of Conditional Correlation Matrices in Graph Learning
This work addresses a computational bottleneck in graph learning for applications like graph signal processing, offering an incremental improvement over existing methods like GLasso.
The paper tackles the scalability issue in learning undirected graphs from node data by proposing a framework that uses low-rank factorization of conditional correlation matrices, resulting in an efficient dimension-versus-performance trade-off as evidenced by experiments on synthetic and real data.
This paper addresses the problem of learning an undirected graph from data gathered at each nodes. Within the graph signal processing framework, the topology of such graph can be linked to the support of the conditional correlation matrix of the data. The corresponding graph learning problem then scales to the squares of the number of variables (nodes), which is usually problematic at large dimension. To tackle this issue, we propose a graph learning framework that leverages a low-rank factorization of the conditional correlation matrix. In order to solve for the resulting optimization problems, we derive tools required to apply Riemannian optimization techniques for this particular structure. The proposal is then particularized to a low-rank constrained counterpart of the GLasso algorithm, i.e., the penalized maximum likelihood estimation of a Gaussian graphical model. Experiments on synthetic and real data evidence that a very efficient dimension-versus-performance trade-off can be achieved with this approach.