Graph neural networks must learn to use distant data correctly
Reachability is not enough: Diagnosing long-range behavior in GNNs
Machine Learning
Summary
Graph neural networks can connect information from faraway points in a graph, but this doesn’t mean they actually use that distant information well. The authors study how much influence distant data really has on predictions and find that limitations in design, training, or computation often make models rely mostly on nearby information. They show that even models that look similar on paper can perform very differently when it comes to using long-range data. This means it’s important not just to design networks that can reach far but to ensure they learn and keep using the right distant information needed for the task.
What this means in practice
- •For machine learning engineers: Diagnose and improve how GNNs use information from distant nodes to enhance prediction accuracy on complex graph tasks.
- •For network analysis tool developers: Develop diagnostic tools that assess and visualize the influence of graph-distance on GNN outputs, revealing hidden failure modes.
Authors
Filippo Maria Bianchi
Abstract
Graph neural networks (GNNs) are often called long-range because their architecture can connect distant nodes, but this does not show whether they use distant information correctly. We introduce a framework that measures how strongly inputs at each graph distance affect predictions and separates limitations due to architecture, finite approximation, training, and numerical execution. Our analysis shows that local message-passing can spread influence slowly, so a finite implementation may rely mainly on nearby inputs even when the ideal computation uses the whole graph. We also explain why mathematically equivalent filters can differ in how easily they are learned and how reliably they run. Across controlled tasks, models with similar architectural reach use distant information very differently, while low average error can hide failures on distant interactions. Together, these results show that long-range capability depends on learning to use information at the distances required by the task and preserving that use during computation.