PaperlayerView exact revision on arXiv

Source-linked AI summary

Persistence weighted Gaussian kernel for topological data analysis

Genki Kusano, Kenji Fukumizu, Yasuaki Hiraoka

arXiv:1601.01741v2math.AT

TL;DR

Statistical analysis of collections of persistence diagrams is difficult because diagrams are variable-size point sets. The paper proposes the persistence weighted Gaussian kernel, which controls persistence contributions, satisfies stability, and supports efficient approximation; experiments cover synthesized, protein, and oxide-glass data, while approximation accuracy depends on the Gaussian bandwidth.

  • Problem

    Statistical methods for many persistence diagrams remain limited, although persistence diagrams capture robust and noisy topological properties.

  • Method

    The paper embeds persistence diagrams with a persistence weighted Gaussian kernel that explicitly controls the effect of persistence and supports random Fourier feature approximation.

  • Results

    The method is demonstrated on synthesized data and real protein and oxide-glass datasets, with analyses including change-point detection, principal component analysis, and support vector machines.

  • Takeaways & Limitations

    PWGK provides a statistical framework for persistence diagrams with persistence control, stability, and efficient Gram-matrix approximation for practical TDA applications.

  • Takeaways & Limitations

    Random Fourier feature approximation can be sensitive to the Gaussian bandwidth σ, with large relative errors when σ is much smaller than distances between diagrams.

Abstract

from arXiv · show

Topological data analysis (TDA) is an emerging mathematical concept for characterizing shapes in complex data. In TDA, persistence diagrams are widely recognized as a useful descriptor of data, and can distinguish robust and noisy topological properties. This paper proposes a kernel method on persistence diagrams to develop a statistical framework in TDA. The proposed kernel satisfies the stability property and provides explicit control on the effect of persistence. Furthermore, the method allows a fast approximation technique. The method is applied into practical data on proteins and oxide glasses, and the results show the advantage of our method compared to other relevant methods on persistence diagrams.

1 Introduction

TDA uses persistent homology and persistence diagrams to represent robust and noisy topological properties, but statistical methods for collections of diagrams remain limited. This paper introduces a persistence weighted Gaussian kernel framework with persistence control, stability, efficient approximation, and applications to protein and oxide-glass data.

  • TDA extracts topological properties such as connected components, rings, and cavities as data descriptors.
  • Persistent homology considers all radius values simultaneously, expressing topological properties together with their persistence.
  • Persistence diagrams encode robustness through persistence, with large-persistence generators treated as reliable structures and near-diagonal generators likely representing noise.
  • Statistical analysis of many persistence diagrams is still limited because diagrams are variable-size point sets rather than standard vectorial data.
  • The persistence weighted Gaussian kernel vectorizes diagrams while controlling persistence effects, satisfying stability and supporting random Fourier feature approximations.
  • The method is demonstrated on synthesized data and real protein and oxide-glass datasets.

2 Background

Persistent diagrams summarize how topological features appear and disappear across a radius filtration, while stability relates diagram differences to perturbations in the underlying data. Kernel mean embeddings provide a vector representation in an RKHS, with Gaussian kernels offering injective representations of finite signed measures.

  • 2.1 Persistence diagram: The fattened ball model represents data by unions of radius-r balls, whose homology dimensions count components, rings, cavities, and higher-dimensional features.
  • 2.1 Persistence diagram: A filtration tracks generators through increasing radii, recording each feature's birth-death pair in a persistence diagram.
  • 2.1 Persistence diagram: Persistence measures a generator's lifetime, so long-lived features are more robust while short-lived, near-diagonal features are more likely noise.
  • 2.1 Persistence diagram: For finite fattened ball models, the infinite-lifetime D0 generator is removed and the remaining persistence diagram has finite cardinality.
  • 2.2 Stability with respect to dB: Persistence diagrams are desired to remain stable under noisy or stochastic perturbations of statistical data.
  • 2.2 Stability with respect to dB: The bottleneck-distance stability proposition bounds diagram distance by the Hausdorff distance between finite data sets.
  • 2.3 Kernel methods for representing signed measures: Kernel mean embedding maps finite signed measures into an RKHS through a Bochner integral of kernel feature vectors.
  • 2.3 Kernel methods for representing signed measures: A C0-universal kernel yields an injective embedding, and the Gaussian kernel is C0-universal on Euclidean space.

3 Kernel methods for persistence diagrams

