Message-passing on hypergraphs: detectability, phase transitions and higher-order information
Abstract
Hypergraphs are widely adopted tools to examine systems with higher-order interactions. Despite recent advancements in methods for community detection in these systems, we still lack a theoretical analysis of their detectability limits. Here, we derive closed-form bounds for community detection in hypergraphs. Using a Message-Passing formulation, we demonstrate that detectability depends on hypergraphs’ structural properties, such as the distribution of hyperedge sizes or their assortativity. Our formulation enables a characterization of the entropy of a hypergraph in relation to that of its clique expansion, showing that community detection is enhanced when hyperedges highly overlap on pairs of nodes. We develop an efficient Message-Passing algorithm to learn communities and model parameters on large systems. Additionally, we devise an exact sampling routine to generate synthetic data from our probabilistic model. With these methods, we numerically investigate the boundaries of community detection in synthetic datasets, and extract communities from real systems. Our results extend the understanding of the limits of community detection in hypergraphs and introduce flexible mathematical tools to study systems with higher-order interactions.
Nicolò Ruggeri
PhD student
My research interests include, but are not limited to, Probabilistic Learning and Network Science, as well as connected fields. In particular, I aim at understanding how current probabilistic models can be improved upon, both on a representation and training level. I am also fascinated by how different ideas and concepts from within and outside ML interpolate in interesting and novel developments. Therefore, I strive to keep a broader view on theoretical and practical insights originating from different fields.
Alessandro Lonardi
PhD student
The main focus of my current research is studying routing problems combining approaches stemming from optimal transport and belief propagation. In particular, I am interested in understanding how different route selection mechanisms affect traffic and total path length of networks. The applications of my work span from urban to biological networks. Previously I was a Master’s Student in Mathematical Engineering at UniPd (Padua, Italy), where I also obtained my Bachelor’s degree in Physics.
Caterina De Bacco
Associate Professor
My research focuses on understanding, optimizing and predicting relations between the microscopic and macroscopic properties of complex large-scale interacting systems.