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

EAGER：学习图算法及其在社交和基因网络中的应用的框架

• 批准号: 1841351
• 负责人: Srinivas Aluru
• 金额: $ 30万
• 依托单位: Georgia Tech Research Corporation
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2018
• 资助国家: 美国
• 起止时间: 2018-09-01 至 2021-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1841351&HistoricalAwards=false
• 关键词: EAGER; Framework; Learning; Graph; Algorithms

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.

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

项目成果

Molecule optimization by explainable evolution

通过可解释的进化进行分子优化

• 发表时间: 2021-01
• 期刊: International Conference on Learning Representation (ICLR
• 作者: Chen, Binghong;Wang, Tianzhe;Li, Chengtao;Dai, Hanjun;Song, Le
• 通讯作者: Song, Le

GLAD: Learning sparse graph recovery

GLAD：学习稀疏图恢复

• 发表时间: 2020-01
• 期刊: International Conference on Learning Representations (ICLR
• 作者: Shrivastava, Harsh;Chen, Xinshi;Chen, Binghong;Lan, Guanghui;Aluru, Srinivas;Liu, Han;Song, Le
• 通讯作者: Song, Le

EnGRaiN : a supervised ensemble learning method for recovery of large-scale gene regulatory networks

EnGRaiN：一种用于恢复大规模基因调控网络的监督集成学习方法

• DOI: 10.1093/bioinformatics/btab829
• 发表时间: 2021-12
• 期刊: Bioinformatics
• 影响因子: 5.8
• 作者: Aluru, Maneesha;Shrivastava, Harsh;Chockalingam, Sriram P.;Shivakumar, Shruti;Aluru, Srinivas;Martelli, ed., Pier Luigi
• 通讯作者: Martelli, ed., Pier Luigi

GRNUlar: A Deep Learning Framework for Recovering Single-Cell Gene Regulatory Networks

GRNUlar：用于恢复单细胞基因调控网络的深度学习框架

• DOI: 10.1089/cmb.2021.0437
• 发表时间: 2022-01
• 期刊: Journal of Computational Biology
• 影响因子: 1.7
• 作者: Shrivastava, Harsh;Zhang, Xiuwei;Song, Le;Aluru, Srinivas
• 通讯作者: Aluru, Srinivas