An Information Theoretic Framework for Graph Novelty Generation via Latent Mixture Modeling
This work provides a principled approach to controlled novelty generation in graphs, addressing a gap in generative models for anomaly detection or creative design.
The paper introduces an information-theoretic framework for generating novel graphs that are distinct from existing patterns while preserving global structural consistency, using latent mixture modeling and MDL-based constraints. Experiments on synthetic and benchmark datasets show the method enables principled novelty generation with quantifiable risk.
We propose an information-theoretic framework for graph novelty generation, which aims to generate data that are distinct from existing patterns while preserving global structural consistency. Our approach embeds data into a latent space, models the latent distribution using finite mixture models, and generates novel samples by imposing explicit novelty and reliability conditions formulated in terms of description length. Specifically, novelty is enforced by requiring generated samples to be poorly explained by all existing mixture components, while reliability constrains their impact on the overall mixture structure under the Minimum Description Length (MDL) principle. We provide a theoretical analysis showing that, with appropriate threshold choices, the probabilities of misclassifying non-novel or unreliable samples converge to zero with explicit rates. Experiments on synthetic and benchmark graph datasets demonstrate that the proposed method enables principled novelty generation with quantifiable risk.