PaperlayerView exact revision on arXiv

Source-linked AI summary

Boundary Detection for High-Dimensional Point Clouds

Abigail Hickok, Valerio Galanti, Osama Al Dalahmah, Andrew J. Blumberg

arXiv:2610.23590v1cs.LGcs.CGstat.ML

TL;DR

Boundary detection in high-dimensional point clouds is challenging when density varies, noise is substantial, or intrinsic dimension is difficult to estimate. The paper introduces a local hyperplane method and a directional-uniformity method that return boundary scores and normals. The methods are tested on synthetic data and applied to tumor-boundary detection and LLM activation geometry.

  • Problem

    Boundary locations and normals are fundamental for point clouds supported on manifolds with boundaries, including high-dimensional spatial transcriptomics and activation data.

    Source: §1 · p. 1

  • Method

    The paper combines local dimension reduction and hyperplane fitting with a directional-uniformity score to detect boundaries and estimate normals.

    Source: §1.1 · p. 1, §2 · p. 3

  • Results

    The hyperplane method works best when local dimension is reliably estimated, while directional uniformity is more robust when noise prevents accurate dimension estimates.

    Source: §1.1 · p. 2

  • Takeaways & Limitations

    The methods identify a tumor boundary in spatial transcriptomics data and characterize boundaries of LLM activation manifolds.

    Source: §5 · p. 9, §7 · p. 10

    When noise leads local PCA to overestimate dimension, the hyperplane method can find the boundary of the thickened object rather than the underlying manifold.

    Source: §4 · pp. 7–8

Abstract

from arXiv · show

We introduce two new methods for boundary detection in high-dimensional point cloud data, intended to work in situations with non-uniform density, high ambient dimension, and substantial noise. Our first method fits a separating hyperplane on local neighborhoods after doing local dimension reduction---this method works best when one can reliably estimate the intrinsic dimension of the data. Our second method measures the directional uniformity of local neighborhoods, and has the best overall performance on synthetic data. In addition to pointwise numerical boundary scores, our algorithms yield an estimated normal vector at each boundary point. We validate our methodology on synthetic data as well as two real examples: we analyze spatial transcriptomics data, where we show that we can detect the boundary of a tumor, and we also study LLM activation geometry.

1 INTRODUCTION

Boundary detection in high-dimensional data matters for locating tissue transitions and studying manifold geometry, but existing approaches face density, dimension, and noise challenges. The paper introduces two methods that estimate boundary scores and normals, with different strengths depending on dimension-estimation reliability and noise.

1 INTRODUCTION

  • Boundary locations and normals matter in high-dimensional data because they can reveal tissue transitions and inform steering interventions on activation manifolds.The manifold hypothesis models point clouds as distributions supported on low-dimensional manifolds, and boundary detection can also support clustering.Source: §1 · p. 1

1.1 CONTRIBUTIONS

  • The hyperplane method performs best when local dimension is reliably estimated, while directional uniformity is more robust when noise disrupts dimension estimates.The hyperplane method is mathematically grounded and both methods are empirically validated on synthetic data.Source: §1.1 · p. 2
  • The methods identify a tumor boundary in spatial transcriptomics data and characterize the boundary of LLM activation manifolds.The LLM application studies the character-counting manifold in open-weight models.Source: §1.1 · p. 2

1.2 RELATED WORK

  • Density-based methods, including reverse-k-nearest-neighbor approaches and CO, perform poorly on non-uniform-density point clouds.Other reviewed methods scale poorly with ambient dimension or are less robust to noise; LoDD has the strongest overall performance among tested prior methods but does not produce normals.Source: §1.2 · p. 2

2 HYPERPLANE METHOD FOR BOUNDARY DETECTION

The hyperplane method distinguishes boundary from interior neighborhoods by finding a direction that places many neighbors on one side. It reduces each neighborhood locally, optimizes a separating hyperplane, and scores the point by the fraction of neighbors on its positive side.

2 HYPERPLANE METHOD FOR BOUNDARY DETECTION

  • The method models a boundary neighborhood as a half ball, where a separating hyperplane can place most neighbors on one side, unlike an interior neighborhood.For an interior point, any hyperplane roughly splits the neighborhood in half.Source: §2 · p. 3

