CS Paper Radar

Bridging persistence of discrete and continuous 1D maps: Total variation, permutation equivalence, and diagonal affine transformations

Matthew Blake, Firas A. Khasawneh

cs.CG math.AT ·submitted 2026-10-22 14:54 UTC · v1

Abstract

Fundamental to the field of topological signal processing (TSP) is the \textit{persistence diagram} (PD), or barcode, of a signal, which gives noise-resistant measures of topologically significant features as distinct from noise. Existing literature proves that the total persistence computed from these diagrams is equal to the total variation, for certain continuous signals on compact domains. We provide a closed formula for this shared quantity, and generalize to all continuous and discrete functions on bounded domains, and to certain functions on non-compact 1D manifolds. Extending the identification of continuous and discrete persistence, we investigate the similarities of functions with the same PDs, and prove that, for any $n$, the persistence diagram can be calculated as a function of the sequence of critical values; we compute these formulas for $n \leq 6$. Finally, we examine which function transformations cause predictable changes in the PD of the transformed function, characterizing affine and linear transformations.

Comment
60 pages, 24 figures

Closest papers

Nearest neighbours by meaning across the whole index.

A differentiability framework for zigzag persistent homology via linear interpolation

cs.LG cs.CGmath.AT ·2026-09-30 ·Enrico Maria Ferrari, Clemens Bannwart, Matteo Biagetti
positiontheory similarity 0.61
Abstract · 9+31 pages, 12 figures, comments welcome!

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.

0.38

New persistent chain spaces: identifying and computing the relevant persistent Laplacians of a filtration

cs.CG math.ATmath.COmath.SP ·2026-11-06 ·Joris Kirchner, Martina Vittorietti
similarity 0.57
Abstract · 34 pages, 12 figures

Persistent homology (PH) summarizes the topological features of data that persist across scales, but it is insensitive to many geometric properties. Persistent Laplacians (PLs) address this limitation: for a pair of simplicial complexes in a filtration, the kernel of the persistent Laplacian recovers the persistent Betti number, while its non-zero spectrum carries additional geometric information. However, PLs are defined for individual pairs of filtration values, so analysing a whole filtration requires evaluating many operators that largely contain the same information, and the result is hard to summarize and interpret. In this paper, we show that this redundancy has a precise structure. For each pair of filtration values, we decompose the space of chains underlying the persistent up-Laplacian into the contributions inherited from the neighboring pairs and a remaining part, which we call the new persistent chain space. We show that the new persistent chain spaces of all earlier pairs form a direct sum decomposition of this space, so that every persistent up-Laplacian in the filtration is determined by them. Moreover, the new persistent chain spaces are non-trivial only at pairs given by the persistence pairing in the same and in the next homological dimension, so that the persistence pairing determines exactly where the persistent up-Laplacian can change. Experiments on several types of point clouds show that evaluating persistent Laplacians only at these pairs reduces the computation time, both for our implementation and for existing software.

0.37

Persistence Meets Resistance: Doubling Down on Hardness

cs.CC math.ATcs.CG ·2026-08-27 ·Benedikt Kolbe, Tim Mayr
top venue similarity 0.53
Abstract · Conference version published at ICALP 2026. https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2026.131

We present results on the approximate computation of stable invariants for filtrations of finite metric spaces in the context of persistent homology. We establish novel approximation algorithms in the setting of $n$-point metric spaces where the growth of the doubling dimension is in $o(\log n)$ and the diameter is bounded. In the $1$-parameter case, by revisiting known techniques (greedy permutations) in a new way, we derive the first linear-time algorithms for the problem of computing additive $\varepsilon$-approximations of any stable barcode. By deriving bounds on the convergence rate and the approximation quality of uniform samples, we extend the approach to selected multiparameter filtrations. We show that for normalized measure bifiltrations, including the multicover and subdivision-Rips bifiltration, any stable invariant can be probabilistically approximated in time constant in $n$. The constants in the running times of our algorithms depend on the doubling dimension, the diameter and the success probability. We further study the problem through the lens of fine-grained complexity and show that computing the rank of a matrix reduces to that of approximating the barcode of the Vietoris--Rips or Čech filtration. We present two variants of the reduction, one for sufficiently good additive approximations and the other for any constant factor multiplicative approximations.

