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
Proceedings of the 40th International Conference on Machine Learning, PMLR 202:5978-6004, 2023.

Abstract

We present two new classes of algorithms for efficient field integration on graphs encoding point cloud data. The first class, SeparatorFactorization (SF), leverages the bounded genus of point cloud mesh graphs, while the second class, RFDiffusion (RFD), uses popular ϵ-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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v202-choromanski23b, 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 = {Proceedings of the 40th International Conference on Machine Learning}, pages = {5978--6004}, year = {2023}, editor = {Krause, Andreas and Brunskill, Emma and Cho, Kyunghyun and Engelhardt, Barbara and Sabato, Sivan and Scarlett, Jonathan}, volume = {202}, series = {Proceedings of Machine Learning Research}, month = {23--29 Jul}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v202/choromanski23b/choromanski23b.pdf}, url = {https://proceedings.mlr.press/v202/choromanski23b.html}, 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.} }
Endnote
%0 Conference Paper %T Efficient Graph Field Integrators Meet Point Clouds %A Krzysztof Marcin Choromanski %A Arijit Sehanobish %A Han Lin %A Yunfan Zhao %A Eli Berger %A Tetiana Parshakova %A Alvin Pan %A David Watkins %A Tianyi Zhang %A Valerii Likhosherstov %A Somnath Basu Roy Chowdhury %A Kumar Avinava Dubey %A Deepali Jain %A Tamas Sarlos %A Snigdha Chaturvedi %A Adrian Weller %B Proceedings of the 40th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2023 %E Andreas Krause %E Emma Brunskill %E Kyunghyun Cho %E Barbara Engelhardt %E Sivan Sabato %E Jonathan Scarlett %F pmlr-v202-choromanski23b %I PMLR %P 5978--6004 %U https://proceedings.mlr.press/v202/choromanski23b.html %V 202 %X 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.
APA
Choromanski, K.M., Sehanobish, A., Lin, H., Zhao, Y., Berger, E., Parshakova, T., Pan, A., Watkins, D., Zhang, T., Likhosherstov, V., Basu Roy Chowdhury, S., Dubey, K.A., Jain, D., Sarlos, T., Chaturvedi, S. & Weller, A.. (2023). Efficient Graph Field Integrators Meet Point Clouds. Proceedings of the 40th International Conference on Machine Learning, in Proceedings of Machine Learning Research 202:5978-6004 Available from https://proceedings.mlr.press/v202/choromanski23b.html.

Related Material