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

Автори: Чжен Пенг Веньбін Хуан Міннань Луо Цінхуа Чжен Юй Ронг Тін'ян Сюй Цзюньчжоу Хуан АНОТАЦІЯ Багатство змісту різних інформаційних мереж, таких як соціальні та комунікаційні мережі, надає безпрецедентний потенціал для навчання високоякісних виразних представлень без зовнішнього нагляду. У цій статті досліджується, як зберігати та витягувати рясну інформацію з графових даних у просторі вбудовування ненав'язливим способом. Для цього ми пропонуємо нову концепцію, Графічну Взаємну Інформацію (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: **1.** комбіновані ваги все ще невідомі, і **2.** вона не враховує топологію (*тобто*, характеристики ребер). Щоб додатково вирішити ці дві проблеми, ми визначаємо наше вимірювання Графічної Взаємної Інформації (GMI) на основі FMI. Зокрема, GMI застосовує інтуїтивне присвоєння значень, встановлюючи ваги у FMI рівними близькості між кожним сусідом та цільовим вузлом у просторі представлень. Щоб зберегти топологічну інформацію, GMI додатково корелює ці ваги з вхідними характеристиками ребер через додатковий член взаємної інформації. Отримана GMI є топологічно інваріантною, а також обчислюваною за допомогою Mutual Information Neural Estimation (MINE) [ ]. Основні внески нашої роботи такі: 2 • * *: Ми узагальнюємо традиційну оцінку MI до графової області і відповідно пропонуємо нову концепцію Графічної Взаємної Інформації (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) позначає граф з *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 (Розклад взаємної інформації). (*hi* |*Xi* ) (*hi* ; *Xi* ) Якщо умовна ймовірність p є мультиплікативною (див. визначення мультиплікативної у [ ]), глобальна взаємна інформація I 36 визначена в Рівн. (1) може бути розкладена як зважена сума локальних MI, а саме, ≤ *wij* ≤ 1 де xj є j-м сусідом вузла i, in - кількість усіх елементів у Xi, а вага wij задовольняє 1 для кожного j. Щоб довести вищезазначену теорему, ми спочатку вводимо два леми та одне визначення. Лема 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* могли бути більш гнучкими та враховувати властиву графам природу. Зрештою, ми виводимо визначення Графічної Взаємної Інформації (GMI). Визначення 2 (Графічна Взаємна Інформація). G = (*X* , *A* ) MI між прихованим вектором h та його підтримуючим графом визначається як де визначення як xj, так і in такі ж, як у Теоремі 1, aij — це вага/характеристика ребра в матриці суміжності A, а σ(·) — це сигмоїдна функція. Інтуїтивно, вага wij у першому члені Рівн. (10) вимірює оброблені в експериментах є незваженими. Формально, ми обчислюємо I (wij ; aij ) = aijloдwij + (1 − aij )loд(1 − wij ). &