{"id":"ab9b4228-fd97-41e4-a06a-2a5cde86ced3","arxiv_id":"2412.05684","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":7.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"A layer-by-layer recursive algorithm computes the full-depth path homology of stratified digraphs, with large speedups over the general algorithm for deep feedforward networks.","lead":"This paper gives a recursive algorithm that computes the full-depth path homology of layered (stratified) directed graphs much faster than the standard method. It targets deep feedforward neural networks, where the interesting topological feature lives at the depth dimension and was previously too expensive to compute.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified.","rationale":"I read the paper as proving a recursive algorithm for full-depth reduced path homology of a fixed stratified digraph, and this claim holds. I independently checked the key structural step: in Proposition 4.2, the subgraph G_pred(x) is built from allowed (p-1)-paths whose last vertex lies in pred(x), so any cycle γ_x in its path space necessarily joins with x to form an allowed p-path. The coordinate recursion in Theorem 4.3 and Algorithm 1 faithfully represents the subspace V_S by deleting row blocks that correspond to non-predecessor coordinates; the convention that N(empty) = identity handles the fully-connected predecessor case. The reader's weakest assumption about stratification non-uniqueness is accurate but not a defect of the algorithm: the paper explicitly limits its intended application to feedforward networks, where the layer structure is canonical. The only other roughness is the abbreviated proof of Proposition 3.4 for s = p; the written argument jumps from ω1 = 0 to the conclusion, but the missing step is a simple split by last-vertex cross-sections and does not change the result. The experiments are consistent with the claimed speedups, the code is open-source, and I found no circularity, hidden parameter fitting, or inconsistency. Therefore the reader's ACCEPT verdict stands without modification.","tokens_in":18829,"tokens_out":46517,"duration_ms":410179,"concrete_test":"Run the released implementation on a fixed random subgraph of Γ3 (e.g., ρ = 0.9, one seed) and recompute β_3 with the general algorithm of [4]; if the two Betti numbers agree, the recursion is confirmed end-to-end. This also checks that the coordinate bookkeeping in Algorithm 1 produces the same invariant as the textbook definition.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim—that the full-depth cycle space of a fixed stratified digraph can be computed by the coordinate recursion V_Kp = N([A_{x1},...,A_{x_{n_p}}])—is sound. The key decomposition (Prop. 4.2) is valid because G_pred(x) is defined using (p-1)-paths whose last vertex lies in pred(x); hence any γ_x in its cycle space automatically gives an allowed p-path γ_x x, and the sum condition Σγ_x = 0 is exactly the boundary condition. The only candidate issue is the one the authors flag in the remark after Def. 1.1: 'full-depth' is stratification-dependent, so β_L is not an invariant of the underlying digraph when layers are not canonical. This is a real scope limitation, but it is explicit and does not affect the intended feedforward-network setting, where layers are architecture-defined. Prop. 3.4's proof is terse for s = p, but the missing split by last-vertex cross-sections is straightforward and does not undermine the statement. No load-bearing error found.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":18971,"tokens_out":30599,"duration_ms":241403,"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":[{"comment":"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.","section":"Section 5.1, complexity estimate"}],"minor_comments":[{"comment":"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":"Section 3, Corollary 3.6"},{"comment":"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.","section":"Section 5.1, basis tracking"},{"comment":"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.","section":"Proposition 3.4, proof"},{"comment":"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.","section":"Algorithm 1, line 29"},{"comment":"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.","section":"Definition 1.1, remark"}],"recommendation":"major_revision","confidential_remarks":"The paper is a solid algorithmic contribution with a sound main recursion, but the stated worst-case complexity bound needs a substantive correction. The stratification-dependence of full-depth homology is a real scope limitation that the authors acknowledge; I would encourage them to state it more prominently in the abstract or introduction. No concerns about novelty or citation practice were found."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Here's my read.\n\nThe new thing is Theorem 4.3: a layer-by-layer recursion for the full-depth cycle space of a stratified digraph. Instead of constructing all allowed L-paths and reducing a huge boundary matrix, each step builds the cycle space of the next layer from the nullspaces of small matrices, with the cost controlled by the previous Betti number. The decomposition behind it (Prop 4.2) is correct; I traced through small examples and got the right Betti numbers. The reduction of maximal path homology of a DAG to full-depth homology on the longest-path subgraph (Prop 3.7) is also new and useful, since it gives DAGs a clearly defined top-dimensional homology.\n\nThe experiments are solid. The comparison uses the external [4] implementation of the general algorithm, reports both numerical and basis-tracked timing, and shows speedups that grow with depth. Code is on GitHub. There is no fitting, no post-hoc selection, and the method is exact rather than approximate.\n\nThe one genuine caveat is the one the authors state themselves: full-depth homology is stratification-dependent. If a digraph admits several layer decompositions (empty edge layers, isolated vertices), beta_L can change. For feedforward networks the layers are canonical, so the target application is safe. I'd still have liked a short discussion of how to pick a layer structure for a general stratified digraph, but the limitation is right there in the remark after Def 1.1, so I can't call it hidden.\n\nMinor soft spots: Corollary 3.6 is proved by omission, but it's only an optional trimming step. The complexity analysis ignores some non-arithmetic overhead, but the reported timings back the headline speedup. The experiments are all on random subgraphs of fully connected layered graphs, which is the main use case, though I'd be curious how the recursion behaves on sparser or uneven layers.\n\nOverall: the central algorithm is a real step forward for computing top-dimensional path homology on DAGs. I'd send it to a serious referee, and I'd probably cite it if I needed to compute path homology of layered networks. Worth a reading group slot for the TDA people.","headline":"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.","tokens_in":19491,"tokens_out":2758,"would_cite":true,"duration_ms":25691,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["55N31","05C20"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["path homology","stratified digraph","full-depth homology","cycle space recursion","Betti number","persistent path homology","feedforward networks","directed acyclic graph"],"falsifier":"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.","tokens_in":18618,"feed_emoji":"🔁","tokens_out":11100,"duration_ms":104061,"temperature":0.7,"pith_summary":"This paper addresses the practical difficulty of computing high-dimensional path homology of stratified digraphs—the layer-structured digraphs used to model feedforward neural networks. General path-homology algorithms scale poorly with dimension, roughly $O(n^{6+3p})$ in the general algorithm, so full-depth homology (dimension equal to the number of layers) has been out of reach except in shallow cases. The authors prove that full-depth cycles of a stratified digraph can be updated recursively one layer at a time, using only null-space computations on matrices built from the previous level's cycle space. The result is an algorithm with complexity $O(\\sum_{p=1}^{L} |K_{p-1}||K_p|b_{p-1}^3)$, and experiments on random subgraphs of fully connected layered graphs show substantial speedups that grow with depth. The same recursion also yields full-depth persistent homology and, for acyclic digraphs, the maximal path homology.","feed_headline":"Layer-by-layer recursion speeds up deep path-homology computation","feed_subtitle":"A null-space recursion computes full-depth Betti numbers of layered digraphs without long-path enumeration; runtime shrinks with depth.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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