Понять, что такое GNN и что она может делать

Графическая нейронная сеть (GNN) в последнее время привлекла большое внимание из-за ее способности анализировать структурные данные графов. Эта статья дает краткое введение в графическую нейронную сеть. Он охватывает некоторые теории графов для облегчения понимания графов и проблем анализа графов. Затем он представляет графическую нейронную сеть в различных формах и их принципах. В нем также рассказывается о возможностях GNN и некоторых приложениях GNN.

Теория графов

Во-первых, нам нужно знать, что такое граф.

Граф - это структура данных, состоящая из двух компонентов: вершин и ребер. Он используется как математическая структура для анализа парных отношений между объектами и сущностями. Обычно граф определяется как G = (V, E), где V - это набор узлов, а E - грани между ними. .

Граф часто представлен матрицей смежности A. Если граф имеет N узлов, то A имеет размер (N x N). Иногда люди предоставляют другую матрицу признаков для описания узлов на графике. Если каждый узел имеет F количество элементов, тогда матрица функций X имеет размер (N x F ).

Почему сложно анализировать график?

Во-первых, графа не существует в евклидовом пространстве, а это значит, что он не может быть представлен никакими системами координат, с которыми мы знакомы. Это значительно усложняет интерпретацию графических данных по сравнению с другими типами данных, такими как волны, изображения или сигналы временных рядов («текст» также можно рассматривать как временные ряды), которые можно легко сопоставить с 2- D или трехмерное евклидово пространство.

Во-вторых, граф не имеет фиксированной формы. Почему? Посмотрите на пример ниже. График (A) и график (B) имеют совершенно разную структуру и визуально различаются. Но когда мы преобразуем его в представление матрицы смежности, два графа имеют одинаковую матрицу смежности (если не учитывать вес ребер). Итак, следует ли считать эти два графика одинаковыми или разными?

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

Зачем нужны графики?

Причины, по которым люди предпочитают работать с графиками, можно резюмировать в нескольких пунктах, перечисленных ниже:

  1. Графики обеспечивают лучший способ работы с абстрактными понятиями, такими как отношения и взаимодействия. Они также предлагают интуитивно-визуальный способ осмысления этих концепций. Графики также составляют естественную основу для анализа отношений в социальном контексте.
  2. Графы могут решать более сложные проблемы, упрощая проблемы до более простых представлений или преобразовывая проблемы в представления с разных точек зрения.
  3. Теории и концепции графов используются для изучения и моделирования социальных сетей, моделей мошенничества, моделей энергопотребления, вирусности и влияния в социальных сетях. Анализ социальных сетей (SNA), вероятно, является самым известным приложением теории графов для науки о данных.

Традиционные методы анализа графов

Традиционные методы в основном основаны на алгоритмах, например:

  1. алгоритмы поиска, например BFS, DFS
  2. алгоритмы кратчайшего пути, например Алгоритм Дейкстры, ближайший сосед
  3. алгоритмы связующего дерева, например Алгоритм Прима
  4. методы кластеризации, например Компоненты с высокой степенью связи, k-среднее

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

Графическая нейронная сеть

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

В литературе представлены в основном три типа графических нейронных сетей:

  1. Рекуррентная графическая нейронная сеть
  2. Пространственная сверточная сеть
  3. Спектральная сверточная сеть

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

Имея это в виду, мы затем даем каждому узлу состояние (x), чтобы представить его концепцию. Мы можем использовать состояние узла (x) для получения вывода (o), то есть решения о концепции. Конечное состояние (x_n) узла обычно называется «внедрением узла». Задача всей GNN - определить «вложение узла» каждого узла, просматривая информацию о его соседних узлах.

Мы начнем с самой новаторской версии Graph Neural Network, Recurrent Graph Neural Network или RecGNN.

Рекуррентная графическая нейронная сеть

Как было сказано в исходной статье GNN, RecGNN построена на основе предположения теоремы Банаха о неподвижной точке. Теорема Банаха о неподвижной точке утверждает, что: Пусть (X, d) - полное метрическое пространство и пусть (T: X → X) - сжимающее отображение. Тогда T имеет единственную неподвижную точку (x ∗) и для любого x∈X последовательность T_n (x) при n → ∞ сходится к (x ∗). Это означает, что если я применяю отображение T к x k раз, x ^ k должно быть почти равно x ^ ( k-1), то есть:

RecGNN определяет параметризованную функцию f_w:

где l_n, l_co, x_ne, l_ne представляет характеристики текущего узла [n], края узел [n], состояние соседних узлов и характеристики соседних узлов. (В исходной статье автор называл особенности узлов метками узлов. Это может вызвать некоторую путаницу.)

Наконец, после k итераций конечное состояние узла используется для создания выходных данных для принятия решения по каждому узлу. Функция вывода определяется как:

Пространственная сверточная сеть

Интуиция сети пространственной свертки аналогична интуиции известной CNN, которая доминирует в литературе по задачам классификации и сегментации изображений. Чтобы понять, что такое CNN на изображениях, вы можете прочитать этот пост, который подробно объясняет CNN.

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

Спектральная сверточная сеть

