Laurent Massoulie (Scientific Director, Paris Inria Centre) Graph Alignment : Informational and Computational limits

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.

The event will take place at M Shed Bristol, with arrival and refreshments from 2.30pm and the talk from 3-4pm.