# Graph Tikhonov Regularization and Interpolation via Random Spanning Forests

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

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Nov 2020.

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

- [A Unified Framework for Fair Spectral Clustering With Effective Graph Learning](https://mlsanity.com/paper/2311.13766/) (2023)
- [Sparsification of the regularized magnetic Laplacian with multi-type spanning forests](https://mlsanity.com/paper/2208.14797/) (2022)
- [Efficient Edge Rewiring Strategies for Enhancing PageRank Fairness](https://mlsanity.com/paper/2602.02512/) (2026)
- [A Review of Graph-Powered Data Quality Applications for IoT Monitoring Sensor Networks](https://mlsanity.com/paper/2410.21006/) (2024)

## Abstract (arXiv)

Novel Monte Carlo estimators are proposed to solve both the Tikhonov regularization (TR) and the interpolation problems on graphs. These estimators are based on random spanning forests (RSF), the theoretical properties of which enable to analyze the estimators' theoretical mean and variance. We also show how to perform hyperparameter tuning for these RSF-based estimators. TR is a component in many well-known algorithms, and we show how the proposed estimators can be easily adapted to avoid expensive intermediate steps in generalized semi-supervised learning, label propagation, Newton's method and iteratively reweighted least squares. In the experiments, we illustrate the proposed methods on several problems and provide observations on their run time.