Séance du 18 mars 2019

Séance organisée par Pierre Latouche et Judith Rousseau

Lieu : IHP, Amphi Darboux

14.00 : François Caron (Université d'Oxford)

Titre : Sparse graphs using exchangeable random measures: Models, Properties and Applications

Résumé : In the talk I will present the class of random graphs based on exchangeable random measures, introduced in [1]. Such class allows to model networks which are either dense or sparse, that is where the number of edges scales subquadratically with the number of nodes. For some values of its parameters, it generates scale-free networks with power-law exponent between 1 and 2. I will present the general construction, a representation theorem for such construction due to Kallenberg, and discuss its sparsity/power-law properties. Then I will introduce a specific model within this framework that allows to capture sparsity/heavy-tailed degree distributions as well as latent overlapping community structure, and a Markov chain Monte Carlo algorithm for posterior inference with this model. Experiments are done on two real-world networks, showing the usefulness of the approach for network analysis.

Based on joint work with Emily Fox, Adrien Todeschini, Xenia Miscouridou, Judith Rousseau.

References:

[1] F. Caron, E.B. Fox. Sparse graphs using exchangeable random measures. Journal of the Royal Statistical Society B (with discussion), vol. 79, Part 5, pp. 1295-1366, 2017.

https://rss.onlinelibrary.wiley.com/doi/epdf/10.1111/rssb.12233

[2] F. Caron, J. Rousseau. On sparsity and power-law properties of graphs based on exchangeable point processes. arXiv:1708.03120, Aug. 2017.

https://arxiv.org/abs/1708.03120

[3] A. Todeschini, X. Miscouridou, F. Caron. Exchangeable Random Measures for Sparse and Modular Graphs with Overlapping Communities. arXiv:1602.0211, version 2, Aug. 2017.

https://arxiv.org/pdf/1602.02114

15.00 : Laurent Massoulié (INRIA)

Titre : Inference in stochastic block models and phase transitions

Résumé : In this talk I will describe results on polynomial time reconstruction of block structure from stochastic block models above the so-called Kesten-Stigum phase transition. In particular spectral methods based on various graph-related matrices will be considered, as well as their robustness properties. I will also discuss the existence of a hard phase below the Kesten-Stigum threshold, where reconstruction is feasible in exponential time but no polynomial time algorithm is known to succeed.

16.00 : Stéphane Robin (INRA AgroParisTech)

Titre : Stochastic block models: beyond variational inference

Résumé : (joint works with S. Donnet and C. Matias). In the paste decades, the stochastic blockmodel has become a popular tool for the statistical analysis of networks. In its simple version, the model assumes that each node belongs to unobserved class and that the value of each edge depends on the respective node memberships. The presence of latent variables (the node memberships) and the specific structure of the data (a network), hamper standard frequentist or Bayesian statistical inference. Many approach rely on variational approximations, which result in efficient inference algorithms, but with few statistical guaranties.

We will introduce two attempts to build upon variational inference to achieve regular statistical inference with usual guaranties. We will first show how an approximate posterior distribution can be derived from a variational approximation and present a sequential Monte Carlo algorithm heading to the true posterior. We will then introduce a composite likelihood approach providing consistent and asymptotically normal estimators.