III: Small: A Novel Framework for Mining Multi-relation and Labeled Graphs

III：Small：挖掘多关系和标记图的新颖框架

• 批准号: 1423321
• 负责人: Saeed Salem
• 金额: $ 34.56万
• 依托单位: North Dakota State University Fargo
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-08-01 至 2019-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1423321&HistoricalAwards=false
• 关键词: III; Small; Novel; Framework; Mining

Complex networks appear in a wide spectrum of fields including bioinformatics and neuroscience. They are governed by intricate webs of interactions among constituent elements. Entities and relationships in graphs are increasingly being annotated with content, thus giving rise to rich attributed graphs. Effective integration of attribute data with network topology will enable scientists to ask new questions and discover novel findings that are not possible using only one source of data. This project is developing methods to find interesting patterns in networks that represent multiple types of information, e.g., gene expression and protein-protein interaction networks along with disease information, or co-authorship graphs with information on both the conference and year of publication. As an example of the value of such pattern discovery, protein-protein interaction subnetworks whose genes are dysregulated in multiple disease genome-wide expression datasets are useful for disease diagnosis and mechanism understanding. The proposed research aims to develop a suite of algorithmic and analytic methods for analyzing large multi-relation and attributed graphs. Specifically, the project is: (i) developing novel concepts and algorithms for mining cross-graph interesting patterns from multi-relation graphs, and coherent patterns from attributed graphs, and (ii) designing computational methods for integrating biological data (e.g., gene expression, protein-protein interaction networks) for discovering coherent and phenotype-specific subnetworks. This poses interesting challenges due to the computational complexity of many subgraph discovery tasks; this project is using application (e.g., biologically) motivated definitions as a starting point to identify interesting pattern definitions for which discovery is tractable. In addition to dissemination to the research community, outcomes will include software tools for use by the broader scientific community, developing new courses in the area of network analysis, educational material for introducing high school students to computational thinking, and increasing minority undergraduate students involvement in research.

复杂网络出现在包括生物信息学和神经科学在内的广泛领域。 它们由组成要素之间错综复杂的相互作用网络所支配。图中的实体和关系越来越多地被内容注释，从而产生了丰富的属性图。属性数据与网络拓扑结构的有效集成将使科学家能够提出新的问题，并发现仅使用一个数据源不可能发现的新发现。 该项目正在开发方法来寻找代表多种类型信息的网络中有趣的模式，例如，基因表达和蛋白质-蛋白质相互作用网络沿着疾病信息，或具有关于会议和出版年份的信息的合著者图表。 作为这种模式发现价值的一个例子，蛋白质-蛋白质相互作用子网络（其基因在多个疾病全基因组表达数据集中失调）可用于疾病诊断和机制理解。 该研究旨在开发一套用于分析大型多关系和属性图的算法和分析方法。具体而言，该项目是：（i）开发用于从多关系图中挖掘交叉图有趣模式以及从属性图中挖掘相干模式的新概念和算法，以及（ii）设计用于整合生物数据的计算方法（例如，基因表达，蛋白质-蛋白质相互作用网络），用于发现连贯的和表型特异性的子网络。 由于许多子图发现任务的计算复杂性，这提出了有趣的挑战;该项目正在使用应用程序（例如，生物学）动机的定义作为起点来识别发现可处理的感兴趣的模式定义。 除了向研究界传播，成果还将包括供更广泛的科学界使用的软件工具，开发网络分析领域的新课程，向高中生介绍计算思维的教育材料，以及增加少数民族本科生参与研究。