Fast computation of the first discrete homology group

2025/12/15 by Jacob Ender, Ender, Jacob, Chris Kapulkin +1
Computer Science · Mathematics · #Topological and Geometric Data Analysis #Advanced Graph Neural Networks #Geometric and Algebraic Topology

paper · pdf · doi:10.48550/arxiv.2512.13929

Abstract

We present a new algorithm for computing the first discrete homology group of a graph. By testing the algorithm on different data sets of random graphs, we find that it significantly outperforms other known algorithms.

Citations

• Biclosed monoidal structures on the categories of digraphs and graphs
• On the homology of simplicial and cubical sets with symmetries
• Data analysis using discrete cubical homology
• Faster computations of discrete homology
• Closed symmetric monoidal structures on the category of graphs
• Listing 4-Cycles
• Cubical setting for discrete homotopy theory, revisited
• On the vanishing of discrete singular cubical homology for graphs
• Homology groups of cubical sets with connections
• Discrete Cubical and Path Homologies of Graphs
• A Homotopy Theory for Graphs

Related

• Faster computations of discrete homology
• Computing eulerian magnitude homology
• Graph homology computations
• The first uniformly finite homology group with coefficients in ℤ and a characterisation of its vanishing in the transitive case
• A Homology Theory of Graphs: First Homology Group of Hamiltonian Graphs