Обзор графовой нейронной сети Третий пункт: обзор GNN от IEEE Fellow

Графическая нейронная сетьПопулярность (GNN) продолжает расти Ранее мы представили две обзорные статьи из Университета Цинхуа, см.:Графовые модели в эпоху глубокого обучения, Цинхуа опубликовал обзор графовых сетей,иОбзор графовых нейронных сетей в Университете Цинхуа: модели и приложения. Недавно научный сотрудник IEEE, старший член и член Zonghan Wu опубликовал еще одну обзорную статью о графовых нейронных сетях. В этой статье представлены базовые знания, история развития, классификация и структура, приложения и т. д. GNN, а также подробно представлены различные модели и методы, включая формулы, диаграммы моделей, алгоритмы и т. д., и я надеюсь, что она будет полезна для всех. .

введение

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

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

Сложность графических данных создает серьезные проблемы для существующих алгоритмов машинного обучения, поскольку графические данные нерегулярны. Размер каждого графа разный, узлы расположены не по порядку, и каждый узел в графе имеет разное количество смежных узлов, из-за чего некоторые важные операции (такие как свертка), которые легко вычислить на изображении, больше не могут быть выполнены. применяется непосредственно к графику. Кроме того, основным предположением существующих алгоритмов машинного обучения является то, что экземпляры независимы друг от друга. Однако каждый экземпляр в данных графа связан с другими экземплярами вокруг него и содержит некоторую сложную информацию о связях для фиксации зависимостей между данными, включая ссылки, дружеские отношения и взаимодействия.

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

Краткая история графовых нейронных сетей

Концепция графовых нейронных сетей была впервые предложена Гори и др. (2005) [16] и дополнительно разъяснена Скарселли и др. (2009) [17]. В этих ранних исследованиях изучалось представление целевых узлов путем итеративного распространения информации о соседях через рекуррентные нейронные архитектуры до тех пор, пока не была достигнута стабильная фиксированная точка. Этот процесс требует значительных вычислительных ресурсов, и решению этой проблемы посвящено множество недавних исследований. В этой статье графовые нейронные сети представляют все методы глубокого обучения для графовых данных.

Вдохновленный большим успехом сверточных сетей в компьютерном зрении, недавно появился ряд подходов, которые переопределяют концепцию свертки для графических данных. Эти методы относятся к категории графовых сверточных сетей (GCN). Первое крупное исследование сверточных сетей графов было представлено Бруной и др. (2013), которые разработали вариант свертки графов на основе теории спектральных графов. С тех пор сверточные сети графов на основе спектра постоянно улучшались, расширялись и совершенствовались. Сверточные сети на основе пространственных графов начали быстро развиваться, поскольку спектральные методы обычно обрабатывают весь граф одновременно и их трудно распараллелить или масштабировать до больших графов. Эти методы выполняют свертку непосредственно в структуре графа, агрегируя информацию о соседних узлах. В сочетании со стратегией выборки вычисления могут выполняться на пакете узлов, а не на всем графе, что обещает повысить эффективность.

Помимо графовых сверточных сетей, в последние годы было разработано множество альтернативных графовых нейронных сетей. Эти методы включают сети внимания к графам (GAT), автокодировщики графов, сети генерации графов и пространственно-временные сети графов. Подробная информация о классификации этих методов подробно описана в главе 3.

Исследование, связанное с графической нейронной сетью. Бронштейн и др. описывают методы глубокого обучения в неевклидовых областях, включая графы и многообразия, с использованием глубокого обучения в символической геометрии. Хотя это первый обзор графовых сверточных сетей, в нем не учитываются несколько важных пространственных подходов, в том числе [15], [19], [24], [26], [27], [28]. обновляется с использованием самых современных тестов. Кроме того, в этот обзор не вошли многие недавно разработанные архитектуры, которые не менее важны, чем графовые сверточные сети.

В другом исследовании Батталья и др. [29] позиционировали графовые сети как строительные блоки для обучения на основе реляционных данных и рассмотрели некоторые графовые нейронные сети в рамках единой структуры. Тем не менее, их общая структура очень абстрактна, теряя понимание каждого метода в исходной статье. Ли и др. [30] провели частичный обзор графовых моделей внимания, типа графовой нейронной сети. Недавно Чжан и др. [31] представили современный обзор по глубокому обучению графов, игнорируя исследования сетей, генерирующих графы, и пространственно-временных сетей графов. В заключение, ни одно из существующих исследований не дает всестороннего обзора графовых нейронных сетей, охватывая только часть графовых сверточных нейронных сетей и изучая ограниченные исследования, таким образом опуская последние достижения в альтернативах графовых нейронных сетей, таких как графовые генерирующие сети и графовое пространство-время. сеть.

