Nearest Graph Laplacians with Prescribed Connected Components: A Convex Framework for Network Reconstruction

Abstract

We study the problem of constructing the nearest graph Laplacian matrix to a given Laplacian while enforcing a prescribed connected-component structure. Let the vertex set be partitioned into nonempty disjoint blocks $C_1,\dots ,C_k$, and let $U=[u_1,\dots ,u_k]$ be the matrix of the corresponding block-indicator vectors. The constraint $MU=0$ ensures that these prescribed indicators lie in the nullspace of the optimized Laplacian $M^{\star }$, and hence the associated graph has at least $k$ connected components. To guarantee exactly the prescribed components, we impose additional block-connectivity constraints on the principal blocks $M_j=M[C_j,C_j]$. These constraints ensure that each prescribed block induces a connected weighted subgraph. The resulting problem is a convex semidefinite optimization problem with a strictly convex Frobenius-norm objective. We prove existence and uniqueness of the minimizer and show that the optimized Laplacian has exactly the prescribed connected components, with nullspace $\mathrm{span}\{u_1,\dots ,u_k\}$. The framework proposed in this work provides a principled tool for quantifying the minimum structural intervention required to transform a graph-based network into one having a prescribed group-separated structure. Numerical examples, including the Sampson monastery positive-affection network, illustrate the nearest faction-consistent weighted reconstruction and the minimum Laplacian perturbation required to realize the prescribed faction structure.