Графовые нейронные сети

Граф

Графовая нейронная сеть (англ. Graph Neural Network, GNN) – тип нейронной сети, которая напрямую работает со структурой графа. Типичным применением GNN является классификация узлов. Концепция графовой нейронной сети была впервые предложена в 2009 году в работе , которая расширила существующие нейронные сети для обработки данных, представленных в графовых областях.

Идея

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

Определение:

Граф – это структура данных, состоящая из двух компонентов: вершин и ребер. Граф G описывается множеством вершин (узлов) V и ребер E, которые он содержит [math]G = (V,E)[/math].

Пример графа для анализа текста.

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

В последние годы системы, основанные на вариантах графовых нейронных сетей, таких как graph convolutional network (GCN), graph attention network (GAT), gated graph neural network (GGNN), продемонстрировали высокую производительность при решении многих задач, обозначенных выше.

Социальные сети

Молекулы

Изображения

Описание

В графе каждый узел определяется его признаками и связанными узлами. Целью GNN является изучение состояния встраивания [math]h_v \in R^{S}[/math], которое содержит информацию об окрестностях для каждого узла. Состояние встраивания [math]h_v[/math] - это s-мерный вектор из вершины [math]v[/math], который может быть использован для получения выхода [math]O_v[/math] (метки узла).

Пусть [math]f[/math] - это параметрическая функция, называемая локальной переходной функцией, которая является общей для всех узлов и обновляет состояние узла в соответствии с входной окрестностью. Также пусть [math]g[/math] - локальная выходная функция, которая описывает, как выход был производен. Тогда [math]h_v[/math] и [math]o_v[/math] определяются следующим образом:

[math]h_v = f{(x_v, x_{co[v]}, h_{ne[v]}, x_{ne[v]})}[/math] [math]o_v = g{(h_v,X_v)}[/math]

где [math]x_v, x_{co[v]}, h_{ne[v]}, x_{ne[v]}[/math] являются признаками [math]v[/math], признаками его ребер, состояний, и признаками узлов в окрестностях [math]v[/math] соответственно.

Пусть [math]H, O, X[/math] и [math]X_N[/math] - это векторы, построенные путем укладки всех состояний, всех выходных данных, всех признаков и всех признаков узлов соответственно. Тогда мы можем представить уравнения в более компактной форме:

[math]H = F{(H,X)}[/math] [math]O = G{(H,X_N)}[/math]

где [math]F[/math] - это глобальная функция перехода, а [math]G[/math] - глобальная выходная функция, которая является сложенной версией [math]f[/math] и [math]g[/math] для всех узлов в графе соответственно. Значение [math]H[/math] является фиксированным и однозначно определяется в предположением о том, что [math]F[/math] - это карта сжатия.

С учетом теоремы Банаха о неподвижной точке GNN использует следующую классическую итерационную схему для вычисления состояния: [math]H^{t+1} = F{(H^t,X)}[/math], где [math]H^t[/math] обозначает [math]t[/math]-ую итерацию [math]H[/math]. Динамическая система из этого уравнения сходится экспоненциально быстро к решению уравнения [math]H = F{(H,X)}[/math] для любого начального значения [math]H(0)[/math]. Стоит отметить, что вычисления описанные в [math]f[/math] и [math]g[/math], могут быть интерпретированы как нейронные сети с прямой связью.

Следующие задачей становится поиск параметров [math]f[/math] и [math]g[/math]. С помощью целевой информации ([math]t_v[/math] для конкретного узла) для контроля, функция потерь может быть вычислена следующим образом:

[math]loss = \sum_{i=1}^{p}{(t_i-o_i)}[/math]

где [math]p[/math] - это число контролируемых узлов. Алгоритм обучения основан на стратегии градиентного спуска и состоит из следующих шагов:

• Состояния [math]h_v^t[/math] итеративно обновляются [math]h_v = f{(x_v, x_{co[v]}, h_{ne[v]}, x_{ne[v]})}[/math] до времени [math]T[/math]. Они стремятся к фиксированному значению [math]H(T) \approx H[/math].
• Градиент весов [math]W[/math] вычисляется из функции потерь.
• Веса [math]W[/math] обновляются в соответствии с градиентом, вычисленным на последнем шаге.

Ограничения

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

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

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

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

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

Источники информации

• The Graph Neural Network Model
• Graph Neural Networks: A Review of Methods and Applications
• A Gentle Introduction to Graph Neural Networks (Basics, DeepWalk, and GraphSage)
• Hands-on Graph Neural Networks with PyTorch & PyTorch Geometric
• Графовые нейронные сети