A directed persistent homology theory for dissimilarity functions

David Méndez, Rubén J. Sánchez-García

Abstract

We develop a theory of persistent homology for directed simplicial complexes which detects persistent directed cycles in odd dimensions. We relate directed persistent homology to classical persistent homology, prove some stability results, and discuss the computational challenges of our approach. Our directed persistent homology theory is motivated by homology with semiring coefficients: by explicitly removing additive inverses, we are able to detect directed cycles algebraically.

TL;DR

Standard persistent homology is "direction-blind," often failing to distinguish between a directed circuit and a random collection of edges. This paper introduces a new directed persistent homology theory that uses semiring-inspired algebra to detect directed cycles in asymmetric data, proving that the resulting "directed barcodes" are mathematically stable and robust for real-world data analysis.

The Challenge of Directionality in TDA

Topological Data Analysis (TDA), specifically persistent homology (PH), has become a powerhouse for finding "holes" in high-dimensional data. However, standard PH has a major blind spot: directionality.

In many real-world systems—like neural pathways, protein-protein interactions, or temporal trade networks—the relationship between A and B is not the same as the relationship between B and A. Standard homology relies on coefficient rings (like integers or field coefficients) where every element has an additive inverse ($1 + (-1) = 0$). This algebraic property causes directed information to "cancel out," making it impossible to distinguish a true directed cycle ($A \to B \to C \to A$) from an undirected one.

Distinguishing between a directed acyclic graph (left) and a directed cycle (right).

The authors aim to bridge this gap by creating a homology theory that respects the "one-way" nature of directed networks, allowing researchers to differentiate between simple connectivity and structured flow.

Methodology: Semirings and Directed Complexes

The authors develop their theory through several key innovations:

  1. Directed Simplicial Complexes: Unlike standard complexes, these are built from ordered tuples of vertices and allow for vertex repetitions. This allows the structure to encode the "flow" of information.
  2. Directed Homology Modules: The core innovation is defining a submodule of homology generated specifically by directed cycles—cycles where all elementary chains have non-negative coefficients.
  3. Semiring Motivation: The theory is mathematically grounded in homology with semiring coefficients (like the natural numbers $\mathbb{N}$ or non-negative reals $\mathbb{R}^+$). Because semirings lack additive inverses, the algebra is forced to preserve the directionality of the cycles rather than letting them cancel out.

The Persistence Pipeline

To apply this to data, the authors define a "directed Rips filtration" for dissimilarity functions (asymmetric distance measures). This produces two sets of barcodes: one for the standard (undirected) homology and one for the new directed homology.

A directed Rips filtration and the resulting persistence barcodes.

This framework works on any finite set $V$ with an arbitrary function $d_V: V \times V \to \mathbb{R}$, which serves as a generalized, asymmetric distance matrix. Synthetic directed graphs are used to demonstrate how the theory distinguishes between directed and undirected cycles as the filtration threshold increases.

Key Insights: Birth, Death, and Dimensions

  • The "Inverse" Problem: The "aha moment" is realizing that the inability to see direction is an algebraic choice. By explicitly removing additive inverses, you force the math to "see" the direction of the flow.
  • Birth vs. Death: A directed cycle is, by definition, also an undirected cycle. Therefore, every bar in a directed barcode can be matched to a bar in the undirected one. Crucially, the directed bar is often born later (it takes more "time" for a cycle to become directed) but they die at the same time.
  • The Odd-Dimension Rule: The authors prove that directed homology is primarily useful for detecting cycles in odd dimensions (like 1D loops). In even dimensions (above 0), directed homology actually becomes trivial (zero), which is a surprising structural property of the theory.

Stability and Computational Results

  • Stability Theorem (Thm 4.19): The authors prove that their directed persistent homology is stable. If you slightly perturb the input data (the dissimilarity function), the resulting directed persistence diagram only changes slightly. This is critical for ensuring the theory works on noisy, real-world data.
  • Matching Proposition (Prop 4.7): They establish a formal injective matching between directed and undirected barcodes, providing a clear way to interpret directed features as "specialized" versions of standard topological features.
  • Computational Mapping: The paper identifies that computing these directed cycles is equivalent to the extreme ray enumeration problem in polyhedral geometry.

Limitations and Future Directions

While promising, the approach faces significant computational complexity. Finding directed cycles is much harder than standard PH; the "double description algorithm" used for extreme ray enumeration is computationally expensive and may struggle with very large datasets. Additionally, the theory currently provides no information for even dimensions ($>0$). Future work should focus on developing algorithms that compute directed homology classes directly, rather than enumerating all possible directed cycles, to improve scalability.

Summary updated

Abstract

We develop a theory of persistent homology for directed simplicial complexes which detects persistent directed cycles in odd dimensions. We relate directed persistent homology to classical persistent homology, prove some stability results, and discuss the computational challenges of our approach. Our directed persistent homology theory is motivated by homology with semiring coefficients: by explicitly removing additive inverses, we are able to detect directed cycles algebraically.
BibTeX
@article{mendez2023directed,
  author = {David Méndez and Rubén J. Sánchez-García},
  title = {{A directed persistent homology theory for dissimilarity functions}},
  journal = {Journal of Applied and Computational Topology},
  year = {2023},
  doi = {10.1007/s41468-023-00124-x},
}
Figure