Графовая нейронная сеть

Графовая нейронная сеть ( GNN ) принадлежит к классу искусственных нейронных сетей для обработки данных, которые могут быть представлены в виде графов .

Основные строительные блоки графовой нейронной сети (GNN). $(1)$ Перестановочно-эквивариантный слой. $(2)$ Локальный слой пула. $(3)$Слой глобального пула (или считывания). Цвета обозначают особенности .

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

Ключевым элементом конструкции GNN является использование парной передачи сообщений , при которой узлы графа итеративно обновляют свои представления, обмениваясь информацией со своими соседями. С момента их создания было предложено несколько различных архитектур GNN. которые реализуют различные варианты передачи сообщений, началось рекурсивно или сверточный конструктив подходы. По состоянию на 2022 год , можно ли определить архитектуру GNN, «выходящую за пределы» передачи сообщений, или каждая GNN может быть построена на передаче сообщений по соответствующим образом определенным графам, остается открытым исследовательским вопросом.

Соответствующие области применения GNN включают обработку естественного языка , социальные сети , сети цитирования , молекулярная биология , химия, физика и NP-трудные задачи комбинаторной оптимизации .

несколько с открытым исходным кодом , реализующих графовые нейронные сети, такие как PyTorch Geometric. библиотек Доступно ( PyTorch ), TensorFlow GNN ( TensorFlow ), jraph ( Google JAX ) и GraphNeuralNetworks.jl /GeometricFlux.jl ( Юлия , Флюкс ).

Архитектура

Архитектура универсальной GNN реализует следующие фундаментальные уровни :

1. Эквивариант перестановки : слой, эквивалентный перестановке, отображает представление графа в обновленное представление того же графа. В литературе эквивариантные слои перестановок реализуются посредством попарной передачи сообщений между узлами графа. Интуитивно понятно, что на уровне передачи сообщений узлы обновляют свои представления, агрегируя сообщения , полученные от их непосредственных соседей. Таким образом, каждый уровень передачи сообщений увеличивает рецептивное поле GNN на один шаг.
2. Локальное объединение : слой локального объединения делает график более грубым за счет понижающей дискретизации . Локальное объединение используется для увеличения рецептивного поля GNN аналогично объединению слоев в сверточных нейронных сетях . Примеры включают пул k-ближайших соседей , пул top-k, и объединение внимания к себе.
3. Глобальное объединение : уровень глобального объединения, также известный как слой чтения , обеспечивает представление всего графа фиксированного размера. Уровень глобального пула должен быть инвариантным к перестановкам, чтобы перестановки в порядке узлов и ребер графа не меняли конечный результат. Примеры включают поэлементную сумму, среднее или максимальное значение.

Было продемонстрировано, что GNN не могут быть более выразительными, чем тест изоморфизма графов Вейсфейлера-Лемана . На практике это означает, что существуют разные графовые структуры (например, молекулы с одинаковыми атомами, но разными связями ), которые не могут быть различимы с помощью GNN. более мощные GNN, работающие с геометриями более высокой размерности, такими как симплициальные комплексы . Могут быть разработаны По состоянию на 2022 год , смогут ли будущие архитектуры преодолеть примитив передачи сообщений, остается открытым исследовательским вопросом.

Неизоморфные графы, которые невозможно отличить с помощью GNN из-за ограничений теста на изоморфизм графов Вейсфейлера-Лемана. Цвета обозначают особенности узла .

Уровни передачи сообщений

Обновление представления узла на уровне нейронной сети передачи сообщений (MPNN). Узел $\mathbf {x} _{0}$ получает сообщения, отправленные всеми его непосредственными соседями $\mathbf {x} _{1}$ к $\mathbf {x} _{4}$. Сообщения вычисляются с помощью функции сообщения. $\phi$, который учитывает особенности как отправителей, так и получателей.

Слои передачи сообщений — это слои, эквивалентные перестановкам, отображающие граф в обновленное представление того же графа. Формально их можно выразить как нейронные сети передачи сообщений (MPNN).

