  We present two new classes of algorithms for efficient field integration on
graphs encoding point clouds. The first class, SeparatorFactorization(SF),
leverages the bounded genus of point cloud mesh graphs, while the second class,
RFDiffusion(RFD), uses popular epsilon-nearest-neighbor graph representations
for point clouds. Both can be viewed as providing the functionality of Fast
Multipole Methods (FMMs), which have had a tremendous impact on efficient
integration, but for non-Euclidean spaces. We focus on geometries induced by
distributions of walk lengths between points (e.g., shortest-path distance). We
provide an extensive theoretical analysis of our algorithms, obtaining new
results in structural graph theory as a byproduct. We also perform exhaustive
empirical evaluation, including on-surface interpolation for rigid and
deformable objects (particularly for mesh-dynamics modeling), Wasserstein
distance computations for point clouds, and the Gromov-Wasserstein variant.

Machine Learning