HotCSE Seminar
Computational Science & Engineering
Wednesday Nov 25, 1pm-2pm, [Meeting Link]

A Framework for Differentiable Discovery of Graph Algorithms

Xinshi Chen
Advisor: Prof. Le Song

ABSTRACT

Recently there is a surge of interest in using graph neural networks (GNNs) to learn algorithms. However, these works focus more on imitating existing algorithms and are limited in two important aspects: the search space for algorithms is too small and the learned GNN models are not interpretable. To address these issues, we propose a novel framework which enlarges the search space using cheap global information from tree decomposition of the graphs and can explain the structures of the graph leading to the decision of learned algorithms. We apply our framework to three NP-complete problems on graphs and show that the framework is able to discover effective and explainable algorithms.

BIO

Xinshi Chen is a 4th year PhD student at Georgia Tech majoring in Machine Learning. She received her bachelor's and M.Phil. degree in Mathematics at the Chinese University of Hong Kong. Her current research focuses on bridging the connection between deep learning and traditional algorithms. She also works on graphical models, structure prediction, and applications in computational biology and recommendation system. Xinshi has spent time at Oak Ridge National Laboratory, Ant Financial, and Facebook AI as a research intern. Her research is generously supported by a Google PhD Fellowship in Machine Learning. Her homepage is [http://xinshi-chen.com].