Network Topology Inference with Sparsity and Laplacian Constraints
Jiaxi Ying Xi Han Rui Zhou Xiwen Wang Hing Cheung So
We tackle the network topology inference problem by utilizing Laplacian
constrained Gaussian graphical models, which recast the task as estimating a
precision matrix in the form of a graph Laplacian. Recent research
\cite{ying2020nonconvex} has uncovered the limitations of the widely used
$\ell_1$-norm in learning sparse graphs under this model: empirically, the
number of nonzero entries in the solution grows with the regularization
parameter of the $\ell_1$-norm; theoretically, a large regularization parameter
leads to a fully connected (densest) graph. To overcome these challenges, we
propose a graph Laplacian estimation method incorporating the $\ell_0$-norm
constraint. An efficient gradient projection algorithm is developed to solve
the resulting optimization problem, characterized by sparsity and Laplacian
constraints. Through numerical experiments with synthetic and financial
time-series datasets, we demonstrate the effectiveness of the proposed method
in network topology inference.