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

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

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.