Graph-SND: Sparse Aggregation for Behavioral Diversity in Multi-Agent Reinforcement Learning

System Neural Diversity (SND) measures behavioral heterogeneity in multi-agent reinforcement learning by averaging pairwise distances over all binomn2 agent pairs, making each call quadratic in team size. We introduce Graph-SND, which replaces this complete-graph average with a weighted average over the edges of an arbitrary graph G. Three regimes follow: G=Kn recovers SND exactly; a fixed sparse G defines a localized diversity measure at O(|E|) cost; and random edge samples yield an unbiased Horvitz-Thompson estimator and a normalized sample mean with O(1/√m) concentration in the sampled edge count m. For fixed sparse graphs we prove forwarding-index distortion bounds for expanders and a spectral refinement under low-rank distance structure; for random d-regular graphs we prove an unconditional probabilistic widetildeO(Dmax/√n) bound. On VMAS we verify recovery, unbiasedness, concentration, and wall-clock scaling, with a PettingZoo TVD panel checking non-Gaussian transfer. In a 500-iteration n=100 PPO run, Bernoulli-0.1 Graph-SND tracks full SND while reducing per-call metric time by about 10×, and frozen-policy GPU timing up to n=500 follows the predicted binomn2/|E| speedup. Random d-regular expanders empirically achieve SNDGu/SND ∈ [0.9987, 1.0013] at Theta(n log n) edges. In DiCo diversity control at n=50, Bernoulli-0.1 Graph-SND preserves set-point tracking with paired reward differences indistinguishable from zero across nine matched cells while cutting per-call metric cost by ~9.5×. Together, these results show that the SND aggregation bottleneck can be removed without changing the metric's semantics, yielding a drop-in sparse alternative that scales beyond complete-graph SND and supports both passive measurement and closed-loop diversity control.