PaperlayerView exact revision on arXiv

Source-linked AI summary

A Time-Vertex Signal Processing Framework

Francesco Grassi, Andreas Loukas, Nathanaël Perraudin, Benjamin Ricaud

arXiv:1705.02307v1cs.LG

TL;DR

Graph-structured data often evolve over time, but graph signal processing methods have commonly underused this temporal dimension. The paper introduces a Time-Vertex Signal Processing Framework combining temporal and graph harmonic analysis, with fast joint filtering and time-vertex dictionaries. Across diverse applications, the framework's tools provide benefits for signal processing and learning, including improved filtering accuracy and source localization.

  • Problem

    Graph signal processing needs methods that jointly model graph structure and temporal evolution in dynamic, high-dimensional non-Euclidean data.

  • Method

    The paper links time-domain signal processing with graph signal processing through joint harmonic analysis, PDE-based motivation, FFC filtering, and overcomplete time-vertex dictionaries.

  • Results

    The framework improves joint-filter approximation accuracy by up to two orders of magnitude and supports applications including mesh denoising, video inpainting, and seismic source localization.

  • Takeaways & Limitations

    Joint analysis of time-vertex signals can benefit regression, learning, and diverse signal-processing tasks involving graph time series.

Abstract

from arXiv · show

An emerging way to deal with high-dimensional non-euclidean data is to assume that the underlying structure can be captured by a graph. Recently, ideas have begun to emerge related to the analysis of time-varying graph signals. This work aims to elevate the notion of joint harmonic analysis to a full-fledged framework denoted as Time-Vertex Signal Processing, that links together the time-domain signal processing techniques with the new tools of graph signal processing. This entails three main contributions: (a) We provide a formal motivation for harmonic time-vertex analysis as an analysis tool for the state evolution of simple Partial Differential Equations on graphs. (b) We improve the accuracy of joint filtering operators by up-to two orders of magnitude. (c) Using our joint filters, we construct time-vertex dictionaries analyzing the different scales and the local time-frequency content of a signal. The utility of our tools is illustrated in numerous applications and datasets, such as dynamic mesh denoising and classification, still-video inpainting, and source localization in seismic events. Our results suggest that joint analysis of time-vertex signals can bring benefits to regression and learning.

I. INTRODUCTION

The paper develops Time-Vertex Signal Processing to analyze graph-structured data that evolve over time, addressing limitations of methods that treat temporal samples independently. It connects joint harmonic analysis to PDEs, accurate filtering, redundant dictionaries, and applications in signal processing and learning.

  • High-dimensional datasets often have complex non-Euclidean structure, motivating graph-based representations and graph Fourier analysis.
  • Existing graph-based methods often ignore temporal evolution by processing successive graph signals independently or averaging them globally.For dynamic systems such as traffic networks, this can bias inference by overlooking temporal behavior.
  • The proposed Time-Vertex Signal Processing Framework links time-domain techniques with graph signal processing for jointly analyzing temporal and vertex dimensions.
  • The framework motivates joint analysis through PDEs on graphs, introduces the Fast Fourier-Chebyshev algorithm, and improves non-separable filtering accuracy by up to two orders of magnitude.FFC targets separable and non-separable filtering objectives at similar complexity to previous joint filters.
  • Redundant time-vertex dictionaries provide frame-based representations, including wavelets for signal scales and short-time Fourier transforms for local time-frequency content.
  • Experiments cover denoising, inpainting, compression, classification, and source localization on dynamic meshes, video, and network data.

B. Time-vertex calculus and variation

