Новы спосаб навучання ШІ на графічных даных без нагляду

```html Аўтары: Чжэнь Пэн Вэньбін Хуан Міньнань Ло Цынхуа Чжэн Юй Жун Цінъян Сюй Цзюньчжоу Хуан РЭЗЮМЭ Багацце зместу розных інфармацыйных сетак, такіх як сацыяльныя сеткі і камунікацыйныя сеткі, забяспечвае беспрэцэдэнтны патэнцыял для навучання якасных прадстаўленчых прадстаўленняў без вонкавага нагляду. У гэтым артыкуле даследуецца, як захаваць і здабыць багатую інфармацыю з даных графавай структуры ў прастору ўбудавання без нагляду. Для гэтага мы прапануем новую канцэпцыю, графічную ўзаемную інфармацыю (GMI), для вымярэння карэляцыі паміж уваходнымі графамі і высокаўзроўневымі схаванымі прадстаўленнямі. GMI абагульняе ідэю звычайных разлікаў узаемнай інфармацыі з вектарнай прасторы ў дамен графа, дзе вымярэнне ўзаемнай інфармацыі з двух аспектаў прыкмет вузлоў і тапалагічнай структуры з'яўляецца неабходным. GMI мае некалькі пераваг: па-першае, ён інварыянтны да ізаморфных пераўтварэнняў уваходных графаў — непазбежнае абмежаванне ў многіх існуючых алгарытмах навучання прадстаўленняў графаў; акрамя таго, яго можна эфектыўна ацаніць і максімізаваць з дапамогай бягучых метадаў ацэнкі ўзаемнай інфармацыі, такіх як MINE; нарэшце, наш тэарэтычны аналіз пацвярджае яго правільнасць і рацыянальнасць. З дапамогай GMI мы распрацоўваем мадэль навучання без нагляду, навучаную шляхам максімізацыі GMI паміж уваходам і выхадам графавага нейроннага энкодера. Шматлікія эксперыменты па трансьдуктыўнай, а таксама індуктыўнай класіфікацыі вузлоў і прадказанні сувязяў дэманструюць, што наш метад пераўзыходзіць сучасныя некантралюемыя аналогі, а часам нават перавышае прадукцыйнасць кантралюемых. 1 УВОДЗІНЫ Для дасягнення надзейнага колькаснага аналізу разнастайных інфармацыйных сетак, навучанне якасных прадстаўленняў для даных графавай структуры стала адной з найбольш захапляльных тэм. Апошнія метады, накіраваныя на гэту мэту, звычайна класіфікуюцца як Графавыя Нейронныя Сеткі (GNN), дасягнулі выдатных поспехаў у вялікай колькасці навучальных задач, такіх як класіфікацыя вузлоў [ , , ], прадказанне сувязяў [ , , ], выраўноўванне графаў [ , , ], генерацыя малекул [ , , ] і інш. Нягледзячы на плённы прагрэс, навучанне GNN у існуючых падыходах звычайна патрабуе пэўнага тыпу нагляду. Безумоўна, маркіровачная інфармацыя дарагая для атрымання — ручная анатацыя або аплата за дазвол, і нават немагчымая для дасягнення з-за палітыкі прыватнасці. Не кажучы ўжо пра тое, што надзейнасць дадзеных пазнак часам выклікае сумневы. Такім чынам, як дасягнуць якаснага прадстаўлення графа без нагляду, стала неабходнасцю для вялікай колькасці практычных выпадкаў, што матывуе даследаванне гэтага артыкула. 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: вагавыя каэфіцыенты па-ранейшаму невядомыя і яна не ўлічвае тапалогію ( ., прыкметы рэбраў). Каб далей вырашыць гэтыя дзве праблемы, мы вызначаем наша вымярэнне Graphical Mutual Information (GMI) на аснове FMI. У прыватнасці, GMI прымяняе інтуітыўнае прызначэнне значэнняў, усталёўваючы вагавыя каэфіцыенты ў FMI роўнымі блізкасці паміж кожным суседам і мэтавым вузлом у прасторы прадстаўлення. Што тычыцца захавання інфармацыі тапалогіі, GMI далей карэлюе гэтыя вагавыя каэфіцыенты з уваходнымі прыкметамі рэбраў праз дадатковы член узаемнай інфармацыі. Атрыманы GMI тапалагічна інварыянтны, а таксама вылічальны з дапамогай Mutual Information Neural Estimation (MINE) Асноўныя ўклады нашай працы наступныя: 1. 2. г.зн [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 альтэрнатыва, дывергенцыя Енсена-Шэнана (JSD) [ ], можа выкарыстоўвацца без клопатаў аб дакладным значэнні MI. Ацэнка ўзаемнай інфармацыі 3 1 21 2 30 . З хуткім развіццём графавых нейронных сетак (GNN), у апошнія гады быў прапанаваны вялікі шэраг алгарытмаў навучання прадстаўленняў графаў на аснове GNN, якія дэманструюць мацнейшую прадукцыйнасць, чым традыцыйныя метады убудавання на аснове выпадковых блуканняў і фактарызацыі [ , , , , ]. Звычайна гэтыя метады можна падзяліць на катэгорыі з наглядам і без нагляду. Сярод іх існуе багатая літаратура па навучанні прадстаўленняў з наглядам над графамі [ , , , , ]. Нягледзячы на іх разнастайнасць у архітэктуры сеткі, яны дасягаюць эмпірычнага поспеху з дапамогай пазнак, якія часта недаступныя ў рэальных сцэнарыях. У гэтым выпадку метады навучання графаў без нагляду [ , , ] маюць больш шырокі патэнцыял прымянення. Вядомы метад — GraphSAGE [ ], індуктыўная структура для навучання GNN праз мэту на аснове выпадковых блуканняў у яго рэжыме без нагляду. І нядаўна 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) абазначае граф з вузламі ∈ V і рэбрамі = ( , ) ∈ E. Прыкметы вузлоў, з меркаванай эмпірычнай размеркаваннем верагоднасці P, даюцца як ∈ N vi eij vi vj X R × = { 1, · · · , }, дзе ∈ R абазначае прыкмету для вузла . Матрыца суседства ∈ R × абазначае суседнія злучэнні, дзе , звязаны з рэбрам , можа быць рэальным лікам або шматмерным вектарам1. N D x x N xi D vi A N N Aij eij Мэта навучання прадстаўлення графа — навучыць энкодер : R × × R × → R × ′ , такім чынам, каб схаваныя вектары = { 1, · · · , } = ( , ) паказвалі высокаўзроўневыя прадстаўленні для ўсіх вузлоў. Працэс кадавання можна перапісаць у форме па вузлах. f N D N N N D H h hN f X A Каб паказаць гэта, мы вызначаем і для вузла як адпаведна прыкметы яго суседзяў і адпаведную матрыцу суседства Xi Ai i пры ўмове суседзяў. У прыватнасці, ўключае ў сябе ўсіх k-мерных суседзяў з ≤ , калі энкодер з'яўляецца -слаёвым GNN, і ён уключае сам вузел , калі мы дадаткова дадамо самазлучэнні ў матрыцу суседства. Тут мы называем падграф, пашыраны і , як для вузла , пазначаны як G . З вызначэннем падтрымліваючага графа, кадаванне для кожнага вузла становіцца = (G ) = ( , ). Xi vi k l f l i Xi Ai падтрымліваючы граф i i hi f i f Xi Ai У Deep InfoMax [ ] мэтай навучання энкодера з'яўляецца максімізацыя MI паміж яго ўходамі і выхадамі. MI ацэньваецца шляхам выкарыстання статыстычнай сеткі ў якасці дыскрымінатора для класіфікацыі выбарак, якія паступаюць з сумеснай размеркавання, і тых, якія атрыманы з прадукту маргіналаў. Натуральна, пры адаптацыі ідэі Deep InfoMax да графаў, мы павінны максімізаваць MI паміж прадстаўленнем і падтрымліваючым графам G для кожнага вузла. Мы абазначаем такую графічную MI як ( ; G ). Аднак вызначыць I (hi ; Gi ) не проста. Труднасці: Труднасці ў вызначэнні графічнай узаемнай інфармацыі. 20 hi i I hi i • Графічная MI павінна быць інварыянтнай адносна індэкса вузла. Іншымі словамі, мы павінны мець ( ; G ) = ( ; G′ ), калі G і G′ ізаморфныя. I hi i I hi i i i • Калі мы выкарыстоўваем метад MINE для разліку MI, дыскрымінатар у MINE прымае толькі ўваходы фіксаванага памеру. Гэта яшчэ не ажыццяўляльна для G , паколькі розныя G звычайна ўключаюць розную колькасць вузлоў і, такім чынам, маюць розныя памеры. i i Каб абыйсці праблему вызначэння графічнай узаемнай інфармацыі, гэты раздзел пачынаецца з увядзення паняцця Feature Mutual Information (FMI), якое абапіраецца толькі на прыкметы вузлоў. На аснове натхнення ад раскладання FMI, мы затым вызначаем Graphical Mutual Information (GMI), якое ўлічвае як прыкметы вузлоў, так і 3.1 Асаблівасці ўзаемнай інфармацыі Мы абазначаем эмпірычнае размеркаванне верагоднасці прыкмет вузлоў як ( ), верагоднасць як ( ), і сумесную размеркаванне як ( , ). Згодна з тэорыяй інфармацыі, MI паміж і вызначаецца як Xi p Xi hi p hi p hi Xi hi Xi Цікава, што мы маем наступную тэарэму раскладання ўзаемнай інфармацыі для разліку ( ; ). I hi Xi Тэарэма 1 (Раскладанне ўзаемнай інфармацыі). ( | ) ( ; ) , Калі ўмоўная верагоднасць p hi Xi мультыплікатыўная (гл. вызначэнне мультыплікатыўнай у [ ]), глабальная ўзаемная інфармацыя I 36 hi Xi , вызначаная ў Eq. (1) можа быць раскладзена як зважонае сумаванне мясцовых MI, а менавіта, ≤ ≤ 1 дзе xj з'яўляецца j-м суседам вузла i, in — колькасць усіх элементаў у Xi , і вага wij задавольвае 1 wij для кожнага j. Каб даказаць вышэйзгаданую тэарэму, мы спачатку ўводзім дзве лемы і адно вызначэнне. Лема 1. Для любых выпадковых зменных X, Y і Z, мы маем З раскладаннем у Тэарэме мы можам разлічыць правую частку Eq. з дапамогай MINE, бо ўваходы дыскрымінатара цяпер становяцца парамі ( , ), памер якіх заўсёды застаецца аднолькавым ( ., ′× ). Акрамя таго, мы можам наладзіць вагавыя каэфіцыенты, каб адлюстраваць ізаморфнае пераўтварэнне уваходных графаў. Напрыклад, калі ўключае толькі аднаяднасных суседзяў вузла , усталяванне ўсіх вагавых каэфіцыентаў роўнымі прывядзе да аднолькавай MI для уваходных вузлоў у розных парадках. 1, (2) hi xj г.зн D D Xi i Нягледзячы на некаторыя перавагі раскладання, цяжка ахарактарызаваць дакладныя значэнні вагавых каэфіцыентаў, паколькі яны звязаны са значэннямі ( ; ) і іх базавым размеркаваннем верагоднасці. I hi xj Трывіяльны спосаб — усталяваць усе вагавыя каэфіцыенты роўнымі , затым максімізацыя правай часткі Eq. эквівалентная максімізацыі ніжняй мяжы ( ; ), шляхам чаго сапраўдная FMI таксама максімізуецца да нейкай ступені. Акрамя гэтага метаду, мы дадаткова прапануем больш удасканаленае рашэнне, разглядаючы вагавыя каэфіцыенты як навучальныя ўвагі, што з'яўляецца тэмай наступнага падзелу. 1 (2) I hi Xi Натхнёныя раскладаннем у Тэарэме мы спрабуем стварыць навучальныя ва 3.2 Тапалагічна-успрымальная ўзаемная інфармацыя 1,