0.55

Message-passing graph persistence

cs.LG cs.AIstat.ML ·2026-11-04 ·Jorge Luiz Franco, Arthur Queiroz Moura, Moacir Ponti, Amauri Souza
benchmarktheory similarity 0.53
Abstract

Message-passing graph neural networks (GNNs) are limited in expressive power by the one-dimensional Weisfeiler-Leman test. Persistent homology (PH) provides topological descriptors that can complement GNN representations, but existing approaches typically compute persistence separately from the representation learning process. In this paper, we introduce Message-Passing Graph Persistence (MGP), a family of topological descriptors that incorporates message passing into graph filtrations. At each filtration step, node embeddings are updated using the current subgraph and associated with persistence events. These embeddings also determine the representatives of connected components during persistence computation. We prove that MGP is invariant under graph isomorphism and that it is strictly more expressive than the PH-based descriptors it extends. We evaluate MGP on an expressivity benchmark and on several graph classification and regression datasets. Experiments show that MGP outperforms other PH-based descriptors on most of these datasets.

0.17

Topological Signal Processing With Unoriented Operators

cs.LG ·2026-09-21 ·Andrea Cavallo, Varun Sarathchandran, Geert Leus, Elvin Isufi
similarity 0.52
Abstract

Topological signal processing (TSP) processes signals on simplicial complexes with oriented boundary operators, which is the natural choice for flow signals or when the topological invariants play a role for the task at hand. However, many higher-order signals carry no orientation, and applying oriented operators to them is not well-defined since it introduces an arbitrary choice of simplex orientation. We study an unoriented TSP (UTSP) framework that replaces oriented boundaries with unoriented incidence matrices. First, we show that unoriented incidence and Laplacian matrices between arbitrary simplicial levels admit graph-like spectral properties. Second, since dropping orientation removes the Hodge decomposition, we introduce an unoriented counterpart, termed interaction-order decomposition, which quantifies how much of a higher-order signal is explained by aggregating lower-order signals. Third, we use this decomposition to derive regularizers for signal reconstruction that penalize each interaction order separately. Experiments on real-world data show that the order-aware regularizers outperform oriented baselines, with the largest gains when the signal energy is unevenly distributed across orders.

0.20

Persistence Positional Encoding: A Minimal Transformer Recipe for Persistence Diagrams

cs.LG ·2026-10-13 ·Eunwoo Heo, Ganghyun Kim, Jaejun Yoo
theory similarity 0.52
Abstract · 25 pages, 6 figures

Persistence diagrams (PDs) represent multiscale topological information as multisets of birth-death pairs $(b,d)$. How best to use them with Transformers, however, remains unclear. Connecting PDs to Transformers requires choosing how topological information is tokenized and exposed to self-attention. Prior methods use specialized designs for tokenization, aggregation, Transformer blocks, or attention, but are hard to compare since reported results rarely share PD inputs, splits, or model-selection rules. We instead confine the diagram-specific design to point representation, mapping each birth-death pair through fixed random Fourier features while leaving the Transformer backbone unchanged, and call this recipe Persistence Positional Encoding (PPE). In matched controls on eight TU graph benchmarks (TU8), changing only point representation shifts macro accuracy by 5.49 to 6.47 percentage points (pp), against 0.47 to 1.45 pp from changing the downstream module, identifying point representation as the dominant design variable tested. We further reevaluate vectorizations, kernels, learned representations, and Transformer-based models under one protocol with shared PD inputs, outer folds, and validation-only selection. Among all evaluated PD methods and downstream configurations, PPE achieves the highest mean on most benchmarks, including TU8, ORBIT5K, and MCB-C. Finally, we prove that grid averaging leaves a reconstruction error at any resolution, whereas a Transformer with fixed random Fourier frequencies is almost surely universal. PPE thus offers a minimal, Transformer-native baseline for persistence diagrams, and a common protocol for future comparison.