The paper vectorizes persistence diagrams in an RKHS using the persistence weighted Gaussian kernel, which downweights low-persistence generators while retaining stability. It also provides a random-Fourier-feature approximation that reduces Gram-matrix computation when diagrams contain many generators.

  • Kernel embedding and analysis: The PWGK embeds persistence diagrams into an RKHS, enabling standard kernel methods such as SVM, kernel PCA, and kernel change point detection.The paper studies both linear and nonlinear kernels on the resulting RKHS representations.
  • Kernel embedding and analysis: The construction treats each persistence diagram as a discrete measure and weights its generators to discount points near the diagonal.The weighted measure uses a weight function w(x) for each generator, with the weighting intended to reduce the influence of likely noise.
  • Persistence weighting: The Gaussian-kernel implementation uses w_arc(x) = arctan(C pers(x)^p), allowing C and p to control persistence effects independently of the bandwidth σ.The weight is increasing with persistence, so noisy and essential generators receive smaller and larger weights, respectively.
  • Stability: The PWGK representation is Lipschitz continuous under the stated compactness and parameter condition p > d + 1.The stability constant depends on M, d, C, p, and σ, but not on the particular finite point sets X and Y.
  • Computation: The exact Gram matrix has complexity O(m^2n^2), while random Fourier features reduce the approximated complexity to O(mnM + n^2M).This approximation is motivated by applications with many generators per diagram and relatively small numbers of diagrams.
  • Computation: Random Fourier-feature approximation can be sensitive to σ; with σ = 0.01, an exact value near 10^-22 was approximated near 10^-3 using M = 10^3.The paper warns that accumulated errors may become critical and that poor bandwidth choices can push Gaussian terms close to 0 or 1.

4 Experiments

The experiments compare PWGK with PSSK and other persistence-diagram representations across classification and SiO2 glass-transition change-point detection. PWGK supports persistence control and efficient approximation while producing meaningful classification, change-point, and phase-separation results.

  • Comparison to PSSK: PWGK independently controls persistence weighting through C and p, unlike PSSK’s single parameter t, and supports random Fourier feature approximation.PSSK approximation instead requires Nyström or incomplete Cholesky methods, while random Fourier features reuse the same expansion across persistence-diagram pairs.
  • Classification with synthesized data: In synthesized SVM experiments, PWGK, PSSK, and Gaussian embeddings were evaluated using average classification rates over 99 test data sets.The experiment uses 100 training data sets, 99 independent test data sets, and 10-fold cross-validation for hyperparameter selection.
  • Analysis of SiO2: The SiO2 experiment treats glass-transition detection as a change-point problem and uses KFDR computed from persistence-diagram kernel Gram matrices.The estimated change point is the index maximizing KFDR, with γ = 10^-3.
  • Analysis of SiO2: The PWGK change-point estimate converges to ℓ=37, whereas PSSK computations with c > 500 are infeasible in reasonable time because Nyström inversion has O(c^3) complexity.PWGK random Fourier feature complexity is O(M), and the paper reports that obtaining ℓ=37 is much faster with PWGK than with PSSK.
  • Analysis of SiO2: The PWGK KPCA plot shows a clear phase change between observations before and after the detected change point, strongly suggesting that it identifies the glass transition.The figure uses PWGK with M = 1000 for the KPCA visualization.
  • Protein classification: Across two protein classification problems, PWGK achieves better performance than the molecular topological fingerprint method under the reported SVM setting.The comparison uses the same SVM setting as the cited molecular-topological-fingerprint study.

5 Conclusion

The paper proposes a kernel framework for persistence diagrams centered on the persistence weighted Gaussian kernel (PWGK), combining persistence control, stability, practical computation, and applications.

  • PWGK controls the effect of persistence in data analysis.
  • The paper proves a stability result with respect to the kernel distance.
  • PWGK produces meaningful results for change point detection, principal component analysis, and support vector machines on physics and biochemistry data.
  • An accurate and efficient Gram-matrix approximation makes the kernel suitable for practical TDA applications.

Supplementary Material

The supplementary material introduces the topological tools used in the paper, supplies proofs of key results, and explains the synthesized data used in Section 4.2.

  • The supplement introduces the topological tools used throughout the paper.
  • It provides proofs of Theorem 3.1 and Proposition 3.1.
  • It explains the synthesized data used in Section 4.2.
  • The proof of Theorem 3.1 introduces sub-level sets and total persistence, followed by a generalization in Section D.

A Topological tools

This section builds the algebraic foundations of TDA, moving from simplicial complexes and chain complexes to homology and induced maps for inclusions.

  • A Topological tools: TDA uses algebraic topology to study geometric properties that are difficult to represent with ordinary feature vectors.
  • A Topological tools: A simplicial complex is a collection of subsets of a finite vertex set, with lower-dimensional faces represented as simplices and subcomplexes formed by suitable subcollections.
  • A Topological tools: The examples distinguish a filled triangle S from its boundary T, whose geometric realizations are illustrated as polyhedra.
  • A Topological tools: Homology is constructed from a chain complex using boundary maps, then quotienting cycles by boundaries; its generators represent holes.
  • A Topological tools: Inclusion of a subcomplex induces a homology map, allowing a ring present in T but absent in S to be described as disappearing under inclusion.
  • A Topological tools: The same homology framework extends to general topological spaces through singular simplices and agrees with simplicial homology for triangulable spaces.

A.3 Persistent homology

