Technical Summary: Voronoi Histograms for Adaptive Vectorization of Expected Persistence Diagrams

1. Problem Statement

Topological Data Analysis (TDA) utilizes Persistent Homology (PH) to capture the topological features of point clouds, encoded as Persistence Diagrams (PDs). A PD represents topological features (cycles) as points $(b, d)$ in an open half-plane $\Omega$, where $b$ and $d$ denote birth and death times. However, PDs cannot be directly used as inputs for standard machine learning algorithms, necessitating vectorization.

A significant bottleneck in using PDs is their high computational complexity; obtaining a PD can reach $O(m^3)$ or even $O(|X|^9)$ for 1-dimensional features. To mitigate this, the Expected Persistence Diagram (EPD) was developed. An EPD is a distribution of topological features derived by averaging the PDs of multiple subsampled subsets of a point cloud. While EPDs reduce time costs, existing vectorization methods for EPDs (such as Persistence Images, Persistence Silhouettes, and Persistence Landscapes) rely on predefined continuous point transformation functions (e.g., Gaussian kernels or landscape functions) and fixed discretization grids. These methods introduce design choices regarding smoothness, bandwidth, and grid resolution, which can blur local mass differences or emphasize non-optimal regions of the $(birth, death)$ plane.

The paper addresses the need for an alternative vectorization method that avoids explicit smooth point transformation models and instead utilizes adaptive, data-dependent partitioning to represent the EPD distribution.

2. Methodology: Voronoi-based Representation (Vrep)

The authors propose Vrep, a vectorization method that treats the empirical EPD as a distribution of topological features and represents it using histograms based on Voronoi Diagrams.

Core Mechanism

1. Codebook Sampling: Instead of a fixed grid, Vrep constructs a set of random codebooks $S$. Each codebook $C = \{c_1, ..., c_k\}$ consists of points sampled from the support of the EPD (the set of topological features).
2. Voronoi Partitioning: For a given codebook $C$, the open half-plane $\Omega$ is partitioned into Voronoi cells $V(c_i)$, where each cell contains points closer to $c_i$ than to any other $c_j$.
3. Histogram Construction: The representation $\Phi(\bar{\mu}, C)$ is defined as the vector of normalized masses of the EPD $\bar{\mu}$ falling into each Voronoi cell:
   $$\Phi(\bar{\mu}, C) = [\bar{\mu}(V(c_1)), \bar{\mu}(V(c_2)), ..., \bar{\mu}(V(c_k))]$$
4. Aggregation: To form the final representation $\hat{\Phi}(\bar{\mu})$, the method concatenates histograms generated from multiple codebooks sampled from the dataset.
5. Diagonal-Aware Variant (Vrepd): A specific variant, Vrepd, includes a Voronoi cell centered at the diagonal $\partial\Omega$ (where $b=d$). This is crucial for separating noise (features near the diagonal) from significant topological features.

Codebook Sampling Strategies

The paper evaluates three strategies for sampling the points within a codebook:

• Default: Uniform sampling from the EPD support.
• Persistence-Weighted: Sampling weighted by persistence ($d-b$), prioritizing significant features.
• Uniform: Sampling from a fixed rectangle above the diagonal (EPD-irrelevant).

Normalization

The method normalizes the EPD to a unit $l_1$-norm ($\bar{\mu} \leftarrow \bar{\mu}/\bar{\mu}(\Omega)$). This treats the EPD as a probability distribution, ensuring all EPDs have the same mass, which allows the direct use of the Wasserstein distance for stability analysis and dissimilarity measurement, avoiding the need for Optimal Partial Transport metrics.

3. Theoretical Contributions

The paper establishes theoretical guarantees regarding the stability and representational capacity of Vrep under specific conditions:

• Stability Bounds: The authors prove that Vrep is stable under perturbations of the EPD. Specifically, if the EPD undergoes a $\Delta$-perturbation (small movement of Dirac masses), the change in the Vrep representation is Lipschitz continuous with respect to $\Delta$. The error bound depends on the codebook size $k$ and the dataset properties.
• Wasserstein-Related Bounds: The paper provides a conditional lower bound relating the $l_1$ distance between two Vrep vectors to the Wasserstein distance ($W_1$) between the underlying EPDs.
  $$\|\Phi(\bar{\mu}, C) - \Phi(\bar{\nu}, C)\|_1 \geq \frac{W_1(\bar{\mu}, \bar{\nu}) - \text{approximation errors}}{d_{max}(C)}$$
  This result clarifies that Vrep preserves Wasserstein-scale variations effectively when the codebook is "well-resolved" (i.e., the approximation error is small relative to the separation of the distributions). It is not a general monotonic preservation guarantee but a conditional consistency statement.

4. Experimental Results

The authors evaluated Vrep and Vrepd on supervised point cloud classification and unsupervised dimensionality reduction tasks, comparing them against standard methods: Persistence Image (PI), Persistence Silhouettes (PS), Persistence Landscape (PL), and the end-to-end network PointNet.

Classification Performance

• Datasets: Experiments were conducted on diverse datasets including Protein structures, CAD mechanical components, and time-series data (transformed into point clouds via time-delay embedding).
• Results: Vrep and Vrepd consistently achieved higher or comparable classification accuracy (using a Random Forest classifier) compared to PI, PS, and PL across most topology-sensitive datasets.
  • On the Protein dataset, Vrep achieved 98.5% accuracy (vs. 95.5% for PI).
  • On CAD datasets, Vrep and Vrepd outperformed other unsupervised methods, though PI showed competitive results in some noise settings.
• Codebook Sensitivity: The persistence-weighted codebook sampling strategy often yielded the best results, particularly in noisy environments, as it focuses the representation on significant topological features.

Stability and Scalability

• Perturbation Stability: Experiments on a 3D dynamical system dataset showed that Vrep is stable under Gaussian noise perturbations. Interestingly, Vrepd (with the diagonal cell) demonstrated slightly higher stability than Vrep, likely due to better separation of noise near the diagonal.
• Time Complexity:
  • Vrep has a time complexity of $O(m^2tk)$ for a dataset of size $m$, where $t$ is the number of codebooks and $k$ is the codebook size. This is quadratic in dataset size.
  • However, Vrep is faster than PL and PS in actual runtime and scales better with the number of sampled PDs ($n$) because it subsamples the EPD support to a fixed size, whereas PI/PS/PL must process every sampled PD individually.
  • While PointNet (supervised) achieved high accuracy, Vrep offers a competitive alternative for unsupervised tasks (like dimensionality reduction) where PointNet cannot be applied.

Unsupervised Dimensionality Reduction

In a t-SNE visualization task on a dynamical system dataset, Vrep produced clusters with higher Calinski-Harabasz (CH) indices (1751) compared to PI (569) and PL (1655), indicating superior cluster separation.

5. Significance and Claims

The paper positions Vrep as a complementary representation rather than a universal replacement for existing methods.

• Adaptive vs. Smooth: The primary contribution is the shift from smooth, kernel-based functional approximations to adaptive, data-dependent counting. Vrep aggregates mass over cells defined by the data itself, making it potentially more faithful to the empirical mass allocation of the EPD.
• Trade-off: The authors explicitly acknowledge the trade-off: Vrep efficiently summarizes coarse mass allocation but is inherently lossy regarding fine-grained geometry within a Voronoi cell. Consequently, smooth methods (like PI or kernel methods) may outperform Vrep when the relevant topological variation involves fine local shifts or shape changes within a cell.
• Unsupervised Utility: A key significance is the method's applicability to unsupervised learning. Unlike supervised deep learning approaches (e.g., PointNet, PersLay), Vrep does not require labels for feature extraction, making it suitable for dimensionality reduction and clustering tasks.
• Modest Claims: The authors do not claim Vrep dominates all existing vectorizations. They note that kernel methods (PWGK, SWK) can outperform Vrep on specific datasets (e.g., CAD) but at a significantly higher computational cost. The paper concludes that Vrep is a competitive, adaptive alternative that offers favorable scaling with the number of sampled PDs and provides a distinct approximation bias suitable for topology-sensitive classification.