Нов начин за обучение на изкуствен интелект върху графични данни без надзор

Автори: Жен Пенг Уенбинг Хуанг Миннан Луо Кингхуа Женг Ю Ронг Тингянг Сю Дзюнжоу Хуанг РЕЗЮМЕ Богатството на съдържанието на различни информационни мрежи, като социални мрежи и комуникационни мрежи, предоставя безпрецедентен потенциал за изучаване на висококачествени представителни репрезентации без външен надзор. Тази статия изследва как да се запази и извлече изобилната информация от данни със структура на граф в пространство на вграждане по ненадзорен начин. За тази цел предлагаме нова концепция, Графична взаимна информация (GMI), за измерване на корелацията между входни графи и скрити представяния на високо ниво. GMI обобщава идеята за конвенционалните изчисления на взаимната информация от векторно пространство до домейна на графи, където измерването на взаимната информация от два аспекта на характеристиките на възлите и топологичната структура е незаменимо. GMI показва няколко предимства: Първо, тя е инвариантна към изоморфна трансформация на входни графи — неизбежно ограничение в много съществуващи алгоритми за учене на графови репрезентации; Освен това, тя може да бъде ефективно оценена и максимизирана от текущи методи за оценка на взаимна информация, като MINE; И накрая, нашият теоретичен анализ потвърждава нейната коректност и рационалност. С помощта на GMI разработваме модел за ненадзорено учене, обучен чрез максимизиране на GMI между входа и изхода на графов невронния енкодер. Значителни експерименти върху транзакционна, както и индуктивна класификация на възли и предсказване на връзки демонстрират, че нашият метод превъзхожда съществуващите ненадзорени методи, а понякога дори надминава и надзорените. 1 ВЪВЕДЕНИЕ За постигане на надежден количествен анализ за разнообразни информационни мрежи, ученето на висококачествени репрезентации за данни със структура на граф се превърна в една от настоящите очарователни теми. Скорошните методи към тази цел, обикновено категоризирани като графови невронни мрежи (GNNs), постигнаха забележителни напредъци в многобройни учебни задачи, като класификация на възли [ , , ], предсказване на връзки [ , , ], подравняване на графи [ , , ], генериране на молекули [ , , ], за да назовем само няколко. Въпреки плодотворния напредък, обучението на GNNs в съществуващите подходи обикновено изисква известна форма на надзор. Несъмнено информацията за етикети е скъпа за придобиване — ръчно анотиране или плащане за разрешение, и дори е невъзможно да се получи поради политиката за поверителност. Да не говорим, че надеждността на дадените етикети понякога е съмнителна. Следователно, как да се постигне висококачествена графова репрезентация без надзор става необходимо за много практически случаи, което мотивира изследването на тази статия. 35 42 50 26 27 49 12 19 43 4 5 46 Чрез внимателно разглеждане на събраните от нас данни със структура на граф, установяваме, че те обикновено идват от различни източници, като социални мрежи, цитатни мрежи и комуникационни мрежи, където съществува огромно количество както съдържателна, така и свързваща информация. Например, данни от много социални платформи като Twitter, Flickr и Facebook включват характеристики на потребителите, *напр.*, основни лични данни, текстове, изображения, IP, и техните взаимоотношения, *напр.*, купуване на един и същ артикул, приятелство. Тези богати данни за съдържание са достатъчни за последващи задачи за извличане без допълнителни насоки: ако две същности показват изключителна сходство във характеристиките, има висока вероятност за връзка между тях (предсказване на връзки), и те вероятно принадлежат към една и съща категория (класификация); ако две същности и двете се свързват с една и съща същност, те вероятно имат сходни характеристики (препоръка). В този смисъл, запазването и извличането на възможно най-много информация от информационни мрежи в пространство на вграждане улеснява ученето на висококачествени представителни репрезентации, които показват желано представяне в задачи за извличане без никаква форма на надзор. Ненадзореното учене на графови репрезентации е по-благоприятен избор в много случаи поради свободата от етикети, особено когато възнамеряваме да се възползваме от големи количества ненадзорени данни. За пълноценно наследяване на богатата информация в графите, в тази статия изпълняваме вграждане на граф, базирано на максимизация на взаимната информация (MI), вдъхновени от емпиричния успех на метода Deep Info-Max [ ], който работи върху изображения. За да открием полезни репрезентации, Deep InfoMax обучава енкодера да максимизира MI между входните си данни (т.е. изображенията) и изходите (т.е. скритите вектори). Когато разглеждаме Deep InfoMax в домейна на графите, първото препятствие, което трябва да преодолеем, е как да дефинираме MI между графи и скрити вектори, докато топологията на графите е по-сложна от изображенията (виж Фигура Едно от предизвикателствата е да се гарантира, че функцията MI между скритата репрезентация на всеки възел и входните характеристики на неговата околност спазва симетричното свойство, или еквивалентно, е инвариантна към пермутации на околностите. Като една скорошна работа, разглеждаща MI, Deep Graph Infomax (DGI) [ ] първо вгражда входен граф и съответен повреден граф, след това обобщава входния граф във вектор чрез функция за извличане, накрая максимизира MI между този обобщен вектор и скритите репрезентации, като дискриминира входния граф (положителна проба) от повредния граф (отрицателна проба). Фигура дава лесно разбираемо общо описание на DGI. Максимизирането на този вид MI се оказва еквивалентно на максимизирането на MI между входните характеристики на възлите и скритите вектори, но тази еквивалентност важи при няколко предварително зададени условия, *напр.*, функцията за извличане трябва да бъде инжективна, което все още изглежда прекалено ограничаващо в реални случаи. Дори и да можем да гарантираме съществуването на инжективна функция за извличане чрез определен дизайн, *напр.*, тази, използвана в DeepSets [ ], инжективната способност на функцията за извличане също се влияе от начина, по който се обучават нейните параметри. Това означава, че една първоначално инжективна функция все още има риск да стане неинжективна, ако се обучава без външен надзор. И ако функцията за извличане не е инжективна, информацията за входния граф, съдържаща се в обобщения вектор, ще намалее с увеличаване на размера на графа. Освен това DGI остава в грубо максимизиране на MI на ниво граф/част. Следователно в DGI няма гаранция, че енкодерът може да извлече достатъчно информация от входните данни, тъй като никога не свързва сложно скритите репрезентации с оригиналните им входове. 20 1). 41 1 47 В тази статия предлагаме по-директен начин за разглеждане на MI по отношение на графични структури, без да използваме функция за извличане или функция за повреждане. Директно извеждаме MI чрез сравняване на входа (т.е. под-графа, състоящ се от входната околност) и изхода (т.е. скритата репрезентация на всеки възел) на енкодера. И интересното е, че нашите теоретични изводи показват, че директно формулираната MI може да бъде разложена на претеглена сума от локални MI между всяка околна характеристика и скрития вектор. По този начин разложихме входните характеристики и направихме изчислението на MI проследимо. Освен това, тази форма на MI може лесно да удовлетвори симетричното свойство, ако коригираме стойностите на теглата. Повече подробности ще предоставим в § Тъй като гореспоменатата MI се измерва предимно на ниво характеристики на възлите, наричаме я Feature Mutual Information (FMI). 3.1. Два оставащи въпроса относно FMI: **1.** комбиниращите тегла все още са неизвестни и **2.** тя не взема предвид топологията (т.е. характеристиките на ребрата). За да адресираме тези два въпроса допълнително, дефинираме нашето измерване Graphical Mutual Information (GMI) въз основа на FMI. По-специално, GMI прилага интуитивно присвояване на стойности, като задава теглата във FMI равни на близостта между всеки съсед и целевия възел в пространството на репрезентациите. Що се отнася до запазването на топологичната информация, GMI допълнително корелира тези тегла с входните характеристики на ребрата чрез допълнителен член за взаимна информация. Полученият GMI е топологично инвариантен и също така изчислим с Mutual Information Neural Estimation (MINE) [ ]. Основните приноси на нашата работа са следните: 2 • * *: Обобщаваме конвенционалната MI оценка в домейна на графите и съответно предлагаме нова концепция за Graphical Mutual Information (GMI). GMI е свободен от Концепции потенциален риск, причинен от функцията за извличане, тъй като той разглежда MI между входни графи и скрити представяния по директен модел. • * *: Чрез нашия теоретичен анализ даваме проследима и изчислима форма на GMI, която разлага Алгоритми целия GMI на претеглена сума от локални MI. С помощта на метода MINE, максимизирането на GMI може лесно да се постигне на ниво възел. • * *: Потвърждаваме ефективността на GMI върху няколко популярни задачи за класификация на възли и предсказване на връзки Експериментални открития включително както транзакционни, така и индуктивни. Експериментите демонстрират, че нашият метод постига обещаващо представяне на разнообразни бенчмаркове и дори понякога превъзхожда надзорените. 2 СВЪРЗАНА РАБОТА В съответствие с фокуса на нашата работа, накратко преглеждаме предишната работа в следните две области: **1.** оценка на взаимна информация и **2.** невронни мрежи за учене на репрезентации върху графи. . Тъй като принципът InfoMax [ ] препоръчва максимизиране на MI между входовете и изходите на невронни мрежи, много методи като ICA алгоритми [ , ] се опитват да използват идеята за MI в ненадзореното учене на характеристики. Въпреки това, тези методи не могат лесно да бъдат обобщени за дълбоки невронни мрежи поради трудността при изчисляването на MI между високомерни непрекъснати променливи. За щастие, Mutual Information Neural Estimation (MINE) [ ] прави оценката на MI върху дълбоки невронни мрежи осъществима чрез обучение на статистическа мрежа като класификатор за разграничаване на проби, идващи от съвместното разпределение и произведението на маргиналните разпределения на две случайни променливи. По-специално, MINE използва точната KL-базирана формулировка на MI, докато не-KL алтернатива, Jensen-Shannon divergence (JSD) [ ], може да се използва без притеснение относно точната стойност на MI. Оценка на взаимна информация 3 1 21 2 30 . С бързото развитие на графовите невронни мрежи (GNNs), голям брой алгоритми за учене на графови репрезентации, базирани на GNNs, бяха предложени през последните години, които показват по-силно представяне от традиционните методи за вграждане, базирани на случайни разходки и факторизация [ , , , , ]. Обикновено тези методи могат да бъдат разделени на надзорени и ненадзорени категории. Сред тях има богата литература за надзорено учене на репрезентации върху графи [ , , , , ]. Въпреки вариациите си в мрежовата архитектура, те постигат емпиричен успех с помощта на етикети, които често не са достъпни в реални сценарии. В този случай, ненадзорените методи за графово учене [ , , ] имат по-широк приложен потенциал. Добре познатият метод е GraphSAGE [ ], индуктивна рамка за обучение на GNNs чрез цел, базирана на случайни разходки в неговия ненадзорен режим. И наскоро, DGI [ ] прилага идеята за максимизиране на MI в домейна на графите и постига силно представяне по ненадзорен модел. Въпреки това, DGI изпълнява грубо максимизиране (т.е., максимизиране на MI на ниво граф/част), което затруднява запазването на деликатната информация във входния граф. Освен това, условието, наложено на функцията за извличане, използвана в DGI, изглежда е прекалено ограничаващо в реални случаи. За разлика от това, ние се фокусираме върху премахването на ограничението на функцията за извличане и постигането на максимизиране на графична взаимна информация на ниво възел чрез директно максимизиране на MI между входовете и изходите на енкодера. Репрезентациите, получени чрез нашия метод, са по-сложни в запазването на информацията от входния граф, което осигурява потенциала му за последващи задачи за извличане от графи, *напр.*, класификация на възли, предсказване на връзки и препоръка. Невронни мрежи за учене на графови репрезентации 6 15 33 34 39 7 9 25 40 48 11 16 41 16 41 3 ГРАФИЧНА ВЗАИМНА ИНФОРМАЦИЯ: ОПРЕДЕЛЕНИЕ И МАКСИМИЗАЦИЯ Преди да продължим, първо предоставяме предварителните концепции, използвани в тази статия. Нека G = (V, E) означава граф с *N* възли *vi* ∈ V и ребра *eij* = (*vi*, *vj*) ∈ E. Характеристиките на възлите, при предполагаемо емпирично разпределение на вероятностите P, са дадени от *X* ∈ R*N* ×*D* = {*x* 1, · · · , *x* N* } където *xi* ∈ R*D* означава характеристиката за възел *vi*. Матрицата на съседство *A* ∈ R*N* ×*N* представлява връзките на ребрата, където *Aij*, свързано с ребро *eij*, може да бъде реално число или многоизмерен вектор1. Целта на ученето на графови репрезентации е да се научи енкодер *f* : R*N* ×*D* × R*N* ×*N* → R*N* ×*D*', така че скритите вектори *H* = {*h*1, · · · , *hN* } = *f* (*X*, *A*) да показват репрезентации на високо ниво за всички възли. Процесът на кодиране може да бъде пренаписан във форма за всеки възел. За да покажем това, дефинираме *Xi* и *Ai* за възел *i* като съответно характеристиките на неговите съседи и съответната матрица на съседство условно на съседите. По-специално, *Xi* включва всички k-хоп съседи на *vi* с *k* ≤ *l*, когато енкодерът *f* е *l*-слоен GNN, и включва самия възел *i*, ако допълнително добавим самопримки в матрицата на съседство. Тук наричаме под-графа, разширен от *Xi* и *Ai*, като *поддържащ граф* за възел *i*, означен с G*i*. С дефиницията на поддържащ граф, кодирането за всеки възел става *hi* = *f* (G*i*) = *f* (*Xi*, *Ai*). В Deep InfoMax [ ], учебната цел на енкодера е да максимизира MI между входовете и изходите му. MI се оценява чрез използване на статистическа мрежа като дискриминатор за класифициране на проби, идващи от съвместното разпределение, и тези, взети от произведението на маргиналните разпределения. Естествено, когато адаптираме идеята на Deep InfoMax към графи, трябва да максимизираме MI между репрезентацията *hi* и поддържащия граф G*i* за всеки възел. Означаваме такава графична MI като *I* (*hi*; G*i*). Въпреки това, не е лесно да се дефинира I (*hi*; Gi*). Трудностите са: Трудности при дефинирането на графична взаимна информация. 20 • Графичната MI трябва да бъде инвариантна по отношение на индекса на възела. С други думи, трябва да имаме *I* (*hi*; G*i*) = *I* (*hi*; G′*i*), ако G*i* и G′*i* са изоморфни. • Ако използваме метода MINE за изчисление на MI, дискриминаторът в MINE приема само входове с фиксиран размер. Това все още е невъзможно за G*i*, тъй като различните G*i* обикновено включват различен брой възли и следователно са с различни размери. За да заобиколим проблема с дефинирането на графична взаимна информация, този раздел започва с въвеждане на концепцията за Feature Mutual Information (FMI), която разчита само на характеристиките на възлите. Въз основа на разлагането на FMI, след това дефинираме Graphical Mutual Information (GMI), която взема предвид както характеристиките на възлите, така и 3.1 Характерна взаимна информация Означаваме емпиричното разпределение на вероятностите на характеристиките на възлите *Xi* като *p* (*Xi*), вероятността на *hi* като *p* (*hi*) и съвместното разпределение като *p* (*hi*, *Xi*). Според теорията на информацията, MI между *hi* и *Xi* се дефинира като Интересно е, че имаме следната теорема за разлагане на взаимната информация за изчисляване на *I* (*hi*; *Xi*). Теорема 1 (Разлагане на взаимната информация). *Ако условната вероятност p*(*hi* |*Xi*) *е мултипликативна (виж дефиницията за мултипликативност в [ ]), глобалната взаимна информация I* (*hi*; *Xi*) *дефинирана в Уравнение* *може да бъде разложена като претеглена сума от локални MI, а именно,* 36 (1) *където xj е j-тият съсед на възел i, in е броят на всички елементи в Xi, и теглото wij удовлетворява* ≤ *wij* ≤ 1 *за всяко j.* 1 За да докажем горната теорема, първо въвеждаме две леми и една дефиниция. Лема 1. *За произволни случайни променливи X, Y и Z, имаме* С разлагането в Теорема можем да изчислим дясната страна на Уравнение чрез MINE, тъй като входовете на дискриминатора сега стават двойки (*hi*, *xj*), чийто размер винаги се поддържа същия (т.е., *D*' - по *D*). Освен това можем да коригираме теглата, за да отразим изоморфната трансформация на входните графи. Например, ако *Xi* съдържа само еднохоп съседи на възел *i*, задаването на всички тегла да бъдат еднакви ще доведе до същата MI за входните възли в различен ред. 1, (2) Въпреки някои предимства на разлагането, е трудно да се характеризират точните стойности на теглата, тъй като те са свързани със стойностите на *I* (*hi*; *xj*) и техните основни разпределения на вероятностите. Тривиален начин е да се зададат всички тегла на , след което максимизирането на дясната страна на Уравнение е еквивалентно на максимизирането на долната граница на *I* (*hi*; *Xi*), чрез което истинският FMI също се максимизира до известна степен. Освен този метод, допълнително предоставяме по-усъвършенствано решение чрез разглеждане на теглата като обучаеми внимание, което е темата в следващия подраздел. 1 (2) Вдъхновени от разлагането в Теорема се опитваме да конструираме обучаеми тегла от другия аспект на графите (т.е., 3.2 Взаимна информация, съобразена с топологията 1, топологичен изглед), така че стойностите на *wij* да могат да бъдат по-гъвкави и да улавят присъщото свойство на графите. В крайна сметка извеждаме дефиницията на Graphical Mutual Information (GMI). Дефиниция 2 (Graphical Mutual Information). *MI между скрития вектор h и неговия поддържащ граф* G = (*X*, *A*) *се дефинира като* където дефинициите както на xj, така и на in са същите като в Теорема 1, aij е теглото/характеристиката на реброто в матрицата на съседство A, и σ(·) е сигмоидна функция. Интуитивно, теглото wij в първия член на Уравнение (10) измерва справяне в експериментите са нетегловни. Формално, изчисляваме I (wij; aij) = aijloдwij + (1 − aij )loд(1 − wij). (12) Чрез максимизиране на I (hi ; Gi ) със сумата от Уравнение (11) и Уравнение (12) върху всички скрити вектори H, стигаме до нашата пълна целева функция за приноса на локална MI към глобалната. Ние реализираме приноса на I (hi ; xj ) чрез сходството между репрезентациите hi и hj (т.е., wij = σ (hThj )). Междувременно, членът I (wij ; aij) максимизира MI между wij и теглото/характеристиката на реброто на входния граф (т.е., aij), за да наложи wij да съответства на топологичните връзки. В този смисъл, степента на приноса ще бъде в съответствие с близостта в топологичната структура, което обикновено се приема като факт, че wij може да бъде по-голямо, ако възел j е "по-близо" до възел i и по-малко иначе. Тази стратегия компенсира недостатъка, че FMI се фокусира само върху характеристиките на възлите и прави локалните MI да допринасят адаптивно към глобалните. За по-добро разбиране на идеята за внимание в тази стратегия, можете да се обърнете към GCN, базиран на внимание. Имайте предвид, че дефиницията на Уравнение (10) е приложима за общи случаи. За някои специфични ситуации, можем леко да модифицираме Уравнение (10) за ефективност. Например, при работа с нетегловни графи (тоест стойността на реброто е 1, ако е свързано, и 0 иначе), можем да заменим втория MI член I (wij ; aij) с загуба на отрицателна крос-ентропия. Минимизирането на крос-ентропията също допринася за максимизиране на MI и осигурява по-ефективно изчисление. Повече подробности ще предоставим в следващия раздел. Като цяло, има няколко предимства от дефиницията на Уравнение (10). Първо, този вид MI е инвариантен към изоморфна трансформация на входните графи. Второ, той е изчислително осъществим, тъй като всеки компонент от дясната страна може да бъде оценен чрез MINE. Още по-важно, GMI е по-мощен от DGI в улавянето на оригиналната входна информация поради ясното му корелиране между скритите вектори и входните характеристики както на възлите, така и на ребрата на фино ниво възел. 3.3 Максимизация на GMI Сега директно максимизираме дясната страна на Уравнение с помощта на MINE. Имайте предвид, че MINE оценява долна граница на MI с представянето на Donsker-Varadhan (DV) [ ] на KL-разминаването между съвместното разпределение и произведението на маргиналните разпределения. Тъй като се фокусираме повече върху максимизирането на MI, отколкото върху получаването на неговата конкретна стойност, могат да бъдат използвани други не-KL алтернативи като Jensen-Shannon MI estimator (JSD) [ ] и Noise-Contrastive estimator (infoNCE) [ ] за негова замяна. Въз основа на експерименталните открития и анализ в [ ], ние използваме JSD оценчик в тази статия с цел ефективност и ефикасност, тъй като infoNCE оценчикът е чувствителен към стратегии за отрицателно семплиране (броя на отрицателните проби), поради което може да се превърне в пречка за големи набори от данни с фиксирана налична памет. Напротив, нечувствителността на JSD оценчика към стратегии за отрицателно семплиране и неговото уважително представяне в много задачи го правят по-подходящ за нашата задача. По-специално, изчисляваме *I* (*hi*; *xj*) в първия член на Уравнение чрез (10) 10 30 31 20 (10)