# Semi-supervised Learning in Network-Structured Data via Total Variation Minimization

arXiv: https://arxiv.org/abs/1901.09838 · HTML: https://mlsanity.com/paper/1901.09838/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jan 2019.

## Built on by (most cited first, 10 of 10)

- [Elastic Graph Neural Networks](https://mlsanity.com/paper/2107.06996/) (2021)
- [Data-heterogeneity-aware Mixing for Decentralized Learning](https://mlsanity.com/paper/2204.06477/) (2022)
- [Clustered Federated Learning via Generalized Total Variation Minimization](https://mlsanity.com/paper/2105.12769/) (2021)
- [Compressed Regression over Adaptive Networks](https://mlsanity.com/paper/2304.03638/) (2023)
- [flow-based clustering and spectral clustering: a comparison](https://mlsanity.com/paper/2206.10019/) (2022)
- [Plug In and Learn: Federated Intelligence over a Smart Grid of Models](https://mlsanity.com/paper/2302.04363/) (2023)
- [Learning Graph ARMA Processes from Time-Vertex Spectra](https://mlsanity.com/paper/2302.06887/) (2023)
- [LogSpecT: Feasible Graph Learning Model from Stationary Signals with Recovery Guarantees](https://mlsanity.com/paper/2305.01379/) (2023)
- [Locally Stationary Graph Processes](https://mlsanity.com/paper/2309.01657/) (2023)
- [Hierarchical Clustering and Signal Denoising on Digraphs](https://mlsanity.com/paper/2609.34670/) (2026)

## Abstract (arXiv)

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.