CS Paper Radar

When Sparsity Breaks Connectivity: Functional Reachability and Guided Topology Dynamics in Extreme Sparse Training

Mohammad Pasande, Mateusz Jaworski, Jeroen Rook, Elena Mocanu

cs.LG ·submitted 2026-10-12 21:38 UTC · v1
code/data

Abstract

Dynamic Sparse Training (DST) periodically prunes and regrows connections, inducing a discrete dynamical mechanism over network topologies. At extreme sparsity ($\ge 99\%$), this dynamic tends to destroy input-output information pathways, and performance with standard magnitude/random updates degrades sharply. We formalize forward, backward, and functional reachability on layered sparse graphs, derive closed-form expectations for reachable neurons and edges, and show that Monte Carlo realizations match the theory. Guided by this reachability-based structure, we bias pruning toward non-functional edges and regrowth toward functionally consistent candidates. We introduce this reachability-driven modification of topology evolution as Reachability-guided in DST, referred to as guided DST. On CIFAR-10/100 and Tiny ImageNet, guided DST recovers large accuracy gaps versus unguided DST (up to $+14.4$ points at $99.9\%$ sparsity on CIFAR-100), and on MLP-Mixer guided DST remains trainable at $99.99\%$ sparsity while unguided random regrowth degrades sharply. These results cast extreme-sparse training as a connectivity-preserving dynamical process. Our implementation is publicly available at https://github.com/mzjaworski/ea_dst.

Closest papers

Nearest neighbours by meaning across the whole index.

DADP: Dynamic Activity-Dependent Pruning, A Reverse Hebbian-Inspired Structural Pruning Method

cs.LG ·2026-10-08 ·Bhushan Deshpande
similarity 0.64
Abstract · 24 Pages, 8 figures

Modern neural networks are heavily over-parameterized. This redundancy incurs substantial compute and memory overhead during training and inference. Existing pruning methods rely on post-hoc magnitude thresholds or static initialization heuristics. Consequently, they often require manual per-layer sparsity targets or expensive retraining cycles. We propose Dynamic Activity-Dependent Pruning (DADP), a biologically inspired structural plasticity mechanism. During training, DADP measures connection importance via the accumulated product of pre-synaptic activations and post-synaptic error gradients. Using a single global threshold instead of fixed layer budgets, DADP dynamically allocates sparsity across network depth while naturally inducing neuron- and channel-level pruning. Across MLP, VGG-16, ResNet-18, BiLSTM-CRF, and MiniBERT architectures, DADP matches or outperforms Magnitude, SNIP and RigL, retaining 73.67% accuracy (dense baseline: 76.06%) at 99% sparsity on ResNet-18. Finally, matrix-based Shannon entropy and effective rank measurements confirm that DADP preserves latent feature diversity at extreme sparsities without representation collapse.

0.17

Reachability is not enough: Diagnosing long-range behavior in GNNs

cs.LG ·2026-09-27 ·Filippo Maria Bianchi
similarity 0.58
Abstract

Graph neural networks (GNNs) are often called long-range because their architecture can connect distant nodes, but this does not show whether they use distant information correctly. We introduce a framework that measures how strongly inputs at each graph distance affect predictions and separates limitations due to architecture, finite approximation, training, and numerical execution. Our analysis shows that local message-passing can spread influence slowly, so a finite implementation may rely mainly on nearby inputs even when the ideal computation uses the whole graph. We also explain why mathematically equivalent filters can differ in how easily they are learned and how reliably they run. Across controlled tasks, models with similar architectural reach use distant information very differently, while low average error can hide failures on distant interactions. Together, these results show that long-range capability depends on learning to use information at the distances required by the task and preserving that use during computation.

0.33

Layerwise Decoupling for Stable Structured Sparsification of Fully Connected Layers

cs.LG stat.ML ·2026-09-17 ·Charles Kulick, Armenak Petrosyan, Sui Tang
theory similarity 0.57
Abstract