Графические нейронные сети и сетевые встраивания. Исследования графовых нейронных сетей тесно связаны с внедрением графов или сетей, что также вызывает растущий интерес в сообществах интеллектуального анализа данных и машинного обучения [32], [33], [34], [35], [36], [37]. ]. Встраивание сети направлено на представление вершин сети в низкоразмерном векторном пространстве путем сохранения архитектуры топологии сети и информации о содержании узла, чтобы любые последующие задачи анализа графа, такие как классификация, кластеризация и рекомендации, могли быть изучены с помощью простых готовых Машинные алгоритмы, такие как машины опорных векторов для классификации, легко выполняются. Многие алгоритмы встраивания в сеть не контролируются, и их можно разделить на три группы [32], а именно: матричная факторизация [38], [39], случайные блуждания [40] и методы глубокого обучения. Методы глубокого обучения для встраивания в сеть также относятся к графовым нейронным сетям, включая алгоритмы на основе графового автоэнкодера (такие как DNGR [41] и SDNE [42]) и сверточные графовые нейронные сети с неконтролируемым обучением (такие как GraphSage [двадцать четыре]). На рисунке 2 показана разница между сетевыми вложениями и графовыми нейронными сетями в этой статье.

Вклад этой статьи заключается в следующем:

• Новая система классификации: учитывая растущее количество исследований глубокого обучения на данных графа, мы предлагаем новую систему классификации нейронной сети графа (GNN). В соответствии с этой системой классификации GNN делятся на 5 категорий: сверточные сети графа, сети внимания графа, автокодировщики графа, сети генерации графа и пространственно-временные сети графа. Мы определяем разницу между графовыми нейронными сетями и сетевыми встраиваниями и проводим связи между различными архитектурами графовых нейронных сетей.

• Всесторонний обзор. В этом обзоре представлен всесторонний обзор современных методов глубокого обучения графических данных. Для каждого типа графовой нейронной сети мы предоставляем подробное описание алгоритма характеристики, а также делаем необходимые сравнения и сводку соответствующих алгоритмов.

• Обширные ресурсы. В этом обзоре представлены обширные ресурсы для графовых нейронных сетей, включая современные алгоритмы, эталонные наборы данных, открытый исходный код и практические приложения. Этот обзор может служить практическим руководством для понимания, использования и разработки методов глубокого обучения для различных практических приложений.

• Будущие направления: в этом обзоре также подчеркиваются текущие ограничения существующих алгоритмов и указываются возможные будущие направления для этой быстро развивающейся области.

Диссертация: Всесторонний обзор графовых нейронных сетей

Ссылка на статью: https://arxiv.org/pdf/1901.00596v1.pdf

Резюме: В последние годы изклассификация изображенийк обработке видео кРаспознавание речиА обработка естественного языка и глубокое обучение произвели революцию в некоторых задачах машинного обучения. Данные в этих задачах обычно представляются в евклидовом пространстве. Однако все больше и больше приложений используют данные, сгенерированные из неевклидовых областей, и представляют их в виде графов со сложными отношениями и взаимозависимостями. Хотя сложность графических данных создает серьезные проблемы для существующих алгоритмов машинного обучения, многие недавние исследования начали распространять методы глубокого обучения на графические данные.

В этой статье рассматриваютсясбор данныхи Graph Neural Networks (GNN) в области машинного обучения, а также классифицирует последние достижения в Graph Neural Networks в соответствии с новыми методами. Сосредоточив внимание на сверточных сетях графов, они также рассматривают другие недавно разработанные архитектуры, такие как сети внимания графов, автокодировщики графов, сети генерации графов и пространственно-временные сети графов. Далее мы обсудим применение графовых нейронных сетей в нескольких областях и обобщим открытые исходные коды и тесты существующих алгоритмов для различных задач обучения. Наконец, мы предлагаем направления исследований в этой быстро развивающейся области.

2. Определения

В этом разделе мы даем определения основных понятий графа. Для удобства запроса мы суммируем часто используемые символы в таблице 1.

3. Классификация и структура

