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.