  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.
