A Unified Framework for Structured Graph Learning via Spectral
  Constraints
  Graph learning from data represents a canonical problem that has received
substantial attention in the literature. However, insufficient work has been
done in incorporating prior structural knowledge onto the learning of
underlying graphical models from data. Learning a graph with a specific
structure is essential for interpretability and identification of the
relationships among data. Useful structured graphs include the multi-component
graph, bipartite graph, connected graph, sparse graph, and regular graph. In
general, structured graph learning is an NP-hard combinatorial problem,
therefore, designing a general tractable optimization method is extremely
challenging. In this paper, we introduce a unified graph learning framework
lying at the integration of Gaussian graphical models and spectral graph
theory. To impose a particular structure on a graph, we first show how to
formulate the combinatorial constraints as an analytical property of the graph
matrix. Then we develop an optimization framework that leverages graph learning
with specific structures via spectral constraints on graph matrices. The
proposed algorithms are provably convergent, computationally efficient, and
practically amenable for numerous graph-based tasks. Extensive numerical
experiments with both synthetic and real data sets illustrate the effectiveness
of the proposed algorithms. The code for all the simulations is made available
as an open source repository.
