*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Title: Learning Neural Algorithms with Graph Structures
Date: Tuesday, Dec 3, 2019
Time: 12:00 p.m. to 1:30 p.m. (EST)
Location: Coda C1003 Adair
Hanjun Dai
School of Computational Science and Engineering,
College of Computing,
Georgia Institute of Technology
Committee:
Dr. Le Song (Advisor, School of Computational Science and Engineering, Georgia Institute of Technology)
Dr. Richard Vuduc (School of Computational Science and Engineering, Georgia Institute of Technology)
Dr. Duen Horng (Polo) Chau (School of Computational Science and Engineering, Georgia Institute of Technology)
Dr. John Schulman (OpenAI)
Dr. Pushmeet Kohli (DeepMind)
Abstract:
Graph structures, like syntax trees, social networks, and programs, are ubiquitous in many real world applications including knowledge graph inference, chemistry and social network analysis. Over the past several decades, many expert-designed algorithms on graphs have been proposed with nice theoretical properties. Recent advances in deep learning have shown strong empirical performances for images, texts and signals. However the combinatorial and discrete nature of graphs makes it non-trivial to apply neural networks in this domain. This thesis will discuss several aspects on how to build a tight connection between neural networks and the classical algorithms for graphs. Specifically:
1) Firstly, the existing algorithms provide an inspiration of deep architecture design, for both the discriminative learning and generative modeling of graphs. Regarding the discriminative representation learning, we show how the graphical model inference algorithms can inspire the design of graph neural networks, and how to scale it up with the idea borrowed from steady states algorithms like PageRank; for generative modeling, we leverage the idea of attribute grammar for syntax trees to help regulate the deep networks.
2) Secondly, the algorithm framework has procedures that can be enhanced by learnable deep network components. We demonstrate by learning the heuristic function in greedy algorithms with reinforcement learning for combinatorial optimization problems over graphs, such as vertex cover and max cut.
3) Finally, as the algorithm structure generally provides a good inductive bias for the problem, we take an initial step towards inductive reasoning for such structure, where we make attempts to reason about the loop invariant for program verification and the reaction templates for retrosynthesis structured prediction.
Besides the topics covered above, we will also discuss limitations and future extensions of this thesis work.
