Scaling Graph-based Semi Supervised Learning to Large Number of Labels Using Count-Min Sketch

Partha Pratim Talukdar, William W. Cohen

Abstract

Graph-based Semi-supervised learning (SSL) algorithms have been successfully used in a large number of applications. These methods classify initially unlabeled nodes by propagating label information from a small set of seed nodes across the graph. However, traditional methods require storing a score for every possible label at every node, leading to a memory bottleneck of $O(m)$ per node, where $m$ is the number of labels. This paper introduces MAD-Sketch, a novel algorithm that integrates the Count-Min Sketch (CMS) data structure into the Modified Adsorption (MAD) framework. By operating directly on compressed sketches, MAD-Sketch reduces space complexity to $O(\log m)$, enabling SSL to scale to datasets with millions of labels with negligible loss in accuracy and significant speedups.

Introduction

Graph-based SSL is a powerful paradigm for leveraging network structure to classify data. However, modern applications—such as tagging web content with millions of entities or classifying the ImageNet hierarchy—render standard $O(m)$ per-node storage impossible. On a graph with millions of nodes and labels, memory requirements quickly exceed the capacity of standard hardware.

The MAD-Sketch Algorithm

The core innovation of MAD-Sketch is the replacement of exact label distributions with a compact $w \times d$ Count-Min Sketch matrix at each node. Labels are hashed into this matrix, and scores are retrieved by taking the minimum value across hashed locations to mitigate collision effects.

A critical property of Count-Min Sketches is their linearity: the sketch of a sum of vectors is equal to the sum of their individual sketches. Since label propagation algorithms like MAD rely on weighted averages of neighbor scores, the entire propagation process can be performed directly on the sketches. This avoids the need to "unpack" sketches into full vectors, maintaining a low memory footprint throughout the computation.

Theoretical analysis suggests that because real-world label distributions are often sparse or follow a power-law (Zipfian) distribution, the approximation error introduced by sketching remains remarkably low.

Experimental Evaluation

The authors evaluated MAD-Sketch on three real-world datasets: Freebase (192 labels), Flickr-10k (10,000 labels), and Flickr-1m (1 million labels). The latter was specifically chosen to test the limits of scalability.

Accuracy and Speed

On the Freebase dataset, MAD-Sketch achieved a Mean Reciprocal Rank (MRR) of 0.28, identical to the exact MAD algorithm, while using significantly less memory. Furthermore, the reduced data structure size improved cache locality, resulting in speedups ranging from 4.7x to 10.8x depending on the sketch dimensions.

Performance comparison on the Freebase dataset, highlighting memory savings and speedups with negligible impact on MRR.

Scaling to the "Impossible"

The true strength of MAD-Sketch was demonstrated on the Flickr-1m dataset. The exact MAD algorithm, requiring over 100GB of RAM, crashed due to an Out-of-Memory (OOM) error by the third iteration. In contrast, MAD-Sketch maintained a stable memory footprint of approximately 15GB and ran to completion.

Memory usage comparison on the Flickr-1m dataset. MAD-Exact fails due to OOM, while MAD-Sketch maintains a manageable, constant memory footprint.

Conclusion

MAD-Sketch addresses the primary scalability bottleneck of graph-based SSL. By exploiting the natural skewness of label distributions and the linearity of Count-Min Sketches, the algorithm enables high-performance classification on graphs with millions of labels. Future work includes addressing the inherent overestimation bias of CMS and exploring the integration of sketching with non-squared loss functions.

Summary updated

Abstract

Graph-based Semi-supervised learning (SSL) algorithms have been successfully used in a large number of applications. These methods classify initially unlabeled nodes by propagating label informatio...
BibTeX
@inproceedings{talukdar2014scaling,
  author = {Partha Pratim Talukdar and William W. Cohen},
  title = {{Scaling Graph-based Semi Supervised Learning to Large Number of Labels Using Count-Min Sketch}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2014},
  url = {https://openreview.net/forum?id=F0biq2oQ7T},
}

Loading related content...

Figure