LAUSR

Learning graph Laplacian matrices plays a crucial role in network analytics when a meaningful graph is not readily available from the datasets. However, graph Laplacian inference is an ill-posed problem, since multiple solutions may exist to associate a graph with the data. Recent papers have exploited signal smoothness or graph sparsity to handle this problem, without considering specific graph topological property such as community structure. Community structure is prevalent in many real-world networks, which can be exploited to learn the data better. In this paper, we propose a framework that learns the graph Laplacians with overlapping community structure, named LOCN (Learning Overlapping Community-based Networks). Our framework encompasses and leverages the community structure information, along with attributes such as sparsity and signal smoothness to capture the intrinsic relationships between data entities, such that the estimated graph can optimally fit the data. Furthermore, the refined graph Laplacian can be leveraged to further improve the detection of network communities. As a result, LOCN can not only learn the graph Laplacian with a good data fit, but also detect the underlying network communities with a high quality. We show that LOCN can achieve good results for both synthetic and real data.