19 citations · 66 across the 12 of their papers we have counts for
13 papers
Statistical-computational gap in multiple Gaussian graph alignment
Bertrand Even, Luca Ganassali
We investigate the existence of a statistical-computational gap in multiple Gaussian graph alignment. We first generalize a previously established informational threshold from Vass…
Aligning Embeddings and Geometric Random Graphs: Informational Results and Computational Approaches for the Procrustes-Wasserstein Problem
Mathieu Even, Luca Ganassali, Jakob Maier +1
The Procrustes-Wasserstein problem consists in matching two high-dimensional point clouds in an unsupervised setting, and has many applications in natural language processing and c…
The graph alignment problem: fundamental limits and efficient algorithms
Luca Ganassali
This thesis studies the graph alignment problem, the noisy version of the graph isomorphism problem, which aims to find a matching between the nodes of two graphs which preserves m…
On sample complexity of conditional independence testing with Von Mises estimator with application to causal discovery
Fateme Jamshidi, Luca Ganassali, Negar Kiyavash
Motivated by conditional independence testing, an essential step in constraint-based causal discovery algorithms, we study the nonparametric Von Mises estimator for the entropy of…
Learning Causal Graphs via Monotone Triangular Transport Maps
Sina Akbari, Luca Ganassali, Negar Kiyavash
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-triangula…
Statistical limits of correlation detection in trees
Luca Ganassali, Laurent Massoulié, Guilhem Semerjian
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. T…
SiMCa: Sinkhorn Matrix Factorization with Capacity Constraints
Eric Daoud, Luca Ganassali, Antoine Baker +1
For a very broad range of problems, recommendation algorithms have been increasingly used over the past decade. In most of these algorithms, the predictions are built upon user-ite…
Correlation detection in trees for planted graph alignment
Luca Ganassali, Laurent Massoulié, Marc Lelarge
Motivated by alignment of correlated sparse random graphs, we introduce a hypothesis testing problem of deciding whether or not two random trees are correlated. We obtain sufficien…
Impossibility of Partial Recovery in the Graph Alignment Problem
Luca Ganassali, Laurent Massoulié, Marc Lelarge
Random graph alignment refers to recovering the underlying vertex correspondence between two random graphs with correlated edges. This can be viewed as an average-case and noisy ve…
Sharp threshold for alignment of graph databases with Gaussian weights
Luca Ganassali
We study the fundamental limits for reconstruction in weighted graph (or matrix) database alignment. We consider a model of two graphs where is a planted uniform permutation…
Probabilistic and mean-field model of COVID-19 epidemics with user mobility and contact tracing
M. Akian, L. Ganassali, S. Gaubert +1
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…
From tree matching to sparse graph alignment
Luca Ganassali, Laurent Massoulié
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 tha…
Spectral Alignment of Correlated Gaussian matrices
Luca Ganassali, Marc Lelarge, Laurent Massoulié
In this paper we analyze a simple spectral method (EIG1) for the problem of matrix alignment, consisting in aligning their leading eigenvectors: given two matrices and , we…