Изменения
замена дефисов на тире
[[Файл:GnnGraph.png|thumb|250px|Граф]]
'''Графовая нейронная сеть''' (англ. Graph Neural Network, GNN) – {{---}} тип нейронной сети, которая напрямую работает со структурой графа. Типичным применением GNN является классификация узлов. Концепция графовой нейронной сети была впервые предложена в 2009 году в работе <ref>[https://ro.uow.edu.au/infopapers/3165/ The graph neural network model, University of Wollongong Australia]</ref>, которая расширила существующие нейронные сети для обработки данных, представленных в графовых областях.
== Идея ==
{{Определение
|definition=
'''Граф''' – {{---}} это структура данных, состоящая из двух компонентов: вершин и ребер. Граф <tex>G</tex> описывается множеством вершин (узлов) <tex>V</tex> и ребер <tex>E</tex>, которые он содержит <tex>G = (V,E)</tex>.
}}
Использование GNN позволяет работать с данными графов, без предварительной обработки. Такой подход позволяет сохранить топологические отношения между узлами графа.
== Описание ==
В графе каждый узел определяется его признаками и связанными узлами. Целью GNN является изучение состояния встраивания <tex>h_v \in R^{S}</tex>, которое содержит информацию об окрестностях для каждого узла. Состояние встраивания <tex>h_v</tex> {{- --}} это s-мерный вектор из вершины <tex>v</tex>, который может быть использован для получения выхода <tex>O_v</tex> (метки узла).
Пусть <tex>f</tex> {{- --}} это параметрическая функция, называемая ''локальной переходной функцией'', которая является общей для всех узлов и обновляет состояние узла в соответствии с входной окрестностью. Также пусть <tex>g</tex> {{--- }} ''локальная выходная функция'', которая описывает, как выход был производен. Тогда <tex>h_v</tex> и <tex>o_v</tex> определяются следующим образом:
<center><tex>h_v = f{(x_v, x_{co[v]}, h_{ne[v]}, x_{ne[v]})}</tex></center>
где <tex>x_v, x_{co[v]}, h_{ne[v]}, x_{ne[v]}</tex> являются признаками <tex>v</tex>, признаками его ребер, состояний, и признаками узлов в окрестностях <tex>v</tex> соответственно.
Пусть <tex>H, O, X</tex> и <tex>X_N</tex> {{- --}} это векторы, построенные путем укладки всех состояний, всех выходных данных, всех признаков и всех признаков узлов соответственно. Тогда мы можем представить уравнения в более компактной форме:
<center><tex>H = F{(H,X)}</tex></center>
<center><tex>O = G{(H,X_N)}</tex></center>
где <tex>F</tex> {{- --}} это ''глобальная функция перехода'', а <tex>G</tex> {{--- }} ''глобальная выходная функция'', которая является сложенной версией <tex>f</tex> и <tex>g</tex> для всех узлов в графе соответственно. Значение <tex>H</tex> является фиксированным и однозначно определяется в предположением о том, что <tex>F</tex> {{--- }} это карта сжатия.
С учетом теоремы Банаха о неподвижной точке GNN использует следующую классическую итерационную схему для вычисления состояния: <tex>H^{t+1} = F{(H^t,X)}</tex>, где <tex>H^t</tex> обозначает <tex>t</tex>-ую итерацию <tex>H</tex>. Динамическая система из этого уравнения сходится экспоненциально быстро к решению уравнения <tex>H = F{(H,X)}</tex> для любого начального значения <tex>H(0)</tex>. Стоит отметить, что вычисления описанные в <tex>f</tex> и <tex>g</tex>, могут быть интерпретированы как нейронные сети с прямой связью.
<center><tex>loss = \sum_{i=1}^{p}{(t_i-o_i)}</tex></center>
где <tex>p</tex> {{- --}} это число контролируемых узлов. Алгоритм обучения основан на стратегии градиентного спуска и состоит из следующих шагов:
* Состояния <tex>h_v^t</tex> итеративно обновляются <tex>h_v = f{(x_v, x_{co[v]}, h_{ne[v]}, x_{ne[v]})}</tex> до времени <tex>T</tex>. Они стремятся к фиксированному значению <tex>H(T) \approx H</tex>.
В последние годы системы, основанные на вариантах графовых нейронных сетей, таких как '''GCN (Graph Convolutional Network)'''<ref>[https://arxiv.org/pdf/1609.02907.pdf Semi-Supervised Classification with Graph Convolutional Networks, Thomas N. Kipf]</ref>, '''GAT (Graph Attention Network)'''<ref>[https://arxiv.org/pdf/1710.10903.pdf Graph Attention Networks, Petar Velickovic]</ref>, '''GGNN (Gated Graph Neural Network)'''<ref>[https://arxiv.org/pdf/1511.05493.pdf Gated Graph Sequence Neural Networks, Yujia Li & Richard Zemel]</ref>, продемонстрировали высокую производительность при решении многих задач.
Для тестирования алгоритмов часто используются датасеты наборов данных сети цитирования, такие как '''Citeseer''', '''Cora''' and '''Pubmed'''. В них узлы {{- --}} это документы, а ребра {{- --}} это ссылки на цитаты. '''GCN''' на этих данных удается добиться точности в районе '''70.3%, 81.5%, 79.0%''' соответственно, а результаты '''GAC''' составляют '''83.0%, 72.5%, 79.0%'''.
'''При решении же реальных задач, данные алгоритмы применяются в следующих областях:'''
