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$, a metric $d$, and a 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 does not exist for dispersion problems. As a result, prior work is limited to brute-force combinatorial or iterative search methods. 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 by sampling along optimization trajectories as they disperse over $(S_N,d)$. Moreover, this approach allows us to generate an initial diverse graph set and, when desired, refine it under bespoke graph distances with minimal overhead. Extensive experiments show our method produces highly diverse graphs while scaling efficiently with respect to $N$ and $k$.