Topological Autoencoders

Michael Moor; Max Horn; Bastian Rieck; Karsten Borgwardt

Source-linked AI summary

Topological Autoencoders

Michael Moor, Max Horn, Bastian Rieck, Karsten Borgwardt

arXiv:1906.00722v5Jun 3, 2019cs.LGmath.ATstat.ML

TL;DR

Autoencoders do not ordinarily preserve the input space’s multi-scale topological structure, while persistent-homology computations are difficult to differentiate. The paper makes these computations compatible with backpropagation and uses them to align input and latent topology. Experiments show interpretable representations and competitive quality metrics without adversely affecting reconstruction error.

Problem
Using topological signatures as constraints for deep learning is difficult because persistent-homology computations are inherently discrete and hard to differentiate.
Method
The method computes persistent homology for input mini-batches and latent codes, then uses their topological differences as a differentiable autoencoder loss.
Results
The method preserves topological structures in synthetic and real-world data, including spatial relationships between nested high-dimensional spheres, while maintaining competitive metrics and reconstruction errors.
Takeaways & Limitations
The learned representations can arrange classes meaningfully rather than merely separating them into distinct clouds, supporting interpretability.
Takeaways & Limitations
The current implementation supports no higher-dimensional features, so experiments focus on 0-dimensional persistence diagrams.

Abstract

from arXiv · show

We propose a novel approach for preserving topological structures of the input space in latent representations of autoencoders. Using persistent homology, a technique from topological data analysis, we calculate topological signatures of both the input and latent space to derive a topological loss term. Under weak theoretical assumptions, we construct this loss in a differentiable manner, such that the encoding learns to retain multi-scale connectivity information. We show that our approach is theoretically well-founded and that it exhibits favourable latent representations on a synthetic manifold as well as on real-world image data sets, while preserving low reconstruction errors.

1. Introduction

The paper addresses the difficulty of differentiably using persistent-homology computations as constraints in deep learning. It introduces a topological autoencoder that aligns data-space and latent-space topology through a new loss.

Persistent-homology computations are inherently discrete, making backpropagation through topological signatures difficult except in special circumstances.
The proposed approach obtains gradients during topological-signature computation, enabling topological constraints in deep neural-network training.
The topological loss harmonises the topology of the data space with that of the latent space.
Mini-batch stability is proved, providing suitable approximations to a dataset’s persistent homology.
Experiments show that preserving topological structures can aid dimensionality reduction and improve interpretability of learned latent representations.

2. Background: Persistent Homology

Persistent homology tracks connectivity-based features across multiple distance scales using nested Vietoris–Rips complexes and persistence diagrams. These diagrams summarize when topological features appear and disappear, providing signatures that can be compared between spaces.

2. Background: Persistent Homology: Persistent homology analyzes dataset topology, including connected components, cycles or tunnels, and voids, through homology groups.The dth homology group records d-dimensional topological features.
2. Background: Persistent Homology: Because the underlying manifold is unknown, persistent homology tracks homology changes across multiple metric scales rather than using one simplicial-complex approximation.
2. Background: Persistent Homology: Vietoris–Rips complexes contain point subsets whose pairwise distances are at most ϵ and are nested as ϵ increases.This nesting enables topological changes to be tracked across scales.
2. Background: Persistent Homology: Persistence diagrams record the creation and destruction thresholds of d-dimensional topological features.A point (a, b) stores the thresholds at which a feature is created and destroyed.
2. Background: Persistent Homology: Persistence pairings identify the simplices responsible for creating and destroying the features represented in persistence diagrams.
2. Background: Persistent Homology: Persistence diagrams are stable under small data perturbations and can be compared using the bottleneck distance.
2. Background: Persistent Homology: The method compares persistence diagrams computed on input mini-batches and corresponding latent codes to constrain latent representations.

3. A Topology-Preserving Autoencoder