We propose a decoupled, layerwise method for structurally sparsifying the fully connected layers of pretrained neural networks. Rather than penalizing all layers jointly, our approach extracts shallow two-layer subnetworks, normalizes the inner weights, and applies a structured group penalty to the outer weight matrix of each block, processing layers sequentially to prune neurons and reduce the width of each layer. We prove that the constrained decoupled objective is equivalent at optimality to a specific joint penalty on the inner and outer weights, for any positively homogeneous activation, and thus admits a clean projected and proximal formulation. Our central finding is that this decoupled reformulation is more robust than coupled methods. In numerical experiments it provides a wider usable range of the regularization strength and a lower rate of catastrophic over-pruning than the tested joint baseline while maintaining comparable accuracy. We establish these properties in controlled classification and sparse-recovery studies, and examine their scope in a high-dimensional PINN stress test and in the feed-forward layers of OPT-1.3B.

0.19

BernBRS: Certified Backward Reachability for Deep Bernstein Neural Networks

cs.LG ·2026-11-17 ·Ibrahim Albool, Yasser Shoukry
similarity 0.57
Abstract · 18 pages, 6 figures, 7 tables

Ensuring the safety of complex neural network systems requires mathematically rigorous verification. While backward reachability analysis is a critical tool for identifying safe initial states, computing tight, formal bounds remains notoriously difficult to scale. Recent advancements have demonstrated that DeepBern-Nets neural networks utilizing Bernstein polynomial activation functions possess advantageous mathematical properties that enable exceptionally fast and tight forward reachability analysis. Building upon this efficiency, this paper introduces BernBRS, a highly accurate and scalable framework for the backward reachability analysis of DeepBern-Nets. BernBRS simultaneously computes certified inner and outer approximations of the Backward Reachable Set (BRS). Rather than relying on single convex bounding, our method intelligently refines a cover of the input space by analyzing activation patterns, splitting the input domain precisely where an exact decomposition of the relaxation gap predicts the most significant reduction in error. This targeted refinement enables high levels of scalability to highly complex and massive architectures that remain intractable for existing certified methods. We demonstrate the efficacy of our framework on high-dimensional models, including a linearized closed-loop approximation of the Half-Cheetah controller and a distilled Bernstein student of a Transformer block and we empirically study how these model-level guarantees relate to the original Half-Cheetah and TinyBERT classifier, respectively.

0.43

Looped GNNs Beyond Fixed Depth: Graph Size Generalization and Parameter-Efficient Adaptation

cs.LG ·2026-10-16 ·Zhiyang Wang, Zhishang Luo, Yusu Wang
similarity 0.57
Abstract · 36 pages, 12 figures

Generalizing from small graphs to larger ones can require computation beyond the depth of a neural model used during training. We study target tasks that admit a common local iterative computation and whose effective dependency radius grows with graph size. The central idea is to learn a local update rule through GNN pretraining, then repeatedly apply the same learned processor beyond the training depth to extend information reach on larger graphs without retraining. Calling such parameter-shared architecture a \emph{looped GNN}, we categorize six schemes for looped GNNs to separate the effects of depth extension, fine-tuning, and freeze-and-steer adaptation. Our analysis establishes fixed-depth information limits and sufficient conditions under which accurate iterative reuse overcomes them. To improve beyond unadapted reuse, we introduce \emph{Loop-Freeze-Steer} (LFS), which freezes the pretrained processor and learns a small controller to steer its repeated application, using much fewer trainable parameters than full fine-tuning. Our finite-sample analysis gives sufficient conditions for adaptation to improve performance on larger graphs. Experiments on synthetic tasks and chip placement evaluate depth extension and adaptation, highlighting LFS's accuracy--trainable-parameter trade-off for size generalization.

0.20

Discrete Diffusion for Large Graph Generation via Structural Candidate Restriction

cs.AI cs.SI ·2026-10-02 ·Yassin Mohamadi, Zeno Geradts, Marcel Worring
similarity 0.57
Abstract

