EAGER: A Framework for Learning Graph Algorithms with Applications to Social and Gene Networks

点击翻译按钮获取中文摘要

Many real world applications, such as discovering gene interaction networks, detecting fraud in financial networks and personalizing recommendations in social networks, involve NP-hard graph problems. Typically, approximation or heuristic algorithms designed for these problems rely heavily on manually specified structural information of graphs. Furthermore, previous graph algorithms seldom systematically exploit a common trait of industrial graph problems: instances of the same type of problem need to be solved repeatedly on a regular basis, and algorithms which are effective on average are more preferable than those with only a worst case guarantee. This project explores a novel deep learning framework for automating the design of algorithms for challenging graph problems. The framework delegates difficult choices during the design to deep learning models, and uses a distribution of problem instances to train effective graph algorithms. The project presents a paradigm shift in graph algorithm design, and results in a software package to disseminate the research. The project also involves a broader swath of students including undergraduates and underrepresented minorities through multiple existing summer research internship programs that target students nationwide.More specifically, the framework casts a graph algorithm as a composition of many small learnable operators either because it works on graph inputs, produces structured outputs, or the computation graph of the algorithm itself contains structures such as branches and recursions. Instead of specifying each operator manually as in traditional algorithm design, the framework parameterizes these operators using nonlinear embeddings, and learns them jointly from graph input and output pairs using supervised learning or reinforcement learning. Though demonstrated in specific gene and social networks, the framework is generic and broadly applicable to a large class of graph analysis problems appearing in a diverse range of real world applications.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.