TOAST: Topological Algorithm for Singularity Tracking
Authors: Julius Von Rohrscheidt
Bastian Rieck
Venue: Submitted to ICLR 2023 (2023)
Keywords: topology
persistent homology
topological data analysis
tda
stratified spaces
singularities

Abstract: The manifold hypothesis, which assumes that data lie on or close to an unknown manifold of low intrinsic dimensionality, is a staple of modern machine learning research. However, recent work has shown that real-world data exhibit distinct non-manifold structures, which result in singularities that can lead to erroneous conclusions about the data. Detecting such singularities is therefore crucial as a precursor to interpolation and inference tasks. We address detecting singularities by developing (i) persistent local homology, a new topology-driven framework for quantifying the intrinsic dimension of a data set locally, and (ii) Euclidicity, a topology-based multi-scale measure for assessing the ‘manifoldness’ of individual points. We show that our approach can reliably identify singularities of complex spaces, while also capturing singular structures in real-world data sets.

Under review as a conference paper at ICLR 2023
TOAST: TOPOLOGICAL ALGORITHM FOR SINGULARITY TRACKING
Anonymous authors Paper under double-blind review
ABSTRACT
The manifold hypothesis, which assumes that data lie on or close to an unknown manifold of low intrinsic dimensionality, is a staple of modern machine learning research. However, recent work has shown that real-world data exhibit distinct non-manifold structures, which result in singularities that can lead to erroneous conclusions about the data. Detecting such singularities is therefore crucial as a precursor to interpolation and inference tasks. We address detecting singularities by developing (i) persistent local homology, a new topology-drives framework for quantifying the intrinsic dimension of a data set locally, and (ii) Euclidicity, a topology-base based multi-scale measure for assessing the 'manifoldness' of individual points. We show that our approach reliably identify singularities of complex spaces, while also capturing singular structures in real-world data sets.
3
7
11
INTRODUCTION
The ever-increasing amount and complexity of real-world data necessitate the development of new 14 methods to extract less complex-but still meaningfiul approach this problem is via dimensionality reduction techniques, where the data is assumed to 16 be of strictly lower dimension than its number of features. Traditional algorithms in this field such PCA restricted to linear descriptions of data, and are therefore of limited non-linear data sets that often appear in practice. By contrast, non-linear dimensionality reduc-
the underlying data. One
17
for complex,
18
19 tion algorithms, such as UMAP (Mcinnes al.] 2018), t-SNE (van der Maaten & Hinton 2008),
20 or autoencoders (Kingma & Welling 2019) share one common assumption: the underlying data is
21 supposed be close to manifold with small intrinsic dimension, i.e. while the input data may have a n-dimensional manifold with < N that best describes the 23 data. For some data sets, this manifold hypothesis is appropriate: certain natural images are known
22 large ambient dimension N, there is a
24 to be well-described by a manifold, for instance (Carlsson) 2009), enabling the use of specialised
25 autoencoders for visualisation (Moor et al., 2020). However, recent research shows evidence that the manifold hypothesis does not necessarily hold for complex data sets (Brown al. 2022), and
27 that manifold learning techniques tend to fail for non- non-manifold data (Rieck & Leitte 2015 Scoccola & Perea 2022). These failures are typically the result of singularities, i.e. regions of space that violate the properties of a manifold. For example, the 'pinched torus,' an object obtained by com-
29
30 pressing a neighbourhood of random point a torus a single point, fails to satisfy the manifold hypothesis at the 'pinch point:" this point, unlike all other points of the 'pinched torus,' does not have a neighbourhood homeomorphic IR (see Fig. [ for illustration).
31
32
33 Since singularities-unn unlike outliers that arise from incorrect labels, for example-may carry relevant information (Jakubowski et al. 2020), we address the shortcomings of existing dimensionality re- duction methods by assuming an agnostic view on any given data set. Instead of trying to prescribe the rigid requirements of manifold, we consider intrinsic dimensionality to be a fundamentally
34
35
36
37 local phenomenon: we permit dimensionality to vary across points in the data set, and, more im-
38 portantly, across the scale of locality to be considered. The only assumption we make that the data is of significantly lower dimension than the dimension of the ambient space. This perspective
40 enables us to assess the deviation of individual points from idealised non-singular spaces, resulting in measure of the Euclidicity of point. Our method is based on a local version of topological data
42 analysis (TDA), a method from computational topology that is capable of quantifying the shape of data set on multiple scales (Edelsbrunner & Harer 2010

---

of this homology class. There are several distance measures for comparing persistence diagrams, Under review as a conference paper at ICLR 2023
PLH
0.04
0.09
0.14
Input space
Persistent intrinsine dimennsion
Euclidicity
Figure 1: Overview of our method. Using persistent local homology (PLH), we derive persistent intrinsic dimension and, subsequently, a Euclidicity score that measures the deviation from a space to Euclidean model space. Here, Euclidicity highlights the singularity at the 'pinch point." Please refer to Section for more details.
44
Our contributions. We present a universal framework for detecting singular regions in data. This framework is agnostic with respect geometric or stochastic properties of the underlying data and only requires a notion of intrinsic dimension of neighbourhoods. Our approach is based on a novel
45
46
47
formulation of persistent local homology (PLH), multi-parameter tool that detects the shape of
48
local neighbourhoods of given point in the data set, making use of multiple scales of locality.
49
We employ PLH in two different capacities: (i) We use PLH to estimate the intrinsic dimension of a point locally. This enables us to assess how complex a given data set is, both in terms of the
50
51
magnitude of the intrinsic dimension and in terms of the variance of its intrinsic dimension across individual points. (ii) Given the intrinsic dimension of the neighbourhood of a point, we use PLH to measure Euclidicity, a novel quantity that we define to measure the deviation of a point from being Euclidean. We also provide theoretical guarantees on the approximation quality for certain classes of spaces and show the utility of our proposed method experimentally on several data sets.
53
55
2 BACKGROUND: PERSISTENT HOMOLOGY AND STRATIFIED SPACES
57 We first provide an overview of persistent homology and stratified spaces, as well as their relation
58 to local homology. The former concept constitutes a generic framework for assessing complex data at multiple scales by measuring its topological characteristics such 'holes' and "voids," while the latter will subsequently serve as a general setting to describe singularities, in which our framework admits advantageous properties.
60
Persistent homology. Persistent homology is a method for computing topological features at dif- ferent scales, capturing an intrinsic notion of relevance in terms of spatial scale parameters. Given finite metric space (X, d), the Vietoris-Rie Rips complex at step t is defined as the abstract simplicial complex V(X. t), in which an abstract k-simplex (Io...., xx) of points in X is spanned and only if 25) < & for all 0 i j a filtration, i.e. a sequence of nested simplicial complexes, which we denote by V(X, .). Applying the ith homology functor to this collection of spaces and inclusions between them induces maps 89 on the homology level //i H; HV (1)) - H;(V(X, (2)) for any 4 < l2. The ith persistent homology (PH) of X with respect to the Vietoris-Rips construction is defined to be the collection of all these ith homology groups, together with the respective induced maps between them, and
65
65
j < I For t S 12, the inclusions V(X, 41 V(X, (2) yield
67
88
70
71
72 denoted by PH, PH can therefore be viewed as a tool that keeps track of topological fea-
73 tures such as holes and voids on multiple scales. For a more comprehensive introduction to PH in
74 the context of machine learning, see Hensel et al. (202T). The so-called 'creation' and 'destruc-
75 tion' times of these features are summarised in a persistence diagram D C x R {oo), where
76 any point (b, d) E D corresponds to homology class that arises at filtration step b, and lasts un-
77 til filtration step d. The difference Id - is referred to as the lifetime or eponymous persistence
79 one of them being the bottleneck distance dg. For two persistence diagrams D, D', is defined as du (D, D') inf., supzed I| >x)) where y ranges over all bijections between D and D'.
For readers familiar with persistent homology, depart from the usual convention of using the threshold parameter since will require it denote the scale of our persistent local homology calculations.
2

---

