Графові нейронні мережі (ГНМ) — це спеціалізовані штучні нейронні мережі, розроблені для завдань, вхідними даними яких є графи.

Яскравим прикладом застосування є молекулярний дизайн ліків. Кожен вхідний зразок є графовим представленням молекули, де атоми утворюють вершини (вузли), а хімічні зв'язки між атомами утворюють ребра. На додаток до графового представлення, вхідні дані також включають відомі хімічні властивості для кожного з атомів. Таким чином, зразки наборів даних можуть відрізнятися за довжиною, що відображає змінну кількість атомів у молекулах та змінну кількість зв'язків між ними. Завдання полягає в прогнозуванні ефективності даної молекули для конкретного медичного застосування, наприклад, усунення бактерій E. coli.

Ключовим елементом архітектури ГНМ є використання парної передачі повідомлень (pairwise message passing), завдяки якій вузли графа ітеративно оновлюють свої представлення, обмінюючись інформацією зі своїми сусідами. Було запропоновано кілька архітектур ГНМ, які реалізують різні варіації передачі повідомлень, починаючи з рекурсивних або згорткових конструктивних підходів. Станом на 2022 рік, залишається відкритим питання, чи можливо визначити архітектури ГНМ, які "виходять за межі" передачі повідомлень, або ж кожна ГНМ може бути побудована на передачі повідомлень через відповідним чином визначені графи.

У більш загальній сфері "геометричного глибокого навчання" деякі наявні архітектури нейронних мереж можуть бути інтерпретовані як ГНМ, що працюють із відповідним чином визначеними графами. Шар згорткової нейронної мережі (ЗНМ), в контексті комп'ютерного зору, можна розглядати як ГНМ, застосовану до графів, вузлами яких є пікселі, і лише суміжні пікселі з'єднані ребрами. Шар трансформера, у обробці природної мови, можна розглядати як ГНМ, застосовану до повних графів, вузлами яких є слова або токени у фрагменті тексту природної мови.

Відповідні домени застосування для ГНМ включають обробку природної мови, соціальні мережі, мережі цитування, молекулярну біологію, Хімія, Фізика та NP-складних задач комбінаторної оптимізації.

Відкриті бібліотеки, що реалізують ГНМ, включають PyTorch Geometric (PyTorch), TensorFlow GNN (TensorFlow), Deep Graph Library (незалежний від фреймворку), jraph (Google JAX), та GraphNeuralNetworks.jl/GeometricFlux.jl (Julia, Flux).

Архітектура

Архітектура загальної ГНМ реалізує такі фундаментальні шари: Інваріантність до перестановок (Permutation equivariant): шар з інваріантністю до перестановок відображає представлення графа в оновлене представлення того ж графа. У літературі шари з інваріантністю до перестановок реалізуються за допомогою парної передачі повідомлень між вершинами графа. Інтуїтивно, у шарі передачі повідомлень вершини **оновлюють** свої представлення, **агрегуючи** **повідомлення**, отримані від своїх безпосередніх сусідів. Таким чином, кожен шар передачі повідомлень збільшує поле сприйняття ГНМ на один "стрибок" (hop). Локальний пулінг (Local pooling): локальний шар пулінгу укрупнює граф шляхом зниження частоти дискретизації. Локальний пулінг використовується для збільшення поля сприйняття ГНМ, подібно до шарів пулінгу у згорткових нейронних мережах. Приклади включають пулінг k-найближчих сусідів (k-nearest neighbours pooling), пулінг за top-k та пулінг на основі само-уваги (self-attention pooling). Глобальний пулінг (Global pooling): шар глобального пулінгу, також відомий як шар зчитування (readout), забезпечує представлення всього графа фіксованого розміру. Шар глобального пулінгу повинен бути інваріантним до перестановок, щоб перестановки у порядку вершин та ребер графа не змінювали кінцевий результат. Приклади включають поелементну суму, середнє або максимум.