Позволять $G=(V,E)$ быть графом , где $V$ это набор узлов и $E$это набор ребер. Позволять $N_{u}$ быть окрестностью некоторого узла $u\in V$. Кроме того, пусть $\mathbf {x} _{u}$ быть особенностями узла $u\in V$, и $\mathbf {e} _{uv}$ быть чертами края $(u,v)\in E$. MPNN Уровень можно выразить следующим образом:

$\mathbf {h} _{u}=\phi \left(\mathbf {x} _{u},\bigoplus _{v\in N_{u}}\psi (\mathbf {x} _{u},\mathbf {x} _{v},\mathbf {e} _{uv})\right)$

где $\phi$ и $\psi$ являются дифференцируемыми функциями (например, искусственные нейронные сети ), и $\bigoplus$является к перестановке инвариантным оператором агрегирования , который может принимать произвольное количество входных данных (например, поэлементную сумму, среднее или максимальное значение). В частности, $\phi$ и $\psi$называются функциями обновления и сообщения соответственно. Интуитивно понятно, что в вычислительном блоке MPNN узлы графа обновляют свои представления, агрегируя сообщения , полученные от своих соседей.

Выходные данные одного или нескольких слоев MPNN являются представлениями узлов. $\mathbf {h} _{u}$ для каждого узла $u\in V$в графике. Представления узлов можно использовать для любой последующей задачи, такой как классификация узлов/графов или прогнозирование ребер.

Узлы графа в MPNN обновляют свое представление, агрегируя информацию от своих непосредственных соседей. Таким образом, укладка $n$ Уровни MPNN означают, что один узел сможет взаимодействовать с узлами, которые находятся не более $n$«прыгает» прочь. В принципе, чтобы гарантировать, что каждый узел получает информацию от каждого другого узла, необходимо сложить количество слоев MPNN, равное диаметру графа . Однако наложение большого количества слоев MPNN может вызвать такие проблемы, как чрезмерное сглаживание. и чрезмерное раздавливание. Чрезмерное сглаживание означает, что представления узлов становятся неразличимыми. Чрезмерное сжатие относится к узкому месту, которое создается путем сжатия долгосрочных зависимостей в представления фиксированного размера. Контрмеры, такие как пропуск соединений (как в остаточных нейронных сетях ), правила закрытого обновления и прыжковые знания может смягчить чрезмерное сглаживание. Изменение последнего слоя, чтобы он стал полностью смежным слоем, т. е. рассматривая граф как полный граф , может уменьшить чрезмерное сжатие в задачах, где требуются зависимости на большие расстояния.

В литературе были разработаны и другие «разновидности» MPNN. такие как сверточные сети на графах и графические сети внимания, определения которых могут быть выражены в терминах формализма MPNN.

Графовая сверточная сеть

Сверточная сеть графов (GCN) была впервые представлена ​​Томасом Кипфом и Максом Веллингом в 2017 году.

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

Формальное выражение слоя GCN выглядит следующим образом:

$\mathbf {H} =\sigma \left({\tilde {\mathbf {D} }}^{-{\frac {1}{2}}}{\tilde {\mathbf {A} }}{\tilde {\mathbf {D} }}^{-{\frac {1}{2}}}\mathbf {X} \mathbf {\Theta } \right)$

где $\mathbf {H}$ - матрица представлений узлов $\mathbf {h} _{u}$, $\mathbf {X}$ это матрица особенностей узла $\mathbf {x} _{u}$, $\sigma (\cdot )$ — функция активации (например, ReLU ), ${\tilde {\mathbf {A} }}$ графов — матрица смежности с добавлением петель, ${\tilde {\mathbf {D} }}$ графа - матрица степеней с добавлением петель, а $\mathbf {\Theta }$ представляет собой матрицу обучаемых параметров.

