Luca Ganassali

Welcome to my personal webpage!

About me

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. Prior to that, I gratued from Ecole Polytechnique in 2018 and got a master degree from Université Paris-Saclay in Probability and Statistics in 2019.

My research interests lie mainly within statistics, probability theory, graph theory and machine learning. More specifically, I'm currently looking at inference problems in graphs and matrices, such as graph alignment. For these problems, I'm interested in 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 epidemiology on graphs, opinion exchange dynamics and graph neural networks.

Contact

INRIA, 3rd floor, Office C321,
2 rue Simone Iff,
75012 Paris.

Publications and preprints

• L.Ganassali, M. Lelarge, L. Massoulié. Correlation detection in trees for partial graph alignment, 2021, preprint (preliminary version).
  [arXiv]

  Short abstract: We consider alignment of sparse graphs, which consists in finding a mapping between the nodes of two graphs which preserves most of the edges. Our approach is to compare local structures in the two graphs, matching two nodes if their neighborhoods are 'close enough': for correlated Erdős-Rényi random graphs, this problem can be locally rephrased in terms of testing whether a pair of branching trees is drawn from either a product distribution, or a correlated distribution. We design an optimal test for this problem which gives rise to a message-passing algorithm for graph alignment. Some conditions for determining whether partial graph alignment (or correlation detection in trees) is feasible in polynomial time are given, completing the recent state-of-the-art diagram.

• L.Ganassali, M. Lelarge, L. Massoulié. Impossibility of Partial Recovery in the Graph Alignment Problem, 2021, COLT 2021.
  [arXiv]

  Short abstract: For the correlated Erdös-Rényi model, we prove an impossibility result for partial recovery in the sparse regime, with constant average degree and correlation, as well as a general bound on the maximal reachable overlap. Our bound is tight in the noiseless case (the graph isomorphism problem) and we conjecture that it is still tight with noise. Our proof technique relies on a careful application of the probabilistic method to build automorphisms between tree components of a subcritical Erdös-Rényi graph.

• L.Ganassali. Sharp threshold for alignment of graph databases with Gaussian weights, 2020, Mathematical and Scientific Machine Learning (MSML21).
  [arXiv]

  Short abstract: We study the fundamental limits for reconstruction in weighted graph (or matrix) database alignment. We consider a model of two graphs G, G', where G and G' have correlated Gaussian edge weights, and then G is relabeled according to a random uniform permutation. We prove that there is a sharp information-theoretic threshold for exact recovery of the planted permutation. This threshold is the same as the one obtained for detection in a recent work by Y. Wu, J. Xu and S. Yu: in other words, for Gaussian weighted graph alignment, the problem of reconstruction is not more difficult than that of detection. The study is based on the analysis of the MAP estimator, and proofs rely on proper use of the correlation structure of energies of permutations.

• M. Akian, L.Ganassali, S. Gaubert, L. Massoulié. Probabilistic and mean-field model of COVID-19 epidemics with user mobility and contact tracing, 2020, preprint.
  [arXiv]

  Short abstract: We propose a detailed discrete-time model of COVID-19 epidemics coming in two flavours, mean-field and probabilistic. The main contribution lies in several extensions of the basic model that capture i) user mobility - distinguishing routing, i.e. change of residence, from commuting, i.e. daily mobility - and ii) contact tracing procedures. We confront this model to public data on daily hospitalizations, and discuss its application as well as underlying estimation procedures.

• L.Ganassali, L. Massoulié. From tree matching to sparse graph alignment, 2020, in Proceedings of Thirty Third Conference on Learning Theory (COLT 2020).
  [arXiv] [PMLR]

  Short abstract: In this paper we consider alignment of sparse graphs, for which we introduce the Neighborhood Tree Matching Algorithm (NTMA). For correlated Erdős-Rényi random graphs, we prove that the algorithm returns -- in polynomial time -- a positive fraction of correctly matched vertices, and a vanishing fraction of mismatches. This result holds with average degree of the graphs in O(1) and correlation parameter s that can be bounded away from 1, conditions under which random graph alignment is particularly challenging. As a byproduct of the analysis we introduce a matching metric between trees and characterize it for several models of correlated random trees.

• L.Ganassali, M. Lelarge, L. Massoulié. Spectral alignment of correlated Gaussian random matrices, 2019, to appear in Journal of Applied Probability.
  [arXiv]

  Short abstract: In this paper we analyze a simple method (EIG1) for the problem of matrix alignment: given A and B, we compute two leading eigenvectors of A and B. The algorithm returns a permutation that aligns these vectors (up to their sign). We analyze this algorithm in a standard Wigner model, and show a zero-one law, that is a threshold on the signal-to-noise ratio above which under which the EIG1 method recovers all but a vanishing part of the underlying permutation, and under which this algorithm cannot recover more than a vansihing proportion of correct matches. This result gives an understanding of the simplest and fastest spectral method for matrix alignment (or complete weighted graph alignment), and involves proof methods and techniques which could be of independent interest.

Conferences, workshops

• Upcoming: Conference on Learning Theory (COLT), August 2021.

• Upcoming: Mathematical and Scientific Machine Learning (MSML), August 2021.

• Conference on Learning Theory (COLT) 9-12 July 2020. The presentation of our paper From tree matching to sparse graph alignment can be found here.
  

• Spectra, Algorithms and Random Walks on Random Networks, CIRM, Luminy, 13-17 January 2020.

• Networking days, Orsay, 23 October 2019.

Some slides

• The slides from my presentation at COLT2021 on Impossibility of Partial Recovery in the Graph Alignment Problem can be found here.

• The slides of a talk about Information-theoretical thresholds for (exact) graph alignment, and a digression about the analysis of the MAP estimator.

• The slides of a presentation about sparse graph alignment, at the Dyogene team seminar in June 2020.
  

Reviewing

• Conferences: IEEE International Symposium on Information Theory, 2021.

• Journals: Journal of Machine Learning Research.

Teaching

• Spring 2020: Tutoring for the MAP361 course at Ecole Polytechnique, some revision exercices (in french) about Borel-Cantelli lemma, Convergence of random variables, and Estimation and CLT.
  

• Fall 2021: TA for the MA16Y020 course: Statistiques et simulations probabilistes, L3, Université de Paris. See the course page.

• Fall 2021: TA for the MA1BY020 course: Statistiques, M1, Université de Paris. See the course page.