Data segmentation based on the local intrinsic dimension
Michele Allegra Elena Facco Francesco Denti Alessandro Laio Antonietta Mira
 

Timeseries thresholding and the definition of avalanche size
    Miguel A. Muñoz
    December 30, 2023
============================================================



empty








§ INTRODUCTION


From string theory to science fiction, the idea that we might be “glued” onto a low-dimensional surface embedded in a space of large dimensionality has tickled the speculations of scientists and writers alike. 
However, when it comes to multidimensional data such a situation is quite common rather than wild speculation: data  often concentrate on hypersurfaces of low intrinsic dimension (ID).
 Estimating the ID of a dataset is a routine task in machine learning: it yields important information on the global structure of a dataset, and is a necessary preliminary step in several analysis pipelines. 
 
In most approaches for dimensionality reduction and manifold learning, the ID is assumed to be constant in the dataset. 
 This assumption is implicit in projection-based  estimators, such as 
 Principal Component Analysis (PCA) and its variants <cit.>, Locally Linear Embedding <cit.>, and Isomap <cit.>; and it also underlies geometric ID estimators <cit.>, which  infer the ID from the distribution of between-point distances. 
The hypothesis of a constant ID complies with simplicity and intuition but is not necessarily valid. 

In fact, many authors have considered the possibility of ID variations  within a dataset <cit.>, often proposing to classify the data according to  this feature. However, the dominant opinion in the community is still that a variable ID is a peculiarity, or a technical detail, rather than a common feature to take into account before performing a data analysis.
This perception is  in part due to the lack of sufficiently general 
methods to track ID variations.
Many of the methods developed in this field make assumptions that limit their applicability to specific classes of data.


Refs. <cit.> use local ID estimators that implicitly or explicitly assume a uniform density. Refs. <cit.> jointly estimate the density and the ID from the scaling of neighbor distances, by approaches which work well only if the density varies slowly and is approximately constant in a large neighborhood of each point. Ref. <cit.> requires a priori knowledge on the number of manifolds and their IDs. 
Refs. <cit.> all require that the manifolds on which the data lay are hyperplanes, or topologically isomorphic to hyperplanes.  These assumptions (locally constant density, and linearity in a suitable set of coordinates) are often violated in the case of real-world data. Moreover, many of the above approaches <cit.> work explicitly with the coordinates of the data, while in many applications only  distances between pairs of data points are available.
To our knowledge, only refs. <cit.> do not make any assumption about the density, as they derive a parametric form of the distance distribution using extreme-value theory, which in principle is valid independently of the form of the underlying density. However, they assume that the low tail of the distance distribution is well approximated by its asymptotic form, an equally non-trivial assumption. 

In this work, we propose a method to segment data based on the local ID  which aims at overcoming the aforementioned limitations.  
Building on TWO-NN <cit.>, a recently proposed ID estimator which is insensitive to density variations and uses only the distances between points, 
we develop  a Bayesian framework that allows identifying, by Gibbs sampling, the regions in the data landscape in which the ID can be considered constant. 
Our approach works even if the data are embedded on highly curved and twisted manifolds, topologically complex and not isomorphic to hyperplanes, and if they are harvested from a non-uniform probability density. Moreover, it is specifically designed to use only the distance between data points, and not their coordinates. 
These features, as we will show, make our approach computationally efficient and more robust than other methods.
Applying our approach to  data of various origins, we  show that ID variations between different regions are common. These variations often reveal fundamental properties of the data: for example, unfolded states in a molecular dynamics trajectory of a protein lie on a manifold of a lower dimension than the one hosting the folded states.
Identifying regions of different dimensionality in a dataset 
can thus be a way to perform  an unsupervised segmentation of the data.
At odds with common approaches, we do not group the data according to their density but perform segmentation based on a geometric property defined on a local scale: the number of 
independent directions along which neighboring data are spread. 




§ METHODS




  §.§.§ A Bayesian approach for discriminating manifolds with different IDs


The starting point of our approach is the recently proposed TWO-NN estimator <cit.>, which infers the IDs from the statistics of the distances of the first two neighbors of each point.
Let the data  (x_1, x_2,...,x_N), with N indicating the number of points, be i) independent and identically distributed samples from a probability density ρ(x) with support on a manifold with unknown dimension d, such that ii) for each point x_i, ρ(x_i) is approximately constant in the spherical neighborhood with center i and radius given by the distance between
i and its second neighbor. Assumption i) is shared  all methods that infer the ID from the distribution of distances (e.g., Refs. <cit.>. Assumption ii) is the key assumption of TWO-NN: while of course it may not be
perfectly satisfied, other methods used to infer the ID from distances require uniformity of the density on a larger scale including the first k neighbors, usually with k≫2.  
Let r_i1 and r_i2 
be the distances of the first and second neighbor of x_i, then  μ_i ≐r_i2/r_i1 follows the Pareto distribution 
f(μ_i | d)=d μ_i^-(d+1). 
This readily allows the estimation of d from μ_i, i=1,2,...,N. We can write the global likelihood of μ≡{μ_i } as 

    P(μ|d)=d^N∏_i=1^N μ_i^-(d+1)=d^N e^-(d+1)V,

where V ≐∑_i=1^N log(μ_i). From Eq. (<ref>), and upon specifying a suitable prior on d, a Bayesian estimate of d is immediately obtained. This estimate is particularly robust to density variations: in <cit.> it was shown that restricting the uniformity requirement only to the region containing the first two neighbors allows properly estimating the ID also in cases where ρ is strongly varying. 

TWO-NN can be extended to yield a heterogeneous-dimensional model with an arbitrarily high number of components. Let  x={ x_i } be i.i.d samples from a density ρ(x) with support on the union of K manifolds with varying dimensions.
This multi-manifold framework is common with many  previous works investigating heterogeneous dimension in a dataset <cit.>.
Formally, let ρ(x) = ∑_k=1^K p_k ρ_k(x) where each ρ_k(x) has support on a manifold of dimension d_k and 
p≐ (p_1, p_2,...,p_K)
are the a priori probabilities that a point belongs to the manifolds 1,…,K. We shall first assume that K is known, and later show how it can be estimated from the data. The distribution of the μ_i is simply a mixture of Pareto distributions:

    P(μ_i | d, p ) ≐∑_k=1^K p_k d_k μ_i^-(d_k+1).

