Semi-Supervised Learning in Network-Structured Data via Total Variation Minimization

Tutkimustuotos: Lehtiartikkelivertaisarvioitu

Tutkijat

  • Alex Jung
  • Alfred Hero
  • Alexandru Mara
  • Saeed Basirian Jahromi
  • Ayelet Heimowitz
  • Yonina C. Eldar

Organisaatiot

  • University of Michigan
  • Ghent University
  • University of Melbourne
  • Princeton University
  • Weizmann Institute of Science

Kuvaus

We provide an analysis and interpretation of total variation (TV) minimization for semi-supervised learning from partially-labeled network-structured data. Our approach exploits an intrinsic duality between TV minimization and network flow problems. In particular, we use Fenchel duality to establish a precise equivalence of TV minimization and a minimum cost flow problem. This provides a link between modern convex optimization methods for non-smooth Lasso-Type problems and maximum flow algorithms. We show how a primal-dual method for TV minimization can be interpreted as distributed network optimization. Moreover, we derive a condition on the network structure and available label information that ensures that TV minimization accurately learns (approximately) piece-wise constant graph signals. This condition depends on the existence of sufficiently large network flows between labeled data points. We verify our analysis in numerical experiments.

Yksityiskohdat

AlkuperäiskieliEnglanti
Artikkeli8902040
Sivut6256-6269
Sivumäärä14
JulkaisuIEEE Transactions on Signal Processing
Vuosikerta67
Numero24
TilaJulkaistu - 2019
OKM-julkaisutyyppiA1 Julkaistu artikkeli, soviteltu

ID: 39381612