acceptodds
Under review as a conference paper at ICLR 2027

A differentiability framework for zigzag persistent homology via linear interpolation

Abstract

Persistent homology can be differentiated and incorporated into learning pipelines, but no analogous framework exists for zigzag persistence, which is needed when the underlying topological structure evolves non-monotonically over time. We develop such a framework for sequences of simplicial complexes obtained by thresholding time-dependent filtering values on a fixed complex. By assigning persistence diagram endpoints the real-valued times at which linearly interpolated filtering values cross the threshold, we transfer the continuity of the filtering values to the diagram points. This yields smooth local lifts of the resulting persistence-diagram-valued map, from which we derive differentials almost everywhere under mild regularity conditions on the parametrization of the filtering values. We prove local Lipschitz continuity outside an explicit measure-zero exclusion set; standard stochastic subgradient convergence guarantees therefore do not apply directly. We argue that, even without such guarantees, this exclusion set is small enough in practice to allow effective optimization. We test this empirically in two experiments: sensor network coverage optimization and dynamic graph classification.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
zigzag persistent homology, differentiable topological data analysis, persistence diagrams, topological layers, time-varying data, dynamic graphs

Reviews

Among:
Shape:
1234this paper, Top 17%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.75 over 4 reviews, above 83% of the others.
Reviewer_21NjOpenReview ↗
Rating
2
Confidence
4
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

The paper develops a differentiability framework for zigzag persistent homology of finite evolving simplicial complexes. It linearly interpolates filtering values, separates discrete event pairing from rational crossing times, and constructs smooth diagram lifts on regions with fixed combinatorial data (Proposition 3.6 and Corollary 3.7). For definable parameterizations, it obtains differentiability outside a parameter-space null set (Proposition 3.8), and proves local bottleneck Lipschitz continuity outside an explicit exclusion set (Theorem 3.9). It also shows why global continuity can fail. Controlled sensor-patrol and temporal-graph experiments illustrate optimizing bar lifetimes and learning a filtering function through the resulting layer. These experiments demonstrate feasibility on designed tasks; they do not establish general temporal-classification superiority or a general convergence guarantee.

Critical strengths
  1. A careful mathematical foundation for an implementable gradient. The event-order invariance argument, fixed-cell rational lifts, parameter-space stratification, and off-exclusion Lipschitz result fit together (pp. 4–7; Appendix C). Explicit counterexamples prevent an overbroad stability or convergence interpretation. The local-lift perspective connects naturally to the cited diagram calculus of Leygonie et al., while addressing the insertion/deletion setting.
  2. Experiments isolate what temporal feature identity adds. The patrol comparison holds the geometric setup fixed while changing the lifetime aggregation, and the classification controls distinguish learning a field from reading temporal pairing (pp. 8–9; Appendices D–E). The paper reports held-out seeds/splits, validation-based restart selection, and all 80 single classification runs, including 22 failures. These are meaningful feasibility checks for the theoretical construction.

The October 7 reviewer-side checks built the native C++ backend and returned 282 passed tests / 6 skipped. Generic-point zigzag gradients agreed to about 1.34e-7 relative error. These checks support the implementation at generic points, while leaving the exact submitted training lineage and tied first-update justification unresolved. The tied-start central-difference discrepancy of about .0822 is not by itself evidence of an invalid Clarke selection. Complete training and 100,000-step patrol results were not assessed at that evidence cutoff.

Critical weaknesses

The theoretical algorithm and the classification evidence are not yet connected by a reproducible, justified implementation. Appendix E.1 specifies a sigmoid field at threshold 0.5 (pp. 38–39), while the archived linked release uses tanh and 0.125 (gnn.py:124, configs/record.txt:1). Its README reports 19/20 solved splits and 0.977 ± 0.094, versus Table 5's 20/20 and 0.995 ± 0.016. These transforms/thresholds need not yield the same complexes or event derivatives. Separately, C.5's almost-sure gradient argument uses continuous parameter perturbations, including initialization; E.1 and the archived training loop use minibatch sampling alone from a tied, zero-residual start. Almost-everywhere differentiability does not justify that prescribed first point. A stale release and a valid one-sided/Clarke selection are plausible resolutions; failed central differences at a nonsmooth point do not prove an invalid subgradient. Nevertheless, both the exact result version and the applicable justification remain unresolved.

