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

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

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.