Descriptive Complexity and Graph Neural Networks

Abstract

Koneoppimisen sisällä kehittynyt syväoppiminen on erityisesti viimeisen vuosikymmenen aikana noussut yhdeksi merkittävimmistä tämänhetkisistä tutkimusaiheista [68]. Suuri osa kehityksestä on kuitenkin perustunut kroonisen epäluotettavaan empiiriseen tutkimukseen samalla kun aiheen matemaattinen teoria on jäänyt pienemmälle huomiolle [40]. Erityistapauksessa, jossa käsiteltävänä on graafimuotoinen data, ovat graafineuroverkot [33, 31] saavuttaneet merkittävän suosion huolimatta siitä, että niiden teoreettiset perusominaisuudet ovat pitkään jääneet epämääräisiksi. Esimerkiksi näiden mallien ilmaisuvoimaa, eli niiden kykyä ilmaista eri funktioita syötetyllä datalla, on vasta hiljattain ymmärretty paremmin [11]. Yhdeksi lupaavaksi lähestymistavaksi tässä on osoittautunut kuvaileva vaativuusteoria, jossa tavoitteena on löytää näitä malleja karakterisoivia logiikoita [41].

Tässä tutkielmassa käsittelen kuvailevan vaativuusteorian soveltamista graafineuroverkkoihin. Luvun 1 johdannon jälkeen aloitan tutkielman varsinaisen sisällön luvussa 2 kattavalla kirjallisuuskatsauksella aiheen historiasta, minkä jälkeen kuvailen yksityiskohtaisesti luvussa 3 miten Ahvosen ja muiden [8] rekurrenttien liukuluvuilla laskevien graafineuroverkkojen karakterisaatio laskevalla modaalisubstituutiokalkyylillä toimii. Kuvailen myös, miten globaalin lukemisen lisääminen graafineuroverkkoihin voidaan simuloida logiikan puolella tätä vastaavalla globaalilla laskevalla modaalitimantilla.

Luvussa 4 tarkastelen erästä tunnettua graafineuroverkkojen erotteluvoiman rajaa eli Weisfeilerin ja Lemanin algoritmia [86, 61] sekä sitä, millä keinoin sen yli voidaan päästä. Eri vaihtoehdoista tehokkain on Saton ja muiden [77] kehittämä noodirandomointi, jossa – hieman yksinkertaistettuna – jokaiselle noodille asetetaan yksilöllinen tunniste. Osoitan uutena tuloksena, että Ahvosen ja muiden [8] karakterisaatiotulosta voidaan helposti laajentaa noodirandomoituun tapaukseen sallimalla logiikassa propositiosymbolien kvantifiointi. Tutkielman lopuksi tutkin tätä uutta logiikkaa tarkemmin muun muassa vertailemalla sitä erääseen sen muunnokseen, joka poikkeaa siitä syntaktisesti vain hieman mutta osoittautuu muilta ominaisuuksiltaan varsin erilaiseksi. Tämän luvun tulokset perustuvat yhteistyöhön Antti Kuusiston kanssa.