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

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

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.