Graph Optimization via Deep Reinforcement Learning

Sponsoring Agency
Samsung Advanced Institute of Technology

Summary

Many important real-world problems are essentially graph optimization/manipulation problems. For example, in order to speed-up or intervene a dissemination, or to increase/decrease average shortest path of a network, we can change the network structure by adding or deleting certain edges. Existing graph optimization/manipulation algorithms mainly adopts linear optimization or spectral analysis on adjacency matrix.

Despite the success of existing methods, graph optimization/manipulation remains a challenging problem and needs further investigation because: (i) The underlying structure of the graph, especially large graphs, is highly non-linear, which cannot be well modeled by existing algorithms that directly operates on adjacency matrix; and (ii) Real graphs can be present in different formats such as heterogeneous graphs and multidimensional graphs; while existing methods are dedicated to plain graphs, i.e., graphs with only nodes and edges. Hence, effective graph optimization methods that can capture high nonlinearity of network structures for decision making and can deal with different types of graphs are needed.

Graph optimization of adding/deleting links or nodes is a sequential decision-making process and reinforcement learning is a natural choice for graph optimization. With reinforcement learning, we can design effective non-linear policy networks for making better decisions in adding/deleting nodes/links. Recent advancement of graph neural networks (GNN) has shown promising results in learning representations of graphs that capture non-linearly of network structures, which paves us a way to represent the graphs as input to policy networks. Therefore, in this project, we embrace new challenges and opportunities to systematically investigate graph optimization via deep reinforcement learning and graph neural networks for various types of graphs.

Term
 -