基于最优传输几何的图粗化方法，提升大规模图的压缩效率与精度。
Gromov-Wasserstein Graph Coarsening
- 利用节点合并的扭曲度度量，迭代优化粗化过程。
- 在六个数据集上优于现有方法，尤其在不同参数下表现稳定。
- 适合需要高效图压缩的科研与工业场景。
我们研究了在Gromov-Wasserstein几何框架下的图粗化问题。提出两种新算法：贪心配对粗化（GPC）通过迭代合并局部扭曲最小的节点对实现粗化；$k$-均值贪心配对粗化（KGPC）则基于成对扭曲度进行聚类，直接合并节点簇。我们给出了方法达到最优粗化的条件，并在六个大规模数据集及下游聚类任务中验证性能。结果表明，所提方法在多种参数与场景下均显著优于现有方法。
原文摘要 · Abstract (English)
We study the problem of graph coarsening within the Gromov-Wasserstein geometry. Specifically, we propose two algorithms that leverage a novel representation of the distortion induced by merging pairs of nodes. The first method, termed Greedy Pair Coarsening (GPC), iteratively merges pairs of nodes that locally minimize a measure of distortion until the desired size is achieved. The second method, termed $k$-means Greedy Pair Coarsening (KGPC), leverages clustering based on pairwise distortion metrics to directly merge clusters of nodes. We provide conditions guaranteeing optimal coarsening for our methods and validate their performance on six large-scale datasets and a downstream clustering task. Results show that the proposed methods outperform existing approaches on a wide range of parameters and scenarios.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。