LSR-Weighted: A Low-cost Sparse Recovery Framework for Weighted Networks under Compressive Sensing

In this work, motivated by network inference, we introduce a general framework called LSR-Weighted to efficiently recover sparse characteristics of links, such as inter-community links, in weighted networks. The links in many real-world networks are not only binary entities, either present or not, but have been associated given weights that record their strengths relative to one another. Such models are generally described in terms of weighted networks.

The LSR-Weighted framework uses a newly emerged paradigm in sparse signal recovery named compressive sensing (CS). For the last couple of years, CS has been attending in signal processing, but its applications in networking is still in its early stages due to some challenges. One of the most limiting challenges is the construction of measurement matrix that should be feasible with two different constraints: (1) In networks, a measurement matrix is in a more restrictive class taking only non-negative integer entries, while random Gaussian measurement matrices are usually used in the CS literature; (2) More substantially in networks, measurements are restricted by network topological constraints which was not considered in existing CS researches. In other words, only nodes that induce a path or connected sub-graph can be aggregated together in the same measurement.

The previous works need three major improvements: (1) Constructing a feasible measurement matrix with less total number of required measurements for efficient sparse recovery when the relative error should be almost zero; (2) Providing the maximum information coverage using these measurements with a lower total cost (weight); (3) Evaluating weighted networks of various kinds to recover sparse specifications of link vectors with more sparsity and less recovery error.

In this work, we propose a Low-cost Sparse Recovery framework for Weighted networks in the context of compressive sensing, called LSR-Weighted, by considering all aforementioned challenges. This framework exploits the correlation between the weights and the topological structure of the network, unveiling the complex architecture shown by real weighted networks. We evaluate performance of the proposed framework on realworld networks of various kinds, in comparison with two of the state-of-the-art methods for this problem. Extensive simulation results illustrate that our method outperforms the previous methods in terms of recovery error for different number of measurements and sparsity, with relatively lower cost.

Related Publication:

Project code:

  • This code is written in Java and contains routines and methods used in the above publication. Please cite the above work if you use this software and contact first author in case of any problems.
 

Sparse Signal Processing Group