Scalable Approximate KNN for Latent Graph Learning

Abstract

The field of Latent Graph Learning addresses problems where learning an implicit graph over the input data can help tackle the task more effectively. During the graph creation process, the standard approach leverages a pair-wise distance matrix, which results in a scalability issue given its quadratic cost. In this paper, we illustrate the problem by analysing some significant works from the field, and then present our proposed solution. We develop an efficient approximate KNN algorithm that leverages a hierarchical data structure, and compare it to the naive approach in terms of graph quality, time-space complexity, and training performance. We show that we significantly outperform standard solutions in memory efficiency.

Authors

• Federico Rios
• Francesco Puddu