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.