Bistra Dilkina: Graph Representation Learning for Optimization on Graphs

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.