We study two notions that refers to asymmetric graphs, which we view as graphs having a unique ordering that can be reconstructed by looking at an unlabeled version of the graph. We consider the relation between these two notions in two regimes: The bounded-degree graph regime, where oracle access to a graph means oracle access to its incidence function, and the dense graph regime, where oracle access to the graph means access to its adjacency predicate. We show that, in the bounded-degree regime, robustly self-ordering and local self-ordering are almost orthogonal; that is, even extremely strong versions of one notion do not imply very weak versions of the other notion. Specifically, we present very efficient local self-ordering procedures for graphs that possess permutations that displace all but one vertex while preserving all but a pair of edges. On the other hand, we prove the existence of robustly self-ordered n-vertex graphs having no local self-ordering procedures even when allowing query complexity \(o({\sqrt{n}})\) . In the dense graph regime, local self-ordering procedures are shown to yield a quantitatively weaker version of the robust self-ordering condition, in which the said proportion is off by a factor that is related to the query complexity of the local self-ordering procedure. Furthermore, we show that this quantitatively loss is inherent. On the other hand, we show how to transform any robustly self-ordered graph into one having a local self-ordering procedure, while preserving the robustness condition. Combined with prior work, this yields explicit constructions of graphs that are both robustly and locally self-ordered, and an application to property testing.