mercredi 11 février 2026

par BUTEL Nathalie

Aurora ROSSI, est une ancienne doctorante d'Emanuele Natale, en visite à i3S pour 2 semaines. Elle présentera les résultats d'un projet dans lequel elle a été impliquée avec Emanuele Natale et Frédéric Giroire.

Cette présentation scientifique débutera le mercredi 11 février 2026 à 14h00 dans l'amphi A 232 sur le Campus Sophia Tech, bâtiment A.

 

Courte biographie : 

Aurora Rossi is a postdoc at the University of Bonn and the Lamarr Institute. She completed her PhD in Computer Science at Université Côte d’Azur (COATI team) and spent two months at the Institute of Science Tokyo via the DocWalker program. Her research focuses on graph-based machine learning and its applications.

 

Titre et résumé :

BRAVA-GNN: Betweenness Ranking Approximation Via Degrees MAss Inspired Graph Neural Network

 

Computing  node importance in networks is a long-standing fundamental problem that has driven extensive study of various centrality measures.

A particularly well‑known centrality measure is betweenness centrality, which, however, becomes computationally prohibitive on large‑scale networks.

Several Graph Neural Network (GNN) models have thus been proposed to predict node rankings according to their relative betweenness centrality. However, state‑of‑the‑art methods fail to generalize to high‑diameter graphs such as road networks.

We propose BRAVA‑GNN, a GNN model that leverages the long‑observed empirical correlation between betweenness centrality and degree‑based quantities such as degree mass. This correlation motivates the use of degree masses as node features and an architecture that implicitly approximates multi‑hop degree mass through message‑passing, as well as synthetic graphs that closely match the degree distribution of real networks as the training set.

While previous work has focused on synthetic training data in the scale‑free regime, we leverage the hyperbolic random graph model, which can reproduce power‑law exponents outside the scale‑free regime, as is the case for real‑world graphs such as road networks.

Extensive experiments on real‑world networks demonstrate that our model, with 54$\times$ fewer parameters, achieves up to 214\% improvement in Kendall-Tau score and 66$\times$ speedup in inference time.

 

Ce travail a été réalisé en collaboration avec Frédéric Giroire, Emanuele Natale, Justin Dachille, Frederik Mallmann-Trenn, Sunil Kumar Maurya, Xin Liu, and Tsuyoshi Murata.