Here, like in ref. <cit.>, we assume that the variables μ_i are independent. This condition could be rigorously imposed by restricting the product in eq. <ref> to data points with no common first and second neighbors. In fact, one does not find significant differences between the empirical distribution of μ obtained with all points and the one obtained by restricting the sample to the independent points (i.e., the empirical distribution of μ, obtained considering entire sample, is well fitted by the theoretical Pareto law). However, restricting the estimation to independent samples generally worsens the estimates, as one is left with a small fraction (typically, ≈ 15%) of the original points. Therefore, for the purpose of parametric inference, we decide to include all points in the estimation. In SI (Table S1) we show that restricting the estimation to independent points yields results that are qualitatively in good agreement with those obtained using all points, but with generally worse dimension estimates. Following the customary approach <cit.> we introduce latent variables z≐ (z_1, z_2,...,z_K) where z_i = k indicates that 
point i belongs to manifold k. We have  P(μ_i | d, p, z  ) = P(μ_i | z_i, d) P_pr(z_i |p) with
with
P(μ_i | z_i, d )= d_z_iμ_i^-(d_z_i+1), P_pr(z_i |p)=p_z_i. 
This yields the posterior 

    P_post(z,d,p | μ)
    ∝  P (μ| z,d) P_pr(z|p) P_pr(d) P_pr(p).

We use independent Gamma priors on d, d_k ∼ Gamma(a_k,b_k) and a joint Dirichlet prior on p∼ Dir(c_1,…,c_K). 
We fix a_k, b_k, c_k =1  ∀ k, corresponding to a maximally non-informative prior on the p and an expectation of  𝔼[d_k]=1 for all k. If one has a different prior expectation on d and p, other choices of prior may be more convenient.

The posterior (<ref>)
does not have an analytically simple form, but it can be sampled by standard Gibbs sampling <cit.>, allowing for the joint estimation of d,p,z.  
However, model (<ref>) has a serious limitation: Pareto distributions with (even largely) different values of d overlap to a great extent. Therefore, the method can not be expected to correctly estimate the z_i: 
a given value μ_i may be compatible with several manifold memberships. This issue can be addressed by correcting an unrealistic feature of model (<ref>), namely, 
the independence of the z_i.
We assume that the neighborhood of a point is more likely to contain points from the same manifold than from different manifolds. This requirement can be enforced with an additional term in the likelihood that penalizes local inhomogeneity (see also Ref. <cit.>).
Consider the q-neighbor matrix 𝒩^(q) with nonzero entries 𝒩_ij^(q) only if 
j ≠ i is among the first  neighbors of i.
Let ξ be the probability to sample the neighbor of a point from the same manifold, and 
1-ξ  the probability  to sample it from a different manifold, with ξ > 0.5.
Define n_i^in as the number of neighbors of i
with the same manifold membership (n_i^in≡∑_j 𝒩_ij^(q)δ_z_i z_j). Then
we  introduce a probability distribution for 
𝒩^(q) as:

    P(𝒩^(q)|z)=∏_i=1^N ξ^n_i^in(1-ξ)^q -n_i^in/𝒵(ξ,N_z_i),

where 𝒵_q is a normalization
factor that depends also on the sizes of the manifolds (see SI for its explicit expression). This term favors homogeneity within a q-neighborhood of each point. 
With this addition, the model now reads:

    P_post(z,d,p| μ, 𝒩^(q)) 
    ∝ P( μ | z,d)  P( 𝒩^(q)|z) 
    P_pr(z|p)P_pr(d)P_pr(p).

The posterior (<ref>) is sampled with Gibbs sampling starting from a random configuration of the parameters. We repeat the sampling M times starting from different random configurations of the parameters, keeping the chain with the highest maximum log-posterior value. The parameters d and p can be estimated by their posterior averages. For all estimations, we only include the last 10% of the points. 
This ensures that the initial burn-in period is excluded <cit.>. Moreover, visual inspection of the MCMC output is performed to ensure that we do not incur in any label switching issues <cit.>. 
Indeed, we observed that once the chains converge to one mode of the posterior distribution they do not transition to different modes. 
As for the z, we estimate the value of π_ik≡ P_post(z_i = k). Point i can be safely assigned to manifold k if

π_ik > 0.8, otherwise we will consider its assignment to be uncertain. 
Note that our definition of “manifold” requires compactness: two spatially separated regions with approximately the same dimension are recognized as distinct manifolds by our approach.  


We name our method Hidalgo (Heterogeneous Intrinsic Dimension Algorithm). Hidalgo has three free parameters: the number of manifolds, K; the local homogeneity range, denoted by q; the local homogeneity level, denoted by ξ.We fix q and ξ based on preliminary tests conducted on several artificial data sets, which show that the optimal “working point” of the method is at q=3,ξ=0.8 (SI, fig. S1). As is common for mixture models, the value of K can be estimated by model selection. 
In particular, we can compare the models with K and K+1 for increasing K, starting from K=1 and stopping when there is no longer significant improvement, as measured  by the average log-posterior. 


The computational complexity of the algorithm depends on the total number of points N, the number of manifolds K, and the parameter q. As input to the Gibbs sampling, the method requires the neighbor matrix and the μ vector. To compute the latter, one must identify the first q neighbors of each point, which, starting from the distance matrix, requires
O(q N^2) steps (possibly reducible to O(q N log N) with efficient nearest-neighbor-search algorithms <cit.>). The computation of a distance matrix from a coordinate matrix takes as O(D N^2) steps, where D is the total number of coordinates. In all practical examples with N≲ 10^6 points these preprocessing steps require much less computational time than the Gibbs sampling. The complexity of the Gibbs sampler is dominated by the sampling of the Z, which scales linearly with N and K, and quadratically with q (in total, KNq^2). The number of iterations required for convergence cannot be simply estimated. In practice, we found this time to be roughly linear in N (SI, Fig S2). Thus, in practice the total complexity of Hidalgo is roughly quadratic in N. The code implementing Hidalgo is freely available at https://github.com/micheleallegra/Hidalgo.



