通过拓扑保持的图简化方法,高效压缩空间图结构。
Topological Spatial Graph Coarsening
- 基于三角感知过滤器构建拓扑描述符,捕捉空间图特征。
- 无需参数调节,可减少图节点数并保留关键拓扑结构。
- 适用于交通网络、分子结构等需保持几何拓扑的应用。
空间图是节点在空间中具有定位信息的特殊图结构(如公共交通网络、分子结构、生物分支系统)。本文研究空间图简化问题,旨在生成节点更少但整体结构保持不变的简化图。为在压缩过程中保留原始图的核心拓扑特性,提出一种基于新框架的拓扑空间图粗化方法。该方法通过合并短边实现图的简化,并引入名为“三角感知图滤波”的新构造方式,将经典点云拓扑描述子(持久性图)适配至空间图。所提方法无需参数调节,且在初始空间图的旋转、平移和缩放变换下保持不变性。在合成与真实空间图上评估表明,该方法能显著降低图规模,同时有效保留重要拓扑信息。
原文摘要 · Abstract (English)
Spatial graphs are particular graphs for which the nodes are localized in space (e.g., public transport network, molecules, branching biological structures). In this work, we consider the problem of spatial graph reduction, that aims to find a smaller spatial graph (i.e., with less nodes) with the same overall structure as the initial one. In this context, performing the graph reduction while preserving the main topological features of the initial graph is particularly relevant, due to the additional spatial information. Thus, we propose a topological spatial graph coarsening approach based on a new framework that finds a trade-off between the graph reduction and the preservation of the topological characteristics. The coarsening is realized by collapsing short edges. In order to capture the topological information required to calibrate the reduction level, we adapt the construction of classical topological descriptors made for point clouds (the so-called persistent diagrams) to spatial graphs. This construction relies on the introduction of a new filtration called triangle-aware graph filtration. Our coarsening approach is parameter-free and we prove that it is equivariant under rotations, translations and scaling of the initial spatial graph. We evaluate the performances of our method on synthetic and real spatial graphs, and show that it significantly reduces the graph sizes while preserving the relevant topological information.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。