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

Obaid Ullah Ahmad, Anwar Said, Mudassir Shabbir, Xenofon Koutsoukos, Waseem AbbasarXiv 2025 · arXiv

TL;DR

This paper introduces a method to "prune" complex graphs into sparse, tree-like "learning backbones" using principles from network control theory. By leveraging the Zero Forcing (ZF) phenomenon, the authors identify minimal substructures that preserve a graph's essential dynamical properties, allowing Graph Neural Networks (GNNs) to achieve comparable—and sometimes superior—classification performance with significantly less data.

What Problem Does This Paper Address?

Graph-based machine learning is powerful but computationally expensive, especially as real-world networks (like social media or chemical molecules) grow in density and complexity. While we know that sparse representations can improve efficiency, the challenge lies in finding a "winning ticket"—a sparse subgraph that retains all the critical information of the original.

Existing sparsification techniques often rely on random sampling or simple pruning, which can lead to information loss, "over-squashing" of signals, or structural bottlenecks. The authors argue that for a graph to be "learnable," it must be "controllable." They turn to Network Control Theory to find the minimal set of edges that ensures information can still propagate effectively across the system.

Methods

The authors propose a framework to extract a Learning Backbone ($\hat{G}$) from an input graph ($G$). The core of their approach is the Zero Forcing (ZF) Process:

  1. Zero Forcing Set (ZFS): Imagine coloring some nodes black (leaders) and others white (followers). A black node can "force" its only white neighbor to turn black. A ZFS is a minimal set of leader nodes that can eventually turn the entire graph black through this chain reaction.
  2. Backbone Construction ($B_z$): The paths formed during this forcing process represent the critical "highways" for information. The authors take these paths and add a minimal number of edges to form a connected tree.
  3. Generalized Backbones ($B_d$): They also explore distance-based backbones that preserve the shortest paths between nodes and leaders, ensuring that the "latency" of information propagation remains low.
The main idea: sparsifying a graph into a learning backbone while maintaining classification accuracy.

This process effectively reduces a complex, loopy graph into a sparse tree structure that is "Strong Structurally Controllable" (SSC), meaning the system's state can be steered regardless of specific edge weights.

Datasets

The framework was evaluated on eight diverse binary graph classification datasets:

  • Molecular/Bioinformatics: MUTAG, PTC, PROTEINS, NCI1.
  • Social/Interaction Networks: Deezer Ego, GitHub Stargazers, Twitch Ego, Reddit Threads.

These range from small molecular graphs (avg. 28 nodes) to larger social structures (up to 957 nodes).

Key Insights and Ideas

  • Control = Learning: The most striking insight is the bridge between control theory and GNNs. If a graph is structurally controllable, a GNN can effectively "steer" node features to produce accurate global labels.
  • Less is More (Noise Reduction): In many cases, the backbone performed better than the full graph. This suggests that dense graphs contain "noisy" edges that actually hinder learning by creating redundant or conflicting signal paths.
  • The Power of Trees: Despite being the simplest connected structure, a carefully chosen tree (the backbone) can capture the "intrinsic behavior" of a complex network.
Fig. 3: Illustration of the proposed framework: The process begins by identifying a leader vertex subset within the graph. Using network control theory, a graph sparsification framework is then applied to derive a tree-like structure, called the ‘learning backbone’, from the original graph.

Key Results

The authors tested their backbones against six different GNN architectures (like GCN, GAT, and GraphSAGE) and compared them to both the original graphs and random spanning trees.

  • Performance Preservation: In 38 out of 48 experimental combinations, the backbones stayed within 5% of the original graph's ROC AUC.
  • Performance Enhancement: In 20 out of 48 cases, the sparse backbone actually outperformed the original graph. For example, using the UniMP model on the PTC dataset, the backbone improved performance by 9.04%.
  • Sparsity: The average degree of the graphs dropped significantly. For the Deezer Ego dataset, the average degree fell from 4.292 to 1.887, representing a massive reduction in edge data.
  • Superiority over Randomness: The control-theoretic backbones outperformed random spanning trees in approximately 80% of cases.

Limitations and Future Work

  • Topology Sensitivity: The method isn't universal. On the NCI1 dataset, performance dropped by over 10% with a GCN model, suggesting that some specific graph tasks rely on the full, dense topology to capture subtle nuances.
  • Computational Scaling: While the resulting backbone is efficient for learning, the initial computation of the Zero Forcing Set can be intensive for extremely large graphs.
  • Future Directions: The authors plan to refine the computation process for large-scale applications and further investigate how the "average degree" of a backbone correlates with its ultimate controllability and learning effectiveness.

Summary updated

Abstract

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.
BibTeX
@misc{ahmad2025learning,
  author = {Obaid Ullah Ahmad and Anwar Said and Mudassir Shabbir and Xenofon Koutsoukos and Waseem Abbas},
  title = {{Learning Backbones: Sparsifying Graphs through Zero Forcing for Effective Graph-Based Learning}},
  year = {2025},
  eprint = {2502.17713},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2502.17713},
}
Figure