Generative Graph Prototypes from Information Theory.

Area of Science:

• Graph theory
• Machine learning
• Statistical modeling

Background:

• Graph data is prevalent in various domains, necessitating efficient methods for analysis and generation.
• Existing generative models for graphs often struggle with capturing complex structural properties.
• The minimum description length (MDL) principle offers a principled way to balance model complexity and data fit.

Purpose of the Study:

• To develop a generative prototype for graph datasets using a minimum description length (MDL) approach.
• To learn a generative supergraph model capable of producing new graph samples.
• To evaluate the utility of the proposed generative model for graph classification, clustering, and synthesis.

Main Methods:

• Constructing a probability distribution for nodes and edges over a supergraph.
• Encoding supergraph complexity using approximate Von Neumann entropy.
• Employing a modified Expectation-Maximization (EM) algorithm to minimize the MDL criterion, treating supergraph structure and node correspondences as missing data.
• Generating new graphs by sampling from learned node and edge occurrence probabilities, assuming independent Bernoulli distributions.

Main Results:

• Empirical evaluations on real-world databases demonstrate the practical utility of the proposed algorithm.
• The generative model proved effective for graph classification, graph clustering, and generating new sample graphs.
• The method successfully learns a supergraph representation from which new graphs can be sampled.

Conclusions:

• The proposed MDL-based generative supergraph model provides an effective framework for graph data analysis and synthesis.
• The approach offers a robust method for learning graph structures and generating realistic graph samples.
• The demonstrated effectiveness across classification, clustering, and generation tasks highlights the model's versatility.