Graph Signal Processing over a Probability Space of Shift Operators

Abstract

Graph signal processing (GSP) uses a shift operator to define a Fourier basis for the set of graph signals. The shift operator is often chosen to capture the graph topology. However, in many applications, the graph topology may be unknown a priori, its structure uncertain, or generated randomly from a predefined set for each observation. Each graph topology gives rise to a different shift operator. In this paper, we develop a GSP framework over a probability space of shift operators. We develop the corresponding notions of Fourier transform, MFC filters, and band-pass filters, which subsumes classical GSP theory as the special case where the probability space consists of a single shift operator. We show that an MFC filter under this framework is the expectation of random convolution filters in classical GSP, while the notion of bandlimitedness requires additional wiggle room from being simply a fixed point of a band-pass filter. We develop a mechanism that facilitates mapping from one space of shift operators to another, which allows our framework to be applied to a rich set of scenarios. We demonstrate how the theory can be applied by using both synthetic and real datasets.

References in corpus (19)

• Semi-Supervised Classification with Graph Convolutional Networks
• The Emerging Field of Signal Processing on Graphs: Extending High-Dimensional Data Analysis to Networks and Other Irregular Domains
• Discrete Signal Processing on Graphs
• Discrete Signal Processing on Graphs: Sampling Theory
• Learning graphs from data: A signal representation perspective
• Connecting the Dots: Identifying Network Structure via Graph Signal Processing
• Efficient Sampling Set Selection for Bandlimited Graph Signals Using Graph Spectral Proxies
• Signals on Graphs: Uncertainty Principle and Sampling
• Sampling of graph signals with successive local aggregations
• Identifying Infection Sources and Regions in Large Networks
• Signal Processing on Graphs: Causal Modeling of Unstructured Data
• A Spectral Graph Uncertainty Principle
• How to Identify an Infection Source with Limited Observations
• Irregularity-Aware Graph Fourier Transforms
• A Primer on PAC-Bayesian Learning
• A Hilbert Space Theory of Generalized Graph Signal Processing
• On the Properties of Gromov Matrices and their Applications in Network Inference
• Bayesian Graph Convolutional Neural Networks Using Non-Parametric Graph Learning
• Signal processing on simplicial complexes