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

Граф

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

Идея

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

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

Анализ текста

Молекулы

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

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

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

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

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

Описание

В графе каждый узел определяется его признаками и связанными узлами. Целью 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] обновляются в соответствии с градиентом, вычисленным на последнем шаге.

Развитие

Пример Graph Convolutional Network

В последние годы системы, основанные на вариантах графовых нейронных сетей, таких как GCN (Graph Convolutional Network), GAT (Graph Attention Network), GGNN (Gated Graph Neural Network), продемонстрировали высокую производительность при решении многих задач.

Для тестирования алгоритмов часто используются датасеты наборов данных сети цитирования, такие как Citeseer, Cora and Pubmed. В них узлы — это документы, а ребра — это ссылки на цитаты. GCN на этих данных удается добиться точности в районе 70.3%, 81.5%, 79.0% соответственно, а результаты GAC составляют 83.0%, 72.5%, 79.0%.

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

• GCN применяют в задачах классификации текстовых данных, изображений, болезней и прогнозировании побочных эффектов;
• GAT используют для классификации текста, обнаружения объектов на изображениях, задач комбинаторной оптимизации;
• GGNN применяют для нейронного машинного перевода, для анализа социальных отношений.

Ограничения

Несмотря на то, что экспериментальные результаты показали, что 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
• Графовые нейронные сети