Luca Ganassali

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, under the supervision of Laurent Massoulié and Marc Lelarge. Here is a short CV.

Contact

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

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

Publications and preprints

S. Akbari, L. Ganassali, N. Kiyavash. Learning causal graphs via monotone triangular transport maps, 2023, submitted.
[arXiv]

Short abstract: We study the problem of causal structure learning from data using optimal transport (OT). Specifically, we first provide a constraint-based method which builds upon lower-triangular monotone parametric transport maps to design conditional independence tests which are agnostic to the noise distribution. We provide an algorithm for causal discovery up to Markov Equivalence with no assumptions on the structural equations/noise distributions, which allows for settings with latent variables. Our approach also extends to score-based causal discovery by providing a novel means for defining scores. This allows us to uniquely recover the causal graph under additional identifiability and structural assumptions, such as additive noise or post-nonlinear models. We provide experimental results to compare the proposed approach with the state of the art on both synthetic and real-world datasets.

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.

Luca Ganassali

About

Contact

Publications and preprints

Conferences, workshops, talks

Reviewing

Teaching