Well, phenomena analogous to what is described by quantum mechanics, for example, have been found in physics of solids (e.g. phonons). Shouldn't be surprising,

Well, phenomena analogous to what is described by quantum mechanics, for example, have been found in physics of solids (e.g. phonons). Shouldn't be surprising, then, that such a universal and rather abstract structure as a graph (especially if you allow to 'update' it) can be made to reflect some aspects of physical reality. Computations are computations, whichever way you approach them. Classical electrodynamics, too, has several equivalent formulations (with the tensorial notation being pretty "graphical" IMHO), and some people do like to create a fuss around particular ones, but that ain't nothing we haven't seen before. What is important, though, is to always make a distinction between a model and the real thing: it wouldn't make sense to say that spacetime is some kind of a graph. (Or would it?)