Thesis defense “Random walk on simplicial complexes”

The notion of Laplacian of a graph can be generalized to simplicial complexes and hypergraphs. This notion contains information on the topology of these structures. Even for a graph, the consideration of associated simplicial complexes can provide information on its shape. Whereas the Laplacian of a graph has a simple probabilistic interpretation as the generator of a continuous time Markov chain on the graph, things are not so direct when considering simplicial complexes. In the first part of this thesis, we define a new Markov chain on simplicial complexes. For a given degree k of simplices, the state space is not the k-simplices as in previous papers about this subject but rather the set of k-chains or k-cochains. This new framework is the natural generalization on the canonical Markov chains on graphs. We show that the generator of our Markov chain is related to the upper Laplacian defined in the context of algebraic topology for discrete structure. We establish several key properties of this new process. We show that when the simplicial complexes under scrutiny are a sequence of ever refining triangulation of the flat torus, the Markov chains tend to a differential form valued continuous process.

 

In the second part of this thesis, we explore some applications of the random walk, i.e., random walk based hole detection and simplicial complexes kernels. For the random walk based hole detection, we introduce an algorithm to make simulations carried for the cycle-valued random walk (k = 1) on a simplicial complex with holes. Since the state space of the cycle-valued random walk consists of all the states in the same homology group, the paths with minimal lengths are supposed to be the holes of the simplicial complex, which is the idea of the algorithm. In the case where we do not know the boundary of the simplicial complex, we need to find the initial state which is in the same homology group as the holes and has an integer value. Thus we calculate the initial states and propose another algorithm to make simulations of integer weighted random walk. Simulation results show that we can always detect the holes of simplicial complexes with boundary (initial state) known, and approximately with initial state unknown. For the simplicial complexes kernels, we extend the definition of random walk based graph kernels in order to measure the similarity between two simplicial complexes. The definition is based on this idea: given a pair of simplicial complexes, we perform our random walks on both, and count the number of matching walks. The more matching walks, the more similar these two simplicial complexes are. In order to count the number of matching walks, we perform a random walk on the direct product simplicial complex of these two simplicial complexes. We compute the probability of the random walk whose length is k, and sum them for all k. The result is the kernel of these two simplicial complexes. In order to reduce computational complexity, we rewrite the sum formula to the inverse of a matrix, and use conjugate gradient methods instead of direct computation. Simulation results show that graph kernels are related to the number of vertices and their connectivity, while simplicial complexes kernels put emphasis on homology properties.

 

Here’s the streaming link:

https://telecom-paris.zoom.us/j/99001968945pwd=MjFiakw4Q3hQaU5hbGZ2U2ZsSWxEUT09

ID de réunion : 990 0196 8945

Code secret : 766753