Questions for authors
  1. Exact-version evidence: Which frozen source/configuration and per-run records produced the sigmoid/0.5 experiment and Table 5? Please map them to the archived tanh/0.125 release, and state which result, if any, changes after reconciliation.

  2. The first update: Were continuously distributed parameter perturbations applied before the first gradient evaluation and at subsequent steps in the submitted runs? If not, can the chosen vector at the tied start be justified as a Clarke selection, or should that update be labeled heuristic? Initial, generic-point and final diagnostics for the exact version would be useful; a failed central difference at a nonsmooth point alone is not dispositive.

  3. Technical positioning: How do the differentiated object, event pairing and regularity assumptions differ from D-GRIL/GRIL and the already cited Scoccola et al. framework? Which obstruction in arbitrary temporal zigzags requires the new rational lifts and exclusion set? GEFL and TopInG provide related learned extended-persistence context, but their static-graph targets are not interchangeable temporal baselines.

  4. Mechanism beyond the designed classification task: With the exact submitted implementation, do the temporal-pairing advantage and single-run success rate persist when the switching rates, decoy strength or number of time samples are varied? A matched simple temporal reader would help determine what is specific to topology. Please separate variability across new generator draws from folds/restarts of the existing two draws. The current all-run table and validation-based restart selection provide useful controls.

  5. Stability in the demonstrated optimization: What do the observed crossing denominators, approaches to the exclusion set, and temporal-resampling sensitivity indicate about gradient conditioning? For patrols, does improving the interpolated-field lifetime also improve the physical uncovered-duration statistic under finer temporal/spatial evaluation? The question concerns the practical relation between the optimized surrogate and its reported geometric evaluator; a general convergence theorem is not required. Runtime measurements are already reported.

Reviewer_oe6uOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper develops a differentiability framework for zigzag persistence generated by thresholding time-dependent filtering values on a fixed simplicial complex. Its central construction replaces discrete barcode endpoint indices with continuous threshold-crossing times obtained through linear interpolation. Validation comprises two synthetic experiments. One is for optimising mobile-sensor trajectories to reduce persistent coverage defects and the other is learning a filtering function for temporal-graph classification.

Critical strengths
  1. Replacing discrete event indices with interpolated crossing times allows gradients to reach the filtering values that generate a zigzag sequence. This enables both topological-loss optimisation and task-driven filtration learning. The accompanying analysis of almost-everywhere differentiability and local Lipschitzness gives the construction a good theoretical basis.

  2. The coverage experiment evaluates the barcode as an optimisation objective, while classification uses it as a learned intermediate representation. Removing the topological objective in the coverage experiment and comparing fixed and learned filtering functions in classification help establish that the proposed gradient pathway contributes to the observed behaviour. The independent geometric coverage evaluator is also valuable.

Critical weaknesses
  1. Both experiments are small and synthetic. The classification task is deliberately constructed to distinguish temporal feature identity from per-frame summaries, making it a useful diagnostic but a limited test of broader utility. The learned per-frame persistence baseline is informative, but there is no comparison with a temporal model receiving the same inputs. In coverage optimisation, the principal comparisons are alternative barcode objectives and motion-only optimisation, rather than a direct coverage-gap objective or revisit-time heuristic. Temporal-resolution sensitivity is also important because interpolating sampled filtering values need not reproduce the exact topology along continuous physical trajectories. These limitations leave uncertainty about how robustly the proposed layer transfers beyond the designed settings.

  2. Appendix C.7 demonstrates that arbitrarily small filtering-value perturbations can produce finite barcode changes. Avoiding exact exceptional points does not establish that optimisation is well behaved near or across these configurations. Empirically, the classification result of (0.995±0.0160.995 \pm 0.016) uses validation-based selection among four restarts, whereas individual runs achieve (0.893±0.1780.893 \pm 0.178), with only 58 of 80 runs meeting the success criterion. Moreover, Appendix C.5 describes additional Gaussian parameter perturbations, while Section 4.2 attributes stochasticity to minibatch sampling alone. This discrepancy matters because the perturbation argument is used to justify avoidance of non-differentiable configurations. Diagnostics of gradient magnitudes, crossing denominators, and loss jumps would help establish whether the theoretical difficulties are benign in the reported experiments.

Questions for authors
  1. Appendix C.5 states that Gaussian parameter perturbations are added at every iteration, including initialisation, whereas Section 4.2 and Appendix E.1 describe minibatch sampling as the only source of optimisation noise. Which procedure was used for the classification results? If additional perturbations were used, please specify their magnitude and placement. Otherwise, how were initialisation and non-differentiable configurations handled?

  2. What distinguishes the 22 unsuccessful classification runs from the successful ones? Do crossing denominators, gradient norms, or changes in event structure indicate instability, or do these runs remain near an uninformative solution? Please also report the numerical accuracy of the finite-difference checks mentioned in Appendix E.3.

  3. How sensitive are the coverage results to temporal sampling resolution? Appendix D.3 also states that the iteration budget was extended from 30,000 to 100,000 on the held-out seeds. Was this extension decided before inspecting held-out outcomes?

  4. Chen et al., A Topological Regularizer for Classifiers via Persistent Homology (AISTATS 2019), optimise a penalty formulated using zeroth-level set-zigzag persistence and establish almost everywhere differentiability under a piecewise-linear approximation. How does the proposed framework differ from this special case? This appears relevant to the introduction’s broad claim that gradients cannot pass through zigzag barcodes.

