Graph-based Deep Learning Analysis and Instance Selection

While deep learning is a powerful tool for many applications, there has been only limited research about selection of data for training, i.e., instance selection, which enhances deep learning scalability by saving computational resources. This can be attributed in part to the difficulty of interpreting deep learning models. While some graph-based methods have been proposed to improve performance and interpret behavior of deep learning, the instance selection problem has not been addressed from a graph perspective. In this paper, we analyze the behavior of deep learning outputs by using the K-nearest neighbor (KNN) graph construction. We observe that when a directed KNN graph is constructed, instead of the more conventional undirected KNN, a large number of instances become isolated nodes, i.e., they do not belong to the directed neighborhoods of any other nodes. Based on this, we propose two new instance selection methods, that both lead to fewer isolated nodes, by either directly eliminating them (minimization approach) or by connecting them more strongly to other points (maximization). Our experiments show that our proposed maximization method leads to better performance than random selection and recent methods for instance selection.