Alessio Borgi

Alessio Borgi

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

The Interleaving Distance and Algebraic Stability

2 minute read

Published:

TL;DR: Two persistence modules M and N are ε-interleaved if there exist module maps φ: M → N(ε) and ψ: N → M(ε) that compose to the canonical shift map. The interleaving distance d_I(M,N) is the infimum of ε for which such an interleaving exists. The isometry theorem (Bauer & Lesnick) proves d_I = d_B — matching the bottleneck distance.

Persistence Modules

A persistence module \(M\) over \(\mathbb{R}\) is a functor from \((\mathbb{R}, \leq)\) to \(\mathbf{Vect}\): a collection of vector spaces \(\{M_t\}_{t \in \mathbb{R}}\) with linear maps \(\phi^M_{s \leq t}: M_s \to M_t\) for \(s \leq t\), satisfying \(\phi^M_{t \leq t} = \mathrm{id}\) and \(\phi^M_{s \leq t} \circ \phi^M_{r \leq s} = \phi^M_{r \leq t}\).

For a filtration \(K^*\), taking \(n\)-th homology gives a persistence module \(H_n(K^*)\).

The Shift Functor

For \(\varepsilon \geq 0\), the \(\varepsilon\)-shift \(M(\varepsilon)\) of a persistence module \(M\) is defined by \(M(\varepsilon)_t = M_{t+\varepsilon}\). There is a natural map \(\eta_\varepsilon^M: M \to M(\varepsilon)\) induced by the module maps.

ε-Interleavings

Two modules \(M\) and \(N\) are \(\varepsilon\)-interleaved if there exist natural transformations:

\[\varphi: M \to N(\varepsilon) \qquad \text{and} \qquad \psi: N \to M(\varepsilon)\]

such that:

$$\psi(\varepsilon) \circ \varphi = \eta_{2\varepsilon}^M \qquad \text{and} \qquad \varphi(\varepsilon) \circ \psi = \eta_{2\varepsilon}^N$$

Intuitively: \(M\) and \(N\) look the same up to a shift of \(\varepsilon\). The interleaving distance is:

\[d_I(M, N) = \inf\{\varepsilon \geq 0 : M \text{ and } N \text{ are } \varepsilon\text{-interleaved}\}\]

The Isometry Theorem

Theorem (Chazal et al. 2009; Bauer & Lesnick 2015 for the isometry):

\[d_I(M, N) = d_B(\mathrm{dgm}(M), \mathrm{dgm}(N))\]

where \(d_B\) is the bottleneck distance between persistence diagrams. This means:

  1. The interleaving distance and bottleneck distance are equal (not just bounded by each other).
  2. The map \(M \mapsto \mathrm{dgm}(M)\) is an isometry from the space of tamely decomposable persistence modules (with interleaving distance) to persistence diagrams (with bottleneck distance).
Key Insight: The isometry theorem is why stability results for persistence diagrams are tight. Every bottleneck distance result (e.g., "a Lipschitz function perturbation changes diagrams by at most the Lipschitz constant × perturbation size") follows from constructing an explicit interleaving between the corresponding persistence modules. The algebraic language makes proofs cleaner and generalisable to arbitrary functors.

References

  • F. Chazal et al., “Proximity of Persistence Modules and Their Diagrams,” SoCG 2009.
  • U. Bauer & M. Lesnick, “Induced Matchings of Barcodes and the Algebraic Stability of Persistence,” SoCG 2015. arXiv:1311.3681.

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.