pith. sign in

arxiv: 1906.10458 · v1 · pith:JGTB6I7Knew · submitted 2019-06-25 · 🧮 math.AT · q-bio.NC

Computing persistent homology of directed flag complexes

Daniel Luetgehetmann , Dejan Govc , Jason Smith , Ran Levi This is my paper

Pith reviewed 2026-05-25 15:59 UTC · model grok-4.3

classification 🧮 math.AT q-bio.NC
keywords persistent homologydirected flag complexFlagserdirected graphscomputational topologybrain microcircuitryRipserhomology computation
0
0 comments X

The pith

Flagser constructs directed flag complexes from graphs and computes their persistent homology with parallel and approximate modes.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents Flagser, a package that builds the directed flag complex of any finite directed graph and then calculates persistent homology under user-chosen filtrations on either the graph or the complex. The homology engine extends Ripser with changes aimed at large-scale runs, while the complex construction is written to run in parallel across any number of cores. An optional approximate mode trades a controlled amount of precision for shorter run times. The authors test the package on brain-circuit reconstructions and other graph collections, recording hardware, memory use, and wall-clock time for each case.

Core claim

Flagser constructs the directed flag complex of a finite directed graph and computes 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 optimized specifically for large computations. The construction of the directed flag complex is done in a way that allows easy parallelization by arbitrarily many cores. Flagser also has the option of working with undirected graphs and an Approximate option that shortens compute time with high accuracy.

What carries the argument

Flagser, the package that builds directed flag complexes from graphs and runs persistent homology on them.

If this is right

  • Homology calculations become feasible on directed graphs too large for earlier tools.
  • Parallel construction removes a serial bottleneck when building the complex.
  • The approximate mode yields usable results on data sets where exact runs would exceed available time or memory.
  • Both directed and undirected graphs can be processed within the same framework.
  • Performance metrics are recorded for every run, allowing direct comparison across data sets.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same parallel-construction pattern could be reused for other simplicial complexes built from graphs.
  • Accuracy of the approximate mode could be measured systematically on benchmark graphs with known answers.
  • Flagser output could serve as input to downstream analyses that combine topology with graph statistics.
  • The package's design suggests a template for adding directed versions to other persistent-homology libraries.

Load-bearing premise

The optimizations for parallelization and approximation preserve the exact mathematical correctness of the persistent homology output.

What would settle it

Take a small directed graph whose persistent homology is already known from an independent, verified implementation and check whether Flagser returns the identical barcodes.

Figures

Figures reproduced from arXiv: 1906.10458 by Daniel Luetgehetmann, Dejan Govc, Jason Smith, Ran Levi.

