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.