8 citations · 17 across the 12 of their papers we have counts for
14 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…
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…
Robust estimation of a Markov chain transition matrix from multiple sample paths
Lasse Leskelä, Maximilien Dreveton
Markov chains are fundamental models for stochastic dynamics, with applications in a wide range of areas such as population dynamics, queueing systems, reinforcement learning, and…
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…
Recovering Small Communities in the Planted Partition Model
Martijn Gösgens, Maximilien Dreveton
We study community recovery in the planted partition model in regimes where the number and sizes of communities may vary arbitrarily with the number of vertices. In such highly unb…
Why the Metric Backbone Preserves Community Structure
Maximilien Dreveton, Charbel Chucri, Matthias Grossglauser +1
The metric backbone of a weighted graph is the union of all-pairs shortest paths. It is obtained by removing all edges that are not the shortest path between and . I…
Universal Lower Bounds and Optimal Rates: Achieving Minimax Clustering Error in Sub-Exponential Mixture Models
Maximilien Dreveton, Alperen Gözeten, Matthias Grossglauser +1
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 label…
Exact Recovery and Bregman Hard Clustering of Node-Attributed Stochastic Block Model
Maximilien Dreveton, Felipe S. Fernandes, Daniel R. Figueiredo
Network clustering tackles the problem of identifying sets of nodes (communities) that have similar connection patterns. However, in many scenarios, nodes also have attributes that…
When Does Bottom-up Beat Top-down in Hierarchical Community Detection?
Maximilien Dreveton, Daichi Kuroda, Matthias Grossglauser +1
Hierarchical clustering of networks consists in finding a tree of communities, such that lower levels of the hierarchy reveal finer-grained community structures. There are two main…
Higher-Order Spectral Clustering for Geometric Graphs
Konstantin Avrachenkov, Andrei Bobu, Maximilien Dreveton
The present paper is devoted to clustering geometric graphs. While the standard spectral clustering is often not effective for geometric graphs, we present an effective generalizat…
Community recovery in non-binary and temporal stochastic block models
Konstantin Avrachenkov, Maximilien Dreveton, Lasse Leskelä
This article studies the estimation of latent community memberships from pairwise interactions in a network of nodes, where the observed interactions can be of arbitrary type,…
Almost exact recovery in noisy semi-supervised learning
Konstantin Avrachenkov, Maximilien Dreveton
Graph-based semi-supervised learning methods combine the graph structure and labeled data to classify unlabeled data. In this work, we study the effect of a noisy oracle on classif…