Unrolling Message-Passing to Understand Information Propagation in Graphs

Message-passing neural networks (MPNNs) propagate information over graphs through repeated aggregation, yet the mechanisms governing signal preservation and degradation remain difficult to characterize exactly. We study this question through unrolled linear message-passing dynamics, where graph propagation is separated from nonlinear feature transformation. This separation makes it possible to derive exact node-to-node Jacobians and to measure two explicit propagation quantities: local sensitivity, which measures pairwise information transfer across the graph, and global sensitivity, which captures depth-induced collapse of information flow. Our analysis links propagation to graph topology and graph shift operators, identifying doubly stochastic learned operators as a principled way to prevent graph-side collapse in the deep regime. The theory also distinguishes topology-dependent degradation, related to over-squashing, from global vanishing caused by repeated nonlinear message passing. Guided by this analysis, we instantiate the theory in Bi-stream Unrolled Message Passing (BUMP), which combines a given graph operator with a learned doubly stochastic operator and fuses their representations after linear propagation. The framework applies to static and temporal graphs, and achieves strong empirical performance on long-range graph prediction, heterophilic node classification, and temporal graph forecasting.