Графовые нейронные сети — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Release version 1.0)
м (rollbackEdits.php mass rollback)
 
(не показано 7 промежуточных версий 3 участников)
Строка 1: Строка 1:
 
[[Файл:GnnGraph.png|thumb|250px|Граф]]
 
[[Файл: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>, которая расширила существующие нейронные сети для обработки данных, представленных в графовых областях.
+
'''Графовая нейронная сеть''' (англ. Graph Neural Network, GNN) {{---}} тип нейронной сети, которая напрямую работает со структурой графа. Типичным применением GNN является классификация узлов. Концепция графовой нейронной сети была впервые предложена в 2009 году в работе <ref>[https://ro.uow.edu.au/infopapers/3165/ The graph neural network model, University of Wollongong Australia]</ref>, которая расширила существующие нейронные сети для обработки данных, представленных в графовых областях.
  
 
== Идея ==
 
== Идея ==
  
При работе с естественными языками, обработке и анализе изображений, построении моделей веб-сетей и еще широком спектре прикладных задач, бывает удобно представлять данные в виде графов. Однако для традиционных методов машинного обучения необходимо предварительно преобразовывать графово структурированные данные в другие структуры данных, к примеру числовой вектор. Такой подход может привести к потере части информации, заключающейся во взаиморасположении узлов сети.
+
При работе с естественными языками, обработке и анализе изображений, построении моделей веб-сетей и еще широком спектре прикладных задач, бывает удобно представлять данные в виде графов:
 +
{|align="center"
 +
|-valign="top"
 +
|[[Файл:Social_network.PNG|250px|thumb|Социальные сети]]
 +
|[[Файл:TextGNN.PNG|thumb|540px|Анализ текста]]
 +
|[[Файл:MoleculeGNN.PNG|400px|thumb|Молекулы]]
 +
|}
 +
 
 +
Однако для традиционных методов машинного обучения необходимо предварительно преобразовывать графово структурированные данные в другие структуры данных, к примеру числовой вектор. Такой подход может привести к потере части информации, заключающейся во взаиморасположении узлов сети.
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Граф это структура данных, состоящая из двух компонентов: вершин и ребер. Граф G описывается множеством вершин (узлов) V и ребер E, которые он содержит <tex>G = (V,E)</tex>.  
+
'''Граф''' {{---}} это структура данных, состоящая из двух компонентов: вершин и ребер. Граф <tex>G</tex> описывается множеством вершин (узлов) <tex>V</tex> и ребер <tex>E</tex>, которые он содержит <tex>G = (V,E)</tex>.  
 
}}
 
}}
[[Файл:TextGNN.PNG|thumb|400px|Пример графа для анализа текста.]]
+
Использование GNN позволяет работать с данными графов, без предварительной обработки. Такой подход позволяет сохранить топологические отношения между узлами графа.  
GNN позволяет обрабатывать графово структурированную информацию без стадии предварительной обработки, сохраняя таким образом топологические отношения между узлами графа. Графовые нейронные сети основаны на механизме распространения информации, т.е. граф обрабатывается набором модулей, каждый из которых связан с узлом графа. В свою очередь модули связаны в соответствии со связями графа. Модули обновляют свое состояние и обмениваются информацией до тех пор, пока не достигнут устойчивого равновесия. Выходные данные GNN вычисляются в каждом узле на основе состояния модуля. Механизм распространения ограничен, чтобы гарантировать, что уникальное устойчивое состояние всегда существует.  
 
  
В последние годы системы, основанные на вариантах графовых нейронных сетей, таких как graph convolutional network (GCN), graph attention network (GAT), gated graph neural network (GGNN), продемонстрировали высокую производительность при решении многих задач, обозначенных выше.
+
В основе GNN заложен механизм распространения информации. Граф обрабатывается набором модулей, которые связаны между собой в соответствии со связями графа. Также каждый из модулей связан с узлами графа. В процессе обучения, модули обновляют свои состояния и обмениваются информацией. Это продолжается до тех пор, пока модули не достигнут устойчивого равновесия (для того, чтобы была гарантия того, что такое устойчивое состояние существует, этот механизм распространения ограничен). Выходные данные GNN вычисляются на основе состояния модуля на каждом узле.
  
{|align="center"
+
[[Файл:GNNanimation.gif]]
|-valign="top"
 
|[[Файл:Social_network.PNG|250px|thumb|Социальные сети]]
 
|[[Файл:MoleculeGNN.PNG|400px|thumb|Молекулы]]
 
|[[Файл:ImageGNN.PNG|312px|thumb|Изображения]]
 
|}
 
  
 
== Описание ==
 
== Описание ==
  
В графе каждый узел определяется его признаками и связанными узлами. Целью GNN является изучение состояния встраивания <tex>h_v \in R^{S}</tex>, которое содержит информацию об окрестностях для каждого узла. Состояние встраивания <tex>h_v</tex> - это s-мерный вектор из вершины <tex>v</tex>, который может быть использован для получения выхода <tex>O_v</tex> (метки узла).  
+
В графе каждый узел определяется его признаками и связанными узлами. Целью 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> определяются следующим образом:
+
Пусть <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>
 
