Computing Persistent Homology of Directed Flag Complexes

Daniel Luetgehetmann, Dejan Govc, Jason P. Smith, Ran LeviPreprints.org 2019 · DOI

Abstract

We present a new computing package Flagser, designed to construct the directed flag complex of a finite directed graph, and compute persistent homology for flexibly defined filtrations on the graph and the resulting complex. The persistent homology computation part of Flagser is based on the program Ripser, but is optimised specifically for large computations. The construction of the directed flag complex is done in a way that allows easy parallelisation by arbitrarily many cores. Flagser also has the option of working with undirected graphs. For homology computations Flagser has an Approximate option, which shortens compute time with remarkable accuracy. We demonstrate the power of Flagser by applying it to the construction of the directed flag complex of digital reconstructions of brain microcircuitry by the Blue Brain Project and several other examples. In some instances we perform computation of homology. For a more complete performance analysis, we also apply Flagser to some other data collections. In all cases the hardware used in the computation, the use of memory and the compute time are recorded.

Introduction

In Topological Data Analysis (TDA), persistent homology is a powerful tool for finding "shape" in data. However, most existing tools are optimized for undirected data, such as point clouds. In neuroscience, researchers often study directed graphs representing neurons and their synaptic connections. The "directed flag complex" of such a graph is a collection of ordered cliques, which can grow exponentially in size.

A directed graph illustrating the basic structure used to build a directed flag complex.

For example, a small slice of a rat's brain might have 30,000 neurons and 8 million edges, resulting in tens of millions of higher-dimensional simplices. Standard TDA software often crashes due to memory exhaustion or takes weeks to run because it tries to store the entire complex in RAM. Flagser is a high-performance software package designed to overcome these hurdles, enabling the processing of massive datasets—such as digital reconstructions of brain microcircuitry containing trillions of simplices—that were previously computationally unreachable.

Methodology

Flagser builds upon the foundations of Ripser but introduces several critical optimizations for the directed case:

  • On-the-fly Construction: Instead of building and storing the entire simplicial complex in memory, Flagser generates simplices as needed. This keeps the memory footprint limited primarily to the original graph's adjacency matrix.
  • Bitset Optimization: The adjacency matrix is stored as bitsets. Finding a new simplex involves calculating the intersection of vertex neighborhoods using fast bitwise "AND" operations.
  • Cohomology and Matrix Reduction: Flagser computes cohomology rather than homology. It uses a four-step heuristic to sort columns, ensuring the reduction process stays sparse and efficient.
  • Approximate Computation: Users can set a limit on the number of reduction steps per column. If a column is too "heavy," Flagser skips it. This provides a massive speedup with a theoretically bounded error.
  • Dynamic Priority Queues: To handle "long" columns during matrix reduction, Flagser dynamically switches from a standard priority queue to a hash-based approach to avoid performance bottlenecks.

Experimental Evaluation

The authors evaluated Flagser on a diverse array of real-world and synthetic datasets, including digital reconstructions from the Blue Brain Project, social networks (YouTube, Facebook), and infrastructure maps (Texas/California road networks).

Key results include:

  • Scale: Using 256 CPUs on an HPC cluster, Flagser successfully processed a mouse neocortex model containing 1.2 trillion simplices in 5 days.
  • Speed: Flagser can construct the directed flag complex of a rat neocortical column on a standard laptop in under 30 seconds.
  • Memory Efficiency: By avoiding explicit storage of the complex, Flagser can run on a 16GB RAM laptop for datasets that would normally require hundreds of gigabytes.
Performance and error metrics for the approximation mode, showing significant speedups with minimal actual error.

As shown in the table above, the approximation heuristic is surprisingly robust. In one test on a Blue Brain Project graph, computation time dropped from 113 seconds to 39 seconds while maintaining a high degree of accuracy. The "actual error" in the Betti numbers was often orders of magnitude smaller than the "theoretical maximum error."

Discussion

A key insight from this work is the "Directed Penalty." The authors discovered that "apparent pairs"—a common optimization in Ripser—cannot be used for directed flag complexes because they are semi-simplicial rather than simplicial. Standard discrete Morse theory rules do not apply, and using them would lead to incorrect results.

Furthermore, the research highlights the difference between structural complexity and size. A random graph and a brain microcircuit with the same number of vertices and edges behave very differently. The brain model is much more "topologically complex," producing far more simplices and requiring more compute power, highlighting the unique structural properties of biological networks.

Limitations and Future Work

While the approximation mode works well, it is currently difficult to predict the exact error margin before running the computation; the theoretical error bound is often too conservative. Additionally, the lack of "apparent pairs" for directed graphs remains a performance bottleneck. Finding a directed-safe version of this optimization is a priority for future development. Finally, while Flagser supports user-defined filtrations, expanding this to more complex, multi-parameter filtrations remains a goal for future versions.

Summary updated

Abstract

We present a new computing package Flagser, designed to construct the directed flag complex of a finite directed graph, and compute persistent homology for flexibly defined filtrations on the graph and the resulting complex. The persistent homology computation part of Flagser is based on the program Ripser [2], but is optimised specifically for large computations. The construction of the directed flag complex is done in a way that allows easy parallelisation by arbitrarily many cores. Flagser also has the option of working with undirected graphs. For homology computations Flagser has an Approximate option, which shortens compute time with remarkable accuracy. We demonstrate the power of Flagser by applying it to the construction of the directed flag complex of digital reconstructions of brain microcircuitry by the Blue Brain Project and several other examples. In some instances we perform computation of homology. For a more complete performance analysis, we also apply Flagser to some other data collections. In all cases the hardware used in the computation, the use of memory and the compute time are recorded.
BibTeX
@misc{luetgehetmann2019computing,
  author = {Daniel Luetgehetmann and Dejan Govc and Jason P. Smith and Ran Levi},
  title = {{Computing Persistent Homology of Directed Flag Complexes}},
  year = {2019},
  doi = {10.20944/preprints201911.0366.v1},
  howpublished = {Preprints.org},
}
Figure