Luca Ganassali

Welcome to my personal webpage!

About me

Since October 2022, I am a postdoctoral researcher at EPFL in BAN chair led by Prof. Negar Kiyavash. Prior to that, I was a PhD student at Inria Paris in the Dyogene team, which is a joint team between Inria and ENS Paris, under the supervision of Laurent Massoulié and Marc Lelarge. Here is a short CV.

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've been looking at inference problems in graphs and matrices, such as graph alignment, 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, statistical learning with optimal transport, and causality.

Contact

Email adress: luca [dot] ganassali [at] epfl [dot] ch

Physical adress: Office 316, Building ODY, EPFL, Lausanne.

Publications and preprints

• L. Ganassali, L. Massoulié, G. Semerjian. Statistical limits of correlation detection in trees, 2022, submitted.
  [arXiv]

  Short abstract: In this paper we address the problem of testing whether two observed trees are sampled either independently or from a joint distribution under which they are correlated. This problem, which we refer to as correlation detection in trees, plays a key role in the study of graph alignment for two correlated random graphs. Motivated by graph alignment, we investigate the conditions of existence of one-sided tests, i.e. tests which have vanishing type I error and non-vanishing power in the limit of large tree depth. For the correlated Galton-Watson model we identify a phase transition in the limit of large degrees: we prove that no such test exists below this threshold and that such a test exists whenever above the threshold, for a large enough mean degree.

• L. Ganassali. The graph alignment problem: fundamental limits and efficient algorithms, PhD dissertation, 2022. [pdf]

• L. Ganassali, M. Lelarge, L. Massoulié. Correlation detection in trees for partial graph alignment, 2021, Innovations in Theoretical Computer Science (ITCS 2022).
  [arXiv] [ITCS (extended abstract)]

  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, in Proceedings of Thirty Fourth Conference on Learning Theory (COLT 2021).
  [arXiv] [PMLR] [COLT presentation]

  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] [PMLR] [MSML presentation]

  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] [COLT presentation]

  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, in Advances in Applied Probability.
  [arXiv] [journal]

  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, talks

• Upcoming: Young European Probabilists (YEP) workshop, Eindhoven, Mar. 27-31, 2023.

• Upcoming: Séminaire de Probabilités/Statistiques, Institut de mathématique d'Orsay, Orsay, Jan. 12, 2023.

• Séminaire de Probabilités, Centre de Mathématiques et Informatique, Université d'Aix-Marseille, Marseille, Nov. 15, 2022. (talk)

• Theoretical Computer Science Spring School: Machine Learning, CIRM, Luminy, May 23-27, 2022.

• CDM Seminar, EPFL, Mar. 17, 2022. (talk)

• DACO Seminar, ETH Zürich, Feb. 28-Mar. 1, 2022. (talk)

• Innovations in Theoretical Computer Science (ITCS), Berkeley (remote), Jan. 31-Feb. 3, 2022. (talk)

• Stochastics Seminar, Georgia Tech (remote), Dec. 9, 2021. (talk)

• Prairie Workshop, Paris, Nov. 10, 2021. (poster)

• Colloque Jeunes Probabilistes et Statisticien-ne-s, Saint Pierre D'Oléron, Oct. 24-29, 2021. (talk, slides)

• Workshop On Future Synergies for Stochastic and Learning Algorithms, CIRM, Luminy, Sept. 27-Oct. 1, 2021. (poster)

• Junior conference Random networks and interacting particle systems (remote), Sept. 6-10, 2021. (talk)

• Conference on Learning Theory (COLT) (remote), Aug. 15-19, 2021. (talk, slides, poster)

• Mathematical and Scientific Machine Learning (MSML) (remote), Aug. 16-19, 2021. (talk)

• Conference on Learning Theory (COLT) (remote), Jul. 9-12, 2020. (talk)

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

• Networking days, Orsay, Oct. 23, 2019. (talk)

Reviewing

• Conferences: ISIT 2021, COLT 2022, MSML 2022.

• Journals: Journal of Machine Learning Research, Annals of Statistics.

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.
  

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

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

• Fall 2021: TA for the MT15Y030 course: Probabilités, L3, Université de Paris. Vous trouverez ici des exercices supplémentaires.

• Spring 2022: TA for the MA1BY020 course: Statistiques, M1, Université de Paris. Voir les TPs.