В частности, пусть $\mathbf {A}$ — матрица смежности графа: тогда можно определить ${\tilde {\mathbf {A} }}=\mathbf {A} +\mathbf {I}$ и ${\tilde {\mathbf {D} }}_{ii}=\sum _{j\in V}{\tilde {A}}_{ij}$, где $\mathbf {I}$обозначает единичную матрицу . Эта нормализация гарантирует, что собственные значения ${\tilde {\mathbf {D} }}^{-{\frac {1}{2}}}{\tilde {\mathbf {A} }}{\tilde {\mathbf {D} }}^{-{\frac {1}{2}}}$ ограничены в диапазоне $[0,1]$, избегая числовых нестабильностей и взрывающихся/исчезающих градиентов .

Ограничением GCN является то, что они не допускают многомерных краевых элементов. $\mathbf {e} _{uv}$. Однако возможно связать скалярные веса $w_{uv}$ к каждому краю, наложив $A_{uv}=w_{uv}$, т. е. устанавливая каждый ненулевой элемент в матрице смежности равным весу соответствующего ребра.

Сеть графического внимания

Сеть внимания на графах (GAT) была представлена ​​Петром Величковичем и др. в 2018 году.

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

Уровень GAT с несколькими головками можно выразить следующим образом:

$\mathbf {h} _{u}={\overset {K}{\underset {k=1}{\Big \Vert }}}\sigma \left(\sum _{v\in N_{u}}\alpha _{uv}\mathbf {W} ^{k}\mathbf {x} _{v}\right)$

где $K$ количество голов внимания , ${\Big \Vert }$ обозначает конкатенацию векторов , $\sigma (\cdot )$ — функция активации (например, ReLU ), $\alpha _{ij}$ – коэффициенты внимания, а $W^{k}$ представляет собой матрицу обучаемых параметров для $k$- внимание головы.

Для последнего уровня GAT выходные данные каждой головки внимания усредняются перед применением функции активации. Формально последний уровень GAT можно записать так:

$\mathbf {h} _{u}=\sigma \left({\frac {1}{K}}\sum _{k=1}^{K}\sum _{v\in N_{u}}\alpha _{uv}\mathbf {W} ^{k}\mathbf {x} _{v}\right)$

Внимание в машинном обучении — это метод, имитирующий когнитивное внимание . В контексте обучения на графиках коэффициент внимания $\alpha _{uv}$ измеряет , насколько важен узел $u\in V$ узел $v\in V$.

Нормированные коэффициенты внимания рассчитываются следующим образом:

$\alpha _{uv}={\frac {\exp({\text{LeakyReLU}}\left(\mathbf {a} ^{T}[\mathbf {W} \mathbf {h} _{u}\Vert \mathbf {W} \mathbf {h} _{v}\Vert \mathbf {e} _{uv}]\right))}{\sum _{z\in N_{u}}\exp({\text{LeakyReLU}}\left(\mathbf {a} ^{T}[\mathbf {W} \mathbf {h} _{u}\Vert \mathbf {W} \mathbf {h} _{z}\Vert \mathbf {e} _{uz}]\right))}}$

где $\mathbf {a}$ вектор обучаемых весов, $\cdot ^{T}$ указывает на транспозицию и ${\text{LeakyReLU}}$представляет собой модифицированную функцию активации ReLU . Коэффициенты внимания нормализованы, чтобы их можно было легко сравнивать на разных узлах.

GCN можно рассматривать как частный случай GAT, где коэффициенты внимания не подлежат изучению, а фиксированы и равны весам ребер. $w_{uv}$.

вентилируемой графовой

Нейронная сеть с последовательностями вентильных графов (GGS-NN) была представлена ​​Yujia Li et al. в 2015 году. GGS-NN расширяет формулировку GNN Скарселли и др. для вывода последовательностей. Структура передачи сообщений реализована как правило обновления ячейки закрытой рекуррентной единицы (GRU).

GGS-NN можно выразить следующим образом:

$\mathbf {h} _{u}^{(0)}=\mathbf {x} _{u}\,\Vert \,\mathbf {0}$

$\mathbf {m} _{u}^{(l+1)}=\sum _{v\in N_{u}}\mathbf {\Theta } \mathbf {h} _{v}$

