I think this problem has been mentioned several times now, so maybe a more detailed elaboration would be nice.

I honestly don't see how you can define any meaningful embedding in a space like, say, $\mathbb{Z}^{1,3}$. For one thing, any finite graph can always be (even polygonally if you want) embedded in an infinite number of different ways into $\mathbb{R}^3$ (that is, without any crossings between vertices). Adding a temporal dimension to this space would inevitably add even more ambiguity.

By the way, let's say we have a graph and choose a certain embedding into $\mathbb{Z}^{1,3}$ by assigning four coordinates to each vertex $(t,\vec{x})$. It is always possible to obtain a new embedding by the transformation (which is just one simple example of many): $$(t,\vec{x})\mapsto (t,\lambda \vec{x})\qquad \lambda \neq 0$$

This could easily turn space-like distances between vertices into time-like distances, deeming these terms useless. Am I wrong here?