PaperlayerView exact revision on arXiv

Source-linked AI summary

Kernel-based Reconstruction of Graph Signals

Daniel Romero, Meng Ma, Georgios B. Giannakis

arXiv:1605.07174v1stat.MLcs.LG

TL;DR

The paper addresses reconstruction of graph signals from noisy observations on a subset of vertices and the associated bandwidth or kernel-selection challenges. It develops kernel regression and two multi-kernel approaches that unify SPoG concepts, reduce estimator optimization, and support real-valued graph-signal reconstruction. Synthetic and real-data experiments demonstrate the proposed methods' merits relative to competing alternatives.

  • Problem

    Graph-signal reconstruction must infer vertex attributes from noisy observations on a subset of vertices, while SPoG bandwidths and kernel-based methods' kernels may require difficult model selection.

  • Method

    The paper uses kernel regression on graph-signal RKHSs, applies the representer theorem, interprets covariance kernels probabilistically, and proposes two multi-kernel techniques for real-valued reconstruction.

  • Results

    Synthetic and real-data experiments demonstrate the merits of the proposed methods relative to state-of-the-art alternatives.

  • Takeaways & Limitations

    Kernel regression provides a unifying framework that accommodates bandlimitedness, graph filters, and the graph Fourier transform while enabling complementary multi-kernel model-selection strategies.

Abstract

from arXiv · show

A number of applications in engineering, social sciences, physics, and biology involve inference over networks. In this context, graph signals are widely encountered as descriptors of vertex attributes or features in graph-structured data. Estimating such signals in all vertices given noisy observations of their values on a subset of vertices has been extensively analyzed in the literature of signal processing on graphs (SPoG). This paper advocates kernel regression as a framework generalizing popular SPoG modeling and reconstruction and expanding their capabilities. Formulating signal reconstruction as a regression task on reproducing kernel Hilbert spaces of graph signals permeates benefits from statistical learning, offers fresh insights, and allows for estimators to leverage richer forms of prior information than existing alternatives. A number of SPoG notions such as bandlimitedness, graph filters, and the graph Fourier transform are naturally accommodated in the kernel framework. Additionally, this paper capitalizes on the so-called representer theorem to devise simpler versions of existing Thikhonov regularized estimators, and offers a novel probabilistic interpretation of kernel methods on graphs based on graphical models. Motivated by the challenges of selecting the bandwidth parameter in SPoG estimators or the kernel map in kernel-based methods, the present paper further proposes two multi-kernel approaches with complementary strengths. Whereas the first enables estimation of the unknown bandwidth of bandlimited signals, the second allows for efficient graph filter selection. Numerical tests with synthetic as well as real data demonstrate the merits of the proposed methods relative to state-of-the-art alternatives.

I. INTRODUCTION

The paper frames graph-signal reconstruction as estimating noisy, partially observed vertex attributes and unifies SPoG and machine-learning approaches through kernel-based learning. It further introduces multi-kernel methods for real-valued reconstruction and model selection.

  • I. INTRODUCTION: Graph-signal reconstruction estimates a graph-defined function from noisy observations collected at only a subset of vertices.Graph signals represent vertex attributes such as age, political alignment, or income.
  • I. INTRODUCTION: Kernel-based learning unifies machine-learning and SPoG perspectives while accommodating bandlimitedness, graph filters, and the graph Fourier transform.The framework connects reconstruction with transductive regression, general kernel methods, and covariance-based LMMSE estimation.
  • I. INTRODUCTION: Kernel methods can reduce Tikhonov-regularized reconstruction to lower-dimensional optimization and support richer prior information through covariance kernels.The paper also develops a graphical-model interpretation and a big-data technique for Laplacian-kernel regression.
  • I. INTRODUCTION: Existing SPoG methods often require an unknown signal bandwidth, while kernel methods require selecting an appropriate kernel.The paper identifies model selection as a challenge for both families of methods.
  • I. INTRODUCTION: Two complementary multi-kernel techniques jointly combine dictionary kernels and estimate real-valued graph signals in a single optimization problem.They address bandwidth estimation for bandlimited signals and efficient graph-filter selection.
  • I. INTRODUCTION: Graph kernels can be constructed from graph topology when conventional feature vectors or metric structure on vertices are unavailable.The paper discusses graph kernels as an alternative to embedding vertices into Euclidean space.

