Efficient Graph Field Integrators Meet Point Clouds

We present two new classes of algorithms for efficient field integration on graphs encoding point cloud data. The first class, $\mathrm{SeparatorFactorization}$ (SF), leverages the bounded genus of point cloud mesh graphs, while the second class, $\mathrm{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 (in particular for mesh-dynamics modeling) as well as Wasserstein distance computations for point clouds, including the Gromov-Wasserstein variant.

Authors

• Krzysztof Choromanski
• Arijit Sehanobish
• Han Lin
• Yunfan Zhao
• Eli Berger
• Tetiana Parshakova
• Alvin Pan
• David Watkins
• Tianyi Zhang
• Valerii Likhosherstov
• Somnath Basu Roy Chowdhury
• Avinava Dubey
• Deepali Jain
• Tamás Sarlós
• Snigdha Chaturvedi
• Adrian Weller

Keywords

No keywords are indexed for this paper.