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 -neighborhood methods are among the most common graph construction methods, due to their computational simplicity, but the choice of parameters such as K and 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.

Download paper here

@inproceedings{shekkizhar2020graph,
  title={Graph Construction from Data by Non-Negative Kernel Regression},
  author={Shekkizhar, Sarath and Ortega, Antonio},
  booktitle={ICASSP 2020-2020 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP)},
  pages={3892--3896},
  year={2020},
  organization={IEEE}
}