4 comments

We thank reviewer ou6u for a careful reading of our draft, the checks they asked helped us make our results more solid.

Appendix C.5 states that Gaussian parameter perturbations are added at every iteration, including initialisation, whereas Section 4.2 and Appendix E.1 describe minibatch sampling as the only source of optimisation noise. Which procedure was used for the classification results? If additional perturbations were used, please specify their magnitude and placement. Otherwise, how were initialisation and non-differentiable configurations handled?

We thank the reviewer for spotting this inconsistency. In the submitted classification results, minibatch sampling was the only source of noise: training started from a zero residual, and no parameter perturbation was added. Without perturbation, nothing prevents an iterate from lying on a non-differentiable configuration, such as a tie of crossing times; at such a configuration, our implementation differentiates the closed-form crossing times of the cell selected by its tie-breaking rule, which gives a derivative fixed by convention rather than a gradient of the loss. As reported in our answer in Appendix E.3, this happened at the zero initialisation.

We have therefore rerun the classification experiment following Appendix C.5, adding a Gaussian perturbation with standard deviation σ = 10⁻⁴, fixed in advance, to the parameters at initialisation and at every iterate. Best-of-4 accuracy is unchanged (20/20 splits solved, 0.995 ± 0.016), and single runs solve 62/80 instead of 58/80. We propose to report these runs in place of the submitted ones in the revised paper, so that Section 4.2 and Appendix E.1 describe the perturbation consistently with Appendix C.5.

What distinguishes the 22 unsuccessful classification runs from the successful ones? Do crossing denominators, gradient norms, or changes in event structure indicate instability, or do these runs remain near an uninformative solution?

We provide a response on the 22 unsuccessful classifications in the general comment.

Please also report the numerical accuracy of the finite-difference checks mentioned in Appendix E.3.

Autograd is compared with central differences (h = 10⁻⁶) along 5 random directions, at the first and final iterate of every run; we report the worst relative error. With the perturbation of Appendix C.5, now used in all reported runs, the median over the 80 runs is 5.5·10⁻⁸ at the first iterate and 4.1·10⁻⁸ at the final one. In the submitted runs, without the perturbation, the first iterate lies on a tie of crossing times, where the loss is not differentiable, and the error there is 0.71; at the final iterate it is 7.0·10⁻⁸. We add the full numbers to Appendix E.3.

How sensitive are the coverage results to temporal sampling resolution?

The coverage gaps we report do not depend on the layer's reading resolution. They come from the independent evaluator of Appendix D.3, which computes, exactly in continuous time, the intervals during which each probe is covered along the true piecewise-linear motion. Between read instants, every robot moves in a straight line, so the diameter of each simplex is convex in time. Linear interpolation therefore never overestimates the filtering value, and at every instant the layer's complex is a subcomplex of the true Rips complex. As already reported in Appendix D.3 for the main runs, the layer’s longest bar is at least the measured maximum gap; this holds in all 150 runs we checked, including the new ones. The paper's reading of 3 instants per move is basically converged. Re-reading the final lifetime trajectories at 6 instants per move changes the longest bar from 9.07 to 9.05 frames (median over seeds); reading only at the waypoints overstates it (14.93).

Appendix D.3 also states that the iteration budget was extended from 30,000 to 100,000 on the held-out seeds. Was this extension decided before inspecting held-out outcomes?

The 100K extension was indeed decided before inspecting held-out outcomes, we will make this explicit in the text.

Chen et al., A Topological Regularizer for Classifiers via Persistent Homology (AISTATS 2019), optimise a penalty formulated using zeroth-level set-zigzag persistence and establish almost everywhere differentiability under a piecewise-linear approximation. How does the proposed framework differ from this special case? This appears relevant to the introduction’s broad claim that gradients cannot pass through zigzag barcodes.

We thank the reviewer for pointing us to Chen et al. (2019); the comparison helps us position our work more precisely.