Time-vertex calculus combines temporal differences with graph-based edge derivatives to characterize variation across consecutive time steps and graph edges. Its joint Laplacian corresponds to a Cartesian-product graph, while mixed norms support signals with different temporal and graph regularity.

  • The framework defines discrete calculus operators to characterize signal smoothness over finite time and graph domains.
  • The symmetric time Laplacian is a discrete second-order time derivative with periodic boundary conditions.
  • The joint gradient concatenates the time gradient with the graph gradient, measuring variation across consecutive time steps and graph edges.
  • The joint Laplacian is equivalent to the Cartesian product of the time and graph Laplacians, forming a multilayer joint graph.Each graph copy corresponds to a time layer, with temporal connections between corresponding nodes at neighboring time steps.
  • The joint gradient's ℓ2 norm measures total variation across edges and consecutive steps, while its ℓ1 norm gives a total-variation regularizer.
  • Mixed norms use independent p- and q-norms with non-negative graph and time weights for signals that vary differently across the two domains.

III. DYNAMICS OVER GRAPHS

The dynamics-over-graphs section uses joint harmonic analysis to characterize solutions of linear PDEs on graphs and to examine nonlinear epidemic processes in the joint frequency domain.

  • Joint Fourier analysis characterizes the state evolution of heat-diffusion and wave PDEs defined on graphs.

A. Linear dynamics on graphs

The framework uses joint time-vertex harmonic analysis to expose structure in graph dynamics, including linear PDEs and epidemic processes. JFT representations reveal patterns that separate conventional time-vertex, GFT, and DFT views.

  • Linear PDE dynamics: Linear graph dynamics can be modeled through heat diffusion and wave equations whose states evolve from an initial condition.The framework analyzes PDE solutions expressed as linear operators applied to the initial condition.
  • Linear PDE dynamics: The heat-diffusion JFT has a smooth non-separable low-pass form determined by the joint response a(λℓ, ωk) = (1 −sλℓ) e−jωk.This response combines graph frequency λℓ with angular frequency ωk.
  • Linear PDE dynamics: Wave-equation stability requires the speed parameter to satisfy s < 4/λmax.This condition follows from requiring arccos(x) to remain defined on x ∈[−1, 1].
  • Linear PDE dynamics: A wave propagating on a graph produces a sparser and more structured JFT than the original time-vertex, GFT, or DFT representations.The comparison is illustrated for waves on a random sensor graph and identifies JFT as the representation revealing the regular pattern.
  • Complex dynamics over networks: For simulated epidemics, JFT spectra distinguish model and contagion settings: SEIRS produces periodic spectral lines, while higher contagion probability occupies larger bandwidth.The larger bandwidth is attributed to the more impulsive behavior of high-probability epidemic breakouts.

IV. FAST FILTERING OF TIME-VERTEX SIGNALS

This section develops fast joint filtering for time-vertex signals, including separable and non-separable responses, and evaluates its accuracy and complexity against existing methods.

  • Illustration: dynamic mesh filtering: Joint low-pass filtering of a dynamic dancer mesh approximates its time-varying skeleton, while a non-separable wave filter emphasizes fluid motion.The low-pass filter attenuates high frequencies in both graph and time domains; the wave filter enhances components non-linearly.
  • Fast filtering: FFC approximates both separable and non-separable joint filters with O(T|E|MG + NT log T) operations and supports distributed implementation.FFT and graph Chebyshev recursion require only local or few-hop information.
  • Numerical comparison: FFC produces significantly more accurate approximations than state-of-the-art methods at the same order, especially for non-separable filters.ARMA2D cannot be used for the non-separable case.
  • Complexity: The FFC complexity is O(T|E|MG + NT log T), compared with O(T|E|MT + NTMT MG) for Cheby2D and O(T|E|MG + T|E|MT) for ARMA2D.ARMA2D is listed only for separable filters, whereas FFC and Cheby2D apply to all filters.

V. TIME-VERTEX DICTIONARIES AND FRAMES

