Exploiting Asynchrony in Large-Scale Graph Mining

每天都会产生大量的数据，分析数据的一种常用技术是以“图”（通常称为网络）的形式表示数据，然后在这些图中提取隐藏的模式和关系，从而有助于推断出有洞察力的结果。这种在图中发现结构模式和关系的过程被称为“图挖掘”，它被广泛用于解决癌症检测、药物发现、欺诈检测和社会互动分析等重要问题。图挖掘通常需要结构等价性检查（正式称为“图同构”），这在计算上非常昂贵，导致分析程序运行数小时甚至数天来处理中等大小的图。当图变大时，问题会进一步恶化，这在各个领域都很常见。

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.