По сравнению с другими типами GNN, этот тип сети свертки графов имеет очень прочную математическую основу. Спектральная сверточная сеть построена на основе теории обработки сигналов графа. И путем упрощения и приближения свертки графа.

С помощью аппроксимации полиномом Чебышева (Хаммонд и др. 2011) свертку графа можно упростить до следующей формы:

После дальнейшего упрощения GCN paper предлагает двухуровневую структуру нейронной сети, которую можно описать одним уравнением, как показано ниже:

где A_head - это предварительно обработанный лапласиан исходной матрицы смежности графа A. (Подробности математики можно найти в статье GCN. Для полного объяснения потребуется много усилий.)

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

Предположим, у нас есть простой граф с 4 узлами. Каждому из этих узлов назначается матрица признаков, как показано на рисунке выше. Легко получить матрицу смежности графа и матрицу функций, как показано ниже:

Обратите внимание, что диагональ матрицы смежности намеренно изменена на «1», чтобы добавить петлю для каждого узла. Это должно включать функцию каждого узла, когда мы выполняем агрегирование функций.

Затем мы выполняем A x X ( давайте сначала забудем о лапласиане A и весовой матрице W для простоты объяснения. )

Результат умножения матриц показан в самой правой матрице. Давайте посмотрим на полученный объект первого узла в качестве примера. Нетрудно заметить, что результат представляет собой сумму всех характеристик [node 1], включая функцию самого [node 1], а функции в [node 4] не включаются, поскольку он не является соседом [node 1] . Математически матрица смежности графа имеет значение «1» только при наличии ребра и «0» в противном случае. Это делает матричное умножение суммой характеристик узлов, которые подключены к опорному узлу.

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

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

Любая графическая нейронная сеть может быть выражена как нейронная сеть передачи сообщений (J. Gilmer et al., 2017) с функцией передачи сообщений, обновление узла и функцию считывания.

Что может сделать GNN?

Проблемы, которые решает GNN, можно условно разделить на три категории:

  1. Классификация узлов
  2. Прогнозирование ссылок
  3. Классификация графов

В классификации узлов задача состоит в том, чтобы предсказать внедрение узла для каждого узла в графе. Этот тип задач обычно обучается полу-контролируемым способом, когда помечена только часть графа. Типичные приложения для классификации узлов включают сети цитирования, сообщения Reddit, видео на Youtube и отношения с друзьями в Facebook.

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

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

Некоторые реальные приложения

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

GNN в обработке естественного языка

GNN широко используется в обработке естественного языка (NLP). Собственно, именно здесь изначально и начинается GNN. Если у кого-то из вас есть опыт в НЛП, вы, должно быть, думаете, что текст должен быть типом последовательных или временных данных, которые лучше всего можно описать с помощью RNN или LTSM. Что ж, GNN подходит к проблеме с совершенно другой точки зрения. GNN использовала внутренние отношения слов или документов для предсказания категорий. Например, сеть цитирования пытается предсказать этикетку каждой статьи в сети, задаваемую соотношением цитирования статьи и словами, которые цитируются в других статьях. Он также может построить синтаксическую модель, рассматривая разные части предложения вместо чисто последовательных, как в RNN или LTSM.

GNN в компьютерном зрении

Многие методы, основанные на CNN, достигли высочайшего уровня в обнаружении объектов на изображениях, но все же мы не знаем взаимоотношений между объектами. Одно из успешных применений GNN в CV - использование графиков для моделирования отношений между объектами, обнаруженными детектором на основе CNN. После того, как объекты обнаружены на изображениях, они затем передаются в GNN-вывод для предсказания взаимосвязи. Результатом вывода GNN является сгенерированный граф, моделирующий отношения между различными объектами.

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

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

GNN в других доменах

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

Заключение

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

GNN - все еще относительно новая область и заслуживает большего внимания исследователей. Это мощный инструмент для анализа графических данных. Но это не ограничивается только задачами в графах. Его можно легко обобщить на любые исследования, которые можно моделировать с помощью графиков. А графическое моделирование - это естественный способ анализа проблемы.

Использованная литература:

  1. Ф. Скарселли, М. Гори, «Модель графовой нейронной сети», Транзакции IEEE в нейронных сетях, 2009 г.
  2. Т. Н. Кипф, М. Веллинг, «Классификация с полууправлением с графовыми сверточными сетями», в Proc. ICLR, 2017.
  3. З. Ву, С. Пан, Ф. Чен, Г. Лонг, Ч. Чжан, Филип С. Ю, Комплексное исследование графических нейронных сетей, arXiv: 1901.00596
  4. Д. Сюй, Ю. Чжу, С. Б. Чой и Л. Фей-Фэй, «Генерация графа сцены с помощью итеративной передачи сообщений», в Proc. CVPR, т. 2, 2017
  5. Дж. Джонсон, А. Гупта и Л. Фей-Фей, «Создание изображения из графов сцены», в Proc. CVPR, 2018 г.
  6. X. Wang, Y. Ye, and A. Gupta, «Распознавание нулевого выстрела через семантические вложения и графы знаний», в CVPR 2018