Numerical integration on graphs: Where to sample and how to weigh

Abstract:

Let $G=(V,E,w)$ be a finite, connected graph with weighted edges. We are interested in the problem of finding a subset $W \subset V$ of vertices and weights $a_w$ such that \begin{equation*} \frac {1}{|V|}\sum _{v \in V}^{}{f(v)} \sim \sum _{w \in W}{a_w f(w)} \end{equation*} for functions $f:V \rightarrow \mathbb {R}$ that are “smooth” with respect to the geometry of the graph; here $\sim$ indicates that we want the right-hand side to be as close to the left-hand side as possible. The main application comprises problems where $f$ is known to vary smoothly over the underlying graph but is expensive to evaluate on even a single vertex. We prove an inequality showing that the integration problem can be rewritten as a geometric problem (“the optimal packing of heat balls”). We discuss how one would construct approximate solutions of the heat ball packing problem; numerical examples demonstrate the efficiency of the method.