Adaptive spatial blocking for scalable clustering inference with applications to high-throughput spatial proteomics

Technical Summary: Adaptive Spatial Blocking for Scalable Clustering Inference

Problem Statement
The analysis of spatial point patterns, particularly in high-throughput spatial proteomics, relies heavily on Ripley's $K$-function to assess clustering. However, existing $K$-based methods, including the recently proposed $KAMP$ framework (Wrobel and Song, 2024), face severe computational bottlenecks when applied to large-scale datasets containing hundreds of thousands to millions of points. Traditional permutation tests require $O(n^2)$ distance calculations, and even the analytical moment-based $KAMP$ approach, while faster, still demands storing pairwise distances for all points, leading to prohibitive memory usage and quadratic computational complexity ($O(n^2)$) as sample sizes increase. Subsampling strategies like independent thinning offer a partial solution but result in significant loss of spatial information and statistical power, failing to fundamentally resolve the quadratic complexity.

Methodology
To address these scalability challenges, the authors propose B-KAMP (Block-based KAMP), a spatial clustering inference framework built upon an adaptive spatial blocking algorithm.

1. Adaptive Spatial Blocking Algorithm:
   The core of the method is an algorithm that partitions a large observation window into a collection of disjoint rectangular blocks. The algorithm operates in three stages:

   • Grid Representation: The domain is discretized into an $R \times C$ grid where each cell contains at most $\sqrt{n}$ points.
   • Block Identification (Phases I & II): Using a histogram-based approach inspired by the "largest rectangle in a histogram" problem, the algorithm iteratively identifies rectangular subregions satisfying specific constraints:
     • Minimum Size: Blocks must contain at least $\sqrt{m}$ points of interest (POIs) and a sufficient number of background points to ensure a non-degenerate permutation distribution.
     • Aspect Ratio: Blocks are constrained by a maximum aspect ratio $\rho$ to ensure statistical stability (avoiding highly elongated shapes that bias edge-corrected estimators).
     • The algorithm prioritizes selecting blocks with the smallest total point counts to maximize the number of disjoint blocks and maintain computational efficiency.
   • Block Complement (Phase III): Residual grid cells not assigned to blocks are iteratively merged into adjacent blocks by expanding the block boundaries to the minimal bounding rectangle, provided the resulting block remains disjoint from others and satisfies the aspect ratio constraints. This minimizes spatial coverage loss.

2. Block-Based Test Statistic:
   Within each identified block $i$, the method computes a standardized $K$-function statistic $Z_i(r)$ using the analytical moments derived from the $KAMP$ framework under a conditional label-permutation null distribution.

   • The global test statistic $Z(r)$ is defined as a weighted sum of the block-level statistics: $Z(r) = \sum w_i Z_i(r)$.
   • The weights $w_i$ are chosen proportional to $n_i/p_i$ (where $n_i$ is the total points and $p_i$ is the local prevalence of POIs in the block) to upweight blocks with sparse signals.
   • Under the conditional blockwise permutation null, the authors prove that as the number of blocks $b \to \infty$, the global statistic $Z(r)$ converges in distribution to a standard normal distribution $\mathcal{N}(0,1)$ via the Lyapunov Central Limit Theorem. This allows for fast $p$-value computation without empirical permutation replicates.

3. Extension to Bivariate Analysis:
   The framework is extended to test for spatial colocalization between two point types (e.g., plasma cells and macrophages) using a bivariate $K$-function estimator, with analogous block-level standardization and aggregation.

Key Contributions

• Scalable Algorithm: The development of an $O(RC)$ adaptive spatial blocking algorithm that efficiently identifies valid rectangular blocks for large-scale point patterns, avoiding the $O(n^2)$ complexity of full-window pairwise calculations.
• Statistical Framework: The formulation of a block-based clustering test that aggregates local evidence through a weighted sum, leveraging asymptotic normality for rapid inference.
• Practical Implementation: The provision of a general-purpose blocking strategy applicable to various scalable spatial methods, with code made available via GitHub.

Results

• Simulation Studies:

  • Computational Efficiency: B-KAMP scales linearly with the number of points and remains feasible for datasets with up to 100,000 points. In contrast, full-window $KAMP$ fails due to memory constraints at $n \ge 40,000$, and thinned $KAMP$($KAMP_{0.25}$) remains computationally expensive. B-KAMP is consistently the fastest method for large $n$.
  • Statistical Power: While full-window methods generally achieve the highest power when feasible, B-KAMP demonstrates competitive power, particularly at radii $r \approx 0.15$ (relative to the block size). It outperforms heavily thinned methods ($KAMP_{0.25}$) and maintains valid Type I error control.
  • Robustness: The method shows robust performance across varying point abundances and grid resolutions.

• Real Data Application (Spatial Proteomics):

  • Applied to a dataset of healthy human intestine tissue (approx. 2.6 million cells across 65 images).
  • The method successfully detected strong spatial aggregation of plasma cells and significant colocalization between plasma cells and macrophages.
  • B-KAMP provided stronger statistical evidence (lower $p$-values) than thinned $KAMP$ baselines for large images and scaled favorably where full-window methods exceeded available memory.

Significance and Claims
The paper claims that B-KAMP offers a favorable balance between statistical power and computational efficiency, enabling rigorous spatial clustering inference for high-throughput spatial proteomics data that was previously computationally prohibitive. The authors position the method not as a replacement for full-window procedures in small datasets, but as a necessary scalable alternative for large-scale images where traditional methods fail.

The authors maintain a modest stance regarding limitations:

• The method is a conditional blockwise test, meaning it does not utilize spatial relationships across block boundaries, potentially attenuating clustering patterns that span multiple blocks and resulting in some loss of power compared to full-window methods.
• The performance depends on the initial grid resolution and the greedy nature of the block complement step (Phase III).
• Future work is suggested to include data-driven grid selection, global optimization for block shapes, and extensions to 3D spatial data.