§ RESULTS




  §.§.§ Validation of the method on artificial data





We first test Hidalgo on artificial data for which the true manifold partition of the data is known. 
We start from the simple case of two manifolds with different IDs, d_1 and d_2. We consider several examples, varying the higher dimension d_1 from 5 to 9 while fixing the lower dimension d_2 to 4. On both manifolds N=1000 points are sampled from a multivariate Gaussian with a variance matrix given by 1/d_i, i=1,2 multiplied by the identity matrix of proper dimension. The two manifolds are embedded in a space with dimension corresponding to the highest dimension d_2, with their centers at a distance of 0.5 standard deviations, so they are partly overlapping. 
In Fig. <ref>a-b we illustrate the results obtained in the case of fixed ξ=0.5, equivalent to the absence of any statistical constraint on neighborhood uniformity (note that for ξ=0.5 the parameter q is irrelevant). 
The estimates of the two dimensions are shown together with the normalized mutual information (NMI) between the estimated assignment of points and the true one. The latter is defined as the MI of the assignment and the ground truth labeling divided by the entropy of the ground truth labeling.
As expected, without a constraint on the assignment of neighbors, the method is not able to correctly separate  the points and thus to estimate the dimensions of the two manifolds, even in the case of quite different IDs (NMI<0.001). As soon as we consider ξ > 0.5, results improve. A detailed analysis of the influence of the hyperparameters q and ξ is reported in SI. Based on such analysis, we identify the optimal parameter choice as q=3,ξ=0.8.
In Fig. <ref>c-d we repeat the same tests as in <ref>a-b but with q=3 and ξ=0.8. Now the NMI between the estimated and ground truth assignment is almost 1 in all cases and, correspondingly, the estimation of d_1 and d_2 is accurate.
To verify whether our approach can discriminate between more than two manifolds (K > 2), we consider a more challenging scenario consisting of five Gaussians with unitary variance in dimensions 1,2,4,5,9 respectively. Some of the Gaussians have similar IDs, as in the case of dimensions 1 and 2, or 4 and 5: Moreover, they can be very close to each other: the centers of those in dimensions 4 and 5 are only half a variance far from each other, and they are crossed by the Gaussian in dimension 1. To analyze such dataset we again choose the hyperparameters q=3 and ξ=0.8. We do not fix the number of manifolds K to its ground truth value K=5, but we try to let the method estimate K without relying on a priori information.
We perform the analysis with different values of K=1,…,6 and compute an estimate of the average of the logarithm of the posterior value ℒ for each K.

Results are shown in Fig. <ref>e. We see that ℒ increases up to K=5, and then decreases, from which we infer that the optimal number of manifolds is K=5. In Fig. <ref>f we illustrate the final assignment of points to the respective manifolds together with the estimated dimensions, upon setting the number of manifolds to K=5. The separation of the manifolds is very good. Only a few points of the manifold with dimension 1 are incorrectly assigned to the one with dimension 2 and vice versa. The values of normalized mutual information between the ground truth and our classification is 0.89.
 
Finally, we show that our method can handle data embedded in curved manifolds, or with complex topologies. Such data should not pose additional challenges to the method: Hidalgo is sensitive only to the local structure
of data. In terms of the distribution of the first and second nearest-neighbor distances,
a 2-d torus looks exactly like a 2-d plane, 
and thus we should be able to correctly classify these objects, that are so topologically different, as 2-d objects regardless of their shape. We generated a dataset with 5 Gaussians in dimension 1, 2, 4, 5, 9
(Fig. <ref>a). Each Gaussian is then embedded on a curved nonlinear manifold:
a 1-dimensional circle, a 2-dimensional torus, a 4-dimensional Swiss
roll, a 5-dimensional sphere, and a 9-dimensional sphere. None of these manifolds is topologically isomorphic to a hyperplane, except for the Swiss roll. Moreover, the manifolds are intersecting. As shown in  Fig. <ref>b, our approach can distinguish the five manifolds. The dimensions are correctly retrieved (Fig. <ref>b), points are assigned to the right manifold with an accuracy corresponding to a value of the normalized mutual information (NMI) =0.84. Only some points of the 3d-torus are misassigned to the 4d-swiss roll. As in the previous example, ℒ increases up to K=5, and then decreases, from which we infer that the optimal number of manifolds is K=5 ( Fig. <ref>c).








  §.§.§ ID variability in a protein folding trajectory








