Timezone: »
Numerous real world applications involve discrete optimization problems on graphs, many of which are NP-hard and hence developing effective combinatorial algorithms is a research challenge. In this talk, I will show how leveraging the power of machine learning, and in particular graph representation learning, can provide a new paradigm for designing data-driven algorithms to solve combinatorial graph optimization problems. Our approaches automatically learn solution strategies from distribution of instances by explicitly considering the combinatorial task during training. We show that we match and often outperform hand-designed algorithms both with learning greedy algorithms for Minimum Vertex Cover, Maxcut and TSP, as well as when using our new framework ClusterNet to learn a graph representation for an efficient differential kmeans proxy for graph problems such as partitioning for Community Detection and node selection for Facility Location.
Author Information
Bistra Dilkina (University of Southern California)
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 Poster: End to end learning and optimization on graphs »
Bryan Wilder · Eric Ewing · Bistra Dilkina · Milind Tambe