Their classifier f is a real function sampled on a fixed graph and replaced by its piecewise-linear extension f̂. The level-set zigzag of f̂ is indexed by the values of f̂ itself, so its bars are born and die at critical values of f̂, namely values of f at vertices: the gradient is then obtained as in ordinary persistence. Our framework differs in what indexes the zigzag: time, an evolution parameter distinct from the filtering values, which are only thresholded. Read on the sequence, endpoints are integer time indices, constant in the values; the interpolation of Eq. (3) is what makes them depend on the filtering values, so that gradients can flow through them.

We agree that our original claim was too broad. We propose to restrict the introduction to time-indexed zigzag barcodes and presents level-set zigzag, citing Chen et al. (2019), as the special case in which the values of a function play the role of time and the existing calculus applies. In Appendix A (paragraph “Differentiability of persistent homology”), we propose to contrast the two uses of linear interpolation: in Chen et al. the endpoints are values of f regardless, and interpolation only places the critical points on vertices; in ours, it is the only source of dependence of the endpoints on the filtering values.

Thank you to authors for the detailed rebuttal, which have addressed most of my main concerns; although some limitations remain regarding optimisation stability and broader empirical validation, I maintain my rating.

We thank the reviewer for their careful reading and for the requested checks, which strengthened the results. We agree on the remaining limitations, and the revised paper states them: standard convergence guarantees for stochastic subgradient methods do not apply directly, since local Lipschitz continuity holds only outside the exclusion set (Section 3.3); Appendix F compares optimizers on the controlled task; and Section 4.2 delimits the scope of the real-data experiment.

Reviewer_BVruOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2(+1)
Soundness
2
Read review
Paper summary

The paper studies persistence diagrams (PD) arising from zigzag filtrations in topological data analysis. In particular, it develops a theory that extends the differentiability framework for PDs by Leygonie et al. (2022) to zigzag persistence. The proposed construction is applied to two small datasets.

Critical strengths
  • Extending the differentiability framework for PDs by Leygonie et al. (2022) to zigzag persistence seems like an important theoretic contribution.
  • The construction for unrolling a sequence of complexes to get a zigzag filtration presented in Section 3.1 is interesting and seems to be correct.
Critical weaknesses
  • It would be good to motivate the real-world applications of the proposed zigzag differentiability framework already in the introduction.
  • Section 2.2. presents definitions and theoretical results from Leygonie et al. (2022) about differentiability of persistence diagrams without giving explanations and interpretations to make the material understandable for readers who are not yet familiar with the work by Leygonie et al. (2022). It would be good to make the paper more self-contained so that readers familiar with the basics of TDA can understand the paper.
  • The theoretical results starting from L184 are not sufficiently motivated. What is the meaning of the map Pp\mathcal{P}_p (both theoretically and in experiments) and why do we need differentiability? The following results are very notation-heavy and it is difficult to understand the meaning of the results. In particular, the theoretical results are not tied into a coherent narrative. It could also help to provide illustrations. The limitations of the theoretical exposition meant that I could not properly verify the theoretical results.
  • The experiment are limited to very small datasets and there is no direct comparison to baseline methods. It is thus not clear what advantages the proposed method has for practitioners.
Questions for authors
  • The two experiments are not sufficiently motivated. For example, what does it mean that MM robots are tasked to "cover" holes, how does this translate to zigzag persistence and why would we want to compute derivatives of the persistence diagram? - again, a better illustration might help here. Instead the paper seems to waste a lot of space to explain a simple thing like stochastic gradient descent (L413 to 424).
5 comments

We thank the reviewer for raising concerns about the readability of our work, this helped us improve its presentation.

It would be good to motivate the real-world applications of the proposed zigzag differentiability framework already in the introduction.

We agree this was not sufficiently clarified in the introduction. We propose adding the following sentence to the introduction after the first paragraph:

Zigzag barcodes are already used to summarize evolving systems, such as temporal contact and communication networks \citep{kim2020dynamic, myers2023temporal}, coverage holes in mobile sensor networks \citep{gamble2015coverage} and neural population activity under time-varying stimuli \citep{gardinazzi2026zigzag}; in each case the sequence of complexes is built by a hand-designed rule, such as a threshold on distances, edge weights or activity, and the barcode is a fixed output. A gradient with respect to the values that generate the sequence lets that rule be learned from a task, as we show on epidemic temporal network classification in Section 4.X, and lets trajectories be optimized against a loss on bar lifetimes, such as the duration of a coverage defect, Section 4.1.

Note that we refer to the real dataset addition we have run and presented in the general response.

