A differentiability framework for zigzag persistent homology via linear interpolation

Enrico Maria Ferrari; Clemens Bannwart; Matteo Biagetti

Figure 4: Example C.18 : an interval broken in the middle (

\mathcal{N}^{\epsilon+}_{p}

). In each panel the upper plot is the piecewise-linear interpolation of the filtering values

v

at

i=0,\dots,N+1

, with the threshold

\epsilon

dashed, and the lower plot is the resulting

H_{0}

barcode on the same time axis. In (a) the value at

i=2

equals

\epsilon

with both neighbours above it, so the exit and the re-entry occur at the same time and cancel as a phantom pair, leaving a single bar. In (b) an arbitrarily small

\delta>0

makes both crossings genuine, and the bar breaks in two.

Figure 5: Example C.19 : an interval of non-vanishing length created from nothing (

\mathcal{N}^{\epsilon,\epsilon}_{p,p+1}

). Same conventions as Figure 4 . In (a) two consecutive values equal

\epsilon

, so

\sigma

never crosses the threshold and the diagram is empty. In (b) raising the first of them by

\delta>0

leaves the value at

i=2

exactly on the threshold, but its right neighbour is now below it, so the configuration is not phantom: the exit is genuine and occurs at

t=2

, producing the bar

\bigl(\tfrac{\epsilon}{\epsilon+\delta},\,2\bigr)

, whose length tends to

1

and not to

0

. In (c) raising both values instead gives the bar

\bigl(\tfrac{\epsilon}{\epsilon+\delta},\,3-\tfrac{\epsilon}{\epsilon+\delta}\bigr)

and the same conclusion holds.

Figure 6: The set

\mathcal{N}_{0}

is represented in red as a subset of

\mathbb{R}^{3|K|}\cong(\mathbb{R}^{3|K|})^{*}=FF_{3}(K)

. The highlighted red lines form

\mathcal{N}^{\epsilon,\epsilon}_{0,1}

, while the transparent red region represents

\mathcal{N}^{\epsilon+}_{0}

. The complementary set of

\mathcal{N}_{0}

is open and connected.

Figure 7: The arena. Left: with no robots each of the nine cells is a hole, so the

1

-Betti number

\beta_{1}=9

; the two circles on one sensor are the Rips radius

R=1.05

, which reaches the four side neighbours and not the diagonals, and the sensing radius

R_{S}=0.61

; the pink diamonds are the area no sensor covers, the cell centres lying

0.707

from their corners. Right: three robots fill three cells,

\beta_{1}=6

. Three robots can never close more than a third of the arena at once, which is why the total hole-time is close to a fixed budget and its distribution in time is the quantity at issue.

strategy	$\mathcal{L}_{\text{topo}}$ : init $\to$ final	longest bar	area $>\Delta$
count (at $\Delta=6$ )	$244.8\to 211.0$	$21.6$ ( $11.3$ – $29.0$ )	$2.7\%$ ( $2.3$ – $3.2$ )
lifetime, $\Delta=6$	$507.9\to 33.8$	$\phantom{0}9.4$ ( $\phantom{0}8.0$ – $10.9$ )	$1.9\%$ ( $0.7$ – $2.9$ )
lifetime, $\Delta=8$	$310.7\to 17.2$	$11.1$ ( $\phantom{0}9.0$ – $13.9$ )	$0.7\%$ ( $0.4$ – $1.9$ )
lifetime, $\Delta=10$	$180.1\to\phantom{0}6.7$	$11.8$ ( $10.3$ – $16.2$ )	$0.5\%$ ( $0.1$ – $1.2$ )
lifetime, $\Delta=12$	$\phantom{0}96.9\to\phantom{0}5.4$	$13.8$ ( $12.3$ – $21.0$ )	$0.1\%$ ( $0.0$ – $0.9$ )

Appendix

Table 1: Topological results of the three-robots-experiment, for count and lifetime strategies, the last with four different tolerance

\Delta

values. The count objective carries no

\Delta

, so its waiting area is computed for

\Delta=6

.

robots	strategy	$\mathcal{L}_{\text{topo}}$ : init $\to$ final	longest bar	area $>\Delta$
$2$	count	$250.8\to 227.9$	$25.4$ ( $19.9$ – $29.0$ )	$3.4\%$ ( $3.1$ – $3.6$ )
$2$	lifetime	$996.2\to 144.6$	$12.4$ ( $10.6$ – $15.9$ )	$3.3\%$ ( $2.7$ – $3.7$ )
$3$	count	$244.8\to 211.0$	$21.6$ ( $11.3$ – $29.0$ )	$2.7\%$ ( $2.3$ – $3.2$ )
$3$	lifetime	$507.9\to 33.8$	$\phantom{0}9.4$ ( $\phantom{0}8.0$ – $10.9$ )	$1.9\%$ ( $0.7$ – $2.9$ )
$4$	count	$239.2\to 197.0$	$17.1$ ( $\phantom{0}9.6$ – $24.6$ )	$1.8\%$ ( $1.3$ – $2.4$ )
$4$	lifetime	$250.4\to 14.8$	$\phantom{0}8.9$ ( $\phantom{0}6.7$ – $10.9$ )	$0.5\%$ ( $0.0$ – $1.3$ )

