How do probabilistic graphical models and graph neural networks look at network data?

Abstract Graphs are a powerful data structure for representing relational data and are widely used to describe complex real-world systems. Probabilistic graphical models (PGMs) and graph neural networks (GNNs) can both leverage graph-structured data, but their inherent functioning is different. The question is how do they compare in capturing the information contained in networked datasets? We address this objective by solving a link prediction task and we conduct three main experiments, on both synthetic and real networks. The first focuses on how PGMs and GNNs handle input features, considering both their type and dimensionality. The second investigates their robustness to noise injected either into node features or graph edges, while the third investigates the impact of graph heterophily. PGMs do not necessarily require features on nodes, while GNNs cannot exploit the network edges alone, and the choice of input features matters. We compare standard GNNs architectures with three PGMs models, variants of stochastic block models. We find that GNNs are outperformed by PGMs when input features are low-dimensional or noisy, mimicking many real scenarios where node attributes might be scalar, missing or corrupted. When high-quality, high-dimensional input features are available and the graph is assortative, both methods can achieve comparable performance on average, but with GNNs outperforming PGMs on a fold-by-fold basis on real networks. Then, we find that PGMs are more robust than GNNs when the heterophily of the graph is increased. Introducing noise into the edges amplifies these trends: the GNN advantage on real assortative graphs diminishes, while the regimes in which PGMs outperform GNNs become even more pronounced. Finally, to assess performance beyond prediction tasks, we also compare the two frameworks in terms of their computational complexity and interpretability.