Глубокое понимание принципа графовой сверточной нейронной сети (GCN)

предисловие

Развитие глубокого обучения меняется с каждым днем, от классических глубоких сетей (DNN, CNN, RNN) до GAN и обучения с подкреплением. Сценариев приложений, охватываемых глубоким обучением, становится все больше и больше. Представленная сегодня графовая нейронная сеть — это еще один класс методов глубокого обучения. Хотя нейронную сеть на графе тоже можно отнести к разряду глубокого обучения, она имеет свои уникальные сценарии применения и реализации алгоритма, что не очень дружелюбно к новичкам. GCN, полное название Graph Convolutional Network, представляет собой граф сверточной сети, Эта статья в основном реализует глубокое понимание GCN и помогает быстро понять принцип и использование GCN.

1. Зачем вам GCN

Вход сверточной нейронной сети (CNN) представляет собой структуру графа с евклидовой структурой, такой как изображение, которое представляет собой такой граф: CNN Ядро свертки (ядро) используется для извлечения признаков из евклидова пространства.Поскольку изображение представляет собой относительно регулярную структуру графа, ядро свертки можно использовать для перевода и извлечения узловых признаков, то есть ядро CNN лежит в его ядре , а ядро маленькое.Окно транслируется на изображение, а фичи извлекаются свёрткой. Ключевым моментом здесь является трансляционная инвариантность структуры изображения: независимо от того, куда маленькое окно перемещается на изображение, его внутренняя структура точно такая же, поэтому CNN может добиться совместного использования параметров. В этом суть CNN. Но обычно мы сталкиваемся с топологическими сетями или социальными сетями, которые выглядят следующим образом 图结构

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

Во-вторых, принцип GCN

1. Определение графа

Структура графа представлена G = (V, E). Граф включает в себя ориентированные графы или неориентированные графы, но в GCN рассматриваются только неориентированные графы. V представляет геометрию узла, E представляет геометрию ребра, а n представляет узел. , а m представляет количество ребер. Ниже мы вводим значение различных символов в GCN для структуры графа:

\\v_i\in V\qquad означает, что v_i является узлом \\e_{ij}=(e_i,e_j)\in E\qquad означает ребро между узлом\quad i и j \\N(v)=\{ u \in V|(v,u)\in E\}\qquad представляет собой множество всех соседей точки v\\A_{ij}\qquad представляет собой матрицу смежности графа\\A_{ij}=1\qquad представляет узел\ Существует ребро между quad i и j\D\qquad представляет собой матрицу степеней текущего графа, D является диагональной матрицей\d_{ii}\in D\quad представляет степень каждого узла в A\X \in R ^{n\times d} представляет вектор признаков из n узлов, а размерность вектора признаков равна d

2. Глобальная сеть контекстной рекламы приближается

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

2.1 Формула расчета матрицы

Предположим, у нас есть пакет данных графа под рукой, есть n узлов (узлов), каждый узел имеет свой собственный вектор признаков, мы устанавливаем признаки этих узлов, чтобы сформировать n×d-мерную матрицу признаков X, а затем отношение также сформирует $n\times n$ размерная матрица смежности A. X и A являются входными данными для нашей модели.

Для всех узлов, т.е. $H^{(l)}$ представляет матрицу собственных векторов, когда все этапы находятся в слое l, $H^{(l+1)}$ Представляет матрицу собственных векторов после одной операции свертки. Формула операции свертки выглядит следующим образом: $H^{(l+1)}=\sigma\left(\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} H^{(l)} W^{(l)}\right)$ $\hat{A}=A+I$ В этой формуле:

$A+I$ , $I$ — единичная матрица, то есть диагональ равна 1, а все остальные — 0
$\tilde{D}$ да $\tilde{A}$ Матрица степеней , метод расчета $\tilde{D}=\sum{\tilde{A}_{ij}}$
$H$ - матрица собственных векторов всех узлов в каждом слое для входного слоя, $H^{(0)}$ эквивалентно $X$ , $[n,d]$ измерение
σ - нелинейная функция активации, такая как $RELU$
$W^{(l)}$ Представляет обучаемую матрицу параметров сверточной трансформации текущего слоя.

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

2.2 Объясните смысл формулы с мелкомасштабной матрицей

Формула рассчитывается с точки зрения матрицы, так зачем нужна такая сложная матричная форма?Во-первых, давайте рассмотрим простейший матричный расчет.

\begin{array}{c} H^{(l+1)}=f\left(H^{(l)}, A\right)=\sigma\left(A H^{(l)} W^{(l)}\right) \\ H^{(0)}=X \in R^{n \times d} \end{array}

