Plenary Speakers
Konstantin Avrachenkov
INRIA
- Title: Accuracy and Efficiency of Semi-Supervised Graph Clustering Methods
- Abstract: This talk covers recent advances in semi-supervised graph clustering, focusing on achieving various levels of recovery—weak, partial, and almost exact—of community structures. We begin by discussing constrained spectral clustering techniques derived from Maximum A Posteriori (MAP) estimation applied to noisy Degree-Corrected Stochastic Block Models (DC-SBMs). Their accuracy and ability to handle noisy labels is emphasized. Then, we introduce a semi-supervised method based on Glauber dynamics for an Ising model, where the energy function includes a quadratic penalty on the magnetization. We provide a mean-field limit for the magnetization of each community, resulting in a unique capability to estimate the number of steps required to achieve targeted classification accuracy. Finally, the theoretical results are illustrated with numerical examples, highlighting the practicality, accuracy, and efficiency of the discussed semi-supervised approaches, particularly in contexts involving limited or noisy labelled data. The talk is based on joint works with Maximilien Dreveton (EPFL) and Diego Goldsztajn (ORT University).
- Bio: Konstantin Avrachenkov received his Master degree in Control Theory from St. Petersburg State Polytechnic University (1996), Ph.D. degree in Mathematics from University of South Australia (2000) and Habilitation from University of Nice Sophia Antipolis (2010). Currently, he is a Director of Research at Inria Sophia Antipolis, France. He is an associate editor of Probability in the Engineering and Informational Sciences, Stochastic Models, ACM TOMPECS, IEEE Trans on Automatic Control, and on advisory boards of ACM POMACS and International Journal of Performance Evaluation. Konstantin has co-authored two books “Analytic Perturbation Theory and its Applications”, SIAM, 2013 and “Statistical Analysis of Networks”, Now Publishers, 2022, and more than 200 articles. He has won 5 best paper awards. His main theoretical research interests are Markov chains, Markov decision processes, random graphs and singular perturbations. He applies these methodological tools to the modelling and control of networks, and to design data mining and machine learning algorithms.
- Web page: https://www-sop.inria.fr/members/Konstantin.Avratchenkov/me.html
Marián Boguñá
Universitat de Barcelona
- Title: Embedding Nodes and Features in Hyperbolic Space: A Geometric Lens on Networks
- Abstract: Network geometry posits that the architecture of real-world complex networks is governed by hidden hyperbolic metric spaces: nodes occupy positions in an underlying negatively curved geometry, and observable connections arise primarily from their hyperbolic distances. This perspective unifies—and quantitatively explains—hallmark properties of complex systems, including heavy-tailed degree distributions, small-world behavior, strong clustering, self-similarity, community structure, and efficient navigability, while also furnishing a renormalization-group formalism for networks. After outlining the core principles and empirical successes of hyperbolic network geometry, I will briefly highlight one practical extension that incorporates node attributes. By treating intrinsic features as first-class entities and linking them to nodes in a bipartite graph, we embed both nodes and features within the same hyperbolic space. This joint embedding uncovers correlations between structure and attributes in real data, enables the generation of synthetic networks with realistic topology, and clarifies why feature-aware deep-learning models—such as Graph Convolutional Neural Networks—perform so well on downstream tasks. Together, the hyperbolic geometric framework and its feature-rich generalization provide a versatile toolkit for analyzing, modelling, and exploiting the multiscale organization of complex systems.
- Bio: M. Boguñá is a full professor at the Departament de Condensed Matter Physics, University of Barcelona. He graduated in Physics in 1994 and obtained his PhD in 1998. In 1999, he moved to the US to do a postdoctoral stay with Prof. G. H. Weiss at the National Institutes of Health, Washington DC. After this period, in 2003, he was awarded a Ramón y Cajal fellowship. He got the tenure position in 2008. During this period, he has also spent several months in the US as invited guest scientist at Indiana University. M. Boguñá has written over 90 publications in major peer reviewed international scientific journals: Nature, Nature Physics, Nature Communications, Nature Reviews Physics, PNAS, Phys. Rev. Letters, and Phys. Rev. X. In January 2008, he obtained the Outstanding Referee award of the American Physical Society. He was awarded as ICREA Academia researcher in 2010, 2015, and 2020. Since January 2013, he serves as an editorial board member for Scientific Reports. His research interests are focused on the study of complex systems. In particular, those systems made up of a large number of units that interact through complex topologies and, therefore, are suitable to be studied using statistical physics tools. Such systems are ubiquitous and can be found in very diverse fields: societies at the large scale, cellular networks, or communication networks like the Internet, to name just a few. One of the major challenges in this field is the understanding of the coupling between the complex topologies shown by these type of systems and the functions they perform. M. Boguñá is one of the major proponents of the new field of Network Geometry, a theory aiming at finding the geometric origin of the discrete structures underlying complex systems.
- Web page: http://complex.ffn.ub.es/~mbogunya/
Gesine Reinert
University of Oxford
- Title: Duplication-divergence models with edge deletion
- Abstract: Duplication-divergence models are a popular model for the evolution of gene and protein interaction networks. However, existing duplication-divergence models often neglect realistic features such as loss of interactions. Moreover, typically in these models, either all vertices in the network are eventually isolated or the network is dense. Motivated by assessing drug effects, this talk we first show empirical results regarding the effect of attacks on protein interaction networks, and compare them to the effect of attacks on a standard duplication-divergence model; there is a clear discrepancy. Hence there is a need for new models of protein interaction network evolution. In this talk we propose two novel models that incorporate random edge deletions into the duplication-divergence framework. Our main result gives lower and upper bounds for the proportion of isolated vertices, when the network size is large. They show that these models possess regimes in which the proportion of isolated vertices can be bounded away from 0 and 1 with high probability. Finally we present a novel model for protein complex hypergraph evolution. This is joint work with Tiffany Lo (Stockholm) and Ruihua Zhang (Oxford)
- Bio: Gesine Reinert is a Research Professor at the Department of Statistics, Oxford, and Fellow at Keble College, Oxford. Her main applied research interests are in network statistics, including the development of machine learning methods for the analysis of network data, as well as theoretical underpinnings. Her theoretical research mostly concentrates on Stein's method to derive bounds on distances between the distributions of random quantities. Gesine Reinert currently chairs the Committee on Statistical Network Science of the Bernoulli Society. She is the currently editor-in-chief of the SpringerBriefs in Probability and Mathematical Statistics. She is a Fellow of the IMS. Currently she is also a fellow of the Alan Turing Institute.
- Web page: https://www.stats.ox.ac.uk/~reinert/