AI_Meetup_Challenge_2026_Jakub_Soska

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é:

1. 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])
2. 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)

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

pip install torch torch-geometric networkx
python run_model.py graph.json
# vlastný graf:
python run_model.py moj_graf.json

Formát vstupu (JSON, presne 10 vrcholov A–J, hrany s strength ∈ (0,1)):

{
  "nodes": ["A","B","C","D","E","F","G","H","I","J"],
  "edges": [["A","C",0.6], ["C","B",0.7], ["A","B",0.2]]
}

Výstup: Predicted path: ['A', 'C', 'B']

Súbory