Recovering Manifold Structure Using Ollivier Ricci Curvature
Authors: Tristan Luca Saidi
Abigail Hickok
Andrew J. Blumberg
Venue: ICLR 2025 Spotlight (2025)
Keywords: Manifold Learning
Persistent Homology
Ollivier-Ricci Curvature
Pruning
Nearest-Neighbor Graphs
Primary area: learning on graphs and other geometries & topologies
TL;DR: We present and test a theoretically grounded method that uses discrete graph curvature to prune nearest-neighbor graphs.

Abstract: We introduce ORC-ManL, a new algorithm to prune spurious edges from nearest neighbor graphs using a criterion based on Ollivier-Ricci curvature and estimated metric distortion. Our motivation comes from manifold learning: we show that when the data generating the nearest-neighbor graph consists of noisy samples from a low-dimensional manifold, edges that shortcut through the ambient space have more negative Ollivier-Ricci curvature than edges that lie along the data manifold. We demonstrate that our method outperforms alternative pruning methods and that it significantly improves performance on many downstream geometric data analysis tasks that use nearest neighbor graphs as input. Specifically, we evaluate on manifold learning, persistent homology, dimension estimation, and others. We also show that ORC-ManL can be used to improve clustering and manifold learning of single-cell RNA sequencing data. Finally, we provide empirical convergence experiments that support our theoretical findings.

Published as a conference paper at ICLR 2025
RECOVERING MANIFOLD OLLIVIER-RICCI CURVATURE
STRUCTURE
USING
Tristan Luca Saidi' Abigail Hickok?, Andrew
J. , Blumberg"
'Department of Computer Science. Columbia University
2 DDpaarmeett of Statisties & Data Science Wu Tsai Institute, Yale University
Departments of Mathematics and Computer Science, Irving Institute for Cancer Dynamics, Columbia University
ABSTRACT
We introduce ORC-MANL, new algorithm to prune spurious edges from nearest neighbor graphs using criterion based on Ollivier-Rice curvature and estimated metric distortion. Our motivation comes from manifold learning: we show that when the data generating the nearest-neighhor graph consists of noisy samples from a low-dimensional manifold, edges that shortcut through the ambient space have more negative Ollivier-Ricci curvature than edges that lie along the data man- ifold. We demonstrate that our method outperforms alternative pruning methods and that it significantly improves performance on many downstream geometric data analysis tasks that use nearest neighbor graphs input. Specifically, we evaluate on manifold learning, persistent homology, dimension estimation, and others. We also show that ORC-MANL can be used to improve clustering and manifold learning of single-cell RNA sequencing data. Finally, we provide em- pirical convergence experiments that support our theoretical findings.
INTRODUCTION
The first step for almost all geometric data analysis tasks is to build nearest neighbor graph. This reflects faith the manifold hypothesis- the belief that the data actually lies on low-dimensional submanifold of the ambient _. In this setting, the nearest neighbor graph recovers the intrinsic geometry of the data manifold, using the observation that small ambient distances lie along the manifold whereas larger may not.
Unfortunately, building nearest neighbor graphs from noisy data typically results in inaccurate rep- resentation of the metric structure of the underlying manifold. In this paper, we study edges in nearest neighbor graphs that shortcut through the ambient space and bridge distant neighborhoods of the underlying manifold. Such "shortcut edges" distort inferred distances and negatively impact downstream algorithms that operate on the graphs.
We show that Ollivier-Rieci curvature (ORC), a measure of discrete curvature graphs (Ollivier 2007], can be used to effectively identify shortcut edges when the data consists of noisy samples from low dimensional submanifold. We also show that graph distances can be used to support the identification of shortcut edges, allowing us to avoid accidentally catching "good" edges. Guided by these results, we describe an algorithm. Ollivier-Ree -iciii Curvature-based Manifold Learning and recovery (ORC-MANI.), to detect and prune shortcut edges.
ORC- MANL marks edges with extremely negative ORC as candidate shortcut edges. The algorithm then constructs a thresholded graph with the candidates removed. We then use the thresholded graph distance between the endpoints of candidate edges to check-if the distance is large, the edge was likely shortcutting the manifold through the ambient space. If the distance is small, the edge is added back to the graph. We find that despite simplicity, ORC-MANL incredibly effective and provides tangible performance improvement for downstream geometric data analysis algorithms for a variety of synthetic and real datasets. Our code for ORC-MANL and all experiments are available on Gi
Conrespondenc:: t s71 oo lumbfa.edu,, abigaf www.kkkle.kkoooooo andrew ummerrgeo umbla.. edu
" Link to implementation http:///////ttt..o////rrereseeee /orem)

---

