Графические нейронные сети пользуются все большим успехом, но что они собой представляют на самом деле? Как они работают? Давайте вместе посмотрим на графики в этих историях! Сегодня: основополагающая статья Скарселли о графической нейронной сети



Присоединяйтесь к Medium по моей реферальной ссылке - Стефано Бозисио
Как участник Medium, часть вашего членского взноса идет писателям, которых вы читаете, и вы получаете полный доступ ко всем историям ... medium.com



Данные часто легко визуализировать и интерпретировать в виде графиков. Графики помогают находить скрытые ответы среди сложных шаблонов, а также проливают свет на лежащие в основе отношения между точками данных. Таким образом, неудивительно, что графические приложения распространены повсеместно: от анализа социальных сетей [1–5] до нейробиологии [6,7], ранжирования страниц [8–10], теории кратчайшего пути [11–14] и химии [15]. –19].

С 2006 года теория графов вошла в тесный контакт с машинным обучением с новой концепцией приложений Graph Neural Networks. Самое первое предложение было опубликовано в 2006 г. Скарселли и Гори [20] и впоследствии обобщено в 2008 г. [21] в статье «Модель графической нейронной сети». Здесь авторы заложили математические основы современной графической нейронной сети. С тех пор в литературе наблюдались всплески в работах по графическому машинному обучению [22–28], которые заставляли мир графов все больше и больше развиваться, более точно определяя, каковы ключевые элементы этих математических структур и как связать их с более совершенными алгоритмами машинного обучения. .

Я думаю, что каждая статья о теории графов и машинном обучении - это приключение, в котором авторы устанавливают свою номенклатуру и математическое развитие. Таким образом, я хотел начать эту серию руководств по графам, чтобы дать простое объяснение с математической строгостью и вычислительными примерами на Python. Сегодня мы начнем это путешествие с основной статьи Скарселли «Модель графической нейронной сети». Начнем!

Модель графической нейронной сети

Определения

Графическая нейронная сеть (GNN) происходит от двух методов машинного обучения: рекурсивной нейронной сети (RNN) [30–32] и цепей Маркова [33–35], где лежащие в основе Идея состоит в том, чтобы кодировать данные с помощью графа, используя отношения между узлами. В частности, подход RNN ориентирован на графы, когда цель пользователя - пометить данный граф после обучения с помеченными графами. Подход с использованием цепей Маркова ориентирован на узлы, когда каждый узел помечен, и пользователь ищет прогнозы на уровне узла. Модель GNN инкапсулирует уроки из этих предыдущих моделей и подходит как для приложений, ориентированных на графы, так и для узлов.

Кроме того, GNN обобщает вычисления на основе графов для обработки как симметричных, так и асимметричных графиков, рис.1. Граф определяется симметричным, если его свойства среди узлов не меняются после изменения положений узлов, а именно вы всегда получаете один и тот же график. Напротив, в асимметричном графе порядок очень важен, поскольку различные графы могут быть получены путем перетасовки позиций узлов. В случае асимметричности пара узлов определяет ребро, которое называется дугой, а граф называется направленным, а именно, он имеет определенное направление.

Вычислительная проницательность

Что касается вычислительных графов, каждый узел обогащен некоторыми атрибутами, собранными в метку. Метка - это вектор с предопределенной размерностью, который кодирует характеристики, описывающие каждый узел (например, средний цвет пикселя в изображении, форму объекта и т. Д.) И отношения между узлами - краями (например, расстояние между интересующими точками. в распознавании изображений и т. д.). Учитывая основные условия функций, структура графа заметно отличается от простой нейронной сети. Действительно, каждый узел мог знать, что происходит в его окрестностях, и мог видеть текущее состояние (или особенности) соседнего узла (рис. 2).

Таким образом, можно определить график как математический объект. Каждый узел имеет определенное состояние x ₙ, которое содержит свойства узлов, а также свойства соседей. Кроме того, с каждым узлом связана функция локального перехода f𝓌, которая моделирует зависимость функций x ₙ от контекста узла n и функция локального вывода g𝓌, которая описывает, как производится вывод для каждого узла.

Пока все хорошо, но при работе с f𝓌 возникают проблемы. Может быть переменное количество аргументов в зависимости от размера соседства или когда набор соседей не упорядочен. Следовательно, f𝓌. должен быть инвариантным к перестановке узлов в окрестности. Чтобы удовлетворить это математическое и техническое ограничение, можно обобщить f𝓌 как функцию h𝓌. Эта последняя функция перехода инвариантна к положениям узлов и количеству узлов в графе и зависит от заданной метки дуги между узлами n и u

Требование: теорема Банаха о неподвижной точке