2.1 THE ALGORITHM

  • Local PCA reduces each neighborhood to the known manifold dimension or, when unknown, a dimension selected using a spectral-gap threshold.The neighborhood is centered so the query point maps to the origin.Source: §2.1 · p. 3
  • The boundary score is the fraction of neighbors on the positive side of the optimized hyperplane, with boundary and interior scores near 1 and .5, respectively.The optimization maximizes a distance-based objective under a unit-norm constraint; this yields a fast closed-form solution.Source: §2.1 · p. 3
  • In half-ball and full-ball simulations, optimized-hyperplane accuracy stays near 1 and 1/2, respectively, through dimension 10.The gap persists at neighborhood size k = 10.Source: §2.1 · p. 4

2.2 CONCENTRATION INEQUALITIES FOR THE BOUNDARY SCORES

  • The concentration analysis assumes independent uniform samples from an n-dimensional ball or half ball, although the optimized direction makes score terms dependent.The stated theoretical results show scores concentrate near 1/2 for interior points and 1 for boundary points.Source: §2.2 · p. 4

3 DIRECTIONAL UNIFORMITY METHOD FOR BOUNDARY DETECTION

Directional uniformity detects boundaries through directional alignment among local neighborhoods. Its score is designed to reduce false boundary flags when noise thickens a manifold into a higher-dimensional object.

3 DIRECTIONAL UNIFORMITY METHOD FOR BOUNDARY DETECTION

  • The method projects neighbors onto a sphere centered at the query point and uses their directional vectors to assess local uniformity.For manifold points, the expected vector is zero; for boundary points, it is nonzero and parallel to the boundary normal.Source: §3 · p. 5
  • Expected scores at boundary points are strictly below 1 and depend on the manifold dimension.The method returns a boundary score for each point.Source: §3 · p. 5
  • The directional-alignment score is more robust to noise than simply using the norm of the mean direction vector.Boundary neighborhoods have stronger vector alignment because their expected direction vector is nonzero.Source: §3 · p. 5
  • In a noisy thin strip, opposing vectors from its two sides cancel, helping avoid flagging its top and bottom as true boundaries.The score is less likely than the mean-vector norm to flag interior points at fixed neighborhood size and high noise.Source: §3 · p. 5, Figure 2 · p. 5

4 BOUNDARY DETECTION ON SYNTHETIC DATA

Synthetic tests show that both HP and DU handle non-uniform density and high ambient dimension, while DU is more robust when noise makes local dimension estimates unreliable. HP can lead when its dimension is fixed or reliably estimated, and the methods also differ in their boundary-normal accuracy.

Surfaces with non-trivial geometry

  • Across six low-noise surfaces, all four methods are reasonably accurate overall, but BEPS produces false positives and LoDD confuses interior 1D points with boundaries.HP assigns scores near .75 near transverse intersections, while DU scores are higher at boundaries and close to 0 in the interior.Source: Figure 3 · p. 6, §4 · p. 6

Non-uniform density

  • On the non-uniform-density disk, LoDD, BEPS, HP, and DU each achieve AUC = 1, while RU, BORDER, and BP score below .5 and CO scores .447.The test compares boundary points with deep-interior points in a disk containing an interior low-density well.Source: Table 1 · p. 6, §4 · p. 6

High ambient dimension

  • In high ambient dimension, HP and DU show clear boundary contrast, whereas BEPS scores are roughly constant and LoDD has interior scores as low as boundary scores.HP has some interior noise and can score self-intersections as highly as boundary points in high ambient dimensions.Source: §4 · pp. 6–7, Figure 4 · p. 7
  • For 2D disks in R^D, HP and DU have AUC values near 1 across D = 3–15, while LoDD degrades; DU also has the highest R^2, near 1, at each D.LoDD's lower R^2 reflects high variance within the disk interior.Source: Figure 5 · p. 7, §4 · p. 7

Intersecting line segments

  • For noisy intersecting line segments, dimension overestimation makes HP detect thickened-arm edges; increasing k to 200 fixes HP, while DU identifies true boundaries at both neighborhood sizes.At k = 100, local PCA assigns 99.1% of points dimension 2; LoDD and BEPS share the limitation, and larger neighborhoods do not help them.Source: Figure 6 · p. 7, §4 · p. 8

Boundary normals

  • HP generally estimates boundary normals more accurately than DU, with the gap widening for 2D disks embedded in higher-dimensional spaces; on n-balls, both are equally accurate.For 2D disks in R^3, the gap narrows as noise increases; at σ = .1, HP's top two local principal components align less well with the tangent space.Source: Figure 8 · p. 8, §4 · p. 9

