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

许多现实世界的应用，如发现基因相互作用网络、检测金融网络中的欺诈和社交网络中的个性化推荐，都涉及到NP-hard图问题。通常，为这些问题设计的近似或启发式算法严重依赖于手动指定的图的结构信息。此外，以前的图算法很少系统地利用工业图问题的共同特征：同一类型问题的实例需要定期重复解决，平均有效的算法比只有最坏情况保证的算法更可取。该项目探索了一种新的深度学习框架，用于自动设计具有挑战性的图问题的算法。该框架将设计过程中的困难选择委托给深度学习模型，并使用问题实例的分布来训练有效的图算法。该项目提出了图形算法设计的范式转变，并产生了一个软件包来传播研究。该项目还通过多个针对全国学生的暑期研究实习项目，吸引了更广泛的学生，包括本科生和代表性不足的少数族裔。更具体地说，该框架将图算法转换为许多小的可学习运算符的组合，因为它可以处理图输入，产生结构化输出，或者算法的计算图本身包含分支和递归等结构。该框架不像传统算法设计那样手动指定每个算子，而是使用非线性嵌入对这些算子进行参数化，并使用监督学习或强化学习从图输入和输出对中共同学习它们。虽然在特定的基因和社会网络中得到了证明，但该框架是通用的，广泛适用于在各种现实世界应用中出现的大量图形分析问题。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.