References:

  • Woojin Kim, Facundo Mémoli, and Zane Smith. Analysis of dynamic graphs and dynamic metric spaces via zigzag persistence. In Topological Data Analysis: The Abel Symposium 2018, Abel Symposia vol. 15, pp. 371–389. Springer, Cham, 2020. doi:10.1007/978-3-030-43408-3_14
  • Audun Myers, David Muñoz, Firas A. Khasawneh, and Elizabeth Munch. Temporal network analysis using zigzag persistence. EPJ Data Science, 12(1):6, 2023. doi:10.1140/epjds/s13688-023-00379-5
  • Jennifer Gamble, Harish Chintakunta, and Hamid Krim. Coordinate-free quantification of coverage in dynamic sensor networks. Signal Processing, 114:1–18, 2015. doi:10.1016/j.sigpro.2015.02.013
  • Yuri Gardinazzi, Alessio Ansuini, Eugenio Piasini, Fabio Anselmi, and Matteo Biagetti. Zigzag persistence of neural responses to time-varying stimuli. In Proceedings of the Geometry, Topology, and Machine Learning Workshop, PMLR vol. 325, pp. 130–144, 2026.

Section 2.2. presents definitions and theoretical results from Leygonie et al. (2022) about differentiability of persistence diagrams without giving explanations and interpretations to make the material understandable for readers who are not yet familiar with the work by Leygonie et al. (2022). It would be good to make the paper more self-contained so that readers familiar with the basics of TDA can understand the paper.

We agree that this material may be unfamiliar to readers who know the basics of TDA but not Leygonie et al. (2022), and we propose to add three sentences in the main text as follows:

Before Definition 2.4: A persistence diagram is an unordered multiset of points, hence not a Euclidean vector that can be differentiated directly; the idea of Leygonie et al. (2022) is to work with ordered diagrams, vectors listing the coordinates of the points in some order, and to forget the order only at the end, through the quotient map below.

After Definition 2.5: Intuitively, a map into D is differentiable at if, near , its diagrams have a fixed number of points that can be ordered so that each birth and death is a Cr function of the parameter, given by the lift B~\widetilde{B}; a map out of D is differentiable if it is smooth in the ordered coordinates, whatever the order.

After Proposition 2.6: The differential of B depends on the chosen lift, but that of the composite does not, since L treats all orderings alike.

The theoretical results starting from L184 are not sufficiently motivated. What is the meaning of the map (both theoretically and in experiments) and why do we need differentiability? The following results are very notation-heavy and it is difficult to understand the meaning of the results. In particular, the theoretical results are not tied into a coherent narrative. It could also help to provide illustrations. The limitations of the theoretical exposition meant that I could not properly verify the theoretical results.

We have expanded on the introduction part (see above) to motivate differentiability. We can propose an illustration to clarify the intuition of how we want to approach the differentiability of the zig zag algorithm. The reviewer can refer to the folder "rebuttal" in the anonymized repository, https://anonymous.4open.science/r/zzdiff-anon-B57D/, Figure 4.

The experiment are limited to very small datasets and there is no direct comparison to baseline methods. It is thus not clear what advantages the proposed method has for practitioners.

We address this valuable concern in the general response.

Dear authors,

Regarding the application to real-world data, see my response to your general update above. At this point it is not clear what the advantage of your method is if random-walk based baselines outperform it.

Adding three sentences on the background on Leygonie et al. (2022) does not sufficiently improve your presentation of the relevant background in my opinion. I believe it would be important to provide more details and explanations, and also a cartoon could help to make the theory more accessible to people familiar with TDA but not the paper by Leygonie et al. (2022).

Given these concerns I cannot raise my score at the moment.

We thank the reviewer for considering our response. On the real-data experiment, please see our reply under the general response. On presentation, we agree that three sentences were not enough. The revised PDF goes further on the three points you raised.

Adding three sentences on the background on Leygonie et al. (2022) does not sufficiently improve your presentation of the relevant background in my opinion. I believe it would be important to provide more details and explanations, and also a cartoon could help to make the theory more accessible to people familiar with TDA but not the paper by Leygonie et al. (2022).

We added a new section in appendix B, B.4, where we follow a diagram with two points, depending on one parameter, through the whole subsection 2.2: the two ordered vectors that represent it, the quotient map that forgets the order, a lift, a loss, and the chain rule with its numbers. Figure 4 shows this in a diagram. The maps that are actually differentiated are drawn differently from those that are not. This example should help readers who know persistence diagrams but not this calculus. We thank the reviewer for helping us improve on the presentation of this part.

The two experiments are not sufficiently motivated. For example, what does it mean that robots are tasked to "cover" holes, how does this translate to zigzag persistence and why would we want to compute derivatives of the persistence diagram? - again, a better illustration might help here. Instead the paper seems to waste a lot of space to explain a simple thing like stochastic gradient descent (L413 to 424).

