Exploiting Asynchrony in Large-Scale Graph Mining

每天都会产生大量的数据，分析数据的一种常用技术是以“图”（通常称为网络）的形式表示数据，然后在这些图中提取隐藏的模式和关系，从而有助于推断出有洞察力的结果。这种在图中发现结构模式和关系的过程被称为“图挖掘”，它被广泛用于解决癌症检测、药物发现、欺诈检测和社会互动分析等重要问题。图挖掘通常需要结构等价性检查（正式称为“图同构”），这在计算上非常昂贵，导致分析程序运行数小时甚至数天来处理中等大小的图。当图变大时，问题会进一步恶化，这在各个领域都很常见。我们建议开发可扩展的图挖掘技术，以对大型静态和动态图进行有效的挖掘。为了实现这一点，我们计划利用“异步”，这是一个基本属性，它打破了跨计算的依赖关系，从而释放了不确定的，但受控的并行执行行为。这开启了广泛的性能优化，以实现高度并发执行，并充分利用多核处理器、ram、网络和磁盘等系统资源。基于这种异步执行，我们将开发异步图挖掘框架，它是通用的，足以通过易于使用的编程api支持大型图上特定于应用程序的挖掘任务。我们还将开发定制的图挖掘解决方案，以支持不同类型的特定领域的图挖掘问题。我们的图形挖掘工具将开放源代码，供健康、医学、数据挖掘和安全等各个重要领域的研究人员使用。它还将帮助各种小型和大型企业；例如，加拿大的Trulioo、CogniLab以及b谷歌和Facebook等其他科技行业公司可以改善他们的重要任务，如分析社交网络、推荐服务、垃圾邮件检测和发现软件漏洞。我们的研究成果将与不同的大学和研究公司分享，以促进更广泛的计算机系统研究界的进一步研究和发展。最后，我们提出的研究开发的技术将被纳入西蒙弗雷泽大学“并行与分布式计算”等相关课程的教材中。

With massive amounts of data being generated every day, a common technique to analyze data is to represent it in form of "graphs" (commonly called networks) and then, extract hidden patterns and relationships within these graphs that help in deducing insightful results. This process of finding structural patterns and relationships in graphs is known as "Graph Mining" and it is widely used to solve important problems like cancer detection, drug discovery, fraud detection and social interaction analysis. Graph mining often requires structural equivalence checks (formally known as "graph isomorphism") that are computationally very expensive, causing the analysis programs to run for hours and even days for just medium sized graphs. The problem further aggravates when graphs grow large, which is common across various domains.We propose to develop scalable graph mining techniques to perform efficient mining over large static and dynamic graphs. To achieve this, we plan to leverage "asynchrony" which is a fundamental property that breaks dependencies across computations, hence unleashing non-deterministic, yet controlled, parallel execution behavior. This opens up a wide range of performance optimizations to enable highly concurrent execution and that fully utilize system resources like multicore processors, RAMs, network and disks. Based on such asynchronous execution, we will develop asynchronous graph mining framework that is general purpose enough to support application-specific mining tasks over large graphs via easy to use programming APIs. We will also develop custom graph mining solutions to support different kinds of domain-specific graph mining problems.Our graph mining tools will be made open-source for researchers across various important domains like health, medicine, data mining and security. It will also help various small and large scale businesses; for example, Canada's Trulioo, CogniLab, and other tech-sector companies like Google and Facebook can improve their important tasks like analyzing social networks, recommend services, spam detection and finding software vulnerabilities. Our research outcomes will be shared with different universities and research firms to foster further research and development by wider computer systems research community. Finally, the techniques developed from our proposed research will be incorporated into course materials of relevant courses like "Parallel & Distributed Computing" at Simon Fraser University.