Scaling Graph-based Semi Supervised Learning to Large Number of Labels Using Count-Min Sketch
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 significance 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(log m), 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 find that MAD-SKETCH is able to scale to datasets with one million labels, which is beyond the scope of existing graph- based SSL algorithms.
Code (0)
등록된 구현이 없습니다.
Similar Papers 제목 키워드 기반
Large Data and Zero Noise Limits of Graph-Based Semi-Supervised Learning Algorithms
Scalings in which the graph Laplacian approaches a differential operator in the large graph limit are used to develop understanding of a number of algorithms for semi-supervised learning; in particular the extension, to …
Vehicle Trajectory Prediction by Transfer Learning of Semi-Supervised Models
In this work we show that semi-supervised models for vehicle trajectory prediction significantly improve performance over supervised models on state-of-the-art real-world benchmarks. Moving from supervised to semi-superv…
Contrastive LearningTrajectory PredictionTransfer LearningA Graph-Partitioning Based Continuous Optimization Approach to Semi-supervised Clustering Problems
Semi-supervised clustering is a basic problem in various applications. Most existing methods require knowledge of the ideal cluster number, which is often difficult to obtain in practice. Besides, satisfying the must-lin…
Clusteringgraph partitioningAnalysis of $p$-Laplacian Regularization in Semi-Supervised Learning
We investigate a family of regression problems in a semi-supervised setting. The task is to assign real-valued labels to a set of $n$ sample points, provided a small training subset of $N$ labeled points. A goal of semi-…
Analysis of Semi-Supervised Learning on Hypergraphs
Hypergraphs provide a natural framework for modeling multiway interactions. We analyze a class of variational semi-supervised learning problems posed on random geometric hypergraphs and establish asymptotic consistency i…