После определения основных функций и структуры графа необходимо вычисление состояния x ₙ - нам нужно определить a. Суть трактовки вычислений GNN Скарселли - это теорема Банаха о неподвижной точке. Теорема Банаха о неподвижной точке также называется c теоремой об отображении притяжения. Эта теорема устанавливает существование и единственность неподвижной точки в заданном метрическом пространстве для функции сжимающего отображения. Что это значит?

  • Неподвижная точка в математике - это решение для заданной функции F, а именно, когда функция является тождественной
  • Затем рассмотрите понятие расстояния, а именно то, насколько две точки a и b находятся далеко друг от друга. Учитывая набор чисел X, можно вычислить расстояние между этими точками. Меры расстояния определяют новое пространство, называемое метрическим пространством, которое представлено набором X и результатом функции расстояния (X, d)
  • Теперь в этом метрическом пространстве у нас может быть математическая функция F, которую можно применить к точкам a и b для получения другой меры. Если расстояние между полученными точками F (a) и F (b) меньше реального расстояния между a и b , F - это карта сжатия.
  • Если F - сжимающееся отображение, то Банах доказал, что для такой функции существует решение с неподвижной точкой

Следствием такой теоремы является то, что можно вычислить текущее состояние узлов с помощью итерационной схемы. Можно сказать, что в основном состояния узлов обновляются каждый раз, чтобы найти нужную метку.

На данный момент мы почти готовы перейти к стадии производства. Однако какие функции должны быть у нас, чтобы f𝓌 / h𝓌 и g𝓌 удовлетворяли теореме Банаха о неподвижной точке? Сюрприз, сюрприз, вот вторая важная часть GNN: эти функции могут быть простыми многослойными перцептронами (MLP). Действительно, MLP может использовать универсальную теорию приближений, поэтому они удовлетворяют требованиям Банаха. Первоначально каждое устройство инициировало случайные состояния. Функции f𝓌 / h𝓌 будут обновлять эти состояния до тех пор, пока не будет достигнута сходимость, а именно, когда будет найдено решение с фиксированной точкой. Затем можно продолжить окончательное вычисление MLP с помощью g𝓌, который, в свою очередь, вернет прогноз вывода для каждого узла или для самого графа.

Теперь, когда мы теоретически увидели, как работает GNN, следите за следующей публикацией, где мы будем реализовывать GNN в вычислительном отношении!

Если у вас возникнут вопросы или комментарии, присылайте мне электронное письмо по адресу [email protected] или прямо здесь, в Medium.

