  Graphs are a central tool in machine learning and information processing as
they allow to conveniently capture the structure of complex datasets. In this
context, it is of high importance to develop flexible models of signals defined
over graphs or networks. In this paper, we generalize the traditional concept
of wide sense stationarity to signals defined over the vertices of arbitrary
weighted undirected graphs. We show that stationarity is expressed through the
graph localization operator reminiscent of translation. We prove that
stationary graph signals are characterized by a well-defined Power Spectral
Density that can be efficiently estimated even for large graphs. We leverage
this new concept to derive Wiener-type estimation procedures of noisy and
partially observed signals and illustrate the performance of this new model for
denoising and regression.
