CS Paper Radar

Unrolling a Graph-Laplacian Denoiser Realizes Only Compositions of Polynomial Graph Filters

Seyed Alireza Hosseini

eess.SP eess.IV ·submitted 2026-08-10 17:58 UTC · v1
theory

Abstract

A recent construction of unrolled networks for graph-based image restoration forms a system matrix from a graph-Laplacian denoiser through a truncated Taylor expansion, then inverts it with a fixed number of conjugate-gradient steps, with the coefficients of both stages learned. This paper shows the resulting map is a polynomial in the denoising operator, of degree at most the product of the two truncation orders, for every setting of those coefficients and therefore at every point of training: the learned steps select an element of a Krylov subspace they cannot enlarge. At the orders used in practice the reachable set is moreover a measure-zero subset of the polynomial class of the network's own degree budget, so the composition constrains the hypothesis space rather than enlarging it. At the standard initialization the realized spectral response is obtained in closed form, exceeding the intended response throughout the interior of the spectrum and approaching a nonzero floor. A lower bound on the operator's condition number, internal to the graph construction rather than to image content, then places the order required for a prescribed accuracy well above the order used in practice. The confining class is precisely the spectral graph filters for which a direct, convex parameterization has long been available.

Closest papers

Nearest neighbours by meaning across the whole index.

Unrolling Lanczos for Ideal Low-pass Graph Filter Approximation

eess.SP ·2026-09-24 ·Parham Eftekhar, Gene Cheung, Mingxiao Liu, H. Vicky Zhao, Xuejun Han +1 more
theory similarity 0.68
Abstract

Low-pass (LP) filtering is a fundamental operation in graph signal processing (GSP). Among finite-order nodal-domain methods, Lanczos-based filtering provides more accurate approximations of ideal LP filters than Chebyshev polynomial methods. We show that the approximation of Lanczos filtering can be further improved through algorithm unrolling and data-driven parameter learning. The key insight is that, because ideal LP filtering is a projection operation into the low-frequency eigen-subspace $\cS_K$, instead of approximating individual eigen-pairs of a graph Laplacian $Ł$ as done in classical Lanczos, an unrolled Lanczos network can directly approximate $\cS_K$. Specifically, we first establish a theorem identifying properties of the Lanczos tridiagonal matrix $\T_m$ that promote accurate approximation of the low-frequency eigen-subspace $\cS_K$. Guided by this theory, we relax the orthogonality constraint on Lanczos vectors, resulting in Ritz vectors that better span $\cS_K$. To ensure numerical stability, we constrain $\T_m$ to be similar to a symmetric matrix, thereby guaranteeing real-valued eigenvalues. Experimental results on random graphs and learned graphs in two natural language processing (NLP) tasks show that our unrolled Lanczos network achieves superior ideal LP filter approximation compared to the classical Lanczos method.

0.16

Joint Image Denoising and Interpolation via Mixed Graph Filtering

eess.IV cs.CVeess.SP ·2026-11-18 ·Gene Cheung, Niruhan Viswarupan, Romisaa Elsaidy
similarity 0.61
Abstract

Images often require both denoising and interpolation, yet treating the two tasks separately is suboptimal: interpolation introduces correlated noise that complicates subsequent denoising, while denoising may remove image details useful for interpolation. In this paper, we study joint image denoising and interpolation from a mixed graph filtering perspective, where denoising is modeled using undirected graph filters and interpolation using directed graph filters. We first establish that, under mild conditions, any (pseudo-)linear denoiser and interpolator can be interpreted as solution filters of maximum a posteriori (MAP) estimation problems regularized by undirected and directed graph smoothness priors, respectively. Guided by these results, we formulate graph-based joint denoising and interpolation problems using both directed and undirected graph structures. We characterize when joint denoising/interpolation reduces to a separable pipeline and when a genuinely coupled optimization is required. For the non-separable case, we recover sparse graph operators from given denoisers and interpolators, yielding an efficient linear-system formulation solvable via conjugate gradient. Experimental results demonstrate that our proposed joint framework consistently outperforms separate denoising and interpolation pipelines across multiple denoiser-interpolator combinations.

0.23

