Adaptive kNN graph model.

Area of Science:

• Artificial Intelligence
• Machine Learning
• Computer Science

Background:

• The k-nearest neighbors (kNN) algorithm is fundamental for non-parametric classification but faces scalability challenges due to the speed-accuracy trade-off.
• Current approximate nearest neighbor methods often reduce classification precision and lack adaptive neighborhood size selection.
• Large-scale kNN deployment is hindered by inference latency and computational complexity.

Purpose of the Study:

• To develop an adaptive graph model that decouples inference latency from computational complexity in kNN.
• To enhance the speed and scalability of kNN classification for real-time applications.
• To provide a robust and adaptable solution for the inference bottleneck in kNN.

Main Methods:

• An adaptive graph model integrating Hierarchical Navigable Small World (HNSW) with a pre-computed voting mechanism.
• Transferring the computational burden of neighbor selection and weighting to the training phase.
• Utilizing a multi-layered topological structure for efficient navigation and precise decision boundary encoding.

Main Results:

• The proposed framework achieves real-time inference speeds without compromising classification accuracy.
• Demonstrated significant acceleration in inference speeds across six diverse datasets compared to eight state-of-the-art baselines.
• The adaptive graph model effectively addresses the inherent inference bottleneck of kNN.

Conclusions:

• The adaptive graph model offers a scalable and robust solution for kNN inference.
• This approach lays an adaptive structural foundation for graph-based non-parametric learning.
• The method successfully balances inference speed and classification accuracy in large-scale applications.