Estimating the intrinsic dimension of datasets by a minimal neighborhood information

By Elena Facco, M. d’Errico, Alex Rodriguez, Alessandro Laio. 2017

477 citations recorded by the source corpus.

Analyzing large volumes of high-dimensional data is an issue of fundamental importance in data science, molecular simulations and beyond. Several approaches work on the assumption that the important content of a dataset belongs to a manifold whose Intrinsic Dimension (ID) is much lower than the crude large number of coordinates. Such manifold is generally twisted and curved; in addition points on it will be non-uniformly distributed: two factors that make the identification of the ID and its exploitation really hard. Here we propose a new ID estimator using only the distance of the first and the second nearest neighbor of each point in the sample. This extreme minimality enables us to reduce the effects of curvature, of density variation, and the resulting computational cost. The ID estimator is theoretically exact in uniformly distributed datasets, and provides consistent measures in general. When used in combination with block analysis, it allows discriminating the relevant dimensions as a function of the block size. This allows estimating the ID even when the data lie on a manifold perturbed by a high-dimensional noise, a situation often encountered in real world data sets. We demonstrate the usefulness of the approach on molecular simulations and image analysis.

Subfields: Biophysics, Molecular Biology, Representation & Self-Supervised Learning

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Biophysics

In Molecular Biology

In Representation & Self-Supervised Learning

Citations in the corpus

A Neural Scaling Law from the Dimension of the Data Manifold (2020, methodology): “We have primarily used the two nearest neighbor method [FdRL17], which was based on the MLE method [LB05] for distances among points in a local neighborhood.”
Dataset Distillation with Infinitely Wide Convolutional Networks (2021, methodology): “We use the “Two-NN” method developed by [Facco et al., 2017], which makes relatively few assumptions and allows to estimate ID only from two nearest-neighbor distances for each datapoint.”
Asymptotic learning curves of kernel methods: empirical data v.s. Teacher-Student paradigm (2019, background): “Obviously, the intrinsic dimension of the data could vary in data space, as has been reported for MNIST (Costa and Hero, 2004; Hein and Audibert, 2005; Rozza et al., 2012; Facco et al., 2017).”
Hausdorff GAN: Improving GAN Generation Quality With Hausdorff Metric (2021, background): “This is because the intrinsic dimension is relevant to the number of variables rather than the quantity [12].”
Modelling the influence of data structure on learning in neural networks (2019, background): “Its dimension can nevertheless be estimated to be around D ≈ 14 based on the neighbourhoods of inputs in the data set (Grassberger & Procaccia, 1983; Costa & Hero, 2004; Levina & Bickel, 2004; Facco et al., 2017; Spigler et al., 2019).”
The Intrinsic Dimension of Images and Its Impact on Learning (2021, methodology): “Notably, GeoMLE and TwoNN severely overestimate dimension, while the kNN graph distance method severely underestimates dimension.”
Intrinsic dimension of data representations in deep neural networks (2019, methodology): “By contrast, when the same comparison was performed on the ID (as computed using TwoNN), the trends obtained on random weights (dashed black curve) and after training the network (solid black curve) were very different.”
Redundancy, Isotropy, and Intrinsic Dimensionality of Prompt-based Text Embeddings (2025, unknown): “…of dimensions required to represent the underlying structure of data representations without significant information loss, and various meth-ods have been proposed for estimating intrinsic dimensions (Bruske and Sommer, 1998; Fukunaga and Olsen, 1971; Levina and Bickel, 2004; Facco et al., 2017).”