Graph Construction From Data By Non-Negative Kernel Regression

Data driven graph constructions are often used in machine learning applications. However, learning an optimal graph from data is still a challenging task. $K$-nearest neighbor and $\epsilon$-neighborhood methods are among the most common graph construction methods, due to their computational simplicity, but the choice of parameters such as $K$ and $\epsilon$ associated with these methods is often ad hoc and lacks a clear interpretation. The main novelty of this paper is to formulate graph construction as the problem of finding a sparse signal approximation in kernel space, and identifying key similarities between methods in signal approximation and existing graph learning methods. We propose non-negative kernel regression~(NNK), an improved approach for graph construction with interesting geometric and theoretical properties. We demonstrate experimentally the efficiency of NNK graphs, their robustness to choice of sparsity $K$ and show that they can outperform state of the art graph methods in semi supervised learning tasks.