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.

图挖掘是一个新兴领域，在许多学科中有着广泛的应用，例如社交媒体和医疗保健。应用的示例包括在社交网络（例如，Facebook），这是有用的个性化推荐，并检测药物之间的相互作用，这可能会对健康造成危险的副作用。在图挖掘中，许多有用的方法可以有效地应用于小图。然而，现实世界的网络规模不断增加是一个重大的挑战，这些方法由于其高计算和空间成本。该项目旨在开发新的图压缩（摘要）方法，以促进大型图的有效分析，并推进广泛的图相关应用。图压缩的目的是从一个巨大的图创建一个更小的图。压缩图实现了若干益处，包括但不限于1）当前图挖掘算法的显著加速，2）存储器空间和通信成本降低，3）改进的数据隐私，4）更有效的图可视化。该项目将为研究生，特别是女性和代表性不足的学生，在图挖掘及其现实生活中的应用提供研究机会。PI还将在本科和研究生课程中纳入研究成果。图压缩算法降低了大型图的复杂性和大小，同时在较小的图中保留了原始图的关键信息。这种缩减对于扩大或扩展现有算法以更好地管理、查询、存储和显示它们至关重要。研究人员将设计图压缩方法，保留所需的图的结构信息，包括相似性和凝聚力，具体到选定的图挖掘问题。该项目将：1）从不同角度提取图的结构信息，包括节点的相似性和子图的内聚性，探索图的空间局部性; 2）开发相应的新的结构感知压缩方法，以应对大型现实网络带来的挑战;以及3）利用针对各种问题提出的压缩方法构建更适合的体系结构，包括网络嵌入和社区搜索，并评估它们在现实世界中的应用，如链接预测，节点分类，异常检测和社区检测。其成果将通过出版物、教程、研讨会以及开源工具、代码和数据集传播。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。