Large Scale Distributed Semi-Supervised Learning Using Streaming Approximation
This addresses the computational and memory bottlenecks in semi-supervised learning for large-scale applications, such as natural language processing, with incremental improvements in efficiency and performance.
The paper tackles the scalability problem of graph-based semi-supervised learning for massive data and large label sets by introducing a streaming approximation method that reduces space complexity per node to O(1) and a distributed algorithm, achieving better performance and significant memory reduction compared to state-of-the-art methods.
Traditional graph-based semi-supervised learning (SSL) approaches, even though widely applied, are not suited for massive data and large label scenarios since they scale linearly with the number of edges $|E|$ and distinct labels $m$. To deal with the large label size problem, recent works propose sketch-based methods to approximate the distribution on labels per node thereby achieving a space reduction from $O(m)$ to $O(\log m)$, under certain conditions. In this paper, we present a novel streaming graph-based SSL approximation that captures the sparsity of the label distribution and ensures the algorithm propagates labels accurately, and further reduces the space complexity per node to $O(1)$. We also provide a distributed version of the algorithm that scales well to large data sizes. Experiments on real-world datasets demonstrate that the new method achieves better performance than existing state-of-the-art algorithms with significant reduction in memory footprint. We also study different graph construction mechanisms for natural language applications and propose a robust graph augmentation strategy trained using state-of-the-art unsupervised deep learning architectures that yields further significant quality gains.