As a first real application of Hidalgo, we address ID estimation for a dynamical system. Asymptotically, dynamical systems are usually restrained to a low-dimensional manifold in phase space, called an attractor. Much effort has been devoted to characterizing the ID of such attractor <cit.>. 
However, in the presence of multiple 
metastable states 
an appropriate description of the visited phase space may require the use of multiple IDs.
Here, we consider the dynamics of the villin headpiece (PDB entry: 2F4K). 
Due to its small size and fast folding kinetics,
this small protein is a prototypical system for molecular dynamics simulations. Our analysis is based on the longest available simulated trajectory of the system from Ref. <cit.>. 
During the simulated 125 μ s, the protein performs approximately 10 transitions between the folded and the unfolded state. 
We expect to find different dimensions in the folded and unfolded state, since these two states are metastable, and they would be considered as different attractors in the language of dynamical systems. Moreover, they are characterized by different chemical and physical features: the folded state is compact and dry in its core, while the unfolded state is swollen, with most of the residues interacting with a large number of water molecules. 
We extract the value of the 32 key observables (the backbone dihedral angles) for all the N=31,000 states in the trajectory and apply Hidalgo to this data of extrinsic dimension D=32. We obtain a vector of estimated intrinsic dimensions d and
an assignment 
of each point i to one of the K manifolds. 
We find four manifolds, three low-dimensional ones (d_1 = 11.8, d_2 = 12.9, d_3 = 13.2) 
and a high-dimensional one (d_4 = 22.7). We recall that two spatially separated regions with approximately the same dimension (in this case, d_2 and d_3) are recognized as distinct manifolds by our approach.  
To test whether this partition into manifolds is related to the separation between the folded and the unfolded state we relate the partition to the fraction of native contacts Q, which can be straightforwardly estimated on each configuration of the system. Q is close to one only if the configuration is folded, while it approaches zero when the protein is unfolded. In Fig. <ref> we plot the probability distribution of Q restricted to the four manifolds. 
We find that the vast majority of  the folded configurations (Q>0.8) are assigned to the high-dimensional manifold. Conversely, the unfolded configurations (Q≤0.8) are most of the times assigned to one of the low-dimensional manifolds. This implies that a configuration belonging to the low dimensional manifolds is almost surely unfolded.
The normalized mutual information  between the manifold assignment and the folded/unfolded classification is 0.60. Thus, we can essentially identify the folded state using the intrinsic dimension, a purely topological observable unaware of any chemical detail. 



  §.§.§ ID variability in time-series from brain imaging


In the next example, we analyze a set of time-series from functional resonance imaging (fMRI) of the brain, representing the BOLD (blood oxygen-level dependent) signal of each voxel, which captures the activity a small part of the brain <cit.>. 
fMRI time-series 
are often  projected on a lower dimension through linear projection techniques like PCA <cit.>, a step that assumes a uniform ID. However, the gross features of the signal (e.g., power spectrum and entropy) are often highly variable in different parts of the brain, and
also non-uniformities in the ID may well be present.
Here, we consider a single-subject fMRI recording containing D=202 images collected while a subject was performing a visuomotor task <cit.>. From the images we extract the N=29851 time series corresponding to the BOLD signals of each voxel.
Applying Hidalgo, we find two manifolds 
with very different dimensions d_1 = 16.2, d_2 = 31.9. 
Again, we relate the identified manifolds to a completely independent quantity, the clustering frequency Φ introduced in <cit.>, which measures the temporal coherence of the signal of a voxel  with the  signals of other voxels in the brain.
Voxels with non-negligible clustering frequency (Φ > 0.2) are likely to belong to  brain areas involved in the cognitive task at hand.  In Fig. <ref> we show the probability distribution of Φ restricted to the two manifolds.  
We find that the “task-related”  voxels (Φ > 0.2) almost invariably belong to the manifold with high dimensionality.
These voxels appear concentrated in the occipital, parietal, and temporal cortex (Fig. <ref> bottom), and belong to a task-relevant network of coherent activity <cit.>. 
The normalized mutual information  between the manifold assignment and the task-relevant/task-irrelevant classification is 0.24; note that this value is lower than for the protein folding case, because the the low-dimensional manifold is “contaminated” by many points with low Φ. 
This result finds an interesting interpretation:  the subset of “relevant” voxels gives rise to patterns that are not only coherent but also characterized by a larger ID than the remainder of the voxels. On the contrary, the incoherent voxels exhibit a lower ID, hence a reduced variability, which is consistent with the fact that the corresponding time series are dominated by low-dimensional noise. Again, this feature emerges from the global topology of the data, revealed by our ID analysis, without exploiting any knowledge of the task that the subject is performing.



  §.§.§ ID variability in financial data



Our final example is in the realm of economics. 
We consider firms in the well-known Compustat database (N=8309). For each firm, we consider D=31 balance sheet variables from the fiscal year 2016 (for details, see Table S2 in the SI). Applying Hidalgo we find 
four manifolds of dimensions d_1=5.4, d_2=6.3, d_3=7.0 and d_4=9.1. 
To understand this result, we try to relate our classification with common indexes showing the type and financial stability of a firm.
We start by relating our classification to the Fama-French classification <cit.>, which assigns each firm to one of twelve categories depending on the firm's trade. In Fig. <ref>(top) we separately consider firms belonging to the different Fama-French classes, and 
compute the fraction of firms assigned to each the four manifolds 
identified by Hidalgo.
The two classifications are not independent, 
since the fractions for different Fama-French classes are highly non-uniform.
More precisely, the normalized mutual information between the two classifications is 0.19, rejecting hypothesis of statistical independence (p-value < 10^-5). 

In particular, firms in the utilities and energy sector show a preference for low dimensions (d_1 and d_2), 
while firms purchasing products (nondurables, durables, manufacturing chemicals, equipment, wholesale) are concentrated in the manifold with the highest dimension d_4. The manifold with intrinsic dimension d_3 mostly includes firms in the financial and health care sectors. 
Different dimensions are not only related to the classification of the firm, but also their financial robustness. 
We consider the S&P quality ratings for the firms assigned to each manifold (also from Compustat; ratings are available for 2894 firms). In Fig. <ref>(bottom) we show the distribution of ratings for the different manifolds. These distributions appear to be different. We cannot predict the rating based on the manifold assignment (the normalized mutual information between the manifold assignment and the rating is 0.04), but companies with worse ratings show a preference to belong to low-dimensional manifolds: by converting ratings into numerical values scores from 1 to 8, we found a Pearson correlation of 0.22 between the local ID and the rating (p<10^-10) 
We suggest a possible interpretation for this phenomenon: a low ID may imply a more rigid balance structure, which may entail a higher sensitivity to market shocks which, in turn, may trigger domino effects in contagion processes. 
This result shows that information about the S&P rating can be derived using only the topological properties of the data landscape, without any in-depth financial analysis.
For example, no information on the commercial relationship between the firms or the nature of their business is used.




  §.§.§ Comparison with other methods




