Graph Tikhonov Regularization and Interpolation via Random Spanning Forests

Abstract

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.

References in corpus (8)

• Emergence of scaling in random networks
• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Determinantal point processes for machine learning
• The solution path of the generalized lasso
• Chebyshev Polynomial Approximation for Distributed Signal Processing
• Convergence and Stability of Graph Convolutional Networks on Large Random Graphs
• Estimating the inverse trace using random forests on graphs
• Random spanning forests, Markov matrix spectra and well distributed points

Cited by in corpus (1)

• Variance reduction in stochastic methods for large-scale regularised least-squares problems