Guest lecture by Stefan Neumann (University of Vienna) on 4.9.2019

Time and place: 4 September at 10 am, room TB180 (Joensuu Science Park). Video connection to Kuopio into room F213.
Title: Bipartite Stochastic Block Models with Tiny Clusters
Speaker: Stefan Neumann, University of Vienna
Did you ever wonder how Amazon implements its "Customers Who Bought This Item Also Bought…”-Feature? In this talk, we will discuss a version of this problem. In particular, we consider the problem of finding planted clusters in random bipartite graphs (e.g., one side of the graph corresponds to Amazon users and the other side corresponds to products). We present a simple two-step algorithm which provably finds even tiny clusters of size O(n^epsilon), where n is the number of vertices in the graph and epsilon > 0. Previous algorithms were only able to identify clusters of size Omega(sqrt(n)).  We evaluate the algorithm on synthetic and on real-world data; the experiments show that the algorithm can find extremely small clusters even in presence of high destructive noise. This paper appeared at NeurIPS 2018.
Stefan Neumann is a fourth year PhD student at University of Vienna. Stefan’s research interests include algorithmic data analysis, theoretical models for practical problems and dynamic graph data structures. Before joining University of Vienna, Stefan obtained a Master’s degree in computer science from Saarland University and Max Planck Institute for Informatics and a Bachelor’s degree in mathematics from University of Jena.