Study of Manifold Geometry Using Multiscale Non-Negative Kernel Graphs

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

This paper presents a framework for analyzing the hidden geometric structure of high-dimensional data using a novel graph construction method called Non-Negative Kernel (NNK) regression graphs. By moving beyond traditional "fixed-neighbor" approaches, the authors provide more robust tools for estimating a dataset's intrinsic dimension, local density, and curvature across multiple scales.

TL;DR

The researchers leverage Non-Negative Kernel (NNK) graphs to better capture the local geometry of data manifolds, overcoming the rigid limitations of standard K-Nearest Neighbor (KNN) graphs. Their approach introduces new metrics for density and curvature and a multiscale merging algorithm that preserves the geometric "skeleton" of a dataset even as it is simplified.

What Problem Does This Paper Address?

Most modern machine learning models operate on high-dimensional data (like images or text embeddings). However, this data usually lies on a lower-dimensional "manifold"—imagine a 2D piece of paper crumpled up into a 3D space. To understand this manifold, researchers typically use similarity graphs like K-Nearest Neighbors (KNN).

The problem is that KNN is "geometry-blind." If you set $K=10$, the algorithm picks the 10 closest points regardless of whether they are all in the same direction or if they actually help define the local shape of the data. This makes properties like Intrinsic Dimension (ID) and curvature very difficult to estimate accurately, as the results are highly sensitive to the choice of $K$.

Methods

The authors propose using Non-Negative Kernel (NNK) regression graphs. Unlike KNN, which simply selects the closest points, NNK uses an optimization step to select a sparse set of neighbors that best represent a query point.

Key technical components include:

  • NNK Optimization: It starts with a neighborhood (like KNN) but then "prunes" redundant neighbors. If a neighbor can be explained as a combination of other, closer neighbors, it is discarded. This results in a local "polytope" (a geometric shape) around each point that is explicitly tied to the local geometry.
  • Geometric Metrics:
    • Density: Measured by the diameter of the NNK polytope.
  • Intrinsic Dimension (ID): Estimated by performing PCA on the NNK neighborhood and counting significant eigenvalues.
  • Curvature: Analyzed by looking at the "principal angles" between the tangent planes of adjacent neighborhoods. On a flat manifold, these planes align (small angles); on a curved one, they diverge.
  • Multiscale Merging: The authors introduce an iterative algorithm that merges the two "closest" points (based on NNK similarity). This allows them to study the manifold at different resolutions (coarse vs. fine) while maintaining the underlying geometric structure.

Datasets

The framework was evaluated on several standard benchmarks:

  • Synthetic Manifolds: A series of datasets with known intrinsic dimensions (ranging from $d=1$ to $d=10$) embedded in higher-dimensional spaces, both linear and non-linear.
  • Isomap Faces: A dataset of face images used to test ID estimation in a high-dimensional but structured real-world setting.
  • MNIST: The classic handwritten digit dataset, used to validate the approach on complex, non-linear real-world data.

Key Insights and Ideas

  • "Necessary" vs. "Nearest" Neighbors: The core "aha moment" is that not all neighbors are created equal. By pruning geometrically redundant connections, NNK graphs become much more robust to the initial choice of $K$.
  • Self-Adaptive Connectivity: In an NNK graph, the number of neighbors isn't fixed. It naturally varies based on where a point sits—for example, points on the edge of a manifold will have fewer neighbors than those in the center.
  • Curvature via Alignment: By measuring the angles between local subspaces, the authors can distinguish between a manifold that is simply noisy and one that is genuinely curved.
  • Geometry-Preserving Simplification: When coarsening a dataset (reducing the number of points), merging based on NNK similarity preserves the local density distribution much better than standard distance-based merging.

Key Results

  • ID Estimation: The NNK approach achieved results competitive with state-of-the-art estimators (like DANCo and MLE) across all synthetic and real datasets. For example, on MNIST, it estimated an ID of 10, which aligns with established literature.
  • Robustness to Scale: In the multiscale experiments, NNK-based merging kept the distribution of "polytope diameters" stable. In contrast, KNN-based merging caused the distribution to shift wildly, losing the original density information of the manifold.
  • Curvature Detection: The distribution of principal angles clearly distinguished between linear manifolds (where angles were mostly near zero) and non-linear manifolds (where angles were spread out).

Limitations and Future Work

While the paper demonstrates the power of NNK for geometric analysis, a few areas remain for exploration:

  • Computational Complexity: NNK requires solving a non-negative optimization problem for every point, which is more computationally expensive than a simple KNN search.
  • High-Noise Scenarios: While the authors mention robustness to noise, extremely noisy datasets might still challenge the sparse selection process of NNK.
  • Deep Learning Integration: The authors suggest this could be used to analyze the feature spaces of deep neural networks, but the current paper focuses primarily on traditional manifold benchmarks. Applying this to "black box" models to see how they warp data geometry during training is a logical next step.

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},
}

Loading related content...

Figure