High noise levels

  • At σ = .05, HP with fixed dimension (AUC .969) leads DU (AUC .932), LoDD (AUC .868), BEPS (AUC .818), and HP with the spectral-gap threshold condition (AUC .816).When noise leads local PCA to overestimate dimension, fixing HP's dimension at 2 recovers the disk boundary; the authors recommend DU when intrinsic dimension cannot be reliably estimated.Source: §4 · p. 8

5 BOUNDARY DETECTION IN SPATIAL TRANSCRIPTOMICS DATA

The study applies boundary detection to glioblastoma spatial transcriptomics to recover cell-state boundaries. HP and DU scores rise at the tissue edge and near parts of the transition between mesenchymal- and proliferative-enriched regions.

5 BOUNDARY DETECTION IN SPATIAL TRANSCRIPTOMICS DATA

  • Spatial transcriptomics measures gene expression across a tissue section, and the study applies the methods to recover cell-state boundaries in glioblastoma.The authors analyze tissue slice ST1A1.Source: §5 · p. 9
  • RCTD abundance estimates define Mes and Pro groups, with the plotted contrast calculated as Mes minus Pro.Mes combines gl Mes1 and gl Mes2; Pro combines gl Pro1 and gl Pro2.Source: §5 · p. 9
  • Both HP and DU assign higher boundary scores along the tissue edge and near parts of the Mes/Pro-enriched transition.The results suggest internal tumor-state transitions can be detected without cell-state labels or predefined tumor-marker genes.Source: §5 · p. 9
  • The analysis uses ST1A1, combining 30 gene-expression principal components with two spatial coordinates for 741 spots in R32.Neighborhoods intersect nearest neighbors in spatial and gene-expression coordinates; HP uses fixed dimension two.Source: §5 · p. 9

6 LLM ACTIVATION GEOMETRY

The paper applies HP and DU to character-counting manifolds in Pythia-2.8B and Llama-3.1-8B activations. Both methods score the averaged manifold's ground-truth boundary higher, and averaged scores on the unaveraged token cloud are also consistently higher at that boundary.

6 LLM ACTIVATION GEOMETRY

  • The study reproduces the character-counting manifold for Pythia-2.8B and Llama-3.1-8B using C4 text with line widths from 15 to 150 characters.Newlines are reinserted at fixed character intervals, rounded to word boundaries.Source: §6 · p. 9
  • The point clouds average layer-4 residual-stream activations for each character position and line width, yielding about 2,300 points per model.Figure 10 presents the Pythia-2.8B cloud; Figure 19 presents Llama-3.1-8B.Source: §6 · p. 10, Figure 10 · p. 10
  • Both detectors assign higher scores to the averaged manifold's ground-truth boundary, where i = 0, i = w, w = 15, or w = 150.For HP, the authors set dimension n = 2 because the surface is parameterized by character position i and line width w; estimated normals tend to point inward.Source: §6 · p. 10
  • Averaged boundary scores for the unaveraged, per-token point cloud are consistently higher at the ground-truth boundary.Each model's token cloud has about 250,000 points; this setting is more challenging because intrinsic dimension is higher and unknown, with other unknown boundaries.Source: §6 · p. 10

7 CONCLUSIONS

The paper presents two methods for detecting boundary points and estimating boundary normals, and reports theoretical justification for HP, empirical comparisons, and applications to transcriptomics and LLM activations. The AI use statement says the authors reviewed the AI-assisted work and take responsibility for the final content.

7 CONCLUSIONS

  • The paper's two methods identify boundary points and calculate boundary normal vectors in high-dimensional, noisy data.The authors report mathematical justification for HP, empirical testing against literature methods on synthetic data, and real-world applications.Source: §7 · p. 10

AI USE STATEMENT

  • Generative AI wrote almost all code and assisted with isolated steps in proofs of Lemmas B.3–B.6.The authors state they reviewed the code and checked the mathematical arguments, and take responsibility for the final content.Source: AI USE STATEMENT · p. 10

A ADDITIONAL EXPERIMENTAL FIGURES

The appendix presents additional experiments spanning hyperplane optimization, non-uniform density, synthetic geometries, noise, intrinsic dimension, spatial transcriptomics, and Llama-3.1-8B activations.

A.1 HYPERPLANE OPTIMIZATION IN HALF AND FULL BALLS

  • Half-ball neighborhoods yield hyperplane accuracies .98 in 2D and .99 in 3D, versus .5 and .6 for full balls.The examples use k = 50 in 2D and k = 100 in 3D.Source: §A.1 · p. 12, Figure 11 · p. 13

