BirkhoffVis

Status: 🟒 Active
Language: Python
Category: Research Software
Repository: https://github.com/st7ma784/birkhoff_visualizer

Overview

Mathematical conceptual ML view

Key Features

  • Demo GraphML

  • WEB UI

  • docker

Technologies & Tags

AI β€’ docker β€’ Machine Learning β€’ prrof-of-concept

Recent Activity

Last Commit: 2025-09-08 by Steve Mander Commit: 10770dcd - fx

Repository Documentation

Birkhoff Polytope Visualizer

This is a lightweight web interface for visualizing doubly stochastic matrices and permutation matrices, which form the Birkhoff polytope - a convex polytope whose vertices are the permutation matrices.

The application now includes three main components:

  1. Matrix Heatmap View - Visualizes matrices as heatmaps with value annotations

  2. Graph View - Interactive graph visualization showing the navigable structure of the Birkhoff polytope

  3. ML Experiment - Reinforcement learning experiment using PPO to solve the Linear Sum Assignment problem

Features

Matrix Heatmap View

  • Generate random matrices and project them onto the Birkhoff polytope using Sinkhorn iterations

  • Create permutation matrices (vertices of the Birkhoff polytope)

  • Generate convex combinations of permutation matrices

  • Project custom matrices onto the Birkhoff polytope

  • Visualize matrices as heatmaps with value annotations

  • Display row and column sums to verify doubly stochastic properties

Graph View

  • Interactive visualization of mathematical structures as graphs using D3.js

  • Two visualization modes toggleable in the interface:

    • Birkhoff Polytope Mode: Visualizes the Birkhoff polytope as a Cayley graph

      • Nodes represent permutation matrices (vertices of the polytope)

      • Edges connect permutations that differ by a single transposition

      • Click on nodes to visualize the corresponding permutation matrix

      • Detailed analysis of row/column overlaps and intersections

    • Assignment Lattice Mode: Visualizes the constraint structure of matrix assignments

      • Nodes represent matrix positions (i,j)

      • Edges connect positions that share the same row or column

      • Shows how assignments block other values in their row/column

ML Experiment

  • Reinforcement learning solution to the Linear Sum Assignment problem using Proximal Policy Optimization (PPO)

  • Environment treats each permutation of assignments as a vertex in a graph, with edges between permutations differing by exactly 2 assignments

  • Agent learns to traverse the graph to find optimal assignment solutions

  • Enhanced with early stopping, layer normalization, and dropout for better training stability

  • Action space pruning implemented to address factorial growth bottleneck for larger matrices

  • Solution quality comparison with Hungarian algorithm for benchmarking

  • Detailed agent logging and graph traversal visualization for interpretability

  • Weights & Biases integration for experiment tracking

Requirements

  • Python 3.7+

  • PyTorch

  • NumPy

  • Matplotlib

  • Flask

  • PyTorch Lightning

  • SciPy

  • Weights & Biases

Installation

  1. Install the required packages:

pip install -r requirements.txt

  1. For the ML experiment, additional dependencies are required:

pip install pytorch-lightning wandb scipy

Usage

Web Interface

  1. Run the Flask application:

python app.py

  1. Open your browser and navigate to http://localhost:5001

  2. For the matrix heatmap view, use the controls to generate different types of matrices:

    • Random Matrix: Creates a random matrix and projects it onto the Birkhoff polytope

    • Permutation Matrix: Generates a permutation matrix (vertex of the polytope)

    • Convex Combination: Creates a doubly stochastic matrix as a combination of permutation matrices

  3. You can also enter custom matrix values in the text area and project them onto the Birkhoff polytope.

  4. Navigate to http://localhost:5001/graph to access the interactive graph visualization.

  5. In the graph view, you can:

    • Select matrix size (2-5) for visualization

    • Toggle between Birkhoff Polytope and Assignment Lattice modes

    • Generate the graph with the β€œGenerate Graph” button

    • Drag nodes to reposition them in the visualization

    • Click nodes to view detailed information in the matrix view

    • Switch between graph and matrix views using the toggle buttons

ML Experiment

  1. Navigate to the ML directory:

cd ML

  1. Run the training script with desired hyperparameters:

python train.py --matrix_size 4 --epochs 50 --lr 3e-4 --gamma 0.99 --epsilon 0.2 --entropy_coef 0.01 --value_coef 0.5 --update_timesteps 20

  1. The experiment will automatically log to Weights & Biases and save checkpoints.

  2. View the results and metrics in the console output or on the W&B dashboard.

Understanding the Birkhoff Polytope

The Birkhoff polytope B_n is the set of all nΓ—n doubly stochastic matrices (matrices with non-negative entries where each row and column sums to 1).

Key properties:

  • It has n! vertices, each corresponding to a permutation matrix

  • Any doubly stochastic matrix can be represented as a convex combination of permutation matrices (Birkhoff-von Neumann theorem)

  • The visualization shows how matrices relate to this polytope structure

Quick Start

# Clone the repository
git clone https://github.com/st7ma784/birkhoff_visualizer
cd BirkhoffVis

# Install dependencies (if requirements.txt exists)
pip install -r requirements.txt

# Or install in development mode
pip install -e .