Published as a conference paper at ICLR 2025
1.1 CONTRIBUTIONS
We introduce ceneral-purpose method, ORC-MANI,, that uses discrete graph curvature detect and prune unwanted connectivity in nearest-neighhor graphs. Our method is theoretically justified, and in practice significantly improves the performance of downstream tasks like manifold learn- ing, persistent homology, and estimation of important geometric quantities like intrinsic dimension and curvature. Furthermore we find that ORC-MANL is effective on real world single-cell RNA sequencing data: ORC-MANL pruning reveals clusters in PBMC data in accordance with ground truth annotations and results in embeddings that better preserves communities of neuronal cells. Fi- nally, we also include experiments to show that our theoretical convergence results are supported by empirical experimentation.
1.2 RELATED WORK
Several graph pruning approaches have been proposed in the literature. Some use density estimation as heuristic for detecting unwanted edges and show results on noiseless toy datasets (Xia et al. 2008 Chao et al. 2007). Zemel & Carreira-Perpiñan (2004) proposed an approach that builds a minimum spanning tree of the original nearest neighbor graph; but this relies on the assumption that shortcutting edges are longer than good edges, phenomenon that does not always hold. Another family of approaches attempt to adaptively tune the number-of-neighbors parameter & of the nearest neighbor graph based on the local geometry of the data. Zhan et al. 2209
Graph Pruning.
; Elhenawy et al. (2199) adopt similar approaches, looking at the linearity of neighborhoods using PCA and pruning accordingly. These methods typically demonstrate a limited set of results on noiseless data and provide little theoretical justification.
Ollivier-Ricci Curvature. Ollivier-Ricci curvature (ORC) was proposed measure of curvature for finite metric spaces by Ollliierr (2007), with follow-up results demonstrating theoretical and empirical convergence the underlying manifold Ricci curvature under mild assumptions (Ollivier) 2009 van der Hoorn et al.] 2021). In the network geometry literature, ORC based approaches have been effective for community detection, drawing connections to Ricci flow from Riemannian geometry (Sia et al. 2019 Ni et al. 2019). Sia et al. (2019) prune edges with extremely negative ORC and justify it using theory that argues that ORC detects communities. Our theoretical work instead justifies the use of ORC for recovering correct munifold structure. A multitude of papers have used ORC for clustering and modeling diffusion processes on graphs as well (Gosztolai & Arnaudon 2021; Tian al.) 2023). This work has led to applications for graph neural networks, where ORC was used to prevent over-squashing and over-smoothing (Liu et al. [003] Nguyen et al. and improving encodings of local graph structure (Fesser & Weber 2024).
2023).
BACKGROUND AND DEFINITIONS
2.1 DIFFERENTIAL AND RIEMANNIAN GEOMETRY
Manifolds. A manifold is generalization of the notion of a surface is topological space that locally looks like Euclidean space. Concretely, a manifold M is an m-dimensional space such that for every point
M there is neighborhood U C M such that U is homeomorphic to RT At every point x E .M one can attach a m-dimensional vector space called the tangent space (denoted T,M) that contains all directions in which path in M can tangentially pass through In similar manner, the normal space at x (denoted M) is a vector space containing all directions normal to M at x. We will work with Riemannian manifolds, which are smooth manifolds endowed with a Riemannian metric. A Riemannian metric is an assignment of an inner product to each tangent space that varies smoothly with respect local similarity, angles, and distances. For a more detailed treatment of differential and Riemannian geometry, we direct readers to Prasolov (2022) and (2118)..
M. This metric allows one to make statements about
Geodesics. In this paper we are concerned with submanifolds M of TR. whose Riemannian metrics are induced by the ambient Euclidean metric. Recall that the length of a continuously differentiable path y [a, bj IRD is L(>) So [T)(()) dt. The geodesic distance between two points x and in submanifold M of D is simply the minimum length over all continuously differentiable paths
2

---

Published as a conference paper at ICLR 2025
connecting and y- In this paper consider the distance metric da, as the length of the geodesic path through M connecting a E M to M.
Tubular Neighborhoods. The 7-tubular neighborhood Tub, (MV of submanifold M of R is the set {x RD d(M, x) I T). where d(M, is the Euclidean distance between æ and the nearest point x' E M.. Intuitively, (MM is "fattened" submanifold of R. that envelops M. We use the tubular neighborhood as a model of the support of a noisy sampling distribution over M with a bounded level of isotropic noise.
Manifold Embedding Parameters. We will define manifold parameters that are central the the- oretical analysis that follows, adopted from Bernstein ett (2001). The minimum radius of curvature is (o(M max,,4 Rt)l where Y R > RD is aime-parameterized unit-speed geodesic in M. Intu- itively, rM(M indicates the extent to which manifold geodesics curl in the ambient Fuclidean space. The min- imum branch separation So(M) is the largest positive number such that Vz, E M. || yll2 < <so(M) im- plies dm( y) S (r)(M). While in general people use quantities like the reach and injectivity radius to describe manifold embeddings, these quantities are intimately related to the ones described; we choose to stick to the described parameters for compat- ibility with theorems invoked from prior work.
mi(M)
M)
M
Figure 1: Visualization of the manifold parameters ro( and (M))
Proposition 1. Suppose M is compact submanifold of without boundary and with a minimum radius of curvature Mo(M). Then Tub,M has minimum radius of curvature of ro(M) T.
2.2 NEAREST NEIGHBOR GRAPHS AND UNWANTED CONNECTIVITY
Geometric machine learning approaches attempt to capture the underlying structure of M from noisy samples X. typically beginning with the construction of nearest neighbor graph. These graphs use connectivity rules of two flavors: e-radius, k-nearest neighbor (k:NN) (Bernstein et al.) 2001]. The e-radius connectivity scheme asserts that for any two vertices a and b, an edge exists between them if lla - b1l2 < The k-NN rule the other hand asserts that the edge exists only b is one of the nearest neighbors of a, or vice versa. While the e-radius rule more amenable theoretical analysis, the k-NN rule is used more often in practice. Unless otherwise specified, an edge (z, y) in neighbor graph is assigned the weight || w112-
Definition 2.1. An edge (I,y) in nearest neighbor graph of noisy samples from M is shortcut edge if
dm(proj z, projm v) > ( + l)ro(M)
where projm(()) is the orthogonal projection onto M and ro ro(M) is the minimum radius of curvature of M.
One of the main corrupting phenomena in the construc- tion of nearest neighbor graphs is the formation of short- cut edges, edges that bridge distant neighborhoods of the underlying manifold M. Figure depicts simple 2-dimensional example of a shortcut edge, while Defi- such
M
Tub,(M)
nition 2.11 provides mathematical description edges. Note that in Section 3 we state the assumption that T < ro(M), which guarantees the uniqueness of the projection map. Intuitively, a shortcut edge is one where large distance through M required to traverse between the endpoints, relative to the Euclidean distance between the endpoints of the edge itself. While the definition has no explicit dependence on |æ vll2, make the sumption in Section 3 that the connectivity threshold (and thus | v|(2) is smaller than (MM.
Figure 2: Visualization of a nearest neighbor graph build from noisy sam- ples from M. Desirable edges are shown green, while the shortcut edge is shown in red.
3

---

Published as a conference paper at ICLR 2025
2.3 OLLIVIER- RICCI CURVATURE
Oliivie-RRicci curvature (ORC) was proposed as a measure of curvature for discrete spaces (Ollivier 2009) by leveraging the connection between optimal transport and Ricci curvature of Riemannian manifolds. While there have been many subtle variations of ORC, we will describe a modification to the most common one. Given an edge (z, y) in weighted graph G with vertices V and edges E, define the neighborhoods of z and y as (xx == {o V (zz, v) E E, v & x} and N(y) == {u E V (y. v) E E, u + y). Further define lrr and My as uniform probability measures over N (ax) {v) and and (wv) \ {z),, respectively. The ORC of the edge (x, v), denoted k(I, y), is defined as
W( My)
<(z, v) ==
de(
where W W(Uz: My) is the I-Wasserstein distance between the measures ft and By (regarded as mea- sures V), with respect to the weighted shortest-path metric d.(:: -). The weighted shortest-path metric da( y) simply represents the total weight of a weight-minimizing path from x to through G. The 1- I-Wasserstein distance is computed by solving the following optimal transport problem,
W (pay My)
inf (Ell(Ee
Σ EVXV
(((a,))((,bb)
where M(p,. My) the set of all measures on V V with marginals μar and My. Intuitively, ORC quantifies the local structure of G: negative curvature implies that the edge is "bottleneck", while positive curvature indicates the edge is present in a highly connected community.
In our setting, the vertices of the graph G are points in Rº, and edges connect points (I, y) such that || - yll S c, where c is a user-chosen connectivity threshold. A common choice is to weight the edges by the Euclidean distance ||-- 2ll2. but make slight modification to this formulation. In computing the ORC in the present paper we use unweighted edges; namely, all edges are snapped to weight of 1. This is a key aspect of our method, as it forces the ORC reflect only the local connectivity and makes it invariant to scale. This modification also restricts the ORC values to lie between 2 and +1, whereas with weighted graphs, the values are unbounded below. For the rest of the paper, any reference to Ollivier-Riee curvature is a reference to the formulation we have just just described. In all cases other than computing ORC, an edge (x. y) is assigned the weight ||x - ull2. as mentioned in Section 2.2]
Proposition 2. For any edge (x,, y) in unweighted graph, -2 S <(x, 3) S 1.
3 METHOD AND THEORETICAL RESULTS
In this section we will describe ORC-MANL, a novel algorithm for pruning nearest neighbor graphs based on ORC and metric distortion. We will also describe the theoretical results that justify the algorithm construction, the proofs of which are in Appendix A.4
ORC- MANL (Algorithm I takes input noisy samples X' from some underlying manifold, an accompanying nearest neighbor graph G (V, F) of the data, and tolerances 5, X E [0, 1]. The method constructs a candidate set of edges that have curvature more negative than threshold just larger than - 1. We note that the exact expression for this threshold, -1 + 4(1 6). arises from Lemma A.I The expression simply captures the notion that shortcut edges tend to have ORC less than some constant value near -1, where ó I results in strict threshold of - and smaller d values introduce slack. Importantly, not every edge in the candidate set is necessarily a shortcut; good edges can have extremely negative curvature well. To combat this, the method proceeds by constructing a thresholded graph G' (V, E') where E' = E \ C. The weighted graph distance ( y) is checked for every edge (ar, y) C. If this distance exceeds the threshold derived in Theorem 3.3 we can be confident that (z, y) undesirably bridges distant neighborhoods of M (a visualization for which is shown in Figure [3). The edge therefore removed from G. If the threshold is not exceeded, the edge is not removed. We would also like to emphasize that the threshold arising from Theorem (3. is unaffected by feature scale, as is equivalent to a bound on de (Ir s)/c. Finally, for a time complexity analysis of the ORC-MANL algorithm we direct readers to Appendix A.2
4

---

Published as a conference paper at ICLR 2025
Algorithm ORC-MANLL
We provide three theoretical results that justify ORC-MANL. First, we show that when the data generating the nearest neighbor graph consists of noisy samples from an underlying manifold M, the ORC of shortcut- ting edges tends to be very negative. Second, we show that as one samples more points, every vertex has an in- creasing number of non-shortcutting edges with very positive ORC. Last, we derive a bound on the graph dis- tance (in the ORC thresholded graph G') between any vertices connected by a shortcut edge in G.
Require: G = (V, a nearest neighbor graph, X, 8
C+ [
2: for (I.y) in E do
& candidate selection
3: k(æ, y) f- OllivierRicei(G. (x, v))
4: if' k(z, y) < -1+ 4(1 then
Lemma A.1
5:
C+ CU ((.((( ((,,))
6: E
7: (V,E")
8: for (z,z) in do
shortcut detection
9:
(=) ShortestPath(G", v)
df (z, v) x(x+1)(->) then b >Theorem 3.3
2v24X
11:
E + E {(x,0)}
return EV
We consider the setting where M is compact m-diimensional smooth sub- manifold of DDD without boundary. Let (MV be the tubular neighborhood of M, and sume X' C (M) consists of n independent draws from the probability density function p: Tub, (M) R+
-le-projm c1ē
20
|| - 21-projm S T
p(2)
Z
(1)
0,
O.W.,
where a normalizing constant such that Siub. (M) p(z)dV integrates to 1. We are given a con- stant À < 1, which controls the threshold we use when checking the weighted graph distances of candidate edges. For the rest the paper, suppose that
1. (Support criteria): 2T 3T < so(M), 37 < <
2. (c-radius criterion): min
- 7) ( -) ro(M))
where sn(M) is the minimum branch separation of M and ro(M) is the minimum radius of curva- ture of M. Assumption I eensuress that the orthogonal projection proj : Tub,. + M is unique, Thile to use Bernstein al. (2001) to make statements about geodesic distances.
Our first theorem establishes that the ORC for shortcut edges converges to negative values in the shortcut edges occur with
limit of vanishing noise a. We note that so long т and nonzero probability. Observe that, in combination with Proposition 2 this result indicates that the ORC of shorteut edges tends concentrate in the bottom third the possible range of values.
Theorem 3.1 (Ollivier-Rice Curvature of Shortcut Edges). Suppose that X; is point cloud sampled from p with parameters a; and т; and G; is its nearest-neighhor graph. Also suppose that M satisfies the conditions above, and - 0+ and - 0+ as i - so. Then as i - co, we have x(x,2) y) < for all shortcut edges (x, y) G2 with probability approaching
To be confident that ORC can be effective at identifying potentially shortcutting edges, would also like to be sure that there exists a sufficient number of good (non-shorteut) edges with more positive ORC. This motivates Theorem 3.2
Theorem 3.2 (Ollivier-Rice) Ricci Curvature Non-Shortcut Edges). Let l be a positive integer.
With high probability the number of points D0, every point has at least k neighbors that it is connected to by non-shoricut edges with ORC +1.
Proofs of Theorem 3.1 and Theorem 3.2 can be found in Appendix A.4.I These results allow us to create a candidate set shorteut edges by looking at the ORC of edges in G. We then expect that the graph G' (V, F'), where F'' has all extremely negative-curvature edges removed, has no
5

---

Published as a conference paper at ICLR 2025
shorteut edges and a large number of good edges. It should therefore have metric structure that is more aligned with that of the underlying manifold M. With that said, we also expect the candidate set to contain some non-shortcut edges, which do not want remove from G. In the last part of our algorithm, we filter our candidate set to identify edges that are most likely to be shortcuts. This motivates our third theorem, which establishes that for vertices that were previously connected in G by a shortcut edge, their weighted graph distance in G' is large relative e.
Theorem 3.3 (Filtered Graph Distance). Suppose that X₂ is a point cloud sampled from with parameters o, and T; and G2 (V,, Ei) its nearest neighbor graph. Also suppose that M satisfies the conditions above and - 0+ and T; - 0t as i + xc. Define the subgraph where
G²= CVs, F2)
E = ( vi) E Es k((),)))) > -1].
Then as 00 we have
da (2, (( + 1)
2V241
for all shortcut edges in Gi with probability approaching where [0, 1] (eq. 344 is a random variable whose distribution is dependent on M and T₁-
Remark 1. The random variable / is inversely related to the number and lengths of edges that shortcut through M but do not satisfy the definition of shortcut edge in M. We expect that 3 concentrates close to I, and experimentally we find that 3 = works well.
Theorem 3.3 arises from two results: (1) one can bound geodesic distances through Tub, with geodesic distances of paths through M with similar endpoints, and (2) under reasonable conditions one can relate the graph distances through nearest neighbor graph built from data sampled from Tub to the geodesic distance through Tub.
Figure 3 shows experimental support for Theorem 3.1 and Theorem 3.22 on two synthetic manifolds averaged across 10 seeds. In accordance with Theorem 3.1 we find that as the noise parameter a falls, the ORC of shortcutting edges falls commensurately. We see that it rapidly drops below -1 and asymptotes to the most negative possible value, -2 In accordance with Theorem 3.2 we find that sample more points each vertex has an increasing num- ber of non-shorteut incident edges with positive ORC. For more empirical support of the theory we provide an illus- trative example in Figure 25 in Appendix A.5.8 We also discuss the behavior of ORC-MANL as a function of un- derlying manifold curvature in Appendix A.5.7
Figure 3: Empirical convergence re- sults. The bottom plots the percent of nodes with at least l incident edges that (x) non-shortcutting and have positive ORC.
EXPERIMENTS
Building nearest neighbor graphs as a data pre-processing step is ubiquitous in geometric data anal- ysis. Therefore our method well suited for evaluation on broad range of algorithms that operate on nearest neighbor graphs.
Our experiments are divided into two sections. Firstly, we evaluate ORC-MANL on a variety of synthetic manifolds for broad array of benchmark geometric data analysis and machine learning tasks. We also compare pruning accuracy to several benchmark methods presented previously in the literature. We then show that ORC-MANL pruning reveals clusters aligned with ground truth annotation for single-cell RNA sequencing (scRNAseq) data of peripheral blood mononuclear cells (PBMCs). We also find that ORC-MANL pruning improves downstream manifold learning em- beddings of scRNAseq data of anterolateral motor cortex (ALM) brain cells in mice. Furthermore, include experiments in Appendix A.5.3 that suggest that ORC-MANL is effective MNIST 2018). and we add ablations for nearest neighbor graph
(Deng) 2012) and KMNIST (Clanuwat et al. parameter i: and OR C-C-AANL. parameters À in Appendix A.5.5

---

Published as a conference paper at ICLR 2025
4.1 RESULTS: SYNTHETIC DATA
For our synthetic manifolds, we have curated list of and 2-dimensional manifolds embedded in I2 and R respectively, that exhibit varying intrinsic and extrinsic curvature. The 1-dimensional manifolds include concentric circles, a mixture of Gaussians, twin moons, an S curve, the 1- dimensional swiss roll, Cassini oval (Cassinil 1693) and concentric parabolas. The 2-dimensional manifolds include chained tori, concentric hyperboloids, an adjacent hyperboloid and paraboloid, adjacent paraboloids and the 2-dimensional swiss roll. Note that we include additional experi- ments indicating the improved performance of spectral clustering with ORC-MANL pruning in Appendix A.3.4 We also provide more experimental details regarding sampling and nearest neigh- bor graph construction in Appendix A.3
4.1.1 PRUNING
Our first experiment quantifies the ability of ORC-MANL to prune (and therefore classify) edges of nearest neighbor graphs. We report classification accuracy for 1-dimensional manifolds in Ta- [lnd 2-dimensional manifolds in Table the tables, we also include performance for several baseline graph pruning approaches. Algorithm descriptions for each baseline are provided in Ap- pendix A.3.1 Accompanying visualizations for ORC-MANL, pruning results are shown in Figure
Table I: Pruning performance of ORC-MANL vs. baselines. For each entry, the top and bottom rows indicate the percentage of "good" edges and shortcut edges removed, respectively.
Concentric Toet
Concentric Hyperboloids
Hyperboloid and Paraboloud
Parsholeids
Swiss Roll
ORC MANL (ours)
100.0 + U.D
0.0 + D.O
99.1 + 2.6
0.0 0.0
89.4 21.3
0.0 0.0
100.0 U.D
0.0 + 0.0
100.0 + 0.O
0.0 + 0.0
ORC ONLY
100.0 0.0
15.7 0.3
100.0 0.0
13.1 0.2
18.1 0.3
3.3
100.0 +
18.0 + 0.3
100.0 0.0
14.8 0.2
Xia
+
0.0 + 0.0
0.4 0.1
4.2
21.3
32.8
MST
Zemel& & Somein-Perpinin 2004 Chao et al, 2007
89.6 3.7
91.611:3
0.2
58.5
18.5::100 10.8
66.2 17.2
2..3+
100.0 0.0
DENSITY
Chao et al. 2006
30.4
16.8
2 8.0
+ 1.6
22.9 0.9
1.0
32.9 1.1
0.6
63.8 1.3
8.9 7.4
29.5 1.0
7.8 0.7
22.0
8: 0.4
4.2
18.9=
34.7 0.5
2.3 0.2
DISTANCE
86.8
5.6
6..1
78.8
26.5
13.7
40.0 9.8
We find that ORC-MANL vastly outperforms all basclines on majority of the synthetic man- ifolds. Our approach removes all shorteut edges in all but two examples, and removes no shortcut edges across all examples. Unsurprisingly, we find that ORC ONLY exhibits identi- cal performance on shortcut edge removal, but typically removes around 15% of good edges as well. BISECTION performs poorly all manifolds except the moons and the S curve, likely stemming from the fact that shortcut edges for those examples travel longer distances and pass through lower density regions than shorteut edges for other synthetic manifolds. This also reflected in stronger performance by DISTANCE the moons and the S curve. MST unsurprisingly performs well on examples where the underlying manifold M has single connected com- ponent (like the swiss roll and S curve) but con- sistently struggles with most other examples. Fi- nally. DENSITY and DISTANCE exhibit erratic per- formance, at times being competitive with ORC- MANI., and at times performing poorly. We attribute this to the variability in the extent to which shorteut edges (I) pass through low density regions, and (2) have longer length relative to other graph edges. Fur- thermore, these effects can be compounded by poor kernel density estimates for the DENSITY baseline.
Figure 4: Visualization of nearest neighbor graphs before and after pruning with ORC- MANL. Shortcut edges are highlighted red.
We would like underscore the fact that algorithm parameters for ORC-MANL are fixed at 0.8 and X 0.01 across all manifolds and trials (and 5

---

Published as a conference paper at ICLR 2025
for ORC ONLY is similarly fixed at 0.8) in Table I The baseline methods MST, DENSITY and DISTANCE however required manual threshold tuning for each manifold in the evaluation set listed. Despite this additional labor induced by parameter tuning, find that ORC-MANL outperforms these other methods. All manifold and algorithm parameters are listed in Table 2 and Table
4.1.2 MANIFOLD LEARNING
We turn evaluate ORC-MANL on manifold learning, family of algorithms concerned with find- ing low dimensional coordinates on the data submanifold. Almost all manifold learning algorithms begin by constructing a nearest neighbor graph, making ORC-MANL perfect pre-pin preccesecsinggggeeeeeeeee step.
We compare embeddings of nearest neighbor graphs with and without ORC-MAN preprocessing for data sampled from noisy 2-dimensional swiss roll embedded in R with and without hole.
We test on Isomap (Tenenbaum et al. 2000), Locally Linear Embeddings (I (I.EE,, (Belkin & Niyogi, 2003), UMAP (Melnnes et al. 20) and t-SNE (Van der Maaten & Hinton (008) shown in Fig-
ure 5 We leave out Laplacian Eigenmaps (Belkin & Niyogi (003) as find that it fails preserve both underlying dimensions of the noisy swiss roll, independent of the presence of shortcut edges. To the best of our understanding. this likely arises from the Repeated Eigendirection Problem (REP) associated with eigenfunction based methods (Dsilva et al.) 2018). For UMAP and t-SNE we use graph distances (induced by the pruned and unpruned graphs respectively) as algorithm inputs.
We observe that across both manifolds and all methods, ORC-MANL, pruning typically improves the emhedding. For Isomap, this improvement is the most pronounced; without pruning. Isomap fails to unroll either swiss roll. We attribute this to distorted geodesic distance estimates (which the first step of the Isomap algorithm) arising from shortcut edges. We also find significant improvement in the quality of the embeddings for LLE. For both manifolds, LLE without ORC-MANL struggles to preserve the primary dimension of the underlying manifold.
Swiss Roll
Swiss Hole
ORC -MANL
None
(a) Isomap (b) LLE
(c) UMAP (d) ESEE
(x) Isomap
(b) LLE
(c) UMAP
(d) & SNE
Figure 5: Embeddings of the noisy 3-dimensional swiss roll (left) and noisy 3-dimensional swiss
hole (right) produced by several popular manifold learning algorithms. The UMAP embeddings shown were run on noisier samples than those for the other embedding algorithms.
We find that UMAP benefits from ORC-MANL pruning well, though the difference with and without pruning emerges only when the noise is extremely large. Finally, t-SNE embeddings for both datasets appear be better when coupled with ORC-MANL, as it prevents discontinuities that arise in the unpruned embeddings. Unfortunately across trials we do not see consistent benefit from pruning, though it is never detrimental. For completeness, embeddings for three different trials shown in Figure 20 in Appendix A.5.2
4.1.3 PERSISTENT HOMOLOGY
Next, we evaluate our method on persistent homology. Persistent homology begins by constructing nested sequence K,, C Kr, C .... K,, ... of simplicial complexes, also referred to as filtered complex. common example is the Vietoris-Rips (VR) filtered complex. For data points X' with metric d, the VR simplicial complex K, has simplex for every subset of points with pairwise distances < r (Ghrist 2014). For our experiments, we construct the VR filtered complex where the metric is the weighted graph distance. One can summarize the result of persistent homology with persistence diagram, simply a multiset of points in IR3. Each point (Fminh- rdeath) in the persistence diagram records the filtration parameter which homology class is born and dies respectively.
We present results for persistent homology applied to nearest neighbor graphs with and without ORC-MANL. preprocessing in Figure We show results on (1) the noisy concentric circles dataset,
8

---

Published as a conference paper at ICLR 2025
and (2) the noisy chained tori manifolds. For each manifold, present the persistence diagram of an oversampled, noiseless point cloud of the manifold as proxy for ground truth. The persistence diagrams are shown for qualitative evaluation, but also include dissimilarity scores measured as the Wasserstein distance to the noiseless persistence diagram for quantitative evaluation (the details for which provided in Appendix A.3.2)
Noiseless
ORC-MANL
None
Noiscless
ORC-MANL
None
Persistence Diagram
Ho: 0
Ho 18.88
Ho 000
Ho
Ho 288194
Hg
Wessenstein Distance
H1:0
1.87
H. 13711
H₁ 35.66
Hy 50.10
H₂:0
H3 28.71
:2:30.100
Figure 6: Persistent homology applied to the concentric-cireles (left) and the chained-tori (right). The bottom row indicates the Wasserstein distance to the noiseless persistence diagram.
We observe that for both datasets, the persistence diagrams computed on ORC-MANL pruned near- neighbor graphs qualitatively and quantitatively more similar the noiseless persistence dia- grams than their unpruned counterparts. We emphasize that for both synthetic manifolds, the pruned diagrams correctly capture the number of essential classes (homology classes that persist forever), while non-prun con-prune diagrams do not. We observe infinite Wasserstein distances for Ho between the unpruned and noiseless persistence diagrams, but only finite distances for the ORC-MANL pruned diagrams. For other homology dimensions, we also see that ORC-MANL pruned diagrams consis- tently exhibit smaller distances to the noiseless than non-pruned diagrams.
4.1.4 GEOMETRIC DESCRIPTORS
MSE 3
XISE: 0,031 RR
MSS:: 0.636
MSE: 2:6c: S
R
Finally, we test the ability of ORC- MANL to preserve geometric descrip- tors of the underlying manifolds. We estimate intrinsic dimension and scalar curvature for the (I) swiss roll and (2) adjacent spheres datasets. We compare our estimates to the ground-truth values. We the maximum likelihood estima- tion approach to estimating intrinsic di- mension from Levina & Bickel| (2004),
GRC
None
Scalur
Intritsle Dimensiin
Sealor Cursature
Intrfiraa sie Dimenston
Curvature
Figure 7: Scalar curvature and intrinsic dimension esti- mation. The star indicates the ground truth.
and we use the algorithm from Hickok & Blumberg (2023) to estimate sealar curvature. The details for both algorithms are detailed in Appendix A..33 and Appendix AA..44] respectively.
We report intrinsic dimension and scalar curvature estimation results on the noisy swiss roll and noisy adjacent spheres dataset in Figure 7 We find that ORC-MANL pruning provides tangible improvement over non-pruned estimates, especially for scalar curvature. For intrinsic dimension estimation we see improved point-wiss accuracy in regions with high number of shortcut edges (for example, the area between the adjacent spheres); in regions with smaller presence of shortcut edges, we find that the unpruned graphs produce accurate results.
4.2 RESULTS: REAL DATA
We evaluate the efficacy of ORC-MANL real-world data by using it to analyze cell-type anno- tated ScRNAseq data of (1) anterolateral motor cortex (ALM) brain cells in mice available from the Allen Institute (Abdelaal al. 2019) and scRNAseq data of peripheral blood mononuclear

---

Published as a conference paper at ICLR 2025
cells (PBMC) available from 10XGenomies. In accordance with previous work, for both datasets extract the 2000 most variable genes, followed by PCA (Pearson, 1901 to obtain a 50-dimensional representation of the original data.
Neuronal
Intibitory
e Non ncuronal
Non-Neurce Neuronal
Neuronal
Neuronal
zdewoss
Non- Neuronal
Isomap1
isomep1
ORC-MANL
None
Figure 8: Isomap (Tenenbaum et al. 2000) embedding of scRNAseq data from anterolateral motor cortex (ALM) brain cells in mice with and without ORC-MANL, pruning.
For the brain cells we use Isomap (Tenenbaum et al. 2000) to embed ORC-MANL pruned and unpruned nearest neighbor graphs. Figure shows the embeddings with base truth annotations. We find that pruning with ORC-MANL qualitatively improves the Isomap embedding of the data, the distinction between neuronal cells (labeled "Inhibitory" and "Excitatory") and non-neuronal cells becomes significantly more pronounced after pruning. For completeness, we include UMAP and t-SNE embeddings of this dataset in the appendix in Figure 23 we observe poor performance as measured by neuronal community preservation both with and without pruning, suggesting issues with the embedding algorithms themselves as opposed to pruning.
Pay COeTTO Vemeory
specrall
Cot Oycrrac 615
USAPPI ORC-MANL
URAP
Special
spectaal
None
ORC-MANL
None
Figure 9: UMAP and spectral embeddings of PBMC scRNAseq data with and without ORC-MANL preprocessing. with edges of the pruned and unpruned graphs visualized in grey. Gaussian noise was added to the spectral embeddings with ORC-MANL pruning for visibility, as connected components get mapped to a single point.
Now we turn to the PBMC dataset, where we show UMAP and spectral embeddings in Figure 9 We find that ORC-MANL pruning leads connected components that largely align with base truth annotations; this is reflected in the spectral embedding, which maps each component to unique lo- cation in the embedding space. Furthermore, edges that formerly bridged seemingly distinct clusters in the embeddings were removed, resulting in clearer cluster structure in the pruned graphs.
5 CONCLUSION
In this work we present ORC-MANL, a theoretically justified and empirically validated approach for nearest neighbor graph pruning- We rigorously demonstrate that shortcut edges necessarily exhibit particularly negative ORC for graphs sampled from manifolds with a bounded level isotropic noise. Our method also validates the removal of any edge by using a theoretically derived bound on graph distances implied by the geometry of shortcut edges. We qualitatively and quantitatively demonstrate that ORC-MANL. is beneficial to variety of downstream geometric data analysis tasks on synthetic and real data. We also compare our method to baselines from the literature its ability correctly prune shorteut edges and avoid non-shorteut edges.
10

---

Published as a conference paper at ICLR 2025
ACKNOWLEDGEMENTS
The authors would like to thank Yining Liu for her invaluable advice on the real data experiments. Furthermore, they would like to thank Gilad Turok, Gabriel Guo, and Nakul Verma for their insight- ful thoughts and discussions about the manuscript and the work. Abigail Hickok was supported by NSF grant DMS- RMM-2203402. Andrew Blumberg was supported part by NFS grant DMS-231 113388 and ONR grant N00014-22-1-2679.
REFERENCES
Tamim Abdelaal, Lieke Michielsen, Davy Cats, Dylan Hoogduin, Hailiang Mei, Marcel JT Rein- ders, and Ahmed Mahfouz. A comparison of automatic cell identification methods for single-cell RNA sequencing data. Genome biology, 1-1,-19, 2019.
Francis Bach and Michael Jordan. Learning spectral clustering. In S. Thrun, Saul, and B. Schölkopf (eds.), Advances in Neural Information Processing Systems, volume 16. MIT Press, 2003. URL Inttps::/proceedinngg hew..eeee....nne................ wwtppppppppcppppp...pppppppppp fitesp/ppr.lseperrrrrr.. pdf
Mikhail Belkin and Partha Niyogi. Laplacian eigenmaps for dimensionality reduction and data representation. Neural computation, 15(6):1373-336, 2003.
Mira Bernstein, Vin Silva, John Langford, and Joshua Tenenbaum. Graph approximations to geodesics on embedded manifolds. 02 2001.
Giovanni Domenico Cassini. De I'Origine du progrès de l'astronomie de son usage dans la géographie et dans la navigation, par M. Cassini. Impr. royale, 1693. URL http::::: //books. hatgglee.cmbooooeeee hock//ookssaa. 7id P.-
googgle. com
Shao Chao, Huang Hou-kuan, and Zhao Lian-wei. P-ISOMAP: A ISOMAP-based data visu- alization algorithm with less sensitivity to the neighborhood size. Acta Electronica Sinica, 34(8): 1497, 2006.
org. http:/eeee/////////////
Shao Chao, Huang Hou-kun, and Zhao Lian-wei. A more topologically stable ISOMAP algorithm. Journal of software, 18(4):869 877, 2007.
Tarin Clanuwat, Mikel Bober-Irizar, Asanobu Kitamoto, Alex Lamb, Kazuaki Yamamoto, and David Ha. Deep learning for classical Japanese literature, 2018.
Li Deng. The MNIST database of handwritten digit images for machine learning research [best of the web]. IEEE Signal Processing Magazine, 141-)144 2012. doi: 10. 1099PP22/2222 2211477.
Carmeline J. Dsilva, Ronen Talmon, Ronald R. Coifman, and Ioannis G. Kevrekidis. Parsimonious representation nonlinear dynamical systems through manifold learning: A chemotaxis case study. Applied and Computational Harmonic Analysis, 44(3):759 2018. ISSN 1063-5203. doi: http:///caoceeeeteeeeeee///////. com/
URL hhtpp:: www.
Mohammed Elhenawy, Mahmoud Masoud, Sebastian Glaser, and Andry Rakotonirainy. Topolog- ical stability: A new algorithm for selecting the nearest neighbors in non-linear dimensionality reduction techniques. arXiv preprini urXiv:1911.05312 2019.
Lukas Fesser and Melanie Weber. Effective structural encodings via local curvature profiles. In The Twelfth International Conference on Learning Representations, 2024.
Robert W Ghrist. Elementary applied topology, volume 1. Createspace Seattle, 2014.
Adam Gosztolai and Alexis Arnaddnn. Unfolding the multiscale structure networks with dynam- ical Ollivier-Ricci curvature. Nature Communications, 12(1 12(1):4561, 2021.

---

Published as a conference paper at ICLR 2025
John Hartigan and Manchek Wong. A k-means clustering algorithm. Journal the Royal Statistical
Sociery. Series C (Applied Staristics), 28(1)1000-108, 1979. ISSN 00359254, 14679876. URL
htttp://wwk jstor. .rg. stabeeabbeleeee..... 2ttlg///aabee223633333 2246833
Abigail Hickok and Andrew J. Blumberg. An intrinsic approach to scalar-curvature estimation for
point clouds, 2023. URL hnttps:/:/
org/abs/ 2208 02615
Lawrence Hubert and Phipps Arabie. Comparing partitions. Journal of classification, 2:193-218, 1985.
Joseph Kruskal. On the Shortest Spanning Subtree of Graph and the Traveling Salesman Problem. In Proceedings of the American Mathematical Society, 7, 1956.
Théo Lacombe, Marco Cuturi, and Steve Oudot. Large scale computation of means and clusters for persistence diagrams using optimal transport. Advances in Neural Information Processing Systems, 31, 2018.
John M Lee. Introduction to Riemannian manifolds, volume 2. Springer, 2018.
Elizaveta Levina and Peter Bickel. Maximum likelihood estimation of intrinsic dimension. Advances in neural information processing systems, 17, 2004.
Yang Liu, Chuan Zhou, Shirui Pan, Jia Wu, Zhao Li, Hongyang Chen, and Peng Zhang. Curvdrop: A Ricci curvature based approach to prevent graph neural networks from over-smoothing and over-squashing. In Proceedings of the ACM Web Conference 2023, pp. 221-230, 2023.
Leland Mclnnes, John Healy, and James Melville. Umap: Uniform manifold approximation and projection for dimension reduction. arXiv preprint arXiv: 1802.0336, 2018a.
Leland McInnes, John Healy, Nathanicl Saul, and Lukas Grossberger. Umap: Uniform manifold approximation and projection. The Journal of Open Source Software, 3(29):861, 2018b.
Khang Nguyen, Nong Minh Hieu, Vinh Due Nguyen, Nhat Ho, Stanley Osher, and Tan Minh Nguyen. Revisiting over-smoothing and over-squashing using Ollivier-Ricei curvature. In ternational Conference on Machine Learning, pp. 25956-25979. PMLR, 2023.
Chien-Chun Ni, Yu- Yao Lin, Feng Luo, and Jie Gao. Community detection on networks with Ricci flow. Scientific reports, 91):9994, 2019.
Yann Ollivier. Ricei curvature of metric spaces. Comples Rendus Mathematique, (4441)))4 2007.
Yann Ollivier. Ricci curvature of Markov chains metric spaces. Journal of Func- tional Analysis, (56(3):810-864 2009. ISSN 0022-1236. doi: http:///bb.org//100000/./. 2008.1 11 1..01.. URL https:::t.... /wt:///wwww//.. sci ecceecediiicccccccccccccccccciic rect wwt. ccom//sccienne//ttticc//iiiiiii
S00221 0T0221236008045222
Karl Pearson. On lines and planes of closest fit to systems of points in space. The London, Edin- burgh, and Dublin Philosophical Magazine and Journal of Science, 2(11):559-772 1901, doi: 10. 478044447774400 URL UtLhttps::/ doi. wrg//0.............oo.. 1080010110011 0111////11784440099446833
Victor Prasolov. Differential Geometry, volume 8. Springer Nature, 2022.
Jayson Sia, Edmond Jonckheere, and Paul Bogdan. Ollivier-Ricei curvature- survature-based method to com- munity detection in complex networks. Scientific reports, 9(I): 2019.
Joshua B. Tenenbaum, Vin de Silva, and John C. Langford. A global geometric framework for non- linear dimensionality reduction. Science, 290655500:23319-2333 2000. doi: 10.1 26/////encee.29// 5500.2319. URL https: wttp///www//.o/ www.sceieee.... org http://aaaa.....///iiiee....ee 29C. 5500. 2319
The GUDHI Project GUDHI User and Reference Manual. GUDHI Editorial Board, 3.1.1 edition, 2020. URL htt.hhttt://guuee inria. fttiia..ffdoooooo fr/doc/3.1.11
12

---

Published as a conference paper at ICLR 2025
Yu Tian, Zachary Lubberts, and Melanie Weber. Curvature-based clustering graphs. arXiv preprint arXiv:2307.10155. 2023.
Alex Tsun. Probability & statistics with applications to computing, 2020.
Pim van der Hoor, William Cunningham, Gabor Lippner, Carlo Trugenberger, and Dmitri Kri- oukov. Ollivier-Rieci curvature convergence in random geometric graphs. Physical Review Re- search, 3(1):013211, 2021.
Laurens Van der Maaten and Geoffrey Hinton. Visualizing data using t-SNE. Journal of machine learning research, 9(11), 2008.
Tian Xia, Jintao Li, Yongdong Zhang, and Sheng Tang. more topologically stable locally linear embedding algorithm based on Rtetree. In Pacific-Asia Conference on Knowledge Discovery and Data Mining. pp. 803-812. Springer. 2008
Richard Zemel and Miguel Carreira-Perpiiaa Proximity graphs for clustering and manifold learn- ing. In L. Saul, Y. Weiss, and L. Bottou (eds.), Advances in Neural Information Processing Sys- lems, volume 17. MIT Press, 2004. URL
www. cc/pppeerr
Yubin Zhan, Jianping Yin, Xinwang Liu, and Guomin Zhang. Adaptive neighborhood select based on local linearity for nonlinear dimensionality reduction. In Advances in Computation and In- telligence: 4th International Symposium, ISICA 2009 Huangshi, China, Ocotober 23-25, 2009 Proceedings 4, pp. 337-348. Springer, 2009.
A APPENDIX
A.1
REPRODUCIBILLITY STATEMENT
Theoretical Results:
We detail global assumptions for all theoretical results in Section 3 also make a concerted effort to clarify all proof-specific assumptions in the Theorem, Lemma and Proposition statements.
We
To ensure the reproducibility of our experimental results we release the source code for ORC-MANL and the scripts for reproducing all experiments Included in the experiment scripts are the parameters used: for clarity we describe key parameter choices throughout the body of the paper, and provide extra details in Appendix A.3
Experimental Results:
A.2 ORC-MANL TIME COMPLEXITY
ARC-MANL consists of two sequential stages. In the first stage the ORC of each edge is evaluated. According to Fesser & Weber (2024) such an operation has complexity O(EE) ( where dmax indicates the highest node degree in the graph. Assuming k-NN connectivity (which is commonplace in practice), we have dmax = (k) and E = ( This means the first stage of the algorithm has complexity (((V The second stage of the ORC-MANL algorithm requires one find the shortest path distance de (x., y) between the endpoints of all candidate edges (I., y) E C' in the ORC thresholded graph G¹. With naive implementation of Dijkstra's 's algorithm the time complexity is (ICT]V))?) but efficient implementations admit a time complexity of [[C[]V log [V]). Finally since C C and [E| = O(V(kk) the time complexity of the second stage of ORC-MANL scales as (2 [V[).
The total time complexity of the ORC-MANL algorithm therefore scales O(IVI==) + (o [V]). Seeing as many geometric data analysis algorithms (c.g.. PCA) require eigen- decompositions that scale as ((VV)) we consider the runtime ORC-MANL be reasonable. For empirical evidence to support this claim, we provide experiments that compare the wall-clock time of ORC-MANL and UMAP for the Swiss Roll in Figure TO For this experiment, both algo- rithms were run 16-core machine with 187 GB of RAM. We use the UMAP implementation from Mcinnes et al. 8b) and the ORC implementation from Ni et al. 2019), both of which use
https:: / thub. com stanSa di /orcm1
13

---

Published as a conference paper at ICLR 2025
ORCManL
600
UMAP
400
Wall
200
100
0
5000
10000
15000
20000
25000
30000
Number points
Figure 10: Wall clock time of the ORC-MANL algorithm and the UMAP algorithm for the noisy Swiss Roll dataset of varying size.
multiprocessing. We see that in this range ORC-MANL runs substantially faster than UMAP and appears to have slower asymptotic growth.
A.3 EXPERIMENTAL DETAILS
For all experiments in Section 4.1 datapoints sampled according to defined in eq. ( for each synthetic manifold M. To achieve this, we sample uniformly from the underlying m-dimensional manifold M (unless otherwise specified) driven by the m-dimensional volume form defined by the Euclidean metric. We then use rejection sampling to obtain isotropic Gaussian noise E NN(0,, I) such that ||El|2 our theoretical analysis assumes e-radius connectivity, e-radius connectivity is more challenging to tune in practice. Since l--NN graphs are more commonplace in the applied literature, we opt to present results on k-NN graphs (unless otherwise specified).
For all experiments detailed in Section 4.1 we use k-NN connectivity; while
A.3.1 PRUNING
Here detail each of the pruning baselines that appear in Table
1. ORC ONLY:
This baseline returns graph G' where edges with curvature less than -1 4(1 5) are removed, but no additional validation step is undertaken. Namely, Algorithm is terminated at line 7 and the graph G' is returned.
2. BISECTION: This method was proposed by Xia et al. (2008) address topological instabil-
ity associated with the Isomap algorithm (Tenenbaum et al. 2000). For each edge (æ,, v), it performs local search around the midpoint -= (x + y) /2 Namely, searches bounding box I [4 - 4 4 e'] for a neighboring point, where is the average distance of and their Rois nearest neighbors. If point exists in the bounding box, the edge is removed.
3. MST: This method was proposed by Zemel & Carreira-Perpiiae (2004) and simplified by Chao et al. (2006). In essence, this leverages the insight that shortcutting edges empirically exhibit longer edge length than their non-shortcutting counterparts (though neither paper presented any theoretical justification for such claims). The method builds a Minimum- Spanning Tree (MST) T of the original graph G with Kruskal's ''s algorithm (Kruskal 1956). The edges in this MST are removed to obtain G' = (V, E \ T), from which one obtains another MST 7'. Finally, and T' are combined get G" If for any edge (æ, y) in G the
14

---

Published as a conference paper at ICLR 2025
graph shortest path distance in G" is larger than some manually set threshold dMST, then it is removed.
4. DENSITY: While similar in theme BISECTION, DENSITY uses explicit kernel density estimation inspired by CCao et al. (0077. For this baseline, we estimate the density at the midpoint of all edges, and remove edges that exhibit especially low density (based on some manually tuned threshold Pmin).
5. DISTANCE: This baseline simply removes the longest edges based on some manually tuned threshold ddist-
We note that for manifolds with single connected component, we estimate edge labels (shortcut versus non-shortcut) by checking whether the ratio of the manifold distance to the Fuclidean distance is large for denser noiseless sample. For reproducibility we include noise parameters used for manifold sampling in Table We also include algorithm parameters for the baselines Table 3 As mentioned earlier in the body of the paper, all ORC-MAND experiments use å 0.8 and X 0.01. Similarly, all ORC ONLY experiments use = 0.8 as well.
Table Manifold noise parameters т and for each manifold used in the pruning evaluation (Fig- ure
M
Concentric Circles
0.28
0.09
Mix. of Gaussians
0.45
0.18
Moons
0.19
0.20
curve
0.52
0.28
Cassini
0. 135
0.05
Tori
0.75
0.4
Hyperboloids
0.25
0.20
Hyp. and Parab.
0.48
0.40
Paraboloids
0.70
0.60
Swiss Roll
2.25
6.25
Table 3: Algorithm parameters for each baseline and each manifold used in the pruning evaluation (Figure 4h.
M
lapis
dMST
Pmin
ddist
Concentric Circles
10
0.5
0.125
0.15
Mix. of Gaussians
0.3
0.15
0.15
Moons
10
0.5
0.175
0.15
curve
10
0.5
0.05
0.15
Cassini
10
0.5
0.20
0.09
Tori
10
1.5
0.0007
1.0
Hyperboloids
10
1.5
0.015
0.4
Hyp. and Parab.
10
0.75
0.015
0.4
Paraboloids
10
1.0
0.01
0.5
Swiss Roll
10
10
0,00005
3.0
A.3.2 PERSISTENCE DISTANCES
We compute distances between persistence diagrams using the approach presented in Lacombe et al. 2018). The p- Wasserstein distance is defined
dr D2)
min (cr((D).D)) (a.1)
Σ -
Σ
||8- (>))))
SED
where Dj and D2 are persistence diagrams represented as a set of points in R2. I(D,, Dz) is the set of all partial matchings between points in D, and points in D2, and (s()) denotes the orthogonal
15

---

Published as a conference paper at ICLR 2025
projection of unmatched point to the diagonal. We use The GUDHI Project (2020) to compute persistence distances with = oc.
A.3.3 INTRINSIC DIMENSION ESTIMATION
We use the maximum-likelihon based approach for estimating intrinsic dimension proposed in Levina & Bickel (0044). The method assumes the data points generated from homogeneous Poisson point process on a manifold. From there, they derive the maximum likelihood estimator for the intrinsic dimension m, with
log (x) Tj (x)
(x(x)
k
where (ar) represents the distance of a to its j-th nearest neighbor and k is user-chosen parameter. In our experiments, we report the meen-squared-eroo (MSE) between pointwise intrinsic dimension estimates and the base truth value for the underlying manifold. While it has been pointed out that the global intrinsic dimension estimate derived Levina & Bickel (2004) is biased, the pointwise extract nearest neighbors and nearest
estimators are, in fact, unbiased. For our experiments neighbor distances using the graph metric. We also use k 200 and n = 4000 (where n the number of points in the sample) for the experiments in Figure
A.3.4 SCALAR CURVATURE ESTIMATION
Scalar curvature assigns scalar quantity each point of Riemannian manifold. It is intimately related to the notion of sectional curvature through the equation S(x) = =Eizj Sec(e, ej), where Sec(-) is the sectional curvature and c1...., Cdt form an orthonormal basis of the manifold's 's tangent space at x. Note that for surfaces (manifolds with intrinsic dimension 2) the scalar curvature simply twice the Gaussian curvature. We use the algorithm from Hickok & Blumberg (2023) to estimate S(z). This method leverages the following result, which relates scalar curvature of an m dimensional manifold M to the volume of geodesic balls relative to Euclidean geodesic balls. It states,
S(x) (o)( C CM) = 6(d O(r*))
(o)(B,(0) C. IT)
for sufficiently small The method first builds nearest neighbor graph and uses the induced graph metric estimate geodesic ball volumes range of scales. From there point-wise estimate $ of scalar curvature can be produced via regression over the volume ratios over some range [0, rmax] In our experiments in Figure / we use 4000 points and Fmax 50 for the swiss roll and Fmax for the adjacent spheres.
A.4 PROOFS
A.4.1 THEOREMS
3.1
3.2
AND 3.3
In this first section we will detail the proof's of the theorem statements put forth in Section For clarity, recall the assumptions: we consider the setting where M a compact m-dimensional smooth submanifold of I2" without boundary. Let Tub, (M) be the tubular neighborhood of M, and assume X' C (Mb) consists of n independent draws from the probability density function p: Tub, (MM R,,,
p(z)
7
26
||z - projm æ112 S
0
o.w.
where Z is normalizing constant such that Srin, (M) P(2)dV integrates to 1. We are given the constant À < For the rest of the paper, suppose
1. (Support criteria): 2r e, 37 so(M), 37 <ro(M)
16

---

Published as a conference paper at ICLR 2025
2. (e-radius criterion); e < min (ss(M 7)2 -
- -) ro(M))
where (u( is the minimum branch separation of M and ru is the minimum radius of curva- ture of M. We can now begin to dissect the argument for Theorem 3.1
Theorem 3.1 (Ollivier- Rolici Curvature of Shortcut Edges). Suppose that X, is a point cloud sampled from p with parameters o; and Tú and G; is its nearest-neighhor graph. Also suppose that M satisfies the conditions above, and + 0+ and Ti - 0+ as - oc. Then as i + co, we have x(x,)) y) I -1 for all shortcut edges (z. y) in G, with probability approaching 1.
This theorem establishes that in the limit of vanishing noise, the ORC of shortcut edges is necessarily upper bounded by -1. The theorem stitches together Lemmas A.3 A.4 and A.1 Here is how we will approach it.
Simply put, one can show that all shortcut edges are necessarily close to a normal direction to the manifold at both endpoints; if this was not the case, the edge would likely intersect the manifold carlier and thus no longer bridge extremely distant neighborhoods. This concept is formalized and proven in Lemma A.3
Given that shortcut edges are close to normal, one can show that most of the measure of epsilon balls around the endpoints concentrates far from the opposing endpoint (assuming the pdf p described above). follows that the neighborhoods of x and y will tend to concentrate far from each other. An example visualization of this phenomenon provided in Figure [1
M
p
L
Be(x)
Be(y)
y
Figure 11: Visualizations of the e-balls at the endpoints of shortcut edge (ar, y).
This divergence between the neighborhoods of x and leads to a large Wasserstein distance between the neighborhoods, implying more negative ORC. This fact is formalized and shown in Lemma A.I With the high-level roadmap in place, we will proceed by proving Theorem 3.1
Proof of Theorem 3.1 Consider a sequence of point clouds { with n points each, where each point cloud was sampled from (defined in eq. (I)) with parameters o, and T, Also suppose or - 0 and T; +
+ oo. Consider the i-th pointcloud in this sequence, and let 2, and y, be any two points connected by a shortcut edge (if they exist).
Since (z,, y1) is a shortcut edge, we can apply Lemma A.3 find the vector Vas, E N Nproj x, M such that the angle dn. between Uz. and (v:: xI;) is less than
(T.)) arccos (ro(M) Ti) (so 7:) 1.277o ((M))(so(M))) - T;) +
< <\/2
(2)
and the angle 9, between (z; (r:-proj x.) and Uz; is less than T/ /2. In an identical manner, A.3 can be applied to find analogous quantities Ug., fg, and dy.- The fact that dz, and dy. are necessarily bounded by formalizes the notion that shortcut edges are necessarily oriented close to normal with respect the manifold at each endpoint.
17

---

Published as a conference paper at ICLR 2025
Now would like to say something about the degree to which the neighborhoods of I; and y likely to overlap. To do so, we define the sets Un, C (z,) and Uy. C (1)) such that for all a, b E Uz, Ug. ||a bll2 e. One particular instantiation of these sets is shown in Figure 12 For the analysis that follows we will consider this instantiation, namely the case where the boundary of Uz, is defined by hyperplane orthogonal to (y: x:2) (and Ug is defined analogously). In this instance, the sets Un, and Ug. are simply hyperspherical caps.
Un x
Ug y
L y
Be(x)
B.(y)
Figure 12: Visualization of the sets Uz and U, for an edge (z, y).
Now lets also define Pa., (x,) == Pla E Un, la E B.(x:)) and po, (2)) = Plbe 1n E (eii)).
We can use Lemma say
2 - 2 Vol(B (0))dz
Sa (dx,)
lim Po. (I,) 6,-01
Vol Rr. (0))
and
22 palli--rraia vall Vol(B Ty. (0) (0))
Lu. (dv,)
lim
Po. (Vi) 2
0.-0
Vol(BR (0))
where
c- ||,; Valla ) -11x; proju æil12 cos()2.)
=x see((d.)))
and
c- --11x1;- Mill2
Sv. =cot(o)) sec(())))
11 - proju vill2 cos( cos(
2
Note that R2:
Ve² ||,, projm
2i
and
V c
|
proj 2,
2
12 S
/e2
22 ||2
proj 24
(2)
otherwise
are defined in Lemma A.4 with analogous quantities defined for yt. Observe that the further the edge (Ia, ys) is from normal with respect to either endpoint (as measured by dha; and ). the smaller Po; (x;) and (y:) are respectively. This follows from the fact that fz, and fy, are increasing functions of dh, and dy, respectively. This can be confirmed by quick visual inspection of Figure
11 the further from normal (x y) is, the less probability density exists in Uº and Uy.
Now we will show that Sn; and [y are increasing in Φ.;; and dy, when in the interval (0, n m/2] (which always the case as shown in A.3 The derivative of cot(c) sec(c) 6) is (b cos(e)) sin (c). Note that the derivative positive on (0, π (2) when < b. From eq. (37) in Lemma A.3 we know that
||,; vill2 V(so(M) Tz)² ||0 proju 32ll3 sin
|| prooo sella coll2)
18

---

Published as a conference paper at ICLR 2025
The right-hand side is bounded from below by c- c-1la; 1-11la,-projj the fact that Ti 2 || - -rro 2:I12. Thus b = ||z, proj Tzil2 cos (0:) > e - ||2; - Yel12 2a, rendering the derivative positive. Since ((T:) is larger than all possible Φz. and dy. fz, ((())) 2 (#,,) and Ja (o(T:) 2 Lu. (dv.). allowing us to conclude that
cos due to assumption and
say
(2 ||z proia z.llž
(s) (0)
(0(T))
lim Po. (I,)
0:-+01
(ol Rr.
(0)
where an analogous bound holds for lim Po. (yt). Taking the limit as T; 0+ yields
lim lim Po. (1,))
(3)
To Tu o.+0+
2- proj-rroja M
(ol (z) (0)) (0))dz
La, (0(7))
lim
(4)
7 ++
Vol(B%,. (0))
Vol(Bm-) (0)) 1 2 far (8(T:)), ve 12; 1x, proju 2; 12
d2
00
(2)
lim T--01
Vol( Rz, (0))
(5)
(V V [|,, projm 2.113 Vol(B Sz, (lim, - ((r))) (2) (e)
(6)
Vol(B (0))
In the second line we can use the dominated convergence theorem to pull lim into the limits of the integral, since the integrand is bounded above by the integrable function Vol (00((B"--000 [-c, el] and bounded below by 0 TT, O. Now further evaluate
1[2 E
lim ((T:) = 4(0)
To +++
(o(M)ss(M))
= arccos ro(M)so(M))
0.
This implies lim, - Ja: (T(()) -oo since Jz: - -0 as argument approaches 0. Note fz, + its argument approaches 0 because - 0*, asec(c) - b cos(c) converges to - b (which we have established is strictly negative) and cot(c) converges to +oo. Now, since Tr, (z) in the integrand 6 is 0 for values less than 2
we can say that [ projm T. 2.
22 proju
Vol(Bm=11 Ta, (2) (0))dz
lim lim Po, (zi) 2
si pro. 2i
a--+0
Vol( (0)
Vol (BW, (0))
(8)
Vol B (0))
Note that the same argument can be used to prove the same equality Po, (v.) in the limit. Now we would like to use these results to make a statement about the number of neighbors that end up falling in either Uz, or Uy. for n i.i.d samples from with parameters a, and T, (eq. (T). Define the
sets Sz. = {a a E (Nx,,) n Uz, } and Sy, = {bl0 E N()))) n Uy. }- Also let No. [a(x,) vil and N₁, = (v.) \ xz/- We can say,
P[|s,,1 No. = Po, (2r) 2 Po. (I:)"
(10)
since No. S n. Through application 9 we can conclude
lim IP S.n.l = Nay = 1. <0000
(11)
19

---

Published as a conference paper at ICLR 2025
With the same argument, say
IP sy = =N 2 Po (u))
(12)
and thus,
lim P
| = -Ny1 1.
(13)
Now we want to use 10 and
12
to bound P||S2211 = No yt = N. Define az. = 11|[; =
NG.] and ay = 1[ - v.
We can apply a union bound to say
PP P(ar. 1, ag
21
E
P(az.: ayd]
Oz AIVo,
2 1
Σ
min P/a:
#VVo #1
1 min P ar. = 11, 1 - -P(ay, = =1]
min - Plux, = 1], Play, = 11}
min
Pl = 1], 1 Play = =11
Taking the limit and applying 11 and 13 yields
lim P Pla- 1, O2 = 1| =1.
10000
This result crystallizes the notion that, in the limit of vanishing noise, the neighborhoods of the endpoints of shortcut edges tend to concentrate very far from each other. To restate formally, we the limit.
have shown that F[SS,, No., |Sy.l Nyy approaches
Now we will apply Lemma A. to control the ORC of the edge (Iz, v.). The Lemma proves that IS Ny and SS,, o2 implies s(x,, y4) < -1+ 2(2 (d.. + oy.)). Combining
everything using 8z, = 6g. =
P[M(E.. & -1] 2 P P(a.. az. 1, 1,, =1]
and taking the limit,
lim P M( vi) S s-1- =1. 1+000
(14)
Since we have a finite number of edges and thus a finite number of shorteut edges, we can apply union bound to say that Equation (14) holds for all edges as + co.
Thus we have a result indicating the convergence of the ORC of shortcut edges to at most -1 in the limit of vanishing noise. To confident that ORC-MANL is truly effective, we would like to be able to say that under some conditions the ORC of non-shorteut edges tends to be less negative, or even positive. This motivates Theorem 3.2
Theorem 3.2 (Ollivier-Ricci Curvature of Non-Shorteut Edges). Let k be positive integer.
With high probability as the number of points n + J0, every point has at least k neighbors that it is connected to by non-shortcut edges with ORC
This theorem states that, as the number of points increases, every point has least non-shorteut incident edges with ORC arbitrarily close to +1 with high probability. We will outline high-level overview of the argument to prove this theorem before delving into the formal proof itself.
First, one should observe that the probability that any point has at least some finite number & of neighbors (independent of n) within a ball radius is increasing in n. An exact bound for this probability results directly from Proposition 4 One then construct sequence n, oo and 6, + 0 such that as goes to infinity, each point has at least & neighbors within distance 6, with high probability.
20

---

Published as a conference paper at ICLR 2025
From here, we want to consider the behavior of the ORC of edges connecting points some distance ó, as tends to infinity (and thus as ô; tends to 0). Proposition and Lemma A.2 in combination allow to show that the distance between two points tends to U. the ORC of the edge connecting them tends to +1 with high probability. From all of this it follows that as n tends to infinity, each
point has many arbitrarily close (and thus non-shorteutring) neighbors connected by an edge with ORC +1 with probability approaching 1. This wraps up the proof sketch.
Proof of Theorem 3.2 First will invoke Proposition say that for all Tub,
8 Vol (0))
P PIup ||= x112 so
c 2=2
2Z
C8
This result indicates that for any point in the tubular neighborhood, there is always nonzero probability that there exists a neighbor at distance at most 6, for > O. Now choose sequences {n and { where n, = and ò, = (C1))1/(2D) 1/(20)) Observe that n. + 0o, 6 + 0 and n,C6 00.
Now we would like to evaluate the probability of the existence of at least k neighbors within radius 6, for n, i.i.d. samples from p. We will use N&; to denote the random variable representing number of neighbors within 6, to some point given n; i.i.d. draws from p. Observe that Ns, is distributed according to Bin(n,, C8P). Thus, we can apply a Chernoff bound to say, for < y <
2n,08
P s (1 (1-7)mm (11-)),066) S exp
and thus,
C8,
P[N, > (1 - 7)m, exp
2
Tsun 2020
Replacing with 1 - C6, we obtain
nCCoP (1 k/(n,, (n,
P[N. > k| > exp
(15)
2
and taking the limit 00. lim P[Na, > k] =1
(16)
since n, n,C8 + 30.
We have established that if the radius 6, shrinks sufficiently slowly, the probability that any point has more than neighbors within this decreasing radius approaches as n, tends to infinity. Now we would like to use this result to make statement about the ORC of edges connecting a point and its neighbors within distance &; To do so, consider point æ and distances {8. such that 8, - O. static point in a sequence of nested point clouds, where each point cloud X;
We can consider is a union of the previous point cloud X;-1 and one more point sampled from Also for each i consider the set of neighbors {v/l vf E X. ve * o1y such that ||æ - s/ | S 5,; note that the earlier results indicate that (vv 1sl > l with probability PPNs, > k),, as described by 15
Let Let r.. (L())) ing themselves). Now define __. to be the neighbors of and yf that lay in Be(x) n (x( )- Finally, let Pa.yz = Pamp [a B. n B. (v()) E (x U B. (v: Observe that [S [ is a ran- dom variable distributed according to Bin ann... Pa.v!) when N Nr..p is fixed. Also note that .V itself is a random variable with a binomial distribution with n, trials. Observe that exhibits success probability p < 2 == C.e!, which follows from slight modification to the result of Proposition 4 Thus, E[N z.gz 2 i.'ep. Armed with this knowledge, define two more sequences
{z, s/ which denotes the set of all neighbors of and of (exclud-
k,, = vi and % = 1/8, We will return to these definitions shortly. First, we will apply Chernoff
bound say
(1 WW
P N = k) s exp
2
21

---

Published as a conference paper at ICLR 2025
and thus,
7
IP A 1 (1
Pz.o/
exp
PPN
P [N N2.0 k)
(17)
2.0
2
k=0
Σ
P[N ain!
P
exp
2
kēkp kPk..ot
+
exp
P
W N2vi k
2
S2
Sexp
1/2)
(18)
7/ Ks 1M I P <P(N n.y I kis + exp
(19)
2
We can apply one more Chernoff bound to bound the first term, resulting in
S exp (
B[N 2. 1(1 k///B/// 2.07 1)2
P[Is x,17 $ (1 - Ws
a. P.p.P.as Pa.v!
2
2 P..isPar.s ) (20)
+ cxp
2
We can apply Proposition 5 to say as + co, Pa.vf + 1.
Now since
+ 0, B(N m. - 00,
ks. /E[, mg + and kike
kis + oa, we have
lim P P < NN No.od = 0
(21)
and thus, since s2 S No Now
lim P || 2.16 = Na.ne!
+000
Now we can invoke Lemma A.2 and Proposition to say that |S ا = N NNa.: implies <<xz vt) = 1. Putting it all together, we see that
lim M(z v() = =1 =.
(22)
1). Now we want to use this to bound the probability that, for fixed i, subset of size lo of all Ns, neighbors have ORC of 1. To do so, let's denote of = [k([,, y/) = 1). Instead of considering all combinations create lower bound. Namely, we will cherry pick the first & indices (unless Ns, < k). Now observe that we can apply union bound to obtain
Now let p P[r(2, y/)
subsets of size k; we will just consider a single one to
P k(, v2) = j e [minfkk (k, No. H]
21
Σ
plat........
min (k: (23)
(1o1))21 E, of <min(k,NN,)
where the second term on the right-hand side sums over all settings of (a?) such that there ex- ists least one af taking the value Now can use the fact that P!, to say
Xn) 5
mixi
P ( = 1 14 E [minfk, No. 2
Σ
min Jelmin(K.N,,)
P[a.]. (24)
{(a)) E, of (min(k
22

---

Published as a conference paper at ICLR 2025
Now will take the limit as i + resulting in
lim P ((), = 1Aj e [kninkk Ns.
1 lim
Σ
min (e H
P P[a.]. (25)
[a
Σ; of <min
Since lim P[N6. k| and since the summation is over a finite number of terms,
lim IP [<(2, = 1 4A E [k]] 21-
Σ
lim min 1 JE min.
P[a[]. (26)
1000
Observe that the limit as goes to infinity, these Two expressions converge 1 and 0 respectively due eq. (22). Thus the limit can be pulled inside of the min function. Since we know that for each element of the sum there necessarily exists an ay = O, one of the arguments of the min function must be O. Thus,
Note Play = and =
lim IP (( = 1 v E [k]] =1. 1000
(27)
Note that for sufficiently large i, 2 and v cannot be shorteut edges as | v/ ll2 < so(M) which, in turn, implies (projjj z, v²) I. Tro(M). Finally, we can succinctly state the conclusion by saying that if grows sufficiently fast, every point has at least k non-shortcut neighbors such that the ORC is with high probability. This completes the proof.
Together, Theorems 3.1 and 3.2 establish that in the limit of vanishing noise and infinite points shortcut edges can be detected with complete accuracy. In practice though, may see too much noise or too few samples to rely on ORC alone. Therefore is interest to us to add another validation step. We do by looking shortest path graph distances in modified version of the original graph, one which has all especially negative curvature edges removed; we call this graph the 'thresholded' graph. Theorem 3.3 establishes that graph shortest paths between endpoints of what were shortcut edges in the original graph necessarily have a large graph distance in the thresholded graph. Figure 13 provides an intuitive visualization of this phenomenon.
GG'
YG
Figure 13:
Visualization of graph shortest paths between the endpoints of shorteut edge (ar, y)- The path TO denotes the path through G (which is trivially a single hop), while YC' denotes the path through the ORC thresholded graph, G'.
Theorem 3.3 (Filtered Graph Distance). Suppose that X, a point cloud sampled from p with parameters o; and and G; = (V,, E.) is its nearest neighbor graph. Also suppose that M satisfies the conditions above and a; + 0+ and T; - 0 as + Dc. Define the subgraph G², = (V,, E.) where
E = (Ix v.) E E, k(Zz, > -11.
23

---

Published as a conference paper at ICLR 2025
Then as i + we have
de {( + 1)(1 - 2)
2v24X
for all shortcut edges in G. with probability approaching where 3 [0, 1] (eq. 334 is random variable whose distribution is dependent on M and T4.
The proof of the theorem adopts the following strategy. Geodesic distances through the manifold M can be bounded as a function of geodesic distances through the tubular neighborhood T using Proposition 3 We can then pull from [Bersstei et al. (2001). which relates graph geodesics to manifold geodesics, bound graph distances through G' as a function of manifold distances M. The theorem can be concisely stated as showing that in the limit of vanishing noise, graph distances in G" between endpoints of (formerly) shortcut edges are necessarily very large.
Again suppose { is sequence of point clouds of size sampled from defined in eq. with parameters o, and Tú with o, + 0+ and T; - 0+ as - cc. Also suppose G, = (Vi, E.)) is the nearest neighbor graph built with parameter from the point cloud X, Consider the i-th pointcloud and nearest neighbor graph in this sequence, and let æ; and y, be any two points connected by shorteut edge (if they exist). Since (æi, 34) is shorteut edge in G2 have,
Proof of Theorem 3.3
d (projm Pt. pt.projm ui) > (T T)ro(M).
From Proposition we know this implies
d (Zi, y:) 2 ro(M) - -
(T 1)ro(M) ro(M)
(28)
(ro(M)- - -T=)(T 1).
(29)
Now consider the ORC thresholded graph Gj₁ = (Vi, ET), with edges
E [ E Es ((1,,")>
We can apply Theorem 3.1 to say that with high probability G² has no shortcut edges. With that in mind, select length minimizing path ag. ... a connecting x; to yi through the graph G² With high probability we have,
dm(proim af projm d(+1) s (t + 1)ro(M).
follows that (af, 4442) S (α + M))((M) + 2T, as M Tub,, if this wasn't 't true, the shortest path through the tubular neighborhood would instead take the path traversed by M through projm at projm a:+1- Now we can say,
d (at, a(+1) s (N l)ro(M) 2T.
Consider the p' of the p hops along this path where
dn a(42) s m(ro(M)- -
Note that from Proposition I we know that the minimum radius of curvature of geodesics in the tubular neighborhood MM) - тG. Now we can invoke the first-order weakening Lemma from Bernstein et al. 2001 with ro ro(M) Ti say
2
d (0), a(41) S |1 - af41ll2
2 (ro(M) - T2)
where the second line follows from assumption 2 Solving for À we get
1
d dau a(t1)
A >
24
ro(M)
24

---

Published as a conference paper at ICLR 2025
and therefore
- 1 1 (duublat.
24 ro(M)
Finally can apply the weakened form of the same Lemma from Bernstein al. (2001) say
drubla;; (411) 2) (1 A)dTab a/411) (1 24 ro(M) - Tj d a(41)
I ||a| - d2+1ll2.
Now consider the other (p 1) 1--1p/ hops, where we know
drub(a d(+1)) > T(ro(M) T.).
We can apply the definition of minimum branch separation say that || | > (T)
In general deriving an expression for the right-hand side terms ro (M) and so (MM is impossible without more information about the embedding of M. Thus, we will proceed without breaking down so MM) We have,
|a alt1ll2 2 so(Tubr,
(30)
so (o(Tub,. ( 1)ra(M) 2T;
dubb, (a a1+1).
(31)
Now we can combine the bounds on ||at aftill2 to say
8o Mu..,.) drub, (a), d(42)
(o Mi) > 11)) Σ draa a(+2)
(32)
( + ()r((M) 2T;
> (1 - X) Σ dnub(a a()))
(33)
where the set of all hops with tubular distance at most (M) - Tz), and L is the set of all remaining hops. Defining
B Es dnnn a(t1)
(34)
(T,n y1)
allows us to say
da (2i,, vi)
> 8(1 - A)dTub V/i)
2 8 {)(ro(M) - [x + 1)
and seeing as we have stipulated that (ro(M)) - T)2 in assumption 2 we can say
dc;(I,,M)) T(T 1)(1 1)
(35)
2/24da
with high probability.
A.4.2 LEMMATA
In this section, we will prove the lemmas used by Theorems 3.1 3.2 and 3.3
Lemmas A.1 and A.2
simply bound (from above and below, respectively) the ORC of an edge based on the locations of each endpoints neighbors. Lemma A. considers the scenario where some subset of the neighbor- hoods of and y are positioned in the sets U, and Uy, respectively (where U, and U, are defined according to Figure 12p. The large distance between U, and y (and vice versa) allows one to lower bound the Wasserstein distance between Nt and py, and thus upper bound the ORC of (a, (z.
Lemma A.1. Let (I, be an edge in a nearest neighbor graph built from potentially noisy samples of M, suppose U2 and Ug are defined as in 12 Define Sz {al E N(xx n Un} and S, {blb E (N(y) n Uy}, and suppose that
SSa
|S by = (W(v)
8_- = [(x) YOH
[사}]'
25

---

Published as a conference paper at ICLR 2025
Then,
x(a, v) - -1+2 (6x + t,,)
Proof. We are interested in bounding the ORC of the edge (x. v) from above. Recall that we have defined ORC to use the unweighted graph metric in Section 2.3 To bound the ORC we need to bound the Wasserstein distance between Me and My. where Me uniform measure on the set (x)) {u} {v V do( v) c v. o x} and My is uniform measure on the set (y) {a} = (u v dc(y. G f y).
Let's define Pe and By as uniform probability measures over Sp and S, respectively, We can bound the Wasserstein distance between pe and My
W(M My) 2 W(Es (yy ((2..12) - W Hy).
Since ||a bl22 > e for all a E SS and for all b Sy. we know that (a b) for all S₂ and for all b E Sy. Thus, lower bound on the first term follows,
W W(as Bay 2.
Now we would like to bound W(2 Ma) from above. There is 1/[W(x)) \ {n}1 mass each node a E supp( while there is (/x) \ {yHl mass on each E supp(ūz). We can define feasible transport plan that transports all excess supp(uz) \ supp(ūz). Since the Wasserstein distance minimizes over all possible transport plans, the Wasserstein cost for this transport plan will upper bound the true distance.
a' E supp(ūz) to the nodes
The excess mass on any a' E supp(iz) is exactly
8 (xx fuH [(x) \ [
which means the total mass that needs to be transported is
1 &.)(() \ fiHll (.1V \ {i)l (V(x)) \ (
- 8z
We also know that from any a' E sup to any suрр()*) there exists length path through the node x. Therefore, (a a') < 2. We can then conclude
W(Ans Mx) s 2(1 5z).
With the same argument, the following bound also be derived, W W(g Myy S 2(1 8y).
Putting all together,
W 2 2- 2(2 (5_ + +8))
Solving for the ORC,
2 2 2-2(2- - (82 + 8y))
<(x, v) $1
1
= = + =-1 2 (5 8y))
Now we can adopt a similar argument to tackle Lemma A.2 Now we are interested in lower bound- ing the ORC based on the neighborhood structure. this scenario, we replace the sets U2 and Ug, with a (x) n (y). Each neighbor of an endpoint (x) that is positioned in this set is necessarily neighbor of the other (y). Therefore if many nodes are present in this set, then many of the neigh- bors of x and y are shared. An upper bound on the Wasserstein distance between μa and Hy follows, which implies a lower bound on the ORC of the edge (z, y).
26

---

Published as a conference paper at ICLR 2025
Lemma A.2. Let (I, y) be an edge in a nearest neighbor graph built from potentially noisy samples of M, and define Sa.y = {a (xx) n (xx)). Suppose that
|5
15
82
by
[W(x) {FH'
[W()) {tH
Then,
<(x, 2 1 2(2 - (62 + 8,))
Proof. We will adopt a very similar argument as that of the proof for Lemma A.1 We are interested
in bounding the ORC of the edge (z, y) from below. Doing so involves bounding the Wasserstein
distance between Hs and Hy: where Ae is a uniform measure on the set .(xx) {u} = {u e
dd(xx,) S e, v + y, v * x} and My is a uniform measure on the set N {œ} = {o E
V da(y,)) v) I 6, v * I. u # y)- Again recall that we have defined ORC to use the unweighted graph metric in Section 2.3
Define Aa,y to be the uniform probability measure over Sz. We can bound the Wasserstein distance between Me and My as
W WHans S W (Hans (nyy) + W (Pz.en Hy).
Now we would like to bound W (e..y) from above. There is 1/[W(z) \ KuHl mass on each node supp(us). while there 1/0z[N((a) \ {y}l mass on each a' E supp(Ae.y) We can define a feasible transport plan that transports all excess mass on a' supp(Ar..) to the nodes supp(uz) gu)p((z..) Since the Wasserstein distance minimizes over all possible transport plans, the Wasserstein cost for this transport plan will upper bound W W(Mx; (2
The excess mass on any a' E supp(fa.) is exactly
8 (x)) fuHl [W(x) [v)l
which means the total mass that needs to be transported is
1
&((()) \ fHHl (.(1((2)) {HHl [V(x)) \ (aH))
- 8y
We also know that from any a' supp((in.) to any supp(u>) there exists length 2 path through the node æ. Therefore, da b) S 2. We can then conclude
W ((z, ( S 2(1 5z)-
With the same argument, the following bound can also be derived,
W W(pay Mby S 22(1 6y).
Putting it all together,
W 22(2 - (6.g + 8y)).
Solving for the ORC,
<(I,y) 2 1 2(2 - (6, + 6n))
1 2 (8, + 8y))
Moving on, Lemma A.3 and Lemma A.4 constitue a majority of the theoretical work of this paper. Together, they show that most of the measure in the e-ball of point connected by shorteut edge
27

---

Published as a conference paper at ICLR 2025
to y tends to concentrate far from y. For context, Theorem 3.1 uses this fact in conjunction with Lemma A.I to show that the ORC of shortcut edges is necessarily very negative.
To set the stage, Lemma A.3 establishes two things. First, and most importantly, it shows that shortcut edge is necessarily oriented close to a normal direction a to the manifold at its endpoints. This concept is rather intuitive; if shorteut edges were closer to tangential directions instead, then these edges would intersect with the manifold prematurely, no longer bridging distant neighborhoods and contradicting their status as shorteuts. The second property the lemma establishes the fact that the residual of the projection (onto .M) of an endpoint æ of a shortcut edge must be within //2 radians of the aforementioned normal direction u. Put simply. this means that the endpoints of a shortcut edge are necessarily displaced off the manifold in the direction of or orthogonal to the normal direction that the edge itself spans. This simply arises from the assumptions about the size of relative to the manifold embedding parameters ro (M) and (MM) We show this second property holds it simplifies some of the downstream calculations.
Lemma A.3. If edge (z. y) in nearest neighbor graph built from potentially noisy samples of M is a shoricul edge then
1. there exists a unit vector v E Nproi a.M (the normal space of M projm x) such that the angle e between v and (y I) is smaller thun
(ro(M)) - (so( -) -12 < 1/2
arccos
(36)
(((M)((Bo()))) - 7)² -
2. the angle 0 between e and (x - proj x) is at most π 7/2.
Proof. Observe that the vector (y 2) can be written as our + 3v, where uy is unit vector Tproi M, while e is a unit vector E MMM This vector is in fact the unit vector in N Nproj, MM that minimizes the angle Φi to (y - z). Motivated by this, Figure 14 visualizes the dimensional subspace spanned by the vectors ur, e and (æ projm Φ). This visualization lays the conceptual foundation that the rest of the proof rests on.
First, we will show (2) holds, as is helpful in showing (I). To do so, we will show that the geometry of shortcutting edges implies bound on || - yll as a function of 0. We will then show that this bound violates the assumptions on the size of E for 0 2 T/2.
Since (z. y) shorteut edge, dproroj 2, projm 8) > (N 1)ro(M) Tr)(M). By the definition of minimum branch separation, we know then || projm I - proj. ull2 2 so(M). Now consider the triangle defined by the endpoints projm u, prooj y and y. We can apply the triangle inequality to say
projm x - -ll2 2 projj x projm vll2 projj --ran--llll vll2
2 (o(M) T
since 2
|| proj y 2/22. Now consider the triangle defined by the endpoints y, proj x and y', where y is the orthogonal projection of y onto the subspace spanned by v and (y - x) centered at projm x (shown in Figure 14p. Note that
1lg - -propo x112 2 V projm x - y113 - || - proj m x sin²
2 (s((M) - 7)² - || projm x1 sin (0).
Finally, consider the triangle defined by the endpoints proj x, 3/ and x', where x' is the orthogonal projection of onto v. Observe that - æ||2 = ||x - proj æ|12 cos(O) and ||ا - 22lla ||z - 2/l2. The second equivalence stems from the fact that the vectors v and by were chosen specifically so that they can be linearly combined to get (y - .r;; it follows that x' y/ is the same as x y. With that in mind, we can apply the triangle inequality again to say
| vlla 2 V (so(M) 7)2 || -proju x=12 sin (0) || -projM cos( (37)
28

---

Published as a conference paper at ICLR 2025
y
proju
v
UT
Figure 14: A visualization the plane spanned by the vectors (y - x) and v, and related quantities.
Property (2) follows from the prescribed upper bound, ||x 8112 S V(su(M) 7)2 -2 from
assumption 2 Thus,
((v((M) -)2 72 ((so(M) r)² || proju x113 1|x- projm 2|12 cos.
Solving for 0,
(so(M) - - -2 2||x1 proim 2212 cos(O) (so(MM) - -)2 - 72 + || projm æ112 cos²(0)
2 (so(M) -)2 - -1x a---roojm x0 sin (0)
(so(M) - 7)² -2 + +|11x Projm 2112 cos(O)) (so(M) -7)-
2 (8o(M) - -7)² - -1 - -eroojjm x1/2
Rearranging little more,
2|xx - proju x|12 cos(O) (Bo(M)
(BO((M) - 7) 72 2 7² || projm x1/2
|| projm x1/
cos(0) 2
2 r - proim x||2 (50 (M) -2
thus,
72 || - x112
0 < arccos
2|| 2ro 7)2
< ar)cos(O)
Since - projj 211e S r. This concludes the proof of (2).
Now we will show (1). At high level, we will show that the angle not smaller than the listed threshold, y must have small Euclidean distance to small neighborhood around a; for points in this neighborhood, the manifold distance to the projection of is large. This leads a contradiction stemming from violation of the minimum branch separation of M.
We will first show that Φ < 7/2 with a simple instantiation of the argument above. We will then proceed to refine the result to establish that ó is actually upper bounded by 36 a complicated function of manifold parameters.
Regime 1: E [m/2, m]. First we will show that for any & in this range, we have violation of minimum branch separation due to proximity between y and proju x. First we will derive || projm x - y" (where y" is the projection of onto the plane spanned by v and x proj x, shown in Figure 15). Consider the triangle with endpoints proj 2, y" and the projection of y onto the v, ur plane. We can use the triangle inequality to get
projm y"112
-V(1E
[| -prpjo x|I2 cos + | - 2/12 cos(o) + || - proj x sin (in
=
=VIl= -i-pprojim 2112 + 2| - proj a1||2|> Ul12 cos(() cos( + || v11 cos?
29

---

Published as a conference paper at ICLR 2025
Now can solve for proj. vll2 by looking the triangle with endpoints proj. 2, y and y" as follows,
projus - 8/12
projm x 12 + 1 u112 (Φ)
1x projm < 2|| projm 0||2||æ y cos(() cos(o) + | y
Note that
| projm x yll2 is decreasing in ø for ø E .T. Rearranging and solving for @ yields,
projm I -- - æ proj 2
arccos
2 - projM x x1|2|| x y cos
Now let
T,2 | projm x13
| y
f(L) arccos
2||x projm x 21|2 2112 cos
We will evaluate f(L) for L = so(M) so (M - T, we have contradiction. Since proju x - y/I2 is decreasing Φ, we know that for all f(L), projm vllz so(M) Evaluating f at so(M)
We will then show shortly that if L is less than
[(so(M) - -)) = arccos (so(M) - -)² || projm x
2| proj 27 2| u/12
cos
Now let's upper bound f(so(M) -) as means to simplify. Since arccos is decreasing on (-1,1)
(Bo(M) 7) - | projuu x || - v113
(88(MM - 7) = arcoos
2|1x - proj M x1|2| æ v112 cOs
(so(M) =)² 7² (V(so(M) r)² -72) )
arccos
Assumption 2
2||x - proj m 0||2||x0 vl12 cos(O)
(so(M) 7) 72 (so(M) 7)2 + 72
arccos
2||1 projm x||2||0 ul12 cos(O)
arccos(O)
= n/2.
Since (s) - 7) < π 7/2, we can say that for all Φ Z 7/2> f(s((M) - -)), proj x Ullz MM Observe that, since (æ. y) is shortcut edge d I. sroproj y) (n + ()ro(M) > (T). From the definition minimum branch separation, we know that this implies ||proj x projm w/12 (MM) Now let's apply the triangle inequality,
projo I - ulla 2 projj proj ulla proj y yl12
2 so(M) T.
Thus, for é 2 7/2 we have contradiction stemming from violation of minimum branch separa- tion. We therefore know that & cannot exist in the interval [T/2, n].
Regime 2: e E x2)). While the previous result gives us a bound on é. we can sharpen it further. Since we are dealing with manifolds without boundary, we can use the exponential map expproi to send the tangent vector er to a geodesic are of M denoted 7. Again we will show that @ is sufficiently large, then the distance from y to y violates the minimum branch separation in the same manner as we saw in Regime I.
Consider the particular scenario where curls away from y maximally. We will approximate near proj x with its osculating circle C: a circle contained in the plane spanned by vy and (y proj .)) with the smallest possible radius of curvature, (M). This particular instantiation is shown in Figure [5] Note that C' approximates a geodesic are passing through proj x with initial velocity ur and curls away from y maximally. Thus the distance between all possible geodesic ares
30

---

Published as a conference paper at ICLR 2025
L
y
proju
v
y
Mo(
UT
Figure 15: A visualization of the plane spanned by the vectors (y - x) and v, and related quantities.
passing through projm æ with velocity vector ey is approximately bounded by the distance between C' and y.
Now we want to derive an expression for the distance between C and y; this distance will be denoted d. We will start by deriving proj -y"" (where y" is the projection of y onto the plane spanned by and x projm I, shown in Figure 15). Consider the triangle defined by projM 4; y" and the projection of y" onto the er plane and apply the Pythagorean theorem say
projm v2112
(38)
=
(ILe projm 2/12 cos(O) + | u|ا2 cos( || projm 2112sin (0)
(39)
-11 [|e--rojjm 2112 + 2| proj =||2||= ||= Ul12 cos(() (f) cos(o) + || e11 cos2(())
(40)
Now consider the triangle defined by the center of the osculating cirele C, y" and y. We solve for + (oM as,
d + ro(M ( x v2ll2 (1
ro(M)) + || sin)
Squaring both sides and plugging in eq. (40) yields the following for the right hand side,
(Il (1 x 1/'12 + ro(M)) || - y112 (e)
(41)
= =I|proj x - 5/ 2ro(MM) ptol://ooouu 1'1l2 + (2) + -|-- - vilă (Φ)
(42)
||æ--roija 2113 + 21| proiu x 2/12 cos cos( + || =11 cos 2
+ 2ro(M)
(43)
V Iee propooo =13 + 2||= proju 2//2|1> vll2 cos(()cos(()) cos || v11 cos
+ ro(M)² + || v1 cos
|| 20oin=013 2|| proi 2||2||= v/12 cos(()))) + || vlا + (M)
+ 2ro(M) ||+ projm x112 + 2||x - proju +||2||> - v/12 cos cos( + || - w113 cos)
(44)
Observe that (d+ (d+ro (d) is decreasing in & on the interval Φ E (0, x/2) since cos 2 0, cos( decreasing on (0, π) and cos)(o) is decreasing on (0, a/2). To establish the contradiction we want to find the Ø' (0, n 7/2) such that d = so(M) 7; from that, know that for any á d'
31

---

Published as a conference paper at ICLR 2025
< so(M) T. Rearranging 44 slightly yields
(1 (d+ro)M) 2 - || u1 ra(
|1- - projoo 21ل + 2|| projm 2112|>> ulle cos(() cos(Ø)
23
2ro(M) v | - projm 21ا + 2||0 - projm 2||2||= - u|12 cos(0) cos(e) + || - U|6 cos (0).
Using these intermediate terms and defining 2 = cos we see
c C2 + Cz2 cav c2 032 c32?.
Rearranging to get a quadratic polynomial gives
2
(a- -2) - 032 - = o 0zz +32+
(a1 - 02)² 203(01 - 02)2 + tz2 = = Go2 + Gesz + cdos²
- (c1 - - + (20s(e1 - 02) + c/(3)) 2 - ( - Gos =-
Applying the quadratic formula,
(20a(c)- 02) + cGcs) + (200((1-c2)= 2
02) o2)+cc(0)
+4 +c(ctcs - ( (0)
2 c/tss dg)
(45)
Evaluating the denominator gives
2 2(cics c3) = 2 -4 -4|2 proj. x =12110= 21ا colccos21 co) + 4ro(M)))lI - v113
(46)
=8 61-11x - -orojpooii- =1 vll2 cos2 + ro(M))]1= - 2113
(47)
= 8|1a v1l (ro(M)2 - || proju 2 cos?(()) (0))
(48)
Evaluating the first term of the numerator,
20g 02)
4|| projm x/|2/1= - 2/12 cos(0)
(ld+ - -| v1l ro(M) - ||x - projjm m =113)
= 4 projm æ 0||2||> v/l2 cos(() (d² 2dro(M || -v12 -1x projm =11))
evaluating the second term of the numerator,
c2 = (ro( projm æ||2||0 - cos(
and combining,
2c1(c1 -c)) +z) cccs 41|x proj 2||2||> - ul12 cos(() (d² 2dro(MM
||
v1l2
||
projm a112 + 2ro(M)²)
(49)
Now we will evaluate terms inside of the square root in 45 Note that the first term is 49 while the second term includes two times (48). The remaining part of the second term is
squared,
(ci 02)² -c²02- = (dl 2dro(M) || - 1 || - proim x012)
4ro(M))?l -art)ll--poooo--m 1112. (50)
32

---

Published as a conference paper at ICLR 2025
Combining everything inside the square root yields,
16|| projm 2 =|[ā|| - yll2 cos²(0)
[[ 2dro(drr)))) - -1| 3112 - | projm ==13) 2T0(M))²
[16|/ -11ll1 projo x: 1 cos2(())) (0) 16|| - v)12ro(M)²
[(de (d) | --1 || - projm 1 <113) ( 2
16||z proj M <112|>> v1l2 cos c d + 2dr - -1|x vll2 - || -proju =113)
+ 64|1 proju M x | قاا cos cos² (0)ro & (Mdo((M) || || 1 || projur x1
+
projor x cos2 (0)
- 1661/= projprroi
v1ل cos cos) d² + 2dro(M) - || v112 - 11 proj a113)
+44||= -1 Proju 2112 cos (0))
+ 16|| - u1l vl (8 + 2dro( - || - =1l2 - || projm <113) 2
- 64|| yl (M) -proj 2112.
Continuing to simplify yields
16||= - vl ( 2drulM - -|0 - v112 - || - proj 2: =11 2
+ 4|| proim 2ll_cos cos) (0) (de + 2dro(M) - || 211² - || pprpioi
+ 4ro 1| - proj 201 cos)(
-AroMM)²lx= proim x11
+ 4|| projm x (012200s(00)) (0)] (51)
Now we will complete the square in the large bracket of of
& + (dro(M) - || v1l2 - || projm x=(3)
+ 4/10 - projm =112 cos 2 (0) (82 + 2dro(M ||00 - v112 1| - projuu =113)
+ 4cos (0)l2 l proj 2112 - 4 cos "o (0)]l - proj 211/
(52)
+ 4ro(M)) proj_ x cos
-4ro(M)² proj =11
- =012 cos (0)-
Now the first three terms and last four terms can be factored,
(00 + 2dro(M) - ||2 vIl22 - || -projo =11) + 2 c0))(() - projo x
(c0s+(0)]l== - projuu 2112
(53)
+ 4ro(M))21 pmoju 21 (0)
-Aro(M)²l1= - proj x113
+41l projou 20133 cos (0).
33

---

Published as a conference paper at ICLR 2025
Further simplifying,
(( 2dro(M) - -| v112 - || -proo x=13) 2c (0) proju m1/
411 --proo x/12
(54)
(11 proju z cos cos + ro(M || proju =112 cos
(d 2dro(M - || E1 || projm =11š) + 2 cos cos proju x12
(55)
4|2 proju z1l ( sin || proj M 2113 cos sin)
& + Mdro(M - || E1 || proju =112) + 2 cos projm x
(56)
| - -projm x 112 (isinn(0)
(ro(M)2 - || projm 211 cos
62
where the two intermediate steps leverage the fact that 1 cos? (0) sin sin)( The equation 45 has
two roots, and one of the two will result in a term on the right-hand side of that is positive (since the denominator necessarily positive); on the interval é E (0, x/2). We want to find a o' such that for all Φ > &' d < s0(M) T.
will consider this root. Recall that d is decreasing in
suffices then find an upper bound for d', which implies finding a lower bound on cos(Ø").
Let's denote 56 with B, and recall that it represents the expression in the large bracket 51 Also recall that 51 is simplified version of the term the radical of We can express the square root of 51 with 4 a vllero(M) B. Observe that B be written va² b2 where a, b > 0.
Since v 63 2 aa-bll for b > can say
> vllero(M)VB
41|x - vil-vllro(M ((e+ (2do((M) - v112 || proju =113]
(57)
+ cos² (0) projm x112
- 2|| projur x|12 sin (0)( ro(M2 || - projm x112 cos)(
Note that the following steps will demonstrate a- 0. justifying the previous step when evaluating so(M) T. Note that
d | v112 ||x proim 0112 (so(M) -7)² - ||x v112 || proj 26 2=12 2 (su(M) - -r)² (V(so(M) - 7)2 - 72)2 - 7
(58)
(59)
(60)
Thus,
a - b2 2(s0(M) 7)) + c00s2 proim
(61)
2|| proiu 2/12 (in ro(M)2 - ||. -projm x11 cos)(
2 ( - ()) 2Tr.(M).
(62)
Note that the last term is necessarily positive since we have stipulated that so(M) 3r. In fact,
> 2h, fact that to sharpen the bound Va² 1 2 b. When 2h, V - 12
34

---

Published as a conference paper at ICLR 2025
0.27b, which can be verified easily by plugging in and bounding. Thus,
4|1x - -lle)r(MMM)V
2 411 - (--lllrr(oM ((1 (d
2dro(M) +ddrl() || - vllă || - projm x(
(63)
+ 2 2cos (0)]l= projm 2
- -0.54| projm 2||2 (in ro( || - projm x cos
Now we will evaluate a hound on one of the roots of 45 by combining 63
49 and 48
(r(lM) - || propm x|12 cos
& 2dro(M) - || - --ll || - projm x113
2||x ul12 (M) ||x - projm x1 coo)(()))
-2ro(M)llz= projm 2112
2 2| uاا ro(M)) - -1|00 - 1po--poojm x112 cos
(ro(M)cos(00) projm x||2 cos (.) To || --roii x112 cos)
(64)
Bounding the numerator of the second term from below (since the denominator is nonnegative),
-2ro(M)lle proju 2|l2 (r((M) cos(0) || - proju # (0)
- 0.27 0.27 (027sin(0) 1|x - proim cos
(65)
2 -2r((M) (ro(M) (000M))002770MMM)
(66)
Now we will bound the numerator of the first term from below. We can apply the lower bound from 60 with d evaluated at so(M) - T to get
(ro(M) || - projom æll2 cO)(
(67)
((s((M) 7)2 + 2dro(M) - -1|x -11--~10 1-33-133 - || projm x113)
2 (ro(M) - (2(0 - r)ro(M))
(68)
= 2(ro(M) - (so( r))o(M).
(69)
Putting it all together, we get
z 2(ro(M (so(M)) ()r 2.5
(70)
2/x0 - 8/12 ro(M)) 1|x - proj.M 1/13 cos?
(no(M) - (su((M) ()) - 1.27ro
(71)
| -lll ro( - || projm x/ cos)
Now will show that the numerator is necessarily larger than zero, allowing further bound by upper bounding the denominator. Note that the numerator is greater than zero if and only if
(ro(M) ()) - T)ro(M) (M2
(ro(M) (so()) -7) 7) 1.27
ro(M)
Note that ( > 2/3 since (M) > 3r, and
> 2 since (n > 3r. Thus, the left-hand side of the equation above is larger than 4/3 which is larger than 1 .7.7.
35

---

Published as a conference paper at ICLR 2025
rendering the statement true and the numerator positive. Now continue bound by upper bounding the denominator,
(ro(M) - ()
(72)
||0 ulla vlll (rl()))) - || - proju 2 cos2 (0)
(ro(M) -
L.270
(73)
ro(M) /(0((/) - 7)2
(ro(M) - (ss)
1.27ro(MM)
(74)
To(M) 7)2 - 72
Finally, we can derive bound on Ø' from 72 since arccos (1'),
(ro(M) (M) T)ro(M) 1. 1.27ro (M)) 7)2 72
Ø' < arccos
(75)
Note that the fact that the numerator and denominator are positive implies the right-hand side of 75 necessarily < T 2/2. For all Φ o' we have (M( T. Thus must also be true that for all larger than the right-hand side of d < so(M) -. however, it remains to show that this is in fact violation of branch separation. Since the nearest point to y on C might not be (and likely is not) projm case of notation, let C(ty,) be the nearest point to y on C.
need to show that the manifold distance between y and this point is large. For
First we need to bound the distance d (projM 2. C(yy)). Since C' has radius of curvature (M d x, C(ty)) can be expressed as
|> ulla sin(
d x, C(t,)) = ro(M) arctan [ s"Il2 + ro(M)
(76)
This follows from Figure 1
approximating the geodesic y with C. The distance along C' from proj. x to (tyy) can be written as the angle swept out times the radius of curvature. Note that arctan(x) is increasing function of x. and arctan(x) for 2 O. Since & [0, x x/2) the argument of arctan in 76 is necessarily non-negative, allowing us to bound it as follows
|| 4/|l sin(d)
dprojim x. C(ty)) = ro(M) arctan
(77)
proo x - y2ll2 + ro(M)
x wlle sin(
S <r((M) arctan
(78)
ro(M)
| sin(()
S <r((M)
(79)
(M(M)
| v||2sin(())
(80)
Now we can apply assumptions on to bound d x, C(ty))
80 as function of manifold embedding parameters.
S || |1ryyla sin(
(81)
Se
(82)
ro(M).
(83)
Now we can apply the triangle inequality,
dm((C(t,) proim v) 2 d x, - (n(C((t),proimm)
(84)
(- + ())(MM) ro(M)
(85)
= =.))
(86)
As before, will apply the definition of minimum branch separation, which states that if (x((C(t))projjmm y) is larger than (MM( then = |[C(t,) - pproo yllz 2 so(M). Apply- ing the triangle inequality one more time leads to the conclusion that ||C(t,,) vll2 so(M) T.
However, we see that when & does not satisfy 75 d < (o(M - 7 and we have a contradiction.
36

---

Published as a conference paper at ICLR 2025
Lemma A.3
formalizes and proves the fact that shorteut edges necessarily oriented close normal direction to M from the perspective of each endpoint. To leverage this result, we then need to be able to say that this orientation implies concentration of measure away from the midpoint of all shortcuts. Figure provides a visualization of this phenomenon, establishing intuition for why this is true.
Concretely, Lemma A.4 derives the measure of the sets U2 and B. (x) detailed in Figure 12 in the limit of vanishing noise. The expressions for the measures of these are obtained by integrating the probability density function (detailed in eq. T over each respective set. What results is an expression that function Φ, the angle between the edge (ær, y) and the closest normal direction of M at .r.
Intuitively, the result matches what we would expect see the no noise (o 0) scenario. The m- dimensional measure of Uz when the center of (x))) is displaced at a distance ||æ - proj A æl1a from a m-dimensional manifold M would simply be (in the locally flat case) proportional to the volume of the intersection, which is a portion
m dimensional ball of radius ve² - | proj x =l.. The conditional probability of point being in Uz given (x(x) would therefore be the ratio of the volume this portion of a m dimensional ball to the full volume of the m dimensional ball. Figure 16 provides visualization for 2-dimensional manifold embedded in RR3.
Ø - 0
U
y
B,(x)
Uz!
M
Figure 16: A visualization of Nproim 2. Un and the edge (z, y) for 2-dimensional manifold embedded in R Observe that the measure of (x) Un approaches the volume of the intersection of (x) \ Un and M as a + intersection of U2 and M as - 0. Both of these regions shown as the 2-dimensional dark grey and matte blue shaded regions respectively.
Similarly, the measure of Uz approaches the volume of the
Lemma A.4. Suppose (z. y) is an edge in nearest neighbor graph built from data consisting of samples from the probability density function defined by Define to be the vector in the normal space of M proj x such that the angle & between and (y x) minimized. Also define
f(Ø) cot(o) (se(O))
|| 8112 de
2
and.
R= Ve² - || proiu x/12
and finally
/ 2 x projm
x
z2 1 1 -
proj 2
r(z)
(87)
0
otherwise
Then
V -- projprroja 11
Vol ((2)
(0))dz
f())
lim Pla Up la B,(+)
(88)
Vol
37

---

Published as a conference paper at ICLR 2025
where m is the dimension of M.
Proof. Rewriting ala E Uz la Be(x)),
Un]
PlaEU,la (x(x)] Pla Be(x))
(89)
((U.)
(90)
H² (B,(()))
Since the probability density in (2(x) is nonuniform, we need to integrate p over the regions we are interested in. To do so, we will integrate along v E Nprojuu M and use locally flat approximation of M. Observe that (y z) can be written our + Bv, where UT T proj as and v is the vector Nproi zM that forms the smallest angle & with the vector (3/ x). Also note that the vector (x proju x) is oriented normal to .M proju I well. It can therefore be written as d + UN. where is the vector defined previously and vn is some other vector in the normal space. It follows that d, || proj. .7|12 cos(0) and d,
| - proj ælI2 sin(O), where 0 is the angular displacement between (or projM 4) and v. visualization of these quantities and vectors provided in Figure 17
(x)
y
dr
UN
proju
dp
UT
M
Figure 17: A visualization of quantities defined and used for Lemma A.4
All coordinates mentioned from here onwards specify displacements from the point proj. x. Note that m orthogonal ambient directions are oriented tangent to M at projm I, while D m directions are oriented normal to M at proj. x. Since the probability density is constant in tangential direc- tions, we will begin by evaluating the measure of the subspace spanned by the normal directions directly; thereafter we will integrate along the tangent directions.
Let U1, U2 um.+..... up denote coordinates in orthonormal basis of N Nproj M., where corresponds with direction v and Uy corresponds with direction uN- Now let 23..... 2m+z denote coordinates in the tangential directions. We choose to define these coordinates with these indices as it reflects the order in which we will integrate. This choice will become clear deeper into the proof.
Observe that æ's only nonzero coordinates (as we have just defined them) are ij and u2. Therefore This arises from the fact
the probability density is symmetric about u; 0 for i E {m+33.... ... D). ..,,,...,,, that the u coordinates are the only coordinates in which the probability density varies coordinates have no effect (due to our locally flat approximation). Therefore, we will begin evaluating the measure the subspace (x) (centered at fixed coordinates U U2 23, 2m+2) spanned by normal directions Um-3: ... uD- The probability density any point in this subspace is simply
38

---

Published as a conference paper at ICLR 2025
function of coordinates,
11 + u2
Li=d+3 up
p(u1. U2, 23..........................22 ................................ 2m+2 (mt....., = Z exp
20²
"[ + up
Li=d+3 u
exp
exp
Z
20²
20
Observe that the point (u1, U2 23...... 2m+ O,...,,, 0) is at the same distance from the boundary of the tubular neighborhood in any direction spanned by ue for i E {m .....,,; D). While
.))
we do not yet have an exact expression for that distance, we can represent as some function of (ui, u2, 23.-..; Zm+2), denoted r(u1, U2, E3,.... zm+2) r. Put another way, if sider the intersection of Mu, (2) and the subspace spanning Mmm+33...., UD centered at (U1, U2, 23...... 2m-2; ... 0). it looks like D m dimensional ball of radius
Thus, we can evaluate the measure of this subspace of (x) centered at the point with coordinates (U1, U2 .......
mm- O, : :)) spanned by normal directions Um+331 ... Up as
uf + u
Σ Limd43 u
exp
exp
dV.
2x²
2a
(,) (B,
Now we will manipulate the term the integral so that it becomes equivalent the CDF of x² distribution with D - 2 degrees of freedom,
u
+
/
ΣP
Limd+3 U
exp
dV
Z
202
202
Um 13.0 B.(0)
(2
P-m-2
u + uz
Eizd+y us
D
exp
P m 2 exp
dV
Z
20²
Um+33n B.)( (2x)
20
D-m-2
12T
Wi + u2
exp
20
:= C
D
2i=d+3 w/
D-m-2 cxp
dV
Wm+DDD (o (2T))
2
F 22
u + u2
e'p
Fxa
20
where the third last line was obtained by applying the change of variables w; u//o for (m + D). Now we would like to integrate this expression over all remaining directions 23..... 2m+2 and Un, U2. To obtain appropriate limits of integration, its helpful explicitly write out an expression for relevant parts of the sets (r) and the local region of Mub in terms of the defined coordinates. The sets can be described as
{ (ul, U2, 23... t Uya+3: up) (n) d,) 2 + (U2 - dz)²
(x) =
+
m
2 + Σ
us
{
91)
1=3
i=d-3
and
S s={ (ui, U2, #3..... 4m, Um +mm ......, up)
Σ
< 72
iE(L22
respectively, where S describes the local region of the tubular neighborhood (when M approxi- mated flat). Naturally, are interested in integrating over the intersection of these two regions.
39

---

Published as a conference paper at ICLR 2025
We will start with 2m+22- Observe that the limits for 2m+2 necessarily symmetric this fol- lows from the fact that the point (U1, U2 23...., 2m+1, O,... 0) is equidistant along 2m-2 from the boundary of B, (x) in both the positive and negative directions. This distance is precisely
2 (ui do)2 (u2 dz)²
(92)
We do not concern ourselves with the boundary of M in the tangential directions because we are employing a locally flat approximation. Now note that, for a point with coordinates (u1, W2, 23,-... 2m-1; 2m+2, O,....0) O) the distance the boundary of Be(x) in any direction
spanned by um43:...,,44 up is a slight modification to 92
m++2
2 - (n1 d.)² (u2 - 1022-))2-
27
(93)
Observe that this gives us part of our expression for r(u1, U2 R3..... mm+)). In the normal di- rections, however, we are also concerned with the boundary of Tub,M, which is necessarily at distance
(94)
Thus, the limits of integration for 2m+2 directions must range from -1 times 92 to +1 times 92 The radius in the argument of Fx² must then be the
in any direction spanned by +
minimum of eq. (93) and eq. 944 Now integrating out 2m+2 yields
(w. - d -- de 1-
up + Uz
Bs
= C'exp
20
(u- do 12)2-112-220 do
minfe² f2 (ui d.)² (U2 2
>
2i=3
m++
2, 72 us
Fx²
džm+2
(95)
where B, (s)
denotes the subset of B, (2) when we fix all listed coordinates
and allow the others to vary. Now we can apply the same argument to integrate out 2m+1. A point with coordinates (u), U2; 23,.... Zd, 0, .) distance
2 (ui d.)² (u2 d,)) )
2
(96)
1=3
from the boundary of (z) in the + 2m+1 directions. Thus,
(x)
(u1.0).2g.....d)
Ve-- (us du)² (12 do 3
(u) de)
uf + uz
Ceep
20
V - (w2-d2)) 12- 3
1 (ui d,)
(w2 do d2)
F2a
minff² - (ni dv)) (u2 - dz) Σ
m2
21 1=3
u²
-22
U2
d d2m+2dZm+11 (97)
x²
Repeating this process for all remaining 2,'s yields
uf uz
B.(x))
= Ceexp
(1),02)
202
(u) dw d,)
(2) (d)=) 2.)2-112- do)² mm
(w) ) (uz 12 1ー
Ve (e- (d)-- (u2-da)) Σm
2 (8) do) 1- (u>
min(c2 (M1 )
(u2
)=)
Σ m+2 23 72 u² - uz3
F2
Ø²
džm+2dzm+1 ... d23. (98)
40

---

Published as a conference paper at ICLR 2025
...,, A point with coordinates (u1, O..., 0) is at distance
ve (u1 - d.)² dz
(99)
from the boundary of Be (x) in the U2 direction, while it is at distance
Ve2 - (n d,,² + dz
(100)
in the +u2 direction. This can be verified by inspecting Figure 17 Since spans a normal direction, we must also consider the boundary of Mu. Namely, the point (u1, O,..., 0) distance
2
(101)
from the boundary of M in the u2 direction. Therefore,
(z)
(w1)
v uz 22 -d.) -d2
[us d.) 19--110 (u2 d=)²
u uz
exp
20
max
v 12
d. -d.
d.) (22
d.)²
2img 27
(M) d. 32 (u2 do 12 Σm+
+1 2
2- (11 d,) 1- (u2 dz)
Σn
< 2 (u) d,)² (u2 d=)² Σm
min - (u1 d,)²
(u2
d=)²
m++ 22 72 u1 u
Fxa
3
2j
o²
dzm+2d2m+1 dzæduz. (102)
And finally since 27 < we have,
a Bi(x)
v - -- v2 x² (wss dd)
de
u1 u2
C
exp
20
max
72 v 22 jus - du [dd=}
1u) do 12
(22
(u) do 2 1 - da) --- Σ 2.
2- [us d.) 1-
(u2 dols >
V - d.) (u2()=- -mm 83
-- -e2 1--110 (u) do) 12- d2)) 1-
minfe² - (Mi - d² (u2
d=)²
-E mm2 2/ 72 - up - =23
F2
d d ... dzzduzdur. (103)
To obtain an expression for (B(()) we need one more component. Visual inspection of Figure 11 reveals that some of the measure of (x) can come from a region of the manifold that is lar intrinsic distance, but small Euclidean distance. This is phenomenon we have not yet accounted for. To do so, we will provide a large overestimate of the measure it contributes (which in the end, will not affect the conclusion of the proof). Since it is hard to quantify the volume of this region in the general case, we know its volume is necessarily bounded by Vol (z)). It follows that its measure is upper bounded by the maximum probability density in the region times Vol (x)).
To find the maximum probability density in this region, we need to reason about the minimum distance any point in this region can have to the manifold. Consider point in this region, and its corresponding nearest point on M, projM p. Since we have stipulated (MM > e, any manifold geodesic path through proj. could not have left (x) and re-entered it without travelling more than (M) distance. Our locally flat approximation ensures that our expression for μi B (x)] accounts for the volume traced out by all geodesic paths that pass through proj before they leave B, (z); thus the only measure we have not accounted for is associated with areas of M where geodesic path through proj.y left B, (x) and later returned.
41

---

Published as a conference paper at ICLR 2025
Since we know the manifold distance from proju projm P exceeds Tro(MM, we know projm x - projM pll2 2 su(M) from the definition of minimum branch separation. Using the say
triangle inequality and applying assumptions to bound and
- projo M pll2 2 projm I prooo pllz 1| projm æ|12 - || pll
so(M) (so(MM -22-
: 8
0.
Thus, the measure of this distant region of Bx(x:) is necessarily bounded above by
vol (o((B(z)) Z exp (
2
Thus, we can safely conclude that
14 (B) x
minn v²² 2 /2 (m
2 e (22
2 U2
C
exp
20
22 max
2 (u) do 1
(12 do 1 - d2) ) 2
V 2- (u) d.)² (u2 dol2 1--21-2 2
(m1 d.) 2-)2-(u22-11111111000011- 12) Em
-- (u) do)3 12-22 d=]² Ei
min - (u1 d² (u2
dz)²
5m+ 24 T² - up - 23
F2
duzduzdus + Vol Vol(B. (B.(xt)
1
82
d2m 4222m+2
Z exp
(104)
20
Computing u[UU2] involves changing the lower limit of integration for 23. In the u1, 23 plane the boundary of Un is simply line with slope tān(ø); the un intercept be obtained with simple follows that the expression for the boundary can be geometry, and is d, - sec(o) - ((ll=-)))))) rearranged as,
23 = col( (w - d, + sec(#) C
y/ vl22
To understand this step encourage the reader to refer back to Figure 12 to recall the definition of Un. Moving forward, for the sake simplicity we can also discard the second term in eq. (I04 to obtain a lower bound on p.[ Therefore,
Uz
mmin
22 -- 22 (ui d +
2 (n) - d.) 12 (ug )2
u² + uz
C
exp
T max
17. (11 d, +
20
jrot(o) (n) -d, d, ) - واريااا
(w) do )3 (uz - d=)²
mm
12 (ui - (2)= Σm
2- 2-1 d.)3- d2 22 L1n
22
(uy -d) 22 22- do Σm
min(e2 (w) d,)²²
(u2
d,)3
m+ 2 72 uř w²
F22
g²
22m+ dzzduzdur (105)
We are interested in evaluating the ratio of 105 and 104 in the limit of 0+. Since 104 is the
measure a finite volume subset of D with a nonempty intersection with the support of p. for all the quantity is nonzero. To make sure the limits converge nonzero value, will multiply
42

---

Published as a conference paper at ICLR 2025
the top and bottom by 2m As will also show, the ensures that the limit of the denominator converges to a nonzero value. Thus we can pull the limit into the fraction to say,
lim 2
lim (|
(106)
- 2na2C (c())) lim 250 2 (x)
The denominator can be bounded with
2TTO2 1 (x(x))
min 72 uf 22 2- (mn -.
c
(1)
d
(u2
"1 U2
2T exp
20
max
(u: -d d. +d,
do 13 u2
2 (1) du 8- u2 dz)
-E 27
2 [ui de) p (u2 d2) Σ
2 (u1 - (u2--2d22 Lin
--ve 2- (ul do) (42 d=) Li
min (22 - (U1 d,)² (u2
dz)
mm+
2/ T2 up - 233
Fx
i=3
g²
dZm+2d2m41 dz3 duzdui +
vol(B (c((t)
Vol
1
exp
82
(107)
2T
CZ
20
Defining everything in the bracket as g(u,, uz) and taking the limit, we get
lim 1
2mo²C (x)
a
rmiuf VT Vel -u)) +d.)
2TO² exp (- ut u²
$ lim a-0
g(u,, u2)duudu1
mmax - v (m do tds tds}
202
1
82
+ lim
Vol (c((x)
exp
(108)
o - 2T
20
The second term can be rewritten as,
lim Vol (x) a (2
82
cxp
20
Since å is a constant, one use repeated applications of L L'Hopital's 's rule to show that this term converges to 0 in the limit. Now we can focus on the first term of eq. (108).
1
lim +u 2 (x)
rmin (VT2-uf 22 (u) d.
o + uz
< lim a-
exp
g(u,, ug duzduu
maxx
(11 d, 3.
2no²
20
(109)
Define the limits of integration for Ug as Liw (u,) and Lup(u) respectively. Now we will rewrite the equation above, replacing the limits of integration with indicators
1 +0+ 2 1 Br (x)
2 + uz
lim
< lim
2T
exp
20
00
1 U22 E (un),(u1), (un()))) in E E |--,, 7) g(u,, u2) (110)
Applying the change of variables wi = u1/0 and W1 = u2/a yields,
lim 1 [x)
000
000
f w
2
u
< lim
exp
o-2
-
2x
(ow((
Tup Tuplowi)
1 W2
W1 I-T/ 7/0| glo ows)duyduw, (111)
σ
43

---

Published as a conference paper at ICLR 2025
Observe that 9 defined is simply integral of function bounded by 1 over region bounded by B. (x). Therefore, must be no larger than Vol(B.(x)) Clearly the function
w + 2
exp
Vol (B.())
2m
2
dominates the integrand of g: furthermore, this function is integrable as the double integral over wi it dominating function to invoke the dominated convergence theorem, allowing us to pull the limit into the integral.
and W2 evaluates to Vol (ol(B,(2) (z)). Therefore
w + w
lim
2 (c(())
<
exp
a-+0+
2x
Loo (oww((w))
(up(ow))) w1 E [-T/0,
lim a-101
W2
lim owz)dzzuy 0
0
(112)
Note that Low (0) is necessarily negative, as 2 2 /² > d, Therefore, the indicator function in the integrand converges pointwise to 1. Writing out the second term,
(aw) - d.) (aw- -d)
lim glow1, ow2) = lim -
a-00
lowi
(ow0 d,)
(awi du)² (aws dz)" Ei 22
(crm - -
2 (oww (ow: (o0 d,)
E
2ow 2 d,)3 -:
min - (owi) d²)²
(ow2
d,)² d²
mm+
27, 72 ow? -ow3)
2i=3
x
d2m d2m+2d2m+1 ... d23. (113)
We can pull all limits of integration into indicator function, but for the sake of brevity will not write it out. Note that this step is simply taken to illustrate the fact that we can invoke the dominated convergence theorem again. Observe then that for all the radicals are nonnegative, we are integrating a Chi-squared CDF (which is bounded above by 1) over m However, the aforementioned indicator function always bounded by an indicator over the set TTr (0). Thus, we can choose [2a.442 BTh (0)) as our integrable dominating function, allowing us to pull the limit into the integrals.
such that the terms inside of
We can evaluate the indicator function in the limit, and pull the indicators back into the limits of integration. Also observe that the integrand (the CDF of the Chi-squared distribution) converges to 1 as its argment converges too. Thus,
B-
lim owz) o-00+
do
d
m 8 --d2
>m+
d2m42d2m411.. da3
18-8 B -m+ x?
(114)
Vol Vol(BB (B)
(115)
44

---

Published as a conference paper at ICLR 2025
where R v2 -12 - 211 since de + d² = 1| proj
M
11
Note B (0)
denotes an
m-dimensional Euclidean ball radius R. Plugging this into eq.
112
lim a=+01 2TO²CH (B(x)) -
exp
+
w
Vol B, (0) dwpdwi
(116)
2T
Vol ( -ol((.. (0)
1
w + w
exp
dwzdwi
(117)
2T
Vol BBTT (0)). Now we want to evaluate
(118)
2T ( [U,] in the limit. Recall,
rmin 1V //. /2---00- -.)) d=
ui + u2
2To2C US
2T exp
20
max ui: (11 - d,) 4d2
(ui dd)) uu2 dd))
(2)
(us d, )2 2 m
coo(()) (u: (d: +sec
c- |z-
(wa-d,)
Σ.
2 (ui d
(w0 d,)
Σ i:m3
2211 - -2 dz)²
1im8 x?
min(62 (w1 d
(u2 d=)²
Σ
m+2
22
72
11 uz)
Fxa
:==
2/
dum+2dze 22
dezduzdur- (119)
Define everything in the bracket to be g (1 U2 23). Rewriting we have,
2 (us d
uf + ub
21 Un 2
2TT exp
mmax
(2) d.,) td.
20
d. (wz -يe
Jcot(o) (116)) (11-d: و I (ui, u2, 22dddddd (120)
Taking the limit both sides,
lim -
2402C
Un N
mmin 72 12 (01 d,)² +d
1
U +
up
lim 7=
exp
2To2
20
mmax
up. e2 ( 2
2- (ui - d, - (oz - dz)²
J'u u2 23)dzzdu2duy. (121)
Jcot(e) (us -d (عملسعل
We will use the same definitions for the limits of integration of u2 from 110 and further define
Liow, (1i, b) cot(Φ) (1 d, + sec(d) (E || y 2
and
Tup.es (u1, (u1, u2) Ve² (w1 dz)2 (wz dz)2.
45

---

Published as a conference paper at ICLR 2025
Converting the limits of integration to indicators,
lim 1 2T02
ui + uz
Us
2
lim a-0+
exp
I (u1,, u2 23)
a-+++
2TO²
20
-00 -00
1
E
Liow (ui, .b), Lup.as (ui, (u1,
Tow (u1), Tup Eup(u1)
[-,,-]]
dzzduzdu1. (122)
Now let's apply the same change of variables w1 u1/0 and w2 =u2/o to get
g (ow), ow2, 23) + w w
lim a=++
2
Us| 2 lim a-0+
exp
2n
2
Loowsss (ow,, +), Lup (oui,, own)
23
Trww (owr)
Tup(ow))
wr [-T//,
U22
0
dzzdwzdw1. (123)
Through a similar argument from
112
we can choose the function
w
+ w
exp
Bol(B,T-
2x
2
dominating function for the integrand. Now we can pull the limit inside the integrals,
wp
lim
2
Up
2
exp
lim g'oou,, ow2, 23) a+0
2x
-00
-00
lim +0+
23
Tnww. (ow1, Φ), Tup. (ow,, mw2)
(low(ow1)) [ap(oru))
E [-T/O,
d23dwydw1. (124)
Observe that the indicator converges
(1=1)=> yl12) v1le) do). ve2 2 || projm
|| 10-110-y/1
1 E (o) (s)((e)
2
Now we want to evaluate g' in the limit,
lim g' (aw), ow2, z3)
a-0
(aw, ) (owg d.) 2-)
(owl d..)2-(ww 2 mmi
lim
a -
Ve / - (o
(ow) do,) 3- 0 dz)² -
minfc2 - (own d ?- (ow2 d
mm+ 22 2.72 ow? ow?)
Fxa
²²
džm+2 dzg. (125)
46

---

Published as a conference paper at ICLR 2025
Again we can pull all limits of integration into an indicator function, but for the sake of brevity will not write it out. Note that this step is simply taken to illustrate the fact that we can invoke the dominated convergence theorem again. Observe then that for all >> 0 such that the terms inside of the radicals are nonnegative, we are integrating a Chi-squared CDF (which is bounded above by 1) over IR. mR--1_ However, the aforementioned indicator function is always bounded by indicator the set B Thus, we can choose 23.6+2 E Bmm=+() as our dominating function, which is clearly integrable. This allows apply the dominated convergence theorem to pull the limit into the integral.
We can evaluate the indicator function in the limit, and pull the indicators back into the limits of integration. Also observe that the integrand (the CDF of the Chi-squared distribution) converges to as its argment converges to +00. Thus,
2 - d2
d4
lim oo2 a-+0-
d
dz4
(126)
- 13-
d3
E1a
= Vol(Bm7-)
(127)
where
V
|10 projm
- -
s || -prooo 2|B
r(23)=
(128)
otherwise
Plugging into 124 we have
100
100
roc
w w/
lim -
2
Ug 2
exp
Vol (ol(Bm-100) (0)
2T
-00
-000
cot(() (sc(()) (c ||
(((c))sse())
yll2
- do) v - ||0 proj
23
2
dzzdwzdw1. (129)
Pulling the indicator back into the limits of integration and rearranging, we get
00
000
x proj
lim a+
21
Uz
2
(oot(d)
sno(())
(-|z-112 -d.
w + wg
Vol Vol (B) d2ydudduy
exp
2T
2
(130)
000
00
w + w
exp
dwpdwi
2T
2
V 1 pa-p-oojjs
Vol
Vol(B.m- (r))) (0))
(cob(o)) soc(o) مااe ddo)
(131)
-- -r-ppan rriuue x
Vol (alBB-110 (B (0))
(132)
(o0(() (cp(es) ( -d.
Let
f()) = cot(o) (scc()) coc(o)(sco(()
(- || y|l2 - de
2
47

---

Published as a conference paper at ICLR 2025
and redefine to Now combine 132 and 118 to obtain the bound on 106 and thus bound
90
proj
PlaEUz B((x)] (() a
T(=)
lim
(133)
(ol(BB(())
where R Ve² - x
and r(2) ve² || projm 2/ -
A.4.3 PROPOSITIONS
While the lemmata represent majority of the theoretical results of this work, the theorems that stitch them together require a few more propositions. We will start by showing that the minimum radius of curvature of geodesic paths through the tubular neighborhood of manifold M have minimum radius curvature ro(M) - T, where ro(M) the minimum radius of curvature of geodesics in M.
Proposition 1. Suppose M is a compact submanifold of R without boundary and with a minimum radius of curvature ro(M). Then Tub, has a minimum radius of curvature of ro(M) T.
Proof. Note that the ambient curvature of a path y through R. can be written k.2 + kg, where kig denotes the geodesic curvature and kn denotes the normal curvature. Paths that are geodesic in some submanifold M necessarily have 0 geodesic curvature with respect to M; thus kn for such curves.
g
Now consider length- parameterized geodesic path Yub [a, b] M.. Since Tuub is geodesic of Mu,, we know that k<t)) = (t) for all f [a, b]. Now let's consider two cases:
1. (tu (t) is at distance less than from M. In this case, the Yrub (t) does not intersect with the boundary of Tub,M; it follows that no directions normal to Tub, exist at this point, and the normal acceleration kt) must be 0. Therefore, k(t) 0. This formalizes an intuitive concept geodesics through M are necessarily straight lines if they do not lie on the boundary of Tub,
2. Yiu (t) is at distance exactly equal to T from M. In this case, there exists a single normal direction to Tub, (t).(t). It simply the direction from Yiu(()) (t) to the nearest point on M (up to sign). Therefore, the only situation in which Trub has nonzero curvature when it lies exactly the boundary of Tub; the curvature is simply the norm of firab(t). which is some vector necessarily normal to the boundary of T at (Tua(t).
follows that bounding the radius of curvature of geodesics through Tub, be accomplished by considering geodesic paths restricted to the boundary of Tub, as all other geodesics through Mub have no curvature (and thus infinite radius of curvature).
Now redefine Tuub to be some geodesic segment that lies entirely on the surface of Tub, with nonzero curvature; suppose this segment starts at (t1b((1)) and ends Yrub (tg). Choose interme- diate and overlapping time intervals { I = [a., af] where a. < af. a/41 < a² < af
and o] = 4, az l2. Observe that U T [4, 42). so the set of interval spans [4, 12). Note that we choose for these intervals be overlapping so we can avoid the case where curvature the endpoints of sub-intervals is unaccounted for.
Now we will analyze single sub-segment of TTub defined by the image of I, = [a]. azl under the map TTub- We encourage the reader to refer to Figure 18 for the remainder of the proof. As previously established, (tu)(t) is necessarily parallel to the vector from proj (to (t) to (t)) Consider the plane spanned by the vectors (t) and ine (t). Now consider the osculating circle O approximation of YTu near Yna (t) for some E Iy. Since I5 can be made arbitrarily small, O is arbitrarily good approximation of (Tbb(() for E T3. Suppose O has some radius r.
48

---

Published as a conference paper at ICLR 2025
YTub
projM(Praa)
nLM
Figure 18: A diagram depicting Yib. projm Mub. O and O'
Finally, consider the path in M defined by the image of (t) for t E I under the map projm Trus (t); colloquially this path is the projection of the subsegment of Ynu onto M. Given that the osculating plane contains the vector (TT locally (for I and we have already tablished that (Tob(() is parallel to the residual of the projection (proiM T (t) (Tu(()) then this projected path must also lie in the plane spanned by the vectors (tw)(t) and TT (t) for f Lj. Since we are considering the case where " (t) is at distance exactly equal to from M for all t, this projected path then approximated with its own osculating circle O' lying in this plane with radius r + T, sharing the same center as O.
Since the projected path approximated by O', its acceleration vector a neighborhood near must be parallel to "Trb((): this implies that it is entirely orthogonal to M,, making the path geodesic in M. Since it geodesic in M, the radius of O' for all segments of all possible geodesics Yiub no smaller than ro(. Solving for the minimum possible radius of O yields ro(M)
We will quickly show that there always exists a geodesic segment in the tubular neighborhood such that O' as defined above achieves this minimum radius ro(M). Pick some geodesic segment in M called TM with a constant nonzero acceleration ||a = l/ro(MM. Note that 7MM can be made infinitesimally small such that the constant acceleration assumption is arbitrarily accurate. Also note that RM is necessarily oriented normal to M, as 7M is a geodesic of M. Define another segment as follows,
Yrub = (t) + (tt())
(134)
(t)ll
where the domain of (Ta)()) is the domain of (.M(() Observe that this segment necessarily lies on the boundary of the tubular neighborhood as it was displaced exactly т from M in the direction (t). which lies normal to M. Also observe that we can approximate (tM(t) with its osculating circle O' arbitrarily well, where O' has radius (.M) Since (t) and (t) lie in the osculating plane, (t)(t) must as well (as we have defined it to be linear combination of these two vectors). In fact, Trub(t) is approximated arbitrarily well by O, its osculating circle centered at the center of O'. This very much mirrors the scenario that we posed earlier in the proof, visualized in Figure [8
Since O and O' lie in the same plane centered about the same point, (t and Fro must be par-
allel. Since (() lies normal to M, ((Ta(() must as well. By construction of (1), (MM (1) must be parallel to the residual of the projection of (I)(()) onto M: this follows from the uniqueness of proj. stemming from the assumptions that ro(M and 27 < (MM (detailed in assumptions 2) and []. This residual is the unique direction normal to the tubular neighborhood at YTo (t), and have just established that (t (and thus (t) is parallel to it. It follows that Yna (f) is geodesic segment of Mub, as its acceleration vector lies completely normal to Tub, Its radius of curvature, (MM T, be deduced from the difference in radii of O and O'.
We can conclude that r, the radius of curvature of any geodesic path in the tubular neighborhood, always achieves minimum ro(M)
49

---

Published as a conference paper at ICLR 2025
Now we will move on to showing that the ORC (as we have defined it in Section 2.3 any edge in an unweighted graph is necessarily restricted to the finite interval |-2, 1].
Proposition 2. For any edge (z, y) in an unweighted graph, -2 S K y) < 1.
Proof. Observe that, under the current construction, the unweighted graph distance between node a E (xx) and E (y) is bounded above and below,
S da b) S 3.
This implies the same bound on the Wasserstein distance between the measures Me and Myy This is clear when we rewrite the I-Wasserstein distance as follows,
W (Has My)
inf (ET))))))
Ba,wyylaa b)]
where [T My) denotes the set of all measures on V x V with marginals Prr and My- Thus,
0 S ((es My) - 3,
and because x(x,y) =1 W(1z, 11, we have
-2 x(x,)) S
Now we will prove a bound on geodesic distances through the tubular neighborhood as a function of manifold geodesic distances. This proposition is used in Theorem 3.3 to bound graph distances of shortcut edges in ORC thresholded graphs.
Proposition 3. Let drun y) be the geodesic distance induced by the Euclidean metric from æ E (Mb to Tub, (M). Then,
drab v)
ro(M) -T ro(M)
d (mrojr x, projm y)
Proof. Let Tub be the geodesic path through Tub, from to y. Select P points {pr)/e (a method for which will be described soon) along Trub and join the projection of successive points pis 1,1+1 with curvature ru(M). Let's denote the segment of Yiub between Pi+1 onto M by a segment Xproj
Also suppose P large enough such that the geodesic segment through M connecting the projections of p; and P++1 can be arbitrarily well approximated by its osculating circle O Observe that since M is smooth and we have required T < so (MM)2 and T < ro(M) in assumptions 1 we have unique projection. It follows that proj (a) Va E Tub, is continuous.
Ps. P++1 TTub i.++1
pitl
proju(pi)
proju(pit1)
i,++1 7min
pi
θ
ro(M) -
Figure 19: A diagram depicting Pt Pi+1 and various related quantities.
50

---

Published as a conference paper at ICLR 2025
Note that
P-1
dTub y) ((Trub)
and
P-1
dm(projm v, proj v) <
AmpprojuP Pi, proj Pi+1) S ==1
M(proi) )
The second incquality in the second statement requires explanation; observe that, since proj is continuous one can choose I such that for all At < T
projm (t (t + At) projm Yrub (tub()) < so(M)
for all t E dom()rus). This gives us principled way of choosing {pili- where p; = Trub Σ}= (At),. From the definition of minimum branch separation, we know that || proj Pi+1 projm P: < (MM)
dmm(proju Pi, proj Pi+1) aro(M). Now we will apply Lemma 3 from Bernstein et al. (001)) to say
proj P++1 proj Pille
dm Ptù Pro)) & (Mo(M)
aresin
(135)
2ro(M)
(136)
The second equality follows from the way have defined L(7proj of curvature ro( from projm Pt to projM Pr+1. Application of some trigonometry yields the length.
6,++ with constant radius
Now consider a single segment defined by p; and Ps+1- Since we assume "proj has curvature ro(M), approximated exactly by its osculating circle with radius ro(M). Let 7mio be the straight-line path between the points at distance ro(M) - from the center of this osculating circle in the directions of projm Pt and projm Pi+1 respectively. A diagram is shown Figure 19 for
2,6++
clarity.
Observe that the length pii+1 min = I(Tmitt)) must be no larger than the length of any straight-line path connecting any a E M and b E Tub,-M such that they project to projM pj and proj Pi+1 respectively. In understanding this, it helps to note that the set of points could lic in is a D m (where m is the dimension of MM dimensional space created by intersecting the tubular neighbor- hood with the hyperplane that contains pt and the center of the osculating circle O2,5-1 (defined earlier in the proof) and spans all manifold normal directions at p;- The set points b could lie in has similar form; just replace p; with 1i+ The only directions from p; and pi+1 (restricted the described subspaces) that bring the points closer is the direction towards the center of the osculating circle O1,411. Starting at p; and pi+1 and travelling in these respective directions until you hit the boundary of the tubular neighborhood will minimize the distance. This minimum distance bounds L(>iib))
1,+1
(,i+1, ), and we can compute it as follows,
3,++1 L L
2 I|a 6112 - 7
(137)
proj P: ppropproi Pi+1l12
(138)
where r is the radius of O4141. Since (x a)/2 increasing for positive v and have
ro(M) -T
proj Ps proj Petall2
(139)
ro(M)
p+++1
(140)
since S r.MM). Thus, we know that L( 2 gii+1 Also note that min be written
function of (( as follows: compute 0, the angle swept out by }proj 2.i+1 0 [ D/roM)
Then observe that p..+1 2(ro(M) sin 2(ro(M) -7) sin([[ ( (/2ro(M))
51

---

Published as a conference paper at ICLR 2025
Finally, note that sin(x) = for small which is a reasonable approximation for large P. Note that P can be made arbitrarily large as segments can be divided in half without shattering the requirement that || projm Pi+1 - projo P:ll2 < so(M). Thus, pi min R 2(ro(M) 1,2 ((poo))))) /200 =
ra(M)-I ((ppro))) ). Putting all together, ro(M)
P-1
drub(T y)
Σ
Σ
pitt
2
min
(M(
[7prroj
ro(M)
ro(M) r
dmroioj Pi, proim Pi+1)
rl(M)
ro(M) -7 - ddm x, M))j ro(M)
Now we will bound the measure of an arbitrary D-dimensional ball centered at point in the tubular neighborhood, result which will be used in Theorem 3.2
Proposition 4. Suppose is the probability density function defined in 7 for manifold M embedded in TR.. Then for ro(M) >>
8D Vol (Bl(B((0)
P Paup
|| 2112
6
(141)
22
Proof. We can rewrite the left-hand side of 141 as
P Paup ||
2112 s 6|
1 {= || x112 S o}}
2 Vol (ol(B((0))
min
p(z)
| Tu M
1 vol(
min
p(z)
||=0||250 28 TTih
The second line follows from the fact that a 8-ball centered exactly on the surface of the tubular neighborhood Tub,M is approximately cut it half; while curvature of M may slightly reduce this volume, considering ro(M) > 8 makes this reasonable approximation. Now it remains to bound the minimum probability density. We can do this by simply choosing the minimum value p takes on in the tubular neighborhood,
min p(z) M
(142)
7
Combining everything,
8 Vol (B)
P PImp
||
x
2112
S
8
6 2.7
(143)
2z
Finally, we will show that the probability that the neighborhoods of two points overlap com- pletly approaches the points converge to each other. This proposition also used in Theo- rem 3.2
52

---

Published as a conference paper at ICLR 2025
Proposition 5. Suppose {ri) and { are sequences of points in a series of point clouds sampled ii.d. according the probability density finction defined 7 Also suppose that lim I Vil12 0. Then
lim P Pamp a Be(x,) n (v(ss) a Be(x)) U Be(us) =. 71000
Proof. Our proof will use similar argument to that of Lemma A.4 the term of interest in friendlier form,
First we will rearrange to put
PP Pamp a E (2) n Be(y) E U U (.))
(144)
(B((()))B()))
(145)
((B(())UBB()))
(BBe(t)nB(())
(146)
- ( (B(e))
Computing each of these terms involves integrating (defined by D over the set of interest. We define S (x), Sy (y) and S2.0 Be(x) Be(y). Evaluating the measures, we have
1 ((B((z))= = / p(=)dV
(147)
JES.
S p(z) Xss (2)dV
(148)
and
/ p(=)dV
n (BB(vv)
(149)
2E8
p(2) xs, (z)dV
(150)
where (2) is indicator function, defined as
{
if E A
(a(2)
0 if A
The measure of the intersection of the two epsilon balls can also be described with
[
((B.(z)
plz)dV
(151)
SESS.
p(z) (s)
(152)
RDD
Now suppose we have two sequences, {xi and {4: where limi-soe = x, lim D: y, and lim ||.; yall2 Now define Sz,i (x;),, Sy (w:) and S (x,x, (y:).
We will show that lim;- (s).(()) (2) = lim;- (z) pointwise, from which will follow that Xs, will converge the same function pointwise. Define X(2) == lim, XsS,. (2). Now
we'll Il show that lim; Xs.. (2) = X(2). This involves showing that for all E RD we have lim Xs.. (a) = x(a). Consider two cases:
x(a) = 1. Since H; + x and ||, - -ysll + 0, we have x; + y. Since X(a) 1. we know that for sufficiently large lla Vall2 < so it follows that ||a - Bl12 S Since z; - y, it must be true that ||a x; l2 I e for sufficiently large i. Thus for sufficiently
large i, XSS. (a) x(a) 1.
53

---

Published as a conference paper at ICLR 2025
X(a) = 0. This implies ||a y4 l2 > for sufficiently large i. Since ||x; yell2 0 must also have that ||a - 2;11e > e for sufficiently large as well. Thus for sufficiently large we have (8.. (a) x(a) 0.
Therefore lim Xs..: (z) lim; (z) - x(2). then follows that the indicator function on intersection of the two epsilon balls (denoted S,,m) must also converge pointwise to x(=). Namely, lim;-ro ,, (z) = X(2).
Now want to these results to evaluate 146 in the limit. As we will show, the denominator converges to a nonzero value, and thus the limit can be taken into the numerator and denominator as follows,
lim Pa Pamp (a (,, a (x(
(153)
(BB(()))B(()))
lim 8000
(BB((z;)) + 1 (B)()) (z; n (1))))
(154)
lim r 11 (B,) Bell))
lim (B.B().)) + (( ((B( B. (. (.()))
(155)
Let's consider the numerator first. Rewriting using 152 we have
lim ((B((()) ( (x)))) 100
lim 1oo
p(z) 3D
XSx (z)dV.
Observe that Ip(2) (=)) S p(z) for all i; p(2) integrable as it represents a probability density function over RR. Thus, we can invoke the dominated convergence theorem to pull the limit inside of the integral obtain,
/ lim p(z) XS (z)dV JRp 10000
lim (B.( +00
I p(z) x(z)dV.
Now let's evaluate (x;)) in the limit. We can invoke the dominated convergence theorem again for both to pull the limit inside of the integral as before,
lim i (B.(z:)) = lim 10000
p(z) Xs., (z)dV
R
/ lim p(z) X8., (=)dV
/ p(z) x(2)dV.
54

---

Published as a conference paper at ICLR 2025
And finally the same steps can be taken to find that lim a (B((s))) Se p(z) x(z)dV.
Stitching it all together, we have
lim Pa Pample aa Be(x,) n Be a E (x,z,) Be 10000
lim 1 (3re n (e()s)
lim (B(((zz)) + M (b))) (Bc n Be(wi)) 1-000
((2) - x(=)dV
RD
p(z) x(z)dV + p(z). -x=)dVV - RD
p(z) x(=)dV
((2) x(=)dV
p(z) x(z)dV
55

---

Published as a conference paper at ICLR 2025
A.5 ADDITIONAL EXPERIMENTS
A.5.1 PRUNING
Pruning performance of our method vs. baselines described in Appendix A.3.I A.3.I For each entry, the top row indicates the percentage of "good" edges removed, while the bottom row indicates the percentage of shortcut edges removed.
Table 4:
Cancentric Circles
Mixture Cansiians
Moons
5
Casini
ORC-MANL (OuES)
100.0 0.0
0.0 + 0.0
100.0 00.0:000
0.0
100.0 00.000..0
0.0 0.0
100.0 0.0
0.0 0.0
100.0 0.0
0.0 1 0.0
12.6 0.2
13.7
12.3
13.4
10.9
100.0
0.0
0.0
0.0
0.0
2.6 0.2
2.0
1.7
1.9
0.1
2 21.5
45.3 18.5
0.D
82.0 33.7
40.0
MST
Zemel& & Cameira Perpiñáe
2004 Chao et
2007
09.6 8.8
0.2
99 11.2
1.3
4.0 12.0
D.3 D.1
100.0 0.0 0.0
0.4
70.0 45.8
0.0
DENSITY
Chao al. 2006
819 16.7
0.4
100.0 0.0.0:00.00
0.0
0.7
23.422344
1.0
3.1 0.3
2.1
0.0
DISTANCE
0.1
2.1
0.1
100.0
8.8
0.0
133
A.5.2 MANIFOLD LEARNING: T-SNE EMBEDDINGS
Here we show additional runs of t-SN (Van der Maaten & Hinton 2008) noisy samples from the swiss roll and the swiss hole. These experiments supplement those that are presented in Figure S We find that t-SNE embeddings are inconsistent between runs for this particular task, so to ensure full transparency we show results on three different samples Figure
Swiss Roll
Swiss Hole
ORC -MANL
None
Trial
Trial
Trial 3
Trial
Trial
Trial
Embeddings produced by t-SNE (Van der Maaten & Hinton 2008 three different sets of noisy samples from the swiss roll (left) and swiss hole (right).
Figure 20:
A.5.3 REAL DATA: MNIST AND KMNIST
ORC-MANL
None
ORC-MANL
None
Figure 21: UMAP embeddings of 10,000 MNIST (left) and KMNIST (right) datapoints using near- est neighbor graphs with and without ORC- preprocessing. Ground truth classes are anno- tated and edges of the pruned and unpruned graphs visualized in grey.
56

---

Published as a conference paper at ICLR 2025
In this section include experiments that demonstrate the efficacy of ORC-MANL canonical datasets the machine learning literature. Specifically, we evaluate on nearest neighbor graphs built from the MNIST Deng 2012) and KMNIST datasets (Clanuwat al. 2018), with results visual- ized in Figure 21 where UMAP used to visualize pruned and unpruned graphs). Unsurprisingly find that ORC-MANL. pruning removes significant number of inter-class edges while also pre- serving intra-class structure. Specifically, we find that ORC-MANL removes 14.92% of inter-class edges and 7.90% of intra-class edges for the MNIST dataset, while it removes 14.70% of inter-class edges and 5.39% of intra-class edges for K.NNIS. We emphasize, however, that edges that connect data points different classes may not necessarily be shortcut edges. Similarly, edges that connect points in the same classes can satisfy the definition of shortcut edges. Thus interpretation of inter versus intra-class edge removal results should be approached with caution.
A.5.4 CLUSTERING
ORC -MANL
ARI: 1.00
ARI: 1.00
ARI: 1.00
ARI: 1.00
None
ARI: 8.2c-4
ARI: 0.36
ARI: 0.99
ARI: 6.9c-3
Figure 22: Spectral clustering applied several synthetic manifolds, with adjusted Rand index (ARI) shown. Nearest neighhor graphs in the top row were pruned by ORC-MANL, while the nearest neighbor graphs on the bottom row were not.
We further evaluate ORC-MANL pruned graphs on spectral clustering, a canonical algorithm for finding communities of arbitrary shape (Bach & Jordan 2003). The algorithm embeds the data using the eigenvectors of the graph Laplacian, and proceeds by running the k-means algorithm on the embedding (Hartigan & Wong 1979). On this task expect ORC-MANL. help very much: the underlying manifold exhibits several connected components, ORC-MANL pruning should reveal them, resulting in easy task for spectral clustering. Unsurprisingly, true, as ORC-MANL improves spectral clustering as measured by the adjusted Rand index (ARI) (Hubert Arabie 1985). A higher ARI indicates better alignment with base truth clustering, with the best possible score being 1. We test on noisy manifolds exhibiting two underlying connected components, where visualization of the results shown in Figure [2] We find that ORC-MANI ensures perfect ARI across examples, while the unpruned graphs result in trivial clustering that not representative of the underlying structure of the data. We do not include t-SNE or UMAP embeddings as they require finite pairwise distances, which does not hold in the case where pruning (correctly) results in more than one connected component.
find that holds
A.5.5 PARAMETER ABLATIONS
To analyze the sensitivity of the ORC-MANL algorithm to key parameters, we include the results of pruning experiments with varying parameter settings. Specifically, we analyze the hearest-neighhor graph parameter kt the ORC threshold parameter 6, and the thresholded graph distance parameter X. The pruning results four synthetic noisy manifolds with 4000 points across 10 seeds are visualized in Ta The top row each entry depicts the mean and standard deviation of the percentage of good edges removed, while the bottom row of each entry depicts the mean and standard deviation of
the percentage of shortcutting edges removed. Parameters are set to 20, = 0.8, and 0.01 unless the said parameter is being varied.
57

---

Published as a conference paper at ICLR 2025
Table 5: Ablation experiments for parameters ò and respectively.
10
20
k 26
30
Concentric Circles
100.D 0.0
100.0 = 0.0
+
100.0 +: U.D
100.0 + 0.0
100.0 + 0.0
0.0 +
Mixture of Caussians
100.0 = 0.0
0.7 + 0.2
2.0e-3 + 4.5e-3
100.0 + 0.D
100.0 + U.D
0.0 0.0
100.0 + 0.0
0.0 0.8
100.0 + 0.0
0.0 = 0.0
Chained Tori
0.7 + 0.3
2.3e-3 + 7.0e-a
100.0 + 0.0
0.0 +.0 0.0
91.6 20.0
0.0 + 0.0
100.0 + 0.0
0.0 + 0.0
Cuncentric Hyperboloids
2.9e-4 8.
0.0
0.0 0.0
= 0.70
5 = 0.75
5 0.80
0.85
0.90
Concentric Circles
96.2
100.0 0.0
100.0 0.0
100.0 1: 0.0
84.6 1: 31.3
Mix ture of Caussians
100.0 0.0
0.3 0.3
100.0 - 0.0
0.0 0.0
100.0 0.0
0.0 + 0.0
100.0 1: 0.0
0.0 0.0
100.0 + 0.0
0.0 + 0.0
Chained Teii
96.0 5.0
0.4 0.2
100.0 0.0
0.0 0.0
100.0 0.0
0.0 + 0.0
1.0
0.0 0.0
97.6
0.0 0.0
Concentric Hyperholaids
5.5
0.4 1:
1.3e- 3.9e-3
100.0
0.0 0.0
1.0
0,0
0.0
A= le-3
A le-2
A 0.1
A 0.2
A 0.5
Concentric Cineles.
0.0 0.0
100.0.:00
0.0
0.0 0.0
2.7e-2 +: 2.3e-2
100.0 0.0
0.3 5.0ee2
100.0 0.0
100.0 1 100.0
12.7 1: 0.1
Mixtare Ganssians
0.0 0.0
0.0
4.6c-2 +: 1.9x-2
0.5 4.3r-2
13.8
0:2
89.2 29.8
100.0
100.0 0.0
100.0 +: 0.0
97.4 7.7
Cosezatic Hyperbolods
0.0
0.0
8.8c-2 5.2c-2
1.0
13.0 0.2
96.8 3.0
98.5 1.S.::3..0
100.0 4: 0.0
100.0 4: 0.0
99.8 4: 0.5
A.5.6 SCRNASEQ REAL DATA: UMAP AND TSNE
@ Exdtatory einbbtory @ Non-no
ORC-MASL
None
ORC-MANL
None
Figure 23: UMAP (McInnes et al. 2018a) 8a) and t-SNE (Van der Maaten & Hinton 2008) embeddings of scRNAseq data from 10000 Anterolateral Motor Cortex (ALM) brain cells in mice with base truth cell-type annotation with and without ORC-MANL pruming. Data available from Abdelaal et al. (2019) and the Allen Brain Institute.
Here we include UMAP Mcinnes et al.) 2018a) and t-SNE Van der Maaten & Hinton 2008 embeddings the of scRNAseg data of brain cells in mice that analyzed in Section 4.2
58

---

Published as a conference paper at ICLR 2025
Figure 23
shows embeddings of scRNAseq data from 10000 Anterolateral Motor Cortex (ALM)
brain cells in mice. Unlike the embeddings produced by Isomap (Tneebbumm et al. 2000) shown in Figure g find that UMAP and t-SNE do poorly with and without ORC-MANL pruning as measured by the extent to which neuronal (consisting of labels "Inhibitory" and "Excitatory") and non-neuronal cell communities are preserved.
A.5.7 MANIFOLD CURVATURE
8(x)
S(x) 0
S(x) =
Ollivier-Red Curvature
Figure 24: Empirical distribution of ORC for 2000 points sampled each from the Bolza surface, the flat torus and the unit 2-sphere using k-NN connectivity (left) and e-radius connectivity (right). The Bolza surface has scalar curvature -2, the flat torus has scalar curvature 0 while the sphere has scalar curvature +2. Note that for 2-dimensional surfaces such these, the scalar curvature is simply twice the Gaussian curvature.
Theoretical and empirical results from van der Hoorn et al. (2021) indicate that under noiseless and uniform sampling, specific instantiation of ORC converges the Ricci curvature of the underlying manifold from which the data was sampled (up to a constant of proportionality). This result could be point of concern for ORC-MANL, it would suggest variable performance manifold curvature. To quell any concern, in Figure 24 we plot the distribution of ORC values (computed with the formulation described in Section 2.3) for nearest neighbor graphs where points were sampled noiselessly from three different manifolds of varying curvature: the Bolza surface (scalar curvature 2), the flat Note that for surfaces such as these, the scalar curvature is simply twice the Ricci curvature.
function of
(scalar curvature and the unit sphere (scalar curvature +2).
In this experiment, we find minimal variation in the distribution of ORC values for the three man- ifolds. While this does not suggest invariance to curvature in general, we consider this to be an indication that for the regimes we expect to encounter in practice, underlying manifold curvature should not be significant cause for concern.
A.5.8 EMPIRICAL CONVERGENCE: THE SWISS ROLL
Figure 25 plots the ORC versus thresholded graph distance for all edges nearest neighbor graph built from noisy samples from the swiss roll. The figure also plots the thresholds indicated from the theoretical results detailed in Section 3 In this example, we see that all shortcut edges have ORC below -1 + 4(1 8). though some non-shorteut edges fall under this threshold too. But the figure also illustrates that all shorteut edges exceed the thresholded graph distance, while no non-shorteut edges do.
59

---

Published as a conference paper at ICLR 2025
Non-Shi Shortcut
Shortcut
1.0
Ollivier Ricci Curvature
0.0
-1.0
2.0
=(m+1)1-A1
2v/4X
Thresholded graph distance, de (u, v)
Figure 25: Plot of ORC versus thresholded graph distance der for all edges in an unpruned nearest neighbor graph the noisy 3D swiss roll. Dotted lines indicate theory-derived thresholds on ORC and thresholded- graph distance respectively. Note that we use 8 0.8, À 0.01 and = 3.
60


Reviews:
[{"review_id": "J7Lc5PgVfO", "reviewer": "Reviewer_7aFm", "summary": "The paper focuses on characterizing ``shortcut'' edges as edges that are essentially unfaithful to the geometric curvature and then designs a polynomial time algorithm to detect these edges. They first define discrete Ricci curvature corresponding to each edge, where a negative curvature implies shortcut edges. To further confirm that these edges are indeed shortcut edges, they ensure that the shortest distance between the corresponding vertices is sufficiently large if the shortcut edges are absent. \n\nThe algorithm is simple to understand, and the idea of negative Ricci curvature certainly shows promise in simulation settings when considering many different kinds of manifolds. The simulation results are quite rigorous, and the application to real-world data shows initial promise.", "questions": "1) The authors assume that the data comes from a smooth manifold $\\mathcal{M}$. However, real-world experiments are conducted on data with underlying clusters, where it makes more sense to assume that different clusters come from different manifolds (leading to multi-manifold structures [1] ). How do the theoretical guarantees of the paper hold in such a setting?\n\n2) For the PBMC dataset, while there are now fewer edges between different separated components of the UMAP/TSNE pictures, in my understanding, the overall UMAP/TSE embedding quality remains unchanged for both pruned and un-pruned nearest neighbor graph distances. Would this be a correct inference? Also, have the authors considered using datasets like Fashion-MNIST (which are quite well-studied in manifold learning literature) to better understand the usability of the method?\n\n3) How did the authors choose the parameters for the baseline algorithms? How did the authors choose the $\\lambda$ and $\\delta$ parameters for the real-world experiments?\n\n4) The authors have not commented on the run time complexity of the algorithm (I understand that it is a theoretical paper). I believe it should be $\\mathcal{O}(|V|^3)$. Is that correct? If so, have the authors attempted to develop faster algorithms via sampling/approximation style techniques?\n\n[1] Trillos, Nicolas Garcia, Pengfei He, and Chenghui Li. \"Large sample spectral analysis of graph-based multi-manifold clustering.\" Journal of Machine Learning Research 24.143 (2023): 1-71.", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "1) The algorithm aims to solve an important problem, pruning of ``bad edges'' in nearest-neighbor data embeddings with underlying manifold structures.\n\n2) The theoretical results of the papers (especially Theorem 3.2 and 3.3) are both simple to understand and insightful.  \n\n3) The algorithm performs very well on large simulation datasets. \n\n4) It also shows some promise in the real-world datasets (Improvement in the performance of ALM data for ISOMAP and reducing some inter-community edges in the PBMC dataset).", "weaknesses": "1) The primary weakness of the paper is that the application to real-world data is quite limited. The authors only consider $2$ real-world datasets. Experiments and verifications on more data (such as image datasets like Fashion-MNIST or K-MNIST) or embeddings of small document datasets would significantly increase confidence in the method. \n\n2) The robustness of the tolerance parameters $\\lambda$ and $\\delta$ are not well explored. This is especially important for the real-world datasets.\n\n3) The time complexity of the algorithm seems quite bad $\\mathcal{O}(|V|^3)$. This is a minor weakness, given the fact that the paper primarily focuses on a theoretically established idea.", "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": "", "extra_scores": {}}, {"review_id": "BrfcUgYa3q", "reviewer": "Reviewer_Dtcv", "summary": "The paper presents ORC-MANL, an algorithm aimed at refining the structure of nearest neighbor graphs by eliminating spurious \"shortcut\" edges that disrupt accurate manifold representations. This method uses Ollivier-Ricci curvature (ORC) to detect and prune edges that likely bypass the true manifold structure. By removing these shortcuts, ORC-MANL improves manifold accuracy, enhancing performance in downstream tasks such as clustering, manifold learning, and persistent homology.", "questions": "See weakness.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- ORC-MANL effectively removes shortcut edges, which often misrepresent relationships in the data by connecting distant points across the manifold. By pruning these edges, the algorithm preserves the true geometric and topological structure of the data, yielding a more accurate manifold representation.\n\n- It is supported by a solid theoretical basis showing how Ollivier-Ricci curvature identifies shortcut edges. Empirical results on synthetic and real datasets confirm that ORC-MANL effectively prunes unnecessary edges while preserving important connections, making it a robust choice across a range of data types and applications.\n\n- It operates with fixed parameters for curvature thresholds across different datasets, reducing the need for dataset-specific tuning. This consistency is an advantage over other methods that require careful parameter adjustment to perform optimally.\n\n- ORC-MANL demonstrates versatility across both synthetic and real-world datasets, including complex biological data like high-dimensional single-cell RNA sequencing. This adaptability makes it suitable for diverse data shapes and manifold structures.", "weaknesses": "- Calculating ORC involves complex optimal transport calculations and distance checks, which can be computationally intensive. This added complexity may limit ORC-MANL's scalability for large graphs or high-dimensional data, making it less suitable for applications requiring quick processing.\n\n- It seems to me that ORC-MANL’s performance depends on how the initial nearest neighbor graph is constructed, including choices like the number of neighbors k in k-NN graphs or the distance threshold ϵ in ϵ-radius graphs. Poorly chosen parameters can produce an inaccurate initial graph, which may reduce the effectiveness of ORC-MANL’s pruning. This sensitivity may require users to fine-tune parameters for each dataset to achieve the best results.\n\n- While ORC-MANL generally operates effectively with fixed parameters, the initial nearest neighbor graph setup (e.g., choosing k for k-NN graphs) may still need adjustment across different data types. This reliance on specific curvature thresholds and distance validations can impose extra processing time, especially in cases where the default settings don’t align well with the data structure.", "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": "", "extra_scores": {}}, {"review_id": "rcKaaSZv48", "reviewer": "Reviewer_rkDt", "summary": "In this paper, the authors propose using the Ollivier-Ricci curvature, calculated for each edge of graph, to prune graphs in machine learning methods that construct local graphs from data points. They develop an algorithm that removes edges that, due to noise, create shortcuts connecting the low-dimensional manifold formed by the data. Using synthetic data where the shortcuts are known, they demonstrate the ability to identify these shortcuts. Furthermore, they experimentally show that this approach is useful for tasks such as preprocessing for manifold learning methods like ISOMAP and UMAP, computing persistent homology, and intrinsic dimension estimation.", "questions": "Major question:\nSince the proposed ORC-based method is based on the idea of removing edges with highly negative curvature, wouldn't it perform poorly when the graph constructed using the epsilon-radius rule has an almost tree-like topology (i.e., graphs with very few cycles or triangles)? In other words, in graphs that are close to tree structures, a majority of edges may have negative curvature, and as a result, wouldn't the ORC-based method over-prune the graph?\n\n\nMinor questions:\nWhat does ORC-MANL stand for? While it's clear that ORC is Ollivier-Ricci curvature, there's no explanation of MANL. Since it is the proposed algorithm in this paper and an important term, it should be spelled out first before abbreviating.\n\nWhy is only Definition 2.1 enclosed in a box and emphasized in color? Other Propositions and Theorems are not treated this way; what is the reason for doing this only for this definition?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "Providing a method that can accurately prune shortcut edges—which significantly affect the performance of downstream tasks—using a relatively simple algorithm will have a major impact on many machine learning algorithms based on local graphs.", "weaknesses": "The presentation of the paper has considerable room for improvement.\n\nGiven the nature of the research, it's somewhat understandable that most of the content is described in the Appendix. However, it is undesirable that figures providing intuitive explanations of geometric concepts and constants (thresholds) that play important roles in the algorithm cannot be interpreted without consulting the Appendix. For example, rather than including numerous detailed experimental results, adding figures that intuitively explain the definition and properties of the minimum branch separation would contribute more to understanding after making rooms by moving one of two experimental results to the Appendix. Additionally, the fact that the basis for comparing with ORC, '-1 + 4(1 - δ)', is provided in Lemma A.1 hinders the understanding of the proposed algorithm.\n\nThe (weighted) shortest-path metrics \\( d_G \\) and \\( d_{\\mathcal{M}} \\) are not formally defined. These are very important quantities, and the discussion should proceed after giving precise definitions of them.\n\nIn Figures 4, 5, and 6, some words (upper left part of Figures) are displayed overlapping, making it impossible to discern what is written.\n\nIt has been pointed out that intrinsic dimension estimation using the MLE by Levina & Bickel has bias.\nhttps://www.inference.org.uk/mackay/dimension/\nIf the claim is that the proposed ORC-MANL preprocessing contributes to correct intrinsic dimension estimation, then a bias-reduced estimator should be used and discuss how their results might change with a different estimator.", "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": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Spotlight)