publications

2025

1. PEIS

   Almost exact recovery in noisy semi-supervised learning

   Konstantin Avrachenkov, and Maximilien Dreveton

   Probability in the Engineering and Informational Sciences, 2025

   Abs DOI

   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 classification. In particular, we derive the maximum a posteriori (MAP) estimator for clustering a degree corrected stochastic block model when a noisy oracle reveals a fraction of the labels. We then propose an algorithm derived from a continuous relaxation of the MAP, and we establish its consistency. Numerical experiments show that our approach achieves promising performance on synthetic and real data sets, even in the case of very noisy labeled data.

2024

1. NeurIPS

   Why the Metric Backbone Preserves Community Structure

   Maximilien Dreveton, Charbel Chucri, Matthias Grossglauser, and Patrick Thiran

   In The Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024

   Abs HTML

   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 preserve many inter-community edges, because these edges serve as bridges connecting two communities, but tends to delete many intra-community edges because the communities are dense. This suggests that the metric backbone would dilute or destroy the community structure of the network. However, this is not borne out by prior empirical work, which instead showed that the metric backbone of real networks preserves the community structure of the original network well. In this work, we analyze the metric backbone of a broad class of weighted random graphs with communities, and we formally prove the robustness of the community structure with respect to the deletion of all the edges that are not in the metric backbone. An empirical comparison of several graph sparsification techniques confirms our theoretical finding and shows that the metric backbone is an efficient sparsifier in the presence of communities.

2. COLT

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

   Maximilien Dreveton, Alperen Gözeten, Matthias Grossglauser, and Patrick Thiran

   In Proceedings of Thirty Seventh Conference on Learning Theory, 2024

   Abs HTML PDF

   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-noise ratios. Simple iterative algorithms, such as Lloyd’s algorithm, attain this optimal error rate. In this paper, we first establish a universal lower bound for the error rate in clustering any mixture model, expressed through Chernoff information, a more versatile measure of model information than signal-to-noise ratios. We then demonstrate that iterative algorithms attain this lower bound in mixture models with sub-exponential tails, notably emphasizing location-scale mixtures featuring Laplace-distributed errors. Additionally, for datasets better modelled by Poisson or Negative Binomial mixtures, we study mixture models whose distributions belong to an exponential family. In such mixtures, we establish that Bregman hard clustering, a variant of Lloyd’s algorithm employing a Bregman divergence, is rate optimal.

2023

1. TNSE

   Recovering static and time-varying communities using persistent edges

   Konstantin Avrachenkov, Maximilien Dreveton, and Lasse Leskelä

   IEEE Transactions On Network Science And Engineering, 2023

   Abs DOI

   This article focuses on spectral methods for recovering communities in temporal networks. In the case of fixed communities, spectral clustering on the simple time-aggregated graph (i.e., the weighted graph formed by the sum of the interactions over all temporal snapshots) does not always produce satisfying results. To utilise information carried by temporal correlations, we propose to employ different weights on freshly appearing and persistent edges. We show that spectral clustering on such weighted graphs can be explained as a relaxation of the maximum likelihood estimator of an extension of the degree-corrected stochastic block model with Markov interactions. We also study the setting of evolving communities, for which we use the prediction at time t−1 as an oracle for inferring the community labels at time t. We demonstrate the accuracy of the proposed methods on synthetic and real data sets.

2. NeurIPS

   Exact recovery and Bregman hard clustering of node-attributed Stochastic Block Model

   Maximilien Dreveton, Felipe Fernandes, and Daniel Figueiredo

   In The Thirty-seventh Conference on Neural Information Processing Systems, 2023

   Abs HTML Video Poster

   Classic 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 are correlated and can also be used to identify node clusters. Thus, network information (edges) and node information (attributes) can be jointly leveraged to design high-performance clustering algorithms. Under a general model for the network and node attributes, this work establishes an information-theoretic criteria for the exact recovery of community labels and characterizes a phase transition determined by the Chernoff-Hellinger divergence of the model. The criteria shows how network and attribute information can be exchanged in order to have exact recovery (e.g., more reliable network information requires less reliable attribute information). This work also presents an iterative clustering algorithm that maximizes the joint likelihood, assuming that the probability distribution of network interactions and node attributes belong to exponential families. This covers a broad range of possible interactions (e.g., edges with weights) and attributes (e.g., non-Gaussian models) while also exploring the connection between exponential families and Bregman divergences. Extensive numerical experiments using synthetic and real data indicate that the proposed algorithm outperforms algorithms that leverage only network or only attribute information as well as recently proposed algorithms that perform clustering using both sources of information. The contributions of this work provide insights into the fundamental limits and practical techniques for inferring community labels on node-attributed networks.

