Study of Manifold Geometry using Multiscale Non-Negative Kernel Graphs

Carlos Hurtado, Sarath Shekkizhar, Javier Ruiz Hidalgo, Antonio Ortega

Abstract

Modern machine learning systems are increasingly trained on large amounts of data embedded in high-dimensional spaces. Often this is done without analyzing the structure of the dataset. In this work, we propose a framework to study the geometric structure of the data. We make use of our recently introduced non-negative kernel (NNK) regression graphs to estimate the point density, intrinsic dimension, and the linearity of the data manifold (curvature). We further generalize the graph construction and geometric estimation to multiple scale by iteratively merging neighborhoods in the input data. Our experiments demonstrate the effectiveness of our proposed approach over other baselines in estimating the local geometry of the data manifolds on synthetic and real datasets.

Introduction

High-dimensional data in modern machine learning typically resides on a lower-dimensional "manifold." Understanding this manifold is crucial, yet standard tools like K-Nearest Neighbor (KNN) graphs are often "geometry-blind." KNN selects neighbors based strictly on distance, regardless of whether they provide redundant or unique geometric information. This lack of geometric awareness makes estimating properties like Intrinsic Dimension (ID) and curvature highly sensitive to the parameter $K$, often leading to inaccurate results as the neighborhood size varies.

KNN low-rank approximation on a non-linear manifold showing the difficulty of estimating intrinsic dimension with standard methods.

Methodology

The researchers propose using Non-Negative Kernel (NNK) regression graphs to overcome these limitations. Unlike KNN, NNK employs an optimization step to select a sparse set of "necessary" neighbors. If a neighbor's contribution can be explained by other closer neighbors, it is pruned. This results in a local NNK Polytope that is explicitly tied to the local geometry of the data.

Geometric Metrics

  • Density: Measured by the diameter of the NNK polytope.
  • Intrinsic Dimension (ID): Estimated by performing PCA on the NNK neighborhood and identifying significant eigenvalues.
  • Curvature: Analyzed by measuring the "principal angles" between the tangent planes of adjacent neighborhoods. On flat manifolds, these planes align (small angles), whereas they diverge on curved manifolds.

Multiscale Merging

To study data at different resolutions, the authors introduce an iterative algorithm that merges points based on NNK similarity. This process collapses points while preserving the underlying geometric "skeleton" and density distribution of the manifold.

The multiscale framework: High-resolution NNK polytopes are merged into a coarse scale representation, preserving the embedded manifold structure.

Experiments and Results

The framework was evaluated on synthetic manifolds, the Isomap Faces dataset, and MNIST.

  • Robust ID Estimation: The NNK approach achieved results competitive with state-of-the-art estimators like DANCo. On the MNIST dataset, it estimated an ID of approximately 10, consistent with established literature.
  • Scale Invariance: In multiscale experiments, NNK-based merging kept the distribution of polytope diameters stable. In contrast, KNN-based methods caused significant shifts, losing critical density information.
  • Curvature Detection: The distribution of principal angles clearly distinguished between linear and non-linear manifolds, providing a reliable metric for local curvature.

Conclusion

By shifting the focus from "nearest" to "necessary" neighbors, NNK graphs provide a robust framework for analyzing high-dimensional data geometry. The self-adaptive nature of NNK connectivity allows for more accurate and scale-invariant estimation of manifold properties. Future research will focus on reducing computational complexity and applying these geometric tools to analyze the internal representations of deep neural networks.

Summary updated

Abstract

Modern machine learning systems are increasingly trained on large amounts of data embedded in high-dimensional spaces. Often this is done without analyzing the structure of the dataset. In this work, we propose a framework to study the geometric structure of the data. We make use of our recently introduced non-negative kernel (NNK) regression graphs to estimate the point density, intrinsic dimension, and the linearity of the data manifold (curvature). We further generalize the graph construction and geometric estimation to multiple scale by iteratively merging neighborhoods in the input data. Our experiments demonstrate the effectiveness of our proposed approach over other baselines in estimating the local geometry of the data manifolds on synthetic and real datasets.
BibTeX
@inproceedings{hurtado2023study,
  author = {Carlos Hurtado and Sarath Shekkizhar and Javier Ruiz Hidalgo and Antonio Ortega},
  title = {{Study of Manifold Geometry using Multiscale Non-Negative Kernel Graphs}},
  booktitle = {IEEE International Conference on Acoustics, Speech and Signal Processing},
  year = {2023},
  doi = {10.1109/icassp49357.2023.10095956},
}
Figure