$\mathbf {h} _{u}^{(l+1)}={\text{GRU}}(\mathbf {m} _{u}^{(l+1)},\mathbf {h} _{u}^{(l)})$

где $\Vert$ обозначает конкатенацию векторов , $\mathbf {0}$ вектор нулей, $\mathbf {\Theta }$ представляет собой матрицу обучаемых параметров, ${\text{GRU}}$ является ячейкой ГРУ, и $l$обозначает индекс последовательности. В GGS-NN представления узлов рассматриваются как скрытые состояния ячейки GRU. Начальные характеристики узла $\mathbf {x} _{u}^{(0)}$дополняются нулями до скрытого измерения состояния ячейки GRU. Одна и та же ячейка GRU используется для обновления представлений для каждого узла.

Слои локального пула

Слои локального пула огрубляют график за счет понижения разрешения. Мы представляем здесь несколько предложенных доступных для изучения стратегий локального объединения. Для каждого случая входными данными являются исходный граф, представленный матрицей $\mathbf {X}$ узловых признаков и матрица смежности графа $\mathbf {A}$. Результатом является новая матрица $\mathbf {X} '$особенностей узлов и новая матрица смежности графов $\mathbf {A} '$.

Объединение Top-k

Мы сначала установили

$\mathbf {y} ={\frac {\mathbf {X} \mathbf {p} }{\Vert \mathbf {p} \Vert }}$

где $\mathbf {p}$— обучаемый вектор проекции . Вектор проекции $\mathbf {p}$ вычисляет значение скалярной проекции для каждого узла графа.

Слой объединения top-k тогда можно формализовать следующим образом:

$\mathbf {X} '=(\mathbf {X} \odot {\text{sigmoid}}(\mathbf {y} ))_{\mathbf {i} }$

$\mathbf {A} '=\mathbf {A} _{\mathbf {i} ,\mathbf {i} }$

где $\mathbf {i} ={\text{top}}_{k}(\mathbf {y} )$ — подмножество узлов с топ-k наивысшими оценками проекций, $\odot$ обозначает поэлементное умножение матриц , а ${\text{sigmoid}}(\cdot )$это сигмовидная функция . Другими словами, узлы с наивысшими показателями проекции из топ-k сохраняются в новой матрице смежности. $\mathbf {A} '$. ${\text{sigmoid}}(\cdot )$ операция создает вектор проекции $\mathbf {p}$ обучаемый методом обратного распространения ошибки , который в противном случае давал бы дискретные выходные данные.

Объединение внимания к себе

Мы сначала установили

$\mathbf {y} ={\text{GNN}}(\mathbf {X} ,\mathbf {A} )$

где ${\text{GNN}}$ представляет собой общий уровень GNN, эквивалентный перестановке (например, GCN, GAT, MPNN).

Уровень объединения внимания тогда можно формализовать следующим образом:

$\mathbf {X} '=(\mathbf {X} \odot \mathbf {y} )_{\mathbf {i} }$

$\mathbf {A} '=\mathbf {A} _{\mathbf {i} ,\mathbf {i} }$

где $\mathbf {i} ={\text{top}}_{k}(\mathbf {y} )$ — подмножество узлов с топ-k наивысшими оценками проекций, $\odot$ обозначает поэлементное умножение матриц .

Уровень объединения самообслуживания можно рассматривать как расширение слоя объединения top-k. В отличие от пула top-k, оценки самовнимания, вычисленные при пуле самоконтроля, учитывают как функции графа, так и топологию графа.

Приложения

Сворачивание белка

См. также: АльфаФолд

Графовые нейронные сети являются одним из основных строительных блоков AlphaFold , программы искусственного интеллекта, разработанной для решения Google DeepMind проблемы сворачивания белков в биологии . AlphaFold занял первое место в нескольких соревнованиях CASP .

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

См. также: Рекомендательная система .

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

Комбинаторная оптимизация

См. Также: Комбинаторная оптимизация.

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

Кибербезопасность

См. также: Система обнаружения вторжений.

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

Внешние ссылки

• https://distill.pub/2021/gnn-intro/