9 papers
Estimation and Recovery of a Planted Dense Subgraph from a Single Network Cascade
Maximilien Dreveton, Paula Mürmann, Patrick Thiran
We study the inference of a planted dense component in a sparse random graph from a single spreading process. The graph has an Erdős-Rényi background with edge probability an…
Hierarchical Clustering Can Jointly Satisfy Richness, Consistency, and Scale Invariance
Daichi Kuroda, Maximilien Dreveton, Matthias Grossglauser +1
Despite its ubiquity, clustering lacks a universally accepted definition of what is a cluster. Kleinberg's Impossibility Theorem formalizes this difficulty by showing that no flat…
Sharp First-Order Lower Bounds under -Polyak-Lojasiewicz Conditions
Saeed Masiha, Negar Kiyavash, Patrick Thiran
We study first-order oracle complexity under the -Polyak-Lojasiewicz condition for . For , we first show that global -sm…
Zeroth-Order Stackelberg Control in Combinatorial Congestion Games
Saeed Masiha, Sepehr Elahi, Negar Kiyavash +1
We study Stackelberg (leader--follower) tuning of network parameters (tolls, capacities, incentives) in combinatorial congestion games, where selfish users choose discrete routes (…
Neighborhood-Aware Graph Labeling Problem
Mohammad Shahverdikondori, Sepehr Elahi, Patrick Thiran +1
Motivated by optimization oracles in bandits with network interference, we study the Neighborhood-Aware Graph Labeling (NAGL) problem. Given a graph , a label set of siz…
Hierarchical Linkage Clustering Beyond Binary Trees and Ultrametrics
Maximilien Dreveton, Matthias Grossglauser, Daichi Kuroda +1
Hierarchical clustering seeks to uncover nested structures in data by constructing a tree of clusters, where deeper levels reveal finer-grained relationships. Traditional methods,…
Optimal Graph Clustering without Edge Density Signals
Maximilien Dreveton, Elaine Siyu Liu, Matthias Grossglauser +1
This paper establishes the theoretical limits of graph clustering under the Popularity-Adjusted Block Model (PABM), addressing limitations of existing models. In contrast to the St…
Learn to Vaccinate: Combining Structure Learning and Effective Vaccination for Epidemic and Outbreak Control
Sepehr Elahi, Paula Mürmann, Patrick Thiran
The Susceptible-Infected-Susceptible (SIS) model is a widely used model for the spread of information and infectious diseases, particularly non-immunizing ones, on a graph. Given a…
Reducing Sensor Requirements by Relaxing the Network Metric Dimension
Paula Mürmann, Robin Jaccard, Maximilien Dreveton +2
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 prop…