Statistical and Computational limits for sparse graph alignment
Event details
| Date | 17.03.2022 |
| Hour | 14:00 › 15:00 |
| Speaker |
Luca Ganassali, Inria |
| Location | |
| Category | Conferences - Seminars |
CDM Seminar by Luca Ganassali, INRIA Paris
Abstract :
Graph alignment refers to recovering the underlying vertex correspondence between two random graphs with correlated edges. This problem can be viewed as an average-case and noisy version of the well-known graph isomorphism problem.
For correlated Erdős-Rényi random graphs, we will give insights on the fundamental limits for the planted formulation of this problem, establishing statistical thresholds for partial recovery. From the computational point of view, we are interested in designing and analyzing efficient (polynomial-time) algorithms to recover efficiently the underlying alignment: in a sparse regime, we exhibit an local rephrasing of the planted alignment problem as the correlation detection problem in trees. Analyzing this related problem enables to derive a message-passing algorithm for our initial task.
Based on joint works with Laurent Massoulié and Marc Lelarge: https://arxiv.org/abs/2002.01258, https://arxiv.org/abs/2102.02685,https://arxiv.org/abs/2107.07623.
Short bio
Since September 2019, I am a Ph.D. student at INRIA Paris under the supervision of Laurent Massoulié and Marc Lelarge. I work in the Dyogene team, which is a joint team between INRIA and ENS Paris.
My research interests lie mainly within statistics, probability theory, graph theory and machine learning. I am interested in studying procedures for learning tasks and inference problems with geometry, symmetries or invariance. More specifically, I'm currently looking at inference problems in graphs and matrices, such as graph alignment. For these problems, I am investigating the information-theoretical and computational thresholds, as well as designing and analyzing new algorithms on random instances to give a better understanding of the regimes in which they may suceed.
Other current topics I'm interested in are graph neural networks, and statistical learning with optimal transport.
Abstract :
Graph alignment refers to recovering the underlying vertex correspondence between two random graphs with correlated edges. This problem can be viewed as an average-case and noisy version of the well-known graph isomorphism problem.
For correlated Erdős-Rényi random graphs, we will give insights on the fundamental limits for the planted formulation of this problem, establishing statistical thresholds for partial recovery. From the computational point of view, we are interested in designing and analyzing efficient (polynomial-time) algorithms to recover efficiently the underlying alignment: in a sparse regime, we exhibit an local rephrasing of the planted alignment problem as the correlation detection problem in trees. Analyzing this related problem enables to derive a message-passing algorithm for our initial task.
Based on joint works with Laurent Massoulié and Marc Lelarge: https://arxiv.org/abs/2002.01258, https://arxiv.org/abs/2102.02685,https://arxiv.org/abs/2107.07623.
Short bio
Since September 2019, I am a Ph.D. student at INRIA Paris under the supervision of Laurent Massoulié and Marc Lelarge. I work in the Dyogene team, which is a joint team between INRIA and ENS Paris.
My research interests lie mainly within statistics, probability theory, graph theory and machine learning. I am interested in studying procedures for learning tasks and inference problems with geometry, symmetries or invariance. More specifically, I'm currently looking at inference problems in graphs and matrices, such as graph alignment. For these problems, I am investigating the information-theoretical and computational thresholds, as well as designing and analyzing new algorithms on random instances to give a better understanding of the regimes in which they may suceed.
Other current topics I'm interested in are graph neural networks, and statistical learning with optimal transport.
Practical information
- General public
- Free