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

By Partha P. Talukdar, William W. Cohen. 2013

28 citations recorded by the source corpus.

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 over the structure of graph starting from seed nodes. Graph-based SSL algorithms usually scale linearly with the number of distinct labels (m), and require O(m) space on each node. Unfortunately, there exist many applications of practical signicance with very large m over large graphs, demanding better space and time complexity. In this paper, we propose MAD-Sketch, a novel graph-based SSL algorithm which compactly stores label distribution on each node using Count-min Sketch, a randomized data structure. We present theoretical analysis showing that under mild conditions, MAD-Sketch can reduce space complexity at each node from O(m) to O(logm), and achieve similar savings in time complexity as well. We support our analysis through experiments on multiple real world datasets. We observe that MAD-Sketch achieves similar performance as existing state-of-the-art graph-based SSL algorithms, while requiring smaller memory footprint and at the same time achieving up to 10x speedup. We nd that MAD-Sketch is able to scale to datasets with one million labels, which is beyond the scope of existing graph-based SSL algorithms.

How researchers see this paper

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

1. Steven Euijong Whang
2. Yuji Roh
3. Geon Heo
4. Peter Christen
5. Xin He

Citations in the corpus

• A Survey on Data Collection for Machine Learning: A Big Data - AI Integration Perspective (2018, methodology): “MAD-Sketch algorithm [102] was proposed to further reduce the space and time complexities of graph-based SSL”
• Large Scale Distributed Semi-Supervised Learning Using Streaming Approximation (2015, unknown): “We tried multiple settings for MAD and MAD-SKETCH algorithms and replicated the best reported performance metrics from [28] using these values, so the baseline results are comparable to their system.”