Graphs are a discrete topological canvas that in many applications can completely replace a continuous manifold. Nevertheless, invariance of dynamics defined on graphs under changes of reference frames is typically attempted by embedding the graph in an ambient manifold. This seems superfluous as node names already label points similarly to a choice of coordinates in continuous space. As node names are fiducial, graph renamings can be seen as a change of coordinates on the graph. Thus, graph renamings correspond to a natively discrete analogue of diffeomorphisms. In quantum theory, node names become even more important. We first provide a robust notion of quantum superpositions of graphs and argue with a simple example that in quantum theory in order to avoid instantaneous signalling it is necessary to use node names to define the â localisationâ of a node, rather than values of a physical field. We propose renaming invariance as a symmetry principle of similar weight to diffeomorphism invariance and show how to impose it at the level of quantum superpositions of graphs.