Forecasting Betweenness Centrality with Graph Neural Networks

Abstract

Betweenness Centrality (BC) is a fundamental measure in network analysis that quantifies, for each node, its importance in terms of their relative positions and ability to efficiently connect to other nodes and facilitate the flow of information of the network. Its analysis can lead to relevant applications on various domains, such as identifying influential individuals in social networks, critical nodes in transportation networks, and essential proteins in biological networks. However, its computation is really expensive when dealing with graphs with a large number of nodes and connections, as is often seen in real-world graphs. In view of this, we analyse the possibility of applying Graph Neural Networks for the computation of BC with the hope of reducing the computational effort needed. In order to find a solution for our purpose, we conducted extensive research in which we found a Graph Neural Network model introduced by [1] for the prediction of the Betweenness Centrality. Therefore, we analysed this approach in depth in order to understand its main features and perform some experiments. In this work we perform and reproduce a selection of the experiments shown by [1], extend- ing their analysis in terms of parameter variability. To further assess the model’s performance in realistic scenarios, we introduce novel experiments considering new metrics and the inclu- sion of graphs that show community structure for the analysis of the model’s accuracy. Our results reveal that the accuracy of the model is heavily influenced by the specific graphs used for training and testing, and that the inclusion of trivial solutions can lead to misleadingly high accuracy. The insights gained from our research contribute to a better understanding of the application of GNNs for BC computation and provide meaningful conclusions for future investigations in this field.