This section constructs time-vertex dictionaries by transforming and jointly localizing spectral kernels, yielding wavelet and short-time Fourier representations for scale and local time-frequency analysis.

  • Representations: The framework generalizes short-time Fourier and wavelet representations by replacing the mother function with a time-vertex spectral kernel and graph translation with joint localization.These representations support time-scale and local time-frequency analysis of time-vertex signals.
  • Joint localization: Joint localization combines graph localization with temporal translation through independent graph-domain localization, inverse DFT, and translation steps.For separable filters, localization can be performed independently in the time and vertex domains.
  • Dictionary construction: The dictionary construction transforms a mother time-vertex kernel across vertex and time parameters, then jointly localizes each resulting kernel at every vertex and time.When redundancy is excessive, the construction can retain only a subset of localization points.
  • Short Time-Vertex Fourier Transform: In the STVFT, a coefficient’s amplitude indicates the presence of spectral mode [zλ, zω] at vertex m and time τ when the mother kernel is localized around [0, 0].Because the mother kernel is separable, its graph and temporal designs can be performed independently.
  • Spectral Time-Vertex Wavelet Transform: The STVWT uses generalized graph dilation with scale parameters zλ and zω, and its mother kernel may be non-separable.The discretization lattice is application-dependent, with m and τ suggested to take all possible vertex and time values.

C. Joint time-vertex frames

The framework uses redundant joint time-vertex dictionaries for analysis and synthesis, with frame conditions ensuring invertibility and fast filtering-based computation. It also identifies a limitation in non-separable subsampled STVFT computation.

  • Time-vertex dictionaries are filter banks whose analysis and synthesis operators transform signals into coefficients and reconstruct them.Analysis coefficients can be acquired through joint filtering, while synthesis sums filtering operations.
  • The transform is generally not exactly reconstructed unless the filter bank is a unitary tight frame.
  • O(|Zλ × Zω|(T|E|MG + NT log T)) is the total analysis complexity using the FFC filtering algorithm, with typically MG ≈50.
  • Non-separable filtering does not exploit lattice subsampling because each filtering operation produces all coefficients.A subsampled STVFT can still be computed efficiently by filtering in the graph domain first and then applying a traditional STFT.
  • A frame condition with bounds 0 < A ≤ B < ∞ guarantees that the dictionary loses no information and is invertible.The ratio A/B is related to the frame operator's condition number and affects reconstruction efficiency.
  • Canonical dual kernels provide a practical inverse transform by enabling a single synthesis operation rather than computationally expensive direct inversion.The canonical dual corresponds to the pseudo-inverse while maintaining low computational complexity.

VI. EXPERIMENTS

Experiments evaluate time-vertex analysis across meshes, traffic, epidemics, video, and seismic data. The reported applications indicate benefits for denoising, recovery, learning, and source localization.

  • The evaluation spans dynamic meshes, PeMS traffic flow, simulated epidemics over Europe, KLCC time-lapse video, and geographically distributed New Zealand earthquake waveforms.
  • Joint analysis is reported to benefit signal denoising and recovery, learning, and source localization problems.
  • The experiments use GSPBOX, UNLocBoX, and LT-FAT, with reproducing code made available online.

A. Compactness of representation

Joint time-vertex representations compact dynamic graph signals and support denoising and video inpainting. Across the reported examples, joint priors exploit structure in both graph and time domains.

  • A. Compactness of representation: JFT has better energy compaction than DFT and GFT across all evaluated datasets, especially for meshes whose graphs capture signal structure well.Compact transforms summarize data and can provide efficient regularizers for regression.
  • A. Compactness of representation: The joint Tikhonov prior enforces smoothness in both graph and time domains through a non-separable lowpass filter.
  • A. Compactness of representation: 0.20 to 0.06: joint denoising reduces the walking-dog mesh's normalized error after Gaussian coordinate noise.Over 20 realizations, joint regularization achieves 0.062 ± 0.0002, compared with 0.067 ± 0.0003 for graph-only and 0.095 ± 0.0002 for time-only methods.
  • B. Regression problems with joint variation priors: The video inpainting setup removes 20% of pixels and 20% of frames from a KLCC time-lapse video, initially yielding normalized error 0.61.The static graph assumption motivates this time-lapse setting because the skyline remains structurally invariant while colors vary over time.
  • B. Regression problems with joint variation priors: 0.049: joint inpainting with an N1,2 regularizer reconstructs the corrupted video with this normalized error.
  • Applications: STVFT representations cluster three dance phases by distances between frame representations and cluster centroids.
  • B. Regression problems with joint variation priors: N1,2 performs better overall because it restores missing frames, while missing-pixel recovery is nearly the same across methods.The comparison includes Tikhonov, TV, and joint regularizers, with errors summarized over pixels-only, frames-only, and the whole video.

