Evolutionary Algorithms for Generating Graphs Matching Desired Laplacian Spectra

Graphs play a crucial role in many applications, ranging from drug discovery to social network modeling and astronomy. Generative models for graphs have substantially advanced in recent years, but we identify relatively simple scenarios where state-of-the-art models struggle to converge within a standard compute budget, or exhibit prohibitively slow generation times. We propose a generative architecture that achieves quality competitive with state-of-the-art models and is orders of magnitude faster at generation. Our approach is inspired by the Aldous-Hoover theorem, a classic representation theorem that characterizes any probability distribution of graphs that is invariant to permutations of node indices or exchangeable. This theorem establishes that three ingredients suffice: a graph-level latent variable, a set of exchangeable node-specific latent variables, and a so-called graphon function that maps graph- and node-level variables to the probability of an edge between any node pair. Given a training set of graphs, our exchangeable Variational Graph AutoEncoder (xVGAE) learns an approximation to their underlying graphons, as well as graph- and node-level latent variables. We show that our xVGAE encodes latent representations that correlate with graph- and node-level properties, and can (quickly, in one shot) generate new graphs that closely match key training set statistics.

Molecule generation methods that leverage generative models have been successfully applied to drug discovery. However, they often require extensive pre-training, suffer statistical biases in the training data, and might suffer from limited interpretability of generated chemical structures. In this work, we introduce SpectralMol, an algorithm based on evolutionary computation that processes chemical structures as a compact matrix of Fourier coefficients, projected onto a fixed basis to generate position-wise latent vectors for SELFIES decoding. The NSGA-II algorithm enforces diversity and enable separate objective functions rather than collapsed objectives into a scalar reward. The quality of the algorithm was tested against standardized benchmarks. The results show comparable aggregate benchmark performance with a task-dependent profile: SpectralMol is strongest on several multi-parameter optimization tasks. The same benchmark was used to perform an ablation study to demonstrate the advantages of a structured latent matrix. Finally, method was tested on a realistic ClpP-targeted drug-discovery benchmark, comparing it with the reinforcement-learning-based model under a fixed oracle-call budget. SpectralMol generates more docking hits and more diverse scaffolds while maintaining competitive physicochemical properties. The representation adopted in this work can cleanly separates scaffold-level modifications from localized substructure variations, as the former occur with perturbations of low-frequency Fourier modes and the latter with perturbations of high-frequency Fourier modes. The results support the evidence that frequency-controlled evolutionary dynamics provide an interpretable, efficient, and training-free route to multi-objective molecular design.

Graph-based techniques and spectral graph theory have enriched the field of machine learning with a variety of critical advances. A central object in the analysis is the graph Laplacian L, which encodes the structure of the graph. We consider the problem of learning over this Laplacian in a distributed streaming setting, where new edges of the graph are observed in real time by a network of workers. In this setting, it is hard to learn quickly or approximately while keeping a distributed representation of L. To address this challenge, we present a novel algorithm, GSQUEAK, which efficiently sparsifies the Laplacian by maintaining a small subset of effective resistances. We show that our algorithm produces sparsifiers with strong spectral approximation guarantees, all while processing edges in a single pass and in a distributed fashion.