Adaptive Neighborhood Selection for Non Uniform Data Distributions

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2640 papers845 conceptsfrozen 2026-10-04

In machine learning, the "neighborhood" of a data point is the foundation for understanding its context. Whether we are classifying 3D LiDAR points, detecting fraudulent transactions, or clustering soil samples, we rely on the assumption that a point’s identity is defined by its closest peers.

However, most traditional algorithms use a fixed definition of proximity—either a fixed number of neighbors ($k$) or a fixed spatial radius ($r$). This creates a "fixed-parameter fallacy": in regions where data is dense, a fixed radius might capture thousands of redundant points; in regions where data is sparse, a fixed $k$ might force the model to look so far away that it pulls in irrelevant information.

Adaptive neighborhood selection moves away from these rigid constraints. Instead of asking "Who are the 10 nearest neighbors?", these models ask, "How far must I look to find a stable geometric or semantic signal?"

Scaling the Receptive Field in 3D Space

The challenge of non-uniform density is most visible in 3D point clouds. In a LiDAR scan, objects close to the sensor are represented by thousands of points, while distant objects may only return a handful.

To address this, Shi Qiu and colleagues introduced the Dense-Resolution Network (DRNet), which learns a per-point dilation factor. This allows the model’s receptive field to adaptively expand in sparse regions and contract in dense areas. The intuition is similar to a camera lens: the model "zooms out" to capture the broad context of a sparse, distant car and "zooms in" to capture the fine-grained surface details of a nearby pedestrian.

A different approach to this problem is found in Reconfigurable Voxels. Tai Wang, Xinge Zhu, and Dahua Lin proposed using a biased random walk to group voxels. Instead of a rigid grid, voxels with low point density initiate a search that prioritizes transitions toward higher-density regions. This ensures that even sparse voxels accumulate enough geometric information to form a stable feature embedding before they are processed by the network.

Robustness through Density-Aware Pruning

In high-dimensional feature spaces, density isn't just about sensor distance; it’s about the "purity" of a neighborhood. In imbalanced datasets, rare classes often form "small disjuncts"—tiny clusters of points that are easily overwhelmed by the global majority. Bartosz Krawczyk argues that adaptive neighborhood estimation is essential here to preserve the structure of these rare sub-concepts, preventing them from being treated as noise.

When data is noisy, simply "looking further" can be dangerous. Tianqiang Huang and colleagues addressed this in their SANDI algorithm by introducing adaptive neighborhood pruning. By dynamically reducing the number of neighbors for points in low-density regions, they prevent the formation of "artificial bridges"—short-circuits in the data graph that would otherwise connect unrelated clusters and distort the global geometry.

Similarly, in the context of clustering, Dongxia Chang and the authors of CRG-clustering use an expansion radius derived from the average distance to the $k$-th nearest neighbor. This allows the boundaries of a cluster to "breathe," expanding where data is spread out and tightening where it is concentrated.

Topological Adaptation in Latent Spaces

Beyond physical or feature distance, some researchers argue that the very definition of a "neighbor" should be topological. Standard $k$-NN is "blind" to the internal structure of a neighborhood. For example, in word embeddings, a word like "bank" might have neighbors related to "finance" and "riverside" all mixed together.

The paper Navigating the Semantic Horizon suggests replacing $k$-NN with Relative Neighborhood Graphs (RNG). In an RNG, two points are connected only if there is no third point that is closer to both of them. This creates a dynamic neighborhood size that adapts to the local density and topology. It naturally captures all relevant "semantic directions" without needing a fixed $k$ that might be too small for common words or too large for rare ones.

This concept of "social context" is also vital in multi-object tracking. Qi Chu and the creators of the Graph Similarity Model (GSM) demonstrate that tracking performance improves when the system adaptively selects neighbors to model the topological relations between objects. In a dense crowd, the model focuses on immediate neighbors to distinguish between similar-looking targets; in a sparse scene, it expands its view to maintain identity through occlusions.

Why It Works: Information Stability

The shared intuition across these 444 papers is the pursuit of information stability. A fixed neighborhood is a gamble: you bet that the local density of your data is uniform. But real-world data is almost never uniform.

By making the neighborhood adaptive—whether through learned dilation in DRNet, biased walks in Reconfigurable Voxels, or topological constraints in RNGs—researchers ensure that every data point, regardless of its isolation or crowding, is processed with a consistent amount of "contextual evidence." This leads to models that are more robust to noise, more sensitive to rare events, and better at generalizing across the vast density variations of the real world.

Papers in this version

Showing 60 of 640 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 938 papers
  2. Version 1 · 2026-10-04 · 640 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_adaptive_neighborhood_selection_6545eee4,
  title = {adaptive neighborhood selection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adaptive-neighborhood-selection/rdr_6545eee40ef74763ae169b2f632d64f1},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_adaptive_neighborhood_selection_for_non__6545eee4_v1,
  title = {Adaptive Neighborhood Selection for Non Uniform Data Distributions},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/adaptive-neighborhood-selection-for-non-uniform-data-distributions/rdr_6545eee40ef74763ae169b2f632d64f1/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}