Directed Multigraph Pattern Detection — GNN Expressivity Study

Reproduces the core experiment from:

Provably Powerful Graph Neural Networks for Directed Multigraphs Egressy et al., AAAI 2024 (arXiv:2306.11586)

What this does

Trains StandardGIN vs MultiGIN on 7 AML (Anti-Money Laundering) subgraph patterns to empirically verify that standard GNNs are blind to out-degree and fan-out in directed multigraphs, while Multi-GIN fixes this.

Results

Pattern	StandardGIN	MultiGIN	Δ
degree_in	0.953	0.843	-0.110
degree_out	0.334	0.480	+0.146 ✓
fan_in	0.964	0.833	-0.132
fan_out	0.310	0.462	+0.152 ✓
scatter_gather	0.634	0.612	-0.022
cycle_3	0.000	0.000	0.000
cycle_4	0.000	0.000	0.000

MultiGIN significantly outperforms on degree_out and fan_out — exactly as proven in Proposition 4.1 of the paper. Cycles require larger graphs (n≥8192) to detect reliably.

Files

• graph_generator.py — Random circulant graph generator + pattern labelling
• models.py — StandardGIN and MultiGIN architectures
• train.py — Training loop, evaluation, results export
• directed_multigraph_visualizer.html — Interactive results dashboard (open in browser)
• results/experiment_results.json — Generated experiment results

Setup and Run

python -m venv venv
source venv/bin/activate        # Windows: venv\Scripts\activate
pip install torch torch_geometric networkx scikit-learn numpy
python train.py

Then open directed_multigraph_visualizer.html in your browser.

Context

Built during a summer fellowship at IIT Madras (via NIT Puducherry MoU) as part of a research study on GNN expressivity for blockchain/AML applications.