БИБЛИОГРАФИЯ

  1. Айзопос, Фотис, Джордж Пападакис и Теодора Варваригу. «Анализ тональности контента в социальных сетях с использованием n-граммовых графиков». Материалы 3-го международного семинара ACM SIGMM по социальным сетям. 2011 г.
  2. Кэмпбелл, Уильям М., Чарли К. Дагли и Клиффорд Дж. Вайнштейн. «Анализ социальных сетей с помощью контента и графиков». Lincoln Laboratory Journal 20.1 (2013): 61–81.
  3. Коган, Питер и др. «Реконструкция и анализ графиков разговоров в твиттере». Материалы первого международного семинара ACM по актуальным темам междисциплинарных исследований социальных сетей. 2012 г.
  4. Амати, Джамбаттиста и др. «TWITTER АНАЛИЗ ВРЕМЕННОЙ ЭВОЛЮЦИИ: СРАВНЕНИЕ ГРАФИКОВ СОБЫТИЙ И ТЕМАТИЧЕСКИХ РЕТВИТОВ». Международный журнал IADIS по компьютерным наукам и информационным системам 11.2 (2016 г.).
  5. Росси, Эмануэле и др. «Сети временных графов для глубокого обучения на динамических графах». Препринт arXiv arXiv: 2006.10637 (2020).
  6. Бассетт, Даниэль С., Перри Зурн и Джошуа И. Голд. «О природе и использовании моделей в сетевой нейробиологии». Nature Reviews Neuroscience 19.9 (2018): 566–578.
  7. Sporns, Олаф. «Методы теории графов: приложения в мозговых сетях». Диалоги в клинической нейробиологии 20,2 (2018): 111.
  8. Абедин, Бабак и Бабак Сохраби. «Приложение теории графов и ранжирование веб-страниц для улучшения структуры ссылок веб-сайта». Поведение и информационные технологии 28.1 (2009): 63–72.
  9. Мегхабхаб, Джордж. «Рейтинг веб-страниц Google применяется к различным топологическим структурам веб-графов». Журнал Американского общества информационных наук и технологий 52.9 (2001): 736–747.
  10. Скарселли, Франко и др. «Графические нейронные сети для ранжирования веб-страниц». Международная конференция по веб-аналитике IEEE / WIC / ACM 2005 г. (WI’05). IEEE, 2005.
  11. Голдберг, Эндрю В. и Крис Харрельсон. «Вычисление кратчайшего пути: поиск соответствует теории графов». СОДА. Vol. 5. 2005.
  12. Галло, Джорджио и Стефано Паллоттино. «Алгоритмы кратчайшего пути». Летопись операционных исследований 13.1 (1988): 1–79.
  13. Боргвардт, Карстен М. и Ханс-Петер Кригель. «Ядра кратчайшего пути на графах». Пятая международная конференция IEEE по интеллектуальному анализу данных (ICDM’05). IEEE, 2005.
  14. Хэдлок, Ф. О. «Алгоритм кратчайшего пути для сеточных графов». Сети 7.4 (1977): 323–334.
  15. Балабан, Александру Т. «Приложения теории графов в химии». Журнал химической информации и компьютерных наук 25.3 (1985): 334–343.
  16. Vergniory, M. G., et al. «Данные теории графов для топологической квантовой химии». Physical Review E 96.2 (2017): 023310.
  17. Брэдлин, Барри и др. «Связность зон для топологической квантовой химии: зонные структуры как проблема теории графов». Physical Review B 97.3 (2018): 035138.
  18. Коли, Коннор В. и др. «Графо-сверточная модель нейронной сети для прогнозирования химической реактивности». Химическая наука 10.2 (2019): 370–377.
  19. Тан, Боуэн и др. «Нейронная сеть передачи сообщений на основе самовнимания для прогнозирования молекулярной липофильности и растворимости в воде». Журнал хеминформатики 12.1 (2020): 1–9.
  20. Скарселли, Франко и др. «Графические нейронные сети для ранжирования веб-страниц». Международная конференция по веб-аналитике IEEE / WIC / ACM 2005 г. (WI’05). IEEE, 2005.
  21. Скарселли, Франко и др. «Модель нейронной сети графа». Транзакции IEEE в нейронных сетях 20.1 (2008): 61–80.
  22. Пероцци, Брайан, Рами Аль-Рфу и Стивен Скиена. «Deepwalk: онлайн-обучение социальных представлений». Материалы 20-й международной конференции ACM SIGKDD по обнаружению знаний и интеллектуальному анализу данных. 2014 г.
  23. Ли, Юджиа и др. «Нейронные сети с последовательностью стробированных графов». Препринт arXiv arXiv: 1511.05493 (2015).
  24. Гилмер, Джастин и др. «Передача нейронных сообщений для квантовой химии». Международная конференция по машинному обучению. ПМЛР, 2017.
  25. Кипф, Томас Н. и Макс Веллинг. «Классификация с полууправлением со сверточными сетями на графах». Препринт arXiv arXiv: 1609.02907 (2016).
  26. Ву, Феликс и др. «Упрощение сверточных сетей на графах». Международная конференция по машинному обучению. ПМЛР, 2019.
  27. Гамильтон, Уильям Л., Рекс Инь и Юре Лесковец. «Обучение индуктивному представлению на больших графах». Труды 31-й Международной конференции по системам обработки нейронной информации. 2017 г.
  28. Батталья, Питер В. и др. «Реляционные индуктивные предубеждения, глубокое обучение и сети на графах». Препринт arXiv arXiv: 1806.01261 ​​ (2018).
  29. Закари, Уэйн В. «Модель информационного потока для конфликта и разделения в малых группах». Журнал антропологических исследований 33.4 (1977): 452–473.
  30. Фраскони, Паоло, Марко Гори и Алессандро Спердути. «Общая основа для адаптивной обработки структур данных». Транзакции IEEE в нейронных сетях 9.5 (1998): 768–786.
  31. Спердути, Алессандро и Антонина Старита. «Контролируемые нейронные сети для классификации структур». Транзакции IEEE в нейронных сетях 8.3 (1997): 714–735.
  32. Хагенбухнер, Маркус, Алессандро Спердути и А Чунг Цой. «Самоорганизующаяся карта для адаптивной обработки структурированных данных». Транзакции IEEE в нейронных сетях 14.3 (2003): 491–505.
  33. Брин, Сергей и Лоуренс Пейдж. «Анатомия крупномасштабной гипертекстовой поисковой системы». Компьютерные сети и системы ISDN 30.1–7 (1998): 107–117.
  34. Кляйнберг, Джон М. «Авторитетные источники в среде с гиперссылками». СОДА. Vol. 98. 1998.
  35. Цой, А Чанг и др. «Адаптивное ранжирование веб-страниц». Материалы 12-й международной конференции по всемирной паутине. 2003 г.