We have compared our method with two state-of-the-art methods in the literature, considering the synthetic datasets as well as the protein folding dataset (for which the folded/unfolded classification yields an approximate “ground truth”). The first method we consider is the “sparse manifold clustering and embedding” (SMCE, Ref. <cit.>). The method creates a graph by connecting neighboring points, supposedly lying on the same manifold, and then uses spectral clustering on this graph to retrieve the manifolds. As an output, it returns a manifold assignment for each point, together with an ID estimate. We resort to the implementation provided by Ehsan Elhamifar (<http://khoury.neu.edu/home/eelhami/codes.htm>). For SMCE, we can compute the NMI between the manifold assignment and the ground-truth manifold label. Furthermore, we can report the estimated local ID for points with a given ground-truth assignment, identified with the ID of the manifold to which they are assigned. SMCE requires to specify the number of manifolds K as input and depends on a free parameter λ.  To present a fair comparison, we fixed K at its ground truth value and explored different values in the range 0.01 ≤λ≤ 20, and we report the results corresponding to the highest NMI with the ground truth. Furthermore, we repeated the estimation M=10 times and kept the results with the highest NMI with the ground truth. The second method is the local ID (LID) estimation by Carter et al. <cit.>, which combines ID estimation restricted to a (large) neighborhood and local smoothing to produce an integer ID estimate for each point. We used the implementation provided by Kerstin Johnsson <cit.> 
(<https://github.com/kjohnsson/intrinsicDimension>) using a neighborhood size  k=50 which is a standard value. Note that the LID estimation is deterministic, so we do not need to repeat the estimation several times. For LID, we can compute the NMI between the (integer) label given by the local ID estimate and the ground truth; moreover, we can compute the average ID, ⟨ d ⟩ for the points with a given ground truth assignment. 

The results of the comparison are presented in Table <ref>. For the examples with two manifolds, SMCE <cit.> is able to correctly retrieve the manifolds with high accuracy (NMI≥ 0.94). The estimate of the lower dimension d_2=4 is always correct, while the highest dimension is underestimated for d_1 ≥ 7.
Overall, SMCE performs very well (even better than Hidalgo) on the datasets with two manifolds, as the two manifolds are well separated, matching well the assumptions of the model. On the examples with five manifolds, the performance of SMCE is worse, as the method cannot correctly retrieve intersecting manifolds. In the example with five linear manifolds, SMCE cannot retrieve the manifold of dimension d_1=1, which is intersecting the manifolds of dimension d_3=4 and d_4=5. Moreover, the ID estimates are quite poor.  In the example with five curved manifolds, SMCE merges the manifolds with d_4=5 and d_5=9,
and cannot retrieve the manifolds with  d_1=1 and d_3=4, which get split. Again, the dimension estimates are poor. For the protein folding data, where regions with different IDs are probably not well separated, SMCE finds a single manifold with d=11, and thus it is not able to detect any ID variation. 

For the examples with two manifolds, the LID method <cit.> is generally able to correctly retrieve regions with different IDs with high accuracy (NMI≥ 0.92), except for the case with d_1=5,d_2=4 where results are inaccurate. The estimate of the lower dimension d_2=4 is always precise, while the higher dimension is always underestimated.  The degree of underestimation increases with increasing d_1. This is expected, since the ID estimates are produced by assuming a uniform density in a large neighborhood of each point, an assumption that fails in these data, especially for points on the manifold with higher dimension. Overall, LID performs quite well (comparably with Hidalgo) in separating regions with different IDs in the datasets with two manifolds, but gives worse ID estimates than Hidalgo. In the examples with five manifolds, the performance of LID is slightly worse. In the example with five linear manifolds LID merges the manifolds of dimension d_3=4 and d_=5, and misassigns some of their points to the manifold of dimension 1. This is because relatively large neighborhoods are used for the estimation of the local ID: this leads to a difficulty in discriminating close regions with similar ID ( d_3=4 and d_4=5) and to a “contamination” of results by points of the manifold with d_1=1 intersecting the two.  In the example with five curved manifolds, LID can correctly identify the manifolds with d_2=2, d_4=5, and d_5=9, even if it underestimates the ID in the latter two cases (high dimension, large density variations). Many points in the manifold of dimension d_3=4 are mis-assigned to the manifold of dimension d_1=1, due to the fact that the two manifolds are highly intersecting. Finally, for the protein folding data, where the density is highly variable, LID shows a tendency for unfolded configurations to have a higher local ID than unfolded ones. However, it cannot discriminate between folded and unfolded configurations as Hidalgo. The ID of the folded configurations is highly underestimated compared to the Hidalgo estimate, probably because of density variations. 

In Figure <ref> we compare the results of the three methods (Hidalgo, SMCE, and LID) for the dataset with five curved manifolds. 






§ DISCUSSION


The increasing availability of a large amount of data has considerably expanded the opportunities and challenges for unsupervised  data analysis. 
Often data come in the form of a completely uncharted
“point cloud” for which no model is at hand.
The primary  goal of the analyst is to uncover some structure within the data. For this purpose, a typical approach is dimensionality reduction, whereby the data are simplified by projecting them onto a low-dimensional space. 

The appropriate intrinsic dimension (ID) of the space onto which one should project the data is not constant everywhere. In this work, we developed an algorithm (Hidalgo) to find manifolds of different IDs in the data. 
Applying Hidalgo, we observed large variations of the ID in datasets of diverse origin (a molecular dynamics simulation, a set of time series from brain imaging, a dataset of firm balance sheets).  This finding suggests that a highly non-uniform ID is not an oddity, but a rather common feature. Generally speaking, ID variations can be expected whenever the system under study can be in various “macrostates” characterized by a different number of degrees of freedom due, for instance, 
to differences in the constraints. 
As an example, the folded state the protein is able to locally explore the phase space in many independent directions, while in the unfolded
state it only performs wider movements in fewer  directions.
In the case of companies, a financially stable company may have more
degrees of freedom to adjust its balance sheet. 
 
In the cases we have analyzed, regions characterized by different dimensions were found to host data points differing in important properties. Thus, variations of the ID within a dataset can be used to classify the data into different categories. 
It is remarkable that such classification is achieved by looking at a simple topological property, the local ID.


Let us stress that ID-based segmentation should not be considered an alternative to clustering methods. In fact, in most cases (e.g., most classical benchmark sets for clustering) different clusters do not correspond to significantly
different intrinsic dimensions - rather, they correspond to regions
of high density of points within a single manifold of well-defined
ID. In such cases, clusters cannot be identified as different manifolds by Hidalgo. Conversely, when the ID is variable, regions of different IDs do not necessarily correspond to clusters in the standard meaning of the word: they may or may not correspond to regions of high density of points. 
A typical example
could be that of protein folding: while the folded configurations
are quite similar to one another, and hence constitute a cluster in
the traditional sense, the unfolded configurations may be very heterogeneous,
hence quite far in data space and then not a “cluster” in the
standard meaning of the word.



The idea that ID may vary in the same data is not new. In fact, many works have discussed the possibility of a variable ID and developed methods to estimate multiple IDs <cit.>. 




Our method builds on these previous contributions but is designed with the specific goal of overcoming technical limitations of other available approaches and make  ID-based segmentation a general-purpose tool. 
Our scheme uses only the distances between the data points, and not their coordinates, which significantly enlarges its scope of applicability. Moreover, the scheme uses only the distances between a point and its  q nearest neighbors, with q ≤ 5. We thus circumvent the notoriously difficult problem of defining a globally meaningful metric <cit.>, only needing a consistent metric on a small local scale.
Finally, Hidalgo is not hindered by density variations or curvature. 
For these reasons, Hidalgo is competitive with other manifold learning and variable ID estimation methods and, in particular, can yield better ID estimates and manifold reconstruction. We have compared our method with two state-of-the-art methods in the literature, the local ID method (LID, <cit.>), and the sparse manifold clustering and embedding (SMCE, <cit.>) method. Both methods show issues in the cases of intersecting manifolds and variable densities and yield worse ID estimates than Hidalgo, especially for large IDs. 


Hidalgo is computationally efficient and therefore suitable for the analysis of large data sets. For example, it takes ≈30 mins to perform the analysis of the neuroimaging data, which includes 30000 data points, on a standard computer using a single core. Implementing the algorithm with parallel Gibbs sampling <cit.> may considerably reduce computing time and then yield a fully scalable 
method. 
Obviously, Hidalgo  has some limitations. 
Some are intrinsic to the way the data are modeled. Hidalgo is not suitable to cover cases in which the ID is a continuously varying parameter <cit.>, or in which sparsity is so strong that points cannot be assumed to be sampled from a continuous distribution. In particular, Hidalgo is not suitable for discrete data for which the basic assumptions of the method are violated. For example, ties in the sample could lead to null distances between neighbors, jeopardizing the computation of μ.


Others are technical issues related with the estimation procedure, and, and least in principle, susceptible to improvement in refined versions of the algorithm: for instance,
one may improve the estimation with suitable enhanced sampling techniques.



Finally, let us point out some further implications of our work. Our findings suggest a caveat with respect to common practices of dimensionality reduction, which assume a uniform ID. In the case of significant variations, a global dimensionality reduction scheme may become inaccurate. 
In principle, the  partition in manifolds obtained with Hidalgo may be the starting point for using standard dimensionality reduction schemes. For example, one can imagine to apply PCA<cit.> or Isomap<cit.>, or sketchmap<cit.> separately to each manifold. However, we point out that a feasible scheme to achieve this goal does not come as an immediate byproduct of our method. Once a manifold with given ID is identified, it is highly nontrivial to provide a suitable parameterization thereof, especially because the manifolds may be highly nonlinear, and even topologically non-trivial. How to suitably integrate our approach with a dimensionality reduction scheme remains a topic for further research. Another  implication is that a simple topological invariant, the ID, can be very a powerful tool for unsupervised data analysis, lending support to current efforts at characterizing topological properties of the data <cit.>. 







  §.§.§ Data availability
 Figure 1, 2, 6 and 7 have raw simulated data. Figure 3,4,5 use real data.
All data used are publicly available in the following github repository: https://github.com/micheleallegra/Hidalgo



  §.§.§ Code availability

Code is publicly available in the following github repository: https://github.com/micheleallegra/Hidalgo






  §.§.§ Acknowledgements

 
 MA was supported by Horizon 2020 FLAG-ERA (European Union), grant ANR-17-HBPR-0001-02 during completion of this work.  
 We thank Giovanni Barone Adesi and Julia Reynolds (Institute of Finance, USI, Lugano, Switzerland) for helping us with the Compustat dataset and offering precious suggestions for its analysis.  We thank Giulia Sormani (SISSA, Trieste, Italy) for suggesting, and providing us with the protein dynamics data. We thank Alex Rodriguez (SISSA, Trieste, Italy) for helping with the analysis of protein data. 
M.A. thanks the SISSA community at large for the substantial moral and intellectual support received, which has been critical for completion of this work. 

 The authors declare that they have no
competing financial interests.  

 Correspondence and requests for materials should be addressed to A.L. (email: laio@sissa.it) and A.M.. (email: antonietta.mira@usi.ch).





  


 
 
 



§ SUPPLEMENTARY INFORMATION



Enforcing neighborhood uniformity. In our model, we wish to obtain well separated manifolds. We do not wish to impose this condition in the form of a rigid constraint, since in real cases regions with different IDs are not completely separated, but only as a “soft constraint”, privileging configurations of z such that the first neighbors of each point are preferentially assigned to the same manifold. In a Bayesian framework, this means that given that j is among the first neighbors of i, the probability that z_i = z_j is increased.

Consider the neighbor matrix 𝒩_ij^(q) defined as: 

    𝒩_ij^(q)=
    1    j≠ i i
    
    0     i=j

 
 
Intuitively, we would like to impose

    P_post(z_i = z_j | 𝒩_ij^(q)=1, μ,p) > P_post(z_i = z_j | 𝒩_ij^(q)=0,μ,p).










 

However, Eq. <ref> is a relation between posterior probabilities, hence it cannot be directly embedded in the likelihood. What we can specify in the likelihood is the probability of observing the data 𝒩_ij^(q), given an assignment z of the points. The way to enforce Eq. <ref> is assuming that the first neighbors of each point are preferentially points of the same manifold. 

Consider the i-th row of the neighbor matrix, 𝒩_i^(q)≡{𝒩_ij^(q),j=1,…,N}. 𝒩_i^(q) is a vector containing q ones and N-q zeros. Without any assumption, all configurations of q zeros and N-q ones 

are equally likely. Instead, we assume that neighbors are preferentially points from the same manifold. 
Formally, we assume that neighbors are selected forn the points of the same manifold with probability ξ
and from a different manifold with probability 1-ξ, with ξ > 1/2. Correspondingly, we introduce a new term in the 
likelihood:

    ℒ(𝒩_i^(q)|z)
    =ξ^n_i^in(z)(1-ξ)^q-n_i^in(z)/𝒵(ξ,N_z_i),

where 

    n_i^in(z)=∑_j𝒩_ij^(q)𝕀_z_j=z_i

is the number of neighbors of i sampled from the same manifold, and 

    q-n_i^in(z)= ∑_j𝒩_ij^(q)𝕀_z_j≠ z_i

is the number of neighbors of i sampled from a different manifold. Function 𝒵 is a normalization factor that depends on ξ:

    𝒵(ξ,N_z_i)=∑_{𝒩_i^(q)}ξ^n_i^in(z)(1-ξ)^q-n_i^in(z).

and can be expressed in a compact way as 

    𝒵(ξ,N_z_i)=(1-ξ)^qN-N_z_iq_2F_1(-q,1-N_z_i,N-N_z_i-q,ξ/1-ξ),

where _2F_1(a,b,c,x) is the hypergeometric function. The derivation of this expression and the details about the likelihood term in (<ref>) are presented below. 
By considering all points i, we obtain the global likelihood 

    ℒ(𝒩^(q)|z, ξ)=∏_iℒ(𝒩_i^(q)|z, ξ)=∏_kξ^n_k^in(1-ξ)^qN_k-n_k^in/𝒵(ξ,N_k)^N_k

where

    n_k^in=∑_ij𝒩_ij^(q)𝕀_z_i=k𝕀_z_j=k

is the total number of  “internal” neighbors of points from manifold
k and

    n_k^out=∑_ij𝒩_ij^(q)𝕀_z_i=k(1-𝕀_z_j=k)=qN_k-n_k^in

is the total number of “external” neighbors of points from k. Note that since 𝒵 depends on i only through the hidden variables z we are able to split the product into K components.

With this additional term in the likelihood, we obtain

P_post(z_i = z_j | 𝒩_ij^(q)=1, μ,p) / P_post(z_i = z_j | μ,p) = ξ/1-ξ > 1/2.




















Derivation of the neighborhood uniformity term. 

With reference to 𝒩_i^(q), without any assumption, all configurations containing q zeros and N-q ones  

are equally likely. It is easy to compute the number of such configurations. The problem is analogous to the problem of selecting q balls from a box containing N-1 balls: we have to choose q neighbors among N-1 points, point i being excluded. The number of possible choices is N-1q. Hence, all configurations of 𝒩_i^(q) being equally likely we would have



ℒ(𝒩_i^(q)|z)=N-1q^-1,     ∀i.

Instead, we assume that the neighbors of a point are preferentially points from the same manifold. 
Formally, we assume that neighbors are selected with probability ξ among the N_z_i points assigned to the same manifold of i, and with probability 1-ξ among the N-N_z_i points assigned to a different manifold. Here ξ > 1/2, so that configurations with neighbors assigned to the same manifold are more likely. 
Now, the problem is analogous to the problem where we have to select q
balls from two boxes, a black box containing N_b balls and a white one
containing N_w balls. Before selecting each ball, we choose the box,
 the black one with probability ξ and the white one
with probability 1-ξ. Clearly, the probability of a choice with n_b black and q-n_b white 
balls is then proportional to ξ^n_b(1-ξ)^q-n_b.
For a given n_b, the number of possible choices of balls is 

    N_bn_bN_wq-n_b




One can easily verify that ∑_n_b=0^qN_bn_bN_wq-n_b=N_b + N_wq. The probability of a given choice is then

    ξ^n_b(1-ξ)^q-n_b/𝒵

where 𝒵=∑_n_b=0^qN_bn_bN_wq-n_bξ^n_b(1-ξ)^q-n_b.
By using the formula (Abramowitz and Stegun, 15.4.1)

    _2F_1(-m,b,c,z)=∑_n=0^m(-)^nmn(b)_n/(c)_nz^n

where (a)_n=a(a+1)… (a+n-1) is the Pochammer symbol and doing some simple algebra, 𝒵 can be compactly expressed as 

    𝒵=(1-ξ)^qN_wq_2F_1(-q,-N_b,N_w-q,ξ/1-ξ).

Replacing N_b with N_z_i-1 (the number of points assigned to the same manifold as i, excluding i), N_w with N-N_z_i (the number of points assigned to a different manifold), and n_b with n_i^in, we obtain the likelihood of a given configuration of 𝒩_i^(q) as

    ℒ(𝒩_i^(q)|z,ξ)=ξ^n_i^in(z)(1-ξ)^q-n_i^in(z)/(1-ξ)^qN-N_z_iq_2F_1(-q,1-N_z_i,N-N_z_i-q,ξ/1-ξ).






















Choice of the free parameters. In order to find a good configuration for the parameters (q, ξ),
we perform tests with several values of q ∈{2,3,…,10} and ξ∈ [0.5,1) for all the artificial datasets used for validation: i) two manifolds of dimension 4 and 5, with a Gaussian density of points; ii) five manifolds of dimension 
1,2,4,5,9, with a Gaussian density of points; iii) five manifolds of dimension 1, 2, 4, 5, 9, with a Gaussian density of points, embedded on a 1-dimensional circle, a 2-dimensional torus, a 4-dimensional Swiss roll, a 5-dimensional sphere and a 9-dimensional sphere. 

