Topological Spatial Graph Coarsening
Abstract
A spatial graph is a graph whose nodes and edges carry spatial attributes. It is a smart modelling choice for capturing the skeleton of a shape, a blood vessel network, a porous tissue, and many other data objects with intrinsically complex geometry, often resulting in graphs with a high node and edge count. In this talk, we introduce a topological spatial graph coarsening approach based on a new framework that balances graph reduction against the preservation of topological characteristics, essential for faithfully representing the underlying shape. 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 persistence diagrams) to spatial graphs. This relies on 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 performance of our method on synthetic and real spatial graphs and show that it significantly reduces the graph sizes while preserving the relevant topological information.