ST-GFM: Spectral-Temporal Graph Forecasting with Measured Perturbation Bounds and Masked Spectral Reconstruction

cs.LG eess.SPstat.ML ·2026-11-02 ·Aashish Bohra, Vivek Vijay
theory similarity 0.57
Abstract · 21 Pages, 11 Figures, 12 Tables, Supplementary Materials attached, Under Review

Graph forecasters for sensor networks are trained in one regime and deployed in others, where sensor coupling and signal frequency content both change. We split this spectral shift into an operator channel and a frequency channel, each with a dimensionless measure. ST-GFM (Spectral-Temporal Graph Forecasting Model) filters every input step with Chebyshev and bidirectional diffusion filters on one learned, non-symmetric operator and alternates them with per-node temporal attention. For the operator channel we prove Frobenius-norm perturbation bounds for both graph branches, show that the Chebyshev bound is attained to first order, and compute its constant from the trained weights and the measured operator norm: 17.9 on METR-LA and 21.5 on PEMS-BAY. Under random edge dropout the trained layer moves by 2.0% to 3.1% of this bound. Masked Spectral Reconstruction (MSR), a self-supervised loss active in the first 40 epochs, matches the log power spectrum of the encoder output to that of the input. For small log-spectral residuals on unclamped bins it is proportional to an Itakura-Saito divergence to leading order. Removing it raises the 60-minute MAE by 0.30 on METR-LA, close to the 0.33 lost when all three self-supervised losses go. Under one shared evaluation pipeline, the 60-minute MAE of ST-GFM is 3.5% below a retrained STAEformer on METR-LA and 13.0% below it on PEMS-BAY. Its 60-minute MAE is 3.0980.017 on METR-LA (five seeds) and 1.5760.006 on PEMS-BAY (three seeds), the lowest PEMS-BAY MAE among twelve published baselines.

0.32

Provable Guarantees for Spectral Structured Prediction

cs.LG ·2026-09-16 ·Violet Zheng, Jean Honorio
similarity 0.57
Abstract

Structured prediction is the simultaneous prediction of multiple labels, and is widely used in various fields, such as natural language processing and computer vision. In this paper, we study binary node label recovery on signed graphs with edge-flip noise, a model introduced by (Globerson et al., 2015), via a simple spectral method that decodes node labels from the signs of the principal eigenvector of the noisy signed adjacency matrix. We develop graph structure-agnostic theoretical guarantees for approximate inference of node labels as well as guarantees for maximum angle deviation with respect to the ground truth node labels. By leveraging tools from matrix concentration theory and eigenvector perturbation analysis, we derive new concentration inequalities that explicitly quantify the effect of the spectral gap of the adjacency matrix, number of nodes, degree distribution, and noise level. As a corollary, we relate our general results to the Cheeger constant and provide results for different classes of graphs. We perform several synthetic experiments to validate our theory. To the best of our knowledge, we are the first to provide theoretical guarantees for the spectral-based approach. As a byproduct of our analysis, we derive technical results that might be of independent interest and useful for other machine learning problems.

0.31

Plug-and-Play Methods Provably Converge Even with Improperly Trained Denoisers: Convergence by Architectural Design

eess.SP math.OCstat.ML ·2026-09-27 ·Henry Pritchard, Rahul Parhi
similarity 0.57
Abstract

Plug-and-Play (PnP) methods replace proximal operators with learned denoisers, which produce state-of-the-art reconstruction quality, but sacrifice the variational interpretation and convergence guarantees of proximal methods. Learned Proximal Networks (LPNs) address this problem by designing the denoiser architecture so that it is exactly the proximal operator of a regularizer. In this work, we clarify the theoretical foundations of LPNs and extend the framework to a broader class of activation functions. We then study two practical mechanisms for controlling the learned prior: (i) averaging the LPN with the identity, a common heuristic in PnP methods, and (ii) directly scaling the implicit regularizer induced by the proximal operator. In particular, we characterize the regularizer induced by averaging and develop a convergent method for evaluating the scaled proximal operator.

0.21

Spectral Limits of Polynomial Graph Filters on the Long-Range Ising Model Benchmark