The crucial figure of merit to assess the performance of the method is the normalized mutual information (NMI)  between the estimated and the true assignment of z, which measures the quality of the assignment of points to manifolds. Indeed, once the manifolds are correctly separated, the problem is essentially reduced to a dimension estimation within the single manifolds (which is successfully solved by TWO-NN). In Fig. <ref>  we show the NMI as a function of (q, ξ). In all cases, we performed 10^5 iterations of the Gibbs sampling and repeated the sampling M=10 times starting from different random configurations of the parameters. We kept the sampling with the highest maximum average of the log-posterior value. 

For all values of q, the MI first increases and then decreases with ξ. This can be expected based on the following considerations. When ξ is close to 0.5, as we discussed above, the method cannot discriminate between different manifolds. When ξ is increased, the posterior distribution starts to prefer configurations that approximately satisfy the neighborhood homogeneity constraint. For sufficiently high ξ, the posterior distribution is sharply peaked at the configuration that optimally satisfies this constraint; correspondingly, if the Gibbs sampler can explore the parameter space exhaustively, it will eventually find this peaked region and remain trapped there. Hence, the NMI achieves average values close to 1. However, for ξ close to 1, the posterior distribution is very likely to also have pronounced local maxima. Therefore, depending on the initial configuration, the sampler may remain trapped in one of them. 

