Learning Cartesian Product Graphs with Laplacian Constraints
This work addresses graph learning for Gaussian graphical models and graph signal processing, offering an incremental improvement with efficient algorithms and consistency guarantees.
The paper tackles the problem of learning Cartesian product graphs under Laplacian constraints, which models higher-order dependencies and generalizes graph signal processing to tensors, and demonstrates that their method outperforms previous approaches in experiments on synthetic and real-world datasets.
Graph Laplacian learning, also known as network topology inference, is a problem of great interest to multiple communities. In Gaussian graphical models (GM), graph learning amounts to endowing covariance selection with the Laplacian structure. In graph signal processing (GSP), it is essential to infer the unobserved graph from the outputs of a filtering system. In this paper, we study the problem of learning Cartesian product graphs under Laplacian constraints. The Cartesian graph product is a natural way for modeling higher-order conditional dependencies and is also the key for generalizing GSP to multi-way tensors. We establish statistical consistency for the penalized maximum likelihood estimation (MLE) of a Cartesian product Laplacian, and propose an efficient algorithm to solve the problem. We also extend our method for efficient joint graph learning and imputation in the presence of structural missing values. Experiments on synthetic and real-world datasets demonstrate that our method is superior to previous GSP and GM methods.