AI Meetup Challenge 2026 — GNN pre aproximáciu najkratšej cesty
Autor: Jakub Soska · Súťažný projekt, AI Meet Up 2026
Čo to je
Experiment, ktorý skúma otázku: dá sa úloha tradične riešená klasickým algoritmom (Dijkstra) naučiť neurónovú sieť?
Model je Graph Neural Network, ktorá pre zadaný graf predikuje, ktoré hrany patria do najkratšej cesty medzi vrcholmi A a B — a to aj pre grafy, ktoré počas tréningu nikdy nevidela.
Prístup
Namiesto toho, aby sieť priamo „vyhŕkla" cestu, je riešenie hybridné:
- GNN ohodnotí každú hranu pravdepodobnosťou, že patrí do najkratšej cesty.
- 2×
GINEConv vrstvy (agregácia od susedov, práca s edge features)
- edge klasifikátor (MLP nad
[h_src, h_dst, edge_attr])
- Skóre sa prevedie na náklady hrán a finálnu cestu vyberie klasický
nx.shortest_path.
Tým sa kombinuje generalizácia neurónovej siete s deterministickou spoľahlivosťou grafového algoritmu pri výbere samotnej cesty.
Reprezentácia: 10 vrcholov (A–J), uzly [is_source, is_target], hrana má strength ∈ (0,1), vzdialenosť = 1 / strength.
Výsledky (testovacia množina)
| Metrika | Hodnota |
|---|
| Accuracy | ~0.90 |
| Precision | ~0.64 |
| Recall | ~0.97 |
| F1 | ~0.76 |
| Exact path match | ~0.92 |
Najdôležitejšia metrika je exact match — podiel prípadov, kde bola celá cesta predikovaná úplne správne.
Tréning: early stopping (zabránenie pretrénovaniu), threshold tuning (optimum ≈ 0.35 podľa exact match), validačné F1 stabilné okolo 0.80 na náhodne generovaných grafoch → model generalizuje, neučí sa naspamäť.
Analýza limitov (čo model nevie)
- Spoľahlivý, keď je najkratšia cesta jednoznačná a graf riedky.
- Zlyháva, keď existuje viacero veľmi podobných ciest s malými rozdielmi vo váhach.
- Ide o aproximáciu — negarantuje optimálne riešenie. Dijkstra je presný a deterministický; GNN je rýchly a generalizuje, ale robí chyby.
Spustenie
1pip install torch torch-geometric networkx
2python run_model.py graph.json
3# vlastný graf:
4python run_model.py moj_graf.json
Formát vstupu (JSON, presne 10 vrcholov A–J, hrany s strength ∈ (0,1)):
1{
2 "nodes": ["A","B","C","D","E","F","G","H","I","J"],
3 "edges": [["A","C",0.6], ["C","B",0.7], ["A","B",0.2]]
4}
Výstup: Predicted path: ['A', 'C', 'B']
Súbory
| Súbor | Obsah |
|---|
model.py | architektúra EdgeGNN (GINEConv + edge MLP) + hybridná predikcia |
run_model.py | CLI (argparse), načítanie grafu, inferencia |
model_state.pt | natrénované váhy |
config.json | hidden, threshold |
graph.json | príkladový vstup |
