Trend Filtering on Graphs

Abstract

We introduce a family of adaptive estimators on graphs, based on penalizing the ${\ell }_1$ norm of discrete graph differences. This generalizes the idea of trend filtering [Kim et al. (2009), Tibshirani (2014)], used for univariate nonparametric regression, to graphs. Analogous to the univariate case, graph trend filtering exhibits a level of local adaptivity unmatched by the usual ${\ell }_2$-based graph smoothers. It is also defined by a convex minimization problem that is readily solved (e.g., by fast ADMM or Newton algorithms). We demonstrate the merits of graph trend filtering through examples and theory.

A short version appeared in AISTATS'2015

References in corpus (1)

• Modular proximal optimization for multidimensional total-variation regularization

Cited by in corpus (11)

• Multiscale spatial density smoothing: an application to large-scale radiological survey and anomaly detection
• Learning on Hypergraphs with Sparsity
• Prediction models for network-linked data
• Detecting Localized Categorical Attributes on Graphs
• Better Conditional Density Estimation for Neural Networks
• Nonparametric density estimation by histogram trend filtering
• MOCCA: mirrored convex/concave optimization for nonconvex composite functions
• Interpretable Low-Dimensional Regression via Data-Adaptive Smoothing
• Joint Estimation of Precision Matrices in Heterogeneous Populations
• High-dimensional Gaussian graphical model for network-linked data
• GapTV: Accurate and Interpretable Low-Dimensional Regression and Classification