Simplicial complex | EPFL Graph Search

In mathematics, a simplicial complex is a set composed of points, line segments, triangles, and their n-dimensional counterparts (see illustration). Simplicial complexes should not be confused with the more abstract notion of a simplicial set appearing in modern simplicial homotopy theory. The purely combinatorial counterpart to a simplicial complex is an abstract simplicial complex. To distinguish a simplicial complex from an abstract simplicial complex, the former is often called a geometric simplicial complex. Definitions A simplicial complex \mathcal{K} is a set of simplices that satisfies the following conditions: :1. Every face of a simplex from \mathcal{K} is also in \mathcal{K}. :2. The non-empty intersection of any two simplices \sigma_1, \sigma_2 \in \mathcal{K} is a face of both \sigma_1 and \sigma_2. See also the definition of an abstract simplicial complex, which loosely speaking is

Collapse-invariant properties of spaces equipped with signals or directions

Stefania Ebli

Collapsing cell complexes was first introduced in the 1930's as a way to deform a space into a topological-equivalent subspace with a sequence of elementary moves. Recently, discrete Morse theory techniques provided an efficient way to construct deformation retracts collapsing one space into the other while preserving global topological properties. This type of collapse, called a Morse matching, has been widely used to speed up computations in (persistent) homology by reducing the size of complexes. Unlike classical collapses, in this thesis we consider topological spaces equipped with signals or directions. The main goal is then to reduce the size of the spaces while preserving as much as possible of both the topological structure and the properties of the signals or the directions. In the first part of the thesis we explore collapsing in topological signal processing. In this context, each signal on the cells of a complex is processed using the combinatorial Laplacian and the resultant Hodge decomposition.In Article 2.1 we provide an approach to signal compression and reconstruction on chain complexes that leverages the tools of algebraic discrete Morse theory. We first prove that any deformation retract of real finite-dimensional based chain complex is equivalent to a Morse matching. We then study the interaction between the Hodge decomposition and signal compression and reconstruction. Specifically, we prove that parts of a signal's Hodge decomposition are preserved under compression and reconstruction for specific classes of discrete Morse deformation retracts of a given based chain complex. Finally, we provide an algorithm to compute Morse matchings with minimal reconstruction error.Complementary to our theoretic results in topological signal processing, we provide two applications in this field. Article 2.2 extends graph convolutional neural networks to simplicial complexes, while Article 2.3 presents a novel algorithm, inspired by the well-known spectral clustering algorithm, to embed simplices in a Euclidean space. The object of our studies in the second part of the thesis is topological spaces equipped with a sense of direction. In the directed setting, the topology of the space is characterized by directed paths between fixed initial and terminal points. Motivated by applications in concurrent programs, we focus on directed Euclidean cubical complexes and their spaces of directed paths.In Article 3.1 we define a notion of directed collapsibility for Euclidean cubical complexes using the notion of past links, a combinatorial local representations of cubical complexes. We show that this notion of collapsability preserves given properties of the directed path spaces. In particular, we give sufficient conditions for a directed Euclidean cubical complex to have a contractible or a connected space of directed paths from a fixed initial vertex.In Article 3.2 we extend these results, providing further conditions for directed collapses to preserve the contractability or conneectdness of spaces of directed paths. Furthermore, we provide simple combinatorial conditions for preserving the topology of past links. These conditions are the first step towards developing an algorithm that checks at each iteration if a collapse preserves certain properties of the directed space.

EPFL2022

Reduced representations of complexes, signals, and multifiltrations

Celia Camille Hacker

The field of computational topology has developed many powerful tools to describe the shape of data, offering an alternative point of view from classical statistics. This results in a variety of complex structures that are not always directly amenable for machine learning tasks. We develop theory and algorithms to produce computable representations of simplicial or cell complexes, potentially equipped with additional information such as signals and multifiltrations. The common goal of the topics discussed in this thesis is to find reduced representations of these often high dimensional and complex structures to better visualize, transform or formulate theoretical results about them. We extend the well known graph learning algorithm node2vec to simplicial complexes, a higher dimensional analogue of graphs. To this end we propose a way to define random walks on simplicial complexes, which we then use to design an extension of node2vec called k-simplex2vec, producing a representation of the simplices in a Euclidean space. Furthermore, the study of this method leads to interesting questions about robustness of graph and simplicial learning methods. In the case of graphs, we study node2vec embeddings arising from different parameter sets, analysing their quality and stability using various measures. In the topic of signal processing, we explore how discrete Morse theory can be used for compression and reconstruction of cell complexes equipped with signals. In particular we study the effect of the compression of a complex on the Hodge decomposition of its signals. We study how the signal changes through compression and reconstruction by introducing a topological reconstruction error, showing in particular that part of the Hodge decomposition is preserved. Moreover, we prove that any deformation retract over R can be expressed as a Morse deformation retract in a well-chosen basis, thus extending the reconstruction results to any deformation retract. In addition, we introduce an algorithm to minimize the loss induced by the reconstruction of a compressed signal. Finally, we use discrete Morse theory to compute an invariant of multi-parameter persistent homology, the rank invariant. We can restrict a multi-parameter persistence module to a one- dimensional persistence module along any line of positive slope and compute the one-dimensional analogue of the rank invariant, namely the barcode. Through a discrete Morse matching we can determine critical values in the multifiltration, which in turn allows us to identify equivalence classes of lines in the parameter space. In our main result, we explain how to compute the barcode along any given line of an equivalence class given the barcode along a representative line. This provides a way to fiber the rank invariant according to the critical values of a discrete Morse matching and to perform computations in the corresponding one-dimensional module, which is much better understood.

EPFL2022

Connecting Hodge and Sakaguchi-Kuramoto through a mathematical framework for coupled oscillators on simplicial complexes

Alexis Arnaudon

Phase synchronizations in models of coupled oscillators such as the Kuramoto model have been widely studied with pairwise couplings on arbitrary topologies, showing many unexpected dynamical behaviors. Here, based on a recent formulation the Kuramoto model on weighted simplicial complexes with phases supported on simplices of any order k, we introduce linear and non-linear frustration terms independent of the orientation of the k + 1 simplices, as a natural generalization of the Sakaguchi-Kuramoto model to simplicial complexes. With increasingly complex simplicial complexes, we study the the dynamics of the edge simplicial Sakaguchi-Kuramoto model with nonlinear frustration to highlight the complexity of emerging dynamical behaviors. We discover various dynamical phenomena, such as the partial loss of synchronization in subspaces aligned with the Hodge subspaces and the emergence of simplicial phase re-locking in regimes of high frustration. Synchronization dynamics in the presence of higher order interactions is well represented through variations of the Kuramoto model and subject of current interest. Here, the authors study and characterize the behavior of the simplicial Kuramoto model with weights on any simplices and in the presence of linear and nonlinear frustration, defined as the simplicial Sakaguchi-Kuramoto model.

NATURE PORTFOLIO2022

Reduced representations of complexes, signals, and multifiltrations

Celia Camille Hacker

EPFL2022

Collapse-invariant properties of spaces equipped with signals or directions

Stefania Ebli

EPFL2022