Abstract
Graph-based Semi-supervised learning (SSL) algorithms classify initially unlabeled nodes by propagating label information over a graph structure starting from seed nodes. While effective, these methods typically scale linearly with the number of distinct labels ($m$), requiring $O(m)$ space per node. This becomes a prohibitive bottleneck for modern applications with millions of labels. We propose MAD-SKETCH, a novel algorithm that uses the Count-Min Sketch data structure to reduce space complexity to $O(\log m)$. Our experiments demonstrate that MAD-SKETCH maintains accuracy while achieving up to a 10x speedup and scaling to datasets with one million labels—a scale beyond the reach of existing graph-based SSL algorithms.
Introduction: The Label Scaling Problem
Graph-based SSL methods, such as label propagation, are highly effective for spreading known "seed" labels across a graph's edges to classify unlabeled nodes. However, a significant limitation is their memory footprint. Standard algorithms maintain a score for every possible label at every single node. In modern contexts—such as tagging massive image databases or entity typing in open-domain knowledge graphs—the number of labels ($m$) can reach into the millions. Because standard algorithms require $O(m)$ space per node, memory and computational costs explode linearly, often exceeding the capacity of even high-end hardware with 100GB+ of RAM.
Methodology: MAD-Sketch
The proposed solution, MAD-Sketch, builds upon the Modified Adsorption (MAD) framework. To bypass the memory bottleneck, it replaces dense label score vectors with a Count-Min Sketch (CMS). CMS is a randomized, highly memory-efficient data structure traditionally used for frequency estimation in massive data streams.
The core innovation lies in leveraging the linearity of CMS. Since the sketch of a sum of vectors equals the sum of their individual sketches, the weighted average updates required by label propagation can be performed directly on the compressed sketches. This allows the algorithm to operate without ever decompressing the data into dense vectors, saving massive amounts of both memory and compute time.
Key Insights
- Skewed Label Distributions: Empirical evidence shows that label scores in SSL naturally follow a power-law (Zipfian) distribution. CMS is uniquely suited for such data, as it accurately preserves high-frequency items (the most relevant labels) while allowing the "long tail" of irrelevant labels to collide harmlessly.
- Community Structure Constraints: The paper proves that a graph's community structure (low max-conductance) naturally limits the spread of irrelevant labels. This physical property translates into tighter mathematical bounds on the approximation error introduced by sketching.
- Math on Compressed Data: The ability to perform iterative matrix mathematics directly on compressed sketches without decompression is the key to unlocking significant runtime speedups.
Experimental Results
The authors evaluated MAD-Sketch on three real-world datasets: Freebase (192 labels), Flickr-10k (10,000 labels), and Flickr-1m (1,000,000 labels).
Performance and Accuracy
On the Freebase dataset, MAD-Sketch matched the exact method's Mean Reciprocal Rank (MRR of 0.28) while significantly reducing memory and time requirements.
As shown in the results above, MAD-Sketch achieved a 4.7x speedup with a standard sketch size. By utilizing a more aggressive sketch configuration ($w=20, d=8$), the algorithm achieved a 10.8x speedup with no loss in accuracy.
Extreme Scaling to One Million Labels
The most significant result was observed on the Flickr-1m dataset. The standard MAD-Exact algorithm failed due to Out-Of-Memory (OOM) errors within just three iterations, even on a machine with 100GB of RAM.
In contrast, MAD-Sketch successfully processed the one-million-label graph with a constant memory footprint of approximately 15-20 GB, demonstrating its ability to handle scales previously considered unreachable for graph-based SSL.
Conclusion and Future Work
MAD-Sketch provides a scalable path for graph-based SSL in high-dimensional label spaces. While it introduces potential overestimation errors due to hash collisions, these are manageable with appropriate sketch sizing. Future research aims to adapt these sketching techniques to other graph-based SSL methods, such as measure propagation, which do not rely on the same squared-loss linearity.
Summary updated