The method constrains autoencoders to preserve topology by comparing persistent-homology-derived distances in data and latent mini-batches. It uses selected topologically relevant edges, bidirectional loss components, and differentiable updates, while mini-batch topology approximates the full data set under the stated assumptions.

Framework: The framework computes persistent homology in data and latent spaces to constrain autoencoders toward topology-preserving representations.The persistent-homology outputs include persistence diagrams and pairings for each space.
Vietoris–Rips Complex Calculation: Persistent-homology pairings identify topologically relevant edges because Vietoris–Rips complexes are fully determined by their edges.For 0-dimensional features, destroyer edges correspond to edges in the data set’s minimum spanning tree.
Topological Autoencoder: The loss uses two directed components, LX→Z and LZ→X, to align selected distances between data and latent spaces.If both spaces align perfectly, both directed losses are zero, although zero total loss does not necessarily imply identical persistence pairings.
Topological Autoencoder: The selected-edge union produces an informative regulariser based on at least |X| distances and is added to reconstruction loss with strength controlled by λ.The formulation compares distances across both spaces rather than matching only their shared selected edges.
Gradient Calculation: The loss is differentiable for each training update because persistence diagrams are stable under infinitesimal perturbations, despite changing nondifferentiably across training.The derivation assumes unique distances and infinitesimal perturbations.
Mini-batch Stability: The mini-batch approximation converges in expected Hausdorff distance as the batch size approaches the full sample size, making subsamples suitable proxies for large-scale topology.The stated result is E[dH(X, Xm)] = 0 as m → n.

4. Related Work

Related work has largely used persistent homology to analyze topological characteristics after embedding, while direct topology-based optimization has only recently become feasible. The proposed approach differs from earlier optimization work by operating directly on distances without requiring known connectivity.

Existing Uses: Persistent homology is often used post hoc to compare topological features across high-dimensional spaces and embeddings.These comparisons assess embedding fidelity and quality.
Topology-Based Optimization: Poulenard et al. demonstrated topology-based optimization of real-valued functions, but required known data connectivity and node-based scalar-valued functions.Their work was described as the first approach for aligning persistence diagrams by modifying input data.
Topology-Based Optimization: The proposed method operates directly on distances and avoids connectivity calculations through the Vietoris–Rips construction.This distinguishes it from the cited earlier optimization approach.

5. Experiments

The experiments evaluate whether TopoAE preserves topology in two latent dimensions across synthetic and image data while maintaining reconstruction quality. Results show strong density preservation and structurally meaningful embeddings, although classical metrics can favor baselines that miss global structure.

Experimental setup: TopoAE learns two-dimensional latent representations for SPHERES, MNIST, FASHION-MNIST, and CIFAR-10, alongside comparisons with UMAP, t-SNE, Isomap, PCA, and standard autoencoders.The evaluation uses visualisations, dimensionality-reduction metrics, and reconstruction error; autoencoder-based methods use invertible transformations for reconstruction evaluation.
Evaluation criteria: The evaluation measures visual quality, dimensionality-reduction metrics, and Data MSE reconstruction error, with KLσ varying the Gaussian-kernel length scale to assess density across multiple scales.Hyperparameters are selected by minimising KL0.1, while Data MSE is evaluated where invertible transformations are available.
Quantitative results: TopoAE preserves data density over multiple length scales and achieves competitive ℓ-Cont and Data MSE without large reconstruction impairments.The authors present the reconstruction result as evidence that imposing topological constraints does not substantially harm reconstruction.
Quantitative results: Classical measures often favor baselines, especially t-SNE’s training performance, but the authors report that these measures can miss relevant structural information.The mismatch is illustrated by the SPHERES manifold, where visual and KL assessments disagree with several classical metrics.
Visualisation of latent spaces: On SPHERES, only TopoAE correctly represents the nesting relationship, whereas t-SNE cuts open the enclosing sphere and distributes its points around the inner spheres.The enclosing sphere contains half of the data, and KL divergence confirms the visual assessment that TopoAE preserves the relevant structure.
Visualisation of latent spaces: On image data, TopoAE organises FASHION-MNIST similarly to UMAP, preserves cluster relationships on MNIST, and consistently identifies a linear two-group substructure in CIFAR-10.The authors also report that t-SNE fragments some FASHION-MNIST classes and that CIFAR-10 is difficult to embed unsupervised in two dimensions.

