CRII: III: Structure-aware Graph Compressing: From Algorithms to Applications

CRII：III：结构感知图压缩：从算法到应用程序

• 批准号: 2104720
• 负责人: Esra Akbas
• 金额: $ 17.43万
• 依托单位: Oklahoma State University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2021
• 资助国家: 美国
• 起止时间: 2021-08-01 至 2023-01-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2104720&HistoricalAwards=false
• 关键词: CRII; III; Structure; aware; Graph

Graph mining is an emerging field with a wide spectrum of applications across many disciplines, such as social media and healthcare. Examples of applications include finding groups of users in social networks (e.g., Facebook), which is useful for a personalized recommendation, and detecting drug-drug interactions, which may cause dangerous side effects on health. In graph mining, many useful methods can be applied to small graphs effectively. However, the ever-increasing size of real-world networks is a major challenge for these methods due to their high computational and space costs. This project aims at developing novel graph compression (summarization) methodologies that facilitate efficient analysis of large graphs and advancing a wide spectrum of graph-related applications. Graph compression aims to create a smaller graph from a massive graph. Compressing graphs achieves several benefits, including but not limited to 1) significant speed-up for current graph mining algorithms, 2) memory space and communication cost reduction, 3) improved data privacy, 4) more effective graph visualization. This project will provide research opportunities to graduate students, especially female and underrepresented students, in graph mining and its real-life applications. The PI will also incorporate the results of the research in undergraduate and graduate-level courses.Graph compression algorithms reduce the complexity and size of large graphs while maintaining the crucial information of the original graph in the smaller graph. Such reductions are essential to scale up or scale out existing algorithms to better manage, query, store, and display them. The investigator will design graph compression methods that preserve the desired structural information of graphs, including similarity and cohesiveness, specific to the selected graph mining problems. This project will: 1) explore the spatial locality property of graphs by taking the structural information from different aspects, including similarity of nodes and cohesiveness of subgraphs; 2) develop the corresponding novel structure-aware compression methods to tackle the challenges brought by large real-world networks; and 3) build more tailored architectures with proposed compression methods for various problems, including network embedding and community search and evaluate them on real-world applications such as link prediction, node classification, anomaly detection, and community detection. Its outcomes will be disseminated through publications, tutorials, workshops, as well as open-source tools, code, and datasets.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.

Graph挖掘是一个新兴领域，在社交媒体和医疗保健等许多学科中具有广泛的应用。应用程序的示例包括在社交网络（例如Facebook）中查找用户组，这对于个性化的建议很有用，并检测药物 - 药物相互作用，这可能会对健康造成危险的副作用。在图挖掘中，许多有用的方法可以有效地应用于小图。但是，由于它们的高度计算和空间成本，现实世界网络的尺寸不断增加，这是这些方法的主要挑战。该项目旨在开发新的图形压缩（摘要）方法，以促进大图的有效分析并推进各种与图形相关的应用。图形压缩旨在从大图创建较小的图形。压缩图可实现多个好处，包括但不限于1）当前图挖掘算法的速度显着，2）记忆空间和通信成本降低，3）改进的数据隐私，4）更有效的图形可视化。该项目将为研究生，尤其是女性和代表性不足的学生提供研究机会。 PI还将在本科和研究生级课程中结合研究结果。图形压缩算法降低了大图的复杂性和大小，同时将原始图的关键信息保持在较小的图中。此类减少对于扩大或扩展现有算法以更好地管理，查询，存储和显示它们至关重要。研究者将设计图形压缩方法，以保留图形所需的结构信息，包括相似性和凝聚力，特定于所选的图挖掘问题。该项目将：1）通过从不同方面获取结构信息，包括节点的相似性和子图的凝聚力来探索图的空间位置属性； 2）开发相应的新型结构感知压缩方法，以应对大型现实世界网络带来的挑战； 3）通过提议的压缩方法来建立更多量身定制的体系结构，以解决各种问题，包括网络嵌入和社区搜索，并在现实世界中对其进行评估，例如链接预测，节点分类，异常检测和社区检测。它的结果将通过出版物，教程，研讨会以及开源工具，代码和数据集进行传播。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的智力优点和更广泛影响的审查标准通过评估来获得支持的。