Graph-Generative-Models-for-Optimization-Instance-Generation

This repository contains the code, datasets, experiments, and figures developed for the thesis Graph-Generative-Models-for-Optimization-Instance-Generation.

The project investigates the use of graph generative models, with a particular emphasis on diffusion models, for generating instances of combinatorial optimization problems. The main focus is on the Maximum Independent Set (MIS) problem, exploring conditional generation strategies based on structural embeddings and persistent homology.

Repository Structure

.
├── Graph_Examples/
├── Instance_Generator/
├── MIS_Generation_Evaluation/
└── README.md

---

Graph_Examples

Contains small illustrative examples and figures used in the thesis.

Included examples

• Maximum Independent Set (MIS)
• Maximum Cut
• Traveling Salesman Problem (TSP)
• Graph Coloring
• Bimodal graph distributions

Main files

Graph_Examples/
├── bimodal.py
├── problems.py
└── plots/

These scripts are used primarily for producing figures appearing in the thesis.

---

Instance_Generator

The core implementation of the graph generation framework.

Instance_Generator/
├── configs/
├── data/
├── generated/
├── src/
├── tools/
└── scripts/

---

Training

Training is launched through:

python src/main.py

Model and experiment settings are defined in:

configs/

which contains:

• Dataset configurations
• Model configurations
• Training hyperparameters
• Experiment settings

---

Graph Generation

Unconditional generation

python src/generate_graphs.py

Conditional generation

python src/generate_conditioned_graphs.py

Generated samples will be stored in:

generated/

---

MIS_Generation_Evaluation

This directory contains the experiments and analysis used to evaluate generated graph instances.

MIS_Generation_Evaluation/
├── data/
├── experiment_new/
├── models/
├── create_datasets.ipynb
└── create_plots.ipynb

---

Visualizations

The folder

experiment_new/

contains figures used in the thesis, including:

• PCA projections
• Kernel density estimates
• Performance comparisons
• Embedding distributions
• Bimodal generation results
• Degeneracy analyses

---

Jupyter Notebooks

Dataset construction

create_datasets.ipynb

Plot generation

create_plots.ipynb

These notebooks reproduce many of the figures presented in the thesis.

---

Typical Workflow

1. Train a diffusion model

python src/main.py

using one of the configuration files inside:

configs/

---

2. Generate graph instances

Unconditional generation:

python src/generate_graphs.py

Conditional generation:

python src/generate_conditioned_graphs.py

---

3. Evaluate generated graphs

Use the notebooks and scripts inside

MIS_Generation_Evaluation/

to:

• Compare original and generated distributions.
• Visualize embeddings.
• Compute graph statistics.
• Reproduce thesis figures.

---

Research Topics

This work combines ideas from:

• Graph Generative Models
• Diffusion Models
• Graph Neural Networks
• Combinatorial Optimization
• Maximum Independent Set
• Conditional Generation
• Persistent Homology
• Topological Data Analysis
• Representation Learning
• Distribution Matching