Sparse Graph Learning from Sparse Data via Fiedler Number Maximization
For practitioners needing to infer graph structure from limited observations, this work provides a robust regularization approach that improves connectivity in sparse graph estimates.
The paper addresses learning a sparse and connected graph from sparse data (K << N) with unknown distribution. By incorporating Fiedler number maximization as a regularization term, the proposed greedy and parallel algorithms outperform previous methods in simulation experiments.
We aim to learn a sparse and connected graph from sparse data, where the number of observations K can be substantially smaller than the signal dimension N for signals x in R^N, and the underlying distribution is unknown. In this severely ill-posed setting, we incorporate Fiedler number (the second eigenvalue of the graph Laplacian matrix that quantifies connectedness) as a robust regularization term in the sparse graph learning objective. We first develop a greedy algorithm that iteratively selects one edge globally for weakening/removal to reduce the objective, leveraging eigenvalue perturbation theorems that bound the adverse effect of an edge change to the Fiedler number. Next, we design a parallel variant, based on the Cheeger's inequality, that recursively partitions an input graph into two sub-graphs using an approximate Cheeger cut to distributedly find an optimal edge. Simulation experiments show that Fiedler number maximization robustifies sparse graph estimates, outperforming previous sparse graph learning algorithms.