В этой части представлен метод классификации графовой нейронной сети. Мы рассмотрели все модели дифференцируемых графов, которые можно объединить с нейронными архитектурами в графовые нейронные сети, и, наконец, классифицировали графовые нейронные сети на: графовые сверточные сети, графовые сети внимания, графовые автоэнкодеры, графовые генерирующие сети и графово-пространственно-временные сети. Среди этих сетей сверточные сети графов играют центральную роль в захвате архитектурных зависимостей. Как показано на рисунке 3 ниже, методы, принадлежащие к другим категориям, используют в качестве основы графовые сверточные сети. В таблице 2 приведены репрезентативные методы для каждой категории.

На рисунке 4 ниже показан процесс изучения представления узла в графовой сверточной сети.

На рисунке 5 ниже показано несколько графовых моделей нейронных сетей, построенных на GCN.

На рисунке ниже показана разница между сверточными сетями графа и сетями внимания графа в агрегировании информации от соседних узлов.

3.2 Структура

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

• Полууправляемое обучение для классификации на уровне узлов. Учитывая единую сеть, в которой некоторые узлы помечены, графовые сверточные сети могут обучаться надежной модели, которая эффективно распознает метки классов непомеченных узлов [14]. С этой целью можно построить сквозную структуру для многоклассовой классификации путем объединения ряда сверточных слоев графа и слоев softmax.

• Контролируемое обучение для классификации на уровне графа. Учитывая набор графовых данных, классификация на уровне графа направлена ​​на предсказание меток классов для всего графа [55], [56], [74], [75]. Сквозное обучение для этой задачи может быть достигнуто с помощью структуры, которая сочетает сверточные слои графа и этапы объединения [55], [56].

• Неконтролируемое обучение вложений графов. Если метки классов недоступны в графе, мы можем изучить вложения графа полностью без присмотра в сквозной среде. Эти алгоритмы используют информацию на уровне границ двумя способами. Простой подход заключается в использовании структуры автоэнкодера, где кодировщик использует слои свертки графа для встраивания графа в скрытые представления, а затем использует декодер для восстановления структуры графа [59], [61]. Другой метод заключается в использовании метода отрицательной выборки для выборки некоторых пар узлов в качестве отрицательных пар и существующих узлов в графе в качестве положительных пар. Затем после сверточного слоя применяется слой логистической регрессии для сквозного обучения [24].

4. Граф сверточных сетей

В этой главе представлен обзор графовых сверточных сетей (GCN), которые являются основой многих сложных моделей графовых нейронных сетей. Методы GCN делятся на две категории: спектральные и пространственные. Спектральные методы определяют свертку графа, вводя фильтры с точки зрения обработки сигнала графа, где операции свертки графа интерпретируются как удаление шума из сигналов графа [76]. Пространственные методы характеризуют свертку графа как агрегирование информации об объектах от соседей. В то время как GCN работает на уровне узла, модули объединения графов могут чередоваться со слоями GCN, чтобы разбить граф на высокоуровневые подструктуры. Как показано на рис. 5а, этот архитектурный проект можно использовать для извлечения представлений на уровне графа и выполнения задач классификации графов. Космические модули GCN и объединения графов будут представлены ниже отдельно.

В разделе GCN, основанном на спектрах, представлены его предыстория, методы и т. Д., К которым относятся Spectral CNN, Chebyshev Spectral CNN (ChebNet), ChebNet первого порядка (1stChebNet) и Adaptive Graph Convolution Network (AGCN).

Пространственные GCN делятся на две категории: рекуррентные пространственные GCN и пространственные GCN на основе композиции. Первые включают графовые нейронные сети (GNN), закрытые графовые нейронные сети (GGNN) и стохастическое стационарное встраивание (SSE). Последний включает в себя: нейронные сети передачи сообщений (MPNN), GraphSage. Кроме того, в этом разделе представлены пространственные варианты GCN за пределами этих двух широких категорий, включая нейронные сети диффузионной свертки (DCNN), PATCHY-SAN, крупномасштабные сети графовой свертки (LGCN), сеть смешанной модели (MoNet).

В этой главе также сравниваются спектральные GCN и пространственные GCN с точки зрения эффективности, универсальности и гибкости, утверждая, что пространственные GCN имеют больше преимуществ и, таким образом, вызывают больший исследовательский интерес.

5 моделей помимо графовых сверточных сетей

