Expressive Power of Invariant and Equivariant Graph Neural Networks
Various classes of Graph Neural Networks (GNN) have been proposed and shown to be successful in a wide range of applications with graph structured data. In this paper, we propose a theoretical...
FLEX: an Adaptive Exploration Algorithm for Nonlinear Systems
Model-based reinforcement learning is a powerful tool, but collecting data to fit an accurate model of the system can be costly. Exploring an unknown environment in a sample-efficient manner is...
Convergence beyond the over-parameterized regime using Rayleigh quotients
In this paper, we present a new strategy to prove the convergence of deep learning architectures to a zero training (or even testing) loss by gradient flow. Our analysis is centered on the notion...
Impossibility of Partial Recovery in the Graph Alignment Problem
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 version of the...
Correlation detection in trees for planted graph alignment
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 sufficient conditions...
Online greedy identification of linear dynamical systems
This work addresses the problem of exploration in an unknown environment. For linear dynamical systems, we use an experimental design framework and introduce an online greedy policy where the...
Asymptotic Bayes risk for Gaussian mixture in a semi-supervised setting
Semi-supervised learning (SSL) uses unlabeled data for training and has been shown to greatly improve performance when compared to a supervised approach on the labeled data available. This claim...
Statistical and computational phase transitions in spiked tensor estimation
We consider tensor factorizations using a generative model and a Bayesian approach. We compute rigorously the mutual information, the Minimal Mean Squared Error (MMSE), and unveil...
Conditioned Text Generation with Transfer for Closed-Domain Dialogue Systems
Scarcity of training data for task-oriented dialogue systems is a well known problem that is usually tackled with costly and time-consuming manual data annotation. An alternative solution is to...
Spectral Alignment of Correlated Gaussian matrices
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 $A$ and $B$, we compute $v_1$...
Weighted Spectral Embedding of Graphs
We present a novel spectral embedding of graphs that incorporates weights assigned to the nodes, quantifying their relative importance. This spectral embedding is based on the first eigenvectors...
InfoCatVAE: Representation Learning with Categorical Variational Autoencoders
This paper describes InfoCatVAE, an extension of the variational autoencoder that enables unsupervised disentangled representation learning. InfoCatVAE uses multimodal distributions for the prior...
Non-backtracking spectrum of random graphs: community detection and non-regular Ramanujan graphs
A non-backtracking walk on a graph is a directed path such that no edge is the inverse of its preceding edge. The non-backtracking matrix of a graph is indexed by its directed edges and can be...
A Streaming Algorithm for Graph Clustering
We introduce a novel algorithm to perform graph clustering in the edge streaming setting. In this model, the graph is presented as a sequence of edges that can be processed strictly once. Our...
Conditioned Query Generation for Task-Oriented Dialogue Systems
Scarcity of training data for task-oriented dialogue systems is a well known problem that is usually tackled with costly and time-consuming manual data annotation. An alternative solution is to...
A linear streaming algorithm for community detection in very large networks
In this paper, we introduce a novel community detection algorithm in graphs, called SCoDA (Streaming Community Detection Algorithm), based on an edge streaming setting. This algorithm has an...
Deep Representation for Patient Visits from Electronic Health Records
We show how to learn low-dimensional representations (embeddings) of patient visits from the corresponding electronic health record (EHR) where International Classification of Diseases (ICD)...
Non-Backtracking Spectrum of Degree-Corrected Stochastic Block Models
Motivated by community detection, we characterise the spectrum of the non-backtracking matrix $B$ in the Degree-Corrected Stochastic Block Model. Specifically, we consider a random graph on $n$...