no. 17 · Wednesday 18 November 2026
Dynamics-preserving graph sparsification
Abstract
Many dynamical systems unfold on networks of nodes coupled by edge interactions. This work is motivated by the following question: can we remove most edges from a networked dynamical system without significantly altering its behavior? For a given network, our goal is to find a sparser network that approximately preserves the dynamics on the nodes. We first study linear diffusion, where node values evolve according to the graph Laplacian. The dominant network sparsification method, effective resistance sampling, preserves all Laplacian eigenvalues within a uniform multiplicative bound. We show that with a limited edge budget, this is dynamically inefficient: diffusion is dominated by the slowest-decaying modes, so enforcing a uniform guarantee spends edges on fast modes that barely affect long-term dynamics. Based on this observation, we derive Diffusion Spectral Error (DSE), which evaluates in closed form the typical error in trajectories between the original and sparsified graphs over random initial conditions. Minimizing this error, which naturally prioritizes slow modes, yields sparse networks explicitly designed to preserve dynamics. At the same sparsification levels, DSE sparsification often preserves diffusion dynamics with several-fold lower error than effective resistance sampling, and up to two orders of magnitude lower on strongly modular networks. Although derived in a linear context, we empirically find that DSE sparsification gives similar improvements in the Kuramoto model (a nonlinear system of coupled oscillators), where DSE sparsification approximately preserves the synchronization threshold and, at strong coupling, order-parameter trajectories.
- fields
- Dynamical Systems