Principle Component Trees and Their Persistent Homology

Ben A. Kizaric, Daniel L. Pimentel-Alarcón

Abstract

Principal Component Trees (PCTs) are a novel graph-based generalization of Principal Component Analysis (PCA) designed to represent complex, intersecting, and hierarchical subspace structures in high-dimensional data. By combining recursive hypothesis testing with persistent homology, PCTs provide a powerful topological signature to compare the structural complexity of datasets, such as neural network latent spaces and word embeddings.

Introduction

Most dimensionality reduction techniques assume data lies either in a single flat subspace (PCA) or in a union of multiple disjoint subspaces (Subspace Clustering). However, real-world data frequently contains features shared across groups alongside unique cluster-specific features. Standard methods struggle to represent these "intersecting unions of subspaces" efficiently.

Principal Component Trees (PCTs) address this gap by proposing a hierarchical structure where each node represents a principal component and branches represent the different ways those components can be mixed to approximate the data. This allows for a more nuanced representation of data that doesn't fit neatly into disjoint clusters.

Conceptual overview of PCTs representing intersecting subspaces (left) and a hierarchical decomposition of image data (right).

Methodology

The core of the PCT framework is the recursive construction of a tree that splits principal components rather than just data points. The algorithm starts at a root node and greedily expands by analyzing residuals—the variance not yet explained by PCA at that level.

To decide whether to split a node into children (indicating a cluster) or maintain it as a single unit, the authors employ a non-parametric Cramér-von Mises hypothesis test. This test evaluates the distribution of pairwise angles between data points; "crowded" angles suggest the presence of subspace clustering. A significant innovation is the intersection test, which prevents premature splitting if two subspaces share a common axis, allowing the PCT to explicitly model intersections.

Indexing and projection logic within a Principal Component Tree.

Furthermore, the authors utilize tools from topology—specifically persistent homology—to define "Height" and "Width" curves. These monotonic signatures describe how the tree's shape evolves as less significant nodes are pruned. The Area Under the Curve (AUC) for these signatures serves as a single-number summary of a dataset's structural complexity or "clusteredness."

Key Insights and Results

The authors demonstrate that if data follows a multivariate normal distribution (no clusters), the PCT naturally reduces to standard PCA, resulting in a tall, thin "degenerate" tree. In contrast, complex datasets like Fashion MNIST exhibit significantly more subspace clustering than standard MNIST. While both have similar dimensions, the MNIST tree is dominated by a single branch, whereas the Fashion MNIST tree splits into two, reflecting its more intricate category structure.

In the realm of neural networks, PCT analysis confirms that classification models create much more clustered latent spaces than generative models like Autoencoders or VAEs. This supports the intuition that classifiers work by forcing data into distinct, separable subspaces. Additionally, the Width Curve ($W_T$) proved to be a highly sensitive measure, clearly distinguishing the isotropic pressure of a VAE (which had the lowest AUC) from the structure of a standard Autoencoder.

In NLP applications, the study found that Russian word embeddings are significantly more clustered than Italian or English ones, suggesting that different languages may have distinct geometric structures for representing common vocabulary.

Conclusion

Principal Component Trees offer a parameter-efficient and topologically grounded approach to modeling high-dimensional data. By capturing intersecting and hierarchical subspace structures, they provide deeper insights into the geometry of latent spaces and linguistic embeddings. Future work may explore non-binary splits and the integration of PCT structures directly into hierarchical neural network architectures to further leverage these geometric insights.

Summary updated

Abstract

Low dimensional models like PCA are often used to simplify complex datasets by learning a single approximating subspace. This paradigm has expanded to union of subspaces models, like those learned by subspace clustering. In this paper, we present Principle Component Trees (PCTs), a graph structure that generalizes these ideas to identify mixtures of components that together describe the subspace structure of high-dimensional datasets. Each node in a PCT corresponds to a principal component of the data, and the edges between nodes indicate the components that must be mixed to produce a subspace that approximates a portion of the data. In order to construct PCTs, we propose two angle-distribution hypothesis tests to detect subspace clusters in the data. To analyze, compare, and select the best PCT model, we define two persistent homology measures that describe their shape. We show our construction yields two key properties of PCTs, namely ancestral orthogonality and non-decreasing singular values. Our main theoretical results show that learning PCTs reduces to PCA under multivariate normality, and that PCTs are efficient parameterizations of intersecting union of subspaces. Finally, we use PCTs to analyze neural network latent space, word embeddings, and reference image datasets.
BibTeX
@inproceedings{kizaric2024principle,
  author = {Ben A. Kizaric and Daniel L. Pimentel-Alarcón},
  title = {{Principle Component Trees and Their Persistent Homology}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i12.29222},
}
Figure