  In this paper, we introduce translation operators on graphs. Contrary to
spectrally-defined translations in the framework of graph signal processing,
our operators mimic neighborhood-preserving properties of translation operators
defined in Euclidean spaces directly in the vertex domain, and therefore do not
deform a signal as it is translated. We show that in the case of grid graphs
built on top of a metric space, these operators exactly match underlying
Euclidean translations, suggesting that they completely leverage the underlying
metric. More generally, these translations are defined on any graph, and can
therefore be used to process signals on those graphs. We show that identifying
proposed translations is in general an NP-Complete problem. To cope with this
issue, we introduce relaxed versions of these operators, and illustrate
translation of signals on random graphs.
