Groot: Node-Specific Global Graph Propagation via Bidirectional Forest Scans

Long-range graph propagation often relies on deep local message passing or dense global interaction mechanisms. We introduce GROOT (Global Rerooting Operator over Trees), a graph neural layer built around a bidirectional forest-scan operator. It compiles a sparse graph into a cached rooted spanning forest and computes node-specific global states through one bottom-up aggregation followed by one top-down rerooting scan. Learned channel-wise gates induce an implicit path kernel in which every source can influence every target within its forest component, without materializing a dense node-pair matrix. Edges outside the forest contribute through a single sparse source-correction term injected into the shared scan. We prove the exact equivalence between the scan and the normalized path- product kernel, characterize its conditional permutation equivariance, and establish O(ED + N D) structural work and O(E + N D) memory for width D. A custom CUDA implementation enables training on large-scale sparse graphs. Across five random seeds, GROOT consistently improves over strong local and global baselines in power-flow estimation, gas-network state estimation, water-network sensor recovery, and graph classification. On a large-scale London road graph, GROOT improves accuracy over GraphSAGE and IM-MPNN by 4.98% and 0.94%, respectively. Controlled experiments isolate the contributions of bidirectional scanning and learned gates, while molecular and citation tasks further characterize the forest-path bias. Overall, these results establish forest scanning as a practical global operator for sparse graphs with reusable tree-aligned propagation structure. Code is available at https://anonymous.4open.science/r/groot-FCC2.