В этом разделе представлен обзор других нейронных сетей графов, помимо сверточных сетей графов, включая нейронные сети внимания графов, автокодировщики графов, модели генерации графов и пространственно-временные сети графов. В таблице ниже приведены основные методы по каждой категории.

5.1 График сети внимания

Механизмы внимания стали почти стандартными в последовательных задачах. Его ценность заключается в возможности сосредоточиться на наиболее важных частях объекта. Этот механизм доказал свою полезность во многих задачах, таких как машинный перевод и понимание естественного языка. Из-за увеличения возможностей модели механизмов внимания графовые нейронные сети могут извлечь большую пользу из механизмов внимания при агрегировании информации, интеграции выходных данных нескольких моделей и создании случайных блужданий, ориентированных на важность.

В этой части представлены различные методы сети графического внимания, в том числе сеть графического внимания (GAT), закрытая сеть внимания (GAAN), графическая модель внимания (GAM), обходы внимания.

Вклад механизма внимания в нейронную сеть графа состоит из трех частей, а именно: присвоение весов внимания разным соседям при агрегировании информации об объектах, интеграция нескольких моделей в соответствии с весами внимания и использование весов внимания для управления случайными блужданиями. Хотя мы классифицируем GAT и GAAN как два подхода к сетям графического внимания, они оба могут использоваться в качестве пространственных сверточных сетей. Преимущество обоих состоит в том, что они могут адаптивно изучать веса важности соседей (как показано на рис. 6). Однако, поскольку мы должны вычислять веса внимания между каждой парой ближайших соседей, вычислительные затраты и потребление памяти быстро растут.

5.2 Автокодировщики графиков

Автоэнкодеры графов — это класс методов встраивания сети, целью которых является представление вершин сети в низкоразмерных векторных пространствах с помощью архитектур нейронных сетей. Типичным решением является использование многослойного персептрона в качестве кодера для получения вложений узлов и декодера для восстановления статистики соседей узла, такой как положительная поточечная взаимная информация (PPMI) или близость первого и второго порядка (близости). 42]. Недавно исследователи пытались использовать GCN в качестве кодировщика, комбинируя GCN и GAN или комбинируя LSTM и GAN при разработке автокодировщиков графов.

В этом разделе представлены автокодировщики на основе GCN и другие варианты. В разделе автокодировщика на основе GCN представлены: автокодировщик графов (GAE), автокодировщик состязательно регуляризованных графов (ARGA). Другие варианты включают: сетевые представления с состязательно регуляризованными автоэнкодерами (NetRA), глубокие нейронные сети для представлений графов (DNGR), структурированные вложения в глубокие сети (структурные вложения в глубокие сети, SDNE), встраивание в глубокие рекурсивные сети (DRNE).

DNGR и SDNE изучают вложения узлов только на основе топологии, в то время как GAE, ARGA, NetRA и DRNE должны изучать вложения узлов на основе информации о топологии и характеристиках содержимого узла. Одной из проблем автокодировщиков графов является разреженность матрицы смежности, из-за которой у декодера гораздо меньше положительных элементов, чем отрицательных. Чтобы решить эту проблему, DNGR восстанавливает более плотную матрицу, матрицу PPMI, SDNE наказывает нулевые элементы матрицы смежности, GAE повторно взвешивает элементы в матрице смежности, а NetRA линеаризует граф в последовательность.

5.3 Сеть генерации графов

Целью сети генерации графов является создание графа на основе набора наблюдаемых графов. Многие из этих методов специфичны для предметной области. Например, при генерации молекулярных графов некоторые исследования моделируют представление молекулярных графов в виде строк SMILES [94], [95], [96], [97]. При обработке естественного языка для создания семантического графа или графа знаний обычно требуется заданное предложение [98], [99]. Недавно исследователи предложили несколько общих методов. В одних исследованиях генеративный процесс рассматривается как формирование узлов или ребер [64], [65], а в других используется генеративно-состязательное обучение [66], [67]. Подходы в этой области либо используют GCN в качестве строительных блоков, либо используют другую архитектуру.

В этом разделе представлены сети генерации графов на основе GCN и другие сети генерации графов. Первый включает в себя: Молекулярно-генеративные состязательные сети (MolGAN) и Глубокие генеративные модели графов (DGMG); последний включает GraphRNN (использующий двухэтапную рекуррентную нейронную сеть для создания моделей с использованием карт глубины) и NetGAN (объединение LSTM и Wasserstein GAN для генерировать графики из методов, основанных на случайном блуждании).