6. Discussion and Conclusion

The paper concludes that persistent-homology-based topological autoencoders can preserve meaningful structure in latent representations while retaining competitive reconstruction and quality metrics. The formulation is broadly applicable, but its computational cost worsens for higher-dimensional features and larger batches.

Discussion and Conclusion: TopoAE combines persistent-homology calculations with backpropagation and uses theoretically justified mini-batch approximations.The method is designed to preserve input-space topological information in deep-neural-network latent encodings.
Discussion and Conclusion: Across synthetic and real-world data, TopoAE captures nested-sphere relationships, achieves competitive quality metrics, and does not adversely affect reconstruction error.The authors also report interpretable representations that spatially arrange classes rather than merely separating them into distinct clouds.
Discussion and Conclusion: TopoAE produces entangled structures viewed as more meaningful representations of underlying manifolds, with supplementary analysis indicating beneficial influence on persistent-homology features.This conclusion concerns both synthetic and real-world experiments.
Future work: The loss can extend to architectures requiring only pairwise distances, including variational autoencoders and a topology-aware PCA variant.The paper presents these extensions as future-work directions rather than as the main evaluated method.
Future work: For higher-dimensional features, calculating Rε can scale progressively worse with increasing batch size, although low-dimensional experiments still show mini-batch speed-up dominating runtime.The computational boundary is tied to the complexity of the Vietoris–Rips calculation.

A.1. Persistent Homology Calculation Details

Persistent homology tracks topological activity across a filtration rather than relying on a single simplicial complex, producing persistence diagrams that record feature lifetimes across scales.

Motivation: Ordinary Betti numbers are often too coarse and sensitive to small changes, motivating persistent homology for point-cloud data with unknown underlying manifolds.The method tracks changes over multiple scales instead of selecting one potentially unstable simplicial complex.
Persistent homology: Persistent homology studies topological features by applying simplicial homology across a nested sequence of simplicial complexes called a filtration.The Vietoris–Rips filtration is defined from a distance function, such as Euclidean distance.
Persistent homology: The dth persistent homology group captures homology classes created at one filtration stage that remain active at a later stage.Its rank defines a persistent Betti number, extending ordinary Betti numbers to indexed pairs of filtration stages.
Persistence diagrams: Persistence diagrams replace filtration indices with real-valued feature birth and death thresholds, providing a fine-grained summary of topological activity.Each diagram entry stores a pair (a, b) associated with a feature created at a and destroyed at b.
Persistence diagrams: For Vietoris–Rips filtrations, feature persistence is measured by the absolute difference between its creation and destruction thresholds.For connected components, creation occurs at a = 0, while destruction corresponds to an edge used in the minimum spanning tree.

A.2. Proof of Theorem 1

Theorem 1 bounds the probability that a subsample’s persistence diagrams differ beyond a threshold, using Hausdorff distance and persistent-homology stability.

Theorem 1: Theorem 1 bounds the probability that persistence diagrams of a size-m subsample exceed a threshold in terms of the bottleneck distance.The subsample is drawn without replacement from a point cloud of cardinality n.
Definitions: The Hausdorff distance is defined using the baseline distance between points, such as Euclidean distance.This distance measures how far the point cloud and its subsample can be from one another under the chosen metric.
Proof: The proof applies persistent-homology stability to the original point cloud and its subsample viewed as finite metric spaces.The stability result is expressed through the Gromov–Hausdorff distance between the two spaces.
Proof: Because the subsample inherits the original metric, its Gromov–Hausdorff distance is bounded by the Hausdorff distance.Substituting this relation into the stability inequality yields the theorem’s claim after taking probabilities.

