Graph Signal Processing

Integral operators play a central role in signal processing, underpinning classical convolution, and filtering on continuous network models such as graphons. While these operators are traditionally analyzed through spectral decompositions, their connection to reproducing kernel Hilbert spaces (RKHS) has not been systematically explored within the algebraic signal processing framework. In this paper, we develop a comprehensive theory showing that the range of integral operators naturally induces RKHS convolutional signal models whose reproducing kernels are determined by a box product of the operator symbols. We characterize the algebraic and spectral properties of these induced RKHS and show that polynomial filtering with integral operators corresponds to iterated box products, giving rise to a unital kernel algebra. This perspective yields pointwise RKHS representations of filters via the reproducing property, providing an alternative to operator-based implementations. Our results establish precise connections between eigendecompositions and RKHS representations in graphon signal processing, extend naturally to directed graphons, and enable novel spatial--spectral localization results. Furthermore, we show that when the spectral domain is a subset of the original domain of the signals, optimal filters for regularized learning problems admit finite-dimensional RKHS representations, providing a principled foundation for learnable filters in integral-operator-based neural architectures.

Despite their theoretical advantages, spectral methods based on the graph Fourier transform (GFT) are seldom used in graph neural networks (GNNs) due to the cost of computing the eigenbasis and the lack of vertex-domain locality in the resulting representations. As a result, most GNNs rely on local approximations such as polynomial Laplacian filters or message passing, which limit their ability to model long-range dependencies. In this paper, we introduce an exact factorization of the GFT into operators acting on subgraphs, which are then combined via a sequence of Cauchy matrices. Building on this factorization, we propose a new class of spectral GNNs, termed L2G-Net (Local to Global Net). Unlike existing spectral methods, which are either fully global (when using the GFT) or local (when using polynomial filters), L2G-Net operates by processing the spectral representations of subgraphs and then combining them via structured matrices. Our algorithm avoids full eigendecompositions, exploiting graph topology to construct the factorization with quadratic complexity in the number of nodes, scaled by the maximum cut size between subgraphs. Experiments stressing long-range dependencies on large graphs show that L2G-Net scales to regimes out of reach for the standard GFT, and is competitive with state-of-the-art methods with orders of magnitude fewer learnable parameters.

Multivariate data often exhibit complex dependencies that violate the assumption of isotropic residual noise. For such cases, we introduce Graph Regularized PCA (GR-PCA). It is a graph-based regularization of PCA that incorporates the dependency structure of the data features by learning a sparse precision graph and biasing loadings toward the low-frequency Fourier modes of the corresponding graph Laplacian. Consequently, high-frequency signals are suppressed, while graph-coherent low-frequency ones are preserved, yielding interpretable principal components aligned with conditional relationships. We evaluate GR-PCA on synthetic data spanning diverse graph topologies, signal-to-noise ratios, and sparsity levels. Compared to mainstream alternatives, it concentrates variance on the intended support, produces loadings with lower graph-Laplacian energy, and remains competitive in out-of-sample reconstruction. When high-frequency signals are present, the graph Laplacian penalty prevents overfitting, reducing the reconstruction accuracy but improving structural fidelity. The advantage over PCA is most pronounced when high-frequency signals are graph-correlated, whereas PCA remains competitive when such signals are nearly rotationally invariant. The procedure is simple to implement, modular with respect to the precision estimator, and scalable, providing a practical route to structure-aware dimensionality reduction that improves structural fidelity without sacrificing predictive performance.

User-generated videos (UGVs) uploaded from mobile phones to social media sites like YouTube and TikTok are short and non-repetitive. We summarize a transitory UGV into several keyframes in linear-time via fast graph sampling based on Gershgorin disc alignment (GDA). Specifically, we first model a sequence of $N$ frames in a UGV as an $M$-hop path graph $\cG^o$ for $M \ll N$, where the similarity between two frames within $M$ time instants is encoded as a positive edge based on feature similarity. Towards efficient sampling, we then ``unfold'' $\cG^o$ to a $1$-hop path graph $\cG$, specified by a generalized graph Laplacian matrix $\cL$, via one of two graph unfolding procedures with provable performance bounds. We show that maximizing the smallest eigenvalue $λ_{\min}(\B)$ of a coefficient matrix $\B = \diag{\h} + μ\cL$, where $\h$ is the binary keyframe selection vector, is equivalent to minimizing a worst-case signal reconstruction error. We maximize instead the Gershgorin circle theorem (GCT) lower bound $λ^-_{\min}(\B)$ by choosing $\h$ via a new fast graph sampling algorithm that iteratively aligns left-ends of Gershgorin discs for all graph nodes (frames). Experiments on multiple short video datasets show that our algorithm achieves comparable or better keyframe selection performance compared to state-of-the-art methods, at a substantially reduced complexity.

We propose a novel framework for learning time-varying graphs from spatiotemporal measurements. Given an appropriate prior on the temporal behavior of signals, our proposed method can estimate time-varying graphs from a small number of available measurements. To achieve this, we introduce three regularization terms in convex optimization problems that constrain the sparseness of temporal variations of the time-varying networks. Moreover, a computationally scalable algorithm is introduced to solve the optimization problem efficiently. The experimental results with synthetic and real datasets (point cloud, temperature, and EEG data) demonstrate that our proposed method outperforms state-of-the-art methods.