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

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

Описание

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

[math]G = (V,E)[/math]

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

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