Numerical Integration on Graphs: where to sample and how to weigh
This work addresses the challenge of efficiently evaluating expensive functions on graphs, which is incremental as it builds on existing integration methods by introducing a geometric reinterpretation.
The paper tackles the problem of approximating the average of smooth functions on a graph by selecting a subset of vertices and weights, proving that this can be reformulated as a geometric heat ball packing problem and demonstrating the method's efficiency with numerical examples.
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 $$ \frac{1}{|V|}\sum_{v \in V}^{}{f(v)} \sim \sum_{w \in W}{a_w f(w)}$$ for functions $f:V \rightarrow \mathbb{R}$ that are `smooth' with respect to the geometry of the graph. The main application are problems where $f$ is known to somehow depend on 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.