SVD-Based UGRM-GFT on Directed Product Graphs

Technical Summary: SVD-Based UGRM-GFT on Directed Product Graphs

Problem Statement
Traditional Graph Signal Processing (GSP) on directed graphs relies heavily on fixed representation matrices, such as the Laplacian or adjacency matrices. These rigid structures limit a model's ability to adapt to complex and varying graph topologies, particularly in directed contexts where edge directionality signifies asymmetric relationships (e.g., information flow or causal dependencies). Furthermore, existing Graph Fourier Transform (GFT) methods often suffer from numerical instability (e.g., Jordan decomposition) or high computational complexity. Additionally, spatiotemporal signals modeled on product graphs often fail to capture correlation attributes across dimensions when restricted to singular directed graphs. While recent SVD-based approaches have addressed stability, they typically remain tied to static operators that lack the flexibility to accommodate structural changes in graph data.

Methodology
To address these limitations, the authors propose a Generalized Graph Fourier Transform (UGRM-GFT) based on Singular Value Decomposition (SVD) and the Unified Graph Representation Matrix (UGRM).

1. Unified Graph Representation Matrix (UGRM): The method utilizes a parameterized matrix $P_{\alpha,k} = \alpha D + (2k - 1)(\alpha - 1)A$, where $D$ is the in-degree matrix, $A$ is the adjacency matrix, and $\alpha, k \in [0, 1]$ are tunable parameters. This formulation allows the matrix to adaptively degenerate into classical representations (Laplacian, adjacency, degree, or signless Laplacian) depending on the parameter values.
2. SVD-Based Transform: Instead of eigen-decomposition, the authors apply SVD to the UGRM. This yields left and right singular vectors ($U_{\alpha,k}$ and $V_{\alpha,k}$) and singular values ($\Sigma_{\alpha,k}$). The transform is defined using both sets of vectors to ensure numerical stability and perfect reconstruction.
3. Spectral Ordering: The paper establishes a parameter-dependent spectral ordering. If the parameter $\beta = (2k-1)(\alpha-1)$ is negative, the operator behaves like a Laplacian (difference-like), and singular values are ordered non-decreasingly (smaller values = lower frequency/smoothness). If $\beta \geq 0$, the operator is adjacency-like (propagation-oriented), and singular values are ordered non-increasingly (larger values = higher energy).
4. Two Variants for Directed Cartesian Product Graphs:
   • UGRM-GFT-I: Performs SVD directly on the composite UGRM of the product graph ($P_{\alpha,k}^{\boxtimes}$). This is suitable for globally coupled signals but has a computational complexity of $O(N^3)$ where $N = N_1 N_2$.
   • UGRM-GFT-II: Applies SVD separately to the UGRMs of the factor graphs ($P_{\alpha,k}^1$ and $P_{\alpha,k}^2$) and recombines them via Kronecker products. This approach reduces computational complexity from $O(N_1^3 N_2^3)$ to $O(N_1^3 + N_2^3)$ while preserving spectral expressiveness.

Key Contributions

• Framework Development: The proposal of an SVD-based UGRM-GFT that unifies traditional graph matrices into a flexible, parameterized framework compatible with general directed graphs.
• Algorithmic Efficiency: The introduction of UGRM-GFT-II, which significantly reduces computational complexity for directed Cartesian product graphs without sacrificing spectral performance.
• Theoretical Analysis: The establishment of approximation error bounds for the proposed method. The authors characterize the spectral behavior relative to parameters $\alpha$ and $k$, proving that the method achieves tighter spectral concentration by aligning the operator with the signal's intrinsic correlation structure.
• Closed-Form Solutions: Derivation of explicit closed-form expressions for both forward and inverse transformations, facilitating practical applications like denoising.

Experimental Results
The authors evaluated the method on three real-world datasets: Sea Surface Temperature (SST), PM-2.5 concentrations, and COVID-19 confirmed cases. These datasets were modeled as signals on directed Cartesian product graphs.

• Denoising Performance: In denoising tasks across varying noise levels ($\sigma \in \{0.1, 0.2, 0.3, 0.4\}$) and graph connectivities (3-NN, 5-NN, 7-NN), UGRM-GFT consistently outperformed traditional fixed-matrix approaches (Lap-GFT, Adj-GFT, Id-GFT, SLap-GFT).
• Metrics: The proposed methods achieved higher Signal-to-Noise Ratios (SNR) and lower Bandlimiting Approximation Errors (BAE). For instance, on the SST dataset, UGRM-GFT-II achieved an SNR of 9.5254 dB compared to 9.2665 dB for Lap-GFT-II.
• Energy Compaction: The UGRM-GFTs demonstrated superior energy compaction. On the SST dataset, the leading 40 spectral components (10% of the spectrum) captured 95.91% of the total signal energy, significantly outperforming fixed-matrix baselines (e.g., Adj-GFT captured only ~22-31%).
• Parameter Adaptation: Bayesian optimization identified optimal parameters $(\alpha^*, k^*)$ that varied by dataset. Smooth geophysical signals (SST, PM-2.5) favored Laplacian-dominated regimes ($\beta < 0$), while the propagation-based COVID dataset favored a regime closer to the boundary ($\beta \approx -0.04$), validating the method's adaptability.
• Efficiency: UGRM-GFT-II reduced the parameter optimization runtime by approximately 22.7% compared to UGRM-GFT-I on a $20 \times 20$ product graph.

Significance and Claims
The paper claims that the proposed UGRM-GFT addresses the rigidity of traditional GSP by introducing a parameterized representation that adapts to the specific correlation structures of graph signals. By leveraging SVD, the method ensures numerical stability while the UGRM framework allows for a continuous interpolation between degree and Laplacian information. The authors assert that this flexibility leads to superior energy compaction and denoising performance across diverse signal types, from smooth geophysical fields to irregular epidemic propagation patterns. The work provides a theoretical foundation for spectral ordering based on operator parameters and demonstrates practical utility through extensive experiments on real-world data.