Beyond Graph Diameter: Structural Determinants of Long-Range Information Propagation in Message-Passing Neural Networks
- 1Department of Computer Science and Media, Technical University Brandenburg (TH Brandenburg), 14770 Brandenburg, Germany
- 2Department of Molecular Biotechnology and Functional Genomics, Technical University of Applied Science Wildau (TH Wildau), 15745 Wildau, Germany
- 3Department of Computer Modeling and Intelligent Technologies, Kharkiv National University of Radio Electronics, 61023 Kharkiv, Ukraine
Abstract
Message-Passing Neural Networks (MPNNs) propagate information through iterative neighborhood aggregation, making long-range information exchange dependent on both network depth and graph structure. This study investigates whether graph diameter adequately characterizes effective information propagation and which topological properties provide additional explanatory information. A mathematical framework is developed to distinguish finite-depth reachability from communication redundancy, including formal results demonstrating that graphs with identical diameters can exhibit fundamentally different connectivity, articulation-point structures, and path redundancy. Controlled experiments were conducted on path, cycle, Erdős–Rényi, grid, and barbell graphs using a label-copying task and MPNNs with 2, 4, 6, and 10 message-passing layers. Graph-level structural measures were correlated with propagation accuracy, complemented by targeted node-removal experiments. The results show that graphs with comparable diameters can exhibit substantially different propagation performance. Average shortest-path length and clustering coefficient showed only weak associations with accuracy, whereas articulation points and edge connectivity exhibited stronger relationships. Removing high-betweenness nodes produced the largest accuracy reductions for several graph topologies, further demonstrating the importance of structurally critical communication pathways. Together, the theoretical and empirical results show that graph diameter alone provides an incomplete characterization of effective information propagation in MPNNs. Message-passing depth determines theoretical reachability, whereas effective long-range propagation additionally depends on graph topology, particularly communication redundancy, structural bottlenecks, connectivity, and the availability of alternative paths.
Related
- Exact Asymptotic Efficiency under zCDP: Diameter-Constrained Information Geometry
- Slow Beats Fast at the Kesten-Stigum Threshold: Minimax, Fisher-Information and Belief-Propagation Characterizations of the Information-Computation Gap in Sparse Stochastic Block Models
- Relevance Propagation as Entropic Optimal Transport on Filippov Neural Networks: Sinkhorn Propagation and Region Relevance in Image Classifiers
- Solving the Nonlinear Westervelt Equation in Ultrasound Propagation Using Physics-Informed Neural Networks
- Generative Replay for Equilibrium Propagation: Toward Edge-Friendly Continual Learning in Hopfield Networks
BibTeX
@article{krueger2026beyond,
title = {{Beyond Graph Diameter: Structural Determinants of Long-Range Information Propagation in Message-Passing Neural Networks}},
author = {Marc Krueger and Marcus Frohme and Alina Nechyporenko},
journal = {Mathematics},
year = {2026},
month = oct,
doi = {10.3390/math14213931},
url = {https://www.mdpi.com/2227-7390/14/21/3931},
note = {CC BY 4.0},
}
RIS
TY - JOUR
TI - Beyond Graph Diameter: Structural Determinants of Long-Range Information Propagation in Message-Passing Neural Networks
AU - Marc Krueger
AU - Marcus Frohme
AU - Alina Nechyporenko
PY - 2026
DA - 2026/10/28
JO - Mathematics
DO - 10.3390/math14213931
UR - https://www.mdpi.com/2227-7390/14/21/3931
AB - Message-Passing Neural Networks (MPNNs) propagate information through iterative neighborhood aggregation, making long-range information exchange dependent on both network depth and graph structure. This study investigates whether graph diameter adequately characterizes effective information propagation and which topological properties provide additional explanatory information. A mathematical framework is developed to distinguish finite-depth reachability from communication redundancy, including formal results demonstrating that graphs with identical diameters can exhibit fundamentally different connectivity, articulation-point structures, and path redundancy. Controlled experiments were conducted on path, cycle, Erdős–Rényi, grid, and barbell graphs using a label-copying task and MPNNs with 2, 4, 6, and 10 message-passing layers. Graph-level structural measures were correlated with propagation accuracy, complemented by targeted node-removal experiments. The results show that graphs with comparable diameters can exhibit substantially different propagation performance. Average shortest-path length and clustering coefficient showed only weak associations with accuracy, whereas articulation points and edge connectivity exhibited stronger relationships. Removing high-betweenness nodes produced the largest accuracy reductions for several graph topologies, further demonstrating the importance of structurally critical communication pathways. Together, the theoretical and empirical results show that graph diameter alone provides an incomplete characterization of effective information propagation in MPNNs. Message-passing depth determines theoretical reachability, whereas effective long-range propagation additionally depends on graph topology, particularly communication redundancy, structural bottlenecks, connectivity, and the availability of alternative paths.
SN - 2227-7390
ER -