Unsupervised Resource Allocation with Graph Neural Networks

Miles Cranmer, Peter Melchior, Brian Nord
NeurIPS 2020 Workshop on Pre-registration in Machine Learning, PMLR 148:272-284, 2021.

Abstract

We present an approach for maximizing a global utility function by learning how to allocate resources in an unsupervised way. We expect interactions between allocation targets to be important and therefore propose to learn the reward structure for near-optimal allocation policies with a GNN. By relaxing the resource constraint, we can employ gradient-based optimization in contrast to more standard evolutionary algorithms. Our algorithm is motivated by a problem in modern astronomy, where one needs to select-based on limited initial information-among $10^9$ galaxies those whose detailed measurement will lead to optimal inference of the composition of the universe. Our technique presents a way of flexibly learning an allocation strategy by only requiring forward simulators for the physics of interest and the measurement process. We anticipate that our technique will also find applications in a range of allocation problems from social science studies to customer satisfaction surveys and exploration strategies of autonomous agents.

Cite this Paper


BibTeX
@InProceedings{pmlr-v148-cranmer21a, title = {Unsupervised {{Resource Allocation}} with {{Graph Neural Networks}}}, author = {Cranmer, Miles and Melchior, Peter and Nord, Brian}, booktitle = {NeurIPS 2020 Workshop on Pre-registration in Machine Learning}, pages = {272--284}, year = {2021}, editor = {Bertinetto, Luca and Henriques, João F. and Albanie, Samuel and Paganini, Michela and Varol, Gül}, volume = {148}, series = {Proceedings of Machine Learning Research}, month = {11 Dec}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v148/cranmer21a/cranmer21a.pdf}, url = {http://proceedings.mlr.press/v148/cranmer21a.html}, abstract = {We present an approach for maximizing a global utility function by learning how to allocate resources in an unsupervised way. We expect interactions between allocation targets to be important and therefore propose to learn the reward structure for near-optimal allocation policies with a GNN. By relaxing the resource constraint, we can employ gradient-based optimization in contrast to more standard evolutionary algorithms. Our algorithm is motivated by a problem in modern astronomy, where one needs to select-based on limited initial information-among $10^9$ galaxies those whose detailed measurement will lead to optimal inference of the composition of the universe. Our technique presents a way of flexibly learning an allocation strategy by only requiring forward simulators for the physics of interest and the measurement process. We anticipate that our technique will also find applications in a range of allocation problems from social science studies to customer satisfaction surveys and exploration strategies of autonomous agents.} }
Endnote
%0 Conference Paper %T Unsupervised Resource Allocation with Graph Neural Networks %A Miles Cranmer %A Peter Melchior %A Brian Nord %B NeurIPS 2020 Workshop on Pre-registration in Machine Learning %C Proceedings of Machine Learning Research %D 2021 %E Luca Bertinetto %E João F. Henriques %E Samuel Albanie %E Michela Paganini %E Gül Varol %F pmlr-v148-cranmer21a %I PMLR %P 272--284 %U http://proceedings.mlr.press/v148/cranmer21a.html %V 148 %X We present an approach for maximizing a global utility function by learning how to allocate resources in an unsupervised way. We expect interactions between allocation targets to be important and therefore propose to learn the reward structure for near-optimal allocation policies with a GNN. By relaxing the resource constraint, we can employ gradient-based optimization in contrast to more standard evolutionary algorithms. Our algorithm is motivated by a problem in modern astronomy, where one needs to select-based on limited initial information-among $10^9$ galaxies those whose detailed measurement will lead to optimal inference of the composition of the universe. Our technique presents a way of flexibly learning an allocation strategy by only requiring forward simulators for the physics of interest and the measurement process. We anticipate that our technique will also find applications in a range of allocation problems from social science studies to customer satisfaction surveys and exploration strategies of autonomous agents.
APA
Cranmer, M., Melchior, P. & Nord, B.. (2021). Unsupervised Resource Allocation with Graph Neural Networks. NeurIPS 2020 Workshop on Pre-registration in Machine Learning, in Proceedings of Machine Learning Research 148:272-284 Available from http://proceedings.mlr.press/v148/cranmer21a.html.

Related Material