Bias-Variance Tradeoff of Graph Laplacian Regularizer
This work addresses parameter selection for graph-based learning tasks, providing theoretical insights that could improve performance in graph signal processing and semi-supervised learning, though it is incremental as it builds on existing regularization methods.
The paper analyzes the bias-variance tradeoff of graph Laplacian regularizer, deriving scaling laws for the optimal regularization parameter based on spectral properties and a new signal-to-noise ratio, and shows near-optimal performance in experiments on synthetic and real-world graphs.
This paper presents a bias-variance tradeoff of graph Laplacian regularizer, which is widely used in graph signal processing and semi-supervised learning tasks. The scaling law of the optimal regularization parameter is specified in terms of the spectral graph properties and a novel signal-to-noise ratio parameter, which suggests selecting a mediocre regularization parameter is often suboptimal. The analysis is applied to three applications, including random, band-limited, and multiple-sampled graph signals. Experiments on synthetic and real-world graphs demonstrate near-optimal performance of the established analysis.