A greedy algorithm to construct sparse graph by using ranked dictionary

L₁ graph is an effective way to represent data samples in many graph-oriented machine learning applications. Its original construction algorithm is nonparametric, and the graphs it generates may have high sparsity. Meanwhile, the construction algorithm also requires many iterative convex optimization calculations and is very time-consuming. Such characteristics would severely limit the application scope of L₁ graph in many real-world tasks. In this paper, we design a greedy algorithm to speed up the construction of L₁ graph. Moreover, we introduce the concept of “Ranked Dictionary” for L₁ minimization. This ranked dictionary not only preserves the locality but also removes the randomness of neighborhood selection during the process of graph construction. To demonstrate the effectiveness of our proposed algorithm, we present our experimental results on several commonly used datasets using two different ranking strategies: One is based on Euclidean distance, and another is based on diffusion distance.