Euler characteristic curves
Davide Gurnari · 2020
The goal of this thesis is to develop an efficient way of computing Euler Characteristic Curves (ECC) of high dimensional datasets and use it as a descriptor of the data. The Euler characteristic for a simplicial complex is the alternate sum of its Betti number, or equivalently alternating sum of numbers of simplices of following dimension. For a filtered complex the Euler curve is a function that assigns an Euler number for each level of filtration. The main advantage is that the Euler Characteristic is addictive, hence we can compute it locally without having to explicitly build up the whole simplicial complex. This allows us to significatively reduce both time and memory requirements and allows us to use topological tools for much larger datasets compared to, for instance, persistent homology. We introduce two algorithms to create a local Vietoris-Rips complex from a point cloud and compute its Euler Characteristic Curve up to a certain filtration level by keeping track of each simplex’s contribution. We present a data structure to optimize the spatial search performed by our algorithms and compute the ECC in a distributed fashion. On common computer clusters, this procedure allows us to build complexes composed of up to 1010 simplices. To our knowledge this is at least two orders of magnitude above the limit for state of the art software. The algorithm is based on an idea of constructing a Vietoris-Rips complex in a distributed algorithm in a way that each simplex is considered at exactly one node of the cluster. We show the results of classification experiments on both synthetic point clouds and real world graphs, for which we use the vectorized ECCs as input for a SVM or NN classifier. Our results over some graph datasets are comparable to the state-of-the-art models.