Neural Dispersion on Graphs

Abstract

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.