# Learning Backbones: Sparsifying Graphs through Zero Forcing for Effective Graph-Based Learning

arXiv: https://arxiv.org/abs/2502.17713 · HTML: https://mlsanity.com/paper/2502.17713/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 11 of its 29 references that are in the map.
- First posted on arXiv 24 Feb 2025.

## Builds on (most cited first, 11 of 11)

- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [Diffusion Improves Graph Learning](https://mlsanity.com/paper/1911.05485/) (2019)
- [A Unified Lottery Ticket Hypothesis for Graph Neural Networks](https://mlsanity.com/paper/2102.06790/) (2021)
- [Controllability of Brain Networks](https://mlsanity.com/paper/1406.5197/) (2014)
- [The Graph Lottery Ticket Hypothesis: Finding Sparse, Informative Graph Structure](https://mlsanity.com/paper/2312.04762/) (2023)
- [Improving Graph Machine Learning Performance Through Feature Augmentation Based on Network Control Theory](https://mlsanity.com/paper/2405.03706/) (2024)
- [Graph Distances and Controllability of Networks](https://mlsanity.com/paper/1608.04309/) (2016)
- [Controllability Backbone in Networks](https://mlsanity.com/paper/2309.02649/) (2023)

## Abstract (arXiv)

This paper introduces a novel framework for graph sparsification that preserves the essential learning attributes of original graphs, improving computational efficiency and reducing complexity in learning algorithms. 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 network control. The key idea is to generate a tree from the original graph that retains critical dynamical properties. By correlating these properties with learning attributes, we construct effective learning backbones. We evaluate the performance of our ZF-based backbones in graph classification tasks across eight datasets and six baseline models. The results demonstrate that our method outperforms existing techniques. Additionally, we explore extensions using node distance metrics to further enhance the framework's utility.