Neural Dispersion on Graphs

We study the problem of generating structurally diverse graphs on $N$ unlabeled vertices. Given a space of such graphs $S_N$, metric $d$, and target cardinality $k$, the objective is to construct a set $\mathcal{G} \subset S_N$ that maximizes pairwise diversity under $d$. While neural generative models may appear appealing as a solution, standard approaches require samples from a target distribution that such dispersion problems lack. Thus, prior work relies primarily on combinatorial or iterative search. We instead treat diversity as an explicit optimization objective, an approach we term Neural Graph Dispersion. An ensemble of generators is optimized under a repulsive potential, producing diverse graphs along optimization trajectories as they disperse over $(S_N,d)$, and avoiding distribution fitting and per-metric retraining entirely. Experiments show our method produces high diversity while scaling N and k an order of magnitude beyond prior work. Our source code is available at https://github.com/ryienh/neural-graph-dispersion.