A.2 NON-UNIFORM DENSITY

  • Figure 12 compares boundary points with low-density interior-well points on a non-uniform 2D disk, showing methods that handle density variation and methods that confuse the groups.The disk has 10,000 points and neighborhood size k = 100; the well density is one ninth of the outer region.Source: Figure 12 · p. 13, §A.2 · p. 13

A.3 SURFACES WITH NON-TRIVIAL GEOMETRY

  • Figure 13 adds boundary-score plots for four synthetic data sets with low noise, complementing earlier cone and saddle-skewer tests.Each cloud has 10,000 points and uses neighborhood size k = 100.Source: §A.3 · p. 13, Figure 13 · p. 14

A.4 HIGH AMBIENT DIMENSION

  • Figures 14 and 15 extend tests to surfaces and noisy 2D disks embedded in R15.Figure 15 uses Gaussian noise σ = .01, 10,000 points, and k = 100; the plots show only the first two coordinates.Source: §A.4 · p. 15, Figure 14 · p. 15, Figure 15 · p. 15

A.5 HIGH NOISE LEVELS

  • Figure 16 plots boundary scores for 2D disks embedded in R3 with isotropic Gaussian noise σ = .05.This is the highest noise level shown for the R3 disks.Source: §A.5 · p. 15, Figure 16 · p. 16

A.6 HIGH INTRINSIC DIMENSION

  • In a noisy 10-dimensional ball, all methods achieve AUC 1 except reverse unreachability, which has AUC .01.Boundary and interior points are defined by norms > .95 and .8, respectively; the 2D display is a thin slice of the 9-dimensional boundary.Source: §A.6 · p. 16, Figure 17 · p. 16

A.7 SPATIAL TRANSCRIPTOMICS

  • Figure 18 shows HP and DU boundary scores on glioblastoma slice ST1A1 at neighborhood sizes k = 75, 100, and 150.It extends the earlier displays at k = 150 for HP and k = 100 for DU.Source: §A.7 · p. 16, Figure 18 · p. 17

A.8 LLAMA-3.1-8B ACTIVATION GEOMETRY

  • For Llama-3.1-8B, the appendix shows the averaged character-counting manifold, detected boundaries, and per-position, per-width scores averaged from the unaveraged token cloud.Figure 19 also shows estimated normal vectors for the top 10% scoring boundary points.Source: §A.8 · p. 16, Figure 19 · p. 17

B.1 PROOF OF THEOREM 2.1 FOR INTERIOR MANIFOLD POINTS

The proof analyzes interior-point scores by bounding probabilities for neighborhoods sampled uniformly from an n-dimensional ball. It uses moment estimates and normal approximations to control those probabilities.

B.1 PROOF OF THEOREM 2.1 FOR INTERIOR MANIFOLD POINTS

  • Uniform sampling from the n-ball gives zero mean and covariance matrix 1/(n+2) times the identity.These statistics supply the moment bounds used in the probability analysis.Source: §B.1 · p. 18
  • The proof applies the Berry–Esseen theorem to approximate a sum of independent, mean-zero neighborhood contributions by a normal variable.The summands are projections of sampled points onto a conditioned direction.Source: §B.1 · pp. 18–19
  • The resulting bound on Q_nk follows after bounding the normal-tail term and the unit-ball volume ratio.The argument uses the monotonicity of the normal CDF after zero and Gautschi’s inequality.Source: §B.1 · pp. 19–20
  • The proof bounds the variance and covariance of indicator variables for the neighborhood events to control their joint behavior.The variance is Q_nk(1 − Q_nk), and the lemma supplies a covariance bound for k ≥ 3.Source: §B.1 · pp. 21–22

B.2 PROOF OF THEOREM 2.2 FOR BOUNDARY POINTS

For boundary points, the proof models neighborhoods as samples from a half-ball and bounds the probability that the neighborhood score has the wrong sign. It also specifies the local spectral-gap rule used to estimate intrinsic dimension.

B.2 PROOF OF THEOREM 2.2 FOR BOUNDARY POINTS

  • The proof models a boundary neighborhood as independent uniform samples from an n-dimensional half-ball whose first coordinate is nonnegative.It shows that the summed neighborhood vector concentrates near its mean, making the conditional wrong-sign probability small when the vector is sufficiently close.Source: §B.2 · pp. 24–25
  • For a half-ball sample, the first coordinate may have nonzero mean while the remaining coordinates have zero mean.The coordinate variances are derived using the same radial distribution as for the full ball.Source: §B.2 · p. 24
  • A Chebyshev bound controls deviations of the summed vector from its mean, and conditioning on that event bounds the wrong-sign probability.The proof then optimizes the deviation parameter to finish the bound.Source: §B.2 · pp. 25–26

