Efficient locality weighted sparse representation for graph-based learning

Constructing a graph to represent the structure among data objects plays a fundamental role in various data mining tasks with graph-based learning. Since traditional pairwise distance-based graph construction is sensitive to noise and outliers, sparse representation based graphs (e.g., ℓ1-graphs) have been proposed in the literature. Although ℓ1-graphs prove powerful and robust for many graph-based learning tasks, it suffers from weak locality and high computation costs. In this paper, we propose a locality weighted sparse representation (LWSR), which aims for good preservation of the locality structure among data objects and a significant reduction of the computation time. LWSR approximates each object as a sparse linear combination of its nearest neighbors, and weights their corresponding coefficients by their distances to the target object. Experimental results show that LWSR-graph based learning methods outperform state-of-the-art methods in both effectiveness and efficiency for graph-based learning.