Message-Passing Monte Carlo: Generating low-discrepancy point sets via graph neural networks

Rusch, TK; Kirk, N; Bronstein, MM; Lemieux, C; Rus, D

AI Collection

Journal article

Message-Passing Monte Carlo: Generating low-discrepancy point sets via graph neural networks

Abstract:: Discrepancy is a well-known measure for the irregularity of the distribution of a point set. Point sets with small discrepancy are called low-discrepancy and are known to efficiently fill the space in a uniform manner. Low-discrepancy points play a central role in many problems in science and engineering, including numerical integration, computer vision, machine perception, computer graphics, machine learning, and simulation. In this work, we present the first machine learning approach to generate a new class of low-discrepancy point sets named Message-Passing Monte Carlo (MPMC) points. Motivated by the geometric nature of generating low-discrepancy point sets, we leverage tools from Geometric Deep Learning and base our model on Graph Neural Networks. We further provide an extension of our framework to higher dimensions, which flexibly allows the generation of custom-made points that emphasize the uniformity in specific dimensions that are primarily important for the particular problem at hand. Finally, we demonstrate that our proposed model achieves state-of-the-art performance superior to previous methods by a significant margin. In fact, MPMC points are empirically shown to be either optimal or near-optimal with respect to the discrepancy for low dimension and small number of points, i.e., for which the optimal discrepancy can be determined. Code for generating MPMC points can be found at https://github.com/tk-rusch/MPMC.Published in Proceedings of the National Academy of Sciences (PNAS): https://www.pnas.org/doi/10.1073/pnas.240991312

Publication status:: Published

Peer review status:: Peer reviewed

Actions

Email

Email this record

Send the bibliographic details of this record to your email address.

Your Email
Please enter the email address that the record information will be sent to.

-
Your message (optional)
Please add any additional information to be included within the email.
Share
Cite

Cite this record

APA Style

Rusch, T. K., Kirk, N., Bronstein, M. M., Lemieux, C., & Rus, D. (2024). Message-Passing Monte Carlo: Generating low-discrepancy point sets via graph neural networks. Proceedings of the National Academy of Sciences, 121(40), e2409913121–e2409913121.

MLA Style

Rusch, TK, et al. “Message-Passing Monte Carlo: Generating Low-Discrepancy Point Sets via Graph Neural Networks.” Proceedings of the National Academy of Sciences, vol. 121, no. 40, 2024, pp. e2409913121–e2409913121.

Chicago Style

Rusch, TK, N Kirk, MM Bronstein, C Lemieux, and D Rus. 2024. “Message-Passing Monte Carlo: Generating Low-Discrepancy Point Sets via Graph Neural Networks.” Proceedings of the National Academy of Sciences 121 (40): e2409913121–e2409913121.
Print