Graph Distribution-valued Signals: A Wasserstein Space Perspective

1. Problem Statement

Classical Graph Signal Processing (GSP) represents signals as vectors where each entry corresponds to a node's value. While effective, this vector-based framework suffers from two critical limitations in real-world applications:

1. Assumption of Synchronous/Complete Observations: Classical GFT and filtering require a complete signal vector (all nodes observed simultaneously). In practice, data collection is often asynchronous, incomplete, or noisy across nodes.
2. Strict Correspondence Requirement: Traditional graph filters are defined as vector-to-vector mappings ($F(x_i) \approx y_i$). This enforces a rigid one-to-one alignment between source and target signals. In prediction tasks, this fails when data exhibits shifts, overlaps, periodic patterns, or missing values, as it cannot handle misalignment or inherent stochasticity.

Existing statistical GSP methods attempt to address randomness but still rely on vector-based representations and sample realizations, failing to treat the probability distribution itself as the primary signal object.

2. Methodology: The GDS Framework

The authors propose a novel framework modeling graph signals as Graph Distribution-Valued Signals (GDSs). Instead of vectors, signals are treated as probability distributions residing in the Wasserstein space ($\mathcal{P}_p(\mathbb{R}^N)$).

Core Concepts

• Signal Representation: A graph signal is a Borel probability measure $\mu$ on $\mathbb{R}^N$. Traditional vector signals $x$ are recovered as special cases where $\mu$ is a Dirac measure ($\delta_x$).
• Wasserstein Space: The space is equipped with the $p$-Wasserstein distance ($W_p$), which measures the minimal "work" to transport one distribution to another. This metric naturally captures both the mean (location) and covariance (variability/dependencies) of the signal.
• GDS Fourier Transform (GDS-FT): Defined as the pushforward measure of the distribution under the transpose of the graph shift operator's eigenvector matrix ($U_G^\top$).
  • $\hat{\mu} = (U_G^\top)_\# \mu$.
  • If $\mu = \delta_x$, this recovers the classical GFT.
• GDS Convolutional Filtering: Filtering is defined as the pushforward of the distribution under a polynomial of the graph shift operator ($F_G$).
  • $F_G(\mu) = (F_G)_\# \mu$.
  • This transforms the entire distribution, modifying not just the mean but also the covariance structure (uncertainty and inter-node dependencies).

Graph Filter Learning (GDS-Cop)

To learn filters without requiring strict sample alignment, the authors propose a Copula-based GDS filter learning approach:

1. Modeling: Local node observations are modeled as marginal distributions (e.g., Gaussians). A Gaussian Copula is used to construct a joint distribution $\mu_{\theta, \kappa}$ that captures inter-node dependencies via a correlation matrix $R$.
2. Objective: The goal is to find a filter $F_G$ and copula parameters such that the filtered source distribution matches a target distribution $\mu^\star$ in Wasserstein distance:
   $$\min_{F_G, R} W_p((F_G)_\# \mu_{\theta, \kappa}, \mu^\star)$$
3. Optimization: Assuming Gaussian distributions, the Wasserstein distance has a closed-form solution involving means and covariances. The problem is solved via alternating minimization (gradient descent) over the filter coefficients and the correlation matrix, with constraints to ensure the correlation matrix remains valid (symmetric, positive semi-definite, unit diagonal).

3. Key Contributions

1. Theoretical Framework: Introduction of the GDS framework, which strictly generalizes classical GSP by embedding vector signals into the Wasserstein space of probability measures.
2. Systematic Dictionary: Establishment of a mapping between core GSP concepts (Fourier transform, convolution, filtering) and their distribution-valued counterparts, proving that classical definitions are recovered as special cases (Dirac measures).
3. Zero-Shot/Robust Learning: Development of a filter learning paradigm that operates on distributions rather than raw samples. This allows for "zero-shot" learning if the distribution is known, or robust learning from samples without requiring synchronous or perfectly aligned data.
4. Algorithmic Implementation: Proposal of the GDS-Cop algorithm, which efficiently learns graph filters by matching distributional statistics (mean and covariance) rather than point-wise errors.

4. Experimental Results

The framework was evaluated on a COVID-19 dataset (daily cases across 58 counties in California) for time-series prediction.

• Baselines: Compared against GSP-LS (Least Squares), GSP-RLS (Regularized LS), GSP-LSCM (Covariance Matching), and GSP-LEV (Heat Kernel Mixture).
• Stress Tests:
  • Masking (Incomplete Data): Entries were randomly masked (60-90% observation). Classical methods (LS, RLS, LSCM) degraded significantly due to their reliance on complete vectors. GDS-Cop and GSP-LEV remained robust.
  • Shuffling (Misalignment): Training data within time windows was randomly permuted. Methods requiring strict temporal alignment failed, while GDS-Cop maintained stability.
• Performance: GDS-Cop consistently achieved the lowest Average Relative Squared Error (ARSE) across all window sizes. Its advantage was most pronounced in larger windows and under noisy/misaligned conditions.

5. Significance

This paper represents a paradigm shift in Graph Signal Processing:

• Handling Uncertainty: It provides a principled mathematical foundation for processing signals where uncertainty and stochasticity are intrinsic, rather than treating them as noise to be filtered out.
• Robustness to Real-World Data: By decoupling the filter learning from strict sample-to-sample correspondence, the framework is highly suitable for applications with asynchronous, incomplete, or irregularly sampled data (e.g., sensor networks, epidemiology, social dynamics).
• Theoretical Unification: It bridges the gap between deterministic signal processing and probabilistic modeling, showing that the latter is a natural generalization of the former within the geometry of the Wasserstein space.

In summary, the GDS framework transforms graph filtering from a linear algebra problem on vectors to an optimal transport problem on distributions, offering superior robustness and flexibility for complex, real-world graph-structured data.