We apologise for missing this question in the first reply, we somehow missed it. The fixed sensors do not see the middle of each lattice cell. In the Rips complex of the network, this gap is a 1-cycle that does not bound, a class of H1. A robot that comes within the Rips radius of the four corners of a cell spans triangles that fill the cycle, and the hole closes; when the robot leaves, the triangles are deleted and the hole reopens. Simplices are inserted and deleted, which is the setting of zigzag persistence, and each H1 bar is an interval during which a hole stays open. We want derivatives because the lengths of these bars are what one would like to control. With our construction, the endpoints are crossing times that depend smoothly on the robot positions, so the gradient of a loss on bar lengths tells each robot how to shift its path to arrive earlier or leave later. With frame indices as endpoints, the same loss is piecewise constant and has no gradient. Section 4.1 now says this, and Figure 3 has a new top row that draws it on one cell. The update rule you pointed to has moved to Appendix D.2, which is where the space came from.

Reviewer_QdiCOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper introduces a framework for differentiating zigzag persistent homology, which allowsincorporating it into grandient descent. The idea is replacing the (discrete, clearly) birth and death indices of zigzag barcodes (i.e., the birth and death of cycles of various lengths in a graph that evolves over time) with continuous threshold-crossing times which are obtained by linearly interpolating some time-dependent filtering values. The authors derive explicit differentials, establish almost-everywhere differentiability under regularity assumptions, and prove local Lipschitz continuity (almost everywhere). The framework is applied on two synthetic applications: optimizing robot trajectories to reduce persistent coverage defects and learning topological features for dynamic graph classification.

Critical strengths

I found the paper interesting and of good technical quality. The problem is well motivated, and extending differentiability from ordinary persistent homology to zigzag persistence is, AFAICS, a meaningful contribution. Notably, while the construction proposed by the authors is relatively simple, their mathematical analysis looks rather compelex. The paper is well written and the experiments demonstrate that useful gradients can be propagated through construction the paper brings forward.

Critical weaknesses

The experimental validation is limited to two synthetic examples, which demonstrate feasibility but provide little evidence of the proposed method being practical and/or scalable. Comparisons with established methods/baselines are also, AFAIC, rather missing. One must note that the theoretical results do not establish convergence of the proposed optimization method. Lastly, te optimization also appears sensitive to initialization: 22 out of 80 classification runs fail to reach 90% accuracy, whereas the reported 99.5% accuracy is obtained by selecting the best of four runs for each dataset split. All considered, I believe the paper makes a potentially valuable theoretical contribution, although its practical relevance remains demonstrated a little insufficiently.

Questions for authors
  • Can the authors provide further evidence of applicability beyond the two synthetic examples, possibly on real-world dynamic graph dataset?

  • What explains the failures of individual optimization runs in the classification experiment (see above)?

  • Could you say something re: scaling with number of simplices and/or time steps? In particular, Appendix D.6 reports a median of 1.5 hours per optimization run, even though the robot example involves only 19 points and approximately 180 simplices.

3 comments

We thank reviewer QdiC for his insightful comments. We address their questions here:

Can the authors provide further evidence of applicability beyond the two synthetic examples, possibly on real-world dynamic graph dataset?

We thank the reviewer for the suggestion. We ran an experiment on the four ct2 collections of Oettershagen et al. (SDM 2020). Details are provided in the general response.

What explains the failures of individual optimization runs in the classification experiment (see above)?

We provide an explanation of these failures in the general response.

Could you say something re: scaling with number of simplices and/or time steps? In particular, Appendix D.6 reports a median of 1.5 hours per optimization run, even though the robot example involves only 19 points and approximately 180 simplices.

The 1.5 hours come from the number of steps, not from the size of the complex: 100,000 steps at 57 ms each (App. D.6).

Compared with computing the zigzag barcode of the same thresholded sequence without gradients, our method uses the Dey–Hou pairing unchanged. The pairing receives an operation stream of the same length n, the number of events, with n ≤ (N+1)|K|; only the order of the stream differs. Outside the pairing, the method adds three steps:

(i) each event is stamped with its crossing time (Eq. 3), O(1) per event, and events are sorted by these times, O(n log n), in place of the per-frame ordering and we mark simultaneous events, O(n).

(ii) after the pairing, the n crossing times are recomputed with automatic differentiation and gathered at the paired indices, O(n);

(iii) the backward pass through this read-out, O(n).

We measured this against the plain computation on two synthetic families, five draws per configuration:

  • upper-star filtrations on triangulated grids, from 8×8 to 96×96 and from N = 16 to 1,024 frames;
  • Rips 2-skeletons of 12 to 60 random-walking points.

