Expanders meet Expressivity: Universal Approximation on fixed sparse masks

Recent work on pruning and the lottery-ticket hypothesis suggests that the graph topology of a sparse subnetwork matters for its performance. Spectral expanders and Ramanujan graphs have emerged as promising masks: they combine sparsity with strong global connectivity, and empirical studies report high accuracy and, in some settings, robustness to noise, even at high sparsity. Whether such masks are justified by approximation theory has remained open. Prior results establish that sparse masks without a spectral gap can emulate ReLU networks with unbounded depth and signed weights. Can a fixed, constant-degree expander mask do so efficiently, with the connections responsible for expansion carrying the computation themselves? We answer affirmatively for ReLU networks. Using auxiliary Ramanujan graphs, we build for every admissible width a three-regular mask, independent of the target and repeated in every layer, whose connections both give it a width-independent spectral gap and route values through the network. Networks on these masks represent exactly every ReLU network, with width linear in the number of neurons and nonzero weights per layer and polylogarithmic depth overhead per layer. Expansion also makes this representation robust to pruning. In a block version of the mask built from a bipartite expander, exact representation survives the deletion of a fixed fraction of the connections between each pair of connected blocks in every layer, with the remaining weights chosen afterwards; a same-degree construction without expansion loses input dependence under an allowed pruning. We also separate spectral expansion from routing: a width-seven Ramanujan mask, stacked any number of times, cannot realise every permutation of its neurons by moving values along vertex-disjoint paths. Moreover, we give uniform approximation rates with explicit width, depth and accuracy, including constructions with bounded weights and activations. We also obtain encoding lengths of optimal order for H\"older classes with exponent at most one under a fixed decoder, extend the results to compositions of Lipschitz functions that each depend on few variables, and prove stability bounds under perturbation of all weights. These results show that expander topology is compatible with efficient exact representation, complementing the empirical success of expander and Ramanujan masks in pruning and lottery-ticket settings.