Efficient Mining of Focused Patterns in Large Attributed Graphs

越来越多的组织和社区关注大数据分析和社交网络分析，以更快、更好地做出可能对商业和/或社会产生影响的决策。这种大型网络（例如，社交网络）可以被建模为属性图-属性伴随节点和边的图。在过去的十年中，我们见证了对挖掘有趣模式的广泛研究。正如在许多应用中所显示的那样，这种模式被认为揭示了网络的基本特征。然而，我们还没有看到太多的进展，模式挖掘属性图。不仅要考虑图的连通性信息，而且要考虑图的属性信息，以发现有意义的模式。* 在这项拟议的研究中，我们强调设计有效和高效的方法来发现基于用户偏好的模式，称为聚焦模式。我们解决了重要的问题，挑战和机会，提高集中模式挖掘属性图。这些问题的出现是由于数据的复杂性、规模和巨大的异质性。首先，我们定义的问题，推断的重点，由用户给出的约束。我们的目标是找到子图，其节点彼此接近，每个节点优选地覆盖多个约束。其次，在传统的子图挖掘中，用户应该降低阈值，以便发现显示感兴趣信息的子图。降低频率阈值会加剧挖掘过程中已经很昂贵的计算。为了解决这个问题，我们引入了新的挑战，高效用集中的模式发现属性图。我们研究理论方面的设计算法，发现高效用的子图在单一和多个图。第三，大多数现有的子图挖掘方法都是针对静态大图或顺序流图设计的。我们研究如何设计算法，工作在MapReduce风格的平台流图。我们设计了资源感知的数据结构来缓存图的足够信息，并在内存约束下找到最佳的子图集的近似算法。* 我们的研究计划符合加拿大的创新议程。在大数据和图形挖掘方面进行世界级的研究有可能吸引来自世界各地的优秀学生，同时留住国内人才。我们计划在他们准备申请学术界和工业界的工作时，将他们置于一个有竞争力的位置。我们预计多达12名学生（包括本科生）将在本研究计划中接受培训。此外，拟议的研究结果是有价值的加拿大和国际商业和政府组织。这些结果也引起了IBM、Facebook和LinkedIn等软件供应商的兴趣。

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.