C. Overcomplete representations

The framework develops time-vertex representations for extracting localized time-frequency and multiscale structure, then demonstrates their utility in dynamic-mesh clustering and seismic source localization.

  • Clustering dynamic meshes using STVFT: 0.926 accuracy is obtained from features built from the clean dynamic-mesh signal before noise corruption.This provides the clean-signal reference for the noisy classification experiments.
  • Clustering dynamic meshes using STVFT: STVFT extracts features associated with individual time instants for classifying phases in a noisy dynamic mesh.The representation uses a fixed nearest-neighbor graph, rectangular temporal windows, and overlapping windows.
  • Clustering dynamic meshes using STVFT: 0.869 average accuracy at −20 dB is achieved by STVFT, compared with 0.792 for JFT.JFT and STVFT have the highest median accuracies among the evaluated representations, while sparse noise reduces raw-signal accuracy to 0.469 at −20 dB and 0.74 at −10 dB.
  • Seismic epicenter estimation with STVWT: STVWT uses a damped-wave PDE kernel to decompose seismic signals into wave-like components for epicenter estimation.The construction selects 10 equally spaced zλ values in [0, 2], sets zω = 1, and fits the damping factor to the recorded signals.
  • Seismic epicenter estimation with STVWT: 48.5 km average error is obtained by STVWT over 40 seismic events, versus 88.3 km for the amplitude-only baseline.The method estimates sources by averaging coordinates associated with the highest-energy nonzero coefficients.

APPENDIX

The appendix connects graph wave propagation to discrete operators, derives a graph-based wave equation, and establishes stability conditions for its numerical evolution.

  • A. Wave equation: The continuous wave equation is formulated for a function of time and space using the Laplacian operator.Although second order in time, it can be rewritten as a first-order system using v(t) := ∂tu(t).
  • A. Wave equation: The graph wave equation replaces the continuous Laplacian with the graph Laplacian and approximates the second-order time derivative using a stencil.The propagation speed satisfies s > 0, while irregular graph domains make the resulting solution differ from a smooth continuous wave after several iterations.
  • A. Wave equation: Kt,s = Ks(LG, t) is defined as the discrete analogue of the wave propagator, obtained by applying a time-parameterized function to the scaled graph Laplacian.The resulting matrix organizes the propagated graph signals across time.
  • A. Wave equation: The joint spectral representation follows from the graph spectral decomposition and the discrete Fourier basis in time.The appendix identifies the relevant temporal eigenvectors as cosine functions and uses them to obtain the joint-domain form.
  • A. Wave equation: s < 4/λmax is required for stability because arccos(x) is defined only for x ∈ [−1, 1].The condition agrees with the stability analysis of a numerical solver for the discrete wave equation.

B. Frame bound for joint time-vertex dictionaries

The frame-bound result gives sufficient spectral conditions under which a joint time-vertex dictionary preserves signal information with bounded energy distortion.

  • B. Frame bound for joint time-vertex dictionaries: A joint time-vertex dictionary is formed from kernels hz(λ, ω) indexed over joint graph-frequency and time-frequency coordinates.The theorem analyzes these kernels in the joint spectral domain.
  • B. Frame bound for joint time-vertex dictionaries: If 0 < A ≤ B < ∞, the dictionary Dh is a frame for any time-vertex signal X ∈ R^N×T.The bounds are determined by the minimum and maximum values attained by the filters over graph and temporal frequencies.
  • B. Frame bound for joint time-vertex dictionaries: Orthogonality of the eigenvectors and Parseval’s relation establish the lower and upper frame bounds in the joint spectral domain.Each spectral contribution is bounded by the corresponding minimum and maximum filter values.
Loading 1705.02307v1…