Under review as a conference paper at ICLR 2023
81
Stratified spaces. Manifolds are widely studied and partic- ularly well-behaved topologiaal spaces: they locally resemble Euclidean space near any point. However, spaces that arise naturally often violate this local homogeneity condition, for example due to the occurrence of singularities (see Fig. for an example), or since the space is of mixed dimensions. Strat- ified spaces generalise the concept of manifold such that singular spaces are also addressed. Large classes of singu- stratified spaces, including
88
x
84
85
(a)
(b)
86
87
Figure 2:
aa
Non-manifold space.
86
(b) Annulus around a regular
89
lar spaces can be formulated (i) complex algebraic varieties, (ii) spaces that are disjoint unions of a finite number of manifolds of arbitrary dimen- sions, and (iii) spaces that admit isolated singularities. Being thus intrinsically capable of describing a wider class of spaces, we argue that stratified spaces are the right tool to analyse real-world data. Subsequently, we define stratified spaces in the setting of simplicial complexes. A stratified simplicial complex] of dimension 0 is finite set of points with the discrete topology. A stratified simplicial complex of dimension n is an n-ddimnnsional simplicial complex X, together with filtration of closed subcomplexes X X,, Xn-1 Xn- 3 C X-1 = 0 such that X; - is an i- i-dimensional manifold for all i. and such that every point X a compact stratified simplicial complex of dimension n k- and c² refers to the open cone construction (see Ap- pendix[A.] If X is a manifold, then independently of the point under consideration,
point X.
(c)
Annulus around
90
singular point. The neighbourhood
91
around y different from all others.
92
94
96
97
98
possesses a distinguished local neighbourhood U R c L in X, where
99
100
101
given by a sphere since for manifold, any point admits a local neighbourhood that is homeomorphic to R". This observation will serve as the primary motivation for our Euclidicity measure in Section 4.2
102
103
Local homology. Local homology serves tool quantify topological properties of infinites- imal small neighhourhoods of a fixed point. For a topological space X and x E X, its ith local \ x)
105
106
limy H, H, X U), where the direct system is given by the induced maps on homology that arise via the inclusion of (small) neighbourhoods of When X is a simplicial complex, we may view x as a vertex in X, using subdivision if neces- sary. Its star St(z)) is defined be the union of simplices in X that have as a face, whereas its link Lk(x) consists of all simplices in St(x) that do not have æ as face. Using excision and the long
homology group is defined H,(X, X
107
108
109
110
111
exact homology sequence (see Appendix A.3)
we have
H, x) (Lk(x))
The key takeaway here is that the homology of T.K(x)) will usually differ from the homology of a sphere, once [x(x) is not homotopy-equivalent to a sphere. For example, when & is an isolated singularity in a stratified simplicial complex X of dimension n. then its distinguished neighbourhood
113
114
115 is given by U = e² L. Thus, Lk(x) L and H;(X, X x) H by Eq. (1. which is usually
116 different from H (S when x does not admit Euclidean neighbourhood. This observation
117
motivates and justifies using local homology for detecting -un-uulidean neighbourhoods.
3
RELATED WORK
118
119
Methods from topological data analysis have recently attracted much attention in machine learning, particularly due to persistent homology, which captures global topological properties of the under- lying data set on different scales. We give a brief overview of existing methods in the emerging field of topology-driven singularity detection, outlining the differences to our approach below. Several works already assume local perspective on homology to detect information about the intrinsic di-
120
121
122
123
124
mensionality of the data or the presence of certain singularities. Rieck et al. (2020) define persistent intersection homology via known stratifications, whereas Fasy & Wang (2016) and Bendich 20088),
126
for instance, both present persistent versions of local homology. By contrast, [ttlz et al. (2020) follow different approach, where local homology is approximated as the absolute homology of
2 Here, we actually mean the geometric realisation of the corresponding simplicial complex; by abuse of notation we may denote both ohjects by the term 'simplicial complex.' 'Heuristically, a local homology class can he thought of as homology class of an infinitesimal small punctured neighbourhood of point.
3

---

Under review as a conference paper at ICLR 2023
small annulus of a given neighbourhood, resulting in an algorithm for geometric anomaly detec- tion (which requires knowing the intrinsic dimension of the data set). [endiihh et al. (2077) employ persistence vineyards, i.. continuous families of persistence diagrams, to assess the local homology of a point in a stratified space, whereas Dey et al. (2014) use local homology to estimate the (global) intrinsic dimension of hidden, possibly noisy manifolds. While manifold learning is concerned with
129
130
131
132
133
the development of algorithms that extract geometric information under the assumption that the given data lie on a manifold. Broown al. (2022) recently introduced the idea assume data spaces to consist of a union of manifolds. Intrinsic dimension is thus allowed to vary across connected components of the data space, but singularities are excluded under this assumption, whereas our framework detects the correct intrinsic dimension for large classes of singular spaces. [Birdal et al.) 2 define a global persistent homology dimension for describing neural networks; our persistent intrinsic dimension, by contrast, is local and may thus change across different points in the data set.
134
135
136
137
138
139
140
Key differences to existing approaches. Our approach crucially differs from existing approaches in essential components. In comparison all aforementioned contributions, we capture additional local geometric information: we consider multiple scales of locality in a persistenl framework for local homology. Concerning the overall construction, (ttlz et al. (2020) is the closest to our method. However, the authors assume that the intrinsic dimension is known and the proposed algorithm uses a fixed scale, whereas our approach (i) operates in a multi-scale setting, (ii) provides local estimates of intrinsic dimensionality of the data space, and (iii) incorporates model spaces that serve com- parison. We can thus measure the deviation from an idealised manifold, requiring fewer assumptions on the structure of the input data (Section 5.4 demonstrates the benefits of this perspective).
141
142
143
144
145
146
147
METHODS
149
Our framework TOAST (Topological Algorithm for Singularity Tracking) consists of two parts: (i) a method to calculate a local intrinsic dimension of the data, and (ii) Euclidicity, a measure for assessing the multi-scale deviation from Fuclidean space. TOAST is based on the assumption that the intrinsic dimension of some given data is not necessarily constant across the data set, and is best described by local measurements, i.e. measurements in small neighbourhood of a given point. Since there is no canonical choice for the magnitude of such neighbourhood, TOAST is built on multi-scale analysis of data. Our main idea involves constructing a collection of local (punctured)
151
152
153
154
155
156
157
neighbourhoods for varying locality scales, and subsequently recording their topological features. This procedure allows us to approximate local topological features (specifically, local homology) of a given point, which we use to measure the intrinsic dimensionality of space. Moreover, by calculating the distance to Fuclidean model spaces, we are capable of detecting singularities in a large range of input data sets. Subsequently, we will briefly describe the 'moving parts' of TOAST; please refer to Appendix I. for a terminology list.
158
160
162
163
4.1 PERSISTENT INTRINSIC DIMENSION
184
For a finite metric space (X, d) and x X. let B2(2) == e X 5 < $} denote the intrinsic annulus of x in X with respect to the parameters and s. Moreover, let F denote a procedure that takes as input a finite metrie space and outputs an ascending filtration of topological spaces such as a Vietoris-Rip filtration. By applying F to the intrinsic annulus of x, we obtain a tri- filtratiion (F(B; (x), r)....... where corresponds to the respective filtration step that is deter- mined by F. Note that this tri-filtration is covariant in and f, but contravariant in r;; we denote it by F(B (z), )). Applying ith homology to this filtration yields a tri-parameter persistent module that call ith persistent local homology (PLH) of denoted by PIH, F) = PH, (F(B((z))), ))). To the best of our knowledge, this is the first time that PLH is considered as a multi-parameter per- sistence module. Since the Vietoris-Rips filtration is the pre-eminent filtration in TDA, we will also
185
186
167
168
170
172
173
174
use the abbreviated notation (z) == (I; V).
175
Our PLH formulation enjoys stability properties similar to the seminal stability theorem in persistent homology (Cohen-Steiner et al. 2007). making it robust to small parameter changes (we assess empirical stability in Section 5.1
178
177
Theorem 1. Given a finite metric space X and x E X, let Bx(x) and B (x) (x) denote two intrinsic annuli with Ir r'l & e1 and is 8 S 62. Furthermore, let D, D' denote the
178
179
4

---

Under review as a conference paper at ICLR 2023
(x)
(o)
(a).
(1B
Figure 3:
The intrinsic annulus (x) around a point æ in a metric space (X, d), as well as three filtration steps with varying parameters. By adjusting and 8, obtain tri-filtration.
persistence diagrams corresponding PH,((;(z): and (B) respectively, Then dB(D, S maxfe1, 22).
180
181
For finite set of points C R. and x E X. we define the persistent intrinsic dimension (PID) of r at scale as (e) == max(i E IN PH;-1 (1; (x)) بf 0 for some and with s < e). This measure serves as a multi-scale characterisation of the intrinsic dimension of a data set. case our data set constitutes manifold sample, it turns out that we can recover the correct dimension.
182
184
Theorem 2. Let M C R be an n-dimensional compact smooth manifold and let X == #1...... FS} } be collection of uniform samples from M. For sufficiently large S, there exist > O such that (e(e) = for all El < E < and any point x E X. Moreover, can be chosen arbitrarily small by increasing S.
186
188
constants e1, E2 e,,
189
180
The implication of Theorem is that iz(() computes the correct intrinsic dimension of M in a certain range of values e >> O, provided the sample is sufficiently large. In particular, (c((c) persists this range, which suggests to consider collection of ig (c) for varying e to analyse the intrinsic dimen- sion of æ. We also have the following corollary, which specifically addresses stratified spaces (such as the 'pinched torus'), implying that our method can correctly detect the intrinsic dimension of individual strata. PID is thus capable of handling large classes of 'non-manifold' data sets.
191
192
193
194
195
X-1 1 be n-dimensional compact stratified simplicial complex, s.f. X4 X1-1 smooth for every i. For a fixed i, let X; = fa1:---, Ks) be collection of uniform samples from X; X,-1- For a sufficiently large S. there are constants 61, <2 > O such that iz(c) = for all 6 < 6 < (2 and any point x E X,. Moreover, 6 can be chosen arbitrarily small by increasing S.
Corollary 1.
Let X Xx, Xn-1 Xn-2 ]
197
199
4.2 EUCLIDICITY
202
Knowledge about the intrinsic dimension of neighbourhood is crucial for measuring to what extent such a neighbourhood deviates from being Euclidean. We refer this deviation as Euclidicity, with the understanding that low values indicate Euclidean neighbourhoods while high values indicate singular regions of data set. Euclidicity can be calculated without stringent assumptions on mani- foldness: let X C R be a finite data set, x E X a point, and assume that we are given an estimate of the intrinsic dimension of x. In particular, the previously-describer PID estimation procedure applicable in this setting and may be used obtain n., for example by calculating statistics the set of (c) for varying locality parameters e. Euclidicity, however, can also make use of other di- mensionality estimation procedures (see Camassta & Staiano (2016) for survey). To assess how far given neighbourhood of x from being Euclidean, we compare it to a Euclidean model space by measuring the deviation of their corresponding persistent local homology features. We start by defining the Euclidean annulus EB, (x) of x for parameters and s to be set of random uniform samples of ty R" < d(z, y) < $} such that [x) [x)( Here, and correspond
203
204
205
207
209
211
213
214
215
to the inner and outer radius of the Euclidean annulus, respectively. For r' < and S s' we extend (x) by sampling additional points to obtain EBC (x)) with |EB (x) = (B:((x:) Iterating this procedure leads to a tri-filtration (F(EB; (c),, t)),... for any filtration F, following our description
217
218
in Section
4.1 We now define the persistent local homology of a Euclidean model space as
PLH F) = PHH((FFF))))))
5

---

Under review as a conference paper at ICLR 2023
Again, for a Vietoris Rips filtration V. we use short-form notation, i.e. PLH PLH,(LL (2; V).
Notice that P (a) implicitly depends on the choice of intrinsic dimension n, and on the samples
220
that are generated randomly. To remove the dependency on the samples, we consider PLH, (x)
221
to be a sample of random variable PLH, (z). Let -(---) be distance measure for 3-parameter
222
223
persistence modules, such as the interleaving distance We then define the Euclidicity of z, denoted by (()), as the expected value of these distances, i.e.
224
((x) = F. (PLH..-1())) PLH -
225
This quantity essentially assesses how far x is from admitting a regular Euclidean neighbourhood.
228
Implementation. Calculating (xx) requires different choices, namely (i) a range of locality scales, (ii) a filtration, and (iii) a distance metric between filtrations D. Using grid I' of possible radii (r, s) with 8, we approximate Eq. using the mean of the bottleneck distances of fibred Vietoris-Rips barcodes, i.e.
227
228
229
((x) = ((PLHH()),
1 Σ (V(PH,)V( )) (V(BB, ))), (4)
= C (r,a)ET
where C' is equal to the number of summands and PLH, (z) refers to a sample from Euclidean
E
231
annulus of the same size as the intrinsic annulus around x. Eq. 4 can be implemented using effective persistent homology calculation methods (Bauer) 202T), thus permitting integration into
existing TDA and machine learning frameworks (The GUDHI Project 2015) Tauzin et al.) 2020).
233
Appendix A.4 [.44| provides pseudocode implementations, while Section [5] discusses how to pick these parameters in practice. We make one specific instantiation of our framework publicly available 5
235
236
The main appeal of our formulation is that calculating both PID and Euclidicity does not require strong assumptions about the input data. Treating dimension as a local quantity that is allowed to vary across multiple scales leads to beneficial expressivity properties. As we showed in Section 4.1 our method is guaranteed to yield the right values for manifolds and stratified sim- plicial complexes. This property substantially increases the practical applicability and expressivity, enabling our framework to handle unions of manifolds of varying dimensions, for instance. We require only a basic assumption, namely that the intrinsic dimension n of the given data space significantly lower than the ambient dimension N, making Euclidicity broadly applicable. Similar to curvature, Euclidicity makes use of the fact that one can compare data to 'model spaces,' allowing for different future adjustments.
Properties.
237
238
239
240
242
244
246
Limitations. Our implementation of Euclidicity makes use of the Vietoris Rips complex, which is known to grow exponentially with increasing dimensionality. While all calculations of Eq. (3) can be performed in parallel-thus substantially improving scalability vis-à-vis persistent homology on the complete input data set, both in terms of dimensions and in terms of samples-thy the memory require- ments for full Vietoris-Rips complex construction may still prevent our method to be applicable for certain high-dimensional data sets. This can be mitigated by selecting a different filtration (Anai)
248
250
251
252
ct al. 2020; Sheehyy (013);; our proof's do not assume a specific filtration, and we leave the treatment
253
of citraation-spcffic theoretical properties for future work. Finally, we remark that the reliability of
254
the Euclidicity score depends on the validity of the intrinsic dimension; otherwise, the comparison
255
does not take place with respect to the appropriate model space.
256
EXPERIMENTS
We demonstrate the expressivity of our proposed TOAST procedure in different settings, empiri- cally showing that it (i) calculates the correct intrinsic dimension, and (ii) detects singularities when analysing data sets with known singular points. We also conduct comparison with one-parameter approaches, showcasing how our multi-scale approach results in more stable outcomes. Finally, we analyse Euclidicity scores of benchmark datasets, giving evidence that our technique can be used as a measure for the geometric complexity of data.
258
259
280
261
262
In our implementation, we will approximate this distance via the bottleneck distance. See the supplementary materials for the code and experiments.

---

Under review as a conference paper at ICLR 2023
5.1
PARAMETER SELECTION
264
Since Eq. (3) intrinsically incorporates multiple scales of locality, we need to specify an upper bound for the radii (Fmin: m'ma:: Smin. Smax) that define the respective annuli in practice. Given point x, we found the following procedure to be useful in practice: we set 8max. i.e. the maximum of the outer radius, to the distance to the kth nearest neighbour of point, and mmins i.e the minimum inner radius, to the smallest non-zero distance to a neighbour of x. Finally, we set the minimum outer radius Smin and the maximum inner radius Tmax to the distance to the _ [h nearest neighbour. While we find k = 50 to yield sufficient results, spaces with high intrinsic dimension may require larger values. The advantage of using such a parameter selection procedure is that it works in a data-driven manner, accounting for differences in density. Since our approach is inherently local, we need to find a balance between sample sizes that are sufficiently large to contain topological information, while the same time being sufficiently small retain local perspective. We found the given range to be an appropriate choice in practice. As for the number of steps, we discretise the parameter range using 20 steps by default. Higher numbers are advisable when there are large
265
266
267
269
271
273
274
275
278
discrepancies between the radii, for instance when 5 Smax > T maxx-
277
278
5.2
PERSISTENT INTRINSIC DIMENSION IS EXPRESSIVE
We first analyse the behaviour of persistent intrinsic di- mension (PID) on samples from a space obtained by con- catenating S (a circle) and S (a sphere) at a gluing point. Table | shows a comparison of PID with state-of-the art dimensionality estimators [ We find that PID outperforms all estimators in terms of mean and standard deviation for the 2D points, thus correctly indicating that the majority of all points admit non-singular 2D neighbourhoods. For the 1D points, the mean of the dimensionality estimate of PID is still close to the ground truth, while its standard de- viation and maximum correctly capture the fact that some ID points are situated closer to the gluing point. This be- haviour is in line with our philosophy of considering di- mensionality as inherently local phenomenon. In case such behaviour is not desirable for a specific data set, Eu- clidicity calculations support any dimensionality estimator; since such estimators do not come with strong guarantees such as Theorem 2 their choice must be ultimately driven by the data set at hand. See Appendix A.6 for a more detailed analysis of these estimates.
280
METHOD MIN
MAX
282
1pca
1.00 1.42#0.78
3.00
283
ID twoNN
0.83 1.00+:0.0
1.20
284
DANCo
1.00 1.00++0.01
1.16
285
PID
1.00 1.12::0.24
1.97
286
1pca
2.00 0.88+-032
3.00
287
tWoNN
1.01 1.90+ 2.53
288
2D
DANCo
1.00 0.10 3.00
289
PID
1.52 1.95 2.08
291
Table 1: Dimensionality estimates for the concatenation of 5 and S
293
294
295
296
Stability. In practice, the sample density may not be sufficiently high for Theorem 2 to apply. This means that there may appear artefact homological features in dimensions higher than the intrinsic dimension of a given space. We thus only consider features that exceed certain persistence thresh- old in comparison to the persistence of features of lower dimension: for any data point æ and the respective intrinsic annulus (z), we eliminate all topological features whose lifetimes are smaller
298
299
300
301
302
than the maximum lifetime of features in one dimension below. This results in markedly stable estimates of intrinsic dimension, which are less prone to overestimations.
303
304
5.3
EUCLIDICITY CAPTURES SINGULARITIES
305
shows that Euclidicity is capable of detecting the singularity of the 'pinched torus.' Of par- ticular relevance is the fact that Fuclidicity also highlights that points in the vicinity of the singular point are not fully regular. This is an important property for practical applications since it implies that Euclidicity can detect such isolated singularities even in the presence of sampling errors.
Fig.
306
307
308
309
Besides the pinched torus, another prototypical example of singular spaces is given by S" V S"" the wedge of two n-dimennionnl spheres. Intuitively, S S is obtained by two n-dimensional spheres that are glued together at certain point. Denoting the gluing point by Zo, for a suitable triangulation of X = 5" v S" this space is naturally stratified by X {zo). Next, we apply TOAST to samples
310
311
312
'Method names taken from the sci ki d- ce-di toolkit. See Appendix A.6 for more details.
7

---

Under review as a conference paper at ICLR 2023
Dimension
4
3
2
H
0.08
0.1
0.12
0.04
0.08
1
5
6
(a)
(b)
(c)
Figure 4: (a):
Euclidicity scores of wedged spheres for different dimensions. High values indicate singular points/neighbouroodd.. The Euclidicity of the singular point always constitutes clear
positive outlier. In 2D, Euclidicity (b) results in clearly-delineated singular region when compared
single-parameter score (C)
313
of such wedged spheres of dimensions 2.3 and 4, calculating their respective Euclidicity scores. Since larger intrinsic dimensions require higher sample sizes to maintain the same density, start with a sample size of 20000 in dimension 2 and increase it consecutively by a factor of 10. We then calculate Fuclidicity of 50 random samples in the respective data set, and additionally for the
315
316
317
singular point zo- Fig. 4a shows the results of our experiments. We observe that the singular point possesses significantly higher Euclidicity score than the random samples. Moreover, we find that Euclidicity scores of non-singular points exhibit high degree of variance across the data, which caused by the fact that the sampled data does not perfectly fit the underlying space the points are being sampled from. This strengthens our main argument: assessing whether specific point is Euclidean does not require binary decision but a continuous measure such as Euclidicity.
318
319
320
322
325
Stability. As predicted by Theorem I Euclidicity estimates are stable in practice. We first note that Euclidicity is robust towards sampling: repeating the calculations for the 'pinched torus' over differ- ent batches results in highly similar distributions that are not distinguishable according to Tukey's s range test (Tukey] 1949) at the a 0.05 confidence level. Moreover, choosing larger locality scales still enables us to detect singularities at higher computational costs and incorporating larger parts of the point cloud. Please refer to Appendix A.5 for a more detailed discussion of this aspect.
324
325
326
327
328
329
5.4
EUCLIDICITY MORE EXPRESSIVE THAN
APPROACHES
Our Euclidicity measure leads significantly more stable results than comparable one- me--arrmettr approach for geometry-based anomaly detection (Stolz et al.] 2020): Fig. 4b and Fig. 4c compare multi-parameter Euclidicity with one-parameter Euclidicity for 20000 samples of S S S The
331
332
333
constant-scale approach results in many points with high anomaly scores that in fact do admit Eu- clidean neighbourhood. We quantify this by analysing the empirical distributions of anomaly scores of the two data spaces (see Appendix A.8 for more details), with the one-parameter method ex- hibiting a much larger variance than our multi-paramete Euclidicity measure. The multi parammprrreeter distribution shows that the mass is concentrated around the mean, but also contains outliers with high Euclidicity scores. These outliers correspond to points the data space whose distance to the singular point is small. We thus conclude that Euclidicity scores increase once one approaches the parameter methods with fixed locality scale. In fact, the main advantage of Euclidicity is that it implicitly incorporates information about the scale which a given data point admits a Fuclidean neighbourhood.
334
335
396
337
338
340
singularity- which is not the case for single-parameter
342
343
5.5
EUCLIDICITY CAPTURES GEOMETRIC COMPLEXITY OF HIGH- DICENSINENSINAL... SPACES
3/4
To test TOAST in an unsupervised setting, we calculate Euclidicity scores for the MNIST and FASHIONMNIST data sets, selecting mini-batches of 1000 samples from subsample of 10000 random images of these data sets. Following Pope et al. (202T), we assume an intrinsic dimension of 10; moreover, we use k 50 neighbours for local scale estima- tion. To ensure that our results are representative, we repeat all calculations for five dif- ferent subsamples. Euclidicity scores range from 5.3] for MNIST, and 11.3,5.0 for FASHIONNNIST. The scores of the two datasets appear to be following different distribu- tions (see Appendix A.7 for visualisation and more detailed depiction of the distributions).
345
346
348
350
8

---

Under review as a conference paper at ICLR 2023
Fig. 5 shows selection of 9 images, corresponding to the lowest, median, and highest Euclidicity scores, respectively. We observe that high Euclidicity scores correspond to images with high degree of non-linearity, whereas low Fuclidicity scores correspond to images that exhibit less complex structures: for MNIST, these are digits of 'I'' Interestingly, we observe the same phenomenon for FASHION- MNIST, where images with low Euclidicity ('pants") possess less geometric complexity in contrast to images with high Euclidicity. Since low Euclidicity can also be seen as an indicator of how close a neighbourhood is to being locally linear, this finding hints at the existence of simple substructures in such data sets. Euclidicity could thus be used as an unsupervised measure of geometric complexity.
3
353
355
(a) MNIST
356
357
358
359
360
(b) MASHI
362
Figure 5: Left to right: low, median, high Euclidicity.
5.6
EUCLIDICITY CAPTURES LOWER- DIMENSIONAL STRUCTURES IN CYTOMETRY DATA
385
To highlight the utility of Euclidicity in unsupervised representation learn- ing, we calculate it ming data set (Zunder et al.) (015). The data set depicts a progression of so- called fibroblasts diverging, and splitting into two different lineages. Fig. 6 shows an embedding obtained via PHATE (Moon et al. 2019) and the Eu- clidicity scores of the original data. We find that high Euclidicity scores correspond to points that exhibit a lower density in the embedding, being in fact situated in lower-dimensional subspaces. Since lower-dimensional points in space can be considered singular in the sense of stratified spaces, this is further evidence for Euclidicity to be a useful tool for detecting non- manifold regions in data. Please refer to Appendix A.9 for more details.
366
induced pluripotent stem cell (iPSC) reprogram-
387
388
369
370
372
374
Figure 6: An em- bedding of the iPSC data with colours based on Euclidicity highlights dense -in-sin regions.
6 DISCUSSION
376
We presented TOAST, novel framework for locally estimating the intrinsic dimension (via PID, the persistent intrinsic dimension) and the 'manifold- ness' (via Euclidicity, multi-scale measure of the deviation from Euclidean space) of point clouds. Our method is based on a novel formulation of per- sistent local homology as a multi-parameter approach, and we provide theo- retical guarantees for it in a dense sample setting. Our experiments showed significant improvements of stability compared to geometry- based anomaly detection methods with fixed locality scales, and we found that Euclidicity can detect singular regions in data sets with known singularities. Using high-diee benchmark data sets, we also observed that Euclidicity can serve as an unsuper- vised measure of geometric complexity
378
380
381
382
383
384
385
386
387
For future work, we envision two relevant research directions. First and foremost will be the inclu- sion of Euclidicity into machine learning models to make them singularity-awart ex experiments in Section 5.3] we believe that Euclidicity could be particularly useful in unsupervised scenarios, provide additional weight in classification settings (to ensure that singular examples are being given lower confidence scores). Moreover, Euclidicity could be used in the detection of adversarial samples-al task for which knowledge about the underlying topology of space is known to be crucial (Jang et al. 2020). As a second direction, we want to further improve the properties of Fuclidicity itself. To this end, we plan investigate if incorporating custom distance measures for parameter persistence modules, i.c. different metrics for Eq. 4 lead to improved results in terms of stability, expressivity, or computational efficiency. Moreover, we hypothesise that replacing the Vietoris-Rip
In light of our
389
391
382
383
394
385
three- three-parameter
396
387
filtration by other constructions (de Silva & Carlsson 2004) could prove benefi- cial in reducing the number of samples for calculating Euclidicity. Along these lines, we also plan
396
to derive theoretical results that relate specific filtrations and the expressivity of the corresponding Fuclidicity measure. Another direction for future research concerns the approximation of a mani-
400
fold from inherently singular data, i.e. finding the best manifold approximation to a given data set with singularities. This way, singularities could be resolved during the training phase of models,
402
provided appropriate loss function exists. Euclidicity may thus serve metric for assessing
404
data sets, paving the way towards more trustworthy and faithful embeddings.

---

Under review as a conference paper at ICLR 2023
REPRODUCIBILITY STATEMENT
406
We provide our code as part of the supplementary materials. All dependencies are listed in the re- spective jecroject toml file, and the README discusses how to install our package and run our experiments. Our implementation leverages multiple CPUs if available but has specific hardware requirements otherwise.
407
409
REFERENCES
Hirokazu Anai, Frédéric Chazal, Mare Glisse, Yuichi Ike, Hiroya Inakoshi, Raphaël Tinarrage, and Yuhei Umeda. DTM-based filtrations. In N. A. Baas, G. E. Carlsson, G. Quick, M. Szymik, and M. Thaule (eds.). Topological Data Analysis, pp. 33-66. Springer, 2020. doi: 10.1007/
412
414
415
Ulrich Bauer. Ripser: efficient computation of Vietoris Rips persistence barcodes. Journal of Applied and Computational Topology, 5(3):391-423, 2021. doi: 00007//41468-021-000077
416
417
Paul Bendich. Analyzing stratified spaces using persistent versions of intersection and local homol- ogy. PhD thesis, Duke University, 2008.
418
Paul Bendich, David Stennn-Seeine, Herbert Edelsbrunner, John Harer, and Dmitriy Morozov. In- ferring local homology from sampled stratified spaces. In IEEE Symposium on Foundations of Computer Science (FOCS), pp. 536-546, 2007. doi: 10.1109/FOCS,2007.55
420
422
Tolga Birdal, Aaron Lou, Leonidas J. Guibas, and Umut Simsekli. Intrinsic dimension, persistent homology and generalization in neural networks. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and J. Wortman Vaughan (eds.), Advances in Neural Information Processing Systems, volume 34, pp. 6776-6789, 2021.
424
425
426
Bradley C.A. Brown, Anthony L. Caterini, Brendan Leigh Ross, Jesse C. Cresswell, and Gabriel Loaiza-Ganem. The union of manifolds hypothesis and its implications for deep generative mod- elling. arXiv:2207.0286. 2022.
428
Francesco Camastra and Antonino Staiano. Intrinsic dimension estimation: Advances and open problems. Information Sciences, 328:26-41 2016. doi: 10.1016//.ins.201111. 2015.08.29...
430
Gunnar Carlsson. Topology and data. Bulletin of the American Mathematical Society, 46(2):255- 308, 2009.
432
433
Frédéric Chazal, Vin De Silva, and Steve Oudot. Persistence stability for geometric complexes. Geometria Dedicata, 173(1):193-114 2014. doi: 10.10077:1071110013999377
434
435
David Sthen-Steiner, Herbert Edelsbrunner, and John Harer. Stability of persistence diagrams. Discrete & Computational Geometry, 37(1):103-120, 2007. doi: 10. 10.10077:004444006-122222 1276-5.
437
Vin de Silva and Gunnar Carlsson. Topological estimation using witness complexes. In M. Gross, H. Pfister, M. Alexa, and S. Rusinkiewicz (eds.), Symposium on Point-Based Graphics. The Eu- rographics Association, 2004. doi: 10233225PBG/SPBGG4155... 166.
439
Tamal K. Dey, Fengtao Fan, and Yusu Wang. Dimension detection with local homology. In Cana- dian Conference on Computational Geometry (CCCG), 2014.
441
Herbert Edelsbrunner and John Harer. Computational topology: An introduction. American Math- ematical Society, Providence, RI, USA, 2010.
443
Brittany Terese Fasy and Bei Wang. Exploring persistent local homology in topological data analy- sis. In IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), pp. 6430 6434, 2016.
445
447
Felix Hensel, Michael Moor, and Bastian Rieck. A survey of topological machine learning methods. Frontiers in Artificial Intelligence, 2021. doi: 2033899frai.2221..0 108.
10

---

Under review as a conference paper at ICLR 2023
Alexander Jakubowski, Milica Gašić, and Mareus Zibrowius. Topology of word embeddings: Sin- gularities reflect polysemy. In Proceedings of the Ninth Joint Conference on Lexical and Compu- national Semantics, pp. 103-113. Association for Computational Linguisties, 2020.
450
452
Uyeong Jang, Susmit Jha, and Somesh Jha. On the need for topology-aware generative models for manifold-based defenses. In International Conference on Learning Representations, 2020. URL https://openrent
453
454
nnt. fnet/fooune
CEYwS
455
Diederik P. Kingma and Max Welling. An introduction to variational autoencoders, Foundations and Trends@ in Machine Learning, 12(4):307-392, 2019. doi: 10.1561/2200000056
Leland McInnes, John Healy, and James Melville. UMAP: Uniform manifold approximation and projection for dimension reduction.
458
2018.
459
Kevin R. Moon, David van Dijk, Zheng Wang, Scott Gigante, Daniel B. Burkhardt, William S. Chen, Kristina Yim, Antonia van den Elzen, Matthew J. Hirm, Ronald R. Coifman, Natalia B. Ivanova, Guy Wolf, and Smita Krishnaswamy, Visualizing structure and transitions in high- high-dimensional biological data. Nature Biotechnology. 37(12): 1482-1492, 2019.
460
461
462
463
Michael Moor, Max Horn, Bastian Rieck, and Karsten Borgwardt. Topological autoencoders. In H. Daumé III and A. Singh (eds.), Proceedings of the 37th International Conference Machine Learning (ICML), number 119 in Proceedings of Machine Learning Research, pp. 7045-7054. PMLR, 2020.
465
Phillip Pope, Chen Zhu, Ahmed Abdelkader, Micah Goldblum, and Tom Goldstein. The intrin- sic dimension of images and its impact on learning. In International Conference on Learning Representations, 2021.
488
469
470
Bastian Rieck and Heike Leitte. Persistent homology for the evaluation of dimensionality reduction schemes. Computer Graphics Forum, 34(3):431 June 2015. doi: 10. 1/111/cff.12655.
Bastian Rieck, Markus Banagl, Filip Sadlo, and Heike Leitte. Persistent intersection homology for the analysis of discrete data, In H. Carr, Fujishiro, Sadlo, and S. Takahashi (eds.), Topological Methods in Data Analysis and Visualization V. pp. 37-51. Springer, Cham, Switzerland, 2020. doi: 10. 10.1007/978-3-03860 0-1099978---030-4336---333
473
475
478
Luis Scoccola and Jose A. Perea. Fiberwise dimensionality reduction of topologically complex data with vector bundles. arXiv:2206.0651/ 2022.
477
478
Donald R. Sheehy. Linear-size approximations to the vietoris-rips filtration. Discrete Computa- lional Geometry, 49(4):778-796, 2013. doi: 10.1007/500454--11-9911---
Bernadette Stolz, Jared Tanner, Heather A. Harrington, and Vidit Nanda. Geometric anomaly
481
detection in data. Proceedings of the National Academy of Sciences, 117633):1666411969, 2020. doi: 00.1073/pnas.200174111
482
483
Guillaume Tauzin, Umberto Lupo, Lewis Tunstall, Julian Burella Pérez, Matteo Caorsi, Anibal Medina-Mardonnes Alberto Dassatti, and Kathryn Hess. giotto-tda: A topological data anal- ysis toolkit for machine learning and data exploration. arXiv:2004.0255// 2020.
485
486
The GUDHI Project. GUDHI User and Reference Manual. GUDHI Editorial Board, 2015. URL http://gudhi: wwarii.ggoorg..o inria ..r fr/
Et/doc/latest.
John W. Tukey. Comparing individual means in the analysis of variance. Biometrics, 5(2):99-114, 1949.
489
490
L Laurens van der Maaten and Geoffrey Hinton. Visualizing data using t-SNE. Journal of Machine Learning Research, (066):2799-600 2008
491
492
Eli R. Zunder, Ernesto Lujan, Yury Goltsev, Marius Wernig, and Garry Nolan. A continuous molecular roadmap to iPSC reprogramming through progression analysis of single-cell mass cy- tometry. Cell Stem Cell, 16(3):323-337, 2015.
494

