[KDD 2020] Voronoi Graph Traversal in High Dimensions with Applications to Topological Data Analysis and Piecewise Linear Interpolation
Aug 13, 20201 views
Voronoi diagrams and their dual, the Delaunay complex, are two,fundamental geometric concepts that lie at the foundation of many,machine learning algorithms and play a role in particular in classical piecewise linear interpolation and regression methods. More,recently, they are also crucial for the construction of a common,class of simplicial complexes such as Alpha and Delaunay-Čech,complexes in topological data analysis. We propose a randomized,approximation approach that mitigates the prohibitive cost of exact,computation of Voronoi diagrams in high dimensions for machine,learning applications. In experiments with data in up to 50 dimensions, we show that this allows us to significantly extend the use,of Voronoi-based simplicial complexes in Topological Data Analysis (TDA) to higher dimensions. We confirm prior TDA results,on image patches that previously had to rely on sub-sampled data,with increased resolution and demonstrate the scalability of our,approach by performing a TDA analysis on synthetic data as well,as on filters of a ResNet neural network architecture. Secondly, we,propose an application of our approach to piecewise linear interpolation of high dimensional data that avoids explicit complete,computation of an associated Delaunay triangulation.