Extracting learning backbones: a zero-forcing-based approach to graph sparsification for graph classification

This paper introduces a control-theoretic framework for graph sparsification aimed at constructing sparse subgraphs that retain the learning capacity of the original graph, reducing structural complexity while maintaining downstream performance. We refer to these sparse graphs as learning backbones. Our approach leverages the zero-forcing (ZF) phenomenon, a dynamic process on graphs with applications in networked system control, to construct a tree that retains key dynamical properties. By exploiting the hypothesized relationship between these properties and the attributes required for effective graph-based learning, we generate the desired learning backbones. We evaluate the proposed approach on graph classification benchmarks across nine datasets and six baseline models, showing that the proposed sparsification strategy substantially reduces edge density while largely preserving classification performance, and in certain cases exhibits robustness in noisy settings. Additionally, we extend the learning backbone framework by incorporating node distance metrics as a complementary control-based sparsification strategy. Finally, we analyze the impact of edge sparsification by progressively removing edges until reaching the ZF-based learning backbone and employ the network usable information (NUI) metric to assess the learning process across varying edge densities.