The number of events n ranges from 258 to 233,558. Stamping and steps (ii)–(iii) both grow linearly in n, but stamping processes events one at a time in a Python loop (3.7 µs per event) while (ii)–(iii) work on whole arrays (0.2–0.4 µs per event once n exceeds a few thousand events); the sort grows as n log n. At the largest instance (96×96 grid, N = 32, C++ engine), the plain computation takes 2.22 s and the differentiable layer 3.57 s, a 61% increase; the gradient pass and backward account for 0.07 s of it (2% of the layer's time).

In the revised draft we propose to:

  • add this benchmark as an appendix, with per-step timings, both engines and growth exponents;
  • state the complexity above in Section 3;

Thanks for the thorough answers and for the new experiments, which address my questions.

The real-data experiment is a welcome addition, and I appreciate that you report where learning helps and where it doesn't. The gains are modest, but it shows that the layer can learn on real data, which is what I was asking for.

The explanation of the failed runs is convincing. It does leave the optimizer that works (Adam) outside the theory, which covers SSD only: please say so plainly in the paper.

The answer on scaling is clear.

I'd also like to see your answer to Reviewer 21Nj on which version of the code produced the classification results. I keep my score.

We thank the reviewer for considering our edits positively, they significantly improved our work.

I'd also like to see your answer to Reviewer 21Nj on which version of the code produced the classification results. I keep my score.

We recognize the anonymized repository was incoherent. All reported results use the sigmoid field at ε = 0.5 (Appendix E.1). The archived release reflected an earlier tanh / ε = 0.125 configuration (19/20, 0.977 ± 0.094). The updated release uses the sigmoid configuration of Table 5 and keeps the tanh grid for reference.

Comments on the paper

5 comments
AuthorsOpenReview ↗

General Response - Part 1

We thank the reviewers for their careful reading; their comments helped us significantly improve the manuscript. We have tried to keep our answers short, following the guidelines. We invite the reviewers to ask for more detail where useful.

We have not submitted yet a modified PDF, as we would appreciate feedback on our replies before doing that.

Here we address two points raised by multiple reviewers. We address the remaining questions within each reviewer's thread.

Failed runs in the classification experiment

Reviewers ask what explains the 22 of 80 single runs that fail, and whether best-of-4 selection hides an instability of the zigzag gradient. We attribute this to the stochastic subgradient descent (SSD) update rule, which we use to remain compliant with the theorem. To verify this hypothesis, we reran the 80 held-out runs of Table 5 with the Adam optimizer. The initialization, minibatch sequence, and zigzag gradient are the same as in the original runs; only the update rule changes. We fixed all the settings on development draws before any held-out run.

Held-out single runs (of 80)SSD (paper)SSD + C.5 perturbation*Adam, constant rate 3·10⁻⁴
Solved (test accuracy > 0.9)586276
Failures: never reach a low training loss / reach it, then lose it / fit, miss on test15 / 5 / 215 / 3 / 00 / 1 / 3
Splits solved by a single run (mean over seeds, of 20)14.515.519.0

*Note: for details about what C.5 perturbation means, please refer to the answer to the first question of reviewer oe6u. Adam is also run with perturbations.

  • The update rule causes the failures, not the gradient.
    • With the same gradient, Adam solves 76 runs
  • Failing SSD runs are not stuck at the start.
    • At step 25 their gradient norms are similar to those of solved runs (2.3–2.6 against 2.1).
    • Afterwards they grow to 5.9–6.6, while those of solved runs shrink to 0.2.
  • The non-differentiable tied start is not the cause. The C.5 perturbation leaves the 15 never-converging runs unchanged.
  • Per-coordinate gradient scaling is the ingredient that matters. This comes from an ablation on development draws.
    • Adam without momentum solves 79 of 80 runs.
    • Without per-coordinate scaling, no setting does better: heavy-ball momentum reaches at best 60, a normalized step length 55, and SSD's own step-size screen 28–60.
    • Adam with SSD's decaying schedule solves 77, so the decay is not the cause.

Overall, this is evidence that SSD is not as efficient as Adam at finding good local minima.

Our optimization discussion concerns SSD (Definition B.6). Adam lies outside it and is reported as a comparison. With Adam, best-of-4 selection is not needed: a single run solves 19.0 of 20 splits on average.

In the revised draft, we will add these checks to Appendix E.

Given what is found in this ablation, we use the Adam optimizer for the real data experiment, presented below.

AuthorsOpenReview ↗

General Response - Part 2

Real data experiment - Dynamic graph classification

The reviewers agree that an application to real data would strengthen the paper, since both experiments are synthetic. Those experiments were designed as controlled tests with a known answer, which leaves the practical case open. We therefore ran an experiment on an established real-data benchmark. It shows the method at work on real data.

Since the paper's claim concerns differentiability, the baseline is a fixed zigzag pipeline: same complexes, reader and training as the learned pipeline, with the filtering function chosen by hand in the baseline case. The published kernels of Oettershagen et al. are reported for reference.

Data. The four ct2 dynamic graph classification collections of Oettershagen et al. (SDM 2020): Infectious, Highschool, Tumblr and DBLP, with 200, 180, 373 and 755 graphs and 48, 203, 89 and 46 frames. Each graph is a real temporal interaction network carrying a simulated SI epidemic; the label is the infection probability (0.2 vs 0.8).

  • Every person is a vertex at every frame; only edges change.

An edge e = (u, v) has filtering value f_e(t) = c_e(t) · g(a, b) − 1/2, with c_e a decaying memory of the last contact on e, a = max(m_u, m_v), b = min(m_u, m_v), and m_x a decaying memory of the infection time of x.

  • Thresholding f_e at 16 levels gives 16 sequences of graphs, so the reader sees the edge field at several scales. Their zigzag persistence in degrees 0 and 1 is computed by the layer of Section 3, turned into persistence images and read by a 3-D CNN.
  • Fixed (baseline): g is one of two hand-designed ansätze, both natural for an epidemic: exposure, g = a − b, high when one endpoint was infected recently and the other was not (a possible transmission); touching, g = a, high when either endpoint was.
  • Learned: g is piecewise linear on a triangulated 9×9 grid (45 values θ ∈ [0, 1]^45), trained jointly with the reader by the gradient through the zigzag layer, starting exactly at exposure or touching. Each learned run is paired with the identical baseline run, θ held fixed.

Protocol. Stratified 10-fold cross-validation repeated 3 times (30 cells per collection); 20% of each training pool for validation; test prediction at the lowest validation loss.

Test accuracy (%)InfectiousHighschoolTumblrDBLP
Fixed zigzag (baseline), exposure81.1779.8167.5071.70
Learned zigzag, from exposure80.8379.4468.7675.31
Δ learned − fixed−0.33 [−2.33, +1.50]−0.37 [−3.70, +2.78]+1.26 [−0.40, +2.92]+3.61 [+1.88, +5.28]
Fixed zigzag (baseline), touching*78.6779.0768.1764.76
Learned zigzag, from touching79.1781.4868.2474.47
Δ learned − fixed+0.50 [−1.83, +2.83]+2.41 [−0.56, +5.37]+0.07 [−1.09, +1.25]+9.71 [+7.97, +11.47]
Oettershagen et al.:
RD-WL76.3384.4469.7467.57
Stat-WL65.1766.4870.0863.92
DL-RW88.0093.3376.5981.90
SE-RW86.8393.7078.4983.54

Means over 30 cells; Δ is the paired difference, mean [95% paired bootstrap]. *Uses the memory timescales selected for exposure; at its own it scores 68.83 on DBLP.

Results.

  1. The method learns. The gradient through the zigzag layer is a descent direction for the training loss: for small steps in θ, with the pairing recomputed, the loss decreases in 306 of 320 readings, and the training loss decreases on all four collections. Training uses Adam, not the scheme of Definition B.6, so this is an empirical check, not a consequence of Section 3.3.

  2. Learning improves over the baseline on DBLP, with a positive trend on Tumblr and Highschool.

    • DBLP. +3.6 points from exposure, the stronger ansatz, and +9.7 from touching; both intervals exclude zero, and the two starts end at the same level (75.3 vs 74.5).
    • Tumblr (from exposure), Highschool (from touching). +1.26 [−0.40, +2.92] and +2.41 [−0.56, +5.37]: not significant at 95%, but most of each interval lies above zero.
    • Elsewhere (Infectious, Highschool from exposure, Tumblr from touching), test accuracy does not change measurably, although the training loss still decreases. We read this as the ansatz leaving little to add on these collections; on the two smallest, one test graph is worth 5.0–5.6 points of fold accuracy.

The random-walk kernels score higher than every topological pipeline. The experiment shows that the filtering function of a zigzag pipeline can be learned through our layer on real data and can improve over a hand-designed ansatz; it does not show that zigzag pipelines are competitive on this benchmark.

We propose to move this experiment into the main body and the synthetic classification experiment to an appendix. Figures of the results and training losses are in the folder "rebuttal" of https://anonymous.4open.science/r/zzdiff-anon-B57D/.

Thanks for sharing these results. It seems like random-walk based methods perform better than the zigzag pipeline you propose; so it is not clear to me how this experiment makes a strong case for your method. Could you please explain how this experiment is supposed to provide strong empirical evidence for your method?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.