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

频繁子图挖掘是数据挖掘中的一项核心任务，可以应用于与图和网络相关的各种现实问题。目前，随着生命科学和社会科学领域大量网络数据的可用性的增加，这一任务的研究价值得到了提高。然而，现有的子图挖掘算法存在各种局限性；其中值得注意的是缺乏可伸缩性、缺乏用户交互以及缺乏挖掘动态图的机制。本研究旨在克服上述局限性，完成以下三个相关任务：(1)利用蒙特卡罗采样机制设计可扩展图挖掘算法；(2)利用子图采样方法开发实时交互图挖掘系统；(3)发现基于采样并由博弈论和经济学原理驱动的图进化模型。本研究建立了一种基于蒙特卡罗采样的子图挖掘新范式。通过避免枚举所有子图模式的需要，这允许开发可扩展的算法。由此产生的算法将应用于系统生物学中的子图挖掘问题，例如，通过从基因组学和蛋白质组学共表达网络中挖掘图来预测疾病途径。本研究的第二个成果是使用子图采样的交互式模式挖掘框架，其中用户反馈指导采样分布的更新，以便后续采样优先考虑用户认为“感兴趣”的模式。第三个成果是子图采样方法，该方法使用博弈论机制设计动态网络中预测任务（如链路预测）的子图演化模型。更广泛的影响：挖掘大型图表的工具的可用性使构建网络生物标志物成为可能，这是疾病诊断和风险因素分析的新特征。基于抽样的交互模式系统有助于从目前许多医院和诊所尚未探索的众多隐藏数据集中挖掘疾病和药物之间“有趣”的关联。可扩展的图形挖掘算法也可能在搜索、电子商务和基于社交网络的行业中找到用途。这项研究的教育目标是利用PI的工业经验来开发一门“大规模数据分析”课程，该课程涉及构建用于工业规模数据的数据挖掘系统所需的方法。有关该项目的其他信息，包括研究结果、方法、算法的开源实现、出版物和数据，可通过该项目的网站http://www.cs.iupui.edu/~alhasan/graph_mining访问。

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.