Hence, one can observe a drop in the NMI. 

In general, these sampling issues can be worsened when q is increased since the local maxima become more and more pronounced. In principle, this problem may be dealt with by resorting to well established enhanced sampling techniques.

For simplicity, in the present work, we prefer to verify that there is a region of the parameter space where the results appear optimal and restrict to these regions for subsequent analyses. 

In general, q=2 yields poor results (NMI≲ 0.4) in all cases. This means that is general q=2 is too low to effectively enforce the uniformity constraint. Analogously, q=10 too high yields poor results (NMI≲ 0.5), except in the simple case of two manifolds. There are two independent reasons for this behavior. First, q=10 can lead to sharp peaks in the posterior, and hence to sampling issues; second, q=10 gives issues in the case of intersecting manifolds, as it enforces uniformity on too large a scale. Good results (NMI≳ 0.75) are found for q=2, 0.75 ≤ξ≤ ,0.80,0.85 and for q=5, 0.65 ≤ξ≤ 0.70. Based on these findings, we identify the optimal “working point" of the method at q=3, ξ=0.8, which yields NMI > 0.80) for all data sets considered. 




Convergence time as a function of sample size. 



In order to test the speed of convergence of the Gibbs sampling as a function of the number of points N, we have generated random data sampled from two manifolds of dimension d_1=9 and d_2=4. As in Results, N/2 points are sampled from a multivariate Gaussian with  a variance matrix given by 1/d_i, i=1,2, times the identity matrix of proper dimension. The two manifolds are embedded in a space with dimension corresponding to the higher dimension d_2, with their centers at a distance of 0.5 standard deviations. We consider different sample sizes N=2^i, {i=6,15 }. 
In order to test convergence, we use the criterion in <cit.>. Given independent samples Y_t (with t=1,…,T and T the total number of samples), and given a function f_t=f(Y_t), convergence can be verified from the behavior of the cumulative sums

    S_t =  ∑_τ=t_0+1^t (f_τ - μ)

