REVIEW 1 major objections 5 minor 29 references
Recursive Computation of Path Homology for Stratified Digraphs
T0 review · 1 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read The paper proves that full-depth path homology of a stratified digraph can be computed layer by layer through null-space recursions, without enumerating long paths.
desk verdict New recursive method for full-depth path homology of stratified digraphs; sound, well-tested, and a real practical advance, with the known caveat that full-depth depends on the chosen stratification. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the cycle space recursion of Theorem 4.3: a linear bijection $\phi_S$ between full-depth cycles on a subgraph layer and tuples $(v_x)_{x\in S^+}$ lying in the null space of $[A_{x_1},\dots,A_{x_{n_p}}]$, where $A_x$ expresses a basis of the predecessor-cycle space in a global basis of the previous level's cycle space. The recursion works by computing, for each vertex in the next layer, the null space of the submatrix that removes the coordinates not connected to that vertex; the new layer's cycle space is then the null space of the concatenated $A_x$'s. This turns a high-dimensional homology computation into repeated linear-algebra null-space computations, with an analytic shortcut when a vertex is connected to all vertices in the previous layer.
What would settle it
Take a small stratified digraph, compute $\beta_L$ with Algorithm 1 and with the general path-homology algorithm of [9], and compare; any mismatch would contradict Theorem 4.3. More sharply, construct a digraph that admits two layerings with different $L$, such as one obtained by adding an empty edge layer, and verify whether the recursion yields different results under the two layerings.
Extended reading notes
Core claim
The central claim is that over the real numbers, the full-depth cycle space of a stratified digraph $G$ with layers $K_0,\dots,K_L$ has a Markovian structure: every full-depth cycle decomposes uniquely as $\sum_{x\in K_L} \gamma_x x$, where each $\gamma_x$ is a cycle in the subgraph ending at $x$'s predecessors and the sum of the $\gamma_x$ is zero. Because there are no $L$-boundaries, the full-depth path homology $H_L(G)$ is exactly this cycle space. The paper encodes each $\gamma_x$ in a fixed basis of the previous cycle space by a matrix $A_x$, so the whole cycle space becomes the null space of the block matrix $[A_{x_1},\dots,A_{x_{n_p}}]$. Theorem 4.3 proves this cycle space recursion and shows that iterating it from $p=0$ to $p=L$ produces a basis of $H_L(G)$, giving the stated complexity bound and the experimental speedups.
Load-bearing premise
The load-bearing premise is that, over the real numbers and for a fixed stratification, every full-depth cycle has a unique zero-sum decomposition into predecessor cycles; if that uniqueness fails—for example under a different layer assignment or with coefficients admitting torsion—the recursion's output is no longer a well-defined invariant of the digraph.
Editorial extensions
If this is right
- Full-depth Betti numbers of deep stratified digraphs become computable in time governed by $|K_{p-1}||K_p|b_{p-1}^3$, rather than the general algorithm's $O(n^{6+3L})$.
- For an increasing filtration of stratified digraphs, full-depth homology classes are never destroyed, so persistent full-depth homology reduces to plotting $\beta_L(G_t)$ against the filtration threshold; the paper demonstrates this on weighted-edge filtrations.
- For any DAG with longest path length $\ell(G)$, the maximal path homology equals the full-depth homology of the subgraph $G^*$ spanned by longest paths, so the recursion computes it after an $O(|V|+|E|)$ pruning step.
- Tracking an explicit basis of cycle paths remains possible but slower; without tracking, the recursion can exploit dense layers analytically, making runtime decrease as edge density increases in some regimes.
Reading between the lines
- Going beyond the paper, the same null-space recursion could compute intermediate-dimensional cycle spaces of stratified digraphs by running the recursion up to a fixed $p<L$ and using the tracked basis of $\ker(\partial_p)$.
- Going beyond the paper, one could test whether a canonical longest-path layering makes $\beta_L$ a digraph invariant, addressing the paper's own remark that layerings are not unique.
- Going beyond the paper, extending the recursion to integer coefficients would require checking whether the unique-decomposition argument survives torsion; a small counterexample would settle it.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes a recursive algorithm to compute the full-depth reduced path homology of a stratified digraph, i.e., the homology in degree equal to the number of layers L. The main theoretical result (Theorem 4.3) shows that the full-depth cycle space of a stratified digraph can be obtained level by level: at each layer, the cycle space is the null space of a concatenated matrix whose blocks are coordinate-change matrices A_x for predecessor subgraphs. The algorithm is extended to maximal path homology of a DAG via Proposition 3.7, which constructs a stratified subgraph consisting of all longest paths. Experiments on random subgraphs of fully connected layered graphs compare runtime against the general path-homology algorithm [4] and report large speedups for deeper graphs, and the method is also applied to full-depth persistent homology.
Significance. If the technical content is correct, this is a useful contribution: it is, to my knowledge, the first algorithm specifically targeting high-dimensional path homology of stratified digraphs and feedforward networks, a regime where the general algorithm's O(n^{6+3p}) cost is prohibitive. The proofs are largely self-contained, the recursion is derived from the definitions rather than fitted, the code is open source, and the baseline is an external implementation. The main limitation, already acknowledged by the authors, is that 'full-depth' homology depends on the chosen stratification, so the algorithm's output is an invariant of the digraph together with its layer decomposition rather than of the underlying digraph alone. The complexity estimate, however, has a gap that needs repair before the theoretical efficiency claim can be accepted as stated.
major comments (1)
- [Section 5.1, complexity estimate] The inequality 'nrow(VKp−1) = P_{x∈K+_{p−1}} ncol(Ax) ≤ |Kp−1|bp−1' is not valid in general. For each x∈K_{p−1}^+, the matrix A_x is constructed from V_{K_{p−2}}, so ncol(A_x) ≤ b_{p−2}, and b_{p−2} can be much larger than b_{p−1}. For example, let L=3, K0={a1,...,am}, K1={u,v}, with a connected bipartite graph having m+2 edges (e.g., pred(u) and pred(v) of sizes about m/2 with a nonempty overlap). Then b0=m−1 and b1=1, while nrow(VK1) = (|pred(u)|−1)+(|pred(v)|−1) = m, so nrow(VK1) = m > |K1|b1 = 2. If K2 contains N vertices each connected only to u, then for each such vertex x, \tilde V_x has nrow about m/2 and ncol=1, so computing Basis(N(\tilde V_x)) costs Ω(m) per vertex; the stated bound O(|K1||K2|b1^3)=O(N) underestimates the true cost Ω(Nm) when N≫m. The complexity formula should be corrected (for example, to a bound involving b_{p−2}b_{p−1}^2 terms, up to base cases) or justified under additional hypotheses.
minor comments (5)
- [Section 3, Corollary 3.6] The proof of Corollary 3.6 is omitted for brevity, but the statement is nontrivial and is used to motivate the trimming procedure; please include a proof or relegate it to an appendix.
- [Section 5.1, basis tracking] The complexity analysis does not include the cost of basis tracking on line 29, although the experiments show that tracking materially increases runtime; the paper should state explicitly that the given bound applies only to the non-tracking mode.
- [Proposition 3.4, proof] In the displayed boundary formula, the term ∂_{s−1}(γ_{xi}x) appears where the path γ_{xi}x has length s; this is presumably a typo for ∂_s(γ_{xi}x) and should be corrected to avoid confusion.
- [Algorithm 1, line 29] The notation B(p) ← B(p−1) Σ_i x_i^p A_{x_i^p} V_i^{(p)} mixes path symbols with matrices; a brief explanation of how B(p) represents a basis of paths and how the multiplication is defined would improve readability.
- [Definition 1.1, remark] The cyclic-shift example for non-unique layers is correct but dense; a small concrete example, rather than only the general construction, would make the remark easier to follow.
Circularity Check
No significant circularity: the recursive full-depth path homology computation is derived from proven decompositions with no fitted parameters and no self-citations.
full rationale
The paper's central result, Theorem 4.3, is derived in the text: Proposition 4.2 proves that every full-depth cycle decomposes uniquely as Σ γ_x x with γ_x ∈ ker(∂_{p-1})∩A_{p-1}(G_pred(x)) and Σ γ_x = 0, and Theorem 4.3 then rewrites this coordinate space as V_{K_p} = N([A_{x_1},...,A_{x_{n_p}}]). The proof uses only the definition of the boundary map, Lemma 2.2, and Proposition 3.4, for which a proof is supplied; Proposition 3.4 is described as an extension of Proposition 4 in [8], but it is not imported as an unverified black box. The algorithm computes an exact algebraic quantity, namely the full-depth cycle space of a fixed stratified digraph, rather than predicting a fitted quantity; no parameter is calibrated to data. The only benchmark comparison uses an external implementation [4] of the general algorithm [9], and the bibliography contains no self-citations by the authors. The non-invariance of 'full-depth' under non-canonical layer choices is explicitly acknowledged in the remark after Definition 1.1 and is a scope limitation, not a circular step. Accordingly, no load-bearing derivation step reduces to its inputs by construction.
Assumptions & free parameters
assumptions (4)
- standard math Path homology with real coefficients is defined by the chain complex (Λ_p, ∂_p) and the invariant subspace Ω_p; the isomorphism H_p = (ker ∂_p ∩ A_p) / ∂_{p+1}(Ω_{p+1}) holds.
- domain assumption In a stratified digraph with layers K0,...,KL, every allowed p-path has its ith vertex in K_i, so cross sections at different depths are disjoint.
- standard math For a DAG, the longest path length ℓ(G) and the subgraph G* of all longest paths can be computed in O(|V|+|E|) using topological sorting and edge relaxation.
- domain assumption The general path homology algorithm of Chowdhury et al. [9] is correct and has complexity O(n^{6+3p}) for p-dimensional homology, serving as a valid baseline.
Cite this review
Pith. "Pith review of Recursive Computation of Path Homology for Stratified Digraphs." pith.science (2026). https://pith.science/paper/TKYSFJ4B
@misc{pith2026241205684,
author = {Pith},
title = {Pith review of: Recursive Computation of Path Homology for Stratified Digraphs},
year = {2026},
howpublished = {\url{https://pith.science/paper/TKYSFJ4B}},
note = {Machine review of arXiv:2412.05684}
}
read the original abstract
Stratified digraphs are popular models for feedforward neural networks. However, computation of their path homologies has been limited to low dimensions due to high computational complexity. A recursive algorithm is proposed to compute certain high-dimensional (reduced) path homologies of stratified digraphs. By recursion on matrix representations of homologies of subgraphs, the algorithm efficiently computes the full-depth path homology of a stratified digraph, i.e. homology with dimension equal to the depth of the graph. The algorithm can be used to compute full-depth persistent homologies and for acyclic digraphs, the maximal path homology, i.e., path homology with dimension equal to the maximum path length of a graph. Numerical experiments show that the algorithm has a significant advantage over the general algorithm in computation time as the depth of stratified digraph increases.
Figures
Reference graph
Works this paper leans on
-
[4]
Carranza, D., Doherty, B., Kapulkin, K., Opie, M., Sarazola, M., and Wong, L. Z. (2022). Python script for computing path homology of digraphs. https://github.com/sheaves/path_ homology, version 1.0.0
work page 2022
-
[1]
Ballester, R., Casacuberta, C., and Escalera, S. (2023). Topological data analysis for neural network analysis: A comprehensive survey. arXiv preprint arXiv:2312.05840
arXiv 2023
-
[2]
Berry, E., Chen, Y.-C., Cisewski-Kehe, J., and Fasy, B. T. (2020). Functional summaries of persistence diagrams. Journal of Applied and Computational Topology , 4(2):211–262
work page 2020
-
[3]
Biscio, C. A. and Møller, J. (2019). The accumulated persistence function, a new useful functional summary statistic for topological data analysis, with a view to brain artery trees and spatial point process applications. Journal of Computational and Graphical Statistics , 28(3):671–681
work page 2019
-
[5]
Chazal, F., De Silva, V., and Oudot, S. (2014a). Persistence stability for geometric complexes. Geometriae Dedicata, 173(1):193–214
work page 2014
-
[6]
Chazal, F., Glisse, M., Labru` ere, C., and Michel, B. (2014b). Convergence rates for persis- tence diagram estimation in topological data analysis. In International Conference on Machine Learning, pages 163–171
work page 2014
-
[7]
Chen, B., Yau, S.-T., and Yeh, Y.-N. (2001). Graph homotopy and Graham homotopy.Discrete Mathematics, 241(1-3):153–170
work page 2001
-
[8]
Chowdhury, S., Gebhart, T., Huntsman, S., and Yutin, M. (2019). Path homologies of deep feedforward networks. In 2019 18th IEEE International Conference On Machine Learning And Applications (ICMLA), pages 1077–1082. 17
work page 2019
Show all 29 references
-
[9]
Chowdhury, S., Huntsman, S., and Yutin, M. (2021). Path homology and temporal networks. In Complex Networks & Their Applications IX , pages 639–650
2021
-
[10]
and M´ emoli, F
Chowdhury, S. and M´ emoli, F. (2018). Persistent path homology of directed networks. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1152–1169
2018
-
[11]
K., Li, T., and Wang, Y
Dey, T. K., Li, T., and Wang, Y. (2022). An efficient algorithm for 1-dimensional (persistent) path homology. Discrete & Computational Geometry , 68(4):1102–1132
2022
-
[12]
Topological persistence and simplification
Edelsbrunner, Letscher, and Zomorodian (2002). Topological persistence and simplification. Discrete & computational geometry , 28:511–533
2002
-
[13]
and Harer, J
Edelsbrunner, H. and Harer, J. L. (2022). Computational Topology: An Introduction. Amer- ican Mathematical Society. Reprint of the 2010 original
2022
-
[14]
Grigor’yan, A., Lin, Y., Muranov, Y., and Yau, S.-T. (2012). Homologies of path complexes and digraphs. arXiv preprint arXiv:1207.2834
2012 arXiv
-
[15]
Grigor’yan, A., Muranov, Y., and Yau, S.-T. (2017). Homologies of digraphs and K¨ unneth formulas. Communications in Analysis and Geometry , 25(5):969–1018
2017
-
[16]
A., Schult, D
Hagberg, A. A., Schult, D. A., and Swart, P. J. (2008). Exploring network structure, dy- namics, and function using NetworkX. In Varoquaux, G., Vaught, T., and Millman, J., editors, Proceedings of the 7th Python in Science Conference , pages 11–15. Python package available at ...
2008
-
[17]
Ivashchenko, A. V. (1994). Contractible transformations do not change the homology groups of graphs. Discrete Mathematics, 126(1-3):159–170
1994
-
[18]
Li, W., Dasarathy, G., Natesan Ramamurthy, K., and Berisha, V. (2020). Finding the ho- mology of decision boundaries with active learning. Advances in Neural Information Processing Systems, 3:8355–8365
2020
-
[19]
Loiseaux, D., Carri` ere, M., and Blumberg, A. (2024). A framework for fast and stable representations of multiparameter persistent homology decompositions. Advances in Neural Information Processing Systems, 36
2024
-
[20]
and Villa, A
Masulli, P. and Villa, A. E. (2016). The topology of the directed clique complex as a network invariant. SpringerPlus, 5:1–12
2016
-
[21]
and Lazar, N
Moon, C. and Lazar, N. A. (2023). Hypothesis testing for shapes using vectorized persistence diagrams. Journal of the Royal Statistical Society Series C: Applied Statistics , 72(3):628–648
2023
-
[22]
Pacault, J. F. (1974). Computing the weak components of a directed graph. SIAM Journal on Computing , 3(1):56–61
1974
-
[23]
P´ erez-Fern´ andez, D., Guti´ errez-Fandi˜ no, A., Armengol-Estap´ e, J., and Villegas, M. (2021). Characterizing and measuring the similarity of neural networks with persistent homology.arXiv preprint arXiv:2101.07752. 18
2021 arXiv
-
[24]
Rathore, A., Chalapathi, N., Palande, S., and Wang, B. (2021). TopoAct: Visually exploring the shape of activations in deep learning. In Computer Graphics Forum , volume 40, pages 382–397
2021
-
[25]
W., Nolte, M., Scolamiero, M., Turner, K., Perin, R., Chindemi, G., D lotko, P., Levi, R., Hess, K., and Markram, H
Reimann, M. W., Nolte, M., Scolamiero, M., Turner, K., Perin, R., Chindemi, G., D lotko, P., Levi, R., Hess, K., and Markram, H. (2017). Cliques of neurons bound into cavities pro- vide a missing link between structure and function. Frontiers in computational neuroscience , 11:266051
2017
-
[26]
Rieck, B., Togninalli, M., Bock, C., Moor, M., Horn, M., Gumbsch, T., and Borgwardt, K. (2018). Neural persistence: A complexity measure for deep neural networks using algebraic topology. arXiv preprint arXiv:1812.09764
2018 arXiv
-
[27]
and Wayne, K
Sedgewick, R. and Wayne, K. (2011). Algorithms. Addison-Wesley Professional, 4 edition
2011
-
[28]
Wasserman, L. (2018). Topological data analysis. Annual Review of Statistics and Its Appli- cation, 5(1):501–532
2018
-
[29]
and Yamana, H
Watanabe, S. and Yamana, H. (2022). Topological measurement of deep neural networks using persistent homology. Annals of Mathematics and Artificial Intelligence , 90(1):75–92. 19
2022
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.