Graph generation improved by sequences of node colors and latent encoding
WL-SeqVAE: Sequence-Based Graph Generation Using Variational Autoencoders and Weisfeiler-Leman Colors
Machine Learning
Summary
Generating graphs, like molecular structures or networks, is often complex because graphs have many connections. The authors propose a method that turns graphs into sequences of colored nodes, summarizing local structure simply. They use a type of neural network called a variational autoencoder to learn from these sequences and create new graphs. This avoids dealing directly with large connection matrices and helps produce graphs that keep meaningful local and global features.
What this means in practice
- •For drug discovery teams: Create molecular structures that follow local chemical patterns by generating graphs from node color sequences combined with latent structural features.$Commercial implications: This enables new molecule design tools that produce valid, structurally consistent compounds for pharmaceutical companies targeting drug discovery.
- •For network infrastructure engineers: Generate synthetic network topologies reflecting realistic local and global structure for testing and simulation in communication networks.
Authors
Iakovos Evdaimon, Giannis Nikolentzos, Achilleas Tsimichodimos, Christos Xypolopoulos, Michalis Vazirgiannis
Abstract
In this paper, we introduce WL-SeqVAE, a sequence-based variational autoencoder for generating graphs. The key observation behind WL-SeqVAE is that node colors induced by the Weisfeiler-Leman (WL) algorithm provide compact discrete summaries of local graph structure and can therefore serve as structural tokens for generation. Rather than learning a distribution over adjacency matrices directly, our method maps each graph to a sequence of WL colors and employs a variational autoencoder that encodes this sequence into a Gaussian latent distribution, from which an autoregressive decoder reconstructs the graph. During generation, compatibility constraints derived from the WL colors guide node and edge predictions, combining global information from the latent representation with local structural consistency. This formulation turns graph generation into a sequence generation problem and avoids directly parameterizing a quadratic adjacency matrix. We evaluate WL-SeqVAE on molecular and general graph generation tasks. Across the evaluated datasets, WL-SeqVAE is competitive with established baselines on several local structural and molecular quality metrics. Code is available at https://github.com/iakovosevdaimon/WL-SeqVAE