Zadání diplomové práce

Reprezentace homomorfismu v grafových neuronových sítích

Velký vzrůst zájmu o umělé neuronové sítě v posledních zhruba 15 letech je především důsledkem toho, že při dostatečném množství dat a dostatečném výpočetním výkonu investovaném do učení sítě jsou schopny s vysokou přesností predikovat hodnoty téměř libovolné funkce. Kromě typů neuronových sítí, které jako vstup přijímají skaláry, vektory, pole a sekvence, včetně různých typů obrázků, zvuků a videa, se v posledním desetiletí stále častěji používají sítě, jejichž vstupem jsou silně strukturovaná data jako text, mluvená řeč, komunikační systémy či sociální sítě. Pro taková data se neuronové sítě používají k jejich zanoření (embedding) do vektorového prostoru mnohem nižší dimenze než je počet stupňů volnosti vstupních strukturovaných dat. V tomto prostoru je k dispozici mnohem bohatší spektrum metod pro analýzu dat a získávání znalostí z nich, přičemž výpočetní náročnost takové analýzy je mnohem nižší než výpočetní náročnost analýzy původních strukturovaných dat. V častém případě, kdy vstupními strukturovanými daty neuronové sítě jsou neorientované nebo orientované grafy, se taková síť obvykle označuje jako grafová neuronová síť.

Různé typy grafových neuronových sítí různým způsobem reprezentují vlastnosti grafů a vztahy mezi nimi. Hodně pozornosti bylo věnováno reprezentaci velmi důležitého vztahu izomorfismu mezi grafy. To je však vztah velmi silný a vyskytující se jen někdy, takže výsledky týkající se reprezentace izomorfismu pomocí grafových neuronových sítí často nelze použít. Pro nejčastěji se vyskytující specifický typ grafů – stromy – byla ale v teorii grafů nedávno ukázána možnost izomorfismus postupně zeslabovat posloupností částečně injektivních homomorfismů, na jejímž konci je obyčejný homomorfismus, který je naopak vztahem hodně slabým. Reprezentace částečně injektivního homomorfismu pomocí grafových neuronových sítí nicméně dosud zkoumána nebyla. Právě jejímu výzkumu by se měla věnovat navržená diplomová práce.

Pokyny pro vypracování

1. Seznamte se s grafovými neuronovými sítěmi, zejména pak s konkrétními typy těchto sítí prezentovanými v doporučené literatuře.

2. V implementačním prostředí své volby implementujte, s případným zahrnutím existujících implementací, knihovnu pro práci s grafovými neuronovými sítěmi, zahrnující alespoň konkrétní typy těchto sítí prezentované v doporučené literatuře.

3. Seznamte se s problematikou reprezentace izomorfismu v grafových neuronových sítích.

4. Seznamte se s konceptem částečně injektivního homomorfismu umožňujícím přechod od izomofrismu k homomorfismu.

5. Navrhněte možnost reprezentace částečně injektivního homomorfismu v grafových neuronových sítích a diskutujte její vlastnosti.

6. Své návrhy experimentálně ověřte pomocí dříve implementované knihovny pro práci s grafovými neuronovými sítěmi.

Doporučená literatura

· Chen, Z. et al. On the equivalence between graph isomorphism testing and function approximation with GNNs. NIPS 2019, 1−9.

· Maron H. et al. Provably powerful graph networks. NIPS 2019, 1−12.

· Nikolentzos, G. et al. K-hop graph neural networks. Neural Networks 130 (2020) 195−205.

· Schulz T.H. et al. Mining Tree Patterns with Partially Injective Homomorphisms. In: ECML PKDD 2018, 585−601.

· Xu, K. et al. How powerful are graph neural networks? ICLR 2019, 1−17.