Variants of k-regular nearest neighbor graph and their construction

Neighborhood graph and its construction play an important role in numerous problems. Many methods have been proposed to improve the classic k-NN construction based on various criteria. Recently, a new structure named k-regular nearest neighbor (k-RNN) graph has been proposed not only to minimize the sum of edge weights (for keeping the creditable neighborhood relationships), but also to require the node degree to be approximately k. However, the proposed graph construction algorithm is highly heuristic, which neither minimizes the cost (sum of edge weights) in an explicit manner nor formalizes the node degree requirement. In this work we formalize the essential requirements behind k-RNN. Several variants of this formalization will be studied, all being formulated as problems of energy function minimization with efficient greedy solutions. An experimental evaluation is also presented to demonstrate the effectiveness of our methods and superior performance compared to previous works.