Does there exist a notion of discrete riemannian metric on graph? I would like to know if there is any notion of a discrete Riemannian metric on graphs. C. Mercat has worked on discrete Riemann Surfaces, but that's not exactly what I am working on.
To be more precise, when one defines a weighted Laplacian $\Delta : \mathbb{R}^V \mapsto \mathbb{R}^V $ on a graph $G=(V,E)$ by
$$
\forall v \in V, \quad \delta (f)(v)=\sum_{w \sim v} a_{\{v,w\}} \big( f(v)-f(w) \big),$$
the family  $ \big( a_{e} \big)_{e \in E}$ of reals indexed by the set of edges can be viewed as a metric on the graph. But the analogy with the case of riemannian metric on manifolds is not so obvious. For instance, what would mean that two such metrics $ \big( a_{e} \big)_{e \in E}$ and $ \big( b_{e} \big)_{e \in E}$ are conformal ?
Thanks in advance,
LC.
 A: There is a very rich theory of discrete conformal equivalence on surface triangulations  stemming from the following definition (attributed to Luo by the references below though see earlier work of Cooper and Rivin and see the comments for more discussion). Let $l,\tilde{l}$ be two metrics on the triangulation $T=(V,E)$, i.e. $l,\tilde{l}\in(\mathbb{R}_{>0})^E$. Then $l$ and $\tilde{l}$ are discretely conformally equivalent if:
$$\tilde{l}_{ij}=e^{(u_i+u_j)/2}l_{ij}$$
for some $u\in\mathbb{R}^V$.  Compare this to the situation for two metrics $g,\tilde{g}$ on a smooth manifold $M$ which are called conformally equivalent if:
$$\tilde{g}=e^{2u}g$$
for some $u\in C^\infty(M)$.
See this paper of Bobenko, Pinkall and Springborn for a variational formulation (making this notion very "practical"; see the computer graphics papers in its references (e.g. the paper of Springborn, Schröder and Pinkall and others citing these works) and connections to circle packing, hyperbolic geometry and much more.  Here's just one of the many attractive images in their paper; this one depicts a discrete conformal map between two metrics on a triangulation of a rectangle:

Note however that the natural Laplace-Beltrami operator in this setting is not the one you've written but rather the "cotangent Laplacian"; see the abovementioned paper of Springborn, Schröder and Pinkall.
I haven't looked into work on this away from the triangulation case, but I'd be very interested in it if it's out there.
A: This circle of questions is studied in this old paper by D. Jakobson and I. Rivin.
A: One can even approximate the metric on a graph by Riemannian metrics on a 2-dim compact manifold. Namely, embed the graph into a Riemann surface, and choose a Riemann metric which gives the edge distance along the edges, and which is very small everywhere else. Then the eigenvalues of the surface Laplacian approximate the eigenvalues of the graph Laplacian. See many papers of Colin de Verdiere who used this method with great success.