cs.LG ·2026-10-15 ·Amin Najafgholizadeh, Mohsen Afsharchi
benchmarktheory similarity 0.56
Abstract · 30 pages, 4 figures, 15 tables

The Long-Range Ising Model benchmark (LRIM) guarantees long-range dependence by construction: each label is the node's spin times the spin field convolved with a power-law coupling, so any model's distance from the target is measurable. We prove that a readout whose filter is a polynomial in the adjacency, the linear core of isotropic message passing and spectral graph networks, leaves an error floor that no degree lowers, because the target varies along a level set of the spectrum on which every such filter is constant. Computed exactly, the floor and the best filter of each degree predict two spectral networks adapted from published architectures to within a tenth of a decade. A filter escapes the floor only if it weighs separately the offsets the adjacency lumps together, and must still resolve the coupling across the whole lattice. A strided filter of about fifty coefficients does both: fitted to the training labels, its test error is 52 times below the best published network's. A dilated convolutional network beats the best published result at 256 nodes, matches it at 1,024, and gives the first in-domain results at the three larger sizes, while a Fourier neural operator with its standard modes falls further behind as the lattice grows. At its standard budget the dilated network stays two to four orders of magnitude short of a larger strided filter fitted to the labels. The analysis carries over to the benchmark's second coupling.

0.25

Polynomial Denoisers on the Image Manifold: Volterra Networks for Self-Contained Pixel Diffusion

cs.AI ·2026-11-07 ·Siddharth Roheda, Rohit Chowdhury, Amit Satish Unde, Aniruddha Bala
theory similarity 0.56
Abstract

Natural images are often conjectured to lie on a low-dimensional manifold within the high-dimensional pixel space. Recent work leverages this to build self-contained pixel-space diffusion models without specialized machinery or pretrained components. A plain Transformer on raw image patches suffices, provided it predicts the clean image rather than the noise and compresses each patch through an aggressive bottleneck. The mixing operator, however, has remained softmax attention, inherited from sequence modeling rather than derived from denoising. For Gaussian noise, the optimal denoiser admits a canonical expansion in polynomial functionals of the observation, the Wiener--Volterra series. We prove that softmax attention, and any normalized mixing rule (including linear attention), cannot realize any polynomial map beyond an affine one. In contrast, Volterra layers realize this class directly and, on a data manifold, achieve approximation rates governed by the manifold dimension rather than the ambient pixel dimension. We therefore propose the architecture these results prescribe; raw image patches passed through a bottleneck embedding, followed by cascaded low-rank Volterra layers, which carry no activation function because each layer is nonlinear in its own right. To our knowledge this is the first pixel-space diffusion architecture whose mixing operators are Volterra layers throughout, with no attention, no convolution, no pretrained components, and no activation function on the residual path. On ImageNet $256 \times 256$ and $512 \times 512$, the resulting model is competitive with self-contained pixel-space diffusion at matched parameter and FLOP budgets.

0.15

Spectral Graph Neural Networks with Hermite Polynomials: A Comprehensive Study

cs.LG ·2026-09-24 ·Shuang Wu
similarity 0.56
Abstract

We study spectral graph neural networks built from Hermite polynomials and propose HermNet, a simple model that combines a nodewise predictor with normalized Hermite propagation. Its sparse recurrence requires neither eigendecomposition nor a learned basis. We distinguish the basic model from optional coordinate calibration, response normalization and Gaussian derivative regularization. Hermite and other complete polynomial bases span the same degree-bounded filter space, but their coordinates can produce different optimization behavior under limited training budgets. We analyze this behavior through spectral signal energy, label sampling, changes in learned features and the bias--variance trade-off of regularization. Controlled synthetic experiments identify a regime in which plain HermNet outperforms matched polynomial-basis alternatives, including with a jointly trained nonlinear predictor. Curvature regularization further improves HermNet when the same functional penalty is available to every comparator. Fixed-predictor controls support the advantage under short training budgets, but longer training removes the plain-model lead. Matched real-data comparisons show accuracy deficits, and architectural and numerical studies identify further limits. Together, the analysis and experiments clarify when Hermite propagation is useful and how calibration and regularization affect its performance.

0.28