Learning Cartesian Product Graphs with Laplacian Constraints
Changhao Shi Gal Mishne
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.