2017/09/12 by Bastien Pasdeloup, Pasdeloup, Bastien, Vincent Gripon +7
Computer Science · Physics and Astronomy · #Advanced Graph Neural Networks #Combinatorics (math.CO) #Complex Network Analysis Techniques #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Topological and Geometric Data Analysis
paper · pdf · doi:10.48550/arxiv.1709.03859
openalex publication_date 2017/09/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.