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.

本文提出了一种新颖的流图半监督学习逼近方法，旨在捕捉标签分布的稀疏性并确保算法准确地传播标签，进一步将每个节点的空间复杂度降低到 O (1)，同时提供了适用于大型数据的分布式算法和为自然语言应用构建的图构建机制以及经过深度学习架构训练的鲁棒性图增强策略，实验结果证明该方法在内存占用上具有显著的降低，并且在性能上优于现有的最先进算法。