Neighborhood Relation-Based Incremental Label Propagation Algorithm for Partially Labeled Hybrid Data

Abstract

Label propagation can rapidly predict the labels of unlabeled objects as the correct answers from a small amount of given label information, which can enhance the performance of subsequent machine learning tasks. Most existing label propagation methods are proposed for static data. However, in many applications, real datasets including multiple feature value types and massive unlabeled objects vary dynamically over time, whereas applying these label propagation methods for dynamic partially labeled hybrid data will be a huge drain due to recalculating from scratch when the data changes every time. To improve efficiency, a novel incremental label propagation algorithm based on neighborhood relation (ILPN) is developed in this paper. Specifically, we first construct graph structures by utilizing neighborhood relations to eliminate unnecessary label information. Then, a new label propagation strategy is designed in consideration of the weights assigned to each class so that it does not rely on a probabilistic transition matrix to fix the structure for propagation. On this basis, a new label propagation algorithm called neighborhood relation-based label propagation (LPN) is developed. For the dynamic partially labeled hybrid data, we integrate incremental learning into LPN and develop an updating mechanism that allows incremental label propagation over previous label propagation results and graph structures, rather than recalculating from scratch. Finally, extensive experiments on UCI datasets validate that our proposed algorithm LPN can outperform other label propagation algorithms in speed on the premise of ensuring accuracy. Especially for simulated dynamic data, the incremental algorithm ILPN is more efficient than other non-incremental methods with the variation of the partially labeled hybrid data.