⚡ electrical engineering

Graph Distribution-valued Signals in Wasserstein Spaces: Theory and Applications

This paper introduces a novel framework for graph signal processing that represents signals as probability measures in Wasserstein spaces, thereby generalizing classical vector-based approaches to handle incomplete observations, signal-dependent graph structures, and inherent uncertainty while providing theoretical stability guarantees and demonstrating practical utility in tasks like filter learning and anomaly detection.

Original authors: Yanan Zhao, Feng Ji, Xingchao Jian, Wee Peng Tay

Published 2026-07-23

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Yanan Zhao, Feng Ji, Xingchao Jian, Wee Peng Tay

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to understand a massive, chaotic party where hundreds of people are talking, dancing, and shouting at once. In the world of data science, this party is called a "network" or a "graph," where every person is a "node" and every conversation is a "connection." For years, scientists have tried to analyze these parties using a method called Graph Signal Processing (GSP). Think of traditional GSP like taking a photo of the entire party at a single, perfect moment. In this photo, you know exactly what every single person is saying, and you know exactly who is standing next to whom. It's a clean, frozen snapshot.

But real life is messy. Sometimes, people are missing from the photo (maybe they stepped out for a drink), sometimes the camera shakes and blurs the connections, and sometimes the "who is talking to whom" changes depending on how loud the music is. Traditional methods struggle here because they demand a perfect, complete snapshot. If you're missing even a few people, the whole photo is useless. This paper steps into that messy reality. It asks: What if, instead of trying to take a perfect photo of one specific moment, we describe the entire vibe of the party? What if we stop looking at individual snapshots and start looking at the "cloud of possibilities" of how the party could look? This is the core idea: moving from rigid, single-point data to flexible, probability-based descriptions that can handle missing pieces and changing rules.

The authors of this paper, Yanan Zhao and colleagues, introduce a new framework called "Graph Distribution-valued Signals" (GDS). Instead of treating data as a single, fixed list of numbers (like a vector), they treat data as a "cloud" or a "distribution" of possibilities. Imagine a traditional signal as a single, sharp arrow pointing to a specific spot on a map. The new GDS approach treats that signal as a fuzzy, glowing cloud that covers a whole area, showing not just where the data is, but where it might be and how likely it is to be there. They do this using a mathematical playground called "Wasserstein space," which is essentially a way to measure the "work" needed to move one cloud of data into the shape of another.

Here is the magic trick: The authors show that their new "cloud" method is a super-powerful upgrade that includes the old "arrow" method as a special case. If your data is perfectly certain and complete, the "cloud" shrinks down to a single sharp point, and you get the old, familiar results back. But when the data is messy, missing, or changing, the cloud expands to capture that uncertainty. They also realized that the "map" of the party (the graph structure) isn't always fixed either. Sometimes, the connections between people depend on what they are saying. So, they created a "Signal-Adaptive Graph Structure," where the map itself can wiggle and change based on the data, just like how a dance floor might rearrange itself depending on the song playing.

To prove this works, the team ran some experiments. First, they tried to predict future trends in COVID-19 cases across 58 counties. In the real world, some counties forget to report their numbers on certain days. The old methods (which need a complete list of numbers for every single day) crashed and burned when data was missing or shuffled out of order. The new GDS method, however, kept working smoothly. It didn't need a perfect list; it just looked at the overall pattern of the "cloud" of data and learned how to predict the next day's numbers, even when 20% of the reports were missing.

Second, they tested the system on detecting "anomalies" or weird behavior in brain signals from epilepsy patients. They looked at the high-frequency "noise" in the brain waves. Instead of just checking if a single number was too high, the new method looked at the entire shape of the distribution of those numbers. The results showed that this cloud-based approach was much better at spotting the difference between a normal brain state and a seizure, even when they only had a small number of samples to work with.

