Clustering Tree-Structured Data on Manifold

Na Lu, Hongyu Miao

TL;DR

This paper introduces TAMBAC, a novel framework for clustering complex tree-structured data (like blood vessels or phylogenetic trees) by representing them as matrices on a manifold. By developing a "Topology-Attribute matrix" and a structure-constrained matrix factorization method, they enable robust clustering of these inherently non-Euclidean data types.

What Problem Does This Paper Address?

Analyzing tree-structured data is challenging because it involves both the branching structure (topology) and the characteristics of the branches themselves (geometry, e.g., length, radius). These data don't fit neatly into standard Euclidean spaces, requiring specialized methods. Existing approaches often struggle to simultaneously capture both topological and geometric information, are computationally expensive, or are limited to specific types of trees (like phylogenetic trees). The authors aim to provide a unified, efficient, and accurate method for clustering these complex, manifold-like data.

Methods

The core of the proposed method, TAMBAC (Topology-Attribute Matrix BAsed Clustering), involves several key steps:

  1. Topology-Attribute Matrix (T-A Matrix) Parameterization: Trees are converted into matrices. A "support tree" is established, and each branch of an individual tree is mapped to a corresponding branch in the support tree. The T-A matrix then encodes this mapping, with rows representing branches and columns representing attributes (like length, radius, tortuosity). If a branch is missing, the corresponding entry is zero.
  2. Structure-Constrained Non-Negative Matrix Factorization (SCNMF): Standard Non-Negative Matrix Factorization (NMF) is adapted to handle the inherent "structure constraints" of tree data (e.g., a branch with a radius must also have a length). This factorization decomposes the T-A matrices into "meta-trees" (basis trees) and "signature vectors" (coefficients representing how each original tree is composed of these meta-trees). This decomposition effectively maps trees into a new "meta-tree space."
  3. Meta-Tree Space and Distance Metric: The meta-tree space is characterized as a "cone space." The authors propose a computationally efficient distance metric (an approximation of the geodesic distance) within this space, based on the concept of a strict consensus tree. This metric is crucial for clustering.
  4. Clustering: Standard clustering algorithms, specifically NCut and K-means (adapted for the meta-tree space using Fréchet mean), are applied to the signature vectors obtained from SCNMF.

Datasets

The paper evaluates TAMBAC using:

  • Simulated T-A Matrices: Generated to control for variations in tree topology (order, depth, branching patterns) and geometric attributes (length, radius, tortuosity).
  • Simulated 3D Vascular Trees: Generated using the VascuSynth tool, mimicking real-world vascular structures with varying topology and geometry based on user-specified parameters.
  • Real Retinal Vascular Images: Data from the publicly available STARE database, containing images of both normal subjects and those with retinopathy, allowing for evaluation on real-world, complex biological structures.

Key Insights and Ideas

  • Manifold Representation is Key: Tree-structured data inherently live on non-Euclidean manifolds, making standard Euclidean methods insufficient. Representing them as matrices on a manifold is a powerful way to enable analysis.
  • T-A Matrix Captures Both Topology and Geometry: The proposed T-A matrix is a flexible and intuitive way to encode both the branching structure and the attributes of tree branches simultaneously.
  • Structure Constraints are Crucial for NMF: Traditional NMF is too simplistic for tree data. Incorporating specific "structure constraints" into the factorization (SCNMF) is essential for extracting meaningful "parts" (meta-trees).
  • Meta-Tree Space as a New Domain: Decomposing trees into meta-trees creates a new feature space (the meta-tree space) where clustering can be performed more effectively.
  • Efficient Geodesic Approximation: Developing a computationally feasible distance metric in the meta-tree space is vital for practical clustering, and their proposed L1-norm based metric offers a good balance of accuracy and efficiency.

Key Results

  • High Clustering Accuracy: TAMBAC consistently achieves high clustering accuracies across simulated and real datasets. For simulated 2-ary trees, accuracies often exceed 90%. For simulated 3D vascular trees, average accuracies are around 77% (NCut) and 74% (K-means). For real retinal data, accuracies are around 73% with two geometric attributes and 71% with three.
  • NCut Outperforms K-means: In most cases, the NCut clustering algorithm within the TAMBAC framework yields better accuracy than K-means.
  • Robustness to Noise: The method shows good robustness to attribute noise (perturbations in branch values) and topology noise (changes in branching structure), with accuracy decreasing only marginally as noise levels increase.
  • Comparison with Other Metrics: TAMBAC with its proposed distance metric generally outperforms other state-of-the-art metrics like QED and Torsello's metric on both simulated and real vascular trees.

Limitations and Future Work

  • Support Tree Regeneration: The support tree, used for T-A matrix construction, is determined by the initial population of trees. If new data with significantly different topologies are introduced, the support tree may need to be regenerated, requiring recomputation.
  • SCNMF Non-Uniqueness: Like other matrix decomposition methods, SCNMF may not always produce the exact same basis vectors (meta-trees) across different runs. However, the paper demonstrates that the clustering performance remains consistent and stable.
  • Future Work: The authors suggest that the issues of support tree regeneration can be addressed by using a sufficiently large support tree or by incorporating incremental learning techniques. They also plan to continue improving and extending the TAMBAC framework.

Summary updated

Abstract

Tree-structured data usually contain both topological and geometrical information, and are necessarily considered on manifold instead of euclidean space for appropriate data parameterization and analysis. In this study, we propose a novel tree-structured data parameterization, called Topology-Attribute matrix (T-A matrix), so the data clustering task can be conducted on matrix manifold. We incorporate the structure constraints embedded in data into the non-negative matrix factorization method to determine meta-trees from the T-A matrix, and the signature vector of each single tree can then be extracted by meta-tree decomposition. The meta-tree space turns out to be a cone space, in which we explore the distance metric and implement the clustering algorithm based on the concepts like Fréchet mean. Finally, the T-A matrix based clustering (TAMBAC) framework is evaluated and compared using both simulated data and real retinal images to illustrate its efficiency and accuracy.
BibTeX
@article{lu2016clustering,
  author = {Na Lu and Hongyu Miao},
  title = {{Clustering Tree-Structured Data on Manifold}},
  journal = {IEEE Trans. Pattern Anal. Mach. Intell.},
  year = {2016},
  url = {https://openreview.net/forum?id=CJj3f81s2Y7},
}
Figure