2013/10/10 by Partha Talukdar, William W. Cohen, Talukdar, Partha Pratim +1 · 2 citations
Computer Science · #Advanced Image and Video Retrieval Techniques #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Data Classification #Text and Document Classification Technologies
paper · pdf · doi:10.48550/arxiv.1310.2959
openalex publication_date 2013/10/10 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
Graph-based Semi-supervised learning (SSL) algorithms have been successfully\nused in a large number of applications. These methods classify initially\nunlabeled nodes by propagating label information over the structure of graph\nstarting from seed nodes. Graph-based SSL algorithms usually scale linearly\nwith the number of distinct labels (m), and require O(m) space on each node.\nUnfortunately, there exist many applications of practical significance with\nvery large m over large graphs, demanding better space and time complexity. In\nthis paper, we propose MAD-SKETCH, a novel graph-based SSL algorithm which\ncompactly stores label distribution on each node using Count-min Sketch, a\nrandomized data structure. We present theoretical analysis showing that under\nmild conditions, MAD-SKETCH can reduce space complexity at each node from O(m)\nto O(log m), and achieve similar savings in time complexity as well. We support\nour analysis through experiments on multiple real world datasets. We observe\nthat MAD-SKETCH achieves similar performance as existing state-of-the-art\ngraph- based SSL algorithms, while requiring smaller memory footprint and at\nthe same time achieving up to 10x speedup. We find that MAD-SKETCH is able to\nscale to datasets with one million labels, which is beyond the scope of\nexisting graph- based SSL algorithms.\n