Efficient Mining of Focused Patterns in Large Attributed Graphs

越来越多的组织和社区正在关注大数据分析和社交网络分析，以做出更快、更好的决策，这些决策可能会对商业和/或社会产生影响。这种大型网络（例如，社交网络）可以建模为属性图——一种带有节点和边的属性的图。在过去的十年中，我们见证了对挖掘图以寻找有趣模式的广泛研究。正如在许多应用中所显示的那样，这种模式被认为揭示了网络的基本特征。然而，我们在属性图的模式挖掘方面还没有看到很大的进展。要发现有意义的模式，不仅要考虑图的连通性信息，还要考虑属性信息。

Increasingly, organizations and communities are focusing on big data analytics and social network analysis to make faster and better decisions that might have a business and/or societal impact. Such large networks (e.g., social networks) can be modeled as attributed graphs - a graph that attributes accompanying the nodes and edges. Over the past decade, we have witnessed extensive study on mining graphs for interesting patterns. As shown in many applications, such patterns are believed to reveal essential features of the network. However, we have not seen much progress in pattern mining over attributed graphs. It is critical not only to consider the connectivity information of a graph but also the attribute information to discover meaningful patterns. In this proposed research, we emphasize on designing effective and efficient methods to find patterns based on user preferences, called focused patterns. We address important problems, challenges, and opportunities for improving focused pattern mining in attributed graphs. These issues arise due to the complexity, scale and massive heterogeneity of data. First, we define the problem of inferring the focus from constraints given by the user. We aim to find subgraphs whose nodes are close to each other with each node preferably covering multiple constraints. Second, in traditional subgraph mining, the user should lower the threshold such that subgraphs showing interesting information are discovered. Lowering the frequency threshold intensifies the already expensive computations of the mining process. To address this, we introduce the new challenge of high utility focused pattern discovery in attributed graphs. We study theoretical aspects to design algorithms for finding high utility subgraphs in both single and multiple graphs. Third, most existing subgraph mining methods are designed for either static big graphs or sequential streaming graphs. We study how to design algorithms to work in a MapReduce-style platform for streaming graphs. We design resource-aware data structures to cache sufficient information of the graph, and approximate algorithms to find the best possible set of subgraphs under the memory constraint. Our research program aligns with Canada's Innovation Agenda. Conducting world-class research in big data and graph mining has the potential to attract talented students from around the world while keeping domestic talents here. We plan to place them in a competitive position as they prepare for applying for jobs in academia and industry. We expect up to twelve students (including undergraduate students) to receive training in this research program. Moreover, the results of the proposed research are valuable for Canadian and international business and government organizations. The outcomes also are of interest to software vendors, such as IBM, Facebook, and LinkedIn.