Control Theoretic Zero Forcing Trees Sparsify Graphs While Preserving Classification Performance

A control-theoretic framework that prunes graphs into minimal zero-forcing trees preserves downstream graph classification accuracy while drastically reducing edge density across benchmark datasets. In an empirical evaluation spanning nine real-world network benchmarks and six graph neural network architectures, researchers demonstrated that sparsified subgraphs rooted in strong structural controllability principles can match or exceed the performance of complete graphs. The approach treats networked graphs as dynamical systems, identifying minimal structural backbones that retain intrinsic control dynamics. Rather than relying on purely statistical filtering or arbitrary distance heuristics, the strategy leverages the zero-forcing process to extract connected tree backbones that guarantee theoretical controllability bounds. Across fifty-four evaluated model and dataset configurations, the zero-forcing set backbones maintained classification performance within five percent of original graphs in forty-three cases and outright outperformed the dense graphs in twenty instances, establishing that critical graph-learning signals can persist across severely simplified network topologies.

Graph classification tasks in machine learning assign discrete category labels to entire graph instances, supporting applications that range from identifying mutagenic compounds in cheminformatics to categorizing conversational threads and collaboration dynamics in social platforms. However, real-world graphs frequently present high edge densities and structural noise, which introduce computational bottlenecks and risk degrading the predictive accuracy of graph neural networks. While existing sparsification methods frequently aim to optimize algebraic connectivity, maintain distance spanners, or preserve community structures through modularity and disparity filtering, these structural objectives often fail to align with the representations required for downstream predictive learning. Alternative techniques such as subgraph sampling, DeepWalk embedding, or Personalized PageRank can inadvertently densify the underlying graphs or introduce heavy computational requirements. Addressing these limitations through the Graph Lottery Ticket Hypothesis, the researchers investigated whether network control theory could extract sparse tree subgraphs that retain only the essential edges governing information diffusion and node interactions.

The foundational framework models an undirected network of nodes as a linear time-invariant dynamical system governed by state equations where system matrices reflect the underlying topology. In this formulation, a subset of nodes is designated as input leaders that apply external signals to regulate the states of the remaining follower nodes across finite time intervals. A graph achieves strong structural controllability when the controllability matrix attains full rank for all feasible non-zero edge weights matching the graph structure, ensuring that control rank remains entirely independent of specific numerical link weights. The dimension of the controllable subspace represents the minimum attainable rank of the controllability matrix across all permissible system matrices, which encompass adjacency, Laplacian, and signless Laplacian matrices. Identifying a controllability backbone requires isolating a minimal edge set whose retention guarantees that any encompassing subgraph maintains at least the controllable subspace dimension of the complete original graph under structural perturbations.

To establish this minimal edge backbone, the researchers utilized zero forcing, an iterative vertex-coloring process that provides a formal lower bound on the strong structural controllability dimension. Under the standard zero-forcing color-change rule, an initial set of black leader vertices sequentially colors adjacent white vertices black whenever a black vertex has exactly one uncolored white neighbor. The derived set denotes the complete set of vertices colored black once propagation ceases, and when this derived set spans the entire graph, the initial leaders constitute a valid zero-forcing set. Because the cardinality of the derived set establishes a rigorous lower bound on the network controllability rank, extracting the sequence of forced edges that propagate coloring from the leaders allows the construction of a sparsified substructure that mathematically preserves the network’s foundational dynamical controllability properties.

The primary sparsification procedure constructs the zero-forcing learning backbone by computing a leader set via a greedy heuristic, generating an acyclic forest consisting of paths originating from each leader node. This initial zero-forcing backbone contains exactly the number of total vertices minus the number of leader vertices, distributed across multiple disconnected components. To ensure usability in standard graph neural networks, the algorithm reintroduces a minimal selection of edges from the original graph to merge these disjoint components into a single connected tree containing exactly one less edge than the total vertex count. Because the underlying zero-forcing paths already satisfy full controllability, connecting the forest into a unified spanning tree preserves strong structural controllability regardless of which valid original edges are reintroduced. The worst-case computational complexity of this construction is governed by the greedy zero-forcing search, which executes in time bounded by the square of the vertex count multiplied by the sum of vertices and edges, while the subsequent breadth-first search and component-merging operations execute in linear time relative to network size.

Alongside the tree-structured zero-forcing backbone, the researchers examined a generalized distance-based control backbone that preserves network controllability while permitting slightly denser topologies. Graph distances dictate the shortest-path communication intervals required for control inputs to permeate a network, directly influencing system stability, responsiveness, and control rank lower bounds. By computing distance-to-leader vectors that record the shortest path lengths between every graph node and each designated leader, the distance-based framework constructs a subgraph with an edge count proportional to the total number of nodes. Although the distance-based approach offers structural flexibility by maintaining key communication pathways, it lacks the formal topological guarantee of producing a connected tree for every connected graph. Consequently, the zero-forcing tree remains the primary focus of the framework as the sparsest possible structurally guaranteed learning backbone.

