Lightweight Label Propagation for Large-Scale Network Data

Lightweight Label Propagation for Large-Scale Network Data

De-Ming Liang, Yu-Feng Li

Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence
Main track. Pages 3421-3427. https://doi.org/10.24963/ijcai.2018/475

Label propagation spreads the soft labels from few labeled data to a large amount of unlabeled data according to the intrinsic graph structure. Nonetheless, most label propagation solutions work under relatively small-scale data and fail to cope with many real applications, such as social network analysis, where graphs usually have millions of nodes. In this paper, we propose a novel algorithm named \algo to deal with large-scale data. A lightweight iterative process derived from the well-known stochastic gradient descent strategy is used to reduce memory overhead and accelerate the solving process. We also give a theoretical analysis on the necessity of the warm-start technique for label propagation. Experiments show that our algorithm can handle million-scale graphs in few seconds while achieving highly competitive performance with existing algorithms.
Keywords:
Machine Learning: Semi-Supervised Learning
Machine Learning Applications: Big data ; Scalability