Abstract:
Graph alignment is a generic unsupervised learning task with many applications, from neuroscience to social network de-anonymization. The alignment of a pair of correlated random graphs turns out to be a problem in high dimensional statistics featuring a rich set of phenomena. Specifically, we shall first present results on information-theoretic limits to feasibility of graph alignment: below some threshold, the observed graphs do not contain enough information for alignment to be feasible, while above that threshold, some algorithms are known to succeed at alignment, although in exponential time. We shall then present results on computational feasibility of alignment, describing a second threshold which determines when a family of ‘local’, polynomial-time algorithms succeed at alignment. Together, these results show a rich phenomenology for graph alignment, displaying an ‘impossible phase’, a ‘hard phase’ and an ‘easy phase’ for feasibility of the task.
Bio:
Laurent Massoulié is a research scientist at Inria, scientific director of the Paris Inria Centre and professor at the Applied Maths Centre of Ecole Polytechnique. His research interests are in machine learning, probabilistic modelling and algorithms for networks. He has held research scientist positions at: France Telecom, Microsoft Research, Thomson-Technicolor, where he headed the Paris Research Lab. He obtained best paper awards at IEEE INFOCOM 1999, ACM SIGMETRICS 2005, ACM CoNEXT 2007, NeurIPS 2018, NeurIPS 2021, was elected "Technicolor Fellow" in 2011, received the "Grand Prix Scientifique" of the Del Duca Foundation delivered by the French Academy of Science in 2017, is a Fellow of the “Prairie” Institute and received the ACM Sigmetrics achievement award in 2023.