A Theoretical Framework to Signed Graph Learning

Music City Center 

In many real-world applications such as biological and social networks, the interactions between the different entities in a complex system are better captured by signed graphs. Learning graph topology from observed signals has been addressed in both statistical theory and graph signal processing. However, most of the approaches focus on unsigned graphs. In this paper, we introduce a signed graph learning method based on the smoothness assumption. In particular, we assume that graph signals admit low-frequency representation over positive edges, while admitting high-frequency representation over negative edges. These two goals are simultaneously achieved and formulated in an optimization problem. A bound on the estimation error of the graph Laplacian is derived as a function of the number of observations and nodes. Finally, the proposed method is compared with both signed and unsigned graph learning approaches with respect to the increasing number of nodes, noise levels, and balance of the graphs.The scalability of the proposed approach compared to the state-of-the-art methods is also illustrated.

Graph Signal Processing

Signed Graph Learning

Estimation Error

Graph Laplacian 

Section on Statistical Learning and Data Science