An Information Theoretic Framework for Graph Novelty Generation via Latent Mixture Modeling

How can we generate novel graph data that are distinct from existing patterns while maintaining structural consistency? The authors address the challenge of novelty generation—creating data that do not belong to any known patterns—by moving beyond traditional data augmentation and extrapolation techniques, which typically aim to preserve or extend existing distributions.

The proposed framework follows a four-step process: encoding, latent mixture modeling, MDL-guided sampling, and decoding. First, graphs are embedded into a latent space using a graph autoencoder. Second, the latent distribution is modeled using a finite mixture model (FMM), specifically von Mises-Fisher mixtures, to represent different graph communities. Third, the authors introduce an MDL-guided sampling algorithm that uses description length as a criterion for acceptance. A sample is accepted as novel if it is poorly explained by existing mixture components (novelty condition) but does not significantly disrupt the global structure of the mixture model (reliability condition). Finally, the latent points are decoded back into graph structures.

The authors provide a theoretical analysis showing that the probabilities of misclassifying non-novel or unreliable samples converge to zero with explicit rates as the sample size increases, provided that appropriate threshold parameters are chosen. This allows for principled novelty generation with quantifiable risk. Empirical experiments on synthetic and benchmark graph datasets demonstrate that this information-theoretic approach allows for more effective control over the trade-off between novelty and reliability compared to existing generative methods.