Timezone: »
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.
Author Information
Bryan Wilder (Harvard University)
Eric Ewing (University of Southern California)
Bistra Dilkina (University of Southern California)
Milind Tambe (USC)
More from the Same Authors
-
2022 : Invited Talk - Bistra Dilkina - University of Southern California »
Bistra Dilkina -
2020 Workshop: Learning Meets Combinatorial Algorithms »
Marin Vlastelica · Jialin Song · Aaron Ferber · Brandon Amos · Georg Martius · Bistra Dilkina · Yisong Yue -
2020 Poster: A General Large Neighborhood Search Framework for Solving Integer Linear Programs »
Jialin Song · ravi lanka · Yisong Yue · Bistra Dilkina -
2019 : Bistra Dilkina: Graph Representation Learning for Optimization on Graphs »
Bistra Dilkina -
2019 : Poster session »
Michael Melese Woldeyohannis · Bernardt Duvenhage · Nyamos Waigama · Asaye Bir Senay · Claire Babirye · Tensaye Ayalew · Kelechi Ogueji · Vinay Prabhu · Prabu Ravindran · Fadilulah Wahab · ChukwuNonso H Nwokoye · Paul Duckworth · Hafte Abera · Abebe Mideksa · Loubna Benabbou · Anugraha Sinha · Ivan Kiskin · Robert Soden · Tupokigwe Isagah · Rehema Mwawado · Yimer Mohammed · Bryan Wilder · Daniel Omeiza · Sunayana Rane · Richard Mgaya · Samsun Knight · Jessenia Gonzalez Villarreal · Eyob Beyene · Monika Obrocka Tulinska · Luis Fernando Cantu Diaz de Leon · Joseph Aro · Michael T Smith · Michael Famoroti · Praneeth Vepakomma · Ramesh Raskar · Debjani Bhowmick · Chukwunonso H Nwokoye · Alejandro Noriega Campero · Hope Mbelwa · Anusua Trivedi -
2019 Poster: Exploring Algorithmic Fairness in Robust Graph Covering Problems »
Aida Rahmattalabi · Phebe Vayanos · Anthony Fulginiti · Eric Rice · Bryan Wilder · Amulya Yadav · Milind Tambe -
2018 : The role of civil society in the age of AI: Beyond buzzwords »
Kathleen Siminyu · Milind Tambe · Michael Skirpan · Dongwoo Kim -
2014 Poster: Diverse Randomized Agents Vote to Win »
Albert Jiang · Leandro Soriano Marcolino · Ariel Procaccia · Tuomas Sandholm · Nisarg Shah · Milind Tambe