5.4 Граф пространственно-временных сетей

Пространственно-временные сети графов охватывают как временные, так и пространственные зависимости пространственно-временных графов. Пространственно-временной граф имеет глобальную структуру графа, и входные данные каждого узла меняются с течением времени. Например, в дорожной сети каждый датчик используется как узел для непрерывной регистрации скорости транспортного потока на определенной дороге, где границы дорожной сети определяются расстоянием между парами датчиков. Целью пространственно-временной сети графа является предсказание будущих значений узлов или меток или предсказание пространственно-временных меток графа. Недавние исследования изучали использование только GCN, комбинируя GCN и RNN или CNN, а также рекуррентные архитектуры, предназначенные для графовых структур.

В этом разделе представлены графовые пространственно-временные сети на основе GCN и другие графовые пространственно-временные сети. К первым относятся: диффузионная сверточная рекуррентная нейронная сеть (DCRNN), CNN-GCN и пространственно-временная GCN (ST-GCN). Другими подходами являются Structural-RNN, повторяющаяся структура структурирования.

Преимущество DCRNN заключается в ее способности обрабатывать долгосрочные зависимости благодаря повторяющейся сетевой архитектуре. Хотя CNN-GCN немного проще, чем DCRNN, CNN-GCN может более эффективно обрабатывать пространственно-временные графики благодаря быстрой реализации 1D CNN. Пространственно-временной GCN рассматривает временной поток как ребра графа, что приводит к квадратичному росту размера матрицы смежности. С одной стороны, это увеличивает вычислительные затраты на сверточные слои графа. С другой стороны, чтобы зафиксировать долгосрочные зависимости, сверточные слои графа должны быть сложены несколько раз. StructuralRNN использует одну и ту же RNN в одной и той же семантической группе, что повышает эффективность модели, но StructuralRNN требует предварительных знаний человека для сегментации семантической группы.

6 приложений

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

6.1 Наборы данных

6.2 Эталонные тесты и реализации с открытым исходным кодом

6.3 Практические случаи применения

В этой статье представлены приложения GNN по областям, включая компьютерное зрение, рекомендательные системы, транспорт, химию и многое другое.

7 будущих направлений

Углубить сеть. Успех глубокого обучения заключается в глубоких нейронных архитектурах. Например, в классификации изображений модель ResNet имеет 152 слоя. Но в графовых сетях эмпирические исследования показали, что производительность модели резко падает по мере увеличения количества сетевых слоев [147]. Согласно статье [147], это связано с эффектом свертки графа, так как она существенно сближает представления соседних узлов, поэтому теоретически при бесконечных свертках представления всех узлов будут сходиться к точке. Это приводит к вопросу: является ли углубление сети по-прежнему хорошей стратегией для изучения графоструктурированных данных?

рецептивное поле. Рецептивное поле узла относится к группе узлов, включая центральный узел и его соседей. Количество соседей (узлов) узла подчиняется степенному закону распределения. Некоторые узлы могут иметь только одного соседа, в то время как другие могут иметь тысячи соседей. Несмотря на стратегии выборки [24], [26], [27], еще предстоит изучить, как выбрать репрезентативные рецептивные поля узлов.

Масштабируемость. Большинство графовых нейронных сетей плохо масштабируются для больших графов. Основная причина заключается в том, что при наложении нескольких слоев свертки графа конечное состояние узла включает в себя скрытые состояния большого числа его соседей, что очень усложняет обратное распространение. Хотя некоторые подходы пытаются повысить эффективность модели за счет быстрой выборки и обучения подграфов [24], [27], они по-прежнему не могут масштабироваться до глубоких архитектур для больших графов.

динамичность и неоднородность. Большинство современных графовых нейронных сетей имеют дело со статическими однородными графами. С одной стороны, предполагается, что графовая архитектура фиксирована. С другой стороны, предполагается, что узлы и ребра графа происходят из одного и того же источника. Однако во многих случаях эти два предположения нереалистичны. В социальной сети в любой момент может присоединиться новый человек, а также выйти из социальной сети человек, существовавший ранее. В рекомендательной системе продукты могут быть разных типов, и их вывод может быть в разных формах, может быть текст, может быть изображения. Следовательно, необходимо разработать новые методы для работы с динамическими и гетерогенными структурами графов.