where μ = 1/T-t_0∑_τ=t_0+1^T f_τ, and t_0 ≥ 1 is any time, usually chosen as higher to the putative burn-in time. At convergence, the behavior of F_t is highly non-smooth; In particular, consider the indicator variable

    e_t =   {
    1  S_t>S_t-1 S_t < S_t-1
    
    1  S_t<S_t-1 S_t > S_t-1
     
    0 .

which indicates whether S_t has a local maximum/minimum at t. At convergence, approximately half of the points should be local minima or maxima. Formally, e_t behaves as a Bernoulli variable ℬ(1/2), and consequently

    E_t =  ∑_τ=t_0+1^t-1 e_τ

behaves as a binomial variable B(t-t_0-1,1/2). Therefore, one should have

    1/2 - Z_α/2/√(t-t_0-1)≤  E_t ≤ 1/2 + Z_α/2/√(t-t_0-1)

for at least (1-α)% of the time (for large t, the binomial will be approximately normal). In other words, when convergence is reached, E_t should fluctuate around 1/2 with a variance compatible with that of a binomial variable. 

To adopt this test to the data, we studied the point-wise dimension estimates d_1t and d_2t. We subsampled the d_it at t=1,θ,2θ,… with θ=10 to ensure independence of the samples. Let D_1t and D_2t be the resulting samples. We used f_1τ=d_1t and f_2τ=d_2t and first verified whether the corresponding E_1t, E_2t  (Eq. <ref>) converged to 1/2. While an excessive variance around 1/2 is a sign of residual non-stationarity, failure of E_t to approach the value 1/2 for increasing t is a likely sign of the non-independence of the samples used <cit.>. Therefore, if E_it did not approach to 1/2, we increased the subsampling at θ=20,θ=50,θ=100,θ=200,θ=500 until ⟨ E_it⟩≃ 1/2 for large t. We divided the D_1t and D_2t in non-overlapping windows of 20 successive points and checked whether E_it was within the bounds (<ref>) with α=0.05 for 95% of the times (at 19 times out of 20) within each window. We then defined as convergence time T_conv the time corresponding to the first window where 
both E_1t, E_2t were satisfying the criterion. 

For each dataset size N, we repeated the assessment of T_conv for M=20 independent Gibbs samplings.  
The results are shown in Fig. <ref>: one can see that the convergence time increases roughly linearly with data size N. 






Restricting the analysis to points with no common first and second neighbor. 







Compustat variables used. 








