Large Scale Distributed Semi-Supervised Learning Using Streaming\n Approximation

Abstract

Traditional graph-based semi-supervised learning (SSL) approaches, even\nthough widely applied, are not suited for massive data and large label\nscenarios since they scale linearly with the number of edges $|E|$ and distinct\nlabels $m$. To deal with the large label size problem, recent works propose\nsketch-based methods to approximate the distribution on labels per node thereby\nachieving a space reduction from $O(m)$ to $O(\\log m)$, under certain\nconditions. In this paper, we present a novel streaming graph-based SSL\napproximation that captures the sparsity of the label distribution and ensures\nthe algorithm propagates labels accurately, and further reduces the space\ncomplexity per node to $O(1)$. We also provide a distributed version of the\nalgorithm that scales well to large data sizes. Experiments on real-world\ndatasets demonstrate that the new method achieves better performance than\nexisting state-of-the-art algorithms with significant reduction in memory\nfootprint. We also study different graph construction mechanisms for natural\nlanguage applications and propose a robust graph augmentation strategy trained\nusing state-of-the-art unsupervised deep learning architectures that yields\nfurther significant quality gains.\n