0.28

Graph Representation via Elements of Discrete Morse and Cobordism Theories

cs.LG math.GN ·2026-10-01 ·Jennifer Rozenblit, Chenguang Yang, Yuxin Liu, Yuzhou Chen, Yulia Gel
similarity 0.52
Abstract

Topology is, by its nature and design, suited to structure that is nonlinear, multiscale, and nonstationary - however, within machine learning, its use remains largely confined to topological data analysis. We advocate that tools from low-dimensional topology which have remained almost exclusively contained within the domain of pure mathematics (such as Morse theory) offer a strong, complementary, and yet virtually unexplored perspective on the hidden structure of data-generating processes and learning tasks built upon them. Here we introduce concepts from cobordism theory and harness tools from discrete Morse theory to improve the performance of graph diffusion models through our pipeline MG-Diff. Further, we derive theoretical guarantees and sufficient conditions so that under a positive decision-gap, the Morse-theoretic tools and their application for induced diffusion guidance are stable under small perturbations. Finally, we illustrate the utility of discrete Morse theory in application to graph diffusion models for spatio-temporal graph forecasting and graph regeneration, and argue that these applications are only a small window into the part of what low-dimensional topology can offer to the field of machine learning.

0.24

Sierpiński--Knopp Wasserstein Distance for Persistence Diagrams and Applications to 2-Wasserstein Approximation

cs.CG cs.LG ·2026-09-01 ·Sebastien Tchitchek, Julien Tierny
benchmarkcode/data similarity 0.51
Abstract · 49 pages, 11 figures, 6 tables. Code and reproducibility package: https://github.com/sebastien-tchitchek/SK-Wasserstein-Reproducibility

This paper introduces the Sierpiński-Knopp (SK) Wasserstein distance, a fast metric between persistence diagrams. The SK-Wasserstein distance, denoted $d_{\mathrm{SK}}$, maps diagram points and their diagonal projections to the unit interval via the Sierpiński-Knopp space-filling curve on the upper diagonal triangle. The encoded point sets are then efficiently matched via one-dimensional optimal assignment, in \(O(N\log N)\) steps, yielding an explicit diagonal-aware point assignment between the two input persistence diagrams. We show that the SK-Wasserstein distance controls the classical \(2\)-Wasserstein distance between diagrams, admits an explicit isometric embedding into a Hilbert space, and induces a positive-definite Gaussian kernel, making the resulting geometry directly compatible with Euclidean and kernel-based learning methods. A tighter surrogate dissimilarity, noted \(W_Γ\), is also introduced based on the point assignments along the curve. Experiments on 12 scientific collections comprising 227 diagrams show median per-collection speedup of \(d_{\mathrm{SK}}\) over state-of-the-art approximations of \(W_2\) is \(626\times\), while the aggregate speedup over the full benchmark is \(2100\times\). Average-linkage partitions obtained from \(d_{\mathrm{SK}}\) and \(W_Γ\) each exactly match the corresponding \(W_2\) partition on 8 of the 12 collections. Hilbert \(k\)-means and Gaussian spectral clustering, both based on \(d_{\mathrm{SK}}\), achieve mean adjusted Rand indices (ARI) of \(0.756\) and \(0.800\), respectively, with respect to the benchmark reference partitions, compared to \(0.750\) obtained by average linkage on \(W_2\). The Gaussian \(d_{\mathrm{SK}}\) kernel supports other kernel-based analysis tasks, as illustrated by its use for contiguous segmentation of ordered diagram collections in our experiments.

0.49