Було продемонстровано, що ГНМ не можуть бути більш виразними, ніж Тест графового ізоморфізму Вейсфейлера–Лемана. На практиці це означає, що існують різні графові структури (наприклад, молекули з однаковими атомами, але різними зв'язками), які не можуть бути розрізнені ГНМ. Можна розробити більш потужні ГНМ, що працюють із геометріями вищої розмірності, такими як симпліційні комплекси. Станом на 2022 рік, чи вдасться майбутнім архітектурам подолати примітив передачі повідомлень, є відкритим дослідницьким питанням.

Навчання гетерофільних графів Принцип **гомофілії**, тобто що вершини з однаковими мітками або схожими атрибутами частіше з'єднані, зазвичай вважався основною причиною переваги Графових нейронних мереж (ГНМ) над традиційними нейронними мережами (НМ) на графоструктурованих даних, особливо в задачах на рівні вершин. Однак останні роботи виявили нетривіальний набір наборів даних, де продуктивність ГНМ порівняно з НМ є незадовільною. Гетерофілія (Heterophily), тобто низька гомофілія, розглядалася як основна причина цього емпіричного спостереження. Дослідники почали переглядати та переоцінювати більшість існуючих графових моделей у сценарії гетерофілії на різних типах графів, наприклад, гетерогенних графах, темпоральних графах та гіперграфах. Крім того, виявлено, що численні графові застосування тісно пов'язані з проблемою гетерофілії, наприклад, виявлення шахрайства/аномалій на графах, змагальні атаки на графах та стійкість, конфіденційність, федеративне навчання та сегментація хмар точок, кластеризація графів, рекомендаційні системи, генеративні моделі, прогнозування зв'язків, класифікація графів та розмальовування, тощо. Протягом останніх кількох років значні зусилля були спрямовані на вивчення та вирішення проблеми гетерофілії в графовому навчанні.

Застосування

Згортання білка

Графові нейронні мережі є одним з основних будівельних блоків AlphaFold, програми штучного інтелекту, розробленої Google's DeepMind для вирішення проблеми згортання білка в біології. AlphaFold посіла перше місце в кількох конкурсах CASP.

Соціальні мережі

Соціальні мережі є основним доменом застосування для ГНМ через їх природне представлення у вигляді соціальних графів. ГНМ використовуються для розробки рекомендаційних систем, заснованих як на соціальних відносинах, так і на відносинах між об'єктами.

Комбінаторна оптимізація

ГНМ використовуються як фундаментальні будівельні блоки для кількох алгоритмів комбінаторної оптимізації. Приклади включають обчислення найкоротших шляхів або ейлерових циклів для даного графа, виведення розміщень кристалів кращих або конкурентних порівняно з рішеннями, створеними людиною, та покращення розроблених експертами правил розгалуження в методі гілок і меж.

Кібербезпека

При розгляді як графа, мережа комп'ютерів може бути проаналізована за допомогою ГНМ для виявлення аномалій. Аномалії в графах походження часто корелюють зі зловмисною діяльністю всередині мережі. ГНМ використовувалися для ідентифікації цих аномалій на окремих вершинах та в шляхах для виявлення зловмисних процесів, або на рівні ребер для виявлення бічного переміщення в мережі.

Водорозподільні мережі

Системи водорозподілу можуть бути змодельовані як графи, що робить їх прямим застосуванням ГНМ. Цей вид алгоритмів застосовувався для прогнозування попиту на воду, з'єднуючи районні облікові зони (DMAs) для підвищення прогностичної здатності. Іншим застосуванням цього алгоритму у моделюванні водорозподілу є розробка метамоделей.

Комп'ютерний зір

Щоб представити зображення як графову структуру, зображення спочатку ділиться на кілька сегментів (patches), кожен з яких розглядається як вершина в графі. Ребра потім формуються шляхом з'єднання кожної вершини з її найближчими сусідами на основі просторової подібності або подібності ознак. Це графове представлення уможливлює застосування моделей графового навчання до візуальних завдань. Реляційна структура допомагає покращити виділення ознак та підвищити продуктивність у задачах розуміння зображень.

Текст та НЛП

Графове представлення тексту допомагає захопити глибші семантичні зв'язки між словами. Багато досліджень використовували графові мережі для підвищення продуктивності в різних завданнях обробки тексту, таких як класифікація тексту, відповіді на запитання, нейронний машинний переклад (NMT), виділення подій, перевірка фактів тощо.

Примітки

Зовнішні посилання A Gentle Introduction to Graph Neural Networks