  Real-world applications often combine learning and optimization problems on
graphs. For instance, our objective may be to cluster the graph in order to
detect meaningful communities (or solve other common graph optimization
problems such as facility location, maxcut, and so on). However, graphs or
related attributes are often only partially observed, introducing learning
problems such as link prediction which must be solved prior to optimization.
Standard approaches treat learning and optimization entirely separately, while
recent machine learning work aims to predict the optimal solution directly from
the inputs. Here, we propose an alternative decision-focused learning approach
that integrates a differentiable proxy for common graph optimization problems
as a layer in learned systems. The main idea is to learn a representation that
maps the original optimization problem onto a simpler proxy problem that can be
efficiently differentiated through. Experimental results show that our
ClusterNet system outperforms both pure end-to-end approaches (that directly
predict the optimal solution) and standard approaches that entirely separate
learning and optimization. Code for our system is available at
https://github.com/bwilder0/clusternet.
