Új módja az AI képzésének graf adatokon felügyelet nélkül

Szerzők: Zhen Peng Wenbing Huang Minnan Luo Qinghua Zheng Yu Rong Tingyang Xu Junzhou Huang RÖVIDÍTÉS A különböző információs hálózatok, például a közösségi és kommunikációs hálózatok tartalmának gazdagsága példátlan potenciált kínál a kiváló minőségű, kifejező reprezentációk külső felügyelet nélküli elsajátítására. Ez a cikk azt vizsgálja, hogyan lehet a grafikon-szerkezetű adatokból származó bőséges információt felügyelet nélkül megőrizni és kinyerni az ágyazási térbe. Ennek érdekében egy új koncepciót, a grafikus kölcsönös információt (GMI) javasolunk a bemeneti grafikonok és a magas szintű rejtett reprezentációk közötti korreláció mérésére. A GMI általánosítja a hagyományos kölcsönös információ számítások vektor területről a grafikon tartományra való ötletét, ahol a csomópontok jellemzői és a topológiai szerkezet mindkét szempontjából elengedhetetlen a kölcsönös információ mérése. A GMI számos előnnyel rendelkezik: Először is, invariáns a bemeneti grafikonok izomorf transzformációjával szemben – ez egy elkerülhetetlen korlátozás sok meglévő grafikon reprezentációs tanulási algoritmusban; Emellett hatékonyan becsülhető és maximalizálható a jelenlegi kölcsönös információ becslési módszerekkel, mint például a MINE; Végül, elméleti elemzésünk megerősíti annak helyességét és racionalitását. A GMI segítségével kifejlesztünk egy felügyelet nélküli tanulási modellt, amelyet a grafikon neurális enkóder bemenete és kimenete közötti GMI maximalizálásával képzünk. A tranzuktív és induktív csomópontosztályozáson és linkjósláson végzett kiterjedt kísérletek azt mutatják, hogy módszerünk felülmúlja a legmodernebb felügyelet nélküli társaikat, sőt néha még a felügyelt módszereket is meghaladja. 1 BEVEZETÉS A különféle információs hálózatok megbízható kvantitatív elemzésének elérése érdekében a grafikon-szerkezetű adatok kiváló minőségű reprezentációs tanulása az egyik jelenleg lenyűgöző téma. Az e cél felé irányuló legújabb módszerek, amelyeket általában grafikon neurális hálózatoknak (GNN-ek) neveznek, figyelemre méltó előrelépéseket tettek számos tanulási feladatban, mint például a csomópontosztályozás [ , , ], linkjóslás [ , , ], grafikonillesztés [ , , ], molekuláris generálás [ , , ], hogy csak néhányat említsünk. Bár gyümölcsöző haladás van, a meglévő megközelítésekben a GNN-ek képzése általában valamilyen felügyeletet igényel. Kétségtelen, hogy a címkézési információk nehezen szerezhetők be – manuális annotálás vagy engedély vásárlása –, és még lehetetlen is elérni az adatvédelmi politika miatt. Nem is beszélve arról, hogy a megadott címkék megbízhatósága néha megkérdőjelezhető. Ezért a felügyelet nélküli kiváló minőségű grafikonreprezentáció elérése számos gyakorlati esetben szükségessé válik, ami motiválja e cikk tanulmányozását. 35 42 50 26 27 49 12 19 43 4 5 46 Az általunk gyűjtött grafikon-szerkezetű adatok gondos vizsgálata során azt találtuk, hogy azok általában különféle forrásokból származnak, mint például a közösségi hálózatok, idézőhálózatok és kommunikációs hálózatok, ahol hatalmas mennyiségű tartalom és összeköttetési információ létezik. Például számos közösségi platform, mint a Twitter, a Flickr és a Facebook adatai tartalmaznak felhasználói jellemzőket, *pl.*, alapvető személyes adatokat, szövegeket, képeket, IP-t, valamint kapcsolataikat, *pl.*, ugyanazon elem vásárlása, barátok. Ezek a gazdag tartalomadatok elegendőek a későbbi bányászati feladatok további útmutatás nélküli támogatásához: ha két entitás extrém hasonlóságot mutat a jellemzőkben, nagy valószínűséggel van köztük kapcsolat (linkjóslás), és valószínűleg ugyanabba a kategóriába tartoznak (osztályozás); ha két entitás mindkettő ugyanarra az entitásra kapcsolódik, valószínűleg hasonló jellemzőik vannak (ajánlás). Ebben az értelemben az információs hálózatokból származó információk lehető leghatékonyabb megőrzése és kinyerése az ágyazási térbe megkönnyíti a kiváló minőségű, kifejező reprezentációk elsajátítását, amelyek kívánatos teljesítményt mutatnak a bányászati feladatokban bármilyen felügyelet nélkül. A felügyelet nélküli grafikonreprezentáció tanulás sok esetben kedvezőbb választás a címkék hiánya miatt, különösen akkor, ha nagyméretű címkézetlen adatokból kívánunk hasznot húzni a vadonban. A grafikonokban rejlő gazdag információk teljes örökléséhez ebben a cikkben a grafikonágyazást a kölcsönös információ (MI) maximalizálásán alapulóan hajtjuk végre, amelyet a Deep Info-Max módszer [ ] empirikus sikere inspirált, amely képeken működik. Hasznos reprezentációk felfedezése érdekében a Deep InfoMax az enkódert arra képezi, hogy maximalizálja az MI-t a bemenetei (vagyis a képek) és a kimenetei (vagyis a rejtett vektorok) között. Amikor a Deep InfoMaxot grafikon tartományban vesszük figyelembe, az első akadály, amin át kell lépnünk, az MI definiálása a grafikonok és a rejtett vektorok között, míg a grafikonok topológiája bonyolultabb, mint a képeké (lásd az 1. ábrát). Az egyik kihívás annak biztosítása, hogy az egyes csomópontok rejtett reprezentációja és a szomszédság bemeneti jellemzői közötti MI-függvény betartsa a szimmetrikus tulajdonságot, vagyis ekvivalens módon, hogy invariáns legyen a szomszédságok permutációival szemben. Az egyik legújabb, MI-t figyelembe vevő munka, a Deep Graph Infomax (DGI) [ ] először beágyaz egy bemeneti grafikon és egy hozzá tartozó korrumpált grafikon, majd egy kiolvasási funkcióval vektorrá összegzi a bemeneti grafikon, végül maximalizálja az MI-t ezen összegző vektor és a rejtett reprezentációk között a bemeneti grafikon (pozitív minta) korrumpált grafikon (negatív minta) általi megkülönböztetésével. Az 1. ábra könnyen érthető áttekintést ad a DGI-ről. Az ilyen típusú MI maximalizálása ekvivalensnek bizonyul a bemeneti csomópont jellemzői és a rejtett vektorok közötti MI maximalizálásával, de ez az ekvivalencia több előzetesen beállított feltétel mellett érvényes, *pl.*, a kiolvasási funkciónak injektívnek kell lennie, ami a valós esetekben túl korlátozottnak tűnik. Még akkor is, ha bizonyos tervezéssel biztosíthatjuk az injektív kiolvasási funkció létezését, *pl.*, a DeepSetsben [ ] használtat, a kiolvasási funkció injektív képességét befolyásolja az is, hogy a paraméterei hogyan vannak képzve. Ez azt jelenti, hogy egy eredetileg injektív függvény még akkor is elveszítheti injektivitását, ha bármilyen külső felügyelet nélkül képzett. És ha a kiolvasási funkció nem injektív, az összefoglaló vektorban lévő bemeneti grafikon információja csökken a grafikon méretének növekedésével. Ezenkívül a DGI durva grafikon/folt szintű MI maximalizálásban marad. Ezért a DGI-ben nincs garancia arra, hogy az enkóder elegendő információt tud desztillálni a bemeneti adatokból, mivel soha nem korrelálja gondosan a rejtett reprezentációkat az eredeti bemeneteikkel. 20 41 47 Ebben a cikkben egy egyenesebb utat javasolunk az MI figyelembevételére grafikus szerkezetek szempontjából, kiolvasási vagy korrupciós funkció használata nélkül. Az MI-t közvetlenül az enkóder bemenete (vagyis a bemeneti szomszédságból álló algráf) és a kimenete (vagyis az egyes csomópontok rejtett reprezentációja) összehasonlításával származtatjuk. És érdekes módon az elméleti levezetéseink kimutatják, hogy a közvetlenül megfogalmazott MI felbontható a helyi MI-k súlyozott összegére az egyes szomszédsági jellemzők és a rejtett vektor között. Ily módon felbontottuk a bemeneti jellemzőket, és kezelhetővé tettük az MI számítást. Ezenkívül ez az MI forma könnyen kielégítheti a szimmetrikus tulajdonságot, ha beállítjuk a súlyok értékeit. További részleteket a 3.1. szakaszban talál. Mivel a fenti MI főként a csomópont jellemzők szintjén mérhető, Jellemző Kölcsönös Információnak (FMI) nevezzük. Két megmaradó kérdés az FMI-vel kapcsolatban: a kombináló súlyok még ismeretlenek, és nem veszi figyelembe a topológiát (vagyis az él jellemzőit). E két probléma további megoldására a Grafikus Kölcsönös Információ (GMI) mérésünket az FMI alapján határozzuk meg. Pontosabban, a GMI intuitív értékhozzárendelést alkalmaz azáltal, hogy az FMI súlyait az egyes szomszédok és a célcsomópont közötti közelségre állítja a reprezentációs térben. A topológiai információ megőrzése érdekében a GMI tovább korrelálja ezeket a súlyokat a bemeneti él jellemzőkkel egy további kölcsönös információs termen keresztül. Az eredményül kapott GMI topológiailag invariáns és kiszámítható is a Mutual Information Neural Estimation (MINE) [ ] segítségével. Munkánk fő hozzájárulásai a következők: 1. 2. 2 • : Általánosítjuk a hagyományos MI becslést a grafikon tartományra, és ennek megfelelően egy új koncepciót, a Grafikus Kölcsönös Információt (GMI) javaslunk. A GMI mentes a Koncepciók potenciális kockázattól, amelyet a kiolvasási funkció okoz, mivel közvetlen módon veszi figyelembe az MI-t a bemeneti grafikonok és a magas szintű ágyazások között. • : Elméleti elemzésünkön keresztül megadunk egy kezelhető és kiszámítható GMI formát, amely az Algoritmusok egész GMI-t a helyi MI-k súlyozott összegére bontja. A MINE módszer segítségével a GMI maximalizálás könnyen elérhető csomópont szinten. • : Ellenőrizzük a GMI hatékonyságát több népszerű csomópontosztályozási és linkjóslási feladatban, beleértve a tranzuktív és induktív feladatokat is. A kísérletek azt mutatják, hogy módszerünk ígéretes teljesítményt nyújt különféle benchmarkokon, sőt néha még a felügyelt társaikat is meghaladja. Kísérleti eredmények 2 KAPCSOLÓDÓ MUNKÁK Munkánk fókusza szerint röviden áttekintjük a korábbi munkákat a következő két területen: kölcsönös információ becslés, és neurális hálózatok grafikonokon történő reprezentációtanuláshoz. 1. 2. . Mivel az InfoMax elv [ ] a neurális hálózatok bemenetei és kimenetei közötti MI maximalizálását támogatja, számos módszer, mint például az ICA algoritmusok [ , ] megpróbálja alkalmazni az MI ötletét a felügyelet nélküli jellemzőtanulásban. Mindazonáltal ezek a módszerek nem általánosíthatók könnyen mély neurális hálózatokra az MI nagy dimenziós folytonos változók közötti kiszámításának nehézsége miatt. Szerencsére a Mutual Information Neural Estimation (MINE) [ ] lehetővé teszi az MI becslését mély neurális hálózatokon egy statisztikai hálózat képzésével, mint osztályozó, hogy megkülönböztesse a közös eloszlásból és a két véletlen változó marginális eloszlásának szorzatából származó mintákat. Pontosabban, a MINE az MI KL-alapú képletét használja, míg egy nem-KL alternatíva, a Jensen-Shannon divergencia (JSD) [ ] használható a pontos MI érték miatti aggodalom nélkül. Kölcsönös információ becslés 3 1 21 2 30 . A grafikon neurális hálózatok (GNN-ek) gyors fejlődésével az elmúlt években számos GNN-alapú grafikonreprezentáció-tanulási algoritmus került előtérbe, amelyek erősebb teljesítményt mutatnak, mint a hagyományos véletlen sétán alapuló és faktorizáción alapuló ágyazási megközelítések [ , , , , ]. Jellemzően ezek a módszerek felügyelt és felügyelet nélküli kategóriákba sorolhatók. Ezek között gazdag irodalom található a grafikonokon történő felügyelt reprezentációtanulásról [ , , , , ]. Annak ellenére, hogy hálózati architektúrájukban eltérnek, empirikus sikereket érnek el címkék segítségével, amelyek valós forgatókönyvekben gyakran nem hozzáférhetők. Ebben az esetben a felügyelet nélküli grafikon tanulási módszerek [ , , ] szélesebb körű alkalmazási potenciállal rendelkeznek. Az ismertebb módszer a GraphSAGE [ ], egy induktív keretrendszer GNN-ek képzésére egy véletlen sétán alapuló célkitűzéssel a felügyelet nélküli beállításban. És nemrégiben a DGI [ ] alkalmazta az MI maximalizálás ötletét a grafikon tartományra, és erős teljesítményt ért el felügyelet nélküli mintában. Azonban a DGI durva maximalizálást valósít meg (vagyis MI maximalizálása grafikon/folt szinten), ami megnehezíti a bemeneti grafikon finom információinak megőrzését. Ezenkívül a DGI-ben használt kiolvasási funkcióra vonatkozó feltétel túl korlátozottnak tűnik a valós esetekben. Ezzel szemben mi arra összpontosítunk, hogy eltávolítsuk a kiolvasási funkció korlátozását, és grafikus kölcsönös információ maximalizálást érjünk el csomópont szinten, közvetlenül az enkóder bemenetei és kimenetei közötti MI maximalizálásával. Az általunk kidolgozott módszerrel származtatott reprezentációk kifinomultabbak a bemeneti grafikon információinak megőrzésében, ami biztosítja a potenciált a downstream grafikon bányászati feladatokhoz, *pl.*, csomópontosztályozás, linkjóslás és ajánlás. Neurális hálózatok grafikonreprezentáció-tanuláshoz 6 15 33 34 39 7 9 25 40 48 11 16 41 16 41 3 GRAFIKUS KÖLCSÖNÖS INFORMÁCIÓ: DEFINÍCIÓ ÉS MAXIMALIZÁLÁS Mielőtt továbbhaladnánk, először megadjuk a cikkben használt előzetes fogalmakat. Jelölje G = (V, E) a grafikon N csomóponttal, vi ∈ V és élek eij = (vi , vj ) ∈ E. A csomópont jellemzőket, feltételezett empirikus P valószínűségi eloszlással, X ∈ R × = {x , · · · , x } jelöli, ahol x ∈ R jelöli az xi csomópont jellemzőjét. Az A ∈ R Adjacency mátrix az élkapcsolatokat reprezentálja, ahol Aij az eij élhez kapcsolódóan valós szám vagy többdimenziós vektor1 lehet. N D 1 N i D N × N A grafikon reprezentációtanulás célja egy f : R × × R × → R × ' enkóder elsajátítása, hogy a H = {h , · · · , h } rejtett vektorok = f (X , A) jelöljék az összes csomópont magas szintű reprezentációját. Az enkódolási folyamat csomópontonkénti formában írható át. N D N N N D 1 N Ennek bemutatásához definiáljuk Xi és Ai az i csomópontra, mint a szomszédai jellemzőit, illetve a hozzájuk tartozó adjacency mátrixot a szomszédok feltételeként. Különösen az Xi minden k-hop szomszédját tartalmazza vi-nek, ahol k ≤ l, ha az f enkóder egy l-rétegű GNN, és tartalmazza magát az i csomópontot is, ha az adjacency mátrixhoz önhurokat adunk hozzá. Itt az Xi és Ai által kibontott algráfot az i csomópontra vonatkozó *támasztó grafikonnak* nevezzük, G -vel jelölve. A támasztó grafikon definíciójával az egyes csomópontok enkódolása h = f (G ) = f (X , A ) lesz. i i i i i A Deep InfoMax [ ] módszerben az enkóder képzési célja az MI maximalizálása a bemenetei és kimenetei között. Az MI-t egy statisztikai hálózat használatával becsülik meg diszkriminátorként a közös eloszlásból származó minták és a marginális eloszlások szorzatából származó minták osztályozására. Természetesen, amikor a Deep InfoMax ötletét a grafikonokra adaptáljuk, maximalizálnunk kell az MI-t a h reprezentáció és a G támasztó grafikon között minden csomópontra. Ezt a grafikus MI-t I (h ; G ) -vel jelöljük. Azonban nem triviális meghatározni az I (h ; G ) -t. A nehézségek a következők: Nehézségek a grafikus kölcsönös információ meghatározásában. 20 i i i i i i • A grafikus MI-nek invariánsnak kell lennie a csomópont index tekintetében. Más szavakkal, ha G és G′ izomorfak egymással, akkor I (h ; G ) = I (h ; G′ ) kell, hogy legyen. i i i i i i • Ha az MI kiszámításához MINE módszert alkalmazunk, a MINE-ben lévő diszkriminátor csak fix méretű bemeneteket fogad el. Ez G esetében még mindig megvalósíthatatlan, mivel a különböző G általában különböző számú csomópontot tartalmaznak, és így eltérő méretűek. i i A grafikus kölcsönös információ meghatározásának problémájának megoldására ez a szakasz a csomópont jellemzőkre támaszkodó Jellemző Kölcsönös Információ (FMI) fogalmának bevezetésével kezdődik. Az FMI dekompozíciójának inspirációjára definiáljuk a Grafikus Kölcsönös Információt (GMI), amely mind a csomópont jellemzőket, mind 3.1 JELLEMZŐ KÖLCSÖNÖS INFORMÁCIÓ Jelöljük a X jellemzők empirikus eloszlását p(X )-nek, a h eloszlását p(h )-nek, és a közös eloszlást p(h , X )-nek. Az információelmélet szerint a h és X közötti MI a következőképpen definiálható: i i i i i i i i Érdekes módon a következő kölcsönös információ dekompozíciós tételünk van az I (h ; X ) kiszámításához. i i 1. tétel (Kölcsönös Információ Dekompozíció). *Ha a feltételes valószínűség p(h |X ) multiplikatív (lásd a multiplikatív definícióját a alatt), akkor a globális kölcsönös információ I (h ; X ), amelyet az (1) egyenlet definiál, súlyozott összegként bontható helyi MI-kre, nevezetesen* i i i i ahol xj az i csomópont j-edik szomszédja, in az Xi összes elemének száma, és a wij súly teljesíti a ≤ wij ≤ 1 értéket minden j-re. 1 A fenti tétel bizonyításához először bevezetünk két lemmát és egy definíciót. 1. lemma. Bármely X, Y és Z véletlen változóra fennáll Az 5. tétel szerinti dekompozícióval kiszámíthatjuk a (2) egyenlet jobb oldalát a MINE segítségével, mivel a diszkriminátor bemenetei most már a (h , x ) párok, amelyek mérete mindig ugyanaz marad (vagyis D' × D). Ezenkívül a súlyokat beállíthatjuk, hogy tükrözzék a bemeneti grafikonok izomorf transzformációját. Például, ha az Xi csak az i csomópont egylépéses szomszédságait tartalmazza, az összes súly azonos értékre állítása ugyanazt az MI-t eredményezi a különböző sorrendű bemeneti csomópontok számára. i j A dekompozíció bizonyos előnyei ellenére nehéz meghatározni a súlyok pontos értékeit, mivel azok az I (h ; x ) értékekhez és a mögöttes eloszlásaikhoz kapcsolódnak. i j Triviális módja az összes súly értékre állítása, majd a (2) egyenlet jobb oldalának maximalizálása az I (h ; X ) alsó határának maximalizálásával ekvivalens, amellyel az igazi FMI is bizonyos mértékig maximalizálódik. Ezen módszer mellett további továbbfejlesztett megoldást kínálunk a súlyok tanítható figyelmekként való figyelembevételével, ami a következő alfejezet témája. 1 i i Az 1. tétel szerinti dekompozíció inspirációjából arra törekszünk, hogy tanítható súlyokat konstruáljunk a grafikonok másik szempontjából (vagyis 3.2 TOPOLÓGIA-TUDATOS KÖLCSÖNÖS INFORMÁCIÓ topológiai nézetből), hogy a w értékek rugalmasabbak legyenek, és megragadják a grafikonok inherent tulajdonságát. Végül levezetjük a Grafikus Kölcsönös Információ (GMI) definícióját. ij 2. definíció (Grafikus Kölcsönös Információ). *A h rejtett vektor és a G = (X , A) támasztó grafikon közötti MI a következőképpen definiálható* ahol mind xj, mind in definíciója megegyezik az 1. tételben szereplővel, a az adjacency mátrix A él súlya/jellemzője, és σ(·) egy szigmoid függvény. ij Intuitívan a (10) egyenlet első tagjában lévő wij súly méri a kísérletekben kezelt súlytalan volt. Formálisan kiszámítjuk az I (w ; a ) = a log(w ) + (1 − a )log(1 − w ). (12) Az I (h ; G ) maximalizálásával a (11) és (12) egyenlet összegével az összes rejtett vektor H felett, elérjük a teljes célfüggvényünket a A helyi MI globális MI-hez való hozzájárulásának mértéke. Az I (h ; x ) hozzájárulást a h és h reprezentációk közötti hasonlósággal (vagyis w = σ(h h )) valósítjuk meg. Ezzel párhuzamosan az I (w ; a ) tag maximalizálja az MI-t a w és az él súlya/jellemzője között (vagyis a ), hogy kényszerítsük a w -t, hogy megfeleljen a topológiai relációknak. Ebben az értelemben a hozzájárulás mértéke összhangban lesz a topológiai szerkezetben lévő közelséggel, amit általában tényként fogadnak el, hogy a w nagyobb lehet, ha a j csomópont "közelebb" van az i csomóponthoz, és fordítva. Ez a stratégia pótolja azt a hibát, hogy az FMI csak a csomópont jellemzőkre összpontosít, és a helyi MI-k adaptív módon járulnak hozzá a globális MI-hez. A figyelem ötletének jobb megértéséhez ebben a stratégiában, tekintse meg a figyelemalapú GCN tanulmányt. Vegye figyelembe, hogy a (10) egyenlet definíciója általános esetekre alkalmazható. Bizonyos speciális helyzetekben a (10) egyenletet kissé módosíthatjuk a hatékonyság érdekében. Például, súlyozatlan grafikonokkal való foglalkozáskor (vagyis az él értéke 1, ha összekapcsolt és 0 egyébként), a második MI tagot I (w ; a ) negatív keresztentrópia veszteséggel helyettesíthetjük. A keresztentrópia minimalizálása szintén hozzájárul az MI maximalizálásához, és hatékonyabb számítást eredményez. További részleteket a következő szakaszban adunk meg. Összességében a (10) egyenlet definíciójának számos előnye van. Először is, ez a fajta MI invariáns a bemeneti grafikonok izomorf transzformációjával szemben. Másodszor, számításilag megvalósítható, mivel a jobb old ij ij ij ij ij ij i i i j i j ij T j ij ij ij ij ij ij ij ij