<center><tex>h_v = f{(x_v, x_{co[v]}, h_{ne[v]}, x_{ne[v]})}</tex></center>
Строка 34: Строка 36:
 
где <tex>x_v, x_{co[v]}, h_{ne[v]}, x_{ne[v]}</tex> являются признаками <tex>v</tex>, признаками его ребер, состояний, и признаками узлов в окрестностях <tex>v</tex> соответственно.
 
где <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> - это векторы, построенные путем укладки всех состояний, всех выходных данных, всех признаков и всех признаков узлов соответственно. Тогда мы можем представить уравнения в более компактной форме:
+
Пусть <tex>H, O, X</tex> и <tex>X_N</tex> {{---}} это векторы, построенные путем укладки всех состояний, всех выходных данных, всех признаков и всех признаков узлов соответственно. Тогда мы можем представить уравнения в более компактной форме:
  
 
<center><tex>H = F{(H,X)}</tex></center>
 
<center><tex>H = F{(H,X)}</tex></center>
Строка 40: Строка 42:
 
<center><tex>O = G{(H,X_N)}</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> - это карта сжатия.
+
где <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>, могут быть интерпретированы как нейронные сети с прямой связью.
 
С учетом теоремы Банаха о неподвижной точке 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>, могут быть интерпретированы как нейронные сети с прямой связью.
Строка 48: Строка 50:
 
<center><tex>loss = \sum_{i=1}^{p}{(t_i-o_i)}</tex></center>
 
<center><tex>loss = \sum_{i=1}^{p}{(t_i-o_i)}</tex></center>
  
где <tex>p</tex> - это число контролируемых узлов. Алгоритм обучения основан на стратегии градиентного спуска и состоит из следующих шагов:
+
где <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>.
 
* Состояния <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>.
 
* Градиент весов <tex>W</tex> вычисляется из функции потерь.
 
* Градиент весов <tex>W</tex> вычисляется из функции потерь.
 
* Веса <tex>W</tex> обновляются в соответствии с градиентом, вычисленным на последнем шаге.
 
* Веса <tex>W</tex> обновляются в соответствии с градиентом, вычисленным на последнем шаге.
 +
 +
== Развитие ==
 +
 +
[[Файл:GCNex.png|thumb|300px|Пример Graph Convolutional Network]]
 +
В последние годы системы, основанные на вариантах графовых нейронных сетей, таких как '''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%'''.
 +
 +
'''При решении же реальных задач, данные алгоритмы применяются в следующих областях:'''
 +
* '''GCN''' применяют в задачах классификации текстовых данных, изображений, болезней и прогнозировании побочных эффектов;
 +
* '''GAT''' используют для классификации текста, обнаружения объектов на изображениях, задач комбинаторной оптимизации;
 +
* '''GGNN''' применяют для нейронного машинного перевода, для анализа социальных отношений.
  
 
== Ограничения ==
 
== Ограничения ==
Строка 65: Строка 79:
  
 
Наконец, нецелесообразно использовать фиксированные точки, если мы сосредоточимся на представлении узлов вместо графиков, поскольку распределение представления в фиксированной точке будет гораздо более гладким по значению и менее информативным для различения каждого узла.
 
Наконец, нецелесообразно использовать фиксированные точки, если мы сосредоточимся на представлении узлов вместо графиков, поскольку распределение представления в фиксированной точке будет гораздо более гладким по значению и менее информативным для различения каждого узла.
 +
 +
==См. также==
 +
*[[:Рекуррентные нейронные сети|Рекуррентные нейронные сети]]
 +
*[[:Рекурсивные нейронные сети|Рекурсивные нейронные сети]]
  
 
== Примечания ==
 
== Примечания ==
Строка 75: Строка 93:
 
* [https://towardsdatascience.com/hands-on-graph-neural-networks-with-pytorch-pytorch-geometric-359487e221a8 Hands-on Graph Neural Networks with PyTorch & PyTorch Geometric]
 
* [https://towardsdatascience.com/hands-on-graph-neural-networks-with-pytorch-pytorch-geometric-359487e221a8 Hands-on Graph Neural Networks with PyTorch & PyTorch Geometric]
 
* [https://cyberleninka.ru/article/n/grafovye-neyronnye-seti Графовые нейронные сети]
 
* [https://cyberleninka.ru/article/n/grafovye-neyronnye-seti Графовые нейронные сети]
 +
 +
[[Категория: Машинное обучение]]
 +
[[Категория: Нейронные сети]]

Текущая версия на 19:16, 4 сентября 2022

Граф

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

Идея

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

Социальные сети
Анализ текста
Молекулы

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

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

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

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

GNNanimation.gif

Описание

В графе каждый узел определяется его признаками и связанными узлами. Целью 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)[2], GAT (Graph Attention Network)[3], GGNN (Gated Graph Neural Network)[4], продемонстрировали высокую производительность при решении многих задач.

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

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

См. также

Примечания

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