---

Under review as a conference paper at ICLR 2023
A
APPENDIX
496
A.1
NOTATION
Symbol
Meaning
c
local annulus scale parameter
R
real numbers
Hi Hi
ith (ordinary) homology functor (with Z/2Z coefficients)
ith reduced homology functor (with Z.227 coefficients)
inf
infimum
487
sup
supremum
l
uniform (infinity) norm
n
intrinsic dimension of the space under consideration
N
ambient dimension of the space under consideration
lim
(categorical) colimit
S
k-dimensional sphere open cone of topological space X
e x x (0, (1)
498
A.2
PROOFS OF THE MAIN STATEMENTS IN THE PAPER
We restate the theorems from the main paper for the convenience of readers, along with their proofs, which were removed for space reasons. We first prove the stability theorem, first stated on p.5iin the main text, which shows that our method enjoys stability properties with respect to radius changes of the intrinsic annuli.
500
502
Theorem 1. Given a finite metric space X and X, let (z(x) and (x) denote two intrinsic annuli with Ir ---1 r'l S eL and Is 8'1 S 62. Furthermore, let D,D' D' denote the persistence diagrams corresponding to PH((Be(rr:))) and PH, (x); V), respectively. Then
503
504
505
506
(D,(DD))) S max(er,e2h
507
Proof. The Hausdorff distance of two non-empty subsets A, X da = inf >
0 A C B,, c Ac). where A, = Usead E X; d(z, a) < e} denotes the e-thickening of A in X. Set maxfer, By assumption, (z)z) C BC and (z(x) C (z) i.c.
510
S e. Using the geometric stability theorem of persistence diagrams (Caazal ct al. 2014), we have dD(D, D') s dz(B,(z), B3 (z)), which proves the claim.
du (x) Bx
511
512
Next, we prove that our persistent intrinsic dimension (PID) measure is capable of capturing the dimension of manifolds correctly, provided sufficiently many samples are present. This theorem was first stated on 5
513
514
Theorem 2. Let M C R be n-dimensional compact smooth manifold and lei X.
516
(ZI....,,2 ,s) a collection of uniform samples from M. For a sufficiently large S, there exist constants 62 0 such that (e) for all e1 E2 and any point z E X. Moreover, can be chosen arbitrarily small by increasing
518
519
Proof. Let x X be an arbitrary point. Since M is a manifold, x admits a Euclidean neighbour- hood U. Since M is smooth, we can assume U to be arbitrarily close to being flat by shrinking it. Thus, we can find e2
520
521
with (x)x) C for all r, s < é2 such that H, (V(BB t)) = for all and all f. Hence, (B)( = 0 for all i > and therefore ig (E2) < By contrast, for sufficiently large, and r, as before, there exists a parameter such that (x), t) is homotopy- equivalent to (n 1)-sphere, and so (z) admits generator, i.e. it is non-trivial. Consequently, PH,-1 (B, # O, and (x2) = n. By further increasing S, we can ensure that the statement still holds when decrease e2, which proves the remaining claims.
i
523
525
12

---

Under review as a conference paper at ICLR 2023
A.3
ADDITIONAL PROOFS
528
To make this paper self-contained, we provide a brief proof of Eq. ( By the excision axiom for
528
homology, we have
H x x) = (S) \ (.)
(5)
530
Since St))) is contractible, the long exact reduced homology sequence of the pair (St()),,((z)) (x)
records exactness of
= (St(z)) + (St(r), St())) \2) - H)-1(St(2)) \ () H(,1(St(z))) =
for all and therefore H, (St(z)), \ æ) = (St(()((x)) \ x). Eq. i now follows from the
532
533
observation that St(z) \ x deformation retracts to Lk(r).
534
A.4
PSEUDOCODE
We provide brief pseudocode implementations of the algorithms discussed in Section the fol- lowing, we use # (X) to denote the number of i-dimensional persistent barcodes of X (w.rt. the Vietoris-Rips filtration, but any other choice of filtration affords the same description), Algo- rithm camammmexpiinn the caleulation of persistent intrinsic dimension (see Section 4.1 in the main paper for details). For the subsequent algorithms, we assume that the estimated dimension of the intrinsic dimension of the data is n. We impose additional requirements on this number; it can, fact, be obtained by any choice of intrinsic dimension estimation method. As a short-hand notation, for sample of {y IR" < dlx,, 8), denote by P. = PH (VEB (z). the respective fibred persistent local homology barcode (calculated 543
535
537
539
540
541
P: PH 7H (xr), )) w.r.t.
w.r.t. the same sample). Algorithm 2 then shows how to calculate the Euclidicity values, following
545 Eq. 3 and one of its potential implementations, given in Eq. (4).
Algorithm An algorithm for calculating the persistent intrinsic dimension (PID)
Require: x E X, Smax. L.
for E T do
Iterate over the parameter grid
2: (.((s) (
3: for <
4: for i = -...,.., - do
5:
Calculate # Bar, (x)) if # Bar, (x)) then
6:
7:
(s()) - +11
8: end if
9:
end for
10: end for
11: return (s)
end for
Algorithm 2 An algorithm for calculating the Euclidicity values 65k
Require: x E X, Smax, L, n. {pI...., ..m).
1: for j = 1,... do
2: for
1...., do 3: for E r do for E.r do
4:
5:
Calculate da (n) F.8 :Pk return (n F.8 (i
D Calculate bottleneck distance
6:
7:
end for end for
8:
Calculate D(p,, Pk) 10: return D(p Pk)
9:
Evaluate Eq. (4)
11:
end for
12:
end for
13

---

Under review as a conference paper at ICLR 2023
0.1
0.15
0.1
0.15
0.1 0.15 0.2
(a)
0.55
(b) Smax 0.65
(c) Smax 0.75
Figure 8: Modifying the outer radius mmax still enables us to detect the singularity of the 'pinched torus.' Larger radii, however, progressively increase the field of influence of our method, thus start- ing to assign high Euclidicity values to larger regions of the point cloud.
0.55
max 0.65
mmax = 0.75
max
200
Count
150
100
50
0.05 0.1 0.15 0.20 0.05 0.1 0.15 0.20 0.05 0.1 0.15 0.2
Euclidicity
Euclidicity
Euclidicity
Figure 9: Histograms of the Euclidicity values for the point clouds shown in Fig. Larger radii result in the distribution accumulating more probability mass at higher Euclidicity values, making the singularity detection procedure less local (but still succeeding in detecting the singularity and its environs).
548
A.5
STABILITY OF EUCLIDICITY ESTIMATES
547
Fig. 7 shows that Euclidicity robust under sampling; repeating the calculations for smaller batches of the 'pinched torus' data (500 points each) still lets us detect the singularity and its neighbours reliably. This robustness is an im- portant property in practice where we are dealing with samples from an unknown data set whose shape properties we want to capture. Euclidic- ity enables us to perform these calculations a robust manner. Following the brief discussion in Section 5.I we show the results of varying 8max, the outer radius of the local annulus, for the 'pinched torus' data set. Fig. g depicts point clouds of 1000 samples; we observe that the sin- gularity. i.c. the 'pinch point,' is always detected. For larger radii, however, this detection becomes progressively more global, incorporating larger parts of the point cloud. Fig. Dddepics the corre- sponding histograms; we observe the same shift in probability mass towards the tail end of the dis- tribution. For extremely large annuli, we estimate that we lose a clear distinction between singular values and non-singular values. Our data-driven parameter selection procedure is thus be preferred in practice since it incorporates data density.
548
549
0.2
Euclidicity
851
0.15
553
0.1
555
0.05
557
1 2
4 5
Sample
559
560
Figure 7: Boxplots of the Euclidicity values of different random samples of the 'pinched torus' data set. While each sample invariably exhibits some degree of geometric variation, we are able reliably identify the singularity and its neigh- bourhood.
562
563
564
586
588
14

---

Under review as a conference paper at ICLR 2023
PVD for k=200
TvoNN for K-200
22
15
0.5
2.0
16
-05
99
1.6
1.4
-30
1.0
12
5.0
12
-03
1
-0.5
1.0
(a) PID
(b) twoNN
Figure 10: Even for large values of k, PID still does not overestimate the local dimensionality of the data, exhibiting a clear distinction between the circle and the sphere, respectively.
A.6 COMPARISON OF PID WITH OTHER DIMENSION ESTIMATES
571 In order to assess the quality of PID, we decided to test its performance on space that is both singu- lar and has non-constant dimension. The data space we chose consists of 2000 samples of S V Sa,
572
i.e. a 1-sphere glued together with 2-sphere at a certain concatenation point. We then applied the
574
PID procedure for a maximum locality scale that was given by the l nearest neighbour distances, for
k (25, 50, 75, 100, 125, 150, 175, 200]. We assigned to each point the average of the PID scores 576 at the respective scales that are less than or equal to the nearest neighbour bound. Subsequently, compared the results with other local dimension estimates for the respective number of neigh- bours The methods that were chosen for comparison include 1pca, t tWONN, KNN, and DANCo; we used the respective implementation from the scikit disitt-dimeiioiioo on Python package
578
579
580
Fig. 10a 10a|shos shows the PID results for a maximum locality scale of 200 neighbours, with colours show- ing the estimated dimension values for each point. Overall, the correct intrinsic dimension is de- tected for most of the points. However, points that lic close to the singular point show a PID value between 1 and 2. Similarly what we already discussed for Euclidicity, PID should therefore also be interpreted as a measure that incorporates the intrinsic dimension of a point on multiple scales of locality. For real-world data, the dimension will generally change when changing the locality scale. However, since there is no canonical choice of scale, we believe that any such scale provides valuable information about the intrinsic dimension that is worth being measured. We therefore argue that multi-scale approach like ours is appropriate in practice, especially in regime that is agnostic with respect to the underlying intrinsic dimension. By contrast, Fig. [0b] shows the corresponding dimension estimates for twoNN, where we observe less stable and reliable results across the dataset.
582
583
584
5e5
586
587
589
591
Fig. Ia shows boxplots of the distributions of the dimension estimates, for all points that lie on the ID-sphere. We see that for PID, the mass is concentrated outliers present, these correspond to points that are close to the singularity, as it was expected. We note that other methods like KNN and 1pca might highly overestimate the dimension, and that the interquartile range is significantly higher for twoNN and KNN. Fig. [Tb]shows the same distributions for the points that lie on the 2D-sphere. Again, 1paa highly overestimates the dimension since the median lies at value of 3. Again. the interquartile range of PID is the tightest, and the estimates are closest to the ground truth. Moreover, the lower-value outliers again correspond points that are close to the singular gluing point.
value of 1. Although there
593
594
585
596
587
598
589
600
Fig. 12a and Fig. 12b show average dimension estimate scores of all investigated methods for vary- ing values of k, both for points on the 1-sphere and the 2-sphere. We note that on average, only tNNNN and DANCo lead to results which are comparable with the reliability of our method. How- ever, as we already saw in Fig. Taaland and Fig. 1Tb] the variance of the scores of our method is signifi- cantly lower, leading to more reliable outputs for each of the points.
602
604
https://sccii diweiitttdmmeiiiiioo www.tiiiedrreddeedddsococoee oo/e// 1atest/
15

---

Under review as a conference paper at ICLR 2023
Distributions dimension estimates of points
Distributions of dimension estimates of 2D points
300
Dimension estimates
Oimension extimates
2.50
20
2.00
175
1.5
1.50
125
10
100
bwoNN
DANCo
bwoNN
KNN
DANCo
PID
(a) 1-sphere dimension estimates
(b) 2-sphere dimension estimates
Figure 11: Estimates of the local intrinsic dimension for points that are close to the ID-sphere, i.e. circle, or the 2D-sphere, respectively.
Dimension estimates of 1D
Dimension estimates of 2D points
PID
2.75
Average dimension estimate
Average dimerssion estimate
twoNN
2.50
KNN
PID
DANCo
2.55
1.3
bwoNNN
12
DANCo
09
125
25
100
125
150
175
200
25
50
75
125 Number neighbours
100
150
175
200
Number neighbours
(b)
Figure 12: Dimension estimates of the ID-sphere and the 2D-sphere for different methods, plotted as function of the number of neighours k.
16

---

Under review as a conference paper at ICLR 2023
3
4
0
5
/
5
5
4
5
6
7
6
6
6
B
5
D
3
4
6
3
5
6
5
2
6
5
8
8
8
5
6
4
7
2
0
6
4
P
4
O
4
4
2
8
6
5
5
4
0
O
6
4
2
4
4
2
4
9
5
0
8
(a)
(b)
(c)
Figure 13: From left to right: more examples of low Euclidicity values, median Eaclidicity values, and high Euclidicity values for the MNIST data
605
A.7
EUCLIDICITY OF MNIST AND FASHIONMNIST
Fig. 13 and Fig. 14 show the Euclidicity results for the 4 additional runs on both the MNIST and 606
FASHIONMNIST data sets. Again, depicted the images with lowest (left), medium (middle), and highest (right) Euclidicity scores for the two datasets. Moving from left to right, the images exhibit increases in the complexity of the local geometry, giving evidence for the reproducibility of the observation we remarked in Section 5.5
608
609
610
Finally, Fig. 15 shows, the empirical distributions of the calculated Fuclidicity scores differ signif- icantly for the MNIST and FASHIONNISTT data sets, with the distribution for MNIST exhibiting bimodal behaviour, whereas the FASHIONMNIST Euclidicity value distribution is unimodal. We hypothesise that this corresponds to regions of simple complexity- and locally linear structures-in the MNIST data set, which are absent in the FASHIONMNIST data set.
612
613
614
615
616
A.8
ONE-PARAMETTR VERSUS MULTI-PARAE PARAMETER EUCLIDICITY FOR WEDGED SPHERES
Fig. shoss the empirical distributions of Euclidicity scores for fixed locality parameters (left) and for our proposed multi-scale locality approach (right). We see that the variance is significantly lower in the multi-scale regime, indicating more stable and robust results. Moreover, the ratio of maximum and mean is higher in the multi-parameter setting, where high Euclidicity scores correspond to data points that lie close the singularity, resulting more reliable outcomes.
618
620
17

---

Under review as a conference paper at ICLR 2023
(a)
(b)
(c)
Figure 14: From left right: more examples low Euclidicity values, median Euclidicity values, and high Euclidicity values for the FASHIONMIIST data set.
Empincal distribution
euclidicity scores images
Empincal euclidiiiyy scores FashionMNIST images
320
15
4.0
45
5.0
Eudidiity
Eucl dicty
(a) MNIST
(b) FASHIONMNIST
Figure 15: Both MNIST and FASHION exhibit markedly different distributions in terms of Euclidicity: MNIST Euclidicity values are bimodal, whereas FASHIONMNIST Euclidicity values are unimodal.
18

---

Under review as a conference paper at ICLR 2023
One-parameter wedged spheres
Mull-parameter wedged
120
120
35
4.
4.5
5.0
5.5
6.0
0.02
0.03
0.04
0.05
0.6
0.0
0d8
Fuciidiity
fuclidedy
(a)
(b)
Figure 16: A comparison of Euclidicity values of one-parameter approach (left) and our multi- parameter approach (right) demonstrates that multiple scales are necessary to adequately capture singularities.
19

---

Under review as a conference paper at ICLR 2023
Euclidicity
Low
High
8
10
12
14
16
18
20
22
24
Intrinsic dimension
Figure 17: comparison of intrinsic dimension estimates computed for points in the iPSC dataset that admit high (left) and low (right) Euclidicity scores. The twONN dimensionality estimator was used for this example.
(a) 10000 points
(b) 5000 points
(c) 1000 points
Figure 18: Euclidicity remains stable under subsampling the iPSC data set. Minor variations in the point cloud shape are due the PHATE embedding algorithm; Euclidicity calculated the raw data.
822
A.9 EUCLIDICITY OF IPSC DATA
The iPSC data set Zunder al. (2015) consists of 33 variables and around 220k samples. It is known to contain branching structures that can best be extracted using PHATE (Moon et al. (2019). non-linear dimensionality reduction algorithm. We only employ this algorithm for visnalisation purposes; all Euclidicity calculations are performed on the original data. Using twNNN for dimen- sionality estimation, we obtained mean intrinsic dimension of 16; as outlined above, other dimen- sionality estimators may be employed as well-we consider this analysis to be a proof of concept first and foremost. We selected parameters as described in Section 5.5 and computed Euclidicity for 10000 samples.
624
625
628
627
628
629
631
We observe that figh-Eiclidictty scores correspond to points that exhibit a lower density in the PHATE embedding and according to the twoNN estimates we see that such points in fact of lower intrinsic dimension; see Fig. 17 for details. More specifically, we calculated the intrinsic dimension for the subsample, observing that the interquartile range for the 1000 points with highest Euclidicity around 12-14, whereas the interquartile range the 1000 lowest Euclidicity points ranges between around 13-16. Again, used the twoNN algorithm for intrinsic dimensionality estimates (using = 50 nearest neighbours). Since lower-dimensional points space can be of stratified spaces, as a useful tool for the detection of non-manifold regions in the data. Finally, we remark that our analyses remain valid under subsampling. Fig. 18 depicts subsamples of different sizes for which we calculated Euclidicity (on the raw data, respectively, using PHATE to obtain embeddings). Euclidicity distributions remain stable and the same phenomena are highlighted for each subsample.
633
635
637
regarded as being singular in the
further evidence for Fuclidicity
639
610
642
However, notice that low-density regions in the PHATE visualisation need not necessarily correspond to low-density regions in the original dataset.
20


Reviews:
[{"review_id": "qtHYDc4W2V", "reviewer": "Reviewer_8kd2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper proposes two measures that encapsulate the topological features of data: Persistent Intrinsic Dimension (PID) and Euclidicity. The authors claim that manifold learning with a fixed intrinsic dimension can be a restrictive assumption in general and it is worth thinking of allowing this dimension to vary for different points on the manifold. The seeming advantages are argued to be the ability to identify singularities (i.e. points that violate the manifold assumption) as well as providing a notion of local geometric complexity in the data. \n\nThe authors spend considerable effort in theoretically elaborating their approach and providing theorems to show that their persistent homology-based method is stable to choice of parameters and sampling issues in the data. Synthetic demonstrations are made on the pinched torus, the wedges spheres as well as image datasets like MNIST and FMNIST. \n", "summary_of_the_review": "Overall, I think this paper proposes an interesting contribution in topological data analysis. However, I am leaning negative considering two factors (1.) The overall confusing structure of the paper and inaccessibility of the core TDA components (2.) Very little emphasis on actual applications with significant impact.   ", "strength_and_weaknesses": "Strengths \n\n- To the best of my non-expert understanding the formulation appears to be novel. I also did find the arguments highlighting the scenarios of “singularities” in the data to be interesting \n- Most experiments do demonstrate the characteristics of the claimed contributions, i.e. the measures PID and Euclidicity provide an interesting way of measuring the complexity of data, with singularities showing up nicely (especially in Figure 1 and 5). \n- The appendix demonstrates some interesting experiments, especially Figures 8 and 10, where a comparison is shown between some well known dimensionality estimators and the proposed approach. \n\nWeaknesses and Questions\n\n- Despite the focused approach to handling singularities in data, I do feel the overall applicability of this method in practice is not well explored. Most experiments are very synthetic and tailor-made for the setting of this paper (eg. pinched torus, wedged spheres etc.) \n- The structure of the paper can be made much better. I feel a lot of the important practical results are left in the appendix. For example sections, A5, A6, and A7 should (with appropriate editing) belong to the main paper and must be argued as a core part of the contribution. \n- Unfortunately, I did not find the material to be satisfactorily self-contained, and I think that it would go a long way to make sections 2 and 4 more accessible to a general representation learning audience.   \n- (suggestion) Consider improving the quality of visualizations, in terms of choosing the view in 3D (eg Figure 10, to see the point of contact between the circle and sphere).  \n- What is the limit on line 111 ?\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "Scasyhnbtcw", "reviewer": "Reviewer_vmhb", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The authors propose a technique based on topological data analysis to: 1. estimate pointwise the intrinsic dimensionality of the data manifold in the local neighbourhood, and 2. assess if the local neighbourhood resembles a Euclidean space with the same dimensionality. In this way, singularities on the data manifold can be found. The method has a multi-scale property as it takes into account neighbourhoods of different size. In the experiments it is demonstrated the effectiveness of the approach.", "summary_of_the_review": "Questions:\n1. I think that a brief summary of the approach is missing, while in several places (e.g. \"Our contributions\") you summarize from a high level point of view the steps of the approach. Perhaps, you could explain in a non-technical way each step e.g. what we need to do intuitively to estimate the intrinsic dimension of the local neighbourhood around a point.\n2. I believe that you could save some space e.g. by moving proofs in the appendix, such that to include some additional figures to demonstrate the steps of the approach.\n3. In high dimensions a lot of data are necessary in order to approximate the data manifold. I appreciate the synthetic and the MNIST/FashionMNIST experiments, but I think that some additional real world data in high dimensions should be conducted.\n\nI think this is an interesting contribution with potential merits, buy as a non-expert in the field I cannot criticize objectively the actual contribution of the method. However, I believe that there is some room for improvement as regards the clarity and the accessibility.", "strength_and_weaknesses": "I think that the problem the paper aims to solve is very interesting and useful for modern machine learning, and it has been motivated well. I am not an expert in the field of topological data analysis, but I believe that the proposed approach differs from the previous related works which are properly presented. The technical content seems to be reasonable and to support the claims, however, I have not checked it thoroughly. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "S8z397x3Ew", "reviewer": "Reviewer_ntAA", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper provides a method for detecting singularities in the data distribution in terms of the manifold hypothesis. The validity of the method is mathematically proven. Finally, it is applied to artificial data and real data to verify its effectiveness.", "summary_of_the_review": "The problem setting is interesting and important, and the report presents a theoretical solution to the issue. On the other hand, its practical use is unclear and I question whether it is appropriate for the scope of the conference. While I believe it is still within the scope at this point, I think it should be in a form that does not raise concerns.\n\n**Conclusion following discussion with the authors**\n\nI believe that our biggest concern, contribution to the AI field, has been resolved by clearly showing that the manifold hypothesis detects situations in which it does not work. Since the specific application of the method remains to be determined, and since there was no score of 7 in the peer review process, the score will be stayed.", "strength_and_weaknesses": "The issues and methods proposed are fine and appear to be theoretically sound. On the other hand, the concern is whether it is appropriate in terms of AI papers. Validation with real-world data has also been done, but it observes the relationship between each data class and indicator, which is different from the original goal of detecting singularities. Therefore, we do not know if it can be used for general AI tasks such as building AI models.For example, monitoring changes in the proposed index against data interpolation (transitions between two images) performed in the generative model, and comparing it to the classifier's confidency. Other considerations might include noise and adversarial attack detection.\n\nMinor point, but the formatting seems incorrect. I don't know why the line numbers are attached, but they should be removed.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject