Beyond Graph Diameter: Structural Determinants of Long-Range Information Propagation in Message-Passing Neural Networks

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.