4.16 Functions on Graphs

Traditional Riemannian manifolds are full of structure that our hypergraphs do not have. Nevertheless, we are beginning to see that there are analogs of many ideas from geometry and calculus on manifolds that can be applied to our hypergraphs—at least in some appropriate limit as they become sufficiently large.

To continue the analogy, consider trying to define a function on a hypergraph. For a scalar function, we might just assign a value to each node of the hypergraph. And if we want the function to be somehow smooth, we should make sure that nearby nodes are assigned similar values.

But what about a vector function? An obvious approach is just to assign values to each directed edge of the hypergraph. And given this, we can find the component in a direction corresponding to a particular geodesic just by averaging over all edges of the hypergraph along that geodesic. (To recover results for continuous spaces, we must take all sorts of potentially intricate limits.)

(At a slightly more formal mathematical level, to define vectors in our system, we need some analog of a tangent space. On manifolds, the tangent space at a point can be defined in terms of the equivalence class of geodesics passing through that point. In our systems, the obvious analog is to look at the edges around a point, which are exactly what any geodesic through that point must traverse.)

For a rank-p tensor function, we can assign values to p edges associated either with a single node, or with a neighborhood of nearby nodes. And, once again, we can compute “projections” of the tensor in particular “directions” by averaging values along p geodesics.

The gradient of a scalar function ∇f at a particular point X can be defined by starting at X and seeing along what geodesic the (suitably averaged) values decrease fastest, and at what rate. The results of this can then be assigned to the edges along the geodesic so as to specify a vector function.

The divergence of a vector function can be defined by looking at a ball in the hypergraph, and asking for the total of the values of the function on all hyperedges in the ball. The analog of Gauss’s theorem then becomes a fairly straightforward “continuity equation” statement about sums of values on edges inside and at the surface of part of a hypergraph.