Publications by Patrick Thiran

Reducing Sensor Requirements by Relaxing the Network Metric Dimension

Patrick Thiran, Maximilien Claude Robert Dreveton

Source localization in graphs involves identifying the origin of a phenomenon or event, such as an epidemic outbreak or a misinformation source, by leveraging structural graph properties. One key concept in this context is the metric dimension, which quant ...

ACM2025

Universal Lower Bounds and Optimal Rates: Achieving Minimax Clustering Error in Sub-Exponential Mixture Models

Patrick Thiran, Matthias Grossglauser, Maximilien Claude Robert Dreveton

Clustering is a pivotal challenge in unsupervised machine learning and is often investigated through the lens of mixture models. The optimal error rate for recovering cluster labels in Gaussian and sub-Gaussian mixture models involves ad hoc signal-to-nois ...

2024

Why the Metric Backbone Preserves Community Structure

Patrick Thiran, Matthias Grossglauser, Maximilien Claude Robert Dreveton

The metric backbone of a weighted graph is the union of all-pairs shortest paths. It is obtained by removing all edges

(u,v)

that are not the shortest path between

u

and

v

. In networks with well-separated communities, the metric backbone tends to pre ...

2024

Relaxing the Additivity Constraints in Decentralized No-Regret High-Dimensional Bayesian Optimization

Patrick Thiran

Bayesian Optimization (BO) is typically used to optimize an unknown function f that is noisy and costly to evaluate, by exploiting an acquisition function that must be maximized at each optimization step. Even if provably asymptotically optimal BO algorith ...

2024

Optimal performance of Graph Convolutional Networks on the Contextual Stochastic Block Model

Patrick Thiran

For Graph Neural Networks, oversmoothing denotes the homogenization of vertex embeddings as the number of layers increases. To better understand this phenomenon, we study community detection with a linearized Graph Convolutional Network on the Contextual S ...

2024

Leveraging Unlabeled Data to Track Memorization

Patrick Thiran, Mahsa Forouzesh, Hanie Sedghi

Deep neural networks may easily memorize noisy labels present in real-world data, which degrades their ability to generalize. It is therefore important to track and evaluate the robustness of models against noisy label memorization. We propose a metric, ca ...

2023

Source identification via contact tracing in the presence of asymptomatic patients

Patrick Thiran, Gergely Odor

Inferring the source of a diffusion in a large network of agents is a difficult but feasible task, if a few agents act as sensors revealing the time at which they got hit by the diffusion. One of the main limitations of current source identification algori ...

SPRINGERNATURE2023

On the transition times in a loss model of wireless networks

Patrick Thiran

SPRINGER2022

Momentum-Based Policy Gradient with Second-Order Information

Patrick Thiran, Negar Kiyavash, Mohammadsadegh Khorasani, Saber Salehkaleybar

Variance-reduced gradient estimators for policy gradient methods have been one of the main focus of research in the reinforcement learning in recent years as they allow acceleration of the estimation process. We propose a variance-reduced policy-gradient m ...

2022

On the robustness of the metric dimension of grid graphs to adding a single edge

Patrick Thiran, Gergely Odor, Satvik Mehul Mashkaria

The metric dimension (MD) of a graph is a combinatorial notion capturing the minimum number of landmark nodes needed to distinguish every pair of nodes in the graph based on graph distance. We study how much the MD can increase if we add a single edge to t ...

2022