Tekoälyn kouluttaminen graafidatalla ilman ohjausta uudella tavalla

Tekijät: Zhen Peng Wenbing Huang Minnan Luo Qinghua Zheng Yu Rong Tingyang Xu Junzhou Huang ABSTRAKTI Erilaisissa tietoverkoissa, kuten sosiaalisissa verkoissa ja viestintäverkoissa, esiintyvän sisällön rikkaus tarjoaa ennennäkemättömän potentiaalin korkealaatuisten esitysten oppimiseen ilman ulkoista valvontaa. Tässä paperissa tutkitaan, miten säilyttää ja poimia runsas informaatio graafirakenteisesta datasta upotusavaruuteen valvomattomalla tavalla. Tätä varten ehdotamme uutta konseptia, graafista keskinäistä informaatiota (GMI), mittaamaan syötegraafien ja korkean tason piilevien esitysten välistä korrelaatiota. GMI yleistää perinteisen keskinäisen informaation laskennan idean vektoritilasta graafidomeeniin, jossa solmuominaisuuksien ja topologisen rakenteen kahden näkökohdan keskinäisen informaation mittaaminen on välttämätöntä. GMI:llä on useita etuja: Ensinnäkin se on invariantti syötegraafien isomorfisille transformaatioille – väistämätön rajoite monissa olemassa olevissa graafiesitysten oppimisalgoritmeissa; Lisäksi se voidaan tehokkaasti arvioida ja maksimoida nykyisillä keskinäisen informaation estimointimenetelmillä, kuten MINE:llä; Lopuksi teoreettinen analyysimme vahvistaa sen oikeellisuuden ja järkevyyden. GMI:n avulla kehitämme valvomattoman oppimismallin, jota koulutetaan maksimoimalla GMI syötteen ja graafineuraalisen enkooderin ulostulon välillä. Huomattavat kokeet transduktiivisessa ja induktiivisessa solmuluokittelussa sekä linkkien ennustamisessa osoittavat, että menetelmämme ylittää huippuluokan valvomattomat vastineet ja joskus jopa ylittää ohjatuilla menetelmillä saavutetun suorituskyvyn. 1 JOHDANTO Luotettavan kvantitatiivisen analyysin saavuttamiseksi erilaisille tietoverkoille, graafirakenteisen datan korkealaatuinen esitysten oppiminen on muodostunut yhdeksi nykyisistä kiehtovista aiheista. Viimeaikaiset menetelmät tämän tavoitteen saavuttamiseksi, yleisesti luokiteltuna graafineuraaliverkoiksi (GNN), ovat edistyneet merkittävästi monissa oppimistehtävissä, kuten solmuluokittelussa [ , , ], linkkien ennustamisessa [ , , ], graafien kohdistamisessa [ , , ], molekyylien generoinnissa [ , , ], muutamia mainitakseni. Huolimatta hedelmällisestä edistyksestä, GNN:ien koulutus olemassa olevissa lähestymistavoissa vaatii yleensä jonkinlaista ohjausta. Epäilemättä merkintätiedon hankkiminen on kallista – manuaalinen annotointi tai lupien maksaminen, ja se on jopa mahdotonta saavuttaa yksityisyyskäytäntöjen vuoksi. Puhumattakaan siitä, että annettujen merkintöjen luotettavuus on joskus kyseenalainen. Siksi, korkealaatuisen graafiesityksen saavuttaminen ilman ohjausta on välttämätöntä monissa käytännön tapauksissa, mikä motivoi tämän paperin tutkimusta. 35 42 50 26 27 49 12 19 43 4 5 46 Tarkasteltuamme huolellisesti keräämäämme graafirakenteista dataa, havaitsemme, että se tulee yleensä eri lähteistä, kuten sosiaalisista verkoista, viittausverkoista ja viestintäverkoista, joissa on valtava määrä sekä sisältö- että linkkitietoa. Esimerkiksi monien sosiaalisten alustojen, kuten Twitterin, Flickrin ja Facebookin, tiedot sisältävät käyttäjäominaisuuksia, kuten henkilökohtaisia perustietoja, tekstejä, kuvia, IP-osoitteita ja heidän suhteitaan, kuten saman tuotteen ostaminen, ystävyyssuhteet. Nämä rikkaat sisältötiedot riittävät tukemaan myöhempiä louhintatehtäviä ilman lisäohjausta: jos kaksi entiteettiä osoittaa äärimmäistä samankaltaisuutta ominaisuuksissa, niiden välillä on suuri todennäköisyys linkille (linkkien ennustaminen), ja ne kuuluvat todennäköisesti samaan luokkaan (luokittelu); jos kaksi entiteettiä yhdistää saman entiteetin, niillä on luultavasti samankaltaisia ominaisuuksia (suositus). Tässä mielessä mahdollisimman suuren tietomäärän säilyttäminen ja poimiminen tietoverkoista upotusavaruuteen helpottaa korkealaatuisten esitysten oppimista, jotka osoittavat toivottua suorituskykyä louhintatehtävissä ilman minkäänlaista ohjausta. Valvomaton graafiesitysten oppiminen on monissa tapauksissa suotuisampi valinta, koska se on vapaa merkinnöistä, erityisesti kun aiomme hyödyntää suuria määriä merkitsemättömiä tietoja. Perimään täysin graafien rikas tieto, tässä paperissa suoritamme graafien upotuksen keskinäisen informaation (MI) maksimoinnin perusteella, inspiroituneena Deep Info-Max -menetelmän [ ] empiirisestä menestyksestä, joka toimii kuvilla. Hyödyllisten esitysten löytämiseksi Deep InfoMax kouluttaa enkooderin maksimoimaan MI:n sen syötteiden (eli kuvien) ja ulostulojen (eli piilevien vektoreiden) välillä. Kun otetaan huomioon Deep InfoMax graafidomeenissa, ensimmäinen este, joka meidän on ylitettävä, on se, miten määritellään MI graafien ja piilevien vektoreiden välillä, kun taas graafien topologia on monimutkaisempi kuin kuvien (katso kuva Yksi haasteista on varmistaa, että MI-funktio jokaisen solmun piilevän esityksen ja sen naapuruston syöteominaisuuksien välillä noudattaa symmetristä ominaisuutta, tai vastaavasti, on invariantti naapurustojen permutaatioille. Yhtenä äskettäisenä MI:tä tarkastelevana työnä Deep Graph Infomax (DGI) [ ] upottaa ensin syötegraafin ja vastaavan korruptoituneen graafin, tiivistää sitten syötegraafin vektoriksi lukutoiminnon avulla, ja lopuksi maksimoi MI:n tämän tiivistysvektorin ja piilevien esitysten välillä erottamalla syötegraafin (positiivinen näyte) korruptoituneesta graafista (negatiivinen näyte). Kuva antaa helposti ymmärrettävän yleiskatsauksen DGI:stä. Tällaisen MI:n maksimoinnin todetaan olevan ekvivalenttia syöte solmuominaisuuksien ja piilevien vektoreiden välisen MI:n maksimoinnille, mutta tämä ekvivalenssi pätee useiden ennalta asetettujen ehtojen vallitessa, esimerkiksi lukutoiminnon on oltava injektiivinen, mikä näyttää olevan liian rajoittunutta todellisissa tapauksissa. Vaikka voisimme taata injektiivisen lukutoiminnon olemassaolon tietyllä suunnittelulla, esimerkiksi DeepSetsissä [ ] käytetyn, lukutoiminnon injektiivisyys riippuu myös siitä, miten sen parametrit koulutetaan. Toisin sanoen, alun perin injektiivinen funktio voi muuttua ei-injektiiviseksi, jos sitä koulutetaan ilman ulkoista ohjausta. Ja jos lukutoiminto ei ole injektiivinen, syötegraafin tieto, joka sisältyy tiivistysvektoriin, vähenee graafin koon kasvaessa. Lisäksi DGI pysyy karkean graafi-/patch-tason MI-maksimoinnin tasolla. Siksi DGI:ssä ei ole takeita siitä, että enkooderi voi tislata riittävästi tietoa syötetiedoista, koska se ei koskaan korreloi huolellisesti piileviä esityksiä alkuperäisten syötteidensä kanssa. 20 1). 41 1 47 Tässä paperissa esitämme suoraviivaisemman tavan tarkastella MI:tä graafirakenteiden suhteen ilman lukutoimintoa ja korruptiotoimintoa. Johdamme MI:n suoraan vertaamalla enkooderin syötettä (eli syöte naapurustosta koostuvaa aligraafia) ja ulostuloa (eli jokaisen solmun piilevää esitystä). Ja mielenkiintoista kyllä, teoreettiset johtopäätöksemme osoittavat, että suoraan muotoiltu MI voidaan hajottaa painotetuksi summaksi paikallisista MI:istä kunkin naapuruston ominaisuuden ja piilevän vektorin välillä. Tällä tavalla olemme hajottaneet syöteominaisuudet ja tehneet MI-laskennasta helpommin käsiteltävän. Lisäksi tämä MI:n muoto voi helposti täyttää symmetrisen ominaisuuden, jos säädämme painojen arvoja. Siirrämme lisätietoja kohtaan § Koska yllä oleva MI mitataan pääasiassa solmuominaisuuksien tasolla, kutsumme sitä ominaisuuskeskinäiseksi informaatioksi (FMI). 3.1. Kaksi jäljellä olevaa kysymystä FMI:hin liittyen: yhdistävät painot ovat edelleen tuntemattomia ja se ei ota huomioon topologiaa (eli reunusominaisuuksia). Näiden kahden kysymyksen ratkaisemiseksi määrittelemme graafisen keskinäisen informaation (GMI) mittauksen FMI:n perusteella. Erityisesti GMI soveltaa intuitiivista arvonantoa asettamalla FMI:n painot yhtä suuriksi kuin kunkin naapurin etäisyys kohdesolmuun esitystilassa. Säilyttääksemme topologiatiedot, GMI korreloi nämä painot edelleen syötteen reunusominaisuuksien kanssa ylimääräisen keskinäisen informaation termin kautta. Tuloksena oleva GMI on topologisesti invariantti ja myös laskettavissa keskinäisen informaation neuroestimaatiolla (MINE) [ ]. Työmme pääkontribuutiot ovat seuraavat: 1. 2. 2 • : Yleistämme perinteisen MI-estimation graafidomeeniin ja ehdotamme vastaavasti uutta graafisen keskinäisen informaation (GMI) konseptia. GMI on vapaa Konseptit lukutoimintoon liittyvästä mahdollisesta riskistä, koska se tarkastelee MI:tä syötegraafien ja korkean tason upotusten välillä suoraviivaisella tavalla. • : Teoreettisen analyysimme avulla annamme helposti käsiteltävän ja laskettavan GMI-muodon, joka hajottaa Algoritmit koko GMI:n painotetuksi summaksi paikallisista MI:istä. MINE-menetelmän avulla GMI-maksimointi voidaan helposti saavuttaa solmutasolla. • : Varmistamme GMI:n tehokkuuden useissa suosituissa solmuluokittelu- ja linkkien ennustamistehtävissä, mukaan lukien sekä transduktiiviset että induktiiviset tehtävät. Kokeet osoittavat, että menetelmämme tuottaa lupaavaa suorituskykyä erilaisilla vertailuarvoilla, ja se ylittää joskus jopa ohjatut vastineet. Kokeelliset löydökset 2 LIITTYVÄ TYÖ Työmme fokuksen mukaisesti tarkastelemme lyhyesti aikaisempia töitä kahdella seuraavalla alueella: keskinäisen informaation estimointi ja neuroverkot esitysten oppimiseen graafien yli. 1. 2. . Koska InfoMax-periaate [ ] kannattaa MI:n maksimointia neuroverkkojen syötteiden ja ulostulojen välillä, monet menetelmät, kuten ICA-algoritmit [ , ], yrittävät hyödyntää MI:n ideaa valvomattomassa ominaisuuksien oppimisessa. Silti näitä menetelmiä ei voida helposti yleistää syväoppimisverkoille, koska MI:n laskeminen korkean ulottuvuuden jatkuvien muuttujien välillä on vaikeaa. Onneksi Mutual Information Neural Estimation (MINE) [ ] tekee MI:n estimoinnista syväoppimisverkoissa mahdollista kouluttamalla tilastoverkkoa luokittelijana erottamaan näytteet, jotka tulevat yhteisestä jakaumasta ja marginaalien tulosta kahdesta satunnaismuuttujasta. Erityisesti MINE käyttää MI:n tarkkaa KL-pohjaista muotoilua, kun taas ei-KL-vaihtoehto, Jensen-Shannonin divergenssi (JSD) [ ], voidaan käyttää ilman huolta MI:n tarkasta arvosta. Keskinäisen informaation estimointi 3 1 21 2 30 . Graafineuraaliverkkojen (GNN) nopean kehityksen myötä on viime vuosina ehdotettu suuri määrä GNN-pohjaisia graafiesitysten oppimisalgoritmeja, jotka osoittavat vahvempaa suorituskykyä kuin perinteiset satunnaisvaellus- ja faktorointipohjaiset upotusmenetelmät [ , , , , ]. Tyypillisesti nämä menetelmät voidaan jakaa ohjattuihin ja valvomattomiin kategorioihin. Niistä on olemassa laaja kirjallisuus ohjatusta esitysten oppimisesta graafien yli [ , , , , ]. Huolimatta niiden verkkoarkkitehtuurin vaihteluista, ne saavuttavat empiiristä menestystä merkintöjen avulla, jotka eivät usein ole saatavilla realistisissa skenaarioissa. Tässä tapauksessa valvomattomat graafien oppimismenetelmät [ , , ] ovat laajemmalti sovellettavissa. Tunnettu menetelmä on GraphSAGE [ ], induktiivinen kehys GNN:ien kouluttamiseksi satunnaisvaellus-pohjaisella tavoitteella sen valvomattomassa asetuksessa. Ja äskettäin DGI [ ] soveltaa MI-maksimoinnin ideaa graafidomeeniin ja saavuttaa vahvan suorituskyvyn valvomattomassa mallissa. DGI kuitenkin toteuttaa karkean maksimoinnin (eli MI:n maksimoinnin graafi-/patch-tasolla), mikä tekee siitä vaikean säilyttää hienovaraista tietoa syötegraafista. Lisäksi DGI:ssä käytettyyn lukutoimintoon asetettu ehto näyttää olevan liian rajoittunut todellisissa tapauksissa. Sitä vastoin keskitymme lukutoiminnon rajoituksen poistamiseen ja graafisen keskinäisen informaation maksimoinnin saavuttamiseen solmutasolla maksimoimalla suoraan enkooderin syötteiden ja ulostulojen välisen MI:n. Menetelmämme johtamat esitykset ovat hienostuneempia syötegraafin tiedon säilyttämisessä, mikä varmistaa sen potentiaalin myöhempiä graafinlouhintatehtäviä varten, esim. solmuluokittelu, linkkien ennustaminen ja suositukset. Neuroverkot graafien esitysten oppimiseen 6 15 33 34 39 7 9 25 40 48 11 16 41 16 41 3 GRAAFINEN KESKINÄINEN INFORMAATIO: MÄÄRITTELY JA MAKsimointI Ennen kuin jatkamme, esitämme ensin tässä paperissa käytetyt alustavat käsitteet. Olkoon G = (V, E) graafi, jossa on solmua ∈ V ja reunat = ( , ) ∈ E. Solmuominaisuudet, joilla on oletettu empiirinen jakauma P, annetaan muodossa ∈ N vi eij vi vj X R × = { 1, · · · , }, missä ∈ R kuvaa solmun ominaisuutta. Adjeksenssimatriisi ∈ R × kuvaa reunayhteyksiä, missä , joka liittyy reunaan , voi olla reaaliluku tai moniulotteinen vektori1. N D x x N xi D vi A N N Aij eij Graafiesitysten oppimisen tavoitteena on oppia enkooderi : R × × R × → R × ′, siten, että piilevät vektorit = { 1, · · · , } = ( , ) osoittavat korkean tason esityksiä kaikille solmuille. Koodausprosessia voidaan kirjoittaa uudelleen solmukohtaisena. f N D N N N D H h hN f X A Tämän osoittamiseksi määrittelemme ja solmulle vastaavasti sen naapureiden ominaisuuksina ja vastaavana adjeksenssimatriisina Xi Ai i ehdollisena naapureiden suhteen. Erityisesti sisältää kaikki -hopin naapurit , kun ≤ , jos enkooderi on -kerroksinen GNN, ja se sisältää itse solmun , jos lisäämme itsesilmukoita adjeksenssimatriisiin. Tässä kutsumme :n ja :n laajentamaa aligraafia tukigraafiksi solmulle , jota merkitään G . Tukigraafin määritelmän avulla kunkin solmun koodaus muuttuu muotoon = (G ) = ( , ). Xi k vi k l f l i Xi Ai i i hi f i f Xi Ai Deep InfoMaxissa [ ], enkooderin koulutustavoitteena on maksimoida MI enkooderin syötteiden ja ulostulojen välillä. MI arvioidaan käyttämällä tilastoverkkoa erottimena luokittelemaan näytteitä, jotka tulevat yhteisestä jakaumasta, ja näytteitä, jotka on otettu marginaalien tulosta. Luonnollisesti, kun sovelletaan Deep InfoMaxin ideaa graafeihin, meidän tulisi maksimoida MI esityksen ja tukigraafin G välillä jokaiselle solmulle. Merkitsemme tällaista graafista MI:tä muodossa ( ; G ). Kuitenkin I (hi ; Gi ) määrittely ei ole suoraviivaista. Vaikeudet ovat: Vaikeudet graafisen keskinäisen informaation määrittelyssä. 20 hi i I hi i • Graafisen MI:n tulee olla invariantti solmun indeksin suhteen. Toisin sanoen, meillä tulee olla ( ; G ) = ( ; G′ ), jos G ja G′ ovat isomorfisia keskenään. I hi i I hi i i i • Jos käytämme MINE-menetelmää MI-laskentaan, MINE:n erotin hyväksyy vain kiinteän kokoisia syötteitä. Tämä on kuitenkin mahdotonta G :lle, koska eri G :t sisältävät yleensä eri määrän solmuja ja ovat siten erikokoisia. i i Graafisen keskinäisen informaation määrittelyn ongelman kiertämiseksi tämä osio alkaa esittelemällä ominaisuuskeskinäisen informaation (FMI) käsitteen, joka perustuu vain solmuominaisuuksiin. FMI:n hajautuksen inspiraation pohjalta määrittelemme sitten graafisen keskinäisen informaation (GMI), joka ottaa huomioon sekä solmuominaisuudet että 3.1 OMINAISUUSKESKINÄINEN INFORMAATIO Merkitsemme solmuominaisuuksien empiirisen todennäköisyysjakauman ( ), :n todennäköisyyden ( ) ja yhteisen jakauman ( , ). Informaatioteorian mukaan MI :n ja :n välillä määritellään Xi p Xi hi p hi p hi Xi hi Xi Mielenkiintoista kyllä, meillä on seuraava keskinäisen informaation hajotusteoreema ( ; ) laskemiseksi. I hi Xi Teoreema 1 (Keskinäisen informaation hajautus). ( | ) ( ; ) Jos ehdollinen todennäköisyys p hi Xi on multiplikatiivinen (katso multiplikatiivisuuden määritelmä kohdassa [ ]), globaali keskinäinen informaatio I 36 hi Xi määriteltynä kaavassa (1) voidaan hajottaa painotetuksi summaksi paikallisista MI:istä, nimittäin, ≤ ≤ 1 missä xj on solmun i j-s naapuri, in on kaikki Xien alkioiden lukumäärä, ja paino wij täyttää ehdon 1 wij jokaiselle j:lle. Tämän teoreeman todistamiseksi esittelemme ensin kaksi lemmaa ja yhden määritelmän. Lemma 1. Millä tahansa satunnaismuuttujilla X, Y ja Z pätee Teoreeman hajautuksen avulla voimme laskea kaavan oikean puolen käyttämällä MINE:tä, koska erottimen syötteistä tulee nyt pareja ( , ), joiden koko pysyy aina samana (eli ′× ). Lisäksi voimme säätää painoja heijastamaan syötegraafien isomorfisia transformaatioita. Esimerkiksi, jos sisältää vain solmun yhden hopin naapureita, kaikkien painojen asettaminen identtisiksi johtaa samaan MI:iin eri järjestyksessä oleville syötesolmuille. 1 (2) hi xj D D Xi i Hajautuksen hyödyistä huolimatta painojen tarkkojen arvojen luonnehtiminen on vaikeaa, koska ne liittyvät ( ; ) arvoihin ja niiden taustalla oleviin todennäköisyysjakaumiin. I hi xj Triviaalinen tapa on asettaa kaikki painot , jolloin kaavan oikean puolen maksimointi vastaa ( ; ) alarajan maksimointia, jolla todellinen FMI maksimoituu jossain määrin. Tämän menetelmän lisäksi tarjoamme lisäksi parannetun ratkaisun tarkastelemalla painoja koulutettavina huomioina, mikä on seuraavan osion aihe. 1 (2) I hi Xi Inspiroituneena Teoreeman hajautuksesta, pyrimme rakentamaan koulutettavia painoja graafien toisesta näkökulmasta (eli 3.2 Topologiaan tietoinen keskinäinen informaatio 1 topologisesta näkökulmasta), jotta -arvot voisivat olla joustavampia ja vangita graafien olennaisia ominaisuuksia. Lopulta johdamme graafisen keskinäisen informaation (GMI) määritelmän. wij Määritelmä 2 (Graafinen keskinäinen informaatio). G = ( , ) MI piilevän vektorin h ja sen tukigraafin X A välillä määritellään muodossa missä sekä xj että in määritelmät ovat samat kuin Teoreemassa 1, aij on reunapaino/ominaisuus adjeksenssimatriisissa A, ja σ(·) on sigmoidifunktio. Intuitiivisesti, kaavan (10) ensimmäisen termin paino wij mittaa kontribuution paikallisesta MI:stä globaaliin. Toteutamme I (hi ; xj ) kontribuution esitysten hi ja hj välisellä samankaltaisuudella (eli wij = σ (hThj )). Samaan aikaan termi I (wij ; aij ) maksimoi MI:n wij:n ja syötegraafin reunapainon/ominaisuuden (eli aij ) välillä, jotta wij noudattaisi topologisia suhteita. Tässä mielessä kontribuution aste olisi yhdenmukainen topologisen rakenteen etäisyyden kanssa, minkä uskotaan yleisesti olevan totta, että wij voi olla suurempi, jos solmu j on "lähempänä" solmua i ja pienempi muuten. Tämä strategia kompensoi FMI:n puutteen, joka keskittyy vain solmuominaisuuksiin, ja saa paikalliset MI:t vaikuttamaan globaaliin adaptiivisesti. Saadaksemme paremman käsityksen huomiomekanismista tässä strategiassa, voit viitata huomiopohjaiseen GCN:ään. Huomaa, että kaavan (10) määritelmä soveltuu yleisiin tapauksiin. Tietyissä erityistapauksissa voimme muokata kaavaa (10) tehokkuuden vuoksi. Esimerkiksi, kun käsitellään painottamattomia graafeja (eli reunusarvo on 1, jos yhdistetty, ja 0 muuten), voisimme korvata toisen MI-termin I (wij ; aij ) negatiivisella ristientropiahäviöllä. Ristientropian minimoiminen edistää myös MI-maksimointia, ja se tuottaa tehokkaamman laskennan. Siirrämme lisätietoja seuraavaan osioon. Kaiken kaikkiaan kaavan (10) määritelmällä on useita etuja. Ensinnäkin, tämän tyyppinen MI on invariantti syötegraafien isomorfisille transformaatioille. Toiseksi, se on laskennallisesti mahdollista, koska oikean puolen jokainen komponentti voidaan arvioida MINE:llä. Vielä tärkeämpää on, että GMI on DGI:tä tehokkaampi alkuperäisen syötetiedon vangitsemisessa, koska se korreloi eksplisiittisesti piilevien vektoreiden ja sekä solmujen että reunusten syöteominaisuuksien välillä hienojakoisella solmutasolla. 3.3 GMI:N MAKsimointi Nyt maksimoimme kaavan oikean puolen MINE:n avulla. Huomaa, että MINE arvioi MI:n alarajan KL-divergenssin Donsker-Varadhan (DV) [ ] muotoilulla yhteisen jakauman ja marginaalien tulon välillä. Koska keskitymme enemmän MI:n maksimointiin sen tarkan arvon saavuttamisen sijaan, muut ei-KL-vaihtoehdot, kuten Jensen-Shannon MI estimator (JSD) [ ] ja Noise-Contrastive estimator (infoNCE) [ ], voidaan käyttää sen korvaamiseen. Perustuen kokeellisiin löydöksiin ja analyysiin [ ], turvaudumme JSD-estimaattoriin tässä paperissa tehokkuuden ja suorituskyvyn vuoksi, koska infoNCE-estimaattori on herkkä negatiiviselle näytteenotto strategialle (negatiivisten näytteiden lukumäärä), joten se voi muodostua pullonkaulaksi suurille dataseteille kiinteällä käytettävissä olevalla muistilla. Sitä vastoin JSD-estimaattorin insensitiivisyys negatiivisille näytteenotto strategioille ja sen kunnioitettava suorituskyky monissa tehtävissä tekevät siitä sopivamman tehtäväämme. Erityisesti laskemme ( ; ) kaavan ensimmäisessä termissä käyttämällä (10) 10 30 31 20 I hi xj (10) missä D : × ′→ R on neuroverkolla konstruoitu erotin parametrilla . on negatiivinen näyte P = P:stä, ja ( ) = (1 + ) kuvaa soft-plus-funktiota. w D D w x j sp x loд ex Kuten § mainittiin, maksimoimme ( ; ) laskemalla sen ristientropian käyttämällä JSD-estimaattoria, koska kokeissa käsittelemämme graafit ovat painottamattomia. Muodollisesti laskemme 3.2:ssä I wij aij Maksimoimalla I (hi ; Gi ) kaavan ja kaavan summan yli kaikkien piilevien vektoreiden H , saavutamme täydellisen tavoitefunktion GMI-optimointiin. Lisäksi voimme lisätä kompromissiparametreja tasapainottaaksemme kaavaa (11) ja (12) joustavuuden lisäämiseksi. (11) (12) 4 KOKEET Tässä osiossa arvioimme empiirisesti GMI:n suorituskykyä kahdessa yleisessä tehtävässä: solmuluokittelu (transduktiivinen ja induktiivinen) ja linkkien ennustaminen. Lisäksi suhteellisen reilu vertailu GMI:n ja kahden muun valvomattoman algoritmin (EP-B ja DGI) välillä esittelee sen tehokkuutta entisestään. Tarjoamme myös t-SNE-kuvien visualisoinnin ja analysoimme mallin syvyyden vaikutusta. 4.1 Datasettit Arvioidaksemme menetelmämme laatua kussakin tehtävässä, käytämme 4 tai 5 yleisesti käytettyä vertailudatasettia aiemmista töistä [ , , Tarkat tilastot annetaan Taulukossa 16 25 41]. 1. Luokittelutehtävässä Cora, Citeseer ja PubMed [ ]2 ovat viittausverkostoja, joissa solmut vastaavat dokumentteja ja reunat edustavat viittauksia. Jokainen dokumentti on yhdistetty sanapussiesityksen vektoriin ja kuuluu yhteen ennalta määritellyistä luokista. Noudattaen transduktiivista asetusta kohdassa [ , ], koulutus suoritetaan kaikilla solmuilla, ja arviointiin käytetään 1000 testisolmua. Reddit3 on suuri sosiaalinen verkko, joka koostuu lukuisista yhteenliitetyistä Reddit-postauksista, jotka on luotu syyskuussa 2014 [ ]. Postaukset käsitellään solmuina ja reunat tarkoittavat samaa käyttäjää, joka kommentoi. 38 25 41 16 ![ Taulukko 1: Kokeissa käytettyjen datasettien tilastot. ](https://cdn.hackernoon.com/images/InxBRjRIs6M1kdhuWcyNHiiUrxm1-eph3eec.jpeg) Luokkamerkintä on yhteisö, ja tavoitteemme on ennustaa, mihin yhteisöön eri postaukset kuuluvat. PPI3 on proteiini-proteiini-interaktiodatasetti, joka sisältää useita graafeja, jotka liittyvät eri ihmiskudoksiin [ ]. Paikalliset geenijoukot, motiivigeenijoukot ja immunologiset allekirjoitukset katsotaan solmuominaisuuksiksi, ja jokaisella solmulla on yhteensä 121 merkintää, jotka on annettu geeniontologian joukkojen perusteella. Tavoitteenamme on luokitella proteiinien toimintoja, jotka voivat kuulua useisiin genreihin eri PPI-graafeissa. Noudattaen induktiivista asetusta kohdassa [ ], Redditissä syötämme malliin ensimmäisten 20 päivän aikana tehdyt postaukset koulutusta varten, kun taas loput käytetään testaukseen (30 % käytetään validoinnissa); PPI:ssä on 20 graafia koulutusta varten, 2 validointia ja 2 testausta varten. On korostettava, että Redditissä ja PPI:ssä testaus suoritetaan tuntemattomilla (kouluttamattomilla) solmuilla ja graafeilla, kun taas kolmea ensimmäistä datasettiä käytetään transduktiiviseen oppimiseen. 52 16 Linkkien ennustamistehtävässä BlogCatalog4 on sosiaalinen blogialusta, jossa bloggaajat seuraavat toisiaan ja rekisteröivät bloginsa ennalta määriteltyihin 6 luokkaan. Blogien tunnisteita käytetään solmuominaisuuksina. Flickr4 on kuvajakoalusta, jossa käyttäjät ovat vuorovaikutuksessa muiden kanssa ja muodostavat sosiaalisen verkoston. Käyttäjät lataavat valokuvia ennalta määritellyillä 9 luokalla ja valitsevat liitetyt tunnisteet heijastamaan heidän kiinnostuksen kohteitaan, jotka tarjoavat attribuuttitietoa. Coren ja PPI:n kuvaus jätetään pois tiiviyden vuoksi. Noudattaen kokeellisia asetuksia ja arviointimittoja kohdassa, annetaan graafi, josta tietyt reunat on poistettu, ja pyrimme ennustamaan näitä puuttuvia linkkejä. Coran, BlogCatalogin ja Flickrin tapauksessa poistamme satunnaisesti 20 %, 50 % ja 70 % reunoista varmistaen samalla, että reunapoiston jälkeen saatu verkko on yhtenäinen ja käytämme vaurioitunutta verkkoa koulutukseen. PPI:n osalta käsittelemme suoraan osaa koulutuksen aikana näkemättömistä reunoista ennustettavina kohteina manuaalisen reunapoiston sijaan. 4.2 Kokeelliset Asetukset Käytämme standardia graafikonvoluutioverkkoa (GCN) seuraavalla kerroskohtaisella propagointisäännöllä enkooderina sekä luokittelu- että linkkien ennustamistehtävissä: Enkooderin suunnittelu. Missä Aˆ = D -1/2AD - 1/2A = A + In, Dii = Aij, H (1) ja H (I + 1) ovat l-kerroksen syöte- ja ulostulomatriisit, ( ) on kerroskohtainen koulutettava painomatriisi. Tässä epälineaarinen muunnos , jota käytämme, on PReLU-funktio (parametrisoidtu ReLU) [ ]. On tunnustettava, että solmulle , sen tukigraafin Gi naapurusto sisältää itse solmun , koska itsesilmukat lisätään A¯ :n kautta. W l σ 17 i Xi i Tarkemmin sanottuna Citeseerin ja PubMedin enkooderissa käytimme yhden kerroksen GCN:ää, jonka ulostulodimensio on ′= 512. Corassa, Redditissä, BlogCatalogissa, Flickrissä ja PPI:ssä käytimme kahden kerroksen GCN:ää enkooderina. Tässä meillä on piilodimensiot ′= 512 jokaisessa GCN-kerroksessa. Huomaa, että samankaltaisen GCN-enkooderin käyttäminen sekä transduktiivisessa että induktiivisessa luokittelutehtävässä tekee ehdottamastamme menetelmästä helpommin seurattavan ja skaalautuvan suuriin verkkoihin kuin DGI, koska DGI:n on suunniteltava vaihtelevia enkoodereita sopeutuakseen eri oppimistehtäviin, erityisesti induktiivisten tehtävien enkooderit ovat liian monimutkaisia ja yksityiskohtaisia, mikä ei ole ystävällistä käytännön sovelluksille. D D Kaavan erotin pisteyttää syöte-ulostulo ominaisuusparit yksinkertaisella bilineaarisella funktiolla, joka on samanlainen kuin erottimessa, jota käytetään kohdassa Erottimen suunnittelu. (11) : missä Θ edustaa koulutettavaa pisteytysmatriisia ja käytetty aktivaatiofunktio on sigmoid, jonka tarkoituksena on muuntaa pisteet todennäköisyyksiksi ( , ) positiivisena esimerkkinä. σ h x Todellisuudessa kaavan ensimmäisen termin painolle on kaksi tapaa saada sen arvo kokeissa. Ensimmäinen on pitää = ( T ), mikä saa paikalliset MI:t vaikuttamaan globaaliin adaptiivisesti, ja kutsumme tätä varianttia GMI-adaptiveksi. Toteutustiedot. (10) wij wij σ h hj Toinen on antaa = , ts. välin vasen päätepiste, johon kuuluu (viittaa Teoreemaan mikä tarkoittaa, että jokaisen paikallisen MI:n kontribuutio on yhtä suuri, ja kutsumme tätä varianttia GMI-meaniksi. Tässä sekä GMI-mean että GMI-adaptive sisällytetään vertailun piiriin perustason algoritmien kanssa. wij 1/in wi j 1), Kaikki kokeet toteutettiin PyTorchissa Glorot-initialisoinnilla ja suoritettiin yhdellä Tesla P40 GPU:lla. Esikäsittelyssä suoritamme rivin normalisoinnin Corassa, Citeseerissa, PubMedissä, BlogCatalogissa ja Flickrissä mukaisesti ja sovellamme kohdassa esitettyä käsittelystrategiaa Redditissä ja PPI:ssä. Koulutuksen aikana käytämme Adam-optimoijaa 0,001 alkuperäisellä koulutusnopeudella kaikissa seitsemässä datasettissä. Ehdotuksen mukaan käytämme varhaisen lopetuksen strategiaa, jonka ikkunakoko on 20 Corassa, Citeseerissa ja PubMedissä, kun taas mallia koulutetaan kiinteän määrän epookkeja induktiivisilla dataseteillä (20 Redditissä, 50 PPI:ssä). Negatiivisten näytteiden lukumäärä on asetettu 5:een. Redditin ja PPI:n suuren koon vuoksi meidän on käytettävä kohdassa [ ] esiteltyä osanäytteenotto-taitoa saadaksemme ne mahtumaan GPU-muistiin. Yksityiskohtaisesti ensin valitaan 256 solmun minipakkaus, ja sitten jokaiselle valitulle solmulle otetaan satunnaisesti 8 ja 5 naapuria ensimmäisessä ja toisessa tasossa. Käytämme yhden hopin naapurustoa tukigraafin rakentamiseen kokeissa ja hyödynnämme (0) (eli pakattua syöteominaisuutta) FMI:n laskemiseen, koska alkuperäisen syöteominaisuuden käyttäminen aiheuttaa GPU-muistin ylivuodon. Kompromissiparametreja säädetään välillä kaavan ja kaavan tasapainottamiseksi. Erän normalisointistrategiaa käytetään mallimme kouluttamiseen Redditissä ja PPI:ssä. 16 XW X (11) (12) Luokittelutehtävässä annamme oppineet upotukset koulutusjoukon yli logistiseen regressioluokittelijaan ja esitämme tulokset testisolmuilla [ , ]. Erityisesti transduktiivisessa oppimisessa käytämme keskimääräistä luokittelutarkkuutta 50 ajon jälkeen suorituskyvyn arvioimiseksi, kun taas induktiivisessa oppimisessa käytetään mikroverkkoon keskiarvoistettua F1-pistettä 50 ajon jälkeen. PPI:ssä ehdotuksen [ ] mukaisesti standardisoimme oppineet upotukset ennen niiden syöttämistä logistiseen regressioluokittelijaan. Linkkien ennustamistehtävässä käyttämämme kriteeri on AUC, joka on ROC-käyrän alle jäävä pinta-ala. AUC:n laskentaan sisältyvät negatiiviset näytteet luodaan valitsemalla satunnaisesti yhtä suuri määrä solmuja ilman yhteyksiä alkuperäisessä graafissa. Mitä lähempänä AUC-pistemäärä on 1:tä, sitä parempi algoritmin suorituskyky on. Samoin ilmoitamme AUC-pistemäärän keskiarvon 10 ajon jälkeen. Arviointimitat. 16 25 41 4.3 Luokittelu Taulukko raportoi menetelmämme ja muiden perustason algoritmien keskimääräisen luokittelutarkkuuden transduktiivisissa tehtävissä. Tässä EP-B [ ], DGI [ ], Planetoid-T [ ], GAT [ ] sekä GWNN [ ] tulokset on otettu niiden alkuperäisistä papereista, ja DeepWalk [ ], LP (Label Propagation) [ ] ja GCN [ ] tulokset on kopioitu Kipf & Wellingiltä [ ]. Raakojen ominaisuuksien osalta syötämme ne logistiseen regressioluokittelijaan koulutusta varten ja esitämme tulokset testausominaisuuksilla5. Vaikka tarjoamme sekä ohjattujen että valvomattomien menetelmien kokeellisia tuloksia, tässä paperissa keskitymme enemmän verrattaessa valvomattomiin menetelmiin, jotka ovat yhdenmukaisia asetuksemme kanssa. Transduktiivinen oppiminen. 2 11 41 45 40 44 33 51 25 25 Kuten voidaan havaita, ehdottamamme GMI-mean ja GMI-adaptive saavuttavat parhaan luokittelutarkkuuden kaikissa kolmessa datasettissä verrattuna muihin valvomattomiin menetelmiin. Pidämme tätä vahvaa suorituskykyä hyödyllisenä pyrkimyksessä maksimoida suoraan graafinen MI enkooderin E syöte- ja ulostuloparien välillä hienojakoisella solmutasolla. Siksi koodattu esitys säilyttää mahdollisimman paljon G:n solmuominaisuuksien ja topologian tietoa, mikä edistää luokittelua. Sitä vastoin EP-B jättää huomiotta syötetietojen ja opittujen esitysten välisen piilevän tiedon, ja DGI pysyy graafi-/patch-tason MI-maksimoinnin tasolla, mikä rajoittaa sen kykyä säilyttää ja poimia alkuperäistä syötetietoa upotusavaruuteen. Siksi hieman heikompi suorituskyky luokittelutehtävissä. Lisäksi, ilman merkkien ohjausta, menetelmämme osoittaa vertailukelpoisia tuloksia joidenkin ohjattujen mallien, kuten GCN:n ja GAT:n, kanssa, ja jopa parempia tuloksia kuin ne Citeseerissa ja PubMedissä. Uskomme, että GMI-maksimoinnin kautta opitut esitykset syötteiden ja ulostulojen välillä perivät graafin G rikkaan tiedon, joka riittää luokitteluun. Vielä merkittävämpää on, että monet käytettävissä olevat merkinnät perustuvat myös G:n tietoihin. Siksi mahdollisimman suuren tiedon säilyttäminen syötteestä voi jossain määrin kompensoida merkin tarjoamaa tietoa, mikä ylläpitää GMI:n suorituskykyä myöhemmissä graafinlouhintatehtävissä. Voidaan väittää, että alkuperäisistä syötteistä oppiminen ilman merkintöjä lupaava korkealaatuisempia esityksiä kuin ohjattu malli, koska koulutusmerkkien äärimmäinen harvuus voi kärsiä ylisovittumisen uhasta tai annettujen merkkien oikeellisuus ei ehkä ole luotettava. Taulukko tiivistää myös mikroverkkoon keskiarvoistetut F1-pisteet GMI:lle ja muille perustason algoritmeille Redditissä ja PPI:ssä. Lainamme DGI:n, GAT:n, FastGCN:n [ ] ja GaAN:n [ ] tulokset niiden alkuperäisistä papereista, kun taas muiden seitsemän verratun menetelmän tulokset on otettu Hamilton et al.:lta [ ] (tässä käytämme uudelleen valvomattoman GraphSAGE:n tuloksia vastaamaan asetustamme). Samoin vertailu valvomattomiin algoritmeihin on työmme painopiste. Induktiivinen oppiminen. 2 7 48 16 GMI-mean ja GMI-adaptive ylittävät menestyksekkäästi kaikki muut kilpailevat valvomattomat algoritmit Redditissä ja PPI:ssä, mikä todistaa GMI-maksimoinnin tehokkuuden induktiivisessa luokittelussa (yleistys tuntemattomiin solmuihin). Mielenkiintoista kyllä, menetelmämme tulos Redditissä on kilpailukykyinen joidenkin edistyneiden ohjattujen mallien kanssa, mutta tilanne PPI:ssä on aivan erilainen. Lisäanalyysin jälkeen huomaamme, että 42 % solmuista on nolla-ominaisuusarvoja PPI:ssä, mikä tarkoittaa, että ominaisuusmatriisi X on hyvin harva [ ]. Tässä tapauksessa pelkästään syötegraafiin G = ( , ) luottaminen rajoittaa valvomattomien lähestymistapojen, mukaan lukien DGI ja meidän menetelmämme, suorituskykyä, kun taas ohjattu oppiminen osoittaa paljon parempaa suorituskykyä lisämerkintöjen tuoman lisätiedon ansiosta. 16 X A Taulukon mukaan kaksi GMI:n varianttia (GMI-mean ja GMI-adaptive), jotka käyttävät erilaisia strategioita kunkin paikallisen MI:n kontribuution mittaamiseen (yksityiskohdat § saavuttavat kilpailukykyisiä tuloksia keskenään, mutta GMI-adaptive osoittaa hieman heikompaa suorituskykyä kuin GMI-mean. Lisäanalyysin perusteella oletamme, että tämä voi johtua adaptiivisen oppimisen luonteesta johtuvista koulutusvaikeuksista. Ehkä GMI-adaptiven suorituskykyä voitaisiin parantaa edistyneen koulutusstrategian avulla. Tässä mielessä GMI-mean on käytännöllisempi ja toteutettavissa, joten sitä voidaan pitää edustavana käytännössä. Arviointi GMI:n kahdella variantilla. 2 4.2), 4.4 TAVOITEFUNKTION TEHOKKUUS Selventääksemme edelleen graafisen MI:n maksimoinnin tehokkuutta valvomattomassa graafiesitysten oppimisessa ja tarjotaksemme suhteellisen reilun vertailun DGI:n ja EP-B:n (kaksi valvomatonta algoritmia) kanssa, korvaamme tavoitefunktion niiden häviöfunktioilla, pitäen samalla muut kokeelliset asetukset muuttumattomina. Taulukko luettelee tulokset transduktiivisessa ja induktiivisessa asetuksessa. Kuten voidaan havaita, GMI (GMI-mean ja GMI-adaptive) saavuttaa vahvemman suorituskyvyn kaikissa viidessä datasetissä, mikä heijastaa DGI:n ja EP-B:n puutteita graafiesitysten oppimistehtävässä. Erityisesti EP-B-häviö asettaa rajoituksia vain jokaiselle solmulle ja sen naapureille ulostulotasolla (upotusavaruus), se jättää huomiotta enkooderin syöte- ja ulostuloparien välisen vuorovaikutuksen, mikä johtaa sen heikkoon kykyyn säilyttää G:n kelvollinen tieto. DGI:n osalta, vaikka se korreloi piilevien esitysten kanssa alkuperäisten syöteominaisuuksiensa kanssa implisiittisesti, se käsittelee MI:tä graafi-/patch-tasolla, mikä on jonkin verran karkeaa. 3 Mielenkiintoista kyllä, verrattuna DGI:hin, FMI (ilman topologia-tietoa) saa enemmän parannusta graafin koon kasvaessa. Tämän havainnon syyksi annamme sen, että lukutoiminnon suorituskyvyn heikkeneminen saa DGI:n menettämään tiettyä hyödyllistä tietoa solmuluokittelutehtävässä graafin koon kasvaessa, vaikka se osoittaa hyvää suorituskykyä pienissä graafeissa, kuten Corassa ja Citeseerissa. Kun syötegraafin topologia heijastuu, GMI ylittää kaikki muut häviötyypit kaikissa dataseteissä. Lisäksi huomataan, että GMI:n koko koulutusprosessi on samanlainen kuin generatiivisten mallien [ , ] erottimien koulutus, ja GMI osoittaa empiirisesti verrattavissa olevaa koulutusnopeutta EP-B:n ja DGI:n kanssa suurimmalla datasetillä Reddit, mikä osoittaa sen hyvän skaalautuvuuden. 14 30 4.5 Linkkien ennustaminen Edellä mainittujen kokeellisten tulosten perusteella havaitsemme, että DGI on vahva kilpailija GMI:lle valvomattomien algoritmien piirissä. Siksi tässä osiossa pyrimme edelleen tutkimaan DGI:n ja GMI:n suorituskykyä toisessa louhintatehtävässä – linkkien ennustamisessa. Tässä vertaamme FMI:tä ja GMI-meania DGI:hin. Taulukko raportoi niiden AUC-pisteet neljässä eri datasetissä. Eri reunojen poistoprosenteilla GMI ja FMI ylittävät huomattavasti DGI:n (paitsi FMI 70,0 % BlogCatalogissa), osoittaen, että graafisen MI:n mittaaminen syötegraafin ja ulostuloesitysten välillä hienojakoisella tavalla pystyy vangitsemaan syötteiden rikkaan tiedon ja tuottamaan hyvän yleistyskyvyn. DGI:n osalta, toisaalta, sen graafi-/patch-tason MI-maksimointi, joka on suhteellisen karkea, rajoittaa sen suorituskykyä näin hienojakoisessa linkkien ennustamistehtävässä; toisaalta korruptiotoiminnon sopimattomuus heikentää DGI:n kykyä oppia tarkkoja esityksiä puuttuvien linkkien ennustamiseksi. Muistakaa, että DGI:n erottimen negatiivinen näyte luodaan korruptoimalla alkuperäinen syötegraafi, ja hyvin suunniteltu korruptiotoiminto on välttämätön, mikä vaatii taitavia strategioita [ ]. Tässä tehtävässä käytämme edelleen ominaisuuksien sekoitustoimintoa, joka osoittaa parhaat tulokset luokittelutehtävässä negatiivisten näytteiden rakentamiseksi. Mutta siinä tapauksessa, että syötegraafi on epätäydellinen topologisten linkkien suhteen, tämän korruptoituneen graafin tarjoama ohjaus erottimessa negatiivisena merkintänä on epäluotettava syötegraafin epätarkkuuden vuoksi, johtaen heikkoon suorituskykyyn. Siksi tehtäväkohtaisen korruptiotoiminnon tarve on DGI:n heikkous. Sitä vastoin GMI on vapaa tästä ongelmasta poistamalla korruptiotoiminnon ja maksimoimalla suoraan enkooderin syötteiden ja ulostulojen välisen graafisen MI:n. Lisäksi voidaan havaita, että FMI on kilpailukykyinen GMI:n kanssa useimmissa tapauksissa, jopa Flickrissä FMI on parempi kuin GMI. Oletamme tämän johtuvan suorasta ja yksityiskohtaisesta solmutasoisesta ominaisuuskeskinäisestä informaation maksimoinnista saaduista hyödyistä. Perustuen homofiliaperiaatteeseen [ ] (eli verkoston entiteetit, joilla on samankaltaisia ominaisuuksia, todennäköisesti yhdistyvät), opittuihin upotuksiin säilytetty syöteominaisuusinformaaatio antaa FMI:lle hyvän kyvyn päätellä puuttuvia linkkejä. 4 41 29 4.6 Visualisointi Intuitiivista havainnollistusta varten Taulukko esittää t-SNE [ ] -kuvia Coran ja Citeseerin opituista upotuksista. Laadullisesti FMI:n ja DGI:n oppimien kuvien jakauma näyttää samankaltaiselta, ja GMI:n tuottamat upotukset muodostavat erottuvampia klustereita kuin raakapiirteet, FMI ja DGI. 5 28 Erityisesti Corassa klustereiden tiiviys ja erotettavuus ovat erittäin ilmeisiä, mikä edustaa seitsemää teemaluokkaa. Määrällisen analyysin osalta yritämme mitata klusterointilaatua laskemalla Silhouette Coefficient -