В приведенной выше формуле W — параметр преобразования свертки, который можно обучить и оптимизировать. Матрица A является матрицей смежности, и если Aij не равно 0, это означает, что вершина i, j является соседом, а ij имеет ребро. H — матрица собственных векторов всех узлов, каждая строка — собственный вектор узла, а H(0) — матрица X. Произведение A и H фактически складывает все векторы соседних узлов, как показано на следующем рисунке, указывая, что $A\times H$ .

\left[\begin{array}{cccc} 0 & 1 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{array}\right]\left[\begin{array}{ccccc} 1 & 1 & 1 & 1 & 1 \\ 2 & 2 & 2 & 2 & 2 \\ 3 & 3 & 3 & 3 & 3 \\ 4 & 4 & 4 & 4 & 4 \end{array}\right]=\left[\begin{array}{ccccc} 5 & 5 & 5 & 5 & 5 \\ 1 & 1 & 1 & 1 & 1 \\ 5 & 5 & 5 & 5 & 5 \\ 3 & 3 & 3 & 3 & 3 \end{array}\right]

$A$ представляет матрицу смежности, $H$ Представляет 4 узла, каждый узел имеет 5-мерный вектор признаков, который будет $А и Н$ Прямое умножение даст результат матрицы AH справа. После получения AH он умножается на параметр обучения W, и, наконец, вектор признаков следующего слоя из 4 узлов получается через функцию активации σ.

Но есть некоторые проблемы с приведенной выше формулой, $AH$ Получается только информация о соседях узла, а информация о самом узле игнорируется. Чтобы решить эту задачу, мы можем преобразовать матрицу $A$ Значение диагональной линии посередине установлено равным 1, то есть каждый узел будет указывать на себя.Новая формула свертки выглядит следующим образом:

\begin{aligned} H^{(l+1)} &=\sigma\left(\tilde{A} H^{(l)} W^{(l)}\right) \\ \tilde{A} &=A+I_{n} \end{aligned}

I — единичная матрица, то есть диагональ равна 1, а остальные — 0. Даже используя приведенную выше формулу свертки, можно учесть информацию о самом узле,Но есть еще проблемы с этой формулой:Матрица A не нормирована, и AH будет складывать векторы всех соседей узла, так что значение собственных векторов некоторых узлов после многослойной свертки будет очень большим. Поскольку матрица смежности не нормализована, это может быть проблематично при извлечении функций графа, например, узлы с большим количеством соседей, как правило, имеют большие собственные значения.Обычно используется метод симметричной нормализации: Нормализация означает, что при агрегировании характеристик узлов-соседей узлового узла

\begin{array}{l} A=D^{-\frac{1}{2}} A D^{-\frac{1}{2}} \\ A_{i j}=\frac{A_{i j}}{\sqrt{d_{i}} \sqrt{d_{j}}} \end{array}

2.3 Подводя итог:

Во-первых, чтобы рассмотреть собственные характеристики всех узлов в A, мы будем $A$ плюс $I$ стать $\tilde{A}$ , а затем для того, чтобы учесть явление, что вектор признаков будет продолжать складываться при агрегировании признаков соседних узлов узла, что приводит к тому явлению, что признаки узлов с большим количеством соседних узлов больше, мы используем симметричная нормализация. Таким образом, можно получить формулу распространения GCN по слоям, $H^{(l+1)}=\sigma\left(\tilde{D}^{-\frac{1}{2}} \tilde{A} \tilde{D}^{-\frac{1}{2}} H^{(l)} W^{(l)}\right)$

Возьмем двухслойную GCN в качестве примера.

\begin{array}{c} \hat{A}=\widetilde{D}^{-\frac{1}{2}} \tilde{A} \widetilde{D}^{-\frac{1}{2}} \\ Z=\operatorname{softmax}\left(\hat{A} \operatorname{ReLu}\left(\hat{A} X W^{(0)}\right) W^{(1)}\right) \end{array}

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

3. Насколько хороша GCN

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

Суммировать

До сих пор мы глубоко понимали связанные концепции GCN, фактически используяКаждое соединение на рисунке не влияет на изменение своего состояния до тех пор, пока сосед и чем дальше точки, тем больше сосед влияет на отношения соседей.Благодаря взаимному влиянию между узлами и обучению матрицы параметров W окончательно изучаются характеристики каждого узла.

При этом количество слоев НКС не должно быть слишком большим., ** Проще говоря, количество слоев gcn сделает вложение каждой точки относительно похожим, что не очень хорошо для функций потерь, таких как классификация узлов позже.Конечно, некоторые эффекты могут быть компенсированы различными нормализациями. С термодинамической точки зрения каждое вложение узла рассматривается как температура узла, а каждая свертка gcn может рассматриваться как теплообмен между каждым узлом и окружающими узлами. При отсутствии внешнего источника тепла (узлы не имеют дополнительных меток), если граф полносвязный, множественные свертки в итоге сделают температуру каждого узла, то есть вложения, одинаковой.

В следующей статье мы обсудим использование DGL для реализации GCN и внедрение GAT.