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?