# Trend Filtering on Graphs

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

## Key facts

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

## Built on by (most cited first, 30 of 45)

- [Elastic Graph Neural Networks](https://mlsanity.com/paper/2107.06996/) (2021)
- [A Survey on Graph Representation Learning Methods](https://mlsanity.com/paper/2204.01855/) (2022)
- [Graph Trend Filtering Networks for Recommendations](https://mlsanity.com/paper/2108.05552/) (2021)
- [Graph Filters for Signal Processing and Machine Learning on Graphs](https://mlsanity.com/paper/2211.08854/) (2022)
- [Optimal Dynamic Regret in Exp-Concave Online Learning](https://mlsanity.com/paper/2104.11824/) (2021)
- [Optimal Dynamic Regret in Proper Online Learning with Strongly Convex Losses and Beyond](https://mlsanity.com/paper/2201.08905/) (2022)
- [Untrained Graph Neural Networks for Denoising](https://mlsanity.com/paper/2109.11700/) (2021)
- [Towards Data-centric Graph Machine Learning: Review and Outlook](https://mlsanity.com/paper/2309.10979/) (2023)
- [Minimax Optimal Regression over Sobolev Spaces via Laplacian Regularization on Neighborhood Graphs](https://mlsanity.com/paper/2106.01529/) (2021)
- [Online Label Shift: Optimal Dynamic Regret meets Practical Algorithms](https://mlsanity.com/paper/2305.19570/) (2023)
- [An Optimal Reduction of TV-Denoising to Adaptive Online Learning](https://mlsanity.com/paper/2101.09438/) (2021)
- [Graph Denoising with Framelet Regularizer](https://mlsanity.com/paper/2111.03264/) (2021)
- [Second Order Path Variationals in Non-Stationary Online Learning](https://mlsanity.com/paper/2205.01921/) (2022)
- [Total Variation Graph Neural Networks](https://mlsanity.com/paper/2211.06218/) (2022)
- [Topologically penalized regression on manifolds](https://mlsanity.com/paper/2110.13749/) (2021)
- [Minimax Optimal Regression over Sobolev Spaces via Laplacian Eigenmaps on Neighborhood Graphs](https://mlsanity.com/paper/2111.07394/) (2021)
- [Robust Time Series Dissimilarity Measure for Outlier Detection and Periodicity Detection](https://mlsanity.com/paper/2206.02956/) (2022)
- [Adaptive and non-adaptive minimax rates for weighted Laplacian-eigenmap based nonparametric regression](https://mlsanity.com/paper/2311.00140/) (2023)
- [Multivariate Trend Filtering for Lattice Data](https://mlsanity.com/paper/2112.14758/) (2021)
- [Tree-based Node Aggregation in Sparse Graphical Models](https://mlsanity.com/paper/2101.12503/) (2021)
- [On Convex Clustering Solutions](https://mlsanity.com/paper/2105.08348/) (2021)
- [The Voronoigram: Minimax Estimation of Bounded Variation Functions From Scattered Data](https://mlsanity.com/paper/2212.14514/) (2022)
- [Towards Understanding Graph Neural Networks: An Algorithm Unrolling Perspective](https://mlsanity.com/paper/2206.04471/) (2022)
- [Variance estimation in graphs with the fused lasso](https://mlsanity.com/paper/2207.12638/) (2022)
- [Heterogeneous Federated Learning on a Graph](https://mlsanity.com/paper/2209.08737/) (2022)
- [ASGNN: Graph Neural Networks with Adaptive Structure](https://mlsanity.com/paper/2210.01002/) (2022)
- [Bayes optimal learning in high-dimensional linear regression with network side information](https://mlsanity.com/paper/2306.05679/) (2023)
- [Nonsmooth Nonparametric Regression via Fractional Laplacian Eigenmaps](https://mlsanity.com/paper/2402.14985/) (2024)
- [Adaptive Estimation and Learning under Temporal Distribution Shift](https://mlsanity.com/paper/2505.15803/) (2025)
- [T-LoHo: A Bayesian Regularization Model for Structured Sparsity and Smoothness on Graphs](https://mlsanity.com/paper/2107.02510/) (2021)

## Abstract (arXiv)

We introduce a family of adaptive estimators on graphs, based on penalizing the ℓ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 ℓ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.