Figure 1
Figure 1. Figure 1: Theoretical and actual error in the computation of the first Betti number by skipping the reduction of columns that require certain numbers of reduction steps. The cell counts are 4656, 35587 and 1485099 in dimensions 0, 1 and 2 respectively, and the first Betti number is 3321. The computations were made as averages over ten runs on a MacBook Pro, 2.5 GHz Intel Core i7 [PITH_FULL_IMAGE:figures/full_fig_p0… view at source ↗
Figure 2
Figure 2. Figure 2: A digraph for which using apparent pairs to compute the ho￾mology of the directed flag complex gives the wrong results. same filtration value. Each index can appear multiple times in this queue, but due to the sorting all repetitions are next to each other in a contiguous block. To determine the final entries of the column after the reduction process, one has to loop over the whole queue and sum the coeffi… view at source ↗
Figure 3
Figure 3. Figure 3: Performance of Flagser on a variety of datasets: BE = Wind￾surfers, GP = Google+, IN = Infectious, JA = Jazz, MQ = Macaques, PR = Protein, FN = 40cycle19, BB = Blue Brain Project neocortical column, BA = Barabasi-Albert Graph, CE = C-Elegans, ER = Erdős-Rényi Graph. In the table above, the dagger symbol on the dataset abbreviation means that the approximate function of Flagser was used with approximation p… view at source ↗
Figure 4
Figure 4. Figure 4: Performance of Flagser computing persistence. The last five datasets are: 19th step of the Rips filtration of the 40-cycle graph (equipped with the graph metric), a sample of a Blue Brain Project reconstruction of the neocortical column or a rat [RNS+17], an Erdős-Rényi graph with a similar number of vertices and connection probability as such a network, a C. Elegans brain network [VCP+11] (Link 9.4) and a… view at source ↗
Figure 5
Figure 5. Figure 5: Performance of Flagser on the Blue Brain Project graph with respect to different values of the Approximate parameter. The Betti num￾bers computed are an approximation to the true Betti numbers. See [PITH_FULL_IMAGE:figures/full_fig_p010_5.png] view at source ↗
Figure 6
Figure 6. Figure 6: Number of skipped columns of the coboundary matrix for the Blue Brain Project graph with respect to different values of the Approxi￾mate parameter. The approximation accuracy of βi depends theoretically on the number of columns skipped in the coboundary matrices for δi−1 and δi . Consider for example β4. By Figures 5 and 6 the true value is β4 = 9821, since in that case no columns are skipped in δ3 and δ4.… view at source ↗
Figure 7
Figure 7. Figure 7: Trajectories of β2 and β3 as a function of the approximation parameter. A change in order of magnitude in the approximation parameter results in a small change in the Betti number computed. Approx. Time Memory β0 β1 β2 β3 1 4m45s 3.25GB 1 19,675 14,675,052 40 10 4m31s 3.10GB 1 19,981 9,204,135 4 100 4m44s 3.18GB 1 19,981 8,074,149 4 1000 5m48s 3.33GB 1 19,981 7,921,730 4 10000 14m18s 3.72GB 1 19,982 7,876,… view at source ↗
Figure 8
Figure 8. Figure 8: Performance of Flagser on an Erdős-Rényi graph with respect to different values of the Approximate parameter. The Betti numbers range from dimension 0 to dimension 3. Approx. δ1 δ2 δ3 1 7,692,010 719,041 124 10 1,501,909 3 0 100 371,920 0 0 1000 219,501 0 0 10000 174,628 0 0 100000 155,685 0 0 [PITH_FULL_IMAGE:figures/full_fig_p011_8.png] view at source ↗
Figure 9
Figure 9. Figure 9: Number of skipped columns of the coboundary matrix for an Erdős-Rényi graph with respect to different values of the Approximate pa￾rameter in dimensions from 1 to 3. of the full neocortex of a mouse ( [PITH_FULL_IMAGE:figures/full_fig_p011_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: Cell count in the Blue Brain reconstruction of the somatosen￾sory cortex. Computation was run on an HPC cluster using 256 CPUs, required 55.69GB of memory and took 7.5 hours to complete [PITH_FULL_IMAGE:figures/full_fig_p012_10.png] view at source ↗
Figure 11
Figure 11. Figure 11: The simplex count for the PL-Left region of a mouse neocortex (local connections only). The complex is 21-dimensional with more than 1.2 trillion 11-dimensional simplices. Computation was run in parallel on two nodes of an HPC cluster with 256 CPUs each, required 1GB of memory and took 5 days to complete (run as 10 different jobs of 24 hours each). probability of connection is roughly half. Hence we expec… view at source ↗
Figure 12
Figure 12. Figure 12: Four large datasets taken from the Koblenz Network Collec￾tion (Link 9.8). (a) Social network of YouTube users and their friendship connections, (b) Friendship data of Facebook users, (c) Road network of the State of Texas, a node is an intersection between roads or road end￾point and edges are road segments and (d) Road network of the State of California. All computations were carried out on an HPC clust… view at source ↗
read the original 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 [Bau18a], but is optimized specifically for large computations. The construction of the directed flag complex is done in a way that allows easy parallelization 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The manuscript introduces the Flagser package for constructing directed flag complexes from directed graphs and computing their persistent homology using an optimized version of Ripser. It includes features for parallel construction, support for undirected graphs, and an Approximate option for faster computations. The package is demonstrated on brain microcircuit data from the Blue Brain Project and other examples, with performance details provided.

Significance. If correct, this tool significantly advances the ability to compute persistent homology on directed structures, which is valuable for topological analysis in fields like neuroscience. The parallelization and approximation features make it practical for large-scale data, and the demonstrations provide evidence of its applicability.

major comments (2)
  1. [Abstract] The parallelization of the directed flag complex construction and the Approximate option are presented without any cross-validation against Ripser or error analysis on small cases, which is necessary to ensure mathematical correctness of the outputs.
  2. [Performance analysis section] The performance analysis on various data collections does not include comparisons of the approximate homology results to exact ones, leaving the 'remarkable accuracy' claim unsubstantiated.
minor comments (1)
  1. Some data collections are referred to as 'several other examples' without explicit listing in the abstract.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful review and constructive feedback on the validation of Flagser's features. We address the major comments point by point below and will revise the manuscript to incorporate the requested analyses.

read point-by-point responses

  1. Referee: [Abstract] The parallelization of the directed flag complex construction and the Approximate option are presented without any cross-validation against Ripser or error analysis on small cases, which is necessary to ensure mathematical correctness of the outputs.

    Authors: We agree that explicit validation strengthens the claims. The parallel construction divides the enumeration of simplices into independent subtasks that preserve the exact mathematical output of the sequential algorithm; we will add a short cross-validation subsection comparing parallel and sequential runs on small directed graphs. For the Approximate option, we will include error analysis on small cases by directly comparing approximate persistence diagrams and Betti numbers against exact results from Ripser, reporting any discrepancies. revision: yes

  2. Referee: [Performance analysis section] The performance analysis on various data collections does not include comparisons of the approximate homology results to exact ones, leaving the 'remarkable accuracy' claim unsubstantiated.

    Authors: This observation is correct. The manuscript currently lacks such direct comparisons, which leaves the accuracy claim without quantitative support. We will revise the performance analysis section to add comparisons on feasible subsets of the data collections (and on additional small benchmark graphs), reporting agreement metrics between approximate and exact homology outputs to substantiate the claim. revision: yes

Circularity Check

0 steps flagged

No circularity: software tool description with external base implementation

full rationale

The manuscript describes the Flagser package for constructing directed flag complexes and computing persistent homology, explicitly stating that the homology computation is based on the external program Ripser [Bau18a]. No mathematical derivations, predictions, fitted parameters, or first-principles results are claimed. There are no equations, self-definitions, or load-bearing self-citations that reduce any output to the paper's own inputs by construction. Performance claims rest on reported runs on external datasets (brain reconstructions, etc.) rather than any internal loop. The paper is self-contained as an implementation report against the cited external baseline.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper contributes a computational implementation rather than new mathematical axioms or entities; it builds on standard concepts from topology.

axioms (1)
  • standard math The mathematical foundations of persistent homology and flag complexes as defined in algebraic topology.
    The computations rely on established definitions from the field.

pith-pipeline@v0.9.0 · 5711 in / 1085 out tokens · 29515 ms · 2026-05-25T15:59:30.767403+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

13 extracted references · 13 canonical work pages

  1. [1]

    Ripser: a lean C ++ code for the computation of V ietoris- R ips persistence barcodes

    Ulrich Bauer. Ripser: a lean C ++ code for the computation of V ietoris- R ips persistence barcodes. http://ripser.org, 2015-2018. Accessed: 29-08-2018

    work page 2015

  2. [2]

    Ripser: Efficient computation of vietoris–rips persistence barcodes

    Ulrich Bauer. Ripser: Efficient computation of vietoris–rips persistence barcodes. http://ulrich-bauer.org/ripser-talk.pdf, 2018. Accessed: 29-08-2018

    work page 2018

  3. [3]

    Phat -- persistent homology algorithms toolbox

    Ulrich Bauer, Michael Kerber, Jan Reininghaus, and Hubert Wagner. Phat -- persistent homology algorithms toolbox. Journal of Symbolic Computation , 78:76 -- 90, 2017. Algorithms and Software for Computational Topology

    work page 2017

  4. [4]

    Costa and M

    A. Costa and M. Farber. Large random simplicial complexes, I . J. Topol. Anal. , 8(3):399--429, 2016

    work page 2016

  5. [5]

    Persistent homology---a survey

    Herbert Edelsbrunner and John Harer. Persistent homology---a survey. In Surveys on discrete and computational geometry , volume 453 of Contemp. Math. , pages 257--282. Amer. Math. Soc., Providence, RI, 2008

    work page 2008

  6. [6]

    Morse theory for cell complexes

    Robin Forman. Morse theory for cell complexes. Advances in Mathematics , 134(1):90 -- 145, 1998

    work page 1998

  7. [7]

    Algebraic topology

    Allen Hatcher . Algebraic topology. Cambridge: Cambridge University Press, 2002

    work page 2002

  8. [8]

    The Gudhi Library: Simplicial Complexes and Persistent Homology

    Cl \'e ment Maria, Jean-Daniel Boissonnat, Marc Glisse, and Mariette Yvinec. The Gudhi Library: Simplicial Complexes and Persistent Homology . Research Report RR-8548, INRIA , June 2014

    work page 2014

  9. [9]

    James R. Munkres. Elements of algebraic topology . Addison-Wesley, 1984

    work page 1984

  10. [10]

    Reimann, Max Nolte, Martina Scolamiero, Katharine Turner, Rodrigo Perin, Giuseppe Chindemi, Pawe D otko, Ran Levi, Kathryn Hess, and Henry Markram

    Michael W. Reimann, Max Nolte, Martina Scolamiero, Katharine Turner, Rodrigo Perin, Giuseppe Chindemi, Pawe D otko, Ran Levi, Kathryn Hess, and Henry Markram. Cliques of neurons bound into cavities provide a missing link between structure and function. Frontiers in Computational Neuroscience , 11:48, 2017

    work page 2017

  11. [11]

    Hierarchical spectral clustering of power grids

    Ruben J Sanchez-Garcia, Max Fennelly, Sean Norris, Nick Wright, Graham Niblo, Jacek Brodzki, and Janusz W Bialek. Hierarchical spectral clustering of power grids. IEEE Transactions on Power Systems , 29(5):2229--2237, 2014

    work page 2014

  12. [12]

    Varshney, Beth L

    Lav R. Varshney, Beth L. Chen, Eric Paniagua, David H. Hall, and Dmitri B. Chklovskii. Structural properties of the caenorhabditis elegans neuronal network. PLoS Computational Biology , 7(2), 2011

    work page 2011

  13. [13]

    Yannakakis

    M. Yannakakis. Computing the minimum fill-in is np-complete. SIAM Journal on Algebraic Discrete Methods , 2(1):77--79, 1981

    work page 1981