Semi-supervised Learning in Network-Structured Data via Total Variation Minimization
We propose and analyze a method for semi-supervised learning from partially-labeled network-structured data. Our approach is based on a graph signal recovery interpretation under a clustering hypothesis that labels of data points belonging to the same well-connected subset (cluster) are similar valued. This lends naturally to learning the labels by total variation (TV) minimization, which we solve by applying a recently proposed primal-dual method for non-smooth convex optimization. The resulting algorithm allows for a highly scalable implementation using message passing over the underlying empirical graph, which renders the algorithm suitable for big data applications. By applying tools of compressed sensing, we derive a sufficient condition on the underlying network structure such that TV minimization recovers clusters in the empirical graph of the data. In particular, we show that the proposed primal-dual method amounts to maximizing network flows over the empirical graph of the dataset. Moreover, the learning accuracy of the proposed algorithm is linked to the set of network flows between data points having known labels. The effectiveness and scalability of our approach is verified by numerical experiments.
Code (0)
등록된 구현이 없습니다.
Tasks
Clusteringcompressed sensingSimilar Papers 제목 키워드 기반
Scalable Semi-Supervised Learning over Networks using Nonsmooth Convex Optimization
We propose a scalable method for semi-supervised (transductive) learning from massive network-structured datasets. Our approach to semi-supervised learning is based on representing the underlying hypothesis as a graph si…
Transductive LearningPutting Self-Supervised Token Embedding on the Tables
Information distribution by electronic messages is a privileged means of transmission for many businesses and individuals, often under the form of plain-text tables. As their number grows, it becomes necessary to use an …
Weighted Nonlocal Total Variation in Image Processing
In this paper, a novel weighted nonlocal total variation (WNTV) method is proposed. Compared to the classical nonlocal total variation methods, our method modifies the energy functional to introduce a weight to balance b…
BIG-bench Machine LearningClusteringColorizationImage Colorization+1Semi-Supervised Learning via Sparse Label Propagation
This work proposes a novel method for semi-supervised learning from partially labeled massive network-structured datasets, i.e., big data over networks. We model the underlying hypothesis, which relates data points to la…
compressed sensingUnsupervised Total Variation Loss for Semi-supervised Deep Learning of Semantic Segmentation
We introduce a novel unsupervised loss function for learning semantic segmentation with deep convolutional neural nets (ConvNet) when densely labeled training images are not available. More specifically, the proposed los…
Semantic Segmentation