Timezone: »

Structured Graph Learning Via Laplacian Spectral Constraints
Sandeep Kumar · Jiaxi Ying · Jose Vinicius de Miranda Cardoso · Daniel Palomar

Wed Dec 11 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #184

Learning a graph with a specific structure is essential for interpretability and identification of the relationships among data. But structured graph learning from observed samples is an NP-hard combinatorial problem. In this paper, we first show, for a set of important graph families it is possible to convert the combinatorial constraints of structure into eigenvalue constraints of the graph Laplacian matrix. Then we introduce a unified graph learning framework lying at the integration of the spectral properties of the Laplacian matrix with Gaussian graphical modeling, which is capable of learning structures of a large class of graph families. The proposed algorithms are provably convergent and practically amenable for big-data specific tasks. Extensive numerical experiments with both synthetic and real datasets demonstrate the effectiveness of the proposed methods. An R package containing codes for all the experimental results is submitted as a supplementary file.

Author Information

Sandeep Kumar (Hong Kong University of Science and Technology)
Jiaxi Ying (The Hong Kong University of Science and Technology)
Jose Vinicius de Miranda Cardoso (Universidade Federal de Campina Grande)
Daniel Palomar (The Hong Kong University of Science and Technology)