A.3. Empirical Convergence Rates of dH

The empirical convergence rate of the Hausdorff distance is roughly similar across ambient dimensions, but its absolute level depends on dimension.

Empirical convergence: The empirical convergence rate of the mean Hausdorff distance is evaluated for subsamples of m points drawn from 100 standard-normal points in d dimensions.Figure A.1 reports the mean convergence behavior as the subsample size varies.
Empirical convergence: The convergence rate is roughly similar across dimensions, while the absolute Hausdorff-distance levels depend on ambient dimension.Thus, dimension changes the scale of the observed distance more than the qualitative convergence pattern.
Bounds: A bound on the convergence rate is feasible but requires more involved assumptions about the measures generating the point cloud and subsample.A simpler worst-case bound uses the diameter of the original point cloud.
Bounds: The diameter bound does not account for the sample size m, whereas Theorem 2 provides an expression that incorporates m.The worst-case bound is therefore insensitive to mini-batch size.

A.4. Proof of Theorem 2

Theorem 2 analyzes the Hausdorff distance between a finite point cloud and a mini-batch by reducing it to maxima of nearest-sample distances and approximating their distribution.

Distance reduction: For a subsample X(m) contained in X, the Hausdorff distance reduces to a one-sided distance because the subsample-to-original distance is zero.Finite point clouds allow the remaining supremum and infimum operations to be treated as maxima and minima.
Distance reduction: The Hausdorff-distance computation forms a distance matrix, takes each row’s minimum distance to the mini-batch, and aggregates these minima.The resulting vector contains the nearest-mini-batch distance for every point in the original cloud.
Distance reduction: The proof isolates the n−m row minima because the first m rows corresponding to sampled points have minimum distance zero.For unsampled points, each minimum is δi = min 1≤j≤m aij.
Distributional analysis: The analysis considers the maximum Z of the row minima and derives its distribution before evaluating its expectation.This converts the Hausdorff-distance problem into an extreme-value calculation.
Assumptions: The approximation imposes i.i.d. sampling of the minimal distances, although metric triangle inequalities make the actual row minima dependent.The proof explicitly requires an independence assumption for this approximation.
Assumptions: The independence approximation overestimates the variance and therefore yields an upper bound on the expected maximum of the minima.Consequently, the resulting expression upper-bounds the actual expected Hausdorff distance.

A.5. Synthetic Data Set

The synthetic-data experiments evaluate topology-preserving autoencoders on SPHERES and compare latent-space quality using reconstruction, nonlinear dimensionality-reduction, density, and topological-distance measures. Preliminary experiments also examine batch-size effects and extend the constraint to variational autoencoders.

Synthetic data set: SPHERES contains eleven high-dimensional 100-spheres in 101-dimensional space, including ten shifted spheres enclosed by a larger sphere.The ten inner spheres have radius r = 5, while the enclosing sphere has radius 5r.
Architectures: The synthetic autoencoder uses a 32−32−2−32−32 multilayer perceptron with a two-neuron bottleneck, ReLU activations, batch normalization, and mean squared error training.
Evaluation: Latent representations are assessed with reconstruction error, distance-matrix and rank-preservation metrics, trustworthiness, continuity, and KL divergence between input and latent density distributions.The trustworthiness and continuity measures compare neighborhood preservation in opposite directions, while KLσ compares density estimates at a length scale σ.
Hyperparameter analysis: Increasing batch size tends to decrease reconstruction loss but increase topological loss, possibly because larger batches permit more complex point arrangements and topologies.
Variational autoencoders: Applying the topological constraint to SPHERES variational autoencoders helps identify the nesting structure of the enclosing sphere.The comparison is between a standard MLP-based VAE and the same architecture augmented with the topological constraint.
Topological fidelity: Topological distances between full-dimensional test data and two-dimensional latent spaces are estimated using W1, W2, and W∞ persistence-diagram distances, with a simple sanity check showing reduced distance.A more involved approach would be required for a proper comparison of topological features between the spaces.