In short, this paper suggests that by treating data as a flexible, probabilistic cloud rather than a rigid, fixed list, we can build systems that are much more robust against missing information, timing errors, and changing environments. It doesn't claim to have solved every problem in the world, but it offers a powerful new lens that makes graph signal processing work in the messy, imperfect reality of the real world, rather than just in the clean, perfect world of textbooks.

Technical Summary: Graph Distribution-valued Signals in Wasserstein Spaces

1. Problem Statement

Classical Graph Signal Processing (GSP) represents signals as vectors indexed by graph vertices, relying on linear operators like the Graph Fourier Transform (GFT) and graph filters. While effective, this vector-based framework faces three critical limitations in real-world applications:

Assumption of Complete Observations: Classical GSP requires synchronous, complete data across all nodes to apply operators like the GFT. In practice, data collection is often asynchronous or incomplete (e.g., missing sensor reports), rendering standard vector-based methods inapplicable or requiring biased imputation.
Requirement for Strict Signal Correspondence: Statistical GSP methods typically learn filters from paired input-output vector samples $\{(x_i, y_i)\}$ . This imposes a rigid one-to-one temporal correspondence. Real-world data often suffers from temporal shifts, overlaps, or shuffling, breaking this alignment.
Assumption of Deterministic Topology: Classical GSP assumes a fixed, known graph topology (e.g., a specific adjacency matrix). However, in many systems, the graph structure is uncertain, partially observed, or inherently dependent on the signal realization itself.

Existing statistical GSP approaches often treat randomness via random variables but still operate on vector samples, failing to fully address these structural and observational uncertainties.

2. Methodology

The authors propose a unified framework where graph signals are modeled not as vectors, but as Graph Distribution-valued Signals (GDSs)—probability measures residing in a Wasserstein space ( $\mathcal{P}_p(\mathbb{R}^N)$ ).

Core Concepts

Graph Distribution-valued Signal (GDS): A signal is defined as a Borel probability measure $\mu \in \mathcal{P}_p(\mathbb{R}^N)$ . Traditional vector signals $x$ are recovered as special cases where $\mu = \delta_x$ (Dirac delta measure).
Signal-Adaptive Graph Structures (SAGS): The framework generalizes fixed graph topologies by modeling the graph $G$ as a random variable conditioned on the signal $x$ . Formally, for a signal $x$ , the graph structure follows a conditional distribution $\nu_x$ . This captures signal-dependent connectivity patterns.
Wasserstein Distance: The framework utilizes the $p$ -Wasserstein distance ( $W_p$ ) to measure discrepancies between signal distributions, providing a metric that accounts for both mean shifts and covariance/structural changes.

Generalized Operations

The paper establishes a systematic dictionary mapping classical GSP concepts to their GDS analogs via pushforward measures:

GDS Fourier Transform (GDS-FT): Defined as the pushforward of the signal distribution $\mu$ through the graph Fourier basis matrix $U_G^\top$ . For a joint distribution of signal and graph, the transform accounts for the uncertainty in the graph topology.
GDS Convolutional Filter: A filter $F_G$ (typically a polynomial of the Graph Shift Operator) acts on the distribution $\mu$ via the pushforward map $(F_G)_*\mu$ . This operation transforms the distribution in the vertex domain to the spectral domain, reshapes it, and transforms it back.
Generalized Transforms: The framework defines generalized transforms for SAGS settings, where the output distribution is derived from the joint distribution of the signal and the signal-dependent graph.

Theoretical Guarantees

The authors establish analytic properties for these generalized transforms:

Continuity: The transforms are shown to be uniformly continuous on compact signal domains and pointwise continuous under Lipschitz conditions on the induced transform distribution.
Stability: These continuity results guarantee that small perturbations in the input distribution (due to noise, distribution shifts, or finite-sample approximation) lead to controlled perturbations in the output, ensuring robustness for learning and inference.

Application Algorithms

Two specific applications are developed to demonstrate the framework:

Graph Filter Learning: The goal is to learn a filter $F_G$ $F_{G}$ that transports an input distribution $\mu_\theta$ $μ_{θ}$ to a target distribution $\mu^\star$ $μ^{⋆}$ . The authors propose two parametric approaches:
- Copula-based: Models the joint distribution by coupling marginals via a Gaussian copula, allowing for flexible dependency modeling even with missing data.
- GMM-based: Represents the joint distribution as a Gaussian Mixture Model (GMM), utilizing the Mixture-Wasserstein distance ( $MW_2$ ) for tractable optimization.
Anomaly Detection: Instead of thresholding scalar statistics (like maximum high-frequency coefficients), the method characterizes the empirical distribution of high-frequency spectral features. Anomalies are detected by measuring the discrepancy (e.g., via $MW_2$ or peak location distance) between a test batch's distribution and a reference distribution estimated from normal data.

3. Key Contributions

Unified Framework: Development of a GSP framework where signals are probability measures in Wasserstein spaces and graph topologies are signal-adaptive distributions, strictly generalizing classical vector-based GSP.
Systematic Correspondence: Formalization of a dictionary mapping core GSP operations (Fourier transform, filtering, convolution) to their distribution-level counterparts, showing classical formulations as special cases.
Stability Theory: Establishment of continuity results for generalized GDS transforms, providing theoretical stability guarantees for input perturbations and distribution approximations.
Empirical Validation: Demonstration of the framework's utility in graph filter learning and anomaly detection, showing superior performance under incomplete and misaligned observations compared to state-of-the-art vector-based methods.

4. Experimental Results

The authors validate the framework using two datasets:

COVID-19 Data (Filter Learning): Using daily case counts from 58 counties, the proposed GDS methods (GDS-Cop and GDS-GMM) were compared against Least-Squares (LS), Regularized LS, and Covariance-Matching graph filtering.
- Robustness to Missing Data: Under a 20% per-node missing rate, classical methods (GSP-LS, GSP-RLS) degraded significantly. GDS methods remained robust because they model distributions rather than requiring complete vectors.
- Robustness to Shuffling: When training data was temporally shuffled, classical methods relying on strict temporal alignment failed. GDS methods remained stable as they learn from distributional properties rather than specific sample pairings.
- Window Size: GDS methods outperformed baselines for larger time windows where sufficient samples exist for distribution estimation. However, for very small windows (2-4 days), GDS methods underperformed due to the difficulty of accurately estimating distributions from few samples.
Brain ECoG Data (Anomaly Detection): Using pre-ictal (normal) and ictal (abnormal) seizure data, the GDS-based anomaly detectors (using Peak location and Mixture Wasserstein distances) were compared against GFT-based, Total Variation (TV), and Variational Autoencoder (ELBO) baselines.
- Performance: GDS methods achieved the highest accuracy across all test batch sizes.
- Sample Efficiency: GDS methods maintained high accuracy even with small batch sizes, whereas point-wise baselines (GSP-GFT) plateaued at low accuracy, and others (GSP-TV, ELBO) required significantly more samples to approach GDS performance.

5. Significance and Claims

The paper claims that the GDS framework offers a principled approach to handling uncertainty and stochasticity in both graph signals and topologies. By shifting from vector spaces to Wasserstein spaces, the framework:

Relaxes Data Requirements: It eliminates the need for complete, synchronous observations and strict temporal alignment, making it suitable for real-world scenarios with missing or irregular data.
Captures Richer Structure: It encodes uncertainty in graph topology and signal correlations directly into the signal representation, rather than treating them as noise or requiring fixed assumptions.
Generalizes Existing Theory: It strictly encompasses classical GSP as a special case (Dirac measures), ensuring backward compatibility while extending capabilities.

The authors note that this flexibility comes with a trade-off: the framework requires sufficient data to accurately estimate underlying distributions. In low-sample regimes, classical vector-based methods may remain preferable. However, for applications involving substantial missingness, sampling variability, or signal-dependent structures, the GDS framework provides a more flexible and robust alternative.