Synthesizing realistic graphs at scale is vital when the graphs of interest are large and real-world samples are limited or access-sensitive. Diffusion-based generators have recently driven much of the progress, offering high modeling capacity, but most such methods have quadratic computational complexity and are hence restricted to small-scale networks, currently up to 3k nodes. Existing non-quadratic methods remain limited by memorization issues and a trade-off between scalability and generation quality. Our goal is to generate large graphs whose structural statistics --- e.g., degree distribution, clustering, and path length --- faithfully reflect those of real-world sparse graphs, without resorting to memorizing the training data. We introduce a discrete graph diffusion model that restricts training to a structurally motivated subset of node pairs --- observed edges and their wedge non-edges --- reducing training complexity below quadratic in the number of nodes. To keep the noisy graph informative throughout both the forward and reverse trajectories, we design a three-class absorbing forward process governed by a \emph{degree-aware, floored} cosine noise schedule: unlike a structure-blind schedule that adds noise to every pair identically, ours adapts to each node's degree and never fully erases the graph's structure, keeping the noisy graph informative at every step. Experiments across diverse datasets show that our model consistently ranks among the top methods for structural fidelity against existing discrete diffusion baselines in large graph generation.

0.25

Learning to Extrapolate in Depth with Looped Transformers

cs.LG ·2026-10-10 ·Huitao Yang, Jianhao Huang, Zixuan Wang, Baharan Mirzasoleiman
similarity 0.56
Abstract

Looped transformers reuse a single block across iterations, raising a natural question: how far can a block trained at one depth be safely extrapolated to greater depths? We study this question for all-pairs graph connectivity, where harder graphs require longer-range information propagation. We show that under exchangeability and symmetric positive initialization, population training at depth K converges to an update rule governed by a single effective parameter that balances graph propagation against fitting structure unresolved at training depth. This trade-off creates a finite extrapolation window: too few test-time loops provide insufficient propagation, while too many eventually create false connections. We derive explicit endpoints for this window and bound the graph hardness solvable beyond training as a function of training depth and hardness. In particular, a test depth chosen solely from the training distribution can guarantee recovery on substantially harder graphs, with a certified depth gain that grows exponentially as training depth outpaces training hardness. Experiments validate the predicted windows and show how compute budget and initialization affect the optimal training depth.

0.36

Learning Computational Structure for Sample-Efficient Prediction

cs.LG cs.AI ·2026-10-20 ·Hangyu Zhou, Constantine Dovrolis, Stephen Mussmann
benchmark similarity 0.56
Abstract · 36 pages

Statistical learning in high dimensions suffers from the curse of dimensionality. Fortunately, many functions of practical interest are compositionally sparse, meaning they admit a composition of local functions, each depending on only a few variables, allowing sample complexity to depend on local arity rather than ambient dimension. Yet realizing this benefit requires exploiting hidden compositional structure, which theory does not establish for practical gradient-based training. We study this gap with CSFRBench, a controlled benchmark that hides the target's compositional computation during training but retains it for diagnosis, and find that dense networks and sparsity-based baselines leave much of that benefit unrealized. Inspired by the spatial organization of biological neural circuits, we introduce Learned Wiring (LeWi): each neuron has a learned low-dimensional embedding, only nearby neurons connect, and embeddings and weights are trained jointly. LeWi improves sample efficiency on targets with hierarchical structure, intermediate reuse, or independent modules. Across 32 additional targets generated by independently sampled computation graphs, LeWi is the most sample-efficient method not given the target graph, with 27% lower mean learning-curve area than dense networks. Dense networks perform better on targets with a single high-arity function. LeWi's representations and connectivity align with the target computation. On 17 world-model prediction tasks spanning control, navigation, and manipulation, LeWi beats the dense baseline on 16 and wins 99/119 baseline comparisons. These results show that jointly learning connectivity and weights can exploit computational structure to improve sample efficiency.

0.21