We consider edge-labeled graphs which model distributed systems. Properties of the labeling can be used in the design of efficient protocols; for example, sense of direction is known to have a strong impact on the communication complexity of many distributed problems. We investigate the relation between symmetries and topology in labeled graphs. In particular, we characterize the classes of completely symmetric and completely surrounding symmetric labeled graphs; we show that the former is a proper subset of the class of regular graphs, while the latter coincides with the class of Cayley graphs. We then focus on the relationship between symmetries and sense of direction in regular graphs. For these graphs, we show an interesting link between minimal sense of direction and Cayley graphs. Namely, we prove that a regular graph has a minimal symmetrical sense of direction iff it is a Cayley graph. We also discuss the relationship between minimal sense of direction and group-based labelings.