CAREER: Parallel Algorithms and Frameworks for Graph and Hypergraph Processing

职业：图和超图处理的并行算法和框架

• 批准号: 1845763
• 负责人: Julian Shun
• 金额: $ 59.76万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2019
• 资助国家: 美国
• 起止时间: 2019-03-01 至 2025-02-28
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1845763&HistoricalAwards=false
• 关键词: CAREER; Parallel; Algorithms; Frameworks; Graph

Graphs are a tool used to model the interactions between various entities. Efficiently processing large graphs has attracted significant attention due to its applications in various domains, such as biology, chemistry, and social network analysis. With the explosion in the volume of data, graphs have become very large and can contain hundreds of billions of vertices and trillions of edges. Various applications also benefit from modeling the underlying data as a hypergraph, which enables relationships among multiple entities to be represented better than a graph. In addition, many of these data sets are changing rapidly in real-time and applications require computing results on the latest data. It is crucial to design high-performance parallel algorithms to enable analysis to be done on graphs and hypergraphs in a timely fashion. However, writing efficient parallel code is notoriously difficult. Furthermore, many parallel algorithms used in practice today do not have strong theoretical guarantees, causing them to perform extremely poorly on certain inputs. To address these challenges, this project involves creating high-level programming frameworks with highly-optimized backends to make it easier for non-experts to write high-performance parallel programs for graphs and hypergraphs dealing with static and streaming data. This project also involves designing parallel algorithms that are efficient both in theory and in practice, so that they can perform well under all possible inputs and across many machine parameters, and scale gracefully to larger data sets. Using the resulting algorithms and frameworks, scientists will be able to use high-level tools to perform graph and hypergraph analytics on massive inputs much more efficiently than before, both in theory and in practice.This project involves designing new parallel primitives and algorithms for many fundamental graph and hypergraph problems that are fast and memory-efficient, both in theory and in practice. The new algorithms are being evaluated on the largest publicly-available data sets using large-scale multicore machines. The project also involves creating high-level abstractions and programming frameworks to support the implementation of theoretically-efficient algorithms on both static and streaming data. First, a domain specific language for graph computations that generates efficient and highly-optimized code from high-level specifications of algorithms and optimizations will be designed. Second, a unified framework for streaming graph analytics that can efficiently support parallel updates to the graph (simultaneously running algorithms and updates), incremental algorithms, and temporal analysis will be developed. Finally, a novel abstraction and framework for hypergraph processing that will support theoretically-efficient implementations of hypergraph algorithms will be designed. The results will lead to fundamental advances in parallel algorithm design and programming frameworks for graph and hypergraph analytics.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.

图是用于对各种实体之间的交互进行建模的工具。高效处理大图由于其在生物学、化学和社交网络分析等各个领域的应用而引起了极大的关注。 随着数据量的爆炸式增长，图变得非常大，可以包含数千亿个顶点和数万亿个边。各种应用程序还受益于将底层数据建模为超图，这使得多个实体之间的关系能够比图更好地表示。 此外，许多数据集实时快速变化，应用程序需要最新数据的计算结果。 设计高性能并行算法以便及时对图和超图进行分析至关重要。 然而，编写高效的并行代码是出了名的困难。此外，当今实践中使用的许多并行算法没有强有力的理论保证，导致它们在某些输入上表现极差。为了应对这些挑战，该项目涉及创建具有高度优化后端的高级编程框架，以使非专家更容易为处理静态和流数据的图和超图编写高性能并行程序。该项目还涉及设计在理论和实践中都高效的并行算法，以便它们可以在所有可能的输入和跨许多机器参数下表现良好，并优雅地扩展到更大的数据集。 使用由此产生的算法和框架，科学家将能够使用高级工具对海量输入执行图形和超图分析，无论是在理论上还是在实践中，都比以前更有效。该项目涉及为许多基本图形和超图问题设计新的并行基元和算法，这些基元和算法在理论和实践中都快速且内存高效。 新算法正在使用大型多核机器在最大的公开数据集上进行评估。该项目还涉及创建高级抽象和编程框架，以支持在静态和流数据上实现理论上高效的算法。首先，将设计一种用于图计算的领域特定语言，该语言根据算法和优化的高级规范生成高效且高度优化的代码。 其次，将开发一个统一的流图分析框架，可以有效地支持图的并行更新（同时运行算法和更新）、增量算法和时间分析。 最后，将设计一种新颖的超图处理抽象和框架，该框架将支持超图算法理论上高效的实现。 研究结果将带来图和超图分析的并行算法设计和编程框架的根本性进步。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。

项目成果

Parallel Five-cycle Counting Algorithms

• DOI: 10.1145/3556541
• 发表时间: 2022-08
• 期刊: ACM Journal of Experimental Algorithmics
• 作者: Jessica Shi;Louisa Ruixue Huang;Julian Shun

Theoretically and Practically Efficient Parallel Nucleus Decomposition

• DOI: 10.14778/3494124.3494140
• 发表时间: 2021-11
• 期刊: ArXiv
• 作者: Jessica Shi;Laxman Dhulipala;Julian Shun

Parallel Index-Based Structural Graph Clustering and Its Approximation

• DOI: 10.1145/3448016.3457278
• 发表时间: 2020-12
• 期刊: Proceedings of the 2021 International Conference on Management of Data
• 作者: Tom Tseng;Laxman Dhulipala;Julian Shun

Parallel Batch-Dynamic k-Clique Counting

• DOI: 10.1137/1.9781611976489.10
• 发表时间: 2020-03
• 期刊: Inorganic chemistry
• 影响因子: 4.6
• 作者: Laxman Dhulipala;Quanquan C. Liu;Julian Shun

Differential Privacy from Locally Adjustable Graph Algorithms: k-Core Decomposition, Low Out-Degree Ordering, and Densest Subgraphs

• DOI: 10.1109/focs54457.2022.00077
• 发表时间: 2022-10
• 期刊: 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS)
• 作者: Laxman Dhulipala;Quanquan C. Liu;Sofya Raskhodnikova;Jessica Shi;Julian Shun;Shangdi Yu