QReduce: A novel quantum annealing approach for graph-based instance selection of high-fidelity training labels in supervised classification and regression datasets

Abstract Instance selection algorithms for supervised classification and regression tasks in machine learning aim to reduce the size of training datasets whilst maintaining the performance of models by selecting the most important, high-fidelity training labels from a large pool of instances in the original datasets. Traditional instance selection methods such as cluster-based techniques demonstrate enhanced generalization capabilities on fewer data points compared with random sampling approaches, but often suffer from high computational costs, sensitivity to hyperparameters and non-deterministic time complexities. This paper proposes QReduce which is a novel instance selection algorithm which models datasets as N-dimensional graphs with each data point corresponding to a vertex and edges constructed between points in a k-nearest neighbour manner. This graph is subjected to quantum annealing to solve the minimum vertex cover or maximum cut graph combinatorial optimization problems and yield a subgraph representing the reduced subset of instances selected for the reduced dataset. Solving such NP-hard problems are intractable for exact classical solvers on account of combinatorial explosion of the problem’s search space, and quantum annealing was shown to outperform other approximate metaheuristic techniques such as simulated annealing, justifying it as a strong metaheuristic optimization model. QReduce enables recursive reduction of the dataset and has the benefits of less sensitivity to hyperparameters as well as a deterministic time complexity, enabling efficient and effective reduction in storage and compute requirements for training complex machine learning models in the age of green and sustainable AI. Experimental results demonstrate the efficacy of QReduce, outperforming existing instance selection techniques and having the highest average percentage data reduction to percentage accuracy reduction ratios on datasets for both classification and regression tasks, thereby making it a best-in-class instance selection algorithm for selecting high-fidelity training labels in supervised machine learning tasks.