C.1 INTRINSIC DIMENSION ESTIMATION

  • The local dimension estimate is the smallest index m for which consecutive covariance eigenvalues satisfy λ_m/λ_(m+1) > τ; otherwise the estimate is D.The default spectral-gap threshold is τ = 7.Source: §C.1 · p. 26

C.2 AUC VALUES FOR SYNTHETIC DATA EXPERIMENTS

Synthetic AUC rankings vary with noise and experimental settings: directional uniformity leads in some comparisons, while fixed-dimension hyperplanes lead in others. The appendix also describes further methodology for the LLM activation analysis.

C.2 AUC VALUES FOR SYNTHETIC DATA EXPERIMENTS

  • For varying ambient dimension and boundary thresholds, DU ranks ahead of HP and LoDD in the reported disk experiments.Figure 20 plots AUC against ambient dimension across thresholds τB from .91 to .98.Source: §C.2 · p. 26, Figure 20 · p. 27
  • At σ = .01 and .02, DU outperforms every method for thresholds .91 ≤ τB ≤ .94; at τB ≥ .95, fixed-dimension HP leads, closely followed by DU.Figure 21 plots AUC against noise level for 2D disks in R3.Source: §C.2 · p. 27, Figure 21 · p. 27
  • At σ = .05, fixed-dimension HP performs best across the tested boundary thresholds, followed by DU, LoDD, BEPS, and spectral-gap HP.Figure 22 plots AUC against ambient dimension for noisy 2D disks in R^D.Source: §C.2 · p. 27, Figure 22 · p. 28

C.4 LLM ACTIVATION GEOMETRY

  • The appendix notes that the paper also applies its boundary-detection algorithms to study LLM activation geometry.It points to results for Pythia-2.8B and Llama-3.1-8B and says the section details the methodology.Source: §C.4 · p. 29

C.4.1 DATA SET

The LLM activation analysis constructs token sequences with varied line widths, extracts layer-4 activations from two language models, and applies boundary detection to averaged and per-token manifolds.

C.4.1 DATA SET

  • The data comprise 28 C4 documents processed at 28 line widths, producing 784 sequences capped at 512 tokens.Documents were selected to have at least 400 non-whitespace characters, and the collection reached at least 250,000 non-newline tokens.Source: §C.4.1 · p. 29

C.4.3 AVERAGED MANIFOLD

  • Each token is labeled by its character position and line width, with position defined by the character count through the token’s end.The averaging procedure retains labels with at least five tokens, yielding 2,311 Pythia points and 2,335 Llama points.Source: §C.4.1 · p. 29, §C.4.3 · p. 29

C.4.2 MODELS AND LAYER SELECTION

  • The study uses Pythia-2.8B and Llama-3.1-8B, extracting residual-stream activations at layer 4 after selecting that layer by visual inspection.The models have dimensions 2560 and 4096, respectively, and each has 32 layers.Source: §C.4.2 · p. 29

C.4.4 BOUNDARY DETECTION ON THE AVERAGED MANIFOLD

  • For the averaged manifolds, PCA reduces the data to 30 dimensions before DU and fixed-dimension-2 HP run with neighborhood size 100.The manifolds are treated as intrinsically two-dimensional because they are parameterized by character position and line width; the methods also yield vectors shown for top-decile boundary scores.Source: §C.4.4 · pp. 29–30

C.4.5 BOUNDARY DETECTION ON THE UN-AVERAGED, PER-TOKEN MANIFOLD

  • For the per-token manifold, PCA reduces about 250,000 points to 30 dimensions, and HP uses the spectral-gap rule rather than fixed dimension 2.Boundary scores are averaged over tokens sharing each character-position and line-width pair.Source: §C.4.5 · p. 30

C.4.6 3D VISUALIZATION

  • The 3D visualizations use PC2–PC4 coordinates because a few outliers dominate the first principal component in both models.Source: §C.4.6 · p. 30

D OTHER BOUNDARY DETECTION VARIANTS

This section compares directional-uniformity and alternative neighborhood-vector scores, finding DU strongest overall across tested noise, dimension, and density settings.

D OTHER BOUNDARY DETECTION VARIANTS

Related papers

Loading 2610.23590v1…