A. Representer theorem

The representer theorem expresses graph-signal estimators using coefficients associated with observed vertices, reducing the reconstruction optimization from N variables to S variables. This reduction also simplifies several existing estimators when S is much smaller than N.

  • A. Representer theorem: Because graph-signal RKHSs are finite-dimensional, the representer theorem admits a proof based solely on linear algebra rather than functional analysis.The theorem remains useful even though graph-signal optimization is inherently finite-dimensional.
  • A. Representer theorem: The representer theorem reduces graph-signal reconstruction from optimization over N variables to optimization over S variables, where typically S ≪ N.The coefficients corresponding to unobserved vertices are zero.
  • A. Representer theorem: The theorem determines the form of the estimator but leaves the optimal coefficients to be found by solving the resulting coefficient optimization problem.The coefficients are collected in α := [α1, …, αS]T.
  • A. Representer theorem: Kernel ridge regression has the closed-form estimate ˆf RR = ¯KΦT (K + µSIS)^−1y.The reduced expression inverts an S × S matrix.
  • A. Representer theorem: The reduced formulation generalizes multiple existing signal reconstructors, including Tikhonov-regularized estimators, through appropriate kernel choices.This enables replacing an N × N matrix inversion with an S × S inversion in the cited comparison.

B. Graph kernels for signal reconstruction

Graph kernels construct signal-reconstruction priors from the graph Laplacian and interpret regularization in the graph-Fourier domain. Their kernel columns provide localized interpolating signals, while Laplacian kernels can encode richer spectral information than bandlimited models.

  • Laplacian kernels: Laplacian kernels apply a user-selected nonnegative map r to the eigenvalues of the graph Laplacian, with common choices including diffusion, random-walk, and Laplacian-regularization kernels.The map r is typically increasing in the eigenvalue.
  • Scalability: Obtaining a Laplacian kernel generally requires eigendecomposing the graph Laplacian, which is computationally challenging for large graphs.The paper proposes two complexity-reduction techniques for big-data scenarios in Appendix B.
  • Spectral interpretation: The Laplacian-kernel regularizer weights graph-Fourier coefficients through r(λn), strongly penalizing components whose corresponding weights are large.The graph Fourier transform consists of projections onto the Laplacian eigenvectors.
  • Spectral interpretation: Increasing r favors smooth signals because smooth signals are expected to have decreasing graph-Fourier magnitudes, and it can use coefficient magnitude information beyond Fourier-support constraints.Bandlimited reconstructors capture support, whereas Laplacian kernels can also leverage magnitude information.
  • Circular-graph example: For circular graphs, the Laplacian is circulant and diagonalized by the standard Fourier matrix, yielding a kernel matrix whose entries depend on index differences.The kernel columns are circular shifts of one another and can be interpreted as centered interpolating signals analogous to sinc functions.

2) Bandlimited kernels:

Bandlimited kernels embed bandlimited signal reconstruction within kernel ridge regression. They recover least-squares estimation as a limiting case while retaining a nonsingular-kernel formulation and supporting probabilistic graph interpretations.

  • Bandlimited kernels: A bandlimited kernel is introduced to show that least-squares estimation for bandlimited signals is a limiting case of kernel ridge regression.The construction is used later to estimate an unknown signal bandwidth from observations.
  • Bandlimited signals: A graph signal is bandlimited when its graph-Fourier expansion has coefficients supported on a subset B of Laplacian eigenvectors.Its bandwidth can be defined as either the cardinality of B or the greatest element of B.
  • Least-squares reconstruction: For a bandlimited signal, least-squares reconstruction uses the observed samples and requires U_B^T Φ^T Φ U_B to be invertible for the Fourier coefficients to be identifiable.The observations satisfy y = ΦU_B f̃_B + e.
  • Relationship to least squares: As β → ∞, kernel ridge regression with the bandlimited kernel converges to the least-squares estimator under the stated invertibility condition.Setting μ = 0 yields exact equality, but produces a degenerate kernel-based estimate.
  • Probabilistic interpretation: The deterministic formulation is complemented by a probabilistic interpretation in which the optimal ridge-regression kernel is the covariance matrix of the signal.The interpretation also characterizes estimates through local LMMSE conditions on a Markov random field.

3) Covariance kernels:

Covariance kernels connect kernel ridge regression with linear minimum mean-square estimation and Markov random-field interpretations of graph signal reconstruction.

  • Covariance kernels: Kernel ridge regression equals the LMMSE estimator when its kernel matrix is the signal covariance C and µS equals the noise variance σ²_e.The kernel similarity κ(v_n,v_n′) then represents cov[f₀(v_n),f₀(v_n′)].
  • Covariance kernels: For mean-square-error minimization, Proposition 2 motivates choosing the kernel matrix close to the signal covariance C.Historical data can support covariance-based kernel selection and parameter tuning, although investigating such approaches is outside the paper’s scope.
  • Covariance kernels: With covariance kernel C, unobserved vertices are estimated from neighboring ridge estimates, while observed values are corrected by estimated observation noise.This yields local LMMSE conditions on a Markov random field.
  • Covariance kernels: Using a kernel different from C preserves a related interpretation on a conditional correlation graph with the adopted kernel as its signal covariance matrix.The conditional correlation graph can be constructed from the inverse covariance structure.

4) Further kernels:

The paper relates kernel-based smoothing to graph filters, showing that ridge smoothers can be implemented through decentralized graph-filter operations.

  • Further kernels: Several existing reconstructors, including least-squares and Tikhonov estimators, can be represented as kernel methods for suitable kernel matrices.This places established graph-signal reconstruction methods within the kernel framework.
  • Kernel-based smoothing and graph filtering: Kernel smoothers can be implemented in a decentralized fashion because graph-filter operations use successive Laplacian products computable through neighboring vertices.This establishes a two-way link between ridge regression smoothers and graph filters.
  • Kernel-based smoothing and graph filtering: Ridge regression smoothing can be interpreted as graph filtering with frequency response r̃(Λ), and conversely a filter determines a coincident Laplacian kernel.The filter implementation uses successive products with the graph Laplacian and neighbor exchanges.
  • Kernel-based smoothing and graph filtering: Figure 2 evaluates NMSE against the diffusion-kernel parameter σ² for several bandwidths B under fixed sampling, graph size, SNR, and regularization settings.The accompanying discussion emphasizes both σ² sensitivity and dependence of the optimum σ² on B.

IV. MULTI-KERNEL GRAPH SIGNAL RECONSTRUCTION

The multi-kernel section addresses kernel sensitivity by selecting suitable kernels from a user-specified dictionary, with complementary algorithms for bandwidth and graph-filter selection.

  • Motivation: Kernel methods are sensitive to kernel choice, and the optimal diffusion parameter σ² depends on the signal bandwidth B.Figure 2 studies NMSE under fixed N, S, SNR, and µ while varying σ² across bandwidths.
  • Motivation: Bandlimited-signal estimators degrade when the assumed frequency support differs from the actual support, while the true bandwidth B is unknown in practice.Existing bandwidth-setting approaches rely on S and L and disregard observations y.
  • Multi-kernel framework: The proposed multi-kernel framework selects suitable kernels from a user-specified dictionary through two algorithms with complementary strengths.Because each kernel determines an RKHS, kernel selection is equivalent to RKHS selection.
  • Multi-kernel framework: The multi-kernel objective uses a sparsity-promoting regularizer on component norms, making it an instance of group Lasso.The selected expansion therefore favors sparse use of the available RKHS components.
  • Algorithms: ADMM solves the multi-kernel optimization by alternating updates of coefficient blocks and auxiliary variables, followed by multiplier updates.The resulting procedure is summarized as Algorithm 1.
  • Algorithms: Algorithm 2 enables kernel selection for ridge smoothing, which is equivalent to optimal graph-filter selection for graph-signal denoising.For Laplacian kernels, shared eigenvectors allow particularly efficient implementation.
  • Implementation considerations: Kernel normalization is recommended to prevent imbalances during kernel selection.The paper also notes that overlapping graph-signal RKHSs prevent use of a direct-sum RKHS construction assumed by another MKL approach.

B. Kernel superposition

Kernel superposition jointly learns nonnegative kernel weights and signal coefficients, trading sparse kernel expansions for a substantially smaller optimization problem. Its Laplacian-kernel specialization enables efficient graph filter selection.

  • Kernel superposition: The alternative MKL approach uses M + S variables instead of MS, but does not guarantee a sparse kernel expansion.It is introduced as a lower-dimensional alternative to the sparse-kernel MKL algorithm.
  • Kernel superposition: Kernel superposition models the combined kernel as a nonnegative weighted sum of dictionary kernels and jointly optimizes weights with signal coefficients.The optimization is separately convex in the weights and coefficients for convex loss functions, although generally not jointly convex.
  • Kernel superposition: The interpolated iterative algorithm solves this optimization for squared loss with kernel weights constrained to a nonnegative Euclidean ball.The radius constraint prevents the weights from diverging.
  • Kernel superposition: For ridge smoothing, kernel selection is equivalent to optimal graph-filter selection, and shared Laplacian-kernel eigenvectors make the updates efficient.The coefficient update can be replaced by a scalar version in the graph-Fourier domain.

V. NUMERICAL TESTS

Synthetic experiments evaluate reconstruction and bandwidth estimation using Monte Carlo tests on random graphs. The proposed MKL estimators remain competitive without knowing the signal bandwidth and can perform well with few samples, while automatic sparsity-path selection remains unresolved.

  • Synthetic experiments: Monte Carlo experiments compare proposed methods with alternatives across random signals, noise, and uniformly sampled vertex sets.The synthetic tests use an Erdős–Rényi graph and bandlimited signals with controlled bandwidth and signal-to-noise ratio.
  • Synthetic bandlimited signals: The bandlimited-signal comparison evaluates NMSE across sampling sizes for a signal with bandwidth B = 20, including MKL, LS, and bandwidth-mismatched estimators.The MKL methods use five bandlimited kernels with bandwidths 5m + 5.
  • Synthetic bandlimited signals: The proposed MKL estimators perform no worse than the BL estimator with perfect bandwidth knowledge despite not knowing the bandwidth.They also provide reasonable performance for small S, avoiding the LS estimator’s need for S ≥ B samples.
  • Bandwidth estimation: Increasing the sparsity penalty forces the MKL expansion toward one kernel, whose bandwidth is expected to be closest to the observed signal’s bandwidth.The sparsity path is illustrated for a signal with B = 20 using a dictionary of 17 bandlimited kernels.
  • Bandwidth estimation: A fully automatic rule for identifying the last vanishing coefficient is not straightforward, so the paper evaluates a naive estimator at a prespecified penalty value.The estimator selects the dictionary bandwidth associated with the largest kernel coefficient norm.

B. Real data

