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.

Machine learning models require diverse training data to learn well and generate reasonable outputs. Unfortunately, in the graph domain, creating diverse datasets is very unintuitive and challenging for humans. Moreover, current computer-aided solutions try to assemble such a set by randomly searching through an astronomically large space of possible graphs. Therefore, they end up being very slow and thus only work on graphs with very few vertices. Our paper proposes a different solution: instead of randomly searching through thousands of options, we teach a neural network to push similar looking graphs away from each other. As they are being pushed away, we take snapshots and use these to make a diverse set. Our method works well and easily scales to very large graphs. With our efficiently generated diverse datasets, other researchers can train better, smarter machine learning models that work well at bigger, more complex scales.