提出可自适应调整比例的异构图压缩方法，兼顾效率与语义一致性。
AH-UGC: Adaptive and Heterogeneous-Universal Graph Coarsening
- 结合局部敏感哈希与一致哈希实现自适应图粗化
- 在23个真实数据集上保持结构与语义完整性
- 首个支持自适应与异构图统一处理的框架，适合大规模图学习
图粗化（Graph Coarsening, GC）是一种重要的图压缩技术，用于提升大规模图的学习与推理效率。然而，现有方法每轮仅生成一个粗化图，更换粗化比例需重新计算，造成额外开销；且多数方法仅适用于同质图，难以满足异构图中多类型节点与边的语义约束。为此，本文提出一种新框架，融合局部敏感哈希（LSH）与一致哈希，实现自适应图粗化。通过哈希机制，方法天然具备高效与可扩展性。针对异构图，设计类型隔离粗化策略，强制同类型节点间合并，保障语义一致性。该方法是首个统一支持自适应与异构图粗化的框架。在23个真实数据集（涵盖同质、异质、同调、异调图）上的大量实验表明，该方法在保持原始图结构与语义完整性的前提下，显著提升可扩展性。
原文摘要 · Abstract (English)
$\textbf{Graph Coarsening (GC)}$ is a prominent graph reduction technique that compresses large graphs to enable efficient learning and inference. However, existing GC methods generate only one coarsened graph per run and must recompute from scratch for each new coarsening ratio, resulting in unnecessary overhead. Moreover, most prior approaches are tailored to $\textit{homogeneous}$ graphs and fail to accommodate the semantic constraints of $\textit{heterogeneous}$ graphs, which comprise multiple node and edge types. To overcome these limitations, we introduce a novel framework that combines Locality Sensitive Hashing (LSH) with Consistent Hashing to enable $\textit{adaptive graph coarsening}$. Leveraging hashing techniques, our method is inherently fast and scalable. For heterogeneous graphs, we propose a $\textit{type isolated coarsening}$ strategy that ensures semantic consistency by restricting merges to nodes of the same type. Our approach is the first unified framework to support both adaptive and heterogeneous coarsening. Extensive evaluations on 23 real-world datasets including homophilic, heterophilic, homogeneous, and heterogeneous graphs demonstrate that our method achieves superior scalability while preserving the structural and semantic integrity of the original graph.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。