Sampling of graph signals based on joint time-vertex fractional Fourier transform

Yu Zhang, Bing‐Zhao Li

TL;DR

This paper introduces a novel framework for sampling and reconstructing time-varying graph signals using the Joint Time-Vertex Fractional Fourier Transform (JFRFT). By introducing fractional-order flexibility into both the temporal and spatial domains, the authors provide a more powerful tool for handling non-stationary and "chirp-like" signals that traditional methods struggle to capture.

What Problem Does This Paper Address?

Graph Signal Processing (GSP) is essential for analyzing data on irregular structures, like sensor networks or social grids. However, most real-world data isn't static; it evolves over time. While the standard Joint Fourier Transform (JFT) can handle time-varying graph signals, it has a major limitation: it is "rigid."

The JFT performs a fixed rotation from the time/vertex domain to the frequency domain. This works well for stationary signals but fails to efficiently represent non-stationary signals—specifically "chirp-like" signals where the frequency changes over time. Furthermore, the volume of data in these joint domains is often massive, making it physically or computationally impossible to record every data point. The challenge is: How can we pick the smallest possible subset of data points (sampling) and still perfectly reconstruct the original signal?

Methods

The authors propose the JFRFT, which generalizes the standard JFT by adding two fractional parameters: $\alpha$ (for time) and $\beta$ (for the graph).

Key components of their approach include:

  • Fractional Flexibility: Unlike the standard Fourier transform (which is a 90-degree rotation to the frequency axis), the JFRFT allows for rotation by any fractional angle. This lets researchers "tune" the transform to find the most compact representation of a signal.
  • Sampling Theory: The paper mathematically defines what it means for a signal to be "jointly bandlimited" in this fractional space and derives the conditions required for perfect recovery.
  • Optimal Sampling Selection: They propose five greedy strategies to select the best sampling nodes:
  • MaxSigMin: Maximizes the smallest singular value to ensure stability.
  • MinTrac: Minimizes the total error energy.
  • MinPinv: Minimizes the Frobenius norm of the recovery operator.
  • MaxSig & MaxVol: Focus on maximizing signal energy and volume in the sampled space.
  • Localized Filtering: To make the method practical for large-scale graphs, they introduce a localized fractional filtering operator. This avoids the need for expensive global calculations (like full eigendecomposition) during the reconstruction process.

Datasets

The researchers validated their framework using three distinct types of data:

  1. U.S. Climate Data: Seasonal temperature, precipitation, and sunshine duration across 48 contiguous U.S. states.
  2. Dog Walking Dynamic Mesh: A dataset representing a moving 3D mesh, used to test how the algorithms scale as the number of graph nodes increases (from 40 to 180 nodes).
  3. Sea Clutter Dataset: Real-world complex-valued radar signals from a spaceborne system, used to test the impact of varying the fractional parameters $(\alpha, \beta)$ on non-stationary data.

Key Insights and Ideas

  • The "Sweet Spot" of Fractional Orders: The most important finding is that the JFRFT isn't just "more math"—it's a better lens. By adjusting $\alpha$ and $\beta$, the authors showed that a signal that looks complex in the standard Fourier domain might become "bandlimited" (simpler) in a fractional domain, allowing for much more accurate reconstruction from fewer samples.
  • Localization Bridges Theory and Practice: The introduction of the localized filtering operator is a major win for efficiency. It allows the sampling strategy to be expressed in terms of local graph structures, which is essential for large-scale networks where global operations are too slow.
  • Greedy is Good: The study confirms that greedy selection strategies significantly outperform uniform random sampling, particularly when the number of available samples is low.

Key Results

  • High Accuracy: In the sunshine duration experiment (192 joint nodes), the MaxSigMin method achieved a remarkably low Normalized Mean Squared Error (NMSE) of $1.61 \times 10^{-6}$ using only 20 samples.
  • Efficiency Trade-offs: The MinPinv method emerged as the "best all-rounder," providing the best balance between low reconstruction error and fast computational runtime as the graph size grew.
  • Parameter Sensitivity: Using the sea clutter data, the authors found a clear optimal point at $(\alpha, \beta) = (1.9, 0.7)$. At this specific "angle," the reconstruction error was minimized, proving that the fractional parameters are critical for real-world, non-stationary signals.

Limitations and Future Work

  • Parameter Tuning: Currently, finding the optimal $\alpha$ and $\beta$ requires a two-stage search (coarse then fine). Future work could focus on automated or adaptive methods to "learn" these parameters directly from the data.
  • Scalability to Massive Graphs: While localization helps, the paper's experiments topped out at 180 nodes. Applying this to million-node social networks would likely require further optimizations in how the localized operators are implemented.
  • Noise Robustness: While the methods were tested with Gaussian noise, exploring how they handle "graph-specific" noise (like missing edges or structural perturbations) remains an open question.

Summary updated

Abstract

With the growing demand for non-Euclidean data analysis, graph signal processing (GSP) has gained significant attention for its capability to handle complex time-varying data. This paper introduces a novel sampling method based on the joint time-vertex fractional Fourier transform (JFRFT), enhancing signal representation in time-frequency analysis and GSP. The JFRFT sampling theory is established by deriving conditions for the perfect recovery of jointly bandlimited signals, along with an optimal sampling set selection strategy. To further enhance the efficiency of large-scale time-vertex signal processing, the design of localized sampling operators is investigated. Numerical simulations and real data experiments validate the superior performance of the proposed methods in terms of recovery accuracy and computational efficiency, offering new insights into efficient time-varying signal processing.
BibTeX
@inproceedings{zhang2025sampling,
  author = {Yu Zhang and Bing‐Zhao Li},
  title = {{Sampling of graph signals based on joint time-vertex fractional Fourier transform}},
  booktitle = {Signal},
  year = {2025},
  doi = {10.1016/j.sigpro.2025.110309},
}

Loading related content...

Figure