Network Topology Inference with Sparsity and Laplacian Constraints
This work addresses network topology inference for applications like financial analysis, but it is incremental as it builds on existing Laplacian constrained models by modifying the sparsity constraint.
The paper tackled the network topology inference problem by proposing a graph Laplacian estimation method with an ℓ₀-norm constraint to overcome limitations of the ℓ₁-norm, which can lead to dense graphs, and demonstrated its effectiveness through numerical experiments on synthetic and financial datasets.
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.