Semantic Neighborhood Fidelity of NN-Descent Graphs for Text Embeddings

Approximate 𝑘 nearest neighbor (𝑘-NN) graphs are widely used to support similarity search, content organization, recommendation, and graph-based learning over text embeddings. Their quality is commonly assessed through Recall@𝑘, which measures agreement with exact nearest-neighbor identities. However, Recall@𝑘 does not indicate whether approximate neighborhoods preserve the category-level agreement observed in exact neighborhoods. This paper investigates approximate cosine 𝑘-NN graphs constructed with NN-Descent over labeled text embedding collections. The evaluation compares exact-neighbor recovery with category-level agreement among approximate neighbors and defines relative semantic neighborhood fidelity, denoted Fidelity@𝑘, with respect to the category consistency of the corresponding exact 𝑘-NN graph. By varying neighborhood size and examining NN-Descent refinement iterations, the study characterizes the relationship between exact-neighbor recovery and category-level neighborhood preservation. Across the evaluated datasets and embedding models, Fidelity@𝑘 remains consistently higher than Recall@𝑘, showing that approximate graphs can preserve category-level neighborhood agreement even when exact-neighbor recovery remains incomplete.