Друзья, а у нас меж тем анонс завтрашнего выступления — на научной части нашего семинара (в этот раз будет проходить онлайн, но можно и нужно прийти на матфак, там организуем трансляцию)

C докладом в этот раз выступит Людмила Прохоренкова, Senior Researcher из Yandex Research. Аннотация доклада:

Challenges of measuring diversity and generating structurally diverse graphs

For many graph-related problems, it can be essential to have a set of graphs that are structurally diverse. For instance, such graphs can be used for testing graph algorithms or their neural approximations. However, generating such a set is challenging.

First, we discuss how to define diversity for a set of graphs, why this task is non-trivial, and how one can choose a proper diversity measure. The problem of defining diversity is interesting in itself: there is a list of three simple desirable properties of a good diversity measure that are hard to simultaneously satisfy. 

For a given diversity measure, we propose and compare several algorithms optimizing it: we consider approaches based on standard random graph models, local graph optimization, genetic algorithms, and neural generative models. We show that it is possible to significantly improve diversity over basic random graph generators. Additionally, our analysis of generated graphs allows us to better understand the properties of graph distances: depending on which diversity measure is used for optimization, the obtained graphs may possess very different structural properties which gives a better understanding of the graph distance underlying the diversity measure.

Сам доклад будет основан на статьях https://arxiv.org/abs/2409.18859 (была на NeurIPS в этом году) и https://arxiv.org/abs/2410.14556. Для удаленных слушателей в этот раз должно быть особенно удобно слушать, так что кто не сможет прийти 25.03.25 в 18:00 в аудиторию 108 — ждем вас в зуме