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, Hanie Sedghi, Mahsa Forouzesh

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, Saber Salehkaleybar, Negar Kiyavash, Mohammadsadegh Khorasani

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

The power of adaptivity in source identification with time queries on the path

Patrick Thiran, Gergely Odor, Victor Cyril L Lecomte

We study the problem of identifying the source of a stochastic diffusion process spreading on a graph based on the arrival times of the diffusion at a few queried nodes. In a graph

G=(V,E)

, an unknown source node

v^* \in V

is drawn uniformly at random, ...

2022

Stochastic Second-Order Methods Improve Best-Known Sample Complexity of SGD for Gradient-Dominated Function

Patrick Thiran, Saber Salehkaleybar, Negar Kiyavash

We study the performance of Stochastic Cubic Regularized Newton (SCRN) on a class of functions satisfying gradient dominance property with

1\le\alpha\le2

which holds in a wide range of applications in machine learning and signal processing. This conditio ...

NeurIPS2022

Cumulants of Hawkes Processes are Robust to Observation Noise

Patrick Thiran, Matthias Grossglauser, Seyed Jalal Etesami, William Trouleau, Negar Kiyavash

Multivariate Hawkes processes (MHPs) are widely used in a variety of fields to model the occurrence of causally related discrete events in continuous time. Most state-of-the-art approaches address the problem of learning MHPs from perfect traces without no ...

JMLR-JOURNAL MACHINE LEARNING RESEARCH2021

A Variational Inference Approach to Learning Multivariate Wold Processes

Patrick Thiran, Matthias Grossglauser, Seyed Jalal Etesami, William Trouleau, Negar Kiyavash

Temporal point-processes are often used for mathematical modeling of sequences of discrete events with asynchronous timestamps. We focus on a class of temporal point-process models called multivariate Wold processes (MWP). These processes are well suited t ...

MICROTOME PUBLISHING2021

War of Words II: Enriched Models of Law-Making Processes

Patrick Thiran, Matthias Grossglauser, Victor Kristof, Aswin Suresh

The European Union law-making process is an instance of a peer- production system. We mine a rich dataset of law edits and intro- duce models predicting their adoption by parliamentary committees. Edits are proposed by parliamentarians, and they can be in ...

ACM2021

Disparity Between Batches as a Signal for Early Stopping

Patrick Thiran, Mahsa Forouzesh

We propose a metric for evaluating the generalization ability of deep neural networks trained with mini-batch gradient descent. Our metric, called gradient disparity, is the l2 norm distance between the gradient vectors of two mini-batches drawn from the t ...

Springer2021

Generalization Comparison of Deep Neural Networks via Output Sensitivity

Patrick Thiran, Farnood Salehi, Mahsa Forouzesh

Although recent works have brought some insights into the performance improvement of techniques used in state-of-the-art deep-learning models, more work is needed to understand their generalization properties. We shed light on this matter by linking the lo ...

IEEE2021

Sequential metric dimension for random graphs

Patrick Thiran, Gergely Odor

In the localization game on a graph, the goal is to find a fixed but unknown target node v* with the least number of distance queries possible. In the j-th step of the game, the player queries a single node v_j and receives, as an answer to their query, th ...

2021

War of Words: The Competitive Dynamics of Legislative Processes

Patrick Thiran, Matthias Grossglauser, Victor Kristof

A body of law is an example of a dynamic corpus of text documents that are jointly maintained by a group of editors who compete and collaborate in complex constellations. Our goal is to develop predictive models for this process, thereby shedding light on ...

ACM / IW3C2 (International World Wide Web Conference Committee)2020

Sub-Matrix Factorization for Real-Time Vote Prediction

Patrick Thiran, Matthias Grossglauser, Victor Kristof

We address the problem of predicting aggregate vote outcomes (e.g., national) from partial outcomes (e.g., regional) that are revealed sequentially. We combine matrix factorization techniques and generalized linear models (GLMs) to obtain a flexible, effic ...

2020