A Framework for Differentiable Discovery of Graph Algorithms

Explore a groundbreaking framework for differentiable discovery of graph algorithms in this 29-minute conference talk by Le Song from Georgia Institute of Technology. Delve into the challenges of using graph neural networks (GNNs) to learn algorithms and discover how this innovative approach addresses limitations in search space and interpretability. Learn how the framework incorporates cheap global information from tree decomposition of graphs and explains the structures leading to algorithmic decisions. Examine applications to three NP-complete graph problems and understand how this method discovers effective and explainable algorithms. Gain insights into topics such as combinatorial optimization, distributed local algorithms, reinforcement learning, and the use of spanning trees as global features. Understand the concept of Differentiable Algorithm Discovery (DAD) and its potential to revolutionize graph algorithm development.

Intro
Graphs are everywhere
Combinatorial optimization over graph
Graph neural networks (GNN/MPN/Structure2vec)
Sequential vs distributed local algorithms
Leaming algorithms with reinforcement leaming
Example of leamed sequential algorithms
Example of distributed local algorithms: PageRank
GNN - Parametrized distributed local graph algorithm
Challenges for leaming new algorithms
Motivating example
Spanning tree solution as cheap global feature
Multiple spanning trees to multiple features
Better learned algorithms with global information
Unsupervised
Better time-solution trade-off
Anchor nodes of explanation
Comparing feature quality
Differentiable Algorithm Discovery (DAD)