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.