Persistent homology tracks homology across a filtration, decomposes its changes into birth-death generators, and represents those generators in persistence diagrams.

  • A.3 Persistent homology: A filtration is a right-continuous family of spaces Xa nested as Xa ⊂ Xb whenever a ≤ b, with inclusion-induced maps between homology groups.
  • A.3 Persistent homology: Persistent homology is defined from the family of homology groups and their induced maps across filtration parameters.
  • A.3 Persistent homology: For tame persistent homology, a unique decomposition expresses persistence through interval generators with birth-death pairs.
  • A.3 Persistent homology: A persistence diagram augments the birth-death multiset with the diagonal having infinite multiplicity.
  • A.3 Persistent homology: Generators near the diagonal represent short-lived, likely noisy features, whereas distant generators represent robust features.
  • A.3 Persistent homology: The paper uses filtrations generated by unions of metric balls around a finite point set and illustrates one filtration and its persistence diagram.

B Sub-level sets

The section introduces sub-level-set filtrations for constructing persistent homology and develops total-persistence bounds needed for stability analysis.

  • Sub-level-set filtration: A function f on M defines the filtration F = {F_a | a ∈ R} through sub-level sets F_a = {x ∈ M | f(x) ≤ a}.Persistent homology is then constructed from this filtration.
  • Stability setup: For sub-level sets, persistence-diagram differences are controlled by the sup-norm difference between the underlying functions.For finite point sets, this function-distance becomes the Hausdorff distance between the sets.
  • Total-persistence bounds: For p > d, the p-degree total persistence of a tame Lipschitz function is bounded using the space dimension, Lipschitz constant, amplitude, and triangulation complexity.The covering quantity N(r) is bounded by C_M/r^d for compact subspaces of R^d.
  • Finite-set specialization: For finite point sets, the associated distance function has Lipschitz constant 1 and amplitude at most diam(M), yielding a total-persistence bound depending on M, d, p, and diam(M).The bound is obtained by embedding the finite set in a triangulable compact region.
  • Diagram-level persistence: For a persistence diagram D, p-degree total persistence is the ℓp-norm of the vector of point persistences, and bounded Pers_p implies bounded Pers_q for p ≤ q.This transfers total-persistence control across degrees.

D Proof of Theorem 3.1 and its generalization

The section proves a generalized stability result for the proposed diagram kernel and shows that, for diagrams from finite sets, its stability constant can be made independent of the particular diagrams.

  • Generalized stability: Theorem D.1 establishes a generalized stability bound for finite persistence diagrams.The proof uses a multi-bijection pairing diagram points while accounting for unmatched points near the diagonal.
  • Constant control: Although the initial constant L(D, E; C, p, σ) depends on both diagrams, that dependence disappears for persistence diagrams obtained from finite sets.The resulting constant depends on M, d, C, p, and σ, but not on X or Y.
  • Proof ingredients: The proof controls kernel differences through persistence-weight bounds, persistence differences, and the inequality 1 − e^-t ≤ t.The persistence map is Lipschitz in the diagram-point distance, with |pers(x) − pers(y)| ≤ 2||x − y||∞.
  • Role of total persistence: Bounded (p − 1)-degree total persistence for D and E makes the coefficient of the stability parameter bounded.Bounded p-degree total persistence follows from the monotonicity result for total persistence.

E Proof of Proposition 3.1

The section verifies the weighted-kernel construction by identifying its weighted function space with an RKHS and invoking uniqueness of reproducing kernels.

  • Weighted space: The weighted function space is a Hilbert space, and multiplication by the positive weight w gives an isomorphism with the original Hilbert space.This establishes the structural basis for the weighted kernel construction.
  • Reproducing kernel: The kernel k_w(·, x) = w(·)w(x)k(·, x) reproduces evaluation in the weighted space, so it is the reproducing kernel of that space.Uniqueness of reproducing kernels completes the identification.
  • Remaining assertion: The second assertion follows directly from Equations (2) and (3) in Section 3.1.The proof treats this assertion as immediate from the earlier kernel definitions.

F Synthesized data

The synthesized-data experiment generates noisy point clouds on one or two circles and assigns binary labels from latent circle structure, allowing topology-based classification under mismatch between true and observed quantities.

  • Data generation: Each synthesized dataset contains a variable number of two-dimensional points arranged on a large circle S1 and, with probability 0.5, a smaller circle S2.The large circle has random center and radius r1 from 1 to 10; the smaller circle has radius 0.2 and contains 10 points when present.
  • Persistence structure: The persistence of the S1 generator is determined essentially by N1 and r1, with birth approximately πr1/N1 and death equal to r1 when no ball intersection occurs.This connects the geometric circle parameters to its persistence-diagram coordinates.
  • Classification labels: The binary label depends on whether S2 exists and whether the hypothetical true S1 generator has long persistence.The conditions use thresholds A_B = 1 and A_D = 4 through z0 and z1, with Y = XOR(z0, z1).
  • Generative model: The section specifies generative distributions for the noisy radius, point count, center, true radius, and true point count.The true point count is sampled as a random integer over a range determined by N* = πr1^o/AB.
  • Noise and classification limit: The observed point cloud and persistence diagram use noisy r1 and N1, whereas the label uses latent true quantities r1^o and N1^o.This randomness means the best classification boundary cannot achieve a 100% classification rate.
Loading 1601.01741v2…