CAREER: A novel framework for mining graph patterns in large biological and social networks

职业：在大型生物和社交网络中挖掘图形模式的新颖框架

• 批准号: 1149851
• 负责人: Mohammad Hasan
• 金额: $ 54.74万
• 依托单位: Indiana University
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-03-01 至 2017-02-28
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1149851&HistoricalAwards=false
• 关键词: CAREER; novel; framework; mining; graph

Frequent subgraph mining is a core task in data mining which can be applied to various real-life problems related to graphs and networks. Presently, the research value of this task has been heightened by the increased availability of massive network data in the domains of life and social sciences. However, existing algorithms for subgraph mining suffer from various limitations; noteworthy among these are lack of scalability, lack of user interaction and the absence of a mechanism to mine dynamic graphs. This research aims to overcome the above limitations by accomplishing the following three related tasks: (1) use of Monte Carlo sampling mechanisms for designing scalable graph mining algorithms; (2) develop real-time interactive graph mining systems using subgraph sampling approaches; and (3) discover models for graph evolution that are based on sampling and driven by the principles of game theory and economics.This research builds a novel paradigm for subgraph mining that is based on Monte Carlo sampling. This allows the development of algorithms that are scalable, by avoiding the need to enumerate all subgraph patterns. The resulting algorithms will be applied to subgraph mining problems in systems biology, e.g., predicting disease pathways by mining graphs from genomics and proteomics co-expression networks. A second outcome of this research is an interactive pattern mining framework using subgraph sampling where user feedback guides updates of the sampling distribution such that subsequent sampling prioritizes patterns that are considered "interesting" to the user. A third outcome is a subgraph sampling method that uses a game theoretic mechanism to design a subgraph evolution model for prediction tasks (such as link prediction) in dynamic networks. Broader Impacts: Availability of tools for mining large graphs enables the opportunity to build network biomarkers, which are novel signatures for disease diagnosis and risk factor analysis. A sampling based interactive pattern system is instrumental to mine "interesting" associations between diseases and medicines from numerous hidden datasets that are currently unexplored in many hospitals and health clinics. Scalable graph mining algorithms are also likely to find use in search, e-commerce and social networks based industry. The educational goal of this research is to leverage the PI's industrial experience to develop a "Large-scale data analysis" course on methods needed to build data mining systems that work on industry-scale data.Additional information about the project, including the findings, methods, open source implementations of algorithms, publications and data can be accessed through the project website at http://www.cs.iupui.edu/~alhasan/graph_mining.

频繁的子图挖掘是数据挖掘的核心任务，可以应用于与图形和网络有关的各种现实生活问题。目前，由于生活和社会科学领域中大量网络数据的可用性增加，该任务的研究价值已得到提高。但是，现有的子图挖掘算法受到各种局限性；其中值得注意的是缺乏可扩展性，缺乏用户相互作用以及缺乏用于开采动态图的机制。这项研究旨在通过完成以下三个相关任务来克服上述局限性：（1）使用蒙特卡洛采样机制来设计可扩展的图形挖掘算法； （2）使用子图采样方法开发实时交互式图挖掘系统； （3）发现基于采样和受游戏理论和经济学原理驱动的图形进化模型。这项研究建立了基于蒙特卡洛采样的新型次级挖掘范式。这可以通过避免列举所有子图模式来开发可扩展的算法。所得算法将应用于系统生物学中的子图采矿问题，例如，通过挖掘基因组学和蛋白质组学共表达网络来预测疾病途径。这项研究的第二个结果是使用子图抽样的交互式模式挖掘框架，其中用户反馈指南对采样分布的更新进行了更新，以便随后的采样优先考虑对用户“有趣”的模式。第三个结果是一种子图抽样方法，该方法使用游戏理论机制来设计动态网络中预测任务（例如链接预测）的子图进化模型。更广泛的影响：挖掘大图的工具的可用性使得有机会建立网络生物标志物，这是用于疾病诊断和危险因素分析的新型签名。基于抽样的交互式模式系统对疾病与药物之间的“有趣”关联起到了重要的作用，这些隐藏数据集目前在许多医院和健康诊所中都无法探索这些关联。可扩展的图表挖掘算法也可能在搜索，电子商务和社交网络的行业中找到使用。这项研究的教育目标是利用PI的工业经验来开发有关构建在行业规模数据上工作的数据挖掘系统所需的方法的“大规模数据分析”课程。有关该项目的信息，包括调查结果，方法，方法，方法，开放源代码，可以通过算法，出版物和数据在项目网站上通过项目网站在项目网站上访问。 http://www.cs.iupui.edu/~alhasan/graph_mining。