83 citations · 332 across the 27 of their papers we have counts for
33 papers
A Generalized Tikhonov Layer for Interpretable-by-design Graph Neural Networks
Nicolas Tremblay, Benjamin Ricaud, Filippo Maria Bianchi
We propose the Tikhonov layer, a graph neural network layer that is interpretable by design: once trained, its learned parameters directly reveal which node features and which aspe…
Convergence of Message Passing Graph Neural Networks with Generic Aggregation On Large Random Graphs
Matthieu Cordonnier, Nicolas Keriven, Nicolas Tremblay +1
We study the convergence of message passing graph neural networks on random graph models to their continuous counterpart as the number of nodes tends to infinity. Until now, this c…
A Faster Sampler for Discrete Determinantal Point Processes
Simon Barthelmé, Nicolas Tremblay, Pierre-Olivier Amblard
Discrete Determinantal Point Processes (DPPs) have a wide array of potential applications for subsampling datasets. They are however held back in some cases by the high cost of sam…
Smoothing complex-valued signals on Graphs with Monte-Carlo
Hugo Jaquard, Michaël Fanuel, Pierre-Olivier Amblard +3
We introduce new smoothing estimators for complex signals on graphs, based on a recently studied Determinantal Point Process (DPP). These estimators are built from subsets of edges…
Variance Reduction for Inverse Trace Estimation via Random Spanning Forests
Yusuf Yigit Pilavci, Pierre-Olivier Amblard, Simon Barthelme +1
The trace $\tr(q(\ma{L} + q\ma{I})^{-1})$, where $\ma{L}$ is a symmetric diagonally dominant matrix, is the quantity of interest in some machine learning problems. However, its dir…
Gaussian Process Regression in the Flat Limit
Simon Barthelmé, Pierre-Olivier Amblard, Nicolas Tremblay +1
Gaussian process (GP) regression is a fundamental tool in Bayesian statistics. It is also known as kriging and is the Bayesian counterpart to the frequentist kernel ridge regressio…
Variance reduction in stochastic methods for large-scale regularised least-squares problems
Yusuf Pilavcı, Pierre-Olivier Amblard, Simon Barthelmé +1
Large dimensional least-squares and regularised least-squares problems are expensive to solve. There exist many approximate techniques, some deterministic (like conjugate gradient)…
Determinantal Point Processes in the Flat Limit
Simon Barthelmé, Nicolas Tremblay, Konstantin Usevich +1
Determinantal point processes (DPPs) are repulsive point processes where the interaction between points depends on the determinant of a positive-semi definite matrix. In this paper…
Nishimori meets Bethe: a spectral method for node classification in sparse weighted graphs
Lorenzo Dall'Amico, Romain Couillet, Nicolas Tremblay
This article unveils a new relation between the Nishimori temperature parametrizing a distribution P and the Bethe free energy on random Erdos-Renyi graphs with edge weights distri…
Graph Tikhonov Regularization and Interpolation via Random Spanning Forests
Yusuf Pilavci, Pierre-Olivier Amblard, Simon Barthelme +1
Novel Monte Carlo estimators are proposed to solve both the Tikhonov regularization (TR) and the interpolation problems on graphs. These estimators are based on random spanning for…
Fast Graph Kernel with Optical Random Features
Hashem Ghanem, Nicolas Keriven, Nicolas Tremblay
The graphlet kernel is a classical method in graph classification. It however suffers from a high computation cost due to the isomorphism test it includes. As a generic proxy, and…
Determinantal Point Processes in the Flat Limit: Extended L-ensembles, Partial-Projection DPPs and Universality Classes
Simon Barthelmé, Nicolas Tremblay, Konstantin Usevich +1
Determinantal point processes (DPPs) are repulsive point processes where the interaction between points depends on the determinant of a positive-semi definite matrix. The contribut…
Community detection in sparse time-evolving graphs with a dynamical Bethe-Hessian
Lorenzo Dall'Amico, Romain Couillet, Nicolas Tremblay
This article considers the problem of community detection in sparse dynamical graphs in which the community structure evolves over time. A fast spectral algorithm based on an exten…
A unified framework for spectral clustering in sparse graphs
Lorenzo Dall'Amico, Romain Couillet, Nicolas Tremblay
This article considers spectral community detection in the regime of sparse networks with heterogeneous degree distributions, for which we devise an algorithm to efficiently retrie…
Optimal Laplacian regularization for sparse spectral community detection
Lorenzo Dall'Amico, Romain Couillet, Nicolas Tremblay
Regularization of the classical Laplacian matrices was empirically shown to improve spectral clustering in sparse networks. It was observed that small regularizations are preferabl…
Smoothing graph signals via random spanning forests
Yusuf Y. Pilavci, Pierre-Olivier Amblard, Simon Barthelmé +1
Another facet of the elegant link between random processes on graphs and Laplacian-based numerical linear algebra is uncovered: based on random spanning forests, novel Monte-Carlo…
Estimating the inverse trace using random forests on graphs
Simon Barthelmé, Nicolas Tremblay, Alexandre Gaudillière +2
Some data analysis problems require the computation of (regularised) inverse traces, i.e. quantities of the form $\Tr (q \bI + \bL)^{-1}$. For large matrices, direct methods are un…
Approximating Spectral Clustering via Sampling: a Review
Nicolas Tremblay, Andreas Loukas
Spectral clustering refers to a family of unsupervised learning algorithms that compute a spectral embedding of the original data based on the eigenvectors of a similarity graph. T…
Revisiting the Bethe-Hessian: Improved Community Detection in Sparse Heterogeneous Graphs
Lorenzo Dall'Amico, Romain Couillet, Nicolas Tremblay
Spectral clustering is one of the most popular, yet still incompletely understood, methods for community detection on graphs. This article studies spectral clustering based on the…
Determinantal Point Processes for Coresets
Nicolas Tremblay, Simon Barthelmé, Pierre-Olivier Amblard
When faced with a data set too large to be processed all at once, an obvious solution is to retain only part of it. In practice this takes a wide variety of different forms, and am…
Asymptotic Equivalence of Fixed-size and Varying-size Determinantal Point Processes
Simon Barthelmé, Pierre-Olivier Amblard, Nicolas Tremblay
Determinantal Point Processes (DPPs) are popular models for point processes with repulsion. They appear in numerous contexts, from physics to graph theory, and display appealing th…
Optimized Algorithms to Sample Determinantal Point Processes
Nicolas Tremblay, Simon Barthelme, Pierre-Olivier Amblard
In this technical report, we discuss several sampling algorithms for Determinantal Point Processes (DPP). DPPs have recently gained a broad interest in the machine learning and sta…
Analyzing the Approximation Error of the Fast Graph Fourier Transform
Luc LeMagoarou, Nicolas Tremblay, Rémi Gribonval
The graph Fourier transform (GFT) is in general dense and requires O(n^2) time to compute and O(n^2) memory space to store. In this paper, we pursue our previous work on the approx…
Design of graph filters and filterbanks
Nicolas Tremblay, Paulo Gonçalves, Pierre Borgnat
Basic operations in graph signal processing consist in processing signals indexed on graphs either by filtering them, to extract specific part out of them, or by changing their dom…