Topological Trajectory Classification and Landmark Inference on Simplicial Complexes
Vincent P. Grande, Josef Hoppe, Florian Frantzen, Michael T. Schaub · 2024
Read Topological Trajectory Classification and Landmark Inference on Simplicial Complexes by Vincent P. Grande, Josef Hoppe, Florian Frantzen, Michael T. Schaub (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-03145.txt.
Introduction
Vincent Grande and co-authors tackle the sorting of paths across a surface in work from 2024. The surface is modeled as a mesh of triangles, and each path is a flow along its edges.
Past methods mapped paths into a special space tied to holes in the surface, which fails when the surface has no holes. The authors treat the fix as a sensor placement task: they search for triangles whose removal creates useful holes that best split the path classes. The same idea is then extended to cases where path labels are not given in advance.
Catalog record
| CREATOR | Vincent P. Grande, Josef Hoppe, Florian Frantzen, Michael T. Schaub |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 27 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-03145
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Topological Trajectory Classification and Landmark Inference on Simplicial Complexes Thanks: Funded by the Ministry of Culture and Science ( MKW ) of the German State of North Rhine-Westphalia (“ NRW -Rückkehrprogramm”), the German Research Council ( DFG ) within Research Training Group 2236 ( U n RAV e L ) and the European Union ( ERC , HIGH-HOP e S , 101039827). Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the European Union or the European Research Council Executive Agency. Neither the European Union nor the granting authority can be held responsible for them. Vincent P. Grande, Josef Hoppe, Florian Frantzen, Michael T. Schaub Abstract We consider the problem of classifying trajectories on a discrete or discretised 2 2 -dimensional manifold modelled by a simplicial complex. Previous works have proposed to project the trajectories into the harmonic eigenspace of the Hodge Laplacian, and then cluster the resulting embeddings. However, if the considered space has vanishing homology (i.e., no “holes” ), then the harmonic space of the 1 1 -Hodge Laplacian is trivial and thus the approach fails. Here we propose to view this issue akin to a sensor placement problem and present an algorithm that aims to learn “optimal holes” to distinguish a set of given trajectory classes. Specifically, given a set of labelled trajectories, which we interpret as edge-flows on the underlying simplicial complex, we search for 2 2 -simplices whose deletion results in an optimal separation of the trajectory labels according to the corresponding spectral embedding of the trajectories into the harmonic space. Finally, we generalise this approach to the unsupervised setting. I Introduction Trajectory data appears in a wide range of applications and settings. Human mobility data can be abstracted as trajectories [ 1 ] , ocean currents can be studied using trajectories of so-called ocean drifters [ 2 ] , animal movement has attracted the interest of biologists and ecologists [ 3 ] , and finally traffic patterns are relevant for city and traffic planning [ 4 ] . These cases do not only differ in the field of application, but also in the domain of the trajectories. Usually, trajectories are either assumed to live in continuous real dimensional space \mathbb{R}^{d} , or on discretised spaces modelled as graphs. Simplicial Complexes (SCs) are generalisations of graphs that also model higher-order geometry and topology and have been shown to be useful for trajectory classification using ’landmark’ faces [ 5 , 6 , 7 ] . Common to all of these approaches is that they classify trajectories classes based on the relation between the trajectories and the landmarks, in particular, how much each trajectory goes around the landmarks. In real-world data, landmarks can correspond to islands separating ocean flows, high mountains disrupting animal movement patterns, or poorly accessible regions of a city dividing traffic flows. While [ 5 ] use random walks and transformations to obtain edge weights, [ 7 ] leverage ideas from differential geometry and topological data analysis, and [ 6 ] view the problem from a network-science perspective. From a mathematical point of view, they interpret the trajectories as edge flow data and then project them into the harmonic space, which is defined as the kernel of the so-called Hodge Laplacian. All of these approaches rely on prior knowledge of the underlying topology of the network. However, in many abstract networks and applications, the set of landmarks or the topology is something we do not know a-priori and what we need to infer from the trajectory data. This is in general a very complex problem and the key challenge that we aim to address in this paper. Related work. The field of signal processing over simplicial complexes has been studied in [ 8 , 9 , 10 ] , utilizing the Hodge Laplacian and its eigenvectors (see also [ 11 ] ). The flow embedding of trajectories into the harmonic space of the Hodge Laplacian was first considered in [ 12 ] and used for outlier detection in [ 6 ] . Recent literature on trajectory prediction and analysis on topological spaces includes [ 13 , 5 ] . The opposite problem is considered in [ 14 , 15 ] , where the authors start with a graph without higher-order structure and learn simplices/cells to add to provide a sparse representation of given edge flows. Other applications of the harmonic space of the Hodge Laplacian can be found in [ 16 , 17 ] . Contributions and Outline. We propose a novel method to classify trajectories on higher-order networks using discrete Hodge Theory. In particular, our method a) extracts the hidden structure/topology of the underlying network based on the trajectory data using landmarks which serve as “holes” , b) classifies the trajectories using the landmarks extracted before, and c) works both in an supervised and an unsupervised setting. We will give background on SC s and discrete Hodge Theory in Section II , introduce our landmark inference method in Section III , will report results on synthetic and real-world data in Section IV , and discuss future work in Section V . II Background In this section, we will give a brief background on simplicial complexes ( SC s) and discrete Hodge Theory for processing edge data. For an introduction to algebraic topology or signal processing on SC s, we refer the reader to [ 18 ] and [ 9 ] . Simplicial complexes. Simplicial complexes are a generalisation of graphs that allow for interactions between more than 2 nodes in a structured way. A simplicial complex \mathcal{S} is a pair (V,S) of a finite set V called vertices and a set S of non-empty subsets of V such that (i) S is closed under taking non-empty subsets and (ii) every vertex is contained in a simplex, i.e. \bigcup_{\sigma\in S}\sigma=V . We call the (k+1) -element subsets of S the k -simplices and denote them by S_{k} . As SC s are generalised graphs, we can identify 0 -simplices with nodes, 1 -simplices with edges, and 2 -simplices with “closed triangles” . For bookkeeping purposes, we fix an ordering of V which allows us to associate a unique ordered tuple (v_{0},\dots,v_{k}) to every k -simplex. We can view this as a reference orientation on the k -simplices for k>0 . Furthermore, we denote by the k -th signal space C_{k} the \mathbb{R} -vector space \mathbb{R}[S_{k}] generated by the set of k -simplices S_{k} and set C_{-1} to be trivial. Elements of C_{1} are signals on oriented edges and we will thus view them as edge flows . We can then define the boundary operators B_{k}(\mathcal{S})\colon C_{k}\to C_{k-1} for k\geq 0 , by B_{k}(\mathcal{S})\colon(v_{0},\dots,v_{k})\mapsto\sum_{i=0}^{k}(-1)^{i}(v_{0},\dots,\hat{v_{i}},\dots,v_{k}) , where \hat{v_{i}} denotes the omission of the i -th entry v_{i} . We will drop \mathcal{S} from the notation if the SC is clear from context. The first boundary operator B_{1} corresponds to the edge-vertex incidence matrix of the underlying graph of the SC . Discrete Hodge Theory and the Hodge Laplacian. As the signal spaces C_{i} are finite-dimensional and have an inner product induced by the orthonormal simplex basis, the boundary operators B_{k} have a matrix representation and a well-defined