Topological Spatial Graph Coarsening
Anna Calissano, Etienne Lasalle · 2025
Read Topological Spatial Graph Coarsening by Anna Calissano, Etienne Lasalle (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2512-24327.txt.
Introduction
Anna Calissano and Etienne Lasalle shrink spatial graphs without flattening their shape. Spatial graphs have nodes placed in space. Transit networks, molecules, and branching structures in biology are examples. Reduction should keep the overall structure with fewer nodes. Shape matters here, because position carries meaning.
Their method collapses short edges step by step. A new filtration captures the shape features that set how far to reduce. It adapts persistent diagrams, built for point clouds, to spatial graphs. The filtration is triangle-aware. The method needs no parameters to tune. It is provably unchanged when the input is rotated, moved, or scaled. Tests used synthetic and real spatial graphs. Sizes fell a great deal under the reduction. The key shape features survived intact.
Catalog record
| CREATOR | Anna Calissano, Etienne Lasalle |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 53 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2512-24327
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Topological Spatial Graph Coarsening Anna Calissano, Etienne Lasalle Abstract 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. keywords Spatial graphs, Graph reduction, Coarsening, Topological data analysis 1 Introduction Spatial graphs are a specific type of graphs with spatial attributes associated to the nodes and edges. They are studied in different applicative context and called with various names. In transport analysis, social network analysis, and epidemiology, they are often referred to as spatial networks ( 6 ; 22 ; 17 ) . Spatial graphs are also closely linked to geometric graphs — which are graphs whose nodes lie in Euclidean space and whose edges are (possibly intersecting) straight lines ( 12 ) . When edges may instead be continuous curves, the structure is known as a topological or metric graph ( 35 ) . Geometric, topological, and metric graphs are extensively studied within graph theory, which explores the possible configurations of a graph with a given number of nodes and constraints on edges; see 37 ; 36 for historical and technical perspectives. Finally, spatial graphs can also be viewed as simplified forms of shape or elastic graphs, where actual shapes are encoded along the edges ( 23 ) . When working with such graph, a common problem is dimensionality as the graphs have a high number of nodes and edges. Airways in the lungs or neurons networks are common real world examples displaying high dimensionality. The problem of decreasing the graph complexity has been studied in the network analysis literature under the name of graph sparsification or graph coarsening (see 24 for a recent overview of the field). Graph sparsification consists in selecting only a subset of nodes and edges ( 3 ) , while graph coarsening consists in grouping the nodes into super-nodes and edges into super-edges using aggregation algorithms ( 32 ) . In this paper, we propose a way to simplify a spatial graph by preserving its topology. We want to preserve the principal graph structure (connected components, large cycles) while removing small and noisy graph components. The principal adjective recalls the principal component analysis as our method is similarly trying to capture the characteristics of the graph which retain the majority of the information. We propose a spatial graph coarsening procedure which is topologically informed - here called Topological Spatial Graph Coarsening . To the best of our knowledge, the proposed method is new in the literature and addresses the open challenge in many real world applications of working with graphs with lower number of nodes. To define a dimensionality reduction procedure which is topologically informed, we need to estimate the topological properties of the spatial graphs. We leverage tools from Topological Data Analysis (TDA) ( 15 ) . Taking its root in the field of algebraic topology, TDA is a recent and promising domain that provides well-founded tools to analyze complex data - such as graphs - for which topological properties represent key insights into understanding the data. Here, by topology we refer to the properties left unchanged by continuous deformations such as rotation, translation, stretching, and bending ( e.g. , number of connected components or holes). A common tool in TDA is the persistent diagram, which is classically used to study the topology of point clouds in \mathbb{R}^{p} - see seminal works by ( 19 ; 10 ; 2 ) . As for point clouds, some attempt have been done to adapt classic filtration to graph data ( 4 ; 31 ; 20 ) . For example, a graph filtration can be defined based on the node degree ( 25 ) , the Jaccard index and Ricci curvature ( 39 ) , or the Heat Kernel ( 11 ; 29 ) . As our graphs have a spatial component, we define a new filtration which is based on both the spatial and the structural information. We name it the triangle-aware graph filtration as it captures cycles information generated by all cycles, even the one induced by triangles in the graph. Given the topological characterization, we can now propose a coarsening procedure for spatial graphs. The new graph preserve the most important topological features of the original graph -measured via our filtration and persistent diagram - with a lower number of nodes and edges. As for any dimensionality reduction technique, we would like to calibrate the reduction level, as too much reduction would yield to an oversimplified graph with missing important features, and too little reduction would not provide a significant and useful coarsening. We define a score to guide the choice of an appropriate reduction level. This score balances the reduced graph complexity with the amount of topological “distortion” between the original and reduced graph evaluated by comparing persistence diagrams. Minimizing this score allows to calibrate the reduction level. The paper is organized as follow. In Section 2 , we introduce the spatial graph object and the coarsening procedure. In Section 3 , we recall how to compute classical persistence diagrams and we introduce the persistence diagram adaptation for spatial graphs (Subsection 3.2 ). In Section 4 , we define the topologically informed spatial graph coarsening. As the new methodology is tailored for spatial graphs, we study the invariance and equivariance properties of the method with respect to rotation, translation and scaling of the node positions; see Section 5 . In Section 6 , we showcase the proposed method on simulated data and on a real world dataset of fungi networks ( 21 ) . 2 Spatial Graph Coarsening Consider a spatial graph G consisting of a set of nodes V=\{v_{1},\dots,v_{n}\} and a set of edges E\in V\times V . In a spatial graph, each node is equipped with spatial positions (X_{u})_{u\in V} , where x_{u}\in\mathbb{R}^{p} for all nodes u , with p being the dimension of the space. The spatial graph is denoted by the triplet G=(V,E,X) . In this work, the nodes are embedded in \mathbb{R}^{p} where p=2,3 and equipped with Euclidean distance. For