Random walks on complex data: from geometric clustering to topological shape recognition

Random walks on discrete settings is one of the most powerful mathematical tools for solving a wide range of theoretical and applied problems in discrete math, probability, theoretical computer science, data science, and machine learning. This ranges from google page rank algorithm to clustering elements in complex networks and detecting topological communities in high dimensional data. In this talk, I will show how random walks can serve as the bridge between quantitative features of data, which are determined by geometric tools such as curvature, and qualitative features that can be detected by topological methods. In traditional data analysis, graphs as the simplest examples of discrete structures are well studied and we have a relatively broad understanding of their topological, geometric and stochastic properties. However, graphs can not present higher order interactions among data points and a main challenge in both theoretical and applied sides is to extend results from graphs to more complicated structures which are suitable for modelling beyond binary interactions. After presenting some of the main ideas of geometric and topological data analysis via random walks on graphs, I will talk about the main challenges of extending some graph-results to higher dimensions and how we can go further. I try to present mostly the intuition behind the ideas and will not go into all the details. Therefore I hope the content would be accessible to those who have not much background in geometric or topological methods. Knowing about Markov chains and stochastic processes would be helpful.