EAGER: Facilitating Graph Computation by Graph Sparsification

在过去的十年中，现代科学和技术见证了网络系统的爆炸式增长，产生了规模、结构和复杂性完全改变的巨大数据海洋，这些数据通常被建模和解释为图形。然而，现实世界的图结构数据非常庞大，并且表现出前所未有的复杂性和独特的挑战，使得它们非常难以管理，摄取成本高，分析复杂。在这个项目中，PI将系统地研究图稀疏化的原理、方法和算法，其目标是将大规模图简化为结构丰富、保持质量的图摘要，以促进和优化现实世界中大规模图的广泛的基于图的计算。该项目将为管理和理解大图形开辟一个新的研究前沿，促进网络系统的广泛可用性，并为整个现代网络社会提供高效、经济、可扩展的图形管理、访问和总结解决方案。PI计划为大图形数据的稀疏化开发新的基础、原理和算法，并系统地解决图形稀疏化的一系列核心挑战：1。大图的关键结构或关键属性应该编码在稀疏化的图摘要中。如何高效、经济、可扩展地稀疏大图形。3. 如何使用稀疏化的图摘要来支持基于图的计算和分析，包括但不限于图聚类、分类、查询处理和链接预测。PI将以他在图数据管理方面的广泛背景为基础，开发新的图稀疏化方法，并将它们集成到现实世界的图数据库和大图中，以促进大规模的图计算。特别是，PI将在一系列蛋白质-蛋白质相互作用网络、社交网络、RNA分子图数据库和原位海洋图数据库中应用和验证所提出的图稀疏化技术。该项目在教育下一代专业工作者和学者，特别是来自代表性不足群体的专业工作者和学者方面发挥着不可或缺的作用，并通过佛罗里达州立大学青年学者计划为K-12的推广活动做出贡献。最后，来自项目的数据、系统工件和出版物将在研究界和公众中广泛传播，以增强研究和教育的基础设施。

Modern science and technology have witnessed in the past decade an explosive growth of networked systems giving rise to a vast ocean of data with completely transformed scale, structure, and complexity, which are often modeled and interpreted as graphs. However, real-world graph-structured data are voluminous and exhibit unprecedented complexity and unique challenges that render them extremely hard to manage, costly to ingest, and complicated to analyze. In this project, the PI will systematically investigate the principles, methodologies, and algorithms of graph sparsification, the objective of which is to simplify large-scale graphs into structure-enriched, quality-preserving graph summaries toward facilitating and optimizing a wide range of graph-based computations in real-world, large-scale graphs. This project will open a new research frontier for managing and understanding big graphs, facilitate the widespread availability of networked systems, and result in efficient, cost-effective, and scalable graph management, access, and summarization solutions for the whole modern, networked society.The PI plans to develop new foundations, principles, and algorithms for sparsifying big graph data, and systematically address a series of central challenges for graph sparsification: 1. What crucial structures or key properties of big graphs should be encoded in sparsified graph summaries. 2 How to sparsify big graphs efficiently, cost-effectively, and scalably. 3. How to employ sparsified graph summaries in support of graph-based computation and analytics, including, but not limited to, graph clustering, classification, query processing, and link prediction. The PI will build on his extensive background in graph data management to develop new graph sparsification methods, and integrate them toward facilitating large-scale graph computation in real-world graph databases and big graphs. In particular, the PI will apply and validate the proposed graph sparsification techniques in a series of protein-protein interaction networks, social networks, RNA molecule graph databases, and in-situ oceanographic graph databases. The project plays an integral part in educating next-generation professional workers and scholars especially from underrepresented groups, and contributing to K-12 outreach activities through the Florida State University Young Scholars program. Finally, data, system artifacts, and publications from the project will be disseminated broadly in the research community and to the public to enhance the infrastructure for research and education.