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

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

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.