Quantum states featuring extensive multipartite entanglement are a resource for quantumenhanced metrology, with sensitivity up to the Heisenberg limit. However, robust generation of these states using unitary dynamics typically requires all-to-all interactions among particles. Here, we demonstrate that optimal states for quantum sensing can be generated with sparse interaction graphs featuring only a logarithmic number of couplings per particle. We show that specific sparse graphs with long-range interactions can approximate the dynamics of all-to-all spin models, such as the one-axis twisting model, even for large system sizes. The resulting sparse coupling graphs and protocol can also be efficiently implemented using dynamic reconfiguration of atoms in optical tweezers.