Empirical validation was performed across nine distinct binary graph classification datasets spanning biological, chemical, and online interaction systems. The chemical and biological benchmarks included MUTAG, which classifies one hundred eighty-eight nitroaromatic compound graphs by mutagenicity against Salmonella typhimurium; PTC, comprising three hundred forty-four molecular graphs evaluated for rodent carcinogenicity; PROTEINS, containing one thousand one hundred thirteen secondary structure networks categorized as enzymes or non-enzymes; and NCI1, which encompasses over four thousand compound graphs screened for bioactivity against lung cancer and melanoma cell lines. Social network benchmarks included IMDB-BINARY, consisting of one thousand actor co-appearance ego-networks labeled by genre; Deezer Ego, comprising user friendship networks classified by the central user’s gender; GitHub Stargazers, containing developer collaboration graphs categorized by machine learning or web development domain expertise; Twitch Ego, evaluating whether users interact with single or multiple games; and Reddit Threads, classifying conversational quality based on user interaction dynamics.

The evaluation tested six graph neural network models: Graph Convolutional Networks (GCN), GraphSAGE, k-GNN, Universal Message Passing (UniMP), Residual Gated Graph ConvNets (ResGatedGCN), and Graph Attention Networks (GAT). All architectures were implemented with a uniform structure featuring three GNN layers with sixty-four hidden units, Sort Aggregation, two one-dimensional convolutional layers with max pooling, and a final two-layer multi-layer perceptron containing thirty-two hidden units per layer. All computational workloads were executed on a dedicated Lambda workstation equipped with an AMD Ryzen Threadripper PRO 3975WX thirty-two-core processor, five hundred twelve gigabytes of system memory, and an NVIDIA RTX 3090 graphics processing unit with sixteen gigabytes of video memory.

Classification efficacy was measured via Receiver Operating Characteristic Area Under the Curve (ROC AUC) scores, comparing zero-forcing backbones directly against full graphs. In molecular datasets like PTC, sparsification enhanced performance, with the transformer-based UniMP achieving a 9.04 percent improvement in ROC AUC when trained on the backbone rather than the complete graph. Deezer Ego networks also demonstrated marked performance gains on pruned structures. Furthermore, when compared against baseline random spanning trees derived from identical graphs, the control-theoretic backbones proved superior in approximately eighty-one percent of cases, with performance differences remaining below two percent across the remaining comparisons.

To investigate the mechanisms underlying these accuracy trends, the researchers analyzed the edge density spectrum by progressively pruning edges in ascending order of their contribution to algebraic connectivity, defined by the second smallest eigenvalue of the graph Laplacian. This analysis evaluated structural degradation alongside Network Usable Information (NUI), an information-theoretic, model-agnostic metric formulated with conditional entropy that establishes a theoretical lower bound on attainable graph neural network accuracy by quantifying the uncertainty remaining after observing topology and node features. The experiments confirmed that real-world networks contain a tripartite distribution of edges: useful edges that drive learning, redundant edges that can be omitted without penalty, and detrimental edges that introduce confounding structural noise. In Twitch Ego and Reddit Threads, both NUI and model accuracy declined gradually as redundant edges were removed, demonstrating that the zero-forcing backbone preserved the most critical learning paths.

Conversely, in the IMDB-BINARY dataset, tracking NUI and GCN accuracy revealed a complex nonlinear relationship across varying edge densities. Pruning edges down toward thirty percent density caused an initial sharp decline in both metrics, reflecting the premature loss of useful structural pathways. However, when edge density was reduced further toward ten percent, classification accuracy rebounded and exceeded the performance of the full graph, exposing the presence of detrimental edges whose elimination purged obstructive noise from the network. To verify these structural dependencies, the authors tested a reordered algebraic connectivity pruning scheme that swapped the removal order of edges positioned above and below the fiftieth percentile. The resulting trajectory exhibited mirrored performance dips at thirty percent and eighty percent density, alongside corresponding shifts at twenty percent, demonstrating that interconnected edge subsets exhibit nonlinear mutual dependencies during message passing.

The study establishes that control-theoretic principles, specifically zero-forcing coloring processes, offer a mathematically grounded methodology for extracting minimal tree-like learning backbones that preserve essential dynamic information while stripping away redundant and detrimental network connectivity. While the current findings confirm substantial edge reduction without sacrificing predictive power across binary classification tasks, the authors noted several boundaries and prospective research directions. The initial extraction of zero-forcing sets introduces upfront computational complexity that must be optimized for massive graphs. Future investigations will evaluate whether control backbones generalize effectively to node classification and link prediction tasks, and whether the theoretical framework can be extended beyond controllability to simultaneously preserve system observability, which governs internal state inference, and dynamic stability in complex interconnected networks.

Subject of Research: Control-theoretic graph sparsification for graph classification using zero-forcing backbones

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

Article References: Ahmad, O. U., Said, A., Koutsoukos, X., & Abbas, W. (2026). Extracting learning backbones: a zero-forcing-based approach to graph sparsification for graph classification. Applied Network Science, 11(1), Article 38. https://doi.org/10.1007/s41109-026-00789-0

Image Credits: AI Generated

DOI: 10.1007/s41109-026-00789-0

Keywords: graph sparsification, zero forcing, learning backbones, graph classification, network control theory, strong structural controllability, graph neural networks, algebraic connectivity, network usable information, spanning trees, graph convolutional networks, UniMP, MUTAG, PTC dataset, IMDB-BINARY, edge density