RII Track-4:NSF: DyG-MAP: Fast Algorithms for Mining and Analysis of Evolving Patterns in Large Dynamic Graphs

RII Track-4：NSF：DyG-MAP：大型动态图中演化模式挖掘和分析的快速算法

• 批准号: 2132212
• 负责人: Shaikh Arifuzzaman
• 金额: $ 24.79万
• 依托单位: University of New Orleans
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2022
• 资助国家: 美国
• 起止时间: 2022-02-01 至 2023-04-30
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2132212&HistoricalAwards=false
• 关键词: RII; Track; NSF; DyG; MAP

Graphs (networks) are a versatile scientific framework to represent and analyze biological, social, and human-made complex systems. Such complex systems are inherently dynamic—for example, social interactions and human activities are intermittent; links appear and disappear in functional brain networks. Despite “time” playing a central role in those systems, most of the classic studies on graphs are based on the topological properties of static graphs (graphs that do not change over time). The existing works on dynamic graphs show only limited scalability for large-scale practical datasets. This proposed research aims at designing fast, scalable methods for revealing dynamic behaviors of a socio-technical system by developing innovative algorithmic and computing techniques. The host site, Berkeley Lab, will provide unique expertise and mentoring and facilitate access to leading supercomputer facilities to achieve the proposed research goals. The project will generate new algorithmic techniques and scalable software tools to advance graph-based data science and high-performance scientific computing. The PI includes an underrepresented graduate student in this research. Educational and training modules will also be developed for PI’s institution from the techniques and results emerging from this project. Thus, the project will enhance the scientific research, training, and education capacity of the PI’s jurisdiction.The goal of this EPSCoR proposal is to develop fast and scalable methods for mining and analyzing large dynamic graphs. Examples of such graphs include social networks, human contact networks, web graphs, and functional brain networks. The proposal addresses substructure-based problems such as finding evolving communities and enumerating interesting temporal subgraphs or motifs with applications in neuroscience, bioinformatics, infrastructure, and social domains. Even though there exists a rich literature for static graphs, the literature for dynamic graphs is very nascent. Existing parallel algorithms for dynamic graphs demonstrate limited scalability due to their low ratio of compute to memory operations and the irregular memory access patterns. Consequently, such algorithms show weak spatial and temporal locality, leading to poor cache utilization and high communication volume. The proposed research will utilize a unique collaboration with the Performance and Algorithms Group of Berkeley Lab to avail the most advanced user facilities and leading expertise to tackle the above technical challenges. The proposal aims at developing scalable parallel methods with efficient load-balancing and communication-avoidance techniques, data reduction approaches with sampling and sparsification, and efficient formalization of temporal metrics. Algorithmic methods generated from this proposal will be applicable in understanding dynamic properties of various real-world systems—for instance, locating key neurons in cortical (brain) networks, route-planning for time-varying traffic in infrastructure networks, modeling disease/virus or information propagation in social/contact networks. Therefore, the project will expand the PI’s research capacity to build impactful software/technology tools and also enhance his ability to serve a diverse student population at his host institution as both a research mentor and an educator.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

图（网络）是代表和分析生物，社会和人为复杂系统的多功能科学框架。这种复杂的系统本质上是动态的，例如，社会互动和人类活动是间歇性的。链接出现并消失在功能性脑网络中。尽管“时间”在这些系统中起着核心作用，但图形上的大多数经典研究都基于静态图的拓扑特性（随着时间的推移不会变化的图）。在动态图上的现有作品仅显示大规模实用数据集的可扩展性有限。这项提出的研究旨在设计快速，可扩展的方法，以通过开发创新的算法和计算技术来揭示社会技术系统的动态行为。主机网站伯克利实验室将提供独特的专业知识和心理化，并促进进入领先的超级计算机设施以实现拟议的研究目标。该项目将生成新的算法技术和可扩展的软件工具，以推动基于图的数据科学和高性能科学计算。 PI在这项研究中包括代表性不足的研究生。从该项目中出现的技术和结果，还将为PI机构开发教育和培训模块。这将增强PI管辖区的科学研究，培训和教育能力。该EPSCOR建议的目的是开发快速，可扩展的方法，用于采矿和分析大型动态图。此类图的示例包括社交网络，人接触网络，网络图和功能性大脑网络。该提案解决了基于子结构的问题，例如寻找不断发展的社区，并列举有趣的临时子图或主题，并在神经科学，生物信息学，基础架构和社会领域中应用。即使存在静态图的丰富文献，动态图的文献也非常新生。动态图的现有并行算法表明，由于其计算与内存操作和不规则的内存访问模式的比例低，因此其可伸缩性有限。因此，这种算法表现出较弱的空间和临时位置，导致缓存利用率差和高通信量。拟议的研究将利用伯克利实验室的性能和算法小组的独特合作，以可用的最先进的用户设施和领先的专业知识来应对上述技术挑战。该建议旨在开发具有有效的负载平衡和避免通信技术的可扩展平行方法，采样和稀疏的数据减少方法以及临时指标的有效格式化。该提案产生的算法方法将适用于理解各种现实世界系统的动态特性，例如，在皮质（脑）网络中找到关键神经元，在基础结构网络中的时间变化的路线计划，对疾病/病毒进行建模或社交/接触网络中的信息传播。因此，该项目将扩大PI的研究能力，以建立有影响力的软件/技术工具，并增强他作为研究精神和教育工作者在其主持人机构中为潜水员的学生提供服务的能力。该奖项反映了NSF的法定任务，并被认为是通过基金会的知识分子和更广泛影响的评估审查审查标准来通过评估来通过评估来获得的支持。