Large Scale Distributed Semi-Supervised Learning Using Streaming Approximation

By Sujith Ravi, Qiming Diao. 2015

50 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

Citations in the corpus

Smart Reply: Automated Response Suggestion for Email (2016, methodology): “So instead, we model the task as a semi-supervised machine learning problem and use scalable graph algorithms [15] to automatically learn this information from data and a few human-provided examples.”
Graph-RISE: Graph-Regularized Image Semantic Embedding (2019, methodology): “On the other hand, when p ′ ( x ) = ϕ ( x ) , where p ′ ( x ) is the predicted label distribution, we have a label propagation objective as in [17] by training with the objective using p ′ ( x ) directly without parameters θ ( i .e., no neural network involved), and letting the distance function d…”
Ultra Fine-Grained Image Semantic Embedding (2020, methodology): “On the other hand, when p′(x) = φ(x), where p′(x) is the predicted label distribution, we have a label propagation objective as in [17] by training with the objective using p′(x) directly without parameters θ (i.”
Hierarchical Label Propagation and Discovery for Machine Generated Email (2016, methodology): “Our method uses the EXPANDER [24] framework and algorithm for propagation and learning label distributions.”