Appendix

Table 2: Robot-count ladder, lifetime objective at

\Delta=6

throughout.

strategy	condition	$\mathcal{L}_{\text{topo}}$ : init $\to$ final	longest bar	area $>\Delta$
lifetime	gradient and noise (reported)	$507.9\to 33.8$	$\phantom{0}9.4$ ( $\phantom{0}8.0$ – $10.9$ )	$1.9\%$ ( $0.7$ – $2.9$ )
lifetime	gradient only, $\sigma=0$	$507.9\to 48.7$	$10.6$ ( $\phantom{0}7.3$ – $29.0$ )	$2.1\%$ ( $0.7$ – $3.4$ )
lifetime	motion only, $\mathcal{L}_{\rm topo}$ removed	$507.9\to 530.9$	$21.3$ ( $18.9$ – $29.0$ )	$2.2\%$ ( $2.0$ – $2.8$ )
count	motion only, $\mathcal{L}_{\rm topo}$ removed	$244.8\to 246.7$	$21.3$ ( $18.9$ – $29.0$ )	$2.2\%$ ( $2.0$ – $2.8$ )

Appendix

Table 3: Three experiments with three robots and

\Delta=6

: stochastic optimization, optimization without noise (gradient only), stochastic optimization without topological term (motion only). In the motion only rows the topological term is removed from the loss, so both strategies give the same run: each row reads its own term along that path, evaluated but not optimized.

Figure 8: The count strategy along the iterate sequence, held-out seeds

10

–

19

, median bold and seeds faint, logarithmic iteration axis. Left: the count term

\mathcal{L}_{\rm topo}=\sum_{(b,d)\in D}(d-b)

on a linear value axis; it descends by

14\%

and no more, because with three robots at least six of the nine cells are open at every instant and the loss has a hard floor. Right: the total loss

\mathcal{L}

, logarithmic value axis; the peak at

k=2

is the first perturbation breaking the unit-speed penalty (which was satisfied by the random walk initialization), and the curve ends

1.1

above

\mathcal{L}_{\rm topo}

.

Figure 9: Left: the topological term at the iterate for the lifetime objective at each tolerance, medians over held-out seeds

10

–

19

, logarithmic axes. Right: the longest

H_{1}

bar at the same iterates, each condition against its own

\Delta

(dashed, matching colours). The objective goes on descending for the whole run at every tolerance.

Figure 10: The total objective

\mathcal{L}

of the lifetime strategy at each tolerance, penalties included, medians over held-out seeds

10

–

19

, logarithmic axes.

Figure 11: The designed task. (a) One figure-eight: two loops sharing a node, each closed while its switch vertex is active. (b) The switch patterns defining the two classes, slow against fast. (c) The resulting Betti curves, identical between the classes at every frame, so a per-frame reading has nothing to separate. (d) The zigzag barcodes of one example of each class under the filtering function the generator knows, at the threshold of the experiment: three bars with the longest at

0.48

against seventeen with the longest at

0.06

.

setting	value	why
$\gamma_{0}$	$0.02$	scanned over $\{0.01,0.02,0.03,0.05,0.1\}$ ; the optimum is interior, larger steps moving the field further and classifying worse
$\alpha$	$0.6$	in $(1/2,1]$ , matching the step-size condition of Proposition B.7 , which on its own brings none of its other hypotheses;
iterations	$3\,200$	at $800$ the loss is still falling when the schedule has decayed the step to nothing; four times the budget removes that truncation
minibatch	$16$ , uniform with replacement	the sampling of Definition B.6
ridge $\lambda$	$10^{-4}$	no measurable effect in development
amplification	$30$	the rescaling of the graph convolution’s weights; without it the graph convolution barely moves beside the reader (Appendix E.1 )

Appendix

Table 4: Stage-2 settings and why they take these values. All were fixed on development draws of the generator, none of which the reported results come from.

read-out	field	runs	solved	accuracy
zigzag	learned	best of 4	$\mathbf{20/20}$	$\mathbf{0.995\pm 0.016}$
		single	$58/80$	$0.893\pm 0.178$
per-frame persistence	learned	best of 4	$0/20$	$0.755\pm 0.112$
		single	$0/80$	$0.635\pm 0.136$
zigzag	signal-only	reader only	$20/20$	$1.000\pm 0.000$
per-frame persistence	signal-only	reader only	$0/20$	$0.500\pm 0.000$

Appendix

Table 5: Temporal-graph classification on the same twenty held-out splits; final-iterate test accuracy, chance

=0.500

; solved counts splits above

0.9

. Learned variants: best of four seeds by final validation loss, and all

80

single runs.

Figure 12: Loss of the runs the protocol keeps: on each of the twenty held-out splits, the seed with the lowest final validation loss among four, which solves its split in every case. Faint lines are the individual validation curves; the solid line is their mean, the dashed line the mean training loss. Both axes logarithmic; the dotted line marks

\ln 2

, the loss at chance.

A differentiability framework for zigzag persistent homology via linear interpolation

Abstract

Figures & tables

Appendix

Explore similar work

Towards Scalable Persistence-Based Topological Optimization

Topological data analysis using persistent discrete homology

Contraction and Hourglass Persistence for Learning on Graphs, Simplices, and Cells