kNN-Graph: k-최근접 이웃을 위한 적응형 그래프 모델

kNN-Graph: An adaptive graph model for $k$-nearest neighbors

k-최근접 이웃(kNN) 알고리즘은 인공지능 분야의 비모수 분류의 핵심이지만, 대규모 응용 분야에 적용할 때 추론 속도와 정확성 간의 균형 때문에 어려움을 겪습니다. 기존의 근사 최근접 이웃 솔루션은 검색 속도를 높이지만, 종종 분류 정확도를 저하시키고 최적의 이웃 크기(k)를 선택하는 데 적응성이 부족합니다. 본 연구에서는 추론 지연 시간을 계산 복잡도와 분리하는 적응형 그래프 모델을 제시합니다. 계층적 탐색 가능한 작은 세상(HNSW) 그래프와 미리 계산된 투표 메커니즘을 통합함으로써, 제안하는 프레임워크는 이웃 선택 및 가중치의 계산 부담을 완전히 학습 단계로 이전합니다. 이 토폴로지 구조 내에서, 상위 그래프 계층은 빠른 탐색을 가능하게 하고, 하위 계층은 노드별 결정 경계를 정밀하게 인코딩하며, 적응적인 이웃 수를 사용합니다. 6개의 다양한 데이터 세트에서 8개의 최첨단 기준 모델과 비교한 결과, 이 아키텍처가 분류 정확도를 손상시키지 않고 추론 속도를 크게 향상시켜 실시간 성능을 달성함을 보여줍니다. 이러한 결과는 kNN의 오랜 추론 병목 현상에 대한 확장 가능하고 견고한 솔루션을 제공하며, 그래프 기반 비모수 학습에 대한 새로운 구조적 패러다임을 제시합니다.

The k-nearest neighbors (kNN) algorithm is a cornerstone of non-parametric classification in artificial intelligence, yet its deployment in large-scale applications is persistently constrained by the computational trade-off between inference speed and accuracy. Existing approximate nearest neighbor solutions accelerate retrieval but often degrade classification precision and lack adaptability in selecting the optimal neighborhood size (k). Here, we present an adaptive graph model that decouples inference latency from computational complexity. By integrating a Hierarchical Navigable Small World (HNSW) graph with a pre-computed voting mechanism, our framework completely transfers the computational burden of neighbor selection and weighting to the training phase. Within this topological structure, higher graph layers enable rapid navigation, while lower layers encode precise, node-specific decision boundaries with adaptive neighbor counts. Benchmarking against eight state-of-the-art baselines across six diverse datasets, we demonstrate that this architecture significantly accelerates inference speeds, achieving real-time performance, without compromising classification accuracy. These findings offer a scalable, robust solution to the long-standing inference bottleneck of kNN, establishing a new structural paradigm for graph-based nonparametric learning.