# Numerical Integration on Graphs: where to sample and how to weigh

arXiv: https://arxiv.org/abs/1803.06989 · HTML: https://mlsanity.com/paper/1803.06989/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Mar 2018.

## Built on by (most cited first, 1 of 1)

- [Spectral Greedy Coresets for Graph Neural Networks](https://mlsanity.com/paper/2405.17404/) (2024)

## Abstract (arXiv)

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 aw such that  frac1|V|sumv ∈ Vf(v) ~ sumw ∈ Waw f(w) for functions f:V rightarrow ℝ 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.