Efficient Graph Field Integrators Meet Point Clouds

Krzysztof Marcin Choromanski, Arijit Sehanobish, Han Lin, Yunfan Zhao, Eli Berger, Tetiana Parshakova, Alvin Pan, David Watkins, Tianyi Zhang, Valerii Likhosherstov, Somnath Basu Roy Chowdhury, Kumar Avinava Dubey, Deepali Jain, Tamas Sarlos, Snigdha Chaturvedi, Adrian Weller

ICML 2023 pp. 5978-6004

/icml/2023/choromanski2023icml-efficient/

Abstract

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.

PDF ICML OpenReview Semantic Scholar

Cite

Text

Choromanski et al. "Efficient Graph Field Integrators Meet Point Clouds." International Conference on Machine Learning, 2023.

Markdown

[Choromanski et al. "Efficient Graph Field Integrators Meet Point Clouds." International Conference on Machine Learning, 2023.](https://mlanthology.org/icml/2023/choromanski2023icml-efficient/)

BibTeX

@inproceedings{choromanski2023icml-efficient,
  title     = {{Efficient Graph Field Integrators Meet Point Clouds}},
  author    = {Choromanski, Krzysztof Marcin and Sehanobish, Arijit and Lin, Han and Zhao, Yunfan and Berger, Eli and Parshakova, Tetiana and Pan, Alvin and Watkins, David and Zhang, Tianyi and Likhosherstov, Valerii and Basu Roy Chowdhury, Somnath and Dubey, Kumar Avinava and Jain, Deepali and Sarlos, Tamas and Chaturvedi, Snigdha and Weller, Adrian},
  booktitle = {International Conference on Machine Learning},
  year      = {2023},
  pages     = {5978-6004},
  volume    = {202},
  url       = {https://mlanthology.org/icml/2023/choromanski2023icml-efficient/}
}