Bias-Variance Tradeoff of Graph Laplacian Regularizer

Abstract

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.

arXiv commentaccepted by IEEE Signal Processing Letters

References in corpus (10)

• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Discrete Signal Processing on Graphs
• Discrete Signal Processing on Graphs: Sampling Theory
• Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies
• Random Walk Graph Laplacian based Smoothness Prior for Soft Decoding of JPEG Images
• Deep Community Detection
• Learning Laplacian Matrix in Smooth Graph Signal Representations
• How to learn a graph from smooth signals
• Phase Transitions in Spectral Community Detection
• Estimating the Trace of the Matrix Inverse by Interpolating from the Diagonal of an Approximate Inverse

Cited by in corpus (5)

• When Does Self-Supervision Help Graph Convolutional Networks?
• Fast Graph Sampling Set Selection Using Gershgorin Disc Alignment
• Node-Adaptive Regularization for Graph Signal Reconstruction
• Revisiting Spectral Graph Clustering with Generative Community Models
• Fast & Robust Image Interpolation using Gradient Graph Laplacian Regularizer