Title: Semi-supervised Learning in Network-Structured Data via Total Variation Minimization,
Abstract: 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.