A Rank Constrained Approach for Graph Learning from Spatio-Temporal Signals

In the task of graph learning, the presence of noise poses a significant challenge to accurately estimate the underlying graph structure. Current approaches often rely on nuclear norm regularization to exploit the low-rank properties of noiseless spatio-temporal signals. However, their performance depends on empirically estimated parameters and also suffers from slow convergence. In this paper, we propose a novel graph learning algorithm from spatio-temporal signals that establishes an upper bound on the rank of the signal matrix, which can be readily estimated. The alternating optimization strategy is employed to tackle the resulting problem. The symmetric adjacency matrix can be updated by solving an quadratic program, while the signal matrix can be effectively achieved by an alternating direction method of multipliers (ADMM). Experimental results show that our algorithm outperforms existing methods in terms of estimation accuracy while maintaining a fast convergence speed.