Neighborhood Size Sensitivity in Graph Construction

357 concepts349 papers1 proposal

Graphs are a powerful abstraction. They allow us to map complex, high-dimensional data into a discrete topological space where Graph Neural Networks (GNNs), spectral clustering, and label propagation algorithms can operate. However, most real-world datasets—such as text embeddings, image features, or single-cell RNA sequences—do not arrive with a ready-made network structure. They must first undergo a graph construction phase.

This phase introduces a critical, yet notoriously fragile, bottleneck: structural hyperparameters. Deciding a neighborhood's size—whether through the number of nearest neighbors ($k$) or a spatial radius threshold—is not merely a tuning detail. It fundamentally dictates the topology of the space the model will navigate, making downstream performance highly sensitive to these initial choices.

The Goldilocks Dilemma of Neighborhood Selection

To understand why graph-based models are so sensitive to neighborhood size, we have to look at what happens to the underlying data manifold when this parameter changes. Graph construction is essentially an attempt to approximate a continuous underlying space using discrete edges. This creates a strict trade-off between two catastrophic failure modes:

[Small Neighborhoods] <----------- [Optimal Balance] -----------> [Large Neighborhoods]
  - Graph fractures                  - Captures true                - Over-smoothing
  - Information loss                   data manifold                - Noise injection
  - Vulnerable to noise              - Stable topology              - Blurs cluster boundaries

1. Under-connectivity (Neighborhoods too small)

When the neighborhood size $k$ or the distance threshold is set too conservatively, the graph fractures into isolated components. Local structural variations and noise dominate the topology. As Zhang et al. observe in Kernel-Induced Label Propagation by Mapping for Semi-Supervised Classification, an underestimated neighborhood prevents the graph from maintaining global connectivity. Information cannot propagate effectively across the network, causing semi-supervised label propagation to stall due to information loss.

2. Over-connectivity (Neighborhoods too large)

Conversely, when the neighborhood size is too generous, the graph becomes overly dense. Edges begin to bridge distinct semantic clusters or separate sub-manifolds, injecting structural noise. Ren et al. emphasize this tension in Self-Supervised Graph Attention Networks for Deep Weighted Multi-View Clustering, noting that while too few neighbors lead to information loss, too many neighbors introduce severe noise that blurs the boundaries between clusters, degrading downstream classification and clustering performance.

Why a Universal Default Fails

If a single dataset had a perfectly uniform distribution, finding the optimal neighborhood size would be trivial. But real-world data manifolds are highly irregular, meaning a fixed hyperparameter cannot fit the entire dataset.

Papp et al. demonstrate in DropGNN: Random Dropouts Increase the Expressiveness of Graph Neural Networks that the effectiveness of neighborhood-based sampling and aggregation is intrinsically tied to local graph density and average node degrees. A neighborhood size that perfectly captures the geometry of a dense region will completely isolate nodes in a sparse region. Conversely, a parameter large enough to connect sparse outliers will turn dense clusters into uninformative, fully connected cliques.

This spatial non-uniformity means that structural hyperparameters must be manually adjusted not just from dataset to dataset, but often from region to region within the same graph.

The Ripple Effect Across Domains

This sensitivity is not isolated to standard node classification; it ripples across every domain that leverages graph-based representations.

  • Single-Cell Biology: In transcriptomics, visualization tools like SPRING rely on $k$-NN graphs to map continuous cell differentiation pathways. A slight miscalibration of $k$ can artificially fracture a continuous biological process into discrete, non-existent cell types, or merge distinct evolutionary lineages into a single path.
  • Neuroscience: Ng demonstrates in Detecting Brain Activation in fMRI Using Group Random Walker that when constructing inter-subject connectivity maps for fMRI analysis, the model's ability to detect localized brain activation is highly sensitive to the exact number of neighbors chosen to bridge different subjects' anatomical regions.
  • Natural Language Processing: When transforming text into graphs, the choice of the sliding window size for edge creation dictates the density of the text representation. Gao et al. show in Learning Graph Pooling and Hybrid Convolutional Operations for Text Representations that this parameter significantly alters the network's ability to capture long-range semantic dependencies versus local syntactic structures.

Mitigating Sensitivity: Alternative Topologies

To break free from the fragility of manual neighborhood selection, researchers are exploring architectures that either adapt to local density or bypass rigid neighborhood definitions entirely.

One prominent direction is the use of graph ensembles. Instead of relying on a single $k$-NN graph, Carreira-Perpiñán et al. propose in Proximity Graphs for Clustering and Manifold Learning using ensembles of Minimum Spanning Trees (MSTs). This approach ensures baseline global connectivity while remaining robust to noise across multiple scales.

Other frameworks attempt to replace static neighborhood boundaries with dynamic or path-based operators. For example, Eliasof et al. develop pathGCN: Learning General Graph Spatial Operators from Paths, which learns spatial filters from random paths rather than a fixed graph Laplacian. However, even these modern alternatives shift the sensitivity to new parameters, such as path lengths and sampling depths.

As Xiong highlights in SLRL: Structured Latent Representation Learning for Multi-view Clustering, the persistent reliance on manual neighbor selection across the literature underscores a foundational challenge: until graph construction can automatically and dynamically adapt to the local density of a data manifold, structural hyperparameter sensitivity will remain a core constraint in graph-based machine learning.

History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_hyperparameter_sensitivity_neighborhood__65281570,
  title = {hyperparameter sensitivity (neighborhood size sensitivity)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/hyperparameter-sensitivity-neighborhood-size-sensitivity/rdr_652815703f104eb789f624b37338e246},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 1, frozen text):

@misc{lacuna_hyperparameter_sensitivity_neighborhood__65281570_v1,
  title = {hyperparameter sensitivity (neighborhood size sensitivity)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/hyperparameter-sensitivity-neighborhood-size-sensitivity/rdr_652815703f104eb789f624b37338e246/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake