Exploiting Asynchrony in Large-Scale Graph Mining

在大规模图挖掘中利用异步

• 批准号: RGPIN-2018-05175
• 负责人: Vora, Keval
• 金额: $ 1.68万
• 依托单位: Simon Fraser University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2022
• 资助国家: 加拿大
• 起止时间: 2022-01-01 至 2023-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=750582
• 关键词: Exploiting; Asynchrony; Large; Scale; Graph

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.

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