Real-data experiments test graph-signal prediction on temperature and airport-delay data. They use training data for graph construction or covariance estimation and evaluate generalization on held-out signals, while the conclusion reports support for the framework’s theoretical findings.

  • Real-data experiments: Real-data experiments split each data set into training and test portions, using held-out observations to evaluate reconstruction performance.Unlike the synthetic tests, the noiseless target signal is unavailable for direct NMSE evaluation on observed and unobserved vertices.
  • Temperature data: The temperature data contain 24 monthly signals measured at 89 Swiss stations, with 12 signals for training and 12 for testing.The task estimates unobserved station values from samples at S vertices.
  • Airport data: The airport data contain 184 daily arrival-delay signals over 50 high-traffic U.S. airports derived from 3 · 10^6 flights.A graph edge connects airports with more than 100 flights during the observation window.
  • Real-data methodology: The covariance-kernel estimator is only nearly optimal because the true data covariance is unknown.Its kernel uses the inverse of the sample covariance matrix estimated from normalized training signals.
  • Real-data methodology: The real-data graph construction required estimating valid Laplacian weights from a matrix solution, but the rationale and details of this approach are omitted.This limitation affected experiments using Laplacian kernels or bandlimited estimators.
  • Airport data: Airport-delay prediction is evaluated with generalization NMSE and root mean-square error when 10 airports are observed and 40 are predicted.The comparison includes a covariance-kernel ridge estimator and multi-kernel methods using 30 diffusion kernels.
  • Conclusions: The conclusion reports that numerical experiments corroborated the validity of the paper’s theoretical findings.It also identifies future work on learned Laplacians, directed graphs, and additional data sets.

APPENDIX A PROOF OF THE REPRESENTER THEOREM

The appendix proves a finite-dimensional representer theorem for graph-signal RKHSs using linear algebra. It decomposes functions into sampled and sampling-null components, then connects the resulting reduced representation to limiting least-squares estimators and computational reductions.

  • Representer theorem: Every graph-RKHS function can be decomposed into a component expanded at sampled vertices and a component that vanishes on the sampling set.This provides an alternative parameterization using sampled-vertex coefficients and a sampling-null residual.
  • Representer theorem: The decomposition is established by choosing coefficients that match the sampled kernel representation while enforcing ΦK̄β = 0.The proof uses equality of the relevant matrix ranges and an eigendecomposition of K̄.
  • Representer theorem: Because the loss depends only on sampled values while the regularizer increases with the residual component, the minimizer sets the sampling-null component to zero.This yields the reduced representer form for the estimator.
  • Computational reductions: Laplacian-kernel matrix evaluation has O(N^3) complexity, motivating approximations based on coarser spectral regularization or low-order polynomials.Sparse Laplacians make powers of L efficient to compute, and the polynomial approach avoids eigenvector computation.
  • Bandlimited limit: As the out-of-band regularization tends to infinity, ridge regression with a bandlimited kernel converges to the least-squares bandlimited estimator.The proof separates in-band and out-of-band blocks and applies block matrix inversion.

APPENDIX D PROOF OF PROPOSITION 3

The proof interprets the optimality condition through conditional estimation in a Gaussian graphical model. At unobserved vertices, reconstructed values agree with LMMSE estimates based on neighboring values, while observed vertices retain observation-specific conditions.

  • Derivation: The proof starts from the first-order optimality condition for the reconstruction problem and rewrites it using block-matrix inversion.The derivation partitions the covariance-related matrix and applies block matrix inversion formulae.
  • Probabilistic interpretation: The conditional variance c1|2:N equals the variance of the LMMSE predictor for f0(v1) given f0(v2), ..., f0(vN).
  • Unobserved vertices: For an unobserved vertex, the optimality condition uses only neighboring vertices because nonadjacent variables have zero precision-matrix entries in the Markov random field.Conditional independence across nonadjacent vertices implies γn,n′ = 0 when no edge connects vn and vn′.
  • Unobserved vertices: Reconstructed values at unobserved vertices agree with their LMMSE estimates given the estimated values at their neighbors.
  • Observed vertices: For an observed vertex, the corresponding row of the observation matrix has a one on its diagonal, yielding a distinct optimality condition from the unobserved case.
Loading 1605.07174v1…