Alessio Borgi

Alessio Borgi

PhD in Graph Neural Networks and Generative AI 👨🏻‍💻🤖

Zigzag Persistence: Topology Along a Non-Monotone Path

2 minute read

Published:

TL;DR: Zigzag persistence handles sequences K₁ ↔ K₂ ↔ ⋯ ↔ Kₙ where arrows can go in either direction (inclusions or deletions). Algebraically, it replaces the persistence module (linear maps between vector spaces in one direction) with a module over a quiver with arbitrary orientations. The interval decomposition theorem still holds, giving a well-defined barcode.

The Limitation of Standard Persistence

In standard persistence, we require \(K_0 \subseteq K_1 \subseteq \cdots \subseteq K_n\): simplices can only be added. This fails for:

  • Time-varying data: points appear and disappear as time progresses.
  • Sliding window analysis: the window moves, so old points leave and new ones enter.
  • Level set analysis: topology of \(f^{-1}(a)\) as \(a\) moves up and down.
  • Data with missing observations: sensors fail and recover.

Zigzag Sequences and Modules

A zigzag filtration is a sequence of simplicial complexes connected by maps that can go in either direction:

$$K_1 \leftrightarrow K_2 \leftrightarrow K_3 \leftrightarrow \cdots \leftrightarrow K_n$$

where each \(\leftrightarrow\) is either an inclusion (\(K_i \hookrightarrow K_{i+1}\)) or a deletion (\(K_i \hookleftarrow K_{i+1}\)). Applying \(H_n\) gives a sequence of vector spaces connected by linear maps in alternating directions — a zigzag module over the quiver \(1 \leftrightarrow 2 \leftrightarrow \cdots \leftrightarrow n\).

Interval Decomposition

Theorem (Carlsson & de Silva 2010): Every zigzag module over a field decomposes uniquely (up to isomorphism) as a direct sum of interval modules \(\mathbb{I}[b,d]\).

Each interval module \(\mathbb{I}[b,d]\) contributes one persistence bar from index \(b\) to \(d\). The resulting zigzag persistence diagram has the same form as standard persistence diagrams and carries the same topological information — the birth and death of homological features.

Key difference from standard persistence: In standard persistence, birth always precedes death and both correspond to simplex additions. In zigzag persistence, a feature can be “born” at a deletion (when a cycle becomes a boundary) and “die” at an addition (when it gets filled in).

Computing Zigzag Persistence

The standard persistence algorithm (boundary matrix reduction) does not directly apply to zigzag modules. Carlsson and de Silva gave an algorithm based on a “diamond principle”: whenever two adjacent maps change direction (forming a diamond), the persistence of the involved generators can be updated with local modifications. The resulting algorithm runs in \(O(n^3)\) time.

Key Insight: Zigzag persistence is the right tool for temporal point cloud data. For a trajectory of point clouds P₁, P₂, ..., Pₙ, define K_i = Rips(Pᵢ, r) and connect adjacent complexes via their union: K_i ↪ K_i ∪ K_{i+1} ↩ K_{i+1}. The resulting zigzag filtration captures which topological features are persistent across time — surviving both appearances and disappearances of points.

References

  • G. Carlsson & V. de Silva, “Zigzag Persistence,” Foundations of Computational Mathematics, 2010. arXiv:0812.0197.
  • S. Oudot, Persistence Theory: From Quiver Representations to Data Analysis, AMS, 2015.

You May Also Enjoy

GAPE: Remember to Forget — Gated Adaptive Positional Encoding

4 minute read

Published:

GAPE is a drop-in RoPE augmentation that adds content-aware attention logit biases: a query-gate suppresses irrelevant distant context while a key-gate preserves salient distant tokens. Provably sharper attention and improved long-context robustness — no architecture changes needed.

PolyNSD: Polynomial Neural Sheaf Diffusion

4 minute read

Published:

PolyNSD replaces the NSD propagation operator with a degree-K Chebyshev polynomial in the normalised sheaf Laplacian, achieving SOTA on homo- and heterophilic benchmarks with only diagonal restriction maps and dramatically lower memory usage.

TDA in Materials Science: Topology of Structure and Phase

3 minute read

Published:

Persistent homology characterises the multi-scale structure of materials — from pore geometry in catalysts to glass transition in amorphous materials. H₀ captures connectivity, H₁ captures channels and rings, H₂ captures enclosed voids. These topological descriptors predict mechanical properties, adsorption capacity, and phase transitions more accurately than geometric averages.

TDA in Drug Discovery: Molecular Topology

3 minute read

Published:

Persistent homology provides multi-scale topological fingerprints of molecular structures — capturing rings, cavities, and protein pockets that traditional cheminformatics descriptors miss. Applications include binding site detection, ADMET property prediction, and protein-ligand interaction modelling.