3. preprint

   When Does Bottom-up Beat Top-down in Hierarchical Community Detection?

   Maximilien Dreveton, Daichi Kuroda, Matthias Grossglauser, and Patrick Thiran

   preprint arXiv:2306.00833, 2023

   Abs arXiv

   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 classes of algorithms tackling this problem. Divisive (top-down) algorithms recursively partition the nodes into two communities, until a stopping rule indicates that no further split is needed. In contrast, agglomerative (bottom-up) algorithms first identify the smallest community structure and then repeatedly merge the communities using a linkage method. In this article, we establish theoretical guarantees for the recovery of the hierarchical tree and community structure of a Hierarchical Stochastic Block Model by a bottom-up algorithm. We also establish that this bottom-up algorithm attains the information-theoretic threshold for exact recovery at intermediate levels of the hierarchy. Notably, these recovery conditions are less restrictive compared to those existing for top-down algorithms. This shows that bottom-up algorithms extend the feasible region for achieving exact recovery at intermediate levels. Numerical experiments on both synthetic and real data sets confirm the superiority of bottom-up algorithms over top-down algorithms. We also observe that top-down algorithms can produce dendrograms with inversions. These findings contribute to a better understanding of hierarchical clustering techniques and their applications in network analysis.

2022

1. Book

   

   Statistical Analysis of Networks

   Konstantin Avrachenkov, and Maximilien Dreveton

   2022

   DOI

2021

1. JFAA

   Higher-order spectral clustering for geometric graphs

   Konstantin Avrachenkov, Andrei Bobu, and Maximilien Dreveton

   Journal of Fourier Analysis and Applications, 2021

   Abs DOI

   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 generalization, which we call higher-order spectral clustering. It resembles in concept the classical spectral clustering method but uses for partitioning the eigenvector associated with a higher-order eigenvalue. We establish the weak consistency of this algorithm for a wide class of geometric graphs which we call Soft Geometric Block Model. A small adjustment of the algorithm provides strong consistency. We also show that our method is effective in numerical experiments even for graphs of modest size.

2020

1. preprint

   Community recovery in non-binary and temporal stochastic block models

   Konstantin Avrachenkov, Maximilien Dreveton, and Lasse Leskelä

   arXiv preprint arXiv:2008.04790, 2020

   Abs arXiv

   This article studies the estimation of latent community memberships from pairwise interactions in a network of N nodes, where the observed interactions can be of arbitrary type, including binary, categorical, and vector-valued, and not excluding even more general objects such as time series or spatial point patterns. As a generative model for such data, we introduce a stochastic block model with a general measurable interaction space S, for which we derive information-theoretic bounds for the minimum achievable error rate. These bounds yield sharp criteria for the existence of consistent and strongly consistent estimators in terms of data sparsity, statistical similarity between intra- and inter-block interaction distributions, and the shape and size of the interaction space. The general framework makes it possible to study temporal and multiplex networks with S=0,1^T, in settings where both N→∞ and T→∞, and the temporal interaction patterns are correlated over time. For temporal Markov interactions, we derive sharp consistency thresholds. We also present fast online estimation algorithms which fully utilise the non-binary nature of the observed data. Numerical experiments on synthetic and real data show that these algorithms rapidly produce accurate estimates even for very sparse data arrays.

2019

1. Book

   

   Leçons pour l’agrégation de mathématiques-Préparation à l’oral

   Maximilien Dreveton, and Joachim Lhabouz

   2019

   Abs HTML

   Ce livre sur l’oral de l’agrégation externe de mathématiques comporte des plans complets de 76 leçons d’algèbre et d’analyse. Sont principalement concernés les candidats à l’agrégation externe, mais ceux du concours interne ou du Capes pourront aussi y trouver des passages utiles. Les plans sont rédigés avec la rigueur attendue par le jury, et le niveau des résultats proposés est conforme aux attendus de l’agrégation. Les quelques passages hors programme sont balisés comme tels. Tous les résultats sont référencés, et ceux qui ne le sont pas sont rédigés avec un soin particulier (quelques résultats originaux sont détaillés en fin de livre, ce qui fait autant de développements possibles). Vous trouverez en outre de nombreuses remarques, ainsi qu’une motivation avant chaque leçon, ce qui vous aidera à donner une très bonne première impression aux jurés le jour J. Les deux auteurs ont assisté à plus de 120 oraux pour vous fournir de nombreux conseils pour réussir vos oraux.

2. WAW

   Almost exact recovery in label spreading

   Konstantin Avrachenkov, and Maximilien Dreveton

   In Algorithms and Models for the Web Graph: 16th International Workshop, WAW 2019, Brisbane, QLD, Australia, July 6–7, 2019, Proceedings 16, 2019

   Abs DOI

   In semi-supervised graph clustering setting, an expert provides cluster membership of few nodes. This little amount of information allows one to achieve high accuracy clustering using efficient computational procedures. Our main goal is to provide a theoretical justification why the graph-based semi-supervised learning works very well. Specifically, for the Stochastic Block Model in the moderately sparse regime, we prove that popular semi-supervised clustering methods like Label Spreading achieve asymptotically almost exact recovery as long as the fraction of labeled nodes does not go to zero and the average degree goes to infinity.