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.

学习 Cartesian 乘积图的问题，统计一致性的 MLE，联合图学习和插补方法

学习带有拉普拉斯约束的笛卡尔积图

Learning Cartesian Product Graphs with Laplacian Constraints

Many signals on Cartesian product graphs appear in the real world, such as
digital images, sensor observation time series, and movie ratings on Netflix.
These signals are "multi-dimensional" and have directional characteristics
along each factor graph. However, the existing graph Fourier transform does not
distinguish these directions, and assigns 1-D spectra to signals on product
graphs. Further, these spectra are often multi-valued at some frequencies. Our
main result is a multi-dimensional graph Fourier transform that solves such
problems associated with the conventional GFT. Using algebraic properties of
Cartesian products, the proposed transform rearranges 1-D spectra obtained by
the conventional GFT into the multi-dimensional frequency domain, of which each
dimension represents a directional frequency along each factor graph. Thus, the
multi-dimensional graph Fourier transform enables directional frequency
analysis, in addition to frequency analysis with the conventional GFT.
Moreover, this rearrangement resolves the multi-valuedness of spectra in some
cases. The multi-dimensional graph Fourier transform is a foundation of novel
filterings and stationarities that utilize dimensional information of graph
signals, which are also discussed in this study. The proposed methods are
applicable to a wide variety of data that can be regarded as signals on
Cartesian product graphs. This study also notes that multivariate graph signals
can be regarded as 2-D univariate graph signals. This correspondence provides
natural definitions of the multivariate graph Fourier transform and the
multivariate stationarity based on their 2-D univariate versions.

本文提出了一种解决现有图傅里叶变换中存在的多值频率以及无法区分方向的问题的多维图傅里叶变换，该变换具有定向频率分析的功能，同时还能实现常规 GFT 中无法实现的滤波和稳定性，可适用于各种能够被视为笛卡尔积图上的信号。